src/tests/SBufFindTest.cc

   1 #include "squid.h"
   2 #include "base/CharacterSet.h"
   3 #include "SBufFindTest.h"
   4 #include <cppunit/extensions/HelperMacros.h>
   5 #include <cppunit/Message.h>
   6 #include <limits>
   7
   8 /* TODO: The whole SBufFindTest class is currently implemented as a single
   9    CppUnit test case (because we do not want to register and report every one
  10    of the thousands of generated test cases). Is there a better way to
  11    integrate with CppUnit?
  12  */
  13
  14 SBufFindTest::SBufFindTest():
  15         caseLimit(std::numeric_limits<int>::max()),
  16         errorLimit(std::numeric_limits<int>::max()),
  17         randomSeed(1),
  18         hushSimilar(true),
  19         maxHayLength(40),
  20         thePos(0),
  21         thePlacement(placeEof),
  22         theStringPos(0),
  23         theBareNeedlePos(0),
  24         theFindString(0),
  25         theFindSBuf(0),
  26         theReportFunc(),
  27         theReportNeedle(),
  28         theReportPos(),
  29         theReportQuote('"'),
  30         caseCount(0),
  31         errorCount(0),
  32         reportCount(0)
  33 {
  34 }
  35
  36 void
  37 SBufFindTest::run()
  38 {
  39     srandom(randomSeed);
  40
  41     for (SBuf::size_type hayLen = 0U; hayLen <= maxHayLength; nextLen(hayLen, maxHayLength)) {
  42         const SBuf cleanHay = RandomSBuf(hayLen);
  43
  44         const SBuf::size_type maxNeedleLen = hayLen + 10;
  45         for (SBuf::size_type needleLen = 0U; needleLen <= maxNeedleLen; nextLen(needleLen, maxNeedleLen)) {
  46             theSBufNeedle = RandomSBuf(needleLen);
  47
  48             for (int i = 0; i < placeEof; i++) {
  49                 thePlacement = Placement(i);
  50                 placeNeedle(cleanHay);
  51
  52                 const SBuf::size_type maxArg =
  53                     max(theSBufHay.length(), theSBufNeedle.length()) + 10;
  54                 for (thePos = 0; thePos <= maxArg; nextLen(thePos, maxArg))
  55                     testAllMethods();
  56
  57                 // the special npos value is not tested as the behavior is
  58                 //  different from std::string (where the behavior is undefined)
  59                 //  It is ad-hoc tested in testSBuf instead
  60                 //thePos = SBuf::npos;
  61                 //testAllMethods();
  62             }
  63         }
  64     }
  65
  66     if (errorCount > 0) {
  67         std::cerr << "Generated SBuf test cases: " << caseCount << std::endl;
  68         std::cerr << "\tfailed cases: " << errorCount << std::endl;
  69         std::cerr << "\treported cases: " << reportCount << std::endl;
  70         std::cerr << "Asserting because some cases failed..." << std::endl;
  71         CPPUNIT_ASSERT(!SBufFindTest::errorCount);
  72     }
  73 }
  74
  75 /// tests SBuf::find(string needle)
  76 void
  77 SBufFindTest::testFindDefs()
  78 {
  79     theFindString = theBareNeedlePos = theStringHay.find(theStringNeedle);
  80     theFindSBuf = theSBufHay.find(theSBufNeedle);
  81     checkResults("find");
  82 }
  83
  84 /// tests SBuf::rfind(string needle)
  85 void
  86 SBufFindTest::testRFindDefs()
  87 {
  88     theFindString = theBareNeedlePos = theStringHay.rfind(theStringNeedle);
  89     theFindSBuf = theSBufHay.rfind(theSBufNeedle);
  90     checkResults("rfind");
  91 }
  92
  93 /// tests SBuf::find(string needle, pos)
  94 void
  95 SBufFindTest::testFind()
  96 {
  97     theFindString = theStringHay.find(theStringNeedle, thePos);
  98     theBareNeedlePos = theStringHay.find(theStringNeedle);
  99     theFindSBuf = theSBufHay.find(theSBufNeedle, thePos);
 100     checkResults("find");
 101 }
 102
 103 /// tests SBuf::findFirstOf(string needle, pos)
 104 void
 105 SBufFindTest::testFindFirstOf()
 106 {
 107     theFindString = theStringHay.find_first_of(theStringNeedle, thePos);
 108     theBareNeedlePos = theStringHay.find_first_of(theStringNeedle);
 109     theFindSBuf = theSBufHay.findFirstOf(CharacterSet("cs",theSBufNeedle.c_str()), thePos);
 110     checkResults("find_first_of");
 111 }
 112
 113 /// tests SBuf::rfind(string needle, pos)
 114 void
 115 SBufFindTest::testRFind()
 116 {
 117     theFindString = theStringHay.rfind(theStringNeedle, thePos);
 118     theBareNeedlePos = theStringHay.rfind(theStringNeedle);
 119     theFindSBuf = theSBufHay.rfind(theSBufNeedle, thePos);
 120     checkResults("rfind");
 121 }
 122
 123 /// tests SBuf::find(char needle)
 124 void
 125 SBufFindTest::testFindCharDefs()
 126 {
 127     const char c = theStringNeedle[0];
 128     theFindString = theBareNeedlePos = theStringHay.find(c);
 129     theFindSBuf = theSBufHay.find(c);
 130     checkResults("find");
 131 }
 132
 133 /// tests SBuf::find(char needle, pos)
 134 void
 135 SBufFindTest::testFindChar()
 136 {
 137     const char c = theStringNeedle[0];
 138     theFindString = theStringHay.find(c, thePos);
 139     theBareNeedlePos = theStringHay.find(c);
 140     theFindSBuf = theSBufHay.find(c, thePos);
 141     checkResults("find");
 142 }
 143
 144 /// tests SBuf::rfind(char needle)
 145 void
 146 SBufFindTest::testRFindCharDefs()
 147 {
 148     const char c = theStringNeedle[0];
 149     theFindString = theBareNeedlePos = theStringHay.rfind(c);
 150     theFindSBuf = theSBufHay.rfind(c);
 151     checkResults("rfind");
 152 }
 153
 154 /// tests SBuf::rfind(char needle, pos)
 155 void
 156 SBufFindTest::testRFindChar()
 157 {
 158     const char c = theStringNeedle[0];
 159     theFindString = theStringHay.rfind(c, thePos);
 160     theBareNeedlePos = theStringHay.rfind(c);
 161     theFindSBuf = theSBufHay.rfind(c, thePos);
 162     checkResults("rfind");
 163 }
 164
 165 /// whether the last SBuf and std::string find() results are the same
 166 bool
 167 SBufFindTest::resultsMatch() const
 168 {
 169     // this method is needed because SBuf and std::string use different
 170     // size_types (and npos values); comparing the result values directly
 171     // would lead to bugs
 172
 173     if (theFindString == std::string::npos && theFindSBuf == SBuf::npos)
 174         return true; // both npos
 175
 176     // now safe to cast a non-negative SBuf result
 177     return theFindString == static_cast<std::string::size_type>(theFindSBuf);
 178 }
 179
 180 /// called at the end of test case to update state, detect and report failures
 181 void
 182 SBufFindTest::checkResults(const char *method)
 183 {
 184     ++caseCount;
 185     if (!resultsMatch())
 186         handleFailure(method);
 187 }
 188
 189 /// helper function to convert "printable" Type to std::string
 190 template<typename Type>
 191 inline std::string
 192 AnyToString(const Type &value)
 193 {
 194     std::stringstream sbuf;
 195     sbuf << value;
 196     return sbuf.str();
 197 }
 198
 199 #if 0
 200 /// helper function to convert SBuf position to a human-friendly string
 201 inline std::string
 202 PosToString(const SBuf::size_type pos)
 203 {
 204     return pos == SBuf::npos ? std::string("npos") : AnyToString(pos);
 205 }
 206 #endif
 207
 208 /// helper function to convert std::string position to a human-friendly string
 209 inline std::string
 210 PosToString(const std::string::size_type pos)
 211 {
 212     return pos == std::string::npos ? std::string("npos") : AnyToString(pos);
 213 }
 214
 215 /// tests each supported SBuf::*find() method using generated hay, needle, pos
 216 void
 217 SBufFindTest::testAllMethods()
 218 {
 219     theStringHay = std::string(theSBufHay.rawContent(), theSBufHay.length());
 220     theStringNeedle = std::string(theSBufNeedle.rawContent(), theSBufNeedle.length());
 221     theBareNeedlePos = std::string::npos;
 222     const std::string reportPos = PosToString(thePos);
 223
 224     // always test string search
 225     {
 226         theReportQuote = '"';
 227         theReportNeedle = theStringNeedle;
 228
 229         theReportPos = "";
 230         testFindDefs();
 231         testRFindDefs();
 232
 233         theReportPos = reportPos;
 234         testFind();
 235         testRFind();
 236         testFindFirstOf();
 237     }
 238
 239     // if possible, test char search
 240     if (!theStringNeedle.empty()) {
 241         theReportQuote = '\'';
 242         theReportNeedle = theStringNeedle[0];
 243
 244         theReportPos = "";
 245         testFindCharDefs();
 246         testRFindCharDefs();
 247
 248         theReportPos = reportPos;
 249         testFindChar();
 250         testRFindChar();
 251     }
 252 }
 253
 254 /// helper function to format a length-based key (part of case category string)
 255 inline std::string
 256 lengthKey(const std::string &str)
 257 {
 258     if (str.length() == 0)
 259         return "0";
 260     if (str.length() == 1)
 261         return "1";
 262     return "N";
 263 }
 264
 265 /// formats position key (part of the case category string)
 266 std::string
 267 SBufFindTest::posKey() const
 268 {
 269     // the search position does not matter if needle is not in hay
 270     if (theBareNeedlePos == std::string::npos)
 271         return std::string();
 272
 273     if (thePos == SBuf::npos)
 274         return ",npos";
 275
 276     if (thePos < theBareNeedlePos)
 277         return ",posL"; // to the Left of the needle
 278
 279     if (thePos == theBareNeedlePos)
 280         return ",posB"; // Beginning of the needle
 281
 282     if (thePos < theBareNeedlePos + theStringNeedle.length())
 283         return ",posM"; // in the Middle of the needle
 284
 285     if (thePos == theBareNeedlePos + theStringNeedle.length())
 286         return ",posE"; // at the End of the needle
 287
 288     if (thePos < theStringHay.length())
 289         return ",posR"; // to the Right of the needle
 290
 291     return ",posP"; // past the hay
 292 }
 293
 294 /// formats placement key (part of the case category string)
 295 std::string
 296 SBufFindTest::placementKey() const
 297 {
 298     // Ignore thePlacement because theBareNeedlePos covers it better: we may
 299     // try to place the needle somewhere, but hay limits the actual placement.
 300
 301     // the placent does not matter if needle is not in hay
 302     if (theBareNeedlePos == std::string::npos)
 303         return std::string();
 304
 305     if (theBareNeedlePos == 0)
 306         return "@B"; // at the beggining of the hay string
 307     if (theBareNeedlePos == theStringHay.length()-theStringNeedle.length())
 308         return "@E"; // at the end of the hay string
 309     return "@M"; // in the "middle" of the hay string
 310 }
 311
 312 /// called when a test case fails; counts and possibly reports the failure
 313 void
 314 SBufFindTest::handleFailure(const char *method)
 315 {
 316     // line break after "........." printed for previous tests
 317     if (!errorCount)
 318         std::cerr << std::endl;
 319
 320     ++errorCount;
 321
 322     if (errorCount > errorLimit) {
 323         std::cerr << "Will stop generating SBuf test cases because the " <<
 324                   "number of failed ones is over the limit: " << errorCount <<
 325                   " (after " << caseCount << " test cases)" << std::endl;
 326         CPPUNIT_ASSERT(errorCount <= errorLimit);
 327         /* NOTREACHED */
 328     }
 329
 330     // format test case category; category allows us to hush failure reports
 331     // for already seen categories with failed cases (to reduce output noise)
 332     std::string category = "hay" + lengthKey(theStringHay) +
 333                            "." + method + '(';
 334     if (theReportQuote == '"')
 335         category += "needle" + lengthKey(theStringNeedle);
 336     else
 337         category += "char";
 338     category += placementKey();
 339     category += posKey();
 340     category += ')';
 341
 342     if (hushSimilar) {
 343         if (failedCats.find(category) != failedCats.end())
 344             return; // do not report another similar test case failure
 345         failedCats.insert(category);
 346     }
 347
 348     std::string reportPos = theReportPos;
 349     if (!reportPos.empty())
 350         reportPos = ", " + reportPos;
 351
 352     std::cerr << "case" << caseCount << ": " <<
 353               "SBuf(\"" << theStringHay << "\")." << method <<
 354               "(" << theReportQuote << theReportNeedle << theReportQuote <<
 355               reportPos << ") returns " << PosToString(theFindSBuf) <<
 356               " instead of " << PosToString(theFindString) <<
 357               std::endl <<
 358               "    std::string(\""  << theStringHay << "\")." << method <<
 359               "(" << theReportQuote << theReportNeedle << theReportQuote <<
 360               reportPos << ") returns " << PosToString(theFindString) <<
 361               std::endl <<
 362               "    category: " << category << std::endl;
 363
 364     ++reportCount;
 365 }
 366
 367 /// generates a random string of the specified length
 368 SBuf
 369 SBufFindTest::RandomSBuf(const int length)
 370 {
 371     static const char characters[] =
 372         "0123456789"
 373         "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
 374         "abcdefghijklomnpqrstuvwxyz";
 375     // sizeof() counts the terminating zero at the end of characters
 376     // TODO: add \0 character (needs reporting adjustments to print it as \0)
 377     static const size_t charCount = sizeof(characters)-1;
 378
 379     char buf[length];
 380     for (int i = 0; i < length; ++i) {
 381         const unsigned int pos = random() % charCount;
 382         assert(pos < sizeof(characters));
 383         assert(characters[pos] > 32);
 384         buf[i] = characters[random() % charCount];
 385     }
 386
 387     return SBuf(buf, length);
 388 }
 389
 390 /// increments len to quickly cover [0, max] range, slowing down in risky areas
 391 /// jumps to max+1 if caseLimit is reached
 392 void
 393 SBufFindTest::nextLen(SBuf::size_type &len, const SBuf::size_type max)
 394 {
 395     assert(len <= max);
 396
 397     if (caseCount >= caseLimit)
 398         len = max+1; // avoid future test cases
 399     else if (len <= 10)
 400         ++len; // move slowly at the beginning of the [0,max] range
 401     else if (len >= max - 10)
 402         ++len; // move slowly at the end of the [0,max] range
 403     else {
 404         // move fast in the middle of the [0,max] range
 405         len += len/10 + 1;
 406
 407         // but do not overshoot the interesting area at the end of the range
 408         if (len > max - 10)
 409             len = max - 10;
 410     }
 411 }
 412
 413 /// Places the needle into the hay using cleanHay as a starting point.
 414 void
 415 SBufFindTest::placeNeedle(const SBuf &cleanHay)
 416 {
 417     // For simplicity, we do not overwrite clean hay characters but use them as
 418     // needle suffix and/or prefix. Should not matter since hay length varies?
 419
 420     // TODO: support two needles per hay (explicitly)
 421     // TODO: better handle cases where clean hay already contains needle
 422     switch (thePlacement) {
 423     case placeBeginning:
 424         theSBufHay.assign(theSBufNeedle).append(cleanHay);
 425         break;
 426
 427     case placeMiddle: {
 428         const SBuf firstHalf = cleanHay.substr(0, cleanHay.length()/2);
 429         const SBuf secondHalf = cleanHay.substr(cleanHay.length()/2);
 430         theSBufHay.assign(firstHalf).append(theSBufNeedle).append(secondHalf);
 431         break;
 432     }
 433
 434     case placeEnd:
 435         theSBufHay.assign(cleanHay).append(theSBufNeedle);
 436         break;
 437
 438     case placeNowhere:
 439         theSBufHay.assign(cleanHay);
 440         break;
 441
 442     case placeEof:
 443         assert(false); // should not happen
 444         break;
 445     }
 446 }