From bd851333e89517762c91a3fef67cf25a6f1bd37a Mon Sep 17 00:00:00 2001 From: "zhanyong.wan" Date: Wed, 30 Sep 2009 23:46:28 +0000 Subject: Implements test shuffling (by Zhanyong Wan, based on Josh Kelley's original patch). Enables death tests on minGW (by Vlad Losev). --- Makefile.am | 25 ++- include/gtest/gtest.h | 28 ++- include/gtest/internal/gtest-port.h | 2 +- scons/SConscript | 1 + src/gtest-internal-inl.h | 139 ++++++++++++--- src/gtest.cc | 106 ++++++++++-- test/gtest-death-test_test.cc | 8 +- test/gtest_shuffle_test.py | 331 ++++++++++++++++++++++++++++++++++++ test/gtest_shuffle_test_.cc | 104 +++++++++++ test/gtest_unittest.cc | 301 +++++++++++++++++++++++++++++++- 10 files changed, 986 insertions(+), 59 deletions(-) create mode 100755 test/gtest_shuffle_test.py create mode 100644 test/gtest_shuffle_test_.cc diff --git a/Makefile.am b/Makefile.am index 0b829ed..3a9233d 100644 --- a/Makefile.am +++ b/Makefile.am @@ -173,22 +173,29 @@ TESTS += samples/sample6_unittest check_PROGRAMS += samples/sample6_unittest samples_sample6_unittest_SOURCES = samples/prime_tables.h \ samples/sample6_unittest.cc -samples_sample6_unittest_LDADD = lib/libgtest_main.la \ - samples/libsamples.la +samples_sample6_unittest_LDADD = lib/libgtest_main.la TESTS += samples/sample7_unittest check_PROGRAMS += samples/sample7_unittest samples_sample7_unittest_SOURCES = samples/prime_tables.h \ samples/sample7_unittest.cc -samples_sample7_unittest_LDADD = lib/libgtest_main.la \ - samples/libsamples.la +samples_sample7_unittest_LDADD = lib/libgtest_main.la TESTS += samples/sample8_unittest check_PROGRAMS += samples/sample8_unittest samples_sample8_unittest_SOURCES = samples/prime_tables.h \ samples/sample8_unittest.cc -samples_sample8_unittest_LDADD = lib/libgtest_main.la \ - samples/libsamples.la +samples_sample8_unittest_LDADD = lib/libgtest_main.la + +TESTS += samples/sample9_unittest +check_PROGRAMS += samples/sample9_unittest +samples_sample9_unittest_SOURCES = samples/sample9_unittest.cc +samples_sample9_unittest_LDADD = lib/libgtest.la + +TESTS += samples/sample10_unittest +check_PROGRAMS += samples/sample10_unittest +samples_sample10_unittest_SOURCES = samples/sample10_unittest.cc +samples_sample10_unittest_LDADD = lib/libgtest.la TESTS += test/gtest-death-test_test check_PROGRAMS += test/gtest-death-test_test @@ -388,6 +395,12 @@ EXTRA_DIST += test/gtest_output_test_golden_lin.txt \ test/gtest_output_test_golden_win.txt TESTS += test/gtest_output_test.py +check_PROGRAMS += test/gtest_shuffle_test_ +test_gtest_shuffle_test__SOURCES = test/gtest_shuffle_test_.cc +test_gtest_shuffle_test__LDADD = lib/libgtest.la +check_SCRIPTS += test/gtest_shuffle_test.py +TESTS += test/gtest_shuffle_test.py + check_PROGRAMS += test/gtest_throw_on_failure_test_ test_gtest_throw_on_failure_test__SOURCES = \ test/gtest_throw_on_failure_test_.cc \ diff --git a/include/gtest/gtest.h b/include/gtest/gtest.h index 6fc5ac5..9be15fb 100644 --- a/include/gtest/gtest.h +++ b/include/gtest/gtest.h @@ -127,7 +127,7 @@ GTEST_DECLARE_int32_(repeat); // stack frames in failure stack traces. GTEST_DECLARE_bool_(show_internal_stack_frames); -// When this flag is specified, tests' order is randomized on every run. +// When this flag is specified, tests' order is randomized on every iteration. GTEST_DECLARE_bool_(shuffle); // This flag specifies the maximum number of stack frames to be @@ -675,6 +675,10 @@ class TestCase { return *test_info_list_; } + // Returns the i-th test among all the tests. i can range from 0 to + // total_test_count() - 1. If i is not in that range, returns NULL. + TestInfo* GetMutableTestInfo(int i); + // Sets the should_run member. void set_should_run(bool should) { should_run_ = should; } @@ -693,9 +697,6 @@ class TestCase { // Runs every test in this TestCase. void Run(); - // Runs every test in the given TestCase. - static void RunTestCase(TestCase * test_case) { test_case->Run(); } - // Returns true iff test passed. static bool TestPassed(const TestInfo * test_info); @@ -708,12 +709,23 @@ class TestCase { // Returns true if the given test should run. static bool ShouldRunTest(const TestInfo *test_info); + // Shuffles the tests in this test case. + void ShuffleTests(internal::Random* random); + + // Restores the test order to before the first shuffle. + void UnshuffleTests(); + // Name of the test case. internal::String name_; // Comment on the test case. internal::String comment_; - // Vector of TestInfos. - internal::Vector* test_info_list_; + // The vector of TestInfos in their original order. It owns the + // elements in the vector. + const internal::scoped_ptr > test_info_list_; + // Provides a level of indirection for the test list to allow easy + // shuffling and restoring the test order. The i-th element in this + // vector is the index of the i-th test in the shuffled test list. + const internal::scoped_ptr > test_indices_; // Pointer to the function that sets up the test case. Test::SetUpTestCaseFunc set_up_tc_; // Pointer to the function that tears down the test case. @@ -1030,6 +1042,10 @@ class UnitTest { // contains a property with the same key, the value will be updated. void RecordPropertyForCurrentTest(const char* key, const char* value); + // Gets the i-th test case among all the test cases. i can range from 0 to + // total_test_case_count() - 1. If i is not in that range, returns NULL. + TestCase* GetMutableTestCase(int i); + // Accessors for the implementation object. internal::UnitTestImpl* impl() { return impl_; } const internal::UnitTestImpl* impl() const { return impl_; } diff --git a/include/gtest/internal/gtest-port.h b/include/gtest/internal/gtest-port.h index ac460ee..ee97881 100644 --- a/include/gtest/internal/gtest-port.h +++ b/include/gtest/internal/gtest-port.h @@ -461,7 +461,7 @@ // pops up a dialog window that cannot be suppressed programmatically. #if GTEST_HAS_STD_STRING && \ (GTEST_OS_LINUX || GTEST_OS_MAC || GTEST_OS_CYGWIN || \ - (GTEST_OS_WINDOWS_DESKTOP && _MSC_VER >= 1400)) + (GTEST_OS_WINDOWS_DESKTOP && _MSC_VER >= 1400) || GTEST_OS_WINDOWS_MINGW) #define GTEST_HAS_DEATH_TEST 1 #include // NOLINT #endif diff --git a/scons/SConscript b/scons/SConscript index f0d4fe4..51a7584 100644 --- a/scons/SConscript +++ b/scons/SConscript @@ -372,6 +372,7 @@ GtestTest(env, 'gtest_xml_outfile2_test_', gtest_main) GtestTest(env, 'gtest_xml_output_unittest_', gtest) GtestTest(env, 'gtest-unittest-api_test', gtest) GtestTest(env, 'gtest-listener_test', gtest) +GtestTest(env, 'gtest_shuffle_test_', gtest) ############################################################ # Tests targets using custom environments. diff --git a/src/gtest-internal-inl.h b/src/gtest-internal-inl.h index d593e82..9a366fe 100644 --- a/src/gtest-internal-inl.h +++ b/src/gtest-internal-inl.h @@ -277,7 +277,7 @@ class Vector { // is created using the copy constructor, and then stored in the // Vector. Changes made to the element in the Vector doesn't affect // the source object, and vice versa. - void PushBack(const E & element) { Insert(element, size_); } + void PushBack(const E& element) { Insert(element, size_); } // Adds an element to the beginning of this Vector. void PushFront(const E& element) { Insert(element, 0); } @@ -369,7 +369,7 @@ class Vector { return NULL; } - // Returns the i-th element of the list, or aborts the program if i + // Returns the i-th element of the Vector, or aborts the program if i // is not in range [0, size()). const E& GetElement(int i) const { GTEST_CHECK_(0 <= i && i < size_) @@ -379,13 +379,84 @@ class Vector { return *(elements_[i]); } - // Returns the i-th element of the list, or default_value if i is not + // Returns a mutable reference to the i-th element of the Vector, or + // aborts the program if i is not in range [0, size()). + E& GetMutableElement(int i) { + GTEST_CHECK_(0 <= i && i < size_) + << "Invalid Vector index " << i << ": must be in range [0, " + << (size_ - 1) << "]."; + + return *(elements_[i]); + } + + // Returns the i-th element of the Vector, or default_value if i is not // in range [0, size()). E GetElementOr(int i, E default_value) const { return (i < 0 || i >= size_) ? default_value : *(elements_[i]); } + // Swaps the i-th and j-th elements of the Vector. Crashes if i or + // j is invalid. + void Swap(int i, int j) { + GTEST_CHECK_(0 <= i && i < size_) + << "Invalid first swap element " << i << ": must be in range [0, " + << (size_ - 1) << "]."; + GTEST_CHECK_(0 <= j && j < size_) + << "Invalid second swap element " << j << ": must be in range [0, " + << (size_ - 1) << "]."; + + E* const temp = elements_[i]; + elements_[i] = elements_[j]; + elements_[j] = temp; + } + + // Performs an in-place shuffle of a range of this Vector's nodes. + // 'begin' and 'end' are element indices as an STL-style range; + // i.e. [begin, end) are shuffled, where 'end' == size() means to + // shuffle to the end of the Vector. + void ShuffleRange(internal::Random* random, int begin, int end) { + GTEST_CHECK_(0 <= begin && begin <= size_) + << "Invalid shuffle range start " << begin << ": must be in range [0, " + << size_ << "]."; + GTEST_CHECK_(begin <= end && end <= size_) + << "Invalid shuffle range finish " << end << ": must be in range [" + << begin << ", " << size_ << "]."; + + // Fisher-Yates shuffle, from + // http://en.wikipedia.org/wiki/Fisher-Yates_shuffle + for (int range_width = end - begin; range_width >= 2; range_width--) { + const int last_in_range = begin + range_width - 1; + const int selected = begin + random->Generate(range_width); + Swap(selected, last_in_range); + } + } + + // Performs an in-place shuffle of this Vector's nodes. + void Shuffle(internal::Random* random) { + ShuffleRange(random, 0, size()); + } + + // Returns a copy of this Vector. + Vector* Clone() const { + Vector* const clone = new Vector; + clone->Reserve(size_); + for (int i = 0; i < size_; i++) { + clone->PushBack(GetElement(i)); + } + return clone; + } + private: + // Makes sure this Vector's capacity is at least the given value. + void Reserve(int new_capacity) { + if (new_capacity <= capacity_) + return; + + capacity_ = new_capacity; + elements_ = static_cast( + realloc(elements_, capacity_*sizeof(elements_[0]))); + } + // Grows the buffer if it is not big enough to hold one more element. void GrowIfNeeded() { if (size_ < capacity_) @@ -397,9 +468,7 @@ class Vector { const int new_capacity = 3*(capacity_/2 + 1); GTEST_CHECK_(new_capacity > capacity_) // Does the new capacity overflow? << "Cannot grow a Vector with " << capacity_ << " elements already."; - capacity_ = new_capacity; - elements_ = static_cast( - realloc(elements_, capacity_*sizeof(elements_[0]))); + Reserve(new_capacity); } // Moves the give consecutive elements to a new index in the Vector. @@ -491,11 +560,6 @@ class TestInfoImpl { // deletes it. void Run(); - // Calls the given TestInfo object's Run() method. - static void RunTest(TestInfo * test_info) { - test_info->impl()->Run(); - } - // Clears the test result. void ClearResult() { result_.Clear(); } @@ -738,7 +802,15 @@ class UnitTestImpl { // Gets the i-th test case among all the test cases. i can range from 0 to // total_test_case_count() - 1. If i is not in that range, returns NULL. const TestCase* GetTestCase(int i) const { - return test_cases_.GetElementOr(i, NULL); + const int index = test_case_indices_.GetElementOr(i, -1); + return index < 0 ? NULL : test_cases_.GetElement(i); + } + + // Gets the i-th test case among all the test cases. i can range from 0 to + // total_test_case_count() - 1. If i is not in that range, returns NULL. + TestCase* GetMutableTestCase(int i) { + const int index = test_case_indices_.GetElementOr(i, -1); + return index < 0 ? NULL : test_cases_.GetElement(index); } // Provides access to the event listener list. @@ -886,9 +958,6 @@ class UnitTestImpl { return &environments_in_reverse_order_; } - internal::Vector* test_cases() { return &test_cases_; } - const internal::Vector* test_cases() const { return &test_cases_; } - // Getters for the per-thread Google Test trace stack. internal::Vector* gtest_trace_stack() { return gtest_trace_stack_.pointer(); @@ -923,16 +992,26 @@ class UnitTestImpl { // UnitTestOptions. Must not be called before InitGoogleTest. void ConfigureXmlOutput(); -// Performs initialization dependent upon flag values obtained in -// ParseGoogleTestFlagsOnly. Is called from InitGoogleTest after the call to -// ParseGoogleTestFlagsOnly. In case a user neglects to call InitGoogleTest -// this function is also called from RunAllTests. Since this function can be -// called more than once, it has to be idempotent. + // Performs initialization dependent upon flag values obtained in + // ParseGoogleTestFlagsOnly. Is called from InitGoogleTest after the call to + // ParseGoogleTestFlagsOnly. In case a user neglects to call InitGoogleTest + // this function is also called from RunAllTests. Since this function can be + // called more than once, it has to be idempotent. void PostFlagParsingInit(); - // Gets the random seed used at the start of the current test run. + // Gets the random seed used at the start of the current test iteration. int random_seed() const { return random_seed_; } + // Gets the random number generator. + internal::Random* random() { return &random_; } + + // Shuffles all test cases, and the tests within each test case, + // making sure that death tests are still run first. + void ShuffleTests(); + + // Restores the test cases and tests to their order before the first shuffle. + void UnshuffleTests(); + private: friend class ::testing::UnitTest; @@ -964,7 +1043,15 @@ class UnitTestImpl { internal::Vector environments_; internal::Vector environments_in_reverse_order_; - internal::Vector test_cases_; // The vector of TestCases. + // The vector of TestCases in their original order. It owns the + // elements in the vector. + internal::Vector test_cases_; + + // Provides a level of indirection for the test case list to allow + // easy shuffling and restoring the test case order. The i-th + // element of this vector is the index of the i-th test case in the + // shuffled order. + internal::Vector test_case_indices_; #if GTEST_HAS_PARAM_TEST // ParameterizedTestRegistry object used to register value-parameterized @@ -1016,6 +1103,9 @@ class UnitTestImpl { // The random number seed used at the beginning of the test run. int random_seed_; + // Our random number generator. + internal::Random random_; + // How long the test took to run, in milliseconds. TimeInMillis elapsed_time_; @@ -1108,13 +1198,14 @@ bool ParseNaturalNumber(const ::std::string& str, Integer* number) { char* end; // BiggestConvertible is the largest integer type that system-provided // string-to-number conversion routines can return. -#if GTEST_OS_WINDOWS +#if GTEST_OS_WINDOWS && !defined(__GNU_C__) + // MSVC and C++ Builder define __int64 instead of the standard long long. typedef unsigned __int64 BiggestConvertible; const BiggestConvertible parsed = _strtoui64(str.c_str(), &end, 10); #else typedef unsigned long long BiggestConvertible; // NOLINT const BiggestConvertible parsed = strtoull(str.c_str(), &end, 10); -#endif // GTEST_OS_WINDOWS +#endif // GTEST_OS_WINDOWS && !defined(__GNU_C__) const bool parse_success = *end == '\0' && errno == 0; // TODO(vladl@google.com): Convert this to compile time assertion when it is diff --git a/src/gtest.cc b/src/gtest.cc index f0d8c38..9340724 100644 --- a/src/gtest.cc +++ b/src/gtest.cc @@ -2343,33 +2343,39 @@ TestCase::TestCase(const char* name, const char* comment, Test::TearDownTestCaseFunc tear_down_tc) : name_(name), comment_(comment), + test_info_list_(new internal::Vector), + test_indices_(new internal::Vector), set_up_tc_(set_up_tc), tear_down_tc_(tear_down_tc), should_run_(false), elapsed_time_(0) { - test_info_list_ = new internal::Vector; } // Destructor of TestCase. TestCase::~TestCase() { // Deletes every Test in the collection. test_info_list_->ForEach(internal::Delete); - - // Then deletes the Test collection. - delete test_info_list_; - test_info_list_ = NULL; } // Returns the i-th test among all the tests. i can range from 0 to // total_test_count() - 1. If i is not in that range, returns NULL. const TestInfo* TestCase::GetTestInfo(int i) const { - return test_info_list_->GetElementOr(i, NULL); + const int index = test_indices_->GetElementOr(i, -1); + return index < 0 ? NULL : test_info_list_->GetElement(index); +} + +// Returns the i-th test among all the tests. i can range from 0 to +// total_test_count() - 1. If i is not in that range, returns NULL. +TestInfo* TestCase::GetMutableTestInfo(int i) { + const int index = test_indices_->GetElementOr(i, -1); + return index < 0 ? NULL : test_info_list_->GetElement(index); } // Adds a test to this test case. Will delete the test upon // destruction of the TestCase object. void TestCase::AddTestInfo(TestInfo * test_info) { test_info_list_->PushBack(test_info); + test_indices_->PushBack(test_indices_->size()); } // Runs every test in this TestCase. @@ -2386,7 +2392,9 @@ void TestCase::Run() { set_up_tc_(); const internal::TimeInMillis start = internal::GetTimeInMillis(); - test_info_list_->ForEach(internal::TestInfoImpl::RunTest); + for (int i = 0; i < total_test_count(); i++) { + GetMutableTestInfo(i)->impl()->Run(); + } elapsed_time_ = internal::GetTimeInMillis() - start; impl->os_stack_trace_getter()->UponLeavingGTest(); @@ -2422,6 +2430,18 @@ bool TestCase::ShouldRunTest(const TestInfo *test_info) { return test_info->impl()->should_run(); } +// Shuffles the tests in this test case. +void TestCase::ShuffleTests(internal::Random* random) { + test_indices_->Shuffle(random); +} + +// Restores the test order to before the first shuffle. +void TestCase::UnshuffleTests() { + for (int i = 0; i < test_indices_->size(); i++) { + test_indices_->GetMutableElement(i) = i; + } +} + // Formats a countable noun. Depending on its quantity, either the // singular form or the plural form is used. e.g. // @@ -3465,6 +3485,12 @@ const TestCase* UnitTest::GetTestCase(int i) const { return impl()->GetTestCase(i); } +// Gets the i-th test case among all the test cases. i can range from 0 to +// total_test_case_count() - 1. If i is not in that range, returns NULL. +TestCase* UnitTest::GetMutableTestCase(int i) { + return impl()->GetMutableTestCase(i); +} + // Returns the list of event listeners that can be used to track events // inside Google Test. TestEventListeners& UnitTest::listeners() { @@ -3717,7 +3743,6 @@ UnitTestImpl::UnitTestImpl(UnitTest* parent) &default_global_test_part_result_reporter_), per_thread_test_part_result_reporter_( &default_per_thread_test_part_result_reporter_), - test_cases_(), #if GTEST_HAS_PARAM_TEST parameterized_test_registry_(), parameterized_tests_registered_(false), @@ -3728,7 +3753,8 @@ UnitTestImpl::UnitTestImpl(UnitTest* parent) ad_hoc_test_result_(), os_stack_trace_getter_(NULL), post_flag_parse_init_performed_(false), - random_seed_(0), + random_seed_(0), // Will be overridden by the flag before first use. + random_(0), // Will be reseeded before first use. #if GTEST_HAS_DEATH_TEST elapsed_time_(0), internal_run_death_test_flag_(NULL), @@ -3822,7 +3848,9 @@ class TestCaseNameIs { }; // Finds and returns a TestCase with the given name. If one doesn't -// exist, creates one and returns it. +// exist, creates one and returns it. It's the CALLER'S +// RESPONSIBILITY to ensure that this function is only called WHEN THE +// TESTS ARE NOT SHUFFLED. // // Arguments: // @@ -3847,13 +3875,16 @@ TestCase* UnitTestImpl::GetTestCase(const char* test_case_name, if (internal::UnitTestOptions::MatchesFilter(String(test_case_name), kDeathTestCaseFilter)) { // Yes. Inserts the test case after the last death test case - // defined so far. + // defined so far. This only works when the test cases haven't + // been shuffled. Otherwise we may end up running a death test + // after a non-death test. test_cases_.Insert(new_test_case, ++last_death_test_case_); } else { // No. Appends to the end of the list. test_cases_.PushBack(new_test_case); } + test_case_indices_.PushBack(test_case_indices_.size()); return new_test_case; } @@ -3938,6 +3969,15 @@ int UnitTestImpl::RunAllTests() { const TimeInMillis start = GetTimeInMillis(); + // Shuffles test cases and tests if requested. + if (has_tests_to_run && GTEST_FLAG(shuffle)) { + random()->Reseed(random_seed_); + // This should be done before calling OnTestIterationStart(), + // such that a test event listener can see the actual test order + // in the event. + ShuffleTests(); + } + // Tells the unit test event listeners that the tests are about to start. repeater->OnTestIterationStart(*parent_, i); @@ -3951,7 +3991,9 @@ int UnitTestImpl::RunAllTests() { // Runs the tests only if there was no fatal failure during global // set-up. if (!Test::HasFatalFailure()) { - test_cases_.ForEach(TestCase::RunTestCase); + for (int i = 0; i < total_test_case_count(); i++) { + GetMutableTestCase(i)->Run(); + } } // Tears down all environments in reverse order afterwards. @@ -3970,8 +4012,16 @@ int UnitTestImpl::RunAllTests() { failed = true; } + // Restores the original test order after the iteration. This + // allows the user to quickly repro a failure that happens in the + // N-th iteration without repeating the first (N - 1) iterations. + // This is not enclosed in "if (GTEST_FLAG(shuffle)) { ... }", in + // case the user somehow changes the value of the flag somewhere + // (it's always safe to unshuffle the tests). + UnshuffleTests(); + if (GTEST_FLAG(shuffle)) { - // Picks a new random seed for each run. + // Picks a new random seed for each iteration. random_seed_ = GetNextRandomSeed(random_seed_); } } @@ -4187,6 +4237,32 @@ TestResult* UnitTestImpl::current_test_result() { current_test_info_->impl()->result() : &ad_hoc_test_result_; } +// Shuffles all test cases, and the tests within each test case, +// making sure that death tests are still run first. +void UnitTestImpl::ShuffleTests() { + // Shuffles the death test cases. + test_case_indices_.ShuffleRange(random(), 0, last_death_test_case_ + 1); + + // Shuffles the non-death test cases. + test_case_indices_.ShuffleRange(random(), last_death_test_case_ + 1, + test_cases_.size()); + + // Shuffles the tests inside each test case. + for (int i = 0; i < test_cases_.size(); i++) { + test_cases_.GetElement(i)->ShuffleTests(random()); + } +} + +// Restores the test cases and tests to their order before the first shuffle. +void UnitTestImpl::UnshuffleTests() { + for (int i = 0; i < test_cases_.size(); i++) { + // Unshuffles the tests in each test case. + test_cases_.GetElement(i)->UnshuffleTests(); + // Resets the index of each test case. + test_case_indices_.GetMutableElement(i) = i; + } +} + // TestInfoImpl constructor. The new instance assumes ownership of the test // factory object. TestInfoImpl::TestInfoImpl(TestInfo* parent, @@ -4401,8 +4477,8 @@ static const char kColorEncodedHelpMessage[] = "Test Execution:\n" " @G--" GTEST_FLAG_PREFIX_ "repeat=@Y[COUNT]@D\n" " Run the tests repeatedly; use a negative count to repeat forever.\n" -" @G--" GTEST_FLAG_PREFIX_ "shuffle\n" -" Randomize tests' orders on every run. To be implemented.\n" +" @G--" GTEST_FLAG_PREFIX_ "shuffle@D\n" +" Randomize tests' orders on every iteration.\n" " @G--" GTEST_FLAG_PREFIX_ "random_seed=@Y[NUMBER]@D\n" " Random number seed to use for shuffling test orders (between 1 and\n" " 99999, or 0 to use a seed based on the current time).\n" diff --git a/test/gtest-death-test_test.cc b/test/gtest-death-test_test.cc index 7bf6a71..288c70a 100644 --- a/test/gtest-death-test_test.cc +++ b/test/gtest-death-test_test.cc @@ -659,7 +659,11 @@ static void TestExitMacros() { EXPECT_EXIT(_exit(1), testing::ExitedWithCode(1), ""); ASSERT_EXIT(_exit(42), testing::ExitedWithCode(42), ""); -#if GTEST_OS_WINDOWS +#if GTEST_OS_WINDOWS && !GTEST_OS_WINDOWS_MINGW + // MinGW (as of MinGW 5.1.6 and MSYS 1.0.11) does not tag crashed + // processes with non-zero exit code and does not honor calls to + // SetErrorMode(SEM_NOGPFAULTERRORBOX) that are supposed to suppress + // error pop-ups. EXPECT_EXIT({ testing::GTEST_FLAG(catch_exceptions) = false; *static_cast(NULL) = 1; @@ -671,7 +675,9 @@ static void TestExitMacros() { *static_cast(NULL) = 1; }, testing::ExitedWithCode(0), "") << "This failure is expected."; }, "This failure is expected."); +#endif // GTEST_OS_WINDOWS && !GTEST_OS_WINDOWS_MINGW +#if GTEST_OS_WINDOWS // Of all signals effects on the process exit code, only those of SIGABRT // are documented on Windows. // See http://msdn.microsoft.com/en-us/library/dwwzkt4c(VS.71).aspx. diff --git a/test/gtest_shuffle_test.py b/test/gtest_shuffle_test.py new file mode 100755 index 0000000..a870a01 --- /dev/null +++ b/test/gtest_shuffle_test.py @@ -0,0 +1,331 @@ +#!/usr/bin/env python +# +# Copyright 2009 Google Inc. All Rights Reserved. +# +# Redistribution and use in source and binary forms, with or without +# modification, are permitted provided that the following conditions are +# met: +# +# * Redistributions of source code must retain the above copyright +# notice, this list of conditions and the following disclaimer. +# * Redistributions in binary form must reproduce the above +# copyright notice, this list of conditions and the following disclaimer +# in the documentation and/or other materials provided with the +# distribution. +# * Neither the name of Google Inc. nor the names of its +# contributors may be used to endorse or promote products derived from +# this software without specific prior written permission. +# +# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +# "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +# LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +# A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +# OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +# SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +# LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +# DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +# THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +# (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +# OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +"""Verifies that test shuffling works.""" + +__author__ = 'wan@google.com (Zhanyong Wan)' + +import os +import gtest_test_utils + +# Command to run the gtest_shuffle_test_ program. +COMMAND = gtest_test_utils.GetTestExecutablePath('gtest_shuffle_test_') + +# The environment variables for test sharding. +TOTAL_SHARDS_ENV_VAR = 'GTEST_TOTAL_SHARDS' +SHARD_INDEX_ENV_VAR = 'GTEST_SHARD_INDEX' + +TEST_FILTER = 'A*.A:A*.B:C*' + +ALL_TESTS = [] +ACTIVE_TESTS = [] +FILTERED_TESTS = [] +SHARDED_TESTS = [] + +SHUFFLED_ALL_TESTS = [] +SHUFFLED_ACTIVE_TESTS = [] +SHUFFLED_FILTERED_TESTS = [] +SHUFFLED_SHARDED_TESTS = [] + + +def AlsoRunDisabledTestsFlag(): + return '--gtest_also_run_disabled_tests' + + +def FilterFlag(test_filter): + return '--gtest_filter=%s' % (test_filter,) + + +def RepeatFlag(n): + return '--gtest_repeat=%s' % (n,) + + +def ShuffleFlag(): + return '--gtest_shuffle' + + +def RandomSeedFlag(n): + return '--gtest_random_seed=%s' % (n,) + + +def RunAndReturnOutput(extra_env, args): + """Runs the test program and returns its output.""" + + try: + original_env = os.environ.copy() + os.environ.update(extra_env) + return gtest_test_utils.Subprocess([COMMAND] + args).output + finally: + for key in extra_env.iterkeys(): + if key in original_env: + os.environ[key] = original_env[key] + else: + del os.environ[key] + + +def GetTestsForAllIterations(extra_env, args): + """Runs the test program and returns a list of test lists. + + Args: + extra_env: a map from environment variables to their values + args: command line flags to pass to gtest_shuffle_test_ + + Returns: + A list where the i-th element is the list of tests run in the i-th + test iteration. + """ + + test_iterations = [] + for line in RunAndReturnOutput(extra_env, args).split('\n'): + if line.startswith('----'): + tests = [] + test_iterations.append(tests) + elif line.strip(): + tests.append(line.strip()) # 'TestCaseName.TestName' + + return test_iterations + + +def GetTestCases(tests): + """Returns a list of test cases in the given full test names. + + Args: + tests: a list of full test names + + Returns: + A list of test cases from 'tests', in their original order. + Consecutive duplicates are removed. + """ + + test_cases = [] + for test in tests: + test_case = test.split('.')[0] + if not test_case in test_cases: + test_cases.append(test_case) + + return test_cases + + +def CalculateTestLists(): + """Calculates the list of tests run under different flags.""" + + if not ALL_TESTS: + ALL_TESTS.extend( + GetTestsForAllIterations({}, [AlsoRunDisabledTestsFlag()])[0]) + + if not ACTIVE_TESTS: + ACTIVE_TESTS.extend(GetTestsForAllIterations({}, [])[0]) + + if not FILTERED_TESTS: + FILTERED_TESTS.extend( + GetTestsForAllIterations({}, [FilterFlag(TEST_FILTER)])[0]) + + if not SHARDED_TESTS: + SHARDED_TESTS.extend( + GetTestsForAllIterations({TOTAL_SHARDS_ENV_VAR: '3', + SHARD_INDEX_ENV_VAR: '1'}, + [])[0]) + + if not SHUFFLED_ALL_TESTS: + SHUFFLED_ALL_TESTS.extend(GetTestsForAllIterations( + {}, [AlsoRunDisabledTestsFlag(), ShuffleFlag(), RandomSeedFlag(1)])[0]) + + if not SHUFFLED_ACTIVE_TESTS: + SHUFFLED_ACTIVE_TESTS.extend(GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(1)])[0]) + + if not SHUFFLED_FILTERED_TESTS: + SHUFFLED_FILTERED_TESTS.extend(GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(1), FilterFlag(TEST_FILTER)])[0]) + + if not SHUFFLED_SHARDED_TESTS: + SHUFFLED_SHARDED_TESTS.extend( + GetTestsForAllIterations({TOTAL_SHARDS_ENV_VAR: '3', + SHARD_INDEX_ENV_VAR: '1'}, + [ShuffleFlag(), RandomSeedFlag(1)])[0]) + + +class GTestShuffleUnitTest(gtest_test_utils.TestCase): + """Tests test shuffling.""" + + def setUp(self): + CalculateTestLists() + + def testShufflePreservesNumberOfTests(self): + self.assertEqual(len(ALL_TESTS), len(SHUFFLED_ALL_TESTS)) + self.assertEqual(len(ACTIVE_TESTS), len(SHUFFLED_ACTIVE_TESTS)) + self.assertEqual(len(FILTERED_TESTS), len(SHUFFLED_FILTERED_TESTS)) + self.assertEqual(len(SHARDED_TESTS), len(SHUFFLED_SHARDED_TESTS)) + + def testShuffleChangesTestOrder(self): + self.assert_(SHUFFLED_ALL_TESTS != ALL_TESTS, SHUFFLED_ALL_TESTS) + self.assert_(SHUFFLED_ACTIVE_TESTS != ACTIVE_TESTS, SHUFFLED_ACTIVE_TESTS) + self.assert_(SHUFFLED_FILTERED_TESTS != FILTERED_TESTS, + SHUFFLED_FILTERED_TESTS) + self.assert_(SHUFFLED_SHARDED_TESTS != SHARDED_TESTS, + SHUFFLED_SHARDED_TESTS) + + def testShuffleChangesTestCaseOrder(self): + self.assert_(GetTestCases(SHUFFLED_ALL_TESTS) != GetTestCases(ALL_TESTS), + GetTestCases(SHUFFLED_ALL_TESTS)) + self.assert_( + GetTestCases(SHUFFLED_ACTIVE_TESTS) != GetTestCases(ACTIVE_TESTS), + GetTestCases(SHUFFLED_ACTIVE_TESTS)) + self.assert_( + GetTestCases(SHUFFLED_FILTERED_TESTS) != GetTestCases(FILTERED_TESTS), + GetTestCases(SHUFFLED_FILTERED_TESTS)) + self.assert_( + GetTestCases(SHUFFLED_SHARDED_TESTS) != GetTestCases(SHARDED_TESTS), + GetTestCases(SHUFFLED_SHARDED_TESTS)) + + def testShuffleDoesNotRepeatTest(self): + for test in SHUFFLED_ALL_TESTS: + self.assertEqual(1, SHUFFLED_ALL_TESTS.count(test), + '%s appears more than once' % (test,)) + for test in SHUFFLED_ACTIVE_TESTS: + self.assertEqual(1, SHUFFLED_ACTIVE_TESTS.count(test), + '%s appears more than once' % (test,)) + for test in SHUFFLED_FILTERED_TESTS: + self.assertEqual(1, SHUFFLED_FILTERED_TESTS.count(test), + '%s appears more than once' % (test,)) + for test in SHUFFLED_SHARDED_TESTS: + self.assertEqual(1, SHUFFLED_SHARDED_TESTS.count(test), + '%s appears more than once' % (test,)) + + def testShuffleDoesNotCreateNewTest(self): + for test in SHUFFLED_ALL_TESTS: + self.assert_(test in ALL_TESTS, '%s is an invalid test' % (test,)) + for test in SHUFFLED_ACTIVE_TESTS: + self.assert_(test in ACTIVE_TESTS, '%s is an invalid test' % (test,)) + for test in SHUFFLED_FILTERED_TESTS: + self.assert_(test in FILTERED_TESTS, '%s is an invalid test' % (test,)) + for test in SHUFFLED_SHARDED_TESTS: + self.assert_(test in SHARDED_TESTS, '%s is an invalid test' % (test,)) + + def testShuffleIncludesAllTests(self): + for test in ALL_TESTS: + self.assert_(test in SHUFFLED_ALL_TESTS, '%s is missing' % (test,)) + for test in ACTIVE_TESTS: + self.assert_(test in SHUFFLED_ACTIVE_TESTS, '%s is missing' % (test,)) + for test in FILTERED_TESTS: + self.assert_(test in SHUFFLED_FILTERED_TESTS, '%s is missing' % (test,)) + for test in SHARDED_TESTS: + self.assert_(test in SHUFFLED_SHARDED_TESTS, '%s is missing' % (test,)) + + def testShuffleLeavesDeathTestsAtFront(self): + non_death_test_found = False + for test in SHUFFLED_ACTIVE_TESTS: + if 'DeathTest.' in test: + self.assert_(not non_death_test_found, + '%s appears after a non-death test' % (test,)) + else: + non_death_test_found = True + + def _VerifyTestCasesDoNotInterleave(self, tests): + test_cases = [] + for test in tests: + [test_case, _] = test.split('.') + if test_cases and test_cases[-1] != test_case: + test_cases.append(test_case) + self.assertEqual(1, test_cases.count(test_case), + 'Test case %s is not grouped together in %s' % + (test_case, tests)) + + def testShuffleDoesNotInterleaveTestCases(self): + self._VerifyTestCasesDoNotInterleave(SHUFFLED_ALL_TESTS) + self._VerifyTestCasesDoNotInterleave(SHUFFLED_ACTIVE_TESTS) + self._VerifyTestCasesDoNotInterleave(SHUFFLED_FILTERED_TESTS) + self._VerifyTestCasesDoNotInterleave(SHUFFLED_SHARDED_TESTS) + + def testShuffleRestoresOrderAfterEachIteration(self): + # Get the test lists in all 3 iterations, using random seed 1, 2, + # and 3 respectively. Google Test picks a different seed in each + # iteration, and this test depends on the current implementation + # picking successive numbers. This dependency is not ideal, but + # makes the test much easier to write. + [tests_in_iteration1, tests_in_iteration2, tests_in_iteration3] = ( + GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(1), RepeatFlag(3)])) + + # Make sure running the tests with random seed 1 gets the same + # order as in iteration 1 above. + [tests_with_seed1] = GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(1)]) + self.assertEqual(tests_in_iteration1, tests_with_seed1) + + # Make sure running the tests with random seed 2 gets the same + # order as in iteration 2 above. Success means that Google Test + # correctly restores the test order before re-shuffling at the + # beginning of iteration 2. + [tests_with_seed2] = GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(2)]) + self.assertEqual(tests_in_iteration2, tests_with_seed2) + + # Make sure running the tests with random seed 3 gets the same + # order as in iteration 3 above. Success means that Google Test + # correctly restores the test order before re-shuffling at the + # beginning of iteration 3. + [tests_with_seed3] = GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(3)]) + self.assertEqual(tests_in_iteration3, tests_with_seed3) + + def testShuffleGeneratesNewOrderInEachIteration(self): + [tests_in_iteration1, tests_in_iteration2, tests_in_iteration3] = ( + GetTestsForAllIterations( + {}, [ShuffleFlag(), RandomSeedFlag(1), RepeatFlag(3)])) + + self.assert_(tests_in_iteration1 != tests_in_iteration2, + tests_in_iteration1) + self.assert_(tests_in_iteration1 != tests_in_iteration3, + tests_in_iteration1) + self.assert_(tests_in_iteration2 != tests_in_iteration3, + tests_in_iteration2) + + def testShuffleShardedTestsPreservesPartition(self): + # If we run M tests on N shards, the same M tests should be run in + # total, regardless of the random seeds used by the shards. + [tests1] = GetTestsForAllIterations({TOTAL_SHARDS_ENV_VAR: '3', + SHARD_INDEX_ENV_VAR: '0'}, + [ShuffleFlag(), RandomSeedFlag(1)]) + [tests2] = GetTestsForAllIterations({TOTAL_SHARDS_ENV_VAR: '3', + SHARD_INDEX_ENV_VAR: '1'}, + [ShuffleFlag(), RandomSeedFlag(20)]) + [tests3] = GetTestsForAllIterations({TOTAL_SHARDS_ENV_VAR: '3', + SHARD_INDEX_ENV_VAR: '2'}, + [ShuffleFlag(), RandomSeedFlag(25)]) + sorted_sharded_tests = tests1 + tests2 + tests3 + sorted_sharded_tests.sort() + sorted_active_tests = [] + sorted_active_tests.extend(ACTIVE_TESTS) + sorted_active_tests.sort() + self.assertEqual(sorted_active_tests, sorted_sharded_tests) + +if __name__ == '__main__': + gtest_test_utils.Main() diff --git a/test/gtest_shuffle_test_.cc b/test/gtest_shuffle_test_.cc new file mode 100644 index 0000000..53ecf77 --- /dev/null +++ b/test/gtest_shuffle_test_.cc @@ -0,0 +1,104 @@ +// Copyright 2009, Google Inc. +// All rights reserved. +// +// Redistribution and use in source and binary forms, with or without +// modification, are permitted provided that the following conditions are +// met: +// +// * Redistributions of source code must retain the above copyright +// notice, this list of conditions and the following disclaimer. +// * Redistributions in binary form must reproduce the above +// copyright notice, this list of conditions and the following disclaimer +// in the documentation and/or other materials provided with the +// distribution. +// * Neither the name of Google Inc. nor the names of its +// contributors may be used to endorse or promote products derived from +// this software without specific prior written permission. +// +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +// +// Author: wan@google.com (Zhanyong Wan) + +// Verifies that test shuffling works. + +#include + +namespace { + +using ::testing::EmptyTestEventListener; +using ::testing::InitGoogleTest; +using ::testing::Message; +using ::testing::Test; +using ::testing::TestEventListeners; +using ::testing::TestInfo; +using ::testing::UnitTest; +using ::testing::internal::String; +using ::testing::internal::scoped_ptr; + +// The test methods are empty, as the sole purpose of this program is +// to print the test names before/after shuffling. + +class A : public Test {}; +TEST_F(A, A) {} +TEST_F(A, B) {} + +TEST(ADeathTest, A) {} +TEST(ADeathTest, B) {} +TEST(ADeathTest, C) {} + +TEST(B, A) {} +TEST(B, B) {} +TEST(B, C) {} +TEST(B, DISABLED_D) {} +TEST(B, DISABLED_E) {} + +TEST(BDeathTest, A) {} +TEST(BDeathTest, B) {} + +TEST(C, A) {} +TEST(C, B) {} +TEST(C, C) {} +TEST(C, DISABLED_D) {} + +TEST(CDeathTest, A) {} + +TEST(DISABLED_D, A) {} +TEST(DISABLED_D, DISABLED_B) {} + +// This printer prints the full test names only, starting each test +// iteration with a "----" marker. +class TestNamePrinter : public EmptyTestEventListener { + public: + virtual void OnTestIterationStart(const UnitTest& /* unit_test */, + int /* iteration */) { + printf("----\n"); + } + + virtual void OnTestStart(const TestInfo& test_info) { + printf("%s.%s\n", test_info.test_case_name(), test_info.name()); + } +}; + +} // namespace + +int main(int argc, char **argv) { + InitGoogleTest(&argc, argv); + + // Replaces the default printer with TestNamePrinter, which prints + // the test name only. + TestEventListeners& listeners = UnitTest::GetInstance()->listeners(); + delete listeners.Release(listeners.default_result_printer()); + listeners.Append(new TestNamePrinter); + + return RUN_ALL_TESTS(); +} diff --git a/test/gtest_unittest.cc b/test/gtest_unittest.cc index ba39ae6..5c69b46 100644 --- a/test/gtest_unittest.cc +++ b/test/gtest_unittest.cc @@ -180,6 +180,19 @@ using testing::internal::kMaxRandomSeed; using testing::internal::kTestTypeIdInGoogleTest; using testing::internal::scoped_ptr; +class TestingVector : public Vector { +}; + +::std::ostream& operator<<(::std::ostream& os, + const TestingVector& vector) { + os << "{ "; + for (int i = 0; i < vector.size(); i++) { + os << vector.GetElement(i) << " "; + } + os << "}"; + return os; +} + // This line tests that we can define tests in an unnamed namespace. namespace { @@ -677,6 +690,53 @@ TEST(VectorTest, GetElementOr) { EXPECT_EQ('x', a.GetElementOr(2, 'x')); } +TEST(VectorTest, Swap) { + Vector a; + a.PushBack(0); + a.PushBack(1); + a.PushBack(2); + + // Swaps an element with itself. + a.Swap(0, 0); + ASSERT_EQ(0, a.GetElement(0)); + ASSERT_EQ(1, a.GetElement(1)); + ASSERT_EQ(2, a.GetElement(2)); + + // Swaps two different elements where the indices go up. + a.Swap(0, 1); + ASSERT_EQ(1, a.GetElement(0)); + ASSERT_EQ(0, a.GetElement(1)); + ASSERT_EQ(2, a.GetElement(2)); + + // Swaps two different elements where the indices go down. + a.Swap(2, 0); + ASSERT_EQ(2, a.GetElement(0)); + ASSERT_EQ(0, a.GetElement(1)); + ASSERT_EQ(1, a.GetElement(2)); +} + +TEST(VectorTest, Clone) { + // Clones an empty Vector. + Vector a; + scoped_ptr > empty(a.Clone()); + EXPECT_EQ(0, empty->size()); + + // Clones a singleton. + a.PushBack(42); + scoped_ptr > singleton(a.Clone()); + ASSERT_EQ(1, singleton->size()); + EXPECT_EQ(42, singleton->GetElement(0)); + + // Clones a Vector with more elements. + a.PushBack(43); + a.PushBack(44); + scoped_ptr > big(a.Clone()); + ASSERT_EQ(3, big->size()); + EXPECT_EQ(42, big->GetElement(0)); + EXPECT_EQ(43, big->GetElement(1)); + EXPECT_EQ(44, big->GetElement(2)); +} + // Tests Vector::Erase(). TEST(VectorDeathTest, Erase) { Vector a; @@ -740,23 +800,252 @@ TEST(VectorDeathTest, Erase) { } // Tests the GetElement accessor. -TEST(ListDeathTest, GetElement) { +TEST(VectorDeathTest, GetElement) { Vector a; a.PushBack(0); a.PushBack(1); a.PushBack(2); + const Vector& b = a; + + EXPECT_EQ(0, b.GetElement(0)); + EXPECT_EQ(1, b.GetElement(1)); + EXPECT_EQ(2, b.GetElement(2)); + EXPECT_DEATH_IF_SUPPORTED( + b.GetElement(3), + "Invalid Vector index 3: must be in range \\[0, 2\\]\\."); + EXPECT_DEATH_IF_SUPPORTED( + b.GetElement(-1), + "Invalid Vector index -1: must be in range \\[0, 2\\]\\."); +} + +// Tests the GetMutableElement accessor. +TEST(VectorDeathTest, GetMutableElement) { + Vector a; + a.PushBack(0); + a.PushBack(1); + a.PushBack(2); + + EXPECT_EQ(0, a.GetMutableElement(0)); + EXPECT_EQ(1, a.GetMutableElement(1)); + EXPECT_EQ(2, a.GetMutableElement(2)); + + a.GetMutableElement(0) = 42; + EXPECT_EQ(42, a.GetMutableElement(0)); + EXPECT_EQ(1, a.GetMutableElement(1)); + EXPECT_EQ(2, a.GetMutableElement(2)); - EXPECT_EQ(0, a.GetElement(0)); - EXPECT_EQ(1, a.GetElement(1)); - EXPECT_EQ(2, a.GetElement(2)); EXPECT_DEATH_IF_SUPPORTED( - a.GetElement(3), + a.GetMutableElement(3), "Invalid Vector index 3: must be in range \\[0, 2\\]\\."); EXPECT_DEATH_IF_SUPPORTED( - a.GetElement(-1), + a.GetMutableElement(-1), "Invalid Vector index -1: must be in range \\[0, 2\\]\\."); } +TEST(VectorDeathTest, Swap) { + Vector a; + a.PushBack(0); + a.PushBack(1); + a.PushBack(2); + + EXPECT_DEATH_IF_SUPPORTED( + a.Swap(-1, 1), + "Invalid first swap element -1: must be in range \\[0, 2\\]"); + EXPECT_DEATH_IF_SUPPORTED( + a.Swap(3, 1), + "Invalid first swap element 3: must be in range \\[0, 2\\]"); + EXPECT_DEATH_IF_SUPPORTED( + a.Swap(1, -1), + "Invalid second swap element -1: must be in range \\[0, 2\\]"); + EXPECT_DEATH_IF_SUPPORTED( + a.Swap(1, 3), + "Invalid second swap element 3: must be in range \\[0, 2\\]"); +} + +TEST(VectorDeathTest, ShuffleRange) { + Vector a; + a.PushBack(0); + a.PushBack(1); + a.PushBack(2); + testing::internal::Random random(1); + + EXPECT_DEATH_IF_SUPPORTED( + a.ShuffleRange(&random, -1, 1), + "Invalid shuffle range start -1: must be in range \\[0, 3\\]"); + EXPECT_DEATH_IF_SUPPORTED( + a.ShuffleRange(&random, 4, 4), + "Invalid shuffle range start 4: must be in range \\[0, 3\\]"); + EXPECT_DEATH_IF_SUPPORTED( + a.ShuffleRange(&random, 3, 2), + "Invalid shuffle range finish 2: must be in range \\[3, 3\\]"); + EXPECT_DEATH_IF_SUPPORTED( + a.ShuffleRange(&random, 3, 4), + "Invalid shuffle range finish 4: must be in range \\[3, 3\\]"); +} + +class VectorShuffleTest : public Test { + protected: + static const int kVectorSize = 20; + + VectorShuffleTest() : random_(1) { + for (int i = 0; i < kVectorSize; i++) { + vector_.PushBack(i); + } + } + + static bool VectorIsCorrupt(const TestingVector& vector) { + if (kVectorSize != vector.size()) { + return true; + } + + bool found_in_vector[kVectorSize] = { false }; + for (int i = 0; i < vector.size(); i++) { + const int e = vector.GetElement(i); + if (e < 0 || e >= kVectorSize || found_in_vector[e]) { + return true; + } + found_in_vector[e] = true; + } + + // Vector size is correct, elements' range is correct, no + // duplicate elements. Therefore no corruption has occurred. + return false; + } + + static bool VectorIsNotCorrupt(const TestingVector& vector) { + return !VectorIsCorrupt(vector); + } + + static bool RangeIsShuffled(const TestingVector& vector, int begin, int end) { + for (int i = begin; i < end; i++) { + if (i != vector.GetElement(i)) { + return true; + } + } + return false; + } + + static bool RangeIsUnshuffled( + const TestingVector& vector, int begin, int end) { + return !RangeIsShuffled(vector, begin, end); + } + + static bool VectorIsShuffled(const TestingVector& vector) { + return RangeIsShuffled(vector, 0, vector.size()); + } + + static bool VectorIsUnshuffled(const TestingVector& vector) { + return !VectorIsShuffled(vector); + } + + testing::internal::Random random_; + TestingVector vector_; +}; // class VectorShuffleTest + +const int VectorShuffleTest::kVectorSize; + +TEST_F(VectorShuffleTest, HandlesEmptyRange) { + // Tests an empty range at the beginning... + vector_.ShuffleRange(&random_, 0, 0); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); + + // ...in the middle... + vector_.ShuffleRange(&random_, kVectorSize/2, kVectorSize/2); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); + + // ...at the end... + vector_.ShuffleRange(&random_, kVectorSize - 1, kVectorSize - 1); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); + + // ...and past the end. + vector_.ShuffleRange(&random_, kVectorSize, kVectorSize); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); +} + +TEST_F(VectorShuffleTest, HandlesRangeOfSizeOne) { + // Tests a size one range at the beginning... + vector_.ShuffleRange(&random_, 0, 1); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); + + // ...in the middle... + vector_.ShuffleRange(&random_, kVectorSize/2, kVectorSize/2 + 1); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); + + // ...and at the end. + vector_.ShuffleRange(&random_, kVectorSize - 1, kVectorSize); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsUnshuffled, vector_); +} + +// Because we use our own random number generator and a fixed seed, +// we can guarantee that the following "random" tests will succeed. + +TEST_F(VectorShuffleTest, ShufflesEntireVector) { + vector_.Shuffle(&random_); + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + EXPECT_FALSE(VectorIsUnshuffled(vector_)) << vector_; + + // Tests the first and last elements in particular to ensure that + // there are no off-by-one problems in our shuffle algorithm. + EXPECT_NE(0, vector_.GetElement(0)); + EXPECT_NE(kVectorSize - 1, vector_.GetElement(kVectorSize - 1)); +} + +TEST_F(VectorShuffleTest, ShufflesStartOfVector) { + const int kRangeSize = kVectorSize/2; + + vector_.ShuffleRange(&random_, 0, kRangeSize); + + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + EXPECT_PRED3(RangeIsShuffled, vector_, 0, kRangeSize); + EXPECT_PRED3(RangeIsUnshuffled, vector_, kRangeSize, kVectorSize); +} + +TEST_F(VectorShuffleTest, ShufflesEndOfVector) { + const int kRangeSize = kVectorSize / 2; + vector_.ShuffleRange(&random_, kRangeSize, kVectorSize); + + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + EXPECT_PRED3(RangeIsUnshuffled, vector_, 0, kRangeSize); + EXPECT_PRED3(RangeIsShuffled, vector_, kRangeSize, kVectorSize); +} + +TEST_F(VectorShuffleTest, ShufflesMiddleOfVector) { + int kRangeSize = kVectorSize/3; + vector_.ShuffleRange(&random_, kRangeSize, 2*kRangeSize); + + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + EXPECT_PRED3(RangeIsUnshuffled, vector_, 0, kRangeSize); + EXPECT_PRED3(RangeIsShuffled, vector_, kRangeSize, 2*kRangeSize); + EXPECT_PRED3(RangeIsUnshuffled, vector_, 2*kRangeSize, kVectorSize); +} + +TEST_F(VectorShuffleTest, ShufflesRepeatably) { + TestingVector vector2; + for (int i = 0; i < kVectorSize; i++) { + vector2.PushBack(i); + } + + random_.Reseed(1234); + vector_.Shuffle(&random_); + random_.Reseed(1234); + vector2.Shuffle(&random_); + + ASSERT_PRED1(VectorIsNotCorrupt, vector_); + ASSERT_PRED1(VectorIsNotCorrupt, vector2); + + for (int i = 0; i < kVectorSize; i++) { + EXPECT_EQ(vector_.GetElement(i), vector2.GetElement(i)) + << " where i is " << i; + } +} + // Tests the size of the AssertHelper class. TEST(AssertHelperTest, AssertHelperIsSmall) { -- cgit v0.12