//===-- 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/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/Sema/Overload.h"
#include "clang/Sema/Initialization.h"
#include "clang/Sema/SemaInternal.h"
#include "clang/AST/ExprConcepts.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, Token NextToken,
bool *PossibleNonPrimary,
bool IsTrailingRequiresClause) {
// 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(), NextToken,
PossibleNonPrimary) &&
CheckConstraintExpression(BinOp->getRHS(), NextToken,
PossibleNonPrimary);
} else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
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()) {
CheckForNonPrimary();
return true;
}
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;
}
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;
}
static bool calculateConstraintSatisfaction(
Sema &S, const NamedDecl *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{},
const_cast<NamedDecl *>(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;
});
}
static bool CheckConstraintSatisfaction(Sema &S, const NamedDecl *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{},
const_cast<NamedDecl *>(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(
const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
ArrayRef<TemplateArgument> TemplateArgs, SourceRange TemplateIDRange,
ConstraintSatisfaction &OutSatisfaction) {
if (ConstraintExprs.empty()) {
OutSatisfaction.IsSatisfied = true;
return false;
}
llvm::FoldingSetNodeID ID;
void *InsertPos;
ConstraintSatisfaction *Satisfaction = nullptr;
bool ShouldCache = LangOpts.ConceptSatisfactionCaching && Template;
if (ShouldCache) {
ConstraintSatisfaction::Profile(ID, Context, Template, TemplateArgs);
Satisfaction = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos);
if (Satisfaction) {
OutSatisfaction = *Satisfaction;
return false;
}
Satisfaction = new ConstraintSatisfaction(Template, TemplateArgs);
} else {
Satisfaction = &OutSatisfaction;
}
if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
TemplateArgs, TemplateIDRange,
*Satisfaction)) {
if (ShouldCache)
delete Satisfaction;
return true;
}
if (ShouldCache) {
// We cannot use InsertNode here because CheckConstraintSatisfaction might
// have invalidated it.
SatisfactionCache.InsertNode(Satisfaction);
OutSatisfaction = *Satisfaction;
}
return false;
}
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::CheckFunctionConstraints(const FunctionDecl *FD,
ConstraintSatisfaction &Satisfaction,
SourceLocation UsageLoc) {
const Expr *RC = FD->getTrailingRequiresClause();
if (RC->isInstantiationDependent()) {
Satisfaction.IsSatisfied = true;
return false;
}
Qualifiers ThisQuals;
CXXRecordDecl *Record = nullptr;
if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
ThisQuals = Method->getMethodQualifiers();
Record = const_cast<CXXRecordDecl *>(Method->getParent());
}
CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
// We substitute with empty arguments in order to rebuild the atomic
// constraint in a constant-evaluated context.
// FIXME: Should this be a dedicated TreeTransform?
return CheckConstraintSatisfaction(
FD, {RC}, /*TemplateArgs=*/{},
SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
Satisfaction);
}
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 diagnoseUnsatisfiedRequirement(Sema &S,
concepts::ExprRequirement *Req,
bool First) {
assert(!Req->isSatisfied()
&& "Diagnose() can only be used on an unsatisfied requirement");
switch (Req->getSatisfactionStatus()) {
case concepts::ExprRequirement::SS_Dependent:
llvm_unreachable("Diagnosing a dependent requirement");
break;
case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
if (!SubstDiag->DiagMessage.empty())
S.Diag(SubstDiag->DiagLoc,
diag::note_expr_requirement_expr_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity
<< SubstDiag->DiagMessage;
else
S.Diag(SubstDiag->DiagLoc,
diag::note_expr_requirement_expr_unknown_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity;
break;
}
case concepts::ExprRequirement::SS_NoexceptNotMet:
S.Diag(Req->getNoexceptLoc(),
diag::note_expr_requirement_noexcept_not_met)
<< (int)First << Req->getExpr();
break;
case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
auto *SubstDiag =
Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
if (!SubstDiag->DiagMessage.empty())
S.Diag(SubstDiag->DiagLoc,
diag::note_expr_requirement_type_requirement_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity
<< SubstDiag->DiagMessage;
else
S.Diag(SubstDiag->DiagLoc,
diag::note_expr_requirement_type_requirement_unknown_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity;
break;
}
case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
ConceptSpecializationExpr *ConstraintExpr =
Req->getReturnTypeRequirementSubstitutedConstraintExpr();
if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1)
// A simple case - expr type is the type being constrained and the concept
// was not provided arguments.
S.Diag(ConstraintExpr->getBeginLoc(),
diag::note_expr_requirement_constraints_not_satisfied_simple)
<< (int)First << S.BuildDecltypeType(Req->getExpr(),
Req->getExpr()->getBeginLoc())
<< ConstraintExpr->getNamedConcept();
else
S.Diag(ConstraintExpr->getBeginLoc(),
diag::note_expr_requirement_constraints_not_satisfied)
<< (int)First << ConstraintExpr;
S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
break;
}
case concepts::ExprRequirement::SS_Satisfied:
llvm_unreachable("We checked this above");
}
}
static void diagnoseUnsatisfiedRequirement(Sema &S,
concepts::TypeRequirement *Req,
bool First) {
assert(!Req->isSatisfied()
&& "Diagnose() can only be used on an unsatisfied requirement");
switch (Req->getSatisfactionStatus()) {
case concepts::TypeRequirement::SS_Dependent:
llvm_unreachable("Diagnosing a dependent requirement");
return;
case concepts::TypeRequirement::SS_SubstitutionFailure: {
auto *SubstDiag = Req->getSubstitutionDiagnostic();
if (!SubstDiag->DiagMessage.empty())
S.Diag(SubstDiag->DiagLoc,
diag::note_type_requirement_substitution_error) << (int)First
<< SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
else
S.Diag(SubstDiag->DiagLoc,
diag::note_type_requirement_unknown_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity;
return;
}
default:
llvm_unreachable("Unknown satisfaction status");
return;
}
}
static void diagnoseUnsatisfiedRequirement(Sema &S,
concepts::NestedRequirement *Req,
bool First) {
if (Req->isSubstitutionFailure()) {
concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
Req->getSubstitutionDiagnostic();
if (!SubstDiag->DiagMessage.empty())
S.Diag(SubstDiag->DiagLoc,
diag::note_nested_requirement_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity
<< SubstDiag->DiagMessage;
else
S.Diag(SubstDiag->DiagLoc,
diag::note_nested_requirement_unknown_substitution_error)
<< (int)First << SubstDiag->SubstitutedEntity;
return;
}
S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
}
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;
} else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
for (concepts::Requirement *Req : RE->getRequirements())
if (!Req->isDependent() && !Req->isSatisfied()) {
if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
diagnoseUnsatisfiedRequirement(S, E, First);
else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
diagnoseUnsatisfiedRequirement(S, T, First);
else
diagnoseUnsatisfiedRequirement(
S, cast<concepts::NestedRequirement>(Req), First);
break;
}
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,
bool First) {
assert(!Satisfaction.IsSatisfied &&
"Attempted to diagnose a satisfied constraint");
for (auto &Pair : Satisfaction.Details) {
diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
First = false;
}
}
void Sema::DiagnoseUnsatisfiedConstraint(
const ASTConstraintSatisfaction &Satisfaction,
bool First) {
assert(!Satisfaction.IsSatisfied &&
"Attempted to diagnose a satisfied constraint");
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;
Atomic.ParameterMapping.emplace(
MutableArrayRef<TemplateArgumentLoc>(
new (S.Context) TemplateArgumentLoc[SubstArgs.size()],
SubstArgs.size()));
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;
}
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;
}
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;
}
concepts::ExprRequirement::ExprRequirement(
Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
ReturnTypeRequirement Req, SatisfactionStatus Status,
ConceptSpecializationExpr *SubstitutedConstraintExpr) :
Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
Status == SS_Dependent &&
(E->containsUnexpandedParameterPack() ||
Req.containsUnexpandedParameterPack()),
Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
Status(Status) {
assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
"Simple requirement must not have a return type requirement or a "
"noexcept specification");
assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
(SubstitutedConstraintExpr != nullptr));
}
concepts::ExprRequirement::ExprRequirement(
SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
Status(SS_ExprSubstitutionFailure) {
assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
"Simple requirement must not have a return type requirement or a "
"noexcept specification");
}
concepts::ExprRequirement::ReturnTypeRequirement::
ReturnTypeRequirement(TemplateParameterList *TPL) :
TypeConstraintInfo(TPL, 0) {
assert(TPL->size() == 1);
const TypeConstraint *TC =
cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
assert(TC &&
"TPL must have a template type parameter with a type constraint");
auto *Constraint =
cast_or_null<ConceptSpecializationExpr>(
TC->getImmediatelyDeclaredConstraint());
bool Dependent = false;
if (Constraint->getTemplateArgsAsWritten()) {
for (auto &ArgLoc :
Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1)) {
if (ArgLoc.getArgument().isDependent()) {
Dependent = true;
break;
}
}
}
TypeConstraintInfo.setInt(Dependent ? 1 : 0);
}
concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
Requirement(RK_Type, T->getType()->isDependentType(),
T->getType()->containsUnexpandedParameterPack(),
// We reach this ctor with either dependent types (in which
// IsSatisfied doesn't matter) or with non-dependent type in
// which the existence of the type indicates satisfaction.
/*IsSatisfied=*/true
), Value(T),
Status(T->getType()->isDependentType() ? SS_Dependent : SS_Satisfied) {}