LCOV - code coverage report
 Current view: top level - Objects - rangeobject.c (source / functions) Hit Total Coverage Test: CPython lcov report Lines: 32 85 37.6 % Date: 2017-04-19 Functions: 5 11 45.5 %
 ` Line data Source code` ``` 1 : /* Range object implementation */ 2 : 3 : #include "Python.h" 4 : 5 : typedef struct { 6 : PyObject_HEAD 7 : long start; 8 : long step; 9 : long len; 10 : } rangeobject; 11 : 12 : /* Return number of items in range (lo, hi, step). step != 0 13 : * required. The result always fits in an unsigned long. 14 : */ 15 : static unsigned long 16 663 : get_len_of_range(long lo, long hi, long step) 17 : { 18 : /* ------------------------------------------------------------- 19 : If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty. 20 : Else for step > 0, if n values are in the range, the last one is 21 : lo + (n-1)*step, which must be <= hi-1. Rearranging, 22 : n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives 23 : the proper value. Since lo < hi in this case, hi-lo-1 >= 0, so 24 : the RHS is non-negative and so truncation is the same as the 25 : floor. Letting M be the largest positive long, the worst case 26 : for the RHS numerator is hi=M, lo=-M-1, and then 27 : hi-lo-1 = M-(-M-1)-1 = 2*M. Therefore unsigned long has enough 28 : precision to compute the RHS exactly. The analysis for step < 0 29 : is similar. 30 : ---------------------------------------------------------------*/ 31 : assert(step != 0); 32 663 : if (step > 0 && lo < hi) 33 663 : return 1UL + (hi - 1UL - lo) / step; 34 0 : else if (step < 0 && lo > hi) 35 0 : return 1UL + (lo - 1UL - hi) / (0UL - step); 36 : else 37 0 : return 0UL; 38 : } 39 : 40 : /* Return a stop value suitable for reconstructing the xrange from 41 : * a (start, stop, step) triple. Used in range_repr and range_reduce. 42 : * Computes start + len * step, clipped to the range [LONG_MIN, LONG_MAX]. 43 : */ 44 : static long 45 0 : get_stop_for_range(rangeobject *r) 46 : { 47 : long last; 48 : 49 0 : if (r->len == 0) 50 0 : return r->start; 51 : 52 : /* The tricky bit is avoiding overflow. We first compute the last entry in 53 : the xrange, start + (len - 1) * step, which is guaranteed to lie within 54 : the range of a long, and then add step to it. See the range_reverse 55 : comments for an explanation of the casts below. 56 : */ 57 0 : last = (long)(r->start + (unsigned long)(r->len - 1) * r->step); 58 0 : if (r->step > 0) 59 0 : return last > LONG_MAX - r->step ? LONG_MAX : last + r->step; 60 : else 61 0 : return last < LONG_MIN - r->step ? LONG_MIN : last + r->step; 62 : } 63 : 64 : static PyObject * 65 663 : range_new(PyTypeObject *type, PyObject *args, PyObject *kw) 66 : { 67 : rangeobject *obj; 68 663 : long ilow = 0, ihigh = 0, istep = 1; 69 : unsigned long n; 70 : 71 663 : if (!_PyArg_NoKeywords("xrange()", kw)) 72 0 : return NULL; 73 : 74 663 : if (PyTuple_Size(args) <= 1) { 75 663 : if (!PyArg_ParseTuple(args, 76 : "l;xrange() requires 1-3 int arguments", 77 : &ihigh)) 78 0 : return NULL; 79 : } 80 : else { 81 0 : if (!PyArg_ParseTuple(args, 82 : "ll|l;xrange() requires 1-3 int arguments", 83 : &ilow, &ihigh, &istep)) 84 0 : return NULL; 85 : } 86 663 : if (istep == 0) { 87 0 : PyErr_SetString(PyExc_ValueError, "xrange() arg 3 must not be zero"); 88 0 : return NULL; 89 : } 90 663 : n = get_len_of_range(ilow, ihigh, istep); 91 663 : if (n > (unsigned long)LONG_MAX || (long)n > PY_SSIZE_T_MAX) { 92 0 : PyErr_SetString(PyExc_OverflowError, 93 : "xrange() result has too many items"); 94 0 : return NULL; 95 : } 96 : 97 663 : obj = PyObject_New(rangeobject, &PyRange_Type); 98 663 : if (obj == NULL) 99 0 : return NULL; 100 663 : obj->start = ilow; 101 663 : obj->len = (long)n; 102 663 : obj->step = istep; 103 663 : return (PyObject *) obj; 104 : } 105 : 106 : PyDoc_STRVAR(range_doc, 107 : "xrange(stop) -> xrange object\n\ 108 : xrange(start, stop[, step]) -> xrange object\n\ 109 : \n\ 110 : Like range(), but instead of returning a list, returns an object that\n\ 111 : generates the numbers in the range on demand. For looping, this is \n\ 112 : slightly faster than range() and more memory efficient."); 113 : 114 : static PyObject * 115 0 : range_item(rangeobject *r, Py_ssize_t i) 116 : { 117 0 : if (i < 0 || i >= r->len) { 118 0 : PyErr_SetString(PyExc_IndexError, 119 : "xrange object index out of range"); 120 0 : return NULL; 121 : } 122 : /* do calculation entirely using unsigned longs, to avoid 123 : undefined behaviour due to signed overflow. */ 124 0 : return PyInt_FromLong((long)(r->start + (unsigned long)i * r->step)); 125 : } 126 : 127 : static Py_ssize_t 128 3 : range_length(rangeobject *r) 129 : { 130 3 : return (Py_ssize_t)(r->len); 131 : } 132 : 133 : static PyObject * 134 0 : range_repr(rangeobject *r) 135 : { 136 : PyObject *rtn; 137 : 138 0 : if (r->start == 0 && r->step == 1) 139 0 : rtn = PyString_FromFormat("xrange(%ld)", 140 : get_stop_for_range(r)); 141 : 142 0 : else if (r->step == 1) 143 0 : rtn = PyString_FromFormat("xrange(%ld, %ld)", 144 : r->start, 145 : get_stop_for_range(r)); 146 : 147 : else 148 0 : rtn = PyString_FromFormat("xrange(%ld, %ld, %ld)", 149 : r->start, 150 : get_stop_for_range(r), 151 : r->step); 152 0 : return rtn; 153 : } 154 : 155 : /* Pickling support */ 156 : static PyObject * 157 0 : range_reduce(rangeobject *r, PyObject *args) 158 : { 159 0 : return Py_BuildValue("(O(lll))", Py_TYPE(r), 160 : r->start, 161 : get_stop_for_range(r), 162 : r->step); 163 : } 164 : 165 : static PySequenceMethods range_as_sequence = { 166 : (lenfunc)range_length, /* sq_length */ 167 : 0, /* sq_concat */ 168 : 0, /* sq_repeat */ 169 : (ssizeargfunc)range_item, /* sq_item */ 170 : 0, /* sq_slice */ 171 : }; 172 : 173 : static PyObject * range_iter(PyObject *seq); 174 : static PyObject * range_reverse(PyObject *seq); 175 : 176 : PyDoc_STRVAR(reverse_doc, 177 : "Returns a reverse iterator."); 178 : 179 : static PyMethodDef range_methods[] = { 180 : {"__reversed__", (PyCFunction)range_reverse, METH_NOARGS, reverse_doc}, 181 : {"__reduce__", (PyCFunction)range_reduce, METH_VARARGS}, 182 : {NULL, NULL} /* sentinel */ 183 : }; 184 : 185 : PyTypeObject PyRange_Type = { 186 : PyObject_HEAD_INIT(&PyType_Type) 187 : 0, /* Number of items for varobject */ 188 : "xrange", /* Name of this type */ 189 : sizeof(rangeobject), /* Basic object size */ 190 : 0, /* Item size for varobject */ 191 : (destructor)PyObject_Del, /* tp_dealloc */ 192 : 0, /* tp_print */ 193 : 0, /* tp_getattr */ 194 : 0, /* tp_setattr */ 195 : 0, /* tp_compare */ 196 : (reprfunc)range_repr, /* tp_repr */ 197 : 0, /* tp_as_number */ 198 : &range_as_sequence, /* tp_as_sequence */ 199 : 0, /* tp_as_mapping */ 200 : 0, /* tp_hash */ 201 : 0, /* tp_call */ 202 : 0, /* tp_str */ 203 : PyObject_GenericGetAttr, /* tp_getattro */ 204 : 0, /* tp_setattro */ 205 : 0, /* tp_as_buffer */ 206 : Py_TPFLAGS_DEFAULT, /* tp_flags */ 207 : range_doc, /* tp_doc */ 208 : 0, /* tp_traverse */ 209 : 0, /* tp_clear */ 210 : 0, /* tp_richcompare */ 211 : 0, /* tp_weaklistoffset */ 212 : range_iter, /* tp_iter */ 213 : 0, /* tp_iternext */ 214 : range_methods, /* tp_methods */ 215 : 0, /* tp_members */ 216 : 0, /* tp_getset */ 217 : 0, /* tp_base */ 218 : 0, /* tp_dict */ 219 : 0, /* tp_descr_get */ 220 : 0, /* tp_descr_set */ 221 : 0, /* tp_dictoffset */ 222 : 0, /* tp_init */ 223 : 0, /* tp_alloc */ 224 : range_new, /* tp_new */ 225 : }; 226 : 227 : /*********************** Xrange Iterator **************************/ 228 : 229 : typedef struct { 230 : PyObject_HEAD 231 : long index; 232 : long start; 233 : long step; 234 : long len; 235 : } rangeiterobject; 236 : 237 : static PyObject * 238 2724 : rangeiter_next(rangeiterobject *r) 239 : { 240 2724 : if (r->index < r->len) 241 2061 : return PyInt_FromLong(r->start + (r->index++) * r->step); 242 663 : return NULL; 243 : } 244 : 245 : static PyObject * 246 0 : rangeiter_len(rangeiterobject *r) 247 : { 248 0 : return PyInt_FromLong(r->len - r->index); 249 : } 250 : 251 : PyDoc_STRVAR(length_hint_doc, "Private method returning an estimate of len(list(it))."); 252 : 253 : static PyMethodDef rangeiter_methods[] = { 254 : {"__length_hint__", (PyCFunction)rangeiter_len, METH_NOARGS, length_hint_doc}, 255 : {NULL, NULL} /* sentinel */ 256 : }; 257 : 258 : static PyTypeObject Pyrangeiter_Type = { 259 : PyObject_HEAD_INIT(&PyType_Type) 260 : 0, /* ob_size */ 261 : "rangeiterator", /* tp_name */ 262 : sizeof(rangeiterobject), /* tp_basicsize */ 263 : 0, /* tp_itemsize */ 264 : /* methods */ 265 : (destructor)PyObject_Del, /* tp_dealloc */ 266 : 0, /* tp_print */ 267 : 0, /* tp_getattr */ 268 : 0, /* tp_setattr */ 269 : 0, /* tp_compare */ 270 : 0, /* tp_repr */ 271 : 0, /* tp_as_number */ 272 : 0, /* tp_as_sequence */ 273 : 0, /* tp_as_mapping */ 274 : 0, /* tp_hash */ 275 : 0, /* tp_call */ 276 : 0, /* tp_str */ 277 : PyObject_GenericGetAttr, /* tp_getattro */ 278 : 0, /* tp_setattro */ 279 : 0, /* tp_as_buffer */ 280 : Py_TPFLAGS_DEFAULT, /* tp_flags */ 281 : 0, /* tp_doc */ 282 : 0, /* tp_traverse */ 283 : 0, /* tp_clear */ 284 : 0, /* tp_richcompare */ 285 : 0, /* tp_weaklistoffset */ 286 : PyObject_SelfIter, /* tp_iter */ 287 : (iternextfunc)rangeiter_next, /* tp_iternext */ 288 : rangeiter_methods, /* tp_methods */ 289 : 0, 290 : }; 291 : 292 : static PyObject * 293 663 : range_iter(PyObject *seq) 294 : { 295 : rangeiterobject *it; 296 : 297 663 : if (!PyRange_Check(seq)) { 298 0 : PyErr_BadInternalCall(); 299 0 : return NULL; 300 : } 301 663 : it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); 302 663 : if (it == NULL) 303 0 : return NULL; 304 663 : it->index = 0; 305 663 : it->start = ((rangeobject *)seq)->start; 306 663 : it->step = ((rangeobject *)seq)->step; 307 663 : it->len = ((rangeobject *)seq)->len; 308 663 : return (PyObject *)it; 309 : } 310 : 311 : static PyObject * 312 0 : range_reverse(PyObject *seq) 313 : { 314 : rangeiterobject *it; 315 : long start, step, len; 316 : 317 0 : if (!PyRange_Check(seq)) { 318 0 : PyErr_BadInternalCall(); 319 0 : return NULL; 320 : } 321 0 : it = PyObject_New(rangeiterobject, &Pyrangeiter_Type); 322 0 : if (it == NULL) 323 0 : return NULL; 324 : 325 0 : start = ((rangeobject *)seq)->start; 326 0 : step = ((rangeobject *)seq)->step; 327 0 : len = ((rangeobject *)seq)->len; 328 : 329 0 : it->index = 0; 330 0 : it->len = len; 331 : /* the casts below guard against signed overflow by turning it 332 : into unsigned overflow instead. The correctness of this 333 : code still depends on conversion from unsigned long to long 334 : wrapping modulo ULONG_MAX+1, which isn't guaranteed (see 335 : C99 6.3.1.3p3) but seems to hold in practice for all 336 : platforms we're likely to meet. 337 : 338 : If step == LONG_MIN then we still end up with LONG_MIN 339 : after negation; but this works out, since we've still got 340 : the correct value modulo ULONG_MAX+1, and the range_item 341 : calculation is also done modulo ULONG_MAX+1. 342 : */ 343 0 : it->start = (long)(start + (unsigned long)(len-1) * step); 344 0 : it->step = (long)(0UL-step); 345 : 346 0 : return (PyObject *)it; 347 : } ```

 Generated by: LCOV version 1.10