Quelle  gtest.cc   Sprache: C

// Copyright 2005, 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.

//
// The Google C++ Testing and Mocking Framework (Google Test)

#include "gtest/gtest.h"

#include <ctype.h>
#include <stdarg.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <wchar.h>
#include <wctype.h>

#include <algorithm>
#include <chrono>  // NOLINT
#include <cmath>
#include <csignal>  // NOLINT: raise(3) is used on some platforms
#include <cstdint>
#include <cstdlib>
#include <cstring>
#include <initializer_list>
#include <iomanip>
#include <ios>
#include <iostream>
#include <iterator>
#include <limits>
#include <list>
#include <map>
#include <ostream>  // NOLINT
#include <set>
#include <sstream>
#include <unordered_set>
#include <utility>
#include <vector>

#include "gtest/gtest-assertion-result.h"
#include "gtest/gtest-spi.h"
#include "gtest/internal/custom/gtest.h"
#include "gtest/internal/gtest-port.h"

#ifdef GTEST_OS_LINUX

#include <fcntl.h>   // NOLINT
#include <limits.h>  // NOLINT
#include <sched.h>   // NOLINT
// Declares vsnprintf().  This header is not available on Windows.
#include <strings.h>   // NOLINT
#include <sys/mman.h>  // NOLINT
#include <sys/time.h>  // NOLINT
#include <unistd.h>    // NOLINT

#include <string>

#elif defined(GTEST_OS_ZOS)
#include <sys/time.h>  // NOLINT

// On z/OS we additionally need strings.h for strcasecmp.
#include <strings.h>   // NOLINT

#elif defined(GTEST_OS_WINDOWS_MOBILE)  // We are on Windows CE.

#include <windows.h>  // NOLINT
#undef min

#elif defined(GTEST_OS_WINDOWS)  // We are on Windows proper.

#include <windows.h>  // NOLINT
#undef min

#ifdef _MSC_VER
#include <crtdbg.h>  // NOLINT
#endif

#include <io.h>         // NOLINT
#include <sys/stat.h>   // NOLINT
#include <sys/timeb.h>  // NOLINT
#include <sys/types.h>  // NOLINT

#ifdef GTEST_OS_WINDOWS_MINGW
#include <sys/time.h>  // NOLINT
#endif                 // GTEST_OS_WINDOWS_MINGW

#else

// cpplint thinks that the header is already included, so we want to
// silence it.
#include <sys/time.h>  // NOLINT
#include <unistd.h>    // NOLINT

#endif  // GTEST_OS_LINUX

#if GTEST_HAS_EXCEPTIONS
#include <stdexcept>
#endif

#if GTEST_CAN_STREAM_RESULTS_
#include <arpa/inet.h>   // NOLINT
#include <netdb.h>       // NOLINT
#include <sys/socket.h>  // NOLINT
#include <sys/types.h>   // NOLINT
#endif

#include "src/gtest-internal-inl.h"

#ifdef GTEST_OS_WINDOWS
#define vsnprintf _vsnprintf
#endif  // GTEST_OS_WINDOWS

#ifdef GTEST_OS_MAC
#ifndef GTEST_OS_IOS
#include <crt_externs.h>
#endif
#endif

#ifdef GTEST_HAS_ABSL
#include "absl/container/flat_hash_set.h"
#include "absl/debugging/failure_signal_handler.h"
#include "absl/debugging/stacktrace.h"
#include "absl/debugging/symbolize.h"
#include "absl/flags/parse.h"
#include "absl/flags/usage.h"
#include "absl/strings/str_cat.h"
#include "absl/strings/str_replace.h"
#include "absl/strings/string_view.h"
#include "absl/strings/strip.h"
#endif  // GTEST_HAS_ABSL

// Checks builtin compiler feature |x| while avoiding an extra layer of #ifdefs
// at the callsite.
#if defined(__has_builtin)
#define GTEST_HAS_BUILTIN(x) __has_builtin(x)
#else
#define GTEST_HAS_BUILTIN(x) 0
#endif  // defined(__has_builtin)

#if defined(GTEST_HAS_ABSL) && !defined(GTEST_NO_ABSL_FLAGS)
#define GTEST_HAS_ABSL_FLAGS
#endif

namespace testing {

using internal::CountIf;
using internal::ForEach;
using internal::GetElementOr;
using internal::Shuffle;

// Constants.

// A test whose test suite name or test name matches this filter is
// disabled and not run.
static const char kDisableTestFilter[] = "DISABLED_*:*/DISABLED_*";

// A test suite whose name matches this filter is considered a death
// test suite and will be run before test suites whose name doesn't
// match this filter.
static const char kDeathTestSuiteFilter[] = "*DeathTest:*DeathTest/*";

// A test filter that matches everything.
static const char kUniversalFilter[] = "*";

// The default output format.
static const char kDefaultOutputFormat[] = "xml";
// The default output file.
static const char kDefaultOutputFile[] = "test_detail";

// The environment variable name for the test shard index.
static const char kTestShardIndex[] = "GTEST_SHARD_INDEX";
// The environment variable name for the total number of test shards.
static const char kTestTotalShards[] = "GTEST_TOTAL_SHARDS";
// The environment variable name for the test shard status file.
static const char kTestShardStatusFile[] = "GTEST_SHARD_STATUS_FILE";

namespace internal {

// The text used in failure messages to indicate the start of the
// stack trace.
const char kStackTraceMarker[] = "\nStack trace:\n";

// g_help_flag is true if and only if the --help flag or an equivalent form
// is specified on the command line.
bool g_help_flag = false;

#if GTEST_HAS_FILE_SYSTEM
// Utility function to Open File for Writing
static FILE* OpenFileForWriting(const std::string& output_file) {
  FILE* fileout = nullptr;
  FilePath output_file_path(output_file);
  FilePath output_dir(output_file_path.RemoveFileName());

  if (output_dir.CreateDirectoriesRecursively()) {
    fileout = posix::FOpen(output_file.c_str(), "w");
  }
  if (fileout == nullptr) {
    GTEST_LOG_(FATAL) << "Unable to open file \"" << output_file << "\"";
  }
  return fileout;
}
#endif  // GTEST_HAS_FILE_SYSTEM

}  // namespace internal

// Bazel passes in the argument to '--test_filter' via the TESTBRIDGE_TEST_ONLY
// environment variable.
static const char* GetDefaultFilter() {
  const char* const testbridge_test_only =
      internal::posix::GetEnv("TESTBRIDGE_TEST_ONLY");
  if (testbridge_test_only != nullptr) {
    return testbridge_test_only;
  }
  return kUniversalFilter;
}

// Bazel passes in the argument to '--test_runner_fail_fast' via the
// TESTBRIDGE_TEST_RUNNER_FAIL_FAST environment variable.
static bool GetDefaultFailFast() {
  const char* const testbridge_test_runner_fail_fast =
      internal::posix::GetEnv("TESTBRIDGE_TEST_RUNNER_FAIL_FAST");
  if (testbridge_test_runner_fail_fast != nullptr) {
    return strcmp(testbridge_test_runner_fail_fast, "1") == 0;
  }
  return false;
}

}  // namespace testing

GTEST_DEFINE_bool_(
    fail_fast,
    testing::internal::BoolFromGTestEnv("fail_fast",
                                        testing::GetDefaultFailFast()),
    "True if and only if a test failure should stop further test execution.");

GTEST_DEFINE_bool_(
    also_run_disabled_tests,
    testing::internal::BoolFromGTestEnv("also_run_disabled_tests", false),
    "Run disabled tests too, in addition to the tests normally being run.");

GTEST_DEFINE_bool_(
    break_on_failure,
    testing::internal::BoolFromGTestEnv("break_on_failure", false),
    "True if and only if a failed assertion should be a debugger "
    "break-point.");

GTEST_DEFINE_bool_(catch_exceptions,
                   testing::internal::BoolFromGTestEnv("catch_exceptions",
                                                       true),
                   "True if and only if " GTEST_NAME_
                   " should catch exceptions and treat them as test failures.");

GTEST_DEFINE_string_(
    color, testing::internal::StringFromGTestEnv("color", "auto"),
    "Whether to use colors in the output. Valid values: yes, no, "
    "and auto. 'auto' means to use colors if the output is "
    "being sent to a terminal and the TERM environment variable "
    "is set to a terminal type that supports colors.");

GTEST_DEFINE_string_(
    filter,
    testing::internal::StringFromGTestEnv("filter",
                                          testing::GetDefaultFilter()),
    "A colon-separated list of glob (not regex) patterns "
    "for filtering the tests to run, optionally followed by a "
    "'-' and a : separated list of negative patterns (tests to "
    "exclude). A test is run if it matches one of the positive "
    "patterns and does not match any of the negative patterns.");

GTEST_DEFINE_bool_(
    install_failure_signal_handler,
    testing::internal::BoolFromGTestEnv("install_failure_signal_handler",
                                        false),
    "If true and supported on the current platform, " GTEST_NAME_
    " should "
    "install a signal handler that dumps debugging information when fatal "
    "signals are raised.");

GTEST_DEFINE_bool_(list_tests, false, "List all tests without running them.");

// The net priority order after flag processing is thus:
//   --gtest_output command line flag
//   GTEST_OUTPUT environment variable
//   XML_OUTPUT_FILE environment variable
//   ''
GTEST_DEFINE_string_(
    output,
    testing::internal::StringFromGTestEnv(
        "output", testing::internal::OutputFlagAlsoCheckEnvVar().c_str()),
    "A format (defaults to \"xml\" but can be specified to be \"json\"), "
    "optionally followed by a colon and an output file name or directory. "
    "A directory is indicated by a trailing pathname separator. "
    "Examples: \"xml:filename.xml\", \"xml::directoryname/\". "
    "If a directory is specified, output files will be created "
    "within that directory, with file-names based on the test "
    "executable's name and, if necessary, made unique by adding "
    "digits.");

GTEST_DEFINE_bool_(
    brief, testing::internal::BoolFromGTestEnv("brief", false),
    "True if only test failures should be displayed in text output.");

GTEST_DEFINE_bool_(print_time,
                   testing::internal::BoolFromGTestEnv("print_time", true),
                   "True if and only if " GTEST_NAME_
                   " should display elapsed time in text output.");

GTEST_DEFINE_bool_(print_utf8,
                   testing::internal::BoolFromGTestEnv("print_utf8", true),
                   "True if and only if " GTEST_NAME_
                   " prints UTF8 characters as text.");

GTEST_DEFINE_int32_(
    random_seed, testing::internal::Int32FromGTestEnv("random_seed", 0),
    "Random number seed to use when shuffling test orders. Must be in range "
    "[1, 99999], or 0 to use a seed based on the current time.");

GTEST_DEFINE_int32_(
    repeat, testing::internal::Int32FromGTestEnv("repeat", 1),
    "How many times to repeat each test. Specify a negative number "
    "for repeating forever. Useful for shaking out flaky tests.");

GTEST_DEFINE_bool_(
    recreate_environments_when_repeating,
    testing::internal::BoolFromGTestEnv("recreate_environments_when_repeating",
                                        false),
    "Controls whether global test environments are recreated for each repeat "
    "of the tests. If set to false the global test environments are only set "
    "up once, for the first iteration, and only torn down once, for the last. "
    "Useful for shaking out flaky tests with stable, expensive test "
    "environments. If --gtest_repeat is set to a negative number, meaning "
    "there is no last run, the environments will always be recreated to avoid "
    "leaks.");

GTEST_DEFINE_bool_(show_internal_stack_frames, false,
                   "True if and only if " GTEST_NAME_
                   " should include internal stack frames when "
                   "printing test failure stack traces.");

GTEST_DEFINE_bool_(shuffle,
                   testing::internal::BoolFromGTestEnv("shuffle", false),
                   "True if and only if " GTEST_NAME_
                   " should randomize tests' order on every run.");

GTEST_DEFINE_int32_(
    stack_trace_depth,
    testing::internal::Int32FromGTestEnv("stack_trace_depth",
                                         testing::kMaxStackTraceDepth),
    "The maximum number of stack frames to print when an "
    "assertion fails. The valid range is 0 through 100, inclusive.");

GTEST_DEFINE_string_(
    stream_result_to,
    testing::internal::StringFromGTestEnv("stream_result_to", ""),
    "This flag specifies the host name and the port number on which to stream "
    "test results. Example: \"localhost:555\". The flag is effective only on "
    "Linux and macOS.");

GTEST_DEFINE_bool_(
    throw_on_failure,
    testing::internal::BoolFromGTestEnv("throw_on_failure", false),
    "When this flag is specified, a failed assertion will throw an exception "
    "if exceptions are enabled or exit the program with a non-zero code "
    "otherwise. For use with an external test framework.");

#if GTEST_USE_OWN_FLAGFILE_FLAG_
GTEST_DEFINE_string_(
    flagfile, testing::internal::StringFromGTestEnv("flagfile", ""),
    "This flag specifies the flagfile to read command-line flags from.");
#endif  // GTEST_USE_OWN_FLAGFILE_FLAG_

namespace testing {
namespace internal {

const uint32_t Random::kMaxRange;

// Generates a random number from [0, range), using a Linear
// Congruential Generator (LCG).  Crashes if 'range' is 0 or greater
// than kMaxRange.
uint32_t Random::Generate(uint32_t range) {
  // These constants are the same as are used in glibc's rand(3).
  // Use wider types than necessary to prevent unsigned overflow diagnostics.
  state_ = static_cast<uint32_t>(1103515245ULL * state_ + 12345U) % kMaxRange;

  GTEST_CHECK_(range > 0) << "Cannot generate a number in the range [0, 0).";
  GTEST_CHECK_(range <= kMaxRange)
      << "Generation of a number in [0, " << range << ") was requested, "
      << "but this can only generate numbers in [0, " << kMaxRange << ").";

  // Converting via modulus introduces a bit of downward bias, but
  // it's simple, and a linear congruential generator isn't too good
  // to begin with.
  return state_ % range;
}

// GTestIsInitialized() returns true if and only if the user has initialized
// Google Test.  Useful for catching the user mistake of not initializing
// Google Test before calling RUN_ALL_TESTS().
static bool GTestIsInitialized() { return !GetArgvs().empty(); }

// Iterates over a vector of TestSuites, keeping a running sum of the
// results of calling a given int-returning method on each.
// Returns the sum.
static int SumOverTestSuiteList(const std::vector<TestSuite*>& case_list,
                                int (TestSuite::*method)() const) {
  int sum = 0;
  for (size_t i = 0; i < case_list.size(); i++) {
    sum += (case_list[i]->*method)();
  }
  return sum;
}

// Returns true if and only if the test suite passed.
static bool TestSuitePassed(const TestSuite* test_suite) {
  return test_suite->should_run() && test_suite->Passed();
}

// Returns true if and only if the test suite failed.
static bool TestSuiteFailed(const TestSuite* test_suite) {
  return test_suite->should_run() && test_suite->Failed();
}

// Returns true if and only if test_suite contains at least one test that
// should run.
static bool ShouldRunTestSuite(const TestSuite* test_suite) {
  return test_suite->should_run();
}

namespace {

// Returns true if test part results of type `type` should include a stack
// trace.
bool ShouldEmitStackTraceForResultType(TestPartResult::Type type) {
  // Suppress emission of the stack trace for SUCCEED() since it likely never
  // requires investigation, and GTEST_SKIP() since skipping is an intentional
  // act by the developer rather than a failure requiring investigation.
  return type != TestPartResult::kSuccess && type != TestPartResult::kSkip;
}

}  // namespace

// AssertHelper constructor.
AssertHelper::AssertHelper(TestPartResult::Type type, const char* file,
                           int line, const char* message)
    : data_(new AssertHelperData(type, file, line, message)) {}

AssertHelper::~AssertHelper() { delete data_; }

// Message assignment, for assertion streaming support.
void AssertHelper::operator=(const Message& message) const {
  UnitTest::GetInstance()->AddTestPartResult(
      data_->type, data_->file, data_->line,
      AppendUserMessage(data_->message, message),
      ShouldEmitStackTraceForResultType(data_->type)
          ? UnitTest::GetInstance()->impl()->CurrentOsStackTraceExceptTop(1)
          : ""
      // Skips the stack frame for this function itself.
  );  // NOLINT
}

namespace {

// When TEST_P is found without a matching INSTANTIATE_TEST_SUITE_P
// to creates test cases for it, a synthetic test case is
// inserted to report ether an error or a log message.
//
// This configuration bit will likely be removed at some point.
constexpr bool kErrorOnUninstantiatedParameterizedTest = true;
constexpr bool kErrorOnUninstantiatedTypeParameterizedTest = true;

// A test that fails at a given file/line location with a given message.
class FailureTest : public Test {
 public:
  explicit FailureTest(const CodeLocation& loc, std::string error_message,
                       bool as_error)
      : loc_(loc),
        error_message_(std::move(error_message)),
        as_error_(as_error) {}

  void TestBody() override {
    if (as_error_) {
      AssertHelper(TestPartResult::kNonFatalFailure, loc_.file.c_str(),
                   loc_.line, "") = Message() << error_message_;
    } else {
      std::cout << error_message_ << std::endl;
    }
  }

 private:
  const CodeLocation loc_;
  const std::string error_message_;
  const bool as_error_;
};

}  // namespace

std::set<std::string>* GetIgnoredParameterizedTestSuites() {
  return UnitTest::GetInstance()->impl()->ignored_parameterized_test_suites();
}

// Add a given test_suit to the list of them allow to go un-instantiated.
MarkAsIgnored::MarkAsIgnored(const char* test_suite) {
  GetIgnoredParameterizedTestSuites()->insert(test_suite);
}

// If this parameterized test suite has no instantiations (and that
// has not been marked as okay), emit a test case reporting that.
void InsertSyntheticTestCase(const std::string& name, CodeLocation location,
                             bool has_test_p) {
  const auto& ignored = *GetIgnoredParameterizedTestSuites();
  if (ignored.find(name) != ignored.end()) return;

  const char kMissingInstantiation[] =  //
      " is defined via TEST_P, but never instantiated. None of the test "
      "cases "
      "will run. Either no INSTANTIATE_TEST_SUITE_P is provided or the only "
      "ones provided expand to nothing."
      "\n\n"
      "Ideally, TEST_P definitions should only ever be included as part of "
      "binaries that intend to use them. (As opposed to, for example, being "
      "placed in a library that may be linked in to get other utilities.)";

  const char kMissingTestCase[] =  //
      " is instantiated via INSTANTIATE_TEST_SUITE_P, but no tests are "
      "defined via TEST_P . No test cases will run."
      "\n\n"
      "Ideally, INSTANTIATE_TEST_SUITE_P should only ever be invoked from "
      "code that always depend on code that provides TEST_P. Failing to do "
      "so is often an indication of dead code, e.g. the last TEST_P was "
      "removed but the rest got left behind.";

  std::string message =
      "Parameterized test suite " + name +
      (has_test_p ? kMissingInstantiation : kMissingTestCase) +
      "\n\n"
      "To suppress this error for this test suite, insert the following line "
      "(in a non-header) in the namespace it is defined in:"
      "\n\n"
      "GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(" +
      name + ");";

  std::string full_name = "UninstantiatedParameterizedTestSuite<" + name + ">";
  RegisterTest(  //
      "GoogleTestVerification", full_name.c_str(),
      nullptr,  // No type parameter.
      nullptr,  // No value parameter.
      location.file.c_str(), location.line, [message, location] {
        return new FailureTest(location, message,
                               kErrorOnUninstantiatedParameterizedTest);
      });
}

void RegisterTypeParameterizedTestSuite(const char* test_suite_name,
                                        CodeLocation code_location) {
  GetUnitTestImpl()->type_parameterized_test_registry().RegisterTestSuite(
      test_suite_name, std::move(code_location));
}

void RegisterTypeParameterizedTestSuiteInstantiation(const char* case_name) {
  GetUnitTestImpl()->type_parameterized_test_registry().RegisterInstantiation(
      case_name);
}

void TypeParameterizedTestSuiteRegistry::RegisterTestSuite(
    const char* test_suite_name, CodeLocation code_location) {
  suites_.emplace(std::string(test_suite_name),
                  TypeParameterizedTestSuiteInfo(std::move(code_location)));
}

void TypeParameterizedTestSuiteRegistry::RegisterInstantiation(
    const char* test_suite_name) {
  auto it = suites_.find(std::string(test_suite_name));
  if (it != suites_.end()) {
    it->second.instantiated = true;
  } else {
    GTEST_LOG_(ERROR) << "Unknown type parameterized test suit '"
                      << test_suite_name << "'";
  }
}

void TypeParameterizedTestSuiteRegistry::CheckForInstantiations() {
  const auto& ignored = *GetIgnoredParameterizedTestSuites();
  for (const auto& testcase : suites_) {
    if (testcase.second.instantiated) continue;
    if (ignored.find(testcase.first) != ignored.end()) continue;

    std::string message =
        "Type parameterized test suite " + testcase.first +
        " is defined via REGISTER_TYPED_TEST_SUITE_P, but never instantiated "
        "via INSTANTIATE_TYPED_TEST_SUITE_P. None of the test cases will run."
        "\n\n"
        "Ideally, TYPED_TEST_P definitions should only ever be included as "
        "part of binaries that intend to use them. (As opposed to, for "
        "example, being placed in a library that may be linked in to get "
        "other "
        "utilities.)"
        "\n\n"
        "To suppress this error for this test suite, insert the following "
        "line "
        "(in a non-header) in the namespace it is defined in:"
        "\n\n"
        "GTEST_ALLOW_UNINSTANTIATED_PARAMETERIZED_TEST(" +
        testcase.first + ");";

    std::string full_name =
        "UninstantiatedTypeParameterizedTestSuite<" + testcase.first + ">";
    RegisterTest(  //
        "GoogleTestVerification", full_name.c_str(),
        nullptr,  // No type parameter.
        nullptr,  // No value parameter.
        testcase.second.code_location.file.c_str(),
        testcase.second.code_location.line, [message, testcase] {
          return new FailureTest(testcase.second.code_location, message,
                                 kErrorOnUninstantiatedTypeParameterizedTest);
        });
  }
}

// A copy of all command line arguments.  Set by InitGoogleTest().
static ::std::vector<std::string> g_argvs;

::std::vector<std::string> GetArgvs() {
#if defined(GTEST_CUSTOM_GET_ARGVS_)
  // GTEST_CUSTOM_GET_ARGVS_() may return a container of std::string or
  // ::string. This code converts it to the appropriate type.
  const auto& custom = GTEST_CUSTOM_GET_ARGVS_();
  return ::std::vector<std::string>(custom.begin(), custom.end());
#else   // defined(GTEST_CUSTOM_GET_ARGVS_)
  return g_argvs;
#endif  // defined(GTEST_CUSTOM_GET_ARGVS_)
}

#if GTEST_HAS_FILE_SYSTEM
// Returns the current application's name, removing directory path if that
// is present.
FilePath GetCurrentExecutableName() {
  FilePath result;

  auto args = GetArgvs();
  if (!args.empty()) {
#if defined(GTEST_OS_WINDOWS) || defined(GTEST_OS_OS2)
    result.Set(FilePath(args[0]).RemoveExtension("exe"));
#else
    result.Set(FilePath(args[0]));
#endif  // GTEST_OS_WINDOWS
  }

  return result.RemoveDirectoryName();
}
#endif  // GTEST_HAS_FILE_SYSTEM

// Functions for processing the gtest_output flag.

// Returns the output format, or "" for normal printed output.
std::string UnitTestOptions::GetOutputFormat() {
  std::string s = GTEST_FLAG_GET(output);
  const char* const gtest_output_flag = s.c_str();
  const char* const colon = strchr(gtest_output_flag, ':');
  return (colon == nullptr)
             ? std::string(gtest_output_flag)
             : std::string(gtest_output_flag,
                           static_cast<size_t>(colon - gtest_output_flag));
}

#if GTEST_HAS_FILE_SYSTEM
// Returns the name of the requested output file, or the default if none
// was explicitly specified.
std::string UnitTestOptions::GetAbsolutePathToOutputFile() {
  std::string s = GTEST_FLAG_GET(output);
  const char* const gtest_output_flag = s.c_str();

  std::string format = GetOutputFormat();
  if (format.empty()) format = std::string(kDefaultOutputFormat);

  const char* const colon = strchr(gtest_output_flag, ':');
  if (colon == nullptr)
    return internal::FilePath::MakeFileName(
               internal::FilePath(
                   UnitTest::GetInstance()->original_working_dir()),
               internal::FilePath(kDefaultOutputFile), 0, format.c_str())
        .string();

  internal::FilePath output_name(colon + 1);
  if (!output_name.IsAbsolutePath())
    output_name = internal::FilePath::ConcatPaths(
        internal::FilePath(UnitTest::GetInstance()->original_working_dir()),
        internal::FilePath(colon + 1));

  if (!output_name.IsDirectory()) return output_name.string();

  internal::FilePath result(internal::FilePath::GenerateUniqueFileName(
      output_name, internal::GetCurrentExecutableName(),
      GetOutputFormat().c_str()));
  return result.string();
}
#endif  // GTEST_HAS_FILE_SYSTEM

// Returns true if and only if the wildcard pattern matches the string. Each
// pattern consists of regular characters, single-character wildcards (?), and
// multi-character wildcards (*).
//
// This function implements a linear-time string globbing algorithm based on
// https://research.swtch.com/glob.
static bool PatternMatchesString(const std::string& name_str,
                                 const char* pattern, const char* pattern_end) {
  const char* name = name_str.c_str();
  const char* const name_begin = name;
  const char* const name_end = name + name_str.size();

  const char* pattern_next = pattern;
  const char* name_next = name;

  while (pattern < pattern_end || name < name_end) {
    if (pattern < pattern_end) {
      switch (*pattern) {
        default:  // Match an ordinary character.
          if (name < name_end && *name == *pattern) {
            ++pattern;
            ++name;
            continue;
          }
          break;
        case '?':  // Match any single character.
          if (name < name_end) {
            ++pattern;
            ++name;
            continue;
          }
          break;
        case '*':
          // Match zero or more characters. Start by skipping over the wildcard
          // and matching zero characters from name. If that fails, restart and
          // match one more character than the last attempt.
          pattern_next = pattern;
          name_next = name + 1;
          ++pattern;
          continue;
      }
    }
    // Failed to match a character. Restart if possible.
    if (name_begin < name_next && name_next <= name_end) {
      pattern = pattern_next;
      name = name_next;
      continue;
    }
    return false;
  }
  return true;
}

namespace {

bool IsGlobPattern(const std::string& pattern) {
  return std::any_of(pattern.begin(), pattern.end(),
                     [](const char c) { return c == '?' || c == '*'; });
}

class UnitTestFilter {
 public:
  UnitTestFilter() = default;

  // Constructs a filter from a string of patterns separated by `:`.
  explicit UnitTestFilter(const std::string& filter) {
    // By design "" filter matches "" string.
    std::vector<std::string> all_patterns;
    SplitString(filter, ':', &all_patterns);
    const auto exact_match_patterns_begin = std::partition(
        all_patterns.begin(), all_patterns.end(), &IsGlobPattern);

    glob_patterns_.reserve(static_cast<size_t>(
        std::distance(all_patterns.begin(), exact_match_patterns_begin)));
    std::move(all_patterns.begin(), exact_match_patterns_begin,
              std::inserter(glob_patterns_, glob_patterns_.begin()));
    std::move(
        exact_match_patterns_begin, all_patterns.end(),
        std::inserter(exact_match_patterns_, exact_match_patterns_.begin()));
  }

  // Returns true if and only if name matches at least one of the patterns in
  // the filter.
  bool MatchesName(const std::string& name) const {
    return exact_match_patterns_.find(name) != exact_match_patterns_.end() ||
           std::any_of(glob_patterns_.begin(), glob_patterns_.end(),
                       [&name](const std::string& pattern) {
                         return PatternMatchesString(
                             name, pattern.c_str(),
                             pattern.c_str() + pattern.size());
                       });
  }

 private:
  std::vector<std::string> glob_patterns_;
  std::unordered_set<std::string> exact_match_patterns_;
};

class PositiveAndNegativeUnitTestFilter {
 public:
  // Constructs a positive and a negative filter from a string. The string
  // contains a positive filter optionally followed by a '-' character and a
  // negative filter. In case only a negative filter is provided the positive
  // filter will be assumed "*".
  // A filter is a list of patterns separated by ':'.
  explicit PositiveAndNegativeUnitTestFilter(const std::string& filter) {
    std::vector<std::string> positive_and_negative_filters;

    // NOTE: `SplitString` always returns a non-empty container.
    SplitString(filter, '-', &positive_and_negative_filters);
    const auto& positive_filter = positive_and_negative_filters.front();

    if (positive_and_negative_filters.size() > 1) {
      positive_filter_ = UnitTestFilter(
          positive_filter.empty() ? kUniversalFilter : positive_filter);

      // TODO(b/214626361): Fail on multiple '-' characters
      // For the moment to preserve old behavior we concatenate the rest of the
      // string parts with `-` as separator to generate the negative filter.
      auto negative_filter_string = positive_and_negative_filters[1];
      for (std::size_t i = 2; i < positive_and_negative_filters.size(); i++)
        negative_filter_string =
            negative_filter_string + '-' + positive_and_negative_filters[i];
      negative_filter_ = UnitTestFilter(negative_filter_string);
    } else {
      // In case we don't have a negative filter and positive filter is ""
      // we do not use kUniversalFilter by design as opposed to when we have a
      // negative filter.
      positive_filter_ = UnitTestFilter(positive_filter);
    }
  }

  // Returns true if and only if test name (this is generated by appending test
  // suit name and test name via a '.' character) matches the positive filter
  // and does not match the negative filter.
  bool MatchesTest(const std::string& test_suite_name,
                   const std::string& test_name) const {
    return MatchesName(test_suite_name + "." + test_name);
  }

  // Returns true if and only if name matches the positive filter and does not
  // match the negative filter.
  bool MatchesName(const std::string& name) const {
    return positive_filter_.MatchesName(name) &&
           !negative_filter_.MatchesName(name);
  }

 private:
  UnitTestFilter positive_filter_;
  UnitTestFilter negative_filter_;
};
}  // namespace

bool UnitTestOptions::MatchesFilter(const std::string& name_str,
                                    const char* filter) {
  return UnitTestFilter(filter).MatchesName(name_str);
}

// Returns true if and only if the user-specified filter matches the test
// suite name and the test name.
bool UnitTestOptions::FilterMatchesTest(const std::string& test_suite_name,
                                        const std::string& test_name) {
  // Split --gtest_filter at '-', if there is one, to separate into
  // positive filter and negative filter portions
  return PositiveAndNegativeUnitTestFilter(GTEST_FLAG_GET(filter))
      .MatchesTest(test_suite_name, test_name);
}

#if GTEST_HAS_SEH
static std::string FormatSehExceptionMessage(DWORD exception_code,
                                             const char* location) {
  Message message;
  message << "SEH exception with code 0x" << std::setbase(16) << exception_code
          << std::setbase(10) << " thrown in " << location << ".";
  return message.GetString();
}

int UnitTestOptions::GTestProcessSEH(DWORD seh_code, const char* location) {
  // Google Test should handle a SEH exception if:
  //   1. the user wants it to, AND
  //   2. this is not a breakpoint exception or stack overflow, AND
  //   3. this is not a C++ exception (VC++ implements them via SEH,
  //      apparently).
  //
  // SEH exception code for C++ exceptions.
  // (see https://support.microsoft.com/kb/185294 for more information).
  const DWORD kCxxExceptionCode = 0xe06d7363;

  if (!GTEST_FLAG_GET(catch_exceptions) || seh_code == kCxxExceptionCode ||
      seh_code == EXCEPTION_BREAKPOINT ||
      seh_code == EXCEPTION_STACK_OVERFLOW) {
    return EXCEPTION_CONTINUE_SEARCH;  // Don't handle these exceptions
  }

  internal::ReportFailureInUnknownLocation(
      TestPartResult::kFatalFailure,
      FormatSehExceptionMessage(seh_code, location) +
          "\n"
          "Stack trace:\n" +
          ::testing::internal::GetCurrentOsStackTraceExceptTop(1));

  return EXCEPTION_EXECUTE_HANDLER;
}
#endif  // GTEST_HAS_SEH

}  // namespace internal

// The c'tor sets this object as the test part result reporter used by
// Google Test.  The 'result' parameter specifies where to report the
// results. Intercepts only failures from the current thread.
ScopedFakeTestPartResultReporter::ScopedFakeTestPartResultReporter(
    TestPartResultArray* result)
    : intercept_mode_(INTERCEPT_ONLY_CURRENT_THREAD), result_(result) {
  Init();
}

// The c'tor sets this object as the test part result reporter used by
// Google Test.  The 'result' parameter specifies where to report the
// results.
ScopedFakeTestPartResultReporter::ScopedFakeTestPartResultReporter(
    InterceptMode intercept_mode, TestPartResultArray* result)
    : intercept_mode_(intercept_mode), result_(result) {
  Init();
}

void ScopedFakeTestPartResultReporter::Init() {
  internal::UnitTestImpl* const impl = internal::GetUnitTestImpl();
  if (intercept_mode_ == INTERCEPT_ALL_THREADS) {
    old_reporter_ = impl->GetGlobalTestPartResultReporter();
    impl->SetGlobalTestPartResultReporter(this);
  } else {
    old_reporter_ = impl->GetTestPartResultReporterForCurrentThread();
    impl->SetTestPartResultReporterForCurrentThread(this);
  }
}

// The d'tor restores the test part result reporter used by Google Test
// before.
ScopedFakeTestPartResultReporter::~ScopedFakeTestPartResultReporter() {
  internal::UnitTestImpl* const impl = internal::GetUnitTestImpl();
  if (intercept_mode_ == INTERCEPT_ALL_THREADS) {
    impl->SetGlobalTestPartResultReporter(old_reporter_);
  } else {
    impl->SetTestPartResultReporterForCurrentThread(old_reporter_);
  }
}

// Increments the test part result count and remembers the result.
// This method is from the TestPartResultReporterInterface interface.
void ScopedFakeTestPartResultReporter::ReportTestPartResult(
    const TestPartResult& result) {
  result_->Append(result);
}

namespace internal {

// Returns the type ID of ::testing::Test.  We should always call this
// instead of GetTypeId< ::testing::Test>() to get the type ID of
// testing::Test.  This is to work around a suspected linker bug when
// using Google Test as a framework on Mac OS X.  The bug causes
// GetTypeId< ::testing::Test>() to return different values depending
// on whether the call is from the Google Test framework itself or
// from user test code.  GetTestTypeId() is guaranteed to always
// return the same value, as it always calls GetTypeId<>() from the
// gtest.cc, which is within the Google Test framework.
TypeId GetTestTypeId() { return GetTypeId<Test>(); }

// The value of GetTestTypeId() as seen from within the Google Test
// library.  This is solely for testing GetTestTypeId().
extern const TypeId kTestTypeIdInGoogleTest = GetTestTypeId();

// This predicate-formatter checks that 'results' contains a test part
// failure of the given type and that the failure message contains the
// given substring.
static AssertionResult HasOneFailure(const char* /* results_expr */,
                                     const char* /* type_expr */,
                                     const char* /* substr_expr */,
                                     const TestPartResultArray& results,
                                     TestPartResult::Type type,
                                     const std::string& substr) {
  const std::string expected(type == TestPartResult::kFatalFailure
                                 ? "1 fatal failure"
                                 : "1 non-fatal failure");
  Message msg;
  if (results.size() != 1) {
    msg << "Expected: " << expected << "\n"
        << " Actual: " << results.size() << " failures";
    for (int i = 0; i < results.size(); i++) {
      msg << "\n" << results.GetTestPartResult(i);
    }
    return AssertionFailure() << msg;
  }

  const TestPartResult& r = results.GetTestPartResult(0);
  if (r.type() != type) {
    return AssertionFailure() << "Expected: " << expected << "\n"
                              << " Actual:\n"
                              << r;
  }

  if (strstr(r.message(), substr.c_str()) == nullptr) {
    return AssertionFailure()
           << "Expected: " << expected << " containing \"" << substr << "\"\n"
           << " Actual:\n"
           << r;
  }

  return AssertionSuccess();
}

// The constructor of SingleFailureChecker remembers where to look up
// test part results, what type of failure we expect, and what
// substring the failure message should contain.
SingleFailureChecker::SingleFailureChecker(const TestPartResultArray* results,
                                           TestPartResult::Type type,
                                           const std::string& substr)
    : results_(results), type_(type), substr_(substr) {}

// The destructor of SingleFailureChecker verifies that the given
// TestPartResultArray contains exactly one failure that has the given
// type and contains the given substring.  If that's not the case, a
// non-fatal failure will be generated.
SingleFailureChecker::~SingleFailureChecker() {
  EXPECT_PRED_FORMAT3(HasOneFailure, *results_, type_, substr_);
}

DefaultGlobalTestPartResultReporter::DefaultGlobalTestPartResultReporter(
    UnitTestImpl* unit_test)
    : unit_test_(unit_test) {}

void DefaultGlobalTestPartResultReporter::ReportTestPartResult(
    const TestPartResult& result) {
  unit_test_->current_test_result()->AddTestPartResult(result);
  unit_test_->listeners()->repeater()->OnTestPartResult(result);
}

DefaultPerThreadTestPartResultReporter::DefaultPerThreadTestPartResultReporter(
    UnitTestImpl* unit_test)
    : unit_test_(unit_test) {}

void DefaultPerThreadTestPartResultReporter::ReportTestPartResult(
    const TestPartResult& result) {
  unit_test_->GetGlobalTestPartResultReporter()->ReportTestPartResult(result);
}

// Returns the global test part result reporter.
TestPartResultReporterInterface*
UnitTestImpl::GetGlobalTestPartResultReporter() {
  internal::MutexLock lock(&global_test_part_result_reporter_mutex_);
  return global_test_part_result_reporter_;
}

// Sets the global test part result reporter.
void UnitTestImpl::SetGlobalTestPartResultReporter(
    TestPartResultReporterInterface* reporter) {
  internal::MutexLock lock(&global_test_part_result_reporter_mutex_);
  global_test_part_result_reporter_ = reporter;
}

// Returns the test part result reporter for the current thread.
TestPartResultReporterInterface*
UnitTestImpl::GetTestPartResultReporterForCurrentThread() {
  return per_thread_test_part_result_reporter_.get();
}

// Sets the test part result reporter for the current thread.
void UnitTestImpl::SetTestPartResultReporterForCurrentThread(
    TestPartResultReporterInterface* reporter) {
  per_thread_test_part_result_reporter_.set(reporter);
}

// Gets the number of successful test suites.
int UnitTestImpl::successful_test_suite_count() const {
  return CountIf(test_suites_, TestSuitePassed);
}

// Gets the number of failed test suites.
int UnitTestImpl::failed_test_suite_count() const {
  return CountIf(test_suites_, TestSuiteFailed);
}

// Gets the number of all test suites.
int UnitTestImpl::total_test_suite_count() const {
  return static_cast<int>(test_suites_.size());
}

// Gets the number of all test suites that contain at least one test
// that should run.
int UnitTestImpl::test_suite_to_run_count() const {
  return CountIf(test_suites_, ShouldRunTestSuite);
}

// Gets the number of successful tests.
int UnitTestImpl::successful_test_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::successful_test_count);
}

// Gets the number of skipped tests.
int UnitTestImpl::skipped_test_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::skipped_test_count);
}

// Gets the number of failed tests.
int UnitTestImpl::failed_test_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::failed_test_count);
}

// Gets the number of disabled tests that will be reported in the XML report.
int UnitTestImpl::reportable_disabled_test_count() const {
  return SumOverTestSuiteList(test_suites_,
                              &TestSuite::reportable_disabled_test_count);
}

// Gets the number of disabled tests.
int UnitTestImpl::disabled_test_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::disabled_test_count);
}

// Gets the number of tests to be printed in the XML report.
int UnitTestImpl::reportable_test_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::reportable_test_count);
}

// Gets the number of all tests.
int UnitTestImpl::total_test_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::total_test_count);
}

// Gets the number of tests that should run.
int UnitTestImpl::test_to_run_count() const {
  return SumOverTestSuiteList(test_suites_, &TestSuite::test_to_run_count);
}

// Returns the current OS stack trace as an std::string.
//
// The maximum number of stack frames to be included is specified by
// the gtest_stack_trace_depth flag.  The skip_count parameter
// specifies the number of top frames to be skipped, which doesn't
// count against the number of frames to be included.
//
// For example, if Foo() calls Bar(), which in turn calls
// CurrentOsStackTraceExceptTop(1), Foo() will be included in the
// trace but Bar() and CurrentOsStackTraceExceptTop() won't.
std::string UnitTestImpl::CurrentOsStackTraceExceptTop(int skip_count) {
  return os_stack_trace_getter()->CurrentStackTrace(
      static_cast<int>(GTEST_FLAG_GET(stack_trace_depth)), skip_count + 1
      // Skips the user-specified number of frames plus this function
      // itself.
  );  // NOLINT
}

// A helper class for measuring elapsed times.
class Timer {
 public:
  Timer() : start_(clock::now()) {}

  // Return time elapsed in milliseconds since the timer was created.
  TimeInMillis Elapsed() {
    return std::chrono::duration_cast<std::chrono::milliseconds>(clock::now() -
                                                                 start_)
        .count();
  }

 private:
  // Fall back to the system_clock when building with newlib on a system
  // without a monotonic clock.
#if defined(_NEWLIB_VERSION) && !defined(CLOCK_MONOTONIC)
  using clock = std::chrono::system_clock;
#else
  using clock = std::chrono::steady_clock;
#endif
  clock::time_point start_;
};

// Returns a timestamp as milliseconds since the epoch. Note this time may jump
// around subject to adjustments by the system, to measure elapsed time use
// Timer instead.
TimeInMillis GetTimeInMillis() {
  return std::chrono::duration_cast<std::chrono::milliseconds>(
             std::chrono::system_clock::now() -
             std::chrono::system_clock::from_time_t(0))
      .count();
}

// Utilities

// class String.

#ifdef GTEST_OS_WINDOWS_MOBILE
// Creates a UTF-16 wide string from the given ANSI string, allocating
// memory using new. The caller is responsible for deleting the return
// value using delete[]. Returns the wide string, or NULL if the
// input is NULL.
LPCWSTR String::AnsiToUtf16(const char* ansi) {
  if (!ansi) return nullptr;
  const int length = strlen(ansi);
  const int unicode_length =
      MultiByteToWideChar(CP_ACP, 0, ansi, length, nullptr, 0);
  WCHAR* unicode = new WCHAR[unicode_length + 1];
  MultiByteToWideChar(CP_ACP, 0, ansi, length, unicode, unicode_length);
  unicode[unicode_length] = 0;
  return unicode;
}

// Creates an ANSI string from the given wide string, allocating
// memory using new. The caller is responsible for deleting the return
// value using delete[]. Returns the ANSI string, or NULL if the
// input is NULL.
const char* String::Utf16ToAnsi(LPCWSTR utf16_str) {
  if (!utf16_str) return nullptr;
  const int ansi_length = WideCharToMultiByte(CP_ACP, 0, utf16_str, -1, nullptr,
                                              0, nullptr, nullptr);
  char* ansi = new char[ansi_length + 1];
  WideCharToMultiByte(CP_ACP, 0, utf16_str, -1, ansi, ansi_length, nullptr,
                      nullptr);
  ansi[ansi_length] = 0;
  return ansi;
}

#endif  // GTEST_OS_WINDOWS_MOBILE

// Compares two C strings.  Returns true if and only if they have the same
// content.
//
// Unlike strcmp(), this function can handle NULL argument(s).  A NULL
// C string is considered different to any non-NULL C string,
// including the empty string.
bool String::CStringEquals(const char* lhs, const char* rhs) {
  if (lhs == nullptr) return rhs == nullptr;

  if (rhs == nullptr) return false;

  return strcmp(lhs, rhs) == 0;
}

#if GTEST_HAS_STD_WSTRING

// Converts an array of wide chars to a narrow string using the UTF-8
// encoding, and streams the result to the given Message object.
static void StreamWideCharsToMessage(const wchar_t* wstr, size_t length,
                                     Message* msg) {
  for (size_t i = 0; i != length;) {  // NOLINT
    if (wstr[i] != L'\0') {
      *msg << WideStringToUtf8(wstr + i, static_cast<int>(length - i));
      while (i != length && wstr[i] != L'\0') i++;
    } else {
      *msg << '\0';
      i++;
    }
  }
}

#endif  // GTEST_HAS_STD_WSTRING

void SplitString(const ::std::string& str, char delimiter,
                 ::std::vector< ::std::string>* dest) {
  ::std::vector< ::std::string> parsed;
  ::std::string::size_type pos = 0;
  while (::testing::internal::AlwaysTrue()) {
    const ::std::string::size_type colon = str.find(delimiter, pos);
    if (colon == ::std::string::npos) {
      parsed.push_back(str.substr(pos));
      break;
    } else {
      parsed.push_back(str.substr(pos, colon - pos));
      pos = colon + 1;
    }
  }
  dest->swap(parsed);
}

}  // namespace internal

// Constructs an empty Message.
// We allocate the stringstream separately because otherwise each use of
// ASSERT/EXPECT in a procedure adds over 200 bytes to the procedure's
// stack frame leading to huge stack frames in some cases; gcc does not reuse
// the stack space.
Message::Message() : ss_(new ::std::stringstream) {
  // By default, we want there to be enough precision when printing
  // a double to a Message.
  *ss_ << std::setprecision(std::numeric_limits<double>::digits10 + 2);
}

// These two overloads allow streaming a wide C string to a Message
// using the UTF-8 encoding.
Message& Message::operator<<(const wchar_t* wide_c_str) {
  return *this << internal::String::ShowWideCString(wide_c_str);
}
Message& Message::operator<<(wchar_t* wide_c_str) {
  return *this << internal::String::ShowWideCString(wide_c_str);
}

#if GTEST_HAS_STD_WSTRING
// Converts the given wide string to a narrow string using the UTF-8
// encoding, and streams the result to this Message object.
Message& Message::operator<<(const ::std::wstring& wstr) {
  internal::StreamWideCharsToMessage(wstr.c_str(), wstr.length(), this);
  return *this;
}
#endif  // GTEST_HAS_STD_WSTRING

// Gets the text streamed to this object so far as an std::string.
// Each '\0' character in the buffer is replaced with "\\0".
std::string Message::GetString() const {
  return internal::StringStreamToString(ss_.get());
}

namespace internal {

namespace edit_distance {
std::vector<EditType> CalculateOptimalEdits(const std::vector<size_t>& left,
                                            const std::vector<size_t>& right) {
  std::vector<std::vector<double> > costs(
      left.size() + 1, std::vector<double>(right.size() + 1));
  std::vector<std::vector<EditType> > best_move(
      left.size() + 1, std::vector<EditType>(right.size() + 1));

  // Populate for empty right.
  for (size_t l_i = 0; l_i < costs.size(); ++l_i) {
    costs[l_i][0] = static_cast<double>(l_i);
    best_move[l_i][0] = kRemove;
  }
  // Populate for empty left.
  for (size_t r_i = 1; r_i < costs[0].size(); ++r_i) {
    costs[0][r_i] = static_cast<double>(r_i);
    best_move[0][r_i] = kAdd;
  }

  for (size_t l_i = 0; l_i < left.size(); ++l_i) {
    for (size_t r_i = 0; r_i < right.size(); ++r_i) {
      if (left[l_i] == right[r_i]) {
        // Found a match. Consume it.
        costs[l_i + 1][r_i + 1] = costs[l_i][r_i];
        best_move[l_i + 1][r_i + 1] = kMatch;
        continue;
      }

      const double add = costs[l_i + 1][r_i];
      const double remove = costs[l_i][r_i + 1];
      const double replace = costs[l_i][r_i];
      if (add < remove && add < replace) {
        costs[l_i + 1][r_i + 1] = add + 1;
        best_move[l_i + 1][r_i + 1] = kAdd;
      } else if (remove < add && remove < replace) {
        costs[l_i + 1][r_i + 1] = remove + 1;
        best_move[l_i + 1][r_i + 1] = kRemove;
      } else {
        // We make replace a little more expensive than add/remove to lower
        // their priority.
        costs[l_i + 1][r_i + 1] = replace + 1.00001;
        best_move[l_i + 1][r_i + 1] = kReplace;
      }
    }
  }

  // Reconstruct the best path. We do it in reverse order.
  std::vector<EditType> best_path;
  for (size_t l_i = left.size(), r_i = right.size(); l_i > 0 || r_i > 0;) {
    EditType move = best_move[l_i][r_i];
    best_path.push_back(move);
    l_i -= move != kAdd;
    r_i -= move != kRemove;
  }
  std::reverse(best_path.begin(), best_path.end());
  return best_path;
}

namespace {

// Helper class to convert string into ids with deduplication.
class InternalStrings {
 public:
  size_t GetId(const std::string& str) {
    IdMap::iterator it = ids_.find(str);
    if (it != ids_.end()) return it->second;
    size_t id = ids_.size();
    return ids_[str] = id;
  }

 private:
  typedef std::map<std::string, size_t> IdMap;
  IdMap ids_;
};

}  // namespace

std::vector<EditType> CalculateOptimalEdits(
    const std::vector<std::string>& left,
    const std::vector<std::string>& right) {
  std::vector<size_t> left_ids, right_ids;
  {
    InternalStrings intern_table;
    for (size_t i = 0; i < left.size(); ++i) {
      left_ids.push_back(intern_table.GetId(left[i]));
    }
    for (size_t i = 0; i < right.size(); ++i) {
      right_ids.push_back(intern_table.GetId(right[i]));
    }
  }
  return CalculateOptimalEdits(left_ids, right_ids);
}

namespace {

// Helper class that holds the state for one hunk and prints it out to the
// stream.
// It reorders adds/removes when possible to group all removes before all
// adds. It also adds the hunk header before printint into the stream.
class Hunk {
 public:
  Hunk(size_t left_start, size_t right_start)
      : left_start_(left_start),
        right_start_(right_start),
        adds_(),
        removes_(),
        common_() {}

  void PushLine(char edit, const char* line) {
    switch (edit) {
      case ' ':
        ++common_;
        FlushEdits();
        hunk_.push_back(std::make_pair(' ', line));
        break;
      case '-':
        ++removes_;
        hunk_removes_.push_back(std::make_pair('-', line));
        break;
      case '+':
        ++adds_;
        hunk_adds_.push_back(std::make_pair('+', line));
        break;
    }
  }

  void PrintTo(std::ostream* os) {
    PrintHeader(os);
    FlushEdits();
    for (std::list<std::pair<char, const char*> >::const_iterator it =
             hunk_.begin();
         it != hunk_.end(); ++it) {
      *os << it->first << it->second << "\n";
    }
  }

  bool has_edits() const { return adds_ || removes_; }

 private:
  void FlushEdits() {
    hunk_.splice(hunk_.end(), hunk_removes_);
    hunk_.splice(hunk_.end(), hunk_adds_);
  }

  // Print a unified diff header for one hunk.
  // The format is
  //   "@@ -<left_start>,<left_length> +<right_start>,<right_length> @@"
  // where the left/right parts are omitted if unnecessary.
  void PrintHeader(std::ostream* ss) const {
    *ss << "@@ ";
    if (removes_) {
      *ss << "-" << left_start_ << "," << (removes_ + common_);
    }
    if (removes_ && adds_) {
      *ss << " ";
    }
    if (adds_) {
      *ss << "+" << right_start_ << "," << (adds_ + common_);
    }
    *ss << " @@\n";
  }

  size_t left_start_, right_start_;
  size_t adds_, removes_, common_;
  std::list<std::pair<char, const char*> > hunk_, hunk_adds_, hunk_removes_;
};

}  // namespace

// Create a list of diff hunks in Unified diff format.
// Each hunk has a header generated by PrintHeader above plus a body with
// lines prefixed with ' ' for no change, '-' for deletion and '+' for
// addition.
// 'context' represents the desired unchanged prefix/suffix around the diff.
// If two hunks are close enough that their contexts overlap, then they are
// joined into one hunk.
std::string CreateUnifiedDiff(const std::vector<std::string>& left,
                              const std::vector<std::string>& right,
                              size_t context) {
  const std::vector<EditType> edits = CalculateOptimalEdits(left, right);

  size_t l_i = 0, r_i = 0, edit_i = 0;
  std::stringstream ss;
  while (edit_i < edits.size()) {
    // Find first edit.
    while (edit_i < edits.size() && edits[edit_i] == kMatch) {
      ++l_i;
      ++r_i;
      ++edit_i;
    }

    // Find the first line to include in the hunk.
    const size_t prefix_context = std::min(l_i, context);
    Hunk hunk(l_i - prefix_context + 1, r_i - prefix_context + 1);
    for (size_t i = prefix_context; i > 0; --i) {
      hunk.PushLine(' ', left[l_i - i].c_str());
    }

    // Iterate the edits until we found enough suffix for the hunk or the input
    // is over.
    size_t n_suffix = 0;
    for (; edit_i < edits.size(); ++edit_i) {
      if (n_suffix >= context) {
        // Continue only if the next hunk is very close.
        auto it = edits.begin() + static_cast<int>(edit_i);
        while (it != edits.end() && *it == kMatch) ++it;
        if (it == edits.end() ||
            static_cast<size_t>(it - edits.begin()) - edit_i >= context) {
          // There is no next edit or it is too far away.
          break;
        }
      }

      EditType edit = edits[edit_i];
      // Reset count when a non match is found.
      n_suffix = edit == kMatch ? n_suffix + 1 : 0;

      if (edit == kMatch || edit == kRemove || edit == kReplace) {
        hunk.PushLine(edit == kMatch ? ' ' : '-', left[l_i].c_str());
      }
      if (edit == kAdd || edit == kReplace) {
        hunk.PushLine('+', right[r_i].c_str());
      }

      // Advance indices, depending on edit type.
      l_i += edit != kAdd;
      r_i += edit != kRemove;
    }

    if (!hunk.has_edits()) {
      // We are done. We don't want this hunk.
      break;
    }

    hunk.PrintTo(&ss);
  }
  return ss.str();
}

}  // namespace edit_distance

namespace {

// The string representation of the values received in EqFailure() are already
// escaped. Split them on escaped '\n' boundaries. Leave all other escaped
// characters the same.
std::vector<std::string> SplitEscapedString(const std::string& str) {
  std::vector<std::string> lines;
  size_t start = 0, end = str.size();
  if (end > 2 && str[0] == '"' && str[end - 1] == '"') {
    ++start;
    --end;
  }
  bool escaped = false;
  for (size_t i = start; i + 1 < end; ++i) {
    if (escaped) {
      escaped = false;
      if (str[i] == 'n') {
        lines.push_back(str.substr(start, i - start - 1));
        start = i + 1;
      }
    } else {
      escaped = str[i] == '\\';
    }
  }
  lines.push_back(str.substr(start, end - start));
  return lines;
}

}  // namespace

// Constructs and returns the message for an equality assertion
// (e.g. ASSERT_EQ, EXPECT_STREQ, etc) failure.
//
// The first four parameters are the expressions used in the assertion
// and their values, as strings.  For example, for ASSERT_EQ(foo, bar)
// where foo is 5 and bar is 6, we have:
//
//   lhs_expression: "foo"
//   rhs_expression: "bar"
//   lhs_value:      "5"
//   rhs_value:      "6"
//
// The ignoring_case parameter is true if and only if the assertion is a
// *_STRCASEEQ*.  When it's true, the string "Ignoring case" will
// be inserted into the message.
AssertionResult EqFailure(const char* lhs_expression,
                          const char* rhs_expression,
                          const std::string& lhs_value,
                          const std::string& rhs_value, bool ignoring_case) {
  Message msg;
  msg << "Expected equality of these values:";
  msg << "\n " << lhs_expression;
  if (lhs_value != lhs_expression) {
    msg << "\n Which is: " << lhs_value;
  }
  msg << "\n " << rhs_expression;
  if (rhs_value != rhs_expression) {
    msg << "\n Which is: " << rhs_value;
  }

  if (ignoring_case) {
    msg << "\nIgnoring case";
  }

  if (!lhs_value.empty() && !rhs_value.empty()) {
    const std::vector<std::string> lhs_lines = SplitEscapedString(lhs_value);
    const std::vector<std::string> rhs_lines = SplitEscapedString(rhs_value);
    if (lhs_lines.size() > 1 || rhs_lines.size() > 1) {
      msg << "\nWith diff:\n"
          << edit_distance::CreateUnifiedDiff(lhs_lines, rhs_lines);
    }
  }

  return AssertionFailure() << msg;
}

// Constructs a failure message for Boolean assertions such as EXPECT_TRUE.
std::string GetBoolAssertionFailureMessage(
    const AssertionResult& assertion_result, const char* expression_text,
    const char* actual_predicate_value, const char* expected_predicate_value) {
  const char* actual_message = assertion_result.message();
  Message msg;
  msg << "Value of: " << expression_text
      << "\n Actual: " << actual_predicate_value;
  if (actual_message[0] != '\0') msg << " (" << actual_message << ")";
  msg << "\nExpected: " << expected_predicate_value;
  return msg.GetString();
}

// Helper function for implementing ASSERT_NEAR. Treats infinity as a specific
// value, such that comparing infinity to infinity is equal, the distance
// between -infinity and +infinity is infinity, and infinity <= infinity is
// true.
AssertionResult DoubleNearPredFormat(const char* expr1, const char* expr2,
                                     const char* abs_error_expr, double val1,
                                     double val2, double abs_error) {
  // We want to return success when the two values are infinity and at least
  // one of the following is true:
  //  * The values are the same-signed infinity.
  //  * The error limit itself is infinity.
  // This is done here so that we don't end up with a NaN when calculating the
  // difference in values.
  if (std::isinf(val1) && std::isinf(val2) &&
      (std::signbit(val1) == std::signbit(val2) ||
       (abs_error > 0.0 && std::isinf(abs_error)))) {
    return AssertionSuccess();
  }

  const double diff = fabs(val1 - val2);
  if (diff <= abs_error) return AssertionSuccess();

  // Find the value which is closest to zero.
  const double min_abs = std::min(fabs(val1), fabs(val2));
  // Find the distance to the next double from that value.
  const double epsilon =
      nextafter(min_abs, std::numeric_limits<double>::infinity()) - min_abs;
  // Detect the case where abs_error is so small that EXPECT_NEAR is
  // effectively the same as EXPECT_EQUAL, and give an informative error
  // message so that the situation can be more easily understood without
  // requiring exotic floating-point knowledge.
  // Don't do an epsilon check if abs_error is zero because that implies
  // that an equality check was actually intended.
  if (!(std::isnan)(val1) && !(std::isnan)(val2) && abs_error > 0 &&
      abs_error < epsilon) {
    return AssertionFailure()
           << "The difference between " << expr1 << " and " << expr2 << " is "
           << diff << ", where\n"
           << expr1 << " evaluates to " << val1 << ",\n"
           << expr2 << " evaluates to " << val2 << ".\nThe abs_error parameter "
           << abs_error_expr << " evaluates to " << abs_error
           << " which is smaller than the minimum distance between doubles for "
              "numbers of this magnitude which is "
           << epsilon
           << ", thus making this EXPECT_NEAR check equivalent to "
              "EXPECT_EQUAL. Consider using EXPECT_DOUBLE_EQ instead.";
  }
  return AssertionFailure()
         << "The difference between " << expr1 << " and " << expr2 << " is "
         << diff << ", which exceeds " << abs_error_expr << ", where\n"
         << expr1 << " evaluates to " << val1 << ",\n"
         << expr2 << " evaluates to " << val2 << ", and\n"
         << abs_error_expr << " evaluates to " << abs_error << ".";
}

// Helper template for implementing FloatLE() and DoubleLE().
template <typename RawType>
AssertionResult FloatingPointLE(const char* expr1, const char* expr2,
                                RawType val1, RawType val2) {
  // Returns success if val1 is less than val2,
  if (val1 < val2) {
    return AssertionSuccess();
  }

  // or if val1 is almost equal to val2.
  const FloatingPoint<RawType> lhs(val1), rhs(val2);
  if (lhs.AlmostEquals(rhs)) {
    return AssertionSuccess();
  }

  // Note that the above two checks will both fail if either val1 or
  // val2 is NaN, as the IEEE floating-point standard requires that
  // any predicate involving a NaN must return false.

  ::std::stringstream val1_ss;
  val1_ss << std::setprecision(std::numeric_limits<RawType>::digits10 + 2)
          << val1;

  ::std::stringstream val2_ss;
  val2_ss << std::setprecision(std::numeric_limits<RawType>::digits10 + 2)
          << val2;

  return AssertionFailure()
         << "Expected: (" << expr1 << ") <= (" << expr2 << ")\n"
         << " Actual: " << StringStreamToString(&val1_ss) << " vs "
         << StringStreamToString(&val2_ss);
}

}  // namespace internal

// Asserts that val1 is less than, or almost equal to, val2.  Fails
// otherwise.  In particular, it fails if either val1 or val2 is NaN.
AssertionResult FloatLE(const char* expr1, const char* expr2, float val1,
                        float val2) {
  return internal::FloatingPointLE<float>(expr1, expr2, val1, val2);
}

// Asserts that val1 is less than, or almost equal to, val2.  Fails
// otherwise.  In particular, it fails if either val1 or val2 is NaN.
AssertionResult DoubleLE(const char* expr1, const char* expr2, double val1,
                         double val2) {
  return internal::FloatingPointLE<double>(expr1, expr2, val1, val2);
}

namespace internal {

// The helper function for {ASSERT|EXPECT}_STREQ.
AssertionResult CmpHelperSTREQ(const char* lhs_expression,
                               const char* rhs_expression, const char* lhs,
                               const char* rhs) {
  if (String::CStringEquals(lhs, rhs)) {
    return AssertionSuccess();
  }

  return EqFailure(lhs_expression, rhs_expression, PrintToString(lhs),
                   PrintToString(rhs), false);
}

// The helper function for {ASSERT|EXPECT}_STRCASEEQ.
AssertionResult CmpHelperSTRCASEEQ(const char* lhs_expression,
                                   const char* rhs_expression, const char* lhs,
                                   const char* rhs) {
  if (String::CaseInsensitiveCStringEquals(lhs, rhs)) {
    return AssertionSuccess();
  }

  return EqFailure(lhs_expression, rhs_expression, PrintToString(lhs),
                   PrintToString(rhs), true);
}

// The helper function for {ASSERT|EXPECT}_STRNE.
AssertionResult CmpHelperSTRNE(const char* s1_expression,
                               const char* s2_expression, const char* s1,
--> --------------------

--> maximum size reached

--> --------------------