SBufFindTest.cc
Go to the documentation of this file.
1/*
2 * Copyright (C) 1996-2023 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 "base/Random.h"
12#include "tests/SBufFindTest.h"
13
14#include <cppunit/extensions/HelperMacros.h>
15#include <cppunit/Message.h>
16#include <limits>
17
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?
22 */
23
25 caseLimit(std::numeric_limits<int>::max()),
26 errorLimit(std::numeric_limits<int>::max()),
27 hushSimilar(true),
28 maxHayLength(40),
29 thePos(0),
30 thePlacement(placeEof),
31 theBareNeedlePos(0),
32 theFindString(0),
33 theFindSBuf(0),
34 theReportFunc(),
35 theReportNeedle(),
36 theReportPos(),
37 theReportQuote('"'),
38 caseCount(0),
39 errorCount(0),
40 reportCount(0)
41{
42}
43
44void
46{
47 for (SBuf::size_type hayLen = 0U; hayLen <= maxHayLength; nextLen(hayLen, maxHayLength)) {
48 const SBuf cleanHay = RandomSBuf(hayLen);
49
50 const SBuf::size_type maxNeedleLen = hayLen + 10;
51 for (SBuf::size_type needleLen = 0U; needleLen <= maxNeedleLen; nextLen(needleLen, maxNeedleLen)) {
52 theSBufNeedle = RandomSBuf(needleLen);
53
54 for (int i = 0; i < placeEof; i++) {
56 placeNeedle(cleanHay);
57
58 const SBuf::size_type maxArg =
60 for (thePos = 0; thePos <= maxArg; nextLen(thePos, maxArg))
62
63 // the special npos value is not tested as the behavior is
64 // different from std::string (where the behavior is undefined)
65 // It is ad-hoc tested in TestSBuf instead
66 //thePos = SBuf::npos;
67 //testAllMethods();
68 }
69 }
70 }
71
72 if (errorCount > 0) {
73 std::cerr << "Generated SBuf test cases: " << caseCount << std::endl;
74 std::cerr << "\tfailed cases: " << errorCount << std::endl;
75 std::cerr << "\treported cases: " << reportCount << std::endl;
76 std::cerr << "Asserting because some cases failed..." << std::endl;
77 CPPUNIT_ASSERT(!SBufFindTest::errorCount);
78 }
79}
80
82void
84{
87 checkResults("find");
88}
89
91void
93{
96 checkResults("rfind");
97}
98
100void
102{
106 checkResults("find");
107}
108
110void
112{
116 checkResults("find_first_of");
117}
118
120void
122{
126 checkResults("rfind");
127}
128
130void
132{
133 const char c = theStringNeedle[0];
136 checkResults("find");
137}
138
140void
142{
143 const char c = theStringNeedle[0];
147 checkResults("find");
148}
149
151void
153{
154 const char c = theStringNeedle[0];
157 checkResults("rfind");
158}
159
161void
163{
164 const char c = theStringNeedle[0];
168 checkResults("rfind");
169}
170
172bool
174{
175 // this method is needed because SBuf and std::string use different
176 // size_types (and npos values); comparing the result values directly
177 // would lead to bugs
178
179 if (theFindString == std::string::npos && theFindSBuf == SBuf::npos)
180 return true; // both npos
181
182 // now safe to cast a non-negative SBuf result
183 return theFindString == static_cast<std::string::size_type>(theFindSBuf);
184}
185
187void
188SBufFindTest::checkResults(const char *method)
189{
190 ++caseCount;
191 if (!resultsMatch())
192 handleFailure(method);
193}
194
196template<typename Type>
197inline std::string
198AnyToString(const Type &value)
199{
200 std::stringstream sbuf;
201 sbuf << value;
202 return sbuf.str();
203}
204
206inline std::string
207PosToString(const std::string::size_type pos)
208{
209 return pos == std::string::npos ? std::string("npos") : AnyToString(pos);
210}
211
213void
215{
218 theBareNeedlePos = std::string::npos;
219 const std::string reportPos = PosToString(thePos);
220
221 // always test string search
222 {
223 theReportQuote = '"';
225
226 theReportPos = "";
227 testFindDefs();
229
230 theReportPos = reportPos;
231 testFind();
232 testRFind();
234 }
235
236 // if possible, test char search
237 if (!theStringNeedle.empty()) {
238 theReportQuote = '\'';
240
241 theReportPos = "";
244
245 theReportPos = reportPos;
246 testFindChar();
248 }
249}
250
252inline std::string
253lengthKey(const std::string &str)
254{
255 if (str.length() == 0)
256 return "0";
257 if (str.length() == 1)
258 return "1";
259 return "N";
260}
261
263std::string
265{
266 // the search position does not matter if needle is not in hay
267 if (theBareNeedlePos == std::string::npos)
268 return std::string();
269
270 if (thePos == SBuf::npos)
271 return ",npos";
272
274 return ",posL"; // to the Left of the needle
275
277 return ",posB"; // Beginning of the needle
278
279 if (thePos < theBareNeedlePos + theStringNeedle.length())
280 return ",posM"; // in the Middle of the needle
281
282 if (thePos == theBareNeedlePos + theStringNeedle.length())
283 return ",posE"; // at the End of the needle
284
285 if (thePos < theStringHay.length())
286 return ",posR"; // to the Right of the needle
287
288 return ",posP"; // past the hay
289}
290
292std::string
294{
295 // Ignore thePlacement because theBareNeedlePos covers it better: we may
296 // try to place the needle somewhere, but hay limits the actual placement.
297
298 // the placent does not matter if needle is not in hay
299 if (theBareNeedlePos == std::string::npos)
300 return std::string();
301
302 if (theBareNeedlePos == 0)
303 return "@B"; // at the beginning of the hay string
304 if (theBareNeedlePos == theStringHay.length()-theStringNeedle.length())
305 return "@E"; // at the end of the hay string
306 return "@M"; // in the "middle" of the hay string
307}
308
310void
311SBufFindTest::handleFailure(const char *method)
312{
313 // line break after "........." printed for previous tests
314 if (!errorCount)
315 std::cerr << std::endl;
316
317 ++errorCount;
318
319 if (errorCount > errorLimit) {
320 std::cerr << "Will stop generating SBuf test cases because the " <<
321 "number of failed ones is over the limit: " << errorCount <<
322 " (after " << caseCount << " test cases)" << std::endl;
323 CPPUNIT_ASSERT(errorCount <= errorLimit);
324 /* NOTREACHED */
325 }
326
327 // format test case category; category allows us to hush failure reports
328 // for already seen categories with failed cases (to reduce output noise)
329 std::string category = "hay" + lengthKey(theStringHay) +
330 "." + method + '(';
331 if (theReportQuote == '"')
332 category += "needle" + lengthKey(theStringNeedle);
333 else
334 category += "char";
335 category += placementKey();
336 category += posKey();
337 category += ')';
338
339 if (hushSimilar) {
340 if (failedCats.find(category) != failedCats.end())
341 return; // do not report another similar test case failure
342 failedCats.insert(category);
343 }
344
345 std::string reportPos = theReportPos;
346 if (!reportPos.empty())
347 reportPos = ", " + reportPos;
348
349 std::cerr << "case" << caseCount << ": " <<
350 "SBuf(\"" << theStringHay << "\")." << method <<
352 reportPos << ") returns " << PosToString(theFindSBuf) <<
353 " instead of " << PosToString(theFindString) <<
354 std::endl <<
355 " std::string(\"" << theStringHay << "\")." << method <<
357 reportPos << ") returns " << PosToString(theFindString) <<
358 std::endl <<
359 " category: " << category << std::endl;
360
361 ++reportCount;
362}
363
365SBuf
366SBufFindTest::RandomSBuf(const int length)
367{
368 static const char characters[] =
369 "0123456789"
370 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
371 "abcdefghijklomnpqrstuvwxyz";
372
373 static std::mt19937 mt(RandomSeed32());
374
375 // sizeof() counts the terminating zero at the end of characters
376 // and the distribution is an 'inclusive' value range, so -2
377 // TODO: add \0 character (needs reporting adjustments to print it as \0)
378 static std::uniform_int_distribution<uint8_t> dist(0, sizeof(characters)-2);
379
380 SBuf buf;
381 buf.reserveCapacity(length);
382 for (int i = 0; i < length; ++i)
383 buf.append(characters[dist(mt)]);
384 return buf;
385}
386
389void
391{
392 assert(len <= max);
393
394 if (caseCount >= caseLimit)
395 len = max+1; // avoid future test cases
396 else if (len <= 10)
397 ++len; // move slowly at the beginning of the [0,max] range
398 else if (len >= max - 10)
399 ++len; // move slowly at the end of the [0,max] range
400 else {
401 // move fast in the middle of the [0,max] range
402 len += len/10 + 1;
403
404 // but do not overshoot the interesting area at the end of the range
405 if (len > max - 10)
406 len = max - 10;
407 }
408}
409
411void
412SBufFindTest::placeNeedle(const SBuf &cleanHay)
413{
414 // For simplicity, we do not overwrite clean hay characters but use them as
415 // needle suffix and/or prefix. Should not matter since hay length varies?
416
417 // TODO: support two needles per hay (explicitly)
418 // TODO: better handle cases where clean hay already contains needle
419 switch (thePlacement) {
420 case placeBeginning:
422 break;
423
424 case placeMiddle: {
425 const SBuf firstHalf = cleanHay.substr(0, cleanHay.length()/2);
426 const SBuf secondHalf = cleanHay.substr(cleanHay.length()/2);
427 theSBufHay.assign(firstHalf).append(theSBufNeedle).append(secondHalf);
428 break;
429 }
430
431 case placeEnd:
433 break;
434
435 case placeNowhere:
436 theSBufHay.assign(cleanHay);
437 break;
438
439 case placeEof:
440 assert(false); // should not happen
441 break;
442 }
443}
444
#define assert(EX)
Definition: assert.h:17
std::mt19937::result_type RandomSeed32()
Definition: Random.cc:13
optimized set of C chars, with quick membership test and merge support
Definition: CharacterSet.h:18
int caseLimit
approximate caseCount limit
Definition: SBufFindTest.h:27
void testRFindDefs()
void testFindChar()
void handleFailure(const char *method)
std::string theStringHay
theHay converted to std::string
Definition: SBufFindTest.h:68
Placement
Supported algorithms for placing needle in the hay.
Definition: SBufFindTest.h:35
SBuf::size_type thePos
search position limit
Definition: SBufFindTest.h:66
int caseCount
cases executed so far
Definition: SBufFindTest.h:83
void checkResults(const char *method)
void testRFind()
std::string theReportPos
Definition: SBufFindTest.h:79
Placement thePlacement
where in the hay the needle is placed
Definition: SBufFindTest.h:67
std::string placementKey() const
void testFindDefs()
std::string::size_type theBareNeedlePos
needle pos w/o thePos restrictions; used for case categorization
Definition: SBufFindTest.h:72
void testFind()
char theReportQuote
Definition: SBufFindTest.h:80
SBuf theSBufNeedle
the string to be found
Definition: SBufFindTest.h:65
void placeNeedle(const SBuf &cleanHay)
bool hushSimilar
whether to report only one failed test case per "category"
Definition: SBufFindTest.h:30
int errorCount
total number of failed test cases so far
Definition: SBufFindTest.h:84
std::string theReportNeedle
Definition: SBufFindTest.h:78
void testRFindCharDefs()
void testFindFirstOf()
void nextLen(SBuf::size_type &len, const SBuf::size_type max)
SBuf::size_type theFindSBuf
Definition: SBufFindTest.h:76
void testAllMethods()
std::string theStringNeedle
theNeedle converted to std::string
Definition: SBufFindTest.h:69
bool resultsMatch() const
std::string posKey() const
std::string::size_type theFindString
Definition: SBufFindTest.h:75
int reportCount
total number of test cases reported so far
Definition: SBufFindTest.h:85
void run()
generates and executes cases using configuration params
SBuf theSBufHay
the string to be searched
Definition: SBufFindTest.h:64
void testRFindChar()
std::set< std::string > failedCats
reported failed categories
Definition: SBufFindTest.h:86
SBuf::size_type maxHayLength
approximate maximum generated hay string length
Definition: SBufFindTest.h:32
void testFindCharDefs()
static SBuf RandomSBuf(const int length)
Definition: SBuf.h:94
const char * rawContent() const
Definition: SBuf.cc:509
static const size_type npos
Definition: SBuf.h:99
const char * c_str()
Definition: SBuf.cc:516
void reserveCapacity(size_type minCapacity)
Definition: SBuf.cc:105
size_type length() const
Returns the number of bytes stored in SBuf.
Definition: SBuf.h:415
size_type rfind(char c, size_type endPos=npos) const
Definition: SBuf.cc:692
size_type find(char c, size_type startPos=0) const
Definition: SBuf.cc:584
size_type findFirstOf(const CharacterSet &set, size_type startPos=0) const
Definition: SBuf.cc:723
SBuf & append(const SBuf &S)
Definition: SBuf.cc:185
SBuf substr(size_type pos, size_type n=npos) const
Definition: SBuf.cc:576
MemBlob::size_type size_type
Definition: SBuf.h:96
SBuf & assign(const SBuf &S)
Definition: SBuf.cc:83
Definition: cf_gen.cc:109
A const & max(A const &lhs, A const &rhs)
STL namespace.
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors