| //===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===// |
| // |
| // The LLVM Compiler Infrastructure |
| // |
| // This file is distributed under the University of Illinois Open Source |
| // License. See LICENSE.TXT for details. |
| // |
| //===----------------------------------------------------------------------===// |
| // |
| // This file implements semantic analysis for C++ constraints and concepts. |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "clang/Sema/Sema.h" |
| #include "clang/Sema/SemaInternal.h" |
| #include "clang/Sema/SemaDiagnostic.h" |
| #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; |
| using namespace sema; |
| |
| bool Sema::CheckConstraintExpression(Expr *ConstraintExpression) { |
| // C++2a [temp.constr.atomic]p1 |
| // ..E shall be a constant expression of type bool. |
| |
| ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts(); |
| |
| if (auto *BinOp = dyn_cast<BinaryOperator>(ConstraintExpression)) { |
| if (BinOp->getOpcode() == BO_LAnd || BinOp->getOpcode() == BO_LOr) |
| return CheckConstraintExpression(BinOp->getLHS()) && |
| CheckConstraintExpression(BinOp->getRHS()); |
| } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression)) |
| return CheckConstraintExpression(C->getSubExpr()); |
| |
| // An atomic constraint! |
| if (ConstraintExpression->isTypeDependent()) |
| return true; |
| |
| QualType Type = ConstraintExpression->getType(); |
| if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) { |
| Diag(ConstraintExpression->getExprLoc(), |
| diag::err_non_bool_atomic_constraint) << Type |
| << ConstraintExpression->getSourceRange(); |
| return false; |
| } |
| return true; |
| } |
| |
| template <typename AtomicEvaluator> |
| static bool |
| calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr, |
| ConstraintSatisfaction &Satisfaction, |
| AtomicEvaluator &&Evaluator) { |
| ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts(); |
| |
| if (auto *BO = dyn_cast<BinaryOperator>(ConstraintExpr)) { |
| if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) { |
| if (calculateConstraintSatisfaction(S, BO->getLHS(), Satisfaction, |
| Evaluator)) |
| return true; |
| |
| bool IsLHSSatisfied = Satisfaction.IsSatisfied; |
| |
| if (BO->getOpcode() == BO_LOr && IsLHSSatisfied) |
| // [temp.constr.op] p3 |
| // A disjunction is a constraint taking two operands. To determine if |
| // a disjunction is satisfied, the satisfaction of the first operand |
| // is checked. If that is satisfied, the disjunction is satisfied. |
| // Otherwise, the disjunction is satisfied if and only if the second |
| // operand is satisfied. |
| return false; |
| |
| if (BO->getOpcode() == BO_LAnd && !IsLHSSatisfied) |
| // [temp.constr.op] p2 |
| // A conjunction is a constraint taking two operands. To determine if |
| // a conjunction is satisfied, the satisfaction of the first operand |
| // is checked. If that is not satisfied, the conjunction is not |
| // satisfied. Otherwise, the conjunction is satisfied if and only if |
| // the second operand is satisfied. |
| return false; |
| |
| return calculateConstraintSatisfaction(S, BO->getRHS(), Satisfaction, |
| std::forward<AtomicEvaluator>(Evaluator)); |
| } |
| } |
| else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) |
| return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction, |
| std::forward<AtomicEvaluator>(Evaluator)); |
| |
| // An atomic constraint expression |
| ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr); |
| |
| if (SubstitutedAtomicExpr.isInvalid()) |
| return true; |
| |
| if (!SubstitutedAtomicExpr.isUsable()) |
| // Evaluator has decided satisfaction without yielding an expression. |
| return false; |
| |
| EnterExpressionEvaluationContext ConstantEvaluated( |
| S, Sema::ExpressionEvaluationContext::ConstantEvaluated); |
| SmallVector<PartialDiagnosticAt, 2> EvaluationDiags; |
| Expr::EvalResult EvalResult; |
| EvalResult.Diag = &EvaluationDiags; |
| if (!SubstitutedAtomicExpr.get()->EvaluateAsRValue(EvalResult, S.Context)) { |
| // C++2a [temp.constr.atomic]p1 |
| // ...E shall be a constant expression of type bool. |
| S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(), |
| diag::err_non_constant_constraint_expression) |
| << SubstitutedAtomicExpr.get()->getSourceRange(); |
| for (const PartialDiagnosticAt &PDiag : EvaluationDiags) |
| S.Diag(PDiag.first, PDiag.second); |
| return true; |
| } |
| |
| Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue(); |
| if (!Satisfaction.IsSatisfied) |
| Satisfaction.Details.emplace_back(ConstraintExpr, |
| SubstitutedAtomicExpr.get()); |
| |
| return false; |
| } |
| |
| template <typename TemplateDeclT> |
| static bool calculateConstraintSatisfaction( |
| Sema &S, TemplateDeclT *Template, ArrayRef<TemplateArgument> TemplateArgs, |
| SourceLocation TemplateNameLoc, MultiLevelTemplateArgumentList &MLTAL, |
| const Expr *ConstraintExpr, ConstraintSatisfaction &Satisfaction) { |
| return calculateConstraintSatisfaction( |
| S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) { |
| EnterExpressionEvaluationContext ConstantEvaluated( |
| S, Sema::ExpressionEvaluationContext::ConstantEvaluated); |
| |
| // Atomic constraint - substitute arguments and check satisfaction. |
| ExprResult SubstitutedExpression; |
| { |
| TemplateDeductionInfo Info(TemplateNameLoc); |
| Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(), |
| Sema::InstantiatingTemplate::ConstraintSubstitution{}, Template, |
| Info, AtomicExpr->getSourceRange()); |
| if (Inst.isInvalid()) |
| return ExprError(); |
| // We do not want error diagnostics escaping here. |
| Sema::SFINAETrap Trap(S); |
| SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr), |
| MLTAL); |
| if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) { |
| // C++2a [temp.constr.atomic]p1 |
| // ...If substitution results in an invalid type or expression, the |
| // constraint is not satisfied. |
| if (!Trap.hasErrorOccurred()) |
| // A non-SFINAE error has occured as a result of this |
| // substitution. |
| return ExprError(); |
| |
| PartialDiagnosticAt SubstDiag{SourceLocation(), |
| PartialDiagnostic::NullDiagnostic()}; |
| Info.takeSFINAEDiagnostic(SubstDiag); |
| // FIXME: Concepts: This is an unfortunate consequence of there |
| // being no serialization code for PartialDiagnostics and the fact |
| // that serializing them would likely take a lot more storage than |
| // just storing them as strings. We would still like, in the |
| // future, to serialize the proper PartialDiagnostic as serializing |
| // it as a string defeats the purpose of the diagnostic mechanism. |
| SmallString<128> DiagString; |
| DiagString = ": "; |
| SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString); |
| unsigned MessageSize = DiagString.size(); |
| char *Mem = new (S.Context) char[MessageSize]; |
| memcpy(Mem, DiagString.c_str(), MessageSize); |
| Satisfaction.Details.emplace_back( |
| AtomicExpr, |
| new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{ |
| SubstDiag.first, StringRef(Mem, MessageSize)}); |
| Satisfaction.IsSatisfied = false; |
| return ExprEmpty(); |
| } |
| } |
| |
| if (!S.CheckConstraintExpression(SubstitutedExpression.get())) |
| return ExprError(); |
| |
| return SubstitutedExpression; |
| }); |
| } |
| |
| template<typename TemplateDeclT> |
| static bool CheckConstraintSatisfaction(Sema &S, TemplateDeclT *Template, |
| ArrayRef<const Expr *> ConstraintExprs, |
| ArrayRef<TemplateArgument> TemplateArgs, |
| SourceRange TemplateIDRange, |
| ConstraintSatisfaction &Satisfaction) { |
| if (ConstraintExprs.empty()) { |
| Satisfaction.IsSatisfied = true; |
| return false; |
| } |
| |
| for (auto& Arg : TemplateArgs) |
| if (Arg.isInstantiationDependent()) { |
| // No need to check satisfaction for dependent constraint expressions. |
| Satisfaction.IsSatisfied = true; |
| return false; |
| } |
| |
| Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(), |
| Sema::InstantiatingTemplate::ConstraintsCheck{}, Template, TemplateArgs, |
| TemplateIDRange); |
| if (Inst.isInvalid()) |
| return true; |
| |
| MultiLevelTemplateArgumentList MLTAL; |
| MLTAL.addOuterTemplateArguments(TemplateArgs); |
| |
| for (const Expr *ConstraintExpr : ConstraintExprs) { |
| if (calculateConstraintSatisfaction(S, Template, TemplateArgs, |
| TemplateIDRange.getBegin(), MLTAL, |
| ConstraintExpr, Satisfaction)) |
| return true; |
| if (!Satisfaction.IsSatisfied) |
| // [temp.constr.op] p2 |
| // [...] To determine if a conjunction is satisfied, the satisfaction |
| // of the first operand is checked. If that is not satisfied, the |
| // conjunction is not satisfied. [...] |
| return false; |
| } |
| return false; |
| } |
| |
| bool Sema::CheckConstraintSatisfaction(TemplateDecl *Template, |
| ArrayRef<const Expr *> ConstraintExprs, |
| ArrayRef<TemplateArgument> TemplateArgs, |
| SourceRange TemplateIDRange, |
| ConstraintSatisfaction &Satisfaction) { |
| return ::CheckConstraintSatisfaction(*this, Template, ConstraintExprs, |
| TemplateArgs, TemplateIDRange, |
| Satisfaction); |
| } |
| |
| bool |
| Sema::CheckConstraintSatisfaction(ClassTemplatePartialSpecializationDecl* Part, |
| ArrayRef<const Expr *> ConstraintExprs, |
| ArrayRef<TemplateArgument> TemplateArgs, |
| SourceRange TemplateIDRange, |
| ConstraintSatisfaction &Satisfaction) { |
| return ::CheckConstraintSatisfaction(*this, Part, ConstraintExprs, |
| TemplateArgs, TemplateIDRange, |
| Satisfaction); |
| } |
| |
| bool |
| Sema::CheckConstraintSatisfaction(VarTemplatePartialSpecializationDecl* Partial, |
| ArrayRef<const Expr *> ConstraintExprs, |
| ArrayRef<TemplateArgument> TemplateArgs, |
| SourceRange TemplateIDRange, |
| ConstraintSatisfaction &Satisfaction) { |
| return ::CheckConstraintSatisfaction(*this, Partial, ConstraintExprs, |
| TemplateArgs, TemplateIDRange, |
| Satisfaction); |
| } |
| |
| bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr, |
| ConstraintSatisfaction &Satisfaction) { |
| return calculateConstraintSatisfaction( |
| *this, ConstraintExpr, Satisfaction, |
| [](const Expr *AtomicExpr) -> ExprResult { |
| return ExprResult(const_cast<Expr *>(AtomicExpr)); |
| }); |
| } |
| |
| bool Sema::EnsureTemplateArgumentListConstraints( |
| TemplateDecl *TD, ArrayRef<TemplateArgument> TemplateArgs, |
| SourceRange TemplateIDRange) { |
| ConstraintSatisfaction Satisfaction; |
| llvm::SmallVector<const Expr *, 3> AssociatedConstraints; |
| TD->getAssociatedConstraints(AssociatedConstraints); |
| if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgs, |
| TemplateIDRange, Satisfaction)) |
| return true; |
| |
| if (!Satisfaction.IsSatisfied) { |
| SmallString<128> TemplateArgString; |
| TemplateArgString = " "; |
| TemplateArgString += getTemplateArgumentBindingsText( |
| TD->getTemplateParameters(), TemplateArgs.data(), TemplateArgs.size()); |
| |
| Diag(TemplateIDRange.getBegin(), |
| diag::err_template_arg_list_constraints_not_satisfied) |
| << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD |
| << TemplateArgString << TemplateIDRange; |
| DiagnoseUnsatisfiedConstraint(Satisfaction); |
| return true; |
| } |
| return false; |
| } |
| |
| static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S, |
| Expr *SubstExpr, |
| bool First = true) { |
| SubstExpr = SubstExpr->IgnoreParenImpCasts(); |
| if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) { |
| switch (BO->getOpcode()) { |
| // These two cases will in practice only be reached when using fold |
| // expressions with || and &&, since otherwise the || and && will have been |
| // broken down into atomic constraints during satisfaction checking. |
| case BO_LOr: |
| // Or evaluated to false - meaning both RHS and LHS evaluated to false. |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), |
| /*First=*/false); |
| return; |
| case BO_LAnd: |
| bool LHSSatisfied; |
| BO->getLHS()->EvaluateAsBooleanCondition(LHSSatisfied, S.Context); |
| if (LHSSatisfied) { |
| // LHS is true, so RHS must be false. |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First); |
| return; |
| } |
| // LHS is false |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First); |
| |
| // RHS might also be false |
| bool RHSSatisfied; |
| BO->getRHS()->EvaluateAsBooleanCondition(RHSSatisfied, S.Context); |
| if (!RHSSatisfied) |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), |
| /*First=*/false); |
| return; |
| case BO_GE: |
| case BO_LE: |
| case BO_GT: |
| case BO_LT: |
| case BO_EQ: |
| case BO_NE: |
| if (BO->getLHS()->getType()->isIntegerType() && |
| BO->getRHS()->getType()->isIntegerType()) { |
| Expr::EvalResult SimplifiedLHS; |
| Expr::EvalResult SimplifiedRHS; |
| BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context); |
| BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context); |
| if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) { |
| S.Diag(SubstExpr->getBeginLoc(), |
| diag::note_atomic_constraint_evaluated_to_false_elaborated) |
| << (int)First << SubstExpr |
| << SimplifiedLHS.Val.getInt().toString(10) |
| << BinaryOperator::getOpcodeStr(BO->getOpcode()) |
| << SimplifiedRHS.Val.getInt().toString(10); |
| return; |
| } |
| } |
| break; |
| |
| default: |
| break; |
| } |
| } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) { |
| if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) { |
| S.Diag( |
| CSE->getSourceRange().getBegin(), |
| diag:: |
| note_single_arg_concept_specialization_constraint_evaluated_to_false) |
| << (int)First |
| << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument() |
| << CSE->getNamedConcept(); |
| } else { |
| S.Diag(SubstExpr->getSourceRange().getBegin(), |
| diag::note_concept_specialization_constraint_evaluated_to_false) |
| << (int)First << CSE; |
| } |
| S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction()); |
| return; |
| } |
| |
| S.Diag(SubstExpr->getSourceRange().getBegin(), |
| diag::note_atomic_constraint_evaluated_to_false) |
| << (int)First << SubstExpr; |
| } |
| |
| template<typename SubstitutionDiagnostic> |
| static void diagnoseUnsatisfiedConstraintExpr( |
| Sema &S, const Expr *E, |
| const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record, |
| bool First = true) { |
| if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){ |
| S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed) |
| << Diag->second; |
| return; |
| } |
| |
| diagnoseWellFormedUnsatisfiedConstraintExpr(S, |
| Record.template get<Expr *>(), First); |
| } |
| |
| void Sema::DiagnoseUnsatisfiedConstraint( |
| const ConstraintSatisfaction& Satisfaction) { |
| assert(!Satisfaction.IsSatisfied && |
| "Attempted to diagnose a satisfied constraint"); |
| bool First = true; |
| for (auto &Pair : Satisfaction.Details) { |
| diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); |
| First = false; |
| } |
| } |
| |
| void Sema::DiagnoseUnsatisfiedConstraint( |
| const ASTConstraintSatisfaction &Satisfaction) { |
| assert(!Satisfaction.IsSatisfied && |
| "Attempted to diagnose a satisfied constraint"); |
| bool First = true; |
| for (auto &Pair : Satisfaction) { |
| diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First); |
| First = false; |
| } |
| } |
| |
| 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()) |
| 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<NormalizedConstraint, NormalizedConstraint> *, 1, |
| CompoundConstraintKind>; |
| |
| llvm::PointerUnion<AtomicConstraint *, CompoundConstraint> Constraint; |
| |
| NormalizedConstraint(AtomicConstraint *C): Constraint{C} { }; |
| NormalizedConstraint(ASTContext &C, NormalizedConstraint LHS, |
| NormalizedConstraint RHS, CompoundConstraintKind Kind) |
| : Constraint{CompoundConstraint{ |
| new (C) std::pair<NormalizedConstraint, NormalizedConstraint>{LHS, |
| RHS}, |
| Kind}} { }; |
| |
| CompoundConstraintKind getCompoundKind() const { |
| assert(!isAtomic() && "getCompoundKind called on atomic constraint."); |
| return Constraint.get<CompoundConstraint>().getInt(); |
| } |
| |
| bool isAtomic() const { return Constraint.is<AtomicConstraint *>(); } |
| |
| NormalizedConstraint &getLHS() const { |
| assert(!isAtomic() && "getLHS called on atomic constraint."); |
| return Constraint.get<CompoundConstraint>().getPointer()->first; |
| } |
| |
| NormalizedConstraint &getRHS() const { |
| assert(!isAtomic() && "getRHS called on atomic constraint."); |
| return Constraint.get<CompoundConstraint>().getPointer()->second; |
| } |
| |
| AtomicConstraint *getAtomicConstraint() const { |
| assert(isAtomic() && |
| "getAtomicConstraint called on non-atomic constraint."); |
| return Constraint.get<AtomicConstraint *>(); |
| } |
| |
| static llvm::Optional<NormalizedConstraint> |
| fromConstraintExprs(Sema &S, NamedDecl *D, ArrayRef<const Expr *> 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<NormalizedConstraint>{}; |
| llvm::Optional<NormalizedConstraint> 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>{}; |
| NormalizedConstraint NewConjunction(S.Context, std::move(*Conjunction), |
| std::move(*Next), CCK_Conjunction); |
| *Conjunction = std::move(NewConjunction); |
| } |
| 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(TemplateParams->size()); |
| 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<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; |
| } |
| |
| llvm::Optional<NormalizedConstraint> |
| 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<const BinaryOperator>(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<const ConceptSpecializationExpr>(E)) { |
| Optional<NormalizedConstraint> 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<A1, A2, ..., AN>, |
| // 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<llvm::SmallVector<AtomicConstraint *, 2>, 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(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(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<const Expr *> P, |
| NamedDecl *DQ, ArrayRef<const Expr *> 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<const Expr *> AC1, |
| NamedDecl *D2, ArrayRef<const Expr *> 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<NamedDecl *, NamedDecl *> 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; |
| } |