rangeの実装(Objects/rangeobject.c)を読んだ

この1年間「Pythonらしさ」がわからず悩み続けた結果、気付いたら私は `range` の実装を読んでいた。

`range` じゃなくて `xrange` を使おうね！っていうPython2時代の話から超脱線した。

# CPythonについて

リポジトリ: https://hg.python.org/cpython
ミラー: https://github.com/python/cpython
(Mercurialはよくわからないので以下全部Git)

https://github.com/python/cpython/tree/master/Objects
に色々と面白そうなものが並んでいる。どれもこれも長くて読み応え半端ない。

> Source files for various builtin objects

# rangeについて

Python2では `range` と `xrange` は違うという話があったらしい。Python3では気にしなくて良くなったらしい。
[2to3](http://docs.python.jp/3.5/library/2to3.html)というものがあるそうで、ちゃんと `xrange` から `range` に直すプログラムも存在している。
https://github.com/python/cpython/blob/master/Lib/lib2to3/fixes/fix_xrange.py

今回は
https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/rangeobject.c
を読む。
1246行もあるけど難易度はきっと低め。

# レッツトライ

## 3〜4: include

ヘッダファイルは
https://github.com/python/cpython/tree/master/Include
に入っている。

rangeobject.cで読むのは

* [Python.h](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/Python.h) … いろいろなヘッダファイルをまとめたやつ
* [structmember.h](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/structmember.h) … `typedef struct PyMemberDef`

の2つ。
`PyMemberDef` の配列は、Cの構造体のメンバの名前や型やオフセットを定義しているらしい。

## rangeobject

### 6〜19: struct rangeobject

構造体rangeobjectは

* PyObject_HEAD (= PyObject ob_base)
* PyObject *start
* PyObject *stop
* PyObject *step
* PyObject *length

を持つ。rangeっぽい。
`PyObject_HEAD` と `PyObject` については[Common Object Structures](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Doc/c-api/structures.rst)に説明があり、全てのオブジェクト型は `PyObject` の拡張になるとのこと。

コメントに[PY_SSIZE_T_MAX](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/pyport.h#L108)なる値が登場している。`Py_ssize_t` は `ssize_t` と違って符合ありのinteger。 `ssize_t` については[PEP 353 -- Using ssize_t as the index type | Python.org](https://www.python.org/dev/peps/pep-0353/)で触れられている。

### 21〜39: validate_step(PyObject *step)

検証ステップ用の補助関数(直訳)。
ステップ0はrangeとして不適当なので、それをチェックしているらしい。ステップの指定がない場合は1とみなされる。

### 41〜42: compute_range_length(PyObject *start, PyObject *stop, PyObject *step)

→151行目

### 44〜64: make_range_object(PyTypeObject *type, PyObject *start, PyObject *stop, PyObject *step)

引数から `rangeobject` を作る。本当に `rangeobject` を作るのは下記range_newのほうで、range_newで色々チェックした後問題がなければmake_range_objectが呼ばれる。
`rangeobject` はオブジェクトなので `PyObject` の拡張である。なので `PyObject` を作ってからrangeの値(startなど)を与える。

`PyObject_New(type, typeobj)` とは `(type *) _PyObject_New(typeobj)` を[示していて](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/objimpl.h#L134-L135)、メモリ割当を行って `PyObject` を作るもの。詳しいことは[object.c](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/object.c)を辿って読めばわかりそう。略。

### 66〜129: range_new(PyTypeObject *type, PyObject *args, PyObject *kw)

ちゃんと諸々のチェックをして `rangeobject` を作る。不適切な値が渡されてきた場合は作るのを諦めて確保したメモリを確保、 `NULL` を返す。
こんなコメントが付いてた。

```c
/* XXX(nnorwitz): should we error check if the user passes any empty ranges?
   range(-10)
   range(0, -5)
   range(0, 5, -1)
*/
```

### 131〜139: PyDoc

PyDoc_STRVARなるマクロを使ってrange(stop)やrange(start, stop[, step])のドキュメントが書かれている。
[PyDoc_STRVAR](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/pymacro.h#L69-L76)は元をただせば

```c
#define PyDoc_VAR(name) static char name[]
```

に行き着く。インラインドキュメント用のマクロとのこと。

### 141〜149: range_dealloc(rangeobject *r)

`struct rangeobject` のメンバの解放→構造体の解放をしている。

### 151〜227: compute_range_length(PyObject *start, PyObject *stop, PyObject *step)

range(lo, hi, step)中のアイテム数を計算して返す。
アルゴリズムは865行目から始まるget_len_of_range(lo, hi, step)と同じらしく、詳しい話はそちらに書いてある。違いは引数が `PyObject` であることと、その `PyObject` を `PyLong` とみなして話が進むこと。

### 229〜233: range_length(rangeobject *r)

メンバのlengthを `Py_ssize_t` にして返す。
ここで使われている[PyLong_AsSsize_t](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/longobject.c)は、int型オブジェクトから `Py_ssize_t` を返すものらしい。

### 235〜248: compute_item(rangeobject *r, PyObject *i)

startとiとstepから値を計算、次の値を出す。コメントにも `return r->start + (i * r->step)` とある。そのまま。

### 250〜307: compute_range_item(rangeobject *r, PyObject *arg)

上記compute_itemを呼び出す方。
その前にarg(実態は `PyLong` らしい)からcompute_item(rangeobject *r, PyObject *i)のiを出して範囲チェックをしている。

### 309〜319: range_item(rangeobject *r, Py_ssize_t i)

上記のcompute_range_itemを呼び出す側。こちらは関数の引数や参照周りの面倒を見ている。

### 321〜358: compute_slice(rangeobject *r, PyObject *_slice)

`rangeobject` のスライスを作る。失敗時の処理や参照解放もやる。

### 360〜409: range_contains_long(rangeobject *r, PyObject *ob)

次のrange_containsやrange_index、range_countで

```c
PyLong_CheckExact(ob) || PyBool_Check(ob)
```

のチェックがされた状態で実行される。[PyLong_CheckExact](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/longobject.h#L16)も[PyBool_Check](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/boolobject.h#L12)も意味はそのまま、型チェックをするマクロ。

中身としては単純にobがrangeobjectの示す範囲内に収まっているか(=存在しているか)。

### 411〜419: range_contains(rangeobject *r, PyObject *ob)

`(PyLong_CheckExact(ob) || PyBool_Check(ob))` なら上記のrange_contains_longを使って、それ以外の時は [_PySequence_IterSearch](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/abstract.c#L1898-L1984) で判定をする。

### 421〜465: range_equals(rangeobject *r0, rangeobject *r1)

2つの `rangeobject` を比較する関数。どこを順番に見ていって判定を出すかの概要がコメントに書いてある。

```c
/*
   if r0 is r1:
       return True
   if len(r0) != len(r1):
       return False
   if not len(r0):
       return True
   if r0.start != r1.start:
       return False
   if len(r0) == 1:
       return True
   return r0.step == r1.step
*/
```

### 467〜495: range_richcompare(PyObject *self, PyObject *other, int op)

引数は `PyObject` だが、ちゃんとotherが `PyRange_Type` かどうかの[チェック](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/rangeobject.h#L22)はある。
opは[比較演算子を指し](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L927)、この関数が対象としているのは `Py_NE` と `Py_EQ` のみ。

最終的にはrange_equalsを呼ぶ。

### 497〜550: range_hash(rangeobject *r)

`rangeobject` 用のハッシュ関数。[Py_hash_t](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/pyport.h#L93)という型で出して返す。ハッシュを出すのに使っている値はlen()とstartとstep。len(r)の値に応じて処理を変えている。

```c
/* Hash function for range objects.  Rough C equivalent of

   if not len(r):
       return hash((len(r), None, None))
   if len(r) == 1:
       return hash((len(r), r.start, None))
   return hash((len(r), r.start, r.step))
*/
```

### 552〜570: range_count(rangeobject *r, PyObject *ob)

`PyLong_CheckExact(ob) || PyBool_Check(ob)` の時はrange_contains_longで、それ以外の時は_PySequence_IterSearchで数える。

### 572〜602: range_index(rangeobject *r, PyObject *ob)

`PyLong_CheckExact(ob) || PyBool_Check(ob)` の時はrange_contains_longで、それ以外の時は_PySequence_IterSearchでさがす。
range_contains_longの場合、存在していることをチェックしたあと

```c
idx = PyNumber_FloorDivide(tmp, r->step);
```

で場所を計算して出している。

### 604〜613: range_as_sequence

[PySequenceMethods](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L287-L299)に合わせて各種関数を登録。
ここでは

| `PySequenceMethods` |range_as_sequence|
|---|---|
| `lenfunc` sq_length|range_length → 229行目|
| `ssizeargfunc` sq_item|range_item → 309行目|
| `objobjproc` sq_contains|range_contains → 411行目|

のみが登録されている。

### 615〜633: range_repr(rangeobject *r)

出力用の文字列をPyUnicodeで出す。stepが1の時はstepは省略される。

### 635〜641: range_reduce(rangeobject *r, PyObject *args)

[pickle](https://docs.python.org/3.6/library/pickle.html)の補助関数らしい。[Py_BuildValue](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/modsupport.h#L22)([\_Py_BuildValue_SizeT](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Python/modsupport.c#L441-L450))に `struct rangeobject` の情報を与える。

### 643〜662: range_subscript(rangeobject* self, PyObject* item)

itemが
[PyIndex_Check](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/abstract.h#L870-L872)(要はint)を通ればcompute_range_itemで、
[PySlice_Check](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/sliceobject.h#L31)(要はslice)を通ればcompute_sliceで、
要素を返す。それ以外はエラー。

### 665〜669: range_as_mapping

こんどは[PyMappingMethods](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L301-L305)に合わせて登録している。実装された関数は3個中2個。

| `PyMappingMethods` |range_as_mapping|
|---|---|
| `lenfunc` mp_length|range_length → 229行目|
| `binaryfunc` mp_subscript|range_subscript → 643行目|

### 671: range_iter(PyObject *seq)

→1076行目

### 672: range_reverse

→1134行目

### 674〜682: PyDoc

reverseとcountとindexのドキュメント。

### 684〜690: range_methods

[PyMethodDef](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/methodobject.h#L54-L61)はPython上の関数とCでの実装の関数、引数情報、ドキュメントを紐づけるもの。

ここでは以下の関数が紐づけられている。

|ビルトイン|Cでの実装|
|---|---|
|\_\_reversed__|range_reverse →1134|
|\_\_reduce__|range_reduce →635|
|count|range_count →552|
|index|range_index →572|

### 692〜697: range_members

[PyMemberDef](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/structmember.h#L18-L24)はCの構造体のメンバの名前とタイプとオフセットを表す。ここではstartとstopとstepの情報の配列になっている。

### 699〜738: PyRange_Type

`PyRange_Type` という型の定義。[いろいろな設定項目がある](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L343-L436)が、rangeの場合は以下のような情報が登録されている。

| `PyTypeObject` | `PyRange_Type` |
|---|---|
| `const char` *tp_name|"range"|
| `Py_ssize_t` tp_basicsize|sizeof(rangeobject)|
| `destructor` tp_dealloc|(destructor)range_dealloc →141|
| `reprfunc` tp_repr|(reprfunc)range_repr →615|
| `PySequenceMethods` *tp_as_sequence|&range_as_sequence →604|
| `PyMappingMethods` *tp_as_mapping|&range_as_mapping →665|
| `hashfunc` tp_hash|(hashfunc)range_hash →497|
| `getattrofunc` tp_getattro|[PyObject_GenericGetAttr](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/object.c#L1118-L1122)|
| `unsigned long` tp_flags|[Py_TPFLAGS_DEFAULT](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L656-L659)|
| `const char` *tp_doc|range_doc|
| `richcmpfunc` tp_richcompare|range_richcompare →467|
| `getiterfunc` tp_iter|range_iter →1076|
| `struct PyMethodDef` *tp_methods|range_methods →684|
| `struct PyMemberDef` *tp_members|range_members →692|
| `newfunc` tp_new|range_new →66|


ちなみに[PyVarObject_HEAD_INIT](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L89-L90)は `PyObject` の初期セグメントを定義する関係のものらしい。

## rangeiterobject

### 740〜753: struct rangeiterobject

`rangeobject` と同じような定義になるが、微妙に異なる。

* PyObject_HEAD (= PyObject ob_base)
* long index
* long start
* long step
* long len

### 755〜764: rangeiter_next(rangeiterobject *r)

startにindex*stepを足すことで次の値を得る。
オーバーフロー回避のためunsignedにキャストして返す処理をしている。

### 766〜770: rangeiter_len(rangeiterobject *r)

len - indexで長さを出す。

### 772〜773: PyDoc

length_hint_doc。リストの長さの概算を出すprivate method、らしい。

### 775〜802: rangeiter_reduce(rangeiterobject *r)

pickle用関数。 `PyLong` への変換がある分rangeobjectよりも手間が多い。

### 804〜817: rangeiter_setstate(rangeiterobject *r, PyObject *state)

indexに値をセットする。

### 819〜820: PyDoc

reduceとsetstateのdoc。どちらもpickle関係、らしい。

### 822〜830: rangeiter_methods

|ビルトイン|Cでの実装|
|---|---|
|\_\_length_hint__|rangeiter_len →766|
|\_\_reduce__|rangeiter_reduce →775|
|\_\_setstate__|rangeiter_setstate → 804|

### 832〜863: PyRangeIter_Type

| `PyTypeObject` | `PyRangeIter_Type` |
|---|---|
| `const char` *tp_name|"range_iterator"|
| `Py_ssize_t` tp_basicsize|sizeof(rangeiterobject)|
| `destructor` tp_dealloc|(destructor)[PyObject_Del](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/objimpl.h#L118)|
| `getattrofunc` tp_getattro|[PyObject_GenericGetAttr](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/object.c#L1118-L1122)|
| `unsigned long` tp_flags|[Py_TPFLAGS_DEFAULT](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L656-L659)|
| `getiterfunc` tp_iter|[PyObject_SelfIter](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/object.c#L990-L995)|
| `iternextfunc` tp_iternext|(iternextfunc)rangeiter_next →755|
| `struct PyMethodDef` *tp_methods|rangeiter_methods →822|

PyObject_DelとPyObject_DELがあるのなんでだろう…。

### 865〜891: get_len_of_range(long lo, long hi, long step)

range(lo, hi, step)中にあるアイテムの数を返す。

```c
    /* -------------------------------------------------------------
    If step > 0 and lo >= hi, or step < 0 and lo <= hi, the range is empty.
    Else for step > 0, if n values are in the range, the last one is
    lo + (n-1)*step, which must be <= hi-1.  Rearranging,
    n <= (hi - lo - 1)/step + 1, so taking the floor of the RHS gives
    the proper value.  Since lo < hi in this case, hi-lo-1 >= 0, so
    the RHS is non-negative and so truncation is the same as the
    floor.  Letting M be the largest positive long, the worst case
    for the RHS numerator is hi=M, lo=-M-1, and then
    hi-lo-1 = M-(-M-1)-1 = 2*M.  Therefore unsigned long has enough
    precision to compute the RHS exactly.  The analysis for step < 0
    is similar.
    ---------------------------------------------------------------*/
```

コメントの説明の方がコードより長い。要は区間をステップ数で割っているだけ。

### 893〜915: fast_range_iter(long start, long stop, long step)

rangeiterを作る。Cのlong型より長いとエラーとしてNULLが返る。

## longrangeiterobject

### 917〜923: struct longrangeiterobject

* PyObject_HEAD (= PyObject ob_base)
* PyObject *index
* PyObject *start
* PyObject *step
* PyObject *len

こっちは `PyObject` 。

### 925〜929: longrangeiter_len(longrangeiterobject *r, PyObject *no_args)

[PyNumber_Subtract](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/abstract.h#L737-L743)でlenからindexを引いて出す。

### 931〜958: longrangeiter_reduce(longrangeiterobject *r)

pickle用。stopを算出し、make_range_objectでrangeobjectを作ることで値を計算する。

### 960〜987: longrangeiter_setstate(longrangeiterobject *r, PyObject *state)

indexにstateを突っ込む。

### 989〜997: longrangeiter_methods

|ビルトイン|Cでの実装|
|---|---|
|\_\_length_hint__|longrangeiter_len →925|
|\_\_reduce__|longrangeiter_reduce →931|
|\_\_setstate__|longrangeiter_setstate → 960|

### 999〜1007: longrangeiter_dealloc(longrangeiterobject *r)

structのメンバ→ `longrangeiterobject` の順で参照を消している。

### 1009〜1041: longrangeiter_next(longrangeiterobject *r)

やはりstartにstep * indexを足して計算している。

### 1043〜1074: PyLongRangeIter_Type

| `PyTypeObject` | `PyRangeIter_Type` |
|---|---|
| `const char` *tp_name|"longrange_iterator"|
| `Py_ssize_t` tp_basicsize|sizeof(longrangeiterobject)|
| `destructor` tp_dealloc|(destructor)longrangeiter_dealloc →999|
| `getattrofunc` tp_getattro|[PyObject_GenericGetAttr](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/object.c#L1118-L1122)|
| `unsigned long` tp_flags|[Py_TPFLAGS_DEFAULT](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Include/object.h#L656-L659)|
| `getiterfunc` tp_iter|[PyObject_SelfIter](https://github.com/python/cpython/blob/28b093620c3ae9be02449ea0cecd8b4d649c80d2/Objects/object.c#L990-L995)|
| `iternextfunc` tp_iternext|(iternextfunc)longrangeiter_next →1009|
| `struct PyMethodDef` *tp_methods|longrangeiter_methods →989|

## iter生成

### 1076〜1132: range_iter(PyObject *seq)

`rangeobject` seqからrangeiterを作るパターンとlongrangeiterを作るパターンがある。start、stop、rangeがCのlong型で表現できるかが境目。

### 1134〜1246: range_reverse(PyObject *seq)

こちらもやはりlongで収まるかのチェックをしている。reverseなのでstepは-stepのチェックも必要。あとはうまくstartとstopを置き換えて生成。

# 感想

長かったけどCPythonの雰囲気はなんとなくわかった気がする。
まともなC言語は初めて読んだし勉強になった。(手続き型言語としてのしょぼいCを大学でやっただけ)

で、結局Pythonらしさってなんだろう。Pythonのきもちはむずかしい。