[libclang] Use a copy of the data-recursive RecursiveASTVisitor inside libclang.

This is temporary until we settle on how to make the main RecursiveASTVisitor safe.
There are some modifications on the original version, to avoid extreme memory usage
when compiling for release.

rdar://11179167

git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@156329 91177308-0d34-0410-b5e6-96231b3b80d8

3 files changed, 2245 insertions, 2 deletions

diff --git a/tools/libclang/IndexBody.cpp b/tools/libclang/IndexBody.cpp
index e975a6d1be..26ec7d123d 100644
--- a/tools/libclang/IndexBody.cpp
+++ b/tools/libclang/IndexBody.cpp
@@ -9,7 +9,7 @@
 
 #include "IndexingContext.h"
 
-#include "clang/AST/RecursiveASTVisitor.h"
+#include "RecursiveASTVisitor.h"
 
 using namespace clang;
 using namespace cxindex;
diff --git a/tools/libclang/IndexTypeSourceInfo.cpp b/tools/libclang/IndexTypeSourceInfo.cpp
index b62d52156b..13b2efdb36 100644
--- a/tools/libclang/IndexTypeSourceInfo.cpp
+++ b/tools/libclang/IndexTypeSourceInfo.cpp
@@ -9,7 +9,7 @@
 
 #include "IndexingContext.h"
 
-#include "clang/AST/RecursiveASTVisitor.h"
+#include "RecursiveASTVisitor.h"
 
 using namespace clang;
 using namespace cxindex;
diff --git a/tools/libclang/RecursiveASTVisitor.h b/tools/libclang/RecursiveASTVisitor.h
new file mode 100644
index 0000000000..e4cf489c23
--- /dev/null
+++ b/tools/libclang/RecursiveASTVisitor.h
@@ -0,0 +1,2243 @@
+//===--- RecursiveASTVisitor.h - Recursive AST Visitor ----------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+//  This file defines the RecursiveASTVisitor interface, which recursively
+//  traverses the entire AST.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_CLANG_LIBCLANG_RECURSIVEASTVISITOR_H
+#define LLVM_CLANG_LIBCLANG_RECURSIVEASTVISITOR_H
+
+#include "clang/AST/Decl.h"
+#include "clang/AST/DeclCXX.h"
+#include "clang/AST/DeclFriend.h"
+#include "clang/AST/DeclObjC.h"
+#include "clang/AST/DeclTemplate.h"
+#include "clang/AST/Expr.h"
+#include "clang/AST/ExprCXX.h"
+#include "clang/AST/ExprObjC.h"
+#include "clang/AST/NestedNameSpecifier.h"
+#include "clang/AST/Stmt.h"
+#include "clang/AST/StmtCXX.h"
+#include "clang/AST/StmtObjC.h"
+#include "clang/AST/TemplateBase.h"
+#include "clang/AST/TemplateName.h"
+#include "clang/AST/Type.h"
+#include "clang/AST/TypeLoc.h"
+
+// The following three macros are used for meta programming.  The code
+// using them is responsible for defining macro OPERATOR().
+
+// All unary operators.
+#define UNARYOP_LIST()                          \
+  OPERATOR(PostInc)   OPERATOR(PostDec)         \
+  OPERATOR(PreInc)    OPERATOR(PreDec)          \
+  OPERATOR(AddrOf)    OPERATOR(Deref)           \
+  OPERATOR(Plus)      OPERATOR(Minus)           \
+  OPERATOR(Not)       OPERATOR(LNot)            \
+  OPERATOR(Real)      OPERATOR(Imag)            \
+  OPERATOR(Extension)
+
+// All binary operators (excluding compound assign operators).
+#define BINOP_LIST() \
+  OPERATOR(PtrMemD)              OPERATOR(PtrMemI)    \
+  OPERATOR(Mul)   OPERATOR(Div)  OPERATOR(Rem)        \
+  OPERATOR(Add)   OPERATOR(Sub)  OPERATOR(Shl)        \
+  OPERATOR(Shr)                                       \
+                                                      \
+  OPERATOR(LT)    OPERATOR(GT)   OPERATOR(LE)         \
+  OPERATOR(GE)    OPERATOR(EQ)   OPERATOR(NE)         \
+  OPERATOR(And)   OPERATOR(Xor)  OPERATOR(Or)         \
+  OPERATOR(LAnd)  OPERATOR(LOr)                       \
+                                                      \
+  OPERATOR(Assign)                                    \
+  OPERATOR(Comma)
+
+// All compound assign operators.
+#define CAO_LIST()                                                      \
+  OPERATOR(Mul) OPERATOR(Div) OPERATOR(Rem) OPERATOR(Add) OPERATOR(Sub) \
+  OPERATOR(Shl) OPERATOR(Shr) OPERATOR(And) OPERATOR(Or)  OPERATOR(Xor)
+
+namespace clang {
+
+// A helper macro to implement short-circuiting when recursing.  It
+// invokes CALL_EXPR, which must be a method call, on the derived
+// object (s.t. a user of RecursiveASTVisitor can override the method
+// in CALL_EXPR).
+#define TRY_TO(CALL_EXPR) \
+  do { if (!getDerived().CALL_EXPR) return false; } while (0)
+
+/// \brief A class that does preorder depth-first traversal on the
+/// entire Clang AST and visits each node.
+///
+/// This class performs three distinct tasks:
+///   1. traverse the AST (i.e. go to each node);
+///   2. at a given node, walk up the class hierarchy, starting from
+///      the node's dynamic type, until the top-most class (e.g. Stmt,
+///      Decl, or Type) is reached.
+///   3. given a (node, class) combination, where 'class' is some base
+///      class of the dynamic type of 'node', call a user-overridable
+///      function to actually visit the node.
+///
+/// These tasks are done by three groups of methods, respectively:
+///   1. TraverseDecl(Decl *x) does task #1.  It is the entry point
+///      for traversing an AST rooted at x.  This method simply
+///      dispatches (i.e. forwards) to TraverseFoo(Foo *x) where Foo
+///      is the dynamic type of *x, which calls WalkUpFromFoo(x) and
+///      then recursively visits the child nodes of x.
+///      TraverseStmt(Stmt *x) and TraverseType(QualType x) work
+///      similarly.
+///   2. WalkUpFromFoo(Foo *x) does task #2.  It does not try to visit
+///      any child node of x.  Instead, it first calls WalkUpFromBar(x)
+///      where Bar is the direct parent class of Foo (unless Foo has
+///      no parent), and then calls VisitFoo(x) (see the next list item).
+///   3. VisitFoo(Foo *x) does task #3.
+///
+/// These three method groups are tiered (Traverse* > WalkUpFrom* >
+/// Visit*).  A method (e.g. Traverse*) may call methods from the same
+/// tier (e.g. other Traverse*) or one tier lower (e.g. WalkUpFrom*).
+/// It may not call methods from a higher tier.
+///
+/// Note that since WalkUpFromFoo() calls WalkUpFromBar() (where Bar
+/// is Foo's super class) before calling VisitFoo(), the result is
+/// that the Visit*() methods for a given node are called in the
+/// top-down order (e.g. for a node of type NamedDecl, the order will
+/// be VisitDecl(), VisitNamedDecl(), and then VisitNamespaceDecl()).
+///
+/// This scheme guarantees that all Visit*() calls for the same AST
+/// node are grouped together.  In other words, Visit*() methods for
+/// different nodes are never interleaved.
+///
+/// Clients of this visitor should subclass the visitor (providing
+/// themselves as the template argument, using the curiously recurring
+/// template pattern) and override any of the Traverse*, WalkUpFrom*,
+/// and Visit* methods for declarations, types, statements,
+/// expressions, or other AST nodes where the visitor should customize
+/// behavior.  Most users only need to override Visit*.  Advanced
+/// users may override Traverse* and WalkUpFrom* to implement custom
+/// traversal strategies.  Returning false from one of these overridden
+/// functions will abort the entire traversal.
+///
+/// By default, this visitor tries to visit every part of the explicit
+/// source code exactly once.  The default policy towards templates
+/// is to descend into the 'pattern' class or function body, not any
+/// explicit or implicit instantiations.  Explicit specializations
+/// are still visited, and the patterns of partial specializations
+/// are visited separately.  This behavior can be changed by
+/// overriding shouldVisitTemplateInstantiations() in the derived class
+/// to return true, in which case all known implicit and explicit
+/// instantiations will be visited at the same time as the pattern
+/// from which they were produced.
+template<typename Derived>
+class RecursiveASTVisitor {
+public:
+  /// \brief Return a reference to the derived class.
+  Derived &getDerived() { return *static_cast<Derived*>(this); }
+
+  /// \brief Return whether this visitor should recurse into
+  /// template instantiations.
+  bool shouldVisitTemplateInstantiations() const { return false; }
+
+  /// \brief Return whether this visitor should recurse into the types of
+  /// TypeLocs.
+  bool shouldWalkTypesOfTypeLocs() const { return true; }
+
+  /// \brief Return whether \param S should be traversed using data recursion
+  /// to avoid a stack overflow with extreme cases.
+  bool shouldUseDataRecursionFor(Stmt *S) const {
+    return isa<BinaryOperator>(S) || isa<UnaryOperator>(S) ||
+           isa<CaseStmt>(S) || isa<CXXOperatorCallExpr>(S);
+  }
+
+  /// \brief Recursively visit a statement or expression, by
+  /// dispatching to Traverse*() based on the argument's dynamic type.
+  ///
+  /// \returns false if the visitation was terminated early, true
+  /// otherwise (including when the argument is NULL).
+  bool TraverseStmt(Stmt *S);
+
+  /// \brief Recursively visit a type, by dispatching to
+  /// Traverse*Type() based on the argument's getTypeClass() property.
+  ///
+  /// \returns false if the visitation was terminated early, true
+  /// otherwise (including when the argument is a Null type).
+  bool TraverseType(QualType T);
+
+  /// \brief Recursively visit a type with location, by dispatching to
+  /// Traverse*TypeLoc() based on the argument type's getTypeClass() property.
+  ///
+  /// \returns false if the visitation was terminated early, true
+  /// otherwise (including when the argument is a Null type location).
+  bool TraverseTypeLoc(TypeLoc TL);
+
+  /// \brief Recursively visit a declaration, by dispatching to
+  /// Traverse*Decl() based on the argument's dynamic type.
+  ///
+  /// \returns false if the visitation was terminated early, true
+  /// otherwise (including when the argument is NULL).
+  bool TraverseDecl(Decl *D);
+
+  /// \brief Recursively visit a C++ nested-name-specifier.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseNestedNameSpecifier(NestedNameSpecifier *NNS);
+
+  /// \brief Recursively visit a C++ nested-name-specifier with location
+  /// information.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseNestedNameSpecifierLoc(NestedNameSpecifierLoc NNS);
+
+  /// \brief Recursively visit a name with its location information.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseDeclarationNameInfo(DeclarationNameInfo NameInfo);
+
+  /// \brief Recursively visit a template name and dispatch to the
+  /// appropriate method.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseTemplateName(TemplateName Template);
+
+  /// \brief Recursively visit a template argument and dispatch to the
+  /// appropriate method for the argument type.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  // FIXME: migrate callers to TemplateArgumentLoc instead.
+  bool TraverseTemplateArgument(const TemplateArgument &Arg);
+
+  /// \brief Recursively visit a template argument location and dispatch to the
+  /// appropriate method for the argument type.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseTemplateArgumentLoc(const TemplateArgumentLoc &ArgLoc);
+
+  /// \brief Recursively visit a set of template arguments.
+  /// This can be overridden by a subclass, but it's not expected that
+  /// will be needed -- this visitor always dispatches to another.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  // FIXME: take a TemplateArgumentLoc* (or TemplateArgumentListInfo) instead.
+  bool TraverseTemplateArguments(const TemplateArgument *Args,
+                                 unsigned NumArgs);
+
+  /// \brief Recursively visit a constructor initializer.  This
+  /// automatically dispatches to another visitor for the initializer
+  /// expression, but not for the name of the initializer, so may
+  /// be overridden for clients that need access to the name.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseConstructorInitializer(CXXCtorInitializer *Init);
+
+  /// \brief Recursively visit a lambda capture.
+  ///
+  /// \returns false if the visitation was terminated early, true otherwise.
+  bool TraverseLambdaCapture(LambdaExpr::Capture C);
+  
+  // ---- Methods on Stmts ----
+
+  // Declare Traverse*() for all concrete Stmt classes.
+#define ABSTRACT_STMT(STMT)
+#define STMT(CLASS, PARENT)                                     \
+  bool Traverse##CLASS(CLASS *S);
+#include "clang/AST/StmtNodes.inc"
+  // The above header #undefs ABSTRACT_STMT and STMT upon exit.
+
+  // Define WalkUpFrom*() and empty Visit*() for all Stmt classes.
+  bool WalkUpFromStmt(Stmt *S) { return getDerived().VisitStmt(S); }
+  bool VisitStmt(Stmt *S) { return true; }
+#define STMT(CLASS, PARENT)                                     \
+  bool WalkUpFrom##CLASS(CLASS *S) {                            \
+    TRY_TO(WalkUpFrom##PARENT(S));                              \
+    TRY_TO(Visit##CLASS(S));                                    \
+    return true;                                                \
+  }                                                             \
+  bool Visit##CLASS(CLASS *S) { return true; }
+#include "clang/AST/StmtNodes.inc"
+
+  // Define Traverse*(), WalkUpFrom*(), and Visit*() for unary
+  // operator methods.  Unary operators are not classes in themselves
+  // (they're all opcodes in UnaryOperator) but do have visitors.
+#define OPERATOR(NAME)                                           \
+  bool TraverseUnary##NAME(UnaryOperator *S) {                  \
+    TRY_TO(WalkUpFromUnary##NAME(S));                           \
+    TRY_TO(TraverseStmt(S->getSubExpr()));                      \
+    return true;                                                \
+  }                                                             \
+  bool WalkUpFromUnary##NAME(UnaryOperator *S) {                \
+    TRY_TO(WalkUpFromUnaryOperator(S));                         \
+    TRY_TO(VisitUnary##NAME(S));                                \
+    return true;                                                \
+  }                                                             \
+  bool VisitUnary##NAME(UnaryOperator *S) { return true; }
+
+  UNARYOP_LIST()
+#undef OPERATOR
+
+  // Define Traverse*(), WalkUpFrom*(), and Visit*() for binary
+  // operator methods.  Binary operators are not classes in themselves
+  // (they're all opcodes in BinaryOperator) but do have visitors.
+#define GENERAL_BINOP_FALLBACK(NAME, BINOP_TYPE)                \
+  bool TraverseBin##NAME(BINOP_TYPE *S) {                       \
+    TRY_TO(WalkUpFromBin##NAME(S));                             \
+    TRY_TO(TraverseStmt(S->getLHS()));                          \
+    TRY_TO(TraverseStmt(S->getRHS()));                          \
+    return true;                                                \
+  }                                                             \
+  bool WalkUpFromBin##NAME(BINOP_TYPE *S) {                     \
+    TRY_TO(WalkUpFrom##BINOP_TYPE(S));                          \
+    TRY_TO(VisitBin##NAME(S));                                  \
+    return true;                                                \
+  }                                                             \
+  bool VisitBin##NAME(BINOP_TYPE *S) { return true; }
+
+#define OPERATOR(NAME) GENERAL_BINOP_FALLBACK(NAME, BinaryOperator)
+  BINOP_LIST()
+#undef OPERATOR
+
+  // Define Traverse*(), WalkUpFrom*(), and Visit*() for compound
+  // assignment methods.  Compound assignment operators are not
+  // classes in themselves (they're all opcodes in
+  // CompoundAssignOperator) but do have visitors.
+#define OPERATOR(NAME) \
+  GENERAL_BINOP_FALLBACK(NAME##Assign, CompoundAssignOperator)
+
+  CAO_LIST()
+#undef OPERATOR
+#undef GENERAL_BINOP_FALLBACK
+
+  // ---- Methods on Types ----
+  // FIXME: revamp to take TypeLoc's rather than Types.
+
+  // Declare Traverse*() for all concrete Type classes.
+#define ABSTRACT_TYPE(CLASS, BASE)
+#define TYPE(CLASS, BASE) \
+  bool Traverse##CLASS##Type(CLASS##Type *T);
+#include "clang/AST/TypeNodes.def"
+  // The above header #undefs ABSTRACT_TYPE and TYPE upon exit.
+
+  // Define WalkUpFrom*() and empty Visit*() for all Type classes.
+  bool WalkUpFromType(Type *T) { return getDerived().VisitType(T); }
+  bool VisitType(Type *T) { return true; }
+#define TYPE(CLASS, BASE)                                       \
+  bool WalkUpFrom##CLASS##Type(CLASS##Type *T) {                \
+    TRY_TO(WalkUpFrom##BASE(T));                                \
+    TRY_TO(Visit##CLASS##Type(T));                              \
+    return true;                                                \
+  }                                                             \
+  bool Visit##CLASS##Type(CLASS##Type *T) { return true; }
+#include "clang/AST/TypeNodes.def"
+
+  // ---- Methods on TypeLocs ----
+  // FIXME: this currently just calls the matching Type methods
+
+  // Declare Traverse*() for all concrete Type classes.
+#define ABSTRACT_TYPELOC(CLASS, BASE)
+#define TYPELOC(CLASS, BASE) \
+  bool Traverse##CLASS##TypeLoc(CLASS##TypeLoc TL);
+#include "clang/AST/TypeLocNodes.def"
+  // The above header #undefs ABSTRACT_TYPELOC and TYPELOC upon exit.
+
+  // Define WalkUpFrom*() and empty Visit*() for all TypeLoc classes.
+  bool WalkUpFromTypeLoc(TypeLoc TL) { return getDerived().VisitTypeLoc(TL); }
+  bool VisitTypeLoc(TypeLoc TL) { return true; }
+
+  // QualifiedTypeLoc and UnqualTypeLoc are not declared in
+  // TypeNodes.def and thus need to be handled specially.
+  bool WalkUpFromQualifiedTypeLoc(QualifiedTypeLoc TL) {
+    return getDerived().VisitUnqualTypeLoc(TL.getUnqualifiedLoc());
+  }
+  bool VisitQualifiedTypeLoc(QualifiedTypeLoc TL) { return true; }
+  bool WalkUpFromUnqualTypeLoc(UnqualTypeLoc TL) {
+    return getDerived().VisitUnqualTypeLoc(TL.getUnqualifiedLoc());
+  }
+  bool VisitUnqualTypeLoc(UnqualTypeLoc TL) { return true; }
+
+  // Note that BASE includes trailing 'Type' which CLASS doesn't.
+#define TYPE(CLASS, BASE)                                       \
+  bool WalkUpFrom##CLASS##TypeLoc(CLASS##TypeLoc TL) {          \
+    TRY_TO(WalkUpFrom##BASE##Loc(TL));                          \
+    TRY_TO(Visit##CLASS##TypeLoc(TL));                          \
+    return true;                                                \
+  }                                                             \
+  bool Visit##CLASS##TypeLoc(CLASS##TypeLoc TL) { return true; }
+#include "clang/AST/TypeNodes.def"
+
+  // ---- Methods on Decls ----
+
+  // Declare Traverse*() for all concrete Decl classes.
+#define ABSTRACT_DECL(DECL)
+#define DECL(CLASS, BASE) \
+  bool Traverse##CLASS##Decl(CLASS##Decl *D);
+#include "clang/AST/DeclNodes.inc"
+  // The above header #undefs ABSTRACT_DECL and DECL upon exit.
+
+  // Define WalkUpFrom*() and empty Visit*() for all Decl classes.
+  bool WalkUpFromDecl(Decl *D) { return getDerived().VisitDecl(D); }
+  bool VisitDecl(Decl *D) { return true; }
+#define DECL(CLASS, BASE)                                       \
+  bool WalkUpFrom##CLASS##Decl(CLASS##Decl *D) {                \
+    TRY_TO(WalkUpFrom##BASE(D));                                \
+    TRY_TO(Visit##CLASS##Decl(D));                              \
+    return true;                                                \
+  }                                                             \
+  bool Visit##CLASS##Decl(CLASS##Decl *D) { return true; }
+#include "clang/AST/DeclNodes.inc"
+
+private:
+  // These are helper methods used by more than one Traverse* method.
+  bool TraverseTemplateParameterListHelper(TemplateParameterList *TPL);
+  bool TraverseClassInstantiations(ClassTemplateDecl* D, Decl *Pattern);
+  bool TraverseFunctionInstantiations(FunctionTemplateDecl* D) ;
+  bool TraverseTemplateArgumentLocsHelper(const TemplateArgumentLoc *TAL,
+                                          unsigned Count);
+  bool TraverseArrayTypeLocHelper(ArrayTypeLoc TL);
+  bool TraverseRecordHelper(RecordDecl *D);
+  bool TraverseCXXRecordHelper(CXXRecordDecl *D);
+  bool TraverseDeclaratorHelper(DeclaratorDecl *D);
+  bool TraverseDeclContextHelper(DeclContext *DC);
+  bool TraverseFunctionHelper(FunctionDecl *D);
+  bool TraverseVarHelper(VarDecl *D);
+
+  bool Walk(Stmt *S);
+
+  struct EnqueueJob {
+    Stmt *S;
+    Stmt::child_iterator StmtIt;
+
+    EnqueueJob(Stmt *S) : S(S), StmtIt() {
+      if (Expr *E = dyn_cast_or_null<Expr>(S))
+        S = E->IgnoreParens();
+    }
+  };
+  bool dataTraverse(Stmt *S);
+};
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::dataTraverse(Stmt *S) {
+
+  SmallVector<EnqueueJob, 16> Queue;
+  Queue.push_back(S);
+
+  while (!Queue.empty()) {
+    EnqueueJob &job = Queue.back();
+    Stmt *CurrS = job.S;
+    if (!CurrS) {
+      Queue.pop_back();
+      continue;
+    }
+
+    if (getDerived().shouldUseDataRecursionFor(CurrS)) {
+      if (job.StmtIt == Stmt::child_iterator()) {
+        if (!Walk(CurrS)) return false;
+        job.StmtIt = CurrS->child_begin();
+      } else {
+        ++job.StmtIt;
+      }
+
+      if (job.StmtIt != CurrS->child_end())
+        Queue.push_back(*job.StmtIt);
+      else
+        Queue.pop_back();
+      continue;
+    }
+
+    Queue.pop_back();
+    TRY_TO(TraverseStmt(CurrS));
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::Walk(Stmt *S) {
+
+#define DISPATCH_WALK(NAME, CLASS, VAR) \
+  return getDerived().WalkUpFrom##NAME(static_cast<CLASS*>(VAR));
+
+  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(S)) {
+    switch (BinOp->getOpcode()) {
+#define OPERATOR(NAME) \
+    case BO_##NAME: DISPATCH_WALK(Bin##NAME, BinaryOperator, S);
+
+    BINOP_LIST()
+#undef OPERATOR
+
+#define OPERATOR(NAME)                                          \
+    case BO_##NAME##Assign:                          \
+    DISPATCH_WALK(Bin##NAME##Assign, CompoundAssignOperator, S);
+
+    CAO_LIST()
+#undef OPERATOR
+    }
+  } else if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(S)) {
+    switch (UnOp->getOpcode()) {
+#define OPERATOR(NAME)                                                  \
+    case UO_##NAME: DISPATCH_WALK(Unary##NAME, UnaryOperator, S);
+
+    UNARYOP_LIST()
+#undef OPERATOR
+    }
+  }
+
+  // Top switch stmt: dispatch to TraverseFooStmt for each concrete FooStmt.
+  switch (S->getStmtClass()) {
+  case Stmt::NoStmtClass: break;
+#define ABSTRACT_STMT(STMT)
+#define STMT(CLASS, PARENT) \
+  case Stmt::CLASS##Class: DISPATCH_WALK(CLASS, CLASS, S);
+#include "clang/AST/StmtNodes.inc"
+  }
+
+#undef DISPATCH_WALK
+
+  return true;
+}
+
+#define DISPATCH(NAME, CLASS, VAR) \
+  return getDerived().Traverse##NAME(static_cast<CLASS*>(VAR))
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseStmt(Stmt *S) {
+  if (!S)
+    return true;
+
+  if (getDerived().shouldUseDataRecursionFor(S))
+    return dataTraverse(S);
+
+  // If we have a binary expr, dispatch to the subcode of the binop.  A smart
+  // optimizer (e.g. LLVM) will fold this comparison into the switch stmt
+  // below.
+  if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(S)) {
+    switch (BinOp->getOpcode()) {
+#define OPERATOR(NAME) \
+    case BO_##NAME: DISPATCH(Bin##NAME, BinaryOperator, S);
+
+    BINOP_LIST()
+#undef OPERATOR
+#undef BINOP_LIST
+
+#define OPERATOR(NAME)                                          \
+    case BO_##NAME##Assign:                          \
+      DISPATCH(Bin##NAME##Assign, CompoundAssignOperator, S);
+
+    CAO_LIST()
+#undef OPERATOR
+#undef CAO_LIST
+    }
+  } else if (UnaryOperator *UnOp = dyn_cast<UnaryOperator>(S)) {
+    switch (UnOp->getOpcode()) {
+#define OPERATOR(NAME)                                                  \
+    case UO_##NAME: DISPATCH(Unary##NAME, UnaryOperator, S);
+
+    UNARYOP_LIST()
+#undef OPERATOR
+#undef UNARYOP_LIST
+    }
+  }
+
+  // Top switch stmt: dispatch to TraverseFooStmt for each concrete FooStmt.
+  switch (S->getStmtClass()) {
+  case Stmt::NoStmtClass: break;
+#define ABSTRACT_STMT(STMT)
+#define STMT(CLASS, PARENT) \
+  case Stmt::CLASS##Class: DISPATCH(CLASS, CLASS, S);
+#include "clang/AST/StmtNodes.inc"
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseType(QualType T) {
+  if (T.isNull())
+    return true;
+
+  switch (T->getTypeClass()) {
+#define ABSTRACT_TYPE(CLASS, BASE)
+#define TYPE(CLASS, BASE) \
+  case Type::CLASS: DISPATCH(CLASS##Type, CLASS##Type, \
+                             const_cast<Type*>(T.getTypePtr()));
+#include "clang/AST/TypeNodes.def"
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseTypeLoc(TypeLoc TL) {
+  if (TL.isNull())
+    return true;
+
+  switch (TL.getTypeLocClass()) {
+#define ABSTRACT_TYPELOC(CLASS, BASE)
+#define TYPELOC(CLASS, BASE) \
+  case TypeLoc::CLASS: \
+    return getDerived().Traverse##CLASS##TypeLoc(*cast<CLASS##TypeLoc>(&TL));
+#include "clang/AST/TypeLocNodes.def"
+  }
+
+  return true;
+}
+
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseDecl(Decl *D) {
+  if (!D)
+    return true;
+
+  // As a syntax visitor, we want to ignore declarations for
+  // implicitly-defined declarations (ones not typed explicitly by the
+  // user).
+  if (D->isImplicit())
+    return true;
+
+  switch (D->getKind()) {
+#define ABSTRACT_DECL(DECL)
+#define DECL(CLASS, BASE) \
+  case Decl::CLASS: DISPATCH(CLASS##Decl, CLASS##Decl, D);
+#include "clang/AST/DeclNodes.inc"
+ }
+
+  return true;
+}
+
+#undef DISPATCH
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseNestedNameSpecifier(
+                                                    NestedNameSpecifier *NNS) {
+  if (!NNS)
+    return true;
+
+  if (NNS->getPrefix())
+    TRY_TO(TraverseNestedNameSpecifier(NNS->getPrefix()));
+
+  switch (NNS->getKind()) {
+  case NestedNameSpecifier::Identifier:
+  case NestedNameSpecifier::Namespace:
+  case NestedNameSpecifier::NamespaceAlias:
+  case NestedNameSpecifier::Global:
+    return true;
+
+  case NestedNameSpecifier::TypeSpec:
+  case NestedNameSpecifier::TypeSpecWithTemplate:
+    TRY_TO(TraverseType(QualType(NNS->getAsType(), 0)));
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseNestedNameSpecifierLoc(
+                                                  NestedNameSpecifierLoc NNS) {
+  if (!NNS)
+    return true;
+
+   if (NestedNameSpecifierLoc Prefix = NNS.getPrefix())
+     TRY_TO(TraverseNestedNameSpecifierLoc(Prefix));
+
+  switch (NNS.getNestedNameSpecifier()->getKind()) {
+  case NestedNameSpecifier::Identifier:
+  case NestedNameSpecifier::Namespace:
+  case NestedNameSpecifier::NamespaceAlias:
+  case NestedNameSpecifier::Global:
+    return true;
+
+  case NestedNameSpecifier::TypeSpec:
+  case NestedNameSpecifier::TypeSpecWithTemplate:
+    TRY_TO(TraverseTypeLoc(NNS.getTypeLoc()));
+    break;
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseDeclarationNameInfo(
+                                                 DeclarationNameInfo NameInfo) {
+  switch (NameInfo.getName().getNameKind()) {
+  case DeclarationName::CXXConstructorName:
+  case DeclarationName::CXXDestructorName:
+  case DeclarationName::CXXConversionFunctionName:
+    if (TypeSourceInfo *TSInfo = NameInfo.getNamedTypeInfo())
+      TRY_TO(TraverseTypeLoc(TSInfo->getTypeLoc()));
+
+    break;
+
+  case DeclarationName::Identifier:
+  case DeclarationName::ObjCZeroArgSelector:
+  case DeclarationName::ObjCOneArgSelector:
+  case DeclarationName::ObjCMultiArgSelector:
+  case DeclarationName::CXXOperatorName:
+  case DeclarationName::CXXLiteralOperatorName:
+  case DeclarationName::CXXUsingDirective:
+    break;
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseTemplateName(TemplateName Template) {
+  if (DependentTemplateName *DTN = Template.getAsDependentTemplateName())
+    TRY_TO(TraverseNestedNameSpecifier(DTN->getQualifier()));
+  else if (QualifiedTemplateName *QTN = Template.getAsQualifiedTemplateName())
+    TRY_TO(TraverseNestedNameSpecifier(QTN->getQualifier()));
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseTemplateArgument(
+                                                const TemplateArgument &Arg) {
+  switch (Arg.getKind()) {
+  case TemplateArgument::Null:
+  case TemplateArgument::Declaration:
+  case TemplateArgument::Integral:
+    return true;
+
+  case TemplateArgument::Type:
+    return getDerived().TraverseType(Arg.getAsType());
+
+  case TemplateArgument::Template:
+  case TemplateArgument::TemplateExpansion:
+    return getDerived().TraverseTemplateName(
+                                          Arg.getAsTemplateOrTemplatePattern());
+
+  case TemplateArgument::Expression:
+    return getDerived().TraverseStmt(Arg.getAsExpr());
+
+  case TemplateArgument::Pack:
+    return getDerived().TraverseTemplateArguments(Arg.pack_begin(),
+                                                  Arg.pack_size());
+  }
+
+  return true;
+}
+
+// FIXME: no template name location?
+// FIXME: no source locations for a template argument pack?
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseTemplateArgumentLoc(
+                                           const TemplateArgumentLoc &ArgLoc) {
+  const TemplateArgument &Arg = ArgLoc.getArgument();
+
+  switch (Arg.getKind()) {
+  case TemplateArgument::Null:
+  case TemplateArgument::Declaration:
+  case TemplateArgument::Integral:
+    return true;
+
+  case TemplateArgument::Type: {
+    // FIXME: how can TSI ever be NULL?
+    if (TypeSourceInfo *TSI = ArgLoc.getTypeSourceInfo())
+      return getDerived().TraverseTypeLoc(TSI->getTypeLoc());
+    else
+      return getDerived().TraverseType(Arg.getAsType());
+  }
+
+  case TemplateArgument::Template:
+  case TemplateArgument::TemplateExpansion:
+    if (ArgLoc.getTemplateQualifierLoc())
+      TRY_TO(getDerived().TraverseNestedNameSpecifierLoc(
+                                            ArgLoc.getTemplateQualifierLoc()));
+    return getDerived().TraverseTemplateName(
+                                         Arg.getAsTemplateOrTemplatePattern());
+
+  case TemplateArgument::Expression:
+    return getDerived().TraverseStmt(ArgLoc.getSourceExpression());
+
+  case TemplateArgument::Pack:
+    return getDerived().TraverseTemplateArguments(Arg.pack_begin(),
+                                                  Arg.pack_size());
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseTemplateArguments(
+                                                  const TemplateArgument *Args,
+                                                            unsigned NumArgs) {
+  for (unsigned I = 0; I != NumArgs; ++I) {
+    TRY_TO(TraverseTemplateArgument(Args[I]));
+  }
+
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseConstructorInitializer(
+                                                     CXXCtorInitializer *Init) {
+  if (TypeSourceInfo *TInfo = Init->getTypeSourceInfo())
+    TRY_TO(TraverseTypeLoc(TInfo->getTypeLoc()));
+
+  if (Init->isWritten())
+    TRY_TO(TraverseStmt(Init->getInit()));
+  return true;
+}
+
+template<typename Derived>
+bool RecursiveASTVisitor<Derived>::TraverseLambdaCapture(LambdaExpr::Capture C){
+  return true;
+}
+
+// ----------------- Type traversal -----------------
+
+// This macro makes available a variable T, the passed-in type.
+#define DEF_TRAVERSE_TYPE(TYPE, CODE)                     \
+  template<typename Derived>                                           \
+  bool RecursiveASTVisitor<Derived>::Traverse##TYPE (TYPE *T) {        \
+    TRY_TO(WalkUpFrom##TYPE (T));                                      \
+    { CODE; }                                                          \
+    return true;                                                       \
+  }
+
+DEF_TRAVERSE_TYPE(BuiltinType, { })
+
+DEF_TRAVERSE_TYPE(ComplexType, {
+    TRY_TO(TraverseType(T->getElementType()));
+  })
+
+DEF_TRAVERSE_TYPE(PointerType, {
+    TRY_TO(TraverseType(T->getPointeeType()));
+  })
+
+DEF_TRAVERSE_TYPE(BlockPointerType, {
+    TRY_TO(TraverseType(T->getPointeeType()));
+  })
+
+DEF_TRAVERSE_TYPE(LValueReferenceType, {
+    TRY_TO(TraverseType(T->getPointeeType()));
+  })
+
+DEF_TRAVERSE_TYPE(RValueReferenceType, {
+    TRY_TO(TraverseType(T->getPointeeType()));
+  })
+
+DEF_TRAVERSE_TYPE(MemberPointerType, {
+    TRY_TO(TraverseType(QualType(T->getClass(), 0)));
+    TRY_TO(TraverseType(T->getPointeeType()));
+  })
+
+DEF_TRAVERSE_TYPE(ConstantArrayType, {
+    TRY_TO(TraverseType(T->getElementType()));
+  })
+
+DEF_TRAVERSE_TYPE(IncompleteArrayType, {
+    TRY_TO(TraverseType(T->getElementType()));
+  })
+
+DEF_TRAVERSE_TYPE(VariableArrayType, {
+    TRY_TO(TraverseType(T->getElementType()));
+    TRY_TO(TraverseStmt(T->getSizeExpr()));
+  })
+
+DEF_TRAVERSE_TYPE(DependentSizedArrayType, {
+    TRY_TO(TraverseType(T->getElementType()));
+    if (T->getSizeExpr())
+      TRY_TO(TraverseStmt(T->getSizeExpr()));
+  })
+
+DEF_TRAVERSE_TYPE(DependentSizedExtVectorType, {
+    if (T->getSizeExpr())
+      TRY_TO(TraverseStmt(T->getSizeExpr()));
+    TRY_TO(TraverseType(T->getElementType()));
+  })
+
+DEF_TRAVERSE_TYPE(VectorType, {
+    TRY_TO(TraverseType(T->getElementType()));
+  })
+
+DEF_TRAVERSE_TYPE(ExtVectorType, {
+    TRY_TO(TraverseType(T->getElementType()));
+  })
+
+DEF_TRAVERSE_TYPE(FunctionNoProtoType, {
+    TRY_TO(TraverseType(T->getResultType()));
+  })
+
+DEF_TRAVERSE_TYPE(FunctionProtoType, {
+    TRY_TO(TraverseType(T->getResultType()));
+
+    for (FunctionProtoType::arg_type_iterator A = T->arg_type_begin(),
+                                           AEnd = T->arg_type_end();
+         A != AEnd; ++A) {
+      TRY_TO(TraverseType(*A));
+    }
+
+    for (FunctionProtoType::exception_iterator E = T->exception_begin(),
+                                            EEnd = T->exception_end();
+         E != EEnd; ++E) {
+      TRY_TO(TraverseType(*E));
+    }
+  })
+
+DEF_TRAVERSE_TYPE(UnresolvedUsingType, { })
+DEF_TRAVERSE_TYPE(TypedefType, { })
+
+DEF_TRAVERSE_TYPE(TypeOfExprType, {
+    TRY_TO(TraverseStmt(T->getUnderlyingExpr()));
+  })
+
+DEF_TRAVERSE_TYPE(TypeOfType, {
+    TRY_TO(TraverseType(T->getUnderlyingType()));
+  })
+
+DEF_TRAVERSE_TYPE(DecltypeType, {
+    TRY_TO(TraverseStmt(T->getUnderlyingExpr()));
+  })
+
+DEF_TRAVERSE_TYPE(UnaryTransformType, {
+    TRY_TO(TraverseType(T->getBaseType()));
+    TRY_TO(TraverseType(T->getUnderlyingType()));
+    })
+
+DEF_TRAVERSE_TYPE(AutoType, {
+    TRY_TO(TraverseType(T->getDeducedType()));
+  })
+
+DEF_TRAVERSE_TYPE(RecordType, { })
+DEF_TRAVERSE_TYPE(EnumType, { })
+DEF_TRAVERSE_TYPE(TemplateTypeParmType, { })
+DEF_TRAVERSE_TYPE(SubstTemplateTypeParmType, { })
+DEF_TRAVERSE_TYPE(SubstTemplateTypeParmPackType, { })
+
+DEF_TRAVERSE_TYPE(TemplateSpecializationType, {
+    TRY_TO(TraverseTemplateName(T->getTemplateName()));
+    TRY_TO(TraverseTemplateArguments(T->getArgs(), T->getNumArgs()));
+  })
+
+DEF_TRAVERSE_TYPE(InjectedClassNameType, { })
+
+DEF_TRAVERSE_TYPE(AttributedType, {
+    TRY_TO(TraverseType(T->getModifiedType()));
+  })
+
+DEF_TRAVERSE_TYPE(ParenType, {
+    TRY_TO(TraverseType(T->getInnerType()));
+  })
+
+DEF_TRAVERSE_TYPE(ElaboratedType, {
+    if (T->getQualifier()) {
+      TRY_TO(TraverseNestedNameSpecifier(T->getQualifier()));
+    }
+    TRY_TO(TraverseType(T->getNamedType()));
+  })
+
+DEF_TRAVERSE_TYPE(DependentNameType, {
+    TRY_TO(TraverseNestedNameSpecifier(T->getQualifier()));
+  })
+
+DEF_TRAVERSE_TYPE(DependentTemplateSpecializationType, {
+    TRY_TO(TraverseNestedNameSpecifier(T->getQualifier()));
+    TRY_TO(TraverseTemplateArguments(T->getArgs(), T->getNumArgs()));
+  })
+
+DEF_TRAVERSE_TYPE(PackExpansionType, {
+    TRY