Traverse PDF page tree only once in CPDF_Document

core/fpdfapi/parser/cpdf_document.cpp

Index: core/fpdfapi/parser/cpdf_document.cpp
diff --git a/core/fpdfapi/parser/cpdf_document.cpp b/core/fpdfapi/parser/cpdf_document.cpp
index c5f64a790ca1d31f6cb4357f5a01b18d6b0585e1..2ef164dbd9a97a0de8700fd7c8f47320d85754ea 100644
--- a/core/fpdfapi/parser/cpdf_document.cpp
+++ b/core/fpdfapi/parser/cpdf_document.cpp
@@ -414,6 +414,7 @@ CPDF_Document::CPDF_Document(std::unique_ptr<CPDF_Parser> pParser)
       m_pRootDict(nullptr),
       m_pInfoDict(nullptr),
       m_bLinearized(false),
+      m_bPagesTraversed(false),
       m_iFirstPageNo(0),
       m_dwFirstPageObjNum(0),
       m_pDocPage(new CPDF_DocPageData(this)),
@@ -477,40 +478,37 @@ void CPDF_Document::LoadPages() {
   m_PageList.SetSize(RetrievePageCount());
 }
 
-CPDF_Dictionary* CPDF_Document::FindPDFPage(CPDF_Dictionary* pPages,
-                                            int iPage,
-                                            int nPagesToGo,
-                                            int level) {
+void CPDF_Document::TraversePDFPages(CPDF_Dictionary* pPages,
+                                     int iPage,
+                                     int level) {
+  if (iPage >= m_PageList.GetSize())
+    return;
   CPDF_Array* pKidList = pPages->GetArrayFor("Kids");
-  if (!pKidList)
-    return nPagesToGo == 0 ? pPages : nullptr;
+  if (!pKidList) {
+    m_PageList.SetAt(iPage, pPages->GetObjNum());
+    return;
+  }
 
   if (level >= FX_MAX_PAGE_LEVEL)
-    return nullptr;
+    return;
 
   for (size_t i = 0; i < pKidList->GetCount(); i++) {
     CPDF_Dictionary* pKid = pKidList->GetDictAt(i);
     if (!pKid) {
-      nPagesToGo--;
+      iPage++;
       continue;
     }
     if (pKid == pPages)
       continue;
     if (!pKid->KeyExist("Kids")) {
-      if (nPagesToGo == 0)
-        return pKid;
-
-      m_PageList.SetAt(iPage - nPagesToGo, pKid->GetObjNum());
-      nPagesToGo--;
+      m_PageList.SetAt(iPage, pKid->GetObjNum());
+      iPage++;
     } else {
       int nPages = pKid->GetIntegerFor("Count");

[Tom Sepez, 2016/10/14 19:01:16]

I think we have to deal with the situation where Count does not agree with
sizeof /Kids array, which is why they had a separate parameter.

[npm, 2016/10/14 19:31:25]

Well, it is not clear to me how we should behave in that case.
But in fact I think this will behave similar in that case:

if Count > sizeOf, some pages indices will be skipped
if Count < sizeOf, all the pages in the Kids array will be used.
But then iPage only increases by Count. So if there's anything after,
the m_PageList values for those will be overriden.

Before this CL:
if Count > sizeOf, some pages indices will be skipped
if Count < sizeOf, the excess pages will be ignored.

[dsinclair, 2016/10/17 13:26:37]

Should we increase iPage by the min(count, sizeof Kids array) to fix the issue
where we either skip or ignore?

[npm, 2016/10/17 21:10:23]

We were not doing this before. I think this might not be the right thing to do:
we should use Count to keep track of the page indices, that is its purpose.

-      if (nPagesToGo < nPages)
-        return FindPDFPage(pKid, iPage, nPagesToGo, level + 1);
-
-      nPagesToGo -= nPages;
+      TraversePDFPages(pKid, iPage, level + 1);
+      iPage += nPages;
     }
   }
-  return nullptr;
 }
 
 CPDF_Dictionary* CPDF_Document::GetPagesDict() const {
@@ -533,22 +531,20 @@ CPDF_Dictionary* CPDF_Document::GetPage(int iPage) {
     }
   }
 
+  if (!m_bPagesTraversed) {
+    CPDF_Dictionary* pPages = GetPagesDict();
+    if (!pPages)
+      return nullptr;
+
+    TraversePDFPages(pPages, 0, 0);

[dsinclair, 2016/10/17 13:26:37]

This may have to do more work then needed in some cases. If we have a 10k page
document and we just want page 1 we'll have to walk all 10k pages the first time
instead of just the first page.

[npm, 2016/10/17 21:10:23]

Changed to traverse only until needed.

+    m_bPagesTraversed = true;
+  }
   int objnum = m_PageList.GetAt(iPage);
   if (objnum) {
     if (CPDF_Dictionary* pDict = ToDictionary(GetOrParseIndirectObject(objnum)))
       return pDict;
   }
-
-  CPDF_Dictionary* pPages = GetPagesDict();
-  if (!pPages)
-    return nullptr;
-
-  CPDF_Dictionary* pPage = FindPDFPage(pPages, iPage, iPage, 0);
-  if (!pPage)
-    return nullptr;
-
-  m_PageList.SetAt(iPage, pPage->GetObjNum());
-  return pPage;
+  return nullptr;
 }
 
 void CPDF_Document::SetPageObjNum(int iPage, uint32_t objNum) {