619 lines · cpp
1//===-- StringRef.cpp - Lightweight String References ---------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/StringRef.h"10#include "llvm/ADT/APFloat.h"11#include "llvm/ADT/APInt.h"12#include "llvm/ADT/Hashing.h"13#include "llvm/ADT/StringExtras.h"14#include "llvm/ADT/edit_distance.h"15#include "llvm/Support/Error.h"16#include <bitset>17 18using namespace llvm;19 20// strncasecmp() is not available on non-POSIX systems, so define an21// alternative function here.22static int ascii_strncasecmp(StringRef LHS, StringRef RHS) {23 for (auto [LC, RC] : zip_equal(LHS, RHS)) {24 unsigned char LHC = toLower(LC);25 unsigned char RHC = toLower(RC);26 if (LHC != RHC)27 return LHC < RHC ? -1 : 1;28 }29 return 0;30}31 32int StringRef::compare_insensitive(StringRef RHS) const {33 size_t Min = std::min(size(), RHS.size());34 if (int Res = ascii_strncasecmp(take_front(Min), RHS.take_front(Min)))35 return Res;36 if (size() == RHS.size())37 return 0;38 return size() < RHS.size() ? -1 : 1;39}40 41bool StringRef::starts_with_insensitive(StringRef Prefix) const {42 return size() >= Prefix.size() &&43 ascii_strncasecmp(take_front(Prefix.size()), Prefix) == 0;44}45 46bool StringRef::ends_with_insensitive(StringRef Suffix) const {47 return size() >= Suffix.size() &&48 ascii_strncasecmp(take_back(Suffix.size()), Suffix) == 0;49}50 51size_t StringRef::find_insensitive(char C, size_t From) const {52 char L = toLower(C);53 return find_if([L](char D) { return toLower(D) == L; }, From);54}55 56/// compare_numeric - Compare strings, handle embedded numbers.57int StringRef::compare_numeric(StringRef RHS) const {58 for (size_t I = 0, E = std::min(size(), RHS.size()); I != E; ++I) {59 // Check for sequences of digits.60 if (isDigit(data()[I]) && isDigit(RHS.data()[I])) {61 // The longer sequence of numbers is considered larger.62 // This doesn't really handle prefixed zeros well.63 size_t J;64 for (J = I + 1; J != E + 1; ++J) {65 bool ld = J < size() && isDigit(data()[J]);66 bool rd = J < RHS.size() && isDigit(RHS.data()[J]);67 if (ld != rd)68 return rd ? -1 : 1;69 if (!rd)70 break;71 }72 // The two number sequences have the same length (J-I), just memcmp them.73 if (int Res = compareMemory(data() + I, RHS.data() + I, J - I))74 return Res < 0 ? -1 : 1;75 // Identical number sequences, continue search after the numbers.76 I = J - 1;77 continue;78 }79 if (data()[I] != RHS.data()[I])80 return (unsigned char)data()[I] < (unsigned char)RHS.data()[I] ? -1 : 1;81 }82 if (size() == RHS.size())83 return 0;84 return size() < RHS.size() ? -1 : 1;85}86 87// Compute the edit distance between the two given strings.88unsigned StringRef::edit_distance(llvm::StringRef Other,89 bool AllowReplacements,90 unsigned MaxEditDistance) const {91 return llvm::ComputeEditDistance(ArrayRef(data(), size()),92 ArrayRef(Other.data(), Other.size()),93 AllowReplacements, MaxEditDistance);94}95 96unsigned llvm::StringRef::edit_distance_insensitive(97 StringRef Other, bool AllowReplacements, unsigned MaxEditDistance) const {98 return llvm::ComputeMappedEditDistance(99 ArrayRef(data(), size()), ArrayRef(Other.data(), Other.size()),100 llvm::toLower, AllowReplacements, MaxEditDistance);101}102 103//===----------------------------------------------------------------------===//104// String Operations105//===----------------------------------------------------------------------===//106 107std::string StringRef::lower() const {108 return std::string(map_iterator(begin(), toLower),109 map_iterator(end(), toLower));110}111 112std::string StringRef::upper() const {113 return std::string(map_iterator(begin(), toUpper),114 map_iterator(end(), toUpper));115}116 117//===----------------------------------------------------------------------===//118// String Searching119//===----------------------------------------------------------------------===//120 121 122/// find - Search for the first string \arg Str in the string.123///124/// \return - The index of the first occurrence of \arg Str, or npos if not125/// found.126size_t StringRef::find(StringRef Str, size_t From) const {127 if (From > size())128 return npos;129 130 const char *Start = data() + From;131 size_t Size = size() - From;132 133 const char *Needle = Str.data();134 size_t N = Str.size();135 if (N == 0)136 return From;137 if (Size < N)138 return npos;139 if (N == 1) {140 const char *Ptr = (const char *)::memchr(Start, Needle[0], Size);141 return Ptr == nullptr ? npos : Ptr - data();142 }143 144 const char *Stop = Start + (Size - N + 1);145 146 if (N == 2) {147 // Provide a fast path for newline finding (CRLF case) in InclusionRewriter.148 // Not the most optimized strategy, but getting memcmp inlined should be149 // good enough.150 do {151 if (std::memcmp(Start, Needle, 2) == 0)152 return Start - data();153 ++Start;154 } while (Start < Stop);155 return npos;156 }157 158 // For short haystacks or unsupported needles fall back to the naive algorithm159 if (Size < 16 || N > 255) {160 do {161 if (std::memcmp(Start, Needle, N) == 0)162 return Start - data();163 ++Start;164 } while (Start < Stop);165 return npos;166 }167 168 // Build the bad char heuristic table, with uint8_t to reduce cache thrashing.169 uint8_t BadCharSkip[256];170 std::memset(BadCharSkip, N, 256);171 for (unsigned i = 0; i != N-1; ++i)172 BadCharSkip[(uint8_t)Str[i]] = N-1-i;173 174 do {175 uint8_t Last = Start[N - 1];176 if (LLVM_UNLIKELY(Last == (uint8_t)Needle[N - 1]))177 if (std::memcmp(Start, Needle, N - 1) == 0)178 return Start - data();179 180 // Otherwise skip the appropriate number of bytes.181 Start += BadCharSkip[Last];182 } while (Start < Stop);183 184 return npos;185}186 187size_t StringRef::find_insensitive(StringRef Str, size_t From) const {188 StringRef This = substr(From);189 while (This.size() >= Str.size()) {190 if (This.starts_with_insensitive(Str))191 return From;192 This = This.drop_front();193 ++From;194 }195 return npos;196}197 198size_t StringRef::rfind_insensitive(char C, size_t From) const {199 From = std::min(From, size());200 size_t i = From;201 while (i != 0) {202 --i;203 if (toLower(data()[i]) == toLower(C))204 return i;205 }206 return npos;207}208 209/// rfind - Search for the last string \arg Str in the string.210///211/// \return - The index of the last occurrence of \arg Str, or npos if not212/// found.213size_t StringRef::rfind(StringRef Str) const {214 return std::string_view(*this).rfind(Str);215}216 217size_t StringRef::rfind_insensitive(StringRef Str) const {218 size_t N = Str.size();219 if (N > size())220 return npos;221 for (size_t i = size() - N + 1, e = 0; i != e;) {222 --i;223 if (substr(i, N).equals_insensitive(Str))224 return i;225 }226 return npos;227}228 229/// find_first_of - Find the first character in the string that is in \arg230/// Chars, or npos if not found.231///232/// Note: O(size() + Chars.size())233StringRef::size_type StringRef::find_first_of(StringRef Chars,234 size_t From) const {235 std::bitset<1 << CHAR_BIT> CharBits;236 for (char C : Chars)237 CharBits.set((unsigned char)C);238 239 for (size_type i = std::min(From, size()), e = size(); i != e; ++i)240 if (CharBits.test((unsigned char)data()[i]))241 return i;242 return npos;243}244 245/// find_first_not_of - Find the first character in the string that is not246/// \arg C or npos if not found.247StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const {248 return std::string_view(*this).find_first_not_of(C, From);249}250 251/// find_first_not_of - Find the first character in the string that is not252/// in the string \arg Chars, or npos if not found.253///254/// Note: O(size() + Chars.size())255StringRef::size_type StringRef::find_first_not_of(StringRef Chars,256 size_t From) const {257 std::bitset<1 << CHAR_BIT> CharBits;258 for (char C : Chars)259 CharBits.set((unsigned char)C);260 261 for (size_type i = std::min(From, size()), e = size(); i != e; ++i)262 if (!CharBits.test((unsigned char)data()[i]))263 return i;264 return npos;265}266 267/// find_last_of - Find the last character in the string that is in \arg C,268/// or npos if not found.269///270/// Note: O(size() + Chars.size())271StringRef::size_type StringRef::find_last_of(StringRef Chars,272 size_t From) const {273 std::bitset<1 << CHAR_BIT> CharBits;274 for (char C : Chars)275 CharBits.set((unsigned char)C);276 277 for (size_type i = std::min(From, size()) - 1, e = -1; i != e; --i)278 if (CharBits.test((unsigned char)data()[i]))279 return i;280 return npos;281}282 283/// find_last_not_of - Find the last character in the string that is not284/// \arg C, or npos if not found.285StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const {286 for (size_type i = std::min(From, size()) - 1, e = -1; i != e; --i)287 if (data()[i] != C)288 return i;289 return npos;290}291 292/// find_last_not_of - Find the last character in the string that is not in293/// \arg Chars, or npos if not found.294///295/// Note: O(size() + Chars.size())296StringRef::size_type StringRef::find_last_not_of(StringRef Chars,297 size_t From) const {298 std::bitset<1 << CHAR_BIT> CharBits;299 for (char C : Chars)300 CharBits.set((unsigned char)C);301 302 for (size_type i = std::min(From, size()) - 1, e = -1; i != e; --i)303 if (!CharBits.test((unsigned char)data()[i]))304 return i;305 return npos;306}307 308void StringRef::split(SmallVectorImpl<StringRef> &A,309 StringRef Separator, int MaxSplit,310 bool KeepEmpty) const {311 StringRef S = *this;312 313 // Count down from MaxSplit. When MaxSplit is -1, this will just split314 // "forever". This doesn't support splitting more than 2^31 times315 // intentionally; if we ever want that we can make MaxSplit a 64-bit integer316 // but that seems unlikely to be useful.317 while (MaxSplit-- != 0) {318 size_t Idx = S.find(Separator);319 if (Idx == npos)320 break;321 322 // Push this split.323 if (KeepEmpty || Idx > 0)324 A.push_back(S.slice(0, Idx));325 326 // Jump forward.327 S = S.substr(Idx + Separator.size());328 }329 330 // Push the tail.331 if (KeepEmpty || !S.empty())332 A.push_back(S);333}334 335void StringRef::split(SmallVectorImpl<StringRef> &A, char Separator,336 int MaxSplit, bool KeepEmpty) const {337 StringRef S = *this;338 339 // Count down from MaxSplit. When MaxSplit is -1, this will just split340 // "forever". This doesn't support splitting more than 2^31 times341 // intentionally; if we ever want that we can make MaxSplit a 64-bit integer342 // but that seems unlikely to be useful.343 while (MaxSplit-- != 0) {344 size_t Idx = S.find(Separator);345 if (Idx == npos)346 break;347 348 // Push this split.349 if (KeepEmpty || Idx > 0)350 A.push_back(S.slice(0, Idx));351 352 // Jump forward.353 S = S.substr(Idx + 1);354 }355 356 // Push the tail.357 if (KeepEmpty || !S.empty())358 A.push_back(S);359}360 361//===----------------------------------------------------------------------===//362// Helpful Algorithms363//===----------------------------------------------------------------------===//364 365/// count - Return the number of non-overlapped occurrences of \arg Str in366/// the string.367size_t StringRef::count(StringRef Str) const {368 size_t Count = 0;369 size_t Pos = 0;370 size_t N = Str.size();371 // TODO: For an empty `Str` we return 0 for legacy reasons. Consider changing372 // this to `Length + 1` which is more in-line with the function373 // description.374 if (!N)375 return 0;376 while ((Pos = find(Str, Pos)) != npos) {377 ++Count;378 Pos += N;379 }380 return Count;381}382 383unsigned llvm::getAutoSenseRadix(StringRef &Str) {384 if (Str.empty())385 return 10;386 387 if (Str.consume_front_insensitive("0x"))388 return 16;389 390 if (Str.consume_front_insensitive("0b"))391 return 2;392 393 if (Str.consume_front("0o"))394 return 8;395 396 if (Str[0] == '0' && Str.size() > 1 && isDigit(Str[1])) {397 Str = Str.substr(1);398 return 8;399 }400 401 return 10;402}403 404bool llvm::consumeUnsignedInteger(StringRef &Str, unsigned Radix,405 unsigned long long &Result) {406 // Autosense radix if not specified.407 if (Radix == 0)408 Radix = getAutoSenseRadix(Str);409 410 // Empty strings (after the radix autosense) are invalid.411 if (Str.empty()) return true;412 413 // Parse all the bytes of the string given this radix. Watch for overflow.414 StringRef Str2 = Str;415 Result = 0;416 while (!Str2.empty()) {417 unsigned CharVal;418 if (Str2[0] >= '0' && Str2[0] <= '9')419 CharVal = Str2[0] - '0';420 else if (Str2[0] >= 'a' && Str2[0] <= 'z')421 CharVal = Str2[0] - 'a' + 10;422 else if (Str2[0] >= 'A' && Str2[0] <= 'Z')423 CharVal = Str2[0] - 'A' + 10;424 else425 break;426 427 // If the parsed value is larger than the integer radix, we cannot428 // consume any more characters.429 if (CharVal >= Radix)430 break;431 432 // Add in this character.433 unsigned long long PrevResult = Result;434 Result = Result * Radix + CharVal;435 436 // Check for overflow by shifting back and seeing if bits were lost.437 if (Result / Radix < PrevResult)438 return true;439 440 Str2 = Str2.substr(1);441 }442 443 // We consider the operation a failure if no characters were consumed444 // successfully.445 if (Str.size() == Str2.size())446 return true;447 448 Str = Str2;449 return false;450}451 452bool llvm::consumeSignedInteger(StringRef &Str, unsigned Radix,453 long long &Result) {454 unsigned long long ULLVal;455 456 // Handle positive strings first.457 if (!Str.starts_with("-")) {458 if (consumeUnsignedInteger(Str, Radix, ULLVal) ||459 // Check for value so large it overflows a signed value.460 (long long)ULLVal < 0)461 return true;462 Result = ULLVal;463 return false;464 }465 466 // Get the positive part of the value.467 StringRef Str2 = Str.drop_front(1);468 if (consumeUnsignedInteger(Str2, Radix, ULLVal) ||469 // Reject values so large they'd overflow as negative signed, but allow470 // "-0". This negates the unsigned so that the negative isn't undefined471 // on signed overflow.472 (long long)-ULLVal > 0)473 return true;474 475 Str = Str2;476 Result = -ULLVal;477 return false;478}479 480/// GetAsUnsignedInteger - Workhorse method that converts a integer character481/// sequence of radix up to 36 to an unsigned long long value.482bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix,483 unsigned long long &Result) {484 if (consumeUnsignedInteger(Str, Radix, Result))485 return true;486 487 // For getAsUnsignedInteger, we require the whole string to be consumed or488 // else we consider it a failure.489 return !Str.empty();490}491 492bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix,493 long long &Result) {494 if (consumeSignedInteger(Str, Radix, Result))495 return true;496 497 // For getAsSignedInteger, we require the whole string to be consumed or else498 // we consider it a failure.499 return !Str.empty();500}501 502bool StringRef::consumeInteger(unsigned Radix, APInt &Result) {503 StringRef Str = *this;504 505 // Autosense radix if not specified.506 if (Radix == 0)507 Radix = getAutoSenseRadix(Str);508 509 assert(Radix > 1 && Radix <= 36);510 511 // Empty strings (after the radix autosense) are invalid.512 if (Str.empty()) return true;513 514 // Skip leading zeroes. This can be a significant improvement if515 // it means we don't need > 64 bits.516 Str = Str.ltrim('0');517 518 // If it was nothing but zeroes....519 if (Str.empty()) {520 Result = APInt(64, 0);521 *this = Str;522 return false;523 }524 525 // (Over-)estimate the required number of bits.526 unsigned Log2Radix = 0;527 while ((1U << Log2Radix) < Radix) Log2Radix++;528 bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix);529 530 unsigned BitWidth = Log2Radix * Str.size();531 if (BitWidth < Result.getBitWidth())532 BitWidth = Result.getBitWidth(); // don't shrink the result533 else if (BitWidth > Result.getBitWidth())534 Result = Result.zext(BitWidth);535 536 APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix537 if (!IsPowerOf2Radix) {538 // These must have the same bit-width as Result.539 RadixAP = APInt(BitWidth, Radix);540 CharAP = APInt(BitWidth, 0);541 }542 543 // Parse all the bytes of the string given this radix.544 Result = 0;545 while (!Str.empty()) {546 unsigned CharVal;547 if (Str[0] >= '0' && Str[0] <= '9')548 CharVal = Str[0]-'0';549 else if (Str[0] >= 'a' && Str[0] <= 'z')550 CharVal = Str[0]-'a'+10;551 else if (Str[0] >= 'A' && Str[0] <= 'Z')552 CharVal = Str[0]-'A'+10;553 else554 break;555 556 // If the parsed value is larger than the integer radix, the string is557 // invalid.558 if (CharVal >= Radix)559 break;560 561 // Add in this character.562 if (IsPowerOf2Radix) {563 Result <<= Log2Radix;564 Result |= CharVal;565 } else {566 Result *= RadixAP;567 CharAP = CharVal;568 Result += CharAP;569 }570 571 Str = Str.substr(1);572 }573 574 // We consider the operation a failure if no characters were consumed575 // successfully.576 if (size() == Str.size())577 return true;578 579 *this = Str;580 return false;581}582 583bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const {584 StringRef Str = *this;585 if (Str.consumeInteger(Radix, Result))586 return true;587 588 // For getAsInteger, we require the whole string to be consumed or else we589 // consider it a failure.590 return !Str.empty();591}592 593bool StringRef::getAsDouble(double &Result, bool AllowInexact) const {594 APFloat F(0.0);595 auto StatusOrErr = F.convertFromString(*this, APFloat::rmNearestTiesToEven);596 if (errorToBool(StatusOrErr.takeError()))597 return true;598 599 APFloat::opStatus Status = *StatusOrErr;600 if (Status != APFloat::opOK) {601 if (!AllowInexact || !(Status & APFloat::opInexact))602 return true;603 }604 605 Result = F.convertToDouble();606 return false;607}608 609// Implementation of StringRef hashing.610hash_code llvm::hash_value(StringRef S) { return hash_combine_range(S); }611 612unsigned DenseMapInfo<StringRef, void>::getHashValue(StringRef Val) {613 assert(Val.data() != getEmptyKey().data() &&614 "Cannot hash the empty key!");615 assert(Val.data() != getTombstoneKey().data() &&616 "Cannot hash the tombstone key!");617 return (unsigned)(hash_value(Val));618}619