ยปCore Development>Code coverage>Objects/rangeobject.c

Python code coverage for Objects/rangeobject.c

#countcontent
1n/a/* Range object implementation */
2n/a
3n/a#include "Python.h"
4n/a#include "structmember.h"
5n/a
6n/a/* Support objects whose length is > PY_SSIZE_T_MAX.
7n/a
8n/a This could be sped up for small PyLongs if they fit in a Py_ssize_t.
9n/a This only matters on Win64. Though we could use long long which
10n/a would presumably help perf.
11n/a*/
12n/a
13n/atypedef struct {
14n/a PyObject_HEAD
15n/a PyObject *start;
16n/a PyObject *stop;
17n/a PyObject *step;
18n/a PyObject *length;
19n/a} rangeobject;
20n/a
21n/a/* Helper function for validating step. Always returns a new reference or
22n/a NULL on error.
23n/a*/
24n/astatic PyObject *
25n/avalidate_step(PyObject *step)
26n/a{
27n/a /* No step specified, use a step of 1. */
28n/a if (!step)
29n/a return PyLong_FromLong(1);
30n/a
31n/a step = PyNumber_Index(step);
32n/a if (step && _PyLong_Sign(step) == 0) {
33n/a PyErr_SetString(PyExc_ValueError,
34n/a "range() arg 3 must not be zero");
35n/a Py_CLEAR(step);
36n/a }
37n/a
38n/a return step;
39n/a}
40n/a
41n/astatic PyObject *
42n/acompute_range_length(PyObject *start, PyObject *stop, PyObject *step);
43n/a
44n/astatic rangeobject *
45n/amake_range_object(PyTypeObject *type, PyObject *start,
46n/a PyObject *stop, PyObject *step)
47n/a{
48n/a rangeobject *obj = NULL;
49n/a PyObject *length;
50n/a length = compute_range_length(start, stop, step);
51n/a if (length == NULL) {
52n/a return NULL;
53n/a }
54n/a obj = PyObject_New(rangeobject, type);
55n/a if (obj == NULL) {
56n/a Py_DECREF(length);
57n/a return NULL;
58n/a }
59n/a obj->start = start;
60n/a obj->stop = stop;
61n/a obj->step = step;
62n/a obj->length = length;
63n/a return obj;
64n/a}
65n/a
66n/a/* XXX(nnorwitz): should we error check if the user passes any empty ranges?
67n/a range(-10)
68n/a range(0, -5)
69n/a range(0, 5, -1)
70n/a*/
71n/astatic PyObject *
72n/arange_new(PyTypeObject *type, PyObject *args, PyObject *kw)
73n/a{
74n/a rangeobject *obj;
75n/a PyObject *start = NULL, *stop = NULL, *step = NULL;
76n/a
77n/a if (!_PyArg_NoKeywords("range()", kw))
78n/a return NULL;
79n/a
80n/a if (PyTuple_Size(args) <= 1) {
81n/a if (!PyArg_UnpackTuple(args, "range", 1, 1, &stop))
82n/a return NULL;
83n/a stop = PyNumber_Index(stop);
84n/a if (!stop)
85n/a return NULL;
86n/a start = PyLong_FromLong(0);
87n/a if (!start) {
88n/a Py_DECREF(stop);
89n/a return NULL;
90n/a }
91n/a step = PyLong_FromLong(1);
92n/a if (!step) {
93n/a Py_DECREF(stop);
94n/a Py_DECREF(start);
95n/a return NULL;
96n/a }
97n/a }
98n/a else {
99n/a if (!PyArg_UnpackTuple(args, "range", 2, 3,
100n/a &start, &stop, &step))
101n/a return NULL;
102n/a
103n/a /* Convert borrowed refs to owned refs */
104n/a start = PyNumber_Index(start);
105n/a if (!start)
106n/a return NULL;
107n/a stop = PyNumber_Index(stop);
108n/a if (!stop) {
109n/a Py_DECREF(start);
110n/a return NULL;
111n/a }
112n/a step = validate_step(step); /* Caution, this can clear exceptions */
113n/a if (!step) {
114n/a Py_DECREF(start);
115n/a Py_DECREF(stop);
116n/a return NULL;
117n/a }
118n/a }
119n/a
120n/a obj = make_range_object(type, start, stop, step);
121n/a if (obj != NULL)
122n/a return (PyObject *) obj;
123n/a
124n/a /* Failed to create object, release attributes */
125n/a Py_DECREF(start);
126n/a Py_DECREF(stop);
127n/a Py_DECREF(step);
128n/a return NULL;
129n/a}
130n/a
131n/aPyDoc_STRVAR(range_doc,
132n/a"range(stop) -> range object\n\
133n/arange(start, stop[, step]) -> range object\n\
134n/a\n\
135n/aReturn an object that produces a sequence of integers from start (inclusive)\n\
136n/ato stop (exclusive) by step. range(i, j) produces i, i+1, i+2, ..., j-1.\n\
137n/astart defaults to 0, and stop is omitted! range(4) produces 0, 1, 2, 3.\n\
138n/aThese are exactly the valid indices for a list of 4 elements.\n\
139n/aWhen step is given, it specifies the increment (or decrement).");
140n/a
141n/astatic void
142n/arange_dealloc(rangeobject *r)
143n/a{
144n/a Py_DECREF(r->start);
145n/a Py_DECREF(r->stop);
146n/a Py_DECREF(r->step);
147n/a Py_DECREF(r->length);
148n/a PyObject_Del(r);
149n/a}
150n/a
151n/a/* Return number of items in range (lo, hi, step) as a PyLong object,
152n/a * when arguments are PyLong objects. Arguments MUST return 1 with
153n/a * PyLong_Check(). Return NULL when there is an error.
154n/a */
155n/astatic PyObject*
156n/acompute_range_length(PyObject *start, PyObject *stop, PyObject *step)
157n/a{
158n/a /* -------------------------------------------------------------
159n/a Algorithm is equal to that of get_len_of_range(), but it operates
160n/a on PyObjects (which are assumed to be PyLong objects).
161n/a ---------------------------------------------------------------*/
162n/a int cmp_result;
163n/a PyObject *lo, *hi;
164n/a PyObject *diff = NULL;
165n/a PyObject *one = NULL;
166n/a PyObject *tmp1 = NULL, *tmp2 = NULL, *result;
167n/a /* holds sub-expression evaluations */
168n/a
169n/a PyObject *zero = PyLong_FromLong(0);
170n/a if (zero == NULL)
171n/a return NULL;
172n/a cmp_result = PyObject_RichCompareBool(step, zero, Py_GT);
173n/a Py_DECREF(zero);
174n/a if (cmp_result == -1)
175n/a return NULL;
176n/a
177n/a if (cmp_result == 1) {
178n/a lo = start;
179n/a hi = stop;
180n/a Py_INCREF(step);
181n/a } else {
182n/a lo = stop;
183n/a hi = start;
184n/a step = PyNumber_Negative(step);
185n/a if (!step)
186n/a return NULL;
187n/a }
188n/a
189n/a /* if (lo >= hi), return length of 0. */
190n/a cmp_result = PyObject_RichCompareBool(lo, hi, Py_GE);
191n/a if (cmp_result != 0) {
192n/a Py_DECREF(step);
193n/a if (cmp_result < 0)
194n/a return NULL;
195n/a return PyLong_FromLong(0);
196n/a }
197n/a
198n/a if ((one = PyLong_FromLong(1L)) == NULL)
199n/a goto Fail;
200n/a
201n/a if ((tmp1 = PyNumber_Subtract(hi, lo)) == NULL)
202n/a goto Fail;
203n/a
204n/a if ((diff = PyNumber_Subtract(tmp1, one)) == NULL)
205n/a goto Fail;
206n/a
207n/a if ((tmp2 = PyNumber_FloorDivide(diff, step)) == NULL)
208n/a goto Fail;
209n/a
210n/a if ((result = PyNumber_Add(tmp2, one)) == NULL)
211n/a goto Fail;
212n/a
213n/a Py_DECREF(tmp2);
214n/a Py_DECREF(diff);
215n/a Py_DECREF(step);
216n/a Py_DECREF(tmp1);
217n/a Py_DECREF(one);
218n/a return result;
219n/a
220n/a Fail:
221n/a Py_DECREF(step);
222n/a Py_XDECREF(tmp2);
223n/a Py_XDECREF(diff);
224n/a Py_XDECREF(tmp1);
225n/a Py_XDECREF(one);
226n/a return NULL;
227n/a}
228n/a
229n/astatic Py_ssize_t
230n/arange_length(rangeobject *r)
231n/a{
232n/a return PyLong_AsSsize_t(r->length);
233n/a}
234n/a
235n/astatic PyObject *
236n/acompute_item(rangeobject *r, PyObject *i)
237n/a{
238n/a PyObject *incr, *result;
239n/a /* PyLong equivalent to:
240n/a * return r->start + (i * r->step)
241n/a */
242n/a incr = PyNumber_Multiply(i, r->step);
243n/a if (!incr)
244n/a return NULL;
245n/a result = PyNumber_Add(r->start, incr);
246n/a Py_DECREF(incr);
247n/a return result;
248n/a}
249n/a
250n/astatic PyObject *
251n/acompute_range_item(rangeobject *r, PyObject *arg)
252n/a{
253n/a int cmp_result;
254n/a PyObject *i, *result;
255n/a
256n/a PyObject *zero = PyLong_FromLong(0);
257n/a if (zero == NULL)
258n/a return NULL;
259n/a
260n/a /* PyLong equivalent to:
261n/a * if (arg < 0) {
262n/a * i = r->length + arg
263n/a * } else {
264n/a * i = arg
265n/a * }
266n/a */
267n/a cmp_result = PyObject_RichCompareBool(arg, zero, Py_LT);
268n/a if (cmp_result == -1) {
269n/a Py_DECREF(zero);
270n/a return NULL;
271n/a }
272n/a if (cmp_result == 1) {
273n/a i = PyNumber_Add(r->length, arg);
274n/a if (!i) {
275n/a Py_DECREF(zero);
276n/a return NULL;
277n/a }
278n/a } else {
279n/a i = arg;
280n/a Py_INCREF(i);
281n/a }
282n/a
283n/a /* PyLong equivalent to:
284n/a * if (i < 0 || i >= r->length) {
285n/a * <report index out of bounds>
286n/a * }
287n/a */
288n/a cmp_result = PyObject_RichCompareBool(i, zero, Py_LT);
289n/a Py_DECREF(zero);
290n/a if (cmp_result == 0) {
291n/a cmp_result = PyObject_RichCompareBool(i, r->length, Py_GE);
292n/a }
293n/a if (cmp_result == -1) {
294n/a Py_DECREF(i);
295n/a return NULL;
296n/a }
297n/a if (cmp_result == 1) {
298n/a Py_DECREF(i);
299n/a PyErr_SetString(PyExc_IndexError,
300n/a "range object index out of range");
301n/a return NULL;
302n/a }
303n/a
304n/a result = compute_item(r, i);
305n/a Py_DECREF(i);
306n/a return result;
307n/a}
308n/a
309n/astatic PyObject *
310n/arange_item(rangeobject *r, Py_ssize_t i)
311n/a{
312n/a PyObject *res, *arg = PyLong_FromSsize_t(i);
313n/a if (!arg) {
314n/a return NULL;
315n/a }
316n/a res = compute_range_item(r, arg);
317n/a Py_DECREF(arg);
318n/a return res;
319n/a}
320n/a
321n/astatic PyObject *
322n/acompute_slice(rangeobject *r, PyObject *_slice)
323n/a{
324n/a PySliceObject *slice = (PySliceObject *) _slice;
325n/a rangeobject *result;
326n/a PyObject *start = NULL, *stop = NULL, *step = NULL;
327n/a PyObject *substart = NULL, *substop = NULL, *substep = NULL;
328n/a int error;
329n/a
330n/a error = _PySlice_GetLongIndices(slice, r->length, &start, &stop, &step);
331n/a if (error == -1)
332n/a return NULL;
333n/a
334n/a substep = PyNumber_Multiply(r->step, step);
335n/a if (substep == NULL) goto fail;
336n/a Py_CLEAR(step);
337n/a
338n/a substart = compute_item(r, start);
339n/a if (substart == NULL) goto fail;
340n/a Py_CLEAR(start);
341n/a
342n/a substop = compute_item(r, stop);
343n/a if (substop == NULL) goto fail;
344n/a Py_CLEAR(stop);
345n/a
346n/a result = make_range_object(Py_TYPE(r), substart, substop, substep);
347n/a if (result != NULL) {
348n/a return (PyObject *) result;
349n/a }
350n/afail:
351n/a Py_XDECREF(start);
352n/a Py_XDECREF(stop);
353n/a Py_XDECREF(step);
354n/a Py_XDECREF(substart);
355n/a Py_XDECREF(substop);
356n/a Py_XDECREF(substep);
357n/a return NULL;
358n/a}
359n/a
360n/a/* Assumes (PyLong_CheckExact(ob) || PyBool_Check(ob)) */
361n/astatic int
362n/arange_contains_long(rangeobject *r, PyObject *ob)
363n/a{
364n/a int cmp1, cmp2, cmp3;
365n/a PyObject *tmp1 = NULL;
366n/a PyObject *tmp2 = NULL;
367n/a PyObject *zero = NULL;
368n/a int result = -1;
369n/a
370n/a zero = PyLong_FromLong(0);
371n/a if (zero == NULL) /* MemoryError in int(0) */
372n/a goto end;
373n/a
374n/a /* Check if the value can possibly be in the range. */
375n/a
376n/a cmp1 = PyObject_RichCompareBool(r->step, zero, Py_GT);
377n/a if (cmp1 == -1)
378n/a goto end;
379n/a if (cmp1 == 1) { /* positive steps: start <= ob < stop */
380n/a cmp2 = PyObject_RichCompareBool(r->start, ob, Py_LE);
381n/a cmp3 = PyObject_RichCompareBool(ob, r->stop, Py_LT);
382n/a }
383n/a else { /* negative steps: stop < ob <= start */
384n/a cmp2 = PyObject_RichCompareBool(ob, r->start, Py_LE);
385n/a cmp3 = PyObject_RichCompareBool(r->stop, ob, Py_LT);
386n/a }
387n/a
388n/a if (cmp2 == -1 || cmp3 == -1) /* TypeError */
389n/a goto end;
390n/a if (cmp2 == 0 || cmp3 == 0) { /* ob outside of range */
391n/a result = 0;
392n/a goto end;
393n/a }
394n/a
395n/a /* Check that the stride does not invalidate ob's membership. */
396n/a tmp1 = PyNumber_Subtract(ob, r->start);
397n/a if (tmp1 == NULL)
398n/a goto end;
399n/a tmp2 = PyNumber_Remainder(tmp1, r->step);
400n/a if (tmp2 == NULL)
401n/a goto end;
402n/a /* result = ((int(ob) - start) % step) == 0 */
403n/a result = PyObject_RichCompareBool(tmp2, zero, Py_EQ);
404n/a end:
405n/a Py_XDECREF(tmp1);
406n/a Py_XDECREF(tmp2);
407n/a Py_XDECREF(zero);
408n/a return result;
409n/a}
410n/a
411n/astatic int
412n/arange_contains(rangeobject *r, PyObject *ob)
413n/a{
414n/a if (PyLong_CheckExact(ob) || PyBool_Check(ob))
415n/a return range_contains_long(r, ob);
416n/a
417n/a return (int)_PySequence_IterSearch((PyObject*)r, ob,
418n/a PY_ITERSEARCH_CONTAINS);
419n/a}
420n/a
421n/a/* Compare two range objects. Return 1 for equal, 0 for not equal
422n/a and -1 on error. The algorithm is roughly the C equivalent of
423n/a
424n/a if r0 is r1:
425n/a return True
426n/a if len(r0) != len(r1):
427n/a return False
428n/a if not len(r0):
429n/a return True
430n/a if r0.start != r1.start:
431n/a return False
432n/a if len(r0) == 1:
433n/a return True
434n/a return r0.step == r1.step
435n/a*/
436n/astatic int
437n/arange_equals(rangeobject *r0, rangeobject *r1)
438n/a{
439n/a int cmp_result;
440n/a PyObject *one;
441n/a
442n/a if (r0 == r1)
443n/a return 1;
444n/a cmp_result = PyObject_RichCompareBool(r0->length, r1->length, Py_EQ);
445n/a /* Return False or error to the caller. */
446n/a if (cmp_result != 1)
447n/a return cmp_result;
448n/a cmp_result = PyObject_Not(r0->length);
449n/a /* Return True or error to the caller. */
450n/a if (cmp_result != 0)
451n/a return cmp_result;
452n/a cmp_result = PyObject_RichCompareBool(r0->start, r1->start, Py_EQ);
453n/a /* Return False or error to the caller. */
454n/a if (cmp_result != 1)
455n/a return cmp_result;
456n/a one = PyLong_FromLong(1);
457n/a if (!one)
458n/a return -1;
459n/a cmp_result = PyObject_RichCompareBool(r0->length, one, Py_EQ);
460n/a Py_DECREF(one);
461n/a /* Return True or error to the caller. */
462n/a if (cmp_result != 0)
463n/a return cmp_result;
464n/a return PyObject_RichCompareBool(r0->step, r1->step, Py_EQ);
465n/a}
466n/a
467n/astatic PyObject *
468n/arange_richcompare(PyObject *self, PyObject *other, int op)
469n/a{
470n/a int result;
471n/a
472n/a if (!PyRange_Check(other))
473n/a Py_RETURN_NOTIMPLEMENTED;
474n/a switch (op) {
475n/a case Py_NE:
476n/a case Py_EQ:
477n/a result = range_equals((rangeobject*)self, (rangeobject*)other);
478n/a if (result == -1)
479n/a return NULL;
480n/a if (op == Py_NE)
481n/a result = !result;
482n/a if (result)
483n/a Py_RETURN_TRUE;
484n/a else
485n/a Py_RETURN_FALSE;
486n/a case Py_LE:
487n/a case Py_GE:
488n/a case Py_LT:
489n/a case Py_GT:
490n/a Py_RETURN_NOTIMPLEMENTED;
491n/a default:
492n/a PyErr_BadArgument();
493n/a return NULL;
494n/a }
495n/a}
496n/a
497n/a/* Hash function for range objects. Rough C equivalent of
498n/a
499n/a if not len(r):
500n/a return hash((len(r), None, None))
501n/a if len(r) == 1:
502n/a return hash((len(r), r.start, None))
503n/a return hash((len(r), r.start, r.step))
504n/a*/
505n/astatic Py_hash_t
506n/arange_hash(rangeobject *r)
507n/a{
508n/a PyObject *t;
509n/a Py_hash_t result = -1;
510n/a int cmp_result;
511n/a
512n/a t = PyTuple_New(3);
513n/a if (!t)
514n/a return -1;
515n/a Py_INCREF(r->length);
516n/a PyTuple_SET_ITEM(t, 0, r->length);
517n/a cmp_result = PyObject_Not(r->length);
518n/a if (cmp_result == -1)
519n/a goto end;
520n/a if (cmp_result == 1) {
521n/a Py_INCREF(Py_None);
522n/a Py_INCREF(Py_None);
523n/a PyTuple_SET_ITEM(t, 1, Py_None);
524n/a PyTuple_SET_ITEM(t, 2, Py_None);
525n/a }
526n/a else {
527n/a PyObject *one;
528n/a Py_INCREF(r->start);
529n/a PyTuple_SET_ITEM(t, 1, r->start);
530n/a one = PyLong_FromLong(1);
531n/a if (!one)
532n/a goto end;
533n/a cmp_result = PyObject_RichCompareBool(r->length, one, Py_EQ);
534n/a Py_DECREF(one);
535n/a if (cmp_result == -1)
536n/a goto end;
537n/a if (cmp_result == 1) {
538n/a Py_INCREF(Py_None);
539n/a PyTuple_SET_ITEM(t, 2, Py_None);
540n/a }
541n/a else {
542n/a Py_INCREF(r->step);
543n/a PyTuple_SET_ITEM(t, 2, r->step);
544n/a }
545n/a }
546n/a result = PyObject_Hash(t);
547n/a end:
548n/a Py_DECREF(t);
549n/a return result;
550n/a}
551n/a
552n/astatic PyObject *
553n/arange_count(rangeobject *r, PyObject *ob)
554n/a{
555n/a if (PyLong_CheckExact(ob) || PyBool_Check(ob)) {
556n/a int result = range_contains_long(r, ob);
557n/a if (result == -1)
558n/a return NULL;
559n/a else if (result)
560n/a return PyLong_FromLong(1);
561n/a else
562n/a return PyLong_FromLong(0);
563n/a } else {
564n/a Py_ssize_t count;
565n/a count = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_COUNT);
566n/a if (count == -1)
567n/a return NULL;
568n/a return PyLong_FromSsize_t(count);
569n/a }
570n/a}
571n/a
572n/astatic PyObject *
573n/arange_index(rangeobject *r, PyObject *ob)
574n/a{
575n/a int contains;
576n/a
577n/a if (!PyLong_CheckExact(ob) && !PyBool_Check(ob)) {
578n/a Py_ssize_t index;
579n/a index = _PySequence_IterSearch((PyObject*)r, ob, PY_ITERSEARCH_INDEX);
580n/a if (index == -1)
581n/a return NULL;
582n/a return PyLong_FromSsize_t(index);
583n/a }
584n/a
585n/a contains = range_contains_long(r, ob);
586n/a if (contains == -1)
587n/a return NULL;
588n/a
589n/a if (contains) {
590n/a PyObject *idx, *tmp = PyNumber_Subtract(ob, r->start);
591n/a if (tmp == NULL)
592n/a return NULL;
593n/a /* idx = (ob - r.start) // r.step */
594n/a idx = PyNumber_FloorDivide(tmp, r->step);
595n/a Py_DECREF(tmp);
596n/a return idx;
597n/a }
598n/a
599n/a /* object is not in the range */
600n/a PyErr_Format(PyExc_ValueError, "%R is not in range", ob);
601n/a return NULL;
602n/a}
603n/a
604n/astatic PySequenceMethods range_as_sequence = {
605n/a (lenfunc)range_length, /* sq_length */
606n/a 0, /* sq_concat */
607n/a 0, /* sq_repeat */
608n/a (ssizeargfunc)range_item, /* sq_item */
609n/a 0, /* sq_slice */
610n/a 0, /* sq_ass_item */
611n/a 0, /* sq_ass_slice */
612n/a (objobjproc)range_contains, /* sq_contains */
613n/a};
614n/a
615n/astatic PyObject *
616n/arange_repr(rangeobject *r)
617n/a{
618n/a Py_ssize_t istep;
619n/a
620n/a /* Check for special case values for printing. We don't always
621n/a need the step value. We don't care about errors
622n/a (it means overflow), so clear the errors. */
623n/a istep = PyNumber_AsSsize_t(r->step, NULL);
624n/a if (istep != 1 || (istep == -1 && PyErr_Occurred())) {
625n/a PyErr_Clear();
626n/a }
627n/a
628n/a if (istep == 1)
629n/a return PyUnicode_FromFormat("range(%R, %R)", r->start, r->stop);
630n/a else
631n/a return PyUnicode_FromFormat("range(%R, %R, %R)",
632n/a r->start, r->stop, r->step);
633n/a}
634n/a
635n/a/* Pickling support */
636n/astatic PyObject *
637n/arange_reduce(rangeobject *r, PyObject *args)
638n/a{
639n/a return Py_BuildValue("(O(OOO))", Py_TYPE(r),
640n/a r->start, r->stop, r->step);
641n/a}
642n/a
643n/astatic PyObject *
644n/arange_subscript(rangeobject* self, PyObject* item)
645n/a{
646n/a if (PyIndex_Check(item)) {
647n/a PyObject *i, *result;
648n/a i = PyNumber_Index(item);
649n/a if (!i)
650n/a return NULL;
651n/a result = compute_range_item(self, i);
652n/a Py_DECREF(i);
653n/a return result;
654n/a }
655n/a if (PySlice_Check(item)) {
656n/a return compute_slice(self, item);
657n/a }
658n/a PyErr_Format(PyExc_TypeError,
659n/a "range indices must be integers or slices, not %.200s",
660n/a item->ob_type->tp_name);
661n/a return NULL;
662n/a}
663n/a
664n/a
665n/astatic PyMappingMethods range_as_mapping = {
666n/a (lenfunc)range_length, /* mp_length */
667n/a (binaryfunc)range_subscript, /* mp_subscript */
668n/a (objobjargproc)0, /* mp_ass_subscript */
669n/a};
670n/a
671n/astatic PyObject * range_iter(PyObject *seq);
672n/astatic PyObject * range_reverse(PyObject *seq);
673n/a
674n/aPyDoc_STRVAR(reverse_doc,
675n/a"Return a reverse iterator.");
676n/a
677n/aPyDoc_STRVAR(count_doc,
678n/a"rangeobject.count(value) -> integer -- return number of occurrences of value");
679n/a
680n/aPyDoc_STRVAR(index_doc,
681n/a"rangeobject.index(value, [start, [stop]]) -> integer -- return index of value.\n"
682n/a"Raise ValueError if the value is not present.");
683n/a
684n/astatic PyMethodDef range_methods[] = {
685n/a {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc},
686n/a {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS},
687n/a {"count", (PyCFunction)range_count, METH_O, count_doc},
688n/a {"index", (PyCFunction)range_index, METH_O, index_doc},
689n/a {NULL, NULL} /* sentinel */
690n/a};
691n/a
692n/astatic PyMemberDef range_members[] = {
693n/a {"start", T_OBJECT_EX, offsetof(rangeobject, start), READONLY},
694n/a {"stop", T_OBJECT_EX, offsetof(rangeobject, stop), READONLY},
695n/a {"step", T_OBJECT_EX, offsetof(rangeobject, step), READONLY},
696n/a {0}
697n/a};
698n/a
699n/aPyTypeObject PyRange_Type = {
700n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
701n/a "range", /* Name of this type */
702n/a sizeof(rangeobject), /* Basic object size */
703n/a 0, /* Item size for varobject */
704n/a (destructor)range_dealloc, /* tp_dealloc */
705n/a 0, /* tp_print */
706n/a 0, /* tp_getattr */
707n/a 0, /* tp_setattr */
708n/a 0, /* tp_reserved */
709n/a (reprfunc)range_repr, /* tp_repr */
710n/a 0, /* tp_as_number */
711n/a &range_as_sequence, /* tp_as_sequence */
712n/a &range_as_mapping, /* tp_as_mapping */
713n/a (hashfunc)range_hash, /* tp_hash */
714n/a 0, /* tp_call */
715n/a 0, /* tp_str */
716n/a PyObject_GenericGetAttr, /* tp_getattro */
717n/a 0, /* tp_setattro */
718n/a 0, /* tp_as_buffer */
719n/a Py_TPFLAGS_DEFAULT, /* tp_flags */
720n/a range_doc, /* tp_doc */
721n/a 0, /* tp_traverse */
722n/a 0, /* tp_clear */
723n/a range_richcompare, /* tp_richcompare */
724n/a 0, /* tp_weaklistoffset */
725n/a range_iter, /* tp_iter */
726n/a 0, /* tp_iternext */
727n/a range_methods, /* tp_methods */
728n/a range_members, /* tp_members */
729n/a 0, /* tp_getset */
730n/a 0, /* tp_base */
731n/a 0, /* tp_dict */
732n/a 0, /* tp_descr_get */
733n/a 0, /* tp_descr_set */
734n/a 0, /* tp_dictoffset */
735n/a 0, /* tp_init */
736n/a 0, /* tp_alloc */
737n/a range_new, /* tp_new */
738n/a};
739n/a
740n/a/*********************** range Iterator **************************/
741n/a
742n/a/* There are 2 types of iterators, one for C longs, the other for
743n/a Python ints (ie, PyObjects). This should make iteration fast
744n/a in the normal case, but possible for any numeric value.
745n/a*/
746n/a
747n/atypedef struct {
748n/a PyObject_HEAD
749n/a long index;
750n/a long start;
751n/a long step;
752n/a long len;
753n/a} rangeiterobject;
754n/a
755n/astatic PyObject *
756n/arangeiter_next(rangeiterobject *r)
757n/a{
758n/a if (r->index < r->len)
759n/a /* cast to unsigned to avoid possible signed overflow
760n/a in intermediate calculations. */
761n/a return PyLong_FromLong((long)(r->start +
762n/a (unsigned long)(r->index++) * r->step));
763n/a return NULL;
764n/a}
765n/a
766n/astatic PyObject *
767n/arangeiter_len(rangeiterobject *r)
768n/a{
769n/a return PyLong_FromLong(r->len - r->index);
770n/a}
771n/a
772n/aPyDoc_STRVAR(length_hint_doc,
773n/a "Private method returning an estimate of len(list(it)).");
774n/a
775n/astatic PyObject *
776n/arangeiter_reduce(rangeiterobject *r)
777n/a{
778n/a PyObject *start=NULL, *stop=NULL, *step=NULL;
779n/a PyObject *range;
780n/a
781n/a /* create a range object for pickling */
782n/a start = PyLong_FromLong(r->start);
783n/a if (start == NULL)
784n/a goto err;
785n/a stop = PyLong_FromLong(r->start + r->len * r->step);
786n/a if (stop == NULL)
787n/a goto err;
788n/a step = PyLong_FromLong(r->step);
789n/a if (step == NULL)
790n/a goto err;
791n/a range = (PyObject*)make_range_object(&PyRange_Type,
792n/a start, stop, step);
793n/a if (range == NULL)
794n/a goto err;
795n/a /* return the result */
796n/a return Py_BuildValue("N(N)i", _PyObject_GetBuiltin("iter"), range, r->index);
797n/aerr:
798n/a Py_XDECREF(start);
799n/a Py_XDECREF(stop);
800n/a Py_XDECREF(step);
801n/a return NULL;
802n/a}
803n/a
804n/astatic PyObject *
805n/arangeiter_setstate(rangeiterobject *r, PyObject *state)
806n/a{
807n/a long index = PyLong_AsLong(state);
808n/a if (index == -1 && PyErr_Occurred())
809n/a return NULL;
810n/a /* silently clip the index value */
811n/a if (index < 0)
812n/a index = 0;
813n/a else if (index > r->len)
814n/a index = r->len; /* exhausted iterator */
815n/a r->index = index;
816n/a Py_RETURN_NONE;
817n/a}
818n/a
819n/aPyDoc_STRVAR(reduce_doc, "Return state information for pickling.");
820n/aPyDoc_STRVAR(setstate_doc, "Set state information for unpickling.");
821n/a
822n/astatic PyMethodDef rangeiter_methods[] = {
823n/a {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS,
824n/a length_hint_doc},
825n/a {"__reduce__", (PyCFunction)rangeiter_reduce, METH_NOARGS,
826n/a reduce_doc},
827n/a {"__setstate__", (PyCFunction)rangeiter_setstate, METH_O,
828n/a setstate_doc},
829n/a {NULL, NULL} /* sentinel */
830n/a};
831n/a
832n/aPyTypeObject PyRangeIter_Type = {
833n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
834n/a "range_iterator", /* tp_name */
835n/a sizeof(rangeiterobject), /* tp_basicsize */
836n/a 0, /* tp_itemsize */
837n/a /* methods */
838n/a (destructor)PyObject_Del, /* tp_dealloc */
839n/a 0, /* tp_print */
840n/a 0, /* tp_getattr */
841n/a 0, /* tp_setattr */
842n/a 0, /* tp_reserved */
843n/a 0, /* tp_repr */
844n/a 0, /* tp_as_number */
845n/a 0, /* tp_as_sequence */
846n/a 0, /* tp_as_mapping */
847n/a 0, /* tp_hash */
848n/a 0, /* tp_call */
849n/a 0, /* tp_str */
850n/a PyObject_GenericGetAttr, /* tp_getattro */
851n/a 0, /* tp_setattro */
852n/a 0, /* tp_as_buffer */
853n/a Py_TPFLAGS_DEFAULT, /* tp_flags */
854n/a 0, /* tp_doc */
855n/a 0, /* tp_traverse */
856n/a 0, /* tp_clear */
857n/a 0, /* tp_richcompare */
858n/a 0, /* tp_weaklistoffset */
859n/a PyObject_SelfIter, /* tp_iter */
860n/a (iternextfunc)rangeiter_next, /* tp_iternext */
861n/a rangeiter_methods, /* tp_methods */
862n/a 0, /* tp_members */
863n/a};
864n/a
865n/a/* Return number of items in range (lo, hi, step). step != 0
866n/a * required. The result always fits in an unsigned long.
867n/a */
868n/astatic unsigned long
869n/aget_len_of_range(long lo, long hi, long step)
870n/a{
871n/a /* -------------------------------------------------------------
872n/a If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
873n/a Else for step > 0, if n values are in the range, the last one is
874n/a lo + (n-1)*step, which must be <= hi-1. Rearranging,
875n/a n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
876n/a the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so
877n/a the RHS is non-negative and so truncation is the same as the
878n/a floor. Letting M be the largest positive long, the worst case
879n/a for the RHS numerator is hi=M, lo=-M-1, and then
880n/a hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough
881n/a precision to compute the RHS exactly. The analysis for step < 0
882n/a is similar.
883n/a ---------------------------------------------------------------*/
884n/a assert(step != 0);
885n/a if (step > 0 && lo < hi)
886n/a return 1UL + (hi - 1UL - lo) / step;
887n/a else if (step < 0 && lo > hi)
888n/a return 1UL + (lo - 1UL - hi) / (0UL - step);
889n/a else
890n/a return 0UL;
891n/a}
892n/a
893n/a/* Initialize a rangeiter object. If the length of the rangeiter object
894n/a is not representable as a C long, OverflowError is raised. */
895n/a
896n/astatic PyObject *
897n/afast_range_iter(long start, long stop, long step)
898n/a{
899n/a rangeiterobject *it = PyObject_New(rangeiterobject, &PyRangeIter_Type);
900n/a unsigned long ulen;
901n/a if (it == NULL)
902n/a return NULL;
903n/a it->start = start;
904n/a it->step = step;
905n/a ulen = get_len_of_range(start, stop, step);
906n/a if (ulen > (unsigned long)LONG_MAX) {
907n/a Py_DECREF(it);
908n/a PyErr_SetString(PyExc_OverflowError,
909n/a "range too large to represent as a range_iterator");
910n/a return NULL;
911n/a }
912n/a it->len = (long)ulen;
913n/a it->index = 0;
914n/a return (PyObject *)it;
915n/a}
916n/a
917n/atypedef struct {
918n/a PyObject_HEAD
919n/a PyObject *index;
920n/a PyObject *start;
921n/a PyObject *step;
922n/a PyObject *len;
923n/a} longrangeiterobject;
924n/a
925n/astatic PyObject *
926n/alongrangeiter_len(longrangeiterobject *r, PyObject *no_args)
927n/a{
928n/a return PyNumber_Subtract(r->len, r->index);
929n/a}
930n/a
931n/astatic PyObject *
932n/alongrangeiter_reduce(longrangeiterobject *r)
933n/a{
934n/a PyObject *product, *stop=NULL;
935n/a PyObject *range;
936n/a
937n/a /* create a range object for pickling. Must calculate the "stop" value */
938n/a product = PyNumber_Multiply(r->len, r->step);
939n/a if (product == NULL)
940n/a return NULL;
941n/a stop = PyNumber_Add(r->start, product);
942n/a Py_DECREF(product);
943n/a if (stop == NULL)
944n/a return NULL;
945n/a Py_INCREF(r->start);
946n/a Py_INCREF(r->step);
947n/a range = (PyObject*)make_range_object(&PyRange_Type,
948n/a r->start, stop, r->step);
949n/a if (range == NULL) {
950n/a Py_DECREF(r->start);
951n/a Py_DECREF(stop);
952n/a Py_DECREF(r->step);
953n/a return NULL;
954n/a }
955n/a
956n/a /* return the result */
957n/a return Py_BuildValue("N(N)O", _PyObject_GetBuiltin("iter"), range, r->index);
958n/a}
959n/a
960n/astatic PyObject *
961n/alongrangeiter_setstate(longrangeiterobject *r, PyObject *state)
962n/a{
963n/a int cmp;
964n/a
965n/a /* clip the value */
966n/a PyObject *zero = PyLong_FromLong(0);
967n/a if (zero == NULL)
968n/a return NULL;
969n/a cmp = PyObject_RichCompareBool(state, zero, Py_LT);
970n/a if (cmp > 0) {
971n/a Py_XSETREF(r->index, zero);
972n/a Py_RETURN_NONE;
973n/a }
974n/a Py_DECREF(zero);
975n/a if (cmp < 0)
976n/a return NULL;
977n/a
978n/a cmp = PyObject_RichCompareBool(r->len, state, Py_LT);
979n/a if (cmp < 0)
980n/a return NULL;
981n/a if (cmp > 0)
982n/a state = r->len;
983n/a
984n/a Py_INCREF(state);
985n/a Py_XSETREF(r->index, state);
986n/a Py_RETURN_NONE;
987n/a}
988n/a
989n/astatic PyMethodDef longrangeiter_methods[] = {
990n/a {"__length_hint__", (PyCFunction)longrangeiter_len, METH_NOARGS,
991n/a length_hint_doc},
992n/a {"__reduce__", (PyCFunction)longrangeiter_reduce, METH_NOARGS,
993n/a reduce_doc},
994n/a {"__setstate__", (PyCFunction)longrangeiter_setstate, METH_O,
995n/a setstate_doc},
996n/a {NULL, NULL} /* sentinel */
997n/a};
998n/a
999n/astatic void
1000n/alongrangeiter_dealloc(longrangeiterobject *r)
1001n/a{
1002n/a Py_XDECREF(r->index);
1003n/a Py_XDECREF(r->start);
1004n/a Py_XDECREF(r->step);
1005n/a Py_XDECREF(r->len);
1006n/a PyObject_Del(r);
1007n/a}
1008n/a
1009n/astatic PyObject *
1010n/alongrangeiter_next(longrangeiterobject *r)
1011n/a{
1012n/a PyObject *one, *product, *new_index, *result;
1013n/a if (PyObject_RichCompareBool(r->index, r->len, Py_LT) != 1)
1014n/a return NULL;
1015n/a
1016n/a one = PyLong_FromLong(1);
1017n/a if (!one)
1018n/a return NULL;
1019n/a
1020n/a new_index = PyNumber_Add(r->index, one);
1021n/a Py_DECREF(one);
1022n/a if (!new_index)
1023n/a return NULL;
1024n/a
1025n/a product = PyNumber_Multiply(r->index, r->step);
1026n/a if (!product) {
1027n/a Py_DECREF(new_index);
1028n/a return NULL;
1029n/a }
1030n/a
1031n/a result = PyNumber_Add(r->start, product);
1032n/a Py_DECREF(product);
1033n/a if (result) {
1034n/a Py_SETREF(r->index, new_index);
1035n/a }
1036n/a else {
1037n/a Py_DECREF(new_index);
1038n/a }
1039n/a
1040n/a return result;
1041n/a}
1042n/a
1043n/aPyTypeObject PyLongRangeIter_Type = {
1044n/a PyVarObject_HEAD_INIT(&PyType_Type, 0)
1045n/a "longrange_iterator", /* tp_name */
1046n/a sizeof(longrangeiterobject), /* tp_basicsize */
1047n/a 0, /* tp_itemsize */
1048n/a /* methods */
1049n/a (destructor)longrangeiter_dealloc, /* tp_dealloc */
1050n/a 0, /* tp_print */
1051n/a 0, /* tp_getattr */
1052n/a 0, /* tp_setattr */
1053n/a 0, /* tp_reserved */
1054n/a 0, /* tp_repr */
1055n/a 0, /* tp_as_number */
1056n/a 0, /* tp_as_sequence */
1057n/a 0, /* tp_as_mapping */
1058n/a 0, /* tp_hash */
1059n/a 0, /* tp_call */
1060n/a 0, /* tp_str */
1061n/a PyObject_GenericGetAttr, /* tp_getattro */
1062n/a 0, /* tp_setattro */
1063n/a 0, /* tp_as_buffer */
1064n/a Py_TPFLAGS_DEFAULT, /* tp_flags */
1065n/a 0, /* tp_doc */
1066n/a 0, /* tp_traverse */
1067n/a 0, /* tp_clear */
1068n/a 0, /* tp_richcompare */
1069n/a 0, /* tp_weaklistoffset */
1070n/a PyObject_SelfIter, /* tp_iter */
1071n/a (iternextfunc)longrangeiter_next, /* tp_iternext */
1072n/a longrangeiter_methods, /* tp_methods */
1073n/a 0,
1074n/a};
1075n/a
1076n/astatic PyObject *
1077n/arange_iter(PyObject *seq)
1078n/a{
1079n/a rangeobject *r = (rangeobject *)seq;
1080n/a longrangeiterobject *it;
1081n/a long lstart, lstop, lstep;
1082n/a PyObject *int_it;
1083n/a
1084n/a assert(PyRange_Check(seq));
1085n/a
1086n/a /* If all three fields and the length convert to long, use the int
1087n/a * version */
1088n/a lstart = PyLong_AsLong(r->start);
1089n/a if (lstart == -1 && PyErr_Occurred()) {
1090n/a PyErr_Clear();
1091n/a goto long_range;
1092n/a }
1093n/a lstop = PyLong_AsLong(r->stop);
1094n/a if (lstop == -1 && PyErr_Occurred()) {
1095n/a PyErr_Clear();
1096n/a goto long_range;
1097n/a }
1098n/a lstep = PyLong_AsLong(r->step);
1099n/a if (lstep == -1 && PyErr_Occurred()) {
1100n/a PyErr_Clear();
1101n/a goto long_range;
1102n/a }
1103n/a int_it = fast_range_iter(lstart, lstop, lstep);
1104n/a if (int_it == NULL && PyErr_ExceptionMatches(PyExc_OverflowError)) {
1105n/a PyErr_Clear();
1106n/a goto long_range;
1107n/a }
1108n/a return (PyObject *)int_it;
1109n/a
1110n/a long_range:
1111n/a it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
1112n/a if (it == NULL)
1113n/a return NULL;
1114n/a
1115n/a /* Do all initialization here, so we can DECREF on failure. */
1116n/a it->start = r->start;
1117n/a it->step = r->step;
1118n/a it->len = r->length;
1119n/a Py_INCREF(it->start);
1120n/a Py_INCREF(it->step);
1121n/a Py_INCREF(it->len);
1122n/a
1123n/a it->index = PyLong_FromLong(0);
1124n/a if (!it->index)
1125n/a goto create_failure;
1126n/a
1127n/a return (PyObject *)it;
1128n/a
1129n/acreate_failure:
1130n/a Py_DECREF(it);
1131n/a return NULL;
1132n/a}
1133n/a
1134n/astatic PyObject *
1135n/arange_reverse(PyObject *seq)
1136n/a{
1137n/a rangeobject *range = (rangeobject*) seq;
1138n/a longrangeiterobject *it;
1139n/a PyObject *one, *sum, *diff, *product;
1140n/a long lstart, lstop, lstep, new_start, new_stop;
1141n/a unsigned long ulen;
1142n/a
1143n/a assert(PyRange_Check(seq));
1144n/a
1145n/a /* reversed(range(start, stop, step)) can be expressed as
1146n/a range(start+(n-1)*step, start-step, -step), where n is the number of
1147n/a integers in the range.
1148n/a
1149n/a If each of start, stop, step, -step, start-step, and the length
1150n/a of the iterator is representable as a C long, use the int
1151n/a version. This excludes some cases where the reversed range is
1152n/a representable as a range_iterator, but it's good enough for
1153n/a common cases and it makes the checks simple. */
1154n/a
1155n/a lstart = PyLong_AsLong(range->start);
1156n/a if (lstart == -1 && PyErr_Occurred()) {
1157n/a PyErr_Clear();
1158n/a goto long_range;
1159n/a }
1160n/a lstop = PyLong_AsLong(range->stop);
1161n/a if (lstop == -1 && PyErr_Occurred()) {
1162n/a PyErr_Clear();
1163n/a goto long_range;
1164n/a }
1165n/a lstep = PyLong_AsLong(range->step);
1166n/a if (lstep == -1 && PyErr_Occurred()) {
1167n/a PyErr_Clear();
1168n/a goto long_range;
1169n/a }
1170n/a /* check for possible overflow of -lstep */
1171n/a if (lstep == LONG_MIN)
1172n/a goto long_range;
1173n/a
1174n/a /* check for overflow of lstart - lstep:
1175n/a
1176n/a for lstep > 0, need only check whether lstart - lstep < LONG_MIN.
1177n/a for lstep < 0, need only check whether lstart - lstep > LONG_MAX
1178n/a
1179n/a Rearrange these inequalities as:
1180n/a
1181n/a lstart - LONG_MIN < lstep (lstep > 0)
1182n/a LONG_MAX - lstart < -lstep (lstep < 0)
1183n/a
1184n/a and compute both sides as unsigned longs, to avoid the
1185n/a possibility of undefined behaviour due to signed overflow. */
1186n/a
1187n/a if (lstep > 0) {
1188n/a if ((unsigned long)lstart - LONG_MIN < (unsigned long)lstep)
1189n/a goto long_range;
1190n/a }
1191n/a else {
1192n/a if (LONG_MAX - (unsigned long)lstart < 0UL - lstep)
1193n/a goto long_range;
1194n/a }
1195n/a
1196n/a ulen = get_len_of_range(lstart, lstop, lstep);
1197n/a if (ulen > (unsigned long)LONG_MAX)
1198n/a goto long_range;
1199n/a
1200n/a new_stop = lstart - lstep;
1201n/a new_start = (long)(new_stop + ulen * lstep);
1202n/a return fast_range_iter(new_start, new_stop, -lstep);
1203n/a
1204n/along_range:
1205n/a it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
1206n/a if (it == NULL)
1207n/a return NULL;
1208n/a
1209n/a /* start + (len - 1) * step */
1210n/a it->len = range->length;
1211n/a Py_INCREF(it->len);
1212n/a
1213n/a one = PyLong_FromLong(1);
1214n/a if (!one)
1215n/a goto create_failure;
1216n/a
1217n/a diff = PyNumber_Subtract(it->len, one);
1218n/a Py_DECREF(one);
1219n/a if (!diff)
1220n/a goto create_failure;
1221n/a
1222n/a product = PyNumber_Multiply(diff, range->step);
1223n/a Py_DECREF(diff);
1224n/a if (!product)
1225n/a goto create_failure;
1226n/a
1227n/a sum = PyNumber_Add(range->start, product);
1228n/a Py_DECREF(product);
1229n/a it->start = sum;
1230n/a if (!it->start)
1231n/a goto create_failure;
1232n/a
1233n/a it->step = PyNumber_Negative(range->step);
1234n/a if (!it->step)
1235n/a goto create_failure;
1236n/a
1237n/a it->index = PyLong_FromLong(0);
1238n/a if (!it->index)
1239n/a goto create_failure;
1240n/a
1241n/a return (PyObject *)it;
1242n/a
1243n/acreate_failure:
1244n/a Py_DECREF(it);
1245n/a return NULL;
1246n/a}