1
// Copyright (c) 2017-2022 Cloudflare, Inc.
2
// Licensed under the Apache 2.0 license found in the LICENSE file or at:
3
//     https://opensource.org/licenses/Apache-2.0
4
//
5
// Adapted from Node.js. Copyright Joyent, Inc. and other Node contributors.
6
//
7
// Permission is hereby granted, free of charge, to any person obtaining a
8
// copy of this software and associated documentation files (the
9
// "Software"), to deal in the Software without restriction, including
10
// without limitation the rights to use, copy, modify, merge, publish,
11
// distribute, sublicense, and/or sell copies of the Software, and to permit
12
// persons to whom the Software is furnished to do so, subject to the
13
// following conditions:
14
//
15
// The above copyright notice and this permission notice shall be included
16
// in all copies or substantial portions of the Software.
17
//
18
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
19
// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
20
// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN
21
// NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM,
22
// DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
23
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE
24
// USE OR OTHER DEALINGS IN THE SOFTWARE.
25
 
26
// Copyright 2011 the V8 project authors. All rights reserved.
27
// Use of this source code is governed by a BSD-style license that can be
28
// found in the LICENSE file.
29
#pragma once
30
 
31
#include <kj/common.h>
32
 
33
#include <cstdint>
34
 
35
using kj::uint;
36
 
37
namespace workerd::api::node {
38
namespace stringsearch {
39
 
40
template <typename T>
41
class Vector {
42
 public:
43
  Vector(T* data, size_t length, bool isForward)
44
      : start_(data),
45
        length_(length),
46
        is_forward_(isForward) {}
47
 
48
  // Returns the start of the memory range.
49
  // For vector v this is NOT necessarily &v[0], see forward().
50
  const T* start() const {
51
    return start_;
52
  }
53
 
54
  // Returns the length of the vector, in characters.
55
  size_t length() const {
56
    return length_;
57
  }
58
 
59
  // Returns true if the Vector is front-to-back, false if back-to-front.
60
  // In the latter case, v[0] corresponds to the *end* of the memory range.
61
  bool forward() const {
62
    return is_forward_;
63
  }
64
 
65
  // Access individual vector elements - checks bounds in debug mode.
66
  T& operator[](size_t index) const {
67
    return start_[is_forward_ ? index : (length_ - index - 1)];
68
  }
69
 
70
 private:
71
  T* start_;
72
  size_t length_;
73
  bool is_forward_;
74
};
75
 
76
//---------------------------------------------------------------------
77
// String Search object.
78
//---------------------------------------------------------------------
79
 
80
// Class holding constants and methods that apply to all string search variants,
81
// independently of subject and pattern char size.
82
class StringSearchBase {
83
 protected:
84
  // Cap on the maximal shift in the Boyer-Moore implementation. By setting a
85
  // limit, we can fix the size of tables. For a needle longer than this limit,
86
  // search will not be optimal, since we only build tables for a suffix
87
  // of the string, but it is a safe approximation.
88
  static const int kBMMaxShift = 250;
89
 
90
  // Reduce alphabet to this size.
91
  // One of the tables used by Boyer-Moore and Boyer-Moore-Horspool has size
92
  // proportional to the input alphabet. We reduce the alphabet size by
93
  // equating input characters modulo a smaller alphabet size. This gives
94
  // a potentially less efficient searching, but is a safe approximation.
95
  // For needles using only characters in the same Unicode 256-code point page,
96
  // there is no search speed degradation.
97
  static const int kLatin1AlphabetSize = 256;
98
  static const int kUC16AlphabetSize = 256;
99
 
100
  // Bad-char shift table stored in the state. It's length is the alphabet size.
101
  // For patterns below this length, the skip length of Boyer-Moore is too short
102
  // to compensate for the algorithmic overhead compared to simple brute force.
103
  static const int kBMMinPatternLength = 8;
104
 
105
  // Store for the BoyerMoore(Horspool) bad char shift table.
106
  int bad_char_shift_table_[kUC16AlphabetSize];
107
  // Store for the BoyerMoore good suffix shift table.
108
  int good_suffix_shift_table_[kBMMaxShift + 1];
109
  // Table used temporarily while building the BoyerMoore good suffix
110
  // shift table.
111
  int suffix_table_[kBMMaxShift + 1];
112
};
113
 
114
template <typename Char>
115
class StringSearch: private StringSearchBase {
116
 public:
117
  using Vector = stringsearch::Vector<const Char>;
118
 
119
  explicit StringSearch(Vector pattern): pattern_(pattern), start_(0) {
120
    if (pattern.length() >= kBMMaxShift) {
121
      start_ = pattern.length() - kBMMaxShift;
122
    }
123
 
124
    size_t pattern_length = pattern_.length();
125
    if (pattern_length < kBMMinPatternLength) {
126
      if (pattern_length == 1) {
127
        strategy_ = SearchStrategy::kSingleChar;
128
        return;
129
      }
130
      strategy_ = SearchStrategy::kLinear;
131
      return;
132
    }
133
    strategy_ = SearchStrategy::kInitial;
134
  }
135
 
136
  size_t Search(Vector subject, size_t index) {
137
    switch (strategy_) {
138
      case kBoyerMooreHorspool:
139
        return BoyerMooreHorspoolSearch(subject, index);
140
      case kBoyerMoore:
141
        return BoyerMooreSearch(subject, index);
142
      case kInitial:
143
        return InitialSearch(subject, index);
144
      case kLinear:
145
        return LinearSearch(subject, index);
146
      case kSingleChar:
147
        return SingleCharSearch(subject, index);
148
    }
149
    __builtin_unreachable();
150
  }
151
 
152
  static inline int AlphabetSize() {
153
    if (sizeof(Char) == 1) {
154
      // Latin1 needle.
155
      return kLatin1AlphabetSize;
156
    } else {
157
      // UC16 needle.
158
      return kUC16AlphabetSize;
159
    }
160
 
161
    static_assert(sizeof(Char) == sizeof(uint8_t) || sizeof(Char) == sizeof(uint16_t),
162
        "sizeof(Char) == sizeof(uint16_t) || sizeof(uint8_t)");
163
  }
164
 
165
 private:
166
  using SearchFunction = size_t (StringSearch::*)(Vector, size_t);
167
  size_t SingleCharSearch(Vector subject, size_t start_index);
168
  size_t LinearSearch(Vector subject, size_t start_index);
169
  size_t InitialSearch(Vector subject, size_t start_index);
170
  size_t BoyerMooreHorspoolSearch(Vector subject, size_t start_index);
171
  size_t BoyerMooreSearch(Vector subject, size_t start_index);
172
 
173
  void PopulateBoyerMooreHorspoolTable();
174
 
175
  void PopulateBoyerMooreTable();
176
 
177
  static inline int CharOccurrence(int* bad_char_occurrence, Char char_code) {
178
    if (sizeof(Char) == 1) {
179
      return bad_char_occurrence[static_cast<uint>(char_code)];
180
    }
181
    // Both pattern and subject are UC16. Reduce character to equivalence class.
182
    uint equiv_class = char_code % kUC16AlphabetSize;
183
    return bad_char_occurrence[equiv_class];
184
  }
185
 
186
  enum SearchStrategy {
187
    kBoyerMooreHorspool,
188
    kBoyerMoore,
189
    kInitial,
190
    kLinear,
191
    kSingleChar,
192
  };
193
 
194
  // The pattern to search for.
195
  Vector pattern_;
196
  SearchStrategy strategy_;
197
  // Cache value of Max(0, pattern_length() - kBMMaxShift)
198
  size_t start_;
199
};
200
 
201
template <typename T, typename U>
202
inline T AlignDown(T value, U alignment) {
203
  return reinterpret_cast<T>((reinterpret_cast<uintptr_t>(value) & ~(alignment - 1)));
204
}
205
 
206
inline uint8_t GetHighestValueByte(uint16_t character) {
207
  return kj::max(static_cast<uint8_t>(character & 0xFF), static_cast<uint8_t>(character >> 8));
208
}
209
 
210
inline uint8_t GetHighestValueByte(uint8_t character) {
211
  return character;
212
}
213
 
214
// Searches for a byte value in a memory buffer, back to front.
215
// Uses memrchr(3) on systems which support it, for speed.
216
// Falls back to a vanilla for loop on non-GNU systems such as Windows.
217
inline const void* MemrchrFill(const void* haystack, uint8_t needle, size_t haystack_len) {
218
#ifdef _GNU_SOURCE
219
  return memrchr(haystack, needle, haystack_len);
220
#else
221
  const uint8_t* haystack8 = static_cast<const uint8_t*>(haystack);
222
  for (size_t i = haystack_len - 1; i != static_cast<size_t>(-1); i--) {
223
    if (haystack8[i] == needle) {
224
      return haystack8 + i;
225
    }
226
  }
227
  return nullptr;
228
#endif
229
}
230
 
231
// Finds the first occurrence of *two-byte* character pattern[0] in the string
232
// `subject`. Does not check that the whole pattern matches.
233
template <typename Char>
234
inline size_t FindFirstCharacter(
235
    Vector<const Char> pattern, Vector<const Char> subject, size_t index) {
236
  const Char pattern_first_char = pattern[0];
237
  const size_t max_n = (subject.length() - pattern.length() + 1);
238
 
239
  // For speed, search for the more `rare` of the two bytes in pattern[0]
240
  // using memchr / memrchr (which are much faster than a simple for loop).
241
  const uint8_t search_byte = GetHighestValueByte(pattern_first_char);
242
  size_t pos = index;
243
  do {
244
    const size_t bytes_to_search = (max_n - pos) * sizeof(Char);
245
    const void* void_pos;
246
    if (subject.forward()) {
247
      // Assert that bytes_to_search won't overflow
248
      void_pos = memchr(subject.start() + pos, search_byte, bytes_to_search);
249
    } else {
250
      void_pos = MemrchrFill(subject.start() + pattern.length() - 1, search_byte, bytes_to_search);
251
    }
252
    const Char* char_pos = static_cast<const Char*>(void_pos);
253
    if (char_pos == nullptr) return subject.length();
254
 
255
    // Then, for each match, verify that the full two bytes match pattern[0].
256
    char_pos = AlignDown(char_pos, sizeof(Char));
257
    size_t raw_pos = static_cast<size_t>(char_pos - subject.start());
258
    pos = subject.forward() ? raw_pos : (subject.length() - raw_pos - 1);
259
    if (subject[pos] == pattern_first_char) {
260
      // Match found, hooray.
261
      return pos;
262
    }
263
    // Search byte matched, but the other byte of pattern[0] didn't. Keep going.
264
  } while (++pos < max_n);
265
 
266
  return subject.length();
267
}
268
 
269
// Finds the first occurrence of the byte pattern[0] in string `subject`.
270
// Does not verify that the whole pattern matches.
271
template <>
272
inline size_t FindFirstCharacter(
273
    Vector<const uint8_t> pattern, Vector<const uint8_t> subject, size_t index) {
274
  const uint8_t pattern_first_char = pattern[0];
275
  const size_t subj_len = subject.length();
276
  const size_t max_n = (subject.length() - pattern.length() + 1);
277
 
278
  const void* pos;
279
  if (subject.forward()) {
280
    pos = memchr(subject.start() + index, pattern_first_char, max_n - index);
281
  } else {
282
    pos = MemrchrFill(subject.start() + pattern.length() - 1, pattern_first_char, max_n - index);
283
  }
284
  const uint8_t* char_pos = static_cast<const uint8_t*>(pos);
285
  if (char_pos == nullptr) {
286
    return subj_len;
287
  }
288
 
289
  size_t raw_pos = static_cast<size_t>(char_pos - subject.start());
290
  return subject.forward() ? raw_pos : (subj_len - raw_pos - 1);
291
}
292
 
293
//---------------------------------------------------------------------
294
// Single Character Pattern Search Strategy
295
//---------------------------------------------------------------------
296
 
297
template <typename Char>
298
size_t StringSearch<Char>::SingleCharSearch(Vector subject, size_t index) {
299
  return FindFirstCharacter(pattern_, subject, index);
300
}
301
 
302
//---------------------------------------------------------------------
303
// Linear Search Strategy
304
//---------------------------------------------------------------------
305
 
306
// Simple linear search for short patterns. Never bails out.
307
template <typename Char>
308
size_t StringSearch<Char>::LinearSearch(Vector subject, size_t index) {
309
  const size_t n = subject.length() - pattern_.length();
310
  for (size_t i = index; i <= n; i++) {
311
    i = FindFirstCharacter(pattern_, subject, i);
312
    if (i == subject.length()) return subject.length();
313
 
314
    bool matches = true;
315
    for (size_t j = 1; j < pattern_.length(); j++) {
316
      if (pattern_[j] != subject[i + j]) {
317
        matches = false;
318
        break;
319
      }
320
    }
321
    if (matches) {
322
      return i;
323
    }
324
  }
325
  return subject.length();
326
}
327
 
328
//---------------------------------------------------------------------
329
// Boyer-Moore string search
330
//---------------------------------------------------------------------
331
 
332
template <typename Char>
333
size_t StringSearch<Char>::BoyerMooreSearch(Vector subject, size_t start_index) {
334
  const size_t subject_length = subject.length();
335
  const size_t pattern_length = pattern_.length();
336
  // Only preprocess at most kBMMaxShift last characters of pattern.
337
  size_t start = start_;
338
 
339
  int* bad_char_occurrence = bad_char_shift_table_;
340
  // Explicitly cast good_suffix_shift_table_ to int* here to avoid a benign UBSan warning.
341
  // good_suffix_shift may point outside of the array, but only indices within the array will
342
  // actually be accessed based on the checks below.
343
  int* good_suffix_shift = static_cast<int*>(good_suffix_shift_table_) - start_;
344
 
345
  Char last_char = pattern_[pattern_length - 1];
346
  size_t index = start_index;
347
  // Continue search from i.
348
  while (index <= subject_length - pattern_length) {
349
    size_t j = pattern_length - 1;
350
    int c;
351
    while (last_char != (c = subject[index + j])) {
352
      int shift = j - CharOccurrence(bad_char_occurrence, c);
353
      index += shift;
354
      if (index > subject_length - pattern_length) {
355
        return subject.length();
356
      }
357
    }
358
    while (pattern_[j] == (c = subject[index + j])) {
359
      if (j == 0) {
360
        return index;
361
      }
362
      j--;
363
    }
364
    if (j < start) {
365
      // we have matched more than our tables allow us to be smart about.
366
      // Fall back on BMH shift.
367
      index += pattern_length - 1 - CharOccurrence(bad_char_occurrence, last_char);
368
    } else {
369
      int gs_shift = good_suffix_shift[j + 1];
370
      int bc_occ = CharOccurrence(bad_char_occurrence, c);
371
      int shift = j - bc_occ;
372
      if (gs_shift > shift) {
373
        shift = gs_shift;
374
      }
375
      index += shift;
376
    }
377
  }
378
 
379
  return subject.length();
380
}
381
 
382
template <typename Char>
383
void StringSearch<Char>::PopulateBoyerMooreTable() {
384
  const size_t pattern_length = pattern_.length();
385
  // Only look at the last kBMMaxShift characters of pattern (from start_
386
  // to pattern_length).
387
  const size_t start = start_;
388
  const size_t length = pattern_length - start;
389
 
390
  // Biased tables so that we can use pattern indices as table indices,
391
  // even if we only cover the part of the pattern from offset start.
392
  // Use explicit int* casts to avoid benign OOB UBsan warnings.
393
  int* shift_table = static_cast<int*>(good_suffix_shift_table_) - start_;
394
  int* suffix_table = static_cast<int*>(suffix_table_) - start_;
395
 
396
  // Initialize table.
397
  for (size_t i = start; i < pattern_length; i++) {
398
    shift_table[i] = length;
399
  }
400
  shift_table[pattern_length] = 1;
401
  suffix_table[pattern_length] = pattern_length + 1;
402
 
403
  if (pattern_length <= start) {
404
    return;
405
  }
406
 
407
  // Find suffixes.
408
  Char last_char = pattern_[pattern_length - 1];
409
  size_t suffix = pattern_length + 1;
410
  {
411
    size_t i = pattern_length;
412
    while (i > start) {
413
      Char c = pattern_[i - 1];
414
      while (suffix <= pattern_length && c != pattern_[suffix - 1]) {
415
        if (static_cast<size_t>(shift_table[suffix]) == length) {
416
          shift_table[suffix] = suffix - i;
417
        }
418
        suffix = suffix_table[suffix];
419
      }
420
      suffix_table[--i] = --suffix;
421
      if (suffix == pattern_length) {
422
        // No suffix to extend, so we check against last_char only.
423
        while ((i > start) && (pattern_[i - 1] != last_char)) {
424
          if (static_cast<size_t>(shift_table[pattern_length]) == length) {
425
            shift_table[pattern_length] = pattern_length - i;
426
          }
427
          suffix_table[--i] = pattern_length;
428
        }
429
        if (i > start) {
430
          suffix_table[--i] = --suffix;
431
        }
432
      }
433
    }
434
  }
435
  // Build shift table using suffixes.
436
  if (suffix < pattern_length) {
437
    for (size_t i = start; i <= pattern_length; i++) {
438
      if (static_cast<size_t>(shift_table[i]) == length) {
439
        shift_table[i] = suffix - start;
440
      }
441
      if (i == suffix) {
442
        suffix = suffix_table[suffix];
443
      }
444
    }
445
  }
446
}
447
 
448
//---------------------------------------------------------------------
449
// Boyer-Moore-Horspool string search.
450
//---------------------------------------------------------------------
451
 
452
template <typename Char>
453
size_t StringSearch<Char>::BoyerMooreHorspoolSearch(Vector subject, size_t start_index) {
454
  const size_t subject_length = subject.length();
455
  const size_t pattern_length = pattern_.length();
456
  int* char_occurrences = bad_char_shift_table_;
457
  int64_t badness = -static_cast<int64_t>(pattern_length);
458
 
459
  // How bad we are doing without a good-suffix table.
460
  Char last_char = pattern_[pattern_length - 1];
461
  int last_char_shift = pattern_length - 1 - CharOccurrence(char_occurrences, last_char);
462
 
463
  // Perform search
464
  size_t index = start_index;  // No matches found prior to this index.
465
  while (index <= subject_length - pattern_length) {
466
    size_t j = pattern_length - 1;
467
    int subject_char;
468
    while (last_char != (subject_char = subject[index + j])) {
469
      int bc_occ = CharOccurrence(char_occurrences, subject_char);
470
      int shift = j - bc_occ;
471
      index += shift;
472
      badness += 1 - shift;  // at most zero, so badness cannot increase.
473
      if (index > subject_length - pattern_length) {
474
        return subject_length;
475
      }
476
    }
477
    j--;
478
    while (pattern_[j] == (subject[index + j])) {
479
      if (j == 0) {
480
        return index;
481
      }
482
      j--;
483
    }
484
    index += last_char_shift;
485
    // Badness increases by the number of characters we have
486
    // checked, and decreases by the number of characters we
487
    // can skip by shifting. It's a measure of how we are doing
488
    // compared to reading each character exactly once.
489
    badness += (pattern_length - j) - last_char_shift;
490
    if (badness > 0) {
491
      PopulateBoyerMooreTable();
492
      strategy_ = SearchStrategy::kBoyerMoore;
493
      return BoyerMooreSearch(subject, index);
494
    }
495
  }
496
  return subject.length();
497
}
498
 
499
template <typename Char>
500
void StringSearch<Char>::PopulateBoyerMooreHorspoolTable() {
501
  const size_t pattern_length = pattern_.length();
502
 
503
  int* bad_char_occurrence = bad_char_shift_table_;
504
 
505
  // Only preprocess at most kBMMaxShift last characters of pattern.
506
  const size_t start = start_;
507
  // Run forwards to populate bad_char_table, so that *last* instance
508
  // of character equivalence class is the one registered.
509
  // Notice: Doesn't include the last character.
510
  const size_t table_size = AlphabetSize();
511
  if (start == 0) {
512
    // All patterns less than kBMMaxShift in length.
513
    kj::arrayPtr(bad_char_occurrence, table_size).fill(-1);
514
  } else {
515
    for (size_t i = 0; i < table_size; i++) {
516
      bad_char_occurrence[i] = start - 1;
517
    }
518
  }
519
  for (size_t i = start; i < pattern_length - 1; i++) {
520
    Char c = pattern_[i];
521
    uint bucket = (sizeof(Char) == 1) ? c : c % AlphabetSize();
522
    bad_char_occurrence[bucket] = i;
523
  }
524
}
525
 
526
//---------------------------------------------------------------------
527
// Linear string search with bailout to BMH.
528
//---------------------------------------------------------------------
529
 
530
// Simple linear search for short patterns, which bails out if the string
531
// isn't found very early in the subject. Upgrades to BoyerMooreHorspool.
532
template <typename Char>
533
size_t StringSearch<Char>::InitialSearch(Vector subject, size_t index) {
534
  const size_t pattern_length = pattern_.length();
535
  // Badness is a count of how much work we have done.  When we have
536
  // done enough work we decide it's probably worth switching to a better
537
  // algorithm.
538
  int64_t badness = -10 - (pattern_length << 2);
539
 
540
  // We know our pattern is at least 2 characters, we cache the first so
541
  // the common case of the first character not matching is faster.
542
  for (size_t i = index, n = subject.length() - pattern_length; i <= n; i++) {
543
    badness++;
544
    if (badness <= 0) {
545
      i = FindFirstCharacter(pattern_, subject, i);
546
      if (i == subject.length()) return subject.length();
547
      size_t j = 1;
548
      do {
549
        if (pattern_[j] != subject[i + j]) {
550
          break;
551
        }
552
        j++;
553
      } while (j < pattern_length);
554
      if (j == pattern_length) {
555
        return i;
556
      }
557
      badness += j;
558
    } else {
559
      PopulateBoyerMooreHorspoolTable();
560
      strategy_ = SearchStrategy::kBoyerMooreHorspool;
561
      return BoyerMooreHorspoolSearch(subject, i);
562
    }
563
  }
564
  return subject.length();
565
}
566
 
567
// Perform a single stand-alone search.
568
// If searching multiple times for the same pattern, a search
569
// object should be constructed once and the Search function then called
570
// for each search.
571
template <typename Char>
572
size_t SearchString(Vector<const Char> subject, Vector<const Char> pattern, size_t start_index) {
573
  StringSearch<Char> search(pattern);
574
  return search.Search(subject, start_index);
575
}
576
}  // namespace stringsearch
577
}  // namespace workerd::api::node
578
 
579
namespace workerd::api::node {
580
 
581
template <typename Char>
582
size_t SearchString(const Char* haystack,
583
    size_t haystack_length,
584
    const Char* needle,
585
    size_t needle_length,
586
    size_t start_index,
587
    bool is_forward) {
588
  if (haystack_length < needle_length) return haystack_length;
589
  // To do a reverse search (lastIndexOf instead of indexOf) without redundant
590
  // code, create two vectors that are reversed views into the input strings.
591
  // For example, v_needle[0] would return the *last* character of the needle.
592
  // So we're searching for the first instance of rev(needle) in rev(haystack)
593
  stringsearch::Vector<const Char> v_needle(needle, needle_length, is_forward);
594
  stringsearch::Vector<const Char> v_haystack(haystack, haystack_length, is_forward);
595
  size_t diff = haystack_length - needle_length;
596
  size_t relative_start_index;
597
  if (is_forward) {
598
    relative_start_index = start_index;
599
  } else if (diff < start_index) {
600
    relative_start_index = 0;
601
  } else {
602
    relative_start_index = diff - start_index;
603
  }
604
  size_t pos = node::stringsearch::SearchString(v_haystack, v_needle, relative_start_index);
605
  if (pos == haystack_length) {
606
    // not found
607
    return pos;
608
  }
609
  return is_forward ? pos : (haystack_length - needle_length - pos);
610
}
611
 
612
template <size_t N>
613
size_t SearchString(const char* haystack, size_t haystack_length, const char (&needle)[N]) {
614
  return SearchString(reinterpret_cast<const uint8_t*>(haystack), haystack_length,
615
      reinterpret_cast<const uint8_t*>(needle), N - 1, 0, true);
616
}
617
 
618
}  // namespace workerd::api::node