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, produces_result=0, 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 198 # Make a subprogram for the expression and record it outside the main tree. 199 200 subprogram = Subprogram(and_, name=hex(id(and_)), acquire_locals=1, returns_value=1, params=[], star=None, dstar=None) 201 self.current_subprograms.append(subprogram) 202 203 nodes = [] 204 last = and_.nodes[-1] 205 for node in and_.nodes: 206 expr = self.dispatch(node) 207 if node is not last: 208 invocation = Not(expr=Invoke(expr=LoadAttr(expr=StoreTemp(expr=expr), name="__true__"), 209 params=[], star=None, dstar=None)) 210 nodes.append(Conditional(test=invocation, body=[Return(expr=LoadTemp())])) 211 nodes.append(ReleaseTemp()) 212 else: 213 nodes.append(Return(expr=expr)) 214 subprogram.code = nodes 215 216 self.current_subprograms.pop() 217 self.subprograms.append(subprogram) 218 219 # Make an invocation of the subprogram. 220 221 result = Invoke(and_, same_frame=1, star=None, dstar=None, args=[]) 222 result.expr = LoadRef(ref=subprogram) 223 return result 224 225 def visitOr(self, or_): 226 227 # Make a subprogram for the expression and record it outside the main tree. 228 229 subprogram = Subprogram(or_, name=hex(id(or_)), acquire_locals=1, returns_value=1, params=[], star=None, dstar=None) 230 self.current_subprograms.append(subprogram) 231 232 nodes = [] 233 last = or_.nodes[-1] 234 for node in or_.nodes: 235 expr = self.dispatch(node) 236 if node is not last: 237 invocation = Invoke(expr=LoadAttr(expr=StoreTemp(expr=expr), name="__true__"), 238 params=[], star=None, dstar=None) 239 nodes.append(Conditional(test=invocation, body=[Return(expr=LoadTemp())])) 240 nodes.append(ReleaseTemp()) 241 else: 242 nodes.append(Return(expr=expr)) 243 subprogram.code = nodes 244 245 self.current_subprograms.pop() 246 self.subprograms.append(subprogram) 247 248 # Make an invocation of the subprogram. 249 250 result = Invoke(or_, same_frame=1, star=None, dstar=None, args=[]) 251 result.expr = LoadRef(ref=subprogram) 252 return result 253 254 def visitNot(self, not_): 255 result = Not(not_, expr=Invoke(expr=LoadAttr(expr=self.dispatch(not_.expr), name="__true__"), 256 params=[], star=None, dstar=None)) 257 return result 258 259 # Operators. 260 261 def visitUnaryAdd(self, unaryadd): 262 return Invoke(expr=LoadAttr(expr=self.dispatch(unaryadd.expr), name="__pos__"), args=[]) 263 264 def visitUnarySub(self, unarysub): 265 return Invoke(expr=LoadAttr(expr=self.dispatch(unarysub.expr), name="__neg__"), args=[]) 266 267 def visitInvert(self, invert): 268 return Invoke(expr=LoadAttr(expr=self.dispatch(invert.expr), name="__invert__"), args=[]) 269 270 # Assignments. 271 272 augassign_methods = { 273 "+=" : "__iadd__", "-=" : "__isub__", "*=" : "__imul__", "/=" : "__idiv__" 274 } 275 276 def visitAugAssign(self, augassign): 277 result = Assign(augassign) 278 expr = self.dispatch(augassign.expr) 279 280 # Simple augmented assignment: name += expr 281 282 if isinstance(augassign.node, compiler.ast.Name): 283 name = augassign.node 284 node = self.dispatch(name) 285 get_incremented = StoreTemp( 286 expr=Invoke(expr=LoadAttr(expr=node, name=self.augassign_methods[augassign.op]), args=[expr]) 287 ) 288 store = StoreName(expr=LoadTemp(), name=name.name) 289 result.code = [get_incremented, store, ReleaseTemp()] 290 291 # Complicated augmented assignment: expr.attr += expr 292 293 elif isinstance(augassign.node, compiler.ast.Getattr): 294 295 # <expr> -> <expr>.attr.__xxx__( 296 297 getattr = augassign.node 298 store_expr = StoreTemp(index="expr", expr=self.dispatch(getattr.expr)) 299 node_attr = LoadAttr(expr=LoadTemp(index="expr"), name=getattr.attrname) 300 get_incremented = StoreTemp( 301 expr=Invoke(expr=LoadAttr(expr=node_attr, name=self.augassign_methods[augassign.op]), args=[expr]) 302 ) 303 store = StoreAttr(expr=LoadTemp(), lvalue=LoadTemp(index="expr"), name=getattr.attrname) 304 result.code = [store_expr, get_incremented, store, ReleaseTemp(index="expr"), ReleaseTemp()] 305 306 # Complicated augassign using slices and subscripts. 307 308 elif isinstance(augassign.node, compiler.ast.Slice): 309 slice = augassign.node 310 store_expr = StoreTemp(index="expr", expr=self.dispatch(slice.expr)) 311 store_lower = StoreTemp(index="lower", expr=self.dispatch_or_none(slice.lower)) 312 store_upper = StoreTemp(index="upper", expr=self.dispatch_or_none(slice.upper)) 313 node_slice = self._visitSlice(LoadTemp(index="expr"), LoadTemp(index="lower"), LoadTemp(index="upper"), "OP_APPLY") 314 get_incremented = StoreTemp( 315 expr=Invoke(expr=LoadAttr(expr=node_slice, name=self.augassign_methods[augassign.op]), args=[expr]) 316 ) 317 store = self._visitSlice(LoadTemp(index="expr"), LoadTemp(index="lower"), LoadTemp(index="upper"), "OP_ASSIGN", expr) 318 result.code = [store_expr, store_lower, store_upper, get_incremented, store, 319 ReleaseTemp(index="expr"), ReleaseTemp(index="lower"), ReleaseTemp(index="upper"), ReleaseTemp()] 320 321 else: 322 raise NotImplementedError, augassign.node.__class__ 323 324 return result 325 326 def visitAssign(self, assign): 327 result = Assign(assign) 328 store = StoreTemp(expr=self.dispatch(assign.expr)) 329 release = ReleaseTemp() 330 result.code = [store] + self.dispatches(assign.nodes, 0) + [release] 331 return result 332 333 def visitAssList(self, asslist, in_sequence=0): 334 if not in_sequence: 335 expr = LoadTemp(asslist) 336 else: 337 expr = Invoke(asslist, expr=LoadAttr(expr=LoadTemp(), name="next")) 338 result = Assign(asslist) 339 store = StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=expr))) 340 release = ReleaseTemp() 341 result.code = [store] + self.dispatches(asslist.nodes, 1) + [release] 342 return result 343 344 visitAssTuple = visitAssList 345 346 def _visitAssNameOrAttr(self, node, in_sequence): 347 if not in_sequence: 348 return LoadTemp(node) 349 else: 350 return Invoke(node, expr=LoadAttr(expr=LoadTemp(), name="next")) 351 352 def visitAssName(self, assname, in_sequence=0): 353 expr = self._visitAssNameOrAttr(assname, in_sequence) 354 result = StoreName(assname, name=assname.name, expr=expr) 355 return result 356 357 def visitAssAttr(self, assattr, in_sequence=0): 358 expr = self._visitAssNameOrAttr(assattr, in_sequence) 359 lvalue = self.dispatch(assattr.expr) 360 result = StoreAttr(assattr, name=assattr.attrname, lvalue=lvalue, expr=expr) 361 return result 362 363 def _visitSlice(self, expr, lower, upper, flags, value=None): 364 if flags == "OP_ASSIGN": 365 args = [value] 366 result = Invoke(expr=LoadAttr(expr=expr, name="__setslice__")) 367 elif flags == "OP_APPLY": 368 args = [] 369 result = Invoke(expr=LoadAttr(expr=expr, name="__getslice__")) 370 else: 371 raise NotImplementedError, flags 372 373 # Add the dimensions. 374 375 args.insert(0, lower) 376 args.insert(1, upper) 377 378 result.args = args 379 return result 380 381 def visitSlice(self, slice, in_sequence=0): 382 value = self._visitAssNameOrAttr(slice, in_sequence) 383 return self._visitSlice(self.dispatch(slice.expr), self.dispatch_or_none(slice.lower), self.dispatch_or_none(slice.upper), slice.flags, value) 384 385 # Invocation and subprogram transformations. 386 387 def _visitFunction(self, function, subprogram): 388 if function.flags & 4 != 0: has_star = 1 389 else: has_star = 0 390 if function.flags & 8 != 0: has_dstar = 1 391 else: has_dstar = 0 392 ndefaults = len(function.defaults) 393 npositional = len(function.argnames) - has_star - has_dstar 394 if has_star: star = function.argnames[npositional] 395 else: star = None 396 if has_dstar: dstar = function.argnames[npositional + has_star] 397 else: dstar = None 398 399 params = [] 400 for i in range(0, npositional - ndefaults): 401 params.append((function.argnames[i], None)) 402 403 # NOTE: Fix/process defaults. 404 405 for i in range(0, ndefaults): 406 default = function.defaults[i] 407 if default is not None: 408 params.append((function.argnames[npositional - ndefaults + i], self.dispatch(default))) 409 else: 410 params.append((function.argnames[npositional - ndefaults + i], default)) 411 412 subprogram.params = params 413 subprogram.star = star 414 subprogram.dstar = dstar 415 self.subprograms.append(subprogram) 416 417 def visitFunction(self, function): 418 419 # Make a subprogram for the function and record it outside the main 420 # tree. 421 422 subprogram = Subprogram(function, name=function.name, returns_value=1, star=None, dstar=None) 423 self.current_subprograms.append(subprogram) 424 subprogram.code = self.dispatch(function.code) 425 self.current_subprograms.pop() 426 self._visitFunction(function, subprogram) 427 428 # Make a definition of the function associating it with a name. 429 430 result = Assign(function) 431 load = LoadRef(ref=subprogram) 432 store = StoreName(name=function.name) 433 result.code = [load, store] 434 return result 435 436 def visitLambda(self, lambda_): 437 438 # Make a subprogram for the function and record it outside the main 439 # tree. 440 441 subprogram = Subprogram(lambda_, name=hex(id(lambda_)), returns_value=1, star=None, dstar=None) 442 self.current_subprograms.append(subprogram) 443 subprogram.code = [Return(expr=self.dispatch(lambda_.code))] 444 self.current_subprograms.pop() 445 self._visitFunction(lambda_, subprogram) 446 447 # Get the subprogram reference to the lambda. 448 449 return LoadRef(ref=subprogram) 450 451 def visitCallFunc(self, callfunc): 452 result = Invoke(callfunc, same_frame=0, star=None, dstar=None) 453 result.args = self.dispatches(callfunc.args) 454 if callfunc.star_args is not None: 455 result.star = self.dispatch(callfunc.star_args) 456 if callfunc.dstar_args is not None: 457 result.dstar = self.dispatch(callfunc.dstar_args) 458 result.expr = self.dispatch(callfunc.node) 459 return result 460 461 def visitWhile(self, while_): 462 463 # Make a subprogram for the block and record it outside the main tree. 464 465 subprogram = Subprogram(while_, name=hex(id(while_)), acquire_locals=1, returns_value=0, params=[], star=None, dstar=None) 466 self.current_subprograms.append(subprogram) 467 468 # Include a conditional statement in the subprogram. 469 470 test = Conditional(else_=[]) 471 test.test = Invoke(expr=LoadAttr(expr=self.dispatch(while_.test), name="__true__"), 472 params=[], star=None, dstar=None) 473 474 # Inside the conditional, add a recursive invocation to the subprogram 475 # if the test condition was satisfied. 476 477 continuation = Invoke(same_frame=1, star=None, dstar=None, args=[]) 478 continuation.expr = LoadRef(ref=subprogram) 479 test.body = self.dispatch(while_.body) + [continuation] 480 if while_.else_ is not None: 481 test.else_ = self.dispatch(while_.else_) 482 subprogram.code = [test] 483 484 self.current_subprograms.pop() 485 self.subprograms.append(subprogram) 486 487 # Make an invocation of the subprogram. 488 489 result = Invoke(while_, same_frame=1, produces_result=0, star=None, dstar=None, args=[]) 490 result.expr = LoadRef(ref=subprogram) 491 return result 492 493 def visitFor(self, for_): 494 495 # Make a subprogram for the block and record it outside the main tree. 496 497 subprogram = Subprogram(for_, name=hex(id(for_)), acquire_locals=1, returns_value=0, params=[], star=None, dstar=None) 498 self.current_subprograms.append(subprogram) 499 500 # Wrap the assignment in a try...except statement. 501 502 try_except = Try(body=[], handlers=[], else_=[], finally_=[]) 503 except_spec = Invoke(expr=LoadName(name="Tuple"), params=[LoadName(name="StopIteration")]) 504 stopiteration = Except(spec=except_spec) 505 stopiteration.code = self.dispatch(for_.else_) 506 try_except.handlers = [stopiteration] 507 508 assign = Assign() 509 assign.code = [ 510 StoreTemp(expr=Invoke(expr=LoadAttr(expr=LoadTemp(), name="next"))), 511 self.dispatch(for_.assign), 512 ReleaseTemp() 513 ] 514 515 # Inside the conditional, add a recursive invocation to the subprogram 516 # if the test condition was satisfied. 517 518 continuation = Invoke(same_frame=1, produces_result=0, star=None, dstar=None, args=[]) 519 continuation.expr = LoadRef(ref=subprogram) 520 try_except.body = [assign] + self.dispatch(for_.body) + [continuation] 521 subprogram.code = [try_except] 522 523 self.subprograms.append(subprogram) 524 self.current_subprograms.pop() 525 526 # Obtain an iterator for the sequence involved. 527 # Then, make an invocation of the subprogram. 528 529 result = Assign(for_) 530 result.code = [ 531 StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=self.dispatch(for_.list)))), 532 Invoke(expr=LoadRef(ref=subprogram), same_frame=1, produces_result=0, star=None, dstar=None, args=[]), 533 ReleaseTemp() 534 ] 535 return result 536 537 # Exception node transformations. 538 539 def visitTryExcept(self, tryexcept): 540 result = Try(tryexcept, body=[], handlers=[], else_=[], finally_=[]) 541 if tryexcept.body is not None: 542 result.body = self.dispatch(tryexcept.body) 543 if tryexcept.else_ is not None: 544 result.else_ = self.dispatch(tryexcept.else_) 545 handlers = [] 546 for spec, assign, stmt in tryexcept.handlers: 547 get_exc = Assign() 548 get_exc.code = [StoreTemp(expr=LoadExc())] 549 if assign is not None: 550 get_exc.code.append(self.dispatch(assign)) 551 get_exc.code.append(ReleaseTemp()) 552 handler = Except() 553 if spec is not None: 554 handler.spec = self.dispatch(spec) 555 handler.code = [get_exc] + self.dispatch(stmt) 556 handlers.append(handler) 557 result.handlers = handlers 558 return result 559 560 def visitTryFinally(self, tryfinally): 561 result = Try(tryfinally, body=[], handlers=[], else_=[], finally_=[]) 562 if tryfinally.body is not None: 563 result.body = self.dispatch(tryfinally.body) 564 if tryfinally.final is not None: 565 result.finally_ = self.dispatch(tryfinally.final) 566 return result 567 568 # vim: tabstop=4 expandtab shiftwidth=4