SF Area/Download Docs: User Internal/Devel		csregex.cpp Go to the documentation of this file. //--------------------------------------------------------------------------- // // Author: Cleo Saulnier // Date: July 14, 2005 // // Regular expression engine. // // See LICENSE file for legal information. // Basically public domain, but author keeps moral rights. // Original author's name above must remain in source. // Simply put, you can do what you want, but don't misrepresent // the origins, and contents, of this code. // // http://sourceforge.net/projects/csregex/ // //--------------------------------------------------------------------------- // We don't use many string functions so // we don't risk that they don't have a // unicode capable compiler. Simply // define the few functions we do use. #include <ctype.h> #include <string.h> #ifdef __BCPLUSPLUS__ #pragma hdrstop #endif #include "csregex.h" //--------------------------------------------------------------------------- #ifdef __BCPLUSPLUS__ #pragma package(smart_init) #endif #ifndef _UNICODE #ifndef __TCHAR_DEFINED #define _tcslen strlen #define _tcscpy strcpy #define _totlower tolower #define _istdigit isdigit #define _T(a) a #endif #endif // This is used when advancing index over offsets. // In ASCII, you advance by 2 chars. // In UNICODE, you advance by 1 wchar_t. #ifdef _UNICODE #define CSREGEX_OFSWIDTH 1 #else #define CSREGEX_OFSWIDTH 2 #endif static _TCHAR* CSRegExErrorStr[] = {_T("OK."), _T("Back references (round brackets) exceed maximum of 9."), _T("Missing end round bracket."), _T("Overlapping/redundant character specs."), _T("Escape character cannot appear at end of string by itself."), _T("Missing end square bracket."), _T("Invalid hex characters in escape sequence."), _T("Invalid repeat format."), _T("Invalid repeat range."), _T("Unbalanced round brackets."), _T("Invalid range."), _T("Invalid backreference."), _T("Regular expression is too long.")}; CSRegEx::CSRegEx() { str = NULL; buf = NULL; str_len = 0; buf_len = 0; buf_size = 0; bMatchHead = false; error = -1; error_code = rge_ok; error_str = CSRegExErrorStr[0]; } CSRegEx::~CSRegEx() { if (buf) delete[] buf; } _TUCHAR* CSRegEx::GetCompiledString() const { _TUCHAR *b = new _TUCHAR[_tcslen(reinterpret_cast<_TCHAR* const>(buf))+1]; _tcscpy(reinterpret_cast<_TCHAR*>(b),reinterpret_cast<_TCHAR*>(buf)); return b; } void CSRegEx::SetCompiledString(_TUCHAR *str) { int len = _tcslen(reinterpret_cast<_TCHAR*>(str))+1; if (len>buf_size) { if (buf_size==0) buf_size = 1024; else delete[] buf; while(len>buf_size) buf_size*=2; buf = new _TUCHAR[buf_size]; } _tcscpy(reinterpret_cast<_TCHAR*>(buf),reinterpret_cast<_TCHAR*>(str)); } void CSRegEx::Put(_TCHAR c) { if (buf_len+1==buf_size) { _TUCHAR *buf1 = new _TUCHAR[buf_size*2]; memcpy(buf1,buf,buf_size*sizeof(_TUCHAR)); delete[] buf; buf = buf1; buf_size*=2; } buf[buf_len++]=c; } // If we have unicode, then a wchar_t is large // enough to hold the offset. // Otherwise, we need to use 2 chars. #ifdef _UNICODE #define PutValue16 Put #define GetValue16(i) \ static_cast<unsigned int>(buf[i]) #else void CSRegEx::PutValue16(unsigned short c) { if (buf_len+2>=buf_size) { unsigned char *buf1 = new unsigned char[buf_size*2]; memcpy(buf1,buf,buf_size); delete[] buf; buf = buf1; buf_size*=2; } // We add 0x0100 because we can't have any 0 values // in the high order. *(reinterpret_cast<unsigned short*>(&buf[buf_len])) = c+0x0100; buf_len+=2; } #define GetValue16(i) \ static_cast<unsigned int>((*(reinterpret_cast<unsigned short*>(&buf[i])))-0x0100) #endif #ifndef _UNICODE bool CSRegEx::Compile(const char *str) { return Compile((const unsigned char*)str); } #endif // Places an offset (v) in a previous location (a) in the // compiled string buffer. #ifndef _UNICODE #define PUT_OFFSET(a, v) \ *(reinterpret_cast<unsigned short*>(&buf[(a)])) = (v)+0x0100 #else #define PUT_OFFSET(a, v) \ buf[(a)] = (v) #endif bool CSRegEx::Compile(const _TUCHAR *str) { error_code = rge_ok; if (buf==NULL) { buf_size = 1024; buf = new _TUCHAR[buf_size]; } buf_len = 0; tal = false; if (str[0]==_T('^')) { Put(rg_hed); str++; } str_len = _tcslen(reinterpret_cast<const _TCHAR*>(str)); this->str = str; opa_cnt=0; error = -1; Put(rg_opa); last_par.push_back(buf_len); PutValue16(0); // temporary forward offset. int pos = Compile(0); if ((last_par.size()!=1)||(pos!=str_len)) { error = pos; error_code = rge_unbalanced_round_bracket; error_str = CSRegExErrorStr[error_code]; last_par.clear(); return false; } if (error!=-1) { error_str = CSRegExErrorStr[error_code]; last_par.clear(); return false; } int parpos = last_par.back(); int offset = buf_len-parpos; PUT_OFFSET(parpos, offset); last_par.pop_back(); Put(rg_cpa); if (tal) Put(rg_tal); Put(rg_end); error_str = CSRegExErrorStr[0]; last_par.clear(); return true; } void CSRegEx::CheckString(int str_idx) { if (GetValue16(str_idx)==1) { buf[str_idx-1] = rg_chr; buf_len = str_idx; Put(buf[str_idx+CSREGEX_OFSWIDTH]); } } int CSRegEx::Compile(int pos) { // This is used to tell if a string has been started. // So further chars can just be appended if true, // or a new string is created if false. bool str_started = false; int str_idx = 0; // Regular expression current char position. int st_pos; while(pos<str_len) { _TUCHAR c = str[pos]; pos++; if (buf_len>=65279) // 0xffff - 0x0100 { error = pos-1; error_code = rge_regex_too_long; return pos-1; } bool esc = false; switch(c) { case _T('.'): if (str_started) { CheckString(str_idx); // Compress string if need be. str_started = false; } st_pos = buf_len; // Save location of this item. Put(rg_dot); pos=CompileModifiers(pos, st_pos); if (error!=-1) return pos; break; case _T('('): { if (str_started) { CheckString(str_idx); str_started = false; } st_pos = buf_len; // match a new expression. int old_pos; int type = 0; old_pos = pos-1; int opa_ofs; if ((pos+1<str_len)&&(str[pos]==_T('?'))&&(str[pos+1]==_T(':'))) { Put(rg_opn); last_par.push_back(buf_len); PutValue16(0); // placeholder for next section. pos+=2; } else { opa_cnt++; opa_ofs = opa_cnt; if (opa_cnt==10) { error = pos; error_code = rge_too_many_refs; return old_pos; } Put(rg_opa+opa_cnt); last_par.push_back(buf_len); PutValue16(0); // placeholder for next section. type = 1; } pos = Compile(pos); // Recursive. if (error!=-1) return pos; if ((pos>=str_len)||(str[pos]!=_T(')'))) { // unbalanced parentheses. error = old_pos; error = rge_missing_round_bracket; return old_pos; } pos++; int parpos = last_par.back(); int offset = buf_len-parpos; PUT_OFFSET(parpos, offset); last_par.pop_back(); Put(type?rg_cpa+opa_ofs:rg_cpn); pos=CompileModifiers(pos, st_pos); if (error!=-1) return pos; break; } case _T('['): if (str_started) { CheckString(str_idx); str_started = false; } st_pos = buf_len; pos = CompileRange(pos); if (error!=-1) return pos; pos = CompileModifiers(pos,st_pos); if (error!=-1) return pos; break; case _T('|'): { if (str_started) { CheckString(str_idx); str_started = false; } int parpos = last_par.back(); int offset = buf_len-parpos; PUT_OFFSET(parpos, offset); Put(rg_orm); last_par.back()=buf_len; // Update last offset. PutValue16(0); break; } case _T(')'): if (str_started) { CheckString(str_idx); str_started = false; } return pos-1; case _T('\\'): // This section falls through to the default section. // Unless it's a backreference. if ((str[pos]>=_T('1'))&&(str[pos]<=_T('9'))) { if (str_started) { CheckString(str_idx); str_started = false; } st_pos = buf_len; Put(rg_bck+(str[pos++]-_T('0'))); pos = CompileModifiers(pos,st_pos); if (error!=-1) return pos; break; } else if (str[pos]==_T('0')) { error = pos-1; error_code = rge_invalid_backreference; return pos-1; } pos = Escape(pos, c); if (error!=-1) return pos; esc = true; default: { if ((!esc)&&(c==_T('$'))&&(pos==str_len)) { tal=true; break; } // Must check if next char is a modifier. // If it is, we output a CHR instead of continuing a STR. _TUCHAR cc; if ((pos<str_len)&&(((cc=str[pos])==_T('?'))||(cc==_T('*'))||(cc==_T('+')))) { if (str_started) { CheckString(str_idx); str_started = false; } st_pos = buf_len; Put(rg_chr); Put(c); pos = CompileModifiers(pos,st_pos); if (error!=-1) return pos; break; } if (str_started) { unsigned int cnt = GetValue16(str_idx); // Overflow can't happen here, so we don't check here. // It's checked at the top of the loop. Put(c); cnt++; PUT_OFFSET(str_idx, cnt); } else { Put(rg_str); str_idx = buf_len; PutValue16(1); Put(c); str_started = true; } } } } if (str_started) { CheckString(str_idx); str_started = false; } return pos; } int CSRegEx::Escape(int pos, _TUCHAR &c) { _TUCHAR c1 = str[pos]; switch(c1) { case _T('n'): c = (_TUCHAR)10; break; case _T('r'): c = (_TUCHAR)13; break; case _T('t'): c = (_TUCHAR)9; break; case _T('a'): c = (_TUCHAR)7; break; case _T('b'): c = (_TUCHAR)8; break; case _T('f'): c = (_TUCHAR)12; break; case _T('v'): c = (_TUCHAR)11; break; case _T('x'): case _T('X'): // exactly 2 or 4 (UNICODE) digits. #ifdef _UNICODE #define ESC_CHARS 4 #else #define ESC_CHARS 2 #endif if (pos+ESC_CHARS>=str_len) { error = pos-1; error_code = rge_esc_eof; return pos; } c = 0; unsigned char h[ESC_CHARS]; h[0] = _totlower(str[pos+1]); h[1] = _totlower(str[pos+2]); #ifdef _UNICODE h[2] = _totlower(str[pos+2]); h[3] = _totlower(str[pos+3]); #endif for(int k=0;k<ESC_CHARS;k++) { c<<=4; if (_istdigit(h[k])) { c += h[k]-_T('0'); } else if ((h[k]>='a')&&(h[k]<='f')) { c += h[k]-_T('a')+(_TUCHAR)10; } else { error = pos+k+1; error_code = rge_invalid_esc_hex; return pos; } } pos+=ESC_CHARS; break; default: c=c1; } pos++; return pos; } int CSRegEx::CompileModifiers(int pos, int st_pos) { if (pos>=str_len) return pos; int old_pos = pos; int buf_idx = buf_len; _TUCHAR c = str[pos]; switch(c) { case _T('?'): Put(rg_qes); PutValue16(buf_len-st_pos); pos++; break; case _T('*'): Put(rg_sta); PutValue16(buf_len-st_pos); pos++; break; case _T('+'): Put(rg_pls); PutValue16(buf_len-st_pos); pos++; break; case _T('{'): // Get the range. // Possibilities: // {start,end} // start-end // {start,} // start-inf // {start} // exactly start times. int start=0; int end = 0; bool inf = false; pos++; if (!_istdigit(str[pos])) { error = pos; error_code = rge_invalid_repeat_format; return pos; } do {start=start*10+static_cast<int>(str[pos++]-_T('0'));} while(_istdigit(str[pos])); if (str[pos]==_T('}')) { // exact {start} end = start; pos++; } else { if (str[pos]!=_T(',')) { error = pos; error_code = rge_invalid_repeat_format; return pos; } pos++; if (str[pos]==_T('}')) { // {start,} inf = true; end = 0; pos++; } else { if (!_istdigit(str[pos])) { error = pos; error_code = rge_invalid_repeat_format; return pos; } do {end=end*10+static_cast<int>(str[pos++]-_T('0'));} while(_istdigit(str[pos])); if (str[pos]!=_T('}')) { error = pos; error_code = rge_invalid_repeat_format; return pos; } // {start,end} pos++; } } if ((start==0)&&(end==1)) { // same as ? Put(rg_qes); PutValue16(buf_len-st_pos); } else if ((start==0)&&(inf)) { // same as * Put(rg_sta); PutValue16(buf_len-st_pos); } else if ((start==1)&&(inf)) { // same as + Put(rg_pls); PutValue16(buf_len-st_pos); } else if (((start==0)&&(end==0))||(start>end)||(start>65277)||(end>65277)||((!inf)&&(end==0))) { // Invalid ranges. error = old_pos; error_code = rge_invalid_repeat_range; return pos; } else { Put(rg_rpt); PutValue16(buf_len-st_pos); PutValue16(start+1); PutValue16((inf)?65279:end+1); } } // If the above doesn't match, neither will this, so it's ok. if (str[pos]==_T('?')) { // lazy. RGTok t = static_cast<RGTok>(buf[buf_idx]); RGTok tt = static_cast<RGTok>(0); if (t==rg_qes) tt=rg_qes_lazy; else if (t==rg_sta) tt=rg_sta_lazy; else if (t==rg_pls) tt=rg_pls_lazy; else if (t==rg_rpt) tt=rg_rpt_lazy; if (tt) { buf[buf_idx] = tt; pos++; } } return pos; } bool CSRegEx::RangeAddChar(vector<_TUCHAR> &chars, vector<_TUCHAR> &start, vector<_TUCHAR> &end, _TUCHAR c) { #ifdef _UNICODE unsigned int xc = static_cast<unsigned int>(c); #else #define xc c #define xi *i #define xj *j #endif // could use map to speed up searches, but there's never // enough chars to really make a difference. for(vector<_TUCHAR>::iterator i=chars.begin();i!=chars.end();i++) { #ifdef _UNICODE unsigned int xi = static_cast<unsigned int>(*i); #endif if (xc==xi) { error_code = rge_overlapping_chars; return false; } } bool added = false; vector<_TUCHAR>::iterator i = start.begin(); vector<_TUCHAR>::iterator j = end.begin(); for(;i!=start.end();i++,j++) { #ifdef _UNICODE unsigned int xi = static_cast<unsigned int>(*i); unsigned int xj = static_cast<unsigned int>(*j); #endif if ((xc>=xi)&&(xc<=xj)) { error_code = rge_overlapping_chars; return false; } if ((!added)&&(xc==xi-1)) { *i = c; added = true; } else if ((!added)&&(xc==xj+1)) { *j = c; added = true; } } if (!added) chars.push_back(c); return true; #ifndef _UNICODE #undef xc #undef xi #undef xj #endif } bool CSRegEx::RangeAddRange(vector<_TUCHAR> &chars, vector<_TUCHAR> &start, vector<_TUCHAR> &end, _TUCHAR cstart, _TUCHAR cend) { #ifdef _UNICODE unsigned int xcstart = static_cast<unsigned int>(cstart); unsigned int xcend = static_cast<unsigned int>(cend); #else #define xcstart cstart #define xcend cend #define xi *i #define xj *j #endif for(vector<_TUCHAR>::iterator i=chars.begin();i!=chars.end();i++) { #ifdef _UNICODE unsigned int xi = static_cast<unsigned int>(*i); #endif if ((xi>=xcstart)&&(xi<=xcend)) { error_code = rge_overlapping_chars; return false; } } bool added = false; vector<_TUCHAR>::iterator i = start.begin(); vector<_TUCHAR>::iterator j = end.begin(); for(;i!=start.end();i++,j++) { #ifdef _UNICODE unsigned int xi = static_cast<unsigned int>(*i); unsigned int xj = static_cast<unsigned int>(*j); #endif if (((xcstart>=xi)&&(xcstart<=xj))||((xcend>=xi)&&(xcend<=xj))) { error_code = rge_overlapping_chars; return false; } if ((!added)&&(xcend==xi-1)) { *i = cstart; added = true; } else if ((!added)&&(xcstart==xj+1)) { *j = cend; added = true; } } if (!added) { start.push_back(cstart); end.push_back(cend); } return true; #ifndef _UNICODE #undef xcstart #undef xcend #undef xi #undef xj #endif } void CSRegEx::CompressRange(vector<_TUCHAR> &chars, vector<_TUCHAR> &start, vector<_TUCHAR> &end) { #ifndef _UNICODE #define xc c #define xc1 c1 #define xst st #define xen en #define xs1 s1 #define xe1 e1 #define xs2 s2 #define xe2 e2 #endif // create ranges with chars if possible. for(unsigned int i=0;i<chars.size();i++) { _TUCHAR c = chars[i]; #ifdef _UNICODE unsigned int xc = static_cast<unsigned int>(c); #endif for (unsigned int j=i+1;j<chars.size();j++) { _TUCHAR c1 = chars[j]; #ifdef _UNICODE unsigned int xc1 = static_cast<unsigned int>(c1); #endif if (xc+1==xc1) { start.push_back(c); end.push_back(c1); // j is always larger, so we have to erase that one first. chars.erase(chars.begin()+j); chars.erase(chars.begin()+i); i--; break; } else if (xc1+1==xc) { start.push_back(c1); end.push_back(c); chars.erase(chars.begin()+j); chars.erase(chars.begin()+i); i--; break; } } } // merge chars into ranges. for(unsigned int i=0;i<chars.size();i++) { _TUCHAR c = chars[i]; #ifdef _UNICODE unsigned int xc = static_cast<unsigned int>(c); #endif for(unsigned int j=0;j<start.size();j++) { _TUCHAR st = start[j]; _TUCHAR en = end[j]; #ifdef _UNICODE unsigned int xst = static_cast<unsigned int>(st); unsigned int xen = static_cast<unsigned int>(en); #endif if (xc==xst-1) { start[j] = c; chars.erase(chars.begin()+i); i--; } else if (xc==xen+1) { end[j] = c; chars.erase(chars.begin()+i); i--; } } } // Merge ranges. for(unsigned int i=0;i<start.size();i++) { _TUCHAR s1 = start[i]; _TUCHAR e1 = end[i]; #ifdef _UNICODE unsigned int xs1 = static_cast<unsigned int>(s1); unsigned int xe1 = static_cast<unsigned int>(e1); #endif bool found = false; for(unsigned int j=i+1;j<end.size();j++) { _TUCHAR s2 = start[j]; _TUCHAR e2 = end[j]; #ifdef _UNICODE unsigned int xs2 = static_cast<unsigned int>(s2); unsigned int xe2 = static_cast<unsigned int>(e2); #endif if (xe2+1==xs1) // goes before { start[i] = s2; start.erase(start.begin()+j); end.erase(end.begin()+j); j--; found = true; } else if (xs2-1==xe1) // goes after { end[i] = e2; start.erase(start.begin()+j); end.erase(end.begin()+j); j--; found = true; } } if (found) i--; // Gotta scan this range again. } #ifndef _UNICODE #undef xc #undef xc1 #undef xst #undef xen #undef xs1 #undef xe1 #undef xs2 #undef xe2 #endif } int CSRegEx::CompileRange(int pos) { vector<_TUCHAR> chars; vector<_TUCHAR> start; vector<_TUCHAR> end; // first char int old_pos = pos-1; int err_pos = pos; if (pos>=str_len) { error = old_pos; error_code = rge_missing_square_bracket; return old_pos; } _TUCHAR c = str[pos]; bool neg = false; if (c==_T('^')) { neg = true; pos++; if (pos>=str_len) { error = pos-1; error_code = rge_missing_square_bracket; return old_pos; } err_pos = pos; c = str[pos]; } pos++; if (c==_T('\\')) { pos = Escape(pos, c); if (error!=-1) return pos; } if (pos>=str_len) { error = old_pos; error_code = rge_missing_square_bracket; return old_pos; } for(;;) { bool range=false; if (pos+1<str_len) { int pos1 = pos; // check for range. _TUCHAR c1 = str[pos1++]; _TUCHAR c2=static_cast<_TUCHAR>(0); if ((c1==_T('-'))&&(pos1<str_len)) { c2 = str[pos1++]; if (c2==_T('\\')) { pos1 = Escape(pos1, c2); if (error!=-1) return pos1; } if (c2!=_T(']')) { #ifdef _UNICODE if (static_cast<unsigned int>(c)>=static_cast<unsigned int>(c2)) #else if (c>=c2) #endif { error = err_pos; error_code = rge_invalid_range; return pos1; } pos = pos1; bool b = RangeAddRange(chars,start,end,c,c2); if (!b) { error = err_pos; return pos; } range = true; } } } if (!range) { bool b = RangeAddChar(chars, start, end, c); if (!b) { error = err_pos; return pos; } } // Get next char. if (pos>=str_len) { error = old_pos; error_code = rge_missing_square_bracket; return pos; } err_pos = pos; c = str[pos++]; if (c==_T(']')) break; if (c==_T('\\')) { pos = Escape(pos, c); if (error!=-1) return pos; } } CompressRange(chars,start,end); // Output the data. Put(neg?rg_grn:rg_grp); PutValue16(chars.size()+1); // We can't have 0 as a char, so add 1 PutValue16(start.size()+1); for(unsigned int i=0;i<chars.size();i++) { Put(chars[i]); } for(unsigned int i=0;i<start.size();i++) { Put(start[i]); Put(end[i]); } return pos; } unsigned int CSRegEx::GetRpt(unsigned int buf_idx, int &low, int &high, bool &lazy, unsigned int &prev) const { RGTok t = static_cast<RGTok>(buf[buf_idx]); lazy = false; switch(t) { case rg_qes_lazy: lazy = true; case rg_qes: low = 0; high = 1; prev = buf_idx+1-GetValue16(buf_idx+1); return buf_idx+1+CSREGEX_OFSWIDTH; case rg_sta_lazy: lazy = true; case rg_sta: low = 0; high = 0x7fffffff; prev = buf_idx+1-GetValue16(buf_idx+1); return buf_idx+1+CSREGEX_OFSWIDTH; case rg_pls_lazy: lazy = true; case rg_pls: low = 1; high = 0x7fffffff; prev = buf_idx+1-GetValue16(buf_idx+1); return buf_idx+1+CSREGEX_OFSWIDTH; case rg_rpt_lazy: lazy = true; case rg_rpt: low = GetValue16(buf_idx+1+CSREGEX_OFSWIDTH)-1; high = GetValue16(buf_idx+1+2*CSREGEX_OFSWIDTH)-1; if (high==65534) high = 0x7fffffff; prev = buf_idx+1-GetValue16(buf_idx+1); return buf_idx+1+3*CSREGEX_OFSWIDTH; default: low=1; high=1; lazy=false; return buf_idx; } } bool CSRegEx::MatchRE(const _TUCHAR *str, const _TUCHAR *re) { if (!Compile(re)) return false; return Match(str); } #ifndef _UNICODE bool CSRegEx::MatchRE(const char *str, const char *re) { return MatchRE((const unsigned char*)str,(const unsigned char*)re); } bool CSRegEx::MatchRE(const unsigned char *str, const char *re) { return MatchRE(str,(const unsigned char*)re); } bool CSRegEx::MatchRE(const char *str, const unsigned char *re) { return MatchRE((const unsigned char*)str,re); } bool CSRegEx::Match(const unsigned char *str, const char *cmp) { return Match(str,(const unsigned char*)cmp); } bool CSRegEx::Match(const char *str, const unsigned char *cmp) { return Match((const unsigned char*)str,cmp); } bool CSRegEx::Match(const char *str, const char *cmp) { return Match((const unsigned char*)str,(const unsigned char*)cmp); } #endif bool CSRegEx::Match(const _TUCHAR *str, const _TUCHAR *cmp) { _TUCHAR *buf1 = buf; // We're removing the const here, but we don't actually // modify the string. It's just so we don't have to // allocate another non-const variable. // The compile function does modify the 'buf' member, // but we don't call it and we remove 'cmp' before // we return, so no problem. buf = const_cast<_TUCHAR*>(cmp); bool b = Match(str); buf = buf1; return b; } #ifndef _UNICODE bool CSRegEx::Match(const char *str) { return Match((const unsigned char*)str); } #endif bool CSRegEx::Match(const _TUCHAR *str) { int max=1; if ((buf[0]!=rg_hed)&&(!bMatchHead)) max = _tcslen(reinterpret_cast<const _TCHAR*>(str)); // TODO: Make a list of FIRST chars and scan for that instead. for(int i=0;i<max;i++) { if (Match1(str+i)) { MatchStart += i; MatchEnd += i; // Cleanup for(int j=0;j<10;j++) { if (match_start[j].size()!=0) { BackStart[j] = match_start[j].back()+i; BackEnd[j] = match_end[j].back()+i; } else { BackStart[j] = 0; BackEnd[j] = 0; } match_start[j].clear(); match_end[j].clear(); } par.clear(); return true; } } // Cleanup for(int i=0;i<10;i++) { match_start[i].clear(); match_end[i].clear(); } par.clear(); return false; } // This checks the results of basic matching. #define CHECK_MATCH() \ if (cnt>=low) /* We got the minimum required.*/ \ { \ /* success. */ \ /* if this is lazy, then we have to keep a ref */ \ /* to the empty match.*/ \ if ((lazy)&&(cnt==0)) \ { \ m->rpt = -1; \ idx++; \ if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} \ m1 = &matches[idx]; \ m1->start = m->end; \ m = m1; \ } \ m->buf_idx = next; \ m->rpt = 0; \ } \ else \ { \ /* failure. */ \ if (cnt==-1) cnt = min; \ idx-=(cnt+1); \ state=1; /* backtrack error. */ \ } bool CSRegEx::Match1(const _TUCHAR *str) { unsigned int par_index=-1; int idx=0; int matches_size = 1024; bool backtrack=false; // Used for lazy backtracking. // Setup this->str = str; matches.resize(matches_size); matches[0].buf_idx=0; matches[0].start = 0; matches[0].rpt = 0; if (buf[0]==rg_hed) matches[0].buf_idx++; int state = 0; // 0=forward, 1=backtrack. CSMatch *m1; while(idx!=-1) { CSMatch *m = &matches[idx]; RGTok t = static_cast<RGTok>(buf[m->buf_idx]); RGTok tt; unsigned int rpt_idx; int low, high; // must be signed. repeat ranges. bool lazy; unsigned int next, prev; // Next and previous item positions. if (state==0) { m->end = m->start; switch(t) { case rg_tal: // If we find end of line, don't advance m->end counter. if (str[m->start]!=_T('\0')) { state = 1; idx--; break; } idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx+1; m1->start = m->end; m1->rpt = 0; break; case rg_chr: { // Get the repeat char, if any. rpt_idx = m->buf_idx+2; next = GetRpt(rpt_idx,low,high,lazy, prev); int cnt=(backtrack)?-1:0; unsigned int min=(backtrack)?m->rpt:0; unsigned int max=(lazy)?((backtrack)?m->rpt+1:low):high; for(unsigned int i=min;i<max;i++) { // Match 1 character. if (str[m->start]!=buf[m->buf_idx+1]) break; cnt=i+1; m->end++; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx; m1->start = m->end; m1->end = m1->start; m1->rpt = m->rpt+1; m = m1; } CHECK_MATCH(); break; } case rg_str: { // rg_str can't be repeated, so this is simple. unsigned int cnt = GetValue16(m->buf_idx+1); for(unsigned int i=0;i<cnt;i++) { if (str[m->end++]!=buf[m->buf_idx+1+CSREGEX_OFSWIDTH+i]) { state = 1; // backtrack error. idx--; break; } } if (state==1) break; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx+1+CSREGEX_OFSWIDTH+cnt; m1->start = m->end; m1->rpt = 0; break; } case rg_dot: { rpt_idx = m->buf_idx+1; next = GetRpt(rpt_idx,low,high,lazy,prev); int cnt=(backtrack)?-1:0; unsigned int min=(backtrack)?m->rpt:0; unsigned int max=(lazy)?((backtrack)?m->rpt+1:low):high; for(unsigned int i=min;i<max;i++) { if (str[m->start]==_T('\0')) break; cnt=i+1; m->end++; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx; m1->start = m->end; m1->end = m1->start; m1->rpt = m->rpt+1; m = m1; } CHECK_MATCH(); break; } case rg_bck: case rg_bck1: case rg_bck2: case rg_bck3: case rg_bck4: case rg_bck5: case rg_bck6: case rg_bck7: case rg_bck8: case rg_bck9: { // match backreference. rpt_idx = m->buf_idx+1; next = GetRpt(rpt_idx,low,high,lazy,prev); int cnt=(backtrack)?-1:0; unsigned int min=(backtrack)?m->rpt:0; unsigned int max=(lazy)?((backtrack)?m->rpt+1:low):high; unsigned int back_idx = t-rg_bck; unsigned int start = match_start[back_idx].back(); unsigned int end = match_end[back_idx].back(); if (start==end) max = low; // For empty backreferences. Has to match minimum, so we'll have redundant entries. for(unsigned int i=min;i<max;i++) { bool bok = true; for(unsigned int j=start;j<end;j++) { if (str[j]!=str[m->end++]) { bok = false; break; } } if (!bok) break; cnt=i+1; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx; m1->start = m->end; m1->end = m1->start; m1->rpt = m->rpt+1; m = m1; } CHECK_MATCH(); break; } case rg_grp: case rg_grn: { // Check group of chars and ranges. unsigned int char_cnt = GetValue16(m->buf_idx+1)-1; unsigned int rng_cnt = GetValue16(m->buf_idx+1+CSREGEX_OFSWIDTH)-1; _TUCHAR c = str[m->start]; rpt_idx = m->buf_idx+1+2*CSREGEX_OFSWIDTH+char_cnt+2*rng_cnt; next = GetRpt(rpt_idx,low,high,lazy,prev); int cnt=(backtrack)?-1:0; unsigned int min=(backtrack)?m->rpt:0; unsigned int max=(lazy)?((backtrack)?m->rpt+1:low):high; if (c!=_T('\0')) { for(unsigned int i=min;i<max;i++) { c = str[m->start]; if (c==_T('\0')) break; bool found = false; unsigned int pos = m->buf_idx+1+2*CSREGEX_OFSWIDTH; for(unsigned int j=0;j<char_cnt;j++) { if (c==buf[pos++]) { found = true; break; } } if (!found) { #ifdef _UNICODE unsigned int xc = static_cast<unsigned int>(c); #else #define xc c #define xlow1 low1 #define xhigh1 high1 #endif for(unsigned int j=0;j<rng_cnt;j++) { _TUCHAR low1 = buf[pos++]; _TUCHAR high1 = buf[pos++]; #ifdef _UNICODE unsigned int xlow1 = static_cast<unsigned int>(low1); unsigned int xhigh1 = static_cast<unsigned int>(high1); #endif if ((xc>=xlow1)&&(xc<=xhigh1)) { found = true; break; } } } #ifndef _UNICODE #undef xc #undef xlow1 #undef xhigh1 #endif // bool b = (t==rg_grn); if (found==b) break; cnt=i+1; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx; m->end++; m1->start = m->end; m1->end = m1->start; m1->rpt = m->rpt+1; m = m1; } } CHECK_MATCH(); break; } case rg_opa: case rg_opa1: case rg_opa2: case rg_opa3: case rg_opa4: case rg_opa5: case rg_opa6: case rg_opa7: case rg_opa8: case rg_opa9: case rg_opn: { par_index++; // Get ourselves a new par index. if (par_index+1>par.size()) par.resize(par_index+1); par[par_index].match_idx = idx; par[par_index].buf_idx = m->buf_idx; // start and end will be updated later. // so just setup the next items. idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx+1+CSREGEX_OFSWIDTH; m1->start = m->end; m1->rpt = 0; // Gotta check for greediness. // If this is the first item and it's lazy, then skip to the end. if (m->rpt==0) { unsigned int pos = m->buf_idx+1+GetValue16(m->buf_idx+1); tt = static_cast<RGTok>(buf[pos]); while(tt==rg_orm) { pos += GetValue16(pos+1)+1; tt = static_cast<RGTok>(buf[pos]); } pos++; int n = GetRpt(pos,low,high,lazy,prev); if ((lazy)&&(low==0)) { // empty entry is ok. m->end = m->start; m->rpt = -1; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = n; m1->start = m->buf_idx; m1->end = par[par_index].match_idx; tt = (RGTok)buf[m->buf_idx]; if ((tt>=rg_opa)&&(tt<=rg_opa9)) { unsigned int k = tt-rg_opa; match_start[k].push_back(m->start); match_end[k].push_back(m->end); } par_index--; m1->rpt = -1; idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-2];} CSMatch *m2 = &matches[idx]; m2->buf_idx = n; m2->start = m->start; m2->rpt = 0; } } break; } case rg_cpa: case rg_cpa1: case rg_cpa2: case rg_cpa3: case rg_cpa4: case rg_cpa5: case rg_cpa6: case rg_cpa7: case rg_cpa8: case rg_cpa9: case rg_cpn: { int k = par[par_index].match_idx; matches[k].end = m->start; m->rpt = matches[k].rpt; m->start = par[par_index].buf_idx; m->end = k; if (t!=rg_cpn) { int k1 = t-rg_cpa; match_start[k1].push_back(matches[k].start); match_end[k1].push_back(matches[k].end); } idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx+1; m1->start = matches[k].end; m1->rpt = 0; par_index--; break; } case rg_orm: // success on matching par, skip ahead. { unsigned int ofs = GetValue16(m->buf_idx+1); unsigned int pos = m->buf_idx+1+ofs; tt = static_cast<RGTok>(buf[pos]); while(tt==rg_orm) { ofs = GetValue16(pos+1); pos += ofs+1; tt = static_cast<RGTok>(buf[pos]); } m->buf_idx=pos; break; } case rg_pls: case rg_sta: case rg_qes: case rg_rpt: case rg_pls_lazy: case rg_sta_lazy: case rg_qes_lazy: case rg_rpt_lazy: { // This will only get here for round brackets. next = GetRpt(m->buf_idx,low,high,lazy,prev); CSMatch *m2 = &matches[idx-1]; m1 = &matches[m2->end]; int rpt = m2->rpt+1; if ((rpt==high)||((lazy)&&(rpt>=low))) { // continue to next item. m->buf_idx = next; break; } else if (rpt==0) { // matches 0 times, but that's not in the range. // ex: matches 0 times, but we have a '+' idx--; state = 1; break; } // Try this same one again. m->buf_idx = prev; m->rpt = m1->rpt+1; break; } case rg_end: // Success MatchStart = match_start[0].back(); MatchEnd = match_end[0].back(); return true; } backtrack = false; } else { // backtrack. // Check if repeat is lazy or not. // lazy // if it's a ), then remove match_start and match_end if necessary. par_index++ // if it's a (, then check if we can advance to next | item. If it's ), continue backtracking as if normal item. // if rpt < low, keep backtracking. // if rpt is zero and {empty} is allowed, convert this item or par set to rpt = -1. // otherwise create next item and we're done. unsigned int next = Next(m->buf_idx); unsigned int n = GetRpt(next,low,high,lazy,prev); tt = static_cast<RGTok>(buf[m->buf_idx]); // ) if ((tt==rg_cpn)||((tt>=rg_cpa)&&(tt<=rg_cpa9))) { if ((lazy)&&(m->rpt+1<high)) { if (m->rpt==-1) { // Gotta expand from empty match to single match. idx--; m = &matches[idx]; m->rpt = 0; // This is all that's needed to do that. } else { // Lazy expands, so repeat another set of round brackets. idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; CSMatch *m2 = &matches[m->end]; m1->buf_idx = prev; m1->start = m2->end; m1->rpt = m2->rpt+1; } state = 0; } else { // Not lazy. So backtrack normal. // Gotta update par indexes. if (m->rpt==-1) { // empty set. // remove last 2 items. idx-=2; } else { par_index++; if (par_index+1>par.size()) par.resize(par_index); par[par_index].buf_idx = m->start; par[par_index].match_idx = m->end; idx--; } if (tt!=rg_cpn) { int k = tt-rg_cpa; match_start[k].pop_back(); match_end[k].pop_back(); } } } else if ((tt==rg_orm)||(tt==rg_opn)||((tt>=rg_opa)&&(tt<=rg_opa9))) { // Gotta try next | section. m->buf_idx = m->buf_idx+1+GetValue16(m->buf_idx+1); tt = static_cast<RGTok>(buf[m->buf_idx]); if (tt==rg_orm) { // Try next | section idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx+1+CSREGEX_OFSWIDTH; m1->start = m->start; m1->rpt = 0; state = 0; } else { // found close par. So backtrack/remove this () set. // Gotta get the real high low. n = GetRpt(Next(m->buf_idx),low,high,lazy,prev); if (lazy) { // This is a bit hard to explain. // If this is the 1st repetition in a lazy expansion, // it will have m->rpt = 0 and we can just remove // it with idx--, and the lazy expansion will fail (regex-wise which is ok). // Other backtracking will resume normally. // But if it isn't the 1st item, then we need // to break through the closing ) of the previous // bracket set so that backtracking will continue. // This is because this is lazy backtracking (haha). // Anyways, if we just remove the current opening (, // when we loop around again and try to backtrack on a ), // since this is a lazy backtracking, it will try to go forward // because lazy backtracking is actually *expansion* and will // match another set of (). THIS VERY SET WHICH JUST FAILED!!! // We'd end up in an endless loop. // So we break through the previous () set's closing ) to // continue the backtracking. par_index--; idx--; if (m->rpt!=0) { m = &matches[idx]; par_index++; if (par_index+1>par.size()) par.resize(par_index); par[par_index].buf_idx = m->start; par[par_index].match_idx = m->end; if (tt!=rg_cpn) { int k = tt-rg_cpa; match_start[k].pop_back(); match_end[k].pop_back(); } idx--; } } else if (m->rpt<low) { // Normal backtracking. par_index--; idx--; } else if ((m->rpt==0)&&(low==0)) { // When shrinking greedy repetitions, // and we're on the first repetition, // and the empty set is valid, then we must try // the empty set. // Convert to rpt -1 // m->rpt=-1 means empty set. m->end = m->start; m->rpt = -1; // Insert closing ) for empty set. idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx; m1->start = par[par_index].buf_idx; m1->end = par[par_index].match_idx; tt = static_cast<RGTok>(buf[par[par_index].buf_idx]); if ((tt>=rg_opa)&&(tt<=rg_opa9)) { unsigned int k = tt-rg_opa; match_start[k].push_back(m->start); match_end[k].push_back(m->end); } par_index--; m1->rpt = -1; // Insert item for next match. // Going forward now. Backtracking done. idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-2];} CSMatch *m2 = &matches[idx]; m2->buf_idx = n; m2->start = m->start; m2->rpt = 0; state = 0; } else { // Done backtracking. // Go forward with next item. par_index--; m1 = &matches[idx-1]; // Previous item is ) m->buf_idx = GetRpt(Next(m1->buf_idx),low,high,lazy,prev); m1 = &matches[m1->end]; // Get previous ( m->start = m1->end; m->rpt = 0; state = 0; } } } else if ((lazy)&&(m->rpt+1==high)) { // backtrack all the way. idx-=(m->rpt+1); } else if ((lazy)&&(m->rpt+1>=low)) { if (m->rpt==-1) { // Expansion of the empty item. // -1 is empty while 0 is first item. m->rpt = 0; } else { // Normal repetition expansion. idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = m->buf_idx; m1->start = m->end; m1->rpt = m->rpt+1; // Increase repetition number. } backtrack = true; state = 0; } else if (m->rpt<low) { // This is normal backtracking. // Everything else is a special case. idx--; } else if ((m->rpt==0)&&(low==0)) { // convert current repeat to 0 matches. // When we shrink past the 1st item and the empty item // is valid, we must try it. // We do that by simply setting m->rpt = -1 // m->rpt = -1 mean empty item or set. m->end = m->start; m->rpt = -1; // Move forward to next item. Done backtracking. idx++; if (idx+1>=matches_size) {matches.resize(matches_size*=2); m=&matches[idx-1];} m1 = &matches[idx]; m1->buf_idx = n; m1->start = m->end; m1->rpt = 0; state = 0; } else { // go forward. // This item ok. m1 = &matches[idx-1]; m->buf_idx = GetRpt(Next(m1->buf_idx),low,high,lazy,prev); m->start = m1->end; m->rpt = 0; state = 0; } } } return false; } unsigned int CSRegEx::Next(unsigned int pos) const { RGTok t = static_cast<RGTok>(buf[pos]); unsigned int cpy = t; cpy>>=5; #ifdef _UNICODE // This takes some explaining. // For ASCII, the item byte is always 1. // Anything after this initial byte will be 2 bytes for offsets. // So if an item takes up 1 byte, then it's also 1 wchar_t in UNICODE // So if an item takes up 3 bytes, then it's 1 byte + 1 offset = 2 in UNCODE // So if an item takes up 5 bytes, then it's 1 byte + 2 offset = 3 in UNCODE // So if an item takes up 7 bytes, then it's 1 byte + 3 offset = 4 in UNCODE // Note that (1+1)/2 = 1 // Note that (3+1)/2 = 2 // Note that (5+1)/2 = 3 // Note that (6+1)/2 = 4 // So, we have to add 1 and divide by 2 to get the number // of wchar_t's in UNICODE. // And that's what we do here. cpy = (cpy+1+(t==rg_chr))>>1; #endif if (cpy==0) { if (t==rg_str) { cpy = GetValue16(pos+1)+1+CSREGEX_OFSWIDTH; } else if ((t==rg_grp)||(t==rg_grn)) { cpy = GetValue16(pos+1)-1+2*(GetValue16(pos+1+CSREGEX_OFSWIDTH)-1)+1+2*CSREGEX_OFSWIDTH; } } return pos+cpy; } Docs for CSRegEx created on Tue Dec 11 14:36:53 2007 by Doxygen 1.4.3 Webmaster: Cléo Saulnier