Pythonに bit演算子を追加してみた

はじめに

はじめまして、#チーム名募集中（モグリン、しみだい）と申します。この記事は東京大学工学部電気電子工学科・電子情報工学科で開講されている「電気電子情報実験・演習第二 /大規模ソフトウェアを手探る」の成果報告レポートになります。今回、私たちのチームでは普段使用しているプログラミング言語である Pythonを手探ることにしました。

実験環境

課題設定

元々 Pythonの内部で C言語が動いているのは2人とも知っていたのですが、どのような挙動をしているのかは全く知らなかったのでそこを探るのが主目的です。しかし、成果物として最終的に Pythonに何らかの変更を加えることを考えるともう少し絞った課題も持つ必要があったので、具体的には以下の課題を設定しました。

まずは build（written by モグリン）

ソースのダウンロード

Pythonは公式のリポジトリが存在するので単純にこれを forkしちゃってもいいんですけどどうせなので OSS（オープンソースソフトウェア）らしく公式の source tarballをダウンロードして展開する方向で行くことにしました。
Python Source Releases | Python.orgから今までリリースされた Pythonの各バージョンをダウンロードすることが出来ます。今回は Python 3.10.7をダウンロードすることにしました。上記のリンクから飛んでソースをダウンロードできます（下の画像のような画面がでるはずなので Gzipped source tarballをクリック）。

ダウンロード画面

無事ダウンロードが終わったら（おそらく Python-3.10.7.tgzというファイルがダウンロードされているはず）適当な作業ディレクトリに移動させて展開、おなじみの

$ tar xvzf Python-3.10.7.tgz

で展開させて、ひとまずソースコードの取り込みは終わりです。

いざ build

まずは展開したディレクトリに移動。

$ cd Python-3.10.7/

次に実行ファイルのインストール先のディレクトリを決めます（もしくは作る）。今回は/home/Python/にインストールすることにします。インストール先のディレクトリが決まったらいよいよ build。

$ CFLAGS="-O0 -g" ./configure --prefix=/home/Python/
$ make
$ make install

するとちょこちょこ警告が出る上に、以下のようなエラーで終わります。

ERROR: pip's dependency resolver does not currently take into account all the packages that are installed. This behaviour is the source of the following dependency conflicts.
numba 0.56.2 requires setuptools<60, but you have setuptools 63.2.0 which is incompatible.

numba 0.56.2 なるものに必要な setuptools 63.2.0 がないせいでうまくbuild出来てないらしい、困った。と思ってよく見るとエラー文の下にもう一行ありました。

Successfully installed pip-22.2.2 setuptools-63.2.0

......これmake installの依存関係が壊れてて正しい順番でコンパイル出来てないだけだったりしません？？？、とは思ったのですが/configureの中身いじるのは流石に骨が折れそうだったので一旦放置、結局実験レベルのコードなら問題なく動いたためここのエラーはこのままでした（いずれ解決したい）。ともあれ、これにて build完了です。

gdbによるデバッグ開始（written by モグリン）

VSCodeで Cファイルをデバッグするにはまず設定ファイル（launch.json）を書かなければいけません。この課題に取り組むプロジェクト直下に.vscode/launch.jsonの形でファイルを作ります。作り終わったら TAさんの資料を参考に以下のようにlaunch.jsonを書きます。

{
    "version": "0.2.0",
    "configurations": [
      {
        "name": "C/C++: debug",
        "type": "cppdbg",
        "request": "launch",
        "program": "/home/Python/bin/python3", // ビルドした Pythonのバイナリへの絶対パス
        "args": ["-c","1+1"],          // 実行時引数
        "stopAtEntry": true,            // 実行後すぐに一旦止める
        "cwd": "${workspaceFolder}",    // 実行時の作業ディレクトリ
        "MIMode": "gdb"                 // 利用するデバッガ。macOS の場合は lldb 推奨
      }
    ]
}

Pythonは python3 -c <実行したいPythonのソースコード> で .pyファイルに書き込むことなくソースコードを実行できます。今回は演算子の挙動を確認したいので引数に["-c", "1+1"]を渡しています。

ここまで来たら後は Ctrl + Shift + Dでデバッガモードに移行し、F5でデバッガを走らせることが出来ます。ステップごとの実行については先ほどの資料に書かれているので省略します。

と、ここまでデバッガの使用方法の説明をしておいてなんですが、結局この実験中でデバッガを使ったのは最初の4日間だけで、さらにはこの期間中の作業はほぼ無に帰しました（追記：相方は何とか役に立ててたらしいです、完全に無駄にならなくてよかった～）。理由については次節で......。

Pythonの内部理解（written by モグリン）

これは実験4日目に他班の発表にて知ったのですが Pythonは構文解析の際に使用する C言語ソースファイルを設定ファイルによる自動生成によって生み出しており、デバッガを使いながら内部を手探る手法と致命的に相性が悪いのです。さらには Pythonは公式ドキュメントで CPythonの内部解説や書き換える際のチェックリスト、使える APIなどを公開しており、これらのドキュメントを把握する方が CPythonを書き換える上でははるかに効率的な方法、ということがわかりました。これを受けてチームとしてデバッガをいじるのではなく、ドキュメントを理解するのに注力するように方針転換することを余儀なくされました。手探るとはなんだったのか......。

いらない前置きが長くなりましたがこの節では読んだ公式ドキュメントとその内容を軽くまとめます。

Changing CPython’s Grammar

CPythonの文法を書き換える際にどのファイルを変更すれば良いかがチェックリスト形式でわかりやすく記載されています。

Compiler Design

CPython内部でソースコードからどうやってバイトコードが生成されるかの流れやオリジナルの新しいバイトコードを追加するにはどうすればよいかが丁寧に記述されています。基本的には Changing CPython’s Grammarでのチェックリストのそれぞれに対して具体的にどう変更すればよいかが記載されているものだと考えれば良いですが、バイトコード生成に関する説明が若干チェックリストでは大雑把なので、こちらを中心に確認すると良いです。内容としては、

当たりを追加で把握しておく必要がありました。

Guide to the Parser

端的に言えば ASTの生成規則いじるにはどうしたらいいですか？→Parser/python.gramを変更しましょう、ということが書かれています。python.gramの実際の文法（PEG）も書かれています。

Python/C API リファレンスマニュアル

実際にコードに新しい処理を追加する際に使える C APIが載っています。

試しに前置 incrementを追加してみる（written by しみだい）

前置 incrementとは、C言語で言うところの++iにあたるもので、機能としては、直後の変数(ここでは i)の値を1増やすというものです。
（C言語での使用例）

int i = 0;
++i;
printf("i = %d\n",i); // i = 1

（この章で実装できた Pythonでの使用例）

i = 0
++i       
print(i) ## 1

実際の実装手順としては、過去の先輩のブログを大いに参考にした上で、Pythonの ver間の際で生まれたバグを多少修正しました。

先述したチェックリストに倣いながら、変更点を順に記します。
Tokenの追加
（Grammer/Tokens, L. 56）

INCREMENT               '++'

++を塊として Tokenに追加することで、+(+a)と解釈されることを防いでいます。

Grammarで定義
（Grammer/python.gram, L. 674）

    | '++' a=NAME { _PyAST_UnaryOp(UInc, a, EXTRA) }

先ほど Tokenとして定義した++の場合についての処理を書いています。
++は変数に働く単項演算子 (UnaryOp) であるため、Grammarの中で単項演算子について記述のある L. 660~670の辺りを見てみると、既に存在する単項演算子の+, -, ~の例から、おそらく_PyAST_UnaryOpの第一引数が実際に Tokenに合わせ何の演算を行うのかを示していることがわかります。そのため、ここではインクリメントを UIncとして、既存の演算子に合わせて上のように++の定義を追加しました。

UIncを演算の一種として定義
（Parser/Python.asdl, L. 102）

    unaryop = Invert | Not | UAdd | USub | UInc

先ほど Grammar内の定義で使用した UIncが、単項演算子++に結びついた演算として ASTで認識されるように、Python.asdl内の該当部分の書き換えを行いました。

ここまででTokens,python.gram,Python.asdlの3ファイルを書き換えましたが、CPython はこれらのファイルに基づいて他のファイルが書き換えられる仕組みがあるため、中身を書き換えるたびに、それぞれmake regen-token,make regen-pegen,make regen-astのコマンドを用いて、自動的に書き換えられるファイルを再生成する必要があります。なお、これらをまとめて行ってくれるmake regen-allのコマンドが存在するため、何か変更を加えて再コンパイルする際は、make clean→make regen-all→make→make installを毎回行うようにするといいと思います。
(ただのmake installではエラーが出る場合があるので、その場合はsudo make installを試してみてください。)

ここまでで一度コンパイルを行い、Pythonを実行してインクリメントを行おうとすると、以下のようなエラーが出ると思います。

>>> i = 0
>>> ++i
SystemError: unary op 5 should not be possible

エラーを見る限り、5番目の unaryopに問題があるようです。先ほどPython.asdl内のunaryopにUIncを追加しましたが、これがまだ上手く認識されていないと考えられます。
そこで、プロジェクト内検索（Command + Shift + F）等で、他の単項演算子(例えば USub)を検索してみると、case文を用いて各単項演算子についての場合分けの処理を行なっている部分が、Python/ast_unparse.c内の L. 180~190辺り、及びPython/compile.c内の L. 3590~3600に存在することがわかります。
これらに UIncの場合を以下のように追加します。
（Python/ast_unparse.c, L. 189）

    case UInc: op = "++"; pr = PR_FACTOR; break;

（Python/compile.c, L. 3600）

    case UInc:
        return UNARY_INCREMENT;

再度コンパイルしてみましょう。初めのmake regen-allコマンドを実行すると、今度は以下のようなエラーが出てきます。

Python/compile.c:3601:16: error: use of undeclared identifier 'UNARY_INCREMENT'
        return UNARY_INCREMENT;
               ^
1 error generated.

先ほどcompile.c内に書いた、UNARY_INCREMENTの部分でエラーを吐いています。元から定義された単項演算子であるUNARY_NEGATIVEではエラーが出ていないため、先ほど同様にプロジェクト内検索を用いて検索してみます。そうすると、UNARY_NEGATIVEについてさらに以下のような記述が見つかるため、UNARY_INCREMENTについての記述を同様に追加する必要がありそうだとわかります。
（Python/compile.c, L. 975）

        /* Unary operators */
        case UNARY_POSITIVE:
        case UNARY_NEGATIVE:
        case UNARY_NOT:
        case UNARY_INVERT:
        case UNARY_INCREMENT:   // 追加部分
            return 0;

（Lib/opcode.py, L. 65）

def_op('UNARY_POSITIVE', 10)
def_op('UNARY_NEGATIVE', 11)
def_op('UNARY_NOT', 12)
def_op('UNARY_INCREMENT', 13) // 追加部分
def_op('UNARY_INVERT', 15)

（Python/ceval.c, L. 1950）

case TARGET(UNARY_NEGATIVE): {
            PyObject *value = TOP();
            PyObject *res = PyNumber_Negative(value);
            Py_DECREF(value);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
}
// 以下追加部分(中括弧内は後述)
case TARGET(UNARY_INCREMENT): {
           
}

なお、上に挙げた部分以外にも、いくつかのファイルでUNARY_NEGATIVEが検索に引っかかると思いますが、○○.rstは(おそらく)ただのドキュメントであり、opcode.hはopcode.pyに合わせてコンパイル(make regen-all)時に自動で書き変わるため触れておらず、test_〇〇.pyはPythonが正常に動作するかの testファイルであるため、新たに書き換える必要はありません。
（追記）
Pythonの公式ドキュメント曰く、

Once the name/number pair has been chosen and entered in Lib/opcode.py, you must also enter it into Doc/library/dis.rst, and regenerate Include/opcode.h and Python/opcode_targets.h by running make regen-opcode regen-opcode-targets.

とのことなので、一応dis.rstも次のように書き足します。
（Doc/library/dis.rst, L. 397）

.. opcode:: UNARY_INCREMENT

   Implements ``TOS = ++TOS``.

ここまでで再度コンパイルを行うと無事にコンパイルが完了し、Pythonを実行してインクリメントを行おうとすると、今度は以下のようなエラーが出ます。

>>> i = 0
>>> ++i
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for ** or pow(): 'bytes' and 'int'

なにやらよくわからないエラーですが、とりあえずコンパイルには成功しました。
ここまでで下準備が完了し、次からいよいよ前置インクリメントの機能的な実装となります。機能としては、主に数値を1増やすことと、増やした後の値を新しい値として保存することが必要です。

まずは前者の数値を1増やすという部分について実装していきます。
（ceval.c内の先ほど記述した箇所について再掲）

case TARGET(UNARY_NEGATIVE): {
            PyObject *value = TOP();
            PyObject *res = PyNumber_Negative(value);
            Py_DECREF(value);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
}

UNARY_NEGATIVEの場合に行なっていることを順に見ていくと、スタックから POP→値の符号を変える→スタックに戻すという流れが見て取れます。これに倣って、UNARY_INCREMENTを記述したものが以下のものです。

        case TARGET(UNARY_INCREMENT): {
            PyObject *value = TOP();
            PyObject *inv = PyNumber_Invert(value);
            PyObject *res = PyNumber_Negative(inv);
            Py_DECREF(value);
            Py_DECREF(inv);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

i + 1 == -(~i)であることを利用すると、上の記述で値に1を足すことができていることがわかります。
改めてコンパイルを行い実行すると、以下の出力を得ます。

>>> i = 0
>>> ++i
1
>>> print(i)
0

3行目で1が足された出力がしっかりと出ていますが、再度iをprintすると元の0に戻ってしまっています。よって、最初に述べた通り、増やした後の値を新しく保存することが必要となります。

そのため、次に、値の保存について実装していきます。
ここの部分に関しては、自分の理解が及ばず、過去の先輩が書いてくださった解説以上に書けることがないため、該当の部分を引用させていただきます。
（Python/compile.c, L.5207）

case UnaryOp_kind:
        if(e->v.UnaryOp.op==UInc){
            VISIT(c, expr, e->v.UnaryOp.operand);
            ADDOP(c, unaryop(e->v.UnaryOp.op));
            ADDOP(c, DUP_TOP);
            assert(e->v.UnaryOp.operand->kind==Name_kind);
            compiler_nameop(c,e->v.UnaryOp.operand->v.Name.id,Store);
        } else {
            VISIT(c, expr, e->v.UnaryOp.operand);
            ADDOP(c, unaryop(e->v.UnaryOp.op));
        }
        break;

最初の2文は他の単行演算子と同様です。スタックの一番上に＋1された後の値が積まれているのでそれをADDOPで複製、一番上をプッシュして値を更新します。

if文により、演算子がインクリメントの場合とそれ以外の場合とで分けています(正直、どこからcompiler_nameop等を見つけてきたのかよくわからない)。

ともかく、これで再度コンパイルを行い実行すると、以下の出力を得ることができます。

>>> i = 0
>>> ++i
1
>>> print(i)
1

これにて、目的の出力を得ることができました。

nand, nor, xnorの追加（written by しみだい）

Pythonには bit演算子として and&, or|, xor^の3種類がありますが、ここでは nand~&, nor~|, xnor~^を新たに実装しました。
先ほどと同様に、順に実装していきます。

Tokenの追加
（Grammer/Tokens, L. 57）

NAND                    '~&'
NOR                     '~|'
XNOR                    '~^'

インクリメントの時と同様に、これらの演算子が塊として認識されるようにTokenを追加します。

Grammarで定義
（Grammer/python.gram, L. 637）

bitwise_or[expr_ty]:
    | a=bitwise_or '|' b=bitwise_xor { _PyAST_BinOp(a, BitOr, b, EXTRA) }
    | a=bitwise_or '~|' b=bitwise_xor { _PyAST_BinOp(a, BitNor, b, EXTRA) }   // 追加部分
    | bitwise_xor
bitwise_xor[expr_ty]:
    | a=bitwise_xor '^' b=bitwise_and { _PyAST_BinOp(a, BitXor, b, EXTRA) }
    | a=bitwise_xor '~^' b=bitwise_and { _PyAST_BinOp(a, BitXnor, b, EXTRA) }   // 追加部分
    | bitwise_and
bitwise_and[expr_ty]:
    | a=bitwise_and '&' b=shift_expr{ _PyAST_BinOp(a, BitAnd, b, EXTRA) }
    | a=bitwise_and '~&' b=shift_expr { _PyAST_BinOp(a, BitNand, b, EXTRA) }   // 追加部分
    | shift_expr

Grammar内で上に挙げた bit演算子が定義されている部分を探し、新たに追加する nand, nor, xnorについて、先ほど定義したトークンを用いて記述します。ここで、関数_PyAST_BinOp内のBitNor, BitXnor, BitNandは新たに作ったものであることに注意してください。

BitNor, BitXnor, BitNandを二項演算の一種として定義
（Parser/Python.asdl, L. 100）

operator = Add | Sub | Mult | MatMult | Div | Mod | Pow | LShift
                 | RShift | BitOr | BitXor | BitAnd | BitNand | BitNor | BitXnor | FloorDiv

先ほどGrammar内で使用したBitNor, BitXnor, BitNandが、二項演算子として認識されるように書き足しました。
次に、インクリメントの場合と同じように、ast_unparse.cとcompile.c、及びopcode.pyの書き換えを行います。
（Python/ast_unparse.c, L. 162）

    case BitOr: op = " | "; pr = PR_BOR; break;
    case BitNor: op = " ~| "; pr = PR_BNOR; break; // 追加部分
    case BitXor: op = " ^ "; pr = PR_BXOR; break;
    case BitXnor: op = " ~^ "; pr = PR_BXNOR; break; // 追加部分
    case BitAnd: op = " & "; pr = PR_BAND; break;
    case BitNand: op = " ~& "; pr = PR_BNAND; break; // 追加部分
    case FloorDiv: op = " // "; pr = PR_TERM; break;
    case Pow: op = " ** "; pr = PR_POWER; rassoc = true; break;
    default:

ここで、新しくPR_BNOR, PR_BXNOR, PR_BNANDを使用したので、他の bit演算子の場合を参考にこれらが定義されるべき場所を探すと、同じくast_unparse.c内にその記述が見つかるため、次のように書き足します。
（Python/ast_unparse.c, L. 109）

    PR_BOR = PR_EXPR,   /* '|' */
    PR_BNOR,            /* '~| */  // 追加部分
    PR_BXOR,            /* '^' */
    PR_BXNOR,           /* '~^'*/  // 追加部分
    PR_BAND,            /* '&' */
    PR_BNAND,           /* '~&' */  // 追加部分

compile.c、及びopcode.pyについては、以下の通りです。
（Python/compile.c, L. 1017）

        case BINARY_AND:
        case BINARY_XOR:
        case BINARY_OR:
        case BINARY_NAND: // 追加部分
        case BINARY_NOR:    // 追加部分
        case BINARY_XNOR:  // 追加部分
            return -1;

（Python/compile.c, L. 3635）

    case BitOr:
        return BINARY_OR;
    case BitXor:
        return BINARY_XOR;
    case BitAnd:
        return BINARY_AND;
    case BitNand:         // ここから追加部分
        return BINARY_NAND;
    case BitNor:
        return BINARY_NOR;
    case BitXnor:
        return BINARY_XNOR;    // ここまで追加部分

（Lib/opcode.py, L. 222）

def_op('BINARY_NAND', 166)
def_op('BINARY_NOR', 167)
def_op('BINARY_XNOR', 168)

ここでopcode.pyを書き換えたので、dis.rstに以下のように書き足しておきます。
（Doc/library/dis.rst, L. 493）

.. opcode:: BINARY_NAND

   Implements ``TOS = TOS1 ~& TOS``.


.. opcode:: BINARY_XNOR

   Implements ``TOS = TOS1 ~^ TOS``.


.. opcode:: BINARY_NOR

   Implements ``TOS = TOS1 ~| TOS``.

インクリメントの場合は、この後compile.cとceval.cの両方を書き換えて実際の機能を実装しましたが、nand, nor, xnorの場合は、他の bit演算子と比較して追加で行うことがなく、ceval.c内の一部の計算処理が異なるのみであるので、compile.cに関しては変更しません。

最後にceval.cの書き換えについて、BINARY_ANDの場合を見てみると、以下のように記述があります。
（Python/ceval.c, L. 2158）

        case TARGET(BINARY_AND): {
            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_And(left, right);
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

これを基に、BINARY_NAND, BINARY_NOR, BINARY_XNORの場合を次のように書き足します。
（Python/ceval.c, L. 2194）

        case TARGET(BINARY_NAND): {

            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_Invert(PyNumber_And(left, right));

            Py_DECREF(left); 
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();

        }

        case TARGET(BINARY_NOR): {

            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_Invert(PyNumber_Or(left, right));

            Py_DECREF(left); 
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();

        }

        case TARGET(BINARY_XNOR): {

            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_Invert(PyNumber_Xor(left, right));

            Py_DECREF(left); 
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();

        }

初めのインクリメントと同じようにここまで実装を行なってきました。

実際にコンパイルを行うと次のような warningが出ます。

Python/ast_opt.c: In function ‘fold_binop’:
Python/ast_opt.c:241:5: warning: enumeration value ‘BitNand’ not handled in switch [-Wswitch]
  241 |     switch (node->v.BinOp.op) {
      |     ^~~~~~
Python/ast_opt.c:241:5: warning: enumeration value ‘BitNor’ not handled in switch [-Wswitch]
Python/ast_opt.c:241:5: warning: enumeration value ‘BitXnor’ not handled in switch [-Wswitch]

怒られてはいるけれどコンパイルは通るので正直微妙なところですが、一応Python/ast_opt.cなるファイルを覗いてみると次のような記述があります。
（Python/ast_opt.c, L. 1, 269）

/* AST Optimizer */
// （中略）
    case BitOr:
        newval = PyNumber_Or(lv, rv);
        break;
    case BitXor:
        newval = PyNumber_Xor(lv, rv);
        break;
    case BitAnd:
        newval = PyNumber_And(lv, rv);
        break;

AST Optimizerと書かれていますし ASTを作るときになんらかの最適化を施すのに必要なのでしょうか？書かれてることは単純なのでとりあえず下のように追加で記述します。
（Python/ast_opt.c, L. 278）

    case BitNand:
        newval = PyNumber_Invert(PyNumber_And(lv, rv));
        break;
    case BitNor:
        newval = PyNumber_Invert(PyNumber_Or(lv, rv));
        break;
    case BitXnor:
        newval = PyNumber_Invert(PyNumber_Xor(lv, rv));
        break;

再度コンパイルしてみると warningが消えています。
実行してみると、以下の出力を得ます。

>>> a = 2          // a = 0010
>>> b = 5          // b = 0101 
>>> a ~& b       //  a ~& b = 1111 (-1)
-1
>>> a ~| b         // a ~| b = 1000 (-8)
-8
>>> a ~^ b       // a ~^ b = 1000 (-8)
-8

よって確かに、目的の機能が実装できています。

in-place演算子の追加（written by モグリン）

in-place演算子とは+=, -=みたいなやつのことです、ここでは nand, nor, xnor の in-place演算子、すなわち~&=, ~|=, ~^=を追加することにします（演算子が長すぎて見た目が気持ち悪い）。とりあえず Tokenを追加します。
（Grammer/Tokens, L. 60）

NANDEQUAL               '~&='
NOREQUAL                '~|='
XNOREQUAL               '~^='

次にGrammer/python.gramで文法を追加するところを探ります、同じ in-place演算子の+=で検索すると無事 in-place演算子のまとまっているそれらしき箇所が発見できるので書き加えます。
（Grammer/python.gram, L. 109）

augassign[AugOperator*]:
    | '+=' { _PyPegen_augoperator(p, Add) }
    | '-=' { _PyPegen_augoperator(p, Sub) }
    | '*=' { _PyPegen_augoperator(p, Mult) }
    | '@=' { CHECK_VERSION(AugOperator*, 5, "The '@' operator is", _PyPegen_augoperator(p, MatMult)) }
    | '/=' { _PyPegen_augoperator(p, Div) }
    | '%=' { _PyPegen_augoperator(p, Mod) }
    | '~&=' { _PyPegen_augoperator(p, BitNand) } # 追加箇所
    | '&=' { _PyPegen_augoperator(p, BitAnd) }
    | '~|=' { _PyPegen_augoperator(p, BitNor) } # 追加箇所
    | '|=' { _PyPegen_augoperator(p, BitOr) }
    | '~^=' { _PyPegen_augoperator(p, BitXnor) } # 追加箇所
    | '^=' { _PyPegen_augoperator(p, BitXor) }
    | '<<=' { _PyPegen_augoperator(p, LShift) }
    | '>>=' { _PyPegen_augoperator(p, RShift) }
    | '**=' { _PyPegen_augoperator(p, Pow) }
    | '//=' { _PyPegen_augoperator(p, FloorDiv) }

ところでコード中のBitNand, BitNor, BitXnorは既に先ほど nand, nor, xnorを追加した時に宣言したものです、ということはもしかして in-place演算子は二項演算子の定義さえしっかりされて言えば文法書き換えだけで勝手にやってくれる！？、と思いmake regen-all, make, make installを試しに実行する（以降、まとめてコンパイルする、と呼ぶことにします）と、なんとちゃんとコンパイルされます。実際に Pythonで定義した in-place演算子を使用してみましょう。

$ home/Python/bin/python3
Python 3.10.7 (main, Nov  7 2022, 05:41:45) [GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> a = 123
>>> a ~&= 456
SystemError: inplace binary op 13 should not be possible

流石にそこまでうまい話ではなかったようです。エラー文を見ると inplace binary opなるものの13番目が使用不可であると読み取れますが、これはおそらくParser/python.asdlで先ほど宣言したoperatorに対応しているのでしょう、実際戻って確かめてみるとBitNandは13番目に宣言されています。
ただ、普通の~&が動く以上、これそのものが使用不可であるはずがありません、考えられるのは in-place演算子では何か別の処理を書き加えなければならないということでしょう、そこで Changing CPython’s Grammarに従って順番に変更する可能性のあるファイルを探っていきます。当たりとしては+=も二項演算子+と同じオペコード、Addを使っているのに動いている以上、どこかで辻褄を合わせる処理を行っているはずなのでそこを見つけることを目指します。すると、Python/compile.cに次のような記述が見つかります。
（Python/compile.c, L. 3656）

static int
inplace_binop(operator_ty op)
{
    switch (op) {
    case Add:
        return INPLACE_ADD;
    case Sub:
        return INPLACE_SUBTRACT;
    case Mult:
        return INPLACE_MULTIPLY;
    case MatMult:
        return INPLACE_MATRIX_MULTIPLY;
    case Div:
        return INPLACE_TRUE_DIVIDE;
    case Mod:
        return INPLACE_MODULO;
    case Pow:
        return INPLACE_POWER;
    case LShift:
        return INPLACE_LSHIFT;
    case RShift:
        return INPLACE_RSHIFT;
    case BitOr:
        return INPLACE_OR;
    case BitXor:
        return INPLACE_XOR;
    case BitAnd:
        return INPLACE_AND;
    case FloorDiv:
        return INPLACE_FLOOR_DIVIDE;
    default:
        PyErr_Format(PyExc_SystemError,
            "inplace binary op %d should not be possible", op);
        return 0;
    }
}

ビンゴですね、ここで同じオペコードでも in-place演算子による処理を分けていたのだとわかるので、ここに手を加えれば良いことがわかります。
ところでここで返り値に指定されているINPLACE_ADD、処理が分かれているのでバイトコードのオペレーションを書かなければいけないのは自明として（やりたくない）、Python/compile.c内で他に書かなければいけないところはないでしょうか。
あと、Addを追う最中に気付きました。単純なことですが同じ bit演算子である&=（オペコードはBitAnd）の方がより現在の書きたい処理に近い気がするのでここからはこれを追います。
戻って Python/compile.c内でBitAndの in-placeオペコード、INPLACE_AND（上のコード参照）で検索を書けると次の部分がヒットします。
（Python/compile.c, L. 955, 1033）

static int
stack_effect(int opcode, int oparg, int jump)
{
    switch (opcode) {
        // （中略）
        case INPLACE_LSHIFT:
        case INPLACE_RSHIFT:
        case INPLACE_AND:
        case INPLACE_XOR:
        case INPLACE_OR:
            return -1;
        // （中略）
    }
    return PY_INVALID_STACK_EFFECT; /* not reachable */
}

明らかにそれっぽいところを見つけたのでここに追加すれば良いのでしょう（そういえば Compiler Designで

you need to introduce the use of the new bytecode. Altering Python/compile.c and Python/ceval.c will be the primary places to change. You must add the case for a new opcode into the ‘switch’ statement in the stack_effect() function in Python/compile.c.

って書いてたな）。よって変更点はまとめると次のようになります。
（Python/compile.c, L. 35）

        case INPLACE_AND:
        case INPLACE_XOR:
        case INPLACE_OR:
        case INPLACE_NAND: // 追加箇所
        case INPLACE_XNOR: // 追加箇所
        case INPLACE_NOR: // 追加箇所
            return -1;

（Python/compile.c, L. 3678）

    case BitOr:
        return INPLACE_OR;
    case BitXor:
        return INPLACE_XOR;
    case BitAnd:
        return INPLACE_AND;

   // 以下追加箇所
    case BitNor:
        return INPLACE_NOR;
    case BitXnor:
        return INPLACE_XNOR;
    case BitNand:
        return INPLACE_NAND;

よし、後は追加したオペコードに対応するバイトコードのオペレーションをPython/ceval.cに追加すれば良いはず、ceval.cでINPLACE_ANDの検索をかけると、該当コードが見つかります。
（Python/ceval.c, L. 2390）

        case TARGET(INPLACE_AND): {
            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_InPlaceAnd(left, right);
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

        case TARGET(INPLACE_XOR): {
            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_InPlaceXor(left, right);
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

        case TARGET(INPLACE_OR): {
            PyObject *right = POP();
            PyObject *left = TOP();
            PyObject *res = PyNumber_InPlaceOr(left, right);
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

後はこれらを参考にしてコードを書けば......、と思ったのですがここで問題が発生します。上記のオペレーションはどれも C API（PyNumber_InPlace*）を用いて実装されていることがわかりますが、これから実装しようとしている nand, nor, xnorはそれだと一筋縄ではいきません。試しにPython/C API リファレンスマニュアルでPyNumber_InPlaceInvertとかがないかな～、と思って探してみますがそれっぽいものは見つかりません、in-place単項演算子ってわけわからないしそれはそう。
ここで解決策としては大きく3つが考えられます。

  • C APIがどのように実装されているのかを調べ同様の C APIを自分で追加する（PyNumber_InPlaceNandなど）。
  • インクリメントの処理を思い出しPython/compile.cに STORE処理を追加する。
  • なんとかPython/ceval.cを書き換える形のまま頑張る。

本当は1番目の方針が良いのでしょうが実験の期限を考えて今回は3番目の選択肢で行こうと思います、決して面倒だったわけではない。
結局以下の形で実装しました。
（Python/ceval.c, L. 2426）

        case TARGET(INPLACE_NAND): {
            PyObject *right = POP();
            PyObject *left = TOP();
            // ~(a&b) = (~a)|(~b)
            PyObject *res = PyNumber_InPlaceOr(PyNumber_Invert(left),PyNumber_Invert(right));
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

        case TARGET(INPLACE_XNOR): {
            PyObject *right = POP();
            PyObject *left = TOP();
            // ~(a^b) = (a&b)|((~a)&(~b))
            PyObject *res = PyNumber_InPlaceOr(PyNumber_And(left,right),
                                               PyNumber_And(PyNumber_Invert(left),PyNumber_Invert(right)));
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

        case TARGET(INPLACE_NOR): {
            PyObject *right = POP();
            PyObject *left = TOP();
            // ~(a|b) = (~a)&(~b)
            PyObject *res = PyNumber_InPlaceAnd(PyNumber_Invert(left),PyNumber_Invert(right));
            Py_DECREF(left);
            Py_DECREF(right);
            SET_TOP(res);
            if (res == NULL)
                goto error;
            DISPATCH();
        }

端的に言えば各演算子を読み替えて既存の C APIを使える形で実装しました、時間がある時に C APIを書き加える実装もしてみたいです。
さあ、これで動くはずです、いざコンパイル！

$ make regen-all
# （中略）
Python/ceval.c: In function ‘_PyEval_EvalFrameDefault’:
Python/ceval.c:2426:21: error: ‘INPLACE_NAND’ undeclared (first use in this function); did you mean ‘INPLACE_AND’?
 2426 |         case TARGET(INPLACE_NAND): {
      |                     ^~~~~~~~~~~~
Python/ceval.c:1299:20: note: in definition of macro ‘TARGET’
 1299 | #define TARGET(op) op: TARGET_##op
      |                    ^~
Python/ceval.c:2426:21: note: each undeclared identifier is reported only once for each function it appears in
 2426 |         case TARGET(INPLACE_NAND): {
      |                     ^~~~~~~~~~~~
Python/ceval.c:1299:20: note: in definition of macro ‘TARGET’
 1299 | #define TARGET(op) op: TARGET_##op
      |                    ^~
Python/ceval.c:2439:21: error: ‘INPLACE_XNOR’ undeclared (first use in this function); did you mean ‘INPLACE_XOR’?
 2439 |         case TARGET(INPLACE_XNOR): {
      |                     ^~~~~~~~~~~~
Python/ceval.c:1299:20: note: in definition of macro ‘TARGET’
 1299 | #define TARGET(op) op: TARGET_##op
      |                    ^~
Python/ceval.c:2453:21: error: ‘INPLACE_NOR’ undeclared (first use in this function); did you mean ‘INPLACE_XOR’?
 2453 |         case TARGET(INPLACE_NOR): {
      |                     ^~~~~~~~~~~
------

Why ?、なんか追加したオペコードが定義されてないのに使われてるみたいに書かれてるけどオペコードとかオペレーションで定義されるものだろ（多分）、どういうことだ。私は完璧なコードを書いたはずだぞ。
脳が怒りで沸騰しそうになりますが冷静に原因を考えましょう、この場合、どこか追加しなければいけないところが追加されてないが故のエラーであると考えるのが自然です。じゃあさっき追ってたINPLACE_ANDを今度はプロジェクト内全検索してみて書き加える場所を探してみましょう。

箸より使った Ctrl + Shift + F

......あっ

First, you must choose a name and a unique identifier number. The official list of bytecode can be found in Lib/opcode.py. If the opcode is to take an argument, it must be given a unique number greater than that assigned to HAVE_ARGUMENT (as found in Lib/opcode.py).


Once the name/number pair has been chosen and entered in Lib/opcode.py, you must also enter it into Doc/library/dis.rst, and regenerate Include/opcode.h and Python/opcode_targets.h by running make regen-opcode regen-opcode-targets.


Compiler Design「Introducing New Bytecode」より

新しいオペコード追加したら Lib/opcode.pyにオペコードを追加する、忘れてた......。というわけで以下のコードを追加します。
（Lib/opcode.py, L. 226）

def_op('INPLACE_NAND', 171)
def_op('INPLACE_XNOR', 172)
def_op('INPLACE_NOR', 173)

（Doc/library/dis.rst, L. 582）

.. opcode:: INPLACE_NAND

   Implements in-place ``TOS = TOS1 ~& TOS``.


.. opcode:: INPLACE_NOR

   Implements in-place ``TOS = TOS1 ~| TOS``.


.. opcode:: INPLACE_XNOR

   Implements in-place ``TOS = TOS1 ~^ TOS``.

追加したら再コンパイルすると、無事に通ります。本当に機能が追加されてるか実験してみましょう。

$ home/Python/bin/python3
Python 3.10.7 (main, Nov  9 2022, 11:38:34) [GCC 11.2.0] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> ~(123 & 456)
-73
>>> a = 123
>>> a ~&= 456
>>> a
-73
>>> ~(123 | 456)
-508
>>> a = 123
>>> a ~|= 456
>>> a
-508
>>> ~(123 ^ 456)
-436
>>> a = 123
>>> a ~^= 456
>>> a
-436

しっかりと意図通りの挙動をしていることが確認できますね、これにて新規に追加した bit演算子に対応する in-place演算子の追加は終わりです、ふい～、長かった。

論理 xor演算子の追加（written by しみだい）

最後に、bool演算としての xorの実装を行いました。ただし、xorは既に組み込まれているxor(a, b)と競合するため、代わりに bxorとしています。
機能としては、以下のようなものを想定しています。

>>> True bxor True
False
>>> True bxor False
True
>>> False bxor True
True
>>> False bxor False
False

今回も、インクリメントの実装に沿って行なっていきます。
ただし、bit演算子や and, orのような二項演算子ではなく、==や>といった比較演算子として、定義していきます。初めは and, orと同じように実装していこうと思ったのですが、作業を進めていくと、and, orと xorの間では実装面で大きな違いがあることが判明したので、比較演算子側から実装を行なっています。その大きな違いについて説明すると、まず and(or)に関しては、A and B and ... のように複数連なっている場合、頭から順に見ていって途中に一つでもFalse(True)があれば、全体としてFalse(True)だと判断することができます。しかし、xorについては、A xor B xor ...とあったときに、A, B, ...の全てのTrue or Falseを見るまでは、全体としてTrueなのかFalseなのかの判断ができません。これが、andや arと xorで、全く違う実装が必要となる理由です。


Tokenの追加
今回、演算子としてbxorという文字列を使用しているため、Tokenの追加は必要ありません。(既にあるnot, and, inなどもTokenに含まれていない。)

Grammarで定義
比較演算子について定義されているところをpython.gramで探すと、eq==や、lt<といった記述が L. 620~640近辺で見つかります。既にある演算子を参考にし、次のように書き換えます。
（Grammar/python.gram, L. 617）

compare_op_bitwise_or_pair[CmpopExprPair*]:
    | eq_bitwise_or
    | noteq_bitwise_or
    | boolxor_bitwise_or  // 追加部分
    | lte_bitwise_or
    | lt_bitwise_or
    | gte_bitwise_or
    | gt_bitwise_or
    | notin_bitwise_or
    | in_bitwise_or
    | isnot_bitwise_or
    | is_bitwise_or
eq_bitwise_or[CmpopExprPair*]: '==' a=bitwise_or { _PyPegen_cmpop_expr_pair(p, Eq, a) }
noteq_bitwise_or[CmpopExprPair*]:
    | (tok='!=' { _PyPegen_check_barry_as_flufl(p, tok) ? NULL : tok}) a=bitwise_or {_PyPegen_cmpop_expr_pair(p, NotEq, a) }
boolxor_bitwise_or[CmpopExprPair*]: 'bxor' a=bitwise_or { _PyPegen_cmpop_expr_pair(p, Boolxor, a) } // 追加部分
lte_bitwise_or[CmpopExprPair*]: '<=' a=bitwise_or { _PyPegen_cmpop_expr_pair(p, LtE, a) }
lt_bitwise_or[CmpopExprPair*]: '<' a=bitwise_or { _PyPegen_cmpop_expr_pair(p, Lt, a) }

ここで、関数内でBoolxorを独自に使用したため、Python.asdlの方に、Boolxorを追加します。
（Parser/Python.asdl, L. 104）

    cmpop = Eq | NotEq | Lt | LtE | Gt | GtE | Is | IsNot | In | NotIn | Boolxor

次に、ここで追加したBoolxorがcase文の分岐に含まれるように、ast_unparse.cとcompile.cに次のように書き足します。
（Python/ast_unparse.c, L. 488）

        case Boolxor:
            op = " bxor ";
            break;

（Python/compile.c, L. 2614）

    case Boolxor:
        cmp = Py_XOR;
        break;

ここで、Py_XORを使用したため、既にある演算子に対応したPy_EQなどの定義元を探すと、object.hで定義されていることがわかるので、次のように書き足します。
（Include/object.h, L. 625）

/* Rich comparison opcodes */
#define Py_LT 0
#define Py_LE 1
#define Py_EQ 2
#define Py_NE 3
#define Py_GT 4
#define Py_GE 5
#define Py_XOR 6  // 追加部分

あとは比較が実際に行われているところを見つけ出し、xorの場合を書き足すだけです。Py_LTなどで検索を行うと、かなり多くのファイルが検索に引っかかりますが、〇〇object.cや〇〇module.cは各オブジェクトについての比較を行うファイルであり、xorでは bool型に絞って演算を行うため、関係ないと考えられます。そうして、関係がありそうなファイルをobject.cに絞ることができました。以下に、その記述を示します。
（Objects/object.c, L. 728）

PyObject *
PyObject_RichCompare(PyObject *v, PyObject *w, int op)
{
    PyThreadState *tstate = _PyThreadState_GET();

    assert(Py_LT <= op && op <= Py_XOR);  // 変更箇所,元々はPy_XORの部分がPy_GEだった
    if (v == NULL || w == NULL) {
        if (!_PyErr_Occurred(tstate)) {
            PyErr_BadInternalCall();
        }
        return NULL;
    }
    if (_Py_EnterRecursiveCall(tstate, " in comparison")) {
        return NULL;
    }
    PyObject *res = do_richcompare(tstate, v, w, op);
    _Py_LeaveRecursiveCall(tstate);
    return res;
}

assert文について、opがPy_LTからPy_GEに限られてしまっているため、Py_GEの部分をPy_XORに書き換えます。これで、Py_XORが認識されるようになりました。

次に、メインの比較をおこなっている部分である、do_richcompare関数を見ていくのですが、ここでデバッガが活躍します。（満を持しての登場）

do_richcompare関数は以下のように記述されており、少し見ただけではどこで比較をおこなっているのかがわかりずらいです。
（Objects/object.c, L. 676）

static PyObject *
do_richcompare(PyThreadState *tstate, PyObject *v, PyObject *w, int op)
{
    richcmpfunc f;
    PyObject *res;
    int checked_reverse_op = 0;

    if (!Py_IS_TYPE(v, Py_TYPE(w)) &&
        PyType_IsSubtype(Py_TYPE(w), Py_TYPE(v)) &&
        (f = Py_TYPE(w)->tp_richcompare) != NULL) {
        checked_reverse_op = 1;
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if ((f = Py_TYPE(v)->tp_richcompare) != NULL) {
        res = (*f)(v, w, op);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    if (!checked_reverse_op && (f = Py_TYPE(w)->tp_richcompare) != NULL) {
        res = (*f)(w, v, _Py_SwappedOp[op]);
        if (res != Py_NotImplemented)
            return res;
        Py_DECREF(res);
    }
    /* If neither object implements it, provide a sensible default
       for == and !=, but raise an exception for ordering. */
    switch (op) {
    case Py_EQ:
        res = (v == w) ? Py_True : Py_False;
        break;
    case Py_NE:
        res = (v != w) ? Py_True : Py_False;
        break;
    default:
        _PyErr_Format(tstate, PyExc_TypeError,
                      "'%s' not supported between instances of '%.100s' and '%.100s'",
                      opstrings[op],
                      Py_TYPE(v)->tp_name,
                      Py_TYPE(w)->tp_name);
        return NULL;
    }
    Py_INCREF(res);
    return res;
}

そのため、適当にTrue == Trueなどを入力としてデバッガを動かしてみることで、3つあるif文の中の2番目の分岐に入り、res = (*f)(v, w, op)によって、真偽値が返ってきていることがわかりました。この関数ポインタが、v, wを入力として受け取り、演算子opを適用して、真偽値を返しているようです。実際に演算を行っているところが判明したため、次のような実装を行いました。
（上の二番目のif文内を次のように書き換え）

    if ((f = Py_TYPE(v)->tp_richcompare) != NULL) {
        if(op == Py_XOR){
            PyObject *v_bool, *w_bool;
            if(PyLong_Check(v)){
                if (PyLong_AsLong(v) == 0){
                    v_bool = Py_False;
                }
                else{
                    v_bool = Py_True;
                }
            }
            if(PyLong_Check(w)){
                if (PyLong_AsLong(w) == 0){
                    w_bool = Py_False;
                }
                else{
                    w_bool = Py_True;
                }
            }
            if(PyBool_Check(v)){
                v_bool = v;
            }
            if(PyBool_Check(w)){
                w_bool = w;
            }
            if (PyBool_Check(v_bool) & PyBool_Check(w_bool)){
                if ((v_bool == Py_True) ^ (w_bool == Py_True)){
                    res = Py_True;
                }
                else {
                    res = Py_False;
                }
            }
            Py_DECREF(v_bool);
            Py_DECREF(w_bool);
        } else {
        res = (*f)(v, w, op);
        }
   }

条件分岐を用いて、演算子がXORの時のみ直接的な処理を行い、それ以外の時は今まで通りに関数ポインタを用いるようにしました。CPythonの内部では、オブジェクトは全てPyObject、真偽値はPy_True及びPy_Falseを用いているため、上のように記述しています。Pythonの元々の仕様として、整数型をbool型として認識する場合0のみFalseを返し、それ以外の非零整数はTrueを返すため、それに合わせて、入力v, wが整数型及びbool型の場合のみ、True or Falseとして認識するようにしました。
また、CPythonでは、参照カウンタと呼ばれるものを用いてガベージコレクションを行っているため、Py_DECREF及びPy_INCREFによって、参照カウンタの値を変更する必要があります。詳しいことは僕自身あまりわかっていないですが、新しく作成した変数を使い終わったタイミングで、Py_DECREFを行なってあげることでうまくいきます。(これを行わなかった場合、Pythonが終了するタイミングでメモリ管理に何か問題が生じ、free()によるエラーが起こります。)

これで、演算子がXORの場合についても真偽値を返すようになったので、再コンパイルし実行すると、目的の出力が得られます。

>>> True bxor True
False
>>> True bxor False
True
>>> False bxor True
True
>>> False bxor False
False

その他の細かい注意点

自動生成が壊れることがある。（written by モグリン）

未だに原因は不明ですがParser/parser.cやInclude/opcode.hのように設定ファイルから自動生成されるファイルはたまにParser/parser.new.c, Include/opcode.h.newのように .newの混じる異なるファイル名として生成されることがあります。当然このままではmake *のどれかで詰まってコンパイルできません。対処法としては地味ですがファイル名検索（Ctrl + P）で .newで調べてヒットしたやつのファイル名から .newを消した後もう一度コンパイルしてました。
（追記）
実験後に判明しましたがこれ恐らく regenerateされるファイル類をまとめて.gitignoreで追跡しないようにしていたせいで起こったバグっぽいです。コンパイルで初めて生成されるファイルはまだしも自動で変更されただけのファイルは.gitigonoreに追加しないのが賢明でしょう。

gdbの挙動が怪しい（written by モグリン）

VSCodeではデバッガが動いている最中に指定した変数（配列も含む）の中身を参照しながらステップを進めることが出来るのですが、ブレークポイントを置いてそこまで一気に飛んだ時とステップごとに実行した時で変数の中身が異なることがありました。また、ステップごとに実行しようとしたのにいきなりブレークポイントまで飛ぶことも結構ありました。これらの原因や解決法は未だにわかっていません。私のチームは実験4日目にしてデバッガを実質的に使わなくなったのであまりこれといった問題はありませんでしたがデバッガを頻繁に活用するときはご注意を......。

参考