Traverse PDF page tree only once in CPDF_Document Try 3

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 222 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),

[Tom Sepez, 2016/11/02 17:37:37]

nit: without actually looking, my hunch is that its easier to track the next
untraversed page than the last traversed one.

[npm, 2016/11/03 00:18:25]

If that makes the code clearer, I can do that. It is just a shift by 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) {
+// When this is called, m_pTreeTraversal[level] exists
+CPDF_Dictionary* CPDF_Document::TraversePDFPages(int iPage,
+                                                 int& nPagesToGo,

[Tom Sepez, 2016/11/02 17:37:37]

I can't help but think this might be easier if we had current page number and an
absolute page number to stop at rather than counting down and maybe missing a
place in some branch.

Here's a suggestion.  Maybe this needs a helper function that's responsible for
flattening, and a top-level function that just gets the value out of the
flattened tree.

[npm, 2016/11/03 00:18:25]

If I understand correctly what you mean by current/absolute, current is iPage -
nPagesToGo + 1, and
absolute is iPage. I can change the meaning of nPagestoGo to be the current
page, if that makes things
more clear.

As for the suggestion, I don't understand exactly what you mean. The problem I
see is we would have to
'partially flatten' the tree up to the page we're supposed to stop at. And I
don't see how doing that without
losing track of what we have flattened and what's still missing will be easier
than the current implementation.

+                                                 int level) {
+  CPDF_Dictionary* pPages = m_pTreeTraversal[level].first;
   CPDF_Array* pKidList = pPages->GetArrayFor("Kids");
-  if (!pKidList)
-    return nPagesToGo == 0 ? pPages : nullptr;
+  if (!pKidList) {
+    if (nPagesToGo != 1)
+      return nullptr;
+    m_PageList.SetAt(iPage, pPages->GetObjNum());
+    return pPages;
+  }
 
-  if (level >= FX_MAX_PAGE_LEVEL)
+  if (level >= FX_MAX_PAGE_LEVEL) {
+    m_pTreeTraversal.pop_back();
     return nullptr;
+  }
 
-  for (size_t i = 0; i < pKidList->GetCount(); i++) {
+  CPDF_Dictionary* page = nullptr;
+  for (size_t i = m_pTreeTraversal[level].second; i < pKidList->GetCount();
+       i++) {
     CPDF_Dictionary* pKid = pKidList->GetDictAt(i);
     if (!pKid) {
       nPagesToGo--;

[Tom Sepez, 2016/11/02 17:37:37]

I worry about this going negative here ...

[npm, 2016/11/03 00:18:25]

Yes, this can go negative. This wouldn't be a problem, other than we processed
some more nodes than was needed.
But this can be avoided by adding a check before the end of the for, so we break
when we are about to go negative.

+      m_pTreeTraversal[level].second++;
       continue;
     }
-    if (pKid == pPages)
+    if (pKid == pPages) {
+      m_pTreeTraversal[level].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--;
+      m_pTreeTraversal[level].second++;
+      if (nPagesToGo == 0) {
+        page = pKid;
+        break;
+      }
     } else {
-      int nPages = pKid->GetIntegerFor("Count");
-      if (nPagesToGo < nPages)
-        return FindPDFPage(pKid, iPage, nPagesToGo, level + 1);
-
-      nPagesToGo -= nPages;
+      // If the vector has size level+1, the child is not in yet
+      if (static_cast<int>(m_pTreeTraversal.size()) == level + 1)
+        m_pTreeTraversal.push_back(std::make_pair(pKid, 0));
+      // Now m_pTreeTraversal[level+1] should exist and be equal to pKid.
+      CPDF_Dictionary* pageKid = TraversePDFPages(iPage, nPagesToGo, level + 1);
+      // Check if child was completely processed, i.e. it popped itself out
+      if (static_cast<int>(m_pTreeTraversal.size()) == level + 1)
+        m_pTreeTraversal[level].second++;
+      // If child did not finish or if no pages to go, we are done
+      if (static_cast<int>(m_pTreeTraversal.size()) != level + 1 ||
+          nPagesToGo <= 0) {
+        page = pageKid;
+        break;
+      }
     }
   }
-  return nullptr;
+  if (m_pTreeTraversal[level].second ==
+      static_cast<int>(pKidList->GetCount())) {
+    m_pTreeTraversal.pop_back();
+  }
+  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;
+    return nullptr;
   }
 
   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());
+  if (m_pTreeTraversal.empty())
+    m_pTreeTraversal.push_back(std::make_pair(pPages, 0));
+  int nPagesToGo = iPage - m_iLastPageTraversed;
+  CPDF_Dictionary* pPage = TraversePDFPages(iPage, nPagesToGo, 0);
+  m_iLastPageTraversed = iPage;
   return pPage;
 }
 
 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,
@@ skipping 142 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,

[Tom Sepez, 2016/11/02 17:37:37]

can we do this refactoring first as a separate CL?  I like these being methods
and removing the |this|, but its hard to see what else changed.

[npm, 2016/11/03 00:18:25]

Sounds good, will do.

+                                       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.clear();
+        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());
+    // Reset tree transversal variables
+    m_iLastPageTraversed = -1;
+    m_pTreeTraversal.clear();
+  } 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_