1e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar//===-- StringRef.cpp - Lightweight String References ---------------------===// 2e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar// 3e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar// The LLVM Compiler Infrastructure 4e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar// 5e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar// This file is distributed under the University of Illinois Open Source 6e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar// License. See LICENSE.TXT for details. 7e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar// 8e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar//===----------------------------------------------------------------------===// 9e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar 10e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar#include "llvm/ADT/StringRef.h" 111e7ad3993d8700488895fa372ecad55443f53485John McCall#include "llvm/ADT/APInt.h" 12528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth#include "llvm/ADT/Hashing.h" 1301d53ec176a6be4585df1f43af11151988ca4b35Kaelyn Uhrain#include "llvm/ADT/edit_distance.h" 14250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer#include <bitset> 15ad6b6da8aafa88fa3bd002f2595121e1227c4b93Douglas Gregor 16e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbarusing namespace llvm; 17e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbar 1877696bebbcb011be861571b105193fc53614c153Daniel Dunbar// MSVC emits references to this into the translation units which reference it. 1977696bebbcb011be861571b105193fc53614c153Daniel Dunbar#ifndef _MSC_VER 20e65512809a4144c17538aac4cc59fac6d325a7e4Daniel Dunbarconst size_t StringRef::npos; 2177696bebbcb011be861571b105193fc53614c153Daniel Dunbar#endif 22cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner 2305872ea804cdc9534960b30d28a391928c61481aBenjamin Kramerstatic char ascii_tolower(char x) { 2405872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer if (x >= 'A' && x <= 'Z') 2505872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer return x - 'A' + 'a'; 2605872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer return x; 2705872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer} 2805872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer 29589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbarstatic char ascii_toupper(char x) { 30589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar if (x >= 'a' && x <= 'z') 31589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar return x - 'a' + 'A'; 32589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar return x; 33589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar} 34589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar 35160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesenstatic bool ascii_isdigit(char x) { 36160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen return x >= '0' && x <= '9'; 37160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen} 38160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen 39f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama// strncasecmp() is not available on non-POSIX systems, so define an 40f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama// alternative function here. 41f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyamastatic int ascii_strncasecmp(const char *LHS, const char *RHS, size_t Length) { 42f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama for (size_t I = 0; I < Length; ++I) { 43f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama unsigned char LHC = ascii_tolower(LHS[I]); 44f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama unsigned char RHC = ascii_tolower(RHS[I]); 4505872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer if (LHC != RHC) 4605872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer return LHC < RHC ? -1 : 1; 4705872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer } 48f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama return 0; 49f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama} 5005872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer 51f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama/// compare_lower - Compare strings, ignoring case. 52f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyamaint StringRef::compare_lower(StringRef RHS) const { 5337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines if (int Res = ascii_strncasecmp(Data, RHS.Data, std::min(Length, RHS.Length))) 54f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama return Res; 5505872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer if (Length == RHS.Length) 560043e35b8261af607d6cf0695b79b1d6584e67acBenjamin Kramer return 0; 5705872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer return Length < RHS.Length ? -1 : 1; 5805872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer} 5905872ea804cdc9534960b30d28a391928c61481aBenjamin Kramer 60f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama/// Check if this string starts with the given \p Prefix, ignoring case. 61f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyamabool StringRef::startswith_lower(StringRef Prefix) const { 62f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama return Length >= Prefix.Length && 63f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama ascii_strncasecmp(Data, Prefix.Data, Prefix.Length) == 0; 64f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama} 65f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama 66f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama/// Check if this string ends with the given \p Suffix, ignoring case. 67f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyamabool StringRef::endswith_lower(StringRef Suffix) const { 68f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama return Length >= Suffix.Length && 69f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0; 70f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama} 71f34c3ca3046378bdb7e49b7366bafca0e0bafb9aRui Ueyama 72160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen/// compare_numeric - Compare strings, handle embedded numbers. 73160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesenint StringRef::compare_numeric(StringRef RHS) const { 7437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_t I = 0, E = std::min(Length, RHS.Length); I != E; ++I) { 757850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen // Check for sequences of digits. 76160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) { 777850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen // The longer sequence of numbers is considered larger. 787850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen // This doesn't really handle prefixed zeros well. 797850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen size_t J; 807850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen for (J = I + 1; J != E + 1; ++J) { 81160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen bool ld = J < Length && ascii_isdigit(Data[J]); 82160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]); 83160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen if (ld != rd) 84160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen return rd ? -1 : 1; 85160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen if (!rd) 86160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen break; 87160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen } 887850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen // The two number sequences have the same length (J-I), just memcmp them. 897850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen if (int Res = compareMemory(Data + I, RHS.Data + I, J - I)) 907850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen return Res < 0 ? -1 : 1; 917850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen // Identical number sequences, continue search after the numbers. 927850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen I = J - 1; 937850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen continue; 94160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen } 957850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen if (Data[I] != RHS.Data[I]) 967850dd0f25ccc5da6df54999a907e1277ed055d6Jakob Stoklund Olesen return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; 97160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen } 98160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen if (Length == RHS.Length) 990043e35b8261af607d6cf0695b79b1d6584e67acBenjamin Kramer return 0; 100160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen return Length < RHS.Length ? -1 : 1; 101160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen} 102160a3bf74d1a2b048f65e2162d038ed96eddde01Jakob Stoklund Olesen 1037e54d5b1562f085c898bf8fcc4ac939ec893444cDouglas Gregor// Compute the edit distance between the two given strings. 104326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencerunsigned StringRef::edit_distance(llvm::StringRef Other, 1055ee568ac2704d7302017d42ad162d4b53d076cbcDouglas Gregor bool AllowReplacements, 1064a48389b27cafe30a38592b50e0f4b9e97b9d65eDmitri Gribenko unsigned MaxEditDistance) const { 10701d53ec176a6be4585df1f43af11151988ca4b35Kaelyn Uhrain return llvm::ComputeEditDistance( 10837ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines makeArrayRef(data(), size()), 10937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines makeArrayRef(Other.data(), Other.size()), 11001d53ec176a6be4585df1f43af11151988ca4b35Kaelyn Uhrain AllowReplacements, MaxEditDistance); 111441c8b4ad17c0d029b2247c367111395e7ad068cDouglas Gregor} 112441c8b4ad17c0d029b2247c367111395e7ad068cDouglas Gregor 11305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner//===----------------------------------------------------------------------===// 114589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar// String Operations 115589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar//===----------------------------------------------------------------------===// 116589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar 117589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbarstd::string StringRef::lower() const { 118589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar std::string Result(size(), char()); 119589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar for (size_type i = 0, e = size(); i != e; ++i) { 120589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar Result[i] = ascii_tolower(Data[i]); 121589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar } 122589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar return Result; 123589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar} 124589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar 125589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbarstd::string StringRef::upper() const { 126589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar std::string Result(size(), char()); 127589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar for (size_type i = 0, e = size(); i != e; ++i) { 128a7b966fc8d63b9b9432e1b33b33d4be6179e1fffBenjamin Kramer Result[i] = ascii_toupper(Data[i]); 129589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar } 130589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar return Result; 131589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar} 132589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar 133589fbb1770df5f7bee1c5e24e9e8f4ca5091d528Daniel Dunbar//===----------------------------------------------------------------------===// 13405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner// String Searching 13505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner//===----------------------------------------------------------------------===// 13605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 13705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 13805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// find - Search for the first string \arg Str in the string. 13905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// 1407a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// \return - The index of the first occurrence of \arg Str, or npos if not 14105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// found. 14264066bd8b593082f622bbc25716938a453363d2fDaniel Dunbarsize_t StringRef::find(StringRef Str, size_t From) const { 14305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t N = Str.size(); 14405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (N > Length) 14505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 1466e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 1476e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer // For short haystacks or unsupported needles fall back to the naive algorithm 1486e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer if (Length < 16 || N > 255 || N == 0) { 14937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_t e = Length - N + 1, i = std::min(From, e); i != e; ++i) 1506e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer if (substr(i, N).equals(Str)) 1516e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer return i; 1526e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer return npos; 1536e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer } 1546e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 155e7a0719161ebc3600d3f584901ab8e2276acdb59Benjamin Kramer if (From >= Length) 156e7a0719161ebc3600d3f584901ab8e2276acdb59Benjamin Kramer return npos; 157e7a0719161ebc3600d3f584901ab8e2276acdb59Benjamin Kramer 1586e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. 1596e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer uint8_t BadCharSkip[256]; 1606e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer std::memset(BadCharSkip, N, 256); 1616e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer for (unsigned i = 0; i != N-1; ++i) 1626e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer BadCharSkip[(uint8_t)Str[i]] = N-1-i; 1636e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 164e7a0719161ebc3600d3f584901ab8e2276acdb59Benjamin Kramer unsigned Len = Length-From, Pos = From; 1656e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer while (Len >= N) { 1666e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer if (substr(Pos, N).equals(Str)) // See if this is the correct substring. 1676e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer return Pos; 1686e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 1696e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer // Otherwise skip the appropriate number of bytes. 170e7a0719161ebc3600d3f584901ab8e2276acdb59Benjamin Kramer uint8_t Skip = BadCharSkip[(uint8_t)(*this)[Pos+N-1]]; 1716e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer Len -= Skip; 1726e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer Pos += Skip; 1736e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer } 1746e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 17505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 17605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 17705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 17805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// rfind - Search for the last string \arg Str in the string. 17905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// 1807a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// \return - The index of the last occurrence of \arg Str, or npos if not 18105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// found. 1822928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarsize_t StringRef::rfind(StringRef Str) const { 18305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t N = Str.size(); 18405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (N > Length) 18505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 18605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner for (size_t i = Length - N + 1, e = 0; i != e;) { 18705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner --i; 18805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (substr(i, N).equals(Str)) 18905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return i; 19005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner } 19105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 19205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 19305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 19464066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// find_first_of - Find the first character in the string that is in \arg 19564066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// Chars, or npos if not found. 19664066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// 197250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer/// Note: O(size() + Chars.size()) 19864066bd8b593082f622bbc25716938a453363d2fDaniel DunbarStringRef::size_type StringRef::find_first_of(StringRef Chars, 19964066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar size_t From) const { 200250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer std::bitset<1 << CHAR_BIT> CharBits; 201250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer for (size_type i = 0; i != Chars.size(); ++i) 202250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer CharBits.set((unsigned char)Chars[i]); 203250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer 20437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length), e = Length; i != e; ++i) 205250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer if (CharBits.test((unsigned char)Data[i])) 20605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return i; 20705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 20805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 20905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 21005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// find_first_not_of - Find the first character in the string that is not 21164066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// \arg C or npos if not found. 21264066bd8b593082f622bbc25716938a453363d2fDaniel DunbarStringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { 21337ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length), e = Length; i != e; ++i) 21464066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar if (Data[i] != C) 21564066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar return i; 21664066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar return npos; 21764066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar} 21864066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar 21964066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// find_first_not_of - Find the first character in the string that is not 22064066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// in the string \arg Chars, or npos if not found. 22164066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// 222250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer/// Note: O(size() + Chars.size()) 22364066bd8b593082f622bbc25716938a453363d2fDaniel DunbarStringRef::size_type StringRef::find_first_not_of(StringRef Chars, 22464066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar size_t From) const { 225250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer std::bitset<1 << CHAR_BIT> CharBits; 226250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer for (size_type i = 0; i != Chars.size(); ++i) 227250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer CharBits.set((unsigned char)Chars[i]); 228250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer 22937ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length), e = Length; i != e; ++i) 230250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer if (!CharBits.test((unsigned char)Data[i])) 23105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return i; 23205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 23305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 23405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 23563c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// find_last_of - Find the last character in the string that is in \arg C, 23663c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// or npos if not found. 23763c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// 23863c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// Note: O(size() + Chars.size()) 23963c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. SpencerStringRef::size_type StringRef::find_last_of(StringRef Chars, 24063c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer size_t From) const { 24163c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer std::bitset<1 << CHAR_BIT> CharBits; 24263c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer for (size_type i = 0; i != Chars.size(); ++i) 24363c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer CharBits.set((unsigned char)Chars[i]); 24463c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer 24537ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) 24663c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer if (CharBits.test((unsigned char)Data[i])) 24763c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer return i; 24863c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer return npos; 24963c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer} 25005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 251b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// find_last_not_of - Find the last character in the string that is not 252b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// \arg C, or npos if not found. 253b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. SpencerStringRef::size_type StringRef::find_last_not_of(char C, size_t From) const { 25437ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) 255b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer if (Data[i] != C) 256b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return i; 257b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return npos; 258b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer} 259b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer 260b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// find_last_not_of - Find the last character in the string that is not in 261b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// \arg Chars, or npos if not found. 262b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// 263b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// Note: O(size() + Chars.size()) 264b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. SpencerStringRef::size_type StringRef::find_last_not_of(StringRef Chars, 265b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer size_t From) const { 266b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer std::bitset<1 << CHAR_BIT> CharBits; 267b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer for (size_type i = 0, e = Chars.size(); i != e; ++i) 268b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer CharBits.set((unsigned char)Chars[i]); 269b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer 27037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) 271b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer if (!CharBits.test((unsigned char)Data[i])) 272b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return i; 273b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return npos; 274b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer} 275b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer 276bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sandsvoid StringRef::split(SmallVectorImpl<StringRef> &A, 277bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands StringRef Separators, int MaxSplit, 278bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands bool KeepEmpty) const { 279bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands StringRef rest = *this; 280bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands 281bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands // rest.data() is used to distinguish cases like "a," that splits into 282bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands // "a" + "" and "a" that splits into "a" + 0. 283bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands for (int splits = 0; 284dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines rest.data() != nullptr && (MaxSplit < 0 || splits < MaxSplit); 285bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands ++splits) { 286bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands std::pair<StringRef, StringRef> p = rest.split(Separators); 287bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands 28837b6e5ae7dff4e50c1c51b64b3459cbbe6b70dafDuncan Sands if (KeepEmpty || p.first.size() != 0) 289bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands A.push_back(p.first); 290bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands rest = p.second; 291bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands } 292bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands // If we have a tail left, add it. 293dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (rest.data() != nullptr && (rest.size() != 0 || KeepEmpty)) 294bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands A.push_back(rest); 295bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands} 296bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands 29705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner//===----------------------------------------------------------------------===// 29805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner// Helpful Algorithms 29905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner//===----------------------------------------------------------------------===// 30005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 30105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// count - Return the number of non-overlapped occurrences of \arg Str in 30205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// the string. 3032928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarsize_t StringRef::count(StringRef Str) const { 30405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t Count = 0; 30505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t N = Str.size(); 30605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (N > Length) 30705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return 0; 30805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner for (size_t i = 0, e = Length - N + 1; i != e; ++i) 30905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (substr(i, N).equals(Str)) 31005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner ++Count; 31105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return Count; 31205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 31305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 3141e7ad3993d8700488895fa372ecad55443f53485John McCallstatic unsigned GetAutoSenseRadix(StringRef &Str) { 3151e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str.startswith("0x")) { 3161e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(2); 3171e7ad3993d8700488895fa372ecad55443f53485John McCall return 16; 3182dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner } 3192dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3202dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner if (Str.startswith("0b")) { 3211e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(2); 3221e7ad3993d8700488895fa372ecad55443f53485John McCall return 2; 3232dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner } 3242dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3252dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner if (Str.startswith("0o")) { 3262dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner Str = Str.substr(2); 3271e7ad3993d8700488895fa372ecad55443f53485John McCall return 8; 3281e7ad3993d8700488895fa372ecad55443f53485John McCall } 3292dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3302dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner if (Str.startswith("0")) 3312dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner return 8; 3322dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3332dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner return 10; 3341e7ad3993d8700488895fa372ecad55443f53485John McCall} 3351e7ad3993d8700488895fa372ecad55443f53485John McCall 3361e7ad3993d8700488895fa372ecad55443f53485John McCall 33763c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner/// GetAsUnsignedInteger - Workhorse method that converts a integer character 33863c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner/// sequence of radix up to 36 to an unsigned long long value. 3399130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencerbool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix, 3409130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer unsigned long long &Result) { 341cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Autosense radix if not specified. 3421e7ad3993d8700488895fa372ecad55443f53485John McCall if (Radix == 0) 3431e7ad3993d8700488895fa372ecad55443f53485John McCall Radix = GetAutoSenseRadix(Str); 344326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 345cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Empty strings (after the radix autosense) are invalid. 346cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner if (Str.empty()) return true; 347326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 348cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Parse all the bytes of the string given this radix. Watch for overflow. 349cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner Result = 0; 350cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner while (!Str.empty()) { 351cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner unsigned CharVal; 352cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner if (Str[0] >= '0' && Str[0] <= '9') 353cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner CharVal = Str[0]-'0'; 354cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner else if (Str[0] >= 'a' && Str[0] <= 'z') 355cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner CharVal = Str[0]-'a'+10; 356cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner else if (Str[0] >= 'A' && Str[0] <= 'Z') 357cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner CharVal = Str[0]-'A'+10; 358cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner else 359cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return true; 360326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 361cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // If the parsed value is larger than the integer radix, the string is 362cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // invalid. 363cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner if (CharVal >= Radix) 364cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return true; 365326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 366cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Add in this character. 367cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner unsigned long long PrevResult = Result; 368cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner Result = Result*Radix+CharVal; 369326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 3706e033d6dcd374634a64825692342c555d2eff38fNick Kledzik // Check for overflow by shifting back and seeing if bits were lost. 3716e033d6dcd374634a64825692342c555d2eff38fNick Kledzik if (Result/Radix < PrevResult) 372cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return true; 373cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner 374cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner Str = Str.substr(1); 375cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner } 376326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 377cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return false; 378cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner} 379cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner 3809130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencerbool llvm::getAsSignedInteger(StringRef Str, unsigned Radix, 3819130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer long long &Result) { 38263c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner unsigned long long ULLVal; 383326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 38463c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Handle positive strings first. 3859130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer if (Str.empty() || Str.front() != '-') { 3869130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer if (getAsUnsignedInteger(Str, Radix, ULLVal) || 38763c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Check for value so large it overflows a signed value. 38863c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner (long long)ULLVal < 0) 38963c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return true; 39063c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner Result = ULLVal; 39163c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return false; 39263c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner } 393326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 39463c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Get the positive part of the value. 3959130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer if (getAsUnsignedInteger(Str.substr(1), Radix, ULLVal) || 39663c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Reject values so large they'd overflow as negative signed, but allow 39763c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // "-0". This negates the unsigned so that the negative isn't undefined 39863c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // on signed overflow. 39963c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner (long long)-ULLVal > 0) 40063c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return true; 401326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 40263c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner Result = -ULLVal; 40363c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return false; 40463c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner} 40563c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner 4061e7ad3993d8700488895fa372ecad55443f53485John McCallbool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { 4071e7ad3993d8700488895fa372ecad55443f53485John McCall StringRef Str = *this; 4081e7ad3993d8700488895fa372ecad55443f53485John McCall 4091e7ad3993d8700488895fa372ecad55443f53485John McCall // Autosense radix if not specified. 4101e7ad3993d8700488895fa372ecad55443f53485John McCall if (Radix == 0) 4111e7ad3993d8700488895fa372ecad55443f53485John McCall Radix = GetAutoSenseRadix(Str); 4121e7ad3993d8700488895fa372ecad55443f53485John McCall 4131e7ad3993d8700488895fa372ecad55443f53485John McCall assert(Radix > 1 && Radix <= 36); 414326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4151e7ad3993d8700488895fa372ecad55443f53485John McCall // Empty strings (after the radix autosense) are invalid. 4161e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str.empty()) return true; 4171e7ad3993d8700488895fa372ecad55443f53485John McCall 4181e7ad3993d8700488895fa372ecad55443f53485John McCall // Skip leading zeroes. This can be a significant improvement if 4191e7ad3993d8700488895fa372ecad55443f53485John McCall // it means we don't need > 64 bits. 4201e7ad3993d8700488895fa372ecad55443f53485John McCall while (!Str.empty() && Str.front() == '0') 4211e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(1); 4221e7ad3993d8700488895fa372ecad55443f53485John McCall 4231e7ad3993d8700488895fa372ecad55443f53485John McCall // If it was nothing but zeroes.... 4241e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str.empty()) { 4251e7ad3993d8700488895fa372ecad55443f53485John McCall Result = APInt(64, 0); 4261e7ad3993d8700488895fa372ecad55443f53485John McCall return false; 4271e7ad3993d8700488895fa372ecad55443f53485John McCall } 4281e7ad3993d8700488895fa372ecad55443f53485John McCall 4291e7ad3993d8700488895fa372ecad55443f53485John McCall // (Over-)estimate the required number of bits. 4301e7ad3993d8700488895fa372ecad55443f53485John McCall unsigned Log2Radix = 0; 4311e7ad3993d8700488895fa372ecad55443f53485John McCall while ((1U << Log2Radix) < Radix) Log2Radix++; 4321e7ad3993d8700488895fa372ecad55443f53485John McCall bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); 4331e7ad3993d8700488895fa372ecad55443f53485John McCall 4341e7ad3993d8700488895fa372ecad55443f53485John McCall unsigned BitWidth = Log2Radix * Str.size(); 4351e7ad3993d8700488895fa372ecad55443f53485John McCall if (BitWidth < Result.getBitWidth()) 4361e7ad3993d8700488895fa372ecad55443f53485John McCall BitWidth = Result.getBitWidth(); // don't shrink the result 437a9963c648e1646fe6fc1015a61a05b08a62d0aa8Chris Lattner else if (BitWidth > Result.getBitWidth()) 43840f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Result = Result.zext(BitWidth); 4391e7ad3993d8700488895fa372ecad55443f53485John McCall 4401e7ad3993d8700488895fa372ecad55443f53485John McCall APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix 4411e7ad3993d8700488895fa372ecad55443f53485John McCall if (!IsPowerOf2Radix) { 4421e7ad3993d8700488895fa372ecad55443f53485John McCall // These must have the same bit-width as Result. 4431e7ad3993d8700488895fa372ecad55443f53485John McCall RadixAP = APInt(BitWidth, Radix); 4441e7ad3993d8700488895fa372ecad55443f53485John McCall CharAP = APInt(BitWidth, 0); 4451e7ad3993d8700488895fa372ecad55443f53485John McCall } 4461e7ad3993d8700488895fa372ecad55443f53485John McCall 4471e7ad3993d8700488895fa372ecad55443f53485John McCall // Parse all the bytes of the string given this radix. 4481e7ad3993d8700488895fa372ecad55443f53485John McCall Result = 0; 4491e7ad3993d8700488895fa372ecad55443f53485John McCall while (!Str.empty()) { 4501e7ad3993d8700488895fa372ecad55443f53485John McCall unsigned CharVal; 4511e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str[0] >= '0' && Str[0] <= '9') 4521e7ad3993d8700488895fa372ecad55443f53485John McCall CharVal = Str[0]-'0'; 4531e7ad3993d8700488895fa372ecad55443f53485John McCall else if (Str[0] >= 'a' && Str[0] <= 'z') 4541e7ad3993d8700488895fa372ecad55443f53485John McCall CharVal = Str[0]-'a'+10; 4551e7ad3993d8700488895fa372ecad55443f53485John McCall else if (Str[0] >= 'A' && Str[0] <= 'Z') 4561e7ad3993d8700488895fa372ecad55443f53485John McCall CharVal = Str[0]-'A'+10; 4571e7ad3993d8700488895fa372ecad55443f53485John McCall else 4581e7ad3993d8700488895fa372ecad55443f53485John McCall return true; 459326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4601e7ad3993d8700488895fa372ecad55443f53485John McCall // If the parsed value is larger than the integer radix, the string is 4611e7ad3993d8700488895fa372ecad55443f53485John McCall // invalid. 4621e7ad3993d8700488895fa372ecad55443f53485John McCall if (CharVal >= Radix) 4631e7ad3993d8700488895fa372ecad55443f53485John McCall return true; 464326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4651e7ad3993d8700488895fa372ecad55443f53485John McCall // Add in this character. 4661e7ad3993d8700488895fa372ecad55443f53485John McCall if (IsPowerOf2Radix) { 4671e7ad3993d8700488895fa372ecad55443f53485John McCall Result <<= Log2Radix; 4681e7ad3993d8700488895fa372ecad55443f53485John McCall Result |= CharVal; 4691e7ad3993d8700488895fa372ecad55443f53485John McCall } else { 4701e7ad3993d8700488895fa372ecad55443f53485John McCall Result *= RadixAP; 4711e7ad3993d8700488895fa372ecad55443f53485John McCall CharAP = CharVal; 4721e7ad3993d8700488895fa372ecad55443f53485John McCall Result += CharAP; 4731e7ad3993d8700488895fa372ecad55443f53485John McCall } 4741e7ad3993d8700488895fa372ecad55443f53485John McCall 4751e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(1); 4761e7ad3993d8700488895fa372ecad55443f53485John McCall } 477326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4781e7ad3993d8700488895fa372ecad55443f53485John McCall return false; 4791e7ad3993d8700488895fa372ecad55443f53485John McCall} 480528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth 481528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth 482528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth// Implementation of StringRef hashing. 483528f0bbe19553dfadedca040df13a389daa7593dChandler Carruthhash_code llvm::hash_value(StringRef S) { 484528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth return hash_combine_range(S.begin(), S.end()); 485528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth} 486