Leaked source code of windows server 2003
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
 
 
 
 
 
 

246 lines
7.5 KiB

/*****************************************************************************
*
* match.cpp
*
* Highly-specialized depot path matching class
*
*****************************************************************************/
#include "sdview.h"
Match::Match(LPCTSTR pszPattern)
{
Tokenizer tok(pszPattern);
String str, strPath, strPats;
while (tok.Token(str)) {
if (MapToFullDepotPath(str, strPath)) {
_AddPattern(strPath, strPats);
}
}
_pszzPats = new TCHAR[strPats.Length()];
if (_pszzPats) {
CopyMemory(_pszzPats, strPats, strPats.Length() * sizeof(TCHAR));
_pszEnd = _pszzPats + strPats.Length();
}
}
BOOL Match::Matches(LPCTSTR pszPath)
{
LPCTSTR pszPat;
if (_pszzPats) {
for (pszPat = _pszzPats;
pszPat < _pszEnd; pszPat += lstrlen(pszPat) + 1) {
if (_Matches(pszPat, pszPath)) {
return TRUE;
}
}
}
return FALSE;
}
#define PAT_END ((TCHAR)0)
#define PAT_START ((TCHAR)1)
#define PAT_DOTS ((TCHAR)2)
#define PAT_STAR ((TCHAR)3)
#define PAT_BRANCH ((TCHAR)4)
#define MAX_BACKTRACK 20 // totally arbitrary
void Match::_AddPattern(LPTSTR pszPat, String& strPats)
{
CharLower(pszPat);
//
// "compile" the pattern by changing "..." to PAT_DOTS and
// "%1" and "*" to PAT_STAR.
//
// Oh, and change "//depot/blah/" and "//depot/private/blah/" to
// "//depot/<PAT_BRANCH>" so we can track across branches.
//
LPTSTR pszIn, pszOut;
int iWildcards = 0;
int cSlashes = 0;
TCHAR pat;
pszIn = pszOut = pszPat;
for (;;) {
switch (*pszIn) {
case TEXT('\r'):
case TEXT('\n'):
case TEXT('\0'):
goto endcompile;
case TEXT('.'):
if (pszIn[1] == TEXT('.') && pszIn[2] == TEXT('.')) {
pszIn += 3;
pat = PAT_DOTS;
goto L_wildcard;
} else {
goto L_default;
}
break;
case TEXT('%'):
if ((UINT)(pszIn[1] - TEXT('1')) < 9) {
pszIn += 2;
pat = PAT_STAR;
goto L_wildcard;
} else {
goto L_default;
}
break;
case TEXT('*'):
pszIn++;
pat = PAT_STAR;
goto L_wildcard;
L_wildcard:
//
// Collapse consecutive wildcards for perf. Otherwise
// a search string of a****b will take exponential
// time.
//
if (pszOut[-1] == pat) {
// ** and ...... are the same as * and ... (respectively)
// so just throw away the second wildcard.
} else if (pszOut[-1] == (PAT_STAR + PAT_DOTS - pat)) {
// ...* and *... are the same as "..."
pszOut[-1] = PAT_DOTS;
} else if (iWildcards++ < MAX_BACKTRACK) {
// just a regular ol' wildcard
*pszOut++ = pat;
} else {
*pszOut++ = PAT_DOTS; // Give up when the limit is reached
goto endcompile;
}
break;
case TEXT('/'):
cSlashes++;
if (cSlashes == 3) {
if (StringBeginsWith(pszIn, TEXT("/private/"))) {
// a private branch
*pszOut++ = PAT_BRANCH;
pszIn += 9; // length of "/private/"
} else {
// a main branch
*pszOut++ = PAT_BRANCH;
}
// Skip over the branch name
while (*pszIn != TEXT('/') &&
*pszIn != TEXT('\r') &&
*pszIn != TEXT('\n') &&
*pszIn != TEXT('\0')) {
pszIn++;
}
} else {
goto L_default;
}
break;
L_default:
default:
*pszOut++ = *pszIn++;
}
}
endcompile:;
*pszOut++ = PAT_END;
// Now add it to the list of patterns we care about
strPats << PAT_START << Substring(pszPat, pszOut);
}
//
// This is the fun part -- funky pattern matching.
//
// The pszPath is assumed to be of the form
//
// //depot/fully/qualified/path#n
//
// PAT_DOTS matches any string.
// PAT_STAR matches any string not including slash.
//
// This code is adapted from code I wrote back in 1993 for the
// Windows 95 Netware emulation layer. I've also seen it stolen
// by Wininet. I guess good code never dies. Or maybe it's just
// that pattern matching is hard. (I suspect the latter because
// the Wininet folks stole the code and then adapted it incorrectly.)
//
BOOL Match::_Matches(LPCTSTR pszPat, LPCTSTR pszPath)
{
struct Backtrack {
int iStart;
int iEnd;
};
Backtrack rgbt[MAX_BACKTRACK+1]; /* +1 for PAT_START fake-backtrack point */
Backtrack *pbt = rgbt;
int i, j; /* i = index to pattern, j = index to target */
int m = lstrlen(pszPath); /* m = length of target */
int back; /* First available slot in backtrack array */
i = -1; /* Will be advanced to 0 */
j = 0;
advance:
++i;
switch (pszPat[i]) {
case PAT_START: pbt->iEnd = 0; goto advance;
case PAT_END: if (pszPath[j] == TEXT('#')) return TRUE;
else goto retreat;
case PAT_DOTS: pbt++; // this is a backtracking rule
pbt->iStart = j;
pbt->iEnd = j = m; goto advance;
case PAT_STAR: pbt++; // this is a backtracking rule
pbt->iStart = j;
while (pszPath[j] != TEXT('/') &&
pszPath[j] != TEXT('#') &&
pszPath[j] != TEXT('\0')) {
j++;
}
pbt->iEnd = j; goto advance;
case PAT_BRANCH: // this is a non-backtracking rule
if (pszPath[j] != TEXT('/')) goto retreat;
if (StringBeginsWith(&pszPath[j], TEXT("/private/"))) {
j += 8;
}
// Skip over the branch name
do {
j++;
} while (pszPath[j] != TEXT('/') &&
pszPath[j] != TEXT('#') &&
pszPath[j] != TEXT('\0'));
goto advance;
default: if (pszPath[j] == pszPat[i]) {
j++;
goto advance;
} else if (pszPath[j] >= TEXT('A') &&
pszPath[j] <= TEXT('Z') &&
pszPath[j] - TEXT('A') + TEXT('a') == pszPat[i]) {
// I hate case-insensitivity
j++;
goto advance;
} else goto retreat;
}
retreat:
--i;
switch (pszPat[i]) {
case PAT_START: return FALSE; // cannot backtrack further
case PAT_DOTS:
case PAT_STAR: if (pbt->iStart == pbt->iEnd) {
pbt--;
goto retreat;
}
j = --pbt->iEnd; goto advance;
default: goto retreat;
}
}