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