Python code coverage for Lib/test/test_generators.py

#	count	content
1	n/a	import copy
2	n/a	import gc
3	n/a	import pickle
4	n/a	import sys
5	n/a	import unittest
6	n/a	import warnings
7	n/a	import weakref
8	n/a	import inspect
9	n/a	import types
10	n/a
11	n/a	from test import support
12	n/a
13	n/a
14	n/a	class FinalizationTest(unittest.TestCase):
15	n/a
16	n/a	def test_frame_resurrect(self):
17	n/a	# A generator frame can be resurrected by a generator's finalization.
18	n/a	def gen():
19	n/a	nonlocal frame
20	n/a	try:
21	n/a	yield
22	n/a	finally:
23	n/a	frame = sys._getframe()
24	n/a
25	n/a	g = gen()
26	n/a	wr = weakref.ref(g)
27	n/a	next(g)
28	n/a	del g
29	n/a	support.gc_collect()
30	n/a	self.assertIs(wr(), None)
31	n/a	self.assertTrue(frame)
32	n/a	del frame
33	n/a	support.gc_collect()
34	n/a
35	n/a	def test_refcycle(self):
36	n/a	# A generator caught in a refcycle gets finalized anyway.
37	n/a	old_garbage = gc.garbage[:]
38	n/a	finalized = False
39	n/a	def gen():
40	n/a	nonlocal finalized
41	n/a	try:
42	n/a	g = yield
43	n/a	yield 1
44	n/a	finally:
45	n/a	finalized = True
46	n/a
47	n/a	g = gen()
48	n/a	next(g)
49	n/a	g.send(g)
50	n/a	self.assertGreater(sys.getrefcount(g), 2)
51	n/a	self.assertFalse(finalized)
52	n/a	del g
53	n/a	support.gc_collect()
54	n/a	self.assertTrue(finalized)
55	n/a	self.assertEqual(gc.garbage, old_garbage)
56	n/a
57	n/a	def test_lambda_generator(self):
58	n/a	# Issue #23192: Test that a lambda returning a generator behaves
59	n/a	# like the equivalent function
60	n/a	f = lambda: (yield 1)
61	n/a	def g(): return (yield 1)
62	n/a
63	n/a	# test 'yield from'
64	n/a	f2 = lambda: (yield from g())
65	n/a	def g2(): return (yield from g())
66	n/a
67	n/a	f3 = lambda: (yield from f())
68	n/a	def g3(): return (yield from f())
69	n/a
70	n/a	for gen_fun in (f, g, f2, g2, f3, g3):
71	n/a	gen = gen_fun()
72	n/a	self.assertEqual(next(gen), 1)
73	n/a	with self.assertRaises(StopIteration) as cm:
74	n/a	gen.send(2)
75	n/a	self.assertEqual(cm.exception.value, 2)
76	n/a
77	n/a
78	n/a	class GeneratorTest(unittest.TestCase):
79	n/a
80	n/a	def test_name(self):
81	n/a	def func():
82	n/a	yield 1
83	n/a
84	n/a	# check generator names
85	n/a	gen = func()
86	n/a	self.assertEqual(gen.__name__, "func")
87	n/a	self.assertEqual(gen.__qualname__,
88	n/a	"GeneratorTest.test_name.<locals>.func")
89	n/a
90	n/a	# modify generator names
91	n/a	gen.__name__ = "name"
92	n/a	gen.__qualname__ = "qualname"
93	n/a	self.assertEqual(gen.__name__, "name")
94	n/a	self.assertEqual(gen.__qualname__, "qualname")
95	n/a
96	n/a	# generator names must be a string and cannot be deleted
97	n/a	self.assertRaises(TypeError, setattr, gen, '__name__', 123)
98	n/a	self.assertRaises(TypeError, setattr, gen, '__qualname__', 123)
99	n/a	self.assertRaises(TypeError, delattr, gen, '__name__')
100	n/a	self.assertRaises(TypeError, delattr, gen, '__qualname__')
101	n/a
102	n/a	# modify names of the function creating the generator
103	n/a	func.__qualname__ = "func_qualname"
104	n/a	func.__name__ = "func_name"
105	n/a	gen = func()
106	n/a	self.assertEqual(gen.__name__, "func_name")
107	n/a	self.assertEqual(gen.__qualname__, "func_qualname")
108	n/a
109	n/a	# unnamed generator
110	n/a	gen = (x for x in range(10))
111	n/a	self.assertEqual(gen.__name__,
112	n/a	"<genexpr>")
113	n/a	self.assertEqual(gen.__qualname__,
114	n/a	"GeneratorTest.test_name.<locals>.<genexpr>")
115	n/a
116	n/a	def test_copy(self):
117	n/a	def f():
118	n/a	yield 1
119	n/a	g = f()
120	n/a	with self.assertRaises(TypeError):
121	n/a	copy.copy(g)
122	n/a
123	n/a	def test_pickle(self):
124	n/a	def f():
125	n/a	yield 1
126	n/a	g = f()
127	n/a	for proto in range(pickle.HIGHEST_PROTOCOL + 1):
128	n/a	with self.assertRaises((TypeError, pickle.PicklingError)):
129	n/a	pickle.dumps(g, proto)
130	n/a
131	n/a
132	n/a	class ExceptionTest(unittest.TestCase):
133	n/a	# Tests for the issue #23353: check that the currently handled exception
134	n/a	# is correctly saved/restored in PyEval_EvalFrameEx().
135	n/a
136	n/a	def test_except_throw(self):
137	n/a	def store_raise_exc_generator():
138	n/a	try:
139	n/a	self.assertEqual(sys.exc_info()[0], None)
140	n/a	yield
141	n/a	except Exception as exc:
142	n/a	# exception raised by gen.throw(exc)
143	n/a	self.assertEqual(sys.exc_info()[0], ValueError)
144	n/a	self.assertIsNone(exc.__context__)
145	n/a	yield
146	n/a
147	n/a	# ensure that the exception is not lost
148	n/a	self.assertEqual(sys.exc_info()[0], ValueError)
149	n/a	yield
150	n/a
151	n/a	# we should be able to raise back the ValueError
152	n/a	raise
153	n/a
154	n/a	make = store_raise_exc_generator()
155	n/a	next(make)
156	n/a
157	n/a	try:
158	n/a	raise ValueError()
159	n/a	except Exception as exc:
160	n/a	try:
161	n/a	make.throw(exc)
162	n/a	except Exception:
163	n/a	pass
164	n/a
165	n/a	next(make)
166	n/a	with self.assertRaises(ValueError) as cm:
167	n/a	next(make)
168	n/a	self.assertIsNone(cm.exception.__context__)
169	n/a
170	n/a	self.assertEqual(sys.exc_info(), (None, None, None))
171	n/a
172	n/a	def test_except_next(self):
173	n/a	def gen():
174	n/a	self.assertEqual(sys.exc_info()[0], ValueError)
175	n/a	yield "done"
176	n/a
177	n/a	g = gen()
178	n/a	try:
179	n/a	raise ValueError
180	n/a	except Exception:
181	n/a	self.assertEqual(next(g), "done")
182	n/a	self.assertEqual(sys.exc_info(), (None, None, None))
183	n/a
184	n/a	def test_except_gen_except(self):
185	n/a	def gen():
186	n/a	try:
187	n/a	self.assertEqual(sys.exc_info()[0], None)
188	n/a	yield
189	n/a	# we are called from "except ValueError:", TypeError must
190	n/a	# inherit ValueError in its context
191	n/a	raise TypeError()
192	n/a	except TypeError as exc:
193	n/a	self.assertEqual(sys.exc_info()[0], TypeError)
194	n/a	self.assertEqual(type(exc.__context__), ValueError)
195	n/a	# here we are still called from the "except ValueError:"
196	n/a	self.assertEqual(sys.exc_info()[0], ValueError)
197	n/a	yield
198	n/a	self.assertIsNone(sys.exc_info()[0])
199	n/a	yield "done"
200	n/a
201	n/a	g = gen()
202	n/a	next(g)
203	n/a	try:
204	n/a	raise ValueError
205	n/a	except Exception:
206	n/a	next(g)
207	n/a
208	n/a	self.assertEqual(next(g), "done")
209	n/a	self.assertEqual(sys.exc_info(), (None, None, None))
210	n/a
211	n/a	def test_except_throw_exception_context(self):
212	n/a	def gen():
213	n/a	try:
214	n/a	try:
215	n/a	self.assertEqual(sys.exc_info()[0], None)
216	n/a	yield
217	n/a	except ValueError:
218	n/a	# we are called from "except ValueError:"
219	n/a	self.assertEqual(sys.exc_info()[0], ValueError)
220	n/a	raise TypeError()
221	n/a	except Exception as exc:
222	n/a	self.assertEqual(sys.exc_info()[0], TypeError)
223	n/a	self.assertEqual(type(exc.__context__), ValueError)
224	n/a	# we are still called from "except ValueError:"
225	n/a	self.assertEqual(sys.exc_info()[0], ValueError)
226	n/a	yield
227	n/a	self.assertIsNone(sys.exc_info()[0])
228	n/a	yield "done"
229	n/a
230	n/a	g = gen()
231	n/a	next(g)
232	n/a	try:
233	n/a	raise ValueError
234	n/a	except Exception as exc:
235	n/a	g.throw(exc)
236	n/a
237	n/a	self.assertEqual(next(g), "done")
238	n/a	self.assertEqual(sys.exc_info(), (None, None, None))
239	n/a
240	n/a	def test_stopiteration_warning(self):
241	n/a	# See also PEP 479.
242	n/a
243	n/a	def gen():
244	n/a	raise StopIteration
245	n/a	yield
246	n/a
247	n/a	with self.assertRaises(StopIteration), \
248	n/a	self.assertWarnsRegex(DeprecationWarning, "StopIteration"):
249	n/a
250	n/a	next(gen())
251	n/a
252	n/a	with self.assertRaisesRegex(DeprecationWarning,
253	n/a	"generator .* raised StopIteration"), \
254	n/a	warnings.catch_warnings():
255	n/a
256	n/a	warnings.simplefilter('error')
257	n/a	next(gen())
258	n/a
259	n/a
260	n/a	def test_tutorial_stopiteration(self):
261	n/a	# Raise StopIteration" stops the generator too:
262	n/a
263	n/a	def f():
264	n/a	yield 1
265	n/a	raise StopIteration
266	n/a	yield 2 # never reached
267	n/a
268	n/a	g = f()
269	n/a	self.assertEqual(next(g), 1)
270	n/a
271	n/a	with self.assertWarnsRegex(DeprecationWarning, "StopIteration"):
272	n/a	with self.assertRaises(StopIteration):
273	n/a	next(g)
274	n/a
275	n/a	with self.assertRaises(StopIteration):
276	n/a	# This time StopIteration isn't raised from the generator's body,
277	n/a	# hence no warning.
278	n/a	next(g)
279	n/a
280	n/a	def test_return_tuple(self):
281	n/a	def g():
282	n/a	return (yield 1)
283	n/a
284	n/a	gen = g()
285	n/a	self.assertEqual(next(gen), 1)
286	n/a	with self.assertRaises(StopIteration) as cm:
287	n/a	gen.send((2,))
288	n/a	self.assertEqual(cm.exception.value, (2,))
289	n/a
290	n/a	def test_return_stopiteration(self):
291	n/a	def g():
292	n/a	return (yield 1)
293	n/a
294	n/a	gen = g()
295	n/a	self.assertEqual(next(gen), 1)
296	n/a	with self.assertRaises(StopIteration) as cm:
297	n/a	gen.send(StopIteration(2))
298	n/a	self.assertIsInstance(cm.exception.value, StopIteration)
299	n/a	self.assertEqual(cm.exception.value.value, 2)
300	n/a
301	n/a
302	n/a	class YieldFromTests(unittest.TestCase):
303	n/a	def test_generator_gi_yieldfrom(self):
304	n/a	def a():
305	n/a	self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_RUNNING)
306	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
307	n/a	yield
308	n/a	self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_RUNNING)
309	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
310	n/a
311	n/a	def b():
312	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
313	n/a	yield from a()
314	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
315	n/a	yield
316	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
317	n/a
318	n/a	gen_b = b()
319	n/a	self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_CREATED)
320	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
321	n/a
322	n/a	gen_b.send(None)
323	n/a	self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_SUSPENDED)
324	n/a	self.assertEqual(gen_b.gi_yieldfrom.gi_code.co_name, 'a')
325	n/a
326	n/a	gen_b.send(None)
327	n/a	self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_SUSPENDED)
328	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
329	n/a
330	n/a	[] = gen_b # Exhaust generator
331	n/a	self.assertEqual(inspect.getgeneratorstate(gen_b), inspect.GEN_CLOSED)
332	n/a	self.assertIsNone(gen_b.gi_yieldfrom)
333	n/a
334	n/a
335	n/a	tutorial_tests = """
336	n/a	Let's try a simple generator:
337	n/a
338	n/a	>>> def f():
339	n/a	... yield 1
340	n/a	... yield 2
341	n/a
342	n/a	>>> for i in f():
343	n/a	... print(i)
344	n/a	1
345	n/a	2
346	n/a	>>> g = f()
347	n/a	>>> next(g)
348	n/a	1
349	n/a	>>> next(g)
350	n/a	2
351	n/a
352	n/a	"Falling off the end" stops the generator:
353	n/a
354	n/a	>>> next(g)
355	n/a	Traceback (most recent call last):
356	n/a	File "<stdin>", line 1, in ?
357	n/a	File "<stdin>", line 2, in g
358	n/a	StopIteration
359	n/a
360	n/a	"return" also stops the generator:
361	n/a
362	n/a	>>> def f():
363	n/a	... yield 1
364	n/a	... return
365	n/a	... yield 2 # never reached
366	n/a	...
367	n/a	>>> g = f()
368	n/a	>>> next(g)
369	n/a	1
370	n/a	>>> next(g)
371	n/a	Traceback (most recent call last):
372	n/a	File "<stdin>", line 1, in ?
373	n/a	File "<stdin>", line 3, in f
374	n/a	StopIteration
375	n/a	>>> next(g) # once stopped, can't be resumed
376	n/a	Traceback (most recent call last):
377	n/a	File "<stdin>", line 1, in ?
378	n/a	StopIteration
379	n/a
380	n/a	However, "return" and StopIteration are not exactly equivalent:
381	n/a
382	n/a	>>> def g1():
383	n/a	... try:
384	n/a	... return
385	n/a	... except:
386	n/a	... yield 1
387	n/a	...
388	n/a	>>> list(g1())
389	n/a	[]
390	n/a
391	n/a	>>> def g2():
392	n/a	... try:
393	n/a	... raise StopIteration
394	n/a	... except:
395	n/a	... yield 42
396	n/a	>>> print(list(g2()))
397	n/a	[42]
398	n/a
399	n/a	This may be surprising at first:
400	n/a
401	n/a	>>> def g3():
402	n/a	... try:
403	n/a	... return
404	n/a	... finally:
405	n/a	... yield 1
406	n/a	...
407	n/a	>>> list(g3())
408	n/a	[1]
409	n/a
410	n/a	Let's create an alternate range() function implemented as a generator:
411	n/a
412	n/a	>>> def yrange(n):
413	n/a	... for i in range(n):
414	n/a	... yield i
415	n/a	...
416	n/a	>>> list(yrange(5))
417	n/a	[0, 1, 2, 3, 4]
418	n/a
419	n/a	Generators always return to the most recent caller:
420	n/a
421	n/a	>>> def creator():
422	n/a	... r = yrange(5)
423	n/a	... print("creator", next(r))
424	n/a	... return r
425	n/a	...
426	n/a	>>> def caller():
427	n/a	... r = creator()
428	n/a	... for i in r:
429	n/a	... print("caller", i)
430	n/a	...
431	n/a	>>> caller()
432	n/a	creator 0
433	n/a	caller 1
434	n/a	caller 2
435	n/a	caller 3
436	n/a	caller 4
437	n/a
438	n/a	Generators can call other generators:
439	n/a
440	n/a	>>> def zrange(n):
441	n/a	... for i in yrange(n):
442	n/a	... yield i
443	n/a	...
444	n/a	>>> list(zrange(5))
445	n/a	[0, 1, 2, 3, 4]
446	n/a
447	n/a	"""
448	n/a
449	n/a	# The examples from PEP 255.
450	n/a
451	n/a	pep_tests = """
452	n/a
453	n/a	Specification: Yield
454	n/a
455	n/a	Restriction: A generator cannot be resumed while it is actively
456	n/a	running:
457	n/a
458	n/a	>>> def g():
459	n/a	... i = next(me)
460	n/a	... yield i
461	n/a	>>> me = g()
462	n/a	>>> next(me)
463	n/a	Traceback (most recent call last):
464	n/a	...
465	n/a	File "<string>", line 2, in g
466	n/a	ValueError: generator already executing
467	n/a
468	n/a	Specification: Return
469	n/a
470	n/a	Note that return isn't always equivalent to raising StopIteration: the
471	n/a	difference lies in how enclosing try/except constructs are treated.
472	n/a	For example,
473	n/a
474	n/a	>>> def f1():
475	n/a	... try:
476	n/a	... return
477	n/a	... except:
478	n/a	... yield 1
479	n/a	>>> print(list(f1()))
480	n/a	[]
481	n/a
482	n/a	because, as in any function, return simply exits, but
483	n/a
484	n/a	>>> def f2():
485	n/a	... try:
486	n/a	... raise StopIteration
487	n/a	... except:
488	n/a	... yield 42
489	n/a	>>> print(list(f2()))
490	n/a	[42]
491	n/a
492	n/a	because StopIteration is captured by a bare "except", as is any
493	n/a	exception.
494	n/a
495	n/a	Specification: Generators and Exception Propagation
496	n/a
497	n/a	>>> def f():
498	n/a	... return 1//0
499	n/a	>>> def g():
500	n/a	... yield f() # the zero division exception propagates
501	n/a	... yield 42 # and we'll never get here
502	n/a	>>> k = g()
503	n/a	>>> next(k)
504	n/a	Traceback (most recent call last):
505	n/a	File "<stdin>", line 1, in ?
506	n/a	File "<stdin>", line 2, in g
507	n/a	File "<stdin>", line 2, in f
508	n/a	ZeroDivisionError: integer division or modulo by zero
509	n/a	>>> next(k) # and the generator cannot be resumed
510	n/a	Traceback (most recent call last):
511	n/a	File "<stdin>", line 1, in ?
512	n/a	StopIteration
513	n/a	>>>
514	n/a
515	n/a	Specification: Try/Except/Finally
516	n/a
517	n/a	>>> def f():
518	n/a	... try:
519	n/a	... yield 1
520	n/a	... try:
521	n/a	... yield 2
522	n/a	... 1//0
523	n/a	... yield 3 # never get here
524	n/a	... except ZeroDivisionError:
525	n/a	... yield 4
526	n/a	... yield 5
527	n/a	... raise
528	n/a	... except:
529	n/a	... yield 6
530	n/a	... yield 7 # the "raise" above stops this
531	n/a	... except:
532	n/a	... yield 8
533	n/a	... yield 9
534	n/a	... try:
535	n/a	... x = 12
536	n/a	... finally:
537	n/a	... yield 10
538	n/a	... yield 11
539	n/a	>>> print(list(f()))
540	n/a	[1, 2, 4, 5, 8, 9, 10, 11]
541	n/a	>>>
542	n/a
543	n/a	Guido's binary tree example.
544	n/a
545	n/a	>>> # A binary tree class.
546	n/a	>>> class Tree:
547	n/a	...
548	n/a	... def __init__(self, label, left=None, right=None):
549	n/a	... self.label = label
550	n/a	... self.left = left
551	n/a	... self.right = right
552	n/a	...
553	n/a	... def __repr__(self, level=0, indent=" "):
554	n/a	... s = level*indent + repr(self.label)
555	n/a	... if self.left:
556	n/a	... s = s + "\\n" + self.left.__repr__(level+1, indent)
557	n/a	... if self.right:
558	n/a	... s = s + "\\n" + self.right.__repr__(level+1, indent)
559	n/a	... return s
560	n/a	...
561	n/a	... def __iter__(self):
562	n/a	... return inorder(self)
563	n/a
564	n/a	>>> # Create a Tree from a list.
565	n/a	>>> def tree(list):
566	n/a	... n = len(list)
567	n/a	... if n == 0:
568	n/a	... return []
569	n/a	... i = n // 2
570	n/a	... return Tree(list[i], tree(list[:i]), tree(list[i+1:]))
571	n/a
572	n/a	>>> # Show it off: create a tree.
573	n/a	>>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
574	n/a
575	n/a	>>> # A recursive generator that generates Tree labels in in-order.
576	n/a	>>> def inorder(t):
577	n/a	... if t:
578	n/a	... for x in inorder(t.left):
579	n/a	... yield x
580	n/a	... yield t.label
581	n/a	... for x in inorder(t.right):
582	n/a	... yield x
583	n/a
584	n/a	>>> # Show it off: create a tree.
585	n/a	>>> t = tree("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
586	n/a	>>> # Print the nodes of the tree in in-order.
587	n/a	>>> for x in t:
588	n/a	... print(' '+x, end='')
589	n/a	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
590	n/a
591	n/a	>>> # A non-recursive generator.
592	n/a	>>> def inorder(node):
593	n/a	... stack = []
594	n/a	... while node:
595	n/a	... while node.left:
596	n/a	... stack.append(node)
597	n/a	... node = node.left
598	n/a	... yield node.label
599	n/a	... while not node.right:
600	n/a	... try:
601	n/a	... node = stack.pop()
602	n/a	... except IndexError:
603	n/a	... return
604	n/a	... yield node.label
605	n/a	... node = node.right
606	n/a
607	n/a	>>> # Exercise the non-recursive generator.
608	n/a	>>> for x in t:
609	n/a	... print(' '+x, end='')
610	n/a	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
611	n/a
612	n/a	"""
613	n/a
614	n/a	# Examples from Iterator-List and Python-Dev and c.l.py.
615	n/a
616	n/a	email_tests = """
617	n/a
618	n/a	The difference between yielding None and returning it.
619	n/a
620	n/a	>>> def g():
621	n/a	... for i in range(3):
622	n/a	... yield None
623	n/a	... yield None
624	n/a	... return
625	n/a	>>> list(g())
626	n/a	[None, None, None, None]
627	n/a
628	n/a	Ensure that explicitly raising StopIteration acts like any other exception
629	n/a	in try/except, not like a return.
630	n/a
631	n/a	>>> def g():
632	n/a	... yield 1
633	n/a	... try:
634	n/a	... raise StopIteration
635	n/a	... except:
636	n/a	... yield 2
637	n/a	... yield 3
638	n/a	>>> list(g())
639	n/a	[1, 2, 3]
640	n/a
641	n/a	Next one was posted to c.l.py.
642	n/a
643	n/a	>>> def gcomb(x, k):
644	n/a	... "Generate all combinations of k elements from list x."
645	n/a	...
646	n/a	... if k > len(x):
647	n/a	... return
648	n/a	... if k == 0:
649	n/a	... yield []
650	n/a	... else:
651	n/a	... first, rest = x[0], x[1:]
652	n/a	... # A combination does or doesn't contain first.
653	n/a	... # If it does, the remainder is a k-1 comb of rest.
654	n/a	... for c in gcomb(rest, k-1):
655	n/a	... c.insert(0, first)
656	n/a	... yield c
657	n/a	... # If it doesn't contain first, it's a k comb of rest.
658	n/a	... for c in gcomb(rest, k):
659	n/a	... yield c
660	n/a
661	n/a	>>> seq = list(range(1, 5))
662	n/a	>>> for k in range(len(seq) + 2):
663	n/a	... print("%d-combs of %s:" % (k, seq))
664	n/a	... for c in gcomb(seq, k):
665	n/a	... print(" ", c)
666	n/a	0-combs of [1, 2, 3, 4]:
667	n/a	[]
668	n/a	1-combs of [1, 2, 3, 4]:
669	n/a	[1]
670	n/a	[2]
671	n/a	[3]
672	n/a	[4]
673	n/a	2-combs of [1, 2, 3, 4]:
674	n/a	[1, 2]
675	n/a	[1, 3]
676	n/a	[1, 4]
677	n/a	[2, 3]
678	n/a	[2, 4]
679	n/a	[3, 4]
680	n/a	3-combs of [1, 2, 3, 4]:
681	n/a	[1, 2, 3]
682	n/a	[1, 2, 4]
683	n/a	[1, 3, 4]
684	n/a	[2, 3, 4]
685	n/a	4-combs of [1, 2, 3, 4]:
686	n/a	[1, 2, 3, 4]
687	n/a	5-combs of [1, 2, 3, 4]:
688	n/a
689	n/a	From the Iterators list, about the types of these things.
690	n/a
691	n/a	>>> def g():
692	n/a	... yield 1
693	n/a	...
694	n/a	>>> type(g)
695	n/a	<class 'function'>
696	n/a	>>> i = g()
697	n/a	>>> type(i)
698	n/a	<class 'generator'>
699	n/a	>>> [s for s in dir(i) if not s.startswith('_')]
700	n/a	['close', 'gi_code', 'gi_frame', 'gi_running', 'gi_yieldfrom', 'send', 'throw']
701	n/a	>>> from test.support import HAVE_DOCSTRINGS
702	n/a	>>> print(i.__next__.__doc__ if HAVE_DOCSTRINGS else 'Implement next(self).')
703	n/a	Implement next(self).
704	n/a	>>> iter(i) is i
705	n/a	True
706	n/a	>>> import types
707	n/a	>>> isinstance(i, types.GeneratorType)
708	n/a	True
709	n/a
710	n/a	And more, added later.
711	n/a
712	n/a	>>> i.gi_running
713	n/a	0
714	n/a	>>> type(i.gi_frame)
715	n/a	<class 'frame'>
716	n/a	>>> i.gi_running = 42
717	n/a	Traceback (most recent call last):
718	n/a	...
719	n/a	AttributeError: readonly attribute
720	n/a	>>> def g():
721	n/a	... yield me.gi_running
722	n/a	>>> me = g()
723	n/a	>>> me.gi_running
724	n/a	0
725	n/a	>>> next(me)
726	n/a	1
727	n/a	>>> me.gi_running
728	n/a	0
729	n/a
730	n/a	A clever union-find implementation from c.l.py, due to David Eppstein.
731	n/a	Sent: Friday, June 29, 2001 12:16 PM
732	n/a	To: python-list@python.org
733	n/a	Subject: Re: PEP 255: Simple Generators
734	n/a
735	n/a	>>> class disjointSet:
736	n/a	... def __init__(self, name):
737	n/a	... self.name = name
738	n/a	... self.parent = None
739	n/a	... self.generator = self.generate()
740	n/a	...
741	n/a	... def generate(self):
742	n/a	... while not self.parent:
743	n/a	... yield self
744	n/a	... for x in self.parent.generator:
745	n/a	... yield x
746	n/a	...
747	n/a	... def find(self):
748	n/a	... return next(self.generator)
749	n/a	...
750	n/a	... def union(self, parent):
751	n/a	... if self.parent:
752	n/a	... raise ValueError("Sorry, I'm not a root!")
753	n/a	... self.parent = parent
754	n/a	...
755	n/a	... def __str__(self):
756	n/a	... return self.name
757	n/a
758	n/a	>>> names = "ABCDEFGHIJKLM"
759	n/a	>>> sets = [disjointSet(name) for name in names]
760	n/a	>>> roots = sets[:]
761	n/a
762	n/a	>>> import random
763	n/a	>>> gen = random.Random(42)
764	n/a	>>> while 1:
765	n/a	... for s in sets:
766	n/a	... print(" %s->%s" % (s, s.find()), end='')
767	n/a	... print()
768	n/a	... if len(roots) > 1:
769	n/a	... s1 = gen.choice(roots)
770	n/a	... roots.remove(s1)
771	n/a	... s2 = gen.choice(roots)
772	n/a	... s1.union(s2)
773	n/a	... print("merged", s1, "into", s2)
774	n/a	... else:
775	n/a	... break
776	n/a	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
777	n/a	merged K into B
778	n/a	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
779	n/a	merged A into F
780	n/a	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
781	n/a	merged E into F
782	n/a	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
783	n/a	merged D into C
784	n/a	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
785	n/a	merged M into C
786	n/a	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
787	n/a	merged J into B
788	n/a	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
789	n/a	merged B into C
790	n/a	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
791	n/a	merged F into G
792	n/a	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
793	n/a	merged L into C
794	n/a	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
795	n/a	merged G into I
796	n/a	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
797	n/a	merged I into H
798	n/a	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
799	n/a	merged C into H
800	n/a	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
801	n/a
802	n/a	"""
803	n/a	# Emacs turd '
804	n/a
805	n/a	# Fun tests (for sufficiently warped notions of "fun").
806	n/a
807	n/a	fun_tests = """
808	n/a
809	n/a	Build up to a recursive Sieve of Eratosthenes generator.
810	n/a
811	n/a	>>> def firstn(g, n):
812	n/a	... return [next(g) for i in range(n)]
813	n/a
814	n/a	>>> def intsfrom(i):
815	n/a	... while 1:
816	n/a	... yield i
817	n/a	... i += 1
818	n/a
819	n/a	>>> firstn(intsfrom(5), 7)
820	n/a	[5, 6, 7, 8, 9, 10, 11]
821	n/a
822	n/a	>>> def exclude_multiples(n, ints):
823	n/a	... for i in ints:
824	n/a	... if i % n:
825	n/a	... yield i
826	n/a
827	n/a	>>> firstn(exclude_multiples(3, intsfrom(1)), 6)
828	n/a	[1, 2, 4, 5, 7, 8]
829	n/a
830	n/a	>>> def sieve(ints):
831	n/a	... prime = next(ints)
832	n/a	... yield prime
833	n/a	... not_divisible_by_prime = exclude_multiples(prime, ints)
834	n/a	... for p in sieve(not_divisible_by_prime):
835	n/a	... yield p
836	n/a
837	n/a	>>> primes = sieve(intsfrom(2))
838	n/a	>>> firstn(primes, 20)
839	n/a	[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71]
840	n/a
841	n/a
842	n/a	Another famous problem: generate all integers of the form
843	n/a	2*i 3*j 5**k
844	n/a	in increasing order, where i,j,k >= 0. Trickier than it may look at first!
845	n/a	Try writing it without generators, and correctly, and without generating
846	n/a	3 internal results for each result output.
847	n/a
848	n/a	>>> def times(n, g):
849	n/a	... for i in g:
850	n/a	... yield n * i
851	n/a	>>> firstn(times(10, intsfrom(1)), 10)
852	n/a	[10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
853	n/a
854	n/a	>>> def merge(g, h):
855	n/a	... ng = next(g)
856	n/a	... nh = next(h)
857	n/a	... while 1:
858	n/a	... if ng < nh:
859	n/a	... yield ng
860	n/a	... ng = next(g)
861	n/a	... elif ng > nh:
862	n/a	... yield nh
863	n/a	... nh = next(h)
864	n/a	... else:
865	n/a	... yield ng
866	n/a	... ng = next(g)
867	n/a	... nh = next(h)
868	n/a
869	n/a	The following works, but is doing a whale of a lot of redundant work --
870	n/a	it's not clear how to get the internal uses of m235 to share a single
871	n/a	generator. Note that me_times2 (etc) each need to see every element in the
872	n/a	result sequence. So this is an example where lazy lists are more natural
873	n/a	(you can look at the head of a lazy list any number of times).
874	n/a
875	n/a	>>> def m235():
876	n/a	... yield 1
877	n/a	... me_times2 = times(2, m235())
878	n/a	... me_times3 = times(3, m235())
879	n/a	... me_times5 = times(5, m235())
880	n/a	... for i in merge(merge(me_times2,
881	n/a	... me_times3),
882	n/a	... me_times5):
883	n/a	... yield i
884	n/a
885	n/a	Don't print "too many" of these -- the implementation above is extremely
886	n/a	inefficient: each call of m235() leads to 3 recursive calls, and in
887	n/a	turn each of those 3 more, and so on, and so on, until we've descended
888	n/a	enough levels to satisfy the print stmts. Very odd: when I printed 5
889	n/a	lines of results below, this managed to screw up Win98's malloc in "the
890	n/a	usual" way, i.e. the heap grew over 4Mb so Win98 started fragmenting
891	n/a	address space, and it looked like a very slow leak.
892	n/a
893	n/a	>>> result = m235()
894	n/a	>>> for i in range(3):
895	n/a	... print(firstn(result, 15))
896	n/a	[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
897	n/a	[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
898	n/a	[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
899	n/a
900	n/a	Heh. Here's one way to get a shared list, complete with an excruciating
901	n/a	namespace renaming trick. The pretty part is that the times() and merge()
902	n/a	functions can be reused as-is, because they only assume their stream
903	n/a	arguments are iterable -- a LazyList is the same as a generator to times().
904	n/a
905	n/a	>>> class LazyList:
906	n/a	... def __init__(self, g):
907	n/a	... self.sofar = []
908	n/a	... self.fetch = g.__next__
909	n/a	...
910	n/a	... def __getitem__(self, i):
911	n/a	... sofar, fetch = self.sofar, self.fetch
912	n/a	... while i >= len(sofar):
913	n/a	... sofar.append(fetch())
914	n/a	... return sofar[i]
915	n/a
916	n/a	>>> def m235():
917	n/a	... yield 1
918	n/a	... # Gack: m235 below actually refers to a LazyList.
919	n/a	... me_times2 = times(2, m235)
920	n/a	... me_times3 = times(3, m235)
921	n/a	... me_times5 = times(5, m235)
922	n/a	... for i in merge(merge(me_times2,
923	n/a	... me_times3),
924	n/a	... me_times5):
925	n/a	... yield i
926	n/a
927	n/a	Print as many of these as you like -- this implementation is memory-
928	n/a	efficient.
929	n/a
930	n/a	>>> m235 = LazyList(m235())
931	n/a	>>> for i in range(5):
932	n/a	... print([m235[j] for j in range(15i, 15(i+1))])
933	n/a	[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
934	n/a	[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
935	n/a	[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
936	n/a	[200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
937	n/a	[400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
938	n/a
939	n/a	Ye olde Fibonacci generator, LazyList style.
940	n/a
941	n/a	>>> def fibgen(a, b):
942	n/a	...
943	n/a	... def sum(g, h):
944	n/a	... while 1:
945	n/a	... yield next(g) + next(h)
946	n/a	...
947	n/a	... def tail(g):
948	n/a	... next(g) # throw first away
949	n/a	... for x in g:
950	n/a	... yield x
951	n/a	...
952	n/a	... yield a
953	n/a	... yield b
954	n/a	... for s in sum(iter(fib),
955	n/a	... tail(iter(fib))):
956	n/a	... yield s
957	n/a
958	n/a	>>> fib = LazyList(fibgen(1, 2))
959	n/a	>>> firstn(iter(fib), 17)
960	n/a	[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
961	n/a
962	n/a
963	n/a	Running after your tail with itertools.tee (new in version 2.4)
964	n/a
965	n/a	The algorithms "m235" (Hamming) and Fibonacci presented above are both
966	n/a	examples of a whole family of FP (functional programming) algorithms
967	n/a	where a function produces and returns a list while the production algorithm
968	n/a	suppose the list as already produced by recursively calling itself.
969	n/a	For these algorithms to work, they must:
970	n/a
971	n/a	- produce at least a first element without presupposing the existence of
972	n/a	the rest of the list
973	n/a	- produce their elements in a lazy manner
974	n/a
975	n/a	To work efficiently, the beginning of the list must not be recomputed over
976	n/a	and over again. This is ensured in most FP languages as a built-in feature.
977	n/a	In python, we have to explicitly maintain a list of already computed results
978	n/a	and abandon genuine recursivity.
979	n/a
980	n/a	This is what had been attempted above with the LazyList class. One problem
981	n/a	with that class is that it keeps a list of all of the generated results and
982	n/a	therefore continually grows. This partially defeats the goal of the generator
983	n/a	concept, viz. produce the results only as needed instead of producing them
984	n/a	all and thereby wasting memory.
985	n/a
986	n/a	Thanks to itertools.tee, it is now clear "how to get the internal uses of
987	n/a	m235 to share a single generator".
988	n/a
989	n/a	>>> from itertools import tee
990	n/a	>>> def m235():
991	n/a	... def _m235():
992	n/a	... yield 1
993	n/a	... for n in merge(times(2, m2),
994	n/a	... merge(times(3, m3),
995	n/a	... times(5, m5))):
996	n/a	... yield n
997	n/a	... m1 = _m235()
998	n/a	... m2, m3, m5, mRes = tee(m1, 4)
999	n/a	... return mRes
1000	n/a
1001	n/a	>>> it = m235()
1002	n/a	>>> for i in range(5):
1003	n/a	... print(firstn(it, 15))
1004	n/a	[1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24]
1005	n/a	[25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80]
1006	n/a	[81, 90, 96, 100, 108, 120, 125, 128, 135, 144, 150, 160, 162, 180, 192]
1007	n/a	[200, 216, 225, 240, 243, 250, 256, 270, 288, 300, 320, 324, 360, 375, 384]
1008	n/a	[400, 405, 432, 450, 480, 486, 500, 512, 540, 576, 600, 625, 640, 648, 675]
1009	n/a
1010	n/a	The "tee" function does just what we want. It internally keeps a generated
1011	n/a	result for as long as it has not been "consumed" from all of the duplicated
1012	n/a	iterators, whereupon it is deleted. You can therefore print the hamming
1013	n/a	sequence during hours without increasing memory usage, or very little.
1014	n/a
1015	n/a	The beauty of it is that recursive running-after-their-tail FP algorithms
1016	n/a	are quite straightforwardly expressed with this Python idiom.
1017	n/a
1018	n/a	Ye olde Fibonacci generator, tee style.
1019	n/a
1020	n/a	>>> def fib():
1021	n/a	...
1022	n/a	... def _isum(g, h):
1023	n/a	... while 1:
1024	n/a	... yield next(g) + next(h)
1025	n/a	...
1026	n/a	... def _fib():
1027	n/a	... yield 1
1028	n/a	... yield 2
1029	n/a	... next(fibTail) # throw first away
1030	n/a	... for res in _isum(fibHead, fibTail):
1031	n/a	... yield res
1032	n/a	...
1033	n/a	... realfib = _fib()
1034	n/a	... fibHead, fibTail, fibRes = tee(realfib, 3)
1035	n/a	... return fibRes
1036	n/a
1037	n/a	>>> firstn(fib(), 17)
1038	n/a	[1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584]
1039	n/a
1040	n/a	"""
1041	n/a
1042	n/a	# syntax_tests mostly provokes SyntaxErrors. Also fiddling with #if 0
1043	n/a	# hackery.
1044	n/a
1045	n/a	syntax_tests = """
1046	n/a
1047	n/a	These are fine:
1048	n/a
1049	n/a	>>> def f():
1050	n/a	... yield 1
1051	n/a	... return
1052	n/a
1053	n/a	>>> def f():
1054	n/a	... try:
1055	n/a	... yield 1
1056	n/a	... finally:
1057	n/a	... pass
1058	n/a
1059	n/a	>>> def f():
1060	n/a	... try:
1061	n/a	... try:
1062	n/a	... 1//0
1063	n/a	... except ZeroDivisionError:
1064	n/a	... yield 666
1065	n/a	... except:
1066	n/a	... pass
1067	n/a	... finally:
1068	n/a	... pass
1069	n/a
1070	n/a	>>> def f():
1071	n/a	... try:
1072	n/a	... try:
1073	n/a	... yield 12
1074	n/a	... 1//0
1075	n/a	... except ZeroDivisionError:
1076	n/a	... yield 666
1077	n/a	... except:
1078	n/a	... try:
1079	n/a	... x = 12
1080	n/a	... finally:
1081	n/a	... yield 12
1082	n/a	... except:
1083	n/a	... return
1084	n/a	>>> list(f())
1085	n/a	[12, 666]
1086	n/a
1087	n/a	>>> def f():
1088	n/a	... yield
1089	n/a	>>> type(f())
1090	n/a	<class 'generator'>
1091	n/a
1092	n/a
1093	n/a	>>> def f():
1094	n/a	... if 0:
1095	n/a	... yield
1096	n/a	>>> type(f())
1097	n/a	<class 'generator'>
1098	n/a
1099	n/a
1100	n/a	>>> def f():
1101	n/a	... if 0:
1102	n/a	... yield 1
1103	n/a	>>> type(f())
1104	n/a	<class 'generator'>
1105	n/a
1106	n/a	>>> def f():
1107	n/a	... if "":
1108	n/a	... yield None
1109	n/a	>>> type(f())
1110	n/a	<class 'generator'>
1111	n/a
1112	n/a	>>> def f():
1113	n/a	... return
1114	n/a	... try:
1115	n/a	... if x==4:
1116	n/a	... pass
1117	n/a	... elif 0:
1118	n/a	... try:
1119	n/a	... 1//0
1120	n/a	... except SyntaxError:
1121	n/a	... pass
1122	n/a	... else:
1123	n/a	... if 0:
1124	n/a	... while 12:
1125	n/a	... x += 1
1126	n/a	... yield 2 # don't blink
1127	n/a	... f(a, b, c, d, e)
1128	n/a	... else:
1129	n/a	... pass
1130	n/a	... except:
1131	n/a	... x = 1
1132	n/a	... return
1133	n/a	>>> type(f())
1134	n/a	<class 'generator'>
1135	n/a
1136	n/a	>>> def f():
1137	n/a	... if 0:
1138	n/a	... def g():
1139	n/a	... yield 1
1140	n/a	...
1141	n/a	>>> type(f())
1142	n/a	<class 'NoneType'>
1143	n/a
1144	n/a	>>> def f():
1145	n/a	... if 0:
1146	n/a	... class C:
1147	n/a	... def __init__(self):
1148	n/a	... yield 1
1149	n/a	... def f(self):
1150	n/a	... yield 2
1151	n/a	>>> type(f())
1152	n/a	<class 'NoneType'>
1153	n/a
1154	n/a	>>> def f():
1155	n/a	... if 0:
1156	n/a	... return
1157	n/a	... if 0:
1158	n/a	... yield 2
1159	n/a	>>> type(f())
1160	n/a	<class 'generator'>
1161	n/a
1162	n/a	This one caused a crash (see SF bug 567538):
1163	n/a
1164	n/a	>>> def f():
1165	n/a	... for i in range(3):
1166	n/a	... try:
1167	n/a	... continue
1168	n/a	... finally:
1169	n/a	... yield i
1170	n/a	...
1171	n/a	>>> g = f()
1172	n/a	>>> print(next(g))
1173	n/a	0
1174	n/a	>>> print(next(g))
1175	n/a	1
1176	n/a	>>> print(next(g))
1177	n/a	2
1178	n/a	>>> print(next(g))
1179	n/a	Traceback (most recent call last):
1180	n/a	StopIteration
1181	n/a
1182	n/a
1183	n/a	Test the gi_code attribute
1184	n/a
1185	n/a	>>> def f():
1186	n/a	... yield 5
1187	n/a	...
1188	n/a	>>> g = f()
1189	n/a	>>> g.gi_code is f.__code__
1190	n/a	True
1191	n/a	>>> next(g)
1192	n/a	5
1193	n/a	>>> next(g)
1194	n/a	Traceback (most recent call last):
1195	n/a	StopIteration
1196	n/a	>>> g.gi_code is f.__code__
1197	n/a	True
1198	n/a
1199	n/a
1200	n/a	Test the __name__ attribute and the repr()
1201	n/a
1202	n/a	>>> def f():
1203	n/a	... yield 5
1204	n/a	...
1205	n/a	>>> g = f()
1206	n/a	>>> g.__name__
1207	n/a	'f'
1208	n/a	>>> repr(g) # doctest: +ELLIPSIS
1209	n/a	'<generator object f at ...>'
1210	n/a
1211	n/a	Lambdas shouldn't have their usual return behavior.
1212	n/a
1213	n/a	>>> x = lambda: (yield 1)
1214	n/a	>>> list(x())
1215	n/a	[1]
1216	n/a
1217	n/a	>>> x = lambda: ((yield 1), (yield 2))
1218	n/a	>>> list(x())
1219	n/a	[1, 2]
1220	n/a	"""
1221	n/a
1222	n/a	# conjoin is a simple backtracking generator, named in honor of Icon's
1223	n/a	# "conjunction" control structure. Pass a list of no-argument functions
1224	n/a	# that return iterable objects. Easiest to explain by example: assume the
1225	n/a	# function list [x, y, z] is passed. Then conjoin acts like:
1226	n/a	#
1227	n/a	# def g():
1228	n/a	# values = [None] * 3
1229	n/a	# for values[0] in x():
1230	n/a	# for values[1] in y():
1231	n/a	# for values[2] in z():
1232	n/a	# yield values
1233	n/a	#
1234	n/a	# So some 3-lists of values may be generated, each time we successfully
1235	n/a	# get into the innermost loop. If an iterator fails (is exhausted) before
1236	n/a	# then, it "backtracks" to get the next value from the nearest enclosing
1237	n/a	# iterator (the one "to the left"), and starts all over again at the next
1238	n/a	# slot (pumps a fresh iterator). Of course this is most useful when the
1239	n/a	# iterators have side-effects, so that which values can be generated at
1240	n/a	# each slot depend on the values iterated at previous slots.
1241	n/a
1242	n/a	def simple_conjoin(gs):
1243	n/a
1244	n/a	values = [None] * len(gs)
1245	n/a
1246	n/a	def gen(i):
1247	n/a	if i >= len(gs):
1248	n/a	yield values
1249	n/a	else:
1250	n/a	for values[i] in gs[i]():
1251	n/a	for x in gen(i+1):
1252	n/a	yield x
1253	n/a
1254	n/a	for x in gen(0):
1255	n/a	yield x
1256	n/a
1257	n/a	# That works fine, but recursing a level and checking i against len(gs) for
1258	n/a	# each item produced is inefficient. By doing manual loop unrolling across
1259	n/a	# generator boundaries, it's possible to eliminate most of that overhead.
1260	n/a	# This isn't worth the bother in general for generators, but conjoin() is
1261	n/a	# a core building block for some CPU-intensive generator applications.
1262	n/a
1263	n/a	def conjoin(gs):
1264	n/a
1265	n/a	n = len(gs)
1266	n/a	values = [None] * n
1267	n/a
1268	n/a	# Do one loop nest at time recursively, until the # of loop nests
1269	n/a	# remaining is divisible by 3.
1270	n/a
1271	n/a	def gen(i):
1272	n/a	if i >= n:
1273	n/a	yield values
1274	n/a
1275	n/a	elif (n-i) % 3:
1276	n/a	ip1 = i+1
1277	n/a	for values[i] in gs[i]():
1278	n/a	for x in gen(ip1):
1279	n/a	yield x
1280	n/a
1281	n/a	else:
1282	n/a	for x in _gen3(i):
1283	n/a	yield x
1284	n/a
1285	n/a	# Do three loop nests at a time, recursing only if at least three more
1286	n/a	# remain. Don't call directly: this is an internal optimization for
1287	n/a	# gen's use.
1288	n/a
1289	n/a	def _gen3(i):
1290	n/a	assert i < n and (n-i) % 3 == 0
1291	n/a	ip1, ip2, ip3 = i+1, i+2, i+3
1292	n/a	g, g1, g2 = gs[i : ip3]
1293	n/a
1294	n/a	if ip3 >= n:
1295	n/a	# These are the last three, so we can yield values directly.
1296	n/a	for values[i] in g():
1297	n/a	for values[ip1] in g1():
1298	n/a	for values[ip2] in g2():
1299	n/a	yield values
1300	n/a
1301	n/a	else:
1302	n/a	# At least 6 loop nests remain; peel off 3 and recurse for the
1303	n/a	# rest.
1304	n/a	for values[i] in g():
1305	n/a	for values[ip1] in g1():
1306	n/a	for values[ip2] in g2():
1307	n/a	for x in _gen3(ip3):
1308	n/a	yield x
1309	n/a
1310	n/a	for x in gen(0):
1311	n/a	yield x
1312	n/a
1313	n/a	# And one more approach: For backtracking apps like the Knight's Tour
1314	n/a	# solver below, the number of backtracking levels can be enormous (one
1315	n/a	# level per square, for the Knight's Tour, so that e.g. a 100x100 board
1316	n/a	# needs 10,000 levels). In such cases Python is likely to run out of
1317	n/a	# stack space due to recursion. So here's a recursion-free version of
1318	n/a	# conjoin too.
1319	n/a	# NOTE WELL: This allows large problems to be solved with only trivial
1320	n/a	# demands on stack space. Without explicitly resumable generators, this is
1321	n/a	# much harder to achieve. OTOH, this is much slower (up to a factor of 2)
1322	n/a	# than the fancy unrolled recursive conjoin.
1323	n/a
1324	n/a	def flat_conjoin(gs): # rename to conjoin to run tests with this instead
1325	n/a	n = len(gs)
1326	n/a	values = [None] * n
1327	n/a	iters = [None] * n
1328	n/a	_StopIteration = StopIteration # make local because caught a lot
1329	n/a	i = 0
1330	n/a	while 1:
1331	n/a	# Descend.
1332	n/a	try:
1333	n/a	while i < n:
1334	n/a	it = iters[i] = gs[i]().__next__
1335	n/a	values[i] = it()
1336	n/a	i += 1
1337	n/a	except _StopIteration:
1338	n/a	pass
1339	n/a	else:
1340	n/a	assert i == n
1341	n/a	yield values
1342	n/a
1343	n/a	# Backtrack until an older iterator can be resumed.
1344	n/a	i -= 1
1345	n/a	while i >= 0:
1346	n/a	try:
1347	n/a	values[i] = iters[i]()
1348	n/a	# Success! Start fresh at next level.
1349	n/a	i += 1
1350	n/a	break
1351	n/a	except _StopIteration:
1352	n/a	# Continue backtracking.
1353	n/a	i -= 1
1354	n/a	else:
1355	n/a	assert i < 0
1356	n/a	break
1357	n/a
1358	n/a	# A conjoin-based N-Queens solver.
1359	n/a
1360	n/a	class Queens:
1361	n/a	def __init__(self, n):
1362	n/a	self.n = n
1363	n/a	rangen = range(n)
1364	n/a
1365	n/a	# Assign a unique int to each column and diagonal.
1366	n/a	# columns: n of those, range(n).
1367	n/a	# NW-SE diagonals: 2n-1 of these, i-j unique and invariant along
1368	n/a	# each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0-
1369	n/a	# based.
1370	n/a	# NE-SW diagonals: 2n-1 of these, i+j unique and invariant along
1371	n/a	# each, smallest i+j is 0, largest is 2n-2.
1372	n/a
1373	n/a	# For each square, compute a bit vector of the columns and
1374	n/a	# diagonals it covers, and for each row compute a function that
1375	n/a	# generates the possibilities for the columns in that row.
1376	n/a	self.rowgenerators = []
1377	n/a	for i in rangen:
1378	n/a	rowuses = [(1 << j) \| # column ordinal
1379	n/a	(1 << (n + i-j + n-1)) \| # NW-SE ordinal
1380	n/a	(1 << (n + 2*n-1 + i+j)) # NE-SW ordinal
1381	n/a	for j in rangen]
1382	n/a
1383	n/a	def rowgen(rowuses=rowuses):
1384	n/a	for j in rangen:
1385	n/a	uses = rowuses[j]
1386	n/a	if uses & self.used == 0:
1387	n/a	self.used \|= uses
1388	n/a	yield j
1389	n/a	self.used &= ~uses
1390	n/a
1391	n/a	self.rowgenerators.append(rowgen)
1392	n/a
1393	n/a	# Generate solutions.
1394	n/a	def solve(self):
1395	n/a	self.used = 0
1396	n/a	for row2col in conjoin(self.rowgenerators):
1397	n/a	yield row2col
1398	n/a
1399	n/a	def printsolution(self, row2col):
1400	n/a	n = self.n
1401	n/a	assert n == len(row2col)
1402	n/a	sep = "+" + "-+" * n
1403	n/a	print(sep)
1404	n/a	for i in range(n):
1405	n/a	squares = [" " for j in range(n)]
1406	n/a	squares[row2col[i]] = "Q"
1407	n/a	print("\|" + "\|".join(squares) + "\|")
1408	n/a	print(sep)
1409	n/a
1410	n/a	# A conjoin-based Knight's Tour solver. This is pretty sophisticated
1411	n/a	# (e.g., when used with flat_conjoin above, and passing hard=1 to the
1412	n/a	# constructor, a 200x200 Knight's Tour was found quickly -- note that we're
1413	n/a	# creating 10s of thousands of generators then!), and is lengthy.
1414	n/a
1415	n/a	class Knights:
1416	n/a	def __init__(self, m, n, hard=0):
1417	n/a	self.m, self.n = m, n
1418	n/a
1419	n/a	# solve() will set up succs[i] to be a list of square #i's
1420	n/a	# successors.
1421	n/a	succs = self.succs = []
1422	n/a
1423	n/a	# Remove i0 from each of its successor's successor lists, i.e.
1424	n/a	# successors can't go back to i0 again. Return 0 if we can
1425	n/a	# detect this makes a solution impossible, else return 1.
1426	n/a
1427	n/a	def remove_from_successors(i0, len=len):
1428	n/a	# If we remove all exits from a free square, we're dead:
1429	n/a	# even if we move to it next, we can't leave it again.
1430	n/a	# If we create a square with one exit, we must visit it next;
1431	n/a	# else somebody else will have to visit it, and since there's
1432	n/a	# only one adjacent, there won't be a way to leave it again.
1433	n/a	# Finelly, if we create more than one free square with a
1434	n/a	# single exit, we can only move to one of them next, leaving
1435	n/a	# the other one a dead end.
1436	n/a	ne0 = ne1 = 0
1437	n/a	for i in succs[i0]:
1438	n/a	s = succs[i]
1439	n/a	s.remove(i0)
1440	n/a	e = len(s)
1441	n/a	if e == 0:
1442	n/a	ne0 += 1
1443	n/a	elif e == 1:
1444	n/a	ne1 += 1
1445	n/a	return ne0 == 0 and ne1 < 2
1446	n/a
1447	n/a	# Put i0 back in each of its successor's successor lists.
1448	n/a
1449	n/a	def add_to_successors(i0):
1450	n/a	for i in succs[i0]:
1451	n/a	succs[i].append(i0)
1452	n/a
1453	n/a	# Generate the first move.
1454	n/a	def first():
1455	n/a	if m < 1 or n < 1:
1456	n/a	return
1457	n/a
1458	n/a	# Since we're looking for a cycle, it doesn't matter where we
1459	n/a	# start. Starting in a corner makes the 2nd move easy.
1460	n/a	corner = self.coords2index(0, 0)
1461	n/a	remove_from_successors(corner)
1462	n/a	self.lastij = corner
1463	n/a	yield corner
1464	n/a	add_to_successors(corner)
1465	n/a
1466	n/a	# Generate the second moves.
1467	n/a	def second():
1468	n/a	corner = self.coords2index(0, 0)
1469	n/a	assert self.lastij == corner # i.e., we started in the corner
1470	n/a	if m < 3 or n < 3:
1471	n/a	return
1472	n/a	assert len(succs[corner]) == 2
1473	n/a	assert self.coords2index(1, 2) in succs[corner]
1474	n/a	assert self.coords2index(2, 1) in succs[corner]
1475	n/a	# Only two choices. Whichever we pick, the other must be the
1476	n/a	# square picked on move m*n, as it's the only way to get back
1477	n/a	# to (0, 0). Save its index in self.final so that moves before
1478	n/a	# the last know it must be kept free.
1479	n/a	for i, j in (1, 2), (2, 1):
1480	n/a	this = self.coords2index(i, j)
1481	n/a	final = self.coords2index(3-i, 3-j)
1482	n/a	self.final = final
1483	n/a
1484	n/a	remove_from_successors(this)
1485	n/a	succs[final].append(corner)
1486	n/a	self.lastij = this
1487	n/a	yield this
1488	n/a	succs[final].remove(corner)
1489	n/a	add_to_successors(this)
1490	n/a
1491	n/a	# Generate moves 3 thru m*n-1.
1492	n/a	def advance(len=len):
1493	n/a	# If some successor has only one exit, must take it.
1494	n/a	# Else favor successors with fewer exits.
1495	n/a	candidates = []
1496	n/a	for i in succs[self.lastij]:
1497	n/a	e = len(succs[i])
1498	n/a	assert e > 0, "else remove_from_successors() pruning flawed"
1499	n/a	if e == 1:
1500	n/a	candidates = [(e, i)]
1501	n/a	break
1502	n/a	candidates.append((e, i))
1503	n/a	else:
1504	n/a	candidates.sort()
1505	n/a
1506	n/a	for e, i in candidates:
1507	n/a	if i != self.final:
1508	n/a	if remove_from_successors(i):
1509	n/a	self.lastij = i
1510	n/a	yield i
1511	n/a	add_to_successors(i)
1512	n/a
1513	n/a	# Generate moves 3 thru m*n-1. Alternative version using a
1514	n/a	# stronger (but more expensive) heuristic to order successors.
1515	n/a	# Since the # of backtracking levels is m*n, a poor move early on
1516	n/a	# can take eons to undo. Smallest square board for which this
1517	n/a	# matters a lot is 52x52.
1518	n/a	def advance_hard(vmid=(m-1)/2.0, hmid=(n-1)/2.0, len=len):
1519	n/a	# If some successor has only one exit, must take it.
1520	n/a	# Else favor successors with fewer exits.
1521	n/a	# Break ties via max distance from board centerpoint (favor
1522	n/a	# corners and edges whenever possible).
1523	n/a	candidates = []
1524	n/a	for i in succs[self.lastij]:
1525	n/a	e = len(succs[i])
1526	n/a	assert e > 0, "else remove_from_successors() pruning flawed"
1527	n/a	if e == 1:
1528	n/a	candidates = [(e, 0, i)]
1529	n/a	break
1530	n/a	i1, j1 = self.index2coords(i)
1531	n/a	d = (i1 - vmid)2 + (j1 - hmid)2
1532	n/a	candidates.append((e, -d, i))
1533	n/a	else:
1534	n/a	candidates.sort()
1535	n/a
1536	n/a	for e, d, i in candidates:
1537	n/a	if i != self.final:
1538	n/a	if remove_from_successors(i):
1539	n/a	self.lastij = i
1540	n/a	yield i
1541	n/a	add_to_successors(i)
1542	n/a
1543	n/a	# Generate the last move.
1544	n/a	def last():
1545	n/a	assert self.final in succs[self.lastij]
1546	n/a	yield self.final
1547	n/a
1548	n/a	if m*n < 4:
1549	n/a	self.squaregenerators = [first]
1550	n/a	else:
1551	n/a	self.squaregenerators = [first, second] + \
1552	n/a	[hard and advance_hard or advance] * (m*n - 3) + \
1553	n/a	[last]
1554	n/a
1555	n/a	def coords2index(self, i, j):
1556	n/a	assert 0 <= i < self.m
1557	n/a	assert 0 <= j < self.n
1558	n/a	return i * self.n + j
1559	n/a
1560	n/a	def index2coords(self, index):
1561	n/a	assert 0 <= index < self.m * self.n
1562	n/a	return divmod(index, self.n)
1563	n/a
1564	n/a	def _init_board(self):
1565	n/a	succs = self.succs
1566	n/a	del succs[:]
1567	n/a	m, n = self.m, self.n
1568	n/a	c2i = self.coords2index
1569	n/a
1570	n/a	offsets = [( 1, 2), ( 2, 1), ( 2, -1), ( 1, -2),
1571	n/a	(-1, -2), (-2, -1), (-2, 1), (-1, 2)]
1572	n/a	rangen = range(n)
1573	n/a	for i in range(m):
1574	n/a	for j in rangen:
1575	n/a	s = [c2i(i+io, j+jo) for io, jo in offsets
1576	n/a	if 0 <= i+io < m and
1577	n/a	0 <= j+jo < n]
1578	n/a	succs.append(s)
1579	n/a
1580	n/a	# Generate solutions.
1581	n/a	def solve(self):
1582	n/a	self._init_board()
1583	n/a	for x in conjoin(self.squaregenerators):
1584	n/a	yield x
1585	n/a
1586	n/a	def printsolution(self, x):
1587	n/a	m, n = self.m, self.n
1588	n/a	assert len(x) == m*n
1589	n/a	w = len(str(m*n))
1590	n/a	format = "%" + str(w) + "d"
1591	n/a
1592	n/a	squares = [[None] * n for i in range(m)]
1593	n/a	k = 1
1594	n/a	for i in x:
1595	n/a	i1, j1 = self.index2coords(i)
1596	n/a	squares[i1][j1] = format % k
1597	n/a	k += 1
1598	n/a
1599	n/a	sep = "+" + ("-" * w + "+") * n
1600	n/a	print(sep)
1601	n/a	for i in range(m):
1602	n/a	row = squares[i]
1603	n/a	print("\|" + "\|".join(row) + "\|")
1604	n/a	print(sep)
1605	n/a
1606	n/a	conjoin_tests = """
1607	n/a
1608	n/a	Generate the 3-bit binary numbers in order. This illustrates dumbest-
1609	n/a	possible use of conjoin, just to generate the full cross-product.
1610	n/a
1611	n/a	>>> for c in conjoin([lambda: iter((0, 1))] * 3):
1612	n/a	... print(c)
1613	n/a	[0, 0, 0]
1614	n/a	[0, 0, 1]
1615	n/a	[0, 1, 0]
1616	n/a	[0, 1, 1]
1617	n/a	[1, 0, 0]
1618	n/a	[1, 0, 1]
1619	n/a	[1, 1, 0]
1620	n/a	[1, 1, 1]
1621	n/a
1622	n/a	For efficiency in typical backtracking apps, conjoin() yields the same list
1623	n/a	object each time. So if you want to save away a full account of its
1624	n/a	generated sequence, you need to copy its results.
1625	n/a
1626	n/a	>>> def gencopy(iterator):
1627	n/a	... for x in iterator:
1628	n/a	... yield x[:]
1629	n/a
1630	n/a	>>> for n in range(10):
1631	n/a	... all = list(gencopy(conjoin([lambda: iter((0, 1))] * n)))
1632	n/a	... print(n, len(all), all[0] == [0] * n, all[-1] == [1] * n)
1633	n/a	0 1 True True
1634	n/a	1 2 True True
1635	n/a	2 4 True True
1636	n/a	3 8 True True
1637	n/a	4 16 True True
1638	n/a	5 32 True True
1639	n/a	6 64 True True
1640	n/a	7 128 True True
1641	n/a	8 256 True True
1642	n/a	9 512 True True
1643	n/a
1644	n/a	And run an 8-queens solver.
1645	n/a
1646	n/a	>>> q = Queens(8)
1647	n/a	>>> LIMIT = 2
1648	n/a	>>> count = 0
1649	n/a	>>> for row2col in q.solve():
1650	n/a	... count += 1
1651	n/a	... if count <= LIMIT:
1652	n/a	... print("Solution", count)
1653	n/a	... q.printsolution(row2col)
1654	n/a	Solution 1
1655	n/a	+-+-+-+-+-+-+-+-+
1656	n/a	\|Q\| \| \| \| \| \| \| \|
1657	n/a	+-+-+-+-+-+-+-+-+
1658	n/a	\| \| \| \| \|Q\| \| \| \|
1659	n/a	+-+-+-+-+-+-+-+-+
1660	n/a	\| \| \| \| \| \| \| \|Q\|
1661	n/a	+-+-+-+-+-+-+-+-+
1662	n/a	\| \| \| \| \| \|Q\| \| \|
1663	n/a	+-+-+-+-+-+-+-+-+
1664	n/a	\| \| \|Q\| \| \| \| \| \|
1665	n/a	+-+-+-+-+-+-+-+-+
1666	n/a	\| \| \| \| \| \| \|Q\| \|
1667	n/a	+-+-+-+-+-+-+-+-+
1668	n/a	\| \|Q\| \| \| \| \| \| \|
1669	n/a	+-+-+-+-+-+-+-+-+
1670	n/a	\| \| \| \|Q\| \| \| \| \|
1671	n/a	+-+-+-+-+-+-+-+-+
1672	n/a	Solution 2
1673	n/a	+-+-+-+-+-+-+-+-+
1674	n/a	\|Q\| \| \| \| \| \| \| \|
1675	n/a	+-+-+-+-+-+-+-+-+
1676	n/a	\| \| \| \| \| \|Q\| \| \|
1677	n/a	+-+-+-+-+-+-+-+-+
1678	n/a	\| \| \| \| \| \| \| \|Q\|
1679	n/a	+-+-+-+-+-+-+-+-+
1680	n/a	\| \| \|Q\| \| \| \| \| \|
1681	n/a	+-+-+-+-+-+-+-+-+
1682	n/a	\| \| \| \| \| \| \|Q\| \|
1683	n/a	+-+-+-+-+-+-+-+-+
1684	n/a	\| \| \| \|Q\| \| \| \| \|
1685	n/a	+-+-+-+-+-+-+-+-+
1686	n/a	\| \|Q\| \| \| \| \| \| \|
1687	n/a	+-+-+-+-+-+-+-+-+
1688	n/a	\| \| \| \| \|Q\| \| \| \|
1689	n/a	+-+-+-+-+-+-+-+-+
1690	n/a
1691	n/a	>>> print(count, "solutions in all.")
1692	n/a	92 solutions in all.
1693	n/a
1694	n/a	And run a Knight's Tour on a 10x10 board. Note that there are about
1695	n/a	20,000 solutions even on a 6x6 board, so don't dare run this to exhaustion.
1696	n/a
1697	n/a	>>> k = Knights(10, 10)
1698	n/a	>>> LIMIT = 2
1699	n/a	>>> count = 0
1700	n/a	>>> for x in k.solve():
1701	n/a	... count += 1
1702	n/a	... if count <= LIMIT:
1703	n/a	... print("Solution", count)
1704	n/a	... k.printsolution(x)
1705	n/a	... else:
1706	n/a	... break
1707	n/a	Solution 1
1708	n/a	+---+---+---+---+---+---+---+---+---+---+
1709	n/a	\| 1\| 58\| 27\| 34\| 3\| 40\| 29\| 10\| 5\| 8\|
1710	n/a	+---+---+---+---+---+---+---+---+---+---+
1711	n/a	\| 26\| 35\| 2\| 57\| 28\| 33\| 4\| 7\| 30\| 11\|
1712	n/a	+---+---+---+---+---+---+---+---+---+---+
1713	n/a	\| 59\|100\| 73\| 36\| 41\| 56\| 39\| 32\| 9\| 6\|
1714	n/a	+---+---+---+---+---+---+---+---+---+---+
1715	n/a	\| 74\| 25\| 60\| 55\| 72\| 37\| 42\| 49\| 12\| 31\|
1716	n/a	+---+---+---+---+---+---+---+---+---+---+
1717	n/a	\| 61\| 86\| 99\| 76\| 63\| 52\| 47\| 38\| 43\| 50\|
1718	n/a	+---+---+---+---+---+---+---+---+---+---+
1719	n/a	\| 24\| 75\| 62\| 85\| 54\| 71\| 64\| 51\| 48\| 13\|
1720	n/a	+---+---+---+---+---+---+---+---+---+---+
1721	n/a	\| 87\| 98\| 91\| 80\| 77\| 84\| 53\| 46\| 65\| 44\|
1722	n/a	+---+---+---+---+---+---+---+---+---+---+
1723	n/a	\| 90\| 23\| 88\| 95\| 70\| 79\| 68\| 83\| 14\| 17\|
1724	n/a	+---+---+---+---+---+---+---+---+---+---+
1725	n/a	\| 97\| 92\| 21\| 78\| 81\| 94\| 19\| 16\| 45\| 66\|
1726	n/a	+---+---+---+---+---+---+---+---+---+---+
1727	n/a	\| 22\| 89\| 96\| 93\| 20\| 69\| 82\| 67\| 18\| 15\|
1728	n/a	+---+---+---+---+---+---+---+---+---+---+
1729	n/a	Solution 2
1730	n/a	+---+---+---+---+---+---+---+---+---+---+
1731	n/a	\| 1\| 58\| 27\| 34\| 3\| 40\| 29\| 10\| 5\| 8\|
1732	n/a	+---+---+---+---+---+---+---+---+---+---+
1733	n/a	\| 26\| 35\| 2\| 57\| 28\| 33\| 4\| 7\| 30\| 11\|
1734	n/a	+---+---+---+---+---+---+---+---+---+---+
1735	n/a	\| 59\|100\| 73\| 36\| 41\| 56\| 39\| 32\| 9\| 6\|
1736	n/a	+---+---+---+---+---+---+---+---+---+---+
1737	n/a	\| 74\| 25\| 60\| 55\| 72\| 37\| 42\| 49\| 12\| 31\|
1738	n/a	+---+---+---+---+---+---+---+---+---+---+
1739	n/a	\| 61\| 86\| 99\| 76\| 63\| 52\| 47\| 38\| 43\| 50\|
1740	n/a	+---+---+---+---+---+---+---+---+---+---+
1741	n/a	\| 24\| 75\| 62\| 85\| 54\| 71\| 64\| 51\| 48\| 13\|
1742	n/a	+---+---+---+---+---+---+---+---+---+---+
1743	n/a	\| 87\| 98\| 89\| 80\| 77\| 84\| 53\| 46\| 65\| 44\|
1744	n/a	+---+---+---+---+---+---+---+---+---+---+
1745	n/a	\| 90\| 23\| 92\| 95\| 70\| 79\| 68\| 83\| 14\| 17\|
1746	n/a	+---+---+---+---+---+---+---+---+---+---+
1747	n/a	\| 97\| 88\| 21\| 78\| 81\| 94\| 19\| 16\| 45\| 66\|
1748	n/a	+---+---+---+---+---+---+---+---+---+---+
1749	n/a	\| 22\| 91\| 96\| 93\| 20\| 69\| 82\| 67\| 18\| 15\|
1750	n/a	+---+---+---+---+---+---+---+---+---+---+
1751	n/a	"""
1752	n/a
1753	n/a	weakref_tests = """\
1754	n/a	Generators are weakly referencable:
1755	n/a
1756	n/a	>>> import weakref
1757	n/a	>>> def gen():
1758	n/a	... yield 'foo!'
1759	n/a	...
1760	n/a	>>> wr = weakref.ref(gen)
1761	n/a	>>> wr() is gen
1762	n/a	True
1763	n/a	>>> p = weakref.proxy(gen)
1764	n/a
1765	n/a	Generator-iterators are weakly referencable as well:
1766	n/a
1767	n/a	>>> gi = gen()
1768	n/a	>>> wr = weakref.ref(gi)
1769	n/a	>>> wr() is gi
1770	n/a	True
1771	n/a	>>> p = weakref.proxy(gi)
1772	n/a	>>> list(p)
1773	n/a	['foo!']
1774	n/a
1775	n/a	"""
1776	n/a
1777	n/a	coroutine_tests = """\
1778	n/a	Sending a value into a started generator:
1779	n/a
1780	n/a	>>> def f():
1781	n/a	... print((yield 1))
1782	n/a	... yield 2
1783	n/a	>>> g = f()
1784	n/a	>>> next(g)
1785	n/a	1
1786	n/a	>>> g.send(42)
1787	n/a	42
1788	n/a	2
1789	n/a
1790	n/a	Sending a value into a new generator produces a TypeError:
1791	n/a
1792	n/a	>>> f().send("foo")
1793	n/a	Traceback (most recent call last):
1794	n/a	...
1795	n/a	TypeError: can't send non-None value to a just-started generator
1796	n/a
1797	n/a
1798	n/a	Yield by itself yields None:
1799	n/a
1800	n/a	>>> def f(): yield
1801	n/a	>>> list(f())
1802	n/a	[None]
1803	n/a
1804	n/a
1805	n/a
1806	n/a	An obscene abuse of a yield expression within a generator expression:
1807	n/a
1808	n/a	>>> list((yield 21) for i in range(4))
1809	n/a	[21, None, 21, None, 21, None, 21, None]
1810	n/a
1811	n/a	And a more sane, but still weird usage:
1812	n/a
1813	n/a	>>> def f(): list(i for i in [(yield 26)])
1814	n/a	>>> type(f())
1815	n/a	<class 'generator'>
1816	n/a
1817	n/a
1818	n/a	A yield expression with augmented assignment.
1819	n/a
1820	n/a	>>> def coroutine(seq):
1821	n/a	... count = 0
1822	n/a	... while count < 200:
1823	n/a	... count += yield
1824	n/a	... seq.append(count)
1825	n/a	>>> seq = []
1826	n/a	>>> c = coroutine(seq)
1827	n/a	>>> next(c)
1828	n/a	>>> print(seq)
1829	n/a	[]
1830	n/a	>>> c.send(10)
1831	n/a	>>> print(seq)
1832	n/a	[10]
1833	n/a	>>> c.send(10)
1834	n/a	>>> print(seq)
1835	n/a	[10, 20]
1836	n/a	>>> c.send(10)
1837	n/a	>>> print(seq)
1838	n/a	[10, 20, 30]
1839	n/a
1840	n/a
1841	n/a	Check some syntax errors for yield expressions:
1842	n/a
1843	n/a	>>> f=lambda: (yield 1),(yield 2)
1844	n/a	Traceback (most recent call last):
1845	n/a	...
1846	n/a	SyntaxError: 'yield' outside function
1847	n/a
1848	n/a	>>> def f(): x = yield = y
1849	n/a	Traceback (most recent call last):
1850	n/a	...
1851	n/a	SyntaxError: assignment to yield expression not possible
1852	n/a
1853	n/a	>>> def f(): (yield bar) = y
1854	n/a	Traceback (most recent call last):
1855	n/a	...
1856	n/a	SyntaxError: can't assign to yield expression
1857	n/a
1858	n/a	>>> def f(): (yield bar) += y
1859	n/a	Traceback (most recent call last):
1860	n/a	...
1861	n/a	SyntaxError: can't assign to yield expression
1862	n/a
1863	n/a
1864	n/a	Now check some throw() conditions:
1865	n/a
1866	n/a	>>> def f():
1867	n/a	... while True:
1868	n/a	... try:
1869	n/a	... print((yield))
1870	n/a	... except ValueError as v:
1871	n/a	... print("caught ValueError (%s)" % (v))
1872	n/a	>>> import sys
1873	n/a	>>> g = f()
1874	n/a	>>> next(g)
1875	n/a
1876	n/a	>>> g.throw(ValueError) # type only
1877	n/a	caught ValueError ()
1878	n/a
1879	n/a	>>> g.throw(ValueError("xyz")) # value only
1880	n/a	caught ValueError (xyz)
1881	n/a
1882	n/a	>>> g.throw(ValueError, ValueError(1)) # value+matching type
1883	n/a	caught ValueError (1)
1884	n/a
1885	n/a	>>> g.throw(ValueError, TypeError(1)) # mismatched type, rewrapped
1886	n/a	caught ValueError (1)
1887	n/a
1888	n/a	>>> g.throw(ValueError, ValueError(1), None) # explicit None traceback
1889	n/a	caught ValueError (1)
1890	n/a
1891	n/a	>>> g.throw(ValueError(1), "foo") # bad args
1892	n/a	Traceback (most recent call last):
1893	n/a	...
1894	n/a	TypeError: instance exception may not have a separate value
1895	n/a
1896	n/a	>>> g.throw(ValueError, "foo", 23) # bad args
1897	n/a	Traceback (most recent call last):
1898	n/a	...
1899	n/a	TypeError: throw() third argument must be a traceback object
1900	n/a
1901	n/a	>>> g.throw("abc")
1902	n/a	Traceback (most recent call last):
1903	n/a	...
1904	n/a	TypeError: exceptions must be classes or instances deriving from BaseException, not str
1905	n/a
1906	n/a	>>> g.throw(0)
1907	n/a	Traceback (most recent call last):
1908	n/a	...
1909	n/a	TypeError: exceptions must be classes or instances deriving from BaseException, not int
1910	n/a
1911	n/a	>>> g.throw(list)
1912	n/a	Traceback (most recent call last):
1913	n/a	...
1914	n/a	TypeError: exceptions must be classes or instances deriving from BaseException, not type
1915	n/a
1916	n/a	>>> def throw(g,exc):
1917	n/a	... try:
1918	n/a	... raise exc
1919	n/a	... except:
1920	n/a	... g.throw(*sys.exc_info())
1921	n/a	>>> throw(g,ValueError) # do it with traceback included
1922	n/a	caught ValueError ()
1923	n/a
1924	n/a	>>> g.send(1)
1925	n/a	1
1926	n/a
1927	n/a	>>> throw(g,TypeError) # terminate the generator
1928	n/a	Traceback (most recent call last):
1929	n/a	...
1930	n/a	TypeError
1931	n/a
1932	n/a	>>> print(g.gi_frame)
1933	n/a	None
1934	n/a
1935	n/a	>>> g.send(2)
1936	n/a	Traceback (most recent call last):
1937	n/a	...
1938	n/a	StopIteration
1939	n/a
1940	n/a	>>> g.throw(ValueError,6) # throw on closed generator
1941	n/a	Traceback (most recent call last):
1942	n/a	...
1943	n/a	ValueError: 6
1944	n/a
1945	n/a	>>> f().throw(ValueError,7) # throw on just-opened generator
1946	n/a	Traceback (most recent call last):
1947	n/a	...
1948	n/a	ValueError: 7
1949	n/a
1950	n/a	Plain "raise" inside a generator should preserve the traceback (#13188).
1951	n/a	The traceback should have 3 levels:
1952	n/a	- g.throw()
1953	n/a	- f()
1954	n/a	- 1/0
1955	n/a
1956	n/a	>>> def f():
1957	n/a	... try:
1958	n/a	... yield
1959	n/a	... except:
1960	n/a	... raise
1961	n/a	>>> g = f()
1962	n/a	>>> try:
1963	n/a	... 1/0
1964	n/a	... except ZeroDivisionError as v:
1965	n/a	... try:
1966	n/a	... g.throw(v)
1967	n/a	... except Exception as w:
1968	n/a	... tb = w.__traceback__
1969	n/a	>>> levels = 0
1970	n/a	>>> while tb:
1971	n/a	... levels += 1
1972	n/a	... tb = tb.tb_next
1973	n/a	>>> levels
1974	n/a	3
1975	n/a
1976	n/a	Now let's try closing a generator:
1977	n/a
1978	n/a	>>> def f():
1979	n/a	... try: yield
1980	n/a	... except GeneratorExit:
1981	n/a	... print("exiting")
1982	n/a
1983	n/a	>>> g = f()
1984	n/a	>>> next(g)
1985	n/a	>>> g.close()
1986	n/a	exiting
1987	n/a	>>> g.close() # should be no-op now
1988	n/a
1989	n/a	>>> f().close() # close on just-opened generator should be fine
1990	n/a
1991	n/a	>>> def f(): yield # an even simpler generator
1992	n/a	>>> f().close() # close before opening
1993	n/a	>>> g = f()
1994	n/a	>>> next(g)
1995	n/a	>>> g.close() # close normally
1996	n/a
1997	n/a	And finalization:
1998	n/a
1999	n/a	>>> def f():
2000	n/a	... try: yield
2001	n/a	... finally:
2002	n/a	... print("exiting")
2003	n/a
2004	n/a	>>> g = f()
2005	n/a	>>> next(g)
2006	n/a	>>> del g
2007	n/a	exiting
2008	n/a
2009	n/a
2010	n/a	GeneratorExit is not caught by except Exception:
2011	n/a
2012	n/a	>>> def f():
2013	n/a	... try: yield
2014	n/a	... except Exception:
2015	n/a	... print('except')
2016	n/a	... finally:
2017	n/a	... print('finally')
2018	n/a
2019	n/a	>>> g = f()
2020	n/a	>>> next(g)
2021	n/a	>>> del g
2022	n/a	finally
2023	n/a
2024	n/a
2025	n/a	Now let's try some ill-behaved generators:
2026	n/a
2027	n/a	>>> def f():
2028	n/a	... try: yield
2029	n/a	... except GeneratorExit:
2030	n/a	... yield "foo!"
2031	n/a	>>> g = f()
2032	n/a	>>> next(g)
2033	n/a	>>> g.close()
2034	n/a	Traceback (most recent call last):
2035	n/a	...
2036	n/a	RuntimeError: generator ignored GeneratorExit
2037	n/a	>>> g.close()
2038	n/a
2039	n/a
2040	n/a	Our ill-behaved code should be invoked during GC:
2041	n/a
2042	n/a	>>> import sys, io
2043	n/a	>>> old, sys.stderr = sys.stderr, io.StringIO()
2044	n/a	>>> g = f()
2045	n/a	>>> next(g)
2046	n/a	>>> del g
2047	n/a	>>> "RuntimeError: generator ignored GeneratorExit" in sys.stderr.getvalue()
2048	n/a	True
2049	n/a	>>> sys.stderr = old
2050	n/a
2051	n/a
2052	n/a	And errors thrown during closing should propagate:
2053	n/a
2054	n/a	>>> def f():
2055	n/a	... try: yield
2056	n/a	... except GeneratorExit:
2057	n/a	... raise TypeError("fie!")
2058	n/a	>>> g = f()
2059	n/a	>>> next(g)
2060	n/a	>>> g.close()
2061	n/a	Traceback (most recent call last):
2062	n/a	...
2063	n/a	TypeError: fie!
2064	n/a
2065	n/a
2066	n/a	Ensure that various yield expression constructs make their
2067	n/a	enclosing function a generator:
2068	n/a
2069	n/a	>>> def f(): x += yield
2070	n/a	>>> type(f())
2071	n/a	<class 'generator'>
2072	n/a
2073	n/a	>>> def f(): x = yield
2074	n/a	>>> type(f())
2075	n/a	<class 'generator'>
2076	n/a
2077	n/a	>>> def f(): lambda x=(yield): 1
2078	n/a	>>> type(f())
2079	n/a	<class 'generator'>
2080	n/a
2081	n/a	>>> def f(): x=(i for i in (yield) if (yield))
2082	n/a	>>> type(f())
2083	n/a	<class 'generator'>
2084	n/a
2085	n/a	>>> def f(d): d[(yield "a")] = d[(yield "b")] = 27
2086	n/a	>>> data = [1,2]
2087	n/a	>>> g = f(data)
2088	n/a	>>> type(g)
2089	n/a	<class 'generator'>
2090	n/a	>>> g.send(None)
2091	n/a	'a'
2092	n/a	>>> data
2093	n/a	[1, 2]
2094	n/a	>>> g.send(0)
2095	n/a	'b'
2096	n/a	>>> data
2097	n/a	[27, 2]
2098	n/a	>>> try: g.send(1)
2099	n/a	... except StopIteration: pass
2100	n/a	>>> data
2101	n/a	[27, 27]
2102	n/a
2103	n/a	"""
2104	n/a
2105	n/a	refleaks_tests = """
2106	n/a	Prior to adding cycle-GC support to itertools.tee, this code would leak
2107	n/a	references. We add it to the standard suite so the routine refleak-tests
2108	n/a	would trigger if it starts being uncleanable again.
2109	n/a
2110	n/a	>>> import itertools
2111	n/a	>>> def leak():
2112	n/a	... class gen:
2113	n/a	... def __iter__(self):
2114	n/a	... return self
2115	n/a	... def __next__(self):
2116	n/a	... return self.item
2117	n/a	... g = gen()
2118	n/a	... head, tail = itertools.tee(g)
2119	n/a	... g.item = head
2120	n/a	... return head
2121	n/a	>>> it = leak()
2122	n/a
2123	n/a	Make sure to also test the involvement of the tee-internal teedataobject,
2124	n/a	which stores returned items.
2125	n/a
2126	n/a	>>> item = next(it)
2127	n/a
2128	n/a
2129	n/a
2130	n/a	This test leaked at one point due to generator finalization/destruction.
2131	n/a	It was copied from Lib/test/leakers/test_generator_cycle.py before the file
2132	n/a	was removed.
2133	n/a
2134	n/a	>>> def leak():
2135	n/a	... def gen():
2136	n/a	... while True:
2137	n/a	... yield g
2138	n/a	... g = gen()
2139	n/a
2140	n/a	>>> leak()
2141	n/a
2142	n/a
2143	n/a
2144	n/a	This test isn't really generator related, but rather exception-in-cleanup
2145	n/a	related. The coroutine tests (above) just happen to cause an exception in
2146	n/a	the generator's __del__ (tp_del) method. We can also test for this
2147	n/a	explicitly, without generators. We do have to redirect stderr to avoid
2148	n/a	printing warnings and to doublecheck that we actually tested what we wanted
2149	n/a	to test.
2150	n/a
2151	n/a	>>> import sys, io
2152	n/a	>>> old = sys.stderr
2153	n/a	>>> try:
2154	n/a	... sys.stderr = io.StringIO()
2155	n/a	... class Leaker:
2156	n/a	... def __del__(self):
2157	n/a	... def invoke(message):
2158	n/a	... raise RuntimeError(message)
2159	n/a	... invoke("test")
2160	n/a	...
2161	n/a	... l = Leaker()
2162	n/a	... del l
2163	n/a	... err = sys.stderr.getvalue().strip()
2164	n/a	... "Exception ignored in" in err
2165	n/a	... "RuntimeError: test" in err
2166	n/a	... "Traceback" in err
2167	n/a	... "in invoke" in err
2168	n/a	... finally:
2169	n/a	... sys.stderr = old
2170	n/a	True
2171	n/a	True
2172	n/a	True
2173	n/a	True
2174	n/a
2175	n/a
2176	n/a	These refleak tests should perhaps be in a testfile of their own,
2177	n/a	test_generators just happened to be the test that drew these out.
2178	n/a
2179	n/a	"""
2180	n/a
2181	n/a	__test__ = {"tut": tutorial_tests,
2182	n/a	"pep": pep_tests,
2183	n/a	"email": email_tests,
2184	n/a	"fun": fun_tests,
2185	n/a	"syntax": syntax_tests,
2186	n/a	"conjoin": conjoin_tests,
2187	n/a	"weakref": weakref_tests,
2188	n/a	"coroutine": coroutine_tests,
2189	n/a	"refleaks": refleaks_tests,
2190	n/a	}
2191	n/a
2192	n/a	# Magic test name that regrtest.py invokes after importing this module.
2193	n/a	# This worms around a bootstrap problem.
2194	n/a	# Note that doctest and regrtest both look in sys.argv for a "-v" argument,
2195	n/a	# so this works as expected in both ways of running regrtest.
2196	n/a	def test_main(verbose=None):
2197	n/a	from test import support, test_generators
2198	n/a	support.run_unittest(__name__)
2199	n/a	support.run_doctest(test_generators, verbose)
2200	n/a
2201	n/a	# This part isn't needed for regrtest, but for running the test directly.
2202	n/a	if __name__ == "__main__":
2203	n/a	test_main(1)