// 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.

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

#include <limits.h>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <cstdint>

#include <fstream>

#include <memory>

#if GTEST_OS_WINDOWS

# include <windows.h>

# include <io.h>

# include <sys/stat.h>

# include <map> // Used in ThreadLocal.

# ifdef _MSC_VER

# include <crtdbg.h>

# endif // _MSC_VER

#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_DRAGONFLY || GTEST_OS_FREEBSD || GTEST_OS_GNU_KFREEBSD || \

GTEST_OS_NETBSD || GTEST_OS_OPENBSD

# include <sys/sysctl.h>

# if GTEST_OS_DRAGONFLY || GTEST_OS_FREEBSD || GTEST_OS_GNU_KFREEBSD

# include <sys/user.h>

# endif

#endif

#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

#if GTEST_OS_FUCHSIA

# include <zircon/process.h>

# include <zircon/syscalls.h>

#endif // GTEST_OS_FUCHSIA

#include "gtest/gtest-spi.h"

#include "gtest/gtest-message.h"

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

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

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

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 || GTEST_OS_GNU_HURD

namespace {

template <typename T>

T ReadProcFileField(const std::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 std::string filename =

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

return ReadProcFileField<size_t>(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_DRAGONFLY || GTEST_OS_FREEBSD || GTEST_OS_GNU_KFREEBSD || \

GTEST_OS_NETBSD

#if GTEST_OS_NETBSD

#undef KERN_PROC

#define KERN_PROC KERN_PROC2

#define kinfo_proc kinfo_proc2

#endif

#if GTEST_OS_DRAGONFLY

#define KP_NLWP(kp) (kp.kp_nthreads)

#elif GTEST_OS_FREEBSD || GTEST_OS_GNU_KFREEBSD

#define KP_NLWP(kp) (kp.ki_numthreads)

#elif GTEST_OS_NETBSD

#define KP_NLWP(kp) (kp.p_nlwps)

#endif

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

// we cannot detect it.

size_t GetThreadCount() {

int mib[] = {

CTL_KERN,

KERN_PROC,

KERN_PROC_PID,

getpid(),

#if GTEST_OS_NETBSD

sizeof(struct kinfo_proc),

1,

#endif

};

u_int miblen = sizeof(mib) / sizeof(mib[0]);

struct kinfo_proc info;

size_t size = sizeof(info);

if (sysctl(mib, miblen, &info, &size, NULL, 0)) {

return 0;

}

return static_cast<size_t>(KP_NLWP(info));

}

#elif GTEST_OS_OPENBSD

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

// we cannot detect it.

size_t GetThreadCount() {

int mib[] = {

CTL_KERN,

KERN_PROC,

KERN_PROC_PID | KERN_PROC_SHOW_THREADS,

getpid(),

sizeof(struct kinfo_proc),

0,

};

u_int miblen = sizeof(mib) / sizeof(mib[0]);

// get number of structs

size_t size;

if (sysctl(mib, miblen, NULL, &size, NULL, 0)) {

return 0;

}

mib[5] = static_cast<int>(size / static_cast<size_t>(mib[4]));

// populate array of structs

struct kinfo_proc info[mib[5]];

if (sysctl(mib, miblen, &info, &size, NULL, 0)) {

return 0;

}

// exclude empty members

size_t nthreads = 0;

for (size_t i = 0; i < size / static_cast<size_t>(mib[4]); i++) {

if (info[i].p_tid != -1)

nthreads++;

}

return nthreads;

}

#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), nullptr);

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), nullptr, 0, &pid, 1);

if (status == 1) {

return entry.pi_thcount;

} else {

return 0;

}

}

#elif GTEST_OS_FUCHSIA

size_t GetThreadCount() {

int dummy_buffer;

size_t avail;

zx_status_t status = zx_object_get_info(

zx_process_self(),

ZX_INFO_PROCESS_THREADS,

&dummy_buffer,

0,

nullptr,

&avail);

if (status == ZX_OK) {

return avail;

} 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(static_cast<DWORD>(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_ != nullptr && handle_ != INVALID_HANDLE_VALUE;

}

Notification::Notification()

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

TRUE, // Do not reset automatically.

FALSE, // Initially unset.

nullptr)) { // Anonymous event.

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

}

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.

if (type_ == kDynamic) {

::DeleteCriticalSection(critical_section_);

delete critical_section_;

critical_section_ = nullptr;

}

}

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;

}

namespace {

#ifdef _MSC_VER

// Use the RAII idiom to flag mem allocs that are intentionally never

// deallocated. The motivation is to silence the false positive mem leaks

// that are reported by the debug version of MS's CRT which can only detect

// if an alloc is missing a matching deallocation.

// Example:

// MemoryIsNotDeallocated memory_is_not_deallocated;

// critical_section_ = new CRITICAL_SECTION;

//

class MemoryIsNotDeallocated

{

public:

MemoryIsNotDeallocated() : old_crtdbg_flag_(0) {

old_crtdbg_flag_ = _CrtSetDbgFlag(_CRTDBG_REPORT_FLAG);

// Set heap allocation block type to _IGNORE_BLOCK so that MS debug CRT

// doesn't report mem leak if there's no matching deallocation.

_CrtSetDbgFlag(old_crtdbg_flag_ & ~_CRTDBG_ALLOC_MEM_DF);

}

~MemoryIsNotDeallocated() {

// Restore the original _CRTDBG_ALLOC_MEM_DF flag

_CrtSetDbgFlag(old_crtdbg_flag_);

}

private:

int old_crtdbg_flag_;

GTEST_DISALLOW_COPY_AND_ASSIGN_(MemoryIsNotDeallocated);

};

#endif // _MSC_VER

} // namespace

// 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;

{

// Use RAII to flag that following mem alloc is never deallocated.

#ifdef _MSC_VER

MemoryIsNotDeallocated memory_is_not_deallocated;

#endif // _MSC_VER

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;

HANDLE thread_handle = ::CreateThread(

nullptr, // 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 != nullptr)

<< "CreateThread failed with error " << ::GetLastError() << ".";

if (thread_handle == nullptr) {

delete param;

}

return thread_handle;

}

private:

struct ThreadMainParam {

ThreadMainParam(Runnable* runnable, Notification* thread_can_start)

: runnable_(runnable),

thread_can_start_(thread_can_start) {

}

std::unique_ptr<Runnable> runnable_;

// Does not own.

Notification* thread_can_start_;

};

static DWORD WINAPI ThreadMain(void* ptr) {

// Transfers ownership.

std::unique_ptr<ThreadMainParam> param(static_cast<ThreadMainParam*>(ptr));

if (param->thread_can_start_ != nullptr)

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) {

#ifdef _MSC_VER

MemoryIsNotDeallocated memory_is_not_deallocated;

#endif // _MSC_VER

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,

std::shared_ptr<ThreadLocalValueHolderBase>(

thread_local_instance->NewValueForCurrentThread())))

.first;

}

return value_pos->second.get();

}

static void OnThreadLocalDestroyed(

const ThreadLocalBase* thread_local_instance) {

std::vector<std::shared_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<std::shared_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<const ThreadLocalBase*,

std::shared_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 != nullptr);

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

// to work correctly under Win98.

DWORD watcher_thread_id;

HANDLE watcher_thread = ::CreateThread(

nullptr, // 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 != nullptr);

// 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();

#ifdef _MSC_VER

MemoryIsNotDeallocated memory_is_not_deallocated;

#endif // _MSC_VER

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); // NOLINT

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

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 if and only if 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 if and only if 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 if and only if ch appears anywhere in str (excluding the

// terminating '\0' character).

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

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

}

// Returns true if and only if 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 if and only if "\\c" is a supported escape sequence.

bool IsValidEscape(char c) {

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

}

// Returns true if and only if 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.

static 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 == nullptr) {

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

return false;

}

bool is_valid = true;

// True if and only if ?, *, 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 if and only if 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 if and only if 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 == nullptr || str == nullptr) 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 if and only if 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 if and only if 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_ = nullptr;

if (regex != nullptr) {

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));