atlrx.h

// This is a part of the Active Template Library.
// Copyright (C) Microsoft Corporation
// All rights reserved.
//
// This source code is only intended as a supplement to the
// Active Template Library Reference and related
// electronic documentation provided with the library.
// See these sources for detailed information regarding the
// Active Template Library product.

#ifndef __ATLRX_H__
#define __ATLRX_H__

#pragma once

#include <atlbase.h>
#include <atlcoll.h>
#include <mbstring.h>

#ifndef ATL_REGEXP_MIN_STACK
#define ATL_REGEXP_MIN_STACK 256
#endif

/* 
	Regular Expression Grammar

	R    - top level grammar rule
	RE   - regular expression
	AltE - Alternative expression
	E    - expression
	SE   - simple expression

	R -> RE
		 '^'RE		(matches begining of string)

	RE -> AltE RE
		  AltE


	AltE -> E
			E '|' AltE
	E -> SE (RepeatOp '?'?)?
	SE -> Arg
		Group
		CharClass
		'\'Abbrev		(see below)
		'\'EscapedChar	(any character including reserved symbols)
		'\'Digit+    (Arg back reference)
		'!'   (not)
		'.'   (any char)
		'$'   (end of input)
		Symbol			(any non-reserved character)
	Arg -> '{'RE'}'
	Group -> '('RE')'
	CharClass -> '[' '^'? CharSet ']'
	CharSet -> CharItem+
	CharItem -> Char('-'Char)?
	RepeatOp ->  '*'
				 '+'
				 '?'
	Abbrev -> Abbreviation defined in CAtlRECharTraits
		Abbrev  Expansion					Meaning
		a		([a-zA-Z0-9])				alpha numeric
		b		([ \\t])					white space (blank)
		c		([a-zA-Z])					alpha
		d		([0-9])						digit
		h		([0-9a-fA-F])				hex digit
		n		(\r|(\r?\n))				newline
		q		(\"[^\"]*\")|(\'[^\']*\')	quoted string
		w		([a-zA-Z]+)					simple word
		z		([0-9]+)					integer
*/

#pragma pack(push,_ATL_PACKING)
namespace ATL {

//Convertion utility classes used to convert char* to RECHAR.
//Used by rx debugging printing.
template <typename RECHARTYPE=char>
class CAToREChar
{
public:
	CAToREChar(const char* psz) throw()
	: m_psz(psz)
	{
	}
	operator const RECHARTYPE*() const throw() { return m_psz; }
	const char* m_psz;
};

template<>
class CAToREChar<wchar_t>
{
public:
	CAToREChar(const char* psz) throw()
	: m_a2w(psz)
	{
	}
	operator const wchar_t*() const throw() { return (wchar_t*)m_a2w; }
	
private:
	CA2W m_a2w;
};

class CAtlRECharTraitsA
{
public:
	typedef char RECHARTYPE;

	static size_t GetBitFieldForRangeArrayIndex(const RECHARTYPE *sz) throw()
	{
#ifndef ATL_NO_CHECK_BIT_FIELD
		ATLASSERT(UseBitFieldForRange());
#endif
		return static_cast<size_t>(static_cast<unsigned char>(*sz));		
	}
	static RECHARTYPE *Next(const RECHARTYPE *sz) throw()
	{
		return (RECHARTYPE *) (sz+1);
	}

	static int Strncmp(const RECHARTYPE *szLeft, const RECHARTYPE *szRight, size_t nCount) throw()
	{
		return strncmp(szLeft, szRight, nCount);
	}

	static int Strnicmp(const RECHARTYPE *szLeft, const RECHARTYPE *szRight, size_t nCount) throw()
	{
		return _strnicmp(szLeft, szRight, nCount);
	}

	_ATL_INSECURE_DEPRECATE("CAtlRECharTraitsA::Strlwr must be passed a buffer size.")
	static RECHARTYPE *Strlwr(RECHARTYPE *sz) throw()
	{
		#pragma warning (push)
		#pragma warning(disable : 4996)
		return _strlwr(sz);
		#pragma warning (pop)
	}

	static RECHARTYPE *Strlwr(RECHARTYPE *sz, int nSize) throw()
	{
		Checked::strlwr_s(sz, nSize);
		return sz;
	}

	static long Strtol(const RECHARTYPE *sz, RECHARTYPE **szEnd, int nBase) throw()
	{
		return strtol(sz, szEnd, nBase);
	}

	static int Isdigit(RECHARTYPE ch) throw()
	{
		return isdigit(static_cast<unsigned char>(ch));
	}

	static const RECHARTYPE** GetAbbrevs()
	{
		static const RECHARTYPE *s_szAbbrevs[] = 
		{
			"a([a-zA-Z0-9])",	// alpha numeric
			"b([ \\t])",		// white space (blank)
			"c([a-zA-Z])",	// alpha
			"d([0-9])",		// digit
			"h([0-9a-fA-F])",	// hex digit
			"n(\r|(\r?\n))",	// newline
			"q(\"[^\"]*\")|(\'[^\']*\')",	// quoted string
			"w([a-zA-Z]+)",	// simple word
			"z([0-9]+)",		// integer
			NULL
		};

		return s_szAbbrevs;
	}

	static BOOL UseBitFieldForRange() throw()
	{
		return TRUE;
	}

	static int ByteLen(const RECHARTYPE *sz) throw()
	{
		return int(strlen(sz));
	}
};

class CAtlRECharTraitsW
{
public:
	typedef WCHAR RECHARTYPE;
	
	static size_t GetBitFieldForRangeArrayIndex(const RECHARTYPE *sz) throw()
	{		
#ifndef ATL_NO_CHECK_BIT_FIELD
		ATLASSERT(UseBitFieldForRange());
#endif
		return static_cast<size_t>(*sz);
	}
	static RECHARTYPE *Next(const RECHARTYPE *sz) throw()
	{
		return (RECHARTYPE *) (sz+1);
	}

	static int Strncmp(const RECHARTYPE *szLeft, const RECHARTYPE *szRight, size_t nCount) throw()
	{
		return wcsncmp(szLeft, szRight, nCount);
	}

	static int Strnicmp(const RECHARTYPE *szLeft, const RECHARTYPE *szRight, size_t nCount) throw()
	{
		return _wcsnicmp(szLeft, szRight, nCount);
	}

	_ATL_INSECURE_DEPRECATE("CAtlRECharTraitsW::Strlwr must be passed a buffer size.")
	static RECHARTYPE *Strlwr(RECHARTYPE *sz) throw()
	{
		#pragma warning (push)
		#pragma warning(disable : 4996)
		return _wcslwr(sz);
		#pragma warning (pop)
	}

	static RECHARTYPE *Strlwr(RECHARTYPE *sz, int nSize) throw()
	{
		Checked::wcslwr_s(sz, nSize);
		return sz;
	}

	static long Strtol(const RECHARTYPE *sz, RECHARTYPE **szEnd, int nBase) throw()
	{
		return wcstol(sz, szEnd, nBase);
	}

	static int Isdigit(RECHARTYPE ch) throw()
	{
		return iswdigit(ch);
	}

	static const RECHARTYPE** GetAbbrevs()
	{
		static const RECHARTYPE *s_szAbbrevs[] = 
		{
			L"a([a-zA-Z0-9])",	// alpha numeric
			L"b([ \\t])",		// white space (blank)
			L"c([a-zA-Z])",	// alpha
			L"d([0-9])",		// digit
			L"h([0-9a-fA-F])",	// hex digit
			L"n(\r|(\r?\n))",	// newline
			L"q(\"[^\"]*\")|(\'[^\']*\')",	// quoted string
			L"w([a-zA-Z]+)",	// simple word
			L"z([0-9]+)",		// integer
			NULL
		};

		return s_szAbbrevs;
	}

	static BOOL UseBitFieldForRange() throw()
	{
		return FALSE;
	}

	static int ByteLen(const RECHARTYPE *sz) throw()
	{
		return int(wcslen(sz)*sizeof(WCHAR));
	}
};

class CAtlRECharTraitsMB
{
public:
	typedef unsigned char RECHARTYPE;

	static size_t GetBitFieldForRangeArrayIndex(const RECHARTYPE *sz) throw()
	{		
#ifndef ATL_NO_CHECK_BIT_FIELD
		ATLASSERT(UseBitFieldForRange());
#endif

		return static_cast<size_t>(*sz);		
	}

	static RECHARTYPE *Next(const RECHARTYPE *sz) throw()
	{
		return _mbsinc(sz);
	}

	static int Strncmp(const RECHARTYPE *szLeft, const RECHARTYPE *szRight, size_t nCount) throw()
	{
		return _mbsncmp(szLeft, szRight, nCount);
	}

	static int Strnicmp(const RECHARTYPE *szLeft, const RECHARTYPE *szRight, size_t nCount) throw()
	{
		return _mbsnicmp(szLeft, szRight, nCount);
	}

	_ATL_INSECURE_DEPRECATE("CAtlRECharTraitsMB::Strlwr must be passed a buffer size.")
	static RECHARTYPE *Strlwr(RECHARTYPE *sz) throw()
	{
		#pragma warning (push)
		#pragma warning(disable : 4996)
		return _mbslwr(sz);
		#pragma warning (pop)
	}

	static RECHARTYPE *Strlwr(RECHARTYPE *sz, int nSize) throw()
	{
		Checked::mbslwr_s(sz, nSize);
		return sz;
	}

	static long Strtol(const RECHARTYPE *sz, RECHARTYPE **szEnd, int nBase) throw()
	{
		return strtol((const char *) sz, (char **) szEnd, nBase);
	}

	static int Isdigit(RECHARTYPE ch) throw()
	{
		return _ismbcdigit((unsigned int) ch);
	}

	static const RECHARTYPE** GetAbbrevs()
	{
		return reinterpret_cast<const RECHARTYPE **>(CAtlRECharTraitsA::GetAbbrevs());
	}

	static BOOL UseBitFieldForRange() throw()
	{
		return FALSE;
	}

	static int ByteLen(const RECHARTYPE *sz) throw()
	{
		return (int)strlen((const char *) sz);
	}
};

#ifndef _UNICODE
typedef CAtlRECharTraitsA CAtlRECharTraits;
#else	// _UNICODE
typedef CAtlRECharTraitsW CAtlRECharTraits;
#endif // !_UNICODE
// Note: If you want to use CAtlRECharTraitsMB you must pass it in
// as a template argument

template <class CharTraits=CAtlRECharTraits>
class CAtlRegExp;	// forward declaration

template <class CharTraits=CAtlRECharTraits>
class CAtlREMatchContext
{
public:
	friend CAtlRegExp<CharTraits>;
	typedef typename CharTraits::RECHARTYPE RECHAR;

	struct MatchGroup
	{
		const RECHAR *szStart;
		const RECHAR *szEnd;
	};

	UINT m_uNumGroups;

	MatchGroup m_Match;

	void GetMatch(UINT nIndex, const RECHAR **szStart, const RECHAR **szEnd)
	{
		ATLENSURE(szStart != NULL);
		ATLENSURE(szEnd != NULL);
		ATLENSURE(nIndex >=0 && nIndex < m_uNumGroups);
		*szStart = m_Matches[nIndex].szStart;
		*szEnd = m_Matches[nIndex].szEnd;
	}

	void GetMatch(UINT nIndex, MatchGroup *pGroup)
	{
		 
		ATLENSURE(pGroup != NULL);
		ATLENSURE(nIndex >=0&&(static_cast<UINT>(nIndex))< m_uNumGroups);
		pGroup->szStart = m_Matches[nIndex].szStart;
		pGroup->szEnd = m_Matches[nIndex].szEnd;
	}

protected:
	CAutoVectorPtr<void *> m_Mem;
	CAutoVectorPtr<MatchGroup> m_Matches;
	CAtlArray<void *> m_stack;
	size_t m_nTos;

public:
	CAtlREMatchContext(size_t nInitStackSize=ATL_REGEXP_MIN_STACK)
	{
		m_uNumGroups = 0;
		m_nTos = 0;
		m_stack.SetCount(nInitStackSize);
		m_Match.szStart = NULL;
		m_Match.szEnd = NULL;
	}

protected:
	BOOL Initialize(UINT uRequiredMem, UINT uNumGroups) throw()
	{
		m_nTos = 0;

		m_uNumGroups = 0;
		m_Matches.Free();

		if (!m_Matches.Allocate(uNumGroups))
			return FALSE;

		m_uNumGroups = uNumGroups;

		m_Mem.Free();

		if (!m_Mem.Allocate(uRequiredMem))
			return FALSE;

		memset(m_Mem.m_p, 0x00, uRequiredMem*sizeof(void *));

		memset(m_Matches, 0x00, m_uNumGroups * sizeof(MatchGroup));
		return TRUE;
	}

	BOOL Push(void *p)
	{
		m_nTos++;
		if (m_stack.GetCount() <= (UINT) m_nTos)
		{
			if (!m_stack.SetCount((m_nTos+1)*2))
			{
				m_nTos--;
				return FALSE;
			}
		}
		m_stack[m_nTos] = p;
		return TRUE;
	}

	BOOL Push(size_t n)
	{
		return Push((void *) n);
	}

	void *Pop() throw()
	{
		if (m_nTos==0)
		{
			// stack underflow
			// this should never happen at match time.
			// (the parsing succeeded when it shouldn't have)
			ATLASSERT(FALSE);
			return NULL;
		}
		void *p = m_stack[m_nTos];
		m_nTos--;
		return p;
	}
};

enum REParseError {
	REPARSE_ERROR_OK = 0,				// No error occurred
	REPARSE_ERROR_OUTOFMEMORY,			// Out of memory
	REPARSE_ERROR_BRACE_EXPECTED,		// A closing brace was expected
	REPARSE_ERROR_PAREN_EXPECTED,		// A closing parenthesis was expected
	REPARSE_ERROR_BRACKET_EXPECTED,		// A closing bracket was expected
	REPARSE_ERROR_UNEXPECTED,			// An unspecified fatal error occurred
	REPARSE_ERROR_EMPTY_RANGE,			// A range expression was empty
	REPARSE_ERROR_INVALID_GROUP,		// A backreference was made to a group
										// that did not exist
	REPARSE_ERROR_INVALID_RANGE,		// An invalid range was specified
	REPARSE_ERROR_EMPTY_REPEATOP,		// A possibly empty * or + was detected
	REPARSE_ERROR_INVALID_INPUT,		// The input string was invalid
};

template <class CharTraits /* =CAtlRECharTraits */>
class CAtlRegExp
{
public:
	CAtlRegExp() throw()
	{
		m_uNumGroups = 0;
		m_uRequiredMem = 0;
		m_bCaseSensitive = TRUE;
		m_LastError = REPARSE_ERROR_OK;
	}

	typedef typename CharTraits::RECHARTYPE RECHAR;

	// CAtlRegExp::Parse
	// Parses the regular expression
	// returns REPARSE_ERROR_OK if successful, an REParseError otherwise
	REParseError Parse(const RECHAR *szRE, BOOL bCaseSensitive=TRUE)
	{
		ATLASSERT(szRE);
		if (!szRE)
			return REPARSE_ERROR_INVALID_INPUT;

		Reset();

		m_bCaseSensitive = bCaseSensitive;

		const RECHAR *szInput = szRE;

		if (!bCaseSensitive)
		{
			// copy the string
			int nSize = CharTraits::ByteLen(szRE)+sizeof(RECHAR);
			szInput = (const RECHAR *) malloc(nSize);
			if (!szInput)
				return REPARSE_ERROR_OUTOFMEMORY;

			Checked::memcpy_s((char *) szInput, nSize, szRE, nSize);

			CharTraits::Strlwr(const_cast<RECHAR *>(szInput), nSize/sizeof(RECHAR));
		}
		const RECHAR *sz = szInput;

		int nCall = AddInstruction(RE_CALL);
		if (nCall < 0)
			return REPARSE_ERROR_OUTOFMEMORY;

		if (*sz == '^')
		{
			if (AddInstruction(RE_FAIL) < 0)
				return REPARSE_ERROR_OUTOFMEMORY;
			sz++;
		}
		else
		{
			if (AddInstruction(RE_ADVANCE) < 0)
				return REPARSE_ERROR_OUTOFMEMORY;
		}

		bool bEmpty = true;
		ParseRE(&sz, bEmpty);
		if (!GetLastParseError())
		{
			GetInstruction(nCall).call.nTarget = 2;

			if (AddInstruction(RE_MATCH) < 0)
				return REPARSE_ERROR_OUTOFMEMORY;
		}

		if (szInput != szRE)
			free((void *) szInput);

		return GetLastParseError();
	}

	BOOL Match(const RECHAR *szIn, CAtlREMatchContext<CharTraits> *pContext, const RECHAR **ppszEnd=NULL)
	{
		ATLASSERT(szIn);
		ATLASSERT(pContext);

		if (!szIn || !pContext)
			return FALSE;

		if (ppszEnd)
			*ppszEnd = NULL;

		const RECHAR *szInput = szIn;

		if (!m_bCaseSensitive)
		{
			int nSize = CharTraits::ByteLen(szIn)+sizeof(RECHAR);
			szInput = (const RECHAR *) malloc(nSize);
			if (!szInput)
				return FALSE;

			Checked::memcpy_s((char *) szInput, nSize, szIn, nSize);
			CharTraits::Strlwr(const_cast<RECHAR *>(szInput), nSize/sizeof(RECHAR));
		}

		if (!pContext->Initialize(m_uRequiredMem, m_uNumGroups))
		{
			if (szInput != szIn)
				free((void *) szInput);
			return FALSE;
		}

		size_t ip = 0;

		const RECHAR *sz = szInput;
		const RECHAR *szCurrInput = szInput;

#pragma warning(push)
#pragma warning(disable:4127) // conditional expression is constant

		while (1)
		{
#ifdef ATLRX_DEBUG
			OnDebugEvent(ip, szInput, sz, pContext);
#endif
			if (ip == 0)
				pContext->m_Match.szStart = sz;

			switch (GetInstruction(ip).type)
 			{
			case RE_NOP:
				ip++;
				break;

			case RE_SYMBOL:
				if (GetInstruction(ip).symbol.nSymbol == static_cast<size_t>(static_cast<_TUCHAR>(*sz)))
				{
					sz = CharTraits::Next(sz);
					ip++;
				}
				else
				{
					ip = (size_t) pContext->Pop();
				}
				break;

			case RE_ANY:
				if (*sz)
				{
					sz = CharTraits::Next(sz);
					ip++;
				}
				else
				{
					ip = (size_t) pContext->Pop();
				}
				break;

			case RE_GROUP_START:
				pContext->m_Matches[GetInstruction(ip).group.nGroup].szStart = sz;
				ip++;
				break;

			case RE_GROUP_END:
				pContext->m_Matches[GetInstruction(ip).group.nGroup].szEnd = sz;
				ip++;
				break;

			case RE_PUSH_CHARPOS:
				pContext->Push((void *) sz);
				ip++;
				break;

			case RE_POP_CHARPOS:
				sz = (RECHAR *) pContext->Pop();
				ip++;
				break;

			case RE_CALL:
				pContext->Push(ip+1);
				ip = GetInstruction(ip).call.nTarget;
				break;

			case RE_JMP:
				ip = GetInstruction(ip).jmp.nTarget;
				break;

			case RE_RETURN:
				ip = (size_t) pContext->Pop();
				break;

			case RE_PUSH_MEMORY:
				pContext->Push((void *) (pContext->m_Mem[GetInstruction(ip).memory.nIndex]));
				ip++;
				break;

			case RE_POP_MEMORY:
				pContext->m_Mem[GetInstruction(ip).memory.nIndex] = pContext->Pop();
				ip++;
				break;

			case RE_STORE_CHARPOS:
				pContext->m_Mem[GetInstruction(ip).memory.nIndex] = (void *) sz;
				ip++;
				break;

			case RE_GET_CHARPOS:
				sz = (RECHAR *) pContext->m_Mem[GetInstruction(ip).memory.nIndex];
				ip++;
				break;

			case RE_STORE_STACKPOS:
				pContext->m_Mem[GetInstruction(ip).memory.nIndex] = (void *) pContext->m_nTos;
				ip++;
				break;

			case RE_GET_STACKPOS:
				pContext->m_nTos = (size_t) pContext->m_Mem[GetInstruction(ip).memory.nIndex];
				ip++;
				break;

			case RE_RET_NOMATCH:
				if (sz == (RECHAR *) pContext->m_Mem[GetInstruction(ip).memory.nIndex])
				{
					// do a return
					ip = (size_t) pContext->Pop();
				}
				else
					ip++;
				break;

			case RE_ADVANCE:
				sz = CharTraits::Next(szCurrInput);
				szCurrInput = sz;
				if (*sz == '\0')
					goto Error;
				ip = 0;
				pContext->m_nTos = 0;
				break;

			case RE_FAIL:
				goto Error;

			case RE_RANGE:
				{
					if (*sz == '\0')
					{
						ip = (size_t) pContext->Pop();
						break;
					}

					RECHAR *pBits = reinterpret_cast<RECHAR *>((&m_Instructions[ip]+1));
					size_t u = CharTraits::GetBitFieldForRangeArrayIndex(sz);
					if (pBits[u >> 3] & 1 << (u & 0x7))
					{
						ip += InstructionsPerRangeBitField();
						ip++;
						sz = CharTraits::Next(sz);
					}
					else
					{
						ip = (size_t) pContext->Pop();
					}
				}
				break;

			case RE_NOTRANGE:
				{
					if (*sz == '\0')
					{
						ip = (size_t) pContext->Pop();
						break;
					}

					RECHAR *pBits = reinterpret_cast<RECHAR *>((&m_Instructions[ip]+1));
					size_t u = static_cast<size_t>(static_cast<_TUCHAR>(* ((RECHAR *) sz)));
					if (pBits[u >> 3] & 1 << (u & 0x7))
					{
						ip = (size_t) pContext->Pop();
					}
					else
					{
						ip += InstructionsPerRangeBitField();
						ip++;
						sz = CharTraits::Next(sz);
					}
				}
				break;

			case RE_RANGE_EX:
				{
					if (*sz == '\0')
					{
						ip = (size_t) pContext->Pop();
						break;
					}

					BOOL bMatch = FALSE;
					size_t inEnd = GetInstruction(ip).range.nTarget;
					ip++;

					while (ip < inEnd)
					{						
						if (static_cast<size_t>(static_cast<_TUCHAR>(*sz)) >= GetInstruction(ip).memory.nIndex && 
							static_cast<size_t>(static_cast<_TUCHAR>(*sz)) <= GetInstruction(ip+1).memory.nIndex)
						{
							// if we match, we jump to the end
							sz = CharTraits::Next(sz);
							ip = inEnd;
							bMatch = TRUE;
						}
						else
						{
							ip += 2;
						}
					}
					if (!bMatch)
					{
						ip = (size_t) pContext->Pop();
					}
				}
				break;

			case RE_NOTRANGE_EX:
				{
					if (*sz == '\0')
					{
						ip = (size_t) pContext->Pop();
						break;
					}

					BOOL bMatch = TRUE;
					size_t inEnd = GetInstruction(ip).range.nTarget;
					ip++;

					while (ip < inEnd)
					{
						if (static_cast<size_t>(static_cast<_TUCHAR>(*sz)) >= GetInstruction(ip).memory.nIndex && 
							static_cast<size_t>(static_cast<_TUCHAR>(*sz)) <= GetInstruction(ip+1).memory.nIndex)
						{
							ip = (size_t) pContext->Pop();
							bMatch = FALSE;
							break;
						}
						else
						{
							// if we match, we jump to the end
							ip += 2;
						}
					}
					if (bMatch)
						sz = CharTraits::Next(sz);
				}
				break;

			case RE_PREVIOUS:
				{
					BOOL bMatch = FALSE;
					if (m_bCaseSensitive)
					{
						bMatch = !CharTraits::Strncmp(sz, pContext->m_Matches[GetInstruction(ip).prev.nGroup].szStart,
							pContext->m_Matches[GetInstruction(ip).prev.nGroup].szEnd-pContext->m_Matches[GetInstruction(ip).prev.nGroup].szStart);
					}
					else
					{
						bMatch = !CharTraits::Strnicmp(sz, pContext->m_Matches[GetInstruction(ip).prev.nGroup].szStart,
							pContext->m_Matches[GetInstruction(ip).prev.nGroup].szEnd-pContext->m_Matches[GetInstruction(ip).prev.nGroup].szStart);
					}
					if (bMatch)
					{
						sz += pContext->m_Matches[GetInstruction(ip).prev.nGroup].szEnd-pContext->m_Matches[GetInstruction(ip).prev.nGroup].szStart;
						ip++;
						break;
					}
					ip = (size_t) pContext->Pop();
				}
				break;

			case RE_MATCH:
				pContext->m_Match.szEnd = sz;
				if (!m_bCaseSensitive)
					FixupMatchContext(pContext, szIn, szInput);
				if (ppszEnd)
					*ppszEnd = szIn + (sz - szInput);
				if (szInput != szIn)
					free((void *) szInput);
				return TRUE;
				break;

			case RE_PUSH_GROUP:
				pContext->Push((void *) pContext->m_Matches[GetInstruction(ip).group.nGroup].szStart);
				pContext->Push((void *) pContext->m_Matches[GetInstruction(ip).group.nGroup].szEnd);
				ip++;
				break;

			case RE_POP_GROUP:
				pContext->m_Matches[GetInstruction(ip).group.nGroup].szEnd = (const RECHAR *) pContext->Pop();
				pContext->m_Matches[GetInstruction(ip).group.nGroup].szStart = (const RECHAR *) pContext->Pop();
				ip++;
				break;

			default:
				ATLASSERT(FALSE);
				break;
			}
		}

#pragma warning(pop) // 4127

		ATLASSERT(FALSE);
Error:
		pContext->m_Match.szEnd = sz;
		if (!m_bCaseSensitive)
			FixupMatchContext(pContext, szIn, szInput);
		if (ppszEnd)
			*ppszEnd = szIn + (sz - szInput);
		if (szInput != szIn)
			free((void *) szInput);
		return FALSE;
	}

protected:
	REParseError m_LastError;

	REParseError GetLastParseError() throw()
	{
		return m_LastError;
	}

	void SetLastParseError(REParseError Error) throw()
	{
		m_LastError = Error;
	}
	// CAtlRegExp::Reset
	// Removes all instructions to allow reparsing into the same instance
	void Reset() throw()
	{
		m_Instructions.RemoveAll();
		m_uRequiredMem = 0;
		m_bCaseSensitive = TRUE;
		m_uNumGroups = 0;
		SetLastParseError(REPARSE_ERROR_OK);
	}


	enum REInstructionType { 
		RE_NOP,
		RE_GROUP_START,
		RE_GROUP_END, 
		RE_SYMBOL,
		RE_ANY,
		RE_RANGE,
		RE_NOTRANGE,
		RE_RANGE_EX,
		RE_NOTRANGE_EX,
		RE_PLUS,
		RE_NG_PLUS,
		RE_QUESTION,
		RE_NG_QUESTION,
		RE_JMP,
		RE_PUSH_CHARPOS,
		RE_POP_CHARPOS,
		RE_CALL,
		RE_RETURN,
		RE_STAR_BEGIN,
		RE_NG_STAR_BEGIN, 
		RE_PUSH_MEMORY,
		RE_POP_MEMORY,
		RE_STORE_CHARPOS,
		RE_STORE_STACKPOS,
		RE_GET_CHARPOS,
		RE_GET_STACKPOS,
		RE_RET_NOMATCH,
		RE_PREVIOUS,
		RE_FAIL,
		RE_ADVANCE,
		RE_MATCH,
		RE_PUSH_GROUP,
		RE_POP_GROUP,
	};

	struct INSTRUCTION_SYMBOL
	{
		size_t nSymbol;
	};

	struct INSTRUCTION_JMP
	{
		size_t nTarget;	
	};

	struct INSTRUCTION_GROUP
	{
		size_t nGroup;
	};

	struct INSTRUCTION_CALL
	{
		size_t nTarget;
	};

	struct INSTRUCTION_MEMORY
	{
		size_t nIndex;
	};

	struct INSTRUCTION_PREVIOUS
	{
		size_t nGroup;
	};

	struct INSTRUCTION_RANGE_EX
	{
		size_t nTarget;
	};

	struct INSTRUCTION
	{
		REInstructionType type;
		union
		{
			INSTRUCTION_SYMBOL symbol;
			INSTRUCTION_JMP jmp;
			INSTRUCTION_GROUP group;
			INSTRUCTION_CALL call;
			INSTRUCTION_MEMORY memory;
			INSTRUCTION_PREVIOUS prev;
			INSTRUCTION_RANGE_EX range;
		};
	};

	inline int InstructionsPerRangeBitField() throw()
	{
		return (256/8) / sizeof(INSTRUCTION) + (((256/8) % sizeof(INSTRUCTION)) ? 1 : 0);
	}

	CAtlArray<INSTRUCTION> m_Instructions;

	UINT m_uNumGroups;
	UINT m_uRequiredMem;
	BOOL m_bCaseSensitive;


	// class used internally to restore
	// parsing state when unwinding
	class CParseState
	{
	public:
		int m_nNumInstructions;
		UINT m_uNumGroups;
		UINT m_uRequiredMem;

		CParseState(CAtlRegExp *pRegExp) throw()
		{
			m_nNumInstructions = (int) pRegExp->m_Instructions.GetCount();
			m_uNumGroups = pRegExp->m_uNumGroups;
			m_uRequiredMem = pRegExp->m_uRequiredMem;
		}

		void Restore(CAtlRegExp *pRegExp)
		{
			pRegExp->m_Instructions.SetCount(m_nNumInstructions);
			pRegExp->m_uNumGroups = m_uNumGroups;
			pRegExp->m_uRequiredMem = m_uRequiredMem;
		}
	};

	int AddInstruction(REInstructionType type)
	{
		if (!m_Instructions.SetCount(m_Instructions.GetCount()+1))
		{
			SetLastParseError(REPARSE_ERROR_OUTOFMEMORY);
			return -1;
		}

		m_Instructions[m_Instructions.GetCount()-1].type = type;
		return (int) m_Instructions.GetCount()-1;
	}

	BOOL PeekToken(const RECHAR **ppszRE, int ch) throw()
	{
		if (**ppszRE != ch)
			return FALSE;
		return TRUE;
	}

	BOOL MatchToken(const RECHAR **ppszRE, int ch) throw()
	{
		if (!PeekToken(ppszRE, ch))
			return FALSE;
		*ppszRE = CharTraits::Next(*ppszRE);
		return TRUE;
	}

	INSTRUCTION &GetInstruction(size_t nIndex) throw()
	{
		return m_Instructions[nIndex];
	}

	// ParseArg: parse grammar rule Arg
	int ParseArg(const RECHAR **ppszRE, bool &bEmpty)
	{
		int nPushGroup = AddInstruction(RE_PUSH_GROUP);
		if (nPushGroup < 0)
			return -1;

		GetInstruction(nPushGroup).group.nGroup = m_uNumGroups;

		int p = AddInstruction(RE_GROUP_START);
		if (p < 0)
			return -1;
		GetInstruction(p).group.nGroup = m_uNumGroups++;

		int nCall = AddInstruction(RE_CALL);
		if (nCall < 0)
			return -1;

		int nPopGroup = AddInstruction(RE_POP_GROUP);
		if (nPopGroup < 0)
			return -1;
		GetInstruction(nPopGroup).group.nGroup = GetInstruction(nPushGroup).group.nGroup;

		if (AddInstruction(RE_RETURN) < 0)
			return -1;

		int nAlt = ParseRE(ppszRE, bEmpty);
		if (nAlt < 0)
		{
			if (GetLastParseError())
				return -1;

			if (!PeekToken(ppszRE, '}'))
			{
				SetLastParseError(REPARSE_ERROR_BRACE_EXPECTED);
				return -1;
			}

			// in the case of an empty group, we add a nop
			nAlt = AddInstruction(RE_NOP);
			if (nAlt < 0)
				return -1;
		}

		GetInstruction(nCall).call.nTarget = nAlt;

		if (!MatchToken(ppszRE, '}'))
		{
			SetLastParseError(REPARSE_ERROR_BRACE_EXPECTED);
			return -1;
		}

		int nEnd = AddInstruction(RE_GROUP_END);
		if (nEnd < 0)
			return -1;
		GetInstruction(nEnd).group.nGroup = GetInstruction(p).group.nGroup;
		return nPushGroup;
	}

	// ParseGroup: parse grammar rule Group
	int ParseGroup(const RECHAR **ppszRE, bool &bEmpty)
	{
		int nCall = AddInstruction(RE_CALL);
		if (nCall < 0)
			return -1;

		if (AddInstruction(RE_RETURN) < 0)
			return -1;

		int nAlt = ParseRE(ppszRE, bEmpty);
		if (nAlt < 0)
		{
			if (GetLastParseError())
				return -1;

			if (!PeekToken(ppszRE, ')'))
			{
				SetLastParseError(REPARSE_ERROR_PAREN_EXPECTED);
				return -1;
			}

			// in the case of an empty group, we add a nop
			nAlt = AddInstruction(RE_NOP);
			if (nAlt < 0)
				return -1;
		}

		GetInstruction(nCall).call.nTarget = nAlt;

		if (!MatchToken(ppszRE, ')'))
		{
			SetLastParseError(REPARSE_ERROR_PAREN_EXPECTED);
			return -1;
		}

		return nCall;
	}

	RECHAR GetEscapedChar(RECHAR ch) throw()
	{
		if (ch == 't')
			return '\t';
		return ch;
	}

	// ParseCharItem: parse grammar rule CharItem
	int ParseCharItem(const RECHAR **ppszRE, RECHAR *pchStartChar, RECHAR *pchEndChar) throw()
	{
		if (**ppszRE == '\\')
		{
			*ppszRE = CharTraits::Next(*ppszRE);
			*pchStartChar = GetEscapedChar(**ppszRE);
		}
		else
			*pchStartChar = **ppszRE;
		*ppszRE = CharTraits::Next(*ppszRE);

		if (!MatchToken(ppszRE, '-'))
		{
			*pchEndChar = *pchStartChar;
			return 0;
		}

		// check for unterminated range
		if (!**ppszRE || PeekToken(ppszRE, ']'))
		{
			SetLastParseError(REPARSE_ERROR_BRACKET_EXPECTED);
			return -1;
		}

		*pchEndChar = **ppszRE;
		*ppszRE = CharTraits::Next(*ppszRE);

		if (*pchEndChar < *pchStartChar)
		{
			SetLastParseError(REPARSE_ERROR_INVALID_RANGE);
			return -1;
		}
		return 0;
	}

	int AddInstructions(int nNumInstructions)
	{
		size_t nCurr = m_Instructions.GetCount();
		if (!m_Instructions.SetCount(nCurr+nNumInstructions))
		{
			SetLastParseError(REPARSE_ERROR_OUTOFMEMORY);
			return -1;
		}
		return (int) nCurr;
	}

	// ParseCharSet: parse grammar rule CharSet
	int ParseCharSet(const RECHAR **ppszRE, BOOL bNot)
	{
		int p = -1;

		unsigned char *pBits = NULL;

		if (CharTraits::UseBitFieldForRange())
		{
			// we use a bit field to represent the characters
			// a 1 bit means match against the character
			// the last 5 bits are used as an index into 
			// the byte array, and the first 3 bits
			// are used to index into the selected byte

			p = AddInstruction(bNot ? RE_NOTRANGE : RE_RANGE);
			if (p < 0)
				return -1;

			// add the required space to hold the character
			// set.  We use one bit per character for ansi
			if (AddInstructions(InstructionsPerRangeBitField()) < 0)
				return -1;

			pBits = (unsigned char *) (&m_Instructions[p+1]);
			memset(pBits, 0x00, 256/8);
		}
		else
		{
			p = AddInstruction(bNot ? RE_NOTRANGE_EX : RE_RANGE_EX);
			if (p < 0)
				return -1;
		}

		RECHAR chStart;
		RECHAR chEnd;

		while (**ppszRE && **ppszRE != ']')
		{
			if (ParseCharItem(ppszRE, &chStart, &chEnd))
				return -1;

			if (CharTraits::UseBitFieldForRange())
			{
				for (int i=chStart; i<=chEnd; i++)
					pBits[i >> 3] |= 1 << (i & 0x7);
			}
			else
			{
				int nStart = AddInstruction(RE_NOP);
				if (nStart < 0)
					return -1;

				int nEnd = AddInstruction(RE_NOP);
				if (nEnd < 0)
					return -1;

				GetInstruction(nStart).memory.nIndex = (int) chStart;
				GetInstruction(nEnd).memory.nIndex = (int) chEnd;
			}
		}

		if (!CharTraits::UseBitFieldForRange())
			GetInstruction(p).range.nTarget = m_Instructions.GetCount();

		return p;
	}

	// ParseCharClass: parse grammar rule CharClass
	int ParseCharClass(const RECHAR **ppszRE, bool &bEmpty)
	{
		bEmpty = false;
		if (MatchToken(ppszRE, ']'))
		{
			SetLastParseError(REPARSE_ERROR_EMPTY_RANGE);
			return -1;
		}

		BOOL bNot = FALSE;
		if (MatchToken(ppszRE, '^'))
			bNot = TRUE;

		if (MatchToken(ppszRE, ']'))
		{
			SetLastParseError(REPARSE_ERROR_EMPTY_RANGE);
			return -1;
		}

		int p = ParseCharSet(ppszRE, bNot);
		if (p < 0)
			return p;
		if (!MatchToken(ppszRE, ']'))
		{
			SetLastParseError(REPARSE_ERROR_BRACKET_EXPECTED);
			return -1;
		}

		return p;
	}

	int AddMemInstruction(REInstructionType type)
	{
		int p = AddInstruction(type);
		if (p < 0)
			return p;
		GetInstruction(p).memory.nIndex = m_uRequiredMem++;
		return p;
	}

	// helper for parsing !SE
	int ParseNot(const RECHAR **ppszRE, bool &bEmpty)
	{
		int nStoreCP = AddMemInstruction(RE_STORE_CHARPOS);
		int nStoreSP = AddMemInstruction(RE_STORE_STACKPOS);

		int nCall = AddInstruction(RE_CALL);
		if (nCall < 0)
			return -1;

		int nGetCP = AddInstruction(RE_GET_CHARPOS);
		if (nGetCP < 0)
			return -1;
		GetInstruction(nGetCP).memory.nIndex = GetInstruction(nStoreCP).memory.nIndex;

		int nGetSP = AddInstruction(RE_GET_STACKPOS);
		if (nGetSP < 0)
			return -1;
		GetInstruction(nGetSP).memory.nIndex = GetInstruction(nStoreSP).memory.nIndex;

		int nJmp = AddInstruction(RE_JMP);
		if (nJmp < 0)
			return -1;

		int nSE = ParseSE(ppszRE, bEmpty);
		if (nSE < 0)
			return nSE;

		// patch the call
		GetInstruction(nCall).call.nTarget = nSE;

		int nGetCP1 = AddInstruction(RE_GET_CHARPOS);
		if (nGetCP1 < 0)
			return -1;
		GetInstruction(nGetCP1).memory.nIndex = GetInstruction(nStoreCP).memory.nIndex;

		int nGetSP1 = AddInstruction(RE_GET_STACKPOS);
		if (nGetSP1 < 0)
			return -1;
		GetInstruction(nGetSP1).memory.nIndex = GetInstruction(nStoreSP).memory.nIndex;

		int nRet = AddInstruction(RE_RETURN);
		if (nRet < 0)
			return -1;

		GetInstruction(nJmp).jmp.nTarget = nRet+1;

		return nStoreCP;
	}

	// ParseAbbrev: parse grammar rule Abbrev
	int ParseAbbrev(const RECHAR **ppszRE, bool &bEmpty)
	{
		const RECHAR **szAbbrevs = CharTraits::GetAbbrevs();

		while (*szAbbrevs)
		{
			if (**ppszRE == **szAbbrevs)
			{
				const RECHAR *szAbbrev = (*szAbbrevs)+1;
				int p = ParseE(&szAbbrev, bEmpty);
				if (p < 0)
				{
					SetLastParseError(REPARSE_ERROR_UNEXPECTED);
					return p;
				}
				*ppszRE = CharTraits::Next(*ppszRE);
				return p;
			}
			szAbbrevs++;
		}
		return -1;
	}

	// ParseSE: parse grammar rule SE (simple expression)
	int ParseSE(const RECHAR **ppszRE, bool &bEmpty)
	{

		if (MatchToken(ppszRE, '{'))
			return ParseArg(ppszRE, bEmpty);
		if (MatchToken(ppszRE, '('))
			return ParseGroup(ppszRE, bEmpty);
		if (MatchToken(ppszRE, '['))
			return ParseCharClass(ppszRE, bEmpty);

		if (MatchToken(ppszRE, '\\'))
		{
			if (!CharTraits::Isdigit(**ppszRE))
			{
				// check for abbreviations
				int p;
				p = ParseAbbrev(ppszRE, bEmpty);
				if (p >= 0)
					return p;

				if (GetLastParseError())
					return -1;

				// escaped char
				p = AddInstruction(RE_SYMBOL);
				if (p < 0)
					return -1;
				GetInstruction(p).symbol.nSymbol = (int) **ppszRE;
				*ppszRE = CharTraits::Next(*ppszRE);
				return p;
			}
			// previous match
			bEmpty = false;
			int nPrev = AddInstruction(RE_PREVIOUS);
			if (nPrev < 0)
				return -1;

			UINT uValue = (UINT) CharTraits::Strtol(*ppszRE, (RECHAR **) ppszRE, 10);
			if (uValue >= m_uNumGroups)
			{
				SetLastParseError(REPARSE_ERROR_INVALID_GROUP);
				return -1;
			}
			GetInstruction(nPrev).prev.nGroup = (size_t) uValue;
			return nPrev;
		}

		if (MatchToken(ppszRE, '!'))
			return ParseNot(ppszRE, bEmpty);

		if (**ppszRE == '}' || **ppszRE == ']' || **ppszRE == ')')
		{
			return -1;
		}

		if (**ppszRE == '\0')
		{
			return -1;
		}

		int p;
		if (**ppszRE == '.')
		{
			p = AddInstruction(RE_ANY);
			if (p < 0)
				return -1;
			bEmpty = false;
		}
		else if (**ppszRE == '$' && (*ppszRE)[1] == '\0')
		{
			p = AddInstruction(RE_SYMBOL);
			if (p < 0)
				return -1;
			GetInstruction(p).symbol.nSymbol = 0;
			bEmpty = false;
		}
		else
		{
			p = AddInstruction(RE_SYMBOL);
			if (p < 0)
				return -1;
			GetInstruction(p).symbol.nSymbol = (int) **ppszRE;
			bEmpty = false;
		}
		*ppszRE = CharTraits::Next(*ppszRE);
		return p;
	}

	// ParseE: parse grammar rule E (expression)
	int ParseE(const RECHAR **ppszRE, bool &bEmpty)
	{
		CParseState ParseState(this);
		const RECHAR *sz = *ppszRE;

		int nSE;

		int nFirst = ParseSE(ppszRE, bEmpty);
		if (nFirst < 0)
			return nFirst;

		REInstructionType type = RE_MATCH;

		if (MatchToken(ppszRE, '*'))
			if(MatchToken(ppszRE, '?'))
				type = RE_NG_STAR_BEGIN;
			else
				type = RE_STAR_BEGIN;


		else if (MatchToken(ppszRE, '+'))
			if(MatchToken(ppszRE, '?'))
				type = RE_NG_PLUS;
			else
				type = RE_PLUS;

		else if (MatchToken(ppszRE, '?'))
			if(MatchToken(ppszRE, '?'))
				type = RE_NG_QUESTION;
			else
				type = RE_QUESTION;


		if (type == RE_MATCH)
			return nFirst;

		if (type == RE_STAR_BEGIN || type == RE_QUESTION|| type == RE_NG_STAR_BEGIN || type == RE_NG_QUESTION)
		{
			ParseState.Restore(this);
		}
		else
		{
			m_uNumGroups = ParseState.m_uNumGroups;
		}
		*ppszRE = sz;

		int nE;

		if (type == RE_NG_STAR_BEGIN || type == RE_NG_PLUS || type == RE_NG_QUESTION) // Non-Greedy
		{			
			int nCall = AddInstruction(RE_CALL);
			if (nCall < 0)
				return -1;

			bEmpty = false;

			nSE = ParseSE(ppszRE, bEmpty);
			if (nSE < 0)
				return nSE;

			if (bEmpty && (type == RE_NG_STAR_BEGIN || type == RE_NG_PLUS))
			{
				SetLastParseError(REPARSE_ERROR_EMPTY_REPEATOP);
				return -1;
			}
			bEmpty = true;

			*ppszRE = CharTraits::Next(*ppszRE);
			*ppszRE = CharTraits::Next(*ppszRE);

			if (type == RE_NG_STAR_BEGIN || type == RE_NG_PLUS)
			{
				int nJmp = AddInstruction(RE_JMP);
				if (nJmp < 0)
					return -1;
				GetInstruction(nCall).call.nTarget = nJmp+1;
				GetInstruction(nJmp).jmp.nTarget = nCall;
			}
			else
				GetInstruction(nCall).call.nTarget = nSE+1;

			if (type == RE_NG_PLUS)
				nE = nFirst;
			else
				nE = nCall;
		}
		else // Greedy
		{

			int nPushMem = AddInstruction(RE_PUSH_MEMORY);
			if (nPushMem < 0)
				return -1;

			int nStore = AddInstruction(RE_STORE_CHARPOS);
			if (nStore < 0)
				return -1;

			if (AddInstruction(RE_PUSH_CHARPOS) < 0)
				return -1;

			int nCall = AddInstruction(RE_CALL);
			if (nCall < 0)
				return -1;

			if (AddInstruction(RE_POP_CHARPOS) < 0)
				return -1;

			int nPopMem = AddInstruction(RE_POP_MEMORY);
			if (nPopMem < 0)
				return -1;

			int nJmp = AddInstruction(RE_JMP);
			if (nJmp < 0)
				return -1;

			GetInstruction(nPushMem).memory.nIndex = m_uRequiredMem++;
			GetInstruction(nStore).memory.nIndex = GetInstruction(nPushMem).memory.nIndex;
			GetInstruction(nCall).call.nTarget = nJmp+1;
			GetInstruction(nPopMem).memory.nIndex = GetInstruction(nPushMem).memory.nIndex;

			bEmpty = false;

			nSE = ParseSE(ppszRE, bEmpty);
			if (nSE < 0)
				return nSE;

			if (bEmpty && (type == RE_STAR_BEGIN || type == RE_PLUS))
			{
				SetLastParseError(REPARSE_ERROR_EMPTY_REPEATOP);
				return -1;
			}

			if (type != RE_PLUS && type != RE_NG_PLUS)
				bEmpty = true;

			*ppszRE = CharTraits::Next(*ppszRE);


			int nRetNoMatch = AddInstruction(RE_RET_NOMATCH);
			if (nRetNoMatch < 0)
				return -1;

			int nStore1 = AddInstruction(RE_STORE_CHARPOS);
			if (nStore1 < 0)
				return -1;

			GetInstruction(nRetNoMatch).memory.nIndex = GetInstruction(nPushMem).memory.nIndex;
			GetInstruction(nStore1).memory.nIndex = GetInstruction(nPushMem).memory.nIndex;

			if (type != RE_QUESTION)
			{
				int nJmp1 = AddInstruction(RE_JMP);
				if (nJmp1 < 0)
					return -1;
				GetInstruction(nJmp1).jmp.nTarget = nPushMem;
			}

			GetInstruction(nJmp).jmp.nTarget = m_Instructions.GetCount();
			if (type == RE_PLUS)
				nE = nFirst;
			else
				nE = nPushMem;
		}

		return nE;
	}


	// ParseAltE: parse grammar rule AltE
	int ParseAltE(const RECHAR **ppszRE, bool &bEmpty)
	{
		const RECHAR *sz = *ppszRE;
		CParseState ParseState(this);

		int nPush = AddInstruction(RE_PUSH_CHARPOS);
		if (nPush < 0)
			return -1;

		int nCall = AddInstruction(RE_CALL);
		if (nCall < 0)
			return -1;

		GetInstruction(nCall).call.nTarget = nPush+4;
		if (AddInstruction(RE_POP_CHARPOS) < 0)
			return -1;

		int nJmpNext = AddInstruction(RE_JMP);
		if (nJmpNext < 0)
			return -1;

		int nE = ParseE(ppszRE, bEmpty);
		if (nE < 0)
		{
			if (GetLastParseError())
				return -1;
			ParseState.Restore(this);
			return nE;
		}

		int nJmpEnd = AddInstruction(RE_JMP);
		if (nJmpEnd < 0)
			return -1;

		GetInstruction(nJmpNext).jmp.nTarget = nJmpEnd+1;

		if (!MatchToken(ppszRE, '|'))
		{
			ParseState.Restore(this);
			*ppszRE = sz;

			return ParseE(ppszRE, bEmpty);
		}

		bool bEmptyAltE;
		int nAltE = ParseAltE(ppszRE, bEmptyAltE);
		GetInstruction(nJmpEnd).jmp.nTarget = m_Instructions.GetCount();
		GetInstruction(nJmpNext).jmp.nTarget = nAltE;
		if (nAltE < 0)
		{
			if (GetLastParseError())
				return -1;
			ParseState.Restore(this);
			return nAltE;
		}
		bEmpty = bEmpty | bEmptyAltE;
		return nPush;
	}

	// ParseRE: parse grammar rule RE (regular expression)
	int ParseRE(const RECHAR **ppszRE, bool &bEmpty)
	{
		if (**ppszRE == '\0')
			return -1;

		int p = ParseAltE(ppszRE, bEmpty);
		if (p < 0)
			return p;

		bool bEmptyRE = true;
		ParseRE(ppszRE, bEmptyRE);
		if (GetLastParseError())
			return -1;
		bEmpty = bEmpty && bEmptyRE;
		return p;
	}

	//pointers to the matched string and matched groups, currently point into an internal allocated 
	//buffer that hold a copy of the input string.
	//This function fix these pointers to point into the original, user supplied buffer (first param to Match method).
	//Example: If a ptr (szStart) currently point to <internal buffer>+3, it is fixed to <user supplied buffer>+3
	void FixupMatchContext(CAtlREMatchContext<CharTraits> *pContext, const RECHAR *szOrig, const RECHAR *szNew) 
	{
		ATLENSURE(pContext);
		ATLASSERT(szOrig);
		ATLASSERT(szNew);

		pContext->m_Match.szStart = szOrig + (pContext->m_Match.szStart - szNew);
		pContext->m_Match.szEnd = szOrig + (pContext->m_Match.szEnd - szNew);
		for (UINT i=0; i<pContext->m_uNumGroups; i++)
		{
			if (pContext->m_Matches[i].szStart==NULL || pContext->m_Matches[i].szEnd==NULL)
			{
				continue; //Do not fix unmatched groups.
			}
			pContext->m_Matches[i].szStart = szOrig + (pContext->m_Matches[i].szStart - szNew);
			pContext->m_Matches[i].szEnd = szOrig + (pContext->m_Matches[i].szEnd - szNew);
		}
	}
	// implementation
	// helpers for dumping and debugging the rx engine
public:
#ifdef ATL_REGEXP_DUMP
	size_t DumpInstruction(size_t ip)
	{
		printf("%08x ", ip);
		switch (GetInstruction(ip).type)
		{
		case RE_NOP:
			printf("NOP\n");
			ip++;
			break;

		case RE_SYMBOL:
			AtlprintfT<RECHAR>(CAToREChar<RECHAR>("Symbol %c\n"),GetInstruction(ip).symbol.nSymbol);			
			ip++;
			break;

		case RE_ANY:
			printf("Any\n");
			ip++;
			break;

		case RE_RANGE:
			printf("Range\n");
			ip++;
			ip += InstructionsPerRangeBitField();
			break;

		case RE_NOTRANGE:
			printf("NOT Range\n");
			ip++;
			ip += InstructionsPerRangeBitField();
			break;

		case RE_RANGE_EX:
			printf("RangeEx %08x\n", GetInstruction(ip).range.nTarget);
			ip++;
			break;

		case RE_NOTRANGE_EX:
			printf("NotRangeEx %08x\n", GetInstruction(ip).range.nTarget);
			ip++;
			break;

		case RE_GROUP_START:
			printf("Start group %d\n", GetInstruction(ip).group.nGroup);
			ip++;
			break;

		case RE_GROUP_END:
			printf("Group end %d\n", GetInstruction(ip).group.nGroup);
			ip++;
			break;

		case RE_PUSH_CHARPOS:
			printf("Push char pos\n");
			ip++;
			break;

		case RE_POP_CHARPOS:
			printf("Pop char pos\n");
			ip++;
			break;

		case RE_STORE_CHARPOS:
			printf("Store char pos %d\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_GET_CHARPOS:
			printf("Get char pos %d\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_STORE_STACKPOS:
			printf("Store stack pos %d\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_GET_STACKPOS:
			printf("Get stack pos %d\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_CALL:
			printf("Call %08x\n", GetInstruction(ip).call.nTarget);
			ip++;
			break;

		case RE_JMP:
			printf("Jump %08x\n", GetInstruction(ip).jmp.nTarget);
			ip++;
			break;

		case RE_RETURN:
			printf("return\n");
			ip++;
			break;

		case RE_PUSH_MEMORY:
			printf("Push memory %08x\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_POP_MEMORY:
			printf("Pop memory %08x\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_RET_NOMATCH:
			printf("Return no match %08x\n", GetInstruction(ip).memory.nIndex);
			ip++;
			break;

		case RE_MATCH:
			printf("END\n");
			ip++;
			break;

		case RE_ADVANCE:
			printf("ADVANCE\n");
			ip++;
			break;

		case RE_FAIL:
			printf("FAIL\n");
			ip++;
			break;

		case RE_PREVIOUS:
			printf("Prev %d\n", GetInstruction(ip).prev.nGroup);
			ip++;
			break;

		case RE_PUSH_GROUP:
			printf("Push group %d\n", GetInstruction(ip).group.nGroup);
			ip++;
			break;

		case RE_POP_GROUP:
			printf("Pop group %d\n", GetInstruction(ip).group.nGroup);
			ip++;
			break;


		default:
			printf("????\n");
			ip++;
			break;
		}
		return ip;
	}

	void Dump(size_t ipCurrent = 0)
	{
		size_t ip = 0;

		while (ip < m_Instructions.GetCount())
		{
			if (ip == ipCurrent)
				printf("->");
			ip = DumpInstruction(ip);
		}
	}
#endif

#ifdef ATLRX_DEBUG
	 void cls( HANDLE hConsole )
	{
		COORD coordScreen = { 0, 0 };    /* here's where we'll home the
											cursor */ 
		BOOL bSuccess;
		DWORD cCharsWritten;
		CONSOLE_SCREEN_BUFFER_INFO csbi; /* to get buffer info */ 
		DWORD dwConSize;                 /* number of character cells in
											the current buffer */ 

		/* get the number of character cells in the current buffer */ 

		bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );
		dwConSize = csbi.dwSize.X * csbi.dwSize.Y;

		/* fill the entire screen with blanks */ 

		bSuccess = FillConsoleOutputCharacter( hConsole, (TCHAR) ' ',
		   dwConSize, coordScreen, &cCharsWritten );

		/* get the current text attribute */ 

		bSuccess = GetConsoleScreenBufferInfo( hConsole, &csbi );

		/* now set the buffer's attributes accordingly */ 

		bSuccess = FillConsoleOutputAttribute( hConsole, csbi.wAttributes,
		   dwConSize, coordScreen, &cCharsWritten );

		/* put the cursor at (0, 0) */ 

		bSuccess = SetConsoleCursorPosition( hConsole, coordScreen );
		return;
	} 

	void DumpStack(CAtlREMatchContext<CharTraits> *pContext)
	{
		for (size_t i=pContext->m_nTos; i>0; i--)
		{
			if (pContext->m_stack[i] < (void *) m_Instructions.GetCount())
				printf("0x%p\n", pContext->m_stack[i]);
			else
			{
				// assume a pointer into the input
				AtlprintfT<RECHAR>(CAToREChar<RECHAR>("%s\n"), pContext->m_stack[i]);
			}
		}
	}

	void DumpMemory(CAtlREMatchContext<CharTraits> *pContext)
	{
		for (UINT i=0; i<m_uRequiredMem; i++)
		{
			AtlprintfT<RECHAR>(CAToREChar<RECHAR>("%d: %s\n"), i, pContext->m_Mem.m_p[i]);
		}
	}

	virtual void OnDebugEvent(size_t ip, const RECHAR *szIn, const RECHAR *sz, CAtlREMatchContext<CharTraits> *pContext)
	{
		cls(GetStdHandle(STD_OUTPUT_HANDLE));
		printf("----------Code---------\n");
		Dump(ip);
		printf("----------Input---------\n");		
		AtlprintfT<RECHAR>(CAToREChar<RECHAR>("%s\n"), szIn);
		for (int s=0; szIn+s < sz; s++)
		{
			printf(" ");
		}		
		printf("^\n");
		printf("----------Memory---------\n");
		DumpMemory(pContext);
		printf("----------Stack---------\n");		
		DumpStack(pContext);
		getchar();
	}
#endif

};

} // namespace ATL
#pragma pack(pop)

#endif // __ATLRX_H__