[Syntax] Tablegen Sequence classes. NFC

[sammccall]

Summary

Similar to the previous patch, this doesn't convert *all* the classes that
could be converted. It also doesn't enforce any new invariants etc.

It *does* include some data we don't use yet: specific token types that are
allowed and optional/required status of sequence items. (Similar to Dmitri's
prototype). I think these are easier to add as we go than later, and serve
a useful documentation purpose.

[sammccall]

Again, the generated code is identical to the code being deleted apart from formatting and the fact that methods are defined inline.

[gribozavr2]

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

123

The reason why in my prototype the grammar rules are separate is to allow expressing rules that depend on each other in a circular fashion. Seems like you avoided the problem right now by removing the need for Expression to refer to all subclasses, but it would come back, in, for example, LambdaExpression -- which is an expression that needs to refer to CompoundStatement that is defined later in this file, while CompoundStatement will need to refer to Expression. Maybe there is also a way to break circularity there by careful ordering -- but we would be mixing the order of expressions and statements.

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

73

[sammccall]

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

123

In the current setup, there's a simple solution to the ordering constraints: define all the Alternatives first. It's not ideal, but I think less confusing than having separate defs for rule vs nodes.

OTOH if we want Alternatives to have down-edges later (which I think would make sense if we use variants rather than subclassing) then we'll definitely run into cycles and will need to break them by splitting out the rules.
(Or if we have cycles that don't involve Alternatives, and don't want to introduce artificial ones).

I think we probably will hit this case, but would like to punt on it a little to see whether it makes sense to break loops only where needed or fully separate declaration/definition.

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

73

Hmm, I don't like swapping the order here - the role is both more important and written first.
I think the issue is the scope of "unique" is ambiguous, I'll try to fix that.

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

 /// Models an `unqualified-id`. C++ [expr.prim.id.unqual]
 /// e.g. the `size` in `std::vector<int>::size`.
 class UnqualifiedId final : public Tree {
 public:
   UnqualifiedId() : Tree(NodeKind::UnqualifiedId) {}
   static bool classof(const Node *N);
 };
 
-/// Models an `id-expression`, e.g. `std::vector<int>::size`.
-/// C++ [expr.prim.id]
-/// id-expression:
-///   unqualified-id
-///   qualified-id
-/// qualified-id:
-///   nested-name-specifier template_opt unqualified-id
-class IdExpression final : public Expression {
-public:
-  IdExpression() : Expression(NodeKind::IdExpression) {}
-  static bool classof(const Node *N);
-  NestedNameSpecifier *getQualifier();
-  Leaf *getTemplateKeyword();
-  UnqualifiedId *getUnqualifiedId();
-};
-
 /// An expression of an unknown kind, i.e. one not currently handled by the
 /// syntax tree.
 class UnknownExpression final : public Expression {
 public:
   UnknownExpression() : Expression(NodeKind::UnknownExpression) {}
   static bool classof(const Node *N);
 };
 
-/// Models a this expression `this`. C++ [expr.prim.this]
-class ThisExpression final : public Expression {
-public:
-  ThisExpression() : Expression(NodeKind::ThisExpression) {}
-  static bool classof(const Node *N);
-  Leaf *getThisKeyword();
-};
-
 /// Models arguments of a function call.
 ///   call-arguments:
 ///     delimited_list(expression, ',')
 /// Note: This construct is a simplification of the grammar rule for
 /// `expression-list`, that is used in the definition of `call-expression`
 class CallArguments final : public List {
 public:
   CallArguments() : List(NodeKind::CallArguments) {}
   static bool classof(const Node *N);
   std::vector<Expression *> getArguments();
   std::vector<List::ElementAndDelimiter<Expression>> getArgumentsAndCommas();
 };
 
-/// A function call. C++ [expr.call]
-/// call-expression:
-///   expression '(' call-arguments ')'
-/// e.g `f(1, '2')` or `this->Base::f()`
-class CallExpression final : public Expression {
-public:
-  CallExpression() : Expression(NodeKind::CallExpression) {}
-  static bool classof(const Node *N);
-  Expression *getCallee();
-  Leaf *getOpenParen();
-  CallArguments *getArguments();
-  Leaf *getCloseParen();
-};
-
-/// Models a parenthesized expression `(E)`. C++ [expr.prim.paren]
-/// e.g. `(3 + 2)` in `a = 1 + (3 + 2);`
-class ParenExpression final : public Expression {
-public:
-  ParenExpression() : Expression(NodeKind::ParenExpression) {}
-  static bool classof(const Node *N);
-  Leaf *getOpenParen();
-  Expression *getSubExpression();
-  Leaf *getCloseParen();
-};
-
-/// Models a class member access. C++ [expr.ref]
-/// member-expression:
-///   expression -> template_opt id-expression
-///   expression .  template_opt id-expression
-/// e.g. `x.a`, `xp->a`
-///
-/// Note: An implicit member access inside a class, i.e. `a` instead of
-/// `this->a`, is an `id-expression`.
-class MemberExpression final : public Expression {
-public:
-  MemberExpression() : Expression(NodeKind::MemberExpression) {}
-  static bool classof(const Node *N);
-  Expression *getObject();
-  Leaf *getAccessToken();
-  Leaf *getTemplateKeyword();
-  IdExpression *getMember();
-};
-
 /// Expression for literals. C++ [lex.literal]
 class LiteralExpression : public Expression {
 public:
   LiteralExpression(NodeKind K) : Expression(K) {}
   static bool classof(const Node *N);
   Leaf *getLiteralToken();
 };
 

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

 include "clang/Tooling/Syntax/Syntax.td"
 
 def TranslationUnit : Unconstrained {
   let documentation = [{
     A root node for a translation unit. Parent is always null.
   }];
 }
 
+def UnqualifiedId : External<Tree> {}
+
+// Lists
+def List : External<Tree> {}
+def DeclaratorList : External<List> {}
+def ParameterDeclarationList : External<List> {}
+def CallArguments : External<List> {}
+def NestedNameSpecifier : External<List> {}
+
 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 ParenExpression : Sequence<Expression> {
+  let documentation = [{
+    Models a parenthesized expression `(E)`. C++ [expr.prim.paren]
+    e.g. `(3 + 2)` in `a = 1 + (3 + 2);`
+  }];
+  let children = [
+    Role<"OpenParen", Token<"l_paren">>,
+    Role<"SubExpression", Expression>,
+    Role<"CloseParen", Token<"r_paren">>,
+  ];
+}
 def LiteralExpression : External<Expression> {}
 def IntegerLiteralExpression : External<LiteralExpression> {}
 def CharacterLiteralExpression : External<LiteralExpression> {}
 def FloatingLiteralExpression : External<LiteralExpression> {}
 def StringLiteralExpression : External<LiteralExpression> {}
 def BoolLiteralExpression : External<LiteralExpression> {}
 def CxxNullPtrExpression : External<LiteralExpression> {}
 def UserDefinedLiteralExpression : External<LiteralExpression> {}
 def IntegerUserDefinedLiteralExpression : External<UserDefinedLiteralExpression> {}
 def FloatUserDefinedLiteralExpression : External<UserDefinedLiteralExpression> {}
 def CharUserDefinedLiteralExpression : External<UserDefinedLiteralExpression> {}
 def StringUserDefinedLiteralExpression : External<UserDefinedLiteralExpression> {}
-def IdExpression : External<Expression> {}
-def MemberExpression : External<Expression> {}
-def ThisExpression : External<Expression> {}
-def CallExpression : External<Expression> {}
+def IdExpression : Sequence<Expression> {
+  let documentation = [{
+    Models an `id-expression`, e.g. `std::vector<int>::size`.
+    C++ [expr.prim.id]
+    id-expression:
+      unqualified-id
+      qualified-id
+    qualified-id:
+      nested-name-specifier template_opt unqualified-id
+  }];
+  let children = [
+    Role<"Qualifier", Optional<NestedNameSpecifier>>,
+    Role<"TemplateKeyword", Optional<Keyword<"template">>>,
+    Role<"UnqualifiedId", UnqualifiedId>,
+  ];
+}
+def MemberExpression : Sequence<Expression> {
+  let documentation = [{
+    Models a class member access. C++ [expr.ref]
+    member-expression:
+      expression -> template_opt id-expression
+      expression .  template_opt id-expression
+    e.g. `x.a`, `xp->a`
+
+    Note: An implicit member access inside a class, i.e. `a` instead of
+    `this->a`, is an `id-expression`.
+  }];
+  let children = [
+    Role<"Object", Expression>,
+    Role<"AccessToken", AnyToken<["period","arrow"]>>,
+    Role<"TemplateKeyword", Optional<Keyword<"template">>>,
+    Role<"Member", IdExpression>,
+  ];
+}
+def ThisExpression : Sequence<Expression> {
+  let documentation = [{
+    Models a this expression `this`. C++ [expr.prim.this]
+  }];
+  let children = [
+    Role<"IntroducerKeyword", Keyword<"this">>,
+  ];
+}
+def CallExpression : Sequence<Expression> {
+  let documentation = [{
+    A function call. C++ [expr.call]
+    call-expression:
+      expression '(' call-arguments ')'
+    e.g `f(1, '2')` or `this->Base::f()`
+  }];
+  let children = [
+    Role<"Callee", Expression>,
+    Role<"OpenParen", Token<"l_paren">>,
+    Role<"Arguments", CallArguments>,
+    Role<"CloseParen", Token<"r_paren">>,
+  ];
+}
 
 // Statements.
 def Statement : External<Tree> {}
 def UnknownStatement : External<Statement> {}
 def DeclarationStatement : External<Statement> {}
 def EmptyStatement : External<Statement> {}
 def SwitchStatement : External<Statement> {}
 def CaseStatement : External<Statement> {}

 def Declarator : External<Tree> {}
 def SimpleDeclarator : External<Declarator> {}
 def ParenDeclarator : External<Declarator> {}
 
 def ArraySubscript : External<Tree> {}
 def TrailingReturnType : External<Tree> {}
 def ParametersAndQualifiers : External<Tree> {}
 def MemberPointer : External<Tree> {}
-def UnqualifiedId : External<Tree> {}
-
-// 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 : 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`.
   }];
 }

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

 // The concrete nodes are defined in terms of these classes in 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.
 //
 //===----------------------------------------------------------------------===//
 
+// Syntax is any constraint on constructs that can appear somewhere.
+class Syntax;
+class Optional<Syntax inner_> : Syntax { Syntax inner = inner_; }
+class AnyToken<list<string> kinds_> : Syntax { list<string> kinds = kinds_; }
+class Token<string kind_> : AnyToken<[kind_]>;
+class Keyword<string kw> : Token<!strconcat("kw_", kw)>;
+
 // Defs derived from NodeType correspond to syntax tree node types.
-class NodeType {
+// NodeType is also a syntax constraint: one node of this type.
+class NodeType : Syntax {
   // 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.

 //   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.
+class Role<string role_, Syntax syntax_> {
+  string role = role_;
+  Syntax syntax = syntax_;
+}
+
+// A node which contains a fixed sequence of children in a particular order.
+//
+// Each child is characterized by a role (unique within the sequence), and
+// has an allowed base type for the node.
+// The role sequence and role/type match are enforced invariants of the class.
+//
+// We also record whether the child is required to be present, and which tokens
+// are permitted (for Leaf nodes). These invariants are not enforced.
+class Sequence<NodeType base_ = Tree> : NodeType {
+  let base = base_;
+  // Children must be Role or have a default role derived from the NodeType.
+  list<Role> children;
+}
+
+// FIXME: add list archetype.

clang/lib/Tooling/Syntax/Nodes.cpp

syntax::DeclaratorList::getDeclaratorsAndCommas() {
   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));
-}
-
-syntax::Leaf *syntax::MemberExpression::getAccessToken() {
-  return llvm::cast_or_null<syntax::Leaf>(
-      findChild(syntax::NodeRole::AccessToken));
-}
-
-syntax::IdExpression *syntax::MemberExpression::getMember() {
-  return cast_or_null<syntax::IdExpression>(
-      findChild(syntax::NodeRole::Member));
-}
-
-syntax::NestedNameSpecifier *syntax::IdExpression::getQualifier() {
-  return cast_or_null<syntax::NestedNameSpecifier>(
-      findChild(syntax::NodeRole::Qualifier));
-}
-
-syntax::Leaf *syntax::IdExpression::getTemplateKeyword() {
-  return llvm::cast_or_null<syntax::Leaf>(
-      findChild(syntax::NodeRole::TemplateKeyword));
-}
-
-syntax::UnqualifiedId *syntax::IdExpression::getUnqualifiedId() {
-  return cast_or_null<syntax::UnqualifiedId>(
-      findChild(syntax::NodeRole::UnqualifiedId));
-}
-
-syntax::Leaf *syntax::ParenExpression::getOpenParen() {
-  return cast_or_null<syntax::Leaf>(findChild(syntax::NodeRole::OpenParen));
-}
-
-syntax::Expression *syntax::ParenExpression::getSubExpression() {
-  return cast_or_null<syntax::Expression>(
-      findChild(syntax::NodeRole::SubExpression));
-}
-
-syntax::Leaf *syntax::ParenExpression::getCloseParen() {
-  return cast_or_null<syntax::Leaf>(findChild(syntax::NodeRole::CloseParen));
-}
-
-syntax::Leaf *syntax::ThisExpression::getThisKeyword() {
-  return cast_or_null<syntax::Leaf>(
-      findChild(syntax::NodeRole::IntroducerKeyword));
-}
-
 syntax::Leaf *syntax::LiteralExpression::getLiteralToken() {
   return cast_or_null<syntax::Leaf>(findChild(syntax::NodeRole::LiteralToken));
 }
 
 syntax::Expression *syntax::BinaryOperatorExpression::getLhs() {
   return cast_or_null<syntax::Expression>(
       findChild(syntax::NodeRole::LeftHandSide));
 }
syntax::Leaf *syntax::BinaryOperatorExpression::getOperatorToken() {
   return cast_or_null<syntax::Leaf>(findChild(syntax::NodeRole::OperatorToken));
 }
 
 syntax::Expression *syntax::BinaryOperatorExpression::getRhs() {
   return cast_or_null<syntax::Expression>(
       findChild(syntax::NodeRole::RightHandSide));
 }
 
-syntax::Expression *syntax::CallExpression::getCallee() {
-  return cast_or_null<syntax::Expression>(findChild(syntax::NodeRole::Callee));
-}
-
-syntax::Leaf *syntax::CallExpression::getOpenParen() {
-  return cast_or_null<syntax::Leaf>(findChild(syntax::NodeRole::OpenParen));
-}
-
-syntax::CallArguments *syntax::CallExpression::getArguments() {
-  return cast_or_null<syntax::CallArguments>(
-      findChild(syntax::NodeRole::Arguments));
-}
-
-syntax::Leaf *syntax::CallExpression::getCloseParen() {
-  return cast_or_null<syntax::Leaf>(findChild(syntax::NodeRole::CloseParen));
-}
-
 syntax::Leaf *syntax::SwitchStatement::getSwitchKeyword() {
   return cast_or_null<syntax::Leaf>(
       findChild(syntax::NodeRole::IntroducerKeyword));
 }
 
 syntax::Statement *syntax::SwitchStatement::getBody() {
   return cast_or_null<syntax::Statement>(
       findChild(syntax::NodeRole::BodyStatement));

clang/utils/TableGen/ClangSyntaxEmitter.cpp

 
 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());
 }
 
+struct SyntaxConstraint {
+  SyntaxConstraint(const llvm::Record &R) {
+    if (R.isSubClassOf("Optional")) {
+      *this = SyntaxConstraint(*R.getValueAsDef("inner"));
+    } else if (R.isSubClassOf("AnyToken")) {
+      NodeType = "Leaf";
+    } else if (R.isSubClassOf("NodeType")) {
+      NodeType = R.getName().str();
+    } else {
+      assert(false && "Unhandled Syntax kind");
+    }
+  }
+
+  std::string NodeType;
+  // optional and leaf types also go here, once we want to use them.
+};
+
 } // namespace
 
 void clang::EmitClangSyntaxNodeList(llvm::RecordKeeper &Records,
                                     llvm::raw_ostream &OS) {
   llvm::emitSourceFileHeader("Syntax tree node list", OS);
   Hierarchy H(Records);
   OS << R"cpp(
 #ifndef NODE
H.visit([&](const Hierarchy::NodeType &N) {
     // 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());
 
+    if (N.Record->isSubClassOf("Sequence")) {
+      // Getters for sequence elements.
+      for (const auto &C : N.Record->getValueAsListOfDefs("children")) {
+        assert(C->isSubClassOf("Role"));
+        llvm::StringRef Role = C->getValueAsString("role");
+        SyntaxConstraint Constraint(*C->getValueAsDef("syntax"));
+        for (const char *Const : {"", "const "})
+          OS << formatv(
+              "  {2}{1} *get{0}() {2} {{\n"
+              "    return llvm::cast_or_null<{1}>(findChild(NodeRole::{0}));\n"
+              "  }\n",
+              Role, Constraint.NodeType, Const);
+      }
+    }
+
     // classof. FIXME: move definition inline once ~all nodes are generated.
     OS << "  static bool classof(const Node *N);\n";
 
     OS << "};\n\n";
   });
 }