third_party/cython/src/Cython/Compiler/FlowControl.py

   1 import cython
   2 cython.declare(PyrexTypes=object, ExprNodes=object, Nodes=object,
   3                Builtin=object, InternalError=object,
   4                error=object, warning=object,
   5                py_object_type=object, unspecified_type=object,
   6                object_expr=object, object_expr_not_none=object,
   7                fake_rhs_expr=object, TypedExprNode=object)
   8
   9 import Builtin
  10 import ExprNodes
  11 import Nodes
  12 import Options
  13 from PyrexTypes import py_object_type, unspecified_type
  14 import PyrexTypes
  15
  16 from Visitor import TreeVisitor, CythonTransform
  17 from Errors import error, warning, InternalError
  18
  19 class TypedExprNode(ExprNodes.ExprNode):
  20     # Used for declaring assignments of a specified type without a known entry.
  21     def __init__(self, type, may_be_none=None, pos=None):
  22         super(TypedExprNode, self).__init__(pos)
  23         self.type = type
  24         self._may_be_none = may_be_none
  25
  26     def may_be_none(self):
  27         return self._may_be_none != False
  28
  29 object_expr = TypedExprNode(py_object_type, may_be_none=True)
  30 object_expr_not_none = TypedExprNode(py_object_type, may_be_none=False)
  31 # Fake rhs to silence "unused variable" warning
  32 fake_rhs_expr = TypedExprNode(unspecified_type)
  33
  34
  35 class ControlBlock(object):
  36     """Control flow graph node. Sequence of assignments and name references.
  37
  38        children  set of children nodes
  39        parents   set of parent nodes
  40        positions set of position markers
  41
  42        stats     list of block statements
  43        gen       dict of assignments generated by this block
  44        bounded   set  of entries that are definitely bounded in this block
  45
  46        Example:
  47
  48         a = 1
  49         b = a + c # 'c' is already bounded or exception here
  50
  51         stats = [Assignment(a), NameReference(a), NameReference(c),
  52                      Assignment(b)]
  53         gen = {Entry(a): Assignment(a), Entry(b): Assignment(b)}
  54         bounded = set([Entry(a), Entry(c)])
  55
  56     """
  57
  58     def __init__(self):
  59         self.children = set()
  60         self.parents = set()
  61         self.positions = set()
  62
  63         self.stats = []
  64         self.gen = {}
  65         self.bounded = set()
  66
  67         self.i_input = 0
  68         self.i_output = 0
  69         self.i_gen = 0
  70         self.i_kill = 0
  71         self.i_state = 0
  72
  73     def empty(self):
  74         return (not self.stats and not self.positions)
  75
  76     def detach(self):
  77         """Detach block from parents and children."""
  78         for child in self.children:
  79             child.parents.remove(self)
  80         for parent in self.parents:
  81             parent.children.remove(self)
  82         self.parents.clear()
  83         self.children.clear()
  84
  85     def add_child(self, block):
  86         self.children.add(block)
  87         block.parents.add(self)
  88
  89
  90 class ExitBlock(ControlBlock):
  91     """Non-empty exit point block."""
  92
  93     def empty(self):
  94         return False
  95
  96
  97 class AssignmentList(object):
  98     def __init__(self):
  99         self.stats = []
 100
 101
 102 class ControlFlow(object):
 103     """Control-flow graph.
 104
 105        entry_point ControlBlock entry point for this graph
 106        exit_point  ControlBlock normal exit point
 107        block       ControlBlock current block
 108        blocks      set    children nodes
 109        entries     set    tracked entries
 110        loops       list   stack for loop descriptors
 111        exceptions  list   stack for exception descriptors
 112     """
 113
 114     def __init__(self):
 115         self.blocks = set()
 116         self.entries = set()
 117         self.loops = []
 118         self.exceptions = []
 119
 120         self.entry_point = ControlBlock()
 121         self.exit_point = ExitBlock()
 122         self.blocks.add(self.exit_point)
 123         self.block = self.entry_point
 124
 125     def newblock(self, parent=None):
 126         """Create floating block linked to `parent` if given.
 127
 128            NOTE: Block is NOT added to self.blocks
 129         """
 130         block = ControlBlock()
 131         self.blocks.add(block)
 132         if parent:
 133             parent.add_child(block)
 134         return block
 135
 136     def nextblock(self, parent=None):
 137         """Create block children block linked to current or `parent` if given.
 138
 139            NOTE: Block is added to self.blocks
 140         """
 141         block = ControlBlock()
 142         self.blocks.add(block)
 143         if parent:
 144             parent.add_child(block)
 145         elif self.block:
 146             self.block.add_child(block)
 147         self.block = block
 148         return self.block
 149
 150     def is_tracked(self, entry):
 151         if entry.is_anonymous:
 152             return False
 153         return (entry.is_local or entry.is_pyclass_attr or entry.is_arg or
 154                 entry.from_closure or entry.in_closure or
 155                 entry.error_on_uninitialized)
 156
 157     def is_statically_assigned(self, entry):
 158         if (entry.is_local and entry.is_variable and
 159                 (entry.type.is_struct_or_union or
 160                  entry.type.is_complex or
 161                  entry.type.is_array or
 162                  entry.type.is_cpp_class)):
 163             # stack allocated structured variable => never uninitialised
 164             return True
 165         return False
 166
 167     def mark_position(self, node):
 168         """Mark position, will be used to draw graph nodes."""
 169         if self.block:
 170             self.block.positions.add(node.pos[:2])
 171
 172     def mark_assignment(self, lhs, rhs, entry):
 173         if self.block and self.is_tracked(entry):
 174             assignment = NameAssignment(lhs, rhs, entry)
 175             self.block.stats.append(assignment)
 176             self.block.gen[entry] = assignment
 177             self.entries.add(entry)
 178
 179     def mark_argument(self, lhs, rhs, entry):
 180         if self.block and self.is_tracked(entry):
 181             assignment = Argument(lhs, rhs, entry)
 182             self.block.stats.append(assignment)
 183             self.block.gen[entry] = assignment
 184             self.entries.add(entry)
 185
 186     def mark_deletion(self, node, entry):
 187         if self.block and self.is_tracked(entry):
 188             assignment = NameDeletion(node, entry)
 189             self.block.stats.append(assignment)
 190             self.block.gen[entry] = Uninitialized
 191             self.entries.add(entry)
 192
 193     def mark_reference(self, node, entry):
 194         if self.block and self.is_tracked(entry):
 195             self.block.stats.append(NameReference(node, entry))
 196             ## XXX: We don't track expression evaluation order so we can't use
 197             ## XXX: successful reference as initialization sign.
 198             ## # Local variable is definitely bound after this reference
 199             ## if not node.allow_null:
 200             ##     self.block.bounded.add(entry)
 201             self.entries.add(entry)
 202
 203     def normalize(self):
 204         """Delete unreachable and orphan blocks."""
 205         queue = set([self.entry_point])
 206         visited = set()
 207         while queue:
 208             root = queue.pop()
 209             visited.add(root)
 210             for child in root.children:
 211                 if child not in visited:
 212                     queue.add(child)
 213         unreachable = self.blocks - visited
 214         for block in unreachable:
 215             block.detach()
 216         visited.remove(self.entry_point)
 217         for block in visited:
 218             if block.empty():
 219                 for parent in block.parents: # Re-parent
 220                     for child in block.children:
 221                         parent.add_child(child)
 222                 block.detach()
 223                 unreachable.add(block)
 224         self.blocks -= unreachable
 225
 226     def initialize(self):
 227         """Set initial state, map assignments to bits."""
 228         self.assmts = {}
 229
 230         bit = 1
 231         for entry in self.entries:
 232             assmts = AssignmentList()
 233             assmts.mask = assmts.bit = bit
 234             self.assmts[entry] = assmts
 235             bit <<= 1
 236
 237         for block in self.blocks:
 238             for stat in block.stats:
 239                 if isinstance(stat, NameAssignment):
 240                     stat.bit = bit
 241                     assmts = self.assmts[stat.entry]
 242                     assmts.stats.append(stat)
 243                     assmts.mask |= bit
 244                     bit <<= 1
 245
 246         for block in self.blocks:
 247             for entry, stat in block.gen.items():
 248                 assmts = self.assmts[entry]
 249                 if stat is Uninitialized:
 250                     block.i_gen |= assmts.bit
 251                 else:
 252                     block.i_gen |= stat.bit
 253                 block.i_kill |= assmts.mask
 254             block.i_output = block.i_gen
 255             for entry in block.bounded:
 256                 block.i_kill |= self.assmts[entry].bit
 257
 258         for assmts in self.assmts.itervalues():
 259             self.entry_point.i_gen |= assmts.bit
 260         self.entry_point.i_output = self.entry_point.i_gen
 261
 262     def map_one(self, istate, entry):
 263         ret = set()
 264         assmts = self.assmts[entry]
 265         if istate & assmts.bit:
 266             if self.is_statically_assigned(entry):
 267                 ret.add(StaticAssignment(entry))
 268             elif entry.from_closure:
 269                 ret.add(Unknown)
 270             else:
 271                 ret.add(Uninitialized)
 272         for assmt in assmts.stats:
 273             if istate & assmt.bit:
 274                 ret.add(assmt)
 275         return ret
 276
 277     def reaching_definitions(self):
 278         """Per-block reaching definitions analysis."""
 279         dirty = True
 280         while dirty:
 281             dirty = False
 282             for block in self.blocks:
 283                 i_input = 0
 284                 for parent in block.parents:
 285                     i_input |= parent.i_output
 286                 i_output = (i_input & ~block.i_kill) | block.i_gen
 287                 if i_output != block.i_output:
 288                     dirty = True
 289                 block.i_input = i_input
 290                 block.i_output = i_output
 291
 292
 293 class LoopDescr(object):
 294     def __init__(self, next_block, loop_block):
 295         self.next_block = next_block
 296         self.loop_block = loop_block
 297         self.exceptions = []
 298
 299
 300 class ExceptionDescr(object):
 301     """Exception handling helper.
 302
 303     entry_point   ControlBlock Exception handling entry point
 304     finally_enter ControlBlock Normal finally clause entry point
 305     finally_exit  ControlBlock Normal finally clause exit point
 306     """
 307
 308     def __init__(self, entry_point, finally_enter=None, finally_exit=None):
 309         self.entry_point = entry_point
 310         self.finally_enter = finally_enter
 311         self.finally_exit = finally_exit
 312
 313
 314 class NameAssignment(object):
 315     def __init__(self, lhs, rhs, entry):
 316         if lhs.cf_state is None:
 317             lhs.cf_state = set()
 318         self.lhs = lhs
 319         self.rhs = rhs
 320         self.entry = entry
 321         self.pos = lhs.pos
 322         self.refs = set()
 323         self.is_arg = False
 324         self.is_deletion = False
 325         self.inferred_type = None
 326
 327     def __repr__(self):
 328         return '%s(entry=%r)' % (self.__class__.__name__, self.entry)
 329
 330     def infer_type(self):
 331         self.inferred_type = self.rhs.infer_type(self.entry.scope)
 332         return self.inferred_type
 333
 334     def type_dependencies(self):
 335         return self.rhs.type_dependencies(self.entry.scope)
 336
 337     @property
 338     def type(self):
 339         if not self.entry.type.is_unspecified:
 340             return self.entry.type
 341         return self.inferred_type
 342
 343
 344 class StaticAssignment(NameAssignment):
 345     """Initialised at declaration time, e.g. stack allocation."""
 346     def __init__(self, entry):
 347         if not entry.type.is_pyobject:
 348             may_be_none = False
 349         else:
 350             may_be_none = None  # unknown
 351         lhs = TypedExprNode(
 352             entry.type, may_be_none=may_be_none, pos=entry.pos)
 353         super(StaticAssignment, self).__init__(lhs, lhs, entry)
 354
 355     def infer_type(self):
 356         return self.entry.type
 357
 358     def type_dependencies(self):
 359         return ()
 360
 361
 362 class Argument(NameAssignment):
 363     def __init__(self, lhs, rhs, entry):
 364         NameAssignment.__init__(self, lhs, rhs, entry)
 365         self.is_arg = True
 366
 367
 368 class NameDeletion(NameAssignment):
 369     def __init__(self, lhs, entry):
 370         NameAssignment.__init__(self, lhs, lhs, entry)
 371         self.is_deletion = True
 372
 373     def infer_type(self):
 374         inferred_type = self.rhs.infer_type(self.entry.scope)
 375         if (not inferred_type.is_pyobject and
 376             inferred_type.can_coerce_to_pyobject(self.entry.scope)):
 377             return py_object_type
 378         self.inferred_type = inferred_type
 379         return inferred_type
 380
 381
 382 class Uninitialized(object):
 383     """Definitely not initialised yet."""
 384
 385
 386 class Unknown(object):
 387     """Coming from outer closure, might be initialised or not."""
 388
 389
 390 class NameReference(object):
 391     def __init__(self, node, entry):
 392         if node.cf_state is None:
 393             node.cf_state = set()
 394         self.node = node
 395         self.entry = entry
 396         self.pos = node.pos
 397
 398     def __repr__(self):
 399         return '%s(entry=%r)' % (self.__class__.__name__, self.entry)
 400
 401
 402 class ControlFlowState(list):
 403     # Keeps track of Node's entry assignments
 404     #
 405     # cf_is_null        [boolean] It is uninitialized
 406     # cf_maybe_null     [boolean] May be uninitialized
 407     # is_single         [boolean] Has only one assignment at this point
 408
 409     cf_maybe_null = False
 410     cf_is_null = False
 411     is_single = False
 412
 413     def __init__(self, state):
 414         if Uninitialized in state:
 415             state.discard(Uninitialized)
 416             self.cf_maybe_null = True
 417             if not state:
 418                 self.cf_is_null = True
 419         elif Unknown in state:
 420             state.discard(Unknown)
 421             self.cf_maybe_null = True
 422         else:
 423             if len(state) == 1:
 424                 self.is_single = True
 425         # XXX: Remove fake_rhs_expr
 426         super(ControlFlowState, self).__init__(
 427             [i for i in state if i.rhs is not fake_rhs_expr])
 428
 429     def one(self):
 430         return self[0]
 431
 432
 433 class GVContext(object):
 434     """Graphviz subgraph object."""
 435
 436     def __init__(self):
 437         self.blockids = {}
 438         self.nextid = 0
 439         self.children = []
 440         self.sources = {}
 441
 442     def add(self, child):
 443         self.children.append(child)
 444
 445     def nodeid(self, block):
 446         if block not in self.blockids:
 447             self.blockids[block] = 'block%d' % self.nextid
 448             self.nextid += 1
 449         return self.blockids[block]
 450
 451     def extract_sources(self, block):
 452         if not block.positions:
 453             return ''
 454         start = min(block.positions)
 455         stop = max(block.positions)
 456         srcdescr = start[0]
 457         if not srcdescr in self.sources:
 458             self.sources[srcdescr] = list(srcdescr.get_lines())
 459         lines = self.sources[srcdescr]
 460         return '\\n'.join([l.strip() for l in lines[start[1] - 1:stop[1]]])
 461
 462     def render(self, fp, name, annotate_defs=False):
 463         """Render graphviz dot graph"""
 464         fp.write('digraph %s {\n' % name)
 465         fp.write(' node [shape=box];\n')
 466         for child in self.children:
 467             child.render(fp, self, annotate_defs)
 468         fp.write('}\n')
 469
 470     def escape(self, text):
 471         return text.replace('"', '\\"').replace('\n', '\\n')
 472
 473
 474 class GV(object):
 475     """Graphviz DOT renderer."""
 476
 477     def __init__(self, name, flow):
 478         self.name = name
 479         self.flow = flow
 480
 481     def render(self, fp, ctx, annotate_defs=False):
 482         fp.write(' subgraph %s {\n' % self.name)
 483         for block in self.flow.blocks:
 484             label = ctx.extract_sources(block)
 485             if annotate_defs:
 486                 for stat in block.stats:
 487                     if isinstance(stat, NameAssignment):
 488                         label += '\n %s [definition]' % stat.entry.name
 489                     elif isinstance(stat, NameReference):
 490                         if stat.entry:
 491                             label += '\n %s [reference]' % stat.entry.name
 492             if not label:
 493                 label = 'empty'
 494             pid = ctx.nodeid(block)
 495             fp.write('  %s [label="%s"];\n' % (pid, ctx.escape(label)))
 496         for block in self.flow.blocks:
 497             pid = ctx.nodeid(block)
 498             for child in block.children:
 499                 fp.write('  %s -> %s;\n' % (pid, ctx.nodeid(child)))
 500         fp.write(' }\n')
 501
 502
 503 class MessageCollection(object):
 504     """Collect error/warnings messages first then sort"""
 505     def __init__(self):
 506         self.messages = []
 507
 508     def error(self, pos, message):
 509         self.messages.append((pos, True, message))
 510
 511     def warning(self, pos, message):
 512         self.messages.append((pos, False, message))
 513
 514     def report(self):
 515         self.messages.sort()
 516         for pos, is_error, message in self.messages:
 517             if is_error:
 518                 error(pos, message)
 519             else:
 520                 warning(pos, message, 2)
 521
 522
 523 def check_definitions(flow, compiler_directives):
 524     flow.initialize()
 525     flow.reaching_definitions()
 526
 527     # Track down state
 528     assignments = set()
 529     # Node to entry map
 530     references = {}
 531     assmt_nodes = set()
 532
 533     for block in flow.blocks:
 534         i_state = block.i_input
 535         for stat in block.stats:
 536             i_assmts = flow.assmts[stat.entry]
 537             state = flow.map_one(i_state, stat.entry)
 538             if isinstance(stat, NameAssignment):
 539                 stat.lhs.cf_state.update(state)
 540                 assmt_nodes.add(stat.lhs)
 541                 i_state = i_state & ~i_assmts.mask
 542                 if stat.is_deletion:
 543                     i_state |= i_assmts.bit
 544                 else:
 545                     i_state |= stat.bit
 546                 assignments.add(stat)
 547                 if stat.rhs is not fake_rhs_expr:
 548                     stat.entry.cf_assignments.append(stat)
 549             elif isinstance(stat, NameReference):
 550                 references[stat.node] = stat.entry
 551                 stat.entry.cf_references.append(stat)
 552                 stat.node.cf_state.update(state)
 553                 ## if not stat.node.allow_null:
 554                 ##     i_state &= ~i_assmts.bit
 555                 ## # after successful read, the state is known to be initialised
 556                 state.discard(Uninitialized)
 557                 state.discard(Unknown)
 558                 for assmt in state:
 559                     assmt.refs.add(stat)
 560
 561     # Check variable usage
 562     warn_maybe_uninitialized = compiler_directives['warn.maybe_uninitialized']
 563     warn_unused_result = compiler_directives['warn.unused_result']
 564     warn_unused = compiler_directives['warn.unused']
 565     warn_unused_arg = compiler_directives['warn.unused_arg']
 566
 567     messages = MessageCollection()
 568
 569     # assignment hints
 570     for node in assmt_nodes:
 571         if Uninitialized in node.cf_state:
 572             node.cf_maybe_null = True
 573             if len(node.cf_state) == 1:
 574                 node.cf_is_null = True
 575             else:
 576                 node.cf_is_null = False
 577         elif Unknown in node.cf_state:
 578             node.cf_maybe_null = True
 579         else:
 580             node.cf_is_null = False
 581             node.cf_maybe_null = False
 582
 583     # Find uninitialized references and cf-hints
 584     for node, entry in references.iteritems():
 585         if Uninitialized in node.cf_state:
 586             node.cf_maybe_null = True
 587             if not entry.from_closure and len(node.cf_state) == 1:
 588                 node.cf_is_null = True
 589             if (node.allow_null or entry.from_closure
 590                 or entry.is_pyclass_attr or entry.type.is_error):
 591                 pass # Can be uninitialized here
 592             elif node.cf_is_null:
 593                 if entry.error_on_uninitialized or (
 594                         Options.error_on_uninitialized and (
 595                         entry.type.is_pyobject or entry.type.is_unspecified)):
 596                     messages.error(
 597                         node.pos,
 598                         "local variable '%s' referenced before assignment"
 599                         % entry.name)
 600                 else:
 601                     messages.warning(
 602                         node.pos,
 603                         "local variable '%s' referenced before assignment"
 604                         % entry.name)
 605             elif warn_maybe_uninitialized:
 606                 messages.warning(
 607                     node.pos,
 608                     "local variable '%s' might be referenced before assignment"
 609                     % entry.name)
 610         elif Unknown in node.cf_state:
 611             # TODO: better cross-closure analysis to know when inner functions
 612             #       are being called before a variable is being set, and when
 613             #       a variable is known to be set before even defining the
 614             #       inner function, etc.
 615             node.cf_maybe_null = True
 616         else:
 617             node.cf_is_null = False
 618             node.cf_maybe_null = False
 619
 620     # Unused result
 621     for assmt in assignments:
 622         if (not assmt.refs and not assmt.entry.is_pyclass_attr
 623             and not assmt.entry.in_closure):
 624             if assmt.entry.cf_references and warn_unused_result:
 625                 if assmt.is_arg:
 626                     messages.warning(assmt.pos, "Unused argument value '%s'" %
 627                                      assmt.entry.name)
 628                 else:
 629                     messages.warning(assmt.pos, "Unused result in '%s'" %
 630                                      assmt.entry.name)
 631             assmt.lhs.cf_used = False
 632
 633     # Unused entries
 634     for entry in flow.entries:
 635         if (not entry.cf_references
 636                 and not entry.is_pyclass_attr):
 637             if entry.name != '_':
 638                 # '_' is often used for unused variables, e.g. in loops
 639                 if entry.is_arg:
 640                     if warn_unused_arg:
 641                         messages.warning(entry.pos, "Unused argument '%s'" %
 642                                          entry.name)
 643                 else:
 644                     if warn_unused:
 645                         messages.warning(entry.pos, "Unused entry '%s'" %
 646                                          entry.name)
 647             entry.cf_used = False
 648
 649     messages.report()
 650
 651     for node in assmt_nodes:
 652         node.cf_state = ControlFlowState(node.cf_state)
 653     for node in references:
 654         node.cf_state = ControlFlowState(node.cf_state)
 655
 656
 657 class AssignmentCollector(TreeVisitor):
 658     def __init__(self):
 659         super(AssignmentCollector, self).__init__()
 660         self.assignments = []
 661
 662     def visit_Node(self):
 663         self._visitchildren(self, None)
 664
 665     def visit_SingleAssignmentNode(self, node):
 666         self.assignments.append((node.lhs, node.rhs))
 667
 668     def visit_CascadedAssignmentNode(self, node):
 669         for lhs in node.lhs_list:
 670             self.assignments.append((lhs, node.rhs))
 671
 672
 673 class ControlFlowAnalysis(CythonTransform):
 674
 675     def visit_ModuleNode(self, node):
 676         self.gv_ctx = GVContext()
 677
 678         # Set of NameNode reductions
 679         self.reductions = set()
 680
 681         self.in_inplace_assignment = False
 682         self.env_stack = []
 683         self.env = node.scope
 684         self.stack = []
 685         self.flow = ControlFlow()
 686         self.visitchildren(node)
 687
 688         check_definitions(self.flow, self.current_directives)
 689
 690         dot_output = self.current_directives['control_flow.dot_output']
 691         if dot_output:
 692             annotate_defs = self.current_directives['control_flow.dot_annotate_defs']
 693             fp = open(dot_output, 'wt')
 694             try:
 695                 self.gv_ctx.render(fp, 'module', annotate_defs=annotate_defs)
 696             finally:
 697                 fp.close()
 698         return node
 699
 700     def visit_FuncDefNode(self, node):
 701         for arg in node.args:
 702             if arg.default:
 703                 self.visitchildren(arg)
 704         self.visitchildren(node, ('decorators',))
 705         self.env_stack.append(self.env)
 706         self.env = node.local_scope
 707         self.stack.append(self.flow)
 708         self.flow = ControlFlow()
 709
 710         # Collect all entries
 711         for entry in node.local_scope.entries.values():
 712             if self.flow.is_tracked(entry):
 713                 self.flow.entries.add(entry)
 714
 715         self.mark_position(node)
 716         # Function body block
 717         self.flow.nextblock()
 718
 719         for arg in node.args:
 720             self._visit(arg)
 721         if node.star_arg:
 722             self.flow.mark_argument(node.star_arg,
 723                                     TypedExprNode(Builtin.tuple_type,
 724                                                   may_be_none=False),
 725                                     node.star_arg.entry)
 726         if node.starstar_arg:
 727             self.flow.mark_argument(node.starstar_arg,
 728                                     TypedExprNode(Builtin.dict_type,
 729                                                   may_be_none=False),
 730                                     node.starstar_arg.entry)
 731         self._visit(node.body)
 732         # Workaround for generators
 733         if node.is_generator:
 734             self._visit(node.gbody.body)
 735
 736         # Exit point
 737         if self.flow.block:
 738             self.flow.block.add_child(self.flow.exit_point)
 739
 740         # Cleanup graph
 741         self.flow.normalize()
 742         check_definitions(self.flow, self.current_directives)
 743         self.flow.blocks.add(self.flow.entry_point)
 744
 745         self.gv_ctx.add(GV(node.local_scope.name, self.flow))
 746
 747         self.flow = self.stack.pop()
 748         self.env = self.env_stack.pop()
 749         return node
 750
 751     def visit_DefNode(self, node):
 752         node.used = True
 753         return self.visit_FuncDefNode(node)
 754
 755     def visit_GeneratorBodyDefNode(self, node):
 756         return node
 757
 758     def visit_CTypeDefNode(self, node):
 759         return node
 760
 761     def mark_assignment(self, lhs, rhs=None):
 762         if not self.flow.block:
 763             return
 764         if self.flow.exceptions:
 765             exc_descr = self.flow.exceptions[-1]
 766             self.flow.block.add_child(exc_descr.entry_point)
 767             self.flow.nextblock()
 768
 769         if not rhs:
 770             rhs = object_expr
 771         if lhs.is_name:
 772             if lhs.entry is not None:
 773                 entry = lhs.entry
 774             else:
 775                 entry = self.env.lookup(lhs.name)
 776             if entry is None: # TODO: This shouldn't happen...
 777                 return
 778             self.flow.mark_assignment(lhs, rhs, entry)
 779         elif isinstance(lhs, ExprNodes.SequenceNode):
 780             for arg in lhs.args:
 781                 self.mark_assignment(arg)
 782         else:
 783             self._visit(lhs)
 784
 785         if self.flow.exceptions:
 786             exc_descr = self.flow.exceptions[-1]
 787             self.flow.block.add_child(exc_descr.entry_point)
 788             self.flow.nextblock()
 789
 790     def mark_position(self, node):
 791         """Mark position if DOT output is enabled."""
 792         if self.current_directives['control_flow.dot_output']:
 793             self.flow.mark_position(node)
 794
 795     def visit_FromImportStatNode(self, node):
 796         for name, target in node.items:
 797             if name != "*":
 798                 self.mark_assignment(target)
 799         self.visitchildren(node)
 800         return node
 801
 802     def visit_AssignmentNode(self, node):
 803         raise InternalError("Unhandled assignment node")
 804
 805     def visit_SingleAssignmentNode(self, node):
 806         self._visit(node.rhs)
 807         self.mark_assignment(node.lhs, node.rhs)
 808         return node
 809
 810     def visit_CascadedAssignmentNode(self, node):
 811         self._visit(node.rhs)
 812         for lhs in node.lhs_list:
 813             self.mark_assignment(lhs, node.rhs)
 814         return node
 815
 816     def visit_ParallelAssignmentNode(self, node):
 817         collector = AssignmentCollector()
 818         collector.visitchildren(node)
 819         for lhs, rhs in collector.assignments:
 820             self._visit(rhs)
 821         for lhs, rhs in collector.assignments:
 822             self.mark_assignment(lhs, rhs)
 823         return node
 824
 825     def visit_InPlaceAssignmentNode(self, node):
 826         self.in_inplace_assignment = True
 827         self.visitchildren(node)
 828         self.in_inplace_assignment = False
 829         self.mark_assignment(node.lhs, node.create_binop_node())
 830         return node
 831
 832     def visit_DelStatNode(self, node):
 833         for arg in node.args:
 834             if arg.is_name:
 835                 entry = arg.entry or self.env.lookup(arg.name)
 836                 if entry.in_closure or entry.from_closure:
 837                     error(arg.pos,
 838                           "can not delete variable '%s' "
 839                           "referenced in nested scope" % entry.name)
 840                 # Mark reference
 841                 self._visit(arg)
 842                 self.flow.mark_deletion(arg, entry)
 843             else:
 844                 self._visit(arg)
 845         return node
 846
 847     def visit_CArgDeclNode(self, node):
 848         entry = self.env.lookup(node.name)
 849         if entry:
 850             may_be_none = not node.not_none
 851             self.flow.mark_argument(
 852                 node, TypedExprNode(entry.type, may_be_none), entry)
 853         return node
 854
 855     def visit_NameNode(self, node):
 856         if self.flow.block:
 857             entry = node.entry or self.env.lookup(node.name)
 858             if entry:
 859                 self.flow.mark_reference(node, entry)
 860
 861                 if entry in self.reductions and not self.in_inplace_assignment:
 862                     error(node.pos,
 863                           "Cannot read reduction variable in loop body")
 864
 865         return node
 866
 867     def visit_StatListNode(self, node):
 868         if self.flow.block:
 869             for stat in node.stats:
 870                 self._visit(stat)
 871                 if not self.flow.block:
 872                     stat.is_terminator = True
 873                     break
 874         return node
 875
 876     def visit_Node(self, node):
 877         self.visitchildren(node)
 878         self.mark_position(node)
 879         return node
 880
 881     def visit_IfStatNode(self, node):
 882         next_block = self.flow.newblock()
 883         parent = self.flow.block
 884         # If clauses
 885         for clause in node.if_clauses:
 886             parent = self.flow.nextblock(parent)
 887             self._visit(clause.condition)
 888             self.flow.nextblock()
 889             self._visit(clause.body)
 890             if self.flow.block:
 891                 self.flow.block.add_child(next_block)
 892         # Else clause
 893         if node.else_clause:
 894             self.flow.nextblock(parent=parent)
 895             self._visit(node.else_clause)
 896             if self.flow.block:
 897                 self.flow.block.add_child(next_block)
 898         else:
 899             parent.add_child(next_block)
 900
 901         if next_block.parents:
 902             self.flow.block = next_block
 903         else:
 904             self.flow.block = None
 905         return node
 906
 907     def visit_WhileStatNode(self, node):
 908         condition_block = self.flow.nextblock()
 909         next_block = self.flow.newblock()
 910         # Condition block
 911         self.flow.loops.append(LoopDescr(next_block, condition_block))
 912         if node.condition:
 913             self._visit(node.condition)
 914         # Body block
 915         self.flow.nextblock()
 916         self._visit(node.body)
 917         self.flow.loops.pop()
 918         # Loop it
 919         if self.flow.block:
 920             self.flow.block.add_child(condition_block)
 921             self.flow.block.add_child(next_block)
 922         # Else clause
 923         if node.else_clause:
 924             self.flow.nextblock(parent=condition_block)
 925             self._visit(node.else_clause)
 926             if self.flow.block:
 927                 self.flow.block.add_child(next_block)
 928         else:
 929             condition_block.add_child(next_block)
 930
 931         if next_block.parents:
 932             self.flow.block = next_block
 933         else:
 934             self.flow.block = None
 935         return node
 936
 937     def mark_forloop_target(self, node):
 938         # TODO: Remove redundancy with range optimization...
 939         is_special = False
 940         sequence = node.iterator.sequence
 941         target = node.target
 942         if isinstance(sequence, ExprNodes.SimpleCallNode):
 943             function = sequence.function
 944             if sequence.self is None and function.is_name:
 945                 entry = self.env.lookup(function.name)
 946                 if not entry or entry.is_builtin:
 947                     if function.name == 'reversed' and len(sequence.args) == 1:
 948                         sequence = sequence.args[0]
 949                     elif function.name == 'enumerate' and len(sequence.args) == 1:
 950                         if target.is_sequence_constructor and len(target.args) == 2:
 951                             iterator = sequence.args[0]
 952                             if iterator.is_name:
 953                                 iterator_type = iterator.infer_type(self.env)
 954                                 if iterator_type.is_builtin_type:
 955                                     # assume that builtin types have a length within Py_ssize_t
 956                                     self.mark_assignment(
 957                                         target.args[0],
 958                                         ExprNodes.IntNode(target.pos, value='PY_SSIZE_T_MAX',
 959                                                           type=PyrexTypes.c_py_ssize_t_type))
 960                                     target = target.args[1]
 961                                     sequence = sequence.args[0]
 962         if isinstance(sequence, ExprNodes.SimpleCallNode):
 963             function = sequence.function
 964             if sequence.self is None and function.is_name:
 965                 entry = self.env.lookup(function.name)
 966                 if not entry or entry.is_builtin:
 967                     if function.name in ('range', 'xrange'):
 968                         is_special = True
 969                         for arg in sequence.args[:2]:
 970                             self.mark_assignment(target, arg)
 971                         if len(sequence.args) > 2:
 972                             self.mark_assignment(
 973                                 target,
 974                                 ExprNodes.binop_node(node.pos,
 975                                                      '+',
 976                                                      sequence.args[0],
 977                                                      sequence.args[2]))
 978
 979         if not is_special:
 980             # A for-loop basically translates to subsequent calls to
 981             # __getitem__(), so using an IndexNode here allows us to
 982             # naturally infer the base type of pointers, C arrays,
 983             # Python strings, etc., while correctly falling back to an
 984             # object type when the base type cannot be handled.
 985
 986             self.mark_assignment(target, node.item)
 987
 988     def visit_ForInStatNode(self, node):
 989         condition_block = self.flow.nextblock()
 990         next_block = self.flow.newblock()
 991         # Condition with iterator
 992         self.flow.loops.append(LoopDescr(next_block, condition_block))
 993         self._visit(node.iterator)
 994         # Target assignment
 995         self.flow.nextblock()
 996
 997         if isinstance(node, Nodes.ForInStatNode):
 998             self.mark_forloop_target(node)
 999         else: # Parallel
1000             self.mark_assignment(node.target)
1001
1002         # Body block
1003         if isinstance(node, Nodes.ParallelRangeNode):
1004             # In case of an invalid
1005             self._delete_privates(node, exclude=node.target.entry)
1006
1007         self.flow.nextblock()
1008         self._visit(node.body)
1009         self.flow.loops.pop()
1010
1011         # Loop it
1012         if self.flow.block:
1013             self.flow.block.add_child(condition_block)
1014         # Else clause
1015         if node.else_clause:
1016             self.flow.nextblock(parent=condition_block)
1017             self._visit(node.else_clause)
1018             if self.flow.block:
1019                 self.flow.block.add_child(next_block)
1020         else:
1021             condition_block.add_child(next_block)
1022
1023         if next_block.parents:
1024             self.flow.block = next_block
1025         else:
1026             self.flow.block = None
1027         return node
1028
1029     def _delete_privates(self, node, exclude=None):
1030         for private_node in node.assigned_nodes:
1031             if not exclude or private_node.entry is not exclude:
1032                 self.flow.mark_deletion(private_node, private_node.entry)
1033
1034     def visit_ParallelRangeNode(self, node):
1035         reductions = self.reductions
1036
1037         # if node.target is None or not a NameNode, an error will have
1038         # been previously issued
1039         if hasattr(node.target, 'entry'):
1040             self.reductions = set(reductions)
1041
1042             for private_node in node.assigned_nodes:
1043                 private_node.entry.error_on_uninitialized = True
1044                 pos, reduction = node.assignments[private_node.entry]
1045                 if reduction:
1046                     self.reductions.add(private_node.entry)
1047
1048             node = self.visit_ForInStatNode(node)
1049
1050         self.reductions = reductions
1051         return node
1052
1053     def visit_ParallelWithBlockNode(self, node):
1054         for private_node in node.assigned_nodes:
1055             private_node.entry.error_on_uninitialized = True
1056
1057         self._delete_privates(node)
1058         self.visitchildren(node)
1059         self._delete_privates(node)
1060
1061         return node
1062
1063     def visit_ForFromStatNode(self, node):
1064         condition_block = self.flow.nextblock()
1065         next_block = self.flow.newblock()
1066         # Condition with iterator
1067         self.flow.loops.append(LoopDescr(next_block, condition_block))
1068         self._visit(node.bound1)
1069         self._visit(node.bound2)
1070         if node.step is not None:
1071             self._visit(node.step)
1072         # Target assignment
1073         self.flow.nextblock()
1074         self.mark_assignment(node.target, node.bound1)
1075         if node.step is not None:
1076             self.mark_assignment(node.target,
1077                                  ExprNodes.binop_node(node.pos, '+',
1078                                                       node.bound1, node.step))
1079         # Body block
1080         self.flow.nextblock()
1081         self._visit(node.body)
1082         self.flow.loops.pop()
1083         # Loop it
1084         if self.flow.block:
1085             self.flow.block.add_child(condition_block)
1086         # Else clause
1087         if node.else_clause:
1088             self.flow.nextblock(parent=condition_block)
1089             self._visit(node.else_clause)
1090             if self.flow.block:
1091                 self.flow.block.add_child(next_block)
1092         else:
1093             condition_block.add_child(next_block)
1094
1095         if next_block.parents:
1096             self.flow.block = next_block
1097         else:
1098             self.flow.block = None
1099         return node
1100
1101     def visit_LoopNode(self, node):
1102         raise InternalError("Generic loops are not supported")
1103
1104     def visit_WithTargetAssignmentStatNode(self, node):
1105         self.mark_assignment(node.lhs, node.rhs)
1106         return node
1107
1108     def visit_WithStatNode(self, node):
1109         self._visit(node.manager)
1110         self._visit(node.enter_call)
1111         self._visit(node.body)
1112         return node
1113
1114     def visit_TryExceptStatNode(self, node):
1115         # After exception handling
1116         next_block = self.flow.newblock()
1117         # Body block
1118         self.flow.newblock()
1119         # Exception entry point
1120         entry_point = self.flow.newblock()
1121         self.flow.exceptions.append(ExceptionDescr(entry_point))
1122         self.flow.nextblock()
1123         ## XXX: links to exception handling point should be added by
1124         ## XXX: children nodes
1125         self.flow.block.add_child(entry_point)
1126         self.flow.nextblock()
1127         self._visit(node.body)
1128         self.flow.exceptions.pop()
1129
1130         # After exception
1131         if self.flow.block:
1132             if node.else_clause:
1133                 self.flow.nextblock()
1134                 self._visit(node.else_clause)
1135             if self.flow.block:
1136                 self.flow.block.add_child(next_block)
1137
1138         for clause in node.except_clauses:
1139             self.flow.block = entry_point
1140             if clause.pattern:
1141                 for pattern in clause.pattern:
1142                     self._visit(pattern)
1143             else:
1144                 # TODO: handle * pattern
1145                 pass
1146             entry_point = self.flow.newblock(parent=self.flow.block)
1147             self.flow.nextblock()
1148             if clause.target:
1149                 self.mark_assignment(clause.target)
1150             self._visit(clause.body)
1151             if self.flow.block:
1152                 self.flow.block.add_child(next_block)
1153
1154         if self.flow.exceptions:
1155             entry_point.add_child(self.flow.exceptions[-1].entry_point)
1156
1157         if next_block.parents:
1158             self.flow.block = next_block
1159         else:
1160             self.flow.block = None
1161         return node
1162
1163     def visit_TryFinallyStatNode(self, node):
1164         body_block = self.flow.nextblock()
1165
1166         # Exception entry point
1167         entry_point = self.flow.newblock()
1168         self.flow.block = entry_point
1169         self._visit(node.finally_clause)
1170
1171         if self.flow.block and self.flow.exceptions:
1172             self.flow.block.add_child(self.flow.exceptions[-1].entry_point)
1173
1174         # Normal execution
1175         finally_enter = self.flow.newblock()
1176         self.flow.block = finally_enter
1177         self._visit(node.finally_clause)
1178         finally_exit = self.flow.block
1179
1180         descr = ExceptionDescr(entry_point, finally_enter, finally_exit)
1181         self.flow.exceptions.append(descr)
1182         if self.flow.loops:
1183             self.flow.loops[-1].exceptions.append(descr)
1184         self.flow.block = body_block
1185         ## XXX: Is it still required
1186         body_block.add_child(entry_point)
1187         self.flow.nextblock()
1188         self._visit(node.body)
1189         self.flow.exceptions.pop()
1190         if self.flow.loops:
1191             self.flow.loops[-1].exceptions.pop()
1192
1193         if self.flow.block:
1194             self.flow.block.add_child(finally_enter)
1195             if finally_exit:
1196                 self.flow.block = self.flow.nextblock(parent=finally_exit)
1197             else:
1198                 self.flow.block = None
1199         return node
1200
1201     def visit_RaiseStatNode(self, node):
1202         self.mark_position(node)
1203         self.visitchildren(node)
1204         if self.flow.exceptions:
1205             self.flow.block.add_child(self.flow.exceptions[-1].entry_point)
1206         self.flow.block = None
1207         return node
1208
1209     def visit_ReraiseStatNode(self, node):
1210         self.mark_position(node)
1211         if self.flow.exceptions:
1212             self.flow.block.add_child(self.flow.exceptions[-1].entry_point)
1213         self.flow.block = None
1214         return node
1215
1216     def visit_ReturnStatNode(self, node):
1217         self.mark_position(node)
1218         self.visitchildren(node)
1219
1220         for exception in self.flow.exceptions[::-1]:
1221             if exception.finally_enter:
1222                 self.flow.block.add_child(exception.finally_enter)
1223                 if exception.finally_exit:
1224                     exception.finally_exit.add_child(self.flow.exit_point)
1225                 break
1226         else:
1227             if self.flow.block:
1228                 self.flow.block.add_child(self.flow.exit_point)
1229         self.flow.block = None
1230         return node
1231
1232     def visit_BreakStatNode(self, node):
1233         if not self.flow.loops:
1234             #error(node.pos, "break statement not inside loop")
1235             return node
1236         loop = self.flow.loops[-1]
1237         self.mark_position(node)
1238         for exception in loop.exceptions[::-1]:
1239             if exception.finally_enter:
1240                 self.flow.block.add_child(exception.finally_enter)
1241                 if exception.finally_exit:
1242                     exception.finally_exit.add_child(loop.next_block)
1243                 break
1244         else:
1245             self.flow.block.add_child(loop.next_block)
1246         self.flow.block = None
1247         return node
1248
1249     def visit_ContinueStatNode(self, node):
1250         if not self.flow.loops:
1251             #error(node.pos, "continue statement not inside loop")
1252             return node
1253         loop = self.flow.loops[-1]
1254         self.mark_position(node)
1255         for exception in loop.exceptions[::-1]:
1256             if exception.finally_enter:
1257                 self.flow.block.add_child(exception.finally_enter)
1258                 if exception.finally_exit:
1259                     exception.finally_exit.add_child(loop.loop_block)
1260                 break
1261         else:
1262             self.flow.block.add_child(loop.loop_block)
1263         self.flow.block = None
1264         return node
1265
1266     def visit_ComprehensionNode(self, node):
1267         if node.expr_scope:
1268             self.env_stack.append(self.env)
1269             self.env = node.expr_scope
1270         # Skip append node here
1271         self._visit(node.loop)
1272         if node.expr_scope:
1273             self.env = self.env_stack.pop()
1274         return node
1275
1276     def visit_ScopedExprNode(self, node):
1277         if node.expr_scope:
1278             self.env_stack.append(self.env)
1279             self.env = node.expr_scope
1280         self.visitchildren(node)
1281         if node.expr_scope:
1282             self.env = self.env_stack.pop()
1283         return node
1284
1285     def visit_PyClassDefNode(self, node):
1286         self.visitchildren(node, ('dict', 'metaclass',
1287                                   'mkw', 'bases', 'class_result'))
1288         self.flow.mark_assignment(node.target, object_expr_not_none,
1289                                   self.env.lookup(node.name))
1290         self.env_stack.append(self.env)
1291         self.env = node.scope
1292         self.flow.nextblock()
1293         self.visitchildren(node, ('body',))
1294         self.flow.nextblock()
1295         self.env = self.env_stack.pop()
1296         return node
1297
1298     def visit_AmpersandNode(self, node):
1299         if node.operand.is_name:
1300             # Fake assignment to silence warning
1301             self.mark_assignment(node.operand, fake_rhs_expr)
1302         self.visitchildren(node)
1303         return node