vim/ycm: replace broken levenshtein with working difflib SequenceMatcher

[dotfiles.git] / vim / ycm_extra_conf.py

diff --git a/vim/ycm_extra_conf.py b/vim/ycm_extra_conf.py
index deeac5ee9b1d153070041042e6921a3b6c85247d..2bd7b4ea0e697377c06df568b7f447c233c77300 100644 (file)
--- a/vim/ycm_extra_conf.py
+++ b/vim/ycm_extra_conf.py
@@ -7,6 +7,7 @@ import os.path
 from glob import glob
 import logging
 import ycm_core
+import difflib
 
 BASE_FLAGS = [
     '-Wall',
@@ -45,26 +46,9 @@ HEADER_EXTENSIONS = [
 ]
 
 
-# Implementation taken from
-# https://en.wikibooks.org/wiki/Algorithm_Implementation/Strings/Levenshtein_distance#Python
-def levenshtein(s, t):
-    ''' From Wikipedia article; Iterative with two matrix rows. '''
-    if s == t: return 0
-    elif len(s) == 0: return len(t)
-    elif len(t) == 0: return len(s)
-    v0 = [None] * (len(t) + 1)
-    v1 = [None] * (len(t) + 1)
-    for i in range(len(v0)):
-        v0[i] = i
-    for i in range(len(s)):
-        v1[0] = i + 1
-        for j in range(len(t)):
-            cost = 0 if s[i] == t[j] else 1
-            v1[j + 1] = min(v1[j] + 1, v0[j + 1] + 1, v0[j] + cost)
-        for j in range(len(v0)):
-            v0[j] = v1[j]
-
-        return v1[len(t)]
+def similarity_ratio(s, t):
+    return difflib.SequenceMatcher(a=s.lower(), b=t.lower()).ratio()
+
 
 def generate_qt_flags():
     flags = ['-isystem', '/usr/include/qt/']
@@ -78,14 +62,14 @@ def find_similar_file_in_database(dbpath, filename):
     logging.info("Trying to find some file close to: " + filename)
     db = json.load(open(dbpath))
     best_filename = ''
-    best_distance = 1 << 31
+    best_ratio = 0
     for entry in db:
-        entry_filename = os.path.normpath(
-            os.path.join(entry["directory"], entry["file"]))
-        distance = levenshtein(str(filename), str(entry_filename))
-        if distance < best_distance:
+        entry_filename = os.path.normpath(os.path.join(entry["directory"],
+                                                       entry["file"]))
+        ratio = similarity_ratio(str(filename), str(entry_filename))
+        if ratio > best_ratio:
             best_filename = entry_filename
-            best_distance = distance
+            best_ratio = ratio
     return best_filename
 
 def ok_compilation_info(info):