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