src/syntax/control_flow.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2008-2009 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 # Analysis control flow and variable visibility in property bodies, statements and expressions
  18 package control_flow
  19
  20 import syntax_base
  21
  22 # Associate symbols to variable
  23 # Can be nested
  24 abstract class ScopeContext
  25         # Look for the variable from its name
  26         # Return null if nothing found
  27         fun [](s: Symbol): nullable Variable
  28         do
  29                 if _dico.has_key(s) then
  30                         return _dico[s]
  31                 else
  32                         return null
  33                 end
  34         end
  35
  36         # Register a new variable with its name
  37         fun add(v: Variable)
  38         do
  39                 var old_var = self[v.name]
  40                 if old_var != null then
  41                         _visitor.error(v.decl, "Error: '{v}' already defined at {old_var.decl.location.relative_to(v.decl.location)}.")
  42                 end
  43                 _dico[v.name] = v
  44                 _all_variables.add(v)
  45         end
  46
  47         # Build a new ScopeContext
  48         fun sub(node: ANode): ScopeContext
  49         do
  50                 return new SubScopeContext.with_prev(self, node)
  51         end
  52
  53         # Variables by name (in the current context only)
  54         var _dico: Map[Symbol, Variable] = new HashMap[Symbol, Variable]
  55
  56         # All variables in all contextes
  57         var _all_variables: Set[Variable]
  58
  59         # The visitor of the context (used to display error)
  60         var _visitor: AbsSyntaxVisitor
  61
  62         # The syntax node that introduced the context
  63         readable var _node: ANode
  64
  65         init(visitor: AbsSyntaxVisitor, node: ANode)
  66         do
  67                 _visitor = visitor
  68                 _node = node
  69         end
  70 end
  71
  72 # Root of a variable scope context hierarchy
  73 class RootScopeContext
  74 special ScopeContext
  75         init(visitor: AbsSyntaxVisitor, node: ANode)
  76         do
  77                 super(visitor, node)
  78                 _all_variables = new HashSet[Variable]
  79         end
  80 end
  81
  82 # Contexts that can see local variables of a prevous context
  83 # Local variables added to this context are not shared with the previous context
  84 class SubScopeContext
  85 special ScopeContext
  86         readable var _prev: ScopeContext
  87
  88         redef fun [](s)
  89         do
  90                 if _dico.has_key(s) then
  91                         return _dico[s]
  92                 else
  93                         return prev[s]
  94                 end
  95         end
  96
  97         init with_prev(p: ScopeContext, node: ANode)
  98         do
  99                 init(p._visitor, node)
 100                 _prev = p
 101                 _all_variables = p._all_variables
 102         end
 103 end
 104
 105 #################################################################
 106
 107 # All-in-one context for flow control.
 108 # It features:
 109 # * reachability
 110 # * set/unset variable
 111 # * adaptive type of variable
 112 # FlowContextes are imutables, new contexts are created:
 113 # * as an empty root context
 114 # * as the adaptation of a existing context (see methods sub_*)
 115 # * as the merge of existing contexts
 116 abstract class FlowContext
 117         # Display an error localised on `n' if the variable `v' is not set
 118         fun check_is_set(n: ANode, v: Variable)
 119         do
 120                 if v.must_be_set and not is_set(v) then
 121                         _visitor.error(n, "Error: variable '{v}' is possibly unset.")
 122                 end
 123         end
 124
 125         # The effective static type of a given variable
 126         # May be different from the declaration static type
 127         fun stype(v: Variable): nullable MMType
 128         do
 129                 return v.stype
 130         end
 131
 132         # Return a context where the variable is marked as set
 133         fun sub_setvariable(v: Variable): FlowContext
 134         do
 135                 var ctx = new SubFlowContext.with_prev(self, node)
 136                 ctx._set_variables.add(v)
 137                 return ctx
 138         end
 139
 140         # Return a context where unreash == true
 141         fun sub_unreash(node: ANode): FlowContext
 142         do
 143                 var ctx = new SubFlowContext.with_prev(self, node)
 144                 ctx._unreash = true
 145                 return ctx
 146         end
 147
 148         # Return a context where v is casted as t
 149         fun sub_with(node: ANode, v: Variable, t: MMType): FlowContext
 150         do
 151                 return new CastFlowContext(self, node, v, t)
 152         end
 153
 154         # Merge various alternative contexts (all must be reashable)
 155         # Note that self can belong to alternatives
 156         # Base is self
 157         fun merge(node: ANode, alternatives: Array[FlowContext]): FlowContext
 158         do
 159                 for a in alternatives do assert not a.unreash
 160                 if alternatives.length == 1 then return alternatives.first
 161                 return new MergeFlowContext(self, node, alternatives)
 162         end
 163
 164         # Merge only context that are reachable
 165         # Used for if/then/else merges
 166         # Base is self
 167         fun merge_reash(node: ANode, alt1, alt2: FlowContext): FlowContext
 168         do
 169                 if alt1.unreash then
 170                         if alt2.unreash then
 171                                 return self.sub_unreash(node)
 172                         else
 173                                 var t = alt2
 174                                 alt2 = alt1
 175                                 alt1 = t
 176                         end
 177                 end
 178
 179                 if alt2.unreash or alt1 == alt2 then
 180                         return alt1
 181                         #if alt1 == self then
 182                         #       return self
 183                         #else
 184                         #       return merge(node, [alt1])
 185                         #end
 186                 else
 187                         return merge(node, [alt1, alt2])
 188                 end
 189         end
 190
 191         # The visitor of the context (used to display error)
 192         var _visitor: AbsSyntaxVisitor
 193
 194         # The syntax node that introduced the context
 195         readable var _node: ANode
 196
 197         init(visitor: AbsSyntaxVisitor, node: ANode)
 198         do
 199                 _visitor = visitor
 200                 _node = node
 201         end
 202
 203         # Is a control flow break met? (return, break, continue)
 204         readable var _unreash: Bool = false
 205
 206         # Is a control flow already broken?
 207         # Used to avoid repeating the same error message
 208         readable writable var _already_unreash: Bool = false
 209
 210         # Set of variable that are set (assigned)
 211         readable var _set_variables: HashSet[Variable] = new HashSet[Variable]
 212
 213         # Is a variable set?
 214         fun is_set(v: Variable): Bool
 215         do
 216                 return _set_variables.has(v)
 217         end
 218 end
 219
 220 # Root of a variable context hierarchy
 221 class RootFlowContext
 222 special FlowContext
 223         init(visitor: AbsSyntaxVisitor, node: ANode)
 224         do
 225                 super(visitor, node)
 226         end
 227 end
 228
 229 # Contexts that are an evolution of a single previous context
 230 class SubFlowContext
 231 special FlowContext
 232         readable var _prev: FlowContext
 233
 234         redef fun is_set(v)
 235         do
 236                 return _set_variables.has(v) or _prev.is_set(v)
 237         end
 238
 239         redef fun stype(v)
 240         do
 241                 return prev.stype(v)
 242         end
 243
 244         init with_prev(p: FlowContext, node: ANode)
 245         do
 246                 init(p._visitor, node)
 247                 _prev = p
 248         end
 249 end
 250
 251 # A variable context where a variable got a type adptation
 252 class CastFlowContext
 253 special SubFlowContext
 254         # The casted variable
 255         var _variable: Variable
 256
 257         # The new static type of the variable
 258         var _stype: nullable MMType
 259
 260         redef fun stype(v)
 261         do
 262                 if v == _variable then
 263                         return _stype
 264                 else
 265                         return prev.stype(v)
 266                 end
 267         end
 268
 269         init(p: FlowContext, node: ANode, v: Variable, s: nullable MMType)
 270         do
 271                 with_prev(p, node)
 272                 _variable = v
 273                 _stype = s
 274         end
 275 end
 276
 277 # Context that resulting from the combinaisons of other contexts.
 278 # Most of the merge computation are done lasily.
 279 class MergeFlowContext
 280 special FlowContext
 281         var _base: FlowContext
 282         var _alts: Array[FlowContext]
 283
 284         # Updated static type of variables
 285         var _stypes: Map[Variable, nullable MMType] = new HashMap[Variable, nullable MMType]
 286
 287         init(base: FlowContext, node: ANode, alts: Array[FlowContext])
 288         do
 289                 super(base._visitor, node)
 290                 _alts = alts
 291                 _base = base
 292         end
 293
 294         redef fun stype(v)
 295         do
 296                 if _stypes.has_key(v) then
 297                         return _stypes[v]
 298                 else
 299                         var s = merge_stype(v)
 300                         _stypes[v] = s
 301                         return s
 302                 end
 303         end
 304
 305         private fun merge_stype(v: Variable): nullable MMType
 306         do
 307                 var candidate: nullable MMType = null
 308                 var is_nullable = false
 309                 var same_candidate: nullable MMType = _alts.first.stype(v)
 310                 for ctx in _alts do
 311                         var t = ctx.stype(v)
 312                         if t == null then
 313                                 return null
 314                         end
 315                         if t != same_candidate then
 316                                 same_candidate = null
 317                         end
 318                         if t isa MMTypeNone then
 319                                 is_nullable = true
 320                                 continue
 321                         end
 322                         if t isa MMNullableType then
 323                                 is_nullable = true
 324                                 t = t.as_notnull
 325                         end
 326                         if candidate == null or candidate < t then
 327                                 candidate = t
 328                         end
 329                 end
 330                 if same_candidate != null then
 331                         return same_candidate
 332                 end
 333                 if is_nullable then
 334                         if candidate == null then
 335                                 return _visitor.type_none
 336                         else
 337                                 candidate = candidate.as_nullable
 338                         end
 339                 end
 340                 if candidate == null then
 341                         return _base.stype(v)
 342                 else
 343                         for ctx in _alts do
 344                                 var t = ctx.stype(v)
 345                                 if not t < candidate then
 346                                         return _base.stype(v)
 347                                 end
 348                         end
 349                 end
 350                 return candidate
 351         end
 352
 353         redef fun is_set(v)
 354         do
 355                 if _set_variables.has(v) then
 356                         return true
 357                 else
 358                         for ctx in _alts do
 359                                 if not ctx.is_set(v) then
 360                                         return false
 361                                 end
 362                         end
 363                         _set_variables.add(v)
 364                         return true
 365                 end
 366         end
 367 end
 368
 369
 370 redef class Variable
 371         # Is the variable must be set before being used ?
 372         fun must_be_set: Bool do return false
 373 end
 374
 375 redef class VarVariable
 376         redef fun must_be_set do return true
 377 end