From a1194775dc3bc3c9471e089797ca08fdbe773794 Mon Sep 17 00:00:00 2001 From: Douglas Gregor Date: Tue, 19 Oct 2010 22:14:33 +0000 Subject: [PATCH] Provide an upper bound to the edit-distance algorithm when performing typo correction, to allow early exits. git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@116868 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Sema/SemaLookup.cpp | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/lib/Sema/SemaLookup.cpp b/lib/Sema/SemaLookup.cpp index de581fc6c6..060274e0d8 100644 --- a/lib/Sema/SemaLookup.cpp +++ b/lib/Sema/SemaLookup.cpp @@ -2730,16 +2730,22 @@ void TypoCorrectionConsumer::FoundDecl(NamedDecl *ND, NamedDecl *Hiding, } 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; -- 2.40.0