diff options
author | Anton Samokhvalov <pg83@yandex.ru> | 2022-02-10 16:45:15 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:45:15 +0300 |
commit | 72cb13b4aff9bc9cf22e49251bc8fd143f82538f (patch) | |
tree | da2c34829458c7d4e74bdfbdf85dff449e9e7fb8 /contrib/tools/cython/Cython/Compiler/FlowControl.py | |
parent | 778e51ba091dc39e7b7fcab2b9cf4dbedfb6f2b5 (diff) | |
download | ydb-72cb13b4aff9bc9cf22e49251bc8fd143f82538f.tar.gz |
Restoring authorship annotation for Anton Samokhvalov <pg83@yandex.ru>. Commit 1 of 2.
Diffstat (limited to 'contrib/tools/cython/Cython/Compiler/FlowControl.py')
-rw-r--r-- | contrib/tools/cython/Cython/Compiler/FlowControl.py | 2542 |
1 files changed, 1271 insertions, 1271 deletions
diff --git a/contrib/tools/cython/Cython/Compiler/FlowControl.py b/contrib/tools/cython/Cython/Compiler/FlowControl.py index df04471f90..9b54d154af 100644 --- a/contrib/tools/cython/Cython/Compiler/FlowControl.py +++ b/contrib/tools/cython/Cython/Compiler/FlowControl.py @@ -1,783 +1,783 @@ -from __future__ import absolute_import - -import cython -cython.declare(PyrexTypes=object, ExprNodes=object, Nodes=object, +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 + 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 - + + +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): + 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: + 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): + 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): + + def error(self, pos, message): self.messages.add((pos, True, message)) - - def warning(self, pos, message): + + def warning(self, pos, message): self.messages.add((pos, False, message)) - - def report(self): + + 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 + 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 + 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): + 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() + # '_' 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) + + # 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: @@ -785,453 +785,453 @@ class ControlFlowAnalysis(CythonTransform): 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 + 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) + 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 - + 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_SizeofVarNode(self, node): return node def visit_TypeidNode(self, 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: + 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], + 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) - + + 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) + 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: + 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 + # 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 - 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) - + + 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 + 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) + outer_exception_handlers = iter(self.flow.exceptions[::-1]) for handler in outer_exception_handlers: if handler.finally_enter: @@ -1244,82 +1244,82 @@ class ControlFlowAnalysis(CythonTransform): exit_point = next_handler.finally_enter break handler.finally_exit.add_child(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 + 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 |