src/WINNT/afsapplib/regexp.cpp

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 extern "C" {
  11 #include <afs/param.h>
  12 #include <afs/stds.h>
  13 }
  14
  15 #include <windows.h>
  16 #include <WINNT/regexp.h>
  17
  18
  19 /*
  20  * DEFINITIONS ________________________________________________________________
  21  *
  22  */
  23
  24 #define markREPEAT       TEXT('\x01')
  25 #define markCHARACTER    TEXT('\x02')
  26 #define markANYCHAR      TEXT('\x04')
  27 #define markCHARSET      TEXT('\x06')
  28 #define markNONCHARSET   TEXT('\x08')
  29 #define markREFERENCE    TEXT('\x0A')
  30 #define markLPAREN       TEXT('\xFC')
  31 #define markRPAREN       TEXT('\xFD')
  32 #define markENDLINE      TEXT('\xFE')
  33 #define markENDPATTERN   TEXT('\xFF')
  34
  35
  36 /*
  37  * CLASS ROUTINES _____________________________________________________________
  38  *
  39  */
  40
  41 REGEXP::REGEXP (void)
  42 {
  43    m_fMatchFromStart = FALSE;
  44    m_achCompiled[0] = TEXT('\0');
  45 }
  46
  47 REGEXP::REGEXP (LPCTSTR pszExpr)
  48 {
  49    m_fMatchFromStart = FALSE;
  50    m_achCompiled[0] = TEXT('\0');
  51    SetExpression (pszExpr);
  52 }
  53
  54 REGEXP::~REGEXP (void)
  55 {
  56    ; // nothing really to do here
  57 }
  58
  59 BOOL REGEXP::SetExpression (LPCTSTR pszExpr)
  60 {
  61    return Compile (pszExpr);
  62 }
  63
  64 BOOL REGEXP::Matches (LPCTSTR pszExpr, LPCTSTR pszString)
  65 {
  66    REGEXP Expr (pszExpr);
  67    return Expr.Matches (pszString);
  68 }
  69
  70 BOOL REGEXP::fIsRegExp (void)
  71 {
  72    if (m_fMatchFromStart) // started with "^"?
  73       return TRUE;        // it's a regexp.
  74
  75    for (LPCTSTR pch = m_achCompiled; (*pch) && (*pch != markENDPATTERN); pch += 2)
  76       {
  77       if (*pch != markCHARACTER)
  78          return TRUE;
  79       }
  80
  81    return FALSE; // just a string of characters
  82 }
  83
  84 BOOL REGEXP::fIsRegExp (LPCTSTR pszExpr)
  85 {
  86    REGEXP Expr (pszExpr);
  87    return Expr.fIsRegExp();
  88 }
  89
  90
  91 /*
  92  * REGEXP _____________________________________________________________________
  93  *
  94  */
  95
  96 BOOL REGEXP::Compile (LPCTSTR pszExpr)
  97 {
  98    BYTE aParens[ nCOMPILED_PARENS_MAX ];
  99    PBYTE pParen = &aParens[0];
 100    LPTSTR pchLastEx = NULL;
 101    int nParens = 0;
 102
 103    // Erase any previous compiled expression
 104    //
 105    LPTSTR pchCompiled = m_achCompiled;
 106    *pchCompiled = TEXT('\0');
 107    m_fMatchFromStart = FALSE;
 108
 109    if (!pszExpr || !*pszExpr)
 110       {
 111       SetLastError (ERROR_INVALID_PARAMETER);
 112       return FALSE;
 113       }
 114
 115    // See if the expression starts with a "^"
 116    //
 117    if ((m_fMatchFromStart = (*pszExpr == TEXT('^'))) == TRUE)
 118       ++pszExpr;
 119
 120    // Start stripping characters from the expression
 121    //
 122    BOOL rc;
 123    for (rc = TRUE; rc; )
 124       {
 125       TCHAR ch;
 126
 127       if ((sizeof(TCHAR)*(pchCompiled - m_achCompiled)) > sizeof(m_achCompiled))
 128          {
 129          SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 130          rc = FALSE;
 131          break;
 132          }
 133
 134       if ((ch = *pszExpr++) == TEXT('\0'))
 135          {
 136          // We finally hit the end of this expression.
 137          //
 138          if (pParen != &aParens[0])
 139             {
 140             SetLastError (ERROR_BAD_FORMAT); // unmatched "\("
 141             rc = FALSE;
 142             }
 143          break;
 144          }
 145
 146       if (ch != TEXT('*'))
 147          pchLastEx = pchCompiled;
 148
 149       switch (ch)
 150          {
 151          case TEXT('.'):
 152          case TEXT('?'):
 153             *pchCompiled++ = markANYCHAR;
 154             break;
 155
 156          case TEXT('*'):
 157             if ((pchLastEx == NULL) || (*pchLastEx == markLPAREN) || (*pchLastEx == markRPAREN))
 158                {
 159                *pchCompiled++ = markCHARACTER;
 160                *pchCompiled++ = ch;
 161                }
 162             else // record that we can repeat the last expression
 163                {
 164                *pchLastEx |= markREPEAT;
 165                }
 166             break;
 167
 168          case TEXT('$'):
 169             if (*pszExpr != TEXT('\0'))
 170                {
 171                *pchCompiled++ = markCHARACTER;
 172                *pchCompiled++ = ch;
 173                }
 174             else // record that we should match end-of-line
 175                {
 176                *pchCompiled++ = markENDLINE;
 177                }
 178             break;
 179
 180          case TEXT('['):
 181             if ((ch = *pszExpr++) == '^')
 182                {
 183                *pchCompiled++ = markNONCHARSET;
 184                ch = *pszExpr++;
 185                }
 186             else
 187                {
 188                *pchCompiled++ = markCHARSET;
 189                }
 190
 191             *pchCompiled++ = 1;            // length; this is pchLastEx[1]
 192
 193             do {
 194                if (ch == TEXT('\0'))
 195                   {
 196                   SetLastError (ERROR_BAD_FORMAT); // unmatched "\("
 197                   rc = FALSE;
 198                   break;
 199                   }
 200
 201                if ((ch == TEXT('-')) && (*pchCompiled != pchLastEx[2]))
 202                   {
 203                   if ((ch = *pszExpr++) == TEXT(']'))
 204                      {
 205                      *pchCompiled++ = TEXT('-');
 206                      pchLastEx[1]++;
 207                      break;
 208                      }
 209                   while ((BYTE)pchCompiled[-1] < (BYTE)ch)
 210                      {
 211                      *pchCompiled = pchCompiled[-1] + 1;
 212                      pchCompiled++;
 213                      pchLastEx[1]++;
 214                      if ((sizeof(TCHAR)*(pchCompiled - m_achCompiled)) > sizeof(m_achCompiled))
 215                         {
 216                         SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 217                         rc = FALSE;
 218                         break;
 219                         }
 220                      }
 221                   }
 222                else
 223                   {
 224                   *pchCompiled++ = ch;
 225                   pchLastEx[1]++;
 226
 227                   if ((sizeof(TCHAR)*(pchCompiled - m_achCompiled)) > sizeof(m_achCompiled))
 228                      {
 229                      SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 230                      rc = FALSE;
 231                      break;
 232                      }
 233                   }
 234
 235                } while ((ch = *pszExpr++) != TEXT(']'));
 236             break;
 237
 238          case TEXT('\\'):
 239             if ((ch = *pszExpr++) == TEXT('('))
 240                {
 241                if (nParens >= nCOMPILED_PARENS_MAX)
 242                   {
 243                   SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 244                   rc = FALSE;
 245                   break;
 246                   }
 247                *pParen++ = nParens;
 248                *pchCompiled++ = markLPAREN;
 249                *pchCompiled++ = nParens++;
 250                }
 251             else if (ch == TEXT(')'))
 252                {
 253                if (pParen == &aParens[0])
 254                   {
 255                   SetLastError (ERROR_BAD_FORMAT);
 256                   rc = FALSE;
 257                   break;
 258                   }
 259                *pchCompiled++ = markRPAREN;
 260                *pchCompiled++ = *--pParen;
 261                }
 262             else if ((ch >= TEXT('1')) && (ch < (TEXT('1') + nCOMPILED_PARENS_MAX)))
 263                {
 264                *pchCompiled++ = markREFERENCE;
 265                *pchCompiled++ = ch - '1';
 266                }
 267             else
 268                {
 269                *pchCompiled++ = markCHARACTER;
 270                *pchCompiled++ = ch;
 271                }
 272             break;
 273
 274          default:
 275             *pchCompiled++ = markCHARACTER;
 276             *pchCompiled++ = ch;
 277             break;
 278          }
 279       }
 280
 281    *pchCompiled++ = markENDPATTERN;
 282    *pchCompiled++ = 0;
 283    return rc;
 284 }
 285
 286
 287 BOOL REGEXP::Matches (LPCTSTR pszString)
 288 {
 289    if (!pszString)
 290       return FALSE;
 291
 292    // Prepare a place to store information about \( and \) pairs
 293    //
 294    LPCTSTR aParenStarts[ nCOMPILED_PARENS_MAX ];
 295    LPCTSTR aParenEnds[ nCOMPILED_PARENS_MAX ];
 296
 297    for (size_t ii = 0; ii < nCOMPILED_PARENS_MAX; ii++)
 298       {
 299       aParenStarts[ii] = NULL;
 300       aParenEnds[ii] = NULL;
 301       }
 302
 303    // If the expression starts with "^", we can do a quick pattern-match...
 304    //
 305    if (m_fMatchFromStart)
 306       {
 307       return MatchSubset (pszString, m_achCompiled, aParenStarts, aParenEnds);
 308       }
 309
 310    // Otherwise, we have to work a little harder. If the expression
 311    // at least starts with a recognized character, we can scan for that
 312    // as the start of a pattern...
 313    //
 314    LPTSTR pchCompiled = m_achCompiled;
 315    if (*pchCompiled == markCHARACTER)
 316       {
 317       TCHAR chStart = pchCompiled[1];
 318       do {
 319          if (*pszString != chStart)
 320             continue;
 321          if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 322             return TRUE;
 323          } while (*pszString++);
 324
 325       return FALSE;
 326       }
 327
 328    // If the expression starts with something weird, we'll have to test
 329    // against every character in the string.
 330    //
 331    do {
 332       if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 333          return TRUE;
 334       } while (*pszString++);
 335
 336    return FALSE;
 337 }
 338
 339
 340 BOOL REGEXP::MatchSubset (LPCTSTR pszString, LPCTSTR pchCompiled, LPCTSTR *aParenStarts, LPCTSTR *aParenEnds)
 341 {
 342    LPCTSTR pchStartOfEx;
 343    int ii;
 344    int cchPattern;
 345
 346    while (1)
 347    switch (*pchCompiled++)
 348       {
 349       case markCHARACTER:
 350          if (*pchCompiled++ == *pszString++)
 351             continue;
 352          return FALSE;
 353
 354       case markANYCHAR:
 355          if (*pszString++)
 356             continue;
 357          return FALSE;
 358
 359       case markENDLINE:
 360          if (*pszString == TEXT('\0'))
 361             continue;
 362          return FALSE;
 363
 364       case markENDPATTERN:
 365          return TRUE;
 366
 367       case markCHARSET:
 368          if (fIsInCharSet (pchCompiled, *pszString++, TRUE))
 369             {
 370             pchCompiled += *pchCompiled;
 371             continue;
 372             }
 373          return FALSE;
 374
 375       case markNONCHARSET:
 376          if (fIsInCharSet (pchCompiled, *pszString++, FALSE))
 377             {
 378             pchCompiled += *pchCompiled;
 379             continue;
 380             }
 381          return FALSE;
 382
 383       case markLPAREN:
 384          aParenStarts[*pchCompiled++] = pszString;
 385          continue;
 386
 387       case markRPAREN:
 388          aParenEnds[*pchCompiled++] = pszString;
 389          continue;
 390
 391       case markREFERENCE:
 392          if (aParenEnds[ii = *pchCompiled++] == 0)
 393             return FALSE; // reference to invalid \(\) pair
 394          if (CompareParen (ii, pszString, aParenStarts, aParenEnds))
 395             {
 396             pszString += aParenEnds[ii] - aParenStarts[ii];
 397             continue;
 398             }
 399          return FALSE;
 400
 401       case markREFERENCE|markREPEAT:
 402          if (aParenEnds[ii = *pchCompiled++] == 0)
 403             return FALSE; // reference to invalid \(\) pair
 404          pchStartOfEx = pszString;
 405          cchPattern = aParenEnds[ii] - aParenStarts[ii];
 406          while (CompareParen (ii, pszString, aParenStarts, aParenEnds))
 407             pszString += cchPattern;
 408          while (pszString >= pchStartOfEx)
 409             {
 410             if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 411                return TRUE;
 412             pszString -= cchPattern;
 413             }
 414          continue;
 415
 416       case markANYCHAR|markREPEAT:
 417          pchStartOfEx = pszString;
 418          while (*pszString++)
 419             ;
 420          goto star;
 421
 422       case markCHARACTER|markREPEAT:
 423          pchStartOfEx = pszString;
 424          while (*pszString++ == *pchCompiled)
 425             ;
 426          pchCompiled++;
 427          goto star;
 428
 429       case markCHARSET|markREPEAT:
 430       case markNONCHARSET|markREPEAT:
 431          pchStartOfEx = pszString;
 432          while (fIsInCharSet (pchCompiled, *pszString++, (pchCompiled[-1] == (markCHARSET|markREPEAT))))
 433             ;
 434          pchCompiled += *pchCompiled;
 435          goto star;
 436
 437       star:
 438          do {
 439             pszString--;
 440             if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 441                return TRUE;
 442             } while (pszString > pchStartOfEx);
 443          return FALSE;
 444
 445       default:
 446          return FALSE; // damaged compiled string
 447       }
 448 }
 449
 450
 451 BOOL REGEXP::CompareParen (int ii, LPCTSTR pszString, LPCTSTR *aParenStarts, LPCTSTR *aParenEnds)
 452 {
 453    LPCTSTR pchInParen = aParenStarts[ii];
 454    while (*pchInParen++ == *pszString++)
 455       if (pchInParen >= aParenEnds[ii])
 456          return TRUE;
 457    return FALSE;
 458 }
 459
 460
 461 BOOL REGEXP::fIsInCharSet (LPCTSTR pszCharSet, TCHAR chTest, int fInclusive)
 462 {
 463    if (chTest == 0)
 464       return FALSE;
 465    for (int n = (int)(*pszCharSet++); --n; )
 466       {
 467       if (*pszCharSet++ == chTest)
 468          return fInclusive;
 469       }
 470    return !fInclusive;
 471 }
 472