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 1304
