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