FlowControl.py 46 KB
Newer Older
1
# cython: language_level=3str
2
# cython: auto_pickle=True
3

4 5
from __future__ import absolute_import

6
import cython
7
cython.declare(PyrexTypes=object, ExprNodes=object, Nodes=object,
Stefan Behnel's avatar
Stefan Behnel committed
8
               Builtin=object, InternalError=object, error=object, warning=object,
9
               fake_rhs_expr=object, TypedExprNode=object)
10

11 12 13 14 15
from . import Builtin
from . import ExprNodes
from . import Nodes
from . import Options
from . import PyrexTypes
16

17 18
from .Visitor import TreeVisitor, CythonTransform
from .Errors import error, warning, InternalError
19 20
from .Optimize import ConstantFolding

21 22

class TypedExprNode(ExprNodes.ExprNode):
23
    # Used for declaring assignments of a specified type without a known entry.
24
    def __init__(self, type, may_be_none=None, pos=None):
25
        super(TypedExprNode, self).__init__(pos)
26
        self.type = type
27
        self._may_be_none = may_be_none
28

29 30 31
    def may_be_none(self):
        return self._may_be_none != False

32
# Fake rhs to silence "unused variable" warning
33
fake_rhs_expr = TypedExprNode(PyrexTypes.unspecified_type)
34

35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67

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()

68 69 70 71 72 73
        self.i_input = 0
        self.i_output = 0
        self.i_gen = 0
        self.i_kill = 0
        self.i_state = 0

74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97
    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


98
class AssignmentList(object):
99 100 101 102
    def __init__(self):
        self.stats = []


103 104 105 106 107 108 109 110 111 112 113 114
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
    """

115
    def __init__(self):
116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153
        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
Vitja Makarov's avatar
Vitja Makarov committed
154
        return (entry.is_local or entry.is_pyclass_attr or entry.is_arg or
Vitja Makarov's avatar
Vitja Makarov committed
155 156
                entry.from_closure or entry.in_closure or
                entry.error_on_uninitialized)
157

158 159 160
    def is_statically_assigned(self, entry):
        if (entry.is_local and entry.is_variable and
                (entry.type.is_struct_or_union or
161
                 entry.type.is_complex or
162 163 164 165 166 167
                 entry.type.is_array or
                 entry.type.is_cpp_class)):
            # stack allocated structured variable => never uninitialised
            return True
        return False

168 169 170 171 172
    def mark_position(self, node):
        """Mark position, will be used to draw graph nodes."""
        if self.block:
            self.block.positions.add(node.pos[:2])

173
    def mark_assignment(self, lhs, rhs, entry):
174
        if self.block and self.is_tracked(entry):
175 176 177 178 179 180 181 182 183 184 185 186 187 188
            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):
189
            assignment = NameDeletion(node, entry)
190 191 192 193 194 195 196
            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))
197 198 199 200 201
            ## 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)
202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219
            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():
220
                for parent in block.parents:  # Re-parent
221 222 223 224 225 226
                    for child in block.children:
                        parent.add_child(child)
                block.detach()
                unreachable.add(block)
        self.blocks -= unreachable

227 228 229 230
    def initialize(self):
        """Set initial state, map assignments to bits."""
        self.assmts = {}

Stefan Behnel's avatar
Stefan Behnel committed
231
        bit = 1
232 233
        for entry in self.entries:
            assmts = AssignmentList()
Stefan Behnel's avatar
Stefan Behnel committed
234
            assmts.mask = assmts.bit = bit
235
            self.assmts[entry] = assmts
Stefan Behnel's avatar
Stefan Behnel committed
236
            bit <<= 1
237 238 239 240

        for block in self.blocks:
            for stat in block.stats:
                if isinstance(stat, NameAssignment):
Stefan Behnel's avatar
Stefan Behnel committed
241
                    stat.bit = bit
242 243
                    assmts = self.assmts[stat.entry]
                    assmts.stats.append(stat)
Stefan Behnel's avatar
Stefan Behnel committed
244 245
                    assmts.mask |= bit
                    bit <<= 1
246 247 248 249 250 251 252 253 254 255 256 257 258

        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

259
        for assmts in self.assmts.values():
260 261 262 263 264 265 266
            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:
267 268 269
            if self.is_statically_assigned(entry):
                ret.add(StaticAssignment(entry))
            elif entry.from_closure:
270 271 272
                ret.add(Unknown)
            else:
                ret.add(Uninitialized)
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
        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

293 294 295 296 297

class LoopDescr(object):
    def __init__(self, next_block, loop_block):
        self.next_block = next_block
        self.loop_block = loop_block
298
        self.exceptions = []
299

300

301 302 303 304 305 306 307 308 309 310 311 312 313
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

314

315 316
class NameAssignment(object):
    def __init__(self, lhs, rhs, entry):
317 318
        if lhs.cf_state is None:
            lhs.cf_state = set()
319 320 321 322 323
        self.lhs = lhs
        self.rhs = rhs
        self.entry = entry
        self.pos = lhs.pos
        self.refs = set()
324
        self.is_arg = False
325
        self.is_deletion = False
326
        self.inferred_type = None
327 328 329 330

    def __repr__(self):
        return '%s(entry=%r)' % (self.__class__.__name__, self.entry)

331 332 333
    def infer_type(self):
        self.inferred_type = self.rhs.infer_type(self.entry.scope)
        return self.inferred_type
334

335 336 337 338 339 340 341 342
    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
343

344

345 346 347 348 349 350 351 352 353 354 355
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)

356
    def infer_type(self):
357 358
        return self.entry.type

359 360
    def type_dependencies(self):
        return ()
361 362


363
class Argument(NameAssignment):
Vitja Makarov's avatar
Vitja Makarov committed
364 365 366
    def __init__(self, lhs, rhs, entry):
        NameAssignment.__init__(self, lhs, rhs, entry)
        self.is_arg = True
367

368 369 370 371 372 373

class NameDeletion(NameAssignment):
    def __init__(self, lhs, entry):
        NameAssignment.__init__(self, lhs, lhs, entry)
        self.is_deletion = True

374 375
    def infer_type(self):
        inferred_type = self.rhs.infer_type(self.entry.scope)
376
        if (not inferred_type.is_pyobject
377 378 379
                and inferred_type.can_coerce_to_pyobject(self.entry.scope)
                and not inferred_type.is_cyp_class):
            # do not coerce cypclass to pyobject just for a del statement
380
            return PyrexTypes.py_object_type
381
        self.inferred_type = inferred_type
382 383
        return inferred_type

384

385
class Uninitialized(object):
386 387 388 389 390 391
    """Definitely not initialised yet."""


class Unknown(object):
    """Coming from outer closure, might be initialised or not."""

392 393 394

class NameReference(object):
    def __init__(self, node, entry):
395 396
        if node.cf_state is None:
            node.cf_state = set()
397 398 399 400 401 402 403 404
        self.node = node
        self.entry = entry
        self.pos = node.pos

    def __repr__(self):
        return '%s(entry=%r)' % (self.__class__.__name__, self.entry)


405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421
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
422 423 424
        elif Unknown in state:
            state.discard(Unknown)
            self.cf_maybe_null = True
425 426 427
        else:
            if len(state) == 1:
                self.is_single = True
428 429 430
        # XXX: Remove fake_rhs_expr
        super(ControlFlowState, self).__init__(
            [i for i in state if i.rhs is not fake_rhs_expr])
431 432 433 434 435

    def one(self):
        return self[0]


436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459
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]
460
        if srcdescr not in self.sources:
461 462 463 464 465 466 467 468 469 470 471 472 473 474 475
            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')

476

477 478 479 480 481 482 483 484 485 486 487 488 489 490
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):
491 492
                        label += '\n %s [%s %s]' % (
                            stat.entry.name, 'deletion' if stat.is_deletion else 'definition', stat.pos[1])
493 494
                    elif isinstance(stat, NameReference):
                        if stat.entry:
495
                            label += '\n %s [reference %s]' % (stat.entry.name, stat.pos[1])
496 497 498 499 500 501 502 503 504 505
            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')

506

507
class MessageCollection(object):
508
    """Collect error/warnings messages first then sort"""
509
    def __init__(self):
510
        self.messages = set()
511 512

    def error(self, pos, message):
513
        self.messages.add((pos, True, message))
514 515

    def warning(self, pos, message):
516
        self.messages.add((pos, False, message))
517

518
    def report(self):
519
        for pos, is_error, message in sorted(self.messages):
520 521 522 523
            if is_error:
                error(pos, message)
            else:
                warning(pos, message, 2)
524 525 526


def check_definitions(flow, compiler_directives):
527 528
    flow.initialize()
    flow.reaching_definitions()
529 530 531

    # Track down state
    assignments = set()
532 533 534 535
    # Node to entry map
    references = {}
    assmt_nodes = set()

536
    for block in flow.blocks:
537
        i_state = block.i_input
538
        for stat in block.stats:
539 540
            i_assmts = flow.assmts[stat.entry]
            state = flow.map_one(i_state, stat.entry)
541
            if isinstance(stat, NameAssignment):
542
                stat.lhs.cf_state.update(state)
543
                assmt_nodes.add(stat.lhs)
544
                i_state = i_state & ~i_assmts.mask
545
                if stat.is_deletion:
546
                    i_state |= i_assmts.bit
547 548
                else:
                    i_state |= stat.bit
549
                assignments.add(stat)
550 551
                if stat.rhs is not fake_rhs_expr:
                    stat.entry.cf_assignments.append(stat)
552
            elif isinstance(stat, NameReference):
553
                references[stat.node] = stat.entry
554
                stat.entry.cf_references.append(stat)
555
                stat.node.cf_state.update(state)
556 557 558
                ## if not stat.node.allow_null:
                ##     i_state &= ~i_assmts.bit
                ## # after successful read, the state is known to be initialised
559
                state.discard(Uninitialized)
560
                state.discard(Unknown)
561 562
                for assmt in state:
                    assmt.refs.add(stat)
563 564

    # Check variable usage
565
    warn_maybe_uninitialized = compiler_directives['warn.maybe_uninitialized']
566 567 568 569
    warn_unused_result = compiler_directives['warn.unused_result']
    warn_unused = compiler_directives['warn.unused']
    warn_unused_arg = compiler_directives['warn.unused_arg']

570 571 572 573 574 575 576 577 578 579
    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
580 581
        elif Unknown in node.cf_state:
            node.cf_maybe_null = True
582 583 584 585 586
        else:
            node.cf_is_null = False
            node.cf_maybe_null = False

    # Find uninitialized references and cf-hints
587
    for node, entry in references.items():
588 589
        if Uninitialized in node.cf_state:
            node.cf_maybe_null = True
590 591
            if not entry.from_closure and len(node.cf_state) == 1:
                node.cf_is_null = True
592
            if (node.allow_null or entry.from_closure
593 594
                    or entry.is_pyclass_attr or entry.type.is_error):
                pass  # Can be uninitialized here
595
            elif node.cf_is_null:
596 597 598
                if entry.error_on_uninitialized or (
                        Options.error_on_uninitialized and (
                        entry.type.is_pyobject or entry.type.is_unspecified)):
599 600 601 602
                    messages.error(
                        node.pos,
                        "local variable '%s' referenced before assignment"
                        % entry.name)
603 604 605 606 607
                else:
                    messages.warning(
                        node.pos,
                        "local variable '%s' referenced before assignment"
                        % entry.name)
608 609 610 611 612
            elif warn_maybe_uninitialized:
                messages.warning(
                    node.pos,
                    "local variable '%s' might be referenced before assignment"
                    % entry.name)
613 614 615 616 617 618
        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
619 620 621 622 623
        else:
            node.cf_is_null = False
            node.cf_maybe_null = False

    # Unused result
624
    for assmt in assignments:
Vitja Makarov's avatar
Vitja Makarov committed
625
        if (not assmt.refs and not assmt.entry.is_pyclass_attr
626
                and not assmt.entry.in_closure):
627
            if assmt.entry.cf_references and warn_unused_result:
628
                if assmt.is_arg:
Vitja Makarov's avatar
Vitja Makarov committed
629 630
                    messages.warning(assmt.pos, "Unused argument value '%s'" %
                                     assmt.entry.name)
631
                else:
Vitja Makarov's avatar
Vitja Makarov committed
632 633
                    messages.warning(assmt.pos, "Unused result in '%s'" %
                                     assmt.entry.name)
634
            assmt.lhs.cf_used = False
635

636
    # Unused entries
637
    for entry in flow.entries:
638
        if (not entry.cf_references
639
                and not entry.is_pyclass_attr):
640
            if entry.name != '_' and not entry.name.startswith('unused'):
641 642 643 644 645 646 647 648 649
                # '_' 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)
650
            entry.cf_used = False
651

652
    messages.report()
653

654
    for node in assmt_nodes:
655
        node.cf_state = ControlFlowState(node.cf_state)
656
    for node in references:
657
        node.cf_state = ControlFlowState(node.cf_state)
658

659 660 661 662 663 664 665

class AssignmentCollector(TreeVisitor):
    def __init__(self):
        super(AssignmentCollector, self).__init__()
        self.assignments = []

    def visit_Node(self):
666
        self._visitchildren(self, None)
667 668 669 670 671 672 673 674 675

    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))


676
class ControlFlowAnalysis(CythonTransform):
677

678
    def visit_ModuleNode(self, node):
679 680
        dot_output = self.current_directives['control_flow.dot_output']
        self.gv_ctx = GVContext() if dot_output else None
681
        self.constant_folder = ConstantFolding()
682

683
        # Set of NameNode reductions
Robert Bradshaw's avatar
Robert Bradshaw committed
684
        self.reductions = set()
685

686
        self.in_inplace_assignment = False
687 688 689 690
        self.env_stack = []
        self.env = node.scope
        self.stack = []
        self.flow = ControlFlow()
691
        self.object_expr = TypedExprNode(PyrexTypes.py_object_type, may_be_none=True)
692 693
        self.visitchildren(node)

694 695
        check_definitions(self.flow, self.current_directives)

696 697
        if dot_output:
            annotate_defs = self.current_directives['control_flow.dot_annotate_defs']
698
            with open(dot_output, 'wt') as fp:
699 700 701 702
                self.gv_ctx.render(fp, 'module', annotate_defs=annotate_defs)
        return node

    def visit_FuncDefNode(self, node):
703 704 705
        for arg in node.args:
            if arg.default:
                self.visitchildren(arg)
706
        self.visitchildren(node, ('decorators',))
707 708 709
        self.env_stack.append(self.env)
        self.env = node.local_scope
        self.stack.append(self.flow)
710
        self.flow = ControlFlow()
711

712 713 714 715 716
        # Collect all entries
        for entry in node.local_scope.entries.values():
            if self.flow.is_tracked(entry):
                self.flow.entries.add(entry)

717 718 719 720
        self.mark_position(node)
        # Function body block
        self.flow.nextblock()

721
        for arg in node.args:
722
            self._visit(arg)
723 724
        if node.star_arg:
            self.flow.mark_argument(node.star_arg,
725 726
                                    TypedExprNode(Builtin.tuple_type,
                                                  may_be_none=False),
727 728 729
                                    node.star_arg.entry)
        if node.starstar_arg:
            self.flow.mark_argument(node.starstar_arg,
730 731
                                    TypedExprNode(Builtin.dict_type,
                                                  may_be_none=False),
732
                                    node.starstar_arg.entry)
733
        self._visit(node.body)
Vitja Makarov's avatar
Vitja Makarov committed
734 735
        # Workaround for generators
        if node.is_generator:
736
            self._visit(node.gbody.body)
737 738 739 740 741 742 743 744 745 746

        # 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)

747 748
        if self.gv_ctx is not None:
            self.gv_ctx.add(GV(node.local_scope.name, self.flow))
749 750 751 752 753 754 755 756 757

        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)

Vitja Makarov's avatar
Vitja Makarov committed
758 759 760
    def visit_GeneratorBodyDefNode(self, node):
        return node

761 762 763 764 765 766 767 768 769 770 771 772
    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:
773
            rhs = self.object_expr
774
        if lhs.is_name:
775 776 777 778
            if lhs.entry is not None:
                entry = lhs.entry
            else:
                entry = self.env.lookup(lhs.name)
779
            if entry is None:  # TODO: This shouldn't happen...
780
                return
781
            self.flow.mark_assignment(lhs, rhs, entry)
782 783
        elif lhs.is_sequence_constructor:
            for i, arg in enumerate(lhs.args):
784 785 786 787 788
                if arg.is_starred:
                    # "a, *b = x" assigns a list to "b"
                    item_node = TypedExprNode(Builtin.list_type, may_be_none=False, pos=arg.pos)
                elif rhs is self.object_expr:
                    item_node = rhs
789
                else:
790
                    item_node = rhs.inferable_item_node(i)
791
                self.mark_assignment(arg, item_node)
792
        else:
793
            self._visit(lhs)
794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811

        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

812
    def visit_AssignmentNode(self, node):
813
        raise InternalError("Unhandled assignment node %s" % type(node))
814

815
    def visit_SingleAssignmentNode(self, node):
816
        self._visit(node.rhs)
817
        self.mark_assignment(node.lhs, node.rhs)
818 819 820
        return node

    def visit_CascadedAssignmentNode(self, node):
821
        self._visit(node.rhs)
822 823 824 825 826 827 828 829
        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:
830
            self._visit(rhs)
831 832 833 834 835
        for lhs, rhs in collector.assignments:
            self.mark_assignment(lhs, rhs)
        return node

    def visit_InPlaceAssignmentNode(self, node):
Mark Florisson's avatar
Mark Florisson committed
836
        self.in_inplace_assignment = True
837
        self.visitchildren(node)
Mark Florisson's avatar
Mark Florisson committed
838
        self.in_inplace_assignment = False
839
        self.mark_assignment(node.lhs, self.constant_folder(node.create_binop_node()))
840 841 842 843 844
        return node

    def visit_DelStatNode(self, node):
        for arg in node.args:
            if arg.is_name:
Vitja Makarov's avatar
Vitja Makarov committed
845 846
                entry = arg.entry or self.env.lookup(arg.name)
                if entry.in_closure or entry.from_closure:
Vitja Makarov's avatar
Vitja Makarov committed
847 848 849
                    error(arg.pos,
                          "can not delete variable '%s' "
                          "referenced in nested scope" % entry.name)
850 851
                if not node.ignore_nonexisting:
                    self._visit(arg)  # mark reference
Vitja Makarov's avatar
Vitja Makarov committed
852
                self.flow.mark_deletion(arg, entry)
853 854
            else:
                self._visit(arg)
855 856 857 858
        return node

    def visit_CArgDeclNode(self, node):
        entry = self.env.lookup(node.name)
859
        if entry:
860
            may_be_none = not node.not_none
861 862
            self.flow.mark_argument(
                node, TypedExprNode(entry.type, may_be_none), entry)
863 864 865 866 867 868 869
        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)
Mark Florisson's avatar
Mark Florisson committed
870 871 872 873 874

                if entry in self.reductions and not self.in_inplace_assignment:
                    error(node.pos,
                          "Cannot read reduction variable in loop body")

875 876 877
        return node

    def visit_StatListNode(self, node):
878 879
        if self.flow.block:
            for stat in node.stats:
880
                self._visit(stat)
881 882 883
                if not self.flow.block:
                    stat.is_terminator = True
                    break
884 885 886 887 888 889 890
        return node

    def visit_Node(self, node):
        self.visitchildren(node)
        self.mark_position(node)
        return node

891 892 893 894 895 896
    def visit_SizeofVarNode(self, node):
        return node

    def visit_TypeidNode(self, node):
        return node

897 898 899 900 901 902
    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)
903
            self._visit(clause.condition)
904
            self.flow.nextblock()
905
            self._visit(clause.body)
906 907 908 909 910
            if self.flow.block:
                self.flow.block.add_child(next_block)
        # Else clause
        if node.else_clause:
            self.flow.nextblock(parent=parent)
911
            self._visit(node.else_clause)
912 913 914 915 916 917 918 919 920 921 922
            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

923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942
    def visit_AssertStatNode(self, node):
        """Essentially an if-condition that wraps a RaiseStatNode.
        """
        self.mark_position(node)
        next_block = self.flow.newblock()
        parent = self.flow.block
        # failure case
        parent = self.flow.nextblock(parent)
        self._visit(node.condition)
        self.flow.nextblock()
        self._visit(node.exception)
        if self.flow.block:
            self.flow.block.add_child(next_block)
        parent.add_child(next_block)
        if next_block.parents:
            self.flow.block = next_block
        else:
            self.flow.block = None
        return node

943 944 945 946 947
    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))
948 949
        if node.condition:
            self._visit(node.condition)
950 951
        # Body block
        self.flow.nextblock()
952
        self._visit(node.body)
953
        self.flow.loops.pop()
954 955 956 957 958 959 960
        # 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)
961
            self._visit(node.else_clause)
962 963 964 965
            if self.flow.block:
                self.flow.block.add_child(next_block)
        else:
            condition_block.add_child(next_block)
966 967 968 969 970

        if next_block.parents:
            self.flow.block = next_block
        else:
            self.flow.block = None
971 972
        return node

973 974 975 976
    def mark_forloop_target(self, node):
        # TODO: Remove redundancy with range optimization...
        is_special = False
        sequence = node.iterator.sequence
977
        target = node.target
978 979 980
        if isinstance(sequence, ExprNodes.SimpleCallNode):
            function = sequence.function
            if sequence.self is None and function.is_name:
981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997
                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]
998 999 1000
        if isinstance(sequence, ExprNodes.SimpleCallNode):
            function = sequence.function
            if sequence.self is None and function.is_name:
1001 1002 1003 1004 1005 1006 1007
                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:
1008
                            self.mark_assignment(target, self.constant_folder(
1009 1010 1011
                                ExprNodes.binop_node(node.pos,
                                                     '+',
                                                     sequence.args[0],
1012
                                                     sequence.args[2])))
1013 1014 1015 1016 1017 1018 1019

        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.
1020 1021

            self.mark_assignment(target, node.item)
1022

1023 1024 1025
    def visit_AsyncForStatNode(self, node):
        return self.visit_ForInStatNode(node)

1026 1027 1028 1029 1030
    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))
1031
        self._visit(node.iterator)
1032 1033
        # Target assignment
        self.flow.nextblock()
1034 1035

        if isinstance(node, Nodes.ForInStatNode):
1036
            self.mark_forloop_target(node)
1037 1038 1039
        elif isinstance(node, Nodes.AsyncForStatNode):
            # not entirely correct, but good enough for now
            self.mark_assignment(node.target, node.item)
1040
        else:  # Parallel
1041
            self.mark_assignment(node.target)
Mark Florisson's avatar
Mark Florisson committed
1042

1043
        # Body block
Mark Florisson's avatar
Mark Florisson committed
1044 1045 1046 1047
        if isinstance(node, Nodes.ParallelRangeNode):
            # In case of an invalid
            self._delete_privates(node, exclude=node.target.entry)

1048
        self.flow.nextblock()
1049
        self._visit(node.body)
1050
        self.flow.loops.pop()
Mark Florisson's avatar
Mark Florisson committed
1051

1052 1053 1054 1055 1056 1057
        # 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)
1058
            self._visit(node.else_clause)
1059 1060 1061 1062
            if self.flow.block:
                self.flow.block.add_child(next_block)
        else:
            condition_block.add_child(next_block)
1063 1064 1065 1066 1067

        if next_block.parents:
            self.flow.block = next_block
        else:
            self.flow.block = None
1068 1069
        return node

Mark Florisson's avatar
Mark Florisson committed
1070 1071 1072 1073 1074
    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)

1075
    def visit_ParallelRangeNode(self, node):
Mark Florisson's avatar
Mark Florisson committed
1076 1077 1078 1079 1080
        reductions = self.reductions

        # if node.target is None or not a NameNode, an error will have
        # been previously issued
        if hasattr(node.target, 'entry'):
Robert Bradshaw's avatar
Robert Bradshaw committed
1081
            self.reductions = set(reductions)
Mark Florisson's avatar
Mark Florisson committed
1082 1083 1084 1085 1086 1087 1088

            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)

1089 1090
            node = self.visit_ForInStatNode(node)

Mark Florisson's avatar
Mark Florisson committed
1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101
        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)

1102 1103
        return node

1104 1105 1106 1107 1108
    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))
1109 1110
        self._visit(node.bound1)
        self._visit(node.bound2)
1111
        if node.step is not None:
1112
            self._visit(node.step)
1113 1114
        # Target assignment
        self.flow.nextblock()
1115 1116
        self.mark_assignment(node.target, node.bound1)
        if node.step is not None:
1117 1118
            self.mark_assignment(node.target, self.constant_folder(
                ExprNodes.binop_node(node.pos, '+', node.bound1, node.step)))
1119 1120
        # Body block
        self.flow.nextblock()
1121
        self._visit(node.body)
1122
        self.flow.loops.pop()
1123 1124 1125 1126 1127 1128
        # 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)
1129
            self._visit(node.else_clause)
1130 1131 1132 1133
            if self.flow.block:
                self.flow.block.add_child(next_block)
        else:
            condition_block.add_child(next_block)
1134 1135 1136 1137 1138

        if next_block.parents:
            self.flow.block = next_block
        else:
            self.flow.block = None
1139 1140 1141
        return node

    def visit_LoopNode(self, node):
1142
        raise InternalError("Generic loops are not supported")
1143

1144
    def visit_WithTargetAssignmentStatNode(self, node):
1145
        self.mark_assignment(node.lhs, node.with_node.enter_call)
1146 1147
        return node

1148
    def visit_WithStatNode(self, node):
1149 1150 1151
        self._visit(node.manager)
        self._visit(node.enter_call)
        self._visit(node.body)
1152
        return node
1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165

    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)
1166
        self.flow.nextblock()
1167
        self._visit(node.body)
1168 1169 1170 1171 1172 1173
        self.flow.exceptions.pop()

        # After exception
        if self.flow.block:
            if node.else_clause:
                self.flow.nextblock()
1174
                self._visit(node.else_clause)
1175 1176 1177 1178 1179 1180 1181
            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:
1182
                    self._visit(pattern)
1183 1184 1185 1186 1187
            else:
                # TODO: handle * pattern
                pass
            entry_point = self.flow.newblock(parent=self.flow.block)
            self.flow.nextblock()
1188 1189
            if clause.target:
                self.mark_assignment(clause.target)
1190
            self._visit(clause.body)
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208
            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
1209
        self._visit(node.finally_except_clause)
1210

1211 1212 1213
        if self.flow.block and self.flow.exceptions:
            self.flow.block.add_child(self.flow.exceptions[-1].entry_point)

1214 1215 1216
        # Normal execution
        finally_enter = self.flow.newblock()
        self.flow.block = finally_enter
1217
        self._visit(node.finally_clause)
1218 1219
        finally_exit = self.flow.block

1220 1221 1222 1223
        descr = ExceptionDescr(entry_point, finally_enter, finally_exit)
        self.flow.exceptions.append(descr)
        if self.flow.loops:
            self.flow.loops[-1].exceptions.append(descr)
1224
        self.flow.block = body_block
1225
        body_block.add_child(entry_point)
1226
        self.flow.nextblock()
1227
        self._visit(node.body)
1228
        self.flow.exceptions.pop()
1229 1230
        if self.flow.loops:
            self.flow.loops[-1].exceptions.pop()
1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241

        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)
Vitja Makarov's avatar
Vitja Makarov committed
1242
        self.visitchildren(node)
1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258
        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)

1259 1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270
        outer_exception_handlers = iter(self.flow.exceptions[::-1])
        for handler in outer_exception_handlers:
            if handler.finally_enter:
                self.flow.block.add_child(handler.finally_enter)
                if handler.finally_exit:
                    # 'return' goes to function exit, or to the next outer 'finally' clause
                    exit_point = self.flow.exit_point
                    for next_handler in outer_exception_handlers:
                        if next_handler.finally_enter:
                            exit_point = next_handler.finally_enter
                            break
                    handler.finally_exit.add_child(exit_point)
1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283
                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)
1284
        for exception in loop.exceptions[::-1]:
1285 1286 1287 1288 1289 1290 1291 1292 1293 1294 1295 1296 1297 1298 1299 1300
            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)
1301
        for exception in loop.exceptions[::-1]:
1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 1312 1313 1314 1315 1316
            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
1317
        self._visit(node.loop)
1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331
        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):
1332 1333
        self.visitchildren(node, ('dict', 'metaclass',
                                  'mkw', 'bases', 'class_result'))
1334
        self.flow.mark_assignment(node.target, node.classobj,
1335
                                  self.env.lookup(node.target.name))
1336 1337 1338
        self.env_stack.append(self.env)
        self.env = node.scope
        self.flow.nextblock()
1339 1340
        if node.doc_node:
            self.flow.mark_assignment(node.doc_node, fake_rhs_expr, node.doc_node.entry)
1341
        self.visitchildren(node, ('body',))
1342 1343 1344
        self.flow.nextblock()
        self.env = self.env_stack.pop()
        return node
1345 1346 1347 1348

    def visit_AmpersandNode(self, node):
        if node.operand.is_name:
            # Fake assignment to silence warning
1349
            self.mark_assignment(node.operand, fake_rhs_expr)
1350 1351
        self.visitchildren(node)
        return node