[Syntax] Start to move trivial Node class definitions to TableGen. NFC

[sammccall]

Summary

This defines two node archetypes with trivial class definitions:

• Alternatives: the generated abstract classes are trivial as all functionality is via LLVM RTTI
• Unconstrained: this is a placeholder, I think all of these are going to be Lists but today they have no special accessors etc, so we just say "could contain anything", and migrate them one-by-one to Sequence later.

Compared to Dmitri's prototype, Nodes.td looks more like a class hierarchy and
less like a grammar. (E.g. variants list the Alternatives parent rather than
vice versa).
The main reasons for this:

• the hierarchy is an important part of the API we want direct control over.
  • e.g. we may introduce abstract bases like "loop" that the grammar doesn't care about in order to model is-a concepts that might make refactorings more expressive. This is less natural in a grammar-like idiom.
  • e.g. we're likely to have to model some alternatives as variants and others as class hierarchies, the choice will probably be based on natural is-a relationships.
• it reduces the cognitive load of switching from editing *.td to working with code that uses the generated classes

[sammccall]

There are *lots* more nodes that can be converted here, I'll wait to review the pattern first :-)

The generated code is identical to the deleted code, except the constructor for abstract classes is protected now.

[gribozavr2]

e.g. we may introduce abstract bases like "loop" that the grammar doesn't care about in order to model is-a concepts that might make refactorings more expressive. This is less natural in a grammar-like idiom.

Loop can be an alternative rule in the grammar, I'm not sure what is less natural about it:

Statement ::=
  IfStatement | LoopStatement | BreakStatement | ...

LoopStatement ::=
  ForLoopStatement | WhileLoopStatement | ...

clang/include/clang/Tooling/Syntax/Syntax.td

35

I think it would be best to make documentation mandatory, and for nodes that are currently lacking it, add a FIXME so that we clearly see where the tech debt is.

47

+

It corresponds to an alternative rule in the grammar, for example:
Statement ::=
  IfStatement | ForStatement | ...

`Statement` should be modeled with `Alternatives<>`. `IfStatement` and `ForStatement` are derived from `Statement`.
``

clang/utils/TableGen/ClangSyntaxEmitter.cpp

149–150

[eduucaldas]

Compared to Dmitri's prototype, Nodes.td looks more like a class hierarchy and
less like a grammar. (E.g. variants list the Alternatives parent rather than
vice versa).

e.g. we may introduce abstract bases like "loop" that the grammar doesn't care about in order to model is-a concepts that might make refactorings more expressive. This is less natural in a grammar-like idiom.

Do you have a concrete example of such abstract base -- loop is in the grammar ? And in the case such an example appear, in my mind we would just change "our grammar" to have an alternative for this "loop" abstract base.

e.g. we're likely to have to model some alternatives as variants and others as class hierarchies, the choice will probably be based on natural is-a relationships.

I agree, alternatives and the two ways to model them are a tricky subject...

it reduces the cognitive load of switching from editing *.td to working with code that uses the generated classes

I think we should consider reading prior to editing.
A grammar is how we represent syntax, and syntax trees model syntax, as such I think we should rather consider the cognitive load of switching between the grammar and the definition of syntax trees.

I have a lot to improve in my writing skills, so I don't know if I could express all my thoughts. We could have a call if you want ;)

[sammccall]

In D90543#2373962, @eduucaldas wrote:

Compared to Dmitri's prototype, Nodes.td looks more like a class hierarchy and
less like a grammar. (E.g. variants list the Alternatives parent rather than
vice versa).

e.g. we may introduce abstract bases like "loop" that the grammar doesn't care about in order to model is-a concepts that might make refactorings more expressive. This is less natural in a grammar-like idiom.

Do you have a concrete example of such abstract base -- loop is in the grammar ? And in the case such an example appear, in my mind we would just change "our grammar" to have an alternative for this "loop" abstract base.

Not really, I think you're right. This is a bad argument.

e.g. we're likely to have to model some alternatives as variants and others as class hierarchies, the choice will probably be based on natural is-a relationships.

I agree, alternatives and the two ways to model them are a tricky subject...

it reduces the cognitive load of switching from editing *.td to working with code that uses the generated classes

I think we should consider reading prior to editing.

Agree. I think the same load exists for reading though.

A grammar is how we represent syntax, and syntax trees model syntax, as such I think we should rather consider the cognitive load of switching between the grammar and the definition of syntax trees.

I don't think people reason about concrete grammar as a collection of productions though, rather as a collection of kinds of nodes and what they're composed of.
And we model it that way in the C++ API! I think the tablegen should follow that too...

[sammccall]

Address comments, rebase

clang/include/clang/Tooling/Syntax/CMakeLists.txt

 clang_tablegen(Nodes.inc -gen-clang-syntax-node-list
   SOURCE Nodes.td
   TARGET ClangSyntaxNodeList)
 
+clang_tablegen(NodeClasses.inc -gen-clang-syntax-node-classes
+  SOURCE Nodes.td
+  TARGET ClangSyntaxNodeClasses)

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

enum class NodeRole : uint8_t {
   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:
-  TranslationUnit() : Tree(NodeKind::TranslationUnit) {}
-  static bool classof(const Node *N);
-};
-
-/// A base class for all expressions. Note that expressions are not statements,
-/// even though they are in clang.
-class Expression : public Tree {
-public:
-  Expression(NodeKind K) : Tree(K) {}
-  static bool classof(const Node *N);
-};
-
-/// A sequence of these specifiers make a `nested-name-specifier`.
-/// e.g. the `std` or `vector<int>` in `std::vector<int>::size`.
-class NameSpecifier : public Tree {
-public:
-  NameSpecifier(NodeKind K) : Tree(K) {}
-  static bool classof(const Node *N);
-};
-
-/// The global namespace name specifier, this specifier doesn't correspond to a
-/// token instead an absence of tokens before a `::` characterizes it, in
-/// `::std::vector<int>` it would be characterized by the absence of a token
-/// before the first `::`
-class GlobalNameSpecifier final : public NameSpecifier {
-public:
-  GlobalNameSpecifier() : NameSpecifier(NodeKind::GlobalNameSpecifier) {}
-  static bool classof(const Node *N);
-};
-
-/// A name specifier holding a decltype, of the form: `decltype ( expression ) `
-/// e.g. the `decltype(s)` in `decltype(s)::size`.
-class DecltypeNameSpecifier final : public NameSpecifier {
-public:
-  DecltypeNameSpecifier() : NameSpecifier(NodeKind::DecltypeNameSpecifier) {}
-  static bool classof(const Node *N);
-};
-
-/// A identifier name specifier, of the form `identifier`
-/// e.g. the `std` in `std::vector<int>::size`.
-class IdentifierNameSpecifier final : public NameSpecifier {
-public:
-  IdentifierNameSpecifier()
-      : NameSpecifier(NodeKind::IdentifierNameSpecifier) {}
-  static bool classof(const Node *N);
-};
-
-/// A name specifier with a simple-template-id, of the form `template_opt
-/// identifier < template-args >` e.g. the `vector<int>` in
-/// `std::vector<int>::size`.
-class SimpleTemplateNameSpecifier final : public NameSpecifier {
-public:
-  SimpleTemplateNameSpecifier()
-      : NameSpecifier(NodeKind::SimpleTemplateNameSpecifier) {}
-  static bool classof(const Node *N);
-};
+#include "clang/Tooling/Syntax/NodeClasses.inc"
 
 /// Models a `nested-name-specifier`. C++ [expr.prim.id.qual]
 /// e.g. the `std::vector<int>::` in `std::vector<int>::size`.
 class NestedNameSpecifier final : public List {
 public:
   NestedNameSpecifier() : List(NodeKind::NestedNameSpecifier) {}
   static bool classof(const Node *N);
   std::vector<NameSpecifier *> getSpecifiers();

clang/include/clang/Tooling/Syntax/Nodes.td

 // The C++ classes for the archetypes themselves are written by hand, and the
 // concrete node classes will be generated. Migration to TableGen is not
 // complete, so currently there is a mix of generated and hand-authored code.
 //
 //===----------------------------------------------------------------------===//
 
 include "clang/Tooling/Syntax/Syntax.td"
 
-def Node : External<?> {}
-def Leaf : External<Node> {}
-def Tree : External<Node> {}
-
-def TranslationUnit : External<Tree> {}
-
-def Expression : External<Tree> {}
+def TranslationUnit : Unconstrained {
+  let documentation = [{
+    A root node for a translation unit. Parent is always null.
+  }];
+}
+
+def Expression : Alternatives {
+  let documentation = [{
+    A base class for all expressions. Note that expressions are not statements,
+    even though they are in clang.
+  }];
+}
 def UnknownExpression : External<Expression> {}
 def UnaryOperatorExpression : External<Tree> {}
 def PrefixUnaryOperatorExpression : External<UnaryOperatorExpression> {}
 def PostfixUnaryOperatorExpression : External<UnaryOperatorExpression> {}
 def BinaryOperatorExpression : External<Expression> {}
 def ParenExpression : External<Expression> {}
 def LiteralExpression : External<Expression> {}
 def IntegerLiteralExpression : External<LiteralExpression> {}

 // Lists
 def List : External<Tree> {}
 def DeclaratorList : External<List> {}
 def ParameterDeclarationList : External<List> {}
 def CallArguments : External<List> {}
 def NestedNameSpecifier : External<List> {}
 
 // Name Specifiers.
-def NameSpecifier : External<Tree> {}
-def GlobalNameSpecifier : External<NameSpecifier> {}
-def DecltypeNameSpecifier : External<NameSpecifier> {}
-def IdentifierNameSpecifier : External<NameSpecifier> {}
-def SimpleTemplateNameSpecifier : External<NameSpecifier> {}
+def NameSpecifier : Alternatives {
+  let documentation = [{
+    A sequence of these specifiers make a `nested-name-specifier`.
+    e.g. the `std` or `vector<int>` in `std::vector<int>::size`.
+  }];
+}
+def GlobalNameSpecifier : Unconstrained<NameSpecifier> {
+  let documentation = [{
+    The global namespace name specifier, this specifier doesn't correspond to a
+    token instead an absence of tokens before a `::` characterizes it, in
+    `::std::vector<int>` it would be characterized by the absence of a token
+    before the first `::`
+  }];
+}
+def DecltypeNameSpecifier : Unconstrained<NameSpecifier> {
+  let documentation = [{
+    A name specifier holding a decltype, of the form: `decltype ( expression ) `
+    e.g. the `decltype(s)` in `decltype(s)::size`.
+  }];
+}
+def IdentifierNameSpecifier : Unconstrained<NameSpecifier> {
+  let documentation = [{
+    A identifier name specifier, of the form `identifier`
+    e.g. the `std` in `std::vector<int>::size`.
+  }];
+}
+def SimpleTemplateNameSpecifier : Unconstrained<NameSpecifier> {
+  let documentation = [{
+    A name specifier with a simple-template-id, of the form `template_opt
+    identifier < template-args >` e.g. the `vector<int>` in
+    `std::vector<int>::size`.
+  }];
+}

clang/include/clang/Tooling/Syntax/Syntax.td

 // complete, so currently there is a mix of generated and hand-authored code.
 //
 //===----------------------------------------------------------------------===//
 
 // Defs derived from NodeType correspond to syntax tree node types.
 class NodeType {
   // The NodeType that this node is derived from in the Node class hierarchy.
   NodeType base = ?;
+  // Documentation for this Node subclass.
+  string documentation;
 }
 
 // A node type which is defined in Nodes.h rather than by generated code.
 // We merely specify the inheritance hierarchy here.
 class External<NodeType base_> : NodeType { let base = base_; }
 
-// FIXME: add sequence, list, and alternative archetypes.
+// Special nodes defined here.
+def Node : External<?> {}
+def Leaf : External<Node> {}
+def Tree : External<Node> {}
+
+// An abstract node type which merely serves as a base for more specific types.
+//
+// This corresponds to an alternative rule in the grammar, such as:
+//   Statement = IfStatement | ForStatement | ...
+// Statement is modeled using Alternatives, and IfStatement.base is Statement.
+class Alternatives<NodeType base_ = Tree> : NodeType { let base = base_; }
+
+// A node type which may contain anything and has no specific accessors.
+// These are generally placeholders for a more precise implementation.
+class Unconstrained<NodeType base_ = Tree> : NodeType { let base = base_; }
+
+// FIXME: add sequence and list archetypes.

clang/utils/TableGen/ClangSyntaxEmitter.cpp

 // These backends consume the definitions of Syntax Tree nodes.
 // See clang/include/clang/Tooling/Syntax/{Syntax,Nodes}.td
 //
 // The -gen-clang-syntax-node-list backend produces a .inc with macro calls
 //   NODE(Kind, BaseKind)
 //   ABSTRACT_NODE(Type, Base, FirstKind, LastKind)
 // similar to those for AST nodes such as AST/DeclNodes.inc.
 //
-// In future, the class definitions will be produced by additional backends.
+// The -gen-clang-syntax-node-classes backend produces definitions for the
+// syntax::Node subclasses (except those marked as External).
+//
+// In future, another backend will encode the structure of the various node
+// types in tables so their invariants can be checked and enforced.
 //
 //===----------------------------------------------------------------------===//
 #include "TableGenBackends.h"
 
 #include <deque>
 
+#include "llvm/ADT/StringExtras.h"
 #include "llvm/Support/FormatVariadic.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/TableGen/Record.h"
 #include "llvm/TableGen/TableGenBackend.h"
 
 namespace {
+using llvm::formatv;
 
 // The class hierarchy of Node types.
 // We assemble this in order to be able to define the NodeKind enum in a
 // stable and useful way, where abstract Node subclasses correspond to ranges.
 class Hierarchy {
 public:
   Hierarchy(const llvm::RecordKeeper &Records) {
     for (llvm::Record *T : Records.getAllDerivedDefinitions("NodeType"))
       add(T);
     for (llvm::Record *Derived : Records.getAllDerivedDefinitions("NodeType"))
       if (llvm::Record *Base = Derived->getValueAsOptionalDef("base"))
         link(Derived, Base);
-    for (NodeType &N : AllTypes)
+    for (NodeType &N : AllTypes) {
       llvm::sort(N.Derived, [](const NodeType *L, const NodeType *R) {
         return L->Record->getName() < R->Record->getName();
       });
+      // Alternatives nodes must have subclasses, External nodes may do.
+      assert(N.Record->isSubClassOf("Alternatives") ||
+             N.Record->isSubClassOf("External") || N.Derived.empty());
+      assert(!N.Record->isSubClassOf("Alternatives") || !N.Derived.empty());
+    }
   }
 
   struct NodeType {
     const llvm::Record *Record = nullptr;
     const NodeType *Base = nullptr;
     std::vector<const NodeType *> Derived;
     llvm::StringRef name() const { return Record->getName(); }
   };
 
   NodeType &get(llvm::StringRef Name = "Node") {
     auto NI = ByName.find(Name);
     assert(NI != ByName.end() && "no such node");
     return *NI->second;
   }
 
+  // Traverse the hierarchy in pre-order (base classes before derived).
+  void visit(llvm::function_ref<void(const NodeType &)> CB,
+             const NodeType *Start = nullptr) {
+    if (Start == nullptr)
+      Start = &get();
+    CB(*Start);
+    for (const NodeType *D : Start->Derived)
+      visit(CB, D);
+  }
+
 private:
   void add(const llvm::Record *R) {
     AllTypes.emplace_back();
     AllTypes.back().Record = R;
     bool Inserted = ByName.try_emplace(R->getName(), &AllTypes.back()).second;
     assert(Inserted && "Duplicate node name");
     (void)Inserted;
   }

 
 const Hierarchy::NodeType &firstConcrete(const Hierarchy::NodeType &N) {
   return N.Derived.empty() ? N : firstConcrete(*N.Derived.front());
 }
 const Hierarchy::NodeType &lastConcrete(const Hierarchy::NodeType &N) {
   return N.Derived.empty() ? N : lastConcrete(*N.Derived.back());
 }
 
-void emitNodeList(const Hierarchy::NodeType &N, llvm::raw_ostream &OS) {
-  // Don't emit ABSTRACT_NODE for node itself, which has no parent.
-  if (N.Base != nullptr) {
-    if (N.Derived.empty())
-      OS << llvm::formatv("CONCRETE_NODE({0},{1})\n", N.name(), N.Base->name());
-    else
-      OS << llvm::formatv("ABSTRACT_NODE({0},{1},{2},{3})\n", N.name(),
-                          N.Base->name(), firstConcrete(N).name(),
-                          lastConcrete(N).name());
-  }
-  for (const auto *C : N.Derived)
-    emitNodeList(*C, OS);
-}
-
 } // namespace
 
 void clang::EmitClangSyntaxNodeList(llvm::RecordKeeper &Records,
                                     llvm::raw_ostream &OS) {
   llvm::emitSourceFileHeader("Syntax tree node list", OS);
-  OS << "// Generated from " << Records.getInputFilename() << "\n";
+  Hierarchy H(Records);
   OS << R"cpp(
 #ifndef NODE
 #define NODE(Kind, Base)
 #endif
 
 #ifndef CONCRETE_NODE
 #define CONCRETE_NODE(Kind, Base) NODE(Kind, Base)
 #endif
 
 #ifndef ABSTRACT_NODE
 #define ABSTRACT_NODE(Kind, Base, First, Last) NODE(Kind, Base)
 #endif
 
 )cpp";
-  emitNodeList(Hierarchy(Records).get(), OS);
+  H.visit([&](const Hierarchy::NodeType &N) {
+    // Don't emit ABSTRACT_NODE for node itself, which has no parent.
+    if (N.Base == nullptr)
+      return;
+    if (N.Derived.empty())
+      OS << formatv("CONCRETE_NODE({0},{1})\n", N.name(), N.Base->name());
+    else
+      OS << formatv("ABSTRACT_NODE({0},{1},{2},{3})\n", N.name(),
+                    N.Base->name(), firstConcrete(N).name(),
+                    lastConcrete(N).name());
+  });
   OS << R"cpp(
 #undef NODE
 #undef CONCRETE_NODE
 #undef ABSTRACT_NODE
 )cpp";
 }
+
+// Format a documentation string as a C++ comment.
+// Trims leading whitespace handling since comments come from a TableGen file:
+//    documentation = [{
+//      This is a widget. Example:
+//        widget.explode()
+//    }];
+// and should be formatted as:
+//    /// This is a widget. Example:
+//    ///   widget.explode()
+// Leading and trailing whitespace lines are stripped.
+// The indentation of the first line is stripped from all lines.
+static void printDoc(llvm::StringRef Doc, llvm::raw_ostream &OS) {
+  Doc = Doc.rtrim();
+  llvm::StringRef Line;
+  while (Line.trim().empty() && !Doc.empty())
+    std::tie(Line, Doc) = Doc.split('\n');
+  llvm::StringRef Indent = Line.take_while(llvm::isSpace);
+  for (; !Line.empty() || !Doc.empty(); std::tie(Line, Doc) = Doc.split('\n')) {
+    Line.consume_front(Indent);
+    OS << "/// " << Line << "\n";
+  }
+}
+
+void clang::EmitClangSyntaxNodeClasses(llvm::RecordKeeper &Records,
+                                       llvm::raw_ostream &OS) {
+  llvm::emitSourceFileHeader("Syntax tree node list", OS);
+  Hierarchy H(Records);
+
+  OS << "\n// Forward-declare node types so we don't have to carefully "
+        "sequence definitions.\n";
+  H.visit([&](const Hierarchy::NodeType &N) {
+    OS << "class " << N.name() << ";\n";
+  });
+
+  OS << "\n// Node definitions\n\n";
+  H.visit([&](const Hierarchy::NodeType &N) {
+    if (N.Record->isSubClassOf("External"))
+      return;
+    printDoc(N.Record->getValueAsString("documentation"), OS);
+    OS << formatv("class {0}{1} : public {2} {{\n", N.name(),
+                  N.Derived.empty() ? " final" : "", N.Base->name());
+
+    // Constructor.
+    if (N.Derived.empty())
+      OS << formatv("public:\n  {0}() : {1}(NodeKind::{0}) {{}\n", N.name(),
+                    N.Base->name());
+    else
+      OS << formatv("protected:\n  {0}(NodeKind K) : {1}(K) {{}\npublic:\n",
+                    N.name(), N.Base->name());
+
+    // classof. FIXME: move definition inline once ~all nodes are generated.
+    OS << "  static bool classof(const Node *N);\n";
+
+    OS << "};\n\n";
+  });
+}

clang/utils/TableGen/TableGen.cpp

enum ActionType {
   GenClangDeclNodes,
   GenClangStmtNodes,
   GenClangTypeNodes,
   GenClangTypeReader,
   GenClangTypeWriter,
   GenClangOpcodes,
   GenClangSACheckers,
   GenClangSyntaxNodeList,
+  GenClangSyntaxNodeClasses,
   GenClangCommentHTMLTags,
   GenClangCommentHTMLTagsProperties,
   GenClangCommentHTMLNamedCharacterReferences,
   GenClangCommentCommandInfo,
   GenClangCommentCommandList,
   GenClangOpenCLBuiltins,
   GenArmNeon,
   GenArmFP16,
cl::values(
         clEnumValN(GenClangTypeWriter, "gen-clang-type-writer",
                    "Generate Clang AbstractTypeWriter class"),
         clEnumValN(GenClangOpcodes, "gen-clang-opcodes",
                    "Generate Clang constexpr interpreter opcodes"),
         clEnumValN(GenClangSACheckers, "gen-clang-sa-checkers",
                    "Generate Clang Static Analyzer checkers"),
         clEnumValN(GenClangSyntaxNodeList, "gen-clang-syntax-node-list",
                    "Generate list of Clang Syntax Tree node types"),
+        clEnumValN(GenClangSyntaxNodeClasses, "gen-clang-syntax-node-classes",
+                   "Generate definitions of Clang Syntax Tree node clasess"),
         clEnumValN(GenClangCommentHTMLTags, "gen-clang-comment-html-tags",
                    "Generate efficient matchers for HTML tag "
                    "names that are used in documentation comments"),
         clEnumValN(GenClangCommentHTMLTagsProperties,
                    "gen-clang-comment-html-tags-properties",
                    "Generate efficient matchers for HTML tag "
                    "properties"),
         clEnumValN(GenClangCommentHTMLNamedCharacterReferences,
case GenClangCommentCommandList:
     EmitClangCommentCommandList(Records, OS);
     break;
   case GenClangOpenCLBuiltins:
     EmitClangOpenCLBuiltins(Records, OS);
     break;
   case GenClangSyntaxNodeList:
     EmitClangSyntaxNodeList(Records, OS);
     break;
+  case GenClangSyntaxNodeClasses:
+    EmitClangSyntaxNodeClasses(Records, OS);
+    break;
   case GenArmNeon:
     EmitNeon(Records, OS);
     break;
   case GenArmFP16:
     EmitFP16(Records, OS);
     break;
   case GenArmBF16:
     EmitBF16(Records, OS);

clang/utils/TableGen/TableGenBackends.h

 void EmitClangCommentCommandInfo(llvm::RecordKeeper &Records,
                                  llvm::raw_ostream &OS);
 void EmitClangCommentCommandList(llvm::RecordKeeper &Records,
                                  llvm::raw_ostream &OS);
 void EmitClangOpcodes(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 
 void EmitClangSyntaxNodeList(llvm::RecordKeeper &Records,
                              llvm::raw_ostream &OS);
+void EmitClangSyntaxNodeClasses(llvm::RecordKeeper &Records,
+                                llvm::raw_ostream &OS);
 
 void EmitNeon(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitFP16(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitBF16(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonSema(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonTest(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeon2(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);
 void EmitNeonSema2(llvm::RecordKeeper &Records, llvm::raw_ostream &OS);