From 1fca4a033f276ae122ce70c35d68e183edf33bfc Mon Sep 17 00:00:00 2001
From: Samir Benmendil <samir.benmendil@ultrahaptics.com>
Date: Wed, 5 Jul 2017 11:27:14 +0100
Subject: [PATCH] vim/ycm: replace broken levenshtein with working difflib
 SequenceMatcher

---
 vim/ycm_extra_conf.py | 36 ++++++++++--------------------------
 1 file changed, 10 insertions(+), 26 deletions(-)

diff --git a/vim/ycm_extra_conf.py b/vim/ycm_extra_conf.py
index deeac5e..2bd7b4e 100644
--- 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):
-- 
2.48.1