File: | llvm/include/llvm/ADT/edit_distance.h |
Warning: | line 96, column 3 Assigned value is garbage or undefined |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- StringRef.cpp - Lightweight String References ---------------------===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | ||||
9 | #include "llvm/ADT/StringRef.h" | |||
10 | #include "llvm/ADT/APFloat.h" | |||
11 | #include "llvm/ADT/APInt.h" | |||
12 | #include "llvm/ADT/Hashing.h" | |||
13 | #include "llvm/ADT/StringExtras.h" | |||
14 | #include "llvm/ADT/edit_distance.h" | |||
15 | #include <bitset> | |||
16 | ||||
17 | using namespace llvm; | |||
18 | ||||
19 | // MSVC emits references to this into the translation units which reference it. | |||
20 | #ifndef _MSC_VER | |||
21 | const size_t StringRef::npos; | |||
22 | #endif | |||
23 | ||||
24 | // strncasecmp() is not available on non-POSIX systems, so define an | |||
25 | // alternative function here. | |||
26 | static int ascii_strncasecmp(const char *LHS, const char *RHS, size_t Length) { | |||
27 | for (size_t I = 0; I < Length; ++I) { | |||
28 | unsigned char LHC = toLower(LHS[I]); | |||
29 | unsigned char RHC = toLower(RHS[I]); | |||
30 | if (LHC != RHC) | |||
31 | return LHC < RHC ? -1 : 1; | |||
32 | } | |||
33 | return 0; | |||
34 | } | |||
35 | ||||
36 | /// compare_lower - Compare strings, ignoring case. | |||
37 | int StringRef::compare_lower(StringRef RHS) const { | |||
38 | if (int Res = ascii_strncasecmp(Data, RHS.Data, std::min(Length, RHS.Length))) | |||
39 | return Res; | |||
40 | if (Length == RHS.Length) | |||
41 | return 0; | |||
42 | return Length < RHS.Length ? -1 : 1; | |||
43 | } | |||
44 | ||||
45 | /// Check if this string starts with the given \p Prefix, ignoring case. | |||
46 | bool StringRef::startswith_lower(StringRef Prefix) const { | |||
47 | return Length >= Prefix.Length && | |||
48 | ascii_strncasecmp(Data, Prefix.Data, Prefix.Length) == 0; | |||
49 | } | |||
50 | ||||
51 | /// Check if this string ends with the given \p Suffix, ignoring case. | |||
52 | bool StringRef::endswith_lower(StringRef Suffix) const { | |||
53 | return Length >= Suffix.Length && | |||
54 | ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0; | |||
55 | } | |||
56 | ||||
57 | size_t StringRef::find_lower(char C, size_t From) const { | |||
58 | char L = toLower(C); | |||
59 | return find_if([L](char D) { return toLower(D) == L; }, From); | |||
60 | } | |||
61 | ||||
62 | /// compare_numeric - Compare strings, handle embedded numbers. | |||
63 | int StringRef::compare_numeric(StringRef RHS) const { | |||
64 | for (size_t I = 0, E = std::min(Length, RHS.Length); I != E; ++I) { | |||
65 | // Check for sequences of digits. | |||
66 | if (isDigit(Data[I]) && isDigit(RHS.Data[I])) { | |||
67 | // The longer sequence of numbers is considered larger. | |||
68 | // This doesn't really handle prefixed zeros well. | |||
69 | size_t J; | |||
70 | for (J = I + 1; J != E + 1; ++J) { | |||
71 | bool ld = J < Length && isDigit(Data[J]); | |||
72 | bool rd = J < RHS.Length && isDigit(RHS.Data[J]); | |||
73 | if (ld != rd) | |||
74 | return rd ? -1 : 1; | |||
75 | if (!rd) | |||
76 | break; | |||
77 | } | |||
78 | // The two number sequences have the same length (J-I), just memcmp them. | |||
79 | if (int Res = compareMemory(Data + I, RHS.Data + I, J - I)) | |||
80 | return Res < 0 ? -1 : 1; | |||
81 | // Identical number sequences, continue search after the numbers. | |||
82 | I = J - 1; | |||
83 | continue; | |||
84 | } | |||
85 | if (Data[I] != RHS.Data[I]) | |||
86 | return (unsigned char)Data[I] < (unsigned char)RHS.Data[I] ? -1 : 1; | |||
87 | } | |||
88 | if (Length == RHS.Length) | |||
89 | return 0; | |||
90 | return Length < RHS.Length ? -1 : 1; | |||
91 | } | |||
92 | ||||
93 | // Compute the edit distance between the two given strings. | |||
94 | unsigned StringRef::edit_distance(llvm::StringRef Other, | |||
95 | bool AllowReplacements, | |||
96 | unsigned MaxEditDistance) const { | |||
97 | return llvm::ComputeEditDistance( | |||
| ||||
98 | makeArrayRef(data(), size()), | |||
99 | makeArrayRef(Other.data(), Other.size()), | |||
100 | AllowReplacements, MaxEditDistance); | |||
101 | } | |||
102 | ||||
103 | //===----------------------------------------------------------------------===// | |||
104 | // String Operations | |||
105 | //===----------------------------------------------------------------------===// | |||
106 | ||||
107 | std::string StringRef::lower() const { | |||
108 | std::string Result(size(), char()); | |||
109 | for (size_type i = 0, e = size(); i != e; ++i) { | |||
110 | Result[i] = toLower(Data[i]); | |||
111 | } | |||
112 | return Result; | |||
113 | } | |||
114 | ||||
115 | std::string StringRef::upper() const { | |||
116 | std::string Result(size(), char()); | |||
117 | for (size_type i = 0, e = size(); i != e; ++i) { | |||
118 | Result[i] = toUpper(Data[i]); | |||
119 | } | |||
120 | return Result; | |||
121 | } | |||
122 | ||||
123 | //===----------------------------------------------------------------------===// | |||
124 | // String Searching | |||
125 | //===----------------------------------------------------------------------===// | |||
126 | ||||
127 | ||||
128 | /// find - Search for the first string \arg Str in the string. | |||
129 | /// | |||
130 | /// \return - The index of the first occurrence of \arg Str, or npos if not | |||
131 | /// found. | |||
132 | size_t StringRef::find(StringRef Str, size_t From) const { | |||
133 | if (From > Length) | |||
134 | return npos; | |||
135 | ||||
136 | const char *Start = Data + From; | |||
137 | size_t Size = Length - From; | |||
138 | ||||
139 | const char *Needle = Str.data(); | |||
140 | size_t N = Str.size(); | |||
141 | if (N == 0) | |||
142 | return From; | |||
143 | if (Size < N) | |||
144 | return npos; | |||
145 | if (N == 1) { | |||
146 | const char *Ptr = (const char *)::memchr(Start, Needle[0], Size); | |||
147 | return Ptr == nullptr ? npos : Ptr - Data; | |||
148 | } | |||
149 | ||||
150 | const char *Stop = Start + (Size - N + 1); | |||
151 | ||||
152 | // For short haystacks or unsupported needles fall back to the naive algorithm | |||
153 | if (Size < 16 || N > 255) { | |||
154 | do { | |||
155 | if (std::memcmp(Start, Needle, N) == 0) | |||
156 | return Start - Data; | |||
157 | ++Start; | |||
158 | } while (Start < Stop); | |||
159 | return npos; | |||
160 | } | |||
161 | ||||
162 | // Build the bad char heuristic table, with uint8_t to reduce cache thrashing. | |||
163 | uint8_t BadCharSkip[256]; | |||
164 | std::memset(BadCharSkip, N, 256); | |||
165 | for (unsigned i = 0; i != N-1; ++i) | |||
166 | BadCharSkip[(uint8_t)Str[i]] = N-1-i; | |||
167 | ||||
168 | do { | |||
169 | uint8_t Last = Start[N - 1]; | |||
170 | if (LLVM_UNLIKELY(Last == (uint8_t)Needle[N - 1])__builtin_expect((bool)(Last == (uint8_t)Needle[N - 1]), false )) | |||
171 | if (std::memcmp(Start, Needle, N - 1) == 0) | |||
172 | return Start - Data; | |||
173 | ||||
174 | // Otherwise skip the appropriate number of bytes. | |||
175 | Start += BadCharSkip[Last]; | |||
176 | } while (Start < Stop); | |||
177 | ||||
178 | return npos; | |||
179 | } | |||
180 | ||||
181 | size_t StringRef::find_lower(StringRef Str, size_t From) const { | |||
182 | StringRef This = substr(From); | |||
183 | while (This.size() >= Str.size()) { | |||
184 | if (This.startswith_lower(Str)) | |||
185 | return From; | |||
186 | This = This.drop_front(); | |||
187 | ++From; | |||
188 | } | |||
189 | return npos; | |||
190 | } | |||
191 | ||||
192 | size_t StringRef::rfind_lower(char C, size_t From) const { | |||
193 | From = std::min(From, Length); | |||
194 | size_t i = From; | |||
195 | while (i != 0) { | |||
196 | --i; | |||
197 | if (toLower(Data[i]) == toLower(C)) | |||
198 | return i; | |||
199 | } | |||
200 | return npos; | |||
201 | } | |||
202 | ||||
203 | /// rfind - Search for the last string \arg Str in the string. | |||
204 | /// | |||
205 | /// \return - The index of the last occurrence of \arg Str, or npos if not | |||
206 | /// found. | |||
207 | size_t StringRef::rfind(StringRef Str) const { | |||
208 | size_t N = Str.size(); | |||
209 | if (N > Length) | |||
210 | return npos; | |||
211 | for (size_t i = Length - N + 1, e = 0; i != e;) { | |||
212 | --i; | |||
213 | if (substr(i, N).equals(Str)) | |||
214 | return i; | |||
215 | } | |||
216 | return npos; | |||
217 | } | |||
218 | ||||
219 | size_t StringRef::rfind_lower(StringRef Str) const { | |||
220 | size_t N = Str.size(); | |||
221 | if (N > Length) | |||
222 | return npos; | |||
223 | for (size_t i = Length - N + 1, e = 0; i != e;) { | |||
224 | --i; | |||
225 | if (substr(i, N).equals_lower(Str)) | |||
226 | return i; | |||
227 | } | |||
228 | return npos; | |||
229 | } | |||
230 | ||||
231 | /// find_first_of - Find the first character in the string that is in \arg | |||
232 | /// Chars, or npos if not found. | |||
233 | /// | |||
234 | /// Note: O(size() + Chars.size()) | |||
235 | StringRef::size_type StringRef::find_first_of(StringRef Chars, | |||
236 | size_t From) const { | |||
237 | std::bitset<1 << CHAR_BIT8> CharBits; | |||
238 | for (size_type i = 0; i != Chars.size(); ++i) | |||
239 | CharBits.set((unsigned char)Chars[i]); | |||
240 | ||||
241 | for (size_type i = std::min(From, Length), e = Length; i != e; ++i) | |||
242 | if (CharBits.test((unsigned char)Data[i])) | |||
243 | return i; | |||
244 | return npos; | |||
245 | } | |||
246 | ||||
247 | /// find_first_not_of - Find the first character in the string that is not | |||
248 | /// \arg C or npos if not found. | |||
249 | StringRef::size_type StringRef::find_first_not_of(char C, size_t From) const { | |||
250 | for (size_type i = std::min(From, Length), e = Length; i != e; ++i) | |||
251 | if (Data[i] != C) | |||
252 | return i; | |||
253 | return npos; | |||
254 | } | |||
255 | ||||
256 | /// find_first_not_of - Find the first character in the string that is not | |||
257 | /// in the string \arg Chars, or npos if not found. | |||
258 | /// | |||
259 | /// Note: O(size() + Chars.size()) | |||
260 | StringRef::size_type StringRef::find_first_not_of(StringRef Chars, | |||
261 | size_t From) const { | |||
262 | std::bitset<1 << CHAR_BIT8> CharBits; | |||
263 | for (size_type i = 0; i != Chars.size(); ++i) | |||
264 | CharBits.set((unsigned char)Chars[i]); | |||
265 | ||||
266 | for (size_type i = std::min(From, Length), e = Length; i != e; ++i) | |||
267 | if (!CharBits.test((unsigned char)Data[i])) | |||
268 | return i; | |||
269 | return npos; | |||
270 | } | |||
271 | ||||
272 | /// find_last_of - Find the last character in the string that is in \arg C, | |||
273 | /// or npos if not found. | |||
274 | /// | |||
275 | /// Note: O(size() + Chars.size()) | |||
276 | StringRef::size_type StringRef::find_last_of(StringRef Chars, | |||
277 | size_t From) const { | |||
278 | std::bitset<1 << CHAR_BIT8> CharBits; | |||
279 | for (size_type i = 0; i != Chars.size(); ++i) | |||
280 | CharBits.set((unsigned char)Chars[i]); | |||
281 | ||||
282 | for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) | |||
283 | if (CharBits.test((unsigned char)Data[i])) | |||
284 | return i; | |||
285 | return npos; | |||
286 | } | |||
287 | ||||
288 | /// find_last_not_of - Find the last character in the string that is not | |||
289 | /// \arg C, or npos if not found. | |||
290 | StringRef::size_type StringRef::find_last_not_of(char C, size_t From) const { | |||
291 | for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) | |||
292 | if (Data[i] != C) | |||
293 | return i; | |||
294 | return npos; | |||
295 | } | |||
296 | ||||
297 | /// find_last_not_of - Find the last character in the string that is not in | |||
298 | /// \arg Chars, or npos if not found. | |||
299 | /// | |||
300 | /// Note: O(size() + Chars.size()) | |||
301 | StringRef::size_type StringRef::find_last_not_of(StringRef Chars, | |||
302 | size_t From) const { | |||
303 | std::bitset<1 << CHAR_BIT8> CharBits; | |||
304 | for (size_type i = 0, e = Chars.size(); i != e; ++i) | |||
305 | CharBits.set((unsigned char)Chars[i]); | |||
306 | ||||
307 | for (size_type i = std::min(From, Length) - 1, e = -1; i != e; --i) | |||
308 | if (!CharBits.test((unsigned char)Data[i])) | |||
309 | return i; | |||
310 | return npos; | |||
311 | } | |||
312 | ||||
313 | void StringRef::split(SmallVectorImpl<StringRef> &A, | |||
314 | StringRef Separator, int MaxSplit, | |||
315 | bool KeepEmpty) const { | |||
316 | StringRef S = *this; | |||
317 | ||||
318 | // Count down from MaxSplit. When MaxSplit is -1, this will just split | |||
319 | // "forever". This doesn't support splitting more than 2^31 times | |||
320 | // intentionally; if we ever want that we can make MaxSplit a 64-bit integer | |||
321 | // but that seems unlikely to be useful. | |||
322 | while (MaxSplit-- != 0) { | |||
323 | size_t Idx = S.find(Separator); | |||
324 | if (Idx == npos) | |||
325 | break; | |||
326 | ||||
327 | // Push this split. | |||
328 | if (KeepEmpty || Idx > 0) | |||
329 | A.push_back(S.slice(0, Idx)); | |||
330 | ||||
331 | // Jump forward. | |||
332 | S = S.slice(Idx + Separator.size(), npos); | |||
333 | } | |||
334 | ||||
335 | // Push the tail. | |||
336 | if (KeepEmpty || !S.empty()) | |||
337 | A.push_back(S); | |||
338 | } | |||
339 | ||||
340 | void StringRef::split(SmallVectorImpl<StringRef> &A, char Separator, | |||
341 | int MaxSplit, bool KeepEmpty) const { | |||
342 | StringRef S = *this; | |||
343 | ||||
344 | // Count down from MaxSplit. When MaxSplit is -1, this will just split | |||
345 | // "forever". This doesn't support splitting more than 2^31 times | |||
346 | // intentionally; if we ever want that we can make MaxSplit a 64-bit integer | |||
347 | // but that seems unlikely to be useful. | |||
348 | while (MaxSplit-- != 0) { | |||
349 | size_t Idx = S.find(Separator); | |||
350 | if (Idx == npos) | |||
351 | break; | |||
352 | ||||
353 | // Push this split. | |||
354 | if (KeepEmpty || Idx > 0) | |||
355 | A.push_back(S.slice(0, Idx)); | |||
356 | ||||
357 | // Jump forward. | |||
358 | S = S.slice(Idx + 1, npos); | |||
359 | } | |||
360 | ||||
361 | // Push the tail. | |||
362 | if (KeepEmpty || !S.empty()) | |||
363 | A.push_back(S); | |||
364 | } | |||
365 | ||||
366 | //===----------------------------------------------------------------------===// | |||
367 | // Helpful Algorithms | |||
368 | //===----------------------------------------------------------------------===// | |||
369 | ||||
370 | /// count - Return the number of non-overlapped occurrences of \arg Str in | |||
371 | /// the string. | |||
372 | size_t StringRef::count(StringRef Str) const { | |||
373 | size_t Count = 0; | |||
374 | size_t N = Str.size(); | |||
375 | if (N > Length) | |||
376 | return 0; | |||
377 | for (size_t i = 0, e = Length - N + 1; i != e; ++i) | |||
378 | if (substr(i, N).equals(Str)) | |||
379 | ++Count; | |||
380 | return Count; | |||
381 | } | |||
382 | ||||
383 | static unsigned GetAutoSenseRadix(StringRef &Str) { | |||
384 | if (Str.empty()) | |||
385 | return 10; | |||
386 | ||||
387 | if (Str.startswith("0x") || Str.startswith("0X")) { | |||
388 | Str = Str.substr(2); | |||
389 | return 16; | |||
390 | } | |||
391 | ||||
392 | if (Str.startswith("0b") || Str.startswith("0B")) { | |||
393 | Str = Str.substr(2); | |||
394 | return 2; | |||
395 | } | |||
396 | ||||
397 | if (Str.startswith("0o")) { | |||
398 | Str = Str.substr(2); | |||
399 | return 8; | |||
400 | } | |||
401 | ||||
402 | if (Str[0] == '0' && Str.size() > 1 && isDigit(Str[1])) { | |||
403 | Str = Str.substr(1); | |||
404 | return 8; | |||
405 | } | |||
406 | ||||
407 | return 10; | |||
408 | } | |||
409 | ||||
410 | bool llvm::consumeUnsignedInteger(StringRef &Str, unsigned Radix, | |||
411 | unsigned long long &Result) { | |||
412 | // Autosense radix if not specified. | |||
413 | if (Radix == 0) | |||
414 | Radix = GetAutoSenseRadix(Str); | |||
415 | ||||
416 | // Empty strings (after the radix autosense) are invalid. | |||
417 | if (Str.empty()) return true; | |||
418 | ||||
419 | // Parse all the bytes of the string given this radix. Watch for overflow. | |||
420 | StringRef Str2 = Str; | |||
421 | Result = 0; | |||
422 | while (!Str2.empty()) { | |||
423 | unsigned CharVal; | |||
424 | if (Str2[0] >= '0' && Str2[0] <= '9') | |||
425 | CharVal = Str2[0] - '0'; | |||
426 | else if (Str2[0] >= 'a' && Str2[0] <= 'z') | |||
427 | CharVal = Str2[0] - 'a' + 10; | |||
428 | else if (Str2[0] >= 'A' && Str2[0] <= 'Z') | |||
429 | CharVal = Str2[0] - 'A' + 10; | |||
430 | else | |||
431 | break; | |||
432 | ||||
433 | // If the parsed value is larger than the integer radix, we cannot | |||
434 | // consume any more characters. | |||
435 | if (CharVal >= Radix) | |||
436 | break; | |||
437 | ||||
438 | // Add in this character. | |||
439 | unsigned long long PrevResult = Result; | |||
440 | Result = Result * Radix + CharVal; | |||
441 | ||||
442 | // Check for overflow by shifting back and seeing if bits were lost. | |||
443 | if (Result / Radix < PrevResult) | |||
444 | return true; | |||
445 | ||||
446 | Str2 = Str2.substr(1); | |||
447 | } | |||
448 | ||||
449 | // We consider the operation a failure if no characters were consumed | |||
450 | // successfully. | |||
451 | if (Str.size() == Str2.size()) | |||
452 | return true; | |||
453 | ||||
454 | Str = Str2; | |||
455 | return false; | |||
456 | } | |||
457 | ||||
458 | bool llvm::consumeSignedInteger(StringRef &Str, unsigned Radix, | |||
459 | long long &Result) { | |||
460 | unsigned long long ULLVal; | |||
461 | ||||
462 | // Handle positive strings first. | |||
463 | if (Str.empty() || Str.front() != '-') { | |||
464 | if (consumeUnsignedInteger(Str, Radix, ULLVal) || | |||
465 | // Check for value so large it overflows a signed value. | |||
466 | (long long)ULLVal < 0) | |||
467 | return true; | |||
468 | Result = ULLVal; | |||
469 | return false; | |||
470 | } | |||
471 | ||||
472 | // Get the positive part of the value. | |||
473 | StringRef Str2 = Str.drop_front(1); | |||
474 | if (consumeUnsignedInteger(Str2, Radix, ULLVal) || | |||
475 | // Reject values so large they'd overflow as negative signed, but allow | |||
476 | // "-0". This negates the unsigned so that the negative isn't undefined | |||
477 | // on signed overflow. | |||
478 | (long long)-ULLVal > 0) | |||
479 | return true; | |||
480 | ||||
481 | Str = Str2; | |||
482 | Result = -ULLVal; | |||
483 | return false; | |||
484 | } | |||
485 | ||||
486 | /// GetAsUnsignedInteger - Workhorse method that converts a integer character | |||
487 | /// sequence of radix up to 36 to an unsigned long long value. | |||
488 | bool llvm::getAsUnsignedInteger(StringRef Str, unsigned Radix, | |||
489 | unsigned long long &Result) { | |||
490 | if (consumeUnsignedInteger(Str, Radix, Result)) | |||
491 | return true; | |||
492 | ||||
493 | // For getAsUnsignedInteger, we require the whole string to be consumed or | |||
494 | // else we consider it a failure. | |||
495 | return !Str.empty(); | |||
496 | } | |||
497 | ||||
498 | bool llvm::getAsSignedInteger(StringRef Str, unsigned Radix, | |||
499 | long long &Result) { | |||
500 | if (consumeSignedInteger(Str, Radix, Result)) | |||
501 | return true; | |||
502 | ||||
503 | // For getAsSignedInteger, we require the whole string to be consumed or else | |||
504 | // we consider it a failure. | |||
505 | return !Str.empty(); | |||
506 | } | |||
507 | ||||
508 | bool StringRef::getAsInteger(unsigned Radix, APInt &Result) const { | |||
509 | StringRef Str = *this; | |||
510 | ||||
511 | // Autosense radix if not specified. | |||
512 | if (Radix == 0) | |||
513 | Radix = GetAutoSenseRadix(Str); | |||
514 | ||||
515 | assert(Radix > 1 && Radix <= 36)((Radix > 1 && Radix <= 36) ? static_cast<void > (0) : __assert_fail ("Radix > 1 && Radix <= 36" , "/build/llvm-toolchain-snapshot-10~+201911111502510600c19528f1809/llvm/lib/Support/StringRef.cpp" , 515, __PRETTY_FUNCTION__)); | |||
516 | ||||
517 | // Empty strings (after the radix autosense) are invalid. | |||
518 | if (Str.empty()) return true; | |||
519 | ||||
520 | // Skip leading zeroes. This can be a significant improvement if | |||
521 | // it means we don't need > 64 bits. | |||
522 | while (!Str.empty() && Str.front() == '0') | |||
523 | Str = Str.substr(1); | |||
524 | ||||
525 | // If it was nothing but zeroes.... | |||
526 | if (Str.empty()) { | |||
527 | Result = APInt(64, 0); | |||
528 | return false; | |||
529 | } | |||
530 | ||||
531 | // (Over-)estimate the required number of bits. | |||
532 | unsigned Log2Radix = 0; | |||
533 | while ((1U << Log2Radix) < Radix) Log2Radix++; | |||
534 | bool IsPowerOf2Radix = ((1U << Log2Radix) == Radix); | |||
535 | ||||
536 | unsigned BitWidth = Log2Radix * Str.size(); | |||
537 | if (BitWidth < Result.getBitWidth()) | |||
538 | BitWidth = Result.getBitWidth(); // don't shrink the result | |||
539 | else if (BitWidth > Result.getBitWidth()) | |||
540 | Result = Result.zext(BitWidth); | |||
541 | ||||
542 | APInt RadixAP, CharAP; // unused unless !IsPowerOf2Radix | |||
543 | if (!IsPowerOf2Radix) { | |||
544 | // These must have the same bit-width as Result. | |||
545 | RadixAP = APInt(BitWidth, Radix); | |||
546 | CharAP = APInt(BitWidth, 0); | |||
547 | } | |||
548 | ||||
549 | // Parse all the bytes of the string given this radix. | |||
550 | Result = 0; | |||
551 | while (!Str.empty()) { | |||
552 | unsigned CharVal; | |||
553 | if (Str[0] >= '0' && Str[0] <= '9') | |||
554 | CharVal = Str[0]-'0'; | |||
555 | else if (Str[0] >= 'a' && Str[0] <= 'z') | |||
556 | CharVal = Str[0]-'a'+10; | |||
557 | else if (Str[0] >= 'A' && Str[0] <= 'Z') | |||
558 | CharVal = Str[0]-'A'+10; | |||
559 | else | |||
560 | return true; | |||
561 | ||||
562 | // If the parsed value is larger than the integer radix, the string is | |||
563 | // invalid. | |||
564 | if (CharVal >= Radix) | |||
565 | return true; | |||
566 | ||||
567 | // Add in this character. | |||
568 | if (IsPowerOf2Radix) { | |||
569 | Result <<= Log2Radix; | |||
570 | Result |= CharVal; | |||
571 | } else { | |||
572 | Result *= RadixAP; | |||
573 | CharAP = CharVal; | |||
574 | Result += CharAP; | |||
575 | } | |||
576 | ||||
577 | Str = Str.substr(1); | |||
578 | } | |||
579 | ||||
580 | return false; | |||
581 | } | |||
582 | ||||
583 | bool StringRef::getAsDouble(double &Result, bool AllowInexact) const { | |||
584 | APFloat F(0.0); | |||
585 | APFloat::opStatus Status = | |||
586 | F.convertFromString(*this, APFloat::rmNearestTiesToEven); | |||
587 | if (Status != APFloat::opOK) { | |||
588 | if (!AllowInexact || !(Status & APFloat::opInexact)) | |||
589 | return true; | |||
590 | } | |||
591 | ||||
592 | Result = F.convertToDouble(); | |||
593 | return false; | |||
594 | } | |||
595 | ||||
596 | // Implementation of StringRef hashing. | |||
597 | hash_code llvm::hash_value(StringRef S) { | |||
598 | return hash_combine_range(S.begin(), S.end()); | |||
599 | } |
1 | //===-- llvm/ADT/edit_distance.h - Array edit distance function --- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This file defines a Levenshtein distance function that works for any two | |||
10 | // sequences, with each element of each sequence being analogous to a character | |||
11 | // in a string. | |||
12 | // | |||
13 | //===----------------------------------------------------------------------===// | |||
14 | ||||
15 | #ifndef LLVM_ADT_EDIT_DISTANCE_H | |||
16 | #define LLVM_ADT_EDIT_DISTANCE_H | |||
17 | ||||
18 | #include "llvm/ADT/ArrayRef.h" | |||
19 | #include <algorithm> | |||
20 | #include <memory> | |||
21 | ||||
22 | namespace llvm { | |||
23 | ||||
24 | /// Determine the edit distance between two sequences. | |||
25 | /// | |||
26 | /// \param FromArray the first sequence to compare. | |||
27 | /// | |||
28 | /// \param ToArray the second sequence to compare. | |||
29 | /// | |||
30 | /// \param AllowReplacements whether to allow element replacements (change one | |||
31 | /// element into another) as a single operation, rather than as two operations | |||
32 | /// (an insertion and a removal). | |||
33 | /// | |||
34 | /// \param MaxEditDistance If non-zero, the maximum edit distance that this | |||
35 | /// routine is allowed to compute. If the edit distance will exceed that | |||
36 | /// maximum, returns \c MaxEditDistance+1. | |||
37 | /// | |||
38 | /// \returns the minimum number of element insertions, removals, or (if | |||
39 | /// \p AllowReplacements is \c true) replacements needed to transform one of | |||
40 | /// the given sequences into the other. If zero, the sequences are identical. | |||
41 | template<typename T> | |||
42 | unsigned ComputeEditDistance(ArrayRef<T> FromArray, ArrayRef<T> ToArray, | |||
43 | bool AllowReplacements = true, | |||
44 | unsigned MaxEditDistance = 0) { | |||
45 | // The algorithm implemented below is the "classic" | |||
46 | // dynamic-programming algorithm for computing the Levenshtein | |||
47 | // distance, which is described here: | |||
48 | // | |||
49 | // http://en.wikipedia.org/wiki/Levenshtein_distance | |||
50 | // | |||
51 | // Although the algorithm is typically described using an m x n | |||
52 | // array, only one row plus one element are used at a time, so this | |||
53 | // implementation just keeps one vector for the row. To update one entry, | |||
54 | // only the entries to the left, top, and top-left are needed. The left | |||
55 | // entry is in Row[x-1], the top entry is what's in Row[x] from the last | |||
56 | // iteration, and the top-left entry is stored in Previous. | |||
57 | typename ArrayRef<T>::size_type m = FromArray.size(); | |||
58 | typename ArrayRef<T>::size_type n = ToArray.size(); | |||
59 | ||||
60 | const unsigned SmallBufferSize = 64; | |||
61 | unsigned SmallBuffer[SmallBufferSize]; | |||
62 | std::unique_ptr<unsigned[]> Allocated; | |||
63 | unsigned *Row = SmallBuffer; | |||
64 | if (n + 1 > SmallBufferSize) { | |||
65 | Row = new unsigned[n + 1]; | |||
66 | Allocated.reset(Row); | |||
67 | } | |||
68 | ||||
69 | for (unsigned i = 1; i <= n; ++i) | |||
70 | Row[i] = i; | |||
71 | ||||
72 | for (typename ArrayRef<T>::size_type y = 1; y <= m; ++y) { | |||
73 | Row[0] = y; | |||
74 | unsigned BestThisRow = Row[0]; | |||
75 | ||||
76 | unsigned Previous = y - 1; | |||
77 | for (typename ArrayRef<T>::size_type x = 1; x <= n; ++x) { | |||
78 | int OldRow = Row[x]; | |||
79 | if (AllowReplacements) { | |||
80 | Row[x] = std::min( | |||
81 | Previous + (FromArray[y-1] == ToArray[x-1] ? 0u : 1u), | |||
82 | std::min(Row[x-1], Row[x])+1); | |||
83 | } | |||
84 | else { | |||
85 | if (FromArray[y-1] == ToArray[x-1]) Row[x] = Previous; | |||
86 | else Row[x] = std::min(Row[x-1], Row[x]) + 1; | |||
87 | } | |||
88 | Previous = OldRow; | |||
89 | BestThisRow = std::min(BestThisRow, Row[x]); | |||
90 | } | |||
91 | ||||
92 | if (MaxEditDistance && BestThisRow > MaxEditDistance) | |||
93 | return MaxEditDistance + 1; | |||
94 | } | |||
95 | ||||
96 | unsigned Result = Row[n]; | |||
| ||||
97 | return Result; | |||
98 | } | |||
99 | ||||
100 | } // End llvm namespace | |||
101 | ||||
102 | #endif |