Hello, The attached patch adds about 700'000 test cases for eight SBuf::find() methods. Needless to say, they are generated rather than manually written. They take a couple of seconds to run. Configuration options allow us to increase or decrease the number of test cases if needed.
The code attempts to avoid reporting the same kind of find() bugs over and over again by suppressing reports about similar failures. The definition of "similar" is imperfect and the corresponding categorization code can probably be significantly improved, but it already results in reporting just 28 out of 22949 failures. Here are a few reported test case failures (stringng r9612): > case196: SBuf("a").rfind("a", 0) returns npos instead of 0 > std::string("a").rfind("a", 0) returns 0 > category: hay1.rfind(needle1@B,posB) > case5796: SBuf("2").rfind("", 0) returns 1 instead of 0 > std::string("2").rfind("", 0) returns 0 > category: hay1.rfind(needle0@E,posL) > case5799: SBuf("2").find("", 1) returns 0 instead of 1 > std::string("2").find("", 1) returns 1 > category: hay1.find(needle0@B,posP) > case6236: SBuf("2Q").rfind("Q", 1) returns npos instead of 1 > std::string("2Q").rfind("Q", 1) returns 1 > category: hayN.rfind(needle1@E,posB) > case22048: SBuf("CQGGR4").rfind('G', 2) returns npos instead of 2 > std::string("CQGGR4").rfind('G', 2) returns 2 > category: hayN.rfind(char@E,posL) > case30524: SBuf("UtRGRR").rfind("RR", 3) returns 4 instead of npos > std::string("UtRGRR").rfind("RR", 3) returns npos > category: hayN.rfind(needleN@E,posL) ... > Generated SBuf test cases: 716672 > failed cases: 22949 > reported cases: 28 > Asserting because some cases failed... Needless to say, all of the above could be coming from the same bug or two in SBuf code. 28 test case failures do not imply that there are 28 different bugs (our the categorization code is not that clever!). The large number of generated test cases, the logic to suppress similar reports, and lack of CppUnit knowledge resulted in very limited CppUnit integration. All the generated test cases are treated as one from CppUnit point of view. Perhaps this can be improved in the future. New generated test cases for SBuf methods other than find() and rfind() should be added as well, of course. Class and file names should be polished. There are a few other TODOs in the patch. As you know, SBuf in the StringNG branch has been under Squid Project review for a very long time. While each review iteration did find some bugs, the overall progress has been very slow. I suspect one of the reasons behind these delays is that it take a long time to find the time for review and then to find the time to fix bugs. By adding these test cases to the branch, I hope we can eliminate some of the delays because at least find() bugs can be found automatically, without yet another review iteration. Similar generated test cases for other areas should be added as well, IMO. Kinkie, would you be interested in taking over this code, polishing it as needed, committing it to stringng, and using it for your work? Thank you, Alex.
Author: Valentin Rakush Author: Alex Rousskov Generate a [configurable] large number of SBuf::*find() test cases using random strings (and std::string as the source of correct outcomes). This is a Measurement Factory project. === modified file 'src/Makefile.am' --- src/Makefile.am 2013-02-24 18:39:40 +0000 +++ src/Makefile.am 2013-02-25 17:13:45 +0000 @@ -3801,40 +3801,42 @@ $(SSL_LIBS) \ $(top_builddir)/lib/libmisccontainers.la \ $(top_builddir)/lib/libmiscencoding.la \ $(top_builddir)/lib/libmiscutil.la \ $(COMPAT_LIB) \ $(SQUID_CPPUNIT_LIBS) \ $(SQUID_CPPUNIT_LA) \ $(SSLLIB) \ $(KRB5LIBS) \ $(COMPAT_LIB) \ $(XTRA_LIBS) tests_testURL_LDFLAGS = $(LIBADD_DL) tests_testURL_DEPENDENCIES = \ $(REPL_OBJS) \ $(SQUID_CPPUNIT_LA) tests_testSBuf_SOURCES= \ tests/testSBuf.h \ tests/testSBuf.cc \ tests/testMain.cc \ + tests/SBufFindTest.h \ + tests/SBufFindTest.cc \ $(SBUF_SOURCE) \ SBufStream.h \ time.cc \ mem.cc \ tests/stub_debug.cc \ tests/stub_fatal.cc \ tests/stub_HelperChildConfig.cc \ tests/stub_cache_cf.cc \ tests/stub_cache_manager.cc \ tests/stub_store.cc \ tests/stub_store_stats.cc \ tests/stub_tools.cc \ SquidString.h \ String.cc \ wordlist.cc \ MemBuf.cc nodist_tests_testSBuf_SOURCES=$(TESTSOURCES) tests_testSBuf_LDFLAGS = $(LIBADD_DL) tests_testSBuf_LDADD=\ $(SQUID_CPPUNIT_LIBS) \ === added file 'src/tests/SBufFindTest.cc' --- src/tests/SBufFindTest.cc 1970-01-01 00:00:00 +0000 +++ src/tests/SBufFindTest.cc 2013-02-25 22:02:27 +0000 @@ -0,0 +1,418 @@ +#include "squid.h" +#include "SBufFindTest.h" +#include <cppunit/extensions/HelperMacros.h> +#include <cppunit/Message.h> +#include <limits> + + +/* TODO: The whole SBufFindTest class is currently implemented as a single + CppUnit test case (because we do not want to register and report every one + of the thousands of generated test cases). Is there a better way to + integrate with CppUnit? + */ + + +SBufFindTest::SBufFindTest(): + caseLimit(std::numeric_limits<int>::max()), + errorLimit(std::numeric_limits<int>::max()), + randomSeed(1), + hushSimilar(true), + maxHayLength(40), + thePos(0), + thePlacement(placeEof), + theStringPos(0), + theBareNeedlePos(0), + caseCount(0), + errorCount(0), + reportCount(0) +{ +} + +void +SBufFindTest::run() +{ + srandom(randomSeed); + + for (SBuf::size_type hayLen = 0; hayLen <= maxHayLength; nextLen(hayLen, maxHayLength)) { + const SBuf cleanHay = RandomSBuf(hayLen); + + const SBuf::size_type maxNeedleLen = hayLen + 10; + for (SBuf::size_type needleLen = 0; needleLen <= maxNeedleLen; nextLen(needleLen, maxNeedleLen)) { + theSBufNeedle = RandomSBuf(needleLen); + + for (int i = 0; i < Placement::placeEof; i++) { + thePlacement = Placement(i); + placeNeedle(cleanHay); + + const SBuf::size_type maxArg = + max(theSBufHay.length(), theSBufNeedle.length()) + 10; + for (thePos = 0; thePos <= maxArg; nextLen(thePos, maxArg)) + testAllMethods(); + + // also test the special npos value + thePos = SBuf::npos; + testAllMethods(); + } + } + } + + if (errorCount > 0) { + std::cerr << "Generated SBuf test cases: " << caseCount << std::endl; + std::cerr << "\tfailed cases: " << errorCount << std::endl; + std::cerr << "\treported cases: " << reportCount << std::endl; + std::cerr << "Asserting because some cases failed..." << std::endl; + CPPUNIT_ASSERT(!SBufFindTest::errorCount); + } +} + +/// tests SBuf::find(string needle) +void +SBufFindTest::testFindDefs() { + theFindString = theBareNeedlePos = theStringHay.find(theStringNeedle); + theFindSBuf = theSBufHay.find(theSBufNeedle); + checkResults("find"); +} + +/// tests SBuf::rfind(string needle) +void +SBufFindTest::testRFindDefs() { + theFindString = theBareNeedlePos = theStringHay.rfind(theStringNeedle); + theFindSBuf = theSBufHay.rfind(theSBufNeedle); + checkResults("rfind"); +} + +/// tests SBuf::find(string needle, pos) +void +SBufFindTest::testFind() { + theFindString = theStringHay.find(theStringNeedle, thePos); + theBareNeedlePos = theStringHay.find(theStringNeedle); + theFindSBuf = theSBufHay.find(theSBufNeedle, thePos); + checkResults("find"); +} + +/// tests SBuf::rfind(string needle, pos) +void +SBufFindTest::testRFind() { + theFindString = theStringHay.rfind(theStringNeedle, thePos); + theBareNeedlePos = theStringHay.rfind(theStringNeedle); + theFindSBuf = theSBufHay.rfind(theSBufNeedle, thePos); + checkResults("rfind"); +} + +/// tests SBuf::find(char needle) +void +SBufFindTest::testFindCharDefs() { + const char c = theStringNeedle[0]; + theFindString = theBareNeedlePos = theStringHay.find(c); + theFindSBuf = theSBufHay.find(c); + checkResults("find"); +} + +/// tests SBuf::find(char needle, pos) +void +SBufFindTest::testFindChar() { + const char c = theStringNeedle[0]; + theFindString = theStringHay.find(c, thePos); + theBareNeedlePos = theStringHay.find(c); + theFindSBuf = theSBufHay.find(c, thePos); + checkResults("find"); +} + +/// tests SBuf::rfind(char needle) +void +SBufFindTest::testRFindCharDefs() { + const char c = theStringNeedle[0]; + theFindString = theBareNeedlePos = theStringHay.rfind(c); + theFindSBuf = theSBufHay.rfind(c); + checkResults("rfind"); +} + +/// tests SBuf::rfind(char needle, pos) +void +SBufFindTest::testRFindChar() { + const char c = theStringNeedle[0]; + theFindString = theStringHay.rfind(c, thePos); + theBareNeedlePos = theStringHay.rfind(c); + theFindSBuf = theSBufHay.rfind(c, thePos); + checkResults("rfind"); +} + +/// whether the last SBuf and std::string find() results are the same +bool +SBufFindTest::resultsMatch() const { + // this method is needed because SBuf and std::string use different + // size_types (and npos values); comparing the result values directly + // would lead to bugs + + if (theFindString == std::string::npos && theFindSBuf == SBuf::npos) + return true; // both npos + + if (theFindSBuf < 0) // should not happen, treat as error + return false; + + // now safe to cast a non-negative SBuf result + return theFindString == static_cast<std::string::size_type>(theFindSBuf); +} + +/// called at the end of test case to update state, detect and report failures +void +SBufFindTest::checkResults(const char *method) { + ++caseCount; + if (!resultsMatch()) + handleFailure(method); +} + +/// helper function to convert "printable" Type to std::string +template<typename Type> +inline std::string +AnyToString(const Type &value) +{ + std::stringstream sbuf; + sbuf << value; + return sbuf.str(); +} + +/// helper function to convert SBuf position to a human-friendly string +inline std::string +PosToString(const SBuf::size_type pos) +{ + return pos == SBuf::npos ? std::string("npos") : AnyToString(pos); +} + +/// helper function to convert std::string position to a human-friendly string +inline std::string +PosToString(const std::string::size_type pos) +{ + return pos == std::string::npos ? std::string("npos") : AnyToString(pos); +} + +/// tests each supported SBuf::*find() method using generated hay, needle, pos +void +SBufFindTest::testAllMethods() { + theStringHay = std::string(theSBufHay.rawContent(), theSBufHay.length()); + theStringNeedle = std::string(theSBufNeedle.rawContent(), theSBufNeedle.length()); + theBareNeedlePos = std::string::npos; + const std::string reportPos = PosToString(thePos); + + // always test string search + { + theReportQuote = '"'; + theReportNeedle = theStringNeedle; + + theReportPos = ""; + testFindDefs(); + testRFindDefs(); + + theReportPos = reportPos; + testFind(); + testRFind(); + } + + // if possible, test char search + if (!theStringNeedle.empty()) { + theReportQuote = '\''; + theReportNeedle = theStringNeedle[0]; + + theReportPos = ""; + testFindCharDefs(); + testRFindCharDefs(); + + theReportPos = reportPos; + testFindChar(); + testRFindChar(); + } +} + +/// helper function to format a length-based key (part of case category string) +inline std::string +lengthKey(const std::string &str) +{ + if (str.length() == 0) + return "0"; + if (str.length() == 1) + return "1"; + return "N"; +} + +/// formats position key (part of the case category string) +std::string +SBufFindTest::posKey() const +{ + // the search position does not matter if needle is not in hay + if (theBareNeedlePos == std::string::npos) + return std::string(); + + if (thePos == SBuf::npos) + return ",npos"; + + if (thePos < 0) + return ",posN"; // negative + + // we know Pos is not negative or special; avoid signed/unsigned warnings + const std::string::size_type pos = + static_cast<std::string::size_type>(thePos); + + if (pos < theBareNeedlePos) + return ",posL"; // to the Left of the needle + if (pos == theBareNeedlePos) + return ",posB"; // Beginning of the needle + if (pos < theBareNeedlePos + theStringNeedle.length()) + return ",posM"; // in the Middle of the needle + if (pos == theBareNeedlePos + theStringNeedle.length()) + return ",posE"; // at the End of the needle + if (pos < theStringHay.length()) + return ",posR"; // to the Right of the needle + return ",posP"; // past the hay +} + +/// formats placement key (part of the case category string) +std::string +SBufFindTest::placementKey() const +{ + // Ignore thePlacement because theBareNeedlePos covers it better: we may + // try to place the needle somewhere, but hay limits the actual placement. + + // the placent does not matter if needle is not in hay + if (theBareNeedlePos == std::string::npos) + return std::string(); + + if (theBareNeedlePos == 0) + return "@B"; // at the beggining of the hay string + if (theBareNeedlePos == theStringHay.length()-theStringNeedle.length()) + return "@E"; // at the end of the hay string + return "@M"; // in the "middle" of the hay string +} + +/// called when a test case fails; counts and possibly reports the failure +void +SBufFindTest::handleFailure(const char *method) { + // line break after "........." printed for previous tests + if (!errorCount) + std::cerr << std::endl; + + ++errorCount; + + if (errorCount > errorLimit) { + std::cerr << "Will stop generating SBuf test cases because the " << + "number of failed ones is over the limit: " << errorCount << + " (after " << caseCount << " test cases)" << std::endl; + CPPUNIT_ASSERT(errorCount <= errorLimit); + /* NOTREACHED */ + } + + // format test case category; category allows us to hush failure reports + // for already seen categories with failed cases (to reduce output noise) + std::string category = "hay" + lengthKey(theStringHay) + + "." + method + '('; + if (theReportQuote == '"') + category += "needle" + lengthKey(theStringNeedle); + else + category += "char"; + category += placementKey(); + category += posKey(); + category += ')'; + + if (hushSimilar) { + if (failedCats.find(category) != failedCats.end()) + return; // do not report another similar test case failure + failedCats.insert(category); + } + + std::string reportPos = theReportPos; + if (!reportPos.empty()) + reportPos = ", " + reportPos; + + std::cerr << "case" << caseCount << ": " << + "SBuf(\"" << theStringHay << "\")." << method << + "(" << theReportQuote << theReportNeedle << theReportQuote << + reportPos << ") returns " << PosToString(theFindSBuf) << + " instead of " << PosToString(theFindString) << + std::endl << + " std::string(\"" << theStringHay << "\")." << method << + "(" << theReportQuote << theReportNeedle << theReportQuote << + reportPos << ") returns " << PosToString(theFindString) << + std::endl << + " category: " << category << std::endl; + + ++reportCount; +} + +/// generates a random string of the specified length +SBuf +SBufFindTest::RandomSBuf(const int length) { + static const char characters[] = + "0123456789" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + "abcdefghijklomnpqrstuvwxyz"; + // sizeof() counts the terminating zero at the end of characters + // TODO: add \0 character (needs reporting adjustments to print it as \0) + static const size_t charCount = sizeof(characters)-1; + + char buf[length]; + for (int i = 0; i < length; ++i) { + const unsigned int pos = random() % charCount; + assert(pos < sizeof(characters)); + assert(characters[pos] > 32); + buf[i] = characters[random() % charCount]; + } + + return SBuf(buf, 0, length); +} + +/// increments len to quickly cover [0, max] range, slowing down in risky areas +/// jumps to max+1 if caseLimit is reached +void +SBufFindTest::nextLen(int &len, const int max) { + assert(len <= max); + + if (caseCount >= caseLimit) + len = max+1; // avoid future test cases + else if (len <= 10) + ++len; // move slowly at the beginning of the [0,max] range + else if (len >= max - 10) + ++len; // move slowly at the end of the [0,max] range + else { + // move fast in the middle of the [0,max] range + len += len/10 + 1; + + // but do not overshoot the interesting area at the end of the range + if (len > max - 10) + len = max - 10; + } +} + +/// Places the needle into the hay using cleanHay as a starting point. +void +SBufFindTest::placeNeedle(const SBuf &cleanHay) { + // For simplicity, we do not overwrite clean hay characters but use them as + // needle suffix and/or prefix. Should not matter since hay length varies? + + // TODO: support two needles per hay (explicitly) + // TODO: better handle cases where clean hay already contains needle + switch (thePlacement) + { + case placeBeginning: + theSBufHay.assign(theSBufNeedle).append(cleanHay); + break; + + case placeMiddle: + { + const SBuf firstHalf = cleanHay.substr(0, cleanHay.length()/2); + const SBuf secondHalf = cleanHay.substr(cleanHay.length()/2); + theSBufHay.assign(firstHalf).append(theSBufNeedle).append(secondHalf); + break; + } + + case placeEnd: + theSBufHay.assign(cleanHay).append(theSBufNeedle); + break; + + case placeNowhere: + theSBufHay.assign(cleanHay); + break; + + case placeEof: + assert(false); // should not happen + break; + } +} === added file 'src/tests/SBufFindTest.h' --- src/tests/SBufFindTest.h 1970-01-01 00:00:00 +0000 +++ src/tests/SBufFindTest.h 2013-02-25 22:02:43 +0000 @@ -0,0 +1,83 @@ +#ifndef SQUID_SRC_TEST_SBUFFINDTEST_H +#define SQUID_SRC_TEST_SBUFFINDTEST_H + +#include "SBuf.h" + +#if HAVE_STRING +#include <string> +#endif + + +/// Generates and executes a [configurable] large number of SBuf::*find() +/// test cases using random strings. Reports detected failures. +class SBufFindTest +{ +public: + SBufFindTest(); + + void run(); ///< generates and executes cases using configuration params + + /* test configuration parameters; can be optionally set before run() */ + int caseLimit; ///< approximate caseCount limit + int errorLimit; ///< errorCount limit + unsigned int randomSeed; ///< pseudo-random sequence choice + /// whether to report only one failed test case per "category" + bool hushSimilar; + /// approximate maximum generated hay string length + SBuf::size_type maxHayLength; + +protected: + /// Supported algorithms for placing needle in the hay. + typedef enum { placeBeginning, placeMiddle, placeEnd, placeNowhere, + placeEof } Placement; // placeLast marker must terminate + + static SBuf RandomSBuf(const int length); + void nextLen(int &len, const int max); + void placeNeedle(const SBuf &cleanHay); + + void testAllMethods(); + void testFindDefs(); + void testFind(); + void testRFindDefs(); + void testRFind(); + void testFindCharDefs(); + void testFindChar(); + void testRFindCharDefs(); + void testRFindChar(); + + std::string posKey() const; + std::string placementKey() const; + + bool resultsMatch() const; + void checkResults(const char *method); + void handleFailure(const char *method); + +private: + /* test case parameters */ + SBuf theSBufHay; ///< the string to be searched + SBuf theSBufNeedle; ///< the string to be found + SBuf::size_type thePos; ///< search position limit + Placement thePlacement; ///< where in the hay the needle is placed + std::string::size_type theStringPos; ///< thePos converted to std::string::size_type + std::string theStringHay; ///< theHay converted to std::string + std::string theStringNeedle; ///< theNeedle converted to std::string + + /// needle pos w/o thePos restrictions; used for case categorization + std::string::size_type theBareNeedlePos; + + /* test case results */ + std::string::size_type theFindString; + SBuf::size_type theFindSBuf; + std::string theReportFunc; + std::string theReportNeedle; + std::string theReportPos; + char theReportQuote; + + /* test progress indicators */ + int caseCount; ///< cases executed so far + int errorCount; ///< total number of failed test cases so far + int reportCount; ///< total number of test cases reported so far + std::set<std::string> failedCats; ///< reported failed categories +}; + +#endif === modified file 'src/tests/testSBuf.cc' --- src/tests/testSBuf.cc 2013-02-24 21:04:30 +0000 +++ src/tests/testSBuf.cc 2013-02-25 17:43:43 +0000 @@ -1,29 +1,30 @@ #include "squid.h" #include "Mem.h" #include "SBuf.h" #include "SBufList.h" #include "SBufStream.h" #include "SBufTokenizer.h" #include "SBufUtil.h" #include "SquidString.h" #include "testSBuf.h" +#include "SBufFindTest.h" #include <iostream> #include <stdexcept> CPPUNIT_TEST_SUITE_REGISTRATION( testSBuf ); /* let this test link sanely */ #include "event.h" #include "MemObject.h" void eventAdd(const char *name, EVH * func, void *arg, double when, int, bool cbdata) {} int64_t MemObject::endOffset() const { return 0; } /* end of stubs */ // test string static char fox[]="The quick brown fox jumped over the lazy dog"; static char fox1[]="The quick brown fox "; @@ -560,20 +561,26 @@ { SBuf haystack(literal); SBuf::size_type idx; // not found idx=haystack.find_first_of(SBuf("ADHRWYP")); CPPUNIT_ASSERT(idx==SBuf::npos); // found at beginning idx=haystack.find_first_of(SBuf("THANDF")); CPPUNIT_ASSERT_EQUAL(0,idx); //found at end of haystack idx=haystack.find_first_of(SBuf("QWERYVg")); CPPUNIT_ASSERT_EQUAL(haystack.length()-1,idx); //found in the middle of haystack idx=haystack.find_first_of(SBuf("QWERqYV")); CPPUNIT_ASSERT_EQUAL(4,idx); } + +void testSBuf::testAutoFind() +{ + SBufFindTest test; + test.run(); +} === modified file 'src/tests/testSBuf.h' --- src/tests/testSBuf.h 2012-12-16 22:01:40 +0000 +++ src/tests/testSBuf.h 2013-02-24 18:21:33 +0000 @@ -33,40 +33,41 @@ CPPUNIT_TEST( testConsume ); CPPUNIT_TEST( testRawContent ); //CPPUNIT_TEST( testRawSpace ); CPPUNIT_TEST( testChop ); CPPUNIT_TEST( testChomp ); CPPUNIT_TEST( testSubstr ); CPPUNIT_TEST( testFindChar ); CPPUNIT_TEST( testFindSBuf ); CPPUNIT_TEST( testRFindChar ); CPPUNIT_TEST( testRFindSBuf ); CPPUNIT_TEST( testFindFirstOf ); CPPUNIT_TEST( testPrintf ); CPPUNIT_TEST( testScanf ); CPPUNIT_TEST( testCopy ); CPPUNIT_TEST( testSBufTokenizer ); CPPUNIT_TEST( testStringOps ); CPPUNIT_TEST( testGrow ); CPPUNIT_TEST( testSBufList ); CPPUNIT_TEST( testBaseName ); CPPUNIT_TEST( testSBufStream ); + CPPUNIT_TEST( testAutoFind ); // CPPUNIT_TEST( testDumpStats ); //fake test, to print alloc stats CPPUNIT_TEST_SUITE_END(); protected: void commonInit(); void testSBufConstructDestruct(); void testSBufConstructDestructAfterMemInit(); void testEqualityTest(); void testAppendSBuf(); void testAppendCString(); void testAppendStdString(); void testAppendf(); void testPrintf(); void testScanf(); void testSubscriptOp(); void testSubscriptOpFail(); void testDumpStats(); void testComparisons(); void testConsume(); @@ -74,23 +75,24 @@ void testRawSpace(); void testChop(); void testChomp(); void testSubstr(); void testTailCopy(); void testSBufLength(); void testFindChar(); void testFindSBuf(); void testRFindChar(); void testRFindSBuf(); void testSearchFail(); void testCopy(); void testSBufTokenizer(); void testStringOps(); void testGrow(); void testStartsWith(); void testSBufList(); void testBaseName(); void testSBufStream(); void testFindFirstOf(); + void testAutoFind(); }; #endif