Pythonを改造しながら文字列の比較演算の実装を見てみる

51, 2019-07-18

目次

Pythonの文字列比較って?

こんにちは、narupoです。

Pythonを使っていてふと疑問に思ったのですが、文字列の比較ってPythonはどうやっているのでしょうか?
==!=はわかるんですが、<>になるとよくわかりません。

:::python
>>> 'abc' < 'def'
True
>>> 'abc' > 'def'
False

何をもってTrue, Falseとしているのか?

結論から言うとPythonは、↑の動作の実装ではC言語のmemcmp関数を使っていました。

今回はこのPythonの文字列比較の実装を調べてみることにしました。
この記事を読むと

  • Pythonの文字列の比較演算の実装

  • PythonのTrue, Falseの実装

  • Pythonのオブジェクトの実装

がわかります。

CPythonをゲットする

Pythonには色々な実装がありますが、今回調べるのは最も一般的と思われるCPythonの実装です。

Gitを使ってCPythonのプロジェクトをクローンします。

$ git clone https://github.com/python/cpython.git

あとはconfigureとやってmakeしてPythonをビルドします。
環境はWindows10のWSLを使っています。Ubuntu16.04ですね。なので生成されるPythonがpython.exeになってますね。

$ cd cpython
$ ./configure
$ make
$ python.exe

unicodeobject.cの実装を見てみる

CPythonではObjects/unicodeobject.c内で文字列の比較(>大なりなどの比較)関数を定義しています。

unicode_compare関数の実装

そしてunicode_compare関数でユニコード・オブジェクト(文字列)の>や<の比較をしています。

:::c
static int
unicode_compare(PyObject *str1, PyObject *str2)
{
    ...
}

引数のstr1, str2は比較される文字列です。

まず、unicode_compare関数ではstr1, str2からオブジェクトの種類を取り出しています。
kind1, kind2int型の整数です。

:::c
kind1 = PyUnicode_KIND(str1);
kind2 = PyUnicode_KIND(str2);

次にstr1, str2からデータを取り出しています。
str1, str2から取り出しているdata1, data2void *型です。

void *型はC言語で型を抽象化したい時に使われるデータ型です。
Pythonは動的型付けを採用していますが、CPythonの実装では型の抽象化のためにこのvoid *型をたくさん使っていると見ていいでしょう。

ユニコードは種類によって複数のバイト数があり得るのでvoid *型でデータを抽象化しているようですね。

:::c
data1 = PyUnicode_DATA(str1);
data2 = PyUnicode_DATA(str2);

このPyUnicode_DATAunicodeobject.hで定義されているマクロです。
オペランドがコンパクトなデータなら_PyUnicode_COMPACT_DATAでデータを取り出し、コンパクトでないデータなら_PyUnicode_NONCOMPACT_DATAassertを実行しています。

:::c++
/* Return a void pointer to the raw unicode buffer. */
#define _PyUnicode_COMPACT_DATA(op)                     \
    (PyUnicode_IS_ASCII(op) ?                   \
     ((void*)((PyASCIIObject*)(op) + 1)) :              \
     ((void*)((PyCompactUnicodeObject*)(op) + 1)))

#define _PyUnicode_NONCOMPACT_DATA(op)                  \
    (assert(((PyUnicodeObject*)(op))->data.any),        \
     ((((PyUnicodeObject *)(op))->data.any)))

#define PyUnicode_DATA(op) \
    (assert(PyUnicode_Check(op)), \
     PyUnicode_IS_COMPACT(op) ? _PyUnicode_COMPACT_DATA(op) :   \
     _PyUnicode_NONCOMPACT_DATA(op))

Pythonを改造して調べる

↓のようなPythonのコードを実行したとき、PyUnicode_DATAは何のデータを取り出すのでしょうか?

:::python
'abc' < 'def'

実験してみたいと思います。
↓のような簡単なマクロをunicodeobject.hに定義します。

:::c++
#define NpUnicode_COMPACT_DATA(op) \
    (PyUnicode_IS_ASCII(op) ? \
        "PyASCIIObject" : \
        "PyCompactUnicodeObject") \

#define NpUnicode_DATA(op) \
    (PyUnicode_IS_COMPACT(op) ? \
        NpUnicode_COMPACT_DATA(op) : \
        "NON COMPACT DATA") \

これらのマクロは、PyUnicode_DATAがどんなデータを取り出しているのかをシミュレートします。
unicodeobject.cunicode_compare関数内に↓を追記します。

:::python
data1 = PyUnicode_DATA(str1);
data2 = PyUnicode_DATA(str2);
printf("data1 = %s\n", NpUnicode_DATA(str1)); // 実験中 ( v_v )
printf("data2 = %s\n", NpUnicode_DATA(str2)); // 実験中 ( v_v )

改造したPythonをビルドして実行してみると、結果は以下のようになりました。
文字列がASCIIの場合はオブジェクトはPyASCIIObjectに、日本語が含まれている場合はPyCompactUnicodeObjectに変換されることがわかります。

>>> 'abc' < 'def'
data1 = PyASCIIObject
data2 = PyASCIIObject
True

>>> '日本語' < 'English'
data1 = PyCompactUnicodeObject
data2 = PyASCIIObject
False

str1, str2から取り出されたデータはswitch文でオブジェクトの種類ごとに分岐して、オブジェクトを比較する処理に入ります。
str1, str2の種類がどちらもPyUnicode_1BYTE_KINDであったとき、オブジェクトから取り出したdata1, data2memcmp関数で比較しています。

:::c
switch(kind1) {
case PyUnicode_1BYTE_KIND:
{
    switch(kind2) {
    case PyUnicode_1BYTE_KIND:
    {
        int cmp = memcmp(data1, data2, len);
        /* normalize result of memcmp() into the range [-1; 1] */
        if (cmp < 0)
            return -1;
        if (cmp > 0)
            return 1;
        break;
    }
    ...
...

memcmp関数はC言語の標準ライブラリです。↓がmemcmpのmanページの一部です。
memcmpは引数s1, s2をnバイト分、先頭からメモリブロックとして比較します。s1, s2が等しければ0、s1の最初のnバイトがs2の最初のnバイトよりも小さい場合は負の整数、大きい場合は正の整数を返します。

:::c
NAME
       memcmp - compare memory areas

SYNOPSIS
       #include <string.h>

       int memcmp(const void *s1, const void *s2, size_t n);

DESCRIPTION
       The  memcmp()  function  compares the first n bytes (each interpreted as unsigned char) of the memory areas s1
       and s2.

RETURN VALUE
       The memcmp() function returns an integer less than, equal to, or greater than zero if the first n bytes of  s1
       is found, respectively, to be less than, to match, or be greater than the first n bytes of s2.

       For  a  nonzero  return  value, the sign is determined by the sign of the difference between the first pair of
       bytes (interpreted as unsigned char) that differ in s1 and s2.

       If n is zero, the return value is zero.

↓が簡単なmemcmp関数のサンプルです。

:::c
#include <stdio.h>
#include <string.h>

int
main(void) {
    const char *s1 = "123";
    const char *s2 = "123";
    printf("%s = %s: %d\n", s1, s2, memcmp((void *)s1, (void *)s2, 3));

    s1 = "123";
    s2 = "223";
    printf("%s = %s: %d\n", s1, s2, memcmp((void *)s1, (void *)s2, 3));

    s1 = "223";
    s2 = "123";
    printf("%s = %s: %d\n", s1, s2, memcmp((void *)s1, (void *)s2, 3));

    return 0;
}

↑のサンプルを実行すると↓のような結果になります。

$ gcc memcmp.c && ./a.out
123 = 123: 0
123 = 223: -1
223 = 123: 1

Pythonの文字列の比較ではC言語のmemcmp関数を使っていることがわかりました。

尻尾をつかんだ

unicode_compare関数の戻り値の行方

unicode_compare関数はmemcmp関数の戻り値を-1 ~ 1の範囲に正規化しています。
ということはこの値が最終的にTrueFalseに変換されるという推測ができます。

実際にどこでTrueFalseに変換されるのか追ってみました。

まず、

:::python
'abc' < 'def'

という文字列の比較演算はObjects/unicodeobject.c内のPyUnicode_RichCompare関数が呼ばれます(unicode_compare関数より浅いところで呼ばれます)。

:::python
PyObject *
PyUnicode_RichCompare(PyObject *left, PyObject *right, int op)
{
    ...
}

この関数ではopの値によって処理が分岐します。
オペレーターが<のときはelse内の処理が呼ばれます。
unicode_compare関数を呼び出してresultに結果を入れています。
resultint型の整数です。
最終的にPy_RETURN_RICHCOMPAREが呼ばれています。

:::python
if (left == right) {
    ...
}
else if (op == Py_EQ || op == Py_NE) {
    ...
}
else {
    result = unicode_compare(left, right);
    Py_RETURN_RICHCOMPARE(result, 0, op);
}

Py_RETURN_RICHCOMPAREはInclude/object.hで定義されているマクロです。

:::c++
/*
 * Macro for implementing rich comparisons
 *
 * Needs to be a macro because any C-comparable type can be used.
 */
#define Py_RETURN_RICHCOMPARE(val1, val2, op)                               \
    do {                                                                    \
        switch (op) {                                                       \
        case Py_EQ: if ((val1) == (val2)) Py_RETURN_TRUE; Py_RETURN_FALSE;  \
        case Py_NE: if ((val1) != (val2)) Py_RETURN_TRUE; Py_RETURN_FALSE;  \
        case Py_LT: if ((val1) < (val2)) Py_RETURN_TRUE; Py_RETURN_FALSE;   \
        case Py_GT: if ((val1) > (val2)) Py_RETURN_TRUE; Py_RETURN_FALSE;   \
        case Py_LE: if ((val1) <= (val2)) Py_RETURN_TRUE; Py_RETURN_FALSE;  \
        case Py_GE: if ((val1) >= (val2)) Py_RETURN_TRUE; Py_RETURN_FALSE;  \
        default:                                                            \
            Py_UNREACHABLE();                                               \
        }                                                                   \
    } while (0)

このマクロを見るとunicode_compare関数の戻り値(-1 ~ 1)であるresultと、数値の0を比較していることがわかります。
その結果によってPy_RETURN_TRUEPy_RETURN_FALSEを実行しています。

このif文はわかりづらいですが、わかりやすくすると以下のような意味です。

:::c
if ((val1) == (val2)) 
    Py_RETURN_TRUE;
Py_RETURN_FALSE;

if文が真になりPy_RETURN_TRUEが実行されればあとのPy_RETURN_FALSEは実行されないということですね。

1行マクロでオブジェクトの参照カウントをカウント

このPy_RETURN_TRUEPy_RETURN_FALSEは名前からして内容を想像できるマクロですが、その定義を見てみると↓のようになっています。
Include/boolobject.hで定義されています。

:::c++
/* Macros for returning Py_True or Py_False, respectively */
#define Py_RETURN_TRUE return Py_INCREF(Py_True), Py_True
#define Py_RETURN_FALSE return Py_INCREF(Py_False), Py_False

この実装の詳細は後述します。

Py_True, Py_Falseの実装

Py_True, Py_FalseというのはPythonのシングルトン・オブジェクトでInclude/boolobject.hでマクロで定義されています。

:::c++
/* Don't use these directly */
PyAPI_DATA(struct _longobject) _Py_FalseStruct, _Py_TrueStruct;

/* Use these macros */
#define Py_False ((PyObject *) &_Py_FalseStruct)
#define Py_True ((PyObject *) &_Py_TrueStruct)

_Py_TrueStructのアドレスをPyObject *型に変換しています。

PyAPI_DATAInclude/pyport.hで定義されているマクロです。

:::c++
#ifndef PyAPI_DATA
#       define PyAPI_DATA(RTYPE) extern RTYPE
#endif

つまり先ほどの

:::python
PyAPI_DATA(struct _longobject) _Py_FalseStruct, _Py_TrueStruct;

という文は

:::c
extern struct _longobject _Py_FalseStruct, _Py_TrueStruct;

に置き換えられるということですね。
これは定義ではなく、このファイルから他のファイルにある_Py_FalseStruct_Py_TrueStructを参照するという意味になります。

struct _longobjectInclude/longintrepr.hで宣言されています。

:::python
struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

PyObject_VAR_HEADInclude/object.hで定義されているマクロです。

:::c++
#define PyObject_VAR_HEAD      PyVarObject ob_base;

PyVarObjectは同じInclude/object.hで宣言されています。

:::c
typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

肝心の_Py_FalseStruct_Py_TrueStructですが、これはObjects/boolobject.c内で定義されています。

:::python
struct _longobject _Py_FalseStruct = {
    PyVarObject_HEAD_INIT(&PyBool_Type, 0)
    { 0 }
};

struct _longobject _Py_TrueStruct = {
    PyVarObject_HEAD_INIT(&PyBool_Type, 1)
    { 1 }
};

struct _longobjectのヘッダーとob_digitに値を入れて真偽値を定義していますね。


1行マクロの正体

:::c++
#define Py_RETURN_TRUE return Py_INCREF(Py_True), Py_True

↑のPy_INCREFInclude/object.hで定義されているマクロです。

:::c++
#define Py_INCREF(op) _Py_INCREF(_PyObject_CAST(op))

_Py_INCREFもobject.h内で定義されています。
これは静的なインライン関数で、内容はオブジェクトの参照カウントをインクリメントしているようです。
Pythonのガベージコレクションのための処理みたいですね。

:::python
static inline void _Py_INCREF(PyObject *op)
{
    _Py_INC_REFTOTAL;
    op->ob_refcnt++;
}

_PyObject_CASTはオブジェクトをPyObject *型にキャストをするためのマクロです。

:::c++
/* Cast argument to PyObject* type. */
#define _PyObject_CAST(op) ((PyObject*)(op))

これらを踏まえて先ほどのPy_RETURN_TRUEマクロの実装を見てみます。

:::c++
#define Py_RETURN_TRUE return Py_INCREF(Py_True), Py_True

C言語ではreturn文でカンマを使うと、最後の要素が返されます。
↓が簡単なC言語のサンプルです。

:::c
#include <stdio.h>

int f(void) {
    int result = 0;
    return result++, result;
}

int main(void) {
    printf("%d\n", f());
    return 0;
}

このサンプルを実行すると実行結果は↓のようになります。

$ gcc test.c && ./a.out
1

つまり、return文でカンマを使うと、先頭の要素から処理が実行されて、最後の要素がreturnで返るということになるみたいです。

ということは、

:::c++
#define Py_RETURN_TRUE return Py_INCREF(Py_True), Py_True

という文は、Py_INCREFマクロでPy_Trueの参照カウントをインクリメントしてから、Py_Truereturnで返すという意味になりますね。
その一連の処理をPy_RETURN_TRUEというマクロで1行にしているということになります。

TrueFalseなどのPythonのシングルトン・オブジェクトも参照カウントがカウントされてるんですね。

PyObjectってなに?

ところで頻繁に出てくるPyObjectはどこで定義されているのでしょうか?
PyObjectInclude/object.hで定義されています。

:::c
/* Nothing is actually declared to be a PyObject, but every pointer to
 * a Python object can be cast to a PyObject*.  This is inheritance built
 * by hand.  Similarly every pointer to a variable-size Python object can,
 * in addition, be cast to PyVarObject*.
 */
typedef struct _object {
    _PyObject_HEAD_EXTRA
    Py_ssize_t ob_refcnt;
    struct _typeobject *ob_type;
} PyObject;

もっとごちゃごちゃした構造体を想像しましたが、すごいシンプルな構造になってますね。

Include/object.hのコメントには↓のようなことが書かれています。

An object has a 'reference count' that is increased or decreased when a
pointer to the object is copied or deleted; when the reference count
reaches zero there are no references to the object left and it can be
removed from the heap.

↓が意訳です。

オブジェクトは'参照カウント'を持ちます。これはポインタがコピーまたは削除されたときにインクリメント、デクリメントされます。
参照カウントがゼロに達したとき、オブジェクトはヒープから削除されます

つまりPyObjectが持つob_refcntが参照カウントということみたいですね。

おわりに

盛大に脇道にそれましたが、文字列の比較ではmemcmp関数が呼ばれ、その結果はunicode_compareで正規化されたあと、Py_TruePy_FalseなどのPythonのシングルトン・オブジェクトに変換されるということがわかりました。

文字列の比較という何てことのない実装から、Pythonの色々な実装を覗くことが出来たと思います。
皆さんのPythonライフの一助になれば幸いです。

以上、narupoでした。