1 // Copyright 2017 The PDFium Authors
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 "core/fxcrt/retain_ptr.h"
11 #include "testing/gtest/include/gtest/gtest.h"
12
13 namespace {
14
AddNameKeyValue(CPDF_Array * names,const char * key,int value)15 void AddNameKeyValue(CPDF_Array* names, const char* key, int value) {
16 names->AppendNew<CPDF_String>(key, false);
17 names->AppendNew<CPDF_Number>(value);
18 }
19
CheckNameKeyValue(const CPDF_Array * names,int pair_index,const char * key,int value)20 void CheckNameKeyValue(const CPDF_Array* names,
21 int pair_index,
22 const char* key,
23 int value) {
24 ASSERT_TRUE(names);
25 EXPECT_STREQ(key, names->GetByteStringAt(pair_index * 2).c_str());
26 EXPECT_EQ(value, names->GetIntegerAt(pair_index * 2 + 1));
27 }
28
AddLimitsArray(CPDF_Dictionary * node,const char * least,const char * greatest)29 void AddLimitsArray(CPDF_Dictionary* node,
30 const char* least,
31 const char* greatest) {
32 auto limits = node->SetNewFor<CPDF_Array>("Limits");
33 limits->AppendNew<CPDF_String>(least, false);
34 limits->AppendNew<CPDF_String>(greatest, false);
35 }
36
CheckLimitsArray(const CPDF_Dictionary * node,const char * least,const char * greatest)37 void CheckLimitsArray(const CPDF_Dictionary* node,
38 const char* least,
39 const char* greatest) {
40 ASSERT_TRUE(node);
41 RetainPtr<const CPDF_Array> limits = node->GetArrayFor("Limits");
42 ASSERT_TRUE(limits);
43 EXPECT_EQ(2u, limits->size());
44 RetainPtr<const CPDF_String> left = limits->GetStringAt(0);
45 ASSERT_TRUE(left);
46 RetainPtr<const CPDF_String> right = limits->GetStringAt(1);
47 ASSERT_TRUE(right);
48 EXPECT_STREQ(least, left->GetString().c_str());
49 EXPECT_STREQ(greatest, right->GetString().c_str());
50 }
51
52 // Set up a name tree with 3 levels and 5 nodes, per diagram:
53 //
54 // [root]
55 // |
56 // |
57 // |
58 // [pKid1]
59 // |
60 // +------------+
61 // | |
62 // [pGrandKid2] [pGrandKid3]
63 // | {9.txt: 999}
64 // |
65 // +-----------------+
66 // | |
67 // [pGreatGrandKid4] [pGreatGrandKid5]
68 // {1.txt: 111} {3.txt: 333}
69 // {2.txt: 222} {5.txt: 555}
70 //
FillNameTreeDict(CPDF_Dictionary * pRootDict)71 void FillNameTreeDict(CPDF_Dictionary* pRootDict) {
72 auto pRootKids = pRootDict->SetNewFor<CPDF_Array>("Kids");
73 auto pKid1 = pRootKids->AppendNew<CPDF_Dictionary>();
74
75 // Make the lower and upper limit out of order on purpose.
76 AddLimitsArray(pKid1.Get(), "9.txt", "1.txt");
77 auto pKids1Kids = pKid1->SetNewFor<CPDF_Array>("Kids");
78 auto pGrandKid2 = pKids1Kids->AppendNew<CPDF_Dictionary>();
79 auto pGrandKid3 = pKids1Kids->AppendNew<CPDF_Dictionary>();
80
81 AddLimitsArray(pGrandKid2.Get(), "1.txt", "5.txt");
82 auto pGrandKid2Kids = pGrandKid2->SetNewFor<CPDF_Array>("Kids");
83 auto pGreatGrandKid4 = pGrandKid2Kids->AppendNew<CPDF_Dictionary>();
84 auto pGreatGrandKid5 = pGrandKid2Kids->AppendNew<CPDF_Dictionary>();
85
86 AddLimitsArray(pGrandKid3.Get(), "9.txt", "9.txt");
87 auto pNames = pGrandKid3->SetNewFor<CPDF_Array>("Names");
88 AddNameKeyValue(pNames.Get(), "9.txt", 999);
89
90 // Make the lower and upper limit out of order on purpose.
91 AddLimitsArray(pGreatGrandKid4.Get(), "2.txt", "1.txt");
92 pNames = pGreatGrandKid4->SetNewFor<CPDF_Array>("Names");
93 AddNameKeyValue(pNames.Get(), "1.txt", 111);
94 AddNameKeyValue(pNames.Get(), "2.txt", 222);
95
96 AddLimitsArray(pGreatGrandKid5.Get(), "3.txt", "5.txt");
97 pNames = pGreatGrandKid5->SetNewFor<CPDF_Array>("Names");
98 AddNameKeyValue(pNames.Get(), "3.txt", 333);
99 AddNameKeyValue(pNames.Get(), "5.txt", 555);
100 }
101
102 } // namespace
103
TEST(cpdf_nametree,GetUnicodeNameWithBOM)104 TEST(cpdf_nametree, GetUnicodeNameWithBOM) {
105 // Set up the root dictionary with a Names array.
106 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
107 auto pNames = pRootDict->SetNewFor<CPDF_Array>("Names");
108
109 // Add the key "1" (with BOM) and value 100 into the array.
110 constexpr char kData[] = "\xFE\xFF\x00\x31";
111 pNames->AppendNew<CPDF_String>(ByteString(kData, sizeof(kData) - 1), true);
112 pNames->AppendNew<CPDF_Number>(100);
113
114 // Check that the key is as expected.
115 std::unique_ptr<CPDF_NameTree> name_tree =
116 CPDF_NameTree::CreateForTesting(pRootDict.Get());
117 WideString stored_name;
118 name_tree->LookupValueAndName(0, &stored_name);
119 EXPECT_STREQ(L"1", stored_name.c_str());
120
121 // Check that the correct value object can be obtained by looking up "1".
122 RetainPtr<const CPDF_Number> pNumber = ToNumber(name_tree->LookupValue(L"1"));
123 ASSERT_TRUE(pNumber);
124 EXPECT_EQ(100, pNumber->GetInteger());
125 }
126
TEST(cpdf_nametree,GetFromTreeWithLimitsArrayWith4Items)127 TEST(cpdf_nametree, GetFromTreeWithLimitsArrayWith4Items) {
128 // After creating a name tree, mutate a /Limits array so it has excess
129 // elements.
130 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
131 FillNameTreeDict(pRootDict.Get());
132 RetainPtr<CPDF_Dictionary> pKid1 =
133 pRootDict->GetMutableArrayFor("Kids")->GetMutableDictAt(0);
134 RetainPtr<CPDF_Dictionary> pGrandKid3 =
135 pKid1->GetMutableArrayFor("Kids")->GetMutableDictAt(1);
136 RetainPtr<CPDF_Array> pLimits = pGrandKid3->GetMutableArrayFor("Limits");
137 ASSERT_EQ(2u, pLimits->size());
138 pLimits->AppendNew<CPDF_Number>(5);
139 pLimits->AppendNew<CPDF_Number>(6);
140 ASSERT_EQ(4u, pLimits->size());
141 std::unique_ptr<CPDF_NameTree> name_tree =
142 CPDF_NameTree::CreateForTesting(pRootDict.Get());
143
144 RetainPtr<const CPDF_Number> pNumber =
145 ToNumber(name_tree->LookupValue(L"9.txt"));
146 ASSERT_TRUE(pNumber);
147 EXPECT_EQ(999, pNumber->GetInteger());
148 CheckLimitsArray(pKid1.Get(), "1.txt", "9.txt");
149 CheckLimitsArray(pGrandKid3.Get(), "9.txt", "9.txt");
150 }
151
TEST(cpdf_nametree,AddIntoNames)152 TEST(cpdf_nametree, AddIntoNames) {
153 // Set up a name tree with a single Names array.
154 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
155 auto pNames = pRootDict->SetNewFor<CPDF_Array>("Names");
156 AddNameKeyValue(pNames.Get(), "2.txt", 222);
157 AddNameKeyValue(pNames.Get(), "7.txt", 777);
158
159 std::unique_ptr<CPDF_NameTree> name_tree =
160 CPDF_NameTree::CreateForTesting(pRootDict.Get());
161
162 // Insert a name that already exists in the names array.
163 EXPECT_FALSE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111),
164 L"2.txt"));
165
166 // Insert in the beginning of the names array.
167 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111),
168 L"1.txt"));
169
170 // Insert in the middle of the names array.
171 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(555),
172 L"5.txt"));
173
174 // Insert at the end of the names array.
175 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(999),
176 L"9.txt"));
177
178 // Check that the names array has the expected key-value pairs.
179 CheckNameKeyValue(pNames.Get(), 0, "1.txt", 111);
180 CheckNameKeyValue(pNames.Get(), 1, "2.txt", 222);
181 CheckNameKeyValue(pNames.Get(), 2, "5.txt", 555);
182 CheckNameKeyValue(pNames.Get(), 3, "7.txt", 777);
183 CheckNameKeyValue(pNames.Get(), 4, "9.txt", 999);
184 }
185
TEST(cpdf_nametree,AddIntoEmptyNames)186 TEST(cpdf_nametree, AddIntoEmptyNames) {
187 // Set up a name tree with an empty Names array.
188 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
189 auto pNames = pRootDict->SetNewFor<CPDF_Array>("Names");
190
191 std::unique_ptr<CPDF_NameTree> name_tree =
192 CPDF_NameTree::CreateForTesting(pRootDict.Get());
193
194 // Insert a name should work.
195 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111),
196 L"2.txt"));
197
198 // Insert a name that already exists in the names array.
199 EXPECT_FALSE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111),
200 L"2.txt"));
201
202 // Insert in the beginning of the names array.
203 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(111),
204 L"1.txt"));
205
206 // Insert in the middle of the names array.
207 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(555),
208 L"5.txt"));
209
210 // Insert at the end of the names array.
211 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(999),
212 L"9.txt"));
213
214 // Check that the names array has the expected key-value pairs.
215 CheckNameKeyValue(pNames.Get(), 0, "1.txt", 111);
216 CheckNameKeyValue(pNames.Get(), 1, "2.txt", 111);
217 CheckNameKeyValue(pNames.Get(), 2, "5.txt", 555);
218 CheckNameKeyValue(pNames.Get(), 3, "9.txt", 999);
219 }
220
TEST(cpdf_nametree,AddIntoKids)221 TEST(cpdf_nametree, AddIntoKids) {
222 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
223 FillNameTreeDict(pRootDict.Get());
224 std::unique_ptr<CPDF_NameTree> name_tree =
225 CPDF_NameTree::CreateForTesting(pRootDict.Get());
226
227 // Check that adding an existing name would fail.
228 EXPECT_FALSE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(444),
229 L"9.txt"));
230
231 // Add a name within the limits of a leaf node.
232 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(444),
233 L"4.txt"));
234 ASSERT_TRUE(name_tree->LookupValue(L"4.txt"));
235 EXPECT_EQ(444, name_tree->LookupValue(L"4.txt")->GetInteger());
236
237 // Add a name that requires changing the limits of two bottom levels.
238 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(666),
239 L"6.txt"));
240 ASSERT_TRUE(name_tree->LookupValue(L"6.txt"));
241 EXPECT_EQ(666, name_tree->LookupValue(L"6.txt")->GetInteger());
242
243 // Add a name that requires changing the limits of two top levels.
244 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(99),
245 L"99.txt"));
246 ASSERT_TRUE(name_tree->LookupValue(L"99.txt"));
247 EXPECT_EQ(99, name_tree->LookupValue(L"99.txt")->GetInteger());
248
249 // Add a name that requires changing the lower limit of all levels.
250 EXPECT_TRUE(name_tree->AddValueAndName(pdfium::MakeRetain<CPDF_Number>(-5),
251 L"0.txt"));
252 ASSERT_TRUE(name_tree->LookupValue(L"0.txt"));
253 EXPECT_EQ(-5, name_tree->LookupValue(L"0.txt")->GetInteger());
254
255 // Check that the node on the first level has the expected limits.
256 RetainPtr<const CPDF_Dictionary> pKid1 =
257 name_tree->GetRootForTesting()->GetArrayFor("Kids")->GetDictAt(0);
258 ASSERT_TRUE(pKid1);
259 CheckLimitsArray(pKid1.Get(), "0.txt", "99.txt");
260
261 // Check that the nodes on the second level has the expected limits and names.
262 RetainPtr<const CPDF_Dictionary> pGrandKid2 =
263 pKid1->GetArrayFor("Kids")->GetDictAt(0);
264 ASSERT_TRUE(pGrandKid2);
265 CheckLimitsArray(pGrandKid2.Get(), "0.txt", "6.txt");
266
267 RetainPtr<const CPDF_Dictionary> pGrandKid3 =
268 pKid1->GetArrayFor("Kids")->GetDictAt(1);
269 ASSERT_TRUE(pGrandKid3);
270 CheckLimitsArray(pGrandKid3.Get(), "9.txt", "99.txt");
271 RetainPtr<const CPDF_Array> pNames = pGrandKid3->GetArrayFor("Names");
272 CheckNameKeyValue(pNames.Get(), 0, "9.txt", 999);
273 CheckNameKeyValue(pNames.Get(), 1, "99.txt", 99);
274
275 // Check that the nodes on the third level has the expected limits and names.
276 RetainPtr<const CPDF_Dictionary> pGreatGrandKid4 =
277 pGrandKid2->GetArrayFor("Kids")->GetDictAt(0);
278 ASSERT_TRUE(pGreatGrandKid4);
279 CheckLimitsArray(pGreatGrandKid4.Get(), "0.txt", "2.txt");
280 pNames = pGreatGrandKid4->GetArrayFor("Names");
281 CheckNameKeyValue(pNames.Get(), 0, "0.txt", -5);
282 CheckNameKeyValue(pNames.Get(), 1, "1.txt", 111);
283 CheckNameKeyValue(pNames.Get(), 2, "2.txt", 222);
284
285 RetainPtr<const CPDF_Dictionary> pGreatGrandKid5 =
286 pGrandKid2->GetArrayFor("Kids")->GetDictAt(1);
287 ASSERT_TRUE(pGreatGrandKid5);
288 CheckLimitsArray(pGreatGrandKid5.Get(), "3.txt", "6.txt");
289 pNames = pGreatGrandKid5->GetArrayFor("Names");
290 CheckNameKeyValue(pNames.Get(), 0, "3.txt", 333);
291 CheckNameKeyValue(pNames.Get(), 1, "4.txt", 444);
292 CheckNameKeyValue(pNames.Get(), 2, "5.txt", 555);
293 CheckNameKeyValue(pNames.Get(), 3, "6.txt", 666);
294 }
295
TEST(cpdf_nametree,DeleteFromKids)296 TEST(cpdf_nametree, DeleteFromKids) {
297 auto pRootDict = pdfium::MakeRetain<CPDF_Dictionary>();
298 FillNameTreeDict(pRootDict.Get());
299 std::unique_ptr<CPDF_NameTree> name_tree =
300 CPDF_NameTree::CreateForTesting(pRootDict.Get());
301
302 // Retrieve the kid dictionaries.
303 RetainPtr<const CPDF_Dictionary> pKid1 =
304 name_tree->GetRootForTesting()->GetArrayFor("Kids")->GetDictAt(0);
305 ASSERT_TRUE(pKid1);
306 RetainPtr<const CPDF_Dictionary> pGrandKid2 =
307 pKid1->GetArrayFor("Kids")->GetDictAt(0);
308 ASSERT_TRUE(pGrandKid2);
309 RetainPtr<const CPDF_Dictionary> pGrandKid3 =
310 pKid1->GetArrayFor("Kids")->GetDictAt(1);
311 ASSERT_TRUE(pGrandKid3);
312 RetainPtr<const CPDF_Dictionary> pGreatGrandKid4 =
313 pGrandKid2->GetArrayFor("Kids")->GetDictAt(0);
314 ASSERT_TRUE(pGreatGrandKid4);
315 RetainPtr<const CPDF_Dictionary> pGreatGrandKid5 =
316 pGrandKid2->GetArrayFor("Kids")->GetDictAt(1);
317 ASSERT_TRUE(pGreatGrandKid5);
318
319 // Check that deleting an out-of-bound index would fail.
320 EXPECT_FALSE(name_tree->DeleteValueAndName(5));
321
322 // Delete the name "9.txt", and check that its node gets deleted and its
323 // parent node's limits get updated.
324 WideString csName;
325 ASSERT_TRUE(name_tree->LookupValue(L"9.txt"));
326 EXPECT_EQ(999, name_tree->LookupValue(L"9.txt")->GetInteger());
327 EXPECT_TRUE(name_tree->LookupValueAndName(4, &csName));
328 EXPECT_STREQ(L"9.txt", csName.c_str());
329 EXPECT_EQ(2u, pKid1->GetArrayFor("Kids")->size());
330 EXPECT_TRUE(name_tree->DeleteValueAndName(4));
331 EXPECT_EQ(1u, pKid1->GetArrayFor("Kids")->size());
332 CheckLimitsArray(pKid1.Get(), "1.txt", "5.txt");
333
334 // Delete the name "2.txt", and check that its node does not get deleted, its
335 // node's limits get updated, and no other limits get updated.
336 ASSERT_TRUE(name_tree->LookupValue(L"2.txt"));
337 EXPECT_EQ(222, name_tree->LookupValue(L"2.txt")->GetInteger());
338 EXPECT_TRUE(name_tree->LookupValueAndName(1, &csName));
339 EXPECT_STREQ(L"2.txt", csName.c_str());
340 EXPECT_EQ(4u, pGreatGrandKid4->GetArrayFor("Names")->size());
341 EXPECT_TRUE(name_tree->DeleteValueAndName(1));
342 EXPECT_EQ(2u, pGreatGrandKid4->GetArrayFor("Names")->size());
343 CheckLimitsArray(pGreatGrandKid4.Get(), "1.txt", "1.txt");
344 CheckLimitsArray(pGrandKid2.Get(), "1.txt", "5.txt");
345 CheckLimitsArray(pKid1.Get(), "1.txt", "5.txt");
346
347 // Delete the name "1.txt", and check that its node gets deleted, and its
348 // parent's and gradparent's limits get updated.
349 ASSERT_TRUE(name_tree->LookupValue(L"1.txt"));
350 EXPECT_EQ(111, name_tree->LookupValue(L"1.txt")->GetInteger());
351 EXPECT_TRUE(name_tree->LookupValueAndName(0, &csName));
352 EXPECT_STREQ(L"1.txt", csName.c_str());
353 EXPECT_EQ(2u, pGrandKid2->GetArrayFor("Kids")->size());
354 EXPECT_TRUE(name_tree->DeleteValueAndName(0));
355 EXPECT_EQ(1u, pGrandKid2->GetArrayFor("Kids")->size());
356 CheckLimitsArray(pGrandKid2.Get(), "3.txt", "5.txt");
357 CheckLimitsArray(pKid1.Get(), "3.txt", "5.txt");
358
359 // Delete the name "3.txt", and check that its node does not get deleted, and
360 // its node's, its parent's, and its grandparent's limits get updated.
361 ASSERT_TRUE(name_tree->LookupValue(L"3.txt"));
362 EXPECT_EQ(333, name_tree->LookupValue(L"3.txt")->GetInteger());
363 EXPECT_TRUE(name_tree->LookupValueAndName(0, &csName));
364 EXPECT_STREQ(L"3.txt", csName.c_str());
365 EXPECT_EQ(4u, pGreatGrandKid5->GetArrayFor("Names")->size());
366 EXPECT_TRUE(name_tree->DeleteValueAndName(0));
367 EXPECT_EQ(2u, pGreatGrandKid5->GetArrayFor("Names")->size());
368 CheckLimitsArray(pGreatGrandKid5.Get(), "5.txt", "5.txt");
369 CheckLimitsArray(pGrandKid2.Get(), "5.txt", "5.txt");
370 CheckLimitsArray(pKid1.Get(), "5.txt", "5.txt");
371
372 // Delete the name "5.txt", and check that all nodes in the tree get deleted
373 // since they are now all empty.
374 ASSERT_TRUE(name_tree->LookupValue(L"5.txt"));
375 EXPECT_EQ(555, name_tree->LookupValue(L"5.txt")->GetInteger());
376 EXPECT_TRUE(name_tree->LookupValueAndName(0, &csName));
377 EXPECT_STREQ(L"5.txt", csName.c_str());
378 EXPECT_EQ(1u, name_tree->GetRootForTesting()->GetArrayFor("Kids")->size());
379 EXPECT_TRUE(name_tree->DeleteValueAndName(0));
380 EXPECT_EQ(0u, name_tree->GetRootForTesting()->GetArrayFor("Kids")->size());
381
382 // Check that the tree is now empty.
383 EXPECT_EQ(0u, name_tree->GetCount());
384 EXPECT_FALSE(name_tree->LookupValueAndName(0, &csName));
385 EXPECT_FALSE(name_tree->DeleteValueAndName(0));
386 }
387