Pythonに前置・後置インクリメントを追加してみた

こんにちは。この記事はEEIC(東京大学工学部 電気電子工学科/電子情報工学科)3年の後期実験「大規模ソフトウェアを手探る」という授業でPythonを改造してインクリメントの機能を追加してみた体験談になります。今後Pythonを改造してみようと思った方にとっての道しるべとなれば幸いです。

このページに載せている変更点はポイントのみの抜粋です。
全変更点は別ページに載せています。

環境

PC: Ubuntu 20.04 LTS
デバッガ: VSCode & GDB 9.2

cpythonのソースコードのクローン & ビルドのテスト

公式のGitHubのリポジトリから引っ張ってきます。

ビルドは

$ CFLAGS="-O0 -g" ./configure --prefix=[directory to install]
$ make -j 8
$ make install

-O0 -gをつけることでデバッガで追跡しやすいようにビルドしています。
makeの-jオプションは高速化のためです。

cpythonのディレクトリには予想を遥かに上回る膨大な量のファイルが入っていてたじろぎましたが、Python Developer's Guide の Changing CPython’s Grammar に Python の文法を書き換える手順が記載されており、無事スタートをきることができました。

班員は全員が学科PCのUbuntuを使用していましたが、自分だけビルド時に以下のようなエラーが出ました。

$ make install

の時に

Traceback (most recent call last):
  File "<frozen zipimport>", line 511, in _get_decompress_func
ModuleNotFoundError: No module named 'zlib'
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
  File "<frozen zipimport>", line 559, in _get_data
  File "<frozen zipimport>", line 514, in _get_decompress_func
zipimport.ZipImportError: can't decompress data; zlib not available
During handling of the above exception, another exception occurred:
Traceback (most recent call last):
  File "<string>", line 6, in <module>
  File "<frozen runpy>", line 222, in run_module
  File "<frozen runpy>", line 148, in _get_module_details
  File "<frozen runpy>", line 112, in _get_module_details
  File "<frozen zipimport>", line 137, in get_code
  File "<frozen zipimport>", line 693, in _get_module_code
  File "<frozen zipimport>", line 561, in _get_data
zipimport.ZipImportError: can't decompress data; zlib not available
Traceback (most recent call last):
  File "<frozen runpy>", line 198, in _run_module_as_main
  File "<frozen runpy>", line 88, in _run_code
  File "/home/denjo/cpython/Lib/ensurepip/__main__.py", line 5, in <module>
    sys.exit(ensurepip._main())
             ^^^^^^^^^^^^^^^^^
  File "/home/denjo/cpython/Lib/ensurepip/__init__.py", line 286, in _main
    return _bootstrap(
           ^^^^^^^^^^^
  File "/home/denjo/cpython/Lib/ensurepip/__init__.py", line 202, in _bootstrap
    return _run_pip([*args, *_PACKAGE_NAMES], additional_paths)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/denjo/cpython/Lib/ensurepip/__init__.py", line 103, in _run_pip
    return subprocess.run(cmd, check=True).returncode
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/denjo/cpython/Lib/subprocess.py", line 570, in run
    raise CalledProcessError(retcode, process.args,
subprocess.CalledProcessError: Command '['/home/denjo/cpython/python', '-W', 'ignore::DeprecationWarning', '-c', '\nimport runpy\nimport sys\nsys.path = [\'/tmp/tmp_betnd_9/setuptools-63.2.0-py3-none-any.whl\', \'/tmp/tmp_betnd_9/pip-22.2.2-py3-none-any.whl\'] + sys.path\nsys.argv[1:] = [\'install\', \'--no-cache-dir\', \'--no-index\', \'--find-links\', \'/tmp/tmp_betnd_9\', \'--root\', \'/\', \'--upgrade\', \'setuptools\', \'pip\']\nrunpy.run_module("pip", run_name="__main__", alter_sys=True)\n']' returned non-zero exit status 1.
make: *** [Makefile:1876: install] エラー 1

このエラーは、

$ sudo apt install zlib1g-dev
$ sudo apt install libssl-dev

とすることで解消できました。

演算子の追加

Pyhton に元から存在する演算子を模倣してみます。インクリメントは単項演算子であるため、unary operator として追加しました。

1. Grammar/Tokensにインクリメントの演算子++を追加
2. Lib/ast.pyにunopとして追加
3. Grammar/python.gramにおいて| '++' a=primary { _PyAST_UnaryOp(Incr, a, EXTRA) }と| a=primary '++' { _PyAST_UnaryOp(Incr, a, EXTRA) }を追加
4. Parser/Python.asdlのunaryopにIncrを追加
5. ast.rstにIncrを追加

オペコードの追加

Lib/opcode.py, Doc/library/dis.rstにopcode=13としてIncrを登録してみます。
そしてmake regen-opcode regen-opcode-targetsを実行。

エラー

全く見に覚えのないwith openというところでエラー。
調べてみるとcpython/Makefileにおいて、make regenで用いられるpythonがpython3.8指定と古かったために起こったエラーと判明。
PYTHON_FOR_REGEN?=python3
と変更して、さらにローカル環境に3.10をインストールすることでエラーは無事解消したのですが、今度はpythonのバージョンに対してUbuntuに元から入っているOpenSSLが古いために別のエラーが生じてしまいました。
OpenSSLバージョン1.1.1qを入れ直し、sudo apt install libssl-devを実行するとエラーが無事解消しました。パッケージの依存関係のためか、ただOpenSSLを入れるだけではだめでlibsslを入れる必要がありました。

バイトコードの追加

オペコードを追加した後、ようやくインクリメントの機能を記述していきます。

ceval.c内に様々な演算子が呼ばれたときの動きが書かれています。
例）UNARY_POSITIVE(足し算の演算子ではなく数値の前につく＋のこと)

TARGET(UNARY_POSITIVE) {
    PyObject *value = TOP();
    PyObject *res = PyNumber_Positive(value);
    Py_DECREF(value);
    SET_TOP(res);
    if (res == NULL)
        goto error;
    DISPATCH();
}

これを見ると演算はPyNumber_Poitiveという関数で行われていることが分かります。そこで同じようにPyNumber_Incrimentという関数を作成してみようとしたのですが、ソースコードを手探っていくうちに演算子についての関数が書かれてあるabstract.cだけでなく、long_object.c,object.c,setobject.c,interpreteridobject.c,operator.c,ast_opt.cなど変更が必要なファイルだらけであり、それらを他の関数の見様見真似で書き加えてみても色々とエラーが出てしまったのでunary_incriment独自の関数を作成することを断念し、既存の加算の関数関数PyNumber_InPlaceAddと1を返す関数_PyLong_GetOne()を利用して、
PyObject *res = PyNumber_InPlaceAdd(value, _PyLong_GetOne());
とすることにしました。
前置と後置の違いについては後に述べることとしてここでは変更したコードだけを載せます。

前置

TARGET(UNARY_PREINCREMENT) {
    PyObject *value = TOP();
    PyObject *res = PyNumber_Add(value, _PyLong_GetOne());
    Py_DECREF(value);
    SET_TOP(res);
    PUSH(res);
    if (res == NULL)
        goto error;
    DISPATCH();
}

後置

TARGET(UNARY_POSTINCREMENT) {
    PyObject *value = TOP();
    PyObject *res = PyNumber_Add(value, _PyLong_GetOne());
    PUSH(res);
    if (res == NULL)
        goto error;
    DISPATCH();
}

コンパイラの対応

上記でインクリメントの機能を実装することができたものの、残念ながら変数の値は書き換わりませんでした。

>>> i = 0
>>> ++i
1
>>> i
0

そこでストア命令が行われているceval.c/TARGET(STORE_NAME)を参考に上記のUNARY_INCREMENTの中にストア命令を組み込みました。

TARGET(UNARY_PREINCREMENT) {
    PyObject *value = TOP();
    PyObject *res = PyNumber_InPlaceAdd(value, _PyLong_GetOne());
    Py_DECREF(value);
    SET_TOP(res);
    if (res == NULL)
        goto error;
    // STORE
    PyObject *name = GETITEM(names, oparg);
    PyObject *ns = LOCALS();
    int err;
    if (ns == NULL) {
        _PyErr_Format(tstate, PyExc_SystemError,
                "no locals found when storing %R", name);
        goto error;
    }
    err = PyObject_SetItem(ns, name, res);
    if (err != 0)
        goto error;
    // end STORE
    DISPATCH();
}

これで変数の値の書き換えは上手くできたのですが、インクリメントの機能をリストの要素やクラスのオブジェクトに対して適応することができませんでした。どうやらSTORE_NAMEというバイトコードは変数限定のストア命令だったようです。というわけでSTOREをインクリメント実行部から分離させ、コンパイラcompile.cにおいてインクリメント命令の直後に適切な種類のSTORE命令を実行させる方針に変更します。

static int
compiler_visit_expr1(struct compiler *c, expr_ty e)
{
    switch (e->kind) {
    // 省略
    case UnaryOp_kind:
        VISIT(c, expr, e->v.UnaryOp.operand);
        ADDOP(c, unaryop(e->v.UnaryOp.op));
        if (e->v.UnaryOp.op == PreIncr || e->v.UnaryOp.op == PostIncr) {
            // increment op
            expr_ty operand = e->v.UnaryOp.operand;
            if (e->v.UnaryOp.operand->kind == Name_kind) {
                // store name
                compiler_nameop(c, operand->v.Name.id, Store);
            }
            else if (e->v.UnaryOp.operand->kind == Subscript_kind) {
                // store subscript
                operand->v.Attribute.ctx = Store;
                VISIT(c, expr, operand);
            }
            else if (e->v.UnaryOp.operand->kind == Attribute_kind) {
                // store attribute
                operand->v.Attribute.ctx = Store;
                VISIT(c, expr, operand);
            }
            else {
                // type error
                PyErr_Format(PyExc_SystemError,
                "invalid node type (%d) for increment",
                e->kind);
                return 0;
            }
        }
        break;
    // 省略
    return 1;
}

ストア命令を型によってif文で場合分けしています。
Name_kindeは変数、Subscript_kindはリストや辞書など、Attribute_kindはクラスのことです。

ポイント

前置・後置の作り分け

前置インクリメントは対象にSTOREされる値も返り値もどちらも+1された値ですが、後置インクリメントではSTOREされる値は+1された後の値、返り値は+1を実行する前の値です。
後述の逆アセンブラdisを使うことで、インクリメントを実行するとまずRETURNが呼び出され、そのあとにSTOREが実行されることが分かりました。
そこでスタックのTOPに返り値を、SECONDにSTOREされる値を入れておくことでインクリメントの仕様を実現しました。

前置インクリメント

後置インクリメント

インクリメント命令の対象は？

はじめはインクリメントの対象は変数のみであると考えていました。そのためPython.gramにおいてNAMEを用いてインクリメントの文法を定義していました。ところが配列の要素やクラスのメンバ変数などもインクリメントの対象であることに先生のコメントで気付き、NAMEでは不十分であることが発覚しました。single_targetなどさまざまなものを試しましたがなかなかうまく行かず、結果primaryを用いることになりました。
ただし、primaryでは定数が含まれてしまい、定数に対してインクリメントを実行するとSegmentation Faultとなってしまうので、Python/ast_opt.cにおいて定数を排除することで対策しています。

if (node->v.UnaryOp.op == PreIncr || node->v.UnaryOp.op == PostIncr) {
    // error
    PyErr_SetString(PyExc_TypeError, "invalid operand type for increment");
    return 0;
}
else {
    PyObject *newval = ops[node->v.UnaryOp.op](arg->v.Constant.value);
    return make_const(node, newval, arena);
}

逆アセンブラ - dis

Pythonのライブラリには逆アセンブラというものがあり、今回の実験ではかなり役に立ちました。
インタプリタ型言語であるPythonのコードを実行する際は、まずAST（抽象構文木）に変換された後仮想的なアセンブリ言語であるバイトコードに変換され、仮想マシン上で実行されます。
このバイトコードを見ることができるのが逆アセンブラです。
Pythonの仮想マシンではメモリ構造としてスタックを用いているため、バイトコードを見ることでどの順でスタックを積めば良いのかが分かります。

以下は今回実装した前置・後置インクリメントのバイトコードです。

>>> import dis
>>> i = 0
>>> dis.dis('i++')
  0           0 RESUME                   0

  1           2 LOAD_NAME                0 (i)
              4 UNARY_POSTINCREMENT
              6 STORE_NAME               0 (i)
              8 RETURN_VALUE
>>> dis.dis('++i')
  0           0 RESUME                   0

  1           2 LOAD_NAME                0 (i)
              4 UNARY_PREINCREMENT
              6 STORE_NAME               0 (i)
              8 RETURN_VALUE

参考サイト集

• "Changing CPython's Grammar", Python Developer's Guide
• "Setup and Building", Python Developer's Guide
• "Compiler Design", Python Developer's Guide
• "PEP 617 – New PEG parser for CPython", Python Enhancement Proposals
• "CPythonに後置インクリメントを加えてみた　全変更点一覧", Qiita
  @DOSS_INCREMENT
• "Pythonが動く仕組み", ゼロから学ぶPython