[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

241–276

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?

278–279

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?

328–335

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

[gribozavr2]

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

211

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

228

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

241–276

I think it is fine as is.

272

Please also define operator!=.

286

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.

330

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

clang/lib/Tooling/Syntax/Tree.cpp

367

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

391–396

421

Ditto?

[eduucaldas]

Answer comments, TODO: think about templated iterators

[eduucaldas]

• Make ElementAndDelimiterIterator templated.

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

272

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

clang/lib/Tooling/Syntax/Tree.cpp

421

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

241–242

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

241–242

Ignore comment above

252

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.

390

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

 
 #include "clang/Basic/LangOptions.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Basic/TokenKinds.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/iterator.h"
+#include "llvm/ADT/iterator_range.h"
 #include "llvm/Support/Allocator.h"
 #include <cstdint>
 
 namespace clang {
 namespace syntax {
 
 /// A memory arena for syntax trees. Also tracks the underlying token buffers,
 /// source manager, etc.

 ///
 /// This type models the following grammar construct:
 /// delimited-list(element, delimiter, termination, canBeEmpty)
 class List : public Tree {
 public:
   template <typename Element> struct ElementAndDelimiter {
     Element *element;
     Leaf *delimiter;
+    bool operator==(const ElementAndDelimiter &Other) const {
+      return element == Other.element && delimiter == Other.delimiter;
+    }
+    bool operator!=(const ElementAndDelimiter &Other) const {
+      return !(*this == Other);
+    }
   };
 
   enum class TerminationKind {
     Terminated,
     MaybeTerminated,
     Separated,
   };
 
   using Tree::Tree;
   static bool classof(const Node *N);
-  /// Returns the elements and corresponding delimiters. Missing elements
-  /// and delimiters are represented as null pointers.
+
+  /// Iterator through elements and their corresponding delimiters. Missing
+  /// elements and delimiters are represented as null pointers. Below we give
+  /// examples of what this iteration would looks like.
   ///
-  /// For example, in a separated list:
+  /// In a separated list:
   /// "a, b, c"  <=> [("a" , ","), ("b" , "," ), ("c" , null)]
   /// "a,  , c"  <=> [("a" , ","), (null, "," ), ("c" , null)]
   /// "a, b  c"  <=> [("a" , ","), ("b" , null), ("c" , null)]
   /// "a, b,"    <=> [("a" , ","), ("b" , "," ), (null, null)]
   ///
   /// In a terminated or maybe-terminated list:
   /// "a; b; c;" <=> [("a" , ";"), ("b" , ";" ), ("c" , ";" )]
   /// "a;  ; c;" <=> [("a" , ";"), (null, ";" ), ("c" , ";" )]
   /// "a; b  c;" <=> [("a" , ";"), ("b" , null), ("c" , ";" )]
   /// "a; b; c"  <=> [("a" , ";"), ("b" , ";" ), ("c" , null)]
+  template <typename ElementType>
+  class ElementAndDelimiterIterator
+      : public llvm::iterator_facade_base<
+            ElementAndDelimiterIterator<ElementType>, std::forward_iterator_tag,
+            ElementAndDelimiter<ElementType>> {
+  public:
+    ElementAndDelimiterIterator(
+        llvm::Optional<ElementAndDelimiter<ElementType>> ED)
+        : EDI(ED) {}
+
+    ElementAndDelimiterIterator &operator++() {
+      assert(EDI.hasValue() && "Incrementing sentinel iterator.");
+      if (auto *Delimiter = EDI.getValue().delimiter)
+        EDI =
+            castToElementType(getElementAndDelimiterAfterDelimiter(Delimiter));
+      else if (auto *Element = EDI.getValue().element)
+        EDI = castToElementType(getElementAndDelimiterAfterElement(Element));
+      else
+        EDI = None;
+      return *this;
+    }
+
+    ElementAndDelimiter<ElementType> &operator*() {
+      assert(EDI.hasValue() && "Dereferencing sentinel iterator.");
+      return EDI.getValue();
+    }
+
+    const ElementAndDelimiter<ElementType> &operator*() const {
+      assert(EDI.hasValue() && "Dereferencing sentinel iterator.");
+      return EDI.getValue();
+    }
+
+    bool operator==(const ElementAndDelimiterIterator &Other) const {
+      return EDI == Other.EDI;
+    }
+
+  private:
+    llvm::Optional<ElementAndDelimiter<ElementType>> EDI;
+
+  public:
+    static llvm::Optional<ElementAndDelimiter<ElementType>>
+    castToElementType(llvm::Optional<ElementAndDelimiter<Node>> ND) {
+      if (!ND)
+        return None;
+      return llvm::Optional<ElementAndDelimiter<ElementType>>(
+          {cast_or_null<ElementType>(ND->element), ND->delimiter});
+    }
+  };
+
+  ElementAndDelimiterIterator<Node> getBeginNode();
+  ElementAndDelimiterIterator<Node> getEndNode();
+
+  template <typename ElementType>
+  using ElementsAndDelimitersRange =
+      llvm::iterator_range<ElementAndDelimiterIterator<ElementType>>;
+
+  ElementsAndDelimitersRange<Node> getNodeRange() {
+    return ElementsAndDelimitersRange<Node>(getBeginNode(), getEndNode());
+  }
+
+  // Returns the elements of the list, and their corresponding delimiters.
+  // Missing elements are represented as null pointers. Iterating through
+  // `getElementsAsNodesAndDelimiters()` is equivalent to iterating through
+  // `getRange()`
   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;
+
+private:
+  static ElementAndDelimiter<Node> getWithDelimiter(Node *Element);
+  static llvm::Optional<ElementAndDelimiter<Node>>
+  getElementAndDelimiterAfterDelimiter(Leaf *Delimiter);
+  static llvm::Optional<ElementAndDelimiter<Node>>
+  getElementAndDelimiterAfterElement(Node *Element);
 };
 
 } // 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));
-  }
+  for (auto C : getNodeRange())
+    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});
-  }
+  for (auto C : getNodeRange())
+    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));
-  }
+  for (auto C : getNodeRange())
+    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});
-  }
+  for (auto C : getNodeRange())
+    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));
-  }
+  for (auto C : getNodeRange())
+    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) {
+  for (auto C : getNodeRange())
     Children.push_back(
-        {llvm::cast<syntax::SimpleDeclaration>(ParameterAsNodeAndComma.element),
-         ParameterAsNodeAndComma.delimiter});
-  }
+        {cast<syntax::SimpleDeclaration>(C.element), C.delimiter});
+
   return Children;
 }
 
 std::vector<syntax::SimpleDeclarator *>
 syntax::DeclaratorList::getDeclarators() {
-  auto DeclaratorsAsNodes = getElementsAsNodes();
   std::vector<syntax::SimpleDeclarator *> Children;
-  for (const auto &DeclaratorAsNode : DeclaratorsAsNodes) {
-    Children.push_back(llvm::cast<syntax::SimpleDeclarator>(DeclaratorAsNode));
-  }
+  for (auto C : getNodeRange())
+    Children.push_back(cast<syntax::SimpleDeclarator>(C.element));
+
   return Children;
 }
 
 std::vector<syntax::List::ElementAndDelimiter<syntax::SimpleDeclarator>>
 syntax::DeclaratorList::getDeclaratorsAndCommas() {
-  auto DeclaratorsAsNodesAndCommas = getElementsAsNodesAndDelimiters();
   std::vector<syntax::List::ElementAndDelimiter<syntax::SimpleDeclarator>>
       Children;
-  for (const auto &DeclaratorAsNodeAndComma : DeclaratorsAsNodesAndCommas) {
+  for (auto C : getNodeRange())
     Children.push_back(
-        {llvm::cast<syntax::SimpleDeclarator>(DeclaratorAsNodeAndComma.element),
-         DeclaratorAsNodeAndComma.delimiter});
-  }
+        {cast<syntax::SimpleDeclarator>(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)};
 
-  switch (getTerminationKind()) {
-  case syntax::List::TerminationKind::Separated: {
-    Children.push_back({ElementWithoutDelimiter, nullptr});
-    break;
-  }
+llvm::Optional<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getElementAndDelimiterAfterDelimiter(syntax::Leaf *Delimiter) {
+  assert(Delimiter && Delimiter->getRole() == syntax::NodeRole::ListDelimiter);
+  auto *List = cast<syntax::List>(Delimiter->getParent());
+  auto *Next = Delimiter->getNextSibling();
+  if (!Next) {
+    switch (List->getTerminationKind()) {
+    // 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();
+  if (!Next)
+    // This was the last element of the list.
+    return None;
+
+  switch (Next->getRole()) {
+  case syntax::NodeRole::ListElement:
+    // We have something of the form "a b ..." => 'b' starts the next
+    // `ElementAndDelimiter`.
+    return getWithDelimiter(Next);
+
+  case syntax::NodeRole::ListDelimiter:
+    // We have something of the form "a , ..." => whatever comes after the comma
+    // starts the next `ElementAndDelimiter`.
+    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;
-  }
-  }
+syntax::List::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getEndNode() {
+  return llvm::Optional<ElementAndDelimiter<Node>>(None);
+}
+
+syntax::List::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getBeginNode() {
+  auto *First = getFirstChild();
+  if (!First)
+    return getEndNode();
+  switch (First->getRole()) {
+  case syntax::NodeRole::ListElement:
+    return llvm::Optional<ElementAndDelimiter<Node>>(getWithDelimiter(First));
+  case syntax::NodeRole::ListDelimiter:
+    return llvm::Optional<ElementAndDelimiter<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() {
+  return std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>(
+      getBeginNode(), getEndNode());
 
+std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
+  std::vector<syntax::Node *> Children;
+  std::transform(
+      getBeginNode(), getEndNode(), std::back_inserter(Children),
+      [](ElementAndDelimiter<syntax::Node> ED) { return ED.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: