Traverse PDF page tree only once in CPDF_Document

core/fpdfapi/parser/cpdf_document.cpp

 // Copyright 2014 PDFium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 // Original code copyright 2014 Foxit Software Inc. http://www.foxitsoftware.com
 
 #include "core/fpdfapi/parser/cpdf_document.h"
 
 #include <memory>
 #include <set>
@@ skipping 396 matching lines @@
 }
 
 }  // namespace
 
 CPDF_Document::CPDF_Document(std::unique_ptr<CPDF_Parser> pParser)
     : CPDF_IndirectObjectHolder(),
       m_pParser(std::move(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)),
       m_pDocRender(new CPDF_DocRenderData(this)),
       m_pByteStringPool(pdfium::MakeUnique<CFX_ByteStringPool>()) {
   if (pParser)
     SetLastObjNum(m_pParser->GetLastObjNum());
 }
 
 CPDF_Document::~CPDF_Document() {
@@ skipping 43 matching lines @@
 
   CPDF_Object* pObjNum = pLinearizationParams->GetObjectFor("O");
   if (ToNumber(pObjNum))
     m_dwFirstPageObjNum = pObjNum->GetInteger();
 }
 
 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 {
   CPDF_Dictionary* pRoot = GetRoot();
   return pRoot ? pRoot->GetDictFor("Pages") : nullptr;
 }
 
 bool CPDF_Document::IsPageLoaded(int iPage) const {
   return !!m_PageList.GetAt(iPage);
 }
 
 CPDF_Dictionary* CPDF_Document::GetPage(int iPage) {
   if (iPage < 0 || iPage >= m_PageList.GetSize())
     return nullptr;
 
   if (m_bLinearized && (iPage == m_iFirstPageNo)) {
     if (CPDF_Dictionary* pDict =
             ToDictionary(GetOrParseIndirectObject(m_dwFirstPageObjNum))) {
       return pDict;
     }
   }
 
+  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) {
   m_PageList.SetAt(iPage, objNum);
 }
 
 int CPDF_Document::FindPageIndex(CPDF_Dictionary* pNode,
                                  uint32_t& skip_count,
                                  uint32_t objnum,
                                  int& index,
@@ skipping 451 matching lines @@
                         pBBox, pLogFont->lfWeight / 5);
   pFontDesc->SetIntegerFor("CapHeight", capheight);
   pFontDict->SetReferenceFor("FontDescriptor", this,
                              AddIndirectObject(pFontDesc));
   hFont = SelectObject(hDC, hFont);
   DeleteObject(hFont);
   DeleteDC(hDC);
   return LoadFont(pBaseDict);
 }
 #endif  //  _FXM_PLATFORM_ == _FXM_PLATFORM_WINDOWS_