contrib/llvm/lib/Support/StringRef.cpp

   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/APFloat.h"
  12 #include "llvm/ADT/APInt.h"
  13 #include "llvm/ADT/Hashing.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 // 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]);
  46     if (LHC != RHC)
  47       return LHC < RHC ? -1 : 1;
  48   }
  49   return 0;
  50 }
  51
  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)))
  55     return Res;
  56   if (Length == RHS.Length)
  57     return 0;
  58   return Length < RHS.Length ? -1 : 1;
  59 }
  60
  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;
  65 }
  66
  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;
  71 }
  72
  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);
  76 }
  77
  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.
  85       size_t J;
  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]);
  89         if (ld != rd)
  90           return rd ? -1 : 1;
  91         if (!rd)
  92           break;
  93       }
  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.
  98       I = J - 1;
  99       continue;
 100     }
 101     if (Data[I] != RHS.Data[I])
 102       return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1;
 103   }
 104   if (Length == RHS.Length)
 105     return 0;
 106   return Length < RHS.Length ? -1 : 1;
 107 }
 108
 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);
 117 }
 118
 119 //===----------------------------------------------------------------------===//
 120 // String Operations
 121 //===----------------------------------------------------------------------===//
 122
 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]);
 127   }
 128   return Result;
 129 }
 130
 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]);
 135   }
 136   return Result;
 137 }
 138
 139 //===----------------------------------------------------------------------===//
 140 // String Searching
 141 //===----------------------------------------------------------------------===//
 142
 143
 144 /// find - Search for the first string \arg Str in the string.
 145 ///
 146 /// \return - The index of the first occurrence of \arg Str, or npos if not
 147 /// found.
 148 size_t StringRef::find(StringRef Str, size_t From) const {
 149   if (From > Length)
 150     return npos;
 151
 152   const char *Start = Data + From;
 153   size_t Size = Length - From;
 154
 155   const char *Needle = Str.data();
 156   size_t N = Str.size();
 157   if (N == 0)
 158     return From;
 159   if (Size < N)
 160     return npos;
 161   if (N == 1) {
 162     const char *Ptr = (const char *)::memchr(Start, Needle[0], Size);
 163     return Ptr == nullptr ? npos : Ptr - Data;
 164   }
 165
 166   const char *Stop = Start + (Size - N + 1);
 167
 168   // For short haystacks or unsupported needles fall back to the naive algorithm
 169   if (Size < 16 || N > 255) {
 170     do {
 171       if (std::memcmp(Start, Needle, N) == 0)
 172         return Start - Data;
 173       ++Start;
 174     } while (Start < Stop);
 175     return npos;
 176   }
 177
 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;
 183
 184   do {
 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)
 188         return Start - Data;
 189
 190     // Otherwise skip the appropriate number of bytes.
 191     Start += BadCharSkip[Last];
 192   } while (Start < Stop);
 193
 194   return npos;
 195 }
 196
 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))
 201       return From;
 202     This = This.drop_front();
 203     ++From;
 204   }
 205   return npos;
 206 }
 207
 208 size_t StringRef::rfind_lower(char C, size_t From) const {
 209   From = std::min(From, Length);
 210   size_t i = From;
 211   while (i != 0) {
 212     --i;
 213     if (ascii_tolower(Data[i]) == ascii_tolower(C))
 214       return i;
 215   }
 216   return npos;
 217 }
 218
 219 /// rfind - Search for the last string \arg Str in the string.
 220 ///
 221 /// \return - The index of the last occurrence of \arg Str, or npos if not
 222 /// found.
 223 size_t StringRef::rfind(StringRef Str) const {
 224   size_t N = Str.size();
 225   if (N > Length)
 226     return npos;
 227   for (size_t i = Length - N + 1, e = 0; i != e;) {
 228     --i;
 229     if (substr(i, N).equals(Str))
 230       return i;
 231   }
 232   return npos;
 233 }
 234
 235 size_t StringRef::rfind_lower(StringRef Str) const {
 236   size_t N = Str.size();
 237   if (N > Length)
 238     return npos;
 239   for (size_t i = Length - N + 1, e = 0; i != e;) {
 240     --i;
 241     if (substr(i, N).equals_lower(Str))
 242       return i;
 243   }
 244   return npos;
 245 }
 246
 247 /// find_first_of - Find the first character in the string that is in \arg
 248 /// Chars, or npos if not found.
 249 ///
 250 /// Note: O(size() + Chars.size())
 251 StringRef::size_type StringRef::find_first_of(StringRef Chars,
 252                                               size_t From) const {
 253   std::bitset<1 << CHAR_BIT> CharBits;
 254   for (size_type i = 0; i != Chars.size(); ++i)
 255     CharBits.set((unsigned char)Chars[i]);
 256
 257   for (size_type i = std::min(From, Length), e = Length; i != e; ++i)
 258     if (CharBits.test((unsigned char)Data[i]))
 259       return i;
 260   return npos;
 261 }
 262
 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)
 267     if (Data[i] != C)
 268       return i;
 269   return npos;
 270 }
 271
 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.
 274 ///
 275 /// Note: O(size() + Chars.size())
 276 StringRef::size_type StringRef::find_first_not_of(StringRef Chars,
 277                                                   size_t From) const {
 278   std::bitset<1 << CHAR_BIT> CharBits;
 279   for (size_type i = 0; i != Chars.size(); ++i)
 280     CharBits.set((unsigned char)Chars[i]);
 281
 282   for (size_type i = std::min(From, Length), e = Length; i != e; ++i)
 283     if (!CharBits.test((unsigned char)Data[i]))
 284       return i;
 285   return npos;
 286 }
 287
 288 /// find_last_of - Find the last character in the string that is in \arg C,
 289 /// or npos if not found.
 290 ///
 291 /// Note: O(size() + Chars.size())
 292 StringRef::size_type StringRef::find_last_of(StringRef Chars,
 293                                              size_t From) const {
 294   std::bitset<1 << CHAR_BIT> CharBits;
 295   for (size_type i = 0; i != Chars.size(); ++i)
 296     CharBits.set((unsigned char)Chars[i]);
 297
 298   for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i)
 299     if (CharBits.test((unsigned char)Data[i]))
 300       return i;
 301   return npos;
 302 }
 303
 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)
 308     if (Data[i] != C)
 309       return i;
 310   return npos;
 311 }
 312
 313 /// find_last_not_of - Find the last character in the string that is not in
 314 /// \arg Chars, or npos if not found.
 315 ///
 316 /// Note: O(size() + Chars.size())
 317 StringRef::size_type StringRef::find_last_not_of(StringRef Chars,
 318                                                  size_t From) const {
 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]);
 322
 323   for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i)
 324     if (!CharBits.test((unsigned char)Data[i]))
 325       return i;
 326   return npos;
 327 }
 328
 329 void StringRef::split(SmallVectorImpl<StringRef> &A,
 330                       StringRef Separator, int MaxSplit,
 331                       bool KeepEmpty) const {
 332   StringRef S = *this;
 333
 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);
 340     if (Idx == npos)
 341       break;
 342
 343     // Push this split.
 344     if (KeepEmpty || Idx > 0)
 345       A.push_back(S.slice(0, Idx));
 346
 347     // Jump forward.
 348     S = S.slice(Idx + Separator.size(), npos);
 349   }
 350
 351   // Push the tail.
 352   if (KeepEmpty || !S.empty())
 353     A.push_back(S);
 354 }
 355
 356 void StringRef::split(SmallVectorImpl<StringRef> &A, char Separator,
 357                       int MaxSplit, bool KeepEmpty) const {
 358   StringRef S = *this;
 359
 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);
 366     if (Idx == npos)
 367       break;
 368
 369     // Push this split.
 370     if (KeepEmpty || Idx > 0)
 371       A.push_back(S.slice(0, Idx));
 372
 373     // Jump forward.
 374     S = S.slice(Idx + 1, npos);
 375   }
 376
 377   // Push the tail.
 378   if (KeepEmpty || !S.empty())
 379     A.push_back(S);
 380 }
 381
 382 //===----------------------------------------------------------------------===//
 383 // Helpful Algorithms
 384 //===----------------------------------------------------------------------===//
 385
 386 /// count - Return the number of non-overlapped occurrences of \arg Str in
 387 /// the string.
 388 size_t StringRef::count(StringRef Str) const {
 389   size_t Count = 0;
 390   size_t N = Str.size();
 391   if (N > Length)
 392     return 0;
 393   for (size_t i = 0, e = Length - N + 1; i != e; ++i)
 394     if (substr(i, N).equals(Str))
 395       ++Count;
 396   return Count;
 397 }
 398
 399 static unsigned GetAutoSenseRadix(StringRef &Str) {
 400   if (Str.empty())
 401     return 10;
 402
 403   if (Str.startswith("0x") || Str.startswith("0X")) {
 404     Str = Str.substr(2);
 405     return 16;
 406   }
 407
 408   if (Str.startswith("0b") || Str.startswith("0B")) {
 409     Str = Str.substr(2);
 410     return 2;
 411   }
 412
 413   if (Str.startswith("0o")) {
 414     Str = Str.substr(2);
 415     return 8;
 416   }
 417
 418   if (Str[0] == '0' && Str.size() > 1 && ascii_isdigit(Str[1])) {
 419     Str = Str.substr(1);
 420     return 8;
 421   }
 422
 423   return 10;
 424 }
 425
 426 bool llvm::consumeUnsignedInteger(StringRef &Str, unsigned Radix,
 427                                   unsigned long long &Result) {
 428   // Autosense radix if not specified.
 429   if (Radix == 0)
 430     Radix = GetAutoSenseRadix(Str);
 431
 432   // Empty strings (after the radix autosense) are invalid.
 433   if (Str.empty()) return true;
 434
 435   // Parse all the bytes of the string given this radix.  Watch for overflow.
 436   StringRef Str2 = Str;
 437   Result = 0;
 438   while (!Str2.empty()) {
 439     unsigned CharVal;
 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;
 446     else
 447       break;
 448
 449     // If the parsed value is larger than the integer radix, we cannot
 450     // consume any more characters.
 451     if (CharVal >= Radix)
 452       break;
 453
 454     // Add in this character.
 455     unsigned long long PrevResult = Result;
 456     Result = Result * Radix + CharVal;
 457
 458     // Check for overflow by shifting back and seeing if bits were lost.
 459     if (Result / Radix < PrevResult)
 460       return true;
 461
 462     Str2 = Str2.substr(1);
 463   }
 464
 465   // We consider the operation a failure if no characters were consumed
 466   // successfully.
 467   if (Str.size() == Str2.size())
 468     return true;
 469
 470   Str = Str2;
 471   return false;
 472 }
 473
 474 bool llvm::consumeSignedInteger(StringRef &Str, unsigned Radix,
 475                                 long long &Result) {
 476   unsigned long long ULLVal;
 477
 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)
 483       return true;
 484     Result = ULLVal;
 485     return false;
 486   }
 487
 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)
 495     return true;
 496
 497   Str = Str2;
 498   Result = -ULLVal;
 499   return false;
 500 }
 501
 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))
 507     return true;
 508
 509   // For getAsUnsignedInteger, we require the whole string to be consumed or
 510   // else we consider it a failure.
 511   return !Str.empty();
 512 }
 513
 514 bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix,
 515                               long long &Result) {
 516   if (consumeSignedInteger(Str, Radix, Result))
 517     return true;
 518
 519   // For getAsSignedInteger, we require the whole string to be consumed or else
 520   // we consider it a failure.
 521   return !Str.empty();
 522 }
 523
 524 bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const {
 525   StringRef Str = *this;
 526
 527   // Autosense radix if not specified.
 528   if (Radix == 0)
 529     Radix = GetAutoSenseRadix(Str);
 530
 531   assert(Radix > 1 && Radix <= 36);
 532
 533   // Empty strings (after the radix autosense) are invalid.
 534   if (Str.empty()) return true;
 535
 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')
 539     Str = Str.substr(1);
 540
 541   // If it was nothing but zeroes....
 542   if (Str.empty()) {
 543     Result = APInt(64, 0);
 544     return false;
 545   }
 546
 547   // (Over-)estimate the required number of bits.
 548   unsigned Log2Radix = 0;
 549   while ((1U << Log2Radix) < Radix) Log2Radix++;
 550   bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix);
 551
 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);
 557
 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);
 563   }
 564
 565   // Parse all the bytes of the string given this radix.
 566   Result = 0;
 567   while (!Str.empty()) {
 568     unsigned CharVal;
 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;
 575     else
 576       return true;
 577
 578     // If the parsed value is larger than the integer radix, the string is
 579     // invalid.
 580     if (CharVal >= Radix)
 581       return true;
 582
 583     // Add in this character.
 584     if (IsPowerOf2Radix) {
 585       Result <<= Log2Radix;
 586       Result |= CharVal;
 587     } else {
 588       Result *= RadixAP;
 589       CharAP = CharVal;
 590       Result += CharAP;
 591     }
 592
 593     Str = Str.substr(1);
 594   }
 595
 596   return false;
 597 }
 598
 599 bool StringRef::getAsDouble(double &Result, bool AllowInexact) const {
 600   APFloat F(0.0);
 601   APFloat::opStatus Status =
 602       F.convertFromString(*this, APFloat::rmNearestTiesToEven);
 603   if (Status != APFloat::opOK) {
 604     if (!AllowInexact || Status != APFloat::opInexact)
 605       return true;
 606   }
 607
 608   Result = F.convertToDouble();
 609   return false;
 610 }
 611
 612 // Implementation of StringRef hashing.
 613 hash_code llvm::hash_value(StringRef S) {
 614   return hash_combine_range(S.begin(), S.end());
 615 }