extension/packages/mode-hints/hints.coffee

   1 ###
   2 # Copyright Anton Khodakivskiy 2012, 2013.
   3 # Copyright Simon Lydell 2013, 2014.
   4 #
   5 # This file is part of VimFx.
   6 #
   7 # VimFx is free software: you can redistribute it and/or modify
   8 # it under the terms of the GNU General Public License as published by
   9 # the Free Software Foundation, either version 3 of the License, or
  10 # (at your option) any later version.
  11 #
  12 # VimFx is distributed in the hope that it will be useful,
  13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 # GNU General Public License for more details.
  16 #
  17 # You should have received a copy of the GNU General Public License
  18 # along with VimFx.  If not, see <http://www.gnu.org/licenses/>.
  19 ###
  20
  21 utils                     = require 'utils'
  22 { getPref }               = require 'prefs'
  23 { Marker }                = require 'mode-hints/marker'
  24 { addHuffmanCodeWordsTo } = require 'mode-hints/huffman'
  25
  26 { interfaces: Ci } = Components
  27
  28 HTMLDocument = Ci.nsIDOMHTMLDocument
  29 XULDocument  = Ci.nsIDOMXULDocument
  30
  31 CONTAINER_ID  = 'VimFxHintMarkerContainer'
  32 Z_INDEX_START = 2147480001 # The highest `z-index` used in style.css plus one.
  33 # In theory, `z-index` can be infinitely large. In practice, Firefox uses a
  34 # 32-bit signed integer to store it, so the maximum value is 2147483647
  35 # (http://www.puidokas.com/max-z-index/). Youtube (insanely) uses 1999999999 for
  36 # its top bar. So by using 2147480001 as a base, we trump that value with lots
  37 # of margin, still leaving a few thousand values for markers, which should be
  38 # more than enough. Hopefully no sites are crazy enough to use even higher
  39 # values.
  40
  41
  42 removeHints = (document) ->
  43   document.getElementById(CONTAINER_ID)?.remove()
  44
  45
  46 injectHints = (window) ->
  47   { document } = window
  48
  49   { clientWidth, clientHeight } = document.documentElement
  50   viewport =
  51     left:    0
  52     top:     0
  53     right:   clientWidth
  54     bottom:  clientHeight
  55     width:   clientWidth
  56     height:  clientHeight
  57     scrollX: window.scrollX
  58     scrollY: window.scrollY
  59   markers = createMarkers(window, viewport)
  60
  61   return if markers.length == 0
  62
  63   for marker in markers
  64     marker.weight = marker.elementShape.area
  65
  66   # Each marker gets a unique `z-index`, so that it can be determined if a
  67   # marker overlaps another.  Put more important markers (higher weight) at the
  68   # end, so that they get higher `z-index`, in order not to be overlapped.
  69   markers.sort((a, b) -> a.weight - b.weight)
  70   for marker, index in markers
  71     marker.markerElement.style.setProperty('z-index', Z_INDEX_START + index,
  72                                            'important')
  73
  74   hintChars = utils.getHintChars()
  75   addHuffmanCodeWordsTo(markers, {alphabet: hintChars},
  76                         (marker, hint) -> marker.setHint(hint))
  77
  78   removeHints(document)
  79   container = utils.createElement(document, 'div', {id: CONTAINER_ID})
  80   document.documentElement.appendChild(container)
  81
  82   for marker in markers
  83     container.appendChild(marker.markerElement)
  84     # Must be done after the hints have been inserted into the DOM (see
  85     # marker.coffee).
  86     marker.setPosition(viewport)
  87
  88   return markers
  89
  90
  91 createMarkers = (window, viewport, parents = []) ->
  92   { document } = window
  93   markers = []
  94
  95   # For now we aren't able to handle hint markers in XUL Documents :(
  96   return [] unless document instanceof HTMLDocument # or document instanceof XULDocument
  97
  98   candidates = utils.getMarkableElements(document, {type: 'all'})
  99   for element in candidates
 100     shape = getElementShape(window, element, viewport, parents)
 101     # If `element` has no visible shape then it shouldn’t get any marker.
 102     continue unless shape
 103
 104     markers.push(new Marker(element, shape))
 105
 106   for frame in window.frames
 107     rect = frame.frameElement.getBoundingClientRect() # Frames only have one.
 108     continue unless isInsideViewport(rect, viewport)
 109
 110     # Calculate the visible part of the frame, according to the parent.
 111     { clientWidth, clientHeight } = frame.document.documentElement
 112     frameViewport =
 113       left:   Math.max(viewport.left - rect.left, 0)
 114       top:    Math.max(viewport.top  - rect.top,  0)
 115       right:  clientWidth  + Math.min(viewport.right  - rect.right,  0)
 116       bottom: clientHeight + Math.min(viewport.bottom - rect.bottom, 0)
 117
 118     computedStyle = window.getComputedStyle(frame.frameElement)
 119     offset =
 120       left: rect.left +
 121         parseFloat(computedStyle.getPropertyValue('border-left-width')) +
 122         parseFloat(computedStyle.getPropertyValue('padding-left'))
 123       top: rect.top +
 124         parseFloat(computedStyle.getPropertyValue('border-top-width')) +
 125         parseFloat(computedStyle.getPropertyValue('padding-top'))
 126
 127     frameMarkers = createMarkers(frame, frameViewport,
 128                                  parents.concat({ window, offset }))
 129     markers.push(frameMarkers...)
 130
 131   return markers
 132
 133 # Returns the “shape” of `element`:
 134 #
 135 # - `rects`: Its `.getClientRects()` rectangles.
 136 # - `visibleRects`: The parts of rectangles out of the above that are inside
 137 #   `viewport`.
 138 # - `nonCoveredPoint`: The coordinates of the first point of `element` that
 139 #   isn’t covered by another element (except children of `element`). It also
 140 #   contains the offset needed to make those coordinates relative to the top
 141 #   frame, as well as the rectangle that the coordinates occur in.
 142 # - `area`: The area of the part of `element` that is inside `viewport`.
 143 #
 144 # Returns `null` if `element` is outside `viewport` or entirely covered by other
 145 # elements.
 146 getElementShape = (window, element, viewport, parents) ->
 147   # `element.getClientRects()` returns a list of rectangles, usually just one,
 148   # which is identical to the one returned by `element.getBoundingClientRect()`.
 149   # However, if `element` is inline and line-wrapped, then it returns one
 150   # rectangle for each line, since each line may be of different length, for
 151   # example. That allows us to properly add hints to line-wrapped links.
 152   rects = element.getClientRects()
 153   totalArea = 0
 154   visibleRects = []
 155   for rect in rects when isInsideViewport(rect, viewport)
 156     visibleRect = adjustRectToViewport(rect, viewport)
 157     continue if visibleRect.area == 0
 158     totalArea += visibleRect.area
 159     visibleRects.push(visibleRect)
 160
 161   if visibleRects.length == 0
 162     if rects.length == 1 and totalArea == 0
 163       [ rect ] = rects
 164       if rect.width > 0 or rect.height > 0
 165         # If we get here, it means that everything inside `element` is floated
 166         # and/or absolutely positioned (and that `element` hasn’t been made to
 167         # “contain” the floats). For example, a link in a menu could contain a
 168         # span of text floated to the left and an icon floated to the right.
 169         # Those are still clickable. Therefore we return the shape of the first
 170         # visible child instead. At least in that example, that’s the best bet.
 171         for child in element.children
 172           shape = getElementShape(window, child, viewport, parents)
 173           return shape if shape
 174     return null
 175
 176
 177   # Even if `element` has a visible rect, it might be covered by other elements.
 178   for visibleRect in visibleRects
 179     nonCoveredPoint = getFirstNonCoveredPoint(window, viewport, element,
 180                                               visibleRect, parents)
 181     if nonCoveredPoint
 182       nonCoveredPoint.rect = visibleRect
 183       break
 184
 185   return null unless nonCoveredPoint
 186
 187   return {
 188     rects, visibleRects, nonCoveredPoint, area: totalArea
 189   }
 190
 191
 192 MINIMUM_EDGE_DISTANCE = 4
 193 isInsideViewport = (rect, viewport) ->
 194   return \
 195     rect.left   <= viewport.right  - MINIMUM_EDGE_DISTANCE and
 196     rect.top    <= viewport.bottom + MINIMUM_EDGE_DISTANCE and
 197     rect.right  >= viewport.left   + MINIMUM_EDGE_DISTANCE and
 198     rect.bottom >= viewport.top    - MINIMUM_EDGE_DISTANCE
 199
 200
 201 adjustRectToViewport = (rect, viewport) ->
 202   # The right and bottom values are subtracted by 1 because
 203   # `document.elementFromPoint(right, bottom)` does not return the element
 204   # otherwise.
 205   left   = Math.max(rect.left,       viewport.left)
 206   right  = Math.min(rect.right - 1,  viewport.right)
 207   top    = Math.max(rect.top,        viewport.top)
 208   bottom = Math.min(rect.bottom - 1, viewport.bottom)
 209
 210   # Make sure that `right >= left and bottom >= top`, since we subtracted by 1
 211   # above.
 212   right  = Math.max(right, left)
 213   bottom = Math.max(bottom, top)
 214
 215   width  = right - left
 216   height = bottom - top
 217   area   = Math.floor(width * height)
 218
 219   return {
 220     left, right, top, bottom
 221     height, width, area
 222   }
 223
 224
 225 getFirstNonCoveredPoint = (window, viewport, element, elementRect, parents) ->
 226   # Before we start we need to hack around a little problem. If `element` has
 227   # `border-radius`, the corners won’t really belong to `element`, so
 228   # `document.elementFromPoint()` will return whatever is behind. This will
 229   # result in missing or out-of-place markers. The solution is to temporarily
 230   # add a CSS class that removes `border-radius`.
 231   element.classList.add('VimFxNoBorderRadius')
 232
 233   # Tries a point `(x + dx, y + dy)`. Returns `(x, y)` (and the frame offset)
 234   # if it passes the tests. Otherwise it tries to the right of whatever is at
 235   # `(x, y)`, `tryRight` times . If nothing succeeds, `false` is returned. `dx`
 236   # and `dy` are used to offset the wanted point `(x, y)` while trying (see the
 237   # invocations of `tryPoint` below).
 238   tryPoint = (x, dx, y, dy, tryRight = 0) ->
 239     elementAtPoint = window.document.elementFromPoint(x + dx, y + dy)
 240     offset = {left: 0, top: 0}
 241     found = false
 242
 243     # Ensure that `element`, or a child of `element` (anything inside an `<a>`
 244     # is clickable too), really is present at (x,y). Note that this is not 100%
 245     # bullet proof: Combinations of CSS can cause this check to fail, even
 246     # though `element` isn’t covered. We don’t try to temporarily reset such CSS
 247     # (as with `border-radius`) because of performance. Instead we rely on that
 248     # some of the attempts below will work.
 249     if element.contains(elementAtPoint) # Note that `a.contains(a) == true`!
 250       found = true
 251       # If we’re currently in a frame, there might be something on top of the
 252       # frame that covers `element`. Therefore we ensure that the frame really
 253       # is present at the point for each parent in `parents`.
 254       currentWindow = window
 255       for parent in parents by -1
 256         offset.left += parent.offset.left
 257         offset.top  += parent.offset.top
 258         elementAtPoint = parent.window.document.elementFromPoint(
 259           offset.left + x + dx, offset.top + y + dy
 260         )
 261         unless elementAtPoint == currentWindow.frameElement
 262           found = false
 263           break
 264         currentWindow = parent.window
 265
 266     if found
 267       return {x, y, offset}
 268     else
 269       return false if elementAtPoint == null or tryRight == 0
 270       rect = elementAtPoint.getBoundingClientRect()
 271       x = rect.right - offset.left + 1
 272       return false if x > viewport.right
 273       return tryPoint(x, 0, y, 0, tryRight - 1)
 274
 275
 276   # Try the following 3 positions, or immediately to the right of a covering
 277   # element at one of those positions, in order. If all of those are covered the
 278   # whole element is considered to be covered. The reasoning is:
 279   #
 280   # - A marker should show up as near the left edge of its visible area as
 281   #   possible. Having it appear to the far right (for example) is confusing.
 282   # - We can’t try too many times because of performance.
 283   #
 284   # +-------------------------------+
 285   # |1 left-top                     |
 286   # |                               |
 287   # |2 left-middle                  |
 288   # |                               |
 289   # |3 left-bottom                  |
 290   # +-------------------------------+
 291   #
 292   # It is safer to try points at least one pixel into the element from the
 293   # edges, hence the `+1`s and `-1`s.
 294   { left, top, bottom, height } = elementRect
 295   nonCoveredPoint =
 296     tryPoint(left, +1, top,              +1, 1) or
 297     tryPoint(left, +1, top + height / 2,  0, 1) or
 298     tryPoint(left, +1, bottom,           -1, 1)
 299
 300   element.classList.remove('VimFxNoBorderRadius')
 301
 302   return nonCoveredPoint
 303
 304
 305 # Finds all stacks of markers that overlap each other (by using `getStackFor`)
 306 # (#1), and rotates their `z-index`:es (#2), thus alternating which markers are
 307 # visible.
 308 rotateOverlappingMarkers = (originalMarkers, forward) ->
 309   # Shallow working copy. This is necessary since `markers` will be mutated and
 310   # eventually empty.
 311   markers = originalMarkers[..]
 312
 313   # (#1)
 314   stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
 315
 316   # (#2)
 317   # Stacks of length 1 don't participate in any overlapping, and can therefore
 318   # be skipped.
 319   for stack in stacks when stack.length > 1
 320     # This sort is not required, but makes the rotation more predictable.
 321     stack.sort((a, b) -> a.markerElement.style.zIndex -
 322                          b.markerElement.style.zIndex)
 323
 324     # Array of z-indices.
 325     indexStack = (marker.markerElement.style.zIndex for marker in stack)
 326     # Shift the array of indices one item forward or back.
 327     if forward
 328       indexStack.unshift(indexStack.pop())
 329     else
 330       indexStack.push(indexStack.shift())
 331
 332     for marker, index in stack
 333       marker.markerElement.style.setProperty('z-index', indexStack[index],
 334                                              'important')
 335
 336   return
 337
 338 # Get an array containing `marker` and all markers that overlap `marker`, if
 339 # any, which is called a "stack". All markers in the returned stack are spliced
 340 # out from `markers`, thus mutating it.
 341 getStackFor = (marker, markers) ->
 342   stack = [marker]
 343
 344   { top, bottom, left, right } = marker.position
 345
 346   index = 0
 347   while index < markers.length
 348     nextMarker = markers[index]
 349
 350     next = nextMarker.position
 351     overlapsVertically   = (next.bottom >= top  and next.top  <= bottom)
 352     overlapsHorizontally = (next.right  >= left and next.left <= right)
 353
 354     if overlapsVertically and overlapsHorizontally
 355       # Also get all markers overlapping this one.
 356       markers.splice(index, 1)
 357       stack = stack.concat(getStackFor(nextMarker, markers))
 358     else
 359       # Continue the search.
 360       index++
 361
 362   return stack
 363
 364
 365 exports.injectHints              = injectHints
 366 exports.removeHints              = removeHints
 367 exports.rotateOverlappingMarkers = rotateOverlappingMarkers