From 0e60b9ef2b79de52ef62101abae2af7292e879b7 Mon Sep 17 00:00:00 2001 From: Artem Strygin Date: Thu, 28 Sep 2017 18:46:03 +0300 Subject: 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 Reviewed-by: dsinclair --- BUILD.gn | 4 + .../parser/cpdf_security_handler_embeddertest.cpp | 1 + fpdfsdk/fpdf_dataavail_embeddertest.cpp | 72 +++++-------- fpdfsdk/fpdfdoc_embeddertest.cpp | 4 + fpdfsdk/fpdfview_embeddertest.cpp | 20 +++- testing/embedder_test.cpp | 97 +++++++++-------- testing/embedder_test.h | 15 +-- testing/fake_file_access.cpp | 115 +++++++++++++++++++++ testing/fake_file_access.h | 42 ++++++++ testing/range_set.cpp | 74 +++++++++++++ testing/range_set.h | 45 ++++++++ 11 files changed, 390 insertions(+), 99 deletions(-) create mode 100644 testing/fake_file_access.cpp create mode 100644 testing/fake_file_access.h create mode 100644 testing/range_set.cpp create mode 100644 testing/range_set.h diff --git a/BUILD.gn b/BUILD.gn index 25c805ccb7..5657ac18f7 100644 --- a/BUILD.gn +++ b/BUILD.gn @@ -2029,6 +2029,10 @@ test("pdfium_embeddertests") { "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 49a898f2ba..91346dae2a 100644 --- a/core/fpdfapi/parser/cpdf_security_handler_embeddertest.cpp +++ b/core/fpdfapi/parser/cpdf_security_handler_embeddertest.cpp @@ -62,6 +62,7 @@ TEST_F(CPDFSecurityHandlerEmbeddertest, PasswordAfterGenerateSave) { 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 c40f8579b6..2084153852 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 @@ class TestAsyncLoader : public FX_DOWNLOADHINTS, FX_FILEAVAIL { } 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 @@ class TestAsyncLoader : public FX_DOWNLOADHINTS, FX_FILEAVAIL { 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(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 @@ class TestAsyncLoader : public FX_DOWNLOADHINTS, FX_FILEAVAIL { size_t max_requested_bound_ = 0; bool is_new_data_available_ = true; - using Range = std::pair; - struct range_compare { - bool operator()(const Range& lval, const Range& rval) const { - return lval.first < rval.first; - } - }; - using RangesContainer = std::set; - RangesContainer available_ranges_; + RangeSet available_ranges_; }; } // namespace @@ -182,13 +158,15 @@ class FPDFDataAvailEmbeddertest : public EmbedderTest {}; 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 5db610e030..19147d4bae 100644 --- a/fpdfsdk/fpdfdoc_embeddertest.cpp +++ b/fpdfsdk/fpdfdoc_embeddertest.cpp @@ -248,6 +248,10 @@ TEST_F(FPDFDocEmbeddertest, GetPageLabels) { 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 97ba9d7c4c..699fc8a71b 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 @@ TEST_F(FPDFViewEmbeddertest, Hang_298) { // 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 82ffb3b825..dab06af50d 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 @@ v8::StartupData* g_v8_snapshot = nullptr; #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 @@ EmbedderTest::EmbedderTest() 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 @@ bool EmbedderTest::OpenDocument(const std::string& filename, file_access_.m_FileLen = static_cast(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(&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) { - *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); + while (nRet == PDF_DATA_NOTAVAIL) { + network_simulator->SetRequestedDataAvailable(); + nRet = + FPDFAvail_IsDocAvail(*avail, network_simulator->GetDownloadHints()); + } if (nRet == PDF_DATA_ERROR) return false; - nRet = FPDFAvail_IsFormAvail(*avail, hints); - if (nRet == PDF_FORM_ERROR || nRet == PDF_FORM_NOTAVAIL) + *document = FPDFAvail_GetDocument(*avail, password); + if (!*document) + return false; + + 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 @@ bool EmbedderTest::OpenDocumentHelper(const char* password, } 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 @@ void EmbedderTest::DoOpenActions() { 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 @@ void EmbedderTest::TestSaved(int width, 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; - - ASSERT_TRUE(OpenDocumentHelper(password, false, &file_avail, &hints, - &file_access, &m_SavedDocument, &m_SavedAvail, + 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; + + saved_fake_file_access_ = + pdfium::MakeUnique(&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 @@ void EmbedderTest::TestAndCloseSaved(int width, int height, const char* md5) { 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 878e50bfdd..be89c2a6cd 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 @@ class EmbedderTest : public ::testing::Test, 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 @@ class EmbedderTest : public ::testing::Test, void CloseSaved(); void TestAndCloseSaved(int width, int height, const char* md5); + void SetWholeFileAvailable(); + Delegate* delegate_; std::unique_ptr 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 @@ class EmbedderTest : public ::testing::Test, FPDF_PAGE m_SavedPage; FPDF_FORMHANDLE m_SavedForm; FPDF_AVAIL m_SavedAvail; + FPDF_FILEACCESS saved_file_access_; // must outlive m_SavedAvail. + std::unique_ptr fake_file_access_; // must outlive avail_. + std::unique_ptr + 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 0000000000..c69f278102 --- /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 +#include +#include +#include + +#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(param)->simulator_->GetBlock( + position, pBuf, size); + } + + private: + fxcrt::UnownedPtr 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(pThis)->simulator_->IsDataAvail(offset, + size); + } + + private: + fxcrt::UnownedPtr 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(pThis)->simulator_->AddSegment( + offset, size); + } + + private: + fxcrt::UnownedPtr simulator_; +}; + +} // namespace + +FakeFileAccess::FakeFileAccess(FPDF_FILEACCESS* file_access) + : file_access_(file_access), + file_access_wrapper_(pdfium::MakeUnique(this)), + file_avail_(pdfium::MakeUnique(this)), + download_hints_(pdfium::MakeUnique(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(position), static_cast(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(GetFileSize()))); + requested_data_.Clear(); +} diff --git a/testing/fake_file_access.h b/testing/fake_file_access.h new file mode 100644 index 0000000000..1328b16392 --- /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 + +#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 file_access_; + std::unique_ptr file_access_wrapper_; + std::unique_ptr file_avail_; + std::unique_ptr 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 0000000000..2fc540f17c --- /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 + +#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(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 0000000000..87cbee910b --- /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 +#include + +class RangeSet { + public: + using Range = std::pair; + + 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; + 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_ -- cgit v1.2.3