[Concepts] Constrained partial specializations and function overloads.

[saar.raz]

Summary

Added support for constraint satisfaction checking and partial ordering of constraints in constrained partial specialization and function template overloads. Depends on D41569.

[saar.raz]

• Correct handling of non-substitutable concept specialization expressions.

[saar.raz]

• Adjusted constraint normalization to piecewise constraint substitution
• Normalized constraints are now represented as described in the standard (a non-substituted expression along with a list of "template arguments").

[saar.raz]

Adjusted to switch to ASTTemplateArgumentListInfo

[saar.raz]

• Fix bad handling of checking of deduced arguments in function templates

[saar.raz]

• Moved constraint checks to the end of FinishTemplateArgumentDeduction

[saar.raz]

Fixed bug in normalization substitution into CSEs
Rebase onto trunk

[martong]

lib/AST/ASTImporter.cpp

5026 ↗

(On Diff #195010)

ClassTemplate is in the "to" context, i.e. it is already imported.
PartialSpec is in the "from" context, not yet imported.
Thus, findPartialSpecialization is going search for a specialization in the "to" context but with constraints which are in the "from" context. So I suppose this will not find any match.
So, first you have to import the associated constraints expression and then use that in the search.

Something like:

ExpectedExpr ConstraintsOrErr = import(D->getAssociatedConstraints());
if (!ConstraintsOrErr)
  return ConstraintsOrErr.takeError();
// ...
ClassTemplate->findPartialSpecialization(TemplateArgs,
          *ConstraintsOrErr, InsertPos);

(The same below.)

[balazske]

lib/AST/ASTImporter.cpp

5096 ↗

(On Diff #195010)

This looks correct: PartSpec is the new instance (but this is not the best name for it, maybe PartialSpec2?).
But: How are the "associated constraint" expressions imported (stored somewhere in the To context)?

[saar.raz]

• Fixed importing of ACs when importing partial specs.
• Adjust to getAssociatedConstraints interface change

[saar.raz]

Renamed PartSpec to PartSpec2 (CR)

[martong]

From the ASTImporter point of view it looks good to me, thanks for the changes!

[rsmith]

(Didn't finish the review, but I have to run now.)

include/clang/AST/DeclTemplate.h

742 ↗

(On Diff #196107)

ProfileArguments &&...ProfileArgs?

1989–2004 ↗

(On Diff #196107)

Hmm, is this the right set of things to be profiling? The relevant rule should be that the template-heads are equivalent and the simple-template-ids are equivalent, and checking the associated constraints isn't sufficient to check the former. Should we be profiling the template parameter list and template arguments instead?

include/clang/Basic/DiagnosticSemaKinds.td

2469–2470 ↗

(On Diff #196107)

Please don't join sentences with periods like this; it looks strange given that we generally render diagnostics in lowercase, and not as full sentences). I'm also not sure what the second sentence here is telling the user. (What do you mean by "any"? "some", or "all", or substitutions the program requires, or something else?)

We generally use "while" not "when" for these "here's what I was doing" notes.

lib/Sema/SemaConcept.cpp

484–486 ↗

(On Diff #196107)

The specification says we substitute into the parameter mapping bottom-up (starting with atomic constraints and then substituting as they get used in enclosing constraints), but you're substituting top-down. That's not equivalent: specifically, the rules say that we should not perform substitution for parameters that are not used in the expansion of a concept ([temp.constr.atomic]p1: "[...] a mapping from the template parameters that appear within E to template arguments involving the [...]"). Example:

template<typename T> concept True = true;
template<typename T> concept Foo = True<T*>;
template<typename T> concept Bar = Foo<T&>;
template<typename T> void f() requires Bar<T>;

Here, the true atomic constraint has no parameter mappings, so we should never perform the substitution that would form T&*, and so shouldn't reject this for forming a pointer to a reference.

I think it's sufficient to first determine which parameters are used in a concept (perhaps when the concept is defined), and then form a parameter mapping top-down skipping the unused arguments, but you need to be careful to do that recursively (Bar doesn't use its T because Foo doesn't use its T).

777–778 ↗

(On Diff #196107)

There are a bunch of ways we can optimize this, but let's get the straightforward approach landed first :)

lib/Sema/SemaTemplate.cpp

3772 ↗

(On Diff #196107)

&& and || on prior line, please.

[saar.raz]

Address all CR comments by rsmith (including rewrite of normalization).
Decided to not support things like:

template<typename T, typename U>
concept C = ...;

template<typename... T> requires C<T...>
struct S { };

For now, as wording is not clear what the normal form of these should be.

[saar.raz]

Addressed in latest diff

[rsmith]

Only a few non-nit comments; if you feel confident addressing those, please feel free to commit after doing so. (If you'd like another round of review, let me know.) Thanks!

clang/include/clang/AST/DeclTemplate.h

796–799 ↗

(On Diff #232457)

Formatting nits:

typename ...ProfileArguments
ProfileArguments &&...ProfileArgs

clang/include/clang/Basic/DiagnosticSemaKinds.td

2507 ↗

(On Diff #232457)

Consider adding "during constraint normalization" before the semicolon.

Giving advice here ("make sure [...]") isn't consistent with our normal diagnostic style, which is to present facts. I wonder if we can rephrase this as a fact? Something like "while substituting into %0 %1; constraint normalization is not a SFINAE context" would work -- though I don't think we mention SFINAE in any diagnostics yet either, and I'd prefer not to, if possible.

Maybe just "while substituting into %0 %1 during constraint normalization" is enough; the fact that we're issuing an error for a substitution failure seems to strongly imply that substitution failure in this context is an error. What do you think?

clang/include/clang/Sema/Sema.h

6036 ↗

(On Diff #232457)

Nit: underindented.

clang/lib/AST/DeclTemplate.cpp

432 ↗

(On Diff #232457)

Nit: parameters after a newline should start in the same column as the first parameter. (Either flow Args onto a new line or indent these parameters to line up with it.)

445–463 ↗

(On Diff #232457)

Should we profile the kind of the template parameter (non-type/type/template) here? The profiling for the different kinds seems like it might not actually collide in practice, but that looks like it's happening by luck rather than by design.

Conversely, can we remove the profiling of the depth and index? That seems like it should be implied by the position of the parameter in the profiling data.

clang/lib/Sema/SemaConcept.cpp

426

Nit: we generally don't use direct-list-initialization. Use parens here.

537–578

You can use Sema::MarkUsedTemplateParameters for this.

... oh, except that it's broken for this case and has a FIXME to walk the full expression in OnlyDeduced = false mode:

// FIXME: if !OnlyDeduced, we have to walk the whole subexpression to
// find other occurrences of template parameters.

Oops. Please either move this into MarkUsedTemplateParameters and call that from here, or at least add a FIXME here to remind us to do so.

clang/lib/Sema/SemaTemplate.cpp

10521–10526 ↗

(On Diff #232457)

Presumably this is unintentional / left behind from editing?

clang/lib/Sema/SemaTemplateDeduction.cpp

2505 ↗

(On Diff #232457)

Is there any code that can be shared between this and ASTContext::getInjectedTemplateArg? (I think probably not, because that creates pack expansions and we don't want them here, but it seems worth considering.)

2514 ↗

(On Diff #232457)

VK_RValue is wrong here: we want an lvalue for a reference parameter. getInjectedTemplateArg uses Expr::getValueKindForType(NTTP->getType()) rather than VK_RValue, but can you add a NonTypeTemplateParmDecl::getValueKindForRef or similar, and use that both there and here, so that we don't need to track down all these places again when adding class type non-type template parameters?

Also NTTP->getType() is wrong in the reference type case (you want getNonLValueExprType).

Alternatively, you could use BuildDeclarationNameExpr, which computes the type and value kind for you. (getInjectedTemplateArg can't do that, because it's not in Sema.)

2739 ↗

(On Diff #232457)

Nit: || on the previous line, please.

5158 ↗

(On Diff #232457)

This should only apply if Better1 and Better2 are both true.

(Eventually -- once the relevant core issue is fixed -- we'll want to use the deductions from the "at least as specialized" checks as inputs to the "more constrained" checks too -- we should substitute those deductions into the normalized constraints prior to checking which is more constrained, so that we're talking about constraints on the same parameters in both sets of constraints. But let's not jump the gun on that.)

5190 ↗

(On Diff #232457)

As above, this should still return false.

5218 ↗

(On Diff #232457)

Likewise here.

5263 ↗

(On Diff #232457)

And here.

[thakis]

This makes clang crash when running tests: http://45.33.8.238/linux/5976/step_7.txt

Please use "Differential Revision: https://reviews.llvm.org/D41910" instead of "Phabricator: D41910" so that phab auto-closes the review and other auto-linking tools work.

[rnk]

This was relanded and reverted again today (d3f5769d5e93b30d4a8b4696381d5e4a304992fa & 79cc9e9b304a90598e8def4c8b5354d1f99186eb). I got this reduction:

template <unsigned> struct a {};
struct DestructibleUnionImpl {
  template <class...> DestructibleUnionImpl(a<0>);
  template <unsigned b, class...> DestructibleUnionImpl(a<b>);
};
class c {
  c() : d(a<0>()) {}
  DestructibleUnionImpl d;
};

Compile with clang -cc1, get this assertion:
clang: /usr/local/google/home/rnk/bisect-llvm-project/llvm/include/llvm/ADT/SmallBitVector.h:452: llvm::SmallBitVector::reference llvm::SmallBitVector::operator[](unsigned int): Assertion `Idx < size() && "Out-of-bounds Bit access."' failed.

Please add this as a test when relanding.

clang/lib/Sema/SemaConcept.cpp

 }
 
 namespace {
 struct AtomicConstraint {
   const Expr *ConstraintExpr;
   llvm::Optional<llvm::SmallVector<TemplateArgumentLoc, 3>> ParameterMapping;
 
   AtomicConstraint(Sema &S, const Expr *ConstraintExpr) :
       ConstraintExpr(ConstraintExpr) { };
 
   bool hasMatchingParameterMapping(ASTContext &C,
                                    const AtomicConstraint &Other) const {
     if (!ParameterMapping != !Other.ParameterMapping)
       return false;
     if (!ParameterMapping)
       return true;
     if (ParameterMapping->size() != Other.ParameterMapping->size())
fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef<const Expr *> E) {
     return Conjunction;
   }
 
 private:
   static llvm::Optional<NormalizedConstraint> fromConstraintExpr(Sema &S,
                                                                  NamedDecl *D,
                                                                  const Expr *E);
 };
 
 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
     ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
     const ASTTemplateArgumentListInfo *ArgsAsWritten) {
   if (!N.isAtomic()) {
     if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
                                     ArgsAsWritten))
       return true;
     return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
                                        ArgsAsWritten);
   }
   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
 
   AtomicConstraint &Atomic = *N.getAtomicConstraint();
   TemplateArgumentListInfo SubstArgs;
   MultiLevelTemplateArgumentList MLTAL;
   MLTAL.addOuterTemplateArguments(TemplateArgs);
   if (!Atomic.ParameterMapping) {
     llvm::SmallBitVector OccurringIndices;
     S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
                                  /*Depth=*/0, OccurringIndices);
     Atomic.ParameterMapping.emplace();
     Atomic.ParameterMapping->reserve(OccurringIndices.size());
     for (unsigned I = 0, C = TemplateParams->size(); I != C; ++I)
-      if (OccurringIndices[I])
+      if (I < OccurringIndices.size() && OccurringIndices[I])
         Atomic.ParameterMapping->push_back(
             S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I],
                 // Here we assume we do not support things like
                 // template<typename A, typename B>
                 // concept C = ...;
                 //
                 // template<typename... Ts> requires C<Ts...>
                 // struct S { };
                 // The above currently yields a diagnostic.
                 // We still might have default arguments for concept parameters.
                 ArgsAsWritten->NumTemplateArgs > I ?
                 ArgsAsWritten->arguments()[I].getLocation() :
                 SourceLocation()));
   }
   Sema::InstantiatingTemplate Inst(
       S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
       Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
       SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
                   ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
     return true;
   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
             N.getAtomicConstraint()->ParameterMapping->begin());
   return false;
 }
if (CacheEntry != SubsumptionCache.end()) {
     Result = CacheEntry->second;
     return false;
   }
   if (subsumes(*this, D1, AC1, D2, AC2, Result))
     return true;
   SubsumptionCache.try_emplace(Key, Result);
   return false;
 }
 No newline at end of file