Remove overlapping rects from link hints

3 files changed, 91 insertions, 8 deletions

diff --git a/content_scripts/link_hints.coffee b/content_scripts/link_hints.coffee
index 4b039935..721070bb 100644
--- a/content_scripts/link_hints.coffee
+++ b/content_scripts/link_hints.coffee
@@ -173,7 +173,35 @@ LinkHints =
       if clientRect != null
         visibleElements.push {element: element, rect: clientRect}
 
-    visibleElements
+    # TODO(mrmr1993): Consider z-index. z-index affects behviour as follows:
+    #  * The document has a local stacking context.
+    #  * An element with z-index specified
+    #    - sets its z-order position in the containing stacking context, and
+    #    - creates a local stacking context containing its children.
+    #  * An element (1) is shown above another element (2) if either
+    #    - in the last stacking context which contains both an ancestor of (1) and an ancestor of (2), the
+    #      ancestor of (1) has a higher z-index than the ancestor of (2); or
+    #    - in the last stacking context which contains both an ancestor of (1) and an ancestor of (2),
+    #        + the ancestors of (1) and (2) have equal z-index, and
+    #        + the ancestor of (1) appears later in the DOM than the ancestor of (2).
+    #
+    # Remove rects from
+    nonOverlappingElements = []
+    visibleElements = visibleElements.reverse()
+    while visibleElement = visibleElements.pop()
+      rects = [visibleElement.rect]
+      for {rect: negativeRect} in visibleElements
+        rects = Array::concat.apply [], (rects.map (rect) -> Utils.subtractRect rect, negativeRect)
+      if rects.length > 0
+        nonOverlappingElements.push {element: visibleElement.element, rect: rects[0]}
+      else
+        # Every part of the element is covered by some other element, so just insert the whole element's
+        # rect.
+        # TODO(mrmr1993): This is probably the wrong thing to do, but we don't want to stop being able to
+        # click some elements that we could click before.
+        nonOverlappingElements.push visibleElement
+
+    nonOverlappingElements
 
   #
   # Handles shift and esc keys. The other keys are passed to getMarkerMatcher().matchHintsByKey.
diff --git a/lib/dom_utils.coffee b/lib/dom_utils.coffee
index aaa93923..7e19a7fc 100644
--- a/lib/dom_utils.coffee
+++ b/lib/dom_utils.coffee
@@ -114,13 +114,8 @@ DomUtils =
         # something more sophisticated, but likely not worth the effort.
         [x1, y1, x2, y2] = coords
 
-      rect = @cropRectToVisible
-        top: imgClientRect.top + y1
-        left: imgClientRect.left + x1
-        right: imgClientRect.left + x2
-        bottom: imgClientRect.top + y2
-        width: x2 - x1
-        height: y2 - y1
+      rect = Utils.shiftRect (Utils.createRect x1, y1, x2, y2), imgClientRect.left, imgClientRect.top
+      rect = @cropRectToVisible rect
 
       rects.push {element: area, rect: rect} unless not rect or isNaN rect.top
     rects
diff --git a/lib/utils.coffee b/lib/utils.coffee
index b7f8731a..6cc45f32 100644
--- a/lib/utils.coffee
+++ b/lib/utils.coffee
@@ -136,6 +136,66 @@ Utils =
   # locale-sensitive uppercase detection
   hasUpperCase: (s) -> s.toLowerCase() != s
 
+  # Create a rect given the top left and bottom right corners.
+  createRect: (x1, y1, x2, y2) ->
+    bottom: y2
+    top: y1
+    left: x1
+    right: x2
+    width: x2 - x1
+    height: y2 - y1
+
+  # Translate a rect by x horizontally and y vertically.
+  shiftRect: (rect, x, y) ->
+    bottom: rect.bottom + y
+    top: rect.top + y
+    left: rect.left + x
+    right: rect.right + x
+    width: rect.width
+    height: rect.height
+
+  # Subtract rect2 from rect1, returning an array of rects which are in rect1 but not rect2.
+  subtractRect: (rect1, rect2_) ->
+    # Bound rect2 by rect1
+    rect2 = {}
+    rect2 = @createRect(
+      Math.max(rect1.left, rect2_.left),
+      Math.max(rect1.top, rect2_.top),
+      Math.min(rect1.right, rect2_.right),
+      Math.min(rect1.bottom, rect2_.bottom)
+    )
+
+    # If bounding rect2 has made the width or height negative, rect1 does not contain rect2.
+    return [rect1] if rect2.width < 0 or rect2.height < 0
+
+    #
+    # All the possible rects, in the order
+    # +-+-+-+
+    # |1|2|3|
+    # +-+-+-+
+    # |4| |5|
+    # +-+-+-+
+    # |6|7|8|
+    # +-+-+-+
+    # where the outer rectangle is rect1 and the inner rectangle is rect 2. Note that the rects may be of
+    # width or height 0.
+    #
+    rects = [
+      # Top row.
+      @createRect rect1.left, rect1.top, rect2.left, rect2.top
+      @createRect rect2.left, rect1.top, rect2.right, rect2.top
+      @createRect rect2.right, rect1.top, rect1.right, rect2.top
+      # Middle row.
+      @createRect rect1.left, rect2.top, rect2.left, rect2.bottom
+      @createRect rect2.right, rect2.top, rect1.right, rect2.bottom
+      # Bottom row.
+      @createRect rect1.left, rect2.bottom, rect2.left, rect1.bottom
+      @createRect rect2.left, rect2.bottom, rect2.right, rect1.bottom
+      @createRect rect2.right, rect2.bottom, rect1.right, rect1.bottom
+    ]
+
+    rects.filter (rect) -> rect.height > 0 and rect.width > 0
+
 # This creates a new function out of an existing function, where the new function takes fewer arguments. This
 # allows us to pass around functions instead of functions + a partial list of arguments.
 Function::curry = ->