Traverse PDF page tree only once in CPDF_Document Try 2

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 212 matching lines @@
   int size = end - start + 1;
   int* widths = FX_Alloc(int, size);
   int i;
   for (i = 0; i < size; i++) {
     int glyph_index = pEncoding->GlyphFromCharCode(start + i);
     widths[i] = pFont->GetGlyphWidth(glyph_index);
   }
   InsertWidthArrayImpl(widths, size, pWidthArray);
 }
 
-int InsertDeletePDFPage(CPDF_Document* pDoc,
-                        CPDF_Dictionary* pPages,
-                        int nPagesToGo,
-                        CPDF_Dictionary* pPage,
-                        FX_BOOL bInsert,
-                        std::set<CPDF_Dictionary*>* pVisited) {
-  CPDF_Array* pKidList = pPages->GetArrayFor("Kids");
-  if (!pKidList)
-    return -1;
-
-  for (size_t i = 0; i < pKidList->GetCount(); i++) {
-    CPDF_Dictionary* pKid = pKidList->GetDictAt(i);
-    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));
-        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);
-        if (InsertDeletePDFPage(pDoc, pKid, nPagesToGo, pPage, bInsert,
-                                pVisited) < 0) {
-          return -1;
-        }
-        pPages->SetIntegerFor(
-            "Count", pPages->GetIntegerFor("Count") + (bInsert ? 1 : -1));
-        return 1;
-      }
-      nPagesToGo -= nPages;
-    }
-  }
-  return 0;
-}
-
-int InsertNewPage(CPDF_Document* pDoc,
-                  int iPage,
-                  CPDF_Dictionary* pPageDict,
-                  CFX_ArrayTemplate<uint32_t>& pageList) {
-  CPDF_Dictionary* pRoot = pDoc->GetRoot();
-  CPDF_Dictionary* pPages = pRoot ? pRoot->GetDictFor("Pages") : nullptr;
-  if (!pPages)
-    return -1;
-
-  int nPages = pDoc->GetPageCount();
-  if (iPage < 0 || iPage > nPages)
-    return -1;
-
-  if (iPage == nPages) {
-    CPDF_Array* pPagesList = pPages->GetArrayFor("Kids");
-    if (!pPagesList) {
-      pPagesList = new CPDF_Array;
-      pPages->SetFor("Kids", pPagesList);
-    }
-    pPagesList->Add(new CPDF_Reference(pDoc, pPageDict->GetObjNum()));
-    pPages->SetIntegerFor("Count", nPages + 1);
-    pPageDict->SetReferenceFor("Parent", pDoc, pPages->GetObjNum());
-  } else {
-    std::set<CPDF_Dictionary*> stack = {pPages};
-    if (InsertDeletePDFPage(pDoc, pPages, iPage, pPageDict, TRUE, &stack) < 0)
-      return -1;
-  }
-  pageList.InsertAt(iPage, pPageDict->GetObjNum());
-  return iPage;
-}
-
 int CountPages(CPDF_Dictionary* pPages,
                std::set<CPDF_Dictionary*>* visited_pages) {
   int count = pPages->GetIntegerFor("Count");
   if (count > 0 && count < FPDF_PAGE_MAX_NUM)
     return count;
   CPDF_Array* pKidList = pPages->GetArrayFor("Kids");
   if (!pKidList)
     return 0;
   count = 0;
   for (size_t i = 0; i < pKidList->GetCount(); i++) {
@@ skipping 76 matching lines @@
   return pFontDesc;
 }
 
 }  // 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_iLastPageTraversed(-1),
       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)
     SetLastObjNum(m_pParser->GetLastObjNum());
 }
 
@@ skipping 44 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::PopAndPropagate() {

[npm, 2016/10/26 15:04:06]

Pop current node. Update index for the parent. Pop parent if it is done.

+  m_pTreeTraversal.pop();

[Tom Sepez, 2016/10/26 15:52:23]

Do we know that it's not empty to begin with?

[npm, 2016/10/26 17:20:18]

Yes, it is only be called when it is nonempty.

+  if (!m_pTreeTraversal.empty()) {

[Tom Sepez, 2016/10/26 15:52:23]

nit: maybe early return.

[npm, 2016/10/26 17:20:18]

Done.

+    std::pair<CPDF_Dictionary*, int>* top = &m_pTreeTraversal.top();
+    top->second++;
+    if (top->second ==
+        static_cast<int>(top->first->GetArrayFor("Kids")->GetCount() - 1))

[Tom Sepez, 2016/10/26 15:52:23]

can count change inbetween subsequent calls so that we might skip over the end
and iterate forever?

[npm, 2016/10/26 17:20:18]

When it is changed in InsertDeletePDFPage, we reset the pdf traversing.
Added reset to place in InsertNewPage where it can change.
CreateNewDoc sets Count to 1, but always called right after constructor.

+      PopAndPropagate();
+  }
+}
+
+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) {

[npm, 2016/10/26 15:04:06]

This only happens when Pages dict is actually a page.

+    PopAndPropagate();
+    if (nPagesToGo != 1)
+      return nullptr;
+    m_PageList.SetAt(iPage, pPages->GetObjNum());
+    return pPages;
+  }
 
-  if (level >= FX_MAX_PAGE_LEVEL)
+  if (m_pTreeTraversal.size() >= FX_MAX_PAGE_LEVEL) {
+    PopAndPropagate();
     return nullptr;
+  }
 
-  for (size_t i = 0; i < pKidList->GetCount(); i++) {
+  CPDF_Dictionary* page = nullptr;
+  for (size_t i = lastProc->second + 1; i < pKidList->GetCount(); i++) {
     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));

[npm, 2016/10/26 15:04:06]

Traverse kid, and break if the number of pages to go is <= number of pages
in the kid, since this means that the answer is whatever the kid found.

+      CPDF_Dictionary* pageKid = TraversePDFPages(iPage, nPagesToGo);
+      if (nPagesToGo <= nPages) {
+        page = pageKid;
+        break;
+      }
       nPagesToGo -= nPages;
     }
   }
-  return nullptr;
+  if (!m_pTreeTraversal.empty() && lastProc == &m_pTreeTraversal.top() &&
+      lastProc->second == static_cast<int>(pKidList->GetCount() - 1)) {
+    PopAndPropagate();
+  }
+  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) {
+    CPDF_Dictionary* pPages = GetPagesDict();
+    if (!pPages)
+      return nullptr;
+    if (m_pTreeTraversal.empty())
+      m_pTreeTraversal.push(std::make_pair(pPages, -1));
+    CPDF_Dictionary* page =
+        TraversePDFPages(iPage, iPage - m_iLastPageTraversed);

[npm, 2016/10/26 15:04:06]

Traverse iPage - m_iLastPageTraversed pages, where the last page
processed is iPage

+    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 141 matching lines @@
   pPages->SetFor("Kids", new CPDF_Array);
   m_pRootDict->SetReferenceFor("Pages", this, AddIndirectObject(pPages));
   m_pInfoDict = new CPDF_Dictionary(m_pByteStringPool);
   AddIndirectObject(m_pInfoDict);
 }
 
 CPDF_Dictionary* CPDF_Document::CreateNewPage(int iPage) {
   CPDF_Dictionary* pDict = new CPDF_Dictionary(m_pByteStringPool);
   pDict->SetNameFor("Type", "Page");
   uint32_t dwObjNum = AddIndirectObject(pDict);
-  if (InsertNewPage(this, iPage, pDict, m_PageList) < 0) {
+  if (InsertNewPage(iPage, pDict, m_PageList) < 0) {
     ReleaseIndirectObject(dwObjNum);
     return nullptr;
   }
   return pDict;
 }
 
+int CPDF_Document::InsertDeletePDFPage(CPDF_Dictionary* pPages,
+                                       int nPagesToGo,
+                                       CPDF_Dictionary* pPage,
+                                       FX_BOOL bInsert,
+                                       std::set<CPDF_Dictionary*>* pVisited) {
+  CPDF_Array* pKidList = pPages->GetArrayFor("Kids");
+  if (!pKidList)
+    return -1;
+
+  for (size_t i = 0; i < pKidList->GetCount(); i++) {
+    CPDF_Dictionary* pKid = pKidList->GetDictAt(i);
+    if (pKid->GetStringFor("Type") == "Page") {
+      if (nPagesToGo == 0) {
+        if (bInsert) {
+          pKidList->InsertAt(i, new CPDF_Reference(this, pPage->GetObjNum()));
+          pPage->SetReferenceFor("Parent", this, pPages->GetObjNum());
+        } else {
+          pKidList->RemoveAt(i);
+        }
+        pPages->SetIntegerFor(
+            "Count", pPages->GetIntegerFor("Count") + (bInsert ? 1 : -1));
+        // Tree will change, so reset tree transversal variables
+        m_iLastPageTraversed = -1;
+        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);
+        if (InsertDeletePDFPage(pKid, nPagesToGo, pPage, bInsert, pVisited) <
+            0) {
+          return -1;
+        }
+        pPages->SetIntegerFor(
+            "Count", pPages->GetIntegerFor("Count") + (bInsert ? 1 : -1));
+        return 1;
+      }
+      nPagesToGo -= nPages;
+    }
+  }
+  return 0;
+}
+
+int CPDF_Document::InsertNewPage(int iPage,
+                                 CPDF_Dictionary* pPageDict,
+                                 CFX_ArrayTemplate<uint32_t>& pageList) {
+  CPDF_Dictionary* pRoot = GetRoot();
+  CPDF_Dictionary* pPages = pRoot ? pRoot->GetDictFor("Pages") : nullptr;
+  if (!pPages)
+    return -1;
+
+  int nPages = GetPageCount();
+  if (iPage < 0 || iPage > nPages)
+    return -1;
+
+  if (iPage == nPages) {
+    CPDF_Array* pPagesList = pPages->GetArrayFor("Kids");
+    if (!pPagesList) {
+      pPagesList = new CPDF_Array;
+      pPages->SetFor("Kids", pPagesList);
+    }
+    pPagesList->Add(new CPDF_Reference(this, pPageDict->GetObjNum()));
+    pPages->SetIntegerFor("Count", nPages + 1);
+    pPageDict->SetReferenceFor("Parent", this, pPages->GetObjNum());
+  } else {
+    std::set<CPDF_Dictionary*> stack = {pPages};
+    if (InsertDeletePDFPage(pPages, iPage, pPageDict, TRUE, &stack) < 0)
+      return -1;
+  }
+  pageList.InsertAt(iPage, pPageDict->GetObjNum());
+  return iPage;
+}
+
 void CPDF_Document::DeletePage(int iPage) {
   CPDF_Dictionary* pPages = GetPagesDict();
   if (!pPages)
     return;
 
   int nPages = pPages->GetIntegerFor("Count");
   if (iPage < 0 || iPage >= nPages)
     return;
 
   std::set<CPDF_Dictionary*> stack = {pPages};
-  if (InsertDeletePDFPage(this, pPages, iPage, nullptr, FALSE, &stack) < 0)
+  if (InsertDeletePDFPage(pPages, iPage, nullptr, FALSE, &stack) < 0)
     return;
 
   m_PageList.RemoveAt(iPage);
 }
 
 CPDF_Font* CPDF_Document::AddStandardFont(const FX_CHAR* font,
                                           CPDF_FontEncoding* pEncoding) {
   CFX_ByteString name(font);
   if (PDF_GetStandardFontName(&name) < 0)
     return nullptr;
@@ skipping 272 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_