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