結局僕たちは intptr_t 同士を演算させても良いのか
C++ において intptr_t 同士の演算がどの程度許可されているのか気になって調べたら意外な事が見つかったのでメモ。
記事中の C++ 規格は 2020/08/09 現在の C++20 の最終 WD である N4861 を参照しています。
intptr_t の定義
そもそも intptr_t や uintptr_t はどう定義されているのか確認しましょう。C++ の規格においてはこれらの型は <cstdint> ヘッダの中に定義される適当な符号付き/符号なし整数型の using であって、コンパイラが実装するかは optional であるとだけ述べられており、その詳細は C ISO 7.20 を参照せよとぶん投げられています。仕方なく C11 の規格を参照し、§7.20.1.4 を読むと intptr_t について
The following type (引用注:
intptr_tのこと) designates a signed integer type with the property that any valid pointer to void can be converted to this type, then converted back to pointer to void, and the result will compare equal to the original pointer:
と述べられています (uintptr_tについても同様)。つまり、有効なvoid*からvoid* → intptr_t → void*と変換できて、変換の結果が元のポインタを保存するような整数型であるということです1。
intptr_t で整数演算がしたい (こともある)
ここで重要なのは、intptr_t → void*という変換単体については何も保証されていないということです。つまり以下のコードの動作は保証されません。
std::intptr_t a = 42; void* p = reinterpret_cast<void*>(a); // p は (おそらく) 無効なポインタになる std::intptr_t b = reinterpret_cast<std::intptr_t>(p); // 無効なポインタの変換は保証されない assert(a == b); // => assertion failed になる可能性が高い
ここから導かれる結論は一般には 「ポインタを整数として扱うべきではない」 というものです。一方で、稀には ポインタが整数であることをフルに活用したコードを書く必要のある場面もあります。その一例が XOR Linked List の実装です。詳細は Wikipedia のページを見ていただければ良いのですが、XOR Linked List は排他的論理和の性質を用いて双方向連結リストの省メモリ化を行うデータ構造であり、ポインタを整数とみなして演算することで実現されます。例えば XOR Linked List 上の要素から終端まで走査する処理を C++ で実装する場合は以下のようなコードを書くことになるでしょう。
template <tyopename T> struct Node<T> { T value; // この要素が持つ値 std::uintptr_t xored; // 前の要素と次の要素へのポインタの XOR }; //... Node<T>* const end = /* 終端のポインタ */; Node<T>* prev_ptr = /* 一つ前の要素を指すポインタ */; Node<T>* cur_ptr = /* 最初の要素のポインタ */ ; while (cur_ptr != end) { some_process(cur_ptr->value); // 何かしらの処理 auto tmp = cur_ptr; cur_ptr = reinterpret_cast<Node<T>*>( cur_ptr->xored ^ reinterpret_cast<std::uintptr_t>(prev_ptr)); prev_ptr = tmp; }
前述の C 言語の規定に則れば、このコードの動作は全く保証されず、未定義動作が起こりうるように思われます。しかし C++ では実は (普通に要素を動的確保している分には) このコードの動作は 保証されているのではないか？というのが今回の趣旨です。
Safely-derived pointers
ほとんど知られていませんが、C++ のポインタには valid/invalid という区別とは別に Safely-derived pointer かどうかという区別があります2。Safely-derived pointer は「有効である事が処理系から確実に追跡可能なポインタ」であり、valid 性よりも少し条件が厳しくなっていること以外はそこまで特段に注意すべきことはない概念なのですが、重要なのはその規格内に存在する integer representation of a safely-derived pointer (Safely-derived pointer の整数表現) についての規定 [basic.stc#dynamic.safety-3] です。少し長いですが丸々引用します。
An integer value is an integer representation of a safely-derived pointer only if its type is at least as large as std::intptr_t and it is one of the following:
the result of a reinterpret_cast of a safely-derived pointer value;
the result of a valid conversion of an integer representation of a safely-derived pointer value;
the value of an object whose value was copied from a traceable pointer object, where at the time of the copy the source object contained an integer representation of a safely-derived pointer value;
the result of an additive or bitwise operation, one of whose operands is an integer representation of a safely-derived pointer value P, if that result converted by reinterpretcast<void*> would compare equal to a safely-derived pointer computable from reinterpretcast<void*>(P).
これを見ると、まず Safely-derived pointer の整数表現とは大まかには Safely-derived pointer を intptr_t や uintptr_t に変換したもの及びそれらを追跡可能な範囲で弄ったものを指すっぽいです。特に最後の文章がこの整数表現性が伝播される二項演算についての記述であり、これによれば intptr_t 同士の二項演算を @ として c = a @ b と書けば
@が加算(減算も？)やビット演算であってaかbのどちらかが Safely-derived pointer であるPの整数表現であり結果である
cがPから計算可能である3
という条件を満たすとき、c も Safely-derived pointer の整数表現である。ということのようです。当然ですが、このとき reinterpret_cast<void*>(c) の結果は Safely-derived pointer であり、その結果をデリファレンスしても未定義動作は起きません。
XOR Linked List のコード再考
ここでもう一度 XOR Linked List のコードを見てみましょう。一箇所コメントを足してあります。
template <tyopename T> struct Node<T> { T value; // この要素が持つ値 std::uintptr_t xored; // 前の要素と次の要素へのポインタの XOR }; //... Node<T>* const end = /* 終端のポインタ */; Node<T>* prev_ptr = /* 一つ前の要素を指すポインタ */; Node<T>* cur_ptr = /* 最初の要素のポインタ */ ; while (cur_ptr != end) { some_process(cur_ptr->value); // 何かしらの処理 auto tmp = cur_ptr; cur_ptr = reinterpret_cast<Node<T>*>( cur_ptr->xored ^ reinterpret_cast<std::uintptr_t>(prev_ptr)); // ??? prev_ptr = tmp; }
ここでは prev_ptr および cur_ptr の初期値は Safely-derived pointer (変な事をしていない、動的領域への valid なポインタ) だと仮定します。すると ??? が付いている部分の XOR 演算では被演算変数である cur_ptr->xored と prev_ptr のうち、prev_ptr が Safely-derived pointer の整数表現であり、またその演算結果は Safely-derived pointer を指しているので、演算結果は無事 Safely-derived pointer の整数表現となります。したがって ??? 部分の後も cur_ptr は Safely-derived 性を保っており、このコードの動作が全体として保証される事が分かりました。
まとめ
以上のように、C 言語では合法ではなかったポインタの演算が C++ で追加された (全く使われていない) 概念により合法になってしまうという現象が発生しているのは非常に面白いなと思いました。一方で、コードを書くたびにこのような事を気にしなければならないのは精神をすり減らす事にもなりますし、まず絶対どこかでチェック漏れが生じます。安全なこともあるとはいえ、基本的にはポインタは整数として扱うべきではないというのは胸に刻んでおくべきでしょう。
