Migrate Declarators to use the List API

[eduucaldas]

Summary

After this change all nodes that have a delimited-list are using the List API.

Implementation details:
Let's look at a declaration with multiple declarators:
int a, b;
To generate a declarator list node we need to have the range of declarators: a, b. However, the ClangAST actually stores them as separate declarations:
int a ;
int b;
To solve that we mark the declarators on each separate declaration in the ClangAST and then for the final declarator int b, we shrink its range to fit to the already marked declarators.

[eduucaldas]

clang/lib/Tooling/Syntax/BuildTree.cpp

594

WDYT about the naming?

clang/unittests/Tooling/Syntax/BuildTreeTest.cpp

2932–2937

This sounds weird and is probably the reason why SO many tests failed.

According to the grammar a function definition/declaration might only have one declarator:

function-definition:
attribute-specifier-seq_opt decl-specifier-seq_opt declarator virt-specifier-seq_opt function-body
...

But our implementation calls processDeclaratorAndDeclaration for DeclaratorDecl, which englobes FunctionDecl.

I also noticed that we seem to have quite extensive support for declarations even rarer ones:
StaticAssertDeclaration, LinkageSpecificationDeclaration ... Moreover, their names and definitions seem to adequately follow the grammar. However we don't have a FunctionDefinition as defined in the grammar. Was grouping FunctionDefintion and FunctionDeclaration as SimpleDeclaration a conscious choice? (I looked quickly at commits that added processDeclaratorAndDeclaration but couldn't find any clue)

[gribozavr2]

clang/lib/Tooling/Syntax/BuildTree.cpp

593

594

Very nice name!

clang/unittests/Tooling/Syntax/BuildTreeTest.cpp

2932–2937

It seemed reasonable for uniformity. However, I can definitely see an argument for defining a special kind of tree node for them, especially now that if we use SimpleDeclaration for functions we would always get a 1-element list wrapper.

On the other hand, the following is a valid declaration:

int x, f(int);

Wouldn't it be weird if function definitions and declarations were modeled differently? I understand they are different in the C++ grammar, but I think it would be at least a bit surprising for users.

[eduucaldas]

clang/unittests/Tooling/Syntax/BuildTreeTest.cpp

2932–2937

Oh my god... that hurts my eyes...

I don't know what is more weird to be fair. In my view unifying both seems like a similar decision as unifying expressions and statements under the same ClangAST node because:

1. I think they have other syntactic differences.
2. I think generally people see declarations and definitions as different things. Whereas having a list in the definition of a function is completely unexpected.

Looking back at the grammar for declarations I think we would also benefit of trying to simplify it before mapping it to syntax trees. Although I would love to do that, I'm afraid there's too much on my plate already.

Should I leave a FIXME regarding this and adapt the other tests? Or do you wanna discuss this more deeply? Both options are fine for me :)

[eduucaldas]

Improve comment

[eduucaldas]

Update tests

clang/include/clang/Tooling/Syntax/Nodes.h

enum class NodeKind : uint16_t {
   SimpleDeclarator,
   ParenDeclarator,
 
   ArraySubscript,
   TrailingReturnType,
   ParametersAndQualifiers,
   MemberPointer,
   UnqualifiedId,
+
+  // Lists
+  DeclaratorList,
   ParameterDeclarationList,
   CallArguments,
-  // Nested Name Specifiers.
   NestedNameSpecifier,
+
+  // Name Specifiers.
   GlobalNameSpecifier,
   DecltypeNameSpecifier,
   IdentifierNameSpecifier,
   SimpleTemplateNameSpecifier,
 };
 /// For debugging purposes.
 raw_ostream &operator<<(raw_ostream &OS, NodeKind K);
 
enum class NodeRole : uint8_t {
   UnqualifiedId,
   Qualifier,
   SubExpression,
   Object,
   AccessToken,
   Member,
   Callee,
   Arguments,
+  Declarators
 };
 /// For debugging purposes.
 raw_ostream &operator<<(raw_ostream &OS, NodeRole R);
 
 class SimpleDeclarator;
 
 /// A root node for a translation unit. Parent is always null.
 class TranslationUnit final : public Tree {

 public:
   LinkageSpecificationDeclaration()
       : Declaration(NodeKind::LinkageSpecificationDeclaration) {}
   static bool classof(const Node *N) {
     return N->getKind() == NodeKind::LinkageSpecificationDeclaration;
   }
 };
 
+class DeclaratorList final : public List {
+public:
+  DeclaratorList() : List(NodeKind::DeclaratorList) {}
+  static bool classof(const Node *N) {
+    return N->getKind() == NodeKind::DeclaratorList;
+  }
+  std::vector<SimpleDeclarator *> getDeclarators();
+  std::vector<List::ElementAndDelimiter<syntax::SimpleDeclarator>>
+  getDeclaratorsAndCommas();
+};
+
 /// Groups multiple declarators (e.g. variables, typedefs, etc.) together. All
 /// grouped declarators share the same declaration specifiers (e.g. 'int' or
 /// 'typedef').
 class SimpleDeclaration final : public Declaration {
 public:
   SimpleDeclaration() : Declaration(NodeKind::SimpleDeclaration) {}
   static bool classof(const Node *N) {
     return N->getKind() == NodeKind::SimpleDeclaration;

clang/lib/Tooling/Syntax/BuildTree.cpp

public:
   void foldNode(llvm::ArrayRef<syntax::Token> Range, syntax::Tree *New,
                 NestedNameSpecifierLoc From) {
     assert(New);
     Pending.foldChildren(Arena, Range, New);
     if (From)
       Mapping.add(From, New);
   }
 
+  /// Populate children for \p New list, assuming it covers tokens from a
+  /// subrange of \p SuperRange.
+  void foldList(ArrayRef<syntax::Token> SuperRange, syntax::List *New,
+                ASTPtr From) {
+    assert(New);
+    auto ListRange = Pending.shrinkToFitList(SuperRange);
+    Pending.foldChildren(Arena, ListRange, New);
+    if (From)
+      Mapping.add(From, New);
+  }
+
   /// 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 assignRole(ArrayRef<syntax::Token> Range, syntax::NodeRole Role) {
       assert((std::next(It) == Trees.end() ||
               std::next(It)->first == Range.end()) &&
              "no child with the specified range");
       assert(It->second->getRole() == NodeRole::Detached &&
              "re-assigning role for a child");
       It->second->setRole(Role);
     }
 
+    /// Shrink \p Range to a subrange that only contains tokens of a list.
+    /// List elements and delimiters should already have correct roles.
+    ArrayRef<syntax::Token> shrinkToFitList(ArrayRef<syntax::Token> Range) {
+      auto BeginChildren = Trees.lower_bound(Range.begin());
+      assert((BeginChildren == Trees.end() ||
+              BeginChildren->first == Range.begin()) &&
+             "Range crosses boundaries of existing subtrees");
+
+      auto EndChildren = Trees.lower_bound(Range.end());
+      assert(
+          (EndChildren == Trees.end() || EndChildren->first == Range.end()) &&
+          "Range crosses boundaries of existing subtrees");
+
+      auto BelongsToList = [](decltype(Trees)::value_type KV) {
+        auto Role = KV.second->getRole();
+        return Role == syntax::NodeRole::ListElement ||
+               Role == syntax::NodeRole::ListDelimiter;
+      };
+
+      auto BeginListChildren =
+          std::find_if(BeginChildren, EndChildren, BelongsToList);
+
+      auto EndListChildren =
+          std::find_if_not(BeginListChildren, EndChildren, BelongsToList);
+
+      return ArrayRef<syntax::Token>(BeginListChildren->first,
+                                     EndListChildren->first);
+    }
+
     /// Add \p Node to the forest and attach child nodes based on \p Tokens.
     void foldChildren(const syntax::Arena &A, ArrayRef<syntax::Token> Tokens,
                       syntax::Tree *Node) {
       // Attach children to `Node`.
       assert(Node->getFirstChild() == nullptr && "node already has children");
 
       auto *FirstToken = Tokens.begin();
       auto BeginChildren = Trees.lower_bound(FirstToken);
private:
   /// declarator in the chain it also folds SimpleDeclaration node.
   template <class T> bool processDeclaratorAndDeclaration(T *D) {
     auto Range = getDeclaratorRange(
         Builder.sourceManager(), D->getTypeSourceInfo()->getTypeLoc(),
         getQualifiedNameStart(D), getInitializerRange(D));
 
     // There doesn't have to be a declarator (e.g. `void foo(int)` only has
     // declaration, but no declarator).
-    if (Range.getBegin().isValid()) {
-      auto *N = new (allocator()) syntax::SimpleDeclarator;
-      Builder.foldNode(Builder.getRange(Range), N, nullptr);
-      Builder.markChild(N, syntax::NodeRole::Declarator);
-    }
+    if (!Range.getBegin().isValid()) {
+      Builder.markChild(new (allocator()) syntax::DeclaratorList,
+                        syntax::NodeRole::Declarators);
+      Builder.foldNode(Builder.getDeclarationRange(D),
+                       new (allocator()) syntax::SimpleDeclaration, D);
+      return true;
+    }
+
+    Builder.markChild(N, syntax::NodeRole::ListElement);
 
-    if (Builder.isResponsibleForCreatingDeclaration(D)) {
-      Builder.foldNode(Builder.getDeclarationRange(D),
+    if (!Builder.isResponsibleForCreatingDeclaration(D)) {
+      // If this is not the last declarator in the declaration we expect a
+      // delimiter after it.
+      const auto *DelimiterToken = std::next(Builder.findToken(Range.getEnd()));
+      if (DelimiterToken->kind() == clang::tok::TokenKind::comma)
+        Builder.markChildToken(DelimiterToken, syntax::NodeRole::ListDelimiter);
+    } else {
+      auto *DL = new (allocator()) syntax::DeclaratorList;
+      auto DeclarationRange = Builder.getDeclarationRange(D);
+      Builder.foldList(DeclarationRange, DL, nullptr);
+
+      Builder.markChild(DL, syntax::NodeRole::Declarators);
+      Builder.foldNode(DeclarationRange,
                        new (allocator()) syntax::SimpleDeclaration, D);
     }
     return true;
   }
 
   /// Returns the range of the built node.
   syntax::TrailingReturnType *buildTrailingReturn(FunctionProtoTypeLoc L) {
     assert(L.getTypePtr()->hasTrailingReturn());

clang/lib/Tooling/Syntax/Nodes.cpp

raw_ostream &syntax::operator<<(raw_ostream &OS, NodeKind K) {
   case NodeKind::NestedNameSpecifier:
     return OS << "NestedNameSpecifier";
   case NodeKind::MemberExpression:
     return OS << "MemberExpression";
   case NodeKind::CallArguments:
     return OS << "CallArguments";
   case NodeKind::ParameterDeclarationList:
     return OS << "ParameterDeclarationList";
+  case NodeKind::DeclaratorList:
+    return OS << "DeclaratorList";
   }
   llvm_unreachable("unknown node kind");
 }
 
 raw_ostream &syntax::operator<<(raw_ostream &OS, NodeRole R) {
   switch (R) {
   case syntax::NodeRole::Detached:
     return OS << "Detached";
raw_ostream &syntax::operator<<(raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::AccessToken:
     return OS << "AccessToken";
   case syntax::NodeRole::Member:
     return OS << "Member";
   case syntax::NodeRole::Callee:
     return OS << "Callee";
   case syntax::NodeRole::Arguments:
     return OS << "Arguments";
+  case syntax::NodeRole::Declarators:
+    return OS << "Declarators";
   }
   llvm_unreachable("invalid role");
 }
 
 // We could have an interator in list to not pay memory costs of temporary
 // vector
 std::vector<syntax::NameSpecifier *>
 syntax::NestedNameSpecifier::getSpecifiers() {
syntax::ParameterDeclarationList::getParametersAndCommas() {
   for (const auto &ParameterAsNodeAndComma : ParametersAsNodesAndCommas) {
     Children.push_back(
         {llvm::cast<syntax::SimpleDeclaration>(ParameterAsNodeAndComma.element),
          ParameterAsNodeAndComma.delimiter});
   }
   return Children;
 }
 
+std::vector<syntax::SimpleDeclarator *>
+syntax::DeclaratorList::getDeclarators() {
+  auto DeclaratorsAsNodes = getElementsAsNodes();
+  std::vector<syntax::SimpleDeclarator *> Children;
+  for (const auto &DeclaratorAsNode : DeclaratorsAsNodes) {
+    Children.push_back(llvm::cast<syntax::SimpleDeclarator>(DeclaratorAsNode));
+  }
+  return Children;
+}
+
+std::vector<syntax::List::ElementAndDelimiter<syntax::SimpleDeclarator>>
+syntax::DeclaratorList::getDeclaratorsAndCommas() {
+  auto DeclaratorsAsNodesAndCommas = getElementsAsNodesAndDelimiters();
+  std::vector<syntax::List::ElementAndDelimiter<syntax::SimpleDeclarator>>
+      Children;
+  for (const auto &DeclaratorAsNodeAndComma : DeclaratorsAsNodesAndCommas) {
+    Children.push_back(
+        {llvm::cast<syntax::SimpleDeclarator>(DeclaratorAsNodeAndComma.element),
+         DeclaratorAsNodeAndComma.delimiter});
+  }
+  return Children;
+}
+
 syntax::Expression *syntax::MemberExpression::getObject() {
   return cast_or_null<syntax::Expression>(findChild(syntax::NodeRole::Object));
 }
 
 syntax::Leaf *syntax::MemberExpression::getTemplateKeyword() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::TemplateKeyword));
 }

clang/lib/Tooling/Syntax/Synthesis.cpp

syntax::Tree *allocateTree(syntax::Arena &A, syntax::NodeKind Kind) {
   case syntax::NodeKind::NestedNameSpecifier:
     return new (A.getAllocator()) syntax::NestedNameSpecifier;
   case syntax::NodeKind::MemberExpression:
     return new (A.getAllocator()) syntax::MemberExpression;
   case syntax::NodeKind::CallArguments:
     return new (A.getAllocator()) syntax::CallArguments;
   case syntax::NodeKind::ParameterDeclarationList:
     return new (A.getAllocator()) syntax::ParameterDeclarationList;
+  case syntax::NodeKind::DeclaratorList:
+    return new (A.getAllocator()) syntax::DeclaratorList;
   }
   llvm_unreachable("unknown node kind");
 }
 } // namespace
 
 syntax::Tree *clang::syntax::createTree(
     syntax::Arena &A,
     ArrayRef<std::pair<syntax::Node *, syntax::NodeRole>> Children,

clang/unittests/Tooling/Syntax/BuildTreeTest.cpp

EXPECT_TRUE(treeDumpEqual(
       R"cpp(
 int *a, b;
 int *c, d;
 )cpp",
       R"txt(
 TranslationUnit Detached
 |-SimpleDeclaration
 | |-'int'
-| |-SimpleDeclarator Declarator
-| | |-'*'
-| | `-'a'
-| |-','
-| |-SimpleDeclarator Declarator
-| | `-'b'
+| |-DeclaratorList Declarators
+| | |-SimpleDeclarator ListElement
+| | | |-'*'
+| | | `-'a'
+| | |-',' ListDelimiter
+| | `-SimpleDeclarator ListElement
+| |   `-'b'
 | `-';'
 `-SimpleDeclaration
   |-'int'
-  |-SimpleDeclarator Declarator
-  | |-'*'
-  | `-'c'
-  |-','
-  |-SimpleDeclarator Declarator
-  | `-'d'
+  |-DeclaratorList Declarators
+  | |-SimpleDeclarator ListElement
+  | | |-'*'
+  | | `-'c'
+  | |-',' ListDelimiter
+  | `-SimpleDeclarator ListElement
+  |   `-'d'
   `-';'
 )txt"));
 }
 
 TEST_P(BuildSyntaxTreeTest, MultipleDeclaratorsGroupingTypedef) {
   EXPECT_TRUE(treeDumpEqual(
       R"cpp(
 typedef int *a, b;
 )cpp",
       R"txt(
 TranslationUnit Detached
 `-SimpleDeclaration
   |-'typedef'
   |-'int'
-  |-SimpleDeclarator Declarator
-  | |-'*'
-  | `-'a'
-  |-','
-  |-SimpleDeclarator Declarator
-  | `-'b'
+  |-DeclaratorList Declarators
+  | |-SimpleDeclarator ListElement
+  | | |-'*'
+  | | `-'a'
+  | |-',' ListDelimiter
+  | `-SimpleDeclarator ListElement
+  |   `-'b'
   `-';'
 )txt"));
 }
 
 TEST_P(BuildSyntaxTreeTest, MultipleDeclaratorsInsideStatement) {
   EXPECT_TRUE(treeDumpEqual(
       R"cpp(
 void foo() {
   int *a, b;
   typedef int *ta, tb;
 }
 )cpp",
       R"txt(
 TranslationUnit Detached
 `-SimpleDeclaration
   |-'void'
-  |-SimpleDeclarator Declarator
-  | |-'foo'
-  | `-ParametersAndQualifiers
-  |   |-'(' OpenParen
-  |   `-')' CloseParen
+  |-DeclaratorList Declarators
+  | `-SimpleDeclarator ListElement
+  |   |-'foo'
+  |   `-ParametersAndQualifiers
+  |     |-'(' OpenParen
+  |     `-')' CloseParen
   `-CompoundStatement
     |-'{' OpenParen
     |-DeclarationStatement Statement
     | |-SimpleDeclaration
     | | |-'int'
-    | | |-SimpleDeclarator Declarator
-    | | | |-'*'
-    | | | `-'a'
-    | | |-','
-    | | `-SimpleDeclarator Declarator
-    | |   `-'b'
+    | | `-DeclaratorList Declarators
+    | |   |-SimpleDeclarator ListElement
+    | |   | |-'*'
+    | |   | `-'a'
+    | |   |-',' ListDelimiter
+    | |   `-SimpleDeclarator ListElement
+    | |     `-'b'
     | `-';'
     |-DeclarationStatement Statement
     | |-SimpleDeclaration
     | | |-'typedef'
     | | |-'int'
-    | | |-SimpleDeclarator Declarator
-    | | | |-'*'
-    | | | `-'ta'
-    | | |-','
-    | | `-SimpleDeclarator Declarator
-    | |   `-'tb'
+    | | `-DeclaratorList Declarators
+    | |   |-SimpleDeclarator ListElement
+    | |   | |-'*'
+    | |   | `-'ta'
+    | |   |-',' ListDelimiter
+    | |   `-SimpleDeclarator ListElement
+    | |     `-'tb'
     | `-';'
     `-'}' CloseParen
 )txt"));
 }
 
 TEST_P(BuildSyntaxTreeTest, SizeTTypedef) {
   if (!GetParam().isCXX11OrLater()) {
     return;