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というものがあるそうで、ちゃんと 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 … いろいろなヘッダファイルをまとめたやつ
• 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に説明があり、全てのオブジェクト型は PyObject の拡張になるとのこと。

コメントにPY_SSIZE_T_MAXなる値が登場している。Py_ssize_t は ssize_t と違って符合ありのinteger。 ssize_t についてはPEP 353 -- Using ssize_t as the index type | Python.orgで触れられている。

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) を示していて、メモリ割当を行って PyObject を作るもの。詳しいことはobject.cを辿って読めばわかりそう。略。

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

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

/* 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は元をただせば

#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は、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で

PyLong_CheckExact(ob) || PyBool_Check(ob)

のチェックがされた状態で実行される。PyLong_CheckExactもPyBool_Checkも意味はそのまま、型チェックをするマクロ。

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

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

(PyLong_CheckExact(ob) || PyBool_Check(ob)) なら上記のrange_contains_longを使って、それ以外の時は _PySequence_IterSearch で判定をする。

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

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

/*
   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 かどうかのチェックはある。
opは比較演算子を指し、この関数が対象としているのは Py_NE と Py_EQ のみ。

最終的にはrange_equalsを呼ぶ。

497〜550: range_hash(rangeobject *r)

rangeobject 用のハッシュ関数。Py_hash_tという型で出して返す。ハッシュを出すのに使っている値はlen()とstartとstep。len(r)の値に応じて処理を変えている。

/* 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の場合、存在していることをチェックしたあと

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

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

604〜613: range_as_sequence

PySequenceMethodsに合わせて各種関数を登録。
ここでは

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の補助関数らしい。Py_BuildValue(_Py_BuildValue_SizeT)に struct rangeobject の情報を与える。

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

itemが
PyIndex_Check(要はint)を通ればcompute_range_itemで、
PySlice_Check(要はslice)を通ればcompute_sliceで、
要素を返す。それ以外はエラー。

665〜669: range_as_mapping

こんどはPyMappingMethodsに合わせて登録している。実装された関数は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はPython上の関数とCでの実装の関数、引数情報、ドキュメントを紐づけるもの。

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

ビルトイン	Cでの実装
__reversed__	range_reverse →1134
__reduce__	range_reduce →635
count	range_count →552
index	range_index →572

692〜697: range_members

PyMemberDefはCの構造体のメンバの名前とタイプとオフセットを表す。ここではstartとstopとstepの情報の配列になっている。

699〜738: PyRange_Type

PyRange_Type という型の定義。いろいろな設定項目があるが、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
unsigned long tp_flags	Py_TPFLAGS_DEFAULT
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は 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
getattrofunc tp_getattro	PyObject_GenericGetAttr
unsigned long tp_flags	Py_TPFLAGS_DEFAULT
getiterfunc tp_iter	PyObject_SelfIter
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)中にあるアイテムの数を返す。

    /* -------------------------------------------------------------
    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で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
unsigned long tp_flags	Py_TPFLAGS_DEFAULT
getiterfunc tp_iter	PyObject_SelfIter
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のきもちはむずかしい。