1 #!/usr/bin/env python 2 3 """ 4 Common functions. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 7 2017, 2018, 2019 Paul Boddie <paul@boddie.org.uk> 8 9 This program is free software; you can redistribute it and/or modify it under 10 the terms of the GNU General Public License as published by the Free Software 11 Foundation; either version 3 of the License, or (at your option) any later 12 version. 13 14 This program is distributed in the hope that it will be useful, but WITHOUT 15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 16 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 17 details. 18 19 You should have received a copy of the GNU General Public License along with 20 this program. If not, see <http://www.gnu.org/licenses/>. 21 """ 22 23 from compiler.transformer import Transformer 24 from errors import InspectError 25 from os import listdir, makedirs, remove 26 from os.path import exists, getmtime, isdir, join, split 27 from results import ConstantValueRef, LiteralSequenceRef, NameRef 28 import compiler.ast 29 30 class CommonOutput: 31 32 "Common output functionality." 33 34 def check_output(self, options=None): 35 36 "Check the existing output and remove it if irrelevant." 37 38 if not exists(self.output): 39 makedirs(self.output) 40 41 details = self.importer.get_cache_details() 42 recorded_details = self.get_output_details() 43 44 # Combine cache details with any options. 45 46 full_details = options and (details + " " + options) or details 47 48 if recorded_details != full_details: 49 self.remove_output() 50 51 writefile(self.get_output_details_filename(), full_details) 52 53 def get_output_details_filename(self): 54 55 "Return the output details filename." 56 57 return join(self.output, "$details") 58 59 def get_output_details(self): 60 61 "Return details of the existing output." 62 63 details_filename = self.get_output_details_filename() 64 65 if not exists(details_filename): 66 return None 67 else: 68 return readfile(details_filename) 69 70 def remove_output(self, dirname=None): 71 72 "Remove the output." 73 74 dirname = dirname or self.output 75 76 for filename in listdir(dirname): 77 path = join(dirname, filename) 78 if isdir(path): 79 self.remove_output(path) 80 else: 81 remove(path) 82 83 def copy(source, target, only_if_newer=True): 84 85 "Copy a text file from 'source' to 'target'." 86 87 if isdir(target): 88 target = join(target, split(source)[-1]) 89 90 if only_if_newer and not is_newer(source, target): 91 return 92 93 infile = open(source) 94 outfile = open(target, "w") 95 96 try: 97 outfile.write(infile.read()) 98 finally: 99 outfile.close() 100 infile.close() 101 102 def is_newer(source, target): 103 104 "Return whether 'source' is newer than 'target'." 105 106 if exists(target): 107 target_mtime = getmtime(target) 108 source_mtime = getmtime(source) 109 return source_mtime > target_mtime 110 111 return True 112 113 class CommonModule: 114 115 "A common module representation." 116 117 def __init__(self, name, importer): 118 119 """ 120 Initialise this module with the given 'name' and an 'importer' which is 121 used to provide access to other modules when required. 122 """ 123 124 self.name = name 125 self.importer = importer 126 self.filename = None 127 128 # Inspection-related attributes. 129 130 self.astnode = None 131 self.encoding = None 132 self.temp = {} 133 self.lambdas = {} 134 135 # Constants, literals and values. 136 137 self.constants = {} 138 self.constant_values = {} 139 self.literals = {} 140 self.literal_types = {} 141 142 # Nested namespaces. 143 144 self.namespace_path = [] 145 self.in_function = False 146 147 # Retain the assignment value expression and track invocations. 148 149 self.in_assignment = None 150 self.in_invocation = None 151 152 # Attribute chain state management. 153 154 self.attrs = [] 155 self.chain_assignment = [] 156 self.chain_invocation = [] 157 158 def __repr__(self): 159 return "CommonModule(%r, %r)" % (self.name, self.importer) 160 161 def parse_file(self, filename): 162 163 "Parse the file with the given 'filename', initialising attributes." 164 165 self.filename = filename 166 167 # Use the Transformer directly to obtain encoding information. 168 169 t = Transformer() 170 f = open(filename) 171 172 try: 173 self.astnode = t.parsesuite(f.read() + "\n") 174 self.encoding = t.encoding 175 finally: 176 f.close() 177 178 # Module-relative naming. 179 180 def get_global_path(self, name): 181 return "%s.%s" % (self.name, name) 182 183 def get_namespace_path(self): 184 return ".".join([self.name] + self.namespace_path) 185 186 def get_object_path(self, name): 187 return ".".join([self.name] + self.namespace_path + [name]) 188 189 # Namespace management. 190 191 def enter_namespace(self, name): 192 193 "Enter the namespace having the given 'name'." 194 195 self.namespace_path.append(name) 196 197 def exit_namespace(self): 198 199 "Exit the current namespace." 200 201 self.namespace_path.pop() 202 203 # Constant reference naming. 204 205 def get_constant_name(self, value, value_type, encoding=None): 206 207 """ 208 Add a new constant to the current namespace for 'value' with 209 'value_type'. 210 """ 211 212 path = self.get_namespace_path() 213 init_item(self.constants, path, dict) 214 return "$c%d" % add_counter_item(self.constants[path], (value, value_type, encoding)) 215 216 # Literal reference naming. 217 218 def get_literal_name(self): 219 220 "Add a new literal to the current namespace." 221 222 path = self.get_namespace_path() 223 init_item(self.literals, path, lambda: 0) 224 return "$C%d" % self.literals[path] 225 226 def next_literal(self): 227 self.literals[self.get_namespace_path()] += 1 228 229 # Temporary variable naming. 230 231 def get_temporary_name(self): 232 path = self.get_namespace_path() 233 init_item(self.temp, path, lambda: 0) 234 return "$t%d" % self.temp[path] 235 236 def next_temporary(self): 237 self.temp[self.get_namespace_path()] += 1 238 239 # Arbitrary function naming. 240 241 def get_lambda_name(self): 242 path = self.get_namespace_path() 243 init_item(self.lambdas, path, lambda: 0) 244 name = "$l%d" % self.lambdas[path] 245 self.lambdas[path] += 1 246 return name 247 248 def reset_lambdas(self): 249 self.lambdas = {} 250 251 # Constant and literal recording. 252 253 def get_constant_value(self, value, literals=None): 254 255 """ 256 Encode the 'value' if appropriate, returning a value, a typename and any 257 encoding. 258 """ 259 260 if isinstance(value, unicode): 261 return value.encode("utf-8"), "unicode", self.encoding 262 263 # Attempt to convert plain strings to text. 264 265 elif isinstance(value, str) and self.encoding: 266 try: 267 return get_string_details(literals, self.encoding) 268 except UnicodeDecodeError: 269 pass 270 271 return value, value.__class__.__name__, None 272 273 def get_constant_reference(self, ref, value, encoding=None): 274 275 """ 276 Return a constant reference for the given 'ref' type and 'value', with 277 the optional 'encoding' applying to text values. 278 """ 279 280 constant_name = self.get_constant_name(value, ref.get_origin(), encoding) 281 282 # Return a reference for the constant. 283 284 objpath = self.get_object_path(constant_name) 285 name_ref = ConstantValueRef(constant_name, ref.instance_of(objpath), value) 286 287 # Record the value and type for the constant. 288 289 self._reserve_constant(objpath, name_ref.value, name_ref.get_origin(), encoding) 290 return name_ref 291 292 def reserve_constant(self, objpath, value, origin, encoding=None): 293 294 """ 295 Reserve a constant within 'objpath' with the given 'value' and having a 296 type with the given 'origin', with the optional 'encoding' applying to 297 text values. 298 """ 299 300 constant_name = self.get_constant_name(value, origin) 301 objpath = self.get_object_path(constant_name) 302 self._reserve_constant(objpath, value, origin, encoding) 303 304 def _reserve_constant(self, objpath, value, origin, encoding): 305 306 """ 307 Store a constant for 'objpath' with the given 'value' and 'origin', with 308 the optional 'encoding' applying to text values. 309 """ 310 311 self.constant_values[objpath] = value, origin, encoding 312 313 def get_literal_reference(self, name, ref, items, cls): 314 315 """ 316 Return a literal reference for the given type 'name', literal 'ref', 317 node 'items' and employing the given 'cls' as the class of the returned 318 reference object. 319 """ 320 321 # Construct an invocation using the items as arguments. 322 323 typename = "$L%s" % name 324 325 invocation = compiler.ast.CallFunc( 326 compiler.ast.Name(typename), 327 items 328 ) 329 330 # Get a name for the actual literal. 331 332 instname = self.get_literal_name() 333 self.next_literal() 334 335 # Record the type for the literal. 336 337 objpath = self.get_object_path(instname) 338 self.literal_types[objpath] = ref.get_origin() 339 340 # Return a wrapper for the invocation exposing the items. 341 342 return cls( 343 instname, 344 ref.instance_of(), 345 self.process_structure_node(invocation), 346 invocation.args 347 ) 348 349 # Node handling. 350 351 def process_structure(self, node): 352 353 """ 354 Within the given 'node', process the program structure. 355 356 During inspection, this will process global declarations, adjusting the 357 module namespace, and import statements, building a module dependency 358 hierarchy. 359 360 During translation, this will consult deduced program information and 361 output translated code. 362 """ 363 364 l = [] 365 for n in node.getChildNodes(): 366 l.append(self.process_structure_node(n)) 367 return l 368 369 def process_augassign_node(self, n): 370 371 "Process the given augmented assignment node 'n'." 372 373 op = operator_functions[n.op] 374 375 if isinstance(n.node, compiler.ast.Getattr): 376 target = compiler.ast.AssAttr(n.node.expr, n.node.attrname, "OP_ASSIGN") 377 elif isinstance(n.node, compiler.ast.Name): 378 target = compiler.ast.AssName(n.node.name, "OP_ASSIGN") 379 else: 380 target = n.node 381 382 assignment = compiler.ast.Assign( 383 [target], 384 compiler.ast.CallFunc( 385 compiler.ast.Name("$op%s" % op), 386 [n.node, n.expr])) 387 388 return self.process_structure_node(assignment) 389 390 def process_assignment_for_object(self, original_name, source): 391 392 """ 393 Return an assignment operation making 'original_name' refer to the given 394 'source'. 395 """ 396 397 assignment = compiler.ast.Assign( 398 [compiler.ast.AssName(original_name, "OP_ASSIGN")], 399 source 400 ) 401 402 return self.process_structure_node(assignment) 403 404 def process_assignment_node_items(self, n, expr): 405 406 """ 407 Process the given assignment node 'n' whose children are to be assigned 408 items of 'expr'. 409 """ 410 411 name_ref = self.process_structure_node(expr) 412 413 # Either unpack the items and present them directly to each assignment 414 # node. 415 416 if isinstance(name_ref, LiteralSequenceRef) and \ 417 self.process_literal_sequence_items(n, name_ref): 418 419 pass 420 421 # Or have the assignment nodes access each item via the sequence API. 422 423 else: 424 self.process_assignment_node_items_by_position(n, expr, name_ref) 425 426 def process_assignment_node_items_by_position(self, n, expr, name_ref): 427 428 """ 429 Process the given sequence assignment node 'n', converting the node to 430 the separate assignment of each target using positional access on a 431 temporary variable representing the sequence. Use 'expr' as the assigned 432 value and 'name_ref' as the reference providing any existing temporary 433 variable. 434 """ 435 436 statements = [] 437 438 # Employ existing names to access the sequence. 439 # Literal sequences do not provide names of accessible objects. 440 441 if isinstance(name_ref, NameRef) and not isinstance(name_ref, LiteralSequenceRef): 442 temp = name_ref.name 443 444 # For other expressions, create a temporary name to reference the items. 445 446 else: 447 temp = self.get_temporary_name() 448 self.next_temporary() 449 450 statements.append( 451 compiler.ast.Assign([compiler.ast.AssName(temp, "OP_ASSIGN")], expr) 452 ) 453 454 # Generate a test for the length of the expression object. 455 456 statements.append(compiler.ast.Discard( 457 compiler.ast.CallFunc(compiler.ast.Name("$seq_test_length"), 458 [compiler.ast.Name(temp), compiler.ast.Const(len(n.nodes))]))) 459 460 # Assign the items to the target nodes. 461 462 for i, node in enumerate(n.nodes): 463 statements.append( 464 compiler.ast.Assign([node], compiler.ast.CallFunc( 465 compiler.ast.Getattr(compiler.ast.Name(temp), 466 "__get_single_item_unchecked__", 467 privileged=True), 468 [compiler.ast.Const(i, str(i))])) 469 ) 470 471 return self.process_structure_node(compiler.ast.Stmt(statements)) 472 473 def process_literal_sequence_items(self, n, name_ref): 474 475 """ 476 Process the given assignment node 'n', obtaining from the given 477 'name_ref' the items to be assigned to the assignment targets. 478 479 Return whether this method was able to process the assignment node as 480 a sequence of direct assignments. 481 """ 482 483 if len(n.nodes) == len(name_ref.items): 484 assigned_names, count = get_names_from_nodes(n.nodes) 485 accessed_names, _count = get_names_from_nodes(name_ref.items) 486 487 # Only assign directly between items if all assigned names are 488 # plain names (not attribute assignments), and if the assigned names 489 # do not appear in the accessed names. 490 491 if len(assigned_names) == count and \ 492 not assigned_names.intersection(accessed_names): 493 494 for node, item in zip(n.nodes, name_ref.items): 495 self.process_assignment_node(node, item) 496 497 return True 498 499 # Otherwise, use the position-based mechanism to obtain values. 500 501 else: 502 return False 503 else: 504 raise InspectError("In %s, item assignment needing %d items is given %d items." % ( 505 self.get_namespace_path(), len(n.nodes), len(name_ref.items))) 506 507 def process_compare_node(self, n): 508 509 """ 510 Process the given comparison node 'n', converting an operator sequence 511 from... 512 513 <expr1> <op1> <expr2> <op2> <expr3> 514 515 ...to... 516 517 <op1>(<expr1>, <expr2>) and <op2>(<expr2>, <expr3>) 518 """ 519 520 invocations = [] 521 last = n.expr 522 523 for op, op_node in n.ops: 524 op = operator_functions.get(op) 525 526 invocations.append(compiler.ast.CallFunc( 527 compiler.ast.Name("$op%s" % op), 528 [last, op_node])) 529 530 last = op_node 531 532 if len(invocations) > 1: 533 result = compiler.ast.And(invocations) 534 else: 535 result = invocations[0] 536 537 return self.process_structure_node(result) 538 539 def process_dict_node(self, node): 540 541 """ 542 Process the given dictionary 'node', returning a list of (key, value) 543 tuples. 544 """ 545 546 l = [] 547 for key, value in node.items: 548 l.append(( 549 self.process_structure_node(key), 550 self.process_structure_node(value))) 551 return l 552 553 def process_for_node(self, n): 554 555 """ 556 Generate attribute accesses for {n.list}.__iter__ and the next method on 557 the iterator, producing a replacement node for the original. 558 """ 559 560 t0 = self.get_temporary_name() 561 self.next_temporary() 562 t1 = self.get_temporary_name() 563 self.next_temporary() 564 t2 = self.get_temporary_name() 565 self.next_temporary() 566 t3 = self.get_temporary_name() 567 self.next_temporary() 568 569 node = compiler.ast.Stmt([ 570 571 # <t0> = {n.list} 572 # <t1> = <t0>.__iter__() 573 574 compiler.ast.Assign( 575 [compiler.ast.AssName(t0, "OP_ASSIGN")], 576 n.list), 577 578 compiler.ast.Assign( 579 [compiler.ast.AssName(t1, "OP_ASSIGN")], 580 compiler.ast.CallFunc( 581 compiler.ast.Getattr(compiler.ast.Name(t0), "__iter__"), 582 [])), 583 584 # <t2> = <t1>.next 585 # try: 586 # while True: 587 # try: 588 # <t3> = <t2>() 589 # except StopIteration: 590 # raise LoopExit 591 # <var>... = <t3> 592 # {n.body} 593 # except LoopExit: 594 # {n.else_} 595 # pass 596 597 compiler.ast.Assign( 598 [compiler.ast.AssName(t2, "OP_ASSIGN")], 599 compiler.ast.Getattr(compiler.ast.Name(t1), "next")), 600 601 compiler.ast.TryExcept( 602 compiler.ast.While( 603 compiler.ast.Name("True"), 604 compiler.ast.Stmt([ 605 compiler.ast.TryExcept( 606 compiler.ast.Assign( 607 [compiler.ast.AssName(t3, "OP_ASSIGN")], 608 compiler.ast.CallFunc( 609 compiler.ast.Name(t2), 610 [])), 611 [(compiler.ast.Name("StopIteration"), None, 612 compiler.ast.Raise(compiler.ast.Name("LoopExit")))], 613 None), 614 compiler.ast.Assign( 615 [n.assign], 616 compiler.ast.Name(t3)), 617 n.body]), 618 None), 619 [(compiler.ast.Name("LoopExit"), None, n.else_ or compiler.ast.Pass())], 620 None) 621 ]) 622 623 self.process_structure_node(node) 624 625 def process_literal_sequence_node(self, n, name, ref, cls): 626 627 """ 628 Process the given literal sequence node 'n' as a function invocation, 629 with 'name' indicating the type of the sequence, and 'ref' being a 630 reference to the type. The 'cls' is used to instantiate a suitable name 631 reference. 632 """ 633 634 if name == "dict": 635 items = [] 636 for key, value in n.items: 637 items.append(compiler.ast.Tuple([key, value])) 638 else: # name in ("list", "tuple"): 639 items = n.nodes 640 641 return self.get_literal_reference(name, ref, items, cls) 642 643 def process_operator_node(self, n): 644 645 """ 646 Process the given operator node 'n' as an operator function invocation. 647 """ 648 649 opname = n.__class__.__name__ 650 operands = n.getChildNodes() 651 652 # Convert a unary operation to an invocation. 653 654 op = unary_operator_functions.get(opname) 655 656 if op: 657 invocation = compiler.ast.CallFunc( 658 compiler.ast.Name("$op%s" % op), 659 [operands[0]] 660 ) 661 662 # Convert a single operator with a list of operands to a combination of 663 # pairwise operations. 664 665 else: 666 op = operator_functions[opname] 667 invocation = self._process_operator_node(op, operands) 668 669 return self.process_structure_node(invocation) 670 671 def _process_operator_node(self, op, operands): 672 673 """ 674 Process the given 'op', being an operator function, together with the 675 supplied 'operands', returning either a single remaining operand or an 676 invocation combining the operands. 677 """ 678 679 remaining = operands[1:] 680 if not remaining: 681 return operands[0] 682 683 return compiler.ast.CallFunc( 684 compiler.ast.Name("$op%s" % op), 685 [operands[0], self._process_operator_node(op, remaining)] 686 ) 687 688 def process_print_node(self, n): 689 690 """ 691 Process the given print node 'n' as an invocation on a stream of the 692 form... 693 694 $print(dest, args, nl) 695 696 The special function name will be translated elsewhere. 697 """ 698 699 nl = isinstance(n, compiler.ast.Printnl) 700 invocation = compiler.ast.CallFunc( 701 compiler.ast.Name("$print"), 702 [n.dest or compiler.ast.Name("None"), 703 compiler.ast.List(list(n.nodes)), 704 nl and compiler.ast.Name("True") or compiler.ast.Name("False")] 705 ) 706 return self.process_structure_node(invocation) 707 708 def process_slice_node(self, n, expr=None): 709 710 """ 711 Process the given slice node 'n' as a method invocation. 712 """ 713 714 if n.flags == "OP_ASSIGN": op = "__setslice__" 715 elif n.flags == "OP_DELETE": op = "__delslice__" 716 else: op = "__getslice__" 717 718 invocation = compiler.ast.CallFunc( 719 compiler.ast.Getattr(n.expr, op), 720 [n.lower or compiler.ast.Name("None"), n.upper or compiler.ast.Name("None")] + 721 (expr and [expr] or []) 722 ) 723 724 # Fix parse tree structure. 725 726 if op == "__delslice__": 727 invocation = compiler.ast.Discard(invocation) 728 729 return self.process_structure_node(invocation) 730 731 def process_sliceobj_node(self, n): 732 733 """ 734 Process the given slice object node 'n' as a slice constructor. 735 """ 736 737 op = "slice" 738 invocation = compiler.ast.CallFunc( 739 compiler.ast.Name("$op%s" % op), 740 n.nodes 741 ) 742 return self.process_structure_node(invocation) 743 744 def process_subscript_node(self, n, expr=None): 745 746 """ 747 Process the given subscript node 'n' as a method invocation. 748 """ 749 750 if n.flags == "OP_ASSIGN": op = "__setitem__" 751 elif n.flags == "OP_DELETE": op = "__delitem__" 752 else: op = "__getitem__" 753 754 invocation = compiler.ast.CallFunc( 755 compiler.ast.Getattr(n.expr, op), 756 list(n.subs) + (expr and [expr] or []) 757 ) 758 759 # Fix parse tree structure. 760 761 if op == "__delitem__": 762 invocation = compiler.ast.Discard(invocation) 763 764 return self.process_structure_node(invocation) 765 766 def process_attribute_chain(self, n): 767 768 """ 769 Process the given attribute access node 'n'. Return a reference 770 describing the expression. 771 """ 772 773 # AssAttr/Getattr are nested with the outermost access being the last 774 # access in any chain. 775 776 self.attrs.insert(0, n.attrname) 777 attrs = self.attrs 778 779 # Break attribute chains where non-access nodes are found. 780 781 if not self.have_access_expression(n): 782 self.reset_attribute_chain() 783 784 # Descend into the expression, extending backwards any existing chain, 785 # or building another for the expression. 786 787 name_ref = self.process_structure_node(n.expr) 788 789 # Restore chain information applying to this node. 790 791 if not self.have_access_expression(n): 792 self.restore_attribute_chain(attrs) 793 794 # Return immediately if the expression was another access and thus a 795 # continuation backwards along the chain. The above processing will 796 # have followed the chain all the way to its conclusion. 797 798 if self.have_access_expression(n): 799 del self.attrs[0] 800 801 return name_ref 802 803 # Attribute chain handling. 804 805 def reset_attribute_chain(self): 806 807 "Reset the attribute chain for a subexpression of an attribute access." 808 809 self.attrs = [] 810 self.chain_assignment.append(self.in_assignment) 811 self.chain_invocation.append(self.in_invocation) 812 self.in_assignment = None 813 self.in_invocation = None 814 815 def restore_attribute_chain(self, attrs): 816 817 "Restore the attribute chain for an attribute access." 818 819 self.attrs = attrs 820 self.in_assignment = self.chain_assignment.pop() 821 self.in_invocation = self.chain_invocation.pop() 822 823 def have_access_expression(self, node): 824 825 "Return whether the expression associated with 'node' is Getattr." 826 827 return isinstance(node.expr, compiler.ast.Getattr) 828 829 def get_name_for_tracking(self, name, name_ref=None, is_global=False): 830 831 """ 832 Return the name to be used for attribute usage observations involving 833 the given 'name' in the current namespace. 834 835 If the name is being used outside a function, and if 'name_ref' is 836 given and indicates a global or if 'is_global' is specified as a true 837 value, a path featuring the name in the global namespace is returned. 838 Otherwise, a path computed using the current namespace and the given 839 name is returned. 840 841 The intention of this method is to provide a suitably-qualified name 842 that can be tracked across namespaces. Where globals are being 843 referenced in class namespaces, they should be referenced using their 844 path within the module, not using a path within each class. 845 846 It may not be possible to identify a global within a function at the 847 time of inspection (since a global may appear later in a file). 848 Consequently, globals are identified by their local name rather than 849 their module-qualified path. 850 """ 851 852 # For functions, use the appropriate local names. 853 854 if self.in_function: 855 return name 856 857 # For global names outside functions, use a global name. 858 859 elif is_global or name_ref and name_ref.is_global_name(): 860 return self.get_global_path(name) 861 862 # Otherwise, establish a name in the current namespace. 863 864 else: 865 return self.get_object_path(name) 866 867 def get_path_for_access(self): 868 869 "Outside functions, register accesses at the module level." 870 871 if not self.in_function: 872 return self.name 873 else: 874 return self.get_namespace_path() 875 876 def get_module_name(self, node): 877 878 """ 879 Using the given From 'node' in this module, calculate any relative import 880 information, returning a tuple containing a module to import along with any 881 names to import based on the node's name information. 882 883 Where the returned module is given as None, whole module imports should 884 be performed for the returned modules using the returned names. 885 """ 886 887 # Absolute import. 888 889 if node.level == 0: 890 return node.modname, node.names 891 892 # Relative to an ancestor of this module. 893 894 else: 895 path = self.name.split(".") 896 level = node.level 897 898 # Relative imports treat package roots as submodules. 899 900 if split(self.filename)[-1] == "__init__.py": 901 level -= 1 902 903 if level > len(path): 904 raise InspectError("Relative import %r involves too many levels up from module %r" % ( 905 ("%s%s" % ("." * node.level, node.modname or "")), self.name)) 906 907 basename = ".".join(path[:len(path)-level]) 908 909 # Name imports from a module. 910 911 if node.modname: 912 return "%s.%s" % (basename, node.modname), node.names 913 914 # Relative whole module imports. 915 916 else: 917 return basename, node.names 918 919 def get_argnames(args): 920 921 """ 922 Return a list of all names provided by 'args'. Since tuples may be 923 employed, the arguments are traversed depth-first. 924 """ 925 926 l = [] 927 for arg in args: 928 if isinstance(arg, tuple): 929 l += get_argnames(arg) 930 else: 931 l.append(arg) 932 return l 933 934 def get_names_from_nodes(nodes): 935 936 """ 937 Return the names employed in the given 'nodes' along with the number of 938 nodes excluding sequences. 939 """ 940 941 names = set() 942 count = 0 943 944 for node in nodes: 945 946 # Add names and count them. 947 948 if isinstance(node, (compiler.ast.AssName, compiler.ast.Name)): 949 names.add(node.name) 950 count += 1 951 952 # Add names from sequences and incorporate their counts. 953 954 elif isinstance(node, (compiler.ast.AssList, compiler.ast.AssTuple, 955 compiler.ast.List, compiler.ast.Set, 956 compiler.ast.Tuple)): 957 _names, _count = get_names_from_nodes(node.nodes) 958 names.update(_names) 959 count += _count 960 961 # Count non-name, non-sequence nodes. 962 963 else: 964 count += 1 965 966 return names, count 967 968 # Location classes. 969 970 class Location: 971 972 "A generic program location." 973 974 def __init__(self, path, name, attrnames=None, version=None, access_number=None): 975 self.path = path 976 self.name = name 977 self.attrnames = attrnames 978 self.version = version 979 self.access_number = access_number 980 981 def __repr__(self): 982 return "Location(%r, %r, %r, %r, %r)" % self.as_tuple() 983 984 def as_tuple(self): 985 return (self.path, self.name, self.attrnames, self.version, self.access_number) 986 987 def __hash__(self): 988 return hash(self.as_tuple()) 989 990 def __eq__(self, other): 991 return self.as_tuple() == other.as_tuple() 992 993 def __cmp__(self, other): 994 return cmp(self.as_tuple(), other.as_tuple()) 995 996 def get_attrname(self): 997 998 """ 999 Extract the first attribute from the attribute names employed in this 1000 location. 1001 """ 1002 1003 attrnames = self.attrnames 1004 if not attrnames: 1005 return attrnames 1006 return get_attrnames(attrnames)[0] 1007 1008 class AccessLocation(Location): 1009 1010 "A specialised access location." 1011 1012 def __init__(self, path, name, attrnames, access_number): 1013 1014 """ 1015 Initialise an access location featuring 'path', 'name', 'attrnames' and 1016 'access_number'. 1017 """ 1018 1019 Location.__init__(self, path, name, attrnames, None, access_number) 1020 1021 def __repr__(self): 1022 return "AccessLocation(%r, %r, %r, %r)" % (self.path, self.name, self.attrnames, self.access_number) 1023 1024 # Result classes. 1025 1026 class InstructionSequence: 1027 1028 "A generic sequence of instructions." 1029 1030 def __init__(self, instructions): 1031 self.instructions = instructions 1032 1033 def get_value_instruction(self): 1034 return self.instructions[-1] 1035 1036 def get_init_instructions(self): 1037 return self.instructions[:-1] 1038 1039 # Dictionary utilities. 1040 1041 def init_item(d, key, fn): 1042 1043 """ 1044 Add to 'd' an entry for 'key' using the callable 'fn' to make an initial 1045 value where no entry already exists. 1046 """ 1047 1048 if not d.has_key(key): 1049 d[key] = fn() 1050 return d[key] 1051 1052 def dict_for_keys(d, keys): 1053 1054 "Return a new dictionary containing entries from 'd' for the given 'keys'." 1055 1056 nd = {} 1057 for key in keys: 1058 if d.has_key(key): 1059 nd[key] = d[key] 1060 return nd 1061 1062 def make_key(s): 1063 1064 "Make sequence 's' into a tuple-based key, first sorting its contents." 1065 1066 l = list(s) 1067 l.sort() 1068 return tuple(l) 1069 1070 def add_counter_item(d, key): 1071 1072 """ 1073 Make a mapping in 'd' for 'key' to the number of keys added before it, thus 1074 maintaining a mapping of keys to their order of insertion. 1075 """ 1076 1077 if not d.has_key(key): 1078 d[key] = len(d.keys()) 1079 return d[key] 1080 1081 def remove_items(d1, d2): 1082 1083 "Remove from 'd1' all items from 'd2'." 1084 1085 for key in d2.keys(): 1086 if d1.has_key(key): 1087 del d1[key] 1088 1089 # Set utilities. 1090 1091 def first(s): 1092 return list(s)[0] 1093 1094 def same(s1, s2): 1095 return set(s1) == set(s2) 1096 1097 def order_dependencies(all_depends): 1098 1099 """ 1100 Produce a dependency ordering for the 'all_depends' mapping. This mapping 1101 has the form "A depends on B, C...". The result will order A, B, C, and so 1102 on. 1103 """ 1104 1105 usage = init_reverse_dependencies(all_depends) 1106 1107 # Produce an ordering by obtaining exposed items (required by items already 1108 # processed) and putting them at the start of the list. 1109 1110 ordered = [] 1111 1112 while usage: 1113 have_next = False 1114 1115 for key, n in usage.items(): 1116 1117 # Add items needed by no other items to the ordering. 1118 1119 if not n: 1120 remove_dependency(key, all_depends, usage, ordered) 1121 have_next = True 1122 1123 if not have_next: 1124 raise ValueError, usage 1125 1126 return ordered 1127 1128 def order_dependencies_partial(all_depends): 1129 1130 """ 1131 Produce a dependency ordering for the 'all_depends' mapping. This mapping 1132 has the form "A depends on B, C...". The result will order A, B, C, and so 1133 on. Where cycles exist, they will be broken and a partial ordering returned. 1134 """ 1135 1136 usage = init_reverse_dependencies(all_depends) 1137 1138 # Duplicate the dependencies for subsequent modification. 1139 1140 new_depends = {} 1141 for key, values in all_depends.items(): 1142 new_depends[key] = set(values) 1143 1144 all_depends = new_depends 1145 1146 # Produce an ordering by obtaining exposed items (required by items already 1147 # processed) and putting them at the start of the list. 1148 1149 ordered = [] 1150 1151 while usage: 1152 least = None 1153 least_key = None 1154 1155 for key, n in usage.items(): 1156 1157 # Add items needed by no other items to the ordering. 1158 1159 if not n: 1160 remove_dependency(key, all_depends, usage, ordered) 1161 least = 0 1162 1163 # When breaking cycles, note the least used items. 1164 1165 elif least is None or len(n) < least: 1166 least_key = key 1167 least = len(n) 1168 1169 if least: 1170 transfer_dependencies(least_key, all_depends, usage, ordered) 1171 1172 return ordered 1173 1174 def init_reverse_dependencies(all_depends): 1175 1176 """ 1177 From 'all_depends', providing a mapping of the form "A depends on B, C...", 1178 record the reverse dependencies, making a mapping of the form 1179 "B is needed by A", "C is needed by A", and so on. 1180 """ 1181 1182 usage = {} 1183 1184 # Record path-based dependencies. 1185 1186 for key in all_depends.keys(): 1187 usage[key] = set() 1188 1189 for key, depends in all_depends.items(): 1190 for depend in depends: 1191 init_item(usage, depend, set) 1192 usage[depend].add(key) 1193 1194 return usage 1195 1196 def transfer_dependencies(key, all_depends, usage, ordered): 1197 1198 """ 1199 Transfer items needed by 'key' to those items needing 'key', found using 1200 'all_depends', and updating 'usage'. Insert 'key' into the 'ordered' 1201 collection of dependencies. 1202 1203 If "A is needed by X" and "B is needed by A", then transferring items needed 1204 by A will cause "B is needed by X" to be recorded as a consequence. 1205 1206 Transferring items also needs to occur in the reverse mapping, so that 1207 "A needs B" and "X needs A", then the consequence must be recorded as 1208 "X needs B". 1209 """ 1210 1211 ordered.insert(0, key) 1212 1213 needing = usage[key] # A is needed by X 1214 needed = all_depends.get(key) # A needs B 1215 1216 if needing: 1217 for depend in needing: 1218 l = all_depends.get(depend) 1219 if not l: 1220 continue 1221 1222 l.remove(key) # X needs (A) 1223 1224 if needed: 1225 l.update(needed) # X needs B... 1226 1227 # Prevent self references. 1228 1229 if depend in needed: 1230 l.remove(depend) 1231 1232 if needed: 1233 for depend in needed: 1234 l = usage.get(depend) 1235 if not l: 1236 continue 1237 1238 l.remove(key) # B is needed by (A) 1239 l.update(needing) # B is needed by X... 1240 1241 # Prevent self references. 1242 1243 if depend in needing: 1244 l.remove(depend) 1245 1246 if needed: 1247 del all_depends[key] 1248 del usage[key] 1249 1250 def remove_dependency(key, all_depends, usage, ordered): 1251 1252 """ 1253 Remove 'key', found in 'all_depends', from 'usage', inserting it into the 1254 'ordered' collection of dependencies. 1255 1256 Given that 'usage' for a given key A would indicate that "A needs <nothing>" 1257 upon removing A from 'usage', the outcome is that all keys needing A will 1258 have A removed from their 'usage' records. 1259 1260 So, if "B needs A", removing A will cause "B needs <nothing>" to be recorded 1261 as a consequence. 1262 """ 1263 1264 ordered.insert(0, key) 1265 1266 depends = all_depends.get(key) 1267 1268 # Reduce usage of the referenced items. 1269 1270 if depends: 1271 for depend in depends: 1272 usage[depend].remove(key) 1273 1274 del usage[key] 1275 1276 # General input/output. 1277 1278 def readfile(filename): 1279 1280 "Return the contents of 'filename'." 1281 1282 f = open(filename) 1283 try: 1284 return f.read() 1285 finally: 1286 f.close() 1287 1288 def writefile(filename, s): 1289 1290 "Write to 'filename' the string 's'." 1291 1292 f = open(filename, "w") 1293 try: 1294 f.write(s) 1295 finally: 1296 f.close() 1297 1298 # General encoding. 1299 1300 def sorted_output(x): 1301 1302 "Sort sequence 'x' and return a string with commas separating the values." 1303 1304 x = map(str, x) 1305 x.sort() 1306 return ", ".join(x) 1307 1308 def get_string_details(literals, encoding): 1309 1310 """ 1311 Determine whether 'literals' represent Unicode strings or byte strings, 1312 using 'encoding' to reproduce byte sequences. 1313 1314 Each literal is the full program representation including prefix and quotes 1315 recoded by the parser to UTF-8. Thus, any literal found to represent a byte 1316 string needs to be translated back to its original encoding. 1317 1318 Return a single encoded literal value, a type name, and the original 1319 encoding as a tuple. 1320 """ 1321 1322 typename = "unicode" 1323 1324 l = [] 1325 1326 for s in literals: 1327 out, _typename = get_literal_details(s) 1328 if _typename == "str": 1329 typename = "str" 1330 l.append(out) 1331 1332 out = "".join(l) 1333 1334 # For Unicode values, convert to the UTF-8 program representation. 1335 1336 if typename == "unicode": 1337 return out.encode("utf-8"), typename, encoding 1338 1339 # For byte string values, convert back to the original encoding. 1340 1341 else: 1342 return out.encode(encoding), typename, encoding 1343 1344 def get_literal_details(s): 1345 1346 """ 1347 Determine whether 's' represents a Unicode string or a byte string, where 1348 's' contains the full program representation of a literal including prefix 1349 and quotes, recoded by the parser to UTF-8. 1350 1351 Find and convert Unicode values starting with <backslash>u or <backslash>U, 1352 and byte or Unicode values starting with <backslash><octal digit> or 1353 <backslash>x. 1354 1355 Literals prefixed with "u" cause <backslash><octal digit> and <backslash>x 1356 to be considered as Unicode values. Otherwise, they produce byte values and 1357 cause unprefixed strings to be considered as byte strings. 1358 1359 Literals prefixed with "r" do not have their backslash-encoded values 1360 converted unless also prefixed with "u", in which case only the above value 1361 formats are converted, not any of the other special sequences for things 1362 like newlines. 1363 1364 Return the literal value as a Unicode object together with the appropriate 1365 type name in a tuple. 1366 """ 1367 1368 l = [] 1369 1370 # Identify the quote character and use it to identify the prefix. 1371 1372 quote_type = s[-1] 1373 prefix_end = s.find(quote_type) 1374 prefix = s[:prefix_end].lower() 1375 1376 if prefix not in ("", "b", "br", "r", "u", "ur"): 1377 raise ValueError, "String literal does not have a supported prefix: %s" % s 1378 1379 if "b" in prefix: 1380 typename = "str" 1381 else: 1382 typename = "unicode" 1383 1384 # Identify triple quotes or single quotes. 1385 1386 if len(s) >= 6 and s[-2] == quote_type and s[-3] == quote_type: 1387 quote = s[prefix_end:prefix_end+3] 1388 current = prefix_end + 3 1389 end = len(s) - 3 1390 else: 1391 quote = s[prefix_end] 1392 current = prefix_end + 1 1393 end = len(s) - 1 1394 1395 # Conversions of some quoted values. 1396 1397 searches = { 1398 "u" : (6, 16), 1399 "U" : (10, 16), 1400 "x" : (4, 16), 1401 } 1402 1403 octal_digits = map(str, range(0, 8)) 1404 1405 # Translations of some quoted values. 1406 1407 escaped = { 1408 "\\" : "\\", "'" : "'", '"' : '"', 1409 "a" : "\a", "b" : "\b", "f" : "\f", 1410 "n" : "\n", "r" : "\r", "t" : "\t", 1411 } 1412 1413 while current < end: 1414 1415 # Look for quoted values. 1416 1417 index = s.find("\\", current) 1418 if index == -1 or index + 1 == end: 1419 l.append(s[current:end]) 1420 break 1421 1422 # Add the preceding text. 1423 1424 l.append(s[current:index]) 1425 1426 # Handle quoted text. 1427 1428 term = s[index+1] 1429 1430 # Add Unicode values. Where a string is u-prefixed, even \o and \x 1431 # produce Unicode values. 1432 1433 if typename == "unicode" and ( 1434 term in ("u", "U") or 1435 "u" in prefix and (term == "x" or term in octal_digits)): 1436 1437 needed, base = searches.get(term, (4, 8)) 1438 value = convert_quoted_value(s, index, needed, end, base, unichr) 1439 l.append(value) 1440 current = index + needed 1441 1442 # Add raw byte values, changing the string type. 1443 1444 elif "r" not in prefix and ( 1445 term == "x" or term in octal_digits): 1446 1447 needed, base = searches.get(term, (4, 8)) 1448 value = convert_quoted_value(s, index, needed, end, base, chr) 1449 l.append(value) 1450 typename = "str" 1451 current = index + needed 1452 1453 # Add other escaped values. 1454 1455 elif "r" not in prefix and escaped.has_key(term): 1456 l.append(escaped[term]) 1457 current = index + 2 1458 1459 # Add other text as found. 1460 1461 else: 1462 l.append(s[index:index+2]) 1463 current = index + 2 1464 1465 # Collect the components into a single Unicode object. Since the literal 1466 # text was already in UTF-8 form, interpret plain strings as UTF-8 1467 # sequences. 1468 1469 out = [] 1470 1471 for value in l: 1472 if isinstance(value, unicode): 1473 out.append(value) 1474 else: 1475 out.append(unicode(value, "utf-8")) 1476 1477 return "".join(out), typename 1478 1479 def convert_quoted_value(s, index, needed, end, base, fn): 1480 1481 """ 1482 Interpret a quoted value in 's' at 'index' with the given 'needed' number of 1483 positions, and with the given 'end' indicating the first position after the 1484 end of the actual string content. 1485 1486 Use 'base' as the numerical base when interpreting the value, and use 'fn' 1487 to convert the value to an appropriate type. 1488 """ 1489 1490 s = s[index:min(index+needed, end)] 1491 1492 # Not a complete occurrence. 1493 1494 if len(s) < needed: 1495 return s 1496 1497 # Test for a well-formed value. 1498 1499 try: 1500 first = base == 8 and 1 or 2 1501 value = int(s[first:needed], base) 1502 except ValueError: 1503 return s 1504 else: 1505 return fn(value) 1506 1507 # Attribute chain decoding. 1508 1509 def get_attrnames(attrnames): 1510 1511 """ 1512 Split the qualified attribute chain 'attrnames' into its components, 1513 handling special attributes starting with "#" that indicate type 1514 conformance. 1515 """ 1516 1517 if attrnames.startswith("#"): 1518 return [attrnames] 1519 else: 1520 return attrnames.split(".") 1521 1522 def get_name_path(path, name): 1523 1524 "Return a suitable qualified name from the given 'path' and 'name'." 1525 1526 if "." in name: 1527 return name 1528 else: 1529 return "%s.%s" % (path, name) 1530 1531 # Usage-related functions. 1532 1533 def get_types_for_usage(attrnames, objects): 1534 1535 """ 1536 Identify the types that can support the given 'attrnames', using the 1537 given 'objects' as the catalogue of type details. 1538 """ 1539 1540 types = [] 1541 for name, _attrnames in objects.items(): 1542 if set(attrnames).issubset(_attrnames): 1543 types.append(name) 1544 return types 1545 1546 def get_invoked_attributes(usage): 1547 1548 "Obtain invoked attribute from the given 'usage'." 1549 1550 invoked = [] 1551 if usage: 1552 for attrname, invocation, assignment in usage: 1553 if invocation: 1554 invoked.append(attrname) 1555 return invoked 1556 1557 def get_assigned_attributes(usage): 1558 1559 "Obtain assigned attribute from the given 'usage'." 1560 1561 assigned = [] 1562 if usage: 1563 for attrname, invocation, assignment in usage: 1564 if assignment: 1565 assigned.append(attrname) 1566 return assigned 1567 1568 # Type and module functions. 1569 # NOTE: This makes assumptions about the __builtins__ structure. 1570 1571 def get_builtin_module(name): 1572 1573 "Return the module name containing the given type 'name'." 1574 1575 if name == "string": 1576 modname = "str" 1577 elif name == "utf8string": 1578 modname = "unicode" 1579 elif name == "NoneType": 1580 modname = "none" 1581 else: 1582 modname = name 1583 1584 return "__builtins__.%s" % modname 1585 1586 def get_builtin_type(name): 1587 1588 "Return the type name provided by the given Python value 'name'." 1589 1590 if name == "str": 1591 return "string" 1592 elif name == "unicode": 1593 return "utf8string" 1594 else: 1595 return name 1596 1597 def get_builtin_class(name): 1598 1599 "Return the full name of the built-in class having the given 'name'." 1600 1601 typename = get_builtin_type(name) 1602 module = get_builtin_module(typename) 1603 return "%s.%s" % (module, typename) 1604 1605 # Useful data. 1606 1607 predefined_constants = "False", "None", "NotImplemented", "True" 1608 1609 privileged_attributes = [ 1610 "__get_single_item_unchecked__", 1611 ] 1612 1613 unary_operator_functions = { 1614 1615 # Unary operations. 1616 1617 "Invert" : "invert", 1618 "UnaryAdd" : "pos", 1619 "UnarySub" : "neg", 1620 } 1621 1622 operator_functions = { 1623 1624 # Fundamental operations. 1625 1626 "is" : "is_", 1627 "is not" : "is_not", 1628 1629 # Binary operations. 1630 1631 "in" : "in_", 1632 "not in" : "not_in", 1633 "Add" : "add", 1634 "Bitand" : "and_", 1635 "Bitor" : "or_", 1636 "Bitxor" : "xor", 1637 "Div" : "div", 1638 "FloorDiv" : "floordiv", 1639 "LeftShift" : "lshift", 1640 "Mod" : "mod", 1641 "Mul" : "mul", 1642 "Power" : "pow", 1643 "RightShift" : "rshift", 1644 "Sub" : "sub", 1645 1646 # Augmented assignment. 1647 1648 "+=" : "iadd", 1649 "-=" : "isub", 1650 "*=" : "imul", 1651 "/=" : "idiv", 1652 "//=" : "ifloordiv", 1653 "%=" : "imod", 1654 "**=" : "ipow", 1655 "<<=" : "ilshift", 1656 ">>=" : "irshift", 1657 "&=" : "iand", 1658 "^=" : "ixor", 1659 "|=" : "ior", 1660 1661 # Comparisons. 1662 1663 "==" : "eq", 1664 "!=" : "ne", 1665 "<" : "lt", 1666 "<=" : "le", 1667 ">=" : "ge", 1668 ">" : "gt", 1669 } 1670 1671 operator_functions.update(unary_operator_functions) 1672 1673 # vim: tabstop=4 expandtab shiftwidth=4