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 17 using namespace llvm; 18 19 // MSVC emits references to this into the translation units which reference it. 20 #ifndef _MSC_VER 21 const size_t StringRef::npos; 22 #endif 23 24 static char ascii_tolower(char x) { 25 if (x >= 'A' && x <= 'Z') 26 return x - 'A' + 'a'; 27 return x; 28 } 29 30 static char ascii_toupper(char x) { 31 if (x >= 'a' && x <= 'z') 32 return x - 'a' + 'A'; 33 return x; 34 } 35 36 static bool ascii_isdigit(char x) { 37 return x >= '0' && x <= '9'; 38 } 39 40 /// compare_lower - Compare strings, ignoring case. 41 int 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. 55 int 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. 86 unsigned 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 99 std::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 107 std::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. 124 size_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. 164 size_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()) 180 StringRef::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. 194 StringRef::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()) 205 StringRef::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()) 221 StringRef::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. 235 StringRef::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()) 246 StringRef::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 258 void 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. 285 size_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 296 static 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. 321 bool 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 362 bool 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 388 bool 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. 465 hash_code llvm::hash_value(StringRef S) { 466 return hash_combine_range(S.begin(), S.end()); 467 } 468