src/tests/SBufFindTest.cc

   1 /*
   2  * Copyright (C) 1996-2022 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
  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     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
  45 SBufFindTest::run()
  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++) {
  55                 thePlacement = Placement(i);
  56                 placeNeedle(cleanHay);
  57
  58                 const SBuf::size_type maxArg =
  59                     max(theSBufHay.length(), theSBufNeedle.length()) + 10;
  60                 for (thePos = 0; thePos <= maxArg; nextLen(thePos, maxArg))
  61                     testAllMethods();
  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
  81 /// tests SBuf::find(string needle)
  82 void
  83 SBufFindTest::testFindDefs()
  84 {
  85     theFindString = theBareNeedlePos = theStringHay.find(theStringNeedle);
  86     theFindSBuf = theSBufHay.find(theSBufNeedle);
  87     checkResults("find");
  88 }
  89
  90 /// tests SBuf::rfind(string needle)
  91 void
  92 SBufFindTest::testRFindDefs()
  93 {
  94     theFindString = theBareNeedlePos = theStringHay.rfind(theStringNeedle);
  95     theFindSBuf = theSBufHay.rfind(theSBufNeedle);
  96     checkResults("rfind");
  97 }
  98
  99 /// tests SBuf::find(string needle, pos)
 100 void
 101 SBufFindTest::testFind()
 102 {
 103     theFindString = theStringHay.find(theStringNeedle, thePos);
 104     theBareNeedlePos = theStringHay.find(theStringNeedle);
 105     theFindSBuf = theSBufHay.find(theSBufNeedle, thePos);
 106     checkResults("find");
 107 }
 108
 109 /// tests SBuf::findFirstOf(string needle, pos)
 110 void
 111 SBufFindTest::testFindFirstOf()
 112 {
 113     theFindString = theStringHay.find_first_of(theStringNeedle, thePos);
 114     theBareNeedlePos = theStringHay.find_first_of(theStringNeedle);
 115     theFindSBuf = theSBufHay.findFirstOf(CharacterSet("cs",theSBufNeedle.c_str()), thePos);
 116     checkResults("find_first_of");
 117 }
 118
 119 /// tests SBuf::rfind(string needle, pos)
 120 void
 121 SBufFindTest::testRFind()
 122 {
 123     theFindString = theStringHay.rfind(theStringNeedle, thePos);
 124     theBareNeedlePos = theStringHay.rfind(theStringNeedle);
 125     theFindSBuf = theSBufHay.rfind(theSBufNeedle, thePos);
 126     checkResults("rfind");
 127 }
 128
 129 /// tests SBuf::find(char needle)
 130 void
 131 SBufFindTest::testFindCharDefs()
 132 {
 133     const char c = theStringNeedle[0];
 134     theFindString = theBareNeedlePos = theStringHay.find(c);
 135     theFindSBuf = theSBufHay.find(c);
 136     checkResults("find");
 137 }
 138
 139 /// tests SBuf::find(char needle, pos)
 140 void
 141 SBufFindTest::testFindChar()
 142 {
 143     const char c = theStringNeedle[0];
 144     theFindString = theStringHay.find(c, thePos);
 145     theBareNeedlePos = theStringHay.find(c);
 146     theFindSBuf = theSBufHay.find(c, thePos);
 147     checkResults("find");
 148 }
 149
 150 /// tests SBuf::rfind(char needle)
 151 void
 152 SBufFindTest::testRFindCharDefs()
 153 {
 154     const char c = theStringNeedle[0];
 155     theFindString = theBareNeedlePos = theStringHay.rfind(c);
 156     theFindSBuf = theSBufHay.rfind(c);
 157     checkResults("rfind");
 158 }
 159
 160 /// tests SBuf::rfind(char needle, pos)
 161 void
 162 SBufFindTest::testRFindChar()
 163 {
 164     const char c = theStringNeedle[0];
 165     theFindString = theStringHay.rfind(c, thePos);
 166     theBareNeedlePos = theStringHay.rfind(c);
 167     theFindSBuf = theSBufHay.rfind(c, thePos);
 168     checkResults("rfind");
 169 }
 170
 171 /// whether the last SBuf and std::string find() results are the same
 172 bool
 173 SBufFindTest::resultsMatch() const
 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
 186 /// called at the end of test case to update state, detect and report failures
 187 void
 188 SBufFindTest::checkResults(const char *method)
 189 {
 190     ++caseCount;
 191     if (!resultsMatch())
 192         handleFailure(method);
 193 }
 194
 195 /// helper function to convert "printable" Type to std::string
 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
 205 /// helper function to convert std::string position to a human-friendly string
 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
 212 /// tests each supported SBuf::*find() method using generated hay, needle, pos
 213 void
 214 SBufFindTest::testAllMethods()
 215 {
 216     theStringHay = std::string(theSBufHay.rawContent(), theSBufHay.length());
 217     theStringNeedle = std::string(theSBufNeedle.rawContent(), theSBufNeedle.length());
 218     theBareNeedlePos = std::string::npos;
 219     const std::string reportPos = PosToString(thePos);
 220
 221     // always test string search
 222     {
 223         theReportQuote = '"';
 224         theReportNeedle = theStringNeedle;
 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 = '\'';
 239         theReportNeedle = theStringNeedle[0];
 240
 241         theReportPos = "";
 242         testFindCharDefs();
 243         testRFindCharDefs();
 244
 245         theReportPos = reportPos;
 246         testFindChar();
 247         testRFindChar();
 248     }
 249 }
 250
 251 /// helper function to format a length-based key (part of case category string)
 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
 262 /// formats position key (part of the case category string)
 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
 291 /// formats placement key (part of the case category string)
 292 std::string
 293 SBufFindTest::placementKey() const
 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
 309 /// called when a test case fails; counts and possibly reports the failure
 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 <<
 351               "(" << theReportQuote << theReportNeedle << theReportQuote <<
 352               reportPos << ") returns " << PosToString(theFindSBuf) <<
 353               " instead of " << PosToString(theFindString) <<
 354               std::endl <<
 355               "    std::string(\""  << theStringHay << "\")." << method <<
 356               "(" << theReportQuote << theReportNeedle << theReportQuote <<
 357               reportPos << ") returns " << PosToString(theFindString) <<
 358               std::endl <<
 359               "    category: " << category << std::endl;
 360
 361     ++reportCount;
 362 }
 363
 364 /// generates a random string of the specified length
 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(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
 387 /// increments len to quickly cover [0, max] range, slowing down in risky areas
 388 /// jumps to max+1 if caseLimit is reached
 389 void
 390 SBufFindTest::nextLen(SBuf::size_type &len, const SBuf::size_type max)
 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
 410 /// Places the needle into the hay using cleanHay as a starting point.
 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:
 421         theSBufHay.assign(theSBufNeedle).append(cleanHay);
 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:
 432         theSBufHay.assign(cleanHay).append(theSBufNeedle);
 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