DR2303: Prefer 'nearer' base classes during template deduction.

[erichkeane]

Summary

DR2303 fixes the case where the derived-base match for template
deduction is ambiguous if a base-of-base ALSO matches. The canonical
example (as shown in the test) is just like the MSVC implementation of
std::tuple.

This fixes a fairly sizable issue, where if a user inherits from
std::tuple on Windows (with the MS STL), they cannot use that type to
call a function that takes std::tuple.

[erichkeane]

I added @rsmith directly, since I suspect he's the most knowledgeable in SemaTemplateDeduction.cpp, but if anyone knows of someone else who is a good fit for this review, please add them as well!

[erichkeane]

Woops, left in a TODO from when I was planning on how to do this patch. Should be ready now :)

[aaron.ballman]

While this looks reasonable to me, I don't feel comfortable signing off on it because Templates Are Complicated (switching myself to a subscriber instead).

[erichkeane]

Also make sure to update the the cxx_dr_status.html document.

Additionally, I sent out a CWG message on the reflector about this: https://godbolt.org/z/bEr61T

My implementation has this as ambiguous, but the wording makes it well-formed I think. I don't think that was the intent of CWG2303, so unless they confirm that this was their intent (or that I'm wrong), I'll leave this patch as is.

[riccibruno]

Also make sure to update the the cxx_dr_status.html document.

It is auto-generated. You need to tag the test case: dr2303: 12.

Edit: And put it at the right place in the file (not at the end).

[erichkeane]

In D84048#2165023, @riccibruno wrote:

Also make sure to update the the cxx_dr_status.html document.

It is auto-generated. You need to tag the test case: dr2303: 12.

Edit: And put it at the right place in the file (not at the end).

Do you have an example of this? I've not seen that anywhere before.

[erichkeane]

In D84048#2165026, @erichkeane wrote:

In D84048#2165023, @riccibruno wrote:

Also make sure to update the the cxx_dr_status.html document.

It is auto-generated. You need to tag the test case: dr2303: 12.

Edit: And put it at the right place in the file (not at the end).

Do you have an example of this? I've not seen that anywhere before.

Ah, doh, I see a few now. Is that number the compiler version number?

[riccibruno]

In D84048#2165026, @erichkeane wrote:

In D84048#2165023, @riccibruno wrote:

Also make sure to update the the cxx_dr_status.html document.

It is auto-generated. You need to tag the test case: dr2303: 12.

Edit: And put it at the right place in the file (not at the end).

Do you have an example of this? I've not seen that anywhere before.

The test-case just above namespace dr2387 { // dr2387: 9.

[riccibruno]

Ah, doh, I see a few now. Is that number the compiler version number?

Yup

[erichkeane]

Revert change to cxx_dr_status and update the test to have the right tag.

[rsmith]

In D84048#2164950, @erichkeane wrote:

Additionally, I sent out a CWG message on the reflector about this: https://godbolt.org/z/bEr61T

My implementation has this as ambiguous, but the wording makes it well-formed I think. I don't think that was the intent of CWG2303, so unless they confirm that this was their intent (or that I'm wrong), I'll leave this patch as is.

Let's wait to hear back. Either option seems plausible here. The wording as written behaves the same way as name shadowing in member name lookup, so it may be intentional.

clang/test/CXX/drs/dr23xx.cpp

118

This should include a comment that make_cxx_dr_status can parse, such as // dr2303: 11 to indicate support in Clang 11 onwards.

clang/www/cxx_dr_status.html

13636

This is a generated file; use make_cxx_dr_status in the same directory to regenerate it.

[erichkeane]

I'd attempted to regenerate the cxx_dr_status.html using make_cxx_dr_status, but I get a 'no such

In D84048#2165080, @rsmith wrote:

In D84048#2164950, @erichkeane wrote:

Additionally, I sent out a CWG message on the reflector about this: https://godbolt.org/z/bEr61T

My implementation has this as ambiguous, but the wording makes it well-formed I think. I don't think that was the intent of CWG2303, so unless they confirm that this was their intent (or that I'm wrong), I'll leave this patch as is.

Let's wait to hear back. Either option seems plausible here. The wording as written behaves the same way as name shadowing in member name lookup, so it may be intentional.

Agreed. I think the pruning mechanism as implemented here is superior for a few reasons (and is easier to reason about mentally), but I want to see what CWG has to say.

FWIW, I though of the problem with this patch AFTER the fact (or at least, completely understood the wording at that point), so I wasn't aware of it when I wrote this patch.

clang/test/CXX/drs/dr23xx.cpp

118

Our current clang-version is 12.0.0, so 12 is correct here, right?

I've not been able to get make_cxx_dr_status work unfortunately. It seems to generate a blank version of the file (well, it HAS html, but none of the content).

I used the cwg_index.html from here: http://www.open-std.org/jtc1/sc22/wg21/docs/cwg_index.html

[erichkeane]

As CWG seems unmoved by my argument as to why CWG2303 should change, I've opted to implement it as worded. As you can see, the implementation is somewhat more complicated, but I believe I made it at least reasonably understandable.

I've also now updated the cwg_dr_status.html file via the script, which I also updated to acknowledge the current released version.

[rsmith]

clang/lib/Sema/SemaTemplateDeduction.cpp

1204–1205

Missing ///

1281

It would be better to add the class to Visited here rather than in the loop below -- that is, only add each class to ToVisit once rather than only processing each class once. That would put a tighter upper bound on the size of ToVisit.

1329–1331

This deduction step seems unnecessary to me (whether deduction succeeds or not here has no impact on the result of the algorithm).

Instead, you could perform the erase_if call below unconditionally. In order for that to be efficient, it'd make sense to also convert Matches into a hash map from (canonical) CXXRecordDecl* to BaseMatch.

1333

Typo "iS".

1351–1353

These fields are used to determine how to diagnose a deduction failure, and don't mean anything if deduction succeeds. I think this (and the tracking of BaseInfo above) is all dead code (and the corresponding code was similarly dead prior to this change).

clang/test/CXX/drs/dr23xx.cpp

118

Oh, right, version 11 already forked. How time flies =) Yes, 12 is correct.

The current list is built from revision 101m of the core issues list. You'll need to grab that from the WG21 wiki; there hasn't been a public release of the core issues list in over 2 years. (Though it looks like you got this working anyway?)

clang/www/cxx_dr_status.html

1507

Please commit the update from "unreleased" to "full" for Clang 11 changes separately.

[erichkeane]

Thanks for the review! I'll get this updated in the morning. I DO have a question on your suggestion for the ToVisit/Visited example, so if you could explain a little better, I'd be grateful.

clang/lib/Sema/SemaTemplateDeduction.cpp

1281

I'm perhaps missing something here... Can you clarify your suggestion a bit more? If we add it to 'Visited' here, it will never get visited in the while-loop below, right?

1329–1331

Ah, yes, thats a really good observation! I'll do that.

1351–1353

I see, so all tracking of BaseInfo isn't useful? That will simplify the code quite a bit then, since BaseInfo accounts for nearly all the code in BaseMatch (both the move operations, and the constructor only exist because of it). BaseMatch becomes essentially a pair otherwise. I think I can actually remove BaseMatch entirely as a result, and change the Matches to a map from RecordType* to the SmallVector of Deduction state.

clang/test/CXX/drs/dr23xx.cpp

118

Yep, I figured that out with help from @aaron.ballman on IRC :) I downloaded 101m from the wiki.

clang/www/cxx_dr_status.html

1507

Will do! I'll do that as review-after-commit, then rebase this on top of it. Thanks!

[rsmith]

clang/lib/Sema/SemaTemplateDeduction.cpp

1281

The idea would be to remove the Visited check in the loops below. We would guarantee that each class is only visited once by only adding it to ToVisit once. (As an example, we do the same thing for Queue and Visited here: https://github.com/llvm/llvm-project/blob/master/clang/lib/Sema/SemaLookup.cpp#L1992)

[erichkeane]

Fix all the things that @rsmith suggested.

Thanks for the feedback, it is looking much better!

I ended up using a MapVector instead of std::map for the RecordType*->SmallVector map, since we iterate over it. While the iteration SHOULDN'T matter (it is just the order that bases are added), if there is any bug/unconsidered situation, we might diagnose in a non-deterministic manner. Let me know if I'm being overly concerned there and I can switch it to std::map (DenseMap ends up being a bad choice according to the docs).

[erichkeane]

Ping! I believe I've done all of the requested changes.

[rsmith]

Thanks, looks nice =)

clang/lib/Sema/SemaTemplateDeduction.cpp

1205

1207–1217

[erichkeane]

Thanks! I'm done for the day, so I'll push in the morning when I'll have a few hours to respond to build bots.

Thanks again!

clang/lib/Sema/SemaTemplateDeduction.cpp

if (auto *ParamRef = Param->getAs<RValueReferenceType>()) {
     if (ParamRef->getPointeeType().getQualifiers())
       return false;
     auto *TypeParm = ParamRef->getPointeeType()->getAs<TemplateTypeParmType>();
     return TypeParm && TypeParm->getIndex() >= FirstInnerIndex;
   }
   return false;
 }
 
+///  Attempt to deduce the template arguments by checking the base types
+///  according to (C++20 [temp.deduct.call] p4b3.
+///
+/// \param S the semantic analysis object within which we are deducing.
+///
+/// \param RecordT the top level record object we are deducing against.
+///
+/// \param TemplateParams the template parameters that we are deducing.
+///
+/// \param SpecParam the template specialization parameter type.
+///
+/// \param Info information about the template argument deduction itself.
+///
+/// \param Deduced the deduced template arguments.
+///
+/// \returns the result of template argument deduction with the bases. "invalid"
+/// means no matches, "success" found a single item, and the
+/// "MiscellaneousDeductionFailure" result happens when the match is ambiguous.
+static Sema::TemplateDeductionResult DeduceTemplateBases(
+    Sema &S, const RecordType *RecordT, TemplateParameterList *TemplateParams,
+    const TemplateSpecializationType *SpecParam, TemplateDeductionInfo &Info,
+    SmallVectorImpl<DeducedTemplateArgument> &Deduced) {
+  // C++14 [temp.deduct.call] p4b3:
+  //   If P is a class and P has the form simple-template-id, then the
+  //   transformed A can be a derived class of the deduced A. Likewise if
+  //   P is a pointer to a class of the form simple-template-id, the
+  //   transformed A can be a pointer to a derived class pointed to by the
+  //   deduced A. However, if there is a class C that is a (direct or
+  //   indirect) base class of D and derived (directly or indirectly) from a
+  //   class B and that would be a valid deduced A, the deduced A cannot be
+  //   B or pointer to B, respectively.
+  //
+  //   These alternatives are considered only if type deduction would
+  //   otherwise fail. If they yield more than one possible deduced A, the
+  //   type deduction fails.
+
+  // Use a breadth-first search through the bases to collect the set of
+  // successful matches. Visited contains the set of nodes we have already
+  // visited, while ToVisit is our stack of records that we still need to
+  // visit.  Matches contains a list of matches that have yet to be
+  // disqualified.
+  llvm::SmallPtrSet<const RecordType *, 8> Visited;
+  SmallVector<const RecordType *, 8> ToVisit;
+  // We iterate over this later, so we have to use MapVector to ensure
+  // determinism.
+  llvm::MapVector<const RecordType *, SmallVector<DeducedTemplateArgument, 8>>
+      Matches;
+
+  auto AddBases = [&Visited, &ToVisit](const RecordType *RT) {
+    CXXRecordDecl *RD = cast<CXXRecordDecl>(RT->getDecl());
+    for (const auto &Base : RD->bases()) {
+      assert(Base.getType()->isRecordType() &&
+             "Base class that isn't a record?");
+      const RecordType *RT = Base.getType()->getAs<RecordType>();
+      if (Visited.insert(RT).second)
+        ToVisit.push_back(Base.getType()->getAs<RecordType>());
+    }
+  };
+
+  // Set up the loop by adding all the bases.
+  AddBases(RecordT);
+
+  // Search each path of bases until we either run into a successful match
+  // (where all bases of it are invalid), or we run out of bases.
+  while (!ToVisit.empty()) {
+    const RecordType *NextT = ToVisit.pop_back_val();
+
+    SmallVector<DeducedTemplateArgument, 8> DeducedCopy(Deduced.begin(),
+                                                        Deduced.end());
+    TemplateDeductionInfo BaseInfo(TemplateDeductionInfo::ForBase, Info);
+    Sema::TemplateDeductionResult BaseResult =
+        DeduceTemplateArguments(S, TemplateParams, SpecParam,
+                                QualType(NextT, 0), BaseInfo, DeducedCopy);
+
+    // If this was a successful deduction, add it to the list of matches,
+    // otherwise we need to continue searching its bases.
+    if (BaseResult == Sema::TDK_Success)
+      Matches.insert({NextT, DeducedCopy});
+    else
+      AddBases(NextT);
+  }
+
+  // At this point, 'Matches' contains a list of seemingly valid bases, however
+  // in the event that we have more than 1 match, it is possible that the base
+  // of one of the matches might be disqualified for being a base of another
+  // valid match. We can count on cyclical instantiations being invalid to
+  // simplify the disqualifications.  That is, if A & B are both matches, and B
+  // inherits from A (disqualifying A), we know that A cannot inherit from B.
+  if (Matches.size() > 1) {
+    Visited.clear();
+    for (const auto &Match : Matches)
+      AddBases(Match.first);
+
+    // We can give up once we have a single item (or have run out of things to
+    // search) since cyclical inheritence isn't valid.
+    while (Matches.size() > 1 && !ToVisit.empty()) {
+      const RecordType *NextT = ToVisit.pop_back_val();
+      Matches.erase(NextT);
+
+      // Always add all bases, since the inheritence tree can contain
+      // disqualifications for multiple matches.
+      AddBases(NextT);
+    }
+  }
+
+  if (Matches.empty())
+    return Sema::TDK_Invalid;
+  if (Matches.size() > 1)
+    return Sema::TDK_MiscellaneousDeductionFailure;
+
+  std::swap(Matches.front().second, Deduced);
+  return Sema::TDK_Success;
+}
+
 /// Deduce the template arguments by comparing the parameter type and
 /// the argument type (C++ [temp.deduct.type]).
 ///
 /// \param S the semantic analysis object within which we are deducing
 ///
 /// \param TemplateParams the template parameters that we are deducing
 ///
 /// \param ParamIn the parameter type
 ///
 /// \param ArgIn the argument type
 ///
 /// \param Info information about the template argument deduction itself
 ///
 /// \param Deduced the deduced template arguments
 ///
 /// \param TDF bitwise OR of the TemplateDeductionFlags bits that describe
 /// how template argument deduction is performed.
 ///
 /// \param PartialOrdering Whether we're performing template argument deduction
 /// in the context of partial ordering (C++0x [temp.deduct.partial]).
 ///
 /// \returns the result of template argument deduction so far. Note that a
 /// "success" result means that template argument deduction has not yet failed,
 /// but it may still fail, later, for other reasons.
 static Sema::TemplateDeductionResult
 DeduceTemplateArgumentsByTypeMatch(Sema &S,
                                    TemplateParameterList *TemplateParams,
                                    QualType ParamIn, QualType ArgIn,
                                    TemplateDeductionInfo &Info,
                             SmallVectorImpl<DeducedTemplateArgument> &Deduced,
                                    unsigned TDF,
                                    bool PartialOrdering,
                                    bool DeducedFromArrayBound) {
   // We only want to look at the canonical types, since typedefs and
   // sugar are not part of template argument deduction.
   QualType Param = S.Context.getCanonicalType(ParamIn);
   QualType Arg = S.Context.getCanonicalType(ArgIn);
 
   // If the argument type is a pack expansion, look at its pattern.
   // This isn't explicitly called out
   if (const PackExpansionType *ArgExpansion
                                             = dyn_cast<PackExpansionType>(Arg))
     Arg = ArgExpansion->getPattern();
 
case Type::TemplateSpecialization: {
         return Result;
 
       // We cannot inspect base classes as part of deduction when the type
       // is incomplete, so either instantiate any templates necessary to
       // complete the type, or skip over it if it cannot be completed.
       if (!S.isCompleteType(Info.getLocation(), Arg))
         return Result;
 
-      // C++14 [temp.deduct.call] p4b3:
-      //   If P is a class and P has the form simple-template-id, then the
-      //   transformed A can be a derived class of the deduced A. Likewise if
-      //   P is a pointer to a class of the form simple-template-id, the
-      //   transformed A can be a pointer to a derived class pointed to by the
-      //   deduced A.
-      //
-      //   These alternatives are considered only if type deduction would
-      //   otherwise fail. If they yield more than one possible deduced A, the
-      //   type deduction fails.
-
       // Reset the incorrectly deduced argument from above.
       Deduced = DeducedOrig;
 
-      // Use data recursion to crawl through the list of base classes.
-      // Visited contains the set of nodes we have already visited, while
-      // ToVisit is our stack of records that we still need to visit.
-      llvm::SmallPtrSet<const RecordType *, 8> Visited;
-      SmallVector<const RecordType *, 8> ToVisit;
-      ToVisit.push_back(RecordT);
-      bool Successful = false;
-      SmallVector<DeducedTemplateArgument, 8> SuccessfulDeduced;
-      while (!ToVisit.empty()) {
-        // Retrieve the next class in the inheritance hierarchy.
-        const RecordType *NextT = ToVisit.pop_back_val();
-
-        // If we have already seen this type, skip it.
-        if (!Visited.insert(NextT).second)
-          continue;
-
-        // If this is a base class, try to perform template argument
-        // deduction from it.
-        if (NextT != RecordT) {
-          TemplateDeductionInfo BaseInfo(TemplateDeductionInfo::ForBase, Info);
-          Sema::TemplateDeductionResult BaseResult =
-              DeduceTemplateArguments(S, TemplateParams, SpecParam,
-                                      QualType(NextT, 0), BaseInfo, Deduced);
-
-          // If template argument deduction for this base was successful,
-          // note that we had some success. Otherwise, ignore any deductions
-          // from this base class.
-          if (BaseResult == Sema::TDK_Success) {
-            // If we've already seen some success, then deduction fails due to
-            // an ambiguity (temp.deduct.call p5).
-            if (Successful)
-              return Sema::TDK_MiscellaneousDeductionFailure;
-
-            Successful = true;
-            std::swap(SuccessfulDeduced, Deduced);
-
-            Info.Param = BaseInfo.Param;
-            Info.FirstArg = BaseInfo.FirstArg;
-            Info.SecondArg = BaseInfo.SecondArg;
-          }
-
-          Deduced = DeducedOrig;
-        }
-
-        // Visit base classes
-        CXXRecordDecl *Next = cast<CXXRecordDecl>(NextT->getDecl());
-        for (const auto &Base : Next->bases()) {
-          assert(Base.getType()->isRecordType() &&
-                 "Base class that isn't a record?");
-          ToVisit.push_back(Base.getType()->getAs<RecordType>());
-        }
-      }
-
-      if (Successful) {
-        std::swap(SuccessfulDeduced, Deduced);
-        return Sema::TDK_Success;
-      }
+      // Check bases according to C++14 [temp.deduct.call] p4b3:
+      Sema::TemplateDeductionResult BaseResult = DeduceTemplateBases(
+          S, RecordT, TemplateParams, SpecParam, Info, Deduced);
 
+      if (BaseResult != Sema::TDK_Invalid)
+        return BaseResult;
       return Result;
     }
 
     //     T type::*
     //     T T::*
     //     T (type::*)()
     //     type (T::*)()
     //     type (type::*)(T)

clang/test/CXX/drs/dr23xx.cpp

#if __cplusplus >= 201402L
   template<int> const int c = 0;
   extern template const int c<0>; // ok, has external linkage despite 'const'
 
   template<typename T> T d = 0;
   extern template int d<int>;
   extern template const int d<const int>;
 #endif
 }
+
+#if __cplusplus >= 201103L
+namespace dr2303 { // dr2303: 12
+template <typename... T>
+struct A;
+template <>
+struct A<> {};
+template <typename T, typename... Ts>
+struct A<T, Ts...> : A<Ts...> {};
+struct B : A<int, int> {};
+struct C : A<int, int>, A<int> {}; // expected-warning {{direct base 'A<int>' is inaccessible}}
+struct D : A<int>, A<int, int> {}; // expected-warning {{direct base 'A<int>' is inaccessible}}
+struct E : A<int, int> {};
+struct F : B, E {};
+
+template <typename... T>
+void f(const A<T...> &) {
+  static_assert(sizeof...(T) == 2, "Should only match A<int,int>");
+}
+template <typename... T>
+void f2(const A<T...> *);
+
+void g() {
+  f(B{}); // This is no longer ambiguous.
+  B b;
+  f2(&b);
+  f(C{});
+  f(D{});
+  f(F{}); // expected-error {{ambiguous conversion from derived class}}
+}
+} //namespace dr2303
+#endif

clang/www/cxx_dr_status.html

<tr id="243">
     <td>NAD</td>
     <td>Weighting of conversion functions in direct-initialization</td>
     <td class="full" align="center">Yes</td>
   </tr>
   <tr id="244">
     <td><a href="https://wg21.link/cwg244">244</a></td>
     <td>CD1</td>
     <td>Destructor lookup</td>
     <td class="full" align="center">Clang 11</td>
   </tr>
   <tr id="245">
     <td><a href="https://wg21.link/cwg245">245</a></td>
     <td>CD1</td>
     <td>Name lookup in <I>elaborated-type-specifier</I>s</td>
     <td class="full" align="center">Yes</td>
   </tr>
   <tr id="246">
<tr id="2302">
     <td>NAD</td>
     <td>Address comparison between different member subobjects</td>
     <td class="none" align="center">Unknown</td>
   </tr>
   <tr id="2303">
     <td><a href="https://wg21.link/cwg2303">2303</a></td>
     <td>DRWP</td>
     <td>Partial ordering and recursive variadic inheritance</td>
-    <td class="none" align="center">Unknown</td>
+    <td class="unreleased" align="center">Clang 12</td>
   </tr>
   <tr id="2304">
     <td><a href="https://wg21.link/cwg2304">2304</a></td>
     <td>NAD</td>
     <td>Incomplete type vs overload resolution</td>
     <td class="none" align="center">Unknown</td>
   </tr>
   <tr id="2305">