1//===-- StringRef.cpp - Lightweight String References ---------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "llvm/ADT/StringRef.h" 11#include "llvm/ADT/APInt.h" 12#include "llvm/ADT/Hashing.h" 13#include "llvm/ADT/OwningPtr.h" 14#include "llvm/ADT/edit_distance.h" 15#include <bitset> 16 17using namespace llvm; 18 19// MSVC emits references to this into the translation units which reference it. 20#ifndef _MSC_VER 21const size_t StringRef::npos; 22#endif 23 24static char ascii_tolower(char x) { 25 if (x >= 'A' && x <= 'Z') 26 return x - 'A' + 'a'; 27 return x; 28} 29 30static char ascii_toupper(char x) { 31 if (x >= 'a' && x <= 'z') 32 return x - 'a' + 'A'; 33 return x; 34} 35 36static bool ascii_isdigit(char x) { 37 return x >= '0' && x <= '9'; 38} 39 40/// compare_lower - Compare strings, ignoring case. 41int StringRef::compare_lower(StringRef RHS) const { 42 for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { 43 unsigned char LHC = ascii_tolower(Data[I]); 44 unsigned char RHC = ascii_tolower(RHS.Data[I]); 45 if (LHC != RHC) 46 return LHC < RHC ? -1 : 1; 47 } 48 49 if (Length == RHS.Length) 50 return 0; 51 return Length < RHS.Length ? -1 : 1; 52} 53 54/// compare_numeric - Compare strings, handle embedded numbers. 55int StringRef::compare_numeric(StringRef RHS) const { 56 for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { 57 // Check for sequences of digits. 58 if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) { 59 // The longer sequence of numbers is considered larger. 60 // This doesn't really handle prefixed zeros well. 61 size_t J; 62 for (J = I + 1; J != E + 1; ++J) { 63 bool ld = J < Length && ascii_isdigit(Data[J]); 64 bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]); 65 if (ld != rd) 66 return rd ? -1 : 1; 67 if (!rd) 68 break; 69 } 70 // The two number sequences have the same length (J-I), just memcmp them. 71 if (int Res = compareMemory(Data + I, RHS.Data + I, J - I)) 72 return Res < 0 ? -1 : 1; 73 // Identical number sequences, continue search after the numbers. 74 I = J - 1; 75 continue; 76 } 77 if (Data[I] != RHS.Data[I]) 78 return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; 79 } 80 if (Length == RHS.Length) 81 return 0; 82 return Length < RHS.Length ? -1 : 1; 83} 84 85// Compute the edit distance between the two given strings. 86unsigned StringRef::edit_distance(llvm::StringRef Other, 87 bool AllowReplacements, 88 unsigned MaxEditDistance) { 89 return llvm::ComputeEditDistance( 90 llvm::ArrayRef<char>(data(), size()), 91 llvm::ArrayRef<char>(Other.data(), Other.size()), 92 AllowReplacements, MaxEditDistance); 93} 94 95//===----------------------------------------------------------------------===// 96// String Operations 97//===----------------------------------------------------------------------===// 98 99std::string StringRef::lower() const { 100 std::string Result(size(), char()); 101 for (size_type i = 0, e = size(); i != e; ++i) { 102 Result[i] = ascii_tolower(Data[i]); 103 } 104 return Result; 105} 106 107std::string StringRef::upper() const { 108 std::string Result(size(), char()); 109 for (size_type i = 0, e = size(); i != e; ++i) { 110 Result[i] = ascii_toupper(Data[i]); 111 } 112 return Result; 113} 114 115//===----------------------------------------------------------------------===// 116// String Searching 117//===----------------------------------------------------------------------===// 118 119 120/// find - Search for the first string \arg Str in the string. 121/// 122/// \return - The index of the first occurrence of \arg Str, or npos if not 123/// found. 124size_t StringRef::find(StringRef Str, size_t From) const { 125 size_t N = Str.size(); 126 if (N > Length) 127 return npos; 128 129 // For short haystacks or unsupported needles fall back to the naive algorithm 130 if (Length < 16 || N > 255 || N == 0) { 131 for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i) 132 if (substr(i, N).equals(Str)) 133 return i; 134 return npos; 135 } 136 137 if (From >= Length) 138 return npos; 139 140 // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. 141 uint8_t BadCharSkip[256]; 142 std::memset(BadCharSkip, N, 256); 143 for (unsigned i = 0; i != N-1; ++i) 144 BadCharSkip[(uint8_t)Str[i]] = N-1-i; 145 146 unsigned Len = Length-From, Pos = From; 147 while (Len >= N) { 148 if (substr(Pos, N).equals(Str)) // See if this is the correct substring. 149 return Pos; 150 151 // Otherwise skip the appropriate number of bytes. 152 uint8_t Skip = BadCharSkip[(uint8_t)(*this)[Pos+N-1]]; 153 Len -= Skip; 154 Pos += Skip; 155 } 156 157 return npos; 158} 159 160/// rfind - Search for the last string \arg Str in the string. 161/// 162/// \return - The index of the last occurrence of \arg Str, or npos if not 163/// found. 164size_t StringRef::rfind(StringRef Str) const { 165 size_t N = Str.size(); 166 if (N > Length) 167 return npos; 168 for (size_t i = Length - N + 1, e = 0; i != e;) { 169 --i; 170 if (substr(i, N).equals(Str)) 171 return i; 172 } 173 return npos; 174} 175 176/// find_first_of - Find the first character in the string that is in \arg 177/// Chars, or npos if not found. 178/// 179/// Note: O(size() + Chars.size()) 180StringRef::size_type StringRef::find_first_of(StringRef Chars, 181 size_t From) const { 182 std::bitset<1 << CHAR_BIT> CharBits; 183 for (size_type i = 0; i != Chars.size(); ++i) 184 CharBits.set((unsigned char)Chars[i]); 185 186 for (size_type i = min(From, Length), e = Length; i != e; ++i) 187 if (CharBits.test((unsigned char)Data[i])) 188 return i; 189 return npos; 190} 191 192/// find_first_not_of - Find the first character in the string that is not 193/// \arg C or npos if not found. 194StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { 195 for (size_type i = min(From, Length), e = Length; i != e; ++i) 196 if (Data[i] != C) 197 return i; 198 return npos; 199} 200 201/// find_first_not_of - Find the first character in the string that is not 202/// in the string \arg Chars, or npos if not found. 203/// 204/// Note: O(size() + Chars.size()) 205StringRef::size_type StringRef::find_first_not_of(StringRef Chars, 206 size_t From) const { 207 std::bitset<1 << CHAR_BIT> CharBits; 208 for (size_type i = 0; i != Chars.size(); ++i) 209 CharBits.set((unsigned char)Chars[i]); 210 211 for (size_type i = min(From, Length), e = Length; i != e; ++i) 212 if (!CharBits.test((unsigned char)Data[i])) 213 return i; 214 return npos; 215} 216 217/// find_last_of - Find the last character in the string that is in \arg C, 218/// or npos if not found. 219/// 220/// Note: O(size() + Chars.size()) 221StringRef::size_type StringRef::find_last_of(StringRef Chars, 222 size_t From) const { 223 std::bitset<1 << CHAR_BIT> CharBits; 224 for (size_type i = 0; i != Chars.size(); ++i) 225 CharBits.set((unsigned char)Chars[i]); 226 227 for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) 228 if (CharBits.test((unsigned char)Data[i])) 229 return i; 230 return npos; 231} 232 233/// find_last_not_of - Find the last character in the string that is not 234/// \arg C, or npos if not found. 235StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const { 236 for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) 237 if (Data[i] != C) 238 return i; 239 return npos; 240} 241 242/// find_last_not_of - Find the last character in the string that is not in 243/// \arg Chars, or npos if not found. 244/// 245/// Note: O(size() + Chars.size()) 246StringRef::size_type StringRef::find_last_not_of(StringRef Chars, 247 size_t From) const { 248 std::bitset<1 << CHAR_BIT> CharBits; 249 for (size_type i = 0, e = Chars.size(); i != e; ++i) 250 CharBits.set((unsigned char)Chars[i]); 251 252 for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) 253 if (!CharBits.test((unsigned char)Data[i])) 254 return i; 255 return npos; 256} 257 258void StringRef::split(SmallVectorImpl<StringRef> &A, 259 StringRef Separators, int MaxSplit, 260 bool KeepEmpty) const { 261 StringRef rest = *this; 262 263 // rest.data() is used to distinguish cases like "a," that splits into 264 // "a" + "" and "a" that splits into "a" + 0. 265 for (int splits = 0; 266 rest.data() != NULL && (MaxSplit < 0 || splits < MaxSplit); 267 ++splits) { 268 std::pair<StringRef, StringRef> p = rest.split(Separators); 269 270 if (KeepEmpty || p.first.size() != 0) 271 A.push_back(p.first); 272 rest = p.second; 273 } 274 // If we have a tail left, add it. 275 if (rest.data() != NULL && (rest.size() != 0 || KeepEmpty)) 276 A.push_back(rest); 277} 278 279//===----------------------------------------------------------------------===// 280// Helpful Algorithms 281//===----------------------------------------------------------------------===// 282 283/// count - Return the number of non-overlapped occurrences of \arg Str in 284/// the string. 285size_t StringRef::count(StringRef Str) const { 286 size_t Count = 0; 287 size_t N = Str.size(); 288 if (N > Length) 289 return 0; 290 for (size_t i = 0, e = Length - N + 1; i != e; ++i) 291 if (substr(i, N).equals(Str)) 292 ++Count; 293 return Count; 294} 295 296static unsigned GetAutoSenseRadix(StringRef &Str) { 297 if (Str.startswith("0x")) { 298 Str = Str.substr(2); 299 return 16; 300 } 301 302 if (Str.startswith("0b")) { 303 Str = Str.substr(2); 304 return 2; 305 } 306 307 if (Str.startswith("0o")) { 308 Str = Str.substr(2); 309 return 8; 310 } 311 312 if (Str.startswith("0")) 313 return 8; 314 315 return 10; 316} 317 318 319/// GetAsUnsignedInteger - Workhorse method that converts a integer character 320/// sequence of radix up to 36 to an unsigned long long value. 321bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix, 322 unsigned long long &Result) { 323 // Autosense radix if not specified. 324 if (Radix == 0) 325 Radix = GetAutoSenseRadix(Str); 326 327 // Empty strings (after the radix autosense) are invalid. 328 if (Str.empty()) return true; 329 330 // Parse all the bytes of the string given this radix. Watch for overflow. 331 Result = 0; 332 while (!Str.empty()) { 333 unsigned CharVal; 334 if (Str[0] >= '0' && Str[0] <= '9') 335 CharVal = Str[0]-'0'; 336 else if (Str[0] >= 'a' && Str[0] <= 'z') 337 CharVal = Str[0]-'a'+10; 338 else if (Str[0] >= 'A' && Str[0] <= 'Z') 339 CharVal = Str[0]-'A'+10; 340 else 341 return true; 342 343 // If the parsed value is larger than the integer radix, the string is 344 // invalid. 345 if (CharVal >= Radix) 346 return true; 347 348 // Add in this character. 349 unsigned long long PrevResult = Result; 350 Result = Result*Radix+CharVal; 351 352 // Check for overflow by shifting back and seeing if bits were lost. 353 if (Result/Radix < PrevResult) 354 return true; 355 356 Str = Str.substr(1); 357 } 358 359 return false; 360} 361 362bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix, 363 long long &Result) { 364 unsigned long long ULLVal; 365 366 // Handle positive strings first. 367 if (Str.empty() || Str.front() != '-') { 368 if (getAsUnsignedInteger(Str, Radix, ULLVal) || 369 // Check for value so large it overflows a signed value. 370 (long long)ULLVal < 0) 371 return true; 372 Result = ULLVal; 373 return false; 374 } 375 376 // Get the positive part of the value. 377 if (getAsUnsignedInteger(Str.substr(1), Radix, ULLVal) || 378 // Reject values so large they'd overflow as negative signed, but allow 379 // "-0". This negates the unsigned so that the negative isn't undefined 380 // on signed overflow. 381 (long long)-ULLVal > 0) 382 return true; 383 384 Result = -ULLVal; 385 return false; 386} 387 388bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { 389 StringRef Str = *this; 390 391 // Autosense radix if not specified. 392 if (Radix == 0) 393 Radix = GetAutoSenseRadix(Str); 394 395 assert(Radix > 1 && Radix <= 36); 396 397 // Empty strings (after the radix autosense) are invalid. 398 if (Str.empty()) return true; 399 400 // Skip leading zeroes. This can be a significant improvement if 401 // it means we don't need > 64 bits. 402 while (!Str.empty() && Str.front() == '0') 403 Str = Str.substr(1); 404 405 // If it was nothing but zeroes.... 406 if (Str.empty()) { 407 Result = APInt(64, 0); 408 return false; 409 } 410 411 // (Over-)estimate the required number of bits. 412 unsigned Log2Radix = 0; 413 while ((1U << Log2Radix) < Radix) Log2Radix++; 414 bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); 415 416 unsigned BitWidth = Log2Radix * Str.size(); 417 if (BitWidth < Result.getBitWidth()) 418 BitWidth = Result.getBitWidth(); // don't shrink the result 419 else if (BitWidth > Result.getBitWidth()) 420 Result = Result.zext(BitWidth); 421 422 APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix 423 if (!IsPowerOf2Radix) { 424 // These must have the same bit-width as Result. 425 RadixAP = APInt(BitWidth, Radix); 426 CharAP = APInt(BitWidth, 0); 427 } 428 429 // Parse all the bytes of the string given this radix. 430 Result = 0; 431 while (!Str.empty()) { 432 unsigned CharVal; 433 if (Str[0] >= '0' && Str[0] <= '9') 434 CharVal = Str[0]-'0'; 435 else if (Str[0] >= 'a' && Str[0] <= 'z') 436 CharVal = Str[0]-'a'+10; 437 else if (Str[0] >= 'A' && Str[0] <= 'Z') 438 CharVal = Str[0]-'A'+10; 439 else 440 return true; 441 442 // If the parsed value is larger than the integer radix, the string is 443 // invalid. 444 if (CharVal >= Radix) 445 return true; 446 447 // Add in this character. 448 if (IsPowerOf2Radix) { 449 Result <<= Log2Radix; 450 Result |= CharVal; 451 } else { 452 Result *= RadixAP; 453 CharAP = CharVal; 454 Result += CharAP; 455 } 456 457 Str = Str.substr(1); 458 } 459 460 return false; 461} 462 463 464// Implementation of StringRef hashing. 465hash_code llvm::hash_value(StringRef S) { 466 return hash_combine_range(S.begin(), S.end()); 467} 468