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 ↗

(On Diff #279598)

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 ↗

(On Diff #279847)

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 ↗

(On Diff #279847)

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;
 }
 
 /// 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
if (ParamRef && ArgRef && S.Context.hasSameUnqualifiedType(Param, Arg)) {
       // Objective-C ARC adds:
       //     - [one type] has non-trivial lifetime, [the other type] has
       //       __unsafe_unretained lifetime, and the types are otherwise
       //       identical
       //
       // A is "considered to be at least as specialized" as P iff deduction
       // succeeds, so we model this as a deduction failure. Note that
       // [the first type] is P and [the other type] is A here; the standard
       // gets this backwards.
       Qualifiers ParamQuals = Param.getQualifiers();
       Qualifiers ArgQuals = Arg.getQualifiers();
       if ((ParamRef->isLValueReferenceType() &&
            !ArgRef->isLValueReferenceType()) ||
           ParamQuals.isStrictSupersetOf(ArgQuals) ||
           (ParamQuals.hasNonTrivialObjCLifetime() &&
            ArgQuals.getObjCLifetime() == Qualifiers::OCL_ExplicitNone &&
            ParamQuals.withoutObjCLifetime() ==
if ((TDF & TDF_TopLevelParameterTypeList) && !Param->isFunctionType()) {
       //   taking the address of a function template (14.8.2.2) or when deducing
       //   template arguments from a function declaration (14.8.2.6) and Pi and
       //   Ai are parameters of the top-level parameter-type-list of P and A,
       //   respectively, Pi is adjusted if it is a forwarding reference and Ai
       //   is an lvalue reference, in
       //   which case the type of Pi is changed to be the template parameter
       //   type (i.e., T&& is changed to simply T). [ Note: As a result, when
       //   Pi is T&& and Ai is X&, the adjusted Pi will be T, causing T to be
       //   deduced as X&. - end note ]
       TDF &= ~TDF_TopLevelParameterTypeList;
       if (isForwardingReference(Param, 0) && Arg->isLValueReferenceType())
         Param = Param->getPointeeType();
     }
   }
 
   // C++ [temp.deduct.type]p9:
   //   A template type argument T, a template template argument TT or a
   //   template non-type argument i can be deduced if P and A have one of
   //   the following forms:
   //
   //     T
   //     cv-list T
   if (const TemplateTypeParmType *TemplateTypeParm
         = Param->getAs<TemplateTypeParmType>()) {
     // Just skip any attempts to deduce from a placeholder type or a parameter
     // at a different depth.
     if (Arg->isPlaceholderType() ||
         Info.getDeducedDepth() != TemplateTypeParm->getDepth())
       return Sema::TDK_Success;
 
     unsigned Index = TemplateTypeParm->getIndex();
     bool RecanonicalizeArg = false;
 
     // If the argument type is an array type, move the qualifiers up to the
     // top level, so they can be matched with the qualifiers on the parameter.
     if (isa<ArrayType>(Arg)) {
       Qualifiers Quals;
       Arg = S.Context.getUnqualifiedArrayType(Arg, Quals);
       if (Quals) {
         Arg = S.Context.getQualifiedType(Arg, Quals);
         RecanonicalizeArg = true;
case Type::TemplateSpecialization: {
       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.
+      //   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.
 
       // 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();
+        bool SkipBases = false;
 
         // 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) {
case Type::TemplateSpecialization: {
               return Sema::TDK_MiscellaneousDeductionFailure;
 
             Successful = true;
             std::swap(SuccessfulDeduced, Deduced);
 
             Info.Param = BaseInfo.Param;
             Info.FirstArg = BaseInfo.FirstArg;
             Info.SecondArg = BaseInfo.SecondArg;
+
+            // In order to implement CWG2303 (added the following to p4b3):
+            //   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.
+            // We shouldn't visit the bases of a successful match ('C'), as they
+            // could only be 'B' here.
+            SkipBases = true;
           }
 
           Deduced = DeducedOrig;
         }
 
         // Visit base classes
+        if (!SkipBases) {
           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;
       }
 
       return Result;
     }

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> {};
+
+template <typename... T>
+void f(const A<T...> &);
+template <typename... T>
+void f2(const A<T...> *);
+
+void g() {
+  f(B{}); // This is no longer ambiguous.
+  B b;
+  f2(&b);
+}
+} //namespace dr2303
+#endif