1 /*
2  * Copyright (C) 1996-2021 The Squid Software Foundation and contributors
3  *
4  * Squid software is distributed under GPLv2+ license and includes
5  * contributions from numerous individuals and organizations.
6  * Please see the COPYING and CONTRIBUTORS files for details.
7  */
8 
9 #include "squid.h"
10 #include "base/CharacterSet.h"
11 #include "sbuf/Algorithms.h"
12 #include "sbuf/SBuf.h"
13 #include "sbuf/Stream.h"
14 #include "tests/SBufFindTest.h"
15 #include "tests/testSBuf.h"
16 #include "unitTestMain.h"
17 
18 #include <iostream>
19 #include <stdexcept>
20 #include <unordered_map>
21 
22 CPPUNIT_TEST_SUITE_REGISTRATION( testSBuf );
23 
24 /* let this test link sanely */
25 #include "event.h"
26 #include "MemObject.h"
27 void
eventAdd(const char * name,EVH * func,void * arg,double when,int,bool cbdata)28 eventAdd(const char *name, EVH * func, void *arg, double when, int, bool cbdata)
29 {}
30 int64_t
endOffset() const31 MemObject::endOffset() const
32 { return 0; }
33 /* end of stubs */
34 
35 // test string
36 static char fox[]="The quick brown fox jumped over the lazy dog";
37 static char fox1[]="The quick brown fox ";
38 static char fox2[]="jumped over the lazy dog";
39 
40 // TEST: globals variables (default/empty and with contents) are
41 //  created outside and before any unit tests and memory subsystem
42 //  initialization. Check for correct constructor operation.
43 SBuf empty_sbuf;
44 SBuf literal("The quick brown fox jumped over the lazy dog");
45 
46 void
testSBufConstructDestruct()47 testSBuf::testSBufConstructDestruct()
48 {
49     /* NOTE: Do not initialize memory here because we need
50      * to test correct operation before and after Mem::Init
51      */
52 
53     // XXX: partial demo below of how to do constructor unit-test. use scope to ensure each test
54     // is working on local-scope variables constructed fresh for the test, and destructed when
55     // scope exists. use nested scopes to test destructor affects on copied data (MemBlob etc)
56 
57     // TEST: default constructor (implicit destructor non-crash test)
58     //  test accessors on empty SBuf.
59     {
60         SBuf s1;
61         CPPUNIT_ASSERT_EQUAL(0U,s1.length());
62         CPPUNIT_ASSERT_EQUAL(SBuf(""),s1);
63         CPPUNIT_ASSERT_EQUAL(empty_sbuf,s1);
64         CPPUNIT_ASSERT_EQUAL(0,strcmp("",s1.c_str()));
65     }
66 
67     // TEST: copy-construct NULL string (implicit destructor non-crash test)
68     {
69         SBuf s1(NULL);
70         CPPUNIT_ASSERT_EQUAL(0U,s1.length());
71         CPPUNIT_ASSERT_EQUAL(SBuf(""),s1);
72         CPPUNIT_ASSERT_EQUAL(empty_sbuf,s1);
73         CPPUNIT_ASSERT_EQUAL(0,strcmp("",s1.c_str()));
74     }
75 
76     // TEST: copy-construct empty string (implicit destructor non-crash test)
77     {
78         SBuf s1("");
79         CPPUNIT_ASSERT_EQUAL(0U,s1.length());
80         CPPUNIT_ASSERT_EQUAL(SBuf(""),s1);
81         CPPUNIT_ASSERT_EQUAL(empty_sbuf,s1);
82         CPPUNIT_ASSERT_EQUAL(0,strcmp("",s1.c_str()));
83     }
84 
85     // TEST: copy-construct from a SBuf
86     {
87         SBuf s1(empty_sbuf);
88         CPPUNIT_ASSERT_EQUAL(0U,s1.length());
89         CPPUNIT_ASSERT_EQUAL(SBuf(""),s1);
90         CPPUNIT_ASSERT_EQUAL(empty_sbuf,s1);
91         CPPUNIT_ASSERT_EQUAL(0,strcmp("",s1.c_str()));
92 
93         SBuf s5(literal);
94         CPPUNIT_ASSERT_EQUAL(literal,s5);
95         SBuf s6(fox);
96         CPPUNIT_ASSERT_EQUAL(literal,s6);
97         // XXX: other state checks. expected result of calling any state accessor on s4 ?
98     }
99 
100     // TEST: check that COW doesn't happen upon copy-construction
101     {
102         SBuf s1(empty_sbuf), s2(s1);
103         CPPUNIT_ASSERT_EQUAL(s1.rawContent(), s2.rawContent());
104         SBuf s3(literal), s4(literal);
105         CPPUNIT_ASSERT_EQUAL(s3.rawContent(), s4.rawContent());
106     }
107 
108     // TEST: sub-string copy
109     {
110         SBuf s1=SBuf(fox+4), s2(fox);
111         SBuf s3=s2.substr(4,s2.length()); //n is out-of-bounds
112         CPPUNIT_ASSERT_EQUAL(s1,s3);
113         SBuf s4=SBuf(fox,4);
114         s3=s2.substr(0,4);
115         CPPUNIT_ASSERT_EQUAL(s4,s3);
116     }
117 
118     // TEST: go via std::string adapter.
119     {
120         std::string str(fox);
121         SBuf s1(str);
122         CPPUNIT_ASSERT_EQUAL(literal,s1);
123     }
124 }
125 
126 void
testSBufConstructDestructAfterMemInit()127 testSBuf::testSBufConstructDestructAfterMemInit()
128 {
129     Mem::Init();
130     testSBufConstructDestruct();
131 }
132 
133 void
testEqualityTest()134 testSBuf::testEqualityTest()
135 {
136     SBuf s1(fox),s2(fox);
137     CPPUNIT_ASSERT_EQUAL(s1,s1); //self-equality
138     CPPUNIT_ASSERT_EQUAL(s1,s2); //same contents
139     s2.assign("The quick brown fox jumped over the lazy doe");
140     CPPUNIT_ASSERT(!(s1 == s2)); //same length, different contents
141     s2.assign("foo");
142     CPPUNIT_ASSERT(!(s1 == s2)); //different length and contents
143     CPPUNIT_ASSERT(s1 != s2);    //while we're ready, let's test inequality
144     s2.clear();
145     CPPUNIT_ASSERT(!(s1 == s2)); //null and not-null
146     CPPUNIT_ASSERT(s1 != s2);    //while we're ready, let's test inequality
147     s1.clear();
148     CPPUNIT_ASSERT_EQUAL(s1,s2); //null and null
149 }
150 
151 void
testAppendSBuf()152 testSBuf::testAppendSBuf()
153 {
154     const SBuf appendix(fox1);
155     const char * const rawAppendix = appendix.rawContent();
156 
157     // check whether the optimization that prevents copying when append()ing to
158     // default-constructed SBuf actually works
159     SBuf s0;
160     s0.append(appendix);
161     CPPUNIT_ASSERT_EQUAL(s0.rawContent(), appendix.rawContent());
162     CPPUNIT_ASSERT_EQUAL(s0, appendix);
163 
164     // paranoid: check that the above code can actually detect copies
165     SBuf s1(fox1);
166     s1.append(appendix);
167     CPPUNIT_ASSERT(s1.rawContent() != appendix.rawContent());
168     CPPUNIT_ASSERT(s1 != appendix);
169     CPPUNIT_ASSERT_EQUAL(rawAppendix, appendix.rawContent());
170 }
171 
172 void
testPrintf()173 testSBuf::testPrintf()
174 {
175     SBuf s1,s2;
176     s1.Printf("%s:%d:%03.3f","fox",10,12345.67);
177     s2.assign("fox:10:12345.670");
178     CPPUNIT_ASSERT_EQUAL(s1,s2);
179 }
180 
181 void
testAppendCString()182 testSBuf::testAppendCString()
183 {
184     SBuf s1(fox1);
185     s1.append(fox2);
186     CPPUNIT_ASSERT_EQUAL(s1,literal);
187 }
188 
189 void
testAppendStdString()190 testSBuf::testAppendStdString()
191 {
192     const char *alphabet="abcdefghijklmnopqrstuvwxyz";
193     {
194         SBuf alpha(alphabet), s;
195         s.append(alphabet,5).append(alphabet+5);
196         CPPUNIT_ASSERT_EQUAL(alpha,s);
197     }
198     {
199         SBuf s;
200         std::string control;
201         s.append(alphabet,5).append("\0",1).append(alphabet+6,SBuf::npos);
202         control.append(alphabet,5).append(1,'\0').append(alphabet,6,std::string::npos);
203         SBuf scontrol(control); // we need this to test the equality. sigh.
204         CPPUNIT_ASSERT_EQUAL(scontrol,s);
205     }
206     {
207         const char *alphazero="abcdefghijk\0mnopqrstuvwxyz";
208         SBuf s(alphazero,26);
209         std::string str(alphazero,26);
210         CPPUNIT_ASSERT_EQUAL(0,memcmp(str.data(),s.rawContent(),26));
211     }
212 }
213 
214 void
testAppendf()215 testSBuf::testAppendf()
216 {
217     SBuf s1,s2;
218     s1.appendf("%s:%d:%03.2f",fox,1234,1234.56);
219     s2.assign("The quick brown fox jumped over the lazy dog:1234:1234.56");
220     CPPUNIT_ASSERT_EQUAL(s2,s1);
221 }
222 
223 void
testDumpStats()224 testSBuf::testDumpStats()
225 {
226     SBuf::GetStats().dump(std::cout);
227     MemBlob::GetStats().dump(std::cout);
228     std::cout << "sizeof(SBuf): " << sizeof(SBuf) << std::endl;
229     std::cout << "sizeof(MemBlob): " << sizeof(MemBlob) << std::endl;
230 }
231 
232 void
testSubscriptOp()233 testSBuf::testSubscriptOp()
234 {
235     SBuf chg(literal);
236     CPPUNIT_ASSERT_EQUAL(chg[5],'u');
237     chg.setAt(5,'e');
238     CPPUNIT_ASSERT_EQUAL(literal[5],'u');
239     CPPUNIT_ASSERT_EQUAL(chg[5],'e');
240 }
241 
242 // note: can't use cppunit's CPPUNIT_TEST_EXCEPTION because TextException asserts, and
243 // so the test can't be properly completed.
244 void
testSubscriptOpFail()245 testSBuf::testSubscriptOpFail()
246 {
247     char c;
248     c=literal.at(literal.length()); //out of bounds by 1
249     //notreached
250     std::cout << c << std::endl;
251 }
252 
sign(int v)253 static int sign(int v)
254 {
255     if (v < 0)
256         return -1;
257     if (v>0)
258         return 1;
259     return 0;
260 }
261 
262 static void
testComparisonStdFull(const char * left,const char * right)263 testComparisonStdFull(const char *left, const char *right)
264 {
265     if (sign(strcmp(left, right)) != sign(SBuf(left).cmp(SBuf(right))))
266         std::cerr << std::endl << " cmp(SBuf) npos " << left << " ?= " << right << std::endl;
267     CPPUNIT_ASSERT_EQUAL(sign(strcmp(left, right)), sign(SBuf(left).cmp(SBuf(right))));
268 
269     if (sign(strcmp(left, right)) != sign(SBuf(left).cmp(right)))
270         std::cerr << std::endl << " cmp(char*) npos " << left << " ?= " << right << std::endl;
271     CPPUNIT_ASSERT_EQUAL(sign(strcmp(left, right)), sign(SBuf(left).cmp(right)));
272 
273     if (sign(strcasecmp(left, right)) != sign(SBuf(left).caseCmp(SBuf(right))))
274         std::cerr << std::endl << " caseCmp(SBuf) npos " << left << " ?= " << right << std::endl;
275     CPPUNIT_ASSERT_EQUAL(sign(strcasecmp(left, right)), sign(SBuf(left).caseCmp(SBuf(right))));
276 
277     if (sign(strcasecmp(left, right)) != sign(SBuf(left).caseCmp(right)))
278         std::cerr << std::endl << " caseCmp(char*) npos " << left << " ?= " << right << std::endl;
279     CPPUNIT_ASSERT_EQUAL(sign(strcasecmp(left, right)), sign(SBuf(left).caseCmp(right)));
280 }
281 
282 static void
testComparisonStdN(const char * left,const char * right,const size_t n)283 testComparisonStdN(const char *left, const char *right, const size_t n)
284 {
285     if (sign(strncmp(left, right, n)) != sign(SBuf(left).cmp(SBuf(right), n)))
286         std::cerr << std::endl << " cmp(SBuf) " << n << ' ' << left << " ?= " << right << std::endl;
287     CPPUNIT_ASSERT_EQUAL(sign(strncmp(left, right, n)), sign(SBuf(left).cmp(SBuf(right), n)));
288 
289     if (sign(strncmp(left, right, n)) != sign(SBuf(left).cmp(right, n)))
290         std::cerr << std::endl << " cmp(char*) " << n << ' ' << SBuf(left) << " ?= " << right << std::endl;
291     CPPUNIT_ASSERT_EQUAL(sign(strncmp(left, right, n)), sign(SBuf(left).cmp(right, n)));
292 
293     if (sign(strncasecmp(left, right, n)) != sign(SBuf(left).caseCmp(SBuf(right), n)))
294         std::cerr << std::endl << " caseCmp(SBuf) " << n << ' ' << left << " ?= " << right << std::endl;
295     CPPUNIT_ASSERT_EQUAL(sign(strncasecmp(left, right, n)), sign(SBuf(left).caseCmp(SBuf(right), n)));
296 
297     if (sign(strncasecmp(left, right, n)) != sign(SBuf(left).caseCmp(right, n)))
298         std::cerr << std::endl << " caseCmp(char*) " << n << ' ' << SBuf(left) << " ?= " << right << std::endl;
299     CPPUNIT_ASSERT_EQUAL(sign(strncasecmp(left, right, n)), sign(SBuf(left).caseCmp(right, n)));
300 }
301 
302 static void
testComparisonStdOneWay(const char * left,const char * right)303 testComparisonStdOneWay(const char *left, const char *right)
304 {
305     testComparisonStdFull(left, right);
306     const size_t maxN = 2 + min(strlen(left), strlen(right));
307     for (size_t n = 0; n <= maxN; ++n) {
308         testComparisonStdN(left, right, n);
309     }
310 }
311 
312 static void
testComparisonStd(const char * s1,const char * s2)313 testComparisonStd(const char *s1, const char *s2)
314 {
315     testComparisonStdOneWay(s1, s2);
316     testComparisonStdOneWay(s2, s1);
317 }
318 
319 void
testComparisons()320 testSBuf::testComparisons()
321 {
322     //same length
323     SBuf s1("foo"),s2("foe");
324     CPPUNIT_ASSERT(s1.cmp(s2)>0);
325     CPPUNIT_ASSERT(s1.caseCmp(s2)>0);
326     CPPUNIT_ASSERT(s2.cmp(s1)<0);
327     CPPUNIT_ASSERT_EQUAL(0,s1.cmp(s2,2));
328     CPPUNIT_ASSERT_EQUAL(0,s1.caseCmp(s2,2));
329     CPPUNIT_ASSERT(s1 > s2);
330     CPPUNIT_ASSERT(s2 < s1);
331     CPPUNIT_ASSERT_EQUAL(sign(s1.cmp(s2)),sign(strcmp(s1.c_str(),s2.c_str())));
332     //different lengths
333     s1.assign("foo");
334     s2.assign("foof");
335     CPPUNIT_ASSERT(s1.cmp(s2)<0);
336     CPPUNIT_ASSERT_EQUAL(sign(s1.cmp(s2)),sign(strcmp(s1.c_str(),s2.c_str())));
337     CPPUNIT_ASSERT(s1 < s2);
338     // specifying the max-length and overhanging size
339     CPPUNIT_ASSERT_EQUAL(1,SBuf("foolong").caseCmp(SBuf("foo"), 5));
340     // case-insensive comaprison
341     s1 = "foo";
342     s2 = "fOo";
343     CPPUNIT_ASSERT_EQUAL(0,s1.caseCmp(s2));
344     CPPUNIT_ASSERT_EQUAL(0,s1.caseCmp(s2,2));
345     // \0-clenliness test
346     s1.assign("f\0oo",4);
347     s2.assign("f\0Oo",4);
348     CPPUNIT_ASSERT(s1.cmp(s2) > 0);
349     CPPUNIT_ASSERT_EQUAL(0,s1.caseCmp(s2));
350     CPPUNIT_ASSERT_EQUAL(0,s1.caseCmp(s2,3));
351     CPPUNIT_ASSERT_EQUAL(0,s1.caseCmp(s2,2));
352     CPPUNIT_ASSERT_EQUAL(0,s1.cmp(s2,2));
353 
354     testComparisonStd("foo", "fooz");
355     testComparisonStd("foo", "foo");
356     testComparisonStd("foo", "f");
357     testComparisonStd("foo", "bar");
358 
359     testComparisonStd("foo", "FOOZ");
360     testComparisonStd("foo", "FOO");
361     testComparisonStd("foo", "F");
362 
363     testComparisonStdOneWay("", "");
364 
365     // rare case C-string input matching SBuf with N>strlen(s)
366     {
367         char *right = xstrdup("foo34567890123456789012345678");
368         SBuf left("fooZYXWVUTSRQPONMLKJIHGFEDCBA");
369         // is 3 bytes in length. NEVER more.
370         right[3] = '\0';
371         left.setAt(3, '\0');
372 
373         // pick another spot to truncate at if something goes horribly wrong.
374         right[14] = '\0';
375         left.setAt(14, '\0');
376 
377         const SBuf::size_type maxN = 20 + min(left.length(), static_cast<SBuf::size_type>(strlen(right)));
378         for (SBuf::size_type n = 0; n <= maxN; ++n) {
379             if (sign(strncmp(left.rawContent(), right, n)) != sign(left.cmp(right, n)) )
380                 std::cerr << std::endl << " cmp(char*) " << n << ' ' << left << " ?= " << right;
381             CPPUNIT_ASSERT_EQUAL(sign(strncmp(left.rawContent(), right, n)), sign(left.cmp(right, n)));
382             if (sign(strncasecmp(left.rawContent(), right, n)) != sign(left.caseCmp(right, n)))
383                 std::cerr << std::endl << " caseCmp(char*) " << n << ' ' << left << " ?= " << right;
384             CPPUNIT_ASSERT_EQUAL(sign(strncasecmp(left.rawContent(), right, n)), sign(left.caseCmp(right, n)));
385         }
386         xfree(right);
387     }
388 }
389 
390 void
testConsume()391 testSBuf::testConsume()
392 {
393     SBuf s1(literal),s2,s3;
394     s2=s1.consume(4);
395     s3.assign("The ");
396     CPPUNIT_ASSERT_EQUAL(s2,s3);
397     s3.assign("quick brown fox jumped over the lazy dog");
398     CPPUNIT_ASSERT_EQUAL(s1,s3);
399     s1.consume(40);
400     CPPUNIT_ASSERT_EQUAL(s1,SBuf());
401 }
402 
403 void
testRawContent()404 testSBuf::testRawContent()
405 {
406     SBuf s1(literal);
407     SBuf s2(s1);
408     s2.append("foo");
409     const char *foo;
410     foo = s1.rawContent();
411     CPPUNIT_ASSERT_EQUAL(0,strncmp(fox,foo,s1.length()));
412     foo = s1.c_str();
413     CPPUNIT_ASSERT(!strcmp(fox,foo));
414 }
415 
416 void
testRawSpace()417 testSBuf::testRawSpace()
418 {
419     SBuf s1(literal);
420     SBuf s2(fox1);
421     char *rb=s2.rawAppendStart(strlen(fox2)+1);
422     strcpy(rb,fox2);
423     s2.rawAppendFinish(rb, strlen(fox2));
424     CPPUNIT_ASSERT_EQUAL(s1,s2);
425 }
426 
427 void
testChop()428 testSBuf::testChop()
429 {
430     SBuf s1(literal),s2;
431     s1.chop(4,5);
432     s2.assign("quick");
433     CPPUNIT_ASSERT_EQUAL(s1,s2);
434     s1=literal;
435     s2.clear();
436     s1.chop(5,0);
437     CPPUNIT_ASSERT_EQUAL(s1,s2);
438     const char *alphabet="abcdefghijklmnopqrstuvwxyz";
439     SBuf a(alphabet);
440     std::string s(alphabet); // TODO
441     {   //regular chopping
442         SBuf b(a);
443         b.chop(3,3);
444         SBuf ref("def");
445         CPPUNIT_ASSERT_EQUAL(ref,b);
446     }
447     {   // chop at end
448         SBuf b(a);
449         b.chop(b.length()-3);
450         SBuf ref("xyz");
451         CPPUNIT_ASSERT_EQUAL(ref,b);
452     }
453     {   // chop at beginning
454         SBuf b(a);
455         b.chop(0,3);
456         SBuf ref("abc");
457         CPPUNIT_ASSERT_EQUAL(ref,b);
458     }
459     {   // chop to zero length
460         SBuf b(a);
461         b.chop(5,0);
462         SBuf ref("");
463         CPPUNIT_ASSERT_EQUAL(ref,b);
464     }
465     {   // chop beyond end (at npos)
466         SBuf b(a);
467         b.chop(SBuf::npos,4);
468         SBuf ref("");
469         CPPUNIT_ASSERT_EQUAL(ref,b);
470     }
471     {   // chop beyond end
472         SBuf b(a);
473         b.chop(b.length()+2,4);
474         SBuf ref("");
475         CPPUNIT_ASSERT_EQUAL(ref,b);
476     }
477     {   // null-chop
478         SBuf b(a);
479         b.chop(0,b.length());
480         SBuf ref(a);
481         CPPUNIT_ASSERT_EQUAL(ref,b);
482     }
483     {   // overflow chopped area
484         SBuf b(a);
485         b.chop(b.length()-3,b.length());
486         SBuf ref("xyz");
487         CPPUNIT_ASSERT_EQUAL(ref,b);
488     }
489 }
490 
491 void
testChomp()492 testSBuf::testChomp()
493 {
494     SBuf s1("complete string");
495     SBuf s2(s1);
496     s2.trim(SBuf(" ,"));
497     CPPUNIT_ASSERT_EQUAL(s1,s2);
498     s2.assign(" complete string ,");
499     s2.trim(SBuf(" ,"));
500     CPPUNIT_ASSERT_EQUAL(s1,s2);
501     s1.assign(", complete string ,");
502     s2=s1;
503     s2.trim(SBuf(" "));
504     CPPUNIT_ASSERT_EQUAL(s1,s2);
505 }
506 
507 // inspired by SBufFindTest; to be expanded.
508 class SBufSubstrAutoTest
509 {
510     SBuf fullString, sb;
511     std::string fullReference, str;
512 public:
performEqualityTest()513     void performEqualityTest() {
514         SBuf ref(str);
515         CPPUNIT_ASSERT_EQUAL(ref,sb);
516     }
SBufSubstrAutoTest()517     SBufSubstrAutoTest() : fullString(fox), fullReference(fox) {
518         for (int offset=fullString.length()-1; offset >= 0; --offset ) {
519             for (int length=fullString.length()-1-offset; length >= 0; --length) {
520                 sb=fullString.substr(offset,length);
521                 str=fullReference.substr(offset,length);
522                 performEqualityTest();
523             }
524         }
525     }
526 };
527 
528 void
testSubstr()529 testSBuf::testSubstr()
530 {
531     SBuf s1(literal),s2,s3;
532     s2=s1.substr(4,5);
533     s3.assign("quick");
534     CPPUNIT_ASSERT_EQUAL(s2,s3);
535     s1.chop(4,5);
536     CPPUNIT_ASSERT_EQUAL(s1,s2);
537     SBufSubstrAutoTest sat; // work done in the constructor
538 }
539 
540 void
testFindChar()541 testSBuf::testFindChar()
542 {
543     const char *alphabet="abcdefghijklmnopqrstuvwxyz";
544     SBuf s1(alphabet);
545     SBuf::size_type idx;
546     SBuf::size_type nposResult=SBuf::npos;
547 
548     // FORWARD SEARCH
549     // needle in haystack
550     idx=s1.find('d');
551     CPPUNIT_ASSERT_EQUAL(3U,idx);
552     CPPUNIT_ASSERT_EQUAL('d',s1[idx]);
553 
554     // needle not present in haystack
555     idx=s1.find(' '); //fails
556     CPPUNIT_ASSERT_EQUAL(nposResult,idx);
557 
558     // search in portion
559     idx=s1.find('e',3U);
560     CPPUNIT_ASSERT_EQUAL(4U,idx);
561 
562     // char not in searched portion
563     idx=s1.find('e',5U);
564     CPPUNIT_ASSERT_EQUAL(nposResult,idx);
565 
566     // invalid start position
567     idx=s1.find('d',SBuf::npos);
568     CPPUNIT_ASSERT_EQUAL(nposResult,idx);
569 
570     // search outside of haystack
571     idx=s1.find('d',s1.length()+1);
572     CPPUNIT_ASSERT_EQUAL(nposResult,idx);
573 
574     // REVERSE SEARCH
575     // needle in haystack
576     idx=s1.rfind('d');
577     CPPUNIT_ASSERT_EQUAL(3U, idx);
578     CPPUNIT_ASSERT_EQUAL('d', s1[idx]);
579 
580     // needle not present in haystack
581     idx=s1.rfind(' '); //fails
582     CPPUNIT_ASSERT_EQUAL(nposResult,idx);
583 
584     // search in portion
585     idx=s1.rfind('e',5);
586     CPPUNIT_ASSERT_EQUAL(4U,idx);
587 
588     // char not in searched portion
589     idx=s1.rfind('e',3);
590     CPPUNIT_ASSERT_EQUAL(nposResult,idx);
591 
592     // overlong haystack specification
593     idx=s1.rfind('d',s1.length()+1);
594     CPPUNIT_ASSERT_EQUAL(3U,idx);
595 }
596 
597 void
testFindSBuf()598 testSBuf::testFindSBuf()
599 {
600     const char *alphabet="abcdefghijklmnopqrstuvwxyz";
601     SBuf haystack(alphabet);
602     SBuf::size_type idx;
603     SBuf::size_type nposResult=SBuf::npos;
604 
605     // FORWARD search
606     // needle in haystack
607     idx = haystack.find(SBuf("def"));
608     CPPUNIT_ASSERT_EQUAL(3U,idx);
609 
610     idx = haystack.find(SBuf("xyz"));
611     CPPUNIT_ASSERT_EQUAL(23U,idx);
612 
613     // needle not in haystack, no initial char match
614     idx = haystack.find(SBuf(" eq"));
615     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
616 
617     // needle not in haystack, initial sequence match
618     idx = haystack.find(SBuf("deg"));
619     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
620 
621     // needle past end of haystack
622     idx = haystack.find(SBuf("xyz1"));
623     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
624 
625     // search in portion: needle not in searched part
626     idx = haystack.find(SBuf("def"),7);
627     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
628 
629     // search in portion: overhang
630     idx = haystack.find(SBuf("def"),4);
631     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
632 
633     // invalid start position
634     idx = haystack.find(SBuf("def"),SBuf::npos);
635     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
636 
637     // needle bigger than haystack
638     idx = SBuf("def").find(haystack);
639     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
640 
641     // search in a double-matching haystack
642     {
643         SBuf h2=haystack;
644         h2.append(haystack);
645 
646         idx = h2.find(SBuf("def"));
647         CPPUNIT_ASSERT_EQUAL(3U,idx);
648 
649         idx = h2.find(SBuf("xyzab"));
650         CPPUNIT_ASSERT_EQUAL(23U,idx);
651     }
652 
653     // REVERSE search
654     // needle in haystack
655     idx = haystack.rfind(SBuf("def"));
656     CPPUNIT_ASSERT_EQUAL(3U,idx);
657 
658     idx = haystack.rfind(SBuf("xyz"));
659     CPPUNIT_ASSERT_EQUAL(23U,idx);
660 
661     // needle not in haystack, no initial char match
662     idx = haystack.rfind(SBuf(" eq"));
663     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
664 
665     // needle not in haystack, initial sequence match
666     idx = haystack.rfind(SBuf("deg"));
667     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
668 
669     // needle past end of haystack
670     idx = haystack.rfind(SBuf("xyz1"));
671     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
672 
673     // search in portion: needle in searched part
674     idx = haystack.rfind(SBuf("def"),7);
675     CPPUNIT_ASSERT_EQUAL(3U, idx);
676 
677     // search in portion: needle not in searched part
678     idx = haystack.rfind(SBuf("mno"),3);
679     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
680 
681     // search in portion: overhang
682     idx = haystack.rfind(SBuf("def"),4);
683     CPPUNIT_ASSERT_EQUAL(3U, idx);
684 
685     // npos start position
686     idx = haystack.rfind(SBuf("def"),SBuf::npos);
687     CPPUNIT_ASSERT_EQUAL(3U, idx);
688 
689     // needle bigger than haystack
690     idx = SBuf("def").rfind(haystack);
691     CPPUNIT_ASSERT_EQUAL(nposResult, idx);
692 
693     // search in a double-matching haystack
694     {
695         SBuf h2=haystack;
696         h2.append(haystack);
697 
698         idx = h2.rfind(SBuf("def"));
699         CPPUNIT_ASSERT_EQUAL(29U,idx);
700 
701         idx = h2.find(SBuf("xyzab"));
702         CPPUNIT_ASSERT_EQUAL(23U,idx);
703     }
704 }
705 
706 void
testRFindChar()707 testSBuf::testRFindChar()
708 {
709     SBuf s1(literal);
710     SBuf::size_type idx;
711     idx=s1.rfind(' ');
712     CPPUNIT_ASSERT_EQUAL(40U,idx);
713     CPPUNIT_ASSERT_EQUAL(' ',s1[idx]);
714 }
715 
716 void
testRFindSBuf()717 testSBuf::testRFindSBuf()
718 {
719     SBuf haystack(literal),afox("fox");
720     SBuf goobar("goobar");
721     SBuf::size_type idx;
722 
723     // corner case: search for a zero-length SBuf
724     idx=haystack.rfind(SBuf(""));
725     CPPUNIT_ASSERT_EQUAL(haystack.length(),idx);
726 
727     // corner case: search for a needle longer than the haystack
728     idx=afox.rfind(SBuf("     "));
729     CPPUNIT_ASSERT_EQUAL(SBuf::npos,idx);
730 
731     idx=haystack.rfind(SBuf("fox"));
732     CPPUNIT_ASSERT_EQUAL(16U,idx);
733 
734     // needle not found, no match for first char
735     idx=goobar.rfind(SBuf("foo"));
736     CPPUNIT_ASSERT_EQUAL(SBuf::npos,idx);
737 
738     // needle not found, match for first char but no match for SBuf
739     idx=haystack.rfind(SBuf("foe"));
740     CPPUNIT_ASSERT_EQUAL(SBuf::npos,idx);
741 
742     SBuf g("g"); //match at the last char
743     idx=haystack.rfind(g);
744     CPPUNIT_ASSERT_EQUAL(43U,idx);
745     CPPUNIT_ASSERT_EQUAL('g',haystack[idx]);
746 
747     idx=haystack.rfind(SBuf("The"));
748     CPPUNIT_ASSERT_EQUAL(0U,idx);
749 
750     haystack.append("The");
751     idx=haystack.rfind(SBuf("The"));
752     CPPUNIT_ASSERT_EQUAL(44U,idx);
753 
754     //partial match
755     haystack="The quick brown fox";
756     SBuf needle("foxy lady");
757     idx=haystack.rfind(needle);
758     CPPUNIT_ASSERT_EQUAL(SBuf::npos,idx);
759 }
760 
761 void
testSBufLength()762 testSBuf::testSBufLength()
763 {
764     SBuf s(fox);
765     CPPUNIT_ASSERT_EQUAL(strlen(fox),(size_t)s.length());
766 }
767 
768 void
testCopy()769 testSBuf::testCopy()
770 {
771     char buf[40]; //shorter than literal()
772     SBuf s(fox1),s2;
773     CPPUNIT_ASSERT_EQUAL(s.length(),s.copy(buf,40));
774     CPPUNIT_ASSERT_EQUAL(0,strncmp(s.rawContent(),buf,s.length()));
775     s=literal;
776     CPPUNIT_ASSERT_EQUAL(40U,s.copy(buf,40));
777     s2.assign(buf,40);
778     s.chop(0,40);
779     CPPUNIT_ASSERT_EQUAL(s2,s);
780 }
781 
782 void
testStringOps()783 testSBuf::testStringOps()
784 {
785     SBuf sng(ToLower(literal)),
786          ref("the quick brown fox jumped over the lazy dog");
787     CPPUNIT_ASSERT_EQUAL(ref,sng);
788     sng=literal;
789     CPPUNIT_ASSERT_EQUAL(0,sng.compare(ref,caseInsensitive));
790     // max-size comparison
791     CPPUNIT_ASSERT_EQUAL(0,ref.compare(SBuf("THE"),caseInsensitive,3));
792     CPPUNIT_ASSERT_EQUAL(1,ref.compare(SBuf("THE"),caseInsensitive,6));
793     CPPUNIT_ASSERT_EQUAL(0,SBuf("the").compare(SBuf("THE"),caseInsensitive,6));
794 }
795 
796 void
testGrow()797 testSBuf::testGrow()
798 {
799     SBuf t;
800     t.assign("foo");
801     const char *ref=t.rawContent();
802     t.reserveCapacity(10240);
803     const char *match=t.rawContent();
804     CPPUNIT_ASSERT(match!=ref);
805     ref=match;
806     t.append(literal).append(literal).append(literal).append(literal).append(literal);
807     t.append(t).append(t).append(t).append(t).append(t);
808     CPPUNIT_ASSERT_EQUAL(ref,match);
809 }
810 
811 void
testReserve()812 testSBuf::testReserve()
813 {
814     SBufReservationRequirements requirements;
815     // use unusual numbers to ensure we do not hit a lucky boundary situation
816     requirements.minSpace = 10;
817     requirements.idealSpace = 82;
818     requirements.maxCapacity = 259;
819     requirements.allowShared = true;
820 
821     // for each possible starting buffer length within the capacity
822     for (SBuf::size_type startLength = 0; startLength <= requirements.maxCapacity; ++startLength) {
823         std::cerr << ".";
824         SBuf b;
825         b.reserveCapacity(startLength);
826         CPPUNIT_ASSERT_EQUAL(b.length(), static_cast<unsigned int>(0));
827         CPPUNIT_ASSERT_EQUAL(b.spaceSize(), startLength);
828 
829         // check that it never grows outside capacity.
830         // do 5 excess cycles to check that.
831         for (SBuf::size_type filled = 0; filled < requirements.maxCapacity +5; ++filled) {
832             CPPUNIT_ASSERT_EQUAL(b.length(), min(filled, requirements.maxCapacity));
833             auto x = b.reserve(requirements);
834             // the amount of space advertized must not cause users to exceed capacity
835             CPPUNIT_ASSERT(x <= requirements.maxCapacity - filled);
836             CPPUNIT_ASSERT(b.spaceSize() <= requirements.maxCapacity - filled);
837             // the total size of buffer must not cause users to exceed capacity
838             CPPUNIT_ASSERT(b.length() + b.spaceSize() <= requirements.maxCapacity);
839             if (x > 0)
840                 b.append('X');
841         }
842     }
843 
844     // the minimal space requirement should overwrite idealSpace preferences
845     requirements.minSpace = 10;
846     for (const int delta: {-1,0,+1}) {
847         requirements.idealSpace = requirements.minSpace + delta;
848         SBuf buffer;
849         buffer.reserve(requirements);
850         CPPUNIT_ASSERT(buffer.spaceSize() >= requirements.minSpace);
851     }
852 }
853 
854 void
testStartsWith()855 testSBuf::testStartsWith()
856 {
857     static SBuf casebuf("THE QUICK");
858     CPPUNIT_ASSERT(literal.startsWith(SBuf(fox1)));
859     CPPUNIT_ASSERT(!SBuf("The quick brown").startsWith(SBuf(fox1))); //too short
860     CPPUNIT_ASSERT(!literal.startsWith(SBuf(fox2))); //different contents
861 
862     // case-insensitive checks
863     CPPUNIT_ASSERT(literal.startsWith(casebuf,caseInsensitive));
864     casebuf=ToUpper(SBuf(fox1));
865     CPPUNIT_ASSERT(literal.startsWith(casebuf,caseInsensitive));
866     CPPUNIT_ASSERT(literal.startsWith(SBuf(fox1),caseInsensitive));
867     casebuf = "tha quick";
868     CPPUNIT_ASSERT_EQUAL(false,literal.startsWith(casebuf,caseInsensitive));
869 }
870 
871 void
testSBufStream()872 testSBuf::testSBufStream()
873 {
874     SBuf b("const.string, int 10 and a float 10.5");
875     SBufStream ss;
876     ss << "const.string, int " << 10 << " and a float " << 10.5;
877     SBuf o=ss.buf();
878     CPPUNIT_ASSERT_EQUAL(b,o);
879     ss.clearBuf();
880     o=ss.buf();
881     CPPUNIT_ASSERT_EQUAL(SBuf(),o);
882     SBuf f1(fox1);
883     SBufStream ss2(f1);
884     ss2 << fox2;
885     CPPUNIT_ASSERT_EQUAL(ss2.buf(),literal);
886     CPPUNIT_ASSERT_EQUAL(f1,SBuf(fox1));
887 }
888 
889 void
testFindFirstOf()890 testSBuf::testFindFirstOf()
891 {
892     SBuf haystack(literal);
893     SBuf::size_type idx;
894 
895     // not found
896     idx=haystack.findFirstOf(CharacterSet("t1","ADHRWYP"));
897     CPPUNIT_ASSERT_EQUAL(SBuf::npos,idx);
898 
899     // found at beginning
900     idx=haystack.findFirstOf(CharacterSet("t2","THANDF"));
901     CPPUNIT_ASSERT_EQUAL(0U,idx);
902 
903     //found at end of haystack
904     idx=haystack.findFirstOf(CharacterSet("t3","QWERYVg"));
905     CPPUNIT_ASSERT_EQUAL(haystack.length()-1,idx);
906 
907     //found in the middle of haystack
908     idx=haystack.findFirstOf(CharacterSet("t4","QWERqYV"));
909     CPPUNIT_ASSERT_EQUAL(4U,idx);
910 }
911 
912 void
testFindFirstNotOf()913 testSBuf::testFindFirstNotOf()
914 {
915     SBuf haystack(literal);
916     SBuf::size_type idx;
917 
918     // all chars from the set
919     idx=haystack.findFirstNotOf(CharacterSet("t1",literal.c_str()));
920     CPPUNIT_ASSERT_EQUAL(SBuf::npos,idx);
921 
922     // found at beginning
923     idx=haystack.findFirstNotOf(CharacterSet("t2","a"));
924     CPPUNIT_ASSERT_EQUAL(0U,idx);
925 
926     //found at end of haystack
927     idx=haystack.findFirstNotOf(CharacterSet("t3",literal.substr(0,literal.length()-1).c_str()));
928     CPPUNIT_ASSERT_EQUAL(haystack.length()-1,idx);
929 
930     //found in the middle of haystack
931     idx=haystack.findFirstNotOf(CharacterSet("t4","The"));
932     CPPUNIT_ASSERT_EQUAL(3U,idx);
933 }
934 
935 void
testAutoFind()936 testSBuf::testAutoFind()
937 {
938     SBufFindTest test;
939     test.run();
940 }
941 
942 void
testStdStringOps()943 testSBuf::testStdStringOps()
944 {
945     const char *alphabet="abcdefghijklmnopqrstuvwxyz";
946     std::string astr(alphabet);
947     SBuf sb(alphabet);
948     CPPUNIT_ASSERT_EQUAL(astr,sb.toStdString());
949 }
950 
951 void
testIterators()952 testSBuf::testIterators()
953 {
954     SBuf text("foo"), text2("foo");
955     CPPUNIT_ASSERT(text.begin() == text.begin());
956     CPPUNIT_ASSERT(text.begin() != text.end());
957     CPPUNIT_ASSERT(text.begin() != text2.begin());
958     {
959         auto i = text.begin();
960         auto e = text.end();
961         CPPUNIT_ASSERT_EQUAL('f', *i);
962         CPPUNIT_ASSERT(i != e);
963         ++i;
964         CPPUNIT_ASSERT_EQUAL('o', *i);
965         CPPUNIT_ASSERT(i != e);
966         ++i;
967         CPPUNIT_ASSERT_EQUAL('o', *i);
968         CPPUNIT_ASSERT(i != e);
969         ++i;
970         CPPUNIT_ASSERT(i == e);
971     }
972     {
973         auto i = text.rbegin();
974         auto e = text.rend();
975         CPPUNIT_ASSERT_EQUAL('o', *i);
976         CPPUNIT_ASSERT(i != e);
977         ++i;
978         CPPUNIT_ASSERT_EQUAL('o', *i);
979         CPPUNIT_ASSERT(i != e);
980         ++i;
981         CPPUNIT_ASSERT_EQUAL('f', *i);
982         CPPUNIT_ASSERT(i != e);
983         ++i;
984         CPPUNIT_ASSERT(i == e);
985     }
986 }
987 
988 void
testSBufHash()989 testSBuf::testSBufHash()
990 {
991     // same SBuf must have same hash
992     auto hasher=std::hash<SBuf>();
993     CPPUNIT_ASSERT_EQUAL(hasher(literal),hasher(literal));
994 
995     // same content must have same hash
996     CPPUNIT_ASSERT_EQUAL(hasher(literal),hasher(SBuf(fox)));
997     CPPUNIT_ASSERT_EQUAL(hasher(SBuf(fox)),hasher(SBuf(fox)));
998 
999     //differen content should have different hash
1000     CPPUNIT_ASSERT(hasher(SBuf(fox)) != hasher(SBuf(fox1)));
1001 
1002     {
1003         std::unordered_map<SBuf, int> um;
1004         um[SBuf("one")] = 1;
1005         um[SBuf("two")] = 2;
1006 
1007         auto i = um.find(SBuf("one"));
1008         CPPUNIT_ASSERT(i != um.end());
1009         CPPUNIT_ASSERT(i->second == 1);
1010 
1011         i = um.find(SBuf("eleventy"));
1012         CPPUNIT_ASSERT(i == um.end());
1013     }
1014 }
1015 
1016