[SyntaxTree] Add reverse links to syntax Nodes.

[eduucaldas]

Summary

Children of a syntax tree had forward links only, because there was no need for reverse links.

This need appeared when we started mutating the syntax tree.
On a forward list, to remove a target node in O(1) we need a pointer to the node before the target. If we don't have this "before" pointer, we have to find it, and that requires O(n).

So in order to remove a syntax node from a tree, we would similarly need to find the node before to then remove. This is both not ergonomic nor does it have a good complexity.

[eduucaldas]

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

257–258

Should we provide an appendChildLowLevel as well?

That has one use inside foldChildren in BuildTree.cpp.
Currently this function does a reverse iteration prepending children. We could change that into a forward iteration appending. There is no impact in time-complexity. This change would just improve readability inside this function.

[gribozavr2]

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

257–258

There is some awkwardness in foldChildren because we can only go in reverse -- maybe append is indeed more natural.

clang/lib/Tooling/Syntax/Tree.cpp

126

Do you plan to remove BeforeBegin argument (in a follow-up if you prefer, but you could also change it here)

291

I think you could fold this check into the for loop below.

[sammccall]

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

121

(Not something to change in this patch...)
Since adding the "get" prefixes, getNextSibling() and now getPreviousSibling() are pretty verbose, we might consider getNext()/getPrevious()

257–258

Consider insert(Node *Child, const Node *Before) where Before=Null means append.

This is fairly ergonomic for common cases:

• append: insert(N, null)
• prepend: insert(N, N->firstChild())
• insert-before: insert(N, M)
• insert-after: insert(N, M->nextSibling())

(Either before or after works fine, before matches STL insert better)

[eduucaldas]

• replaceChildRangeLowLevel now takes Begin instead of BeforeBegin
• appendChildLowLevel

[eduucaldas]

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

121

I agree

257–258

That is great, but we have even a superset of this:
replaceChildRangeLowLevel(Node* BeforeBegin, Node* End, Node* New)
where:
insert(Child, Before) = replaceChildRangeLowLevel(Before, Before->getNextSibling(), Child)

I think the point of having append and prepend is that until now that's what builders need, and such a specialization carries more semantics.

For the mutations API, where we need this kind of capability we provide replaceChildRangeLowLevel.

257–258

I replace every place where we did a reverse iteration prepending for a normal iteration appending, and now there are no more users of prepend ^^.

I propose we keep it anyways, we have bidirection list, makes sense to have both.

[sammccall]

LG from my side.

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

257–258

I'm not sure this is the right set of operations, but as long as it's private it's probably not worth worrying too much about.
(By the same token, I think unused functions should be dropped, but up to you).

Let's revisit if we add a public mutation API.

[gribozavr2]

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

121

I like having the word "sibling" in the name -- getNext() makes me wonder, "next what?"

If this was an iterator abstraction where next/previous are core to the meaning, sure, but a tree node is more complex.

253

This is a complete nitpick, but could you put append before prepend? I think a lot more people are interested in append. Same in the two overloads below.

257–258

That is great, but we have even a superset of this:

I mean, if we intend to provide a convenient API, adding insert would make sense even if it is not needed right now. From the industry experience with containers, we know that replace, insert, append, prepend are all common operations, and even though all of them can be expressed with just replace, people like to use specialized operations as that expresses the intent better.

OTOH, it seems like the design here is that mutations are provided by the MutationsImpl class, so any such convenience operation needs to be implemented there.

266

It would be great to document that nullptr in Begin or End mean the one-past-end position.

clang/lib/Tooling/Syntax/BuildTree.cpp

639–640

Remove the comment?

clang/lib/Tooling/Syntax/Synthesis.cpp

204

Use a range-based for loop?

clang/lib/Tooling/Syntax/Tree.cpp

128–129

Seems like Begin==nullptr is only allowed when this subtree has no children. I'd think that Begin==End==nullptr is a valid way to append children even to non-empty trees.

Do we have tests for this function? Would be really good to add that case.

159

169–171

Thinking about the semantics of this operation, do we need to break the sibling links in the range that is being removed? We expect the sibling links to be established in the new range. That's a suspicious asymmetry.

178

[eduucaldas]

Rebase to include ChildIterator patch.

[eduucaldas]

This comment was removed by eduucaldas.

[eduucaldas]

Answered all comments but:

• Add tests for replaceChildRangeLowLevel
• Asymmetry of replaceChildRangeLowLevel, do we need to separate children of the replaced range?

[eduucaldas]

Rebase

[eduucaldas]

As we discussed offline we will probably not provide replaceChildRange in the public mutations API anymore.

As a result I don't think we should be chaining changes related to replaceChildRange in this patch, and thus it should be ready to go.

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

public:
   /// modifiable.
   bool canModify() const { return CanModify; }
 
   const Tree *getParent() const { return Parent; }
   Tree *getParent() { return Parent; }
 
   const Node *getNextSibling() const { return NextSibling; }
   Node *getNextSibling() { return NextSibling; }
+  const Node *getPreviousSibling() const { return PreviousSibling; }
+  Node *getPreviousSibling() { return PreviousSibling; }
 
   /// Dumps the structure of a subtree. For debugging and testing purposes.
   std::string dump(const SourceManager &SM) const;
   /// Dumps the tokens forming this subtree.
   std::string dumpTokens(const SourceManager &SM) const;
 
   /// Asserts invariants on this node of the tree and its immediate children.
   /// Will not recurse into the subtree. No-op if NDEBUG is set.
private:
   friend class MutationsImpl;
   // FactoryImpl sets CanModify flag.
   friend class FactoryImpl;
 
   void setRole(NodeRole NR);
 
   Tree *Parent;
   Node *NextSibling;
+  Node *PreviousSibling;
   unsigned Kind : 16;
   unsigned Role : 8;
   unsigned Original : 1;
   unsigned CanModify : 1;
 };
 
 /// A leaf node points to a single token inside the expanded token stream.
 class Leaf final : public Node {
 public:
   Leaf(const Token *T);
   static bool classof(const Node *N);
 
   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 ChildIteratorBase
-      : public llvm::iterator_facade_base<DerivedT, std::forward_iterator_tag,
-                                          NodeT> {
+      : public llvm::iterator_facade_base<
+            DerivedT, std::bidirectional_iterator_tag, NodeT> {
   protected:
     NodeT *N = nullptr;
     using Base = ChildIteratorBase;
 
   public:
     ChildIteratorBase() = default;
     explicit ChildIteratorBase(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);
     }
+    DerivedT &operator--() {
+      N = N->getPreviousSibling();
+      return *static_cast<DerivedT *>(this);
+    }
 
     /// Truthy if valid (not past-the-end).
     /// This allows: if (auto It = find_if(N.children(), ...) )
     explicit operator bool() const { return N != nullptr; }
     /// The element, or nullptr if past-the-end.
     NodeT *asPointer() const { return N; }
   };
 
 public:
   static bool classof(const Node *N);
 
   Node *getFirstChild() { return FirstChild; }
   const Node *getFirstChild() const { return FirstChild; }
+  Node *getLastChild() { return LastChild; }
+  const Node *getLastChild() const { return LastChild; }
 
   const Leaf *findFirstLeaf() const;
   Leaf *findFirstLeaf() {
     return const_cast<Leaf *>(const_cast<const Tree *>(this)->findFirstLeaf());
   }
 
   const Leaf *findLastLeaf() const;
   Leaf *findLastLeaf() {
public:
   Node *findChild(NodeRole R) {
     return const_cast<Node *>(const_cast<const Tree *>(this)->findChild(R));
   }
 
 protected:
   using Node::Node;
 
 private:
-  /// Prepend \p Child to the list of children and and sets the parent pointer.
+  /// Prepend \p Child to the list of children and sets the parent pointer.
   /// A very low-level operation that does not check any invariants, only used
   /// by TreeBuilder and FactoryImpl.
   /// EXPECTS: Role != Detached.
   void prependChildLowLevel(Node *Child, NodeRole Role);
-  /// Like the previous overload, but does not set role for \p Child.
+  /// Similar but appends.
+  void appendChildLowLevel(Node *Child, NodeRole Role);
+
+  /// Like the previous overloads, but does not set role for \p Child.
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
+  void appendChildLowLevel(Node *Child);
   friend class TreeBuilder;
   friend class FactoryImpl;
 
-  /// Replace a range of children [BeforeBegin->NextSibling, End) with a list of
+  /// Replace a range of children [Begin, End) with a list of
   /// new nodes starting at \p New.
   /// 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);
+  void replaceChildRangeLowLevel(Node *Begin, Node *End, Node *New);
   friend class MutationsImpl;
 
   Node *FirstChild = nullptr;
+  Node *LastChild = 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::ConstChildIterator &A,
                        const Tree::ConstChildIterator &B) {
   return A.operator==(B);

clang/lib/Tooling/Syntax/BuildTree.cpp

void foldChildren(const syntax::Arena &A, ArrayRef<syntax::Token> Tokens,
       assert((BeginChildren == Trees.end() ||
               BeginChildren->first == FirstToken) &&
              "fold crosses boundaries of existing subtrees");
       auto EndChildren = Trees.lower_bound(Tokens.end());
       assert(
           (EndChildren == Trees.end() || EndChildren->first == Tokens.end()) &&
           "fold crosses boundaries of existing subtrees");
 
       // We need to go in reverse order, because we can only prepend.
-      for (auto It = EndChildren; It != BeginChildren; --It) {
-        auto *C = std::prev(It)->second;
+      for (auto It = BeginChildren; It != EndChildren; ++It) {
+        auto *C = It->second;
         if (C->getRole() == NodeRole::Detached)
           C->setRole(NodeRole::Unknown);
-        Node->prependChildLowLevel(C);
+        Node->appendChildLowLevel(C);
       }
 
       // Mark that this node came from the AST and is backed by the source code.
       Node->Original = true;
       Node->CanModify =
           A.getTokenBuffer().spelledForExpanded(Tokens).hasValue();
 
       Trees.erase(BeginChildren, EndChildren);

clang/lib/Tooling/Syntax/Mutations.cpp

 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Casting.h"
 #include <cassert>
 #include <string>
 
 using namespace clang;
 
-static syntax::Node *findPrevious(syntax::Node *N) {
-  assert(N);
-  assert(N->getParent());
-  if (N->getParent()->getFirstChild() == N)
-    return nullptr;
-  for (syntax::Node *C = N->getParent()->getFirstChild(); C != nullptr;
-       C = C->getNextSibling()) {
-    if (C->getNextSibling() == N)
-      return C;
-  }
-  llvm_unreachable("could not find a child node");
-}
-
 // This class has access to the internals of tree nodes. Its sole purpose is to
 // define helpers that allow implementing the high-level mutation operations.
 class syntax::MutationsImpl {
 public:
   /// Add a new node with a specified role.
   static void addAfter(syntax::Node *Anchor, syntax::Node *New, NodeRole Role) {
     assert(Anchor != nullptr);
     assert(Anchor->Parent != nullptr);
     assert(New->Parent == nullptr);
     assert(New->NextSibling == nullptr);
+    assert(New->PreviousSibling == nullptr);
     assert(New->isDetached());
     assert(Role != NodeRole::Detached);
 
     New->setRole(Role);
     auto *P = Anchor->getParent();
-    P->replaceChildRangeLowLevel(Anchor, Anchor->getNextSibling(), New);
+    P->replaceChildRangeLowLevel(Anchor->getNextSibling(),
+                                 Anchor->getNextSibling(), New);
 
     P->assertInvariants();
   }
 
   /// Replace the node, keeping the role.
   static void replace(syntax::Node *Old, syntax::Node *New) {
     assert(Old != nullptr);
     assert(Old->Parent != nullptr);
     assert(Old->canModify());
     assert(New->Parent == nullptr);
     assert(New->NextSibling == nullptr);
+    assert(New->PreviousSibling == nullptr);
     assert(New->isDetached());
 
     New->Role = Old->Role;
     auto *P = Old->getParent();
-    P->replaceChildRangeLowLevel(findPrevious(Old), Old->getNextSibling(), New);
+    P->replaceChildRangeLowLevel(Old, Old->getNextSibling(), New);
 
     P->assertInvariants();
   }
 
   /// Completely remove the node from its parent.
   static void remove(syntax::Node *N) {
     assert(N != nullptr);
     assert(N->Parent != nullptr);
     assert(N->canModify());
 
     auto *P = N->getParent();
-    P->replaceChildRangeLowLevel(findPrevious(N), N->getNextSibling(),
+    P->replaceChildRangeLowLevel(N, N->getNextSibling(),
                                  /*New=*/nullptr);
 
     P->assertInvariants();
     N->assertInvariants();
   }
 };
 
 void syntax::removeStatement(syntax::Arena &A, syntax::Statement *S) {

clang/lib/Tooling/Syntax/Synthesis.cpp

 class clang::syntax::FactoryImpl {
 public:
   static void setCanModify(syntax::Node *N) { N->CanModify = true; }
 
   static void prependChildLowLevel(syntax::Tree *T, syntax::Node *Child,
                                    syntax::NodeRole R) {
     T->prependChildLowLevel(Child, R);
   }
+  static void appendChildLowLevel(syntax::Tree *T, syntax::Node *Child,
+                                  syntax::NodeRole R) {
+    T->appendChildLowLevel(Child, R);
+  }
 
   static std::pair<FileID, ArrayRef<Token>>
   lexBuffer(syntax::Arena &A, std::unique_ptr<llvm::MemoryBuffer> Buffer) {
     return A.lexBuffer(std::move(Buffer));
   }
 };
 
 // FIXME: `createLeaf` is based on `syntax::tokenize` internally, as such it

 } // namespace
 
 syntax::Tree *clang::syntax::createTree(
     syntax::Arena &A,
     ArrayRef<std::pair<syntax::Node *, syntax::NodeRole>> Children,
     syntax::NodeKind K) {
   auto *T = allocateTree(A, K);
   FactoryImpl::setCanModify(T);
-  for (auto ChildIt = Children.rbegin(); ChildIt != Children.rend(); ++ChildIt)
-    FactoryImpl::prependChildLowLevel(T, ChildIt->first, ChildIt->second);
+  for (const auto *ChildIt = Children.begin(); ChildIt != Children.end();
+       ++ChildIt)
+    FactoryImpl::appendChildLowLevel(T, ChildIt->first, ChildIt->second);
 
   T->assertInvariants();
   return T;
 }
 
 syntax::Node *clang::syntax::deepCopyExpandingMacros(syntax::Arena &A,
                                                      const syntax::Node *N) {
   if (const auto *L = dyn_cast<syntax::Leaf>(N))

clang/lib/Tooling/Syntax/Tree.cpp

syntax::Leaf::Leaf(const syntax::Token *Tok) : Node(NodeKind::Leaf), Tok(Tok) {
   assert(Tok != nullptr);
 }
 
 bool syntax::Leaf::classof(const Node *N) {
   return N->getKind() == NodeKind::Leaf;
 }
 
 syntax::Node::Node(NodeKind Kind)
-    : Parent(nullptr), NextSibling(nullptr), Kind(static_cast<unsigned>(Kind)),
-      Role(0), Original(false), CanModify(false) {
+    : Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+      Kind(static_cast<unsigned>(Kind)), Role(0), Original(false),
+      CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
 bool syntax::Node::isDetached() const {
   return getRole() == NodeRole::Detached;
 }
 
 void syntax::Node::setRole(NodeRole NR) {
   this->Role = static_cast<unsigned>(NR);
 }
 
 bool syntax::Tree::classof(const Node *N) {
   return N->getKind() > NodeKind::Leaf;
 }
 
+void syntax::Tree::appendChildLowLevel(Node *Child, NodeRole Role) {
+  assert(Child->getRole() == NodeRole::Detached);
+  assert(Role != NodeRole::Detached);
+
+  Child->setRole(Role);
+  appendChildLowLevel(Child);
+}
+
+void syntax::Tree::appendChildLowLevel(Node *Child) {
+  assert(Child->Parent == nullptr);
+  assert(Child->NextSibling == nullptr);
+  assert(Child->PreviousSibling == nullptr);
+  assert(Child->getRole() != NodeRole::Detached);
+
+  Child->Parent = this;
+  if (this->LastChild) {
+    Child->PreviousSibling = this->LastChild;
+    this->LastChild->NextSibling = Child;
+  } else
+    this->FirstChild = Child;
+
+  this->LastChild = Child;
+}
+
 void syntax::Tree::prependChildLowLevel(Node *Child, NodeRole Role) {
   assert(Child->getRole() == NodeRole::Detached);
   assert(Role != NodeRole::Detached);
 
   Child->setRole(Role);
   prependChildLowLevel(Child);
 }
 
 void syntax::Tree::prependChildLowLevel(Node *Child) {
   assert(Child->Parent == nullptr);
   assert(Child->NextSibling == nullptr);
+  assert(Child->PreviousSibling == nullptr);
   assert(Child->getRole() != NodeRole::Detached);
 
   Child->Parent = this;
+  if (this->FirstChild) {
     Child->NextSibling = this->FirstChild;
+    this->FirstChild->PreviousSibling = Child;
+  } else
+    this->LastChild = Child;
+
   this->FirstChild = Child;
 }
 
-void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
+void syntax::Tree::replaceChildRangeLowLevel(Node *Begin, Node *End,
                                              Node *New) {
-  assert((!BeforeBegin || BeforeBegin->Parent == this) &&
-         "`BeforeBegin` is not a child of `this`.");
+  assert(((!Begin && !FirstChild) || Begin->Parent == this) &&
+         "`Begin` is not a child of `this`.");
   assert((!End || End->Parent == this) && "`End` is not a child of `this`.");
   assert(canModify() && "Cannot modify `this`.");
 
-  Node *&Begin = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
     assert(N->Parent == nullptr);
     assert(N->getRole() != NodeRole::Detached && "Roles must be set");
     // FIXME: sanity-check the role.
   }
 
   auto Reachable = [](Node *From, Node *N) {
     if (!N)
       return true;
     for (auto *It = From; It; It = It->NextSibling)
       if (It == N)
         return true;
     return false;
   };
-  assert(Reachable(FirstChild, BeforeBegin) &&
-         "`BeforeBegin` is not reachable.");
-  assert(Reachable(Begin, End) && "`End` is not after `BeforeBegin`.");
+  assert(Reachable(FirstChild, Begin) && "`Begin` is not reachable.");
+  assert(Reachable(Begin, End) && "`End` is not after `Begin`.");
 #endif
 
-  if (!New && Begin == End)
+  if (!New && (!Begin || Begin == End))
     return;
 
   // Mark modification.
   for (auto *T = this; T && T->Original; T = T->Parent)
     T->Original = false;
 
+  // Point to node before the range to be removed, to later insert the `New`
+  // range after it.
+  auto *BeforeBegin = Begin ? Begin->PreviousSibling : nullptr;
+
   // Detach old nodes.
   for (auto *N = Begin; N != End;) {
     auto *Next = N->NextSibling;
 
     N->setRole(NodeRole::Detached);
     N->Parent = nullptr;
     N->NextSibling = nullptr;
+    N->PreviousSibling = nullptr;
     if (N->Original)
       traverse(N, [](Node *C) { C->Original = false; });
 
     N = Next;
   }
 
+  // Attach new range.
+  auto *&NewBegin = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto *&NewLast = End ? End->PreviousSibling : LastChild;
+
   if (!New) {
-    Begin = End;
+    NewBegin = End;
+    NewLast = BeforeBegin;
     return;
   }
-  // Attach new nodes.
-  Begin = New;
-  auto *Last = New;
+
+  New->PreviousSibling = BeforeBegin;
+  NewBegin = New;
+
+  Node *LastInNew;
   for (auto *N = New; N != nullptr; N = N->NextSibling) {
-    Last = N;
+    LastInNew = N;
     N->Parent = this;
   }
-  Last->NextSibling = End;
+  LastInNew->NextSibling = End;
+  NewLast = LastInNew;
 }
 
 namespace {
 static void dumpLeaf(raw_ostream &OS, const syntax::Leaf *L,
                      const SourceManager &SM) {
   assert(L);
   const auto *Token = L->getToken();
   assert(Token);
#ifndef NDEBUG
 
   const auto *T = dyn_cast<Tree>(this);
   if (!T)
     return;
   for (const Node &C : T->getChildren()) {
     if (T->isOriginal())
       assert(C.isOriginal());
     assert(!C.isDetached());
     assert(C.getParent() == T);
+    const auto *Next = C.getNextSibling();
+    assert(!Next || &C == Next->getPreviousSibling());
+    if (!C.getNextSibling())
+      assert(&C == T->getLastChild() &&
+             "Last child is reachable by advancing from the first child.");
   }
 
   const auto *L = dyn_cast<List>(T);
   if (!L)
     return;
   for (const Node &C : T->getChildren()) {
     assert(C.getRole() == NodeRole::ListElement ||
            C.getRole() == NodeRole::ListDelimiter);
if (const auto *L = dyn_cast<syntax::Leaf>(&C))
       return L;
     if (const auto *L = cast<syntax::Tree>(C).findFirstLeaf())
       return L;
   }
   return nullptr;
 }
 
 const syntax::Leaf *syntax::Tree::findLastLeaf() const {
-  const syntax::Leaf *Last = nullptr;
-  for (const Node &C : getChildren()) {
-    if (const auto *L = dyn_cast<syntax::Leaf>(&C))
-      Last = L;
-    else if (const auto *L = cast<syntax::Tree>(C).findLastLeaf())
-      Last = L;
+  for (auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
+    if (auto *L = dyn_cast<syntax::Leaf>(C))
+      return L;
+    if (auto *L = cast<syntax::Tree>(C)->findLastLeaf())
+      return L;
   }
-  return Last;
+  return nullptr;
 }
 
 const syntax::Node *syntax::Tree::findChild(NodeRole R) const {
   for (const Node &C : getChildren()) {
     if (C.getRole() == R)
       return &C;
   }
   return nullptr;