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>
+#include <utility>
 #include <vector>
 
 #include "core/fpdfapi/cpdf_modulemgr.h"
 #include "core/fpdfapi/font/cpdf_fontencoding.h"
 #include "core/fpdfapi/page/cpdf_docpagedata.h"
 #include "core/fpdfapi/page/cpdf_pagemodule.h"
 #include "core/fpdfapi/page/pageint.h"
 #include "core/fpdfapi/parser/cpdf_array.h"
 #include "core/fpdfapi/parser/cpdf_dictionary.h"
 #include "core/fpdfapi/parser/cpdf_number.h"
@@ skipping 234 matching lines @@
     if (pKid->GetStringFor("Type") == "Page") {
       if (nPagesToGo == 0) {
         if (bInsert) {
           pKidList->InsertAt(i, new CPDF_Reference(pDoc, pPage->GetObjNum()));
           pPage->SetReferenceFor("Parent", pDoc, pPages->GetObjNum());
         } else {
           pKidList->RemoveAt(i);
         }
         pPages->SetIntegerFor(
             "Count", pPages->GetIntegerFor("Count") + (bInsert ? 1 : -1));
+        // Tree will change, so reset tree transversal variables
+        pDoc->m_iLastPageTraversed = -1;
+        pDoc->m_pTreeTraversal = std::stack<std::pair<CPDF_Dictionary*, int>>();
         return 1;
       }
       nPagesToGo--;
     } else {
       int nPages = pKid->GetIntegerFor("Count");
       if (nPagesToGo < nPages) {
         if (pdfium::ContainsKey(*pVisited, pKid))
           return -1;
 
         pdfium::ScopedSetInsertion<CPDF_Dictionary*> insertion(pVisited, pKid);
@@ skipping 128 matching lines @@
   pFontDesc->SetIntegerFor("Ascent", ascend);
   pFontDesc->SetIntegerFor("Descent", descend);
   pFontDesc->SetIntegerFor("StemV", stemV);
   return pFontDesc;
 }
 
 }  // namespace
 
 CPDF_Document::CPDF_Document(std::unique_ptr<CPDF_Parser> pParser)
     : CPDF_IndirectObjectHolder(),
+      m_iLastPageTraversed(-1),
       m_pParser(std::move(pParser)),
       m_pRootDict(nullptr),
       m_pInfoDict(nullptr),
       m_bLinearized(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)
@@ skipping 47 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) {
+CPDF_Dictionary* CPDF_Document::TraversePDFPages(int iPage, int nPagesToGo) {
+  std::pair<CPDF_Dictionary*, int>* lastProc = &m_pTreeTraversal.top();
+  CPDF_Dictionary* pPages = lastProc->first;
   CPDF_Array* pKidList = pPages->GetArrayFor("Kids");
-  if (!pKidList)
-    return nPagesToGo == 0 ? pPages : nullptr;
+  if (!pKidList) {
+    m_pTreeTraversal.pop();
+    if (nPagesToGo != 1)

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

Before nPagesToGo was the number of pages left minus 1. So compare with 1
instead of 0.

[dsinclair, 2016/10/18 13:35:59]

So, this is check if we're on the page we're looking for?

[npm, 2016/10/18 14:26:31]

The if(!pKidList) will only be entered when the root node is actually page.
Notice that we don't add nodes without Kids into the stack in this method.
If the root has no kids, it has to be a single page.

+      return nullptr;
+    m_PageList.SetAt(iPage, pPages->GetObjNum());
+    return pPages;
+  }
 
-  if (level >= FX_MAX_PAGE_LEVEL)
+  if (m_pTreeTraversal.size() >= FX_MAX_PAGE_LEVEL) {
+    m_pTreeTraversal.pop();
     return nullptr;
+  }
 
-  for (size_t i = 0; i < pKidList->GetCount(); i++) {
+  bool shouldFinish = pPages->GetIntegerFor("Count") <= nPagesToGo;

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

This will make sure that the page is popped properly even when the number
of leafs does not match Count.

+  CPDF_Dictionary* page = nullptr;
+  for (size_t i = lastProc->second + 1; i < pKidList->GetCount(); i++) {

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

lastProc->second is the index of the last completely processed kid, which
initially is -1, and should be pKidList->GetCount()-1 when done.

     CPDF_Dictionary* pKid = pKidList->GetDictAt(i);
     if (!pKid) {
       nPagesToGo--;
+      lastProc->second++;
       continue;
     }
-    if (pKid == pPages)
+    if (pKid == pPages) {
+      lastProc->second++;
       continue;
+    }
     if (!pKid->KeyExist("Kids")) {
-      if (nPagesToGo == 0)
-        return pKid;
-
-      m_PageList.SetAt(iPage - nPagesToGo, pKid->GetObjNum());
+      m_PageList.SetAt(iPage - nPagesToGo + 1, pKid->GetObjNum());
       nPagesToGo--;
+      lastProc->second++;
+      if (nPagesToGo == 0) {
+        page = pKid;
+        break;
+      }
     } else {
       int nPages = pKid->GetIntegerFor("Count");
-      if (nPagesToGo < nPages)
-        return FindPDFPage(pKid, iPage, nPagesToGo, level + 1);
-
+      m_pTreeTraversal.push(std::make_pair(pKid, -1));
+      CPDF_Dictionary* pageKid = TraversePDFPages(iPage, nPagesToGo);
+      // If the stack top is current element, kid was completely processed.
+      if (lastProc == &m_pTreeTraversal.top())
+        lastProc->second++;
+      if (nPagesToGo <= nPages) {
+        page = pageKid;
+        break;
+      }
       nPagesToGo -= nPages;
     }
   }
-  return nullptr;
+  if (shouldFinish ||
+      lastProc->second == static_cast<int>(pKidList->GetCount() - 1)) {
+    m_pTreeTraversal.pop();
+  }
+  return page;
 }
 
 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;
     }
   }
 
   int objnum = m_PageList.GetAt(iPage);
-  if (objnum) {
-    if (CPDF_Dictionary* pDict = ToDictionary(GetOrParseIndirectObject(objnum)))
-      return pDict;
+  if (!objnum || m_iLastPageTraversed < iPage) {
+    CPDF_Dictionary* pPages = GetPagesDict();
+    if (!pPages)
+      return nullptr;
+    if (m_pTreeTraversal.empty())
+      m_pTreeTraversal.push(std::make_pair(pPages, -1));
+    CPDF_Dictionary* page = TraversePDFPages(m_iLastPageTraversed + 1,
+                                             iPage - m_iLastPageTraversed);
+    m_iLastPageTraversed = iPage;
+    return page;
   }
-
-  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;
+  if (CPDF_Dictionary* pDict = ToDictionary(GetOrParseIndirectObject(objnum)))
+    return pDict;
+  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_