# This file is part of NIT ( http://www.nitlanguage.org ).
#
-# Copyright 2008 Jean Privat <jean@pryen.org>
+# Copyright 2008-2009 Jean Privat <jean@pryen.org>
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# See the License for the specific language governing permissions and
# limitations under the License.
-# Analysis control flow in property bodies, statements and expressions
+# Analysis control flow and variable visibility in property bodies, statements and expressions
package control_flow
import syntax_base
-redef class MMSrcModule
- # Walk trough the module and type statments and expressions
- # Require than supermodules are processed
- meth do_control_flow(tc: ToolContext)
+# Associate symbols to variable
+# Can be nested
+abstract class ScopeContext
+ # Look for the variable from its name
+ # Return null if nothing found
+ fun [](s: Symbol): nullable Variable
do
- var tv = new ControlFlowVisitor(tc, self)
- tv.visit(node)
- end
-end
-
-redef class Variable
- # Is the variable must be set before being used ?
- meth must_be_set: Bool do return false
-end
-
-redef class VarVariable
- redef meth must_be_set do return true
-end
-
-
-
-# Control flow visitor
-# * Check reachability in methods
-# * Associate breaks and continues
-# * Check some other warning
-private class ControlFlowVisitor
-special AbsSyntaxVisitor
- redef meth visit(n)
- do
- if n != null then n.accept_control_flow(self)
+ if _dico.has_key(s) then
+ return _dico[s]
+ else
+ return null
+ end
end
- # Number of nested once
- readable writable attr _once_count: Int = 0
-
- # Current knowledge about variables types
- readable writable attr _control_flow_ctx: ControlFlowContext
-
- meth check_is_set(n: PNode, v: Variable)
+ # Register a new variable with its name
+ fun add(v: Variable)
do
- if v.must_be_set and not control_flow_ctx.is_set(v) then
- error(n, "Error: variable '{v}' is possibly unset.")
- var cfc = control_flow_ctx
- while cfc != null do
- print("cfc: " + cfc.set_variables.join(" "))
- cfc = cfc.prev
- end
+ var old_var = self[v.name]
+ if old_var != null then
+ _visitor.error(v.decl, "Error: '{v}' already defined at {old_var.decl.location.relative_to(v.decl.location)}.")
end
+ _dico[v.name] = v
+ _all_variables.add(v)
end
- meth mark_is_set(v: Variable)
+ # Build a new ScopeContext
+ fun sub(node: ANode): ScopeContext
do
- control_flow_ctx.set_variables.add(v)
+ return new SubScopeContext.with_prev(self, node)
end
- init(tc, m) do super
-end
-
-private class ControlFlowContext
- # Previous control flow context if any
- readable attr _prev: ControlFlowContext
-
- # Is a control flow break met? (return, break, continue)
- readable writable attr _unreash: Bool = false
-
- # Is a control flow already broken?
- # Used to avoid repeating the same error message
- readable writable attr _already_unreash: Bool = false
+ # Variables by name (in the current context only)
+ var _dico: Map[Symbol, Variable] = new HashMap[Symbol, Variable]
- # Set of variable that are set (assigned)
- readable attr _set_variables: HashSet[Variable] = new HashSet[Variable]
-
- # Is a variable set?
- meth is_set(v: Variable): Bool
- do
- return _set_variables.has(v) or (_prev != null and _prev.is_set(v))
- end
+ # All variables in all contextes
+ var _all_variables: Set[Variable]
- meth sub: ControlFlowContext
- do
- return new ControlFlowContext.with_prev(self)
- end
+ # The visitor of the context (used to display error)
+ var _visitor: AbsSyntaxVisitor
- init
- do
- end
+ # The syntax node that introduced the context
+ readable var _node: ANode
- init with_prev(p: ControlFlowContext)
+ init(visitor: AbsSyntaxVisitor, node: ANode)
do
- _prev = p
- _unreash = p.unreash
- _already_unreash = p.already_unreash
+ _visitor = visitor
+ _node = node
end
end
-###############################################################################
-
-redef class PNode
- private meth accept_control_flow(v: ControlFlowVisitor)
+# Root of a variable scope context hierarchy
+class RootScopeContext
+special ScopeContext
+ init(visitor: AbsSyntaxVisitor, node: ANode)
do
- accept_abs_syntax_visitor(v)
+ super(visitor, node)
+ _all_variables = new HashSet[Variable]
end
end
-redef class AMethPropdef
- redef meth accept_control_flow(v)
- do
- v.control_flow_ctx = new ControlFlowContext
- super
- end
-end
+# Contexts that can see local variables of a prevous context
+# Local variables added to this context are not shared with the previous context
+class SubScopeContext
+special ScopeContext
+ readable var _prev: ScopeContext
-redef class AConcreteMethPropdef
- redef meth accept_control_flow(v)
+ redef fun [](s)
do
- super
- if v.control_flow_ctx.unreash == false and method.signature.return_type != null then
- v.error(self, "Control error: Reached end of function (a 'return' with a value was expected).")
+ if _dico.has_key(s) then
+ return _dico[s]
+ else
+ return prev[s]
end
end
-end
-redef class AVardeclExpr
- redef meth accept_control_flow(v)
+ init with_prev(p: ScopeContext, node: ANode)
do
- super
- if n_expr != null then v.mark_is_set(variable)
+ init(p._visitor, node)
+ _prev = p
+ _all_variables = p._all_variables
end
end
-redef class ABlockExpr
- redef meth accept_control_flow(v)
+#################################################################
+
+# All-in-one context for flow control.
+# It features:
+# * reachability
+# * set/unset variable
+# * adaptive type of variable
+# FlowContextes are imutables, new contexts are created:
+# * as an empty root context
+# * as the adaptation of a existing context (see methods sub_*)
+# * as the merge of existing contexts
+abstract class FlowContext
+ # Display an error localised on `n' if the variable `v' is not set
+ fun check_is_set(n: ANode, v: Variable)
do
- for e in n_expr do
- if v.control_flow_ctx.unreash and not v.control_flow_ctx.already_unreash then
- v.control_flow_ctx.already_unreash = true
- v.warning(e, "Warning: unreachable statement.")
- end
- v.visit(e)
+ if v.must_be_set and not is_set(v) then
+ _visitor.error(n, "Error: variable '{v}' is possibly unset.")
end
end
-end
-redef class AReturnExpr
- redef meth accept_control_flow(v)
+ # The effective static type of a given variable
+ # May be different from the declaration static type
+ fun stype(v: Variable): nullable MMType
do
- super
- v.control_flow_ctx.unreash = true
+ return v.stype
end
-end
-redef class ABreakExpr
- redef meth accept_control_flow(v)
+ # Return a context where the variable is marked as set
+ fun sub_setvariable(v: Variable): FlowContext
do
- super
- v.control_flow_ctx.unreash = true
+ var ctx = new SubFlowContext.with_prev(self, node)
+ ctx._set_variables.add(v)
+ return ctx
end
-end
-redef class AContinueExpr
- redef meth accept_control_flow(v)
+
+ # Return a context where unreash == true
+ fun sub_unreash(node: ANode): FlowContext
do
- super
- v.control_flow_ctx.unreash = true
+ var ctx = new SubFlowContext.with_prev(self, node)
+ ctx._unreash = true
+ return ctx
end
-end
-redef class AAbortExpr
- redef meth accept_control_flow(v)
+ # Return a context where v is casted as t
+ fun sub_with(node: ANode, v: Variable, t: MMType): FlowContext
do
- super
- v.control_flow_ctx.unreash = true
+ return new CastFlowContext(self, node, v, t)
end
-end
-redef class AClosureCallExpr
- redef meth accept_control_flow(v)
+ # Merge various alternative contexts (all must be reashable)
+ # Note that self can belong to alternatives
+ # Base is self
+ fun merge(node: ANode, alternatives: Array[FlowContext]): FlowContext
do
- super
- if variable.closure.is_break then v.control_flow_ctx.unreash = true
+ for a in alternatives do assert not a.unreash
+ if alternatives.length == 1 then return alternatives.first
+ return new MergeFlowContext(self, node, alternatives)
end
-end
-redef class AIfExpr
- redef meth accept_control_flow(v)
+ # Merge only context that are reachable
+ # Used for if/then/else merges
+ # Base is self
+ fun merge_reash(node: ANode, alt1, alt2: FlowContext): FlowContext
do
- v.visit(n_expr)
-
- var old_control_flow_ctx = v.control_flow_ctx
- v.control_flow_ctx = v.control_flow_ctx.sub
-
- v.visit(n_then)
+ if alt1.unreash then
+ if alt2.unreash then
+ return self.sub_unreash(node)
+ else
+ var t = alt2
+ alt2 = alt1
+ alt1 = t
+ end
+ end
- if n_else == null then
- # Restore control flow ctx since the 'then" block is optional
- v.control_flow_ctx = old_control_flow_ctx
+ if alt2.unreash or alt1 == alt2 then
+ return alt1
+ #if alt1 == self then
+ # return self
+ #else
+ # return merge(node, [alt1])
+ #end
else
- # Remember what appens in the 'then'
- var then_control_flow_ctx = v.control_flow_ctx
- # Reset to execute the 'else'
- v.control_flow_ctx = old_control_flow_ctx.sub
+ return merge(node, [alt1, alt2])
+ end
+ end
- v.visit(n_else)
+ # The visitor of the context (used to display error)
+ var _visitor: AbsSyntaxVisitor
- # Merge then and else in the old control_flow
- old_control_flow_ctx.unreash = v.control_flow_ctx.unreash and then_control_flow_ctx.unreash
+ # The syntax node that introduced the context
+ readable var _node: ANode
- if v.control_flow_ctx.unreash then v.control_flow_ctx = then_control_flow_ctx
- if then_control_flow_ctx.unreash then then_control_flow_ctx = v.control_flow_ctx
- for variable in v.control_flow_ctx.set_variables do
- if then_control_flow_ctx.is_set(variable) then
- old_control_flow_ctx.set_variables.add(variable)
- end
- end
- v.control_flow_ctx = old_control_flow_ctx
- end
+ init(visitor: AbsSyntaxVisitor, node: ANode)
+ do
+ _visitor = visitor
+ _node = node
end
-end
-class AControlableBlock
-special PExpr
- redef meth accept_control_flow(v)
- do
- # Store old control flow values
- var old_control_flow_ctx = v.control_flow_ctx
- v.control_flow_ctx = v.control_flow_ctx.sub
+ # Is a control flow break met? (return, break, continue)
+ readable var _unreash: Bool = false
- super
+ # Is a control flow already broken?
+ # Used to avoid repeating the same error message
+ readable writable var _already_unreash: Bool = false
- # Check control flow if any
- check_control_flow(v)
+ # Set of variable that are set (assigned)
+ readable var _set_variables: HashSet[Variable] = new HashSet[Variable]
- # Restore control flow value since all controlable blocks are optionnal
- v.control_flow_ctx = old_control_flow_ctx
+ # Is a variable set?
+ fun is_set(v: Variable): Bool
+ do
+ return _set_variables.has(v)
end
-
- private meth check_control_flow(v: ControlFlowVisitor) do end
end
-redef class AWhileExpr
-special AControlableBlock
+# Root of a variable context hierarchy
+class RootFlowContext
+special FlowContext
+ init(visitor: AbsSyntaxVisitor, node: ANode)
+ do
+ super(visitor, node)
+ end
end
-redef class AForExpr
-special AControlableBlock
-end
+# Contexts that are an evolution of a single previous context
+class SubFlowContext
+special FlowContext
+ readable var _prev: FlowContext
-redef class AVarExpr
- redef meth accept_control_flow(v)
+ redef fun is_set(v)
do
- super
- v.check_is_set(self, variable)
+ return _set_variables.has(v) or _prev.is_set(v)
end
-end
-redef class AVarAssignExpr
- redef meth accept_control_flow(v)
+ redef fun stype(v)
do
- super
- v.mark_is_set(variable)
+ return prev.stype(v)
end
-end
-redef class AVarReassignExpr
- redef meth accept_control_flow(v)
+ init with_prev(p: FlowContext, node: ANode)
do
- super
- v.check_is_set(self, variable)
- v.mark_is_set(variable)
+ init(p._visitor, node)
+ _prev = p
end
end
-redef class AClosureDecl
- redef meth accept_control_flow(v)
- do
- if n_expr != null then
- var old_control_flow_ctx = v.control_flow_ctx
- v.control_flow_ctx = v.control_flow_ctx.sub
-
- super
+# A variable context where a variable got a type adptation
+class CastFlowContext
+special SubFlowContext
+ # The casted variable
+ var _variable: Variable
- if v.control_flow_ctx.unreash == false then
- if variable.closure.signature.return_type != null then
- v.error(self, "Control error: Reached end of bloc (a 'continue' with a value was expected).")
- else if variable.closure.is_break then
- v.error(self, "Control error: Reached end of break bloc (an 'abort' was expected).")
- end
- end
+ # The new static type of the variable
+ var _stype: nullable MMType
- v.control_flow_ctx = old_control_flow_ctx
+ redef fun stype(v)
+ do
+ if v == _variable then
+ return _stype
+ else
+ return prev.stype(v)
end
end
+
+ init(p: FlowContext, node: ANode, v: Variable, s: nullable MMType)
+ do
+ with_prev(p, node)
+ _variable = v
+ _stype = s
+ end
end
-redef class AClosureDef
-special AControlableBlock
- redef meth accept_control_flow(v)
+# Context that resulting from the combinaisons of other contexts.
+# Most of the merge computation are done lasily.
+class MergeFlowContext
+special FlowContext
+ var _base: FlowContext
+ var _alts: Array[FlowContext]
+
+ # Updated static type of variables
+ var _stypes: Map[Variable, nullable MMType] = new HashMap[Variable, nullable MMType]
+
+ init(base: FlowContext, node: ANode, alts: Array[FlowContext])
do
- for va in variables do v.mark_is_set(va)
- super
+ super(base._visitor, node)
+ _alts = alts
+ _base = base
end
- redef meth check_control_flow(v)
+ redef fun stype(v)
do
- if v.control_flow_ctx.unreash == false then
- if closure.signature.return_type != null then
- v.error(self, "Control error: Reached end of bloc (a 'continue' with a value was expected).")
- else if closure.is_break then
- v.error(self, "Control error: Reached end of break bloc (a 'break' was expected).")
+ if _stypes.has_key(v) then
+ return _stypes[v]
+ else
+ var s = merge_stype(v)
+ _stypes[v] = s
+ return s
+ end
+ end
+
+ private fun merge_stype(v: Variable): nullable MMType
+ do
+ var candidate: nullable MMType = null
+ var is_nullable = false
+ var same_candidate: nullable MMType = _alts.first.stype(v)
+ for ctx in _alts do
+ var t = ctx.stype(v)
+ if t == null then
+ return null
+ end
+ if t != same_candidate then
+ same_candidate = null
+ end
+ if t isa MMTypeNone then
+ is_nullable = true
+ continue
+ end
+ if t isa MMNullableType then
+ is_nullable = true
+ t = t.as_notnull
+ end
+ if candidate == null or candidate < t then
+ candidate = t
+ end
+ end
+ if same_candidate != null then
+ return same_candidate
+ end
+ if is_nullable then
+ if candidate == null then
+ return _visitor.type_none
+ else
+ candidate = candidate.as_nullable
+ end
+ end
+ if candidate == null then
+ return _base.stype(v)
+ else
+ for ctx in _alts do
+ var t = ctx.stype(v)
+ if not t < candidate then
+ return _base.stype(v)
+ end
end
end
+ return candidate
end
-end
-redef class AOnceExpr
- redef meth accept_control_flow(v)
+ redef fun is_set(v)
do
- if v.once_count > 0 then
- v.warning(self, "Useless once in a once expression.")
+ if _set_variables.has(v) then
+ return true
+ else
+ for ctx in _alts do
+ if not ctx.is_set(v) then
+ return false
+ end
+ end
+ _set_variables.add(v)
+ return true
end
- v.once_count = v.once_count + 1
+ end
+end
- super
- v.once_count = v.once_count - 1
- end
+redef class Variable
+ # Is the variable must be set before being used ?
+ fun must_be_set: Bool do return false
end
+redef class VarVariable
+ redef fun must_be_set do return true
+end