Add a manual implementation of the edit distance algorithm

We were using editdistance, which is super fast, but the downside is that
it might require a compiler on some envs in order to be installed. As such,
it is also a hindrance not just for these kind of envs, but for PyPy as well,
since it is written in C. Let's use a handcraft implementation
for now.
Close #1423

2 files changed, 20 insertions, 3 deletions

diff --git a/pylint/__pkginfo__.py b/pylint/__pkginfo__.py
index 4e0592f1a..0c955817a 100644
--- a/pylint/__pkginfo__.py
+++ b/pylint/__pkginfo__.py
@@ -26,7 +26,6 @@ install_requires = [
     'six',
     'isort >= 4.2.5',
     'mccabe',
-    'editdistance',
 ]
 
 dependency_links = []
diff --git a/pylint/checkers/typecheck.py b/pylint/checkers/typecheck.py
index ece6ebd76..8ae8f4467 100644
--- a/pylint/checkers/typecheck.py
+++ b/pylint/checkers/typecheck.py
@@ -25,7 +25,6 @@ import re
 import shlex
 import sys
 
-import editdistance
 import six
 
 import astroid
@@ -119,6 +118,25 @@ def _(node):
     return itertools.chain(values, other_values)
 
 
+def _string_distance(seq1, seq2):
+    seq2_length = len(seq2)
+
+    row = list(range(1, seq2_length + 1)) + [0]
+    for seq1_index, seq1_char in enumerate(seq1):
+        last_row = row
+        row = [0] * seq2_length + [seq1_index + 1]
+
+        for seq2_index, seq2_char in enumerate(seq2):
+            row[seq2_index] = min(
+                last_row[seq2_index] + 1,
+                row[seq2_index - 1] + 1,
+                last_row[seq2_index - 1] + (seq1_char != seq2_char)
+
+            )
+
+    return row[seq2_length - 1]
+
+
 def _similar_names(owner, attrname, distance_threshold, max_choices):
     """Given an owner and a name, try to find similar names
 
@@ -132,7 +150,7 @@ def _similar_names(owner, attrname, distance_threshold, max_choices):
         if name == attrname:
             continue
 
-        distance = editdistance.eval(attrname, name)
+        distance = _string_distance(attrname, name)
         if distance <= distance_threshold:
             possible_names.append((name, distance))