Provide an upper bound to the edit-distance algorithm when performing
typo correction, to allow early exits.
llvm-svn: 116868
diff --git a/clang/lib/Sema/SemaLookup.cpp b/clang/lib/Sema/SemaLookup.cpp
index de581fc..060274e 100644
--- a/clang/lib/Sema/SemaLookup.cpp
+++ b/clang/lib/Sema/SemaLookup.cpp
@@ -2730,16 +2730,22 @@
}
void TypoCorrectionConsumer::FoundName(llvm::StringRef Name) {
+ using namespace std;
+
// Use a simple length-based heuristic to determine the minimum possible
// edit distance. If the minimum isn't good enough, bail out early.
unsigned MinED = abs((int)Name.size() - (int)Typo.size());
if (MinED > BestEditDistance || (MinED && Typo.size() / MinED < 3))
return;
+ // Compute an upper bound on the allowable edit distance, so that the
+ // edit-distance algorithm can short-circuit.
+ unsigned UpperBound = min(unsigned((Typo.size() + 2) / 3), BestEditDistance);
+
// Compute the edit distance between the typo and the name of this
// entity. If this edit distance is not worse than the best edit
// distance we've seen so far, add it to the list of results.
- unsigned ED = Typo.edit_distance(Name);
+ unsigned ED = Typo.edit_distance(Name, true, UpperBound);
if (ED == 0)
return;