[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-11-05 Thread Eduardo Caldas via Phabricator via cfe-commits 
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.
Closed by commit rG23657d9cc332: [SyntaxTree] Add reverse links to syntax 
Nodes. (authored by eduucaldas).

Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/BuildTree.cpp
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Synthesis.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -74,6 +75,30 @@
   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);
@@ -85,22 +110,26 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  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 || 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
 assert(N->Parent == nullptr);
@@ -116,9 +145,8 @@
 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)
@@ -128,6 +156,10 @@
   for (auto *T = this; T && T->Original; T = T->Parent)
 T->Original = false;
 
+  // Save the node before the range to be removed. Later we insert the `New`
+  // range after this node.
+  auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;
+
   // Detach old nodes.
   for (auto *N = Begin; N != End;) {
 auto *Next = N->NextSibling;
@@ -135,24 +167,33 @@
 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto * = End ? End->PreviousSibling : LastChild;
+
   if (!New) {
-Begin = End;
+NewFirst = End;
+NewLast = BeforeBegin;
 return;
   }
-  // Attach new nodes.
-  Begin = New;
-  auto *Last = New;
+
+  New->PreviousSibling = BeforeBegin;
+  NewFirst = 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 {
@@ -248,6 +289,11 @@
   assert(C.isOriginal());

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-11-04 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas updated this revision to Diff 302879.
eduucaldas added a comment.

Rebase


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/BuildTree.cpp
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Synthesis.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -74,6 +75,30 @@
   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);
@@ -85,22 +110,26 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  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 || 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
 assert(N->Parent == nullptr);
@@ -116,9 +145,8 @@
 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)
@@ -128,6 +156,10 @@
   for (auto *T = this; T && T->Original; T = T->Parent)
 T->Original = false;
 
+  // Save the node before the range to be removed. Later we insert the `New`
+  // range after this node.
+  auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;
+
   // Detach old nodes.
   for (auto *N = Begin; N != End;) {
 auto *Next = N->NextSibling;
@@ -135,24 +167,33 @@
 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto * = End ? End->PreviousSibling : LastChild;
+
   if (!New) {
-Begin = End;
+NewFirst = End;
+NewLast = BeforeBegin;
 return;
   }
-  // Attach new nodes.
-  Begin = New;
-  auto *Last = New;
+
+  New->PreviousSibling = BeforeBegin;
+  NewFirst = 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 {
@@ -248,6 +289,11 @@
   assert(C.isOriginal());
 assert(!C.isDetached());
 assert(C.getParent() == T);
+const auto *Next = C.getNextSibling();
+assert(!Next ||  == Next->getPreviousSibling());
+

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-11-04 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas added a comment.

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas updated this revision to Diff 301315.
eduucaldas marked 9 inline comments as done.
eduucaldas added a comment.

Answered all comments but:

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/BuildTree.cpp
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Synthesis.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -74,6 +75,30 @@
   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);
@@ -85,22 +110,26 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  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 || 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
 assert(N->Parent == nullptr);
@@ -116,9 +145,8 @@
 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)
@@ -128,6 +156,10 @@
   for (auto *T = this; T && T->Original; T = T->Parent)
 T->Original = false;
 
+  // Save the node before the range to be removed. Later we insert the `New`
+  // range after this node.
+  auto *BeforeBegin = Begin ? Begin->PreviousSibling : LastChild;
+
   // Detach old nodes.
   for (auto *N = Begin; N != End;) {
 auto *Next = N->NextSibling;
@@ -135,24 +167,33 @@
 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto * = End ? End->PreviousSibling : LastChild;
+
   if (!New) {
-Begin = End;
+NewFirst = End;
+NewLast = BeforeBegin;
 return;
   }
-  // Attach new nodes.
-  Begin = New;
-  auto *Last = New;
+
+  New->PreviousSibling = BeforeBegin;
+  NewFirst = 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 {
@@

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas updated this revision to Diff 301256.
eduucaldas added a comment.

I was silly on the last rebase. Ignore this.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/BuildTree.cpp
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Synthesis.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -74,6 +75,30 @@
   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);
@@ -85,22 +110,26 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
 assert(N->Parent == nullptr);
@@ -116,18 +145,21 @@
 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;
@@ -135,24 +167,33 @@
 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto * = 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 {
@@ -248,6 +289,11 @@
   assert(C.isOriginal());
 assert(!C.isDetached());

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas updated this revision to Diff 301255.
eduucaldas added a comment.

Rebase to include ChildIterator patch.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/BuildTree.cpp
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Synthesis.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -74,6 +75,30 @@
   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);
@@ -85,22 +110,26 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
 assert(N->Parent == nullptr);
@@ -116,18 +145,21 @@
 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;
@@ -135,24 +167,33 @@
 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto * = 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 {
@@ -245,9 +286,14 @@
 return;
   for (const Node  : T->getChildren()) {
 if (T->isOriginal())
-

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Dmitri Gribenko via Phabricator via cfe-commits 
gribozavr2 added inline comments.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:188
+  /// Similar but appends.
+  void appendChildLowLevel(Node *Child, NodeRole Role);
+

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.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:201
   /// (!) \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;

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



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:109
   Node *getNextSibling() { return NextSibling; }
+  const Node *getPreviousSibling() const { return PreviousSibling; }
+  Node *getPreviousSibling() { return PreviousSibling; }

eduucaldas wrote:
> sammccall wrote:
> > (Not something to change in this patch...)
> > Since adding the "get" prefixes, getNextSibling() and now 
> > getPreviousSibling() are pretty verbose, we might consider 
> > getNext()/getPrevious()
> I agree
> 
> 
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.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

eduucaldas wrote:
> eduucaldas wrote:
> > sammccall wrote:
> > > gribozavr2 wrote:
> > > > eduucaldas wrote:
> > > > > 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.
> > > > There is some awkwardness in foldChildren because we can only go in 
> > > > reverse -- maybe append is indeed more natural.
> > > 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)
> > 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`.
> 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.
> 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.



Comment at: clang/lib/Tooling/Syntax/BuildTree.cpp:639
 
   // We need to go in reverse order, because we can only prepend.
+  for (auto It = BeginChildren; It != EndChildren; ++It) {

Remove the comment?



Comment at: clang/lib/Tooling/Syntax/Synthesis.cpp:204
+  for (const auto *ChildIt = Children.begin(); ChildIt != Children.end();
+   ++ChildIt)
+FactoryImpl::appendChildLowLevel(T, ChildIt->first, ChildIt->second);

Use a range-based for loop?



Comment at: clang/lib/Tooling/Syntax/Tree.cpp:128
  Node *New) {
-  assert((!BeforeBegin || BeforeBegin->Parent == this) &&
- "`BeforeBegin` is not a child of `this`.");
+  assert(((!Begin && !FirstChild) ||

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Sam McCall via Phabricator via cfe-commits 
sammccall added a comment.

LG from my side.




Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

eduucaldas wrote:
> eduucaldas wrote:
> > sammccall wrote:
> > > gribozavr2 wrote:
> > > > eduucaldas wrote:
> > > > > 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.
> > > > There is some awkwardness in foldChildren because we can only go in 
> > > > reverse -- maybe append is indeed more natural.
> > > 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)
> > 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`.
> 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.
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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas marked 2 inline comments as done.
eduucaldas added inline comments.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:109
   Node *getNextSibling() { return NextSibling; }
+  const Node *getPreviousSibling() const { return PreviousSibling; }
+  Node *getPreviousSibling() { return PreviousSibling; }

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





Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

sammccall wrote:
> gribozavr2 wrote:
> > eduucaldas wrote:
> > > 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.
> > There is some awkwardness in foldChildren because we can only go in reverse 
> > -- maybe append is indeed more natural.
> 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)
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`.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

eduucaldas wrote:
> sammccall wrote:
> > gribozavr2 wrote:
> > > eduucaldas wrote:
> > > > 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.
> > > There is some awkwardness in foldChildren because we can only go in 
> > > reverse -- maybe append is indeed more natural.
> > 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)
> 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`.
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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-28 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas updated this revision to Diff 301198.
eduucaldas marked 3 inline comments as done.
eduucaldas added a comment.

- `replaceChildRangeLowLevel` now takes Begin instead of BeforeBegin
- `appendChildLowLevel`


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/BuildTree.cpp
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Synthesis.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -74,6 +75,30 @@
   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);
@@ -85,22 +110,26 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
-
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
 assert(N->Parent == nullptr);
@@ -116,18 +145,21 @@
 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;
@@ -135,24 +167,33 @@
 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 * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  auto * = 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 {
@@ -248,6

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-27 Thread Sam McCall via Phabricator via cfe-commits 
sammccall added inline comments.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:109
   Node *getNextSibling() { return NextSibling; }
+  const Node *getPreviousSibling() const { return PreviousSibling; }
+  Node *getPreviousSibling() { return PreviousSibling; }

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



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

gribozavr2 wrote:
> eduucaldas wrote:
> > 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.
> There is some awkwardness in foldChildren because we can only go in reverse 
> -- maybe append is indeed more natural.
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)


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-27 Thread Dmitri Gribenko via Phabricator via cfe-commits 
gribozavr2 added inline comments.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

eduucaldas wrote:
> 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.
There is some awkwardness in foldChildren because we can only go in reverse -- 
maybe append is indeed more natural.



Comment at: clang/lib/Tooling/Syntax/Tree.cpp:102
 
 void syntax::Tree::replaceChildRangeLowLevel(Node *BeforeBegin, Node *End,
  Node *New) {

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



Comment at: clang/lib/Tooling/Syntax/Tree.cpp:262
+;
+  assert(Last == T->getLastChild() &&
+ "Last child is reachable by advancing from the first child.");

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


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-27 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas added a reviewer: gribozavr2.
eduucaldas added a subscriber: sammccall.
eduucaldas added inline comments.



Comment at: clang/include/clang/Tooling/Syntax/Tree.h:189
   /// EXPECTS: Child->Role != Detached
   void prependChildLowLevel(Node *Child);
   friend class TreeBuilder;

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.


Repository:
  rG LLVM Github Monorepo

CHANGES SINCE LAST ACTION
  https://reviews.llvm.org/D90240/new/

https://reviews.llvm.org/D90240

___
cfe-commits mailing list
cfe-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/cfe-commits

[PATCH] D90240: [SyntaxTree] Add reverse links to syntax Nodes.

2020-10-27 Thread Eduardo Caldas via Phabricator via cfe-commits 
eduucaldas created this revision.
Herald added a project: clang.
Herald added a subscriber: cfe-commits.
eduucaldas requested review of this revision.

Rationale:
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.


Repository:
  rG LLVM Github Monorepo

https://reviews.llvm.org/D90240

Files:
  clang/include/clang/Tooling/Syntax/Tree.h
  clang/lib/Tooling/Syntax/Mutations.cpp
  clang/lib/Tooling/Syntax/Tree.cpp

Index: clang/lib/Tooling/Syntax/Tree.cpp
===
--- clang/lib/Tooling/Syntax/Tree.cpp
+++ clang/lib/Tooling/Syntax/Tree.cpp
@@ -57,8 +57,9 @@
 }
 
 syntax::Node::Node(NodeKind Kind)
-: Parent(nullptr), NextSibling(nullptr), Kind(static_cast(Kind)),
-  Role(0), Original(false), CanModify(false) {
+: Parent(nullptr), NextSibling(nullptr), PreviousSibling(nullptr),
+  Kind(static_cast(Kind)), Role(0), Original(false),
+  CanModify(false) {
   this->setRole(NodeRole::Detached);
 }
 
@@ -85,10 +86,16 @@
 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;
-  Child->NextSibling = this->FirstChild;
+  if (this->FirstChild) {
+Child->NextSibling = this->FirstChild;
+this->FirstChild->PreviousSibling = Child;
+  } else
+this->LastChild = Child;
+
   this->FirstChild = Child;
 }
 
@@ -100,6 +107,7 @@
   assert(canModify() && "Cannot modify `this`.");
 
   Node * = BeforeBegin ? BeforeBegin->NextSibling : FirstChild;
+  Node * = End ? End->PreviousSibling : LastChild;
 
 #ifndef NDEBUG
   for (auto *N = New; N; N = N->NextSibling) {
@@ -135,6 +143,7 @@
 N->setRole(NodeRole::Detached);
 N->Parent = nullptr;
 N->NextSibling = nullptr;
+N->PreviousSibling = nullptr;
 if (N->Original)
   traverse(N, [](Node *C) { C->Original = false; });
 
@@ -143,16 +152,19 @@
 
   if (!New) {
 Begin = End;
+Last = BeforeBegin;
 return;
   }
   // Attach new nodes.
   Begin = New;
-  auto *Last = New;
+  New->PreviousSibling = BeforeBegin;
+  auto *LastInNew = New;
   for (auto *N = New; N != nullptr; N = N->NextSibling) {
-Last = N;
+LastInNew = N;
 N->Parent = this;
   }
-  Last->NextSibling = End;
+  LastInNew->NextSibling = End;
+  Last = LastInNew;
 }
 
 namespace {
@@ -243,11 +255,20 @@
   const auto *T = dyn_cast(this);
   if (!T)
 return;
+
+  const auto *Last = T->getFirstChild();
+  for (; Last && Last->getNextSibling(); Last = Last->getNextSibling())
+;
+  assert(Last == T->getLastChild() &&
+ "Last child is reachable by advancing from the first child.");
+
   for (const auto *C = T->getFirstChild(); C; C = C->getNextSibling()) {
 if (T->isOriginal())
   assert(C->isOriginal());
 assert(!C->isDetached());
 assert(C->getParent() == T);
+const auto *Next = C->getNextSibling();
+assert(!Next || C == Next->getPreviousSibling());
   }
 
   const auto *L = dyn_cast(T);
@@ -282,14 +303,13 @@
 }
 
 syntax::Leaf *syntax::Tree::findLastLeaf() {
-  syntax::Leaf *Last = nullptr;
-  for (auto *C = getFirstChild(); C; C = C->getNextSibling()) {
+  for (auto *C = getLastChild(); C; C = C->getPreviousSibling()) {
 if (auto *L = dyn_cast(C))
-  Last = L;
-else if (auto *L = cast(C)->findLastLeaf())
-  Last = L;
+  return L;
+if (auto *L = cast(C)->findLastLeaf())
+  return L;
   }
-  return Last;
+  return nullptr;
 }
 
 syntax::Node *syntax::Tree::findChild(NodeRole R) {
Index: clang/lib/Tooling/Syntax/Mutations.cpp
===
--- clang/lib/Tooling/Syntax/Mutations.cpp
+++ clang/lib/Tooling/Syntax/Mutations.cpp
@@ -23,19 +23,6 @@
 
 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 {
@@ -46,6 +33,7 @@
 assert(Anchor->Parent != nullptr);
 assert(New->Parent ==