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