[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

242–277

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?

279–280

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?

441–448

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

[gribozavr2]

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

212

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

229

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

242–277

I think it is fine as is.

273

Please also define operator!=.

287

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.

443

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

clang/lib/Tooling/Syntax/Tree.cpp

331

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

340–345

348

Ditto?

[eduucaldas]

Answer comments, TODO: think about templated iterators

[eduucaldas]

• Make ElementAndDelimiterIterator templated.

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

273

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

clang/lib/Tooling/Syntax/Tree.cpp

348

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

242–243

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

242–243

Ignore comment above

253

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.

391

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>
+#include <iterator>
 
 namespace clang {
 namespace syntax {
 
 /// A memory arena for syntax trees. Also tracks the underlying token buffers,
 /// source manager, etc.
 class Arena {
 public:

 ///
 /// 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)]
+  ///
+  /// NOTE: This iterator *should* be a forward 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 std::iterator<std::input_iterator_tag,
+                             ElementAndDelimiter<ElementType>, ptrdiff_t,
+                             const ElementAndDelimiter<ElementType> *,
+                             ElementAndDelimiter<ElementType>> {
+  public:
+    ElementAndDelimiterIterator &operator++() {
+      assert(Kind != IteratorKind::End && "Incrementing end iterator.");
+      if (Kind == IteratorKind::BeforeBegin) {
+        if (auto *Begin = Parent->getFirstChild()) {
+          Kind = IteratorKind::NotSentinel;
+          if (isElement(Begin))
+            Current = getWithDelimiter(cast<ElementType>(Begin));
+          else
+            Current = {nullptr, cast<Leaf>(Begin)};
+        } else
+          Kind = IteratorKind::End;
+      } else {
+        auto Next = [](ElementAndDelimiter<ElementType> ED)
+            -> llvm::Optional<ElementAndDelimiter<ElementType>> {
+          auto *N = ED.element ? ED.element : ED.delimiter;
+          if (!N)
+            return None;
+          if (isElement(N))
+            return getElementAndDelimiterAfterElement(cast<ElementType>(N));
+          return getElementAndDelimiterAfterDelimiter(cast<Leaf>(N));
+        }(Current);
+        if (Next.hasValue())
+          Current = Next.getValue();
+        else
+          Kind = IteratorKind::End;
+      }
+      return *this;
+    }
+    ElementAndDelimiterIterator operator++(int) {
+      auto tmp = *this;
+      ++*this;
+      return tmp;
+    }
+
+    ElementAndDelimiter<ElementType> operator*() const {
+      assert(Kind == IteratorKind::NotSentinel &&
+             "Dereferencing sentinel iterator.");
+      return Current;
+    }
+
+    bool operator==(const ElementAndDelimiterIterator &Other) const {
+      return (Parent == Other.Parent && Kind == Other.Kind &&
+              (Kind != IteratorKind::NotSentinel || Current == Other.Current));
+    }
+
+    bool operator!=(const ElementAndDelimiterIterator &Other) const {
+      return !(*this == Other);
+    }
+
+  private:
+    enum class IteratorKind { BeforeBegin, End, NotSentinel };
+
+    List *Parent;
+    IteratorKind Kind;
+    // If `Kind != NotSentinel`, then `Current` has trash.
+    ElementAndDelimiter<ElementType> Current;
+
+  public:
+    List *getParent() { return Parent; }
+    const List *getParent() const { return Parent; }
+
+    bool isEnd() const { return Kind == IteratorKind::End; };
+    bool isBeforeBegin() const { return Kind == IteratorKind::BeforeBegin; };
+    bool isSentinel() const { return Kind != IteratorKind::NotSentinel; };
+
+    static ElementAndDelimiterIterator<ElementType> makeEnd(List *Parent) {
+      assert(Parent);
+      ElementAndDelimiterIterator<ElementType> It;
+      It.Parent = Parent;
+      It.Kind = IteratorKind::End;
+      return It;
+    }
+
+    static ElementAndDelimiterIterator<ElementType>
+    makeBeforeBegin(List *Parent) {
+      assert(Parent);
+      ElementAndDelimiterIterator<ElementType> It;
+      It.Parent = Parent;
+      It.Kind = IteratorKind::BeforeBegin;
+      return It;
+    }
+
+  private:
+    static ElementAndDelimiter<ElementType>
+    getWithDelimiter(ElementType *Element) {
+      assert(Element && isElement(Element));
+      auto *Next = Element->getNextSibling();
+      if (!Next)
+        return {Element, nullptr};
+
+      if (isElement(Next))
+        return {Element, nullptr};
+      if (isDelimiter(Next))
+        return {Element, cast<Leaf>(Next)};
+
+      llvm_unreachable(
+          "A list can have only elements and delimiters as children.");
+    }
+
+    static llvm::Optional<ElementAndDelimiter<ElementType>>
+    getElementAndDelimiterAfterDelimiter(Leaf *Delimiter) {
+      assert(Delimiter && isDelimiter(Delimiter));
+      auto *L = cast<List>(Delimiter->getParent());
+      auto *Next = Delimiter->getNextSibling();
+      if (!Next) {
+        switch (L->getTerminationKind()) {
+        // List is separated and ends with delimiter
+        // => missing last ElementAndDelimiter.
+        case TerminationKind::Separated:
+          return llvm::Optional<ElementAndDelimiter<ElementType>>(
+              {nullptr, nullptr});
+        case TerminationKind::Terminated:
+        case TerminationKind::MaybeTerminated:
+          return None;
+        }
+      }
+      if (isElement(Next))
+        return getWithDelimiter(cast<ElementType>(Next));
+
+      // Consecutive Delimiters => missing Element
+      if (isDelimiter(Next))
+        return llvm::Optional<ElementAndDelimiter<ElementType>>(
+            {nullptr, cast<Leaf>(Next)});
+      llvm_unreachable(
+          "A list can have only elements and delimiters as children.");
+    }
+
+    static llvm::Optional<ElementAndDelimiter<ElementType>>
+    getElementAndDelimiterAfterElement(ElementType *Element) {
+      assert(Element && isElement(Element));
+      auto *Next = Element->getNextSibling();
+      if (!Next)
+        // This was the last element of the list.
+        return None;
+
+      if (isElement(Next))
+        // We have something of the form "a b ..." => 'b' starts the next
+        // `ElementAndDelimiter`.
+        return getWithDelimiter(cast<ElementType>(Next));
+      if (isDelimiter(Next))
+        // We have something of the form "a , ..." => whatever comes after the
+        // comma starts the next `ElementAndDelimiter`.
+        return getElementAndDelimiterAfterDelimiter(cast<Leaf>(Next));
+
+      llvm_unreachable(
+          "A list can have only elements and delimiters as children.");
+    }
+  };
+
+  ElementAndDelimiterIterator<Node> getBeforeBegin();
+  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 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));
-  }
+  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

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.");
-    }
-  }
+bool syntax::List::isElement(syntax::Node *N) {
+  return N && N->getRole() == NodeRole::ListElement;
 
-  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;
-  }
-  }
+bool syntax::List::isDelimiter(syntax::Node *N) {
+  return N && N->getRole() == NodeRole::ListDelimiter;
 
-  return Children;
+syntax::List::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getBeforeBegin() {
+  return ElementAndDelimiterIterator<Node>::makeBeforeBegin(this);
 }
 
-// Almost the same implementation of `getElementsAsNodesAndDelimiters` but
-// ignoring delimiters
-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.");
-    }
-  }
+syntax::List::ElementAndDelimiterIterator<syntax::Node>
+syntax::List::getBeginNode() {
+  return std::next(ElementAndDelimiterIterator<Node>::makeBeforeBegin(this));
 
-  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 ElementAndDelimiterIterator<Node>::makeEnd(this);
+
+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:

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_Iterator_StableDereference) {
+  if (!GetParam().isCXX()) {
+    return;
+  }
+  buildTree("", GetParam());
+
+  // "a:: b:: c"
+  auto *List = dyn_cast<syntax::List>(syntax::createTree(
+      *Arena,
+      {
+          {createLeaf(*Arena, tok::identifier, "a"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::identifier, "b"), NodeRole::ListElement},
+          {createLeaf(*Arena, tok::coloncolon), NodeRole::ListDelimiter},
+          {createLeaf(*Arena, tok::identifier, "c"), NodeRole::ListElement},
+      },
+      NodeKind::NestedNameSpecifier));
+
+  auto It = List->getBeginNode();
+  const auto &First = *It;
+  auto ItAssign = It;
+
+  EXPECT_EQ(dumpElementAndDelimiter(First), "('a', '::')");
+  ++It;
+  EXPECT_EQ(dumpElementAndDelimiter(First), "('a', '::')");
+
+  EXPECT_EQ(*ItAssign, First);
+
+  auto It2 = std::next(List->getBeforeBegin(), 2);
+  EXPECT_EQ(It, It2);
+  EXPECT_EQ(*It, *It2);
+
+  ++It;
+  ++It;
+  EXPECT_EQ(It, List->getEndNode());
+}
 } // namespace