1 #!/usr/bin/env python 2 3 """ 4 Simplified program nodes for easier type propagation and analysis. This module 5 contains nodes representing program instructions or operations, program 6 structure or organisation, and abstract program data. 7 8 Copyright (C) 2006, 2007 Paul Boddie <paul@boddie.org.uk> 9 10 This software is free software; you can redistribute it and/or 11 modify it under the terms of the GNU General Public License as 12 published by the Free Software Foundation; either version 2 of 13 the License, or (at your option) any later version. 14 15 This software is distributed in the hope that it will be useful, 16 but WITHOUT ANY WARRANTY; without even the implied warranty of 17 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 GNU General Public License for more details. 19 20 You should have received a copy of the GNU General Public 21 License along with this library; see the file LICENCE.txt 22 If not, write to the Free Software Foundation, Inc., 23 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 24 """ 25 26 from simplified.utils import Structure, WithName, name 27 import sys 28 29 # Simplified program nodes. 30 31 class Node: 32 33 """ 34 A result node with common attributes: 35 36 original The original node from which this node was created. 37 defining Whether the node defines something in the original program. 38 name Any name involved (variable or attribute). 39 index Any index involved (temporary variable name). 40 value Any constant value. 41 ref Any reference to (for example) subprograms. 42 nstype Any indication of the namespace type involved in a name access. 43 44 Expression-related attributes: 45 46 expr Any contributing expression. 47 lvalue Any target expression. 48 test Any test expression in a conditional instruction. 49 50 Invocation and subprogram attributes: 51 52 args Any collection of argument nodes. 53 params Any collection of parameter nodes and defaults. 54 55 Statement-grouping attributes: 56 57 body Any conditional code depending on the success of a test. 58 else_ Any conditional code depending on the failure of a test. 59 handler Any exception handler code. 60 finally_ Any code which will be executed regardless. 61 code Any unconditional code. 62 choices Any choices which may be included in the final program. 63 """ 64 65 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 66 expression_attributes = "expr", "lvalue", "test" 67 argument_attributes = "star", "dstar" 68 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 69 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" 70 71 def __init__(self, original=None, defining=0, **kw): 72 73 """ 74 Initialise a program node with a link to an optional 'original' AST 75 node. An optional 'defining' parameter (if set to a true value), sets 76 this node as the defining node in the original. 77 """ 78 79 self.original = original 80 self.defining = defining 81 self.copies = {} 82 83 if self.original is not None and defining: 84 self.original._node = self 85 for name, value in kw.items(): 86 setattr(self, name, value) 87 88 # Annotations. 89 90 self.types = set() 91 92 def __repr__(self): 93 94 "Return a readable representation." 95 96 if hasattr(self, "full_name"): 97 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 98 elif hasattr(self, "name"): 99 s = "%s '%s'" % (self.__class__.__name__, self.name) 100 elif hasattr(self, "index"): 101 s = "%s (%s)" % (self.__class__.__name__, self.index) 102 elif hasattr(self, "value"): 103 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 104 elif hasattr(self, "ref"): 105 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 106 else: 107 s = "%s" % (self.__class__.__name__,) 108 109 # Annotations. 110 111 if self.types: 112 return "%s -> %s" % (s, self.types) 113 else: 114 return s 115 116 def _pprint(self, indent, continuation, s, stream=None): 117 118 """ 119 Print, at the given 'indent' level, with the given 'continuation' text, 120 the string 's', either to the given, optional 'stream' or to standard 121 output, this node's "pretty" representation. 122 """ 123 124 stream = stream or sys.stdout 125 if continuation: 126 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 127 else: 128 print >>stream, (" " * indent) + s 129 130 def pprint(self, indent=0, continuation=None, stream=None): 131 132 """ 133 Print, at the given, optional 'indent', with the given optional 134 'continuation' text, either to the given, optional 'stream' or to 135 standard output, this node's "pretty" representation along with its 136 children and their "pretty" representation (and so on). 137 """ 138 139 stream = stream or sys.stdout 140 self._pprint(indent, continuation, repr(self), stream) 141 142 # Subprogram-related details. 143 144 if hasattr(self, "params"): 145 for name, default in self.params: 146 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 147 if hasattr(self, "star") and self.star: 148 name, default = self.star 149 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 150 if hasattr(self, "dstar") and self.dstar: 151 name, default = self.dstar 152 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 153 if getattr(self, "internal", 0): 154 self._pprint(indent + 2, "( ", "internal", stream=stream) 155 if getattr(self, "structure", 0): 156 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 157 158 # Expression-related details. 159 160 if hasattr(self, "expr"): 161 self.expr.pprint(indent + 2, "- ", stream=stream) 162 if hasattr(self, "nodes"): 163 for node in self.nodes: 164 node.pprint(indent + 2, "- ", stream=stream) 165 if hasattr(self, "lvalue"): 166 self.lvalue.pprint(indent + 2, "->", stream=stream) 167 if hasattr(self, "nstype"): 168 self._pprint(indent + 2, "", self.nstype, stream=stream) 169 if hasattr(self, "args"): 170 for arg in self.pos_args: 171 arg.pprint(indent + 2, "( ", stream=stream) 172 for name, arg in self.kw_args.items(): 173 arg.pprint(indent + 2, "( ", stream=stream) 174 if hasattr(self, "star") and self.star: 175 self.star.pprint(indent + 2, "( ", stream=stream) 176 if hasattr(self, "dstar") and self.dstar: 177 self.dstar.pprint(indent + 2, "( ", stream=stream) 178 179 # Statement-related details. 180 181 if hasattr(self, "test"): 182 self.test.pprint(indent + 2, "? ", stream=stream) 183 for attr in self.grouping_attributes: 184 if hasattr(self, attr) and getattr(self, attr): 185 self._pprint(indent, "", "%s {" % attr, stream=stream) 186 for node in getattr(self, attr): 187 node.pprint(indent + 2, stream=stream) 188 self._pprint(indent, "", "}", stream=stream) 189 190 # Annotations. 191 192 if hasattr(self, "accesses"): 193 self._pprint(indent, "", "--------", stream=stream) 194 for ref, attributes in self.accesses.items(): 195 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 196 self._pprint(indent, "", "--------", stream=stream) 197 if hasattr(self, "writes"): 198 self._pprint(indent, "", "--------", stream=stream) 199 for ref, attribute in self.writes.items(): 200 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 201 self._pprint(indent, "", "--------", stream=stream) 202 203 # Node discovery functions. 204 205 def active(self): 206 207 "Return the active copies of this node or a list containing this node." 208 209 return self.copies.values() or [self] 210 211 # Node manipulation functions. 212 213 def copy(self, instance=None, new_name=None): 214 215 """ 216 Perform a deep copy of the node, optionally specifying the 'instance' 217 for whom the copy has been requested and a 'new_name' for the copied 218 node. Return new unannotated copies of the node and its descendants. 219 """ 220 221 # Copy the common attributes of this node. 222 223 common = {} 224 for attr in self.common_attributes: 225 if hasattr(self, attr): 226 common[attr] = getattr(self, attr) 227 228 # Add new attributes specially for copies. 229 230 common["instance"] = instance 231 232 if new_name is not None: 233 common["copy_of"] = self 234 common["name"] = new_name 235 236 # Instantiate the copy, avoiding side-effects with original and defining. 237 238 node = self.__class__(**common) 239 node.defining = self.defining 240 241 # Add links to copies from originals. 242 243 self.copies[instance] = node 244 245 # Copy attributes of different types. 246 247 for attr in self.expression_attributes: 248 if hasattr(self, attr): 249 n = getattr(self, attr) 250 if n is None: 251 n2 = n 252 else: 253 n2 = n.copy(instance) 254 setattr(node, attr, n2) 255 256 for attr in self.argument_attributes: 257 if hasattr(self, attr): 258 t = getattr(self, attr) 259 if t is None: 260 t2 = t 261 else: 262 name, n = t 263 n2 = n.copy(instance) 264 t2 = name, n2 265 setattr(node, attr, t2) 266 267 for attr in self.invocation_attributes: 268 if hasattr(self, attr): 269 l = getattr(self, attr) 270 l2 = [] 271 for name, n in l: 272 if n is None: 273 l2.append((name, n)) 274 else: 275 l2.append((name, n.copy(instance))) 276 setattr(node, attr, l2) 277 278 for attr in self.grouping_attributes: 279 if hasattr(self, attr): 280 l = getattr(self, attr) 281 setattr(node, attr, [n.copy(instance) for n in l]) 282 283 # Arguments are usually processed further - "args" is useless. 284 285 if hasattr(self, "pos_args"): 286 node.pos_args = [n.copy(instance) for n in self.pos_args] 287 288 if hasattr(self, "kw_args"): 289 node.kw_args = {} 290 for name, n in self.kw_args.items(): 291 node.kw_args[name] = n.copy(instance) 292 293 return node 294 295 # These are the supported "operations" described by simplified program nodes. 296 297 class Pass(Node): "A placeholder node corresponding to pass." 298 class Assign(Node): "A grouping node for assignment-related operations." 299 class Keyword(Node): "A grouping node for keyword arguments." 300 class Global(Node): "A global name designator." 301 class Import(Node): "A module import operation." 302 class LoadTemp(Node): "Load a previously-stored temporary value." 303 class LoadName(Node): "Load a named object." 304 class LoadAttr(Node): "Load an object attribute." 305 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 306 class LoadExc(Node): "Load a handled exception." 307 class ResetExc(Node): "Reset the exception state." 308 class StoreTemp(Node): "Store a temporary value." 309 class StoreName(Node): "Associate a name with an object." 310 class StoreAttr(Node): "Associate an object's attribute with a value." 311 class ReleaseTemp(Node): "Release a temporary value." 312 class Try(Node): "A try...except...else...finally grouping node." 313 class Raise(Node): "An exception raising node." 314 class Not(Node): "A negation of an expression." 315 class CheckType(Node): "Check a value's type from a list of choices." 316 class Return(Node): "Return an evaluated expression." 317 class Invoke(Node): "An invocation." 318 319 # There are two types of return node: return from function and return from 320 # block. 321 322 class ReturnFromFunction(Return): 323 pass 324 325 class ReturnFromBlock(Return): 326 pass 327 328 # NOTE: Not actually supported. 329 # Additionally, yield statements act like return statements for the purposes 330 # of this system. 331 332 class Yield(ReturnFromFunction): 333 pass 334 335 # Some behaviour is set as the default in conditional nodes but may be 336 # overridden. 337 338 class Conditional(Node): 339 340 "A conditional node consisting of a test and outcomes." 341 342 def __init__(self, *args, **kw): 343 self.isolate_test = 0 344 Node.__init__(self, *args, **kw) 345 346 # Invocations involve some more work to process calculated attributes. 347 348 class InvokeFunction(Invoke): 349 350 "A function or method invocation." 351 352 def __init__(self, *args, **kw): 353 self.args = [] 354 self.star = None 355 self.dstar = None 356 Invoke.__init__(self, *args, **kw) 357 self.set_args(self.args) 358 self.share_locals = 0 359 360 def set_args(self, args): 361 362 "Sort the 'args' into positional and keyword arguments." 363 364 self.pos_args = [] 365 self.kw_args = {} 366 add_kw = 0 367 for arg in args: 368 if not add_kw: 369 if not isinstance(arg, Keyword): 370 self.pos_args.append(arg) 371 else: 372 add_kw = 1 373 if add_kw: 374 if isinstance(arg, Keyword): 375 self.kw_args[arg.name] = arg.expr 376 else: 377 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 378 379 class InvokeRef(Invoke): 380 381 "A block or loop invocation." 382 383 def __init__(self, *args, **kw): 384 self.share_locals = 1 385 Invoke.__init__(self, *args, **kw) 386 387 # Program structure nodes. 388 389 class Module(Node, Structure): 390 391 "A Python module." 392 393 def full_name(self): 394 return "module %s" % self.name 395 396 class Subprogram(Node, WithName): 397 398 "A subprogram: functions, methods and loops." 399 400 def __init__(self, *args, **kw): 401 Node.__init__(self, *args, **kw) 402 WithName.__init__(self) 403 self.raises = set() 404 self.returns = set() 405 self.return_locals = set() 406 407 # vim: tabstop=4 expandtab shiftwidth=4