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    for (BOOL rc = TRUE; rc; )
 123       {
 124       TCHAR ch;
 125
 126       if ((sizeof(TCHAR)*(pchCompiled - m_achCompiled)) > sizeof(m_achCompiled))
 127          {
 128          SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 129          rc = FALSE;
 130          break;
 131          }
 132
 133       if ((ch = *pszExpr++) == TEXT('\0'))
 134          {
 135          // We finally hit the end of this expression.
 136          //
 137          if (pParen != &aParens[0])
 138             {
 139             SetLastError (ERROR_BAD_FORMAT); // unmatched "\("
 140             rc = FALSE;
 141             }
 142          break;
 143          }
 144
 145       if (ch != TEXT('*'))
 146          pchLastEx = pchCompiled;
 147
 148       switch (ch)
 149          {
 150          case TEXT('.'):
 151          case TEXT('?'):
 152             *pchCompiled++ = markANYCHAR;
 153             break;
 154
 155          case TEXT('*'):
 156             if ((pchLastEx == NULL) || (*pchLastEx == markLPAREN) || (*pchLastEx == markRPAREN))
 157                {
 158                *pchCompiled++ = markCHARACTER;
 159                *pchCompiled++ = ch;
 160                }
 161             else // record that we can repeat the last expression
 162                {
 163                *pchLastEx |= markREPEAT;
 164                }
 165             break;
 166
 167          case TEXT('$'):
 168             if (*pszExpr != TEXT('\0'))
 169                {
 170                *pchCompiled++ = markCHARACTER;
 171                *pchCompiled++ = ch;
 172                }
 173             else // record that we should match end-of-line
 174                {
 175                *pchCompiled++ = markENDLINE;
 176                }
 177             break;
 178
 179          case TEXT('['):
 180             if ((ch = *pszExpr++) == '^')
 181                {
 182                *pchCompiled++ = markNONCHARSET;
 183                ch = *pszExpr++;
 184                }
 185             else
 186                {
 187                *pchCompiled++ = markCHARSET;
 188                }
 189
 190             *pchCompiled++ = 1;            // length; this is pchLastEx[1]
 191
 192             do {
 193                if (ch == TEXT('\0'))
 194                   {
 195                   SetLastError (ERROR_BAD_FORMAT); // unmatched "\("
 196                   rc = FALSE;
 197                   break;
 198                   }
 199
 200                if ((ch == TEXT('-')) && (*pchCompiled != pchLastEx[2]))
 201                   {
 202                   if ((ch = *pszExpr++) == TEXT(']'))
 203                      {
 204                      *pchCompiled++ = TEXT('-');
 205                      pchLastEx[1]++;
 206                      break;
 207                      }
 208                   while ((BYTE)pchCompiled[-1] < (BYTE)ch)
 209                      {
 210                      *pchCompiled = pchCompiled[-1] + 1;
 211                      pchCompiled++;
 212                      pchLastEx[1]++;
 213                      if ((sizeof(TCHAR)*(pchCompiled - m_achCompiled)) > sizeof(m_achCompiled))
 214                         {
 215                         SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 216                         rc = FALSE;
 217                         break;
 218                         }
 219                      }
 220                   }
 221                else
 222                   {
 223                   *pchCompiled++ = ch;
 224                   pchLastEx[1]++;
 225
 226                   if ((sizeof(TCHAR)*(pchCompiled - m_achCompiled)) > sizeof(m_achCompiled))
 227                      {
 228                      SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 229                      rc = FALSE;
 230                      break;
 231                      }
 232                   }
 233
 234                } while ((ch = *pszExpr++) != TEXT(']'));
 235             break;
 236
 237          case TEXT('\\'):
 238             if ((ch = *pszExpr++) == TEXT('('))
 239                {
 240                if (nParens >= nCOMPILED_PARENS_MAX)
 241                   {
 242                   SetLastError (ERROR_META_EXPANSION_TOO_LONG);
 243                   rc = FALSE;
 244                   break;
 245                   }
 246                *pParen++ = nParens;
 247                *pchCompiled++ = markLPAREN;
 248                *pchCompiled++ = nParens++;
 249                }
 250             else if (ch == TEXT(')'))
 251                {
 252                if (pParen == &aParens[0])
 253                   {
 254                   SetLastError (ERROR_BAD_FORMAT);
 255                   rc = FALSE;
 256                   break;
 257                   }
 258                *pchCompiled++ = markRPAREN;
 259                *pchCompiled++ = *--pParen;
 260                }
 261             else if ((ch >= TEXT('1')) && (ch < (TEXT('1') + nCOMPILED_PARENS_MAX)))
 262                {
 263                *pchCompiled++ = markREFERENCE;
 264                *pchCompiled++ = ch - '1';
 265                }
 266             else
 267                {
 268                *pchCompiled++ = markCHARACTER;
 269                *pchCompiled++ = ch;
 270                }
 271             break;
 272
 273          default:
 274             *pchCompiled++ = markCHARACTER;
 275             *pchCompiled++ = ch;
 276             break;
 277          }
 278       }
 279
 280    *pchCompiled++ = markENDPATTERN;
 281    *pchCompiled++ = 0;
 282    return rc;
 283 }
 284
 285
 286 BOOL REGEXP::Matches (LPCTSTR pszString)
 287 {
 288    if (!pszString)
 289       return FALSE;
 290
 291    // Prepare a place to store information about \( and \) pairs
 292    //
 293    LPCTSTR aParenStarts[ nCOMPILED_PARENS_MAX ];
 294    LPCTSTR aParenEnds[ nCOMPILED_PARENS_MAX ];
 295
 296    for (size_t ii = 0; ii < nCOMPILED_PARENS_MAX; ii++)
 297       {
 298       aParenStarts[ii] = NULL;
 299       aParenEnds[ii] = NULL;
 300       }
 301
 302    // If the expression starts with "^", we can do a quick pattern-match...
 303    //
 304    if (m_fMatchFromStart)
 305       {
 306       return MatchSubset (pszString, m_achCompiled, aParenStarts, aParenEnds);
 307       }
 308
 309    // Otherwise, we have to work a little harder. If the expression
 310    // at least starts with a recognized character, we can scan for that
 311    // as the start of a pattern...
 312    //
 313    LPTSTR pchCompiled = m_achCompiled;
 314    if (*pchCompiled == markCHARACTER)
 315       {
 316       TCHAR chStart = pchCompiled[1];
 317       do {
 318          if (*pszString != chStart)
 319             continue;
 320          if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 321             return TRUE;
 322          } while (*pszString++);
 323
 324       return FALSE;
 325       }
 326
 327    // If the expression starts with something weird, we'll have to test
 328    // against every character in the string.
 329    //
 330    do {
 331       if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 332          return TRUE;
 333       } while (*pszString++);
 334
 335    return FALSE;
 336 }
 337
 338
 339 BOOL REGEXP::MatchSubset (LPCTSTR pszString, LPCTSTR pchCompiled, LPCTSTR *aParenStarts, LPCTSTR *aParenEnds)
 340 {
 341    LPCTSTR pchStartOfEx;
 342    int ii;
 343    int cchPattern;
 344
 345    while (1)
 346    switch (*pchCompiled++)
 347       {
 348       case markCHARACTER:
 349          if (*pchCompiled++ == *pszString++)
 350             continue;
 351          return FALSE;
 352
 353       case markANYCHAR:
 354          if (*pszString++)
 355             continue;
 356          return FALSE;
 357
 358       case markENDLINE:
 359          if (*pszString == TEXT('\0'))
 360             continue;
 361          return FALSE;
 362
 363       case markENDPATTERN:
 364          return TRUE;
 365
 366       case markCHARSET:
 367          if (fIsInCharSet (pchCompiled, *pszString++, TRUE))
 368             {
 369             pchCompiled += *pchCompiled;
 370             continue;
 371             }
 372          return FALSE;
 373
 374       case markNONCHARSET:
 375          if (fIsInCharSet (pchCompiled, *pszString++, FALSE))
 376             {
 377             pchCompiled += *pchCompiled;
 378             continue;
 379             }
 380          return FALSE;
 381
 382       case markLPAREN:
 383          aParenStarts[*pchCompiled++] = pszString;
 384          continue;
 385
 386       case markRPAREN:
 387          aParenEnds[*pchCompiled++] = pszString;
 388          continue;
 389
 390       case markREFERENCE:
 391          if (aParenEnds[ii = *pchCompiled++] == 0)
 392             return FALSE; // reference to invalid \(\) pair
 393          if (CompareParen (ii, pszString, aParenStarts, aParenEnds))
 394             {
 395             pszString += aParenEnds[ii] - aParenStarts[ii];
 396             continue;
 397             }
 398          return FALSE;
 399
 400       case markREFERENCE|markREPEAT:
 401          if (aParenEnds[ii = *pchCompiled++] == 0)
 402             return FALSE; // reference to invalid \(\) pair
 403          pchStartOfEx = pszString;
 404          cchPattern = aParenEnds[ii] - aParenStarts[ii];
 405          while (CompareParen (ii, pszString, aParenStarts, aParenEnds))
 406             pszString += cchPattern;
 407          while (pszString >= pchStartOfEx)
 408             {
 409             if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 410                return TRUE;
 411             pszString -= cchPattern;
 412             }
 413          continue;
 414
 415       case markANYCHAR|markREPEAT:
 416          pchStartOfEx = pszString;
 417          while (*pszString++)
 418             ;
 419          goto star;
 420
 421       case markCHARACTER|markREPEAT:
 422          pchStartOfEx = pszString;
 423          while (*pszString++ == *pchCompiled)
 424             ;
 425          pchCompiled++;
 426          goto star;
 427
 428       case markCHARSET|markREPEAT:
 429       case markNONCHARSET|markREPEAT:
 430          pchStartOfEx = pszString;
 431          while (fIsInCharSet (pchCompiled, *pszString++, (pchCompiled[-1] == (markCHARSET|markREPEAT))))
 432             ;
 433          pchCompiled += *pchCompiled;
 434          goto star;
 435
 436       star:
 437          do {
 438             pszString--;
 439             if (MatchSubset (pszString, pchCompiled, aParenStarts, aParenEnds))
 440                return TRUE;
 441             } while (pszString > pchStartOfEx);
 442          return FALSE;
 443
 444       default:
 445          return FALSE; // damaged compiled string
 446       }
 447 }
 448
 449
 450 BOOL REGEXP::CompareParen (int ii, LPCTSTR pszString, LPCTSTR *aParenStarts, LPCTSTR *aParenEnds)
 451 {
 452    LPCTSTR pchInParen = aParenStarts[ii];
 453    while (*pchInParen++ == *pszString++)
 454       if (pchInParen >= aParenEnds[ii])
 455          return TRUE;
 456    return FALSE;
 457 }
 458
 459
 460 BOOL REGEXP::fIsInCharSet (LPCTSTR pszCharSet, TCHAR chTest, int fInclusive)
 461 {
 462    if (chTest == 0)
 463       return FALSE;
 464    for (int n = (int)(*pszCharSet++); --n; )
 465       {
 466       if (*pszCharSet++ == chTest)
 467          return fInclusive;
 468       }
 469    return !fInclusive;
 470 }
 471