1 // Copyright 2019 PDFium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "core/fxcrt/tree_node.h"
6
7 #include <memory>
8
9 #include "testing/gtest/include/gtest/gtest.h"
10 #include "third_party/base/ptr_util.h"
11
12 namespace fxcrt {
13
14 class TestTreeNode : public TreeNode<TestTreeNode> {};
15
16 // NOTE: Successful cases are covered via RetainedTreeNode tests.
17 // These tests check that we trip CHECKS given bad calls.
18
TEST(TreeNode,SelfAppendFirstChild)19 TEST(TreeNode, SelfAppendFirstChild) {
20 auto pNode = pdfium::MakeUnique<TestTreeNode>();
21 EXPECT_DEATH(pNode->AppendFirstChild(pNode.get()), "");
22 }
23
TEST(TreeNode,SelfAppendLastChild)24 TEST(TreeNode, SelfAppendLastChild) {
25 auto pNode = pdfium::MakeUnique<TestTreeNode>();
26 EXPECT_DEATH(pNode->AppendLastChild(pNode.get()), "");
27 }
28
TEST(TreeNode,SelfInsertBeforeOther)29 TEST(TreeNode, SelfInsertBeforeOther) {
30 auto pNode = pdfium::MakeUnique<TestTreeNode>();
31 auto pOther = pdfium::MakeUnique<TestTreeNode>();
32 pNode->AppendFirstChild(pOther.get());
33 EXPECT_DEATH(pNode->InsertBefore(pNode.get(), pOther.get()), "");
34 }
35
TEST(TreeNode,InsertOtherBeforeSelf)36 TEST(TreeNode, InsertOtherBeforeSelf) {
37 auto pNode = pdfium::MakeUnique<TestTreeNode>();
38 auto pOther = pdfium::MakeUnique<TestTreeNode>();
39 pNode->AppendFirstChild(pOther.get());
40 EXPECT_DEATH(pNode->InsertBefore(pOther.get(), pNode.get()), "");
41 }
42
TEST(TreeNode,SelfInsertAfterOther)43 TEST(TreeNode, SelfInsertAfterOther) {
44 auto pNode = pdfium::MakeUnique<TestTreeNode>();
45 auto pOther = pdfium::MakeUnique<TestTreeNode>();
46 pNode->AppendFirstChild(pOther.get());
47 EXPECT_DEATH(pNode->InsertBefore(pNode.get(), pOther.get()), "");
48 }
49
TEST(TreeNode,InsertOtherAfterSelf)50 TEST(TreeNode, InsertOtherAfterSelf) {
51 auto pNode = pdfium::MakeUnique<TestTreeNode>();
52 auto pOther = pdfium::MakeUnique<TestTreeNode>();
53 pNode->AppendFirstChild(pOther.get());
54 EXPECT_DEATH(pNode->InsertBefore(pOther.get(), pNode.get()), "");
55 }
56
TEST(TreeNode,RemoveParentless)57 TEST(TreeNode, RemoveParentless) {
58 auto pNode = pdfium::MakeUnique<TestTreeNode>();
59 EXPECT_DEATH(pNode->GetParent()->RemoveChild(pNode.get()), "");
60 }
61
TEST(TreeNode,RemoveFromWrongParent)62 TEST(TreeNode, RemoveFromWrongParent) {
63 auto pGoodParent = pdfium::MakeUnique<TestTreeNode>();
64 auto pBadParent = pdfium::MakeUnique<TestTreeNode>();
65 auto pNode = pdfium::MakeUnique<TestTreeNode>();
66 pGoodParent->AppendFirstChild(pNode.get());
67 EXPECT_DEATH(pBadParent->RemoveChild(pNode.get()), "");
68 }
69
TEST(TreeNode,SafeRemove)70 TEST(TreeNode, SafeRemove) {
71 auto pParent = pdfium::MakeUnique<TestTreeNode>();
72 auto pChild = pdfium::MakeUnique<TestTreeNode>();
73 pParent->AppendFirstChild(pChild.get());
74 pChild->RemoveSelfIfParented();
75 EXPECT_EQ(nullptr, pParent->GetFirstChild());
76 EXPECT_EQ(nullptr, pChild->GetParent());
77 }
78
TEST(TreeNode,SafeRemoveParentless)79 TEST(TreeNode, SafeRemoveParentless) {
80 auto pNode = pdfium::MakeUnique<TestTreeNode>();
81 pNode->RemoveSelfIfParented();
82 EXPECT_EQ(nullptr, pNode->GetParent());
83 }
84
TEST(TreeNode,RemoveAllChildren)85 TEST(TreeNode, RemoveAllChildren) {
86 auto pParent = pdfium::MakeUnique<TestTreeNode>();
87 pParent->RemoveAllChildren();
88 EXPECT_EQ(nullptr, pParent->GetFirstChild());
89
90 auto p0 = pdfium::MakeUnique<TestTreeNode>();
91 auto p1 = pdfium::MakeUnique<TestTreeNode>();
92 auto p2 = pdfium::MakeUnique<TestTreeNode>();
93 auto p3 = pdfium::MakeUnique<TestTreeNode>();
94 pParent->AppendLastChild(p0.get());
95 pParent->AppendLastChild(p1.get());
96 pParent->AppendLastChild(p2.get());
97 pParent->AppendLastChild(p3.get());
98 pParent->RemoveAllChildren();
99 EXPECT_EQ(nullptr, pParent->GetFirstChild());
100 }
101
TEST(TreeNode,NthChild)102 TEST(TreeNode, NthChild) {
103 auto pParent = pdfium::MakeUnique<TestTreeNode>();
104 EXPECT_EQ(nullptr, pParent->GetNthChild(-1));
105 EXPECT_EQ(nullptr, pParent->GetNthChild(0));
106
107 auto p0 = pdfium::MakeUnique<TestTreeNode>();
108 auto p1 = pdfium::MakeUnique<TestTreeNode>();
109 auto p2 = pdfium::MakeUnique<TestTreeNode>();
110 auto p3 = pdfium::MakeUnique<TestTreeNode>();
111 pParent->AppendLastChild(p0.get());
112 pParent->AppendLastChild(p1.get());
113 pParent->AppendLastChild(p2.get());
114 pParent->AppendLastChild(p3.get());
115 EXPECT_EQ(nullptr, pParent->GetNthChild(-1));
116 EXPECT_EQ(p0.get(), pParent->GetNthChild(0));
117 EXPECT_EQ(p1.get(), pParent->GetNthChild(1));
118 EXPECT_EQ(p2.get(), pParent->GetNthChild(2));
119 EXPECT_EQ(p3.get(), pParent->GetNthChild(3));
120 EXPECT_EQ(nullptr, pParent->GetNthChild(4));
121 pParent->RemoveAllChildren();
122 }
123
TEST(TreeNode,AppendFirstChild)124 TEST(TreeNode, AppendFirstChild) {
125 auto parent = pdfium::MakeUnique<TestTreeNode>();
126 auto child0 = pdfium::MakeUnique<TestTreeNode>();
127 auto child1 = pdfium::MakeUnique<TestTreeNode>();
128 parent->AppendFirstChild(child0.get());
129 EXPECT_EQ(child0.get(), parent->GetFirstChild());
130 parent->AppendFirstChild(child1.get());
131 EXPECT_EQ(child1.get(), parent->GetFirstChild());
132 EXPECT_EQ(child1.get(), parent->GetNthChild(0));
133 EXPECT_EQ(child0.get(), parent->GetNthChild(1));
134 }
135
TEST(TreeNode,RemoveChild)136 TEST(TreeNode, RemoveChild) {
137 auto parent = pdfium::MakeUnique<TestTreeNode>();
138 auto child0 = pdfium::MakeUnique<TestTreeNode>();
139 auto child1 = pdfium::MakeUnique<TestTreeNode>();
140
141 parent->AppendFirstChild(child0.get());
142 parent->AppendLastChild(child1.get());
143 EXPECT_EQ(child0.get(), parent->GetFirstChild());
144 EXPECT_EQ(child1.get(), parent->GetLastChild());
145 parent->RemoveChild(child0.get());
146 EXPECT_EQ(child1.get(), parent->GetFirstChild());
147 EXPECT_EQ(child1.get(), parent->GetLastChild());
148 parent->RemoveChild(child1.get());
149 EXPECT_EQ(nullptr, parent->GetFirstChild());
150 EXPECT_EQ(nullptr, parent->GetLastChild());
151
152 parent->AppendFirstChild(child0.get());
153 parent->AppendLastChild(child1.get());
154 EXPECT_EQ(child0.get(), parent->GetFirstChild());
155 EXPECT_EQ(child1.get(), parent->GetLastChild());
156 parent->RemoveChild(child1.get());
157 EXPECT_EQ(child0.get(), parent->GetFirstChild());
158 EXPECT_EQ(child0.get(), parent->GetLastChild());
159 parent->RemoveChild(child0.get());
160 EXPECT_EQ(nullptr, parent->GetFirstChild());
161 EXPECT_EQ(nullptr, parent->GetLastChild());
162 }
163
164 } // namespace fxcrt
165