1 // Copyright 2017 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/fpdfdoc/cpdf_nametree.h"
6 #include "core/fpdfapi/parser/cpdf_array.h"
7 #include "core/fpdfapi/parser/cpdf_dictionary.h"
8 #include "core/fpdfapi/parser/cpdf_number.h"
9 #include "core/fpdfapi/parser/cpdf_string.h"
10 #include "testing/gtest/include/gtest/gtest.h"
11 #include "third_party/base/ptr_util.h"
12
13 namespace {
14
AddNameKeyValue(CPDF_Array * pNames,const char * key,const int value)15 void AddNameKeyValue(CPDF_Array* pNames, const char* key, const int value) {
16 pNames->AddNew<CPDF_String>(key, false);
17 pNames->AddNew<CPDF_Number>(value);
18 }
19
CheckNameKeyValue(CPDF_Array * pNames,const int index,const char * key,const int value)20 void CheckNameKeyValue(CPDF_Array* pNames,
21 const int index,
22 const char* key,
23 const int value) {
24 EXPECT_STREQ(key, pNames->GetStringAt(index * 2).c_str());
25 EXPECT_EQ(value, pNames->GetIntegerAt(index * 2 + 1));
26 }
27
AddLimitsArray(CPDF_Dictionary * pNode,const char * least,const char * greatest)28 void AddLimitsArray(CPDF_Dictionary* pNode,
29 const char* least,
30 const char* greatest) {
31 CPDF_Array* pLimits = pNode->SetNewFor<CPDF_Array>("Limits");
32 pLimits->AddNew<CPDF_String>(least, false);
33 pLimits->AddNew<CPDF_String>(greatest, false);
34 }
35
CheckLimitsArray(CPDF_Dictionary * pNode,const char * least,const char * greatest)36 void CheckLimitsArray(CPDF_Dictionary* pNode,
37 const char* least,
38 const char* greatest) {
39 CPDF_Array* pLimits = pNode->GetArrayFor("Limits");
40 ASSERT_TRUE(pLimits);
41 EXPECT_STREQ(least, pLimits->GetStringAt(0).c_str());
42 EXPECT_STREQ(greatest, pLimits->GetStringAt(1).c_str());
43 }
44
FillNameTreeDict(CPDF_Dictionary * pRootDict)45 void FillNameTreeDict(CPDF_Dictionary* pRootDict) {
46 CPDF_Array* pKids = pRootDict->SetNewFor<CPDF_Array>("Kids");
47 CPDF_Dictionary* pKid1 = pKids->AddNew<CPDF_Dictionary>();
48
49 // Make the lower and upper limit out of order on purpose.
50 AddLimitsArray(pKid1, "9.txt", "1.txt");
51 pKids = pKid1->SetNewFor<CPDF_Array>("Kids");
52 CPDF_Dictionary* pKid2 = pKids->AddNew<CPDF_Dictionary>();
53 CPDF_Dictionary* pKid3 = pKids->AddNew<CPDF_Dictionary>();
54
55 AddLimitsArray(pKid2, "1.txt", "5.txt");
56 pKids = pKid2->SetNewFor<CPDF_Array>("Kids");
57 CPDF_Dictionary* pKid4 = pKids->AddNew<CPDF_Dictionary>();
58 CPDF_Dictionary* pKid5 = pKids->AddNew<CPDF_Dictionary>();
59
60 AddLimitsArray(pKid3, "9.txt", "9.txt");
61 CPDF_Array* pNames = pKid3->SetNewFor<CPDF_Array>("Names");
62 AddNameKeyValue(pNames, "9.txt", 999);
63
64 // Make the lower and upper limit out of order on purpose.
65 AddLimitsArray(pKid4, "2.txt", "1.txt");
66 pNames = pKid4->SetNewFor<CPDF_Array>("Names");
67 AddNameKeyValue(pNames, "1.txt", 111);
68 AddNameKeyValue(pNames, "2.txt", 222);
69
70 AddLimitsArray(pKid5, "3.txt", "5.txt");
71 pNames = pKid5->SetNewFor<CPDF_Array>("Names");
72 AddNameKeyValue(pNames, "3.txt", 333);
73 AddNameKeyValue(pNames, "5.txt", 555);
74 }
75
76 } // namespace
77
TEST(cpdf_nametree,GetUnicodeNameWithBOM)78 TEST(cpdf_nametree, GetUnicodeNameWithBOM) {
79 // Set up the root dictionary with a Names array.
80 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
81 CPDF_Array* pNames = pRootDict->SetNewFor<CPDF_Array>("Names");
82
83 // Add the key "1" (with BOM) and value 100 into the array.
84 std::ostringstream buf;
85 constexpr char kData[] = "\xFE\xFF\x00\x31";
86 for (size_t i = 0; i < sizeof(kData); ++i)
87 buf.put(kData[i]);
88 pNames->AddNew<CPDF_String>(ByteString(buf), true);
89 pNames->AddNew<CPDF_Number>(100);
90
91 // Check that the key is as expected.
92 CPDF_NameTree nameTree(pRootDict.Get());
93 WideString storedName;
94 nameTree.LookupValueAndName(0, &storedName);
95 EXPECT_STREQ(L"1", storedName.c_str());
96
97 // Check that the correct value object can be obtained by looking up "1".
98 WideString matchName = L"1";
99 CPDF_Object* pObj = nameTree.LookupValue(matchName);
100 ASSERT_TRUE(pObj->IsNumber());
101 EXPECT_EQ(100, pObj->AsNumber()->GetInteger());
102 }
103
TEST(cpdf_nametree,AddIntoNames)104 TEST(cpdf_nametree, AddIntoNames) {
105 // Set up a name tree with a single Names array.
106 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
107 CPDF_Array* pNames = pRootDict->SetNewFor<CPDF_Array>("Names");
108 AddNameKeyValue(pNames, "2.txt", 222);
109 AddNameKeyValue(pNames, "7.txt", 777);
110
111 CPDF_NameTree nameTree(pRootDict.Get());
112 pNames = nameTree.GetRootForTest()->GetArrayFor("Names");
113
114 // Insert a name that already exists in the names array.
115 EXPECT_FALSE(
116 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111), L"2.txt"));
117
118 // Insert in the beginning of the names array.
119 EXPECT_TRUE(
120 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111), L"1.txt"));
121
122 // Insert in the middle of the names array.
123 EXPECT_TRUE(
124 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(555), L"5.txt"));
125
126 // Insert at the end of the names array.
127 EXPECT_TRUE(
128 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(999), L"9.txt"));
129
130 // Check that the names array has the expected key-value pairs.
131 CheckNameKeyValue(pNames, 0, "1.txt", 111);
132 CheckNameKeyValue(pNames, 1, "2.txt", 222);
133 CheckNameKeyValue(pNames, 2, "5.txt", 555);
134 CheckNameKeyValue(pNames, 3, "7.txt", 777);
135 CheckNameKeyValue(pNames, 4, "9.txt", 999);
136 }
137
TEST(cpdf_nametree,AddIntoKids)138 TEST(cpdf_nametree, AddIntoKids) {
139 // Set up a name tree with five nodes of three levels.
140 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
141 FillNameTreeDict(pRootDict.Get());
142 CPDF_NameTree nameTree(pRootDict.Get());
143
144 // Check that adding an existing name would fail.
145 EXPECT_FALSE(
146 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(444), L"9.txt"));
147
148 // Add a name within the limits of a leaf node.
149 EXPECT_TRUE(
150 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(444), L"4.txt"));
151 ASSERT_TRUE(nameTree.LookupValue(L"4.txt"));
152 EXPECT_EQ(444, nameTree.LookupValue(L"4.txt")->GetInteger());
153
154 // Add a name that requires changing the limits of two bottom levels.
155 EXPECT_TRUE(
156 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(666), L"6.txt"));
157 ASSERT_TRUE(nameTree.LookupValue(L"6.txt"));
158 EXPECT_EQ(666, nameTree.LookupValue(L"6.txt")->GetInteger());
159
160 // Add a name that requires changing the limits of two top levels.
161 EXPECT_TRUE(
162 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(99), L"99.txt"));
163 ASSERT_TRUE(nameTree.LookupValue(L"99.txt"));
164 EXPECT_EQ(99, nameTree.LookupValue(L"99.txt")->GetInteger());
165
166 // Add a name that requires changing the lower limit of all levels.
167 EXPECT_TRUE(
168 nameTree.AddValueAndName(pdfium::MakeRetain<CPDF_Number>(-5), L"0.txt"));
169 ASSERT_TRUE(nameTree.LookupValue(L"0.txt"));
170 EXPECT_EQ(-5, nameTree.LookupValue(L"0.txt")->GetInteger());
171
172 // Check that the node on the first level has the expected limits.
173 CPDF_Dictionary* pKid1 =
174 nameTree.GetRootForTest()->GetArrayFor("Kids")->GetDictAt(0);
175 ASSERT_TRUE(pKid1);
176 CheckLimitsArray(pKid1, "0.txt", "99.txt");
177
178 // Check that the nodes on the second level has the expected limits and names.
179 CPDF_Dictionary* pKid2 = pKid1->GetArrayFor("Kids")->GetDictAt(0);
180 ASSERT_TRUE(pKid2);
181 CheckLimitsArray(pKid2, "0.txt", "6.txt");
182
183 CPDF_Dictionary* pKid3 = pKid1->GetArrayFor("Kids")->GetDictAt(1);
184 ASSERT_TRUE(pKid3);
185 CheckLimitsArray(pKid3, "9.txt", "99.txt");
186 CPDF_Array* pNames = pKid3->GetArrayFor("Names");
187 ASSERT_TRUE(pNames);
188 CheckNameKeyValue(pNames, 0, "9.txt", 999);
189 CheckNameKeyValue(pNames, 1, "99.txt", 99);
190
191 // Check that the nodes on the third level has the expected limits and names.
192 CPDF_Dictionary* pKid4 = pKid2->GetArrayFor("Kids")->GetDictAt(0);
193 ASSERT_TRUE(pKid4);
194 CheckLimitsArray(pKid4, "0.txt", "2.txt");
195 pNames = pKid4->GetArrayFor("Names");
196 ASSERT_TRUE(pNames);
197 CheckNameKeyValue(pNames, 0, "0.txt", -5);
198 CheckNameKeyValue(pNames, 1, "1.txt", 111);
199 CheckNameKeyValue(pNames, 2, "2.txt", 222);
200
201 CPDF_Dictionary* pKid5 = pKid2->GetArrayFor("Kids")->GetDictAt(1);
202 ASSERT_TRUE(pKid5);
203 CheckLimitsArray(pKid5, "3.txt", "6.txt");
204 pNames = pKid5->GetArrayFor("Names");
205 ASSERT_TRUE(pNames);
206 CheckNameKeyValue(pNames, 0, "3.txt", 333);
207 CheckNameKeyValue(pNames, 1, "4.txt", 444);
208 CheckNameKeyValue(pNames, 2, "5.txt", 555);
209 CheckNameKeyValue(pNames, 3, "6.txt", 666);
210 }
211
TEST(cpdf_nametree,DeleteFromKids)212 TEST(cpdf_nametree, DeleteFromKids) {
213 // Set up a name tree with five nodes of three levels.
214 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
215 FillNameTreeDict(pRootDict.Get());
216 CPDF_NameTree nameTree(pRootDict.Get());
217
218 // Retrieve the kid dictionaries.
219 CPDF_Dictionary* pKid1 =
220 nameTree.GetRootForTest()->GetArrayFor("Kids")->GetDictAt(0);
221 ASSERT_TRUE(pKid1);
222 CPDF_Dictionary* pKid2 = pKid1->GetArrayFor("Kids")->GetDictAt(0);
223 ASSERT_TRUE(pKid2);
224 CPDF_Dictionary* pKid3 = pKid1->GetArrayFor("Kids")->GetDictAt(1);
225 ASSERT_TRUE(pKid3);
226 CPDF_Dictionary* pKid4 = pKid2->GetArrayFor("Kids")->GetDictAt(0);
227 ASSERT_TRUE(pKid4);
228 CPDF_Dictionary* pKid5 = pKid2->GetArrayFor("Kids")->GetDictAt(1);
229 ASSERT_TRUE(pKid5);
230
231 // Check that deleting an out-of-bound index would fail.
232 EXPECT_FALSE(nameTree.DeleteValueAndName(5));
233
234 // Delete the name "9.txt", and check that its node gets deleted and its
235 // parent node's limits get updated.
236 WideString csName;
237 ASSERT_TRUE(nameTree.LookupValue(L"9.txt"));
238 EXPECT_EQ(999, nameTree.LookupValue(L"9.txt")->GetInteger());
239 EXPECT_TRUE(nameTree.LookupValueAndName(4, &csName));
240 EXPECT_STREQ(L"9.txt", csName.c_str());
241 EXPECT_EQ(2u, pKid1->GetArrayFor("Kids")->size());
242 EXPECT_TRUE(nameTree.DeleteValueAndName(4));
243 EXPECT_EQ(1u, pKid1->GetArrayFor("Kids")->size());
244 CheckLimitsArray(pKid1, "1.txt", "5.txt");
245
246 // Delete the name "2.txt", and check that its node does not get deleted, its
247 // node's limits get updated, and no other limits get updated.
248 ASSERT_TRUE(nameTree.LookupValue(L"2.txt"));
249 EXPECT_EQ(222, nameTree.LookupValue(L"2.txt")->GetInteger());
250 EXPECT_TRUE(nameTree.LookupValueAndName(1, &csName));
251 EXPECT_STREQ(L"2.txt", csName.c_str());
252 EXPECT_EQ(4u, pKid4->GetArrayFor("Names")->size());
253 EXPECT_TRUE(nameTree.DeleteValueAndName(1));
254 EXPECT_EQ(2u, pKid4->GetArrayFor("Names")->size());
255 CheckLimitsArray(pKid4, "1.txt", "1.txt");
256 CheckLimitsArray(pKid2, "1.txt", "5.txt");
257 CheckLimitsArray(pKid1, "1.txt", "5.txt");
258
259 // Delete the name "1.txt", and check that its node gets deleted, and its
260 // parent's and gradparent's limits get updated.
261 ASSERT_TRUE(nameTree.LookupValue(L"1.txt"));
262 EXPECT_EQ(111, nameTree.LookupValue(L"1.txt")->GetInteger());
263 EXPECT_TRUE(nameTree.LookupValueAndName(0, &csName));
264 EXPECT_STREQ(L"1.txt", csName.c_str());
265 EXPECT_EQ(2u, pKid2->GetArrayFor("Kids")->size());
266 EXPECT_TRUE(nameTree.DeleteValueAndName(0));
267 EXPECT_EQ(1u, pKid2->GetArrayFor("Kids")->size());
268 CheckLimitsArray(pKid2, "3.txt", "5.txt");
269 CheckLimitsArray(pKid1, "3.txt", "5.txt");
270
271 // Delete the name "3.txt", and check that its node does not get deleted, and
272 // its node's, its parent's, and its grandparent's limits get updated.
273 ASSERT_TRUE(nameTree.LookupValue(L"3.txt"));
274 EXPECT_EQ(333, nameTree.LookupValue(L"3.txt")->GetInteger());
275 EXPECT_TRUE(nameTree.LookupValueAndName(0, &csName));
276 EXPECT_STREQ(L"3.txt", csName.c_str());
277 EXPECT_EQ(4u, pKid5->GetArrayFor("Names")->size());
278 EXPECT_TRUE(nameTree.DeleteValueAndName(0));
279 EXPECT_EQ(2u, pKid5->GetArrayFor("Names")->size());
280 CheckLimitsArray(pKid5, "5.txt", "5.txt");
281 CheckLimitsArray(pKid2, "5.txt", "5.txt");
282 CheckLimitsArray(pKid1, "5.txt", "5.txt");
283
284 // Delete the name "5.txt", and check that all nodes in the tree get deleted
285 // since they are now all empty.
286 ASSERT_TRUE(nameTree.LookupValue(L"5.txt"));
287 EXPECT_EQ(555, nameTree.LookupValue(L"5.txt")->GetInteger());
288 EXPECT_TRUE(nameTree.LookupValueAndName(0, &csName));
289 EXPECT_STREQ(L"5.txt", csName.c_str());
290 EXPECT_EQ(1u, nameTree.GetRootForTest()->GetArrayFor("Kids")->size());
291 EXPECT_TRUE(nameTree.DeleteValueAndName(0));
292 EXPECT_EQ(0u, nameTree.GetRootForTest()->GetArrayFor("Kids")->size());
293
294 // Check that the tree is now empty.
295 EXPECT_EQ(0u, nameTree.GetCount());
296 EXPECT_FALSE(nameTree.LookupValueAndName(0, &csName));
297 EXPECT_FALSE(nameTree.DeleteValueAndName(0));
298 }
299