2 * Copyright (C) 1996-2020 The Squid Software Foundation and contributors
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.
10 #include "base/CharacterSet.h"
11 #include "tests/SBufFindTest.h"
13 #include <cppunit/extensions/HelperMacros.h>
14 #include <cppunit/Message.h>
18 /* TODO: The whole SBufFindTest class is currently implemented as a single
19 CppUnit test case (because we do not want to register and report every one
20 of the thousands of generated test cases). Is there a better way to
21 integrate with CppUnit?
24 SBufFindTest::SBufFindTest():
25 caseLimit(std::numeric_limits
<int>::max()),
26 errorLimit(std::numeric_limits
<int>::max()),
30 thePlacement(placeEof
),
48 for (SBuf::size_type hayLen
= 0U; hayLen
<= maxHayLength
; nextLen(hayLen
, maxHayLength
)) {
49 const SBuf cleanHay
= RandomSBuf(hayLen
);
51 const SBuf::size_type maxNeedleLen
= hayLen
+ 10;
52 for (SBuf::size_type needleLen
= 0U; needleLen
<= maxNeedleLen
; nextLen(needleLen
, maxNeedleLen
)) {
53 theSBufNeedle
= RandomSBuf(needleLen
);
55 for (int i
= 0; i
< placeEof
; i
++) {
56 thePlacement
= Placement(i
);
57 placeNeedle(cleanHay
);
59 const SBuf::size_type maxArg
=
60 max(theSBufHay
.length(), theSBufNeedle
.length()) + 10;
61 for (thePos
= 0; thePos
<= maxArg
; nextLen(thePos
, maxArg
))
64 // the special npos value is not tested as the behavior is
65 // different from std::string (where the behavior is undefined)
66 // It is ad-hoc tested in testSBuf instead
67 //thePos = SBuf::npos;
74 std::cerr
<< "Generated SBuf test cases: " << caseCount
<< std::endl
;
75 std::cerr
<< "\tfailed cases: " << errorCount
<< std::endl
;
76 std::cerr
<< "\treported cases: " << reportCount
<< std::endl
;
77 std::cerr
<< "Asserting because some cases failed..." << std::endl
;
78 CPPUNIT_ASSERT(!SBufFindTest::errorCount
);
82 /// tests SBuf::find(string needle)
84 SBufFindTest::testFindDefs()
86 theFindString
= theBareNeedlePos
= theStringHay
.find(theStringNeedle
);
87 theFindSBuf
= theSBufHay
.find(theSBufNeedle
);
91 /// tests SBuf::rfind(string needle)
93 SBufFindTest::testRFindDefs()
95 theFindString
= theBareNeedlePos
= theStringHay
.rfind(theStringNeedle
);
96 theFindSBuf
= theSBufHay
.rfind(theSBufNeedle
);
97 checkResults("rfind");
100 /// tests SBuf::find(string needle, pos)
102 SBufFindTest::testFind()
104 theFindString
= theStringHay
.find(theStringNeedle
, thePos
);
105 theBareNeedlePos
= theStringHay
.find(theStringNeedle
);
106 theFindSBuf
= theSBufHay
.find(theSBufNeedle
, thePos
);
107 checkResults("find");
110 /// tests SBuf::findFirstOf(string needle, pos)
112 SBufFindTest::testFindFirstOf()
114 theFindString
= theStringHay
.find_first_of(theStringNeedle
, thePos
);
115 theBareNeedlePos
= theStringHay
.find_first_of(theStringNeedle
);
116 theFindSBuf
= theSBufHay
.findFirstOf(CharacterSet("cs",theSBufNeedle
.c_str()), thePos
);
117 checkResults("find_first_of");
120 /// tests SBuf::rfind(string needle, pos)
122 SBufFindTest::testRFind()
124 theFindString
= theStringHay
.rfind(theStringNeedle
, thePos
);
125 theBareNeedlePos
= theStringHay
.rfind(theStringNeedle
);
126 theFindSBuf
= theSBufHay
.rfind(theSBufNeedle
, thePos
);
127 checkResults("rfind");
130 /// tests SBuf::find(char needle)
132 SBufFindTest::testFindCharDefs()
134 const char c
= theStringNeedle
[0];
135 theFindString
= theBareNeedlePos
= theStringHay
.find(c
);
136 theFindSBuf
= theSBufHay
.find(c
);
137 checkResults("find");
140 /// tests SBuf::find(char needle, pos)
142 SBufFindTest::testFindChar()
144 const char c
= theStringNeedle
[0];
145 theFindString
= theStringHay
.find(c
, thePos
);
146 theBareNeedlePos
= theStringHay
.find(c
);
147 theFindSBuf
= theSBufHay
.find(c
, thePos
);
148 checkResults("find");
151 /// tests SBuf::rfind(char needle)
153 SBufFindTest::testRFindCharDefs()
155 const char c
= theStringNeedle
[0];
156 theFindString
= theBareNeedlePos
= theStringHay
.rfind(c
);
157 theFindSBuf
= theSBufHay
.rfind(c
);
158 checkResults("rfind");
161 /// tests SBuf::rfind(char needle, pos)
163 SBufFindTest::testRFindChar()
165 const char c
= theStringNeedle
[0];
166 theFindString
= theStringHay
.rfind(c
, thePos
);
167 theBareNeedlePos
= theStringHay
.rfind(c
);
168 theFindSBuf
= theSBufHay
.rfind(c
, thePos
);
169 checkResults("rfind");
172 /// whether the last SBuf and std::string find() results are the same
174 SBufFindTest::resultsMatch() const
176 // this method is needed because SBuf and std::string use different
177 // size_types (and npos values); comparing the result values directly
178 // would lead to bugs
180 if (theFindString
== std::string::npos
&& theFindSBuf
== SBuf::npos
)
181 return true; // both npos
183 // now safe to cast a non-negative SBuf result
184 return theFindString
== static_cast<std::string::size_type
>(theFindSBuf
);
187 /// called at the end of test case to update state, detect and report failures
189 SBufFindTest::checkResults(const char *method
)
193 handleFailure(method
);
196 /// helper function to convert "printable" Type to std::string
197 template<typename Type
>
199 AnyToString(const Type
&value
)
201 std::stringstream sbuf
;
207 /// helper function to convert SBuf position to a human-friendly string
209 PosToString(const SBuf::size_type pos
)
211 return pos
== SBuf::npos
? std::string("npos") : AnyToString(pos
);
215 /// helper function to convert std::string position to a human-friendly string
217 PosToString(const std::string::size_type pos
)
219 return pos
== std::string::npos
? std::string("npos") : AnyToString(pos
);
222 /// tests each supported SBuf::*find() method using generated hay, needle, pos
224 SBufFindTest::testAllMethods()
226 theStringHay
= std::string(theSBufHay
.rawContent(), theSBufHay
.length());
227 theStringNeedle
= std::string(theSBufNeedle
.rawContent(), theSBufNeedle
.length());
228 theBareNeedlePos
= std::string::npos
;
229 const std::string reportPos
= PosToString(thePos
);
231 // always test string search
233 theReportQuote
= '"';
234 theReportNeedle
= theStringNeedle
;
240 theReportPos
= reportPos
;
246 // if possible, test char search
247 if (!theStringNeedle
.empty()) {
248 theReportQuote
= '\'';
249 theReportNeedle
= theStringNeedle
[0];
255 theReportPos
= reportPos
;
261 /// helper function to format a length-based key (part of case category string)
263 lengthKey(const std::string
&str
)
265 if (str
.length() == 0)
267 if (str
.length() == 1)
272 /// formats position key (part of the case category string)
274 SBufFindTest::posKey() const
276 // the search position does not matter if needle is not in hay
277 if (theBareNeedlePos
== std::string::npos
)
278 return std::string();
280 if (thePos
== SBuf::npos
)
283 if (thePos
< theBareNeedlePos
)
284 return ",posL"; // to the Left of the needle
286 if (thePos
== theBareNeedlePos
)
287 return ",posB"; // Beginning of the needle
289 if (thePos
< theBareNeedlePos
+ theStringNeedle
.length())
290 return ",posM"; // in the Middle of the needle
292 if (thePos
== theBareNeedlePos
+ theStringNeedle
.length())
293 return ",posE"; // at the End of the needle
295 if (thePos
< theStringHay
.length())
296 return ",posR"; // to the Right of the needle
298 return ",posP"; // past the hay
301 /// formats placement key (part of the case category string)
303 SBufFindTest::placementKey() const
305 // Ignore thePlacement because theBareNeedlePos covers it better: we may
306 // try to place the needle somewhere, but hay limits the actual placement.
308 // the placent does not matter if needle is not in hay
309 if (theBareNeedlePos
== std::string::npos
)
310 return std::string();
312 if (theBareNeedlePos
== 0)
313 return "@B"; // at the beggining of the hay string
314 if (theBareNeedlePos
== theStringHay
.length()-theStringNeedle
.length())
315 return "@E"; // at the end of the hay string
316 return "@M"; // in the "middle" of the hay string
319 /// called when a test case fails; counts and possibly reports the failure
321 SBufFindTest::handleFailure(const char *method
)
323 // line break after "........." printed for previous tests
325 std::cerr
<< std::endl
;
329 if (errorCount
> errorLimit
) {
330 std::cerr
<< "Will stop generating SBuf test cases because the " <<
331 "number of failed ones is over the limit: " << errorCount
<<
332 " (after " << caseCount
<< " test cases)" << std::endl
;
333 CPPUNIT_ASSERT(errorCount
<= errorLimit
);
337 // format test case category; category allows us to hush failure reports
338 // for already seen categories with failed cases (to reduce output noise)
339 std::string category
= "hay" + lengthKey(theStringHay
) +
341 if (theReportQuote
== '"')
342 category
+= "needle" + lengthKey(theStringNeedle
);
345 category
+= placementKey();
346 category
+= posKey();
350 if (failedCats
.find(category
) != failedCats
.end())
351 return; // do not report another similar test case failure
352 failedCats
.insert(category
);
355 std::string reportPos
= theReportPos
;
356 if (!reportPos
.empty())
357 reportPos
= ", " + reportPos
;
359 std::cerr
<< "case" << caseCount
<< ": " <<
360 "SBuf(\"" << theStringHay
<< "\")." << method
<<
361 "(" << theReportQuote
<< theReportNeedle
<< theReportQuote
<<
362 reportPos
<< ") returns " << PosToString(theFindSBuf
) <<
363 " instead of " << PosToString(theFindString
) <<
365 " std::string(\"" << theStringHay
<< "\")." << method
<<
366 "(" << theReportQuote
<< theReportNeedle
<< theReportQuote
<<
367 reportPos
<< ") returns " << PosToString(theFindString
) <<
369 " category: " << category
<< std::endl
;
374 /// generates a random string of the specified length
376 SBufFindTest::RandomSBuf(const int length
)
378 static const char characters
[] =
380 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
381 "abcdefghijklomnpqrstuvwxyz";
383 static std::mt19937
mt(time(0));
385 // sizeof() counts the terminating zero at the end of characters
386 // and the distribution is an 'inclusive' value range, so -2
387 // TODO: add \0 character (needs reporting adjustments to print it as \0)
388 static xuniform_int_distribution
<uint8_t> dist(0, sizeof(characters
)-2);
391 buf
.reserveCapacity(length
);
392 for (int i
= 0; i
< length
; ++i
)
393 buf
.append(characters
[dist(mt
)]);
397 /// increments len to quickly cover [0, max] range, slowing down in risky areas
398 /// jumps to max+1 if caseLimit is reached
400 SBufFindTest::nextLen(SBuf::size_type
&len
, const SBuf::size_type max
)
404 if (caseCount
>= caseLimit
)
405 len
= max
+1; // avoid future test cases
407 ++len
; // move slowly at the beginning of the [0,max] range
408 else if (len
>= max
- 10)
409 ++len
; // move slowly at the end of the [0,max] range
411 // move fast in the middle of the [0,max] range
414 // but do not overshoot the interesting area at the end of the range
420 /// Places the needle into the hay using cleanHay as a starting point.
422 SBufFindTest::placeNeedle(const SBuf
&cleanHay
)
424 // For simplicity, we do not overwrite clean hay characters but use them as
425 // needle suffix and/or prefix. Should not matter since hay length varies?
427 // TODO: support two needles per hay (explicitly)
428 // TODO: better handle cases where clean hay already contains needle
429 switch (thePlacement
) {
431 theSBufHay
.assign(theSBufNeedle
).append(cleanHay
);
435 const SBuf firstHalf
= cleanHay
.substr(0, cleanHay
.length()/2);
436 const SBuf secondHalf
= cleanHay
.substr(cleanHay
.length()/2);
437 theSBufHay
.assign(firstHalf
).append(theSBufNeedle
).append(secondHalf
);
442 theSBufHay
.assign(cleanHay
).append(theSBufNeedle
);
446 theSBufHay
.assign(cleanHay
);
450 assert(false); // should not happen