[SyntaxTree] Provide iterator-like functions for Lists

[eduucaldas]

• [SyntaxTree] Provide iterator for List that iterates through ElementAndDelimiters even for not well-defined lists.

[eduucaldas]

Better comments

[eduucaldas]

Reorganize methods to minimize diffs

[eduucaldas]

Replace auto .. = std::vector(); with std::vector ..;

[eduucaldas]

This is quite low priority, compared to the other branches of work, but it was almost ready work, so I decided to polish it and send it to review now.

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

237–272

Should we hide some of this? Most of the member functions are a couple of lines, so I decided not to. What is your opinion?

260–267

These are all private static methods, should we hide them from the header?

274–275

I chose to leave it as getBegin and getEnd instead of getElementsAndDelimitersBegin. I did this because the return type of those methods already tells us that we're getting an ElementAndDelimiterIterator.

What do you think?

[gribozavr2]

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

209

Please also define operator!= even if it is not used yet.

231

"how something looks" or "what something looks like"

237–272

I think it is fine as is.

262

People can use "find usages" to find what uses these methods. Such comments often go out of date.

268

Please also define operator!=.

282

I'd imagine derived classes would have iterators that produce strongly-typed elements, right?

If so, these methods getBegin()/getEnd()/getRange() should have the word "Node" in them.

clang/lib/Tooling/Syntax/Tree.cpp

409

I have a hard time understand what a b x and the comma stand for in these comments.

409–414

410

Ditto?

[eduucaldas]

Answer comments, TODO: think about templated iterators

[eduucaldas]

• Make ElementAndDelimiterIterator templated.

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

268

this is defined by the iterato_facade_base, take a look at the comments in this class template

clang/lib/Tooling/Syntax/Tree.cpp

410

Here we could do std::transform(getBegin(), getEnd(), std::back_inserter(result), [](ElementAndDelimiter ED){return ED.element;}). Is that more idiomatic?

[eduucaldas]

Haven't yet implemented BeforeBegin, waiting for a heads up on the patch as is.

[eduucaldas]

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

237–238

Since we're gonna provide strongly-typed iterators, I make the Iterator a class template.

I keep the base functions as they were, getElementAndDelimiterAfter..., but I cast their result using castToElementType.

Another option would be to make the base functions also templated and not perform any casting.

We'll use castToElementType to provide the strongly-typed iterators as well.

[eduucaldas]

• [SyntaxTree] ElementAndDelimiterIterator is polymorphic and supports BeforeBegin iterator

[eduucaldas]

Linting

[eduucaldas]

Add tests, ElementAndDelimiter are input iterators

[eduucaldas]

rename getBeforeBegin

[eduucaldas]

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

237–238

Ignore comment above

248

Since NodeRole is forward declared, we cannot access NodeRole::ListElement within the header, this is my work-around.

Another possibility would be to not forward declare and put NodeRole definition here. I think this is a bad choice because most roles are linked to syntax.

I declare isElement as a static private member function of List from lack of better place, I accept suggestions.

386

I have a hard time finding a name that is expressive enough and concise enough. The current one seems to imply that we're getting a node...

Alternatives:

• getBeforeBeginWithElementAsNode
• getBeforeBeginWithNodes
• getBeforeBeginBase
• getBeforeBeginNodeAndDelimiter

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

 /// delimited-list(element, delimiter, termination, canBeEmpty)
 class List : public Tree {
 public:
   template <typename Element> struct ElementAndDelimiter {
     Element *element;
     Leaf *delimiter;
   };
 
   enum class TerminationKind {
     Terminated,
     MaybeTerminated,
     Separated,
   };
 
   using Tree::Tree;
   static bool classof(const Node *N);
+
+  ElementAndDelimiter<Node> getWithDelimiter(Node *Element);
+  llvm::Optional<ElementAndDelimiter<Node>>
+  getElementAndDelimiterAfterDelimiter(Leaf *Delimiter);
+  llvm::Optional<ElementAndDelimiter<Node>>
+  getElementAndDelimiterAfterElement(Node *Element);
+  llvm::Optional<ElementAndDelimiter<Node>>
+  getNext(ElementAndDelimiter<Node> &B);
+  llvm::Optional<ElementAndDelimiter<Node>> getFirst();
+
   /// 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() const;
 
   TerminationKind getTerminationKind() const;
 
   /// 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 false.
   bool canBeEmpty() const;
 };
 
 } // namespace syntax
 } // namespace clang
 
 #endif

clang/lib/Tooling/Syntax/Nodes.cpp

raw_ostream &syntax::operator<<(raw_ostream &OS, NodeRole R) {
   }
   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() {
-  auto SpecifiersAsNodes = getElementsAsNodes();
-  std::vector<syntax::NameSpecifier *> Children;
-  for (const auto &Element : SpecifiersAsNodes) {
-    Children.push_back(llvm::cast<syntax::NameSpecifier>(Element));
-  }
+  auto Children = std::vector<syntax::NameSpecifier *>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back(cast<syntax::NameSpecifier>(C->element));
+
   return Children;
 }
 
 std::vector<syntax::List::ElementAndDelimiter<syntax::NameSpecifier>>
 syntax::NestedNameSpecifier::getSpecifiersAndDoubleColons() {
-  auto SpecifiersAsNodesAndDoubleColons = getElementsAsNodesAndDelimiters();
-  std::vector<syntax::List::ElementAndDelimiter<syntax::NameSpecifier>>
-      Children;
-  for (const auto &SpecifierAndDoubleColon : SpecifiersAsNodesAndDoubleColons) {
-    Children.push_back(
-        {llvm::cast<syntax::NameSpecifier>(SpecifierAndDoubleColon.element),
-         SpecifierAndDoubleColon.delimiter});
-  }
+  auto Children =
+      std::vector<syntax::List::ElementAndDelimiter<syntax::NameSpecifier>>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back({cast<syntax::NameSpecifier>(C->element), C->delimiter});
+
   return Children;
 }
 
 std::vector<syntax::Expression *> syntax::CallArguments::getArguments() {
-  auto ArgumentsAsNodes = getElementsAsNodes();
-  std::vector<syntax::Expression *> Children;
-  for (const auto &ArgumentAsNode : ArgumentsAsNodes) {
-    Children.push_back(llvm::cast<syntax::Expression>(ArgumentAsNode));
-  }
+  auto Children = std::vector<syntax::Expression *>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back(cast<syntax::Expression>(C->element));
+
   return Children;
 }
 
 std::vector<syntax::List::ElementAndDelimiter<syntax::Expression>>
 syntax::CallArguments::getArgumentsAndCommas() {
-  auto ArgumentsAsNodesAndCommas = getElementsAsNodesAndDelimiters();
-  std::vector<syntax::List::ElementAndDelimiter<syntax::Expression>> Children;
-  for (const auto &ArgumentAsNodeAndComma : ArgumentsAsNodesAndCommas) {
-    Children.push_back(
-        {llvm::cast<syntax::Expression>(ArgumentAsNodeAndComma.element),
-         ArgumentAsNodeAndComma.delimiter});
-  }
+  auto Children =
+      std::vector<syntax::List::ElementAndDelimiter<syntax::Expression>>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back({cast<syntax::Expression>(C->element), C->delimiter});
+
   return Children;
 }
 
 std::vector<syntax::SimpleDeclaration *>
 syntax::ParameterDeclarationList::getParameterDeclarations() {
-  auto ParametersAsNodes = getElementsAsNodes();
-  std::vector<syntax::SimpleDeclaration *> Children;
-  for (const auto &ParameterAsNode : ParametersAsNodes) {
-    Children.push_back(llvm::cast<syntax::SimpleDeclaration>(ParameterAsNode));
-  }
+  auto Children = std::vector<syntax::SimpleDeclaration *>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back(cast<syntax::SimpleDeclaration>(C->element));
+
   return Children;
 }
 
 std::vector<syntax::List::ElementAndDelimiter<syntax::SimpleDeclaration>>
 syntax::ParameterDeclarationList::getParametersAndCommas() {
-  auto ParametersAsNodesAndCommas = getElementsAsNodesAndDelimiters();
-  std::vector<syntax::List::ElementAndDelimiter<syntax::SimpleDeclaration>>
-      Children;
-  for (const auto &ParameterAsNodeAndComma : ParametersAsNodesAndCommas) {
+  auto Children = std::vector<
+      syntax::List::ElementAndDelimiter<syntax::SimpleDeclaration>>();
+  for (auto C = getFirst(); C; C = getNext(*C))
     Children.push_back(
-        {llvm::cast<syntax::SimpleDeclaration>(ParameterAsNodeAndComma.element),
-         ParameterAsNodeAndComma.delimiter});
-  }
+        {cast<syntax::SimpleDeclaration>(C->element), C->delimiter});
+
   return Children;
 }
 
 syntax::Expression *syntax::MemberExpression::getObject() {
   return cast_or_null<syntax::Expression>(findChild(syntax::NodeRole::Object));
 }
 
 syntax::Leaf *syntax::MemberExpression::getTemplateKeyword() {

clang/lib/Tooling/Syntax/Tree.cpp

 //===- Tree.cpp -----------------------------------------------*- C++ -*-=====//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 #include "clang/Tooling/Syntax/Tree.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 
 using namespace clang;
 
 namespace {
 static void traverse(const syntax::Node *N,
bool syntax::List::classof(const syntax::Node *N) {
   case syntax::NodeKind::CallArguments:
   case syntax::NodeKind::ParameterDeclarationList:
     return true;
   default:
     return false;
   }
 }
 
-std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
-syntax::List::getElementsAsNodesAndDelimiters() {
-  if (!getFirstChild())
-    return {};
-
-  std::vector<syntax::List::ElementAndDelimiter<Node>> Children;
-  syntax::Node *ElementWithoutDelimiter = nullptr;
-  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
-    switch (C->getRole()) {
-    case syntax::NodeRole::ListElement: {
-      if (ElementWithoutDelimiter) {
-        Children.push_back({ElementWithoutDelimiter, nullptr});
-      }
-      ElementWithoutDelimiter = C;
-      break;
-    }
-    case syntax::NodeRole::ListDelimiter: {
-      Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(C)});
-      ElementWithoutDelimiter = nullptr;
-      break;
-    }
-    default:
-      llvm_unreachable(
-          "A list can have only elements and delimiters as children.");
-    }
-  }
+syntax::List::ElementAndDelimiter<syntax::Node>
+syntax::List::getWithDelimiter(syntax::Node *Element) {
+  assert(Element && Element->getRole() == syntax::NodeRole::ListElement);
+  auto *Next = Element->getNextSibling();
+  if (!Next)
+    return {Element, nullptr};
+  switch (Next->getRole()) {
+  case syntax::NodeRole::ListElement:
+    return {Element, nullptr};
+  case syntax::NodeRole::ListDelimiter:
+    return {Element, cast<syntax::Leaf>(Next)};
 
+llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getElementAndDelimiterAfterDelimiter(syntax::Leaf *Delimiter) {
+  assert(Delimiter && Delimiter->getRole() == syntax::NodeRole::ListDelimiter);
+  auto *Next = Delimiter->getNextSibling();
+  if (!Next) {
     switch (getTerminationKind()) {
-  case syntax::List::TerminationKind::Separated: {
-    Children.push_back({ElementWithoutDelimiter, nullptr});
-    break;
-  }
+    // List is separated and ends with delimiter
+    // => missing last ElementAndDelimiter.
+    case syntax::List::TerminationKind::Separated:
+      return llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>(
+          {nullptr, nullptr});
     case syntax::List::TerminationKind::Terminated:
-  case syntax::List::TerminationKind::MaybeTerminated: {
-    if (ElementWithoutDelimiter) {
-      Children.push_back({ElementWithoutDelimiter, nullptr});
+    case syntax::List::TerminationKind::MaybeTerminated:
+      return None;
     }
-    break;
   }
+  switch (Next->getRole()) {
+  case syntax::NodeRole::ListElement:
+    return getWithDelimiter(Next);
+
+  // Consecutive Delimiters => missing Element
+  case syntax::NodeRole::ListDelimiter:
+    return llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>(
+        {nullptr, cast<Leaf>(Next)});
+  default:
+    llvm_unreachable(
+        "A list can have only elements and delimiters as children.");
   }
-
-  return Children;
 }
 
-// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
-// ignoring delimiters
-std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
-  if (!getFirstChild())
-    return {};
+llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getElementAndDelimiterAfterElement(syntax::Node *Element) {
+  assert(Element && Element->getRole() == syntax::NodeRole::ListElement);
+  auto *Next = Element->getNextSibling();
+  // a  b, x => End of list, this was the last ElementAndDelimiter.
+  if (!Next)
+    return None;
+
+  switch (Next->getRole()) {
+  // x  b, c => next ElementAndDelimiter starts with 'b'.
+  case syntax::NodeRole::ListElement:
+    return getWithDelimiter(Next);
+
+  // a  x, c => next ElementAndDelimiter starts after ','.
+  case syntax::NodeRole::ListDelimiter:
+    return getElementAndDelimiterAfterDelimiter(cast<Leaf>(Next));
 
-  std::vector<syntax::Node *> Children;
-  syntax::Node *ElementWithoutDelimiter = nullptr;
-  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
-    switch (C->getRole()) {
-    case syntax::NodeRole::ListElement: {
-      if (ElementWithoutDelimiter) {
-        Children.push_back(ElementWithoutDelimiter);
-      }
-      ElementWithoutDelimiter = C;
-      break;
-    }
-    case syntax::NodeRole::ListDelimiter: {
-      Children.push_back(ElementWithoutDelimiter);
-      ElementWithoutDelimiter = nullptr;
-      break;
-    }
-    default:
-      llvm_unreachable("A list has only elements or delimiters.");
-    }
-  }
+    llvm_unreachable(
+        "A list can have only elements and delimiters as children.");
 
-  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;
-  }
-  }
+llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getNext(syntax::List::ElementAndDelimiter<syntax::Node> &ED) {
+  if (auto *Delimiter = ED.delimiter)
+    return getElementAndDelimiterAfterDelimiter(Delimiter);
+  if (auto *Element = ED.element)
+    return getElementAndDelimiterAfterElement(Element);
+  return None;
+}
+
+llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getFirst() {
+  auto *First = this->getFirstChild();
+  if (!First)
+    return None;
+  switch (First->getRole()) {
+  case syntax::NodeRole::ListElement:
+    return getWithDelimiter(First);
+  case syntax::NodeRole::ListDelimiter:
+    return llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>(
+        {nullptr, cast<Leaf>(First)});
+  default:
+    llvm_unreachable(
+        "A list can have only elements and delimiters as children.");
+
+std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getElementsAsNodesAndDelimiters() {
+  auto Children = std::vector<syntax::List::ElementAndDelimiter<Node>>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back(*C);
+
+  return Children;
 
+// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
+// ignoring delimiters
+std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
+  auto Children = std::vector<syntax::Node *>();
+  for (auto C = getFirst(); C; C = getNext(*C))
+    Children.push_back(C->element);
+
   return Children;
 }
 
 clang::tok::TokenKind syntax::List::getDelimiterTokenKind() const {
   switch (this->getKind()) {
   case NodeKind::NestedNameSpecifier:
     return clang::tok::coloncolon;
   case NodeKind::CallArguments:
   case NodeKind::ParameterDeclarationList:
     return clang::tok::comma;
   default:
     llvm_unreachable("This is not a subclass of List, thus "
                      "getDelimiterTokenKind() cannot be called");