From fc0731b98a67c793862288f8ae334322666214dc Mon Sep 17 00:00:00 2001 From: Saar Raz Date: Wed, 18 Dec 2019 20:59:01 +0200 Subject: [PATCH] [Concepts] Constrained partial specializations and function overloads. Added support for constraint satisfaction checking and partial ordering of constraints in constrained partial specialization and function template overloads. Phabricator: D41910 --- clang/include/clang/AST/DeclTemplate.h | 29 +- clang/include/clang/Basic/DiagnosticSemaKinds.td | 15 +- clang/include/clang/Sema/Sema.h | 58 ++++ clang/lib/AST/ASTImporter.cpp | 34 +- clang/lib/AST/DeclTemplate.cpp | 79 ++++- clang/lib/Frontend/FrontendActions.cpp | 4 + clang/lib/Sema/SemaConcept.cpp | 360 +++++++++++++++++++++ clang/lib/Sema/SemaTemplate.cpp | 30 +- clang/lib/Sema/SemaTemplateDeduction.cpp | 231 ++++++++++--- clang/lib/Sema/SemaTemplateInstantiate.cpp | 42 +++ clang/lib/Sema/SemaTemplateInstantiateDecl.cpp | 5 +- clang/lib/Serialization/ASTReaderDecl.cpp | 10 +- clang/lib/Serialization/ASTWriterDecl.cpp | 8 +- clang/test/CXX/expr/expr.prim/expr.prim.id/p3.cpp | 15 +- .../CXX/temp/temp.constr/temp.constr.normal/p1.cpp | 18 ++ .../class-template-partial-specializations.cpp | 50 +++ .../temp.constr.order/function-templates.cpp | 82 +++++ .../var-template-partial-specializations.cpp | 53 +++ 18 files changed, 1021 insertions(+), 102 deletions(-) mode change 100644 => 100755 clang/include/clang/AST/DeclTemplate.h mode change 100644 => 100755 clang/include/clang/Sema/Sema.h mode change 100644 => 100755 clang/lib/AST/DeclTemplate.cpp mode change 100644 => 100755 clang/lib/Sema/SemaConcept.cpp mode change 100644 => 100755 clang/lib/Sema/SemaTemplate.cpp mode change 100644 => 100755 clang/lib/Sema/SemaTemplateInstantiateDecl.cpp create mode 100644 clang/test/CXX/temp/temp.constr/temp.constr.normal/p1.cpp create mode 100644 clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp create mode 100644 clang/test/CXX/temp/temp.constr/temp.constr.order/function-templates.cpp create mode 100644 clang/test/CXX/temp/temp.constr/temp.constr.order/var-template-partial-specializations.cpp diff --git a/clang/include/clang/AST/DeclTemplate.h b/clang/include/clang/AST/DeclTemplate.h old mode 100644 new mode 100755 index 3bebba5b..8b2c271 --- a/clang/include/clang/AST/DeclTemplate.h +++ b/clang/include/clang/AST/DeclTemplate.h @@ -793,9 +793,10 @@ protected: void loadLazySpecializationsImpl() const; - template typename SpecEntryTraits::DeclType* + template + typename SpecEntryTraits::DeclType* findSpecializationImpl(llvm::FoldingSetVector &Specs, - ArrayRef Args, void *&InsertPos); + void *&InsertPos, ProfileArguments &&...ProfileArgs); template void addSpecializationImpl(llvm::FoldingSetVector &Specs, @@ -2056,7 +2057,14 @@ public: ->getInjectedSpecializationType(); } - // FIXME: Add Profile support! + void Profile(llvm::FoldingSetNodeID &ID) const { + Profile(ID, getTemplateArgs().asArray(), getTemplateParameters(), + getASTContext()); + } + + static void + Profile(llvm::FoldingSetNodeID &ID, ArrayRef TemplateArgs, + TemplateParameterList *TPL, ASTContext &Context); static bool classof(const Decl *D) { return classofKind(D->getKind()); } @@ -2180,7 +2188,8 @@ public: /// Return the partial specialization with the provided arguments if it /// exists, otherwise return the insertion point. ClassTemplatePartialSpecializationDecl * - findPartialSpecialization(ArrayRef Args, void *&InsertPos); + findPartialSpecialization(ArrayRef Args, + TemplateParameterList *TPL, void *&InsertPos); /// Insert the specified partial specialization knowing that it is not /// already in. InsertPos must be obtained from findPartialSpecialization. @@ -2880,6 +2889,15 @@ public: return First->InstantiatedFromMember.setInt(true); } + void Profile(llvm::FoldingSetNodeID &ID) const { + Profile(ID, getTemplateArgs().asArray(), getTemplateParameters(), + getASTContext()); + } + + static void + Profile(llvm::FoldingSetNodeID &ID, ArrayRef TemplateArgs, + TemplateParameterList *TPL, ASTContext &Context); + static bool classof(const Decl *D) { return classofKind(D->getKind()); } static bool classofKind(Kind K) { @@ -2998,7 +3016,8 @@ public: /// Return the partial specialization with the provided arguments if it /// exists, otherwise return the insertion point. VarTemplatePartialSpecializationDecl * - findPartialSpecialization(ArrayRef Args, void *&InsertPos); + findPartialSpecialization(ArrayRef Args, + TemplateParameterList *TPL, void *&InsertPos); /// Insert the specified partial specialization knowing that it is not /// already in. InsertPos must be obtained from findPartialSpecialization. diff --git a/clang/include/clang/Basic/DiagnosticSemaKinds.td b/clang/include/clang/Basic/DiagnosticSemaKinds.td index c7b501b..71f9a18 100644 --- a/clang/include/clang/Basic/DiagnosticSemaKinds.td +++ b/clang/include/clang/Basic/DiagnosticSemaKinds.td @@ -2590,11 +2590,6 @@ def note_single_arg_concept_specialization_constraint_evaluated_to_false : Note< "%select{and |because }0%1 does not satisfy %2">; def note_atomic_constraint_evaluated_to_false_elaborated : Note< "%select{and |because }0'%1' (%2 %3 %4) evaluated to false">; -def err_could_not_normalize_ill_formed_constraint : Error< - "required expansion of concept specialization %0 failed, substituted " - "expression would be illegal">; -def note_could_not_normalize_ill_formed_constraint_reason : Note< - "because: %0">; def err_template_different_requires_clause : Error< "requires clause differs in template redeclaration">; @@ -4596,6 +4591,11 @@ def note_checking_constraints_for_class_spec_id_here : Note< "specialization '%0' required here">; def note_constraint_substitution_here : Note< "while substituting template arguments into constraint expression here">; +def note_constraint_normalization_here : Note< + "while calculating associated constraint of template '%0' here">; +def note_parameter_mapping_substitution_here : Note< + "while substituting into concept arguments here; substitution failures not " + "allowed in concept arguments">; def note_instantiation_contexts_suppressed : Note< "(skipping %0 context%s0 in backtrace; use -ftemplate-backtrace-limit=0 to " "see all)">; @@ -4759,8 +4759,9 @@ def note_template_declared_here : Note< "%select{function template|class template|variable template" "|type alias template|template template parameter}0 " "%1 declared here">; -def err_alias_template_expansion_into_fixed_list : Error< - "pack expansion used as argument for non-pack parameter of alias template">; +def err_template_expansion_into_fixed_list : Error< + "pack expansion used as argument for non-pack parameter of %select{alias " + "template|concept}0">; def note_parameter_type : Note< "parameter of type %0 is declared here">; diff --git a/clang/include/clang/Sema/Sema.h b/clang/include/clang/Sema/Sema.h old mode 100644 new mode 100755 index eb6a4eb..2730eef --- a/clang/include/clang/Sema/Sema.h +++ b/clang/include/clang/Sema/Sema.h @@ -6170,6 +6170,25 @@ public: /// A diagnostic is emitted if it is not, and false is returned. bool CheckConstraintExpression(Expr *CE); +private: + /// \brief Caches pairs of template-like decls whose associated constraints + /// were checked for subsumption and whether or not the first's constraints + /// did in fact subsume the second's. + llvm::DenseMap, bool> SubsumptionCache; + +public: + /// \brief Check whether the given declaration's associated constraints are + /// at least as constrained than another declaration's according to the + /// partial ordering of constraints. + /// + /// \param Result If no error occurred, receives the result of true if D1 is + /// at least constrained than D2, and false otherwise. + /// + /// \returns true if an error occurred, false otherwise. + bool IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef AC1, + NamedDecl *D2, ArrayRef AC2, + bool &Result); + /// \brief Check whether the given list of constraint expressions are /// satisfied (as if in a 'conjunction') given template arguments. /// \param ConstraintExprs a list of constraint expressions, treated as if @@ -6248,6 +6267,10 @@ public: void DiagnoseUnsatisfiedIllFormedConstraint(SourceLocation DiagnosticLocation, StringRef Diagnostic); + void + DiagnoseRedeclarationConstraintMismatch(const TemplateParameterList *Old, + const TemplateParameterList *New); + // ParseObjCStringLiteral - Parse Objective-C string literals. ExprResult ParseObjCStringLiteral(SourceLocation *AtLocs, ArrayRef Strings); @@ -6887,6 +6910,12 @@ public: QualType NTTPType, SourceLocation Loc); + /// Get a template argument mapping the given template parameter to itself, + /// e.g. for X in \c template, this would return an expression template + /// argument referencing X. + TemplateArgumentLoc getIdentityTemplateArgumentLoc(Decl *Param, + SourceLocation Location); + void translateTemplateArguments(const ASTTemplateArgsPtr &In, TemplateArgumentListInfo &Out); @@ -7785,6 +7814,9 @@ public: bool isTemplateTemplateParameterAtLeastAsSpecializedAs( TemplateParameterList *P, TemplateDecl *AArg, SourceLocation Loc); + void MarkUsedTemplateParameters(const Expr *E, bool OnlyDeduced, + unsigned Depth, llvm::SmallBitVector &Used); + void MarkUsedTemplateParameters(const TemplateArgumentList &TemplateArgs, bool OnlyDeduced, unsigned Depth, @@ -7878,6 +7910,13 @@ public: // We are substituting template arguments into a constraint expression. ConstraintSubstitution, + // We are normalizing a constraint expression. + ConstraintNormalization, + + // We are substituting into the parameter mapping of an atomic constraint + // during normalization. + ParameterMappingSubstitution, + /// We are rewriting a comparison operator in terms of an operator<=>. RewritingOperatorAsSpaceship, @@ -8159,6 +8198,19 @@ public: sema::TemplateDeductionInfo &DeductionInfo, SourceRange InstantiationRange); + struct ConstraintNormalization {}; + /// \brief Note that we are normalizing a constraint expression. + InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation, + ConstraintNormalization, NamedDecl *Template, + SourceRange InstantiationRange); + + struct ParameterMappingSubstitution {}; + /// \brief Note that we are subtituting into the parameter mapping of an + /// atomic constraint during constraint normalization. + InstantiatingTemplate(Sema &SemaRef, SourceLocation PointOfInstantiation, + ParameterMappingSubstitution, NamedDecl *Template, + SourceRange InstantiationRange); + /// Note that we have finished instantiating this template. void Clear(); @@ -8492,6 +8544,12 @@ public: SubstTemplateParams(TemplateParameterList *Params, DeclContext *Owner, const MultiLevelTemplateArgumentList &TemplateArgs); + bool + SubstTemplateArguments(ArrayRef Args, + const MultiLevelTemplateArgumentList &TemplateArgs, + TemplateArgumentListInfo &Outputs); + + Decl *SubstDecl(Decl *D, DeclContext *Owner, const MultiLevelTemplateArgumentList &TemplateArgs); diff --git a/clang/lib/AST/ASTImporter.cpp b/clang/lib/AST/ASTImporter.cpp index b75a689..20c1241 100644 --- a/clang/lib/AST/ASTImporter.cpp +++ b/clang/lib/AST/ASTImporter.cpp @@ -5278,16 +5278,25 @@ ExpectedDecl ASTNodeImporter::VisitClassTemplateSpecializationDecl( if (Error Err = ImportTemplateArguments( D->getTemplateArgs().data(), D->getTemplateArgs().size(), TemplateArgs)) return std::move(Err); - - // Try to find an existing specialization with these template arguments. + // Try to find an existing specialization with these template arguments and + // template parameter list. void *InsertPos = nullptr; ClassTemplateSpecializationDecl *PrevDecl = nullptr; ClassTemplatePartialSpecializationDecl *PartialSpec = dyn_cast(D); - if (PartialSpec) - PrevDecl = - ClassTemplate->findPartialSpecialization(TemplateArgs, InsertPos); - else + + // Import template parameters. + TemplateParameterList *ToTPList = nullptr; + + if (PartialSpec) { + auto ToTPListOrErr = import(PartialSpec->getTemplateParameters()); + if (!ToTPListOrErr) + return ToTPListOrErr.takeError(); + ToTPList = *ToTPListOrErr; + PrevDecl = ClassTemplate->findPartialSpecialization(TemplateArgs, + *ToTPListOrErr, + InsertPos); + } else PrevDecl = ClassTemplate->findSpecialization(TemplateArgs, InsertPos); if (PrevDecl) { @@ -5346,13 +5355,9 @@ ExpectedDecl ASTNodeImporter::VisitClassTemplateSpecializationDecl( return std::move(Err); CanonInjType = CanonInjType.getCanonicalType(); - auto ToTPListOrErr = import(PartialSpec->getTemplateParameters()); - if (!ToTPListOrErr) - return ToTPListOrErr.takeError(); - if (GetImportedOrCreateDecl( D2, D, Importer.getToContext(), D->getTagKind(), DC, - *BeginLocOrErr, *IdLocOrErr, *ToTPListOrErr, ClassTemplate, + *BeginLocOrErr, *IdLocOrErr, ToTPList, ClassTemplate, llvm::makeArrayRef(TemplateArgs.data(), TemplateArgs.size()), ToTAInfo, CanonInjType, cast_or_null(PrevDecl))) @@ -5360,10 +5365,11 @@ ExpectedDecl ASTNodeImporter::VisitClassTemplateSpecializationDecl( // Update InsertPos, because preceding import calls may have invalidated // it by adding new specializations. - if (!ClassTemplate->findPartialSpecialization(TemplateArgs, InsertPos)) + auto *PartSpec2 = cast(D2); + if (!ClassTemplate->findPartialSpecialization(TemplateArgs, ToTPList, + InsertPos)) // Add this partial specialization to the class template. - ClassTemplate->AddPartialSpecialization( - cast(D2), InsertPos); + ClassTemplate->AddPartialSpecialization(PartSpec2, InsertPos); } else { // Not a partial specialization. if (GetImportedOrCreateDecl( diff --git a/clang/lib/AST/DeclTemplate.cpp b/clang/lib/AST/DeclTemplate.cpp old mode 100644 new mode 100755 index 7e013c6..2373439 --- a/clang/lib/AST/DeclTemplate.cpp +++ b/clang/lib/AST/DeclTemplate.cpp @@ -231,15 +231,16 @@ void RedeclarableTemplateDecl::loadLazySpecializationsImpl() const { } } -template +template typename RedeclarableTemplateDecl::SpecEntryTraits::DeclType * RedeclarableTemplateDecl::findSpecializationImpl( - llvm::FoldingSetVector &Specs, ArrayRef Args, - void *&InsertPos) { + llvm::FoldingSetVector &Specs, void *&InsertPos, + ProfileArguments&&... ProfileArgs) { using SETraits = SpecEntryTraits; llvm::FoldingSetNodeID ID; - EntryType::Profile(ID, Args, getASTContext()); + EntryType::Profile(ID, std::forward(ProfileArgs)..., + getASTContext()); EntryType *Entry = Specs.FindNodeOrInsertPos(ID, InsertPos); return Entry ? SETraits::getDecl(Entry)->getMostRecentDecl() : nullptr; } @@ -254,8 +255,8 @@ void RedeclarableTemplateDecl::addSpecializationImpl( #ifndef NDEBUG void *CorrectInsertPos; assert(!findSpecializationImpl(Specializations, - SETraits::getTemplateArgs(Entry), - CorrectInsertPos) && + CorrectInsertPos, + SETraits::getTemplateArgs(Entry)) && InsertPos == CorrectInsertPos && "given incorrect InsertPos for specialization"); #endif @@ -312,7 +313,7 @@ FunctionTemplateDecl::getSpecializations() const { FunctionDecl * FunctionTemplateDecl::findSpecialization(ArrayRef Args, void *&InsertPos) { - return findSpecializationImpl(getSpecializations(), Args, InsertPos); + return findSpecializationImpl(getSpecializations(), InsertPos, Args); } void FunctionTemplateDecl::addSpecialization( @@ -418,7 +419,7 @@ ClassTemplateDecl::newCommon(ASTContext &C) const { ClassTemplateSpecializationDecl * ClassTemplateDecl::findSpecialization(ArrayRef Args, void *&InsertPos) { - return findSpecializationImpl(getSpecializations(), Args, InsertPos); + return findSpecializationImpl(getSpecializations(), InsertPos, Args); } void ClassTemplateDecl::AddSpecialization(ClassTemplateSpecializationDecl *D, @@ -427,9 +428,48 @@ void ClassTemplateDecl::AddSpecialization(ClassTemplateSpecializationDecl *D, } ClassTemplatePartialSpecializationDecl * -ClassTemplateDecl::findPartialSpecialization(ArrayRef Args, - void *&InsertPos) { - return findSpecializationImpl(getPartialSpecializations(), Args, InsertPos); +ClassTemplateDecl::findPartialSpecialization( + ArrayRef Args, + TemplateParameterList *TPL, void *&InsertPos) { + return findSpecializationImpl(getPartialSpecializations(), InsertPos, Args, + TPL); +} + +static void ProfileTemplateParameterList(ASTContext &C, + llvm::FoldingSetNodeID &ID, const TemplateParameterList *TPL) { + const Expr *RC = TPL->getRequiresClause(); + ID.AddBoolean(RC != nullptr); + if (RC) + RC->Profile(ID, C, /*Canonical=*/true); + ID.AddInteger(TPL->size()); + for (NamedDecl *D : *TPL) { + if (const auto *NTTP = dyn_cast(D)) { + ID.AddInteger(0); + ID.AddBoolean(NTTP->isParameterPack()); + NTTP->getType().getCanonicalType().Profile(ID); + continue; + } + if (const auto *TTP = dyn_cast(D)) { + ID.AddInteger(1); + ID.AddBoolean(TTP->isParameterPack()); + // TODO: Concepts: profile type-constraints. + continue; + } + const auto *TTP = cast(D); + ID.AddInteger(2); + ID.AddBoolean(TTP->isParameterPack()); + ProfileTemplateParameterList(C, ID, TTP->getTemplateParameters()); + } +} + +void +ClassTemplatePartialSpecializationDecl::Profile(llvm::FoldingSetNodeID &ID, + ArrayRef TemplateArgs, TemplateParameterList *TPL, + ASTContext &Context) { + ID.AddInteger(TemplateArgs.size()); + for (const TemplateArgument &TemplateArg : TemplateArgs) + TemplateArg.Profile(ID, Context); + ProfileTemplateParameterList(Context, ID, TPL); } void ClassTemplateDecl::AddPartialSpecialization( @@ -1035,7 +1075,7 @@ VarTemplateDecl::newCommon(ASTContext &C) const { VarTemplateSpecializationDecl * VarTemplateDecl::findSpecialization(ArrayRef Args, void *&InsertPos) { - return findSpecializationImpl(getSpecializations(), Args, InsertPos); + return findSpecializationImpl(getSpecializations(), InsertPos, Args); } void VarTemplateDecl::AddSpecialization(VarTemplateSpecializationDecl *D, @@ -1045,8 +1085,19 @@ void VarTemplateDecl::AddSpecialization(VarTemplateSpecializationDecl *D, VarTemplatePartialSpecializationDecl * VarTemplateDecl::findPartialSpecialization(ArrayRef Args, - void *&InsertPos) { - return findSpecializationImpl(getPartialSpecializations(), Args, InsertPos); + TemplateParameterList *TPL, void *&InsertPos) { + return findSpecializationImpl(getPartialSpecializations(), InsertPos, Args, + TPL); +} + +void +VarTemplatePartialSpecializationDecl::Profile(llvm::FoldingSetNodeID &ID, + ArrayRef TemplateArgs, TemplateParameterList *TPL, + ASTContext &Context) { + ID.AddInteger(TemplateArgs.size()); + for (const TemplateArgument &TemplateArg : TemplateArgs) + TemplateArg.Profile(ID, Context); + ProfileTemplateParameterList(Context, ID, TPL); } void VarTemplateDecl::AddPartialSpecialization( diff --git a/clang/lib/Frontend/FrontendActions.cpp b/clang/lib/Frontend/FrontendActions.cpp index aeea63c..cbcaf2f 100644 --- a/clang/lib/Frontend/FrontendActions.cpp +++ b/clang/lib/Frontend/FrontendActions.cpp @@ -425,6 +425,10 @@ private: return "ConstraintsCheck"; case CodeSynthesisContext::ConstraintSubstitution: return "ConstraintSubstitution"; + case CodeSynthesisContext::ConstraintNormalization: + return "ConstraintNormalization"; + case CodeSynthesisContext::ParameterMappingSubstitution: + return "ParameterMappingSubstitution"; } return ""; } diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp old mode 100644 new mode 100755 index f917d9c..cd41000 --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -17,6 +17,7 @@ #include "clang/Sema/TemplateDeduction.h" #include "clang/Sema/Template.h" #include "clang/AST/ExprCXX.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/PointerUnion.h" using namespace clang; @@ -414,4 +415,363 @@ void Sema::DiagnoseUnsatisfiedConstraint( diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); First = false; } +} + +namespace { +struct AtomicConstraint { + const Expr *ConstraintExpr; + llvm::Optional> 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()) + return false; + + for (unsigned I = 0, S = ParameterMapping->size(); I < S; ++I) + if (!C.getCanonicalTemplateArgument((*ParameterMapping)[I].getArgument()) + .structurallyEquals(C.getCanonicalTemplateArgument( + (*Other.ParameterMapping)[I].getArgument()))) + return false; + return true; + } + + bool subsumes(ASTContext &C, const AtomicConstraint &Other) const { + // C++ [temp.constr.order] p2 + // - an atomic constraint A subsumes another atomic constraint B + // if and only if the A and B are identical [...] + // + // C++ [temp.constr.atomic] p2 + // Two atomic constraints are identical if they are formed from the + // same expression and the targets of the parameter mappings are + // equivalent according to the rules for expressions [...] + + // We do not actually substitute the parameter mappings into the + // constraint expressions, therefore the constraint expressions are + // the originals, and comparing them will suffice. + if (ConstraintExpr != Other.ConstraintExpr) + return false; + + // Check that the parameter lists are identical + return hasMatchingParameterMapping(C, Other); + } +}; + +/// \brief A normalized constraint, as defined in C++ [temp.constr.normal], is +/// either an atomic constraint, a conjunction of normalized constraints or a +/// disjunction of normalized constraints. +struct NormalizedConstraint { + enum CompoundConstraintKind { CCK_Conjunction, CCK_Disjunction }; + + using CompoundConstraint = llvm::PointerIntPair< + std::pair *, 1, + CompoundConstraintKind>; + + llvm::PointerUnion Constraint; + + NormalizedConstraint(AtomicConstraint *C): Constraint{C} { }; + NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS, + NormalizedConstraint RHS, CompoundConstraintKind Kind) + : Constraint{CompoundConstraint{ + new (C) std::pair{LHS, + RHS}, + Kind}} { }; + + CompoundConstraintKind getCompoundKind() const { + assert(!isAtomic() && "getCompoundKind called on atomic constraint."); + return Constraint.get().getInt(); + } + + bool isAtomic() const { return Constraint.is(); } + + NormalizedConstraint &getLHS() const { + assert(!isAtomic() && "getLHS called on atomic constraint."); + return Constraint.get().getPointer()->first; + } + + NormalizedConstraint &getRHS() const { + assert(!isAtomic() && "getRHS called on atomic constraint."); + return Constraint.get().getPointer()->second; + } + + AtomicConstraint *getAtomicConstraint() const { + assert(isAtomic() && + "getAtomicConstraint called on non-atomic constraint."); + return Constraint.get(); + } + + static llvm::Optional + fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef E) { + assert(E.size() != 0); + auto First = fromConstraintExpr(S, D, E[0]); + if (E.size() == 1) + return First; + auto Second = fromConstraintExpr(S, D, E[1]); + if (!Second) + return llvm::Optional{}; + llvm::Optional Conjunction; + Conjunction.emplace(S.Context, std::move(*First), std::move(*Second), + CCK_Conjunction); + for (unsigned I = 2; I < E.size(); ++I) { + auto Next = fromConstraintExpr(S, D, E[I]); + if (!Next) + return llvm::Optional{}; + NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction), + std::move(*Next), CCK_Conjunction); + *Conjunction = std::move(NewConjunction); + } + return Conjunction; + } + +private: + static llvm::Optional fromConstraintExpr(Sema &S, + NamedDecl *D, + const Expr *E); +}; + +static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N, + ConceptDecl *Concept, ArrayRef 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]) + Atomic.ParameterMapping->push_back( + S.getIdentityTemplateArgumentLoc(TemplateParams->begin()[I], + // Here we assume we do not support things like + // template + // concept C = ...; + // + // template requires C + // 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; +} + +llvm::Optional +NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) { + assert(E != nullptr); + + // C++ [temp.constr.normal]p1.1 + // [...] + // - The normal form of an expression (E) is the normal form of E. + // [...] + E = E->IgnoreParenImpCasts(); + if (auto *BO = dyn_cast(E)) { + if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) { + auto LHS = fromConstraintExpr(S, D, BO->getLHS()); + if (!LHS) + return None; + auto RHS = fromConstraintExpr(S, D, BO->getRHS()); + if (!RHS) + return None; + + return NormalizedConstraint( + S.Context, *LHS, *RHS, + BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction); + } + } else if (auto *CSE = dyn_cast(E)) { + Optional SubNF; + { + Sema::InstantiatingTemplate Inst( + S, CSE->getExprLoc(), + Sema::InstantiatingTemplate::ConstraintNormalization{}, D, + CSE->getSourceRange()); + // C++ [temp.constr.normal]p1.1 + // [...] + // The normal form of an id-expression of the form C, + // where C names a concept, is the normal form of the + // constraint-expression of C, after substituting A1, A2, ..., AN for C’s + // respective template parameters in the parameter mappings in each atomic + // constraint. If any such substitution results in an invalid type or + // expression, the program is ill-formed; no diagnostic is required. + // [...] + SubNF = fromConstraintExpr(S, CSE->getNamedConcept(), + CSE->getNamedConcept()->getConstraintExpr()); + if (!SubNF) + return None; + } + + if (substituteParameterMappings( + S, *SubNF, CSE->getNamedConcept(), + CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten())) + return None; + + return SubNF; + } + return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)}; +} + +} // namespace + +using NormalForm = + llvm::SmallVector, 4>; + +static NormalForm makeCNF(const NormalizedConstraint &Normalized) { + if (Normalized.isAtomic()) + return {{Normalized.getAtomicConstraint()}}; + + NormalForm LCNF = makeCNF(Normalized.getLHS()); + NormalForm RCNF = makeCNF(Normalized.getRHS()); + if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) { + LCNF.reserve(LCNF.size() + RCNF.size()); + while (!RCNF.empty()) + LCNF.push_back(std::move(RCNF.pop_back_val())); + return LCNF; + } + + // Disjunction + NormalForm Res; + Res.reserve(LCNF.size() * RCNF.size()); + for (auto &LDisjunction : LCNF) + for (auto &RDisjunction : RCNF) { + NormalForm::value_type Combined; + Combined.reserve(LDisjunction.size() + RDisjunction.size()); + std::copy(LDisjunction.begin(), LDisjunction.end(), + std::back_inserter(Combined)); + std::copy(RDisjunction.begin(), RDisjunction.end(), + std::back_inserter(Combined)); + Res.emplace_back(Combined); + } + return Res; +} + +static NormalForm makeDNF(const NormalizedConstraint &Normalized) { + if (Normalized.isAtomic()) + return {{Normalized.getAtomicConstraint()}}; + + NormalForm LDNF = makeDNF(Normalized.getLHS()); + NormalForm RDNF = makeDNF(Normalized.getRHS()); + if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) { + LDNF.reserve(LDNF.size() + RDNF.size()); + while (!RDNF.empty()) + LDNF.push_back(std::move(RDNF.pop_back_val())); + return LDNF; + } + + // Conjunction + NormalForm Res; + Res.reserve(LDNF.size() * RDNF.size()); + for (auto &LConjunction : LDNF) { + for (auto &RConjunction : RDNF) { + NormalForm::value_type Combined; + Combined.reserve(LConjunction.size() + RConjunction.size()); + std::copy(LConjunction.begin(), LConjunction.end(), + std::back_inserter(Combined)); + std::copy(RConjunction.begin(), RConjunction.end(), + std::back_inserter(Combined)); + Res.emplace_back(Combined); + } + } + return Res; +} + +static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef P, + NamedDecl *DQ, ArrayRef Q, bool &Subsumes) { + // C++ [temp.constr.order] p2 + // In order to determine if a constraint P subsumes a constraint Q, P is + // transformed into disjunctive normal form, and Q is transformed into + // conjunctive normal form. [...] + auto PNormalized = NormalizedConstraint::fromConstraintExprs(S, DP, P); + if (!PNormalized) + return true; + const NormalForm PDNF = makeDNF(*PNormalized); + + auto QNormalized = NormalizedConstraint::fromConstraintExprs(S, DQ, Q); + if (!QNormalized) + return true; + const NormalForm QCNF = makeCNF(*QNormalized); + + // C++ [temp.constr.order] p2 + // Then, P subsumes Q if and only if, for every disjunctive clause Pi in the + // disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in + // the conjuctive normal form of Q, where [...] + for (const auto &Pi : PDNF) { + for (const auto &Qj : QCNF) { + // C++ [temp.constr.order] p2 + // - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if + // and only if there exists an atomic constraint Pia in Pi for which + // there exists an atomic constraint, Qjb, in Qj such that Pia + // subsumes Qjb. + bool Found = false; + for (const AtomicConstraint *Pia : Pi) { + for (const AtomicConstraint *Qjb : Qj) { + if (Pia->subsumes(S.Context, *Qjb)) { + Found = true; + break; + } + } + if (Found) + break; + } + if (!Found) { + Subsumes = false; + return false; + } + } + } + Subsumes = true; + return false; +} + +bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef AC1, + NamedDecl *D2, ArrayRef AC2, + bool &Result) { + if (AC1.empty()) { + Result = AC2.empty(); + return false; + } + if (AC2.empty()) { + // TD1 has associated constraints and TD2 does not. + Result = true; + return false; + } + + std::pair Key{D1, D2}; + auto CacheEntry = SubsumptionCache.find(Key); + 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 diff --git a/clang/lib/Sema/SemaTemplate.cpp b/clang/lib/Sema/SemaTemplate.cpp old mode 100644 new mode 100755 index 6998955..ade8a5a --- a/clang/lib/Sema/SemaTemplate.cpp +++ b/clang/lib/Sema/SemaTemplate.cpp @@ -1120,11 +1120,11 @@ NamedDecl *Sema::ActOnNonTypeTemplateParameter(Scope *S, Declarator &D, // Check that we have valid decl-specifiers specified. auto CheckValidDeclSpecifiers = [this, &D] { // C++ [temp.param] - // p1 + // p1 // template-parameter: // ... // parameter-declaration - // p2 + // p2 // ... A storage class shall not be specified in a template-parameter // declaration. // [dcl.typedef]p1: @@ -3900,7 +3900,9 @@ DeclResult Sema::ActOnVarTemplateSpecialization( } if (isSameAsPrimaryTemplate(VarTemplate->getTemplateParameters(), - Converted)) { + Converted) && + (!Context.getLangOpts().ConceptsTS || + !TemplateParams->hasAssociatedConstraints())) { // C++ [temp.class.spec]p9b3: // // -- The argument list of the specialization shall not be identical @@ -3919,8 +3921,8 @@ DeclResult Sema::ActOnVarTemplateSpecialization( VarTemplateSpecializationDecl *PrevDecl = nullptr; if (IsPartialSpecialization) - // FIXME: Template parameter list matters too - PrevDecl = VarTemplate->findPartialSpecialization(Converted, InsertPos); + PrevDecl = VarTemplate->findPartialSpecialization(Converted, TemplateParams, + InsertPos); else PrevDecl = VarTemplate->findSpecialization(Converted, InsertPos); @@ -5273,12 +5275,16 @@ bool Sema::CheckTemplateArgumentList( bool PackExpansionIntoNonPack = NewArgs[ArgIdx].getArgument().isPackExpansion() && (!(*Param)->isTemplateParameterPack() || getExpandedPackSize(*Param)); - if (PackExpansionIntoNonPack && isa(Template)) { + if (PackExpansionIntoNonPack && (isa(Template) || + isa(Template))) { // Core issue 1430: we have a pack expansion as an argument to an // alias template, and it's not part of a parameter pack. This // can't be canonicalized, so reject it now. + // As for concepts - we cannot normalize constraints where this + // situation exists. Diag(NewArgs[ArgIdx].getLocation(), - diag::err_alias_template_expansion_into_fixed_list) + diag::err_template_expansion_into_fixed_list) + << (isa(Template) ? 1 : 0) << NewArgs[ArgIdx].getSourceRange(); Diag((*Param)->getLocation(), diag::note_template_param_here); return true; @@ -7112,6 +7118,7 @@ static bool MatchTemplateParameterKind(Sema &S, NamedDecl *New, NamedDecl *Old, bool Complain, Sema::TemplateParameterListEqualKind Kind, SourceLocation TemplateArgLoc) { + // TODO: Concepts: Check constrained-parameter constraints here. // Check the actual kind (type, non-type, template). if (Old->getKind() != New->getKind()) { if (Complain) { @@ -7813,8 +7820,9 @@ DeclResult Sema::ActOnClassTemplateSpecialization( ClassTemplateSpecializationDecl *PrevDecl = nullptr; if (isPartialSpecialization) - // FIXME: Template parameter list matters, too - PrevDecl = ClassTemplate->findPartialSpecialization(Converted, InsertPos); + PrevDecl = ClassTemplate->findPartialSpecialization(Converted, + TemplateParams, + InsertPos); else PrevDecl = ClassTemplate->findSpecialization(Converted, InsertPos); @@ -7838,7 +7846,9 @@ DeclResult Sema::ActOnClassTemplateSpecialization( Converted); if (Context.hasSameType(CanonType, - ClassTemplate->getInjectedClassNameSpecialization())) { + ClassTemplate->getInjectedClassNameSpecialization()) && + (!Context.getLangOpts().ConceptsTS || + !TemplateParams->hasAssociatedConstraints())) { // C++ [temp.class.spec]p9b3: // // -- The argument list of the specialization shall not be identical diff --git a/clang/lib/Sema/SemaTemplateDeduction.cpp b/clang/lib/Sema/SemaTemplateDeduction.cpp index 3274477..df4f6f6 100644 --- a/clang/lib/Sema/SemaTemplateDeduction.cpp +++ b/clang/lib/Sema/SemaTemplateDeduction.cpp @@ -24,6 +24,7 @@ #include "clang/AST/Expr.h" #include "clang/AST/ExprCXX.h" #include "clang/AST/NestedNameSpecifier.h" +#include "clang/AST/RecursiveASTVisitor.h" #include "clang/AST/TemplateBase.h" #include "clang/AST/TemplateName.h" #include "clang/AST/Type.h" @@ -2501,6 +2502,30 @@ Sema::getTrivialTemplateArgumentLoc(const TemplateArgument &Arg, llvm_unreachable("Invalid TemplateArgument Kind!"); } +TemplateArgumentLoc +Sema::getIdentityTemplateArgumentLoc(Decl *TemplateParm, + SourceLocation Location) { + if (auto *TTP = dyn_cast(TemplateParm)) + return getTrivialTemplateArgumentLoc( + TemplateArgument( + Context.getTemplateTypeParmType(TTP->getDepth(), TTP->getIndex(), + TTP->isParameterPack(), TTP)), + QualType(), Location.isValid() ? Location : TTP->getLocation()); + else if (auto *TTP = dyn_cast(TemplateParm)) + return getTrivialTemplateArgumentLoc(TemplateArgument(TemplateName(TTP)), + QualType(), + Location.isValid() ? Location : + TTP->getLocation()); + auto *NTTP = cast(TemplateParm); + CXXScopeSpec SS; + DeclarationNameInfo Info(NTTP->getDeclName(), + Location.isValid() ? Location : NTTP->getLocation()); + Expr *E = BuildDeclarationNameExpr(SS, Info, NTTP).get(); + return getTrivialTemplateArgumentLoc(TemplateArgument(E), NTTP->getType(), + Location.isValid() ? Location : + NTTP->getLocation()); +} + /// Convert the given deduced template argument and add it to the set of /// fully-converted template arguments. static bool @@ -2591,23 +2616,6 @@ ConvertDeducedTemplateArgument(Sema &S, NamedDecl *Param, return ConvertArg(Arg, 0); } -template -static Sema::TemplateDeductionResult -CheckDeducedArgumentConstraints(Sema& S, TemplateDeclT *Template, - ArrayRef DeducedArgs, - TemplateDeductionInfo &Info) { - llvm::SmallVector AssociatedConstraints; - Template->getAssociatedConstraints(AssociatedConstraints); - if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, - DeducedArgs, Info.getLocation(), - Info.AssociatedConstraintsSatisfaction) || - !Info.AssociatedConstraintsSatisfaction.IsSatisfied) { - Info.reset(TemplateArgumentList::CreateCopy(S.Context, DeducedArgs)); - return Sema::TDK_ConstraintsNotSatisfied; - } - return Sema::TDK_Success; -} - // FIXME: This should not be a template, but // ClassTemplatePartialSpecializationDecl sadly does not derive from // TemplateDecl. @@ -2705,10 +2713,6 @@ static Sema::TemplateDeductionResult ConvertDeducedTemplateArguments( // If we get here, we successfully used the default template argument. } - if (Sema::TemplateDeductionResult Result - = CheckDeducedArgumentConstraints(S, Template, Builder, Info)) - return Result; - return Sema::TDK_Success; } @@ -2730,6 +2734,23 @@ struct IsPartialSpecialization { static constexpr bool value = true; }; +template +static Sema::TemplateDeductionResult +CheckDeducedArgumentConstraints(Sema& S, TemplateDeclT *Template, + ArrayRef DeducedArgs, + TemplateDeductionInfo& Info) { + llvm::SmallVector AssociatedConstraints; + Template->getAssociatedConstraints(AssociatedConstraints); + if (S.CheckConstraintSatisfaction(Template, AssociatedConstraints, + DeducedArgs, Info.getLocation(), + Info.AssociatedConstraintsSatisfaction) || + !Info.AssociatedConstraintsSatisfaction.IsSatisfied) { + Info.reset(TemplateArgumentList::CreateCopy(S.Context, DeducedArgs)); + return Sema::TDK_ConstraintsNotSatisfied; + } + return Sema::TDK_Success; +} + /// Complete template argument deduction for a partial specialization. template static typename std::enable_if::value, @@ -2811,6 +2832,9 @@ FinishTemplateArgumentDeduction( if (Trap.hasErrorOccurred()) return Sema::TDK_SubstitutionFailure; + if (auto Result = CheckDeducedArgumentConstraints(S, Partial, Builder, Info)) + return Result; + return Sema::TDK_Success; } @@ -2853,6 +2877,10 @@ static Sema::TemplateDeductionResult FinishTemplateArgumentDeduction( if (Trap.hasErrorOccurred()) return Sema::TDK_SubstitutionFailure; + if (auto Result = CheckDeducedArgumentConstraints(S, Template, Builder, + Info)) + return Result; + return Sema::TDK_Success; } @@ -3364,6 +3392,11 @@ Sema::TemplateDeductionResult Sema::FinishTemplateArgumentDeduction( PartialOverloading)) return Result; + if (TemplateDeductionResult Result + = CheckDeducedArgumentConstraints(*this, FunctionTemplate, Builder, + Info)) + return Result; + // C++ [temp.deduct.call]p10: [DR1391] // If deduction succeeds for all parameters that contain // template-parameters that participate in template argument deduction, @@ -4929,6 +4962,21 @@ Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, TemplatePartialOrderingContext TPOC, unsigned NumCallArguments1, unsigned NumCallArguments2) { + + auto JudgeByConstraints = [&] () -> FunctionTemplateDecl * { + llvm::SmallVector AC1, AC2; + FT1->getAssociatedConstraints(AC1); + FT2->getAssociatedConstraints(AC2); + bool AtLeastAsConstrained1, AtLeastAsConstrained2; + if (IsAtLeastAsConstrained(FT1, AC1, FT2, AC2, AtLeastAsConstrained1)) + return nullptr; + if (IsAtLeastAsConstrained(FT2, AC2, FT1, AC1, AtLeastAsConstrained2)) + return nullptr; + if (AtLeastAsConstrained1 == AtLeastAsConstrained2) + return nullptr; + return AtLeastAsConstrained1 ? FT1 : FT2; + }; + bool Better1 = isAtLeastAsSpecializedAs(*this, Loc, FT1, FT2, TPOC, NumCallArguments1); bool Better2 = isAtLeastAsSpecializedAs(*this, Loc, FT2, FT1, TPOC, @@ -4938,7 +4986,7 @@ Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, return Better1 ? FT1 : FT2; if (!Better1 && !Better2) // Neither is better than the other - return nullptr; + return JudgeByConstraints(); // FIXME: This mimics what GCC implements, but doesn't match up with the // proposed resolution for core issue 692. This area needs to be sorted out, @@ -4948,7 +4996,7 @@ Sema::getMoreSpecializedTemplate(FunctionTemplateDecl *FT1, if (Variadic1 != Variadic2) return Variadic1? FT2 : FT1; - return nullptr; + return JudgeByConstraints(); } /// Determine if the two templates are equivalent. @@ -5073,7 +5121,6 @@ template static bool isAtLeastAsSpecializedAs(Sema &S, QualType T1, QualType T2, TemplateLikeDecl *P2, TemplateDeductionInfo &Info) { - // TODO: Concepts: Regard constraints // C++ [temp.class.order]p1: // For two class template partial specializations, the first is at least as // specialized as the second if, given the following rewrite to two @@ -5144,8 +5191,21 @@ Sema::getMoreSpecializedPartialSpecialization( bool Better1 = isAtLeastAsSpecializedAs(*this, PT1, PT2, PS2, Info); bool Better2 = isAtLeastAsSpecializedAs(*this, PT2, PT1, PS1, Info); - if (Better1 == Better2) - return nullptr; + if (!Better1 && !Better2) + return nullptr; + if (Better1 && Better2) { + llvm::SmallVector AC1, AC2; + PS1->getAssociatedConstraints(AC1); + PS2->getAssociatedConstraints(AC2); + bool AtLeastAsConstrained1, AtLeastAsConstrained2; + if (IsAtLeastAsConstrained(PS1, AC1, PS2, AC2, AtLeastAsConstrained1)) + return nullptr; + if (IsAtLeastAsConstrained(PS2, AC2, PS1, AC1, AtLeastAsConstrained2)) + return nullptr; + if (AtLeastAsConstrained1 == AtLeastAsConstrained2) + return nullptr; + return AtLeastAsConstrained1 ? PS1 : PS2; + } return Better1 ? PS1 : PS2; } @@ -5157,11 +5217,22 @@ bool Sema::isMoreSpecializedThanPrimary( QualType PartialT = Spec->getInjectedSpecializationType(); if (!isAtLeastAsSpecializedAs(*this, PartialT, PrimaryT, Primary, Info)) return false; - if (isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) { - Info.clearSFINAEDiagnostic(); + if (!isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) + return true; + Info.clearSFINAEDiagnostic(); + llvm::SmallVector PrimaryAC, SpecAC; + Primary->getAssociatedConstraints(PrimaryAC); + Spec->getAssociatedConstraints(SpecAC); + bool AtLeastAsConstrainedPrimary, AtLeastAsConstrainedSpec; + if (IsAtLeastAsConstrained(Spec, SpecAC, Primary, PrimaryAC, + AtLeastAsConstrainedSpec)) + return false; + if (!AtLeastAsConstrainedSpec) return false; - } - return true; + if (IsAtLeastAsConstrained(Primary, PrimaryAC, Spec, SpecAC, + AtLeastAsConstrainedPrimary)) + return false; + return !AtLeastAsConstrainedPrimary; } VarTemplatePartialSpecializationDecl * @@ -5184,8 +5255,22 @@ Sema::getMoreSpecializedPartialSpecialization( bool Better1 = isAtLeastAsSpecializedAs(*this, PT1, PT2, PS2, Info); bool Better2 = isAtLeastAsSpecializedAs(*this, PT2, PT1, PS1, Info); - if (Better1 == Better2) + if (!Better1 && !Better2) return nullptr; + if (Better1 && Better2) { + llvm::SmallVector AC1, AC2; + PS1->getAssociatedConstraints(AC1); + PS2->getAssociatedConstraints(AC2); + bool AtLeastAsConstrained1, AtLeastAsConstrained2; + if (IsAtLeastAsConstrained(PS1, AC1, PS2, AC2, AtLeastAsConstrained1)) + return nullptr; + if (IsAtLeastAsConstrained(PS2, AC2, PS1, AC1, AtLeastAsConstrained2)) + return nullptr; + if (AtLeastAsConstrained1 == AtLeastAsConstrained2) { + return nullptr; + } + return AtLeastAsConstrained1 ? PS1 : PS2; + } return Better1 ? PS1 : PS2; } @@ -5205,13 +5290,25 @@ bool Sema::isMoreSpecializedThanPrimary( CanonTemplate, PrimaryArgs); QualType PartialT = Context.getTemplateSpecializationType( CanonTemplate, Spec->getTemplateArgs().asArray()); + if (!isAtLeastAsSpecializedAs(*this, PartialT, PrimaryT, Primary, Info)) return false; - if (isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) { - Info.clearSFINAEDiagnostic(); + if (!isAtLeastAsSpecializedAs(*this, PrimaryT, PartialT, Spec, Info)) + return true; + Info.clearSFINAEDiagnostic(); + llvm::SmallVector PrimaryAC, SpecAC; + Primary->getAssociatedConstraints(PrimaryAC); + Spec->getAssociatedConstraints(SpecAC); + bool AtLeastAsConstrainedPrimary, AtLeastAsConstrainedSpec; + if (IsAtLeastAsConstrained(Spec, SpecAC, Primary, PrimaryAC, + AtLeastAsConstrainedSpec)) return false; - } - return true; + if (!AtLeastAsConstrainedSpec) + return false; + if (IsAtLeastAsConstrained(Primary, PrimaryAC, Spec, SpecAC, + AtLeastAsConstrainedPrimary)) + return false; + return !AtLeastAsConstrainedPrimary; } bool Sema::isTemplateTemplateParameterAtLeastAsSpecializedAs( @@ -5277,6 +5374,49 @@ bool Sema::isTemplateTemplateParameterAtLeastAsSpecializedAs( return isAtLeastAsSpecializedAs(*this, PType, AType, AArg, Info); } +struct OccurringTemplateParameterFinder : + RecursiveASTVisitor { + llvm::SmallBitVector &OccurringIndices; + + OccurringTemplateParameterFinder(llvm::SmallBitVector &OccurringIndices) + : OccurringIndices(OccurringIndices) { } + + bool VisitTemplateTypeParmType(TemplateTypeParmType *T) { + assert(T->getDepth() == 0 && "This assumes that we allow concepts at " + "namespace scope only"); + noteParameter(T->getIndex()); + return true; + } + + bool TraverseTemplateName(TemplateName Template) { + if (auto *TTP = + dyn_cast(Template.getAsTemplateDecl())) { + assert(TTP->getDepth() == 0 && "This assumes that we allow concepts at " + "namespace scope only"); + noteParameter(TTP->getIndex()); + } + RecursiveASTVisitor:: + TraverseTemplateName(Template); + return true; + } + + bool VisitDeclRefExpr(DeclRefExpr *E) { + if (auto *NTTP = dyn_cast(E->getDecl())) { + assert(NTTP->getDepth() == 0 && "This assumes that we allow concepts at " + "namespace scope only"); + noteParameter(NTTP->getIndex()); + } + return true; + } + +protected: + void noteParameter(unsigned Index) { + if (OccurringIndices.size() >= Index) + OccurringIndices.resize(Index + 1, false); + OccurringIndices.set(Index); + } +}; + /// Mark the template parameters that are used by the given /// expression. static void @@ -5285,6 +5425,11 @@ MarkUsedTemplateParameters(ASTContext &Ctx, bool OnlyDeduced, unsigned Depth, llvm::SmallBitVector &Used) { + if (!OnlyDeduced) { + OccurringTemplateParameterFinder(Used).TraverseStmt(const_cast(E)); + return; + } + // We can deduce from a pack expansion. if (const PackExpansionExpr *Expansion = dyn_cast(E)) E = Expansion->getPattern(); @@ -5303,8 +5448,6 @@ MarkUsedTemplateParameters(ASTContext &Ctx, break; } - // FIXME: if !OnlyDeduced, we have to walk the whole subexpression to - // find other occurrences of template parameters. const DeclRefExpr *DRE = dyn_cast(E); if (!DRE) return; @@ -5684,6 +5827,20 @@ MarkUsedTemplateParameters(ASTContext &Ctx, } } +/// Mark which template parameters are used in a given expression. +/// +/// \param E the expression from which template parameters will be deduced. +/// +/// \param Used a bit vector whose elements will be set to \c true +/// to indicate when the corresponding template parameter will be +/// deduced. +void +Sema::MarkUsedTemplateParameters(const Expr *E, bool OnlyDeduced, + unsigned Depth, + llvm::SmallBitVector &Used) { + ::MarkUsedTemplateParameters(Context, E, OnlyDeduced, Depth, Used); +} + /// Mark which template parameters can be deduced from a given /// template argument list. /// diff --git a/clang/lib/Sema/SemaTemplateInstantiate.cpp b/clang/lib/Sema/SemaTemplateInstantiate.cpp index 6db8eb3..770c07d 100644 --- a/clang/lib/Sema/SemaTemplateInstantiate.cpp +++ b/clang/lib/Sema/SemaTemplateInstantiate.cpp @@ -207,6 +207,8 @@ bool Sema::CodeSynthesisContext::isInstantiationRecord() const { case DefiningSynthesizedFunction: case ExceptionSpecEvaluation: case ConstraintSubstitution: + case ParameterMappingSubstitution: + case ConstraintNormalization: case RewritingOperatorAsSpaceship: return false; @@ -380,6 +382,22 @@ Sema::InstantiatingTemplate::InstantiatingTemplate( PointOfInstantiation, InstantiationRange, Template, nullptr, {}, &DeductionInfo) {} +Sema::InstantiatingTemplate::InstantiatingTemplate( + Sema &SemaRef, SourceLocation PointOfInstantiation, + ConstraintNormalization, NamedDecl *Template, + SourceRange InstantiationRange) + : InstantiatingTemplate( + SemaRef, CodeSynthesisContext::ConstraintNormalization, + PointOfInstantiation, InstantiationRange, Template) {} + +Sema::InstantiatingTemplate::InstantiatingTemplate( + Sema &SemaRef, SourceLocation PointOfInstantiation, + ParameterMappingSubstitution, NamedDecl *Template, + SourceRange InstantiationRange) + : InstantiatingTemplate( + SemaRef, CodeSynthesisContext::ParameterMappingSubstitution, + PointOfInstantiation, InstantiationRange, Template) {} + void Sema::pushCodeSynthesisContext(CodeSynthesisContext Ctx) { Ctx.SavedInNonInstantiationSFINAEContext = InNonInstantiationSFINAEContext; InNonInstantiationSFINAEContext = false; @@ -733,6 +751,17 @@ void Sema::PrintInstantiationStack() { diag::note_constraint_substitution_here) << Active->InstantiationRange; break; + case CodeSynthesisContext::ConstraintNormalization: + Diags.Report(Active->PointOfInstantiation, + diag::note_constraint_normalization_here) + << cast(Active->Entity)->getName() + << Active->InstantiationRange; + break; + case CodeSynthesisContext::ParameterMappingSubstitution: + Diags.Report(Active->PointOfInstantiation, + diag::note_parameter_mapping_substitution_here) + << Active->InstantiationRange; + break; } } } @@ -757,6 +786,8 @@ Optional Sema::isSFINAEContext() const { case CodeSynthesisContext::DefaultFunctionArgumentInstantiation: case CodeSynthesisContext::ExceptionSpecInstantiation: case CodeSynthesisContext::ConstraintsCheck: + case CodeSynthesisContext::ParameterMappingSubstitution: + case CodeSynthesisContext::ConstraintNormalization: // This is a template instantiation, so there is no SFINAE. return None; @@ -2926,6 +2957,17 @@ Sema::SubstStmt(Stmt *S, const MultiLevelTemplateArgumentList &TemplateArgs) { return Instantiator.TransformStmt(S); } +bool Sema::SubstTemplateArguments( + ArrayRef Args, + const MultiLevelTemplateArgumentList &TemplateArgs, + TemplateArgumentListInfo &Out) { + TemplateInstantiator Instantiator(*this, TemplateArgs, + SourceLocation(), + DeclarationName()); + return Instantiator.TransformTemplateArguments(Args.begin(), Args.end(), + Out); +} + ExprResult Sema::SubstExpr(Expr *E, const MultiLevelTemplateArgumentList &TemplateArgs) { if (!E) diff --git a/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp b/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp old mode 100644 new mode 100755 index 0bff074..a8fc77f --- a/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp +++ b/clang/lib/Sema/SemaTemplateInstantiateDecl.cpp @@ -3706,7 +3706,8 @@ TemplateDeclInstantiator::InstantiateClassTemplatePartialSpecialization( // in the member template's set of class template partial specializations. void *InsertPos = nullptr; ClassTemplateSpecializationDecl *PrevDecl - = ClassTemplate->findPartialSpecialization(Converted, InsertPos); + = ClassTemplate->findPartialSpecialization(Converted, InstParams, + InsertPos); // Build the canonical type that describes the converted template // arguments of the class template partial specialization. @@ -3830,7 +3831,7 @@ TemplateDeclInstantiator::InstantiateVarTemplatePartialSpecialization( // in the member template's set of variable template partial specializations. void *InsertPos = nullptr; VarTemplateSpecializationDecl *PrevDecl = - VarTemplate->findPartialSpecialization(Converted, InsertPos); + VarTemplate->findPartialSpecialization(Converted, InstParams, InsertPos); // Build the canonical type that describes the converted template // arguments of the variable template partial specialization. diff --git a/clang/lib/Serialization/ASTReaderDecl.cpp b/clang/lib/Serialization/ASTReaderDecl.cpp index 0240984..3351f76 100644 --- a/clang/lib/Serialization/ASTReaderDecl.cpp +++ b/clang/lib/Serialization/ASTReaderDecl.cpp @@ -2176,12 +2176,14 @@ ASTDeclReader::VisitClassTemplateSpecializationDeclImpl( void ASTDeclReader::VisitClassTemplatePartialSpecializationDecl( ClassTemplatePartialSpecializationDecl *D) { - RedeclarableResult Redecl = VisitClassTemplateSpecializationDeclImpl(D); - + // We need to read the template params first because redeclarable is going to + // need them for profiling TemplateParameterList *Params = Record.readTemplateParameterList(); D->TemplateParams = Params; D->ArgsAsWritten = Record.readASTTemplateArgumentListInfo(); + RedeclarableResult Redecl = VisitClassTemplateSpecializationDeclImpl(D); + // These are read/set from/to the first declaration. if (ThisDeclID == Redecl.getFirstID()) { D->InstantiatedFromMember.setPointer( @@ -2279,12 +2281,12 @@ ASTDeclReader::VisitVarTemplateSpecializationDeclImpl( /// using Template(Partial)SpecializationDecl as input type. void ASTDeclReader::VisitVarTemplatePartialSpecializationDecl( VarTemplatePartialSpecializationDecl *D) { - RedeclarableResult Redecl = VisitVarTemplateSpecializationDeclImpl(D); - TemplateParameterList *Params = Record.readTemplateParameterList(); D->TemplateParams = Params; D->ArgsAsWritten = Record.readASTTemplateArgumentListInfo(); + RedeclarableResult Redecl = VisitVarTemplateSpecializationDeclImpl(D); + // These are read/set from/to the first declaration. if (ThisDeclID == Redecl.getFirstID()) { D->InstantiatedFromMember.setPointer( diff --git a/clang/lib/Serialization/ASTWriterDecl.cpp b/clang/lib/Serialization/ASTWriterDecl.cpp index 8931dc0..66f4db8 100644 --- a/clang/lib/Serialization/ASTWriterDecl.cpp +++ b/clang/lib/Serialization/ASTWriterDecl.cpp @@ -1539,11 +1539,11 @@ void ASTDeclWriter::VisitClassTemplateSpecializationDecl( void ASTDeclWriter::VisitClassTemplatePartialSpecializationDecl( ClassTemplatePartialSpecializationDecl *D) { - VisitClassTemplateSpecializationDecl(D); - Record.AddTemplateParameterList(D->getTemplateParameters()); Record.AddASTTemplateArgumentListInfo(D->getTemplateArgsAsWritten()); + VisitClassTemplateSpecializationDecl(D); + // These are read/set from/to the first declaration. if (D->getPreviousDecl() == nullptr) { Record.AddDeclRef(D->getInstantiatedFromMember()); @@ -1599,11 +1599,11 @@ void ASTDeclWriter::VisitVarTemplateSpecializationDecl( void ASTDeclWriter::VisitVarTemplatePartialSpecializationDecl( VarTemplatePartialSpecializationDecl *D) { - VisitVarTemplateSpecializationDecl(D); - Record.AddTemplateParameterList(D->getTemplateParameters()); Record.AddASTTemplateArgumentListInfo(D->getTemplateArgsAsWritten()); + VisitVarTemplateSpecializationDecl(D); + // These are read/set from/to the first declaration. if (D->getPreviousDecl() == nullptr) { Record.AddDeclRef(D->getInstantiatedFromMember()); diff --git a/clang/test/CXX/expr/expr.prim/expr.prim.id/p3.cpp b/clang/test/CXX/expr/expr.prim/expr.prim.id/p3.cpp index 1e10d45..fb39782 100644 --- a/clang/test/CXX/expr/expr.prim/expr.prim.id/p3.cpp +++ b/clang/test/CXX/expr/expr.prim/expr.prim.id/p3.cpp @@ -75,11 +75,8 @@ static_assert(!IsTypePredicate); template concept OneOf = (Same || ...); -template -constexpr bool S = OneOf; - -static_assert(S); -static_assert(!S); +static_assert(OneOf); +static_assert(!OneOf); namespace piecewise_substitution { template @@ -178,3 +175,11 @@ template concept AccessPrivate = T{}.f; static_assert(AccessPrivate); // expected-error@-1{{static_assert failed}} // expected-note@-2{{because 'T4' does not satisfy 'AccessPrivate'}} + +template +// expected-note@-1{{template parameter is declared here}} +concept C8 = sizeof(T) > sizeof(U); + +template +constexpr bool B8 = C8; +// expected-error@-1{{pack expansion used as argument for non-pack parameter of concept}} diff --git a/clang/test/CXX/temp/temp.constr/temp.constr.normal/p1.cpp b/clang/test/CXX/temp/temp.constr/temp.constr.normal/p1.cpp new file mode 100644 index 0000000..387b75c --- /dev/null +++ b/clang/test/CXX/temp/temp.constr/temp.constr.normal/p1.cpp @@ -0,0 +1,18 @@ +// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -x c++ -verify %s + +template concept True = true; +template concept Foo = True; +template concept Bar = Foo; +template requires Bar struct S { }; +template requires Bar && true struct S { }; + +template concept True2 = sizeof(T) >= 0; +template concept Foo2 = True2; +// expected-error@-1{{'type name' declared as a pointer to a reference of type 'type-parameter-0-0 &'}} +template concept Bar2 = Foo2; +// expected-note@-1{{while substituting into concept arguments here; substitution failures not allowed in concept arguments}} +template requires Bar2 struct S2 { }; +// expected-note@-1{{template is declared here}} +template requires Bar2 && true struct S2 { }; +// expected-error@-1{{class template partial specialization is not more specialized than the primary template}} +// expected-note@-2{{while calculating associated constraint of template 'S2' here}} diff --git a/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp b/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp new file mode 100644 index 0000000..8c2f552 --- /dev/null +++ b/clang/test/CXX/temp/temp.constr/temp.constr.order/class-template-partial-specializations.cpp @@ -0,0 +1,50 @@ +// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -x c++ -verify %s + +template requires sizeof(T) >= 4 +class A{}; // expected-note{{template is declared here}} + +template requires sizeof(T) >= 4 && sizeof(T) <= 10 +class A{}; // expected-error{{class template partial specialization is not more specialized than the primary template}} + +template +concept C1 = sizeof(T) >= 4; + +template requires C1 +class B{}; + +template requires C1 && sizeof(T) <= 10 +class B{}; + +template +concept C2 = sizeof(T) > 1 && sizeof(T) <= 8; + +template +class C{}; + +template requires C1 +class C{}; + +template +class D{}; // expected-note{{previous definition is here}} + +template +class D{}; // expected-error{{class template partial specialization does not specialize any template argument; to define the primary template, remove the template argument list}} expected-error{{redefinition of 'D'}} + +template requires C1 // expected-note{{previous template declaration is here}} +class E{}; + +template // expected-error{{requires clause differs in template redeclaration}} +class E{}; // expected-error{{class template partial specialization does not specialize any template argument; to define the primary template, remove the template argument list}} + +template +struct F{ enum{ value = 1 }; }; + +template requires C1 && C2 +struct F{ enum{ value = 2 }; }; + +template requires C1 || C2 +struct F{ enum{ value = 3 }; }; + +static_assert(F::value == 2); +static_assert(F::value == 3); +static_assert(F::value == 1); diff --git a/clang/test/CXX/temp/temp.constr/temp.constr.order/function-templates.cpp b/clang/test/CXX/temp/temp.constr/temp.constr.order/function-templates.cpp new file mode 100644 index 0000000..d1b5218 --- /dev/null +++ b/clang/test/CXX/temp/temp.constr/temp.constr.order/function-templates.cpp @@ -0,0 +1,82 @@ +// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -x c++ -verify %s + +template requires sizeof(T) >= 4 +bool a() { return false; } // expected-note {{candidate function [with T = unsigned int]}} + +template requires sizeof(T) >= 4 && sizeof(T) <= 10 +bool a() { return true; } // expected-note {{candidate function [with T = unsigned int]}} + +bool av = a(); // expected-error {{call to 'a' is ambiguous}} + +template +concept C1 = sizeof(T) >= 4; + +template requires C1 +constexpr bool b() { return false; } + +template requires C1 && sizeof(T) <= 10 +constexpr bool b() { return true; } + +static_assert(b()); +static_assert(!b()); + +template +concept C2 = sizeof(T) > 1 && sizeof(T) <= 8; + +template +bool c() { return false; } + +template requires C1 +bool c() { return true; } + +template requires C1 +constexpr bool d() { return false; } + +template +constexpr bool d() { return true; } + +static_assert(!d()); + +template +constexpr int e() { return 1; } + +template requires C1 && C2 +constexpr int e() { return 2; } + +template requires C1 || C2 +constexpr int e() { return 3; } + +static_assert(e() == 2); +static_assert(e() == 3); +static_assert(e() == 1); + +template +concept BiggerThan = sizeof(T) > sizeof(U); + +template +concept BiggerThanInt = BiggerThan; + +template requires BiggerThan +void f() { } +// expected-note@-1 {{candidate function [with T = long long, U = int]}} + +template requires BiggerThanInt +void f() { } +// expected-note@-1 {{candidate function [with T = long long, U = int]}} + +static_assert(sizeof(f())); +// expected-error@-1 {{call to 'f' is ambiguous}} + +template +concept C3 = true; + +template +concept C4 = true && C3; + +template requires C3 +int g() { } + +template requires C4 +int g() { } + +static_assert(sizeof(g())); \ No newline at end of file diff --git a/clang/test/CXX/temp/temp.constr/temp.constr.order/var-template-partial-specializations.cpp b/clang/test/CXX/temp/temp.constr/temp.constr.order/var-template-partial-specializations.cpp new file mode 100644 index 0000000..b40c77e --- /dev/null +++ b/clang/test/CXX/temp/temp.constr/temp.constr.order/var-template-partial-specializations.cpp @@ -0,0 +1,53 @@ +// RUN: %clang_cc1 -std=c++2a -fconcepts-ts -x c++ -verify %s + +template requires sizeof(T) >= 4 +bool a = false; // expected-note{{template is declared here}} + +template requires sizeof(T) >= 4 && sizeof(T) <= 10 +bool a = true; // expected-error{{variable template partial specialization is not more specialized than the primary template}} + +template +concept C1 = sizeof(T) >= 4; + +template requires C1 +bool b = false; + +template requires C1 && sizeof(T) <= 10 +bool b = true; + +template +concept C2 = sizeof(T) > 1 && sizeof(T) <= 8; + +template +bool c = false; + +template requires C1 +bool c = true; + +template +bool d = false; + +template +bool d = true; // expected-error{{variable template partial specialization does not specialize any template argument; to define the primary template, remove the template argument list}} + +template requires C1 +bool e = false; + +template +bool e = true; // expected-error{{variable template partial specialization does not specialize any template argument; to define the primary template, remove the template argument list}} + +template +constexpr int f = 1; + +template requires C1 && C2 +constexpr int f = 2; + +template requires C1 || C2 +constexpr int f = 3; + +static_assert(f == 2); +static_assert(f == 3); +static_assert(f == 1); + + + -- 2.7.4