[Syntax] Remove delayed folding from tree building.

[hlopko]

Summary

This patch removes delayed folding and replaces it with forward peeking.

Delayed folding was previously used as a solution to the problem that
declaration doesn't have a representation in the AST. For example following
code:

int a,b;

is expressed in the AST as:

TranslationUnitDecl
|-...
|-VarDecl `int a`
`-VarDecl `int b`

And in the syntax tree we need:

*: TranslationUnit
`-SimpleDeclaration
  |-int
  |-SimpleDeclarator
  | `-a
  |-,
  |-SimpleDeclarator
  | `-b
  |-;

So in words, we need to create SimpleDeclaration to be a parent of
SimpleDeclarator nodes. Previously we used delayed folding to make sure SimpleDeclarations will be
eventually created. And in case multiple declarators requested declaration
creation, declaration range was extended to cover all declarators.

This design started to be hard to reason about, so we decided to replace it with
forward peeking. The last declarator node in the chain is responsible for creating
SimpleDeclaration for the whole chain. Range of the declaration corresponds to
the source range of the declarator node. Declarator decides whether its the last
one by peeking to the next AST node (see isResponsibleForCreatingDeclaration).

This patch does following:

• Removed delayed folding logic
• Tweaks Token.dumpForTests
• Moves getQualifiedNameStart inside BuildTreeVisitor
• Extracts BuildTreeVisitor.ProcessDeclaratorAndDeclaration
• Renames Builder.getDeclRange to Builder.getDeclarationRange and uses the method in all places.
• Adds a bunch of tests

[hlopko]

Reformat

[hlopko]

Polish

[hlopko]

Rebase

[hlopko]

Rebase

[gribozavr2]

Could you add the following tests?

struct Point { int x, y; } point, *pointPtr;
typedef struct Point { int x, y; } PointTy, *PointPtr;
typedef struct { int x, y; } PointTy, *PointPtr;

clang/lib/Tooling/Syntax/BuildTree.cpp

278

I think this cast should not be necessary -- D is already a const T*.

[hlopko]

Remove unnecessary cast

[hlopko]

I propose adding those tests in a separate patch to keep this one focused. Those tests are currently failing, because:

• we assume initializer, if present, is extending the declarator range, but struct P {} p; has initializer ending where declarator ended already.
• UnknownExpressions finds its way inside SimpleDeclarator for p in struct P {} p, *pp;
• typedefs also fail, unable to find the end of declarator properly. I didn't investigate further.

Fixing those seems worthy of a separate patch.

clang/lib/Tooling/Syntax/BuildTree.cpp

 #include <cstddef>
 #include <map>
 
 using namespace clang;
 
 LLVM_ATTRIBUTE_UNUSED
 static bool isImplicitExpr(clang::Expr *E) { return E->IgnoreImplicit() != E; }
 
-static SourceLocation getQualifiedNameStart(DeclaratorDecl *D) {
-  auto DN = D->getDeclName();
-  bool IsAnonymous = DN.isIdentifier() && !DN.getAsIdentifierInfo();
-  if (IsAnonymous)
-    return SourceLocation();
-  return D->getQualifierLoc() ? D->getQualifierLoc().getBeginLoc()
-                              : D->getLocation();
-}
-
 namespace {
 /// Get start location of the Declarator from the TypeLoc.
 /// E.g.:
 ///   loc of `(` in `int (a)`
 ///   loc of `*` in `int *(a)`
 ///   loc of the first `(` in `int (*a)(int)`
 ///   loc of the `*` in `int *(a)(int)`
 ///   loc of the first `*` in `const int *const *volatile a;`
if (From)
       Mapping.add(From, New);
   }
   void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
                 TypeLoc L) {
     // FIXME: add mapping for TypeLocs
     foldNode(Range, New, nullptr);
   }
 
-  /// Must be called with the range of each `DeclaratorDecl`. Ensures the
-  /// corresponding declarator nodes are covered by `SimpleDeclaration`.
-  void noticeDeclRange(llvm::ArrayRef<syntax::Token> Range);
-
   /// Notifies that we should not consume trailing semicolon when computing
   /// token range of \p D.
   void noticeDeclWithoutSemicolon(Decl *D);
 
   /// Mark the \p Child node with a corresponding \p Role. All marked children
   /// should be consumed by foldNode.
   /// When called on expressions (clang::Expr is derived from clang::Stmt),
   /// wraps expressions into expression statement.
   void markStmtChild(Stmt *Child, NodeRole Role);
   /// Should be called for expressions in non-statement position to avoid
   /// wrapping into expression statement.
   void markExprChild(Expr *Child, NodeRole Role);
   /// Set role for a token starting at \p Loc.
   void markChildToken(SourceLocation Loc, NodeRole R);
   /// Set role for \p T.
   void markChildToken(const syntax::Token *T, NodeRole R);
 
   /// Set role for \p N.
   void markChild(syntax::Node *N, NodeRole R);
   /// Set role for the syntax node matching \p N.
   void markChild(ASTPtr N, NodeRole R);
-  /// Set role for the delayed node that spans exactly \p Range.
-  void markDelayedChild(llvm::ArrayRef<syntax::Token> Range, NodeRole R);
-  /// Set role for the node that may or may not be delayed. Node must span
-  /// exactly \p Range.
-  void markMaybeDelayedChild(llvm::ArrayRef<syntax::Token> Range, NodeRole R);
 
   /// Finish building the tree and consume the root node.
   syntax::TranslationUnit *finalize() && {
     auto Tokens = Arena.tokenBuffer().expandedTokens();
     assert(!Tokens.empty());
     assert(Tokens.back().kind() == tok::eof);
 
     // Build the root of the tree, consuming all the children.
public:
   }
 
   llvm::ArrayRef<syntax::Token>
   getTemplateRange(const ClassTemplateSpecializationDecl *D) const {
     auto Tokens = getRange(D->getSourceRange());
     return maybeAppendSemicolon(Tokens, D);
   }
 
-  llvm::ArrayRef<syntax::Token> getDeclRange(const Decl *D) const {
+  template <class T> bool isResponsibleForCreatingDeclaration(const T *D) const {
+    static_assert((
+          std::is_base_of<DeclaratorDecl, T>::value ||
+          std::is_base_of<TypedefNameDecl, T>::value),
+        "only DeclaratorDecl and TypedefNameDecl are supported.");
+
+    const auto *V = llvm::dyn_cast<T>(D);
+    // We only handle VarDecls and TypedefDecls right now.
+    if (V == nullptr) { return false; }
+
+    const Decl *Next = V->getNextDeclInContext();
+
+    // There's no further sibling, this one is responsible.
+    if (Next == nullptr) { return true; }
+    const auto *NextV = llvm::dyn_cast<T>(Next);
+    // Next sibling is not a VarDecl, this one is responsible.
+    if (NextV == nullptr) { return true; }
+    // Next sibling begins at the same loc, it must be the same declaration.
+    if (NextV->getBeginLoc() != V->getBeginLoc()) { return true; }
+
+    // NextV is a member of the same declaration, and we need the last member to
+    // create declaration.
+    return false;
+  }
+
+  llvm::ArrayRef<syntax::Token> getDeclarationRange(Decl *D) {
     llvm::ArrayRef<clang::syntax::Token> Tokens;
     // We want to drop the template parameters for specializations.
-    if (const auto *S = llvm::dyn_cast<TagDecl>(D))
+    if (const auto *S = llvm::dyn_cast<TagDecl>(D)) {
       Tokens = getRange(S->TypeDecl::getBeginLoc(), S->getEndLoc());
-    else
+    } else {
       Tokens = getRange(D->getSourceRange());
+    }
     return maybeAppendSemicolon(Tokens, D);
   }
+
   llvm::ArrayRef<syntax::Token> getExprRange(const Expr *E) const {
     return getRange(E->getSourceRange());
   }
+
   /// Find the adjusted range for the statement, consuming the trailing
   /// semicolon when needed.
   llvm::ArrayRef<syntax::Token> getStmtRange(const Stmt *S) const {
     auto Tokens = getRange(S->getSourceRange());
     if (isa<CompoundStmt>(S))
       return Tokens;
 
     // Some statements miss a trailing semicolon, e.g. 'return', 'continue' and
Forest(syntax::Arena &A) {
       for (auto &T : A.tokenBuffer().expandedTokens().drop_back()) {
         auto *L = new (A.allocator()) syntax::Leaf(&T);
         L->Original = true;
         L->CanModify = A.tokenBuffer().spelledForExpanded(T).hasValue();
         Trees.insert(Trees.end(), {&T, L});
       }
     }
 
-    ~Forest() { assert(DelayedFolds.empty()); }
-
-    void assignRoleDelayed(llvm::ArrayRef<syntax::Token> Range,
-                           syntax::NodeRole Role) {
-      auto It = DelayedFolds.find(Range.begin());
-      assert(It != DelayedFolds.end());
-      assert(It->second.End == Range.end());
-      It->second.Role = Role;
-    }
-
-    void assignRoleMaybeDelayed(llvm::ArrayRef<syntax::Token> Range,
-                                syntax::NodeRole Role) {
-      auto It = DelayedFolds.find(Range.begin());
-      if (It == DelayedFolds.end())
-        return assignRole(Range, Role);
-      assert(It->second.End == Range.end());
-      It->second.Role = Role;
-    }
+    ~Forest() {}
 
     void assignRole(llvm::ArrayRef<syntax::Token> Range,
                     syntax::NodeRole Role) {
       assert(!Range.empty());
       auto It = Trees.lower_bound(Range.begin());
+      /* auto Next = std::next(It); */
       assert(It != Trees.end() && "no node found");
       assert(It->first == Range.begin() && "no child with the specified range");
       assert((std::next(It) == Trees.end() ||
               std::next(It)->first == Range.end()) &&
              "no child with the specified range");
       assert(It->second->role() == NodeRole::Detached &&
              "re-assigning role for a child");
       It->second->setRole(Role);
     }
 
     /// Add \p Node to the forest and attach child nodes based on \p Tokens.
     void foldChildren(const syntax::Arena &A,
                       llvm::ArrayRef<syntax::Token> Tokens,
                       syntax::Tree *Node) {
-      // Execute delayed folds inside `Tokens`.
-      auto BeginFolds = DelayedFolds.lower_bound(Tokens.begin());
-      auto EndFolds = BeginFolds;
-      for (; EndFolds != DelayedFolds.end() &&
-             EndFolds->second.End <= Tokens.end();
-           ++EndFolds)
-        ;
-      // We go in reverse order to ensure we fold deeper nodes first.
-      for (auto RevIt = EndFolds; RevIt != BeginFolds; --RevIt) {
-        auto It = std::prev(RevIt);
-        foldChildrenEager(A, llvm::makeArrayRef(It->first, It->second.End),
-                          It->second.Node);
-      }
-      DelayedFolds.erase(BeginFolds, EndFolds);
-
       // Attach children to `Node`.
-      foldChildrenEager(A, Tokens, Node);
-    }
+      assert(Node->firstChild() == nullptr && "node already has children");
 
-    /// Schedule a call to `foldChildren` that will only be executed when
-    /// containing node is folded. The range of delayed nodes can be extended by
-    /// calling `extendDelayedFold`. Only one delayed node for each starting
-    /// token is allowed.
-    void foldChildrenDelayed(llvm::ArrayRef<syntax::Token> Tokens,
-                             syntax::Tree *Node) {
-      assert(!Tokens.empty());
-      bool Inserted =
-          DelayedFolds.insert({Tokens.begin(), DelayedFold{Tokens.end(), Node}})
-              .second;
-      (void)Inserted;
-      assert(Inserted && "Multiple delayed folds start at the same token");
+      auto *FirstToken = Tokens.begin();
+      auto BeginChildren = Trees.lower_bound(FirstToken);
+
+      assert((BeginChildren == Trees.end() ||
+              BeginChildren->first == FirstToken) &&
+             "fold crosses boundaries of existing subtrees");
+      auto EndChildren = Trees.lower_bound(Tokens.end());
+      assert(
+          (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&
+          "fold crosses boundaries of existing subtrees");
+
+      // We need to go in reverse order, because we can only prepend.
+      for (auto It = EndChildren; It != BeginChildren; --It) {
+        auto *C = std::prev(It)->second;
+        if (C->role() == NodeRole::Detached)
+          C->setRole(NodeRole::Unknown);
+        Node->prependChildLowLevel(C);
       }
 
-    /// If there a delayed fold, starting at `ExtendedRange.begin()`, extends
-    /// its endpoint to `ExtendedRange.end()` and returns true.
-    /// Otherwise, returns false.
-    bool extendDelayedFold(llvm::ArrayRef<syntax::Token> ExtendedRange) {
-      assert(!ExtendedRange.empty());
-      auto It = DelayedFolds.find(ExtendedRange.data());
-      if (It == DelayedFolds.end())
-        return false;
-      assert(It->second.End <= ExtendedRange.end());
-      It->second.End = ExtendedRange.end();
-      return true;
+      // Mark that this node came from the AST and is backed by the source code.
+      Node->Original = true;
+      Node->CanModify = A.tokenBuffer().spelledForExpanded(Tokens).hasValue();
+
+      Trees.erase(BeginChildren, EndChildren);
+      Trees.insert({FirstToken, Node});
     }
 
     // EXPECTS: all tokens were consumed and are owned by a single root node.
     syntax::Node *finalize() && {
       assert(Trees.size() == 1);
       auto *Root = Trees.begin()->second;
       Trees = {};
       return Root;
std::string str(const syntax::Arena &A) const {
             "- '{0}' covers '{1}'+{2} tokens\n", It->second->kind(),
             It->first->text(A.sourceManager()), CoveredTokens));
         R += It->second->dump(A);
       }
       return R;
     }
 
   private:
-    /// Implementation detail of `foldChildren`, does acutal folding ignoring
-    /// delayed folds.
-    void foldChildrenEager(const syntax::Arena &A,
-                           llvm::ArrayRef<syntax::Token> Tokens,
-                           syntax::Tree *Node) {
-      assert(Node->firstChild() == nullptr && "node already has children");
-
-      auto *FirstToken = Tokens.begin();
-      auto BeginChildren = Trees.lower_bound(FirstToken);
-      assert((BeginChildren == Trees.end() ||
-              BeginChildren->first == FirstToken) &&
-             "fold crosses boundaries of existing subtrees");
-      auto EndChildren = Trees.lower_bound(Tokens.end());
-      assert(
-          (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&
-          "fold crosses boundaries of existing subtrees");
-
-      // We need to go in reverse order, because we can only prepend.
-      for (auto It = EndChildren; It != BeginChildren; --It) {
-        auto *C = std::prev(It)->second;
-        if (C->role() == NodeRole::Detached)
-          C->setRole(NodeRole::Unknown);
-        Node->prependChildLowLevel(C);
-      }
-
-      // Mark that this node came from the AST and is backed by the source code.
-      Node->Original = true;
-      Node->CanModify = A.tokenBuffer().spelledForExpanded(Tokens).hasValue();
-
-      Trees.erase(BeginChildren, EndChildren);
-      Trees.insert({FirstToken, Node});
-    }
-
     /// Maps from the start token to a subtree starting at that token.
     /// Keys in the map are pointers into the array of expanded tokens, so
     /// pointer order corresponds to the order of preprocessor tokens.
     std::map<const syntax::Token *, syntax::Node *> Trees;
-
-    /// See documentation of `foldChildrenDelayed` for details.
-    struct DelayedFold {
-      const syntax::Token *End = nullptr;
-      syntax::Tree *Node = nullptr;
-      NodeRole Role = NodeRole::Unknown;
-    };
-    std::map<const syntax::Token *, DelayedFold> DelayedFolds;
   };
 
   /// For debugging purposes.
   std::string str() { return Pending.str(Arena); }
 
   syntax::Arena &Arena;
   /// To quickly find tokens by their start location.
   llvm::DenseMap</*SourceLocation*/ unsigned, const syntax::Token *>
       LocationToToken;
   Forest Pending;
   llvm::DenseSet<Decl *> DeclsWithoutSemicolons;
+  llvm::DenseSet<const Decl *> DeclsWithDeclarationAlreadyCreated;
   ASTToSyntaxMapping Mapping;
 };
 
 namespace {
 class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
 public:
   explicit BuildTreeVisitor(ASTContext &Ctx, syntax::TreeBuilder &Builder)
       : Builder(Builder), LangOpts(Ctx.getLangOpts()) {}
 
   bool shouldTraversePostOrder() const { return true; }
 
   bool WalkUpFromDeclaratorDecl(DeclaratorDecl *DD) {
-    // Ensure declarators are covered by SimpleDeclaration.
-    Builder.noticeDeclRange(Builder.getDeclRange(DD));
-
-    // Build the declarator node.
-    SourceRange Initializer;
-    if (auto *V = llvm::dyn_cast<VarDecl>(DD)) {
-      auto *I = V->getInit();
-      // Initializers in range-based-for are not part of the declarator
-      if (I && !V->isCXXForRangeDecl())
-        Initializer = I->getSourceRange();
-    }
-    auto Declarator = getDeclaratorRange(
-        Builder.sourceManager(), DD->getTypeSourceInfo()->getTypeLoc(),
-        getQualifiedNameStart(DD), Initializer);
-    if (Declarator.isValid()) {
-      auto *N = new (allocator()) syntax::SimpleDeclarator;
-      Builder.foldNode(Builder.getRange(Declarator), N, DD);
-      Builder.markChild(N, syntax::NodeRole::SimpleDeclaration_declarator);
-    }
+    return ProcessDeclaratorAndDeclaration(DD);
 
-    return true;
-  }
-
-  bool WalkUpFromTypedefNameDecl(TypedefNameDecl *D) {
-    // Ensure declarators are covered by SimpleDeclaration.
-    Builder.noticeDeclRange(Builder.getDeclRange(D));
-
-    auto R = getDeclaratorRange(
-        Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
-        /*Name=*/D->getLocation(), /*Initializer=*/SourceRange());
-    if (R.isValid()) {
-      auto *N = new (allocator()) syntax::SimpleDeclarator;
-      Builder.foldNode(Builder.getRange(R), N, D);
-      Builder.markChild(N, syntax::NodeRole::SimpleDeclaration_declarator);
-    }
-    return true;
+  bool WalkUpFromTypedefNameDecl(TypedefNameDecl *TD) {
+    return ProcessDeclaratorAndDeclaration(TD);
   }
 
   bool VisitDecl(Decl *D) {
     assert(!D->isImplicit());
-    Builder.foldNode(Builder.getDeclRange(D),
+    Builder.foldNode(Builder.getDeclarationRange(D),
                      new (allocator()) syntax::UnknownDeclaration(), D);
     return true;
   }
 
   // RAV does not call WalkUpFrom* on explicit instantiations, so we have to
   // override Traverse.
   // FIXME: make RAV call WalkUpFrom* instead.
   bool
   TraverseClassTemplateSpecializationDecl(ClassTemplateSpecializationDecl *C) {
     if (!RecursiveASTVisitor::TraverseClassTemplateSpecializationDecl(C))
       return false;
     if (C->isExplicitSpecialization())
       return true; // we are only interested in explicit instantiations.
     auto *Declaration =
         cast<syntax::SimpleDeclaration>(handleFreeStandingTagDecl(C));
     foldExplicitTemplateInstantiation(
         Builder.getTemplateRange(C), Builder.findToken(C->getExternLoc()),
         Builder.findToken(C->getTemplateKeywordLoc()), Declaration, C);
     return true;
   }
 
   bool WalkUpFromTemplateDecl(TemplateDecl *S) {
     foldTemplateDeclaration(
-        Builder.getDeclRange(S),
+        Builder.getDeclarationRange(S),
         Builder.findToken(S->getTemplateParameters()->getTemplateLoc()),
-        Builder.getDeclRange(S->getTemplatedDecl()), S);
+        Builder.getDeclarationRange(S->getTemplatedDecl()), S);
     return true;
   }
 
   bool WalkUpFromTagDecl(TagDecl *C) {
     // FIXME: build the ClassSpecifier node.
     if (!C->isFreeStanding()) {
       assert(C->getNumTemplateParameterLists() == 0);
       return true;
     }
     handleFreeStandingTagDecl(C);
     return true;
   }
 
   syntax::Declaration *handleFreeStandingTagDecl(TagDecl *C) {
     assert(C->isFreeStanding());
     // Class is a declaration specifier and needs a spanning declaration node.
-    auto DeclarationRange = Builder.getDeclRange(C);
+    auto DeclarationRange = Builder.getDeclarationRange(C);
     syntax::Declaration *Result = new (allocator()) syntax::SimpleDeclaration;
     Builder.foldNode(DeclarationRange, Result, nullptr);
 
     // Build TemplateDeclaration nodes if we had template parameters.
     auto ConsumeTemplateParameters = [&](const TemplateParameterList &L) {
       const auto *TemplateKW = Builder.findToken(L.getTemplateLoc());
       auto R = llvm::makeArrayRef(TemplateKW, DeclarationRange.end());
       Result =
public:
   bool WalkUpFromExpr(Expr *E) {
     assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
     Builder.foldNode(Builder.getExprRange(E),
                      new (allocator()) syntax::UnknownExpression, E);
     return true;
   }
 
   bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
-    auto Tokens = Builder.getDeclRange(S);
+    auto Tokens = Builder.getDeclarationRange(S);
     if (Tokens.front().kind() == tok::coloncolon) {
       // Handle nested namespace definitions. Those start at '::' token, e.g.
       // namespace a^::b {}
       // FIXME: build corresponding nodes for the name of this namespace.
       return true;
     }
     Builder.foldNode(Tokens, new (allocator()) syntax::NamespaceDefinition, S);
     return true;
bool WalkUpFromArrayTypeLoc(ArrayTypeLoc L) {
     Builder.markChildToken(L.getRBracketLoc(), syntax::NodeRole::CloseParen);
     Builder.foldNode(Builder.getRange(L.getLBracketLoc(), L.getRBracketLoc()),
                      new (allocator()) syntax::ArraySubscript, L);
     return true;
   }
 
   bool WalkUpFromFunctionTypeLoc(FunctionTypeLoc L) {
     Builder.markChildToken(L.getLParenLoc(), syntax::NodeRole::OpenParen);
-    for (auto *P : L.getParams())
-      Builder.markDelayedChild(
-          Builder.getDeclRange(P),
+    for (auto *P : L.getParams()) {
+      Builder.markChild(
+          P,
           syntax::NodeRole::ParametersAndQualifiers_parameter);
+    }
     Builder.markChildToken(L.getRParenLoc(), syntax::NodeRole::CloseParen);
     Builder.foldNode(Builder.getRange(L.getLParenLoc(), L.getEndLoc()),
                      new (allocator()) syntax::ParametersAndQualifiers, L);
     return true;
   }
 
   bool WalkUpFromFunctionProtoTypeLoc(FunctionProtoTypeLoc L) {
     if (!L.getTypePtr()->hasTrailingReturn())
       return WalkUpFromFunctionTypeLoc(L);
 
-    auto TrailingReturnTokens = BuildTrailingReturn(L);
+    auto* TrailingReturnTokens = BuildTrailingReturn(L);
     // Finish building the node for parameters.
     Builder.markChild(TrailingReturnTokens,
                       syntax::NodeRole::ParametersAndQualifiers_trailingReturn);
     return WalkUpFromFunctionTypeLoc(L);
   }
 
   bool WalkUpFromMemberPointerTypeLoc(MemberPointerTypeLoc L) {
     auto SR = L.getLocalSourceRange();
bool WalkUpFromCXXForRangeStmt(CXXForRangeStmt *S) {
     Builder.markChildToken(S->getForLoc(), syntax::NodeRole::IntroducerKeyword);
     Builder.markStmtChild(S->getBody(), syntax::NodeRole::BodyStatement);
     Builder.foldNode(Builder.getStmtRange(S),
                      new (allocator()) syntax::RangeBasedForStatement, S);
     return true;
   }
 
   bool WalkUpFromEmptyDecl(EmptyDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::EmptyDeclaration, S);
     return true;
   }
 
   bool WalkUpFromStaticAssertDecl(StaticAssertDecl *S) {
     Builder.markExprChild(S->getAssertExpr(),
                           syntax::NodeRole::StaticAssertDeclaration_condition);
     Builder.markExprChild(S->getMessage(),
                           syntax::NodeRole::StaticAssertDeclaration_message);
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::StaticAssertDeclaration, S);
     return true;
   }
 
   bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::LinkageSpecificationDeclaration,
                      S);
     return true;
   }
 
   bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::NamespaceAliasDefinition, S);
     return true;
   }
 
   bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::UsingNamespaceDirective, S);
     return true;
   }
 
   bool WalkUpFromUsingDecl(UsingDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::UsingDeclaration, S);
     return true;
   }
 
   bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::UsingDeclaration, S);
     return true;
   }
 
   bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::UsingDeclaration, S);
     return true;
   }
 
   bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
-    Builder.foldNode(Builder.getDeclRange(S),
+    Builder.foldNode(Builder.getDeclarationRange(S),
                      new (allocator()) syntax::TypeAliasDeclaration, S);
     return true;
   }
 
 private:
+
+  template <class T> SourceLocation getQualifiedNameStart(T *D) {
+    static_assert((
+          std::is_base_of<DeclaratorDecl, T>::value ||
+          std::is_base_of<TypedefNameDecl, T>::value),
+        "only DeclaratorDecl and TypedefNameDecl are supported.");
+
+    auto DN = D->getDeclName();
+    bool IsAnonymous = DN.isIdentifier() && !DN.getAsIdentifierInfo();
+    if (IsAnonymous)
+      return SourceLocation();
+
+    if (const auto *DD = llvm::dyn_cast<DeclaratorDecl>(D)) {
+      if (DD->getQualifierLoc()) {
+        return DD->getQualifierLoc().getBeginLoc();
+      }
+    }
+
+    return D->getLocation();
+  }
+
+  // Folds SimpleDeclarator (if present) and in case this is the last declarator
+  // in the chain it also folds SimpleDeclaration node.
+  template <class T> bool ProcessDeclaratorAndDeclaration(T *D) {
+    SourceRange Initializer;
+    if (auto *V = llvm::dyn_cast<VarDecl>(D)) {
+      auto *I = V->getInit();
+      // Initializers in range-based-for are not part of the declarator
+      if (I && !V->isCXXForRangeDecl())
+        Initializer = I->getSourceRange();
+    }
+    auto Range = getDeclaratorRange(
+        Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
+        getQualifiedNameStart(D), Initializer);
+
+    // There doesn't have to be a declarator (e.g. `void foo(int)` only has
+    // declaration).
+    if (Range.getBegin().isValid()) {
+      auto *N = new (allocator()) syntax::SimpleDeclarator;
+      Builder.foldNode(Builder.getRange(Range), N, nullptr);
+      Builder.markChild(N, syntax::NodeRole::SimpleDeclaration_declarator);
+    }
+
+    if (Builder.isResponsibleForCreatingDeclaration(D)) {
+      Builder.foldNode(
+          Builder.getDeclarationRange(D), new (allocator()) syntax::SimpleDeclaration, D);
+    }
+    return true;
+  }
+
+
   /// Returns the range of the built node.
   syntax::TrailingReturnType *BuildTrailingReturn(FunctionProtoTypeLoc L) {
     assert(L.getTypePtr()->hasTrailingReturn());
 
     auto ReturnedType = L.getReturnLoc();
     // Build node for the declarator, if any.
     auto ReturnDeclaratorRange =
         getDeclaratorRange(this->Builder.sourceManager(), ReturnedType,
syntax::TrailingReturnType *BuildTrailingReturn(FunctionProtoTypeLoc L) {
     const auto *Arrow = Return.begin() - 1;
     assert(Arrow->kind() == tok::arrow);
     auto Tokens = llvm::makeArrayRef(Arrow, Return.end());
     Builder.markChildToken(Arrow, syntax::NodeRole::TrailingReturnType_arrow);
     if (ReturnDeclarator)
       Builder.markChild(ReturnDeclarator,
                         syntax::NodeRole::TrailingReturnType_declarator);
     auto *R = new (allocator()) syntax::TrailingReturnType;
-    Builder.foldNode(Tokens, R, nullptr);
+    Builder.foldNode(Tokens, R, L);
     return R;
   }
 
   void foldExplicitTemplateInstantiation(
       ArrayRef<syntax::Token> Range, const syntax::Token *ExternKW,
       const syntax::Token *TemplateKW,
       syntax::SimpleDeclaration *InnerDeclaration, Decl *From) {
     assert(!ExternKW || ExternKW->kind() == tok::kw_extern);
Builder.foldNode(
         Range, new (allocator()) syntax::ExplicitTemplateInstantiation, From);
   }
 
   syntax::TemplateDeclaration *foldTemplateDeclaration(
       ArrayRef<syntax::Token> Range, const syntax::Token *TemplateKW,
       ArrayRef<syntax::Token> TemplatedDeclaration, Decl *From) {
     assert(TemplateKW && TemplateKW->kind() == tok::kw_template);
     Builder.markChildToken(TemplateKW, syntax::NodeRole::IntroducerKeyword);
-    Builder.markMaybeDelayedChild(
-        TemplatedDeclaration,
-        syntax::NodeRole::TemplateDeclaration_declaration);
 
     auto *N = new (allocator()) syntax::TemplateDeclaration;
     Builder.foldNode(Range, N, From);
+    Builder.markChild(N,
+         syntax::NodeRole::TemplateDeclaration_declaration);
     return N;
   }
 
   /// A small helper to save some typing.
   llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
 
   syntax::TreeBuilder &Builder;
   const LangOptions &LangOpts;
 };
 } // namespace
 
-void syntax::TreeBuilder::noticeDeclRange(llvm::ArrayRef<syntax::Token> Range) {
-  if (Pending.extendDelayedFold(Range))
-    return;
-  Pending.foldChildrenDelayed(Range,
-                              new (allocator()) syntax::SimpleDeclaration);
-}
-
 void syntax::TreeBuilder::noticeDeclWithoutSemicolon(Decl *D) {
   DeclsWithoutSemicolons.insert(D);
 }
 
 void syntax::TreeBuilder::markChildToken(SourceLocation Loc, NodeRole Role) {
   if (Loc.isInvalid())
     return;
   Pending.assignRole(*findToken(Loc), Role);

 }
 
 void syntax::TreeBuilder::markChild(ASTPtr N, NodeRole R) {
   auto *SN = Mapping.find(N);
   assert(SN != nullptr);
   setRole(SN, R);
 }
 
-void syntax::TreeBuilder::markDelayedChild(llvm::ArrayRef<syntax::Token> Range,
-                                           NodeRole R) {
-  Pending.assignRoleDelayed(Range, R);
-}
-
-void syntax::TreeBuilder::markMaybeDelayedChild(
-    llvm::ArrayRef<syntax::Token> Range, NodeRole R) {
-  Pending.assignRoleMaybeDelayed(Range, R);
-}
-
 void syntax::TreeBuilder::markStmtChild(Stmt *Child, NodeRole Role) {
   if (!Child)
     return;
 
   syntax::Tree *ChildNode = Mapping.find(Child);
   assert(ChildNode != nullptr);
 
   // This is an expression in a statement position, consume the trailing

clang/lib/Tooling/Syntax/Tokens.cpp

 }
 
 std::string syntax::Token::str() const {
   return std::string(llvm::formatv("Token({0}, length = {1})",
                                    tok::getTokenName(kind()), length()));
 }
 
 std::string syntax::Token::dumpForTests(const SourceManager &SM) const {
   return std::string(
-      llvm::formatv("{0}   {1}", tok::getTokenName(kind()), text(SM)));
+      llvm::formatv("Token(`{0}`, {1}, length = {2})", text(SM), tok::getTokenName(kind()), length()));
 }
 
 std::string TokenBuffer::dumpForTests() const {
   auto PrintToken = [this](const syntax::Token &T) -> std::string {
     if (T.kind() == tok::eof)
       return "<eof>";
     return std::string(T.text(*SourceMgr));
   };

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-SimpleDeclaration
   |   |-(
   |   `-)
   `-CompoundStatement
     |-{
     `-}
 )txt");
 }
 
+TEST_F(SyntaxTreeTest, SimpleVariable) {
+  expectTreeDumpEqual(
+      R"cpp(
+int a;
+int b = 42;
+    )cpp",
+      R"txt(
+*: TranslationUnit
+|-SimpleDeclaration
+| |-int
+| |-SimpleDeclarator
+| | `-a
+| `-;
+`-SimpleDeclaration
+  |-int
+  |-SimpleDeclarator
+  | |-b
+  | |-=
+  | `-UnknownExpression
+  |   `-42
+  `-;
+)txt");
+}
+
+TEST_F(SyntaxTreeTest, SimpleFunction) {
+  expectTreeDumpEqual(
+      R"cpp(
+void foo(int a, int b) {}
+    )cpp",
+      R"txt(
+*: TranslationUnit
+`-SimpleDeclaration
+  |-void
+  |-SimpleDeclarator
+  | |-foo
+  | `-ParametersAndQualifiers
+  |   |-(
+  |   |-SimpleDeclaration
+  |   | |-int
+  |   | `-SimpleDeclarator
+  |   |   `-a
+  |   |-,
+  |   |-SimpleDeclaration
+  |   | |-int
+  |   | `-SimpleDeclarator
+  |   |   `-b
+  |   `-)
+  `-CompoundStatement
+    |-{
+    `-}
+)txt");
+}
+
 TEST_F(SyntaxTreeTest, If) {
   expectTreeDumpEqual(
       R"cpp(
 int main() {
   if (true) {}
   if (true) {} else if (false) {}
 }
         )cpp",
`-CompoundStatement
     |   `-;
     `-}
 )txt");
 }
 
 TEST_F(SyntaxTreeTest, MultipleDeclaratorsGrouping) {
   expectTreeDumpEqual(
       R"cpp(
-      int *a, b;
+      int *a, b; int *c, d;
   )cpp",
       R"txt(
 *: TranslationUnit
+|-SimpleDeclaration
+| |-int
+| |-SimpleDeclarator
+| | |-*
+| | `-a
+| |-,
+| |-SimpleDeclarator
+| | `-b
+| `-;
 `-SimpleDeclaration
   |-int
   |-SimpleDeclarator
   | |-*
-  | `-a
+  | `-c
   |-,
   |-SimpleDeclarator
-  | `-b
+  | `-d
   `-;
   )txt");
+}
+
+TEST_F(SyntaxTreeTest, MultipleDeclaratorsGroupingTypedef) {
   expectTreeDumpEqual(
       R"cpp(
     typedef int *a, b;
   )cpp",
       R"txt(
 *: TranslationUnit
 `-SimpleDeclaration
   |-typedef
std::vector<std::pair<std::string /*Input*/, std::string /*Expected*/>>
           {"void test() { if (true) [[{}]] else {} }",
            "void test() { if (true) ; else {} }"},
           {"void test() { [[;]] }", "void test() {  }"}};
   for (const auto &C : Cases)
     CheckTransformation(C.first, C.second, RemoveStatement);
 }
 
 TEST_F(SyntaxTreeTest, SynthesizedNodes) {
-  buildTree("");
+  buildTree(";");
 
   auto *C = syntax::createPunctuation(*Arena, tok::comma);
   ASSERT_NE(C, nullptr);
   EXPECT_EQ(C->token()->kind(), tok::comma);
   EXPECT_TRUE(C->canModify());
   EXPECT_FALSE(C->isOriginal());
   EXPECT_TRUE(C->isDetached());
 
   auto *S = syntax::createEmptyStatement(*Arena);
   ASSERT_NE(S, nullptr);
   EXPECT_TRUE(S->canModify());
   EXPECT_FALSE(S->isOriginal());
   EXPECT_TRUE(S->isDetached());
 }
 
 } // namespace