// Copyright 2008, 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)

#include "gtest/internal/gtest-port.h"

#include <limits.h>

#include <stdlib.h>

#include <stdio.h>

#include <string.h>

#include <fstream>

#if GTEST_OS_WINDOWS

# include <windows.h>

# include <io.h>

# include <sys/stat.h>

# include <map>  // Used in ThreadLocal.

#else

# include <unistd.h>

#endif  // GTEST_OS_WINDOWS

#if GTEST_OS_MAC

# include <mach/mach_init.h>

# include <mach/task.h>

# include <mach/vm_map.h>

#endif  // GTEST_OS_MAC

#if GTEST_OS_QNX

# include <devctl.h>

# include <fcntl.h>

# include <sys/procfs.h>

#endif  // GTEST_OS_QNX

#if GTEST_OS_AIX

# include <procinfo.h>

# include <sys/types.h>

#endif  // GTEST_OS_AIX

#include "gtest/gtest-spi.h"

#include "gtest/gtest-message.h"

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

#include "gtest/internal/gtest-string.h"

// Indicates that this translation unit is part of Google Test's

// implementation.  It must come before gtest-internal-inl.h is

// included, or there will be a compiler error.  This trick exists to

// prevent the accidental inclusion of gtest-internal-inl.h in the

// user's code.

#define GTEST_IMPLEMENTATION_ 1

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

#undef GTEST_IMPLEMENTATION_

namespace testing {

namespace internal {

#if defined(_MSC_VER) || defined(__BORLANDC__)

// MSVC and C++Builder do not provide a definition of STDERR_FILENO.

const int kStdOutFileno = 1;

const int kStdErrFileno = 2;

#else

const int kStdOutFileno = STDOUT_FILENO;

const int kStdErrFileno = STDERR_FILENO;

#endif  // _MSC_VER

#if GTEST_OS_LINUX

namespace {

template <typename T>

T ReadProcFileField(const string& filename, int field) {

  std::string dummy;

  std::ifstream file(filename.c_str());

  while (field-- > 0) {

    file >> dummy;

  }

  T output = 0;

  file >> output;

  return output;

}

}  // namespace

// Returns the number of active threads, or 0 when there is an error.

size_t GetThreadCount() {

  const string filename =

      (Message() << "/proc/" << getpid() << "/stat").GetString();

  return ReadProcFileField<int>(filename, 19);

}

#elif GTEST_OS_MAC

size_t GetThreadCount() {

  const task_t task = mach_task_self();

  mach_msg_type_number_t thread_count;

  thread_act_array_t thread_list;

  const kern_return_t status = task_threads(task, &thread_list, &thread_count);

  if (status == KERN_SUCCESS) {

    // task_threads allocates resources in thread_list and we need to free them

    // to avoid leaks.

    vm_deallocate(task,

                  reinterpret_cast<vm_address_t>(thread_list),

                  sizeof(thread_t) * thread_count);

    return static_cast<size_t>(thread_count);

  } else {

    return 0;

  }

}

#elif GTEST_OS_QNX

// Returns the number of threads running in the process, or 0 to indicate that

// we cannot detect it.

size_t GetThreadCount() {

  const int fd = open("/proc/self/as", O_RDONLY);

  if (fd < 0) {

    return 0;

  }

  procfs_info process_info;

  const int status =

      devctl(fd, DCMD_PROC_INFO, &process_info, sizeof(process_info), NULL);

  close(fd);

  if (status == EOK) {

    return static_cast<size_t>(process_info.num_threads);

  } else {

    return 0;

  }

}

#elif GTEST_OS_AIX

size_t GetThreadCount() {

  struct procentry64 entry;

  pid_t pid = getpid();

  int status = getprocs64(&entry, sizeof(entry), NULL, 0, &pid, 1);

  if (status == 1) {

    return entry.pi_thcount;

  } else {

    return 0;

  }

}

#else

size_t GetThreadCount() {

  // There's no portable way to detect the number of threads, so we just

  // return 0 to indicate that we cannot detect it.

  return 0;

}

#endif  // GTEST_OS_LINUX

#if GTEST_IS_THREADSAFE && GTEST_OS_WINDOWS

void SleepMilliseconds(int n) {

  ::Sleep(n);

}

AutoHandle::AutoHandle()

    : handle_(INVALID_HANDLE_VALUE) {}

AutoHandle::AutoHandle(Handle handle)

    : handle_(handle) {}

AutoHandle::~AutoHandle() {

  Reset();

}

AutoHandle::Handle AutoHandle::Get() const {

  return handle_;

}

void AutoHandle::Reset() {

  Reset(INVALID_HANDLE_VALUE);

}

void AutoHandle::Reset(HANDLE handle) {

  // Resetting with the same handle we already own is invalid.

  if (handle_ != handle) {

    if (IsCloseable()) {

      ::CloseHandle(handle_);

    }

    handle_ = handle;

  } else {

    GTEST_CHECK_(!IsCloseable())

        << "Resetting a valid handle to itself is likely a programmer error "

            "and thus not allowed.";

  }

}

bool AutoHandle::IsCloseable() const {

  // Different Windows APIs may use either of these values to represent an

  // invalid handle.

  return handle_ != NULL && handle_ != INVALID_HANDLE_VALUE;

}

Notification::Notification()

    : event_(::CreateEvent(NULL,   // Default security attributes.

                           TRUE,   // Do not reset automatically.

                           FALSE,  // Initially unset.

                           NULL)) {  // Anonymous event.

  GTEST_CHECK_(event_.Get() != NULL);

}

void Notification::Notify() {

  GTEST_CHECK_(::SetEvent(event_.Get()) != FALSE);

}

void Notification::WaitForNotification() {

  GTEST_CHECK_(

      ::WaitForSingleObject(event_.Get(), INFINITE) == WAIT_OBJECT_0);

}

Mutex::Mutex()

    : owner_thread_id_(0),

      type_(kDynamic),

      critical_section_init_phase_(0),

      critical_section_(new CRITICAL_SECTION) {

  ::InitializeCriticalSection(critical_section_);

}

Mutex::~Mutex() {

  // Static mutexes are leaked intentionally. It is not thread-safe to try

  // to clean them up.

  // TODO(yukawa): Switch to Slim Reader/Writer (SRW) Locks, which requires

  // nothing to clean it up but is available only on Vista and later.

  // http://msdn.microsoft.com/en-us/library/windows/desktop/aa904937.aspx

  if (type_ == kDynamic) {

    ::DeleteCriticalSection(critical_section_);

    delete critical_section_;

    critical_section_ = NULL;

  }

}

void Mutex::Lock() {

  ThreadSafeLazyInit();

  ::EnterCriticalSection(critical_section_);

  owner_thread_id_ = ::GetCurrentThreadId();

}

void Mutex::Unlock() {

  ThreadSafeLazyInit();

  // We don't protect writing to owner_thread_id_ here, as it's the

  // caller's responsibility to ensure that the current thread holds the

  // mutex when this is called.

  owner_thread_id_ = 0;

  ::LeaveCriticalSection(critical_section_);

}

// Does nothing if the current thread holds the mutex. Otherwise, crashes

// with high probability.

void Mutex::AssertHeld() {

  ThreadSafeLazyInit();

  GTEST_CHECK_(owner_thread_id_ == ::GetCurrentThreadId())

      << "The current thread is not holding the mutex @" << this;

}

// Initializes owner_thread_id_ and critical_section_ in static mutexes.

void Mutex::ThreadSafeLazyInit() {

  // Dynamic mutexes are initialized in the constructor.

  if (type_ == kStatic) {

    switch (

        ::InterlockedCompareExchange(&critical_section_init_phase_, 1L, 0L)) {

      case 0:

        // If critical_section_init_phase_ was 0 before the exchange, we

        // are the first to test it and need to perform the initialization.

        owner_thread_id_ = 0;

        critical_section_ = new CRITICAL_SECTION;

        ::InitializeCriticalSection(critical_section_);

        // Updates the critical_section_init_phase_ to 2 to signal

        // initialization complete.

        GTEST_CHECK_(::InterlockedCompareExchange(

                          &critical_section_init_phase_, 2L, 1L) ==

                      1L);

        break;

      case 1:

        // Somebody else is already initializing the mutex; spin until they

        // are done.

        while (::InterlockedCompareExchange(&critical_section_init_phase_,

                                            2L,

                                            2L) != 2L) {

          // Possibly yields the rest of the thread's time slice to other

          // threads.

          ::Sleep(0);

        }

        break;

      case 2:

        break;  // The mutex is already initialized and ready for use.

      default:

        GTEST_CHECK_(false)

            << "Unexpected value of critical_section_init_phase_ "

            << "while initializing a static mutex.";

    }

  }

}

namespace {

class ThreadWithParamSupport : public ThreadWithParamBase {

 public:

  static HANDLE CreateThread(Runnable* runnable,

                             Notification* thread_can_start) {

    ThreadMainParam* param = new ThreadMainParam(runnable, thread_can_start);

    DWORD thread_id;

    // TODO(yukawa): Consider to use _beginthreadex instead.

    HANDLE thread_handle = ::CreateThread(

        NULL,    // Default security.

        0,       // Default stack size.

        &ThreadWithParamSupport::ThreadMain,

        param,   // Parameter to ThreadMainStatic

        0x0,     // Default creation flags.

        &thread_id);  // Need a valid pointer for the call to work under Win98.

    GTEST_CHECK_(thread_handle != NULL) << "CreateThread failed with error "

                                        << ::GetLastError() << ".";

    if (thread_handle == NULL) {

      delete param;

    }

    return thread_handle;

  }

 private:

  struct ThreadMainParam {

    ThreadMainParam(Runnable* runnable, Notification* thread_can_start)

        : runnable_(runnable),

          thread_can_start_(thread_can_start) {

    }

    scoped_ptr<Runnable> runnable_;

    // Does not own.

    Notification* thread_can_start_;

  };

  static DWORD WINAPI ThreadMain(void* ptr) {

    // Transfers ownership.

    scoped_ptr<ThreadMainParam> param(static_cast<ThreadMainParam*>(ptr));

    if (param->thread_can_start_ != NULL)

      param->thread_can_start_->WaitForNotification();

    param->runnable_->Run();

    return 0;

  }

  // Prohibit instantiation.

  ThreadWithParamSupport();

  GTEST_DISALLOW_COPY_AND_ASSIGN_(ThreadWithParamSupport);

};

}  // namespace

ThreadWithParamBase::ThreadWithParamBase(Runnable *runnable,

                                         Notification* thread_can_start)

      : thread_(ThreadWithParamSupport::CreateThread(runnable,

                                                     thread_can_start)) {

}

ThreadWithParamBase::~ThreadWithParamBase() {

  Join();

}

void ThreadWithParamBase::Join() {

  GTEST_CHECK_(::WaitForSingleObject(thread_.Get(), INFINITE) == WAIT_OBJECT_0)

      << "Failed to join the thread with error " << ::GetLastError() << ".";

}

// Maps a thread to a set of ThreadIdToThreadLocals that have values

// instantiated on that thread and notifies them when the thread exits.  A

// ThreadLocal instance is expected to persist until all threads it has

// values on have terminated.

class ThreadLocalRegistryImpl {

 public:

  // Registers thread_local_instance as having value on the current thread.

  // Returns a value that can be used to identify the thread from other threads.

  static ThreadLocalValueHolderBase* GetValueOnCurrentThread(

      const ThreadLocalBase* thread_local_instance) {

    DWORD current_thread = ::GetCurrentThreadId();

    MutexLock lock(&mutex_);

    ThreadIdToThreadLocals* const thread_to_thread_locals =

        GetThreadLocalsMapLocked();

    ThreadIdToThreadLocals::iterator thread_local_pos =

        thread_to_thread_locals->find(current_thread);

    if (thread_local_pos == thread_to_thread_locals->end()) {

      thread_local_pos = thread_to_thread_locals->insert(

          std::make_pair(current_thread, ThreadLocalValues())).first;

      StartWatcherThreadFor(current_thread);

    }

    ThreadLocalValues& thread_local_values = thread_local_pos->second;

    ThreadLocalValues::iterator value_pos =

        thread_local_values.find(thread_local_instance);

    if (value_pos == thread_local_values.end()) {

      value_pos =

          thread_local_values

              .insert(std::make_pair(

                  thread_local_instance,

                  linked_ptr<ThreadLocalValueHolderBase>(

                      thread_local_instance->NewValueForCurrentThread())))

              .first;

    }

    return value_pos->second.get();

  }

  static void OnThreadLocalDestroyed(

      const ThreadLocalBase* thread_local_instance) {

    std::vector<linked_ptr<ThreadLocalValueHolderBase> > value_holders;

    // Clean up the ThreadLocalValues data structure while holding the lock, but

    // defer the destruction of the ThreadLocalValueHolderBases.

    {

      MutexLock lock(&mutex_);

      ThreadIdToThreadLocals* const thread_to_thread_locals =

          GetThreadLocalsMapLocked();

      for (ThreadIdToThreadLocals::iterator it =

          thread_to_thread_locals->begin();

          it != thread_to_thread_locals->end();

          ++it) {

        ThreadLocalValues& thread_local_values = it->second;

        ThreadLocalValues::iterator value_pos =

            thread_local_values.find(thread_local_instance);

        if (value_pos != thread_local_values.end()) {

          value_holders.push_back(value_pos->second);

          thread_local_values.erase(value_pos);

          // This 'if' can only be successful at most once, so theoretically we

          // could break out of the loop here, but we don't bother doing so.

        }

      }

    }

    // Outside the lock, let the destructor for 'value_holders' deallocate the

    // ThreadLocalValueHolderBases.

  }

  static void OnThreadExit(DWORD thread_id) {

    GTEST_CHECK_(thread_id != 0) << ::GetLastError();

    std::vector<linked_ptr<ThreadLocalValueHolderBase> > value_holders;

    // Clean up the ThreadIdToThreadLocals data structure while holding the

    // lock, but defer the destruction of the ThreadLocalValueHolderBases.

    {

      MutexLock lock(&mutex_);

      ThreadIdToThreadLocals* const thread_to_thread_locals =

          GetThreadLocalsMapLocked();

      ThreadIdToThreadLocals::iterator thread_local_pos =

          thread_to_thread_locals->find(thread_id);

      if (thread_local_pos != thread_to_thread_locals->end()) {

        ThreadLocalValues& thread_local_values = thread_local_pos->second;

        for (ThreadLocalValues::iterator value_pos =

            thread_local_values.begin();

            value_pos != thread_local_values.end();

            ++value_pos) {

          value_holders.push_back(value_pos->second);

        }

        thread_to_thread_locals->erase(thread_local_pos);

      }

    }

    // Outside the lock, let the destructor for 'value_holders' deallocate the

    // ThreadLocalValueHolderBases.

  }

 private:

  // In a particular thread, maps a ThreadLocal object to its value.

  typedef std::map

                   linked_ptr<ThreadLocalValueHolderBase> > ThreadLocalValues;

  // Stores all ThreadIdToThreadLocals having values in a thread, indexed by

  // thread's ID.

  typedef std::map<DWORD, ThreadLocalValues> ThreadIdToThreadLocals;

  // Holds the thread id and thread handle that we pass from

  // StartWatcherThreadFor to WatcherThreadFunc.

  typedef std::pair<DWORD, HANDLE> ThreadIdAndHandle;

  static void StartWatcherThreadFor(DWORD thread_id) {

    // The returned handle will be kept in thread_map and closed by

    // watcher_thread in WatcherThreadFunc.

    HANDLE thread = ::OpenThread(SYNCHRONIZE | THREAD_QUERY_INFORMATION,

                                 FALSE,

                                 thread_id);

    GTEST_CHECK_(thread != NULL);

    // We need to to pass a valid thread ID pointer into CreateThread for it

    // to work correctly under Win98.

    DWORD watcher_thread_id;

    HANDLE watcher_thread = ::CreateThread(

        NULL,   // Default security.

        0,      // Default stack size

        &ThreadLocalRegistryImpl::WatcherThreadFunc,

        reinterpret_cast<LPVOID>(new ThreadIdAndHandle(thread_id, thread)),

        CREATE_SUSPENDED,

        &watcher_thread_id);

    GTEST_CHECK_(watcher_thread != NULL);

    // Give the watcher thread the same priority as ours to avoid being

    // blocked by it.

    ::SetThreadPriority(watcher_thread,

                        ::GetThreadPriority(::GetCurrentThread()));

    ::ResumeThread(watcher_thread);

    ::CloseHandle(watcher_thread);

  }

  // Monitors exit from a given thread and notifies those

  // ThreadIdToThreadLocals about thread termination.

  static DWORD WINAPI WatcherThreadFunc(LPVOID param) {

    const ThreadIdAndHandle* tah =

        reinterpret_cast<const ThreadIdAndHandle*>(param);

    GTEST_CHECK_(

        ::WaitForSingleObject(tah->second, INFINITE) == WAIT_OBJECT_0);

    OnThreadExit(tah->first);

    ::CloseHandle(tah->second);

    delete tah;

    return 0;

  }

  // Returns map of thread local instances.

  static ThreadIdToThreadLocals* GetThreadLocalsMapLocked() {

    mutex_.AssertHeld();

    static ThreadIdToThreadLocals* map = new ThreadIdToThreadLocals;

    return map;

  }

  // Protects access to GetThreadLocalsMapLocked() and its return value.

  static Mutex mutex_;

  // Protects access to GetThreadMapLocked() and its return value.

  static Mutex thread_map_mutex_;

};

Mutex ThreadLocalRegistryImpl::mutex_(Mutex::kStaticMutex);

Mutex ThreadLocalRegistryImpl::thread_map_mutex_(Mutex::kStaticMutex);

ThreadLocalValueHolderBase* ThreadLocalRegistry::GetValueOnCurrentThread(

      const ThreadLocalBase* thread_local_instance) {

  return ThreadLocalRegistryImpl::GetValueOnCurrentThread(

      thread_local_instance);

}

void ThreadLocalRegistry::OnThreadLocalDestroyed(

      const ThreadLocalBase* thread_local_instance) {

  ThreadLocalRegistryImpl::OnThreadLocalDestroyed(thread_local_instance);

}

#endif  // GTEST_IS_THREADSAFE && GTEST_OS_WINDOWS

#if GTEST_USES_POSIX_RE

// Implements RE.  Currently only needed for death tests.

RE::~RE() {

  if (is_valid_) {

    // regfree'ing an invalid regex might crash because the content

    // of the regex is undefined. Since the regex's are essentially

    // the same, one cannot be valid (or invalid) without the other

    // being so too.

    regfree(&partial_regex_);

    regfree(&full_regex_);

  }

  free(const_cast<char*>(pattern_));

}

// Returns true iff regular expression re matches the entire str.

bool RE::FullMatch(const char* str, const RE& re) {

  if (!re.is_valid_) return false;

  regmatch_t match;

  return regexec(&re.full_regex_, str, 1, &match, 0) == 0;

}

// Returns true iff regular expression re matches a substring of str

// (including str itself).

bool RE::PartialMatch(const char* str, const RE& re) {

  if (!re.is_valid_) return false;

  regmatch_t match;

  return regexec(&re.partial_regex_, str, 1, &match, 0) == 0;

}

// Initializes an RE from its string representation.

void RE::Init(const char* regex) {

  pattern_ = posix::StrDup(regex);

  // Reserves enough bytes to hold the regular expression used for a

  // full match.

  const size_t full_regex_len = strlen(regex) + 10;

  char* const full_pattern = new char[full_regex_len];

  snprintf(full_pattern, full_regex_len, "^(%s)$", regex);

  is_valid_ = regcomp(&full_regex_, full_pattern, REG_EXTENDED) == 0;

  // We want to call regcomp(&partial_regex_, ...) even if the

  // previous expression returns false.  Otherwise partial_regex_ may

  // not be properly initialized can may cause trouble when it's

  // freed.

  //

  // Some implementation of POSIX regex (e.g. on at least some

  // versions of Cygwin) doesn't accept the empty string as a valid

  // regex.  We change it to an equivalent form "()" to be safe.

  if (is_valid_) {

    const char* const partial_regex = (*regex == '\0') ? "()" : regex;

    is_valid_ = regcomp(&partial_regex_, partial_regex, REG_EXTENDED) == 0;

  }

  EXPECT_TRUE(is_valid_)

      << "Regular expression \"" << regex

      << "\" is not a valid POSIX Extended regular expression.";

  delete[] full_pattern;

}

#elif GTEST_USES_SIMPLE_RE

// Returns true iff ch appears anywhere in str (excluding the

// terminating '\0' character).

bool IsInSet(char ch, const char* str) {

  return ch != '\0' && strchr(str, ch) != NULL;

}

// Returns true iff ch belongs to the given classification.  Unlike

// similar functions in <ctype.h>, these aren't affected by the

// current locale.

bool IsAsciiDigit(char ch) { return '0' <= ch && ch <= '9'; }

bool IsAsciiPunct(char ch) {

  return IsInSet(ch, "^-!\"#$%&'()*+,./:;<=>?@[\\]_`{|}~");

}

bool IsRepeat(char ch) { return IsInSet(ch, "?*+"); }

bool IsAsciiWhiteSpace(char ch) { return IsInSet(ch, " \f\n\r\t\v"); }

bool IsAsciiWordChar(char ch) {

  return ('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z') ||

      ('0' <= ch && ch <= '9') || ch == '_';

}

// Returns true iff "\\c" is a supported escape sequence.

bool IsValidEscape(char c) {

  return (IsAsciiPunct(c) || IsInSet(c, "dDfnrsStvwW"));

}

// Returns true iff the given atom (specified by escaped and pattern)

// matches ch.  The result is undefined if the atom is invalid.

bool AtomMatchesChar(bool escaped, char pattern_char, char ch) {

  if (escaped) {  // "\\p" where p is pattern_char.

    switch (pattern_char) {

      case 'd': return IsAsciiDigit(ch);

      case 'D': return !IsAsciiDigit(ch);

      case 'f': return ch == '\f';

      case 'n': return ch == '\n';

      case 'r': return ch == '\r';

      case 's': return IsAsciiWhiteSpace(ch);

      case 'S': return !IsAsciiWhiteSpace(ch);

      case 't': return ch == '\t';

      case 'v': return ch == '\v';

      case 'w': return IsAsciiWordChar(ch);

      case 'W': return !IsAsciiWordChar(ch);

    }

    return IsAsciiPunct(pattern_char) && pattern_char == ch;

  }

  return (pattern_char == '.' && ch != '\n') || pattern_char == ch;

}

// Helper function used by ValidateRegex() to format error messages.

std::string FormatRegexSyntaxError(const char* regex, int index) {

  return (Message() << "Syntax error at index " << index

          << " in simple regular expression \"" << regex << "\": ").GetString();

}

// Generates non-fatal failures and returns false if regex is invalid;

// otherwise returns true.

bool ValidateRegex(const char* regex) {

  if (regex == NULL) {

    // TODO(wan@google.com): fix the source file location in the

    // assertion failures to match where the regex is used in user

    // code.

    ADD_FAILURE() << "NULL is not a valid simple regular expression.";

    return false;

  }

  bool is_valid = true;

  // True iff ?, *, or + can follow the previous atom.

  bool prev_repeatable = false;

  for (int i = 0; regex[i]; i++) {

    if (regex[i] == '\\') {  // An escape sequence

      i++;

      if (regex[i] == '\0') {

        ADD_FAILURE() << FormatRegexSyntaxError(regex, i - 1)

                      << "'\\' cannot appear at the end.";

        return false;

      }

      if (!IsValidEscape(regex[i])) {

        ADD_FAILURE() << FormatRegexSyntaxError(regex, i - 1)

                      << "invalid escape sequence \"\\" << regex[i] << "\".";

        is_valid = false;

      }

      prev_repeatable = true;

    } else {  // Not an escape sequence.

      const char ch = regex[i];

      if (ch == '^' && i > 0) {

        ADD_FAILURE() << FormatRegexSyntaxError(regex, i)

                      << "'^' can only appear at the beginning.";

        is_valid = false;

      } else if (ch == '$' && regex[i + 1] != '\0') {

        ADD_FAILURE() << FormatRegexSyntaxError(regex, i)

                      << "'$' can only appear at the end.";

        is_valid = false;

      } else if (IsInSet(ch, "()[]{}|")) {

        ADD_FAILURE() << FormatRegexSyntaxError(regex, i)

                      << "'" << ch << "' is unsupported.";

        is_valid = false;

      } else if (IsRepeat(ch) && !prev_repeatable) {

        ADD_FAILURE() << FormatRegexSyntaxError(regex, i)

                      << "'" << ch << "' can only follow a repeatable token.";

        is_valid = false;

      }

      prev_repeatable = !IsInSet(ch, "^$?*+");

    }

  }

  return is_valid;

}

// Matches a repeated regex atom followed by a valid simple regular

// expression.  The regex atom is defined as c if escaped is false,

// or \c otherwise.  repeat is the repetition meta character (?, *,

// or +).  The behavior is undefined if str contains too many

// characters to be indexable by size_t, in which case the test will

// probably time out anyway.  We are fine with this limitation as

// std::string has it too.

bool MatchRepetitionAndRegexAtHead(

    bool escaped, char c, char repeat, const char* regex,

    const char* str) {

  const size_t min_count = (repeat == '+') ? 1 : 0;

  const size_t max_count = (repeat == '?') ? 1 :

      static_cast<size_t>(-1) - 1;

  // We cannot call numeric_limits::max() as it conflicts with the

  // max() macro on Windows.

  for (size_t i = 0; i <= max_count; ++i) {

    // We know that the atom matches each of the first i characters in str.

    if (i >= min_count && MatchRegexAtHead(regex, str + i)) {

      // We have enough matches at the head, and the tail matches too.

      // Since we only care about *whether* the pattern matches str

      // (as opposed to *how* it matches), there is no need to find a

      // greedy match.

      return true;

    }

    if (str[i] == '\0' || !AtomMatchesChar(escaped, c, str[i]))

      return false;

  }

  return false;

}

// Returns true iff regex matches a prefix of str.  regex must be a

// valid simple regular expression and not start with "^", or the

// result is undefined.

bool MatchRegexAtHead(const char* regex, const char* str) {

  if (*regex == '\0')  // An empty regex matches a prefix of anything.

    return true;

  // "$" only matches the end of a string.  Note that regex being

  // valid guarantees that there's nothing after "$" in it.

  if (*regex == '$')

    return *str == '\0';

  // Is the first thing in regex an escape sequence?

  const bool escaped = *regex == '\\';

  if (escaped)

    ++regex;

  if (IsRepeat(regex[1])) {

    // MatchRepetitionAndRegexAtHead() calls MatchRegexAtHead(), so

    // here's an indirect recursion.  It terminates as the regex gets

    // shorter in each recursion.

    return MatchRepetitionAndRegexAtHead(

        escaped, regex[0], regex[1], regex + 2, str);

  } else {

    // regex isn't empty, isn't "$", and doesn't start with a

    // repetition.  We match the first atom of regex with the first

    // character of str and recurse.

    return (*str != '\0') && AtomMatchesChar(escaped, *regex, *str) &&

        MatchRegexAtHead(regex + 1, str + 1);

  }

}

// Returns true iff regex matches any substring of str.  regex must be

// a valid simple regular expression, or the result is undefined.

//

// The algorithm is recursive, but the recursion depth doesn't exceed

// the regex length, so we won't need to worry about running out of

// stack space normally.  In rare cases the time complexity can be

// exponential with respect to the regex length + the string length,

// but usually it's must faster (often close to linear).

bool MatchRegexAnywhere(const char* regex, const char* str) {

  if (regex == NULL || str == NULL)

    return false;

  if (*regex == '^')

    return MatchRegexAtHead(regex + 1, str);

  // A successful match can be anywhere in str.

  do {

    if (MatchRegexAtHead(regex, str))

      return true;

  } while (*str++ != '\0');

  return false;

}

// Implements the RE class.

RE::~RE() {

  free(const_cast<char*>(pattern_));

  free(const_cast<char*>(full_pattern_));

}

// Returns true iff regular expression re matches the entire str.

bool RE::FullMatch(const char* str, const RE& re) {

  return re.is_valid_ && MatchRegexAnywhere(re.full_pattern_, str);

}

// Returns true iff regular expression re matches a substring of str

// (including str itself).

bool RE::PartialMatch(const char* str, const RE& re) {

  return re.is_valid_ && MatchRegexAnywhere(re.pattern_, str);

}

// Initializes an RE from its string representation.

void RE::Init(const char* regex) {

  pattern_ = full_pattern_ = NULL;

  if (regex != NULL) {

    pattern_ = posix::StrDup(regex);

  }

  is_valid_ = ValidateRegex(regex);

  if (!is_valid_) {

    // No need to calculate the full pattern when the regex is invalid.

    return;

  }

  const size_t len = strlen(regex);

  // Reserves enough bytes to hold the regular expression used for a

  // full match: we need space to prepend a '^', append a '$', and

  // terminate the string with '\0'.

  char* buffer = static_cast<char*>(malloc(len + 3));

  full_pattern_ = buffer;

  if (*regex != '^')

    *buffer++ = '^';  // Makes sure full_pattern_ starts with '^'.

  // We don't use snprintf or strncpy, as they trigger a warning when

  // compiled with VC++ 8.0.

  memcpy(buffer, regex, len);

  buffer += len;

  if (len == 0 || regex[len - 1] != '$')

    *buffer++ = '$';  // Makes sure full_pattern_ ends with '$'.

  *buffer = '\0';

}

#endif  // GTEST_USES_POSIX_RE

const char kUnknownFile[] = "unknown file";

// Formats a source file path and a line number as they would appear

// in an error message from the compiler used to compile this code.

GTEST_API_ ::std::string FormatFileLocation(const char* file, int line) {