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