SBufFindTest.cc
Go to the documentation of this file.
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 "tests/SBufFindTest.h"
12 
13 #include <cppunit/extensions/HelperMacros.h>
14 #include <cppunit/Message.h>
15 #include <limits>
16 #include <random>
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 
44 void
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 
82 void
84 {
87  checkResults("find");
88 }
89 
91 void
93 {
96  checkResults("rfind");
97 }
98 
100 void
102 {
106  checkResults("find");
107 }
108 
110 void
112 {
116  checkResults("find_first_of");
117 }
118 
120 void
122 {
126  checkResults("rfind");
127 }
128 
130 void
132 {
133  const char c = theStringNeedle[0];
136  checkResults("find");
137 }
138 
140 void
142 {
143  const char c = theStringNeedle[0];
144  theFindString = theStringHay.find(c, thePos);
145  theBareNeedlePos = theStringHay.find(c);
147  checkResults("find");
148 }
149 
151 void
153 {
154  const char c = theStringNeedle[0];
157  checkResults("rfind");
158 }
159 
161 void
163 {
164  const char c = theStringNeedle[0];
165  theFindString = theStringHay.rfind(c, thePos);
166  theBareNeedlePos = theStringHay.rfind(c);
168  checkResults("rfind");
169 }
170 
172 bool
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 
187 void
188 SBufFindTest::checkResults(const char *method)
189 {
190  ++caseCount;
191  if (!resultsMatch())
192  handleFailure(method);
193 }
194 
196 template<typename Type>
197 inline std::string
198 AnyToString(const Type &value)
199 {
200  std::stringstream sbuf;
201  sbuf << value;
202  return sbuf.str();
203 }
204 
206 inline std::string
207 PosToString(const std::string::size_type pos)
208 {
209  return pos == std::string::npos ? std::string("npos") : AnyToString(pos);
210 }
211 
213 void
215 {
216  theStringHay = std::string(theSBufHay.rawContent(), theSBufHay.length());
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();
228  testRFindDefs();
229 
230  theReportPos = reportPos;
231  testFind();
232  testRFind();
233  testFindFirstOf();
234  }
235 
236  // if possible, test char search
237  if (!theStringNeedle.empty()) {
238  theReportQuote = '\'';
240 
241  theReportPos = "";
244 
245  theReportPos = reportPos;
246  testFindChar();
247  testRFindChar();
248  }
249 }
250 
252 inline std::string
253 lengthKey(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 
263 std::string
264 SBufFindTest::posKey() const
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 
273  if (thePos < theBareNeedlePos)
274  return ",posL"; // to the Left of the needle
275 
276  if (thePos == theBareNeedlePos)
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 
292 std::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 
310 void
311 SBufFindTest::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 
365 SBuf
366 SBufFindTest::RandomSBuf(const int length)
367 {
368  static const char characters[] =
369  "0123456789"
370  "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
371  "abcdefghijklomnpqrstuvwxyz";
372 
373  static std::mt19937 mt(time(0));
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 xuniform_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 
389 void
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 
411 void
412 SBufFindTest::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 
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::size_type theFindString
Definition: SBufFindTest.h:75
size_type find(char c, size_type startPos=0) const
Definition: SBuf.cc:584
void testRFindCharDefs()
void testAllMethods()
SBuf & assign(const SBuf &S)
Definition: SBuf.cc:83
Placement thePlacement
where in the hay the needle is placed
Definition: SBufFindTest.h:67
void run()
generates and executes cases using configuration params
SBuf theSBufHay
the string to be searched
Definition: SBufFindTest.h:64
char theReportQuote
Definition: SBufFindTest.h:80
void testFindCharDefs()
static SBuf RandomSBuf(const int length)
void testFindChar()
void nextLen(SBuf::size_type &len, const SBuf::size_type max)
Definition: SBuf.h:87
std::string::size_type theBareNeedlePos
needle pos w/o thePos restrictions; used for case categorization
Definition: SBufFindTest.h:72
Placement
Supported algorithms for placing needle in the hay.
Definition: SBufFindTest.h:35
int caseCount
cases executed so far
Definition: SBufFindTest.h:83
std::string theStringHay
theHay converted to std::string
Definition: SBufFindTest.h:68
SBuf::size_type thePos
search position limit
Definition: SBufFindTest.h:66
std::string placementKey() const
SBuf substr(size_type pos, size_type n=npos) const
Definition: SBuf.cc:576
void testFindDefs()
A const & max(A const &lhs, A const &rhs)
std::string posKey() const
std::string theReportPos
Definition: SBufFindTest.h:79
size_type rfind(char c, size_type endPos=npos) const
Definition: SBuf.cc:692
int reportCount
total number of test cases reported so far
Definition: SBufFindTest.h:85
const char * rawContent() const
Definition: SBuf.cc:509
void testRFindDefs()
MemBlob::size_type size_type
Definition: SBuf.h:89
#define true
Definition: GnuRegex.c:234
std::string theStringNeedle
theNeedle converted to std::string
Definition: SBufFindTest.h:69
std::string theReportNeedle
Definition: SBufFindTest.h:78
SBuf::size_type theFindSBuf
Definition: SBufFindTest.h:76
Definition: cf_gen.cc:109
#define assert(EX)
Definition: assert.h:19
void checkResults(const char *method)
const char * c_str()
Definition: SBuf.cc:516
size_type length() const
Returns the number of bytes stored in SBuf.
Definition: SBuf.h:408
void placeNeedle(const SBuf &cleanHay)
SBuf & append(const SBuf &S)
Definition: SBuf.cc:185
static const size_type npos
Definition: SBuf.h:92
int caseLimit
approximate caseCount limit
Definition: SBufFindTest.h:27
void testFindFirstOf()
bool resultsMatch() const
void reserveCapacity(size_type minCapacity)
Definition: SBuf.cc:105
void handleFailure(const char *method)
std::set< std::string > failedCats
reported failed categories
Definition: SBufFindTest.h:86
void testRFindChar()
optimized set of C chars, with quick membership test and merge support
Definition: CharacterSet.h:18
void testRFind()
SBuf::size_type maxHayLength
approximate maximum generated hay string length
Definition: SBufFindTest.h:32
size_type findFirstOf(const CharacterSet &set, size_type startPos=0) const
Definition: SBuf.cc:723
void testFind()
SBuf theSBufNeedle
the string to be found
Definition: SBufFindTest.h:65
int unsigned int
Definition: stub_fd.cc:19

 

Introduction

Documentation

Support

Miscellaneous

Web Site Translations

Mirrors