model: try_get_primitive_method asks for a MClass (and not a MType)
[nit.git] / src / model / model.nit
index dbaf282..ae55960 100644 (file)
@@ -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,44 +558,76 @@ 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 types
+
+               # First, resolve the formal types to a common version in the receiver
+               # The trick here is that fixed formal type will be associed to the bound
+               # And unfixed formal types will be associed to a canonical formal type.
                if sub isa MParameterType or sub isa MVirtualType then
                        assert anchor != null
-                       sub = sub.resolve_for(anchor, anchor, mmodule, false)
+                       sub = sub.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, false)
                end
                if sup isa MParameterType or sup isa MVirtualType then
                        assert anchor != null
-                       sup = sup.resolve_for(anchor, anchor, mmodule, false)
+                       sup = sup.resolve_for(anchor.mclass.mclass_type, anchor, mmodule, false)
                end
 
-               if sup isa MParameterType or sup isa MVirtualType or sup isa MNullType then
+               # Does `sup` accept null or not?
+               # Discard the nullable marker if it exists
+               var sup_accept_null = false
+               if sup isa MNullableType then
+                       sup_accept_null = true
+                       sup = sup.mtype
+               else if sup isa MNullType then
+                       sup_accept_null = true
+               end
+
+               # Can `sub` provide null or not?
+               # Thus we can match with `sup_accept_null`
+               # Also discard the nullable marker if it exists
+               if sub isa MNullableType then
+                       if not sup_accept_null then return false
+                       sub = sub.mtype
+               else if sub isa MNullType then
+                       return sup_accept_null
+               end
+               # Now the case of direct null and nullable is over.
+
+               # A unfixed formal type can only accept itself
+               if sup isa MParameterType or sup isa MVirtualType then
                        return sub == sup
                end
+
+               # If `sub` is a formal type, then it is accepted if its bound is accepted
                if sub isa MParameterType or sub isa MVirtualType then
                        assert anchor != null
                        sub = sub.anchor_to(mmodule, anchor)
-               end
-               if sup isa MNullableType then
-                       if sub isa MNullType then
-                               return true
-                       else if sub isa MNullableType then
-                               return sub.mtype.is_subtype(mmodule, anchor, sup.mtype)
-                       else if sub isa MClassType then
-                               return sub.is_subtype(mmodule, anchor, sup.mtype)
-                       else
-                               abort
+
+                       # Manage the second layer of null/nullable
+                       if sub isa MNullableType then
+                               if not sup_accept_null then return false
+                               sub = sub.mtype
+                       else if sub isa MNullType then
+                               return sup_accept_null
                        end
                end
 
-               assert sup isa MClassType # It is the only remaining type
-               if sub isa MNullableType or sub isa MNullType then
+               assert sub isa MClassType # It is the only remaining type
+
+               if sup isa MNullType then
+                       # `sup` accepts only null
                        return false
                end
 
+               assert sup isa MClassType # It is the only remaining type
+
+               # Now both are MClassType, we need to dig
+
                if sub == sup then return true
 
-               assert sub isa MClassType # It is the only remaining type
                if anchor == null then anchor = sub # UGLY: any anchor will work
                var resolved_sub = sub.anchor_to(mmodule, anchor)
                var res = resolved_sub.collect_mclasses(mmodule).has(sup.mclass)
@@ -592,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
@@ -611,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
@@ -633,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
@@ -648,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
@@ -660,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
@@ -697,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
@@ -760,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
@@ -846,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
+       # Example: "Map[String, List[Int]]"
+       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))
@@ -867,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
@@ -876,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.
@@ -915,18 +1094,49 @@ class MVirtualType
 
        redef fun resolve_for(mtype, anchor, mmodule, cleanup_virtual)
        do
-               if not cleanup_virtual then return self
+               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
-               var res = verbatim_bound.resolve_for(mtype, anchor, mmodule, true)
+               var res = verbatim_bound.resolve_for(mtype, anchor, mmodule, cleanup_virtual)
                #print "{class_name}: {self}/{mtype}/{anchor} -> {self}/{resolved_reciever}/{anchor} -> {verbatim_bound}/{mtype}/{anchor} -> {res}"
-               return res
+
+               # What to return here? There is a bunch a special cases:
+               # If 'cleanup_virtual' we must return the resolved type, since we cannot return self
+               if cleanup_virtual then return res
+               # If the reciever is a intern class, then the virtual type cannot be redefined since there is no possible subclass. self is just fixed. so simply return the resolution
+               if resolved_reciever isa MNullableType then resolved_reciever = resolved_reciever.mtype
+               if resolved_reciever.as(MClassType).mclass.kind == enum_kind then return res
+               # If the resolved type isa MVirtualType, it means that self was bound to it, and cannot be unbound. self is just fixed. so return the resolution.
+               if res isa MVirtualType then return res
+               # It the resolved type isa intern class, then there is no possible valid redefinition is any potentiel subclass. self is just fixed. so simply return the resolution
+               if res isa MClassType and res.mclass.kind == enum_kind then return res
+               # TODO: Add 'fixed' virtual type in the specification.
+               # TODO: What if bound to a MParameterType?
+               # Note that Nullable types can always be redefined by the non nullable version, so there is no specific case on it.
+
+               # If anything apply, then `self' cannot be resolved, so return self
+               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
@@ -1001,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
@@ -1011,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!
@@ -1028,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
@@ -1039,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
@@ -1047,7 +1276,6 @@ class MParameterType
 end
 
 # A type prefixed with "nullable"
-# FIXME Stub implementation
 class MNullableType
        super MType
 
@@ -1059,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
@@ -1071,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
@@ -1106,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]
 
@@ -1142,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
@@ -1191,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
@@ -1220,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)
@@ -1417,19 +1668,53 @@ abstract class MProperty
        end
 
        # Return the most specific definition in the linearization of `mtype`.
-       # If mtype does not know mproperty then null is returned.
        #
        # If you want to know the next properties in the linearization,
        # look at `MPropDef::lookup_next_definition`.
        #
-       # FIXME: NOT YET IMPLEMENTED
+       # FIXME: the linearisation is still unspecified
        #
        # REQUIRE: not mtype.need_anchor
-       fun lookup_first_definition(mmodule: MModule, mtype: MType): nullable MPROPDEF
+       # 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
-               return null
+               if mtype isa MNullableType then mtype = mtype.mtype
+
+               var cache = self.lookup_all_definitions_cache[mmodule, mtype]
+               if cache != null then return cache
+
+               #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
@@ -1516,30 +1801,32 @@ 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
 
        # Return the next definition in linearization of `mtype`.
-       # If there is no next method then null is returned.
        #
        # This method is used to determine what method is called by a super.
        #
-       # FIXME: NOT YET IMPLEMENTED
-       #
        # REQUIRE: not mtype.need_anchor
-       fun lookup_next_definition(mmodule: MModule, mtype: MType): nullable MPROPDEF
+       fun lookup_next_definition(mmodule: MModule, mtype: MType): MPROPDEF
        do
                assert not mtype.need_anchor
-               return null
+
+               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
 
@@ -1557,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