Make the sort used for filetered link hints stable.

JavaScript's sort function is not stable; this PR makes the sort used for filtered link hints stable.

There are two reasons for doing this:

- High-scoring hints are more likely to keep the same hint string as the user continues typing. (Currently, the hints assigned change based on the vaguaries of the non-stable sort.)

- For equal-scoring hints, we retain the visit-child-before-parent ordering (which is used to NOT match a parent's text if we have already matched that text in a child).

And, as a result of all of that, the UX is more predictable and hence better.

2 files changed, 22 insertions, 18 deletions

diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee
index 54c10284..18c608a5 100644
--- a/content_scripts/link_hints.coffee
+++ b/content_scripts/link_hints.coffee
@@ -126,18 +126,22 @@ class LinkHintsMode
   #
   # Creates a link marker for the given link.
   #
-  createMarkerFor: (link) ->
-    marker = DomUtils.createElement "div"
-    marker.className = "vimiumReset internalVimiumHintMarker vimiumHintMarker"
-    marker.clickableItem = link.element
+  createMarkerFor: do ->
+    # This count is used to rank equal-scoring hints when sorting, thereby making JavaScript's sort stable.
+    stableSortCount = 0
+    (link) ->
+      marker = DomUtils.createElement "div"
+      marker.className = "vimiumReset internalVimiumHintMarker vimiumHintMarker"
+      marker.clickableItem = link.element
+      marker.stableSortCount = ++stableSortCount
 
-    clientRect = link.rect
-    marker.style.left = clientRect.left + window.scrollX + "px"
-    marker.style.top = clientRect.top  + window.scrollY  + "px"
+      clientRect = link.rect
+      marker.style.left = clientRect.left + window.scrollX + "px"
+      marker.style.top = clientRect.top  + window.scrollY  + "px"
 
-    marker.rect = link.rect
+      marker.rect = link.rect
 
-    marker
+      marker
 
   #
   # Determine whether the element is visible and clickable. If it is, find the rect bounding the element in
@@ -584,11 +588,8 @@ class FilterHints
     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
+    hintMarkers = hintMarkers[..].sort (a,b) ->
+      if b.score == a.score then b.stableSortCount - a.stableSortCount else b.score - a.score
 
     linkHintNumber = 1
     for linkMarker in hintMarkers
diff --git a/tests/dom_tests/dom_tests.coffee b/tests/dom_tests/dom_tests.coffee
index a79735ae..9d703774 100644
--- a/tests/dom_tests/dom_tests.coffee
+++ b/tests/dom_tests/dom_tests.coffee
@@ -185,18 +185,21 @@ context "Filtered link hints",
 
     should "label the hints", ->
       hintMarkers = getHintMarkers()
-      for i in [0...4]
-        assert.equal (i + 1).toString(), hintMarkers[i].textContent.toLowerCase()
+      expectedMarkers = [1..4].map (m) -> m.toString()
+      actualMarkers = [0...4].map (i) -> hintMarkers[i].textContent.toLowerCase()
+      assert.equal expectedMarkers.length, actualMarkers.length
+      for marker in expectedMarkers
+        assert.isTrue marker in actualMarkers
 
     should "narrow the hints", ->
       hintMarkers = getHintMarkers()
       sendKeyboardEvent "T"
       sendKeyboardEvent "R"
       assert.equal "none", hintMarkers[0].style.display
-      assert.equal "1", hintMarkers[1].hintString
+      assert.equal "3", hintMarkers[1].hintString
       assert.equal "", hintMarkers[1].style.display
       sendKeyboardEvent "A"
-      assert.equal "2", hintMarkers[3].hintString
+      assert.equal "1", hintMarkers[3].hintString
 
   context "Image hints",