clang/lib/Sema/SemaConcept.cpp

   1 //===-- SemaConcept.cpp - Semantic Analysis for Constraints and Concepts --===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 //  This file implements semantic analysis for C++ constraints and concepts.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "clang/Sema/SemaConcept.h"
  14 #include "clang/Sema/Sema.h"
  15 #include "clang/Sema/SemaInternal.h"
  16 #include "clang/Sema/SemaDiagnostic.h"
  17 #include "clang/Sema/TemplateDeduction.h"
  18 #include "clang/Sema/Template.h"
  19 #include "clang/Sema/Overload.h"
  20 #include "clang/Sema/Initialization.h"
  21 #include "clang/AST/ExprConcepts.h"
  22 #include "clang/AST/RecursiveASTVisitor.h"
  23 #include "clang/Basic/OperatorPrecedence.h"
  24 #include "llvm/ADT/DenseMap.h"
  25 #include "llvm/ADT/PointerUnion.h"
  26 #include "llvm/ADT/StringExtras.h"
  27
  28 using namespace clang;
  29 using namespace sema;
  30
  31 namespace {
  32 class LogicalBinOp {
  33   OverloadedOperatorKind Op = OO_None;
  34   const Expr *LHS = nullptr;
  35   const Expr *RHS = nullptr;
  36
  37 public:
  38   LogicalBinOp(const Expr *E) {
  39     if (auto *BO = dyn_cast<BinaryOperator>(E)) {
  40       Op = BinaryOperator::getOverloadedOperator(BO->getOpcode());
  41       LHS = BO->getLHS();
  42       RHS = BO->getRHS();
  43     } else if (auto *OO = dyn_cast<CXXOperatorCallExpr>(E)) {
  44       // If OO is not || or && it might not have exactly 2 arguments.
  45       if (OO->getNumArgs() == 2) {
  46         Op = OO->getOperator();
  47         LHS = OO->getArg(0);
  48         RHS = OO->getArg(1);
  49       }
  50     }
  51   }
  52
  53   bool isAnd() const { return Op == OO_AmpAmp; }
  54   bool isOr() const { return Op == OO_PipePipe; }
  55   explicit operator bool() const { return isAnd() || isOr(); }
  56
  57   const Expr *getLHS() const { return LHS; }
  58   const Expr *getRHS() const { return RHS; }
  59 };
  60 }
  61
  62 bool Sema::CheckConstraintExpression(const Expr *ConstraintExpression,
  63                                      Token NextToken, bool *PossibleNonPrimary,
  64                                      bool IsTrailingRequiresClause) {
  65   // C++2a [temp.constr.atomic]p1
  66   // ..E shall be a constant expression of type bool.
  67
  68   ConstraintExpression = ConstraintExpression->IgnoreParenImpCasts();
  69
  70   if (LogicalBinOp BO = ConstraintExpression) {
  71     return CheckConstraintExpression(BO.getLHS(), NextToken,
  72                                      PossibleNonPrimary) &&
  73            CheckConstraintExpression(BO.getRHS(), NextToken,
  74                                      PossibleNonPrimary);
  75   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpression))
  76     return CheckConstraintExpression(C->getSubExpr(), NextToken,
  77                                      PossibleNonPrimary);
  78
  79   QualType Type = ConstraintExpression->getType();
  80
  81   auto CheckForNonPrimary = [&] {
  82     if (PossibleNonPrimary)
  83       *PossibleNonPrimary =
  84           // We have the following case:
  85           // template<typename> requires func(0) struct S { };
  86           // The user probably isn't aware of the parentheses required around
  87           // the function call, and we're only going to parse 'func' as the
  88           // primary-expression, and complain that it is of non-bool type.
  89           (NextToken.is(tok::l_paren) &&
  90            (IsTrailingRequiresClause ||
  91             (Type->isDependentType() &&
  92              isa<UnresolvedLookupExpr>(ConstraintExpression)) ||
  93             Type->isFunctionType() ||
  94             Type->isSpecificBuiltinType(BuiltinType::Overload))) ||
  95           // We have the following case:
  96           // template<typename T> requires size_<T> == 0 struct S { };
  97           // The user probably isn't aware of the parentheses required around
  98           // the binary operator, and we're only going to parse 'func' as the
  99           // first operand, and complain that it is of non-bool type.
 100           getBinOpPrecedence(NextToken.getKind(),
 101                              /*GreaterThanIsOperator=*/true,
 102                              getLangOpts().CPlusPlus11) > prec::LogicalAnd;
 103   };
 104
 105   // An atomic constraint!
 106   if (ConstraintExpression->isTypeDependent()) {
 107     CheckForNonPrimary();
 108     return true;
 109   }
 110
 111   if (!Context.hasSameUnqualifiedType(Type, Context.BoolTy)) {
 112     Diag(ConstraintExpression->getExprLoc(),
 113          diag::err_non_bool_atomic_constraint) << Type
 114         << ConstraintExpression->getSourceRange();
 115     CheckForNonPrimary();
 116     return false;
 117   }
 118
 119   if (PossibleNonPrimary)
 120       *PossibleNonPrimary = false;
 121   return true;
 122 }
 123
 124 template <typename AtomicEvaluator>
 125 static bool
 126 calculateConstraintSatisfaction(Sema &S, const Expr *ConstraintExpr,
 127                                 ConstraintSatisfaction &Satisfaction,
 128                                 AtomicEvaluator &&Evaluator) {
 129   ConstraintExpr = ConstraintExpr->IgnoreParenImpCasts();
 130
 131   if (LogicalBinOp BO = ConstraintExpr) {
 132     if (calculateConstraintSatisfaction(S, BO.getLHS(), Satisfaction,
 133                                         Evaluator))
 134       return true;
 135
 136     bool IsLHSSatisfied = Satisfaction.IsSatisfied;
 137
 138     if (BO.isOr() && IsLHSSatisfied)
 139       // [temp.constr.op] p3
 140       //    A disjunction is a constraint taking two operands. To determine if
 141       //    a disjunction is satisfied, the satisfaction of the first operand
 142       //    is checked. If that is satisfied, the disjunction is satisfied.
 143       //    Otherwise, the disjunction is satisfied if and only if the second
 144       //    operand is satisfied.
 145       return false;
 146
 147     if (BO.isAnd() && !IsLHSSatisfied)
 148       // [temp.constr.op] p2
 149       //    A conjunction is a constraint taking two operands. To determine if
 150       //    a conjunction is satisfied, the satisfaction of the first operand
 151       //    is checked. If that is not satisfied, the conjunction is not
 152       //    satisfied. Otherwise, the conjunction is satisfied if and only if
 153       //    the second operand is satisfied.
 154       return false;
 155
 156     return calculateConstraintSatisfaction(
 157         S, BO.getRHS(), Satisfaction, std::forward<AtomicEvaluator>(Evaluator));
 158   } else if (auto *C = dyn_cast<ExprWithCleanups>(ConstraintExpr)) {
 159     return calculateConstraintSatisfaction(S, C->getSubExpr(), Satisfaction,
 160         std::forward<AtomicEvaluator>(Evaluator));
 161   }
 162
 163   // An atomic constraint expression
 164   ExprResult SubstitutedAtomicExpr = Evaluator(ConstraintExpr);
 165
 166   if (SubstitutedAtomicExpr.isInvalid())
 167     return true;
 168
 169   if (!SubstitutedAtomicExpr.isUsable())
 170     // Evaluator has decided satisfaction without yielding an expression.
 171     return false;
 172
 173   EnterExpressionEvaluationContext ConstantEvaluated(
 174       S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
 175   SmallVector<PartialDiagnosticAt, 2> EvaluationDiags;
 176   Expr::EvalResult EvalResult;
 177   EvalResult.Diag = &EvaluationDiags;
 178   if (!SubstitutedAtomicExpr.get()->EvaluateAsConstantExpr(EvalResult,
 179                                                            S.Context) ||
 180       !EvaluationDiags.empty()) {
 181     // C++2a [temp.constr.atomic]p1
 182     //   ...E shall be a constant expression of type bool.
 183     S.Diag(SubstitutedAtomicExpr.get()->getBeginLoc(),
 184            diag::err_non_constant_constraint_expression)
 185         << SubstitutedAtomicExpr.get()->getSourceRange();
 186     for (const PartialDiagnosticAt &PDiag : EvaluationDiags)
 187       S.Diag(PDiag.first, PDiag.second);
 188     return true;
 189   }
 190
 191   assert(EvalResult.Val.isInt() &&
 192          "evaluating bool expression didn't produce int");
 193   Satisfaction.IsSatisfied = EvalResult.Val.getInt().getBoolValue();
 194   if (!Satisfaction.IsSatisfied)
 195     Satisfaction.Details.emplace_back(ConstraintExpr,
 196                                       SubstitutedAtomicExpr.get());
 197
 198   return false;
 199 }
 200
 201 static bool calculateConstraintSatisfaction(
 202     Sema &S, const NamedDecl *Template, SourceLocation TemplateNameLoc,
 203     const MultiLevelTemplateArgumentList &MLTAL, const Expr *ConstraintExpr,
 204     ConstraintSatisfaction &Satisfaction) {
 205   return calculateConstraintSatisfaction(
 206       S, ConstraintExpr, Satisfaction, [&](const Expr *AtomicExpr) {
 207         EnterExpressionEvaluationContext ConstantEvaluated(
 208             S, Sema::ExpressionEvaluationContext::ConstantEvaluated);
 209
 210         // Atomic constraint - substitute arguments and check satisfaction.
 211         ExprResult SubstitutedExpression;
 212         {
 213           TemplateDeductionInfo Info(TemplateNameLoc);
 214           Sema::InstantiatingTemplate Inst(S, AtomicExpr->getBeginLoc(),
 215               Sema::InstantiatingTemplate::ConstraintSubstitution{},
 216               const_cast<NamedDecl *>(Template), Info,
 217               AtomicExpr->getSourceRange());
 218           if (Inst.isInvalid())
 219             return ExprError();
 220           // We do not want error diagnostics escaping here.
 221           Sema::SFINAETrap Trap(S);
 222           SubstitutedExpression = S.SubstExpr(const_cast<Expr *>(AtomicExpr),
 223                                               MLTAL);
 224           // Substitution might have stripped off a contextual conversion to
 225           // bool if this is the operand of an '&&' or '||'. For example, we
 226           // might lose an lvalue-to-rvalue conversion here. If so, put it back
 227           // before we try to evaluate.
 228           if (!SubstitutedExpression.isInvalid())
 229             SubstitutedExpression =
 230                 S.PerformContextuallyConvertToBool(SubstitutedExpression.get());
 231           if (SubstitutedExpression.isInvalid() || Trap.hasErrorOccurred()) {
 232             // C++2a [temp.constr.atomic]p1
 233             //   ...If substitution results in an invalid type or expression, the
 234             //   constraint is not satisfied.
 235             if (!Trap.hasErrorOccurred())
 236               // A non-SFINAE error has occurred as a result of this
 237               // substitution.
 238               return ExprError();
 239
 240             PartialDiagnosticAt SubstDiag{SourceLocation(),
 241                                           PartialDiagnostic::NullDiagnostic()};
 242             Info.takeSFINAEDiagnostic(SubstDiag);
 243             // FIXME: Concepts: This is an unfortunate consequence of there
 244             //  being no serialization code for PartialDiagnostics and the fact
 245             //  that serializing them would likely take a lot more storage than
 246             //  just storing them as strings. We would still like, in the
 247             //  future, to serialize the proper PartialDiagnostic as serializing
 248             //  it as a string defeats the purpose of the diagnostic mechanism.
 249             SmallString<128> DiagString;
 250             DiagString = ": ";
 251             SubstDiag.second.EmitToString(S.getDiagnostics(), DiagString);
 252             unsigned MessageSize = DiagString.size();
 253             char *Mem = new (S.Context) char[MessageSize];
 254             memcpy(Mem, DiagString.c_str(), MessageSize);
 255             Satisfaction.Details.emplace_back(
 256                 AtomicExpr,
 257                 new (S.Context) ConstraintSatisfaction::SubstitutionDiagnostic{
 258                         SubstDiag.first, StringRef(Mem, MessageSize)});
 259             Satisfaction.IsSatisfied = false;
 260             return ExprEmpty();
 261           }
 262         }
 263
 264         if (!S.CheckConstraintExpression(SubstitutedExpression.get()))
 265           return ExprError();
 266
 267         return SubstitutedExpression;
 268       });
 269 }
 270
 271 static bool CheckConstraintSatisfaction(
 272     Sema &S, const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
 273     const MultiLevelTemplateArgumentList &TemplateArgsLists,
 274     SourceRange TemplateIDRange, ConstraintSatisfaction &Satisfaction) {
 275   if (ConstraintExprs.empty()) {
 276     Satisfaction.IsSatisfied = true;
 277     return false;
 278   }
 279
 280   if (TemplateArgsLists.isAnyArgInstantiationDependent()) {
 281     // No need to check satisfaction for dependent constraint expressions.
 282     Satisfaction.IsSatisfied = true;
 283     return false;
 284   }
 285
 286   ArrayRef<TemplateArgument> TemplateArgs =
 287       TemplateArgsLists.getNumSubstitutedLevels() > 0
 288           ? TemplateArgsLists.getOutermost()
 289           : ArrayRef<TemplateArgument> {};
 290   Sema::InstantiatingTemplate Inst(S, TemplateIDRange.getBegin(),
 291       Sema::InstantiatingTemplate::ConstraintsCheck{},
 292       const_cast<NamedDecl *>(Template), TemplateArgs, TemplateIDRange);
 293   if (Inst.isInvalid())
 294     return true;
 295
 296   for (const Expr *ConstraintExpr : ConstraintExprs) {
 297     if (calculateConstraintSatisfaction(S, Template, TemplateIDRange.getBegin(),
 298                                         TemplateArgsLists, ConstraintExpr,
 299                                         Satisfaction))
 300       return true;
 301     if (!Satisfaction.IsSatisfied)
 302       // [temp.constr.op] p2
 303       //   [...] To determine if a conjunction is satisfied, the satisfaction
 304       //   of the first operand is checked. If that is not satisfied, the
 305       //   conjunction is not satisfied. [...]
 306       return false;
 307   }
 308   return false;
 309 }
 310
 311 bool Sema::CheckConstraintSatisfaction(
 312     const NamedDecl *Template, ArrayRef<const Expr *> ConstraintExprs,
 313     const MultiLevelTemplateArgumentList &TemplateArgsLists,
 314     SourceRange TemplateIDRange, ConstraintSatisfaction &OutSatisfaction) {
 315   if (ConstraintExprs.empty()) {
 316     OutSatisfaction.IsSatisfied = true;
 317     return false;
 318   }
 319   if (!Template) {
 320     return ::CheckConstraintSatisfaction(*this, nullptr, ConstraintExprs,
 321                                          TemplateArgsLists, TemplateIDRange,
 322                                          OutSatisfaction);
 323   }
 324
 325   // A list of the template argument list flattened in a predictible manner for
 326   // the purposes of caching. The ConstraintSatisfaction type is in AST so it
 327   // has no access to the MultiLevelTemplateArgumentList, so this has to happen
 328   // here.
 329   llvm::SmallVector<TemplateArgument, 4> FlattenedArgs;
 330   for (ArrayRef<TemplateArgument> List : TemplateArgsLists)
 331     FlattenedArgs.insert(FlattenedArgs.end(), List.begin(), List.end());
 332
 333   llvm::FoldingSetNodeID ID;
 334   ConstraintSatisfaction::Profile(ID, Context, Template, FlattenedArgs);
 335   void *InsertPos;
 336   if (auto *Cached = SatisfactionCache.FindNodeOrInsertPos(ID, InsertPos)) {
 337     OutSatisfaction = *Cached;
 338     return false;
 339   }
 340   auto Satisfaction =
 341       std::make_unique<ConstraintSatisfaction>(Template, FlattenedArgs);
 342   if (::CheckConstraintSatisfaction(*this, Template, ConstraintExprs,
 343                                     TemplateArgsLists, TemplateIDRange,
 344                                     *Satisfaction)) {
 345     return true;
 346   }
 347   OutSatisfaction = *Satisfaction;
 348   // We cannot use InsertPos here because CheckConstraintSatisfaction might have
 349   // invalidated it.
 350   // Note that entries of SatisfactionCache are deleted in Sema's destructor.
 351   SatisfactionCache.InsertNode(Satisfaction.release());
 352   return false;
 353 }
 354
 355 bool Sema::CheckConstraintSatisfaction(const Expr *ConstraintExpr,
 356                                        ConstraintSatisfaction &Satisfaction) {
 357   return calculateConstraintSatisfaction(
 358       *this, ConstraintExpr, Satisfaction,
 359       [this](const Expr *AtomicExpr) -> ExprResult {
 360         // We only do this to immitate lvalue-to-rvalue conversion.
 361         return PerformContextuallyConvertToBool(const_cast<Expr *>(AtomicExpr));
 362       });
 363 }
 364
 365 bool Sema::CheckFunctionConstraints(const FunctionDecl *FD,
 366                                     ConstraintSatisfaction &Satisfaction,
 367                                     SourceLocation UsageLoc) {
 368   const Expr *RC = FD->getTrailingRequiresClause();
 369   if (RC->isInstantiationDependent()) {
 370     Satisfaction.IsSatisfied = true;
 371     return false;
 372   }
 373   Qualifiers ThisQuals;
 374   CXXRecordDecl *Record = nullptr;
 375   if (auto *Method = dyn_cast<CXXMethodDecl>(FD)) {
 376     ThisQuals = Method->getMethodQualifiers();
 377     Record = const_cast<CXXRecordDecl *>(Method->getParent());
 378   }
 379   CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
 380   // We substitute with empty arguments in order to rebuild the atomic
 381   // constraint in a constant-evaluated context.
 382   // FIXME: Should this be a dedicated TreeTransform?
 383   return CheckConstraintSatisfaction(
 384       FD, {RC}, /*TemplateArgs=*/{},
 385       SourceRange(UsageLoc.isValid() ? UsageLoc : FD->getLocation()),
 386       Satisfaction);
 387 }
 388
 389 bool Sema::EnsureTemplateArgumentListConstraints(
 390     TemplateDecl *TD, const MultiLevelTemplateArgumentList &TemplateArgsLists,
 391     SourceRange TemplateIDRange) {
 392   ConstraintSatisfaction Satisfaction;
 393   llvm::SmallVector<const Expr *, 3> AssociatedConstraints;
 394   TD->getAssociatedConstraints(AssociatedConstraints);
 395   if (CheckConstraintSatisfaction(TD, AssociatedConstraints, TemplateArgsLists,
 396                                   TemplateIDRange, Satisfaction))
 397     return true;
 398
 399   if (!Satisfaction.IsSatisfied) {
 400     SmallString<128> TemplateArgString;
 401     TemplateArgString = " ";
 402     TemplateArgString += getTemplateArgumentBindingsText(
 403         TD->getTemplateParameters(), TemplateArgsLists.getInnermost().data(),
 404         TemplateArgsLists.getInnermost().size());
 405
 406     Diag(TemplateIDRange.getBegin(),
 407          diag::err_template_arg_list_constraints_not_satisfied)
 408         << (int)getTemplateNameKindForDiagnostics(TemplateName(TD)) << TD
 409         << TemplateArgString << TemplateIDRange;
 410     DiagnoseUnsatisfiedConstraint(Satisfaction);
 411     return true;
 412   }
 413   return false;
 414 }
 415
 416 bool Sema::CheckInstantiatedFunctionTemplateConstraints(
 417     SourceLocation PointOfInstantiation, FunctionDecl *Decl,
 418     ArrayRef<TemplateArgument> TemplateArgs,
 419     ConstraintSatisfaction &Satisfaction) {
 420   // In most cases we're not going to have constraints, so check for that first.
 421   FunctionTemplateDecl *Template = Decl->getPrimaryTemplate();
 422   // Note - code synthesis context for the constraints check is created
 423   // inside CheckConstraintsSatisfaction.
 424   SmallVector<const Expr *, 3> TemplateAC;
 425   Template->getAssociatedConstraints(TemplateAC);
 426   if (TemplateAC.empty()) {
 427     Satisfaction.IsSatisfied = true;
 428     return false;
 429   }
 430
 431   // Enter the scope of this instantiation. We don't use
 432   // PushDeclContext because we don't have a scope.
 433   Sema::ContextRAII savedContext(*this, Decl);
 434   LocalInstantiationScope Scope(*this);
 435   MultiLevelTemplateArgumentList MLTAL;
 436   // FIXME: This will be replaced with some logic to get all the template
 437   // arguments when we switch to deferred template instantiation.
 438   MLTAL.addOuterTemplateArguments(TemplateArgs);
 439
 440   // If this is not an explicit specialization - we need to get the instantiated
 441   // version of the template arguments and add them to scope for the
 442   // substitution.
 443   if (Decl->isTemplateInstantiation()) {
 444     InstantiatingTemplate Inst(*this, Decl->getPointOfInstantiation(),
 445         InstantiatingTemplate::ConstraintsCheck{}, Decl->getPrimaryTemplate(),
 446         TemplateArgs, SourceRange());
 447     if (Inst.isInvalid())
 448       return true;
 449     MultiLevelTemplateArgumentList MLTAL(
 450         *Decl->getTemplateSpecializationArgs());
 451     if (addInstantiatedParametersToScope(
 452             Decl, Decl->getPrimaryTemplate()->getTemplatedDecl(), Scope, MLTAL))
 453       return true;
 454   }
 455   Qualifiers ThisQuals;
 456   CXXRecordDecl *Record = nullptr;
 457   if (auto *Method = dyn_cast<CXXMethodDecl>(Decl)) {
 458     ThisQuals = Method->getMethodQualifiers();
 459     Record = Method->getParent();
 460   }
 461   CXXThisScopeRAII ThisScope(*this, Record, ThisQuals, Record != nullptr);
 462   return CheckConstraintSatisfaction(Template, TemplateAC, MLTAL,
 463                                      PointOfInstantiation, Satisfaction);
 464 }
 465
 466 static void diagnoseUnsatisfiedRequirement(Sema &S,
 467                                            concepts::ExprRequirement *Req,
 468                                            bool First) {
 469   assert(!Req->isSatisfied()
 470          && "Diagnose() can only be used on an unsatisfied requirement");
 471   switch (Req->getSatisfactionStatus()) {
 472     case concepts::ExprRequirement::SS_Dependent:
 473       llvm_unreachable("Diagnosing a dependent requirement");
 474       break;
 475     case concepts::ExprRequirement::SS_ExprSubstitutionFailure: {
 476       auto *SubstDiag = Req->getExprSubstitutionDiagnostic();
 477       if (!SubstDiag->DiagMessage.empty())
 478         S.Diag(SubstDiag->DiagLoc,
 479                diag::note_expr_requirement_expr_substitution_error)
 480                << (int)First << SubstDiag->SubstitutedEntity
 481                << SubstDiag->DiagMessage;
 482       else
 483         S.Diag(SubstDiag->DiagLoc,
 484                diag::note_expr_requirement_expr_unknown_substitution_error)
 485             << (int)First << SubstDiag->SubstitutedEntity;
 486       break;
 487     }
 488     case concepts::ExprRequirement::SS_NoexceptNotMet:
 489       S.Diag(Req->getNoexceptLoc(),
 490              diag::note_expr_requirement_noexcept_not_met)
 491           << (int)First << Req->getExpr();
 492       break;
 493     case concepts::ExprRequirement::SS_TypeRequirementSubstitutionFailure: {
 494       auto *SubstDiag =
 495           Req->getReturnTypeRequirement().getSubstitutionDiagnostic();
 496       if (!SubstDiag->DiagMessage.empty())
 497         S.Diag(SubstDiag->DiagLoc,
 498                diag::note_expr_requirement_type_requirement_substitution_error)
 499             << (int)First << SubstDiag->SubstitutedEntity
 500             << SubstDiag->DiagMessage;
 501       else
 502         S.Diag(SubstDiag->DiagLoc,
 503                diag::note_expr_requirement_type_requirement_unknown_substitution_error)
 504             << (int)First << SubstDiag->SubstitutedEntity;
 505       break;
 506     }
 507     case concepts::ExprRequirement::SS_ConstraintsNotSatisfied: {
 508       ConceptSpecializationExpr *ConstraintExpr =
 509           Req->getReturnTypeRequirementSubstitutedConstraintExpr();
 510       if (ConstraintExpr->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
 511         // A simple case - expr type is the type being constrained and the concept
 512         // was not provided arguments.
 513         Expr *e = Req->getExpr();
 514         S.Diag(e->getBeginLoc(),
 515                diag::note_expr_requirement_constraints_not_satisfied_simple)
 516             << (int)First << S.Context.getReferenceQualifiedType(e)
 517             << ConstraintExpr->getNamedConcept();
 518       } else {
 519         S.Diag(ConstraintExpr->getBeginLoc(),
 520                diag::note_expr_requirement_constraints_not_satisfied)
 521             << (int)First << ConstraintExpr;
 522       }
 523       S.DiagnoseUnsatisfiedConstraint(ConstraintExpr->getSatisfaction());
 524       break;
 525     }
 526     case concepts::ExprRequirement::SS_Satisfied:
 527       llvm_unreachable("We checked this above");
 528   }
 529 }
 530
 531 static void diagnoseUnsatisfiedRequirement(Sema &S,
 532                                            concepts::TypeRequirement *Req,
 533                                            bool First) {
 534   assert(!Req->isSatisfied()
 535          && "Diagnose() can only be used on an unsatisfied requirement");
 536   switch (Req->getSatisfactionStatus()) {
 537   case concepts::TypeRequirement::SS_Dependent:
 538     llvm_unreachable("Diagnosing a dependent requirement");
 539     return;
 540   case concepts::TypeRequirement::SS_SubstitutionFailure: {
 541     auto *SubstDiag = Req->getSubstitutionDiagnostic();
 542     if (!SubstDiag->DiagMessage.empty())
 543       S.Diag(SubstDiag->DiagLoc,
 544              diag::note_type_requirement_substitution_error) << (int)First
 545           << SubstDiag->SubstitutedEntity << SubstDiag->DiagMessage;
 546     else
 547       S.Diag(SubstDiag->DiagLoc,
 548              diag::note_type_requirement_unknown_substitution_error)
 549           << (int)First << SubstDiag->SubstitutedEntity;
 550     return;
 551   }
 552   default:
 553     llvm_unreachable("Unknown satisfaction status");
 554     return;
 555   }
 556 }
 557
 558 static void diagnoseUnsatisfiedRequirement(Sema &S,
 559                                            concepts::NestedRequirement *Req,
 560                                            bool First) {
 561   if (Req->isSubstitutionFailure()) {
 562     concepts::Requirement::SubstitutionDiagnostic *SubstDiag =
 563         Req->getSubstitutionDiagnostic();
 564     if (!SubstDiag->DiagMessage.empty())
 565       S.Diag(SubstDiag->DiagLoc,
 566              diag::note_nested_requirement_substitution_error)
 567              << (int)First << SubstDiag->SubstitutedEntity
 568              << SubstDiag->DiagMessage;
 569     else
 570       S.Diag(SubstDiag->DiagLoc,
 571              diag::note_nested_requirement_unknown_substitution_error)
 572           << (int)First << SubstDiag->SubstitutedEntity;
 573     return;
 574   }
 575   S.DiagnoseUnsatisfiedConstraint(Req->getConstraintSatisfaction(), First);
 576 }
 577
 578
 579 static void diagnoseWellFormedUnsatisfiedConstraintExpr(Sema &S,
 580                                                         Expr *SubstExpr,
 581                                                         bool First = true) {
 582   SubstExpr = SubstExpr->IgnoreParenImpCasts();
 583   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(SubstExpr)) {
 584     switch (BO->getOpcode()) {
 585     // These two cases will in practice only be reached when using fold
 586     // expressions with || and &&, since otherwise the || and && will have been
 587     // broken down into atomic constraints during satisfaction checking.
 588     case BO_LOr:
 589       // Or evaluated to false - meaning both RHS and LHS evaluated to false.
 590       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
 591       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
 592                                                   /*First=*/false);
 593       return;
 594     case BO_LAnd: {
 595       bool LHSSatisfied =
 596           BO->getLHS()->EvaluateKnownConstInt(S.Context).getBoolValue();
 597       if (LHSSatisfied) {
 598         // LHS is true, so RHS must be false.
 599         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(), First);
 600         return;
 601       }
 602       // LHS is false
 603       diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getLHS(), First);
 604
 605       // RHS might also be false
 606       bool RHSSatisfied =
 607           BO->getRHS()->EvaluateKnownConstInt(S.Context).getBoolValue();
 608       if (!RHSSatisfied)
 609         diagnoseWellFormedUnsatisfiedConstraintExpr(S, BO->getRHS(),
 610                                                     /*First=*/false);
 611       return;
 612     }
 613     case BO_GE:
 614     case BO_LE:
 615     case BO_GT:
 616     case BO_LT:
 617     case BO_EQ:
 618     case BO_NE:
 619       if (BO->getLHS()->getType()->isIntegerType() &&
 620           BO->getRHS()->getType()->isIntegerType()) {
 621         Expr::EvalResult SimplifiedLHS;
 622         Expr::EvalResult SimplifiedRHS;
 623         BO->getLHS()->EvaluateAsInt(SimplifiedLHS, S.Context,
 624                                     Expr::SE_NoSideEffects,
 625                                     /*InConstantContext=*/true);
 626         BO->getRHS()->EvaluateAsInt(SimplifiedRHS, S.Context,
 627                                     Expr::SE_NoSideEffects,
 628                                     /*InConstantContext=*/true);
 629         if (!SimplifiedLHS.Diag && ! SimplifiedRHS.Diag) {
 630           S.Diag(SubstExpr->getBeginLoc(),
 631                  diag::note_atomic_constraint_evaluated_to_false_elaborated)
 632               << (int)First << SubstExpr
 633               << toString(SimplifiedLHS.Val.getInt(), 10)
 634               << BinaryOperator::getOpcodeStr(BO->getOpcode())
 635               << toString(SimplifiedRHS.Val.getInt(), 10);
 636           return;
 637         }
 638       }
 639       break;
 640
 641     default:
 642       break;
 643     }
 644   } else if (auto *CSE = dyn_cast<ConceptSpecializationExpr>(SubstExpr)) {
 645     if (CSE->getTemplateArgsAsWritten()->NumTemplateArgs == 1) {
 646       S.Diag(
 647           CSE->getSourceRange().getBegin(),
 648           diag::
 649           note_single_arg_concept_specialization_constraint_evaluated_to_false)
 650           << (int)First
 651           << CSE->getTemplateArgsAsWritten()->arguments()[0].getArgument()
 652           << CSE->getNamedConcept();
 653     } else {
 654       S.Diag(SubstExpr->getSourceRange().getBegin(),
 655              diag::note_concept_specialization_constraint_evaluated_to_false)
 656           << (int)First << CSE;
 657     }
 658     S.DiagnoseUnsatisfiedConstraint(CSE->getSatisfaction());
 659     return;
 660   } else if (auto *RE = dyn_cast<RequiresExpr>(SubstExpr)) {
 661     for (concepts::Requirement *Req : RE->getRequirements())
 662       if (!Req->isDependent() && !Req->isSatisfied()) {
 663         if (auto *E = dyn_cast<concepts::ExprRequirement>(Req))
 664           diagnoseUnsatisfiedRequirement(S, E, First);
 665         else if (auto *T = dyn_cast<concepts::TypeRequirement>(Req))
 666           diagnoseUnsatisfiedRequirement(S, T, First);
 667         else
 668           diagnoseUnsatisfiedRequirement(
 669               S, cast<concepts::NestedRequirement>(Req), First);
 670         break;
 671       }
 672     return;
 673   }
 674
 675   S.Diag(SubstExpr->getSourceRange().getBegin(),
 676          diag::note_atomic_constraint_evaluated_to_false)
 677       << (int)First << SubstExpr;
 678 }
 679
 680 template<typename SubstitutionDiagnostic>
 681 static void diagnoseUnsatisfiedConstraintExpr(
 682     Sema &S, const Expr *E,
 683     const llvm::PointerUnion<Expr *, SubstitutionDiagnostic *> &Record,
 684     bool First = true) {
 685   if (auto *Diag = Record.template dyn_cast<SubstitutionDiagnostic *>()){
 686     S.Diag(Diag->first, diag::note_substituted_constraint_expr_is_ill_formed)
 687         << Diag->second;
 688     return;
 689   }
 690
 691   diagnoseWellFormedUnsatisfiedConstraintExpr(S,
 692       Record.template get<Expr *>(), First);
 693 }
 694
 695 void
 696 Sema::DiagnoseUnsatisfiedConstraint(const ConstraintSatisfaction& Satisfaction,
 697                                     bool First) {
 698   assert(!Satisfaction.IsSatisfied &&
 699          "Attempted to diagnose a satisfied constraint");
 700   for (auto &Pair : Satisfaction.Details) {
 701     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
 702     First = false;
 703   }
 704 }
 705
 706 void Sema::DiagnoseUnsatisfiedConstraint(
 707     const ASTConstraintSatisfaction &Satisfaction,
 708     bool First) {
 709   assert(!Satisfaction.IsSatisfied &&
 710          "Attempted to diagnose a satisfied constraint");
 711   for (auto &Pair : Satisfaction) {
 712     diagnoseUnsatisfiedConstraintExpr(*this, Pair.first, Pair.second, First);
 713     First = false;
 714   }
 715 }
 716
 717 const NormalizedConstraint *
 718 Sema::getNormalizedAssociatedConstraints(
 719     NamedDecl *ConstrainedDecl, ArrayRef<const Expr *> AssociatedConstraints) {
 720   auto CacheEntry = NormalizationCache.find(ConstrainedDecl);
 721   if (CacheEntry == NormalizationCache.end()) {
 722     auto Normalized =
 723         NormalizedConstraint::fromConstraintExprs(*this, ConstrainedDecl,
 724                                                   AssociatedConstraints);
 725     CacheEntry =
 726         NormalizationCache
 727             .try_emplace(ConstrainedDecl,
 728                          Normalized
 729                              ? new (Context) NormalizedConstraint(
 730                                  std::move(*Normalized))
 731                              : nullptr)
 732             .first;
 733   }
 734   return CacheEntry->second;
 735 }
 736
 737 static bool substituteParameterMappings(Sema &S, NormalizedConstraint &N,
 738     ConceptDecl *Concept, ArrayRef<TemplateArgument> TemplateArgs,
 739     const ASTTemplateArgumentListInfo *ArgsAsWritten) {
 740   if (!N.isAtomic()) {
 741     if (substituteParameterMappings(S, N.getLHS(), Concept, TemplateArgs,
 742                                     ArgsAsWritten))
 743       return true;
 744     return substituteParameterMappings(S, N.getRHS(), Concept, TemplateArgs,
 745                                        ArgsAsWritten);
 746   }
 747   TemplateParameterList *TemplateParams = Concept->getTemplateParameters();
 748
 749   AtomicConstraint &Atomic = *N.getAtomicConstraint();
 750   TemplateArgumentListInfo SubstArgs;
 751   MultiLevelTemplateArgumentList MLTAL;
 752   MLTAL.addOuterTemplateArguments(TemplateArgs);
 753   if (!Atomic.ParameterMapping) {
 754     llvm::SmallBitVector OccurringIndices(TemplateParams->size());
 755     S.MarkUsedTemplateParameters(Atomic.ConstraintExpr, /*OnlyDeduced=*/false,
 756                                  /*Depth=*/0, OccurringIndices);
 757     TemplateArgumentLoc *TempArgs =
 758         new (S.Context) TemplateArgumentLoc[OccurringIndices.count()];
 759     for (unsigned I = 0, J = 0, C = TemplateParams->size(); I != C; ++I)
 760       if (OccurringIndices[I])
 761         new (&(TempArgs)[J++])
 762             TemplateArgumentLoc(S.getIdentityTemplateArgumentLoc(
 763                 TemplateParams->begin()[I],
 764                 // Here we assume we do not support things like
 765                 // template<typename A, typename B>
 766                 // concept C = ...;
 767                 //
 768                 // template<typename... Ts> requires C<Ts...>
 769                 // struct S { };
 770                 // The above currently yields a diagnostic.
 771                 // We still might have default arguments for concept parameters.
 772                 ArgsAsWritten->NumTemplateArgs > I
 773                     ? ArgsAsWritten->arguments()[I].getLocation()
 774                     : SourceLocation()));
 775     Atomic.ParameterMapping.emplace(TempArgs,  OccurringIndices.count());
 776   }
 777   Sema::InstantiatingTemplate Inst(
 778       S, ArgsAsWritten->arguments().front().getSourceRange().getBegin(),
 779       Sema::InstantiatingTemplate::ParameterMappingSubstitution{}, Concept,
 780       SourceRange(ArgsAsWritten->arguments()[0].getSourceRange().getBegin(),
 781                   ArgsAsWritten->arguments().back().getSourceRange().getEnd()));
 782   if (S.SubstTemplateArguments(*Atomic.ParameterMapping, MLTAL, SubstArgs))
 783     return true;
 784
 785   TemplateArgumentLoc *TempArgs =
 786       new (S.Context) TemplateArgumentLoc[SubstArgs.size()];
 787   std::copy(SubstArgs.arguments().begin(), SubstArgs.arguments().end(),
 788             TempArgs);
 789   Atomic.ParameterMapping.emplace(TempArgs, SubstArgs.size());
 790   return false;
 791 }
 792
 793 Optional<NormalizedConstraint>
 794 NormalizedConstraint::fromConstraintExprs(Sema &S, NamedDecl *D,
 795                                           ArrayRef<const Expr *> E) {
 796   assert(E.size() != 0);
 797   auto Conjunction = fromConstraintExpr(S, D, E[0]);
 798   if (!Conjunction)
 799     return None;
 800   for (unsigned I = 1; I < E.size(); ++I) {
 801     auto Next = fromConstraintExpr(S, D, E[I]);
 802     if (!Next)
 803       return None;
 804     *Conjunction = NormalizedConstraint(S.Context, std::move(*Conjunction),
 805                                         std::move(*Next), CCK_Conjunction);
 806   }
 807   return Conjunction;
 808 }
 809
 810 llvm::Optional<NormalizedConstraint>
 811 NormalizedConstraint::fromConstraintExpr(Sema &S, NamedDecl *D, const Expr *E) {
 812   assert(E != nullptr);
 813
 814   // C++ [temp.constr.normal]p1.1
 815   // [...]
 816   // - The normal form of an expression (E) is the normal form of E.
 817   // [...]
 818   E = E->IgnoreParenImpCasts();
 819   if (LogicalBinOp BO = E) {
 820     auto LHS = fromConstraintExpr(S, D, BO.getLHS());
 821     if (!LHS)
 822       return None;
 823     auto RHS = fromConstraintExpr(S, D, BO.getRHS());
 824     if (!RHS)
 825       return None;
 826
 827     return NormalizedConstraint(S.Context, std::move(*LHS), std::move(*RHS),
 828                                 BO.isAnd() ? CCK_Conjunction : CCK_Disjunction);
 829   } else if (auto *CSE = dyn_cast<const ConceptSpecializationExpr>(E)) {
 830     const NormalizedConstraint *SubNF;
 831     {
 832       Sema::InstantiatingTemplate Inst(
 833           S, CSE->getExprLoc(),
 834           Sema::InstantiatingTemplate::ConstraintNormalization{}, D,
 835           CSE->getSourceRange());
 836       // C++ [temp.constr.normal]p1.1
 837       // [...]
 838       // The normal form of an id-expression of the form C<A1, A2, ..., AN>,
 839       // where C names a concept, is the normal form of the
 840       // constraint-expression of C, after substituting A1, A2, ..., AN for C’s
 841       // respective template parameters in the parameter mappings in each atomic
 842       // constraint. If any such substitution results in an invalid type or
 843       // expression, the program is ill-formed; no diagnostic is required.
 844       // [...]
 845       ConceptDecl *CD = CSE->getNamedConcept();
 846       SubNF = S.getNormalizedAssociatedConstraints(CD,
 847                                                    {CD->getConstraintExpr()});
 848       if (!SubNF)
 849         return None;
 850     }
 851
 852     Optional<NormalizedConstraint> New;
 853     New.emplace(S.Context, *SubNF);
 854
 855     if (substituteParameterMappings(
 856             S, *New, CSE->getNamedConcept(),
 857             CSE->getTemplateArguments(), CSE->getTemplateArgsAsWritten()))
 858       return None;
 859
 860     return New;
 861   }
 862   return NormalizedConstraint{new (S.Context) AtomicConstraint(S, E)};
 863 }
 864
 865 using NormalForm =
 866     llvm::SmallVector<llvm::SmallVector<AtomicConstraint *, 2>, 4>;
 867
 868 static NormalForm makeCNF(const NormalizedConstraint &Normalized) {
 869   if (Normalized.isAtomic())
 870     return {{Normalized.getAtomicConstraint()}};
 871
 872   NormalForm LCNF = makeCNF(Normalized.getLHS());
 873   NormalForm RCNF = makeCNF(Normalized.getRHS());
 874   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Conjunction) {
 875     LCNF.reserve(LCNF.size() + RCNF.size());
 876     while (!RCNF.empty())
 877       LCNF.push_back(RCNF.pop_back_val());
 878     return LCNF;
 879   }
 880
 881   // Disjunction
 882   NormalForm Res;
 883   Res.reserve(LCNF.size() * RCNF.size());
 884   for (auto &LDisjunction : LCNF)
 885     for (auto &RDisjunction : RCNF) {
 886       NormalForm::value_type Combined;
 887       Combined.reserve(LDisjunction.size() + RDisjunction.size());
 888       std::copy(LDisjunction.begin(), LDisjunction.end(),
 889                 std::back_inserter(Combined));
 890       std::copy(RDisjunction.begin(), RDisjunction.end(),
 891                 std::back_inserter(Combined));
 892       Res.emplace_back(Combined);
 893     }
 894   return Res;
 895 }
 896
 897 static NormalForm makeDNF(const NormalizedConstraint &Normalized) {
 898   if (Normalized.isAtomic())
 899     return {{Normalized.getAtomicConstraint()}};
 900
 901   NormalForm LDNF = makeDNF(Normalized.getLHS());
 902   NormalForm RDNF = makeDNF(Normalized.getRHS());
 903   if (Normalized.getCompoundKind() == NormalizedConstraint::CCK_Disjunction) {
 904     LDNF.reserve(LDNF.size() + RDNF.size());
 905     while (!RDNF.empty())
 906       LDNF.push_back(RDNF.pop_back_val());
 907     return LDNF;
 908   }
 909
 910   // Conjunction
 911   NormalForm Res;
 912   Res.reserve(LDNF.size() * RDNF.size());
 913   for (auto &LConjunction : LDNF) {
 914     for (auto &RConjunction : RDNF) {
 915       NormalForm::value_type Combined;
 916       Combined.reserve(LConjunction.size() + RConjunction.size());
 917       std::copy(LConjunction.begin(), LConjunction.end(),
 918                 std::back_inserter(Combined));
 919       std::copy(RConjunction.begin(), RConjunction.end(),
 920                 std::back_inserter(Combined));
 921       Res.emplace_back(Combined);
 922     }
 923   }
 924   return Res;
 925 }
 926
 927 template<typename AtomicSubsumptionEvaluator>
 928 static bool subsumes(NormalForm PDNF, NormalForm QCNF,
 929                      AtomicSubsumptionEvaluator E) {
 930   // C++ [temp.constr.order] p2
 931   //   Then, P subsumes Q if and only if, for every disjunctive clause Pi in the
 932   //   disjunctive normal form of P, Pi subsumes every conjunctive clause Qj in
 933   //   the conjuctive normal form of Q, where [...]
 934   for (const auto &Pi : PDNF) {
 935     for (const auto &Qj : QCNF) {
 936       // C++ [temp.constr.order] p2
 937       //   - [...] a disjunctive clause Pi subsumes a conjunctive clause Qj if
 938       //     and only if there exists an atomic constraint Pia in Pi for which
 939       //     there exists an atomic constraint, Qjb, in Qj such that Pia
 940       //     subsumes Qjb.
 941       bool Found = false;
 942       for (const AtomicConstraint *Pia : Pi) {
 943         for (const AtomicConstraint *Qjb : Qj) {
 944           if (E(*Pia, *Qjb)) {
 945             Found = true;
 946             break;
 947           }
 948         }
 949         if (Found)
 950           break;
 951       }
 952       if (!Found)
 953         return false;
 954     }
 955   }
 956   return true;
 957 }
 958
 959 template<typename AtomicSubsumptionEvaluator>
 960 static bool subsumes(Sema &S, NamedDecl *DP, ArrayRef<const Expr *> P,
 961                      NamedDecl *DQ, ArrayRef<const Expr *> Q, bool &Subsumes,
 962                      AtomicSubsumptionEvaluator E) {
 963   // C++ [temp.constr.order] p2
 964   //   In order to determine if a constraint P subsumes a constraint Q, P is
 965   //   transformed into disjunctive normal form, and Q is transformed into
 966   //   conjunctive normal form. [...]
 967   auto *PNormalized = S.getNormalizedAssociatedConstraints(DP, P);
 968   if (!PNormalized)
 969     return true;
 970   const NormalForm PDNF = makeDNF(*PNormalized);
 971
 972   auto *QNormalized = S.getNormalizedAssociatedConstraints(DQ, Q);
 973   if (!QNormalized)
 974     return true;
 975   const NormalForm QCNF = makeCNF(*QNormalized);
 976
 977   Subsumes = subsumes(PDNF, QCNF, E);
 978   return false;
 979 }
 980
 981 bool Sema::IsAtLeastAsConstrained(NamedDecl *D1, ArrayRef<const Expr *> AC1,
 982                                   NamedDecl *D2, ArrayRef<const Expr *> AC2,
 983                                   bool &Result) {
 984   if (AC1.empty()) {
 985     Result = AC2.empty();
 986     return false;
 987   }
 988   if (AC2.empty()) {
 989     // TD1 has associated constraints and TD2 does not.
 990     Result = true;
 991     return false;
 992   }
 993
 994   std::pair<NamedDecl *, NamedDecl *> Key{D1, D2};
 995   auto CacheEntry = SubsumptionCache.find(Key);
 996   if (CacheEntry != SubsumptionCache.end()) {
 997     Result = CacheEntry->second;
 998     return false;
 999   }
1000
1001   if (subsumes(*this, D1, AC1, D2, AC2, Result,
1002         [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1003           return A.subsumes(Context, B);
1004         }))
1005     return true;
1006   SubsumptionCache.try_emplace(Key, Result);
1007   return false;
1008 }
1009
1010 bool Sema::MaybeEmitAmbiguousAtomicConstraintsDiagnostic(NamedDecl *D1,
1011     ArrayRef<const Expr *> AC1, NamedDecl *D2, ArrayRef<const Expr *> AC2) {
1012   if (isSFINAEContext())
1013     // No need to work here because our notes would be discarded.
1014     return false;
1015
1016   if (AC1.empty() || AC2.empty())
1017     return false;
1018
1019   auto NormalExprEvaluator =
1020       [this] (const AtomicConstraint &A, const AtomicConstraint &B) {
1021         return A.subsumes(Context, B);
1022       };
1023
1024   const Expr *AmbiguousAtomic1 = nullptr, *AmbiguousAtomic2 = nullptr;
1025   auto IdenticalExprEvaluator =
1026       [&] (const AtomicConstraint &A, const AtomicConstraint &B) {
1027         if (!A.hasMatchingParameterMapping(Context, B))
1028           return false;
1029         const Expr *EA = A.ConstraintExpr, *EB = B.ConstraintExpr;
1030         if (EA == EB)
1031           return true;
1032
1033         // Not the same source level expression - are the expressions
1034         // identical?
1035         llvm::FoldingSetNodeID IDA, IDB;
1036         EA->Profile(IDA, Context, /*Canonical=*/true);
1037         EB->Profile(IDB, Context, /*Canonical=*/true);
1038         if (IDA != IDB)
1039           return false;
1040
1041         AmbiguousAtomic1 = EA;
1042         AmbiguousAtomic2 = EB;
1043         return true;
1044       };
1045
1046   {
1047     // The subsumption checks might cause diagnostics
1048     SFINAETrap Trap(*this);
1049     auto *Normalized1 = getNormalizedAssociatedConstraints(D1, AC1);
1050     if (!Normalized1)
1051       return false;
1052     const NormalForm DNF1 = makeDNF(*Normalized1);
1053     const NormalForm CNF1 = makeCNF(*Normalized1);
1054
1055     auto *Normalized2 = getNormalizedAssociatedConstraints(D2, AC2);
1056     if (!Normalized2)
1057       return false;
1058     const NormalForm DNF2 = makeDNF(*Normalized2);
1059     const NormalForm CNF2 = makeCNF(*Normalized2);
1060
1061     bool Is1AtLeastAs2Normally = subsumes(DNF1, CNF2, NormalExprEvaluator);
1062     bool Is2AtLeastAs1Normally = subsumes(DNF2, CNF1, NormalExprEvaluator);
1063     bool Is1AtLeastAs2 = subsumes(DNF1, CNF2, IdenticalExprEvaluator);
1064     bool Is2AtLeastAs1 = subsumes(DNF2, CNF1, IdenticalExprEvaluator);
1065     if (Is1AtLeastAs2 == Is1AtLeastAs2Normally &&
1066         Is2AtLeastAs1 == Is2AtLeastAs1Normally)
1067       // Same result - no ambiguity was caused by identical atomic expressions.
1068       return false;
1069   }
1070
1071   // A different result! Some ambiguous atomic constraint(s) caused a difference
1072   assert(AmbiguousAtomic1 && AmbiguousAtomic2);
1073
1074   Diag(AmbiguousAtomic1->getBeginLoc(), diag::note_ambiguous_atomic_constraints)
1075       << AmbiguousAtomic1->getSourceRange();
1076   Diag(AmbiguousAtomic2->getBeginLoc(),
1077        diag::note_ambiguous_atomic_constraints_similar_expression)
1078       << AmbiguousAtomic2->getSourceRange();
1079   return true;
1080 }
1081
1082 concepts::ExprRequirement::ExprRequirement(
1083     Expr *E, bool IsSimple, SourceLocation NoexceptLoc,
1084     ReturnTypeRequirement Req, SatisfactionStatus Status,
1085     ConceptSpecializationExpr *SubstitutedConstraintExpr) :
1086     Requirement(IsSimple ? RK_Simple : RK_Compound, Status == SS_Dependent,
1087                 Status == SS_Dependent &&
1088                 (E->containsUnexpandedParameterPack() ||
1089                  Req.containsUnexpandedParameterPack()),
1090                 Status == SS_Satisfied), Value(E), NoexceptLoc(NoexceptLoc),
1091     TypeReq(Req), SubstitutedConstraintExpr(SubstitutedConstraintExpr),
1092     Status(Status) {
1093   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1094          "Simple requirement must not have a return type requirement or a "
1095          "noexcept specification");
1096   assert((Status > SS_TypeRequirementSubstitutionFailure && Req.isTypeConstraint()) ==
1097          (SubstitutedConstraintExpr != nullptr));
1098 }
1099
1100 concepts::ExprRequirement::ExprRequirement(
1101     SubstitutionDiagnostic *ExprSubstDiag, bool IsSimple,
1102     SourceLocation NoexceptLoc, ReturnTypeRequirement Req) :
1103     Requirement(IsSimple ? RK_Simple : RK_Compound, Req.isDependent(),
1104                 Req.containsUnexpandedParameterPack(), /*IsSatisfied=*/false),
1105     Value(ExprSubstDiag), NoexceptLoc(NoexceptLoc), TypeReq(Req),
1106     Status(SS_ExprSubstitutionFailure) {
1107   assert((!IsSimple || (Req.isEmpty() && NoexceptLoc.isInvalid())) &&
1108          "Simple requirement must not have a return type requirement or a "
1109          "noexcept specification");
1110 }
1111
1112 concepts::ExprRequirement::ReturnTypeRequirement::
1113 ReturnTypeRequirement(TemplateParameterList *TPL) :
1114     TypeConstraintInfo(TPL, false) {
1115   assert(TPL->size() == 1);
1116   const TypeConstraint *TC =
1117       cast<TemplateTypeParmDecl>(TPL->getParam(0))->getTypeConstraint();
1118   assert(TC &&
1119          "TPL must have a template type parameter with a type constraint");
1120   auto *Constraint =
1121       cast<ConceptSpecializationExpr>(TC->getImmediatelyDeclaredConstraint());
1122   bool Dependent =
1123       Constraint->getTemplateArgsAsWritten() &&
1124       TemplateSpecializationType::anyInstantiationDependentTemplateArguments(
1125           Constraint->getTemplateArgsAsWritten()->arguments().drop_front(1));
1126   TypeConstraintInfo.setInt(Dependent ? true : false);
1127 }
1128
1129 concepts::TypeRequirement::TypeRequirement(TypeSourceInfo *T) :
1130     Requirement(RK_Type, T->getType()->isInstantiationDependentType(),
1131                 T->getType()->containsUnexpandedParameterPack(),
1132                 // We reach this ctor with either dependent types (in which
1133                 // IsSatisfied doesn't matter) or with non-dependent type in
1134                 // which the existence of the type indicates satisfaction.
1135                 /*IsSatisfied=*/true),
1136     Value(T),
1137     Status(T->getType()->isInstantiationDependentType() ? SS_Dependent
1138                                                         : SS_Satisfied) {}