[Syntax] Add iterators over children of syntax trees.

[sammccall]

Summary

This gives us slightly nicer syntax (foreach) for idioms currently expressed
as a loop, and the option to use range algorithms where it makes sense
(e.g. llvm::all_of et al encapsulate the needed flow control in a useful way).

It's also a building block for iteration over filtered views (e.g. iterate over
all Stmt children, with the right type):
for (const Statement &S : filter<Statement>(N.children()))

...

I realize the recent direction has been mostly towards strongly-typed
node-specific facilities, but I think it's important we have convenient
generic facilities too.

[eduucaldas]

Thanks Sam! I learned a lot from your patch ^^

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

157–184

I think we should only have an iterator through Nodes, not a general one like this.

In general Tree has *heterogeneous* children:
For instance, 1+2 yields the syntax tree:

BinaryOperatorExpression
|-  IntegerLiteralExpression
|-  Leaf
`- IntegerLiteralExpression

Very rarely will syntax trees have all their children of the same kind, so I don't think it makes sense to try an provide an iterator template. That makes sense for lists , because generally they *have* the same kind. But in that case we provide special iterators for lists only.

202–219

TL;DR:
child_iterator -> ChildIterator
const_child_iterator -> ConstChildIterator
children -> getChildren

I see you followed the naming convention of the ClangAST, which makes loads of sense.

In syntax trees we follow the naming conventions of the conding standard -- just because we want consistency and we had to pick a guideline to follow -- according to that, functions should be verb like and names should be camel case.

If like us you chose const_child_iterator and children kind of "just because", could you change it to follow ConstChildIterator and getChildren respectively.

clang/lib/Tooling/Syntax/Tree.cpp

22–23

Hmm...
That looks funny, if the user uses a range-based for loop and forgets the &, then we would be copying the Node???

Also in many places we had to get the address to the node. That is not really consistent with how the syntax trees API's were designed, they generally take pointers instead of references. (that said we could obviously reconsider those design choices)

clang/unittests/Tooling/Syntax/TreeTest.cpp

129

Suggestion:
I would split this into Iterators and ConstIterators.

139

nit, feel free to ignore.

159–169

Is there a reason why you didn't use a range-based for loop over Children?

[sammccall]

Style changes

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

157–184

This does only iterate over nodes, note this class is private.
This is a common pattern when implementing iterators: you need iterator and const_iterator, they have almost identical implementations but operate on different types (const T vs T). Thus a private template.

Sometimes it's used directly (using iterator = iterator_base<Node>) but that means the template needs to be visible and also leads to worse compiler diagnostics when the canonical type is printed. Inheritance lets us prevent direct use of the base class and give the iterator classes distinct names.

---

That said, in future, I think we should (later) have a facility to iterate over children of a certain type. This would explicitly be a filtering operation, ignoring nodes not of that type.
Providing these typed operations for concrete subclasses of List makes sense, but in clangd outside of specific refactorings we've found generic facilities to often be more useful. When we designed syntax trees, providing a simple and generic data structure that could be used directly was an explicit goal.

202–219

In syntax trees we follow the naming conventions of the conding standard

I see that's been used in some of the newer classes, and that you changed this file to follow that style in 4c14ee61b73746b314d83e7c52e03d6527b78105. However it's not the original style we used here and elsewhere in libSyntax.
It's a bit frustrating to hear the argument about consistency, because we were quite careful and deliberate about this style, which was IMO fairly consistent prior to that change.

I'm willing to change these to match the local style in this file. However *_iterator, *_begin/end/range() is more common than FooIterator etc in LLVM overall (I think for consistency with iterator etc, which is endorsed by the style guide). So I don't think this change is particularly an improvement, even in terms of consistency.

clang/lib/Tooling/Syntax/Tree.cpp

22–23

That looks funny, if the user uses a range-based for loop and forgets the &, then we would be copying the Node???

It doesn't look funny to me - foreach usually iterates over values rather than pointers. This raises a good point - it looks like Node is copyable and shouldn't be. (The default copy operation violates the tree invariants, e.g. the copied node will not be a child of its parent). I'll send a patch...

(That said this is always the case with copyable objects in range-based for loops, and indeed using references - that doesn't usually mean we avoid using them)

Also in many places we had to get the address to the node. That is not really consistent with how the syntax trees API's were designed, they generally take pointers instead of references

I'm not convinced that taking the address is itself a burden, any more than using -> instead of . is a burden.
Sometimes the use of pointer vs reference intends to convey something about address stability, but here this goes with the type as all nodes are allocated on the arena. (IMO this is a part of the AST design that works well).
The other thing it conveys is nullability, and this seems valuable enough that IMO APIs that take *non-nullable* nodes by pointer should be reconsidered.

For the iterators specifically, the main alternative here I guess is having Tree::children() act as a container of *pointers to* children, instead of the children themselves. This *is* highly unconventional and surprising. Consider the ubiquitous for (const auto&N : T->children())... now the author/reader expects N to be a const reference to a child, instead it's a const reference to a non-const pointer to a child....

clang/unittests/Tooling/Syntax/TreeTest.cpp

129

Hmm, I'm not a big fan of duplicating all the setup bits. And where would we test that iterators can be converted to an equivalent const_iterator? (This doubles as our implicit test of the multi-pass guarantee, too...)

159–169

I want to be really explicit about the expectation that this yields three elements (as opposed to say zero).

The ElementsAre tests above should disallow that going wrong, but calling the methods once directly with the dumbest possible code seems worthwhile to me.

[gribozavr2]

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

182

"nodePointer()" ?

202–219

It can go either way:

As an exception, classes that mimic STL classes can have member names in STL’s style of lower-case words separated by underscores

210

clang/lib/Tooling/Syntax/Tree.cpp

22–23

That looks funny, if the user uses a range-based for loop and forgets the &, then we would be copying the Node???

Aren't they noncopyable?

[sammccall]

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

182

I find this a little confusing; it suggests to me there's also something *other* than the node here.
What aspect does it help with?

I can live with it, though currently would prefer pointer(), getPointer() or asPointer().

202–219

Yeah, though read narrowly that doesn't apply (Tree doesn't really mimic STL, and the rule applies to Tree::ChildIterator's members rather than the class itself).

I think it's rare enough to spell out iterator class names that those don't matter at all, and getChildren() is necessary given getParent() etc.

clang/lib/Tooling/Syntax/Tree.cpp

22–23

Noncopyable after D90163.

[sammccall]

Simplify ConstChildIterator cross-constructor

[gribozavr2]

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

182

it suggests to me there's also something *other* than the node here.

Not in this case, but there often are other pointers -- LLVM types often have an "opaque pointer" representation, and that was the first thing that I thought about when I read asPointer(). However, it is strongly typed, so one can figure it out. Up to you.

[eduucaldas]

Thanks for the instructive replies

[RKSimon]

@sammccall I've pushed rGc0053c62d9a0 to fix MSVC builds which were struggling to find a default constructor for ConstChildIterator

http://lab.llvm.org:8011/#/builders/83

[sammccall]

Ah, thanks a lot, sorry for missing that!

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/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:
public:
   const Token *getToken() const { return Tok; }
 
 private:
   const Token *Tok;
 };
 
 /// A node that has children and represents a syntactic language construct.
 class Tree : public Node {
+  /// Iterator over children (common base for const/non-const).
+  /// Not invalidated by tree mutations (holds a stable node pointer).
+  template <typename DerivedT, typename NodeT>
+  class child_iterator_base
+      : public llvm::iterator_facade_base<DerivedT, std::forward_iterator_tag,
+                                          NodeT> {
+  protected:
+    NodeT *N = nullptr;
+    using Base = child_iterator_base;
+
+  public:
+    child_iterator_base() = default;
+    explicit child_iterator_base(NodeT *N) : N(N) {}
+
+    bool operator==(const DerivedT &O) const { return O.N == N; }
+    NodeT &operator*() const { return *N; }
+    DerivedT &operator++() {
+      N = N->getNextSibling();
+      return *static_cast<DerivedT *>(this);
+    }
+
+    /// Truthy if valid (not past-the-end).
+    /// This allows: if (auto It = find_first(N.children(), ...) )
+    explicit operator bool() const { return N != nullptr; }
+    /// The element, or nullptr if past-the-end.
+    NodeT *asPointer() const { return N; }
+  };
+
 public:
   using Node::Node;
   static bool classof(const Node *N);
 
   Node *getFirstChild() { return FirstChild; }
   const Node *getFirstChild() const { return FirstChild; }
 
   Leaf *findFirstLeaf();
   const Leaf *findFirstLeaf() const {
     return const_cast<Tree *>(this)->findFirstLeaf();
   }
 
   Leaf *findLastLeaf();
   const Leaf *findLastLeaf() const {
     return const_cast<Tree *>(this)->findLastLeaf();
   }
 
+  /// child_iterator is not invalidated by mutations.
+  struct child_iterator : child_iterator_base<child_iterator, Node> {
+    using Base::Base;
+  };
+  struct const_child_iterator
+      : child_iterator_base<const_child_iterator, const Node> {
+    using Base::Base;
+    const_child_iterator(const child_iterator &I)
+        : Base(I == child_iterator() ? nullptr : &*I) {}
+  };
+
+  llvm::iterator_range<child_iterator> children() {
+    return {child_iterator(getFirstChild()), child_iterator()};
+  }
+  llvm::iterator_range<const_child_iterator> children() const {
+    return {const_child_iterator(getFirstChild()), const_child_iterator()};
+  }
+
 protected:
   /// Find the first node with a corresponding role.
   Node *findChild(NodeRole R);
 
 private:
   /// Prepend \p Child to the list of children and and sets the parent pointer.
   /// A very low-level operation that does not check any invariants, only used
   /// by TreeBuilder and FactoryImpl.
private:
   /// Only used by MutationsImpl to implement higher-level mutation operations.
   /// (!) \p New can be null to model removal of the child range.
   void replaceChildRangeLowLevel(Node *BeforeBegin, Node *End, Node *New);
   friend class MutationsImpl;
 
   Node *FirstChild = nullptr;
 };
 
+// Provide missing non_const == const overload.
+// iterator_facade_base requires == to be a member, but implicit conversions
+// don't work on the LHS of a member operator.
+inline bool operator==(const Tree::const_child_iterator &A,
+                       const Tree::const_child_iterator &B) {
+  return A.operator==(B);
+}
+
 /// 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;

clang/lib/Tooling/Syntax/Tree.cpp

 #include <cassert>
 
 using namespace clang;
 
 namespace {
 static void traverse(const syntax::Node *N,
                      llvm::function_ref<void(const syntax::Node *)> Visit) {
   if (auto *T = dyn_cast<syntax::Tree>(N)) {
-    for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling())
-      traverse(C, Visit);
+    for (const syntax::Node &C : T->children())
+      traverse(&C, Visit);
   }
   Visit(N);
 }
 static void traverse(syntax::Node *N,
                      llvm::function_ref<void(syntax::Node *)> Visit) {
   traverse(static_cast<const syntax::Node *>(N), [&](const syntax::Node *N) {
     Visit(const_cast<syntax::Node *>(N));
   });
if (const auto *L = dyn_cast<syntax::Leaf>(N)) {
     return;
   }
 
   const auto *T = cast<syntax::Tree>(N);
   OS << T->getKind();
   DumpExtraInfo(N);
   OS << "\n";
 
-  for (const auto *It = T->getFirstChild(); It; It = It->getNextSibling()) {
+  for (const syntax::Node &It : T->children()) {
     for (bool Filled : IndentMask) {
       if (Filled)
         OS << "| ";
       else
         OS << "  ";
     }
-    if (!It->getNextSibling()) {
+    if (!It.getNextSibling()) {
       OS << "`-";
       IndentMask.push_back(false);
     } else {
       OS << "|-";
       IndentMask.push_back(true);
     }
-    dumpNode(OS, It, SM, IndentMask);
+    dumpNode(OS, &It, SM, IndentMask);
     IndentMask.pop_back();
   }
 }
 } // namespace
 
 std::string syntax::Node::dump(const SourceManager &SM) const {
   std::string Str;
   llvm::raw_string_ostream OS(Str);
#ifndef NDEBUG
   if (isDetached())
     assert(getParent() == nullptr);
   else
     assert(getParent() != nullptr);
 
   const auto *T = dyn_cast<Tree>(this);
   if (!T)
     return;
-  for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
+  for (const Node &C : T->children()) {
     if (T->isOriginal())
-      assert(C->isOriginal());
-    assert(!C->isDetached());
-    assert(C->getParent() == T);
+      assert(C.isOriginal());
+    assert(!C.isDetached());
+    assert(C.getParent() == T);
   }
 
   const auto *L = dyn_cast<List>(T);
   if (!L)
     return;
-  for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
-    assert(C->getRole() == NodeRole::ListElement ||
-           C->getRole() == NodeRole::ListDelimiter);
-    if (C->getRole() == NodeRole::ListDelimiter) {
+  for (const Node &C : T->children()) {
+    assert(C.getRole() == NodeRole::ListElement ||
+           C.getRole() == NodeRole::ListDelimiter);
+    if (C.getRole() == NodeRole::ListDelimiter) {
       assert(isa<Leaf>(C));
-      assert(cast<Leaf>(C)->getToken()->kind() == L->getDelimiterTokenKind());
+      assert(cast<Leaf>(C).getToken()->kind() == L->getDelimiterTokenKind());
     }
   }
 
 #endif
 }
 
 void syntax::Node::assertInvariantsRecursive() const {
 #ifndef NDEBUG
   traverse(this, [&](const syntax::Node *N) { N->assertInvariants(); });
 #endif
 }
 
 syntax::Leaf *syntax::Tree::findFirstLeaf() {
-  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
-    if (auto *L = dyn_cast<syntax::Leaf>(C))
+  for (Node &C : children()) {
+    if (auto *L = dyn_cast<syntax::Leaf>(&C))
       return L;
-    if (auto *L = cast<syntax::Tree>(C)->findFirstLeaf())
+    if (auto *L = cast<syntax::Tree>(C).findFirstLeaf())
       return L;
   }
   return nullptr;
 }
 
 syntax::Leaf *syntax::Tree::findLastLeaf() {
   syntax::Leaf *Last = nullptr;
-  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
-    if (auto *L = dyn_cast<syntax::Leaf>(C))
+  for (Node &C : children()) {
+    if (auto *L = dyn_cast<syntax::Leaf>(&C))
       Last = L;
-    else if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+    else if (auto *L = cast<syntax::Tree>(C).findLastLeaf())
       Last = L;
   }
   return Last;
 }
 
 syntax::Node *syntax::Tree::findChild(NodeRole R) {
-  for (auto *C = FirstChild; C; C = C->getNextSibling()) {
-    if (C->getRole() == R)
-      return C;
+  for (Node &C : children()) {
+    if (C.getRole() == R)
+      return &C;
   }
   return nullptr;
 }
 
 bool syntax::List::classof(const syntax::Node *N) {
   switch (N->getKind()) {
   case syntax::NodeKind::NestedNameSpecifier:
   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()) {
+  for (Node &C : children()) {
+    switch (C.getRole()) {
     case syntax::NodeRole::ListElement: {
       if (ElementWithoutDelimiter) {
         Children.push_back({ElementWithoutDelimiter, nullptr});
       }
-      ElementWithoutDelimiter = C;
+      ElementWithoutDelimiter = &C;
       break;
     }
     case syntax::NodeRole::ListDelimiter: {
-      Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(C)});
+      Children.push_back({ElementWithoutDelimiter, cast<syntax::Leaf>(&C)});
       ElementWithoutDelimiter = nullptr;
       break;
     }
     default:
       llvm_unreachable(
           "A list can have only elements and delimiters as children.");
     }
   }

 // 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()) {
+  for (Node &C : children()) {
+    switch (C.getRole()) {
     case syntax::NodeRole::ListElement: {
       if (ElementWithoutDelimiter) {
         Children.push_back(ElementWithoutDelimiter);
       }
-      ElementWithoutDelimiter = C;
+      ElementWithoutDelimiter = &C;
       break;
     }
     case syntax::NodeRole::ListDelimiter: {
       Children.push_back(ElementWithoutDelimiter);
       ElementWithoutDelimiter = nullptr;
       break;
     }
     default:

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/Basic/SourceManager.h"
 #include "clang/Tooling/Syntax/BuildTree.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "llvm/ADT/STLExtras.h"
 #include "gtest/gtest.h"
 
 using namespace clang;
 using namespace clang::syntax;
 
 namespace {
+using testing::ElementsAre;
 
 class TreeTest : public SyntaxTreeTest {
 private:
   Tree *createTree(ArrayRef<const Node *> Children) {
     std::vector<std::pair<Node *, NodeRole>> ChildrenWithRoles;
     ChildrenWithRoles.reserve(Children.size());
     for (const auto *Child : Children) {
       ChildrenWithRoles.push_back(std::make_pair(
TEST_P(TreeTest, LastLeaf) {
   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);
   }
 }
 
+TEST_F(TreeTest, Iterators) {
+  buildTree("", allTestClangConfigs().front());
+  std::vector<Node *> Children = {createLeaf(*Arena, tok::identifier, "a"),
+                                  createLeaf(*Arena, tok::identifier, "b"),
+                                  createLeaf(*Arena, tok::identifier, "c")};
+  auto *Tree = syntax::createTree(*Arena,
+                                  {{Children[0], NodeRole::LeftHandSide},
+                                   {Children[1], NodeRole::OperatorToken},
+                                   {Children[2], NodeRole::RightHandSide}},
+                                  NodeKind::TranslationUnit);
+  const syntax::Tree *ConstTree = Tree;
+
+  auto Range = Tree->children();
+  EXPECT_THAT(Range, ElementsAre(role(NodeRole::LeftHandSide),
+                                 role(NodeRole::OperatorToken),
+                                 role(NodeRole::RightHandSide)));
+
+  auto ConstRange = ConstTree->children();
+  EXPECT_THAT(ConstRange, ElementsAre(role(NodeRole::LeftHandSide),
+                                      role(NodeRole::OperatorToken),
+                                      role(NodeRole::RightHandSide)));
+
+  // FIXME: mutate and observe no invalidation. Mutations are private for now...
+  auto It = Range.begin();
+  auto CIt = ConstRange.begin();
+  static_assert(std::is_same<decltype(*It), syntax::Node &>::value,
+                "mutable range");
+  static_assert(std::is_same<decltype(*CIt), const syntax::Node &>::value,
+                "const range");
+
+  for (unsigned I = 0; I < 3; ++I) {
+    EXPECT_EQ(It, CIt);
+    EXPECT_TRUE(It);
+    EXPECT_TRUE(CIt);
+    EXPECT_EQ(It.asPointer(), Children[I]);
+    EXPECT_EQ(CIt.asPointer(), Children[I]);
+    EXPECT_EQ(&*It, Children[I]);
+    EXPECT_EQ(&*CIt, Children[I]);
+    ++It;
+    ++CIt;
+  }
+  EXPECT_EQ(It, CIt);
+  EXPECT_EQ(It, Tree::child_iterator());
+  EXPECT_EQ(CIt, Tree::const_child_iterator());
+  EXPECT_FALSE(It);
+  EXPECT_FALSE(CIt);
+  EXPECT_EQ(nullptr, It.asPointer());
+  EXPECT_EQ(nullptr, CIt.asPointer());
+}
+
 class ListTest : public SyntaxTreeTest {
 private:
   std::string dumpQuotedTokensOrNull(const Node *N) {
     return N ? "'" +
                    StringRef(N->dumpTokens(Arena->getSourceManager()))
                        .trim()
                        .str() +
                    "'"

clang/unittests/Tooling/Syntax/TreeTestBase.h

 
 #include "clang/Basic/LLVM.h"
 #include "clang/Frontend/CompilerInvocation.h"
 #include "clang/Testing/TestClangConfig.h"
 #include "clang/Tooling/Syntax/Nodes.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "clang/Tooling/Syntax/Tree.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/Support/ScopedPrinter.h"
 #include "llvm/Testing/Support/Annotations.h"
+#include "gmock/gmock.h"
 #include "gtest/gtest.h"
 
 namespace clang {
 namespace syntax {
 class SyntaxTreeTest : public ::testing::Test,
                        public ::testing::WithParamInterface<TestClangConfig> {
 protected:
   // Build a syntax tree for the code.
IntrusiveRefCntPtr<SourceManager> SourceMgr =
       new SourceManager(*Diags, *FileMgr);
   std::shared_ptr<CompilerInvocation> Invocation;
   // Set after calling buildTree().
   std::unique_ptr<syntax::TokenBuffer> TB;
   std::unique_ptr<syntax::Arena> Arena;
 };
 
 std::vector<TestClangConfig> allTestClangConfigs();
+
+MATCHER_P(role, R, "") {
+  if (arg.getRole() == R)
+    return true;
+  *result_listener << "role is " << llvm::to_string(arg.getRole());
+  return false;
+}
+
 } // namespace syntax
 } // namespace clang
 #endif // LLVM_CLANG_UNITTESTS_TOOLING_SYNTAX_TREETESTBASE_H