Space rotates hints (to make hidden hints visible).

It is common for link-hint markers to be close togother, and
overlapping.

Here, `<Space>` rotates hint markers such that hidden markers become
visible.

For filtered hints we additionally require a modifier (because `<space>`
on its own is already a token separator).

The calculation of overlapping hints is quite expensive: O(n^2) in the
best case and O(n^3) in the worst cast.  The worst case is
extraordinarily unlikely to arise in practice.

2 files changed, 87 insertions, 30 deletions

diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee
index 2548abb3..77235ef5 100644
--- a/content_scripts/link_hints.coffee
+++ b/content_scripts/link_hints.coffee
@@ -110,6 +110,7 @@ HintCoordinator =
 
   # The following messages are exchanged between frames while link-hints mode is active.
   updateKeyState: (request) -> @linkHintsMode.updateKeyState request
+  rotateHints: -> @linkHintsMode.rotateHints()
   setOpenLinkMode: ({modeIndex}) -> @linkHintsMode.setOpenLinkMode availableModes[modeIndex], false
   activateActiveHintMarker: -> @linkHintsMode.activateLink @linkHintsMode.markerMatcher.activeHintMarker
   getLocalHintMarker: (hint) -> if hint.frameId == frameId then @localHints[hint.localIndex] else null
@@ -199,26 +200,32 @@ class LinkHintsMode
   #
   # Creates a link marker for the given link.
   #
-  createMarkerFor: (desc) ->
-    marker =
-      if desc.frameId == frameId
-        localHintDescriptor = HintCoordinator.getLocalHintMarker desc
-        el = DomUtils.createElement "div"
-        el.rect = localHintDescriptor.rect
-        el.style.left = el.rect.left + "px"
-        el.style.top = el.rect.top  + "px"
-        extend el,
-          className: "vimiumReset internalVimiumHintMarker vimiumHintMarker"
-          showLinkText: localHintDescriptor.showLinkText
-          localHintDescriptor: localHintDescriptor
-      else
-        {}
+  createMarkerFor: do ->
+    # This generates z-index values which are greater than all of the other z-index values used by Vimium.
+    baseZIndex = 2140000000
+
+    (desc) ->
+      marker =
+        if desc.frameId == frameId
+          localHintDescriptor = HintCoordinator.getLocalHintMarker desc
+          el = DomUtils.createElement "div"
+          el.rect = localHintDescriptor.rect
+          el.style.left = el.rect.left + "px"
+          el.style.top = el.rect.top  + "px"
+          # Each hint marker is assigned a different z-index.
+          el.style.zIndex = baseZIndex += 1
+          extend el,
+            className: "vimiumReset internalVimiumHintMarker vimiumHintMarker"
+            showLinkText: localHintDescriptor.showLinkText
+            localHintDescriptor: localHintDescriptor
+        else
+          {}
 
-    extend marker,
-      hintDescriptor: desc
-      isLocalMarker: desc.frameId == frameId
-      linkText: desc.linkText
-      stableSortCount: ++@stableSortCount
+      extend marker,
+        hintDescriptor: desc
+        isLocalMarker: desc.frameId == frameId
+        linkText: desc.linkText
+        stableSortCount: ++@stableSortCount
 
   # Handles <Shift> and <Ctrl>.
   onKeyDownInMode: (event) ->
@@ -274,6 +281,9 @@ class LinkHintsMode
       @tabCount = previousTabCount + (if event.shiftKey then -1 else 1)
       @updateVisibleMarkers @tabCount
 
+    else if event.keyCode == keyCodes.space and @markerMatcher.shouldRotateHints event
+      HintCoordinator.sendMessage "rotateHints"
+
     else
       return
 
@@ -310,6 +320,49 @@ class LinkHintsMode
 
     @setIndicator()
 
+  # Rotate the hints' z-index values so that hidden hints become visible.
+  rotateHints: do ->
+    markerOverlapsStack = (marker, stack) ->
+      for otherMarker in stack
+        return true if Rect.rectsOverlap marker.markerRect, otherMarker.markerRect
+      false
+
+    ->
+      # Get local, visible hint markers.
+      localHintMarkers = @hintMarkers.filter (marker) ->
+        marker.isLocalMarker and marker.style.display != "none"
+
+      # Fill in the markers' rects, if necessary.
+      marker.markerRect ?= marker.getClientRects()[0] for marker in localHintMarkers
+
+      # Calculate the overlapping groups of hints.  This is O(n^2) in the best case and O(n^3) in the worst
+      # case.
+      stacks = []
+      for marker in localHintMarkers
+        stackForThisMarker = null
+        stacks =
+          for stack in stacks
+            if markerOverlapsStack marker, stack
+              if stackForThisMarker?
+                # Merge stack into stackForThisMarker and discard stack.
+                stackForThisMarker.push stack...
+                continue
+              else
+                stack.push marker
+                stackForThisMarker = stack
+            else
+              stack
+        stacks.push [marker] unless stackForThisMarker?
+
+      # Rotate the z-indexes within each stack.
+      for stack in stacks
+        if 1 < stack.length
+          zIndexes = (marker.style.zIndex for marker in stack)
+          zIndexes.push zIndexes[0]
+          marker.style.zIndex = zIndexes[index + 1] for marker, index in stack
+
+      null # Prevent Coffeescript from building an unnecessary array.
+
   # When only one hint remains, activate it in the appropriate way.  The current frame may or may not contain
   # the matched link, and may or may not have the focus.  The resulting four cases are accounted for here by
   # selectively pushing the appropriate HintCoordinator.onExit handlers.
@@ -420,6 +473,9 @@ class AlphabetHints
     @hintKeystrokeQueue.push (if @useKeydown then keydownKeyChar else keyChar)
   popKeyChar: -> @hintKeystrokeQueue.pop()
 
+  # For alphabet hints, <Space> always rotates the hints, regardless of modifiers.
+  shouldRotateHints: -> true
+
 # Use numbers (usually) for hints, and also filter links by their text.
 class FilterHints
   constructor: ->
@@ -540,6 +596,10 @@ class FilterHints
         # them as if their length was 100 (so, quite long).
         score / Math.log 1 + (linkMarker.linkText.length || 100)
 
+  # For filtered hints, we require a modifier (because <Space> on its own is a token separator).
+  shouldRotateHints: (event) ->
+    event.ctrlKey or event.altKey or event.metaKey
+
 #
 # Make each hint character a span, so that we can highlight the typed characters as you type them.
 #
diff --git a/content_scripts/vimium.css b/content_scripts/vimium.css
index be9d4a65..edb1ab85 100644
--- a/content_scripts/vimium.css
+++ b/content_scripts/vimium.css
@@ -3,9 +3,9 @@
  * use the same CSS class names that the page is using, so the page's CSS doesn't mess with the style of our
  * Vimium dialogs.
  *
- * The z-indexes of Vimium elements are very large, because we always want them to show on top. Chrome may
- * support up to Number.MAX_VALUE, which is approximately 1.7976e+308. We're using 2^31, which is the max
- * value of a signed 32 bit int. Let's try larger values if 2**31 empirically isn't large enough.
+ * The z-indexes of Vimium elements are very large, because we always want them to show on top.  We know
+ * that Chrome supports z-index values up to about 2^31.  The values we use are large numbers approaching
+ * that bound.  However, we must leave headroom for link hints.  Hint marker z-indexes start at 2140000001.
  */
 
 /*
@@ -58,7 +58,7 @@ tr.vimiumReset {
   vertical-align: baseline;
   white-space: normal;
   width: auto;
-  z-index: 2147483648;
+  z-index: 2140000000; /* Vimium's reference z-index value. */
 }
 
 thead.vimiumReset, tbody.vimiumReset {
@@ -147,7 +147,7 @@ iframe.vimiumHelpDialogFrame {
   display: block;
   position: fixed;
   border: none;
-  z-index: 2147483645; /* One less than hint markers. */
+  z-index: 2139999997; /* Three less than the reference value. */
 }
 
 div#vimiumHelpDialogContainer {
@@ -335,8 +335,7 @@ iframe.vimiumHUDFrame {
   padding: 0px;
   margin: 0;
   border: none;
-  /* One less than vimium's hint markers, so link hints can be shown e.g. for the HUD panel's close button. */
-  z-index: 2147483646;
+  z-index: 2149999998; /* Two less than the reference value. */
   opacity: 0;
 }
 
@@ -377,9 +376,7 @@ iframe.vomnibarFrame {
   margin: 0 0 0 -40%;
   border: none;
   font-family: sans-serif;
-
-  /* One less than hint markers. */
-  z-index: 2147483646;
+  z-index: 2149999998; /* Two less than the reference value. */
 }
 
 div.vimiumFlash {
@@ -387,7 +384,7 @@ div.vimiumFlash {
   padding: 1px;
   background-color: transparent;
   position: absolute;
-  z-index: 2147483648;
+  z-index: 2140000000;
 }
 
 /* UIComponent CSS */