# HG changeset patch # User paulb@localhost.localdomain # Date 1175813598 -7200 # Node ID 5c20f017c8de525ad48fd79a5e8d28f72a58c9e6 # Parent c8616d31e76cadc16b43c41fec94d02fccf21717 Introduced sets throughout the code. Created a simplified package containing essential classes. Changed the annotation visitor so that nodes are not returned from each visitor method. Added a check on the context when invoking subprograms so that the extra Self node is not inserted into the arguments for non-instance methods or functions. diff -r c8616d31e76c -r 5c20f017c8de annotate.py --- a/annotate.py Sun Apr 01 17:43:20 2007 +0200 +++ b/annotate.py Fri Apr 06 00:53:18 2007 +0200 @@ -75,7 +75,7 @@ "Initialise a 'node' for annotation." if not hasattr(node, attr): - setattr(node, attr, []) + setattr(node, attr, set()) def annotate(self, node, types, attr="types"): @@ -92,7 +92,7 @@ for type in types: if type not in target: - target.append(type) + target.add(type) self.count += 1 system = System() @@ -176,14 +176,13 @@ # NOTE: Not declaring module namespace usage, even though it is used. - return self.process_node(module, self.global_namespace, 0) + self.process_node(module, self.global_namespace, 0) def process_node(self, node, locals, using_module_namespace): """ Process a subprogram or module 'node', indicating the initial 'locals'. - Return an annotated subprogram or module. Note that this method may - mutate nodes in the original program. + Note that this method may mutate nodes in the original program. """ # Recursion test. @@ -192,7 +191,7 @@ if not self.rerun_subprograms.has_key(node): self.rerun_subprograms[node] = [] self.rerun_subprograms[node].append(locals) - return node + return # Record the current subprogram and namespace. @@ -222,8 +221,8 @@ node.namespace = self.namespace self.set_module_namespace(using_module_namespace) - result = self.dispatch(node) - self.extract_results(result) + self.dispatch(node) + self.extract_results(node) while self.rerun_subprograms.has_key(node): all_rerun_locals = self.rerun_subprograms[node] @@ -235,8 +234,8 @@ node.namespace = rerun_locals self.set_module_namespace(using_module_namespace) - result = self.dispatch(node) - self.extract_results(result) + self.dispatch(node) + self.extract_results(node) # Restore the previous subprogram and namespace. @@ -244,8 +243,6 @@ self.current_subprograms.pop() self.reset_module_namespace(using_module_namespace) - return result - def set_module_namespace(self, using_module_namespace): """ @@ -266,15 +263,15 @@ if using_module_namespace: self.module.namespace = self.namespace - def extract_results(self, result): + def extract_results(self, node): "Extract results from the namespace." - result.namespace = self.namespace - self.system.annotate(result, self.namespace.raises, "raises") - self.system.annotate(result, self.namespace.returns, "returns") - if hasattr(result, "return_locals"): - combine(result.return_locals, self.namespace.return_locals) + node.namespace = self.namespace + self.system.annotate(node, self.namespace.raises, "raises") + self.system.annotate(node, self.namespace.returns, "returns") + if hasattr(node, "return_locals"): + node.return_locals.update(self.namespace.return_locals) def annotate(self, node, types=None): @@ -300,7 +297,7 @@ for param, types in items: if not node.paramtypes.has_key(param): - node.paramtypes[param] = [] + node.paramtypes[param] = set() self.system.combine(node.paramtypes[param], types) # Visitor methods. @@ -316,7 +313,7 @@ def dispatch(self, node, *args): try: - return Visitor.dispatch(self, node, *args) + Visitor.dispatch(self, node, *args) except AnnotationError, exc: exc.add(node) raise @@ -328,31 +325,29 @@ def visitAssign(self, assign): """ - Return the 'assign' node whose contents (merely a group of nodes) have - been processed. + Process the 'assign' node and its contents. """ - assign.code = self.dispatches(assign.code) - return assign + self.dispatches(assign.code) def visitCheckType(self, checktype): """ - Return the 'checktype' node, processing the expression to find the - possible types of the exception, and processing each choice to build a - list of checked types for the exception. + Process the 'checktype' node, finding the possible types of the + exception, and processing each choice to build a list of checked types + for the exception. """ inverted = getattr(checktype, "inverted", 0) - checktype.expr = self.dispatch(checktype.expr) + self.dispatch(checktype.expr) expr_types = self.namespace.types - choice_types = [] + choice_types = set() choices = [] for choice in checktype.choices: choices.append(self.dispatch(choice)) - choice_types += self.namespace.types + choice_types.update(self.namespace.types) for expr_type in expr_types: in_choices = expr_type.type.get_class() in choice_types @@ -363,12 +358,10 @@ if not inverted and not in_choices or inverted and in_choices: self._prune_non_accesses(checktype.expr, expr_type) - return checktype - def visitConditional(self, conditional): """ - Return the 'conditional' node, processing the test, body and else + Process the 'conditional' node, processing the test, body and else clauses and recording their processed forms. The body and else clauses are processed within their own namespaces, and the test is also processed in its own namespace if 'isolate_test' is set on the @@ -391,7 +384,7 @@ self.module.namespace = self.namespace self.namespace.merge_namespace(saved_namespace) - conditional.test = self.dispatch(conditional.test) + self.dispatch(conditional.test) # Where the test may affect the body and the else clause, save the # namespace after processing the test. @@ -406,12 +399,12 @@ # NOTE: Exception recording. else: - test_raises = [] - combine(test_raises, self.namespace.raises) + test_raises = set() + test_raises.update(self.namespace.raises) # Process the body clause. - conditional.body = self.dispatches(conditional.body) + self.dispatches(conditional.body) body_namespace = self.namespace # Use the saved namespace as a template for the else clause. @@ -423,7 +416,7 @@ # Process the else clause. - conditional.else_ = self.dispatches(conditional.else_) + self.dispatches(conditional.else_) else_namespace = self.namespace # Merge the body and else namespaces. @@ -442,37 +435,34 @@ if exc_type not in body_namespace.raises: self.namespace.revoke_exception_type(exc_type) - return conditional - def visitGlobal(self, global_): """ - Return the 'global_' node unprocessed since namespaces should have + Leave the 'global_' node unprocessed since namespaces should have already been altered to take global names into consideration. """ - return global_ + pass def visitImport(self, import_): """ - Return the 'import_' node, importing the module with the stated name + Process the 'import_' node, importing the module with the stated name and storing details on the node. """ module = self.importer.load(import_.name, self.builtins, getattr(import_, "alias", None)) if module is not None: - self.namespace.set_types([module]) + self.namespace.set_types(set([module])) else: - self.namespace.set_types([]) + self.namespace.set_types(set()) self.annotate(import_) # mainly for viewing purposes - return import_ def _visitInvoke(self, invoke, invocation_types, have_args): """ - Return the processed 'invoke' node, using the given 'invocation_types' - as the list of callables to be investigated for instantiation or for the + Process the 'invoke' node, using the given 'invocation_types' as the + list of callables to be investigated for instantiation or for the invocation of functions or blocks. If 'have_args' is a true value, any invocation or instantiation will involve arguments. """ @@ -556,21 +546,20 @@ # Associate the instance with the result of this invocation. - self.namespace.set_types([Attribute(None, instance)]) + self.namespace.set_types(set([Attribute(None, instance)])) self.annotate(invoke) # Remember the invocations that were found, along with the return type # information. invoke.invocations = invocations - self.namespace.set_types(getattr(invoke, "types", [])) - return invoke + self.namespace.set_types(getattr(invoke, "types", set())) def visitInvokeRef(self, invoke): """ - Return the processed 'invoke' node, first finding the callables - indicated by the reference. + Process the 'invoke' node, first finding the callables indicated by the + reference. """ # Where the invocation belongs to an instance but the invoked subprogram @@ -585,57 +574,79 @@ #print "Created", invoke.ref, "for", getattr(invoke.ref, "instance", None) invoke.ref.module.simplifier.subnames[invoke.ref.full_name()] = invoke.ref invocation_types = [Attribute(None, invoke.ref)] - return self._visitInvoke(invoke, invocation_types, have_args=0) + self._visitInvoke(invoke, invocation_types, have_args=0) def visitInvokeFunction(self, invoke): """ - Return the processed 'invoke' node, first finding the callables - indicated by the expression. + Process the 'invoke' node, first finding the callables indicated by the + expression. """ - invoke.expr = self.dispatch(invoke.expr) + self.dispatch(invoke.expr) invocation_types = self.namespace.types # Invocation processing starts with making sure that the arguments have # been processed. - return self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke)) + self._visitInvoke(invoke, invocation_types, have_args=self.process_args(invoke)) def visitLoadAttr(self, loadattr): """ - Return the 'loadattr' node, processing and storing the expression, and + Process the 'loadattr' node, processing and storing the expression, and using the expression's types to construct records of accesses and non-accesses using the stated attribute name. """ - loadattr.expr = self.dispatch(loadattr.expr) - types = [] + self.dispatch(loadattr.expr) + types = set() non_accesses = [] accesses = {} + + # For each expression type... + for attr in self.namespace.types: + + # Find types for the named attribute. + attributes = get_attributes(attr.type, loadattr.name) + + # Where no attributes exist... + if not attributes: + + # Register new invalid accesses and mark a possible exception. + if not attr in non_accesses: non_accesses.append(attr) - combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError")) + self.namespace.raises.update(self.get_builtin_instances(loadattr, "AttributeError")) # Revoke this type from any name involved. self._prune_non_accesses(loadattr.expr, attr) + # For each type found... + for attribute, accessor in attributes: + + # For actual attributes, register the type and remember the + # access. + if attribute is not None: - types.append(attribute) + types.add(attribute) if not accesses.has_key(attr.type): accesses[attr.type] = [] if not (attribute, accessor) in accesses[attr.type]: accesses[attr.type].append((attribute, accessor)) + + # Otherwise, register new invalid accesses and note a possible + # exception. + else: if not attr in non_accesses: non_accesses.append(attr) - combine(self.namespace.raises, self.get_builtin_instances(loadattr, "AttributeError")) + self.namespace.raises.update(self.get_builtin_instances(loadattr, "AttributeError")) # Revoke this type from any name involved. @@ -643,11 +654,13 @@ if not types: print "No attribute found for", loadattr.name, "given", self.namespace.types + + # Remember the result types. + self.namespace.set_types(types) loadattr.non_accesses = non_accesses loadattr.accesses = accesses self.annotate(loadattr) - return loadattr def _prune_non_accesses(self, expr, attr): @@ -679,41 +692,37 @@ def visitLoadExc(self, loadexc): """ - Return the 'loadexc' node, discovering the possible exception types + Process the 'loadexc' node, discovering the possible exception types raised. """ self.namespace.set_types(self.namespace.raises) self.annotate(loadexc) - return loadexc def visitLoadName(self, loadname): """ - Return the 'loadname' node, processing the name information on the node + Process the 'loadname' node, processing the name information on the node to determine which types are involved with the name. """ self.namespace.set_types(self.namespace.load(loadname.name)) - result = loadname - self.annotate(result) - return result + self.annotate(loadname) def visitLoadRef(self, loadref): """ - Return the 'loadref' node, obtaining type information about the + Process the 'loadref' node, obtaining type information about the reference stated on the node. """ - self.namespace.set_types([Attribute(None, loadref.ref)]) + self.namespace.set_types(set([Attribute(None, loadref.ref)])) self.annotate(loadref) - return loadref def visitLoadTemp(self, loadtemp): """ - Return the 'loadtemp' node, obtaining type information about the + Process the 'loadtemp' node, obtaining type information about the temporary variable accessed, and removing variable information where the 'release' attribute has been set on the node. """ @@ -727,35 +736,31 @@ except KeyError: raise AnnotationMessage, "Temporary store index '%s' not defined." % index self.annotate(loadtemp) - return loadtemp def visitModule(self, module): """ - Return the processed 'module' whose contents (merely a group of nodes) - are processed. + Process the 'module' and its contents. """ - module.code = self.dispatches(module.code) - return module + self.dispatches(module.code) def visitNot(self, not_): - "Return the 'not_' node whose expression is processed." + "Process the 'not_' node and its expression." - not_.expr = self.dispatch(not_.expr) - return not_ + self.dispatch(not_.expr) def visitPass(self, pass_): - "Return the unprocessed 'pass_' node." + "Leave the 'pass_' node unprocessed." - return pass_ + pass def visitRaise(self, raise_): """ - Return the 'raise_' node, processing any traceback information along + Process the 'raise_' node, processing any traceback information along with the raised exception expression, converting the node into a kind of invocation where the expression is found not to be an invocation itself. This node affects the namespace, adding exception types to the list of @@ -763,8 +768,8 @@ """ if getattr(raise_, "traceback", None) is not None: - raise_.traceback = self.dispatch(raise_.traceback) - raise_.expr = self.dispatch(raise_.expr) + self.dispatch(raise_.traceback) + self.dispatch(raise_.expr) # Handle bare name exceptions by converting any classes to instances. @@ -773,21 +778,20 @@ raise_.kw_args = {} raise_.star = None raise_.dstar = None - types = [] + types = set() for attr in self.namespace.types: if isinstance(attr.type, Class): self._visitInvoke(raise_, [attr], have_args=0) - types += self.namespace.types + types.update(self.namespace.types) else: types = self.namespace.types - combine(self.namespace.raises, types) - return raise_ + self.namespace.raises.update(types) def visitReleaseTemp(self, releasetemp): """ - Return the 'releasetemp' node, removing temporary variable information + Process the 'releasetemp' node, removing temporary variable information from the current namespace. """ @@ -798,16 +802,14 @@ raise AnnotationMessage, "Temporary store index '%s' not defined." % index except IndexError: pass #raise AnnotationMessage, "Temporary store index '%s' is empty." % index - return releasetemp def visitResetExc(self, resetexc): - self.namespace.raises = [] - return resetexc + self.namespace.raises = set() def visitReturn(self, return_): """ - Return the 'return_' node, processing any expression and obtaining type + Process the 'return_' node, processing any expression and obtaining type information to be accumulated in the current namespace's list of return types. A snapshot of the namespace is taken for the purposes of reconciling or merging namespaces where subprograms actually share @@ -815,11 +817,10 @@ """ if hasattr(return_, "expr"): - return_.expr = self.dispatch(return_.expr) - combine(self.namespace.returns, self.namespace.types) + self.dispatch(return_.expr) + self.namespace.returns.update(self.namespace.types) self.annotate(return_) self.namespace.snapshot() - return return_ visitReturnFromBlock = visitReturn visitReturnFromFunction = visitReturn @@ -827,15 +828,15 @@ def visitStoreAttr(self, storeattr): """ - Return the 'storeattr' node, processing the expression and target, and + Process the 'storeattr' node, processing the expression and target, and using the type information obtained to build records of legitimate writes to the stated attribute, along with "impossible" non-writes to the attribute. """ - storeattr.expr = self.dispatch(storeattr.expr) + self.dispatch(storeattr.expr) expr = self.namespace.types - storeattr.lvalue = self.dispatch(storeattr.lvalue) + self.dispatch(storeattr.lvalue) writes = {} non_writes = [] for attr in self.namespace.types: @@ -850,50 +851,46 @@ print "Unable to store attribute", storeattr.name, "given", self.namespace.types storeattr.writes = writes storeattr.non_writes = non_writes - return storeattr def visitStoreName(self, storename): """ - Return the 'storename' node, processing the expression on the node and + Process the 'storename' node, processing the expression on the node and associating the type information obtained with the stated name in the current namespace. """ - storename.expr = self.dispatch(storename.expr) + self.dispatch(storename.expr) self.namespace.store(storename.name, self.namespace.types) self.annotate(storename) - return storename def visitStoreTemp(self, storetemp): """ - Return the 'storetemp' node, processing the expression on the node and + Process the 'storetemp' node, processing the expression on the node and associating the type information obtained with a temporary variable in the current namespace. """ - storetemp.expr = self.dispatch(storetemp.expr) + self.dispatch(storetemp.expr) index = getattr(storetemp, "index", None) if not self.namespace.temp.has_key(index): self.namespace.temp[index] = [] self.namespace.temp[index].append(self.namespace.types) - return storetemp def visitSubprogram(self, subprogram): """ - Return the 'subprogram' node, processing its contents (a group of nodes + Process the 'subprogram' node, processing its contents (a group of nodes comprising the subprogram). """ - subprogram.code = self.dispatches(subprogram.code) - return subprogram + self.dispatches(subprogram.code) def visitTry(self, try_): """ - Return the 'try_' node, processing the body clause in its own namespace + Process the 'try_' node, processing the body clause in its own namespace derived from the current namespace, processing any handler clause using the namespace information accumulated in the body, and processing any else and finally clauses, attempting to supply each with appropriate @@ -902,7 +899,7 @@ is_module = self.namespace is self.module.namespace - try_.body = self.dispatches(try_.body) + self.dispatches(try_.body) # Save the namespace from the body. @@ -912,7 +909,7 @@ # Process the handler. if hasattr(try_, "handler"): - try_.handler = self.dispatches(try_.handler) + self.dispatches(try_.handler) # Save the namespace from the handler. @@ -935,8 +932,8 @@ # Empty the raised exceptions for the else clause. - self.namespace.raises = [] - try_.else_ = self.dispatches(try_.else_) + self.namespace.raises = set() + self.dispatches(try_.else_) self.namespace.raises = raises # Merge the namespaces. @@ -949,8 +946,7 @@ # Process the finally clause, if any. - try_.finally_ = self.dispatches(try_.finally_) - return try_ + self.dispatches(try_.finally_) def visitYield(self, yield_): raise NotImplementedError, "The yield statement is not currently supported." @@ -967,7 +963,7 @@ if not type.has_instance(node): instance = Instance() instance.namespace = Namespace() - instance.namespace.store("__class__", [Attribute(None, type)]) + instance.namespace.store("__class__", set([Attribute(None, type)])) type.add_instance(node, instance) else: instance = type.get_instance(node) @@ -1029,7 +1025,7 @@ # NOTE: within a method definition. if getattr(target, "name", None) is not None and not getattr(target, "is_method", 0): - namespace.store(target.name, [Attribute(None, target)]) + namespace.store(target.name, set([Attribute(None, target)])) # Process the subprogram. @@ -1070,9 +1066,9 @@ # Incorporate any raised exceptions. if not hasattr(invoke, "raises"): - invoke.raises = [] - combine(invoke.raises, target.raises) - combine(self.namespace.raises, target.raises) + invoke.raises = set() + invoke.raises.update(target.raises) + self.namespace.raises.update(target.raises) def process_args(self, invocation): @@ -1081,19 +1077,19 @@ any arguments were processed. """ - invocation.pos_args = self.dispatches(invocation.pos_args) - invocation.kw_args = self.dispatch_dict(invocation.kw_args) + self.dispatches(invocation.pos_args) + self.dispatch_dict(invocation.kw_args) # Get type information for star and dstar arguments. if invocation.star is not None: param, default = invocation.star - default = self.dispatch(default) + self.dispatch(default) invocation.star = param, default if invocation.dstar is not None: param, default = invocation.dstar - default = self.dispatch(default) + self.dispatch(default) invocation.dstar = param, default if invocation.pos_args or invocation.kw_args or invocation.star or invocation.dstar: @@ -1108,7 +1104,9 @@ given 'context' (which may be None). """ - if context is not None: + # NOTE: Support class methods! + + if context is not None and isinstance(context.type, Instance): pos_args = [Self(context)] + invocation.pos_args else: pos_args = invocation.pos_args @@ -1134,7 +1132,7 @@ if hasattr(arg, "types"): items.append((param, arg.types)) else: - items.append((param, [])) # Annotation has not succeeded. + items.append((param, set())) # Annotation has not succeeded. params = params[1:] else: star_args.append(arg) @@ -1147,13 +1145,14 @@ arg = kw_args[param] del kw_args[param] elif default is not None: - arg = self.dispatch(default) + self.dispatch(default) + arg = default else: raise AnnotationMessage, "No argument supplied in '%s' for parameter '%s'." % (subprogram, param) if hasattr(arg, "types"): items.append((param, arg.types)) else: - items.append((param, [])) # Annotation has not succeeded. + items.append((param, set())) # Annotation has not succeeded. params = params[1:] dstar_args = kw_args.items() @@ -1409,24 +1408,24 @@ """ self.names = {} - self.returns = [] - self.return_locals = [] - self.raises = [] + self.returns = set() + self.return_locals = set() + self.raises = set() self.temp = {} - self.types = [] + self.types = set() def set_types(self, types): "Set the current collection of 'types'." - self.types = types[:] + self.types = types.copy() def add(self, name, types): "Add to the entry with the given 'name' the specified 'types'." if self.names.has_key(name): - combine(self.names[name], types) + self.names[name].update(types) else: self.store(name, types) @@ -1434,7 +1433,7 @@ "Store in (or associate with) the given 'name' the specified 'types'." - self.names[name] = types[:] + self.names[name] = types.copy() __setitem__ = store @@ -1453,7 +1452,7 @@ "Revoke from the entry for the given 'name' the specified 'type'." - new_types = self.names[name][:] + new_types = self.names[name].copy() new_types.remove(type) self.names[name] = new_types @@ -1467,7 +1466,7 @@ "Revoke from the temporary variable 'index' the given 'type'." - new_types = self.temp[index][-1][:] + new_types = self.temp[index][-1].copy() new_types.remove(type) self.temp[index][-1] = new_types @@ -1481,15 +1480,15 @@ """ self.merge_items(namespace.names.items()) - combine(self.raises, namespace.raises) + self.raises.update(namespace.raises) if everything: - combine(self.returns, namespace.returns) - combine(self.return_locals, namespace.return_locals) + self.returns.update(namespace.returns) + self.return_locals.update(namespace.return_locals) for name, values in namespace.temp.items(): if values: if not self.temp.has_key(name) or not self.temp[name]: - self.temp[name] = [[]] - combine(self.temp[name][-1], values[-1]) + self.temp[name] = [set()] + self.temp[name][-1].update(values[-1]) def merge_items(self, items): @@ -1503,10 +1502,10 @@ "Merge the entry for the given 'name' and 'types' with this namespace." if not self.names.has_key(name): - self.names[name] = types[:] + self.names[name] = types.copy() else: existing = self.names[name] - combine(existing, types) + existing.update(types) def snapshot(self): @@ -1514,7 +1513,7 @@ namespace = Namespace() namespace.merge_namespace(self) - self.return_locals.append(namespace) + self.return_locals.add(namespace) def reset(self): @@ -1766,7 +1765,7 @@ try: while 1: s = raw_input("> ") - print eval(s) + print eval(s, vars) except EOFError: pass diff -r c8616d31e76c -r 5c20f017c8de simplified.py --- a/simplified.py Sun Apr 01 17:43:20 2007 +0200 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,776 +0,0 @@ -#!/usr/bin/env python - -""" -Simplified program nodes for easier type propagation and analysis. This module -contains nodes representing program instructions or operations, program -structure or organisation, and abstract program data. - -Copyright (C) 2006, 2007 Paul Boddie - -This software is free software; you can redistribute it and/or -modify it under the terms of the GNU General Public License as -published by the Free Software Foundation; either version 2 of -the License, or (at your option) any later version. - -This software is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public -License along with this library; see the file LICENCE.txt -If not, write to the Free Software Foundation, Inc., -51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA -""" - -from compiler.visitor import ASTVisitor -import sys - -# Location of the built-in libraries. -# NOTE: Change this if the package structure changes. - -import os - -libdir = os.path.join(os.path.split(__file__)[0], "lib") - -# Exceptions. - -class SimplifiedError(Exception): - - "An error in the annotation process." - - def __init__(self, exc, node, *args): - - """ - Initialise the error with an existing exception 'exc', the 'node' at - which this error occurs, along with additional optional arguments. - """ - - Exception.__init__(self, *args) - self.nodes = [node] - self.exc = exc - - def add(self, node): - - "Add the given 'node' to the path of nodes leading from the exception." - - self.nodes.append(node) - - def __str__(self): - - "Return a string showing the principal exception details." - - return "%s, %s" % (self.exc, self.nodes) - -# Unique name registration. - -class Naming: - - "Maintain records of unique names for each simple name." - - index_separator = "-" - - def __init__(self): - self.names = {} - - def get(self, obj): - return obj._unique_name - - def set(self, obj, name): - if hasattr(obj, "_unique_name"): - return - if not self.names.has_key(name): - self.names[name] = 0 - n = self.names[name] + 1 - self.names[name] = n - obj._unique_name = "%s%s%d" % (name, self.index_separator, n) - -naming = Naming() - -def name(obj, name): - - "Return a unique name for the given 'obj', indicating the base 'name'." - - naming.set(obj, name) - return naming.get(obj) - -# Named nodes are those which can be referenced in some way. - -class WithName: - - "Node naming." - - def __init__(self): - self._full_name = name(self, self.name or "$untitled") - - def full_name(self): - return self._full_name - -# Elementary visitor support. - -class Visitor(ASTVisitor): - - "A visitor base class." - - def __init__(self): - ASTVisitor.__init__(self) - - def default(self, node, *args): - raise SimplifiedError, (None, node) - - def dispatch(self, node, *args): - return ASTVisitor.dispatch(self, node, *args) - - def dispatches(self, nodes, *args): - results = [] - for node in nodes: - results.append(self.dispatch(node, *args)) - return results - - def dispatch_dict(self, d, *args): - results = {} - for name, node in d.items(): - results[name] = self.dispatch(node, *args) - return results - -# Simplified program nodes. - -class Node: - - """ - A result node with common attributes: - - original The original node from which this node was created. - defining Whether the node defines something in the original program. - name Any name involved (variable or attribute). - index Any index involved (temporary variable name). - value Any constant value. - ref Any reference to (for example) subprograms. - nstype Any indication of the namespace type involved in a name access. - - Expression-related attributes: - - expr Any contributing expression. - lvalue Any target expression. - test Any test expression in a conditional instruction. - - Invocation and subprogram attributes: - - args Any collection of argument nodes. - params Any collection of parameter nodes and defaults. - - Statement-grouping attributes: - - body Any conditional code depending on the success of a test. - else_ Any conditional code depending on the failure of a test. - handler Any exception handler code. - finally_ Any code which will be executed regardless. - code Any unconditional code. - choices Any choices which may be included in the final program. - """ - - common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" - expression_attributes = "expr", "lvalue", "test" - argument_attributes = "star", "dstar" - invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" - grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" - - def __init__(self, original=None, defining=0, **kw): - - """ - Initialise a program node with a link to an optional 'original' AST - node. An optional 'defining' parameter (if set to a true value), sets - this node as the defining node in the original. - """ - - self.original = original - self.defining = defining - self.copies = {} - - if self.original is not None and defining: - self.original._node = self - for name, value in kw.items(): - setattr(self, name, value) - - def __repr__(self): - - "Return a readable representation." - - if hasattr(self, "full_name"): - s = "%s '%s'" % (self.__class__.__name__, self.full_name()) - elif hasattr(self, "name"): - s = "%s '%s'" % (self.__class__.__name__, self.name) - elif hasattr(self, "index"): - s = "%s (%s)" % (self.__class__.__name__, self.index) - elif hasattr(self, "value"): - s = "%s %s" % (self.__class__.__name__, repr(self.value)) - elif hasattr(self, "ref"): - s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) - else: - s = "%s" % (self.__class__.__name__,) - - # Annotations. - - if hasattr(self, "types"): - return "%s -> %s" % (s, self.types) - else: - return s - - def _pprint(self, indent, continuation, s, stream=None): - - """ - Print, at the given 'indent' level, with the given 'continuation' text, - the string 's', either to the given, optional 'stream' or to standard - output, this node's "pretty" representation. - """ - - stream = stream or sys.stdout - if continuation: - print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s - else: - print >>stream, (" " * indent) + s - - def pprint(self, indent=0, continuation=None, stream=None): - - """ - Print, at the given, optional 'indent', with the given optional - 'continuation' text, either to the given, optional 'stream' or to - standard output, this node's "pretty" representation along with its - children and their "pretty" representation (and so on). - """ - - stream = stream or sys.stdout - self._pprint(indent, continuation, repr(self), stream) - - # Subprogram-related details. - - if hasattr(self, "params"): - for name, default in self.params: - self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) - if hasattr(self, "star") and self.star: - name, default = self.star - self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) - if hasattr(self, "dstar") and self.dstar: - name, default = self.dstar - self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) - if getattr(self, "internal", 0): - self._pprint(indent + 2, "( ", "internal", stream=stream) - if getattr(self, "structure", 0): - self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) - - # Expression-related details. - - if hasattr(self, "expr"): - self.expr.pprint(indent + 2, "- ", stream=stream) - if hasattr(self, "nodes"): - for node in self.nodes: - node.pprint(indent + 2, "- ", stream=stream) - if hasattr(self, "lvalue"): - self.lvalue.pprint(indent + 2, "->", stream=stream) - if hasattr(self, "nstype"): - self._pprint(indent + 2, "", self.nstype, stream=stream) - if hasattr(self, "args"): - for arg in self.pos_args: - arg.pprint(indent + 2, "( ", stream=stream) - for name, arg in self.kw_args.items(): - arg.pprint(indent + 2, "( ", stream=stream) - if hasattr(self, "star") and self.star: - self.star.pprint(indent + 2, "( ", stream=stream) - if hasattr(self, "dstar") and self.dstar: - self.dstar.pprint(indent + 2, "( ", stream=stream) - - # Statement-related details. - - if hasattr(self, "test"): - self.test.pprint(indent + 2, "? ", stream=stream) - for attr in self.grouping_attributes: - if hasattr(self, attr) and getattr(self, attr): - self._pprint(indent, "", "%s {" % attr, stream=stream) - for node in getattr(self, attr): - node.pprint(indent + 2, stream=stream) - self._pprint(indent, "", "}", stream=stream) - - # Annotations. - - if hasattr(self, "accesses"): - self._pprint(indent, "", "--------", stream=stream) - for ref, attributes in self.accesses.items(): - self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) - self._pprint(indent, "", "--------", stream=stream) - if hasattr(self, "writes"): - self._pprint(indent, "", "--------", stream=stream) - for ref, attribute in self.writes.items(): - self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) - self._pprint(indent, "", "--------", stream=stream) - - # Node discovery functions. - - def active(self): - - "Return the active copies of this node or a list containing this node." - - return self.copies.values() or [self] - - # Node manipulation functions. - - def copy(self, instance=None, new_name=None): - - """ - Perform a deep copy of the node, optionally specifying the 'instance' - for whom the copy has been requested and a 'new_name' for the copied - node. Return new unannotated copies of the node and its descendants. - """ - - # Copy the common attributes of this node. - - common = {} - for attr in self.common_attributes: - if hasattr(self, attr): - common[attr] = getattr(self, attr) - - # Add new attributes specially for copies. - - common["instance"] = instance - - if new_name is not None: - common["copy_of"] = self - common["name"] = new_name - - # Instantiate the copy, avoiding side-effects with original and defining. - - node = self.__class__(**common) - node.defining = self.defining - - # Add links to copies from originals. - - self.copies[instance] = node - - # Copy attributes of different types. - - for attr in self.expression_attributes: - if hasattr(self, attr): - n = getattr(self, attr) - if n is None: - n2 = n - else: - n2 = n.copy(instance) - setattr(node, attr, n2) - - for attr in self.argument_attributes: - if hasattr(self, attr): - t = getattr(self, attr) - if t is None: - t2 = t - else: - name, n = t - n2 = n.copy(instance) - t2 = name, n2 - setattr(node, attr, t2) - - for attr in self.invocation_attributes: - if hasattr(self, attr): - l = getattr(self, attr) - l2 = [] - for name, n in l: - if n is None: - l2.append((name, n)) - else: - l2.append((name, n.copy(instance))) - setattr(node, attr, l2) - - for attr in self.grouping_attributes: - if hasattr(self, attr): - l = getattr(self, attr) - setattr(node, attr, [n.copy(instance) for n in l]) - - # Arguments are usually processed further - "args" is useless. - - if hasattr(self, "pos_args"): - node.pos_args = [n.copy(instance) for n in self.pos_args] - - if hasattr(self, "kw_args"): - node.kw_args = {} - for name, n in self.kw_args.items(): - node.kw_args[name] = n.copy(instance) - - return node - -# Comparable nodes based on naming. - -class Comparable(Node): - - "Comparable nodes implementing the 'full_name' method." - - def __eq__(self, other): - # NOTE: Single instance: all instances are the same - # NOTE: Multiple instances: all instances are different - if hasattr(other, "full_name"): - return self.full_name() == other.full_name() - else: - return NotImplemented - - def __hash__(self): - return id(self) - -# These are the supported "operations" described by simplified program nodes. - -class Pass(Node): "A placeholder node corresponding to pass." -class Assign(Node): "A grouping node for assignment-related operations." -class Keyword(Node): "A grouping node for keyword arguments." -class Global(Node): "A global name designator." -class Import(Node): "A module import operation." -class LoadTemp(Node): "Load a previously-stored temporary value." -class LoadName(Node): "Load a named object." -class LoadAttr(Node): "Load an object attribute." -class LoadRef(Node): "Load a reference, typically a subprogram or a constant." -class LoadExc(Node): "Load a handled exception." -class ResetExc(Node): "Reset the exception state." -class StoreTemp(Node): "Store a temporary value." -class StoreName(Node): "Associate a name with an object." -class StoreAttr(Node): "Associate an object's attribute with a value." -class ReleaseTemp(Node): "Release a temporary value." -class Try(Node): "A try...except...else...finally grouping node." -class Raise(Node): "An exception raising node." -class Not(Node): "A negation of an expression." -class CheckType(Node): "Check a value's type from a list of choices." - -# There are two types of return node: return from function and return from -# block. - -class Return(Node): - - "Return an evaluated expression." - - pass - -class ReturnFromFunction(Return): - pass - -class ReturnFromBlock(Return): - pass - -# NOTE: Not actually supported. -# Additionally, yield statements act like return statements for the purposes -# of this system. - -class Yield(ReturnFromFunction): - pass - -# Some behaviour is set as the default in conditional nodes but may be -# overridden. - -class Conditional(Node): - - "A conditional node consisting of a test and outcomes." - - def __init__(self, *args, **kw): - self.isolate_test = 0 - Node.__init__(self, *args, **kw) - -# Invocations involve some more work to process calculated attributes. - -class Invoke(Node): - - "An invocation." - - pass - -class InvokeFunction(Invoke): - - "A function or method invocation." - - def __init__(self, *args, **kw): - self.args = [] - self.star = None - self.dstar = None - Invoke.__init__(self, *args, **kw) - self.set_args(self.args) - self.share_locals = 0 - - def set_args(self, args): - - "Sort the 'args' into positional and keyword arguments." - - self.pos_args = [] - self.kw_args = {} - add_kw = 0 - for arg in args: - if not add_kw: - if not isinstance(arg, Keyword): - self.pos_args.append(arg) - else: - add_kw = 1 - if add_kw: - if isinstance(arg, Keyword): - self.kw_args[arg.name] = arg.expr - else: - raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self - -class InvokeRef(Invoke): - - "A block or loop invocation." - - def __init__(self, *args, **kw): - self.share_locals = 1 - Invoke.__init__(self, *args, **kw) - -# Program structure nodes. - -class Subprogram(Node, WithName): - - "A subprogram: functions, methods and loops." - - def __init__(self, *args, **kw): - Node.__init__(self, *args, **kw) - WithName.__init__(self) - self.returns = [] - self.return_locals = [] - self.raises = [] - -class Module(Comparable): - - "A Python module." - - def full_name(self): - return "module %s" % self.name - -# Special non-program nodes. - -class Structure(Comparable): "A non-program node containing some kind of namespace." - -class _Class(Structure, WithName): - - "A Python class." - - def __init__(self, *args, **kw): - Structure.__init__(self, *args, **kw) - WithName.__init__(self) - - def full_name(self): - return "class %s" % self._full_name - -class SingleInstanceClass(_Class): - - "A Python class." - - def __init__(self, *args, **kw): - _Class.__init__(self, *args, **kw) - self.instance = None - - def has_instance(self, node): - return self.instance is not None - - def add_instance(self, node, instance): - self.instance = instance - - def get_instance(self, node): - return self.instance - - def get_instance_name(self, instance): - return self._full_name - - # Attribute propagation. - - def get_attribute_for_instance(self, attribute, instance): - return attribute - -class MultipleInstanceClass(_Class): - - "A Python class." - - def __init__(self, *args, **kw): - _Class.__init__(self, *args, **kw) - self.instances = {} - self.attributes_for_instances = {} - - def _get_key(self, node): - return id(getattr(node, "original", None)) # self.module.original - - def has_instance(self, node): - return self.instances.has_key(self._get_key(node)) - - def add_instance(self, node, instance): - self.instances[self._get_key(node)] = instance - - def get_instance(self, node): - return self.instances[self._get_key(node)] - - def get_instance_name(self, instance): - return name(instance, self._full_name) - - # Attribute propagation. - - def get_attribute_for_instance(self, attribute, instance): - - # Create specialised methods. - - if isinstance(attribute.type, Subprogram): - subprogram = attribute.type - - # Each instance may have its own version of the subprogram. - - key = (subprogram, instance) - if not self.attributes_for_instances.has_key(key): - new_subprogram = subprogram.copy(instance, subprogram.full_name()) - subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram - self.attributes_for_instances[key] = Attribute(attribute.context, new_subprogram) - print "New subprogram", new_subprogram, "for", key - - return self.attributes_for_instances[key] - - # The original nodes are returned for other attributes. - - else: - return attribute - -class SelectiveMultipleInstanceClass(MultipleInstanceClass): - - "A Python class which provides multiple instances depending on the class." - - def _get_key(self, node): - if self.namespace.has_key("__atomic__"): - return id(self) - else: - return MultipleInstanceClass._get_key(self, node) - -class ProlificMultipleInstanceClass(MultipleInstanceClass): - - """ - A Python class which provides multiple instances for different versions of - methods. In order to avoid unbounded instance production (since new - instances cause new copies of methods which in turn would cause new - instances), a relations dictionary is maintained which attempts to map - "requesting instances" to existing instances, suggesting such instances in - preference to new ones. - """ - - def __init__(self, *args, **kw): - MultipleInstanceClass.__init__(self, *args, **kw) - self.instance_relations = {} - - def _get_key(self, node): - if self.namespace.has_key("__atomic__"): - return id(self) - else: - return id(node) - - def has_instance(self, node): - requesting_instance = getattr(node, "instance", None) - #return requesting_instance is not None and requesting_instance.get_class() is self or \ - return self.instance_relations.has_key(requesting_instance) or self.instances.has_key(self._get_key(node)) - - def add_instance(self, node, instance): - requesting_instance = getattr(node, "instance", None) - print "New instance", instance, "for", id(node), requesting_instance - self.instances[self._get_key(node)] = instance - if requesting_instance is not None: - self.instance_relations[requesting_instance] = instance - requesting_instance.get_class().instance_relations[instance] = requesting_instance - - def get_instance(self, node): - requesting_instance = getattr(node, "instance", None) - #if requesting_instance is not None and requesting_instance.get_class() is self: - # return requesting_instance - return self.instance_relations.get(requesting_instance) or self.instances[self._get_key(node)] - -class Instance(Structure): - - "An instance." - - def full_name(self): - return self.get_class().get_instance_name(self) - - def get_class(self): - return self.namespace.load("__class__")[0].type - - def __repr__(self): - return "Instance of type '%s'" % self.full_name() - - def __eq__(self, other): - # NOTE: Single instance: all instances are the same - # NOTE: Multiple instances: all instances are different - return self.full_name() == other.full_name() - - def __hash__(self): - return id(self) - -class Constant(Instance): - - "A constant initialised with a type name for future processing." - - def __init__(self, *args, **kw): - Instance.__init__(self, *args, **kw) - self.typename = self.value.__class__.__name__ - - # NOTE: Hacked full_name avoiding instantiation ordering issues: - # NOTE: initialise built-in types, initialise built-in constants. - - #def full_name(self): - # try: - # return Instance.full_name(self) - # except KeyError: - # return self.typename + "-c" - -class Attribute: - - """ - An attribute abstraction, indicating the type of the attribute along with - its context or origin. - """ - - def __init__(self, context, type): - self.context = context - self.type = type - - def __eq__(self, other): - return hasattr(other, "type") and other.type == self.type or other == self.type - - def __repr__(self): - return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) - - def __hash__(self): - return id(self) - -# Additional program and AST nodes. - -class Self: - - """ - A program node encapsulating object/context information in an argument list. - This is not particularly like Attribute, Class, Instance or other such - things, since it actually appears in the program representation. - """ - - def __init__(self, attribute): - self.types = [attribute] - -class Op: - - "A replacement AST node representing an operation in a Compare construct." - - def __init__(self, name, expr): - self.name = name - self.expr = expr - -# Configuration setting. - -Class = SingleInstanceClass -#Class = MultipleInstanceClass - -def set_single_instance_mode(): - global Class - Class = SingleInstanceClass - -def set_multiple_instance_mode(): - global Class - Class = MultipleInstanceClass - -def set_selective_multiple_instance_mode(): - global Class - Class = SelectiveMultipleInstanceClass - -def set_prolific_multiple_instance_mode(): - global Class - Class = ProlificMultipleInstanceClass - -# vim: tabstop=4 expandtab shiftwidth=4 diff -r c8616d31e76c -r 5c20f017c8de simplified/__init__.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/simplified/__init__.py Fri Apr 06 00:53:18 2007 +0200 @@ -0,0 +1,37 @@ +#!/usr/bin/env python + +""" +Simplified program representation. + +Copyright (C) 2006, 2007 Paul Boddie + +This software is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 2 of +the License, or (at your option) any later version. + +This software is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public +License along with this library; see the file LICENCE.txt +If not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA +""" + +__version__ = "0.1" + +from simplified.ast import * +from simplified.data import * +from simplified.program import * +from simplified.utils import * +import os + +# Location of the built-in libraries. +# NOTE: Change this if the package structure changes. + +libdir = os.path.join(os.path.split(os.path.split(__file__)[0])[0], "lib") + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r c8616d31e76c -r 5c20f017c8de simplified/ast.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/simplified/ast.py Fri Apr 06 00:53:18 2007 +0200 @@ -0,0 +1,44 @@ +#!/usr/bin/env python + +""" +Additional program AST nodes. + +Copyright (C) 2006, 2007 Paul Boddie + +This software is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 2 of +the License, or (at your option) any later version. + +This software is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public +License along with this library; see the file LICENCE.txt +If not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA +""" + +class Self: + + """ + A program node encapsulating object/context information in an argument list. + This is not particularly like Attribute, Class, Instance or other such + things, since it actually appears in the program representation. + """ + + def __init__(self, attribute): + self.types = set() + self.types.add(attribute) + +class Op: + + "A replacement AST node representing an operation in a Compare construct." + + def __init__(self, name, expr): + self.name = name + self.expr = expr + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r c8616d31e76c -r 5c20f017c8de simplified/data.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/simplified/data.py Fri Apr 06 00:53:18 2007 +0200 @@ -0,0 +1,237 @@ +#!/usr/bin/env python + +""" +Simplified program data. + +Copyright (C) 2006, 2007 Paul Boddie + +This software is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 2 of +the License, or (at your option) any later version. + +This software is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public +License along with this library; see the file LICENCE.txt +If not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA +""" + +from simplified.utils import Structure, WithName, name + +# Special non-program nodes. + +class _Class(Structure, WithName): + + "A Python class." + + def __init__(self, *args, **kw): + Structure.__init__(self, *args, **kw) + WithName.__init__(self) + + def full_name(self): + return "class %s" % self._full_name + +class SingleInstanceClass(_Class): + + "A Python class." + + def __init__(self, *args, **kw): + _Class.__init__(self, *args, **kw) + self.instance = None + + def has_instance(self, node): + return self.instance is not None + + def add_instance(self, node, instance): + self.instance = instance + + def get_instance(self, node): + return self.instance + + def get_instance_name(self, instance): + return self._full_name + + # Attribute propagation. + + def get_attribute_for_instance(self, attribute, instance): + return attribute + +class MultipleInstanceClass(_Class): + + "A Python class." + + def __init__(self, *args, **kw): + _Class.__init__(self, *args, **kw) + self.instances = {} + self.attributes_for_instances = {} + + def _get_key(self, node): + return id(getattr(node, "original", None)) # self.module.original + + def has_instance(self, node): + return self.instances.has_key(self._get_key(node)) + + def add_instance(self, node, instance): + self.instances[self._get_key(node)] = instance + + def get_instance(self, node): + return self.instances[self._get_key(node)] + + def get_instance_name(self, instance): + return name(instance, self._full_name) + + # Attribute propagation. + + def get_attribute_for_instance(self, attribute, instance): + + # Create specialised methods. + + if isinstance(attribute.type, Subprogram): + subprogram = attribute.type + + # Each instance may have its own version of the subprogram. + + key = (subprogram, instance) + if not self.attributes_for_instances.has_key(key): + new_subprogram = subprogram.copy(instance, subprogram.full_name()) + subprogram.module.simplifier.subnames[new_subprogram.full_name()] = new_subprogram + self.attributes_for_instances[key] = Attribute(attribute.context, new_subprogram) + print "New subprogram", new_subprogram, "for", key + + return self.attributes_for_instances[key] + + # The original nodes are returned for other attributes. + + else: + return attribute + +class SelectiveMultipleInstanceClass(MultipleInstanceClass): + + "A Python class which provides multiple instances depending on the class." + + def _get_key(self, node): + if self.namespace.has_key("__atomic__"): + return id(self) + else: + return MultipleInstanceClass._get_key(self, node) + +class ProlificMultipleInstanceClass(MultipleInstanceClass): + + """ + A Python class which provides multiple instances for different versions of + methods. In order to avoid unbounded instance production (since new + instances cause new copies of methods which in turn would cause new + instances), a relations dictionary is maintained which attempts to map + "requesting instances" to existing instances, suggesting such instances in + preference to new ones. + """ + + def __init__(self, *args, **kw): + MultipleInstanceClass.__init__(self, *args, **kw) + self.instance_relations = {} + + def _get_key(self, node): + if self.namespace.has_key("__atomic__"): + return id(self) + else: + return id(node) + + def has_instance(self, node): + requesting_instance = getattr(node, "instance", None) + #return requesting_instance is not None and requesting_instance.get_class() is self or \ + return self.instance_relations.has_key(requesting_instance) or self.instances.has_key(self._get_key(node)) + + def add_instance(self, node, instance): + requesting_instance = getattr(node, "instance", None) + print "New instance", instance, "for", id(node), requesting_instance + self.instances[self._get_key(node)] = instance + if requesting_instance is not None: + self.instance_relations[requesting_instance] = instance + requesting_instance.get_class().instance_relations[instance] = requesting_instance + + def get_instance(self, node): + requesting_instance = getattr(node, "instance", None) + #if requesting_instance is not None and requesting_instance.get_class() is self: + # return requesting_instance + return self.instance_relations.get(requesting_instance) or self.instances[self._get_key(node)] + +class Instance(Structure): + + "An instance." + + def full_name(self): + return self.get_class().get_instance_name(self) + + def get_class(self): + for n in self.namespace.load("__class__"): + return n.type + else: + raise ValueError, "__class__" + + def __repr__(self): + return "Instance of type '%s'" % self.full_name() + + def __eq__(self, other): + # NOTE: Single instance: all instances are the same + # NOTE: Multiple instances: all instances are different + return self.full_name() == other.full_name() + + def __hash__(self): + return id(self) + +class Constant: + + "A constant initialised with a type name for future processing." + + def __init__(self, name, value): + self.name = name + self.value = value + self.typename = self.value.__class__.__name__ + +class Attribute: + + """ + An attribute abstraction, indicating the type of the attribute along with + its context or origin. + """ + + def __init__(self, context, type): + self.context = context + self.type = type + + def __eq__(self, other): + return hasattr(other, "type") and other.type == self.type or other == self.type + + def __repr__(self): + return "Attribute(%s, %s)" % (repr(self.context), repr(self.type)) + + def __hash__(self): + return id(self.type) + +# Configuration setting. + +Class = SingleInstanceClass +#Class = MultipleInstanceClass + +def set_single_instance_mode(): + global Class + Class = SingleInstanceClass + +def set_multiple_instance_mode(): + global Class + Class = MultipleInstanceClass + +def set_selective_multiple_instance_mode(): + global Class + Class = SelectiveMultipleInstanceClass + +def set_prolific_multiple_instance_mode(): + global Class + Class = ProlificMultipleInstanceClass + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r c8616d31e76c -r 5c20f017c8de simplified/program.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/simplified/program.py Fri Apr 06 00:53:18 2007 +0200 @@ -0,0 +1,407 @@ +#!/usr/bin/env python + +""" +Simplified program nodes for easier type propagation and analysis. This module +contains nodes representing program instructions or operations, program +structure or organisation, and abstract program data. + +Copyright (C) 2006, 2007 Paul Boddie + +This software is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 2 of +the License, or (at your option) any later version. + +This software is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public +License along with this library; see the file LICENCE.txt +If not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA +""" + +from simplified.utils import Structure, WithName, name +import sys + +# Simplified program nodes. + +class Node: + + """ + A result node with common attributes: + + original The original node from which this node was created. + defining Whether the node defines something in the original program. + name Any name involved (variable or attribute). + index Any index involved (temporary variable name). + value Any constant value. + ref Any reference to (for example) subprograms. + nstype Any indication of the namespace type involved in a name access. + + Expression-related attributes: + + expr Any contributing expression. + lvalue Any target expression. + test Any test expression in a conditional instruction. + + Invocation and subprogram attributes: + + args Any collection of argument nodes. + params Any collection of parameter nodes and defaults. + + Statement-grouping attributes: + + body Any conditional code depending on the success of a test. + else_ Any conditional code depending on the failure of a test. + handler Any exception handler code. + finally_ Any code which will be executed regardless. + code Any unconditional code. + choices Any choices which may be included in the final program. + """ + + common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" + expression_attributes = "expr", "lvalue", "test" + argument_attributes = "star", "dstar" + invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" + grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" + + def __init__(self, original=None, defining=0, **kw): + + """ + Initialise a program node with a link to an optional 'original' AST + node. An optional 'defining' parameter (if set to a true value), sets + this node as the defining node in the original. + """ + + self.original = original + self.defining = defining + self.copies = {} + + if self.original is not None and defining: + self.original._node = self + for name, value in kw.items(): + setattr(self, name, value) + + # Annotations. + + self.types = set() + + def __repr__(self): + + "Return a readable representation." + + if hasattr(self, "full_name"): + s = "%s '%s'" % (self.__class__.__name__, self.full_name()) + elif hasattr(self, "name"): + s = "%s '%s'" % (self.__class__.__name__, self.name) + elif hasattr(self, "index"): + s = "%s (%s)" % (self.__class__.__name__, self.index) + elif hasattr(self, "value"): + s = "%s %s" % (self.__class__.__name__, repr(self.value)) + elif hasattr(self, "ref"): + s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) + else: + s = "%s" % (self.__class__.__name__,) + + # Annotations. + + if self.types: + return "%s -> %s" % (s, self.types) + else: + return s + + def _pprint(self, indent, continuation, s, stream=None): + + """ + Print, at the given 'indent' level, with the given 'continuation' text, + the string 's', either to the given, optional 'stream' or to standard + output, this node's "pretty" representation. + """ + + stream = stream or sys.stdout + if continuation: + print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s + else: + print >>stream, (" " * indent) + s + + def pprint(self, indent=0, continuation=None, stream=None): + + """ + Print, at the given, optional 'indent', with the given optional + 'continuation' text, either to the given, optional 'stream' or to + standard output, this node's "pretty" representation along with its + children and their "pretty" representation (and so on). + """ + + stream = stream or sys.stdout + self._pprint(indent, continuation, repr(self), stream) + + # Subprogram-related details. + + if hasattr(self, "params"): + for name, default in self.params: + self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) + if hasattr(self, "star") and self.star: + name, default = self.star + self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) + if hasattr(self, "dstar") and self.dstar: + name, default = self.dstar + self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) + if getattr(self, "internal", 0): + self._pprint(indent + 2, "( ", "internal", stream=stream) + if getattr(self, "structure", 0): + self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) + + # Expression-related details. + + if hasattr(self, "expr"): + self.expr.pprint(indent + 2, "- ", stream=stream) + if hasattr(self, "nodes"): + for node in self.nodes: + node.pprint(indent + 2, "- ", stream=stream) + if hasattr(self, "lvalue"): + self.lvalue.pprint(indent + 2, "->", stream=stream) + if hasattr(self, "nstype"): + self._pprint(indent + 2, "", self.nstype, stream=stream) + if hasattr(self, "args"): + for arg in self.pos_args: + arg.pprint(indent + 2, "( ", stream=stream) + for name, arg in self.kw_args.items(): + arg.pprint(indent + 2, "( ", stream=stream) + if hasattr(self, "star") and self.star: + self.star.pprint(indent + 2, "( ", stream=stream) + if hasattr(self, "dstar") and self.dstar: + self.dstar.pprint(indent + 2, "( ", stream=stream) + + # Statement-related details. + + if hasattr(self, "test"): + self.test.pprint(indent + 2, "? ", stream=stream) + for attr in self.grouping_attributes: + if hasattr(self, attr) and getattr(self, attr): + self._pprint(indent, "", "%s {" % attr, stream=stream) + for node in getattr(self, attr): + node.pprint(indent + 2, stream=stream) + self._pprint(indent, "", "}", stream=stream) + + # Annotations. + + if hasattr(self, "accesses"): + self._pprint(indent, "", "--------", stream=stream) + for ref, attributes in self.accesses.items(): + self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) + self._pprint(indent, "", "--------", stream=stream) + if hasattr(self, "writes"): + self._pprint(indent, "", "--------", stream=stream) + for ref, attribute in self.writes.items(): + self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) + self._pprint(indent, "", "--------", stream=stream) + + # Node discovery functions. + + def active(self): + + "Return the active copies of this node or a list containing this node." + + return self.copies.values() or [self] + + # Node manipulation functions. + + def copy(self, instance=None, new_name=None): + + """ + Perform a deep copy of the node, optionally specifying the 'instance' + for whom the copy has been requested and a 'new_name' for the copied + node. Return new unannotated copies of the node and its descendants. + """ + + # Copy the common attributes of this node. + + common = {} + for attr in self.common_attributes: + if hasattr(self, attr): + common[attr] = getattr(self, attr) + + # Add new attributes specially for copies. + + common["instance"] = instance + + if new_name is not None: + common["copy_of"] = self + common["name"] = new_name + + # Instantiate the copy, avoiding side-effects with original and defining. + + node = self.__class__(**common) + node.defining = self.defining + + # Add links to copies from originals. + + self.copies[instance] = node + + # Copy attributes of different types. + + for attr in self.expression_attributes: + if hasattr(self, attr): + n = getattr(self, attr) + if n is None: + n2 = n + else: + n2 = n.copy(instance) + setattr(node, attr, n2) + + for attr in self.argument_attributes: + if hasattr(self, attr): + t = getattr(self, attr) + if t is None: + t2 = t + else: + name, n = t + n2 = n.copy(instance) + t2 = name, n2 + setattr(node, attr, t2) + + for attr in self.invocation_attributes: + if hasattr(self, attr): + l = getattr(self, attr) + l2 = [] + for name, n in l: + if n is None: + l2.append((name, n)) + else: + l2.append((name, n.copy(instance))) + setattr(node, attr, l2) + + for attr in self.grouping_attributes: + if hasattr(self, attr): + l = getattr(self, attr) + setattr(node, attr, [n.copy(instance) for n in l]) + + # Arguments are usually processed further - "args" is useless. + + if hasattr(self, "pos_args"): + node.pos_args = [n.copy(instance) for n in self.pos_args] + + if hasattr(self, "kw_args"): + node.kw_args = {} + for name, n in self.kw_args.items(): + node.kw_args[name] = n.copy(instance) + + return node + +# These are the supported "operations" described by simplified program nodes. + +class Pass(Node): "A placeholder node corresponding to pass." +class Assign(Node): "A grouping node for assignment-related operations." +class Keyword(Node): "A grouping node for keyword arguments." +class Global(Node): "A global name designator." +class Import(Node): "A module import operation." +class LoadTemp(Node): "Load a previously-stored temporary value." +class LoadName(Node): "Load a named object." +class LoadAttr(Node): "Load an object attribute." +class LoadRef(Node): "Load a reference, typically a subprogram or a constant." +class LoadExc(Node): "Load a handled exception." +class ResetExc(Node): "Reset the exception state." +class StoreTemp(Node): "Store a temporary value." +class StoreName(Node): "Associate a name with an object." +class StoreAttr(Node): "Associate an object's attribute with a value." +class ReleaseTemp(Node): "Release a temporary value." +class Try(Node): "A try...except...else...finally grouping node." +class Raise(Node): "An exception raising node." +class Not(Node): "A negation of an expression." +class CheckType(Node): "Check a value's type from a list of choices." +class Return(Node): "Return an evaluated expression." +class Invoke(Node): "An invocation." + +# There are two types of return node: return from function and return from +# block. + +class ReturnFromFunction(Return): + pass + +class ReturnFromBlock(Return): + pass + +# NOTE: Not actually supported. +# Additionally, yield statements act like return statements for the purposes +# of this system. + +class Yield(ReturnFromFunction): + pass + +# Some behaviour is set as the default in conditional nodes but may be +# overridden. + +class Conditional(Node): + + "A conditional node consisting of a test and outcomes." + + def __init__(self, *args, **kw): + self.isolate_test = 0 + Node.__init__(self, *args, **kw) + +# Invocations involve some more work to process calculated attributes. + +class InvokeFunction(Invoke): + + "A function or method invocation." + + def __init__(self, *args, **kw): + self.args = [] + self.star = None + self.dstar = None + Invoke.__init__(self, *args, **kw) + self.set_args(self.args) + self.share_locals = 0 + + def set_args(self, args): + + "Sort the 'args' into positional and keyword arguments." + + self.pos_args = [] + self.kw_args = {} + add_kw = 0 + for arg in args: + if not add_kw: + if not isinstance(arg, Keyword): + self.pos_args.append(arg) + else: + add_kw = 1 + if add_kw: + if isinstance(arg, Keyword): + self.kw_args[arg.name] = arg.expr + else: + raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self + +class InvokeRef(Invoke): + + "A block or loop invocation." + + def __init__(self, *args, **kw): + self.share_locals = 1 + Invoke.__init__(self, *args, **kw) + +# Program structure nodes. + +class Module(Node, Structure): + + "A Python module." + + def full_name(self): + return "module %s" % self.name + +class Subprogram(Node, WithName): + + "A subprogram: functions, methods and loops." + + def __init__(self, *args, **kw): + Node.__init__(self, *args, **kw) + WithName.__init__(self) + self.raises = set() + self.returns = set() + self.return_locals = set() + +# vim: tabstop=4 expandtab shiftwidth=4 diff -r c8616d31e76c -r 5c20f017c8de simplified/utils.py --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/simplified/utils.py Fri Apr 06 00:53:18 2007 +0200 @@ -0,0 +1,167 @@ +#!/usr/bin/env python + +""" +Simplified program utilities. + +Copyright (C) 2006, 2007 Paul Boddie + +This software is free software; you can redistribute it and/or +modify it under the terms of the GNU General Public License as +published by the Free Software Foundation; either version 2 of +the License, or (at your option) any later version. + +This software is distributed in the hope that it will be useful, +but WITHOUT ANY WARRANTY; without even the implied warranty of +MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +GNU General Public License for more details. + +You should have received a copy of the GNU General Public +License along with this library; see the file LICENCE.txt +If not, write to the Free Software Foundation, Inc., +51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA +""" + +from compiler.visitor import ASTVisitor + +# Exceptions. + +class SimplifiedError(Exception): + + "An error in the annotation process." + + def __init__(self, exc, node, *args): + + """ + Initialise the error with an existing exception 'exc', the 'node' at + which this error occurs, along with additional optional arguments. + """ + + Exception.__init__(self, *args) + self.nodes = [node] + self.exc = exc + + def add(self, node): + + "Add the given 'node' to the path of nodes leading from the exception." + + self.nodes.append(node) + + def __str__(self): + + "Return a string showing the principal exception details." + + return "%s, %s" % (self.exc, self.nodes) + +# Elementary visitor support. + +class Visitor(ASTVisitor): + + "A visitor base class." + + def __init__(self): + ASTVisitor.__init__(self) + + def default(self, node, *args): + raise SimplifiedError, (None, node) + + def dispatch(self, node, *args): + return ASTVisitor.dispatch(self, node, *args) + + def dispatches(self, nodes, *args): + results = [] + for node in nodes: + results.append(self.dispatch(node, *args)) + return results + + def dispatch_dict(self, d, *args): + results = {} + for name, node in d.items(): + results[name] = self.dispatch(node, *args) + return results + +# Unique name registration. + +class Naming: + + "Maintain records of unique names for each simple name." + + index_separator = "-" + + def __init__(self): + self.names = {} + + def get(self, obj): + return obj._unique_name + + def set(self, obj, name): + if hasattr(obj, "_unique_name"): + return + if not self.names.has_key(name): + self.names[name] = 0 + n = self.names[name] + 1 + self.names[name] = n + obj._unique_name = "%s%s%d" % (name, self.index_separator, n) + +def name(obj, name): + + "Return a unique name for the given 'obj', indicating the base 'name'." + + naming.set(obj, name) + return naming.get(obj) + +# Naming singleton. + +naming = Naming() + +# Named nodes are those which can be referenced in some way. + +class WithName: + + "Node naming." + + def __init__(self): + + "Initialise the object's full name." + + self._full_name = name(self, self.name or "$untitled") + + def full_name(self): + + "Return the object's full name." + + return self._full_name + +# Comparable nodes based on naming. + +class Comparable: + + "Comparable nodes implementing the 'full_name' method." + + def __eq__(self, other): + + "This object is equal to 'other' if the full names are the same." + + # NOTE: Single instance: all instances are the same + # NOTE: Multiple instances: all instances are different + if hasattr(other, "full_name"): + return self.full_name() == other.full_name() + else: + return NotImplemented + + def __hash__(self): + + "The hash of this object is based on its full name." + + return hash(self.full_name()) + +# Structure nodes indicating namespace-bearing objects. + +class Structure(Comparable): + + "A non-program node containing some kind of namespace." + + def __init__(self, **kw): + for name, value in kw.items(): + setattr(self, name, value) + +# vim: tabstop=4 expandtab shiftwidth=4