Implements test shuffling (by Zhanyong Wan, based on Josh Kelley's original patch).

Enables death tests on minGW (by Vlad Losev).


git-svn-id: http://googletest.googlecode.com/svn/trunk@322 861a406c-534a-0410-8894-cb66d6ee9925

1 files changed, 115 insertions, 24 deletions

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<E**>(
+        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<E**>(
-        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<TestCase*>* test_cases() { return &test_cases_; }
-  const internal::Vector<TestCase*>* test_cases() const { return &test_cases_; }
-
   // Getters for the per-thread Google Test trace stack.
   internal::Vector<TraceInfo>* 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<Environment*> environments_;
   internal::Vector<Environment*> environments_in_reverse_order_;
 
-  internal::Vector<TestCase*> test_cases_;  // The vector of TestCases.
+  // The vector of TestCases in their original order.  It owns the
+  // elements in the vector.
+  internal::Vector<TestCase*> 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<int> 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