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