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