Introduce GCedTreeNode class template.

Represents a DOM-like structure that can be garbage collected. This
requires allowing the tree_node.h template to use arbitrary pointer
types for its members.

Change-Id: I9dcbadf9965750ff0d84616f404503067371c930
Reviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/70690
Commit-Queue: Tom Sepez <tsepez@chromium.org>
Reviewed-by: Lei Zhang <thestig@chromium.org>
diff --git a/core/fxcrt/tree_node.h b/core/fxcrt/tree_node.h
index 5b1d7df..ce5b414 100644
--- a/core/fxcrt/tree_node.h
+++ b/core/fxcrt/tree_node.h
@@ -11,7 +11,7 @@
 namespace fxcrt {
 
 // Implements the usual DOM/XML-ish trees.
-template <typename T>
+template <typename T, typename PtrType = T*>
 class TreeNode {
  public:
   TreeNode() = default;
@@ -130,22 +130,29 @@
       parent->RemoveChild(static_cast<T*>(this));
   }
 
+ protected:
+  const PtrType& RawParent() const { return m_pParent; }
+  const PtrType& RawFirstChild() const { return m_pFirstChild; }
+  const PtrType& RawLastChild() const { return m_pLastChild; }
+  const PtrType& RawNextSibling() const { return m_pNextSibling; }
+  const PtrType& RawPrevSibling() const { return m_pPrevSibling; }
+
  private:
   // Child left in state where sibling members need subsequent adjustment.
   void BecomeParent(T* child) {
     CHECK(child != this);  // Detect attempts at self-insertion.
     if (child->m_pParent)
-      child->m_pParent->TreeNode<T>::RemoveChild(child);
+      child->m_pParent->TreeNode<T, PtrType>::RemoveChild(child);
     child->m_pParent = static_cast<T*>(this);
     CHECK(!child->m_pNextSibling);
     CHECK(!child->m_pPrevSibling);
   }
 
-  T* m_pParent = nullptr;       // Raw, intra-tree pointer.
-  T* m_pFirstChild = nullptr;   // Raw, intra-tree pointer.
-  T* m_pLastChild = nullptr;    // Raw, intra-tree pointer.
-  T* m_pNextSibling = nullptr;  // Raw, intra-tree pointer
-  T* m_pPrevSibling = nullptr;  // Raw, intra-tree pointer
+  PtrType m_pParent = nullptr;       // Default: Raw, intra-tree pointer.
+  PtrType m_pFirstChild = nullptr;   // Default: Raw, intra-tree pointer.
+  PtrType m_pLastChild = nullptr;    // Default: Raw, intra-tree pointer.
+  PtrType m_pNextSibling = nullptr;  // Default: Raw, intra-tree pointer
+  PtrType m_pPrevSibling = nullptr;  // Default: Raw, intra-tree pointer
 };
 
 }  // namespace fxcrt
diff --git a/fxjs/BUILD.gn b/fxjs/BUILD.gn
index 6ec9276..6c9e655 100644
--- a/fxjs/BUILD.gn
+++ b/fxjs/BUILD.gn
@@ -114,6 +114,7 @@
 
     if (pdf_enable_xfa) {
       sources += [
+        "gc/gced_tree_node.h",
         "gc/heap.cpp",
         "gc/heap.h",
         "xfa/cfxjse_class.cpp",
@@ -242,6 +243,7 @@
     pdfium_root_dir = "../"
     if (pdf_enable_xfa) {
       sources += [
+        "gc/gced_tree_node_embeddertest.cpp",
         "gc/heap_embeddertest.cpp",
         "xfa/cfxjse_app_embeddertest.cpp",
         "xfa/cfxjse_formcalc_context_embeddertest.cpp",
diff --git a/fxjs/gc/gced_tree_node.h b/fxjs/gc/gced_tree_node.h
new file mode 100644
index 0000000..a983fe5
--- /dev/null
+++ b/fxjs/gc/gced_tree_node.h
@@ -0,0 +1,43 @@
+// Copyright 2020 PDFium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#ifndef FXJS_GC_GCED_TREE_NODE_H_
+#define FXJS_GC_GCED_TREE_NODE_H_
+
+#include "core/fxcrt/tree_node.h"
+#include "third_party/base/logging.h"
+#include "v8/include/cppgc/allocation.h"
+#include "v8/include/cppgc/member.h"
+#include "v8/include/cppgc/visitor.h"
+
+namespace fxjs {
+
+// For DOM/XML-ish trees, where references outside the tree are RetainPtr<T>,
+// and the parent node also "retains" its children but doesn't always have
+// a direct pointer to them.
+template <typename T>
+class GCedTreeNode : public TreeNode<T, cppgc::Member<T>>,
+                     public cppgc::GarbageCollected<GCedTreeNode<T>> {
+ public:
+  using TreeNode<T, cppgc::Member<T>>::RemoveChild;
+
+  virtual void Trace(cppgc::Visitor* visitor) const {
+    visitor->Trace(TreeNode<T, cppgc::Member<T>>::RawParent());
+    visitor->Trace(TreeNode<T, cppgc::Member<T>>::RawFirstChild());
+    visitor->Trace(TreeNode<T, cppgc::Member<T>>::RawLastChild());
+    visitor->Trace(TreeNode<T, cppgc::Member<T>>::RawNextSibling());
+    visitor->Trace(TreeNode<T, cppgc::Member<T>>::RawPrevSibling());
+  }
+
+ protected:
+  GCedTreeNode() = default;
+  GCedTreeNode(const GCedTreeNode& that) = delete;
+  GCedTreeNode& operator=(const GCedTreeNode& that) = delete;
+};
+
+}  // namespace fxjs
+
+using fxjs::GCedTreeNode;
+
+#endif  // FXJS_GC_GCED_TREE_NODE_H_
diff --git a/fxjs/gc/gced_tree_node_embeddertest.cpp b/fxjs/gc/gced_tree_node_embeddertest.cpp
new file mode 100644
index 0000000..9dd218b
--- /dev/null
+++ b/fxjs/gc/gced_tree_node_embeddertest.cpp
@@ -0,0 +1,146 @@
+// Copyright 2020 PDFium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "fxjs/gc/gced_tree_node.h"
+
+#include "core/fxcrt/observed_ptr.h"
+#include "fxjs/gc/heap.h"
+#include "testing/gced_embeddertest.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "third_party/base/stl_util.h"
+#include "v8/include/cppgc/allocation.h"
+#include "v8/include/cppgc/persistent.h"
+
+namespace {
+
+class ObservableGCedTreeNodeForTest
+    : public GCedTreeNode<ObservableGCedTreeNodeForTest>,
+      public Observable {
+ public:
+  CONSTRUCT_VIA_MAKE_GARBAGE_COLLECTED;
+
+ private:
+  ObservableGCedTreeNodeForTest() = default;
+};
+
+}  // namespace
+
+class GCedTreeNodeEmbedderTest : public GCedEmbedderTest {
+ public:
+  static cppgc::Persistent<ObservableGCedTreeNodeForTest> s_root;
+
+  void SetUp() override {
+    GCedEmbedderTest::SetUp();
+    heap_ = FXGC_CreateHeap();
+  }
+
+  void TearDown() override {
+    s_root = nullptr;  // Can't (yet) outlive |heap_|.
+    heap_.reset();
+    GCedEmbedderTest::TearDown();
+  }
+
+  cppgc::Heap* heap() const { return heap_.get(); }
+  ObservableGCedTreeNodeForTest* CreateNode() {
+    return cppgc::MakeGarbageCollected<ObservableGCedTreeNodeForTest>(
+        heap_.get());
+  }
+
+  void ForceGCAndPump() {
+    heap()->ForceGarbageCollectionSlow(
+        "GCedTreeNodeEmbedderTest", "test",
+        cppgc::Heap::StackState::kNoHeapPointers);
+    PumpPlatformMessageLoop();
+  }
+
+  void AddClutterToFront(ObservableGCedTreeNodeForTest* parent) {
+    for (int i = 0; i < 4; ++i) {
+      parent->AppendFirstChild(
+          cppgc::MakeGarbageCollected<ObservableGCedTreeNodeForTest>(
+              heap_.get()));
+    }
+  }
+
+  void AddClutterToBack(ObservableGCedTreeNodeForTest* parent) {
+    for (int i = 0; i < 4; ++i) {
+      parent->AppendLastChild(
+          cppgc::MakeGarbageCollected<ObservableGCedTreeNodeForTest>(
+              heap_.get()));
+    }
+  }
+
+ private:
+  FXGCScopedHeap heap_;
+};
+
+cppgc::Persistent<ObservableGCedTreeNodeForTest>
+    GCedTreeNodeEmbedderTest::s_root;
+
+TEST_F(GCedTreeNodeEmbedderTest, OneRefence) {
+  s_root = CreateNode();
+  ObservedPtr<ObservableGCedTreeNodeForTest> watcher(s_root);
+  ForceGCAndPump();
+  EXPECT_TRUE(watcher);
+}
+
+TEST_F(GCedTreeNodeEmbedderTest, NoReferences) {
+  ObservedPtr<ObservableGCedTreeNodeForTest> watcher(CreateNode());
+  ForceGCAndPump();
+  EXPECT_FALSE(watcher);
+}
+
+TEST_F(GCedTreeNodeEmbedderTest, FirstHasParent) {
+  s_root = CreateNode();
+  ObservedPtr<ObservableGCedTreeNodeForTest> watcher(CreateNode());
+  s_root->AppendFirstChild(watcher.Get());
+  ForceGCAndPump();
+  ASSERT_TRUE(s_root);
+  EXPECT_TRUE(watcher);
+  s_root->RemoveChild(watcher.Get());
+  ForceGCAndPump();
+  ASSERT_TRUE(s_root);
+  EXPECT_FALSE(watcher);
+
+  // Now add some clutter.
+  watcher.Reset(CreateNode());
+  s_root->AppendFirstChild(watcher.Get());
+  AddClutterToFront(s_root);
+  AddClutterToBack(s_root);
+  ForceGCAndPump();
+  ASSERT_TRUE(s_root);
+  EXPECT_TRUE(watcher);
+  s_root->RemoveChild(watcher.Get());
+  ForceGCAndPump();
+  EXPECT_TRUE(s_root);
+  EXPECT_FALSE(watcher);
+}
+
+TEST_F(GCedTreeNodeEmbedderTest, RemoveSelf) {
+  s_root = CreateNode();
+  ObservedPtr<ObservableGCedTreeNodeForTest> watcher(CreateNode());
+  s_root->AppendFirstChild(watcher.Get());
+  ForceGCAndPump();
+  EXPECT_TRUE(s_root);
+  ASSERT_TRUE(watcher);
+  watcher->RemoveSelfIfParented();
+  ForceGCAndPump();
+  EXPECT_TRUE(s_root);
+  EXPECT_FALSE(watcher);
+}
+
+TEST_F(GCedTreeNodeEmbedderTest, InsertBeforeAfter) {
+  s_root = CreateNode();
+  AddClutterToFront(s_root);
+  ObservedPtr<ObservableGCedTreeNodeForTest> watcher(CreateNode());
+  s_root->AppendFirstChild(watcher.Get());
+  s_root->InsertBefore(s_root->GetFirstChild(), s_root->GetLastChild());
+  s_root->InsertAfter(s_root->GetLastChild(), s_root->GetFirstChild());
+  ForceGCAndPump();
+  ASSERT_TRUE(s_root);
+  EXPECT_TRUE(watcher);
+  s_root->RemoveChild(watcher.Get());
+  ForceGCAndPump();
+  EXPECT_TRUE(s_root);
+  EXPECT_FALSE(watcher);
+}
diff --git a/fxjs/gc/heap.h b/fxjs/gc/heap.h
index 7792cbc..96ec209 100644
--- a/fxjs/gc/heap.h
+++ b/fxjs/gc/heap.h
@@ -20,4 +20,8 @@
 void FXGC_Release();
 FXGCScopedHeap FXGC_CreateHeap();
 
+#define CONSTRUCT_VIA_MAKE_GARBAGE_COLLECTED \
+  template <typename T>                      \
+  friend class cppgc::MakeGarbageCollectedTrait
+
 #endif  // FXJS_GC_HEAP_H_