yohhoyの日記

技術的メモをしていきたい日記

"Poison-pill" overload for CPO

C++20標準ライブラリで導入された Customization Point Object (CPO)定義で必要となる Poison-pill*1 オーバーロードについてメモ。std::ranges::swapstd::ranges::begin/endなどのCPO定義で利用される。

本記事の内容はStackOverflowで見つけた質問と回答に基づく。

std::ranges名前空間でのCPO定義位置からは、親名前空間stdで定義されるカスタマイズポイント同名の制約のない関数テンプレート(std::swapstd::begin/end)が "見えて” しまうため、同関数テンプレートシグネチャをdelete宣言してオーバーロード候補から除外する(★印)。

// std::ranges::swap CPO実装イメージ(超簡略化版)
namespace std::ranges {
  namespace swap_impl {
    template<class T> void swap(T&, T&) = delete;  // ★

    struct swap_fn {
      template<class T1, class T2>
        requires /* C++20 18.4.9/p2/b1 */
      constexpr void operator()(T1& e1, T2& e2) const {
        // 非修飾名・ADL経由でカスタマイズポイント(swap)を呼び出す
        swap(e1, e2);
      }
      // ...
    };
  }

  // std::ranges::swap CPO定義
  inline namespace swap_cpo {
    inline constexpr swap_impl::swap_fn swap{};
    // Hidden friendとの名前衝突回避のためインライン名前空間が必要
    // 詳細説明は提案文書 P1895R0 を参照のこと
  }
}

C++20 Rangesライブラリの前身、Ranges TS検討当時の提案文書 P0370R3 Ranges TS Design Updates Omnibus より一部引用。

unqualified name lookup for the name swap could find the unconstrained swap in namespace std either directly - it’s only a couple of hops up the namespace hierarchy - or via ADL if std is an associated namespace of T or U. If std::swap is unconstrained, the concept is "satisfied" for all types, and effectively useless. The Ranges TS deals with this problem by requiring changes to std::swap, a practice which has historically been forbidden for TSs. Applying similar constraints to all of the customization points defined in the TS by modifying the definitions in namespace std is an unsatisfactory solution, if not an altogether untenable.


We propose a combination of the approach used in N4381 with a "poison pill" technique to correct the lookup problem. Namely, we specify that unqualified lookup intended to find user-defined overloads via ADL must be performed in a context that includes a deleted overload matching the signature of the implementation in namespace std. E.g., for the customization point begin, the unqualified lookup for begin(E) (for some arbitrary expression E) is performed in a context that includes the declaration void begin(const auto&) = delete;. This "poison pill" has two distinct effects on overload resolution. First, the poison pill hides the declaration in namespace std from normal unqualified lookup, simply by having the same name. Second, for actual argument expressions for which the overload in namespace std is viable and found by ADL, the poison pill will also be viable causing overload resolution to fail due to ambiguity. The net effect is to preclude the overload in namespace std from being chosen by overload resolution, or indeed any overload found by ADL that is not more specialized or more constrained than the poison pill.

C++20(N4861) 16.4.2.2.6/p6より引用(下線部は強調)。

[Note: Many of the customization point objects in the library evaluate function call expressions with an unqualified name which results in a call to a program-defined function found by argument dependent name lookup (6.5.2). To preclude such an expression resulting in a call to unconstrained functions with the same name in namespace std, customization point objects specify that lookup for these expressions is performed in a context that includes deleted overloads matching the signatures of overloads defined in namespace std. When the deleted overloads are viable, program-defined overloads need be more specialized (13.7.6.2) or more constrained (13.5.4) to be used by a customization point object. -- end note]

関連URL

std::search_nアルゴリズムとゼロ長サブシーケンス一致

N要素からなるサブシーケンス検索を行うC++標準アルゴリズムstd::search_nでは、“0個の任意要素からなるサブシーケンス” は常に先頭位置にマッチする。

#include <algorithm>

int arr[5] = {0, 10, 10, 20, 30};

// 2個の要素10からなるサブシーケンス
auto itr1 = std::search_n(arr, arr + 5, 2, 10);
assert(itr1 == arr + 1);  // index=1

// 2個の要素20からなるサブシーケンス
auto itr2 = std::search_n(arr, arr + 5, 2, 20);
assert(itr2 == arr + 5);  // NOT FOUND

// 0個の要素42からなるサブシーケンス
auto itr3 = std::search_n(arr, arr + 5, 0, 42);
assert(itr3 == arr + 0);  // index=0

C++03 25.1.9/p4-6より引用。

template<class ForwardIterator, class Size, class T>
  ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count,
           const T& value);

template<class ForwardIterator, class Size, class T,
         class BinaryPredicate>
  ForwardIterator
    search_n(ForwardIterator first, ForwardIterator last, Size count,
          const T& value, BinaryPredicate pred);

4 Requires: Type T is EqualityComparable (20.1.1), type Size is convertible to integral type (4.7, 12.3).
5 Effects: Finds a subsequence of equal values in a sequence.
6 Returns: The first iterator i in the range [first, last - count) such that for any non-negative integer n less than count the following corresponding conditions hold: *(i + n) == value, pred(*(i + n),value) != false. Returns last if no such iterator is found.

関連URL

requires制約とテンプレート特殊化の関係

C++20コンセプトで導入されたrequires節と、テンプレート特殊化の組み合わせには注意が必要。

例えば制約付きプライマリテンプレート(#1)に対してdouble型で明示的特殊化(#2)しようとしても、下記記述コードでは#2定義でill-formedになる。これは#1のrequires節によりT=doubleのときプライマリテンプレート不在とみなされるため。

#include <concepts>

// #1 プライマリテンプレート(?)
template<typename T>
  requires (!std::floating_point<T>)
int f(T) { return 0; }

// #2 double型による特殊化
template<>
int f(double) { return 1; }  // NG

assert( f(42) == 0 );
assert( f(3.14) == 1 );

テンプレートの明示的特殊化ではなく通常関数によるオーバーロードを行うか、プライマリテンプレートの関連制約(requires節)を削除すれば期待通り動作する。

// #1 制約付きテンプレート
template<typename T>
  requires (!std::floating_point<T>)
int f(T) { return 0; }

// #2 double型でオーバーロード
int f(double) { return 1; }  // OK
// #1 プライマリテンプレート
template<typename T>
int f(T) { return 0; }

// #2 double型による特殊化
template<>
int f(double) { return 1; }  // OK

C++20 13.9.3/p12より引用。

[Note: An explicit specialization of a constrained template is required to satisfy that template's associated constraints (13.5.2). The satisfaction of constraints is determined when forming the template name of an explicit specialization in which all template arguments are specified (13.3), or, for explicit specializations of function templates, during template argument deduction (13.10.2.6) when one or more trailing template arguments are left unspecified. -- end note]

関連URL

電子書籍"Pro TBB: C++ Parallel Programming with Threading Building Blocks"

Intel oneTBB(oneAPI Threading Building Blocks)によるC++並列プログラミングの電子書籍。PDF形式(754頁)がCC-NC-ND 4.0ライセンスで公開されている。

コンセプトのパラメータ置換失敗はハードエラーではない

C++2a(C++20)コンセプトにおける原始制約(atomic constraint)では、パラメータ置換(parameter mapping)の失敗はハードエラー(ill-formed)を引き起こさず、その制約式を満たさない(not satisfied)と解釈される。C++17現在はstd::void_tstd::conjunctionを駆使した難解なテンプレートメタプログラミング技法が要求されるが、C++2aでは単純な制約式記述によるコンセプト定義により代替される。はず。\\\\٩( 'ω' )و ////

ある型TT::value_type = int型を定義するか確認するメタ関数/コンセプトIntContainerの実装例。

// C++17
#include <type_traits>

// 補助メタ関数 HasValueType
template <class, class = std::void_t<>>
struct HasValueType
  : std::false_type {};
template <class T>
struct HasValueType<T, std::void_t<typename T::value_type>>
  : std::true_type {};

// 補助メタ関数 IntValueType
template <typename T>
struct IntValueType
  : std::is_same<typename T::value_type, int> {};

template <typename T>
using IntContainer
  = std::conjunction<HasValueType<T>, IntValueType<T>>;
// std::conjunctionメタ関数を用いてメタ関数HasValueTypeが真のときのみ
// メタ関数IntValueTypeをインスタンス化する必要がある(&&ではダメ)

static_assert( IntContainer<std::list<int>>::value);
static_assert(!IntContainer<std::list<char>>::value);
static_assert(!IntContainer<int>::value);
// C++2a
#include <concepts>

template <typename T>
concept IntContainer = std::same_as<typename T::value_type, int>;
// T::value_typeがint以外 or 無効な場合は制約式がnot satisfiedとなる

static_assert( IntContainer<std::list<int>>);
static_assert(!IntContainer<std::list<char>>);
static_assert(!IntContainer<int>);

ノート:制約式IntContainer<int>の正規形はstd::same_as<typename T::value_type, int>(T=int)よりstd::is_same_v<T↦typename int::value_type, U↦int>std::is_same_v<T↦int, U↦typename int::value_type>となり*1typename int::value_typeは無効な型のため原始制約はいずれも満たされない(not satisfied)。たぶん\( 'ω' )/

C++2a DIS(N4681) 13.5.1.2/p1, p3, 13.5.3/p1-2より一部引用(下線部は強調)。

1 An atomic constraint is formed from an expression E and a mapping from the template parameters that appear within E to template arguments that are formed via substitution during constraint normalization in the declaration of a constrained entity (and, therefore, can involve the unsubstituted template parameters of the constrained entity), called the parameter mapping (13.5.2). (snip)

3 To determine if an atomic constraint is satisfied, the parameter mapping and template arguments are first substituted into its expression. If substitution results in an invalid type or expression, the constraint is not satisfied. Otherwise, the lvalue-to-rvalue conversion (7.3.1) is performed if necessary, and E shall be a constant expression of type bool. The constraint is satisfied if and only if evaluation of E results in true. If, at different points in the program, the satisfaction result is different for identical atomic constraints and template arguments, the program is ill-formed, no diagnostic required. (snip)

1 The normal form of an expression E is a constraint (13.5.1) that is defined as follows:

  • (snip)
  • The normal form of a concept-id C<A1, A2, ..., An> is the normal form of the constraint-expression of C, after substituting A1, A2, ..., An for C's respective template parameters in the parameter mappings in each atomic constraint. If any such substitution results in an invalid type or expression, the program is ill-formed; no diagnostic is required. [Example:
template<typename T> concept A = T::value || true;
template<typename U> concept B = A<U*>;
template<typename V> concept C = B<V&>;

Normalization of B's constraint-expression is valid and results in T::value (with the mapping T ↦ U*) ∨ true (with an empty mapping), despite the expression T::value being ill-formed for a pointer type T. Normalization of C's constraint-expression results in the program being ill-formed, because it would form the invalid type V&* in the parameter mapping. --end example]

  • The normal form of any other expression E is the atomic constraint whose expression is E and whose parameter mapping is the identity mapping.

2 The process of obtaining the normal form of a constraint-expression is called normalization. [Note: Normalization of constraint-expressions is performed when determining the associated constraints (13.5.1) of a declaration and when evaluating the value of an id-expression that names a concept specialization (7.5.4). --end note]

関連URL

*1:ここではパラメータマッピングを ↦ 記号で表記する。記号 ∧ は制約式の conjunction を表す(13.5.1.1)。

コンセプトと短絡評価

C++2a(C++20)コンセプトの制約式(constraint-expression)では、論理演算&&, ||は短絡評価される。*1

C++17現在のテンプレートメタプログラミングではstd::conjunction, std::disjunctionメタ関数を必要とするが、C++2aコンセプト導入により自然な制約記述が可能となる。

T型が「std::atomic<T>が常にロックフリー(lock free)か否か」を判定するメタ関数は、std::conjunctionメタ関数を利用して下記の通りに記述できる。

// C++17
#include <atomic>
#include <type_traits>

template <typename T>
struct is_lock_free_impl
  : std::bool_constant<std::atomic<T>::is_always_lock_free> { };

template <typename T>
using is_lock_free
  = std::conjunction<std::is_trivially_copyable<T>, is_lock_free_impl<T>>;

メタ関数is_lock_freeの定義で&&演算子を使った場合、左辺std::is_trivially_copyable<T>::valueの真偽値に関わらず右辺is_lock_free_impl<T>::valueインスタンス化が行われる。

conjunction/disjunctionと短絡インスタンス化
// C++2a
#include <atomic>
#include <type_traits>

// コンセプトis_lock_free
template <typename T>
concept is_lock_free
  = std::is_trivially_copyable_v<T> && std::atomic<T>::is_always_lock_free;

// (std::atomic<int>型がロックフリーに振る舞う処理系を仮定)
static_assert( is_lock_free<int>, "int is lock-free" );  // OK

// 非Trivially Copyableなクラス型X
struct X { ~X() {} };
static_assert( !is_lock_free<X>, "X is not lock-free" );  // OK

C++2a DIS(N4681) 13.5.1.1/p1-3より引用(下線部は強調)。

1 There are two binary logical operations on constraints: conjunction and disjunction. [Note: These logical operations have no corresponding C++ syntax. For the purpose of exposition, conjunction is spelled using the symbol ∧ and disjunction is spelled using the symbol ∨. The operands of these operations are called the left and right operands. In the constraint AB, A is the left operand, and B is the right operand. --end note]
2 A conjunction is a constraint taking two operands. To determine if a conjunction is satisfied, the satisfaction of the first operand is checked. If that is not satisfied, the conjunction is not satisfied. Otherwise, the conjunction is satisfied if and only if the second operand is satisfied.
3 A disjunction is a constraint taking two operands. To determine if a disjunction is satisfied, the satisfaction of the first operand is checked. If that is satisfied, the disjunction is satisfied. Otherwise, the disjunction is satisfied if and only if the second operand is satisfied.

関連URL

*1:C++コンセプト制約式を用いたオーバーロード解決においては、演算子 &&, ||, ! がブール代数的な論理積論理和/論理否定から期待されるセマンティクスとは多少異なる動作をする。詳細は C++コンセプトとド・モルガンの法則 を参照のこと。

関数/ラムダ式への値束縛

プログラミング言語Pythonにおいて、関数やラムダ式にローカル変数の「値」を束縛する方法。

下記コードでは “引数x定義時の値nで冪乗” する関数を個別生成するつもりが、実際には “引数x変数nの値で冪乗” する同一の関数が生成される。forループ終了後の変数nは値3となっており、プログラマの期待に反する実行結果となる。

# 関数
ops = []
for n in range(4):
    def fn(x):
        return x ** n
    ops.append(fn)
print([f(2) for f in ops])  # [8, 8, 8, 8]

# ラムダ式
ops = []
for n in range(4):
    ops.append(lambda x: x ** n)
print([f(2) for f in ops])  # [8, 8, 8, 8]

関数やラムダ式のデフォルト引数値は定義時に評価される*1ことを利用し、次のようにローカル変数の値を束縛できる。

# 関数
ops = []
for n in range(4):
    def fn(x, n=n):
        return x ** n
    ops.append(fn)
print([f(2) for f in ops])  # [1, 2, 4, 8]

# ラムダ式
ops = []
for n in range(4):
    ops.append(lambda x, n=n: x ** n)
print([f(2) for f in ops])  # [1, 2, 4, 8]

他の実装手段として、関数/ラムダ式入れ子にし外側だけ評価する方法や、 functools.partial 関数を利用する方法がある。

# 関数の入れ子
ops = []
for n in range(4):
    def fn(n):
        def fn0(x):
            return x ** n
        return fn0
    ops.append(fn(n))
print([f(2) for f in ops])  # [1, 2, 4, 8]

# ラムダ式の入れ子と即時評価
ops = []
for n in range(4):
    fn = (lambda n: lambda x: x ** n)(n)
    ops.append(fn)
print([f(2) for f in ops])  # [1, 2, 4, 8]
from functools import partial

# 関数+partial
ops = []
for n in range(4):
    def fn(x, n):
        return x ** n
    ops.append(partial(fn, n=n))
print([f(2) for f in ops])  # [1, 2, 4, 8]

# ラムダ式+partial
ops = []
for n in range(4):
    fn = lambda x, n: x ** n
    ops.append(partial(fn, n=n))
print([f(2) for f in ops])  # [1, 2, 4, 8]

関連URL