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 Tuple construction attributes: 56 57 nodes Any expressions used to initialise a tuple 58 59 Statement-grouping attributes: 60 61 body Any conditional code depending on the success of a test. 62 else_ Any conditional code depending on the failure of a test. 63 handler Any exception handler code. 64 finally_ Any code which will be executed regardless. 65 code Any unconditional code. 66 choices Any choices which may be included in the final program. 67 """ 68 69 common_attributes = "name", "index", "value", "nstype", "internal", "returns_value", "is_method", "ref", "module", "structures", "original" 70 expression_attributes = "expr", "lvalue", "test" 71 argument_attributes = "star", "dstar" 72 invocation_attributes = "params", # not "args" - see "pos_args", "kw_args" 73 grouping_attributes = "code", "body", "else_", "handler", "finally_", "choices" 74 75 def __init__(self, original=None, defining=0, **kw): 76 77 """ 78 Initialise a program node with a link to an optional 'original' AST 79 node. An optional 'defining' parameter (if set to a true value), sets 80 this node as the defining node in the original. 81 """ 82 83 self.original = original 84 self.defining = defining 85 self.copies = {} 86 87 if self.original is not None and defining: 88 self.original._node = self 89 for name, value in kw.items(): 90 setattr(self, name, value) 91 92 # Annotations. 93 94 self.types = set() 95 96 def __repr__(self): 97 98 "Return a readable representation." 99 100 if hasattr(self, "full_name"): 101 s = "%s '%s'" % (self.__class__.__name__, self.full_name()) 102 elif hasattr(self, "name"): 103 s = "%s '%s'" % (self.__class__.__name__, self.name) 104 elif hasattr(self, "index"): 105 s = "%s (%s)" % (self.__class__.__name__, self.index) 106 elif hasattr(self, "value"): 107 s = "%s %s" % (self.__class__.__name__, repr(self.value)) 108 elif hasattr(self, "ref"): 109 s = "%s '%s'" % (self.__class__.__name__, name(self.ref, self.ref.name)) 110 else: 111 s = "%s" % (self.__class__.__name__,) 112 113 # Annotations. 114 115 if self.types: 116 return "%s -> %s" % (s, self.types) 117 else: 118 return s 119 120 def _pprint(self, indent, continuation, s, stream=None): 121 122 """ 123 Print, at the given 'indent' level, with the given 'continuation' text, 124 the string 's', either to the given, optional 'stream' or to standard 125 output, this node's "pretty" representation. 126 """ 127 128 stream = stream or sys.stdout 129 if continuation: 130 print >>stream, (" " * max(0, indent - len(continuation))) + continuation + s 131 else: 132 print >>stream, (" " * indent) + s 133 134 def pprint(self, indent=0, continuation=None, stream=None): 135 136 """ 137 Print, at the given, optional 'indent', with the given optional 138 'continuation' text, either to the given, optional 'stream' or to 139 standard output, this node's "pretty" representation along with its 140 children and their "pretty" representation (and so on). 141 """ 142 143 stream = stream or sys.stdout 144 self._pprint(indent, continuation, repr(self), stream) 145 146 # Subprogram-related details. 147 148 if hasattr(self, "params"): 149 for name, default in self.params: 150 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 151 if hasattr(self, "star") and self.star: 152 name, default = self.star 153 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 154 if hasattr(self, "dstar") and self.dstar: 155 name, default = self.dstar 156 self._pprint(indent + 2, "( ", "%s default %s" % (name, default), stream=stream) 157 if getattr(self, "internal", 0): 158 self._pprint(indent + 2, "( ", "internal", stream=stream) 159 if getattr(self, "structure", 0): 160 self._pprint(indent + 2, "( ", "structure '%s'" % self.structure.name, stream=stream) 161 162 # Expression-related details. 163 164 if hasattr(self, "expr"): 165 self.expr.pprint(indent + 2, "- ", stream=stream) 166 if hasattr(self, "nodes"): 167 for node in self.nodes: 168 node.pprint(indent + 2, "- ", stream=stream) 169 if hasattr(self, "lvalue"): 170 self.lvalue.pprint(indent + 2, "->", stream=stream) 171 if hasattr(self, "nstype"): 172 self._pprint(indent + 2, "", self.nstype, stream=stream) 173 if hasattr(self, "args"): 174 for arg in self.pos_args: 175 arg.pprint(indent + 2, "( ", stream=stream) 176 for name, arg in self.kw_args.items(): 177 arg.pprint(indent + 2, "( ", stream=stream) 178 if hasattr(self, "star") and self.star: 179 self.star.pprint(indent + 2, "( ", stream=stream) 180 if hasattr(self, "dstar") and self.dstar: 181 self.dstar.pprint(indent + 2, "( ", stream=stream) 182 183 # Statement-related details. 184 185 if hasattr(self, "test"): 186 self.test.pprint(indent + 2, "? ", stream=stream) 187 for attr in self.grouping_attributes: 188 if hasattr(self, attr) and getattr(self, attr): 189 self._pprint(indent, "", "%s {" % attr, stream=stream) 190 for node in getattr(self, attr): 191 node.pprint(indent + 2, stream=stream) 192 self._pprint(indent, "", "}", stream=stream) 193 194 # Annotations. 195 196 if hasattr(self, "accesses"): 197 self._pprint(indent, "", "--------", stream=stream) 198 for ref, attributes in self.accesses.items(): 199 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, ", ".join([("%s via %s" % attr_acc) for attr_acc in attributes])), stream=stream) 200 self._pprint(indent, "", "--------", stream=stream) 201 if hasattr(self, "writes"): 202 self._pprint(indent, "", "--------", stream=stream) 203 for ref, attribute in self.writes.items(): 204 self._pprint(indent + 2, "| ", "when %s: %s" % (ref, attribute), stream=stream) 205 self._pprint(indent, "", "--------", stream=stream) 206 207 # Node discovery functions. 208 209 def active(self): 210 211 "Return the active copies of this node or a list containing this node." 212 213 return self.copies.values() or [self] 214 215 # Node manipulation functions. 216 217 def copy(self, instance=None, new_name=None): 218 219 """ 220 Perform a deep copy of the node, optionally specifying the 'instance' 221 for whom the copy has been requested and a 'new_name' for the copied 222 node. Return new unannotated copies of the node and its descendants. 223 """ 224 225 # Copy the common attributes of this node. 226 227 common = {} 228 for attr in self.common_attributes: 229 if hasattr(self, attr): 230 common[attr] = getattr(self, attr) 231 232 # Add new attributes specially for copies. 233 234 common["instance"] = instance 235 236 if new_name is not None: 237 common["copy_of"] = self 238 common["name"] = new_name 239 240 # Instantiate the copy, avoiding side-effects with original and defining. 241 242 node = self.__class__(**common) 243 node.defining = self.defining 244 245 # Add links to copies from originals. 246 247 self.copies[instance] = node 248 249 # Copy attributes of different types. 250 251 for attr in self.expression_attributes: 252 if hasattr(self, attr): 253 n = getattr(self, attr) 254 if n is None: 255 n2 = n 256 else: 257 n2 = n.copy(instance) 258 setattr(node, attr, n2) 259 260 for attr in self.argument_attributes: 261 if hasattr(self, attr): 262 t = getattr(self, attr) 263 if t is None: 264 t2 = t 265 else: 266 name, n = t 267 n2 = n.copy(instance) 268 t2 = name, n2 269 setattr(node, attr, t2) 270 271 for attr in self.invocation_attributes: 272 if hasattr(self, attr): 273 l = getattr(self, attr) 274 l2 = [] 275 for name, n in l: 276 if n is None: 277 l2.append((name, n)) 278 else: 279 l2.append((name, n.copy(instance))) 280 setattr(node, attr, l2) 281 282 for attr in self.grouping_attributes: 283 if hasattr(self, attr): 284 l = getattr(self, attr) 285 setattr(node, attr, [n.copy(instance) for n in l]) 286 287 # Arguments are usually processed further - "args" is useless. 288 289 if hasattr(self, "pos_args"): 290 node.pos_args = [n.copy(instance) for n in self.pos_args] 291 292 if hasattr(self, "kw_args"): 293 node.kw_args = {} 294 for name, n in self.kw_args.items(): 295 node.kw_args[name] = n.copy(instance) 296 297 return node 298 299 # These are the supported "operations" described by simplified program nodes. 300 301 class Pass(Node): "A placeholder node corresponding to pass." 302 class Assign(Node): "A grouping node for assignment-related operations." 303 class Keyword(Node): "A grouping node for keyword arguments." 304 class Global(Node): "A global name designator." 305 class Import(Node): "A module import operation." 306 class LoadTemp(Node): "Load a previously-stored temporary value." 307 class LoadName(Node): "Load a named object." 308 class LoadAttr(Node): "Load an object attribute." 309 class LoadRef(Node): "Load a reference, typically a subprogram or a constant." 310 class LoadExc(Node): "Load a handled exception." 311 class ResetExc(Node): "Reset the exception state." 312 class StoreTemp(Node): "Store a temporary value." 313 class StoreName(Node): "Associate a name with an object." 314 class StoreAttr(Node): "Associate an object's attribute with a value." 315 class ReleaseTemp(Node): "Release a temporary value." 316 class Try(Node): "A try...except...else...finally grouping node." 317 class Raise(Node): "An exception raising node." 318 class Not(Node): "A negation of an expression." 319 class CheckType(Node): "Check a value's type from a list of choices." 320 class Return(Node): "Return an evaluated expression." 321 class Invoke(Node): "An invocation." 322 class MakeTuple(Node): "Make a tuple object." 323 324 # There are two types of return node: return from function and return from 325 # block. 326 327 class ReturnFromFunction(Return): 328 pass 329 330 class ReturnFromBlock(Return): 331 pass 332 333 # NOTE: Not actually supported. 334 # Additionally, yield statements act like return statements for the purposes 335 # of this system. 336 337 class Yield(ReturnFromFunction): 338 pass 339 340 # Some behaviour is set as the default in conditional nodes but may be 341 # overridden. 342 343 class Conditional(Node): 344 345 "A conditional node consisting of a test and outcomes." 346 347 def __init__(self, *args, **kw): 348 self.isolate_test = 0 349 Node.__init__(self, *args, **kw) 350 351 # Invocations involve some more work to process calculated attributes. 352 353 class InvokeFunction(Invoke): 354 355 "A function or method invocation." 356 357 def __init__(self, *args, **kw): 358 self.args = [] 359 self.star = None 360 self.dstar = None 361 Invoke.__init__(self, *args, **kw) 362 self.set_args(self.args) 363 self.share_locals = 0 364 365 def set_args(self, args): 366 367 "Sort the 'args' into positional and keyword arguments." 368 369 self.pos_args = [] 370 self.kw_args = {} 371 add_kw = 0 372 for arg in args: 373 if not add_kw: 374 if not isinstance(arg, Keyword): 375 self.pos_args.append(arg) 376 else: 377 add_kw = 1 378 if add_kw: 379 if isinstance(arg, Keyword): 380 self.kw_args[arg.name] = arg.expr 381 else: 382 raise TypeError, "Positional argument appears after keyword arguments in '%s'." % self 383 384 class InvokeRef(Invoke): 385 386 "A block or loop invocation." 387 388 def __init__(self, *args, **kw): 389 self.share_locals = 1 390 Invoke.__init__(self, *args, **kw) 391 392 # Program structure nodes. 393 394 class Module(Node, Structure): 395 396 "A Python module." 397 398 def full_name(self): 399 return "module %s" % self.name 400 401 class Subprogram(Node, WithName): 402 403 "A subprogram: functions, methods and loops." 404 405 def __init__(self, *args, **kw): 406 Node.__init__(self, *args, **kw) 407 WithName.__init__(self) 408 self.raises = set() 409 self.returns = set() 410 self.return_locals = set() 411 412 # vim: tabstop=4 expandtab shiftwidth=4