[Concepts] Fix Function Template Concepts comparisons

[erichkeane]

Summary

As reported in GH61959, the patch for https://reviews.llvm.org/D146178
regressed some comparisons of non-out-of-line function constraints.
This patch fixes it by making sure we skip the list of template
arguments from a partial specialization (where they don't really
matter!).

There was 1 other workaround that was made for checking deduced
arguments that this removes part of.

Fixes: #61959

[rsmith]

clang/lib/Sema/SemaTemplateDeduction.cpp

2854–2858

It's not obvious to me what this was doing, so I'm not sure whether it's correct to remove it. Can you explain? It makes me uncomfortable that we would treat class template partial specializations and variable template partial specializations differently, at least without a good explanation for why that's appropriate -- perhaps we should apply this same set of changes to variable template partial specializations too, and remove this mechanism entirely?

clang/lib/Sema/SemaTemplateInstantiate.cpp

350

354

Can we produce a "done" response instead here? It doesn't seem right to carry on to the next level here without adding a level of template arguments -- if any further arguments were somehow collected, they would be collected at the wrong template depth. But, as far as I can determine, we should never encounter a partial specialization declaration except in cases where there is nothing remaining to be substituted (all outer substitutions would be identity substitutions). I think the same thing applies when we reach a class template declaration (the first branch in HandleRecordDecl) -- we should just be able to stop in that case too, rather than collecting some identity template arguments and carrying on to an outer level.

If we can't produce a "done" response here for some reason, then we should collect a level of identity template arguments instead.

[erichkeane]

clang/lib/Sema/SemaTemplateDeduction.cpp

2854–2858

Absolutely! And I suspect at a certain point we are going to want to remove this entirely, it is a bit of a hack (and I couldn't come up with a good repro that this caused a problem, and the VarTemplateSpecializationDecl code does a lot of work).

Basically, when doing the CheckDeducedArgumentConstraints below, we get the instantiation args list (see this being used on 2869).

However, the 'inner most' args when this is a Partial Specialization end up being 'wrong', since they come from the partial specialization. This is used to determine whether we need to replace them with the args we already have. However, this patch now makes it so ClassTemplatePartialSpecializationDecls no longer generate template arguments in getTemplateInstantiationArgs (which has seen a bit of a refactor since you were here last, since it was a bit of a difficult to understand function that didn't seem to cover many cases well, and had a lot of repetation).

clang/lib/Sema/SemaTemplateInstantiate.cpp

354

For constraints, the arguments are relative to namespace scope as far as I can tell. If we ended up 'stopping' we would miss references to the outer template, so something like:

template<typename T>
struct Outer {

  template<typename U>
  struct Inner {
     void foo() requires (is_same<T, U>){}
  };

};

Right? The substitution fo 'T' would be invalid at that point?

Also, what do you mean by 'identity' template arguments? I'm not sure I follow.

[erichkeane]

clang/lib/Sema/SemaTemplateInstantiate.cpp

354

Er, I meant something like (since it needs to be a partial spec):

 1 template<typename T>
 2 concept C = true;
 3
 4 template<typename T>
 5 struct Outer {
 6   template<typename U, typename V>
 7   struct Inner {};
 8   template<typename U>
 9   struct Inner<U, U> {
10     void foo()  requires C<U> && C<T>{}
11     void foo()  requires true{}
12   };
13 };

[erichkeane]

Hmmm... the examples I thought would cause a problem don't seem to when switching that to Done. So I'm going to run regression tests and give that a shot.

I think I now get what you mean about 'Identity' arguments, we basically need to have arguments to keep something like the above example (where 'foo' is a template, and the partial specialization is done correctly), and when trying to substitute into it, we would end up having the arguments to Outer and Foo, but substitution would think of the Foo args as the Inner args for depth. I'm giving the testing a shot, and will see if that fixes the problem without causing a regression in any of the concerns I have. I suspect I don't have a problem with the 'identity' for the same reason 'Done' works: we never hit that situation.

[alexander-shaposhnikov]

clang/lib/Sema/SemaTemplateInstantiate.cpp

323

/* not directly related to this patch, just one thought while we are here */
it would be useful to add missing documentation (comments) for the last parameter
(SkipForSpecialization)
p.s. perhaps, expanding the comment (or even adding some examples) would be super helpful as well (for future readers)

[erichkeane]

The switching that to 'done' seems to have broken cases where the partial specialization itself has requires clauses on it, see https://github.com/llvm/llvm-project/blob/main/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp#L75

Static Assert on 75 and 76 now fail with:

 error: 'error' diagnostics seen but not expected:
  File /localdisk2/ekeane1/workspaces/llvm-project/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp Line 75: static assertion failed due to requirement 'S<1>::F<unsigned int>::value == 2'
  File /localdisk2/ekeane1/workspaces/llvm-project/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp Line 76: static assertion failed due to requirement 'S<1>::F<char[10]>::value == 3'
error: 'note' diagnostics seen but not expected:
  File /localdisk2/ekeane1/workspaces/llvm-project/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp Line 75: expression evaluates to '1 == 2'
  File /localdisk2/ekeane1/workspaces/llvm-project/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp Line 76: expression evaluates to '1 == 3'
4 errors generated.

AND https://github.com/llvm/llvm-project/blob/main/clang/test/SemaTemplate/concepts.cpp#L323

error: 'error' diagnostics seen but not expected:
  File /localdisk2/ekeane1/workspaces/llvm-project/clang/test/SemaTemplate/concepts.cpp Line 332: no type named 'type' in 'DeducedTemplateArgs::ItrTraits<DeducedTemplateArgs::not_complete_itr>::Ptr<DeducedTemplateArgs::not_complete_itr>'
error: 'note' diagnostics seen but not expected:
  File /localdisk2/ekeane1/workspaces/llvm-project/clang/test/SemaTemplate/concepts.cpp Line 341: in instantiation of template class 'DeducedTemplateArgs::ItrTraits<DeducedTemplateArgs::complete_itr>' requested here
2 errors generated.

So I think it is causing something to not be in the right order there (particularly the 1st one). I'll look into the identity replacement of template args.

clang/lib/Sema/SemaTemplateInstantiate.cpp

323

I definitely agree.. I don't particularly understand what happened there, but I couldn't come up with an alternate fix/come up with a 'better' solution to the problem. See original commit here: https://reviews.llvm.org/D134128

[rsmith]

In D147722#4249612, @erichkeane wrote:

Hmmm... the examples I thought would cause a problem don't seem to when switching that to Done. So I'm going to run regression tests and give that a shot.

I think I now get what you mean about 'Identity' arguments, we basically need to have arguments to keep something like the above example (where 'foo' is a template, and the partial specialization is done correctly), and when trying to substitute into it, we would end up having the arguments to Outer and Foo, but substitution would think of the Foo args as the Inner args for depth. I'm giving the testing a shot, and will see if that fixes the problem without causing a regression in any of the concerns I have. I suspect I don't have a problem with the 'identity' for the same reason 'Done' works: we never hit that situation.

If we know that all further levels will be "identity" levels (mapping template-param-i-j to template-param-i-j), then we can use MultiLevelTemplateArgumentList::addOuterRetainedLevels to represent that and leave those levels alone. That will mean the getNumSubstitutedLevels() == 0 check in SubstituteConstraintExpression will fire a lot more often, which seems like a nice benefit.

[ayermolo]

With this patch here is still a build failure in our code base. I am trying to create a small repro. But from high level there is a templated class that has partial specializations, and it errors out on definition of a function that doesn't have any.

[alexander-shaposhnikov]

fwiw - I can revert https://reviews.llvm.org/D146178 for now till we fix the newly discovered cases (at the moment I'm aware of GH61959 and the one reported by @ilya-biryukov.
Basically let me know what you think - i'm looking into the issue reported by Ilya, but it will take time.

[ayermolo]

That would be great. :)

[ChuanqiXu]

In D147722#4250133, @alexander-shaposhnikov wrote:

fwiw - I can revert https://reviews.llvm.org/D146178 for now till we fix the newly discovered cases (at the moment I'm aware of GH61959 and the one reported by @ilya-biryukov.
Basically let me know what you think - i'm looking into the issue reported by Ilya, but it will take time.

+1 since this breaks our codebases too.

[erichkeane]

I think it is probably a good idea to revert that one until you get a chance to figure out that problem (and #61993 if it is related!). Other than the test being dependent on your change (and perhaps failing without your change), this is otherwise unrelated, so I might commit it anyway.

[ayermolo]

OK was able to create small(ish) repro

main.h

#include <type_traits>
enum class Enums {
    ACCESS = 0,
    MAP = 1,
};

template <typename TDM,typename TM, Enums kStrategy = Enums::MAP>
class DMap {
 public:
    template <typename TIDR>
        requires std::is_convertible_v<TIDR, TDM>
      void getOrCreate(TIDR v);
};

template <typename TDM, typename TM>
class DMap<TDM, TM, Enums::ACCESS> {
 public:
    template <typename TIDR>
        requires std::is_convertible_v<TIDR, TDM>
      void getOrCreate(TIDR v);

};

main.cpp

#include "main.h"

// broken with original patch, broken with follow up fix
template <typename TDM, typename TM, Enums kStrategy>
template <typename TIDR>
        requires std::is_convertible_v<TIDR, TDM>
inline void
DMap<TDM, TM, kStrategy>::getOrCreate(TIDR v) {
}

// broken with original patch, fixed with follow up fix
template <typename TDM, typename TM>
template <typename TIDR>
      requires std::is_convertible_v<TIDR, TDM>
inline void
DMap<TDM, TM, Enums::ACCESS>::getOrCreate(TIDR v) {
}


int foo() {
    DMap<int, int> map;
    long i;
    map.getOrCreate(i);
}

[erichkeane]

Made changes as requested by Richard. "SkipForInstantiation" needed to be added when we added levels, but I think this is something that probably needs to be looked at and removed in the future.

I also see the change that this means to fix is reverted, so @alexander-shaposhnikov : feel free to take this and integrated it into your patch if you'd like.

[erichkeane]

Superceded by https://reviews.llvm.org/D146178

clang/include/clang/Sema/Template.h

void addOuterTemplateArguments(std::nullopt_t) {
       assert(!NumRetainedOuterLevels &&
              "substituted args outside retained args?");
       TemplateArgumentLists.push_back({});
     }
 
     /// Replaces the current 'innermost' level with the provided argument list.
     /// This is useful for type deduction cases where we need to get the entire
     /// list from the AST, but then add the deduced innermost list.
-    void replaceInnermostTemplateArguments(ArgList Args) {
-      assert(TemplateArgumentLists.size() > 0 && "Replacing in an empty list?");
+    void replaceInnermostTemplateArguments(Decl *AssociatedDecl, ArgList Args) {
+      assert((TemplateArgumentLists.size() > 0 || NumRetainedOuterLevels) &&
+             "Replacing in an empty list?");
+
+      if (TemplateArgumentLists.size() > 0) {
+        assert((TemplateArgumentLists[0].AssociatedDeclAndFinal.getPointer() ||
+                TemplateArgumentLists[0].AssociatedDeclAndFinal.getPointer() ==
+                    AssociatedDecl) &&
+               "Trying to change incorrect declaration?");
         TemplateArgumentLists[0].Args = Args;
+      } else {
+        --NumRetainedOuterLevels;
+        TemplateArgumentLists.push_back(
+            {{AssociatedDecl, /*Final=*/false}, Args});
+      }
     }
 
     /// Add an outermost level that we are not substituting. We have no
     /// arguments at this level, and do not remove it from the depth of inner
     /// template parameters that we instantiate.
     void addOuterRetainedLevel() {
       ++NumRetainedOuterLevels;
     }

clang/lib/Sema/SemaTemplateDeduction.cpp

 static bool DeducedArgsNeedReplacement(TemplateDeclT *Template) {
   return false;
 }
 template <>
 bool DeducedArgsNeedReplacement<VarTemplatePartialSpecializationDecl>(
     VarTemplatePartialSpecializationDecl *Spec) {
   return !Spec->isClassScopeExplicitSpecialization();
 }
 template <>
 bool DeducedArgsNeedReplacement<ClassTemplatePartialSpecializationDecl>(
     ClassTemplatePartialSpecializationDecl *Spec) {
-  return !Spec->isClassScopeExplicitSpecialization();
+  return true;
 }
 
 template <typename TemplateDeclT>
 static Sema::TemplateDeductionResult
 CheckDeducedArgumentConstraints(Sema &S, TemplateDeclT *Template,
                                 ArrayRef<TemplateArgument> SugaredDeducedArgs,
                                 ArrayRef<TemplateArgument> CanonicalDeducedArgs,
                                 TemplateDeductionInfo &Info) {
   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
MultiLevelTemplateArgumentList MLTAL = S.getTemplateInstantiationArgs(
       /*RelativeToPrimary=*/true, /*Pattern=*/
       nullptr, /*ForConstraintInstantiation=*/true);
 
   // getTemplateInstantiationArgs picks up the non-deduced version of the
   // template args when this is a variable template partial specialization and
   // not class-scope explicit specialization, so replace with Deduced Args
   // instead of adding to inner-most.
   if (NeedsReplacement)
-    MLTAL.replaceInnermostTemplateArguments(CanonicalDeducedArgs);
+    MLTAL.replaceInnermostTemplateArguments(Template, CanonicalDeducedArgs);
 
   if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, MLTAL,
                                     Info.getLocation(),
                                     Info.AssociatedConstraintsSatisfaction) ||
       !Info.AssociatedConstraintsSatisfaction.IsSatisfied) {
     Info.reset(
         TemplateArgumentList::CreateCopy(S.Context, SugaredDeducedArgs),
         TemplateArgumentList::CreateCopy(S.Context, CanonicalDeducedArgs));

clang/lib/Sema/SemaTemplateInstantiate.cpp

 Response
 HandleDefaultTempArgIntoTempTempParam(const TemplateTemplateParmDecl *TTP,
                                       MultiLevelTemplateArgumentList &Result) {
   for (unsigned I = 0, N = TTP->getDepth() + 1; I != N; ++I)
     Result.addOuterTemplateArguments(std::nullopt);
   return Response::Done();
 }
 
+Response HandlePartialClassTemplateSpec(
+    const ClassTemplatePartialSpecializationDecl *PartialClassTemplSpec,
+    MultiLevelTemplateArgumentList &Result, bool SkipForSpecialization) {
+  // We don't want the arguments from the Partial Specialization, since
+  // anything instantiating here cannot access the arguments from the
+  // specialized template anyway, so any substitution we would do with these
+  // partially specialized arguments would 'wrong' and confuse constraint
+  // instantiation. We only do this in the case of a constraint check, since
+  // code elsewhere actually uses these and replaces them later with what
+  // they mean.
+  // If we know this is the 'top level', we can replace this with an
+  // OuterRetainedLevel, else we have to generate a set of identity arguments.
+
+  // If this is the top-level template entity, we can just add a retained level
+  // and be done.
+  if (!PartialClassTemplSpec->getTemplateDepth()) {
+    if (!SkipForSpecialization)
+      Result.addOuterRetainedLevel();
+    return Response::Done();
+  }
+
+  // Else, we can replace this with an 'empty' level, and the checking will just
+  // alter the 'depth', since this we don't have the 'Index' for this level.
+  if (!SkipForSpecialization)
+    Result.addOuterTemplateArguments(
+        const_cast<ClassTemplatePartialSpecializationDecl *>(
+            PartialClassTemplSpec),
+        {}, /*Final=*/false);
+
+  return Response::UseNextDecl(PartialClassTemplSpec);
+}
+
 // Add template arguments from a class template instantiation.
 Response
 HandleClassTemplateSpec(const ClassTemplateSpecializationDecl *ClassTemplSpec,
                         MultiLevelTemplateArgumentList &Result,
                         bool SkipForSpecialization) {
   if (!ClassTemplSpec->isClassScopeExplicitSpecialization()) {
     // We're done when we hit an explicit specialization.
     if (ClassTemplSpec->getSpecializationKind() == TSK_ExplicitSpecialization &&

 /// \param Pattern If non-NULL, indicates the pattern from which we will be
 /// instantiating the definition of the given declaration, \p ND. This is
 /// used to determine the proper set of template instantiation arguments for
 /// friend function template specializations.
 ///
 /// \param ForConstraintInstantiation when collecting arguments,
 /// ForConstraintInstantiation indicates we should continue looking when
 /// encountering a lambda generic call operator, and continue looking for
 /// arguments on an enclosing class template.
 
 MultiLevelTemplateArgumentList Sema::getTemplateInstantiationArgs(
     const NamedDecl *ND, bool Final, const TemplateArgumentList *Innermost,
     bool RelativeToPrimary, const FunctionDecl *Pattern,
     bool ForConstraintInstantiation, bool SkipForSpecialization) {
   assert(ND && "Can't find arguments for a decl if one isn't provided");
   // Accumulate the set of template argument lists in this structure.
   MultiLevelTemplateArgumentList Result;
 
   if (Innermost)
     Result.addOuterTemplateArguments(const_cast<NamedDecl *>(ND),
                                      Innermost->asArray(), Final);
 
   const Decl *CurDecl = ND;
 
   while (!CurDecl->isFileContextDecl()) {
     using namespace TemplateInstArgsHelpers;
     Response R;
     if (const auto *VarTemplSpec =
             dyn_cast<VarTemplateSpecializationDecl>(CurDecl)) {
       R = HandleVarTemplateSpec(VarTemplSpec, Result, SkipForSpecialization);
+    } else if (const auto *PartialClassTemplSpec =
+                   dyn_cast<ClassTemplatePartialSpecializationDecl>(CurDecl)) {
+      R = HandlePartialClassTemplateSpec(PartialClassTemplSpec, Result,
+                                         SkipForSpecialization);
     } else if (const auto *ClassTemplSpec =
                    dyn_cast<ClassTemplateSpecializationDecl>(CurDecl)) {
       R = HandleClassTemplateSpec(ClassTemplSpec, Result,
                                   SkipForSpecialization);
     } else if (const auto *Function = dyn_cast<FunctionDecl>(CurDecl)) {
       R = HandleFunction(Function, Result, Pattern, RelativeToPrimary,
                          ForConstraintInstantiation);
     } else if (const auto *Rec = dyn_cast<CXXRecordDecl>(CurDecl)) {
       R = HandleRecordDecl(Rec, Result, Context, ForConstraintInstantiation);
     } else if (const auto *CSD =
                    dyn_cast<ImplicitConceptSpecializationDecl>(CurDecl)) {
       R = HandleImplicitConceptSpecializationDecl(CSD, Result);
     } else if (const auto *FTD = dyn_cast<FunctionTemplateDecl>(CurDecl)) {
       R = HandleFunctionTemplateDecl(FTD);

clang/test/SemaTemplate/concepts.cpp

 template<typename T, typename U> concept C = true;
 
 template<typename T> auto L = []<C<T> U>() {};
 
 struct Q {
   template<C<int> U> friend constexpr auto decltype(L<int>)::operator()() const;
 };
 } // namespace TemplateInsideNonTemplateClass
+
+namespace GH61959 {
+template <typename T0>
+concept C = (sizeof(T0) >= 4);
+
+template<typename...>
+struct Orig { };
+
+template<typename T>
+struct Orig<T> {
+  template<typename> requires C<T>
+  void f() { }
+
+  template<typename> requires true
+  void f() { }
+};
+
+template <typename...> struct Mod {};
+
+template <typename T1, typename T2>
+struct Mod<T1, T2> {
+  template <typename> requires C<T1>
+  constexpr static int f() { return 1; }
+
+  template <typename> requires C<T2>
+  constexpr static int f() { return 2; }
+};
+
+static_assert(Mod<int, char>::f<double>() == 1);
+static_assert(Mod<char, int>::f<double>() == 2);
+
+template<typename T>
+struct Outer {
+  template<typename ...>
+  struct Inner {};
+
+  template<typename U>
+  struct Inner<U> {
+    template<typename V>
+    void foo()  requires C<U> && C<T> && C<V>{}
+    template<typename V>
+    void foo()  requires true{}
+  };
+};
+
+void bar() {
+  Outer<int>::Inner<float> I;
+  I.foo<char>();
+}
+}