[SyntaxTree] Implement the List construct.

[eduucaldas]

Summary

We defined a List construct to help with the implementation of list-like
grammar rules. This is a first implementation of this API.

[eduucaldas]

clang/include/clang/Tooling/Syntax/Tree.h

223

As this is a base List, we don't have the necessary information tom implement the following methods. I chose to give them default values, check their definition

[gribozavr2]

I feel uneasy about adding this code without tests. Could we maybe port the function parameter list to use this infrastructure, and then add tests that exercise getElementsAsNodesAndDelimiters?

clang/include/clang/Tooling/Syntax/Tree.h

194

enum class?

Also, I think it should be renamed to ListTerminationKind or moved into List as a nested type.

197

Add a "WithoutDelimiters" case as well?

200

Could you add a doc comment?

229

Should we change this function to return optional to allow representing lists that don't have any delimiters?

232

Please add a doc comment that emphasizes that any list can be empty when the syntax tree represents code with syntax errors.

clang/lib/Tooling/Syntax/Tree.cpp

277

This assert is only correct for valid code. When a syntax tree represents invalid code, any list can be empty.

293

298

368

I think the eventual implementation should switch on the syntax tree node kind and return the appropriate information. Right now, there are no subclasses of List, to these methods should be implemented as llvm_unreachable.

[eduucaldas]

Answer comments

non-delimited-lists need further discussion

clang/include/clang/Tooling/Syntax/Tree.h

197

I think we might want to treat non-delimited-list in another way. as many of the member functions stop making sense.
getElementsAsNodesAndDelimiters
getDelimiterTokenKind
getTerminationKind

229

Cf, previous comment on non-delimited-lists

clang/lib/Tooling/Syntax/Tree.cpp

277

Yeah, of course, we had already discussed that verifying those things in the casa of valid code would be the task of the verifier.

[gribozavr2]

clang/include/clang/Tooling/Syntax/Tree.h

197

OK, I'm convinced.

[gribozavr2]

clang/include/clang/Tooling/Syntax/Tree.h

247

I just realized that the rest of the syntax tree API does not use the get~ prefix. However, most of Clang does, as far as I know. Which way should we repaint?

[eduucaldas]

clang/include/clang/Tooling/Syntax/Tree.h

247

Let's go with Clang! I can make this change in another patch

[gribozavr2]

clang/include/clang/Tooling/Syntax/Tree.h

194

"""
A list of elements separated or terminated by a fixed token.

This type models the following grammar construct:
delimited-list(element, delimiter, termination, canBeEmpty)
"""

249

"Whether this list can be empty in syntactically and semantically correct code.

This list may be empty when the source code has errors even if canBeEmpty() returns true."

clang/lib/Tooling/Syntax/Tree.cpp

367

I think a better error message would say that there are no subclasses of List, so this method can't be called.

[eduucaldas]

Answer code-review

clang/include/clang/Tooling/Syntax/Tree.h

249

"...even if canBeEmpty() returns false"

clang/lib/Tooling/Syntax/Tree.cpp

367

Very sorry about that, this error was a copy-paste, I forgot to edit it

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

enum class NodeRole : uint8_t {
   LiteralToken,
   /// Tokens or Keywords
   ArrowToken,
   ExternKeyword,
   /// An inner statement for those that have only a single child of kind
   /// statement, e.g. loop body for while, for, etc; inner statement for case,
   /// default, etc.
   BodyStatement,
+  List_element,
+  List_delimiter,
 
   // Roles specific to particular node kinds.
   OperatorExpression_operatorToken,
   UnaryOperatorExpression_operand,
   BinaryOperatorExpression_leftHandSide,
   BinaryOperatorExpression_rightHandSide,
   CaseStatement_value,
   IfStatement_thenStatement,

clang/include/clang/Tooling/Syntax/Tree.h

private:
   /// Only used by MutationsImpl to implement higher-level mutation operations.
   /// (!) \p New can be null to model removal of the child range.
   void replaceChildRangeLowLevel(Node *BeforeBegin, Node *End, Node *New);
   friend class MutationsImpl;
 
   Node *FirstChild = nullptr;
 };
 
+/// A Tree that represents a syntactic list of elements.
+///
+/// We try to model with this type the artificial grammar-construct:
+/// delimited-list(element, delimiter, termination, canBeEmpty)
+///
+/// For example, from C++ [dcl.decl]:
+/// init-declarator-list:
+///   init-declarator
+///   init-declarator-list , init-declarator
+/// May be mapped to:
+///   delimited-list(init-declarator, ',', separated, !canBeEmpty)
+///
+/// Thus the `InitDeclaratorList` syntax node would inherit from `List`, with:
+/// getTerminationKind() returning `Separated`
+/// canBeEmpty() returning `true`
+/// getDelimiterTokenKind() returning `,`
+class List : public Tree {
+  template <typename Element> struct ElementAndDelimiter {
+    Element *element;
+    Leaf *delimiter;
+  };
+
+  enum class TerminationKind {
+    Terminated,
+    MaybeTerminated,
+    Separated,
+  };
+
+  /// Returns the elements and corresponding delimiters. Missing elements
+  /// and delimiters are represented as null pointers.
+  ///
+  /// For example, in a separated list:
+  /// "a, b, c" <=> [("a", ","), ("b", ","), ("c", null)]
+  /// "a, , c" <=> [("a", ","), (null, ","), ("c", ",)]
+  /// "a, b," <=> [("a", ","), ("b", ","), (null, null)]
+  ///
+  /// In a terminated or maybe-terminated list:
+  /// "a, b," <=> [("a", ","), ("b", ",")]
+  std::vector<ElementAndDelimiter<Node>> getElementsAsNodesAndDelimiters();
+
+  /// Returns the elements of the list. Missing elements are represented
+  /// as null pointers in the same way as in the return value of
+  /// `getElementsAsNodesAndDelimiters()`.
+  std::vector<Node *> getElementsAsNodes();
+
+  // These can't be implemented with the information we have!
+
+  /// Returns the appropriate delimiter for this list.
+  ///
+  /// Useful for discovering the correct delimiter to use when adding
+  /// elements to empty or one-element lists.
+  clang::tok::TokenKind getDelimiterTokenKind();
+
+  TerminationKind getTerminationKind();
+
+  /// Return whether *under valid code* the list can be empty.
+  ///
+  /// If the underlying source code is not expected to be valid, then the list
+  /// may be empty even if canBeEmpty() returns false.
+  bool canBeEmpty();
+};
+
 } // namespace syntax
 } // namespace clang
 
 #endif

clang/lib/Tooling/Syntax/Nodes.cpp

llvm::raw_ostream &syntax::operator<<(llvm::raw_ostream &OS, NodeRole R) {
   case syntax::NodeRole::LiteralToken:
     return OS << "LiteralToken";
   case syntax::NodeRole::ArrowToken:
     return OS << "ArrowToken";
   case syntax::NodeRole::ExternKeyword:
     return OS << "ExternKeyword";
   case syntax::NodeRole::BodyStatement:
     return OS << "BodyStatement";
+  case syntax::NodeRole::List_element:
+    return OS << "List_element";
+  case syntax::NodeRole::List_delimiter:
+    return OS << "List_delimiter";
   case syntax::NodeRole::CaseStatement_value:
     return OS << "CaseStatement_value";
   case syntax::NodeRole::IfStatement_thenStatement:
     return OS << "IfStatement_thenStatement";
   case syntax::NodeRole::IfStatement_elseKeyword:
     return OS << "IfStatement_elseKeyword";
   case syntax::NodeRole::IfStatement_elseStatement:
     return OS << "IfStatement_elseStatement";

clang/lib/Tooling/Syntax/Tree.cpp

 
 syntax::Node *syntax::Tree::findChild(NodeRole R) {
   for (auto *C = FirstChild; C; C = C->nextSibling()) {
     if (C->role() == R)
       return C;
   }
   return nullptr;
 }
+
+std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getElementsAsNodesAndDelimiters() {
+  if (!firstChild())
+    return {};
+
+  auto children = std::vector<syntax::List::ElementAndDelimiter<Node>>();
+  syntax::Node *elementWithoutDelimiter = nullptr;
+  for (auto *C = firstChild(); C; C = C->nextSibling()) {
+    switch (C->role()) {
+    case syntax::NodeRole::List_element: {
+      if (elementWithoutDelimiter) {
+        children.push_back({elementWithoutDelimiter, nullptr});
+      }
+      elementWithoutDelimiter = C;
+      break;
+    }
+    case syntax::NodeRole::List_delimiter: {
+      children.push_back({elementWithoutDelimiter, cast<syntax::Leaf>(C)});
+      elementWithoutDelimiter = nullptr;
+      break;
+    }
+    default:
+      llvm_unreachable(
+          "A list can have only elements and delimiters as children.");
+    }
+  }
+
+  switch (getTerminationKind()) {
+  case syntax::List::TerminationKind::Separated: {
+    children.push_back({elementWithoutDelimiter, nullptr});
+    break;
+  }
+  case syntax::List::TerminationKind::Terminated:
+  case syntax::List::TerminationKind::MaybeTerminated: {
+    if (elementWithoutDelimiter) {
+      children.push_back({elementWithoutDelimiter, nullptr});
+    }
+    break;
+  }
+  }
+
+  return children;
+}
+
+// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
+// ignoring delimiters
+std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
+  if (!firstChild())
+    return {};
+
+  auto children = std::vector<syntax::Node *>();
+  syntax::Node *elementWithoutDelimiter = nullptr;
+  for (auto *C = firstChild(); C; C = C->nextSibling()) {
+    switch (C->role()) {
+    case syntax::NodeRole::List_element: {
+      if (elementWithoutDelimiter) {
+        children.push_back(elementWithoutDelimiter);
+      }
+      elementWithoutDelimiter = C;
+      break;
+    }
+    case syntax::NodeRole::List_delimiter: {
+      children.push_back(elementWithoutDelimiter);
+      elementWithoutDelimiter = nullptr;
+      break;
+    }
+    default:
+      llvm_unreachable("A list has only elements or delimiters.");
+    }
+  }
+
+  switch (getTerminationKind()) {
+  case syntax::List::TerminationKind::Separated: {
+    children.push_back(elementWithoutDelimiter);
+    break;
+  }
+  case syntax::List::TerminationKind::Terminated:
+  case syntax::List::TerminationKind::MaybeTerminated: {
+    if (elementWithoutDelimiter) {
+      children.push_back(elementWithoutDelimiter);
+    }
+    break;
+  }
+  }
+
+  return children;
+}
+
+// The methods below can't be implemented without information about the derived
+// list. These methods will be implemented by switching on the derived list's
+// `NodeKind`
+
+clang::tok::TokenKind syntax::List::getDelimiterTokenKind() {
+  llvm_unreachable("A list can have only elements and delimiters as children.");
+}
+
+syntax::List::TerminationKind syntax::List::getTerminationKind() {
+  llvm_unreachable("A list can have only elements and delimiters as children.");
+}
+
+bool syntax::List::canBeEmpty() {
+  llvm_unreachable("A list can have only elements and delimiters as children.");
+}