StringRef.cpp revision 13302ec089d56b91f5d4b775910439ab9a74fd41
1//===-- StringRef.cpp - Lightweight String References ---------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "llvm/ADT/StringRef.h" 11#include "llvm/ADT/APInt.h" 12#include "llvm/ADT/OwningPtr.h" 13#include <bitset> 14 15using namespace llvm; 16 17// MSVC emits references to this into the translation units which reference it. 18#ifndef _MSC_VER 19const size_t StringRef::npos; 20#endif 21 22static char ascii_tolower(char x) { 23 if (x >= 'A' && x <= 'Z') 24 return x - 'A' + 'a'; 25 return x; 26} 27 28static bool ascii_isdigit(char x) { 29 return x >= '0' && x <= '9'; 30} 31 32/// compare_lower - Compare strings, ignoring case. 33int StringRef::compare_lower(StringRef RHS) const { 34 for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { 35 unsigned char LHC = ascii_tolower(Data[I]); 36 unsigned char RHC = ascii_tolower(RHS.Data[I]); 37 if (LHC != RHC) 38 return LHC < RHC ? -1 : 1; 39 } 40 41 if (Length == RHS.Length) 42 return 0; 43 return Length < RHS.Length ? -1 : 1; 44} 45 46/// compare_numeric - Compare strings, handle embedded numbers. 47int StringRef::compare_numeric(StringRef RHS) const { 48 for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) { 49 if (Data[I] == RHS.Data[I]) 50 continue; 51 if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) { 52 // The longer sequence of numbers is larger. This doesn't really handle 53 // prefixed zeros well. 54 for (size_t J = I+1; J != E+1; ++J) { 55 bool ld = J < Length && ascii_isdigit(Data[J]); 56 bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]); 57 if (ld != rd) 58 return rd ? -1 : 1; 59 if (!rd) 60 break; 61 } 62 } 63 return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; 64 } 65 if (Length == RHS.Length) 66 return 0; 67 return Length < RHS.Length ? -1 : 1; 68} 69 70// Compute the edit distance between the two given strings. 71unsigned StringRef::edit_distance(llvm::StringRef Other, 72 bool AllowReplacements, 73 unsigned MaxEditDistance) { 74 // The algorithm implemented below is the "classic" 75 // dynamic-programming algorithm for computing the Levenshtein 76 // distance, which is described here: 77 // 78 // http://en.wikipedia.org/wiki/Levenshtein_distance 79 // 80 // Although the algorithm is typically described using an m x n 81 // array, only two rows are used at a time, so this implemenation 82 // just keeps two separate vectors for those two rows. 83 size_type m = size(); 84 size_type n = Other.size(); 85 86 const unsigned SmallBufferSize = 64; 87 unsigned SmallBuffer[SmallBufferSize]; 88 llvm::OwningArrayPtr<unsigned> Allocated; 89 unsigned *previous = SmallBuffer; 90 if (2*(n + 1) > SmallBufferSize) { 91 previous = new unsigned [2*(n+1)]; 92 Allocated.reset(previous); 93 } 94 unsigned *current = previous + (n + 1); 95 96 for (unsigned i = 0; i <= n; ++i) 97 previous[i] = i; 98 99 for (size_type y = 1; y <= m; ++y) { 100 current[0] = y; 101 unsigned BestThisRow = current[0]; 102 103 for (size_type x = 1; x <= n; ++x) { 104 if (AllowReplacements) { 105 current[x] = min(previous[x-1] + ((*this)[y-1] == Other[x-1]? 0u:1u), 106 min(current[x-1], previous[x])+1); 107 } 108 else { 109 if ((*this)[y-1] == Other[x-1]) current[x] = previous[x-1]; 110 else current[x] = min(current[x-1], previous[x]) + 1; 111 } 112 BestThisRow = min(BestThisRow, current[x]); 113 } 114 115 if (MaxEditDistance && BestThisRow > MaxEditDistance) 116 return MaxEditDistance + 1; 117 118 unsigned *tmp = current; 119 current = previous; 120 previous = tmp; 121 } 122 123 unsigned Result = previous[n]; 124 return Result; 125} 126 127//===----------------------------------------------------------------------===// 128// String Searching 129//===----------------------------------------------------------------------===// 130 131 132/// find - Search for the first string \arg Str in the string. 133/// 134/// \return - The index of the first occurence of \arg Str, or npos if not 135/// found. 136size_t StringRef::find(StringRef Str, size_t From) const { 137 size_t N = Str.size(); 138 if (N > Length) 139 return npos; 140 for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i) 141 if (substr(i, N).equals(Str)) 142 return i; 143 return npos; 144} 145 146/// rfind - Search for the last string \arg Str in the string. 147/// 148/// \return - The index of the last occurence of \arg Str, or npos if not 149/// found. 150size_t StringRef::rfind(StringRef Str) const { 151 size_t N = Str.size(); 152 if (N > Length) 153 return npos; 154 for (size_t i = Length - N + 1, e = 0; i != e;) { 155 --i; 156 if (substr(i, N).equals(Str)) 157 return i; 158 } 159 return npos; 160} 161 162/// find_first_of - Find the first character in the string that is in \arg 163/// Chars, or npos if not found. 164/// 165/// Note: O(size() + Chars.size()) 166StringRef::size_type StringRef::find_first_of(StringRef Chars, 167 size_t From) const { 168 std::bitset<1 << CHAR_BIT> CharBits; 169 for (size_type i = 0; i != Chars.size(); ++i) 170 CharBits.set((unsigned char)Chars[i]); 171 172 for (size_type i = min(From, Length), e = Length; i != e; ++i) 173 if (CharBits.test((unsigned char)Data[i])) 174 return i; 175 return npos; 176} 177 178/// find_first_not_of - Find the first character in the string that is not 179/// \arg C or npos if not found. 180StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { 181 for (size_type i = min(From, Length), e = Length; i != e; ++i) 182 if (Data[i] != C) 183 return i; 184 return npos; 185} 186 187/// find_first_not_of - Find the first character in the string that is not 188/// in the string \arg Chars, or npos if not found. 189/// 190/// Note: O(size() + Chars.size()) 191StringRef::size_type StringRef::find_first_not_of(StringRef Chars, 192 size_t From) const { 193 std::bitset<1 << CHAR_BIT> CharBits; 194 for (size_type i = 0; i != Chars.size(); ++i) 195 CharBits.set((unsigned char)Chars[i]); 196 197 for (size_type i = min(From, Length), e = Length; i != e; ++i) 198 if (!CharBits.test((unsigned char)Data[i])) 199 return i; 200 return npos; 201} 202 203 204//===----------------------------------------------------------------------===// 205// Helpful Algorithms 206//===----------------------------------------------------------------------===// 207 208/// count - Return the number of non-overlapped occurrences of \arg Str in 209/// the string. 210size_t StringRef::count(StringRef Str) const { 211 size_t Count = 0; 212 size_t N = Str.size(); 213 if (N > Length) 214 return 0; 215 for (size_t i = 0, e = Length - N + 1; i != e; ++i) 216 if (substr(i, N).equals(Str)) 217 ++Count; 218 return Count; 219} 220 221static unsigned GetAutoSenseRadix(StringRef &Str) { 222 if (Str.startswith("0x")) { 223 Str = Str.substr(2); 224 return 16; 225 } else if (Str.startswith("0b")) { 226 Str = Str.substr(2); 227 return 2; 228 } else if (Str.startswith("0")) { 229 return 8; 230 } else { 231 return 10; 232 } 233} 234 235 236/// GetAsUnsignedInteger - Workhorse method that converts a integer character 237/// sequence of radix up to 36 to an unsigned long long value. 238static bool GetAsUnsignedInteger(StringRef Str, unsigned Radix, 239 unsigned long long &Result) { 240 // Autosense radix if not specified. 241 if (Radix == 0) 242 Radix = GetAutoSenseRadix(Str); 243 244 // Empty strings (after the radix autosense) are invalid. 245 if (Str.empty()) return true; 246 247 // Parse all the bytes of the string given this radix. Watch for overflow. 248 Result = 0; 249 while (!Str.empty()) { 250 unsigned CharVal; 251 if (Str[0] >= '0' && Str[0] <= '9') 252 CharVal = Str[0]-'0'; 253 else if (Str[0] >= 'a' && Str[0] <= 'z') 254 CharVal = Str[0]-'a'+10; 255 else if (Str[0] >= 'A' && Str[0] <= 'Z') 256 CharVal = Str[0]-'A'+10; 257 else 258 return true; 259 260 // If the parsed value is larger than the integer radix, the string is 261 // invalid. 262 if (CharVal >= Radix) 263 return true; 264 265 // Add in this character. 266 unsigned long long PrevResult = Result; 267 Result = Result*Radix+CharVal; 268 269 // Check for overflow. 270 if (Result < PrevResult) 271 return true; 272 273 Str = Str.substr(1); 274 } 275 276 return false; 277} 278 279bool StringRef::getAsInteger(unsigned Radix, unsigned long long &Result) const { 280 return GetAsUnsignedInteger(*this, Radix, Result); 281} 282 283 284bool StringRef::getAsInteger(unsigned Radix, long long &Result) const { 285 unsigned long long ULLVal; 286 287 // Handle positive strings first. 288 if (empty() || front() != '-') { 289 if (GetAsUnsignedInteger(*this, Radix, ULLVal) || 290 // Check for value so large it overflows a signed value. 291 (long long)ULLVal < 0) 292 return true; 293 Result = ULLVal; 294 return false; 295 } 296 297 // Get the positive part of the value. 298 if (GetAsUnsignedInteger(substr(1), Radix, ULLVal) || 299 // Reject values so large they'd overflow as negative signed, but allow 300 // "-0". This negates the unsigned so that the negative isn't undefined 301 // on signed overflow. 302 (long long)-ULLVal > 0) 303 return true; 304 305 Result = -ULLVal; 306 return false; 307} 308 309bool StringRef::getAsInteger(unsigned Radix, int &Result) const { 310 long long Val; 311 if (getAsInteger(Radix, Val) || 312 (int)Val != Val) 313 return true; 314 Result = Val; 315 return false; 316} 317 318bool StringRef::getAsInteger(unsigned Radix, unsigned &Result) const { 319 unsigned long long Val; 320 if (getAsInteger(Radix, Val) || 321 (unsigned)Val != Val) 322 return true; 323 Result = Val; 324 return false; 325} 326 327bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { 328 StringRef Str = *this; 329 330 // Autosense radix if not specified. 331 if (Radix == 0) 332 Radix = GetAutoSenseRadix(Str); 333 334 assert(Radix > 1 && Radix <= 36); 335 336 // Empty strings (after the radix autosense) are invalid. 337 if (Str.empty()) return true; 338 339 // Skip leading zeroes. This can be a significant improvement if 340 // it means we don't need > 64 bits. 341 while (!Str.empty() && Str.front() == '0') 342 Str = Str.substr(1); 343 344 // If it was nothing but zeroes.... 345 if (Str.empty()) { 346 Result = APInt(64, 0); 347 return false; 348 } 349 350 // (Over-)estimate the required number of bits. 351 unsigned Log2Radix = 0; 352 while ((1U << Log2Radix) < Radix) Log2Radix++; 353 bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); 354 355 unsigned BitWidth = Log2Radix * Str.size(); 356 if (BitWidth < Result.getBitWidth()) 357 BitWidth = Result.getBitWidth(); // don't shrink the result 358 else 359 Result.zext(BitWidth); 360 361 APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix 362 if (!IsPowerOf2Radix) { 363 // These must have the same bit-width as Result. 364 RadixAP = APInt(BitWidth, Radix); 365 CharAP = APInt(BitWidth, 0); 366 } 367 368 // Parse all the bytes of the string given this radix. 369 Result = 0; 370 while (!Str.empty()) { 371 unsigned CharVal; 372 if (Str[0] >= '0' && Str[0] <= '9') 373 CharVal = Str[0]-'0'; 374 else if (Str[0] >= 'a' && Str[0] <= 'z') 375 CharVal = Str[0]-'a'+10; 376 else if (Str[0] >= 'A' && Str[0] <= 'Z') 377 CharVal = Str[0]-'A'+10; 378 else 379 return true; 380 381 // If the parsed value is larger than the integer radix, the string is 382 // invalid. 383 if (CharVal >= Radix) 384 return true; 385 386 // Add in this character. 387 if (IsPowerOf2Radix) { 388 Result <<= Log2Radix; 389 Result |= CharVal; 390 } else { 391 Result *= RadixAP; 392 CharAP = CharVal; 393 Result += CharAP; 394 } 395 396 Str = Str.substr(1); 397 } 398 399 return false; 400} 401