Rokiのチラ裏

学生による学習のログ

sha-2 の理論と実装

ふと国内でもある程度取り上げられている記事 Learn Blockchains by Building One – Hacker Noon を見て自分も何か実装してみるか〜と思ったのだが、私の観測範囲内では C++ の sha-2 ハッシュ関数がライブラリとしてあまりよく整備されていない気がしたので、ブロックチェーンの実装に取り組む前に FIPS180-4を参考にこの際実装する事とし、その過程をメモ。尚、本エントリにおける文中(x) 下線はその内容がテーブルや式と関連付いている事を示す。

SHA-2は、Secure Hash Algorithmシリーズの暗号学的ハッシュ関数で、SHA-1の改良版である。National Security Agency(NSA)によって設計され、2001年にNational Institute of Standards and Technology(NIST)によってFederal Information Processing Standard(FIPS) PUB 180-4として標準化された。[..] SHA-2には、前身のSHA-1から多くの改良が加えられている。それ以前のハッシュ関数は出力が固定長で強度もその長さによって決まる値に固定されていたが、SHA-2はSHA-224、SHA-256、SHA-384、SHA-512、SHA-512/224、SHA-512/256の6つのバリエーションを持ち、ハッシュ長は224、256、384、512ビットのいずれかである。[..] SHA-2シリーズは US 6829355 によってカバーされているが、アメリカ合衆国は、この特許をロイヤリティフリーで開放している。-- wikipedia
全ての SHA-2 アルゴリズムは、メッセージダイジェストと呼ばれる凝縮表現を生成するためにメッセージを処理できる反復的な一方向ハッシュ関数であり、これらのアルゴリズムにより、メッセージの整合性を検証する事ができる。メッセージの変更は、非常に高い確率で異なるメッセージダイジェストとなり、デジタル署名やメッセージ認証コードの生成と検証、乱数やビットの生成に役立つ。
FIPS180-4/5.3 で定められた初期値*1を入力データによって反復的に変化させる。入力データを(a)一定の単位(メッセージブロック)に分割し、各単位に(b)各アルゴリズムごとによって定められた関数による計算処理(Hash computation)を施す。この時、各計算処理はその前回の計算処理で発生したハッシュを用い、全てのメッセージブロックにこの操作を行う。最後のメッセージブロックで発生した値をハッシュ値の最終結果(メッセージダイジェスト)とする。メッセージブロックやその他のサイズは下図の通り各アルゴリズムによって異なる。

アルゴリズムメッセージサイズ (bits)(a) ブロックサイズ(bits)(c) ワードサイズ (bits)メッセージダイジェストサイズ
SHA-1 2^{64}51232160
SHA-224 2^{64}51232224
SHA-256 2^{64}51232256
SHA-384 2^{128}102464384
SHA-512 2^{128}102464512
SHA-512/224 2^{128}102464224
SHA-512/256 2^{128}102464256

メッセージブロックに分割する時、(a) 指定のブロックサイズに余りなく切り分けられるとは限らない。そのような入力データに対して*2、メッセージブロックの生成においてパディングを追加する。以下各記号を FIPS18-4 に準じて次のように定義する。

  •  M: ハッシュされるメッセージ。
  •  M^{(i)}:  m ビットのサイズを有するメッセージブロック  i
  •  l: メッセージの長さ、 M をビット単位で示す。
  •  k: パディングステップ中にメッセージに追加された 0 の数。
  •  w: ワードのビット数。

    パディングは、入力データの直後にまず 1 ビットを置く。次に SHA-256 などでは式  l + 1 + k = 448 \bmod{512} に対する最小で非負の解である  k ビット分を、SHA-512 などでは式  l + 1 + k = 896 \bmod{1024} に対する最小で非負の解である  k ビット分を、先ほどの 1 ビットの直後に続くようにして拡張し、拡張したパディングを 0 で埋める。さらに続くようにして SHA-256 などでは  l に等しい 64 ビットの、SHA-512 などでは  l に等しい 128 ビットのブロックを追加する。これらの違いは(c) ワードサイズに起因する(つまり、 l 2w_{len} ビットで表される)。以下にメッセージブロックの全体構造を示す*3
 \large{M=\underbrace{\overbrace{\underbrace{01100001}_{\rm ``{\bf a}”}\quad\underbrace{01100010}_{\rm ``{\bf b}”}\quad\dots\quad\underbrace{01100011}_{\rm ``{\bf c}”}}^{l\,{\rm bits}}}_{{\rm Massage\,(}M_{\rm in}{\rm )}}\quad\underbrace{1\quad\overbrace{00\dots0}^{k\,{\rm zero\,bits}}\quad\overbrace{00\dots0\underbrace{110\dots00}_{l}}^{2w_{\rm len}\,{\rm bits}}}_{\rm Padding}}

例えば、SHA-256 において  M が "abc"(8 ビット ASCII)であるとき  M は 24 ビットの長さを有するため、まず"abc"の後方に 1 ビットを置き、次に  k ビットすなわち 423 ビット分( k = 448 - (24 + 1))を 0 で埋め、最後尾に  l を置く( 24 + 1 + 423 + 64 = 512)。

 \large\underbrace{01100001}_{"a"}\ \underbrace{01100010}_{"b"}\ \underbrace{01100011}_{"c"}\ 1\ \overbrace{00...00}^{423}\ \overbrace{00...0\underbrace{11000}_{l = 24}}^{64}

SHA-512 などでは  896 - (24 + 1) = 871 = k から 871 ビット分を 0 で埋める事となる( 24 + 1 + 871 + 128 = 1024)。

 \large\underbrace{01100001}_{"a"}\ \underbrace{01100010}_{"b"}\ \underbrace{01100011}_{"c"}\ 1\ \overbrace{00...00}^{871}\ \overbrace{00...0\underbrace{11000}_{l = 24}}^{128}

これらパディング済みのメッセージブロックを(c) アルゴリズムごとの指定のワードサイズで分割したベクトルとする。また  N をパディング済みのメッセージのブロック数、分割によって得られた  N 個のブロックを  M^{(1)}, M^{(2)}, ..., M^{(N)} と表す。各メッセージブロック  M^{(1)}, M^{(2)}, ..., M^{(N)} は以下のステップを使用して順番に( M^{(i)} (1 \leq i \leq N) というように)処理される。

  1.  M^{(i)} を 16 分割したベクトルとし、 M^{(i)}_{j} i 番目のメッセージブロックの  j 番目のワードとし、 M^{(i)}_{0}, M^{(i)}_{1}, ..., M^{(i)}_{15} と表す(例えば  M^{(i)}_{0} はメッセージブロック  i の左端のワードである。)。次に、 H^{(i)} i 番目のハッシュ値とし、同様に各  H^{(i)} を 16 分割したベクトルにし、 H^{(i)}_{0}, H^{(i)}_{1}, ..., H^{(i)}_{15} と表す(つまり、 H^{(0)} は初期ハッシュ値 H^{(N)}は最終ハッシュ値であり最終ハッシュ値においてはメッセージダイジェストを決定するために使用される)。両者ともに、 w_{len} の長さを持つビット列である。
  2. メッセージスケジュールを準備する。 W_{t} t 番目の  w ビットワードとする。尚  \sigma_0(x) \sigma_1(x) は各アルゴリズムごとに異なる(SHA-224, 256 は \sigma_0^{\\\{ 256 \\\}} \sigma_1^{\\\{ 256 \\\}} 、SHA-384, 512, 512/224, 512/256 は  \sigma_0^{\\\{ 512 \\\}} \sigma_1^{\\\{ 512 \\\}})。
     \large{{W_t = \left\{
    \begin{array}{ll}
    M_t^{(i)} & (0 \leq t \leq 15)\\
    \sigma_1(W_{t-2})+W_{t-7}+\sigma_0(W_{t-15})+W_{t-16} & (16 \leq t \leq (n_{\rm rnd} - 1))
    \end{array}
    \right.}}
  3.  a, b, c, d, e, f, g, h の 8 つを作業変数とする。次のように、 (i - 1) 番目のハッシュ値で初期化する。
     \large{\begin{align}
    a&=H_0^{(i-1)}\\
    b&=H_1^{(i-1)}\\
    c&=H_2^{(i-1)}\\
    d&=H_3^{(i-1)}\\
    e&=H_4^{(i-1)}\\
    f&=H_5^{(i-1)}\\
    g&=H_6^{(i-1)}\\
    h&=H_7^{(i-1)}
    \end{align}
    }
  4.  Ch(x, y, z) = (x \land y) \bigoplus (-x \land z) Maj(x, y, z) = (x \land y) \bigoplus (x \land z) \bigoplus (y \land z) K_{t} を利用する定数値とする。また、次の通り各記号を定義する。

    •  \land: Bitwise AND
    •  \lor: Bitwise OR
    •  \bigoplus: Bitwise XOR
    •  \lnot: Bitwise 補数演算
    •  +:  \pmod{2^{w}} の加算

    また、次の通り各関数を定義する。
    Hash operations
     ROTL^{n}(x): 左回転(circular left shift)。 x w ビットワードであり整数  n 0 \leq n \lt w である。 ROTL^{n}(x) = (x \ll n) \lor (x \gg w - n) と定義される。
     ROTR^{n}(x): 右回転(circular right shift)。 x w ビットワードであり整数  n 0 \leq n \lt w である。 ROTR^{n}(x) = (x \gg n) \lor (x \ll w - n) と定義される。
     SHR^{n}(x): 右シフト。 x w ビットワードであり整数  n 0 \leq n \lt w である。 SHR^{n}(x) = x \gg n と定義される。
    Hash computation
    (b) SHA-224, SHA-256 ( x, y, z は 32 ビットワードである。)
     \sum_{0}^{(256)}(x) = ROTR^{2}(x) \bigoplus ROTR^{13}(x) \bigoplus ROTR^{22}(x)
     \sum_{1}^{(256)}(x) = ROTR^{6}(x) \bigoplus ROTR^{11}(x) \bigoplus ROTR^{25}(x)
     \sigma_{0}^{(256)}(x) = ROTR^{7}(x) \bigoplus ROTR^{18}(x) \bigoplus SHR^{3}(x)
     \sigma_{1}^{(256)}(x) = ROTR^{17}(x) \bigoplus ROTR^{19}(x) \bigoplus SHR^{10}(x)
    (b) SHA-384, SHA-512, SHA-512/224, SHA512/256( x, y, z は 64 ビットワードである。)
     \sum_{0}^{(512)}(x) = ROTR^{28}(x) \bigoplus ROTR^{34}(x) \bigoplus ROTR^{39}(x)
     \sum_{1}^{(512)}(x) = ROTR^{14}(x) \bigoplus ROTR^{18}(x) \bigoplus ROTR^{41}(x)
     \sigma_{0}^{(512)}(x) = ROTR^{1}(x) \bigoplus ROTR^{8}(x) \bigoplus SHR^{7}(x)
     \sigma_{1}^{(512)}(x) = ROTR^{19}(x) \bigoplus ROTR^{61}(x) \bigoplus SHR^{6}(x)
     t 0 から  n_{\rm rnd} - 1 まで繰り返して次のようにローテートする。尚  K_{t} は各アルゴリズムごとに異なる( \Sigma_0(x) \Sigma_1(x) に関しては前述した通り)(SHA-224, 256 は  K_{t}^{\\\{256\\\}}、SHA-384, 512, 512/224, 512/256 は  K_{t}^{\\\{512\\\}})。
     \large{\begin{align}
    T_1&=h+\Sigma_1(e)+{\it Ch}(e,f,g)+K_t+W_t\\
    T_2&=\Sigma_0(a)+{\it Maj}(a,b,c)\\
    h&=g\\
    g&=f\\
    f&=e\\
    e&=d+T_1\\
    d&=c\\
    c&=b\\
    b&=a\\
    a&=T_1+T_2
    \end{align}
    }
  5.  i 番目の中間ハッシュ値  H^{(i)} を次のようにして計算する。
     \large{\begin{align}
    H_0^{(i)}&=a+H_0^{(i-1)}\\
    H_1^{(i)}&=b+H_1^{(i-1)}\\
    H_2^{(i)}&=c+H_2^{(i-1)}\\
    H_3^{(i)}&=d+H_3^{(i-1)}\\
    H_4^{(i)}&=e+H_4^{(i-1)}\\
    H_5^{(i)}&=f+H_5^{(i-1)}\\
    H_6^{(i)}&=g+H_6^{(i-1)}\\
    H_7^{(i)}&=h+H_7^{(i-1)}\\
    \end{align}
    }

以上の操作をメッセージブロックに対して反復的に実行する*4

実装

github.com

sha-224, 256, 384, 512, 512/224, 512/256 の全てに対応しており、ハッシュ値の生成において当コンポーネントはスレッドセーフである。さらに、これの C++ Library-Wide Hash コンセプトを満たす関数オブジェクト型を用意してあるので、例えば次のようにして標準コンテナのハッシュ生成などに利用できる(オーバーキル気味のような気もするが)。

なおテストは次のようにして実行している。

*1:この値は Nothing up my sleeve number であり、SHA-2 では小さな素数平方根と立方根から成る値で定義している。

*2:厳密に設計の観点で補足するならば、実際は例え M がブロックサイズの倍数だったとしてもパディング処理は施される

*3:FIPS180-4/5.1 には各アルゴリズムごとの具体的な全体構造が示されている

*4:この一連の操作は Merkle–Damgård construction と呼ばれる

Searching and Manipulation of Parameter Packs

2014 年頃に提案されていたペーパー、N4144, Searching and Manipulation of Parameter Packs をふと見かけて少し思うところがあったのでそれについてのチラ裏記事(特別新しい技術、発想ではないと思うのだが、何だかんだ同じような事をしている有名どころを見た事がないので)。
同ペーパー内でis_contained_inというメタ関数が提案されている。これは、パラメータパックに対して線形時間をかけて指定された型がその内部に含まれるかチェックするメタ関数である。しかし実際の利用においては、この機能では乏しすぎる。実際に利用したいのは、ある型Tが含まれるかではなくあるポリシーに沿う型が含まれるかであって、ある型Tが含まれるかあるポリシーに沿う型が含まれるかで表現できる。また、ポリシーは<type_traits>の資産を活かして表現できる設計が好ましいように思う。

conditionalを使うと無駄なインスタンス化が発生しうるのでそれを使わない実装としている。次のように利用できる。

#include <srook/tmpl/vt/is_contained_in_like.hpp>
#include <type_traits>
#include <string>

struct X{};

using namespace srook::tmpl::vt;
typedef packer<float, int, double> type1;
typedef packer<packer<X, int>, packer<std::string, int>> type2;
typedef packer<packer<X, int>, packer<int, int>> type3;

static_assert(is_contained_in_like<is_integral, type1>{});
static_assert(!is_contained_in_like<is_convertible, type2>{};) // == !conjunction<is_convertible<X, int>, is_convertible<std::string, int>>::value
static_assert(is_contained_in_like<is_same, type3>{};) // == is_contained_in<T, packer<Ts...>>::value

packerの内部にpackerを持たせると、第一引数で渡されたメタ関数にそのpackerを 1 単位として転送する。実際に多くの場面で利用するためにはこれの亜種としていくらかメタ関数を作っておくと便利だ。例えば、あるポリシーに沿う型をある型に置き換えるといった処理の場合、次のようなメタ関数があれば便利になるだろう。

これは、例えば以下のようにして利用できる。

これは与えられた算術型の内、整数型を全て浮動小数点数型にする関数の冒頭であるが、このようにして宣言する事で、型を見るだけで(は言い過ぎかもしれないが)関数そのものの動作を把握する事もできる。

See also

haskell $ 演算子の挙動

プログラミング言語 Haskell における演算子$に関するメモ。 次の関数  f(x, y) は指定範囲の数列のうちの偶数の二乗の総和を求める関数である。

f x y = sum $ map (^2) $ filter even [x..y]
g x y | x < y = f x y | x > y = f y x

main = print $ g 1 10

これは次のコードと等価である。

f x y = ((sum) (map (^2) (filter even [x..y])))
g x y | x < y = f x y | x > y = f y x

main = print $ g 1 10

$は以下の実行結果が示すように GHC.Base モジュールで定義されている。

Prelude> :i ($)
($) ::
  forall (r :: GHC.Types.RuntimeRep) a (b :: TYPE r).
  (a -> b) -> a -> b
        -- Defined in ‘GHC.Base’
infixr 0 $

執筆時現在の定義*1*2は以下の通りである*3

infixr 0  $, $!

--- 略

{-# INLINE ($) #-}
($) :: forall r a (b :: TYPE r). (a -> b) -> a -> b
f $ x =  f x

上記定義の通り、$演算子は関数とその引数を受け取りその引数を関数に転送する。また優先レベルは 0 であり右に結合する。以上の定義を参考に次のコードの評価順序を順にシミュレートする。

f x y = sum $ map (^2) $ filter even [x..y]

$ は優先順位が最も低いので以下のように括弧がつく。

f x y = (sum) $ (map (^2)) $ (filter even [x..y])

$は右に結合するので以下のように括弧がつく。

f x y = (sum) $ ((map (^2)) $ (filter even [x..y]))

$を消去して以下の式に納まる。

f x y = ((sum) ((map (^2)) (filter even [x..y])))

Polymorphic Memory Resources

先日策定された C++17 から追加された Polymorphic Memory Rerouces についてのメモ。同提案でも言及されている通りstd::allocatorは、型にそのアロケータ情報を含む事で利用されるため、コンパイル時にしか指定することが出来ず、結果として同じ型のオブジェクトは同じアロケータしか持つことが出来なかった。これに対して<memory_resources>ポリモーフィックなランタイム動作を行うことで、同じ型のオブジェクトでも、異なるアロケータを持つことができるようにする*1
C++17 から<memory_resource>ヘッダが追加され、std::pmr名前空間下にpolymorphic_allocator, memory_resource, pool_options, synchronized_pool_resource, unsynchronized_pool_resource, monotonic_buffer_resourceクラス、new_delete_resource, null_memory_resource, get_default_resource, set_default_resource関数が定義される。大元の提案は、N3525*2、同提案の最終リビジョンは N3916 r2。以下は C++17(N4659) [mem.res.syn] から引用*3

namespace std::pmr {
  // [mem.res.class], class memory_­resource
  class memory_resource;

  bool operator==(const memory_resource& a, const memory_resource& b) noexcept;
  bool operator!=(const memory_resource& a, const memory_resource& b) noexcept;

  // [mem.poly.allocator.class], class template polymorphic_­allocator
  template<class Tp> class polymorphic_allocator;

  template<class T1, class T2>
    bool operator==(const polymorphic_allocator<T1>& a,
                    const polymorphic_allocator<T2>& b) noexcept;
  template<class T1, class T2>
    bool operator!=(const polymorphic_allocator<T1>& a,
                    const polymorphic_allocator<T2>& b) noexcept;

  // [mem.res.global], global memory resources
  memory_resource* new_delete_resource() noexcept;
  memory_resource* null_memory_resource() noexcept;
  memory_resource* set_default_resource(memory_resource* r) noexcept;
  memory_resource* get_default_resource() noexcept;

  // [mem.res.pool], pool resource classes
  struct pool_options;
  class synchronized_pool_resource;
  class unsynchronized_pool_resource;
  class monotonic_buffer_resource;
}

Abstract base class memory_resource

Abstract base class memory_resource はブロックの割り当て及び割り当て解除ができるメモリリソースを記述する。これは純粋仮想関数である do_allocate, do_deallocate, do_is_equal をそれぞれ呼び出す関数 allocate*4, deallocate 及び is_equal を提供する。N4659/[mem.res.class] から引用。

namespace std::pmr {
  class memory_resource {
    static constexpr size_t max_align = alignof(max_align_t);   // exposition only

  public:
    virtual ~memory_resource();

    void* allocate(size_t bytes, size_t alignment = max_align);
    void deallocate(void* p, size_t bytes, size_t alignment = max_align);

    bool is_equal(const memory_resource& other) const noexcept;

  private:
    virtual void* do_allocate(size_t bytes, size_t alignment) = 0;
    virtual void do_deallocate(void* p, size_t bytes, size_t alignment) = 0;

    virtual bool do_is_equal(const memory_resource& other) const noexcept = 0;
  };
}

memory_resourceクラスを派生させ、各純粋仮想関数を実装する事でそれを共有メモリリソースとして使用できる。do_allocate関数はアロケートされた記憶領域へのポインタを返さなければならない。この時返された記憶領域のアラインメントがサポートされていない場合、指定されたアラインメントに揃えられ、それ以外の場合max_alignに揃えられる。要求されたサイズとアラインメントでメモリを割り当てることができない場合、適切な例外をスローしなければならない。

virtual void* do_allocate(size_t bytes, size_t alignment) = 0;

do_deallocate関数は、アロケートされた記憶域を破棄しなければならない。

virtual void do_deallocate(void* p, size_t bytes, size_t alignment) = 0;

do_is_equal関数は、このクラスからアロケートされたメモリを他のクラスからデアロケート出来る場合にtrueを返し、そうでない場合はfalseを返さなければならない。

virtual bool do_is_equal(const memory_resource& other) const noexcept = 0;

以下のように利用できる*5

#include <memory_resource>

class X : public std::pmr::memory_resource {
protected:
    void* do_allocate(std::size_t bytes, [[maybe_unused]] std::size_t alignment) override { return ::operator new(bytes); }
    void do_deallocate(void* p, [[maybe_unused]] std::size_t bytes, [[maybe_unused]] std::size_t alignment) override { ::operator delete(p); }
    bool do_is_equal(const std::pmr::memory_resource& other) const noexcept override { return this == std::addressof(other); }
};

Class Template polymorphic_allocator<T>

N4659/[mem.poly.allocator.class] から引用。

namespace std::pmr {
  template<class Tp>
    class polymorphic_allocator {
      memory_resource* memory_rsrc;     // exposition only

    public:
      using value_type = Tp;

      // [mem.poly.allocator.ctor], constructors
      polymorphic_allocator() noexcept;
      polymorphic_allocator(memory_resource* r);

      polymorphic_allocator(const polymorphic_allocator& other) = default;

      template<class U>
        polymorphic_allocator(const polymorphic_allocator<U>& other) noexcept;

      polymorphic_allocator& operator=(const polymorphic_allocator& rhs) = delete;

      // [mem.poly.allocator.mem], member functions
      Tp* allocate(size_t n);
      void deallocate(Tp* p, size_t n);

      template<class T, class... Args>
        void construct(T* p, Args&&... args);

      template<class T1, class T2, class... Args1, class... Args2>
        void construct(pair<T1, T2>* p, piecewise_construct_t,
                       tuple<Args1...> x, tuple<Args2...> y);
      template<class T1, class T2>
        void construct(pair<T1, T2>* p);
      template<class T1, class T2, class U, class V>
        void construct(pair<T1, T2>* p, U&& x, V&& y);
      template<class T1, class T2, class U, class V>
        void construct(pair<T1, T2>* p, const pair<U, V>& pr);
      template<class T1, class T2, class U, class V>
        void construct(pair<T1, T2>* p, pair<U, V>&& pr);

      template<class T>
        void destroy(T* p);

      polymorphic_allocator select_on_container_copy_construction() const;

      memory_resource* resource() const;
    };
}

インタフェースから見てわかるように、クラスpolymorphic_allocator<T>はアロケータの必要用件、インタフェースに合わせて上記memory_resourceをラップするクラスである。コンストラクタにはメモリリソースのポインタを渡す。上述したクラスXを例えば次のように利用できる。

template <class T>
using poly_vector = std::vector<T, std::pmr::polymorphic_allocator<T>>;

int main()
{
    auto r = std::make_unique<X>();
    std::pmr::polymorphic_allocator<int> pa(r.get());
    [[maybe_unused]] poly_vector<int> v(pa);
}

尚、std::pmr::polymorphic_allocatorはデフォルトコンストラクトする事ができ、その場合内部のメモリリソースは下記で説明されているstd::pmr::set_default_resourceによってデフォルトのメモリリソースが設定されない限り、std::pmr::new_delete_resourceの戻り値に設定され、そうでない場合、std::pmr::set_default_resourceで設定されたメモリリソースが設定される。

Access to program-wide memory_­resource objects

以下に示す関数らは、一般的なメモリリソースを提供する。

new_delete_resource

memory_resource* new_delete_resource() noexcept;

new_delete_resourceは上述したクラスXと同じ役割を果たすメモリリソースへのポインタを返す。つまり、::operator new::operator deleteを利用してメモリをアロケート、デアロケートするメモリリソースへのポインタが返される。この関数は、何度呼び出しても同じ値が返される。次の例は、std::vectorのアロケート、デアロケートにおいて、上述のメモリリソースXのアロケート、デアロケートと似たように*6振る舞う。

std::pmr::polymorphic_allocator<int> pa(std::pmr::new_delete_resource());
[[maybe_unused]] poly_vector<int> v(pa);

assert(std::pmr::new_delete_resource() == std::pmr::new_delete_resource());

尚、この時返されるポインタpis_equal(r)と呼び出した時、&r == pが返される。

auto p = pmr::new_delete_resource();
assert(p->is_equal(*p));

null_memory_resource

memory_resource* null_memory_resource() noexcept;

これは、allocateが呼び出された時に常にstd::bad_alloc例外を送出し、失敗するメモリリソースへのポインタを返す。これは、1つのメモリリソースが、別のメモリリソースに依存するようなメモリリソースのチェーンの終わりを設定するのに便利に利用できる。一番初めのメモリリソースが、自身のメモリプールを使い果たす事を予測できないような状況で null なメモリリソースを仕様してヒープから誤ってメモリをアロケートしてしまうというような事を回避できる。

try {
    std::pmr::polymorphic_allocator<int> pa(pmr::null_memory_resource());
    [[maybe_unused]] typename decltype(pa)::value_type* p = pa.allocate(1); // always throw std::bad_alloc
} catch (const std::exception& e) {
    std::cerr << e.what() << std::endl;
}

set_default_resource

memory_resource* set_default_resource(memory_resource* r) noexcept;

これは、r が null でない限りデフォルトメモリリソースをrに設定する。そうでない場合、デフォルトメモリリソースをstd::pmr::new_delete_resourceの戻り値に設定する。

inline std::pmr::memory_resource* X_resource()
{
    static X resource;
    return static_cast<std::pmr::memory_resource*>(&resource);
}

std::pmr::set_default_resource(X_resource());
std::pmr::polymorphic_allocator<int> pa1;
assert(pa1.resource() == X_resource());
    
std::pmr::set_default_resource(nullptr);
std::pmr::polymorphic_allocator<int> pa2;
assert(pa2.resource() == std::pmr::new_delete_resource());

get_default_resource

memory_resource* get_default_resource() noexcept;

これは、現在のデフォルトメモリリソースポインタの値を返す。

assert(std::pmr::get_default_resource() == std::pmr::new_delete_resource());
std::pmr::set_default_resource(X_resource());
assert(std::pmr::get_default_resource() == X_resource());

Pool resource classes

以下に示すクラスらは、標準的なプールリソースを提供する。

synchronized_pool_resource, unsynchronized_pool_resource

これらはまとめてプールリソースと呼ばれる。プールリソースは以下のような特徴を持つ。

  • アロケートされた記憶域を所有し、アロケートされたブロックの一部、または全てに対してdeallocateが呼び出されなくても破棄時に自動的に解放される汎用リソースである。
  • プールリソースは、プールの集合によって構成され、異なるブロックサイズの要求を処理する。それぞれ個々のプールは、一様なサイズのブロックに分割されたチャンクの集合を管理し、do_allocateの呼び出しを介して返される。do_allocate(size, alignment)への各呼び出しは少なくともsizeバイトを扱うプールにディスパッチされる。
  • 特定のプールが使い尽くされた時に、そのプールからブロックを割り当てると上流アロケータ( upstream\ allocator)*7から追加のメモリチャンクが割り当てられ、プールが補充される。連続した補充ごとに得られるチャンクサイズは幾何級数的に増加する*8
  • 任意のプールの最大ブロックサイズを超えるアロケーション要求は、上流アロケータから直接実行される。
  • pool_options構造体をプールリソースコンストラクタに渡して、最大ブロックサイズと最大チャンクサイズを調整することができる。


synchronized_pool_resourceは、外部同期なしで複数のスレッドからアクセスすることができ、同期コストを削減するためにスレッド固有のプールを持つことができる。unsynchronized_pool_resourceクラスは、複数のスレッドから同時にアクセスすることはできないが、シングルスレッドアプリケーションのような同期コストを払う必要のない場面では最適である。以下に、二つのクラスのインタフェースを N4659/[mem.res.pool.overview] から引用する。

namespace std::pmr {
  struct pool_options {
    size_t max_blocks_per_chunk = 0;
    size_t largest_required_pool_block = 0;
  };

  class synchronized_pool_resource : public memory_resource {
  public:
    synchronized_pool_resource(const pool_options& opts, memory_resource* upstream);

    synchronized_pool_resource()
        : synchronized_pool_resource(pool_options(), get_default_resource()) {}
    explicit synchronized_pool_resource(memory_resource* upstream)
        : synchronized_pool_resource(pool_options(), upstream) {}
    explicit synchronized_pool_resource(const pool_options& opts)
        : synchronized_pool_resource(opts, get_default_resource()) {}

    synchronized_pool_resource(const synchronized_pool_resource&) = delete;
    virtual ~synchronized_pool_resource();

    synchronized_pool_resource& operator=(const synchronized_pool_resource&) = delete;

    void release();
    memory_resource* upstream_resource() const;
    pool_options options() const;

  protected:
    void* do_allocate(size_t bytes, size_t alignment) override;
    void do_deallocate(void* p, size_t bytes, size_t alignment) override;

    bool do_is_equal(const memory_resource& other) const noexcept override;
  };

  class unsynchronized_pool_resource : public memory_resource {
  public:
    unsynchronized_pool_resource(const pool_options& opts, memory_resource* upstream);

    unsynchronized_pool_resource()
        : unsynchronized_pool_resource(pool_options(), get_default_resource()) {}
    explicit unsynchronized_pool_resource(memory_resource* upstream)
        : unsynchronized_pool_resource(pool_options(), upstream) {}
    explicit unsynchronized_pool_resource(const pool_options& opts)
        : unsynchronized_pool_resource(opts, get_default_resource()) {}

    unsynchronized_pool_resource(const unsynchronized_pool_resource&) = delete;
    virtual ~unsynchronized_pool_resource();

    unsynchronized_pool_resource& operator=(const unsynchronized_pool_resource&) = delete;

    void release();
    memory_resource* upstream_resource() const;
    pool_options options() const;

  protected:
    void* do_allocate(size_t bytes, size_t alignment) override;
    void do_deallocate(void* p, size_t bytes, size_t alignment) override;

    bool do_is_equal(const memory_resource& other) const noexcept override;
  };
}

pool_optionsは前述した通り、プールリソース用のコンストラクターオプションとして利用する事ができ、そのように構成されている。pool_optionsには二つのデータメンバが用意されているが、プールリソースの動作に対する各データメンバの効果は以下の通りである。

size_t max_blocks_per_chunk;
プールを補充するために上流メモリリソースから一度に割り当てられるブロックの最大数を指定する。size_t max_blocks_per_chunk;の値が 0 であるか、実装定義の制限値よりも大きい場合は、その制限が代わりに使用される。実装では、この変数で指定されている値よりも小さい値を使用する事があり、プールごとに異なる値を使用する可能性がある。
size_t largest_required_pool_block;
プールする最大ブロックサイズを指定する。この値よりも大きな単一のブロックを割り当てる操作は、上流メモリリソースから直接割り当てられる。0 であるか、実装定義の制限値よりも大きい場合は、その制限が代わりに使用される。実装では、この変数で指定した閾値を超えた閾値を選択する事ができる。

以下のように使用できる。

std::pmr::synchronized_pool_resource pool1;
[[maybe_unused]] std::pmr::synchronized_pool_resource pool2(X_resource());
[[maybe_unused]] std::pmr::synchronized_pool_resource pool3(std::pmr::pool_options{ 0, 0 });
[[maybe_unused]] std::pmr::synchronized_pool_resource pool4(std::pmr::pool_options{ 0, 0 }, X_resource());

std::pmr::polymorphic_allocator<int> pa(pool1);

poly_vector<int> v(pa);

Class monotonic_­buffer_­resource

これは、上流メモリリソースから十分な大きさのストレージを確保し、各オブジェクトが必要とするサイズに切り分けて返すメモリリソースである。特徴として、std::pmr::monotonic_buffer_resource自身が破棄されるまで、一度占有されたメモリ空間は解放される事はない。これは、全てのメモリリソースオブジェクトが破棄された時に一括して解放される状況で、高速なメモリアロケーションを実現する事を目的とした専用メモリリソースである。加えて、以下の性質がある。

  • deallocateが呼び出されても、何もしない。よって、消費されるメモリ量はリソースが破棄されるまで単調増加する。
  • プログラムは、メモリ要求を満たすためにアロケータが使用する初期バッファを指定する事ができる。
  • 初期バッファ(存在する場合)が使い果たされると、初期バッファは、構築時に供給される上流メモリリソースから追​​加のバッファを取得する。各追加バッファは、幾何学的な進行に従って、前のバッファよりも大きくなる。
  • 一度に1つの制御スレッドからのアクセスを意図している。すなわち、allocatedeallocateの呼び出しは互いに同期しない。つまりスレッドセーフでない。
  • アロケートされたブロックのいくつかに対してデアロケート処理が呼び出されていなくても、割り振られたメモリーをデストラクト時に解放する。

    以下にstd::pmr::monotonic_buffer_resourceクラスのインタフェースを N4659/[mem.res.monotonic.buffer] から引用する。
namespace std::pmr {
  class monotonic_buffer_resource : public memory_resource {
    memory_resource* upstream_rsrc;     // exposition only
    void* current_buffer;               // exposition only
    size_t next_buffer_size;            // exposition only

  public:
    explicit monotonic_buffer_resource(memory_resource* upstream);
    monotonic_buffer_resource(size_t initial_size, memory_resource* upstream);
    monotonic_buffer_resource(void* buffer, size_t buffer_size, memory_resource* upstream);

    monotonic_buffer_resource()
        : monotonic_buffer_resource(get_default_resource()) {}
    explicit monotonic_buffer_resource(size_t initial_size)
        : monotonic_buffer_resource(initial_size, get_default_resource()) {}
    monotonic_buffer_resource(void* buffer, size_t buffer_size)
        : monotonic_buffer_resource(buffer, buffer_size, get_default_resource()) {}

    monotonic_buffer_resource(const monotonic_buffer_resource&) = delete;

    virtual ~monotonic_buffer_resource();

    monotonic_buffer_resource& operator=(const monotonic_buffer_resource&) = delete;

    void release();
    memory_resource* upstream_resource() const;

  protected:
    void* do_allocate(size_t bytes, size_t alignment) override;
    void do_deallocate(void* p, size_t bytes, size_t alignment) override;

    bool do_is_equal(const memory_resource& other) const noexcept override;
  };
}

以下の様に利用できる。

constexpr std::size_t buff_size = 1024;
auto buf = std::make_unique<unsigned char[]>(buff_size);

std::pmr::monotonic_buffer_resource mbr1; // #1
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr2(X_resource()); // #2
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr3(buff_size, std::pmr::get_default_resource()); //#3
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr4(buf.get(), buff_size); // #4
[[maybe_unused]] std::pmr::monotonic_buffer_resource mbr5(buf.get(), buff_size, std::pmr::get_default_resource()); // #5

std::pmr::polymorphic_allocator<int> pa(mbr1);
poly_vector<int> v(pa);

#1 では  current\ buffer を nullptr に設定し、 next\ buffer\ size を実装定義のサイズに設定し、上流メモリリソースをデフォルトメモリリソースから設定する。#2 では任意のメモリリソースを受け取っている。 #3 はそれに加えて  next\ buffer\ size を少なくともbuff_sizeに設定する。#4 では、 current\ bufferbuf.get() の戻り値に設定し、 next\ buffer\ size を少なくともbuff_sizeに設定する。#5 はそれに加えて上流メモリリソースをstd::pmr::get_default_resourceの戻り値に設定している。
尚、std::pmr::monotoric_buffer_resource::do_is_equalは N4659/[mem.res.monotonic.buffer.mem] で次の様にダウンキャストを行うと述べられている(執筆時最新のドラフト(C++20) N4713/[mem.res.monotonic.buffer.mem]でも同様)。

bool do_is_equal(const memory_resource& other) const noexcept override;
Returns:this == dynamic_cast(&other)

しかし、この比較処理はオブジェクトの等価判定ではなくアドレスの等価判定であるため、このようなダウンキャストは余分である。これは先に挙げたstd::pmr::synchronized_pool_resource::do_is_equalstd::pmr::unsynchronized_pool_resource::do_is_equal にも見られ、既に LWG に報告されている

Aliases for container classes

これまで例として利用してきたpoly_vectorエイリアステンプレートと同じエイリアステンプレートが標準からも提供される。

namespace std {
namespace pmr {

template <class T>
using vector<T> = std::vector<T, polymorphic_allocator<T>>;

} // namespace pmr
} // namespace std

上記の様なエイリアステンプレートが提供されるライブラリーらは以下の通りである*9

  • string
  • deque
  • forward_list
  • list
  • vector
  • map
  • set
  • unorderd_map
  • unorderd_set
  • regex

*1:「オブジェクトの型はメモリを取得するために使用するアロケータと独立しなければならない」と述べられている(N3916 r2/3)。

*2:この提案ではアロケータで Type Erasure を利用することでインタフェースを改善し、動的にアロケータを使えるようにするというものだった

*3:p0790r0 では memory_resource クラスに strong_equality の space ship operator を定義する提案がされている。それと伴い memory_resource クラスを基底とする三つのクラスも自ずと strong_equality となる。

*4:C++20 では、P0600R1 によって nodiscard 属性が指定される

*5:簡単のため、アラインメントのチェック、例外送出などの処理を行なっていないが、実際の利用では厳密なチェックと例外送出を行う事が望ましい。例えば、アラインメントが 0 と等しい、または 2 の冪乗であるかをチェックしそれに応じて max_align を返すなどの処理が考えられる。

*6:前述した通り、X ではアラインメントの整合性チェックとそれに応じた例外処理を省いている点で異なる

*7:これは、コンストラクト時に指定されるメモリリソースが利用される。コンストラクト時に指定しない場合、デフォルトメモリリソースが利用される。

*8:チャンク単位でメモリを割り当てる事で、メモリ内で連続したアロケーションを獲得できる機会を増やす。これはフラグメンテーションの防止につながる。

*9:P0220r1 -> n4562 参照。

implicitly capture の振る舞い

以下の例が成り立つ。

const int i = 123; // #1
const float f = 123.f; // #2

[]{ i; }(); // OK
[]{ f; }(); // ill-formed

C++17 のラムダ式における reaching scope に関する記述 n4659/[expr.prim] 3, 7, n4659/[expr.prim.lambda.capture] 8 から引用。太文字は強調。

A lambda-expression whose smallest enclosing scope is a block scope is a local lambda expression; any other lambda-expression shall not have a capture-default or simple-capture in its lambda-introducer. The reaching scope of a local lambda expression is the set of enclosing scopes up to and including the innermost enclosing function and its parameters. [ Note: This reaching scope includes any intervening lambda-expressions.  — end note ]
(snip)
A lambda-expression with an associated capture-default that does not explicitly capture *this or a variable with automatic storage duration (this excludes any id-expression that has been found to refer to an init-capture's associated non-static data member), is said to implicitly capture the entity (i.e., *this or a variable) if the compound-statement:
— odr-uses the entity (in the case of a variable),
— odr-uses this (in the case of the object designated by *this), or
— names the entity in a potentially evaluated expression where the enclosing full-expression depends on a generic lambda parameter declared within the reaching scope of the lambda-expression.
[ Example:
void f(int, const int (&)[2] = {})    { }   // #1
void f(const int&, const int (&)[1])  { }   // #2
void test() {
  const int x = 17;
  auto g = [](auto a) {
    f(x);                       // OK: calls #1, does not capture x
  };

  auto g2 = [=](auto a) {
    int selector[sizeof(a) == 1 ? 1 : 2]{};
    f(x, selector);             // OK: is a dependent expression, so captures x
  };
}
— end example ] All such implicitly captured entities shall be declared within the reaching scope of the lambda expression. [ Note: The implicit capture of an entity by a nested lambda-expression can cause its implicit capture by the containing lambda-expression (see below). Implicit odr-uses of this can result in implicit capture.  — end note ]
(snip)
If a lambda-expression or an instantiation of the function call operator template of a generic lambda odr-uses this or a variable with automatic storage duration from its reaching scope, that entity shall be captured by the lambda-expression.

続いて  odr-used に関する記述、同ドラフト [basic.def.odr] 3

A variable x whose name appears as a potentially-evaluated expression ex is odr-used unless applying the lvalue-to-rvalue conversion to x yields a constant expression (snip) or e is a discarded-value expression.

続いて  constant-expression に関する記述、同ドラフト[expr.const] 2.7.1 *1

— an lvalue-to-rvalue conversion unless it is applied to
— a non-volatile glvalue of integral or enumeration type that refers to a complete non-volatile const object with a preceding initialization, initialized with a constant expression, or
— a non-volatile glvalue that refers to a subobject of a string literal, or
— a non-volatile glvalue that refers to a non-volatile object defined with constexpr, or that refers to a non-mutable subobject of such an object, or
— a non-volatile glvalue of literal type that refers to a non-volatile object whose lifetime began within the evaluation of e;

まとめ

ブロックスコープ内のラムダの場合、reaching scope 内の特定の基準を満たす変数はキャプチャされなくともラムダ内では限られた用途で使用できる。reaching scope にはラムダが定義された時点でスコープ内にある、ラムダを含む関数のローカル変数が含まれる。特定の基準と限られた用途とは以下の通りである。

  1. ラムダの内部で変数は  odr-used であってはならない。つまり
    •  discarded-value\ expression または
    • 値の取り出し
  2. 変数は次のいずれかでなければならない。
    • 初期化子が  constant-expression である 非volatileconstな整数、enum、または
    • volatileconstexprな変数、及びそのようなサブオブジェクト


初めに示された例で、#1 は  constant-expression であり、かつ内部での利用方法は  discarded-value\ expression であるので  odr-used でない。よって implicitly capture が有効である。#2 は #1 と同じくラムダの reaching scope の対象とはなるものの、2 を満たさないため、#2 は implicitly capture の対象とはならない。

see also

*1:過去に const floating-point を constant expression にする要求を EWG が CWG に要請した事があるが拒否されている

Java Evaluate Operands before Operation

Java の order of eval についてメモ。

x = 1;
x = ++x + x++; // 3 が保証される

JLS 15.7.2. Evaluate Operands before Operation から引用。

The Java programming language guarantees that every operand of an operator (except the conditional operators &&, ||, and ? :) appears to be fully evaluated before any part of the operation itself is performed.

Consistent/three-way comparison

先日、米国のニューメキシコ州アルバカーキで開催された ISO C++ 委員会による国際会議にて C++20 に追加された Consistent comparison (p0515) についてのメモ。当エントリー内容は同提案書である p0515r2 に基づく*1。また、同提案の採択と共に導入される Library Support for the Spaceship (Comparison) Operator (p0786r0) も参考としている。

P0515 によって、新しいコア言語機能*2 three-way comparison operator (三方向比較演算子)*3が導入された。これは次の形式をとる。

 lhs \lt=\gt rhs

ドラフトでは次のように記される。

 compare-expression:
 shift-expression
 compare-expression \lt=\gt shift-expression

この式は

  •  lhs \lt rhs である場合、< 0 を比較するオブジェクト( -1)を返す
  •  lhs \gt rhs である場合、> 0 を比較するオブジェクト( +1)を返す
  •  lhs rhs が等価/同等である場合に == 0を比較するオブジェクト( 0)を返す


この時、

  • オペランドの1つが bool type であり、もう一方がそうでない場合は ill-formed である。
  • 両方のオペランドが arithmetic type である場合は、通常の arithmetic conversions がオペランドに適用される。arithmetic conversions で、integral type から floating point type への変換以外の narrowing conversion が必要な場合、ill-formed である。
  • それ以外で、オペランドが integral type である場合、その型の prvalue を返す。

    また、

  • three-way comparison operator はユーザー定義でオーバーロードする事ができ、operator <よりも優先度が高く、<<よりも低い*4

  • 通常リテラル 0 と比較できる型を返すが expression template をサポートするなどの他の戻り型も許可される(言語と標準ライブラリで定義された全てのoperator <=>は、下記で述べる std 名前空間内に定義されるカテゴリ型の1つを返す*5。)
  • fundamental な bool, integral, pointer 型の場合、operator <=> は、strong_ordering を返す。
  • pointer 型の場合様々な cv 修飾と derived から base への変換で同種の組み込みの<=>を呼び出す事ができる。また、組み込みの heterogeneous な operator<=>(T*, nullptr_t)もある。
  • 基本的な floating point 型の場合、operator <=>は、partial_ordering を返し*6、引数をより大きな floating point type に拡大する事によって heterogeneously に呼び出す事ができる。
  • enumeration の場合、operator <=>は enumeration の underlying type の <=>と同じものを返す。同じ値を持つ複数の enumerator がある場合(つまり substitutability が保持されない事を意味する)、型が strong_ordering の場合は weak_ordering に調整され、strong_equality の場合は weak_equality に調整される。
  • nullptr_tの場合、operator <=>は、strong_ordering を返し*7、常に等しくなる。
  • コピー可能な配列T[N](すなわち、非静的データメンバ)の場合、T[N] <=> T[N]Tと同じ<=>による型を返す。また、辞書式に要素間の比較を実行する。他の配列の場合、コピーできないため、operator <=>はない*8
  • void 型はオブジェクトタイプとなれないため、void に対するoperator <=>はない。


three-way comparison operator を利用すると、任意の型の全ての比較を明快に記述する事ができる。そのためには、以下で示されているように、適切な比較のためのカテゴリ型を返すoperator <=>を定義する。

  • 任意の型が演算子  \lt をサポートしているのであれば、_orderingを返し、<,>,<=,>=,==,!=を効率的に生成する。そうでなければ、_equalityを返し、==!=を効率的に生成する。
  • 任意の型a == bf(a) == f(b)*9を意味する*10のであれば、strongを返す。そうでなければ、weakを返す。


この関係性は以下のように表す事ができる。

comparison category types

a == bf(a) == f(b)
表す  a_{0}strong
表さない  a_{1}weak
 +
a < b がサポートされて
いる  b_{0}_ordering
いない  b_{1}_equality
 \downarrow
  •  a_{0} + b_{0} \rightarrowstrong_ordering
  •  a_{0} + b_{1} \rightarrowstrong_equality
  •  a_{1} + b_{0} \rightarrowweak_ordering
  •  a_{1} + b_{1} \rightarrowweak_equality


更に、ordering されていない結果を追加で許可するpartial_orderingもサポートされており、これを返す事もできる*11。これらは全てstd名前空間下にカテゴリ型として定義されており、<compare>ヘッダーをインクルードする事によって利用する事ができる*12。下図のように各カテゴリは一定の is-a 関係、すなわち暗黙変換可能な関係を持っている。p0515r2 に良い図があるので、拝借させて頂く。

f:id:Rok1:20171126213023p:plain

それぞれには予め定義された値があり、それぞれの _order に三つの数値、 _equality には二つの数値がある。さらに partial_ordering は数値とは別に順序付けされていない値を表す事ができる。

category -1 0 +1 Non-numeric values
strong_ordering less equal greater -
weak_ordering less equivalent greater -
partial_ordering less equivalent greater unordered
strong_equality equal nonequal -
weak_equality equivalent nonequivalent -

それぞれ以下のように暗黙的に変換される。

値が {less, equal, greater} の strong_ordering 値が {less, equivalent, greater} の weak_ordering 値が {less, equivalent, greater, unordered} の partial_ordering 値が {equal, unequal} の strong_equality
値が {less, equivalent, greater} の weak_ordering(つまり、同じ値を保持する) 値が {less, equivalent, greater} の partial_ordering(つまり、同じ値を保持する) 値が {nonequivalent, greater, unordered} の weak_equality(つまり、unordered または abs() を適用) 値が {equivalent, nonequivalent} の weak_equality(つまり、同じ値を保持する)
値が {less, equivalent, greater} の partial_ordering(つまり、同じ値を保持する) 値が {nonequivalent, equivalent, nonequivalent} の weak_equality(つまり、abs() を適用) - -
値が {unequal, equal, unequal} の strong_equality(つまり、abs() を適用) - - -
値が {nonequivalent, equivalent, nonequivalent} の weak_equality(つまり、abs() を適用) - - -

これらを踏まえた簡単見分け表は以下のようになる。(p0515r0/5.1.2 参照)

To model this Write operator <=> that returns a And we'll generate  a@b as  a \lt=\gt b @ 0 for
Total order std::strong_ordering < > <= >= == !=
Weak order std::weak_ordering < > <= >= == !=
Partial order std::partial_ordering < > <= >= == !=
Equality comparable std::strong_equality == !=
Equivalence comparable std::weak_equality == !=

ここまでのまとめ

[expr.spaceship] がよくまとまっているのでそれの和訳 + 補足。

  • lhs <=> rhs という形式をとる。
  • 両方のオペランドが arithmetic type である場合、通常の arithmetic conversion ([expr.arith.conv]) がオペランドに適用される。その後、
    • integral type から floating point type への変換以外の narrowing conversion([dcl.init.list])が必要となる場合、ill-formed である。
    • そうでなく、オペランドが integral type である場合、結果はstd::strong_ordering型となる。第一オペランド lhs 、第二オペランド rhs とした時、両方のオペランドが算術的に等しい場合は、std::strong_ordering::equal、第一オペランドが第二オペランドよりも算術的に小さい場合( lhs \lt rhs)はstd::strong_ordering::less、それ以外の場合はstd::strong_ordering::greaterを返す。
    • そうでなく、オペランドが floating point である場合、結果はstd::partial_ordering型となる。式a<=>bは、a が b より小さい場合はstd::partial_ordering::less、b より大きい場合はstd::partial_ordering::greater、a が b と等価であるならば、std::partial_ordering::equivalent、そうでなければstd::partial_ordering::unorderedを返す。
  • 両方のオペランドが同じ enumeration type である場合、オペレータはオペランドの underlying type の型に変換し<=>を変換されたオペランドに適用した結果を返す
  • オペランドの少なくとも1つが pointer 型、array-to-pointer conversion([conv.array])、pointer conversions ([conv.ptr])、function pointer conversions([conv.fctptr])、および修飾変換([conv.qual])は両方のオペランドに対して実行され、それらを複合ポインタ型(composite pointer type)([expr.type])にする。オペランドの少なくとも1つが pointer-to-member 型である場合、メンバへのポインタへの変換([conv.mem])と修飾変換([conv.equal])が両方のオペランドで実行され、複合ポインタ型(composite pointer type)([expr.type])にする。両方のオペランドが null pointer 定数であるが、両方とも integer 型でない場合、pointer conversions([conv.ptr])は両方のオペランドで実行され、それらを複合ポインタ型(composite pointer type)([expr.type])にする。全てのケースで変換後、オペランドらは同じ型でなければならない。尚、両方のオペランドが配列である場合、配列からポインタへの変換([conv.array])は適用されない。
  • 複合ポインタ型が関数ポインタ型、ポインタへのポインタ型、またはstd::nullptr_tの場合、結果はstd::strong_equality型である。結果は、オペランドが equal([expr.eq]) を比較した場合std::strong_equality::equal、unequal を比較した場合はstd::strong_equality::unequal、そうでない場合、unspecified である。
  • 複合ポインタ型がオブジェクトポインタ型の場合、p<=>qstd::strong_ordering型である。2つのポインタオペランドpqが equal ([exptr.eq])を比較するとp<=>qstd::strong_ordering::equalを返し、pqが等しくない場合、p<=>qqpより大きい場合はstd::strong_ordering::lessを返し、pqより大きい場合([expr.rel])はstd::strong_ordering::greaterを返す。それ以外の場合、unspecified である。
  • それ以外の場合、プログラムは ill-formed である。
  • 5つの比較カテゴリ型([cmp.categories])(型 std::strong_orderingstd::strong_equalitystd::weak_orderingstd::weak_equalitystd::partial_ordering)は predefined ではない。そのようなクラス型を使用する前に<compare>ヘッダーが含まれていない場合 -- 型が指定されていない暗黙的な使用(例えば、auto specifier を([dcl.spec.auto])介したデフォルトの three-way comparison([class.spaceship])や、ビルトイン演算子の使用) -- は ill-formed である。
  • 既に比較をサポートしている各標準ライブラリ型に対して適切な比較カテゴリタイプを返す非メンバoperator <=>比較が提供される。これは、既に指定された演算子で一貫した結果を得る事ができるよう提供される*13

Generating two-way comparisons: Rewrite

コンパイラ生成のoperator <=>を除いて、比較式  a @ b ( @は比較演算子)の場合、 a@b,  a \lt=\gt b および  b \lt=\gt a の名前探索を実行する。potential candidate <=>が見つかった場合、次のいずれかが真であれば、それを overload resolution に含める。

  • <=>std::*_ordering を返し、 @==, !=, <, >, <=, >= のうちのいずれかである。
  • <=>std::*_equalityを返し、 @==, !=のうちのいずれかである。

    次に、通常の overload resolution rules に基づいて最適な一致を選択する。ただし、 a @ b,  a \lt=\gt b および/または  b \lt=\gt aが曖昧である場合、最終的に a @ b より  a \lt=\gt b a \lt=\gt b より  b \lt=\gt a といった優先順位になる。つまり、

  •  a \lt=\gt b が best match である場合、 a @ b a \lt=\gt b @ 0 に書き換える。

  •  b \lt=\gt a が best match である場合、 a @ b 0 @ b \lt=\gt a に書き換える。

= default

membership 比較の記述を省略するために、ユーザー宣言された比較演算子はデフォルトで=defaultを使用して以下のセマンティックスで memberwise 比較を選択できる。

  • 関数が<=>の場合、パラメータの型は同じでなければならない。また、戻り値の型はstd:: comparison typesのいずれかでなければならない。また、デフォルトの本体は T の基本(left-to-right depth-first)サブメンバとメンバ(宣言順)サブオブジェクトを連続的に比較して<=>を計算し、以下のように等しくない結果が見つかると早期に停止する。
if (auto cmp = lhs.o <=> rhs.o; cmp != 0) return cmp;
return strong_ordering::equal;
  • 関数が6つの比較演算子の場合、パラメータの型は同じでなければならず、戻り値の型は bool でなければならず、デフォルトの本体は Generating two-way comparisons: Rewrite で述べた規則で呼び出され、対応する<=>を呼び出す。

class template common_comparison_category

common_comparison_category は、全てのテンプレート引数を変換できる最も強い比較カテゴリのエイリアスを提供する。

template <class... Ts>
struct common_comparison_category {
    using type = ...
};

common_comparison_category_t は、Tsから次のように計算される型  C である。

  • Ts が空の時、 Cstrong_orderingである。
  • そのほかの場合、各  T_{i} が戻り型  Cmp_{i} をサポートする場合、 C は全ての  Cmp_{i} から変換できる最も強いカテゴリ型である。
  • そうでない場合、 Cvoidである。

Comparison algorithms

[cmp.alg] を参照。

template<class T> constexpr strong_ordering strong_order(const T& a, const T& b);

二つの値を比較し、strong_ordering 型の結果を生成する。

  • もしnumeric_limits<T>::is_iec559が true の場合、ISO/IEC/IEEE 60559 で指定されている totalOrder 操作と一貫性のある型の結果を返す
  • それ以外の場合、その式が well-formed であり、strong_ordering に変換可能であれば a<=>bを返す。
  • それ以外の場合、式a <=> bが well-formed である場合、関数は削除されたものとして定義される。
  • それ以外の場合、式a == ba < bがそれぞれ well-formed で bool に変換可能ならば
    • もしa == bが true なら strong_ordering::equalを返す
    • それ以外の場合、a < bが true なら、strong_ordering::lessを返す
    • それ以外の場合、strong_ordering::greaterを返す
  • それ以外の場合、関数は削除されたものとして定義される。

template<class T> constexpr weak_ordering weak_order(const T& a, const T& b);

二つの値を比較し、weak_ordering 型の結果を生成する。

  • 式が well-formed で weak_ordering に変換可能であれば、a <=> bを返す
  • それ以外の場合、式a <=> bが well-formed である場合、関数は削除されたものとして定義される。
  • それ以外の場合、式a == ba < bがそれぞれ well-formed で bool に変換可能ならば
    • もしa == bが true なら weak_ordering::equivalentを返す
    • それ以外の場合、a < bが true なら weak_ordering::less を返す
    • それ以外の場合、weak_ordering::greaterを返す
  • それ以外の場合、関数は削除されたものとして定義される。

template<class T> constexpr partial_ordering partial_order(const T& a, const T& b);

二つの値を比較し、partial_ordering 型の結果を生成する。

  • 式が well-formed で partial_ordering に変換可能であれば、a <=> bを返す。
  • それ以外の場合、式a <=> bが well-formed である場合、関数は削除されたものとして定義される。
  • それ以外の場合、式a == ba < bがそれぞれ well-formed で bool に変換可能ならば
    • もしa == bが true なら partial_ordering::equivalentを返す
    • それ以外の場合、a < bが true なら partial_ordering::lessを返す
    • それ以外の場合、partial_ordering::greaterを返す
  • それ以外の場合、関数は削除されたものとして定義される。

template<class T> constexpr strong_equality strong_equal(const T& a, const T& b);

二つの値を比較し、strong_equality 型の結果を生成する。

  • 式が well-formed で strong_equality に変換可能であれば、a <=> bを返す。
  • それ以外の場合、式a <=> bが well-formed である場合、関数は削除されたものとして定義される。
  • それ以外の場合、式a == bが well-formed で bool に変換可能ならば
    • もしa == bが true なら strong_equality::equalを返す
    • それ以外の場合、strong_equality::nonequalを返す
  • それ以外の場合、関数は削除されたものとして定義される。

template<class T> constexpr weak_equality weak_equal(const T& a, const T& b);

二つの値を比較し、weak_equality 型の結果を生成する。

  • 式が well-formed で weak_equality に変換可能であれば、a <=> bを返す。
  • それ以外の場合、式a <=> bが well-formed である場合、関数は削除されたものとして定義される。
  • それ以外の場合、式a == bが well-formed で bool に変換可能ならば
    • a == bが true ならweak_equality::equivalentを返す。
    • それ以外の場合、weak_equality::nonequivalentを返す。
  • それ以外の場合、関数は削除されたものとして定義される。

    次に [alg.3way] を参照。
template<class T, class U> constexpr auto compare_3way(const T& a, const U& b);

二つの値を比較し、最も強い適用可能な比較カテゴリ型を戻す。

  • a <=> bが well-formed である場合、a <=> bを返す。
  • それ以外の場合、a == bまたa < bが well-formed で bool に変換可能な場合、a == bが true である場合、std::strong_ordering::equal、そうでない場合、a < bが true である場合、std::strong_ordering::less、そうでない場合、std::strong_ordering::greaterを返す。
  • それ以外の場合、a == b が well-formed で bool に変換可能な場合、a == bが true である場合std::strong_equality::equal、そうでない場合、std::strong_equality::none_equalを返す。
  • それ以外の場合、関数は削除されたものとして定義される。

template<class InputIterator1, class InputIterator2, class Cmp>
  constexpr auto
    lexicographical_compare_3way(InputIterator1 b1, InputIterator1 e1,
                                 InputIterator2 b2, InputIterator2 e2,
                                 Cmp comp)
      -> common_comparison_category_t<decltype(comp(*b1, *b2)), strong_ordering>;
  • Cmpは戻り型が比較カテゴリ型の関数オブジェクト型とする。
  • 辞書学的に 2 つの範囲を比較し、最も強力な適用可能な比較カテゴリの結果を生成する。効果は以下の通りである。
for ( ; b1 != e1 && b2 != e2; void(++b1), void(++b2) )
  if (auto cmp = comp(*b1,*b2); cmp != 0)
    return cmp;
return b1 != e1 ? strong_ordering::greater :
       b2 != e2 ? strong_ordering::less :
                  strong_ordering::equal;

また次のオーバーロードも定義される。

template<class InputIterator1, class InputIterator2>
  constexpr auto
    lexicographical_compare_3way(InputIterator1 b1, InputIterator1 e1,
                                 InputIterator2 b2, InputIterator2 e2);

効果は次の通りである。

return lexicographical_compare_3way(b1, e1, b2, e2,
                                    [](const auto& t, const auto& u) {
                                      return compare_3way(t, u);
                                    });

strong ordered type の例

完全に ordering 付けられた memberwise*14の比較を取得するためには、std::strong_orderingを返す。以下のように記述できる。

class Point {
    int x; int y;
public:
    friend std::strong_ordering operator<=>(const Point&, const Point&) = default;
};

これによってPointは、全ての比較をサポートした事となる。<=>を一度呼び出す事によって、全ての比較をあたかも*15別の実際の関数を作成せずに効率的に実装する。

Point p1, pt2;
if (pt1 == pt2) { /* ... */ } // ok

set<Point> s; // ok
s.insert(pt1); // ok

if (pt1 <= pt2) { /* ... */ } // ok, single call to <=>

非 memberwise に対する ordering は、= defaultの替わりに、独自の定義を作成する*16 *17 *18

class TotallyOrdered : Base {
    string tax_id;
    string first_name;
    string last_name;
public:
    std::strong_ordering operator<=>(const TotallyOrdered& that) const {
        if (auto cmp = (Base&)(*this) <=> (Base&)that; cmp != 0) return cmp;
        if (auto cmp = last_name <=> that.last_name; cmp != 0) return cmp;
        if (auto cmp = first_name <=> that.first_name; cmp != 0) return cmp;
        return tax_id <=> that.tax_id;
    }
};

この提案によって、TotallyOrderedを使用するコードは、完全に ordering された三つの比較を含む全ての比較を実行する事ができ、<=>一つの呼び出しで効率的に実装される(as-if)。

TotallyOrdered to1, to2;
if (to1 == to2) { /*...*/ } // ok
set<TotallyOrdered> s; // ok
s.insert(to1); // ok
if (to1 <= to2) { /*...*/ } // ok, single call to <=>

weakly ordered type の例

weak ordering を定義するためにはstd::weak_orderingを返す。weak ordering を定義したい場面として、例えば以下のように大文字小文字を区別しないような文字列比較が考えられる。これにはメンバの一つをメンバ自身の持つ比較とは異なる方法で比較を行うために、= defaultではなく、独自のカスタム比較を使用する。

class CaseInsensitiveString {
    string s;
public:
    friend std::weak_ordering operator<=>(const CaseInsensitiveString& a, const CaseInsensitiveString& b) {
        return case_insensitive_comare(a.s.c_str(), b.s.c_str());
    }
};

この提案によって、CaseInsensitiveStringを使用するコードは weak ordering の three-way comparison を含む全ての比較を実行でき、<=>一つの呼び出しで効率的に実装される(as-if)。

CaseInsensitiveString cis1, cis2;
if (cis1 == cis2) { /*...*/ } // ok
set<CaseInsensitiveString> s; // ok
s.insert(/*...*/); // ok
if (cis1 <= cis2) { /*...*/ } // ok, performs one comparison operation

さらに、C スタイルのchar*文字列との symmetric heterogeneous comparison*19を提供するには以下のように記述できる。

// add this function in CaseInsensitiveString
 friend std::weak_ordering operator<=>(const CaseInsensitiveString& a, const char* b) {
     return case_insensitive_compare(a.s.c_str(), b);
 }

この提案によって、CaseInsensitiveStringを使用するコードは全ての文字列 string/char* および char*/string で比較を実行でき、<=および他の比較演算子は単一の<=>を使用して効率的に実装される。

Partially ordered type の例

partially ordered なクラスはstd::partial_orderingを返すoperator <=>を定義する事で、コンパイラ生成の比較として全ての双方向の比較を取得 する事ができる。結果は、2つのオブジェクト間に順序関係がない(unordered)である事を表す事ができ、その場合、双方向比較の全てがfalseを返す。

class PersonInFamilyTree {
public:
    std::partial_ordering operator<=>(const PersonInFamilyTree& that) const {
        if (this->is_the_same_person_as(that)) return partial_ordering::equivalent;
        if (this->is_transitive_child_of(that)) return partial_ordering::less;
        if (that.is_transitive_child_of(*this)) return partial_ordering::greater;
        return partial_ordering::unordered;
    }
};

この提案によって、 PersonInFamilyTreeは全ての比較を実行する事ができる。

PersonInFamilyTree per1, per2;
 if (per1 == per2) { /*...*/ } // ok, per1 is per2
else if (per1 < per2) { /*...*/ } // ok, per2 is an ancestor of per1
else if (per1 <= per2) { /*...*/ } // ok, per2 is per1 or an ancestor of per1
else if (per1 > per2) { /*...*/ } // ok, per1 is an ancestor of per2
else if (per1 >= per2) { /*...*/ } // ok, per1 is per2 or an ancestor of per2
else { /*...*/ } // per1 and per2 are unrelated
 if (per1 != per2) { /*...*/ } // ok, per1 is not per2

Equality comparable type の例

equality compare ができ、カスタマイズされた順序付けのあるクラスはstd::strong_equalityを返すoperator <=>を定義しコンパイラ生成の比較として==および!=を取得する事ができる。例えば

class EqualityComparable {
    string name;
    BigInt number1;
    BigInt number2;
public:
    std::strong_equality operator<=>(const EqualityComparable& that) const {
        if (auto cmp = number1 <=> that.number1; cmp != 0) return cmp;
        if (auto cmp = number2 <=> that.number2; cmp != 0) return cmp;
        return name <=> that.name;
    }
};

この提案によって、EqualityComparable==!=を実行する事ができる。

Equivalence comparable type の例

equivalence compare ができ、カスタマイズされた順序付けのあるクラスはstd::weak_equalityを返すoperator<=>を定義しコンパイラ生成の比較として==および!=を取得する事ができる。例えば

class EquivalenceComparable {
    CaseInsensitiveString name;
    BigInt number1;
    BigInt number2;
public:
    std::weak_equality operator<=>(const EquivalenceComparable& that) const {
        if (auto cmp = number1 <=> that.number1; cmp != 0) return cmp;
        if (auto cmp = number2 <=> that.number2; cmp != 0) return cmp;
        return name <=> that.name;
    }
};

この提案によって、EquivalenceComparable==!=を実行する事ができる。

尚この提案が C++20 に導入されるにあたって、std::rel_ops::rel_opsは deprecated とされる。似たような機能を持つ Boost Operators Library も今後の使用は避けた方が良いだろう。また、以下のようなoperator<=のアドレスをテンプレートパラメータやoperator >の左辺オペランドに適用するコードは C++20 以降互換性のないものとなる。解決策としては下記のようにスペースを入れる必要がある*20

X<&Y::operator<=>(); // C++20: NG
x + &operator<=>y; // C++20: NG

X<&Y::operator<= >(); // OK
x + &operator<= >y; // OK

別のホワイトペーパー P0790R0 ではoperator <=>が与える影響と、既存の標準ライブラリの対応がリストアップされている。

*1:同提案のデザイン原則として、Herb Sutter 氏定番の三つの原則が掲げられている。これについては P0707R1 Metaclasses の Design principlesを参照。

*2:これはコア言語機能ではあるが、この新しい演算子の動作は comparison category type と呼ばれる新しい標準ライブラリコンポーネントに依存する形となる。

*3:口語では spaceship operator の名でよく知られている

*4:例えば同じ優先順位だった場合、@ が任意の比較演算子である時、a <=> b @ 0 は、正しく評価されるが、0 @ a <=> b を書くと <=> が矛盾した動きをする事となる。@ が {==, !=} の時は最初に評価されるが、@ が {<, >, <=, >=} の時は二番目に評価される事となる。a<=> b @ 0 と 0 @ a <=> b を一貫させるには <=> は < より少し優先度が高いはずである。

*5:尚、operator <=> の実装の外側にあるユーザーコードでは <=> を直接呼び出すべきではない。あくまでもライブラリや特定の型の実装で利用するべきであり、例えば a < b を ユーザランドで a <=> b < 0と記述するべきではない。

*6:符号付き 0 と NaN の両方をサポートするために partial_ordering を使用する。-0 <=> +0 は equival を返し、NaN <=> anything は何も返さない。

*7:常に equal を返すため、単に strong_equality を返す事もできるが、strong_ordering を返す事でより多くのコンテキストで使用できる。

*8:配列の場合、コピーと比較の一貫性を維持するために配列が言語によってコピーできない場合は比較を行わない。配列同士の場合、配列からポインタへの変換は適用されないため、arr1 <=> arr2 は ill-formed である事に注意

*9:f は 非 private な const インタフェースを使用してアクセス可能な comparison-salient の状態を読み込む

*10:substitutability

*11:つまり、strong ordering, weak ordering は六つの比較演算子を全てを許可し、x < y, x == y, x > y のどれかが true でなければならないが、partial ordering は六つの比較演算子の全てを許可するが、x < y, x == y, x > y のどれも true である必要はない。strong ordering, weak ordering の特徴はTrichotomy のままである。

*12:[expr.spaceship]/10

*13:コンテナ(文字列含む)、string_view, optional, any, unique_ptr 及び shared_ptr などのいくつかの std:: 型はカスタムセマンティックスを取得するためにカスタム演算子 <=> を宣言して定義する。特に、string と string_view は strcmp と同等のものが得られ、strcmp とは異なり組み込みの null が尊重される点で優れている点に留意。また、complex といった 一部の std:: 型で <=> は strong_equality などの弱い比較カテゴリを返す。

*14:各基本またはメンバのサブオブジェクトについての略語であると本文にて述べられている

*15:pt1 == pt2 の場合、quality implementation が内部の2つの int メンバに対して == を呼び出す事が期待されるため、ここでは as-if と述べられている。

*16:メンバが strong_ordering を持たない場合、該当コードはコンパイル時にエラーを発生させる。これによって、比較のセマンティックスと実際の実装が異なっていたとしても、コンパイル時に捕らえる事ができる

*17:ユーザー定義の operator <=> が total order である事を保証する最も効果的な方法は、全てのデータメンバ(基底)を明示的に比較する事である。データメンバを余らせると、a == b が f(a) == f(b) であるという substitutability を提供できなくなるリスクがある。

*18:ここで memberwise <=> と 0 を比較する事は、個々のデータメンバの比較カテゴリを agnostic にするためのもの(比較カテゴリは変化する可能性がある)であり、意図的なものである。

*19:対称異種比較と言ったところか。weak ordering の定義そのままである

*20:本文によれば、唯一の後方ソースコードに対する非互換性であるとのこと。また、このようなコードをスペースなしで動作させるための特別な構文解析ルールを採用する事もできるが、利益があまりにも少ないとのこと。