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). --- src/gtest-internal-inl.h | 139 +++++++++++++++++++++++++++++++++++++++-------- src/gtest.cc | 106 +++++++++++++++++++++++++++++++----- 2 files changed, 206 insertions(+), 39 deletions(-) (limited to 'src') diff --git a/src/gtest-internal-inl.h b/src/gtest-internal-inl.h index d593e82c..9a366fe5 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 f0d8c38c..93407245 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" -- cgit v1.2.3