extension/lib/hints.coffee

   1 ###
   2 # Copyright Anton Khodakivskiy 2012, 2013.
   3 # Copyright Simon Lydell 2013, 2014, 2015, 2016.
   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 viewportUtils = require('./viewport')
  28
  29 {devtools} = Cu.import('resource://devtools/shared/Loader.jsm', {})
  30
  31 CONTAINER_ID = 'VimFxMarkersContainer'
  32
  33 Element = Ci.nsIDOMElement
  34 XULDocument = Ci.nsIDOMXULDocument
  35
  36 shutdownHandlerAdded = false
  37
  38 # For some time we used to return the hints container from `injectHints`, and
  39 # use that reference to remove the hints when needed. That’s fine in theory, but
  40 # in case anything breaks we might loose that reference and end up with
  41 # unremovable hints on the screen. Explicitly looking for an element with the
  42 # container ID is more fail-safe.
  43 removeHints = (window) ->
  44   window.document.getElementById(CONTAINER_ID)?.remove()
  45
  46 # Create `Marker`s for every element (represented by a regular object of data
  47 # about the element—a “wrapper,” a stand-in for the real element, which is only
  48 # accessible in frame scripts) in `wrappers`, and insert them into `window`.
  49 injectHints = (window, wrappers, viewport, options) ->
  50   semantic = []
  51   unsemantic = []
  52   combined = []
  53   markerMap = {}
  54
  55   for wrapper in wrappers
  56     marker = new Marker(wrapper, window.document)
  57     group = switch
  58       when wrapper.parentIndex?
  59         combined
  60       when wrapper.semantic
  61         semantic
  62       else
  63         unsemantic
  64     group.push(marker)
  65     markerMap[wrapper.elementIndex] = marker
  66
  67   markers = semantic.concat(unsemantic)
  68
  69   # Each marker gets a unique `z-index`, so that it can be determined if a
  70   # marker overlaps another. Put more important markers (higher weight) at the
  71   # end, so that they get higher `z-index`, in order not to be overlapped.
  72   zIndex = 0
  73   setZIndexes = (markers) ->
  74     markers.sort((a, b) -> a.weight - b.weight)
  75     for marker in markers when marker not instanceof huffman.BranchPoint
  76       marker.markerElement.style.zIndex = zIndex
  77       zIndex += 1
  78       # Add `z-index` space for all the children of the marker.
  79       zIndex += marker.wrapper.numChildren if marker.wrapper.numChildren?
  80     return
  81
  82   # The `markers` passed to this function have been sorted by `setZIndexes` in
  83   # advance, so we can skip sorting in the `huffman.createTree` function.
  84   hintChars = options.hint_chars
  85   createHuffmanTree = (markers) ->
  86     return huffman.createTree(markers, hintChars.length, {sorted: true})
  87
  88   # Semantic elements should always get better hints and higher `z-index`:es
  89   # than unsemantic ones, even if they are smaller. The former is achieved by
  90   # putting the unsemantic elements in their own branch of the huffman tree.
  91   if unsemantic.length > 0
  92     if markers.length > hintChars.length
  93       setZIndexes(unsemantic)
  94       subTree = createHuffmanTree(unsemantic)
  95       semantic.push(subTree)
  96     else
  97       semantic.push(unsemantic...)
  98
  99   setZIndexes(semantic)
 100
 101   tree = createHuffmanTree(semantic)
 102   tree.assignCodeWords(hintChars, (marker, hint) -> marker.setHint(hint))
 103
 104   # Markers for links with the same href can be combined to use the same hint.
 105   # They should all have the same `z-index` (because they all have the same
 106   # combined weight), but in case any of them cover another they still get a
 107   # unique `z-index` (space for this was added in `setZIndexes`).
 108   for marker in combined
 109     parent = markerMap[marker.wrapper.parentIndex]
 110     parentZIndex = Number(parent.markerElement.style.zIndex)
 111     marker.markerElement.style.zIndex = parentZIndex
 112     parent.markerElement.style.zIndex = parentZIndex + 1
 113     marker.setHint(parent.hint)
 114   markers.push(combined...)
 115
 116   removeHints(window) # Better safe than sorry.
 117   container = window.document.createElement('box')
 118   container.id = CONTAINER_ID
 119
 120   zoom = 1
 121
 122   if options.ui
 123     container.classList.add('ui')
 124     window.document.getElementById('browser-panel').appendChild(container)
 125   else
 126     {ZoomManager, gBrowser: {selectedBrowser: browser}} = window
 127     browser.parentNode.appendChild(container)
 128     # If “full zoom” is not used, it means that “Zoom text only” is enabled.
 129     # If so, that “zoom” does not need to be taken into account.
 130     # `.getCurrentMode()` is added by the “Default FullZoom Level” extension.
 131     if ZoomManager.getCurrentMode?(browser) ? ZoomManager.useFullZoom
 132       zoom = ZoomManager.getZoomForBrowser(browser)
 133
 134   for marker in markers
 135     container.appendChild(marker.markerElement)
 136     # Must be done after the hints have been inserted into the DOM (see
 137     # marker.coffee).
 138     marker.setPosition(viewport, zoom)
 139
 140   unless shutdownHandlerAdded
 141     module.onShutdown(removeHints.bind(null, window))
 142     shutdownHandlerAdded = true
 143
 144   return {markers, markerMap}
 145
 146 getMarkableElements = (window, filter) ->
 147   viewport = viewportUtils.getWindowViewport(window)
 148   wrappers = []
 149   _getMarkableElements(window, viewport, wrappers, filter)
 150   return wrappers
 151
 152 # `filter` is a function that is given every element in every frame of the page.
 153 # It should return wrapper objects for markable elements and a falsy value for
 154 # all other elements. All returned wrappers are added to `wrappers`. `wrappers`
 155 # is modified instead of using return values to avoid array concatenation for
 156 # each frame. It might sound expensive to go through _every_ element, but that’s
 157 # actually what other methods like using XPath or CSS selectors would need to do
 158 # anyway behind the scenes.
 159 _getMarkableElements = (window, viewport, wrappers, filter, parents = []) ->
 160   {document} = window
 161
 162   for element in getAllElements(document) when element instanceof Element
 163     # `getRects` is fast and filters out most elements, so run it first of all.
 164     rects = getRects(element, viewport)
 165     continue unless rects.length > 0
 166     continue unless wrapper = filter(
 167       element, (elementArg) ->
 168         return getElementShape(
 169           window, viewport, parents, elementArg,
 170           if elementArg == element then rects else null
 171         )
 172     )
 173     wrappers.push(wrapper)
 174
 175   for frame in window.frames when frame.frameElement
 176     continue unless result = viewportUtils.getFrameViewport(
 177       frame.frameElement, viewport
 178     )
 179     {viewport: frameViewport, offset} = result
 180     _getMarkableElements(
 181       frame, frameViewport, wrappers, filter, parents.concat({window, offset})
 182     )
 183
 184   return
 185
 186 getAllElements = (document) ->
 187   unless document instanceof XULDocument
 188     return document.getElementsByTagName('*')
 189
 190   # Use a `Set` since this algorithm may find the same element more than once.
 191   # Ideally we should find a way to find all elements without duplicates.
 192   elements = new Set()
 193   getAllRegular = (element) ->
 194     # The first time `zF` is run `.getElementsByTagName('*')` may oddly include
 195     # `undefined` in its result! Filter those out.
 196     for child in element.getElementsByTagName('*') when child
 197       elements.add(child)
 198       getAllAnonymous(child)
 199     return
 200   getAllAnonymous = (element) ->
 201     for child in document.getAnonymousNodes(element) or []
 202       continue unless child instanceof Element
 203       elements.add(child)
 204       getAllRegular(child)
 205     return
 206   getAllRegular(document.documentElement)
 207   return Array.from(elements)
 208
 209 getRects = (element, viewport) ->
 210   # `element.getClientRects()` returns a list of rectangles, usually just one,
 211   # which is identical to the one returned by `element.getBoundingClientRect()`.
 212   # However, if `element` is inline and line-wrapped, then it returns one
 213   # rectangle for each line, since each line may be of different length, for
 214   # example. That allows us to properly add hints to line-wrapped links.
 215   return Array.filter(
 216     element.getClientRects(),
 217     (rect) -> viewportUtils.isInsideViewport(rect, viewport)
 218   )
 219
 220 # Returns the “shape” of `element`:
 221 #
 222 # - `nonCoveredPoint`: The coordinates of the first point of `element` that
 223 #   isn’t covered by another element (except children of `element`). It also
 224 #   contains the offset needed to make those coordinates relative to the top
 225 #   frame, as well as the rectangle that the coordinates occur in.
 226 # - `area`: The area of the part of `element` that is inside `viewport`.
 227 #
 228 # Returns `null` if `element` is outside `viewport` or entirely covered by other
 229 # elements.
 230 getElementShape = (window, viewport, parents, element, rects = null) ->
 231   rects ?= getRects(element, viewport)
 232   totalArea = 0
 233   visibleRects = []
 234   for rect in rects
 235     visibleRect = viewportUtils.adjustRectToViewport(rect, viewport)
 236     continue if visibleRect.area == 0
 237     totalArea += visibleRect.area
 238     visibleRects.push(visibleRect)
 239
 240   if visibleRects.length == 0
 241     if rects.length == 1 and totalArea == 0
 242       [rect] = rects
 243       if rect.width > 0 or rect.height > 0
 244         # If we get here, it means that everything inside `element` is floated
 245         # and/or absolutely positioned (and that `element` hasn’t been made to
 246         # “contain” the floats). For example, a link in a menu could contain a
 247         # span of text floated to the left and an icon floated to the right.
 248         # Those are still clickable. Therefore we return the shape of the first
 249         # visible child instead. At least in that example, that’s the best bet.
 250         for child in element.children
 251           shape = getElementShape(window, viewport, parents, child)
 252           return shape if shape
 253     return null
 254
 255   # Even if `element` has a visible rect, it might be covered by other elements.
 256   for visibleRect in visibleRects
 257     nonCoveredPoint = getFirstNonCoveredPoint(
 258       window, viewport, element, visibleRect, parents
 259     )
 260     break if nonCoveredPoint
 261
 262   return null unless nonCoveredPoint
 263
 264   return {
 265     nonCoveredPoint, area: totalArea
 266   }
 267
 268 getFirstNonCoveredPoint = (window, viewport, element, elementRect, parents) ->
 269   # Tries a point `(x + dx, y + dy)`. Returns `(x, y)` (and the frame offset)
 270   # if it passes the tests. Otherwise it tries to the right of whatever is at
 271   # `(x, y)`, `tryRight` times . If nothing succeeds, `false` is returned. `dx`
 272   # and `dy` are used to offset the wanted point `(x, y)` while trying (see the
 273   # invocations of `tryPoint` below).
 274   tryPoint = (x, dx, y, dy, tryRight = 0) ->
 275     elementAtPoint = window.document.elementFromPoint(x + dx, y + dy)
 276     offset = {left: 0, top: 0}
 277     found = false
 278     firstLevel = true
 279
 280     # Ensure that `element`, or a child of `element` (anything inside an `<a>`
 281     # is clickable too), really is present at (x,y). Note that this is not 100%
 282     # bullet proof: Combinations of CSS can cause this check to fail, even
 283     # though `element` isn’t covered. We don’t try to temporarily reset such CSS
 284     # because of performance. Instead we rely on that some of the attempts below
 285     # will work. (See further down for the special value `-1` of `tryRight`.)
 286     if contains(element, elementAtPoint) or tryRight == -1
 287       found = true
 288       # If we’re currently in a frame, there might be something on top of the
 289       # frame that covers `element`. Therefore we ensure that the frame really
 290       # is present at the point for each parent in `parents`.
 291       currentWindow = window
 292       for parent in parents by -1
 293         # If leaving the devtools container take the devtools zoom into account.
 294         if utils.isDevtoolsWindow(currentWindow)
 295           toolbox = window.top.gDevTools.getToolbox(
 296             devtools.TargetFactory.forTab(window.top.gBrowser.selectedTab)
 297           )
 298           if toolbox
 299             devtoolsZoom = toolbox.zoomValue
 300             offset.left *= devtoolsZoom
 301             offset.top  *= devtoolsZoom
 302             x  *= devtoolsZoom
 303             y  *= devtoolsZoom
 304             dx *= devtoolsZoom
 305             dy *= devtoolsZoom
 306
 307         offset.left += parent.offset.left
 308         offset.top  += parent.offset.top
 309         elementAtPoint = parent.window.document.elementFromPoint(
 310           offset.left + x + dx, offset.top + y + dy
 311         )
 312         firstLevel = false
 313         unless contains(currentWindow.frameElement, elementAtPoint)
 314           found = false
 315           break
 316         currentWindow = parent.window
 317
 318     return {x, y, offset} if found
 319
 320     return false if elementAtPoint == null or tryRight <= 0
 321     rect = elementAtPoint.getBoundingClientRect()
 322
 323     # `.getBoundingClientRect()` does not include pseudo-elements that are
 324     # absolutely positioned so that they go outside of the element (which is
 325     # common for `/###\`-looking tabs), but calling `.elementAtPoint()` on the
 326     # pseudo-element _does_ return the element. This means that the covering
 327     # element’s _rect_ won’t cover the element we’re looking for. If so, it’s
 328     # better to try again, forcing the element to be considered located at this
 329     # point. That’s what `-1` for the `tryRight` argument means.
 330     if firstLevel and rect.right <= x + offset.left
 331       return tryPoint(x, dx, y, dy, -1)
 332
 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. These are never returned by
 363 # `document.elementFromPoint` but their closest non-anonymous parents are.
 364 normalize = (element) ->
 365   normalized = element.ownerDocument.getBindingParent(element) or element
 366   normalized = normalized.parentNode while normalized.prefix?
 367   return normalized
 368
 369 # Returns whether `element` corresponds to `elementAtPoint`. This is only
 370 # complicated for browser elements in the web page content area.
 371 # `.elementAtPoint()` always returns `<tabbrowser#content>` then. The element
 372 # might be in another tab and thus invisible, but `<tabbrowser#content>` is the
 373 # same and visible in _all_ tabs, so we have to check that the element really
 374 # belongs to the current tab.
 375 contains = (element, elementAtPoint) ->
 376   return false unless elementAtPoint
 377   container = normalize(element)
 378   if elementAtPoint.localName == 'tabbrowser' and elementAtPoint.id == 'content'
 379     {gBrowser} = element.ownerGlobal.top
 380     tabpanel = gBrowser.getNotificationBox(gBrowser.selectedBrowser)
 381     return tabpanel.contains(element)
 382   else
 383     # Note that `a.contains(a)` is supposed to be true, but strangely aren’t for
 384     # `<menulist>`s in the Add-ons Manager, so do a direct comparison as well.
 385     return container == elementAtPoint or container.contains(elementAtPoint)
 386
 387 module.exports = {
 388   removeHints
 389   injectHints
 390   getMarkableElements
 391 }