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