X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2Ftest%2FRangeTest.cpp;h=294659c90d621ad7e5775cf5f459164b1e55aff8;hp=1c2b1f369cde9e074cf7da29518f493e20353b49;hb=8cb615a27594078056b2e4ec2350660e594f5a89;hpb=1408e9d51430bb51b0a07a4bebb43325c2190f21 diff --git a/folly/test/RangeTest.cpp b/folly/test/RangeTest.cpp index 1c2b1f36..294659c9 100644 --- a/folly/test/RangeTest.cpp +++ b/folly/test/RangeTest.cpp @@ -1,5 +1,5 @@ /* - * Copyright 2013 Facebook, Inc. + * Copyright 2016 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -17,29 +17,28 @@ // @author Kristina Holst (kholst@fb.com) // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com) -#include "folly/Range.h" +#include +#include +#include + +#include +#include #include -#include +#include #include -#include +#include +#include #include +#include #include -namespace folly { namespace detail { - -// declaration of functions in Range.cpp -size_t qfind_first_byte_of_memchr(const StringPiece& haystack, - const StringPiece& needles); - -size_t qfind_first_byte_of_byteset(const StringPiece& haystack, - const StringPiece& needles); - -}} // namespaces - using namespace folly; +using namespace folly::detail; using namespace std; +static_assert(std::is_literal_type::value, ""); + BOOST_CONCEPT_ASSERT((boost::RandomAccessRangeConcept)); TEST(StringPiece, All) { @@ -113,6 +112,7 @@ TEST(StringPiece, All) { EXPECT_EQ(s.find('y'), StringPiece::npos); EXPECT_EQ(s.find('y', 1), StringPiece::npos); EXPECT_EQ(s.find('o', 4), StringPiece::npos); // starting position too far + EXPECT_TRUE(s.contains('z')); // starting pos that is obviously past the end -- This works for std::string EXPECT_EQ(s.toString().find('y', 55), StringPiece::npos); EXPECT_EQ(s.find('z', s.size()), StringPiece::npos); @@ -120,6 +120,7 @@ TEST(StringPiece, All) { // null char EXPECT_EQ(s.find('\0'), std::string().find('\0')); EXPECT_EQ(s.find('\0'), StringPiece::npos); + EXPECT_FALSE(s.contains('\0')); // single char rfinds EXPECT_EQ(s.rfind('b'), 6); @@ -136,8 +137,10 @@ TEST(StringPiece, All) { EXPECT_EQ(s.find_first_of("bar"), 3); EXPECT_EQ(s.find_first_of("ba", 3), 3); EXPECT_EQ(s.find_first_of("ba", 4), 4); + EXPECT_TRUE(s.contains("bar")); EXPECT_EQ(s.find_first_of("xyxy"), StringPiece::npos); EXPECT_EQ(s.find_first_of("xyxy", 1), StringPiece::npos); + EXPECT_FALSE(s.contains("xyxy")); // starting position too far EXPECT_EQ(s.find_first_of("foo", 4), StringPiece::npos); // starting pos that is obviously past the end -- This works for std::string @@ -290,6 +293,570 @@ TEST(StringPiece, InvalidRange) { EXPECT_THROW(a.subpiece(6), std::out_of_range); } +constexpr char helloArray[] = "hello"; + +TEST(StringPiece, Constexpr) { + constexpr StringPiece hello1("hello"); + EXPECT_EQ("hello", hello1); + static_assert(hello1.size() == 5, "hello size should be 5 at compile time"); + + constexpr StringPiece hello2(helloArray); + EXPECT_EQ("hello", hello2); + static_assert(hello2.size() == 5, "hello size should be 5 at compile time"); +} + +TEST(StringPiece, Prefix) { + StringPiece a("hello"); + EXPECT_TRUE(a.startsWith("")); + EXPECT_TRUE(a.startsWith("h")); + EXPECT_TRUE(a.startsWith('h')); + EXPECT_TRUE(a.startsWith("hello")); + EXPECT_FALSE(a.startsWith("hellox")); + EXPECT_FALSE(a.startsWith('x')); + EXPECT_FALSE(a.startsWith("x")); + + { + auto b = a; + EXPECT_TRUE(b.removePrefix("")); + EXPECT_EQ("hello", b); + } + { + auto b = a; + EXPECT_TRUE(b.removePrefix("h")); + EXPECT_EQ("ello", b); + } + { + auto b = a; + EXPECT_TRUE(b.removePrefix('h')); + EXPECT_EQ("ello", b); + } + { + auto b = a; + EXPECT_TRUE(b.removePrefix("hello")); + EXPECT_EQ("", b); + } + { + auto b = a; + EXPECT_FALSE(b.removePrefix("hellox")); + EXPECT_EQ("hello", b); + } + { + auto b = a; + EXPECT_FALSE(b.removePrefix("x")); + EXPECT_EQ("hello", b); + } + { + auto b = a; + EXPECT_FALSE(b.removePrefix('x')); + EXPECT_EQ("hello", b); + } +} + +TEST(StringPiece, Suffix) { + StringPiece a("hello"); + EXPECT_TRUE(a.endsWith("")); + EXPECT_TRUE(a.endsWith("o")); + EXPECT_TRUE(a.endsWith('o')); + EXPECT_TRUE(a.endsWith("hello")); + EXPECT_FALSE(a.endsWith("xhello")); + EXPECT_FALSE(a.endsWith("x")); + EXPECT_FALSE(a.endsWith('x')); + + { + auto b = a; + EXPECT_TRUE(b.removeSuffix("")); + EXPECT_EQ("hello", b); + } + { + auto b = a; + EXPECT_TRUE(b.removeSuffix("o")); + EXPECT_EQ("hell", b); + } + { + auto b = a; + EXPECT_TRUE(b.removeSuffix('o')); + EXPECT_EQ("hell", b); + } + { + auto b = a; + EXPECT_TRUE(b.removeSuffix("hello")); + EXPECT_EQ("", b); + } + { + auto b = a; + EXPECT_FALSE(b.removeSuffix("xhello")); + EXPECT_EQ("hello", b); + } + { + auto b = a; + EXPECT_FALSE(b.removeSuffix("x")); + EXPECT_EQ("hello", b); + } + { + auto b = a; + EXPECT_FALSE(b.removeSuffix('x')); + EXPECT_EQ("hello", b); + } +} + +TEST(StringPiece, PrefixEmpty) { + StringPiece a; + EXPECT_TRUE(a.startsWith("")); + EXPECT_FALSE(a.startsWith("a")); + EXPECT_FALSE(a.startsWith('a')); + EXPECT_TRUE(a.removePrefix("")); + EXPECT_EQ("", a); + EXPECT_FALSE(a.removePrefix("a")); + EXPECT_EQ("", a); + EXPECT_FALSE(a.removePrefix('a')); + EXPECT_EQ("", a); +} + +TEST(StringPiece, SuffixEmpty) { + StringPiece a; + EXPECT_TRUE(a.endsWith("")); + EXPECT_FALSE(a.endsWith("a")); + EXPECT_FALSE(a.endsWith('a')); + EXPECT_TRUE(a.removeSuffix("")); + EXPECT_EQ("", a); + EXPECT_FALSE(a.removeSuffix("a")); + EXPECT_EQ("", a); + EXPECT_FALSE(a.removeSuffix('a')); + EXPECT_EQ("", a); +} + +TEST(StringPiece, erase) { + StringPiece a("hello"); + auto b = a.begin(); + auto e = b + 1; + a.erase(b, e); + EXPECT_EQ("ello", a); + + e = a.end(); + b = e - 1; + a.erase(b, e); + EXPECT_EQ("ell", a); + + b = a.end() - 1; + e = a.end() - 1; + EXPECT_THROW(a.erase(b, e), std::out_of_range); + + b = a.begin(); + e = a.end(); + a.erase(b, e); + EXPECT_EQ("", a); + + a = "hello"; + b = a.begin(); + e = b + 2; + a.erase(b, e); + EXPECT_EQ("llo", a); + + b = a.end() - 2; + e = a.end(); + a.erase(b, e); + EXPECT_EQ("l", a); + + a = " hello "; + boost::algorithm::trim(a); + EXPECT_EQ(a, "hello"); +} + +TEST(StringPiece, split_step_char_delimiter) { + // 0 1 2 + // 012345678901234567890123456 + auto const s = "this is just a test string"; + auto const e = std::next(s, std::strlen(s)); + EXPECT_EQ('\0', *e); + + folly::StringPiece p(s); + EXPECT_EQ(s, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(s, p); + + auto x = p.split_step(' '); + EXPECT_EQ(std::next(s, 5), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("this", x); + + x = p.split_step(' '); + EXPECT_EQ(std::next(s, 8), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("is", x); + + x = p.split_step('u'); + EXPECT_EQ(std::next(s, 10), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("j", x); + + x = p.split_step(' '); + EXPECT_EQ(std::next(s, 13), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("st", x); + + x = p.split_step(' '); + EXPECT_EQ(std::next(s, 14), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + + x = p.split_step(' '); + EXPECT_EQ(std::next(s, 16), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("a", x); + + x = p.split_step(' '); + EXPECT_EQ(std::next(s, 21), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("test", x); + + x = p.split_step(' '); + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("string", x); + + x = p.split_step(' '); + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); +} + +TEST(StringPiece, split_step_range_delimiter) { + // 0 1 2 3 + // 0123456789012345678901234567890123 + auto const s = "this is just a test string"; + auto const e = std::next(s, std::strlen(s)); + EXPECT_EQ('\0', *e); + + folly::StringPiece p(s); + EXPECT_EQ(s, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(s, p); + + auto x = p.split_step(" "); + EXPECT_EQ(std::next(s, 6), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("this", x); + + x = p.split_step(" "); + EXPECT_EQ(std::next(s, 10), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("is", x); + + x = p.split_step("u"); + EXPECT_EQ(std::next(s, 12), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("j", x); + + x = p.split_step(" "); + EXPECT_EQ(std::next(s, 16), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("st", x); + + x = p.split_step(" "); + EXPECT_EQ(std::next(s, 18), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + + x = p.split_step(" "); + EXPECT_EQ(std::next(s, 21), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("a", x); + + x = p.split_step(" "); + EXPECT_EQ(std::next(s, 28), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(" test", x); + + x = p.split_step(" "); + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("string", x); + + x = p.split_step(" "); + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + + x = p.split_step(" "); + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); +} + +void split_step_with_process_noop(folly::StringPiece) {} + +TEST(StringPiece, split_step_with_process_char_delimiter) { + // 0 1 2 + // 012345678901234567890123456 + auto const s = "this is just a test string"; + auto const e = std::next(s, std::strlen(s)); + EXPECT_EQ('\0', *e); + + folly::StringPiece p(s); + EXPECT_EQ(s, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(s, p); + + EXPECT_EQ(1, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 5), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("this", x); + return 1; + }))); + + EXPECT_EQ(2, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 8), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("is", x); + return 2; + }))); + + EXPECT_EQ(3, (p.split_step('u', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 10), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("j", x); + return 3; + }))); + + EXPECT_EQ(4, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 13), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("st", x); + return 4; + }))); + + EXPECT_EQ(5, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 14), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + return 5; + }))); + + EXPECT_EQ(6, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 16), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("a", x); + return 6; + }))); + + EXPECT_EQ(7, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 21), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("test", x); + return 7; + }))); + + EXPECT_EQ(8, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("string", x); + return 8; + }))); + + EXPECT_EQ(9, (p.split_step(' ', [&](folly::StringPiece x) { + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + return 9; + }))); + + EXPECT_TRUE((std::is_same< + void, + decltype(p.split_step(' ', split_step_with_process_noop)) + >::value)); + + EXPECT_NO_THROW(p.split_step(' ', split_step_with_process_noop)); +} + +TEST(StringPiece, split_step_with_process_range_delimiter) { + // 0 1 2 3 + // 0123456789012345678901234567890123 + auto const s = "this is just a test string"; + auto const e = std::next(s, std::strlen(s)); + EXPECT_EQ('\0', *e); + + folly::StringPiece p(s); + EXPECT_EQ(s, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(s, p); + + EXPECT_EQ(1, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 6), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("this", x); + return 1; + }))); + + EXPECT_EQ(2, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 10), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("is", x); + return 2; + }))); + + EXPECT_EQ(3, (p.split_step("u", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 12), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("j", x); + return 3; + }))); + + EXPECT_EQ(4, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 16), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("st", x); + return 4; + }))); + + EXPECT_EQ(5, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 18), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + return 5; + }))); + + EXPECT_EQ(6, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 21), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("a", x); + return 6; + }))); + + EXPECT_EQ(7, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(std::next(s, 28), p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(" test", x); + return 7; + }))); + + EXPECT_EQ(8, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("string", x); + return 8; + }))); + + EXPECT_EQ(9, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + return 9; + }))); + + EXPECT_EQ(10, (p.split_step(" ", [&](folly::StringPiece x) { + EXPECT_EQ(e, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ("", x); + return 10; + }))); + + EXPECT_TRUE((std::is_same< + void, + decltype(p.split_step(' ', split_step_with_process_noop)) + >::value)); + + EXPECT_NO_THROW(p.split_step(' ', split_step_with_process_noop)); +} + +TEST(StringPiece, split_step_with_process_char_delimiter_additional_args) { + // 0 1 2 + // 012345678901234567890123456 + auto const s = "this is just a test string"; + auto const e = std::next(s, std::strlen(s)); + auto const delimiter = ' '; + EXPECT_EQ('\0', *e); + + folly::StringPiece p(s); + EXPECT_EQ(s, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(s, p); + + auto const functor = []( + folly::StringPiece s, + folly::StringPiece expected + ) { + EXPECT_EQ(expected, s); + return expected; + }; + + auto const checker = [&](folly::StringPiece expected) { + EXPECT_EQ(expected, p.split_step(delimiter, functor, expected)); + }; + + checker("this"); + checker("is"); + checker("just"); + checker(""); + checker("a"); + checker("test"); + checker("string"); + checker(""); + checker(""); + + EXPECT_TRUE(p.empty()); +} + +TEST(StringPiece, split_step_with_process_range_delimiter_additional_args) { + // 0 1 2 3 + // 0123456789012345678901234567890123 + auto const s = "this is just a test string"; + auto const e = std::next(s, std::strlen(s)); + auto const delimiter = " "; + EXPECT_EQ('\0', *e); + + folly::StringPiece p(s); + EXPECT_EQ(s, p.begin()); + EXPECT_EQ(e, p.end()); + EXPECT_EQ(s, p); + + auto const functor = []( + folly::StringPiece s, + folly::StringPiece expected + ) { + EXPECT_EQ(expected, s); + return expected; + }; + + auto const checker = [&](folly::StringPiece expected) { + EXPECT_EQ(expected, p.split_step(delimiter, functor, expected)); + }; + + checker("this"); + checker("is"); + checker("just"); + checker(""); + checker("a"); + checker(" test"); + checker("string"); + checker(""); + checker(""); + + EXPECT_TRUE(p.empty()); +} + +TEST(StringPiece, NoInvalidImplicitConversions) { + struct IsString { + bool operator()(folly::Range) { return false; } + bool operator()(folly::StringPiece) { return true; } + }; + + std::string s = "hello"; + EXPECT_TRUE(IsString()(s)); +} + +TEST(qfind, UInt32_Ranges) { + vector a({1, 2, 3, 260, 5}); + vector b({2, 3, 4}); + + auto a_range = folly::Range(&a[0], a.size()); + auto b_range = folly::Range(&b[0], b.size()); + + EXPECT_EQ(qfind(a_range, b_range), string::npos); + + a[3] = 4; + EXPECT_EQ(qfind(a_range, b_range), 1); +} + template class NeedleFinderTest : public ::testing::Test { public: @@ -312,19 +879,14 @@ struct NoSseNeedleFinder { } }; -struct MemchrNeedleFinder { - static size_t find_first_byte_of(StringPiece haystack, StringPiece needles) { - return detail::qfind_first_byte_of_memchr(haystack, needles); - } -}; - struct ByteSetNeedleFinder { static size_t find_first_byte_of(StringPiece haystack, StringPiece needles) { return detail::qfind_first_byte_of_byteset(haystack, needles); } }; -typedef ::testing::Types NeedleFinders; TYPED_TEST_CASE(NeedleFinderTest, NeedleFinders); @@ -367,9 +929,9 @@ TYPED_TEST(NeedleFinderTest, Empty) { TYPED_TEST(NeedleFinderTest, Unaligned) { // works correctly even if input buffers are not 16-byte aligned string s = "0123456789ABCDEFGH"; - for (int i = 0; i < s.size(); ++i) { + for (size_t i = 0; i < s.size(); ++i) { StringPiece a(s.c_str() + i); - for (int j = 0; j < s.size(); ++j) { + for (size_t j = 0; j < s.size(); ++j) { StringPiece b(s.c_str() + j); EXPECT_EQ((i > j) ? 0 : j - i, this->find_first_byte_of(a, b)); } @@ -384,23 +946,23 @@ TYPED_TEST(NeedleFinderTest, Needles256) { const auto maxValue = std::numeric_limits::max(); // make the size ~big to avoid any edge-case branches for tiny haystacks const int haystackSize = 50; - for (int i = minValue; i <= maxValue; i++) { // <= + for (size_t i = minValue; i <= maxValue; i++) { // <= needles.push_back(i); } EXPECT_EQ(StringPiece::npos, this->find_first_byte_of("", needles)); - for (int i = minValue; i <= maxValue; i++) { + for (size_t i = minValue; i <= maxValue; i++) { EXPECT_EQ(0, this->find_first_byte_of(string(haystackSize, i), needles)); } needles.append("these are redundant characters"); EXPECT_EQ(StringPiece::npos, this->find_first_byte_of("", needles)); - for (int i = minValue; i <= maxValue; i++) { + for (size_t i = minValue; i <= maxValue; i++) { EXPECT_EQ(0, this->find_first_byte_of(string(haystackSize, i), needles)); } } TYPED_TEST(NeedleFinderTest, Base) { - for (int i = 0; i < 32; ++i) { + for (size_t i = 0; i < 32; ++i) { for (int j = 0; j < 32; ++j) { string s = string(i, 'X') + "abca" + string(i, 'X'); string delims = string(j, 'Y') + "a" + string(j, 'Y'); @@ -418,14 +980,22 @@ const size_t kPageSize = 4096; void createProtectedBuf(StringPiece& contents, char** buf) { ASSERT_LE(contents.size(), kPageSize); const size_t kSuccess = 0; - char* tmp; - if (kSuccess != posix_memalign((void**)buf, kPageSize, 2 * kPageSize)) { + char* pageAlignedBuf = (char*)aligned_malloc(2 * kPageSize, kPageSize); + if (pageAlignedBuf == nullptr) { ASSERT_FALSE(true); } - mprotect(*buf + kPageSize, kPageSize, PROT_NONE); + // Protect the page after the first full page-aligned region of the + // malloc'ed buffer + mprotect(pageAlignedBuf + kPageSize, kPageSize, PROT_NONE); size_t newBegin = kPageSize - contents.size(); - memcpy(*buf + newBegin, contents.data(), contents.size()); - contents.reset(*buf + newBegin, contents.size()); + memcpy(pageAlignedBuf + newBegin, contents.data(), contents.size()); + contents.reset(pageAlignedBuf + newBegin, contents.size()); + *buf = pageAlignedBuf; +} + +void freeProtectedBuf(char* buf) { + mprotect(buf + kPageSize, kPageSize, PROT_READ | PROT_WRITE); + aligned_free(buf); } TYPED_TEST(NeedleFinderTest, NoSegFault) { @@ -459,9 +1029,204 @@ TYPED_TEST(NeedleFinderTest, NoSegFault) { s1.begin(), s1.end()); auto e2 = (f2 == s2.end()) ? StringPiece::npos : f2 - s2.begin(); EXPECT_EQ(r2, e2); - free(buf1); - free(buf2); + freeProtectedBuf(buf1); + freeProtectedBuf(buf2); } } } } + +TEST(NonConstTest, StringPiece) { + std::string hello("hello"); + MutableStringPiece sp(&hello.front(), hello.size()); + sp[0] = 'x'; + EXPECT_EQ("xello", hello); + { + StringPiece s(sp); + EXPECT_EQ("xello", s); + } + { + ByteRange r1(sp); + MutableByteRange r2(sp); + } +} + +// Similar to the begin() template functions, but instread of returing +// an iterator, return a pointer to data. +template +typename Container::value_type* dataPtr(Container& cont) { + // NOTE: &cont[0] is undefined if cont is empty (it creates a + // reference to nullptr - which is not dereferenced, but still UBSAN). + return cont.data(); +} +template +constexpr T* dataPtr(T (&arr)[N]) noexcept { + return &arr[0]; +} + +template +void testRangeFunc(C&& x, size_t n) { + const auto& cx = x; + // type, conversion checks + Range r1 = range(std::forward(x)); + Range r2 = range(std::forward(x)); + Range r3 = range(cx); + Range r5 = range(std::move(cx)); + EXPECT_EQ(r1.begin(), dataPtr(x)); + EXPECT_EQ(r1.end(), dataPtr(x) + n); + EXPECT_EQ(n, r1.size()); + EXPECT_EQ(n, r2.size()); + EXPECT_EQ(n, r3.size()); + EXPECT_EQ(n, r5.size()); +} + +TEST(RangeFunc, Vector) { + std::vector x; + testRangeFunc(x, 0); + x.push_back(2); + testRangeFunc(x, 1); + testRangeFunc(std::vector{1, 2}, 2); +} + +TEST(RangeFunc, Array) { + std::array x; + testRangeFunc(x, 3); +} + +TEST(RangeFunc, CArray) { + int x[] {1, 2, 3, 4}; + testRangeFunc(x, 4); +} + +std::string get_rand_str(size_t size, + std::uniform_int_distribution<>& dist, + std::mt19937& gen) { + std::string ret(size, '\0'); + for (size_t i = 0; i < size; ++i) { + ret[i] = static_cast(dist(gen)); + } + + return ret; +} + +namespace folly { +bool operator==(MutableStringPiece mp, StringPiece sp) { + return mp.compare(sp) == 0; +} + +bool operator==(StringPiece sp, MutableStringPiece mp) { + return mp.compare(sp) == 0; +} +} + +TEST(ReplaceAt, exhaustiveTest) { + char input[] = "this is nice and long input"; + auto msp = MutableStringPiece(input); + auto str = std::string(input); + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<> dist('a', 'z'); + + for (int i=0; i < 100; ++i) { + for (size_t j = 1; j <= msp.size(); ++j) { + auto replacement = get_rand_str(j, dist, gen); + for (size_t pos = 0; pos < msp.size() - j; ++pos) { + msp.replaceAt(pos, replacement); + str.replace(pos, replacement.size(), replacement); + EXPECT_EQ(msp.compare(str), 0); + } + } + } + + // too far + EXPECT_EQ(msp.replaceAt(msp.size() - 2, StringPiece("meh")), false); +} + +TEST(ReplaceAll, basicTest) { + char input[] = "this is nice and long input"; + auto orig = std::string(input); + auto msp = MutableStringPiece(input); + + EXPECT_EQ(msp.replaceAll("is", "si"), 2); + EXPECT_EQ("thsi si nice and long input", msp); + EXPECT_EQ(msp.replaceAll("si", "is"), 2); + EXPECT_EQ(msp, orig); + + EXPECT_EQ(msp.replaceAll("abcd", "efgh"), 0); // nothing to replace + EXPECT_EQ(msp, orig); + + // at the very beginning + EXPECT_EQ(msp.replaceAll("this", "siht"), 1); + EXPECT_EQ("siht is nice and long input", msp); + EXPECT_EQ(msp.replaceAll("siht", "this"), 1); + EXPECT_EQ(msp, orig); + + // at the very end + EXPECT_EQ(msp.replaceAll("input", "soput"), 1); + EXPECT_EQ("this is nice and long soput", msp); + EXPECT_EQ(msp.replaceAll("soput", "input"), 1); + EXPECT_EQ(msp, orig); + + // all spaces + EXPECT_EQ(msp.replaceAll(" ", "@"), 5); + EXPECT_EQ("this@is@nice@and@long@input", msp); + EXPECT_EQ(msp.replaceAll("@", " "), 5); + EXPECT_EQ(msp, orig); +} + +TEST(ReplaceAll, randomTest) { + char input[] = "abcdefghijklmnoprstuwqz"; // no pattern repeata inside + auto orig = std::string(input); + auto msp = MutableStringPiece(input); + + std::random_device rd; + std::mt19937 gen(rd()); + std::uniform_int_distribution<> dist('A', 'Z'); + + for (int i=0; i < 100; ++i) { + for (size_t j = 1; j <= orig.size(); ++j) { + auto replacement = get_rand_str(j, dist, gen); + for (size_t pos = 0; pos < msp.size() - j; ++pos) { + auto piece = orig.substr(pos, j); + EXPECT_EQ(msp.replaceAll(piece, replacement), 1); + EXPECT_EQ(msp.find(replacement), pos); + EXPECT_EQ(msp.replaceAll(replacement, piece), 1); + EXPECT_EQ(msp, orig); + } + } + } +} + +TEST(ReplaceAll, BadArg) { + int count = 0; + auto fst = "longer"; + auto snd = "small"; + char input[] = "meh meh meh"; + auto all = MutableStringPiece(input); + + try { + all.replaceAll(fst, snd); + } catch (std::invalid_argument&) { + ++count; + } + + try { + all.replaceAll(snd, fst); + } catch (std::invalid_argument&) { + ++count; + } + + EXPECT_EQ(count, 2); +} + +TEST(Range, Constructors) { + vector c = {1, 2, 3}; + typedef Range::iterator> RangeType; + typedef Range::const_iterator> ConstRangeType; + RangeType cr(c.begin(), c.end()); + auto subpiece1 = ConstRangeType(cr, 1, 5); + auto subpiece2 = ConstRangeType(cr, 1); + EXPECT_EQ(subpiece1.size(), 2); + EXPECT_EQ(subpiece1.begin(), subpiece2.begin()); + EXPECT_EQ(subpiece1.end(), subpiece2.end()); +}