[Syntax] Build nodes for simple cases of top level declarations

[ilya-biryukov]

Summary

More complicated nodes (e.g. template declarations) will be implemented
in the follow-up patches.

[gribozavr2]

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

347

Why no semicolon, here and in other newly-added comments below? Seems like these syntax nodes cover the semicolon as implemented.

380

Isn't it a "nested name specifier" since C++17?

clang/lib/Tooling/Syntax/BuildTree.cpp

528

Why not also mark the message?

clang/unittests/Tooling/Syntax/TreeTest.cpp

517

Also add namespace a::b {} ?

692

Duplicate test? (There's one above that's exactly like this.)

[ilya-biryukov]

• Remove the duplicate test
• Add 'message' to the node for static_assert
• Handle nested namespace definitions, add them to the tests

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

347

I was torn on this...
In the statement position, this semicolon is not consumed by declarations (instead, it's consumed by DeclarationStatement). However, it is consumed at the namespace and TU level.

I've decided to punt on this until we add accessors for the semicolon and add a comment to the corresponding accessors, explaining the percularities of its placement.

Decided to keep it out from the comment, since it's not present sometimes.

Don't have a strong opinion here, can add it back

380

nested-name-specifier is a qualifier
it's actually something like <nested-name-qualifier>? <identifier>. Which is quite verbose, so decided decided to go with <name> to keep it small for now.

May have to change to something more suitable when we actually start building syntax trees for names.

Does keeping <name> make sense for now? Do you think we should be more precise from the start?

Happy to go in either direction, actually.

clang/lib/Tooling/Syntax/BuildTree.cpp

528

Good point. Done.

We don't have a node for StringLiteral, but we're returning it as <expression> for now.

clang/unittests/Tooling/Syntax/TreeTest.cpp

517

Done. This was also broken, now fixed. Thanks for bringing this up.

692

Thanks! Totally accidental, did not notice this.

[merge_guards_bot]

Build result: pass - 60626 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[ilya-biryukov]

• Do not call Builder.getRange() twice for namespaces

[merge_guards_bot]

Build result: pass - 60626 tests passed, 0 failed and 726 were skipped.

Log files: console-log.txt, CMakeCache.txt

[ilya-biryukov]

Landing as is, but happy to address any comments in the follow-up patches.
@gribozavr2, please feel free to leave any suggestions in the review comments, despite it being closed.

[gribozavr2]

Updated version LGTM, thanks!

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

347

It is fine to punt until later.

380

"name" != "identifier" so it is technically correct. Once we have accessors, they should have comments about what the actual options for the name are, and with that, I don't mind having just "name" here.

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

enum class NodeKind : uint16_t {
   BreakStatement,
   ReturnStatement,
   RangeBasedForStatement,
   ExpressionStatement,
   CompoundStatement,
 
   // Declarations
   UnknownDeclaration,
+  EmptyDeclaration,
+  StaticAssertDeclaration,
+  LinkageSpecificationDeclaration,
   SimpleDeclaration,
+  NamespaceDefinition,
+  NamespaceAliasDefinition,
+  UsingNamespaceDirective,
+  UsingDeclaration,
+  TypeAliasDeclaration
 };
 /// For debugging purposes.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, NodeKind K);
 
 /// A relation between a parent and child node, e.g. 'left-hand-side of
 /// a binary expression'. Used for implementing accessors.
 enum class NodeRole : uint8_t {
   // Roles common to multiple node kinds.
enum class NodeRole : uint8_t {
 
   // Roles specific to particular node kinds.
   CaseStatement_value,
   IfStatement_thenStatement,
   IfStatement_elseKeyword,
   IfStatement_elseStatement,
   ReturnStatement_value,
   ExpressionStatement_expression,
-  CompoundStatement_statement
+  CompoundStatement_statement,
+  StaticAssertDeclaration_condition,
+  StaticAssertDeclaration_message
 };
 /// For debugging purposes.
 llvm::raw_ostream &operator<<(llvm::raw_ostream &OS, NodeRole R);
 
 /// A root node for a translation unit. Parent is always null.
 class TranslationUnit final : public Tree {
 public:
   TranslationUnit() : Tree(NodeKind::TranslationUnit) {}

 /// correspond 1-to-1 to clang::Decl. Syntax trees distinguish between top-level
 /// declarations (e.g. namespace definitions) and declarators (e.g. variables,
 /// typedefs, etc.). Declarators are stored inside SimpleDeclaration.
 class Declaration : public Tree {
 public:
   Declaration(NodeKind K) : Tree(K) {}
   static bool classof(const Node *N) {
     return NodeKind::UnknownDeclaration <= N->kind() &&
-           N->kind() <= NodeKind::SimpleDeclaration;
+           N->kind() <= NodeKind::TypeAliasDeclaration;
   }
 };
 
 /// Declaration of an unknown kind, e.g. not yet supported in syntax trees.
 class UnknownDeclaration final : public Declaration {
 public:
   UnknownDeclaration() : Declaration(NodeKind::UnknownDeclaration) {}
   static bool classof(const Node *N) {
     return N->kind() == NodeKind::UnknownDeclaration;
   }
 };
 
+/// A semicolon in the top-level context. Does not declare anything.
+class EmptyDeclaration final : public Declaration {
+public:
+  EmptyDeclaration() : Declaration(NodeKind::EmptyDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::EmptyDeclaration;
+  }
+};
+
+/// static_assert(<condition>, <message>)
+/// static_assert(<condition>)
+class StaticAssertDeclaration final : public Declaration {
+public:
+  StaticAssertDeclaration() : Declaration(NodeKind::StaticAssertDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::StaticAssertDeclaration;
+  }
+  syntax::Expression *condition();
+  syntax::Expression *message();
+};
+
+/// extern <string-literal> declaration
+/// extern <string-literal> { <decls>  }
+class LinkageSpecificationDeclaration final : public Declaration {
+public:
+  LinkageSpecificationDeclaration()
+      : Declaration(NodeKind::LinkageSpecificationDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::LinkageSpecificationDeclaration;
+  }
+};
+
 /// 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->kind() == NodeKind::SimpleDeclaration;
   }
 };
+
+/// namespace <name> { <decls> }
+class NamespaceDefinition final : public Declaration {
+public:
+  NamespaceDefinition() : Declaration(NodeKind::NamespaceDefinition) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::NamespaceDefinition;
+  }
+};
+
+/// namespace <name> = <namespace-reference>
+class NamespaceAliasDefinition final : public Declaration {
+public:
+  NamespaceAliasDefinition()
+      : Declaration(NodeKind::NamespaceAliasDefinition) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::NamespaceAliasDefinition;
+  }
+};
+
+/// using namespace <name>
+class UsingNamespaceDirective final : public Declaration {
+public:
+  UsingNamespaceDirective() : Declaration(NodeKind::UsingNamespaceDirective) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::UsingNamespaceDirective;
+  }
+};
+
+/// using <scope>::<name>
+/// using typename <scope>::<name>
+class UsingDeclaration final : public Declaration {
+public:
+  UsingDeclaration() : Declaration(NodeKind::UsingDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::UsingDeclaration;
+  }
+};
+
+/// using <name> = <type>
+class TypeAliasDeclaration final : public Declaration {
+public:
+  TypeAliasDeclaration() : Declaration(NodeKind::TypeAliasDeclaration) {}
+  static bool classof(const Node *N) {
+    return N->kind() == NodeKind::TypeAliasDeclaration;
+  }
+};
+
 } // namespace syntax
 } // namespace clang
 #endif

clang/lib/Tooling/Syntax/BuildTree.cpp

private:
     std::map<const syntax::Token *, DelayedFold> DelayedFolds;
   };
 
   /// For debugging purposes.
   std::string str() { return Pending.str(Arena); }
 
   syntax::Arena &Arena;
   Forest Pending;
-  llvm::DenseSet<Decl*> DeclsWithoutSemicolons;
+  llvm::DenseSet<Decl *> DeclsWithoutSemicolons;
 };
 
 namespace {
 class BuildTreeVisitor : public RecursiveASTVisitor<BuildTreeVisitor> {
 public:
   explicit BuildTreeVisitor(ASTContext &Ctx, syntax::TreeBuilder &Builder)
       : Builder(Builder), LangOpts(Ctx.getLangOpts()) {}
 
public:
   // Some expressions are not yet handled by syntax trees.
   bool WalkUpFromExpr(Expr *E) {
     assert(!isImplicitExpr(E) && "should be handled by TraverseStmt");
     Builder.foldNode(Builder.getExprRange(E),
                      new (allocator()) syntax::UnknownExpression);
     return true;
   }
 
+  bool WalkUpFromNamespaceDecl(NamespaceDecl *S) {
+    auto Tokens = Builder.getRange(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(Builder.getRange(S),
+                     new (allocator()) syntax::NamespaceDefinition);
+    return true;
+  }
+
   // The code below is very regular, it could even be generated with some
   // preprocessor magic. We merely assign roles to the corresponding children
   // and fold resulting nodes.
   bool WalkUpFromDeclStmt(DeclStmt *S) {
     Builder.foldNode(Builder.getStmtRange(S),
                      new (allocator()) syntax::DeclarationStatement);
     return true;
   }
public:
   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);
     return true;
   }
 
+  bool WalkUpFromEmptyDecl(EmptyDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::EmptyDeclaration);
+    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.getRange(S),
+                     new (allocator()) syntax::StaticAssertDeclaration);
+    return true;
+  }
+
+  bool WalkUpFromLinkageSpecDecl(LinkageSpecDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::LinkageSpecificationDeclaration);
+    return true;
+  }
+
+  bool WalkUpFromNamespaceAliasDecl(NamespaceAliasDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::NamespaceAliasDefinition);
+    return true;
+  }
+
+  bool WalkUpFromUsingDirectiveDecl(UsingDirectiveDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::UsingNamespaceDirective);
+    return true;
+  }
+
+  bool WalkUpFromUsingDecl(UsingDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::UsingDeclaration);
+    return true;
+  }
+
+  bool WalkUpFromUnresolvedUsingValueDecl(UnresolvedUsingValueDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::UsingDeclaration);
+    return true;
+  }
+
+  bool WalkUpFromUnresolvedUsingTypenameDecl(UnresolvedUsingTypenameDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::UsingDeclaration);
+    return true;
+  }
+
+  bool WalkUpFromTypeAliasDecl(TypeAliasDecl *S) {
+    Builder.foldNode(Builder.getRange(S),
+                     new (allocator()) syntax::TypeAliasDeclaration);
+    return true;
+  }
+
 private:
   /// A small helper to save some typing.
   llvm::BumpPtrAllocator &allocator() { return Builder.allocator(); }
 
   syntax::TreeBuilder &Builder;
   const LangOptions &LangOpts;
 };
 } // namespace
Pending.assignRole(getExprRange(E),
                        NodeRole::ExpressionStatement_expression);
     // (!) 'getRange(Stmt)' ensures this already covers a trailing semicolon.
     Pending.foldChildren(Range, new (allocator()) syntax::ExpressionStatement);
   }
   Pending.assignRole(Range, Role);
 }
 
 void syntax::TreeBuilder::markExprChild(Expr *Child, NodeRole Role) {
+  if (!Child)
+    return;
+
   Pending.assignRole(getExprRange(Child), Role);
 }
 
 const syntax::Token *syntax::TreeBuilder::findToken(SourceLocation L) const {
   auto Tokens = Arena.tokenBuffer().expandedTokens();
   auto &SM = Arena.sourceManager();
   auto It = llvm::partition_point(Tokens, [&](const syntax::Token &T) {
     return SM.isBeforeInTranslationUnit(T.location(), L);

clang/lib/Tooling/Syntax/Nodes.cpp

llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeKind K) {
   case NodeKind::RangeBasedForStatement:
     return OS << "RangeBasedForStatement";
   case NodeKind::ExpressionStatement:
     return OS << "ExpressionStatement";
   case NodeKind::CompoundStatement:
     return OS << "CompoundStatement";
   case NodeKind::UnknownDeclaration:
     return OS << "UnknownDeclaration";
+  case NodeKind::EmptyDeclaration:
+    return OS << "EmptyDeclaration";
+  case NodeKind::StaticAssertDeclaration:
+    return OS << "StaticAssertDeclaration";
+  case NodeKind::LinkageSpecificationDeclaration:
+    return OS << "LinkageSpecificationDeclaration";
   case NodeKind::SimpleDeclaration:
     return OS << "SimpleDeclaration";
+  case NodeKind::NamespaceDefinition:
+    return OS << "NamespaceDefinition";
+  case NodeKind::NamespaceAliasDefinition:
+    return OS << "NamespaceAliasDefinition";
+  case NodeKind::UsingNamespaceDirective:
+    return OS << "UsingNamespaceDirective";
+  case NodeKind::UsingDeclaration:
+    return OS << "UsingDeclaration";
+  case NodeKind::TypeAliasDeclaration:
+    return OS << "TypeAliasDeclaration";
   }
   llvm_unreachable("unknown node kind");
 }
 
 llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeRole R) {
   switch (R) {
   case syntax::NodeRole::Detached:
     return OS << "Detached";
llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::IfStatement_elseStatement:
     return OS << "IfStatement_elseStatement";
   case syntax::NodeRole::ReturnStatement_value:
     return OS << "ReturnStatement_value";
   case syntax::NodeRole::ExpressionStatement_expression:
     return OS << "ExpressionStatement_expression";
   case syntax::NodeRole::CompoundStatement_statement:
     return OS << "CompoundStatement_statement";
+  case syntax::NodeRole::StaticAssertDeclaration_condition:
+    return OS << "StaticAssertDeclaration_condition";
+  case syntax::NodeRole::StaticAssertDeclaration_message:
+    return OS << "StaticAssertDeclaration_message";
   }
   llvm_unreachable("invalid role");
 }
 
 syntax::Leaf *syntax::SwitchStatement::switchKeyword() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::IntroducerKeyword));
 }
std::vector<syntax::Statement *> syntax::CompoundStatement::statements() {
   }
   return Children;
 }
 
 syntax::Leaf *syntax::CompoundStatement::rbrace() {
   return llvm::cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::CloseParen));
 }
+
+syntax::Expression *syntax::StaticAssertDeclaration::condition() {
+  return llvm::cast_or_null<syntax::Expression>(
+      findChild(syntax::NodeRole::StaticAssertDeclaration_condition));
+}
+
+syntax::Expression *syntax::StaticAssertDeclaration::message() {
+  return llvm::cast_or_null<syntax::Expression>(
+      findChild(syntax::NodeRole::StaticAssertDeclaration_message));
+}

clang/unittests/Tooling/Syntax/TreeTest.cpp

`-CompoundStatement
     | | |-typedef
     | | |-int
     | | |-*
     | | |-ta
     | | |-,
     | | `-tb
     | `-;
     `-}
-  )txt"}};
+  )txt"},
+      {R"cpp(
+namespace a { namespace b {} }
+namespace a::b {}
+namespace {}
+
+namespace foo = a;
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-NamespaceDefinition
+| |-namespace
+| |-a
+| |-{
+| |-NamespaceDefinition
+| | |-namespace
+| | |-b
+| | |-{
+| | `-}
+| `-}
+|-NamespaceDefinition
+| |-namespace
+| |-a
+| |-::
+| |-b
+| |-{
+| `-}
+|-NamespaceDefinition
+| |-namespace
+| |-{
+| `-}
+`-NamespaceAliasDefinition
+  |-namespace
+  |-foo
+  |-=
+  |-a
+  `-;
+)txt"},
+      {R"cpp(
+namespace ns {}
+using namespace ::ns;
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-NamespaceDefinition
+| |-namespace
+| |-ns
+| |-{
+| `-}
+`-UsingNamespaceDirective
+  |-using
+  |-namespace
+  |-::
+  |-ns
+  `-;
+       )txt"},
+      {R"cpp(
+namespace ns { int a; }
+using ns::a;
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-NamespaceDefinition
+| |-namespace
+| |-ns
+| |-{
+| |-SimpleDeclaration
+| | |-int
+| | |-a
+| | `-;
+| `-}
+`-UsingDeclaration
+  |-using
+  |-ns
+  |-::
+  |-a
+  `-;
+       )txt"},
+      {R"cpp(
+template <class T> struct X {
+  using T::foo;
+  using typename T::bar;
+};
+    )cpp",
+       R"txt(
+*: TranslationUnit
+`-UnknownDeclaration
+  |-template
+  |-<
+  |-UnknownDeclaration
+  | |-class
+  | `-T
+  |->
+  |-struct
+  |-X
+  |-{
+  |-UsingDeclaration
+  | |-using
+  | |-T
+  | |-::
+  | |-foo
+  | `-;
+  |-UsingDeclaration
+  | |-using
+  | |-typename
+  | |-T
+  | |-::
+  | |-bar
+  | `-;
+  |-}
+  `-;
+       )txt"},
+      {R"cpp(
+using type = int;
+    )cpp",
+       R"txt(
+*: TranslationUnit
+`-TypeAliasDeclaration
+  |-using
+  |-type
+  |-=
+  |-int
+  `-;
+       )txt"},
+      {R"cpp(
+;
+    )cpp",
+       R"txt(
+*: TranslationUnit
+`-EmptyDeclaration
+  `-;
+       )txt"},
+      {R"cpp(
+static_assert(true, "message");
+static_assert(true);
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-StaticAssertDeclaration
+| |-static_assert
+| |-(
+| |-UnknownExpression
+| | `-true
+| |-,
+| |-UnknownExpression
+| | `-"message"
+| |-)
+| `-;
+`-StaticAssertDeclaration
+  |-static_assert
+  |-(
+  |-UnknownExpression
+  | `-true
+  |-)
+  `-;
+       )txt"},
+      {R"cpp(
+extern "C" int a;
+extern "C" { int b; int c; }
+    )cpp",
+       R"txt(
+*: TranslationUnit
+|-LinkageSpecificationDeclaration
+| |-extern
+| |-"C"
+| `-SimpleDeclaration
+|   |-int
+|   |-a
+|   `-;
+`-LinkageSpecificationDeclaration
+  |-extern
+  |-"C"
+  |-{
+  |-SimpleDeclaration
+  | |-int
+  | |-b
+  | `-;
+  |-SimpleDeclaration
+  | |-int
+  | |-c
+  | `-;
+  `-}
+       )txt"},
+  };
 
   for (const auto &T : Cases) {
     SCOPED_TRACE(T.first);
 
     auto *Root = buildTree(T.first);
     std::string Expected = llvm::StringRef(T.second).trim().str();
     std::string Actual = llvm::StringRef(Root->dump(*Arena)).trim();
     EXPECT_EQ(Expected, Actual) << "the resulting dump is:\n" << Actual;
   }
 }
 } // namespace