prefer marking continguous characters

1 files changed, 49 insertions, 12 deletions

diff --git a/lib/completion.js b/lib/completion.js
index 446b9cab..67d8b219 100644
--- a/lib/completion.js
+++ b/lib/completion.js
@@ -20,6 +20,38 @@ var completion = (function() {
       return query.replace(self.regexNonWord, '').toLowerCase();
     }
 
+    /** Returns the non-matching and matching string parts, in alternating order (starting with a
+     * non-matching part) or null, if the string doesn't match the query.
+     *
+     * Sample: match("codecodec","code.google.com/codec") would yield ["", "code", ".google.com/", "codec"]
+     *
+     * Note that this function matches the longest possible parts of a string and is therefore not very
+     * efficient. _Don't use this to check if a string matches a query_. Use `getMatcher(query).test(str)`
+     * instead.
+     */
+    self.match = function(query, str) {
+      query = self.normalize(query);
+      if (query.length == 0)
+        return str.length ? [str] : [];
+
+      for (var i = query.length; i >= 1; --i) {
+        var part = query.slice(0, i);
+        var partOffset = str.toLowerCase().indexOf(part);
+        if (partOffset < 0)
+          continue;
+
+        // we use recursive backtracking here, this is why it's slow.
+        rest = self.match(query.slice(i), str.slice(partOffset + i));
+        if (!rest) continue;
+
+        return [
+          str.slice(0, partOffset),
+          part,
+        ].concat(rest);
+      }
+      return null;
+    }
+
     /** Calculates a very simple similarity value between a :query and a :string. The current
       * implementation simply returns the cumulated length of query parts that are also found
       * in the string, raised to the power of 3.
@@ -155,30 +187,35 @@ var completion = (function() {
         // tags and reinsert them after the matching process
         var htmlTags = {};
         str = stripHtmlTags(str, htmlTags);
-        var match = fuzzyMatcher.getMatcher(query).exec(str);
+        var groups = fuzzyMatcher.match(query, str);
         var html = '';
-        var i = 0;
+        var htmlOffset = 0;
 
         // this helper function adds the HTML generated _for one single character_ to the HTML output
         // and reinserts HTML tags stripped before, if they were at this position
         function addToHtml(str) {
-          if (i in htmlTags)
-            html += htmlTags[i];
+          if (htmlOffset in htmlTags)
+            html += htmlTags[htmlOffset];
           html += str;
-          ++i;
+          ++htmlOffset;
+        }
+
+        function addCharsWithDecoration(str, before, after) {
+          before = before || '';
+          after = after || '';
+          for (var i = 0; i < str.length; ++i)
+            addToHtml(before + str[i] + after);
         }
 
         // iterate over the match groups. They are non-matched and matched string parts, in alternating order
-        for (var m = 1; m < match.length; ++m) {
-          if (m % 2 == 1)
+        for (var i = 0; i < groups.length; ++i) {
+          if (i % 2 == 0)
             // we have a non-matched part, it could have several characters. We need to insert them character
             // by character, so that addToHtml can keep track of the position in the original string
-            for (var j = 0; j < match[m].length; ++j)
-              addToHtml(match[m][j]);
+            addCharsWithDecoration(groups[i]);
           else
-            // we have a matched part, which consists of exactly one character. In addition to the character
-            // itself, we add some decorating HTML.
-            addToHtml('<span class="fuzzyMatch">' + match[m] + '</span>');
+            // we have a matched part. In addition to the characters themselves, we add some decorating HTML.
+            addCharsWithDecoration(groups[i], '<span class="fuzzyMatch">', '</span>');
         };
 
         // call it another time so that a tag at the very last position is reinserted