StringRef.h revision 263508
1//===--- StringRef.h - Constant String Reference Wrapper --------*- C++ -*-===// 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#ifndef LLVM_ADT_STRINGREF_H 11#define LLVM_ADT_STRINGREF_H 12 13#include "llvm/Support/type_traits.h" 14#include <algorithm> 15#include <cassert> 16#include <cstring> 17#include <limits> 18#include <string> 19#include <utility> 20 21namespace llvm { 22 template <typename T> 23 class SmallVectorImpl; 24 class APInt; 25 class hash_code; 26 class StringRef; 27 28 /// Helper functions for StringRef::getAsInteger. 29 bool getAsUnsignedInteger(StringRef Str, unsigned Radix, 30 unsigned long long &Result); 31 32 bool getAsSignedInteger(StringRef Str, unsigned Radix, long long &Result); 33 34 /// StringRef - Represent a constant reference to a string, i.e. a character 35 /// array and a length, which need not be null terminated. 36 /// 37 /// This class does not own the string data, it is expected to be used in 38 /// situations where the character data resides in some other buffer, whose 39 /// lifetime extends past that of the StringRef. For this reason, it is not in 40 /// general safe to store a StringRef. 41 class StringRef { 42 public: 43 typedef const char *iterator; 44 typedef const char *const_iterator; 45 static const size_t npos = ~size_t(0); 46 typedef size_t size_type; 47 48 private: 49 /// The start of the string, in an external buffer. 50 const char *Data; 51 52 /// The length of the string. 53 size_t Length; 54 55 // Workaround PR5482: nearly all gcc 4.x miscompile StringRef and std::min() 56 // Changing the arg of min to be an integer, instead of a reference to an 57 // integer works around this bug. 58 static size_t min(size_t a, size_t b) { return a < b ? a : b; } 59 static size_t max(size_t a, size_t b) { return a > b ? a : b; } 60 61 // Workaround memcmp issue with null pointers (undefined behavior) 62 // by providing a specialized version 63 static int compareMemory(const char *Lhs, const char *Rhs, size_t Length) { 64 if (Length == 0) { return 0; } 65 return ::memcmp(Lhs,Rhs,Length); 66 } 67 68 public: 69 /// @name Constructors 70 /// @{ 71 72 /// Construct an empty string ref. 73 /*implicit*/ StringRef() : Data(0), Length(0) {} 74 75 /// Construct a string ref from a cstring. 76 /*implicit*/ StringRef(const char *Str) 77 : Data(Str) { 78 assert(Str && "StringRef cannot be built from a NULL argument"); 79 Length = ::strlen(Str); // invoking strlen(NULL) is undefined behavior 80 } 81 82 /// Construct a string ref from a pointer and length. 83 /*implicit*/ StringRef(const char *data, size_t length) 84 : Data(data), Length(length) { 85 assert((data || length == 0) && 86 "StringRef cannot be built from a NULL argument with non-null length"); 87 } 88 89 /// Construct a string ref from an std::string. 90 /*implicit*/ StringRef(const std::string &Str) 91 : Data(Str.data()), Length(Str.length()) {} 92 93 /// @} 94 /// @name Iterators 95 /// @{ 96 97 iterator begin() const { return Data; } 98 99 iterator end() const { return Data + Length; } 100 101 /// @} 102 /// @name String Operations 103 /// @{ 104 105 /// data - Get a pointer to the start of the string (which may not be null 106 /// terminated). 107 const char *data() const { return Data; } 108 109 /// empty - Check if the string is empty. 110 bool empty() const { return Length == 0; } 111 112 /// size - Get the string size. 113 size_t size() const { return Length; } 114 115 /// front - Get the first character in the string. 116 char front() const { 117 assert(!empty()); 118 return Data[0]; 119 } 120 121 /// back - Get the last character in the string. 122 char back() const { 123 assert(!empty()); 124 return Data[Length-1]; 125 } 126 127 /// equals - Check for string equality, this is more efficient than 128 /// compare() when the relative ordering of inequal strings isn't needed. 129 bool equals(StringRef RHS) const { 130 return (Length == RHS.Length && 131 compareMemory(Data, RHS.Data, RHS.Length) == 0); 132 } 133 134 /// equals_lower - Check for string equality, ignoring case. 135 bool equals_lower(StringRef RHS) const { 136 return Length == RHS.Length && compare_lower(RHS) == 0; 137 } 138 139 /// compare - Compare two strings; the result is -1, 0, or 1 if this string 140 /// is lexicographically less than, equal to, or greater than the \p RHS. 141 int compare(StringRef RHS) const { 142 // Check the prefix for a mismatch. 143 if (int Res = compareMemory(Data, RHS.Data, min(Length, RHS.Length))) 144 return Res < 0 ? -1 : 1; 145 146 // Otherwise the prefixes match, so we only need to check the lengths. 147 if (Length == RHS.Length) 148 return 0; 149 return Length < RHS.Length ? -1 : 1; 150 } 151 152 /// compare_lower - Compare two strings, ignoring case. 153 int compare_lower(StringRef RHS) const; 154 155 /// compare_numeric - Compare two strings, treating sequences of digits as 156 /// numbers. 157 int compare_numeric(StringRef RHS) const; 158 159 /// \brief Determine the edit distance between this string and another 160 /// string. 161 /// 162 /// \param Other the string to compare this string against. 163 /// 164 /// \param AllowReplacements whether to allow character 165 /// replacements (change one character into another) as a single 166 /// operation, rather than as two operations (an insertion and a 167 /// removal). 168 /// 169 /// \param MaxEditDistance If non-zero, the maximum edit distance that 170 /// this routine is allowed to compute. If the edit distance will exceed 171 /// that maximum, returns \c MaxEditDistance+1. 172 /// 173 /// \returns the minimum number of character insertions, removals, 174 /// or (if \p AllowReplacements is \c true) replacements needed to 175 /// transform one of the given strings into the other. If zero, 176 /// the strings are identical. 177 unsigned edit_distance(StringRef Other, bool AllowReplacements = true, 178 unsigned MaxEditDistance = 0) const; 179 180 /// str - Get the contents as an std::string. 181 std::string str() const { 182 if (Data == 0) return std::string(); 183 return std::string(Data, Length); 184 } 185 186 /// @} 187 /// @name Operator Overloads 188 /// @{ 189 190 char operator[](size_t Index) const { 191 assert(Index < Length && "Invalid index!"); 192 return Data[Index]; 193 } 194 195 /// @} 196 /// @name Type Conversions 197 /// @{ 198 199 operator std::string() const { 200 return str(); 201 } 202 203 /// @} 204 /// @name String Predicates 205 /// @{ 206 207 /// Check if this string starts with the given \p Prefix. 208 bool startswith(StringRef Prefix) const { 209 return Length >= Prefix.Length && 210 compareMemory(Data, Prefix.Data, Prefix.Length) == 0; 211 } 212 213 /// Check if this string starts with the given \p Prefix, ignoring case. 214 bool startswith_lower(StringRef Prefix) const; 215 216 /// Check if this string ends with the given \p Suffix. 217 bool endswith(StringRef Suffix) const { 218 return Length >= Suffix.Length && 219 compareMemory(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0; 220 } 221 222 /// Check if this string ends with the given \p Suffix, ignoring case. 223 bool endswith_lower(StringRef Suffix) const; 224 225 /// @} 226 /// @name String Searching 227 /// @{ 228 229 /// Search for the first character \p C in the string. 230 /// 231 /// \returns The index of the first occurrence of \p C, or npos if not 232 /// found. 233 size_t find(char C, size_t From = 0) const { 234 for (size_t i = min(From, Length), e = Length; i != e; ++i) 235 if (Data[i] == C) 236 return i; 237 return npos; 238 } 239 240 /// Search for the first string \p Str in the string. 241 /// 242 /// \returns The index of the first occurrence of \p Str, or npos if not 243 /// found. 244 size_t find(StringRef Str, size_t From = 0) const; 245 246 /// Search for the last character \p C in the string. 247 /// 248 /// \returns The index of the last occurrence of \p C, or npos if not 249 /// found. 250 size_t rfind(char C, size_t From = npos) const { 251 From = min(From, Length); 252 size_t i = From; 253 while (i != 0) { 254 --i; 255 if (Data[i] == C) 256 return i; 257 } 258 return npos; 259 } 260 261 /// Search for the last string \p Str in the string. 262 /// 263 /// \returns The index of the last occurrence of \p Str, or npos if not 264 /// found. 265 size_t rfind(StringRef Str) const; 266 267 /// Find the first character in the string that is \p C, or npos if not 268 /// found. Same as find. 269 size_t find_first_of(char C, size_t From = 0) const { 270 return find(C, From); 271 } 272 273 /// Find the first character in the string that is in \p Chars, or npos if 274 /// not found. 275 /// 276 /// Complexity: O(size() + Chars.size()) 277 size_t find_first_of(StringRef Chars, size_t From = 0) const; 278 279 /// Find the first character in the string that is not \p C or npos if not 280 /// found. 281 size_t find_first_not_of(char C, size_t From = 0) const; 282 283 /// Find the first character in the string that is not in the string 284 /// \p Chars, or npos if not found. 285 /// 286 /// Complexity: O(size() + Chars.size()) 287 size_t find_first_not_of(StringRef Chars, size_t From = 0) const; 288 289 /// Find the last character in the string that is \p C, or npos if not 290 /// found. 291 size_t find_last_of(char C, size_t From = npos) const { 292 return rfind(C, From); 293 } 294 295 /// Find the last character in the string that is in \p C, or npos if not 296 /// found. 297 /// 298 /// Complexity: O(size() + Chars.size()) 299 size_t find_last_of(StringRef Chars, size_t From = npos) const; 300 301 /// Find the last character in the string that is not \p C, or npos if not 302 /// found. 303 size_t find_last_not_of(char C, size_t From = npos) const; 304 305 /// Find the last character in the string that is not in \p Chars, or 306 /// npos if not found. 307 /// 308 /// Complexity: O(size() + Chars.size()) 309 size_t find_last_not_of(StringRef Chars, size_t From = npos) const; 310 311 /// @} 312 /// @name Helpful Algorithms 313 /// @{ 314 315 /// Return the number of occurrences of \p C in the string. 316 size_t count(char C) const { 317 size_t Count = 0; 318 for (size_t i = 0, e = Length; i != e; ++i) 319 if (Data[i] == C) 320 ++Count; 321 return Count; 322 } 323 324 /// Return the number of non-overlapped occurrences of \p Str in 325 /// the string. 326 size_t count(StringRef Str) const; 327 328 /// Parse the current string as an integer of the specified radix. If 329 /// \p Radix is specified as zero, this does radix autosensing using 330 /// extended C rules: 0 is octal, 0x is hex, 0b is binary. 331 /// 332 /// If the string is invalid or if only a subset of the string is valid, 333 /// this returns true to signify the error. The string is considered 334 /// erroneous if empty or if it overflows T. 335 template <typename T> 336 typename enable_if_c<std::numeric_limits<T>::is_signed, bool>::type 337 getAsInteger(unsigned Radix, T &Result) const { 338 long long LLVal; 339 if (getAsSignedInteger(*this, Radix, LLVal) || 340 static_cast<T>(LLVal) != LLVal) 341 return true; 342 Result = LLVal; 343 return false; 344 } 345 346 template <typename T> 347 typename enable_if_c<!std::numeric_limits<T>::is_signed, bool>::type 348 getAsInteger(unsigned Radix, T &Result) const { 349 unsigned long long ULLVal; 350 if (getAsUnsignedInteger(*this, Radix, ULLVal) || 351 static_cast<T>(ULLVal) != ULLVal) 352 return true; 353 Result = ULLVal; 354 return false; 355 } 356 357 /// Parse the current string as an integer of the specified \p Radix, or of 358 /// an autosensed radix if the \p Radix given is 0. The current value in 359 /// \p Result is discarded, and the storage is changed to be wide enough to 360 /// store the parsed integer. 361 /// 362 /// \returns true if the string does not solely consist of a valid 363 /// non-empty number in the appropriate base. 364 /// 365 /// APInt::fromString is superficially similar but assumes the 366 /// string is well-formed in the given radix. 367 bool getAsInteger(unsigned Radix, APInt &Result) const; 368 369 /// @} 370 /// @name String Operations 371 /// @{ 372 373 // Convert the given ASCII string to lowercase. 374 std::string lower() const; 375 376 /// Convert the given ASCII string to uppercase. 377 std::string upper() const; 378 379 /// @} 380 /// @name Substring Operations 381 /// @{ 382 383 /// Return a reference to the substring from [Start, Start + N). 384 /// 385 /// \param Start The index of the starting character in the substring; if 386 /// the index is npos or greater than the length of the string then the 387 /// empty substring will be returned. 388 /// 389 /// \param N The number of characters to included in the substring. If N 390 /// exceeds the number of characters remaining in the string, the string 391 /// suffix (starting with \p Start) will be returned. 392 StringRef substr(size_t Start, size_t N = npos) const { 393 Start = min(Start, Length); 394 return StringRef(Data + Start, min(N, Length - Start)); 395 } 396 397 /// Return a StringRef equal to 'this' but with the first \p N elements 398 /// dropped. 399 StringRef drop_front(size_t N = 1) const { 400 assert(size() >= N && "Dropping more elements than exist"); 401 return substr(N); 402 } 403 404 /// Return a StringRef equal to 'this' but with the last \p N elements 405 /// dropped. 406 StringRef drop_back(size_t N = 1) const { 407 assert(size() >= N && "Dropping more elements than exist"); 408 return substr(0, size()-N); 409 } 410 411 /// Return a reference to the substring from [Start, End). 412 /// 413 /// \param Start The index of the starting character in the substring; if 414 /// the index is npos or greater than the length of the string then the 415 /// empty substring will be returned. 416 /// 417 /// \param End The index following the last character to include in the 418 /// substring. If this is npos, or less than \p Start, or exceeds the 419 /// number of characters remaining in the string, the string suffix 420 /// (starting with \p Start) will be returned. 421 StringRef slice(size_t Start, size_t End) const { 422 Start = min(Start, Length); 423 End = min(max(Start, End), Length); 424 return StringRef(Data + Start, End - Start); 425 } 426 427 /// Split into two substrings around the first occurrence of a separator 428 /// character. 429 /// 430 /// If \p Separator is in the string, then the result is a pair (LHS, RHS) 431 /// such that (*this == LHS + Separator + RHS) is true and RHS is 432 /// maximal. If \p Separator is not in the string, then the result is a 433 /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). 434 /// 435 /// \param Separator The character to split on. 436 /// \returns The split substrings. 437 std::pair<StringRef, StringRef> split(char Separator) const { 438 size_t Idx = find(Separator); 439 if (Idx == npos) 440 return std::make_pair(*this, StringRef()); 441 return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); 442 } 443 444 /// Split into two substrings around the first occurrence of a separator 445 /// string. 446 /// 447 /// If \p Separator is in the string, then the result is a pair (LHS, RHS) 448 /// such that (*this == LHS + Separator + RHS) is true and RHS is 449 /// maximal. If \p Separator is not in the string, then the result is a 450 /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). 451 /// 452 /// \param Separator - The string to split on. 453 /// \return - The split substrings. 454 std::pair<StringRef, StringRef> split(StringRef Separator) const { 455 size_t Idx = find(Separator); 456 if (Idx == npos) 457 return std::make_pair(*this, StringRef()); 458 return std::make_pair(slice(0, Idx), slice(Idx + Separator.size(), npos)); 459 } 460 461 /// Split into substrings around the occurrences of a separator string. 462 /// 463 /// Each substring is stored in \p A. If \p MaxSplit is >= 0, at most 464 /// \p MaxSplit splits are done and consequently <= \p MaxSplit 465 /// elements are added to A. 466 /// If \p KeepEmpty is false, empty strings are not added to \p A. They 467 /// still count when considering \p MaxSplit 468 /// An useful invariant is that 469 /// Separator.join(A) == *this if MaxSplit == -1 and KeepEmpty == true 470 /// 471 /// \param A - Where to put the substrings. 472 /// \param Separator - The string to split on. 473 /// \param MaxSplit - The maximum number of times the string is split. 474 /// \param KeepEmpty - True if empty substring should be added. 475 void split(SmallVectorImpl<StringRef> &A, 476 StringRef Separator, int MaxSplit = -1, 477 bool KeepEmpty = true) const; 478 479 /// Split into two substrings around the last occurrence of a separator 480 /// character. 481 /// 482 /// If \p Separator is in the string, then the result is a pair (LHS, RHS) 483 /// such that (*this == LHS + Separator + RHS) is true and RHS is 484 /// minimal. If \p Separator is not in the string, then the result is a 485 /// pair (LHS, RHS) where (*this == LHS) and (RHS == ""). 486 /// 487 /// \param Separator - The character to split on. 488 /// \return - The split substrings. 489 std::pair<StringRef, StringRef> rsplit(char Separator) const { 490 size_t Idx = rfind(Separator); 491 if (Idx == npos) 492 return std::make_pair(*this, StringRef()); 493 return std::make_pair(slice(0, Idx), slice(Idx+1, npos)); 494 } 495 496 /// Return string with consecutive characters in \p Chars starting from 497 /// the left removed. 498 StringRef ltrim(StringRef Chars = " \t\n\v\f\r") const { 499 return drop_front(std::min(Length, find_first_not_of(Chars))); 500 } 501 502 /// Return string with consecutive characters in \p Chars starting from 503 /// the right removed. 504 StringRef rtrim(StringRef Chars = " \t\n\v\f\r") const { 505 return drop_back(Length - std::min(Length, find_last_not_of(Chars) + 1)); 506 } 507 508 /// Return string with consecutive characters in \p Chars starting from 509 /// the left and right removed. 510 StringRef trim(StringRef Chars = " \t\n\v\f\r") const { 511 return ltrim(Chars).rtrim(Chars); 512 } 513 514 /// @} 515 }; 516 517 /// @name StringRef Comparison Operators 518 /// @{ 519 520 inline bool operator==(StringRef LHS, StringRef RHS) { 521 return LHS.equals(RHS); 522 } 523 524 inline bool operator!=(StringRef LHS, StringRef RHS) { 525 return !(LHS == RHS); 526 } 527 528 inline bool operator<(StringRef LHS, StringRef RHS) { 529 return LHS.compare(RHS) == -1; 530 } 531 532 inline bool operator<=(StringRef LHS, StringRef RHS) { 533 return LHS.compare(RHS) != 1; 534 } 535 536 inline bool operator>(StringRef LHS, StringRef RHS) { 537 return LHS.compare(RHS) == 1; 538 } 539 540 inline bool operator>=(StringRef LHS, StringRef RHS) { 541 return LHS.compare(RHS) != -1; 542 } 543 544 inline std::string &operator+=(std::string &buffer, StringRef string) { 545 return buffer.append(string.data(), string.size()); 546 } 547 548 /// @} 549 550 /// \brief Compute a hash_code for a StringRef. 551 hash_code hash_value(StringRef S); 552 553 // StringRefs can be treated like a POD type. 554 template <typename T> struct isPodLike; 555 template <> struct isPodLike<StringRef> { static const bool value = true; }; 556 557 /// Construct a string ref from a boolean. 558 inline StringRef toStringRef(bool B) { 559 return StringRef(B ? "true" : "false"); 560 } 561} 562 563#endif 564