src/tests/SBufFindTest.cc

   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
  24 SBufFindTest::SBufFindTest():
  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     theStringPos(0),
  32     theBareNeedlePos(0),
  33     theFindString(0),
  34     theFindSBuf(0),
  35     theReportFunc(),
  36     theReportNeedle(),
  37     theReportPos(),
  38     theReportQuote('"'),
  39     caseCount(0),
  40     errorCount(0),
  41     reportCount(0)
  42 {
  43 }
  44
  45 void
  46 SBufFindTest::run()
  47 {
  48     for (SBuf::size_type hayLen = 0U; hayLen <= maxHayLength; nextLen(hayLen, maxHayLength)) {
  49         const SBuf cleanHay = RandomSBuf(hayLen);
  50
  51         const SBuf::size_type maxNeedleLen = hayLen + 10;
  52         for (SBuf::size_type needleLen = 0U; needleLen <= maxNeedleLen; nextLen(needleLen, maxNeedleLen)) {
  53             theSBufNeedle = RandomSBuf(needleLen);
  54
  55             for (int i = 0; i < placeEof; i++) {
  56                 thePlacement = Placement(i);
  57                 placeNeedle(cleanHay);
  58
  59                 const SBuf::size_type maxArg =
  60                     max(theSBufHay.length(), theSBufNeedle.length()) + 10;
  61                 for (thePos = 0; thePos <= maxArg; nextLen(thePos, maxArg))
  62                     testAllMethods();
  63
  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;
  68                 //testAllMethods();
  69             }
  70         }
  71     }
  72
  73     if (errorCount > 0) {
  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);
  79     }
  80 }
  81
  82 /// tests SBuf::find(string needle)
  83 void
  84 SBufFindTest::testFindDefs()
  85 {
  86     theFindString = theBareNeedlePos = theStringHay.find(theStringNeedle);
  87     theFindSBuf = theSBufHay.find(theSBufNeedle);
  88     checkResults("find");
  89 }
  90
  91 /// tests SBuf::rfind(string needle)
  92 void
  93 SBufFindTest::testRFindDefs()
  94 {
  95     theFindString = theBareNeedlePos = theStringHay.rfind(theStringNeedle);
  96     theFindSBuf = theSBufHay.rfind(theSBufNeedle);
  97     checkResults("rfind");
  98 }
  99
 100 /// tests SBuf::find(string needle, pos)
 101 void
 102 SBufFindTest::testFind()
 103 {
 104     theFindString = theStringHay.find(theStringNeedle, thePos);
 105     theBareNeedlePos = theStringHay.find(theStringNeedle);
 106     theFindSBuf = theSBufHay.find(theSBufNeedle, thePos);
 107     checkResults("find");
 108 }
 109
 110 /// tests SBuf::findFirstOf(string needle, pos)
 111 void
 112 SBufFindTest::testFindFirstOf()
 113 {
 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");
 118 }
 119
 120 /// tests SBuf::rfind(string needle, pos)
 121 void
 122 SBufFindTest::testRFind()
 123 {
 124     theFindString = theStringHay.rfind(theStringNeedle, thePos);
 125     theBareNeedlePos = theStringHay.rfind(theStringNeedle);
 126     theFindSBuf = theSBufHay.rfind(theSBufNeedle, thePos);
 127     checkResults("rfind");
 128 }
 129
 130 /// tests SBuf::find(char needle)
 131 void
 132 SBufFindTest::testFindCharDefs()
 133 {
 134     const char c = theStringNeedle[0];
 135     theFindString = theBareNeedlePos = theStringHay.find(c);
 136     theFindSBuf = theSBufHay.find(c);
 137     checkResults("find");
 138 }
 139
 140 /// tests SBuf::find(char needle, pos)
 141 void
 142 SBufFindTest::testFindChar()
 143 {
 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");
 149 }
 150
 151 /// tests SBuf::rfind(char needle)
 152 void
 153 SBufFindTest::testRFindCharDefs()
 154 {
 155     const char c = theStringNeedle[0];
 156     theFindString = theBareNeedlePos = theStringHay.rfind(c);
 157     theFindSBuf = theSBufHay.rfind(c);
 158     checkResults("rfind");
 159 }
 160
 161 /// tests SBuf::rfind(char needle, pos)
 162 void
 163 SBufFindTest::testRFindChar()
 164 {
 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");
 170 }
 171
 172 /// whether the last SBuf and std::string find() results are the same
 173 bool
 174 SBufFindTest::resultsMatch() const
 175 {
 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
 179
 180     if (theFindString == std::string::npos && theFindSBuf == SBuf::npos)
 181         return true; // both npos
 182
 183     // now safe to cast a non-negative SBuf result
 184     return theFindString == static_cast<std::string::size_type>(theFindSBuf);
 185 }
 186
 187 /// called at the end of test case to update state, detect and report failures
 188 void
 189 SBufFindTest::checkResults(const char *method)
 190 {
 191     ++caseCount;
 192     if (!resultsMatch())
 193         handleFailure(method);
 194 }
 195
 196 /// helper function to convert "printable" Type to std::string
 197 template<typename Type>
 198 inline std::string
 199 AnyToString(const Type &value)
 200 {
 201     std::stringstream sbuf;
 202     sbuf << value;
 203     return sbuf.str();
 204 }
 205
 206 #if 0
 207 /// helper function to convert SBuf position to a human-friendly string
 208 inline std::string
 209 PosToString(const SBuf::size_type pos)
 210 {
 211     return pos == SBuf::npos ? std::string("npos") : AnyToString(pos);
 212 }
 213 #endif
 214
 215 /// helper function to convert std::string position to a human-friendly string
 216 inline std::string
 217 PosToString(const std::string::size_type pos)
 218 {
 219     return pos == std::string::npos ? std::string("npos") : AnyToString(pos);
 220 }
 221
 222 /// tests each supported SBuf::*find() method using generated hay, needle, pos
 223 void
 224 SBufFindTest::testAllMethods()
 225 {
 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);
 230
 231     // always test string search
 232     {
 233         theReportQuote = '"';
 234         theReportNeedle = theStringNeedle;
 235
 236         theReportPos = "";
 237         testFindDefs();
 238         testRFindDefs();
 239
 240         theReportPos = reportPos;
 241         testFind();
 242         testRFind();
 243         testFindFirstOf();
 244     }
 245
 246     // if possible, test char search
 247     if (!theStringNeedle.empty()) {
 248         theReportQuote = '\'';
 249         theReportNeedle = theStringNeedle[0];
 250
 251         theReportPos = "";
 252         testFindCharDefs();
 253         testRFindCharDefs();
 254
 255         theReportPos = reportPos;
 256         testFindChar();
 257         testRFindChar();
 258     }
 259 }
 260
 261 /// helper function to format a length-based key (part of case category string)
 262 inline std::string
 263 lengthKey(const std::string &str)
 264 {
 265     if (str.length() == 0)
 266         return "0";
 267     if (str.length() == 1)
 268         return "1";
 269     return "N";
 270 }
 271
 272 /// formats position key (part of the case category string)
 273 std::string
 274 SBufFindTest::posKey() const
 275 {
 276     // the search position does not matter if needle is not in hay
 277     if (theBareNeedlePos == std::string::npos)
 278         return std::string();
 279
 280     if (thePos == SBuf::npos)
 281         return ",npos";
 282
 283     if (thePos < theBareNeedlePos)
 284         return ",posL"; // to the Left of the needle
 285
 286     if (thePos == theBareNeedlePos)
 287         return ",posB"; // Beginning of the needle
 288
 289     if (thePos < theBareNeedlePos + theStringNeedle.length())
 290         return ",posM"; // in the Middle of the needle
 291
 292     if (thePos == theBareNeedlePos + theStringNeedle.length())
 293         return ",posE"; // at the End of the needle
 294
 295     if (thePos < theStringHay.length())
 296         return ",posR"; // to the Right of the needle
 297
 298     return ",posP"; // past the hay
 299 }
 300
 301 /// formats placement key (part of the case category string)
 302 std::string
 303 SBufFindTest::placementKey() const
 304 {
 305     // Ignore thePlacement because theBareNeedlePos covers it better: we may
 306     // try to place the needle somewhere, but hay limits the actual placement.
 307
 308     // the placent does not matter if needle is not in hay
 309     if (theBareNeedlePos == std::string::npos)
 310         return std::string();
 311
 312     if (theBareNeedlePos == 0)
 313         return "@B"; // at the beginning 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
 317 }
 318
 319 /// called when a test case fails; counts and possibly reports the failure
 320 void
 321 SBufFindTest::handleFailure(const char *method)
 322 {
 323     // line break after "........." printed for previous tests
 324     if (!errorCount)
 325         std::cerr << std::endl;
 326
 327     ++errorCount;
 328
 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);
 334         /* NOTREACHED */
 335     }
 336
 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) +
 340                            "." + method + '(';
 341     if (theReportQuote == '"')
 342         category += "needle" + lengthKey(theStringNeedle);
 343     else
 344         category += "char";
 345     category += placementKey();
 346     category += posKey();
 347     category += ')';
 348
 349     if (hushSimilar) {
 350         if (failedCats.find(category) != failedCats.end())
 351             return; // do not report another similar test case failure
 352         failedCats.insert(category);
 353     }
 354
 355     std::string reportPos = theReportPos;
 356     if (!reportPos.empty())
 357         reportPos = ", " + reportPos;
 358
 359     std::cerr << "case" << caseCount << ": " <<
 360               "SBuf(\"" << theStringHay << "\")." << method <<
 361               "(" << theReportQuote << theReportNeedle << theReportQuote <<
 362               reportPos << ") returns " << PosToString(theFindSBuf) <<
 363               " instead of " << PosToString(theFindString) <<
 364               std::endl <<
 365               "    std::string(\""  << theStringHay << "\")." << method <<
 366               "(" << theReportQuote << theReportNeedle << theReportQuote <<
 367               reportPos << ") returns " << PosToString(theFindString) <<
 368               std::endl <<
 369               "    category: " << category << std::endl;
 370
 371     ++reportCount;
 372 }
 373
 374 /// generates a random string of the specified length
 375 SBuf
 376 SBufFindTest::RandomSBuf(const int length)
 377 {
 378     static const char characters[] =
 379         "0123456789"
 380         "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 381         "abcdefghijklomnpqrstuvwxyz";
 382
 383     static std::mt19937 mt(time(0));
 384
 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);
 389
 390     SBuf buf;
 391     buf.reserveCapacity(length);
 392     for (int i = 0; i < length; ++i)
 393         buf.append(characters[dist(mt)]);
 394     return buf;
 395 }
 396
 397 /// increments len to quickly cover [0, max] range, slowing down in risky areas
 398 /// jumps to max+1 if caseLimit is reached
 399 void
 400 SBufFindTest::nextLen(SBuf::size_type &len, const SBuf::size_type max)
 401 {
 402     assert(len <= max);
 403
 404     if (caseCount >= caseLimit)
 405         len = max+1; // avoid future test cases
 406     else if (len <= 10)
 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
 410     else {
 411         // move fast in the middle of the [0,max] range
 412         len += len/10 + 1;
 413
 414         // but do not overshoot the interesting area at the end of the range
 415         if (len > max - 10)
 416             len = max - 10;
 417     }
 418 }
 419
 420 /// Places the needle into the hay using cleanHay as a starting point.
 421 void
 422 SBufFindTest::placeNeedle(const SBuf &cleanHay)
 423 {
 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?
 426
 427     // TODO: support two needles per hay (explicitly)
 428     // TODO: better handle cases where clean hay already contains needle
 429     switch (thePlacement) {
 430     case placeBeginning:
 431         theSBufHay.assign(theSBufNeedle).append(cleanHay);
 432         break;
 433
 434     case placeMiddle: {
 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);
 438         break;
 439     }
 440
 441     case placeEnd:
 442         theSBufHay.assign(cleanHay).append(theSBufNeedle);
 443         break;
 444
 445     case placeNowhere:
 446         theSBufHay.assign(cleanHay);
 447         break;
 448
 449     case placeEof:
 450         assert(false); // should not happen
 451         break;
 452     }
 453 }
 454