1.1 --- a/annotate.py Sun Jul 23 23:56:11 2006 +0200
1.2 +++ b/annotate.py Sun Jul 23 23:57:13 2006 +0200
1.3 @@ -1,7 +1,9 @@
1.4 #!/usr/bin/env python
1.5
1.6 """
1.7 -Traverse and annotate simplified AST structures.
1.8 +Annotate simplified AST structures. The code in this module operates upon nodes
1.9 +which are produced when simplifying AST node trees originating from the compiler
1.10 +module.
1.11
1.12 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
1.13
1.14 @@ -24,7 +26,33 @@
1.15 from simplified import *
1.16 import compiler
1.17
1.18 +class System:
1.19 +
1.20 + "A class maintaining the state of the annotation system."
1.21 +
1.22 + def __init__(self):
1.23 + self.count = 0
1.24 + def init(self, node):
1.25 + if not hasattr(node, "types"):
1.26 + node.types = []
1.27 + def annotate(self, node, types):
1.28 + self.init(node)
1.29 + for type in types:
1.30 + if type not in node.types:
1.31 + node.types.append(type)
1.32 + self.count += 1
1.33 +
1.34 +system = System()
1.35 +
1.36 +# Namespaces and related abstractions.
1.37 +
1.38 class Namespace:
1.39 +
1.40 + """
1.41 + A local namespace which may either relate to a genuine set of function
1.42 + locals or the initialisation of a structure.
1.43 + """
1.44 +
1.45 def __init__(self, local_is_structure=0):
1.46 if local_is_structure:
1.47 self.local = "structure"
1.48 @@ -62,7 +90,10 @@
1.49 return self.names[name]
1.50
1.51 def merge(self, namespace):
1.52 - for name, types in namespace.names.items():
1.53 + self.merge_items(namespace.names.items())
1.54 +
1.55 + def merge_items(self, items):
1.56 + for name, types in items:
1.57 if not self.names.has_key(name):
1.58 self.names[name] = types
1.59 else:
1.60 @@ -71,35 +102,56 @@
1.61 if type not in existing:
1.62 existing.append(type)
1.63
1.64 -class System:
1.65 - def __init__(self):
1.66 - self.count = 0
1.67 - def init(self, node):
1.68 - if not hasattr(node, "types"):
1.69 - node.types = []
1.70 - def annotate(self, node, types):
1.71 - for type in types:
1.72 - if type not in node.types:
1.73 - node.types.append(type)
1.74 - self.count += 1
1.75 +class Attribute:
1.76 +
1.77 + """
1.78 + An attribute abstraction, indicating the type of the attribute along with
1.79 + its context or origin.
1.80 + """
1.81 +
1.82 + def __init__(self, context, type):
1.83 + self.context = context
1.84 + self.type = type
1.85 +
1.86 + def __eq__(self, other):
1.87 + return hasattr(other, "type") and other.type == self.type or other == self.type
1.88 +
1.89 +# Annotation.
1.90
1.91 class Annotator(Visitor):
1.92 +
1.93 + """
1.94 + The type annotator which traverses the program nodes, typically depth-first,
1.95 + and maintains a record of the current set of types applying to the currently
1.96 + considered operation. Such types are also recorded on the nodes, and a
1.97 + special "system" record is maintained to monitor the level of annotation
1.98 + activity with a view to recognising when no more annotations are possible.
1.99 + """
1.100 +
1.101 def __init__(self):
1.102 Visitor.__init__(self)
1.103 - self.system = System()
1.104 + self.system = system
1.105 self.types = None
1.106 self.temp = {}
1.107
1.108 - def process(self, node, global_namespace=None):
1.109 + def process(self, node, locals=None, globals=None):
1.110 +
1.111 + """
1.112 + Process a subprogram or module 'node', indicating any initial 'locals'
1.113 + and 'globals' if either are defined. Return an annotated subprogram or
1.114 + module. Note that this method may mutate nodes in the original program.
1.115 + """
1.116 +
1.117 if hasattr(node, "structure"):
1.118 - self.structure = node.structure
1.119 - has_structure = 1
1.120 + self.structure = node.structure; has_structure = 1
1.121 else:
1.122 - self.structure = None
1.123 - has_structure = 0
1.124 + self.structure = None; has_structure = 0
1.125
1.126 self.namespace = Namespace(self.structure is not None)
1.127 - self.global_namespace = global_namespace or self.namespace # NOTE: Improve this.
1.128 + if locals is not None:
1.129 + self.namespace.merge(locals)
1.130 +
1.131 + self.global_namespace = globals or self.namespace # NOTE: Improve this.
1.132
1.133 if has_structure:
1.134 node.structure.namespace = self.namespace
1.135 @@ -110,27 +162,23 @@
1.136
1.137 return result
1.138
1.139 + def annotate(self, node):
1.140 +
1.141 + "Annotate the given 'node' in the system."
1.142 +
1.143 + self.system.annotate(node, self.types)
1.144 +
1.145 def default(self, node):
1.146 +
1.147 + """
1.148 + Process the given 'node', given that it does not have a specific
1.149 + handler.
1.150 + """
1.151 +
1.152 for attr in ("args",):
1.153 value = getattr(node, attr, None)
1.154 if value is not None:
1.155 setattr(node, attr, self.dispatches(value))
1.156 -
1.157 - # NOTE: This will eventually use both defaults and supplied arguments.
1.158 -
1.159 - for attr in ("params",):
1.160 - value = getattr(node, attr, None)
1.161 - if value is not None:
1.162 - params = []
1.163 - for name, default in value:
1.164 - if default is not None:
1.165 - n = self.dispatch(default)
1.166 - self.namespace.store(name, self.types)
1.167 - else:
1.168 - n = None
1.169 - self.namespace.store(name, [])
1.170 - params.append((name, n))
1.171 - setattr(node, attr, params)
1.172 for attr in ("expr", "lvalue", "test", "handler", "star", "dstar"):
1.173 value = getattr(node, attr, None)
1.174 if value is not None:
1.175 @@ -151,22 +199,23 @@
1.176
1.177 def visitLoadRef(self, loadref):
1.178 self.types = [loadref.ref]
1.179 + self.annotate(loadref)
1.180 return loadref
1.181
1.182 def visitLoadName(self, loadname):
1.183 scope = self.namespace.find_for_load(loadname.name)
1.184 - print "LoadName", scope
1.185 if scope == "structure":
1.186 - return self.dispatch(LoadAttr(expr=LoadRef(ref=self.structure), name=loadname.name))
1.187 + result = self.dispatch(LoadAttr(expr=LoadRef(ref=self.structure), name=loadname.name))
1.188 elif scope == "global":
1.189 - return self.dispatch(LoadGlobal(name=loadname.name))
1.190 + result = self.dispatch(LoadGlobal(name=loadname.name))
1.191 else:
1.192 self.types = self.namespace.load(loadname.name)
1.193 - return loadname
1.194 + result = loadname
1.195 + self.annotate(result)
1.196 + return result
1.197
1.198 def visitStoreName(self, storename):
1.199 scope = self.namespace.find_for_store(storename.name)
1.200 - print "StoreName", scope
1.201 if scope == "structure":
1.202 return self.dispatch(StoreAttr(lvalue=LoadRef(ref=self.structure), name=storename.name, expr=storename.expr))
1.203 elif scope == "global":
1.204 @@ -178,6 +227,7 @@
1.205
1.206 def visitLoadGlobal(self, loadglobal):
1.207 self.types = self.global_namespace.load(loadglobal.name)
1.208 + self.annotate(loadglobal)
1.209 return loadglobal
1.210
1.211 def visitStoreGlobal(self, storeglobal):
1.212 @@ -191,6 +241,7 @@
1.213 def visitLoadTemp(self, loadtemp):
1.214 index = getattr(loadtemp, "index", None)
1.215 self.types = self.temp[index]
1.216 + self.annotate(loadtemp)
1.217 return loadtemp
1.218
1.219 def visitStoreTemp(self, storetemp):
1.220 @@ -208,8 +259,10 @@
1.221 loadattr.expr = self.dispatch(loadattr.expr)
1.222 types = []
1.223 for ref in self.types:
1.224 - types += ref.namespace.load(loadattr.name)
1.225 + for type in ref.namespace.load(loadattr.name):
1.226 + types.append(Attribute(ref, type))
1.227 self.types = types
1.228 + self.annotate(loadattr)
1.229 return loadattr
1.230
1.231 def visitStoreAttr(self, storeattr):
1.232 @@ -220,4 +273,103 @@
1.233 ref.namespace.store(storeattr.name, expr)
1.234 return storeattr
1.235
1.236 + def visitInvoke(self, invoke):
1.237 + invoke.expr = self.dispatch(invoke.expr)
1.238 + expr = self.types
1.239 + types = []
1.240 + args = []
1.241 +
1.242 + # Get type information for regular arguments.
1.243 +
1.244 + for arg in invoke.args:
1.245 + args.append(self.dispatch(arg))
1.246 + types.append(self.types)
1.247 +
1.248 + # Get type information for star and dstar arguments.
1.249 +
1.250 + if invoke.star is not None:
1.251 + param, default = invoke.star
1.252 + default = self.dispatch(default)
1.253 + invoke.star = param, default
1.254 + types.append(default.types)
1.255 +
1.256 + if invoke.dstar is not None:
1.257 + param, default = invoke.dstar
1.258 + default = self.dispatch(default)
1.259 + invoke.dstar = param, default
1.260 + types.append(default.types)
1.261 +
1.262 + invoke.args = args
1.263 + invoke.types = expr
1.264 +
1.265 + # NOTE: Now locate and invoke the subprogram.
1.266 +
1.267 + for subprogram in expr:
1.268 + items = self.make_items(invoke, subprogram)
1.269 + self.process(subprogram, self.make_namespace(items), self.global_namespace)
1.270 +
1.271 + return invoke
1.272 +
1.273 + def make_items(self, invocation, subprogram):
1.274 + # NOTE: Support star and dstar.
1.275 + args = invocation.args
1.276 + params = subprogram.params
1.277 + items = []
1.278 + keywords = {}
1.279 +
1.280 + # Process the specified arguments.
1.281 +
1.282 + for arg in args:
1.283 + if isinstance(arg, Keyword):
1.284 + keywords[arg.name] = arg.expr
1.285 + continue
1.286 + elif params:
1.287 + param, default = params[0]
1.288 + if arg is None:
1.289 + arg = self.dispatch(default)
1.290 + else:
1.291 + raise TypeError, "Invocation has too many arguments."
1.292 + items.append((param, arg.types))
1.293 + params = params[1:]
1.294 +
1.295 + # Collect the remaining defaults.
1.296 +
1.297 + while params:
1.298 + param, default = params[0]
1.299 + if keywords.has_key(param):
1.300 + arg = keywords[param]
1.301 + else:
1.302 + arg = self.dispatch(default)
1.303 + items.append((param, arg.types))
1.304 + params = params[1:]
1.305 +
1.306 + # Add star and dstar.
1.307 +
1.308 + if invocation.star is not None:
1.309 + if subprogram.star is not None:
1.310 + param, default = subprogram.star
1.311 + items.append((param, invocation.star.types))
1.312 + else:
1.313 + raise TypeError, "Invocation provides unwanted *args."
1.314 + elif subprogram.star is not None:
1.315 + param, default = subprogram.star
1.316 + items.append((param, self.dispatch(default)))
1.317 +
1.318 + if invocation.dstar is not None:
1.319 + if subprogram.dstar is not None:
1.320 + param, default = subprogram.dstar
1.321 + items.append((param, invocation.dstar.types))
1.322 + else:
1.323 + raise TypeError, "Invocation provides unwanted **args."
1.324 + elif subprogram.dstar is not None:
1.325 + param, default = subprogram.dstar
1.326 + items.append((param, self.dispatch(default)))
1.327 +
1.328 + return items
1.329 +
1.330 + def make_namespace(self, items):
1.331 + namespace = Namespace()
1.332 + namespace.merge_items(items)
1.333 + return namespace
1.334 +
1.335 # vim: tabstop=4 expandtab shiftwidth=4
2.1 --- a/simplified.py Sun Jul 23 23:56:11 2006 +0200
2.2 +++ b/simplified.py Sun Jul 23 23:57:13 2006 +0200
2.3 @@ -23,6 +23,29 @@
2.4
2.5 from compiler.visitor import ASTVisitor
2.6
2.7 +# Elementary visitor support.
2.8 +
2.9 +class Visitor(ASTVisitor):
2.10 +
2.11 + "A visitor base class."
2.12 +
2.13 + def __init__(self):
2.14 + ASTVisitor.__init__(self)
2.15 +
2.16 + def default(self, node, *args):
2.17 + raise ValueError, node.__class__
2.18 +
2.19 + def dispatch(self, node, *args):
2.20 + return ASTVisitor.dispatch(self, node, *args)
2.21 +
2.22 + def dispatches(self, nodes, *args):
2.23 + results = []
2.24 + for node in nodes:
2.25 + results.append(self.dispatch(node, *args))
2.26 + return results
2.27 +
2.28 +# Simplified program nodes.
2.29 +
2.30 class Node:
2.31
2.32 """
2.33 @@ -87,6 +110,12 @@
2.34 if hasattr(self, "params"):
2.35 for name, default in self.params:
2.36 self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
2.37 + if hasattr(self, "star") and self.star:
2.38 + name, default = self.star
2.39 + self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
2.40 + if hasattr(self, "dstar") and self.dstar:
2.41 + name, default = self.dstar
2.42 + self._pprint(indent + 2, "( ", "%s -> %s" % (name, default))
2.43 if getattr(self, "acquire_locals", 0):
2.44 self._pprint(indent + 2, "( ", "acquiring locals")
2.45 if getattr(self, "structure", 0):
2.46 @@ -111,10 +140,14 @@
2.47 if hasattr(self, "args"):
2.48 for arg in self.args:
2.49 arg.pprint(indent + 2, "( ")
2.50 + if hasattr(self, "star") and self.star:
2.51 + self.star.pprint(indent + 2, "( ")
2.52 + if hasattr(self, "dstar") and self.dstar:
2.53 + self.dstar.pprint(indent + 2, "( ")
2.54
2.55 class Module(Node): "A Python module."
2.56 class Subprogram(Node): "A subprogram: functions, methods and loops."
2.57 -class Class(Node): "A Python class."
2.58 +class Constant(Node): "A constant."
2.59 class Pass(Node): "A placeholder node corresponding to pass."
2.60 class Invoke(Node): "A function, method or loop invocation."
2.61 class Return(Node): "Return an evaluated expression."
2.62 @@ -126,7 +159,6 @@
2.63 class LoadName(Node): "Load a named object."
2.64 class LoadGlobal(Node): "Load a named global object."
2.65 class LoadAttr(Node): "Load an object attribute."
2.66 -class LoadConst(Node): "Load a constant."
2.67 class LoadRef(Node): "Load a reference, typically a subprogram."
2.68 class LoadExc(Node): "Load a handled exception."
2.69 class StoreTemp(Node): "Store a temporary value."
2.70 @@ -138,24 +170,6 @@
2.71 class Try(Node): "A try...except...else...finally grouping node."
2.72 class Raise(Node): "An exception raising node."
2.73 class Not(Node): "A negation of an expression."
2.74 -
2.75 -class Visitor(ASTVisitor):
2.76 -
2.77 - "A visitor base class."
2.78 -
2.79 - def __init__(self):
2.80 - ASTVisitor.__init__(self)
2.81 -
2.82 - def default(self, node, *args):
2.83 - raise ValueError, node.__class__
2.84 -
2.85 - def dispatch(self, node, *args):
2.86 - return ASTVisitor.dispatch(self, node, *args)
2.87 -
2.88 - def dispatches(self, nodes, *args):
2.89 - results = []
2.90 - for node in nodes:
2.91 - results.append(self.dispatch(node, *args))
2.92 - return results
2.93 +class Class(Node): "A Python class."
2.94
2.95 # vim: tabstop=4 expandtab shiftwidth=4
3.1 --- a/simplify.py Sun Jul 23 23:56:11 2006 +0200
3.2 +++ b/simplify.py Sun Jul 23 23:57:13 2006 +0200
3.3 @@ -1,7 +1,9 @@
3.4 #!/usr/bin/env python
3.5
3.6 """
3.7 -Simplify AST structures for easier type propagation and analysis.
3.8 +Simplify AST structures for easier type propagation and analysis. The code in
3.9 +this module processes AST trees originating from the compiler module and
3.10 +produces a result tree consisting of instruction-oriented program nodes.
3.11
3.12 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk>
3.13
3.14 @@ -46,7 +48,8 @@
3.15 Visitor.__init__(self)
3.16 self.result = None # The resulting tree.
3.17 self.subprograms = [] # Subprograms outside the tree.
3.18 - self.structures = [] # Structures/classes
3.19 + self.structures = [] # Structures/classes.
3.20 + self.constants = {} # Constants.
3.21 self.current_subprograms = [] # Current subprograms being processed.
3.22
3.23 def process(self, node):
3.24 @@ -115,7 +118,9 @@
3.25 return result
3.26
3.27 def visitConst(self, const):
3.28 - result = LoadConst(const, value=const.value)
3.29 + if not self.constants.has_key(const.value):
3.30 + self.constants[const.value] = Constant(name=repr(const.value), value=const.value)
3.31 + result = LoadRef(ref=self.constants[const.value])
3.32 return result
3.33
3.34 def visitReturn(self, return_):
3.35 @@ -146,16 +151,16 @@
3.36 return result
3.37
3.38 def visitTuple(self, tuple):
3.39 - return self._visitBuiltin(tuple, "Tuple")
3.40 + return self._visitBuiltin(tuple, "tuple")
3.41
3.42 def visitList(self, list):
3.43 - return self._visitBuiltin(list, "List")
3.44 + return self._visitBuiltin(list, "list")
3.45
3.46 def visitDict(self, dict):
3.47 - result = Invoke(dict, expr=LoadName(name="Dict"))
3.48 + result = Invoke(dict, expr=LoadName(name="dict"))
3.49 args = []
3.50 for key, value in dict.items:
3.51 - tuple = Invoke(expr=LoadName(name="Tuple"), star=None, dstar=None)
3.52 + tuple = Invoke(expr=LoadName(name="tuple"), star=None, dstar=None)
3.53 tuple.args = [self.dispatch(key), self.dispatch(value)]
3.54 args.append(tuple)
3.55 result.args = args
3.56 @@ -549,7 +554,7 @@
3.57 if len(subs) == 1:
3.58 return self.dispatch(subs[0])
3.59 else:
3.60 - return Invoke(expr=LoadName(name="Tuple"), args=self.dispatches(subs))
3.61 + return Invoke(expr=LoadName(name="tuple"), args=self.dispatches(subs))
3.62
3.63 def visitSubscript(self, subscript, in_sequence=0):
3.64 value = self._visitAssNameOrAttr(subscript, in_sequence)
3.65 @@ -562,7 +567,9 @@
3.66 structure = Class(name=hex(id(class_)), bases=class_.bases)
3.67 self.structures.append(structure)
3.68
3.69 - subprogram = Subprogram(name=hex(id(class_)), acquire_locals=1, structure=structure, params=[], star=None, dstar=None)
3.70 + # Make a subprogram which initialises the class structure.
3.71 +
3.72 + subprogram = Subprogram(name=hex(id(class_)), structure=structure, params=[], star=None, dstar=None)
3.73 self.current_subprograms.append(subprogram)
3.74
3.75 subprogram.code = self.dispatch(class_.code)
3.76 @@ -585,10 +592,17 @@
3.77 else: has_dstar = 0
3.78 ndefaults = len(function.defaults)
3.79 npositional = len(function.argnames) - has_star - has_dstar
3.80 - if has_star: star = function.argnames[npositional]
3.81 - else: star = None
3.82 - if has_dstar: dstar = function.argnames[npositional + has_star]
3.83 - else: dstar = None
3.84 +
3.85 + # Produce star and dstar parameters with appropriate defaults.
3.86 +
3.87 + if has_star:
3.88 + star = (function.argnames[npositional], Invoke(expr=LoadName(name="list"), args=[], star=None, dstar=None))
3.89 + else:
3.90 + star = None
3.91 + if has_dstar:
3.92 + dstar = (function.argnames[npositional + has_star], Invoke(expr=LoadName(name="dict"), args=[], star=None, dstar=None))
3.93 + else:
3.94 + dstar = None
3.95
3.96 params = []
3.97 for i in range(0, npositional - ndefaults):