[Concepts] Requires Expressions

Implement support for C++2a requires-expressions.

Re-commit after compilation failure on some platforms due to alignment issues with PointerIntPair.

Differential Revision: https://reviews.llvm.org/D50360
diff --git a/clang/lib/Serialization/ASTCommon.cpp b/clang/lib/Serialization/ASTCommon.cpp
index cdb5b17..f93f1f7 100644
--- a/clang/lib/Serialization/ASTCommon.cpp
+++ b/clang/lib/Serialization/ASTCommon.cpp
@@ -402,6 +402,7 @@
   case Decl::Binding:
   case Decl::Concept:
   case Decl::LifetimeExtendedTemporary:
+  case Decl::RequiresExprBody:
     return false;
 
   // These indirectly derive from Redeclarable<T> but are not actually
diff --git a/clang/lib/Serialization/ASTReaderDecl.cpp b/clang/lib/Serialization/ASTReaderDecl.cpp
index 96a7d5a..4fd079e 100644
--- a/clang/lib/Serialization/ASTReaderDecl.cpp
+++ b/clang/lib/Serialization/ASTReaderDecl.cpp
@@ -375,6 +375,7 @@
     void VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
     DeclID VisitTemplateDecl(TemplateDecl *D);
     void VisitConceptDecl(ConceptDecl *D);
+    void VisitRequiresExprBodyDecl(RequiresExprBodyDecl *D);
     RedeclarableResult VisitRedeclarableTemplateDecl(RedeclarableTemplateDecl *D);
     void VisitClassTemplateDecl(ClassTemplateDecl *D);
     void VisitBuiltinTemplateDecl(BuiltinTemplateDecl *D);
@@ -2037,6 +2038,9 @@
   mergeMergeable(D);
 }
 
+void ASTDeclReader::VisitRequiresExprBodyDecl(RequiresExprBodyDecl *D) {
+}
+
 ASTDeclReader::RedeclarableResult
 ASTDeclReader::VisitRedeclarableTemplateDecl(RedeclarableTemplateDecl *D) {
   RedeclarableResult Redecl = VisitRedeclarable(D);
@@ -3839,6 +3843,9 @@
   case DECL_CONCEPT:
     D = ConceptDecl::CreateDeserialized(Context, ID);
     break;
+  case DECL_REQUIRES_EXPR_BODY:
+    D = RequiresExprBodyDecl::CreateDeserialized(Context, ID);
+    break;
   case DECL_STATIC_ASSERT:
     D = StaticAssertDecl::CreateDeserialized(Context, ID);
     break;
diff --git a/clang/lib/Serialization/ASTReaderStmt.cpp b/clang/lib/Serialization/ASTReaderStmt.cpp
index f558c26..5dd0ef9 100644
--- a/clang/lib/Serialization/ASTReaderStmt.cpp
+++ b/clang/lib/Serialization/ASTReaderStmt.cpp
@@ -724,6 +724,28 @@
   E->setRParenLoc(readSourceLocation());
 }
 
+static ConstraintSatisfaction
+readConstraintSatisfaction(ASTRecordReader &Record) {
+  ConstraintSatisfaction Satisfaction;
+  Satisfaction.IsSatisfied = Record.readInt();
+  if (!Satisfaction.IsSatisfied) {
+    unsigned NumDetailRecords = Record.readInt();
+    for (unsigned i = 0; i != NumDetailRecords; ++i) {
+      Expr *ConstraintExpr = Record.readExpr();
+      if (bool IsDiagnostic = Record.readInt()) {
+        SourceLocation DiagLocation = Record.readSourceLocation();
+        std::string DiagMessage = Record.readString();
+        Satisfaction.Details.emplace_back(
+            ConstraintExpr, new (Record.getContext())
+                                ConstraintSatisfaction::SubstitutionDiagnostic{
+                                    DiagLocation, DiagMessage});
+      } else
+        Satisfaction.Details.emplace_back(ConstraintExpr, Record.readExpr());
+    }
+  }
+  return Satisfaction;
+}
+
 void ASTStmtReader::VisitConceptSpecializationExpr(
         ConceptSpecializationExpr *E) {
   VisitExpr(E);
@@ -737,26 +759,121 @@
   for (unsigned I = 0; I < NumTemplateArgs; ++I)
     Args.push_back(Record.readTemplateArgument());
   E->setTemplateArguments(Args);
-  ConstraintSatisfaction Satisfaction;
-  Satisfaction.IsSatisfied = Record.readInt();
-  if (!Satisfaction.IsSatisfied) {
-    unsigned NumDetailRecords = Record.readInt();
-    for (unsigned i = 0; i != NumDetailRecords; ++i) {
-      Expr *ConstraintExpr = Record.readExpr();
-      bool IsDiagnostic = Record.readInt();
-      if (IsDiagnostic) {
-        SourceLocation DiagLocation = Record.readSourceLocation();
-        std::string DiagMessage = Record.readString();
-        Satisfaction.Details.emplace_back(
-            ConstraintExpr, new (Record.getContext())
-                                ConstraintSatisfaction::SubstitutionDiagnostic{
-                                    DiagLocation, DiagMessage});
-      } else
-        Satisfaction.Details.emplace_back(ConstraintExpr, Record.readExpr());
+  E->Satisfaction = E->isValueDependent() ? nullptr :
+      ASTConstraintSatisfaction::Create(Record.getContext(),
+                                        readConstraintSatisfaction(Record));
+}
+
+static concepts::Requirement::SubstitutionDiagnostic *
+readSubstitutionDiagnostic(ASTRecordReader &Record) {
+  std::string SubstitutedEntity = Record.readString();
+  SourceLocation DiagLoc = Record.readSourceLocation();
+  std::string DiagMessage = Record.readString();
+  return new (Record.getContext())
+      concepts::Requirement::SubstitutionDiagnostic{SubstitutedEntity, DiagLoc,
+                                                    DiagMessage};
+}
+
+void ASTStmtReader::VisitRequiresExpr(RequiresExpr *E) {
+  VisitExpr(E);
+  unsigned NumLocalParameters = Record.readInt();
+  unsigned NumRequirements = Record.readInt();
+  E->RequiresExprBits.RequiresKWLoc = Record.readSourceLocation();
+  E->RequiresExprBits.IsSatisfied = Record.readInt();
+  E->Body = Record.readDeclAs<RequiresExprBodyDecl>();
+  llvm::SmallVector<ParmVarDecl *, 4> LocalParameters;
+  for (unsigned i = 0; i < NumLocalParameters; ++i)
+    LocalParameters.push_back(cast<ParmVarDecl>(Record.readDecl()));
+  std::copy(LocalParameters.begin(), LocalParameters.end(),
+            E->getTrailingObjects<ParmVarDecl *>());
+  llvm::SmallVector<concepts::Requirement *, 4> Requirements;
+  for (unsigned i = 0; i < NumRequirements; ++i) {
+    auto RK =
+        static_cast<concepts::Requirement::RequirementKind>(Record.readInt());
+    concepts::Requirement *R = nullptr;
+    switch (RK) {
+      case concepts::Requirement::RK_Type: {
+        auto Status =
+            static_cast<concepts::TypeRequirement::SatisfactionStatus>(
+                Record.readInt());
+        if (Status == concepts::TypeRequirement::SS_SubstitutionFailure)
+          R = new (Record.getContext())
+              concepts::TypeRequirement(readSubstitutionDiagnostic(Record));
+        else
+          R = new (Record.getContext())
+              concepts::TypeRequirement(Record.readTypeSourceInfo());
+      } break;
+      case concepts::Requirement::RK_Simple:
+      case concepts::Requirement::RK_Compound: {
+        auto Status =
+            static_cast<concepts::ExprRequirement::SatisfactionStatus>(
+                Record.readInt());
+        llvm::PointerUnion<concepts::Requirement::SubstitutionDiagnostic *,
+                           Expr *> E;
+        if (Status == concepts::ExprRequirement::SS_ExprSubstitutionFailure) {
+          E = readSubstitutionDiagnostic(Record);
+        } else
+          E = Record.readExpr();
+
+        llvm::Optional<concepts::ExprRequirement::ReturnTypeRequirement> Req;
+        ConceptSpecializationExpr *SubstitutedConstraintExpr = nullptr;
+        SourceLocation NoexceptLoc;
+        if (RK == concepts::Requirement::RK_Simple) {
+          Req.emplace();
+        } else {
+          NoexceptLoc = Record.readSourceLocation();
+          switch (auto returnTypeRequirementKind = Record.readInt()) {
+            case 0:
+              // No return type requirement.
+              Req.emplace();
+              break;
+            case 1: {
+              // type-constraint
+              TemplateParameterList *TPL = Record.readTemplateParameterList();
+              if (Status >=
+                  concepts::ExprRequirement::SS_ConstraintsNotSatisfied)
+                SubstitutedConstraintExpr =
+                    cast<ConceptSpecializationExpr>(Record.readExpr());
+              Req.emplace(TPL);
+            } break;
+            case 2:
+              // Substitution failure
+              Req.emplace(readSubstitutionDiagnostic(Record));
+              break;
+          }
+        }
+        if (Expr *Ex = E.dyn_cast<Expr *>())
+          R = new (Record.getContext()) concepts::ExprRequirement(
+                  Ex, RK == concepts::Requirement::RK_Simple, NoexceptLoc,
+                  std::move(*Req), Status, SubstitutedConstraintExpr);
+        else
+          R = new (Record.getContext()) concepts::ExprRequirement(
+                  E.get<concepts::Requirement::SubstitutionDiagnostic *>(),
+                  RK == concepts::Requirement::RK_Simple, NoexceptLoc,
+                  std::move(*Req));
+      } break;
+      case concepts::Requirement::RK_Nested: {
+        if (bool IsSubstitutionDiagnostic = Record.readInt()) {
+          R = new (Record.getContext()) concepts::NestedRequirement(
+              readSubstitutionDiagnostic(Record));
+          break;
+        }
+        Expr *E = Record.readExpr();
+        if (E->isInstantiationDependent())
+          R = new (Record.getContext()) concepts::NestedRequirement(E);
+        else
+          R = new (Record.getContext())
+              concepts::NestedRequirement(Record.getContext(), E,
+                                          readConstraintSatisfaction(Record));
+      } break;
     }
+    if (!R)
+      continue;
+    Requirements.push_back(R);
   }
-  E->Satisfaction = ASTConstraintSatisfaction::Create(Record.getContext(),
-                                                      Satisfaction);
+  std::copy(Requirements.begin(), Requirements.end(),
+            E->getTrailingObjects<concepts::Requirement *>());
+  E->RBraceLoc = Record.readSourceLocation();
 }
 
 void ASTStmtReader::VisitArraySubscriptExpr(ArraySubscriptExpr *E) {
@@ -3566,11 +3683,18 @@
       S = new (Context) DependentCoawaitExpr(Empty);
       break;
 
-    case EXPR_CONCEPT_SPECIALIZATION:
+    case EXPR_CONCEPT_SPECIALIZATION: {
       unsigned numTemplateArgs = Record[ASTStmtReader::NumExprFields];
       S = ConceptSpecializationExpr::Create(Context, Empty, numTemplateArgs);
       break;
-      
+    }
+
+    case EXPR_REQUIRES:
+      unsigned numLocalParameters = Record[ASTStmtReader::NumExprFields];
+      unsigned numRequirement = Record[ASTStmtReader::NumExprFields + 1];
+      S = RequiresExpr::Create(Context, Empty, numLocalParameters,
+                               numRequirement);
+      break;
     }
 
     // We hit a STMT_STOP, so we're done with this expression.
diff --git a/clang/lib/Serialization/ASTWriter.cpp b/clang/lib/Serialization/ASTWriter.cpp
index 8247f5a..c216b14 100644
--- a/clang/lib/Serialization/ASTWriter.cpp
+++ b/clang/lib/Serialization/ASTWriter.cpp
@@ -885,6 +885,7 @@
   RECORD(DECL_NON_TYPE_TEMPLATE_PARM);
   RECORD(DECL_TEMPLATE_TEMPLATE_PARM);
   RECORD(DECL_CONCEPT);
+  RECORD(DECL_REQUIRES_EXPR_BODY);
   RECORD(DECL_TYPE_ALIAS_TEMPLATE);
   RECORD(DECL_STATIC_ASSERT);
   RECORD(DECL_CXX_BASE_SPECIFIERS);
diff --git a/clang/lib/Serialization/ASTWriterDecl.cpp b/clang/lib/Serialization/ASTWriterDecl.cpp
index b2a8c11..459e617 100644
--- a/clang/lib/Serialization/ASTWriterDecl.cpp
+++ b/clang/lib/Serialization/ASTWriterDecl.cpp
@@ -104,6 +104,7 @@
     void VisitNonTypeTemplateParmDecl(NonTypeTemplateParmDecl *D);
     void VisitTemplateDecl(TemplateDecl *D);
     void VisitConceptDecl(ConceptDecl *D);
+    void VisitRequiresExprBodyDecl(RequiresExprBodyDecl *D);
     void VisitRedeclarableTemplateDecl(RedeclarableTemplateDecl *D);
     void VisitClassTemplateDecl(ClassTemplateDecl *D);
     void VisitVarTemplateDecl(VarTemplateDecl *D);
@@ -1481,6 +1482,10 @@
   Code = serialization::DECL_CONCEPT;
 }
 
+void ASTDeclWriter::VisitRequiresExprBodyDecl(RequiresExprBodyDecl *D) {
+  Code = serialization::DECL_REQUIRES_EXPR_BODY;
+}
+
 void ASTDeclWriter::VisitRedeclarableTemplateDecl(RedeclarableTemplateDecl *D) {
   VisitRedeclarable(D);
 
diff --git a/clang/lib/Serialization/ASTWriterStmt.cpp b/clang/lib/Serialization/ASTWriterStmt.cpp
index 9231f3b..1b118c2 100644
--- a/clang/lib/Serialization/ASTWriterStmt.cpp
+++ b/clang/lib/Serialization/ASTWriterStmt.cpp
@@ -12,6 +12,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "clang/Serialization/ASTRecordWriter.h"
+#include "clang/Sema/DeclSpec.h"
 #include "clang/AST/ASTContext.h"
 #include "clang/AST/DeclCXX.h"
 #include "clang/AST/DeclObjC.h"
@@ -388,19 +389,9 @@
   Code = serialization::EXPR_DEPENDENT_COAWAIT;
 }
 
-void ASTStmtWriter::VisitConceptSpecializationExpr(
-        ConceptSpecializationExpr *E) {
-  VisitExpr(E);
-  ArrayRef<TemplateArgument> TemplateArgs = E->getTemplateArguments();
-  Record.push_back(TemplateArgs.size());
-  Record.AddNestedNameSpecifierLoc(E->getNestedNameSpecifierLoc());
-  Record.AddSourceLocation(E->getTemplateKWLoc());
-  Record.AddDeclarationNameInfo(E->getConceptNameInfo());
-  Record.AddDeclRef(E->getNamedConcept());
-  Record.AddASTTemplateArgumentListInfo(E->getTemplateArgsAsWritten());
-  for (const TemplateArgument &Arg : TemplateArgs)
-    Record.AddTemplateArgument(Arg);
-  const ASTConstraintSatisfaction &Satisfaction = E->getSatisfaction();
+static void
+addConstraintSatisfaction(ASTRecordWriter &Record,
+                          const ASTConstraintSatisfaction &Satisfaction) {
   Record.push_back(Satisfaction.IsSatisfied);
   if (!Satisfaction.IsSatisfied) {
     Record.push_back(Satisfaction.NumRecords);
@@ -418,10 +409,98 @@
       }
     }
   }
+}
+
+static void
+addSubstitutionDiagnostic(
+    ASTRecordWriter &Record,
+    const concepts::Requirement::SubstitutionDiagnostic *D) {
+  Record.AddString(D->SubstitutedEntity);
+  Record.AddSourceLocation(D->DiagLoc);
+  Record.AddString(D->DiagMessage);
+}
+
+void ASTStmtWriter::VisitConceptSpecializationExpr(
+        ConceptSpecializationExpr *E) {
+  VisitExpr(E);
+  ArrayRef<TemplateArgument> TemplateArgs = E->getTemplateArguments();
+  Record.push_back(TemplateArgs.size());
+  Record.AddNestedNameSpecifierLoc(E->getNestedNameSpecifierLoc());
+  Record.AddSourceLocation(E->getTemplateKWLoc());
+  Record.AddDeclarationNameInfo(E->getConceptNameInfo());
+  Record.AddDeclRef(E->getNamedConcept());
+  Record.AddASTTemplateArgumentListInfo(E->getTemplateArgsAsWritten());
+  for (const TemplateArgument &Arg : TemplateArgs)
+    Record.AddTemplateArgument(Arg);
+  if (!E->isValueDependent())
+    addConstraintSatisfaction(Record, E->getSatisfaction());
 
   Code = serialization::EXPR_CONCEPT_SPECIALIZATION;
 }
 
+void ASTStmtWriter::VisitRequiresExpr(RequiresExpr *E) {
+  VisitExpr(E);
+  Record.push_back(E->getLocalParameters().size());
+  Record.push_back(E->getRequirements().size());
+  Record.AddSourceLocation(E->RequiresExprBits.RequiresKWLoc);
+  Record.push_back(E->RequiresExprBits.IsSatisfied);
+  Record.AddDeclRef(E->getBody());
+  for (ParmVarDecl *P : E->getLocalParameters())
+    Record.AddDeclRef(P);
+  for (concepts::Requirement *R : E->getRequirements()) {
+    if (auto *TypeReq = dyn_cast<concepts::TypeRequirement>(R)) {
+      Record.push_back(concepts::Requirement::RK_Type);
+      Record.push_back(TypeReq->Status);
+      if (TypeReq->Status == concepts::TypeRequirement::SS_SubstitutionFailure)
+        addSubstitutionDiagnostic(Record, TypeReq->getSubstitutionDiagnostic());
+      else
+        Record.AddTypeSourceInfo(TypeReq->getType());
+    } else if (auto *ExprReq = dyn_cast<concepts::ExprRequirement>(R)) {
+      Record.push_back(ExprReq->getKind());
+      Record.push_back(ExprReq->Status);
+      if (ExprReq->isExprSubstitutionFailure()) {
+        addSubstitutionDiagnostic(Record,
+         ExprReq->Value.get<concepts::Requirement::SubstitutionDiagnostic *>());
+      } else
+        Record.AddStmt(ExprReq->Value.get<Expr *>());
+      if (ExprReq->getKind() == concepts::Requirement::RK_Compound) {
+        Record.AddSourceLocation(ExprReq->NoexceptLoc);
+        const auto &RetReq = ExprReq->getReturnTypeRequirement();
+        if (RetReq.isSubstitutionFailure()) {
+          Record.push_back(2);
+          addSubstitutionDiagnostic(Record, RetReq.getSubstitutionDiagnostic());
+        } else if (RetReq.isTypeConstraint()) {
+          Record.push_back(1);
+          Record.AddTemplateParameterList(
+              RetReq.getTypeConstraintTemplateParameterList());
+          if (ExprReq->Status >=
+              concepts::ExprRequirement::SS_ConstraintsNotSatisfied)
+            Record.AddStmt(
+                ExprReq->getReturnTypeRequirementSubstitutedConstraintExpr());
+        } else {
+          assert(RetReq.isEmpty());
+          Record.push_back(0);
+        }
+      }
+    } else {
+      auto *NestedReq = cast<concepts::NestedRequirement>(R);
+      Record.push_back(concepts::Requirement::RK_Nested);
+      Record.push_back(NestedReq->isSubstitutionFailure());
+      if (NestedReq->isSubstitutionFailure()){
+        addSubstitutionDiagnostic(Record,
+                                  NestedReq->getSubstitutionDiagnostic());
+      } else {
+        Record.AddStmt(NestedReq->Value.get<Expr *>());
+        if (!NestedReq->isDependent())
+          addConstraintSatisfaction(Record, *NestedReq->Satisfaction);
+      }
+    }
+  }
+  Record.AddSourceLocation(E->getEndLoc());
+
+  Code = serialization::EXPR_REQUIRES;
+}
+
 
 void ASTStmtWriter::VisitCapturedStmt(CapturedStmt *S) {
   VisitStmt(S);