Provide an upper bound to the edit-distance algorithm when performing

typo correction, to allow early exits.

llvm-svn: 116868

1 files changed, 7 insertions, 1 deletions

diff --git a/clang/lib/Sema/SemaLookup.cpp b/clang/lib/Sema/SemaLookup.cpp
index de581fc6c60..060274e0d8a 100644
--- a/clang/lib/Sema/SemaLookup.cpp
+++ b/clang/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;