Debian Codegraph @

Lib/test/test_generators.py

raw
1 import copy
2 import gc
3 import pickle
4 import sys
5 import doctest
6 import unittest
7 import weakref
8 import inspect
9 import textwrap
10 import types
11
12 from test import support
13
14 try:
15 import _testcapi
16 except ImportError:
17 _testcapi = None
18
19
20 # This tests to make sure that if a SIGINT arrives just before we send into a
21 # yield from chain, the KeyboardInterrupt is raised in the innermost
22 # generator (see bpo-30039).
23 @unittest.skipUnless(_testcapi is not None and
24 hasattr(_testcapi, "raise_SIGINT_then_send_None"),
25 "needs _testcapi.raise_SIGINT_then_send_None")
26 class SignalAndYieldFromTest(unittest.TestCase):
27
28 def generator1(self):
29 return (yield from self.generator2())
30
31 def generator2(self):
32 try:
33 yield
34 except KeyboardInterrupt:
35 return "PASSED"
36 else:
37 return "FAILED"
38
39 def test_raise_and_yield_from(self):
40 gen = self.generator1()
41 gen.send(None)
42 try:
43 _testcapi.raise_SIGINT_then_send_None(gen)
44 except BaseException as _exc:
45 exc = _exc
46 self.assertIs(type(exc), StopIteration)
47 self.assertEqual(exc.value, "PASSED")
48
49
50 class FinalizationTest(unittest.TestCase):
51
52 def test_frame_resurrect(self):
53 # A generator frame can be resurrected by a generator's finalization.
54 def gen():
55 nonlocal frame
56 try:
57 yield
58 finally:
59 frame = sys._getframe()
60
61 g = gen()
62 wr = weakref.ref(g)
63 next(g)
64 del g
65 support.gc_collect()
66 self.assertIs(wr(), None)
67 self.assertTrue(frame)
68 del frame
69 support.gc_collect()
70
71 def test_refcycle(self):
72 # A generator caught in a refcycle gets finalized anyway.
73 old_garbage = gc.garbage[:]
74 finalized = False
75 def gen():
76 nonlocal finalized
77 try:
78 g = yield
79 yield 1
80 finally:
81 finalized = True
82
83 g = gen()
84 next(g)
85 g.send(g)
86 self.assertGreaterEqual(sys.getrefcount(g), 2)
87 self.assertFalse(finalized)
88 del g
89 support.gc_collect()
90 self.assertTrue(finalized)
91 self.assertEqual(gc.garbage, old_garbage)
92
93 def test_lambda_generator(self):
94 # bpo-23192, gh-119897: Test that a lambda returning a generator behaves
95 # like the equivalent function
96 f = lambda: (yield 1)
97 self.assertIsInstance(f(), types.GeneratorType)
98 self.assertEqual(next(f()), 1)
99
100 def g(): return (yield 1)
101
102 # test 'yield from'
103 f2 = lambda: (yield from g())
104 def g2(): return (yield from g())
105
106 f3 = lambda: (yield from f())
107 def g3(): return (yield from f())
108
109 for gen_fun in (f, g, f2, g2, f3, g3):
110 gen = gen_fun()
111 self.assertEqual(next(gen), 1)
112 with self.assertRaises(StopIteration) as cm:
113 gen.send(2)
114 self.assertEqual(cm.exception.value, 2)
115
116 def test_generator_resurrect(self):
117 # Test that a resurrected generator still has a valid gi_code
118 resurrected = []
119
120 # Resurrect a generator in a finalizer
121 exec(textwrap.dedent("""
122 def gen():
123 try:
124 yield
125 except:
126 resurrected.append(g)
127
128 g = gen()
129 next(g)
130 """), {"resurrected": resurrected})
131
132 support.gc_collect()
133
134 self.assertEqual(len(resurrected), 1)
135 self.assertIsInstance(resurrected[0].gi_code, types.CodeType)
136
137 def test_exhausted_generator_frame_cycle(self):
138 def g():
139 yield
140
141 generator = g()
142 frame = generator.gi_frame
143 self.assertIsNone(frame.f_back)
144 next(generator)
145 self.assertIsNone(frame.f_back)
146 next(generator, None)
147 self.assertIsNone(frame.f_back)
148
149
150 class GeneratorTest(unittest.TestCase):
151
152 def test_name(self):
153 def func():
154 yield 1
155
156 # check generator names
157 gen = func()
158 self.assertEqual(gen.__name__, "func")
159 self.assertEqual(gen.__qualname__,
160 "GeneratorTest.test_name.<locals>.func")
161
162 # modify generator names
163 gen.__name__ = "name"
164 gen.__qualname__ = "qualname"
165 self.assertEqual(gen.__name__, "name")
166 self.assertEqual(gen.__qualname__, "qualname")
167
168 # generator names must be a string and cannot be deleted
169 self.assertRaises(TypeError, setattr, gen, '__name__', 123)
170 self.assertRaises(TypeError, setattr, gen, '__qualname__', 123)
171 self.assertRaises(TypeError, delattr, gen, '__name__')
172 self.assertRaises(TypeError, delattr, gen, '__qualname__')
173
174 # modify names of the function creating the generator
175 func.__qualname__ = "func_qualname"
176 func.__name__ = "func_name"
177 gen = func()
178 self.assertEqual(gen.__name__, "func_name")
179 self.assertEqual(gen.__qualname__, "func_qualname")
180
181 # unnamed generator
182 gen = (x for x in range(10))
183 self.assertEqual(gen.__name__,
184 "<genexpr>")
185 self.assertEqual(gen.__qualname__,
186 "GeneratorTest.test_name.<locals>.<genexpr>")
187
188 def test_copy(self):
189 def f():
190 yield 1
191 g = f()
192 with self.assertRaises(TypeError):
193 copy.copy(g)
194
195 def test_pickle(self):
196 def f():
197 yield 1
198 g = f()
199 for proto in range(pickle.HIGHEST_PROTOCOL + 1):
200 with self.assertRaises((TypeError, pickle.PicklingError)):
201 pickle.dumps(g, proto)
202
203 def test_send_non_none_to_new_gen(self):
204 def f():
205 yield 1
206 g = f()
207 with self.assertRaises(TypeError):
208 g.send(0)
209 self.assertEqual(next(g), 1)
210
211 def test_handle_frame_object_in_creation(self):
212
213 #Attempt to expose partially constructed frames
214 #See https://github.com/python/cpython/issues/94262
215
216 def cb(*args):
217 inspect.stack()
218
219 def gen():
220 yield 1
221
222 thresholds = gc.get_threshold()
223
224 gc.callbacks.append(cb)
225 gc.set_threshold(1, 0, 0)
226 try:
227 gen()
228 finally:
229 gc.set_threshold(*thresholds)
230 gc.callbacks.pop()
231
232 class Sneaky:
233 def __del__(self):
234 inspect.stack()
235
236 sneaky = Sneaky()
237 sneaky._s = Sneaky()
238 sneaky._s._s = sneaky
239
240 gc.set_threshold(1, 0, 0)
241 try:
242 del sneaky
243 gen()
244 finally:
245 gc.set_threshold(*thresholds)
246
247 def test_ag_frame_f_back(self):
248 async def f():
249 yield
250 ag = f()
251 self.assertIsNone(ag.ag_frame.f_back)
252
253 def test_cr_frame_f_back(self):
254 async def f():
255 pass
256 cr = f()
257 self.assertIsNone(cr.cr_frame.f_back)
258 cr.close() # Suppress RuntimeWarning.
259
260 def test_gi_frame_f_back(self):
261 def f():
262 yield
263 gi = f()
264 self.assertIsNone(gi.gi_frame.f_back)
265
266 def test_issue103488(self):
267
268 def gen_raises():
269 yield
270 raise ValueError()
271
272 def loop():
273 try:
274 for _ in gen_raises():
275 if True is False:
276 return
277 except ValueError:
278 pass
279
280 #This should not raise
281 loop()
282
283 def test_genexpr_only_calls_dunder_iter_once(self):
284
285 class Iterator:
286
287 def __init__(self):
288 self.val = 0
289
290 def __next__(self):
291 if self.val == 2:
292 raise StopIteration
293 self.val += 1
294 return self.val
295
296 # No __iter__ method
297
298 class C:
299
300 def __iter__(self):
301 return Iterator()
302
303 self.assertEqual([1, 2], list(i for i in C()))
304
305 def test_close_clears_frame(self):
306 # gh-142766: Test that closing a generator clears its frame
307 class DetectDelete:
308 def __init__(self):
309 DetectDelete.deleted = False
310
311 def __del__(self):
312 DetectDelete.deleted = True
313
314 def generator(arg):
315 yield
316
317 # Test a freshly created generator (not suspended)
318 g = generator(DetectDelete())
319 g.close()
320 self.assertTrue(DetectDelete.deleted)
321
322 # Test a suspended generator
323 g = generator(DetectDelete())
324 next(g)
325 g.close()
326 self.assertTrue(DetectDelete.deleted)
327
328 # Clear via gi_frame.clear()
329 g = generator(DetectDelete())
330 g.gi_frame.clear()
331 self.assertTrue(DetectDelete.deleted)
332
333 class ModifyUnderlyingIterableTest(unittest.TestCase):
334 iterables = [
335 range(0),
336 range(20),
337 [1, 2, 3],
338 (2,),
339 {13, 48, 211},
340 frozenset((15, 8, 6)),
341 {1: 2, 3: 4},
342 ]
343
344 non_iterables = [
345 None,
346 42,
347 3.0,
348 2j,
349 ]
350
351 def genexpr(self):
352 return (x for x in range(10))
353
354 def genfunc(self):
355 def gen(it):
356 for x in it:
357 yield x
358 return gen(range(10))
359
360 def process_tests(self, get_generator, is_expr):
361 err_iterator = "'.*' object is not an iterator"
362 err_iterable = "'.*' object is not iterable"
363 for obj in self.iterables:
364 g_obj = get_generator(obj)
365 with self.subTest(g_obj=g_obj, obj=obj):
366 if is_expr:
367 self.assertRaisesRegex(TypeError, err_iterator, list, g_obj)
368 else:
369 self.assertListEqual(list(g_obj), list(obj))
370
371 g_iter = get_generator(iter(obj))
372 with self.subTest(g_iter=g_iter, obj=obj):
373 self.assertListEqual(list(g_iter), list(obj))
374
375 for obj in self.non_iterables:
376 g_obj = get_generator(obj)
377 with self.subTest(g_obj=g_obj):
378 err = err_iterator if is_expr else err_iterable
379 self.assertRaisesRegex(TypeError, err, list, g_obj)
380
381 def test_modify_f_locals(self):
382 def modify_f_locals(g, local, obj):
383 g.gi_frame.f_locals[local] = obj
384 return g
385
386 def get_generator_genexpr(obj):
387 return modify_f_locals(self.genexpr(), '.0', obj)
388
389 def get_generator_genfunc(obj):
390 return modify_f_locals(self.genfunc(), 'it', obj)
391
392 self.process_tests(get_generator_genexpr, True)
393 self.process_tests(get_generator_genfunc, False)
394
395 def test_new_gen_from_gi_code(self):
396 def new_gen_from_gi_code(g, obj):
397 generator_func = types.FunctionType(g.gi_code, {})
398 return generator_func(obj)
399
400 def get_generator_genexpr(obj):
401 return new_gen_from_gi_code(self.genexpr(), obj)
402
403 def get_generator_genfunc(obj):
404 return new_gen_from_gi_code(self.genfunc(), obj)
405
406 self.process_tests(get_generator_genexpr, True)
407 self.process_tests(get_generator_genfunc, False)
408
409
410 class ExceptionTest(unittest.TestCase):
411 # Tests for the issue #23353: check that the currently handled exception
412 # is correctly saved/restored in PyEval_EvalFrameEx().
413
414 def test_except_throw(self):
415 def store_raise_exc_generator():
416 try:
417 self.assertIsNone(sys.exception())
418 yield
419 except Exception as exc:
420 # exception raised by gen.throw(exc)
421 self.assertIsInstance(sys.exception(), ValueError)
422 self.assertIsNone(exc.__context__)
423 yield
424
425 # ensure that the exception is not lost
426 self.assertIsInstance(sys.exception(), ValueError)
427 yield
428
429 # we should be able to raise back the ValueError
430 raise
431
432 make = store_raise_exc_generator()
433 next(make)
434
435 try:
436 raise ValueError()
437 except Exception as exc:
438 try:
439 make.throw(exc)
440 except Exception:
441 pass
442
443 next(make)
444 with self.assertRaises(ValueError) as cm:
445 next(make)
446 self.assertIsNone(cm.exception.__context__)
447
448 self.assertIsNone(sys.exception())
449
450 def test_except_next(self):
451 def gen():
452 self.assertIsInstance(sys.exception(), ValueError)
453 yield "done"
454
455 g = gen()
456 try:
457 raise ValueError
458 except Exception:
459 self.assertEqual(next(g), "done")
460 self.assertIsNone(sys.exception())
461
462 def test_except_gen_except(self):
463 def gen():
464 try:
465 self.assertIsNone(sys.exception())
466 yield
467 # we are called from "except ValueError:", TypeError must
468 # inherit ValueError in its context
469 raise TypeError()
470 except TypeError as exc:
471 self.assertIsInstance(sys.exception(), TypeError)
472 self.assertEqual(type(exc.__context__), ValueError)
473 # here we are still called from the "except ValueError:"
474 self.assertIsInstance(sys.exception(), ValueError)
475 yield
476 self.assertIsNone(sys.exception())
477 yield "done"
478
479 g = gen()
480 next(g)
481 try:
482 raise ValueError
483 except Exception:
484 next(g)
485
486 self.assertEqual(next(g), "done")
487 self.assertIsNone(sys.exception())
488
489 def test_nested_gen_except_loop(self):
490 def gen():
491 for i in range(100):
492 self.assertIsInstance(sys.exception(), TypeError)
493 yield "doing"
494
495 def outer():
496 try:
497 raise TypeError
498 except:
499 for x in gen():
500 yield x
501
502 try:
503 raise ValueError
504 except Exception:
505 for x in outer():
506 self.assertEqual(x, "doing")
507 self.assertEqual(sys.exception(), None)
508
509 def test_except_throw_exception_context(self):
510 def gen():
511 try:
512 try:
513 self.assertIsNone(sys.exception())
514 yield
515 except ValueError:
516 # we are called from "except ValueError:"
517 self.assertIsInstance(sys.exception(), ValueError)
518 raise TypeError()
519 except Exception as exc:
520 self.assertIsInstance(sys.exception(), TypeError)
521 self.assertEqual(type(exc.__context__), ValueError)
522 # we are still called from "except ValueError:"
523 self.assertIsInstance(sys.exception(), ValueError)
524 yield
525 self.assertIsNone(sys.exception())
526 yield "done"
527
528 g = gen()
529 next(g)
530 try:
531 raise ValueError
532 except Exception as exc:
533 g.throw(exc)
534
535 self.assertEqual(next(g), "done")
536 self.assertIsNone(sys.exception())
537
538 def test_except_throw_bad_exception(self):
539 class E(Exception):
540 def __new__(cls, *args, **kwargs):
541 return cls
542
543 def boring_generator():
544 yield
545
546 gen = boring_generator()
547
548 err_msg = 'should have returned an instance of BaseException'
549
550 with self.assertRaisesRegex(TypeError, err_msg):
551 gen.throw(E)
552
553 self.assertRaises(StopIteration, next, gen)
554
555 def generator():
556 with self.assertRaisesRegex(TypeError, err_msg):
557 yield
558
559 gen = generator()
560 next(gen)
561 with self.assertRaises(StopIteration):
562 gen.throw(E)
563
564 def test_gen_3_arg_deprecation_warning(self):
565 def g():
566 yield 42
567
568 gen = g()
569 with self.assertWarns(DeprecationWarning):
570 with self.assertRaises(TypeError):
571 gen.throw(TypeError, TypeError(24), None)
572
573 def test_stopiteration_error(self):
574 # See also PEP 479.
575
576 def gen():
577 raise StopIteration
578 yield
579
580 with self.assertRaisesRegex(RuntimeError, 'raised StopIteration'):
581 next(gen())
582
583 def test_tutorial_stopiteration(self):
584 # Raise StopIteration" stops the generator too:
585
586 def f():
587 yield 1
588 raise StopIteration
589 yield 2 # never reached
590
591 g = f()
592 self.assertEqual(next(g), 1)
593
594 with self.assertRaisesRegex(RuntimeError, 'raised StopIteration'):
595 next(g)
596
597 def test_return_tuple(self):
598 def g():
599 return (yield 1)
600
601 gen = g()
602 self.assertEqual(next(gen), 1)
603 with self.assertRaises(StopIteration) as cm:
604 gen.send((2,))
605 self.assertEqual(cm.exception.value, (2,))
606
607 def test_return_stopiteration(self):
608 def g():
609 return (yield 1)
610
611 gen = g()
612 self.assertEqual(next(gen), 1)
613 with self.assertRaises(StopIteration) as cm:
614 gen.send(StopIteration(2))
615 self.assertIsInstance(cm.exception.value, StopIteration)
616 self.assertEqual(cm.exception.value.value, 2)
617
618
619 class GeneratorCloseTest(unittest.TestCase):
620
621 def test_close_no_return_value(self):
622 def f():
623 yield
624
625 gen = f()
626 gen.send(None)
627 self.assertIsNone(gen.close())
628
629 def test_close_return_value(self):
630 def f():
631 try:
632 yield
633 # close() raises GeneratorExit here, which is caught
634 except GeneratorExit:
635 return 0
636
637 gen = f()
638 gen.send(None)
639 self.assertEqual(gen.close(), 0)
640
641 def test_close_not_catching_exit(self):
642 def f():
643 yield
644 # close() raises GeneratorExit here, which isn't caught and
645 # therefore propagates -- no return value
646 return 0
647
648 gen = f()
649 gen.send(None)
650 self.assertIsNone(gen.close())
651
652 def test_close_not_started(self):
653 def f():
654 try:
655 yield
656 except GeneratorExit:
657 return 0
658
659 gen = f()
660 self.assertIsNone(gen.close())
661
662 def test_close_exhausted(self):
663 def f():
664 try:
665 yield
666 except GeneratorExit:
667 return 0
668
669 gen = f()
670 next(gen)
671 with self.assertRaises(StopIteration):
672 next(gen)
673 self.assertIsNone(gen.close())
674
675 def test_close_closed(self):
676 def f():
677 try:
678 yield
679 except GeneratorExit:
680 return 0
681
682 gen = f()
683 gen.send(None)
684 self.assertEqual(gen.close(), 0)
685 self.assertIsNone(gen.close())
686
687 def test_close_raises(self):
688 def f():
689 try:
690 yield
691 except GeneratorExit:
692 pass
693 raise RuntimeError
694
695 gen = f()
696 gen.send(None)
697 with self.assertRaises(RuntimeError):
698 gen.close()
699
700 def test_close_releases_frame_locals(self):
701 # See gh-118272
702
703 class Foo:
704 pass
705
706 f = Foo()
707 f_wr = weakref.ref(f)
708
709 def genfn():
710 a = f
711 yield
712
713 g = genfn()
714 next(g)
715 del f
716 g.close()
717 support.gc_collect()
718 self.assertIsNone(f_wr())
719
720
721 # See https://github.com/python/cpython/issues/125723
722 class GeneratorDeallocTest(unittest.TestCase):
723 def test_frame_outlives_generator(self):
724 def g1():
725 a = 42
726 yield sys._getframe()
727
728 def g2():
729 a = 42
730 yield
731
732 def g3(obj):
733 a = 42
734 obj.frame = sys._getframe()
735 yield
736
737 class ObjectWithFrame():
738 def __init__(self):
739 self.frame = None
740
741 def get_frame(index):
742 if index == 1:
743 return next(g1())
744 elif index == 2:
745 gen = g2()
746 next(gen)
747 return gen.gi_frame
748 elif index == 3:
749 obj = ObjectWithFrame()
750 next(g3(obj))
751 return obj.frame
752 else:
753 return None
754
755 for index in (1, 2, 3):
756 with self.subTest(index=index):
757 frame = get_frame(index)
758 frame_locals = frame.f_locals
759 self.assertIn('a', frame_locals)
760 self.assertEqual(frame_locals['a'], 42)
761
762 def test_frame_locals_outlive_generator(self):
763 frame_locals1 = None
764
765 def g1():
766 nonlocal frame_locals1
767 frame_locals1 = sys._getframe().f_locals
768 a = 42
769 yield
770
771 def g2():
772 a = 42
773 yield sys._getframe().f_locals
774
775 def get_frame_locals(index):
776 if index == 1:
777 nonlocal frame_locals1
778 next(g1())
779 return frame_locals1
780 if index == 2:
781 return next(g2())
782 else:
783 return None
784
785 for index in (1, 2):
786 with self.subTest(index=index):
787 frame_locals = get_frame_locals(index)
788 self.assertIn('a', frame_locals)
789 self.assertEqual(frame_locals['a'], 42)
790
791 def test_frame_locals_outlive_generator_with_exec(self):
792 def g():
793 a = 42
794 yield locals(), sys._getframe().f_locals
795
796 locals_ = {'g': g}
797 for i in range(10):
798 exec("snapshot, live_locals = next(g())", locals=locals_)
799 for l in (locals_['snapshot'], locals_['live_locals']):
800 self.assertIn('a', l)
801 self.assertEqual(l['a'], 42)
802
803
804 class GeneratorThrowTest(unittest.TestCase):
805
806 def test_exception_context_with_yield(self):
807 def f():
808 try:
809 raise KeyError('a')
810 except Exception:
811 yield
812
813 gen = f()
814 gen.send(None)
815 with self.assertRaises(ValueError) as cm:
816 gen.throw(ValueError)
817 context = cm.exception.__context__
818 self.assertEqual((type(context), context.args), (KeyError, ('a',)))
819
820 def test_exception_context_with_yield_inside_generator(self):
821 # Check that the context is also available from inside the generator
822 # with yield, as opposed to outside.
823 def f():
824 try:
825 raise KeyError('a')
826 except Exception:
827 try:
828 yield
829 except Exception as exc:
830 self.assertEqual(type(exc), ValueError)
831 context = exc.__context__
832 self.assertEqual((type(context), context.args),
833 (KeyError, ('a',)))
834 yield 'b'
835
836 gen = f()
837 gen.send(None)
838 actual = gen.throw(ValueError)
839 # This ensures that the assertions inside were executed.
840 self.assertEqual(actual, 'b')
841
842 def test_exception_context_with_yield_from(self):
843 def f():
844 yield
845
846 def g():
847 try:
848 raise KeyError('a')
849 except Exception:
850 yield from f()
851
852 gen = g()
853 gen.send(None)
854 with self.assertRaises(ValueError) as cm:
855 gen.throw(ValueError)
856 context = cm.exception.__context__
857 self.assertEqual((type(context), context.args), (KeyError, ('a',)))
858
859 def test_exception_context_with_yield_from_with_context_cycle(self):
860 # Check trying to create an exception context cycle:
861 # https://bugs.python.org/issue40696
862 has_cycle = None
863
864 def f():
865 yield
866
867 def g(exc):
868 nonlocal has_cycle
869 try:
870 raise exc
871 except Exception:
872 try:
873 yield from f()
874 except Exception as exc:
875 has_cycle = (exc is exc.__context__)
876 yield
877
878 exc = KeyError('a')
879 gen = g(exc)
880 gen.send(None)
881 gen.throw(exc)
882 # This also distinguishes from the initial has_cycle=None.
883 self.assertEqual(has_cycle, False)
884
885 def test_throw_after_none_exc_type(self):
886 def g():
887 try:
888 raise KeyError
889 except KeyError:
890 pass
891
892 try:
893 yield
894 except Exception:
895 raise RuntimeError
896
897 gen = g()
898 gen.send(None)
899 with self.assertRaises(RuntimeError) as cm:
900 gen.throw(ValueError)
901
902
903 class GeneratorStackTraceTest(unittest.TestCase):
904
905 def check_stack_names(self, frame, expected):
906 names = []
907 while frame:
908 name = frame.f_code.co_name
909 # Stop checking frames when we get to our test helper.
910 if (name.startswith('check_') or name.startswith('call_')
911 or name.startswith('test')):
912 break
913
914 names.append(name)
915 frame = frame.f_back
916
917 self.assertEqual(names, expected)
918
919 def check_yield_from_example(self, call_method):
920 def f():
921 self.check_stack_names(sys._getframe(), ['f', 'g'])
922 try:
923 yield
924 except Exception:
925 pass
926 self.check_stack_names(sys._getframe(), ['f', 'g'])
927
928 def g():
929 self.check_stack_names(sys._getframe(), ['g'])
930 yield from f()
931 self.check_stack_names(sys._getframe(), ['g'])
932
933 gen = g()
934 gen.send(None)
935 try:
936 call_method(gen)
937 except StopIteration:
938 pass
939
940 def test_send_with_yield_from(self):
941 def call_send(gen):
942 gen.send(None)
943
944 self.check_yield_from_example(call_send)
945
946 def test_throw_with_yield_from(self):
947 def call_throw(gen):
948 gen.throw(RuntimeError)
949
950 self.check_yield_from_example(call_throw)
951
952 def test_throw_with_yield_from_custom_generator(self):
953
954 class CustomGen:
955 def __init__(self, test):
956 self.test = test
957 def throw(self, *args):
958 self.test.check_stack_names(sys._getframe(), ['throw', 'g'])
959 def __iter__(self):
960 return self
961 def __next__(self):
962 return 42
963
964 def g(target):
965 yield from target
966
967 gen = g(CustomGen(self))
968 gen.send(None)
969 gen.throw(RuntimeError)
970
971
972 class YieldFromTests(unittest.TestCase):
973 def test_generator_gi_yieldfrom(self):
974 def a():
975 self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_RUNNING)
976 self.assertIsNone(gen_b.gi_yieldfrom)
977 yield
978 self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_RUNNING)
979 self.assertIsNone(gen_b.gi_yieldfrom)
980
981 def b():
982 self.assertIsNone(gen_b.gi_yieldfrom)
983 yield from a()
984 self.assertIsNone(gen_b.gi_yieldfrom)
985 yield
986 self.assertIsNone(gen_b.gi_yieldfrom)
987
988 gen_b = b()
989 self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_CREATED)
990 self.assertIsNone(gen_b.gi_yieldfrom)
991
992 gen_b.send(None)
993 self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_SUSPENDED)
994 self.assertEqual(gen_b.gi_yieldfrom.gi_code.co_name, 'a')
995
996 gen_b.send(None)
997 self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_SUSPENDED)
998 self.assertIsNone(gen_b.gi_yieldfrom)
999
1000 [] = gen_b # Exhaust generator
1001 self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_CLOSED)
1002 self.assertIsNone(gen_b.gi_yieldfrom)
1003
1004
1005 tutorial_tests = """
1006 Let's try a simple generator:
1007
1008 >>> def f():
1009 ... yield 1
1010 ... yield 2
1011
1012 >>> for i in f():
1013 ... print(i)
1014 1
1015 2
1016 >>> g = f()
1017 >>> next(g)
1018 1
1019 >>> next(g)
1020 2
1021
1022 "Falling off the end" stops the generator:
1023
1024 >>> next(g)
1025 Traceback (most recent call last):
1026 File "<stdin>", line 1, in ?
1027 File "<stdin>", line 2, in g
1028 StopIteration
1029
1030 "return" also stops the generator:
1031
1032 >>> def f():
1033 ... yield 1
1034 ... return
1035 ... yield 2 # never reached
1036 ...
1037 >>> g = f()
1038 >>> next(g)
1039 1
1040 >>> next(g)
1041 Traceback (most recent call last):
1042 File "<stdin>", line 1, in ?
1043 File "<stdin>", line 3, in f
1044 StopIteration
1045 >>> next(g) # once stopped, can't be resumed
1046 Traceback (most recent call last):
1047 File "<stdin>", line 1, in ?
1048 StopIteration
1049
1050 However, "return" and StopIteration are not exactly equivalent:
1051
1052 >>> def g1():
1053 ... try:
1054 ... return
1055 ... except:
1056 ... yield 1
1057 ...
1058 >>> list(g1())
1059 []
1060
1061 >>> def g2():
1062 ... try:
1063 ... raise StopIteration
1064 ... except:
1065 ... yield 42
1066 >>> print(list(g2()))
1067 [42]
1068
1069 This may be surprising at first:
1070
1071 >>> def g3():
1072 ... try:
1073 ... return
1074 ... finally:
1075 ... yield 1
1076 ...
1077 >>> list(g3())
1078 [1]
1079
1080 Let's create an alternate range() function implemented as a generator:
1081
1082 >>> def yrange(n):
1083 ... for i in range(n):
1084 ... yield i
1085 ...
1086 >>> list(yrange(5))
1087 [0, 1, 2, 3, 4]
1088
1089 Generators always return to the most recent caller:
1090
1091 >>> def creator():
1092 ... r = yrange(5)
1093 ... print("creator", next(r))
1094 ... return r
1095 ...
1096 >>> def caller():
1097 ... r = creator()
1098 ... for i in r:
1099 ... print("caller", i)
1100 ...
1101 >>> caller()
1102 creator 0
1103 caller 1
1104 caller 2
1105 caller 3
1106 caller 4
1107
1108 Generators can call other generators:
1109
1110 >>> def zrange(n):
1111 ... for i in yrange(n):
1112 ... yield i
1113 ...
1114 >>> list(zrange(5))
1115 [0, 1, 2, 3, 4]
1116
1117 """
1118
1119 # The examples from PEP 255.
1120
1121 pep_tests = """
1122
1123 Specification: Yield
1124
1125 Restriction: A generator cannot be resumed while it is actively
1126 running:
1127
1128 >>> def g():
1129 ... i = next(me)
1130 ... yield i
1131 >>> me = g()
1132 >>> next(me)
1133 Traceback (most recent call last):
1134 ...
1135 File "<string>", line 2, in g
1136 ValueError: generator already executing
1137
1138 Specification: Return
1139
1140 Note that return isn't always equivalent to raising StopIteration: the
1141 difference lies in how enclosing try/except constructs are treated.
1142 For example,
1143
1144 >>> def f1():
1145 ... try:
1146 ... return
1147 ... except:
1148 ... yield 1
1149 >>> print(list(f1()))
1150 []
1151
1152 because, as in any function, return simply exits, but
1153
1154 >>> def f2():
1155 ... try:
1156 ... raise StopIteration
1157 ... except:
1158 ... yield 42
1159 >>> print(list(f2()))
1160 [42]
1161
1162 because StopIteration is captured by a bare "except", as is any
1163 exception.
1164
1165 Specification: Generators and Exception Propagation
1166
1167 >>> def f():
1168 ... return 1//0
1169 >>> def g():
1170 ... yield f() # the zero division exception propagates
1171 ... yield 42 # and we'll never get here
1172 >>> k = g()
1173 >>> next(k)
1174 Traceback (most recent call last):
1175 File "<stdin>", line 1, in ?
1176 File "<stdin>", line 2, in g
1177 File "<stdin>", line 2, in f
1178 ZeroDivisionError: division by zero
1179 >>> next(k) # and the generator cannot be resumed
1180 Traceback (most recent call last):
1181 File "<stdin>", line 1, in ?
1182 StopIteration
1183 >>>
1184
1185 Specification: Try/Except/Finally
1186
1187 >>> def f():
1188 ... try:
1189 ... yield 1
1190 ... try:
1191 ... yield 2
1192 ... 1//0
1193 ... yield 3 # never get here
1194 ... except ZeroDivisionError:
1195 ... yield 4
1196 ... yield 5
1197 ... raise
1198 ... except:
1199 ... yield 6
1200 ... yield 7 # the "raise" above stops this
1201 ... except:
1202 ... yield 8
1203 ... yield 9
1204 ... try:
1205 ... x = 12
1206 ... finally:
1207 ... yield 10
1208 ... yield 11
1209 >>> print(list(f()))
1210 [1, 2, 4, 5, 8, 9, 10, 11]
1211 >>>
1212
1213 Guido's binary tree example.
1214
1215 >>> # A binary tree class.
1216 >>> class Tree:
1217 ...
1218 ... def __init__(self, label, left=None, right=None):
1219 ... self.label = label
1220 ... self.left = left
1221 ... self.right = right
1222 ...
1223 ... def __repr__(self, level=0, indent=" "):
1224 ... s = level*indent + repr(self.label)
1225 ... if self.left:
1226 ... s = s + "\\n" + self.left.__repr__(level+1, indent)
1227 ... if self.right:
1228 ... s = s + "\\n" + self.right.__repr__(level+1, indent)
1229 ... return s
1230 ...
1231 ... def __iter__(self):
1232 ... return inorder(self)
1233
1234 >>> # Create a Tree from a list.
1235 >>> def tree(list):
1236 ... n = len(list)
1237 ... if n == 0:
1238 ... return []
1239 ... i = n // 2
1240 ... return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
1241
1242 >>> # Show it off: create a tree.
1243 >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
1244
1245 >>> # A recursive generator that generates Tree labels in in-order.
1246 >>> def inorder(t):
1247 ... if t:
1248 ... for x in inorder(t.left):
1249 ... yield x
1250 ... yield t.label
1251 ... for x in inorder(t.right):
1252 ... yield x
1253
1254 >>> # Show it off: create a tree.
1255 >>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
1256 >>> # Print the nodes of the tree in in-order.
1257 >>> for x in t:
1258 ... print(' '+x, end='')
1259 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1260
1261 >>> # A non-recursive generator.
1262 >>> def inorder(node):
1263 ... stack = []
1264 ... while node:
1265 ... while node.left:
1266 ... stack.append(node)
1267 ... node = node.left
1268 ... yield node.label
1269 ... while not node.right:
1270 ... try:
1271 ... node = stack.pop()
1272 ... except IndexError:
1273 ... return
1274 ... yield node.label
1275 ... node = node.right
1276
1277 >>> # Exercise the non-recursive generator.
1278 >>> for x in t:
1279 ... print(' '+x, end='')
1280 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1281
1282 """
1283
1284 # Examples from Iterator-List and Python-Dev and c.l.py.
1285
1286 email_tests = """
1287
1288 The difference between yielding None and returning it.
1289
1290 >>> def g():
1291 ... for i in range(3):
1292 ... yield None
1293 ... yield None
1294 ... return
1295 >>> list(g())
1296 [None, None, None, None]
1297
1298 Ensure that explicitly raising StopIteration acts like any other exception
1299 in try/except, not like a return.
1300
1301 >>> def g():
1302 ... yield 1
1303 ... try:
1304 ... raise StopIteration
1305 ... except:
1306 ... yield 2
1307 ... yield 3
1308 >>> list(g())
1309 [1, 2, 3]
1310
1311 Next one was posted to c.l.py.
1312
1313 >>> def gcomb(x, k):
1314 ... "Generate all combinations of k elements from list x."
1315 ...
1316 ... if k > len(x):
1317 ... return
1318 ... if k == 0:
1319 ... yield []
1320 ... else:
1321 ... first, rest = x[0], x[1:]
1322 ... # A combination does or doesn't contain first.
1323 ... # If it does, the remainder is a k-1 comb of rest.
1324 ... for c in gcomb(rest, k-1):
1325 ... c.insert(0, first)
1326 ... yield c
1327 ... # If it doesn't contain first, it's a k comb of rest.
1328 ... for c in gcomb(rest, k):
1329 ... yield c
1330
1331 >>> seq = list(range(1, 5))
1332 >>> for k in range(len(seq) + 2):
1333 ... print("%d-combs of %s:" % (k, seq))
1334 ... for c in gcomb(seq, k):
1335 ... print(" ", c)
1336 0-combs of [1, 2, 3, 4]:
1337 []
1338 1-combs of [1, 2, 3, 4]:
1339 [1]
1340 [2]
1341 [3]
1342 [4]
1343 2-combs of [1, 2, 3, 4]:
1344 [1, 2]
1345 [1, 3]
1346 [1, 4]
1347 [2, 3]
1348 [2, 4]
1349 [3, 4]
1350 3-combs of [1, 2, 3, 4]:
1351 [1, 2, 3]
1352 [1, 2, 4]
1353 [1, 3, 4]
1354 [2, 3, 4]
1355 4-combs of [1, 2, 3, 4]:
1356 [1, 2, 3, 4]
1357 5-combs of [1, 2, 3, 4]:
1358
1359 From the Iterators list, about the types of these things.
1360
1361 >>> def g():
1362 ... yield 1
1363 ...
1364 >>> type(g)
1365 <class 'function'>
1366 >>> i = g()
1367 >>> type(i)
1368 <class 'generator'>
1369 >>> [s for s in dir(i) if not s.startswith('_')]
1370 ['close', 'gi_code', 'gi_frame', 'gi_running', 'gi_suspended', 'gi_yieldfrom', 'send', 'throw']
1371 >>> from test.support import HAVE_DOCSTRINGS
1372 >>> print(i.__next__.__doc__ if HAVE_DOCSTRINGS else 'Implement next(self).')
1373 Implement next(self).
1374 >>> iter(i) is i
1375 True
1376 >>> import types
1377 >>> isinstance(i, types.GeneratorType)
1378 True
1379
1380 And more, added later.
1381
1382 >>> i.gi_running
1383 0
1384 >>> type(i.gi_frame)
1385 <class 'frame'>
1386 >>> i.gi_running = 42
1387 Traceback (most recent call last):
1388 ...
1389 AttributeError: attribute 'gi_running' of 'generator' objects is not writable
1390 >>> def g():
1391 ... yield me.gi_running
1392 >>> me = g()
1393 >>> me.gi_running
1394 0
1395 >>> next(me)
1396 1
1397 >>> me.gi_running
1398 0
1399
1400 A clever union-find implementation from c.l.py, due to David Eppstein.
1401 Sent: Friday, June 29, 2001 12:16 PM
1402 To: [email protected]
1403 Subject: Re: PEP 255: Simple Generators
1404
1405 >>> class disjointSet:
1406 ... def __init__(self, name):
1407 ... self.name = name
1408 ... self.parent = None
1409 ... self.generator = self.generate()
1410 ...
1411 ... def generate(self):
1412 ... while not self.parent:
1413 ... yield self
1414 ... for x in self.parent.generator:
1415 ... yield x
1416 ...
1417 ... def find(self):
1418 ... return next(self.generator)
1419 ...
1420 ... def union(self, parent):
1421 ... if self.parent:
1422 ... raise ValueError("Sorry, I'm not a root!")
1423 ... self.parent = parent
1424 ...
1425 ... def __str__(self):
1426 ... return self.name
1427
1428 >>> names = "ABCDEFGHIJKLM"
1429 >>> sets = [disjointSet(name) for name in names]
1430 >>> roots = sets[:]
1431
1432 >>> import random
1433 >>> gen = random.Random(42)
1434 >>> while 1:
1435 ... for s in sets:
1436 ... print(" %s->%s" % (s, s.find()), end='')
1437 ... print()
1438 ... if len(roots) > 1:
1439 ... s1 = gen.choice(roots)
1440 ... roots.remove(s1)
1441 ... s2 = gen.choice(roots)
1442 ... s1.union(s2)
1443 ... print("merged", s1, "into", s2)
1444 ... else:
1445 ... break
1446 A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->K L->L M->M
1447 merged K into B
1448 A->A B->B C->C D->D E->E F->F G->G H->H I->I J->J K->B L->L M->M
1449 merged A into F
1450 A->F B->B C->C D->D E->E F->F G->G H->H I->I J->J K->B L->L M->M
1451 merged E into F
1452 A->F B->B C->C D->D E->F F->F G->G H->H I->I J->J K->B L->L M->M
1453 merged D into C
1454 A->F B->B C->C D->C E->F F->F G->G H->H I->I J->J K->B L->L M->M
1455 merged M into C
1456 A->F B->B C->C D->C E->F F->F G->G H->H I->I J->J K->B L->L M->C
1457 merged J into B
1458 A->F B->B C->C D->C E->F F->F G->G H->H I->I J->B K->B L->L M->C
1459 merged B into C
1460 A->F B->C C->C D->C E->F F->F G->G H->H I->I J->C K->C L->L M->C
1461 merged F into G
1462 A->G B->C C->C D->C E->G F->G G->G H->H I->I J->C K->C L->L M->C
1463 merged L into C
1464 A->G B->C C->C D->C E->G F->G G->G H->H I->I J->C K->C L->C M->C
1465 merged G into I
1466 A->I B->C C->C D->C E->I F->I G->I H->H I->I J->C K->C L->C M->C
1467 merged I into H
1468 A->H B->C C->C D->C E->H F->H G->H H->H I->H J->C K->C L->C M->C
1469 merged C into H
1470 A->H B->H C->H D->H E->H F->H G->H H->H I->H J->H K->H L->H M->H
1471
1472 """
1473 # Emacs turd '
1474
1475 # Fun tests (for sufficiently warped notions of "fun").
1476
1477 fun_tests = """
1478
1479 Build up to a recursive Sieve of Eratosthenes generator.
1480
1481 >>> def firstn(g, n):
1482 ... return [next(g) for i in range(n)]
1483
1484 >>> def intsfrom(i):
1485 ... while 1:
1486 ... yield i
1487 ... i += 1
1488
1489 >>> firstn(intsfrom(5), 7)
1490 [5, 6, 7, 8, 9, 10, 11]
1491
1492 >>> def exclude_multiples(n, ints):
1493 ... for i in ints:
1494 ... if i % n:
1495 ... yield i
1496
1497 >>> firstn(exclude_multiples(3, intsfrom(1)), 6)
1498 [1, 2, 4, 5, 7, 8]
1499
1500 >>> def sieve(ints):
1501 ... prime = next(ints)
1502 ... yield prime
1503 ... not_divisible_by_prime = exclude_multiples(prime, ints)
1504 ... for p in sieve(not_divisible_by_prime):
1505 ... yield p
1506
1507 >>> primes = sieve(intsfrom(2))
1508 >>> firstn(primes, 20)
1509 [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
1510
1511
1512 Another famous problem: generate all integers of the form
1513 2**i * 3**j * 5**k
1514 in increasing order, where i,j,k >= 0. Trickier than it may look at first!
1515 Try writing it without generators, and correctly, and without generating
1516 3 internal results for each result output.
1517
1518 >>> def times(n, g):
1519 ... for i in g:
1520 ... yield n * i
1521 >>> firstn(times(10, intsfrom(1)), 10)
1522 [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
1523
1524 >>> def merge(g, h):
1525 ... ng = next(g)
1526 ... nh = next(h)
1527 ... while 1:
1528 ... if ng < nh:
1529 ... yield ng
1530 ... ng = next(g)
1531 ... elif ng > nh:
1532 ... yield nh
1533 ... nh = next(h)
1534 ... else:
1535 ... yield ng
1536 ... ng = next(g)
1537 ... nh = next(h)
1538
1539 The following works, but is doing a whale of a lot of redundant work --
1540 it's not clear how to get the internal uses of m235 to share a single
1541 generator. Note that me_times2 (etc) each need to see every element in the
1542 result sequence. So this is an example where lazy lists are more natural
1543 (you can look at the head of a lazy list any number of times).
1544
1545 >>> def m235():
1546 ... yield 1
1547 ... me_times2 = times(2, m235())
1548 ... me_times3 = times(3, m235())
1549 ... me_times5 = times(5, m235())
1550 ... for i in merge(merge(me_times2,
1551 ... me_times3),
1552 ... me_times5):
1553 ... yield i
1554
1555 Don't print "too many" of these -- the implementation above is extremely
1556 inefficient: each call of m235() leads to 3 recursive calls, and in
1557 turn each of those 3 more, and so on, and so on, until we've descended
1558 enough levels to satisfy the print stmts. Very odd: when I printed 5
1559 lines of results below, this managed to screw up Win98's malloc in "the
1560 usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting
1561 address space, and it *looked* like a very slow leak.
1562
1563 >>> result = m235()
1564 >>> for i in range(3):
1565 ... print(firstn(result, 15))
1566 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
1567 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
1568 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
1569
1570 Heh. Here's one way to get a shared list, complete with an excruciating
1571 namespace renaming trick. The *pretty* part is that the times() and merge()
1572 functions can be reused as-is, because they only assume their stream
1573 arguments are iterable -- a LazyList is the same as a generator to times().
1574
1575 >>> class LazyList:
1576 ... def __init__(self, g):
1577 ... self.sofar = []
1578 ... self.fetch = g.__next__
1579 ...
1580 ... def __getitem__(self, i):
1581 ... sofar, fetch = self.sofar, self.fetch
1582 ... while i >= len(sofar):
1583 ... sofar.append(fetch())
1584 ... return sofar[i]
1585
1586 >>> def m235():
1587 ... yield 1
1588 ... # Gack: m235 below actually refers to a LazyList.
1589 ... me_times2 = times(2, m235)
1590 ... me_times3 = times(3, m235)
1591 ... me_times5 = times(5, m235)
1592 ... for i in merge(merge(me_times2,
1593 ... me_times3),
1594 ... me_times5):
1595 ... yield i
1596
1597 Print as many of these as you like -- *this* implementation is memory-
1598 efficient.
1599
1600 >>> m235 = LazyList(m235())
1601 >>> for i in range(5):
1602 ... print([m235[j] for j in range(15*i, 15*(i+1))])
1603 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
1604 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
1605 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
1606 [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
1607 [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
1608
1609 Ye olde Fibonacci generator, LazyList style.
1610
1611 >>> def fibgen(a, b):
1612 ...
1613 ... def sum(g, h):
1614 ... while 1:
1615 ... yield next(g) + next(h)
1616 ...
1617 ... def tail(g):
1618 ... next(g) # throw first away
1619 ... for x in g:
1620 ... yield x
1621 ...
1622 ... yield a
1623 ... yield b
1624 ... for s in sum(iter(fib),
1625 ... tail(iter(fib))):
1626 ... yield s
1627
1628 >>> fib = LazyList(fibgen(1, 2))
1629 >>> firstn(iter(fib), 17)
1630 [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
1631
1632
1633 Running after your tail with itertools.tee (new in version 2.4)
1634
1635 The algorithms "m235" (Hamming) and Fibonacci presented above are both
1636 examples of a whole family of FP (functional programming) algorithms
1637 where a function produces and returns a list while the production algorithm
1638 suppose the list as already produced by recursively calling itself.
1639 For these algorithms to work, they must:
1640
1641 - produce at least a first element without presupposing the existence of
1642 the rest of the list
1643 - produce their elements in a lazy manner
1644
1645 To work efficiently, the beginning of the list must not be recomputed over
1646 and over again. This is ensured in most FP languages as a built-in feature.
1647 In python, we have to explicitly maintain a list of already computed results
1648 and abandon genuine recursivity.
1649
1650 This is what had been attempted above with the LazyList class. One problem
1651 with that class is that it keeps a list of all of the generated results and
1652 therefore continually grows. This partially defeats the goal of the generator
1653 concept, viz. produce the results only as needed instead of producing them
1654 all and thereby wasting memory.
1655
1656 Thanks to itertools.tee, it is now clear "how to get the internal uses of
1657 m235 to share a single generator".
1658
1659 >>> from itertools import tee
1660 >>> def m235():
1661 ... def _m235():
1662 ... yield 1
1663 ... for n in merge(times(2, m2),
1664 ... merge(times(3, m3),
1665 ... times(5, m5))):
1666 ... yield n
1667 ... m1 = _m235()
1668 ... m2, m3, m5, mRes = tee(m1, 4)
1669 ... return mRes
1670
1671 >>> it = m235()
1672 >>> for i in range(5):
1673 ... print(firstn(it, 15))
1674 [1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
1675 [25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
1676 [81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
1677 [200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
1678 [400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
1679
1680 The "tee" function does just what we want. It internally keeps a generated
1681 result for as long as it has not been "consumed" from all of the duplicated
1682 iterators, whereupon it is deleted. You can therefore print the hamming
1683 sequence during hours without increasing memory usage, or very little.
1684
1685 The beauty of it is that recursive running-after-their-tail FP algorithms
1686 are quite straightforwardly expressed with this Python idiom.
1687
1688 Ye olde Fibonacci generator, tee style.
1689
1690 >>> def fib():
1691 ...
1692 ... def _isum(g, h):
1693 ... while 1:
1694 ... yield next(g) + next(h)
1695 ...
1696 ... def _fib():
1697 ... yield 1
1698 ... yield 2
1699 ... next(fibTail) # throw first away
1700 ... for res in _isum(fibHead, fibTail):
1701 ... yield res
1702 ...
1703 ... realfib = _fib()
1704 ... fibHead, fibTail, fibRes = tee(realfib, 3)
1705 ... return fibRes
1706
1707 >>> firstn(fib(), 17)
1708 [1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
1709
1710 """
1711
1712 # syntax_tests mostly provokes SyntaxErrors. Also fiddling with #if 0
1713 # hackery.
1714
1715 syntax_tests = """
1716
1717 These are fine:
1718
1719 >>> def f():
1720 ... yield 1
1721 ... return
1722
1723 >>> def f():
1724 ... try:
1725 ... yield 1
1726 ... finally:
1727 ... pass
1728
1729 >>> def f():
1730 ... try:
1731 ... try:
1732 ... 1//0
1733 ... except ZeroDivisionError:
1734 ... yield 666
1735 ... except:
1736 ... pass
1737 ... finally:
1738 ... pass
1739
1740 >>> def f():
1741 ... try:
1742 ... try:
1743 ... yield 12
1744 ... 1//0
1745 ... except ZeroDivisionError:
1746 ... yield 666
1747 ... except:
1748 ... try:
1749 ... x = 12
1750 ... finally:
1751 ... yield 12
1752 ... except:
1753 ... return
1754 >>> list(f())
1755 [12, 666]
1756
1757 >>> def f():
1758 ... yield
1759 >>> type(f())
1760 <class 'generator'>
1761
1762
1763 >>> def f():
1764 ... if 0:
1765 ... yield
1766 >>> type(f())
1767 <class 'generator'>
1768
1769
1770 >>> def f():
1771 ... if 0:
1772 ... yield 1
1773 >>> type(f())
1774 <class 'generator'>
1775
1776 >>> def f():
1777 ... if "":
1778 ... yield None
1779 >>> type(f())
1780 <class 'generator'>
1781
1782 >>> def f():
1783 ... return
1784 ... try:
1785 ... if x==4:
1786 ... pass
1787 ... elif 0:
1788 ... try:
1789 ... 1//0
1790 ... except SyntaxError:
1791 ... pass
1792 ... else:
1793 ... if 0:
1794 ... while 12:
1795 ... x += 1
1796 ... yield 2 # don't blink
1797 ... f(a, b, c, d, e)
1798 ... else:
1799 ... pass
1800 ... except:
1801 ... x = 1
1802 ... return
1803 >>> type(f())
1804 <class 'generator'>
1805
1806 >>> def f():
1807 ... if 0:
1808 ... def g():
1809 ... yield 1
1810 ...
1811 >>> type(f())
1812 <class 'NoneType'>
1813
1814 >>> def f():
1815 ... if 0:
1816 ... class C:
1817 ... def __init__(self):
1818 ... yield 1
1819 ... def f(self):
1820 ... yield 2
1821 >>> type(f())
1822 <class 'NoneType'>
1823
1824 >>> def f():
1825 ... if 0:
1826 ... return
1827 ... if 0:
1828 ... yield 2
1829 >>> type(f())
1830 <class 'generator'>
1831
1832 This one caused a crash (see SF bug 567538):
1833
1834 >>> def f():
1835 ... for i in range(3):
1836 ... try:
1837 ... continue
1838 ... finally:
1839 ... yield i
1840 ...
1841 >>> g = f()
1842 >>> print(next(g))
1843 0
1844 >>> print(next(g))
1845 1
1846 >>> print(next(g))
1847 2
1848 >>> print(next(g))
1849 Traceback (most recent call last):
1850 StopIteration
1851
1852
1853 Test the gi_code attribute
1854
1855 >>> def f():
1856 ... yield 5
1857 ...
1858 >>> g = f()
1859 >>> g.gi_code is f.__code__
1860 True
1861 >>> next(g)
1862 5
1863 >>> next(g)
1864 Traceback (most recent call last):
1865 StopIteration
1866 >>> g.gi_code is f.__code__
1867 True
1868
1869
1870 Test the __name__ attribute and the repr()
1871
1872 >>> def f():
1873 ... yield 5
1874 ...
1875 >>> g = f()
1876 >>> g.__name__
1877 'f'
1878 >>> repr(g) # doctest: +ELLIPSIS
1879 '<generator object f at ...>'
1880
1881 Lambdas shouldn't have their usual return behavior.
1882
1883 >>> x = lambda: (yield 1)
1884 >>> list(x())
1885 [1]
1886
1887 >>> x = lambda: ((yield 1), (yield 2))
1888 >>> list(x())
1889 [1, 2]
1890 """
1891
1892 # conjoin is a simple backtracking generator, named in honor of Icon's
1893 # "conjunction" control structure. Pass a list of no-argument functions
1894 # that return iterable objects. Easiest to explain by example: assume the
1895 # function list [x, y, z] is passed. Then conjoin acts like:
1896 #
1897 # def g():
1898 # values = [None] * 3
1899 # for values[0] in x():
1900 # for values[1] in y():
1901 # for values[2] in z():
1902 # yield values
1903 #
1904 # So some 3-lists of values *may* be generated, each time we successfully
1905 # get into the innermost loop. If an iterator fails (is exhausted) before
1906 # then, it "backtracks" to get the next value from the nearest enclosing
1907 # iterator (the one "to the left"), and starts all over again at the next
1908 # slot (pumps a fresh iterator). Of course this is most useful when the
1909 # iterators have side-effects, so that which values *can* be generated at
1910 # each slot depend on the values iterated at previous slots.
1911
1912 def simple_conjoin(gs):
1913
1914 values = [None] * len(gs)
1915
1916 def gen(i):
1917 if i >= len(gs):
1918 yield values
1919 else:
1920 for values[i] in gs[i]():
1921 for x in gen(i+1):
1922 yield x
1923
1924 for x in gen(0):
1925 yield x
1926
1927 # That works fine, but recursing a level and checking i against len(gs) for
1928 # each item produced is inefficient. By doing manual loop unrolling across
1929 # generator boundaries, it's possible to eliminate most of that overhead.
1930 # This isn't worth the bother *in general* for generators, but conjoin() is
1931 # a core building block for some CPU-intensive generator applications.
1932
1933 def conjoin(gs):
1934
1935 n = len(gs)
1936 values = [None] * n
1937
1938 # Do one loop nest at time recursively, until the # of loop nests
1939 # remaining is divisible by 3.
1940
1941 def gen(i):
1942 if i >= n:
1943 yield values
1944
1945 elif (n-i) % 3:
1946 ip1 = i+1
1947 for values[i] in gs[i]():
1948 for x in gen(ip1):
1949 yield x
1950
1951 else:
1952 for x in _gen3(i):
1953 yield x
1954
1955 # Do three loop nests at a time, recursing only if at least three more
1956 # remain. Don't call directly: this is an internal optimization for
1957 # gen's use.
1958
1959 def _gen3(i):
1960 assert i < n and (n-i) % 3 == 0
1961 ip1, ip2, ip3 = i+1, i+2, i+3
1962 g, g1, g2 = gs[i : ip3]
1963
1964 if ip3 >= n:
1965 # These are the last three, so we can yield values directly.
1966 for values[i] in g():
1967 for values[ip1] in g1():
1968 for values[ip2] in g2():
1969 yield values
1970
1971 else:
1972 # At least 6 loop nests remain; peel off 3 and recurse for the
1973 # rest.
1974 for values[i] in g():
1975 for values[ip1] in g1():
1976 for values[ip2] in g2():
1977 for x in _gen3(ip3):
1978 yield x
1979
1980 for x in gen(0):
1981 yield x
1982
1983 # And one more approach: For backtracking apps like the Knight's Tour
1984 # solver below, the number of backtracking levels can be enormous (one
1985 # level per square, for the Knight's Tour, so that e.g. a 100x100 board
1986 # needs 10,000 levels). In such cases Python is likely to run out of
1987 # stack space due to recursion. So here's a recursion-free version of
1988 # conjoin too.
1989 # NOTE WELL: This allows large problems to be solved with only trivial
1990 # demands on stack space. Without explicitly resumable generators, this is
1991 # much harder to achieve. OTOH, this is much slower (up to a factor of 2)
1992 # than the fancy unrolled recursive conjoin.
1993
1994 def flat_conjoin(gs): # rename to conjoin to run tests with this instead
1995 n = len(gs)
1996 values = [None] * n
1997 iters = [None] * n
1998 _StopIteration = StopIteration # make local because caught a *lot*
1999 i = 0
2000 while 1:
2001 # Descend.
2002 try:
2003 while i < n:
2004 it = iters[i] = gs[i]().__next__
2005 values[i] = it()
2006 i += 1
2007 except _StopIteration:
2008 pass
2009 else:
2010 assert i == n
2011 yield values
2012
2013 # Backtrack until an older iterator can be resumed.
2014 i -= 1
2015 while i >= 0:
2016 try:
2017 values[i] = iters[i]()
2018 # Success! Start fresh at next level.
2019 i += 1
2020 break
2021 except _StopIteration:
2022 # Continue backtracking.
2023 i -= 1
2024 else:
2025 assert i < 0
2026 break
2027
2028 # A conjoin-based N-Queens solver.
2029
2030 class Queens:
2031 def __init__(self, n):
2032 self.n = n
2033 rangen = range(n)
2034
2035 # Assign a unique int to each column and diagonal.
2036 # columns: n of those, range(n).
2037 # NW-SE diagonals: 2n-1 of these, i-j unique and invariant along
2038 # each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0-
2039 # based.
2040 # NE-SW diagonals: 2n-1 of these, i+j unique and invariant along
2041 # each, smallest i+j is 0, largest is 2n-2.
2042
2043 # For each square, compute a bit vector of the columns and
2044 # diagonals it covers, and for each row compute a function that
2045 # generates the possibilities for the columns in that row.
2046 self.rowgenerators = []
2047 for i in rangen:
2048 rowuses = [(1 << j) | # column ordinal
2049 (1 << (n + i-j + n-1)) | # NW-SE ordinal
2050 (1 << (n + 2*n-1 + i+j)) # NE-SW ordinal
2051 for j in rangen]
2052
2053 def rowgen(rowuses=rowuses):
2054 for j in rangen:
2055 uses = rowuses[j]
2056 if uses & self.used == 0:
2057 self.used |= uses
2058 yield j
2059 self.used &= ~uses
2060
2061 self.rowgenerators.append(rowgen)
2062
2063 # Generate solutions.
2064 def solve(self):
2065 self.used = 0
2066 for row2col in conjoin(self.rowgenerators):
2067 yield row2col
2068
2069 def printsolution(self, row2col):
2070 n = self.n
2071 assert n == len(row2col)
2072 sep = "+" + "-+" * n
2073 print(sep)
2074 for i in range(n):
2075 squares = [" " for j in range(n)]
2076 squares[row2col[i]] = "Q"
2077 print("|" + "|".join(squares) + "|")
2078 print(sep)
2079
2080 # A conjoin-based Knight's Tour solver. This is pretty sophisticated
2081 # (e.g., when used with flat_conjoin above, and passing hard=1 to the
2082 # constructor, a 200x200 Knight's Tour was found quickly -- note that we're
2083 # creating 10s of thousands of generators then!), and is lengthy.
2084
2085 class Knights:
2086 def __init__(self, m, n, hard=0):
2087 self.m, self.n = m, n
2088
2089 # solve() will set up succs[i] to be a list of square #i's
2090 # successors.
2091 succs = self.succs = []
2092
2093 # Remove i0 from each of its successor's successor lists, i.e.
2094 # successors can't go back to i0 again. Return 0 if we can
2095 # detect this makes a solution impossible, else return 1.
2096
2097 def remove_from_successors(i0, len=len):
2098 # If we remove all exits from a free square, we're dead:
2099 # even if we move to it next, we can't leave it again.
2100 # If we create a square with one exit, we must visit it next;
2101 # else somebody else will have to visit it, and since there's
2102 # only one adjacent, there won't be a way to leave it again.
2103 # Finally, if we create more than one free square with a
2104 # single exit, we can only move to one of them next, leaving
2105 # the other one a dead end.
2106 ne0 = ne1 = 0
2107 for i in succs[i0]:
2108 s = succs[i]
2109 s.remove(i0)
2110 e = len(s)
2111 if e == 0:
2112 ne0 += 1
2113 elif e == 1:
2114 ne1 += 1
2115 return ne0 == 0 and ne1 < 2
2116
2117 # Put i0 back in each of its successor's successor lists.
2118
2119 def add_to_successors(i0):
2120 for i in succs[i0]:
2121 succs[i].append(i0)
2122
2123 # Generate the first move.
2124 def first():
2125 if m < 1 or n < 1:
2126 return
2127
2128 # Since we're looking for a cycle, it doesn't matter where we
2129 # start. Starting in a corner makes the 2nd move easy.
2130 corner = self.coords2index(0, 0)
2131 remove_from_successors(corner)
2132 self.lastij = corner
2133 yield corner
2134 add_to_successors(corner)
2135
2136 # Generate the second moves.
2137 def second():
2138 corner = self.coords2index(0, 0)
2139 assert self.lastij == corner # i.e., we started in the corner
2140 if m < 3 or n < 3:
2141 return
2142 assert len(succs[corner]) == 2
2143 assert self.coords2index(1, 2) in succs[corner]
2144 assert self.coords2index(2, 1) in succs[corner]
2145 # Only two choices. Whichever we pick, the other must be the
2146 # square picked on move m*n, as it's the only way to get back
2147 # to (0, 0). Save its index in self.final so that moves before
2148 # the last know it must be kept free.
2149 for i, j in (1, 2), (2, 1):
2150 this = self.coords2index(i, j)
2151 final = self.coords2index(3-i, 3-j)
2152 self.final = final
2153
2154 remove_from_successors(this)
2155 succs[final].append(corner)
2156 self.lastij = this
2157 yield this
2158 succs[final].remove(corner)
2159 add_to_successors(this)
2160
2161 # Generate moves 3 through m*n-1.
2162 def advance(len=len):
2163 # If some successor has only one exit, must take it.
2164 # Else favor successors with fewer exits.
2165 candidates = []
2166 for i in succs[self.lastij]:
2167 e = len(succs[i])
2168 assert e > 0, "else remove_from_successors() pruning flawed"
2169 if e == 1:
2170 candidates = [(e, i)]
2171 break
2172 candidates.append((e, i))
2173 else:
2174 candidates.sort()
2175
2176 for e, i in candidates:
2177 if i != self.final:
2178 if remove_from_successors(i):
2179 self.lastij = i
2180 yield i
2181 add_to_successors(i)
2182
2183 # Generate moves 3 through m*n-1. Alternative version using a
2184 # stronger (but more expensive) heuristic to order successors.
2185 # Since the # of backtracking levels is m*n, a poor move early on
2186 # can take eons to undo. Smallest square board for which this
2187 # matters a lot is 52x52.
2188 def advance_hard(vmid=(m-1)/2.0, hmid=(n-1)/2.0, len=len):
2189 # If some successor has only one exit, must take it.
2190 # Else favor successors with fewer exits.
2191 # Break ties via max distance from board centerpoint (favor
2192 # corners and edges whenever possible).
2193 candidates = []
2194 for i in succs[self.lastij]:
2195 e = len(succs[i])
2196 assert e > 0, "else remove_from_successors() pruning flawed"
2197 if e == 1:
2198 candidates = [(e, 0, i)]
2199 break
2200 i1, j1 = self.index2coords(i)
2201 d = (i1 - vmid)**2 + (j1 - hmid)**2
2202 candidates.append((e, -d, i))
2203 else:
2204 candidates.sort()
2205
2206 for e, d, i in candidates:
2207 if i != self.final:
2208 if remove_from_successors(i):
2209 self.lastij = i
2210 yield i
2211 add_to_successors(i)
2212
2213 # Generate the last move.
2214 def last():
2215 assert self.final in succs[self.lastij]
2216 yield self.final
2217
2218 if m*n < 4:
2219 self.squaregenerators = [first]
2220 else:
2221 self.squaregenerators = [first, second] + \
2222 [hard and advance_hard or advance] * (m*n - 3) + \
2223 [last]
2224
2225 def coords2index(self, i, j):
2226 assert 0 <= i < self.m
2227 assert 0 <= j < self.n
2228 return i * self.n + j
2229
2230 def index2coords(self, index):
2231 assert 0 <= index < self.m * self.n
2232 return divmod(index, self.n)
2233
2234 def _init_board(self):
2235 succs = self.succs
2236 del succs[:]
2237 m, n = self.m, self.n
2238 c2i = self.coords2index
2239
2240 offsets = [( 1, 2), ( 2, 1), ( 2, -1), ( 1, -2),
2241 (-1, -2), (-2, -1), (-2, 1), (-1, 2)]
2242 rangen = range(n)
2243 for i in range(m):
2244 for j in rangen:
2245 s = [c2i(i+io, j+jo) for io, jo in offsets
2246 if 0 <= i+io < m and
2247 0 <= j+jo < n]
2248 succs.append(s)
2249
2250 # Generate solutions.
2251 def solve(self):
2252 self._init_board()
2253 for x in conjoin(self.squaregenerators):
2254 yield x
2255
2256 def printsolution(self, x):
2257 m, n = self.m, self.n
2258 assert len(x) == m*n
2259 w = len(str(m*n))
2260 format = "%" + str(w) + "d"
2261
2262 squares = [[None] * n for i in range(m)]
2263 k = 1
2264 for i in x:
2265 i1, j1 = self.index2coords(i)
2266 squares[i1][j1] = format % k
2267 k += 1
2268
2269 sep = "+" + ("-" * w + "+") * n
2270 print(sep)
2271 for i in range(m):
2272 row = squares[i]
2273 print("|" + "|".join(row) + "|")
2274 print(sep)
2275
2276 conjoin_tests = """
2277
2278 Generate the 3-bit binary numbers in order. This illustrates dumbest-
2279 possible use of conjoin, just to generate the full cross-product.
2280
2281 >>> for c in conjoin([lambda: iter((0, 1))] * 3):
2282 ... print(c)
2283 [0, 0, 0]
2284 [0, 0, 1]
2285 [0, 1, 0]
2286 [0, 1, 1]
2287 [1, 0, 0]
2288 [1, 0, 1]
2289 [1, 1, 0]
2290 [1, 1, 1]
2291
2292 For efficiency in typical backtracking apps, conjoin() yields the same list
2293 object each time. So if you want to save away a full account of its
2294 generated sequence, you need to copy its results.
2295
2296 >>> def gencopy(iterator):
2297 ... for x in iterator:
2298 ... yield x[:]
2299
2300 >>> for n in range(10):
2301 ... all = list(gencopy(conjoin([lambda: iter((0, 1))] * n)))
2302 ... print(n, len(all), all[0] == [0] * n, all[-1] == [1] * n)
2303 0 1 True True
2304 1 2 True True
2305 2 4 True True
2306 3 8 True True
2307 4 16 True True
2308 5 32 True True
2309 6 64 True True
2310 7 128 True True
2311 8 256 True True
2312 9 512 True True
2313
2314 And run an 8-queens solver.
2315
2316 >>> q = Queens(8)
2317 >>> LIMIT = 2
2318 >>> count = 0
2319 >>> for row2col in q.solve():
2320 ... count += 1
2321 ... if count <= LIMIT:
2322 ... print("Solution", count)
2323 ... q.printsolution(row2col)
2324 Solution 1
2325 +-+-+-+-+-+-+-+-+
2326 |Q| | | | | | | |
2327 +-+-+-+-+-+-+-+-+
2328 | | | | |Q| | | |
2329 +-+-+-+-+-+-+-+-+
2330 | | | | | | | |Q|
2331 +-+-+-+-+-+-+-+-+
2332 | | | | | |Q| | |
2333 +-+-+-+-+-+-+-+-+
2334 | | |Q| | | | | |
2335 +-+-+-+-+-+-+-+-+
2336 | | | | | | |Q| |
2337 +-+-+-+-+-+-+-+-+
2338 | |Q| | | | | | |
2339 +-+-+-+-+-+-+-+-+
2340 | | | |Q| | | | |
2341 +-+-+-+-+-+-+-+-+
2342 Solution 2
2343 +-+-+-+-+-+-+-+-+
2344 |Q| | | | | | | |
2345 +-+-+-+-+-+-+-+-+
2346 | | | | | |Q| | |
2347 +-+-+-+-+-+-+-+-+
2348 | | | | | | | |Q|
2349 +-+-+-+-+-+-+-+-+
2350 | | |Q| | | | | |
2351 +-+-+-+-+-+-+-+-+
2352 | | | | | | |Q| |
2353 +-+-+-+-+-+-+-+-+
2354 | | | |Q| | | | |
2355 +-+-+-+-+-+-+-+-+
2356 | |Q| | | | | | |
2357 +-+-+-+-+-+-+-+-+
2358 | | | | |Q| | | |
2359 +-+-+-+-+-+-+-+-+
2360
2361 >>> print(count, "solutions in all.")
2362 92 solutions in all.
2363
2364 And run a Knight's Tour on a 10x10 board. Note that there are about
2365 20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion.
2366
2367 >>> k = Knights(10, 10)
2368 >>> LIMIT = 2
2369 >>> count = 0
2370 >>> for x in k.solve():
2371 ... count += 1
2372 ... if count <= LIMIT:
2373 ... print("Solution", count)
2374 ... k.printsolution(x)
2375 ... else:
2376 ... break
2377 Solution 1
2378 +---+---+---+---+---+---+---+---+---+---+
2379 | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8|
2380 +---+---+---+---+---+---+---+---+---+---+
2381 | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11|
2382 +---+---+---+---+---+---+---+---+---+---+
2383 | 59|100| 73| 36| 41| 56| 39| 32| 9| 6|
2384 +---+---+---+---+---+---+---+---+---+---+
2385 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
2386 +---+---+---+---+---+---+---+---+---+---+
2387 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
2388 +---+---+---+---+---+---+---+---+---+---+
2389 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
2390 +---+---+---+---+---+---+---+---+---+---+
2391 | 87| 98| 91| 80| 77| 84| 53| 46| 65| 44|
2392 +---+---+---+---+---+---+---+---+---+---+
2393 | 90| 23| 88| 95| 70| 79| 68| 83| 14| 17|
2394 +---+---+---+---+---+---+---+---+---+---+
2395 | 97| 92| 21| 78| 81| 94| 19| 16| 45| 66|
2396 +---+---+---+---+---+---+---+---+---+---+
2397 | 22| 89| 96| 93| 20| 69| 82| 67| 18| 15|
2398 +---+---+---+---+---+---+---+---+---+---+
2399 Solution 2
2400 +---+---+---+---+---+---+---+---+---+---+
2401 | 1| 58| 27| 34| 3| 40| 29| 10| 5| 8|
2402 +---+---+---+---+---+---+---+---+---+---+
2403 | 26| 35| 2| 57| 28| 33| 4| 7| 30| 11|
2404 +---+---+---+---+---+---+---+---+---+---+
2405 | 59|100| 73| 36| 41| 56| 39| 32| 9| 6|
2406 +---+---+---+---+---+---+---+---+---+---+
2407 | 74| 25| 60| 55| 72| 37| 42| 49| 12| 31|
2408 +---+---+---+---+---+---+---+---+---+---+
2409 | 61| 86| 99| 76| 63| 52| 47| 38| 43| 50|
2410 +---+---+---+---+---+---+---+---+---+---+
2411 | 24| 75| 62| 85| 54| 71| 64| 51| 48| 13|
2412 +---+---+---+---+---+---+---+---+---+---+
2413 | 87| 98| 89| 80| 77| 84| 53| 46| 65| 44|
2414 +---+---+---+---+---+---+---+---+---+---+
2415 | 90| 23| 92| 95| 70| 79| 68| 83| 14| 17|
2416 +---+---+---+---+---+---+---+---+---+---+
2417 | 97| 88| 21| 78| 81| 94| 19| 16| 45| 66|
2418 +---+---+---+---+---+---+---+---+---+---+
2419 | 22| 91| 96| 93| 20| 69| 82| 67| 18| 15|
2420 +---+---+---+---+---+---+---+---+---+---+
2421 """
2422
2423 weakref_tests = """\
2424 Generators are weakly referencable:
2425
2426 >>> import weakref
2427 >>> def gen():
2428 ... yield 'foo!'
2429 ...
2430 >>> wr = weakref.ref(gen)
2431 >>> wr() is gen
2432 True
2433 >>> p = weakref.proxy(gen)
2434
2435 Generator-iterators are weakly referencable as well:
2436
2437 >>> gi = gen()
2438 >>> wr = weakref.ref(gi)
2439 >>> wr() is gi
2440 True
2441 >>> p = weakref.proxy(gi)
2442 >>> list(p)
2443 ['foo!']
2444
2445 """
2446
2447 coroutine_tests = """\
2448 >>> from test.support import gc_collect
2449
2450 Sending a value into a started generator:
2451
2452 >>> def f():
2453 ... print((yield 1))
2454 ... yield 2
2455 >>> g = f()
2456 >>> next(g)
2457 1
2458 >>> g.send(42)
2459 42
2460 2
2461
2462 Sending a value into a new generator produces a TypeError:
2463
2464 >>> f().send("foo")
2465 Traceback (most recent call last):
2466 ...
2467 TypeError: can't send non-None value to a just-started generator
2468
2469
2470 Yield by itself yields None:
2471
2472 >>> def f(): yield
2473 >>> list(f())
2474 [None]
2475
2476
2477 Yield is allowed only in the outermost iterable in generator expression:
2478
2479 >>> def f(): list(i for i in [(yield 26)])
2480 >>> type(f())
2481 <class 'generator'>
2482
2483
2484 A yield expression with augmented assignment.
2485
2486 >>> def coroutine(seq):
2487 ... count = 0
2488 ... while count < 200:
2489 ... count += yield
2490 ... seq.append(count)
2491 >>> seq = []
2492 >>> c = coroutine(seq)
2493 >>> next(c)
2494 >>> print(seq)
2495 []
2496 >>> c.send(10)
2497 >>> print(seq)
2498 [10]
2499 >>> c.send(10)
2500 >>> print(seq)
2501 [10, 20]
2502 >>> c.send(10)
2503 >>> print(seq)
2504 [10, 20, 30]
2505
2506
2507 Check some syntax errors for yield expressions:
2508
2509 >>> f=lambda: (yield 1),(yield 2)
2510 Traceback (most recent call last):
2511 ...
2512 SyntaxError: 'yield' outside function
2513
2514 >>> f=lambda: (yield from (1,2)), (yield from (3,4))
2515 Traceback (most recent call last):
2516 ...
2517 SyntaxError: 'yield from' outside function
2518
2519 >>> yield from [1,2]
2520 Traceback (most recent call last):
2521 ...
2522 SyntaxError: 'yield from' outside function
2523
2524 >>> def f(): x = yield = y
2525 Traceback (most recent call last):
2526 ...
2527 SyntaxError: assignment to yield expression not possible
2528
2529 >>> def f(): (yield bar) = y
2530 Traceback (most recent call last):
2531 ...
2532 SyntaxError: cannot assign to yield expression here. Maybe you meant '==' instead of '='?
2533
2534 >>> def f(): (yield bar) += y
2535 Traceback (most recent call last):
2536 ...
2537 SyntaxError: 'yield expression' is an illegal expression for augmented assignment
2538
2539
2540 Now check some throw() conditions:
2541
2542 >>> def f():
2543 ... while True:
2544 ... try:
2545 ... print((yield))
2546 ... except ValueError as v:
2547 ... print("caught ValueError (%s)" % (v))
2548 >>> import sys
2549 >>> g = f()
2550 >>> next(g)
2551
2552 >>> g.throw(ValueError) # type only
2553 caught ValueError ()
2554
2555 >>> g.throw(ValueError("xyz")) # value only
2556 caught ValueError (xyz)
2557
2558 >>> import warnings
2559 >>> old_filters = warnings.filters.copy()
2560 >>> warnings.filterwarnings("ignore", category=DeprecationWarning)
2561
2562 # Filter DeprecationWarning: regarding the (type, val, tb) signature of throw().
2563 # Deprecation warnings are re-enabled below.
2564
2565 >>> g.throw(ValueError, ValueError(1)) # value+matching type
2566 caught ValueError (1)
2567
2568 >>> g.throw(ValueError, TypeError(1)) # mismatched type, rewrapped
2569 caught ValueError (1)
2570
2571 >>> g.throw(ValueError, ValueError(1), None) # explicit None traceback
2572 caught ValueError (1)
2573
2574 >>> g.throw(ValueError(1), "foo") # bad args
2575 Traceback (most recent call last):
2576 ...
2577 TypeError: instance exception may not have a separate value
2578
2579 >>> g.throw(ValueError, "foo", 23) # bad args
2580 Traceback (most recent call last):
2581 ...
2582 TypeError: throw() third argument must be a traceback object
2583
2584 >>> g.throw("abc")
2585 Traceback (most recent call last):
2586 ...
2587 TypeError: exceptions must be classes or instances deriving from BaseException, not str
2588
2589 >>> g.throw(0)
2590 Traceback (most recent call last):
2591 ...
2592 TypeError: exceptions must be classes or instances deriving from BaseException, not int
2593
2594 >>> g.throw(list)
2595 Traceback (most recent call last):
2596 ...
2597 TypeError: exceptions must be classes or instances deriving from BaseException, not type
2598
2599 >>> def throw(g,exc):
2600 ... try:
2601 ... raise exc
2602 ... except:
2603 ... g.throw(*sys.exc_info())
2604 >>> throw(g,ValueError) # do it with traceback included
2605 caught ValueError ()
2606
2607 >>> g.send(1)
2608 1
2609
2610 >>> throw(g,TypeError) # terminate the generator
2611 Traceback (most recent call last):
2612 ...
2613 TypeError
2614
2615 >>> print(g.gi_frame)
2616 None
2617
2618 >>> g.send(2)
2619 Traceback (most recent call last):
2620 ...
2621 StopIteration
2622
2623 >>> g.throw(ValueError,6) # throw on closed generator
2624 Traceback (most recent call last):
2625 ...
2626 ValueError: 6
2627
2628 >>> f().throw(ValueError,7) # throw on just-opened generator
2629 Traceback (most recent call last):
2630 ...
2631 ValueError: 7
2632
2633 >>> warnings.filters[:] = old_filters
2634
2635 # Re-enable DeprecationWarning: the (type, val, tb) exception representation is deprecated,
2636 # and may be removed in a future version of Python.
2637
2638 Plain "raise" inside a generator should preserve the traceback (#13188).
2639 The traceback should have 3 levels:
2640 - g.throw()
2641 - f()
2642 - 1/0
2643
2644 >>> def f():
2645 ... try:
2646 ... yield
2647 ... except:
2648 ... raise
2649 >>> g = f()
2650 >>> try:
2651 ... 1/0
2652 ... except ZeroDivisionError as v:
2653 ... try:
2654 ... g.throw(v)
2655 ... except Exception as w:
2656 ... tb = w.__traceback__
2657 >>> levels = 0
2658 >>> while tb:
2659 ... levels += 1
2660 ... tb = tb.tb_next
2661 >>> levels
2662 3
2663
2664 Now let's try closing a generator:
2665
2666 >>> def f():
2667 ... try: yield
2668 ... except GeneratorExit:
2669 ... print("exiting")
2670
2671 >>> g = f()
2672 >>> next(g)
2673 >>> g.close()
2674 exiting
2675 >>> g.close() # should be no-op now
2676
2677 >>> f().close() # close on just-opened generator should be fine
2678
2679 >>> def f(): yield # an even simpler generator
2680 >>> f().close() # close before opening
2681 >>> g = f()
2682 >>> next(g)
2683 >>> g.close() # close normally
2684
2685 And finalization:
2686
2687 >>> def f():
2688 ... try: yield
2689 ... finally:
2690 ... print("exiting")
2691
2692 >>> g = f()
2693 >>> next(g)
2694 >>> del g; gc_collect() # For PyPy or other GCs.
2695 exiting
2696
2697
2698 GeneratorExit is not caught by except Exception:
2699
2700 >>> def f():
2701 ... try: yield
2702 ... except Exception:
2703 ... print('except')
2704 ... finally:
2705 ... print('finally')
2706
2707 >>> g = f()
2708 >>> next(g)
2709 >>> del g; gc_collect() # For PyPy or other GCs.
2710 finally
2711
2712
2713 Now let's try some ill-behaved generators:
2714
2715 >>> def f():
2716 ... try: yield
2717 ... except GeneratorExit:
2718 ... yield "foo!"
2719 >>> g = f()
2720 >>> next(g)
2721 >>> g.close()
2722 Traceback (most recent call last):
2723 ...
2724 RuntimeError: generator ignored GeneratorExit
2725 >>> g.close()
2726
2727
2728 Our ill-behaved code should be invoked during GC:
2729
2730 >>> with support.catch_unraisable_exception() as cm:
2731 ... g = f()
2732 ... next(g)
2733 ... gen_repr = repr(g)
2734 ... del g
2735 ...
2736 ... cm.unraisable.err_msg == (f'Exception ignored while closing '
2737 ... f'generator {gen_repr}')
2738 ... cm.unraisable.exc_type == RuntimeError
2739 ... "generator ignored GeneratorExit" in str(cm.unraisable.exc_value)
2740 ... cm.unraisable.exc_traceback is not None
2741 True
2742 True
2743 True
2744 True
2745
2746 And errors thrown during closing should propagate:
2747
2748 >>> def f():
2749 ... try: yield
2750 ... except GeneratorExit:
2751 ... raise TypeError("fie!")
2752 >>> g = f()
2753 >>> next(g)
2754 >>> g.close()
2755 Traceback (most recent call last):
2756 ...
2757 TypeError: fie!
2758
2759
2760 Ensure that various yield expression constructs make their
2761 enclosing function a generator:
2762
2763 >>> def f(): x += yield
2764 >>> type(f())
2765 <class 'generator'>
2766
2767 >>> def f(): x = yield
2768 >>> type(f())
2769 <class 'generator'>
2770
2771 >>> def f(): lambda x=(yield): 1
2772 >>> type(f())
2773 <class 'generator'>
2774
2775 >>> def f(d): d[(yield "a")] = d[(yield "b")] = 27
2776 >>> data = [1,2]
2777 >>> g = f(data)
2778 >>> type(g)
2779 <class 'generator'>
2780 >>> g.send(None)
2781 'a'
2782 >>> data
2783 [1, 2]
2784 >>> g.send(0)
2785 'b'
2786 >>> data
2787 [27, 2]
2788 >>> try: g.send(1)
2789 ... except StopIteration: pass
2790 >>> data
2791 [27, 27]
2792
2793 """
2794
2795 refleaks_tests = """
2796 Prior to adding cycle-GC support to itertools.tee, this code would leak
2797 references. We add it to the standard suite so the routine refleak-tests
2798 would trigger if it starts being uncleanable again.
2799
2800 >>> import itertools
2801 >>> def leak():
2802 ... class gen:
2803 ... def __iter__(self):
2804 ... return self
2805 ... def __next__(self):
2806 ... return self.item
2807 ... g = gen()
2808 ... head, tail = itertools.tee(g)
2809 ... g.item = head
2810 ... return head
2811 >>> it = leak()
2812
2813 Make sure to also test the involvement of the tee-internal teedataobject,
2814 which stores returned items.
2815
2816 >>> item = next(it)
2817
2818
2819
2820 This test leaked at one point due to generator finalization/destruction.
2821 It was copied from Lib/test/leakers/test_generator_cycle.py before the file
2822 was removed.
2823
2824 >>> def leak():
2825 ... def gen():
2826 ... while True:
2827 ... yield g
2828 ... g = gen()
2829
2830 >>> leak()
2831
2832
2833
2834 This test isn't really generator related, but rather exception-in-cleanup
2835 related. The coroutine tests (above) just happen to cause an exception in
2836 the generator's __del__ (tp_del) method. We can also test for this
2837 explicitly, without generators. We do have to redirect stderr to avoid
2838 printing warnings and to doublecheck that we actually tested what we wanted
2839 to test.
2840
2841 >>> from test import support
2842 >>> class Leaker:
2843 ... def __del__(self):
2844 ... def invoke(message):
2845 ... raise RuntimeError(message)
2846 ... invoke("del failed")
2847 ...
2848 >>> with support.catch_unraisable_exception() as cm:
2849 ... leaker = Leaker()
2850 ... del_repr = repr(type(leaker).__del__)
2851 ... del leaker
2852 ...
2853 ... cm.unraisable.err_msg == (f'Exception ignored while '
2854 ... f'calling deallocator {del_repr}')
2855 ... cm.unraisable.exc_type == RuntimeError
2856 ... str(cm.unraisable.exc_value) == "del failed"
2857 ... cm.unraisable.exc_traceback is not None
2858 True
2859 True
2860 True
2861 True
2862
2863
2864 These refleak tests should perhaps be in a testfile of their own,
2865 test_generators just happened to be the test that drew these out.
2866
2867 """
2868
2869 __test__ = {"tut": tutorial_tests,
2870 "pep": pep_tests,
2871 "email": email_tests,
2872 "fun": fun_tests,
2873 "syntax": syntax_tests,
2874 "conjoin": conjoin_tests,
2875 "weakref": weakref_tests,
2876 "coroutine": coroutine_tests,
2877 "refleaks": refleaks_tests,
2878 }
2879
2880 def load_tests(loader, tests, pattern):
2881 tests.addTest(doctest.DocTestSuite())
2882 return tests
2883
2884
2885 if __name__ == "__main__":
2886 unittest.main()