src/kits/tracker/TrackerString.cpp

   1 /*
   2 Open Tracker License
   3
   4 Terms and Conditions
   5
   6 Copyright (c) 1991-2000, Be Incorporated. All rights reserved.
   7
   8 Permission is hereby granted, free of charge, to any person obtaining a copy of
   9 this software and associated documentation files (the "Software"), to deal in
  10 the Software without restriction, including without limitation the rights to
  11 use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies
  12 of the Software, and to permit persons to whom the Software is furnished to do
  13 so, subject to the following conditions:
  14
  15 The above copyright notice and this permission notice applies to all licensees
  16 and shall be included in all copies or substantial portions of the Software.
  17
  18 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  19 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF TITLE, MERCHANTABILITY,
  20 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
  21 BE INCORPORATED BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
  22 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF, OR IN CONNECTION
  23 WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  24
  25 Except as contained in this notice, the name of Be Incorporated shall not be
  26 used in advertising or otherwise to promote the sale, use or other dealings in
  27 this Software without prior written authorization from Be Incorporated.
  28
  29 Tracker(TM), Be(R), BeOS(R), and BeIA(TM) are trademarks or registered trademarks
  30 of Be Incorporated in the United States and other countries. Other brand product
  31 names are registered trademarks or trademarks of their respective holders.
  32 All rights reserved.
  33 */
  34
  35 #include "TrackerString.h"
  36
  37 #include <stdio.h>
  38 #include <stdlib.h>
  39 #include <strings.h>
  40
  41
  42 //      #pragma mark - TrackerString
  43
  44
  45 TrackerString::TrackerString()
  46 {
  47 }
  48
  49
  50 TrackerString::TrackerString(const char* string)
  51         :
  52         BString(string)
  53 {
  54 }
  55
  56
  57 TrackerString::TrackerString(const TrackerString &string)
  58         :
  59         BString(string)
  60 {
  61 }
  62
  63
  64 TrackerString::TrackerString(const char* string, int32 maxLength)
  65         :
  66         BString(string, maxLength)
  67 {
  68 }
  69
  70
  71 TrackerString::~TrackerString()
  72 {
  73 }
  74
  75
  76 bool
  77 TrackerString::Matches(const char* string, bool caseSensitivity,
  78         TrackerStringExpressionType expressionType) const
  79 {
  80         switch (expressionType) {
  81                 default:
  82                 case kNone:
  83                         return false;
  84
  85                 case kStartsWith:
  86                         return StartsWith(string, caseSensitivity);
  87
  88                 case kEndsWith:
  89                         return EndsWith(string, caseSensitivity);
  90
  91                 case kContains:
  92                         return Contains(string, caseSensitivity);
  93
  94                 case kGlobMatch:
  95                         return MatchesGlob(string, caseSensitivity);
  96
  97                 case kRegexpMatch:
  98                         return MatchesRegExp(string, caseSensitivity);
  99         }
 100 }
 101
 102
 103 bool
 104 TrackerString::MatchesRegExp(const char* pattern, bool caseSensitivity) const
 105 {
 106         BString patternString(pattern);
 107         BString textString(String());
 108
 109         if (caseSensitivity == false) {
 110                 patternString.ToLower();
 111                 textString.ToLower();
 112         }
 113
 114         RegExp expression(patternString);
 115
 116         if (expression.InitCheck() != B_OK)
 117                 return false;
 118
 119         return expression.Matches(textString);
 120 }
 121
 122
 123 bool
 124 TrackerString::MatchesGlob(const char* string, bool caseSensitivity) const
 125 {
 126         return StringMatchesPattern(String(), string, caseSensitivity);
 127 }
 128
 129
 130 bool
 131 TrackerString::EndsWith(const char* string, bool caseSensitivity) const
 132 {
 133         // If "string" is longer than "this",
 134         // we should simply return false
 135         int32 position = Length() - (int32)strlen(string);
 136         if (position < 0)
 137                 return false;
 138
 139         if (caseSensitivity)
 140                 return FindLast(string) == position;
 141         else
 142                 return IFindLast(string) == position;
 143 }
 144
 145
 146 bool
 147 TrackerString::StartsWith(const char* string, bool caseSensitivity) const
 148 {
 149         if (caseSensitivity)
 150                 return FindFirst(string) == 0;
 151         else
 152                 return IFindFirst(string) == 0;
 153 }
 154
 155
 156 bool
 157 TrackerString::Contains(const char* string, bool caseSensitivity) const
 158 {
 159         if (caseSensitivity)
 160                 return FindFirst(string) > -1;
 161         else
 162                 return IFindFirst(string) > -1;
 163 }
 164
 165
 166 // MatchesBracketExpression() assumes 'pattern' to point to the
 167 // character following the initial '[' in a bracket expression.
 168 // The reason is that an encountered '[' will be taken literally.
 169 // (Makes it possible to match a '[' with the expression '[[]').
 170 bool
 171 TrackerString::MatchesBracketExpression(const char* string,
 172         const char* pattern, bool caseSensitivity) const
 173 {
 174         bool GlyphMatch = IsStartOfGlyph(string[0]);
 175
 176         if (IsInsideGlyph(string[0]))
 177                 return false;
 178
 179         char testChar = ConditionalToLower(string[0], caseSensitivity);
 180         bool match = false;
 181
 182         bool inverse = *pattern == '^' || *pattern == '!';
 183                 // We allow both ^ and ! as a initial inverting character.
 184
 185         if (inverse)
 186                 pattern++;
 187
 188         while (!match && *pattern != ']' && *pattern != '\0') {
 189                 switch (*pattern) {
 190                         case '-':
 191                         {
 192                                 char start = ConditionalToLower(*(pattern - 1),
 193                                         caseSensitivity);
 194                                 char stop = ConditionalToLower(*(pattern + 1),
 195                                         caseSensitivity);
 196
 197                                 if (IsGlyph(start) || IsGlyph(stop))
 198                                         return false;
 199                                                 // Not a valid range!
 200
 201                                 if ((islower(start) && islower(stop))
 202                                         || (isupper(start) && isupper(stop))
 203                                         || (isdigit(start) && isdigit(stop))) {
 204                                         // Make sure 'start' and 'stop' are of the same type.
 205                                         match = start <= testChar && testChar <= stop;
 206                                 } else {
 207                                         // If no valid range, we've got a syntax error.
 208                                         return false;
 209                                 }
 210
 211                                 break;
 212                         }
 213
 214                         default:
 215                                 if (GlyphMatch)
 216                                         match = UTF8CharsAreEqual(string, pattern);
 217                                 else
 218                                         match = CharsAreEqual(testChar, *pattern, caseSensitivity);
 219                                 break;
 220                 }
 221
 222                 if (!match) {
 223                         pattern++;
 224                         if (IsInsideGlyph(pattern[0]))
 225                                 pattern = MoveToEndOfGlyph(pattern);
 226                 }
 227         }
 228
 229         // Consider an unmatched bracket a failure
 230         // (i.e. when detecting a '\0' instead of a ']'.)
 231         if (*pattern == '\0')
 232                 return false;
 233
 234         return (match ^ inverse) != 0;
 235 }
 236
 237
 238 bool
 239 TrackerString::StringMatchesPattern(const char* string, const char* pattern,
 240         bool caseSensitivity) const
 241 {
 242         // One could do this dynamically, counting the number of *'s,
 243         // but then you have to free them at every exit of this
 244         // function, which is awkward and ugly.
 245         const int32 kWildCardMaximum = 100;
 246         const char* pStorage[kWildCardMaximum];
 247         const char* sStorage[kWildCardMaximum];
 248
 249         int32 patternLevel = 0;
 250
 251         if (string == NULL || pattern == NULL)
 252                 return false;
 253
 254         while (*pattern != '\0') {
 255                 switch (*pattern) {
 256                         case '?':
 257                                 pattern++;
 258                                 string++;
 259                                 if (IsInsideGlyph(string[0]))
 260                                         string = MoveToEndOfGlyph(string);
 261                                 break;
 262
 263                         case '*':
 264                         {
 265                                 // Collapse any ** and *? constructions:
 266                                 while (*pattern == '*' || *pattern == '?') {
 267                                         pattern++;
 268                                         if (*pattern == '?' && string != '\0') {
 269                                                 string++;
 270                                                 if (IsInsideGlyph(string[0]))
 271                                                         string = MoveToEndOfGlyph(string);
 272                                         }
 273                                 }
 274
 275                                 if (*pattern == '\0') {
 276                                         // An ending * matches all strings.
 277                                         return true;
 278                                 }
 279
 280                                 bool match = false;
 281                                 const char* pBefore = pattern - 1;
 282
 283                                 if (*pattern == '[') {
 284                                         pattern++;
 285
 286                                         while (!match && *string != '\0') {
 287                                                 match = MatchesBracketExpression(string++, pattern,
 288                                                         caseSensitivity);
 289                                         }
 290
 291                                         while (*pattern != ']' && *pattern != '\0') {
 292                                                 // Skip the rest of the bracket:
 293                                                 pattern++;
 294                                         }
 295
 296                                         if (*pattern == '\0') {
 297                                                 // Failure if no closing bracket;
 298                                                 return false;
 299                                         }
 300                                 } else {
 301                                         // No bracket, just one character:
 302                                         while (!match && *string != '\0') {
 303                                                 if (IsGlyph(string[0]))
 304                                                         match = UTF8CharsAreEqual(string++, pattern);
 305                                                 else {
 306                                                         match = CharsAreEqual(*string++, *pattern,
 307                                                                 caseSensitivity);
 308                                                 }
 309                                         }
 310                                 }
 311
 312                                 if (!match)
 313                                         return false;
 314                                 else {
 315                                         pStorage[patternLevel] = pBefore;
 316                                         if (IsInsideGlyph(string[0]))
 317                                                 string = MoveToEndOfGlyph(string);
 318
 319                                         sStorage[patternLevel++] = string;
 320                                         if (patternLevel > kWildCardMaximum)
 321                                                 return false;
 322
 323                                         pattern++;
 324                                         if (IsInsideGlyph(pattern[0]))
 325                                                 pattern = MoveToEndOfGlyph(pattern);
 326                                 }
 327                                 break;
 328                         }
 329
 330                         case '[':
 331                                 pattern++;
 332
 333                                 if (!MatchesBracketExpression(string, pattern,
 334                                                 caseSensitivity)) {
 335                                         if (patternLevel > 0) {
 336                                                 pattern = pStorage[--patternLevel];
 337                                                 string = sStorage[patternLevel];
 338                                         } else
 339                                                 return false;
 340                                 } else {
 341                                         // Skip the rest of the bracket:
 342                                         while (*pattern != ']' && *pattern != '\0')
 343                                                 pattern++;
 344
 345                                         // Failure if no closing bracket;
 346                                         if (*pattern == '\0')
 347                                                 return false;
 348
 349                                         string++;
 350                                         if (IsInsideGlyph(string[0]))
 351                                                 string = MoveToEndOfGlyph(string);
 352                                         pattern++;
 353                                 }
 354                                 break;
 355
 356                         default:
 357                         {
 358                                 bool equal = false;
 359                                 if (IsGlyph(string[0]))
 360                                         equal = UTF8CharsAreEqual(string, pattern);
 361                                 else
 362                                         equal = CharsAreEqual(*string, *pattern, caseSensitivity);
 363
 364                                 if (equal) {
 365                                         pattern++;
 366                                         if (IsInsideGlyph(pattern[0]))
 367                                                 pattern = MoveToEndOfGlyph(pattern);
 368                                         string++;
 369                                         if (IsInsideGlyph(string[0]))
 370                                                 string = MoveToEndOfGlyph(string);
 371                                 } else if (patternLevel > 0) {
 372                                                 pattern = pStorage[--patternLevel];
 373                                                 string = sStorage[patternLevel];
 374                                 } else
 375                                         return false;
 376                                 break;
 377                         }
 378                 }
 379
 380                 if (*pattern == '\0' && *string != '\0' && patternLevel > 0) {
 381                         pattern = pStorage[--patternLevel];
 382                         string = sStorage[patternLevel];
 383                 }
 384         }
 385
 386         return *string == '\0' && *pattern == '\0';
 387 }
 388
 389
 390 bool
 391 TrackerString::UTF8CharsAreEqual(const char* string1,
 392         const char* string2) const
 393 {
 394         const char* s1 = string1;
 395         const char* s2 = string2;
 396
 397         if (IsStartOfGlyph(*s1) && *s1 == *s2) {
 398                 s1++;
 399                 s2++;
 400
 401                 while (IsInsideGlyph(*s1) && *s1 == *s2) {
 402                         s1++;
 403                         s2++;
 404                 }
 405
 406                 return !IsInsideGlyph(*s1)
 407                         && !IsInsideGlyph(*s2) && *(s1 - 1) == *(s2 - 1);
 408         } else
 409                 return false;
 410 }
 411
 412
 413 const char*
 414 TrackerString::MoveToEndOfGlyph(const char* string) const
 415 {
 416         const char* ptr = string;
 417
 418         while (IsInsideGlyph(*ptr))
 419                 ptr++;
 420
 421         return ptr;
 422 }
 423
 424
 425 bool
 426 TrackerString::IsGlyph(char ch) const
 427 {
 428         return (ch & 0x80) == 0x80;
 429 }
 430
 431
 432 bool
 433 TrackerString::IsInsideGlyph(char ch) const
 434 {
 435         return (ch & 0xC0) == 0x80;
 436 }
 437
 438
 439 bool
 440 TrackerString::IsStartOfGlyph(char ch) const
 441 {
 442         return (ch & 0xC0) == 0xC0;
 443 }