LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@DOSS_INCREMENT

CPythonに後置インクリメントを加えてみた　実装編

Last updated at Posted at 2015-11-25

リンクリスト

全三回プラス番外編になっています。
CPythonに後置インクリメントを加えてみた　概要とまとめ
CPythonに後置インクリメントを加えてみた　実装編
CPythonに後置インクリメントを加えてみた　全変更点一覧
CPythonに後置インクリメントを加えてみた　番外編

実装編

いよいよ実際に実装する段である。

ビルド

環境

  • Ubuntu 15.04
  • gcc (Ubuntu 4.9.2-10ubuntu13) 4.9.2
  • GNU Make 4.0

Python 3.5.0のダウンロード

公式ウェブサイトからPython 3.5.0（本実験開始時点2015/10/22における最新版）をダウンロードして適当なディレクトリに置く。

ビルド

$ cd Python-3.5.0/
$ CFLAGS="-O0" ./configure --prefix=$HOME/local

$ ./configure      
checking build system type... x86_64-unknown-linux-gnu
checking host system type... x86_64-unknown-linux-gnu
...
creating Modules/Setup.local
creating Makefile

$ make -j 8 && make install
gcc -pthread -c -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes    -Werror=declaration-after-statement   -I. -IInclude -I./Include    -DPy_BUILD_CORE -o Programs/python.o ./Programs/python.c
gcc -pthread -c -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes    -Werror=declaration-after-statement   -I. -IInclude -I./Include    -DPy_BUILD_CORE -o Parser/acceler.o Parser/acceler.c
...

$ ./local/bin/python3
Python 3.5.0 (default, Nov 12 2015, 16:48:32)
[GCC 4.9.2] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>>

...

特にエラーがでて止まるなどということはなかった。
なお、Building and Using a Debug Version of Python ― Python Extension Patterns 0.1.0 documentationには、

$ ../configure CFLAGS='-DPy_DEBUG -DPy_TRACE_REFS' --with-pydebug

のようにオプションをつければデバッグしやすくなるように色々な情報が出力されるらしく、ソースコード中にもそれらしいマクロが定義されているのを見つけたが、結局使い方はよくわからなかった。

いじるのに使ったツール

  • gdb (+ emacs)
    • emacs: M-x gud-gdb
  • find
    • find . -name "hogehoge"
  • grep
    • grep hogehoge -r . -I
  • ctags
    • ctags **/*.c **/*.h

ソースコードを読むための技術というページをこれを書きながら見つけた。

手探る！

tokenに切り分ける

取り敢えず、Pythonがどのように動いているかを知るためにgdbで動きを追う。
EmacsでM-x gud-gdbとしてgdbを起動して、以下のようなPythonスクリプトを読ませて挙動を確かめる。

test.py
a = 0
a += 1
a++

これを素直に実行してみると

  File "test.py", line 3
    a++
      ^
SyntaxError: invalid syntax

と表示される。

そこで、main関数にブレークポイントを設定して動作を追いかけていく。

main関数はPrograms/python.cにある。
最初の方はargv_copyという変数がどうのこうのというのが続くが、引数の処理をしているだけなので飛ばして行くと、69行目から

Programs/python.c
res = Py_Main(argc, argv_copy);
    for (i = 0; i < argc; i++) {
            PyMem_RawFree(argv_copy2[i]);
    }
    PyMem_RawFree(argv_copy);
    PyMem_RawFree(argv_copy2);
    return res;

というのが見つかる。明らかに怪しいのでPy_Main関数の中を見ていく。これはModules/main.c内にある。

追っていくと768行目にsts = run_file(fp, filename, &cf);というのが見つかるのでステップインすると、今度は318行目にrun = PyRun_AnyFileExFlags(fp, filename_str, filename != NULL, p_cf);が見つかる。

このようにして名前を手がかりにして動きを追っていくと、

Python/pythonrun.c, 68: PyRun_AnyFileExFlags(FILE *fp, const char *filename, int closeit, PyCompilerFlags *flags)
Python/pythonrun.c, 339: PyRun_SimpleFileExFlags(FILE *fp, const char *filename, int closeit, PyCompilerFlags *flags)
PyRun_FileExFlags(fp, filename, Py_file_input, d, d,
closeit, flags);
Python/pythonrun.c, 396: PyRun_FileExFlags(fp, filename, Py_file_input, d, d, closeit, flags);

PyRun_FileExFlagsを追うと、その中（Python/pythonrun.cの916行目）にmod = PyParser_ASTFromStringObject(str, filename, start, flags, arena);というものを見つける。

関数名に”Parser”と入っている上に、ここでmodにNULLが代入されて、すぐ後のif文でgoto exit;している。くさい。中を見る。

Python/pythonrun.c: PyParser_ASTFromStringObject→Parser/parsetok.c: PyParser_ParseFileObject→Parser/parsetok.c: parsetokと辿っていくと201行目から以下のような箇所が見つかる。

    for (;;) {
            char *a, *b;
        int type;
            size_t len;
            char *str;
        int col_offset;

            type = PyTokenizer_Get(tok, &a, &b);
        if (type == ERRORTOKEN) {
                    err_ret->error = tok->done;
                    break;
            }

        ...

        len = b - a; /* XXX this may compute NULL - NULL */
            str = (char *) PyObject_MALLOC(len + 1);
        if (str == NULL) {
         
...

無限ループなので入力を片っ端から処理しているところだろうとあたりをつけて、試しにstrの値を表示しながらループを回していくと、strには順に”a”, “=”, “0”, “”, “a”, “+=”, “1”, “”, “a”, “+”, “+”, “”と入り、263行目PyParser_AddTokenでエラーを表す返り値が返ってきていることが分かる。

PyParser_AddToken内に入るとすぐilabel = classify(ps, type, str);という行が見つかり、このあとilabelの値に応じてエラー処理するところに飛んでいるっぽい。

classify内は


static int
classify(parser_state *ps, int type, const char *str)
{
    grammar *g = ps->p_grammar;
    int n = g->g_ll.ll_nlabels;

    ...

    {
        label *l = g->g_ll.ll_label;
            int i;
            for (i = n; i > 0; i--, l++) {
                    if (l->lb_type == type && l->lb_str == NULL) {
                        D(printf("It's a token we know\n"));
                        return n - i;
                    }
            }
    }

    D(printf("Illegal token\n"));
    return -1;
}

という具合になっている。

ざっと見た感じ、トークンのリストがあって、そこから一致するトークンを探しだしているようだ。

ということで、まず、インクリメントの”++”をひとつのトークンとして読むように改良する。このリストにどうにか”++”を追加できればここはクリアできそう。

遡っていき、parsetok関数内のtype = PyTokenizer_Get(tok, &a, &b);から、Parser/tokenizer.c: int PyTokenizer_Get(struct tok_state *tok, char **p_start, char **p_end)→Parser/tokenizer.c: static int tok_get(struct tok_state *tok, char **p_start, char **p_end)とくる。

コメントを参考に改行や数字を切り分けていると思しき部分を飛ばして行くと、/* Check for two-character token */というコメントから始まるブロック中にPyToken_TwoCharsやらPyToken_ThreeCharsといった関数が呼びだされているのがわかる。こいつらの中を見てみると、

Parser/tokenizer.c
    switch (c1) {
    case '=':
                switch (c2) {
                    case '=':               return EQEQUAL;
                }
                break;

という風にswitch文が続いており、ここに追加すれば++をトークンとして認識してくれそう。

まず、このreturnしているEQEQUALが定義されているInclude/token.hの最後にINCREMENTをこのように追加してみる。

Include/token.h
#define ERRORTOKEN    56
#define N_TOKENS    57

#ifdef DOSS_INCREMENT
#define INCREMENT 58
#endif

以下、変更点は#ifdef DOSS_INCREMENTと#endifで囲って示す。

更にgrep “EQEQUAL” -r -Iとしてみると、Parser/tokenizer.c 内にトークンの名前の配列があるので、以下のように手を加える。

Parser/tokenizer.c
/* Token names */

const char *_PyParser_TokenNames[] = {
 ...
    "<ERRORTOKEN>",
    "<N_TOKENS>"
    #ifdef DOSS_INCREMENT
    ,"INCREMENT"
    #endif
 };
Parser/tokenizer.c

int
PyToken_TwoChars(int c1, int c2)
{
    switch (c1) {
        ...
    case '+':
            switch (c2) {
            case '=':               return PLUSEQUAL;
            #ifdef DOSS_INCREMENT
            case '+':               return INCREMENT;
            #endif
        }
        break;
    
    （略）

さきほどのスイッチ文の場所に、定義したINCREMENTを返すように書き加える。

ここまでやってmakeしなおして、gdbで追いかけると、確かに++が一トークンとして読まれているのがわかる。なお、#ifdef DOSS_INCREMNET〜#endifを有効にするためにCFLAGSに　-DDOSS_INCREMENT=1を追加して、makeを行った。

もちろん、この変更だけではまだPyParser_AddToken関数がエラーの戻り値を返すままである。

大本命Grammar

さて、python grammarでググって見るとなんとGrammarというファイルが存在していることが判明した。そのサイトはここである。"the full Python grammar, as it is read by the parser generator and used to parse Python source files"なんて書いてある。読まねばなるまい。

開いて見ると正規表現によく似た文法の定義が書いてある。拡張BNF記法というらしい。こんなＣ言語でもないファイルで文法が書かれているのがにわかに信じられなかったのでこのファイルを消してmakeしてみた。するとビルドできなかった。どうやら本当に使われているらしい。
インクリメントに似ている累乗**の近くを見てみると、なんだか近いところがあったのでここを真似て変更することにした。

Grammar
#######################################
# #ifdef DOSS_INCREMENT
# Tips: We should not use Japanese here!!
#######################################
#factor: ('+'|'-'|'~') factor | power
#power: atom_expr ['**' factor]
# factor: power
factor: ['+'|'-'|'~'] inc ['**' factor]
inc: atom_expr ['++']
#######################################

最初の二行、

Grammar
factor: ('+'|'-'|'~') factor | power
power: atom_expr ['**' factor]

がもともとあったもの、下の二行,

Grammar
factor: ['+'|'-'|'~'] inc ['**' factor]
inc: atom_expr ['++']

が変更後である。なおコメント記号が#なので注意されたい。インクリメントを実装する以上、符号がいくつも付けられたらまずいと考えて、高々一つまでしか符号はつけられないようにした。あと++の演算子の優先順位は**よりも大きくした。

このGrammarファイルは後々までいろいろと助けてくれる。なんとコメントアウトされた部分にこれからのおおまかな道筋が書かれていた。一つ目は、文末の以下のコメントである。

Grammar
# The reason that keywords are test nodes instead of NAME is that using NAME
# results in an ambiguity. ast.c makes sure it's a NAME.
# "test '=' test" is really "keyword '=' test", but we have no such token.
# These need to be in a single rule to avoid grammar that is ambiguous
# to our LL(1) parser. Even though 'test' includes '*expr' in star_expr,
# we explicitly match '*' here, too, to give it proper precedence.
# Illegal combinations and orderings are blocked in ast.c:
# multiple (test comp_for) arguements are blocked; keyword unpackings
# that precede iterable unpackings are blocked; etc.

長いので要約するとast.cもいじってね、ということらしい。また、Grammarの初めにはこんなこともかいてある。

Grammar
# NOTE WELL: You should also follow all the steps listed at
# https://docs.python.org/devguide/grammar.html

なんと便利なサイトも紹介してくれている。このサイト、Pythonの公式ページで新しい文法の追加手順が書かれている。ただし、とても簡素に。

抽象構文木登場

Grammarで言われたとおりast.cを書き換えることにする。どうにも木構造を作っているらしいが、返り値がint型なのを見るに、文法エラーがないかどうかチェックしているだけっぽい。木構造はすでにつくられているのだろう。
よくわからないので、他のコードを真似て雰囲気でインクリメント用のものを実装する。ここで単に真似る、といってもこつがある。Grammarで変更したのは、factor,powerなのでおそらくこの二つを変更ないし削除して、incを打ち込めば良さそうということがわかる。あとは、++と同じ単項演算子の+,-,~あたりがどんな動作をしているのかを調べていくのである。具体的な変更は、ここを参照してもらいたい。

では早速makeしよう。

In file included from Python/ast.c:7:0:
Python/ast.c: In function ‘ast_for_inc’:
Python/ast.c:2492:22: error: ‘UInc’ undeclared (first use in this function)
       return UnaryOp(UInc, expression, LINENO(n), n->n_col_offset, c->c_arena);
                      ^
Include/Python-ast.h:503:49: note: in definition of macro ‘UnaryOp’
 #define UnaryOp(a0, a1, a2, a3, a4) _Py_UnaryOp(a0, a1, a2, a3, a4)
                                                 ^
Python/ast.c:2492:22: note: each undeclared identifier is reported only once for each function it appears in
       return UnaryOp(UInc, expression, LINENO(n), n->n_col_offset, c->c_arena);
                      ^
Include/Python-ast.h:503:49: note: in definition of macro ‘UnaryOp’
 #define UnaryOp(a0, a1, a2, a3, a4) _Py_UnaryOp(a0, a1, a2, a3, a4)
                                                 ^
make: *** [Python/ast.o] エラー 1

ast.cでエラーがでている。たしかにUIncなんて定義した記憶はない。このあとどうしようかとテキトーに前見た便利なサイトを見ていく。チェックリストを一部抜粋すると、

  • Grammar/Grammar: OK, you’d probably worked this one out :)
  • Parser/Python.asdl may need changes to match the Grammar. Run make to regenerate Include/Python-ast.h and Python/Python-ast.c.
  • Python/ast.c will need changes to create the AST objects involved with the Grammar change.
  • Parser/pgen needs to be rerun to regenerate Include/graminit.h and Python/graminit.c. (make should handle this for you.)
  • Python/symtable.c: This handles the symbol collection pass that happens immediately before the compilation pass.
  • Python/compile.c: You will need to create or modify the compiler_* functions to generate opcodes for your productions.

一番上はやった。二番目はよく意味がわからん。必要なのか？ast.cは書き換えた。pgenとsymtableを見るが特に変更するべき点が見つからない。とりあえず飛ばす。compile.cなんてものがあるらしい。インタプリタ言語であるはずのPythonでコンパイル…？気になるのでググるとまた便利なサイトが見つかった。コンパイラの作り方らしい。どうも本当にコンパイルしているようだ。bytecodeなんてものも見える。いろいろ調べた結果、どうもPython Virtual Machineというものがあって、それ用のバイトコードらしい。なんか低レイヤになってきたな。

compile.cの書き換え

たしかにcompile.cには、

compile.c
/*
 * This file compiles an abstract syntax tree (AST) into Python bytecode.
 *

なんて書いてある。UnaryやUAdd,powerなんかの単語で検索して、まわりに合わせるように自然にインクリメント用のものを追加していく。

compile.c
    case UNARY_POSITIVE:
    case UNARY_NEGATIVE:
    case UNARY_NOT:
    case UNARY_INVERT:
#ifdef DOSS_INCREMENT
    case UNARY_INCREMENT:
#endif
        return 0;
compile.c
    case UAdd:
        return UNARY_POSITIVE;
    case USub:
        return UNARY_NEGATIVE;
#ifdef DOSS_INCREMENT
    case UInc:
        return UNARY_INCREMENT;
#endif

のように変更した。ところでcompile.cでのマクロの使い方がとても面白いので余裕があればhogeにて説明しよう。さてmakeしよう。

In file included from Python/ast.c:7:0:
Python/ast.c: In function ‘ast_for_inc’:
Python/ast.c:2492:22: error: ‘UInc’ undeclared (first use in this function)
       return UnaryOp(UInc, expression, LINENO(n), n->n_col_offset, c->c_arena);
                      ^
Include/Python-ast.h:503:49: note: in definition of macro ‘UnaryOp’
 #define UnaryOp(a0, a1, a2, a3, a4) _Py_UnaryOp(a0, a1, a2, a3, a4)
                                                 ^
Python/ast.c:2492:22: note: each undeclared identifier is reported only once for each function it appears in
       return UnaryOp(UInc, expression, LINENO(n), n->n_col_offset, c->c_arena);
                      ^
Include/Python-ast.h:503:49: note: in definition of macro ‘UnaryOp’
 #define UnaryOp(a0, a1, a2, a3, a4) _Py_UnaryOp(a0, a1, a2, a3, a4)
                                                 ^
Python/compile.c: In function ‘PyCompile_OpcodeStackEffect’:
Python/compile.c:877:7: error: ‘UNARY_INCREMENT’ undeclared (first use in this function)
  case UNARY_INCREMENT:
       ^
Python/compile.c:877:7: note: each undeclared identifier is reported only once for each function it appears in
Python/compile.c: In function ‘unaryop’:
Python/compile.c:2755:7: error: ‘UInc’ undeclared (first use in this function)
  case UInc:
       ^
Python/compile.c:2756:10: error: ‘UNARY_INCREMENT’ undeclared (first use in this function)
   return UNARY_INCREMENT;
          ^
make: *** [Python/ast.o] エラー 1
make: *** 未完了のジョブを待っています....
make: *** [Python/compile.o] エラー 1

UIncとUNARY_INCREMENTが定義されていないと怒られてしまった。たしかに定義した記憶がない。

UNARY_INCREMENTを定義

まずはUNARY_INCREMENTから解決しよう。どこで定義するか調べるために

$ grep UNARY_INCREMENT . -r -I

とすると、./Include/opcode.h:#define UNARY_POSITIVE 10が見つかった。じゃあアドホックに追加しよう。

opcode.h
#define UNARY_POSITIVE           10
#define UNARY_NEGATIVE           11
#define UNARY_NOT                12
#ifdef DOSS_INCREMENT
#define UNARY_INCREMENT          13
#endif
#define UNARY_INVERT             15

UIncを定義

つぎにUIncを定義するべきファイルを見つけるためにまずはast.cにおいて単項演算子の（符号の）+がどんなふうに呼ばれているのか調べる。

ast.c
case PLUS:
            return UnaryOp(UAdd, expression, LINENO(n), n->n_col_offset,
                           c->c_arena);

こんな感じらしい。シンボリックリンクでUnaryOp()の定義元に飛ぶと、Python-ast.hの中であった。基本的に新しいソースコードにあった時は、一番はじめか一番最後にそのソースコードについての説明があるので例に漏れずそれを見る。

Python-ast.h
/* File automatically generated by Parser/asdl_c.py. */

一行目にこんなことが書いてある。このファイル自体が自動生成されているようだ。asdl_c.pyではたしかに自動生成するっぽいコードが書いてある。じゃあ実際に自動生成する現場を見てみよう。makeしたときに実行されるコマンドはMakefileの中にある。

$ grep asdl_c.py Makefile
ASDLGEN_FILES=    $(srcdir)/Parser/asdl.py $(srcdir)/Parser/asdl_c.py
ASDLGEN=    python3 $(srcdir)/Parser/asdl_c.py

たしかに使われている。今度は、

$ grep ASDLGEN Makefile
ASDLGEN_FILES=    $(srcdir)/Parser/asdl.py $(srcdir)/Parser/asdl_c.py
ASDLGEN=    python3 $(srcdir)/Parser/asdl_c.py
$(AST_H): $(AST_ASDL) $(ASDLGEN_FILES)
    $(ASDLGEN) -h $(AST_H_DIR) $(AST_ASDL)
$(AST_C): $(AST_H) $(AST_ASDL) $(ASDLGEN_FILES)
    $(ASDLGEN) -c $(AST_C_DIR) $(AST_ASDL)

として生成現場を見る。実際に生成を駆動するのはAST_ASDLらしいので、

$ grep AST_ASDL Makefile
AST_ASDL=    $(srcdir)/Parser/Python.asdl
$(AST_H): $(AST_ASDL) $(ASDLGEN_FILES)
    $(ASDLGEN) -h $(AST_H_DIR) $(AST_ASDL)
$(AST_C): $(AST_H) $(AST_ASDL) $(ASDLGEN_FILES)
    $(ASDLGEN) -c $(AST_C_DIR) $(AST_ASDL)

とすれば、Python.asdlが見つかる。さて見てみよう。だらーっ、と見ていくとGrammarでみたような単語が並んでいる。そこでpowerやUAddなどの単語で検索していくと次の行が見つかる。

Python.asdl
    unaryop = Invert | Not | UAdd | USub

単項演算子の種類を規定しているっぽい。そこでこれにUIncを追加してみる。

Python.asdl
    -- #ifdef DOSS_INCREMENT
    -- unaryop = Invert | Not | UAdd | USub
    unaryop = Invert | Not | UAdd | USub | UInc
    -- #endif

なおコメントが--らしい。さあmakeしよう。なんとビルドできた！だがチラっとerrorと見えた気がする…。なのでmake | grep errorで実行。

/Modules/parsermodule.c: In function ‘validate_power’:
/Modules/parsermodule.c:2501:37: error: ‘power’ undeclared (first use in this function)
     int res = (validate_ntype(tree, power) && (nch >= 1)
                                     ^
/Modules/parsermodule.c:2501:37: note: each undeclared identifier is reported only once for each function it appears in
/Modules/parsermodule.c: In function ‘validate_node’:
/Modules/parsermodule.c:3390:16: error: ‘power’ undeclared (first use in this function)
           case power:
                ^

parsermodule.cも変更する必要がありそうだ。

parsermodule.cの変更

validateと名のつく関数が大量においてあり、どうもGrammarで定義した文法の引数の数、型があっているかどうかをチェックしているっぽい。Grammarで新しくincをつくり、powerを消したので、対応する変化をこちらにも施さなければならない。変更箇所が多いのでここで確認してほしい。

ここまで変更するとmake、make installとも通るのでとりあえず実行してみる。

$ ./python3
Python 3.5.0 (default, Nov 16 2015, 17:03:57)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> i=0
>>> i++
XXX lineno: 1, opcode: 101
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
SystemError: unknown opcode
>>> +++++1
  File "<stdin>", line 1
    +++++1
     ^
SyntaxError: invalid syntax

なんとi++が「文法上」許容されるようになった。ただしかし実行時にそんなオペコードは登録されていないと弾かれた。たしかに登録していない。一方の+++++1はSyntax Errorになった。もともとのPythonでは許容される表現だが、インクリメント実装に合わせてGrammarで禁じたものだ。たしかに文法エラーになっているので文法の書き換えは成功している。

「中身」の実装

残すは、++の「中身」だけである。方針としてはunknown opcodeがどこで発せられているか調べて定義元でインクリメントの動作を定義すれば良いのだろう。gdbを使って追跡していく。なおこのときrun test.pyとしたが、test.pyの中身は以下。

i=0
i++

エラーメッセージはpythonrun.c:401,PyErr_Print()で発せられているようである。

pythonrun.c
    } else {
        /* When running from stdin, leave __main__.__loader__ alone */
        if (strcmp(filename, "<stdin>") != 0 &&
            set_main_loader(d, filename, "SourceFileLoader") < 0) {
            fprintf(stderr, "python: failed to set __main__.__loader__\n");
            ret = -1;
            goto done;
        }
        v = PyRun_FileExFlags(fp, filename, Py_file_input, d, d,
                              closeit, flags);
    }
    flush_io();
    if (v == NULL) {
        PyErr_Print();
        goto done;
    }
    Py_DECREF(v);

v == NULLであるからエラーメッセージが出ているので、PyRun_FileExFlags()に潜っていく。この関数の返り値は、pythonrun.c:961,run_mod()によって、さらにそれは…ともぐっていく。するとceval.cに辿り着き、3429行目でPyErr_SetString(PyExc_SystemError, "unknown opcode");とエラーメッセージをセットしていることがわかる。
ceval.cの説明は極めてシンプルで、

ceval.c
/* Execute compiled code */

となっている。Python Virtual Machineの心臓部、VMのALUといったところか。ということはここをいじればインクリメントを実装できそうではある。ただ、漫然と眺めていても糸口が掴めそうにはなかった。

ちょっと後戻り

それにしたってopcode.hでオペコードを定義したのにunknownとはどういうことかと思ってもう一度opcode.hを開いてみる。一行目に

opcode.h
/* Auto-generated by Tools/scripts/generate_opcode_h.py */

なんて書いてあった。直接変えても意味なかったんだ。Makefileを検索する。

$ grep opcode.h Makefile -3
PGENOBJS=    $(POBJS) $(PGOBJS)

##########################################################################
# opcode.h generation
OPCODE_H_DIR=     $(srcdir)/Include
OPCODE_H_SCRIPT= $(srcdir)/Tools/scripts/generate_opcode_h.py
OPCODE_H=    $(OPCODE_H_DIR)/opcode.h
OPCODE_H_GEN=    python3  $(OPCODE_H_SCRIPT) $(srcdir)/Lib/opcode.py $(OPCODE_H)
#
##########################################################################

opcode.pyなんてもので生成しているらしい。ここはこんな風に追加した。

opcode.py
def_op('NOP', 9)
def_op('UNARY_POSITIVE', 10)
def_op('UNARY_NEGATIVE', 11)
def_op('UNARY_NOT', 12)
#ifdef DOSS_INCREMENT
def_op('UNARY_INCREMENT',13)
#endif
def_op('UNARY_INVERT', 15)

見つからない関数

makeするとエラーメッセージがさらに進化した。

In file included from Python/ceval.c:891:0:
Python/ceval.c: In function ‘PyEval_EvalFrameEx’:
Python/opcode_targets.h:15:5: error: label ‘TARGET_UNARY_INCREMENT’ used but not defined
     &&TARGET_UNARY_INCREMENT,
     ^
gcc -pthread -c -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -Wstrict-prototypes -O0 -g -DDOSS_INCREMENT=1   -Werror=declaration-after-statement   -I. -IInclude -I./Include    -DPy_BUILD_CORE -o Python/future.o Python/future.c
make: *** [Python/ceval.o] エラー 1
make: *** 未完了のジョブを待っています....

エラーの通りopcode_targets.hにはTARGET_UNARY_INCREMENTが自動生成されていた。その定義がceval.cにないのが問題らしい。でもTARGET_UNARY_POSITIVEでceval.cを検索しても一致するものがない。

$ grep TARGET_UNARY_POSITIVE . -r -I
./Python/opcode_targets.h:    &&TARGET_UNARY_POSITIVE,

ここでしか使われていない…！これはおかしい。条件を狭めてceval.cでUNARY_POSITIVEを検索すると

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

こんなものがヒットした。これは関数…ではない。マクロだ！冒頭の方にに邪悪なマクロの定義が見つかる。こんな文言も。

ceval.c
/* Computed GOTOs, or
       the-optimization-commonly-but-improperly-known-as-"threaded code"
   using gcc's labels-as-values extension
   (http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html).

説明を読む限りswitch文でオペコードを分類するよりもマクロを使ってgoto文を駆使したほうが早いらしい。インタプリタ言語の涙ぐましい高速化への工夫が垣間見える。このせいでコードの可読性が著しく損なわれているが。

ということでTARGET(UNARY_INCREMENT)を作成する。

ceval.c
    #ifdef DOSS_INCREMENT
            TARGET(UNARY_INCREMENT) {
                PyObject *left = TOP();
                PyObject *inv, *sum;
                // note that -(~x) == x+1 for all x
                inv = PyNumber_Invert(left);
                //Py_DECREF(left);
                if (inv == NULL)
                    goto error;
                sum = PyNumber_Negative(inv);
                Py_DECREF(inv);
                if (sum == NULL)
                    goto error;

                SET_TOP(sum);

                DISPATCH();
            }
    #endif

TOPやSET_TOPというのはスタックへのアクセスらしい。またPy_DECREF()マクロがよく呼ばれているようだが、おそらくガベージコレクションをしているのではないかと思われる。

卑怯な定義

上でPyNumber_Invert()やPyNumber_Negative()が出てくる。たしかにインクリメントを正統に実装するためにはPyNumber_Increment()なる関数を作ったほうがいいのかもしれない。あるいは1を表すオブジェクトを作成して、加算命令で実現するべきだったかもしれない。ただ、関数の定義元を調べに行き、色々してみたが複雑でよくわからず、時間的制約もあったので、既存の関数をうまく利用することになったことをここに告白する。

-(~x) == x+1 for all x

という事実を用いてxから既存の関数のみでx+1を生成することに成功した。これをmakeして動かすと、

$ ./python3
Python 3.5.0 (default, Nov 16 2015, 18:50:21)
[GCC 4.8.4] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> i=0
>>> print(i++)
1
>>> i
0

なんと認識して動き出した。i++に対してちゃんと値が返ってくるようになった。ただしiの値が書き換わることはなかった。いままで「自然に」インクリメントを定義してきたが、どこかでその自然さから変数の書き換えが漏れたらしい。

evalとexec

parsermodule.cに以下のような意味深なコメントを見つけた。

parsermodule.c
/*  There are two types of intermediate objects we're interested in:
 *  'eval' and 'exec' types.  These constants can be used in the st_type
 *  field of the object type to identify which any given object represents.
 *  These should probably go in an external header to allow other extensions
 *  to use them, but then, we really should be using C++ too.  ;-)
 */

すなわちevalとexecの二つのタイプがあるらしい。これはi+1とi+=1に代表される。いま問題なのは++iはこれら両方の性質を合わせ持つことである。

変数の書き換えはi+=1で行われる。これはGrammarでどのように定義されているのかと調べるとAugAssignとなっていて今まで見てきた+や-とは全く別の場所にある。文法の段階から変数の書き換え部分とはまったくことなるところに存在していたのだ。デバッガで追って見るとAugAssignの方ではceval.cにおいてSTORE命令が実行されていた。時間の制約上、文法段階から見直すことは避けたいし、なにより+=の方に焦点を当てると変数は書き換わるが値が返ってこない可能性があった。

overviewふたたび

ここでPythonの流れを整理する。

  1. トークナイザーで入力文字列をトークンに分ける
  2. Grammarにしたがって具体構文木を作る
  3. ast.cで抽象構文木を作成する
  4. compile.cで抽象構文木をバイトコードに変換する
  5. ceval.cによってバイトコードをVM上で実行する

最後のつめ

evalとexecが分離しているPython設計思想に反したインクリメントを実装するのだからどうやっても綺麗に実装できることはない。ただ、上の選択肢の中から一つ変えるものを選ぶのならば、最も正統だと思われるのはcompile.cを書き換えることだと思われる。今までは、インクリメントに対する構文木に対して明示的には+1した値を返すオペコードしか出力しなかった。これに対してSTORE命令も追加することによって所望の動作を獲得できると考えられる。

i++という書き方から++のオペランドはiとなっているはずである。これをAugAssignに対応する場所にあるSTORE命令をコピーしてきて+1演算を行った後に追加するだけで実行することができた。

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?