extension/lib/hints.coffee

   1 ###
   2 # Copyright Anton Khodakivskiy 2012, 2013.
   3 # Copyright Simon Lydell 2013, 2014, 2015.
   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 # This file contains functions for getting markable elements, and related data,
  22 # as well as for creating and inserting markers for markable elements.
  23
  24 huffman    = require('n-ary-huffman')
  25 { Marker } = require('./marker')
  26 utils      = require('./utils')
  27
  28 CONTAINER_ID = 'VimFxMarkersContainer'
  29
  30 Element     = Ci.nsIDOMElement
  31 XULDocument = Ci.nsIDOMXULDocument
  32
  33 # For some time we used to return the hints container from `injectHints`, and
  34 # use that reference to remove the hints when needed. That’s fine in theory, but
  35 # in case anything breaks we might loose that reference and end up with
  36 # unremovable hints on the screen. Explicitly looking for an element with the
  37 # container ID is more fail-safe.
  38 removeHints = (window) ->
  39   window.document.getElementById(CONTAINER_ID)?.remove()
  40
  41 # Create `Marker`s for every element (represented by a regular object of data
  42 # about the element—a “wrapper,” a stand-in for the real element, which is only
  43 # accessible in frame scripts) in `wrappers`, and insert them into `window`.
  44 injectHints = (window, wrappers, viewport, options) ->
  45   semantic   = []
  46   unsemantic = []
  47   combined   = []
  48   markerMap  = {}
  49
  50   for wrapper in wrappers
  51     marker = new Marker(wrapper, window.document)
  52     group = switch
  53       when wrapper.parentIndex? then combined
  54       when wrapper.semantic     then semantic
  55       else unsemantic
  56     group.push(marker)
  57     markerMap[wrapper.elementIndex] = marker
  58
  59   markers = semantic.concat(unsemantic)
  60
  61   return null if markers.length == 0
  62
  63   # Each marker gets a unique `z-index`, so that it can be determined if a
  64   # marker overlaps another. Put more important markers (higher weight) at the
  65   # end, so that they get higher `z-index`, in order not to be overlapped.
  66   zIndex = 0
  67   setZIndexes = (markers) ->
  68     markers.sort((a, b) -> a.weight - b.weight)
  69     for marker in markers when marker not instanceof huffman.BranchPoint
  70       marker.markerElement.style.zIndex = zIndex++
  71       # Add `z-index` space for all the children of the marker.
  72       zIndex += marker.wrapper.numChildren if marker.wrapper.numChildren?
  73
  74   # The `markers` passed to this function have been sorted by `setZIndexes` in
  75   # advance, so we can skip sorting in the `huffman.createTree` function.
  76   hintChars = options.hint_chars
  77   createHuffmanTree = (markers) ->
  78     return huffman.createTree(markers, hintChars.length, {sorted: true})
  79
  80   # Semantic elements should always get better hints and higher `z-index`:es
  81   # than unsemantic ones, even if they are smaller. The former is achieved by
  82   # putting the unsemantic elements in their own branch of the huffman tree.
  83   if unsemantic.length > 0
  84     if markers.length > hintChars.length
  85       setZIndexes(unsemantic)
  86       subTree = createHuffmanTree(unsemantic)
  87       semantic.push(subTree)
  88     else
  89       semantic.push(unsemantic...)
  90
  91   setZIndexes(semantic)
  92
  93   tree = createHuffmanTree(semantic)
  94   tree.assignCodeWords(hintChars, (marker, hint) -> marker.setHint(hint))
  95
  96   # Markers for links with the same href can be combined to use the same hint.
  97   # They should all have the same `z-index` (because they all have the same
  98   # combined weight), but in case any of them cover another they still get a
  99   # unique `z-index` (space for this was added in `setZIndexes`).
 100   for marker in combined
 101     parent = markerMap[marker.wrapper.parentIndex]
 102     marker.markerElement.style.zIndex = parent.markerElement.style.zIndex++
 103     marker.setHint(parent.hint)
 104   markers.push(combined...)
 105
 106   removeHints(window) # Better safe than sorry.
 107   container = window.document.createElement('box')
 108   container.id = CONTAINER_ID
 109   window.gBrowser.mCurrentBrowser.parentNode.appendChild(container)
 110
 111   zoom = window.ZoomManager.getZoomForBrowser(window.gBrowser.selectedBrowser)
 112   for marker in markers
 113     container.appendChild(marker.markerElement)
 114     # Must be done after the hints have been inserted into the DOM (see
 115     # marker.coffee).
 116     marker.setPosition(viewport, zoom)
 117
 118   return markers
 119
 120
 121 getMarkableElementsAndViewport = (window, filter) ->
 122   {
 123     clientWidth, clientHeight # Viewport size excluding scrollbars, usually.
 124     scrollWidth, scrollHeight
 125   } = window.document.documentElement
 126   { innerWidth, innerHeight } = window # Viewport size including scrollbars.
 127   # We don’t want markers to cover the scrollbars, so we should use
 128   # `clientWidth` and `clientHeight`. However, when there are no scrollbars
 129   # those might be too small. Then we use `innerWidth` and `innerHeight`.
 130   width  = if scrollWidth  > innerWidth  then clientWidth  else innerWidth
 131   height = if scrollHeight > innerHeight then clientHeight else innerHeight
 132   viewport = {
 133     left:   0
 134     top:    0
 135     right:  width
 136     bottom: height
 137     width
 138     height
 139   }
 140
 141   wrappers = []
 142   getMarkableElements(window, viewport, wrappers, filter)
 143   return {wrappers, viewport}
 144
 145 # `filter` is a function that is given every element in every frame of the page.
 146 # It should return wrapper objects for markable elements and a falsy value for
 147 # all other elements. All returned wrappers are added to `wrappers`. `wrappers`
 148 # is modified instead of using return values to avoid array concatenation for
 149 # each frame. It might sound expensive to go through _every_ element, but that’s
 150 # actually what other methods like using XPath or CSS selectors would need to do
 151 # anyway behind the scenes.
 152 getMarkableElements = (window, viewport, wrappers, filter, parents = []) ->
 153   { document } = window
 154
 155   localGetElementShape = getElementShape.bind(null, window, viewport, parents)
 156   for element in getElements(document, viewport) when element instanceof Element
 157     continue unless wrapper = filter(element, localGetElementShape)
 158     wrappers.push(wrapper)
 159
 160   for frame in window.frames
 161     rect = frame.frameElement.getBoundingClientRect() # Frames only have one.
 162     continue unless isInsideViewport(rect, viewport)
 163
 164     # Calculate the visible part of the frame, according to the parent.
 165     { clientWidth, clientHeight } = frame.document.documentElement
 166     frameViewport =
 167       left:   Math.max(viewport.left - rect.left, 0)
 168       top:    Math.max(viewport.top  - rect.top,  0)
 169       right:  clientWidth  + Math.min(viewport.right  - rect.right,  0)
 170       bottom: clientHeight + Math.min(viewport.bottom - rect.bottom, 0)
 171
 172     # `.getComputedStyle()` may return `null` if the computed style isn’t
 173     # availble yet. If so, consider the element not visible.
 174     continue unless computedStyle = window.getComputedStyle(frame.frameElement)
 175     offset =
 176       left: rect.left +
 177         parseFloat(computedStyle.getPropertyValue('border-left-width')) +
 178         parseFloat(computedStyle.getPropertyValue('padding-left'))
 179       top: rect.top +
 180         parseFloat(computedStyle.getPropertyValue('border-top-width')) +
 181         parseFloat(computedStyle.getPropertyValue('padding-top'))
 182
 183     getMarkableElements(frame, frameViewport, wrappers, filter,
 184                         parents.concat({ window, offset }))
 185
 186   return
 187
 188 # Returns a suitable set of elements in `document` that could possibly get
 189 # markers.
 190 getElements = (document, viewport) ->
 191   # In XUL documents we have to resort to get every single element in the entire
 192   # document, because there are lots of complicated “anonymous” elements, which
 193   # `windowUtils.nodesFromRect()` does not catch.
 194   if document instanceof XULDocument
 195     elements = []
 196     getAllRegular = (element) ->
 197       for child in element.getElementsByTagName('*')
 198         elements.push(child)
 199         getAllAnonymous(child)
 200       return
 201     getAllAnonymous = (element) ->
 202       for child in document.getAnonymousNodes(element) or []
 203         continue unless child instanceof Element
 204         elements.push(child)
 205         getAllRegular(child)
 206       return
 207     getAllRegular(document.documentElement)
 208     return elements
 209   # In other documents we can use a super-fast Firefox API to get all elements
 210   # in the viewport.
 211   else
 212     windowUtils = document.defaultView
 213       .QueryInterface(Ci.nsIInterfaceRequestor)
 214       .getInterface(Ci.nsIDOMWindowUtils)
 215     return windowUtils.nodesFromRect(
 216       viewport.left, viewport.top, # Rect coordinates, relative to the viewport.
 217       # Distances to expand in all directions: top, right, bottom, left.
 218       0, viewport.right, viewport.bottom, 0,
 219       true, # Unsure what this does. Toggling it seems to make no difference.
 220       true  # Ensure that the list of matching elements is fully up to date.
 221     )
 222
 223 # Returns the “shape” of `element`:
 224 #
 225 # - `nonCoveredPoint`: The coordinates of the first point of `element` that
 226 #   isn’t covered by another element (except children of `element`). It also
 227 #   contains the offset needed to make those coordinates relative to the top
 228 #   frame, as well as the rectangle that the coordinates occur in.
 229 # - `area`: The area of the part of `element` that is inside `viewport`.
 230 #
 231 # Returns `null` if `element` is outside `viewport` or entirely covered by other
 232 # elements.
 233 getElementShape = (window, viewport, parents, element) ->
 234   # `element.getClientRects()` returns a list of rectangles, usually just one,
 235   # which is identical to the one returned by `element.getBoundingClientRect()`.
 236   # However, if `element` is inline and line-wrapped, then it returns one
 237   # rectangle for each line, since each line may be of different length, for
 238   # example. That allows us to properly add hints to line-wrapped links.
 239   rects = element.getClientRects()
 240   totalArea = 0
 241   visibleRects = []
 242   # The `isInsideViewport` check is not needed in HTML documents, but in XUL
 243   # documents (see `getElements()`). However, there seems to be no performance
 244   # gain in not running the check in HTML documents, so let’s keep it simple.
 245   for rect in rects when isInsideViewport(rect, viewport)
 246     visibleRect = adjustRectToViewport(rect, viewport)
 247     continue if visibleRect.area == 0
 248     totalArea += visibleRect.area
 249     visibleRects.push(visibleRect)
 250
 251   if visibleRects.length == 0
 252     if rects.length == 1 and totalArea == 0
 253       [ rect ] = rects
 254       if rect.width > 0 or rect.height > 0
 255         # If we get here, it means that everything inside `element` is floated
 256         # and/or absolutely positioned (and that `element` hasn’t been made to
 257         # “contain” the floats). For example, a link in a menu could contain a
 258         # span of text floated to the left and an icon floated to the right.
 259         # Those are still clickable. Therefore we return the shape of the first
 260         # visible child instead. At least in that example, that’s the best bet.
 261         for child in element.children
 262           shape = getElementShape(window, viewport, parents, child)
 263           return shape if shape
 264     return null
 265
 266   # Even if `element` has a visible rect, it might be covered by other elements.
 267   for visibleRect in visibleRects
 268     nonCoveredPoint = getFirstNonCoveredPoint(window, viewport, element,
 269                                               visibleRect, parents)
 270     if nonCoveredPoint
 271       nonCoveredPoint.rect = visibleRect
 272       break
 273
 274   return null unless nonCoveredPoint
 275
 276   return {
 277     nonCoveredPoint, area: totalArea
 278   }
 279
 280
 281 MINIMUM_EDGE_DISTANCE = 4
 282 isInsideViewport = (rect, viewport) ->
 283   return \
 284     rect.left   <= viewport.right  - MINIMUM_EDGE_DISTANCE and
 285     rect.top    <= viewport.bottom + MINIMUM_EDGE_DISTANCE and
 286     rect.right  >= viewport.left   + MINIMUM_EDGE_DISTANCE and
 287     rect.bottom >= viewport.top    - MINIMUM_EDGE_DISTANCE
 288
 289
 290 adjustRectToViewport = (rect, viewport) ->
 291   # The right and bottom values are subtracted by 1 because
 292   # `document.elementFromPoint(right, bottom)` does not return the element
 293   # otherwise.
 294   left   = Math.max(rect.left,       viewport.left)
 295   right  = Math.min(rect.right - 1,  viewport.right)
 296   top    = Math.max(rect.top,        viewport.top)
 297   bottom = Math.min(rect.bottom - 1, viewport.bottom)
 298
 299   # Make sure that `right >= left and bottom >= top`, since we subtracted by 1
 300   # above.
 301   right  = Math.max(right, left)
 302   bottom = Math.max(bottom, top)
 303
 304   width  = right - left
 305   height = bottom - top
 306   area   = Math.floor(width * height)
 307
 308   return {
 309     left, right, top, bottom
 310     height, width, area
 311   }
 312
 313
 314 getFirstNonCoveredPoint = (window, viewport, element, elementRect, parents) ->
 315   # Tries a point `(x + dx, y + dy)`. Returns `(x, y)` (and the frame offset)
 316   # if it passes the tests. Otherwise it tries to the right of whatever is at
 317   # `(x, y)`, `tryRight` times . If nothing succeeds, `false` is returned. `dx`
 318   # and `dy` are used to offset the wanted point `(x, y)` while trying (see the
 319   # invocations of `tryPoint` below).
 320   tryPoint = (x, dx, y, dy, tryRight = 0) ->
 321     elementAtPoint = window.document.elementFromPoint(x + dx, y + dy)
 322     offset = {left: 0, top: 0}
 323     found = false
 324
 325     # Ensure that `element`, or a child of `element` (anything inside an `<a>`
 326     # is clickable too), really is present at (x,y). Note that this is not 100%
 327     # bullet proof: Combinations of CSS can cause this check to fail, even
 328     # though `element` isn’t covered. We don’t try to temporarily reset such CSS
 329     # because of performance. Instead we rely on that some of the attempts below
 330     # will work.
 331     if element.contains(elementAtPoint) or # Note that `a.contains(a) == true`!
 332        (window.document instanceof XULDocument and
 333         getClosestNonAnonymousParent(element) == elementAtPoint)
 334       found = true
 335       # If we’re currently in a frame, there might be something on top of the
 336       # frame that covers `element`. Therefore we ensure that the frame really
 337       # is present at the point for each parent in `parents`.
 338       currentWindow = window
 339       for parent in parents by -1
 340         offset.left += parent.offset.left
 341         offset.top  += parent.offset.top
 342         elementAtPoint = parent.window.document.elementFromPoint(
 343           offset.left + x + dx, offset.top + y + dy
 344         )
 345         unless elementAtPoint == currentWindow.frameElement
 346           found = false
 347           break
 348         currentWindow = parent.window
 349
 350     if found
 351       return {x, y, offset}
 352     else
 353       return false if elementAtPoint == null or tryRight == 0
 354       rect = elementAtPoint.getBoundingClientRect()
 355       x = rect.right - offset.left + 1
 356       return false if x > viewport.right
 357       return tryPoint(x, 0, y, 0, tryRight - 1)
 358
 359
 360   # Try the left-middle point, or immediately to the right of a covering element
 361   # at that point. If both of those are covered the whole element is considered
 362   # to be covered. The reasoning is:
 363   #
 364   # - A marker should show up as near the left edge of its visible area as
 365   #   possible. Having it appear to the far right (for example) is confusing.
 366   # - We can’t try too many times because of performance.
 367   # - We used to try left-top first, but if `element` has `border-radius`, the
 368   #   corners won’t really belong to `element`, so `document.elementFromPoint()`
 369   #   will return whatever is behind. This will result in missing or
 370   #   out-of-place markers. The solution is to temporarily add a CSS class that
 371   #   removes `border-radius`, but that turned out to be rather slow, making it
 372   #   not worth it. Usually you don’t see the difference between left-top and
 373   #   left-middle, because links are usually not that high.
 374   # - We used to try left-bottom as well, but that is so rare that it’s not
 375   #   worth it.
 376   #
 377   # It is safer to try points at least one pixel into the element from the
 378   # edges, hence the `+1`.
 379   { left, top, bottom, height } = elementRect
 380   nonCoveredPoint = tryPoint(left, +1, Math.floor(top + height / 2), 0, 1)
 381
 382   return nonCoveredPoint
 383
 384 # In XUL documents there are “anonymous” elements, whose node names start with
 385 # `xul:` or `html:`. These are never returned by `document.elementFromPoint` but
 386 # their closest non-anonymous parents are.
 387 getClosestNonAnonymousParent = (element) ->
 388   element = element.parentNode while element.prefix?
 389   return element
 390
 391 module.exports = {
 392   removeHints
 393   injectHints
 394   getMarkableElementsAndViewport
 395 }