Branch data 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 : 24 : _grouper_traverse(_grouperobject *igo, visitproc visit, void *arg)
470 : : {
471 [ + - - + ]: 24 : Py_VISIT(igo->parent);
472 [ + - - + ]: 24 : Py_VISIT(igo->tgtkey);
473 : 24 : 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 : : 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 : 20168459 : teedataobject_getitem(teedataobject *tdo, int i)
620 : : {
621 : : PyObject *value;
622 : :
623 : : assert(i < LINKCELLS);
624 [ + + ]: 20168459 : if (i < tdo->numread)
625 : 75015 : value = tdo->values[i];
626 : : else {
627 : : /* this is the lead iterator, so fetch more data */
628 : : assert(i == tdo->numread);
629 [ + + ]: 20093444 : if (tdo->running) {
630 : 2 : PyErr_SetString(PyExc_RuntimeError,
631 : : "cannot re-enter the tee iterator");
632 : 2 : return NULL;
633 : : }
634 : 20093442 : tdo->running = 1;
635 : 20093442 : value = PyIter_Next(tdo->it);
636 : 20093442 : tdo->running = 0;
637 [ + + ]: 20093442 : if (value == NULL)
638 : 255 : return NULL;
639 : 20093187 : tdo->numread++;
640 : 20093187 : tdo->values[i] = value;
641 : : }
642 : 20168202 : Py_INCREF(value);
643 : 20168202 : return value;
644 : : }
645 : :
646 : : static int
647 : 2446117 : teedataobject_traverse(teedataobject *tdo, visitproc visit, void * arg)
648 : : {
649 : : int i;
650 : :
651 [ + - - + ]: 2446117 : Py_VISIT(tdo->it);
652 [ + + ]: 141869077 : for (i = 0; i < tdo->numread; i++)
653 [ + - - + ]: 139422960 : Py_VISIT(tdo->values[i]);
654 [ + + - + ]: 2446117 : Py_VISIT(tdo->nextlink);
655 : 2446117 : return 0;
656 : : }
657 : :
658 : : static void
659 : 352737 : teedataobject_safe_decref(PyObject *obj)
660 : : {
661 [ + + + - : 1056276 : 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 [ + + ]: 20446075 : for (i=0 ; i<tdo->numread ; i++)
679 [ + + ]: 20093338 : 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 : : 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 : : 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 : 20168459 : tee_next(teeobject *to)
818 : : {
819 : : PyObject *value, *link;
820 : :
821 [ + + ]: 20168459 : 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 : 20168459 : value = teedataobject_getitem(to->dataobj, to->index);
829 [ + + ]: 20168459 : if (value == NULL)
830 : 257 : return NULL;
831 : 20168202 : to->index++;
832 : 20168202 : return value;
833 : : }
834 : :
835 : : static int
836 : 261 : tee_traverse(teeobject *to, visitproc visit, void *arg)
837 : : {
838 [ + - - + ]: 261 : Py_VISIT((PyObject *)to->dataobj);
839 : 261 : 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 : 6221273 : cycle_next(cycleobject *lz)
1142 : : {
1143 : : PyObject *item;
1144 : :
1145 [ + + ]: 6221273 : 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 [ + + ]: 6215617 : 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 : 702496 : 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 : 578 : 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 : 578 : it = PyObject_GetIter(seq);
1295 [ + + ]: 578 : if (it == NULL)
1296 : 10 : return NULL;
1297 : :
1298 : : /* create dropwhileobject structure */
1299 : 568 : lz = (dropwhileobject *)type->tp_alloc(type, 0);
1300 [ - + ]: 568 : if (lz == NULL) {
1301 : 0 : Py_DECREF(it);
1302 : 0 : return NULL;
1303 : : }
1304 : 568 : Py_INCREF(func);
1305 : 568 : lz->func = func;
1306 : 568 : lz->it = it;
1307 : 568 : lz->start = 0;
1308 : :
1309 : 568 : return (PyObject *)lz;
1310 : : }
1311 : :
1312 : : static void
1313 : 568 : dropwhile_dealloc(dropwhileobject *lz)
1314 : : {
1315 : 568 : PyObject_GC_UnTrack(lz);
1316 : 568 : Py_XDECREF(lz->func);
1317 : 568 : Py_XDECREF(lz->it);
1318 : 568 : Py_TYPE(lz)->tp_free(lz);
1319 : 568 : }
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 : 6964 : dropwhile_next(dropwhileobject *lz)
1331 : : {
1332 : : PyObject *item, *good;
1333 : 6964 : PyObject *it = lz->it;
1334 : : long ok;
1335 : : PyObject *(*iternext)(PyObject *);
1336 : :
1337 : 6964 : iternext = *Py_TYPE(it)->tp_iternext;
1338 : : for (;;) {
1339 : 7314 : item = iternext(it);
1340 [ + + ]: 7314 : if (item == NULL)
1341 : 539 : return NULL;
1342 [ + + ]: 6775 : if (lz->start == 1)
1343 : 5928 : return item;
1344 : :
1345 : 847 : good = PyObject_CallOneArg(lz->func, item);
1346 [ + + ]: 847 : if (good == NULL) {
1347 : 2 : Py_DECREF(item);
1348 : 2 : return NULL;
1349 : : }
1350 : 845 : ok = PyObject_IsTrue(good);
1351 : 845 : Py_DECREF(good);
1352 [ + + ]: 845 : if (ok == 0) {
1353 : 495 : lz->start = 1;
1354 : 495 : return item;
1355 : : }
1356 : 350 : Py_DECREF(item);
1357 [ - + ]: 350 : 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 : 173580 : islice_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
1606 : : {
1607 : : PyObject *seq;
1608 : 173580 : Py_ssize_t start=0, stop=-1, step=1;
1609 : 173580 : PyObject *it, *a1=NULL, *a2=NULL, *a3=NULL;
1610 : : Py_ssize_t numargs;
1611 : : isliceobject *lz;
1612 : :
1613 [ + + + + : 173580 : if ((type == &islice_type || type->tp_init == islice_type.tp_init) &&
+ + ]
1614 [ + + ]: 22 : !_PyArg_NoKeywords("islice", kwds))
1615 : 1 : return NULL;
1616 : :
1617 [ + + ]: 173579 : if (!PyArg_UnpackTuple(args, "islice", 2, 4, &seq, &a1, &a2, &a3))
1618 : 2 : return NULL;
1619 : :
1620 : 173577 : numargs = PyTuple_Size(args);
1621 [ + + ]: 173577 : if (numargs == 2) {
1622 [ + + ]: 145004 : if (a1 != Py_None) {
1623 : 144896 : stop = PyNumber_AsSsize_t(a1, PyExc_OverflowError);
1624 [ + + ]: 144896 : 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 [ + + ]: 28573 : if (a1 != Py_None)
1635 : 28571 : start = PyNumber_AsSsize_t(a1, PyExc_OverflowError);
1636 [ + + + - ]: 28573 : if (start == -1 && PyErr_Occurred())
1637 : 2 : PyErr_Clear();
1638 [ + + ]: 28573 : 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 [ + + + + ]: 173574 : 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 [ + + ]: 173570 : 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 [ + + ]: 173570 : 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 : 173568 : it = PyObject_GetIter(seq);
1671 [ + + ]: 173568 : if (it == NULL)
1672 : 23074 : return NULL;
1673 : :
1674 : : /* create isliceobject structure */
1675 : 150494 : lz = (isliceobject *)type->tp_alloc(type, 0);
1676 [ - + ]: 150494 : if (lz == NULL) {
1677 : 0 : Py_DECREF(it);
1678 : 0 : return NULL;
1679 : : }
1680 : 150494 : lz->it = it;
1681 : 150494 : lz->next = start;
1682 : 150494 : lz->stop = stop;
1683 : 150494 : lz->step = step;
1684 : 150494 : lz->cnt = 0L;
1685 : :
1686 : 150494 : return (PyObject *)lz;
1687 : : }
1688 : :
1689 : : static void
1690 : 150494 : islice_dealloc(isliceobject *lz)
1691 : : {
1692 : 150494 : PyObject_GC_UnTrack(lz);
1693 : 150494 : Py_XDECREF(lz->it);
1694 : 150494 : Py_TYPE(lz)->tp_free(lz);
1695 : 150494 : }
1696 : :
1697 : : static int
1698 : 58 : islice_traverse(isliceobject *lz, visitproc visit, void *arg)
1699 : : {
1700 [ + + - + ]: 58 : Py_VISIT(lz->it);
1701 : 58 : return 0;
1702 : : }
1703 : :
1704 : : static PyObject *
1705 : 9234452 : islice_next(isliceobject *lz)
1706 : : {
1707 : : PyObject *item;
1708 : 9234452 : PyObject *it = lz->it;
1709 : 9234452 : Py_ssize_t stop = lz->stop;
1710 : : Py_ssize_t oldnext;
1711 : : PyObject *(*iternext)(PyObject *);
1712 : :
1713 [ + + ]: 9234452 : if (it == NULL)
1714 : 12 : return NULL;
1715 : :
1716 : 9234440 : iternext = *Py_TYPE(it)->tp_iternext;
1717 [ + + ]: 9763102 : while (lz->cnt < lz->next) {
1718 : 528723 : item = iternext(it);
1719 [ + + ]: 528723 : if (item == NULL)
1720 : 61 : goto empty;
1721 : 528662 : Py_DECREF(item);
1722 : 528662 : lz->cnt++;
1723 : : }
1724 [ + + + + ]: 9234379 : if (stop != -1 && lz->cnt >= stop)
1725 : 32777 : goto empty;
1726 : 9201602 : item = iternext(it);
1727 [ + + ]: 9201602 : if (item == NULL)
1728 : 111065 : goto empty;
1729 : 9090537 : lz->cnt++;
1730 : 9090537 : oldnext = lz->next;
1731 : : /* The (size_t) cast below avoids the danger of undefined
1732 : : behaviour from signed integer overflow. */
1733 : 9090537 : lz->next += (size_t)lz->step;
1734 [ + + + + : 9090537 : if (lz->next < oldnext || (stop != -1 && lz->next > stop))
+ + ]
1735 : 29 : lz->next = stop;
1736 : 9090537 : return item;
1737 : :
1738 : 143903 : empty:
1739 [ + - ]: 143903 : Py_CLEAR(lz->it);
1740 : 143903 : 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 : 9030 : 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 : 9030 : it = PyObject_GetIter(seq);
1877 [ + + ]: 9030 : if (it == NULL)
1878 : 10 : return NULL;
1879 : :
1880 : : /* create starmapobject structure */
1881 : 9020 : lz = (starmapobject *)type->tp_alloc(type, 0);
1882 [ - + ]: 9020 : if (lz == NULL) {
1883 : 0 : Py_DECREF(it);
1884 : 0 : return NULL;
1885 : : }
1886 : 9020 : Py_INCREF(func);
1887 : 9020 : lz->func = func;
1888 : 9020 : lz->it = it;
1889 : :
1890 : 9020 : return (PyObject *)lz;
1891 : : }
1892 : :
1893 : : static void
1894 : 9020 : starmap_dealloc(starmapobject *lz)
1895 : : {
1896 : 9020 : PyObject_GC_UnTrack(lz);
1897 : 9020 : Py_XDECREF(lz->func);
1898 : 9020 : Py_XDECREF(lz->it);
1899 : 9020 : Py_TYPE(lz)->tp_free(lz);
1900 : 9020 : }
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 : 34316 : starmap_next(starmapobject *lz)
1912 : : {
1913 : : PyObject *args;
1914 : : PyObject *result;
1915 : 34316 : PyObject *it = lz->it;
1916 : :
1917 : 34316 : args = (*Py_TYPE(it)->tp_iternext)(it);
1918 [ + + ]: 34316 : if (args == NULL)
1919 : 9012 : 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 : 34560 : chain_new_internal(PyTypeObject *type, PyObject *source)
2002 : : {
2003 : : chainobject *lz;
2004 : :
2005 : 34560 : lz = (chainobject *)type->tp_alloc(type, 0);
2006 [ - + ]: 34560 : if (lz == NULL) {
2007 : 0 : Py_DECREF(source);
2008 : 0 : return NULL;
2009 : : }
2010 : :
2011 : 34560 : lz->source = source;
2012 : 34560 : lz->active = NULL;
2013 : 34560 : return (PyObject *)lz;
2014 : : }
2015 : :
2016 : : static PyObject *
2017 : 24888 : chain_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2018 : : {
2019 : : PyObject *source;
2020 : :
2021 [ + + + + : 24888 : if ((type == &chain_type || type->tp_init == chain_type.tp_init) &&
+ + ]
2022 [ + - ]: 1 : !_PyArg_NoKeywords("chain", kwds))
2023 : 1 : return NULL;
2024 : :
2025 : 24887 : source = PyObject_GetIter(args);
2026 [ - + ]: 24887 : if (source == NULL)
2027 : 0 : return NULL;
2028 : :
2029 : 24887 : 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 : 34560 : chain_dealloc(chainobject *lz)
2055 : : {
2056 : 34560 : PyObject_GC_UnTrack(lz);
2057 : 34560 : Py_XDECREF(lz->active);
2058 : 34560 : Py_XDECREF(lz->source);
2059 : 34560 : Py_TYPE(lz)->tp_free(lz);
2060 : 34560 : }
2061 : :
2062 : : static int
2063 : 3942 : chain_traverse(chainobject *lz, visitproc visit, void *arg)
2064 : : {
2065 [ + + - + ]: 3942 : Py_VISIT(lz->source);
2066 [ + + - + ]: 3942 : Py_VISIT(lz->active);
2067 : 3942 : return 0;
2068 : : }
2069 : :
2070 : : static PyObject *
2071 : 4257093 : 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 [ + + ]: 18647301 : while (lz->source != NULL) {
2079 [ + + ]: 14390203 : if (lz->active == NULL) {
2080 : 10167609 : PyObject *iterable = PyIter_Next(lz->source);
2081 [ + + ]: 10167609 : if (iterable == NULL) {
2082 [ + - ]: 30892 : Py_CLEAR(lz->source);
2083 : 30892 : return NULL; /* no more input sources */
2084 : : }
2085 : 10136717 : lz->active = PyObject_GetIter(iterable);
2086 : 10136717 : Py_DECREF(iterable);
2087 [ + + ]: 10136717 : if (lz->active == NULL) {
2088 [ + - ]: 19 : Py_CLEAR(lz->source);
2089 : 19 : return NULL; /* input not iterable */
2090 : : }
2091 : : }
2092 : 14359292 : item = (*Py_TYPE(lz->active)->tp_iternext)(lz->active);
2093 [ + + ]: 14359292 : if (item != NULL)
2094 : 4226169 : return item;
2095 [ + + ]: 10133123 : 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 [ - + ]: 10133115 : 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 : 59190 : product_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
2228 : : {
2229 : : productobject *lz;
2230 : 59190 : Py_ssize_t nargs, npools, repeat=1;
2231 : 59190 : PyObject *pools = NULL;
2232 : 59190 : Py_ssize_t *indices = NULL;
2233 : : Py_ssize_t i;
2234 : :
2235 [ + + ]: 59190 : 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 : : assert(PyTuple_CheckExact(args));
2254 [ + + ]: 59189 : if (repeat == 0) {
2255 : 26 : nargs = 0;
2256 : : } else {
2257 : 59163 : nargs = PyTuple_GET_SIZE(args);
2258 [ - + ]: 59163 : 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 : 59189 : npools = nargs * repeat;
2264 : :
2265 [ + - ]: 59189 : indices = PyMem_New(Py_ssize_t, npools);
2266 [ - + ]: 59189 : if (indices == NULL) {
2267 : : PyErr_NoMemory();
2268 : 0 : goto error;
2269 : : }
2270 : :
2271 : 59189 : pools = PyTuple_New(npools);
2272 [ - + ]: 59189 : if (pools == NULL)
2273 : 0 : goto error;
2274 : :
2275 [ + + ]: 149524 : for (i=0; i < nargs ; ++i) {
2276 : 90351 : PyObject *item = PyTuple_GET_ITEM(args, i);
2277 : 90351 : PyObject *pool = PySequence_Tuple(item);
2278 [ + + ]: 90351 : if (pool == NULL)
2279 : 16 : goto error;
2280 : 90335 : PyTuple_SET_ITEM(pools, i, pool);
2281 : 90335 : indices[i] = 0;
2282 : : }
2283 [ + + ]: 60164 : 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 : 59173 : lz = (productobject *)type->tp_alloc(type, 0);
2292 [ - + ]: 59173 : if (lz == NULL)
2293 : 0 : goto error;
2294 : :
2295 : 59173 : lz->pools = pools;
2296 : 59173 : lz->indices = indices;
2297 : 59173 : lz->result = NULL;
2298 : 59173 : lz->stopped = 0;
2299 : :
2300 : 59173 : 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 : 59173 : product_dealloc(productobject *lz)
2311 : : {
2312 : 59173 : PyObject_GC_UnTrack(lz);
2313 : 59173 : Py_XDECREF(lz->pools);
2314 : 59173 : Py_XDECREF(lz->result);
2315 [ + - ]: 59173 : if (lz->indices != NULL)
2316 : 59173 : PyMem_Free(lz->indices);
2317 : 59173 : Py_TYPE(lz)->tp_free(lz);
2318 : 59173 : }
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 : 1533036 : product_next(productobject *lz)
2342 : : {
2343 : : PyObject *pool;
2344 : : PyObject *elem;
2345 : : PyObject *oldelem;
2346 : 1533036 : PyObject *pools = lz->pools;
2347 : 1533036 : PyObject *result = lz->result;
2348 : 1533036 : Py_ssize_t npools = PyTuple_GET_SIZE(pools);
2349 : : Py_ssize_t i;
2350 : :
2351 [ + + ]: 1533036 : if (lz->stopped)
2352 : 19 : return NULL;
2353 : :
2354 [ + + ]: 1533017 : if (result == NULL) {
2355 : : /* On the first pass, return an initial tuple filled with the
2356 : : first element from each pool. */
2357 : 59139 : result = PyTuple_New(npools);
2358 [ - + ]: 59139 : if (result == NULL)
2359 : 0 : goto empty;
2360 : 59139 : lz->result = result;
2361 [ + + ]: 149673 : for (i=0; i < npools; i++) {
2362 : 90860 : pool = PyTuple_GET_ITEM(pools, i);
2363 [ + + ]: 90860 : if (PyTuple_GET_SIZE(pool) == 0)
2364 : 326 : goto empty;
2365 : 90534 : elem = PyTuple_GET_ITEM(pool, 0);
2366 : 90534 : Py_INCREF(elem);
2367 : 90534 : PyTuple_SET_ITEM(result, i, elem);
2368 : : }
2369 : : } else {
2370 : 1473878 : Py_ssize_t *indices = lz->indices;
2371 : :
2372 : : /* Copy the previous result tuple or re-use it if available */
2373 [ + + ]: 1473878 : if (Py_REFCNT(result) > 1) {
2374 : 1369215 : PyObject *old_result = result;
2375 : 1369215 : result = _PyTuple_FromArray(_PyTuple_ITEMS(old_result), npools);
2376 [ - + ]: 1369215 : if (result == NULL)
2377 : 0 : goto empty;
2378 : 1369215 : lz->result = result;
2379 : 1369215 : 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 : 3 : _PyObject_GC_TRACK(result);
2385 : : }
2386 : : /* Now, we've got the only copy so we can update it in-place */
2387 : : 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 [ + + ]: 1818390 : for (i=npools-1 ; i >= 0 ; i--) {
2392 : 1760097 : pool = PyTuple_GET_ITEM(pools, i);
2393 : 1760097 : indices[i]++;
2394 [ + + ]: 1760097 : if (indices[i] == PyTuple_GET_SIZE(pool)) {
2395 : : /* Roll-over and advance to next pool */
2396 : 344512 : indices[i] = 0;
2397 : 344512 : elem = PyTuple_GET_ITEM(pool, 0);
2398 : 344512 : Py_INCREF(elem);
2399 : 344512 : oldelem = PyTuple_GET_ITEM(result, i);
2400 : 344512 : PyTuple_SET_ITEM(result, i, elem);
2401 : 344512 : Py_DECREF(oldelem);
2402 : : } else {
2403 : : /* No rollover. Just increment and stop here. */
2404 : 1415585 : elem = PyTuple_GET_ITEM(pool, indices[i]);
2405 : 1415585 : Py_INCREF(elem);
2406 : 1415585 : oldelem = PyTuple_GET_ITEM(result, i);
2407 : 1415585 : PyTuple_SET_ITEM(result, i, elem);
2408 : 1415585 : Py_DECREF(oldelem);
2409 : 1415585 : break;
2410 : : }
2411 : : }
2412 : :
2413 : : /* If i is negative, then the indices have all rolled-over
2414 : : and we're done. */
2415 [ + + ]: 1473878 : if (i < 0)
2416 : 58293 : goto empty;
2417 : : }
2418 : :
2419 : 1474398 : Py_INCREF(result);
2420 : 1474398 : return result;
2421 : :
2422 : 58619 : empty:
2423 : 58619 : lz->stopped = 1;
2424 : 58619 : 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 : : 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 : 1079375 : combinations_next(combinationsobject *co)
2674 : : {
2675 : : PyObject *elem;
2676 : : PyObject *oldelem;
2677 : 1079375 : PyObject *pool = co->pool;
2678 : 1079375 : Py_ssize_t *indices = co->indices;
2679 : 1079375 : PyObject *result = co->result;
2680 : 1079375 : Py_ssize_t n = PyTuple_GET_SIZE(pool);
2681 : 1079375 : Py_ssize_t r = co->r;
2682 : : Py_ssize_t i, j, index;
2683 : :
2684 [ + + ]: 1079375 : if (co->stopped)
2685 : 258 : return NULL;
2686 : :
2687 [ + + ]: 1079117 : 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 [ + + ]: 1073522 : 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 [ + + ]: 1048805 : 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 : : 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 [ + + ]: 1073522 : 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 : 1068025 : indices[i]++;
2735 [ + + ]: 2124770 : for (j=i+1 ; j<r ; j++)
2736 : 1056745 : 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 [ + + ]: 3192795 : 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 : : 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 : : 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 : : 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 : : 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 : 27907 : 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 : 27907 : PyObject *pool = NULL;
3267 : 27907 : Py_ssize_t *indices = NULL;
3268 : 27907 : Py_ssize_t *cycles = NULL;
3269 : : Py_ssize_t i;
3270 : :
3271 : 27907 : pool = PySequence_Tuple(iterable);
3272 [ + + ]: 27907 : if (pool == NULL)
3273 : 1 : goto error;
3274 : 27906 : n = PyTuple_GET_SIZE(pool);
3275 : :
3276 : 27906 : r = n;
3277 [ + + ]: 27906 : 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 [ + + ]: 27905 : if (r < 0) {
3287 : 1 : PyErr_SetString(PyExc_ValueError, "r must be non-negative");
3288 : 1 : goto error;
3289 : : }
3290 : :
3291 [ + - ]: 27904 : indices = PyMem_New(Py_ssize_t, n);
3292 [ + - ]: 27904 : cycles = PyMem_New(Py_ssize_t, r);
3293 [ + - - + ]: 27904 : if (indices == NULL || cycles == NULL) {
3294 : : PyErr_NoMemory();
3295 : 0 : goto error;
3296 : : }
3297 : :
3298 [ + + ]: 67490 : for (i=0 ; i<n ; i++)
3299 : 39586 : indices[i] = i;
3300 [ + + ]: 66272 : for (i=0 ; i<r ; i++)
3301 : 38368 : cycles[i] = n - i;
3302 : :
3303 : : /* create permutationsobject structure */
3304 : 27904 : po = (permutationsobject *)type->tp_alloc(type, 0);
3305 [ - + ]: 27904 : if (po == NULL)
3306 : 0 : goto error;
3307 : :
3308 : 27904 : po->pool = pool;
3309 : 27904 : po->indices = indices;
3310 : 27904 : po->cycles = cycles;
3311 : 27904 : po->result = NULL;
3312 : 27904 : po->r = r;
3313 : 27904 : po->stopped = r > n ? 1 : 0;
3314 : :
3315 : 27904 : 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 : 27904 : permutations_dealloc(permutationsobject *po)
3328 : : {
3329 : 27904 : PyObject_GC_UnTrack(po);
3330 : 27904 : Py_XDECREF(po->pool);
3331 : 27904 : Py_XDECREF(po->result);
3332 : 27904 : PyMem_Free(po->indices);
3333 : 27904 : PyMem_Free(po->cycles);
3334 : 27904 : Py_TYPE(po)->tp_free(po);
3335 : 27904 : }
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 : 72718 : permutations_next(permutationsobject *po)
3358 : : {
3359 : : PyObject *elem;
3360 : : PyObject *oldelem;
3361 : 72718 : PyObject *pool = po->pool;
3362 : 72718 : Py_ssize_t *indices = po->indices;
3363 : 72718 : Py_ssize_t *cycles = po->cycles;
3364 : 72718 : PyObject *result = po->result;
3365 : 72718 : Py_ssize_t n = PyTuple_GET_SIZE(pool);
3366 : 72718 : Py_ssize_t r = po->r;
3367 : : Py_ssize_t i, j, k, index;
3368 : :
3369 [ + + ]: 72718 : if (po->stopped)
3370 : 252 : return NULL;
3371 : :
3372 [ + + ]: 72466 : if (result == NULL) {
3373 : : /* On the first pass, initialize result tuple using the indices */
3374 : 27522 : result = PyTuple_New(r);
3375 [ - + ]: 27522 : if (result == NULL)
3376 : 0 : goto empty;
3377 : 27522 : po->result = result;
3378 [ + + ]: 64647 : for (i=0; i<r ; i++) {
3379 : 37125 : index = indices[i];
3380 : 37125 : elem = PyTuple_GET_ITEM(pool, index);
3381 : 37125 : Py_INCREF(elem);
3382 : 37125 : PyTuple_SET_ITEM(result, i, elem);
3383 : : }
3384 : : } else {
3385 [ + + ]: 44944 : if (n == 0)
3386 : 29 : goto empty;
3387 : :
3388 : : /* Copy the previous result tuple or re-use it if available */
3389 [ + + ]: 44915 : if (Py_REFCNT(result) > 1) {
3390 : 44602 : PyObject *old_result = result;
3391 : 44602 : result = _PyTuple_FromArray(_PyTuple_ITEMS(old_result), r);
3392 [ - + ]: 44602 : if (result == NULL)
3393 : 0 : goto empty;
3394 : 44602 : po->result = result;
3395 : 44602 : 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 : : assert(r == 0 || Py_REFCNT(result) == 1);
3404 : :
3405 : : /* Decrement rightmost cycle, moving leftward upon zero rollover */
3406 [ + + ]: 99211 : for (i=r-1 ; i>=0 ; i--) {
3407 : 71948 : cycles[i] -= 1;
3408 [ + + ]: 71948 : if (cycles[i] == 0) {
3409 : : /* rotatation: indices[i:] = indices[i+1:] + indices[i:i+1] */
3410 : 54296 : index = indices[i];
3411 [ + + ]: 71071 : for (j=i ; j<n-1 ; j++)
3412 : 16775 : indices[j] = indices[j+1];
3413 : 54296 : indices[n-1] = index;
3414 : 54296 : cycles[i] = n - i;
3415 : : } else {
3416 : 17652 : j = cycles[i];
3417 : 17652 : index = indices[i];
3418 : 17652 : indices[i] = indices[n-j];
3419 : 17652 : indices[n-j] = index;
3420 : :
3421 [ + + ]: 53355 : 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 : 35703 : index = indices[k];
3425 : 35703 : elem = PyTuple_GET_ITEM(pool, index);
3426 : 35703 : Py_INCREF(elem);
3427 : 35703 : oldelem = PyTuple_GET_ITEM(result, k);
3428 : 35703 : PyTuple_SET_ITEM(result, k, elem);
3429 : 35703 : Py_DECREF(oldelem);
3430 : : }
3431 : 17652 : break;
3432 : : }
3433 : : }
3434 : : /* If i is negative, then the cycles have all
3435 : : rolled-over and we're done. */
3436 [ + + ]: 44915 : if (i < 0)
3437 : 27263 : goto empty;
3438 : : }
3439 : 45174 : Py_INCREF(result);
3440 : 45174 : return result;
3441 : :
3442 : 27292 : empty:
3443 : 27292 : po->stopped = 1;
3444 : 27292 : 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 : : 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 : 413 : 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 : 413 : it = PyObject_GetIter(seq);
4001 [ + + ]: 413 : if (it == NULL)
4002 : 11 : return NULL;
4003 : :
4004 : : /* create filterfalseobject structure */
4005 : 402 : lz = (filterfalseobject *)type->tp_alloc(type, 0);
4006 [ - + ]: 402 : if (lz == NULL) {
4007 : 0 : Py_DECREF(it);
4008 : 0 : return NULL;
4009 : : }
4010 : 402 : Py_INCREF(func);
4011 : 402 : lz->func = func;
4012 : 402 : lz->it = it;
4013 : :
4014 : 402 : return (PyObject *)lz;
4015 : : }
4016 : :
4017 : : static void
4018 : 402 : filterfalse_dealloc(filterfalseobject *lz)
4019 : : {
4020 : 402 : PyObject_GC_UnTrack(lz);
4021 : 402 : Py_XDECREF(lz->func);
4022 : 402 : Py_XDECREF(lz->it);
4023 : 402 : Py_TYPE(lz)->tp_free(lz);
4024 : 402 : }
4025 : :
4026 : : static int
4027 : 176 : filterfalse_traverse(filterfalseobject *lz, visitproc visit, void *arg)
4028 : : {
4029 [ + - - + ]: 176 : Py_VISIT(lz->it);
4030 [ + - - + ]: 176 : Py_VISIT(lz->func);
4031 : 176 : return 0;
4032 : : }
4033 : :
4034 : : static PyObject *
4035 : 305227 : filterfalse_next(filterfalseobject *lz)
4036 : : {
4037 : : PyObject *item;
4038 : 305227 : PyObject *it = lz->it;
4039 : : long ok;
4040 : : PyObject *(*iternext)(PyObject *);
4041 : :
4042 : 305227 : iternext = *Py_TYPE(it)->tp_iternext;
4043 : : for (;;) {
4044 : 308590 : item = iternext(it);
4045 [ + + ]: 308590 : if (item == NULL)
4046 : 415 : return NULL;
4047 : :
4048 [ + + + + ]: 308175 : if (lz->func == Py_None || lz->func == (PyObject *)&PyBool_Type) {
4049 : 16 : ok = PyObject_IsTrue(item);
4050 : : } else {
4051 : : PyObject *good;
4052 : 308159 : good = PyObject_CallOneArg(lz->func, item);
4053 [ + + ]: 308159 : if (good == NULL) {
4054 : 1 : Py_DECREF(item);
4055 : 1 : return NULL;
4056 : : }
4057 : 308158 : ok = PyObject_IsTrue(good);
4058 : 308158 : Py_DECREF(good);
4059 : : }
4060 [ + + ]: 308174 : if (ok == 0)
4061 : 304811 : 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 : 17276 : 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 : 17276 : Py_ssize_t cnt = 0;
4174 : : long step;
4175 : :
4176 [ + + + + : 17276 : 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 [ + + + + : 19006 : 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 [ + + ]: 17274 : if (long_cnt != NULL) {
4187 [ + + ]: 13210 : if (fast_mode) {
4188 : : assert(PyLong_Check(long_cnt));
4189 : 13193 : cnt = PyLong_AsSsize_t(long_cnt);
4190 [ + + + + ]: 13193 : if (cnt == -1 && PyErr_Occurred()) {
4191 : 530 : PyErr_Clear();
4192 : 530 : fast_mode = 0;
4193 : : }
4194 : : }
4195 : : } else {
4196 : 4064 : cnt = 0;
4197 : 4064 : long_cnt = _PyLong_GetZero();
4198 : : }
4199 : 17274 : Py_INCREF(long_cnt);
4200 : :
4201 : : /* If not specified, step defaults to 1 */
4202 [ + + ]: 17274 : if (long_step == NULL) {
4203 : 15537 : long_step = _PyLong_GetOne();
4204 : : }
4205 : 17274 : Py_INCREF(long_step);
4206 : :
4207 : : assert(long_cnt != NULL && long_step != NULL);
4208 : :
4209 : : /* Fast mode only works when the step is 1 */
4210 [ + + ]: 17274 : if (fast_mode) {
4211 : : assert(PyLong_Check(long_step));
4212 : 16727 : step = PyLong_AsLong(long_step);
4213 [ + + ]: 16727 : if (step != 1) {
4214 : 1164 : fast_mode = 0;
4215 [ + + + + ]: 1164 : if (step == -1 && PyErr_Occurred())
4216 : 267 : PyErr_Clear();
4217 : : }
4218 : : }
4219 : :
4220 [ + + ]: 17274 : if (fast_mode)
4221 [ + - ]: 15563 : Py_CLEAR(long_cnt);
4222 : : else
4223 : 1711 : cnt = PY_SSIZE_T_MAX;
4224 : :
4225 : : assert((cnt != PY_SSIZE_T_MAX && long_cnt == NULL && fast_mode) ||
4226 : : (cnt == PY_SSIZE_T_MAX && long_cnt != NULL && !fast_mode));
4227 : : assert(!fast_mode ||
4228 : : (PyLong_Check(long_step) && PyLong_AS_LONG(long_step) == 1));
4229 : :
4230 : : /* create countobject structure */
4231 : 17274 : lz = (countobject *)type->tp_alloc(type, 0);
4232 [ - + ]: 17274 : if (lz == NULL) {
4233 : 0 : Py_XDECREF(long_cnt);
4234 : 0 : Py_DECREF(long_step);
4235 : 0 : return NULL;
4236 : : }
4237 : 17274 : lz->cnt = cnt;
4238 : 17274 : lz->long_cnt = long_cnt;
4239 : 17274 : lz->long_step = long_step;
4240 : :
4241 : 17274 : return (PyObject *)lz;
4242 : : }
4243 : :
4244 : : static void
4245 : 17270 : count_dealloc(countobject *lz)
4246 : : {
4247 : 17270 : PyObject_GC_UnTrack(lz);
4248 : 17270 : Py_XDECREF(lz->long_cnt);
4249 : 17270 : Py_XDECREF(lz->long_step);
4250 : 17270 : Py_TYPE(lz)->tp_free(lz);
4251 : 17270 : }
4252 : :
4253 : : static int
4254 : 164200 : count_traverse(countobject *lz, visitproc visit, void *arg)
4255 : : {
4256 [ + + - + ]: 164200 : Py_VISIT(lz->long_cnt);
4257 [ + - - + ]: 164200 : Py_VISIT(lz->long_step);
4258 : 164200 : 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 : : 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 : 183119 : count_next(countobject *lz)
4285 : : {
4286 [ + + ]: 183119 : if (lz->cnt == PY_SSIZE_T_MAX)
4287 : 6948 : return count_nextlong(lz);
4288 : 176171 : 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 : 46332 : repeat_new(PyTypeObject *type, PyObject *args, PyObject *kwds)
4386 : : {
4387 : : repeatobject *ro;
4388 : : PyObject *element;
4389 : 46332 : Py_ssize_t cnt = -1, n_args;
4390 : : static char *kwargs[] = {"object", "times", NULL};
4391 : :
4392 : 46332 : n_args = PyTuple_GET_SIZE(args);
4393 [ + + ]: 46332 : if (kwds != NULL)
4394 : 16 : n_args += PyDict_GET_SIZE(kwds);
4395 [ + + ]: 46332 : if (!PyArg_ParseTupleAndKeywords(args, kwds, "O|n:repeat", kwargs,
4396 : : &element, &cnt))
4397 : 6 : return NULL;
4398 : : /* Does user supply times argument? */
4399 [ + + + + ]: 46326 : if (n_args == 2 && cnt < 0)
4400 : 13 : cnt = 0;
4401 : :
4402 : 46326 : ro = (repeatobject *)type->tp_alloc(type, 0);
4403 [ - + ]: 46326 : if (ro == NULL)
4404 : 0 : return NULL;
4405 : 46326 : Py_INCREF(element);
4406 : 46326 : ro->element = element;
4407 : 46326 : ro->cnt = cnt;
4408 : 46326 : return (PyObject *)ro;
4409 : : }
4410 : :
4411 : : static void
4412 : 46326 : repeat_dealloc(repeatobject *ro)
4413 : : {
4414 : 46326 : PyObject_GC_UnTrack(ro);
4415 : 46326 : Py_XDECREF(ro->element);
4416 : 46326 : Py_TYPE(ro)->tp_free(ro);
4417 : 46326 : }
4418 : :
4419 : : static int
4420 : 3366 : repeat_traverse(repeatobject *ro, visitproc visit, void *arg)
4421 : : {
4422 [ + - - + ]: 3366 : Py_VISIT(ro->element);
4423 : 3366 : return 0;
4424 : : }
4425 : :
4426 : : static PyObject *
4427 : 28330221 : repeat_next(repeatobject *ro)
4428 : : {
4429 [ + + ]: 28330221 : if (ro->cnt == 0)
4430 : 42871 : return NULL;
4431 [ + + ]: 28287350 : if (ro->cnt > 0)
4432 : 28249024 : ro->cnt--;
4433 : 28287350 : Py_INCREF(ro->element);
4434 : 28287350 : 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 : : 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 : 32 : zip_longest_traverse(ziplongestobject *lz, visitproc visit, void *arg)
4623 : : {
4624 [ + - - + ]: 32 : Py_VISIT(lz->ittuple);
4625 [ + - - + ]: 32 : Py_VISIT(lz->result);
4626 [ + - - + ]: 32 : Py_VISIT(lz->fillvalue);
4627 : 32 : return 0;
4628 : : }
4629 : :
4630 : : static PyObject *
4631 : 1094287 : zip_longest_next(ziplongestobject *lz)
4632 : : {
4633 : : Py_ssize_t i;
4634 : 1094287 : Py_ssize_t tuplesize = lz->tuplesize;
4635 : 1094287 : PyObject *result = lz->result;
4636 : : PyObject *it;
4637 : : PyObject *item;
4638 : : PyObject *olditem;
4639 : :
4640 [ + + ]: 1094287 : if (tuplesize == 0)
4641 : 1 : return NULL;
4642 [ - + ]: 1094286 : if (lz->numactive == 0)
4643 : 0 : return NULL;
4644 [ + + ]: 1094286 : if (Py_REFCNT(result) == 1) {
4645 : 549112 : Py_INCREF(result);
4646 [ + + ]: 1620159 : for (i=0 ; i < tuplesize ; i++) {
4647 : 1098209 : it = PyTuple_GET_ITEM(lz->ittuple, i);
4648 [ + + ]: 1098209 : if (it == NULL) {
4649 : 7 : Py_INCREF(lz->fillvalue);
4650 : 7 : item = lz->fillvalue;
4651 : : } else {
4652 : 1098202 : item = PyIter_Next(it);
4653 [ + + ]: 1098202 : 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 : 1071047 : olditem = PyTuple_GET_ITEM(result, i);
4668 : 1071047 : PyTuple_SET_ITEM(result, i, item);
4669 : 1071047 : 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 : 3 : _PyObject_GC_TRACK(result);
4675 : : }
4676 : : } else {
4677 : 545174 : result = PyTuple_New(tuplesize);
4678 [ - + ]: 545174 : if (result == NULL)
4679 : 0 : return NULL;
4680 [ + + ]: 1658722 : for (i=0 ; i < tuplesize ; i++) {
4681 : 1118083 : it = PyTuple_GET_ITEM(lz->ittuple, i);
4682 [ + + ]: 1118083 : if (it == NULL) {
4683 : 33112 : Py_INCREF(lz->fillvalue);
4684 : 33112 : item = lz->fillvalue;
4685 : : } else {
4686 : 1084971 : item = PyIter_Next(it);
4687 [ + + ]: 1084971 : 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 : 1113548 : PyTuple_SET_ITEM(result, i, item);
4702 : : }
4703 : : }
4704 : 1062589 : 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 : 1984 : itertoolsmodule_exec(PyObject *m)
4841 : : {
4842 : 1984 : 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 : 1984 : Py_SET_TYPE(&teedataobject_type, &PyType_Type);
4867 : :
4868 [ + + ]: 43648 : for (size_t i = 0; i < Py_ARRAY_LENGTH(typelist); i++) {
4869 [ - + ]: 41664 : if (PyModule_AddType(m, typelist[i]) < 0) {
4870 : 0 : return -1;
4871 : : }
4872 : : }
4873 : :
4874 : 1984 : 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 : 1984 : PyInit_itertools(void)
4902 : : {
4903 : 1984 : return PyModuleDef_Init(&itertoolsmodule);
4904 : : }
|
