string-search.h 19.4 KB
Newer Older
1
// Copyright 2011 the V8 project authors. All rights reserved.
2 3
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
4 5 6 7

#ifndef V8_STRING_SEARCH_H_
#define V8_STRING_SEARCH_H_

8 9 10
#include "src/isolate.h"
#include "src/vector.h"

11 12 13 14
namespace v8 {
namespace internal {


15 16 17 18 19 20 21 22 23 24 25 26
//---------------------------------------------------------------------
// String Search object.
//---------------------------------------------------------------------

// Class holding constants and methods that apply to all string search variants,
// independently of subject and pattern char size.
class StringSearchBase {
 protected:
  // Cap on the maximal shift in the Boyer-Moore implementation. By setting a
  // limit, we can fix the size of tables. For a needle longer than this limit,
  // search will not be optimal, since we only build tables for a suffix
  // of the string, but it is a safe approximation.
27
  static const int kBMMaxShift = Isolate::kBMMaxShift;
28 29 30 31 32 33 34 35

  // Reduce alphabet to this size.
  // One of the tables used by Boyer-Moore and Boyer-Moore-Horspool has size
  // proportional to the input alphabet. We reduce the alphabet size by
  // equating input characters modulo a smaller alphabet size. This gives
  // a potentially less efficient searching, but is a safe approximation.
  // For needles using only characters in the same Unicode 256-code point page,
  // there is no search speed degradation.
36
  static const int kLatin1AlphabetSize = 256;
37
  static const int kUC16AlphabetSize = Isolate::kUC16AlphabetSize;
38 39 40 41 42 43

  // Bad-char shift table stored in the state. It's length is the alphabet size.
  // For patterns below this length, the skip length of Boyer-Moore is too short
  // to compensate for the algorithmic overhead compared to simple brute force.
  static const int kBMMinPatternLength = 7;

44
  static inline bool IsOneByteString(Vector<const uint8_t> string) {
45 46 47
    return true;
  }

48 49
  static inline bool IsOneByteString(Vector<const uc16> string) {
    return String::IsOneByte(string.start(), string.length());
50 51
  }

52
  friend class Isolate;
53 54 55 56 57
};


template <typename PatternChar, typename SubjectChar>
class StringSearch : private StringSearchBase {
58
 public:
59 60 61
  StringSearch(Isolate* isolate, Vector<const PatternChar> pattern)
      : isolate_(isolate),
        pattern_(pattern),
62 63
        start_(Max(0, pattern.length() - kBMMaxShift)) {
    if (sizeof(PatternChar) > sizeof(SubjectChar)) {
64
      if (!IsOneByteString(pattern_)) {
65 66 67 68 69 70 71 72 73 74 75 76
        strategy_ = &FailSearch;
        return;
      }
    }
    int pattern_length = pattern_.length();
    if (pattern_length < kBMMinPatternLength) {
      if (pattern_length == 1) {
        strategy_ = &SingleCharSearch;
        return;
      }
      strategy_ = &LinearSearch;
      return;
77
    }
78
    strategy_ = &InitialSearch;
79
  }
80 81 82

  int Search(Vector<const SubjectChar> subject, int index) {
    return strategy_(this, subject, index);
83
  }
84 85 86

  static inline int AlphabetSize() {
    if (sizeof(PatternChar) == 1) {
87 88
      // Latin1 needle.
      return kLatin1AlphabetSize;
89
    } else {
90
      DCHECK_EQ(sizeof(PatternChar), 2);
91 92 93
      // UC16 needle.
      return kUC16AlphabetSize;
    }
94
  }
95

96
 private:
97 98 99 100 101 102 103 104 105 106
  typedef int (*SearchFunction)(  // NOLINT - it's not a cast!
      StringSearch<PatternChar, SubjectChar>*,
      Vector<const SubjectChar>,
      int);

  static int FailSearch(StringSearch<PatternChar, SubjectChar>*,
                        Vector<const SubjectChar>,
                        int) {
    return -1;
  }
107

108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132
  static int SingleCharSearch(StringSearch<PatternChar, SubjectChar>* search,
                              Vector<const SubjectChar> subject,
                              int start_index);

  static int LinearSearch(StringSearch<PatternChar, SubjectChar>* search,
                          Vector<const SubjectChar> subject,
                          int start_index);

  static int InitialSearch(StringSearch<PatternChar, SubjectChar>* search,
                           Vector<const SubjectChar> subject,
                           int start_index);

  static int BoyerMooreHorspoolSearch(
      StringSearch<PatternChar, SubjectChar>* search,
      Vector<const SubjectChar> subject,
      int start_index);

  static int BoyerMooreSearch(StringSearch<PatternChar, SubjectChar>* search,
                              Vector<const SubjectChar> subject,
                              int start_index);

  void PopulateBoyerMooreHorspoolTable();

  void PopulateBoyerMooreTable();

133 134 135 136 137 138 139 140
  static inline bool exceedsOneByte(uint8_t c) {
    return false;
  }

  static inline bool exceedsOneByte(uint16_t c) {
    return c > String::kMaxOneByteCharCodeU;
  }

141 142 143 144 145 146
  static inline int CharOccurrence(int* bad_char_occurrence,
                                   SubjectChar char_code) {
    if (sizeof(SubjectChar) == 1) {
      return bad_char_occurrence[static_cast<int>(char_code)];
    }
    if (sizeof(PatternChar) == 1) {
147
      if (exceedsOneByte(char_code)) {
148 149
        return -1;
      }
150
      return bad_char_occurrence[static_cast<unsigned int>(char_code)];
151
    }
152
    // Both pattern and subject are UC16. Reduce character to equivalence class.
153 154 155 156
    int equiv_class = char_code % kUC16AlphabetSize;
    return bad_char_occurrence[equiv_class];
  }

157 158 159 160 161
  // The following tables are shared by all searches.
  // TODO(lrn): Introduce a way for a pattern to keep its tables
  // between searches (e.g., for an Atom RegExp).

  // Store for the BoyerMoore(Horspool) bad char shift table.
162 163 164
  // Return a table covering the last kBMMaxShift+1 positions of
  // pattern.
  int* bad_char_table() {
165
    return isolate_->bad_char_shift_table();
166 167
  }

168
  // Store for the BoyerMoore good suffix shift table.
169 170 171
  int* good_suffix_shift_table() {
    // Return biased pointer that maps the range  [start_..pattern_.length()
    // to the kGoodSuffixShiftTable array.
172
    return isolate_->good_suffix_shift_table() - start_;
173 174
  }

175 176
  // Table used temporarily while building the BoyerMoore good suffix
  // shift table.
177 178 179
  int* suffix_table() {
    // Return biased pointer that maps the range  [start_..pattern_.length()
    // to the kSuffixTable array.
180
    return isolate_->suffix_table() - start_;
181 182
  }

183
  Isolate* isolate_;
184 185 186 187 188 189
  // The pattern to search for.
  Vector<const PatternChar> pattern_;
  // Pointer to implementation of the search.
  SearchFunction strategy_;
  // Cache value of Max(0, pattern_length() - kBMMaxShift)
  int start_;
190 191 192
};


193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
template <typename T, typename U>
inline T AlignDown(T value, U alignment) {
  return reinterpret_cast<T>(
      (reinterpret_cast<uintptr_t>(value) & ~(alignment - 1)));
}


inline uint8_t GetHighestValueByte(uc16 character) {
  return Max(static_cast<uint8_t>(character & 0xFF),
             static_cast<uint8_t>(character >> 8));
}


inline uint8_t GetHighestValueByte(uint8_t character) { return character; }


209
template <typename PatternChar, typename SubjectChar>
210 211 212
inline int FindFirstCharacter(Vector<const PatternChar> pattern,
                              Vector<const SubjectChar> subject, int index) {
  const PatternChar pattern_first_char = pattern[0];
213 214
  const int max_n = (subject.length() - pattern.length() + 1);

215 216 217 218 219
  const uint8_t search_byte = GetHighestValueByte(pattern_first_char);
  const SubjectChar search_char = static_cast<SubjectChar>(pattern_first_char);
  int pos = index;
  do {
    DCHECK_GE(max_n - pos, 0);
220
    const SubjectChar* char_pos = reinterpret_cast<const SubjectChar*>(
221 222
        memchr(subject.start() + pos, search_byte,
               (max_n - pos) * sizeof(SubjectChar)));
223
    if (char_pos == nullptr) return -1;
224 225 226 227 228
    char_pos = AlignDown(char_pos, sizeof(SubjectChar));
    pos = static_cast<int>(char_pos - subject.start());
    if (subject[pos] == search_char) return pos;
  } while (++pos < max_n);

229 230 231 232
  return -1;
}


233 234 235
//---------------------------------------------------------------------
// Single Character Pattern Search Strategy
//---------------------------------------------------------------------
236

237 238 239 240 241
template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::SingleCharSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    Vector<const SubjectChar> subject,
    int index) {
242
  DCHECK_EQ(1, search->pattern_.length());
243
  PatternChar pattern_first_char = search->pattern_[0];
244 245 246
  if (sizeof(PatternChar) > sizeof(SubjectChar)) {
    if (exceedsOneByte(pattern_first_char)) {
      return -1;
247 248
    }
  }
249
  return FindFirstCharacter(search->pattern_, subject, index);
250 251 252 253 254 255 256 257
}

//---------------------------------------------------------------------
// Linear Search Strategy
//---------------------------------------------------------------------


template <typename PatternChar, typename SubjectChar>
258 259 260
inline bool CharCompare(const PatternChar* pattern,
                        const SubjectChar* subject,
                        int length) {
261
  DCHECK_GT(length, 0);
262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
  int pos = 0;
  do {
    if (pattern[pos] != subject[pos]) {
      return false;
    }
    pos++;
  } while (pos < length);
  return true;
}


// Simple linear search for short patterns. Never bails out.
template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::LinearSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    Vector<const SubjectChar> subject,
    int index) {
  Vector<const PatternChar> pattern = search->pattern_;
280
  DCHECK_GT(pattern.length(), 1);
281 282 283 284
  int pattern_length = pattern.length();
  int i = index;
  int n = subject.length() - pattern_length;
  while (i <= n) {
285 286 287 288
    i = FindFirstCharacter(pattern, subject, i);
    if (i == -1) return -1;
    DCHECK_LE(i, n);
    i++;
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337
    // Loop extracted to separate function to allow using return to do
    // a deeper break.
    if (CharCompare(pattern.start() + 1,
                    subject.start() + i,
                    pattern_length - 1)) {
      return i - 1;
    }
  }
  return -1;
}

//---------------------------------------------------------------------
// Boyer-Moore string search
//---------------------------------------------------------------------

template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    Vector<const SubjectChar> subject,
    int start_index) {
  Vector<const PatternChar> pattern = search->pattern_;
  int subject_length = subject.length();
  int pattern_length = pattern.length();
  // Only preprocess at most kBMMaxShift last characters of pattern.
  int start = search->start_;

  int* bad_char_occurence = search->bad_char_table();
  int* good_suffix_shift = search->good_suffix_shift_table();

  PatternChar last_char = pattern[pattern_length - 1];
  int index = start_index;
  // Continue search from i.
  while (index <= subject_length - pattern_length) {
    int j = pattern_length - 1;
    int c;
    while (last_char != (c = subject[index + j])) {
      int shift =
          j - CharOccurrence(bad_char_occurence, c);
      index += shift;
      if (index > subject_length - pattern_length) {
        return -1;
      }
    }
    while (j >= 0 && pattern[j] == (c = subject[index + j])) j--;
    if (j < 0) {
      return index;
    } else if (j < start) {
      // we have matched more than our tables allow us to be smart about.
      // Fall back on BMH shift.
338 339 340
      index += pattern_length - 1
          - CharOccurrence(bad_char_occurence,
                           static_cast<SubjectChar>(last_char));
341 342 343 344 345 346 347 348 349 350
    } else {
      int gs_shift = good_suffix_shift[j + 1];
      int bc_occ =
          CharOccurrence(bad_char_occurence, c);
      int shift = j - bc_occ;
      if (gs_shift > shift) {
        shift = gs_shift;
      }
      index += shift;
    }
351
  }
352 353

  return -1;
354 355 356
}


357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376
template <typename PatternChar, typename SubjectChar>
void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() {
  int pattern_length = pattern_.length();
  const PatternChar* pattern = pattern_.start();
  // Only look at the last kBMMaxShift characters of pattern (from start_
  // to pattern_length).
  int start = start_;
  int length = pattern_length - start;

  // Biased tables so that we can use pattern indices as table indices,
  // even if we only cover the part of the pattern from offset start.
  int* shift_table = good_suffix_shift_table();
  int* suffix_table = this->suffix_table();

  // Initialize table.
  for (int i = start; i < pattern_length; i++) {
    shift_table[i] = length;
  }
  shift_table[pattern_length] = 1;
  suffix_table[pattern_length] = pattern_length + 1;
377

378 379 380 381
  if (pattern_length <= start) {
    return;
  }

382 383 384
  // Find suffixes.
  PatternChar last_char = pattern[pattern_length - 1];
  int suffix = pattern_length + 1;
385
  {
386
    int i = pattern_length;
387 388
    while (i > start) {
      PatternChar c = pattern[i - 1];
389 390 391
      while (suffix <= pattern_length && c != pattern[suffix - 1]) {
        if (shift_table[suffix] == length) {
          shift_table[suffix] = suffix - i;
392
        }
393
        suffix = suffix_table[suffix];
394
      }
395 396
      suffix_table[--i] = --suffix;
      if (suffix == pattern_length) {
397 398
        // No suffix to extend, so we check against last_char only.
        while ((i > start) && (pattern[i - 1] != last_char)) {
399 400
          if (shift_table[pattern_length] == length) {
            shift_table[pattern_length] = pattern_length - i;
401
          }
402
          suffix_table[--i] = pattern_length;
403 404
        }
        if (i > start) {
405
          suffix_table[--i] = --suffix;
406 407 408 409
        }
      }
    }
  }
410 411 412 413 414
  // Build shift table using suffixes.
  if (suffix < pattern_length) {
    for (int i = start; i <= pattern_length; i++) {
      if (shift_table[i] == length) {
        shift_table[i] = suffix - start;
415 416
      }
      if (i == suffix) {
417
        suffix = suffix_table[suffix];
418 419 420 421 422
      }
    }
  }
}

423 424 425
//---------------------------------------------------------------------
// Boyer-Moore-Horspool string search.
//---------------------------------------------------------------------
426

427 428 429 430 431 432 433 434 435 436
template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::BoyerMooreHorspoolSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    Vector<const SubjectChar> subject,
    int start_index) {
  Vector<const PatternChar> pattern = search->pattern_;
  int subject_length = subject.length();
  int pattern_length = pattern.length();
  int* char_occurrences = search->bad_char_table();
  int badness = -pattern_length;
437 438

  // How bad we are doing without a good-suffix table.
439 440
  PatternChar last_char = pattern[pattern_length - 1];
  int last_char_shift = pattern_length - 1 -
441
      CharOccurrence(char_occurrences, static_cast<SubjectChar>(last_char));
442
  // Perform search
443 444 445 446 447 448
  int index = start_index;  // No matches found prior to this index.
  while (index <= subject_length - pattern_length) {
    int j = pattern_length - 1;
    int subject_char;
    while (last_char != (subject_char = subject[index + j])) {
      int bc_occ = CharOccurrence(char_occurrences, subject_char);
449
      int shift = j - bc_occ;
450
      index += shift;
451
      badness += 1 - shift;  // at most zero, so badness cannot increase.
452
      if (index > subject_length - pattern_length) {
453 454 455 456
        return -1;
      }
    }
    j--;
457
    while (j >= 0 && pattern[j] == (subject[index + j])) j--;
458
    if (j < 0) {
459
      return index;
460
    } else {
461
      index += last_char_shift;
462 463 464 465
      // Badness increases by the number of characters we have
      // checked, and decreases by the number of characters we
      // can skip by shifting. It's a measure of how we are doing
      // compared to reading each character exactly once.
466
      badness += (pattern_length - j) - last_char_shift;
467
      if (badness > 0) {
468 469 470
        search->PopulateBoyerMooreTable();
        search->strategy_ = &BoyerMooreSearch;
        return BoyerMooreSearch(search, subject, index);
471 472 473 474 475 476 477
      }
    }
  }
  return -1;
}


478 479 480
template <typename PatternChar, typename SubjectChar>
void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() {
  int pattern_length = pattern_.length();
481

482 483 484 485 486 487 488 489 490 491 492 493 494 495 496
  int* bad_char_occurrence = bad_char_table();

  // Only preprocess at most kBMMaxShift last characters of pattern.
  int start = start_;
  // Run forwards to populate bad_char_table, so that *last* instance
  // of character equivalence class is the one registered.
  // Notice: Doesn't include the last character.
  int table_size = AlphabetSize();
  if (start == 0) {  // All patterns less than kBMMaxShift in length.
    memset(bad_char_occurrence,
           -1,
           table_size * sizeof(*bad_char_occurrence));
  } else {
    for (int i = 0; i < table_size; i++) {
      bad_char_occurrence[i] = start - 1;
497 498
    }
  }
499 500 501 502 503
  for (int i = start; i < pattern_length - 1; i++) {
    PatternChar c = pattern_[i];
    int bucket = (sizeof(PatternChar) == 1) ? c : c % AlphabetSize();
    bad_char_occurrence[bucket] = i;
  }
504 505
}

506 507 508
//---------------------------------------------------------------------
// Linear string search with bailout to BMH.
//---------------------------------------------------------------------
509

510 511
// Simple linear search for short patterns, which bails out if the string
// isn't found very early in the subject. Upgrades to BoyerMooreHorspool.
512
template <typename PatternChar, typename SubjectChar>
513 514 515 516 517
int StringSearch<PatternChar, SubjectChar>::InitialSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    Vector<const SubjectChar> subject,
    int index) {
  Vector<const PatternChar> pattern = search->pattern_;
518 519 520 521 522 523 524 525
  int pattern_length = pattern.length();
  // Badness is a count of how much work we have done.  When we have
  // done enough work we decide it's probably worth switching to a better
  // algorithm.
  int badness = -10 - (pattern_length << 2);

  // We know our pattern is at least 2 characters, we cache the first so
  // the common case of the first character not matching is faster.
526
  for (int i = index, n = subject.length() - pattern_length; i <= n; i++) {
527
    badness++;
528
    if (badness <= 0) {
529 530 531
      i = FindFirstCharacter(pattern, subject, i);
      if (i == -1) return -1;
      DCHECK_LE(i, n);
532 533 534 535 536 537 538 539 540
      int j = 1;
      do {
        if (pattern[j] != subject[i + j]) {
          break;
        }
        j++;
      } while (j < pattern_length);
      if (j == pattern_length) {
        return i;
541
      }
542
      badness += j;
543
    } else {
544 545 546
      search->PopulateBoyerMooreHorspoolTable();
      search->strategy_ = &BoyerMooreHorspoolSearch;
      return BoyerMooreHorspoolSearch(search, subject, i);
547 548 549 550 551 552
    }
  }
  return -1;
}


553 554 555 556
// Perform a a single stand-alone search.
// If searching multiple times for the same pattern, a search
// object should be constructed once and the Search function then called
// for each search.
557
template <typename SubjectChar, typename PatternChar>
558 559 560 561
int SearchString(Isolate* isolate,
                 Vector<const SubjectChar> subject,
                 Vector<const PatternChar> pattern,
                 int start_index) {
562
  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
563
  return search.Search(subject, start_index);
564 565
}

566 567 568 569
// A wrapper function around SearchString that wraps raw pointers to the subject
// and pattern as vectors before calling SearchString. Used from the
// StringIndexOf builtin.
template <typename SubjectChar, typename PatternChar>
570 571 572
intptr_t SearchStringRaw(Isolate* isolate, const SubjectChar* subject_ptr,
                         int subject_length, const PatternChar* pattern_ptr,
                         int pattern_length, int start_index) {
573 574 575 576 577 578
  DisallowHeapAllocation no_gc;
  Vector<const SubjectChar> subject(subject_ptr, subject_length);
  Vector<const PatternChar> pattern(pattern_ptr, pattern_length);
  return SearchString(isolate, subject, pattern, start_index);
}

579 580
}  // namespace internal
}  // namespace v8
581 582

#endif  // V8_STRING_SEARCH_H_