StringRef.cpp revision dce4a407a24b04eebc6a376f8e62b41aaa7b071f
190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===-- StringRef.cpp - Lightweight String References ---------------------===// 290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// The LLVM Compiler Infrastructure 490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// This file is distributed under the University of Illinois Open Source 690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// License. See LICENSE.TXT for details. 790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// 890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 1090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "llvm/ADT/StringRef.h" 1190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "llvm/ADT/APInt.h" 1290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "llvm/ADT/Hashing.h" 1390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include "llvm/ADT/edit_distance.h" 1490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#include <bitset> 1590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 1690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)using namespace llvm; 1790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 1890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// MSVC emits references to this into the translation units which reference it. 1990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#ifndef _MSC_VER 2090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)const size_t StringRef::npos; 2190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)#endif 2290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 2390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)static char ascii_tolower(char x) { 2490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (x >= 'A' && x <= 'Z') 2590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return x - 'A' + 'a'; 2690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return x; 2790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 2890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 2990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)static char ascii_toupper(char x) { 3090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (x >= 'a' && x <= 'z') 3190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return x - 'a' + 'A'; 3290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return x; 3390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 3490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 3590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)static bool ascii_isdigit(char x) { 3690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return x >= '0' && x <= '9'; 3790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 3890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 3990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// strncasecmp() is not available on non-POSIX systems, so define an 4090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// alternative function here. 4190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)static int ascii_strncasecmp(const char *LHS, const char *RHS, size_t Length) { 4290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_t I = 0; I < Length; ++I) { 4390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned char LHC = ascii_tolower(LHS[I]); 4490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned char RHC = ascii_tolower(RHS[I]); 4590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (LHC != RHC) 4690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return LHC < RHC ? -1 : 1; 4790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 4890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 0; 4990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 5090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 5190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// compare_lower - Compare strings, ignoring case. 5290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)int StringRef::compare_lower(StringRef RHS) const { 5390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (int Res = ascii_strncasecmp(Data, RHS.Data, min(Length, RHS.Length))) 5490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Res; 5590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Length == RHS.Length) 5690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 0; 5790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Length < RHS.Length ? -1 : 1; 5890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 5990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 6090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Check if this string starts with the given \p Prefix, ignoring case. 6190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)bool StringRef::startswith_lower(StringRef Prefix) const { 6290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Length >= Prefix.Length && 6390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ascii_strncasecmp(Data, Prefix.Data, Prefix.Length) == 0; 6490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 6590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 6690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Check if this string ends with the given \p Suffix, ignoring case. 6790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)bool StringRef::endswith_lower(StringRef Suffix) const { 6890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Length >= Suffix.Length && 6990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0; 7090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 7190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 7290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// compare_numeric - Compare strings, handle embedded numbers. 7390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)int StringRef::compare_numeric(StringRef RHS) const { 7490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { 7590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Check for sequences of digits. 7690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) { 7790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // The longer sequence of numbers is considered larger. 7890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // This doesn't really handle prefixed zeros well. 7990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t J; 8090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (J = I + 1; J != E + 1; ++J) { 8190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) bool ld = J < Length && ascii_isdigit(Data[J]); 8290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]); 8390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (ld != rd) 8490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return rd ? -1 : 1; 8590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (!rd) 8690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) break; 8790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 8890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // The two number sequences have the same length (J-I), just memcmp them. 8990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (int Res = compareMemory(Data + I, RHS.Data + I, J - I)) 9090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Res < 0 ? -1 : 1; 9190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Identical number sequences, continue search after the numbers. 9290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) I = J - 1; 9390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) continue; 9490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 9590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Data[I] != RHS.Data[I]) 9690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; 9790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 9890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Length == RHS.Length) 9990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 0; 10090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Length < RHS.Length ? -1 : 1; 10190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 10290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 10390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// Compute the edit distance between the two given strings. 10490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)unsigned StringRef::edit_distance(llvm::StringRef Other, 10590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) bool AllowReplacements, 10690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned MaxEditDistance) const { 10790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return llvm::ComputeEditDistance( 10890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) llvm::ArrayRef<char>(data(), size()), 10990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) llvm::ArrayRef<char>(Other.data(), Other.size()), 11090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) AllowReplacements, MaxEditDistance); 11190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 11290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 11390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 11490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// String Operations 11590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 11690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 11790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)std::string StringRef::lower() const { 11890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::string Result(size(), char()); 11990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = 0, e = size(); i != e; ++i) { 12090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result[i] = ascii_tolower(Data[i]); 12190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 12290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Result; 12390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 12490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 12590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)std::string StringRef::upper() const { 12690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::string Result(size(), char()); 12790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = 0, e = size(); i != e; ++i) { 12890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result[i] = ascii_toupper(Data[i]); 12990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 13090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Result; 13190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 13290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 13390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 13490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// String Searching 13590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 13690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 13790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 13890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find - Search for the first string \arg Str in the string. 13990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// 14090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// \return - The index of the first occurrence of \arg Str, or npos if not 14190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// found. 14290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)size_t StringRef::find(StringRef Str, size_t From) const { 14390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t N = Str.size(); 14490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (N > Length) 14590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 14690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 14790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // For short haystacks or unsupported needles fall back to the naive algorithm 14890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Length < 16 || N > 255 || N == 0) { 14990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i) 15090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (substr(i, N).equals(Str)) 15190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 15290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 15390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 15490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 15590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (From >= Length) 15690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 15790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 15890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. 15990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) uint8_t BadCharSkip[256]; 16090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::memset(BadCharSkip, N, 256); 16190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (unsigned i = 0; i != N-1; ++i) 16290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) BadCharSkip[(uint8_t)Str[i]] = N-1-i; 16390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 16490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned Len = Length-From, Pos = From; 16590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) while (Len >= N) { 16690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (substr(Pos, N).equals(Str)) // See if this is the correct substring. 16790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Pos; 16890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 16990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Otherwise skip the appropriate number of bytes. 17090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) uint8_t Skip = BadCharSkip[(uint8_t)(*this)[Pos+N-1]]; 17190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Len -= Skip; 17290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Pos += Skip; 17390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 17490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 17590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 17690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 17790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 17890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// rfind - Search for the last string \arg Str in the string. 17990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// 18090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// \return - The index of the last occurrence of \arg Str, or npos if not 18190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// found. 18290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)size_t StringRef::rfind(StringRef Str) const { 18390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t N = Str.size(); 18490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (N > Length) 18590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 18690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_t i = Length - N + 1, e = 0; i != e;) { 18790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) --i; 18890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (substr(i, N).equals(Str)) 18990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 19090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 19190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 19290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 19390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 19490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find_first_of - Find the first character in the string that is in \arg 19590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Chars, or npos if not found. 19690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// 19790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Note: O(size() + Chars.size()) 19890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)StringRef::size_type StringRef::find_first_of(StringRef Chars, 19990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t From) const { 20090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::bitset<1 << CHAR_BIT> CharBits; 20190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = 0; i != Chars.size(); ++i) 20290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharBits.set((unsigned char)Chars[i]); 20390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 20490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = min(From, Length), e = Length; i != e; ++i) 20590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (CharBits.test((unsigned char)Data[i])) 20690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 20790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 20890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 20990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 21090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find_first_not_of - Find the first character in the string that is not 21190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// \arg C or npos if not found. 21290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { 21390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = min(From, Length), e = Length; i != e; ++i) 21490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Data[i] != C) 21590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 21690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 21790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 21890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 21990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find_first_not_of - Find the first character in the string that is not 22090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// in the string \arg Chars, or npos if not found. 22190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// 22290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Note: O(size() + Chars.size()) 22390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)StringRef::size_type StringRef::find_first_not_of(StringRef Chars, 22490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t From) const { 22590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::bitset<1 << CHAR_BIT> CharBits; 22690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = 0; i != Chars.size(); ++i) 22790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharBits.set((unsigned char)Chars[i]); 22890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 22990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = min(From, Length), e = Length; i != e; ++i) 23090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (!CharBits.test((unsigned char)Data[i])) 23190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 23290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 23390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 23490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 23590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find_last_of - Find the last character in the string that is in \arg C, 23690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// or npos if not found. 23790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// 23890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Note: O(size() + Chars.size()) 23990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)StringRef::size_type StringRef::find_last_of(StringRef Chars, 24090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t From) const { 24190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::bitset<1 << CHAR_BIT> CharBits; 24290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = 0; i != Chars.size(); ++i) 24390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharBits.set((unsigned char)Chars[i]); 24490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 24590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) 24690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (CharBits.test((unsigned char)Data[i])) 24790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 24890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 24990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 25090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 25190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find_last_not_of - Find the last character in the string that is not 25290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// \arg C, or npos if not found. 25390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const { 25490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) 25590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Data[i] != C) 25690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 25790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 25890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 25990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 26090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// find_last_not_of - Find the last character in the string that is not in 26190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// \arg Chars, or npos if not found. 26290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// 26390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// Note: O(size() + Chars.size()) 26490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)StringRef::size_type StringRef::find_last_not_of(StringRef Chars, 26590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t From) const { 26690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::bitset<1 << CHAR_BIT> CharBits; 26790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = 0, e = Chars.size(); i != e; ++i) 26890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharBits.set((unsigned char)Chars[i]); 26990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 27090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_type i = min(From, Length) - 1, e = -1; i != e; --i) 27190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (!CharBits.test((unsigned char)Data[i])) 27290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return i; 27390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return npos; 27490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 27590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 27690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)void StringRef::split(SmallVectorImpl<StringRef> &A, 27790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) StringRef Separators, int MaxSplit, 27890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) bool KeepEmpty) const { 27990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) StringRef rest = *this; 28090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 28190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // rest.data() is used to distinguish cases like "a," that splits into 28290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // "a" + "" and "a" that splits into "a" + 0. 28390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (int splits = 0; 28490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) rest.data() != nullptr && (MaxSplit < 0 || splits < MaxSplit); 28590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ++splits) { 28690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) std::pair<StringRef, StringRef> p = rest.split(Separators); 28790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 28890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (KeepEmpty || p.first.size() != 0) 28990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) A.push_back(p.first); 29090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) rest = p.second; 29190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 29290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // If we have a tail left, add it. 29390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (rest.data() != nullptr && (rest.size() != 0 || KeepEmpty)) 29490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) A.push_back(rest); 29590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 29690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 29790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 29890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)// Helpful Algorithms 29990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)//===----------------------------------------------------------------------===// 30090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 30190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// count - Return the number of non-overlapped occurrences of \arg Str in 30290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// the string. 30390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)size_t StringRef::count(StringRef Str) const { 30490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t Count = 0; 30590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) size_t N = Str.size(); 30690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (N > Length) 30790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 0; 30890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) for (size_t i = 0, e = Length - N + 1; i != e; ++i) 30990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (substr(i, N).equals(Str)) 31090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) ++Count; 31190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return Count; 31290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 31390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 31490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)static unsigned GetAutoSenseRadix(StringRef &Str) { 31590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.startswith("0x")) { 31690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Str = Str.substr(2); 31790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 16; 31890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 31990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 32090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.startswith("0b")) { 32190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Str = Str.substr(2); 32290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 2; 32390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 32490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 32590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.startswith("0o")) { 32690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Str = Str.substr(2); 32790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 8; 32890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 32990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 33090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.startswith("0")) 33190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 8; 33290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 33390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return 10; 33490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 33590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 33690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 33790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// GetAsUnsignedInteger - Workhorse method that converts a integer character 33890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)/// sequence of radix up to 36 to an unsigned long long value. 33990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix, 34090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned long long &Result) { 34190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Autosense radix if not specified. 34290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Radix == 0) 34390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Radix = GetAutoSenseRadix(Str); 34490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 34590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Empty strings (after the radix autosense) are invalid. 34690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.empty()) return true; 34790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 34890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Parse all the bytes of the string given this radix. Watch for overflow. 34990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = 0; 35090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) while (!Str.empty()) { 35190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned CharVal; 35290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str[0] >= '0' && Str[0] <= '9') 35390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharVal = Str[0]-'0'; 35490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else if (Str[0] >= 'a' && Str[0] <= 'z') 35590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharVal = Str[0]-'a'+10; 35690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else if (Str[0] >= 'A' && Str[0] <= 'Z') 35790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharVal = Str[0]-'A'+10; 35890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else 35990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 36090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 36190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // If the parsed value is larger than the integer radix, the string is 36290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // invalid. 36390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (CharVal >= Radix) 36490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 36590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 36690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Add in this character. 36790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned long long PrevResult = Result; 36890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = Result*Radix+CharVal; 36990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 37090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Check for overflow by shifting back and seeing if bits were lost. 37190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Result/Radix < PrevResult) 37290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 37390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 37490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Str = Str.substr(1); 37590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 37690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 37790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return false; 37890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 37990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 38090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix, 38190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) long long &Result) { 38290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned long long ULLVal; 38390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 38490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Handle positive strings first. 38590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.empty() || Str.front() != '-') { 38690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (getAsUnsignedInteger(Str, Radix, ULLVal) || 38790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Check for value so large it overflows a signed value. 38890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) (long long)ULLVal < 0) 38990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 39090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = ULLVal; 39190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return false; 39290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 39390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 39490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Get the positive part of the value. 39590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (getAsUnsignedInteger(Str.substr(1), Radix, ULLVal) || 39690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Reject values so large they'd overflow as negative signed, but allow 39790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // "-0". This negates the unsigned so that the negative isn't undefined 39890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // on signed overflow. 39990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) (long long)-ULLVal > 0) 40090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 40190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 40290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = -ULLVal; 40390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return false; 40490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)} 40590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 40690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles)bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { 40790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) StringRef Str = *this; 40890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 40990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Autosense radix if not specified. 41090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Radix == 0) 41190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Radix = GetAutoSenseRadix(Str); 41290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 41390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) assert(Radix > 1 && Radix <= 36); 41490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 41590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Empty strings (after the radix autosense) are invalid. 41690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.empty()) return true; 41790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 41890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Skip leading zeroes. This can be a significant improvement if 41990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // it means we don't need > 64 bits. 42090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) while (!Str.empty() && Str.front() == '0') 42190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Str = Str.substr(1); 42290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 42390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // If it was nothing but zeroes.... 42490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str.empty()) { 42590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = APInt(64, 0); 42690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return false; 42790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 42890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 42990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // (Over-)estimate the required number of bits. 43090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned Log2Radix = 0; 43190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) while ((1U << Log2Radix) < Radix) Log2Radix++; 43290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); 43390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 43490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned BitWidth = Log2Radix * Str.size(); 43590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (BitWidth < Result.getBitWidth()) 43690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) BitWidth = Result.getBitWidth(); // don't shrink the result 43790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else if (BitWidth > Result.getBitWidth()) 43890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = Result.zext(BitWidth); 43990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 44090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix 44190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (!IsPowerOf2Radix) { 44290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // These must have the same bit-width as Result. 44390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) RadixAP = APInt(BitWidth, Radix); 44490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharAP = APInt(BitWidth, 0); 44590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 44690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 44790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Parse all the bytes of the string given this radix. 44890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result = 0; 44990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) while (!Str.empty()) { 45090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) unsigned CharVal; 45190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (Str[0] >= '0' && Str[0] <= '9') 45290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharVal = Str[0]-'0'; 45390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else if (Str[0] >= 'a' && Str[0] <= 'z') 45490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharVal = Str[0]-'a'+10; 45590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else if (Str[0] >= 'A' && Str[0] <= 'Z') 45690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharVal = Str[0]-'A'+10; 45790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) else 45890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 45990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 46090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // If the parsed value is larger than the integer radix, the string is 46190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // invalid. 46290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (CharVal >= Radix) 46390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return true; 46490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 46590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) // Add in this character. 46690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) if (IsPowerOf2Radix) { 46790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result <<= Log2Radix; 46890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result |= CharVal; 46990dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } else { 47090dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result *= RadixAP; 47190dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) CharAP = CharVal; 47290dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Result += CharAP; 47390dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 47490dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 47590dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) Str = Str.substr(1); 47690dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) } 47790dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) 47890dce4d38c5ff5333bea97d859d4e484e27edf0cTorne (Richard Coles) return false; 479} 480 481 482// Implementation of StringRef hashing. 483hash_code llvm::hash_value(StringRef S) { 484 return hash_combine_range(S.begin(), S.end()); 485} 486