Lichen

common.py

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