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