Add some stronger checks to TreeNode<>
Self-insertion was not previously detected, nor removal from
null |this| in all cases.
Change-Id: I839d795f0eed1751857bab8432960b9b3f54c372
Reviewed-on: https://pdfium-review.googlesource.com/c/pdfium/+/53651
Commit-Queue: Tom Sepez <tsepez@chromium.org>
Reviewed-by: Lei Zhang <thestig@chromium.org>
diff --git a/core/fxcrt/BUILD.gn b/core/fxcrt/BUILD.gn
index f74c3d3..88337ff 100644
--- a/core/fxcrt/BUILD.gn
+++ b/core/fxcrt/BUILD.gn
@@ -161,6 +161,7 @@
"retained_tree_node_unittest.cpp",
"shared_copy_on_write_unittest.cpp",
"string_pool_template_unittest.cpp",
+ "tree_node_unittest.cpp",
"unowned_ptr_unittest.cpp",
"weak_ptr_unittest.cpp",
"widestring_unittest.cpp",
diff --git a/core/fxcrt/retained_tree_node_unittest.cpp b/core/fxcrt/retained_tree_node_unittest.cpp
index c41b5ef..3fabb80 100644
--- a/core/fxcrt/retained_tree_node_unittest.cpp
+++ b/core/fxcrt/retained_tree_node_unittest.cpp
@@ -45,6 +45,7 @@
{
RetainPtr<ObservableRetainedTreeNodeForTest> ptr =
pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
+ EXPECT_FALSE(ptr->HasChild(ptr.Get()));
watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
EXPECT_TRUE(watcher.Get());
}
@@ -60,6 +61,8 @@
pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
parent->AppendFirstChild(ptr);
+ EXPECT_FALSE(parent->HasChild(parent.Get()));
+ EXPECT_TRUE(parent->HasChild(ptr.Get()));
EXPECT_TRUE(watcher.Get());
}
EXPECT_TRUE(watcher.Get());
@@ -89,6 +92,8 @@
pdfium::MakeRetain<ObservableRetainedTreeNodeForTest>();
watcher = ObservableRetainedTreeNodeForTest::ObservedPtr(ptr.Get());
parent->AppendLastChild(ptr);
+ EXPECT_FALSE(parent->HasChild(parent.Get()));
+ EXPECT_TRUE(parent->HasChild(ptr.Get()));
EXPECT_TRUE(watcher.Get());
}
{
diff --git a/core/fxcrt/tree_node.h b/core/fxcrt/tree_node.h
index 7bded93..7f1f46a 100644
--- a/core/fxcrt/tree_node.h
+++ b/core/fxcrt/tree_node.h
@@ -23,13 +23,19 @@
T* GetNextSibling() const { return m_pNextSibling; }
T* GetPrevSibling() const { return m_pPrevSibling; }
+ bool HasChild(const T* child) const {
+ return child != this && child->m_pParent == this;
+ }
+
void AppendFirstChild(T* child) {
BecomeParent(child);
if (m_pFirstChild) {
+ CHECK(m_pLastChild);
m_pFirstChild->m_pPrevSibling = child;
child->m_pNextSibling = m_pFirstChild;
m_pFirstChild = child;
} else {
+ CHECK(!m_pLastChild);
m_pFirstChild = child;
m_pLastChild = child;
}
@@ -38,10 +44,12 @@
void AppendLastChild(T* child) {
BecomeParent(child);
if (m_pLastChild) {
+ CHECK(m_pFirstChild);
m_pLastChild->m_pNextSibling = child;
child->m_pPrevSibling = m_pLastChild;
m_pLastChild = child;
} else {
+ CHECK(!m_pFirstChild);
m_pFirstChild = child;
m_pLastChild = child;
}
@@ -52,14 +60,16 @@
AppendLastChild(child);
return;
}
- CHECK(other->m_pParent == this);
BecomeParent(child);
+ CHECK(HasChild(other));
child->m_pNextSibling = other;
child->m_pPrevSibling = other->m_pPrevSibling;
- if (other->m_pPrevSibling)
- other->m_pPrevSibling->m_pNextSibling = child;
- else
+ if (m_pFirstChild == other) {
+ CHECK(!other->m_pPrevSibling);
m_pFirstChild = child;
+ } else {
+ other->m_pPrevSibling->m_pNextSibling = child;
+ }
other->m_pPrevSibling = child;
}
@@ -68,29 +78,33 @@
AppendFirstChild(child);
return;
}
- CHECK(other->m_pParent == this);
BecomeParent(child);
+ CHECK(HasChild(other));
child->m_pNextSibling = other->m_pNextSibling;
child->m_pPrevSibling = other;
- if (other->m_pNextSibling)
- other->m_pNextSibling->m_pPrevSibling = child;
- else
+ if (m_pLastChild == other) {
+ CHECK(!other->m_pNextSibling);
m_pLastChild = child;
+ } else {
+ other->m_pNextSibling->m_pPrevSibling = child;
+ }
other->m_pNextSibling = child;
}
void RemoveChild(T* child) {
- CHECK(child->m_pParent == this);
- if (child->m_pNextSibling)
- child->m_pNextSibling->m_pPrevSibling = child->m_pPrevSibling;
- else
+ CHECK(HasChild(child));
+ if (m_pLastChild == child) {
+ CHECK(!child->m_pNextSibling);
m_pLastChild = child->m_pPrevSibling;
-
- if (child->m_pPrevSibling)
- child->m_pPrevSibling->m_pNextSibling = child->m_pNextSibling;
- else
+ } else {
+ child->m_pNextSibling->m_pPrevSibling = child->m_pPrevSibling;
+ }
+ if (m_pFirstChild == child) {
+ CHECK(!child->m_pPrevSibling);
m_pFirstChild = child->m_pNextSibling;
-
+ } else {
+ child->m_pPrevSibling->m_pNextSibling = child->m_pNextSibling;
+ }
child->m_pParent = nullptr;
child->m_pPrevSibling = nullptr;
child->m_pNextSibling = nullptr;
@@ -99,11 +113,12 @@
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 = static_cast<T*>(this);
- ASSERT(!child->m_pNextSibling);
- ASSERT(!child->m_pPrevSibling);
+ CHECK(!child->m_pNextSibling);
+ CHECK(!child->m_pPrevSibling);
}
T* m_pParent = nullptr; // Raw, intra-tree pointer.
diff --git a/core/fxcrt/tree_node_unittest.cpp b/core/fxcrt/tree_node_unittest.cpp
new file mode 100644
index 0000000..f2334cf
--- /dev/null
+++ b/core/fxcrt/tree_node_unittest.cpp
@@ -0,0 +1,70 @@
+// Copyright 2019 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 "core/fxcrt/tree_node.h"
+
+#include <memory>
+
+#include "testing/gtest/include/gtest/gtest.h"
+#include "third_party/base/ptr_util.h"
+
+namespace fxcrt {
+
+class TestTreeNode : public TreeNode<TestTreeNode> {};
+
+// NOTE: Successful cases are covered via RetainedTreeNode tests.
+// These tests check that we trip CHECKS given bad calls.
+
+TEST(TreeNode, SelfAppendFirstChild) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ EXPECT_DEATH(pNode->AppendFirstChild(pNode.get()), "");
+}
+
+TEST(TreeNode, SelfAppendLastChild) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ EXPECT_DEATH(pNode->AppendLastChild(pNode.get()), "");
+}
+
+TEST(TreeNode, SelfInsertBeforeOther) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ auto pOther = pdfium::MakeUnique<TestTreeNode>();
+ pNode->AppendFirstChild(pOther.get());
+ EXPECT_DEATH(pNode->InsertBefore(pNode.get(), pOther.get()), "");
+}
+
+TEST(TreeNode, InsertOtherBeforeSelf) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ auto pOther = pdfium::MakeUnique<TestTreeNode>();
+ pNode->AppendFirstChild(pOther.get());
+ EXPECT_DEATH(pNode->InsertBefore(pOther.get(), pNode.get()), "");
+}
+
+TEST(TreeNode, SelfInsertAfterOther) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ auto pOther = pdfium::MakeUnique<TestTreeNode>();
+ pNode->AppendFirstChild(pOther.get());
+ EXPECT_DEATH(pNode->InsertBefore(pNode.get(), pOther.get()), "");
+}
+
+TEST(TreeNode, InsertOtherAfterSelf) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ auto pOther = pdfium::MakeUnique<TestTreeNode>();
+ pNode->AppendFirstChild(pOther.get());
+ EXPECT_DEATH(pNode->InsertBefore(pOther.get(), pNode.get()), "");
+}
+
+TEST(TreeNode, RemoveParentless) {
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ EXPECT_DEATH(pNode->GetParent()->RemoveChild(pNode.get()), "");
+}
+
+TEST(TreeNode, RemoveFromWrongParent) {
+ auto pGoodParent = pdfium::MakeUnique<TestTreeNode>();
+ auto pBadParent = pdfium::MakeUnique<TestTreeNode>();
+ auto pNode = pdfium::MakeUnique<TestTreeNode>();
+ pGoodParent->AppendFirstChild(pNode.get());
+ EXPECT_DEATH(pBadParent->RemoveChild(pNode.get()), "");
+}
+
+} // namespace fxcrt
