1 #!/usr/bin/env python 2 3 """ 4 Simplify AST structures for easier type propagation and analysis. 5 6 Copyright (C) 2006 Paul Boddie <paul@boddie.org.uk> 7 8 This software is free software; you can redistribute it and/or 9 modify it under the terms of the GNU General Public License as 10 published by the Free Software Foundation; either version 2 of 11 the License, or (at your option) any later version. 12 13 This software is distributed in the hope that it will be useful, 14 but WITHOUT ANY WARRANTY; without even the implied warranty of 15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16 GNU General Public License for more details. 17 18 You should have received a copy of the GNU General Public 19 License along with this library; see the file LICENCE.txt 20 If not, write to the Free Software Foundation, Inc., 21 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA 22 """ 23 24 from compiler.visitor import ASTVisitor 25 import compiler.ast 26 from simplified import * 27 28 class Simplifier(ASTVisitor): 29 30 """ 31 A simplifying visitor for AST nodes. 32 33 Covered: And, AssAttr, AssList, AssName, AssTuple, Assign, AugAssign, Break, 34 CallFunc, Class, Const, Continue, Dict, Discard, For, From, 35 Function, Getattr, Global, If, Import, Invert, Keyword, Lambda, 36 List, Module, Name, Not, Or, Pass, Raise, Return, Stmt, TryExcept, 37 TryFinally, Tuple, While, UnaryAdd, UnarySub. 38 39 Missing: Add, Assert, Backquote, Bitand, Bitor, Bitxor, Compare, Decorators, 40 Div, Ellipsis, Exec, FloorDiv, LeftShift, ListComp, ListCompFor, 41 ListCompIf, Mod, Mul, Power, Print, Printnl, RightShift, 42 Slice, Sliceobj, Sub, Subscript, Yield. 43 """ 44 45 def __init__(self): 46 ASTVisitor.__init__(self) 47 self.result = None # The resulting tree. 48 self.subprograms = [] # Subprograms outside the tree. 49 self.current_subprograms = [] # Current subprograms being processed. 50 51 # Generic visitor methods. 52 53 def default(self, node, *args): 54 raise ValueError, node.__class__ 55 56 def dispatch(self, node, *args): 57 return ASTVisitor.dispatch(self, node, *args) 58 59 def dispatches(self, nodes, *args): 60 results = [] 61 for node in nodes: 62 results.append(self.dispatch(node, *args)) 63 return results 64 65 def dispatch_or_none(self, node, *args): 66 if node is not None: 67 return self.dispatch(node, *args) 68 else: 69 return LoadName(name="None") 70 71 # Placeholder or deletion transformations. 72 73 def visitStmt(self, stmt): 74 return self.dispatches(stmt.nodes) 75 76 def visitPass(self, pass_): 77 return Pass(pass_) 78 79 def visitDiscard(self, discard): 80 return self.dispatch(discard.expr) 81 82 # Relatively trivial transformations. 83 84 def visitModule(self, module): 85 self.result = Module(module) 86 self.result.code = self.dispatch(module.node) 87 return self.result 88 89 def visitClass(self, class_): 90 result = Class(class_, name=class_.name, bases=class_.bases) 91 result.code = self.dispatch(class_.code) 92 return result 93 94 def visitGetattr(self, getattr): 95 result = LoadAttr(getattr, name=getattr.attrname) 96 result.expr = self.dispatch(getattr.expr) 97 return result 98 99 def visitKeyword(self, keyword): 100 result = Keyword(keyword, name=keyword.name) 101 result.expr = self.dispatch(keyword.expr) 102 return result 103 104 def visitGlobal(self, global_): 105 result = Global(global_, names=global_.names) 106 return result 107 108 def visitImport(self, import_): 109 result = Assign(import_) 110 code = [] 111 for path, alias in import_.names: 112 importer = Import(name=path) 113 top = alias or path.split(".")[0] 114 code.append(StoreName(expr=importer, name=top)) 115 result.code = code 116 return result 117 118 def visitFrom(self, from_): 119 result = Assign(from_) 120 code = [] 121 code.append(StoreTemp(expr=Import(name=from_.modname))) 122 for name, alias in from_.names: 123 code.append(StoreName(expr=LoadAttr(expr=LoadTemp(), name=name), name=(alias or name))) 124 result.code = code 125 return result 126 127 def visitName(self, name): 128 result = LoadName(name, name=name.name) 129 return result 130 131 def visitConst(self, const): 132 result = LoadConst(const, value=const.value) 133 return result 134 135 def visitReturn(self, return_): 136 result = Return(return_) 137 result.expr = self.dispatch(return_.value) 138 return result 139 140 def visitBreak(self, break_): 141 result = Return(break_) 142 return result 143 144 def visitContinue(self, continue_): 145 result = Invoke(continue_, same_frame=1, star=None, dstar=None, args=[]) 146 result.expr = LoadRef(ref=self.current_subprograms[-1]) 147 return result 148 149 def visitRaise(self, raise_): 150 result = Raise(raise_, expr=self.dispatch(raise_.expr1), traceback=None) 151 if raise_.expr2 is not None: 152 result.args = [self.dispatch(raise_.expr2)] 153 if raise_.expr3 is not None: 154 result.traceback = self.dispatch(raise_.expr3) 155 return result 156 157 def visitIf(self, if_): 158 result = If(if_, else_=[]) 159 tests = [] 160 for compare, stmt in if_.tests: 161 # Produce something like... 162 # expr.__true__() ? body 163 test = Conditional(else_=[], test=Invoke( 164 expr=LoadAttr(expr=self.dispatch(compare), name="__true__"), 165 params=[], star=None, dstar=None)) 166 test.body = self.dispatch(stmt) 167 tests.append(test) 168 result.tests = tests 169 if if_.else_ is not None: 170 result.else_ = self.dispatch(if_.else_) 171 return result 172 173 def _visitBuiltin(self, builtin, name): 174 result = Invoke(builtin, expr=LoadName(name=name)) 175 result.args = self.dispatches(builtin.nodes) 176 return result 177 178 def visitTuple(self, tuple): 179 return self._visitBuiltin(tuple, "Tuple") 180 181 def visitList(self, list): 182 return self._visitBuiltin(list, "List") 183 184 def visitDict(self, dict): 185 result = Invoke(expr=LoadName(name="Dict")) 186 args = [] 187 for key, value in dict.items: 188 tuple = Invoke(expr=LoadName(name="Tuple"), star=None, dstar=None) 189 tuple.args = [self.dispatch(key), self.dispatch(value)] 190 args.append(tuple) 191 result.args = args 192 return result 193 194 # Logical operators. 195 196 def visitAnd(self, and_): 197 result = And(and_) 198 nodes = [] 199 for node in and_.nodes: 200 nodes.append(Invoke(expr=LoadAttr(expr=self.dispatch(node), name="__true__"), 201 params=[], star=None, dstar=None)) 202 result.nodes = nodes 203 return result 204 205 def visitOr(self, or_): 206 result = Or(or_) 207 nodes = [] 208 for node in or_.nodes: 209 nodes.append(Invoke(expr=LoadAttr(expr=self.dispatch(node), name="__true__"), 210 params=[], star=None, dstar=None)) 211 result.nodes = nodes 212 return result 213 214 def visitNot(self, not_): 215 result = Not(not_, expr=Invoke(expr=LoadAttr(expr=self.dispatch(not_.expr), name="__true__"), 216 params=[], star=None, dstar=None)) 217 return result 218 219 # Operators. 220 221 def visitUnaryAdd(self, unaryadd): 222 return Invoke(expr=LoadAttr(expr=self.dispatch(unaryadd.expr), name="__pos__"), args=[]) 223 224 def visitUnarySub(self, unarysub): 225 return Invoke(expr=LoadAttr(expr=self.dispatch(unarysub.expr), name="__neg__"), args=[]) 226 227 def visitInvert(self, invert): 228 return Invoke(expr=LoadAttr(expr=self.dispatch(invert.expr), name="__invert__"), args=[]) 229 230 # Assignments. 231 232 augassign_methods = { 233 "+=" : "__iadd__", "-=" : "__isub__", "*=" : "__imul__", "/=" : "__idiv__" 234 } 235 236 def visitAugAssign(self, augassign): 237 result = Assign(augassign) 238 expr = self.dispatch(augassign.expr) 239 240 # Simple augmented assignment: name += expr 241 242 if isinstance(augassign.node, compiler.ast.Name): 243 name = augassign.node 244 node = self.dispatch(name) 245 get_incremented = StoreTemp( 246 expr=Invoke(expr=LoadAttr(expr=node, name=self.augassign_methods[augassign.op]), args=[expr]) 247 ) 248 store = StoreName(expr=LoadTemp(), name=name.name) 249 result.code = [get_incremented, store, ReleaseTemp()] 250 251 # Complicated augmented assignment: expr.attr += expr 252 253 elif isinstance(augassign.node, compiler.ast.Getattr): 254 255 # <expr> -> <expr>.attr.__xxx__( 256 257 getattr = augassign.node 258 store_expr = StoreTemp(index="expr", expr=self.dispatch(getattr.expr)) 259 node_attr = LoadAttr(expr=LoadTemp(index="expr"), name=getattr.attrname) 260 get_incremented = StoreTemp( 261 expr=Invoke(expr=LoadAttr(expr=node_attr, name=self.augassign_methods[augassign.op]), args=[expr]) 262 ) 263 store = StoreAttr(expr=LoadTemp(), lvalue=LoadTemp(index="expr"), name=getattr.attrname) 264 result.code = [store_expr, get_incremented, store, ReleaseTemp(index="expr"), ReleaseTemp()] 265 266 # Complicated augassign using slices and subscripts. 267 268 elif isinstance(augassign.node, compiler.ast.Slice): 269 slice = augassign.node 270 store_expr = StoreTemp(index="expr", expr=self.dispatch(slice.expr)) 271 store_lower = StoreTemp(index="lower", expr=self.dispatch_or_none(slice.lower)) 272 store_upper = StoreTemp(index="upper", expr=self.dispatch_or_none(slice.upper)) 273 node_slice = self._visitSlice(LoadTemp(index="expr"), LoadTemp(index="lower"), LoadTemp(index="upper"), "OP_APPLY") 274 get_incremented = StoreTemp( 275 expr=Invoke(expr=LoadAttr(expr=node_slice, name=self.augassign_methods[augassign.op]), args=[expr]) 276 ) 277 store = self._visitSlice(LoadTemp(index="expr"), LoadTemp(index="lower"), LoadTemp(index="upper"), "OP_ASSIGN", expr) 278 result.code = [store_expr, store_lower, store_upper, get_incremented, store, 279 ReleaseTemp(index="expr"), ReleaseTemp(index="lower"), ReleaseTemp(index="upper"), ReleaseTemp()] 280 281 else: 282 raise NotImplementedError, augassign.node.__class__ 283 284 return result 285 286 def visitAssign(self, assign): 287 result = Assign(assign) 288 store = StoreTemp(expr=self.dispatch(assign.expr)) 289 release = ReleaseTemp() 290 result.code = [store] + self.dispatches(assign.nodes, 0) + [release] 291 return result 292 293 def visitAssList(self, asslist, in_sequence=0): 294 if not in_sequence: 295 expr = LoadTemp(asslist) 296 else: 297 expr = Invoke(asslist, expr=LoadAttr(expr=LoadTemp(), name="next")) 298 result = Assign(asslist) 299 store = StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=expr))) 300 release = ReleaseTemp() 301 result.code = [store] + self.dispatches(asslist.nodes, 1) + [release] 302 return result 303 304 visitAssTuple = visitAssList 305 306 def _visitAssNameOrAttr(self, node, in_sequence): 307 if not in_sequence: 308 return LoadTemp(node) 309 else: 310 return Invoke(node, expr=LoadAttr(expr=LoadTemp(), name="next")) 311 312 def visitAssName(self, assname, in_sequence=0): 313 expr = self._visitAssNameOrAttr(assname, in_sequence) 314 result = StoreName(assname, name=assname.name, expr=expr) 315 return result 316 317 def visitAssAttr(self, assattr, in_sequence=0): 318 expr = self._visitAssNameOrAttr(assattr, in_sequence) 319 lvalue = self.dispatch(assattr.expr) 320 result = StoreAttr(assattr, name=assattr.attrname, lvalue=lvalue, expr=expr) 321 return result 322 323 def _visitSlice(self, expr, lower, upper, flags, value=None): 324 if flags == "OP_ASSIGN": 325 args = [value] 326 result = Invoke(expr=LoadAttr(expr=expr, name="__setslice__")) 327 elif flags == "OP_APPLY": 328 args = [] 329 result = Invoke(expr=LoadAttr(expr=expr, name="__getslice__")) 330 else: 331 raise NotImplementedError, flags 332 333 # Add the dimensions. 334 335 args.insert(0, lower) 336 args.insert(1, upper) 337 338 result.args = args 339 return result 340 341 def visitSlice(self, slice, in_sequence=0): 342 value = self._visitAssNameOrAttr(slice, in_sequence) 343 return self._visitSlice(self.dispatch(slice.expr), self.dispatch_or_none(slice.lower), self.dispatch_or_none(slice.upper), slice.flags, value) 344 345 # Invocation and subprogram transformations. 346 347 def _visitFunction(self, function, subprogram): 348 if function.flags & 4 != 0: has_star = 1 349 else: has_star = 0 350 if function.flags & 8 != 0: has_dstar = 1 351 else: has_dstar = 0 352 ndefaults = len(function.defaults) 353 npositional = len(function.argnames) - has_star - has_dstar 354 if has_star: star = function.argnames[npositional] 355 else: star = None 356 if has_dstar: dstar = function.argnames[npositional + has_star] 357 else: dstar = None 358 359 params = [] 360 for i in range(0, npositional - ndefaults): 361 params.append((function.argnames[i], None)) 362 363 # NOTE: Fix/process defaults. 364 365 for i in range(0, ndefaults): 366 default = function.defaults[i] 367 if default is not None: 368 params.append((function.argnames[npositional - ndefaults + i], self.dispatch(default))) 369 else: 370 params.append((function.argnames[npositional - ndefaults + i], default)) 371 372 subprogram.params = params 373 subprogram.star = star 374 subprogram.dstar = dstar 375 self.subprograms.append(subprogram) 376 377 def visitFunction(self, function): 378 379 # Make a subprogram for the function and record it outside the main 380 # tree. 381 382 subprogram = Subprogram(function, name=function.name, star=None, dstar=None) 383 self.current_subprograms.append(subprogram) 384 subprogram.code = self.dispatch(function.code) 385 self.current_subprograms.pop() 386 self._visitFunction(function, subprogram) 387 388 # Make a definition of the function associating it with a name. 389 390 result = Assign(function) 391 load = LoadRef(ref=subprogram) 392 store = StoreName(name=function.name) 393 result.code = [load, store] 394 return result 395 396 def visitLambda(self, lambda_): 397 398 # Make a subprogram for the function and record it outside the main 399 # tree. 400 401 subprogram = Subprogram(lambda_, name=hex(id(lambda_)), star=None, dstar=None) 402 self.current_subprograms.append(subprogram) 403 subprogram.code = [Return(expr=self.dispatch(lambda_.code))] 404 self.current_subprograms.pop() 405 self._visitFunction(lambda_, subprogram) 406 407 # Get the subprogram reference to the lambda. 408 409 return LoadRef(ref=subprogram) 410 411 def visitCallFunc(self, callfunc): 412 result = Invoke(callfunc, same_frame=0, star=None, dstar=None) 413 result.args = self.dispatches(callfunc.args) 414 if callfunc.star_args is not None: 415 result.star = self.dispatch(callfunc.star_args) 416 if callfunc.dstar_args is not None: 417 result.dstar = self.dispatch(callfunc.dstar_args) 418 result.expr = self.dispatch(callfunc.node) 419 return result 420 421 def visitWhile(self, while_): 422 423 # Make a subprogram for the block and record it outside the main tree. 424 425 subprogram = Subprogram(while_, name=hex(id(while_)), acquire_locals=1, params=[], star=None, dstar=None) 426 self.current_subprograms.append(subprogram) 427 428 # Include a conditional statement in the subprogram. 429 430 test = Conditional(else_=[]) 431 test.test = Invoke(expr=LoadAttr(expr=self.dispatch(while_.test), name="__true__"), 432 params=[], star=None, dstar=None) 433 434 # Inside the conditional, add a recursive invocation to the subprogram 435 # if the test condition was satisfied. 436 437 continuation = Invoke(same_frame=1, star=None, dstar=None, args=[]) 438 continuation.expr = LoadRef(ref=subprogram) 439 test.body = self.dispatch(while_.body) + [continuation] 440 if while_.else_ is not None: 441 test.else_ = self.dispatch(while_.else_) 442 subprogram.code = [test] 443 444 self.current_subprograms.pop() 445 self.subprograms.append(subprogram) 446 447 # Make an invocation of the subprogram. 448 449 result = Invoke(while_, same_frame=1, star=None, dstar=None, args=[]) 450 result.expr = LoadRef(ref=subprogram) 451 return result 452 453 def visitFor(self, for_): 454 455 # Make a subprogram for the block and record it outside the main tree. 456 457 subprogram = Subprogram(for_, name=hex(id(for_)), acquire_locals=1, params=[], star=None, dstar=None) 458 self.current_subprograms.append(subprogram) 459 460 # Wrap the assignment in a try...except statement. 461 462 try_except = Try(body=[], handlers=[], else_=[], finally_=[]) 463 except_spec = Invoke(expr=LoadName(name="Tuple"), params=[LoadName(name="StopIteration")]) 464 stopiteration = Except(spec=except_spec) 465 stopiteration.code = self.dispatch(for_.else_) 466 try_except.handlers = [stopiteration] 467 468 assign = Assign() 469 assign.code = [ 470 StoreTemp(expr=Invoke(expr=LoadAttr(expr=LoadTemp(), name="next"))), 471 self.dispatch(for_.assign), 472 ReleaseTemp() 473 ] 474 475 # Inside the conditional, add a recursive invocation to the subprogram 476 # if the test condition was satisfied. 477 478 continuation = Invoke(same_frame=1, star=None, dstar=None, args=[]) 479 continuation.expr = LoadRef(ref=subprogram) 480 try_except.body = [assign] + self.dispatch(for_.body) + [continuation] 481 subprogram.code = [try_except] 482 483 self.subprograms.append(subprogram) 484 self.current_subprograms.pop() 485 486 # Obtain an iterator for the sequence involved. 487 # Then, make an invocation of the subprogram. 488 489 result = Assign(for_) 490 result.code = [ 491 StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=self.dispatch(for_.list)))), 492 Invoke(expr=LoadRef(ref=subprogram), same_frame=1, star=None, dstar=None, args=[]), 493 ReleaseTemp() 494 ] 495 return result 496 497 # Exception node transformations. 498 499 def visitTryExcept(self, tryexcept): 500 result = Try(tryexcept, body=[], handlers=[], else_=[], finally_=[]) 501 if tryexcept.body is not None: 502 result.body = self.dispatch(tryexcept.body) 503 if tryexcept.else_ is not None: 504 result.else_ = self.dispatch(tryexcept.else_) 505 handlers = [] 506 for spec, assign, stmt in tryexcept.handlers: 507 get_exc = Assign() 508 get_exc.code = [StoreTemp(expr=LoadExc())] 509 if assign is not None: 510 get_exc.code.append(self.dispatch(assign)) 511 get_exc.code.append(ReleaseTemp()) 512 handler = Except() 513 if spec is not None: 514 handler.spec = self.dispatch(spec) 515 handler.code = [get_exc] + self.dispatch(stmt) 516 handlers.append(handler) 517 result.handlers = handlers 518 return result 519 520 def visitTryFinally(self, tryfinally): 521 result = Try(tryfinally, body=[], handlers=[], else_=[], finally_=[]) 522 if tryfinally.body is not None: 523 result.body = self.dispatch(tryfinally.body) 524 if tryfinally.final is not None: 525 result.finally_ = self.dispatch(tryfinally.final) 526 return result 527 528 # vim: tabstop=4 expandtab shiftwidth=4