模板部分排序-为什么部分推导在这里成功？

Question

考虑下面这个简单的（在模板问题中算是简单的）例子：

#include <iostream>

template <typename T>
struct identity;

template <>
struct identity<int> {
    using type = int;
};

template<typename T> void bar(T, T ) { std::cout << "a\n"; }
template<typename T> void bar(T, typename identity<T>::type) { std::cout << "b\n"; }

int main ()
{
    bar(0, 0);
}

无论是clang还是gcc都会打印出"a"。根据[temp.deduct.partial]和[temp.func.order]中的规则，在确定部分排序时，我们需要合成一些唯一的类型。因此我们有两个推导的尝试：

+---+-------------------------------+-------------------------------------------+
|   | Parameters                    | Arguments                                 |
+---+-------------------------------+-------------------------------------------+
| a | T, typename identity<T>::type | UniqueA, UniqueA                          |
| b | T, T                          | UniqueB, typename identity<UniqueB>::type |
+---+-------------------------------+-------------------------------------------+

针对 "b" 的推论，根据 Richard Corden的答案，表达式 typename identity<UniqueB>::type 被视为类型而不是被评估。也就是说，它将合成为以下形式：

+---+-------------------------------+--------------------+
|   | Parameters                    | Arguments          |
+---+-------------------------------+--------------------+
| a | T, typename identity<T>::type | UniqueA, UniqueA   |
| b | T, T                          | UniqueB, UniqueB_2 |
+---+-------------------------------+--------------------+

很明显，“b”的推导失败了，因为它们是两种不同的类型，所以你不能同时将“T”推导到它们。

然而，在我看来，“A”的推导也应该失败。对于第一个参数，你会匹配“T == UniqueA”。第二个参数是一个非推导上下文 - 所以如果“UniqueA”可转换为“identity::type”，那么这个推导是否成功呢？后者是一种替换失败，所以我不知道这个推导怎么可能成功。

在这种情况下，gcc和clang为什么更喜欢使用“a”重载呢？

- Barry

---

我认为https://dev59.com/GnM_5IYBdhLWcg3w43lt#1182688包含相关信息。 - bogdan

@bogdan 是的，添加“如果特定的P不包含参与模板参数推断的模板参数，则该P不用于确定顺序。”会澄清这个问题。但它并不能解决 typename identity<UniqueB>::type --> UniqueB_2 的问题。你想将所有这些内容合并成一个答案吗？ - Barry

很抱歉，我说过我会在“明天”写答案；显然这没有发生，而且，无论如何，我不确定它是否会为此带来有用的东西。真正需要的是来自权威来源的答案，并且是标准中的清晰文本。我想现在先不写答案了。 - bogdan

提议的解决方案 http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_active.html#1391 可能会处理这个问题。 - T.C.

@T.C. 是的，看起来是这样的。对于 temp.deduct.partial 的更改将排除 typename identity<T>::type 参数的考虑。 - Barry

Answer 1

根据评论，我认为函数模板部分排序算法有几个方面在标准中不清楚或未指定，这在您的示例中体现出来。

更有趣的是，MSVC（我测试了12和14）拒绝了调用，称其具有二义性。我认为标准中没有任何东西可以确凿地证明哪个编译器是正确的，但我想我可能知道差异来自何处；下面有一个关于此的注释。

您的问题（以及这个）促使我进行更多的调查以了解事物的运作方式。我决定撰写此答案，不是因为我认为它具有权威性，而是为了将我找到的信息组织在一个地方（在评论中无法容纳）。我希望这将是有用的。

---

首先， 问题1391的提议解决方案。我们在评论和聊天中进行了广泛讨论。我认为，尽管它确实提供了一些澄清，但也引入了一些问题。它将[14.8.2.4p4]更改为（加粗的新文本）：每个来自参数模板的被提名的类型和相应的来自参数模板的类型都用作P和A的类型。如果特定的P不包含参与模板参数推导的模板参数，则不使用该P来确定顺序。我认为这不是一个好主意，原因有几个：

• If P is non-dependent, it doesn't contain any template parameters at all, so it doesn't contain any that participate in argument deduction either, which would make the bold statement apply to it. However, that would make template<class T> f(T, int) and template<class T, class U> f(T, U) unordered, which doesn't make sense. This is arguably a matter of interpretation of the wording, but it could cause confusion.
• It messes with the notion of used to determine the ordering, which affects [14.8.2.4p11]. This makes template<class T> void f(T) and template<class T> void f(typename A<T>::a) unordered (deduction succeeds from first to second, because T is not used in a type used for partial ordering according to the new rule, so it can remain without a value). Currently, all compilers I've tested report the second as more specialized.

• It would make #2 more specialized than #1 in the following example:

  #include <iostream>
  
  template<class T> struct A { using a = T; };
  
  struct D { };
  template<class T> struct B { B() = default; B(D) { } };
  template<class T> struct C { C() = default; C(D) { } };
  
  template<class T> void f(T, B<T>) { std::cout << "#1\n"; } // #1
  template<class T> void f(T, C<typename A<T>::a>) { std::cout << "#2\n"; } // #2
  
  int main()
  {
     f<int>(1, D());
  }
  

  (#2's second parameter is not used for partial ordering, so deduction succeeds from #1 to #2 but not the other way around). Currently, the call is ambiguous, and should arguably remain so.

---

在查看了Clang对于部分排序算法的实现后，我认为标准文本可以做出如下修改以反映实际情况：

保留[p4]不变，在[p8]和[p9]之间添加以下内容：

对于

/ 对：

• 如果

  是非依赖的，则仅当

  和是相同类型时，才会认为推导成功。

• 不会对

  中出现的非推导上下文进行推导模板参数的替换，也不会影响推导过程的结果。

• 如果成功地推导出了

  的所有模板参数的模板参数值，除了那些仅出现在非推导上下文中的参数，那么推导就被认为是成功的（即使在特定的

  / 对的推导过程中，一些用于

  的参数最终仍然没有值）。

注：

• 关于第二个要点：[14.8.2.5p1] 讨论了找到模板参数值，使得在替换推导的值后（称为推导出的A），P与A兼容。这可能会引起对部分排序实际发生的混淆；没有进行任何替换。
• 在某些情况下，MSVC似乎没有实现第三个要点。有关详细信息，请参见下一节。
• 第二和第三个要点旨在涵盖P具有形式如A<T，typename U :: b>的情况，这些情况不包含问题1391中的措辞。

将当前[p10]更改为：

如果且仅当：

• 对于用于确定排序的每一对类型，来自 F 的类型至少与来自 G 的类型一样具体，且
• 使用转换后的 F 作为参数模板和 G 作为参数模板执行推导时，在所有类型对中完成推导后，用于确定排序的来自 G 的类型中使用的所有模板参数都具有值，并且这些值在所有类型对中保持一致。

如果 F 至少与 G 一样具体且 G 不至少与 F 一样具体，则 F 比 G 更具体。

将当前整个 [p11] 改为注释。

解决方案1391条附加的备注需要进行调整，以适用于[14.8.2.1]，但不适用于[14.8.2.4]。

---

对于MSVC，在某些情况下，似乎需要为P中的所有模板参数在特定的P / A配对的推导过程中接收值，以便从A到P的推导成功。我认为这可能是你的示例和其他示例中实现差异的原因，但我至少看到过一种情况，上述规则似乎不适用，所以我不确定该相信什么。

另一个例子是：将template<typename T> void bar(T, T)更改为template<typename T, typename U> void bar(T, U)，则会交换结果：在Clang和GCC中，调用是不明确的，但在MSVC中解析为b。

有一个不适用上述规则的例子：

#include <iostream>

template<class T> struct A { using a = T; };
template<class, class> struct B { };

template<class T, class U> void f(B<U, T>) { std::cout << "#1\n"; }
template<class T, class U> void f(B<U, typename A<T>::a>) { std::cout << "#2\n"; }

int main()
{
   f<int>(B<int, int>());
}

这会在Clang和GCC中选择#2，正如预期的那样，但是MSVC将调用拒绝为不明确；不知道为什么。

---

在标准中描述的部分排序算法提到需要合成“唯一类型、值或类模板”以生成参数。Clang通过不合成任何东西来管理它，而是直接使用依赖类型的原始形式（如声明）并进行双向匹配。这是有道理的，因为替换合成类型不会添加任何新信息。它无法改变A类型的形式，因为通常没有办法确定替换形式可以解析为哪些具体类型。合成类型是未知的，这使它们非常类似于模板参数。

当遇到一个非推导上下文的P时，Clang的模板参数推导算法会简单地跳过它，在该特定步骤返回“成功”。这不仅发生在部分排序期间，还发生在所有类型的推导中，不仅在函数参数列表的顶层，还在以复合类型形式遇到非推导上下文时进行递归。我第一次看到这个时感到惊讶，但经过思考，它当然是有道理的，并且符合标准（在[14.8.2.5p4]中，“[...]不参与类型推导[...]”）。

这与Richard Corden关于他的回答所说的一致，但我必须实际看到编译器代码才能理解所有含义（这不是他答案的问题，而是我的问题 - 作为程序员，总是在思考代码）。

我在这个答案中包含了更多关于Clang实现的信息。

- bogdan

---

太棒了。一如既往。+1 - Columbo

我刚刚注意到，我给这个答案点了赞并设置了悬赏，但实际上从未接受过它。糟糕？无论如何，如果你在附近，我有另一个问题。 - Barry

@jackX 我不同意“只有当”的说法；在许多情况下，模板参数出现在推导和非推导上下文中，即使推导仍然失败。否则，在您的示例中，使用#1作为参数和#2作为参数进行推导失败，因为最终T仍然没有值。但是，在单个P/A对的级别上进行推导被认为是第二个对的成功，其中typename A<T>::a作为P。一般来说（不是在这个示例中），这允许从另一个P/A对中潜在地推导出T并最终具有一个值。 - bogdan

@jackX 对于你的第一个问题，如果我理解正确，我的答案是“是的”。我不会说“对于任何非推导上下文，都可以被推导”，那有点自相矛盾；对于一个 P/A 对，推导被认为是成功的，即使在 P 中出现的一些参数可能仍然没有值，因为它们只出现在该 P 的非推导上下文中。这个明确规则的原因是措辞使用了每个单独对的成功/失败结果，这与“正常”的推导（[temp.deduct.type] 和朋友）不同，其中... - bogdan

非推断上下文根本不参与推断，我们只关心最终的总体结果。[p10] 最后一句话就是这个意思。至于你的第二个问题，“只有”的原因是参数可以在同一个 P 中出现在推断和非推断上下文中，例如 B<T, typename A<T>::a>。 - bogdan

Answer 2

我认为关键在于以下语句：

第二个参数属于非推导上下文 - 因此，只有当UniqueA可转换为identity::type时，才能成功推导？

类型推导不执行"转换"的检查。这些检查是作为重载分辨率的一部分使用真实显式和推导参数进行的。

以下是选择要调用的函数模板所采取的步骤的摘要(所有引用都来自N3937, ~ C++ '14)：

1. 将显式参数替换，并检查生成的函数类型是否有效。(14.8.2/2)
2. 执行类型推导并替换生成的推导参数。再次，结果类型必须有效。(14.8.2/5)
3. 在重载分辨率中，成功完成步骤1和2的函数模板被专门化并包括在重载集中。(14.8.3/1)
4. 通过重载解决方案比较转换序列。(13.3.3)
5. 如果两个函数专业化的转换序列都不是“更好”的，则使用部分排序算法找到更专业的函数模板。(13.3.3)
6. 部分排序算法仅检查类型推导是否成功。(14.5.6.2/2)

在第4步之前，编译器已经知道使用实际参数时两个专业化都可以调用。步骤5和6正在用于确定哪个函数更为专业化。

- Richard Corden

---

@Barry：类型推导决定了模板参数的替换，需要进行一些检查（例如，类型通常必须匹配）。如果所有参数都有值，则将它们代入类型中以检查最终类型是否“有效”。非推断上下文不会对模板参数的值做出贡献，但在检查类型时会使用它们。问题是，我不确定您是否可以得到一个合成类型，导致无效类型，即 A<T>::type 是有效的，但 A<Q>::type 不是有效的。 - Richard Corden

但是我们需要确定(6)中的类型匹配，这就是为什么我们知道“b”扣除失败的原因。如果在检查类型时仍然使用未推断的上下文，那么“a”怎么不会失败呢？你必须不检查identity<UniqueA>::type吗？ - Barry

@Barry: [同样的评论-小修改] 推导失败是因为T首先推导到Q1，然后推导到identity<Q1>::type。它们不被视为相同的类型。反过来，T推导到Q2，由于identity<T>::type是一个非推导上下文，所以没有推导发生。我们留下了一个有效值T，所以推导成功。 - Richard Corden

例如，如果你的说法是正确的，为什么template<typename T> void f(T, int)比template<typename T, typename U> void f(T, U)更特化？对于第二个参数，从int到U的推导显然成功，那么按照你的逻辑，反过来，从Q2（为U合成）到int，没有进行推导。正如你上面解释的那样，我们只剩下一个有效的T值，所以推导成功。每个重载至少和另一个一样特化，因此不能选择哪个更特化。 - bogdan

让我们在聊天中继续这个讨论。 - Richard Corden