/src/capnproto/c++/src/kj/string.c++

Source (jump to first uncovered line)
// Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
// Licensed under the MIT License:
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// in the Software without restriction, including without limitation the rights
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
// copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
// THE SOFTWARE.

#include "string.h"
#include "debug.h"
#include <stdio.h>
#include <float.h>
#include <errno.h>
#include <stdlib.h>
#include <stdint.h>
#if !defined(_WIN32)
#include <string.h>
#endif

namespace kj {

namespace {
bool isHex(const char *s) {
  if (*s == '-') s++;
  return s[0] == '0' && (s[1] == 'x' || s[1] == 'X');
}

long long parseSigned(const StringPtr& s, long long min, long long max) {
  KJ_REQUIRE(s != nullptr, "String does not contain valid number", s) { return 0; }
  char *endPtr;
  errno = 0;
  auto value = strtoll(s.begin(), &endPtr, isHex(s.cStr()) ? 16 : 10);
  KJ_REQUIRE(endPtr == s.end(), "String does not contain valid number", s) { return 0; }
  KJ_REQUIRE(errno != ERANGE, "Value out-of-range", s) { return 0; }
  KJ_REQUIRE(value >= min && value <= max, "Value out-of-range", value, min, max) { return 0; }
  return value;
}

Maybe<long long> tryParseSigned(const StringPtr& s, long long min, long long max) {
  if (s == nullptr) { return kj::none; } // String does not contain valid number.
  char *endPtr;
  errno = 0;
  auto value = strtoll(s.begin(), &endPtr, isHex(s.cStr()) ? 16 : 10);
  if (endPtr != s.end() || errno == ERANGE || value < min || max < value) {
    return kj::none;
  }
  return value;
}

unsigned long long parseUnsigned(const StringPtr& s, unsigned long long max) {
  KJ_REQUIRE(s != nullptr, "String does not contain valid number", s) { return 0; }
  char *endPtr;
  errno = 0;
  auto value = strtoull(s.begin(), &endPtr, isHex(s.cStr()) ? 16 : 10);
  KJ_REQUIRE(endPtr == s.end(), "String does not contain valid number", s) { return 0; }
  KJ_REQUIRE(errno != ERANGE, "Value out-of-range", s) { return 0; }
  KJ_REQUIRE(value <= max, "Value out-of-range", value, max) { return 0; }
  //strtoull("-1") does not fail with ERANGE
  KJ_REQUIRE(s[0] != '-', "Value out-of-range", s) { return 0; }
  return value;
}

Maybe<unsigned long long> tryParseUnsigned(const StringPtr& s, unsigned long long max) {
  if (s == nullptr) { return kj::none; } // String does not contain valid number.
  char *endPtr;
  errno = 0;
  auto value = strtoull(s.begin(), &endPtr, isHex(s.cStr()) ? 16 : 10);
  if (endPtr != s.end() || errno == ERANGE || max < value || s[0] == '-') { return kj::none; }
  return value;
}

template <typename T>
T parseInteger(const StringPtr& s) {
  if (static_cast<T>(minValue) < 0) {
    long long min = static_cast<T>(minValue);
    long long max = static_cast<T>(maxValue);
    return static_cast<T>(parseSigned(s, min, max));
  } else {
    unsigned long long max = static_cast<T>(maxValue);
    return static_cast<T>(parseUnsigned(s, max));
  }
}

template <typename T>
Maybe<T> tryParseInteger(const StringPtr& s) {
  if (static_cast<T>(minValue) < 0) {
    long long min = static_cast<T>(minValue);
    long long max = static_cast<T>(maxValue);
    return static_cast<Maybe<T>>(tryParseSigned(s, min, max));
  } else {
    unsigned long long max = static_cast<T>(maxValue);
    return static_cast<Maybe<T>>(tryParseUnsigned(s, max));
  }
}

} // namespace

#define PARSE_AS_INTEGER(T) \
    template <> T StringPtr::parseAs<T>() const { return parseInteger<T>(*this); }
PARSE_AS_INTEGER(char);
PARSE_AS_INTEGER(signed char);
PARSE_AS_INTEGER(unsigned char);
PARSE_AS_INTEGER(short);
PARSE_AS_INTEGER(unsigned short);
PARSE_AS_INTEGER(int);
PARSE_AS_INTEGER(unsigned int);
PARSE_AS_INTEGER(long);
PARSE_AS_INTEGER(unsigned long);
PARSE_AS_INTEGER(long long);
PARSE_AS_INTEGER(unsigned long long);
#undef PARSE_AS_INTEGER

#define TRY_PARSE_AS_INTEGER(T) \
    template <> Maybe<T> StringPtr::tryParseAs<T>() const { return tryParseInteger<T>(*this); }
TRY_PARSE_AS_INTEGER(char);
TRY_PARSE_AS_INTEGER(signed char);
TRY_PARSE_AS_INTEGER(unsigned char);
TRY_PARSE_AS_INTEGER(short);
TRY_PARSE_AS_INTEGER(unsigned short);
TRY_PARSE_AS_INTEGER(int);
TRY_PARSE_AS_INTEGER(unsigned int);
TRY_PARSE_AS_INTEGER(long);
TRY_PARSE_AS_INTEGER(unsigned long);
TRY_PARSE_AS_INTEGER(long long);
TRY_PARSE_AS_INTEGER(unsigned long long);
#undef TRY_PARSE_AS_INTEGER

String heapString(size_t size) {
  char* buffer = _::HeapArrayDisposer::allocate<char>(size + 1);
  buffer[size] = '\0';
  return String(buffer, size, _::HeapArrayDisposer::instance);
}

String heapString(const char* value, size_t size) {
  char* buffer = _::HeapArrayDisposer::allocate<char>(size + 1);
  if (size != 0u) {
    memcpy(buffer, value, size);
  }
  buffer[size] = '\0';
  return String(buffer, size, _::HeapArrayDisposer::instance);
}

template <typename T>
static CappedArray<char, sizeof(T) * 2 + 1> hexImpl(T i) {
  // We don't use sprintf() because it's not async-signal-safe (for strPreallocated()).
  CappedArray<char, sizeof(T) * 2 + 1> result;
  uint8_t reverse[sizeof(T) * 2];
  uint8_t* p = reverse;
  if (i == 0) {
    *p++ = 0;
  } else {
    while (i > 0) {
      *p++ = i % 16;
      i /= 16;
    }
  }

  char* p2 = result.begin();
  while (p > reverse) {
    *p2++ = "0123456789abcdef"[*--p];
  }
  result.setSize(p2 - result.begin());
  return result;
}

#define HEXIFY_INT(type) \
CappedArray<char, sizeof(type) * 2 + 1> hex(type i) { \
  return hexImpl<type>(i); \
}

HEXIFY_INT(unsigned char);
HEXIFY_INT(unsigned short);
HEXIFY_INT(unsigned int);
HEXIFY_INT(unsigned long);
HEXIFY_INT(unsigned long long);

#undef HEXIFY_INT

namespace _ {  // private

StringPtr Stringifier::operator*(decltype(nullptr)) const {
  return "nullptr";
}

StringPtr Stringifier::operator*(bool b) const {
  return b ? StringPtr("true") : StringPtr("false");
}

template <typename T, typename Unsigned>
static CappedArray<char, sizeof(T) * 3 + 2> stringifyImpl(T i) {
  // We don't use sprintf() because it's not async-signal-safe (for strPreallocated()).
  CappedArray<char, sizeof(T) * 3 + 2> result;
  bool negative = i < 0;
  // Note that if `i` is the most-negative value, negating it produces the same bit value. But
  // since it's a signed integer, this is considered an overflow. We therefore must make it
  // unsigned first, then negate it, to avoid ubsan complaining.
  Unsigned u = i;
  if (negative) u = -u;
  uint8_t reverse[sizeof(T) * 3 + 1];
  uint8_t* p = reverse;
  if (u == 0) {
    *p++ = 0;
  } else {
    while (u > 0) {
      *p++ = u % 10;
      u /= 10;
    }
  }

  char* p2 = result.begin();
  if (negative) *p2++ = '-';
  while (p > reverse) {
    *p2++ = '0' + *--p;
  }
  result.setSize(p2 - result.begin());
  return result;
}

#define STRINGIFY_INT(type, unsigned) \
CappedArray<char, sizeof(type) * 3 + 2> Stringifier::operator*(type i) const { \
  return stringifyImpl<type, unsigned>(i); \
}

STRINGIFY_INT(signed char, uint);
STRINGIFY_INT(unsigned char, uint);
STRINGIFY_INT(short, uint);
STRINGIFY_INT(unsigned short, uint);
STRINGIFY_INT(int, uint);
STRINGIFY_INT(unsigned int, uint);
STRINGIFY_INT(long, unsigned long);
STRINGIFY_INT(unsigned long, unsigned long);
STRINGIFY_INT(long long, unsigned long long);
STRINGIFY_INT(unsigned long long, unsigned long long);

#undef STRINGIFY_INT

CappedArray<char, sizeof(const void*) * 2 + 1> Stringifier::operator*(const void* i) const { \
  return hexImpl<uintptr_t>(reinterpret_cast<uintptr_t>(i));
}

namespace {

// ----------------------------------------------------------------------
// DoubleToBuffer()
// FloatToBuffer()
//    Copied from Protocol Buffers, (C) Google, BSD license.
//    Kenton wrote this code originally.  The following commentary is
//    from the original.
//
//    Description: converts a double or float to a string which, if
//    passed to NoLocaleStrtod(), will produce the exact same original double
//    (except in case of NaN; all NaNs are considered the same value).
//    We try to keep the string short but it's not guaranteed to be as
//    short as possible.
//
//    DoubleToBuffer() and FloatToBuffer() write the text to the given
//    buffer and return it.  The buffer must be at least
//    kDoubleToBufferSize bytes for doubles and kFloatToBufferSize
//    bytes for floats.  kFastToBufferSize is also guaranteed to be large
//    enough to hold either.
//
//    We want to print the value without losing precision, but we also do
//    not want to print more digits than necessary.  This turns out to be
//    trickier than it sounds.  Numbers like 0.2 cannot be represented
//    exactly in binary.  If we print 0.2 with a very large precision,
//    e.g. "%.50g", we get "0.2000000000000000111022302462515654042363167".
//    On the other hand, if we set the precision too low, we lose
//    significant digits when printing numbers that actually need them.
//    It turns out there is no precision value that does the right thing
//    for all numbers.
//
//    Our strategy is to first try printing with a precision that is never
//    over-precise, then parse the result with strtod() to see if it
//    matches.  If not, we print again with a precision that will always
//    give a precise result, but may use more digits than necessary.
//
//    An arguably better strategy would be to use the algorithm described
//    in "How to Print Floating-Point Numbers Accurately" by Steele &
//    White, e.g. as implemented by David M. Gay's dtoa().  It turns out,
//    however, that the following implementation is about as fast as
//    DMG's code.  Furthermore, DMG's code locks mutexes, which means it
//    will not scale well on multi-core machines.  DMG's code is slightly
//    more accurate (in that it will never use more digits than
//    necessary), but this is probably irrelevant for most users.
//
//    Rob Pike and Ken Thompson also have an implementation of dtoa() in
//    third_party/fmt/fltfmt.cc.  Their implementation is similar to this
//    one in that it makes guesses and then uses strtod() to check them.
//    Their implementation is faster because they use their own code to
//    generate the digits in the first place rather than use snprintf(),
//    thus avoiding format string parsing overhead.  However, this makes
//    it considerably more complicated than the following implementation,
//    and it is embedded in a larger library.  If speed turns out to be
//    an issue, we could re-implement this in terms of their
//    implementation.
// ----------------------------------------------------------------------

#ifdef _WIN32
// MSVC has only _snprintf, not snprintf.
//
// MinGW has both snprintf and _snprintf, but they appear to be different
// functions.  The former is buggy.  When invoked like so:
//   char buffer[32];
//   snprintf(buffer, 32, "%.*g\n", FLT_DIG, 1.23e10f);
// it prints "1.23000e+10".  This is plainly wrong:  %g should never print
// trailing zeros after the decimal point.  For some reason this bug only
// occurs with some input values, not all.  In any case, _snprintf does the
// right thing, so we use it.
#define snprintf _snprintf
#endif

inline bool IsNaN(double value) {
  // NaN is never equal to anything, even itself.
  return value != value;
}

// In practice, doubles should never need more than 24 bytes and floats
// should never need more than 14 (including null terminators), but we
// overestimate to be safe.
static const int kDoubleToBufferSize = 32;
static const int kFloatToBufferSize = 24;

static inline bool IsValidFloatChar(char c) {
  return ('0' <= c && c <= '9') ||
         c == 'e' || c == 'E' ||
         c == '+' || c == '-';
}

void DelocalizeRadix(char* buffer) {
  // Fast check:  if the buffer has a normal decimal point, assume no
  // translation is needed.
  if (strchr(buffer, '.') != NULL) return;

  // Find the first unknown character.
  while (IsValidFloatChar(*buffer)) ++buffer;

  if (*buffer == '\0') {
    // No radix character found.
    return;
  }

  // We are now pointing at the locale-specific radix character.  Replace it
  // with '.'.
  *buffer = '.';
  ++buffer;

  if (!IsValidFloatChar(*buffer) && *buffer != '\0') {
    // It appears the radix was a multi-byte character.  We need to remove the
    // extra bytes.
    char* target = buffer;
    do { ++buffer; } while (!IsValidFloatChar(*buffer) && *buffer != '\0');
    memmove(target, buffer, strlen(buffer) + 1);
  }
}

void RemovePlus(char* buffer) {
  // Remove any + characters because they are redundant and ugly.

  for (;;) {
    buffer = strchr(buffer, '+');
    if (buffer == NULL) {
      return;
    }
    memmove(buffer, buffer + 1, strlen(buffer + 1) + 1);
  }
}

#if _WIN32
void RemoveE0(char* buffer) {
  // Remove redundant leading 0's after an e, e.g. 1e012. Seems to appear on
  // Windows.

  // Find and skip 'e'.
  char* ptr = strchr(buffer, 'e');
  if (ptr == nullptr) return;
  ++ptr;

  // Skip '-'.
  if (*ptr == '-') ++ptr;

  // Skip '0's.
  char* ptr2 = ptr;
  while (*ptr2 == '0') ++ptr2;

  // If we went past the last digit, back up one.
  if (*ptr2 < '0' || *ptr2 > '9') --ptr2;

  // Move bytes backwards.
  if (ptr2 > ptr) {
    memmove(ptr, ptr2, strlen(ptr2) + 1);
  }
}
#endif

char* DoubleToBuffer(double value, char* buffer) {
  // DBL_DIG is 15 for IEEE-754 doubles, which are used on almost all
  // platforms these days.  Just in case some system exists where DBL_DIG
  // is significantly larger -- and risks overflowing our buffer -- we have
  // this assert.
  static_assert(DBL_DIG < 20, "DBL_DIG is too big.");

  if (value == inf()) {
    strcpy(buffer, "inf");
    return buffer;
  } else if (value == -inf()) {
    strcpy(buffer, "-inf");
    return buffer;
  } else if (IsNaN(value)) {
    strcpy(buffer, "nan");
    return buffer;
  }

  int snprintf_result KJ_UNUSED =
    snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG, value);

  // The snprintf should never overflow because the buffer is significantly
  // larger than the precision we asked for.
  KJ_DASSERT(snprintf_result > 0 && snprintf_result < kDoubleToBufferSize);

  // We need to make parsed_value volatile in order to force the compiler to
  // write it out to the stack.  Otherwise, it may keep the value in a
  // register, and if it does that, it may keep it as a long double instead
  // of a double.  This long double may have extra bits that make it compare
  // unequal to "value" even though it would be exactly equal if it were
  // truncated to a double.
  volatile double parsed_value = strtod(buffer, NULL);
  if (parsed_value != value) {
    int snprintf_result2 KJ_UNUSED =
      snprintf(buffer, kDoubleToBufferSize, "%.*g", DBL_DIG+2, value);

    // Should never overflow; see above.
    KJ_DASSERT(snprintf_result2 > 0 && snprintf_result2 < kDoubleToBufferSize);
  }

  DelocalizeRadix(buffer);
  RemovePlus(buffer);
#if _WIN32
  RemoveE0(buffer);
#endif // _WIN32
  return buffer;
}

bool safe_strtof(const char* str, float* value) {
  char* endptr;
  errno = 0;  // errno only gets set on errors
#if defined(_WIN32) || defined (__hpux)  // has no strtof()
  *value = static_cast<float>(strtod(str, &endptr));
#else
  *value = strtof(str, &endptr);
#endif
  return *str != 0 && *endptr == 0 && errno == 0;
}

char* FloatToBuffer(float value, char* buffer) {
  // FLT_DIG is 6 for IEEE-754 floats, which are used on almost all
  // platforms these days.  Just in case some system exists where FLT_DIG
  // is significantly larger -- and risks overflowing our buffer -- we have
  // this assert.
  static_assert(FLT_DIG < 10, "FLT_DIG is too big");

  if (value == inf()) {
    strcpy(buffer, "inf");
    return buffer;
  } else if (value == -inf()) {
    strcpy(buffer, "-inf");
    return buffer;
  } else if (IsNaN(value)) {
    strcpy(buffer, "nan");
    return buffer;
  }

  int snprintf_result KJ_UNUSED =
    snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG, value);

  // The snprintf should never overflow because the buffer is significantly
  // larger than the precision we asked for.
  KJ_DASSERT(snprintf_result > 0 && snprintf_result < kFloatToBufferSize);

  float parsed_value;
  if (!safe_strtof(buffer, &parsed_value) || parsed_value != value) {
    int snprintf_result2 KJ_UNUSED =
      snprintf(buffer, kFloatToBufferSize, "%.*g", FLT_DIG+2, value);

    // Should never overflow; see above.
    KJ_DASSERT(snprintf_result2 > 0 && snprintf_result2 < kFloatToBufferSize);
  }

  DelocalizeRadix(buffer);
  RemovePlus(buffer);
#if _WIN32
  RemoveE0(buffer);
#endif // _WIN32
  return buffer;
}

// ----------------------------------------------------------------------
// NoLocaleStrtod()
//   This code will make you cry.
// ----------------------------------------------------------------------

namespace {

// Returns a string identical to *input except that the character pointed to
// by radix_pos (which should be '.') is replaced with the locale-specific
// radix character.
kj::String LocalizeRadix(const char* input, const char* radix_pos) {
  // Determine the locale-specific radix character by calling sprintf() to
  // print the number 1.5, then stripping off the digits.  As far as I can
  // tell, this is the only portable, thread-safe way to get the C library
  // to divuldge the locale's radix character.  No, localeconv() is NOT
  // thread-safe.
  char temp[16];
  int size = snprintf(temp, sizeof(temp), "%.1f", 1.5);
  KJ_ASSERT(temp[0] == '1');
  KJ_ASSERT(temp[size-1] == '5');
  KJ_ASSERT(size <= 6);

  // Now replace the '.' in the input with it.
  return kj::str(
      kj::arrayPtr(input, radix_pos),
      kj::arrayPtr(temp + 1, size - 2),
      kj::StringPtr(radix_pos + 1));
}

}  // namespace

double NoLocaleStrtod(const char* text, char** original_endptr) {
  // We cannot simply set the locale to "C" temporarily with setlocale()
  // as this is not thread-safe.  Instead, we try to parse in the current
  // locale first.  If parsing stops at a '.' character, then this is a
  // pretty good hint that we're actually in some other locale in which
  // '.' is not the radix character.

  char* temp_endptr;
  double result = strtod(text, &temp_endptr);
  if (original_endptr != NULL) *original_endptr = temp_endptr;
  if (*temp_endptr != '.') return result;

  // Parsing halted on a '.'.  Perhaps we're in a different locale?  Let's
  // try to replace the '.' with a locale-specific radix character and
  // try again.
  kj::String localized = LocalizeRadix(text, temp_endptr);
  const char* localized_cstr = localized.cStr();
  char* localized_endptr;
  result = strtod(localized_cstr, &localized_endptr);
  if ((localized_endptr - localized_cstr) >
      (temp_endptr - text)) {
    // This attempt got further, so replacing the decimal must have helped.
    // Update original_endptr to point at the right location.
    if (original_endptr != NULL) {
      // size_diff is non-zero if the localized radix has multiple bytes.
      int size_diff = localized.size() - strlen(text);
      // const_cast is necessary to match the strtod() interface.
      *original_endptr = const_cast<char*>(
        text + (localized_endptr - localized_cstr - size_diff));
    }
  }

  return result;
}

// ----------------------------------------------------------------------
// End of code copied from Protobuf
// ----------------------------------------------------------------------

}  // namespace

CappedArray<char, kFloatToBufferSize> Stringifier::operator*(float f) const {
  CappedArray<char, kFloatToBufferSize> result;
  result.setSize(strlen(FloatToBuffer(f, result.begin())));
  return result;
}

CappedArray<char, kDoubleToBufferSize> Stringifier::operator*(double f) const {
  CappedArray<char, kDoubleToBufferSize> result;
  result.setSize(strlen(DoubleToBuffer(f, result.begin())));
  return result;
}

double parseDouble(const StringPtr& s) {
  KJ_REQUIRE(s != nullptr, "String does not contain valid number", s) { return 0; }
  char *endPtr;
  errno = 0;
  auto value = _::NoLocaleStrtod(s.begin(), &endPtr);
  KJ_REQUIRE(endPtr == s.end(), "String does not contain valid floating number", s) { return 0; }
#if _WIN32 || __CYGWIN__ || __BIONIC__
  // When Windows' strtod() parses "nan", it returns a value with the sign bit set. But, our
  // preferred canonical value for NaN does not have the sign bit set, and all other platforms
  // return one without the sign bit set. So, on Windows, detect NaN and return our preferred
  // version.
  //
  // Cygwin seemingly does not try to emulate Linux behavior here, but rather allows Windows'
  // behavior to leak through. (Conversely, WINE actually produces the Linux behavior despite
  // trying to behave like Win32...)
  //
  // Bionic (Android) failed the unit test and so I added it to the list without investigating
  // further.
  if (isNaN(value)) {
    // NaN
    return kj::nan();
  }
#endif
  return value;
}

Maybe<double> tryParseDouble(const StringPtr& s) {
  if(s == nullptr) { return kj::none; }
  char *endPtr;
  errno = 0;
  auto value = _::NoLocaleStrtod(s.begin(), &endPtr);
  if (endPtr != s.end()) { return kj::none; }
#if _WIN32 || __CYGWIN__ || __BIONIC__
  if (isNaN(value)) {
    return kj::nan();
  }
#endif
  return value;
}

}  // namespace _ (private)

template <> double StringPtr::parseAs<double>() const { return _::parseDouble(*this); }
template <> float StringPtr::parseAs<float>() const { return _::parseDouble(*this); }

template <> Maybe<double> StringPtr::tryParseAs<double>() const { return _::tryParseDouble(*this); }
template <> Maybe<float> StringPtr::tryParseAs<float>() const { return _::tryParseDouble(*this); }

Maybe<size_t> StringPtr::find(const StringPtr& other) const {
  if (other.size() == 0) {
    return size_t(0);
  }
  if (size() == 0) {
    return kj::none;
  }
  if (other.size() > size()) {
    // We won't find the entirety of other if other is longer than this.
    return kj::none;
  }

#if !defined(_WIN32)
  void* found = memmem(begin(), size(), other.begin(), other.size());
  if (found == nullptr) {
    return kj::none;
  } else {
    return static_cast<char*>(found)-begin();
  }
#else
  // TODO(perf) This is O(len(this)*len(other)), which is very slow on big strings.
  //
  // On platforms that don't support memem, we should implement the Two-Way String-Matching
  // algorithm with linear performance.  The Two-Way String-Matching algorithm is described in
  // Crochemore and Perrin's CACM paper (Crochemore M., Perrin D., 1991, Two-way
  // string-matching, Journal of the ACM 38(3):651-675).
  //
  // * A scan of the original paper can be found at
  //   https://monge.univ-mlv.fr/~mac/Articles-PDF/CP-1991-jacm.pdf.
  //
  // * I find Python's implementation notes much easier to understand than the original paoer.
  //   https://github.com/python/cpython/blob/main/Objects/stringlib/stringlib_find_two_way_notes.txt
  //
  // * https://www-igm.univ-mlv.fr/~lecroq/string/node26.html#SECTION00260 has a description of
  //   the algorithm with some C code.
  for (size_t i = 0; i + other.size() <= size(); ++i) {
    if (slice(i).startsWith(other)) {
      return i;
    }
  }

  return kj::none;
#endif
}

}  // namespace kj

Coverage Report

Created: 2024-02-11 06:27