Implement FakeFileAccess.
Update embedder tests to simulate unavailable data and download requests.
Change-Id: I634fa89d2a0c859243e849752936da87568909f4
Reviewed-on: https://pdfium-review.googlesource.com/11890
Commit-Queue: Art Snake <art-snake@yandex-team.ru>
Reviewed-by: dsinclair <dsinclair@chromium.org>
diff --git a/BUILD.gn b/BUILD.gn
index 25c805c..5657ac1 100644
--- a/BUILD.gn
+++ b/BUILD.gn
@@ -2029,6 +2029,10 @@
"testing/embedder_test.h",
"testing/embedder_test_mock_delegate.h",
"testing/embedder_test_timer_handling_delegate.h",
+ "testing/fake_file_access.cpp",
+ "testing/fake_file_access.h",
+ "testing/range_set.cpp",
+ "testing/range_set.h",
]
deps = [
":pdfium",
diff --git a/core/fpdfapi/parser/cpdf_security_handler_embeddertest.cpp b/core/fpdfapi/parser/cpdf_security_handler_embeddertest.cpp
index 49a898f..91346da 100644
--- a/core/fpdfapi/parser/cpdf_security_handler_embeddertest.cpp
+++ b/core/fpdfapi/parser/cpdf_security_handler_embeddertest.cpp
@@ -62,6 +62,7 @@
CompareBitmap(page_bitmap, 612, 792, md5);
FPDFBitmap_Destroy(page_bitmap);
EXPECT_TRUE(FPDFPage_GenerateContent(page));
+ SetWholeFileAvailable();
EXPECT_TRUE(FPDF_SaveAsCopy(document(), this, 0));
UnloadPage(page);
}
diff --git a/fpdfsdk/fpdf_dataavail_embeddertest.cpp b/fpdfsdk/fpdf_dataavail_embeddertest.cpp
index c40f857..2084153 100644
--- a/fpdfsdk/fpdf_dataavail_embeddertest.cpp
+++ b/fpdfsdk/fpdf_dataavail_embeddertest.cpp
@@ -12,10 +12,25 @@
#include "public/fpdfview.h"
#include "testing/embedder_test.h"
#include "testing/gtest/include/gtest/gtest.h"
+#include "testing/range_set.h"
#include "testing/test_support.h"
#include "testing/utils/path_service.h"
namespace {
+
+class MockDownloadHints : public FX_DOWNLOADHINTS {
+ public:
+ static void SAddSegment(FX_DOWNLOADHINTS* pThis, size_t offset, size_t size) {
+ }
+
+ MockDownloadHints() {
+ FX_DOWNLOADHINTS::version = 1;
+ FX_DOWNLOADHINTS::AddSegment = SAddSegment;
+ }
+
+ ~MockDownloadHints() {}
+};
+
class TestAsyncLoader : public FX_DOWNLOADHINTS, FX_FILEAVAIL {
public:
explicit TestAsyncLoader(const std::string& file_name) {
@@ -60,7 +75,9 @@
}
size_t max_already_available_bound() const {
- return available_ranges_.empty() ? 0 : available_ranges_.rbegin()->second;
+ return available_ranges_.IsEmpty()
+ ? 0
+ : available_ranges_.ranges().rbegin()->second;
}
void FlushRequestedData() {
@@ -72,45 +89,11 @@
private:
void SetDataAvailable(size_t start, size_t size) {
- if (size == 0)
- return;
- const auto range = std::make_pair(start, start + size);
- if (available_ranges_.empty()) {
- available_ranges_.insert(range);
- return;
- }
- auto start_it = available_ranges_.upper_bound(range);
- if (start_it != available_ranges_.begin())
- --start_it; // start now points to the key equal or lower than offset.
- if (start_it->second < range.first)
- ++start_it; // start element is entirely before current range, skip it.
-
- auto end_it = available_ranges_.upper_bound(
- std::make_pair(range.second, range.second));
- if (start_it == end_it) { // No ranges to merge.
- available_ranges_.insert(range);
- return;
- }
-
- --end_it;
-
- size_t new_start = std::min<size_t>(start_it->first, range.first);
- size_t new_end = std::max(end_it->second, range.second);
-
- available_ranges_.erase(start_it, ++end_it);
- available_ranges_.insert(std::make_pair(new_start, new_end));
+ available_ranges_.Union(RangeSet::Range(start, start + size));
}
bool CheckDataAlreadyAvailable(size_t start, size_t size) const {
- if (size == 0)
- return false;
- const auto range = std::make_pair(start, start + size);
- auto it = available_ranges_.upper_bound(range);
- if (it == available_ranges_.begin())
- return false; // No ranges includes range.start().
-
- --it; // Now it starts equal or before range.start().
- return it->second >= range.second;
+ return available_ranges_.Contains(RangeSet::Range(start, start + size));
}
int GetBlockImpl(unsigned long pos, unsigned char* pBuf, unsigned long size) {
@@ -165,14 +148,7 @@
size_t max_requested_bound_ = 0;
bool is_new_data_available_ = true;
- using Range = std::pair<size_t, size_t>;
- struct range_compare {
- bool operator()(const Range& lval, const Range& rval) const {
- return lval.first < rval.first;
- }
- };
- using RangesContainer = std::set<Range, range_compare>;
- RangesContainer available_ranges_;
+ RangeSet available_ranges_;
};
} // namespace
@@ -182,13 +158,15 @@
TEST_F(FPDFDataAvailEmbeddertest, TrailerUnterminated) {
// Document must load without crashing but is too malformed to be available.
EXPECT_FALSE(OpenDocument("trailer_unterminated.pdf"));
- EXPECT_FALSE(FPDFAvail_IsDocAvail(avail_, &hints_));
+ MockDownloadHints hints;
+ EXPECT_FALSE(FPDFAvail_IsDocAvail(avail_, &hints));
}
TEST_F(FPDFDataAvailEmbeddertest, TrailerAsHexstring) {
// Document must load without crashing but is too malformed to be available.
EXPECT_FALSE(OpenDocument("trailer_as_hexstring.pdf"));
- EXPECT_FALSE(FPDFAvail_IsDocAvail(avail_, &hints_));
+ MockDownloadHints hints;
+ EXPECT_FALSE(FPDFAvail_IsDocAvail(avail_, &hints));
}
TEST_F(FPDFDataAvailEmbeddertest, LoadUsingHintTables) {
diff --git a/fpdfsdk/fpdfdoc_embeddertest.cpp b/fpdfsdk/fpdfdoc_embeddertest.cpp
index 5db610e..19147d4 100644
--- a/fpdfsdk/fpdfdoc_embeddertest.cpp
+++ b/fpdfsdk/fpdfdoc_embeddertest.cpp
@@ -248,6 +248,10 @@
EXPECT_TRUE(OpenDocument("page_labels.pdf"));
EXPECT_EQ(7, FPDF_GetPageCount(document()));
+ // We do not request labels, when use FPDFAvail_IsXXXAvail.
+ // Flush all data, to allow read labels.
+ SetWholeFileAvailable();
+
unsigned short buf[128];
EXPECT_EQ(0u, FPDF_GetPageLabel(document(), -2, buf, sizeof(buf)));
EXPECT_EQ(0u, FPDF_GetPageLabel(document(), -1, buf, sizeof(buf)));
diff --git a/fpdfsdk/fpdfview_embeddertest.cpp b/fpdfsdk/fpdfview_embeddertest.cpp
index 97ba9d7..699fc8a 100644
--- a/fpdfsdk/fpdfview_embeddertest.cpp
+++ b/fpdfsdk/fpdfview_embeddertest.cpp
@@ -12,6 +12,23 @@
#include "testing/gtest/include/gtest/gtest.h"
#include "testing/utils/path_service.h"
+namespace {
+
+class MockDownloadHints : public FX_DOWNLOADHINTS {
+ public:
+ static void SAddSegment(FX_DOWNLOADHINTS* pThis, size_t offset, size_t size) {
+ }
+
+ MockDownloadHints() {
+ FX_DOWNLOADHINTS::version = 1;
+ FX_DOWNLOADHINTS::AddSegment = SAddSegment;
+ }
+
+ ~MockDownloadHints() {}
+};
+
+} // namespace
+
TEST(fpdf, CApiTest) {
EXPECT_TRUE(CheckPDFiumCApi());
}
@@ -319,12 +336,13 @@
// reference loop. Cross references will be rebuilt successfully.
TEST_F(FPDFViewEmbeddertest, CrossRefV4Loop) {
EXPECT_TRUE(OpenDocument("bug_xrefv4_loop.pdf"));
+ MockDownloadHints hints;
// Make sure calling FPDFAvail_IsDocAvail() on this file does not infinite
// loop either. See bug 875.
int ret = PDF_DATA_NOTAVAIL;
while (ret == PDF_DATA_NOTAVAIL)
- ret = FPDFAvail_IsDocAvail(avail_, &hints_);
+ ret = FPDFAvail_IsDocAvail(avail_, &hints);
EXPECT_EQ(PDF_DATA_AVAIL, ret);
}
diff --git a/testing/embedder_test.cpp b/testing/embedder_test.cpp
index 82ffb3b..dab06af 100644
--- a/testing/embedder_test.cpp
+++ b/testing/embedder_test.cpp
@@ -19,6 +19,7 @@
#include "testing/gmock/include/gmock/gmock.h"
#include "testing/test_support.h"
#include "testing/utils/path_service.h"
+#include "third_party/base/ptr_util.h"
#ifdef PDF_ENABLE_V8
#include "v8/include/v8-platform.h"
@@ -36,12 +37,6 @@
#endif // V8_USE_EXTERNAL_STARTUP_DATA
#endif // PDF_ENABLE_V8
-FPDF_BOOL Is_Data_Avail(FX_FILEAVAIL* pThis, size_t offset, size_t size) {
- return true;
-}
-
-void Add_Segment(FX_DOWNLOADHINTS* pThis, size_t offset, size_t size) {}
-
int GetBitmapBytesPerPixel(FPDF_BITMAP bitmap) {
const int format = FPDFBitmap_GetFormat(bitmap);
switch (format) {
@@ -69,9 +64,7 @@
loader_(nullptr),
file_length_(0),
file_contents_(nullptr) {
- memset(&hints_, 0, sizeof(hints_));
memset(&file_access_, 0, sizeof(file_access_));
- memset(&file_avail_, 0, sizeof(file_avail_));
delegate_ = default_delegate_.get();
#ifdef PDF_ENABLE_V8
@@ -151,46 +144,52 @@
file_access_.m_FileLen = static_cast<unsigned long>(file_length_);
file_access_.m_GetBlock = TestLoader::GetBlock;
file_access_.m_Param = loader_;
- return OpenDocumentHelper(password, must_linearize, &file_avail_, &hints_,
- &file_access_, &document_, &avail_, &form_handle_);
+ fake_file_access_ = pdfium::MakeUnique<FakeFileAccess>(&file_access_);
+ return OpenDocumentHelper(password, must_linearize, fake_file_access_.get(),
+ &document_, &avail_, &form_handle_);
}
bool EmbedderTest::OpenDocumentHelper(const char* password,
bool must_linearize,
- FX_FILEAVAIL* file_avail,
- FX_DOWNLOADHINTS* hints,
- FPDF_FILEACCESS* file_access,
+ FakeFileAccess* network_simulator,
FPDF_DOCUMENT* document,
FPDF_AVAIL* avail,
FPDF_FORMHANDLE* form_handle) {
- file_avail->version = 1;
- file_avail->IsDataAvail = Is_Data_Avail;
-
- hints->version = 1;
- hints->AddSegment = Add_Segment;
-
- *avail = FPDFAvail_Create(file_avail, file_access);
-
+ network_simulator->AddSegment(0, 1024);
+ network_simulator->SetRequestedDataAvailable();
+ *avail = FPDFAvail_Create(network_simulator->GetFileAvail(),
+ network_simulator->GetFileAccess());
if (FPDFAvail_IsLinearized(*avail) == PDF_LINEARIZED) {
+ int32_t nRet = PDF_DATA_NOTAVAIL;
+ while (nRet == PDF_DATA_NOTAVAIL) {
+ network_simulator->SetRequestedDataAvailable();
+ nRet =
+ FPDFAvail_IsDocAvail(*avail, network_simulator->GetDownloadHints());
+ }
+ if (nRet == PDF_DATA_ERROR)
+ return false;
+
*document = FPDFAvail_GetDocument(*avail, password);
if (!*document)
return false;
- int32_t nRet = PDF_DATA_NOTAVAIL;
- while (nRet == PDF_DATA_NOTAVAIL)
- nRet = FPDFAvail_IsDocAvail(*avail, hints);
- if (nRet == PDF_DATA_ERROR)
- return false;
-
- nRet = FPDFAvail_IsFormAvail(*avail, hints);
- if (nRet == PDF_FORM_ERROR || nRet == PDF_FORM_NOTAVAIL)
+ nRet = PDF_DATA_NOTAVAIL;
+ while (nRet == PDF_DATA_NOTAVAIL) {
+ network_simulator->SetRequestedDataAvailable();
+ nRet =
+ FPDFAvail_IsFormAvail(*avail, network_simulator->GetDownloadHints());
+ }
+ if (nRet == PDF_FORM_ERROR)
return false;
int page_count = FPDF_GetPageCount(*document);
for (int i = 0; i < page_count; ++i) {
nRet = PDF_DATA_NOTAVAIL;
- while (nRet == PDF_DATA_NOTAVAIL)
- nRet = FPDFAvail_IsPageAvail(*avail, i, hints);
+ while (nRet == PDF_DATA_NOTAVAIL) {
+ network_simulator->SetRequestedDataAvailable();
+ nRet = FPDFAvail_IsPageAvail(*avail, i,
+ network_simulator->GetDownloadHints());
+ }
if (nRet == PDF_DATA_ERROR)
return false;
@@ -198,8 +197,9 @@
} else {
if (must_linearize)
return false;
-
- *document = FPDF_LoadCustomDocument(file_access, password);
+ network_simulator->SetWholeFileAvailable();
+ *document =
+ FPDF_LoadCustomDocument(network_simulator->GetFileAccess(), password);
if (!*document)
return false;
}
@@ -248,14 +248,16 @@
int EmbedderTest::GetFirstPageNum() {
int first_page = FPDFAvail_GetFirstPageNum(document_);
- (void)FPDFAvail_IsPageAvail(avail_, first_page, &hints_);
+ (void)FPDFAvail_IsPageAvail(avail_, first_page,
+ fake_file_access_->GetDownloadHints());
return first_page;
}
int EmbedderTest::GetPageCount() {
int page_count = FPDF_GetPageCount(document_);
for (int i = 0; i < page_count; ++i)
- (void)FPDFAvail_IsPageAvail(avail_, i, &hints_);
+ (void)FPDFAvail_IsPageAvail(avail_, i,
+ fake_file_access_->GetDownloadHints());
return page_count;
}
@@ -314,16 +316,16 @@
int height,
const char* md5,
const char* password) {
- FPDF_FILEACCESS file_access;
- memset(&file_access, 0, sizeof(file_access));
- file_access.m_FileLen = m_String.size();
- file_access.m_GetBlock = GetBlockFromString;
- file_access.m_Param = &m_String;
- FX_FILEAVAIL file_avail;
- FX_DOWNLOADHINTS hints;
+ memset(&saved_file_access_, 0, sizeof(saved_file_access_));
+ saved_file_access_.m_FileLen = m_String.size();
+ saved_file_access_.m_GetBlock = GetBlockFromString;
+ saved_file_access_.m_Param = &m_String;
- ASSERT_TRUE(OpenDocumentHelper(password, false, &file_avail, &hints,
- &file_access, &m_SavedDocument, &m_SavedAvail,
+ saved_fake_file_access_ =
+ pdfium::MakeUnique<FakeFileAccess>(&saved_file_access_);
+
+ ASSERT_TRUE(OpenDocumentHelper(password, false, saved_fake_file_access_.get(),
+ &m_SavedDocument, &m_SavedAvail,
&m_SavedForm));
EXPECT_EQ(1, FPDF_GetPageCount(m_SavedDocument));
m_SavedPage = FPDF_LoadPage(m_SavedDocument, 0);
@@ -346,6 +348,11 @@
CloseSaved();
}
+void EmbedderTest::SetWholeFileAvailable() {
+ ASSERT(fake_file_access_);
+ fake_file_access_->SetWholeFileAvailable();
+}
+
FPDF_PAGE EmbedderTest::Delegate::GetPage(FPDF_FORMFILLINFO* info,
FPDF_DOCUMENT document,
int page_index) {
diff --git a/testing/embedder_test.h b/testing/embedder_test.h
index 878e50b..be89c2a 100644
--- a/testing/embedder_test.h
+++ b/testing/embedder_test.h
@@ -14,6 +14,7 @@
#include "public/fpdf_formfill.h"
#include "public/fpdf_save.h"
#include "public/fpdfview.h"
+#include "testing/fake_file_access.h"
#include "testing/gtest/include/gtest/gtest.h"
#include "testing/test_support.h"
@@ -116,9 +117,7 @@
protected:
bool OpenDocumentHelper(const char* password,
bool must_linearize,
- FX_FILEAVAIL* file_avail,
- FX_DOWNLOADHINTS* hints,
- FPDF_FILEACCESS* file_access,
+ FakeFileAccess* network_simulator,
FPDF_DOCUMENT* document,
FPDF_AVAIL* avail,
FPDF_FORMHANDLE* form_handle);
@@ -151,14 +150,14 @@
void CloseSaved();
void TestAndCloseSaved(int width, int height, const char* md5);
+ void SetWholeFileAvailable();
+
Delegate* delegate_;
std::unique_ptr<Delegate> default_delegate_;
FPDF_DOCUMENT document_;
FPDF_FORMHANDLE form_handle_;
FPDF_AVAIL avail_;
- FX_DOWNLOADHINTS hints_;
- FPDF_FILEACCESS file_access_;
- FX_FILEAVAIL file_avail_;
+ FPDF_FILEACCESS file_access_; // must outlive avail_.
#ifdef PDF_ENABLE_V8
v8::Platform* platform_;
#endif // PDF_ENABLE_V8
@@ -172,6 +171,10 @@
FPDF_PAGE m_SavedPage;
FPDF_FORMHANDLE m_SavedForm;
FPDF_AVAIL m_SavedAvail;
+ FPDF_FILEACCESS saved_file_access_; // must outlive m_SavedAvail.
+ std::unique_ptr<FakeFileAccess> fake_file_access_; // must outlive avail_.
+ std::unique_ptr<FakeFileAccess>
+ saved_fake_file_access_; // must outlive m_SavedAvail.
private:
static void UnsupportedHandlerTrampoline(UNSUPPORT_INFO*, int type);
diff --git a/testing/fake_file_access.cpp b/testing/fake_file_access.cpp
new file mode 100644
index 0000000..c69f278
--- /dev/null
+++ b/testing/fake_file_access.cpp
@@ -0,0 +1,115 @@
+// Copyright 2017 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.
+
+#include "testing/fake_file_access.h"
+
+#include <algorithm>
+#include <set>
+#include <utility>
+#include <vector>
+
+#include "core/fxcrt/fx_system.h"
+#include "third_party/base/ptr_util.h"
+
+namespace {
+
+class FileAccessWrapper : public FPDF_FILEACCESS {
+ public:
+ explicit FileAccessWrapper(FakeFileAccess* simulator)
+ : simulator_(simulator) {
+ m_FileLen = simulator_->GetFileSize();
+ m_GetBlock = &GetBlockImpl;
+ m_Param = this;
+ }
+
+ static int GetBlockImpl(void* param,
+ unsigned long position,
+ unsigned char* pBuf,
+ unsigned long size) {
+ return static_cast<FileAccessWrapper*>(param)->simulator_->GetBlock(
+ position, pBuf, size);
+ }
+
+ private:
+ fxcrt::UnownedPtr<FakeFileAccess> simulator_;
+};
+
+class FileAvailImpl : public FX_FILEAVAIL {
+ public:
+ explicit FileAvailImpl(FakeFileAccess* simulator) : simulator_(simulator) {
+ version = 1;
+ IsDataAvail = &IsDataAvailImpl;
+ }
+
+ static FPDF_BOOL IsDataAvailImpl(FX_FILEAVAIL* pThis,
+ size_t offset,
+ size_t size) {
+ return static_cast<FileAvailImpl*>(pThis)->simulator_->IsDataAvail(offset,
+ size);
+ }
+
+ private:
+ fxcrt::UnownedPtr<FakeFileAccess> simulator_;
+};
+
+class DownloadHintsImpl : public FX_DOWNLOADHINTS {
+ public:
+ explicit DownloadHintsImpl(FakeFileAccess* simulator)
+ : simulator_(simulator) {
+ version = 1;
+ AddSegment = &AddSegmentImpl;
+ }
+
+ static void AddSegmentImpl(FX_DOWNLOADHINTS* pThis,
+ size_t offset,
+ size_t size) {
+ return static_cast<DownloadHintsImpl*>(pThis)->simulator_->AddSegment(
+ offset, size);
+ }
+
+ private:
+ fxcrt::UnownedPtr<FakeFileAccess> simulator_;
+};
+
+} // namespace
+
+FakeFileAccess::FakeFileAccess(FPDF_FILEACCESS* file_access)
+ : file_access_(file_access),
+ file_access_wrapper_(pdfium::MakeUnique<FileAccessWrapper>(this)),
+ file_avail_(pdfium::MakeUnique<FileAvailImpl>(this)),
+ download_hints_(pdfium::MakeUnique<DownloadHintsImpl>(this)) {
+ ASSERT(file_access_);
+}
+
+FakeFileAccess::~FakeFileAccess() {}
+
+FPDF_BOOL FakeFileAccess::IsDataAvail(size_t offset, size_t size) const {
+ return available_data_.Contains(RangeSet::Range(offset, offset + size));
+}
+
+void FakeFileAccess::AddSegment(size_t offset, size_t size) {
+ requested_data_.Union(RangeSet::Range(offset, offset + size));
+}
+
+unsigned long FakeFileAccess::GetFileSize() {
+ return file_access_->m_FileLen;
+}
+
+int FakeFileAccess::GetBlock(unsigned long position,
+ unsigned char* pBuf,
+ unsigned long size) {
+ if (!IsDataAvail(static_cast<size_t>(position), static_cast<size_t>(size)))
+ return false;
+ return file_access_->m_GetBlock(file_access_->m_Param, position, pBuf, size);
+}
+
+void FakeFileAccess::SetRequestedDataAvailable() {
+ available_data_.Union(requested_data_);
+ requested_data_.Clear();
+}
+
+void FakeFileAccess::SetWholeFileAvailable() {
+ available_data_.Union(RangeSet::Range(0, static_cast<size_t>(GetFileSize())));
+ requested_data_.Clear();
+}
diff --git a/testing/fake_file_access.h b/testing/fake_file_access.h
new file mode 100644
index 0000000..1328b16
--- /dev/null
+++ b/testing/fake_file_access.h
@@ -0,0 +1,42 @@
+// Copyright 2017 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.
+
+#ifndef TESTING_FAKE_FILE_ACCESS_H_
+#define TESTING_FAKE_FILE_ACCESS_H_
+
+#include <memory>
+
+#include "core/fxcrt/unowned_ptr.h"
+#include "public/fpdf_dataavail.h"
+#include "public/fpdfview.h"
+#include "testing/range_set.h"
+
+class FakeFileAccess {
+ public:
+ explicit FakeFileAccess(FPDF_FILEACCESS* file_access);
+ ~FakeFileAccess();
+
+ FPDF_FILEACCESS* GetFileAccess() const { return file_access_wrapper_.get(); }
+ FX_FILEAVAIL* GetFileAvail() const { return file_avail_.get(); }
+ FX_DOWNLOADHINTS* GetDownloadHints() const { return download_hints_.get(); }
+
+ FPDF_BOOL IsDataAvail(size_t offset, size_t size) const;
+ void AddSegment(size_t offset, size_t size);
+
+ unsigned long GetFileSize();
+
+ int GetBlock(unsigned long position, unsigned char* pBuf, unsigned long size);
+ void SetRequestedDataAvailable();
+ void SetWholeFileAvailable();
+
+ private:
+ fxcrt::UnownedPtr<FPDF_FILEACCESS> file_access_;
+ std::unique_ptr<FPDF_FILEACCESS> file_access_wrapper_;
+ std::unique_ptr<FX_FILEAVAIL> file_avail_;
+ std::unique_ptr<FX_DOWNLOADHINTS> download_hints_;
+ RangeSet available_data_;
+ RangeSet requested_data_;
+};
+
+#endif // TESTING_FAKE_FILE_ACCESS_H_
diff --git a/testing/range_set.cpp b/testing/range_set.cpp
new file mode 100644
index 0000000..2fc540f
--- /dev/null
+++ b/testing/range_set.cpp
@@ -0,0 +1,74 @@
+// Copyright 2017 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.
+
+#include "testing/range_set.h"
+
+#include <algorithm>
+
+#include "core/fxcrt/fx_system.h"
+
+RangeSet::RangeSet() {}
+RangeSet::~RangeSet() {}
+
+bool RangeSet::Contains(const Range& range) const {
+ if (IsEmptyRange(range))
+ return false;
+
+ const Range fixed_range = FixDirection(range);
+ auto it = ranges().upper_bound(fixed_range);
+
+ if (it == ranges().begin())
+ return false; // No ranges includes range.first.
+
+ --it; // Now it starts equal or before range.first.
+ return it->second >= fixed_range.second;
+}
+
+void RangeSet::Union(const Range& range) {
+ if (IsEmptyRange(range))
+ return;
+
+ Range fixed_range = FixDirection(range);
+ if (IsEmpty()) {
+ ranges_.insert(fixed_range);
+ return;
+ }
+
+ auto start = ranges_.upper_bound(fixed_range);
+ if (start != ranges_.begin())
+ --start; // start now points to the key equal or lower than offset.
+
+ if (start->second < fixed_range.first)
+ ++start; // start element is entirely before current range, skip it.
+
+ auto end = ranges_.upper_bound(Range(fixed_range.second, fixed_range.second));
+
+ if (start == end) { // No ranges to merge.
+ ranges_.insert(fixed_range);
+ return;
+ }
+
+ --end;
+
+ const int new_start = std::min<size_t>(start->first, fixed_range.first);
+ const int new_end = std::max(end->second, fixed_range.second);
+
+ ranges_.erase(start, ++end);
+ ranges_.insert(Range(new_start, new_end));
+}
+
+void RangeSet::Union(const RangeSet& range_set) {
+ ASSERT(&range_set != this);
+ for (const auto& it : range_set.ranges())
+ Union(it);
+}
+
+RangeSet::Range RangeSet::FixDirection(const Range& range) const {
+ return range.first <= range.second ? range
+ : Range(range.second + 1, range.first + 1);
+}
+
+bool RangeSet::IsEmptyRange(const Range& range) const {
+ return range.first == range.second;
+}
diff --git a/testing/range_set.h b/testing/range_set.h
new file mode 100644
index 0000000..87cbee9
--- /dev/null
+++ b/testing/range_set.h
@@ -0,0 +1,45 @@
+// Copyright 2017 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.
+
+#ifndef TESTING_RANGE_SET_H_
+#define TESTING_RANGE_SET_H_
+
+#include <set>
+#include <utility>
+
+class RangeSet {
+ public:
+ using Range = std::pair<size_t, size_t>;
+
+ RangeSet();
+ ~RangeSet();
+
+ bool Contains(const Range& range) const;
+
+ void Union(const Range& range);
+
+ void Union(const RangeSet& range_set);
+
+ bool IsEmpty() const { return ranges().empty(); }
+
+ void Clear() { ranges_.clear(); }
+
+ struct range_compare {
+ bool operator()(const Range& lval, const Range& rval) const {
+ return lval.first < rval.first;
+ }
+ };
+
+ using RangesContainer = std::set<Range, range_compare>;
+ const RangesContainer& ranges() const { return ranges_; }
+
+ private:
+ Range FixDirection(const Range& range) const;
+
+ bool IsEmptyRange(const Range& range) const;
+
+ RangesContainer ranges_;
+};
+
+#endif // TESTING_RANGE_SET_H_
