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 # Placeholder or deletion transformations. 66 67 def visitStmt(self, stmt): 68 return self.dispatches(stmt.nodes) 69 70 def visitPass(self, pass_): 71 return Pass(pass_) 72 73 def visitDiscard(self, discard): 74 return self.dispatch(discard.expr) 75 76 # Relatively trivial transformations. 77 78 def visitModule(self, module): 79 self.result = Module(module) 80 self.result.code = self.dispatch(module.node) 81 return self.result 82 83 def visitClass(self, class_): 84 result = Class(class_, name=class_.name, bases=class_.bases) 85 result.code = self.dispatch(class_.code) 86 return result 87 88 def visitGetattr(self, getattr): 89 result = LoadAttr(getattr, name=getattr.attrname) 90 result.expr = self.dispatch(getattr.expr) 91 return result 92 93 def visitKeyword(self, keyword): 94 result = Keyword(keyword, name=keyword.name) 95 result.expr = self.dispatch(keyword.expr) 96 return result 97 98 def visitGlobal(self, global_): 99 result = Global(global_, names=global_.names) 100 return result 101 102 def visitImport(self, import_): 103 result = Assign(import_) 104 code = [] 105 for path, alias in import_.names: 106 importer = Import(name=path) 107 top = alias or path.split(".")[0] 108 code.append(StoreName(expr=importer, name=top)) 109 result.code = code 110 return result 111 112 def visitFrom(self, from_): 113 result = Assign(from_) 114 code = [] 115 code.append(StoreTemp(expr=Import(name=from_.modname))) 116 for name, alias in from_.names: 117 code.append(StoreName(expr=LoadAttr(expr=LoadTemp(), name=name), name=(alias or name))) 118 result.code = code 119 return result 120 121 def visitName(self, name): 122 result = LoadName(name, name=name.name) 123 return result 124 125 def visitConst(self, const): 126 result = LoadConst(const, value=const.value) 127 return result 128 129 def visitReturn(self, return_): 130 result = Return(return_) 131 result.expr = self.dispatch(return_.value) 132 return result 133 134 def visitBreak(self, break_): 135 result = Return(break_) 136 return result 137 138 def visitContinue(self, continue_): 139 result = Invoke(continue_, same_frame=1, star=None, dstar=None, args=[]) 140 result.expr = LoadRef(ref=self.current_subprograms[-1]) 141 return result 142 143 def visitRaise(self, raise_): 144 result = Raise(raise_, expr=self.dispatch(raise_.expr1), traceback=None) 145 if raise_.expr2 is not None: 146 result.args = [self.dispatch(raise_.expr2)] 147 if raise_.expr3 is not None: 148 result.traceback = self.dispatch(raise_.expr3) 149 return result 150 151 def visitIf(self, if_): 152 result = If(if_, else_=[]) 153 tests = [] 154 for compare, stmt in if_.tests: 155 # Produce something like... 156 # expr.__true__() ? body 157 test = Conditional(else_=[], test=Invoke( 158 expr=LoadAttr(expr=self.dispatch(compare), name="__true__"), 159 params=[], star=None, dstar=None)) 160 test.body = self.dispatch(stmt) 161 tests.append(test) 162 result.tests = tests 163 if if_.else_ is not None: 164 result.else_ = self.dispatch(if_.else_) 165 return result 166 167 def _visitBuiltin(self, builtin, name): 168 result = Invoke(builtin, expr=LoadName(name=name)) 169 result.args = self.dispatches(builtin.nodes) 170 return result 171 172 def visitTuple(self, tuple): 173 return self._visitBuiltin(tuple, "Tuple") 174 175 def visitList(self, list): 176 return self._visitBuiltin(list, "List") 177 178 def visitDict(self, dict): 179 result = Invoke(expr=LoadName(name="Dict")) 180 args = [] 181 for key, value in dict.items: 182 tuple = Invoke(expr=LoadName(name="Tuple"), star=None, dstar=None) 183 tuple.args = [self.dispatch(key), self.dispatch(value)] 184 args.append(tuple) 185 result.args = args 186 return result 187 188 # Logical operators. 189 190 def visitAnd(self, and_): 191 result = And(and_) 192 nodes = [] 193 for node in and_.nodes: 194 nodes.append(Invoke(expr=LoadAttr(expr=self.dispatch(node), name="__true__"), 195 params=[], star=None, dstar=None)) 196 result.nodes = nodes 197 return result 198 199 def visitOr(self, or_): 200 result = Or(or_) 201 nodes = [] 202 for node in or_.nodes: 203 nodes.append(Invoke(expr=LoadAttr(expr=self.dispatch(node), name="__true__"), 204 params=[], star=None, dstar=None)) 205 result.nodes = nodes 206 return result 207 208 def visitNot(self, not_): 209 result = Not(not_, expr=Invoke(expr=LoadAttr(expr=self.dispatch(not_.expr), name="__true__"), 210 params=[], star=None, dstar=None)) 211 return result 212 213 # Operators. 214 215 def visitUnaryAdd(self, unaryadd): 216 return Invoke(expr=LoadAttr(expr=self.dispatch(unaryadd.expr), name="__pos__"), args=[]) 217 218 def visitUnarySub(self, unarysub): 219 return Invoke(expr=LoadAttr(expr=self.dispatch(unarysub.expr), name="__neg__"), args=[]) 220 221 def visitInvert(self, invert): 222 return Invoke(expr=LoadAttr(expr=self.dispatch(invert.expr), name="__invert__"), args=[]) 223 224 # Assignments. 225 226 augassign_methods = { 227 "+=" : "__iadd__", "-=" : "__isub__", "*=" : "__imul__", "/=" : "__idiv__" 228 } 229 230 def visitAugAssign(self, augassign): 231 result = Assign(augassign) 232 expr = self.dispatch(augassign.expr) 233 234 # Simple augmented assignment: name += expr 235 236 if isinstance(augassign.node, compiler.ast.Name): 237 node = self.dispatch(augassign.node) 238 get_incremented = StoreTemp( 239 expr=Invoke(expr=LoadAttr(expr=node, name=self.augassign_methods[augassign.op]), args=[expr]) 240 ) 241 store = StoreName(expr=LoadTemp(), name=augassign.node.name) 242 result.code = [get_incremented, store, ReleaseTemp()] 243 244 # Complicated augmented assignment: expr.attr += expr 245 246 elif isinstance(augassign.node, compiler.ast.Getattr): 247 store_expr = StoreTemp(index=1, expr=self.dispatch(augassign.node.expr)) 248 node_attr = LoadAttr(expr=LoadTemp(index=1), name=augassign.node.attrname) 249 get_incremented = StoreTemp( 250 expr=Invoke(expr=LoadAttr(expr=node_attr, name=self.augassign_methods[augassign.op]), args=[expr]) 251 ) 252 store = StoreAttr(expr=LoadTemp(), lvalue=LoadTemp(index=1), name=augassign.node.attrname) 253 result.code = [store_expr, get_incremented, store, ReleaseTemp(index=1), ReleaseTemp()] 254 255 else: 256 raise NotImplementedError, augassign.node.__class__ 257 258 return result 259 260 def visitAssign(self, assign): 261 result = Assign(assign) 262 store = StoreTemp(expr=self.dispatch(assign.expr)) 263 release = ReleaseTemp() 264 result.code = [store] + self.dispatches(assign.nodes, 0) + [release] 265 return result 266 267 def visitAssList(self, asslist, in_sequence=0): 268 if not in_sequence: 269 expr = LoadTemp(asslist) 270 else: 271 expr = Invoke(asslist, expr=LoadAttr(expr=LoadTemp(), name="next")) 272 result = Assign(asslist) 273 store = StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=expr))) 274 release = ReleaseTemp() 275 result.code = [store] + self.dispatches(asslist.nodes, 1) + [release] 276 return result 277 278 visitAssTuple = visitAssList 279 280 def _visitAssNameOrAttr(self, node, in_sequence): 281 if not in_sequence: 282 return LoadTemp(node) 283 else: 284 return Invoke(node, expr=LoadAttr(expr=LoadTemp(), name="next")) 285 286 def visitAssName(self, assname, in_sequence=0): 287 expr = self._visitAssNameOrAttr(assname, in_sequence) 288 result = StoreName(assname, name=assname.name, expr=expr) 289 return result 290 291 def visitAssAttr(self, assattr, in_sequence=0): 292 expr = self._visitAssNameOrAttr(assattr, in_sequence) 293 lvalue = self.dispatch(assattr.expr) 294 result = StoreAttr(assattr, name=assattr.attrname, lvalue=lvalue, expr=expr) 295 return result 296 297 # Invocation and subprogram transformations. 298 299 def _visitFunction(self, function, subprogram): 300 if function.flags & 4 != 0: has_star = 1 301 else: has_star = 0 302 if function.flags & 8 != 0: has_dstar = 1 303 else: has_dstar = 0 304 ndefaults = len(function.defaults) 305 npositional = len(function.argnames) - has_star - has_dstar 306 if has_star: star = function.argnames[npositional] 307 else: star = None 308 if has_dstar: dstar = function.argnames[npositional + has_star] 309 else: dstar = None 310 311 params = [] 312 for i in range(0, npositional - ndefaults): 313 params.append((function.argnames[i], None)) 314 315 # NOTE: Fix/process defaults. 316 317 for i in range(0, ndefaults): 318 default = function.defaults[i] 319 if default is not None: 320 params.append((function.argnames[npositional - ndefaults + i], self.dispatch(default))) 321 else: 322 params.append((function.argnames[npositional - ndefaults + i], default)) 323 324 subprogram.params = params 325 subprogram.star = star 326 subprogram.dstar = dstar 327 self.subprograms.append(subprogram) 328 329 def visitFunction(self, function): 330 331 # Make a subprogram for the function and record it outside the main 332 # tree. 333 334 subprogram = Subprogram(function, name=function.name, star=None, dstar=None) 335 self.current_subprograms.append(subprogram) 336 subprogram.code = self.dispatch(function.code) 337 self.current_subprograms.pop() 338 self._visitFunction(function, subprogram) 339 340 # Make a definition of the function associating it with a name. 341 342 result = Assign(function) 343 load = LoadRef(ref=subprogram) 344 store = StoreName(name=function.name) 345 result.code = [load, store] 346 return result 347 348 def visitLambda(self, lambda_): 349 350 # Make a subprogram for the function and record it outside the main 351 # tree. 352 353 subprogram = Subprogram(lambda_, name=hex(id(lambda_)), star=None, dstar=None) 354 self.current_subprograms.append(subprogram) 355 subprogram.code = [Return(expr=self.dispatch(lambda_.code))] 356 self.current_subprograms.pop() 357 self._visitFunction(lambda_, subprogram) 358 359 # Get the subprogram reference to the lambda. 360 361 return LoadRef(ref=subprogram) 362 363 def visitCallFunc(self, callfunc): 364 result = Invoke(callfunc, same_frame=0, star=None, dstar=None) 365 result.args = self.dispatches(callfunc.args) 366 if callfunc.star_args is not None: 367 result.star = self.dispatch(callfunc.star_args) 368 if callfunc.dstar_args is not None: 369 result.dstar = self.dispatch(callfunc.dstar_args) 370 result.expr = self.dispatch(callfunc.node) 371 return result 372 373 def visitWhile(self, while_): 374 375 # Make a subprogram for the block and record it outside the main tree. 376 377 subprogram = Subprogram(while_, name=hex(id(while_)), acquire_locals=1, params=[], star=None, dstar=None) 378 self.current_subprograms.append(subprogram) 379 380 # Include a conditional statement in the subprogram. 381 382 test = Conditional(else_=[]) 383 test.test = Invoke(expr=LoadAttr(expr=self.dispatch(while_.test), name="__true__"), 384 params=[], star=None, dstar=None) 385 386 # Inside the conditional, add a recursive invocation to the subprogram 387 # if the test condition was satisfied. 388 389 continuation = Invoke(same_frame=1, star=None, dstar=None, args=[]) 390 continuation.expr = LoadRef(ref=subprogram) 391 test.body = self.dispatch(while_.body) + [continuation] 392 if while_.else_ is not None: 393 test.else_ = self.dispatch(while_.else_) 394 subprogram.code = [test] 395 396 self.current_subprograms.pop() 397 self.subprograms.append(subprogram) 398 399 # Make an invocation of the subprogram. 400 401 result = Invoke(while_, same_frame=1, star=None, dstar=None, args=[]) 402 result.expr = LoadRef(ref=subprogram) 403 return result 404 405 def visitFor(self, for_): 406 407 # Make a subprogram for the block and record it outside the main tree. 408 409 subprogram = Subprogram(for_, name=hex(id(for_)), acquire_locals=1, params=[], star=None, dstar=None) 410 self.current_subprograms.append(subprogram) 411 412 # Wrap the assignment in a try...except statement. 413 414 try_except = Try(body=[], handlers=[], else_=[], finally_=[]) 415 except_spec = Invoke(expr=LoadName(name="Tuple"), params=[LoadName(name="StopIteration")]) 416 stopiteration = Except(spec=except_spec) 417 stopiteration.code = self.dispatch(for_.else_) 418 try_except.handlers = [stopiteration] 419 420 assign = Assign() 421 assign.code = [ 422 StoreTemp(expr=Invoke(expr=LoadAttr(expr=LoadTemp(), name="next"))), 423 self.dispatch(for_.assign), 424 ReleaseTemp() 425 ] 426 427 # Inside the conditional, add a recursive invocation to the subprogram 428 # if the test condition was satisfied. 429 430 continuation = Invoke(same_frame=1, star=None, dstar=None, args=[]) 431 continuation.expr = LoadRef(ref=subprogram) 432 try_except.body = [assign] + self.dispatch(for_.body) + [continuation] 433 subprogram.code = [try_except] 434 435 self.subprograms.append(subprogram) 436 self.current_subprograms.pop() 437 438 # Obtain an iterator for the sequence involved. 439 # Then, make an invocation of the subprogram. 440 441 result = Assign(for_) 442 result.code = [ 443 StoreTemp(expr=Invoke(expr=LoadAttr(name="__iter__", expr=self.dispatch(for_.list)))), 444 Invoke(expr=LoadRef(ref=subprogram), same_frame=1, star=None, dstar=None, args=[]), 445 ReleaseTemp() 446 ] 447 return result 448 449 # Exception node transformations. 450 451 def visitTryExcept(self, tryexcept): 452 result = Try(tryexcept, body=[], handlers=[], else_=[], finally_=[]) 453 if tryexcept.body is not None: 454 result.body = self.dispatch(tryexcept.body) 455 if tryexcept.else_ is not None: 456 result.else_ = self.dispatch(tryexcept.else_) 457 handlers = [] 458 for spec, assign, stmt in tryexcept.handlers: 459 get_exc = Assign() 460 get_exc.code = [StoreTemp(expr=LoadExc())] 461 if assign is not None: 462 get_exc.code.append(self.dispatch(assign)) 463 get_exc.code.append(ReleaseTemp()) 464 handler = Except() 465 if spec is not None: 466 handler.spec = self.dispatch(spec) 467 handler.code = [get_exc] + self.dispatch(stmt) 468 handlers.append(handler) 469 result.handlers = handlers 470 return result 471 472 def visitTryFinally(self, tryfinally): 473 result = Try(tryfinally, body=[], handlers=[], else_=[], finally_=[]) 474 if tryfinally.body is not None: 475 result.body = self.dispatch(tryfinally.body) 476 if tryfinally.final is not None: 477 result.finally_ = self.dispatch(tryfinally.final) 478 return result 479 480 # vim: tabstop=4 expandtab shiftwidth=4