Merge: Fix type adaptation when there is loops

Basically one of the oldest bug of Nit.

The point of adaptive typing is that the static types of variables follows the static types of the assigned values, type tests and comparison to null.
This is a great feature of the language but was buggy because loops where not taken in account (old TODO), until the present PR.

The basic idea is just to track if a type adaptation occurs, if yes replay the whole typing phase.
The immediate drawback is that now typing require 2 passes most of the time, and sometime more.

This PR was a roller-coaster of emotions to develop since a lot a surprise issues were discovered.

* bug in flow that give me hours of despair.
* duplication of error messages; because multiple passes.
* premature warning/error messages; because some error conditions on types are detected at the first pass but a second pass find it is fine in fact... but too late the error message was printed.
* almost work at the first time (modulo the previous issues)
* only two bugs found in the whole code, quite impressive, and one of them is not a real bug but an autocast issue.

The issue about error duplication and premature errors is only workadounded (or fixme) in most places.
But proper solutions will be required in future PR.

close #647 and close #86, then reopen it again, then reclose it.

Pull-Request: #1257
Reviewed-by: Alexis Laferrière <alexis.laf@xymus.net>
Reviewed-by: Lucas Bajolet <r4pass@hotmail.com>
Reviewed-by: Alexandre Terrasa <alexandre@moz-code.org>

diff --combined src/compiler/abstract_compiler.nit
index 3116924,f579a32..8c9e4b7
--- 1/src/compiler/abstract_compiler.nit
--- 2/src/compiler/abstract_compiler.nit
+++ b/src/compiler/abstract_compiler.nit
@@@ -1628,6 -1628,12 +1628,12 @@@ abstract class AbstractCompilerVisito
        fun stmt(nexpr: nullable AExpr)
        do
                if nexpr == null then return
+               if nexpr.mtype == null and not nexpr.is_typed then
+                       # Untyped expression.
+                       # Might mean dead code
+                       # So just return
+                       return
+               end
  
                var narray = nexpr.comprehension
                if narray != null then
@@@ -1647,6 -1653,13 +1653,13 @@@
        # `mtype` is the expected return type, pass null if no specific type is expected.
        fun expr(nexpr: AExpr, mtype: nullable MType): RuntimeVariable
        do
+               if nexpr.mtype == null then
+                       # Untyped expression.
+                       # Might mean dead code
+                       # so return a placebo result
+                       if mtype == null then mtype = compiler.mainmodule.object_type
+                       return new_var(mtype)
+               end
                var old = self.current_node
                self.current_node = nexpr
                var res = nexpr.expr(self).as(not null)
@@@ -3026,9 -3039,7 +3039,9 @@@ redef class ANewExp
  
                var recv = v.init_instance_or_extern(mtype)
  
 -              var callsite = self.callsite.as(not null)
 +              var callsite = self.callsite
 +              if callsite == null then return recv
 +
                var args = v.varargize(callsite.mpropdef, recv, self.n_args.n_exprs)
                var res2 = v.compile_callsite(callsite, args)
                if res2 != null then

diff --combined src/semantize/typing.nit
index 2bbc78b,6727d02..a46f632
--- 1/src/semantize/typing.nit
--- 2/src/semantize/typing.nit
+++ b/src/semantize/typing.nit
@@@ -239,12 -239,16 +239,16 @@@ private class TypeVisito
  
                if not mtype2 isa MNullType then return
  
                # Check of useless null
                if not check_can_be_null(anode.n_expr, mtype) then return
  
-               mtype = mtype.as_notnull
+               if mtype isa MNullType then
+                       # Because of type adaptation, we cannot just stop here
+                       # so return use `null` as a bottom type that will be merged easily (cf) `merge_types`
+                       mtype = null
+               else
+                       mtype = mtype.as_notnull
+               end
  
                # Check for type adaptation
                var variable = anode.n_expr.its_variable
@@@ -252,11 -256,11 +256,11 @@@
  
                # One is null (mtype2 see above) the other is not null
                if anode isa AEqExpr then
-                       anode.after_flow_context.when_true.set_var(variable, mtype2)
-                       anode.after_flow_context.when_false.set_var(variable, mtype)
+                       anode.after_flow_context.when_true.set_var(self, variable, mtype2)
+                       anode.after_flow_context.when_false.set_var(self, variable, mtype)
                else if anode isa ANeExpr then
-                       anode.after_flow_context.when_false.set_var(variable, mtype2)
-                       anode.after_flow_context.when_true.set_var(variable, mtype)
+                       anode.after_flow_context.when_false.set_var(self, variable, mtype2)
+                       anode.after_flow_context.when_true.set_var(self, variable, mtype)
                else
                        abort
                end
@@@ -444,6 -448,8 +448,8 @@@
  
        fun get_variable(node: AExpr, variable: Variable): nullable MType
        do
+               if not variable.is_adapted then return variable.declared_type
+ 
                var flow = node.after_flow_context
                if flow == null then
                        self.error(node, "No context!")
@@@ -456,7 -462,7 +462,7 @@@
                        #node.debug("*** START Collected for {variable}")
                        var mtypes = flow.collect_types(variable)
                        #node.debug("**** END Collected for {variable}")
-                       if mtypes == null or mtypes.length == 0 then
+                       if mtypes.length == 0 then
                                return variable.declared_type
                        else if mtypes.length == 1 then
                                return mtypes.first
@@@ -468,12 -474,18 +474,18 @@@
                end
        end
  
+       # Some variables where type-adapted during the visit
+       var dirty = false
+ 
+       # Some loops had been visited during the visit
+       var has_loop = false
+ 
        fun set_variable(node: AExpr, variable: Variable, mtype: nullable MType)
        do
                var flow = node.after_flow_context
                assert flow != null
  
-               flow.set_var(variable, mtype)
+               flow.set_var(self, variable, mtype)
        end
  
        fun merge_types(node: ANode, col: Array[nullable MType]): nullable MType
@@@ -540,49 -552,58 +552,58 @@@ en
  redef class Variable
        # The declared type of the variable
        var declared_type: nullable MType
+ 
+       # Was the variable type-adapted?
+       # This is used to speedup type retrieval while it remains `false`
+       private var is_adapted = false
  end
  
  redef class FlowContext
        # Store changes of types because of type evolution
        private var vars = new HashMap[Variable, nullable MType]
-       private var cache = new HashMap[Variable, nullable Array[nullable MType]]
  
        # Adapt the variable to a static type
        # Warning1: do not modify vars directly.
        # Warning2: sub-flow may have cached a unadapted variable
-       private fun set_var(variable: Variable, mtype: nullable MType)
+       private fun set_var(v: TypeVisitor, variable: Variable, mtype: nullable MType)
        do
+               if variable.declared_type == mtype and not variable.is_adapted then return
+               if vars.has_key(variable) and vars[variable] == mtype then return
                self.vars[variable] = mtype
-               self.cache.keys.remove(variable)
+               v.dirty = true
+               variable.is_adapted = true
+               #node.debug "set {variable} to {mtype or else "X"}"
        end
  
-       private fun collect_types(variable: Variable): nullable Array[nullable MType]
+       # Look in the flow and previous flow and collect all first reachable type adaptation of a local variable
+       private fun collect_types(variable: Variable): Array[nullable MType]
        do
-               if cache.has_key(variable) then
-                       return cache[variable]
-               end
-               var res: nullable Array[nullable MType] = null
-               if vars.has_key(variable) then
-                       var mtype = vars[variable]
-                       res = [mtype]
-               else if self.previous.is_empty then
-                       # Root flow
-                       res = [variable.declared_type]
-               else
-                       for flow in self.previous do
-                               if flow.is_unreachable then continue
-                               var r2 = flow.collect_types(variable)
-                               if r2 == null then continue
-                               if res == null then
-                                       res = r2.to_a
-                               else
-                                       for t in r2 do
-                                               if not res.has(t) then res.add(t)
-                                       end
+               #node.debug "flow for {variable}"
+               var res = new Array[nullable MType]
+ 
+               var todo = [self]
+               var seen = new HashSet[FlowContext]
+               while not todo.is_empty do
+                       var f = todo.pop
+                       if f.is_unreachable then continue
+                       if seen.has(f) then continue
+                       seen.add f
+ 
+                       if f.vars.has_key(variable) then
+                               # Found something. Collect it and do not process further on this path
+                               res.add f.vars[variable]
+                               #f.node.debug "process {variable}: got {f.vars[variable] or else "X"}"
+                       else
+                               todo.add_all f.previous
+                               todo.add_all f.loops
+                               if f.previous.is_empty then
+                                       # Root flowcontext mean a parameter or something related
+                                       res.add variable.declared_type
+                                       #f.node.debug "root process {variable}: got {variable.declared_type or else "X"}"
                                end
                        end
                end
-               cache[variable] = res
+               #self.node.debug "##### end flow for {variable}: {res.join(" ")}"
                return res
        end
  end
@@@ -623,7 -644,12 +644,12 @@@ redef class AMethPropde
                        assert variable != null
                        variable.declared_type = mtype
                end
-               v.visit_stmt(nblock)
+ 
+               loop
+                       v.dirty = false
+                       v.visit_stmt(nblock)
+                       if not v.has_loop or not v.dirty then break
+               end
  
                if not nblock.after_flow_context.is_unreachable and msignature.return_mtype != null then
                        # We reach the end of the function without having a return, it is bad
@@@ -952,8 -978,8 +978,8 @@@ en
  redef class AWhileExpr
        redef fun accept_typing(v)
        do
+               v.has_loop = true
                v.visit_expr_bool(n_expr)
- 
                v.visit_stmt(n_block)
                self.is_typed = true
        end
@@@ -962,6 -988,7 +988,7 @@@ en
  redef class ALoopExpr
        redef fun accept_typing(v)
        do
+               v.has_loop = true
                v.visit_stmt(n_block)
                self.is_typed = true
        end
@@@ -1097,12 -1124,14 +1124,14 @@@ redef class AForExp
  
        redef fun accept_typing(v)
        do
+               v.has_loop = true
                var mtype = v.visit_expr(n_expr)
                if mtype == null then return
  
                self.do_type_iterator(v, mtype)
  
                v.visit_stmt(n_block)
+ 
                self.mtype = n_block.mtype
                self.is_typed = true
        end
@@@ -1317,6 -1346,8 +1346,8 @@@ redef class AArrayExp
                        end
                end
                if mtype == null then
+                       # Ensure monotony for type adaptation on loops
+                       if self.element_mtype != null then mtypes.add self.element_mtype
                        mtype = v.merge_types(self, mtypes)
                end
                if mtype == null or mtype isa MNullType then
@@@ -1401,7 -1432,7 +1432,7 @@@ redef class AIsaExp
                        #var from = if orig != null then orig.to_s else "invalid"
                        #var to = if mtype != null then mtype.to_s else "invalid"
                        #debug("adapt {variable}: {from} -> {to}")
-                       self.after_flow_context.when_true.set_var(variable, mtype)
+                       self.after_flow_context.when_true.set_var(v, variable, mtype)
                end
  
                self.mtype = v.type_bool(self)
@@@ -1844,7 -1875,6 +1875,7 @@@ redef class ANewExp
                end
  
                self.recvtype = recvtype
 +              var kind = recvtype.mclass.kind
  
                var name: String
                var nid = self.n_id
@@@ -1853,24 -1883,11 +1884,24 @@@
                else
                        name = "new"
                end
 +              if name == "intern" then
 +                      if kind != concrete_kind then
 +                              v.error(self, "Type Error: Cannot instantiate {kind} {recvtype}.")
 +                              return
 +                      end
 +                      if n_args.n_exprs.not_empty then
 +                              v.error(n_args, "Type Error: the intern constructor expects no arguments.")
 +                              return
 +                      end
 +                      # Our job is done
 +                      self.mtype = recvtype
 +                      return
 +              end
 +
                var callsite = v.get_method(self, recvtype, name, false)
                if callsite == null then return
  
                if not callsite.mproperty.is_new then
 -                      var kind = recvtype.mclass.kind
                        if kind != concrete_kind then
                                v.error(self, "Type Error: Cannot instantiate {kind} {recvtype}.")
                                return