Bug Summary

File:include/llvm/ADT/edit_distance.h
Warning:line 96, column 3
Assigned value is garbage or undefined

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name StringRef.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -momit-leaf-frame-pointer -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-9/lib/clang/9.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Support -I /build/llvm-toolchain-snapshot-9~svn362543/lib/Support -I /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/include -I /build/llvm-toolchain-snapshot-9~svn362543/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/include/clang/9.0.0/include/ -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-9/lib/clang/9.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++11 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-9~svn362543/build-llvm/lib/Support -fdebug-prefix-map=/build/llvm-toolchain-snapshot-9~svn362543=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -o /tmp/scan-build-2019-06-05-060531-1271-1 -x c++ /build/llvm-toolchain-snapshot-9~svn362543/lib/Support/StringRef.cpp -faddrsig

/build/llvm-toolchain-snapshot-9~svn362543/lib/Support/StringRef.cpp

→
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
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
24// strncasecmp() is not available on non-POSIX systems, so define an
25// alternative function here.
26static 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.
37int 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.
46bool 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.
52bool StringRef::endswith_lower(StringRef Suffix) const {
53 return Length >= Suffix.Length &&
54 ascii_strncasecmp(end() - Suffix.Length, Suffix.Data, Suffix.Length) == 0;
55}
56
57size_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.
63int 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.
94unsigned StringRef::edit_distance(llvm::StringRef Other,
95 bool AllowReplacements,
96 unsigned MaxEditDistance) const {
97 return llvm::ComputeEditDistance(
1
Calling 'ComputeEditDistance<char>'
→
98 makeArrayRef(data(), size()),
99 makeArrayRef(Other.data(), Other.size()),
100 AllowReplacements, MaxEditDistance);
101}
102
103//===----------------------------------------------------------------------===//
104// String Operations
105//===----------------------------------------------------------------------===//
106
107std::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
115std::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.
132size_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
181size_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
192size_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.
207size_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
219size_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())
235StringRef::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.
249StringRef::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())
260StringRef::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())
276StringRef::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.
290StringRef::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())
301StringRef::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
313void 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
340void 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.
372size_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
383static 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
410bool 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
458bool 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.
488bool 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
498bool 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
508bool 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-9~svn362543/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
583bool 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.
597hash_code llvm::hash_value(StringRef S) {
598 return hash_combine_range(S.begin(), S.end());
599}
←

/build/llvm-toolchain-snapshot-9~svn362543/include/llvm/ADT/edit_distance.h

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
22namespace 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.
41template<typename T>
42unsigned 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) {
2
←
Assuming the condition is false
→
3
←
Taking false branch
→
65 Row = new unsigned[n + 1];
66 Allocated.reset(Row);
67 }
68
69 for (unsigned i = 1; i <= n; ++i)
4
←
Assuming 'i' is > 'n'
→
5
←
Loop condition is false. Execution continues on line 72
→
70 Row[i] = i;
71
72 for (typename ArrayRef<T>::size_type y = 1; y <= m; ++y) {
6
←
Assuming 'y' is > 'm'
→
7
←
Loop condition is false. Execution continues on line 96
→
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];
8
←
Assigned value is garbage or undefined
97 return Result;
98}
99
100} // End llvm namespace
101
102#endif