Posted at
PythonDay 10

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

More than 1 year has passed since last update.

この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では rangexrange は違うという話があったらしい。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.htypedef 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_HEADPyObject についてはCommon Object Structuresに説明があり、全てのオブジェクト型は PyObject の拡張になるとのこと。

コメントにPY_SSIZE_T_MAXなる値が登場している。Py_ssize_tssize_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 であることと、その PyObjectPyLong とみなして話が進むこと。


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_CheckExactPyBool_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_NEPy_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_INITPyObject の初期セグメントを定義する関係のものらしい。


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のきもちはむずかしい。