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                 if _stypes.has_key(v) then
  64                         return _stypes[v]
  65                 else
  66                         return v.stype
  67                 end
  68         end
  69
  70         # Set effective static type of a given variable
  71         # May be different from the declaration static type
  72         fun stype=(v: Variable, t: nullable MMType)
  73         do
  74                 _stypes[v] = t
  75         end
  76
  77         # Variables by name (in the current context only)
  78         var _dico: Map[Symbol, Variable]
  79
  80         # All variables in all contextes
  81         var _all_variables: Set[Variable]
  82
  83         # Updated static type of variables
  84         var _stypes: Map[Variable, nullable MMType] = new HashMap[Variable, nullable MMType]
  85
  86         # Build a new VariableContext
  87         fun sub(node: ANode): SubVariableContext
  88         do
  89                 return new SubVariableContext.with_prev(self, node)
  90         end
  91
  92         # Build a nested VariableContext with new variable information
  93         fun sub_with(node: ANode, v: Variable, t: MMType): SubVariableContext
  94         do
  95                 var ctx = sub(node)
  96                 ctx.stype(v) = t
  97                 return ctx
  98         end
  99
 100         # The visitor of the context (used to display error)
 101         var _visitor: AbsSyntaxVisitor
 102
 103         # The syntax node that introduced the context
 104         readable var _node: ANode
 105
 106         init(visitor: AbsSyntaxVisitor, node: ANode)
 107         do
 108                 _visitor = visitor
 109                 _node = node
 110                 _dico = new HashMap[Symbol, Variable]
 111         end
 112
 113         # Is a control flow break met? (return, break, continue)
 114         readable writable var _unreash: Bool = false
 115
 116         # Is a control flow already broken?
 117         # Used to avoid repeating the same error message
 118         readable writable var _already_unreash: Bool = false
 119
 120         # Set of variable that are set (assigned)
 121         readable var _set_variables: HashSet[Variable] = new HashSet[Variable]
 122
 123         # Is a variable set?
 124         fun is_set(v: Variable): Bool
 125         do
 126                 return _set_variables.has(v)
 127         end
 128
 129         # Merge back one flow context information
 130         fun merge(ctx: VariableContext)
 131         do
 132                 if ctx.unreash then
 133                         unreash = true
 134                         if ctx.already_unreash then already_unreash = true
 135                         return
 136                 end
 137                 for v in _all_variables do
 138                         if not is_set(v) and ctx.is_set(v) then
 139                                 mark_is_set(v)
 140                         end
 141                         var s = stype(v)
 142                         var s1 = ctx.stype(v)
 143                         if s1 != s then stype(v) = s1
 144                 end
 145         end
 146
 147         # Merge back two alternative flow context informations
 148         fun merge2(ctx1, ctx2, basectx: VariableContext)
 149         do
 150                 if ctx1.unreash then
 151                         merge(ctx2)
 152                         return
 153                 else if ctx2.unreash then
 154                         merge(ctx1)
 155                         return
 156                 end
 157                 for v in _all_variables do
 158                         if not is_set(v) and ctx1.is_set(v) and ctx2.is_set(v) then
 159                                 mark_is_set(v)
 160                         end
 161
 162                         var s = stype(v)
 163                         var s1 = ctx1.stype(v)
 164                         var s2 = ctx2.stype(v)
 165                         if s1 == s and s2 == s then
 166                                 # NOP
 167                         else if s1 == null or s2 == null then
 168                                 stype(v) = null
 169                         else
 170                                 var sm = merge_types(s1, s2)
 171                                 if sm == null then
 172                                         stype(v) = basectx.stype(v)
 173                                 else
 174                                         stype(v) = sm
 175                                 end
 176                         end
 177                 end
 178         end
 179
 180         # Combine and get the most specific comon supertype
 181         # return null if no comon supertype is found
 182         private fun merge_types(t1, t2: MMType): nullable MMType
 183         do
 184                 if t1 == t2 then return t1
 185                 if t1 isa MMTypeNone then return t2.as_nullable
 186                 if t2 isa MMTypeNone then return t1.as_nullable
 187                 var is_nullable = false
 188                 if t1.is_nullable then
 189                         is_nullable = true
 190                         t1 = t1.as_notnull
 191                 end
 192                 if t2.is_nullable then
 193                         is_nullable = true
 194                         t2 = t2.as_notnull
 195                 end
 196                 var t: MMType
 197                 if t1 < t2 then
 198                         t = t2
 199                 else if t2 < t1 then
 200                         t = t1
 201                 else
 202                         return null
 203                 end
 204                 if is_nullable then t = t.as_nullable
 205                 return t
 206         end
 207
 208         redef fun to_s
 209         do
 210                 var s = new Buffer
 211                 s.append(node.location.to_s)
 212                 for v in _all_variables do
 213                         var t = stype(v)
 214                         if t == null then continue
 215                         s.append(" {v}:{t}")
 216                 end
 217                 return s.to_s
 218         end
 219 end
 220
 221 class RootVariableContext
 222 special VariableContext
 223         init(visitor: AbsSyntaxVisitor, node: ANode)
 224         do
 225                 super(visitor, node)
 226                 _all_variables = new HashSet[Variable]
 227         end
 228 end
 229
 230 class SubVariableContext
 231 special VariableContext
 232         readable var _prev: VariableContext
 233
 234         redef fun [](s)
 235         do
 236                 if _dico.has_key(s) then
 237                         return _dico[s]
 238                 else
 239                         return prev[s]
 240                 end
 241         end
 242
 243         redef fun stype(v)
 244         do
 245                 if _stypes.has_key(v) then
 246                         return _stypes[v]
 247                 else
 248                         return prev.stype(v)
 249                 end
 250         end
 251
 252         init with_prev(p: VariableContext, node: ANode)
 253         do
 254                 init(p._visitor, node)
 255                 _prev = p
 256                 _all_variables = p._all_variables
 257         end
 258
 259         redef fun is_set(v)
 260         do
 261                 return _set_variables.has(v) or _prev.is_set(v)
 262         end
 263 end
 264
 265 redef class Variable
 266         # Is the variable must be set before being used ?
 267         fun must_be_set: Bool do return false
 268 end
 269
 270 redef class VarVariable
 271         redef fun must_be_set do return true
 272 end