Modules/itertoolsmodule.c

Source:

cpython 3.14 @ ab2d84fe1023/Modules/itertoolsmodule.c ↗

itertools provides composable lazy iterators. All types implement tp_iter (returns self) and tp_iternext (returns next item or NULL on exhaustion).

Map

Lines	Symbol	Role
1-200	count	Infinite counter: count(10, 2) → 10, 12, 14, ...
201-400	cycle	Infinite cycle over a sequence
401-600	repeat	Repeat one value N (or infinite) times
601-900	chain, chain.from_iterable	Concatenate iterables lazily
901-1100	islice	Slice an iterator by start/stop/step
1101-1300	takewhile, dropwhile	Predicate-based prefix/suffix
1301-1500	filterfalse	Complement of filter
1501-1700	starmap	f(*args) for each args in iterable
1701-2000	zip_longest	zip with fillvalue for unequal lengths
2001-2800	product	Cartesian product
2801-3500	permutations	All permutations of r items
3501-4500	combinations, combinations_with_replacement	C(n,r) subsets

Reading

count

// CPython: Modules/itertoolsmodule.c:85 count_next
static PyObject *
count_next(countobject *lz)
{
    PyObject *result = lz->cnt;
    if (lz->long_cnt == NULL && lz->cnt_long == NULL) {
        /* Fast path for small integers */
        if (lz->cnt <= LONG_MAX - lz->step) {
            lz->cnt += lz->step;
            return PyLong_FromSsize_t(result_as_ssize);
        }
    }
    /* Slow path: arbitrary-precision */
    lz->long_cnt = PyNumber_Add(lz->long_cnt, lz->long_step);
    return Py_NewRef(result);
}

cycle

// CPython: Modules/itertoolsmodule.c:265 cycle_next
static PyObject *
cycle_next(cycleobject *lz)
{
    if (!lz->exhausted) {
        /* Still draining the source iterator */
        PyObject *item = PyIter_Next(lz->it);
        if (item != NULL) {
            PyList_Append(lz->saved, item);
            return item;
        }
        lz->exhausted = 1;
        lz->index = 0;
    }
    /* Replay from saved list */
    if (PyList_GET_SIZE(lz->saved) == 0) return NULL;
    PyObject *item = PyList_GET_ITEM(lz->saved, lz->index);
    lz->index = (lz->index + 1) % PyList_GET_SIZE(lz->saved);
    return Py_NewRef(item);
}

cycle buffers the entire input sequence after first pass — memory usage is O(n).

chain

// CPython: Modules/itertoolsmodule.c:660 chain_next
static PyObject *
chain_next(chainobject *lz)
{
    PyObject *item;
    while (lz->source != NULL) {
        item = (*Py_TYPE(lz->source)->tp_iternext)(lz->source);
        if (item != NULL) return item;
        /* Current sub-iterator exhausted: advance to next */
        Py_CLEAR(lz->source);
        lz->source = PyIter_Next(lz->source_iterables);
        if (lz->source == NULL) return NULL;
    }
    return NULL;
}

islice

// CPython: Modules/itertoolsmodule.c:960 islice_next
static PyObject *
islice_next(isliceobject *lz)
{
    /* Skip items up to lz->next */
    while (lz->cnt < lz->next) {
        PyObject *item = PyIter_Next(lz->it);
        if (item == NULL) return NULL;
        Py_DECREF(item);
        lz->cnt++;
    }
    if (lz->stop != -1 && lz->cnt >= lz->stop) return NULL;
    PyObject *item = PyIter_Next(lz->it);
    lz->cnt++;
    lz->next += lz->step;
    return item;
}

product

// CPython: Modules/itertoolsmodule.c:2120 product_next
static PyObject *
product_next(productobject *lz)
{
    /* Build result tuple from current indices */
    PyObject *result = PyTuple_New(lz->npools);
    for (int i = 0; i < lz->npools; i++) {
        PyObject *pool = PyTuple_GET_ITEM(lz->pools, i);
        PyObject *el = PyTuple_GET_ITEM(pool, lz->indices[i]);
        PyTuple_SET_ITEM(result, i, Py_NewRef(el));
    }
    /* Increment indices from right to left (odometer) */
    for (int i = lz->npools - 1; i >= 0; i--) {
        lz->indices[i]++;
        if (lz->indices[i] < PyTuple_GET_SIZE(PyTuple_GET_ITEM(lz->pools, i)))
            break;
        lz->indices[i] = 0;
        if (i == 0) { lz->stopped = 1; break; }
    }
    return result;
}

product('AB', repeat=2) → AA, AB, BA, BB. The odometer pattern increments from the rightmost pool.

combinations

// CPython: Modules/itertoolsmodule.c:3700 combinations_next
static PyObject *
combinations_next(combinationsobject *co)
{
    /* Increment the rightmost index that can still be incremented */
    for (i = co->r - 1; i >= 0; i--) {
        if (co->indices[i] != i + co->n - co->r)
            break;
    }
    if (i < 0) return NULL;  /* exhausted */
    co->indices[i]++;
    for (j = i + 1; j < co->r; j++)
        co->indices[j] = co->indices[j-1] + 1;
    ...
}

gopy notes

All itertools types are in module/itertools/ as Go structs implementing objects.Iterator. cycle stores the buffer as a []PyObject. product uses an integer index array. combinations and permutations use the same increment-from-right odometer pattern as the C.