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 { 143f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (From > Length) 144f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return npos; 145f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 146f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const char *Needle = Str.data(); 14705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t N = Str.size(); 148f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (N == 0) 149f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return From; 150f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 151f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar size_t Size = Length - From; 152f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Size < N) 15305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 1546e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 155f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const char *Start = Data + From; 156f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar const char *Stop = Start + (Size - N + 1); 157f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 1586e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer // For short haystacks or unsupported needles fall back to the naive algorithm 159f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Size < 16 || N > 255) { 160f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar do { 161f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (std::memcmp(Start, Needle, N) == 0) 162f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Start - Data; 163f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ++Start; 164f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } while (Start < Stop); 1656e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer return npos; 1666e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer } 1676e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 1686e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. 1696e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer uint8_t BadCharSkip[256]; 1706e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer std::memset(BadCharSkip, N, 256); 1716e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer for (unsigned i = 0; i != N-1; ++i) 1726e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer BadCharSkip[(uint8_t)Str[i]] = N-1-i; 1736e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 174f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar do { 175f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (std::memcmp(Start, Needle, N) == 0) 176f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return Start - Data; 1776e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 1786e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer // Otherwise skip the appropriate number of bytes. 179f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Start += BadCharSkip[(uint8_t)Start[N-1]]; 180f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } while (Start < Stop); 1816e6a558ebce556476d8fd659b419a2760f2ab154Benjamin Kramer 18205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 18305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 18405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 18505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// rfind - Search for the last string \arg Str in the string. 18605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// 1877a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// \return - The index of the last occurrence of \arg Str, or npos if not 18805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// found. 1892928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarsize_t StringRef::rfind(StringRef Str) const { 19005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t N = Str.size(); 19105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (N > Length) 19205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 19305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner for (size_t i = Length - N + 1, e = 0; i != e;) { 19405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner --i; 19505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (substr(i, N).equals(Str)) 19605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return i; 19705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner } 19805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 19905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 20005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 20164066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// find_first_of - Find the first character in the string that is in \arg 20264066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// Chars, or npos if not found. 20364066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// 204250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer/// Note: O(size() + Chars.size()) 20564066bd8b593082f622bbc25716938a453363d2fDaniel DunbarStringRef::size_type StringRef::find_first_of(StringRef Chars, 20664066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar size_t From) const { 207250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer std::bitset<1 << CHAR_BIT> CharBits; 208250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer for (size_type i = 0; i != Chars.size(); ++i) 209250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer CharBits.set((unsigned char)Chars[i]); 210250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer 21137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length), e = Length; i != e; ++i) 212250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer if (CharBits.test((unsigned char)Data[i])) 21305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return i; 21405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 21505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 21605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 21705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// find_first_not_of - Find the first character in the string that is not 21864066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// \arg C or npos if not found. 21964066bd8b593082f622bbc25716938a453363d2fDaniel DunbarStringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { 22037ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length), e = Length; i != e; ++i) 22164066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar if (Data[i] != C) 22264066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar return i; 22364066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar return npos; 22464066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar} 22564066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar 22664066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// find_first_not_of - Find the first character in the string that is not 22764066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// in the string \arg Chars, or npos if not found. 22864066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar/// 229250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer/// Note: O(size() + Chars.size()) 23064066bd8b593082f622bbc25716938a453363d2fDaniel DunbarStringRef::size_type StringRef::find_first_not_of(StringRef Chars, 23164066bd8b593082f622bbc25716938a453363d2fDaniel Dunbar size_t From) const { 232250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer std::bitset<1 << CHAR_BIT> CharBits; 233250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer for (size_type i = 0; i != Chars.size(); ++i) 234250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer CharBits.set((unsigned char)Chars[i]); 235250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer 23637ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length), e = Length; i != e; ++i) 237250eb005d91e80b05a61345394bae9e9528151acBenjamin Kramer if (!CharBits.test((unsigned char)Data[i])) 23805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return i; 23905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return npos; 24005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 24105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 24263c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// find_last_of - Find the last character in the string that is in \arg C, 24363c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// or npos if not found. 24463c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// 24563c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer/// Note: O(size() + Chars.size()) 24663c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. SpencerStringRef::size_type StringRef::find_last_of(StringRef Chars, 24763c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer size_t From) const { 24863c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer std::bitset<1 << CHAR_BIT> CharBits; 24963c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer for (size_type i = 0; i != Chars.size(); ++i) 25063c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer CharBits.set((unsigned char)Chars[i]); 25163c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer 25237ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) 25363c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer if (CharBits.test((unsigned char)Data[i])) 25463c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer return i; 25563c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer return npos; 25663c133b67d61b0c457ff46c957aed2b8d90b599cMichael J. Spencer} 25705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 258b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// find_last_not_of - Find the last character in the string that is not 259b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// \arg C, or npos if not found. 260b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. SpencerStringRef::size_type StringRef::find_last_not_of(char C, size_t From) const { 26137ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) 262b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer if (Data[i] != C) 263b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return i; 264b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return npos; 265b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer} 266b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer 267b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// find_last_not_of - Find the last character in the string that is not in 268b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// \arg Chars, or npos if not found. 269b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// 270b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer/// Note: O(size() + Chars.size()) 271b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. SpencerStringRef::size_type StringRef::find_last_not_of(StringRef Chars, 272b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer size_t From) const { 273b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer std::bitset<1 << CHAR_BIT> CharBits; 274b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer for (size_type i = 0, e = Chars.size(); i != e; ++i) 275b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer CharBits.set((unsigned char)Chars[i]); 276b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer 27737ed9c199ca639565f6ce88105f9e39e898d82d0Stephen Hines for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) 278b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer if (!CharBits.test((unsigned char)Data[i])) 279b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return i; 280b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer return npos; 281b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer} 282b0940b46edbbe9d3f62d7f6f70330fd87f3507e1Michael J. Spencer 283bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sandsvoid StringRef::split(SmallVectorImpl<StringRef> &A, 284f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar StringRef Separator, int MaxSplit, 285bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands bool KeepEmpty) const { 286f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar StringRef S = *this; 287f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 288f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Count down from MaxSplit. When MaxSplit is -1, this will just split 289f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // "forever". This doesn't support splitting more than 2^31 times 290f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // intentionally; if we ever want that we can make MaxSplit a 64-bit integer 291f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // but that seems unlikely to be useful. 292f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar while (MaxSplit-- != 0) { 293f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar size_t Idx = S.find(Separator); 294f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Idx == npos) 295f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 296f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 297f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Push this split. 298f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (KeepEmpty || Idx > 0) 299f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar A.push_back(S.slice(0, Idx)); 300f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 301f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Jump forward. 302f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar S = S.slice(Idx + Separator.size(), npos); 303f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar } 304f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 305f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Push the tail. 306f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (KeepEmpty || !S.empty()) 307f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar A.push_back(S); 308f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar} 309f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 310f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainarvoid StringRef::split(SmallVectorImpl<StringRef> &A, char Separator, 311f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar int MaxSplit, bool KeepEmpty) const { 312f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar StringRef S = *this; 313f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 314f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Count down from MaxSplit. When MaxSplit is -1, this will just split 315f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // "forever". This doesn't support splitting more than 2^31 times 316f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // intentionally; if we ever want that we can make MaxSplit a 64-bit integer 317f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // but that seems unlikely to be useful. 318f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar while (MaxSplit-- != 0) { 319f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar size_t Idx = S.find(Separator); 320f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Idx == npos) 321f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar break; 322f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 323f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Push this split. 324f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (KeepEmpty || Idx > 0) 325f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar A.push_back(S.slice(0, Idx)); 326f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 327f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Jump forward. 328f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar S = S.slice(Idx + 1, npos); 329bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands } 330f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 331f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Push the tail. 332f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (KeepEmpty || !S.empty()) 333f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar A.push_back(S); 334bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands} 335bf8653ff3b70d2a1bb059a958d7612954408d998Duncan Sands 33605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner//===----------------------------------------------------------------------===// 33705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner// Helpful Algorithms 33805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner//===----------------------------------------------------------------------===// 33905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 34005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// count - Return the number of non-overlapped occurrences of \arg Str in 34105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner/// the string. 3422928c83b010f7cfdb0f819199d806f6942a7d995Daniel Dunbarsize_t StringRef::count(StringRef Str) const { 34305a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t Count = 0; 34405a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner size_t N = Str.size(); 34505a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (N > Length) 34605a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return 0; 34705a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner for (size_t i = 0, e = Length - N + 1; i != e; ++i) 34805a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner if (substr(i, N).equals(Str)) 34905a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner ++Count; 35005a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner return Count; 35105a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner} 35205a32c8ab118d9c92dc9b4ecaa7a6fed67241215Chris Lattner 3531e7ad3993d8700488895fa372ecad55443f53485John McCallstatic unsigned GetAutoSenseRadix(StringRef &Str) { 354de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Str.startswith("0x") || Str.startswith("0X")) { 3551e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(2); 3561e7ad3993d8700488895fa372ecad55443f53485John McCall return 16; 3572dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner } 3582dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 359de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (Str.startswith("0b") || Str.startswith("0B")) { 3601e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(2); 3611e7ad3993d8700488895fa372ecad55443f53485John McCall return 2; 3622dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner } 3632dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3642dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner if (Str.startswith("0o")) { 3652dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner Str = Str.substr(2); 3661e7ad3993d8700488895fa372ecad55443f53485John McCall return 8; 3671e7ad3993d8700488895fa372ecad55443f53485John McCall } 3682dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3692dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner if (Str.startswith("0")) 3702dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner return 8; 3712dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner 3722dbd7844e831caa107c6c9c57889f3d89b843ef3Chris Lattner return 10; 3731e7ad3993d8700488895fa372ecad55443f53485John McCall} 3741e7ad3993d8700488895fa372ecad55443f53485John McCall 3751e7ad3993d8700488895fa372ecad55443f53485John McCall 37663c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner/// GetAsUnsignedInteger - Workhorse method that converts a integer character 37763c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner/// sequence of radix up to 36 to an unsigned long long value. 3789130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencerbool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix, 3799130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer unsigned long long &Result) { 380cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Autosense radix if not specified. 3811e7ad3993d8700488895fa372ecad55443f53485John McCall if (Radix == 0) 3821e7ad3993d8700488895fa372ecad55443f53485John McCall Radix = GetAutoSenseRadix(Str); 383326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 384cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Empty strings (after the radix autosense) are invalid. 385cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner if (Str.empty()) return true; 386326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 387cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Parse all the bytes of the string given this radix. Watch for overflow. 388cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner Result = 0; 389cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner while (!Str.empty()) { 390cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner unsigned CharVal; 391cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner if (Str[0] >= '0' && Str[0] <= '9') 392cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner CharVal = Str[0]-'0'; 393cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner else if (Str[0] >= 'a' && Str[0] <= 'z') 394cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner CharVal = Str[0]-'a'+10; 395cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner else if (Str[0] >= 'A' && Str[0] <= 'Z') 396cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner CharVal = Str[0]-'A'+10; 397cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner else 398cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return true; 399326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 400cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // If the parsed value is larger than the integer radix, the string is 401cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // invalid. 402cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner if (CharVal >= Radix) 403cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return true; 404326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 405cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner // Add in this character. 406cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner unsigned long long PrevResult = Result; 407cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner Result = Result*Radix+CharVal; 408326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4096e033d6dcd374634a64825692342c555d2eff38fNick Kledzik // Check for overflow by shifting back and seeing if bits were lost. 4106e033d6dcd374634a64825692342c555d2eff38fNick Kledzik if (Result/Radix < PrevResult) 411cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return true; 412cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner 413cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner Str = Str.substr(1); 414cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner } 415326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 416cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner return false; 417cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner} 418cea1438cf59c7cd3a632d61d78e68589315510d3Chris Lattner 4199130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencerbool llvm::getAsSignedInteger(StringRef Str, unsigned Radix, 4209130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer long long &Result) { 42163c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner unsigned long long ULLVal; 422326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 42363c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Handle positive strings first. 4249130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer if (Str.empty() || Str.front() != '-') { 4259130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer if (getAsUnsignedInteger(Str, Radix, ULLVal) || 42663c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Check for value so large it overflows a signed value. 42763c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner (long long)ULLVal < 0) 42863c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return true; 42963c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner Result = ULLVal; 43063c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return false; 43163c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner } 432326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 43363c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Get the positive part of the value. 4349130b42a85998238b7bbe25ed2989e0605f636f0Michael J. Spencer if (getAsUnsignedInteger(Str.substr(1), Radix, ULLVal) || 43563c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // Reject values so large they'd overflow as negative signed, but allow 43663c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // "-0". This negates the unsigned so that the negative isn't undefined 43763c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner // on signed overflow. 43863c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner (long long)-ULLVal > 0) 43963c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return true; 440326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 44163c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner Result = -ULLVal; 44263c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner return false; 44363c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner} 44463c6b7dc67f0061340c0701f3d5b1de142f58cecChris Lattner 4451e7ad3993d8700488895fa372ecad55443f53485John McCallbool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { 4461e7ad3993d8700488895fa372ecad55443f53485John McCall StringRef Str = *this; 4471e7ad3993d8700488895fa372ecad55443f53485John McCall 4481e7ad3993d8700488895fa372ecad55443f53485John McCall // Autosense radix if not specified. 4491e7ad3993d8700488895fa372ecad55443f53485John McCall if (Radix == 0) 4501e7ad3993d8700488895fa372ecad55443f53485John McCall Radix = GetAutoSenseRadix(Str); 4511e7ad3993d8700488895fa372ecad55443f53485John McCall 4521e7ad3993d8700488895fa372ecad55443f53485John McCall assert(Radix > 1 && Radix <= 36); 453326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4541e7ad3993d8700488895fa372ecad55443f53485John McCall // Empty strings (after the radix autosense) are invalid. 4551e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str.empty()) return true; 4561e7ad3993d8700488895fa372ecad55443f53485John McCall 4571e7ad3993d8700488895fa372ecad55443f53485John McCall // Skip leading zeroes. This can be a significant improvement if 4581e7ad3993d8700488895fa372ecad55443f53485John McCall // it means we don't need > 64 bits. 4591e7ad3993d8700488895fa372ecad55443f53485John McCall while (!Str.empty() && Str.front() == '0') 4601e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(1); 4611e7ad3993d8700488895fa372ecad55443f53485John McCall 4621e7ad3993d8700488895fa372ecad55443f53485John McCall // If it was nothing but zeroes.... 4631e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str.empty()) { 4641e7ad3993d8700488895fa372ecad55443f53485John McCall Result = APInt(64, 0); 4651e7ad3993d8700488895fa372ecad55443f53485John McCall return false; 4661e7ad3993d8700488895fa372ecad55443f53485John McCall } 4671e7ad3993d8700488895fa372ecad55443f53485John McCall 4681e7ad3993d8700488895fa372ecad55443f53485John McCall // (Over-)estimate the required number of bits. 4691e7ad3993d8700488895fa372ecad55443f53485John McCall unsigned Log2Radix = 0; 4701e7ad3993d8700488895fa372ecad55443f53485John McCall while ((1U << Log2Radix) < Radix) Log2Radix++; 4711e7ad3993d8700488895fa372ecad55443f53485John McCall bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); 4721e7ad3993d8700488895fa372ecad55443f53485John McCall 4731e7ad3993d8700488895fa372ecad55443f53485John McCall unsigned BitWidth = Log2Radix * Str.size(); 4741e7ad3993d8700488895fa372ecad55443f53485John McCall if (BitWidth < Result.getBitWidth()) 4751e7ad3993d8700488895fa372ecad55443f53485John McCall BitWidth = Result.getBitWidth(); // don't shrink the result 476a9963c648e1646fe6fc1015a61a05b08a62d0aa8Chris Lattner else if (BitWidth > Result.getBitWidth()) 47740f8f6264d5af2c38e797e0dc59827cd231e8ff7Jay Foad Result = Result.zext(BitWidth); 4781e7ad3993d8700488895fa372ecad55443f53485John McCall 4791e7ad3993d8700488895fa372ecad55443f53485John McCall APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix 4801e7ad3993d8700488895fa372ecad55443f53485John McCall if (!IsPowerOf2Radix) { 4811e7ad3993d8700488895fa372ecad55443f53485John McCall // These must have the same bit-width as Result. 4821e7ad3993d8700488895fa372ecad55443f53485John McCall RadixAP = APInt(BitWidth, Radix); 4831e7ad3993d8700488895fa372ecad55443f53485John McCall CharAP = APInt(BitWidth, 0); 4841e7ad3993d8700488895fa372ecad55443f53485John McCall } 4851e7ad3993d8700488895fa372ecad55443f53485John McCall 4861e7ad3993d8700488895fa372ecad55443f53485John McCall // Parse all the bytes of the string given this radix. 4871e7ad3993d8700488895fa372ecad55443f53485John McCall Result = 0; 4881e7ad3993d8700488895fa372ecad55443f53485John McCall while (!Str.empty()) { 4891e7ad3993d8700488895fa372ecad55443f53485John McCall unsigned CharVal; 4901e7ad3993d8700488895fa372ecad55443f53485John McCall if (Str[0] >= '0' && Str[0] <= '9') 4911e7ad3993d8700488895fa372ecad55443f53485John McCall CharVal = Str[0]-'0'; 4921e7ad3993d8700488895fa372ecad55443f53485John McCall else if (Str[0] >= 'a' && Str[0] <= 'z') 4931e7ad3993d8700488895fa372ecad55443f53485John McCall CharVal = Str[0]-'a'+10; 4941e7ad3993d8700488895fa372ecad55443f53485John McCall else if (Str[0] >= 'A' && Str[0] <= 'Z') 4951e7ad3993d8700488895fa372ecad55443f53485John McCall CharVal = Str[0]-'A'+10; 4961e7ad3993d8700488895fa372ecad55443f53485John McCall else 4971e7ad3993d8700488895fa372ecad55443f53485John McCall return true; 498326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 4991e7ad3993d8700488895fa372ecad55443f53485John McCall // If the parsed value is larger than the integer radix, the string is 5001e7ad3993d8700488895fa372ecad55443f53485John McCall // invalid. 5011e7ad3993d8700488895fa372ecad55443f53485John McCall if (CharVal >= Radix) 5021e7ad3993d8700488895fa372ecad55443f53485John McCall return true; 503326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 5041e7ad3993d8700488895fa372ecad55443f53485John McCall // Add in this character. 5051e7ad3993d8700488895fa372ecad55443f53485John McCall if (IsPowerOf2Radix) { 5061e7ad3993d8700488895fa372ecad55443f53485John McCall Result <<= Log2Radix; 5071e7ad3993d8700488895fa372ecad55443f53485John McCall Result |= CharVal; 5081e7ad3993d8700488895fa372ecad55443f53485John McCall } else { 5091e7ad3993d8700488895fa372ecad55443f53485John McCall Result *= RadixAP; 5101e7ad3993d8700488895fa372ecad55443f53485John McCall CharAP = CharVal; 5111e7ad3993d8700488895fa372ecad55443f53485John McCall Result += CharAP; 5121e7ad3993d8700488895fa372ecad55443f53485John McCall } 5131e7ad3993d8700488895fa372ecad55443f53485John McCall 5141e7ad3993d8700488895fa372ecad55443f53485John McCall Str = Str.substr(1); 5151e7ad3993d8700488895fa372ecad55443f53485John McCall } 516326990f1eb7ff005adabe46a1f982eff8835813eMichael J. Spencer 5171e7ad3993d8700488895fa372ecad55443f53485John McCall return false; 5181e7ad3993d8700488895fa372ecad55443f53485John McCall} 519528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth 520528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth 521528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth// Implementation of StringRef hashing. 522528f0bbe19553dfadedca040df13a389daa7593dChandler Carruthhash_code llvm::hash_value(StringRef S) { 523528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth return hash_combine_range(S.begin(), S.end()); 524528f0bbe19553dfadedca040df13a389daa7593dChandler Carruth} 525