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