[SyntaxTree] Provide iterators for Lists

[eduucaldas]

Summary

Provide an iterator for List that iterates through elements and delimiters on pairs. This iterator is robust to missing elements.
For instance, in the following function call:
f(a b, , )
The iterator would emit the following elements and delimiters:
[("a", null), ("b", ","), (null, ","), (null, null) ]

This iterator abstracts out many corner cases when dealing with lists, thus providing a cleaner interface for mutation and traversal of Lists.

Note: This iterator has the memory footprint of one pointer.

[gribozavr2]

Could you add tests that verify the pairing of elements and delimiters?

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

214

[eduucaldas]

In D90161#2353736, @gribozavr2 wrote:

Could you add tests that verify the pairing of elements and delimiters?

Those are surfaced through the previous tests, via getElementsAsNodesAndDelimiters

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

442

What do you think?

I didn't change it, because we had agreed on ElementsAsNodesAndDelimiters.

[eduucaldas]

Fix comment.

[sammccall]

(I started to review this, but now the current diff has only your changes against the first diff, rather than against master - can you upload a new diff?)

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

231

this name is bulky and hard to read, leads to more unwieldy names later (e.g. getElementAndDelimiterBeforeBegin which despite its length is unclear that it's even an iterator).

Would there be actual confusion in calling this ElementIterator, and providing the associated delimiters in addition to the elements?

282

nit: const (and getDelimiter)

iterators, like pointers, don't propagate const to their pointees.

(This rarely matters, but it sometimes comes up with template goop)

[eduucaldas]

Diff against master, sorry about that

[sammccall]

This seems like more implementation and API complexity than is justified by the problems it's solving.
I do think it's possible to drastically simplify it (I've left some suggestions here) but if not, I think we should move it to its own header.

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

231

overall, this design seems to be focused on the size being a single pointer, at the cost of complexity of most of the operations.

Why is this important to optimize for, compared to doing something like:

private:
  Node *Elt, *Delim, *Next;
  void advance() {
    // read one element
    // set Elt and/or Delim
    // always advances Next by at least one
  }
public:
  Iterator(Node *Start) : Elt(nullptr), Delim(nullptr), Next(Start) {}
  operator++() { advance(); }
  Leaf *getDelimiter() { return Delim; }
  Node *getElement() { return Elt; }

(Performance isn't the biggest concern here, but I'd usually expect two extra pointers on the stack to be preferable to all the branches in the current impl)

231

how sure are we that the template and strong typing is worthwhile on the iterators? Can we try without it for a while and see how painful it is?

235

Are the before-begin iterators needed immediately?

My understanding is that before-begin iterators are used with nodes due to the single-linked-list implementation, but that's going away. Can we avoid adding more of these by sequencing those changes differently?

242

NotSentinel -> Element?

Logically, the iterator is pointing at an element in the list. (If the element happens to be missing, fine...)

272

If we're not willing for this to be an InputIterator (I'm still not clear *why* not) or a stashing iterator (ditto), then maybe we might as well define operator* to refer to Element so people only have to use explicit iterators if they care about delimiters?

285

this is a crash if the list contains elements that have a type that doesn't match the container's expected type.

If we really need the strongly-typed version of this for constrained lists, we should define behavior here - probably return nullptr, just like an accessor on Tree for a strongly-typed single child whose type doesn't match what's expected.

364

what's the use case for this? What does it return on a default-constructed iterator?

443

these names are way way too long unless this is is going to be very rarely used (in which case it shouldn't be members at all).
Can we have iterator_range<...> getDelimitedElements() or something? (FWIW I'd prefer just getElements() and have the vector version be collectElements() or so)

clang/lib/Tooling/Syntax/Tree.cpp

352

Let's avoid deliberately crashing on invalid code.

I'd suggest either treating over non-element-non-delimiters as if they don't exist, or treating them as elements by default.

[eduucaldas]

I left some points unanswered, I'll answer them tomorrow :)

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

231

how sure are we that the template and strong typing is worthwhile on the iterators? Can we try without it for a while and see how painful it is?

It avoids duplication of code on derived classes - CallArguments, ParameterDeclarationList.... I suggest that we try to simplify other things and then rediscuss this point.

1. BeforeBegin.
2. Trying to fit everything into a pointer.
3. Templates and strong typing.

231

Would there be actual confusion in calling this ElementIterator, and providing the associated delimiters in addition to the elements?

This is a very interesting proposition! And it brought some interesting ideas. We'll further develop on them and answer to this inline tomorrow :)

235

https://reviews.llvm.org/D90240

242

Agreed

285

We want children of lists with role ListElement to have the expected C++ type.

Here is how an accessor on Tree is implemented.

syntax::Expression *syntax::BinaryOperatorExpression::getLhs() {   
  return cast_or_null<syntax::Expression>(                                   
  findChild(syntax::NodeRole::LeftHandSide)); 
}

Notice that if there is a Node with LeftHandSide it *must* be of the type Expression.

364

This is useful for the mutations API.
To remove a range of list elements, you may need to know the termination kind of this list, and thus you need to access the parent list.
Of course you could do it like getElement()->getParent() but that wouldn't work for sentinels and neither for the case of a missing last element on a separated list.

"a, b,"    <=> [("a" , ","), ("b" , "," ), (null, null)]

I confess I didn't think on default-constructed iterators. I don't see any use for those, however they *are* required for LegacyForwardIterator and onwards.

clang/lib/Tooling/Syntax/Tree.cpp

352

We thought about invalid code.
This llvm_unreachable states an invariant on List, that any children can only have one of the two roles.

This would imply that a tree builder - which for invalid code would be the pseudo parser - would assign ListDelimiter for everything that matches the expected delimiter, and try to parse other things into the expected ElementType.

Let's examine an example. In:
f(1, +, 2)
We have the List CallArguments for which ElementType = Expression.
We have some options:

• + is a Leaf with role Unknown.(which breaks the current invariant)
• + is part of an Expression, more specifically a BinaryOperatorExpression with lhs and rhs missing.

At the same time we could think of another example:
f(1, int, 2)
What would we do in this case?

In conclusion, I think this invariant is a bit constraining. We can consider relaxing it to allow Unknown roles. I think in general it would be good for us to have a common understanding of the plans for the pseudo parser.

[eduucaldas]

• const on getElement and similar.
• NotSentinel -> Element

[sammccall]

clang/lib/Tooling/Syntax/Tree.cpp

352

We thought about invalid code.
This llvm_unreachable states an invariant on List, that any children can only have one of the two roles.

I think this is a bigger topic we should separate from this code review (though it ties into the template question). Maybe we can meet later in the week?

There's a tension between the generic and typed interfaces when it comes to modification: the typed interfaces benefit from and can enforce strong semantic invariants, where generic interfaces cannot.
It looks like the current approach is "invariants are strong, generic mutation APIs don't exist".
I'm not sure this is the right long-term direction:

• many candidate invariants are incompatible with rich representation of broken code, and pseudoparsing, it's going to make the model very hard to understand
• it requires all refactorings to be built on "blessed" in-tree primitives that preserve invariants. This does not scale well, and does not give out-of-tree users the flexibility they need to solve their problems - many are stuck until the next LLVM release.
• generic/uniform access is empirically useful for some problems, and making access read-only is a large restriction on that option. (Examples: pseudoparsing, de/serialization)
• breaking invariants is sometimes the right thing to do. Consider a user dragging code around in an IDE - we'd adjust the selection (e.g. snap to complete nodes) before moving it, but we can't just reject the edit due to syntax.

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

 };
 
 /// 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:
+  using Tree::Tree;
+  static bool classof(const Node *N);
+
   template <typename Element> struct ElementAndDelimiter {
     Element *element;
     Leaf *delimiter;
   };
 
-  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 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)]
-  std::vector<ElementAndDelimiter<Node>> getElementsAsNodesAndDelimiters();
+  ///
+  /// NOTE: This iterator *should* be a standard iterator, however until C++17
+  /// we can only have reference proxies for input iterators, and
+  /// `ElementAndDelimiter` acts as one.
+  template <typename ElementType> class ElementAndDelimiterIterator {
+  public:
+    ElementAndDelimiterIterator &operator++() {
+      switch (getKind()) {
+      case IteratorKind::BeforeBegin: {
+        if (auto *Begin = getParent()->getFirstChild())
+          setElementOrDelimiter(Begin);
+        else
+          setSentinel(IteratorKind::End);
+        return *this;
+      }
+      case IteratorKind::Element: {
+        auto *DelimiterOrElement = getDelimiterOrElement();
+        assert(DelimiterOrElement);
+        auto *Next = DelimiterOrElement->getNextSibling();
+        if (Next) {
+          setElementOrDelimiter(Next);
+          return *this;
+        }
+        if (getParent()->getTerminationKind() == TerminationKind::Separated &&
+            isDelimiter(DelimiterOrElement))
+          setSentinel(IteratorKind::MissingLastInSeparated);
+        else
+          setSentinel(IteratorKind::End);
+        return *this;
+      }
+      case IteratorKind::MissingLastInSeparated: {
+        setSentinel(IteratorKind::End);
+        return *this;
+      }
+      case IteratorKind::End:
+        llvm_unreachable("Incrementing end iterator.");
+      }
+    }
+
+    ElementAndDelimiterIterator operator++(int) {
+      auto tmp = *this;
+      ++*this;
+      return tmp;
+    }
+
+    // An `operator*` would return an `ElementAndDelimiter`, but it would return
+    // it as a value instead of the expected reference, since this
+    // `ElementAndDelimiter` isn't stored anywhere. Returning a value for the
+    // operator* breaks the specification of a common iterator. As such we
+    // prefer to not provide this operator at all to not create false
+    // expectations on the user.
+    //
+    // Instead we define `getElement()` and `getDelimiter()`.
+
+    /// Returns what you would expect from `It->element`.
+    ElementType *getElement() const {
+      auto *ElementOrDelimiter = getElementOrDelimiter();
+      if (ElementOrDelimiter && isElement(ElementOrDelimiter))
+        return cast<ElementType>(ElementOrDelimiter);
+      return nullptr;
+    }
+
+    /// Returns what you would expect from `It->delimiter`.
+    Leaf *getDelimiter() const {
+      auto *DelimiterOrElement = getDelimiterOrElement();
+      if (DelimiterOrElement && isDelimiter(DelimiterOrElement))
+        return cast<Leaf>(DelimiterOrElement);
+      return nullptr;
+    }
+
+    bool operator==(const ElementAndDelimiterIterator &Other) const {
+      return Opaque == Other.Opaque;
+    }
+
+    bool operator!=(const ElementAndDelimiterIterator &Other) const {
+      return !(*this == Other);
+    }
+
+  private:
+    enum class IteratorKind {
+      BeforeBegin,
+      End,
+      Element,
+      MissingLastInSeparated // Models ElementAndDelimiter = (nullptr, nullptr).
+    };
+
+    // The pointer inside `Opaque` changes semantics according to the
+    // `IteratorKind`. For `NotSentinel` it stores the `Element` or, if the
+    // element is missing, the following `Delimiter`. Otherwise it
+    // stores the `Parent`. Invariant: Opaque != nullptr.
+    llvm::PointerIntPair<Node *, 2, IteratorKind> Opaque;
+
+    void setSentinel(IteratorKind K) {
+      assert(K != IteratorKind::Element);
+      auto *Parent = getParent();
+      Opaque.setPointerAndInt(Parent, K);
+    }
+    void setElementOrDelimiter(Node *EOrD) {
+      Opaque.setPointerAndInt(EOrD, IteratorKind::Element);
+    }
+
+    /// For the current `ElementAndDelimiter` returns the element if it is
+    /// present, otherwise returns the delimiter.
+    ///
+    /// Examples:
+    ///  ElementAndDelimiter | ElementOrDelimiter
+    ///  (Element, Delimiter)| Element
+    ///  (Element, nullptr  )| Element
+    ///  (nullptr, Delimiter)| Delimiter
+    ///  (nullptr, nullptr  )| nullptr
+    Node *getElementOrDelimiter() const {
+      switch (getKind()) {
+      case IteratorKind::Element: {
+        return Opaque.getPointer();
+      }
+      case IteratorKind::MissingLastInSeparated:
+        return nullptr;
+      case IteratorKind::BeforeBegin:
+      case IteratorKind::End:
+        llvm_unreachable("Dereferencing sentinel iterator");
+      }
+    }
+    /// For the current `ElementAndDelimiter` returns the delimiter if it is
+    /// present, otherwise returns the element.
+    Node *getDelimiterOrElement() const {
+      auto *ElementOrDelimiter = getElementOrDelimiter();
+      if (!ElementOrDelimiter)
+        return nullptr;
+      auto *Next = ElementOrDelimiter->getNextSibling();
+      if (isElement(ElementOrDelimiter) && Next && isDelimiter(Next)) {
+        return Next;
+      }
+      return ElementOrDelimiter;
+    }
+    IteratorKind getKind() const { return Opaque.getInt(); }
+
+  public:
+    List *getParent() {
+      switch (getKind()) {
+      case IteratorKind::Element:
+        return cast<List>(getElementOrDelimiter()->getParent());
+      case IteratorKind::BeforeBegin:
+      case IteratorKind::MissingLastInSeparated:
+      case IteratorKind::End:
+        return cast<List>(Opaque.getPointer());
+      }
+    }
+    const List *getParent() const {
+      return const_cast<ElementAndDelimiterIterator *>(this)->getParent();
+    }
+
+  private:
+    ElementAndDelimiterIterator(Node *N, IteratorKind K) : Opaque(N, K) {}
+
+  public:
+    static ElementAndDelimiterIterator<ElementType> beforeBegin(List *Parent) {
+      assert(Parent);
+      return ElementAndDelimiterIterator<ElementType>(
+          Parent, IteratorKind::BeforeBegin);
+    }
+
+    static ElementAndDelimiterIterator<ElementType> begin(List *Parent) {
+      return ++beforeBegin(Parent);
+    }
+
+    static ElementAndDelimiterIterator<ElementType> end(List *Parent) {
+      assert(Parent);
+      return ElementAndDelimiterIterator<ElementType>(Parent,
+                                                      IteratorKind::End);
+    }
+  };
+
+protected:
+  // These function templates are specialized in syntax nodes inheriting from
+  // `List`, according to their `ElementType`s.
+
+  template <typename ElementType>
+  ElementAndDelimiterIterator<ElementType> getElementAndDelimiterBeforeBegin() {
+    return ElementAndDelimiterIterator<ElementType>::beforeBegin(this);
+  }
+  template <typename ElementType>
+  ElementAndDelimiterIterator<ElementType> getElementAndDelimiterBegin() {
+    return ElementAndDelimiterIterator<ElementType>::begin(this);
+  }
+  template <typename ElementType>
+  ElementAndDelimiterIterator<ElementType> getElementAndDelimiterEnd() {
+    return ElementAndDelimiterIterator<ElementType>::end(this);
+  }
+
+  /// Returns the elements of the list, and their corresponding delimiters.
+  /// Missing elements are represented as null pointers.
+  template <typename ElementType>
+  std::vector<ElementAndDelimiter<ElementType>> getElementsAndDelimiters() {
+    std::vector<ElementAndDelimiter<ElementType>> Result;
+    for (auto It = getElementAndDelimiterBegin<ElementType>(),
+              End = getElementAndDelimiterEnd<ElementType>();
+         It != End; ++It)
+      Result.push_back({It.getElement(), It.getDelimiter()});
+    return Result;
+  }
 
   /// Returns the elements of the list. Missing elements are represented
   /// as null pointers in the same way as in the return value of
-  /// `getElementsAsNodesAndDelimiters()`.
+  /// `getElementsAndDelimiters()`.
+  template <typename ElementType> std::vector<ElementType *> getElements() {
+    std::vector<ElementType *> Result;
+    for (auto It = getElementAndDelimiterBegin<ElementType>(),
+              End = getElementAndDelimiterEnd<ElementType>();
+         It != End; ++It)
+      Result.push_back(It.getElement());
+    return Result;
+  }
+
+public:
+  ElementAndDelimiterIterator<Node>
+  getElementsAsNodesAndDelimitersBeforeBegin();
+  ElementAndDelimiterIterator<Node> getElementsAsNodesAndDelimitersBegin();
+  ElementAndDelimiterIterator<Node> getElementsAsNodesAndDelimitersEnd();
+
+  std::vector<ElementAndDelimiter<Node>> getElementsAsNodesAndDelimiters();
   std::vector<Node *> getElementsAsNodes();
 
-  // These can't be implemented with the information we have!
+  enum class TerminationKind {
+    Terminated,
+    MaybeTerminated,
+    Separated,
+  };
+
+  TerminationKind getTerminationKind() const;
 
   /// 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 bool isElement(Node *N);
+  static bool isDelimiter(Node *N);
 };
 
 } // 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));
-  }
-  return Children;
+  return getElements<NameSpecifier>();
 }
 
 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});
-  }
-  return Children;
+  return getElementsAndDelimiters<NameSpecifier>();
 }
 
 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));
-  }
-  return Children;
+  return getElements<Expression>();
 }
 
 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});
-  }
-  return Children;
+  return getElementsAndDelimiters<Expression>();
 }
 
 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));
-  }
-  return Children;
+  return getElements<SimpleDeclaration>();
 }
 
 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) {
-    Children.push_back(
-        {llvm::cast<syntax::SimpleDeclaration>(ParameterAsNodeAndComma.element),
-         ParameterAsNodeAndComma.delimiter});
-  }
-  return Children;
+  return getElementsAndDelimiters<SimpleDeclaration>();
 }
 
 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));
-  }
-  return Children;
+  return getElements<SimpleDeclarator>();
 }
 
 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) {
-    Children.push_back(
-        {llvm::cast<syntax::SimpleDeclarator>(DeclaratorAsNodeAndComma.element),
-         DeclaratorAsNodeAndComma.delimiter});
-  }
-  return Children;
+  return getElementsAndDelimiters<SimpleDeclarator>();
 }
 
 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>(

clang/lib/Tooling/Syntax/Tree.cpp

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::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getElementsAsNodesAndDelimitersBeforeBegin() {
+  return syntax::List::ElementAndDelimiterIterator<syntax::Node>::beforeBegin(
+      this);
+}
+syntax::List::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getElementsAsNodesAndDelimitersBegin() {
+  return syntax::List::ElementAndDelimiterIterator<syntax::Node>::begin(this);
+}
+syntax::List::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getElementsAsNodesAndDelimitersEnd() {
+  return ElementAndDelimiterIterator<syntax::Node>::end(this);
 
-  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;
+// Returns the elements of the list, and their corresponding delimiters.
+// Missing elements are represented as null pointers.
+std::vector<syntax::List::ElementAndDelimiter<syntax::Node>>
+syntax::List::getElementsAsNodesAndDelimiters() {
+  return getElementsAndDelimiters<syntax::Node>();
 }
 
-// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
-// ignoring delimiters
+/// Returns the elements of the list. Missing elements are represented
+/// as null pointers in the same way as in the return value of
+/// `getElementsAndDelimiters()`.
 std::vector<syntax::Node *> syntax::List::getElementsAsNodes() {
-  if (!getFirstChild())
-    return {};
-
-  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.");
-    }
-  }
+  return getElements<syntax::Node>();
+
+/// Expects a List child.
+bool syntax::List::isElement(syntax::Node *N) {
+  assert(N);
+  assert(isa<syntax::List>(N->getParent()));
+  switch (N->getRole()) {
+  case NodeRole::ListElement:
+    return true;
+  case NodeRole::ListDelimiter:
+    return false;
+    llvm_unreachable("List children can only be 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;
-  }
+/// Expects a List child.
+bool syntax::List::isDelimiter(syntax::Node *N) {
+  assert(N);
+  assert(isa<syntax::List>(N->getParent()));
+  switch (N->getRole()) {
+  case NodeRole::ListElement:
+    return false;
+  case NodeRole::ListDelimiter:
+    return true;
+  default:
+    llvm_unreachable("List children can only be elements or delimiters.");
   }
-
-  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:

clang/unittests/Tooling/Syntax/TreeTest.cpp

 //===- TreeTest.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 "TreeTestBase.h"
 #include "clang/Tooling/Syntax/BuildTree.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "llvm/ADT/STLExtras.h"
+#include "llvm/Support/raw_ostream.h"
 #include "gtest/gtest.h"
 
 using namespace clang;
 using namespace clang::syntax;
 
 namespace {
 
 class TreeTest : public SyntaxTreeTest {
std::vector<const Node *> Leafs = {createLeaf(*Arena, tok::l_paren),
                                      createLeaf(*Arena, tok::r_paren)};
   for (const auto *Tree : generateAllTreesWithShape(Leafs, {3u})) {
     ASSERT_TRUE(Tree->findLastLeaf() != nullptr);
     EXPECT_EQ(Tree->findLastLeaf()->getToken()->kind(), tok::r_paren);
   }
 }
 
 class ListTest : public SyntaxTreeTest {
-private:
+protected:
   std::string dumpQuotedTokensOrNull(const Node *N) {
     return N ? "'" +
                    StringRef(N->dumpTokens(Arena->getSourceManager()))
                        .trim()
                        .str() +
                    "'"
              : "null";
   }
 
-protected:
+  std::string
+  dumpElementAndDelimiter(const List::ElementAndDelimiter<Node> ED) {
+    std::string Storage;
+    llvm::raw_string_ostream OS(Storage);
+    OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", "
+       << dumpQuotedTokensOrNull(ED.delimiter) << ")";
+    return OS.str();
+  }
+
   std::string
   dumpElementsAndDelimiters(ArrayRef<List::ElementAndDelimiter<Node>> EDs) {
     std::string Storage;
     llvm::raw_string_ostream OS(Storage);
 
     OS << "[";
 
     llvm::interleaveComma(
         EDs, OS, [&OS, this](const List::ElementAndDelimiter<Node> &ED) {
-          OS << "(" << dumpQuotedTokensOrNull(ED.element) << ", "
-             << dumpQuotedTokensOrNull(ED.delimiter) << ")";
+          OS << dumpElementAndDelimiter(ED);
         });
 
     OS << "]";
 
     return OS.str();
   }
 
   std::string dumpNodes(ArrayRef<Node *> Nodes) {
auto *List = dyn_cast<syntax::List>(syntax::createTree(
       },
       NodeKind::NestedNameSpecifier));
 
   EXPECT_EQ(dumpElementsAndDelimiters(List->getElementsAsNodesAndDelimiters()),
             "[('a', '::'), ('b', '::'), ('c', null)]");
   EXPECT_EQ(dumpNodes(List->getElementsAsNodes()), "['a', 'b', 'c']");
 }
 
+TEST_P(ListTest, List_Terminated_Iterator_Parent) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  buildTree("", GetParam());
+
+  // "a   b::  :: c"
+  auto *List = dyn_cast<syntax::NestedNameSpecifier>(syntax::createTree(
+      *Arena,
+      {
+          {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
+      },
+      NodeKind::NestedNameSpecifier));
+
+  EXPECT_EQ(List->getElementsAsNodesAndDelimitersBeforeBegin().getParent(),
+            List);
+
+  for (auto It = List->getElementsAsNodesAndDelimitersBegin(),
+            End = List->getElementsAsNodesAndDelimitersEnd();
+       It != End; ++It)
+    EXPECT_EQ(It.getParent(), List);
+
+  EXPECT_EQ(List->getElementsAsNodesAndDelimitersEnd().getParent(), List);
+}
+
+TEST_P(ListTest, List_Terminated_Iterator_Equality) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  buildTree("", GetParam());
+
+  // "a   b::  :: c"
+  auto *List = dyn_cast<syntax::NestedNameSpecifier>(syntax::createTree(
+      *Arena,
+      {
+          {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
+      },
+      NodeKind::NestedNameSpecifier));
+
+  // different iterators are different.
+  for (auto BeforeIt = List->getElementsAsNodesAndDelimitersBeforeBegin(),
+            End = List->getElementsAsNodesAndDelimitersEnd();
+       BeforeIt != End; ++BeforeIt) {
+    auto It = BeforeIt;
+    ++It;
+    for (; It != End; ++It) {
+      EXPECT_NE(BeforeIt, It);
+    }
+  }
+
+  // Equal iterators are equal.
+  for (auto It = List->getElementsAsNodesAndDelimitersBegin(),
+            It2 = List->getElementsAsNodesAndDelimitersBegin(),
+            End = List->getElementsAsNodesAndDelimitersEnd();
+       It != End && It2 != End;) {
+    EXPECT_EQ(++It, ++It2);
+  }
+
+  // Different sentinel iterators are different.
+  EXPECT_NE(List->getElementsAsNodesAndDelimitersBeforeBegin(),
+            List->getElementsAsNodesAndDelimitersEnd());
+}
+
+TEST_P(ListTest, List_Separated_Iterator_Parent) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  buildTree("", GetParam());
+
+  // "a  b,  ,"
+  auto *List = dyn_cast<syntax::CallArguments>(syntax::createTree(
+      *Arena,
+      {
+          {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
+      },
+      NodeKind::CallArguments));
+
+  EXPECT_EQ(List->getElementsAsNodesAndDelimitersBeforeBegin().getParent(),
+            List);
+
+  for (auto It = List->getElementsAsNodesAndDelimitersBegin(),
+            End = List->getElementsAsNodesAndDelimitersEnd();
+       It != End; ++It)
+    EXPECT_EQ(It.getParent(), List);
+
+  EXPECT_EQ(List->getElementsAsNodesAndDelimitersEnd().getParent(), List);
+}
+
+TEST_P(ListTest, List_Separated_Iterator_Equality) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  buildTree("", GetParam());
+
+  // "a  b,  ,"
+  auto *List = dyn_cast<syntax::CallArguments>(syntax::createTree(
+      *Arena,
+      {
+          {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::comma), NodeRole::ListDelimiter},
+      },
+      NodeKind::CallArguments));
+
+  // different iterators are different.
+  for (auto BeforeIt = List->getElementsAsNodesAndDelimitersBeforeBegin(),
+            End = List->getElementsAsNodesAndDelimitersEnd();
+       BeforeIt != End; ++BeforeIt) {
+    auto It = BeforeIt;
+    ++It;
+    for (; It != End; ++It) {
+      EXPECT_NE(BeforeIt, It);
+    }
+  }
+
+  // Equal iterators are equal.
+  for (auto It = List->getElementsAsNodesAndDelimitersBegin(),
+            It2 = List->getElementsAsNodesAndDelimitersBegin(),
+            End = List->getElementsAsNodesAndDelimitersEnd();
+       It != End && It2 != End;) {
+    EXPECT_EQ(++It, ++It2);
+  }
+
+  // Different sentinel iterators are different.
+  EXPECT_NE(List->getElementsAsNodesAndDelimitersBeforeBegin(),
+            List->getElementsAsNodesAndDelimitersEnd());
+}
 } // namespace