1/*
2 * Copyright 2011-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17// @author Kristina Holst (kholst@fb.com)
18// @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
19
20#include <folly/Range.h>
21
22#include <array>
23#include <deque>
24#include <iterator>
25#include <limits>
26#include <random>
27#include <string>
28#include <type_traits>
29#include <vector>
30
31#include <boost/algorithm/string/trim.hpp>
32#include <boost/range/concepts.hpp>
33
34#include <folly/Memory.h>
35#include <folly/portability/GMock.h>
36#include <folly/portability/GTest.h>
37#include <folly/portability/SysMman.h>
38
39using namespace folly;
40using namespace folly::detail;
41using namespace std;
42
43static_assert(std::is_literal_type<StringPiece>::value, "");
44
45BOOST_CONCEPT_ASSERT((boost::RandomAccessRangeConcept<StringPiece>));
46
47TEST(StringPiece, All) {
48 const char* foo = "foo";
49 const char* foo2 = "foo";
50 string fooStr(foo);
51 string foo2Str(foo2);
52
53 // we expect the compiler to optimize things so that there's only one copy
54 // of the string literal "foo", even though we've got it in multiple places
55 EXPECT_EQ(foo, foo2); // remember, this uses ==, not strcmp, so it's a ptr
56 // comparison rather than lexical
57
58 // the string object creates copies though, so the c_str of these should be
59 // distinct
60 EXPECT_NE(fooStr.c_str(), foo2Str.c_str());
61
62 // test the basic StringPiece functionality
63 StringPiece s(foo);
64 EXPECT_EQ(s.size(), 3);
65
66 EXPECT_EQ(s.start(), foo); // ptr comparison
67 EXPECT_NE(s.start(), fooStr.c_str()); // ptr comparison
68 EXPECT_NE(s.start(), foo2Str.c_str()); // ptr comparison
69
70 EXPECT_EQ(s.toString(), foo); // lexical comparison
71 EXPECT_EQ(s.toString(), fooStr.c_str()); // lexical comparison
72 EXPECT_EQ(s.toString(), foo2Str.c_str()); // lexical comparison
73
74 EXPECT_EQ(s, foo); // lexical comparison
75 EXPECT_EQ(s, fooStr); // lexical comparison
76 EXPECT_EQ(s, foo2Str); // lexical comparison
77 EXPECT_EQ(foo, s);
78
79 // check using StringPiece to reference substrings
80 const char* foobarbaz = "foobarbaz";
81
82 // the full "foobarbaz"
83 s.reset(foobarbaz, strlen(foobarbaz));
84 EXPECT_EQ(s.size(), 9);
85 EXPECT_EQ(s.start(), foobarbaz);
86 EXPECT_EQ(s, "foobarbaz");
87
88 // only the 'foo'
89 s.assign(foobarbaz, foobarbaz + 3);
90 EXPECT_EQ(s.size(), 3);
91 EXPECT_EQ(s.start(), foobarbaz);
92 EXPECT_EQ(s, "foo");
93
94 // find
95 s.reset(foobarbaz, strlen(foobarbaz));
96 EXPECT_EQ(s.find("bar"), 3);
97 EXPECT_EQ(s.find("ba", 3), 3);
98 EXPECT_EQ(s.find("ba", 4), 6);
99 EXPECT_EQ(s.find("notfound"), StringPiece::npos);
100 EXPECT_EQ(s.find("notfound", 1), StringPiece::npos);
101 EXPECT_EQ(s.find("bar", 4), StringPiece::npos); // starting position too far
102 // starting pos that is obviously past the end -- This works for std::string
103 EXPECT_EQ(s.toString().find("notfound", 55), StringPiece::npos);
104 EXPECT_EQ(s.find("z", s.size()), StringPiece::npos);
105 EXPECT_EQ(s.find("z", 55), StringPiece::npos);
106 // empty needle
107 EXPECT_EQ(s.find(""), std::string().find(""));
108 EXPECT_EQ(s.find(""), 0);
109
110 // single char finds
111 EXPECT_EQ(s.find('b'), 3);
112 EXPECT_EQ(s.find('b', 3), 3);
113 EXPECT_EQ(s.find('b', 4), 6);
114 EXPECT_EQ(s.find('o', 2), 2);
115 EXPECT_EQ(s.find('y'), StringPiece::npos);
116 EXPECT_EQ(s.find('y', 1), StringPiece::npos);
117 EXPECT_EQ(s.find('o', 4), StringPiece::npos); // starting position too far
118 EXPECT_TRUE(s.contains('z'));
119 // starting pos that is obviously past the end -- This works for std::string
120 EXPECT_EQ(s.toString().find('y', 55), StringPiece::npos);
121 EXPECT_EQ(s.find('z', s.size()), StringPiece::npos);
122 EXPECT_EQ(s.find('z', 55), StringPiece::npos);
123 // null char
124 EXPECT_EQ(s.find('\0'), std::string().find('\0'));
125 EXPECT_EQ(s.find('\0'), StringPiece::npos);
126 EXPECT_FALSE(s.contains('\0'));
127
128 // single char rfinds
129 EXPECT_EQ(s.rfind('b'), 6);
130 EXPECT_EQ(s.rfind('y'), StringPiece::npos);
131 EXPECT_EQ(s.str().rfind('y'), StringPiece::npos);
132 EXPECT_EQ(ByteRange(s).rfind('b'), 6);
133 EXPECT_EQ(ByteRange(s).rfind('y'), StringPiece::npos);
134 // null char
135 EXPECT_EQ(s.rfind('\0'), s.str().rfind('\0'));
136 EXPECT_EQ(s.rfind('\0'), StringPiece::npos);
137
138 // find_first_of
139 s.reset(foobarbaz, strlen(foobarbaz));
140 EXPECT_EQ(s.find_first_of("bar"), 3);
141 EXPECT_EQ(s.find_first_of("ba", 3), 3);
142 EXPECT_EQ(s.find_first_of("ba", 4), 4);
143 EXPECT_TRUE(s.contains("bar"));
144 EXPECT_EQ(s.find_first_of("xyxy"), StringPiece::npos);
145 EXPECT_EQ(s.find_first_of("xyxy", 1), StringPiece::npos);
146 EXPECT_FALSE(s.contains("xyxy"));
147 // starting position too far
148 EXPECT_EQ(s.find_first_of("foo", 4), StringPiece::npos);
149 // starting pos that is obviously past the end -- This works for std::string
150 EXPECT_EQ(s.toString().find_first_of("xyxy", 55), StringPiece::npos);
151 EXPECT_EQ(s.find_first_of("z", s.size()), StringPiece::npos);
152 EXPECT_EQ(s.find_first_of("z", 55), StringPiece::npos);
153 // empty needle. Note that this returns npos, while find() returns 0!
154 EXPECT_EQ(s.find_first_of(""), std::string().find_first_of(""));
155 EXPECT_EQ(s.find_first_of(""), StringPiece::npos);
156
157 // single char find_first_ofs
158 EXPECT_EQ(s.find_first_of('b'), 3);
159 EXPECT_EQ(s.find_first_of('b', 3), 3);
160 EXPECT_EQ(s.find_first_of('b', 4), 6);
161 EXPECT_EQ(s.find_first_of('o', 2), 2);
162 EXPECT_EQ(s.find_first_of('y'), StringPiece::npos);
163 EXPECT_EQ(s.find_first_of('y', 1), StringPiece::npos);
164 // starting position too far
165 EXPECT_EQ(s.find_first_of('o', 4), StringPiece::npos);
166 // starting pos that is obviously past the end -- This works for std::string
167 EXPECT_EQ(s.toString().find_first_of('y', 55), StringPiece::npos);
168 EXPECT_EQ(s.find_first_of('z', s.size()), StringPiece::npos);
169 EXPECT_EQ(s.find_first_of('z', 55), StringPiece::npos);
170 // null char
171 EXPECT_EQ(s.find_first_of('\0'), std::string().find_first_of('\0'));
172 EXPECT_EQ(s.find_first_of('\0'), StringPiece::npos);
173
174 // just "barbaz"
175 s.reset(foobarbaz + 3, strlen(foobarbaz + 3));
176 EXPECT_EQ(s.size(), 6);
177 EXPECT_EQ(s.start(), foobarbaz + 3);
178 EXPECT_EQ(s, "barbaz");
179
180 // just "bar"
181 s.reset(foobarbaz + 3, 3);
182 EXPECT_EQ(s.size(), 3);
183 EXPECT_EQ(s, "bar");
184
185 // clear
186 s.clear();
187 EXPECT_EQ(s.toString(), "");
188
189 // test an empty StringPiece
190 StringPiece s2;
191 EXPECT_EQ(s2.size(), 0);
192
193 // Test comparison operators
194 foo = "";
195 EXPECT_LE(s, foo);
196 EXPECT_LE(foo, s);
197 EXPECT_GE(s, foo);
198 EXPECT_GE(foo, s);
199 EXPECT_EQ(s, foo);
200 EXPECT_EQ(foo, s);
201
202 foo = "abc";
203 EXPECT_LE(s, foo);
204 EXPECT_LT(s, foo);
205 EXPECT_GE(foo, s);
206 EXPECT_GT(foo, s);
207 EXPECT_NE(s, foo);
208
209 EXPECT_LE(s, s);
210 EXPECT_LE(s, s);
211 EXPECT_GE(s, s);
212 EXPECT_GE(s, s);
213 EXPECT_EQ(s, s);
214 EXPECT_EQ(s, s);
215
216 s = "abc";
217 s2 = "abc";
218 EXPECT_LE(s, s2);
219 EXPECT_LE(s2, s);
220 EXPECT_GE(s, s2);
221 EXPECT_GE(s2, s);
222 EXPECT_EQ(s, s2);
223 EXPECT_EQ(s2, s);
224}
225
226TEST(StringPiece, CustomAllocator) {
227 using Alloc = AlignedSysAllocator<char>;
228 Alloc const alloc{32};
229 char const* const text = "foo bar baz";
230 std::basic_string<char, std::char_traits<char>, Alloc> str{text, alloc};
231 EXPECT_EQ("foo", StringPiece(str).subpiece(0, 3));
232 EXPECT_EQ("bar", StringPiece(str, 4).subpiece(0, 3));
233 EXPECT_EQ("baz", StringPiece(str, 8, 3));
234 StringPiece piece;
235 piece.reset(str);
236 EXPECT_EQ("foo", piece.subpiece(0, 3));
237}
238
239template <class T>
240void expectLT(const T& a, const T& b) {
241 EXPECT_TRUE(a < b);
242 EXPECT_TRUE(a <= b);
243 EXPECT_FALSE(a == b);
244 EXPECT_FALSE(a >= b);
245 EXPECT_FALSE(a > b);
246
247 EXPECT_FALSE(b < a);
248 EXPECT_FALSE(b <= a);
249 EXPECT_TRUE(b >= a);
250 EXPECT_TRUE(b > a);
251}
252
253template <class T>
254void expectEQ(const T& a, const T& b) {
255 EXPECT_FALSE(a < b);
256 EXPECT_TRUE(a <= b);
257 EXPECT_TRUE(a == b);
258 EXPECT_TRUE(a >= b);
259 EXPECT_FALSE(a > b);
260}
261
262TEST(StringPiece, EightBitComparisons) {
263 char values[] = {'\x00', '\x20', '\x40', '\x7f', '\x80', '\xc0', '\xff'};
264 constexpr size_t count = sizeof(values) / sizeof(values[0]);
265 for (size_t i = 0; i < count; ++i) {
266 std::string a(1, values[i]);
267 // Defeat copy-on-write
268 std::string aCopy(a.data(), a.size());
269 expectEQ(a, aCopy);
270 expectEQ(StringPiece(a), StringPiece(aCopy));
271
272 for (size_t j = i + 1; j < count; ++j) {
273 std::string b(1, values[j]);
274 expectLT(a, b);
275 expectLT(StringPiece(a), StringPiece(b));
276 }
277 }
278}
279
280TEST(StringPiece, ToByteRange) {
281 StringPiece a("hello");
282 ByteRange b(a);
283 EXPECT_EQ(
284 static_cast<const void*>(a.begin()), static_cast<const void*>(b.begin()));
285 EXPECT_EQ(
286 static_cast<const void*>(a.end()), static_cast<const void*>(b.end()));
287
288 // and convert back again
289 StringPiece c(b);
290 EXPECT_EQ(a.begin(), c.begin());
291 EXPECT_EQ(a.end(), c.end());
292}
293
294TEST(StringPiece, InvalidRange) {
295 StringPiece a("hello");
296 EXPECT_EQ(a, a.subpiece(0, 10));
297 EXPECT_EQ(StringPiece("ello"), a.subpiece(1));
298 EXPECT_EQ(StringPiece("ello"), a.subpiece(1, std::string::npos));
299 EXPECT_EQ(StringPiece("ell"), a.subpiece(1, 3));
300 EXPECT_THROW(a.subpiece(6, 7), std::out_of_range);
301 EXPECT_THROW(a.subpiece(6), std::out_of_range);
302
303 std::string b("hello");
304 EXPECT_EQ(a, StringPiece(b, 0, 10));
305 EXPECT_EQ("ello", a.subpiece(1));
306 EXPECT_EQ("ello", a.subpiece(1, std::string::npos));
307 EXPECT_EQ("ell", a.subpiece(1, 3));
308 EXPECT_THROW(a.subpiece(6, 7), std::out_of_range);
309 EXPECT_THROW(a.subpiece(6), std::out_of_range);
310}
311
312TEST(StringPiece, Constexpr) {
313 constexpr const char* helloArray = "hello";
314
315 constexpr StringPiece hello1("hello");
316 EXPECT_EQ("hello", hello1);
317 static_assert(hello1.size() == 5, "hello size should be 5 at compile time");
318
319 constexpr StringPiece hello2(helloArray);
320 EXPECT_EQ("hello", hello2);
321 static_assert(hello2.size() == 5, "hello size should be 5 at compile time");
322}
323
324TEST(StringPiece, Prefix) {
325 StringPiece a("hello");
326 EXPECT_TRUE(a.startsWith(""));
327 EXPECT_TRUE(a.startsWith("h"));
328 EXPECT_TRUE(a.startsWith('h'));
329 EXPECT_TRUE(a.startsWith("hello"));
330 EXPECT_FALSE(a.startsWith("hellox"));
331 EXPECT_FALSE(a.startsWith('x'));
332 EXPECT_FALSE(a.startsWith("x"));
333
334 EXPECT_TRUE(a.startsWith("", folly::AsciiCaseInsensitive()));
335 EXPECT_TRUE(a.startsWith("hello", folly::AsciiCaseInsensitive()));
336 EXPECT_TRUE(a.startsWith("hellO", folly::AsciiCaseInsensitive()));
337 EXPECT_TRUE(a.startsWith("HELL", folly::AsciiCaseInsensitive()));
338 EXPECT_TRUE(a.startsWith("H", folly::AsciiCaseInsensitive()));
339 EXPECT_FALSE(a.startsWith("HELLOX", folly::AsciiCaseInsensitive()));
340 EXPECT_FALSE(a.startsWith("x", folly::AsciiCaseInsensitive()));
341 EXPECT_FALSE(a.startsWith("X", folly::AsciiCaseInsensitive()));
342
343 {
344 auto b = a;
345 EXPECT_TRUE(b.removePrefix(""));
346 EXPECT_EQ("hello", b);
347 }
348 {
349 auto b = a;
350 EXPECT_TRUE(b.removePrefix("h"));
351 EXPECT_EQ("ello", b);
352 }
353 {
354 auto b = a;
355 EXPECT_TRUE(b.removePrefix('h'));
356 EXPECT_EQ("ello", b);
357 }
358 {
359 auto b = a;
360 EXPECT_TRUE(b.removePrefix("hello"));
361 EXPECT_EQ("", b);
362 }
363 {
364 auto b = a;
365 EXPECT_FALSE(b.removePrefix("hellox"));
366 EXPECT_EQ("hello", b);
367 }
368 {
369 auto b = a;
370 EXPECT_FALSE(b.removePrefix("x"));
371 EXPECT_EQ("hello", b);
372 }
373 {
374 auto b = a;
375 EXPECT_FALSE(b.removePrefix('x'));
376 EXPECT_EQ("hello", b);
377 }
378}
379
380TEST(StringPiece, Suffix) {
381 StringPiece a("hello");
382 EXPECT_TRUE(a.endsWith(""));
383 EXPECT_TRUE(a.endsWith("o"));
384 EXPECT_TRUE(a.endsWith('o'));
385 EXPECT_TRUE(a.endsWith("hello"));
386 EXPECT_FALSE(a.endsWith("xhello"));
387 EXPECT_FALSE(a.endsWith("x"));
388 EXPECT_FALSE(a.endsWith('x'));
389
390 EXPECT_TRUE(a.endsWith("", folly::AsciiCaseInsensitive()));
391 EXPECT_TRUE(a.endsWith("o", folly::AsciiCaseInsensitive()));
392 EXPECT_TRUE(a.endsWith("O", folly::AsciiCaseInsensitive()));
393 EXPECT_TRUE(a.endsWith("hello", folly::AsciiCaseInsensitive()));
394 EXPECT_TRUE(a.endsWith("hellO", folly::AsciiCaseInsensitive()));
395 EXPECT_FALSE(a.endsWith("xhello", folly::AsciiCaseInsensitive()));
396 EXPECT_FALSE(a.endsWith("Xhello", folly::AsciiCaseInsensitive()));
397 EXPECT_FALSE(a.endsWith("x", folly::AsciiCaseInsensitive()));
398 EXPECT_FALSE(a.endsWith("X", folly::AsciiCaseInsensitive()));
399
400 {
401 auto b = a;
402 EXPECT_TRUE(b.removeSuffix(""));
403 EXPECT_EQ("hello", b);
404 }
405 {
406 auto b = a;
407 EXPECT_TRUE(b.removeSuffix("o"));
408 EXPECT_EQ("hell", b);
409 }
410 {
411 auto b = a;
412 EXPECT_TRUE(b.removeSuffix('o'));
413 EXPECT_EQ("hell", b);
414 }
415 {
416 auto b = a;
417 EXPECT_TRUE(b.removeSuffix("hello"));
418 EXPECT_EQ("", b);
419 }
420 {
421 auto b = a;
422 EXPECT_FALSE(b.removeSuffix("xhello"));
423 EXPECT_EQ("hello", b);
424 }
425 {
426 auto b = a;
427 EXPECT_FALSE(b.removeSuffix("x"));
428 EXPECT_EQ("hello", b);
429 }
430 {
431 auto b = a;
432 EXPECT_FALSE(b.removeSuffix('x'));
433 EXPECT_EQ("hello", b);
434 }
435}
436
437TEST(StringPiece, Equals) {
438 StringPiece a("hello");
439
440 EXPECT_TRUE(a.equals("HELLO", AsciiCaseInsensitive()));
441 EXPECT_FALSE(a.equals("HELLOX", AsciiCaseInsensitive()));
442}
443
444TEST(StringPiece, PrefixEmpty) {
445 StringPiece a;
446 EXPECT_TRUE(a.startsWith(""));
447 EXPECT_FALSE(a.startsWith("a"));
448 EXPECT_FALSE(a.startsWith('a'));
449 EXPECT_TRUE(a.removePrefix(""));
450 EXPECT_EQ("", a);
451 EXPECT_FALSE(a.removePrefix("a"));
452 EXPECT_EQ("", a);
453 EXPECT_FALSE(a.removePrefix('a'));
454 EXPECT_EQ("", a);
455}
456
457TEST(StringPiece, SuffixEmpty) {
458 StringPiece a;
459 EXPECT_TRUE(a.endsWith(""));
460 EXPECT_FALSE(a.endsWith("a"));
461 EXPECT_FALSE(a.endsWith('a'));
462 EXPECT_TRUE(a.removeSuffix(""));
463 EXPECT_EQ("", a);
464 EXPECT_FALSE(a.removeSuffix("a"));
465 EXPECT_EQ("", a);
466 EXPECT_FALSE(a.removeSuffix('a'));
467 EXPECT_EQ("", a);
468}
469
470TEST(StringPiece, erase) {
471 StringPiece a("hello");
472 auto b = a.begin();
473 auto e = b + 1;
474 a.erase(b, e);
475 EXPECT_EQ("ello", a);
476
477 e = a.end();
478 b = e - 1;
479 a.erase(b, e);
480 EXPECT_EQ("ell", a);
481
482 b = a.end() - 1;
483 e = a.end() - 1;
484 EXPECT_THROW(a.erase(b, e), std::out_of_range);
485
486 b = a.begin();
487 e = a.end();
488 a.erase(b, e);
489 EXPECT_EQ("", a);
490
491 a = "hello";
492 b = a.begin();
493 e = b + 2;
494 a.erase(b, e);
495 EXPECT_EQ("llo", a);
496
497 b = a.end() - 2;
498 e = a.end();
499 a.erase(b, e);
500 EXPECT_EQ("l", a);
501
502 a = " hello ";
503 boost::algorithm::trim(a);
504 EXPECT_EQ(a, "hello");
505}
506
507TEST(StringPiece, split_step_char_delimiter) {
508 // 0 1 2
509 // 012345678901234567890123456
510 auto const s = "this is just a test string";
511 auto const e = std::next(s, std::strlen(s));
512 EXPECT_EQ('\0', *e);
513
514 folly::StringPiece p(s);
515 EXPECT_EQ(s, p.begin());
516 EXPECT_EQ(e, p.end());
517 EXPECT_EQ(s, p);
518
519 auto x = p.split_step(' ');
520 EXPECT_EQ(std::next(s, 5), p.begin());
521 EXPECT_EQ(e, p.end());
522 EXPECT_EQ("this", x);
523
524 x = p.split_step(' ');
525 EXPECT_EQ(std::next(s, 8), p.begin());
526 EXPECT_EQ(e, p.end());
527 EXPECT_EQ("is", x);
528
529 x = p.split_step('u');
530 EXPECT_EQ(std::next(s, 10), p.begin());
531 EXPECT_EQ(e, p.end());
532 EXPECT_EQ("j", x);
533
534 x = p.split_step(' ');
535 EXPECT_EQ(std::next(s, 13), p.begin());
536 EXPECT_EQ(e, p.end());
537 EXPECT_EQ("st", x);
538
539 x = p.split_step(' ');
540 EXPECT_EQ(std::next(s, 14), p.begin());
541 EXPECT_EQ(e, p.end());
542 EXPECT_EQ("", x);
543
544 x = p.split_step(' ');
545 EXPECT_EQ(std::next(s, 16), p.begin());
546 EXPECT_EQ(e, p.end());
547 EXPECT_EQ("a", x);
548
549 x = p.split_step(' ');
550 EXPECT_EQ(std::next(s, 21), p.begin());
551 EXPECT_EQ(e, p.end());
552 EXPECT_EQ("test", x);
553
554 x = p.split_step(' ');
555 EXPECT_EQ(e, p.begin());
556 EXPECT_EQ(e, p.end());
557 EXPECT_EQ("string", x);
558
559 x = p.split_step(' ');
560 EXPECT_EQ(e, p.begin());
561 EXPECT_EQ(e, p.end());
562 EXPECT_EQ("", x);
563}
564
565TEST(StringPiece, split_step_range_delimiter) {
566 // 0 1 2 3
567 // 0123456789012345678901234567890123
568 auto const s = "this is just a test string";
569 auto const e = std::next(s, std::strlen(s));
570 EXPECT_EQ('\0', *e);
571
572 folly::StringPiece p(s);
573 EXPECT_EQ(s, p.begin());
574 EXPECT_EQ(e, p.end());
575 EXPECT_EQ(s, p);
576
577 auto x = p.split_step(" ");
578 EXPECT_EQ(std::next(s, 6), p.begin());
579 EXPECT_EQ(e, p.end());
580 EXPECT_EQ("this", x);
581
582 x = p.split_step(" ");
583 EXPECT_EQ(std::next(s, 10), p.begin());
584 EXPECT_EQ(e, p.end());
585 EXPECT_EQ("is", x);
586
587 x = p.split_step("u");
588 EXPECT_EQ(std::next(s, 12), p.begin());
589 EXPECT_EQ(e, p.end());
590 EXPECT_EQ("j", x);
591
592 x = p.split_step(" ");
593 EXPECT_EQ(std::next(s, 16), p.begin());
594 EXPECT_EQ(e, p.end());
595 EXPECT_EQ("st", x);
596
597 x = p.split_step(" ");
598 EXPECT_EQ(std::next(s, 18), p.begin());
599 EXPECT_EQ(e, p.end());
600 EXPECT_EQ("", x);
601
602 x = p.split_step(" ");
603 EXPECT_EQ(std::next(s, 21), p.begin());
604 EXPECT_EQ(e, p.end());
605 EXPECT_EQ("a", x);
606
607 x = p.split_step(" ");
608 EXPECT_EQ(std::next(s, 28), p.begin());
609 EXPECT_EQ(e, p.end());
610 EXPECT_EQ(" test", x);
611
612 x = p.split_step(" ");
613 EXPECT_EQ(e, p.begin());
614 EXPECT_EQ(e, p.end());
615 EXPECT_EQ("string", x);
616
617 x = p.split_step(" ");
618 EXPECT_EQ(e, p.begin());
619 EXPECT_EQ(e, p.end());
620 EXPECT_EQ("", x);
621
622 x = p.split_step(" ");
623 EXPECT_EQ(e, p.begin());
624 EXPECT_EQ(e, p.end());
625 EXPECT_EQ("", x);
626}
627
628void split_step_with_process_noop(folly::StringPiece) {}
629
630TEST(StringPiece, split_step_with_process_char_delimiter) {
631 // 0 1 2
632 // 012345678901234567890123456
633 auto const s = "this is just a test string";
634 auto const e = std::next(s, std::strlen(s));
635 EXPECT_EQ('\0', *e);
636
637 folly::StringPiece p(s);
638 EXPECT_EQ(s, p.begin());
639 EXPECT_EQ(e, p.end());
640 EXPECT_EQ(s, p);
641
642 EXPECT_EQ(1, (p.split_step(' ', [&](folly::StringPiece x) {
643 EXPECT_EQ(std::next(s, 5), p.begin());
644 EXPECT_EQ(e, p.end());
645 EXPECT_EQ("this", x);
646 return 1;
647 })));
648
649 EXPECT_EQ(2, (p.split_step(' ', [&](folly::StringPiece x) {
650 EXPECT_EQ(std::next(s, 8), p.begin());
651 EXPECT_EQ(e, p.end());
652 EXPECT_EQ("is", x);
653 return 2;
654 })));
655
656 EXPECT_EQ(3, (p.split_step('u', [&](folly::StringPiece x) {
657 EXPECT_EQ(std::next(s, 10), p.begin());
658 EXPECT_EQ(e, p.end());
659 EXPECT_EQ("j", x);
660 return 3;
661 })));
662
663 EXPECT_EQ(4, (p.split_step(' ', [&](folly::StringPiece x) {
664 EXPECT_EQ(std::next(s, 13), p.begin());
665 EXPECT_EQ(e, p.end());
666 EXPECT_EQ("st", x);
667 return 4;
668 })));
669
670 EXPECT_EQ(5, (p.split_step(' ', [&](folly::StringPiece x) {
671 EXPECT_EQ(std::next(s, 14), p.begin());
672 EXPECT_EQ(e, p.end());
673 EXPECT_EQ("", x);
674 return 5;
675 })));
676
677 EXPECT_EQ(6, (p.split_step(' ', [&](folly::StringPiece x) {
678 EXPECT_EQ(std::next(s, 16), p.begin());
679 EXPECT_EQ(e, p.end());
680 EXPECT_EQ("a", x);
681 return 6;
682 })));
683
684 EXPECT_EQ(7, (p.split_step(' ', [&](folly::StringPiece x) {
685 EXPECT_EQ(std::next(s, 21), p.begin());
686 EXPECT_EQ(e, p.end());
687 EXPECT_EQ("test", x);
688 return 7;
689 })));
690
691 EXPECT_EQ(8, (p.split_step(' ', [&](folly::StringPiece x) {
692 EXPECT_EQ(e, p.begin());
693 EXPECT_EQ(e, p.end());
694 EXPECT_EQ("string", x);
695 return 8;
696 })));
697
698 EXPECT_EQ(9, (p.split_step(' ', [&](folly::StringPiece x) {
699 EXPECT_EQ(e, p.begin());
700 EXPECT_EQ(e, p.end());
701 EXPECT_EQ("", x);
702 return 9;
703 })));
704
705 EXPECT_TRUE(
706 (std::is_same<
707 void,
708 decltype(p.split_step(' ', split_step_with_process_noop))>::value));
709
710 EXPECT_NO_THROW(p.split_step(' ', split_step_with_process_noop));
711}
712
713TEST(StringPiece, split_step_with_process_range_delimiter) {
714 // 0 1 2 3
715 // 0123456789012345678901234567890123
716 auto const s = "this is just a test string";
717 auto const e = std::next(s, std::strlen(s));
718 EXPECT_EQ('\0', *e);
719
720 folly::StringPiece p(s);
721 EXPECT_EQ(s, p.begin());
722 EXPECT_EQ(e, p.end());
723 EXPECT_EQ(s, p);
724
725 EXPECT_EQ(1, (p.split_step(" ", [&](folly::StringPiece x) {
726 EXPECT_EQ(std::next(s, 6), p.begin());
727 EXPECT_EQ(e, p.end());
728 EXPECT_EQ("this", x);
729 return 1;
730 })));
731
732 EXPECT_EQ(2, (p.split_step(" ", [&](folly::StringPiece x) {
733 EXPECT_EQ(std::next(s, 10), p.begin());
734 EXPECT_EQ(e, p.end());
735 EXPECT_EQ("is", x);
736 return 2;
737 })));
738
739 EXPECT_EQ(3, (p.split_step("u", [&](folly::StringPiece x) {
740 EXPECT_EQ(std::next(s, 12), p.begin());
741 EXPECT_EQ(e, p.end());
742 EXPECT_EQ("j", x);
743 return 3;
744 })));
745
746 EXPECT_EQ(4, (p.split_step(" ", [&](folly::StringPiece x) {
747 EXPECT_EQ(std::next(s, 16), p.begin());
748 EXPECT_EQ(e, p.end());
749 EXPECT_EQ("st", x);
750 return 4;
751 })));
752
753 EXPECT_EQ(5, (p.split_step(" ", [&](folly::StringPiece x) {
754 EXPECT_EQ(std::next(s, 18), p.begin());
755 EXPECT_EQ(e, p.end());
756 EXPECT_EQ("", x);
757 return 5;
758 })));
759
760 EXPECT_EQ(6, (p.split_step(" ", [&](folly::StringPiece x) {
761 EXPECT_EQ(std::next(s, 21), p.begin());
762 EXPECT_EQ(e, p.end());
763 EXPECT_EQ("a", x);
764 return 6;
765 })));
766
767 EXPECT_EQ(7, (p.split_step(" ", [&](folly::StringPiece x) {
768 EXPECT_EQ(std::next(s, 28), p.begin());
769 EXPECT_EQ(e, p.end());
770 EXPECT_EQ(" test", x);
771 return 7;
772 })));
773
774 EXPECT_EQ(8, (p.split_step(" ", [&](folly::StringPiece x) {
775 EXPECT_EQ(e, p.begin());
776 EXPECT_EQ(e, p.end());
777 EXPECT_EQ("string", x);
778 return 8;
779 })));
780
781 EXPECT_EQ(9, (p.split_step(" ", [&](folly::StringPiece x) {
782 EXPECT_EQ(e, p.begin());
783 EXPECT_EQ(e, p.end());
784 EXPECT_EQ("", x);
785 return 9;
786 })));
787
788 EXPECT_EQ(10, (p.split_step(" ", [&](folly::StringPiece x) {
789 EXPECT_EQ(e, p.begin());
790 EXPECT_EQ(e, p.end());
791 EXPECT_EQ("", x);
792 return 10;
793 })));
794
795 EXPECT_TRUE(
796 (std::is_same<
797 void,
798 decltype(p.split_step(' ', split_step_with_process_noop))>::value));
799
800 EXPECT_NO_THROW(p.split_step(' ', split_step_with_process_noop));
801}
802
803TEST(StringPiece, split_step_with_process_char_delimiter_additional_args) {
804 // 0 1 2
805 // 012345678901234567890123456
806 auto const s = "this is just a test string";
807 auto const e = std::next(s, std::strlen(s));
808 auto const delimiter = ' ';
809 EXPECT_EQ('\0', *e);
810
811 folly::StringPiece p(s);
812 EXPECT_EQ(s, p.begin());
813 EXPECT_EQ(e, p.end());
814 EXPECT_EQ(s, p);
815
816 auto const functor = [](folly::StringPiece s_, folly::StringPiece expected) {
817 EXPECT_EQ(expected, s_);
818 return expected;
819 };
820
821 auto const checker = [&](folly::StringPiece expected) {
822 EXPECT_EQ(expected, p.split_step(delimiter, functor, expected));
823 };
824
825 checker("this");
826 checker("is");
827 checker("just");
828 checker("");
829 checker("a");
830 checker("test");
831 checker("string");
832 checker("");
833 checker("");
834
835 EXPECT_TRUE(p.empty());
836}
837
838TEST(StringPiece, split_step_with_process_range_delimiter_additional_args) {
839 // 0 1 2 3
840 // 0123456789012345678901234567890123
841 auto const s = "this is just a test string";
842 auto const e = std::next(s, std::strlen(s));
843 auto const delimiter = " ";
844 EXPECT_EQ('\0', *e);
845
846 folly::StringPiece p(s);
847 EXPECT_EQ(s, p.begin());
848 EXPECT_EQ(e, p.end());
849 EXPECT_EQ(s, p);
850
851 auto const functor = [](folly::StringPiece s_, folly::StringPiece expected) {
852 EXPECT_EQ(expected, s_);
853 return expected;
854 };
855
856 auto const checker = [&](folly::StringPiece expected) {
857 EXPECT_EQ(expected, p.split_step(delimiter, functor, expected));
858 };
859
860 checker("this");
861 checker("is");
862 checker("just");
863 checker("");
864 checker("a");
865 checker(" test");
866 checker("string");
867 checker("");
868 checker("");
869
870 EXPECT_TRUE(p.empty());
871}
872
873TEST(StringPiece, NoInvalidImplicitConversions) {
874 struct IsString {
875 bool operator()(folly::Range<int*>) {
876 return false;
877 }
878 bool operator()(folly::StringPiece) {
879 return true;
880 }
881 };
882
883 std::string s = "hello";
884 EXPECT_TRUE(IsString()(s));
885}
886
887TEST(qfind, UInt32_Ranges) {
888 vector<uint32_t> a({1, 2, 3, 260, 5});
889 vector<uint32_t> b({2, 3, 4});
890
891 auto a_range = folly::Range<const uint32_t*>(&a[0], a.size());
892 auto b_range = folly::Range<const uint32_t*>(&b[0], b.size());
893
894 EXPECT_EQ(qfind(a_range, b_range), string::npos);
895
896 a[3] = 4;
897 EXPECT_EQ(qfind(a_range, b_range), 1);
898}
899
900template <typename NeedleFinder>
901class NeedleFinderTest : public ::testing::Test {
902 public:
903 static size_t find_first_byte_of(StringPiece haystack, StringPiece needles) {
904 return NeedleFinder::find_first_byte_of(haystack, needles);
905 }
906};
907
908struct SseNeedleFinder {
909 static size_t find_first_byte_of(StringPiece haystack, StringPiece needles) {
910 // This will only use the SSE version if it is supported on this CPU
911 // (selected using ifunc).
912 return detail::qfind_first_byte_of(haystack, needles);
913 }
914};
915
916struct NoSseNeedleFinder {
917 static size_t find_first_byte_of(StringPiece haystack, StringPiece needles) {
918 return detail::qfind_first_byte_of_nosse(haystack, needles);
919 }
920};
921
922struct ByteSetNeedleFinder {
923 static size_t find_first_byte_of(StringPiece haystack, StringPiece needles) {
924 return detail::qfind_first_byte_of_byteset(haystack, needles);
925 }
926};
927
928using NeedleFinders =
929 ::testing::Types<SseNeedleFinder, NoSseNeedleFinder, ByteSetNeedleFinder>;
930TYPED_TEST_CASE(NeedleFinderTest, NeedleFinders);
931
932TYPED_TEST(NeedleFinderTest, Null) {
933 { // null characters in the string
934 string s(10, char(0));
935 s[5] = 'b';
936 string delims("abc");
937 EXPECT_EQ(5, this->find_first_byte_of(s, delims));
938 }
939 { // null characters in delim
940 string s("abc");
941 string delims(10, char(0));
942 delims[3] = 'c';
943 delims[7] = 'b';
944 EXPECT_EQ(1, this->find_first_byte_of(s, delims));
945 }
946 { // range not terminated by null character
947 string buf = "abcdefghijklmnopqrstuvwxyz";
948 StringPiece s(buf.data() + 5, 3);
949 StringPiece delims("z");
950 EXPECT_EQ(string::npos, this->find_first_byte_of(s, delims));
951 }
952}
953
954TYPED_TEST(NeedleFinderTest, DelimDuplicates) {
955 string delims(1000, 'b');
956 EXPECT_EQ(1, this->find_first_byte_of("abc", delims));
957 EXPECT_EQ(string::npos, this->find_first_byte_of("ac", delims));
958}
959
960TYPED_TEST(NeedleFinderTest, Empty) {
961 string a = "abc";
962 string b = "";
963 EXPECT_EQ(string::npos, this->find_first_byte_of(a, b));
964 EXPECT_EQ(string::npos, this->find_first_byte_of(b, a));
965 EXPECT_EQ(string::npos, this->find_first_byte_of(b, b));
966}
967
968TYPED_TEST(NeedleFinderTest, Unaligned) {
969 // works correctly even if input buffers are not 16-byte aligned
970 string s = "0123456789ABCDEFGH";
971 for (size_t i = 0; i < s.size(); ++i) {
972 StringPiece a(s.c_str() + i);
973 for (size_t j = 0; j < s.size(); ++j) {
974 StringPiece b(s.c_str() + j);
975 EXPECT_EQ((i > j) ? 0 : j - i, this->find_first_byte_of(a, b));
976 }
977 }
978}
979
980// for some algorithms (specifically those that create a set of needles),
981// we check for the edge-case of _all_ possible needles being sought.
982TYPED_TEST(NeedleFinderTest, Needles256) {
983 string needles;
984 const auto minValue = std::numeric_limits<StringPiece::value_type>::min();
985 const auto maxValue = std::numeric_limits<StringPiece::value_type>::max();
986 // make the size ~big to avoid any edge-case branches for tiny haystacks
987 const int haystackSize = 50;
988 for (int i = minValue; i <= maxValue; i++) { // <=
989 needles.push_back(i);
990 }
991 EXPECT_EQ(StringPiece::npos, this->find_first_byte_of("", needles));
992 for (int i = minValue; i <= maxValue; i++) {
993 EXPECT_EQ(0, this->find_first_byte_of(string(haystackSize, i), needles));
994 }
995
996 needles.append("these are redundant characters");
997 EXPECT_EQ(StringPiece::npos, this->find_first_byte_of("", needles));
998 for (int i = minValue; i <= maxValue; i++) {
999 EXPECT_EQ(0, this->find_first_byte_of(string(haystackSize, i), needles));
1000 }
1001}
1002
1003TYPED_TEST(NeedleFinderTest, Base) {
1004 for (size_t i = 0; i < 32; ++i) {
1005 for (int j = 0; j < 32; ++j) {
1006 string s = string(i, 'X') + "abca" + string(i, 'X');
1007 string delims = string(j, 'Y') + "a" + string(j, 'Y');
1008 EXPECT_EQ(i, this->find_first_byte_of(s, delims));
1009 }
1010 }
1011}
1012
1013const size_t kPageSize = 4096;
1014// Updates contents so that any read accesses past the last byte will
1015// cause a SIGSEGV. It accomplishes this by changing access to the page that
1016// begins immediately after the end of the contents (as allocators and mmap()
1017// all operate on page boundaries, this is a reasonable assumption).
1018// This function will also initialize buf, which caller must free().
1019void createProtectedBuf(StringPiece& contents, char** buf) {
1020 ASSERT_LE(contents.size(), kPageSize);
1021 char* pageAlignedBuf = (char*)aligned_malloc(2 * kPageSize, kPageSize);
1022 if (pageAlignedBuf == nullptr) {
1023 FAIL();
1024 }
1025 // Protect the page after the first full page-aligned region of the
1026 // malloc'ed buffer
1027 mprotect(pageAlignedBuf + kPageSize, kPageSize, PROT_NONE);
1028 size_t newBegin = kPageSize - contents.size();
1029 memcpy(pageAlignedBuf + newBegin, contents.data(), contents.size());
1030 contents.reset(pageAlignedBuf + newBegin, contents.size());
1031 *buf = pageAlignedBuf;
1032}
1033
1034void freeProtectedBuf(char* buf) {
1035 mprotect(buf + kPageSize, kPageSize, PROT_READ | PROT_WRITE);
1036 aligned_free(buf);
1037}
1038
1039TYPED_TEST(NeedleFinderTest, NoSegFault) {
1040 const string base = string(32, 'a') + string("b");
1041 const string delims = string(32, 'c') + string("b");
1042 for (int i = 0; i <= 32; i++) {
1043 for (int j = 0; j <= 33; j++) {
1044 for (int shouldFind = 0; shouldFind <= 1; ++shouldFind) {
1045 StringPiece s1(base);
1046 s1.advance(i);
1047 ASSERT_TRUE(!s1.empty());
1048 if (!shouldFind) {
1049 s1.pop_back();
1050 }
1051 StringPiece s2(delims);
1052 s2.advance(j);
1053 char* buf1;
1054 char* buf2;
1055 createProtectedBuf(s1, &buf1);
1056 createProtectedBuf(s2, &buf2);
1057 // printf("s1: '%s' (%ld) \ts2: '%s' (%ld)\n",
1058 // string(s1.data(), s1.size()).c_str(), s1.size(),
1059 // string(s2.data(), s2.size()).c_str(), s2.size());
1060 auto r1 = this->find_first_byte_of(s1, s2);
1061 auto f1 =
1062 std::find_first_of(s1.begin(), s1.end(), s2.begin(), s2.end());
1063 auto e1 = (f1 == s1.end()) ? StringPiece::npos : f1 - s1.begin();
1064 EXPECT_EQ(r1, e1);
1065 auto r2 = this->find_first_byte_of(s2, s1);
1066 auto f2 =
1067 std::find_first_of(s2.begin(), s2.end(), s1.begin(), s1.end());
1068 auto e2 = (f2 == s2.end()) ? StringPiece::npos : f2 - s2.begin();
1069 EXPECT_EQ(r2, e2);
1070 freeProtectedBuf(buf1);
1071 freeProtectedBuf(buf2);
1072 }
1073 }
1074 }
1075}
1076
1077TEST(NonConstTest, StringPiece) {
1078 std::string hello("hello");
1079 MutableStringPiece sp(&hello.front(), hello.size());
1080 sp[0] = 'x';
1081 EXPECT_EQ("xello", hello);
1082 {
1083 StringPiece s(sp);
1084 EXPECT_EQ("xello", s);
1085 }
1086 {
1087 ByteRange r1(sp);
1088 MutableByteRange r2(sp);
1089 }
1090}
1091
1092// Similar to the begin() template functions, but instread of returing
1093// an iterator, return a pointer to data.
1094template <class Container>
1095typename Container::value_type* dataPtr(Container& cont) {
1096 // NOTE: &cont[0] is undefined if cont is empty (it creates a
1097 // reference to nullptr - which is not dereferenced, but still UBSAN).
1098 return cont.data();
1099}
1100template <class T, size_t N>
1101constexpr T* dataPtr(T (&arr)[N]) noexcept {
1102 return &arr[0];
1103}
1104
1105template <class C>
1106void testRangeFunc(C&& x, size_t n) {
1107 const auto& cx = x;
1108 // type, conversion checks
1109 using R1Iter =
1110 std::conditional_t<_t<std::is_reference<C>>::value, int*, int const*>;
1111 Range<R1Iter> r1 = range(std::forward<C>(x));
1112 Range<const int*> r2 = range(std::forward<C>(x));
1113 Range<const int*> r3 = range(cx);
1114 Range<const int*> r5 = range(std::move(cx));
1115 EXPECT_EQ(r1.begin(), dataPtr(x));
1116 EXPECT_EQ(r1.end(), dataPtr(x) + n);
1117 EXPECT_EQ(n, r1.size());
1118 EXPECT_EQ(n, r2.size());
1119 EXPECT_EQ(n, r3.size());
1120 EXPECT_EQ(n, r5.size());
1121}
1122
1123TEST(RangeFunc, Vector) {
1124 std::vector<int> x;
1125 testRangeFunc(x, 0);
1126 x.push_back(2);
1127 testRangeFunc(x, 1);
1128 testRangeFunc(std::vector<int>{1, 2}, 2);
1129}
1130
1131TEST(RangeFunc, Array) {
1132 std::array<int, 3> x;
1133 testRangeFunc(x, 3);
1134}
1135
1136TEST(RangeFunc, CArray) {
1137 int x[]{1, 2, 3, 4};
1138 testRangeFunc(x, 4);
1139}
1140
1141TEST(RangeFunc, ConstexprCArray) {
1142 static constexpr const int numArray[4] = {3, 17, 1, 9};
1143 constexpr const auto numArrayRange = range(numArray);
1144 EXPECT_EQ(17, numArrayRange[1]);
1145 constexpr const auto numArrayRangeSize = numArrayRange.size();
1146 EXPECT_EQ(4, numArrayRangeSize);
1147}
1148
1149TEST(RangeFunc, ConstexprStdArray) {
1150 static constexpr const std::array<int, 4> numArray = {{3, 17, 1, 9}};
1151 constexpr const auto numArrayRange = range(numArray);
1152 EXPECT_EQ(17, numArrayRange[1]);
1153 constexpr const auto numArrayRangeSize = numArrayRange.size();
1154 EXPECT_EQ(4, numArrayRangeSize);
1155}
1156
1157TEST(RangeFunc, ConstexprStdArrayZero) {
1158 static constexpr const std::array<int, 0> numArray = {};
1159 constexpr const auto numArrayRange = range(numArray);
1160 constexpr const auto numArrayRangeSize = numArrayRange.size();
1161 EXPECT_EQ(0, numArrayRangeSize);
1162}
1163
1164TEST(RangeFunc, ConstexprIteratorPair) {
1165 static constexpr const int numArray[4] = {3, 17, 1, 9};
1166 constexpr const auto numPtr = static_cast<const int*>(numArray);
1167 constexpr const auto numIterRange = range(numPtr + 1, numPtr + 3);
1168 EXPECT_EQ(1, numIterRange[1]);
1169 constexpr const auto numIterRangeSize = numIterRange.size();
1170 EXPECT_EQ(2, numIterRangeSize);
1171}
1172
1173TEST(RangeFunc, ConstexprCollection) {
1174 class IntCollection {
1175 public:
1176 constexpr IntCollection(const int* d, size_t s) : data_(d), size_(s) {}
1177 constexpr const int* data() const {
1178 return data_;
1179 }
1180 constexpr size_t size() const {
1181 return size_;
1182 }
1183
1184 private:
1185 const int* data_;
1186 size_t size_;
1187 };
1188 static constexpr const int numArray[4] = {3, 17, 1, 9};
1189 constexpr const auto numPtr = static_cast<const int*>(numArray);
1190 constexpr const auto numColl = IntCollection(numPtr + 1, 2);
1191 constexpr const auto numCollRange = range(numColl);
1192 EXPECT_EQ(1, numCollRange[1]);
1193 constexpr const auto numCollRangeSize = numCollRange.size();
1194 EXPECT_EQ(2, numCollRangeSize);
1195}
1196
1197TEST(CRangeFunc, CArray) {
1198 int numArray[4] = {3, 17, 1, 9};
1199 auto const numArrayRange = crange(numArray);
1200 EXPECT_TRUE(
1201 (std::is_same<int const*, decltype(numArrayRange)::iterator>::value));
1202 EXPECT_THAT(numArrayRange, testing::ElementsAreArray(numArray));
1203}
1204
1205TEST(CRangeFunc, StdArray) {
1206 std::array<int, 4> numArray = {{3, 17, 1, 9}};
1207 auto const numArrayRange = crange(numArray);
1208 EXPECT_TRUE(
1209 (std::is_same<int const*, decltype(numArrayRange)::iterator>::value));
1210 EXPECT_THAT(numArrayRange, testing::ElementsAreArray(numArray));
1211}
1212
1213TEST(CRangeFunc, StdArrayZero) {
1214 std::array<int, 0> numArray = {};
1215 auto const numArrayRange = crange(numArray);
1216 EXPECT_TRUE(
1217 (std::is_same<int const*, decltype(numArrayRange)::iterator>::value));
1218 EXPECT_THAT(numArrayRange, testing::IsEmpty());
1219}
1220
1221TEST(CRangeFunc, Collection) {
1222 class IntCollection {
1223 public:
1224 constexpr IntCollection(int* d, size_t s) : data_(d), size_(s) {}
1225 constexpr int const* data() const {
1226 return data_;
1227 }
1228 constexpr size_t size() const {
1229 return size_;
1230 }
1231
1232 private:
1233 int* data_;
1234 size_t size_;
1235 };
1236 int numArray[4] = {3, 17, 1, 9};
1237 auto numPtr = static_cast<int*>(numArray);
1238 auto numColl = IntCollection(numPtr + 1, 2);
1239 auto const numCollRange = crange(numColl);
1240 EXPECT_TRUE(
1241 (std::is_same<int const*, decltype(numCollRange)::iterator>::value));
1242 EXPECT_THAT(numCollRange, testing::ElementsAreArray({17, 1}));
1243}
1244
1245std::string get_rand_str(
1246 size_t size,
1247 std::uniform_int_distribution<>& dist,
1248 std::mt19937& gen) {
1249 std::string ret(size, '\0');
1250 for (size_t i = 0; i < size; ++i) {
1251 ret[i] = static_cast<char>(dist(gen));
1252 }
1253
1254 return ret;
1255}
1256
1257namespace folly {
1258bool operator==(MutableStringPiece mp, StringPiece sp) {
1259 return mp.compare(sp) == 0;
1260}
1261
1262bool operator==(StringPiece sp, MutableStringPiece mp) {
1263 return mp.compare(sp) == 0;
1264}
1265} // namespace folly
1266
1267TEST(ReplaceAt, exhaustiveTest) {
1268 char input[] = "this is nice and long input";
1269 auto msp = MutableStringPiece(input);
1270 auto str = std::string(input);
1271 std::random_device rd;
1272 std::mt19937 gen(rd());
1273 std::uniform_int_distribution<> dist('a', 'z');
1274
1275 for (int i = 0; i < 100; ++i) {
1276 for (size_t j = 1; j <= msp.size(); ++j) {
1277 auto replacement = get_rand_str(j, dist, gen);
1278 for (size_t pos = 0; pos < msp.size() - j; ++pos) {
1279 msp.replaceAt(pos, replacement);
1280 str.replace(pos, replacement.size(), replacement);
1281 EXPECT_EQ(msp.compare(str), 0);
1282 }
1283 }
1284 }
1285
1286 // too far
1287 EXPECT_EQ(msp.replaceAt(msp.size() - 2, StringPiece("meh")), false);
1288}
1289
1290TEST(ReplaceAll, basicTest) {
1291 char input[] = "this is nice and long input";
1292 auto orig = std::string(input);
1293 auto msp = MutableStringPiece(input);
1294
1295 EXPECT_EQ(msp.replaceAll("is", "si"), 2);
1296 EXPECT_EQ("thsi si nice and long input", msp);
1297 EXPECT_EQ(msp.replaceAll("si", "is"), 2);
1298 EXPECT_EQ(msp, orig);
1299
1300 EXPECT_EQ(msp.replaceAll("abcd", "efgh"), 0); // nothing to replace
1301 EXPECT_EQ(msp, orig);
1302
1303 // at the very beginning
1304 EXPECT_EQ(msp.replaceAll("this", "siht"), 1);
1305 EXPECT_EQ("siht is nice and long input", msp);
1306 EXPECT_EQ(msp.replaceAll("siht", "this"), 1);
1307 EXPECT_EQ(msp, orig);
1308
1309 // at the very end
1310 EXPECT_EQ(msp.replaceAll("input", "soput"), 1);
1311 EXPECT_EQ("this is nice and long soput", msp);
1312 EXPECT_EQ(msp.replaceAll("soput", "input"), 1);
1313 EXPECT_EQ(msp, orig);
1314
1315 // all spaces
1316 EXPECT_EQ(msp.replaceAll(" ", "@"), 5);
1317 EXPECT_EQ("this@is@nice@and@long@input", msp);
1318 EXPECT_EQ(msp.replaceAll("@", " "), 5);
1319 EXPECT_EQ(msp, orig);
1320}
1321
1322TEST(ReplaceAll, randomTest) {
1323 char input[] = "abcdefghijklmnoprstuwqz"; // no pattern repeata inside
1324 auto orig = std::string(input);
1325 auto msp = MutableStringPiece(input);
1326
1327 std::random_device rd;
1328 std::mt19937 gen(rd());
1329 std::uniform_int_distribution<> dist('A', 'Z');
1330
1331 for (int i = 0; i < 100; ++i) {
1332 for (size_t j = 1; j <= orig.size(); ++j) {
1333 auto replacement = get_rand_str(j, dist, gen);
1334 for (size_t pos = 0; pos < msp.size() - j; ++pos) {
1335 auto piece = orig.substr(pos, j);
1336 EXPECT_EQ(msp.replaceAll(piece, replacement), 1);
1337 EXPECT_EQ(msp.find(replacement), pos);
1338 EXPECT_EQ(msp.replaceAll(replacement, piece), 1);
1339 EXPECT_EQ(msp, orig);
1340 }
1341 }
1342 }
1343}
1344
1345TEST(ReplaceAll, BadArg) {
1346 int count = 0;
1347 auto fst = "longer";
1348 auto snd = "small";
1349 char input[] = "meh meh meh";
1350 auto all = MutableStringPiece(input);
1351
1352 try {
1353 all.replaceAll(fst, snd);
1354 } catch (std::invalid_argument&) {
1355 ++count;
1356 }
1357
1358 try {
1359 all.replaceAll(snd, fst);
1360 } catch (std::invalid_argument&) {
1361 ++count;
1362 }
1363
1364 EXPECT_EQ(count, 2);
1365}
1366
1367TEST(Range, Constructors) {
1368 vector<int> c = {1, 2, 3};
1369 typedef Range<vector<int>::iterator> RangeType;
1370 typedef Range<vector<int>::const_iterator> ConstRangeType;
1371 RangeType cr(c.begin(), c.end());
1372 auto subpiece1 = ConstRangeType(cr, 1, 5);
1373 auto subpiece2 = ConstRangeType(cr, 1);
1374 EXPECT_EQ(subpiece1.size(), 2);
1375 EXPECT_EQ(subpiece1.begin(), subpiece2.begin());
1376 EXPECT_EQ(subpiece1.end(), subpiece2.end());
1377}
1378
1379TEST(Range, ArrayConstructors) {
1380 auto charArray = std::array<char, 4>{{'t', 'e', 's', 't'}};
1381 auto constCharArray = std::array<char, 6>{{'f', 'o', 'o', 'b', 'a', 'r'}};
1382 auto emptyArray = std::array<char, 0>{};
1383
1384 auto sp1 = StringPiece{charArray};
1385 EXPECT_EQ(4, sp1.size());
1386 EXPECT_EQ(charArray.data(), sp1.data());
1387
1388 auto sp2 = StringPiece(constCharArray);
1389 EXPECT_EQ(6, sp2.size());
1390 EXPECT_EQ(constCharArray.data(), sp2.data());
1391
1392 auto msp = MutableStringPiece(charArray);
1393 EXPECT_EQ(4, msp.size());
1394 EXPECT_EQ(charArray.data(), msp.data());
1395
1396 auto esp = StringPiece(emptyArray);
1397 EXPECT_EQ(0, esp.size());
1398 EXPECT_EQ(nullptr, esp.data());
1399
1400 auto emsp = MutableStringPiece(emptyArray);
1401 EXPECT_EQ(0, emsp.size());
1402 EXPECT_EQ(nullptr, emsp.data());
1403
1404 static constexpr std::array<int, 4> numArray = {{3, 17, 1, 9}};
1405 constexpr auto numRange = Range<const int*>{numArray};
1406 EXPECT_EQ(17, numRange[1]);
1407
1408 static constexpr std::array<int, 0> emptyNumArray{};
1409 constexpr auto emptyNumRange = Range<const int*>{emptyNumArray};
1410 EXPECT_EQ(0, emptyNumRange.size());
1411}
1412
1413TEST(Range, ConstexprAccessors) {
1414 constexpr StringPiece piece = range("hello");
1415 static_assert(piece.size() == 6u, "");
1416 static_assert(piece.end() - piece.begin() == 6u, "");
1417 static_assert(piece.data() == piece.begin(), "");
1418 static_assert(piece.start() == piece.begin(), "");
1419 static_assert(piece.cbegin() == piece.begin(), "");
1420 static_assert(piece.cend() == piece.end(), "");
1421 static_assert(*piece.begin() == 'h', "");
1422 static_assert(*(piece.end() - 1) == '\0', "");
1423}
1424
1425TEST(Range, LiteralSuffix) {
1426 constexpr auto literalPiece = "hello"_sp;
1427 constexpr StringPiece piece = "hello";
1428 EXPECT_EQ(literalPiece, piece);
1429 constexpr auto literalPiece8 = u8"hello"_sp;
1430 constexpr Range<char const*> piece8 = u8"hello";
1431 EXPECT_EQ(literalPiece8, piece8);
1432 constexpr auto literalPiece16 = u"hello"_sp;
1433 constexpr Range<char16_t const*> piece16{u"hello", 5};
1434 EXPECT_EQ(literalPiece16, piece16);
1435 constexpr auto literalPiece32 = U"hello"_sp;
1436 constexpr Range<char32_t const*> piece32{U"hello", 5};
1437 EXPECT_EQ(literalPiece32, piece32);
1438 constexpr auto literalPieceW = L"hello"_sp;
1439 constexpr Range<wchar_t const*> pieceW{L"hello", 5};
1440 EXPECT_EQ(literalPieceW, pieceW);
1441}
1442
1443TEST(Range, LiteralSuffixContainsNulBytes) {
1444 constexpr auto literalPiece = "\0foo\0"_sp;
1445 EXPECT_EQ(5u, literalPiece.size());
1446}
1447
1448class tag {};
1449class fake_string_view {
1450 private:
1451 StringPiece piece_;
1452
1453 public:
1454 using size_type = std::size_t;
1455 explicit fake_string_view(char const* s, size_type c, tag = {})
1456 : piece_(s, c) {}
1457 /* implicit */ operator StringPiece() const {
1458 return piece_;
1459 }
1460 friend bool operator==(char const* rhs, fake_string_view lhs) {
1461 return rhs == lhs.piece_;
1462 }
1463};
1464
1465TEST(Range, StringPieceExplicitConversionOperator) {
1466 using PieceM = StringPiece;
1467 using PieceC = StringPiece const;
1468
1469 EXPECT_FALSE((std::is_convertible<PieceM, int>::value));
1470 EXPECT_FALSE((std::is_convertible<PieceM, std::string>::value));
1471 EXPECT_FALSE((std::is_convertible<PieceM, std::vector<char>>::value));
1472 EXPECT_FALSE((std::is_convertible<PieceM, fake_string_view>::value));
1473 EXPECT_FALSE((std::is_constructible<int, PieceM>::value));
1474 EXPECT_TRUE((std::is_constructible<std::string, PieceM>::value));
1475 EXPECT_TRUE((std::is_constructible<std::vector<char>, PieceM>::value));
1476 EXPECT_TRUE((std::is_constructible<fake_string_view, PieceM>::value));
1477
1478 EXPECT_FALSE((std::is_convertible<PieceC, int>::value));
1479 EXPECT_FALSE((std::is_convertible<PieceC, std::string>::value));
1480 EXPECT_FALSE((std::is_convertible<PieceC, std::vector<char>>::value));
1481 EXPECT_FALSE((std::is_convertible<PieceC, fake_string_view>::value));
1482 EXPECT_FALSE((std::is_constructible<int, PieceC>::value));
1483 EXPECT_TRUE((std::is_constructible<std::string, PieceC>::value));
1484 EXPECT_TRUE((std::is_constructible<std::vector<char>, PieceC>::value));
1485 EXPECT_TRUE((std::is_constructible<fake_string_view, PieceC>::value));
1486
1487 using testing::ElementsAreArray;
1488 std::array<char, 5> array = {{'h', 'e', 'l', 'l', 'o'}};
1489 PieceM piecem{array};
1490 PieceC piecec{array};
1491 std::allocator<char> alloc;
1492
1493 EXPECT_EQ("hello", std::string(piecem));
1494 EXPECT_EQ("hello", std::string(piecec));
1495 EXPECT_EQ("hello", std::string{piecem});
1496 EXPECT_EQ("hello", std::string{piecec});
1497 EXPECT_EQ("hello", piecem.to<std::string>());
1498 EXPECT_EQ("hello", piecec.to<std::string>());
1499 EXPECT_EQ("hello", piecem.to<std::string>(alloc));
1500 EXPECT_EQ("hello", piecec.to<std::string>(alloc));
1501
1502 EXPECT_THAT(std::vector<char>(piecem), ElementsAreArray(array));
1503 EXPECT_THAT(std::vector<char>(piecec), ElementsAreArray(array));
1504 EXPECT_THAT(std::vector<char>{piecem}, ElementsAreArray(array));
1505 EXPECT_THAT(std::vector<char>{piecec}, ElementsAreArray(array));
1506 EXPECT_THAT(piecem.to<std::vector<char>>(), ElementsAreArray(array));
1507 EXPECT_THAT(piecec.to<std::vector<char>>(), ElementsAreArray(array));
1508 EXPECT_THAT(piecem.to<std::vector<char>>(alloc), ElementsAreArray(array));
1509 EXPECT_THAT(piecec.to<std::vector<char>>(alloc), ElementsAreArray(array));
1510
1511 EXPECT_EQ("hello", fake_string_view(piecem));
1512 EXPECT_EQ("hello", fake_string_view(piecec));
1513 EXPECT_EQ("hello", fake_string_view{piecem});
1514 EXPECT_EQ("hello", fake_string_view{piecec});
1515 EXPECT_EQ("hello", piecem.to<fake_string_view>());
1516 EXPECT_EQ("hello", piecec.to<fake_string_view>());
1517 EXPECT_EQ("hello", piecem.to<fake_string_view>(tag{}));
1518 EXPECT_EQ("hello", piecec.to<fake_string_view>(tag{}));
1519}
1520
1521TEST(Range, MutableStringPieceExplicitConversionOperator) {
1522 using PieceM = MutableStringPiece;
1523 using PieceC = MutableStringPiece const;
1524
1525 EXPECT_FALSE((std::is_convertible<PieceM, int>::value));
1526 EXPECT_FALSE((std::is_convertible<PieceM, std::string>::value));
1527 EXPECT_FALSE((std::is_convertible<PieceM, std::vector<char>>::value));
1528 EXPECT_FALSE((std::is_convertible<PieceM, fake_string_view>::value));
1529 EXPECT_FALSE((std::is_constructible<int, PieceM>::value));
1530 EXPECT_TRUE((std::is_constructible<std::string, PieceM>::value));
1531 EXPECT_TRUE((std::is_constructible<std::vector<char>, PieceM>::value));
1532 EXPECT_TRUE((std::is_constructible<fake_string_view, PieceM>::value));
1533
1534 EXPECT_FALSE((std::is_convertible<PieceC, int>::value));
1535 EXPECT_FALSE((std::is_convertible<PieceC, std::string>::value));
1536 EXPECT_FALSE((std::is_convertible<PieceC, std::vector<char>>::value));
1537 EXPECT_FALSE((std::is_convertible<PieceC, fake_string_view>::value));
1538 EXPECT_FALSE((std::is_constructible<int, PieceC>::value));
1539 EXPECT_TRUE((std::is_constructible<std::string, PieceC>::value));
1540 EXPECT_TRUE((std::is_constructible<std::vector<char>, PieceC>::value));
1541 EXPECT_TRUE((std::is_constructible<fake_string_view, PieceC>::value));
1542
1543 using testing::ElementsAreArray;
1544 std::array<char, 5> array = {{'h', 'e', 'l', 'l', 'o'}};
1545 PieceM piecem{array};
1546 PieceC piecec{array};
1547 std::allocator<char> alloc;
1548
1549 EXPECT_EQ("hello", std::string(piecem));
1550 EXPECT_EQ("hello", std::string(piecec));
1551 EXPECT_EQ("hello", std::string{piecem});
1552 EXPECT_EQ("hello", std::string{piecec});
1553 EXPECT_EQ("hello", piecem.to<std::string>());
1554 EXPECT_EQ("hello", piecec.to<std::string>());
1555 EXPECT_EQ("hello", piecem.to<std::string>(alloc));
1556 EXPECT_EQ("hello", piecec.to<std::string>(alloc));
1557
1558 EXPECT_THAT(std::vector<char>(piecem), ElementsAreArray(array));
1559 EXPECT_THAT(std::vector<char>(piecec), ElementsAreArray(array));
1560 EXPECT_THAT(std::vector<char>{piecem}, ElementsAreArray(array));
1561 EXPECT_THAT(std::vector<char>{piecec}, ElementsAreArray(array));
1562 EXPECT_THAT(piecem.to<std::vector<char>>(), ElementsAreArray(array));
1563 EXPECT_THAT(piecec.to<std::vector<char>>(), ElementsAreArray(array));
1564 EXPECT_THAT(piecem.to<std::vector<char>>(alloc), ElementsAreArray(array));
1565 EXPECT_THAT(piecec.to<std::vector<char>>(alloc), ElementsAreArray(array));
1566
1567 EXPECT_EQ("hello", fake_string_view(piecem));
1568 EXPECT_EQ("hello", fake_string_view(piecec));
1569 EXPECT_EQ("hello", fake_string_view{piecem});
1570 EXPECT_EQ("hello", fake_string_view{piecec});
1571 EXPECT_EQ("hello", piecem.to<fake_string_view>());
1572 EXPECT_EQ("hello", piecec.to<fake_string_view>());
1573 EXPECT_EQ("hello", piecem.to<fake_string_view>(tag{}));
1574 EXPECT_EQ("hello", piecec.to<fake_string_view>(tag{}));
1575}
1576
1577#if FOLLY_HAS_STRING_VIEW
1578namespace {
1579std::size_t stringViewSize(std::string_view s) {
1580 return s.size();
1581}
1582
1583std::size_t stringPieceSize(StringPiece s) {
1584 return s.size();
1585}
1586
1587struct TrickyTarget {
1588 TrickyTarget(char const*, char const*) : which{1} {}
1589 TrickyTarget(char const*, std::size_t) : which{2} {}
1590 TrickyTarget(std::string_view) : which{3} {}
1591
1592 int which;
1593};
1594
1595struct TrickierTarget {
1596 TrickierTarget(std::deque<char>::const_iterator, std::size_t) : which{1} {}
1597 TrickierTarget(std::string_view) : which{2} {}
1598
1599 int which;
1600};
1601} // namespace
1602
1603TEST(StringPiece, StringViewConversion) {
1604 StringPiece piece("foo");
1605 std::string str("bar");
1606 MutableStringPiece mut(str.data(), str.size());
1607 std::string_view view("baz");
1608
1609 EXPECT_EQ(stringViewSize(piece), 3);
1610 EXPECT_EQ(stringViewSize(str), 3);
1611 EXPECT_EQ(stringViewSize(mut), 3);
1612 EXPECT_EQ(stringPieceSize(mut), 3);
1613 EXPECT_EQ(stringPieceSize(str), 3);
1614 EXPECT_EQ(stringPieceSize(view), 3);
1615
1616 view = mut;
1617 piece = view;
1618 EXPECT_EQ(piece[2], 'r');
1619 piece = "quux";
1620 view = piece;
1621 EXPECT_EQ(view.size(), 4);
1622
1623 TrickyTarget tt1(piece);
1624 EXPECT_EQ(tt1.which, 3);
1625 TrickyTarget tt2(view);
1626 EXPECT_EQ(tt2.which, 3);
1627
1628 std::deque<char> deq;
1629 deq.push_back('a');
1630 deq.push_back('b');
1631 deq.push_back('c');
1632 Range<std::deque<char>::const_iterator> deqRange{deq.begin(), deq.end()};
1633 TrickierTarget tt3(deqRange);
1634 EXPECT_EQ(tt3.which, 1);
1635}
1636
1637namespace {
1638
1639// Range with non-pod value type should not cause compile errors.
1640class NonPOD {
1641 public:
1642 NonPOD() {}
1643};
1644void test_func(Range<const NonPOD*>) {}
1645
1646} // anonymous namespace
1647
1648#endif
1649
1650namespace {
1651// Nested class should not cause compile errors due to incomplete parent
1652class Parent {
1653 struct Nested : Range<const Parent*> {};
1654};
1655} // namespace
1656