1 //===-- StringRef.cpp - Lightweight String References ---------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/StringRef.h"
11 #include "llvm/ADT/APFloat.h"
12 #include "llvm/ADT/APInt.h"
13 #include "llvm/ADT/Hashing.h"
14 #include "llvm/ADT/edit_distance.h"
19 // MSVC emits references to this into the translation units which reference it.
21 const size_t StringRef::npos;
24 static char ascii_tolower(char x) {
25 if (x >= 'A' && x <= 'Z')
30 static char ascii_toupper(char x) {
31 if (x >= 'a' && x <= 'z')
36 static bool ascii_isdigit(char x) {
37 return x >= '0' && x <= '9';
40 // strncasecmp() is not available on non-POSIX systems, so define an
41 // alternative function here.
42 static int ascii_strncasecmp(const char *LHS, const char *RHS, size_t Length) {
43 for (size_t I = 0; I < Length; ++I) {
44 unsigned char LHC = ascii_tolower(LHS[I]);
45 unsigned char RHC = ascii_tolower(RHS[I]);
47 return LHC < RHC ? -1 : 1;
52 /// compare_lower - Compare strings, ignoring case.
53 int StringRef::compare_lower(StringRef RHS) const {
54 if (int Res = ascii_strncasecmp(Data, RHS.Data, std::min(Length, RHS.Length)))
56 if (Length == RHS.Length)
58 return Length < RHS.Length ? -1 : 1;
61 /// Check if this string starts with the given \p Prefix, ignoring case.
62 bool StringRef::startswith_lower(StringRef Prefix) const {
63 return Length >= Prefix.Length &&
64 ascii_strncasecmp(Data, Prefix.Data, Prefix.Length) == 0;
67 /// Check if this string ends with the given \p Suffix, ignoring case.
68 bool StringRef::endswith_lower(StringRef Suffix) const {
69 return Length >= Suffix.Length &&
70 ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0;
73 size_t StringRef::find_lower(char C, size_t From) const {
74 char L = ascii_tolower(C);
75 return find_if([L](char D) { return ascii_tolower(D) == L; }, From);
78 /// compare_numeric - Compare strings, handle embedded numbers.
79 int StringRef::compare_numeric(StringRef RHS) const {
80 for (size_t I = 0, E = std::min(Length, RHS.Length); I != E; ++I) {
81 // Check for sequences of digits.
82 if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) {
83 // The longer sequence of numbers is considered larger.
84 // This doesn't really handle prefixed zeros well.
86 for (J = I + 1; J != E + 1; ++J) {
87 bool ld = J < Length && ascii_isdigit(Data[J]);
88 bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]);
94 // The two number sequences have the same length (J-I), just memcmp them.
95 if (int Res = compareMemory(Data + I, RHS.Data + I, J - I))
96 return Res < 0 ? -1 : 1;
97 // Identical number sequences, continue search after the numbers.
101 if (Data[I] != RHS.Data[I])
102 return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1;
104 if (Length == RHS.Length)
106 return Length < RHS.Length ? -1 : 1;
109 // Compute the edit distance between the two given strings.
110 unsigned StringRef::edit_distance(llvm::StringRef Other,
111 bool AllowReplacements,
112 unsigned MaxEditDistance) const {
113 return llvm::ComputeEditDistance(
114 makeArrayRef(data(), size()),
115 makeArrayRef(Other.data(), Other.size()),
116 AllowReplacements, MaxEditDistance);
119 //===----------------------------------------------------------------------===//
121 //===----------------------------------------------------------------------===//
123 std::string StringRef::lower() const {
124 std::string Result(size(), char());
125 for (size_type i = 0, e = size(); i != e; ++i) {
126 Result[i] = ascii_tolower(Data[i]);
131 std::string StringRef::upper() const {
132 std::string Result(size(), char());
133 for (size_type i = 0, e = size(); i != e; ++i) {
134 Result[i] = ascii_toupper(Data[i]);
139 //===----------------------------------------------------------------------===//
141 //===----------------------------------------------------------------------===//
144 /// find - Search for the first string \arg Str in the string.
146 /// \return - The index of the first occurrence of \arg Str, or npos if not
148 size_t StringRef::find(StringRef Str, size_t From) const {
152 const char *Start = Data + From;
153 size_t Size = Length - From;
155 const char *Needle = Str.data();
156 size_t N = Str.size();
162 const char *Ptr = (const char *)::memchr(Start, Needle[0], Size);
163 return Ptr == nullptr ? npos : Ptr - Data;
166 const char *Stop = Start + (Size - N + 1);
168 // For short haystacks or unsupported needles fall back to the naive algorithm
169 if (Size < 16 || N > 255) {
171 if (std::memcmp(Start, Needle, N) == 0)
174 } while (Start < Stop);
178 // Build the bad char heuristic table, with uint8_t to reduce cache thrashing.
179 uint8_t BadCharSkip[256];
180 std::memset(BadCharSkip, N, 256);
181 for (unsigned i = 0; i != N-1; ++i)
182 BadCharSkip[(uint8_t)Str[i]] = N-1-i;
185 uint8_t Last = Start[N - 1];
186 if (LLVM_UNLIKELY(Last == (uint8_t)Needle[N - 1]))
187 if (std::memcmp(Start, Needle, N - 1) == 0)
190 // Otherwise skip the appropriate number of bytes.
191 Start += BadCharSkip[Last];
192 } while (Start < Stop);
197 size_t StringRef::find_lower(StringRef Str, size_t From) const {
198 StringRef This = substr(From);
199 while (This.size() >= Str.size()) {
200 if (This.startswith_lower(Str))
202 This = This.drop_front();
208 size_t StringRef::rfind_lower(char C, size_t From) const {
209 From = std::min(From, Length);
213 if (ascii_tolower(Data[i]) == ascii_tolower(C))
219 /// rfind - Search for the last string \arg Str in the string.
221 /// \return - The index of the last occurrence of \arg Str, or npos if not
223 size_t StringRef::rfind(StringRef Str) const {
224 size_t N = Str.size();
227 for (size_t i = Length - N + 1, e = 0; i != e;) {
229 if (substr(i, N).equals(Str))
235 size_t StringRef::rfind_lower(StringRef Str) const {
236 size_t N = Str.size();
239 for (size_t i = Length - N + 1, e = 0; i != e;) {
241 if (substr(i, N).equals_lower(Str))
247 /// find_first_of - Find the first character in the string that is in \arg
248 /// Chars, or npos if not found.
250 /// Note: O(size() + Chars.size())
251 StringRef::size_type StringRef::find_first_of(StringRef Chars,
253 std::bitset<1 << CHAR_BIT> CharBits;
254 for (size_type i = 0; i != Chars.size(); ++i)
255 CharBits.set((unsigned char)Chars[i]);
257 for (size_type i = std::min(From, Length), e = Length; i != e; ++i)
258 if (CharBits.test((unsigned char)Data[i]))
263 /// find_first_not_of - Find the first character in the string that is not
264 /// \arg C or npos if not found.
265 StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const {
266 for (size_type i = std::min(From, Length), e = Length; i != e; ++i)
272 /// find_first_not_of - Find the first character in the string that is not
273 /// in the string \arg Chars, or npos if not found.
275 /// Note: O(size() + Chars.size())
276 StringRef::size_type StringRef::find_first_not_of(StringRef Chars,
278 std::bitset<1 << CHAR_BIT> CharBits;
279 for (size_type i = 0; i != Chars.size(); ++i)
280 CharBits.set((unsigned char)Chars[i]);
282 for (size_type i = std::min(From, Length), e = Length; i != e; ++i)
283 if (!CharBits.test((unsigned char)Data[i]))
288 /// find_last_of - Find the last character in the string that is in \arg C,
289 /// or npos if not found.
291 /// Note: O(size() + Chars.size())
292 StringRef::size_type StringRef::find_last_of(StringRef Chars,
294 std::bitset<1 << CHAR_BIT> CharBits;
295 for (size_type i = 0; i != Chars.size(); ++i)
296 CharBits.set((unsigned char)Chars[i]);
298 for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i)
299 if (CharBits.test((unsigned char)Data[i]))
304 /// find_last_not_of - Find the last character in the string that is not
305 /// \arg C, or npos if not found.
306 StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const {
307 for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i)
313 /// find_last_not_of - Find the last character in the string that is not in
314 /// \arg Chars, or npos if not found.
316 /// Note: O(size() + Chars.size())
317 StringRef::size_type StringRef::find_last_not_of(StringRef Chars,
319 std::bitset<1 << CHAR_BIT> CharBits;
320 for (size_type i = 0, e = Chars.size(); i != e; ++i)
321 CharBits.set((unsigned char)Chars[i]);
323 for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i)
324 if (!CharBits.test((unsigned char)Data[i]))
329 void StringRef::split(SmallVectorImpl<StringRef> &A,
330 StringRef Separator, int MaxSplit,
331 bool KeepEmpty) const {
334 // Count down from MaxSplit. When MaxSplit is -1, this will just split
335 // "forever". This doesn't support splitting more than 2^31 times
336 // intentionally; if we ever want that we can make MaxSplit a 64-bit integer
337 // but that seems unlikely to be useful.
338 while (MaxSplit-- != 0) {
339 size_t Idx = S.find(Separator);
344 if (KeepEmpty || Idx > 0)
345 A.push_back(S.slice(0, Idx));
348 S = S.slice(Idx + Separator.size(), npos);
352 if (KeepEmpty || !S.empty())
356 void StringRef::split(SmallVectorImpl<StringRef> &A, char Separator,
357 int MaxSplit, bool KeepEmpty) const {
360 // Count down from MaxSplit. When MaxSplit is -1, this will just split
361 // "forever". This doesn't support splitting more than 2^31 times
362 // intentionally; if we ever want that we can make MaxSplit a 64-bit integer
363 // but that seems unlikely to be useful.
364 while (MaxSplit-- != 0) {
365 size_t Idx = S.find(Separator);
370 if (KeepEmpty || Idx > 0)
371 A.push_back(S.slice(0, Idx));
374 S = S.slice(Idx + 1, npos);
378 if (KeepEmpty || !S.empty())
382 //===----------------------------------------------------------------------===//
383 // Helpful Algorithms
384 //===----------------------------------------------------------------------===//
386 /// count - Return the number of non-overlapped occurrences of \arg Str in
388 size_t StringRef::count(StringRef Str) const {
390 size_t N = Str.size();
393 for (size_t i = 0, e = Length - N + 1; i != e; ++i)
394 if (substr(i, N).equals(Str))
399 static unsigned GetAutoSenseRadix(StringRef &Str) {
403 if (Str.startswith("0x") || Str.startswith("0X")) {
408 if (Str.startswith("0b") || Str.startswith("0B")) {
413 if (Str.startswith("0o")) {
418 if (Str[0] == '0' && Str.size() > 1 && ascii_isdigit(Str[1])) {
426 bool llvm::consumeUnsignedInteger(StringRef &Str, unsigned Radix,
427 unsigned long long &Result) {
428 // Autosense radix if not specified.
430 Radix = GetAutoSenseRadix(Str);
432 // Empty strings (after the radix autosense) are invalid.
433 if (Str.empty()) return true;
435 // Parse all the bytes of the string given this radix. Watch for overflow.
436 StringRef Str2 = Str;
438 while (!Str2.empty()) {
440 if (Str2[0] >= '0' && Str2[0] <= '9')
441 CharVal = Str2[0] - '0';
442 else if (Str2[0] >= 'a' && Str2[0] <= 'z')
443 CharVal = Str2[0] - 'a' + 10;
444 else if (Str2[0] >= 'A' && Str2[0] <= 'Z')
445 CharVal = Str2[0] - 'A' + 10;
449 // If the parsed value is larger than the integer radix, we cannot
450 // consume any more characters.
451 if (CharVal >= Radix)
454 // Add in this character.
455 unsigned long long PrevResult = Result;
456 Result = Result * Radix + CharVal;
458 // Check for overflow by shifting back and seeing if bits were lost.
459 if (Result / Radix < PrevResult)
462 Str2 = Str2.substr(1);
465 // We consider the operation a failure if no characters were consumed
467 if (Str.size() == Str2.size())
474 bool llvm::consumeSignedInteger(StringRef &Str, unsigned Radix,
476 unsigned long long ULLVal;
478 // Handle positive strings first.
479 if (Str.empty() || Str.front() != '-') {
480 if (consumeUnsignedInteger(Str, Radix, ULLVal) ||
481 // Check for value so large it overflows a signed value.
482 (long long)ULLVal < 0)
488 // Get the positive part of the value.
489 StringRef Str2 = Str.drop_front(1);
490 if (consumeUnsignedInteger(Str2, Radix, ULLVal) ||
491 // Reject values so large they'd overflow as negative signed, but allow
492 // "-0". This negates the unsigned so that the negative isn't undefined
493 // on signed overflow.
494 (long long)-ULLVal > 0)
502 /// GetAsUnsignedInteger - Workhorse method that converts a integer character
503 /// sequence of radix up to 36 to an unsigned long long value.
504 bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix,
505 unsigned long long &Result) {
506 if (consumeUnsignedInteger(Str, Radix, Result))
509 // For getAsUnsignedInteger, we require the whole string to be consumed or
510 // else we consider it a failure.
514 bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix,
516 if (consumeSignedInteger(Str, Radix, Result))
519 // For getAsSignedInteger, we require the whole string to be consumed or else
520 // we consider it a failure.
524 bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const {
525 StringRef Str = *this;
527 // Autosense radix if not specified.
529 Radix = GetAutoSenseRadix(Str);
531 assert(Radix > 1 && Radix <= 36);
533 // Empty strings (after the radix autosense) are invalid.
534 if (Str.empty()) return true;
536 // Skip leading zeroes. This can be a significant improvement if
537 // it means we don't need > 64 bits.
538 while (!Str.empty() && Str.front() == '0')
541 // If it was nothing but zeroes....
543 Result = APInt(64, 0);
547 // (Over-)estimate the required number of bits.
548 unsigned Log2Radix = 0;
549 while ((1U << Log2Radix) < Radix) Log2Radix++;
550 bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix);
552 unsigned BitWidth = Log2Radix * Str.size();
553 if (BitWidth < Result.getBitWidth())
554 BitWidth = Result.getBitWidth(); // don't shrink the result
555 else if (BitWidth > Result.getBitWidth())
556 Result = Result.zext(BitWidth);
558 APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix
559 if (!IsPowerOf2Radix) {
560 // These must have the same bit-width as Result.
561 RadixAP = APInt(BitWidth, Radix);
562 CharAP = APInt(BitWidth, 0);
565 // Parse all the bytes of the string given this radix.
567 while (!Str.empty()) {
569 if (Str[0] >= '0' && Str[0] <= '9')
570 CharVal = Str[0]-'0';
571 else if (Str[0] >= 'a' && Str[0] <= 'z')
572 CharVal = Str[0]-'a'+10;
573 else if (Str[0] >= 'A' && Str[0] <= 'Z')
574 CharVal = Str[0]-'A'+10;
578 // If the parsed value is larger than the integer radix, the string is
580 if (CharVal >= Radix)
583 // Add in this character.
584 if (IsPowerOf2Radix) {
585 Result <<= Log2Radix;
599 bool StringRef::getAsDouble(double &Result, bool AllowInexact) const {
601 APFloat::opStatus Status =
602 F.convertFromString(*this, APFloat::rmNearestTiesToEven);
603 if (Status != APFloat::opOK) {
604 if (!AllowInexact || Status != APFloat::opInexact)
608 Result = F.convertToDouble();
612 // Implementation of StringRef hashing.
613 hash_code llvm::hash_value(StringRef S) {
614 return hash_combine_range(S.begin(), S.end());