Introduce basic support for dependent types, type-dependent

expressions, and value-dependent expressions. This permits us to parse
some template definitions.

This is not a complete solution; we're missing type- and
value-dependent computations for most of the expression types, and
we're missing checks for dependent types and type-dependent
expressions throughout Sema.

llvm-svn: 60615

6 files changed, 135 insertions, 4 deletions

diff --git a/clang/lib/AST/ASTContext.cpp b/clang/lib/AST/ASTContext.cpp
index 7c8b4b1b413..35647cf02aa 100644
--- a/clang/lib/AST/ASTContext.cpp
+++ b/clang/lib/AST/ASTContext.cpp
@@ -183,7 +183,14 @@ void ASTContext::InitBuiltinTypes() {
   InitBuiltinType(WCharTy,             BuiltinType::WChar);
 
   // Placeholder type for functions.
-  InitBuiltinType(OverloadTy,         BuiltinType::Overload);
+  InitBuiltinType(OverloadTy,          BuiltinType::Overload);
+
+  // Placeholder type for type-dependent expressions whose type is
+  // completely unknown. No code should ever check a type against
+  // DependentTy and users should never see it; however, it is here to
+  // help diagnose failures to properly check for type-dependent
+  // expressions.
+  InitBuiltinType(DependentTy,         BuiltinType::Dependent);
 
   // C99 6.2.5p11.
   FloatComplexTy      = getComplexType(FloatTy);
@@ -235,6 +242,8 @@ ASTContext::getTypeInfo(const Type *T) {
     assert(0 && "Incomplete types have no size!");
   case Type::VariableArray:
     assert(0 && "VLAs not implemented yet!");
+  case Type::DependentSizedArray:
+    assert(0 && "Dependently-sized arrays don't have a known size");
   case Type::ConstantArray: {
     const ConstantArrayType *CAT = cast<ConstantArrayType>(T);
     
@@ -759,6 +768,28 @@ QualType ASTContext::getVariableArrayType(QualType EltTy, Expr *NumElts,
   return QualType(New, 0);
 }
 
+/// getDependentSizedArrayType - Returns a non-unique reference to
+/// the type for a dependently-sized array of the specified element
+/// type. FIXME: We will need these to be uniqued, or at least
+/// comparable, at some point.
+QualType ASTContext::getDependentSizedArrayType(QualType EltTy, Expr *NumElts,
+                                                ArrayType::ArraySizeModifier ASM,
+                                                unsigned EltTypeQuals) {
+  assert((NumElts->isTypeDependent() || NumElts->isValueDependent()) && 
+         "Size must be type- or value-dependent!");
+
+  // Since we don't unique expressions, it isn't possible to unique
+  // dependently-sized array types.
+
+  DependentSizedArrayType *New 
+    = new DependentSizedArrayType(EltTy, QualType(), NumElts, 
+                                  ASM, EltTypeQuals);
+
+  DependentSizedArrayTypes.push_back(New);
+  Types.push_back(New);
+  return QualType(New, 0);
+}
+
 QualType ASTContext::getIncompleteArrayType(QualType EltTy,
                                             ArrayType::ArraySizeModifier ASM,
                                             unsigned EltTypeQuals) {
@@ -1174,6 +1205,11 @@ QualType ASTContext::getCanonicalType(QualType T) {
     return getIncompleteArrayType(NewEltTy, IAT->getSizeModifier(),
                                   IAT->getIndexTypeQualifier());
   
+  if (DependentSizedArrayType *DSAT = dyn_cast<DependentSizedArrayType>(AT))
+    return getDependentSizedArrayType(NewEltTy, DSAT->getSizeExpr(),
+                                      DSAT->getSizeModifier(),
+                                      DSAT->getIndexTypeQualifier());    
+
   // FIXME: What is the ownership of size expressions in VLAs?
   VariableArrayType *VAT = cast<VariableArrayType>(AT);
   return getVariableArrayType(NewEltTy, VAT->getSizeExpr(),
@@ -1246,6 +1282,16 @@ const ArrayType *ASTContext::getAsArrayType(QualType T) {
     return cast<ArrayType>(getIncompleteArrayType(NewEltTy,
                                                   IAT->getSizeModifier(),
                                                  IAT->getIndexTypeQualifier()));
+
+  // FIXME: What is the ownership of size expressions in
+  // dependent-sized array types?
+  if (const DependentSizedArrayType *DSAT 
+        = dyn_cast<DependentSizedArrayType>(ATy))
+    return cast<ArrayType>(
+                     getDependentSizedArrayType(NewEltTy, 
+                                                DSAT->getSizeExpr(),
+                                                DSAT->getSizeModifier(),
+                                                DSAT->getIndexTypeQualifier()));
   
   // FIXME: What is the ownership of size expressions in VLAs?
   const VariableArrayType *VAT = cast<VariableArrayType>(ATy);
diff --git a/clang/lib/AST/CFG.cpp b/clang/lib/AST/CFG.cpp
index 82336a44e08..69e82f2b832 100644
--- a/clang/lib/AST/CFG.cpp
+++ b/clang/lib/AST/CFG.cpp
@@ -154,6 +154,8 @@ private:
   bool badCFG;
 };
   
+// FIXME: Add support for dependent-sized array types in C++?
+// Does it even make sense to build a CFG for an uninstantiated template?
 static VariableArrayType* FindVA(Type* t) {
   while (ArrayType* vt = dyn_cast<ArrayType>(t)) {
     if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt))
diff --git a/clang/lib/AST/Expr.cpp b/clang/lib/AST/Expr.cpp
index a3264b010b7..14db18c1345 100644
--- a/clang/lib/AST/Expr.cpp
+++ b/clang/lib/AST/Expr.cpp
@@ -103,7 +103,10 @@ const char *UnaryOperator::getOpcodeStr(Opcode Op) {
 
 CallExpr::CallExpr(StmtClass SC, Expr *fn, Expr **args, unsigned numargs, 
                    QualType t, SourceLocation rparenloc)
-  : Expr(SC, t), NumArgs(numargs) {
+  : Expr(SC, t, 
+         fn->isTypeDependent() || hasAnyTypeDependentArguments(args, numargs),
+         fn->isValueDependent() || hasAnyValueDependentArguments(args, numargs)),
+    NumArgs(numargs) {
   SubExprs = new Stmt*[numargs+1];
   SubExprs[FN] = fn;
   for (unsigned i = 0; i != numargs; ++i)
@@ -113,7 +116,10 @@ CallExpr::CallExpr(StmtClass SC, Expr *fn, Expr **args, unsigned numargs,
 
 CallExpr::CallExpr(Expr *fn, Expr **args, unsigned numargs, QualType t,
                    SourceLocation rparenloc)
-  : Expr(CallExprClass, t), NumArgs(numargs) {
+  : Expr(CallExprClass, t,
+         fn->isTypeDependent() || hasAnyTypeDependentArguments(args, numargs),
+         fn->isValueDependent() || hasAnyValueDependentArguments(args, numargs)),
+    NumArgs(numargs) {
   SubExprs = new Stmt*[numargs+1];
   SubExprs[FN] = fn;
   for (unsigned i = 0; i != numargs; ++i)
@@ -631,6 +637,26 @@ Expr *Expr::IgnoreParenCasts() {
   }
 }
 
+/// hasAnyTypeDependentArguments - Determines if any of the expressions
+/// in Exprs is type-dependent.
+bool Expr::hasAnyTypeDependentArguments(Expr** Exprs, unsigned NumExprs) {
+  for (unsigned I = 0; I < NumExprs; ++I)
+    if (Exprs[I]->isTypeDependent())
+      return true;
+
+  return false;
+}
+
+/// hasAnyValueDependentArguments - Determines if any of the expressions
+/// in Exprs is value-dependent.
+bool Expr::hasAnyValueDependentArguments(Expr** Exprs, unsigned NumExprs) {
+  for (unsigned I = 0; I < NumExprs; ++I)
+    if (Exprs[I]->isValueDependent())
+      return true;
+
+  return false;
+}
+
 bool Expr::isConstantExpr(ASTContext &Ctx, SourceLocation *Loc) const {
   switch (getStmtClass()) {
   default:
diff --git a/clang/lib/AST/StmtIterator.cpp b/clang/lib/AST/StmtIterator.cpp
index 46882422e1c..48003450191 100644
--- a/clang/lib/AST/StmtIterator.cpp
+++ b/clang/lib/AST/StmtIterator.cpp
@@ -16,6 +16,8 @@
 
 using namespace clang;
 
+// FIXME: Add support for dependent-sized array types in C++?
+// Does it even make sense to build a CFG for an uninstantiated template?
 static inline VariableArrayType* FindVA(Type* t) {
   while (ArrayType* vt = dyn_cast<ArrayType>(t)) {
     if (VariableArrayType* vat = dyn_cast<VariableArrayType>(vt))
diff --git a/clang/lib/AST/Type.cpp b/clang/lib/AST/Type.cpp
index 303fc7e7ca5..5909c976aa6 100644
--- a/clang/lib/AST/Type.cpp
+++ b/clang/lib/AST/Type.cpp
@@ -43,6 +43,10 @@ void VariableArrayType::Destroy(ASTContext& C) {
   delete this;  
 }
 
+void DependentSizedArrayType::Destroy(ASTContext& C) {
+  SizeExpr->Destroy(C);
+  delete this;
+}
 
 /// getArrayElementTypeNoTypeQual - If this is an array type, return the
 /// element type of the array, potentially with type qualifiers missing.
@@ -634,11 +638,12 @@ bool Type::isAggregateType() const {
 
 /// isConstantSizeType - Return true if this is not a variable sized type,
 /// according to the rules of C99 6.7.5p3.  It is not legal to call this on
-/// incomplete types.
+/// incomplete types or dependent types.
 bool Type::isConstantSizeType() const {
   if (const ASQualType *ASQT = dyn_cast<ASQualType>(CanonicalType))
     return ASQT->getBaseType()->isConstantSizeType();
   assert(!isIncompleteType() && "This doesn't make sense for incomplete types");
+  assert(!isDependentType() && "This doesn't make sense for dependent types");
   // The VAT must have a size, as it is known to be complete.
   return !isa<VariableArrayType>(CanonicalType);
 }
@@ -706,6 +711,7 @@ const char *BuiltinType::getName() const {
   case LongDouble:        return "long double";
   case WChar:             return "wchar_t";
   case Overload:          return "<overloaded function type>";
+  case Dependent:         return "<dependent type>";
   }
 }
 
@@ -780,6 +786,11 @@ QualType TypedefType::LookThroughTypedefs() const {
   }
 }
 
+TypeOfExpr::TypeOfExpr(Expr *E, QualType can)
+  : Type(TypeOfExp, can, E->isTypeDependent()), TOExpr(E) {
+  assert(!isa<TypedefType>(can) && "Invalid canonical type");
+}
+
 bool RecordType::classof(const TagType *TT) {
   return isa<RecordDecl>(TT->getDecl());
 }
@@ -932,6 +943,30 @@ void VariableArrayType::getAsStringInternal(std::string &S) const {
   getElementType().getAsStringInternal(S);
 }
 
+void DependentSizedArrayType::getAsStringInternal(std::string &S) const {
+  S += '[';
+  
+  if (getIndexTypeQualifier()) {
+    AppendTypeQualList(S, getIndexTypeQualifier());
+    S += ' ';
+  }
+  
+  if (getSizeModifier() == Static)
+    S += "static";
+  else if (getSizeModifier() == Star)
+    S += '*';
+  
+  if (getSizeExpr()) {
+    std::string SStr;
+    llvm::raw_string_ostream s(SStr);
+    getSizeExpr()->printPretty(s);
+    S += s.str();
+  }
+  S += ']';
+  
+  getElementType().getAsStringInternal(S);
+}
+
 void VectorType::getAsStringInternal(std::string &S) const {
   // FIXME: We prefer to print the size directly here, but have no way
   // to get the size of the type.
diff --git a/clang/lib/AST/TypeSerialization.cpp b/clang/lib/AST/TypeSerialization.cpp
index 3bdc946de7e..8e35f187a3e 100644
--- a/clang/lib/AST/TypeSerialization.cpp
+++ b/clang/lib/AST/TypeSerialization.cpp
@@ -315,6 +315,26 @@ Type* VariableArrayType::CreateImpl(ASTContext& Context, Deserializer& D) {
 }
 
 //===----------------------------------------------------------------------===//
+// DependentSizedArrayType
+//===----------------------------------------------------------------------===//
+
+void DependentSizedArrayType::EmitImpl(Serializer& S) const {
+  S.Emit(getElementType());
+  S.EmitInt(getSizeModifier());
+  S.EmitInt(getIndexTypeQualifier());
+  S.EmitOwnedPtr(SizeExpr);
+}
+
+Type* DependentSizedArrayType::CreateImpl(ASTContext& Context, Deserializer& D) {
+  QualType ElTy = QualType::ReadVal(D);
+  ArraySizeModifier am = static_cast<ArraySizeModifier>(D.ReadInt());
+  unsigned ITQ = D.ReadInt();  
+  Expr* SizeExpr = D.ReadOwnedPtr<Expr>(Context);
+  
+  return Context.getDependentSizedArrayType(ElTy,SizeExpr,am,ITQ).getTypePtr();
+}
+
+//===----------------------------------------------------------------------===//
 // IncompleteArrayType
 //===----------------------------------------------------------------------===//