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 and variables to type
  23 # Can be nested
  24 abstract class VariableContext
  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         fun mark_is_set(v: Variable)
  48         do
  49                 _set_variables.add(v)
  50         end
  51
  52         fun check_is_set(n: ANode, v: Variable)
  53         do
  54                 if v.must_be_set and not is_set(v) then
  55                         _visitor.error(n, "Error: variable '{v}' is possibly unset.")
  56                 end
  57         end
  58
  59         # The effective static type of a given variable
  60         # May be different from the declaration static type
  61         fun stype(v: Variable): nullable MMType
  62         do
  63                 return v.stype
  64         end
  65
  66         # Variables by name (in the current context only)
  67         var _dico: Map[Symbol, Variable]
  68
  69         # All variables in all contextes
  70         var _all_variables: Set[Variable]
  71
  72         # Build a new VariableContext
  73         fun sub(node: ANode): VariableContext
  74         do
  75                 return new SubVariableContext.with_prev(self, node)
  76         end
  77
  78         # Build a nested VariableContext with new variable information
  79         fun sub_with(node: ANode, v: Variable, t: MMType): VariableContext
  80         do
  81                 return new CastVariableContext(self, node, v, t)
  82         end
  83
  84         # Merge various alternative contexts
  85         # Note that self can belong to alternatives
  86         fun merge(node: ANode, alternatives: Array[VariableContext], base: VariableContext): VariableContext
  87         do
  88                 return new MergeVariableContext(self, node, alternatives, base)
  89         end
  90
  91         # Merge only context that are reachable
  92         # Used for if/then/else merges
  93         # Base is self
  94         fun merge_reash(node: ANode, alt1, alt2: VariableContext, base: VariableContext): VariableContext
  95         do
  96                 if alt1.unreash then
  97                         if alt2.unreash then
  98                                 unreash = true
  99                                 return self
 100                         else
 101                                 var t = alt2
 102                                 alt2 = alt1
 103                                 alt1 = t
 104                         end
 105                 end
 106
 107                 if alt2.unreash or alt1 == alt2 then
 108                         if alt1 == self then
 109                                 return self
 110                         else
 111                                 return merge(node, [alt1], base)
 112                         end
 113                 else
 114                         return merge(node, [alt1, alt2], base)
 115                 end
 116         end
 117
 118         # The visitor of the context (used to display error)
 119         var _visitor: AbsSyntaxVisitor
 120
 121         # The syntax node that introduced the context
 122         readable var _node: ANode
 123
 124         init(visitor: AbsSyntaxVisitor, node: ANode)
 125         do
 126                 _visitor = visitor
 127                 _node = node
 128                 _dico = new HashMap[Symbol, Variable]
 129         end
 130
 131         # Is a control flow break met? (return, break, continue)
 132         readable writable var _unreash: Bool = false
 133
 134         # Is a control flow already broken?
 135         # Used to avoid repeating the same error message
 136         readable writable var _already_unreash: Bool = false
 137
 138         # Set of variable that are set (assigned)
 139         readable var _set_variables: HashSet[Variable] = new HashSet[Variable]
 140
 141         # Is a variable set?
 142         fun is_set(v: Variable): Bool
 143         do
 144                 return _set_variables.has(v)
 145         end
 146
 147         redef fun to_s
 148         do
 149                 var s = new Buffer
 150                 s.append(node.location.to_s)
 151                 for v in _all_variables do
 152                         var t = stype(v)
 153                         if t == null then continue
 154                         s.append(" {v}:{t}")
 155                 end
 156                 return s.to_s
 157         end
 158
 159         private fun is_in(ctx: VariableContext): Bool = self == ctx
 160 end
 161
 162 # Root of a variable context hierarchy
 163 class RootVariableContext
 164 special VariableContext
 165         init(visitor: AbsSyntaxVisitor, node: ANode)
 166         do
 167                 super(visitor, node)
 168                 _all_variables = new HashSet[Variable]
 169         end
 170 end
 171
 172 # Contexts that can see local variables of a prevous context
 173 # Local variables added to this context are not shared with the previous context
 174 class SubVariableContext
 175 special VariableContext
 176         readable var _prev: VariableContext
 177
 178         redef fun is_in(ctx)
 179         do
 180                 return ctx == self or _prev.is_in(ctx)
 181         end
 182
 183         redef fun [](s)
 184         do
 185                 if _dico.has_key(s) then
 186                         return _dico[s]
 187                 else
 188                         return prev[s]
 189                 end
 190         end
 191
 192         redef fun is_set(v)
 193         do
 194                 return _set_variables.has(v) or _prev.is_set(v)
 195         end
 196
 197         redef fun stype(v)
 198         do
 199                 return prev.stype(v)
 200         end
 201
 202         init with_prev(p: VariableContext, node: ANode)
 203         do
 204                 init(p._visitor, node)
 205                 _prev = p
 206                 _all_variables = p._all_variables
 207         end
 208 end
 209
 210 # A variable context where a variable got a type evolution
 211 class CastVariableContext
 212 special SubVariableContext
 213         # The casted variable
 214         var _variable: Variable
 215
 216         # The new static type of the variable
 217         var _stype: nullable MMType
 218
 219         redef fun stype(v)
 220         do
 221                 if v == _variable then
 222                         return _stype
 223                 else
 224                         return prev.stype(v)
 225                 end
 226         end
 227
 228         init(p: VariableContext, node: ANode, v: Variable, s: nullable MMType)
 229         do
 230                 with_prev(p, node)
 231                 _variable = v
 232                 _stype = s
 233         end
 234 end
 235
 236 # Context that follows a previous context but where
 237 # Variable current static type and variable is_set depends on the combinaison of other contexts
 238 class MergeVariableContext
 239 special SubVariableContext
 240         var _base: VariableContext
 241         var _alts: Array[VariableContext]
 242
 243         # Updated static type of variables
 244         var _stypes: Map[Variable, nullable MMType] = new HashMap[Variable, nullable MMType]
 245
 246         init(prev: VariableContext, node: ANode, alts: Array[VariableContext], base: VariableContext)
 247         do
 248                 assert prev.is_in(base) else print "{node.location}: Error: prev {prev.node.location} is not in base {base.node.location}"
 249                 for a in alts do assert a.is_in(prev) else print "{node.location}: Error: alternative {a.node.location} is not in prev {prev.node.location}"
 250                 with_prev(prev, node)
 251                 _alts = alts
 252                 _base = base
 253         end
 254
 255         redef fun stype(v)
 256         do
 257                 if _stypes.has_key(v) then
 258                         return _stypes[v]
 259                 else
 260                         var s = merge_stype(v)
 261                         _stypes[v] = s
 262                         return s
 263                 end
 264         end
 265
 266         private fun merge_stype(v: Variable): nullable MMType
 267         do
 268                 var candidate: nullable MMType = null
 269                 var is_nullable = false
 270                 var same_candidate: nullable MMType = _alts.first.stype(v)
 271                 for ctx in _alts do
 272                         var t = ctx.stype(v)
 273                         if t == null then
 274                                 return null
 275                         end
 276                         if t != same_candidate then
 277                                 same_candidate = null
 278                         end
 279                         if t isa MMTypeNone then
 280                                 is_nullable = true
 281                                 continue
 282                         end
 283                         if t isa MMNullableType then
 284                                 is_nullable = true
 285                                 t = t.as_notnull
 286                         end
 287                         if candidate == null or candidate < t then
 288                                 candidate = t
 289                         end
 290                 end
 291                 if same_candidate != null then
 292                         return same_candidate
 293                 end
 294                 if is_nullable then
 295                         if candidate == null then
 296                                 return _visitor.type_none
 297                         else
 298                                 candidate = candidate.as_nullable
 299                         end
 300                 end
 301                 if candidate == null then
 302                         return _base.stype(v)
 303                 else
 304                         for ctx in _alts do
 305                                 var t = ctx.stype(v)
 306                                 if not t < candidate then
 307                                         return _base.stype(v)
 308                                 end
 309                         end
 310                 end
 311                 return candidate
 312         end
 313
 314         redef fun is_set(v)
 315         do
 316                 if _set_variables.has(v) then
 317                         return true
 318                 else
 319                         for ctx in _alts do
 320                                 if not ctx.is_set(v) then
 321                                         print "{node.location}: is_set({v}) ? false : because not set in {ctx.node.location}"
 322                                         return false
 323                                 end
 324                         end
 325                         _set_variables.add(v)
 326                         return true
 327                 end
 328         end
 329 end
 330
 331
 332 redef class Variable
 333         # Is the variable must be set before being used ?
 334         fun must_be_set: Bool do return false
 335 end
 336
 337 redef class VarVariable
 338         redef fun must_be_set do return true
 339 end