extension/lib/marker-container.coffee

   1 ###
   2 # Copyright Simon Lydell 2013, 2014, 2015, 2016.
   3 #
   4 # This file is part of VimFx.
   5 #
   6 # VimFx is free software: you can redistribute it and/or modify
   7 # it under the terms of the GNU General Public License as published by
   8 # the Free Software Foundation, either version 3 of the License, or
   9 # (at your option) any later version.
  10 #
  11 # VimFx is distributed in the hope that it will be useful,
  12 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 # GNU General Public License for more details.
  15 #
  16 # You should have received a copy of the GNU General Public License
  17 # along with VimFx.  If not, see <http://www.gnu.org/licenses/>.
  18 ###
  19
  20 # This file manages a collection of hint markers. This involves creating them,
  21 # assigning hints to them and matching them against pressed keys.
  22
  23 huffman = require('n-ary-huffman')
  24 Marker = require('./marker')
  25
  26 CONTAINER_ID = 'VimFxMarkersContainer'
  27
  28 # `z-index` can be infinite in theory, but not in practice. This is the largest
  29 # value Firefox handles.
  30 MAX_Z_INDEX = 2147483647
  31
  32 class MarkerContainer
  33   constructor: (options) ->
  34     {
  35       @window
  36       @getComplementaryWrappers
  37       hintChars
  38       @adjustZoom = true
  39     } = options
  40
  41     [@primaryHintChars, @secondaryHintChars] = hintChars.split(' ')
  42     @alphabet = @primaryHintChars + @secondaryHintChars
  43     @numEnteredChars = 0
  44
  45     @isComplementary = false
  46     @hasLookedForComplementaryWrappers = false
  47
  48     @markers = []
  49     @markerMap = {}
  50
  51     @container = @window.document.createElement('box')
  52     @container.id = CONTAINER_ID
  53
  54   # This static method looks for an element with the container ID and removes
  55   # it. This is more fail-safe than `@container?.remove()`, because we might
  56   # loose the reference to the container. Then we’d end up with unremovable
  57   # hints on the screen (which has happened in the past).
  58   @remove: (window) ->
  59     window.document.getElementById(CONTAINER_ID)?.remove()
  60
  61   remove: ->
  62     MarkerContainer.remove(@window)
  63     @container = null
  64
  65   reset: ->
  66     @numEnteredChars = 0
  67     marker.reset() for marker in @markers when marker.hintIndex > 0
  68     @refreshComplementaryVisiblity()
  69
  70   refreshComplementaryVisiblity: ->
  71     for marker in @markers
  72       marker.setVisibility(marker.isComplementary == @isComplementary)
  73     return
  74
  75   # Create `Marker`s for every element (represented by a regular object of data
  76   # about the element—a “wrapper,” a stand-in for the real element, which is
  77   # only accessible in frame scripts) in `wrappers`, and insert them into
  78   # `@window`.
  79   injectHints: (wrappers, viewport, pass) ->
  80     isComplementary = (pass == 'complementary')
  81     combined = []
  82     markers = []
  83     markerMap = {}
  84
  85     for wrapper in wrappers
  86       marker = new Marker(wrapper, @window.document, {isComplementary})
  87       if wrapper.parentIndex?
  88         combined.push(marker)
  89       else
  90         markers.push(marker)
  91       markerMap[wrapper.elementIndex] = marker
  92
  93     # Both the `z-index` assignment and the Huffman algorithm below require the
  94     # markers to be sorted.
  95     markers.sort((a, b) -> a.weight - b.weight)
  96
  97     # Each marker gets a unique `z-index`, so that it can be determined if a
  98     # marker overlaps another. More important markers (higher weight) should
  99     # have higher `z-index`, in order not to start out overlapped. Existing
 100     # markers should also have higher `z-index` than newer markers, which is why
 101     # we start out large and not at zero.
 102     zIndex =
 103       MAX_Z_INDEX - markers.length - combined.length - @markers.length + 1
 104     for marker in markers
 105       marker.markerElement.style.zIndex = zIndex
 106       zIndex += 1
 107       # Add `z-index` space for all the children of the marker.
 108       zIndex += marker.wrapper.numChildren if marker.wrapper.numChildren?
 109
 110     prefixes = switch pass
 111       when 'first'
 112         @primaryHintChars
 113       when 'second'
 114         @primaryHintChars[@markers.length..] + @secondaryHintChars
 115       else
 116         @alphabet
 117     diff = @alphabet.length - prefixes.length
 118     paddedMarkers =
 119       if diff > 0
 120         # Dummy nodes with infinite weight are be guaranteed to be first-level
 121         # children of the Huffman tree. When there are less prefixes than
 122         # characters in the alphabet, adding a few such dummy nodes makes sure
 123         # that there is one child per prefix in the first level (discarding the
 124         # dummy children).
 125         markers.concat(Array(diff).fill({weight: Infinity}))
 126       else
 127         # Otherwise, nothing needs to be done. Simply use as many prefixes as
 128         # needed (and ignore any remaining ones).
 129         markers
 130
 131     tree = huffman.createTree(paddedMarkers, @alphabet.length, {sorted: true})
 132
 133     setHint = (marker, hint) -> marker.setHint(hint)
 134     index = 0
 135     for node in tree.children by -1 when node.weight != Infinity
 136       prefix = prefixes[index]
 137       if node instanceof huffman.BranchPoint
 138         node.assignCodeWords(@alphabet, setHint, prefix)
 139       else
 140         setHint(node, prefix)
 141       index += 1
 142
 143     # Markers for links with the same href can be combined to use the same hint.
 144     # They should all have the same `z-index` (because they all have the same
 145     # combined weight), but in case any of them cover another they still get a
 146     # unique `z-index` (space for this was added above).
 147     for marker in combined
 148       parent = markerMap[marker.wrapper.parentIndex]
 149       parentZIndex = Number(parent.markerElement.style.zIndex)
 150       marker.markerElement.style.zIndex = parentZIndex
 151       parent.markerElement.style.zIndex = parentZIndex + 1
 152       marker.setHint(parent.hint)
 153     markers.push(combined...)
 154
 155     zoom = 1
 156     if @adjustZoom
 157       {ZoomManager, gBrowser: {selectedBrowser: browser}} = @window
 158       # If “full zoom” is not used, it means that “Zoom text only” is enabled.
 159       # If so, that “zoom” does not need to be taken into account.
 160       # `.getCurrentMode()` is added by the “Default FullZoom Level” extension.
 161       if ZoomManager.getCurrentMode?(browser) ? ZoomManager.useFullZoom
 162         zoom = ZoomManager.getZoomForBrowser(browser)
 163
 164     fragment = @window.document.createDocumentFragment()
 165     fragment.appendChild(marker.markerElement) for marker in markers
 166     @container.appendChild(fragment)
 167
 168     # Must be done after the hints have been inserted into the DOM (see
 169     # `Marker::setPosition`).
 170     marker.setPosition(viewport, zoom) for marker in markers
 171
 172     @markers.push(markers...)
 173     Object.assign(@markerMap, markerMap)
 174
 175   toggleComplementary: ->
 176     if not @isComplementary and not @hasLookedForComplementaryWrappers
 177       @isComplementary = true
 178       @hasLookedForComplementaryWrappers = true
 179       @getComplementaryWrappers(({wrappers, viewport}) =>
 180         if wrappers.length > 0
 181           @injectHints(wrappers, viewport, 'complementary')
 182           if @isComplementary
 183             @reset()
 184           else
 185             @refreshComplementaryVisiblity()
 186         else
 187           @isComplementary = false
 188           @hasLookedForComplementaryWrappers = false
 189       )
 190     else
 191       @isComplementary = not @isComplementary
 192       @reset()
 193
 194   matchHintChar: (char) ->
 195     matchedMarkers = []
 196
 197     for marker in @markers
 198       if marker.isComplementary == @isComplementary and
 199          marker.hintIndex == @numEnteredChars
 200         matched = marker.matchHintChar(char)
 201         marker.hide() unless matched
 202         if marker.isMatched()
 203           marker.markMatched(true)
 204           matchedMarkers.push(marker)
 205
 206     @numEnteredChars += 1
 207     return matchedMarkers
 208
 209   deleteHintChar: ->
 210     for marker in @markers
 211       switch marker.hintIndex - @numEnteredChars
 212         when 0
 213           marker.deleteHintChar()
 214         when -1
 215           marker.show()
 216     @numEnteredChars -= 1 unless @numEnteredChars == 0
 217
 218
 219   rotateOverlapping: (forward) ->
 220     rotateOverlappingMarkers(@markers, forward)
 221
 222 # Finds all stacks of markers that overlap each other (by using `getStackFor`)
 223 # (#1), and rotates their `z-index`:es (#2), thus alternating which markers are
 224 # visible.
 225 rotateOverlappingMarkers = (originalMarkers, forward) ->
 226   # Shallow working copy. This is necessary since `markers` will be mutated and
 227   # eventually empty.
 228   markers = originalMarkers[..]
 229
 230   # (#1)
 231   stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
 232
 233   # (#2)
 234   # Stacks of length 1 don't participate in any overlapping, and can therefore
 235   # be skipped.
 236   for stack in stacks when stack.length > 1
 237     # This sort is not required, but makes the rotation more predictable.
 238     stack.sort((a, b) ->
 239       return a.markerElement.style.zIndex - b.markerElement.style.zIndex
 240     )
 241
 242     zIndices = (marker.markerElement.style.zIndex for marker in stack)
 243     # Shift the `z-index`:es one item forward or back. The higher the `z-index`,
 244     # the more important the element. `forward` should give the next-most
 245     # important element the best `z-index` and so on.
 246     if forward
 247       zIndices.push(zIndices.shift())
 248     else
 249       zIndices.unshift(zIndices.pop())
 250
 251     for marker, index in stack
 252       marker.markerElement.style.zIndex = zIndices[index]
 253
 254   return
 255
 256 # Get an array containing `marker` and all markers that overlap `marker`, if
 257 # any, which is called a "stack". All markers in the returned stack are spliced
 258 # out from `markers`, thus mutating it.
 259 getStackFor = (marker, markers) ->
 260   stack = [marker]
 261
 262   {top, bottom, left, right} = marker.position
 263
 264   index = 0
 265   while index < markers.length
 266     nextMarker = markers[index]
 267
 268     next = nextMarker.position
 269     overlapsVertically   = (next.bottom >= top  and next.top  <= bottom)
 270     overlapsHorizontally = (next.right  >= left and next.left <= right)
 271
 272     if overlapsVertically and overlapsHorizontally
 273       # Also get all markers overlapping this one.
 274       markers.splice(index, 1)
 275       stack = stack.concat(getStackFor(nextMarker, markers))
 276     else
 277       # Continue the search.
 278       index += 1
 279
 280   return stack
 281
 282 module.exports = MarkerContainer