Fix infinite loop for bookmark search

BUG=pdfium:420
R=tsepez@chromium.org

Review URL: https://codereview.chromium.org/1757373002 .

4 files changed, 251 insertions, 7 deletions

diff --git a/fpdfsdk/src/fpdfdoc.cpp b/fpdfsdk/src/fpdfdoc.cpp
index 50f3e2c904..4b5da2ffc3 100644
--- a/fpdfsdk/src/fpdfdoc.cpp
+++ b/fpdfsdk/src/fpdfdoc.cpp
@@ -6,7 +6,10 @@
 
 #include "public/fpdf_doc.h"
 
+#include <set>
+
 #include "fpdfsdk/include/fsdk_define.h"
+#include "third_party/base/stl_util.h"
 
 namespace {
 
@@ -14,17 +17,24 @@ int THISMODULE = 0;
 
 CPDF_Bookmark FindBookmark(const CPDF_BookmarkTree& tree,
                            CPDF_Bookmark bookmark,
-                           const CFX_WideString& title) {
+                           const CFX_WideString& title,
+                           std::set<CPDF_Dictionary*>* visited) {
+  // Return if already checked to avoid circular calling.
+  if (pdfium::ContainsKey(*visited, bookmark.GetDict()))
+    return CPDF_Bookmark();
+  visited->insert(bookmark.GetDict());
+
   if (bookmark.GetDict() &&
       bookmark.GetTitle().CompareNoCase(title.c_str()) == 0) {
-    // First check this item
+    // First check this item.
     return bookmark;
   }
-  // go into children items
+
+  // Go into children items.
   CPDF_Bookmark child = tree.GetFirstChild(bookmark);
-  while (child.GetDict()) {
-    // check if this item
-    CPDF_Bookmark found = FindBookmark(tree, child, title);
+  while (child.GetDict() && !pdfium::ContainsKey(*visited, child.GetDict())) {
+    // Check this item and its children.
+    CPDF_Bookmark found = FindBookmark(tree, child, title, visited);
     if (found.GetDict())
       return found;
     child = tree.GetNextSibling(child);
@@ -101,7 +111,8 @@ DLLEXPORT FPDF_BOOKMARK STDCALL FPDFBookmark_Find(FPDF_DOCUMENT document,
   CPDF_BookmarkTree tree(pDoc);
   FX_STRSIZE len = CFX_WideString::WStringLength(title);
   CFX_WideString encodedTitle = CFX_WideString::FromUTF16LE(title, len);
-  return FindBookmark(tree, CPDF_Bookmark(), encodedTitle).GetDict();
+  std::set<CPDF_Dictionary*> visited;
+  return FindBookmark(tree, CPDF_Bookmark(), encodedTitle, &visited).GetDict();
 }
 
 DLLEXPORT FPDF_DEST STDCALL FPDFBookmark_GetDest(FPDF_DOCUMENT document,
diff --git a/fpdfsdk/src/fpdfdoc_embeddertest.cpp b/fpdfsdk/src/fpdfdoc_embeddertest.cpp
index a789dade36..0ca6a48ca7 100644
--- a/fpdfsdk/src/fpdfdoc_embeddertest.cpp
+++ b/fpdfsdk/src/fpdfdoc_embeddertest.cpp
@@ -125,3 +125,14 @@ TEST_F(FPDFDocEmbeddertest, FindBookmarks) {
       GetFPDFWideString(L"A BAD Beginning");
   EXPECT_EQ(nullptr, FPDFBookmark_Find(document(), bad_title.get()));
 }
+
+// Check circular bookmarks will not cause infinite loop.
+TEST_F(FPDFDocEmbeddertest, FindBookmarks_bug420) {
+  // Open a file with circular bookmarks.
+  EXPECT_TRUE(OpenDocument("bookmarks_circular.pdf"));
+
+  // Try to find a title.
+  std::unique_ptr<unsigned short, pdfium::FreeDeleter> title =
+      GetFPDFWideString(L"anything");
+  EXPECT_EQ(nullptr, FPDFBookmark_Find(document(), title.get()));
+}
diff --git a/testing/resources/bookmarks_circular.in b/testing/resources/bookmarks_circular.in
new file mode 100644
index 0000000000..48a5695e17
--- /dev/null
+++ b/testing/resources/bookmarks_circular.in
@@ -0,0 +1,98 @@
+{{header}}
+{{object 1 0}} <<
+  /Type /Catalog
+  /Pages 2 0 R
+  /Outlines 14 0 R
+>>
+endobj
+{{object 2 0}} <<
+  /Type /Pages
+  /Count 2
+  /Kids [
+    3 0 R
+    4 0 R
+  ]
+>>
+endobj
+% Page number 0.
+{{object 3 0}} <<
+  /Type /Page
+  /Parent 2 0 R
+  /Resources <<
+    /Font <</F1 15 0 R>>
+  >>
+  /Contents [21 0 R]
+  /MediaBox [0 0 612 792]
+>>
+endobj
+% Page number 1.
+{{object 4 0}} <<
+  /Type /Page
+  /Parent 2 0 R
+  /Resources  <<
+    /Font <</F1 15 0 R>>
+  >>
+  /Contents [22 0 R]
+  /MediaBox [0 0 612 792]
+>>
+endobj
+% First bookmark
+{{object 10 0}} <<
+  /Title (A Good Beginning)
+  /Parent 14 0 R
+  /Next 11 0 R
+  /Dest (foo)
+>>
+endobj
+% Last bookmark
+{{object 11 0}} <<
+  /Title (A Good Ending)
+  /Parent 14 0 R
+  /Next 10 0 R
+  /Dest (bar)
+>>
+endobj
+% Root bookmark
+{{object 14 0}} <<
+  /Type /Outlines
+  /First 10 0 R
+  /Last  11 0 R
+  /Count 2
+>>
+endobj
+% Font resource.
+{{object 15 0}} <<
+  /Type /Font
+  /Subtype /Type1
+  /BaseFont /Arial
+>>
+endobj
+% Content for page 0.
+{{object 21 0}} <<
+  /Length 0
+>>
+stream
+BT
+/F1 20 Tf
+100 600 TD (Page1)Tj
+ET
+endstream
+endobj
+% Content for page 1.
+{{object 22 0}} <<
+  /Length 0
+>>
+stream
+BT
+/F1 20 Tf
+100 600 TD (Page2)Tj
+ET
+endstream
+endobj
+{{xref}}
+trailer <<
+  /Size 6
+  /Root 1 0 R
+>>
+{{startxref}}
+%%EOF
diff --git a/testing/resources/bookmarks_circular.pdf b/testing/resources/bookmarks_circular.pdf
new file mode 100644
index 0000000000..e7eb624781
--- /dev/null
+++ b/testing/resources/bookmarks_circular.pdf
@@ -0,0 +1,124 @@
+%PDF-1.7
+% ò¤ô
+1 0 obj <<
+  /Type /Catalog
+  /Pages 2 0 R
+  /Outlines 14 0 R
+>>
+endobj
+2 0 obj <<
+  /Type /Pages
+  /Count 2
+  /Kids [
+    3 0 R
+    4 0 R
+  ]
+>>
+endobj
+% Page number 0.
+3 0 obj <<
+  /Type /Page
+  /Parent 2 0 R
+  /Resources <<
+    /Font <</F1 15 0 R>>
+  >>
+  /Contents [21 0 R]
+  /MediaBox [0 0 612 792]
+>>
+endobj
+% Page number 1.
+4 0 obj <<
+  /Type /Page
+  /Parent 2 0 R
+  /Resources  <<
+    /Font <</F1 15 0 R>>
+  >>
+  /Contents [22 0 R]
+  /MediaBox [0 0 612 792]
+>>
+endobj
+% First bookmark
+10 0 obj <<
+  /Title (A Good Beginning)
+  /Parent 14 0 R
+  /Next 11 0 R
+  /Dest (foo)
+>>
+endobj
+% Last bookmark
+11 0 obj <<
+  /Title (A Good Ending)
+  /Parent 14 0 R
+  /Next 10 0 R
+  /Dest (bar)
+>>
+endobj
+% Root bookmark
+14 0 obj <<
+  /Type /Outlines
+  /First 10 0 R
+  /Last  11 0 R
+  /Count 2
+>>
+endobj
+% Font resource.
+15 0 obj <<
+  /Type /Font
+  /Subtype /Type1
+  /BaseFont /Arial
+>>
+endobj
+% Content for page 0.
+21 0 obj <<
+  /Length 0
+>>
+stream
+BT
+/F1 20 Tf
+100 600 TD (Page1)Tj
+ET
+endstream
+endobj
+% Content for page 1.
+22 0 obj <<
+  /Length 0
+>>
+stream
+BT
+/F1 20 Tf
+100 600 TD (Page2)Tj
+ET
+endstream
+endobj
+xref
+0 23
+0000000000 65535 f 
+0000000015 00000 n 
+0000000087 00000 n 
+0000000185 00000 n 
+0000000346 00000 n 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000508 00000 n 
+0000000620 00000 n 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000729 00000 n 
+0000000829 00000 n 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000000 65535 f 
+0000000924 00000 n 
+0000001034 00000 n 
+trailer <<
+  /Size 6
+  /Root 1 0 R
+>>
+startxref
+1122
+%%EOF