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

10 files changed, 986 insertions, 59 deletions

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<TestInfo*>* test_info_list_;
+  // The vector of TestInfos in their original order.  It owns the
+  // elements in the vector.
+  const internal::scoped_ptr<internal::Vector<TestInfo*> > 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<internal::Vector<int> > 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 <vector>  // 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<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
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<TestInfo*>),
+      test_indices_(new internal::Vector<int>),
       set_up_tc_(set_up_tc),
       tear_down_tc_(tear_down_tc),
       should_run_(false),
       elapsed_time_(0) {
-  test_info_list_ = new internal::Vector<TestInfo *>;
 }
 
 // Destructor of TestCase.
 TestCase::~TestCase() {
   // Deletes every Test in the collection.
   test_info_list_->ForEach(internal::Delete<TestInfo>);
-
-  // 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<int*>(NULL) = 1;
@@ -671,7 +675,9 @@ static void TestExitMacros() {
       *static_cast<int*>(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 <gtest/gtest.h>
+
+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<int> {
+};
+
+::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<int> 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<int> a;
+  scoped_ptr<Vector<int> > empty(a.Clone());
+  EXPECT_EQ(0, empty->size());
+
+  // Clones a singleton.
+  a.PushBack(42);
+  scoped_ptr<Vector<int> > 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<Vector<int> > 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<int> a;
@@ -740,23 +800,252 @@ TEST(VectorDeathTest, Erase) {
 }
 
 // Tests the GetElement accessor.
-TEST(ListDeathTest, GetElement) {
+TEST(VectorDeathTest, GetElement) {
   Vector<int> a;
   a.PushBack(0);
   a.PushBack(1);
   a.PushBack(2);
+  const Vector<int>& 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<int> 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<int> 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<int> 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) {