1 #!/usr/bin/env python 2 3 """ 4 Common functions. 5 6 Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012, 2013, 7 2014, 2015, 2016 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 errors import * 24 from os import listdir, makedirs, remove 25 from os.path import exists, isdir, join, split 26 from results import ConstantValueRef, LiteralSequenceRef, NameRef 27 import compiler 28 29 class CommonOutput: 30 31 "Common output functionality." 32 33 def check_output(self): 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 if recorded_details != details: 44 self.remove_output() 45 46 writefile(self.get_output_details_filename(), details) 47 48 def get_output_details_filename(self): 49 50 "Return the output details filename." 51 52 return join(self.output, "$details") 53 54 def get_output_details(self): 55 56 "Return details of the existing output." 57 58 details_filename = self.get_output_details_filename() 59 60 if not exists(details_filename): 61 return None 62 else: 63 return readfile(details_filename) 64 65 def remove_output(self, dirname=None): 66 67 "Remove the output." 68 69 dirname = dirname or self.output 70 71 for filename in listdir(dirname): 72 path = join(dirname, filename) 73 if isdir(path): 74 self.remove_output(path) 75 else: 76 remove(path) 77 78 class CommonModule: 79 80 "A common module representation." 81 82 def __init__(self, name, importer): 83 84 """ 85 Initialise this module with the given 'name' and an 'importer' which is 86 used to provide access to other modules when required. 87 """ 88 89 self.name = name 90 self.importer = importer 91 self.filename = None 92 93 # Inspection-related attributes. 94 95 self.astnode = None 96 self.iterators = {} 97 self.temp = {} 98 self.lambdas = {} 99 100 # Constants, literals and values. 101 102 self.constants = {} 103 self.constant_values = {} 104 self.literals = {} 105 self.literal_types = {} 106 107 # Nested namespaces. 108 109 self.namespace_path = [] 110 self.in_function = False 111 112 # Attribute chains. 113 114 self.attrs = [] 115 116 def __repr__(self): 117 return "CommonModule(%r, %r)" % (self.name, self.importer) 118 119 def parse_file(self, filename): 120 121 "Parse the file with the given 'filename', initialising attributes." 122 123 self.filename = filename 124 self.astnode = compiler.parseFile(filename) 125 126 # Module-relative naming. 127 128 def get_global_path(self, name): 129 return "%s.%s" % (self.name, name) 130 131 def get_namespace_path(self): 132 return ".".join([self.name] + self.namespace_path) 133 134 def get_object_path(self, name): 135 return ".".join([self.name] + self.namespace_path + [name]) 136 137 def get_parent_path(self): 138 return ".".join([self.name] + self.namespace_path[:-1]) 139 140 # Namespace management. 141 142 def enter_namespace(self, name): 143 144 "Enter the namespace having the given 'name'." 145 146 self.namespace_path.append(name) 147 148 def exit_namespace(self): 149 150 "Exit the current namespace." 151 152 self.namespace_path.pop() 153 154 # Constant reference naming. 155 156 def get_constant_name(self, value): 157 158 "Add a new constant to the current namespace for 'value'." 159 160 path = self.get_namespace_path() 161 init_item(self.constants, path, dict) 162 return "$c%d" % add_counter_item(self.constants[path], value) 163 164 # Literal reference naming. 165 166 def get_literal_name(self): 167 168 "Add a new literal to the current namespace." 169 170 path = self.get_namespace_path() 171 init_item(self.literals, path, lambda: 0) 172 return "$C%d" % self.literals[path] 173 174 def next_literal(self): 175 self.literals[self.get_namespace_path()] += 1 176 177 # Temporary iterator naming. 178 179 def get_iterator_path(self): 180 return self.in_function and self.get_namespace_path() or self.name 181 182 def get_iterator_name(self): 183 path = self.get_iterator_path() 184 init_item(self.iterators, path, lambda: 0) 185 return "$i%d" % self.iterators[path] 186 187 def next_iterator(self): 188 self.iterators[self.get_iterator_path()] += 1 189 190 # Temporary variable naming. 191 192 def get_temporary_name(self): 193 path = self.get_namespace_path() 194 init_item(self.temp, path, lambda: 0) 195 return "$t%d" % self.temp[path] 196 197 def next_temporary(self): 198 self.temp[self.get_namespace_path()] += 1 199 200 # Arbitrary function naming. 201 202 def get_lambda_name(self): 203 path = self.get_namespace_path() 204 init_item(self.lambdas, path, lambda: 0) 205 name = "$l%d" % self.lambdas[path] 206 self.lambdas[path] += 1 207 return name 208 209 def reset_lambdas(self): 210 self.lambdas = {} 211 212 # Constant and literal recording. 213 214 def get_constant_reference(self, ref, value): 215 216 "Return a constant reference for the given 'ref' type and 'value'." 217 218 constant_name = self.get_constant_name(value) 219 220 # Return a reference for the constant. 221 222 objpath = self.get_object_path(constant_name) 223 name_ref = ConstantValueRef(constant_name, ref.instance_of(), value) 224 225 # Record the value and type for the constant. 226 227 self.constant_values[objpath] = name_ref.value, name_ref.get_origin() 228 return name_ref 229 230 def get_literal_reference(self, name, ref, items, cls): 231 232 """ 233 Return a literal reference for the given type 'name', literal 'ref', 234 node 'items' and employing the given 'cls' as the class of the returned 235 reference object. 236 """ 237 238 # Construct an invocation using the items as arguments. 239 240 typename = "$L%s" % name 241 242 invocation = compiler.ast.CallFunc( 243 compiler.ast.Name(typename), 244 items 245 ) 246 247 # Get a name for the actual literal. 248 249 instname = self.get_literal_name() 250 self.next_literal() 251 252 # Record the type for the literal. 253 254 objpath = self.get_object_path(instname) 255 self.literal_types[objpath] = ref.get_origin() 256 257 # Return a wrapper for the invocation exposing the items. 258 259 return cls( 260 instname, 261 ref.instance_of(), 262 self.process_structure_node(invocation), 263 invocation.args 264 ) 265 266 # Node handling. 267 268 def process_structure(self, node): 269 270 """ 271 Within the given 'node', process the program structure. 272 273 During inspection, this will process global declarations, adjusting the 274 module namespace, and import statements, building a module dependency 275 hierarchy. 276 277 During translation, this will consult deduced program information and 278 output translated code. 279 """ 280 281 l = [] 282 for n in node.getChildNodes(): 283 l.append(self.process_structure_node(n)) 284 return l 285 286 def process_augassign_node(self, n): 287 288 "Process the given augmented assignment node 'n'." 289 290 op = operator_functions[n.op] 291 292 if isinstance(n.node, compiler.ast.Getattr): 293 target = compiler.ast.AssAttr(n.node.expr, n.node.attrname, "OP_ASSIGN") 294 elif isinstance(n.node, compiler.ast.Name): 295 target = compiler.ast.AssName(n.node.name, "OP_ASSIGN") 296 else: 297 target = n.node 298 299 assignment = compiler.ast.Assign( 300 [target], 301 compiler.ast.CallFunc( 302 compiler.ast.Name("$op%s" % op), 303 [n.node, n.expr])) 304 305 return self.process_structure_node(assignment) 306 307 def process_assignment_for_function(self, original_name, name): 308 309 """ 310 Return an assignment operation making 'original_name' refer to the given 311 'name'. 312 """ 313 314 assignment = compiler.ast.Assign( 315 [compiler.ast.AssName(original_name, "OP_ASSIGN")], 316 compiler.ast.Name(name) 317 ) 318 319 return self.process_structure_node(assignment) 320 321 def process_assignment_node_items(self, n, expr): 322 323 """ 324 Process the given assignment node 'n' whose children are to be assigned 325 items of 'expr'. 326 """ 327 328 name_ref = self.process_structure_node(expr) 329 330 # Either unpack the items and present them directly to each assignment 331 # node. 332 333 if isinstance(name_ref, LiteralSequenceRef): 334 self.process_literal_sequence_items(n, name_ref) 335 336 # Or have the assignment nodes access each item via the sequence API. 337 338 else: 339 self.process_assignment_node_items_by_position(n, expr, name_ref) 340 341 def process_assignment_node_items_by_position(self, n, expr, name_ref): 342 343 """ 344 Process the given sequence assignment node 'n', converting the node to 345 the separate assignment of each target using positional access on a 346 temporary variable representing the sequence. Use 'expr' as the assigned 347 value and 'name_ref' as the reference providing any existing temporary 348 variable. 349 """ 350 351 assignments = [] 352 353 if isinstance(name_ref, NameRef): 354 temp = name_ref.name 355 else: 356 temp = self.get_temporary_name() 357 self.next_temporary() 358 359 assignments.append( 360 compiler.ast.Assign([compiler.ast.AssName(temp, "OP_ASSIGN")], expr) 361 ) 362 363 for i, node in enumerate(n.nodes): 364 assignments.append( 365 compiler.ast.Assign([node], compiler.ast.Subscript( 366 compiler.ast.Name(temp), "OP_APPLY", [compiler.ast.Const(i)])) 367 ) 368 369 return self.process_structure_node(compiler.ast.Stmt(assignments)) 370 371 def process_literal_sequence_items(self, n, name_ref): 372 373 """ 374 Process the given assignment node 'n', obtaining from the given 375 'name_ref' the items to be assigned to the assignment targets. 376 """ 377 378 if len(n.nodes) == len(name_ref.items): 379 for node, item in zip(n.nodes, name_ref.items): 380 self.process_assignment_node(node, item) 381 else: 382 raise InspectError("In %s, item assignment needing %d items is given %d items." % ( 383 self.get_namespace_path(), len(n.nodes), len(name_ref.items))) 384 385 def process_compare_node(self, n): 386 387 """ 388 Process the given comparison node 'n', converting an operator sequence 389 from... 390 391 <expr1> <op1> <expr2> <op2> <expr3> 392 393 ...to... 394 395 <op1>(<expr1>, <expr2>) and <op2>(<expr2>, <expr3>) 396 """ 397 398 invocations = [] 399 last = n.expr 400 401 for op, op_node in n.ops: 402 op = operator_functions.get(op) 403 404 invocations.append(compiler.ast.CallFunc( 405 compiler.ast.Name("$op%s" % op), 406 [last, op_node])) 407 408 last = op_node 409 410 if len(invocations) > 1: 411 result = compiler.ast.And(invocations) 412 else: 413 result = invocations[0] 414 415 return self.process_structure_node(result) 416 417 def process_dict_node(self, node): 418 419 """ 420 Process the given dictionary 'node', returning a list of (key, value) 421 tuples. 422 """ 423 424 l = [] 425 for key, value in node.items: 426 l.append(( 427 self.process_structure_node(key), 428 self.process_structure_node(value))) 429 return l 430 431 def process_for_node(self, n): 432 433 """ 434 Generate attribute accesses for {n.list}.__iter__ and the next method on 435 the iterator, producing a replacement node for the original. 436 """ 437 438 node = compiler.ast.Stmt([ 439 440 # <iterator> = {n.list}.__iter__ 441 442 compiler.ast.Assign( 443 [compiler.ast.AssName(self.get_iterator_name(), "OP_ASSIGN")], 444 compiler.ast.CallFunc( 445 compiler.ast.Getattr(n.list, "__iter__"), 446 [] 447 )), 448 449 # try: 450 # while True: 451 # <var>... = <iterator>.next() 452 # ... 453 # except StopIteration: 454 # pass 455 456 compiler.ast.TryExcept( 457 compiler.ast.While( 458 compiler.ast.Name("True"), 459 compiler.ast.Stmt([ 460 compiler.ast.Assign( 461 [n.assign], 462 compiler.ast.CallFunc( 463 compiler.ast.Getattr(compiler.ast.Name(self.get_iterator_name()), "next"), 464 [] 465 )), 466 n.body]), 467 None), 468 [(compiler.ast.Name("StopIteration"), None, compiler.ast.Stmt([compiler.ast.Pass()]))], 469 None) 470 ]) 471 472 self.next_iterator() 473 self.process_structure_node(node) 474 475 def process_literal_sequence_node(self, n, name, ref, cls): 476 477 """ 478 Process the given literal sequence node 'n' as a function invocation, 479 with 'name' indicating the type of the sequence, and 'ref' being a 480 reference to the type. The 'cls' is used to instantiate a suitable name 481 reference. 482 """ 483 484 if name == "dict": 485 items = [] 486 for key, value in n.items: 487 items.append(compiler.ast.Tuple([key, value])) 488 else: # name in ("list", "tuple"): 489 items = n.nodes 490 491 return self.get_literal_reference(name, ref, items, cls) 492 493 def process_operator_node(self, n): 494 495 """ 496 Process the given operator node 'n' as an operator function invocation. 497 """ 498 499 op = operator_functions[n.__class__.__name__] 500 invocation = compiler.ast.CallFunc( 501 compiler.ast.Name("$op%s" % op), 502 list(n.getChildNodes()) 503 ) 504 return self.process_structure_node(invocation) 505 506 def process_slice_node(self, n, expr=None): 507 508 """ 509 Process the given slice node 'n' as an operator function invocation. 510 """ 511 512 op = n.flags == "OP_ASSIGN" and "setslice" or "getslice" 513 invocation = compiler.ast.CallFunc( 514 compiler.ast.Name("$op%s" % op), 515 [n.expr, n.lower or compiler.ast.Name("None"), n.upper or compiler.ast.Name("None")] + 516 (expr and [expr] or []) 517 ) 518 return self.process_structure_node(invocation) 519 520 def process_sliceobj_node(self, n): 521 522 """ 523 Process the given slice object node 'n' as a slice constructor. 524 """ 525 526 op = "slice" 527 invocation = compiler.ast.CallFunc( 528 compiler.ast.Name("$op%s" % op), 529 n.nodes 530 ) 531 return self.process_structure_node(invocation) 532 533 def process_subscript_node(self, n, expr=None): 534 535 """ 536 Process the given subscript node 'n' as an operator function invocation. 537 """ 538 539 op = n.flags == "OP_ASSIGN" and "setitem" or "getitem" 540 invocation = compiler.ast.CallFunc( 541 compiler.ast.Name("$op%s" % op), 542 [n.expr] + list(n.subs) + (expr and [expr] or []) 543 ) 544 return self.process_structure_node(invocation) 545 546 def process_attribute_chain(self, n): 547 548 """ 549 Process the given attribute access node 'n'. Return a reference 550 describing the expression. 551 """ 552 553 # AssAttr/Getattr are nested with the outermost access being the last 554 # access in any chain. 555 556 self.attrs.insert(0, n.attrname) 557 attrs = self.attrs 558 559 # Break attribute chains where non-access nodes are found. 560 561 if not self.have_access_expression(n): 562 self.reset_attribute_chain() 563 564 # Descend into the expression, extending backwards any existing chain, 565 # or building another for the expression. 566 567 name_ref = self.process_structure_node(n.expr) 568 569 # Restore chain information applying to this node. 570 571 if not self.have_access_expression(n): 572 self.restore_attribute_chain(attrs) 573 574 # Return immediately if the expression was another access and thus a 575 # continuation backwards along the chain. The above processing will 576 # have followed the chain all the way to its conclusion. 577 578 if self.have_access_expression(n): 579 del self.attrs[0] 580 581 return name_ref 582 583 def reset_attribute_chain(self): 584 585 "Reset the attribute chain for a subexpression of an attribute access." 586 587 self.attrs = [] 588 589 def restore_attribute_chain(self, attrs): 590 591 "Restore the attribute chain for an attribute access." 592 593 self.attrs = attrs 594 595 def have_access_expression(self, node): 596 597 "Return whether the expression associated with 'node' is Getattr." 598 599 return isinstance(node.expr, compiler.ast.Getattr) 600 601 def get_name_for_tracking(self, name, path=None): 602 603 """ 604 Return the name to be used for attribute usage observations involving 605 the given 'name' in the current namespace. If 'path' is indicated and 606 the name is being used outside a function, return the path value; 607 otherwise, return a path computed using the current namespace and the 608 given name. 609 610 The intention of this method is to provide a suitably-qualified name 611 that can be tracked across namespaces. Where globals are being 612 referenced in class namespaces, they should be referenced using their 613 path within the module, not using a path within each class. 614 615 It may not be possible to identify a global within a function at the 616 time of inspection (since a global may appear later in a file). 617 Consequently, globals are identified by their local name rather than 618 their module-qualified path. 619 """ 620 621 # For functions, use the appropriate local names. 622 623 if self.in_function: 624 return name 625 626 # For static namespaces, use the given qualified name. 627 628 elif path: 629 return path 630 631 # Otherwise, establish a name in the current (module) namespace. 632 633 else: 634 return self.get_object_path(name) 635 636 def get_path_for_access(self): 637 638 "Outside functions, register accesses at the module level." 639 640 if not self.in_function: 641 return self.name 642 else: 643 return self.get_namespace_path() 644 645 def get_module_name(self, node): 646 647 """ 648 Using the given From 'node' in this module, calculate any relative import 649 information, returning a tuple containing a module to import along with any 650 names to import based on the node's name information. 651 652 Where the returned module is given as None, whole module imports should 653 be performed for the returned modules using the returned names. 654 """ 655 656 # Absolute import. 657 658 if node.level == 0: 659 return node.modname, node.names 660 661 # Relative to an ancestor of this module. 662 663 else: 664 path = self.name.split(".") 665 level = node.level 666 667 # Relative imports treat package roots as submodules. 668 669 if split(self.filename)[-1] == "__init__.py": 670 level -= 1 671 672 if level > len(path): 673 raise InspectError("Relative import %r involves too many levels up from module %r" % ( 674 ("%s%s" % ("." * node.level, node.modname or "")), self.name)) 675 676 basename = ".".join(path[:len(path)-level]) 677 678 # Name imports from a module. 679 680 if node.modname: 681 return "%s.%s" % (basename, node.modname), node.names 682 683 # Relative whole module imports. 684 685 else: 686 return basename, node.names 687 688 def get_argnames(args): 689 690 """ 691 Return a list of all names provided by 'args'. Since tuples may be 692 employed, the arguments are traversed depth-first. 693 """ 694 695 l = [] 696 for arg in args: 697 if isinstance(arg, tuple): 698 l += get_argnames(arg) 699 else: 700 l.append(arg) 701 return l 702 703 # Dictionary utilities. 704 705 def init_item(d, key, fn): 706 707 """ 708 Add to 'd' an entry for 'key' using the callable 'fn' to make an initial 709 value where no entry already exists. 710 """ 711 712 if not d.has_key(key): 713 d[key] = fn() 714 return d[key] 715 716 def dict_for_keys(d, keys): 717 718 "Return a new dictionary containing entries from 'd' for the given 'keys'." 719 720 nd = {} 721 for key in keys: 722 if d.has_key(key): 723 nd[key] = d[key] 724 return nd 725 726 def make_key(s): 727 728 "Make sequence 's' into a tuple-based key, first sorting its contents." 729 730 l = list(s) 731 l.sort() 732 return tuple(l) 733 734 def add_counter_item(d, key): 735 736 """ 737 Make a mapping in 'd' for 'key' to the number of keys added before it, thus 738 maintaining a mapping of keys to their order of insertion. 739 """ 740 741 if not d.has_key(key): 742 d[key] = len(d.keys()) 743 return d[key] 744 745 def remove_items(d1, d2): 746 747 "Remove from 'd1' all items from 'd2'." 748 749 for key in d2.keys(): 750 if d1.has_key(key): 751 del d1[key] 752 753 # Set utilities. 754 755 def first(s): 756 return list(s)[0] 757 758 def same(s1, s2): 759 return set(s1) == set(s2) 760 761 # General input/output. 762 763 def readfile(filename): 764 765 "Return the contents of 'filename'." 766 767 f = open(filename) 768 try: 769 return f.read() 770 finally: 771 f.close() 772 773 def writefile(filename, s): 774 775 "Write to 'filename' the string 's'." 776 777 f = open(filename, "w") 778 try: 779 f.write(s) 780 finally: 781 f.close() 782 783 # General encoding. 784 785 def sorted_output(x): 786 787 "Sort sequence 'x' and return a string with commas separating the values." 788 789 x = map(str, x) 790 x.sort() 791 return ", ".join(x) 792 793 # Attribute chain decoding. 794 795 def get_attrnames(attrnames): 796 797 """ 798 Split the qualified attribute chain 'attrnames' into its components, 799 handling special attributes starting with "#" that indicate type 800 conformance. 801 """ 802 803 if attrnames.startswith("#"): 804 return [attrnames] 805 else: 806 return attrnames.split(".") 807 808 def get_attrname_from_location(location): 809 810 """ 811 Extract the first attribute from the attribute names employed in a 812 'location'. 813 """ 814 815 path, name, attrnames, access = location 816 if not attrnames: 817 return attrnames 818 return get_attrnames(attrnames)[0] 819 820 def get_name_path(path, name): 821 822 "Return a suitable qualified name from the given 'path' and 'name'." 823 824 if "." in name: 825 return name 826 else: 827 return "%s.%s" % (path, name) 828 829 # Usage-related functions. 830 831 def get_types_for_usage(attrnames, objects): 832 833 """ 834 Identify the types that can support the given 'attrnames', using the 835 given 'objects' as the catalogue of type details. 836 """ 837 838 types = [] 839 for name, _attrnames in objects.items(): 840 if set(attrnames).issubset(_attrnames): 841 types.append(name) 842 return types 843 844 def get_invoked_attributes(usage): 845 846 "Obtain invoked attribute from the given 'usage'." 847 848 invoked = [] 849 if usage: 850 for attrname, invocation, assignment in usage: 851 if invocation: 852 invoked.append(attrname) 853 return invoked 854 855 def get_assigned_attributes(usage): 856 857 "Obtain assigned attribute from the given 'usage'." 858 859 assigned = [] 860 if usage: 861 for attrname, invocation, assignment in usage: 862 if assignment: 863 assigned.append(attrname) 864 return assigned 865 866 # Useful data. 867 868 predefined_constants = "False", "None", "NotImplemented", "True" 869 870 operator_functions = { 871 872 # Fundamental operations. 873 874 "is" : "is_", 875 "is not" : "is_not", 876 877 # Binary operations. 878 879 "in" : "in_", 880 "not in" : "not_in", 881 "Add" : "add", 882 "Bitand" : "and_", 883 "Bitor" : "or_", 884 "Bitxor" : "xor", 885 "Div" : "div", 886 "FloorDiv" : "floordiv", 887 "LeftShift" : "lshift", 888 "Mod" : "mod", 889 "Mul" : "mul", 890 "Power" : "pow", 891 "RightShift" : "rshift", 892 "Sub" : "sub", 893 894 # Unary operations. 895 896 "Invert" : "invert", 897 "UnaryAdd" : "pos", 898 "UnarySub" : "neg", 899 900 # Augmented assignment. 901 902 "+=" : "iadd", 903 "-=" : "isub", 904 "*=" : "imul", 905 "/=" : "idiv", 906 "//=" : "ifloordiv", 907 "%=" : "imod", 908 "**=" : "ipow", 909 "<<=" : "ilshift", 910 ">>=" : "irshift", 911 "&=" : "iand", 912 "^=" : "ixor", 913 "|=" : "ior", 914 915 # Comparisons. 916 917 "==" : "eq", 918 "!=" : "ne", 919 "<" : "lt", 920 "<=" : "le", 921 ">=" : "ge", 922 ">" : "gt", 923 } 924 925 # vim: tabstop=4 expandtab shiftwidth=4