[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

302–337

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?

310–317

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

339–340

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

208

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

292

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

302–337

I think it is fine as is.

312

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

333

Please also define operator!=.

347

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

405

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

405–410

407

Ditto?

[eduucaldas]

Answer comments, TODO: think about templated iterators

[eduucaldas]

• Make ElementAndDelimiterIterator templated.

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

333

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

clang/lib/Tooling/Syntax/Tree.cpp

407

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

302–303

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

302–303

Ignore comment above

313

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.

451

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.

 };
 
 /// A list of Elements separated or terminated by a fixed token.
 ///
 /// 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;
-  };
+  using Tree::Tree;
+  static bool classof(const Node *N);
+
+  // 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;
 
   enum class TerminationKind {
     Terminated,
     MaybeTerminated,
     Separated,
   };
 
-  using Tree::Tree;
-  static bool classof(const Node *N);
+  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;
+
+public:
+  template <typename Element> struct ElementAndDelimiter {
+    Element *element;
+    Leaf *delimiter;
+    bool operator==(const ElementAndDelimiter &Other) const {
+      return element == Other.element && delimiter == Other.delimiter;
+    }
+  };
+
+  class ElementAndDelimiterIterator
+      : public llvm::iterator_facade_base<ElementAndDelimiterIterator,
+                                          std::forward_iterator_tag,
+                                          ElementAndDelimiter<Node>> {
+  public:
+    ElementAndDelimiterIterator(llvm::Optional<ElementAndDelimiter<Node>> ED)
+        : EDI(ED) {}
+
+    ElementAndDelimiterIterator &operator++() {
+      assert(EDI.hasValue() && "Incrementing sentinel iterator.");
+      if (auto *Delimiter = EDI.getValue().delimiter)
+        EDI = getElementAndDelimiterAfterDelimiter(Delimiter);
+      else if (auto *Element = EDI.getValue().element)
+        EDI = getElementAndDelimiterAfterElement(Element);
+      else
+        EDI = None;
+      return *this;
+    }
+
+    ElementAndDelimiter<Node> &operator*() {
+      assert(EDI.hasValue() && "Dereferencing sentinel iterator.");
+      return EDI.getValue();
+    }
+
+    const ElementAndDelimiter<Node> &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<Node>> EDI;
+  };
+
+  ElementAndDelimiterIterator getBegin();
+  ElementAndDelimiterIterator getEnd();
+
+  using ElementsAndDelimitersRange =
+      llvm::iterator_range<ElementAndDelimiterIterator>;
+
+  ElementsAndDelimitersRange getRange() {
+    return ElementsAndDelimitersRange(getBegin(), getEnd());
+  }
+
   /// 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" , 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)]
   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:
+  // Auxiliary methods for implementing `ElementAndDelimiterIterator`.
+  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));
-  }
+  auto Children = std::vector<syntax::NameSpecifier *>();
+  for (auto C : getRange())
+    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 : getRange())
+    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 : getRange())
+    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 : getRange())
+    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 : getRange())
+    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 : getRange())
     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));
-  }
+  auto Children = std::vector<syntax::SimpleDeclarator *>();
+  for (auto C : getRange())
+    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) {
+  auto Children = std::vector<
+      syntax::List::ElementAndDelimiter<syntax::SimpleDeclarator>>();
+  for (auto C : getRange())
     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();
+  // 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;
-  }
+syntax::List::ElementAndDelimiterIterator syntax::List::getEnd() {
+  return llvm::Optional<ElementAndDelimiter<Node>>(None);
+
+syntax::List::ElementAndDelimiterIterator syntax::List::getBegin() {
+  auto *First = getFirstChild();
+  if (!First)
+    return getEnd();
+  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() {
+  auto Children = std::vector<syntax::List::ElementAndDelimiter<Node>>();
+  for (auto C : getRange()) {
+    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 : getRange()) {
+    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 "