[gcjx] Patch: FYI: initial type inference code
Tom Tromey
tromey@redhat.com
Tue Oct 18 22:16:00 GMT 2005
I'm checking this in on the gcjx branch.
This is an initial draft of the type inference code. It is not
complete, and in fact there are still many ugly bits. However, I
didn't want to carry around a huge patch for this. This code does
suffice to compile a few simple generic method invocations.
Tom
Index: ChangeLog
from Tom Tromey <tromey@redhat.com>
* model/classinst.hh (model_class_instance::type_map_match_p):
Removed.
* model/method.cc (apply_type_map): Updated.
* model/method.hh (model_method::instance_cache): New field.
* model/class.cc (create_instance): Updated.
* model/class.hh (model_class::instances): Removed.
(model_class::instance_cache): New field.
* model/parameters.cc (find_instance): New method.
(add_instance): Likewise.
* model/parameters.hh (class model_instance_cache): New class.
* model/class.cc (create_type_map): Removed.
(create_instance): Updated.
* model/parameters.hh (model_parameters::create_type_map):
Declare.
* model/parameters.cc (create_type_map): New method.
* model/class.hh (model_class::create_instance): Updated
documentation.
(model_class::create_type_map): Removed.
* model/method.hh (model_method::do_method_conversion_p):
Declare.
(model_method::method_conversion_p): Likewise.
* model/method.cc (do_method_conversion_p): New methods.
(method_conversion_p): Use it. Return a method.
(method_conversion_p): New overload.
* model/invoke.hh (model_invocation_base::compute_type_parameters):
Declare.
* unify.cc: New file.
* unify.hh: New file.
* Makefile.am (headers): Added unify.hh.
(model_sources): Added unify.cc.
* model/classinst.cc (get_type_map): New method.
* model/classinst.hh (model_class_instance::get_type_map): New
overload.
* model/wildcard.hh (model_wildcard::wildcard_p): New method.
(model_wildcard): New constructor.
(model_wildcard::has_bound_p): New method.
* model/class.hh (model_class::get_type_parameters): New method.
(model_class::wildcard_p): Likewise.
* model/parameters.hh (model_parameters::begin): New method.
(model_parameters::end): Likewise.
* model/method.hh (model_method::get_type_parameters): New
method.
* model/classinst.hh (model_class_instance::get_type_map):
Declare.
* model/wildcard.hh (model_wildcard::super_p): New method.
(model_wildcard::get_bound): Likewise.
Index: Makefile.am
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/Attic/Makefile.am,v
retrieving revision 1.1.2.7
diff -u -r1.1.2.7 Makefile.am
--- Makefile.am 12 Oct 2005 19:07:42 -0000 1.1.2.7
+++ Makefile.am 18 Oct 2005 22:13:06 -0000
@@ -74,11 +74,12 @@
reader/zereader.hh reader/mmapbuffer.hh reader/readbuffer.hh \
reader/zebuffer.hh reader/source.hh resolve.hh scope.hh source/lex.hh \
source/machine.hh source/parse.hh source/token.hh source/tstream.hh \
-source/ucs2.hh typedefs.hh util.hh visitor.hh warnings.hh watch.hh
+source/ucs2.hh typedefs.hh unify.hh util.hh visitor.hh warnings.hh \
+watch.hh
dot_sources = access.cc classcache.cc compiler.cc conversions.cc \
defassign.cc directory.cc dump.cc factory.cc fold.cc init.cc \
-location.cc name.cc owner.cc scope.cc util.cc warnings.cc
+location.cc name.cc owner.cc scope.cc unify.cc util.cc warnings.cc
model_sources = model/annotation.cc model/annomember.cc model/annotype.cc \
model/annovalue.cc model/arrayinit.cc model/arrayref.cc \
Index: unify.cc
===================================================================
RCS file: unify.cc
diff -N unify.cc
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ unify.cc 18 Oct 2005 22:13:07 -0000
@@ -0,0 +1,596 @@
+// Type unification.
+
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of GCC.
+//
+// gcjx is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Library General Public
+// License as published by the Free Software Foundation; either
+// version 2 of the License, or (at your option) any later version.
+//
+// gcjx is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Library General Public License for more details.
+//
+// You should have received a copy of the GNU Library General Public
+// License along with gcjx; see the file COPYING.LIB. If
+// not, write to the Free Software Foundation, Inc.,
+// 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+#include "typedefs.hh"
+
+
+// U << V : U convertible to V by method invoc. conv.
+
+/// This class implements the type inference algorithm as explained in
+/// the JLS 3. Names in this class are general chosen to follow the
+/// JLS. Reading the text is strongly advised, this code is not
+/// intended to be easy to follow without having it alongside.
+class unifier
+{
+ typedef std::list< std::pair<model_class *, model_class *> > constraint_list;
+
+ typedef std::map< model_class *, std::set<model_class_instance *> >
+ inv_map_type;
+
+ // Inferred constraints; indexed by constraint_type.
+ constraint_list constraints[3];
+
+ std::map<model_class *, model_class *> mapping;
+
+ // The formal type parameters for the method.
+ std::set<model_type_variable *> formal_type_params;
+
+ // This is used to avoid memory leaks when creating temporary
+ // wildcards and other objects during unification.
+ std::list<ref_element> gcpro;
+
+ // Location we should use when creating things.
+ location where;
+
+ typedef enum
+ {
+ LESS_THAN = 0,
+ EQUAL = 1,
+ GREATER_THAN = 2
+ } constraint_type;
+
+ static constraint_type invert (constraint_type t)
+ {
+ if (t == LESS_THAN)
+ return GREATER_THAN;
+ if (t == GREATER_THAN)
+ return LESS_THAN;
+ return EQUAL;
+ }
+
+ void imply (constraint_type type, model_class *formal, model_class *actual)
+ {
+ constraints[type].push_back (std::make_pair (formal, actual));
+ }
+
+ bool formal_type_variable_p (model_class *klass)
+ {
+ model_type_variable *tv = dynamic_cast<model_type_variable *> (klass);
+ return (tv != NULL
+ && formal_type_params.find (tv) != formal_type_params.end ());
+ }
+
+ // Compute the supertype set and the erased supertype set.
+ void compute_supertype_sets (model_class *klass,
+ std::set<model_class *> &st,
+ std::set<model_class *> &est)
+ {
+ while (klass != NULL)
+ {
+ st.insert (klass);
+ est.insert (assert_cast<model_class *> (klass->erasure ()));
+ std::list<ref_forwarding_type> ifaces (klass->get_interfaces ());
+ for (std::list<ref_forwarding_type>::const_iterator i
+ = ifaces.begin ();
+ i != ifaces.end ();
+ ++i)
+ compute_supertype_sets (assert_cast<model_class *> ((*i)->type ()),
+ st, est);
+ klass = klass->get_superclass ();
+ }
+ }
+
+ // Compute the erased candidate set and the complete supertype set.
+ void compute_ec (const std::set<model_class *> &types,
+ std::set<model_class *> &ec,
+ std::set<model_class *> &st)
+ {
+ bool first = true;
+ for (std::set<model_class *>::const_iterator i = types.begin ();
+ i != types.end ();
+ ++i)
+ {
+ std::set<model_class *> inter, newset;
+ compute_supertype_sets (*i, st, inter);
+ if (! first)
+ std::set_intersection (ec.begin (), ec.end (),
+ inter.begin (), inter.end (),
+ std::inserter (newset, newset.begin ()));
+ ec = newset;
+ first = false;
+ }
+ }
+
+ // Computed the minimal erased candidate set.
+ void compute_mec (const std::set<model_class *> &ec,
+ std::set<model_class *> &mec)
+ {
+ for (std::set<model_class *>::const_iterator i = ec.begin ();
+ i != ec.end ();
+ ++i)
+ {
+ bool found = false;
+ for (std::set<model_class *>::const_iterator j = ec.begin ();
+ j != ec.end ();
+ ++j)
+ {
+ // Don't compare to self.
+ if (*i == *j)
+ continue;
+ if ((*i)->assignable_from_p (*j))
+ {
+ found = true;
+ break;
+ }
+ }
+ if (! found)
+ mec.insert (*i);
+ }
+ }
+
+ // Compute the invocation sets, given a set of input types.
+ void compute_inv (const std::set<model_class *> &input_types,
+ inv_map_type &invocation_map)
+ {
+ std::set<model_class *> ec, st, mec;
+ compute_ec (input_types, ec, st);
+ compute_mec (ec, mec);
+
+ for (std::set<model_class *>::const_iterator i = mec.begin ();
+ i != mec.end ();
+ ++i)
+ {
+ if ((*i)->get_type_parameters ().empty ())
+ continue;
+
+ std::set<model_class_instance *> one_inv;
+ for (std::set<model_class *>::const_iterator j = st.begin ();
+ j != st.end ();
+ ++j)
+ {
+ model_class_instance *ci
+ = dynamic_cast<model_class_instance *> (*j);
+ if (ci != NULL && ci->get_parent () == *i)
+ one_inv.insert (ci);
+ }
+
+ invocation_map[*i] = one_inv;
+ }
+ }
+
+ model_class *compute_glb (model_class *left, model_class *right)
+ {
+ // FIXME
+ return left;
+ }
+
+ // Compute the least containing type argument for a pair of classes.
+ model_class *compute_lcta (model_class *left, model_class *right)
+ {
+ model_class *result;
+ if (left->wildcard_p () && right->wildcard_p ())
+ {
+ model_wildcard *leftw = assert_cast<model_wildcard *> (left);
+ model_wildcard *rightw = assert_cast<model_wildcard *> (right);
+ model_class *lbound = leftw->get_bound ();
+ model_class *rbound = rightw->get_bound ();
+
+ if (leftw->super_p ())
+ {
+ assert (rightw->super_p ()); // FIXME
+ result = new model_wildcard (where, compute_glb (lbound, rbound),
+ true);
+ }
+ else if (rightw->super_p ())
+ {
+ if (lbound == rbound)
+ result = lbound;
+ else
+ result = new model_wildcard (where);
+ }
+ else
+ result = new model_wildcard (where, compute_lub (lbound, rbound));
+ }
+ else if (right->wildcard_p ())
+ {
+ model_wildcard *rw = assert_cast<model_wildcard *> (right);
+ model_class *rbound = rw->get_bound ();
+ model_class *new_bound;
+ if (rw->super_p ())
+ new_bound = compute_glb (left, rbound);
+ else
+ new_bound = compute_lub (left, rbound);
+ result = new model_wildcard (where, new_bound, rw->super_p ());
+ gcpro.push_back (result);
+ }
+ else if (left == right)
+ result = left;
+ else
+ {
+ model_class *lub = compute_lub (left, right);
+ result = new model_wildcard (where, lub);
+ gcpro.push_back (result);
+ }
+ return result;
+ }
+
+ // Compute the least containing invocation given an invocation set.
+ model_class *compute_lci (const std::set<model_class_instance *> &inv)
+ {
+ assert (! inv.empty ());
+ model_class *outer = NULL;
+ std::list<model_class *> current;
+ for (std::set<model_class_instance *>::const_iterator i = inv.begin ();
+ i != inv.end ();
+ ++i)
+ {
+ model_class_instance *ci = *i;
+ if (outer == NULL)
+ {
+ // First time through.
+ outer = ci->get_parent ();
+ ci->get_type_map (current);
+ continue;
+ }
+
+ assert (outer == ci->get_parent ());
+
+ std::list<model_class *> ci_params;
+ ci->get_type_map (ci_params);
+
+ std::list<model_class *> nextparams;
+ std::list<model_class *>::const_iterator it1 = current.begin ();
+ std::list<model_class *>::const_iterator it2 = ci_params.begin ();
+ while (it1 != current.end ())
+ {
+ nextparams.push_back (compute_lcta (*it1, *it2));
+ ++it1;
+ ++it2;
+ }
+ assert (it2 == ci_params.end ());
+
+ current = nextparams;
+ }
+
+ assert (outer != NULL);
+ return outer->create_instance (outer /* FIXME */, current);
+ }
+
+ // This name comes from the JLS.
+ model_class *compute_lub (const std::set<model_class *> &constraints)
+ {
+ inv_map_type inv_map;
+ compute_inv (constraints, inv_map);
+
+ model_class *result = NULL;
+
+ for (inv_map_type::const_iterator i = inv_map.begin ();
+ i != inv_map.end ();
+ ++i)
+ {
+ model_class *arg = (*i).first;
+ const std::set<model_class_instance *> &inv = (*i).second;
+ if (! arg->get_type_parameters ().empty ())
+ arg = compute_lci (inv);
+ // FIXME: this is wrong, we need to compute a bound.
+ result = arg;
+ }
+
+ return result;
+ }
+
+ model_class *compute_lub (model_class *one, model_class *two)
+ {
+ std::set<model_class *> constraints;
+ constraints.insert (one);
+ constraints.insert (two);
+ return compute_lub (constraints);
+ }
+
+ model_class *conforming_array_type (model_class *actual)
+ {
+ if (actual->array_p ())
+ {
+ // Maybe.
+ }
+ // FIXME: is the erasure correct here?
+ // We actually want the upper bound.
+ else if (actual->erasure ()->array_p ())
+ actual = assert_cast<model_class *> (actual->erasure ());
+ else
+ return NULL;
+ actual = assert_cast<model_class *> (actual->element_type ());
+ return actual->reference_p () ? actual : NULL;
+ }
+
+ void unify (constraint_type constraint, model_type *actual_in,
+ model_class *formal)
+ {
+ if (actual_in == null_type)
+ {
+ // Nothing to do.
+ return;
+ }
+
+ if (actual_in->primitive_p ())
+ {
+ if (constraint == LESS_THAN)
+ actual_in = boxing_conversion (actual_in);
+ else
+ {
+ // Nothing to do.
+ return;
+ }
+ }
+
+ model_class *actual;
+ actual = assert_cast<model_class *> (actual_in);
+
+ // Note that we could see a type variable here that is not one of
+ // the formal variables of the method in question, for instance if
+ // this method is in a generic class.
+ if (formal_type_variable_p (formal))
+ {
+ imply (invert (constraint), formal, actual);
+ return;
+ }
+
+ model_class *elt;
+ if (formal->array_p () && (elt = conforming_array_type (actual)))
+ {
+ unify (constraint, elt,
+ assert_cast<model_class *> (formal->element_type ()));
+ return;
+ }
+
+ if (! formal->parameterized_p ())
+ {
+ // No constraint implied.
+ return;
+ }
+ model_class_instance *formalci
+ = assert_cast<model_class_instance *> (formal);
+ model_class_instance *actualci
+ = assert_cast<model_class_instance *> (actual);
+
+ // FIXME: check that ACTUAL "inherits from FORMAL's erasure".
+ // For '<' case only.
+
+ std::list<model_class *> formal_map, actual_map;
+ formalci->get_type_map (formal_map);
+ actualci->get_type_map (actual_map);
+
+ std::list<model_class *>::const_iterator i_f = formal_map.begin ();
+ std::list<model_class *>::const_iterator i_a = actual_map.begin ();
+ while (i_f != formal_map.end ())
+ {
+ model_class *inner_f = *i_f;
+ model_wildcard *inner_f_w = dynamic_cast<model_wildcard *> (inner_f);
+ model_class *inner_a = *i_a;
+ model_wildcard *inner_a_w = dynamic_cast<model_wildcard *> (inner_a);
+
+ if (! inner_f->wildcard_p ())
+ {
+ if (constraint == GREATER_THAN)
+ {
+ // FIXME.
+ }
+ else
+ unify (EQUAL, inner_a, inner_f);
+ }
+ else if (inner_f_w->super_p ())
+ {
+ if (inner_a->wildcard_p ())
+ {
+ if (inner_a_w->super_p ())
+ unify (GREATER_THAN, inner_a, inner_f);
+ }
+ else
+ unify (GREATER_THAN, inner_a, inner_f);
+ }
+ else if (inner_f_w->has_bound_p ())
+ {
+ // 'extends' wildcard.
+ if (inner_a->wildcard_p ())
+ {
+ if (! inner_a_w->super_p () && inner_a_w->has_bound_p ())
+ unify (LESS_THAN, inner_a, inner_f);
+ }
+ else
+ unify (LESS_THAN, inner_a, inner_f);
+ }
+
+ ++i_a;
+ ++i_f;
+ }
+ assert (i_a == actual_map.end ());
+ }
+
+ model_class *maybe_map (const std::map<model_class *, model_class *> &themap,
+ model_class *type)
+ {
+ std::map<model_class *, model_class *>::const_iterator i
+ = themap.find (type);
+ if (i == themap.end ())
+ return type;
+ return (*i).second;
+ }
+
+ void update_map (std::map<model_class *, model_class *> &themap,
+ model_class *from, model_class *to)
+ {
+ // FIXME: what if we have an existing OLD->FROM mapping?
+ // FIXME: and what if we create a loop?
+ themap[from] = to;
+ }
+
+ void consider_equality ()
+ {
+ constraint_list &eq = constraints[EQUAL];
+ for (constraint_list::const_iterator i = eq.begin ();
+ i != eq.end ();
+ ++i)
+ {
+ model_class *left = maybe_map (mapping, (*i).first);
+ model_class *right = maybe_map (mapping, (*i).second);
+
+ // Ignore identities.
+ if (left == right)
+ continue;
+
+ if (formal_type_variable_p (right))
+ std::swap (left, right);
+ // Due to mapping we might see two non-type variables here.
+ // That is an error as it means there are inconsistent
+ // constraints.
+ if (! formal_type_variable_p (left))
+ abort (); // FIXME
+
+ // If both happen to be type variables, either mapping will
+ // do.
+ update_map (mapping, left, right);
+ }
+ }
+
+ bool mapping_complete_p ()
+ {
+ for (std::set<model_type_variable *>::const_iterator i
+ = formal_type_params.begin ();
+ i != formal_type_params.end ();
+ ++i)
+ {
+ if (mapping.find (*i) == mapping.end ())
+ return false;
+ }
+ return true;
+ }
+
+ void update_constraint_set (constraint_type type,
+ model_type_variable *var,
+ std::set<model_class *> &result)
+ {
+ for (constraint_list::const_iterator i = constraints[type].begin ();
+ i != constraints[type].end ();
+ ++i)
+ {
+ model_class *first = (*i).first;
+ model_class *second = (*i).second;
+ result.insert (first == var ? second : first);
+ }
+ }
+
+ void resolve_constraints (model_type_map &result)
+ {
+ consider_equality ();
+ for (std::set<model_type_variable *>::const_iterator i
+ = formal_type_params.begin ();
+ i != formal_type_params.end ();
+ ++i)
+ {
+ if (mapping.find (*i) == mapping.end ())
+ {
+ // FIXME: should we check the other constraints too?
+ continue;
+ }
+
+ std::set<model_class *> constraints;
+ update_constraint_set (LESS_THAN, *i, constraints);
+ update_constraint_set (GREATER_THAN, *i, constraints);
+ result.add (*i, compute_lub (constraints));
+ }
+ }
+
+ void get_formal_argument_types (model_method *method,
+ std::list<model_type *> &formal)
+ {
+ std::list<ref_variable_decl> formal_v = method->get_parameters ();
+ for (std::list<ref_variable_decl>::const_iterator i = formal_v.begin ();
+ i != formal_v.end ();
+ ++i)
+ formal.push_back ((*i)->type ());
+ }
+
+ void get_formal_type_parameters (model_method *method)
+ {
+ const model_parameters ¶ms = method->get_type_parameters ();
+ for (std::list<ref_type_variable>::const_iterator i = params.begin ();
+ i != params.end ();
+ ++i)
+ formal_type_params.insert ((*i).get ());
+ assert (! formal_type_params.empty ());
+ }
+
+public:
+
+ void unify (const std::list<model_type *> &actual, model_method *method,
+ model_type_map &result)
+ {
+ std::list<model_type *> formal;
+ get_formal_argument_types (method, formal);
+ get_formal_type_parameters (method);
+
+ std::list<model_type *>::const_iterator ai = actual.begin ();
+ std::list<model_type *>::const_iterator fi = formal.begin ();
+
+ // FIXED_FORMAL is used when processing a varargs call.
+ model_type *fixed_formal = NULL;
+
+ while (ai != actual.end ()
+ && (fixed_formal || fi != formal.end ()))
+ {
+ model_type *ft;
+ model_type *at = *ai++;
+
+ if (fixed_formal)
+ ft = fixed_formal;
+ else
+ {
+ ft = *fi++;
+ if (method->varargs_p () && fi == formal.end ())
+ {
+ // The type of the last formal argument must be an
+ // array type. Every subsequent actual argument must
+ // now be unified against the element type of the
+ // array.
+ fixed_formal = ft->element_type ();
+ ft = fixed_formal;
+ }
+ }
+
+ // It doesn't make sense to unify against a formal argument
+ // with primitive type (?).
+ if (! ft->primitive_p ())
+ unify (LESS_THAN, at, assert_cast<model_class *> (ft));
+ }
+
+ resolve_constraints (result);
+ }
+};
+
+void
+unify (const std::list<model_type *> &actual,
+ model_method *method,
+ model_class *assignment_type,
+ model_type_map &result)
+{
+ unifier u;
+ u.unify (actual, method, result);
+}
Index: unify.hh
===================================================================
RCS file: unify.hh
diff -N unify.hh
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ unify.hh 18 Oct 2005 22:13:07 -0000
@@ -0,0 +1,39 @@
+// Type unification.
+
+// Copyright (C) 2005 Free Software Foundation, Inc.
+//
+// This file is part of GCC.
+//
+// gcjx is free software; you can redistribute it and/or
+// modify it under the terms of the GNU Library General Public
+// License as published by the Free Software Foundation; either
+// version 2 of the License, or (at your option) any later version.
+//
+// gcjx is distributed in the hope that it will be useful,
+// but WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
+// Library General Public License for more details.
+//
+// You should have received a copy of the GNU Library General Public
+// License along with gcjx; see the file COPYING.LIB. If
+// not, write to the Free Software Foundation, Inc.,
+// 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+
+#ifndef GCJX_UNIFY_HH
+#define GCJX_UNIFY_HH
+
+/// Perform type inference according to the algorithm in the JLS.
+/// @param actual the actual argument types
+/// @param method the method being invoked
+/// @param assignment_type if not null, the type to which the result
+/// of this method is converted by assignment conversion. If no
+/// assignment conversion is performed, should be NULL.
+/// @param result the resulting actual argument types
+/// FIXME: actual result type ... ?
+void
+unify (const std::list<model_type *> &actual,
+ model_method *method,
+ model_class *assignment_type,
+ model_type_map &result);
+
+#endif // GCJX_UNIFY_HH
Index: model/class.cc
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/class.cc,v
retrieving revision 1.1.2.16
diff -u -r1.1.2.16 class.cc
--- model/class.cc 12 Oct 2005 19:07:42 -0000 1.1.2.16
+++ model/class.cc 18 Oct 2005 22:13:08 -0000
@@ -1998,35 +1998,6 @@
}
void
-model_class::create_type_map (model_type_map &result,
- model_element *request,
- const std::list<model_class *> &type_list)
-{
- std::list<model_class *>::const_iterator type_iter
- = type_list.begin ();
- std::list<ref_type_variable>::const_iterator var_iter
- = type_parameters.type_parameters.begin ();
-
- while (type_iter != type_list.end ()
- && var_iter != type_parameters.type_parameters.end ())
- {
- (*var_iter)->validate (request, *type_iter);
- result.add ((*var_iter).get (), *type_iter);
- ++type_iter;
- ++var_iter;
- }
-
- if (type_iter == type_list.end ()
- && var_iter != type_parameters.type_parameters.end ())
- throw request->error ("too few type parameters to %1")
- % this;
- else if (type_iter != type_list.end ()
- && var_iter == type_parameters.type_parameters.end ())
- throw request->error ("too many type parameters to %1")
- % this;
-}
-
-void
model_class::check_interface_instances (model_class *base,
std::map<model_class *, model_class *> &track)
{
@@ -2078,19 +2049,15 @@
const std::list<model_class *> ¶ms)
{
model_type_map type_map;
- create_type_map (type_map, request, params);
+ type_parameters.create_type_map (type_map, request, params);
if (type_parameters.empty () || type_map.empty_p ())
return this;
// See if this instance has been cached.
- for (std::list<ref_class_instance>::const_iterator i = instances.begin ();
- i != instances.end ();
- ++i)
- {
- if ((*i)->type_map_match_p (type_map))
- return (*i).get ();
- }
+ model_class_instance *cache = instance_cache.find_instance (type_map);
+ if (cache != NULL)
+ return cache;
// We need to have our superclasses installed before we can proceed.
resolve_classes ();
@@ -2145,7 +2112,7 @@
if (this_0)
result->set_this_0 (this_0);
- instances.push_back (result);
+ instance_cache.add_instance (type_map, result);
return result.get ();
}
Index: model/class.hh
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/class.hh,v
retrieving revision 1.1.2.6
diff -u -r1.1.2.6 class.hh
--- model/class.hh 12 Oct 2005 19:07:42 -0000 1.1.2.6
+++ model/class.hh 18 Oct 2005 22:13:08 -0000
@@ -61,7 +61,6 @@
/// all the needed functionality (fields, methods, etc). It also
/// knows the inheritance rules and other things like that.
///
-
/// A model_class is also used as the type of a class. In particular,
/// for ordinary classes, the model_class is both the declaration and
/// the type. For generic classes, the model_class is the declaration
@@ -181,8 +180,8 @@
// The 'class$' method, if one is needed.
ref_method class_;
- // List of all class instances.
- std::list<ref_class_instance> instances;
+ // All the instances of this class.
+ model_instance_cache<model_class_instance> instance_cache;
// This holds any accessor methods we had to create. This maps the
// referenced member to the accessor.
@@ -305,6 +304,11 @@
type_parameters = tps;
}
+ const model_parameters &get_type_parameters () const
+ {
+ return type_parameters;
+ }
+
void set_name (const std::string &n)
{
name = n;
@@ -471,6 +475,12 @@
return false;
}
+ // Return true if this class is a wildcard class.
+ virtual bool wildcard_p () const
+ {
+ return false;
+ }
+
// Return true if this class was defined in a static context.
bool static_context_p () const
{
@@ -584,10 +594,6 @@
used = true;
}
- /// Construct a new type map for this class given a list of types.
- void create_type_map (model_type_map &, model_element *,
- const std::list<model_class *> &);
-
/// Apply the type map to this generic type and return a
/// parameterized instance. Multiple calls to this with the
/// equivalent type map will all return the same result.
@@ -595,7 +601,9 @@
const model_type_map &);
/// Create a parameterized instance of this class given a list of
- /// argument types.
+ /// argument types. This should only be called on a model_class,
+ /// not on an instance of a subclass; to apply a type map
+ /// composition, use apply_type_map.
model_class *create_instance (model_element *,
const std::list<model_class *> &);
Index: model/classinst.cc
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/classinst.cc,v
retrieving revision 1.1.2.2
diff -u -r1.1.2.2 classinst.cc
--- model/classinst.cc 12 Oct 2005 19:07:42 -0000 1.1.2.2
+++ model/classinst.cc 18 Oct 2005 22:13:08 -0000
@@ -69,6 +69,16 @@
}
}
+void
+model_class_instance::get_type_map (std::list<model_class *> &result)
+{
+ for (std::list<ref_type_variable>::const_iterator i
+ = type_parameters.begin ();
+ i != type_parameters.end ();
+ ++i)
+ result.push_back (type_map.find ((*i).get ()));
+}
+
model_class *
model_class_instance::apply_type_map (model_element *request,
const model_type_map &other_type_map)
Index: model/classinst.hh
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/classinst.hh,v
retrieving revision 1.1.2.2
diff -u -r1.1.2.2 classinst.hh
--- model/classinst.hh 12 Oct 2005 19:07:42 -0000 1.1.2.2
+++ model/classinst.hh 18 Oct 2005 22:13:08 -0000
@@ -48,13 +48,6 @@
{
}
- /// Return true if the given type map is an exact match for our type
- /// map. This is used to cache class instances.
- bool type_map_match_p (const model_type_map &other) const
- {
- return type_map == other;
- }
-
bool parameterized_p () const
{
return true;
@@ -65,6 +58,15 @@
return parent;
}
+ const model_type_map &get_type_map () const
+ {
+ return type_map;
+ }
+
+ // Retrieve the type map in "argument form" -- in the same order as
+ // the parameters given when instantiating this class.
+ void get_type_map (std::list<model_class *> &result);
+
model_class *apply_type_map (model_element *, const model_type_map &);
// FIXME: could have covariant return here..
Index: model/invoke.cc
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/invoke.cc,v
retrieving revision 1.1.2.8
diff -u -r1.1.2.8 invoke.cc
--- model/invoke.cc 14 Oct 2005 22:04:40 -0000 1.1.2.8
+++ model/invoke.cc 18 Oct 2005 22:13:08 -0000
@@ -58,9 +58,13 @@
i != accessible.end ();
++i)
{
- if (potentially_applicable_p (*i, actual_types)
- && (*i)->method_conversion_p (actual_types, phase))
- applicable.insert (*i);
+ if (potentially_applicable_p (*i, actual_types))
+ {
+ model_method *newmeth
+ = (*i)->method_conversion_p (actual_types, phase);
+ if (newmeth)
+ applicable.insert (newmeth);
+ }
}
if (! should_loop)
break;
Index: model/method.cc
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/method.cc,v
retrieving revision 1.1.2.7
diff -u -r1.1.2.7 method.cc
--- model/method.cc 14 Oct 2005 22:04:40 -0000 1.1.2.7
+++ model/method.cc 18 Oct 2005 22:13:08 -0000
@@ -22,6 +22,7 @@
#include "typedefs.hh"
#include "defassign.hh"
#include "dump.hh"
+#include "unify.hh"
// FIXME this should probably be a method on model_type.
// FIXME duplicated in throwsclause.cc
@@ -170,9 +171,9 @@
return potentially_applicable_p (args);
}
-bool
-model_method::method_conversion_p (const std::list<model_type *> &args,
- method_phase phase)
+model_method *
+model_method::do_method_conversion_p (const std::list<model_type *> &args,
+ method_phase phase)
{
std::list<ref_variable_decl>::const_iterator this_it
= parameters.begin ();
@@ -202,7 +203,7 @@
++args_it;
if (! method_invocation_conversion (formal_type, actual_type, phase))
- return false;
+ return NULL;
}
// Actually handle varargs. We do this here because it is valid for
@@ -226,18 +227,53 @@
model_type *actual_type = *args_it;
if (! method_invocation_conversion (formal_type, actual_type,
phase))
- return false;
+ return NULL;
++args_it;
}
- return true;
+ return this;
}
// Wrong number of arguments.
if (this_it != parameters.end () || args_it != args.end ())
- return false;
+ return NULL;
- return true;
+ return this;
+}
+
+model_method *
+model_method::do_method_conversion_p (const model_type_map &typeargs,
+ const std::list<model_type *> &args,
+ method_phase phase)
+{
+ model_method *new_meth = apply_type_map (typeargs, get_declaring_class ());
+ return new_meth->do_method_conversion_p (args, phase);
+}
+
+model_method *
+model_method::method_conversion_p (const std::list<model_type *> &args,
+ method_phase phase)
+{
+ if (! type_parameters.empty ())
+ {
+ model_type_map typeargs;
+ // FIXME: return result..? error detection?
+ // FIXME: pass in argument for varargs handling.
+ unify (args, this, NULL /* FIXME */, typeargs);
+ return do_method_conversion_p (typeargs, args, phase);
+ }
+ return do_method_conversion_p (args, phase);
+}
+
+model_method *
+model_method::method_conversion_p (const std::list<model_class *> &typeargs,
+ const std::list<model_type *> &args,
+ method_phase phase)
+{
+ model_type_map the_map;
+ // FIXME: error handling?
+ type_parameters.create_type_map (the_map, this /* FIXME */, typeargs);
+ return do_method_conversion_p (the_map, args, phase);
}
void
@@ -762,8 +798,15 @@
model_class *enclosing)
{
// FIXME: if argument and return types don't change, perhaps we
- // should just return 'this'.
- return new model_method (this, type_map, enclosing);
+ // should just return 'this'?
+
+ model_method *cache = instance_cache.find_instance (type_map);
+ if (cache != NULL)
+ return cache;
+
+ model_method *result = new model_method (this, type_map, enclosing);
+ instance_cache.add_instance (type_map, result);
+ return result;
}
Index: model/method.hh
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/method.hh,v
retrieving revision 1.1.2.6
diff -u -r1.1.2.6 method.hh
--- model/method.hh 14 Oct 2005 22:04:40 -0000 1.1.2.6
+++ model/method.hh 18 Oct 2005 22:13:08 -0000
@@ -84,8 +84,16 @@
// this is used by GCC for debugging information.
location method_end;
+ // All generic instantiations of this method.
+ model_instance_cache<model_method> instance_cache;
+
void massage_modifiers (const ref_modifier_list &);
bool return_type_substitutable_p (model_type *, model_type *) const;
+ model_method *do_method_conversion_p (const std::list<model_type *> &,
+ method_phase);
+ model_method *do_method_conversion_p (const model_type_map &,
+ const std::list<model_type *> &,
+ method_phase);
annotation_kind get_annotation_kind () const
{
@@ -213,6 +221,11 @@
type_parameters = ts;
}
+ const model_parameters &get_type_parameters () const
+ {
+ return type_parameters;
+ }
+
void set_return_type (const ref_forwarding_type &t)
{
return_type = t;
@@ -263,10 +276,19 @@
// Return TRUE if this method is more specific than OTHER.
bool more_specific_p (model_method *other);
- /// Return TRUE if arguments of the given types can be passed to
- /// this method. The phase determines what kinds of conversions are
- /// considered.
- bool method_conversion_p (const std::list<model_type *> &, method_phase);
+ /// Return the method if arguments of the given types can be passed
+ /// to this method. The phase determines what kinds of conversions
+ /// are considered. The returned method might differ from 'this' if
+ /// a generic instance is created.
+ model_method *method_conversion_p (const std::list<model_type *> &,
+ method_phase);
+
+ /// Like the above, but handles method conversion in the case where
+ /// there are explicit type parameters to the invocation of a
+ /// generic method.
+ model_method *method_conversion_p (const std::list<model_class *> &,
+ const std::list<model_type *> &,
+ method_phase);
/// Like the above, but wrap actual arguments in casts as
/// appropriate. Note that there is no phase argument here; when
Index: model/parameters.cc
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/parameters.cc,v
retrieving revision 1.1.2.1
diff -u -r1.1.2.1 parameters.cc
--- model/parameters.cc 13 Jan 2005 03:18:36 -0000 1.1.2.1
+++ model/parameters.cc 18 Oct 2005 22:13:08 -0000
@@ -71,6 +71,32 @@
&& other_it == other.type_parameters.end ());
}
+void
+model_parameters::create_type_map (model_type_map &result,
+ model_element *request,
+ const std::list<model_class *> &type_list)
+{
+ std::list<model_class *>::const_iterator type_iter
+ = type_list.begin ();
+ std::list<ref_type_variable>::const_iterator var_iter
+ = type_parameters.begin ();
+
+ while (type_iter != type_list.end () && var_iter != type_parameters.end ())
+ {
+ (*var_iter)->validate (request, *type_iter);
+ result.add ((*var_iter).get (), *type_iter);
+ ++type_iter;
+ ++var_iter;
+ }
+
+ if (type_iter == type_list.end () && var_iter != type_parameters.end ())
+ throw request->error ("too few type parameters to %1")
+ % "FIXME";
+ else if (type_iter != type_list.end () && var_iter == type_parameters.end ())
+ throw request->error ("too many type parameters to %1")
+ % "FIXME";
+}
+
std::string
model_parameters::get_pretty_name () const
{
@@ -105,3 +131,34 @@
}
return result;
}
+
+
+
+template<typename T>
+T *
+model_instance_cache<T>::find_instance (const model_type_map &type_map)
+{
+ for (typename data_type::const_iterator i = instances.begin ();
+ i != instances.end ();
+ ++i)
+ {
+ if ((*i).first == type_map)
+ return (*i).second.get ();
+ }
+
+ return NULL;
+}
+
+template<typename T>
+void
+model_instance_cache<T>::add_instance (const model_type_map &type_map,
+ const owner<T> &instance)
+{
+ instances.push_back (std::make_pair (type_map, instance));
+}
+
+
+
+// Instantiations.
+template class model_instance_cache<model_class_instance>;
+template class model_instance_cache<model_method>;
Index: model/parameters.hh
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/parameters.hh,v
retrieving revision 1.1.2.2
diff -u -r1.1.2.2 parameters.hh
--- model/parameters.hh 14 Oct 2005 22:04:40 -0000 1.1.2.2
+++ model/parameters.hh 18 Oct 2005 22:13:08 -0000
@@ -45,6 +45,16 @@
type_parameters = ts;
}
+ std::list<ref_type_variable>::const_iterator begin () const
+ {
+ return type_parameters.begin ();
+ }
+
+ std::list<ref_type_variable>::const_iterator end () const
+ {
+ return type_parameters.end ();
+ }
+
bool empty () const
{
return type_parameters.empty ();
@@ -60,6 +70,9 @@
/// otherwise.
bool create_type_map (model_type_map &, const model_parameters &) const;
+ void create_type_map (model_type_map &, model_element *,
+ const std::list<model_class *> &);
+
void resolve_classes (resolution_scope *scope);
void look_up_name (const std::string &name,
@@ -75,4 +88,27 @@
std::string get_signature ();
};
+/// This is a cache of instances of a given class, either a
+/// model_class_instance or a model_method.
+template<typename T>
+class model_instance_cache
+{
+ // FIXME: this implies copying the type map...
+ typedef std::list< std::pair< model_type_map, owner<T> > >
+ data_type;
+
+ // List of all the known instances.
+ data_type instances;
+
+public:
+
+ /// Look up an instantiation. If the element is found in the cache,
+ /// returns it. Otherwise, returns NULL.
+ T *find_instance (const model_type_map &type_map);
+
+ /// Add an element to the cache.
+ void add_instance (const model_type_map &type_map,
+ const owner<T> &instance);
+};
+
#endif // GCJX_MODEL_PARAMETERS_HH
Index: model/wildcard.hh
===================================================================
RCS file: /cvs/gcc/gcc/gcjx/model/Attic/wildcard.hh,v
retrieving revision 1.1.2.2
diff -u -r1.1.2.2 wildcard.hh
--- model/wildcard.hh 12 Oct 2005 19:07:42 -0000 1.1.2.2
+++ model/wildcard.hh 18 Oct 2005 22:13:08 -0000
@@ -44,6 +44,13 @@
{
}
+ model_wildcard (const location &w, model_class *b, bool spr = false)
+ : model_class (w),
+ is_super (spr),
+ bound (new model_forwarding_resolved (w, b))
+ {
+ }
+
void set_bound (const ref_forwarding_type &b)
{
bound = b;
@@ -54,6 +61,28 @@
is_super = true;
}
+ bool super_p () const
+ {
+ return is_super;
+ }
+
+ bool wildcard_p () const
+ {
+ return true;
+ }
+
+ model_class *get_bound () const
+ {
+ if (! bound)
+ return NULL;
+ return assert_cast<model_class *> (bound->type ());
+ }
+
+ bool has_bound_p () const
+ {
+ return bool (bound);
+ }
+
model_type *erasure ();
bool assignable_from_p (model_type *);
More information about the Java-patches
mailing list