Line data Source code
1 : #define PY_SSIZE_T_CLEAN
2 : #include "Python.h"
3 : #include "pycore_call.h" // _PyObject_CallNoArgs()
4 : #include "pycore_long.h" // _PyLong_GetZero()
5 : #include "pycore_object.h" // _PyObject_GC_TRACK()
6 : #include "pycore_tuple.h" // _PyTuple_ITEMS()
7 : #include <stddef.h> // offsetof()
8 :
9 : /* Itertools module written and maintained
10 : by Raymond D. Hettinger <python@rcn.com>
11 : */
12 :
13 : /*[clinic input]
14 : module itertools
15 : class itertools.groupby "groupbyobject *" "&groupby_type"
16 : class itertools._grouper "_grouperobject *" "&_grouper_type"
17 : class itertools.teedataobject "teedataobject *" "&teedataobject_type"
18 : class itertools._tee "teeobject *" "&tee_type"
19 : class itertools.cycle "cycleobject *" "&cycle_type"
20 : class itertools.dropwhile "dropwhileobject *" "&dropwhile_type"
21 : class itertools.takewhile "takewhileobject *" "&takewhile_type"
22 : class itertools.starmap "starmapobject *" "&starmap_type"
23 : class itertools.chain "chainobject *" "&chain_type"
24 : class itertools.combinations "combinationsobject *" "&combinations_type"
25 : class itertools.combinations_with_replacement "cwr_object *" "&cwr_type"
26 : class itertools.permutations "permutationsobject *" "&permutations_type"
27 : class itertools.accumulate "accumulateobject *" "&accumulate_type"
28 : class itertools.compress "compressobject *" "&compress_type"
29 : class itertools.filterfalse "filterfalseobject *" "&filterfalse_type"
30 : class itertools.count "countobject *" "&count_type"
31 : class itertools.pairwise "pairwiseobject *" "&pairwise_type"
32 : [clinic start generated code]*/
33 : /*[clinic end generated code: output=da39a3ee5e6b4b0d input=6498ed21fbe1bf94]*/
34 :
35 : static PyTypeObject groupby_type;
36 : static PyTypeObject _grouper_type;
37 : static PyTypeObject teedataobject_type;
38 : static PyTypeObject tee_type;
39 : static PyTypeObject cycle_type;
40 : static PyTypeObject dropwhile_type;
41 : static PyTypeObject takewhile_type;
42 : static PyTypeObject starmap_type;
43 : static PyTypeObject combinations_type;
44 : static PyTypeObject cwr_type;
45 : static PyTypeObject permutations_type;
46 : static PyTypeObject accumulate_type;
47 : static PyTypeObject compress_type;
48 : static PyTypeObject filterfalse_type;
49 : static PyTypeObject count_type;
50 : static PyTypeObject pairwise_type;
51 :
52 : #include "clinic/itertoolsmodule.c.h"
53 :
54 : /* pairwise object ***********************************************************/
55 :
56 : typedef struct {
57 : PyObject_HEAD
58 : PyObject *it;
59 : PyObject *old;
60 : } pairwiseobject;
61 :
62 : /*[clinic input]
63 : @classmethod
64 : itertools.pairwise.__new__ as pairwise_new
65 : iterable: object
66 : /
67 : Return an iterator of overlapping pairs taken from the input iterator.
68 :
69 : s -> (s0,s1), (s1,s2), (s2, s3), ...
70 :
71 : [clinic start generated code]*/
72 :
73 : static PyObject *
74 52 : pairwise_new_impl(PyTypeObject *type, PyObject *iterable)
75 : /*[clinic end generated code: output=9f0267062d384456 input=6e7c3cddb431a8d6]*/
76 : {
77 : PyObject *it;
78 : pairwiseobject *po;
79 :
80 52 : it = PyObject_GetIter(iterable);
81 52 : if (it == NULL) {
82 11 : return NULL;
83 : }
84 41 : po = (pairwiseobject *)type->tp_alloc(type, 0);
85 41 : if (po == NULL) {
86 0 : Py_DECREF(it);
87 0 : return NULL;
88 : }
89 41 : po->it = it;
90 41 : po->old = NULL;
91 41 : return (PyObject *)po;
92 : }
93 :
94 : static void
95 41 : pairwise_dealloc(pairwiseobject *po)
96 : {
97 41 : PyObject_GC_UnTrack(po);
98 41 : Py_XDECREF(po->it);
99 41 : Py_XDECREF(po->old);
100 41 : Py_TYPE(po)->tp_free(po);
101 41 : }
102 :
103 : static int
104 8 : pairwise_traverse(pairwiseobject *po, visitproc visit, void *arg)
105 : {
106 8 : Py_VISIT(po->it);
107 8 : Py_VISIT(po->old);
108 8 : return 0;
109 : }
110 :
111 : static PyObject *
112 15250 : pairwise_next(pairwiseobject *po)
113 : {
114 15250 : PyObject *it = po->it;
115 15250 : PyObject *old = po->old;
116 : PyObject *new, *result;
117 :
118 15250 : if (it == NULL) {
119 0 : return NULL;
120 : }
121 15250 : if (old == NULL) {
122 41 : po->old = old = (*Py_TYPE(it)->tp_iternext)(it);
123 41 : if (old == NULL) {
124 16 : Py_CLEAR(po->it);
125 16 : return NULL;
126 : }
127 : }
128 15234 : new = (*Py_TYPE(it)->tp_iternext)(it);
129 15234 : if (new == NULL) {
130 24 : Py_CLEAR(po->it);
131 24 : Py_CLEAR(po->old);
132 24 : return NULL;
133 : }
134 : /* Future optimization: Reuse the result tuple as we do in enumerate() */
135 15210 : result = PyTuple_Pack(2, old, new);
136 15210 : Py_SETREF(po->old, new);
137 15210 : return result;
138 : }
139 :
140 : static PyTypeObject pairwise_type = {
141 : PyVarObject_HEAD_INIT(&PyType_Type, 0)
142 : "itertools.pairwise", /* tp_name */
143 : sizeof(pairwiseobject), /* tp_basicsize */
144 : 0, /* tp_itemsize */
145 : /* methods */
146 : (destructor)pairwise_dealloc, /* tp_dealloc */
147 : 0, /* tp_vectorcall_offset */
148 : 0, /* tp_getattr */
149 : 0, /* tp_setattr */
150 : 0, /* tp_as_async */
151 : 0, /* tp_repr */
152 : 0, /* tp_as_number */
153 : 0, /* tp_as_sequence */
154 : 0, /* tp_as_mapping */
155 : 0, /* tp_hash */
156 : 0, /* tp_call */
157 : 0, /* tp_str */
158 : PyObject_GenericGetAttr, /* tp_getattro */
159 : 0, /* tp_setattro */
160 : 0, /* tp_as_buffer */
161 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
162 : Py_TPFLAGS_BASETYPE, /* tp_flags */
163 : pairwise_new__doc__, /* tp_doc */
164 : (traverseproc)pairwise_traverse, /* tp_traverse */
165 : 0, /* tp_clear */
166 : 0, /* tp_richcompare */
167 : 0, /* tp_weaklistoffset */
168 : PyObject_SelfIter, /* tp_iter */
169 : (iternextfunc)pairwise_next, /* tp_iternext */
170 : 0, /* tp_methods */
171 : 0, /* tp_members */
172 : 0, /* tp_getset */
173 : 0, /* tp_base */
174 : 0, /* tp_dict */
175 : 0, /* tp_descr_get */
176 : 0, /* tp_descr_set */
177 : 0, /* tp_dictoffset */
178 : 0, /* tp_init */
179 : PyType_GenericAlloc, /* tp_alloc */
180 : pairwise_new, /* tp_new */
181 : PyObject_GC_Del, /* tp_free */
182 : };
183 :
184 :
185 : /* groupby object ************************************************************/
186 :
187 : typedef struct {
188 : PyObject_HEAD
189 : PyObject *it;
190 : PyObject *keyfunc;
191 : PyObject *tgtkey;
192 : PyObject *currkey;
193 : PyObject *currvalue;
194 : const void *currgrouper; /* borrowed reference */
195 : } groupbyobject;
196 :
197 : static PyObject *_grouper_create(groupbyobject *, PyObject *);
198 :
199 : /*[clinic input]
200 : @classmethod
201 : itertools.groupby.__new__
202 :
203 : iterable as it: object
204 : Elements to divide into groups according to the key function.
205 : key as keyfunc: object = None
206 : A function for computing the group category for each element.
207 : If the key function is not specified or is None, the element itself
208 : is used for grouping.
209 :
210 : make an iterator that returns consecutive keys and groups from the iterable
211 : [clinic start generated code]*/
212 :
213 : static PyObject *
214 3253 : itertools_groupby_impl(PyTypeObject *type, PyObject *it, PyObject *keyfunc)
215 : /*[clinic end generated code: output=cbb1ae3a90fd4141 input=6b3d123e87ff65a1]*/
216 : {
217 : groupbyobject *gbo;
218 :
219 3253 : gbo = (groupbyobject *)type->tp_alloc(type, 0);
220 3253 : if (gbo == NULL)
221 0 : return NULL;
222 3253 : gbo->tgtkey = NULL;
223 3253 : gbo->currkey = NULL;
224 3253 : gbo->currvalue = NULL;
225 3253 : gbo->keyfunc = keyfunc;
226 3253 : Py_INCREF(keyfunc);
227 3253 : gbo->it = PyObject_GetIter(it);
228 3253 : if (gbo->it == NULL) {
229 31 : Py_DECREF(gbo);
230 31 : return NULL;
231 : }
232 3222 : return (PyObject *)gbo;
233 : }
234 :
235 : static void
236 3253 : groupby_dealloc(groupbyobject *gbo)
237 : {
238 3253 : PyObject_GC_UnTrack(gbo);
239 3253 : Py_XDECREF(gbo->it);
240 3253 : Py_XDECREF(gbo->keyfunc);
241 3253 : Py_XDECREF(gbo->tgtkey);
242 3253 : Py_XDECREF(gbo->currkey);
243 3253 : Py_XDECREF(gbo->currvalue);
244 3253 : Py_TYPE(gbo)->tp_free(gbo);
245 3253 : }
246 :
247 : static int
248 8 : groupby_traverse(groupbyobject *gbo, visitproc visit, void *arg)
249 : {
250 8 : Py_VISIT(gbo->it);
251 8 : Py_VISIT(gbo->keyfunc);
252 8 : Py_VISIT(gbo->tgtkey);
253 8 : Py_VISIT(gbo->currkey);
254 8 : Py_VISIT(gbo->currvalue);
255 8 : return 0;
256 : }
257 :
258 : Py_LOCAL_INLINE(int)
259 254136 : groupby_step(groupbyobject *gbo)
260 : {
261 : PyObject *newvalue, *newkey, *oldvalue;
262 :
263 254136 : newvalue = PyIter_Next(gbo->it);
264 254136 : if (newvalue == NULL)
265 3871 : return -1;
266 :
267 250265 : if (gbo->keyfunc == Py_None) {
268 18572 : newkey = newvalue;
269 18572 : Py_INCREF(newvalue);
270 : } else {
271 231693 : newkey = PyObject_CallOneArg(gbo->keyfunc, newvalue);
272 231693 : if (newkey == NULL) {
273 3 : Py_DECREF(newvalue);
274 3 : return -1;
275 : }
276 : }
277 :
278 250262 : oldvalue = gbo->currvalue;
279 250262 : gbo->currvalue = newvalue;
280 250262 : Py_XSETREF(gbo->currkey, newkey);
281 250262 : Py_XDECREF(oldvalue);
282 250262 : return 0;
283 : }
284 :
285 : static PyObject *
286 119538 : groupby_next(groupbyobject *gbo)
287 : {
288 : PyObject *r, *grouper;
289 :
290 119538 : gbo->currgrouper = NULL;
291 : /* skip to next iteration group */
292 : for (;;) {
293 138908 : if (gbo->currkey == NULL)
294 : /* pass */;
295 135029 : else if (gbo->tgtkey == NULL)
296 3112 : break;
297 : else {
298 : int rcmp;
299 :
300 131917 : rcmp = PyObject_RichCompareBool(gbo->tgtkey, gbo->currkey, Py_EQ);
301 131917 : if (rcmp == -1)
302 1 : return NULL;
303 131916 : else if (rcmp == 0)
304 113284 : break;
305 : }
306 :
307 22511 : if (groupby_step(gbo) < 0)
308 3141 : return NULL;
309 : }
310 116396 : Py_INCREF(gbo->currkey);
311 116396 : Py_XSETREF(gbo->tgtkey, gbo->currkey);
312 :
313 116396 : grouper = _grouper_create(gbo, gbo->tgtkey);
314 116396 : if (grouper == NULL)
315 0 : return NULL;
316 :
317 116396 : r = PyTuple_Pack(2, gbo->currkey, grouper);
318 116396 : Py_DECREF(grouper);
319 116396 : return r;
320 : }
321 :
322 : static PyObject *
323 60 : groupby_reduce(groupbyobject *lz, PyObject *Py_UNUSED(ignored))
324 : {
325 : /* reduce as a 'new' call with an optional 'setstate' if groupby
326 : * has started
327 : */
328 : PyObject *value;
329 60 : if (lz->tgtkey && lz->currkey && lz->currvalue)
330 24 : value = Py_BuildValue("O(OO)(OOO)", Py_TYPE(lz),
331 : lz->it, lz->keyfunc, lz->currkey, lz->currvalue, lz->tgtkey);
332 : else
333 36 : value = Py_BuildValue("O(OO)", Py_TYPE(lz),
334 : lz->it, lz->keyfunc);
335 :
336 60 : return value;
337 : }
338 :
339 : PyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
340 :
341 : static PyObject *
342 24 : groupby_setstate(groupbyobject *lz, PyObject *state)
343 : {
344 : PyObject *currkey, *currvalue, *tgtkey;
345 24 : if (!PyTuple_Check(state)) {
346 0 : PyErr_SetString(PyExc_TypeError, "state is not a tuple");
347 0 : return NULL;
348 : }
349 24 : if (!PyArg_ParseTuple(state, "OOO", &currkey, &currvalue, &tgtkey)) {
350 0 : return NULL;
351 : }
352 24 : Py_INCREF(currkey);
353 24 : Py_XSETREF(lz->currkey, currkey);
354 24 : Py_INCREF(currvalue);
355 24 : Py_XSETREF(lz->currvalue, currvalue);
356 24 : Py_INCREF(tgtkey);
357 24 : Py_XSETREF(lz->tgtkey, tgtkey);
358 24 : Py_RETURN_NONE;
359 : }
360 :
361 : PyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
362 :
363 : static PyMethodDef groupby_methods[] = {
364 : {"__reduce__", (PyCFunction)groupby_reduce, METH_NOARGS,
365 : reduce_doc},
366 : {"__setstate__", (PyCFunction)groupby_setstate, METH_O,
367 : setstate_doc},
368 : {NULL, NULL} /* sentinel */
369 : };
370 :
371 : static PyTypeObject groupby_type = {
372 : PyVarObject_HEAD_INIT(NULL, 0)
373 : "itertools.groupby", /* tp_name */
374 : sizeof(groupbyobject), /* tp_basicsize */
375 : 0, /* tp_itemsize */
376 : /* methods */
377 : (destructor)groupby_dealloc, /* tp_dealloc */
378 : 0, /* tp_vectorcall_offset */
379 : 0, /* tp_getattr */
380 : 0, /* tp_setattr */
381 : 0, /* tp_as_async */
382 : 0, /* tp_repr */
383 : 0, /* tp_as_number */
384 : 0, /* tp_as_sequence */
385 : 0, /* tp_as_mapping */
386 : 0, /* tp_hash */
387 : 0, /* tp_call */
388 : 0, /* tp_str */
389 : PyObject_GenericGetAttr, /* tp_getattro */
390 : 0, /* tp_setattro */
391 : 0, /* tp_as_buffer */
392 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
393 : Py_TPFLAGS_BASETYPE, /* tp_flags */
394 : itertools_groupby__doc__, /* tp_doc */
395 : (traverseproc)groupby_traverse, /* tp_traverse */
396 : 0, /* tp_clear */
397 : 0, /* tp_richcompare */
398 : 0, /* tp_weaklistoffset */
399 : PyObject_SelfIter, /* tp_iter */
400 : (iternextfunc)groupby_next, /* tp_iternext */
401 : groupby_methods, /* tp_methods */
402 : 0, /* tp_members */
403 : 0, /* tp_getset */
404 : 0, /* tp_base */
405 : 0, /* tp_dict */
406 : 0, /* tp_descr_get */
407 : 0, /* tp_descr_set */
408 : 0, /* tp_dictoffset */
409 : 0, /* tp_init */
410 : 0, /* tp_alloc */
411 : itertools_groupby, /* tp_new */
412 : PyObject_GC_Del, /* tp_free */
413 : };
414 :
415 :
416 : /* _grouper object (internal) ************************************************/
417 :
418 : typedef struct {
419 : PyObject_HEAD
420 : PyObject *parent;
421 : PyObject *tgtkey;
422 : } _grouperobject;
423 :
424 : /*[clinic input]
425 : @classmethod
426 : itertools._grouper.__new__
427 :
428 : parent: object(subclass_of='&groupby_type')
429 : tgtkey: object
430 : /
431 : [clinic start generated code]*/
432 :
433 : static PyObject *
434 24 : itertools__grouper_impl(PyTypeObject *type, PyObject *parent,
435 : PyObject *tgtkey)
436 : /*[clinic end generated code: output=462efb1cdebb5914 input=dc180d7771fc8c59]*/
437 : {
438 24 : return _grouper_create((groupbyobject*) parent, tgtkey);
439 : }
440 :
441 : static PyObject *
442 116420 : _grouper_create(groupbyobject *parent, PyObject *tgtkey)
443 : {
444 : _grouperobject *igo;
445 :
446 116420 : igo = PyObject_GC_New(_grouperobject, &_grouper_type);
447 116420 : if (igo == NULL)
448 0 : return NULL;
449 116420 : igo->parent = (PyObject *)parent;
450 116420 : Py_INCREF(parent);
451 116420 : igo->tgtkey = tgtkey;
452 116420 : Py_INCREF(tgtkey);
453 116420 : parent->currgrouper = igo; /* borrowed reference */
454 :
455 116420 : PyObject_GC_Track(igo);
456 116420 : return (PyObject *)igo;
457 : }
458 :
459 : static void
460 116420 : _grouper_dealloc(_grouperobject *igo)
461 : {
462 116420 : PyObject_GC_UnTrack(igo);
463 116420 : Py_DECREF(igo->parent);
464 116420 : Py_DECREF(igo->tgtkey);
465 116420 : PyObject_GC_Del(igo);
466 116420 : }
467 :
468 : static int
469 116444 : _grouper_traverse(_grouperobject *igo, visitproc visit, void *arg)
470 : {
471 116444 : Py_VISIT(igo->parent);
472 116444 : Py_VISIT(igo->tgtkey);
473 116444 : return 0;
474 : }
475 :
476 : static PyObject *
477 335581 : _grouper_next(_grouperobject *igo)
478 : {
479 335581 : groupbyobject *gbo = (groupbyobject *)igo->parent;
480 : PyObject *r;
481 : int rcmp;
482 :
483 335581 : if (gbo->currgrouper != igo)
484 3 : return NULL;
485 335578 : if (gbo->currvalue == NULL) {
486 231625 : if (groupby_step(gbo) < 0)
487 733 : return NULL;
488 : }
489 :
490 334845 : assert(gbo->currkey != NULL);
491 334845 : rcmp = PyObject_RichCompareBool(igo->tgtkey, gbo->currkey, Py_EQ);
492 334845 : if (rcmp <= 0)
493 : /* got any error or current group is end */
494 103218 : return NULL;
495 :
496 231627 : r = gbo->currvalue;
497 231627 : gbo->currvalue = NULL;
498 231627 : Py_CLEAR(gbo->currkey);
499 :
500 231627 : return r;
501 : }
502 :
503 : static PyObject *
504 30 : _grouper_reduce(_grouperobject *lz, PyObject *Py_UNUSED(ignored))
505 : {
506 30 : if (((groupbyobject *)lz->parent)->currgrouper != lz) {
507 6 : return Py_BuildValue("N(())", _PyEval_GetBuiltin(&_Py_ID(iter)));
508 : }
509 24 : return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->parent, lz->tgtkey);
510 : }
511 :
512 : static PyMethodDef _grouper_methods[] = {
513 : {"__reduce__", (PyCFunction)_grouper_reduce, METH_NOARGS,
514 : reduce_doc},
515 : {NULL, NULL} /* sentinel */
516 : };
517 :
518 :
519 : static PyTypeObject _grouper_type = {
520 : PyVarObject_HEAD_INIT(NULL, 0)
521 : "itertools._grouper", /* tp_name */
522 : sizeof(_grouperobject), /* tp_basicsize */
523 : 0, /* tp_itemsize */
524 : /* methods */
525 : (destructor)_grouper_dealloc, /* tp_dealloc */
526 : 0, /* tp_vectorcall_offset */
527 : 0, /* tp_getattr */
528 : 0, /* tp_setattr */
529 : 0, /* tp_as_async */
530 : 0, /* tp_repr */
531 : 0, /* tp_as_number */
532 : 0, /* tp_as_sequence */
533 : 0, /* tp_as_mapping */
534 : 0, /* tp_hash */
535 : 0, /* tp_call */
536 : 0, /* tp_str */
537 : PyObject_GenericGetAttr, /* tp_getattro */
538 : 0, /* tp_setattro */
539 : 0, /* tp_as_buffer */
540 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
541 : 0, /* tp_doc */
542 : (traverseproc)_grouper_traverse, /* tp_traverse */
543 : 0, /* tp_clear */
544 : 0, /* tp_richcompare */
545 : 0, /* tp_weaklistoffset */
546 : PyObject_SelfIter, /* tp_iter */
547 : (iternextfunc)_grouper_next, /* tp_iternext */
548 : _grouper_methods, /* tp_methods */
549 : 0, /* tp_members */
550 : 0, /* tp_getset */
551 : 0, /* tp_base */
552 : 0, /* tp_dict */
553 : 0, /* tp_descr_get */
554 : 0, /* tp_descr_set */
555 : 0, /* tp_dictoffset */
556 : 0, /* tp_init */
557 : 0, /* tp_alloc */
558 : itertools__grouper, /* tp_new */
559 : PyObject_GC_Del, /* tp_free */
560 : };
561 :
562 :
563 : /* tee object and with supporting function and objects ***********************/
564 :
565 : /* The teedataobject pre-allocates space for LINKCELLS number of objects.
566 : To help the object fit neatly inside cache lines (space for 16 to 32
567 : pointers), the value should be a multiple of 16 minus space for
568 : the other structure members including PyHEAD overhead. The larger the
569 : value, the less memory overhead per object and the less time spent
570 : allocating/deallocating new links. The smaller the number, the less
571 : wasted space and the more rapid freeing of older data.
572 : */
573 : #define LINKCELLS 57
574 :
575 : typedef struct {
576 : PyObject_HEAD
577 : PyObject *it;
578 : int numread; /* 0 <= numread <= LINKCELLS */
579 : int running;
580 : PyObject *nextlink;
581 : PyObject *(values[LINKCELLS]);
582 : } teedataobject;
583 :
584 : typedef struct {
585 : PyObject_HEAD
586 : teedataobject *dataobj;
587 : int index; /* 0 <= index <= LINKCELLS */
588 : PyObject *weakreflist;
589 : } teeobject;
590 :
591 : static PyObject *
592 352736 : teedataobject_newinternal(PyObject *it)
593 : {
594 : teedataobject *tdo;
595 :
596 352736 : tdo = PyObject_GC_New(teedataobject, &teedataobject_type);
597 352736 : if (tdo == NULL)
598 0 : return NULL;
599 :
600 352736 : tdo->running = 0;
601 352736 : tdo->numread = 0;
602 352736 : tdo->nextlink = NULL;
603 352736 : Py_INCREF(it);
604 352736 : tdo->it = it;
605 352736 : PyObject_GC_Track(tdo);
606 352736 : return (PyObject *)tdo;
607 : }
608 :
609 : static PyObject *
610 353777 : teedataobject_jumplink(teedataobject *tdo)
611 : {
612 353777 : if (tdo->nextlink == NULL)
613 352487 : tdo->nextlink = teedataobject_newinternal(tdo->it);
614 353777 : Py_XINCREF(tdo->nextlink);
615 353777 : return tdo->nextlink;
616 : }
617 :
618 : static PyObject *
619 20168500 : teedataobject_getitem(teedataobject *tdo, int i)
620 : {
621 : PyObject *value;
622 :
623 20168500 : assert(i < LINKCELLS);
624 20168500 : if (i < tdo->numread)
625 75015 : value = tdo->values[i];
626 : else {
627 : /* this is the lead iterator, so fetch more data */
628 20093400 : assert(i == tdo->numread);
629 20093400 : if (tdo->running) {
630 2 : PyErr_SetString(PyExc_RuntimeError,
631 : "cannot re-enter the tee iterator");
632 2 : return NULL;
633 : }
634 20093400 : tdo->running = 1;
635 20093400 : value = PyIter_Next(tdo->it);
636 20093400 : tdo->running = 0;
637 20093400 : if (value == NULL)
638 255 : return NULL;
639 20093200 : tdo->numread++;
640 20093200 : tdo->values[i] = value;
641 : }
642 20168200 : Py_INCREF(value);
643 20168200 : return value;
644 : }
645 :
646 : static int
647 2798850 : teedataobject_traverse(teedataobject *tdo, visitproc visit, void * arg)
648 : {
649 : int i;
650 :
651 2798850 : Py_VISIT(tdo->it);
652 142222000 : for (i = 0; i < tdo->numread; i++)
653 139423000 : Py_VISIT(tdo->values[i]);
654 2798850 : Py_VISIT(tdo->nextlink);
655 2798850 : return 0;
656 : }
657 :
658 : static void
659 352737 : teedataobject_safe_decref(PyObject *obj)
660 : {
661 1056280 : while (obj && Py_IS_TYPE(obj, &teedataobject_type) &&
662 352487 : Py_REFCNT(obj) == 1) {
663 351052 : PyObject *nextlink = ((teedataobject *)obj)->nextlink;
664 351052 : ((teedataobject *)obj)->nextlink = NULL;
665 351052 : Py_DECREF(obj);
666 351052 : obj = nextlink;
667 : }
668 352737 : Py_XDECREF(obj);
669 352737 : }
670 :
671 : static int
672 352737 : teedataobject_clear(teedataobject *tdo)
673 : {
674 : int i;
675 : PyObject *tmp;
676 :
677 352737 : Py_CLEAR(tdo->it);
678 20446100 : for (i=0 ; i<tdo->numread ; i++)
679 20093300 : Py_CLEAR(tdo->values[i]);
680 352737 : tmp = tdo->nextlink;
681 352737 : tdo->nextlink = NULL;
682 352737 : teedataobject_safe_decref(tmp);
683 352737 : return 0;
684 : }
685 :
686 : static void
687 352736 : teedataobject_dealloc(teedataobject *tdo)
688 : {
689 352736 : PyObject_GC_UnTrack(tdo);
690 352736 : teedataobject_clear(tdo);
691 352736 : PyObject_GC_Del(tdo);
692 352736 : }
693 :
694 : static PyObject *
695 44 : teedataobject_reduce(teedataobject *tdo, PyObject *Py_UNUSED(ignored))
696 : {
697 : int i;
698 : /* create a temporary list of already iterated values */
699 44 : PyObject *values = PyList_New(tdo->numread);
700 :
701 44 : if (!values)
702 0 : return NULL;
703 176 : for (i=0 ; i<tdo->numread ; i++) {
704 132 : Py_INCREF(tdo->values[i]);
705 132 : PyList_SET_ITEM(values, i, tdo->values[i]);
706 : }
707 44 : return Py_BuildValue("O(ONO)", Py_TYPE(tdo), tdo->it,
708 : values,
709 44 : tdo->nextlink ? tdo->nextlink : Py_None);
710 : }
711 :
712 : /*[clinic input]
713 : @classmethod
714 : itertools.teedataobject.__new__
715 : iterable as it: object
716 : values: object(subclass_of='&PyList_Type')
717 : next: object
718 : /
719 : Data container common to multiple tee objects.
720 : [clinic start generated code]*/
721 :
722 : static PyObject *
723 62 : itertools_teedataobject_impl(PyTypeObject *type, PyObject *it,
724 : PyObject *values, PyObject *next)
725 : /*[clinic end generated code: output=3343ceb07e08df5e input=be60f2fabd2b72ba]*/
726 : {
727 : teedataobject *tdo;
728 : Py_ssize_t i, len;
729 :
730 62 : assert(type == &teedataobject_type);
731 :
732 62 : tdo = (teedataobject *)teedataobject_newinternal(it);
733 62 : if (!tdo)
734 0 : return NULL;
735 :
736 62 : len = PyList_GET_SIZE(values);
737 62 : if (len > LINKCELLS)
738 0 : goto err;
739 212 : for (i=0; i<len; i++) {
740 150 : tdo->values[i] = PyList_GET_ITEM(values, i);
741 150 : Py_INCREF(tdo->values[i]);
742 : }
743 : /* len <= LINKCELLS < INT_MAX */
744 62 : tdo->numread = Py_SAFE_DOWNCAST(len, Py_ssize_t, int);
745 :
746 62 : if (len == LINKCELLS) {
747 0 : if (next != Py_None) {
748 0 : if (!Py_IS_TYPE(next, &teedataobject_type))
749 0 : goto err;
750 0 : assert(tdo->nextlink == NULL);
751 0 : Py_INCREF(next);
752 0 : tdo->nextlink = next;
753 : }
754 : } else {
755 62 : if (next != Py_None)
756 0 : goto err; /* shouldn't have a next if we are not full */
757 : }
758 62 : return (PyObject*)tdo;
759 :
760 0 : err:
761 0 : Py_XDECREF(tdo);
762 0 : PyErr_SetString(PyExc_ValueError, "Invalid arguments");
763 0 : return NULL;
764 : }
765 :
766 : static PyMethodDef teedataobject_methods[] = {
767 : {"__reduce__", (PyCFunction)teedataobject_reduce, METH_NOARGS,
768 : reduce_doc},
769 : {NULL, NULL} /* sentinel */
770 : };
771 :
772 : static PyTypeObject teedataobject_type = {
773 : PyVarObject_HEAD_INIT(0, 0) /* Must fill in type value later */
774 : "itertools._tee_dataobject", /* tp_name */
775 : sizeof(teedataobject), /* tp_basicsize */
776 : 0, /* tp_itemsize */
777 : /* methods */
778 : (destructor)teedataobject_dealloc, /* tp_dealloc */
779 : 0, /* tp_vectorcall_offset */
780 : 0, /* tp_getattr */
781 : 0, /* tp_setattr */
782 : 0, /* tp_as_async */
783 : 0, /* tp_repr */
784 : 0, /* tp_as_number */
785 : 0, /* tp_as_sequence */
786 : 0, /* tp_as_mapping */
787 : 0, /* tp_hash */
788 : 0, /* tp_call */
789 : 0, /* tp_str */
790 : PyObject_GenericGetAttr, /* tp_getattro */
791 : 0, /* tp_setattro */
792 : 0, /* tp_as_buffer */
793 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
794 : itertools_teedataobject__doc__, /* tp_doc */
795 : (traverseproc)teedataobject_traverse, /* tp_traverse */
796 : (inquiry)teedataobject_clear, /* tp_clear */
797 : 0, /* tp_richcompare */
798 : 0, /* tp_weaklistoffset */
799 : 0, /* tp_iter */
800 : 0, /* tp_iternext */
801 : teedataobject_methods, /* tp_methods */
802 : 0, /* tp_members */
803 : 0, /* tp_getset */
804 : 0, /* tp_base */
805 : 0, /* tp_dict */
806 : 0, /* tp_descr_get */
807 : 0, /* tp_descr_set */
808 : 0, /* tp_dictoffset */
809 : 0, /* tp_init */
810 : 0, /* tp_alloc */
811 : itertools_teedataobject, /* tp_new */
812 : PyObject_GC_Del, /* tp_free */
813 : };
814 :
815 :
816 : static PyObject *
817 20168500 : tee_next(teeobject *to)
818 : {
819 : PyObject *value, *link;
820 :
821 20168500 : if (to->index >= LINKCELLS) {
822 353777 : link = teedataobject_jumplink(to->dataobj);
823 353777 : if (link == NULL)
824 0 : return NULL;
825 353777 : Py_SETREF(to->dataobj, (teedataobject *)link);
826 353777 : to->index = 0;
827 : }
828 20168500 : value = teedataobject_getitem(to->dataobj, to->index);
829 20168500 : if (value == NULL)
830 257 : return NULL;
831 20168200 : to->index++;
832 20168200 : return value;
833 : }
834 :
835 : static int
836 570 : tee_traverse(teeobject *to, visitproc visit, void *arg)
837 : {
838 570 : Py_VISIT((PyObject *)to->dataobj);
839 570 : return 0;
840 : }
841 :
842 : static PyObject *
843 122 : tee_copy(teeobject *to, PyObject *Py_UNUSED(ignored))
844 : {
845 : teeobject *newto;
846 :
847 122 : newto = PyObject_GC_New(teeobject, &tee_type);
848 122 : if (newto == NULL)
849 0 : return NULL;
850 122 : Py_INCREF(to->dataobj);
851 122 : newto->dataobj = to->dataobj;
852 122 : newto->index = to->index;
853 122 : newto->weakreflist = NULL;
854 122 : PyObject_GC_Track(newto);
855 122 : return (PyObject *)newto;
856 : }
857 :
858 : PyDoc_STRVAR(teecopy_doc, "Returns an independent iterator.");
859 :
860 : static PyObject *
861 189 : tee_fromiterable(PyObject *iterable)
862 : {
863 : teeobject *to;
864 : PyObject *it;
865 :
866 189 : it = PyObject_GetIter(iterable);
867 189 : if (it == NULL)
868 1 : return NULL;
869 188 : if (PyObject_TypeCheck(it, &tee_type)) {
870 1 : to = (teeobject *)tee_copy((teeobject *)it, NULL);
871 1 : goto done;
872 : }
873 :
874 187 : PyObject *dataobj = teedataobject_newinternal(it);
875 187 : if (!dataobj) {
876 0 : to = NULL;
877 0 : goto done;
878 : }
879 187 : to = PyObject_GC_New(teeobject, &tee_type);
880 187 : if (to == NULL) {
881 0 : Py_DECREF(dataobj);
882 0 : goto done;
883 : }
884 187 : to->dataobj = (teedataobject *)dataobj;
885 187 : to->index = 0;
886 187 : to->weakreflist = NULL;
887 187 : PyObject_GC_Track(to);
888 188 : done:
889 188 : Py_DECREF(it);
890 188 : return (PyObject *)to;
891 : }
892 :
893 : /*[clinic input]
894 : @classmethod
895 : itertools._tee.__new__
896 : iterable: object
897 : /
898 : Iterator wrapped to make it copyable.
899 : [clinic start generated code]*/
900 :
901 : static PyObject *
902 83 : itertools__tee_impl(PyTypeObject *type, PyObject *iterable)
903 : /*[clinic end generated code: output=b02d3fd26c810c3f input=adc0779d2afe37a2]*/
904 : {
905 83 : return tee_fromiterable(iterable);
906 : }
907 :
908 : static int
909 309 : tee_clear(teeobject *to)
910 : {
911 309 : if (to->weakreflist != NULL)
912 1 : PyObject_ClearWeakRefs((PyObject *) to);
913 309 : Py_CLEAR(to->dataobj);
914 309 : return 0;
915 : }
916 :
917 : static void
918 309 : tee_dealloc(teeobject *to)
919 : {
920 309 : PyObject_GC_UnTrack(to);
921 309 : tee_clear(to);
922 309 : PyObject_GC_Del(to);
923 309 : }
924 :
925 : static PyObject *
926 56 : tee_reduce(teeobject *to, PyObject *Py_UNUSED(ignored))
927 : {
928 56 : return Py_BuildValue("O(())(Oi)", Py_TYPE(to), to->dataobj, to->index);
929 : }
930 :
931 : static PyObject *
932 80 : tee_setstate(teeobject *to, PyObject *state)
933 : {
934 : teedataobject *tdo;
935 : int index;
936 80 : if (!PyTuple_Check(state)) {
937 0 : PyErr_SetString(PyExc_TypeError, "state is not a tuple");
938 0 : return NULL;
939 : }
940 80 : if (!PyArg_ParseTuple(state, "O!i", &teedataobject_type, &tdo, &index)) {
941 0 : return NULL;
942 : }
943 80 : if (index < 0 || index > LINKCELLS) {
944 0 : PyErr_SetString(PyExc_ValueError, "Index out of range");
945 0 : return NULL;
946 : }
947 80 : Py_INCREF(tdo);
948 80 : Py_XSETREF(to->dataobj, tdo);
949 80 : to->index = index;
950 80 : Py_RETURN_NONE;
951 : }
952 :
953 : static PyMethodDef tee_methods[] = {
954 : {"__copy__", (PyCFunction)tee_copy, METH_NOARGS, teecopy_doc},
955 : {"__reduce__", (PyCFunction)tee_reduce, METH_NOARGS, reduce_doc},
956 : {"__setstate__", (PyCFunction)tee_setstate, METH_O, setstate_doc},
957 : {NULL, NULL} /* sentinel */
958 : };
959 :
960 : static PyTypeObject tee_type = {
961 : PyVarObject_HEAD_INIT(NULL, 0)
962 : "itertools._tee", /* tp_name */
963 : sizeof(teeobject), /* tp_basicsize */
964 : 0, /* tp_itemsize */
965 : /* methods */
966 : (destructor)tee_dealloc, /* tp_dealloc */
967 : 0, /* tp_vectorcall_offset */
968 : 0, /* tp_getattr */
969 : 0, /* tp_setattr */
970 : 0, /* tp_as_async */
971 : 0, /* tp_repr */
972 : 0, /* tp_as_number */
973 : 0, /* tp_as_sequence */
974 : 0, /* tp_as_mapping */
975 : 0, /* tp_hash */
976 : 0, /* tp_call */
977 : 0, /* tp_str */
978 : 0, /* tp_getattro */
979 : 0, /* tp_setattro */
980 : 0, /* tp_as_buffer */
981 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC, /* tp_flags */
982 : itertools__tee__doc__, /* tp_doc */
983 : (traverseproc)tee_traverse, /* tp_traverse */
984 : (inquiry)tee_clear, /* tp_clear */
985 : 0, /* tp_richcompare */
986 : offsetof(teeobject, weakreflist), /* tp_weaklistoffset */
987 : PyObject_SelfIter, /* tp_iter */
988 : (iternextfunc)tee_next, /* tp_iternext */
989 : tee_methods, /* tp_methods */
990 : 0, /* tp_members */
991 : 0, /* tp_getset */
992 : 0, /* tp_base */
993 : 0, /* tp_dict */
994 : 0, /* tp_descr_get */
995 : 0, /* tp_descr_set */
996 : 0, /* tp_dictoffset */
997 : 0, /* tp_init */
998 : 0, /* tp_alloc */
999 : itertools__tee, /* tp_new */
1000 : PyObject_GC_Del, /* tp_free */
1001 : };
1002 :
1003 : /*[clinic input]
1004 : itertools.tee
1005 : iterable: object
1006 : n: Py_ssize_t = 2
1007 : /
1008 : Returns a tuple of n independent iterators.
1009 : [clinic start generated code]*/
1010 :
1011 : static PyObject *
1012 120 : itertools_tee_impl(PyObject *module, PyObject *iterable, Py_ssize_t n)
1013 : /*[clinic end generated code: output=1c64519cd859c2f0 input=c99a1472c425d66d]*/
1014 : {
1015 : Py_ssize_t i;
1016 : PyObject *it, *copyable, *copyfunc, *result;
1017 :
1018 120 : if (n < 0) {
1019 1 : PyErr_SetString(PyExc_ValueError, "n must be >= 0");
1020 1 : return NULL;
1021 : }
1022 119 : result = PyTuple_New(n);
1023 119 : if (result == NULL)
1024 0 : return NULL;
1025 119 : if (n == 0)
1026 1 : return result;
1027 118 : it = PyObject_GetIter(iterable);
1028 118 : if (it == NULL) {
1029 11 : Py_DECREF(result);
1030 11 : return NULL;
1031 : }
1032 :
1033 107 : if (_PyObject_LookupAttr(it, &_Py_ID(__copy__), ©func) < 0) {
1034 0 : Py_DECREF(it);
1035 0 : Py_DECREF(result);
1036 0 : return NULL;
1037 : }
1038 107 : if (copyfunc != NULL) {
1039 1 : copyable = it;
1040 : }
1041 : else {
1042 106 : copyable = tee_fromiterable(it);
1043 106 : Py_DECREF(it);
1044 106 : if (copyable == NULL) {
1045 0 : Py_DECREF(result);
1046 0 : return NULL;
1047 : }
1048 106 : copyfunc = PyObject_GetAttr(copyable, &_Py_ID(__copy__));
1049 106 : if (copyfunc == NULL) {
1050 0 : Py_DECREF(copyable);
1051 0 : Py_DECREF(result);
1052 0 : return NULL;
1053 : }
1054 : }
1055 :
1056 107 : PyTuple_SET_ITEM(result, 0, copyable);
1057 220 : for (i = 1; i < n; i++) {
1058 113 : copyable = _PyObject_CallNoArgs(copyfunc);
1059 113 : if (copyable == NULL) {
1060 0 : Py_DECREF(copyfunc);
1061 0 : Py_DECREF(result);
1062 0 : return NULL;
1063 : }
1064 113 : PyTuple_SET_ITEM(result, i, copyable);
1065 : }
1066 107 : Py_DECREF(copyfunc);
1067 107 : return result;
1068 : }
1069 :
1070 :
1071 : /* cycle object **************************************************************/
1072 :
1073 : typedef struct {
1074 : PyObject_HEAD
1075 : PyObject *it;
1076 : PyObject *saved;
1077 : Py_ssize_t index;
1078 : int firstpass;
1079 : } cycleobject;
1080 :
1081 : /*[clinic input]
1082 : @classmethod
1083 : itertools.cycle.__new__
1084 : iterable: object
1085 : /
1086 : Return elements from the iterable until it is exhausted. Then repeat the sequence indefinitely.
1087 : [clinic start generated code]*/
1088 :
1089 : static PyObject *
1090 216 : itertools_cycle_impl(PyTypeObject *type, PyObject *iterable)
1091 : /*[clinic end generated code: output=f60e5ec17a45b35c input=9d1d84bcf66e908b]*/
1092 : {
1093 : PyObject *it;
1094 : PyObject *saved;
1095 : cycleobject *lz;
1096 :
1097 : /* Get iterator. */
1098 216 : it = PyObject_GetIter(iterable);
1099 216 : if (it == NULL)
1100 11 : return NULL;
1101 :
1102 205 : saved = PyList_New(0);
1103 205 : if (saved == NULL) {
1104 0 : Py_DECREF(it);
1105 0 : return NULL;
1106 : }
1107 :
1108 : /* create cycleobject structure */
1109 205 : lz = (cycleobject *)type->tp_alloc(type, 0);
1110 205 : if (lz == NULL) {
1111 0 : Py_DECREF(it);
1112 0 : Py_DECREF(saved);
1113 0 : return NULL;
1114 : }
1115 205 : lz->it = it;
1116 205 : lz->saved = saved;
1117 205 : lz->index = 0;
1118 205 : lz->firstpass = 0;
1119 :
1120 205 : return (PyObject *)lz;
1121 : }
1122 :
1123 : static void
1124 205 : cycle_dealloc(cycleobject *lz)
1125 : {
1126 205 : PyObject_GC_UnTrack(lz);
1127 205 : Py_XDECREF(lz->it);
1128 205 : Py_XDECREF(lz->saved);
1129 205 : Py_TYPE(lz)->tp_free(lz);
1130 205 : }
1131 :
1132 : static int
1133 2 : cycle_traverse(cycleobject *lz, visitproc visit, void *arg)
1134 : {
1135 2 : Py_VISIT(lz->it);
1136 2 : Py_VISIT(lz->saved);
1137 2 : return 0;
1138 : }
1139 :
1140 : static PyObject *
1141 6221270 : cycle_next(cycleobject *lz)
1142 : {
1143 : PyObject *item;
1144 :
1145 6221270 : if (lz->it != NULL) {
1146 5838 : item = PyIter_Next(lz->it);
1147 5838 : if (item != NULL) {
1148 5650 : if (lz->firstpass)
1149 37 : return item;
1150 5613 : if (PyList_Append(lz->saved, item)) {
1151 0 : Py_DECREF(item);
1152 0 : return NULL;
1153 : }
1154 5613 : return item;
1155 : }
1156 : /* Note: StopIteration is already cleared by PyIter_Next() */
1157 188 : if (PyErr_Occurred())
1158 6 : return NULL;
1159 182 : Py_CLEAR(lz->it);
1160 : }
1161 6215610 : if (PyList_GET_SIZE(lz->saved) == 0)
1162 7 : return NULL;
1163 6215610 : item = PyList_GET_ITEM(lz->saved, lz->index);
1164 6215610 : lz->index++;
1165 6215610 : if (lz->index >= PyList_GET_SIZE(lz->saved))
1166 702492 : lz->index = 0;
1167 6215610 : Py_INCREF(item);
1168 6215610 : return item;
1169 : }
1170 :
1171 : static PyObject *
1172 37 : cycle_reduce(cycleobject *lz, PyObject *Py_UNUSED(ignored))
1173 : {
1174 : /* Create a new cycle with the iterator tuple, then set the saved state */
1175 37 : if (lz->it == NULL) {
1176 16 : PyObject *it = PyObject_GetIter(lz->saved);
1177 16 : if (it == NULL)
1178 0 : return NULL;
1179 16 : if (lz->index != 0) {
1180 16 : PyObject *res = _PyObject_CallMethod(it, &_Py_ID(__setstate__),
1181 : "n", lz->index);
1182 16 : if (res == NULL) {
1183 0 : Py_DECREF(it);
1184 0 : return NULL;
1185 : }
1186 16 : Py_DECREF(res);
1187 : }
1188 16 : return Py_BuildValue("O(N)(OO)", Py_TYPE(lz), it, lz->saved, Py_True);
1189 : }
1190 21 : return Py_BuildValue("O(O)(OO)", Py_TYPE(lz), lz->it, lz->saved,
1191 21 : lz->firstpass ? Py_True : Py_False);
1192 : }
1193 :
1194 : static PyObject *
1195 50 : cycle_setstate(cycleobject *lz, PyObject *state)
1196 : {
1197 50 : PyObject *saved=NULL;
1198 : int firstpass;
1199 50 : if (!PyTuple_Check(state)) {
1200 1 : PyErr_SetString(PyExc_TypeError, "state is not a tuple");
1201 1 : return NULL;
1202 : }
1203 49 : if (!PyArg_ParseTuple(state, "O!i", &PyList_Type, &saved, &firstpass)) {
1204 4 : return NULL;
1205 : }
1206 45 : Py_INCREF(saved);
1207 45 : Py_XSETREF(lz->saved, saved);
1208 45 : lz->firstpass = firstpass != 0;
1209 45 : lz->index = 0;
1210 45 : Py_RETURN_NONE;
1211 : }
1212 :
1213 : static PyMethodDef cycle_methods[] = {
1214 : {"__reduce__", (PyCFunction)cycle_reduce, METH_NOARGS,
1215 : reduce_doc},
1216 : {"__setstate__", (PyCFunction)cycle_setstate, METH_O,
1217 : setstate_doc},
1218 : {NULL, NULL} /* sentinel */
1219 : };
1220 :
1221 : static PyTypeObject cycle_type = {
1222 : PyVarObject_HEAD_INIT(NULL, 0)
1223 : "itertools.cycle", /* tp_name */
1224 : sizeof(cycleobject), /* tp_basicsize */
1225 : 0, /* tp_itemsize */
1226 : /* methods */
1227 : (destructor)cycle_dealloc, /* tp_dealloc */
1228 : 0, /* tp_vectorcall_offset */
1229 : 0, /* tp_getattr */
1230 : 0, /* tp_setattr */
1231 : 0, /* tp_as_async */
1232 : 0, /* tp_repr */
1233 : 0, /* tp_as_number */
1234 : 0, /* tp_as_sequence */
1235 : 0, /* tp_as_mapping */
1236 : 0, /* tp_hash */
1237 : 0, /* tp_call */
1238 : 0, /* tp_str */
1239 : PyObject_GenericGetAttr, /* tp_getattro */
1240 : 0, /* tp_setattro */
1241 : 0, /* tp_as_buffer */
1242 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
1243 : Py_TPFLAGS_BASETYPE, /* tp_flags */
1244 : itertools_cycle__doc__, /* tp_doc */
1245 : (traverseproc)cycle_traverse, /* tp_traverse */
1246 : 0, /* tp_clear */
1247 : 0, /* tp_richcompare */
1248 : 0, /* tp_weaklistoffset */
1249 : PyObject_SelfIter, /* tp_iter */
1250 : (iternextfunc)cycle_next, /* tp_iternext */
1251 : cycle_methods, /* tp_methods */
1252 : 0, /* tp_members */
1253 : 0, /* tp_getset */
1254 : 0, /* tp_base */
1255 : 0, /* tp_dict */
1256 : 0, /* tp_descr_get */
1257 : 0, /* tp_descr_set */
1258 : 0, /* tp_dictoffset */
1259 : 0, /* tp_init */
1260 : 0, /* tp_alloc */
1261 : itertools_cycle, /* tp_new */
1262 : PyObject_GC_Del, /* tp_free */
1263 : };
1264 :
1265 :
1266 : /* dropwhile object **********************************************************/
1267 :
1268 : typedef struct {
1269 : PyObject_HEAD
1270 : PyObject *func;
1271 : PyObject *it;
1272 : long start;
1273 : } dropwhileobject;
1274 :
1275 : /*[clinic input]
1276 : @classmethod
1277 : itertools.dropwhile.__new__
1278 : predicate as func: object
1279 : iterable as seq: object
1280 : /
1281 : Drop items from the iterable while predicate(item) is true.
1282 :
1283 : Afterwards, return every element until the iterable is exhausted.
1284 : [clinic start generated code]*/
1285 :
1286 : static PyObject *
1287 436 : itertools_dropwhile_impl(PyTypeObject *type, PyObject *func, PyObject *seq)
1288 : /*[clinic end generated code: output=92f9d0d89af149e4 input=d39737147c9f0a26]*/
1289 : {
1290 : PyObject *it;
1291 : dropwhileobject *lz;
1292 :
1293 : /* Get iterator. */
1294 436 : it = PyObject_GetIter(seq);
1295 436 : if (it == NULL)
1296 10 : return NULL;
1297 :
1298 : /* create dropwhileobject structure */
1299 426 : lz = (dropwhileobject *)type->tp_alloc(type, 0);
1300 426 : if (lz == NULL) {
1301 0 : Py_DECREF(it);
1302 0 : return NULL;
1303 : }
1304 426 : Py_INCREF(func);
1305 426 : lz->func = func;
1306 426 : lz->it = it;
1307 426 : lz->start = 0;
1308 :
1309 426 : return (PyObject *)lz;
1310 : }
1311 :
1312 : static void
1313 426 : dropwhile_dealloc(dropwhileobject *lz)
1314 : {
1315 426 : PyObject_GC_UnTrack(lz);
1316 426 : Py_XDECREF(lz->func);
1317 426 : Py_XDECREF(lz->it);
1318 426 : Py_TYPE(lz)->tp_free(lz);
1319 426 : }
1320 :
1321 : static int
1322 2 : dropwhile_traverse(dropwhileobject *lz, visitproc visit, void *arg)
1323 : {
1324 2 : Py_VISIT(lz->it);
1325 2 : Py_VISIT(lz->func);
1326 2 : return 0;
1327 : }
1328 :
1329 : static PyObject *
1330 6574 : dropwhile_next(dropwhileobject *lz)
1331 : {
1332 : PyObject *item, *good;
1333 6574 : PyObject *it = lz->it;
1334 : long ok;
1335 : PyObject *(*iternext)(PyObject *);
1336 :
1337 6574 : iternext = *Py_TYPE(it)->tp_iternext;
1338 : for (;;) {
1339 6798 : item = iternext(it);
1340 6798 : if (item == NULL)
1341 397 : return NULL;
1342 6401 : if (lz->start == 1)
1343 5782 : return item;
1344 :
1345 619 : good = PyObject_CallOneArg(lz->func, item);
1346 619 : if (good == NULL) {
1347 2 : Py_DECREF(item);
1348 2 : return NULL;
1349 : }
1350 617 : ok = PyObject_IsTrue(good);
1351 617 : Py_DECREF(good);
1352 617 : if (ok == 0) {
1353 393 : lz->start = 1;
1354 393 : return item;
1355 : }
1356 224 : Py_DECREF(item);
1357 224 : if (ok < 0)
1358 0 : return NULL;
1359 : }
1360 : }
1361 :
1362 : static PyObject *
1363 14 : dropwhile_reduce(dropwhileobject *lz, PyObject *Py_UNUSED(ignored))
1364 : {
1365 14 : return Py_BuildValue("O(OO)l", Py_TYPE(lz), lz->func, lz->it, lz->start);
1366 : }
1367 :
1368 : static PyObject *
1369 20 : dropwhile_setstate(dropwhileobject *lz, PyObject *state)
1370 : {
1371 20 : int start = PyObject_IsTrue(state);
1372 20 : if (start < 0)
1373 0 : return NULL;
1374 20 : lz->start = start;
1375 20 : Py_RETURN_NONE;
1376 : }
1377 :
1378 : static PyMethodDef dropwhile_methods[] = {
1379 : {"__reduce__", (PyCFunction)dropwhile_reduce, METH_NOARGS,
1380 : reduce_doc},
1381 : {"__setstate__", (PyCFunction)dropwhile_setstate, METH_O,
1382 : setstate_doc},
1383 : {NULL, NULL} /* sentinel */
1384 : };
1385 :
1386 : static PyTypeObject dropwhile_type = {
1387 : PyVarObject_HEAD_INIT(NULL, 0)
1388 : "itertools.dropwhile", /* tp_name */
1389 : sizeof(dropwhileobject), /* tp_basicsize */
1390 : 0, /* tp_itemsize */
1391 : /* methods */
1392 : (destructor)dropwhile_dealloc, /* tp_dealloc */
1393 : 0, /* tp_vectorcall_offset */
1394 : 0, /* tp_getattr */
1395 : 0, /* tp_setattr */
1396 : 0, /* tp_as_async */
1397 : 0, /* tp_repr */
1398 : 0, /* tp_as_number */
1399 : 0, /* tp_as_sequence */
1400 : 0, /* tp_as_mapping */
1401 : 0, /* tp_hash */
1402 : 0, /* tp_call */
1403 : 0, /* tp_str */
1404 : PyObject_GenericGetAttr, /* tp_getattro */
1405 : 0, /* tp_setattro */
1406 : 0, /* tp_as_buffer */
1407 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
1408 : Py_TPFLAGS_BASETYPE, /* tp_flags */
1409 : itertools_dropwhile__doc__, /* tp_doc */
1410 : (traverseproc)dropwhile_traverse, /* tp_traverse */
1411 : 0, /* tp_clear */
1412 : 0, /* tp_richcompare */
1413 : 0, /* tp_weaklistoffset */
1414 : PyObject_SelfIter, /* tp_iter */
1415 : (iternextfunc)dropwhile_next, /* tp_iternext */
1416 : dropwhile_methods, /* tp_methods */
1417 : 0, /* tp_members */
1418 : 0, /* tp_getset */
1419 : 0, /* tp_base */
1420 : 0, /* tp_dict */
1421 : 0, /* tp_descr_get */
1422 : 0, /* tp_descr_set */
1423 : 0, /* tp_dictoffset */
1424 : 0, /* tp_init */
1425 : 0, /* tp_alloc */
1426 : itertools_dropwhile, /* tp_new */
1427 : PyObject_GC_Del, /* tp_free */
1428 : };
1429 :
1430 :
1431 : /* takewhile object **********************************************************/
1432 :
1433 : typedef struct {
1434 : PyObject_HEAD
1435 : PyObject *func;
1436 : PyObject *it;
1437 : long stop;
1438 : } takewhileobject;
1439 :
1440 : /*[clinic input]
1441 : @classmethod
1442 : itertools.takewhile.__new__
1443 : predicate as func: object
1444 : iterable as seq: object
1445 : /
1446 : Return successive entries from an iterable as long as the predicate evaluates to true for each entry.
1447 : [clinic start generated code]*/
1448 :
1449 : static PyObject *
1450 86 : itertools_takewhile_impl(PyTypeObject *type, PyObject *func, PyObject *seq)
1451 : /*[clinic end generated code: output=bb179ea7864e2ef6 input=ba5255f7519aa119]*/
1452 : {
1453 : PyObject *it;
1454 : takewhileobject *lz;
1455 :
1456 : /* Get iterator. */
1457 86 : it = PyObject_GetIter(seq);
1458 86 : if (it == NULL)
1459 10 : return NULL;
1460 :
1461 : /* create takewhileobject structure */
1462 76 : lz = (takewhileobject *)type->tp_alloc(type, 0);
1463 76 : if (lz == NULL) {
1464 0 : Py_DECREF(it);
1465 0 : return NULL;
1466 : }
1467 76 : Py_INCREF(func);
1468 76 : lz->func = func;
1469 76 : lz->it = it;
1470 76 : lz->stop = 0;
1471 :
1472 76 : return (PyObject *)lz;
1473 : }
1474 :
1475 : static void
1476 76 : takewhile_dealloc(takewhileobject *lz)
1477 : {
1478 76 : PyObject_GC_UnTrack(lz);
1479 76 : Py_XDECREF(lz->func);
1480 76 : Py_XDECREF(lz->it);
1481 76 : Py_TYPE(lz)->tp_free(lz);
1482 76 : }
1483 :
1484 : static int
1485 2 : takewhile_traverse(takewhileobject *lz, visitproc visit, void *arg)
1486 : {
1487 2 : Py_VISIT(lz->it);
1488 2 : Py_VISIT(lz->func);
1489 2 : return 0;
1490 : }
1491 :
1492 : static PyObject *
1493 174 : takewhile_next(takewhileobject *lz)
1494 : {
1495 : PyObject *item, *good;
1496 174 : PyObject *it = lz->it;
1497 : long ok;
1498 :
1499 174 : if (lz->stop == 1)
1500 1 : return NULL;
1501 :
1502 173 : item = (*Py_TYPE(it)->tp_iternext)(it);
1503 173 : if (item == NULL)
1504 18 : return NULL;
1505 :
1506 155 : good = PyObject_CallOneArg(lz->func, item);
1507 155 : if (good == NULL) {
1508 2 : Py_DECREF(item);
1509 2 : return NULL;
1510 : }
1511 153 : ok = PyObject_IsTrue(good);
1512 153 : Py_DECREF(good);
1513 153 : if (ok > 0)
1514 100 : return item;
1515 53 : Py_DECREF(item);
1516 53 : if (ok == 0)
1517 53 : lz->stop = 1;
1518 53 : return NULL;
1519 : }
1520 :
1521 : static PyObject *
1522 14 : takewhile_reduce(takewhileobject *lz, PyObject *Py_UNUSED(ignored))
1523 : {
1524 14 : return Py_BuildValue("O(OO)l", Py_TYPE(lz), lz->func, lz->it, lz->stop);
1525 : }
1526 :
1527 : static PyObject *
1528 20 : takewhile_reduce_setstate(takewhileobject *lz, PyObject *state)
1529 : {
1530 20 : int stop = PyObject_IsTrue(state);
1531 :
1532 20 : if (stop < 0)
1533 0 : return NULL;
1534 20 : lz->stop = stop;
1535 20 : Py_RETURN_NONE;
1536 : }
1537 :
1538 : static PyMethodDef takewhile_reduce_methods[] = {
1539 : {"__reduce__", (PyCFunction)takewhile_reduce, METH_NOARGS,
1540 : reduce_doc},
1541 : {"__setstate__", (PyCFunction)takewhile_reduce_setstate, METH_O,
1542 : setstate_doc},
1543 : {NULL, NULL} /* sentinel */
1544 : };
1545 :
1546 : static PyTypeObject takewhile_type = {
1547 : PyVarObject_HEAD_INIT(NULL, 0)
1548 : "itertools.takewhile", /* tp_name */
1549 : sizeof(takewhileobject), /* tp_basicsize */
1550 : 0, /* tp_itemsize */
1551 : /* methods */
1552 : (destructor)takewhile_dealloc, /* tp_dealloc */
1553 : 0, /* tp_vectorcall_offset */
1554 : 0, /* tp_getattr */
1555 : 0, /* tp_setattr */
1556 : 0, /* tp_as_async */
1557 : 0, /* tp_repr */
1558 : 0, /* tp_as_number */
1559 : 0, /* tp_as_sequence */
1560 : 0, /* tp_as_mapping */
1561 : 0, /* tp_hash */
1562 : 0, /* tp_call */
1563 : 0, /* tp_str */
1564 : PyObject_GenericGetAttr, /* tp_getattro */
1565 : 0, /* tp_setattro */
1566 : 0, /* tp_as_buffer */
1567 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
1568 : Py_TPFLAGS_BASETYPE, /* tp_flags */
1569 : itertools_takewhile__doc__, /* tp_doc */
1570 : (traverseproc)takewhile_traverse, /* tp_traverse */
1571 : 0, /* tp_clear */
1572 : 0, /* tp_richcompare */
1573 : 0, /* tp_weaklistoffset */
1574 : PyObject_SelfIter, /* tp_iter */
1575 : (iternextfunc)takewhile_next, /* tp_iternext */
1576 : takewhile_reduce_methods, /* tp_methods */
1577 : 0, /* tp_members */
1578 : 0, /* tp_getset */
1579 : 0, /* tp_base */
1580 : 0, /* tp_dict */
1581 : 0, /* tp_descr_get */
1582 : 0, /* tp_descr_set */
1583 : 0, /* tp_dictoffset */
1584 : 0, /* tp_init */
1585 : 0, /* tp_alloc */
1586 : itertools_takewhile, /* tp_new */
1587 : PyObject_GC_Del, /* tp_free */
1588 : };
1589 :
1590 :
1591 : /* islice object *************************************************************/
1592 :
1593 : typedef struct {
1594 : PyObject_HEAD
1595 : PyObject *it;
1596 : Py_ssize_t next;
1597 : Py_ssize_t stop;
1598 : Py_ssize_t step;
1599 : Py_ssize_t cnt;
1600 : } isliceobject;
1601 :
1602 : static PyTypeObject islice_type;
1603 :
1604 : static PyObject *
1605 173998 : islice_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1606 : {
1607 : PyObject *seq;
1608 173998 : Py_ssize_t start=0, stop=-1, step=1;
1609 173998 : PyObject *it, *a1=NULL, *a2=NULL, *a3=NULL;
1610 : Py_ssize_t numargs;
1611 : isliceobject *lz;
1612 :
1613 173998 : if ((type == &islice_type || type->tp_init == islice_type.tp_init) &&
1614 22 : !_PyArg_NoKeywords("islice", kwds))
1615 1 : return NULL;
1616 :
1617 173997 : if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))
1618 2 : return NULL;
1619 :
1620 173995 : numargs = PyTuple_Size(args);
1621 173995 : if (numargs == 2) {
1622 144913 : if (a1 != Py_None) {
1623 144805 : stop = PyNumber_AsSsize_t(a1, PyExc_OverflowError);
1624 144805 : if (stop == -1) {
1625 1 : if (PyErr_Occurred())
1626 1 : PyErr_Clear();
1627 1 : PyErr_SetString(PyExc_ValueError,
1628 : "Stop argument for islice() must be None or "
1629 : "an integer: 0 <= x <= sys.maxsize.");
1630 1 : return NULL;
1631 : }
1632 : }
1633 : } else {
1634 29082 : if (a1 != Py_None)
1635 29080 : start = PyNumber_AsSsize_t(a1, PyExc_OverflowError);
1636 29082 : if (start == -1 && PyErr_Occurred())
1637 2 : PyErr_Clear();
1638 29082 : if (a2 != Py_None) {
1639 182 : stop = PyNumber_AsSsize_t(a2, PyExc_OverflowError);
1640 182 : if (stop == -1) {
1641 2 : if (PyErr_Occurred())
1642 2 : PyErr_Clear();
1643 2 : PyErr_SetString(PyExc_ValueError,
1644 : "Stop argument for islice() must be None or "
1645 : "an integer: 0 <= x <= sys.maxsize.");
1646 2 : return NULL;
1647 : }
1648 : }
1649 : }
1650 173992 : if (start<0 || stop<-1) {
1651 4 : PyErr_SetString(PyExc_ValueError,
1652 : "Indices for islice() must be None or "
1653 : "an integer: 0 <= x <= sys.maxsize.");
1654 4 : return NULL;
1655 : }
1656 :
1657 173988 : if (a3 != NULL) {
1658 213 : if (a3 != Py_None)
1659 212 : step = PyNumber_AsSsize_t(a3, PyExc_OverflowError);
1660 213 : if (step == -1 && PyErr_Occurred())
1661 0 : PyErr_Clear();
1662 : }
1663 173988 : if (step<1) {
1664 2 : PyErr_SetString(PyExc_ValueError,
1665 : "Step for islice() must be a positive integer or None.");
1666 2 : return NULL;
1667 : }
1668 :
1669 : /* Get iterator. */
1670 173986 : it = PyObject_GetIter(seq);
1671 173986 : if (it == NULL)
1672 23074 : return NULL;
1673 :
1674 : /* create isliceobject structure */
1675 150912 : lz = (isliceobject *)type->tp_alloc(type, 0);
1676 150912 : if (lz == NULL) {
1677 0 : Py_DECREF(it);
1678 0 : return NULL;
1679 : }
1680 150912 : lz->it = it;
1681 150912 : lz->next = start;
1682 150912 : lz->stop = stop;
1683 150912 : lz->step = step;
1684 150912 : lz->cnt = 0L;
1685 :
1686 150912 : return (PyObject *)lz;
1687 : }
1688 :
1689 : static void
1690 150912 : islice_dealloc(isliceobject *lz)
1691 : {
1692 150912 : PyObject_GC_UnTrack(lz);
1693 150912 : Py_XDECREF(lz->it);
1694 150912 : Py_TYPE(lz)->tp_free(lz);
1695 150912 : }
1696 :
1697 : static int
1698 60 : islice_traverse(isliceobject *lz, visitproc visit, void *arg)
1699 : {
1700 60 : Py_VISIT(lz->it);
1701 60 : return 0;
1702 : }
1703 :
1704 : static PyObject *
1705 9234660 : islice_next(isliceobject *lz)
1706 : {
1707 : PyObject *item;
1708 9234660 : PyObject *it = lz->it;
1709 9234660 : Py_ssize_t stop = lz->stop;
1710 : Py_ssize_t oldnext;
1711 : PyObject *(*iternext)(PyObject *);
1712 :
1713 9234660 : if (it == NULL)
1714 12 : return NULL;
1715 :
1716 9234640 : iternext = *Py_TYPE(it)->tp_iternext;
1717 9811010 : while (lz->cnt < lz->next) {
1718 576428 : item = iternext(it);
1719 576428 : if (item == NULL)
1720 61 : goto empty;
1721 576367 : Py_DECREF(item);
1722 576367 : lz->cnt++;
1723 : }
1724 9234580 : if (stop != -1 && lz->cnt >= stop)
1725 32683 : goto empty;
1726 9201900 : item = iternext(it);
1727 9201900 : if (item == NULL)
1728 111068 : goto empty;
1729 9090830 : lz->cnt++;
1730 9090830 : oldnext = lz->next;
1731 : /* The (size_t) cast below avoids the danger of undefined
1732 : behaviour from signed integer overflow. */
1733 9090830 : lz->next += (size_t)lz->step;
1734 9090830 : if (lz->next < oldnext || (stop != -1 && lz->next > stop))
1735 29 : lz->next = stop;
1736 9090830 : return item;
1737 :
1738 143812 : empty:
1739 143812 : Py_CLEAR(lz->it);
1740 143812 : return NULL;
1741 : }
1742 :
1743 : static PyObject *
1744 70 : islice_reduce(isliceobject *lz, PyObject *Py_UNUSED(ignored))
1745 : {
1746 : /* When unpickled, generate a new object with the same bounds,
1747 : * then 'setstate' with the next and count
1748 : */
1749 : PyObject *stop;
1750 :
1751 70 : if (lz->it == NULL) {
1752 : PyObject *empty_list;
1753 : PyObject *empty_it;
1754 12 : empty_list = PyList_New(0);
1755 12 : if (empty_list == NULL)
1756 0 : return NULL;
1757 12 : empty_it = PyObject_GetIter(empty_list);
1758 12 : Py_DECREF(empty_list);
1759 12 : if (empty_it == NULL)
1760 0 : return NULL;
1761 12 : return Py_BuildValue("O(Nn)n", Py_TYPE(lz), empty_it, 0, 0);
1762 : }
1763 58 : if (lz->stop == -1) {
1764 0 : stop = Py_None;
1765 0 : Py_INCREF(stop);
1766 : } else {
1767 58 : stop = PyLong_FromSsize_t(lz->stop);
1768 58 : if (stop == NULL)
1769 0 : return NULL;
1770 : }
1771 58 : return Py_BuildValue("O(OnNn)n", Py_TYPE(lz),
1772 : lz->it, lz->next, stop, lz->step,
1773 : lz->cnt);
1774 : }
1775 :
1776 : static PyObject *
1777 100 : islice_setstate(isliceobject *lz, PyObject *state)
1778 : {
1779 100 : Py_ssize_t cnt = PyLong_AsSsize_t(state);
1780 :
1781 100 : if (cnt == -1 && PyErr_Occurred())
1782 0 : return NULL;
1783 100 : lz->cnt = cnt;
1784 100 : Py_RETURN_NONE;
1785 : }
1786 :
1787 : static PyMethodDef islice_methods[] = {
1788 : {"__reduce__", (PyCFunction)islice_reduce, METH_NOARGS,
1789 : reduce_doc},
1790 : {"__setstate__", (PyCFunction)islice_setstate, METH_O,
1791 : setstate_doc},
1792 : {NULL, NULL} /* sentinel */
1793 : };
1794 :
1795 : PyDoc_STRVAR(islice_doc,
1796 : "islice(iterable, stop) --> islice object\n\
1797 : islice(iterable, start, stop[, step]) --> islice object\n\
1798 : \n\
1799 : Return an iterator whose next() method returns selected values from an\n\
1800 : iterable. If start is specified, will skip all preceding elements;\n\
1801 : otherwise, start defaults to zero. Step defaults to one. If\n\
1802 : specified as another value, step determines how many values are\n\
1803 : skipped between successive calls. Works like a slice() on a list\n\
1804 : but returns an iterator.");
1805 :
1806 : static PyTypeObject islice_type = {
1807 : PyVarObject_HEAD_INIT(NULL, 0)
1808 : "itertools.islice", /* tp_name */
1809 : sizeof(isliceobject), /* tp_basicsize */
1810 : 0, /* tp_itemsize */
1811 : /* methods */
1812 : (destructor)islice_dealloc, /* tp_dealloc */
1813 : 0, /* tp_vectorcall_offset */
1814 : 0, /* tp_getattr */
1815 : 0, /* tp_setattr */
1816 : 0, /* tp_as_async */
1817 : 0, /* tp_repr */
1818 : 0, /* tp_as_number */
1819 : 0, /* tp_as_sequence */
1820 : 0, /* tp_as_mapping */
1821 : 0, /* tp_hash */
1822 : 0, /* tp_call */
1823 : 0, /* tp_str */
1824 : PyObject_GenericGetAttr, /* tp_getattro */
1825 : 0, /* tp_setattro */
1826 : 0, /* tp_as_buffer */
1827 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
1828 : Py_TPFLAGS_BASETYPE, /* tp_flags */
1829 : islice_doc, /* tp_doc */
1830 : (traverseproc)islice_traverse, /* tp_traverse */
1831 : 0, /* tp_clear */
1832 : 0, /* tp_richcompare */
1833 : 0, /* tp_weaklistoffset */
1834 : PyObject_SelfIter, /* tp_iter */
1835 : (iternextfunc)islice_next, /* tp_iternext */
1836 : islice_methods, /* tp_methods */
1837 : 0, /* tp_members */
1838 : 0, /* tp_getset */
1839 : 0, /* tp_base */
1840 : 0, /* tp_dict */
1841 : 0, /* tp_descr_get */
1842 : 0, /* tp_descr_set */
1843 : 0, /* tp_dictoffset */
1844 : 0, /* tp_init */
1845 : 0, /* tp_alloc */
1846 : islice_new, /* tp_new */
1847 : PyObject_GC_Del, /* tp_free */
1848 : };
1849 :
1850 :
1851 : /* starmap object ************************************************************/
1852 :
1853 : typedef struct {
1854 : PyObject_HEAD
1855 : PyObject *func;
1856 : PyObject *it;
1857 : } starmapobject;
1858 :
1859 : /*[clinic input]
1860 : @classmethod
1861 : itertools.starmap.__new__
1862 : function as func: object
1863 : iterable as seq: object
1864 : /
1865 : Return an iterator whose values are returned from the function evaluated with an argument tuple taken from the given sequence.
1866 : [clinic start generated code]*/
1867 :
1868 : static PyObject *
1869 9028 : itertools_starmap_impl(PyTypeObject *type, PyObject *func, PyObject *seq)
1870 : /*[clinic end generated code: output=79eeb81d452c6e8d input=844766df6a0d4dad]*/
1871 : {
1872 : PyObject *it;
1873 : starmapobject *lz;
1874 :
1875 : /* Get iterator. */
1876 9028 : it = PyObject_GetIter(seq);
1877 9028 : if (it == NULL)
1878 10 : return NULL;
1879 :
1880 : /* create starmapobject structure */
1881 9018 : lz = (starmapobject *)type->tp_alloc(type, 0);
1882 9018 : if (lz == NULL) {
1883 0 : Py_DECREF(it);
1884 0 : return NULL;
1885 : }
1886 9018 : Py_INCREF(func);
1887 9018 : lz->func = func;
1888 9018 : lz->it = it;
1889 :
1890 9018 : return (PyObject *)lz;
1891 : }
1892 :
1893 : static void
1894 9018 : starmap_dealloc(starmapobject *lz)
1895 : {
1896 9018 : PyObject_GC_UnTrack(lz);
1897 9018 : Py_XDECREF(lz->func);
1898 9018 : Py_XDECREF(lz->it);
1899 9018 : Py_TYPE(lz)->tp_free(lz);
1900 9018 : }
1901 :
1902 : static int
1903 2 : starmap_traverse(starmapobject *lz, visitproc visit, void *arg)
1904 : {
1905 2 : Py_VISIT(lz->it);
1906 2 : Py_VISIT(lz->func);
1907 2 : return 0;
1908 : }
1909 :
1910 : static PyObject *
1911 34314 : starmap_next(starmapobject *lz)
1912 : {
1913 : PyObject *args;
1914 : PyObject *result;
1915 34314 : PyObject *it = lz->it;
1916 :
1917 34314 : args = (*Py_TYPE(it)->tp_iternext)(it);
1918 34314 : if (args == NULL)
1919 9010 : return NULL;
1920 25304 : if (!PyTuple_CheckExact(args)) {
1921 26 : PyObject *newargs = PySequence_Tuple(args);
1922 26 : Py_DECREF(args);
1923 26 : if (newargs == NULL)
1924 1 : return NULL;
1925 25 : args = newargs;
1926 : }
1927 25303 : result = PyObject_Call(lz->func, args, NULL);
1928 25303 : Py_DECREF(args);
1929 25303 : return result;
1930 : }
1931 :
1932 : static PyObject *
1933 14 : starmap_reduce(starmapobject *lz, PyObject *Py_UNUSED(ignored))
1934 : {
1935 : /* Just pickle the iterator */
1936 14 : return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->func, lz->it);
1937 : }
1938 :
1939 : static PyMethodDef starmap_methods[] = {
1940 : {"__reduce__", (PyCFunction)starmap_reduce, METH_NOARGS,
1941 : reduce_doc},
1942 : {NULL, NULL} /* sentinel */
1943 : };
1944 :
1945 : static PyTypeObject starmap_type = {
1946 : PyVarObject_HEAD_INIT(NULL, 0)
1947 : "itertools.starmap", /* tp_name */
1948 : sizeof(starmapobject), /* tp_basicsize */
1949 : 0, /* tp_itemsize */
1950 : /* methods */
1951 : (destructor)starmap_dealloc, /* tp_dealloc */
1952 : 0, /* tp_vectorcall_offset */
1953 : 0, /* tp_getattr */
1954 : 0, /* tp_setattr */
1955 : 0, /* tp_as_async */
1956 : 0, /* tp_repr */
1957 : 0, /* tp_as_number */
1958 : 0, /* tp_as_sequence */
1959 : 0, /* tp_as_mapping */
1960 : 0, /* tp_hash */
1961 : 0, /* tp_call */
1962 : 0, /* tp_str */
1963 : PyObject_GenericGetAttr, /* tp_getattro */
1964 : 0, /* tp_setattro */
1965 : 0, /* tp_as_buffer */
1966 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
1967 : Py_TPFLAGS_BASETYPE, /* tp_flags */
1968 : itertools_starmap__doc__, /* tp_doc */
1969 : (traverseproc)starmap_traverse, /* tp_traverse */
1970 : 0, /* tp_clear */
1971 : 0, /* tp_richcompare */
1972 : 0, /* tp_weaklistoffset */
1973 : PyObject_SelfIter, /* tp_iter */
1974 : (iternextfunc)starmap_next, /* tp_iternext */
1975 : starmap_methods, /* tp_methods */
1976 : 0, /* tp_members */
1977 : 0, /* tp_getset */
1978 : 0, /* tp_base */
1979 : 0, /* tp_dict */
1980 : 0, /* tp_descr_get */
1981 : 0, /* tp_descr_set */
1982 : 0, /* tp_dictoffset */
1983 : 0, /* tp_init */
1984 : 0, /* tp_alloc */
1985 : itertools_starmap, /* tp_new */
1986 : PyObject_GC_Del, /* tp_free */
1987 : };
1988 :
1989 :
1990 : /* chain object **************************************************************/
1991 :
1992 : typedef struct {
1993 : PyObject_HEAD
1994 : PyObject *source; /* Iterator over input iterables */
1995 : PyObject *active; /* Currently running input iterator */
1996 : } chainobject;
1997 :
1998 : static PyTypeObject chain_type;
1999 :
2000 : static PyObject *
2001 34548 : chain_new_internal(PyTypeObject *type, PyObject *source)
2002 : {
2003 : chainobject *lz;
2004 :
2005 34548 : lz = (chainobject *)type->tp_alloc(type, 0);
2006 34548 : if (lz == NULL) {
2007 0 : Py_DECREF(source);
2008 0 : return NULL;
2009 : }
2010 :
2011 34548 : lz->source = source;
2012 34548 : lz->active = NULL;
2013 34548 : return (PyObject *)lz;
2014 : }
2015 :
2016 : static PyObject *
2017 24876 : chain_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2018 : {
2019 : PyObject *source;
2020 :
2021 24876 : if ((type == &chain_type || type->tp_init == chain_type.tp_init) &&
2022 1 : !_PyArg_NoKeywords("chain", kwds))
2023 1 : return NULL;
2024 :
2025 24875 : source = PyObject_GetIter(args);
2026 24875 : if (source == NULL)
2027 0 : return NULL;
2028 :
2029 24875 : return chain_new_internal(type, source);
2030 : }
2031 :
2032 : /*[clinic input]
2033 : @classmethod
2034 : itertools.chain.from_iterable
2035 : iterable as arg: object
2036 : /
2037 : Alternative chain() constructor taking a single iterable argument that evaluates lazily.
2038 : [clinic start generated code]*/
2039 :
2040 : static PyObject *
2041 9673 : itertools_chain_from_iterable(PyTypeObject *type, PyObject *arg)
2042 : /*[clinic end generated code: output=667ae7a7f7b68654 input=72c39e3a2ca3be85]*/
2043 : {
2044 : PyObject *source;
2045 :
2046 9673 : source = PyObject_GetIter(arg);
2047 9673 : if (source == NULL)
2048 0 : return NULL;
2049 :
2050 9673 : return chain_new_internal(type, source);
2051 : }
2052 :
2053 : static void
2054 34548 : chain_dealloc(chainobject *lz)
2055 : {
2056 34548 : PyObject_GC_UnTrack(lz);
2057 34548 : Py_XDECREF(lz->active);
2058 34548 : Py_XDECREF(lz->source);
2059 34548 : Py_TYPE(lz)->tp_free(lz);
2060 34548 : }
2061 :
2062 : static int
2063 3924 : chain_traverse(chainobject *lz, visitproc visit, void *arg)
2064 : {
2065 3924 : Py_VISIT(lz->source);
2066 3924 : Py_VISIT(lz->active);
2067 3924 : return 0;
2068 : }
2069 :
2070 : static PyObject *
2071 4259280 : chain_next(chainobject *lz)
2072 : {
2073 : PyObject *item;
2074 :
2075 : /* lz->source is the iterator of iterables. If it's NULL, we've already
2076 : * consumed them all. lz->active is the current iterator. If it's NULL,
2077 : * we should grab a new one from lz->source. */
2078 14392600 : while (lz->source != NULL) {
2079 14392600 : if (lz->active == NULL) {
2080 10167800 : PyObject *iterable = PyIter_Next(lz->source);
2081 10167800 : if (iterable == NULL) {
2082 30881 : Py_CLEAR(lz->source);
2083 30881 : return NULL; /* no more input sources */
2084 : }
2085 10136900 : lz->active = PyObject_GetIter(iterable);
2086 10136900 : Py_DECREF(iterable);
2087 10136900 : if (lz->active == NULL) {
2088 19 : Py_CLEAR(lz->source);
2089 19 : return NULL; /* input not iterable */
2090 : }
2091 : }
2092 14361700 : item = (*Py_TYPE(lz->active)->tp_iternext)(lz->active);
2093 14361700 : if (item != NULL)
2094 4228360 : return item;
2095 10133300 : if (PyErr_Occurred()) {
2096 40 : if (PyErr_ExceptionMatches(PyExc_StopIteration))
2097 32 : PyErr_Clear();
2098 : else
2099 8 : return NULL; /* input raised an exception */
2100 : }
2101 : /* lz->active is consumed, try with the next iterable. */
2102 10133300 : Py_CLEAR(lz->active);
2103 : }
2104 : /* Everything had been consumed already. */
2105 5 : return NULL;
2106 : }
2107 :
2108 : static PyObject *
2109 66 : chain_reduce(chainobject *lz, PyObject *Py_UNUSED(ignored))
2110 : {
2111 66 : if (lz->source) {
2112 : /* we can't pickle function objects (itertools.from_iterable) so
2113 : * we must use setstate to replace the iterable. One day we
2114 : * will fix pickling of functions
2115 : */
2116 66 : if (lz->active) {
2117 19 : return Py_BuildValue("O()(OO)", Py_TYPE(lz), lz->source, lz->active);
2118 : } else {
2119 47 : return Py_BuildValue("O()(O)", Py_TYPE(lz), lz->source);
2120 : }
2121 : } else {
2122 0 : return Py_BuildValue("O()", Py_TYPE(lz)); /* exhausted */
2123 : }
2124 : return NULL;
2125 : }
2126 :
2127 : static PyObject *
2128 85 : chain_setstate(chainobject *lz, PyObject *state)
2129 : {
2130 85 : PyObject *source, *active=NULL;
2131 :
2132 85 : if (!PyTuple_Check(state)) {
2133 2 : PyErr_SetString(PyExc_TypeError, "state is not a tuple");
2134 2 : return NULL;
2135 : }
2136 83 : if (!PyArg_ParseTuple(state, "O|O", &source, &active)) {
2137 1 : return NULL;
2138 : }
2139 82 : if (!PyIter_Check(source) || (active != NULL && !PyIter_Check(active))) {
2140 2 : PyErr_SetString(PyExc_TypeError, "Arguments must be iterators.");
2141 2 : return NULL;
2142 : }
2143 :
2144 80 : Py_INCREF(source);
2145 80 : Py_XSETREF(lz->source, source);
2146 80 : Py_XINCREF(active);
2147 80 : Py_XSETREF(lz->active, active);
2148 80 : Py_RETURN_NONE;
2149 : }
2150 :
2151 : PyDoc_STRVAR(chain_doc,
2152 : "chain(*iterables) --> chain object\n\
2153 : \n\
2154 : Return a chain object whose .__next__() method returns elements from the\n\
2155 : first iterable until it is exhausted, then elements from the next\n\
2156 : iterable, until all of the iterables are exhausted.");
2157 :
2158 : static PyMethodDef chain_methods[] = {
2159 : ITERTOOLS_CHAIN_FROM_ITERABLE_METHODDEF
2160 : {"__reduce__", (PyCFunction)chain_reduce, METH_NOARGS,
2161 : reduce_doc},
2162 : {"__setstate__", (PyCFunction)chain_setstate, METH_O,
2163 : setstate_doc},
2164 : {"__class_getitem__", Py_GenericAlias,
2165 : METH_O|METH_CLASS, PyDoc_STR("See PEP 585")},
2166 : {NULL, NULL} /* sentinel */
2167 : };
2168 :
2169 : static PyTypeObject chain_type = {
2170 : PyVarObject_HEAD_INIT(NULL, 0)
2171 : "itertools.chain", /* tp_name */
2172 : sizeof(chainobject), /* tp_basicsize */
2173 : 0, /* tp_itemsize */
2174 : /* methods */
2175 : (destructor)chain_dealloc, /* tp_dealloc */
2176 : 0, /* tp_vectorcall_offset */
2177 : 0, /* tp_getattr */
2178 : 0, /* tp_setattr */
2179 : 0, /* tp_as_async */
2180 : 0, /* tp_repr */
2181 : 0, /* tp_as_number */
2182 : 0, /* tp_as_sequence */
2183 : 0, /* tp_as_mapping */
2184 : 0, /* tp_hash */
2185 : 0, /* tp_call */
2186 : 0, /* tp_str */
2187 : PyObject_GenericGetAttr, /* tp_getattro */
2188 : 0, /* tp_setattro */
2189 : 0, /* tp_as_buffer */
2190 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2191 : Py_TPFLAGS_BASETYPE, /* tp_flags */
2192 : chain_doc, /* tp_doc */
2193 : (traverseproc)chain_traverse, /* tp_traverse */
2194 : 0, /* tp_clear */
2195 : 0, /* tp_richcompare */
2196 : 0, /* tp_weaklistoffset */
2197 : PyObject_SelfIter, /* tp_iter */
2198 : (iternextfunc)chain_next, /* tp_iternext */
2199 : chain_methods, /* tp_methods */
2200 : 0, /* tp_members */
2201 : 0, /* tp_getset */
2202 : 0, /* tp_base */
2203 : 0, /* tp_dict */
2204 : 0, /* tp_descr_get */
2205 : 0, /* tp_descr_set */
2206 : 0, /* tp_dictoffset */
2207 : 0, /* tp_init */
2208 : 0, /* tp_alloc */
2209 : chain_new, /* tp_new */
2210 : PyObject_GC_Del, /* tp_free */
2211 : };
2212 :
2213 :
2214 : /* product object ************************************************************/
2215 :
2216 : typedef struct {
2217 : PyObject_HEAD
2218 : PyObject *pools; /* tuple of pool tuples */
2219 : Py_ssize_t *indices; /* one index per pool */
2220 : PyObject *result; /* most recently returned result tuple */
2221 : int stopped; /* set to 1 when the iterator is exhausted */
2222 : } productobject;
2223 :
2224 : static PyTypeObject product_type;
2225 :
2226 : static PyObject *
2227 59536 : product_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2228 : {
2229 : productobject *lz;
2230 59536 : Py_ssize_t nargs, npools, repeat=1;
2231 59536 : PyObject *pools = NULL;
2232 59536 : Py_ssize_t *indices = NULL;
2233 : Py_ssize_t i;
2234 :
2235 59536 : if (kwds != NULL) {
2236 529 : char *kwlist[] = {"repeat", 0};
2237 529 : PyObject *tmpargs = PyTuple_New(0);
2238 529 : if (tmpargs == NULL)
2239 1 : return NULL;
2240 529 : if (!PyArg_ParseTupleAndKeywords(tmpargs, kwds, "|n:product",
2241 : kwlist, &repeat)) {
2242 1 : Py_DECREF(tmpargs);
2243 1 : return NULL;
2244 : }
2245 528 : Py_DECREF(tmpargs);
2246 528 : if (repeat < 0) {
2247 0 : PyErr_SetString(PyExc_ValueError,
2248 : "repeat argument cannot be negative");
2249 0 : return NULL;
2250 : }
2251 : }
2252 :
2253 59535 : assert(PyTuple_CheckExact(args));
2254 59535 : if (repeat == 0) {
2255 26 : nargs = 0;
2256 : } else {
2257 59509 : nargs = PyTuple_GET_SIZE(args);
2258 59509 : if ((size_t)nargs > PY_SSIZE_T_MAX/sizeof(Py_ssize_t)/repeat) {
2259 0 : PyErr_SetString(PyExc_OverflowError, "repeat argument too large");
2260 0 : return NULL;
2261 : }
2262 : }
2263 59535 : npools = nargs * repeat;
2264 :
2265 59535 : indices = PyMem_New(Py_ssize_t, npools);
2266 59535 : if (indices == NULL) {
2267 0 : PyErr_NoMemory();
2268 0 : goto error;
2269 : }
2270 :
2271 59535 : pools = PyTuple_New(npools);
2272 59535 : if (pools == NULL)
2273 0 : goto error;
2274 :
2275 150442 : for (i=0; i < nargs ; ++i) {
2276 90923 : PyObject *item = PyTuple_GET_ITEM(args, i);
2277 90923 : PyObject *pool = PySequence_Tuple(item);
2278 90923 : if (pool == NULL)
2279 16 : goto error;
2280 90907 : PyTuple_SET_ITEM(pools, i, pool);
2281 90907 : indices[i] = 0;
2282 : }
2283 60510 : for ( ; i < npools; ++i) {
2284 991 : PyObject *pool = PyTuple_GET_ITEM(pools, i - nargs);
2285 991 : Py_INCREF(pool);
2286 991 : PyTuple_SET_ITEM(pools, i, pool);
2287 991 : indices[i] = 0;
2288 : }
2289 :
2290 : /* create productobject structure */
2291 59519 : lz = (productobject *)type->tp_alloc(type, 0);
2292 59519 : if (lz == NULL)
2293 0 : goto error;
2294 :
2295 59519 : lz->pools = pools;
2296 59519 : lz->indices = indices;
2297 59519 : lz->result = NULL;
2298 59519 : lz->stopped = 0;
2299 :
2300 59519 : return (PyObject *)lz;
2301 :
2302 16 : error:
2303 16 : if (indices != NULL)
2304 16 : PyMem_Free(indices);
2305 16 : Py_XDECREF(pools);
2306 16 : return NULL;
2307 : }
2308 :
2309 : static void
2310 59519 : product_dealloc(productobject *lz)
2311 : {
2312 59519 : PyObject_GC_UnTrack(lz);
2313 59519 : Py_XDECREF(lz->pools);
2314 59519 : Py_XDECREF(lz->result);
2315 59519 : if (lz->indices != NULL)
2316 59519 : PyMem_Free(lz->indices);
2317 59519 : Py_TYPE(lz)->tp_free(lz);
2318 59519 : }
2319 :
2320 : static PyObject *
2321 2 : product_sizeof(productobject *lz, void *unused)
2322 : {
2323 : Py_ssize_t res;
2324 :
2325 2 : res = _PyObject_SIZE(Py_TYPE(lz));
2326 2 : res += PyTuple_GET_SIZE(lz->pools) * sizeof(Py_ssize_t);
2327 2 : return PyLong_FromSsize_t(res);
2328 : }
2329 :
2330 : PyDoc_STRVAR(sizeof_doc, "Returns size in memory, in bytes.");
2331 :
2332 : static int
2333 46 : product_traverse(productobject *lz, visitproc visit, void *arg)
2334 : {
2335 46 : Py_VISIT(lz->pools);
2336 46 : Py_VISIT(lz->result);
2337 46 : return 0;
2338 : }
2339 :
2340 : static PyObject *
2341 1470370 : product_next(productobject *lz)
2342 : {
2343 : PyObject *pool;
2344 : PyObject *elem;
2345 : PyObject *oldelem;
2346 1470370 : PyObject *pools = lz->pools;
2347 1470370 : PyObject *result = lz->result;
2348 1470370 : Py_ssize_t npools = PyTuple_GET_SIZE(pools);
2349 : Py_ssize_t i;
2350 :
2351 1470370 : if (lz->stopped)
2352 19 : return NULL;
2353 :
2354 1470360 : if (result == NULL) {
2355 : /* On the first pass, return an initial tuple filled with the
2356 : first element from each pool. */
2357 59485 : result = PyTuple_New(npools);
2358 59485 : if (result == NULL)
2359 0 : goto empty;
2360 59485 : lz->result = result;
2361 150627 : for (i=0; i < npools; i++) {
2362 91474 : pool = PyTuple_GET_ITEM(pools, i);
2363 91474 : if (PyTuple_GET_SIZE(pool) == 0)
2364 332 : goto empty;
2365 91142 : elem = PyTuple_GET_ITEM(pool, 0);
2366 91142 : Py_INCREF(elem);
2367 91142 : PyTuple_SET_ITEM(result, i, elem);
2368 : }
2369 : } else {
2370 1410870 : Py_ssize_t *indices = lz->indices;
2371 :
2372 : /* Copy the previous result tuple or re-use it if available */
2373 1410870 : if (Py_REFCNT(result) > 1) {
2374 1306210 : PyObject *old_result = result;
2375 1306210 : result = _PyTuple_FromArray(_PyTuple_ITEMS(old_result), npools);
2376 1306210 : if (result == NULL)
2377 0 : goto empty;
2378 1306210 : lz->result = result;
2379 1306210 : Py_DECREF(old_result);
2380 : }
2381 : // bpo-42536: The GC may have untracked this result tuple. Since we're
2382 : // recycling it, make sure it's tracked again:
2383 104663 : else if (!_PyObject_GC_IS_TRACKED(result)) {
2384 4 : _PyObject_GC_TRACK(result);
2385 : }
2386 : /* Now, we've got the only copy so we can update it in-place */
2387 1410870 : assert (npools==0 || Py_REFCNT(result) == 1);
2388 :
2389 : /* Update the pool indices right-to-left. Only advance to the
2390 : next pool when the previous one rolls-over */
2391 1750570 : for (i=npools-1 ; i >= 0 ; i--) {
2392 1691940 : pool = PyTuple_GET_ITEM(pools, i);
2393 1691940 : indices[i]++;
2394 1691940 : if (indices[i] == PyTuple_GET_SIZE(pool)) {
2395 : /* Roll-over and advance to next pool */
2396 339702 : indices[i] = 0;
2397 339702 : elem = PyTuple_GET_ITEM(pool, 0);
2398 339702 : Py_INCREF(elem);
2399 339702 : oldelem = PyTuple_GET_ITEM(result, i);
2400 339702 : PyTuple_SET_ITEM(result, i, elem);
2401 339702 : Py_DECREF(oldelem);
2402 : } else {
2403 : /* No rollover. Just increment and stop here. */
2404 1352240 : elem = PyTuple_GET_ITEM(pool, indices[i]);
2405 1352240 : Py_INCREF(elem);
2406 1352240 : oldelem = PyTuple_GET_ITEM(result, i);
2407 1352240 : PyTuple_SET_ITEM(result, i, elem);
2408 1352240 : Py_DECREF(oldelem);
2409 1352240 : break;
2410 : }
2411 : }
2412 :
2413 : /* If i is negative, then the indices have all rolled-over
2414 : and we're done. */
2415 1410870 : if (i < 0)
2416 58633 : goto empty;
2417 : }
2418 :
2419 1411390 : Py_INCREF(result);
2420 1411390 : return result;
2421 :
2422 58965 : empty:
2423 58965 : lz->stopped = 1;
2424 58965 : return NULL;
2425 : }
2426 :
2427 : static PyObject *
2428 84 : product_reduce(productobject *lz, PyObject *Py_UNUSED(ignored))
2429 : {
2430 84 : if (lz->stopped) {
2431 18 : return Py_BuildValue("O(())", Py_TYPE(lz));
2432 66 : } else if (lz->result == NULL) {
2433 48 : return Py_BuildValue("OO", Py_TYPE(lz), lz->pools);
2434 : } else {
2435 : PyObject *indices;
2436 : Py_ssize_t n, i;
2437 :
2438 : /* we must pickle the indices use them for setstate, and
2439 : * additionally indicate that the iterator has started
2440 : */
2441 18 : n = PyTuple_GET_SIZE(lz->pools);
2442 18 : indices = PyTuple_New(n);
2443 18 : if (indices == NULL)
2444 0 : return NULL;
2445 36 : for (i=0; i<n; i++){
2446 18 : PyObject* index = PyLong_FromSsize_t(lz->indices[i]);
2447 18 : if (!index) {
2448 0 : Py_DECREF(indices);
2449 0 : return NULL;
2450 : }
2451 18 : PyTuple_SET_ITEM(indices, i, index);
2452 : }
2453 18 : return Py_BuildValue("OON", Py_TYPE(lz), lz->pools, indices);
2454 : }
2455 : }
2456 :
2457 : static PyObject *
2458 20 : product_setstate(productobject *lz, PyObject *state)
2459 : {
2460 : PyObject *result;
2461 : Py_ssize_t n, i;
2462 :
2463 20 : n = PyTuple_GET_SIZE(lz->pools);
2464 20 : if (!PyTuple_Check(state) || PyTuple_GET_SIZE(state) != n) {
2465 0 : PyErr_SetString(PyExc_ValueError, "invalid arguments");
2466 0 : return NULL;
2467 : }
2468 41 : for (i=0; i<n; i++)
2469 : {
2470 22 : PyObject* indexObject = PyTuple_GET_ITEM(state, i);
2471 22 : Py_ssize_t index = PyLong_AsSsize_t(indexObject);
2472 : PyObject* pool;
2473 : Py_ssize_t poolsize;
2474 22 : if (index < 0 && PyErr_Occurred())
2475 0 : return NULL; /* not an integer */
2476 22 : pool = PyTuple_GET_ITEM(lz->pools, i);
2477 22 : poolsize = PyTuple_GET_SIZE(pool);
2478 22 : if (poolsize == 0) {
2479 1 : lz->stopped = 1;
2480 1 : Py_RETURN_NONE;
2481 : }
2482 : /* clamp the index */
2483 21 : if (index < 0)
2484 0 : index = 0;
2485 21 : else if (index > poolsize-1)
2486 1 : index = poolsize-1;
2487 21 : lz->indices[i] = index;
2488 : }
2489 :
2490 19 : result = PyTuple_New(n);
2491 19 : if (!result)
2492 0 : return NULL;
2493 39 : for (i=0; i<n; i++) {
2494 20 : PyObject *pool = PyTuple_GET_ITEM(lz->pools, i);
2495 20 : PyObject *element = PyTuple_GET_ITEM(pool, lz->indices[i]);
2496 20 : Py_INCREF(element);
2497 20 : PyTuple_SET_ITEM(result, i, element);
2498 : }
2499 19 : Py_XSETREF(lz->result, result);
2500 19 : Py_RETURN_NONE;
2501 : }
2502 :
2503 : static PyMethodDef product_methods[] = {
2504 : {"__reduce__", (PyCFunction)product_reduce, METH_NOARGS,
2505 : reduce_doc},
2506 : {"__setstate__", (PyCFunction)product_setstate, METH_O,
2507 : setstate_doc},
2508 : {"__sizeof__", (PyCFunction)product_sizeof, METH_NOARGS,
2509 : sizeof_doc},
2510 : {NULL, NULL} /* sentinel */
2511 : };
2512 :
2513 : PyDoc_STRVAR(product_doc,
2514 : "product(*iterables, repeat=1) --> product object\n\
2515 : \n\
2516 : Cartesian product of input iterables. Equivalent to nested for-loops.\n\n\
2517 : For example, product(A, B) returns the same as: ((x,y) for x in A for y in B).\n\
2518 : The leftmost iterators are in the outermost for-loop, so the output tuples\n\
2519 : cycle in a manner similar to an odometer (with the rightmost element changing\n\
2520 : on every iteration).\n\n\
2521 : To compute the product of an iterable with itself, specify the number\n\
2522 : of repetitions with the optional repeat keyword argument. For example,\n\
2523 : product(A, repeat=4) means the same as product(A, A, A, A).\n\n\
2524 : product('ab', range(3)) --> ('a',0) ('a',1) ('a',2) ('b',0) ('b',1) ('b',2)\n\
2525 : product((0,1), (0,1), (0,1)) --> (0,0,0) (0,0,1) (0,1,0) (0,1,1) (1,0,0) ...");
2526 :
2527 : static PyTypeObject product_type = {
2528 : PyVarObject_HEAD_INIT(NULL, 0)
2529 : "itertools.product", /* tp_name */
2530 : sizeof(productobject), /* tp_basicsize */
2531 : 0, /* tp_itemsize */
2532 : /* methods */
2533 : (destructor)product_dealloc, /* tp_dealloc */
2534 : 0, /* tp_vectorcall_offset */
2535 : 0, /* tp_getattr */
2536 : 0, /* tp_setattr */
2537 : 0, /* tp_as_async */
2538 : 0, /* tp_repr */
2539 : 0, /* tp_as_number */
2540 : 0, /* tp_as_sequence */
2541 : 0, /* tp_as_mapping */
2542 : 0, /* tp_hash */
2543 : 0, /* tp_call */
2544 : 0, /* tp_str */
2545 : PyObject_GenericGetAttr, /* tp_getattro */
2546 : 0, /* tp_setattro */
2547 : 0, /* tp_as_buffer */
2548 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2549 : Py_TPFLAGS_BASETYPE, /* tp_flags */
2550 : product_doc, /* tp_doc */
2551 : (traverseproc)product_traverse, /* tp_traverse */
2552 : 0, /* tp_clear */
2553 : 0, /* tp_richcompare */
2554 : 0, /* tp_weaklistoffset */
2555 : PyObject_SelfIter, /* tp_iter */
2556 : (iternextfunc)product_next, /* tp_iternext */
2557 : product_methods, /* tp_methods */
2558 : 0, /* tp_members */
2559 : 0, /* tp_getset */
2560 : 0, /* tp_base */
2561 : 0, /* tp_dict */
2562 : 0, /* tp_descr_get */
2563 : 0, /* tp_descr_set */
2564 : 0, /* tp_dictoffset */
2565 : 0, /* tp_init */
2566 : 0, /* tp_alloc */
2567 : product_new, /* tp_new */
2568 : PyObject_GC_Del, /* tp_free */
2569 : };
2570 :
2571 :
2572 : /* combinations object *******************************************************/
2573 :
2574 : typedef struct {
2575 : PyObject_HEAD
2576 : PyObject *pool; /* input converted to a tuple */
2577 : Py_ssize_t *indices; /* one index per result element */
2578 : PyObject *result; /* most recently returned result tuple */
2579 : Py_ssize_t r; /* size of result tuple */
2580 : int stopped; /* set to 1 when the iterator is exhausted */
2581 : } combinationsobject;
2582 :
2583 :
2584 : /*[clinic input]
2585 : @classmethod
2586 : itertools.combinations.__new__
2587 : iterable: object
2588 : r: Py_ssize_t
2589 : Return successive r-length combinations of elements in the iterable.
2590 :
2591 : combinations(range(4), 3) --> (0,1,2), (0,1,3), (0,2,3), (1,2,3)
2592 : [clinic start generated code]*/
2593 :
2594 : static PyObject *
2595 6012 : itertools_combinations_impl(PyTypeObject *type, PyObject *iterable,
2596 : Py_ssize_t r)
2597 : /*[clinic end generated code: output=87a689b39c40039c input=06bede09e3da20f8]*/
2598 : {
2599 : combinationsobject *co;
2600 : Py_ssize_t n;
2601 6012 : PyObject *pool = NULL;
2602 6012 : Py_ssize_t *indices = NULL;
2603 : Py_ssize_t i;
2604 :
2605 6012 : pool = PySequence_Tuple(iterable);
2606 6012 : if (pool == NULL)
2607 0 : goto error;
2608 6012 : n = PyTuple_GET_SIZE(pool);
2609 6012 : if (r < 0) {
2610 1 : PyErr_SetString(PyExc_ValueError, "r must be non-negative");
2611 1 : goto error;
2612 : }
2613 :
2614 6011 : indices = PyMem_New(Py_ssize_t, r);
2615 6011 : if (indices == NULL) {
2616 0 : PyErr_NoMemory();
2617 0 : goto error;
2618 : }
2619 :
2620 23548 : for (i=0 ; i<r ; i++)
2621 17537 : indices[i] = i;
2622 :
2623 : /* create combinationsobject structure */
2624 6011 : co = (combinationsobject *)type->tp_alloc(type, 0);
2625 6011 : if (co == NULL)
2626 0 : goto error;
2627 :
2628 6011 : co->pool = pool;
2629 6011 : co->indices = indices;
2630 6011 : co->result = NULL;
2631 6011 : co->r = r;
2632 6011 : co->stopped = r > n ? 1 : 0;
2633 :
2634 6011 : return (PyObject *)co;
2635 :
2636 1 : error:
2637 1 : if (indices != NULL)
2638 0 : PyMem_Free(indices);
2639 1 : Py_XDECREF(pool);
2640 1 : return NULL;
2641 : }
2642 :
2643 : static void
2644 6011 : combinations_dealloc(combinationsobject *co)
2645 : {
2646 6011 : PyObject_GC_UnTrack(co);
2647 6011 : Py_XDECREF(co->pool);
2648 6011 : Py_XDECREF(co->result);
2649 6011 : if (co->indices != NULL)
2650 6011 : PyMem_Free(co->indices);
2651 6011 : Py_TYPE(co)->tp_free(co);
2652 6011 : }
2653 :
2654 : static PyObject *
2655 2 : combinations_sizeof(combinationsobject *co, void *unused)
2656 : {
2657 : Py_ssize_t res;
2658 :
2659 2 : res = _PyObject_SIZE(Py_TYPE(co));
2660 2 : res += co->r * sizeof(Py_ssize_t);
2661 2 : return PyLong_FromSsize_t(res);
2662 : }
2663 :
2664 : static int
2665 14 : combinations_traverse(combinationsobject *co, visitproc visit, void *arg)
2666 : {
2667 14 : Py_VISIT(co->pool);
2668 14 : Py_VISIT(co->result);
2669 14 : return 0;
2670 : }
2671 :
2672 : static PyObject *
2673 1079380 : combinations_next(combinationsobject *co)
2674 : {
2675 : PyObject *elem;
2676 : PyObject *oldelem;
2677 1079380 : PyObject *pool = co->pool;
2678 1079380 : Py_ssize_t *indices = co->indices;
2679 1079380 : PyObject *result = co->result;
2680 1079380 : Py_ssize_t n = PyTuple_GET_SIZE(pool);
2681 1079380 : Py_ssize_t r = co->r;
2682 : Py_ssize_t i, j, index;
2683 :
2684 1079380 : if (co->stopped)
2685 258 : return NULL;
2686 :
2687 1079120 : if (result == NULL) {
2688 : /* On the first pass, initialize result tuple using the indices */
2689 5595 : result = PyTuple_New(r);
2690 5595 : if (result == NULL)
2691 0 : goto empty;
2692 5595 : co->result = result;
2693 21452 : for (i=0; i<r ; i++) {
2694 15857 : index = indices[i];
2695 15857 : elem = PyTuple_GET_ITEM(pool, index);
2696 15857 : Py_INCREF(elem);
2697 15857 : PyTuple_SET_ITEM(result, i, elem);
2698 : }
2699 : } else {
2700 : /* Copy the previous result tuple or re-use it if available */
2701 1073520 : if (Py_REFCNT(result) > 1) {
2702 24717 : PyObject *old_result = result;
2703 24717 : result = _PyTuple_FromArray(_PyTuple_ITEMS(old_result), r);
2704 24717 : if (result == NULL)
2705 0 : goto empty;
2706 24717 : co->result = result;
2707 24717 : Py_DECREF(old_result);
2708 : }
2709 : // bpo-42536: The GC may have untracked this result tuple. Since we're
2710 : // recycling it, make sure it's tracked again:
2711 1048800 : else if (!_PyObject_GC_IS_TRACKED(result)) {
2712 1 : _PyObject_GC_TRACK(result);
2713 : }
2714 : /* Now, we've got the only copy so we can update it in-place
2715 : * CPython's empty tuple is a singleton and cached in
2716 : * PyTuple's freelist.
2717 : */
2718 1073520 : assert(r == 0 || Py_REFCNT(result) == 1);
2719 :
2720 : /* Scan indices right-to-left until finding one that is not
2721 : at its maximum (i + n - r). */
2722 2145760 : for (i=r-1 ; i >= 0 && indices[i] == i+n-r ; i--)
2723 : ;
2724 :
2725 : /* If i is negative, then the indices are all at
2726 : their maximum value and we're done. */
2727 1073520 : if (i < 0)
2728 5497 : goto empty;
2729 :
2730 : /* Increment the current index which we know is not at its
2731 : maximum. Then move back to the right setting each index
2732 : to its lowest possible value (one higher than the index
2733 : to its left -- this maintains the sort order invariant). */
2734 1068020 : indices[i]++;
2735 2124770 : for (j=i+1 ; j<r ; j++)
2736 1056740 : indices[j] = indices[j-1] + 1;
2737 :
2738 : /* Update the result tuple for the new indices
2739 : starting with i, the leftmost index that changed */
2740 3192800 : for ( ; i<r ; i++) {
2741 2124770 : index = indices[i];
2742 2124770 : elem = PyTuple_GET_ITEM(pool, index);
2743 2124770 : Py_INCREF(elem);
2744 2124770 : oldelem = PyTuple_GET_ITEM(result, i);
2745 2124770 : PyTuple_SET_ITEM(result, i, elem);
2746 2124770 : Py_DECREF(oldelem);
2747 : }
2748 : }
2749 :
2750 1073620 : Py_INCREF(result);
2751 1073620 : return result;
2752 :
2753 5497 : empty:
2754 5497 : co->stopped = 1;
2755 5497 : return NULL;
2756 : }
2757 :
2758 : static PyObject *
2759 450 : combinations_reduce(combinationsobject *lz, PyObject *Py_UNUSED(ignored))
2760 : {
2761 450 : if (lz->result == NULL) {
2762 270 : return Py_BuildValue("O(On)", Py_TYPE(lz), lz->pool, lz->r);
2763 180 : } else if (lz->stopped) {
2764 0 : return Py_BuildValue("O(()n)", Py_TYPE(lz), lz->r);
2765 : } else {
2766 : PyObject *indices;
2767 : Py_ssize_t i;
2768 :
2769 : /* we must pickle the indices and use them for setstate */
2770 180 : indices = PyTuple_New(lz->r);
2771 180 : if (!indices)
2772 0 : return NULL;
2773 546 : for (i=0; i<lz->r; i++)
2774 : {
2775 366 : PyObject* index = PyLong_FromSsize_t(lz->indices[i]);
2776 366 : if (!index) {
2777 0 : Py_DECREF(indices);
2778 0 : return NULL;
2779 : }
2780 366 : PyTuple_SET_ITEM(indices, i, index);
2781 : }
2782 :
2783 180 : return Py_BuildValue("O(On)N", Py_TYPE(lz), lz->pool, lz->r, indices);
2784 : }
2785 : }
2786 :
2787 : static PyObject *
2788 180 : combinations_setstate(combinationsobject *lz, PyObject *state)
2789 : {
2790 : PyObject *result;
2791 : Py_ssize_t i;
2792 180 : Py_ssize_t n = PyTuple_GET_SIZE(lz->pool);
2793 :
2794 180 : if (!PyTuple_Check(state) || PyTuple_GET_SIZE(state) != lz->r) {
2795 0 : PyErr_SetString(PyExc_ValueError, "invalid arguments");
2796 0 : return NULL;
2797 : }
2798 :
2799 546 : for (i=0; i<lz->r; i++) {
2800 : Py_ssize_t max;
2801 366 : PyObject* indexObject = PyTuple_GET_ITEM(state, i);
2802 366 : Py_ssize_t index = PyLong_AsSsize_t(indexObject);
2803 :
2804 366 : if (index == -1 && PyErr_Occurred())
2805 0 : return NULL; /* not an integer */
2806 366 : max = i + n - lz->r;
2807 : /* clamp the index (beware of negative max) */
2808 366 : if (index > max)
2809 0 : index = max;
2810 366 : if (index < 0)
2811 0 : index = 0;
2812 366 : lz->indices[i] = index;
2813 : }
2814 :
2815 180 : result = PyTuple_New(lz->r);
2816 180 : if (result == NULL)
2817 0 : return NULL;
2818 546 : for (i=0; i<lz->r; i++) {
2819 366 : PyObject *element = PyTuple_GET_ITEM(lz->pool, lz->indices[i]);
2820 366 : Py_INCREF(element);
2821 366 : PyTuple_SET_ITEM(result, i, element);
2822 : }
2823 :
2824 180 : Py_XSETREF(lz->result, result);
2825 180 : Py_RETURN_NONE;
2826 : }
2827 :
2828 : static PyMethodDef combinations_methods[] = {
2829 : {"__reduce__", (PyCFunction)combinations_reduce, METH_NOARGS,
2830 : reduce_doc},
2831 : {"__setstate__", (PyCFunction)combinations_setstate, METH_O,
2832 : setstate_doc},
2833 : {"__sizeof__", (PyCFunction)combinations_sizeof, METH_NOARGS,
2834 : sizeof_doc},
2835 : {NULL, NULL} /* sentinel */
2836 : };
2837 :
2838 : static PyTypeObject combinations_type = {
2839 : PyVarObject_HEAD_INIT(NULL, 0)
2840 : "itertools.combinations", /* tp_name */
2841 : sizeof(combinationsobject), /* tp_basicsize */
2842 : 0, /* tp_itemsize */
2843 : /* methods */
2844 : (destructor)combinations_dealloc, /* tp_dealloc */
2845 : 0, /* tp_vectorcall_offset */
2846 : 0, /* tp_getattr */
2847 : 0, /* tp_setattr */
2848 : 0, /* tp_as_async */
2849 : 0, /* tp_repr */
2850 : 0, /* tp_as_number */
2851 : 0, /* tp_as_sequence */
2852 : 0, /* tp_as_mapping */
2853 : 0, /* tp_hash */
2854 : 0, /* tp_call */
2855 : 0, /* tp_str */
2856 : PyObject_GenericGetAttr, /* tp_getattro */
2857 : 0, /* tp_setattro */
2858 : 0, /* tp_as_buffer */
2859 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
2860 : Py_TPFLAGS_BASETYPE, /* tp_flags */
2861 : itertools_combinations__doc__, /* tp_doc */
2862 : (traverseproc)combinations_traverse,/* tp_traverse */
2863 : 0, /* tp_clear */
2864 : 0, /* tp_richcompare */
2865 : 0, /* tp_weaklistoffset */
2866 : PyObject_SelfIter, /* tp_iter */
2867 : (iternextfunc)combinations_next, /* tp_iternext */
2868 : combinations_methods, /* tp_methods */
2869 : 0, /* tp_members */
2870 : 0, /* tp_getset */
2871 : 0, /* tp_base */
2872 : 0, /* tp_dict */
2873 : 0, /* tp_descr_get */
2874 : 0, /* tp_descr_set */
2875 : 0, /* tp_dictoffset */
2876 : 0, /* tp_init */
2877 : 0, /* tp_alloc */
2878 : itertools_combinations, /* tp_new */
2879 : PyObject_GC_Del, /* tp_free */
2880 : };
2881 :
2882 :
2883 : /* combinations with replacement object **************************************/
2884 :
2885 : /* Equivalent to:
2886 :
2887 : def combinations_with_replacement(iterable, r):
2888 : "combinations_with_replacement('ABC', 2) --> AA AB AC BB BC CC"
2889 : # number items returned: (n+r-1)! / r! / (n-1)!
2890 : pool = tuple(iterable)
2891 : n = len(pool)
2892 : indices = [0] * r
2893 : yield tuple(pool[i] for i in indices)
2894 : while 1:
2895 : for i in reversed(range(r)):
2896 : if indices[i] != n - 1:
2897 : break
2898 : else:
2899 : return
2900 : indices[i:] = [indices[i] + 1] * (r - i)
2901 : yield tuple(pool[i] for i in indices)
2902 :
2903 : def combinations_with_replacement2(iterable, r):
2904 : 'Alternate version that filters from product()'
2905 : pool = tuple(iterable)
2906 : n = len(pool)
2907 : for indices in product(range(n), repeat=r):
2908 : if sorted(indices) == list(indices):
2909 : yield tuple(pool[i] for i in indices)
2910 : */
2911 : typedef struct {
2912 : PyObject_HEAD
2913 : PyObject *pool; /* input converted to a tuple */
2914 : Py_ssize_t *indices; /* one index per result element */
2915 : PyObject *result; /* most recently returned result tuple */
2916 : Py_ssize_t r; /* size of result tuple */
2917 : int stopped; /* set to 1 when the cwr iterator is exhausted */
2918 : } cwrobject;
2919 :
2920 : /*[clinic input]
2921 : @classmethod
2922 : itertools.combinations_with_replacement.__new__
2923 : iterable: object
2924 : r: Py_ssize_t
2925 : Return successive r-length combinations of elements in the iterable allowing individual elements to have successive repeats.
2926 :
2927 : combinations_with_replacement('ABC', 2) --> ('A','A'), ('A','B'), ('A','C'), ('B','B'), ('B','C'), ('C','C')
2928 : [clinic start generated code]*/
2929 :
2930 : static PyObject *
2931 998 : itertools_combinations_with_replacement_impl(PyTypeObject *type,
2932 : PyObject *iterable,
2933 : Py_ssize_t r)
2934 : /*[clinic end generated code: output=48b26856d4e659ca input=1dc58e82a0878fdc]*/
2935 : {
2936 : cwrobject *co;
2937 : Py_ssize_t n;
2938 998 : PyObject *pool = NULL;
2939 998 : Py_ssize_t *indices = NULL;
2940 : Py_ssize_t i;
2941 :
2942 998 : pool = PySequence_Tuple(iterable);
2943 998 : if (pool == NULL)
2944 0 : goto error;
2945 998 : n = PyTuple_GET_SIZE(pool);
2946 998 : if (r < 0) {
2947 1 : PyErr_SetString(PyExc_ValueError, "r must be non-negative");
2948 1 : goto error;
2949 : }
2950 :
2951 997 : indices = PyMem_New(Py_ssize_t, r);
2952 997 : if (indices == NULL) {
2953 0 : PyErr_NoMemory();
2954 0 : goto error;
2955 : }
2956 :
2957 3420 : for (i=0 ; i<r ; i++)
2958 2423 : indices[i] = 0;
2959 :
2960 : /* create cwrobject structure */
2961 997 : co = (cwrobject *)type->tp_alloc(type, 0);
2962 997 : if (co == NULL)
2963 0 : goto error;
2964 :
2965 997 : co->pool = pool;
2966 997 : co->indices = indices;
2967 997 : co->result = NULL;
2968 997 : co->r = r;
2969 997 : co->stopped = !n && r;
2970 :
2971 997 : return (PyObject *)co;
2972 :
2973 1 : error:
2974 1 : if (indices != NULL)
2975 0 : PyMem_Free(indices);
2976 1 : Py_XDECREF(pool);
2977 1 : return NULL;
2978 : }
2979 :
2980 : static void
2981 997 : cwr_dealloc(cwrobject *co)
2982 : {
2983 997 : PyObject_GC_UnTrack(co);
2984 997 : Py_XDECREF(co->pool);
2985 997 : Py_XDECREF(co->result);
2986 997 : if (co->indices != NULL)
2987 997 : PyMem_Free(co->indices);
2988 997 : Py_TYPE(co)->tp_free(co);
2989 997 : }
2990 :
2991 : static PyObject *
2992 2 : cwr_sizeof(cwrobject *co, void *unused)
2993 : {
2994 : Py_ssize_t res;
2995 :
2996 2 : res = _PyObject_SIZE(Py_TYPE(co));
2997 2 : res += co->r * sizeof(Py_ssize_t);
2998 2 : return PyLong_FromSsize_t(res);
2999 : }
3000 :
3001 : static int
3002 18 : cwr_traverse(cwrobject *co, visitproc visit, void *arg)
3003 : {
3004 18 : Py_VISIT(co->pool);
3005 18 : Py_VISIT(co->result);
3006 18 : return 0;
3007 : }
3008 :
3009 : static PyObject *
3010 9195 : cwr_next(cwrobject *co)
3011 : {
3012 : PyObject *elem;
3013 : PyObject *oldelem;
3014 9195 : PyObject *pool = co->pool;
3015 9195 : Py_ssize_t *indices = co->indices;
3016 9195 : PyObject *result = co->result;
3017 9195 : Py_ssize_t n = PyTuple_GET_SIZE(pool);
3018 9195 : Py_ssize_t r = co->r;
3019 : Py_ssize_t i, index;
3020 :
3021 9195 : if (co->stopped)
3022 39 : return NULL;
3023 :
3024 9156 : if (result == NULL) {
3025 : /* On the first pass, initialize result tuple with pool[0] */
3026 746 : result = PyTuple_New(r);
3027 746 : if (result == NULL)
3028 0 : goto empty;
3029 746 : co->result = result;
3030 746 : if (n > 0) {
3031 725 : elem = PyTuple_GET_ITEM(pool, 0);
3032 2565 : for (i=0; i<r ; i++) {
3033 1840 : assert(indices[i] == 0);
3034 1840 : Py_INCREF(elem);
3035 1840 : PyTuple_SET_ITEM(result, i, elem);
3036 : }
3037 : }
3038 : } else {
3039 : /* Copy the previous result tuple or re-use it if available */
3040 8410 : if (Py_REFCNT(result) > 1) {
3041 8043 : PyObject *old_result = result;
3042 8043 : result = _PyTuple_FromArray(_PyTuple_ITEMS(old_result), r);
3043 8043 : if (result == NULL)
3044 0 : goto empty;
3045 8043 : co->result = result;
3046 8043 : Py_DECREF(old_result);
3047 : }
3048 : // bpo-42536: The GC may have untracked this result tuple. Since we're
3049 : // recycling it, make sure it's tracked again:
3050 367 : else if (!_PyObject_GC_IS_TRACKED(result)) {
3051 1 : _PyObject_GC_TRACK(result);
3052 : }
3053 : /* Now, we've got the only copy so we can update it in-place CPython's
3054 : empty tuple is a singleton and cached in PyTuple's freelist. */
3055 8410 : assert(r == 0 || Py_REFCNT(result) == 1);
3056 :
3057 : /* Scan indices right-to-left until finding one that is not
3058 : * at its maximum (n-1). */
3059 15356 : for (i=r-1 ; i >= 0 && indices[i] == n-1; i--)
3060 : ;
3061 :
3062 : /* If i is negative, then the indices are all at
3063 : their maximum value and we're done. */
3064 8410 : if (i < 0)
3065 438 : goto empty;
3066 :
3067 : /* Increment the current index which we know is not at its
3068 : maximum. Then set all to the right to the same value. */
3069 7972 : index = indices[i] + 1;
3070 7972 : assert(index < n);
3071 7972 : elem = PyTuple_GET_ITEM(pool, index);
3072 22332 : for ( ; i<r ; i++) {
3073 14360 : indices[i] = index;
3074 14360 : Py_INCREF(elem);
3075 14360 : oldelem = PyTuple_GET_ITEM(result, i);
3076 14360 : PyTuple_SET_ITEM(result, i, elem);
3077 14360 : Py_DECREF(oldelem);
3078 : }
3079 : }
3080 :
3081 8718 : Py_INCREF(result);
3082 8718 : return result;
3083 :
3084 438 : empty:
3085 438 : co->stopped = 1;
3086 438 : return NULL;
3087 : }
3088 :
3089 : static PyObject *
3090 432 : cwr_reduce(cwrobject *lz, PyObject *Py_UNUSED(ignored))
3091 : {
3092 432 : if (lz->result == NULL) {
3093 222 : return Py_BuildValue("O(On)", Py_TYPE(lz), lz->pool, lz->r);
3094 210 : } else if (lz->stopped) {
3095 0 : return Py_BuildValue("O(()n)", Py_TYPE(lz), lz->r);
3096 : } else {
3097 : PyObject *indices;
3098 : Py_ssize_t i;
3099 :
3100 : /* we must pickle the indices and use them for setstate */
3101 210 : indices = PyTuple_New(lz->r);
3102 210 : if (!indices)
3103 0 : return NULL;
3104 720 : for (i=0; i<lz->r; i++) {
3105 510 : PyObject* index = PyLong_FromSsize_t(lz->indices[i]);
3106 510 : if (!index) {
3107 0 : Py_DECREF(indices);
3108 0 : return NULL;
3109 : }
3110 510 : PyTuple_SET_ITEM(indices, i, index);
3111 : }
3112 :
3113 210 : return Py_BuildValue("O(On)N", Py_TYPE(lz), lz->pool, lz->r, indices);
3114 : }
3115 : }
3116 :
3117 : static PyObject *
3118 210 : cwr_setstate(cwrobject *lz, PyObject *state)
3119 : {
3120 : PyObject *result;
3121 : Py_ssize_t n, i;
3122 :
3123 210 : if (!PyTuple_Check(state) || PyTuple_GET_SIZE(state) != lz->r)
3124 : {
3125 0 : PyErr_SetString(PyExc_ValueError, "invalid arguments");
3126 0 : return NULL;
3127 : }
3128 :
3129 210 : n = PyTuple_GET_SIZE(lz->pool);
3130 720 : for (i=0; i<lz->r; i++) {
3131 510 : PyObject* indexObject = PyTuple_GET_ITEM(state, i);
3132 510 : Py_ssize_t index = PyLong_AsSsize_t(indexObject);
3133 :
3134 510 : if (index < 0 && PyErr_Occurred())
3135 0 : return NULL; /* not an integer */
3136 : /* clamp the index */
3137 510 : if (index < 0)
3138 0 : index = 0;
3139 510 : else if (index > n-1)
3140 0 : index = n-1;
3141 510 : lz->indices[i] = index;
3142 : }
3143 210 : result = PyTuple_New(lz->r);
3144 210 : if (result == NULL)
3145 0 : return NULL;
3146 720 : for (i=0; i<lz->r; i++) {
3147 510 : PyObject *element = PyTuple_GET_ITEM(lz->pool, lz->indices[i]);
3148 510 : Py_INCREF(element);
3149 510 : PyTuple_SET_ITEM(result, i, element);
3150 : }
3151 210 : Py_XSETREF(lz->result, result);
3152 210 : Py_RETURN_NONE;
3153 : }
3154 :
3155 : static PyMethodDef cwr_methods[] = {
3156 : {"__reduce__", (PyCFunction)cwr_reduce, METH_NOARGS,
3157 : reduce_doc},
3158 : {"__setstate__", (PyCFunction)cwr_setstate, METH_O,
3159 : setstate_doc},
3160 : {"__sizeof__", (PyCFunction)cwr_sizeof, METH_NOARGS,
3161 : sizeof_doc},
3162 : {NULL, NULL} /* sentinel */
3163 : };
3164 :
3165 : static PyTypeObject cwr_type = {
3166 : PyVarObject_HEAD_INIT(NULL, 0)
3167 : "itertools.combinations_with_replacement", /* tp_name */
3168 : sizeof(cwrobject), /* tp_basicsize */
3169 : 0, /* tp_itemsize */
3170 : /* methods */
3171 : (destructor)cwr_dealloc, /* tp_dealloc */
3172 : 0, /* tp_vectorcall_offset */
3173 : 0, /* tp_getattr */
3174 : 0, /* tp_setattr */
3175 : 0, /* tp_as_async */
3176 : 0, /* tp_repr */
3177 : 0, /* tp_as_number */
3178 : 0, /* tp_as_sequence */
3179 : 0, /* tp_as_mapping */
3180 : 0, /* tp_hash */
3181 : 0, /* tp_call */
3182 : 0, /* tp_str */
3183 : PyObject_GenericGetAttr, /* tp_getattro */
3184 : 0, /* tp_setattro */
3185 : 0, /* tp_as_buffer */
3186 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3187 : Py_TPFLAGS_BASETYPE, /* tp_flags */
3188 : itertools_combinations_with_replacement__doc__, /* tp_doc */
3189 : (traverseproc)cwr_traverse, /* tp_traverse */
3190 : 0, /* tp_clear */
3191 : 0, /* tp_richcompare */
3192 : 0, /* tp_weaklistoffset */
3193 : PyObject_SelfIter, /* tp_iter */
3194 : (iternextfunc)cwr_next, /* tp_iternext */
3195 : cwr_methods, /* tp_methods */
3196 : 0, /* tp_members */
3197 : 0, /* tp_getset */
3198 : 0, /* tp_base */
3199 : 0, /* tp_dict */
3200 : 0, /* tp_descr_get */
3201 : 0, /* tp_descr_set */
3202 : 0, /* tp_dictoffset */
3203 : 0, /* tp_init */
3204 : 0, /* tp_alloc */
3205 : itertools_combinations_with_replacement, /* tp_new */
3206 : PyObject_GC_Del, /* tp_free */
3207 : };
3208 :
3209 :
3210 : /* permutations object ********************************************************
3211 :
3212 : def permutations(iterable, r=None):
3213 : # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
3214 : # permutations(range(3)) --> 012 021 102 120 201 210
3215 : pool = tuple(iterable)
3216 : n = len(pool)
3217 : r = n if r is None else r
3218 : if r > n:
3219 : return
3220 : indices = list(range(n))
3221 : cycles = list(range(n, n-r, -1))
3222 : yield tuple(pool[i] for i in indices[:r])
3223 : while n:
3224 : for i in reversed(range(r)):
3225 : cycles[i] -= 1
3226 : if cycles[i] == 0:
3227 : indices[i:] = indices[i+1:] + indices[i:i+1]
3228 : cycles[i] = n - i
3229 : else:
3230 : j = cycles[i]
3231 : indices[i], indices[-j] = indices[-j], indices[i]
3232 : yield tuple(pool[i] for i in indices[:r])
3233 : break
3234 : else:
3235 : return
3236 : */
3237 :
3238 : typedef struct {
3239 : PyObject_HEAD
3240 : PyObject *pool; /* input converted to a tuple */
3241 : Py_ssize_t *indices; /* one index per element in the pool */
3242 : Py_ssize_t *cycles; /* one rollover counter per element in the result */
3243 : PyObject *result; /* most recently returned result tuple */
3244 : Py_ssize_t r; /* size of result tuple */
3245 : int stopped; /* set to 1 when the iterator is exhausted */
3246 : } permutationsobject;
3247 :
3248 : /*[clinic input]
3249 : @classmethod
3250 : itertools.permutations.__new__
3251 : iterable: object
3252 : r as robj: object = None
3253 : Return successive r-length permutations of elements in the iterable.
3254 :
3255 : permutations(range(3), 2) --> (0,1), (0,2), (1,0), (1,2), (2,0), (2,1)
3256 : [clinic start generated code]*/
3257 :
3258 : static PyObject *
3259 28303 : itertools_permutations_impl(PyTypeObject *type, PyObject *iterable,
3260 : PyObject *robj)
3261 : /*[clinic end generated code: output=296a72fa76d620ea input=57d0170a4ac0ec7a]*/
3262 : {
3263 : permutationsobject *po;
3264 : Py_ssize_t n;
3265 : Py_ssize_t r;
3266 28303 : PyObject *pool = NULL;
3267 28303 : Py_ssize_t *indices = NULL;
3268 28303 : Py_ssize_t *cycles = NULL;
3269 : Py_ssize_t i;
3270 :
3271 28303 : pool = PySequence_Tuple(iterable);
3272 28303 : if (pool == NULL)
3273 1 : goto error;
3274 28302 : n = PyTuple_GET_SIZE(pool);
3275 :
3276 28302 : r = n;
3277 28302 : if (robj != Py_None) {
3278 973 : if (!PyLong_Check(robj)) {
3279 1 : PyErr_SetString(PyExc_TypeError, "Expected int as r");
3280 1 : goto error;
3281 : }
3282 972 : r = PyLong_AsSsize_t(robj);
3283 972 : if (r == -1 && PyErr_Occurred())
3284 0 : goto error;
3285 : }
3286 28301 : if (r < 0) {
3287 1 : PyErr_SetString(PyExc_ValueError, "r must be non-negative");
3288 1 : goto error;
3289 : }
3290 :
3291 28300 : indices = PyMem_New(Py_ssize_t, n);
3292 28300 : cycles = PyMem_New(Py_ssize_t, r);
3293 28300 : if (indices == NULL || cycles == NULL) {
3294 0 : PyErr_NoMemory();
3295 0 : goto error;
3296 : }
3297 :
3298 68414 : for (i=0 ; i<n ; i++)
3299 40114 : indices[i] = i;
3300 67196 : for (i=0 ; i<r ; i++)
3301 38896 : cycles[i] = n - i;
3302 :
3303 : /* create permutationsobject structure */
3304 28300 : po = (permutationsobject *)type->tp_alloc(type, 0);
3305 28300 : if (po == NULL)
3306 0 : goto error;
3307 :
3308 28300 : po->pool = pool;
3309 28300 : po->indices = indices;
3310 28300 : po->cycles = cycles;
3311 28300 : po->result = NULL;
3312 28300 : po->r = r;
3313 28300 : po->stopped = r > n ? 1 : 0;
3314 :
3315 28300 : return (PyObject *)po;
3316 :
3317 3 : error:
3318 3 : if (indices != NULL)
3319 0 : PyMem_Free(indices);
3320 3 : if (cycles != NULL)
3321 0 : PyMem_Free(cycles);
3322 3 : Py_XDECREF(pool);
3323 3 : return NULL;
3324 : }
3325 :
3326 : static void
3327 28300 : permutations_dealloc(permutationsobject *po)
3328 : {
3329 28300 : PyObject_GC_UnTrack(po);
3330 28300 : Py_XDECREF(po->pool);
3331 28300 : Py_XDECREF(po->result);
3332 28300 : PyMem_Free(po->indices);
3333 28300 : PyMem_Free(po->cycles);
3334 28300 : Py_TYPE(po)->tp_free(po);
3335 28300 : }
3336 :
3337 : static PyObject *
3338 4 : permutations_sizeof(permutationsobject *po, void *unused)
3339 : {
3340 : Py_ssize_t res;
3341 :
3342 4 : res = _PyObject_SIZE(Py_TYPE(po));
3343 4 : res += PyTuple_GET_SIZE(po->pool) * sizeof(Py_ssize_t);
3344 4 : res += po->r * sizeof(Py_ssize_t);
3345 4 : return PyLong_FromSsize_t(res);
3346 : }
3347 :
3348 : static int
3349 18 : permutations_traverse(permutationsobject *po, visitproc visit, void *arg)
3350 : {
3351 18 : Py_VISIT(po->pool);
3352 18 : Py_VISIT(po->result);
3353 18 : return 0;
3354 : }
3355 :
3356 : static PyObject *
3357 73642 : permutations_next(permutationsobject *po)
3358 : {
3359 : PyObject *elem;
3360 : PyObject *oldelem;
3361 73642 : PyObject *pool = po->pool;
3362 73642 : Py_ssize_t *indices = po->indices;
3363 73642 : Py_ssize_t *cycles = po->cycles;
3364 73642 : PyObject *result = po->result;
3365 73642 : Py_ssize_t n = PyTuple_GET_SIZE(pool);
3366 73642 : Py_ssize_t r = po->r;
3367 : Py_ssize_t i, j, k, index;
3368 :
3369 73642 : if (po->stopped)
3370 252 : return NULL;
3371 :
3372 73390 : if (result == NULL) {
3373 : /* On the first pass, initialize result tuple using the indices */
3374 27918 : result = PyTuple_New(r);
3375 27918 : if (result == NULL)
3376 0 : goto empty;
3377 27918 : po->result = result;
3378 65571 : for (i=0; i<r ; i++) {
3379 37653 : index = indices[i];
3380 37653 : elem = PyTuple_GET_ITEM(pool, index);
3381 37653 : Py_INCREF(elem);
3382 37653 : PyTuple_SET_ITEM(result, i, elem);
3383 : }
3384 : } else {
3385 45472 : if (n == 0)
3386 29 : goto empty;
3387 :
3388 : /* Copy the previous result tuple or re-use it if available */
3389 45443 : if (Py_REFCNT(result) > 1) {
3390 45130 : PyObject *old_result = result;
3391 45130 : result = _PyTuple_FromArray(_PyTuple_ITEMS(old_result), r);
3392 45130 : if (result == NULL)
3393 0 : goto empty;
3394 45130 : po->result = result;
3395 45130 : Py_DECREF(old_result);
3396 : }
3397 : // bpo-42536: The GC may have untracked this result tuple. Since we're
3398 : // recycling it, make sure it's tracked again:
3399 313 : else if (!_PyObject_GC_IS_TRACKED(result)) {
3400 1 : _PyObject_GC_TRACK(result);
3401 : }
3402 : /* Now, we've got the only copy so we can update it in-place */
3403 45443 : assert(r == 0 || Py_REFCNT(result) == 1);
3404 :
3405 : /* Decrement rightmost cycle, moving leftward upon zero rollover */
3406 100399 : for (i=r-1 ; i>=0 ; i--) {
3407 72740 : cycles[i] -= 1;
3408 72740 : if (cycles[i] == 0) {
3409 : /* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
3410 54956 : index = indices[i];
3411 71863 : for (j=i ; j<n-1 ; j++)
3412 16907 : indices[j] = indices[j+1];
3413 54956 : indices[n-1] = index;
3414 54956 : cycles[i] = n - i;
3415 : } else {
3416 17784 : j = cycles[i];
3417 17784 : index = indices[i];
3418 17784 : indices[i] = indices[n-j];
3419 17784 : indices[n-j] = index;
3420 :
3421 53751 : for (k=i; k<r ; k++) {
3422 : /* start with i, the leftmost element that changed */
3423 : /* yield tuple(pool[k] for k in indices[:r]) */
3424 35967 : index = indices[k];
3425 35967 : elem = PyTuple_GET_ITEM(pool, index);
3426 35967 : Py_INCREF(elem);
3427 35967 : oldelem = PyTuple_GET_ITEM(result, k);
3428 35967 : PyTuple_SET_ITEM(result, k, elem);
3429 35967 : Py_DECREF(oldelem);
3430 : }
3431 17784 : break;
3432 : }
3433 : }
3434 : /* If i is negative, then the cycles have all
3435 : rolled-over and we're done. */
3436 45443 : if (i < 0)
3437 27659 : goto empty;
3438 : }
3439 45702 : Py_INCREF(result);
3440 45702 : return result;
3441 :
3442 27688 : empty:
3443 27688 : po->stopped = 1;
3444 27688 : return NULL;
3445 : }
3446 :
3447 : static PyObject *
3448 420 : permutations_reduce(permutationsobject *po, PyObject *Py_UNUSED(ignored))
3449 : {
3450 420 : if (po->result == NULL) {
3451 252 : return Py_BuildValue("O(On)", Py_TYPE(po), po->pool, po->r);
3452 168 : } else if (po->stopped) {
3453 0 : return Py_BuildValue("O(()n)", Py_TYPE(po), po->r);
3454 : } else {
3455 168 : PyObject *indices=NULL, *cycles=NULL;
3456 : Py_ssize_t n, i;
3457 :
3458 : /* we must pickle the indices and cycles and use them for setstate */
3459 168 : n = PyTuple_GET_SIZE(po->pool);
3460 168 : indices = PyTuple_New(n);
3461 168 : if (indices == NULL)
3462 0 : goto err;
3463 840 : for (i=0; i<n; i++) {
3464 672 : PyObject* index = PyLong_FromSsize_t(po->indices[i]);
3465 672 : if (!index)
3466 0 : goto err;
3467 672 : PyTuple_SET_ITEM(indices, i, index);
3468 : }
3469 :
3470 168 : cycles = PyTuple_New(po->r);
3471 168 : if (cycles == NULL)
3472 0 : goto err;
3473 504 : for (i=0 ; i<po->r ; i++) {
3474 336 : PyObject* index = PyLong_FromSsize_t(po->cycles[i]);
3475 336 : if (!index)
3476 0 : goto err;
3477 336 : PyTuple_SET_ITEM(cycles, i, index);
3478 : }
3479 168 : return Py_BuildValue("O(On)(NN)", Py_TYPE(po),
3480 : po->pool, po->r,
3481 : indices, cycles);
3482 0 : err:
3483 0 : Py_XDECREF(indices);
3484 0 : Py_XDECREF(cycles);
3485 0 : return NULL;
3486 : }
3487 : }
3488 :
3489 : static PyObject *
3490 168 : permutations_setstate(permutationsobject *po, PyObject *state)
3491 : {
3492 : PyObject *indices, *cycles, *result;
3493 : Py_ssize_t n, i;
3494 :
3495 168 : if (!PyTuple_Check(state)) {
3496 0 : PyErr_SetString(PyExc_TypeError, "state is not a tuple");
3497 0 : return NULL;
3498 : }
3499 168 : if (!PyArg_ParseTuple(state, "O!O!",
3500 : &PyTuple_Type, &indices,
3501 : &PyTuple_Type, &cycles)) {
3502 0 : return NULL;
3503 : }
3504 :
3505 168 : n = PyTuple_GET_SIZE(po->pool);
3506 168 : if (PyTuple_GET_SIZE(indices) != n || PyTuple_GET_SIZE(cycles) != po->r) {
3507 0 : PyErr_SetString(PyExc_ValueError, "invalid arguments");
3508 0 : return NULL;
3509 : }
3510 :
3511 840 : for (i=0; i<n; i++) {
3512 672 : PyObject* indexObject = PyTuple_GET_ITEM(indices, i);
3513 672 : Py_ssize_t index = PyLong_AsSsize_t(indexObject);
3514 672 : if (index < 0 && PyErr_Occurred())
3515 0 : return NULL; /* not an integer */
3516 : /* clamp the index */
3517 672 : if (index < 0)
3518 0 : index = 0;
3519 672 : else if (index > n-1)
3520 0 : index = n-1;
3521 672 : po->indices[i] = index;
3522 : }
3523 :
3524 504 : for (i=0; i<po->r; i++) {
3525 336 : PyObject* indexObject = PyTuple_GET_ITEM(cycles, i);
3526 336 : Py_ssize_t index = PyLong_AsSsize_t(indexObject);
3527 336 : if (index < 0 && PyErr_Occurred())
3528 0 : return NULL; /* not an integer */
3529 336 : if (index < 1)
3530 0 : index = 1;
3531 336 : else if (index > n-i)
3532 0 : index = n-i;
3533 336 : po->cycles[i] = index;
3534 : }
3535 168 : result = PyTuple_New(po->r);
3536 168 : if (result == NULL)
3537 0 : return NULL;
3538 504 : for (i=0; i<po->r; i++) {
3539 336 : PyObject *element = PyTuple_GET_ITEM(po->pool, po->indices[i]);
3540 336 : Py_INCREF(element);
3541 336 : PyTuple_SET_ITEM(result, i, element);
3542 : }
3543 168 : Py_XSETREF(po->result, result);
3544 168 : Py_RETURN_NONE;
3545 : }
3546 :
3547 : static PyMethodDef permuations_methods[] = {
3548 : {"__reduce__", (PyCFunction)permutations_reduce, METH_NOARGS,
3549 : reduce_doc},
3550 : {"__setstate__", (PyCFunction)permutations_setstate, METH_O,
3551 : setstate_doc},
3552 : {"__sizeof__", (PyCFunction)permutations_sizeof, METH_NOARGS,
3553 : sizeof_doc},
3554 : {NULL, NULL} /* sentinel */
3555 : };
3556 :
3557 : static PyTypeObject permutations_type = {
3558 : PyVarObject_HEAD_INIT(NULL, 0)
3559 : "itertools.permutations", /* tp_name */
3560 : sizeof(permutationsobject), /* tp_basicsize */
3561 : 0, /* tp_itemsize */
3562 : /* methods */
3563 : (destructor)permutations_dealloc, /* tp_dealloc */
3564 : 0, /* tp_vectorcall_offset */
3565 : 0, /* tp_getattr */
3566 : 0, /* tp_setattr */
3567 : 0, /* tp_as_async */
3568 : 0, /* tp_repr */
3569 : 0, /* tp_as_number */
3570 : 0, /* tp_as_sequence */
3571 : 0, /* tp_as_mapping */
3572 : 0, /* tp_hash */
3573 : 0, /* tp_call */
3574 : 0, /* tp_str */
3575 : PyObject_GenericGetAttr, /* tp_getattro */
3576 : 0, /* tp_setattro */
3577 : 0, /* tp_as_buffer */
3578 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3579 : Py_TPFLAGS_BASETYPE, /* tp_flags */
3580 : itertools_permutations__doc__, /* tp_doc */
3581 : (traverseproc)permutations_traverse,/* tp_traverse */
3582 : 0, /* tp_clear */
3583 : 0, /* tp_richcompare */
3584 : 0, /* tp_weaklistoffset */
3585 : PyObject_SelfIter, /* tp_iter */
3586 : (iternextfunc)permutations_next, /* tp_iternext */
3587 : permuations_methods, /* tp_methods */
3588 : 0, /* tp_members */
3589 : 0, /* tp_getset */
3590 : 0, /* tp_base */
3591 : 0, /* tp_dict */
3592 : 0, /* tp_descr_get */
3593 : 0, /* tp_descr_set */
3594 : 0, /* tp_dictoffset */
3595 : 0, /* tp_init */
3596 : 0, /* tp_alloc */
3597 : itertools_permutations, /* tp_new */
3598 : PyObject_GC_Del, /* tp_free */
3599 : };
3600 :
3601 :
3602 : /* accumulate object ********************************************************/
3603 :
3604 : typedef struct {
3605 : PyObject_HEAD
3606 : PyObject *total;
3607 : PyObject *it;
3608 : PyObject *binop;
3609 : PyObject *initial;
3610 : } accumulateobject;
3611 :
3612 : /*[clinic input]
3613 : @classmethod
3614 : itertools.accumulate.__new__
3615 : iterable: object
3616 : func as binop: object = None
3617 : *
3618 : initial: object = None
3619 : Return series of accumulated sums (or other binary function results).
3620 : [clinic start generated code]*/
3621 :
3622 : static PyObject *
3623 182 : itertools_accumulate_impl(PyTypeObject *type, PyObject *iterable,
3624 : PyObject *binop, PyObject *initial)
3625 : /*[clinic end generated code: output=66da2650627128f8 input=c4ce20ac59bf7ffd]*/
3626 : {
3627 : PyObject *it;
3628 : accumulateobject *lz;
3629 :
3630 : /* Get iterator. */
3631 182 : it = PyObject_GetIter(iterable);
3632 182 : if (it == NULL)
3633 6 : return NULL;
3634 :
3635 : /* create accumulateobject structure */
3636 176 : lz = (accumulateobject *)type->tp_alloc(type, 0);
3637 176 : if (lz == NULL) {
3638 0 : Py_DECREF(it);
3639 0 : return NULL;
3640 : }
3641 :
3642 176 : if (binop != Py_None) {
3643 21 : Py_XINCREF(binop);
3644 21 : lz->binop = binop;
3645 : }
3646 176 : lz->total = NULL;
3647 176 : lz->it = it;
3648 176 : Py_XINCREF(initial);
3649 176 : lz->initial = initial;
3650 176 : return (PyObject *)lz;
3651 : }
3652 :
3653 : static void
3654 176 : accumulate_dealloc(accumulateobject *lz)
3655 : {
3656 176 : PyObject_GC_UnTrack(lz);
3657 176 : Py_XDECREF(lz->binop);
3658 176 : Py_XDECREF(lz->total);
3659 176 : Py_XDECREF(lz->it);
3660 176 : Py_XDECREF(lz->initial);
3661 176 : Py_TYPE(lz)->tp_free(lz);
3662 176 : }
3663 :
3664 : static int
3665 2 : accumulate_traverse(accumulateobject *lz, visitproc visit, void *arg)
3666 : {
3667 2 : Py_VISIT(lz->binop);
3668 2 : Py_VISIT(lz->it);
3669 2 : Py_VISIT(lz->total);
3670 2 : Py_VISIT(lz->initial);
3671 2 : return 0;
3672 : }
3673 :
3674 : static PyObject *
3675 105483 : accumulate_next(accumulateobject *lz)
3676 : {
3677 : PyObject *val, *newtotal;
3678 :
3679 105483 : if (lz->initial != Py_None) {
3680 8 : lz->total = lz->initial;
3681 8 : Py_INCREF(Py_None);
3682 8 : lz->initial = Py_None;
3683 8 : Py_INCREF(lz->total);
3684 8 : return lz->total;
3685 : }
3686 105475 : val = (*Py_TYPE(lz->it)->tp_iternext)(lz->it);
3687 105475 : if (val == NULL)
3688 107 : return NULL;
3689 :
3690 105368 : if (lz->total == NULL) {
3691 136 : Py_INCREF(val);
3692 136 : lz->total = val;
3693 136 : return lz->total;
3694 : }
3695 :
3696 105232 : if (lz->binop == NULL)
3697 105187 : newtotal = PyNumber_Add(lz->total, val);
3698 : else
3699 45 : newtotal = PyObject_CallFunctionObjArgs(lz->binop, lz->total, val, NULL);
3700 105232 : Py_DECREF(val);
3701 105232 : if (newtotal == NULL)
3702 5 : return NULL;
3703 :
3704 105227 : Py_INCREF(newtotal);
3705 105227 : Py_SETREF(lz->total, newtotal);
3706 105227 : return newtotal;
3707 : }
3708 :
3709 : static PyObject *
3710 53 : accumulate_reduce(accumulateobject *lz, PyObject *Py_UNUSED(ignored))
3711 : {
3712 53 : if (lz->initial != Py_None) {
3713 : PyObject *it;
3714 :
3715 6 : assert(lz->total == NULL);
3716 6 : if (PyType_Ready(&chain_type) < 0)
3717 0 : return NULL;
3718 6 : it = PyObject_CallFunction((PyObject *)&chain_type, "(O)O",
3719 : lz->initial, lz->it);
3720 6 : if (it == NULL)
3721 0 : return NULL;
3722 6 : return Py_BuildValue("O(NO)O", Py_TYPE(lz),
3723 6 : it, lz->binop?lz->binop:Py_None, Py_None);
3724 : }
3725 47 : if (lz->total == Py_None) {
3726 : PyObject *it;
3727 :
3728 8 : if (PyType_Ready(&chain_type) < 0)
3729 0 : return NULL;
3730 8 : if (PyType_Ready(&islice_type) < 0)
3731 0 : return NULL;
3732 8 : it = PyObject_CallFunction((PyObject *)&chain_type, "(O)O",
3733 : lz->total, lz->it);
3734 8 : if (it == NULL)
3735 0 : return NULL;
3736 8 : it = PyObject_CallFunction((PyObject *)Py_TYPE(lz), "NO",
3737 8 : it, lz->binop ? lz->binop : Py_None);
3738 8 : if (it == NULL)
3739 0 : return NULL;
3740 8 : return Py_BuildValue("O(NiO)", &islice_type, it, 1, Py_None);
3741 : }
3742 78 : return Py_BuildValue("O(OO)O", Py_TYPE(lz),
3743 39 : lz->it, lz->binop?lz->binop:Py_None,
3744 39 : lz->total?lz->total:Py_None);
3745 : }
3746 :
3747 : static PyObject *
3748 20 : accumulate_setstate(accumulateobject *lz, PyObject *state)
3749 : {
3750 20 : Py_INCREF(state);
3751 20 : Py_XSETREF(lz->total, state);
3752 20 : Py_RETURN_NONE;
3753 : }
3754 :
3755 : static PyMethodDef accumulate_methods[] = {
3756 : {"__reduce__", (PyCFunction)accumulate_reduce, METH_NOARGS,
3757 : reduce_doc},
3758 : {"__setstate__", (PyCFunction)accumulate_setstate, METH_O,
3759 : setstate_doc},
3760 : {NULL, NULL} /* sentinel */
3761 : };
3762 :
3763 : static PyTypeObject accumulate_type = {
3764 : PyVarObject_HEAD_INIT(NULL, 0)
3765 : "itertools.accumulate", /* tp_name */
3766 : sizeof(accumulateobject), /* tp_basicsize */
3767 : 0, /* tp_itemsize */
3768 : /* methods */
3769 : (destructor)accumulate_dealloc, /* tp_dealloc */
3770 : 0, /* tp_vectorcall_offset */
3771 : 0, /* tp_getattr */
3772 : 0, /* tp_setattr */
3773 : 0, /* tp_as_async */
3774 : 0, /* tp_repr */
3775 : 0, /* tp_as_number */
3776 : 0, /* tp_as_sequence */
3777 : 0, /* tp_as_mapping */
3778 : 0, /* tp_hash */
3779 : 0, /* tp_call */
3780 : 0, /* tp_str */
3781 : PyObject_GenericGetAttr, /* tp_getattro */
3782 : 0, /* tp_setattro */
3783 : 0, /* tp_as_buffer */
3784 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3785 : Py_TPFLAGS_BASETYPE, /* tp_flags */
3786 : itertools_accumulate__doc__, /* tp_doc */
3787 : (traverseproc)accumulate_traverse, /* tp_traverse */
3788 : 0, /* tp_clear */
3789 : 0, /* tp_richcompare */
3790 : 0, /* tp_weaklistoffset */
3791 : PyObject_SelfIter, /* tp_iter */
3792 : (iternextfunc)accumulate_next, /* tp_iternext */
3793 : accumulate_methods, /* tp_methods */
3794 : 0, /* tp_members */
3795 : 0, /* tp_getset */
3796 : 0, /* tp_base */
3797 : 0, /* tp_dict */
3798 : 0, /* tp_descr_get */
3799 : 0, /* tp_descr_set */
3800 : 0, /* tp_dictoffset */
3801 : 0, /* tp_init */
3802 : 0, /* tp_alloc */
3803 : itertools_accumulate, /* tp_new */
3804 : PyObject_GC_Del, /* tp_free */
3805 : };
3806 :
3807 :
3808 : /* compress object ************************************************************/
3809 :
3810 : /* Equivalent to:
3811 :
3812 : def compress(data, selectors):
3813 : "compress('ABCDEF', [1,0,1,0,1,1]) --> A C E F"
3814 : return (d for d, s in zip(data, selectors) if s)
3815 : */
3816 :
3817 : typedef struct {
3818 : PyObject_HEAD
3819 : PyObject *data;
3820 : PyObject *selectors;
3821 : } compressobject;
3822 :
3823 : /*[clinic input]
3824 : @classmethod
3825 : itertools.compress.__new__
3826 : data as seq1: object
3827 : selectors as seq2: object
3828 : Return data elements corresponding to true selector elements.
3829 :
3830 : Forms a shorter iterator from selected data elements using the selectors to
3831 : choose the data elements.
3832 : [clinic start generated code]*/
3833 :
3834 : static PyObject *
3835 291 : itertools_compress_impl(PyTypeObject *type, PyObject *seq1, PyObject *seq2)
3836 : /*[clinic end generated code: output=7e67157212ed09e0 input=79596d7cd20c77e5]*/
3837 : {
3838 291 : PyObject *data=NULL, *selectors=NULL;
3839 : compressobject *lz;
3840 :
3841 291 : data = PyObject_GetIter(seq1);
3842 291 : if (data == NULL)
3843 11 : goto fail;
3844 280 : selectors = PyObject_GetIter(seq2);
3845 280 : if (selectors == NULL)
3846 2 : goto fail;
3847 :
3848 : /* create compressobject structure */
3849 278 : lz = (compressobject *)type->tp_alloc(type, 0);
3850 278 : if (lz == NULL)
3851 0 : goto fail;
3852 278 : lz->data = data;
3853 278 : lz->selectors = selectors;
3854 278 : return (PyObject *)lz;
3855 :
3856 13 : fail:
3857 13 : Py_XDECREF(data);
3858 13 : Py_XDECREF(selectors);
3859 13 : return NULL;
3860 : }
3861 :
3862 : static void
3863 278 : compress_dealloc(compressobject *lz)
3864 : {
3865 278 : PyObject_GC_UnTrack(lz);
3866 278 : Py_XDECREF(lz->data);
3867 278 : Py_XDECREF(lz->selectors);
3868 278 : Py_TYPE(lz)->tp_free(lz);
3869 278 : }
3870 :
3871 : static int
3872 2 : compress_traverse(compressobject *lz, visitproc visit, void *arg)
3873 : {
3874 2 : Py_VISIT(lz->data);
3875 2 : Py_VISIT(lz->selectors);
3876 2 : return 0;
3877 : }
3878 :
3879 : static PyObject *
3880 35745 : compress_next(compressobject *lz)
3881 : {
3882 35745 : PyObject *data = lz->data, *selectors = lz->selectors;
3883 : PyObject *datum, *selector;
3884 35745 : PyObject *(*datanext)(PyObject *) = *Py_TYPE(data)->tp_iternext;
3885 35745 : PyObject *(*selectornext)(PyObject *) = *Py_TYPE(selectors)->tp_iternext;
3886 : int ok;
3887 :
3888 : while (1) {
3889 : /* Steps: get datum, get selector, evaluate selector.
3890 : Order is important (to match the pure python version
3891 : in terms of which input gets a chance to raise an
3892 : exception first).
3893 : */
3894 :
3895 65953 : datum = datanext(data);
3896 65953 : if (datum == NULL)
3897 132 : return NULL;
3898 :
3899 65821 : selector = selectornext(selectors);
3900 65821 : if (selector == NULL) {
3901 25 : Py_DECREF(datum);
3902 25 : return NULL;
3903 : }
3904 :
3905 65796 : ok = PyObject_IsTrue(selector);
3906 65796 : Py_DECREF(selector);
3907 65796 : if (ok > 0)
3908 35588 : return datum;
3909 30208 : Py_DECREF(datum);
3910 30208 : if (ok < 0)
3911 0 : return NULL;
3912 : }
3913 : }
3914 :
3915 : static PyObject *
3916 112 : compress_reduce(compressobject *lz, PyObject *Py_UNUSED(ignored))
3917 : {
3918 112 : return Py_BuildValue("O(OO)", Py_TYPE(lz),
3919 : lz->data, lz->selectors);
3920 : }
3921 :
3922 : static PyMethodDef compress_methods[] = {
3923 : {"__reduce__", (PyCFunction)compress_reduce, METH_NOARGS,
3924 : reduce_doc},
3925 : {NULL, NULL} /* sentinel */
3926 : };
3927 :
3928 : static PyTypeObject compress_type = {
3929 : PyVarObject_HEAD_INIT(NULL, 0)
3930 : "itertools.compress", /* tp_name */
3931 : sizeof(compressobject), /* tp_basicsize */
3932 : 0, /* tp_itemsize */
3933 : /* methods */
3934 : (destructor)compress_dealloc, /* tp_dealloc */
3935 : 0, /* tp_vectorcall_offset */
3936 : 0, /* tp_getattr */
3937 : 0, /* tp_setattr */
3938 : 0, /* tp_as_async */
3939 : 0, /* tp_repr */
3940 : 0, /* tp_as_number */
3941 : 0, /* tp_as_sequence */
3942 : 0, /* tp_as_mapping */
3943 : 0, /* tp_hash */
3944 : 0, /* tp_call */
3945 : 0, /* tp_str */
3946 : PyObject_GenericGetAttr, /* tp_getattro */
3947 : 0, /* tp_setattro */
3948 : 0, /* tp_as_buffer */
3949 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
3950 : Py_TPFLAGS_BASETYPE, /* tp_flags */
3951 : itertools_compress__doc__, /* tp_doc */
3952 : (traverseproc)compress_traverse, /* tp_traverse */
3953 : 0, /* tp_clear */
3954 : 0, /* tp_richcompare */
3955 : 0, /* tp_weaklistoffset */
3956 : PyObject_SelfIter, /* tp_iter */
3957 : (iternextfunc)compress_next, /* tp_iternext */
3958 : compress_methods, /* tp_methods */
3959 : 0, /* tp_members */
3960 : 0, /* tp_getset */
3961 : 0, /* tp_base */
3962 : 0, /* tp_dict */
3963 : 0, /* tp_descr_get */
3964 : 0, /* tp_descr_set */
3965 : 0, /* tp_dictoffset */
3966 : 0, /* tp_init */
3967 : 0, /* tp_alloc */
3968 : itertools_compress, /* tp_new */
3969 : PyObject_GC_Del, /* tp_free */
3970 : };
3971 :
3972 :
3973 : /* filterfalse object ************************************************************/
3974 :
3975 : typedef struct {
3976 : PyObject_HEAD
3977 : PyObject *func;
3978 : PyObject *it;
3979 : } filterfalseobject;
3980 :
3981 : /*[clinic input]
3982 : @classmethod
3983 : itertools.filterfalse.__new__
3984 : function as func: object
3985 : iterable as seq: object
3986 : /
3987 : Return those items of iterable for which function(item) is false.
3988 :
3989 : If function is None, return the items that are false.
3990 : [clinic start generated code]*/
3991 :
3992 : static PyObject *
3993 403 : itertools_filterfalse_impl(PyTypeObject *type, PyObject *func, PyObject *seq)
3994 : /*[clinic end generated code: output=55f87eab9fc0484e input=2d684a2c66f99cde]*/
3995 : {
3996 : PyObject *it;
3997 : filterfalseobject *lz;
3998 :
3999 : /* Get iterator. */
4000 403 : it = PyObject_GetIter(seq);
4001 403 : if (it == NULL)
4002 11 : return NULL;
4003 :
4004 : /* create filterfalseobject structure */
4005 392 : lz = (filterfalseobject *)type->tp_alloc(type, 0);
4006 392 : if (lz == NULL) {
4007 0 : Py_DECREF(it);
4008 0 : return NULL;
4009 : }
4010 392 : Py_INCREF(func);
4011 392 : lz->func = func;
4012 392 : lz->it = it;
4013 :
4014 392 : return (PyObject *)lz;
4015 : }
4016 :
4017 : static void
4018 392 : filterfalse_dealloc(filterfalseobject *lz)
4019 : {
4020 392 : PyObject_GC_UnTrack(lz);
4021 392 : Py_XDECREF(lz->func);
4022 392 : Py_XDECREF(lz->it);
4023 392 : Py_TYPE(lz)->tp_free(lz);
4024 392 : }
4025 :
4026 : static int
4027 174 : filterfalse_traverse(filterfalseobject *lz, visitproc visit, void *arg)
4028 : {
4029 174 : Py_VISIT(lz->it);
4030 174 : Py_VISIT(lz->func);
4031 174 : return 0;
4032 : }
4033 :
4034 : static PyObject *
4035 305213 : filterfalse_next(filterfalseobject *lz)
4036 : {
4037 : PyObject *item;
4038 305213 : PyObject *it = lz->it;
4039 : long ok;
4040 : PyObject *(*iternext)(PyObject *);
4041 :
4042 305213 : iternext = *Py_TYPE(it)->tp_iternext;
4043 : for (;;) {
4044 308576 : item = iternext(it);
4045 308576 : if (item == NULL)
4046 405 : return NULL;
4047 :
4048 308171 : if (lz->func == Py_None || lz->func == (PyObject *)&PyBool_Type) {
4049 16 : ok = PyObject_IsTrue(item);
4050 : } else {
4051 : PyObject *good;
4052 308155 : good = PyObject_CallOneArg(lz->func, item);
4053 308155 : if (good == NULL) {
4054 1 : Py_DECREF(item);
4055 1 : return NULL;
4056 : }
4057 308154 : ok = PyObject_IsTrue(good);
4058 308154 : Py_DECREF(good);
4059 : }
4060 308170 : if (ok == 0)
4061 304807 : return item;
4062 3363 : Py_DECREF(item);
4063 3363 : if (ok < 0)
4064 0 : return NULL;
4065 : }
4066 : }
4067 :
4068 : static PyObject *
4069 12 : filterfalse_reduce(filterfalseobject *lz, PyObject *Py_UNUSED(ignored))
4070 : {
4071 12 : return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->func, lz->it);
4072 : }
4073 :
4074 : static PyMethodDef filterfalse_methods[] = {
4075 : {"__reduce__", (PyCFunction)filterfalse_reduce, METH_NOARGS,
4076 : reduce_doc},
4077 : {NULL, NULL} /* sentinel */
4078 : };
4079 :
4080 : static PyTypeObject filterfalse_type = {
4081 : PyVarObject_HEAD_INIT(NULL, 0)
4082 : "itertools.filterfalse", /* tp_name */
4083 : sizeof(filterfalseobject), /* tp_basicsize */
4084 : 0, /* tp_itemsize */
4085 : /* methods */
4086 : (destructor)filterfalse_dealloc, /* tp_dealloc */
4087 : 0, /* tp_vectorcall_offset */
4088 : 0, /* tp_getattr */
4089 : 0, /* tp_setattr */
4090 : 0, /* tp_as_async */
4091 : 0, /* tp_repr */
4092 : 0, /* tp_as_number */
4093 : 0, /* tp_as_sequence */
4094 : 0, /* tp_as_mapping */
4095 : 0, /* tp_hash */
4096 : 0, /* tp_call */
4097 : 0, /* tp_str */
4098 : PyObject_GenericGetAttr, /* tp_getattro */
4099 : 0, /* tp_setattro */
4100 : 0, /* tp_as_buffer */
4101 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
4102 : Py_TPFLAGS_BASETYPE, /* tp_flags */
4103 : itertools_filterfalse__doc__, /* tp_doc */
4104 : (traverseproc)filterfalse_traverse, /* tp_traverse */
4105 : 0, /* tp_clear */
4106 : 0, /* tp_richcompare */
4107 : 0, /* tp_weaklistoffset */
4108 : PyObject_SelfIter, /* tp_iter */
4109 : (iternextfunc)filterfalse_next, /* tp_iternext */
4110 : filterfalse_methods, /* tp_methods */
4111 : 0, /* tp_members */
4112 : 0, /* tp_getset */
4113 : 0, /* tp_base */
4114 : 0, /* tp_dict */
4115 : 0, /* tp_descr_get */
4116 : 0, /* tp_descr_set */
4117 : 0, /* tp_dictoffset */
4118 : 0, /* tp_init */
4119 : 0, /* tp_alloc */
4120 : itertools_filterfalse, /* tp_new */
4121 : PyObject_GC_Del, /* tp_free */
4122 : };
4123 :
4124 :
4125 : /* count object ************************************************************/
4126 :
4127 : typedef struct {
4128 : PyObject_HEAD
4129 : Py_ssize_t cnt;
4130 : PyObject *long_cnt;
4131 : PyObject *long_step;
4132 : } countobject;
4133 :
4134 : /* Counting logic and invariants:
4135 :
4136 : fast_mode: when cnt an integer < PY_SSIZE_T_MAX and no step is specified.
4137 :
4138 : assert(cnt != PY_SSIZE_T_MAX && long_cnt == NULL && long_step==PyLong(1));
4139 : Advances with: cnt += 1
4140 : When count hits Y_SSIZE_T_MAX, switch to slow_mode.
4141 :
4142 : slow_mode: when cnt == PY_SSIZE_T_MAX, step is not int(1), or cnt is a float.
4143 :
4144 : assert(cnt == PY_SSIZE_T_MAX && long_cnt != NULL && long_step != NULL);
4145 : All counting is done with python objects (no overflows or underflows).
4146 : Advances with: long_cnt += long_step
4147 : Step may be zero -- effectively a slow version of repeat(cnt).
4148 : Either long_cnt or long_step may be a float, Fraction, or Decimal.
4149 : */
4150 :
4151 : /*[clinic input]
4152 : @classmethod
4153 : itertools.count.__new__
4154 : start as long_cnt: object(c_default="NULL") = 0
4155 : step as long_step: object(c_default="NULL") = 1
4156 : Return a count object whose .__next__() method returns consecutive values.
4157 :
4158 : Equivalent to:
4159 : def count(firstval=0, step=1):
4160 : x = firstval
4161 : while 1:
4162 : yield x
4163 : x += step
4164 : [clinic start generated code]*/
4165 :
4166 : static PyObject *
4167 17322 : itertools_count_impl(PyTypeObject *type, PyObject *long_cnt,
4168 : PyObject *long_step)
4169 : /*[clinic end generated code: output=09a9250aebd00b1c input=d7a85eec18bfcd94]*/
4170 : {
4171 : countobject *lz;
4172 : int fast_mode;
4173 17322 : Py_ssize_t cnt = 0;
4174 : long step;
4175 :
4176 17322 : if ((long_cnt != NULL && !PyNumber_Check(long_cnt)) ||
4177 1737 : (long_step != NULL && !PyNumber_Check(long_step))) {
4178 2 : PyErr_SetString(PyExc_TypeError, "a number is required");
4179 2 : return NULL;
4180 : }
4181 :
4182 19052 : fast_mode = (long_cnt == NULL || PyLong_Check(long_cnt)) &&
4183 1732 : (long_step == NULL || PyLong_Check(long_step));
4184 :
4185 : /* If not specified, start defaults to 0 */
4186 17320 : if (long_cnt != NULL) {
4187 13221 : if (fast_mode) {
4188 13204 : assert(PyLong_Check(long_cnt));
4189 13204 : cnt = PyLong_AsSsize_t(long_cnt);
4190 13204 : if (cnt == -1 && PyErr_Occurred()) {
4191 530 : PyErr_Clear();
4192 530 : fast_mode = 0;
4193 : }
4194 : }
4195 : } else {
4196 4099 : cnt = 0;
4197 4099 : long_cnt = _PyLong_GetZero();
4198 : }
4199 17320 : Py_INCREF(long_cnt);
4200 :
4201 : /* If not specified, step defaults to 1 */
4202 17320 : if (long_step == NULL) {
4203 15583 : long_step = _PyLong_GetOne();
4204 : }
4205 17320 : Py_INCREF(long_step);
4206 :
4207 17320 : assert(long_cnt != NULL && long_step != NULL);
4208 :
4209 : /* Fast mode only works when the step is 1 */
4210 17320 : if (fast_mode) {
4211 16773 : assert(PyLong_Check(long_step));
4212 16773 : step = PyLong_AsLong(long_step);
4213 16773 : if (step != 1) {
4214 1164 : fast_mode = 0;
4215 1164 : if (step == -1 && PyErr_Occurred())
4216 267 : PyErr_Clear();
4217 : }
4218 : }
4219 :
4220 17320 : if (fast_mode)
4221 15609 : Py_CLEAR(long_cnt);
4222 : else
4223 1711 : cnt = PY_SSIZE_T_MAX;
4224 :
4225 17320 : assert((cnt != PY_SSIZE_T_MAX && long_cnt == NULL && fast_mode) ||
4226 : (cnt == PY_SSIZE_T_MAX && long_cnt != NULL && !fast_mode));
4227 17320 : assert(!fast_mode ||
4228 : (PyLong_Check(long_step) && PyLong_AS_LONG(long_step) == 1));
4229 :
4230 : /* create countobject structure */
4231 17320 : lz = (countobject *)type->tp_alloc(type, 0);
4232 17320 : if (lz == NULL) {
4233 0 : Py_XDECREF(long_cnt);
4234 0 : Py_DECREF(long_step);
4235 0 : return NULL;
4236 : }
4237 17320 : lz->cnt = cnt;
4238 17320 : lz->long_cnt = long_cnt;
4239 17320 : lz->long_step = long_step;
4240 :
4241 17320 : return (PyObject *)lz;
4242 : }
4243 :
4244 : static void
4245 17316 : count_dealloc(countobject *lz)
4246 : {
4247 17316 : PyObject_GC_UnTrack(lz);
4248 17316 : Py_XDECREF(lz->long_cnt);
4249 17316 : Py_XDECREF(lz->long_step);
4250 17316 : Py_TYPE(lz)->tp_free(lz);
4251 17316 : }
4252 :
4253 : static int
4254 169988 : count_traverse(countobject *lz, visitproc visit, void *arg)
4255 : {
4256 169988 : Py_VISIT(lz->long_cnt);
4257 169988 : Py_VISIT(lz->long_step);
4258 169988 : return 0;
4259 : }
4260 :
4261 : static PyObject *
4262 6948 : count_nextlong(countobject *lz)
4263 : {
4264 : PyObject *long_cnt;
4265 : PyObject *stepped_up;
4266 :
4267 6948 : long_cnt = lz->long_cnt;
4268 6948 : if (long_cnt == NULL) {
4269 : /* Switch to slow_mode */
4270 1 : long_cnt = PyLong_FromSsize_t(PY_SSIZE_T_MAX);
4271 1 : if (long_cnt == NULL)
4272 0 : return NULL;
4273 : }
4274 6948 : assert(lz->cnt == PY_SSIZE_T_MAX && long_cnt != NULL);
4275 :
4276 6948 : stepped_up = PyNumber_Add(long_cnt, lz->long_step);
4277 6948 : if (stepped_up == NULL)
4278 0 : return NULL;
4279 6948 : lz->long_cnt = stepped_up;
4280 6948 : return long_cnt;
4281 : }
4282 :
4283 : static PyObject *
4284 129205 : count_next(countobject *lz)
4285 : {
4286 129205 : if (lz->cnt == PY_SSIZE_T_MAX)
4287 6948 : return count_nextlong(lz);
4288 122257 : return PyLong_FromSsize_t(lz->cnt++);
4289 : }
4290 :
4291 : static PyObject *
4292 96 : count_repr(countobject *lz)
4293 : {
4294 96 : if (lz->cnt != PY_SSIZE_T_MAX)
4295 15 : return PyUnicode_FromFormat("%s(%zd)",
4296 : _PyType_Name(Py_TYPE(lz)), lz->cnt);
4297 :
4298 81 : if (PyLong_Check(lz->long_step)) {
4299 78 : long step = PyLong_AsLong(lz->long_step);
4300 78 : if (step == -1 && PyErr_Occurred()) {
4301 16 : PyErr_Clear();
4302 : }
4303 78 : if (step == 1) {
4304 : /* Don't display step when it is an integer equal to 1 */
4305 7 : return PyUnicode_FromFormat("%s(%R)",
4306 : _PyType_Name(Py_TYPE(lz)),
4307 : lz->long_cnt);
4308 : }
4309 : }
4310 74 : return PyUnicode_FromFormat("%s(%R, %R)",
4311 : _PyType_Name(Py_TYPE(lz)),
4312 : lz->long_cnt, lz->long_step);
4313 : }
4314 :
4315 : static PyObject *
4316 958 : count_reduce(countobject *lz, PyObject *Py_UNUSED(ignored))
4317 : {
4318 958 : if (lz->cnt == PY_SSIZE_T_MAX)
4319 806 : return Py_BuildValue("O(OO)", Py_TYPE(lz), lz->long_cnt, lz->long_step);
4320 152 : return Py_BuildValue("O(n)", Py_TYPE(lz), lz->cnt);
4321 : }
4322 :
4323 : static PyMethodDef count_methods[] = {
4324 : {"__reduce__", (PyCFunction)count_reduce, METH_NOARGS,
4325 : reduce_doc},
4326 : {NULL, NULL} /* sentinel */
4327 : };
4328 :
4329 : static PyTypeObject count_type = {
4330 : PyVarObject_HEAD_INIT(NULL, 0)
4331 : "itertools.count", /* tp_name */
4332 : sizeof(countobject), /* tp_basicsize */
4333 : 0, /* tp_itemsize */
4334 : /* methods */
4335 : (destructor)count_dealloc, /* tp_dealloc */
4336 : 0, /* tp_vectorcall_offset */
4337 : 0, /* tp_getattr */
4338 : 0, /* tp_setattr */
4339 : 0, /* tp_as_async */
4340 : (reprfunc)count_repr, /* tp_repr */
4341 : 0, /* tp_as_number */
4342 : 0, /* tp_as_sequence */
4343 : 0, /* tp_as_mapping */
4344 : 0, /* tp_hash */
4345 : 0, /* tp_call */
4346 : 0, /* tp_str */
4347 : PyObject_GenericGetAttr, /* tp_getattro */
4348 : 0, /* tp_setattro */
4349 : 0, /* tp_as_buffer */
4350 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
4351 : Py_TPFLAGS_BASETYPE, /* tp_flags */
4352 : itertools_count__doc__, /* tp_doc */
4353 : (traverseproc)count_traverse, /* tp_traverse */
4354 : 0, /* tp_clear */
4355 : 0, /* tp_richcompare */
4356 : 0, /* tp_weaklistoffset */
4357 : PyObject_SelfIter, /* tp_iter */
4358 : (iternextfunc)count_next, /* tp_iternext */
4359 : count_methods, /* tp_methods */
4360 : 0, /* tp_members */
4361 : 0, /* tp_getset */
4362 : 0, /* tp_base */
4363 : 0, /* tp_dict */
4364 : 0, /* tp_descr_get */
4365 : 0, /* tp_descr_set */
4366 : 0, /* tp_dictoffset */
4367 : 0, /* tp_init */
4368 : 0, /* tp_alloc */
4369 : itertools_count, /* tp_new */
4370 : PyObject_GC_Del, /* tp_free */
4371 : };
4372 :
4373 :
4374 : /* repeat object ************************************************************/
4375 :
4376 : typedef struct {
4377 : PyObject_HEAD
4378 : PyObject *element;
4379 : Py_ssize_t cnt;
4380 : } repeatobject;
4381 :
4382 : static PyTypeObject repeat_type;
4383 :
4384 : static PyObject *
4385 46435 : repeat_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4386 : {
4387 : repeatobject *ro;
4388 : PyObject *element;
4389 46435 : Py_ssize_t cnt = -1, n_args;
4390 : static char *kwargs[] = {"object", "times", NULL};
4391 :
4392 46435 : n_args = PyTuple_GET_SIZE(args);
4393 46435 : if (kwds != NULL)
4394 16 : n_args += PyDict_GET_SIZE(kwds);
4395 46435 : if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|n:repeat", kwargs,
4396 : &element, &cnt))
4397 6 : return NULL;
4398 : /* Does user supply times argument? */
4399 46429 : if (n_args == 2 && cnt < 0)
4400 13 : cnt = 0;
4401 :
4402 46429 : ro = (repeatobject *)type->tp_alloc(type, 0);
4403 46429 : if (ro == NULL)
4404 0 : return NULL;
4405 46429 : Py_INCREF(element);
4406 46429 : ro->element = element;
4407 46429 : ro->cnt = cnt;
4408 46429 : return (PyObject *)ro;
4409 : }
4410 :
4411 : static void
4412 46429 : repeat_dealloc(repeatobject *ro)
4413 : {
4414 46429 : PyObject_GC_UnTrack(ro);
4415 46429 : Py_XDECREF(ro->element);
4416 46429 : Py_TYPE(ro)->tp_free(ro);
4417 46429 : }
4418 :
4419 : static int
4420 3336 : repeat_traverse(repeatobject *ro, visitproc visit, void *arg)
4421 : {
4422 3336 : Py_VISIT(ro->element);
4423 3336 : return 0;
4424 : }
4425 :
4426 : static PyObject *
4427 28291500 : repeat_next(repeatobject *ro)
4428 : {
4429 28291500 : if (ro->cnt == 0)
4430 42975 : return NULL;
4431 28248600 : if (ro->cnt > 0)
4432 28210200 : ro->cnt--;
4433 28248600 : Py_INCREF(ro->element);
4434 28248600 : return ro->element;
4435 : }
4436 :
4437 : static PyObject *
4438 7 : repeat_repr(repeatobject *ro)
4439 : {
4440 7 : if (ro->cnt == -1)
4441 1 : return PyUnicode_FromFormat("%s(%R)",
4442 : _PyType_Name(Py_TYPE(ro)), ro->element);
4443 : else
4444 6 : return PyUnicode_FromFormat("%s(%R, %zd)",
4445 : _PyType_Name(Py_TYPE(ro)), ro->element,
4446 : ro->cnt);
4447 : }
4448 :
4449 : static PyObject *
4450 25 : repeat_len(repeatobject *ro, PyObject *Py_UNUSED(ignored))
4451 : {
4452 25 : if (ro->cnt == -1) {
4453 1 : PyErr_SetString(PyExc_TypeError, "len() of unsized object");
4454 1 : return NULL;
4455 : }
4456 24 : return PyLong_FromSize_t(ro->cnt);
4457 : }
4458 :
4459 : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it)).");
4460 :
4461 : static PyObject *
4462 14 : repeat_reduce(repeatobject *ro, PyObject *Py_UNUSED(ignored))
4463 : {
4464 : /* unpickle this so that a new repeat iterator is constructed with an
4465 : * object, then call __setstate__ on it to set cnt
4466 : */
4467 14 : if (ro->cnt >= 0)
4468 14 : return Py_BuildValue("O(On)", Py_TYPE(ro), ro->element, ro->cnt);
4469 : else
4470 0 : return Py_BuildValue("O(O)", Py_TYPE(ro), ro->element);
4471 : }
4472 :
4473 : static PyMethodDef repeat_methods[] = {
4474 : {"__length_hint__", (PyCFunction)repeat_len, METH_NOARGS, length_hint_doc},
4475 : {"__reduce__", (PyCFunction)repeat_reduce, METH_NOARGS, reduce_doc},
4476 : {NULL, NULL} /* sentinel */
4477 : };
4478 :
4479 : PyDoc_STRVAR(repeat_doc,
4480 : "repeat(object [,times]) -> create an iterator which returns the object\n\
4481 : for the specified number of times. If not specified, returns the object\n\
4482 : endlessly.");
4483 :
4484 : static PyTypeObject repeat_type = {
4485 : PyVarObject_HEAD_INIT(NULL, 0)
4486 : "itertools.repeat", /* tp_name */
4487 : sizeof(repeatobject), /* tp_basicsize */
4488 : 0, /* tp_itemsize */
4489 : /* methods */
4490 : (destructor)repeat_dealloc, /* tp_dealloc */
4491 : 0, /* tp_vectorcall_offset */
4492 : 0, /* tp_getattr */
4493 : 0, /* tp_setattr */
4494 : 0, /* tp_as_async */
4495 : (reprfunc)repeat_repr, /* tp_repr */
4496 : 0, /* tp_as_number */
4497 : 0, /* tp_as_sequence */
4498 : 0, /* tp_as_mapping */
4499 : 0, /* tp_hash */
4500 : 0, /* tp_call */
4501 : 0, /* tp_str */
4502 : PyObject_GenericGetAttr, /* tp_getattro */
4503 : 0, /* tp_setattro */
4504 : 0, /* tp_as_buffer */
4505 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
4506 : Py_TPFLAGS_BASETYPE, /* tp_flags */
4507 : repeat_doc, /* tp_doc */
4508 : (traverseproc)repeat_traverse, /* tp_traverse */
4509 : 0, /* tp_clear */
4510 : 0, /* tp_richcompare */
4511 : 0, /* tp_weaklistoffset */
4512 : PyObject_SelfIter, /* tp_iter */
4513 : (iternextfunc)repeat_next, /* tp_iternext */
4514 : repeat_methods, /* tp_methods */
4515 : 0, /* tp_members */
4516 : 0, /* tp_getset */
4517 : 0, /* tp_base */
4518 : 0, /* tp_dict */
4519 : 0, /* tp_descr_get */
4520 : 0, /* tp_descr_set */
4521 : 0, /* tp_dictoffset */
4522 : 0, /* tp_init */
4523 : 0, /* tp_alloc */
4524 : repeat_new, /* tp_new */
4525 : PyObject_GC_Del, /* tp_free */
4526 : };
4527 :
4528 :
4529 : /* ziplongest object *********************************************************/
4530 :
4531 : typedef struct {
4532 : PyObject_HEAD
4533 : Py_ssize_t tuplesize;
4534 : Py_ssize_t numactive;
4535 : PyObject *ittuple; /* tuple of iterators */
4536 : PyObject *result;
4537 : PyObject *fillvalue;
4538 : } ziplongestobject;
4539 :
4540 : static PyTypeObject ziplongest_type;
4541 :
4542 : static PyObject *
4543 31789 : zip_longest_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4544 : {
4545 : ziplongestobject *lz;
4546 : Py_ssize_t i;
4547 : PyObject *ittuple; /* tuple of iterators */
4548 : PyObject *result;
4549 31789 : PyObject *fillvalue = Py_None;
4550 : Py_ssize_t tuplesize;
4551 :
4552 31789 : if (kwds != NULL && PyDict_CheckExact(kwds) && PyDict_GET_SIZE(kwds) > 0) {
4553 31596 : fillvalue = NULL;
4554 31596 : if (PyDict_GET_SIZE(kwds) == 1) {
4555 31595 : fillvalue = PyDict_GetItemWithError(kwds, &_Py_ID(fillvalue));
4556 : }
4557 31596 : if (fillvalue == NULL) {
4558 2 : if (!PyErr_Occurred()) {
4559 2 : PyErr_SetString(PyExc_TypeError,
4560 : "zip_longest() got an unexpected keyword argument");
4561 : }
4562 2 : return NULL;
4563 : }
4564 : }
4565 :
4566 : /* args must be a tuple */
4567 31787 : assert(PyTuple_Check(args));
4568 31787 : tuplesize = PyTuple_GET_SIZE(args);
4569 :
4570 : /* obtain iterators */
4571 31787 : ittuple = PyTuple_New(tuplesize);
4572 31787 : if (ittuple == NULL)
4573 0 : return NULL;
4574 95320 : for (i=0; i < tuplesize; i++) {
4575 63546 : PyObject *item = PyTuple_GET_ITEM(args, i);
4576 63546 : PyObject *it = PyObject_GetIter(item);
4577 63546 : if (it == NULL) {
4578 13 : Py_DECREF(ittuple);
4579 13 : return NULL;
4580 : }
4581 63533 : PyTuple_SET_ITEM(ittuple, i, it);
4582 : }
4583 :
4584 : /* create a result holder */
4585 31774 : result = PyTuple_New(tuplesize);
4586 31774 : if (result == NULL) {
4587 0 : Py_DECREF(ittuple);
4588 0 : return NULL;
4589 : }
4590 95306 : for (i=0 ; i < tuplesize ; i++) {
4591 63532 : Py_INCREF(Py_None);
4592 63532 : PyTuple_SET_ITEM(result, i, Py_None);
4593 : }
4594 :
4595 : /* create ziplongestobject structure */
4596 31774 : lz = (ziplongestobject *)type->tp_alloc(type, 0);
4597 31774 : if (lz == NULL) {
4598 0 : Py_DECREF(ittuple);
4599 0 : Py_DECREF(result);
4600 0 : return NULL;
4601 : }
4602 31774 : lz->ittuple = ittuple;
4603 31774 : lz->tuplesize = tuplesize;
4604 31774 : lz->numactive = tuplesize;
4605 31774 : lz->result = result;
4606 31774 : Py_INCREF(fillvalue);
4607 31774 : lz->fillvalue = fillvalue;
4608 31774 : return (PyObject *)lz;
4609 : }
4610 :
4611 : static void
4612 31774 : zip_longest_dealloc(ziplongestobject *lz)
4613 : {
4614 31774 : PyObject_GC_UnTrack(lz);
4615 31774 : Py_XDECREF(lz->ittuple);
4616 31774 : Py_XDECREF(lz->result);
4617 31774 : Py_XDECREF(lz->fillvalue);
4618 31774 : Py_TYPE(lz)->tp_free(lz);
4619 31774 : }
4620 :
4621 : static int
4622 30 : zip_longest_traverse(ziplongestobject *lz, visitproc visit, void *arg)
4623 : {
4624 30 : Py_VISIT(lz->ittuple);
4625 30 : Py_VISIT(lz->result);
4626 30 : Py_VISIT(lz->fillvalue);
4627 30 : return 0;
4628 : }
4629 :
4630 : static PyObject *
4631 1094290 : zip_longest_next(ziplongestobject *lz)
4632 : {
4633 : Py_ssize_t i;
4634 1094290 : Py_ssize_t tuplesize = lz->tuplesize;
4635 1094290 : PyObject *result = lz->result;
4636 : PyObject *it;
4637 : PyObject *item;
4638 : PyObject *olditem;
4639 :
4640 1094290 : if (tuplesize == 0)
4641 1 : return NULL;
4642 1094290 : if (lz->numactive == 0)
4643 0 : return NULL;
4644 1094290 : if (Py_REFCNT(result) == 1) {
4645 549112 : Py_INCREF(result);
4646 1620160 : for (i=0 ; i < tuplesize ; i++) {
4647 1098210 : it = PyTuple_GET_ITEM(lz->ittuple, i);
4648 1098210 : if (it == NULL) {
4649 7 : Py_INCREF(lz->fillvalue);
4650 7 : item = lz->fillvalue;
4651 : } else {
4652 1098200 : item = PyIter_Next(it);
4653 1098200 : if (item == NULL) {
4654 55758 : lz->numactive -= 1;
4655 55758 : if (lz->numactive == 0 || PyErr_Occurred()) {
4656 27162 : lz->numactive = 0;
4657 27162 : Py_DECREF(result);
4658 27162 : return NULL;
4659 : } else {
4660 28596 : Py_INCREF(lz->fillvalue);
4661 28596 : item = lz->fillvalue;
4662 28596 : PyTuple_SET_ITEM(lz->ittuple, i, NULL);
4663 28596 : Py_DECREF(it);
4664 : }
4665 : }
4666 : }
4667 1071050 : olditem = PyTuple_GET_ITEM(result, i);
4668 1071050 : PyTuple_SET_ITEM(result, i, item);
4669 1071050 : Py_DECREF(olditem);
4670 : }
4671 : // bpo-42536: The GC may have untracked this result tuple. Since we're
4672 : // recycling it, make sure it's tracked again:
4673 521950 : if (!_PyObject_GC_IS_TRACKED(result)) {
4674 4 : _PyObject_GC_TRACK(result);
4675 : }
4676 : } else {
4677 545174 : result = PyTuple_New(tuplesize);
4678 545174 : if (result == NULL)
4679 0 : return NULL;
4680 1658720 : for (i=0 ; i < tuplesize ; i++) {
4681 1118080 : it = PyTuple_GET_ITEM(lz->ittuple, i);
4682 1118080 : if (it == NULL) {
4683 33112 : Py_INCREF(lz->fillvalue);
4684 33112 : item = lz->fillvalue;
4685 : } else {
4686 1084970 : item = PyIter_Next(it);
4687 1084970 : if (item == NULL) {
4688 7694 : lz->numactive -= 1;
4689 7694 : if (lz->numactive == 0 || PyErr_Occurred()) {
4690 4535 : lz->numactive = 0;
4691 4535 : Py_DECREF(result);
4692 4535 : return NULL;
4693 : } else {
4694 3159 : Py_INCREF(lz->fillvalue);
4695 3159 : item = lz->fillvalue;
4696 3159 : PyTuple_SET_ITEM(lz->ittuple, i, NULL);
4697 3159 : Py_DECREF(it);
4698 : }
4699 : }
4700 : }
4701 1113550 : PyTuple_SET_ITEM(result, i, item);
4702 : }
4703 : }
4704 1062590 : return result;
4705 : }
4706 :
4707 : static PyObject *
4708 48 : zip_longest_reduce(ziplongestobject *lz, PyObject *Py_UNUSED(ignored))
4709 : {
4710 :
4711 : /* Create a new tuple with empty sequences where appropriate to pickle.
4712 : * Then use setstate to set the fillvalue
4713 : */
4714 : int i;
4715 48 : PyObject *args = PyTuple_New(PyTuple_GET_SIZE(lz->ittuple));
4716 :
4717 48 : if (args == NULL)
4718 0 : return NULL;
4719 144 : for (i=0; i<PyTuple_GET_SIZE(lz->ittuple); i++) {
4720 96 : PyObject *elem = PyTuple_GET_ITEM(lz->ittuple, i);
4721 96 : if (elem == NULL) {
4722 6 : elem = PyTuple_New(0);
4723 6 : if (elem == NULL) {
4724 0 : Py_DECREF(args);
4725 0 : return NULL;
4726 : }
4727 : } else
4728 90 : Py_INCREF(elem);
4729 96 : PyTuple_SET_ITEM(args, i, elem);
4730 : }
4731 48 : return Py_BuildValue("ONO", Py_TYPE(lz), args, lz->fillvalue);
4732 : }
4733 :
4734 : static PyObject *
4735 18 : zip_longest_setstate(ziplongestobject *lz, PyObject *state)
4736 : {
4737 18 : Py_INCREF(state);
4738 18 : Py_XSETREF(lz->fillvalue, state);
4739 18 : Py_RETURN_NONE;
4740 : }
4741 :
4742 : static PyMethodDef zip_longest_methods[] = {
4743 : {"__reduce__", (PyCFunction)zip_longest_reduce, METH_NOARGS,
4744 : reduce_doc},
4745 : {"__setstate__", (PyCFunction)zip_longest_setstate, METH_O,
4746 : setstate_doc},
4747 : {NULL, NULL} /* sentinel */
4748 : };
4749 :
4750 : PyDoc_STRVAR(zip_longest_doc,
4751 : "zip_longest(iter1 [,iter2 [...]], [fillvalue=None]) --> zip_longest object\n\
4752 : \n\
4753 : Return a zip_longest object whose .__next__() method returns a tuple where\n\
4754 : the i-th element comes from the i-th iterable argument. The .__next__()\n\
4755 : method continues until the longest iterable in the argument sequence\n\
4756 : is exhausted and then it raises StopIteration. When the shorter iterables\n\
4757 : are exhausted, the fillvalue is substituted in their place. The fillvalue\n\
4758 : defaults to None or can be specified by a keyword argument.\n\
4759 : ");
4760 :
4761 : static PyTypeObject ziplongest_type = {
4762 : PyVarObject_HEAD_INIT(NULL, 0)
4763 : "itertools.zip_longest", /* tp_name */
4764 : sizeof(ziplongestobject), /* tp_basicsize */
4765 : 0, /* tp_itemsize */
4766 : /* methods */
4767 : (destructor)zip_longest_dealloc, /* tp_dealloc */
4768 : 0, /* tp_vectorcall_offset */
4769 : 0, /* tp_getattr */
4770 : 0, /* tp_setattr */
4771 : 0, /* tp_as_async */
4772 : 0, /* tp_repr */
4773 : 0, /* tp_as_number */
4774 : 0, /* tp_as_sequence */
4775 : 0, /* tp_as_mapping */
4776 : 0, /* tp_hash */
4777 : 0, /* tp_call */
4778 : 0, /* tp_str */
4779 : PyObject_GenericGetAttr, /* tp_getattro */
4780 : 0, /* tp_setattro */
4781 : 0, /* tp_as_buffer */
4782 : Py_TPFLAGS_DEFAULT | Py_TPFLAGS_HAVE_GC |
4783 : Py_TPFLAGS_BASETYPE, /* tp_flags */
4784 : zip_longest_doc, /* tp_doc */
4785 : (traverseproc)zip_longest_traverse, /* tp_traverse */
4786 : 0, /* tp_clear */
4787 : 0, /* tp_richcompare */
4788 : 0, /* tp_weaklistoffset */
4789 : PyObject_SelfIter, /* tp_iter */
4790 : (iternextfunc)zip_longest_next, /* tp_iternext */
4791 : zip_longest_methods, /* tp_methods */
4792 : 0, /* tp_members */
4793 : 0, /* tp_getset */
4794 : 0, /* tp_base */
4795 : 0, /* tp_dict */
4796 : 0, /* tp_descr_get */
4797 : 0, /* tp_descr_set */
4798 : 0, /* tp_dictoffset */
4799 : 0, /* tp_init */
4800 : 0, /* tp_alloc */
4801 : zip_longest_new, /* tp_new */
4802 : PyObject_GC_Del, /* tp_free */
4803 : };
4804 :
4805 :
4806 : /* module level code ********************************************************/
4807 :
4808 : PyDoc_STRVAR(module_doc,
4809 : "Functional tools for creating and using iterators.\n\
4810 : \n\
4811 : Infinite iterators:\n\
4812 : count(start=0, step=1) --> start, start+step, start+2*step, ...\n\
4813 : cycle(p) --> p0, p1, ... plast, p0, p1, ...\n\
4814 : repeat(elem [,n]) --> elem, elem, elem, ... endlessly or up to n times\n\
4815 : \n\
4816 : Iterators terminating on the shortest input sequence:\n\
4817 : accumulate(p[, func]) --> p0, p0+p1, p0+p1+p2\n\
4818 : chain(p, q, ...) --> p0, p1, ... plast, q0, q1, ...\n\
4819 : chain.from_iterable([p, q, ...]) --> p0, p1, ... plast, q0, q1, ...\n\
4820 : compress(data, selectors) --> (d[0] if s[0]), (d[1] if s[1]), ...\n\
4821 : dropwhile(pred, seq) --> seq[n], seq[n+1], starting when pred fails\n\
4822 : groupby(iterable[, keyfunc]) --> sub-iterators grouped by value of keyfunc(v)\n\
4823 : filterfalse(pred, seq) --> elements of seq where pred(elem) is False\n\
4824 : islice(seq, [start,] stop [, step]) --> elements from\n\
4825 : seq[start:stop:step]\n\
4826 : pairwise(s) --> (s[0],s[1]), (s[1],s[2]), (s[2], s[3]), ...\n\
4827 : starmap(fun, seq) --> fun(*seq[0]), fun(*seq[1]), ...\n\
4828 : tee(it, n=2) --> (it1, it2 , ... itn) splits one iterator into n\n\
4829 : takewhile(pred, seq) --> seq[0], seq[1], until pred fails\n\
4830 : zip_longest(p, q, ...) --> (p[0], q[0]), (p[1], q[1]), ...\n\
4831 : \n\
4832 : Combinatoric generators:\n\
4833 : product(p, q, ... [repeat=1]) --> cartesian product\n\
4834 : permutations(p[, r])\n\
4835 : combinations(p, r)\n\
4836 : combinations_with_replacement(p, r)\n\
4837 : ");
4838 :
4839 : static int
4840 2005 : itertoolsmodule_exec(PyObject *m)
4841 : {
4842 2005 : PyTypeObject *typelist[] = {
4843 : &accumulate_type,
4844 : &combinations_type,
4845 : &cwr_type,
4846 : &cycle_type,
4847 : &dropwhile_type,
4848 : &takewhile_type,
4849 : &islice_type,
4850 : &starmap_type,
4851 : &chain_type,
4852 : &compress_type,
4853 : &filterfalse_type,
4854 : &count_type,
4855 : &ziplongest_type,
4856 : &pairwise_type,
4857 : &permutations_type,
4858 : &product_type,
4859 : &repeat_type,
4860 : &groupby_type,
4861 : &_grouper_type,
4862 : &tee_type,
4863 : &teedataobject_type
4864 : };
4865 :
4866 2005 : Py_SET_TYPE(&teedataobject_type, &PyType_Type);
4867 :
4868 44110 : for (size_t i = 0; i < Py_ARRAY_LENGTH(typelist); i++) {
4869 42105 : if (PyModule_AddType(m, typelist[i]) < 0) {
4870 0 : return -1;
4871 : }
4872 : }
4873 :
4874 2005 : return 0;
4875 : }
4876 :
4877 : static struct PyModuleDef_Slot itertoolsmodule_slots[] = {
4878 : {Py_mod_exec, itertoolsmodule_exec},
4879 : {0, NULL}
4880 : };
4881 :
4882 : static PyMethodDef module_methods[] = {
4883 : ITERTOOLS_TEE_METHODDEF
4884 : {NULL, NULL} /* sentinel */
4885 : };
4886 :
4887 :
4888 : static struct PyModuleDef itertoolsmodule = {
4889 : PyModuleDef_HEAD_INIT,
4890 : "itertools",
4891 : module_doc,
4892 : 0,
4893 : module_methods,
4894 : itertoolsmodule_slots,
4895 : NULL,
4896 : NULL,
4897 : NULL
4898 : };
4899 :
4900 : PyMODINIT_FUNC
4901 2005 : PyInit_itertools(void)
4902 : {
4903 2005 : return PyModuleDef_Init(&itertoolsmodule);
4904 : }
|
