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       if marker.isComplementary == @isComplementary and @numEnteredChars > 0
  93         marker.hide()
  94
  95     # Both the `z-index` assignment and the Huffman algorithm below require the
  96     # markers to be sorted.
  97     markers.sort((a, b) -> a.weight - b.weight)
  98
  99     # Each marker gets a unique `z-index`, so that it can be determined if a
 100     # marker overlaps another. More important markers (higher weight) should
 101     # have higher `z-index`, in order not to start out overlapped. Existing
 102     # markers should also have higher `z-index` than newer markers, which is why
 103     # we start out large and not at zero.
 104     zIndex =
 105       MAX_Z_INDEX - markers.length - combined.length - @markers.length + 1
 106     for marker in markers
 107       marker.markerElement.style.zIndex = zIndex
 108       zIndex += 1
 109       # Add `z-index` space for all the children of the marker.
 110       zIndex += marker.wrapper.numChildren if marker.wrapper.numChildren?
 111
 112     prefixes = switch pass
 113       when 'first'
 114         @primaryHintChars
 115       when 'second'
 116         @primaryHintChars[@markers.length..] + @secondaryHintChars
 117       else
 118         @alphabet
 119     diff = @alphabet.length - prefixes.length
 120     paddedMarkers =
 121       if diff > 0
 122         # Dummy nodes with infinite weight are be guaranteed to be first-level
 123         # children of the Huffman tree. When there are less prefixes than
 124         # characters in the alphabet, adding a few such dummy nodes makes sure
 125         # that there is one child per prefix in the first level (discarding the
 126         # dummy children).
 127         markers.concat(Array(diff).fill({weight: Infinity}))
 128       else
 129         # Otherwise, nothing needs to be done. Simply use as many prefixes as
 130         # needed (and ignore any remaining ones).
 131         markers
 132
 133     tree = huffman.createTree(paddedMarkers, @alphabet.length, {sorted: true})
 134
 135     setHint = (marker, hint) -> marker.setHint(hint)
 136     index = 0
 137     for node in tree.children by -1 when node.weight != Infinity
 138       prefix = prefixes[index]
 139       if node instanceof huffman.BranchPoint
 140         node.assignCodeWords(@alphabet, setHint, prefix)
 141       else
 142         setHint(node, prefix)
 143       index += 1
 144
 145     # Markers for links with the same href can be combined to use the same hint.
 146     # They should all have the same `z-index` (because they all have the same
 147     # combined weight), but in case any of them cover another they still get a
 148     # unique `z-index` (space for this was added above).
 149     for marker in combined
 150       parent = markerMap[marker.wrapper.parentIndex]
 151       parentZIndex = Number(parent.markerElement.style.zIndex)
 152       marker.markerElement.style.zIndex = parentZIndex
 153       parent.markerElement.style.zIndex = parentZIndex + 1
 154       marker.setHint(parent.hint)
 155     markers.push(combined...)
 156
 157     zoom = 1
 158     if @adjustZoom
 159       {ZoomManager, gBrowser: {selectedBrowser: browser}} = @window
 160       # If “full zoom” is not used, it means that “Zoom text only” is enabled.
 161       # If so, that “zoom” does not need to be taken into account.
 162       # `.getCurrentMode()` is added by the “Default FullZoom Level” extension.
 163       if ZoomManager.getCurrentMode?(browser) ? ZoomManager.useFullZoom
 164         zoom = ZoomManager.getZoomForBrowser(browser)
 165
 166     fragment = @window.document.createDocumentFragment()
 167     fragment.appendChild(marker.markerElement) for marker in markers
 168     @container.appendChild(fragment)
 169
 170     # Must be done after the hints have been inserted into the DOM (see
 171     # `Marker::setPosition`).
 172     marker.setPosition(viewport, zoom) for marker in markers
 173
 174     @markers.push(markers...)
 175     Object.assign(@markerMap, markerMap)
 176
 177   toggleComplementary: ->
 178     if not @isComplementary and not @hasLookedForComplementaryWrappers
 179       @isComplementary = true
 180       @hasLookedForComplementaryWrappers = true
 181       @getComplementaryWrappers(({wrappers, viewport}) =>
 182         if wrappers.length > 0
 183           @injectHints(wrappers, viewport, 'complementary')
 184           if @isComplementary
 185             @reset()
 186           else
 187             @refreshComplementaryVisiblity()
 188         else
 189           @isComplementary = false
 190           @hasLookedForComplementaryWrappers = false
 191       )
 192     else
 193       @isComplementary = not @isComplementary
 194       @reset()
 195
 196   matchHintChar: (char) ->
 197     matchedMarkers = []
 198
 199     for marker in @markers
 200       if marker.isComplementary == @isComplementary and
 201          marker.hintIndex == @numEnteredChars
 202         matched = marker.matchHintChar(char)
 203         marker.hide() unless matched
 204         if marker.isMatched()
 205           marker.markMatched(true)
 206           matchedMarkers.push(marker)
 207
 208     @numEnteredChars += 1
 209     return matchedMarkers
 210
 211   deleteHintChar: ->
 212     for marker in @markers
 213       switch marker.hintIndex - @numEnteredChars
 214         when 0
 215           marker.deleteHintChar()
 216         when -1
 217           marker.show()
 218     @numEnteredChars -= 1 unless @numEnteredChars == 0
 219
 220
 221   rotateOverlapping: (forward) ->
 222     rotateOverlappingMarkers(@markers, forward)
 223
 224 # Finds all stacks of markers that overlap each other (by using `getStackFor`)
 225 # (#1), and rotates their `z-index`:es (#2), thus alternating which markers are
 226 # visible.
 227 rotateOverlappingMarkers = (originalMarkers, forward) ->
 228   # `markers` will be mutated and eventually empty.
 229   markers = originalMarkers.filter((marker) -> marker.visible)
 230
 231   # (#1)
 232   stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
 233
 234   # (#2)
 235   # Stacks of length 1 don't participate in any overlapping, and can therefore
 236   # be skipped.
 237   for stack in stacks when stack.length > 1
 238     # This sort is not required, but makes the rotation more predictable.
 239     stack.sort((a, b) ->
 240       return a.markerElement.style.zIndex - b.markerElement.style.zIndex
 241     )
 242
 243     zIndices = (marker.markerElement.style.zIndex for marker in stack)
 244     # Shift the `z-index`:es one item forward or back. The higher the `z-index`,
 245     # the more important the element. `forward` should give the next-most
 246     # important element the best `z-index` and so on.
 247     if forward
 248       zIndices.push(zIndices.shift())
 249     else
 250       zIndices.unshift(zIndices.pop())
 251
 252     for marker, index in stack
 253       marker.markerElement.style.zIndex = zIndices[index]
 254
 255   return
 256
 257 # Get an array containing `marker` and all markers that overlap `marker`, if
 258 # any, which is called a "stack". All markers in the returned stack are spliced
 259 # out from `markers`, thus mutating it.
 260 getStackFor = (marker, markers) ->
 261   stack = [marker]
 262
 263   {top, bottom, left, right} = marker.position
 264
 265   index = 0
 266   while index < markers.length
 267     nextMarker = markers[index]
 268
 269     next = nextMarker.position
 270     overlapsVertically   = (next.bottom >= top  and next.top  <= bottom)
 271     overlapsHorizontally = (next.right  >= left and next.left <= right)
 272
 273     if overlapsVertically and overlapsHorizontally
 274       # Also get all markers overlapping this one.
 275       markers.splice(index, 1)
 276       stack = stack.concat(getStackFor(nextMarker, markers))
 277     else
 278       # Continue the search.
 279       index += 1
 280
 281   return stack
 282
 283 module.exports = MarkerContainer