defaultdict について実装を見てみた

# はじめに
組み込み collections モジュールで定義されている defaultdict の第一引数には **default_factory** を指定します。これは通例、辞書型の値 (のデフォルト値) を生成する関数になります。

これに対して [Effective Python 第2版 ―Pythonプログラムを改良する90項目](https://www.amazon.co.jp/dp/4873119170) の項目38「単純なインタフェースにはクラスの代わりに関数を使う」において以下のような記述がありました。

> キーが見つからないとログを取り、デフォルト値として0を返すフックを次のように定義します。
> ...
> 初期状態の辞書と追加データ集合を指定すると、この log_missing 関数が実行されます。

これは、その default_factory として任意の関数を渡すことを意味しています。これは一体どうなっているのだろうと思い、defaultdict の実装を見ることにしました。

# 前提
以降の話は [Python 3.10.0](https://github.com/python/cpython/tree/v3.10.0) を前提とします。3 系であればそれほど大きな差異はないと思いますが。

# ソースコードを見てみる
defaultdict は [Modules/_collectionsmodule.c](https://github.com/python/cpython/blob/v3.10.0/Modules/_collectionsmodule.c) に定義されています。

## オブジェクトの初期化
Python の Class コンストラクタである \_\_init\_\_() に相当する関数は **defdict_init** であることがわかります([tp_initの部分](https://github.com/python/cpython/blob/v3.10.0/Modules/_collectionsmodule.c#L2289))。

```c:Modules/_collectionsmodule.c
            newdefault = PyTuple_GET_ITEM(args, 0);
            if (!PyCallable_Check(newdefault) && newdefault != Py_None) {
                PyErr_SetString(PyExc_TypeError,
                    "first argument must be callable or None");
                return -1;
            }
...(snip)...
    Py_XINCREF(newdefault);
    dd->default_factory = newdefault;
```

defaultdict の引数は順序引数 args に収まっているので、一番目の引数は newdefault として取り出されます。そして **PyCallable_Check()** によってそれが呼び出し可能かどうかがチェックされます。つまり default_factory は呼び出し可能なものであればなんでもいいということになります。その後 newdefault の値 (正確にはアドレス) は defdictobject 構造体の default_factory メンバに代入されています。

因みに newdefault は PyObject 型の構造体ですが、Py_XINCREF() によって ob_refcnt メンバーの値がインクリメントされています。これは PyObject 型オブジェクトの参照回数を管理する変数で、この値が 0 になった時にオブジェクトを削除 (deallocate) できるようにする仕組みのようです。

## 存在しないキーへのアクセス
存在しないキーにアクセスした場合、dict 型では \_\_getitem\_\_() から \_\_missing\_\_() が呼ばれるようになっています ([object.\_\_missing\_\_ のドキュメント参照](https://docs.python.org/ja/3.10/reference/datamodel.html#object.__missing__))。dict のサブクラスである defaultdict も同じです。なお \_\_missing\_\_() は [defdict_missing](https://github.com/python/cpython/blob/v3.10.0/Modules/_collectionsmodule.c#L2094-L2095) で定義されております。

```c:Modules/_collectionsmodule.c
static PyObject *
defdict_missing(defdictobject *dd, PyObject *key)
{
    PyObject *factory = dd->default_factory;

...(snip)...

    value = _PyObject_CallNoArg(factory);
    if (value == NULL)
        return value;
    if (PyObject_SetItem((PyObject *)dd, key, value) < 0) {
        Py_DECREF(value);
        return NULL;
    }
    return value;
}
```

まず defdictobject 型構造体の default_factory を取り出します。この値は defdict_init() で設定されたものです。そして default_factory を引数なしで呼び出して (**\_PyObject_CallNoArg**)、その結果を value に代入します。value の値が NULL であればそこで終了ですが、それ以外の場合には、キー (key) に対する値の初期値として value をセットし (**PyObject_SetItem**)、成功したら value を返します。

# Effective Python 項目38へ再訪
defaultdict 型の値として整数値を使う場合、以下のようなコードでオブジェクトを生成することができます。`int()` の返り値は 0 なのでキーが存在しない場合のデフォルト値は 0 となります。

```python
dict_val = defaultdict(int)
```

項目38の例でも値として整数値が使用されています。そして、キーが存在しない場合にデフォルト値 0 が設定されるだけでなく、新たにキーが追加されたというメッセージを出力するために、`int` の代わりとして 0 を返す関数 `log_missing` を default_factory として指定していたというわけです。

```python
from collections import defaultdict

def log_missing():
    print('Key added')
    return 0

current = {'green': 12, 'blue': 13}
result = defaultdict(log_missing, current)
```

もともとこのようなフック関数としての利用を想定して defaultdict が実装されていたのかわかりませんが、実装を逆手に取ってこういう使い方をするのはとても面白いと思いました。