src/semantize/typing.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2012 Jean Privat <jean@pryen.org>
   4 #
   5 # Licensed under the Apache License, Version 2.0 (the "License");
   6 # you may not use this file except in compliance with the License.
   7 # You may obtain a copy of the License at
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  11 # Unless required by applicable law or agreed to in writing, software
  12 # distributed under the License is distributed on an "AS IS" BASIS,
  13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14 # See the License for the specific language governing permissions and
  15 # limitations under the License.
  16
  17 # Intraprocedural resolution of static types and OO-services
  18 # By OO-services we mean message sending, attribute access, instantiation, etc.
  19 module typing
  20
  21 import modelize
  22 import local_var_init
  23
  24 redef class ToolContext
  25         var typing_phase: Phase = new TypingPhase(self, [flow_phase, modelize_property_phase, local_var_init_phase])
  26 end
  27
  28 private class TypingPhase
  29         super Phase
  30         redef fun process_npropdef(npropdef) do npropdef.do_typing(toolcontext.modelbuilder)
  31 end
  32
  33 private class TypeVisitor
  34         var modelbuilder:  ModelBuilder
  35
  36         # The module of the analysis
  37         # Used to correctly query the model
  38         var mmodule: MModule
  39
  40         # The static type of the receiver
  41         # Mainly used for type tests and type resolutions
  42         var anchor: nullable MClassType = null
  43
  44         # The analyzed mclassdef
  45         var mclassdef: nullable MClassDef = null
  46
  47         # The analyzed property
  48         var mpropdef: nullable MPropDef
  49
  50         var selfvariable = new Variable("self")
  51
  52         # Is `self` use restricted?
  53         # * no explicit `self`
  54         # * method called on the implicit self must be top-level
  55         # Currently only used for `new` factory since there is no valid receiver inside
  56         var is_toplevel_context = false
  57
  58         init
  59         do
  60                 var mpropdef = self.mpropdef
  61
  62                 if mpropdef != null then
  63                         self.mpropdef = mpropdef
  64                         var mclassdef = mpropdef.mclassdef
  65                         self.mclassdef = mclassdef
  66                         self.anchor = mclassdef.bound_mtype
  67
  68                         var mclass = mclassdef.mclass
  69
  70                         var selfvariable = new Variable("self")
  71                         self.selfvariable = selfvariable
  72                         selfvariable.declared_type = mclass.mclass_type
  73
  74                         var mprop = mpropdef.mproperty
  75                         if mprop isa MMethod and mprop.is_new then
  76                                 is_toplevel_context = true
  77                         end
  78                 end
  79         end
  80
  81         fun anchor_to(mtype: MType): MType
  82         do
  83                 var anchor = anchor
  84                 if anchor == null then
  85                         assert not mtype.need_anchor
  86                         return mtype
  87                 end
  88                 return mtype.anchor_to(mmodule, anchor)
  89         end
  90
  91         fun is_subtype(sub, sup: MType): Bool
  92         do
  93                 return sub.is_subtype(mmodule, anchor, sup)
  94         end
  95
  96         fun resolve_for(mtype, subtype: MType, for_self: Bool): MType
  97         do
  98                 #print "resolve_for {mtype} sub={subtype} forself={for_self} mmodule={mmodule} anchor={anchor}"
  99                 var res = mtype.resolve_for(subtype, anchor, mmodule, not for_self)
 100                 return res
 101         end
 102
 103         # Check that `sub` is a subtype of `sup`.
 104         # If `sub` is not a valid suptype, then display an error on `node` an return null.
 105         # If `sub` is a safe subtype of `sup` then return `sub`.
 106         # If `sub` is an unsafe subtype (ie an implicit cast is required), then return `sup`.
 107         #
 108         # The point of the return type is to determinate the usable type on an expression when `autocast` is true:
 109         # If the suptype is safe, then the return type is the one on the expression typed by `sub`.
 110         # Is the subtype is unsafe, then the return type is the one of an implicit cast on `sup`.
 111         fun check_subtype(node: ANode, sub, sup: MType, autocast: Bool): nullable MType
 112         do
 113                 if self.is_subtype(sub, sup) then return sub
 114                 if autocast and self.is_subtype(sub, self.anchor_to(sup)) then
 115                         # FIXME workaround to the current unsafe typing policy. To remove once fixed virtual types exists.
 116                         #node.debug("Unsafe typing: expected {sup}, got {sub}")
 117                         return sup
 118                 end
 119                 if sub.need_anchor then
 120                         var u = anchor_to(sub)
 121                         self.modelbuilder.error(node, "Type Error: expected `{sup}`, got `{sub}: {u}`.")
 122                 else
 123                         self.modelbuilder.error(node, "Type Error: expected `{sup}`, got `{sub}`.")
 124                 end
 125                 return null
 126         end
 127
 128         # Visit an expression and do not care about the return value
 129         fun visit_stmt(nexpr: nullable AExpr)
 130         do
 131                 if nexpr == null then return
 132                 nexpr.accept_typing(self)
 133         end
 134
 135         # Visit an expression and expects that it is not a statement
 136         # Return the type of the expression
 137         # Display an error and return null if:
 138         #  * the type cannot be determined or
 139         #  * `nexpr` is a statement
 140         fun visit_expr(nexpr: AExpr): nullable MType
 141         do
 142                 nexpr.accept_typing(self)
 143                 var mtype = nexpr.mtype
 144                 if mtype != null then return mtype
 145                 if not nexpr.is_typed then
 146                         if not self.modelbuilder.toolcontext.error_count > 0 then # check that there is really an error
 147                                 if self.modelbuilder.toolcontext.verbose_level > 1 then
 148                                         nexpr.debug("No return type but no error.")
 149                                 end
 150                         end
 151                         return null # forward error
 152                 end
 153                 self.error(nexpr, "Error: expected an expression.")
 154                 return null
 155         end
 156
 157         # Visit an expression and expect its static type is a least a `sup`
 158         # Return the type of the expression or null if
 159         #  * the type cannot be determined or
 160         #  * `nexpr` is a statement or
 161         #  * `nexpr` is not a `sup`
 162         fun visit_expr_subtype(nexpr: AExpr, sup: nullable MType): nullable MType
 163         do
 164                 var sub = visit_expr(nexpr)
 165                 if sub == null then return null # Forward error
 166
 167                 if sup == null then return null # Forward error
 168
 169                 var res = check_subtype(nexpr, sub, sup, true)
 170                 if res != sub then
 171                         nexpr.implicit_cast_to = res
 172                 end
 173                 return res
 174         end
 175
 176         # Visit an expression and expect its static type is a `Bool`
 177         # Return the type of the expression or null if
 178         #  * the type cannot be determined or
 179         #  * `nexpr` is a statement or
 180         #  * `nexpr` is not a `Bool`
 181         fun visit_expr_bool(nexpr: AExpr): nullable MType
 182         do
 183                 return self.visit_expr_subtype(nexpr, self.type_bool(nexpr))
 184         end
 185
 186
 187         fun visit_expr_cast(node: ANode, nexpr: AExpr, ntype: AType): nullable MType
 188         do
 189                 var sub = visit_expr(nexpr)
 190                 if sub == null then return null # Forward error
 191
 192                 var sup = self.resolve_mtype(ntype)
 193                 if sup == null then return null # Forward error
 194
 195                 if sup == sub then
 196                         self.modelbuilder.warning(node, "useless-type-test", "Warning: expression is already a `{sup}`.")
 197                 else if self.is_subtype(sub, sup) then
 198                         self.modelbuilder.warning(node, "useless-type-test", "Warning: expression is already a `{sup}` since it is a `{sub}`.")
 199                 end
 200                 return sup
 201         end
 202
 203         # Can `mtype` be null (up to the current knowledge)?
 204         fun can_be_null(mtype: MType): Bool
 205         do
 206                 if mtype isa MNullableType or mtype isa MNullType then return true
 207                 if mtype isa MFormalType then
 208                         var x = anchor_to(mtype)
 209                         if x isa MNullableType or x isa MNullType then return true
 210                 end
 211                 return false
 212         end
 213
 214         # Check that `mtype` can be null (up to the current knowledge).
 215         #
 216         # If not then display a `useless-null-test` warning on node and return false.
 217         # Else return true.
 218         fun check_can_be_null(anode: ANode, mtype: MType): Bool
 219         do
 220                 if can_be_null(mtype) then return true
 221
 222                 if mtype isa MFormalType then
 223                         var res = anchor_to(mtype)
 224                         modelbuilder.warning(anode, "useless-null-test", "Warning: expression is not null, since it is a `{mtype}: {res}`.")
 225                 else
 226                         modelbuilder.warning(anode, "useless-null-test", "Warning: expression is not null, since it is a `{mtype}`.")
 227                 end
 228                 return false
 229         end
 230
 231         # Special verification on != and == for null
 232         # Return true
 233         fun null_test(anode: ABinopExpr)
 234         do
 235                 var mtype = anode.n_expr.mtype
 236                 var mtype2 = anode.n_expr2.mtype
 237
 238                 if mtype == null or mtype2 == null then return
 239
 240                 if not mtype2 isa MNullType then return
 241
 242                 # Check of useless null
 243                 if not check_can_be_null(anode.n_expr, mtype) then return
 244
 245                 if mtype isa MNullType then
 246                         # Because of type adaptation, we cannot just stop here
 247                         # so return use `null` as a bottom type that will be merged easily (cf) `merge_types`
 248                         mtype = null
 249                 else
 250                         mtype = mtype.as_notnull
 251                 end
 252
 253                 # Check for type adaptation
 254                 var variable = anode.n_expr.its_variable
 255                 if variable == null then return
 256
 257                 # One is null (mtype2 see above) the other is not null
 258                 if anode isa AEqExpr then
 259                         anode.after_flow_context.when_true.set_var(self, variable, mtype2)
 260                         anode.after_flow_context.when_false.set_var(self, variable, mtype)
 261                 else if anode isa ANeExpr then
 262                         anode.after_flow_context.when_false.set_var(self, variable, mtype2)
 263                         anode.after_flow_context.when_true.set_var(self, variable, mtype)
 264                 else
 265                         abort
 266                 end
 267         end
 268
 269         fun try_get_mproperty_by_name2(anode: ANode, mtype: MType, name: String): nullable MProperty
 270         do
 271                 return self.modelbuilder.try_get_mproperty_by_name2(anode, mmodule, mtype, name)
 272         end
 273
 274         fun resolve_mtype(node: AType): nullable MType
 275         do
 276                 return self.modelbuilder.resolve_mtype(mmodule, mclassdef, node)
 277         end
 278
 279         fun try_get_mclass(node: ANode, name: String): nullable MClass
 280         do
 281                 var mclass = modelbuilder.try_get_mclass_by_name(node, mmodule, name)
 282                 return mclass
 283         end
 284
 285         fun get_mclass(node: ANode, name: String): nullable MClass
 286         do
 287                 var mclass = modelbuilder.get_mclass_by_name(node, mmodule, name)
 288                 return mclass
 289         end
 290
 291         fun type_bool(node: ANode): nullable MType
 292         do
 293                 var mclass = self.get_mclass(node, "Bool")
 294                 if mclass == null then return null
 295                 return mclass.mclass_type
 296         end
 297
 298         fun get_method(node: ANode, recvtype: MType, name: String, recv_is_self: Bool): nullable CallSite
 299         do
 300                 var unsafe_type = self.anchor_to(recvtype)
 301
 302                 #debug("recv: {recvtype} (aka {unsafe_type})")
 303                 if recvtype isa MNullType then
 304                         # `null` only accepts some methods of object.
 305                         if name == "==" or name == "!=" or name == "is_same_instance" then
 306                                 var objclass = get_mclass(node, "Object")
 307                                 if objclass == null then return null # Forward error
 308                                 unsafe_type = objclass.mclass_type
 309                         else
 310                                 self.error(node, "Error: method `{name}` called on `null`.")
 311                                 return null
 312                         end
 313                 end
 314
 315                 var mproperty = self.try_get_mproperty_by_name2(node, unsafe_type, name)
 316                 if name == "new" and mproperty == null then
 317                         name = "init"
 318                         mproperty = self.try_get_mproperty_by_name2(node, unsafe_type, name)
 319                 end
 320
 321                 if mproperty == null then
 322                         if recv_is_self then
 323                                 self.modelbuilder.error(node, "Error: method or variable `{name}` unknown in `{recvtype}`.")
 324                         else if recvtype.need_anchor then
 325                                 self.modelbuilder.error(node, "Error: method `{name}` does not exists in `{recvtype}: {unsafe_type}`.")
 326                         else
 327                                 self.modelbuilder.error(node, "Error: method `{name}` does not exists in `{recvtype}`.")
 328                         end
 329                         return null
 330                 end
 331
 332                 assert mproperty isa MMethod
 333
 334                 if is_toplevel_context and recv_is_self and not mproperty.is_toplevel then
 335                         error(node, "Error: `{name}` is not a top-level method, thus need a receiver.")
 336                 end
 337                 if not recv_is_self and mproperty.is_toplevel then
 338                         error(node, "Error: cannot call `{name}`, a top-level method, with a receiver.")
 339                 end
 340
 341                 if mproperty.visibility == protected_visibility and not recv_is_self and self.mmodule.visibility_for(mproperty.intro_mclassdef.mmodule) < intrude_visibility and not modelbuilder.toolcontext.opt_ignore_visibility.value then
 342                         self.modelbuilder.error(node, "Error: method `{name}` is protected and can only accessed by `self`.")
 343                         return null
 344                 end
 345
 346                 var info = mproperty.deprecation
 347                 if info != null and self.mpropdef.mproperty.deprecation == null then
 348                         var mdoc = info.mdoc
 349                         if mdoc != null then
 350                                 self.modelbuilder.warning(node, "deprecated-method", "Deprecation Warning: method `{name}` is deprecated: {mdoc.content.first}")
 351                         else
 352                                 self.modelbuilder.warning(node, "deprecated-method", "Deprecation Warning: method `{name}` is deprecated.")
 353                         end
 354                 end
 355
 356                 var propdefs = mproperty.lookup_definitions(self.mmodule, unsafe_type)
 357                 var mpropdef
 358                 if propdefs.length == 0 then
 359                         self.modelbuilder.error(node, "Type Error: no definition found for property `{name}` in `{unsafe_type}`.")
 360                         return null
 361                 else if propdefs.length == 1 then
 362                         mpropdef = propdefs.first
 363                 else
 364                         self.modelbuilder.warning(node, "property-conflict", "Warning: conflicting property definitions for property `{name}` in `{unsafe_type}`: {propdefs.join(" ")}")
 365                         mpropdef = mproperty.intro
 366                 end
 367
 368
 369                 var msignature = mpropdef.new_msignature or else mpropdef.msignature
 370                 if msignature == null then return null # skip error
 371                 msignature = resolve_for(msignature, recvtype, recv_is_self).as(MSignature)
 372
 373                 var erasure_cast = false
 374                 var rettype = mpropdef.msignature.return_mtype
 375                 if not recv_is_self and rettype != null then
 376                         rettype = rettype.undecorate
 377                         if rettype isa MParameterType then
 378                                 var erased_rettype = msignature.return_mtype
 379                                 assert erased_rettype != null
 380                                 #node.debug("Erasure cast: Really a {rettype} but unsafely a {erased_rettype}")
 381                                 erasure_cast = true
 382                         end
 383                 end
 384
 385                 var callsite = new CallSite(node, recvtype, mmodule, anchor, recv_is_self, mproperty, mpropdef, msignature, erasure_cast)
 386                 return callsite
 387         end
 388
 389         fun try_get_method(node: ANode, recvtype: MType, name: String, recv_is_self: Bool): nullable CallSite
 390         do
 391                 var unsafe_type = self.anchor_to(recvtype)
 392                 var mproperty = self.try_get_mproperty_by_name2(node, unsafe_type, name)
 393                 if mproperty == null then return null
 394                 return get_method(node, recvtype, name, recv_is_self)
 395         end
 396
 397
 398         # Visit the expressions of args and check their conformity with the corresponding type in signature
 399         # The point of this method is to handle varargs correctly
 400         # Note: The signature must be correctly adapted
 401         fun check_signature(node: ANode, args: Array[AExpr], mproperty: MProperty, msignature: MSignature): nullable SignatureMap
 402         do
 403                 var vararg_rank = msignature.vararg_rank
 404                 if vararg_rank >= 0 then
 405                         if args.length < msignature.arity then
 406                                 modelbuilder.error(node, "Error: expected at least {msignature.arity} argument(s) for `{mproperty}{msignature}`; got {args.length}. See introduction at `{mproperty.full_name}`.")
 407                                 return null
 408                         end
 409                 else if args.length != msignature.arity then
 410                         if msignature.arity == msignature.min_arity then
 411                                 modelbuilder.error(node, "Error: expected {msignature.arity} argument(s) for `{mproperty}{msignature}`; got {args.length}. See introduction at `{mproperty.full_name}`.")
 412                                 return null
 413                         end
 414                         if args.length > msignature.arity then
 415                                 modelbuilder.error(node, "Error: expected at most {msignature.arity} argument(s) for `{mproperty}{msignature}`; got {args.length}. See introduction at `{mproperty.full_name}`.")
 416                                 return null
 417                         end
 418                         if args.length < msignature.min_arity then
 419                                 modelbuilder.error(node, "Error: expected at least {msignature.min_arity} argument(s) for `{mproperty}{msignature}`; got {args.length}. See introduction at `{mproperty.full_name}`.")
 420                                 return null
 421                         end
 422                 end
 423
 424                 #debug("CALL {unsafe_type}.{msignature}")
 425
 426                 # Associate each parameter to a position in the arguments
 427                 var map = new SignatureMap
 428
 429                 var setted = args.length - msignature.min_arity
 430                 var vararg_decl = args.length - msignature.arity
 431                 var j = 0
 432                 for i in [0..msignature.arity[ do
 433                         var param = msignature.mparameters[i]
 434                         if param.is_default then
 435                                 if setted > 0 then
 436                                         setted -= 1
 437                                 else
 438                                         continue
 439                                 end
 440                         end
 441                         var arg = args[j]
 442                         map.map[i] = j
 443                         j += 1
 444
 445                         if i == vararg_rank then
 446                                 j += vararg_decl
 447                                 continue # skip the vararg
 448                         end
 449
 450                         var paramtype = param.mtype
 451                         self.visit_expr_subtype(arg, paramtype)
 452                 end
 453                 if vararg_rank >= 0 then
 454                         var paramtype = msignature.mparameters[vararg_rank].mtype
 455                         var first = args[vararg_rank]
 456                         if vararg_decl == 0 and first isa AVarargExpr then
 457                                 var mclass = get_mclass(node, "Array")
 458                                 if mclass == null then return null # Forward error
 459                                 var array_mtype = mclass.get_mtype([paramtype])
 460                                 self.visit_expr_subtype(first.n_expr, array_mtype)
 461                                 first.mtype  = first.n_expr.mtype
 462                         else
 463                                 map.vararg_decl = vararg_decl + 1
 464                                 for i in [vararg_rank..vararg_rank+vararg_decl] do
 465                                         self.visit_expr_subtype(args[i], paramtype)
 466                                 end
 467                         end
 468                 end
 469
 470                 return map
 471         end
 472
 473         fun error(node: ANode, message: String)
 474         do
 475                 self.modelbuilder.toolcontext.error(node.hot_location, message)
 476         end
 477
 478         fun get_variable(node: AExpr, variable: Variable): nullable MType
 479         do
 480                 if not variable.is_adapted then return variable.declared_type
 481
 482                 var flow = node.after_flow_context
 483                 if flow == null then return null # skip error
 484
 485                 if flow.vars.has_key(variable) then
 486                         return flow.vars[variable]
 487                 else
 488                         #node.debug("*** START Collected for {variable}")
 489                         var mtypes = flow.collect_types(variable)
 490                         #node.debug("**** END Collected for {variable}")
 491                         if mtypes.length == 0 then
 492                                 return variable.declared_type
 493                         else if mtypes.length == 1 then
 494                                 return mtypes.first
 495                         else
 496                                 var res = merge_types(node,mtypes)
 497                                 if res == null then res = variable.declared_type
 498                                 return res
 499                         end
 500                 end
 501         end
 502
 503         # Some variables where type-adapted during the visit
 504         var dirty = false
 505
 506         # Some loops had been visited during the visit
 507         var has_loop = false
 508
 509         fun set_variable(node: AExpr, variable: Variable, mtype: nullable MType)
 510         do
 511                 var flow = node.after_flow_context
 512                 assert flow != null
 513
 514                 flow.set_var(self, variable, mtype)
 515         end
 516
 517         fun merge_types(node: ANode, col: Array[nullable MType]): nullable MType
 518         do
 519                 if col.length == 1 then return col.first
 520                 for t1 in col do
 521                         if t1 == null then continue # return null
 522                         var found = true
 523                         for t2 in col do
 524                                 if t2 == null then continue # return null
 525                                 if can_be_null(t2) and not can_be_null(t1) then
 526                                         t1 = t1.as_nullable
 527                                 end
 528                                 if not is_subtype(t2, t1) then found = false
 529                         end
 530                         if found then
 531                                 #print "merge {col.join(" ")} -> {t1}"
 532                                 return t1
 533                         end
 534                 end
 535                 #self.modelbuilder.warning(node, "Type Error: {col.length} conflicting types: <{col.join(", ")}>")
 536                 return null
 537         end
 538 end
 539
 540 # Mapping between parameters and arguments in a call.
 541 #
 542 # Parameters and arguments are not stored in the class but referenced by their position (starting from 0)
 543 #
 544 # The point of this class is to help engine and other things to map arguments in the AST to parameters of the model.
 545 class SignatureMap
 546         # Associate a parameter to an argument
 547         var map = new ArrayMap[Int, Int]
 548
 549         # The length of the vararg sequence
 550         # 0 if no vararg or if reverse vararg (cf `AVarargExpr`)
 551         var vararg_decl: Int = 0
 552 end
 553
 554 # A specific method call site with its associated informations.
 555 class CallSite
 556         # The associated node for location
 557         var node: ANode
 558
 559         # The static type of the receiver (possibly unresolved)
 560         var recv: MType
 561
 562         # The module where the callsite is present
 563         var mmodule: MModule
 564
 565         # The anchor to use with `recv` or `msignature`
 566         var anchor: nullable MClassType
 567
 568         # Is the receiver self?
 569         # If "for_self", virtual types of the signature are kept
 570         # If "not_for_self", virtual type are erased
 571         var recv_is_self: Bool
 572
 573         # The designated method
 574         var mproperty: MMethod
 575
 576         # The statically designated method definition
 577         # The most specif one, it is.
 578         var mpropdef: MMethodDef
 579
 580         # The resolved signature for the receiver
 581         var msignature: MSignature
 582
 583         # Is a implicit cast required on erasure typing policy?
 584         var erasure_cast: Bool
 585
 586         # The mapping used on the call to associate arguments to parameters
 587         # If null then no specific association is required.
 588         var signaturemap: nullable SignatureMap = null
 589
 590         private fun check_signature(v: TypeVisitor, args: Array[AExpr]): Bool
 591         do
 592                 var map = v.check_signature(self.node, args, self.mproperty, self.msignature)
 593                 signaturemap = map
 594                 return map == null
 595         end
 596 end
 597
 598 redef class Variable
 599         # The declared type of the variable
 600         var declared_type: nullable MType
 601
 602         # Was the variable type-adapted?
 603         # This is used to speedup type retrieval while it remains `false`
 604         private var is_adapted = false
 605 end
 606
 607 redef class FlowContext
 608         # Store changes of types because of type evolution
 609         private var vars = new HashMap[Variable, nullable MType]
 610
 611         # Adapt the variable to a static type
 612         # Warning1: do not modify vars directly.
 613         # Warning2: sub-flow may have cached a unadapted variable
 614         private fun set_var(v: TypeVisitor, variable: Variable, mtype: nullable MType)
 615         do
 616                 if variable.declared_type == mtype and not variable.is_adapted then return
 617                 if vars.has_key(variable) and vars[variable] == mtype then return
 618                 self.vars[variable] = mtype
 619                 v.dirty = true
 620                 variable.is_adapted = true
 621                 #node.debug "set {variable} to {mtype or else "X"}"
 622         end
 623
 624         # Look in the flow and previous flow and collect all first reachable type adaptation of a local variable
 625         private fun collect_types(variable: Variable): Array[nullable MType]
 626         do
 627                 #node.debug "flow for {variable}"
 628                 var res = new Array[nullable MType]
 629
 630                 var todo = [self]
 631                 var seen = new HashSet[FlowContext]
 632                 while not todo.is_empty do
 633                         var f = todo.pop
 634                         if f.is_unreachable then continue
 635                         if seen.has(f) then continue
 636                         seen.add f
 637
 638                         if f.vars.has_key(variable) then
 639                                 # Found something. Collect it and do not process further on this path
 640                                 res.add f.vars[variable]
 641                                 #f.node.debug "process {variable}: got {f.vars[variable] or else "X"}"
 642                         else
 643                                 todo.add_all f.previous
 644                                 todo.add_all f.loops
 645                                 if f.previous.is_empty then
 646                                         # Root flowcontext mean a parameter or something related
 647                                         res.add variable.declared_type
 648                                         #f.node.debug "root process {variable}: got {variable.declared_type or else "X"}"
 649                                 end
 650                         end
 651                 end
 652                 #self.node.debug "##### end flow for {variable}: {res.join(" ")}"
 653                 return res
 654         end
 655 end
 656
 657 redef class APropdef
 658         # The entry point of the whole typing analysis
 659         fun do_typing(modelbuilder: ModelBuilder)
 660         do
 661         end
 662
 663         # The variable associated to the receiver (if any)
 664         var selfvariable: nullable Variable
 665 end
 666
 667 redef class AMethPropdef
 668         redef fun do_typing(modelbuilder: ModelBuilder)
 669         do
 670                 var nblock = self.n_block
 671                 if nblock == null then return
 672
 673                 var mpropdef = self.mpropdef
 674                 if mpropdef == null then return # skip error
 675
 676                 var v = new TypeVisitor(modelbuilder, mpropdef.mclassdef.mmodule, mpropdef)
 677                 self.selfvariable = v.selfvariable
 678
 679                 var mmethoddef = self.mpropdef.as(not null)
 680                 var msignature = mmethoddef.msignature
 681                 if msignature == null then return # skip error
 682                 for i in [0..msignature.arity[ do
 683                         var mtype = msignature.mparameters[i].mtype
 684                         if msignature.vararg_rank == i then
 685                                 var arrayclass = v.get_mclass(self.n_signature.n_params[i], "Array")
 686                                 if arrayclass == null then return # Skip error
 687                                 mtype = arrayclass.get_mtype([mtype])
 688                         end
 689                         var variable = self.n_signature.n_params[i].variable
 690                         assert variable != null
 691                         variable.declared_type = mtype
 692                 end
 693
 694                 loop
 695                         v.dirty = false
 696                         v.visit_stmt(nblock)
 697                         if not v.has_loop or not v.dirty then break
 698                 end
 699
 700                 if not nblock.after_flow_context.is_unreachable and msignature.return_mtype != null then
 701                         # We reach the end of the function without having a return, it is bad
 702                         v.error(self, "Error: reached end of function; expected `return` with a value.")
 703                 end
 704         end
 705 end
 706
 707 redef class AAttrPropdef
 708         redef fun do_typing(modelbuilder: ModelBuilder)
 709         do
 710                 if not has_value then return
 711
 712                 var mpropdef = self.mpropdef
 713                 if mpropdef == null then return # skip error
 714
 715                 var v = new TypeVisitor(modelbuilder, mpropdef.mclassdef.mmodule, mpropdef)
 716                 self.selfvariable = v.selfvariable
 717
 718                 var nexpr = self.n_expr
 719                 if nexpr != null then
 720                         var mtype = self.mpropdef.static_mtype
 721                         v.visit_expr_subtype(nexpr, mtype)
 722                 end
 723                 var nblock = self.n_block
 724                 if nblock != null then
 725                         v.visit_stmt(nblock)
 726                         if not nblock.after_flow_context.is_unreachable then
 727                                 # We reach the end of the init without having a return, it is bad
 728                                 v.error(self, "Error: reached end of block; expected `return`.")
 729                         end
 730                 end
 731         end
 732 end
 733
 734 ###
 735
 736 redef class AExpr
 737         # The static type of the expression.
 738         # null if self is a statement or in case of error
 739         var mtype: nullable MType = null
 740
 741         # Is the statement correctly typed?
 742         # Used to distinguish errors and statements when `mtype == null`
 743         var is_typed: Bool = false
 744
 745         # If required, the following implicit cast `.as(XXX)`
 746         # Such a cast may by required after evaluating the expression when
 747         # a unsafe operation is detected (silently accepted by the Nit language).
 748         # The attribute is computed by `check_subtype`
 749         var implicit_cast_to: nullable MType = null
 750
 751         # Return the variable read (if any)
 752         # Used to perform adaptive typing
 753         fun its_variable: nullable Variable do return null
 754
 755         private fun accept_typing(v: TypeVisitor)
 756         do
 757                 v.error(self, "no implemented accept_typing for {self.class_name}")
 758         end
 759
 760         # Is non-null if `self` is a leaf of a comprehension array construction.
 761         # In this case, the enclosing literal array node is designated.
 762         # The result of the evaluation of `self` must be
 763         # stored inside the designated array (there is an implicit `push`)
 764         var comprehension: nullable AArrayExpr = null
 765 end
 766
 767 redef class ABlockExpr
 768         redef fun accept_typing(v)
 769         do
 770                 for e in self.n_expr do v.visit_stmt(e)
 771                 self.is_typed = true
 772         end
 773
 774         # The type of a blockexpr is the one of the last expression (or null if empty)
 775         redef fun mtype
 776         do
 777                 if self.n_expr.is_empty then return null
 778                 return self.n_expr.last.mtype
 779         end
 780 end
 781
 782 redef class AVardeclExpr
 783         redef fun accept_typing(v)
 784         do
 785                 var variable = self.variable
 786                 if variable == null then return # Skip error
 787
 788                 var ntype = self.n_type
 789                 var mtype: nullable MType
 790                 if ntype == null then
 791                         mtype = null
 792                 else
 793                         mtype = v.resolve_mtype(ntype)
 794                         if mtype == null then return # Skip error
 795                 end
 796
 797                 var nexpr = self.n_expr
 798                 if nexpr != null then
 799                         if mtype != null then
 800                                 var etype = v.visit_expr_subtype(nexpr, mtype)
 801                                 if etype == mtype then
 802                                         assert ntype != null
 803                                         v.modelbuilder.advice(ntype, "useless-type", "Warning: useless type definition for variable `{variable.name}`")
 804                                 end
 805                         else
 806                                 mtype = v.visit_expr(nexpr)
 807                                 if mtype == null then return # Skip error
 808                         end
 809                 end
 810
 811                 var decltype = mtype
 812                 if mtype == null or mtype isa MNullType then
 813                         var objclass = v.get_mclass(self, "Object")
 814                         if objclass == null then return # skip error
 815                         decltype = objclass.mclass_type.as_nullable
 816                         if mtype == null then mtype = decltype
 817                 end
 818
 819                 variable.declared_type = decltype
 820                 v.set_variable(self, variable, mtype)
 821
 822                 #debug("var {variable}: {mtype}")
 823
 824                 self.mtype = mtype
 825                 self.is_typed = true
 826         end
 827 end
 828
 829 redef class AVarExpr
 830         redef fun its_variable do return self.variable
 831         redef fun accept_typing(v)
 832         do
 833                 var variable = self.variable
 834                 if variable == null then return # Skip error
 835
 836                 var mtype = v.get_variable(self, variable)
 837                 if mtype != null then
 838                         #debug("{variable} is {mtype}")
 839                 else
 840                         #debug("{variable} is untyped")
 841                 end
 842
 843                 self.mtype = mtype
 844         end
 845 end
 846
 847 redef class AVarAssignExpr
 848         redef fun accept_typing(v)
 849         do
 850                 var variable = self.variable
 851                 assert variable != null
 852
 853                 var mtype = v.visit_expr_subtype(n_value, variable.declared_type)
 854
 855                 v.set_variable(self, variable, mtype)
 856
 857                 self.is_typed = true
 858         end
 859 end
 860
 861 redef class AReassignFormExpr
 862         # The method designed by the reassign operator.
 863         var reassign_callsite: nullable CallSite
 864
 865         var read_type: nullable MType = null
 866
 867         # Determine the `reassign_property`
 868         # `readtype` is the type of the reading of the left value.
 869         # `writetype` is the type of the writing of the left value.
 870         # (Because of `ACallReassignExpr`, both can be different.
 871         # Return the static type of the value to store.
 872         private fun resolve_reassignment(v: TypeVisitor, readtype, writetype: MType): nullable MType
 873         do
 874                 var reassign_name = self.n_assign_op.operator
 875
 876                 self.read_type = readtype
 877
 878                 var callsite = v.get_method(self.n_assign_op, readtype, reassign_name, false)
 879                 if callsite == null then return null # Skip error
 880                 self.reassign_callsite = callsite
 881
 882                 var msignature = callsite.msignature
 883                 var rettype = msignature.return_mtype
 884                 assert msignature.arity == 1 and rettype != null
 885
 886                 var value_type = v.visit_expr_subtype(self.n_value, msignature.mparameters.first.mtype)
 887                 if value_type == null then return null # Skip error
 888
 889                 v.check_subtype(self, rettype, writetype, false)
 890                 return rettype
 891         end
 892 end
 893
 894 redef class AVarReassignExpr
 895         redef fun accept_typing(v)
 896         do
 897                 var variable = self.variable
 898                 assert variable != null
 899
 900                 var readtype = v.get_variable(self, variable)
 901                 if readtype == null then return
 902
 903                 read_type = readtype
 904
 905                 var writetype = variable.declared_type
 906                 if writetype == null then return
 907
 908                 var rettype = self.resolve_reassignment(v, readtype, writetype)
 909
 910                 v.set_variable(self, variable, rettype)
 911
 912                 self.is_typed = true
 913         end
 914 end
 915
 916
 917 redef class AContinueExpr
 918         redef fun accept_typing(v)
 919         do
 920                 var nexpr = self.n_expr
 921                 if nexpr != null then
 922                         v.visit_expr(nexpr)
 923                 end
 924                 self.is_typed = true
 925         end
 926 end
 927
 928 redef class ABreakExpr
 929         redef fun accept_typing(v)
 930         do
 931                 var nexpr = self.n_expr
 932                 if nexpr != null then
 933                         v.visit_expr(nexpr)
 934                 end
 935                 self.is_typed = true
 936         end
 937 end
 938
 939 redef class AReturnExpr
 940         redef fun accept_typing(v)
 941         do
 942                 var nexpr = self.n_expr
 943                 var ret_type
 944                 var mpropdef = v.mpropdef
 945                 if mpropdef isa MMethodDef then
 946                         ret_type = mpropdef.msignature.return_mtype
 947                 else if mpropdef isa MAttributeDef then
 948                         ret_type = mpropdef.static_mtype
 949                 else
 950                         abort
 951                 end
 952                 if nexpr != null then
 953                         if ret_type != null then
 954                                 v.visit_expr_subtype(nexpr, ret_type)
 955                         else
 956                                 v.visit_expr(nexpr)
 957                                 v.error(nexpr, "Error: `return` with value in a procedure.")
 958                         end
 959                 else if ret_type != null then
 960                         v.error(self, "Error: `return` without value in a function.")
 961                 end
 962                 self.is_typed = true
 963         end
 964 end
 965
 966 redef class AAbortExpr
 967         redef fun accept_typing(v)
 968         do
 969                 self.is_typed = true
 970         end
 971 end
 972
 973 redef class AIfExpr
 974         redef fun accept_typing(v)
 975         do
 976                 v.visit_expr_bool(n_expr)
 977
 978                 v.visit_stmt(n_then)
 979                 v.visit_stmt(n_else)
 980
 981                 self.is_typed = true
 982
 983                 if n_then != null and n_else == null then
 984                         self.mtype = n_then.mtype
 985                 end
 986         end
 987 end
 988
 989 redef class AIfexprExpr
 990         redef fun accept_typing(v)
 991         do
 992                 v.visit_expr_bool(n_expr)
 993
 994                 var t1 = v.visit_expr(n_then)
 995                 var t2 = v.visit_expr(n_else)
 996
 997                 if t1 == null or t2 == null then
 998                         return # Skip error
 999                 end
1000
1001                 var t = v.merge_types(self, [t1, t2])
1002                 if t == null then
1003                         v.error(self, "Type Error: ambiguous type `{t1}` vs `{t2}`.")
1004                 end
1005                 self.mtype = t
1006         end
1007 end
1008
1009 redef class ADoExpr
1010         redef fun accept_typing(v)
1011         do
1012                 v.visit_stmt(n_block)
1013                 self.is_typed = true
1014         end
1015 end
1016
1017 redef class AWhileExpr
1018         redef fun accept_typing(v)
1019         do
1020                 v.has_loop = true
1021                 v.visit_expr_bool(n_expr)
1022                 v.visit_stmt(n_block)
1023                 self.is_typed = true
1024         end
1025 end
1026
1027 redef class ALoopExpr
1028         redef fun accept_typing(v)
1029         do
1030                 v.has_loop = true
1031                 v.visit_stmt(n_block)
1032                 self.is_typed = true
1033         end
1034 end
1035
1036 redef class AForExpr
1037         var coltype: nullable MClassType
1038
1039         var method_iterator: nullable CallSite
1040         var method_is_ok: nullable CallSite
1041         var method_item: nullable CallSite
1042         var method_next: nullable CallSite
1043         var method_key: nullable CallSite
1044         var method_finish: nullable CallSite
1045
1046         var method_lt: nullable CallSite
1047         var method_successor: nullable CallSite
1048
1049         private fun do_type_iterator(v: TypeVisitor, mtype: MType)
1050         do
1051                 if mtype isa MNullType then
1052                         v.error(self, "Type Error: `for` cannot iterate over `null`.")
1053                         return
1054                 end
1055
1056                 # get obj class
1057                 var objcla = v.get_mclass(self, "Object")
1058                 if objcla == null then return
1059
1060                 # check iterator method
1061                 var itdef = v.get_method(self, mtype, "iterator", n_expr isa ASelfExpr)
1062                 if itdef == null then
1063                         v.error(self, "Type Error: `for` expects a type providing an `iterator` method, got `{mtype}`.")
1064                         return
1065                 end
1066                 self.method_iterator = itdef
1067
1068                 # check that iterator return something
1069                 var ittype = itdef.msignature.return_mtype
1070                 if ittype == null then
1071                         v.error(self, "Type Error: `for` expects the method `iterator` to return an `Iterator` or `MapIterator` type.")
1072                         return
1073                 end
1074
1075                 # get iterator type
1076                 var colit_cla = v.try_get_mclass(self, "Iterator")
1077                 var mapit_cla = v.try_get_mclass(self, "MapIterator")
1078                 var is_col = false
1079                 var is_map = false
1080
1081                 if colit_cla != null and v.is_subtype(ittype, colit_cla.get_mtype([objcla.mclass_type.as_nullable])) then
1082                         # Iterator
1083                         var coltype = ittype.supertype_to(v.mmodule, v.anchor, colit_cla)
1084                         var variables =  self.variables
1085                         if variables.length != 1 then
1086                                 v.error(self, "Type Error: `for` expects only one variable when using `Iterator`.")
1087                         else
1088                                 variables.first.declared_type = coltype.arguments.first
1089                         end
1090                         is_col = true
1091                 end
1092
1093                 if mapit_cla != null and v.is_subtype(ittype, mapit_cla.get_mtype([objcla.mclass_type.as_nullable, objcla.mclass_type.as_nullable])) then
1094                         # Map Iterator
1095                         var coltype = ittype.supertype_to(v.mmodule, v.anchor, mapit_cla)
1096                         var variables = self.variables
1097                         if variables.length != 2 then
1098                                 v.error(self, "Type Error: `for` expects two variables when using `MapIterator`.")
1099                         else
1100                                 variables[0].declared_type = coltype.arguments[0]
1101                                 variables[1].declared_type = coltype.arguments[1]
1102                         end
1103                         is_map = true
1104                 end
1105
1106                 if not is_col and not is_map then
1107                         v.error(self, "Type Error: `for` expects the method `iterator` to return an `Iterator` or `MapIterator` type.")
1108                         return
1109                 end
1110
1111                 # anchor formal and virtual types
1112                 if mtype.need_anchor then mtype = v.anchor_to(mtype)
1113
1114                 mtype = mtype.undecorate
1115                 self.coltype = mtype.as(MClassType)
1116
1117                 # get methods is_ok, next, item
1118                 var ikdef = v.get_method(self, ittype, "is_ok", false)
1119                 if ikdef == null then
1120                         v.error(self, "Type Error: `for` expects a method `is_ok` in type `{ittype}`.")
1121                         return
1122                 end
1123                 self.method_is_ok = ikdef
1124
1125                 var itemdef = v.get_method(self, ittype, "item", false)
1126                 if itemdef == null then
1127                         v.error(self, "Type Error: `for` expects a method `item` in type `{ittype}`.")
1128                         return
1129                 end
1130                 self.method_item = itemdef
1131
1132                 var nextdef = v.get_method(self, ittype, "next", false)
1133                 if nextdef == null then
1134                         v.error(self, "Type Error: `for` expects a method `next` in type {ittype}.")
1135                         return
1136                 end
1137                 self.method_next = nextdef
1138
1139                 self.method_finish = v.try_get_method(self, ittype, "finish", false)
1140
1141                 if is_map then
1142                         var keydef = v.get_method(self, ittype, "key", false)
1143                         if keydef == null then
1144                                 v.error(self, "Type Error: `for` expects a method `key` in type `{ittype}`.")
1145                                 return
1146                         end
1147                         self.method_key = keydef
1148                 end
1149
1150                 if self.variables.length == 1 and n_expr isa ARangeExpr then
1151                         var variable = variables.first
1152                         var vtype = variable.declared_type.as(not null)
1153
1154                         if n_expr isa AOrangeExpr then
1155                                 self.method_lt = v.get_method(self, vtype, "<", false)
1156                         else
1157                                 self.method_lt = v.get_method(self, vtype, "<=", false)
1158                         end
1159
1160                         self.method_successor = v.get_method(self, vtype, "successor", false)
1161                 end
1162         end
1163
1164         redef fun accept_typing(v)
1165         do
1166                 v.has_loop = true
1167                 var mtype = v.visit_expr(n_expr)
1168                 if mtype == null then return
1169
1170                 self.do_type_iterator(v, mtype)
1171
1172                 v.visit_stmt(n_block)
1173
1174                 self.mtype = n_block.mtype
1175                 self.is_typed = true
1176         end
1177 end
1178
1179 redef class AWithExpr
1180         var method_start: nullable CallSite
1181         var method_finish: nullable CallSite
1182
1183         redef fun accept_typing(v: TypeVisitor)
1184         do
1185                 var mtype = v.visit_expr(n_expr)
1186                 if mtype == null then return
1187
1188                 method_start = v.get_method(self, mtype, "start", n_expr isa ASelfExpr)
1189                 method_finish = v.get_method(self, mtype, "finish", n_expr isa ASelfExpr)
1190
1191                 v.visit_stmt(n_block)
1192                 self.mtype = n_block.mtype
1193                 self.is_typed = true
1194         end
1195 end
1196
1197 redef class AAssertExpr
1198         redef fun accept_typing(v)
1199         do
1200                 v.visit_expr_bool(n_expr)
1201
1202                 v.visit_stmt(n_else)
1203                 self.is_typed = true
1204         end
1205 end
1206
1207 redef class AOrExpr
1208         redef fun accept_typing(v)
1209         do
1210                 v.visit_expr_bool(n_expr)
1211                 v.visit_expr_bool(n_expr2)
1212                 self.mtype = v.type_bool(self)
1213         end
1214 end
1215
1216 redef class AImpliesExpr
1217         redef fun accept_typing(v)
1218         do
1219                 v.visit_expr_bool(n_expr)
1220                 v.visit_expr_bool(n_expr2)
1221                 self.mtype = v.type_bool(self)
1222         end
1223 end
1224
1225 redef class AAndExpr
1226         redef fun accept_typing(v)
1227         do
1228                 v.visit_expr_bool(n_expr)
1229                 v.visit_expr_bool(n_expr2)
1230                 self.mtype = v.type_bool(self)
1231         end
1232 end
1233
1234
1235 redef class ANotExpr
1236         redef fun accept_typing(v)
1237         do
1238                 v.visit_expr_bool(n_expr)
1239                 self.mtype = v.type_bool(self)
1240         end
1241 end
1242
1243 redef class AOrElseExpr
1244         redef fun accept_typing(v)
1245         do
1246                 var t1 = v.visit_expr(n_expr)
1247                 var t2 = v.visit_expr(n_expr2)
1248
1249                 if t1 == null or t2 == null then
1250                         return # Skip error
1251                 end
1252
1253                 if t1 isa MNullType then
1254                         v.error(n_expr, "Type Error: `or else` on `null`.")
1255                 else if v.check_can_be_null(n_expr, t1) then
1256                         t1 = t1.as_notnull
1257                 end
1258
1259                 var t = v.merge_types(self, [t1, t2])
1260                 if t == null then
1261                         var c = v.get_mclass(self, "Object")
1262                         if c == null then return # forward error
1263                         t = c.mclass_type
1264                         if v.can_be_null(t2) then
1265                                 t = t.as_nullable
1266                         end
1267                         #v.error(self, "Type Error: ambiguous type {t1} vs {t2}")
1268                 end
1269                 self.mtype = t
1270         end
1271 end
1272
1273 redef class ATrueExpr
1274         redef fun accept_typing(v)
1275         do
1276                 self.mtype = v.type_bool(self)
1277         end
1278 end
1279
1280 redef class AFalseExpr
1281         redef fun accept_typing(v)
1282         do
1283                 self.mtype = v.type_bool(self)
1284         end
1285 end
1286
1287 redef class AIntExpr
1288         redef fun accept_typing(v)
1289         do
1290                 var mclass = v.get_mclass(self, "Int")
1291                 if mclass == null then return # Forward error
1292                 self.mtype = mclass.mclass_type
1293         end
1294 end
1295
1296 redef class AFloatExpr
1297         redef fun accept_typing(v)
1298         do
1299                 var mclass = v.get_mclass(self, "Float")
1300                 if mclass == null then return # Forward error
1301                 self.mtype = mclass.mclass_type
1302         end
1303 end
1304
1305 redef class ACharExpr
1306         redef fun accept_typing(v)
1307         do
1308                 var mclass = v.get_mclass(self, "Char")
1309                 if mclass == null then return # Forward error
1310                 self.mtype = mclass.mclass_type
1311         end
1312 end
1313
1314 redef class AStringFormExpr
1315         redef fun accept_typing(v)
1316         do
1317                 var mclass = v.get_mclass(self, "String")
1318                 if mclass == null then return # Forward error
1319                 self.mtype = mclass.mclass_type
1320         end
1321 end
1322
1323 redef class ASuperstringExpr
1324         redef fun accept_typing(v)
1325         do
1326                 var mclass = v.get_mclass(self, "String")
1327                 if mclass == null then return # Forward error
1328                 self.mtype = mclass.mclass_type
1329                 var objclass = v.get_mclass(self, "Object")
1330                 if objclass == null then return # Forward error
1331                 var objtype = objclass.mclass_type
1332                 for nexpr in self.n_exprs do
1333                         v.visit_expr_subtype(nexpr, objtype)
1334                 end
1335         end
1336 end
1337
1338 redef class AArrayExpr
1339         # The `with_capacity` method on Array
1340         var with_capacity_callsite: nullable CallSite
1341
1342         # The `push` method on arrays
1343         var push_callsite: nullable CallSite
1344
1345         # The element of each type
1346         var element_mtype: nullable MType
1347
1348         # Set that `self` is a part of comprehension array `na`
1349         # If `self` is a `for`, or a `if`, then `set_comprehension` is recursively applied.
1350         private fun set_comprehension(n: nullable AExpr)
1351         do
1352                 if n == null then
1353                         return
1354                 else if n isa AForExpr then
1355                         set_comprehension(n.n_block)
1356                 else if n isa AIfExpr then
1357                         set_comprehension(n.n_then)
1358                         set_comprehension(n.n_else)
1359                 else
1360                         # is a leave
1361                         n.comprehension = self
1362                 end
1363         end
1364         redef fun accept_typing(v)
1365         do
1366                 var mtype: nullable MType = null
1367                 var ntype = self.n_type
1368                 if ntype != null then
1369                         mtype = v.resolve_mtype(ntype)
1370                         if mtype == null then return # Skip error
1371                 end
1372                 var mtypes = new Array[nullable MType]
1373                 var useless = false
1374                 for e in self.n_exprs do
1375                         var t = v.visit_expr(e)
1376                         if t == null then
1377                                 return # Skip error
1378                         end
1379                         set_comprehension(e)
1380                         if mtype != null then
1381                                 if v.check_subtype(e, t, mtype, false) == null then return # Forward error
1382                                 if t == mtype then useless = true
1383                         else
1384                                 mtypes.add(t)
1385                         end
1386                 end
1387                 if mtype == null then
1388                         # Ensure monotony for type adaptation on loops
1389                         if self.element_mtype != null then mtypes.add self.element_mtype
1390                         mtype = v.merge_types(self, mtypes)
1391                 end
1392                 if mtype == null or mtype isa MNullType then
1393                         v.error(self, "Type Error: ambiguous array type {mtypes.join(" ")}")
1394                         return
1395                 end
1396                 if useless then
1397                         assert ntype != null
1398                         v.modelbuilder.warning(ntype, "useless-type", "Warning: useless type declaration `{mtype}` in literal Array since it can be inferred from the elements type.")
1399                 end
1400
1401                 self.element_mtype = mtype
1402
1403                 var mclass = v.get_mclass(self, "Array")
1404                 if mclass == null then return # Forward error
1405                 var array_mtype = mclass.get_mtype([mtype])
1406
1407                 with_capacity_callsite = v.get_method(self, array_mtype, "with_capacity", false)
1408                 push_callsite = v.get_method(self, array_mtype, "push", false)
1409
1410                 self.mtype = array_mtype
1411         end
1412 end
1413
1414 redef class ARangeExpr
1415         var init_callsite: nullable CallSite
1416
1417         redef fun accept_typing(v)
1418         do
1419                 var discrete_class = v.get_mclass(self, "Discrete")
1420                 if discrete_class == null then return # Forward error
1421                 var discrete_type = discrete_class.intro.bound_mtype
1422                 var t1 = v.visit_expr_subtype(self.n_expr, discrete_type)
1423                 var t2 = v.visit_expr_subtype(self.n_expr2, discrete_type)
1424                 if t1 == null or t2 == null then return
1425                 var mclass = v.get_mclass(self, "Range")
1426                 if mclass == null then return # Forward error
1427                 var mtype
1428                 if v.is_subtype(t1, t2) then
1429                         mtype = mclass.get_mtype([t2])
1430                 else if v.is_subtype(t2, t1) then
1431                         mtype = mclass.get_mtype([t1])
1432                 else
1433                         v.error(self, "Type Error: cannot create range: `{t1}` vs `{t2}`.")
1434                         return
1435                 end
1436
1437                 self.mtype = mtype
1438
1439                 # get the constructor
1440                 var callsite
1441                 if self isa ACrangeExpr then
1442                         callsite = v.get_method(self, mtype, "init", false)
1443                 else if self isa AOrangeExpr then
1444                         callsite = v.get_method(self, mtype, "without_last", false)
1445                 else
1446                         abort
1447                 end
1448                 init_callsite = callsite
1449         end
1450 end
1451
1452 redef class ANullExpr
1453         redef fun accept_typing(v)
1454         do
1455                 self.mtype = v.mmodule.model.null_type
1456         end
1457 end
1458
1459 redef class AIsaExpr
1460         # The static type to cast to.
1461         # (different from the static type of the expression that is `Bool`).
1462         var cast_type: nullable MType
1463         redef fun accept_typing(v)
1464         do
1465                 var mtype = v.visit_expr_cast(self, self.n_expr, self.n_type)
1466                 self.cast_type = mtype
1467
1468                 var variable = self.n_expr.its_variable
1469                 if variable != null then
1470                         #var orig = self.n_expr.mtype
1471                         #var from = if orig != null then orig.to_s else "invalid"
1472                         #var to = if mtype != null then mtype.to_s else "invalid"
1473                         #debug("adapt {variable}: {from} -> {to}")
1474                         self.after_flow_context.when_true.set_var(v, variable, mtype)
1475                 end
1476
1477                 self.mtype = v.type_bool(self)
1478         end
1479 end
1480
1481 redef class AAsCastExpr
1482         redef fun accept_typing(v)
1483         do
1484                 self.mtype = v.visit_expr_cast(self, self.n_expr, self.n_type)
1485         end
1486 end
1487
1488 redef class AAsNotnullExpr
1489         redef fun accept_typing(v)
1490         do
1491                 var mtype = v.visit_expr(self.n_expr)
1492                 if mtype == null then return # Forward error
1493
1494                 if mtype isa MNullType then
1495                         v.error(self, "Type Error: `as(not null)` on `null`.")
1496                         return
1497                 end
1498
1499                 if v.check_can_be_null(n_expr, mtype) then
1500                         mtype = mtype.as_notnull
1501                 end
1502
1503                 self.mtype = mtype
1504         end
1505 end
1506
1507 redef class AParExpr
1508         redef fun accept_typing(v)
1509         do
1510                 self.mtype = v.visit_expr(self.n_expr)
1511         end
1512 end
1513
1514 redef class AOnceExpr
1515         redef fun accept_typing(v)
1516         do
1517                 self.mtype = v.visit_expr(self.n_expr)
1518         end
1519 end
1520
1521 redef class ASelfExpr
1522         redef var its_variable: nullable Variable
1523         redef fun accept_typing(v)
1524         do
1525                 if v.is_toplevel_context and not self isa AImplicitSelfExpr then
1526                         v.error(self, "Error: `self` cannot be used in top-level method.")
1527                 end
1528                 var variable = v.selfvariable
1529                 self.its_variable = variable
1530                 self.mtype = v.get_variable(self, variable)
1531         end
1532 end
1533
1534 redef class AImplicitSelfExpr
1535         # Is the implicit receiver `sys`?
1536         #
1537         # By default, the implicit receiver is `self`.
1538         # But when there is not method for `self`, `sys` is used as a fall-back.
1539         # Is this case this flag is set to `true`.
1540         var is_sys = false
1541 end
1542
1543 ## MESSAGE SENDING AND PROPERTY
1544
1545 redef class ASendExpr
1546         # The property invoked by the send.
1547         var callsite: nullable CallSite
1548
1549         redef fun accept_typing(v)
1550         do
1551                 var nrecv = self.n_expr
1552                 var recvtype = v.visit_expr(nrecv)
1553                 var name = self.property_name
1554                 var node = self.property_node
1555
1556                 if recvtype == null then return # Forward error
1557
1558                 var callsite = null
1559                 var unsafe_type = v.anchor_to(recvtype)
1560                 var mproperty = v.try_get_mproperty_by_name2(node, unsafe_type, name)
1561                 if mproperty == null and nrecv isa AImplicitSelfExpr then
1562                         # Special fall-back search in `sys` when noting found in the implicit receiver.
1563                         var sysclass = v.try_get_mclass(node, "Sys")
1564                         if sysclass != null then
1565                                 var systype = sysclass.mclass_type
1566                                 mproperty = v.try_get_mproperty_by_name2(node, systype, name)
1567                                 if mproperty != null then
1568                                         callsite = v.get_method(node, systype, name, false)
1569                                         if callsite == null then return # Forward error
1570                                         # Update information, we are looking at `sys` now, not `self`
1571                                         nrecv.is_sys = true
1572                                         nrecv.its_variable = null
1573                                         nrecv.mtype = systype
1574                                         recvtype = systype
1575                                 end
1576                         end
1577                 end
1578                 if callsite == null then
1579                         # If still nothing, just exit
1580                         callsite = v.get_method(node, recvtype, name, nrecv isa ASelfExpr)
1581                         if callsite == null then return
1582                 end
1583
1584                 self.callsite = callsite
1585                 var msignature = callsite.msignature
1586
1587                 var args = compute_raw_arguments
1588
1589                 callsite.check_signature(v, args)
1590
1591                 if callsite.mproperty.is_init then
1592                         var vmpropdef = v.mpropdef
1593                         if not (vmpropdef isa MMethodDef and vmpropdef.mproperty.is_init) then
1594                                 v.error(node, "Error: an `init` can only be called from another `init`.")
1595                         end
1596                         if vmpropdef isa MMethodDef and vmpropdef.mproperty.is_root_init and not callsite.mproperty.is_root_init then
1597                                 v.error(node, "Error: `{vmpropdef}` cannot call a factory `{callsite.mproperty}`.")
1598                         end
1599                 end
1600
1601                 var ret = msignature.return_mtype
1602                 if ret != null then
1603                         self.mtype = ret
1604                 else
1605                         self.is_typed = true
1606                 end
1607         end
1608
1609         # The name of the property
1610         # Each subclass simply provide the correct name.
1611         private fun property_name: String is abstract
1612
1613         # The node identifying the name (id, operator, etc) for messages.
1614         #
1615         # Is `self` by default
1616         private fun property_node: ANode do return self
1617
1618         # An array of all arguments (excluding self)
1619         fun raw_arguments: Array[AExpr] do return compute_raw_arguments
1620
1621         private fun compute_raw_arguments: Array[AExpr] is abstract
1622 end
1623
1624 redef class ABinopExpr
1625         redef fun compute_raw_arguments do return [n_expr2]
1626         redef fun property_name do return operator
1627         redef fun property_node do return n_op
1628 end
1629 redef class AEqExpr
1630         redef fun accept_typing(v)
1631         do
1632                 super
1633                 v.null_test(self)
1634         end
1635 end
1636 redef class ANeExpr
1637         redef fun accept_typing(v)
1638         do
1639                 super
1640                 v.null_test(self)
1641         end
1642 end
1643
1644 redef class AUnaryopExpr
1645         redef fun property_name do return "unary {operator}"
1646         redef fun compute_raw_arguments do return new Array[AExpr]
1647 end
1648
1649
1650 redef class ACallExpr
1651         redef fun property_name do return n_id.text
1652         redef fun property_node do return n_id
1653         redef fun compute_raw_arguments do return n_args.to_a
1654 end
1655
1656 redef class ACallAssignExpr
1657         redef fun property_name do return n_id.text + "="
1658         redef fun property_node do return n_id
1659         redef fun compute_raw_arguments
1660         do
1661                 var res = n_args.to_a
1662                 res.add(n_value)
1663                 return res
1664         end
1665 end
1666
1667 redef class ABraExpr
1668         redef fun property_name do return "[]"
1669         redef fun compute_raw_arguments do return n_args.to_a
1670 end
1671
1672 redef class ABraAssignExpr
1673         redef fun property_name do return "[]="
1674         redef fun compute_raw_arguments
1675         do
1676                 var res = n_args.to_a
1677                 res.add(n_value)
1678                 return res
1679         end
1680 end
1681
1682 redef class ASendReassignFormExpr
1683         # The property invoked for the writing
1684         var write_callsite: nullable CallSite
1685
1686         redef fun accept_typing(v)
1687         do
1688                 var recvtype = v.visit_expr(self.n_expr)
1689                 var name = self.property_name
1690                 var node = self.property_node
1691
1692                 if recvtype == null then return # Forward error
1693
1694                 var for_self = self.n_expr isa ASelfExpr
1695                 var callsite = v.get_method(node, recvtype, name, for_self)
1696
1697                 if callsite == null then return
1698                 self.callsite = callsite
1699
1700                 var args = compute_raw_arguments
1701
1702                 callsite.check_signature(v, args)
1703
1704                 var readtype = callsite.msignature.return_mtype
1705                 if readtype == null then
1706                         v.error(node, "Error: `{name}` is not a function.")
1707                         return
1708                 end
1709
1710                 var wcallsite = v.get_method(node, recvtype, name + "=", self.n_expr isa ASelfExpr)
1711                 if wcallsite == null then return
1712                 self.write_callsite = wcallsite
1713
1714                 var wtype = self.resolve_reassignment(v, readtype, wcallsite.msignature.mparameters.last.mtype)
1715                 if wtype == null then return
1716
1717                 args = args.to_a # duplicate so raw_arguments keeps only the getter args
1718                 args.add(self.n_value)
1719                 wcallsite.check_signature(v, args)
1720
1721                 self.is_typed = true
1722         end
1723 end
1724
1725 redef class ACallReassignExpr
1726         redef fun property_name do return n_id.text
1727         redef fun property_node do return n_id
1728         redef fun compute_raw_arguments do return n_args.to_a
1729 end
1730
1731 redef class ABraReassignExpr
1732         redef fun property_name do return "[]"
1733         redef fun compute_raw_arguments do return n_args.to_a
1734 end
1735
1736 redef class AInitExpr
1737         redef fun property_name do return "init"
1738         redef fun property_node do return n_kwinit
1739         redef fun compute_raw_arguments do return n_args.to_a
1740 end
1741
1742 redef class AExprs
1743         fun to_a: Array[AExpr] do return self.n_exprs.to_a
1744 end
1745
1746 ###
1747
1748 redef class ASuperExpr
1749         # The method to call if the super is in fact a 'super init call'
1750         # Note: if the super is a normal call-next-method, then this attribute is null
1751         var callsite: nullable CallSite
1752
1753         # The method to call is the super is a standard `call-next-method` super-call
1754         # Note: if the super is a special super-init-call, then this attribute is null
1755         var mpropdef: nullable MMethodDef
1756
1757         redef fun accept_typing(v)
1758         do
1759                 var anchor = v.anchor
1760                 assert anchor != null
1761                 var recvtype = v.get_variable(self, v.selfvariable)
1762                 assert recvtype != null
1763                 var mproperty = v.mpropdef.mproperty
1764                 if not mproperty isa MMethod then
1765                         v.error(self, "Error: `super` only usable in a `method`.")
1766                         return
1767                 end
1768                 var superprops = mproperty.lookup_super_definitions(v.mmodule, anchor)
1769                 if superprops.length == 0 then
1770                         if mproperty.is_init and v.mpropdef.is_intro then
1771                                 process_superinit(v)
1772                                 return
1773                         end
1774                         v.error(self, "Error: no super method to call for `{mproperty}`.")
1775                         return
1776                 end
1777                 # FIXME: covariance of return type in linear extension?
1778                 var superprop = superprops.first
1779
1780                 var msignature = superprop.msignature.as(not null)
1781                 msignature = v.resolve_for(msignature, recvtype, true).as(MSignature)
1782                 var args = self.n_args.to_a
1783                 if args.length > 0 then
1784                         signaturemap = v.check_signature(self, args, mproperty, msignature)
1785                 end
1786                 self.mtype = msignature.return_mtype
1787                 self.is_typed = true
1788                 v.mpropdef.has_supercall = true
1789                 mpropdef = v.mpropdef.as(MMethodDef)
1790         end
1791
1792         # The mapping used on the call to associate arguments to parameters.
1793         # If null then no specific association is required.
1794         var signaturemap: nullable SignatureMap
1795
1796         private fun process_superinit(v: TypeVisitor)
1797         do
1798                 var anchor = v.anchor
1799                 assert anchor != null
1800                 var recvtype = v.get_variable(self, v.selfvariable)
1801                 assert recvtype != null
1802                 var mpropdef = v.mpropdef
1803                 assert mpropdef isa MMethodDef
1804                 var mproperty = mpropdef.mproperty
1805                 var superprop: nullable MMethodDef = null
1806                 for msupertype in mpropdef.mclassdef.supertypes do
1807                         msupertype = msupertype.anchor_to(v.mmodule, anchor)
1808                         var errcount = v.modelbuilder.toolcontext.error_count
1809                         var candidate = v.try_get_mproperty_by_name2(self, msupertype, mproperty.name).as(nullable MMethod)
1810                         if candidate == null then
1811                                 if v.modelbuilder.toolcontext.error_count > errcount then return # Forward error
1812                                 continue # Try next super-class
1813                         end
1814                         if superprop != null and candidate.is_root_init then
1815                                 continue
1816                         end
1817                         if superprop != null and superprop.mproperty != candidate and not superprop.mproperty.is_root_init then
1818                                 v.error(self, "Error: conflicting super constructor to call for `{mproperty}`: `{candidate.full_name}`, `{superprop.mproperty.full_name}`")
1819                                 return
1820                         end
1821                         var candidatedefs = candidate.lookup_definitions(v.mmodule, anchor)
1822                         if superprop != null and superprop.mproperty == candidate then
1823                                 if superprop == candidatedefs.first then continue
1824                                 candidatedefs.add(superprop)
1825                         end
1826                         if candidatedefs.length > 1 then
1827                                 v.error(self, "Error: conflicting property definitions for property `{mproperty}` in `{recvtype}`: {candidatedefs.join(", ")}")
1828                                 return
1829                         end
1830                         superprop = candidatedefs.first
1831                 end
1832                 if superprop == null then
1833                         v.error(self, "Error: no super method to call for `{mproperty}`.")
1834                         return
1835                 end
1836
1837                 var msignature = superprop.new_msignature or else superprop.msignature.as(not null)
1838                 msignature = v.resolve_for(msignature, recvtype, true).as(MSignature)
1839
1840                 var callsite = new CallSite(self, recvtype, v.mmodule, v.anchor, true, superprop.mproperty, superprop, msignature, false)
1841                 self.callsite = callsite
1842
1843                 var args = self.n_args.to_a
1844                 if args.length > 0 then
1845                         callsite.check_signature(v, args)
1846                 else
1847                         # Check there is at least enough parameters
1848                         if mpropdef.msignature.arity < msignature.arity then
1849                                 v.error(self, "Error: not enough implicit arguments to pass. Got `{mpropdef.msignature.arity}`, expected at least `{msignature.arity}`. Signature is `{msignature}`.")
1850                                 return
1851                         end
1852                         # Check that each needed parameter is conform
1853                         var i = 0
1854                         for sp in msignature.mparameters do
1855                                 var p = mpropdef.msignature.mparameters[i]
1856                                 if not v.is_subtype(p.mtype, sp.mtype) then
1857                                         v.error(self, "Type Error: expected argument #{i} of type `{sp.mtype}`, got implicit argument `{p.name}` of type `{p.mtype}`. Signature is {msignature}")
1858                                         return
1859                                 end
1860                                 i += 1
1861                         end
1862                 end
1863
1864                 self.is_typed = true
1865         end
1866 end
1867
1868 ####
1869
1870 redef class ANewExpr
1871         # The constructor invoked by the new.
1872         var callsite: nullable CallSite
1873
1874         # The designated type
1875         var recvtype: nullable MClassType
1876
1877         redef fun accept_typing(v)
1878         do
1879                 var recvtype = v.resolve_mtype(self.n_type)
1880                 if recvtype == null then return
1881
1882                 if not recvtype isa MClassType then
1883                         if recvtype isa MNullableType then
1884                                 v.error(self, "Type Error: cannot instantiate the nullable type `{recvtype}`.")
1885                                 return
1886                         else if recvtype isa MFormalType then
1887                                 v.error(self, "Type Error: cannot instantiate the formal type `{recvtype}`.")
1888                                 return
1889                         else
1890                                 v.error(self, "Type Error: cannot instantiate the type `{recvtype}`.")
1891                                 return
1892                         end
1893                 end
1894
1895                 self.recvtype = recvtype
1896                 var kind = recvtype.mclass.kind
1897
1898                 var name: String
1899                 var nid = self.n_id
1900                 var node: ANode
1901                 if nid != null then
1902                         name = nid.text
1903                         node = nid
1904                 else
1905                         name = "new"
1906                         node = self.n_kwnew
1907                 end
1908                 if name == "intern" then
1909                         if kind != concrete_kind then
1910                                 v.error(self, "Type Error: cannot instantiate {kind} {recvtype}.")
1911                                 return
1912                         end
1913                         if n_args.n_exprs.not_empty then
1914                                 v.error(n_args, "Type Error: the intern constructor expects no arguments.")
1915                                 return
1916                         end
1917                         # Our job is done
1918                         self.mtype = recvtype
1919                         return
1920                 end
1921
1922                 var callsite = v.get_method(node, recvtype, name, false)
1923                 if callsite == null then return
1924
1925                 if not callsite.mproperty.is_new then
1926                         if kind != concrete_kind then
1927                                 v.error(self, "Type Error: cannot instantiate {kind} `{recvtype}`.")
1928                                 return
1929                         end
1930                         self.mtype = recvtype
1931                 else
1932                         self.mtype = callsite.msignature.return_mtype
1933                         assert self.mtype != null
1934                 end
1935
1936                 self.callsite = callsite
1937
1938                 if not callsite.mproperty.is_init_for(recvtype.mclass) then
1939                         v.error(self, "Error: `{name}` is not a constructor.")
1940                         return
1941                 end
1942
1943                 var args = n_args.to_a
1944                 callsite.check_signature(v, args)
1945         end
1946 end
1947
1948 ####
1949
1950 redef class AAttrFormExpr
1951         # The attribute accessed.
1952         var mproperty: nullable MAttribute
1953
1954         # The static type of the attribute.
1955         var attr_type: nullable MType
1956
1957         # Resolve the attribute accessed.
1958         private fun resolve_property(v: TypeVisitor)
1959         do
1960                 var recvtype = v.visit_expr(self.n_expr)
1961                 if recvtype == null then return # Skip error
1962                 var node = self.n_id
1963                 var name = node.text
1964                 if recvtype isa MNullType then
1965                         v.error(node, "Error: attribute `{name}` access on `null`.")
1966                         return
1967                 end
1968
1969                 var unsafe_type = v.anchor_to(recvtype)
1970                 var mproperty = v.try_get_mproperty_by_name2(node, unsafe_type, name)
1971                 if mproperty == null then
1972                         v.modelbuilder.error(node, "Error: attribute `{name}` does not exist in `{recvtype}`.")
1973                         return
1974                 end
1975                 assert mproperty isa MAttribute
1976                 self.mproperty = mproperty
1977
1978                 var mpropdefs = mproperty.lookup_definitions(v.mmodule, unsafe_type)
1979                 assert mpropdefs.length == 1
1980                 var mpropdef = mpropdefs.first
1981                 var attr_type = mpropdef.static_mtype
1982                 if attr_type == null then return # skip error
1983                 attr_type = v.resolve_for(attr_type, recvtype, self.n_expr isa ASelfExpr)
1984                 self.attr_type = attr_type
1985         end
1986 end
1987
1988 redef class AAttrExpr
1989         redef fun accept_typing(v)
1990         do
1991                 self.resolve_property(v)
1992                 self.mtype = self.attr_type
1993         end
1994 end
1995
1996
1997 redef class AAttrAssignExpr
1998         redef fun accept_typing(v)
1999         do
2000                 self.resolve_property(v)
2001                 var mtype = self.attr_type
2002
2003                 v.visit_expr_subtype(self.n_value, mtype)
2004                 self.is_typed = true
2005         end
2006 end
2007
2008 redef class AAttrReassignExpr
2009         redef fun accept_typing(v)
2010         do
2011                 self.resolve_property(v)
2012                 var mtype = self.attr_type
2013                 if mtype == null then return # Skip error
2014
2015                 self.resolve_reassignment(v, mtype, mtype)
2016
2017                 self.is_typed = true
2018         end
2019 end
2020
2021 redef class AIssetAttrExpr
2022         redef fun accept_typing(v)
2023         do
2024                 self.resolve_property(v)
2025                 var mtype = self.attr_type
2026                 if mtype == null then return # Skip error
2027
2028                 var recvtype = self.n_expr.mtype.as(not null)
2029                 var bound = v.resolve_for(mtype, recvtype, false)
2030                 if bound isa MNullableType then
2031                         v.error(n_id, "Type Error: `isset` on a nullable attribute.")
2032                 end
2033                 self.mtype = v.type_bool(self)
2034         end
2035 end
2036
2037 redef class AVarargExpr
2038         redef fun accept_typing(v)
2039         do
2040                 # This kind of pseudo-expression can be only processed trough a signature
2041                 # See `check_signature`
2042                 # Other cases are a syntax error.
2043                 v.error(self, "Syntax Error: unexpected `...`.")
2044         end
2045 end
2046
2047 ###
2048
2049 redef class ADebugTypeExpr
2050         redef fun accept_typing(v)
2051         do
2052                 var expr = v.visit_expr(self.n_expr)
2053                 if expr == null then return
2054                 var unsafe = v.anchor_to(expr)
2055                 var ntype = self.n_type
2056                 var mtype = v.resolve_mtype(ntype)
2057                 if mtype != null and mtype != expr then
2058                         var umtype = v.anchor_to(mtype)
2059                         v.modelbuilder.warning(self, "debug", "Found type {expr} (-> {unsafe}), expected {mtype} (-> {umtype})")
2060                 end
2061                 self.is_typed = true
2062         end
2063 end