1314 lines
44 KiB
Python
1314 lines
44 KiB
Python
from __future__ import absolute_import
|
|
|
|
import cython
|
|
cython.declare(PyrexTypes=object, ExprNodes=object, Nodes=object,
|
|
Builtin=object, InternalError=object, error=object, warning=object,
|
|
py_object_type=object, unspecified_type=object,
|
|
object_expr=object, fake_rhs_expr=object, TypedExprNode=object)
|
|
|
|
from . import Builtin
|
|
from . import ExprNodes
|
|
from . import Nodes
|
|
from . import Options
|
|
from .PyrexTypes import py_object_type, unspecified_type
|
|
from . import PyrexTypes
|
|
|
|
from .Visitor import TreeVisitor, CythonTransform
|
|
from .Errors import error, warning, InternalError
|
|
from .Optimize import ConstantFolding
|
|
|
|
|
|
class TypedExprNode(ExprNodes.ExprNode):
|
|
# Used for declaring assignments of a specified type without a known entry.
|
|
def __init__(self, type, may_be_none=None, pos=None):
|
|
super(TypedExprNode, self).__init__(pos)
|
|
self.type = type
|
|
self._may_be_none = may_be_none
|
|
|
|
def may_be_none(self):
|
|
return self._may_be_none != False
|
|
|
|
object_expr = TypedExprNode(py_object_type, may_be_none=True)
|
|
# Fake rhs to silence "unused variable" warning
|
|
fake_rhs_expr = TypedExprNode(unspecified_type)
|
|
|
|
|
|
class ControlBlock(object):
|
|
"""Control flow graph node. Sequence of assignments and name references.
|
|
|
|
children set of children nodes
|
|
parents set of parent nodes
|
|
positions set of position markers
|
|
|
|
stats list of block statements
|
|
gen dict of assignments generated by this block
|
|
bounded set of entries that are definitely bounded in this block
|
|
|
|
Example:
|
|
|
|
a = 1
|
|
b = a + c # 'c' is already bounded or exception here
|
|
|
|
stats = [Assignment(a), NameReference(a), NameReference(c),
|
|
Assignment(b)]
|
|
gen = {Entry(a): Assignment(a), Entry(b): Assignment(b)}
|
|
bounded = set([Entry(a), Entry(c)])
|
|
|
|
"""
|
|
|
|
def __init__(self):
|
|
self.children = set()
|
|
self.parents = set()
|
|
self.positions = set()
|
|
|
|
self.stats = []
|
|
self.gen = {}
|
|
self.bounded = set()
|
|
|
|
self.i_input = 0
|
|
self.i_output = 0
|
|
self.i_gen = 0
|
|
self.i_kill = 0
|
|
self.i_state = 0
|
|
|
|
def empty(self):
|
|
return (not self.stats and not self.positions)
|
|
|
|
def detach(self):
|
|
"""Detach block from parents and children."""
|
|
for child in self.children:
|
|
child.parents.remove(self)
|
|
for parent in self.parents:
|
|
parent.children.remove(self)
|
|
self.parents.clear()
|
|
self.children.clear()
|
|
|
|
def add_child(self, block):
|
|
self.children.add(block)
|
|
block.parents.add(self)
|
|
|
|
|
|
class ExitBlock(ControlBlock):
|
|
"""Non-empty exit point block."""
|
|
|
|
def empty(self):
|
|
return False
|
|
|
|
|
|
class AssignmentList(object):
|
|
def __init__(self):
|
|
self.stats = []
|
|
|
|
|
|
class ControlFlow(object):
|
|
"""Control-flow graph.
|
|
|
|
entry_point ControlBlock entry point for this graph
|
|
exit_point ControlBlock normal exit point
|
|
block ControlBlock current block
|
|
blocks set children nodes
|
|
entries set tracked entries
|
|
loops list stack for loop descriptors
|
|
exceptions list stack for exception descriptors
|
|
"""
|
|
|
|
def __init__(self):
|
|
self.blocks = set()
|
|
self.entries = set()
|
|
self.loops = []
|
|
self.exceptions = []
|
|
|
|
self.entry_point = ControlBlock()
|
|
self.exit_point = ExitBlock()
|
|
self.blocks.add(self.exit_point)
|
|
self.block = self.entry_point
|
|
|
|
def newblock(self, parent=None):
|
|
"""Create floating block linked to `parent` if given.
|
|
|
|
NOTE: Block is NOT added to self.blocks
|
|
"""
|
|
block = ControlBlock()
|
|
self.blocks.add(block)
|
|
if parent:
|
|
parent.add_child(block)
|
|
return block
|
|
|
|
def nextblock(self, parent=None):
|
|
"""Create block children block linked to current or `parent` if given.
|
|
|
|
NOTE: Block is added to self.blocks
|
|
"""
|
|
block = ControlBlock()
|
|
self.blocks.add(block)
|
|
if parent:
|
|
parent.add_child(block)
|
|
elif self.block:
|
|
self.block.add_child(block)
|
|
self.block = block
|
|
return self.block
|
|
|
|
def is_tracked(self, entry):
|
|
if entry.is_anonymous:
|
|
return False
|
|
return (entry.is_local or entry.is_pyclass_attr or entry.is_arg or
|
|
entry.from_closure or entry.in_closure or
|
|
entry.error_on_uninitialized)
|
|
|
|
def is_statically_assigned(self, entry):
|
|
if (entry.is_local and entry.is_variable and
|
|
(entry.type.is_struct_or_union or
|
|
entry.type.is_complex or
|
|
entry.type.is_array or
|
|
entry.type.is_cpp_class)):
|
|
# stack allocated structured variable => never uninitialised
|
|
return True
|
|
return False
|
|
|
|
def mark_position(self, node):
|
|
"""Mark position, will be used to draw graph nodes."""
|
|
if self.block:
|
|
self.block.positions.add(node.pos[:2])
|
|
|
|
def mark_assignment(self, lhs, rhs, entry):
|
|
if self.block and self.is_tracked(entry):
|
|
assignment = NameAssignment(lhs, rhs, entry)
|
|
self.block.stats.append(assignment)
|
|
self.block.gen[entry] = assignment
|
|
self.entries.add(entry)
|
|
|
|
def mark_argument(self, lhs, rhs, entry):
|
|
if self.block and self.is_tracked(entry):
|
|
assignment = Argument(lhs, rhs, entry)
|
|
self.block.stats.append(assignment)
|
|
self.block.gen[entry] = assignment
|
|
self.entries.add(entry)
|
|
|
|
def mark_deletion(self, node, entry):
|
|
if self.block and self.is_tracked(entry):
|
|
assignment = NameDeletion(node, entry)
|
|
self.block.stats.append(assignment)
|
|
self.block.gen[entry] = Uninitialized
|
|
self.entries.add(entry)
|
|
|
|
def mark_reference(self, node, entry):
|
|
if self.block and self.is_tracked(entry):
|
|
self.block.stats.append(NameReference(node, entry))
|
|
## XXX: We don't track expression evaluation order so we can't use
|
|
## XXX: successful reference as initialization sign.
|
|
## # Local variable is definitely bound after this reference
|
|
## if not node.allow_null:
|
|
## self.block.bounded.add(entry)
|
|
self.entries.add(entry)
|
|
|
|
def normalize(self):
|
|
"""Delete unreachable and orphan blocks."""
|
|
queue = set([self.entry_point])
|
|
visited = set()
|
|
while queue:
|
|
root = queue.pop()
|
|
visited.add(root)
|
|
for child in root.children:
|
|
if child not in visited:
|
|
queue.add(child)
|
|
unreachable = self.blocks - visited
|
|
for block in unreachable:
|
|
block.detach()
|
|
visited.remove(self.entry_point)
|
|
for block in visited:
|
|
if block.empty():
|
|
for parent in block.parents: # Re-parent
|
|
for child in block.children:
|
|
parent.add_child(child)
|
|
block.detach()
|
|
unreachable.add(block)
|
|
self.blocks -= unreachable
|
|
|
|
def initialize(self):
|
|
"""Set initial state, map assignments to bits."""
|
|
self.assmts = {}
|
|
|
|
bit = 1
|
|
for entry in self.entries:
|
|
assmts = AssignmentList()
|
|
assmts.mask = assmts.bit = bit
|
|
self.assmts[entry] = assmts
|
|
bit <<= 1
|
|
|
|
for block in self.blocks:
|
|
for stat in block.stats:
|
|
if isinstance(stat, NameAssignment):
|
|
stat.bit = bit
|
|
assmts = self.assmts[stat.entry]
|
|
assmts.stats.append(stat)
|
|
assmts.mask |= bit
|
|
bit <<= 1
|
|
|
|
for block in self.blocks:
|
|
for entry, stat in block.gen.items():
|
|
assmts = self.assmts[entry]
|
|
if stat is Uninitialized:
|
|
block.i_gen |= assmts.bit
|
|
else:
|
|
block.i_gen |= stat.bit
|
|
block.i_kill |= assmts.mask
|
|
block.i_output = block.i_gen
|
|
for entry in block.bounded:
|
|
block.i_kill |= self.assmts[entry].bit
|
|
|
|
for assmts in self.assmts.values():
|
|
self.entry_point.i_gen |= assmts.bit
|
|
self.entry_point.i_output = self.entry_point.i_gen
|
|
|
|
def map_one(self, istate, entry):
|
|
ret = set()
|
|
assmts = self.assmts[entry]
|
|
if istate & assmts.bit:
|
|
if self.is_statically_assigned(entry):
|
|
ret.add(StaticAssignment(entry))
|
|
elif entry.from_closure:
|
|
ret.add(Unknown)
|
|
else:
|
|
ret.add(Uninitialized)
|
|
for assmt in assmts.stats:
|
|
if istate & assmt.bit:
|
|
ret.add(assmt)
|
|
return ret
|
|
|
|
def reaching_definitions(self):
|
|
"""Per-block reaching definitions analysis."""
|
|
dirty = True
|
|
while dirty:
|
|
dirty = False
|
|
for block in self.blocks:
|
|
i_input = 0
|
|
for parent in block.parents:
|
|
i_input |= parent.i_output
|
|
i_output = (i_input & ~block.i_kill) | block.i_gen
|
|
if i_output != block.i_output:
|
|
dirty = True
|
|
block.i_input = i_input
|
|
block.i_output = i_output
|
|
|
|
|
|
class LoopDescr(object):
|
|
def __init__(self, next_block, loop_block):
|
|
self.next_block = next_block
|
|
self.loop_block = loop_block
|
|
self.exceptions = []
|
|
|
|
|
|
class ExceptionDescr(object):
|
|
"""Exception handling helper.
|
|
|
|
entry_point ControlBlock Exception handling entry point
|
|
finally_enter ControlBlock Normal finally clause entry point
|
|
finally_exit ControlBlock Normal finally clause exit point
|
|
"""
|
|
|
|
def __init__(self, entry_point, finally_enter=None, finally_exit=None):
|
|
self.entry_point = entry_point
|
|
self.finally_enter = finally_enter
|
|
self.finally_exit = finally_exit
|
|
|
|
|
|
class NameAssignment(object):
|
|
def __init__(self, lhs, rhs, entry):
|
|
if lhs.cf_state is None:
|
|
lhs.cf_state = set()
|
|
self.lhs = lhs
|
|
self.rhs = rhs
|
|
self.entry = entry
|
|
self.pos = lhs.pos
|
|
self.refs = set()
|
|
self.is_arg = False
|
|
self.is_deletion = False
|
|
self.inferred_type = None
|
|
|
|
def __repr__(self):
|
|
return '%s(entry=%r)' % (self.__class__.__name__, self.entry)
|
|
|
|
def infer_type(self):
|
|
self.inferred_type = self.rhs.infer_type(self.entry.scope)
|
|
return self.inferred_type
|
|
|
|
def type_dependencies(self):
|
|
return self.rhs.type_dependencies(self.entry.scope)
|
|
|
|
@property
|
|
def type(self):
|
|
if not self.entry.type.is_unspecified:
|
|
return self.entry.type
|
|
return self.inferred_type
|
|
|
|
|
|
class StaticAssignment(NameAssignment):
|
|
"""Initialised at declaration time, e.g. stack allocation."""
|
|
def __init__(self, entry):
|
|
if not entry.type.is_pyobject:
|
|
may_be_none = False
|
|
else:
|
|
may_be_none = None # unknown
|
|
lhs = TypedExprNode(
|
|
entry.type, may_be_none=may_be_none, pos=entry.pos)
|
|
super(StaticAssignment, self).__init__(lhs, lhs, entry)
|
|
|
|
def infer_type(self):
|
|
return self.entry.type
|
|
|
|
def type_dependencies(self):
|
|
return ()
|
|
|
|
|
|
class Argument(NameAssignment):
|
|
def __init__(self, lhs, rhs, entry):
|
|
NameAssignment.__init__(self, lhs, rhs, entry)
|
|
self.is_arg = True
|
|
|
|
|
|
class NameDeletion(NameAssignment):
|
|
def __init__(self, lhs, entry):
|
|
NameAssignment.__init__(self, lhs, lhs, entry)
|
|
self.is_deletion = True
|
|
|
|
def infer_type(self):
|
|
inferred_type = self.rhs.infer_type(self.entry.scope)
|
|
if (not inferred_type.is_pyobject and
|
|
inferred_type.can_coerce_to_pyobject(self.entry.scope)):
|
|
return py_object_type
|
|
self.inferred_type = inferred_type
|
|
return inferred_type
|
|
|
|
|
|
class Uninitialized(object):
|
|
"""Definitely not initialised yet."""
|
|
|
|
|
|
class Unknown(object):
|
|
"""Coming from outer closure, might be initialised or not."""
|
|
|
|
|
|
class NameReference(object):
|
|
def __init__(self, node, entry):
|
|
if node.cf_state is None:
|
|
node.cf_state = set()
|
|
self.node = node
|
|
self.entry = entry
|
|
self.pos = node.pos
|
|
|
|
def __repr__(self):
|
|
return '%s(entry=%r)' % (self.__class__.__name__, self.entry)
|
|
|
|
|
|
class ControlFlowState(list):
|
|
# Keeps track of Node's entry assignments
|
|
#
|
|
# cf_is_null [boolean] It is uninitialized
|
|
# cf_maybe_null [boolean] May be uninitialized
|
|
# is_single [boolean] Has only one assignment at this point
|
|
|
|
cf_maybe_null = False
|
|
cf_is_null = False
|
|
is_single = False
|
|
|
|
def __init__(self, state):
|
|
if Uninitialized in state:
|
|
state.discard(Uninitialized)
|
|
self.cf_maybe_null = True
|
|
if not state:
|
|
self.cf_is_null = True
|
|
elif Unknown in state:
|
|
state.discard(Unknown)
|
|
self.cf_maybe_null = True
|
|
else:
|
|
if len(state) == 1:
|
|
self.is_single = True
|
|
# XXX: Remove fake_rhs_expr
|
|
super(ControlFlowState, self).__init__(
|
|
[i for i in state if i.rhs is not fake_rhs_expr])
|
|
|
|
def one(self):
|
|
return self[0]
|
|
|
|
|
|
class GVContext(object):
|
|
"""Graphviz subgraph object."""
|
|
|
|
def __init__(self):
|
|
self.blockids = {}
|
|
self.nextid = 0
|
|
self.children = []
|
|
self.sources = {}
|
|
|
|
def add(self, child):
|
|
self.children.append(child)
|
|
|
|
def nodeid(self, block):
|
|
if block not in self.blockids:
|
|
self.blockids[block] = 'block%d' % self.nextid
|
|
self.nextid += 1
|
|
return self.blockids[block]
|
|
|
|
def extract_sources(self, block):
|
|
if not block.positions:
|
|
return ''
|
|
start = min(block.positions)
|
|
stop = max(block.positions)
|
|
srcdescr = start[0]
|
|
if not srcdescr in self.sources:
|
|
self.sources[srcdescr] = list(srcdescr.get_lines())
|
|
lines = self.sources[srcdescr]
|
|
return '\\n'.join([l.strip() for l in lines[start[1] - 1:stop[1]]])
|
|
|
|
def render(self, fp, name, annotate_defs=False):
|
|
"""Render graphviz dot graph"""
|
|
fp.write('digraph %s {\n' % name)
|
|
fp.write(' node [shape=box];\n')
|
|
for child in self.children:
|
|
child.render(fp, self, annotate_defs)
|
|
fp.write('}\n')
|
|
|
|
def escape(self, text):
|
|
return text.replace('"', '\\"').replace('\n', '\\n')
|
|
|
|
|
|
class GV(object):
|
|
"""Graphviz DOT renderer."""
|
|
|
|
def __init__(self, name, flow):
|
|
self.name = name
|
|
self.flow = flow
|
|
|
|
def render(self, fp, ctx, annotate_defs=False):
|
|
fp.write(' subgraph %s {\n' % self.name)
|
|
for block in self.flow.blocks:
|
|
label = ctx.extract_sources(block)
|
|
if annotate_defs:
|
|
for stat in block.stats:
|
|
if isinstance(stat, NameAssignment):
|
|
label += '\n %s [%s %s]' % (
|
|
stat.entry.name, 'deletion' if stat.is_deletion else 'definition', stat.pos[1])
|
|
elif isinstance(stat, NameReference):
|
|
if stat.entry:
|
|
label += '\n %s [reference %s]' % (stat.entry.name, stat.pos[1])
|
|
if not label:
|
|
label = 'empty'
|
|
pid = ctx.nodeid(block)
|
|
fp.write(' %s [label="%s"];\n' % (pid, ctx.escape(label)))
|
|
for block in self.flow.blocks:
|
|
pid = ctx.nodeid(block)
|
|
for child in block.children:
|
|
fp.write(' %s -> %s;\n' % (pid, ctx.nodeid(child)))
|
|
fp.write(' }\n')
|
|
|
|
|
|
class MessageCollection(object):
|
|
"""Collect error/warnings messages first then sort"""
|
|
def __init__(self):
|
|
self.messages = set()
|
|
|
|
def error(self, pos, message):
|
|
self.messages.add((pos, True, message))
|
|
|
|
def warning(self, pos, message):
|
|
self.messages.add((pos, False, message))
|
|
|
|
def report(self):
|
|
for pos, is_error, message in sorted(self.messages):
|
|
if is_error:
|
|
error(pos, message)
|
|
else:
|
|
warning(pos, message, 2)
|
|
|
|
|
|
def check_definitions(flow, compiler_directives):
|
|
flow.initialize()
|
|
flow.reaching_definitions()
|
|
|
|
# Track down state
|
|
assignments = set()
|
|
# Node to entry map
|
|
references = {}
|
|
assmt_nodes = set()
|
|
|
|
for block in flow.blocks:
|
|
i_state = block.i_input
|
|
for stat in block.stats:
|
|
i_assmts = flow.assmts[stat.entry]
|
|
state = flow.map_one(i_state, stat.entry)
|
|
if isinstance(stat, NameAssignment):
|
|
stat.lhs.cf_state.update(state)
|
|
assmt_nodes.add(stat.lhs)
|
|
i_state = i_state & ~i_assmts.mask
|
|
if stat.is_deletion:
|
|
i_state |= i_assmts.bit
|
|
else:
|
|
i_state |= stat.bit
|
|
assignments.add(stat)
|
|
if stat.rhs is not fake_rhs_expr:
|
|
stat.entry.cf_assignments.append(stat)
|
|
elif isinstance(stat, NameReference):
|
|
references[stat.node] = stat.entry
|
|
stat.entry.cf_references.append(stat)
|
|
stat.node.cf_state.update(state)
|
|
## if not stat.node.allow_null:
|
|
## i_state &= ~i_assmts.bit
|
|
## # after successful read, the state is known to be initialised
|
|
state.discard(Uninitialized)
|
|
state.discard(Unknown)
|
|
for assmt in state:
|
|
assmt.refs.add(stat)
|
|
|
|
# Check variable usage
|
|
warn_maybe_uninitialized = compiler_directives['warn.maybe_uninitialized']
|
|
warn_unused_result = compiler_directives['warn.unused_result']
|
|
warn_unused = compiler_directives['warn.unused']
|
|
warn_unused_arg = compiler_directives['warn.unused_arg']
|
|
|
|
messages = MessageCollection()
|
|
|
|
# assignment hints
|
|
for node in assmt_nodes:
|
|
if Uninitialized in node.cf_state:
|
|
node.cf_maybe_null = True
|
|
if len(node.cf_state) == 1:
|
|
node.cf_is_null = True
|
|
else:
|
|
node.cf_is_null = False
|
|
elif Unknown in node.cf_state:
|
|
node.cf_maybe_null = True
|
|
else:
|
|
node.cf_is_null = False
|
|
node.cf_maybe_null = False
|
|
|
|
# Find uninitialized references and cf-hints
|
|
for node, entry in references.items():
|
|
if Uninitialized in node.cf_state:
|
|
node.cf_maybe_null = True
|
|
if not entry.from_closure and len(node.cf_state) == 1:
|
|
node.cf_is_null = True
|
|
if (node.allow_null or entry.from_closure
|
|
or entry.is_pyclass_attr or entry.type.is_error):
|
|
pass # Can be uninitialized here
|
|
elif node.cf_is_null:
|
|
if entry.error_on_uninitialized or (
|
|
Options.error_on_uninitialized and (
|
|
entry.type.is_pyobject or entry.type.is_unspecified)):
|
|
messages.error(
|
|
node.pos,
|
|
"local variable '%s' referenced before assignment"
|
|
% entry.name)
|
|
else:
|
|
messages.warning(
|
|
node.pos,
|
|
"local variable '%s' referenced before assignment"
|
|
% entry.name)
|
|
elif warn_maybe_uninitialized:
|
|
messages.warning(
|
|
node.pos,
|
|
"local variable '%s' might be referenced before assignment"
|
|
% entry.name)
|
|
elif Unknown in node.cf_state:
|
|
# TODO: better cross-closure analysis to know when inner functions
|
|
# are being called before a variable is being set, and when
|
|
# a variable is known to be set before even defining the
|
|
# inner function, etc.
|
|
node.cf_maybe_null = True
|
|
else:
|
|
node.cf_is_null = False
|
|
node.cf_maybe_null = False
|
|
|
|
# Unused result
|
|
for assmt in assignments:
|
|
if (not assmt.refs and not assmt.entry.is_pyclass_attr
|
|
and not assmt.entry.in_closure):
|
|
if assmt.entry.cf_references and warn_unused_result:
|
|
if assmt.is_arg:
|
|
messages.warning(assmt.pos, "Unused argument value '%s'" %
|
|
assmt.entry.name)
|
|
else:
|
|
messages.warning(assmt.pos, "Unused result in '%s'" %
|
|
assmt.entry.name)
|
|
assmt.lhs.cf_used = False
|
|
|
|
# Unused entries
|
|
for entry in flow.entries:
|
|
if (not entry.cf_references
|
|
and not entry.is_pyclass_attr):
|
|
if entry.name != '_' and not entry.name.startswith('unused'):
|
|
# '_' is often used for unused variables, e.g. in loops
|
|
if entry.is_arg:
|
|
if warn_unused_arg:
|
|
messages.warning(entry.pos, "Unused argument '%s'" %
|
|
entry.name)
|
|
else:
|
|
if warn_unused:
|
|
messages.warning(entry.pos, "Unused entry '%s'" %
|
|
entry.name)
|
|
entry.cf_used = False
|
|
|
|
messages.report()
|
|
|
|
for node in assmt_nodes:
|
|
node.cf_state = ControlFlowState(node.cf_state)
|
|
for node in references:
|
|
node.cf_state = ControlFlowState(node.cf_state)
|
|
|
|
|
|
class AssignmentCollector(TreeVisitor):
|
|
def __init__(self):
|
|
super(AssignmentCollector, self).__init__()
|
|
self.assignments = []
|
|
|
|
def visit_Node(self):
|
|
self._visitchildren(self, None)
|
|
|
|
def visit_SingleAssignmentNode(self, node):
|
|
self.assignments.append((node.lhs, node.rhs))
|
|
|
|
def visit_CascadedAssignmentNode(self, node):
|
|
for lhs in node.lhs_list:
|
|
self.assignments.append((lhs, node.rhs))
|
|
|
|
|
|
class ControlFlowAnalysis(CythonTransform):
|
|
|
|
def visit_ModuleNode(self, node):
|
|
self.gv_ctx = GVContext()
|
|
self.constant_folder = ConstantFolding()
|
|
|
|
# Set of NameNode reductions
|
|
self.reductions = set()
|
|
|
|
self.in_inplace_assignment = False
|
|
self.env_stack = []
|
|
self.env = node.scope
|
|
self.stack = []
|
|
self.flow = ControlFlow()
|
|
self.visitchildren(node)
|
|
|
|
check_definitions(self.flow, self.current_directives)
|
|
|
|
dot_output = self.current_directives['control_flow.dot_output']
|
|
if dot_output:
|
|
annotate_defs = self.current_directives['control_flow.dot_annotate_defs']
|
|
fp = open(dot_output, 'wt')
|
|
try:
|
|
self.gv_ctx.render(fp, 'module', annotate_defs=annotate_defs)
|
|
finally:
|
|
fp.close()
|
|
return node
|
|
|
|
def visit_FuncDefNode(self, node):
|
|
for arg in node.args:
|
|
if arg.default:
|
|
self.visitchildren(arg)
|
|
self.visitchildren(node, ('decorators',))
|
|
self.env_stack.append(self.env)
|
|
self.env = node.local_scope
|
|
self.stack.append(self.flow)
|
|
self.flow = ControlFlow()
|
|
|
|
# Collect all entries
|
|
for entry in node.local_scope.entries.values():
|
|
if self.flow.is_tracked(entry):
|
|
self.flow.entries.add(entry)
|
|
|
|
self.mark_position(node)
|
|
# Function body block
|
|
self.flow.nextblock()
|
|
|
|
for arg in node.args:
|
|
self._visit(arg)
|
|
if node.star_arg:
|
|
self.flow.mark_argument(node.star_arg,
|
|
TypedExprNode(Builtin.tuple_type,
|
|
may_be_none=False),
|
|
node.star_arg.entry)
|
|
if node.starstar_arg:
|
|
self.flow.mark_argument(node.starstar_arg,
|
|
TypedExprNode(Builtin.dict_type,
|
|
may_be_none=False),
|
|
node.starstar_arg.entry)
|
|
self._visit(node.body)
|
|
# Workaround for generators
|
|
if node.is_generator:
|
|
self._visit(node.gbody.body)
|
|
|
|
# Exit point
|
|
if self.flow.block:
|
|
self.flow.block.add_child(self.flow.exit_point)
|
|
|
|
# Cleanup graph
|
|
self.flow.normalize()
|
|
check_definitions(self.flow, self.current_directives)
|
|
self.flow.blocks.add(self.flow.entry_point)
|
|
|
|
self.gv_ctx.add(GV(node.local_scope.name, self.flow))
|
|
|
|
self.flow = self.stack.pop()
|
|
self.env = self.env_stack.pop()
|
|
return node
|
|
|
|
def visit_DefNode(self, node):
|
|
node.used = True
|
|
return self.visit_FuncDefNode(node)
|
|
|
|
def visit_GeneratorBodyDefNode(self, node):
|
|
return node
|
|
|
|
def visit_CTypeDefNode(self, node):
|
|
return node
|
|
|
|
def mark_assignment(self, lhs, rhs=None):
|
|
if not self.flow.block:
|
|
return
|
|
if self.flow.exceptions:
|
|
exc_descr = self.flow.exceptions[-1]
|
|
self.flow.block.add_child(exc_descr.entry_point)
|
|
self.flow.nextblock()
|
|
|
|
if not rhs:
|
|
rhs = object_expr
|
|
if lhs.is_name:
|
|
if lhs.entry is not None:
|
|
entry = lhs.entry
|
|
else:
|
|
entry = self.env.lookup(lhs.name)
|
|
if entry is None: # TODO: This shouldn't happen...
|
|
return
|
|
self.flow.mark_assignment(lhs, rhs, entry)
|
|
elif lhs.is_sequence_constructor:
|
|
for i, arg in enumerate(lhs.args):
|
|
if not rhs or arg.is_starred:
|
|
item_node = None
|
|
else:
|
|
item_node = rhs.inferable_item_node(i)
|
|
self.mark_assignment(arg, item_node)
|
|
else:
|
|
self._visit(lhs)
|
|
|
|
if self.flow.exceptions:
|
|
exc_descr = self.flow.exceptions[-1]
|
|
self.flow.block.add_child(exc_descr.entry_point)
|
|
self.flow.nextblock()
|
|
|
|
def mark_position(self, node):
|
|
"""Mark position if DOT output is enabled."""
|
|
if self.current_directives['control_flow.dot_output']:
|
|
self.flow.mark_position(node)
|
|
|
|
def visit_FromImportStatNode(self, node):
|
|
for name, target in node.items:
|
|
if name != "*":
|
|
self.mark_assignment(target)
|
|
self.visitchildren(node)
|
|
return node
|
|
|
|
def visit_AssignmentNode(self, node):
|
|
raise InternalError("Unhandled assignment node")
|
|
|
|
def visit_SingleAssignmentNode(self, node):
|
|
self._visit(node.rhs)
|
|
self.mark_assignment(node.lhs, node.rhs)
|
|
return node
|
|
|
|
def visit_CascadedAssignmentNode(self, node):
|
|
self._visit(node.rhs)
|
|
for lhs in node.lhs_list:
|
|
self.mark_assignment(lhs, node.rhs)
|
|
return node
|
|
|
|
def visit_ParallelAssignmentNode(self, node):
|
|
collector = AssignmentCollector()
|
|
collector.visitchildren(node)
|
|
for lhs, rhs in collector.assignments:
|
|
self._visit(rhs)
|
|
for lhs, rhs in collector.assignments:
|
|
self.mark_assignment(lhs, rhs)
|
|
return node
|
|
|
|
def visit_InPlaceAssignmentNode(self, node):
|
|
self.in_inplace_assignment = True
|
|
self.visitchildren(node)
|
|
self.in_inplace_assignment = False
|
|
self.mark_assignment(node.lhs, self.constant_folder(node.create_binop_node()))
|
|
return node
|
|
|
|
def visit_DelStatNode(self, node):
|
|
for arg in node.args:
|
|
if arg.is_name:
|
|
entry = arg.entry or self.env.lookup(arg.name)
|
|
if entry.in_closure or entry.from_closure:
|
|
error(arg.pos,
|
|
"can not delete variable '%s' "
|
|
"referenced in nested scope" % entry.name)
|
|
if not node.ignore_nonexisting:
|
|
self._visit(arg) # mark reference
|
|
self.flow.mark_deletion(arg, entry)
|
|
else:
|
|
self._visit(arg)
|
|
return node
|
|
|
|
def visit_CArgDeclNode(self, node):
|
|
entry = self.env.lookup(node.name)
|
|
if entry:
|
|
may_be_none = not node.not_none
|
|
self.flow.mark_argument(
|
|
node, TypedExprNode(entry.type, may_be_none), entry)
|
|
return node
|
|
|
|
def visit_NameNode(self, node):
|
|
if self.flow.block:
|
|
entry = node.entry or self.env.lookup(node.name)
|
|
if entry:
|
|
self.flow.mark_reference(node, entry)
|
|
|
|
if entry in self.reductions and not self.in_inplace_assignment:
|
|
error(node.pos,
|
|
"Cannot read reduction variable in loop body")
|
|
|
|
return node
|
|
|
|
def visit_StatListNode(self, node):
|
|
if self.flow.block:
|
|
for stat in node.stats:
|
|
self._visit(stat)
|
|
if not self.flow.block:
|
|
stat.is_terminator = True
|
|
break
|
|
return node
|
|
|
|
def visit_Node(self, node):
|
|
self.visitchildren(node)
|
|
self.mark_position(node)
|
|
return node
|
|
|
|
def visit_IfStatNode(self, node):
|
|
next_block = self.flow.newblock()
|
|
parent = self.flow.block
|
|
# If clauses
|
|
for clause in node.if_clauses:
|
|
parent = self.flow.nextblock(parent)
|
|
self._visit(clause.condition)
|
|
self.flow.nextblock()
|
|
self._visit(clause.body)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
# Else clause
|
|
if node.else_clause:
|
|
self.flow.nextblock(parent=parent)
|
|
self._visit(node.else_clause)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
else:
|
|
parent.add_child(next_block)
|
|
|
|
if next_block.parents:
|
|
self.flow.block = next_block
|
|
else:
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_WhileStatNode(self, node):
|
|
condition_block = self.flow.nextblock()
|
|
next_block = self.flow.newblock()
|
|
# Condition block
|
|
self.flow.loops.append(LoopDescr(next_block, condition_block))
|
|
if node.condition:
|
|
self._visit(node.condition)
|
|
# Body block
|
|
self.flow.nextblock()
|
|
self._visit(node.body)
|
|
self.flow.loops.pop()
|
|
# Loop it
|
|
if self.flow.block:
|
|
self.flow.block.add_child(condition_block)
|
|
self.flow.block.add_child(next_block)
|
|
# Else clause
|
|
if node.else_clause:
|
|
self.flow.nextblock(parent=condition_block)
|
|
self._visit(node.else_clause)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
else:
|
|
condition_block.add_child(next_block)
|
|
|
|
if next_block.parents:
|
|
self.flow.block = next_block
|
|
else:
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def mark_forloop_target(self, node):
|
|
# TODO: Remove redundancy with range optimization...
|
|
is_special = False
|
|
sequence = node.iterator.sequence
|
|
target = node.target
|
|
if isinstance(sequence, ExprNodes.SimpleCallNode):
|
|
function = sequence.function
|
|
if sequence.self is None and function.is_name:
|
|
entry = self.env.lookup(function.name)
|
|
if not entry or entry.is_builtin:
|
|
if function.name == 'reversed' and len(sequence.args) == 1:
|
|
sequence = sequence.args[0]
|
|
elif function.name == 'enumerate' and len(sequence.args) == 1:
|
|
if target.is_sequence_constructor and len(target.args) == 2:
|
|
iterator = sequence.args[0]
|
|
if iterator.is_name:
|
|
iterator_type = iterator.infer_type(self.env)
|
|
if iterator_type.is_builtin_type:
|
|
# assume that builtin types have a length within Py_ssize_t
|
|
self.mark_assignment(
|
|
target.args[0],
|
|
ExprNodes.IntNode(target.pos, value='PY_SSIZE_T_MAX',
|
|
type=PyrexTypes.c_py_ssize_t_type))
|
|
target = target.args[1]
|
|
sequence = sequence.args[0]
|
|
if isinstance(sequence, ExprNodes.SimpleCallNode):
|
|
function = sequence.function
|
|
if sequence.self is None and function.is_name:
|
|
entry = self.env.lookup(function.name)
|
|
if not entry or entry.is_builtin:
|
|
if function.name in ('range', 'xrange'):
|
|
is_special = True
|
|
for arg in sequence.args[:2]:
|
|
self.mark_assignment(target, arg)
|
|
if len(sequence.args) > 2:
|
|
self.mark_assignment(target, self.constant_folder(
|
|
ExprNodes.binop_node(node.pos,
|
|
'+',
|
|
sequence.args[0],
|
|
sequence.args[2])))
|
|
|
|
if not is_special:
|
|
# A for-loop basically translates to subsequent calls to
|
|
# __getitem__(), so using an IndexNode here allows us to
|
|
# naturally infer the base type of pointers, C arrays,
|
|
# Python strings, etc., while correctly falling back to an
|
|
# object type when the base type cannot be handled.
|
|
|
|
self.mark_assignment(target, node.item)
|
|
|
|
def visit_AsyncForStatNode(self, node):
|
|
return self.visit_ForInStatNode(node)
|
|
|
|
def visit_ForInStatNode(self, node):
|
|
condition_block = self.flow.nextblock()
|
|
next_block = self.flow.newblock()
|
|
# Condition with iterator
|
|
self.flow.loops.append(LoopDescr(next_block, condition_block))
|
|
self._visit(node.iterator)
|
|
# Target assignment
|
|
self.flow.nextblock()
|
|
|
|
if isinstance(node, Nodes.ForInStatNode):
|
|
self.mark_forloop_target(node)
|
|
elif isinstance(node, Nodes.AsyncForStatNode):
|
|
# not entirely correct, but good enough for now
|
|
self.mark_assignment(node.target, node.item)
|
|
else: # Parallel
|
|
self.mark_assignment(node.target)
|
|
|
|
# Body block
|
|
if isinstance(node, Nodes.ParallelRangeNode):
|
|
# In case of an invalid
|
|
self._delete_privates(node, exclude=node.target.entry)
|
|
|
|
self.flow.nextblock()
|
|
self._visit(node.body)
|
|
self.flow.loops.pop()
|
|
|
|
# Loop it
|
|
if self.flow.block:
|
|
self.flow.block.add_child(condition_block)
|
|
# Else clause
|
|
if node.else_clause:
|
|
self.flow.nextblock(parent=condition_block)
|
|
self._visit(node.else_clause)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
else:
|
|
condition_block.add_child(next_block)
|
|
|
|
if next_block.parents:
|
|
self.flow.block = next_block
|
|
else:
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def _delete_privates(self, node, exclude=None):
|
|
for private_node in node.assigned_nodes:
|
|
if not exclude or private_node.entry is not exclude:
|
|
self.flow.mark_deletion(private_node, private_node.entry)
|
|
|
|
def visit_ParallelRangeNode(self, node):
|
|
reductions = self.reductions
|
|
|
|
# if node.target is None or not a NameNode, an error will have
|
|
# been previously issued
|
|
if hasattr(node.target, 'entry'):
|
|
self.reductions = set(reductions)
|
|
|
|
for private_node in node.assigned_nodes:
|
|
private_node.entry.error_on_uninitialized = True
|
|
pos, reduction = node.assignments[private_node.entry]
|
|
if reduction:
|
|
self.reductions.add(private_node.entry)
|
|
|
|
node = self.visit_ForInStatNode(node)
|
|
|
|
self.reductions = reductions
|
|
return node
|
|
|
|
def visit_ParallelWithBlockNode(self, node):
|
|
for private_node in node.assigned_nodes:
|
|
private_node.entry.error_on_uninitialized = True
|
|
|
|
self._delete_privates(node)
|
|
self.visitchildren(node)
|
|
self._delete_privates(node)
|
|
|
|
return node
|
|
|
|
def visit_ForFromStatNode(self, node):
|
|
condition_block = self.flow.nextblock()
|
|
next_block = self.flow.newblock()
|
|
# Condition with iterator
|
|
self.flow.loops.append(LoopDescr(next_block, condition_block))
|
|
self._visit(node.bound1)
|
|
self._visit(node.bound2)
|
|
if node.step is not None:
|
|
self._visit(node.step)
|
|
# Target assignment
|
|
self.flow.nextblock()
|
|
self.mark_assignment(node.target, node.bound1)
|
|
if node.step is not None:
|
|
self.mark_assignment(node.target, self.constant_folder(
|
|
ExprNodes.binop_node(node.pos, '+', node.bound1, node.step)))
|
|
# Body block
|
|
self.flow.nextblock()
|
|
self._visit(node.body)
|
|
self.flow.loops.pop()
|
|
# Loop it
|
|
if self.flow.block:
|
|
self.flow.block.add_child(condition_block)
|
|
# Else clause
|
|
if node.else_clause:
|
|
self.flow.nextblock(parent=condition_block)
|
|
self._visit(node.else_clause)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
else:
|
|
condition_block.add_child(next_block)
|
|
|
|
if next_block.parents:
|
|
self.flow.block = next_block
|
|
else:
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_LoopNode(self, node):
|
|
raise InternalError("Generic loops are not supported")
|
|
|
|
def visit_WithTargetAssignmentStatNode(self, node):
|
|
self.mark_assignment(node.lhs, node.with_node.enter_call)
|
|
return node
|
|
|
|
def visit_WithStatNode(self, node):
|
|
self._visit(node.manager)
|
|
self._visit(node.enter_call)
|
|
self._visit(node.body)
|
|
return node
|
|
|
|
def visit_TryExceptStatNode(self, node):
|
|
# After exception handling
|
|
next_block = self.flow.newblock()
|
|
# Body block
|
|
self.flow.newblock()
|
|
# Exception entry point
|
|
entry_point = self.flow.newblock()
|
|
self.flow.exceptions.append(ExceptionDescr(entry_point))
|
|
self.flow.nextblock()
|
|
## XXX: links to exception handling point should be added by
|
|
## XXX: children nodes
|
|
self.flow.block.add_child(entry_point)
|
|
self.flow.nextblock()
|
|
self._visit(node.body)
|
|
self.flow.exceptions.pop()
|
|
|
|
# After exception
|
|
if self.flow.block:
|
|
if node.else_clause:
|
|
self.flow.nextblock()
|
|
self._visit(node.else_clause)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
|
|
for clause in node.except_clauses:
|
|
self.flow.block = entry_point
|
|
if clause.pattern:
|
|
for pattern in clause.pattern:
|
|
self._visit(pattern)
|
|
else:
|
|
# TODO: handle * pattern
|
|
pass
|
|
entry_point = self.flow.newblock(parent=self.flow.block)
|
|
self.flow.nextblock()
|
|
if clause.target:
|
|
self.mark_assignment(clause.target)
|
|
self._visit(clause.body)
|
|
if self.flow.block:
|
|
self.flow.block.add_child(next_block)
|
|
|
|
if self.flow.exceptions:
|
|
entry_point.add_child(self.flow.exceptions[-1].entry_point)
|
|
|
|
if next_block.parents:
|
|
self.flow.block = next_block
|
|
else:
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_TryFinallyStatNode(self, node):
|
|
body_block = self.flow.nextblock()
|
|
|
|
# Exception entry point
|
|
entry_point = self.flow.newblock()
|
|
self.flow.block = entry_point
|
|
self._visit(node.finally_except_clause)
|
|
|
|
if self.flow.block and self.flow.exceptions:
|
|
self.flow.block.add_child(self.flow.exceptions[-1].entry_point)
|
|
|
|
# Normal execution
|
|
finally_enter = self.flow.newblock()
|
|
self.flow.block = finally_enter
|
|
self._visit(node.finally_clause)
|
|
finally_exit = self.flow.block
|
|
|
|
descr = ExceptionDescr(entry_point, finally_enter, finally_exit)
|
|
self.flow.exceptions.append(descr)
|
|
if self.flow.loops:
|
|
self.flow.loops[-1].exceptions.append(descr)
|
|
self.flow.block = body_block
|
|
## XXX: Is it still required
|
|
body_block.add_child(entry_point)
|
|
self.flow.nextblock()
|
|
self._visit(node.body)
|
|
self.flow.exceptions.pop()
|
|
if self.flow.loops:
|
|
self.flow.loops[-1].exceptions.pop()
|
|
|
|
if self.flow.block:
|
|
self.flow.block.add_child(finally_enter)
|
|
if finally_exit:
|
|
self.flow.block = self.flow.nextblock(parent=finally_exit)
|
|
else:
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_RaiseStatNode(self, node):
|
|
self.mark_position(node)
|
|
self.visitchildren(node)
|
|
if self.flow.exceptions:
|
|
self.flow.block.add_child(self.flow.exceptions[-1].entry_point)
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_ReraiseStatNode(self, node):
|
|
self.mark_position(node)
|
|
if self.flow.exceptions:
|
|
self.flow.block.add_child(self.flow.exceptions[-1].entry_point)
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_ReturnStatNode(self, node):
|
|
self.mark_position(node)
|
|
self.visitchildren(node)
|
|
|
|
for exception in self.flow.exceptions[::-1]:
|
|
if exception.finally_enter:
|
|
self.flow.block.add_child(exception.finally_enter)
|
|
if exception.finally_exit:
|
|
exception.finally_exit.add_child(self.flow.exit_point)
|
|
break
|
|
else:
|
|
if self.flow.block:
|
|
self.flow.block.add_child(self.flow.exit_point)
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_BreakStatNode(self, node):
|
|
if not self.flow.loops:
|
|
#error(node.pos, "break statement not inside loop")
|
|
return node
|
|
loop = self.flow.loops[-1]
|
|
self.mark_position(node)
|
|
for exception in loop.exceptions[::-1]:
|
|
if exception.finally_enter:
|
|
self.flow.block.add_child(exception.finally_enter)
|
|
if exception.finally_exit:
|
|
exception.finally_exit.add_child(loop.next_block)
|
|
break
|
|
else:
|
|
self.flow.block.add_child(loop.next_block)
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_ContinueStatNode(self, node):
|
|
if not self.flow.loops:
|
|
#error(node.pos, "continue statement not inside loop")
|
|
return node
|
|
loop = self.flow.loops[-1]
|
|
self.mark_position(node)
|
|
for exception in loop.exceptions[::-1]:
|
|
if exception.finally_enter:
|
|
self.flow.block.add_child(exception.finally_enter)
|
|
if exception.finally_exit:
|
|
exception.finally_exit.add_child(loop.loop_block)
|
|
break
|
|
else:
|
|
self.flow.block.add_child(loop.loop_block)
|
|
self.flow.block = None
|
|
return node
|
|
|
|
def visit_ComprehensionNode(self, node):
|
|
if node.expr_scope:
|
|
self.env_stack.append(self.env)
|
|
self.env = node.expr_scope
|
|
# Skip append node here
|
|
self._visit(node.loop)
|
|
if node.expr_scope:
|
|
self.env = self.env_stack.pop()
|
|
return node
|
|
|
|
def visit_ScopedExprNode(self, node):
|
|
if node.expr_scope:
|
|
self.env_stack.append(self.env)
|
|
self.env = node.expr_scope
|
|
self.visitchildren(node)
|
|
if node.expr_scope:
|
|
self.env = self.env_stack.pop()
|
|
return node
|
|
|
|
def visit_PyClassDefNode(self, node):
|
|
self.visitchildren(node, ('dict', 'metaclass',
|
|
'mkw', 'bases', 'class_result'))
|
|
self.flow.mark_assignment(node.target, node.classobj,
|
|
self.env.lookup(node.name))
|
|
self.env_stack.append(self.env)
|
|
self.env = node.scope
|
|
self.flow.nextblock()
|
|
self.visitchildren(node, ('body',))
|
|
self.flow.nextblock()
|
|
self.env = self.env_stack.pop()
|
|
return node
|
|
|
|
def visit_AmpersandNode(self, node):
|
|
if node.operand.is_name:
|
|
# Fake assignment to silence warning
|
|
self.mark_assignment(node.operand, fake_rhs_expr)
|
|
self.visitchildren(node)
|
|
return node
|