X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FStringRef.cpp;h=7ecff2964c517f25274740f12adc8a9b7b114e18;hb=4b85564ba4a41465155b9128a68e5e14fea78365;hp=e577b954c553a3fcda63ad3ad2efaf76684d14b4;hpb=ad6b6da8aafa88fa3bd002f2595121e1227c4b93;p=oota-llvm.git diff --git a/lib/Support/StringRef.cpp b/lib/Support/StringRef.cpp index e577b954c55..7ecff2964c5 100644 --- a/lib/Support/StringRef.cpp +++ b/lib/Support/StringRef.cpp @@ -8,7 +8,10 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/StringRef.h" -#include +#include "llvm/ADT/APInt.h" +#include "llvm/ADT/Hashing.h" +#include "llvm/ADT/edit_distance.h" +#include using namespace llvm; @@ -23,73 +26,107 @@ static char ascii_tolower(char x) { return x; } -/// compare_lower - Compare strings, ignoring case. -int StringRef::compare_lower(StringRef RHS) const { - for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { - char LHC = ascii_tolower(Data[I]); - char RHC = ascii_tolower(RHS.Data[I]); +static char ascii_toupper(char x) { + if (x >= 'a' && x <= 'z') + return x - 'a' + 'A'; + return x; +} + +static bool ascii_isdigit(char x) { + return x >= '0' && x <= '9'; +} + +// strncasecmp() is not available on non-POSIX systems, so define an +// alternative function here. +static int ascii_strncasecmp(const char *LHS, const char *RHS, size_t Length) { + for (size_t I = 0; I < Length; ++I) { + unsigned char LHC = ascii_tolower(LHS[I]); + unsigned char RHC = ascii_tolower(RHS[I]); if (LHC != RHC) return LHC < RHC ? -1 : 1; } + return 0; +} +/// compare_lower - Compare strings, ignoring case. +int StringRef::compare_lower(StringRef RHS) const { + if (int Res = ascii_strncasecmp(Data, RHS.Data, std::min(Length, RHS.Length))) + return Res; if (Length == RHS.Length) - return 0; + return 0; return Length < RHS.Length ? -1 : 1; } -// Compute the edit distance between the two given strings. -unsigned StringRef::edit_distance(llvm::StringRef Other, - bool AllowReplacements) { - // The algorithm implemented below is the "classic" - // dynamic-programming algorithm for computing the Levenshtein - // distance, which is described here: - // - // http://en.wikipedia.org/wiki/Levenshtein_distance - // - // Although the algorithm is typically described using an m x n - // array, only two rows are used at a time, so this implemenation - // just keeps two separate vectors for those two rows. - size_type m = size(); - size_type n = Other.size(); - - unsigned SmallPrevious[32]; - unsigned SmallCurrent[32]; - - unsigned *previous = SmallPrevious; - unsigned *current = SmallCurrent; - if (n + 1 > 32) { - previous = new unsigned [n+1]; - current = new unsigned [n+1]; - } - - for (unsigned i = 0; i <= n; ++i) - previous[i] = i; - - for (size_type y = 1; y <= m; ++y) { - std::memset(current, 0, (n + 1) * sizeof(unsigned)); - current[0] = y; - for (size_type x = 1; x <= n; ++x) { - if (AllowReplacements) { - current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u), - min(current[x-1], previous[x])+1); - } - else { - if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1]; - else current[x] = min(current[x-1], previous[x]) + 1; +/// Check if this string starts with the given \p Prefix, ignoring case. +bool StringRef::startswith_lower(StringRef Prefix) const { + return Length >= Prefix.Length && + ascii_strncasecmp(Data, Prefix.Data, Prefix.Length) == 0; +} + +/// Check if this string ends with the given \p Suffix, ignoring case. +bool StringRef::endswith_lower(StringRef Suffix) const { + return Length >= Suffix.Length && + ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0; +} + +/// compare_numeric - Compare strings, handle embedded numbers. +int StringRef::compare_numeric(StringRef RHS) const { + for (size_t I = 0, E = std::min(Length, RHS.Length); I != E; ++I) { + // Check for sequences of digits. + if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) { + // The longer sequence of numbers is considered larger. + // This doesn't really handle prefixed zeros well. + size_t J; + for (J = I + 1; J != E + 1; ++J) { + bool ld = J < Length && ascii_isdigit(Data[J]); + bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]); + if (ld != rd) + return rd ? -1 : 1; + if (!rd) + break; } + // The two number sequences have the same length (J-I), just memcmp them. + if (int Res = compareMemory(Data + I, RHS.Data + I, J - I)) + return Res < 0 ? -1 : 1; + // Identical number sequences, continue search after the numbers. + I = J - 1; + continue; } - - unsigned *tmp = current; - current = previous; - previous = tmp; + if (Data[I] != RHS.Data[I]) + return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; } + if (Length == RHS.Length) + return 0; + return Length < RHS.Length ? -1 : 1; +} + +// Compute the edit distance between the two given strings. +unsigned StringRef::edit_distance(llvm::StringRef Other, + bool AllowReplacements, + unsigned MaxEditDistance) const { + return llvm::ComputeEditDistance( + makeArrayRef(data(), size()), + makeArrayRef(Other.data(), Other.size()), + AllowReplacements, MaxEditDistance); +} + +//===----------------------------------------------------------------------===// +// String Operations +//===----------------------------------------------------------------------===// - unsigned Result = previous[n]; - if (n + 1 > 32) { - delete [] previous; - delete [] current; +std::string StringRef::lower() const { + std::string Result(size(), char()); + for (size_type i = 0, e = size(); i != e; ++i) { + Result[i] = ascii_tolower(Data[i]); + } + return Result; +} + +std::string StringRef::upper() const { + std::string Result(size(), char()); + for (size_type i = 0, e = size(); i != e; ++i) { + Result[i] = ascii_toupper(Data[i]); } - return Result; } @@ -100,21 +137,54 @@ unsigned StringRef::edit_distance(llvm::StringRef Other, /// find - Search for the first string \arg Str in the string. /// -/// \return - The index of the first occurence of \arg Str, or npos if not +/// \return - The index of the first occurrence of \arg Str, or npos if not /// found. size_t StringRef::find(StringRef Str, size_t From) const { + if (From > Length) + return npos; + + const char *Needle = Str.data(); size_t N = Str.size(); - if (N > Length) + if (N == 0) + return From; + + size_t Size = Length - From; + if (Size < N) return npos; - for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i) - if (substr(i, N).equals(Str)) - return i; + + const char *Start = Data + From; + const char *Stop = Start + (Size - N + 1); + + // For short haystacks or unsupported needles fall back to the naive algorithm + if (Size < 16 || N > 255) { + do { + if (std::memcmp(Start, Needle, N) == 0) + return Start - Data; + ++Start; + } while (Start < Stop); + return npos; + } + + // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. + uint8_t BadCharSkip[256]; + std::memset(BadCharSkip, N, 256); + for (unsigned i = 0; i != N-1; ++i) + BadCharSkip[(uint8_t)Str[i]] = N-1-i; + + do { + if (std::memcmp(Start, Needle, N) == 0) + return Start - Data; + + // Otherwise skip the appropriate number of bytes. + Start += BadCharSkip[(uint8_t)Start[N-1]]; + } while (Start < Stop); + return npos; } /// rfind - Search for the last string \arg Str in the string. /// -/// \return - The index of the last occurence of \arg Str, or npos if not +/// \return - The index of the last occurrence of \arg Str, or npos if not /// found. size_t StringRef::rfind(StringRef Str) const { size_t N = Str.size(); @@ -131,11 +201,15 @@ size_t StringRef::rfind(StringRef Str) const { /// find_first_of - Find the first character in the string that is in \arg /// Chars, or npos if not found. /// -/// Note: O(size() * Chars.size()) +/// Note: O(size() + Chars.size()) StringRef::size_type StringRef::find_first_of(StringRef Chars, size_t From) const { - for (size_type i = min(From, Length), e = Length; i != e; ++i) - if (Chars.find(Data[i]) != npos) + std::bitset<1 << CHAR_BIT> CharBits; + for (size_type i = 0; i != Chars.size(); ++i) + CharBits.set((unsigned char)Chars[i]); + + for (size_type i = std::min(From, Length), e = Length; i != e; ++i) + if (CharBits.test((unsigned char)Data[i])) return i; return npos; } @@ -143,7 +217,7 @@ StringRef::size_type StringRef::find_first_of(StringRef Chars, /// find_first_not_of - Find the first character in the string that is not /// \arg C or npos if not found. StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { - for (size_type i = min(From, Length), e = Length; i != e; ++i) + for (size_type i = std::min(From, Length), e = Length; i != e; ++i) if (Data[i] != C) return i; return npos; @@ -152,15 +226,112 @@ StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { /// find_first_not_of - Find the first character in the string that is not /// in the string \arg Chars, or npos if not found. /// -/// Note: O(size() * Chars.size()) +/// Note: O(size() + Chars.size()) StringRef::size_type StringRef::find_first_not_of(StringRef Chars, size_t From) const { - for (size_type i = min(From, Length), e = Length; i != e; ++i) - if (Chars.find(Data[i]) == npos) + std::bitset<1 << CHAR_BIT> CharBits; + for (size_type i = 0; i != Chars.size(); ++i) + CharBits.set((unsigned char)Chars[i]); + + for (size_type i = std::min(From, Length), e = Length; i != e; ++i) + if (!CharBits.test((unsigned char)Data[i])) return i; return npos; } +/// find_last_of - Find the last character in the string that is in \arg C, +/// or npos if not found. +/// +/// Note: O(size() + Chars.size()) +StringRef::size_type StringRef::find_last_of(StringRef Chars, + size_t From) const { + std::bitset<1 << CHAR_BIT> CharBits; + for (size_type i = 0; i != Chars.size(); ++i) + CharBits.set((unsigned char)Chars[i]); + + for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) + if (CharBits.test((unsigned char)Data[i])) + return i; + return npos; +} + +/// find_last_not_of - Find the last character in the string that is not +/// \arg C, or npos if not found. +StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const { + for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) + if (Data[i] != C) + return i; + return npos; +} + +/// find_last_not_of - Find the last character in the string that is not in +/// \arg Chars, or npos if not found. +/// +/// Note: O(size() + Chars.size()) +StringRef::size_type StringRef::find_last_not_of(StringRef Chars, + size_t From) const { + std::bitset<1 << CHAR_BIT> CharBits; + for (size_type i = 0, e = Chars.size(); i != e; ++i) + CharBits.set((unsigned char)Chars[i]); + + for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) + if (!CharBits.test((unsigned char)Data[i])) + return i; + return npos; +} + +void StringRef::split(SmallVectorImpl &A, + StringRef Separator, int MaxSplit, + bool KeepEmpty) const { + StringRef S = *this; + + // Count down from MaxSplit. When MaxSplit is -1, this will just split + // "forever". This doesn't support splitting more than 2^31 times + // intentionally; if we ever want that we can make MaxSplit a 64-bit integer + // but that seems unlikely to be useful. + while (MaxSplit-- != 0) { + size_t Idx = S.find(Separator); + if (Idx == npos) + break; + + // Push this split. + if (KeepEmpty || Idx > 0) + A.push_back(S.slice(0, Idx)); + + // Jump forward. + S = S.slice(Idx + Separator.size(), npos); + } + + // Push the tail. + if (KeepEmpty || !S.empty()) + A.push_back(S); +} + +void StringRef::split(SmallVectorImpl &A, char Separator, + int MaxSplit, bool KeepEmpty) const { + StringRef S = *this; + + // Count down from MaxSplit. When MaxSplit is -1, this will just split + // "forever". This doesn't support splitting more than 2^31 times + // intentionally; if we ever want that we can make MaxSplit a 64-bit integer + // but that seems unlikely to be useful. + while (MaxSplit-- != 0) { + size_t Idx = S.find(Separator); + if (Idx == npos) + break; + + // Push this split. + if (KeepEmpty || Idx > 0) + A.push_back(S.slice(0, Idx)); + + // Jump forward. + S = S.slice(Idx + 1, npos); + } + + // Push the tail. + if (KeepEmpty || !S.empty()) + A.push_back(S); +} //===----------------------------------------------------------------------===// // Helpful Algorithms @@ -179,27 +350,40 @@ size_t StringRef::count(StringRef Str) const { return Count; } +static unsigned GetAutoSenseRadix(StringRef &Str) { + if (Str.startswith("0x")) { + Str = Str.substr(2); + return 16; + } + + if (Str.startswith("0b")) { + Str = Str.substr(2); + return 2; + } + + if (Str.startswith("0o")) { + Str = Str.substr(2); + return 8; + } + + if (Str.startswith("0")) + return 8; + + return 10; +} + + /// GetAsUnsignedInteger - Workhorse method that converts a integer character /// sequence of radix up to 36 to an unsigned long long value. -static bool GetAsUnsignedInteger(StringRef Str, unsigned Radix, - unsigned long long &Result) { +bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix, + unsigned long long &Result) { // Autosense radix if not specified. - if (Radix == 0) { - if (Str.startswith("0x")) { - Str = Str.substr(2); - Radix = 16; - } else if (Str.startswith("0b")) { - Str = Str.substr(2); - Radix = 2; - } else if (Str.startswith("0")) - Radix = 8; - else - Radix = 10; - } - + if (Radix == 0) + Radix = GetAutoSenseRadix(Str); + // Empty strings (after the radix autosense) are invalid. if (Str.empty()) return true; - + // Parse all the bytes of the string given this radix. Watch for overflow. Result = 0; while (!Str.empty()) { @@ -212,70 +396,129 @@ static bool GetAsUnsignedInteger(StringRef Str, unsigned Radix, CharVal = Str[0]-'A'+10; else return true; - + // If the parsed value is larger than the integer radix, the string is // invalid. if (CharVal >= Radix) return true; - + // Add in this character. unsigned long long PrevResult = Result; Result = Result*Radix+CharVal; - - // Check for overflow. - if (Result < PrevResult) + + // Check for overflow by shifting back and seeing if bits were lost. + if (Result/Radix < PrevResult) return true; Str = Str.substr(1); } - - return false; -} -bool StringRef::getAsInteger(unsigned Radix, unsigned long long &Result) const { - return GetAsUnsignedInteger(*this, Radix, Result); + return false; } - -bool StringRef::getAsInteger(unsigned Radix, long long &Result) const { +bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix, + long long &Result) { unsigned long long ULLVal; - + // Handle positive strings first. - if (empty() || front() != '-') { - if (GetAsUnsignedInteger(*this, Radix, ULLVal) || + if (Str.empty() || Str.front() != '-') { + if (getAsUnsignedInteger(Str, Radix, ULLVal) || // Check for value so large it overflows a signed value. (long long)ULLVal < 0) return true; Result = ULLVal; return false; } - + // Get the positive part of the value. - if (GetAsUnsignedInteger(substr(1), Radix, ULLVal) || + if (getAsUnsignedInteger(Str.substr(1), Radix, ULLVal) || // Reject values so large they'd overflow as negative signed, but allow // "-0". This negates the unsigned so that the negative isn't undefined // on signed overflow. (long long)-ULLVal > 0) return true; - + Result = -ULLVal; return false; } -bool StringRef::getAsInteger(unsigned Radix, int &Result) const { - long long Val; - if (getAsInteger(Radix, Val) || - (int)Val != Val) - return true; - Result = Val; +bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { + StringRef Str = *this; + + // Autosense radix if not specified. + if (Radix == 0) + Radix = GetAutoSenseRadix(Str); + + assert(Radix > 1 && Radix <= 36); + + // Empty strings (after the radix autosense) are invalid. + if (Str.empty()) return true; + + // Skip leading zeroes. This can be a significant improvement if + // it means we don't need > 64 bits. + while (!Str.empty() && Str.front() == '0') + Str = Str.substr(1); + + // If it was nothing but zeroes.... + if (Str.empty()) { + Result = APInt(64, 0); + return false; + } + + // (Over-)estimate the required number of bits. + unsigned Log2Radix = 0; + while ((1U << Log2Radix) < Radix) Log2Radix++; + bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); + + unsigned BitWidth = Log2Radix * Str.size(); + if (BitWidth < Result.getBitWidth()) + BitWidth = Result.getBitWidth(); // don't shrink the result + else if (BitWidth > Result.getBitWidth()) + Result = Result.zext(BitWidth); + + APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix + if (!IsPowerOf2Radix) { + // These must have the same bit-width as Result. + RadixAP = APInt(BitWidth, Radix); + CharAP = APInt(BitWidth, 0); + } + + // Parse all the bytes of the string given this radix. + Result = 0; + while (!Str.empty()) { + unsigned CharVal; + if (Str[0] >= '0' && Str[0] <= '9') + CharVal = Str[0]-'0'; + else if (Str[0] >= 'a' && Str[0] <= 'z') + CharVal = Str[0]-'a'+10; + else if (Str[0] >= 'A' && Str[0] <= 'Z') + CharVal = Str[0]-'A'+10; + else + return true; + + // If the parsed value is larger than the integer radix, the string is + // invalid. + if (CharVal >= Radix) + return true; + + // Add in this character. + if (IsPowerOf2Radix) { + Result <<= Log2Radix; + Result |= CharVal; + } else { + Result *= RadixAP; + CharAP = CharVal; + Result += CharAP; + } + + Str = Str.substr(1); + } + return false; } -bool StringRef::getAsInteger(unsigned Radix, unsigned &Result) const { - unsigned long long Val; - if (getAsInteger(Radix, Val) || - (unsigned)Val != Val) - return true; - Result = Val; - return false; -} + +// Implementation of StringRef hashing. +hash_code llvm::hash_value(StringRef S) { + return hash_combine_range(S.begin(), S.end()); +}