src/tests/SBufFindTest.cc

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