Merge pull request #1726 from smblott-github/rank-filter-hints

Rank filtered hints by score.

3 files changed, 60 insertions, 20 deletions

diff --git a/README.md b/README.md
index a3bf84bb..b2b865f1 100644
--- a/README.md
+++ b/README.md
@@ -163,7 +163,8 @@ Release Notes
 - Added <tt>\`\`</tt> to jump back to the previous position after selected jump-like movements: <br/>
     (`gg`, `G`, `n`, `N`, `/` and local mark movements).
 - Global marks are now persistent (across tab closes and browser sessions) and synced.
-- For filtered link hints (not the default), you can now use `Tab` to select hints.
+- For filtered link hints (not the default), you can now use `Tab` and `Enter`
+  to select hints and hints are ordered by best match.
 - Bug fixes, including:
     - Bookmarklets accessed from the Vomnibar.
     - Global marks on non-Windows platforms.
diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee
index 107a292e..15af15c5 100644
--- a/content_scripts/link_hints.coffee
+++ b/content_scripts/link_hints.coffee
@@ -478,7 +478,7 @@ class FilterHints
         @labelMap[forElement] = labelText
 
   generateHintString: (linkHintNumber) ->
-    numberToHintString linkHintNumber + 1, @linkHintNumbers.toUpperCase()
+    numberToHintString linkHintNumber, @linkHintNumbers.toUpperCase()
 
   generateLinkText: (element) ->
     linkText = ""
@@ -512,8 +512,7 @@ class FilterHints
   fillInMarkers: (hintMarkers) ->
     @generateLabelMap()
     DomUtils.textContent.reset()
-    for marker, idx in hintMarkers
-      marker.hintString = @generateHintString(idx)
+    for marker in hintMarkers
       linkTextObject = @generateLinkText(marker.clickableItem)
       marker.linkText = linkTextObject.text
       marker.showLinkText = linkTextObject.show
@@ -522,7 +521,9 @@ class FilterHints
     @activeHintMarker = hintMarkers[0]
     @activeHintMarker?.classList.add "vimiumActiveHintMarker"
 
-    hintMarkers
+    # We use @filterLinkHints() here (although we know that all of the hints will match) to fill in the hint
+    # strings.  This ensures that we always get hint strings in the same order.
+    @filterLinkHints hintMarkers
 
   getMatchingHints: (hintMarkers, tabCount = 0) ->
     delay = 0
@@ -563,15 +564,46 @@ class FilterHints
 
   # Filter link hints by search string, renumbering the hints as necessary.
   filterLinkHints: (hintMarkers) ->
-    idx = 0
-    linkSearchString = @linkTextKeystrokeQueue.join("").toLowerCase()
-
+    linkSearchString = @linkTextKeystrokeQueue.join("").trim().toLowerCase()
+    do (scoreFunction = @scoreLinkHint linkSearchString) ->
+      linkMarker.score = scoreFunction linkMarker for linkMarker in hintMarkers
+    # The Javascript sort() method is known not to be stable.  Nevertheless, we require (and assume, here)
+    # that it is deterministic.  So, if the user is typing hint characters, then hints will always end up in
+    # the same order and hence with the same hint strings (because hint-string filtering happens after the
+    # filtering here).
+    hintMarkers = hintMarkers[..].sort (a,b) -> b.score - a.score
+
+    linkHintNumber = 1
     for linkMarker in hintMarkers
-      continue unless 0 <= linkMarker.linkText.toLowerCase().indexOf linkSearchString
-      linkMarker.hintString = @generateHintString idx++
+      continue unless 0 < linkMarker.score
+      linkMarker.hintString = @generateHintString linkHintNumber++
       @renderMarker linkMarker
       linkMarker
 
+  # Assign a score to a filter match (higher is better).  We assign a higher score for matches at the start of
+  # a word, and a considerably higher score still for matches which are whole words.
+  scoreLinkHint: (linkSearchString) ->
+    searchWords = linkSearchString.trim().split /\s+/
+    (linkMarker) ->
+      linkWords = linkMarker.linkWords ?= linkMarker.linkText.trim().toLowerCase().split /\s+/
+
+      searchWordScores =
+        for searchWord in searchWords
+          linkWordScores =
+            for linkWord, idx in linkWords
+              if linkWord == searchWord
+                if idx == 0 then 8 else 6
+              else if linkWord.startsWith searchWord
+                if idx == 0 then 4 else 2
+              else if 0 <= linkWord.indexOf searchWord
+                1
+              else
+                0
+          Math.max linkWordScores...
+
+      addFunc = (a,b) -> a + b
+      if 0 in searchWordScores then 0 else searchWordScores.reduce addFunc, 0
+
 #
 # Make each hint character a span, so that we can highlight the typed characters as you type them.
 #
diff --git a/tests/dom_tests/dom_tests.coffee b/tests/dom_tests/dom_tests.coffee
index dd2f5a5d..a79735ae 100644
--- a/tests/dom_tests/dom_tests.coffee
+++ b/tests/dom_tests/dom_tests.coffee
@@ -212,11 +212,14 @@ context "Filtered link hints",
       @linkHints.deactivateMode()
 
     should "label the images", ->
-      hintMarkers = getHintMarkers()
-      assert.equal "1: alt text", hintMarkers[0].textContent.toLowerCase()
-      assert.equal "2: some title", hintMarkers[1].textContent.toLowerCase()
-      assert.equal "3: alt text", hintMarkers[2].textContent.toLowerCase()
-      assert.equal "4", hintMarkers[3].textContent.toLowerCase()
+      hintMarkers = getHintMarkers().map (marker) -> marker.textContent.toLowerCase()
+      # We don't know the actual hint numbers which will be assigned, so we replace them with "N".
+      hintMarkers = hintMarkers.map (str) -> str.replace /^[1-4]/, "N"
+      assert.equal 4, hintMarkers.length
+      assert.isTrue "N: alt text" in hintMarkers
+      assert.isTrue "N: some title" in hintMarkers
+      assert.isTrue "N: alt text" in hintMarkers
+      assert.isTrue "N" in hintMarkers
 
   context "Input hints",
 
@@ -235,11 +238,15 @@ context "Filtered link hints",
 
     should "label the input elements", ->
       hintMarkers = getHintMarkers()
-      assert.equal "1", hintMarkers[0].textContent.toLowerCase()
-      assert.equal "2", hintMarkers[1].textContent.toLowerCase()
-      assert.equal "3: a label", hintMarkers[2].textContent.toLowerCase()
-      assert.equal "4: a label", hintMarkers[3].textContent.toLowerCase()
-      assert.equal "5", hintMarkers[4].textContent.toLowerCase()
+      hintMarkers = getHintMarkers().map (marker) -> marker.textContent.toLowerCase()
+      # We don't know the actual hint numbers which will be assigned, so we replace them with "N".
+      hintMarkers = hintMarkers.map (str) -> str.replace /^[1-5]/, "N"
+      assert.equal 5, hintMarkers.length
+      assert.isTrue "N" in hintMarkers
+      assert.isTrue "N" in hintMarkers
+      assert.isTrue "N: a label" in hintMarkers
+      assert.isTrue "N: a label" in hintMarkers
+      assert.isTrue "N" in hintMarkers
 
 context "Input focus",