X-Git-Url: http://nitlanguage.org diff --git a/src/model/model.nit b/src/model/model.nit index 168de18..ae55960 100644 --- a/src/model/model.nit +++ b/src/model/model.nit @@ -32,6 +32,7 @@ module model import poset import location import model_base +private import more_collections redef class Model # All known classes @@ -139,6 +140,7 @@ redef class MModule for m in self.in_importation.greaters do for cd in m.mclassdefs do var c = cd.mclass + res.add_node(c) for s in cd.supertypes do res.add_edge(c, s.mclass) end @@ -148,6 +150,31 @@ redef class MModule return res end + # Sort a given array of classes using the linerarization order of the module + # The most general is first, the most specific is last + fun linearize_mclasses(mclasses: Array[MClass]) + do + self.flatten_mclass_hierarchy.sort(mclasses) + end + + # Sort a given array of class definitions using the linerarization order of the module + # the refinement link is stronger than the specialisation link + # The most general is first, the most specific is last + fun linearize_mclassdefs(mclassdefs: Array[MClassDef]) + do + var sorter = new MClassDefSorter(self) + sorter.sort(mclassdefs) + end + + # Sort a given array of property definitions using the linerarization order of the module + # the refinement link is stronger than the specialisation link + # The most general is first, the most specific is last + fun linearize_mpropdefs(mpropdefs: Array[MPropDef]) + do + var sorter = new MPropDefSorter(self) + sorter.sort(mpropdefs) + end + private var flatten_mclass_hierarchy_cache: nullable POSet[MClass] = null # The primitive type Object, the root of the class hierarchy @@ -200,25 +227,55 @@ redef class MModule end # Try to get the primitive method named `name' on the type `recv' - fun try_get_primitive_method(name: String, recv: MType): nullable MMethod + fun try_get_primitive_method(name: String, recv: MClass): nullable MMethod do var props = self.model.get_mproperties_by_name(name) if props == null then return null var res: nullable MMethod = null for mprop in props do assert mprop isa MMethod - if not recv.has_mproperty(self, mprop) then continue - if res == null then - res = mprop - else - print("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}") - abort + var intro = mprop.intro_mclassdef + for mclassdef in recv.mclassdefs do + if not self.in_importation.greaters.has(mclassdef.mmodule) then continue + if not mclassdef.in_hierarchy.greaters.has(intro) then continue + if res == null then + res = mprop + else if res != mprop then + print("Fatal Error: ambigous property name '{name}'; conflict between {mprop.full_name} and {res.full_name}") + abort + end end end return res end end +private class MClassDefSorter + super AbstractSorter[MClassDef] + var mmodule: MModule + redef fun compare(a, b) + do + var ca = a.mclass + var cb = b.mclass + if ca != cb then return mmodule.flatten_mclass_hierarchy.compare(ca, cb) + return mmodule.model.mclassdef_hierarchy.compare(a, b) + end +end + +private class MPropDefSorter + super AbstractSorter[MPropDef] + var mmodule: MModule + redef fun compare(pa, pb) + do + var a = pa.mclassdef + var b = pb.mclassdef + var ca = a.mclass + var cb = b.mclass + if ca != cb then return mmodule.flatten_mclass_hierarchy.compare(ca, cb) + return mmodule.model.mclassdef_hierarchy.compare(a, b) + end +end + # A named class # # MClass are global to the model; it means that a MClass is not bound to a @@ -381,7 +438,7 @@ class MClassDef # Internal name combining the module and the class # Example: "mymodule#MyClass" - redef fun to_s do return "{mmodule}#{mclass}" + redef var to_s: String init(mmodule: MModule, bound_mtype: MClassType, location: Location, parameter_names: Array[String]) do @@ -393,6 +450,7 @@ class MClassDef mmodule.mclassdefs.add(self) mclass.mclassdefs.add(self) self.parameter_names = parameter_names + self.to_s = "{mmodule}#{mclass}" end # All declared super-types @@ -483,12 +541,6 @@ end # * foo(othertype, anchor, mmodule) # * foo(anchor, mmodule, othertype) # * foo(othertype, mmodule, anchor) -# -# FIXME: Add a 'is_valid_anchor' to improve imputability. -# Currently, anchors are used "as it" without check thus if the caller gives a -# bad anchor, then the method will likely crash (abort) in a bad case -# -# FIXME: maybe allways add an anchor with a nullable type (as in is_subtype) abstract class MType # The model of the type @@ -498,6 +550,7 @@ abstract class MType # The typing is done using the standard typing policy of Nit. # # REQUIRE: anchor == null implies not self.need_anchor and not sup.need_anchor + # REQUIRE: anchor != null implies self.can_resolve_for(anchor, null, mmodule) and sup.can_resolve_for(anchor, null, mmodule) fun is_subtype(mmodule: MModule, anchor: nullable MClassType, sup: MType): Bool do var sub = self @@ -505,6 +558,9 @@ abstract class MType if anchor == null then assert not sub.need_anchor assert not sup.need_anchor + else + assert sub.can_resolve_for(anchor, null, mmodule) + assert sup.can_resolve_for(anchor, null, mmodule) end # First, resolve the formal types to a common version in the receiver @@ -621,7 +677,7 @@ abstract class MType if not need_anchor then return self assert not anchor.need_anchor # Just resolve to the anchor and clear all the virtual types - var res = self.resolve_for(anchor, anchor, mmodule, true) + var res = self.resolve_for(anchor, null, mmodule, true) assert not res.need_anchor return res end @@ -640,12 +696,19 @@ abstract class MType # H[Int] supertype_to G #-> G[Int, Bool] # # REQUIRE: `super_mclass' is a super-class of `self' + # REQUIRE: self.need_anchor implies anchor != null and self.can_resolve_for(anchor, null, mmodule) # ENSURE: return.mclass = mclass - fun supertype_to(mmodule: MModule, anchor: MClassType, super_mclass: MClass): MClassType + fun supertype_to(mmodule: MModule, anchor: nullable MClassType, super_mclass: MClass): MClassType do if super_mclass.arity == 0 then return super_mclass.mclass_type if self isa MClassType and self.mclass == super_mclass then return self - var resolved_self = self.anchor_to(mmodule, anchor) + var resolved_self + if self.need_anchor then + assert anchor != null + resolved_self = self.anchor_to(mmodule, anchor) + else + resolved_self = self + end var supertypes = resolved_self.collect_mtypes(mmodule) for supertype in supertypes do if supertype.mclass == super_mclass then @@ -662,10 +725,14 @@ abstract class MType # # This function returns self if `need_anchor' is false. # - # Example: + # ## Example 1 + # # class G[E] # class H[F] super G[F] - # Array[E] resolve_for H[Int] #-> Array[Int] + # class X[Z] + # + # Array[E].resolve_for(H[Int]) #-> Array[Int] + # Array[E].resolve_for(G[Z], X[Int]) #-> Array[Z] # # Explanation of the example: # * Array[E].need_anchor is true because there is a formal generic @@ -677,10 +744,11 @@ abstract class MType # * So, in H[Int], Array[E] is Array[Int] # # This function is mainly used to inherit a signature. - # Because, unlike `anchor_type', we do not want a full resolution of + # Because, unlike `anchor_to', we do not want a full resolution of # a type but only an adapted version of it. # - # Example: + # ## Example 2 + # # class A[E] # foo(e:E):E # end @@ -689,18 +757,66 @@ abstract class MType # The signature on foo is (e: E): E # If we resolve the signature for B, we get (e:Int):Int # + # ## Example 3 + # + # class A[E] + # fun foo(e:E) is abstract + # end + # class B[F] + # var a: A[Array[F]] + # fun bar do a.foo(x) # <- x is here + # end + # + # The first question is: is foo available on `a`? + # + # The static type of a is `A[Array[F]]`, that is an open type. + # in order to find a method `foo`, whe must look at a resolved type. + # + # A[Array[F]].anchor_to(B[nullable Object]) #-> A[Array[nullable Object]] + # + # the method `foo` exists in `A[Array[nullable Object]]`, therefore `foo` exists for `a`. + # + # The next question is: what is the accepted types for `x'? + # + # the signature of `foo` is `foo(e:E)`, thus we must resolve the type E + # + # E.resolve_for(A[Array[F]],B[nullable Object]) #-> Array[F] + # + # The resolution can be done because `E` make sense for the class A (see `can_resolve_for`) + # # TODO: Explain the cleanup_virtual # # FIXME: the parameter `cleanup_virtual' is just a bad idea, but having # two function instead of one seems also to be a bad idea. # + # REQUIRE: can_resolve_for(mtype, anchor, mmodule) # ENSURE: not self.need_anchor implies return == self - fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MType is abstract + fun resolve_for(mtype: MType, anchor: nullable MClassType, mmodule: MModule, cleanup_virtual: Bool): MType is abstract + + # Can the type be resolved? + # + # In order to resolve open types, the formal types must make sence. + # + # ## Example + # + # class A[E] + # end + # class B[F] + # end + # + # E.can_resolve_for(A[Int]) #-> true, E make sense in A + # E.can_resolve_for(B[Int]) #-> false, E does not make sense in B + # B[E].can_resolve_for(A[F], B[Object]) #-> true, + # B[E] is a red hearing only the E is important, + # E make sense in A + # + # REQUIRE: anchor != null implies not anchor.need_anchor + # REQUIRE: mtype.need_anchor implies anchor != null and mtype.can_resolve_for(anchor, null, mmodule) + # ENSURE: not self.need_anchor implies return == true + fun can_resolve_for(mtype: MType, anchor: nullable MClassType, mmodule: MModule): Bool is abstract # Return the nullable version of the type # If the type is already nullable then self is returned - # - # FIXME: DO NOT WORK YET fun as_nullable: MType do var res = self.as_nullable_cache @@ -726,6 +842,19 @@ abstract class MType return 1 end + # The length of the type seen as a tree. + # + # A -> 1 + # G[A] -> 2 + # H[A, B] -> 3 + # H[G[A], B] -> 4 + # + # Formal types have a length of 1. + fun length: Int + do + return 1 + end + # Compute all the classdefs inherited/imported. # The returned set contains: # * the class definitions from `mmodule` and its imported modules @@ -789,7 +918,9 @@ class MClassType return super.as(MClassType) end - redef fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MClassType do return self + redef fun resolve_for(mtype: MType, anchor: nullable MClassType, mmodule: MModule, cleanup_virtual: Bool): MClassType do return self + + redef fun can_resolve_for(mtype, anchor, mmodule) do return true redef fun collect_mclassdefs(mmodule) do @@ -875,20 +1006,20 @@ class MGenericType break end end + + self.to_s = "{mclass}[{arguments.join(", ")}]" end # Recursively print the type of the arguments within brackets. # Example: "Map[String, List[Int]]" - redef fun to_s - do - return "{mclass}[{arguments.join(", ")}]" - end + redef var to_s: String redef var need_anchor: Bool redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) do if not need_anchor then return self + assert can_resolve_for(mtype, anchor, mmodule) var types = new Array[MType] for t in arguments do types.add(t.resolve_for(mtype, anchor, mmodule, cleanup_virtual)) @@ -896,6 +1027,16 @@ class MGenericType return mclass.get_mtype(types) end + redef fun can_resolve_for(mtype, anchor, mmodule) + do + if not need_anchor then return true + for t in arguments do + if not t.can_resolve_for(mtype, anchor, mmodule) then return false + end + return true + end + + redef fun depth do var dmax = 0 @@ -905,6 +1046,15 @@ class MGenericType end return dmax + 1 end + + redef fun length + do + var res = 1 + for a in self.arguments do + res += a.length + end + return res + end end # A virtual formal type. @@ -944,11 +1094,18 @@ class MVirtualType redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) do + assert can_resolve_for(mtype, anchor, mmodule) # self is a virtual type declared (or inherited) in mtype # The point of the function it to get the bound of the virtual type that make sense for mtype # But because mtype is maybe a virtual/formal type, we need to get a real receiver first #print "{class_name}: {self}/{mtype}/{anchor}?" - var resolved_reciever = mtype.resolve_for(anchor, anchor, mmodule, true) + var resolved_reciever + if mtype.need_anchor then + assert anchor != null + resolved_reciever = mtype.resolve_for(anchor, null, mmodule, true) + else + resolved_reciever = mtype + end # Now, we can get the bound var verbatim_bound = lookup_bound(mmodule, resolved_reciever) # The bound is exactly as declared in the "type" property, so we must resolve it again @@ -973,6 +1130,15 @@ class MVirtualType return self end + redef fun can_resolve_for(mtype, anchor, mmodule) + do + if mtype.need_anchor then + assert anchor != null + mtype = mtype.anchor_to(mmodule, anchor) + end + return mtype.has_mproperty(mmodule, mproperty) + end + redef fun to_s do return self.mproperty.to_s init(mproperty: MProperty) @@ -1045,6 +1211,7 @@ class MParameterType redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) do + assert can_resolve_for(mtype, anchor, mmodule) #print "{class_name}: {self}/{mtype}/{anchor}?" if mtype isa MGenericType and mtype.mclass == self.mclass then @@ -1055,14 +1222,20 @@ class MParameterType # The point of the function it to get the bound of the virtual type that make sense for mtype # But because mtype is maybe a virtual/formal type, we need to get a real receiver first # FIXME: What happend here is far from clear. Thus this part must be validated and clarified - var resolved_receiver = mtype.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, true) + var resolved_receiver + if mtype.need_anchor then + assert anchor != null + resolved_receiver = mtype.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, true) + else + resolved_receiver = mtype + end if resolved_receiver isa MNullableType then resolved_receiver = resolved_receiver.mtype if resolved_receiver isa MParameterType then assert resolved_receiver.mclass == anchor.mclass resolved_receiver = anchor.arguments[resolved_receiver.rank] if resolved_receiver isa MNullableType then resolved_receiver = resolved_receiver.mtype end - assert resolved_receiver isa MClassType else print "{class_name}: {self}/{mtype}/{anchor}? {resolved_receiver}" + assert resolved_receiver isa MClassType # Eh! The parameter is in the current class. # So we return the corresponding argument, no mater what! @@ -1072,7 +1245,10 @@ class MParameterType return res end - resolved_receiver = resolved_receiver.resolve_for(anchor, anchor, mmodule, false) + if resolved_receiver.need_anchor then + assert anchor != null + resolved_receiver = resolved_receiver.resolve_for(anchor, null, mmodule, false) + end # Now, we can get the bound var verbatim_bound = lookup_bound(mmodule, resolved_receiver) # The bound is exactly as declared in the "type" property, so we must resolve it again @@ -1083,6 +1259,15 @@ class MParameterType return res end + redef fun can_resolve_for(mtype, anchor, mmodule) + do + if mtype.need_anchor then + assert anchor != null + mtype = mtype.anchor_to(mmodule, anchor) + end + return mtype.collect_mclassdefs(mmodule).has(mclass.intro) + end + init(mclass: MClass, rank: Int) do self.mclass = mclass @@ -1091,7 +1276,6 @@ class MParameterType end # A type prefixed with "nullable" -# FIXME Stub implementation class MNullableType super MType @@ -1103,9 +1287,10 @@ class MNullableType init(mtype: MType) do self.mtype = mtype + self.to_s = "nullable {mtype}" end - redef fun to_s do return "nullable {mtype}" + redef var to_s: String redef fun need_anchor do return mtype.need_anchor redef fun as_nullable do return self @@ -1115,8 +1300,15 @@ class MNullableType return res.as_nullable end + redef fun can_resolve_for(mtype, anchor, mmodule) + do + return self.mtype.can_resolve_for(mtype, anchor, mmodule) + end + redef fun depth do return self.mtype.depth + redef fun length do return self.mtype.length + redef fun collect_mclassdefs(mmodule) do assert not self.need_anchor @@ -1150,6 +1342,7 @@ class MNullType redef fun as_nullable do return self redef fun need_anchor do return false redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual) do return self + redef fun can_resolve_for(mtype, anchor, mmodule) do return true redef fun collect_mclassdefs(mmodule) do return new HashSet[MClassDef] @@ -1186,6 +1379,20 @@ class MSignature return dmax + 1 end + redef fun length + do + var res = 1 + var t = self.return_mtype + if t != null then res += t.length + for p in mparameters do + res += p.mtype.length + end + for p in mclosures do + res += p.mtype.length + end + return res + end + # REQUIRE: 1 <= mparameters.count p -> p.is_vararg init(mparameters: Array[MParameter], return_mtype: nullable MType) do @@ -1235,7 +1442,7 @@ class MSignature return b.to_s end - redef fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MSignature + redef fun resolve_for(mtype: MType, anchor: nullable MClassType, mmodule: MModule, cleanup_virtual: Bool): MSignature do var params = new Array[MParameter] for p in self.mparameters do @@ -1264,7 +1471,7 @@ class MParameter # Is the parameter a vararg? var is_vararg: Bool - fun resolve_for(mtype: MType, anchor: MClassType, mmodule: MModule, cleanup_virtual: Bool): MParameter + fun resolve_for(mtype: MType, anchor: nullable MClassType, mmodule: MModule, cleanup_virtual: Bool): MParameter do if not self.mtype.need_anchor then return self var newtype = self.mtype.resolve_for(mtype, anchor, mmodule, cleanup_virtual) @@ -1471,16 +1678,43 @@ abstract class MProperty # REQUIRE: mtype.has_mproperty(mmodule, self) fun lookup_first_definition(mmodule: MModule, mtype: MType): MPROPDEF do + return lookup_all_definitions(mmodule, mtype).first + end + + # Return all definitions in a linearisation order + # Most speficic first, most general last + fun lookup_all_definitions(mmodule: MModule, mtype: MType): Array[MPROPDEF] + do assert not mtype.need_anchor - assert mtype.has_mproperty(mmodule, self) + if mtype isa MNullableType then mtype = mtype.mtype - var candidates = self.lookup_definitions(mmodule, mtype) - if candidates.length == 1 then return candidates.first - assert candidates.length > 0 + var cache = self.lookup_all_definitions_cache[mmodule, mtype] + if cache != null then return cache - print "BADLINEXT chose {candidates.first} in: {candidates.join(", ")}" - return candidates.first + #print "select prop {mproperty} for {mtype} in {self}" + # First, select all candidates + var candidates = new Array[MPROPDEF] + for mpropdef in self.mpropdefs do + # If the definition is not imported by the module, then skip + if not mmodule.in_importation <= mpropdef.mclassdef.mmodule then continue + # If the definition is not inherited by the type, then skip + if not mtype.is_subtype(mmodule, null, mpropdef.mclassdef.bound_mtype) then continue + # Else, we keep it + candidates.add(mpropdef) + end + # Fast track for only one candidate + if candidates.length <= 1 then + self.lookup_all_definitions_cache[mmodule, mtype] = candidates + return candidates + end + + mmodule.linearize_mpropdefs(candidates) + candidates = candidates.reversed + self.lookup_all_definitions_cache[mmodule, mtype] = candidates + return candidates end + + private var lookup_all_definitions_cache: HashMap2[MModule, MType, Array[MPROPDEF]] = new HashMap2[MModule, MType, Array[MPROPDEF]] end # A global method @@ -1567,14 +1801,12 @@ abstract class MPropDef self.location = location mclassdef.mpropdefs.add(self) mproperty.mpropdefs.add(self) + self.to_s = "{mclassdef}#{mproperty}" end # Internal name combining the module, the class and the property # Example: "mymodule#MyClass#mymethod" - redef fun to_s - do - return "{mclassdef}#{mproperty}" - end + redef var to_s: String # Is self the definition that introduce the property? fun is_intro: Bool do return mproperty.intro == self @@ -1583,19 +1815,18 @@ abstract class MPropDef # # This method is used to determine what method is called by a super. # - # FIXME: IMPLEMENTED AS A static designation, it is ugly - # # REQUIRE: not mtype.need_anchor fun lookup_next_definition(mmodule: MModule, mtype: MType): MPROPDEF do assert not mtype.need_anchor - var mpropdefs = self.mproperty.lookup_super_definitions(self.mclassdef.mmodule, self.mclassdef.bound_mtype) - assert not mpropdefs.is_empty - if mpropdefs.length > 1 then - print "BADLINEXT chose next {mpropdefs.first} in: {mpropdefs.join(", ")}" - end - return mpropdefs.first + var mpropdefs = self.mproperty.lookup_all_definitions(mmodule, mtype) + var i = mpropdefs.iterator + while i.is_ok and i.item != self do i.next + assert has_property: i.is_ok + i.next + assert has_next_property: i.is_ok + return i.item end end @@ -1613,6 +1844,9 @@ class MMethodDef # The signature attached to the property definition var msignature: nullable MSignature writable = null + + # The the method definition abstract? + var is_abstract: Bool writable = false end # A local definition of an attribute