diff options
Diffstat (limited to 'clang/lib/Sema/SemaConcept.cpp')
| -rw-r--r-- | clang/lib/Sema/SemaConcept.cpp | 821 |
1 files changed, 762 insertions, 59 deletions
diff --git a/clang/lib/Sema/SemaConcept.cpp b/clang/lib/Sema/SemaConcept.cpp index 848ccf543445..018ac2d7dc9d 100644 --- a/clang/lib/Sema/SemaConcept.cpp +++ b/clang/lib/Sema/SemaConcept.cpp @@ -11,15 +11,24 @@ // //===----------------------------------------------------------------------===// +#include "clang/Sema/SemaConcept.h" #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 "clang/Basic/OperatorPrecedence.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/PointerUnion.h" using namespace clang; using namespace sema; -bool Sema::CheckConstraintExpression(Expr *ConstraintExpression) { +bool +Sema::CheckConstraintExpression(Expr *ConstraintExpression, Token NextToken, + bool *PossibleNonPrimary, + bool IsTrailingRequiresClause) { // C++2a [temp.constr.atomic]p1 // ..E shall be a constant expression of type bool. @@ -27,99 +36,793 @@ bool Sema::CheckConstraintExpression(Expr *ConstraintExpression) { if (auto *BinOp = dyn_cast<BinaryOperator>(ConstraintExpression)) { if (BinOp->getOpcode() == BO_LAnd || BinOp->getOpcode() == BO_LOr) - return CheckConstraintExpression(BinOp->getLHS()) && - CheckConstraintExpression(BinOp->getRHS()); + return CheckConstraintExpression(BinOp->getLHS(), NextToken, + PossibleNonPrimary) && + CheckConstraintExpression(BinOp->getRHS(), NextToken, + PossibleNonPrimary); } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression)) - return CheckConstraintExpression(C->getSubExpr()); + return CheckConstraintExpression(C->getSubExpr(), NextToken, + PossibleNonPrimary); + + QualType Type = ConstraintExpression->getType(); + + auto CheckForNonPrimary = [&] { + if (PossibleNonPrimary) + *PossibleNonPrimary = + // We have the following case: + // template<typename> requires func(0) struct S { }; + // The user probably isn't aware of the parentheses required around + // the function call, and we're only going to parse 'func' as the + // primary-expression, and complain that it is of non-bool type. + (NextToken.is(tok::l_paren) && + (IsTrailingRequiresClause || + (Type->isDependentType() && + IsDependentFunctionNameExpr(ConstraintExpression)) || + Type->isFunctionType() || + Type->isSpecificBuiltinType(BuiltinType::Overload))) || + // We have the following case: + // template<typename T> requires size_<T> == 0 struct S { }; + // The user probably isn't aware of the parentheses required around + // the binary operator, and we're only going to parse 'func' as the + // first operand, and complain that it is of non-bool type. + getBinOpPrecedence(NextToken.getKind(), + /*GreaterThanIsOperator=*/true, + getLangOpts().CPlusPlus11) > prec::LogicalAnd; + }; // An atomic constraint! - if (ConstraintExpression->isTypeDependent()) + if (ConstraintExpression->isTypeDependent()) { + CheckForNonPrimary(); return true; + } - QualType Type = ConstraintExpression->getType(); if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) { Diag(ConstraintExpression->getExprLoc(), diag::err_non_bool_atomic_constraint) << Type << ConstraintExpression->getSourceRange(); + CheckForNonPrimary(); return false; } + + if (PossibleNonPrimary) + *PossibleNonPrimary = false; return true; } -bool -Sema::CalculateConstraintSatisfaction(ConceptDecl *NamedConcept, - MultiLevelTemplateArgumentList &MLTAL, - Expr *ConstraintExpr, - bool &IsSatisfied) { +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) { - if (CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getLHS(), - IsSatisfied)) + if (BO->getOpcode() == BO_LAnd || BO->getOpcode() == BO_LOr) { + if (calculateConstraintSatisfaction(S, BO->getLHS(), Satisfaction, + Evaluator)) return true; - if (!IsSatisfied) + + 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; - return CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getRHS(), - IsSatisfied); - } else if (BO->getOpcode() == BO_LOr) { - if (CalculateConstraintSatisfaction(NamedConcept, MLTAL, BO->getLHS(), - IsSatisfied)) - return true; - if (IsSatisfied) + + 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(NamedConcept, MLTAL, BO->getRHS(), - IsSatisfied); + + return calculateConstraintSatisfaction(S, BO->getRHS(), Satisfaction, + std::forward<AtomicEvaluator>(Evaluator)); } } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) - return CalculateConstraintSatisfaction(NamedConcept, MLTAL, C->getSubExpr(), - IsSatisfied); + return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction, + std::forward<AtomicEvaluator>(Evaluator)); - EnterExpressionEvaluationContext ConstantEvaluated( - *this, Sema::ExpressionEvaluationContext::ConstantEvaluated); + // An atomic constraint expression + ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr); - // Atomic constraint - substitute arguments and check satisfaction. - ExprResult E; - { - TemplateDeductionInfo Info(ConstraintExpr->getBeginLoc()); - InstantiatingTemplate Inst(*this, ConstraintExpr->getBeginLoc(), - InstantiatingTemplate::ConstraintSubstitution{}, - NamedConcept, Info, - ConstraintExpr->getSourceRange()); - if (Inst.isInvalid()) - return true; - // We do not want error diagnostics escaping here. - Sema::SFINAETrap Trap(*this); + if (SubstitutedAtomicExpr.isInvalid()) + return true; + + if (!SubstitutedAtomicExpr.isUsable()) + // Evaluator has decided satisfaction without yielding an expression. + return false; - E = SubstExpr(ConstraintExpr, MLTAL); - if (E.isInvalid() || Trap.hasErrorOccurred()) { + 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 - // ...If substitution results in an invalid type or expression, the - // constraint is not satisfied. - IsSatisfied = false; + // ...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); +} - if (!CheckConstraintExpression(E.get())) +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; - SmallVector<PartialDiagnosticAt, 2> EvaluationDiags; - Expr::EvalResult EvalResult; - EvalResult.Diag = &EvaluationDiags; - if (!E.get()->EvaluateAsRValue(EvalResult, Context)) { - // C++2a [temp.constr.atomic]p1 - // ...E shall be a constant expression of type bool. - Diag(E.get()->getBeginLoc(), - diag::err_non_constant_constraint_expression) - << E.get()->getSourceRange(); - for (const PartialDiagnosticAt &PDiag : EvaluationDiags) - Diag(PDiag.first, PDiag.second); + 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; + } +} + +const NormalizedConstraint * +Sema::getNormalizedAssociatedConstraints( + NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) { + auto CacheEntry = NormalizationCache.find(ConstrainedDecl); + if (CacheEntry == NormalizationCache.end()) { + auto Normalized = + NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl, + AssociatedConstraints); + CacheEntry = + NormalizationCache + .try_emplace(ConstrainedDecl, + Normalized + ? new (Context) NormalizedConstraint( + std::move(*Normalized)) + : nullptr) + .first; + } + return CacheEntry->second; +} + +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( + MutableArrayRef<TemplateArgumentLoc>( + new (S.Context) TemplateArgumentLoc[OccurringIndices.count()], + OccurringIndices.count())); + for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I) + if (OccurringIndices[I]) + new (&(*Atomic.ParameterMapping)[J++]) TemplateArgumentLoc( + 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; +} + +Optional<NormalizedConstraint> +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 None; + 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; +} + +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, std::move(*LHS), std::move(*RHS), + BO->getOpcode() == BO_LAnd ? CCK_Conjunction : CCK_Disjunction); + } + } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) { + const 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. + // [...] + ConceptDecl *CD = CSE->getNamedConcept(); + SubNF = S.getNormalizedAssociatedConstraints(CD, + {CD->getConstraintExpr()}); + if (!SubNF) + return None; + } + + Optional<NormalizedConstraint> New; + New.emplace(S.Context, *SubNF); + + if (substituteParameterMappings( + S, *New, CSE->getNamedConcept(), + CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten())) + return None; + + return New; + } + return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)}; +} + +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; +} + +template<typename AtomicSubsumptionEvaluator> +static bool subsumes(NormalForm PDNF, NormalForm QCNF, + AtomicSubsumptionEvaluator E) { + // 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 (E(*Pia, *Qjb)) { + Found = true; + break; + } + } + if (Found) + break; + } + if (!Found) + return false; + } + } + return true; +} + +template<typename AtomicSubsumptionEvaluator> +static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P, + NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes, + AtomicSubsumptionEvaluator E) { + // 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 = S.getNormalizedAssociatedConstraints(DP, P); + if (!PNormalized) + return true; + const NormalForm PDNF = makeDNF(*PNormalized); + + auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q); + if (!QNormalized) return true; + const NormalForm QCNF = makeCNF(*QNormalized); + + Subsumes = subsumes(PDNF, QCNF, E); + 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; } - IsSatisfied = EvalResult.Val.getInt().getBoolValue(); + 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, + [this] (const AtomicConstraint &A, const AtomicConstraint &B) { + return A.subsumes(Context, B); + })) + return true; + SubsumptionCache.try_emplace(Key, Result); return false; -}
\ No newline at end of file +} + +bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1, + ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) { + if (isSFINAEContext()) + // No need to work here because our notes would be discarded. + return false; + + if (AC1.empty() || AC2.empty()) + return false; + + auto NormalExprEvaluator = + [this] (const AtomicConstraint &A, const AtomicConstraint &B) { + return A.subsumes(Context, B); + }; + + const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr; + auto IdenticalExprEvaluator = + [&] (const AtomicConstraint &A, const AtomicConstraint &B) { + if (!A.hasMatchingParameterMapping(Context, B)) + return false; + const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr; + if (EA == EB) + return true; + + // Not the same source level expression - are the expressions + // identical? + llvm::FoldingSetNodeID IDA, IDB; + EA->Profile(IDA, Context, /*Cannonical=*/true); + EB->Profile(IDB, Context, /*Cannonical=*/true); + if (IDA != IDB) + return false; + + AmbiguousAtomic1 = EA; + AmbiguousAtomic2 = EB; + return true; + }; + + { + // The subsumption checks might cause diagnostics + SFINAETrap Trap(*this); + auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1); + if (!Normalized1) + return false; + const NormalForm DNF1 = makeDNF(*Normalized1); + const NormalForm CNF1 = makeCNF(*Normalized1); + + auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2); + if (!Normalized2) + return false; + const NormalForm DNF2 = makeDNF(*Normalized2); + const NormalForm CNF2 = makeCNF(*Normalized2); + + bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator); + bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator); + bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator); + bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator); + if (Is1AtLeastAs2 == Is1AtLeastAs2Normally && + Is2AtLeastAs1 == Is2AtLeastAs1Normally) + // Same result - no ambiguity was caused by identical atomic expressions. + return false; + } + + // A different result! Some ambiguous atomic constraint(s) caused a difference + assert(AmbiguousAtomic1 && AmbiguousAtomic2); + + Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints) + << AmbiguousAtomic1->getSourceRange(); + Diag(AmbiguousAtomic2->getBeginLoc(), + diag::note_ambiguous_atomic_constraints_similar_expression) + << AmbiguousAtomic2->getSourceRange(); + return true; +} |