src/syntax/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 flow
  19
  20 import syntax_base
  21
  22 #################################################################
  23
  24 # All-in-one context for flow control.
  25 # It features:
  26 # * reachability
  27 # * set/unset variable
  28 # * adaptive type of variable
  29 # FlowContextes are imutables, new contexts are created:
  30 # * as an empty root context
  31 # * as the adaptation of a existing context (see methods sub_*)
  32 # * as the merge of existing contexts
  33 abstract class FlowContext
  34         # Display an error localised on `n' if the variable `v' is not set
  35         fun check_is_set(n: ANode, v: Variable)
  36         do
  37                 if v.must_be_set and not is_set(v) then
  38                         _visitor.error(n, "Error: variable '{v}' is possibly unset.")
  39                 end
  40         end
  41
  42         # The effective static type of a given variable
  43         # May be different from the declaration static type
  44         fun stype(v: Variable): nullable MMType
  45         do
  46                 return v.stype
  47         end
  48
  49         # Return a context where the variable is marked as set
  50         fun sub_setvariable(v: Variable): FlowContext
  51         do
  52                 var ctx = new SubFlowContext.with_prev(self, node)
  53                 ctx._set_variables.add(v)
  54                 return ctx
  55         end
  56
  57         # Return a context where unreash == true
  58         fun sub_unreash(node: ANode): FlowContext
  59         do
  60                 var ctx = new SubFlowContext.with_prev(self, node)
  61                 ctx._unreash = true
  62                 return ctx
  63         end
  64
  65         # Return a context where v is casted as t
  66         fun sub_with(node: ANode, v: Variable, t: MMType): FlowContext
  67         do
  68                 return new CastFlowContext(self, node, v, t)
  69         end
  70
  71         # Merge various alternative contexts (all must be reashable)
  72         # Note that self can belong to alternatives
  73         # Base is self
  74         fun merge(node: ANode, alternatives: Array[FlowContext]): FlowContext
  75         do
  76                 for a in alternatives do assert not a.unreash
  77                 if alternatives.length == 1 then return alternatives.first
  78                 return new MergeFlowContext(self, node, alternatives)
  79         end
  80
  81         # Merge only context that are reachable
  82         # Used for if/then/else merges
  83         # Base is self
  84         fun merge_reash(node: ANode, alt1, alt2: FlowContext): FlowContext
  85         do
  86                 if alt1.unreash then
  87                         if alt2.unreash then
  88                                 return self.sub_unreash(node)
  89                         else
  90                                 var t = alt2
  91                                 alt2 = alt1
  92                                 alt1 = t
  93                         end
  94                 end
  95
  96                 if alt2.unreash or alt1 == alt2 then
  97                         return alt1
  98                         #if alt1 == self then
  99                         #       return self
 100                         #else
 101                         #       return merge(node, [alt1])
 102                         #end
 103                 else
 104                         return merge(node, [alt1, alt2])
 105                 end
 106         end
 107
 108         # The visitor of the context (used to display error)
 109         var _visitor: AbsSyntaxVisitor
 110
 111         # The syntax node that introduced the context
 112         readable var _node: ANode
 113
 114         init(visitor: AbsSyntaxVisitor, node: ANode)
 115         do
 116                 _visitor = visitor
 117                 _node = node
 118         end
 119
 120         # Is a control flow break met? (return, break, continue)
 121         readable var _unreash: Bool = false
 122
 123         # Is a control flow already broken?
 124         # Used to avoid repeating the same error message
 125         readable writable var _already_unreash: Bool = false
 126
 127         # Set of variable that are set (assigned)
 128         readable var _set_variables: HashSet[Variable] = new HashSet[Variable]
 129
 130         # Is a variable set?
 131         fun is_set(v: Variable): Bool
 132         do
 133                 return _set_variables.has(v)
 134         end
 135 end
 136
 137 # Root of a variable context hierarchy
 138 class RootFlowContext
 139         super FlowContext
 140         init(visitor: AbsSyntaxVisitor, node: ANode)
 141         do
 142                 super(visitor, node)
 143         end
 144 end
 145
 146 # Contexts that are an evolution of a single previous context
 147 class SubFlowContext
 148         super FlowContext
 149         readable var _prev: FlowContext
 150
 151         redef fun is_set(v)
 152         do
 153                 return _set_variables.has(v) or _prev.is_set(v)
 154         end
 155
 156         redef fun stype(v)
 157         do
 158                 return prev.stype(v)
 159         end
 160
 161         init with_prev(p: FlowContext, node: ANode)
 162         do
 163                 init(p._visitor, node)
 164                 _prev = p
 165         end
 166 end
 167
 168 # A variable context where a variable got a type adptation
 169 class CastFlowContext
 170         super SubFlowContext
 171         # The casted variable
 172         var _variable: Variable
 173
 174         # The new static type of the variable
 175         var _stype: nullable MMType
 176
 177         redef fun stype(v)
 178         do
 179                 if v == _variable then
 180                         return _stype
 181                 else
 182                         return prev.stype(v)
 183                 end
 184         end
 185
 186         init(p: FlowContext, node: ANode, v: Variable, s: nullable MMType)
 187         do
 188                 with_prev(p, node)
 189                 _variable = v
 190                 _stype = s
 191         end
 192 end
 193
 194 # Context that resulting from the combinaisons of other contexts.
 195 # Most of the merge computation are done lasily.
 196 class MergeFlowContext
 197         super FlowContext
 198         var _base: FlowContext
 199         var _alts: Array[FlowContext]
 200
 201         # Updated static type of variables
 202         var _stypes: Map[Variable, nullable MMType] = new HashMap[Variable, nullable MMType]
 203
 204         init(base: FlowContext, node: ANode, alts: Array[FlowContext])
 205         do
 206                 super(base._visitor, node)
 207                 _alts = alts
 208                 _base = base
 209         end
 210
 211         redef fun stype(v)
 212         do
 213                 if _stypes.has_key(v) then
 214                         return _stypes[v]
 215                 else
 216                         var s = merge_stype(v)
 217                         _stypes[v] = s
 218                         return s
 219                 end
 220         end
 221
 222         private fun merge_stype(v: Variable): nullable MMType
 223         do
 224                 var candidate: nullable MMType = null
 225                 var is_nullable = false
 226                 var same_candidate: nullable MMType = _alts.first.stype(v)
 227                 for ctx in _alts do
 228                         var t = ctx.stype(v)
 229                         if t == null then
 230                                 return null
 231                         end
 232                         if t != same_candidate then
 233                                 same_candidate = null
 234                         end
 235                         if t isa MMTypeNone then
 236                                 is_nullable = true
 237                                 continue
 238                         end
 239                         if t isa MMNullableType then
 240                                 is_nullable = true
 241                                 t = t.as_notnull
 242                         end
 243                         if candidate == null or candidate < t then
 244                                 candidate = t
 245                         end
 246                 end
 247                 if same_candidate != null then
 248                         return same_candidate
 249                 end
 250                 if is_nullable then
 251                         if candidate == null then
 252                                 return _visitor.type_none
 253                         else
 254                                 candidate = candidate.as_nullable
 255                         end
 256                 end
 257                 if candidate == null then
 258                         return _base.stype(v)
 259                 else
 260                         for ctx in _alts do
 261                                 var t = ctx.stype(v)
 262                                 if not t < candidate then
 263                                         return _base.stype(v)
 264                                 end
 265                         end
 266                 end
 267                 return candidate
 268         end
 269
 270         redef fun is_set(v)
 271         do
 272                 if _set_variables.has(v) then
 273                         return true
 274                 else
 275                         for ctx in _alts do
 276                                 if not ctx.is_set(v) then
 277                                         return false
 278                                 end
 279                         end
 280                         _set_variables.add(v)
 281                         return true
 282                 end
 283         end
 284 end
 285
 286
 287 redef class Variable
 288         # Is the variable must be set before being used ?
 289         fun must_be_set: Bool do return false
 290 end
 291
 292 redef class VarVariable
 293         redef fun must_be_set do return true
 294 end