Home CPython C Python

# Range 的實現原理

老規矩，先看看 range 的 docstring

range(stop) -> range object
range(start, stop[, step]) -> range object
Return an object that produces a sequence of integers from start (inclusive)
to stop (exclusive) by step.  range(i, j) produces i, i+1, i+2, ..., j-1.
start defaults to 0, and stop is omitted!  range(4) produces 0, 1, 2, 3.
These are exactly the valid indices for a list of 4 elements.
When step is given, it specifies the increment (or decrement).


首先，調用 range () 時，它會返回一個 range object，那在 CPython 裏，對應的就是 rangeobject 結構體，但最終返回的還是 PyObject *，range 對應 CPython 中 PyRange_Type，位於 Objects/rangeobject.c


PyTypeObject PyRange_Type = {
        PyVarObject_HEAD_INIT(&PyType_Type, 0)
        "range",                /* Name of this type */
        sizeof(rangeobject),    /* Basic object size */
        0,                      /* Item size for varobject */
        (destructor)range_dealloc, /* tp_dealloc */
        0,                      /* tp_vectorcall_offset */
        0,                      /* tp_getattr */
        0,                      /* tp_setattr */
        0,                      /* tp_as_async */
        (reprfunc)range_repr,   /* tp_repr */
        &range_as_number,       /* tp_as_number */
        &range_as_sequence,     /* tp_as_sequence */
        &range_as_mapping,      /* tp_as_mapping */
        (hashfunc)range_hash,   /* tp_hash */
        0,                      /* tp_call */
        0,                      /* tp_str */
        PyObject_GenericGetAttr,  /* tp_getattro */
        0,                      /* tp_setattro */
        0,                      /* tp_as_buffer */
        Py_TPFLAGS_DEFAULT,     /* tp_flags */
        range_doc,              /* tp_doc */ 
        0,                      /* tp_traverse */
        0,                      /* tp_clear */
        range_richcompare,      /* tp_richcompare */
        0,                      /* tp_weaklistoffset */
        range_iter,             /* tp_iter */
        0,                      /* tp_iternext */
        range_methods,          /* tp_methods */
        range_members,          /* tp_members */
        0,                      /* tp_getset */
        0,                      /* tp_base */
        0,                      /* tp_dict */
        0,                      /* tp_descr_get */
        0,                      /* tp_descr_set */
        0,                      /* tp_dictoffset */
        0,                      /* tp_init */
        0,                      /* tp_alloc */
        range_new,              /* tp_new */
        .tp_vectorcall = (vectorcallfunc)range_vectorcall
};
在調用 range (10)、range (0, 10)、range (0, 10, 2) 的時候，首先會執行 range_new 方法


static PyObject *
range_new(PyTypeObject *type, PyObject *args, PyObject *kw)
{
    if (!_PyArg_NoKeywords("range", kw))
	// 校驗是否沒有傳遞關鍵字，如果沒有傳遞，表示真，傳遞了，為假
        return NULL;
    /*
	創建 rangeobject 並返回，_PyTuple_ITEMS 將 args 轉爲 PyTupleObject, 並取出 ob_item
	PyTyple_GET_SIZE 獲取參數的數量
    */
    return range_from_array(type, _PyTuple_ITEMS(args), PyTuple_GET_SIZE(args));
}
那在創建 range 對象時，主要是執行了 range_from_array 方法，一切事情都發生在裏面


static PyObject *
range_from_array(PyTypeObject *type, PyObject *const *args, Py_ssize_t num_args)
{
    rangeobject *obj; // 首先聲明一個 rangeobject 對象，如果創建成功就會返回此對象
    PyObject *start = NULL, *stop = NULL, *step = NULL; // 定義 range 的起始、結尾、間隔
    // 參數個數
    switch (num_args) {
        case 3:
	    // 傳遞了 3 個參數: start、stop、step
            step = args[2]; // 取出第 3 个参数：间隔
            /* fallthrough */
        case 2:
	    // 傳遞了 2 個參數: start、stop
            /* Convert borrowed refs to owned refs */
            start = PyNumber_Index(args[0]); // 校验类型并返回索引，方法实现在下方
            if (!start) {
		// 为空，不是有效的 int
                return NULL;
            }
            stop = PyNumber_Index(args[1]); // 校验类型并返回索引
            if (!stop) {
		// 为空，不是有效的 int
                Py_DECREF(start); // 引用计数 - 1
                return NULL;
            }
	    // 验证间隔，实现方法在下面
            step = validate_step(step);  /* Caution, this can clear exceptions */
            if (!step) {
		// 如果为空
                Py_DECREF(start); //start 引用计数 - 1
                Py_DECREF(stop); //stop 引用计数 - 1
                return NULL; // 结束
            }
            break;
        case 1:
	    // 傳遞了 1 個參數: stop
            stop = PyNumber_Index(args[0]); // 校验类型並返回索引
            if (!stop) {
                return NULL;
            }
            Py_INCREF(_PyLong_Zero);
            start = _PyLong_Zero;
            Py_INCREF(_PyLong_One);
            step = _PyLong_One;
            break;
        case 0:
	    // 儅 range 傳遞參數為 0 個時，抛異常
            PyErr_SetString(PyExc_TypeError,
                            "range expected at least 1 argument, got 0");
            return NULL;
        default:
	    // 儅 range 傳遞參數超過 3 個時，抛異常
            PyErr_Format(PyExc_TypeError,
                         "range expected at most 3 arguments, got %zd",
                         num_args);
            return NULL;
    }
    obj = make_range_object(type, start, stop, step); // 真正開始創建 rangeobject, 裏面做了計算 range 的範圍長度
    if (obj != NULL) {
	// 創建 rangeobject 成功，返回 PyObject *
        return (PyObject *) obj;
    }
    /* Failed to create object, release attributes */
    // 創建失敗，釋放屬性
    Py_DECREF(start);
    Py_DECREF(stop);
    Py_DECREF(step);
    return NULL;
}
static PyObject *
validate_step(PyObject *step)
{
    // 校验间隔
    /* No step specified, use a step of 1. */
    if (!step)
	// 如果没有指定间隔，就默认使用 1
        return PyLong_FromLong(1); // 从 C long int 中创建一个 Python int 对象
    step = PyNumber_Index(step); // 校验类型并返回索引
    if (step && _PyLong_Sign(step) == 0) {
	// 如果间隔给了 0, 抛异常
        PyErr_SetString(PyExc_ValueError,
                        "range() arg 3 must not be zero");
        Py_CLEAR(step);
    }
    return step; // 返回步长
}
image.png


PyNumber_Index 方法的定义，返回 Python int 对象，如果结果不是 int，就会引发 TypeError，或者对象不能作为索引


PyObject *
PyNumber_Index(PyObject *item)
{
    PyObject *result = NULL;
    if (item == NULL) {
        return null_error();
    }
    if (PyLong_Check(item)) {
	// 如果 item 是一個 PyLongObject 或者子類，則返回 True
        Py_INCREF(item); // 引用計數 + 1
        return item;
    }
    if (!_PyIndex_Check(item)) {
	// 如果對象不是一個 PyLongObject，檢查對象是否定義了__index__方法
        PyErr_Format(PyExc_TypeError,
                     "'%.200s' object cannot be interpreted "
                     "as an integer", Py_TYPE(item)->tp_name);
        return NULL;
    }
    // 在 item 的父類中，獲取 tp_as_number (實現了數字協議對象相關的結構), 並取出 np_index 調用，對應 Python 對象的__index__方法，
    result = Py_TYPE(item)->tp_as_number->nb_index(item);
    if (!result || PyLong_CheckExact(result))
	// 如果返回非 0 或者為 PyLongObject
        return result; // 成功返回
    if (!PyLong_Check(result)) {
	// 如果返回的不是一個 PyLongObject, 抛異常，比如在 Python 中返回 None 或者非 int 對象
        PyErr_Format(PyExc_TypeError,
                     "__index__ returned non-int (type %.200s)",
                     Py_TYPE(result)->tp_name);
        Py_DECREF(result); // 引用計數 - 1
        return NULL;
    }
    /* Issue #17576: warn if 'result' not of exact type int. */
    if (PyErr_WarnFormat(PyExc_DeprecationWarning, 1,
            "__index__ returned non-int (type %.200s).  "
            "The ability to return an instance of a strict subclass of int "
            "is deprecated, and may be removed in a future version of Python.",
            Py_TYPE(result)->tp_name)) {
        Py_DECREF(result);
        return NULL;
    }
    return result;
}
在 PyNumber_Index 中，如果對象不是 PyLongObject，還會檢查對象是否定義了__index__，在沒有重載的情況下作爲參數傳遞給 range

image.png


如果重載了__index__方法的情況下，range 成功創建了 rangeobject

image.png


如果重載了__index__方法，但是返回的不是 PyLongObject，就會抛異常: “index returned non-int (type %.200s)”

image.png


# for … in range 時，發生了什麽？


在 Python 中，對一個對象進行循環迭代時，首先會調用對象的__iter__方法，獲取 iterator，再對 iterator 一直調用__next__方法，獲取 iterable，直到遇到 StopIteration，就會停止，那麽在對 rangeobject 進行迭代時，就是執行了 rangeobject 定義好的__iter__方法，對應 range_iter 方法


static PyObject *
range_iter(PyObject *seq)
{
    rangeobject *r = (rangeobject *)seq;
    longrangeiterobject *it; // 在調用__iter__時，如果大小範圍超出，返回的是 longrangeiterobject, 儅調用__next__時，實際就是調用它的__next__方法，而不是 rangeobject
    long lstart, lstop, lstep; // 起始、結束、間隔
    unsigned long ulen;
    assert(PyRange_Check(seq));
    
    // If all three fields and the length convert to long, use the int
    ......
    
    /*
	get_len_of_range 主要計算 range 範圍 / 長度
	如果 step > 0 并且 start >= stop，或者 step < 0 并且 start <= stop, 那麽返回的範圍為空 -> []
	對於 step > 0, 如果 n 個值在範圍内，則最後一個值為 start + (n - 1) * step && <= stop - 1
	1. 儅 step (間隔) > 0 && start (起始) < stop (結束) 時，1 + (stop - 1 - start) /step, 如 1 + (10 - 1 - 0) / 1 = 10
	2. 儅 step < 0 && start > stop 時，1 + (start - 1 - stop) / (0 - (-step)), 如 1 + (0 - 1 - 10) / (0 - (-1)) = -10
	3. 否則返回 0, 也就是空範圍
    */
    ulen = get_len_of_range(lstart, lstop, lstep);
    if (ulen > (unsigned long)LONG_MAX) {
	// 如果計算的範圍長度大於最大範圍，
        goto long_range;
    }
    /* check for potential overflow of lstart + ulen * lstep */
    if (ulen) {
        if (lstep > 0) {
            if (lstop > LONG_MAX - (lstep - 1))
                goto long_range;
        }
        else {
            if (lstop < LONG_MIN + (-1 - lstep))
                goto long_range;
        }
    }
    // 範圍一般都不會太大，一般都會進入該方法，這裏返回的是 rangeiterobject, 而不是 longrangeiterobject
    return fast_range_iter(lstart, lstop, lstep, (long)ulen);
  long_range:
    // 超出最大值，返回 longrangeiterobject
    it = PyObject_New(longrangeiterobject, &PyLongRangeIter_Type);
    if (it == NULL)
        return NULL;
    it->start = r->start; // 起始
    it->step = r->step; // 結尾
    it->len = r->length; // 長度 / 範圍
    it->index = _PyLong_Zero; // 索引
    Py_INCREF(it->start); // 引用計數 + 1
    Py_INCREF(it->step);
    Py_INCREF(it->len);
    Py_INCREF(it->index);
    return (PyObject *)it;
}
static PyObject *
fast_range_iter(long start, long stop, long step, long len)
{
    rangeiterobject *it = PyObject_New(rangeiterobject, &PyRangeIter_Type);
    if (it == NULL)
        return NULL;
    it->start = start;
    it->step = step;
    it->len = len;
    it->index = 0; // 索引默認為 0
    return (PyObject *)it;
}
關於 get_len_of_range 的注釋説明，是我找女同事翻譯的，也不一定都對，但是特別感謝她😜




如果 step > 0 且 lo >= hi，或 step <0 且 lo <= hi，则范围为空。否则对于 step> 0，如果 n 个值在范围内，则最后一个是

 lo + (n-1) step，它必须 <= hi-1。 重新排列，n <= (hi - lo - 1)/step + 1，所以拿 RHS 的底层给出适当的值。 因为 lo < hi 在这种情况下， hi-lo-1 >= 0，所以 RHS 是非负数，因此截断与底层一样。 令 M 为最大的正长整型，RHS 分子最坏的情况是 hi=M, lo=-M-1, 然后 hi-lo-1 = M-(-M-1)-1 = 2M。 因此 无符号长整型 就足够精确计算 RHS 的精准度。 step < 0 的分析很相似。




儅執行 for … in range (10) 時，它才開始計算範圍，如果範圍沒有超出最大值，那麽返回的對象為 rangeiterobject，那麽此時，在調用__next__時，就是調用 rangeiterobject 的__next__方法，rangeiterobject 對應 PyRangeIter_Type, __next__會調用 rangeiter_next


static PyObject *
rangeiter_next(rangeiterobject *r)
{
    // 每調用一次__next__, 就會執行這裏
    if (r->index < r->len)
	// 如果 index 小於計算的範圍，index 默認為 0
        /* cast to unsigned to avoid possible signed overflow
           in intermediate calculations. */
	// 返回一個 PyLongObject，每次計算為
	// 假設 range (10), 那麽第 1 次，start 為 0, index 為 0, step 默認為 1
	// 第 1 次: 0 + 0 * 1 = 0
	// 第 2 次: 0 + 1 * 1 = 1
	// 第 10 次: 0 + 9 * 1 = 9
	// 結果為: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
        return PyLong_FromLong((long)(r->start +
                                      (unsigned long)(r->index++) * r->step));
    return NULL;
}
range 的基本流程基本就這些了，還有一些 count、index 方法，我基本沒用過，有興趣可以自己去探討一下


      

          
          
      

  


   


    

  
    
      
    
    Edited on
    
  
  
      
        
      
      Views
      
      times
  



      


  
  
Give me a cup of [coffee]~(￣▽￣)~*

  

      
      

        小芳芳 WeChat Pay
        
WeChat Pay

      

      
      

        小芳芳 Alipay
        
Alipay