diff options
Diffstat (limited to 'Lib')
-rw-r--r-- | Lib/compiler/ast.py | 76 | ||||
-rw-r--r-- | Lib/compiler/pycodegen.py | 89 | ||||
-rw-r--r-- | Lib/compiler/symbols.py | 41 | ||||
-rw-r--r-- | Lib/compiler/transformer.py | 53 | ||||
-rwxr-xr-x | Lib/symbol.py | 38 | ||||
-rw-r--r-- | Lib/test/test_deque.py | 2 | ||||
-rw-r--r-- | Lib/test/test_genexps.py | 258 | ||||
-rw-r--r-- | Lib/test/test_grammar.py | 43 | ||||
-rw-r--r-- | Lib/test/test_parser.py | 2 |
9 files changed, 584 insertions, 18 deletions
diff --git a/Lib/compiler/ast.py b/Lib/compiler/ast.py index a10225b..064df50 100644 --- a/Lib/compiler/ast.py +++ b/Lib/compiler/ast.py @@ -1236,6 +1236,82 @@ class ListCompFor(Node): def __repr__(self): return "ListCompFor(%s, %s, %s)" % (repr(self.assign), repr(self.list), repr(self.ifs)) +class GenExpr(Node): + nodes["genexpr"] = "GenExpr" + def __init__(self, code): + self.code = code + self.argnames = ['[outmost-iterable]'] + self.varargs = self.kwargs = None + + def getChildren(self): + return self.code, + + def getChildNodes(self): + return self.code, + + def __repr__(self): + return "GenExpr(%s)" % (repr(self.code),) + +class GenExprInner(Node): + nodes["genexprinner"] = "GenExprInner" + def __init__(self, expr, quals): + self.expr = expr + self.quals = quals + + def getChildren(self): + children = [] + children.append(self.expr) + children.extend(flatten(self.quals)) + return tuple(children) + + def getChildNodes(self): + nodelist = [] + nodelist.append(self.expr) + nodelist.extend(flatten_nodes(self.quals)) + return tuple(nodelist) + + def __repr__(self): + return "GenExprInner(%s, %s)" % (repr(self.expr), repr(self.quals)) + +class GenExprFor(Node): + nodes["genexprfor"] = "GenExprFor" + def __init__(self, assign, iter, ifs): + self.assign = assign + self.iter = iter + self.ifs = ifs + self.is_outmost = False + + def getChildren(self): + children = [] + children.append(self.assign) + children.append(self.iter) + children.extend(flatten(self.ifs)) + return tuple(children) + + def getChildNodes(self): + nodelist = [] + nodelist.append(self.assign) + nodelist.append(self.iter) + nodelist.extend(flatten_nodes(self.ifs)) + return tuple(nodelist) + + def __repr__(self): + return "GenExprFor(%s, %s, %s)" % (repr(self.assign), repr(self.iter), repr(self.ifs)) + +class GenExprIf(Node): + nodes["genexprif"] = "GenExprIf" + def __init__(self, test): + self.test = test + + def getChildren(self): + return self.test, + + def getChildNodes(self): + return self.test, + + def __repr__(self): + return "GenExprIf(%s)" % (repr(self.test),) + klasses = globals() for k in nodes.keys(): nodes[k] = klasses[nodes[k]] diff --git a/Lib/compiler/pycodegen.py b/Lib/compiler/pycodegen.py index 292e859..ef5a0d3 100644 --- a/Lib/compiler/pycodegen.py +++ b/Lib/compiler/pycodegen.py @@ -619,6 +619,79 @@ class CodeGenerator: self.newBlock() self.emit('POP_TOP') + def visitGenExpr(self, node): + gen = GenExprCodeGenerator(node, self.scopes, self.class_name, + self.get_module()) + walk(node.code, gen) + gen.finish() + self.set_lineno(node) + frees = gen.scope.get_free_vars() + if frees: + for name in frees: + self.emit('LOAD_CLOSURE', name) + self.emit('LOAD_CONST', gen) + self.emit('MAKE_CLOSURE', 0) + else: + self.emit('LOAD_CONST', gen) + self.emit('MAKE_FUNCTION', 0) + + # precomputation of outmost iterable + self.visit(node.code.quals[0].iter) + self.emit('GET_ITER') + self.emit('CALL_FUNCTION', 1) + + def visitGenExprInner(self, node): + self.set_lineno(node) + # setup list + + stack = [] + for i, for_ in zip(range(len(node.quals)), node.quals): + start, anchor = self.visit(for_) + cont = None + for if_ in for_.ifs: + if cont is None: + cont = self.newBlock() + self.visit(if_, cont) + stack.insert(0, (start, cont, anchor)) + + self.visit(node.expr) + self.emit('YIELD_VALUE') + + for start, cont, anchor in stack: + if cont: + skip_one = self.newBlock() + self.emit('JUMP_FORWARD', skip_one) + self.startBlock(cont) + self.emit('POP_TOP') + self.nextBlock(skip_one) + self.emit('JUMP_ABSOLUTE', start) + self.startBlock(anchor) + self.emit('LOAD_CONST', None) + + def visitGenExprFor(self, node): + start = self.newBlock() + anchor = self.newBlock() + + if node.is_outmost: + self.loadName('[outmost-iterable]') + else: + self.visit(node.iter) + self.emit('GET_ITER') + + self.nextBlock(start) + self.set_lineno(node, force=True) + self.emit('FOR_ITER', anchor) + self.nextBlock() + self.visit(node.assign) + return start, anchor + + def visitGenExprIf(self, node, branch): + self.set_lineno(node, force=True) + self.visit(node.test) + self.emit('JUMP_IF_FALSE', branch) + self.newBlock() + self.emit('POP_TOP') + # exception related def visitAssert(self, node): @@ -1199,6 +1272,7 @@ class AbstractFunctionCode: klass.lambdaCount = klass.lambdaCount + 1 else: name = func.name + args, hasTupleArg = generateArgList(func.argnames) self.graph = pyassem.PyFlowGraph(name, func.filename, args, optimized=1) @@ -1263,6 +1337,21 @@ class FunctionCodeGenerator(NestedScopeMixin, AbstractFunctionCode, if self.scope.generator is not None: self.graph.setFlag(CO_GENERATOR) +class GenExprCodeGenerator(NestedScopeMixin, AbstractFunctionCode, + CodeGenerator): + super_init = CodeGenerator.__init__ # call be other init + scopes = None + + __super_init = AbstractFunctionCode.__init__ + + def __init__(self, gexp, scopes, class_name, mod): + self.scopes = scopes + self.scope = scopes[gexp] + self.__super_init(gexp, scopes, 1, class_name, mod) + self.graph.setFreeVars(self.scope.get_free_vars()) + self.graph.setCellVars(self.scope.get_cell_vars()) + self.graph.setFlag(CO_GENERATOR) + class AbstractClassCode: def __init__(self, klass, scopes, module): diff --git a/Lib/compiler/symbols.py b/Lib/compiler/symbols.py index fa668f1..6843e19 100644 --- a/Lib/compiler/symbols.py +++ b/Lib/compiler/symbols.py @@ -179,6 +179,21 @@ class ModuleScope(Scope): class FunctionScope(Scope): pass +class GenExprScope(Scope): + __super_init = Scope.__init__ + + __counter = 1 + + def __init__(self, module, klass=None): + i = self.__counter + self.__counter += 1 + self.__super_init("generator expression<%d>"%i, module, klass) + self.add_param('[outmost-iterable]') + + def get_names(self): + keys = Scope.get_names() + return keys + class LambdaScope(FunctionScope): __super_init = Scope.__init__ @@ -220,6 +235,32 @@ class SymbolVisitor: self.visit(node.code, scope) self.handle_free_vars(scope, parent) + def visitGenExpr(self, node, parent): + scope = GenExprScope(self.module, self.klass); + if parent.nested or isinstance(parent, FunctionScope) \ + or isinstance(parent, GenExprScope): + scope.nested = 1 + + self.scopes[node] = scope + self.visit(node.code, scope) + + self.handle_free_vars(scope, parent) + + def visitGenExprInner(self, node, scope): + for genfor in node.quals: + self.visit(genfor, scope) + + self.visit(node.expr, scope) + + def visitGenExprFor(self, node, scope): + self.visit(node.assign, scope, 1) + self.visit(node.iter, scope) + for if_ in node.ifs: + self.visit(if_, scope) + + def visitGenExprIf(self, node, scope): + self.visit(node.test, scope) + def visitLambda(self, node, parent, assign=0): # Lambda is an expression, so it could appear in an expression # context where assign is passed. The transformer should catch diff --git a/Lib/compiler/transformer.py b/Lib/compiler/transformer.py index 9074fc7..6832cf1 100644 --- a/Lib/compiler/transformer.py +++ b/Lib/compiler/transformer.py @@ -534,6 +534,12 @@ class Transformer: testlist1 = testlist exprlist = testlist + def testlist_gexp(self, nodelist): + if len(nodelist) == 2 and nodelist[1][0] == symbol.gen_for: + test = self.com_node(nodelist[0]) + return self.com_generator_expression(test, nodelist[1]) + return self.testlist(nodelist) + def test(self, nodelist): # and_test ('or' and_test)* | lambdef if len(nodelist) == 1 and nodelist[0][0] == symbol.lambdef: @@ -1085,6 +1091,48 @@ class Transformer: values.append(self.com_node(nodelist[i])) return List(values) + if hasattr(symbol, 'gen_for'): + def com_generator_expression(self, expr, node): + # gen_iter: gen_for | gen_if + # gen_for: 'for' exprlist 'in' test [gen_iter] + # gen_if: 'if' test [gen_iter] + + lineno = node[1][2] + fors = [] + while node: + t = node[1][1] + if t == 'for': + assignNode = self.com_assign(node[2], OP_ASSIGN) + genNode = self.com_node(node[4]) + newfor = GenExprFor(assignNode, genNode, []) + newfor.lineno = node[1][2] + fors.append(newfor) + if (len(node)) == 5: + node = None + else: + node = self.com_gen_iter(node[5]) + elif t == 'if': + test = self.com_node(node[2]) + newif = GenExprIf(test) + newif.lineno = node[1][2] + newfor.ifs.append(newif) + if len(node) == 3: + node = None + else: + node = self.com_gen_iter(node[3]) + else: + raise SyntaxError, \ + ("unexpected generator expression element: %s %d" + % (node, lineno)) + fors[0].is_outmost = True + n = GenExpr(GenExprInner(expr, fors)) + n.lineno = lineno + return n + + def com_gen_iter(self, node): + assert node[0] == symbol.gen_iter + return node[1] + def com_dictmaker(self, nodelist): # dictmaker: test ':' test (',' test ':' value)* [','] items = [] @@ -1122,6 +1170,8 @@ class Transformer: if node[0] == token.STAR or node[0] == token.DOUBLESTAR: break kw, result = self.com_argument(node, kw) + if len_nodelist != 2 and isinstance(result, GenExpr): + raise SyntaxError, 'generator expression needs parenthesis' args.append(result) else: # No broken by star arg, so skip the last one we processed. @@ -1148,6 +1198,9 @@ class Transformer: return CallFunc(primaryNode, args, star_node, dstar_node) def com_argument(self, nodelist, kw): + if len(nodelist) == 3 and nodelist[2][0] == symbol.gen_for: + test = self.com_node(nodelist[1]) + return 0, self.com_generator_expression(test, nodelist[2]) if len(nodelist) == 2: if kw: raise SyntaxError, "non-keyword arg after keyword arg" diff --git a/Lib/symbol.py b/Lib/symbol.py index 38c6193..c839e4a 100755 --- a/Lib/symbol.py +++ b/Lib/symbol.py @@ -61,23 +61,27 @@ factor = 303 power = 304 atom = 305 listmaker = 306 -lambdef = 307 -trailer = 308 -subscriptlist = 309 -subscript = 310 -sliceop = 311 -exprlist = 312 -testlist = 313 -testlist_safe = 314 -dictmaker = 315 -classdef = 316 -arglist = 317 -argument = 318 -list_iter = 319 -list_for = 320 -list_if = 321 -testlist1 = 322 -encoding_decl = 323 +testlist_gexp = 307 +lambdef = 308 +trailer = 309 +subscriptlist = 310 +subscript = 311 +sliceop = 312 +exprlist = 313 +testlist = 314 +testlist_safe = 315 +dictmaker = 316 +classdef = 317 +arglist = 318 +argument = 319 +list_iter = 320 +list_for = 321 +list_if = 322 +gen_iter = 323 +gen_for = 324 +gen_if = 325 +testlist1 = 326 +encoding_decl = 327 #--end constants-- sym_name = {} diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py index 9b857c5..bad8857 100644 --- a/Lib/test/test_deque.py +++ b/Lib/test/test_deque.py @@ -566,7 +566,7 @@ def test_main(verbose=None): # doctests from test import test_deque -# test_support.run_doctest(test_deque, verbose) + test_support.run_doctest(test_deque, verbose) if __name__ == "__main__": test_main(verbose=True) diff --git a/Lib/test/test_genexps.py b/Lib/test/test_genexps.py new file mode 100644 index 0000000..b09fc95 --- /dev/null +++ b/Lib/test/test_genexps.py @@ -0,0 +1,258 @@ +doctests = """ + +Test simple loop with conditional + + >>> sum(i*i for i in range(100) if i&1 == 1) + 166650 + +Test simple nesting + + >>> list((i,j) for i in range(3) for j in range(4) ) + [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)] + +Test nesting with the inner expression dependent on the outer + + >>> list((i,j) for i in range(4) for j in range(i) ) + [(1, 0), (2, 0), (2, 1), (3, 0), (3, 1), (3, 2)] + +Make sure the induction variable is not exposed + + >>> i = 20 + >>> sum(i*i for i in range(100)) + 328350 + >>> i + 20 + +Test first class + + >>> g = (i*i for i in range(4)) + >>> type(g) + <type 'generator'> + >>> list(g) + [0, 1, 4, 9] + +Test direct calls to next() + + >>> g = (i*i for i in range(3)) + >>> g.next() + 0 + >>> g.next() + 1 + >>> g.next() + 4 + >>> g.next() + Traceback (most recent call last): + File "<pyshell#21>", line 1, in -toplevel- + g.next() + StopIteration + +Does it stay stopped? + + >>> g.next() + Traceback (most recent call last): + File "<pyshell#21>", line 1, in -toplevel- + g.next() + StopIteration + >>> list(g) + [] + +Test running gen when defining function is out of scope + + >>> def f(n): + ... return (i*i for i in xrange(n)) + ... + >>> list(f(10)) + [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] + + >>> def f(n): + ... return ((i,j) for i in xrange(3) for j in xrange(n)) + ... + >>> list(f(4)) + [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)] + >>> def f(n): + ... return ((i,j) for i in xrange(3) for j in xrange(4) if j in xrange(n)) + ... + >>> list(f(4)) + [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)] + >>> list(f(2)) + [(0, 0), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1)] + +#Verify that parenthesis are required in a statement +#>>> def f(n): +#... return i*i for i in xrange(n) +#... +#SyntaxError: invalid syntax + +Verify early binding for the outermost for-expression + + >>> x=10 + >>> g = (i*i for i in range(x)) + >>> x = 5 + >>> list(g) + [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] + +Verify late binding for the outermost if-expression + + >>> include = (2,4,6,8) + >>> g = (i*i for i in range(10) if i in include) + >>> include = (1,3,5,7,9) + >>> list(g) + [1, 9, 25, 49, 81] + +Verify late binding for the innermost for-expression + + >>> g = ((i,j) for i in range(3) for j in range(x)) + >>> x = 4 + >>> list(g) + [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3), (2, 0), (2, 1), (2, 2), (2, 3)] + +Verify re-use of tuples (a side benefit of using genexps over listcomps) + + >>> tupleids = map(id, ((i,i) for i in xrange(10))) + >>> max(tupleids) - min(tupleids) + 0 + + + +########### Tests borrowed from or inspired by test_generators.py ############ + +Make a generator that acts like range() + + >>> yrange = lambda n: (i for i in xrange(n)) + >>> list(yrange(10)) + [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] + +Generators always return to the most recent caller: + + >>> def creator(): + ... r = yrange(5) + ... print "creator", r.next() + ... return r + ... + >>> def caller(): + ... r = creator() + ... for i in r: + ... print "caller", i + ... + >>> caller() + creator 0 + caller 1 + caller 2 + caller 3 + caller 4 + +Generators can call other generators: + + >>> def zrange(n): + ... for i in yrange(n): + ... yield i + ... + >>> list(zrange(5)) + [0, 1, 2, 3, 4] + + +Verify that a gen exp cannot be resumed while it is actively running: + + >>> g = (me.next() for i in xrange(10)) + >>> me = g + >>> me.next() + Traceback (most recent call last): + File "<pyshell#30>", line 1, in -toplevel- + me.next() + File "<pyshell#28>", line 1, in <generator expression> + g = (me.next() for i in xrange(10)) + ValueError: generator already executing + +Verify exception propagation + + >>> g = (10 // i for i in (5, 0, 2)) + >>> g.next() + 2 + >>> g.next() + Traceback (most recent call last): + File "<pyshell#37>", line 1, in -toplevel- + g.next() + File "<pyshell#35>", line 1, in <generator expression> + g = (10 // i for i in (5, 0, 2)) + ZeroDivisionError: integer division or modulo by zero + >>> g.next() + Traceback (most recent call last): + File "<pyshell#38>", line 1, in -toplevel- + g.next() + StopIteration + +Make sure that None is a valid return value + + >>> list(None for i in xrange(10)) + [None, None, None, None, None, None, None, None, None, None] + +Check that generator attributes are present + + >>> g = (i*i for i in range(3)) + >>> expected = set(['gi_frame', 'gi_running', 'next']) + >>> set(attr for attr in dir(g) if not attr.startswith('__')) >= expected + True + + >>> print g.next.__doc__ + x.next() -> the next value, or raise StopIteration + >>> import types + >>> isinstance(g, types.GeneratorType) + True + +Check the __iter__ slot is defined to return self + + >>> iter(g) is g + True + +Verify that the running flag is set properly + + >>> g = (me.gi_running for i in (0,1)) + >>> me = g + >>> me.gi_running + 0 + >>> me.next() + 1 + >>> me.gi_running + 0 + +Verify that genexps are weakly referencable + + >>> import weakref + >>> g = (i*i for i in range(4)) + >>> wr = weakref.ref(g) + >>> wr() is g + True + >>> p = weakref.proxy(g) + >>> list(p) + [0, 1, 4, 9] + + +""" + + +__test__ = {'doctests' : doctests} + +def test_main(verbose=None): + import sys + from test import test_support + from test import test_genexps + test_support.run_doctest(test_genexps, verbose) + + # verify reference counting + if verbose and hasattr(sys, "gettotalrefcount"): + import gc + counts = [None] * 5 + for i in xrange(len(counts)): + test_support.run_doctest(test_genexps, verbose) + gc.collect() + counts[i] = sys.gettotalrefcount() + print counts + +if __name__ == "__main__": + test_main(verbose=True) + + + + + + diff --git a/Lib/test/test_grammar.py b/Lib/test/test_grammar.py index 0eed4bb..e0d5b74 100644 --- a/Lib/test/test_grammar.py +++ b/Lib/test/test_grammar.py @@ -739,3 +739,46 @@ print [ for (sp_sno, sp_pno) in suppart if sno == sp_sno and pno == sp_pno ] + +# generator expression tests +g = ([x for x in range(10)] for x in range(1)) +verify(g.next() == [x for x in range(10)]) +try: + g.next() + raise TestFailed, 'should produce StopIteration exception' +except StopIteration: + pass + +a = 1 +try: + g = (a for d in a) + g.next() + raise TestFailed, 'should produce TypeError' +except TypeError: + pass + +verify(list((x, y) for x in 'abcd' for y in 'abcd') == [(x, y) for x in 'abcd' for y in 'abcd']) +verify(list((x, y) for x in 'ab' for y in 'xy') == [(x, y) for x in 'ab' for y in 'xy']) + +a = [x for x in range(10)] +b = (x for x in (y for y in a)) +verify(sum(b) == sum([x for x in range(10)])) + +verify(sum(x**2 for x in range(10)) == sum([x**2 for x in range(10)])) +verify(sum(x*x for x in range(10) if x%2) == sum([x*x for x in range(10) if x%2])) +verify(sum(x for x in (y for y in range(10))) == sum([x for x in range(10)])) +verify(sum(x for x in (y for y in (z for z in range(10)))) == sum([x for x in range(10)])) +verify(sum(x for x in [y for y in (z for z in range(10))]) == sum([x for x in range(10)])) +verify(sum(x for x in (y for y in (z for z in range(10) if True)) if True) == sum([x for x in range(10)])) +verify(sum(x for x in (y for y in (z for z in range(10) if True) if False) if True) == 0) +check_syntax("foo(x for x in range(10), 100)") +check_syntax("foo(100, x for x in range(10))") + +# test for outmost iterable precomputation +x = 10; g = (i for i in range(x)); x = 5 +verify(len(list(g)) == 10) + +# This should hold, since we're only precomputing outmost iterable. +x = 10; t = False; g = ((i,j) for i in range(x) if t for j in range(x)) +x = 5; t = True; +verify([(i,j) for i in range(10) for j in range(5)] == list(g)) diff --git a/Lib/test/test_parser.py b/Lib/test/test_parser.py index 7860e7b..9652f6b 100644 --- a/Lib/test/test_parser.py +++ b/Lib/test/test_parser.py @@ -67,6 +67,8 @@ class RoundtripLegalSyntaxTestCase(unittest.TestCase): self.check_expr("lambda foo=bar, blaz=blat+2, **z: 0") self.check_expr("lambda foo=bar, blaz=blat+2, *y, **z: 0") self.check_expr("lambda x, *y, **z: 0") + self.check_expr("(x for x in range(10))") + self.check_expr("foo(x for x in range(10))") def test_print(self): self.check_suite("print") |