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/Hashing.h"
13#include "llvm/ADT/OwningPtr.h"
14#include "llvm/ADT/edit_distance.h"
15#include <bitset>
16
17using namespace llvm;
18
19// MSVC emits references to this into the translation units which reference it.
20#ifndef _MSC_VER
21const size_t StringRef::npos;
22#endif
23
24static char ascii_tolower(char x) {
25  if (x >= 'A' && x <= 'Z')
26    return x - 'A' + 'a';
27  return x;
28}
29
30static char ascii_toupper(char x) {
31  if (x >= 'a' && x <= 'z')
32    return x - 'a' + 'A';
33  return x;
34}
35
36static bool ascii_isdigit(char x) {
37  return x >= '0' && x <= '9';
38}
39
40/// compare_lower - Compare strings, ignoring case.
41int StringRef::compare_lower(StringRef RHS) const {
42  for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) {
43    unsigned char LHC = ascii_tolower(Data[I]);
44    unsigned char RHC = ascii_tolower(RHS.Data[I]);
45    if (LHC != RHC)
46      return LHC < RHC ? -1 : 1;
47  }
48
49  if (Length == RHS.Length)
50    return 0;
51  return Length < RHS.Length ? -1 : 1;
52}
53
54/// compare_numeric - Compare strings, handle embedded numbers.
55int StringRef::compare_numeric(StringRef RHS) const {
56  for (size_t I = 0, E = min(Length, RHS.Length); I != E; ++I) {
57    // Check for sequences of digits.
58    if (ascii_isdigit(Data[I]) && ascii_isdigit(RHS.Data[I])) {
59      // The longer sequence of numbers is considered larger.
60      // This doesn't really handle prefixed zeros well.
61      size_t J;
62      for (J = I + 1; J != E + 1; ++J) {
63        bool ld = J < Length && ascii_isdigit(Data[J]);
64        bool rd = J < RHS.Length && ascii_isdigit(RHS.Data[J]);
65        if (ld != rd)
66          return rd ? -1 : 1;
67        if (!rd)
68          break;
69      }
70      // The two number sequences have the same length (J-I), just memcmp them.
71      if (int Res = compareMemory(Data + I, RHS.Data + I, J - I))
72        return Res < 0 ? -1 : 1;
73      // Identical number sequences, continue search after the numbers.
74      I = J - 1;
75      continue;
76    }
77    if (Data[I] != RHS.Data[I])
78      return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1;
79  }
80  if (Length == RHS.Length)
81    return 0;
82  return Length < RHS.Length ? -1 : 1;
83}
84
85// Compute the edit distance between the two given strings.
86unsigned StringRef::edit_distance(llvm::StringRef Other,
87                                  bool AllowReplacements,
88                                  unsigned MaxEditDistance) {
89  return llvm::ComputeEditDistance(
90      llvm::ArrayRef<char>(data(), size()),
91      llvm::ArrayRef<char>(Other.data(), Other.size()),
92      AllowReplacements, MaxEditDistance);
93}
94
95//===----------------------------------------------------------------------===//
96// String Operations
97//===----------------------------------------------------------------------===//
98
99std::string StringRef::lower() const {
100  std::string Result(size(), char());
101  for (size_type i = 0, e = size(); i != e; ++i) {
102    Result[i] = ascii_tolower(Data[i]);
103  }
104  return Result;
105}
106
107std::string StringRef::upper() const {
108  std::string Result(size(), char());
109  for (size_type i = 0, e = size(); i != e; ++i) {
110    Result[i] = ascii_toupper(Data[i]);
111  }
112  return Result;
113}
114
115//===----------------------------------------------------------------------===//
116// String Searching
117//===----------------------------------------------------------------------===//
118
119
120/// find - Search for the first string \arg Str in the string.
121///
122/// \return - The index of the first occurrence of \arg Str, or npos if not
123/// found.
124size_t StringRef::find(StringRef Str, size_t From) const {
125  size_t N = Str.size();
126  if (N > Length)
127    return npos;
128
129  // For short haystacks or unsupported needles fall back to the naive algorithm
130  if (Length < 16 || N > 255 || N == 0) {
131    for (size_t e = Length - N + 1, i = min(From, e); i != e; ++i)
132      if (substr(i, N).equals(Str))
133        return i;
134    return npos;
135  }
136
137  if (From >= Length)
138    return npos;
139
140  // Build the bad char heuristic table, with uint8_t to reduce cache thrashing.
141  uint8_t BadCharSkip[256];
142  std::memset(BadCharSkip, N, 256);
143  for (unsigned i = 0; i != N-1; ++i)
144    BadCharSkip[(uint8_t)Str[i]] = N-1-i;
145
146  unsigned Len = Length-From, Pos = From;
147  while (Len >= N) {
148    if (substr(Pos, N).equals(Str)) // See if this is the correct substring.
149      return Pos;
150
151    // Otherwise skip the appropriate number of bytes.
152    uint8_t Skip = BadCharSkip[(uint8_t)(*this)[Pos+N-1]];
153    Len -= Skip;
154    Pos += Skip;
155  }
156
157  return npos;
158}
159
160/// rfind - Search for the last string \arg Str in the string.
161///
162/// \return - The index of the last occurrence of \arg Str, or npos if not
163/// found.
164size_t StringRef::rfind(StringRef Str) const {
165  size_t N = Str.size();
166  if (N > Length)
167    return npos;
168  for (size_t i = Length - N + 1, e = 0; i != e;) {
169    --i;
170    if (substr(i, N).equals(Str))
171      return i;
172  }
173  return npos;
174}
175
176/// find_first_of - Find the first character in the string that is in \arg
177/// Chars, or npos if not found.
178///
179/// Note: O(size() + Chars.size())
180StringRef::size_type StringRef::find_first_of(StringRef Chars,
181                                              size_t From) const {
182  std::bitset<1 << CHAR_BIT> CharBits;
183  for (size_type i = 0; i != Chars.size(); ++i)
184    CharBits.set((unsigned char)Chars[i]);
185
186  for (size_type i = min(From, Length), e = Length; i != e; ++i)
187    if (CharBits.test((unsigned char)Data[i]))
188      return i;
189  return npos;
190}
191
192/// find_first_not_of - Find the first character in the string that is not
193/// \arg C or npos if not found.
194StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const {
195  for (size_type i = min(From, Length), e = Length; i != e; ++i)
196    if (Data[i] != C)
197      return i;
198  return npos;
199}
200
201/// find_first_not_of - Find the first character in the string that is not
202/// in the string \arg Chars, or npos if not found.
203///
204/// Note: O(size() + Chars.size())
205StringRef::size_type StringRef::find_first_not_of(StringRef Chars,
206                                                  size_t From) const {
207  std::bitset<1 << CHAR_BIT> CharBits;
208  for (size_type i = 0; i != Chars.size(); ++i)
209    CharBits.set((unsigned char)Chars[i]);
210
211  for (size_type i = min(From, Length), e = Length; i != e; ++i)
212    if (!CharBits.test((unsigned char)Data[i]))
213      return i;
214  return npos;
215}
216
217/// find_last_of - Find the last character in the string that is in \arg C,
218/// or npos if not found.
219///
220/// Note: O(size() + Chars.size())
221StringRef::size_type StringRef::find_last_of(StringRef Chars,
222                                             size_t From) const {
223  std::bitset<1 << CHAR_BIT> CharBits;
224  for (size_type i = 0; i != Chars.size(); ++i)
225    CharBits.set((unsigned char)Chars[i]);
226
227  for (size_type i = min(From, Length) - 1, e = -1; i != e; --i)
228    if (CharBits.test((unsigned char)Data[i]))
229      return i;
230  return npos;
231}
232
233/// find_last_not_of - Find the last character in the string that is not
234/// \arg C, or npos if not found.
235StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const {
236  for (size_type i = min(From, Length) - 1, e = -1; i != e; --i)
237    if (Data[i] != C)
238      return i;
239  return npos;
240}
241
242/// find_last_not_of - Find the last character in the string that is not in
243/// \arg Chars, or npos if not found.
244///
245/// Note: O(size() + Chars.size())
246StringRef::size_type StringRef::find_last_not_of(StringRef Chars,
247                                                 size_t From) const {
248  std::bitset<1 << CHAR_BIT> CharBits;
249  for (size_type i = 0, e = Chars.size(); i != e; ++i)
250    CharBits.set((unsigned char)Chars[i]);
251
252  for (size_type i = min(From, Length) - 1, e = -1; i != e; --i)
253    if (!CharBits.test((unsigned char)Data[i]))
254      return i;
255  return npos;
256}
257
258void StringRef::split(SmallVectorImpl<StringRef> &A,
259                      StringRef Separators, int MaxSplit,
260                      bool KeepEmpty) const {
261  StringRef rest = *this;
262
263  // rest.data() is used to distinguish cases like "a," that splits into
264  // "a" + "" and "a" that splits into "a" + 0.
265  for (int splits = 0;
266       rest.data() != NULL && (MaxSplit < 0 || splits < MaxSplit);
267       ++splits) {
268    std::pair<StringRef, StringRef> p = rest.split(Separators);
269
270    if (KeepEmpty || p.first.size() != 0)
271      A.push_back(p.first);
272    rest = p.second;
273  }
274  // If we have a tail left, add it.
275  if (rest.data() != NULL && (rest.size() != 0 || KeepEmpty))
276    A.push_back(rest);
277}
278
279//===----------------------------------------------------------------------===//
280// Helpful Algorithms
281//===----------------------------------------------------------------------===//
282
283/// count - Return the number of non-overlapped occurrences of \arg Str in
284/// the string.
285size_t StringRef::count(StringRef Str) const {
286  size_t Count = 0;
287  size_t N = Str.size();
288  if (N > Length)
289    return 0;
290  for (size_t i = 0, e = Length - N + 1; i != e; ++i)
291    if (substr(i, N).equals(Str))
292      ++Count;
293  return Count;
294}
295
296static unsigned GetAutoSenseRadix(StringRef &Str) {
297  if (Str.startswith("0x")) {
298    Str = Str.substr(2);
299    return 16;
300  }
301
302  if (Str.startswith("0b")) {
303    Str = Str.substr(2);
304    return 2;
305  }
306
307  if (Str.startswith("0o")) {
308    Str = Str.substr(2);
309    return 8;
310  }
311
312  if (Str.startswith("0"))
313    return 8;
314
315  return 10;
316}
317
318
319/// GetAsUnsignedInteger - Workhorse method that converts a integer character
320/// sequence of radix up to 36 to an unsigned long long value.
321bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix,
322                                unsigned long long &Result) {
323  // Autosense radix if not specified.
324  if (Radix == 0)
325    Radix = GetAutoSenseRadix(Str);
326
327  // Empty strings (after the radix autosense) are invalid.
328  if (Str.empty()) return true;
329
330  // Parse all the bytes of the string given this radix.  Watch for overflow.
331  Result = 0;
332  while (!Str.empty()) {
333    unsigned CharVal;
334    if (Str[0] >= '0' && Str[0] <= '9')
335      CharVal = Str[0]-'0';
336    else if (Str[0] >= 'a' && Str[0] <= 'z')
337      CharVal = Str[0]-'a'+10;
338    else if (Str[0] >= 'A' && Str[0] <= 'Z')
339      CharVal = Str[0]-'A'+10;
340    else
341      return true;
342
343    // If the parsed value is larger than the integer radix, the string is
344    // invalid.
345    if (CharVal >= Radix)
346      return true;
347
348    // Add in this character.
349    unsigned long long PrevResult = Result;
350    Result = Result*Radix+CharVal;
351
352    // Check for overflow by shifting back and seeing if bits were lost.
353    if (Result/Radix < PrevResult)
354      return true;
355
356    Str = Str.substr(1);
357  }
358
359  return false;
360}
361
362bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix,
363                              long long &Result) {
364  unsigned long long ULLVal;
365
366  // Handle positive strings first.
367  if (Str.empty() || Str.front() != '-') {
368    if (getAsUnsignedInteger(Str, Radix, ULLVal) ||
369        // Check for value so large it overflows a signed value.
370        (long long)ULLVal < 0)
371      return true;
372    Result = ULLVal;
373    return false;
374  }
375
376  // Get the positive part of the value.
377  if (getAsUnsignedInteger(Str.substr(1), Radix, ULLVal) ||
378      // Reject values so large they'd overflow as negative signed, but allow
379      // "-0".  This negates the unsigned so that the negative isn't undefined
380      // on signed overflow.
381      (long long)-ULLVal > 0)
382    return true;
383
384  Result = -ULLVal;
385  return false;
386}
387
388bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const {
389  StringRef Str = *this;
390
391  // Autosense radix if not specified.
392  if (Radix == 0)
393    Radix = GetAutoSenseRadix(Str);
394
395  assert(Radix > 1 && Radix <= 36);
396
397  // Empty strings (after the radix autosense) are invalid.
398  if (Str.empty()) return true;
399
400  // Skip leading zeroes.  This can be a significant improvement if
401  // it means we don't need > 64 bits.
402  while (!Str.empty() && Str.front() == '0')
403    Str = Str.substr(1);
404
405  // If it was nothing but zeroes....
406  if (Str.empty()) {
407    Result = APInt(64, 0);
408    return false;
409  }
410
411  // (Over-)estimate the required number of bits.
412  unsigned Log2Radix = 0;
413  while ((1U << Log2Radix) < Radix) Log2Radix++;
414  bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix);
415
416  unsigned BitWidth = Log2Radix * Str.size();
417  if (BitWidth < Result.getBitWidth())
418    BitWidth = Result.getBitWidth(); // don't shrink the result
419  else if (BitWidth > Result.getBitWidth())
420    Result = Result.zext(BitWidth);
421
422  APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix
423  if (!IsPowerOf2Radix) {
424    // These must have the same bit-width as Result.
425    RadixAP = APInt(BitWidth, Radix);
426    CharAP = APInt(BitWidth, 0);
427  }
428
429  // Parse all the bytes of the string given this radix.
430  Result = 0;
431  while (!Str.empty()) {
432    unsigned CharVal;
433    if (Str[0] >= '0' && Str[0] <= '9')
434      CharVal = Str[0]-'0';
435    else if (Str[0] >= 'a' && Str[0] <= 'z')
436      CharVal = Str[0]-'a'+10;
437    else if (Str[0] >= 'A' && Str[0] <= 'Z')
438      CharVal = Str[0]-'A'+10;
439    else
440      return true;
441
442    // If the parsed value is larger than the integer radix, the string is
443    // invalid.
444    if (CharVal >= Radix)
445      return true;
446
447    // Add in this character.
448    if (IsPowerOf2Radix) {
449      Result <<= Log2Radix;
450      Result |= CharVal;
451    } else {
452      Result *= RadixAP;
453      CharAP = CharVal;
454      Result += CharAP;
455    }
456
457    Str = Str.substr(1);
458  }
459
460  return false;
461}
462
463
464// Implementation of StringRef hashing.
465hash_code llvm::hash_value(StringRef S) {
466  return hash_combine_range(S.begin(), S.end());
467}
468