yohhoyの日記

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

コンセプト制約式の包摂関係とオーバーロード解決

C++ C++2a

C++2a(C++20)で導入されるコンセプト(concept)に関して、制約式(constraint-expression)間の包摂(subsume)ルールに基づくオーバーロード解決のメモ。

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

要約：制約式の包摂関係(subsumption relation)判定では、制約を構成するトークン列が同じというだけではダメで、C++ソースコード上での記述位置（＝構文木におけるノード）の同一性が考慮される。こんなん分かる気がしない_(:3｣∠)_

制約式を指定した2つの関数オーバーロード定義において、コンセプト名とテンプレート名では制約式の包摂関係の判断規則が異なるため、★箇所におけるオーバーロード解決の振る舞いが変化する。

// C++2a(N4830)
#if コンセプト
template <typename T> concept C1 = true;  // #1
template <typename T> concept C2 = true;  // #2
#elif 変数テンプレート
template <typename T> inline constexpr bool C1 = true;
template <typename T> inline constexpr bool C2 = true;
#endif

// [A] 制約式C1<T> && C2<T>
template <typename T>
  requires C1<T> && C2<T>  // #3
constexpr int foo() { return 0; }

// [B] 制約式C1<T>
template <typename T>
  requires C1<T>           // #4
constexpr int foo() { return 1; }

foo<int>();  // ★ [A]/[B] or...?
C1, C2がコンセプト名の場合
制約式C1<T> && C2<T>は制約式C1<T>を包摂する(subsume)ため、より強く制約された(more constrained) 関数[A] が選択される。正規化(normalization)によって前者はtrue#1∧true#2に、後者はtrue#1となる。このとき原子制約(atomic constraint) true#1は “同一の式(the same expression)” から構成されるため、C1<T> && C2<T> subsume C1<T>という包摂関係が成立する。
C1, C2が非コンセプト名（テンプレート）の場合
制約式C1<T> && C2<T>と制約式C1<T>は互いに包摂関係になく、関数呼び出しのオーバーロード解決は曖昧となるためプログラムはill-formed。正規化(normalization)によって前者はC1<T>#3∧C2<T>#3に、後者はC1<T>#4となる。このとき原子制約C1<T>#3とC1<T>#4は “同一の式(the same expression)” からは構成されておらず、無関係な制約式として解釈される。

原子制約の同一性(identical)判定基準は、Concepts TS時点の (PDF)P0717R1 Semantic constraint matching for concepts にて次のように説明される（下線部は強調）。

Equivalence during partial ordering
We propose to use a different model for determining whether two atomic constraints are equivalent. Tersely, we can describe this as follows: two atomic constraints are equivalent only if they originate from the same source-level construct.

メモ：C++20標準ライブラリ提供のコンセプト実装にて exposition only なコンセプトを多用しているのは、そのコンセプト名から期待される包摂関係が成り立つよう考慮した結果と思われる。

2019-09-11追記：P0717R1を実装したVisual Studio 2019 16.3 Preview 2で動作確認を行ったところ、上記解釈通りの実行結果「コンセプト名では[A]を選択／非コンセプト名ではオーバーロード解決が曖昧」が得られた。後者のエラー出力は下記の通り：

error C2668: 'foo': ambiguous call to overloaded function
message : could be 'int foo<int>(void)'
message : or       'int foo<int>(void)'
message : while trying to match the argument list '()'

2019-10-17追記：GCC 10.0.0 20191015(experimental)でも上記解釈通り動作することを確認。後者のエラー出力は下記の通り：

In function 'int main()':
error: call of overloaded 'f<int, int>()' is ambiguous
  |   return f<int, int>();
  |                      ^
note: candidate: 'constexpr int f() [with T = int; U = int]'
  | constexpr int f() { return 1; }  // #1
  |               ^
note: candidate: 'constexpr int f() [with T = int; U = int]'
  | constexpr int f() { return 2; }  // #2
  |               ^

C++2a言語仕様

N4830*1(C++2a WD) 13.4.1.2/p1-2, 13.4.3/p1-2, 13.4.4/p1-4, 13.6.6.2/p2より一部引用（下線部は強調）。

1 An atomic constraint is formed from an expression E and a mapping from the template parameters that appear within E to template arguments involving the template parameters of the constrained entity, called the parameter mapping (13.4.2). [Note: Atomic constraints are formed by constraint normalization (13.4.3). E is never a logical AND expression (7.6.14) nor a logical OR expression (7.6.15). -- end note]
2 Two atomic constraints are identical if they are formed from the same expression and the targets of the parameter mappings are equivalent according to the rules for expressions described in 13.6.6.1.

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

  • The normal form of an expression ( E ) is the normal form of E.
  • The normal form of an expression E1 || E2 is the disjunction (13.4.1.1) of the normal forms of E1 and E2.
  • The normal form of an expression E1 && E2 is the conjunction of the normal forms of E1 and E2.
  • The normal form of an id-expression of the form C<A1, A2, ..., An>, where C names a concept, 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. (snip)
  • 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.4.1) of a declaration and when evaluating the value of an id-expression that names a concept specialization (7.5.4). -- end note]

1 A constraint P subsumes a constraint Q if and only if, for every disjunctive clause Pi in the disjunctive normal form132 of P, Pi subsumes every conjunctive clause Qj in the conjunctive normal form133 of Q, where

  • a disjunctive clause Pi subsumes a conjunctive clause Qj if and only if there exists an atomic constraint Pia in Pi for which there exists an atomic constraint Qjb in Qj such that Pia subsumes Qjb, and
  • an atomic constraint A subsumes another atomic constraint B if and only if the A and B are identical using the rules described in 13.4.1.2.

[Example: Let A and B be atomic constraints (13.4.1.2). The constraint A ∧ B subsumes A, but A does not subsume A ∧ B. The constraint A subsumes A ∨ B, but A ∨ B does not subsume A. Also note that every constraint subsumes itself. -- end example]
脚注132) A constraint is in disjunctive normal form when it is a disjunction of clauses where each clause is a conjunction of atomic constraints. (snip)
脚注133) A constraint is in conjunctive normal form when it is a conjunction of clauses where each clause is a disjunction of atomic constraints. (snip)

2 [Note: The subsumption relation defines a partial ordering on constraints. This partial ordering is used to determine

  • (snip)
  • the partial ordering of function templates (13.6.6.2).

-- end note]
3 A declaration D1 is at least as constrained as a declaration D2 if

  • D1 and D2 are both constrained declarations and D1's associated constraints subsume those of D2; or
  • D2 has no associated constraints.

4 A declaration D1 is more constrained than another declaration D2 when D1 is at least as constrained as D2, and D2 is not at least as constrained as D1. (snip)

2 Partial ordering selects which of two function templates is more specialized than the other by transforming each template in turn (see next paragraph) and performing template argument deduction using the function type. The deduction process determines whether one of the templates is more specialized than the other. If so, the more specialized template is the one chosen by the partial ordering process. If both deductions succeed, the partial ordering selects the more constrained template as described by the rules in 13.4.4.

§13.4.1.2 [temp.constr.atomic]/p2 で言及される "the same expression" の解釈については、https://github.com/cplusplus/draft/issues/2554 が挙げられている。より明確化されたWordingへと変更されるかも。

2020-01-22追記：C++2a WD (PDF)N4842にて構文規則のフォントが変更され*2、言語仕様から本来の意図を読み取りやすくなった。

関連URL

*1:http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/n4830.pdf

*2:N4843 Editors' Report: "The typeface used for grammar productions has been changed from italic to a slanted sans-serif font in order to distinguish grammar productions from defined terms."