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 utils = require('./utils')
  26
  27 CONTAINER_ID = 'VimFxMarkersContainer'
  28
  29 # `z-index` can be infinite in theory, but not in practice. This is the largest
  30 # value Firefox handles.
  31 MAX_Z_INDEX = 2147483647
  32
  33 SPACE = ' '
  34
  35 class MarkerContainer
  36   constructor: (options) ->
  37     {
  38       @window
  39       @getComplementaryWrappers
  40       hintChars
  41       @adjustZoom = true
  42     } = options
  43
  44     [@primaryHintChars, @secondaryHintChars] = hintChars.split(' ')
  45     @alphabet = @primaryHintChars + @secondaryHintChars
  46     @enteredHint = ''
  47     @enteredText = ''
  48
  49     @isComplementary = false
  50     @complementaryState = 'NOT_REQUESTED'
  51
  52     @visualFeedbackUpdater = null
  53
  54     @markers = []
  55     @markerMap = {}
  56     @highlightedMarkers = []
  57
  58     @container = @window.document.createElement('box')
  59     @container.id = CONTAINER_ID
  60     if @alphabet not in [@alphabet.toLowerCase(), @alphabet.toUpperCase()]
  61       @container.classList.add('has-mixedcase')
  62
  63   # This static method looks for an element with the container ID and removes
  64   # it. This is more fail-safe than `@container?.remove()`, because we might
  65   # loose the reference to the container. Then we’d end up with unremovable
  66   # hints on the screen (which has happened in the past).
  67   @remove: (window) ->
  68     window.document.getElementById(CONTAINER_ID)?.remove()
  69
  70   remove: ->
  71     MarkerContainer.remove(@window)
  72     @container = null
  73
  74   reset: ->
  75     @enteredHint = ''
  76     @enteredText = ''
  77     @resetMarkers()
  78
  79   resetMarkers: ->
  80     @resetHighlightedMarkers()
  81     for marker in @markers
  82       if marker.isComplementary == @isComplementary
  83         marker.reset()
  84         @updateHighlightedMarkers(marker)
  85       else
  86         marker.hide()
  87     @markHighlightedMarkers()
  88
  89   resetHighlightedMarkers: ->
  90     marker.markHighlighted(false) for marker in @highlightedMarkers
  91     @highlightedMarkers = []
  92
  93   markHighlightedMarkers: ->
  94     marker.markHighlighted(true) for marker in @highlightedMarkers
  95     return
  96
  97   updateHighlightedMarkers: (marker) ->
  98     return unless marker.visible
  99
 100     if @highlightedMarkers.length == 0
 101       @highlightedMarkers = [marker]
 102       return
 103
 104     [firstHighlightedMarker] = @highlightedMarkers
 105     comparison = compareHints(marker, firstHighlightedMarker, @alphabet)
 106
 107     if comparison == 0 and firstHighlightedMarker.visible
 108       @highlightedMarkers.push(marker)
 109       return
 110
 111     if comparison < 0 or not firstHighlightedMarker.visible
 112       @highlightedMarkers = [marker]
 113       return
 114
 115   # Create `Marker`s for every element (represented by a regular object of data
 116   # about the element—a “wrapper,” a stand-in for the real element, which is
 117   # only accessible in frame scripts) in `wrappers`, and insert them into
 118   # `@window`.
 119   injectHints: (wrappers, viewport, pass) ->
 120     isComplementary = (pass == 'complementary')
 121     markers = Array(wrappers.length)
 122     markerMap = {}
 123
 124     for wrapper, index in wrappers
 125       marker = new Marker(wrapper, @window.document, {isComplementary})
 126       markers[index] = marker
 127       markerMap[wrapper.elementIndex] = marker
 128       if marker.isComplementary != @isComplementary or @enteredHint != ''
 129         marker.hide()
 130
 131     nonCombinedMarkers =
 132       markers.filter((marker) -> not marker.wrapper.parentIndex?)
 133     prefixes = switch pass
 134       when 'first'
 135         @primaryHintChars
 136       when 'second'
 137         @primaryHintChars[@markers.length..] + @secondaryHintChars
 138       else
 139         @alphabet
 140     diff = @alphabet.length - prefixes.length
 141     paddedMarkers =
 142       if diff > 0
 143         # Dummy nodes with infinite weight are guaranteed to be first-level
 144         # children of the Huffman tree. When there are less prefixes than
 145         # characters in the alphabet, adding a few such dummy nodes makes sure
 146         # that there is one child per prefix in the first level (discarding the
 147         # dummy children).
 148         nonCombinedMarkers.concat(Array(diff).fill({weight: Infinity}))
 149       else
 150         # Otherwise, nothing needs to be done. Simply use as many prefixes as
 151         # needed (and ignore any remaining ones).
 152         nonCombinedMarkers
 153
 154     tree = huffman.createTree(paddedMarkers, @alphabet.length)
 155
 156     index = 0
 157     for node in tree.children by -1 when node.weight != Infinity
 158       prefix = prefixes[index]
 159       if node instanceof huffman.BranchPoint
 160         node.assignCodeWords(@alphabet, setHint, prefix)
 161       else
 162         setHint(node, prefix)
 163       index += 1
 164
 165     # Each marker gets a unique `z-index`, so that it can be determined if a
 166     # marker overlaps another. Larger elements should have higher `z-index`,
 167     # because it looks odd when the hint for a smaller element overlaps the hint
 168     # for a larger element. Existing markers should also have higher `z-index`
 169     # than newer markers, which is why we start out large and not at zero.
 170     zIndex = MAX_Z_INDEX - markers.length - @markers.length + 1
 171     markers.sort((a, b) -> a.wrapper.area - b.wrapper.area)
 172     for marker in markers
 173       marker.markerElement.style.zIndex = zIndex
 174       zIndex += 1
 175
 176       if marker.wrapper.parentIndex?
 177         parent = markerMap[marker.wrapper.parentIndex]
 178         marker.setHint(parent.hint)
 179
 180       @updateHighlightedMarkers(marker)
 181
 182     @markHighlightedMarkers()
 183
 184     zoom = 1
 185     if @adjustZoom
 186       {ZoomManager, gBrowser: {selectedBrowser: browser}} = @window
 187       # If “full zoom” is not used, it means that “Zoom text only” is enabled.
 188       # If so, that “zoom” does not need to be taken into account.
 189       # `.getCurrentMode()` is added by the “Default FullZoom Level” extension.
 190       if ZoomManager.getCurrentMode?(browser) ? ZoomManager.useFullZoom
 191         zoom = ZoomManager.getZoomForBrowser(browser)
 192
 193     fragment = @window.document.createDocumentFragment()
 194     fragment.appendChild(marker.markerElement) for marker in markers
 195     @container.appendChild(fragment)
 196
 197     # Must be done after the hints have been inserted into the DOM (see
 198     # `Marker::setPosition`).
 199     marker.setPosition(viewport, zoom) for marker in markers
 200
 201     @markers.push(markers...)
 202     Object.assign(@markerMap, markerMap)
 203
 204     if @enteredText != ''
 205       [matchingMarkers, nonMatchingMarkers] = @matchText(@enteredText)
 206       marker.hide() for marker in nonMatchingMarkers
 207       @setHintsForTextFilteredMarkers()
 208       @updateVisualFeedback(matchingMarkers)
 209
 210   setHintsForTextFilteredMarkers: ->
 211     markers = []
 212     combined = []
 213     visibleParentMap = {}
 214
 215     visibleMarkers = @markers.filter((marker) -> marker.visible)
 216
 217     for marker in visibleMarkers
 218       wrappedMarker = wrapTextFilteredMarker(marker)
 219       {parentIndex} = marker.wrapper
 220
 221       if parentIndex?
 222         parent =
 223           if parentIndex of visibleParentMap
 224             visibleParentMap[parentIndex]
 225           else
 226             wrapTextFilteredMarker(@markerMap[parentIndex])
 227
 228         # If the parent isn’t visible, it’s because it didn’t match
 229         # `@enteredText`. If so, promote this marker as the parent.
 230         visibleParent = if parent.marker.visible then parent else wrappedMarker
 231         visibleParentIndex = visibleParent.marker.wrapper.elementIndex
 232         visibleParentMap[visibleParentIndex] = visibleParent
 233
 234         if visibleParent == wrappedMarker
 235           markers.push(wrappedMarker)
 236         else
 237           combined.push(wrappedMarker)
 238           # Make sure that all combined markers use the highest weight.
 239           if visibleParent.weight < wrappedMarker.weight
 240             visibleParent.weight = wrappedMarker.weight
 241
 242       else
 243         markers.push(wrappedMarker)
 244
 245     tree = huffman.createTree(markers, @alphabet.length)
 246     tree.assignCodeWords(@alphabet, ({marker}, hint) -> marker.setHint(hint))
 247
 248     for {marker} in combined
 249       {marker: parent} = visibleParentMap[marker.wrapper.parentIndex]
 250       marker.setHint(parent.hint)
 251
 252     @resetHighlightedMarkers()
 253     for {marker} in markers.concat(combined)
 254       @updateHighlightedMarkers(marker)
 255       marker.refreshPosition()
 256     @markHighlightedMarkers()
 257
 258     return
 259
 260   toggleComplementary: ->
 261     if not @isComplementary and
 262        @complementaryState in ['NOT_REQUESTED', 'NOT_FOUND']
 263       @isComplementary = true
 264       @complementaryState = 'PENDING'
 265       @getComplementaryWrappers(({wrappers, viewport}) =>
 266         if wrappers.length > 0
 267           @complementaryState = 'FOUND'
 268           @enteredText = '' if @isComplementary
 269           @injectHints(wrappers, viewport, 'complementary')
 270           if @isComplementary
 271             @reset()
 272             @updateVisualFeedback([])
 273         else
 274           @isComplementary = false
 275           @complementaryState = 'NOT_FOUND'
 276       )
 277
 278     else
 279       @isComplementary = not @isComplementary
 280       unless @complementaryState == 'PENDING'
 281         @reset()
 282         @updateVisualFeedback([])
 283
 284   matchHint: (hint) ->
 285     matchingMarkers = []
 286     nonMatchingMarkers = []
 287
 288     for marker in @markers when marker.visible
 289       if marker.matchHint(hint)
 290         matchingMarkers.push(marker)
 291       else
 292         nonMatchingMarkers.push(marker)
 293
 294     return [matchingMarkers, nonMatchingMarkers]
 295
 296   matchText: (text) ->
 297     matchingMarkers = []
 298     nonMatchingMarkers = []
 299
 300     splitEnteredText = @splitEnteredText(text)
 301     for marker in @markers when marker.visible
 302       if marker.matchText(splitEnteredText)
 303         matchingMarkers.push(marker)
 304       else
 305         nonMatchingMarkers.push(marker)
 306
 307     return [matchingMarkers, nonMatchingMarkers]
 308
 309   splitEnteredText: (text = @enteredText) ->
 310     return text.trim().split(SPACE)
 311
 312   isHintChar: (char) ->
 313     return (@enteredHint != '' or char in @alphabet)
 314
 315   addChar: (char, isHintChar = null) ->
 316     @isComplementary = false if @complementaryState == 'PENDING'
 317     isHintChar ?= @isHintChar(char)
 318     hint = @enteredHint + char
 319     text = @enteredText + char.toLowerCase()
 320
 321     if not isHintChar and char == SPACE
 322       matchingMarkers = @markers.filter((marker) -> marker.visible)
 323       unless @enteredText == '' or @enteredText.endsWith(SPACE)
 324         @enteredText = text
 325         @updateVisualFeedback(matchingMarkers)
 326       return matchingMarkers
 327
 328     [matchingMarkers, nonMatchingMarkers] =
 329       if isHintChar
 330         @matchHint(hint)
 331       else
 332         @matchText(text)
 333
 334     return nonMatchingMarkers if matchingMarkers.length == 0
 335
 336     marker.hide() for marker in nonMatchingMarkers
 337
 338     if isHintChar
 339       @enteredHint = hint
 340       @resetHighlightedMarkers()
 341       for marker in matchingMarkers
 342         marker.markMatchedPart(hint)
 343         @updateHighlightedMarkers(marker)
 344       @markHighlightedMarkers()
 345     else
 346       @enteredText = text
 347       @setHintsForTextFilteredMarkers() unless nonMatchingMarkers.length == 0
 348
 349     @updateVisualFeedback(matchingMarkers)
 350     return matchingMarkers
 351
 352   deleteChar: ->
 353     @isComplementary = false if @complementaryState == 'PENDING'
 354     return @deleteHintChar() or @deleteTextChar()
 355
 356   deleteHintChar: ->
 357     return false if @enteredHint == ''
 358     hint = @enteredHint[...-1]
 359     matchingMarkers = []
 360
 361     @resetHighlightedMarkers()
 362     for marker in @markers when marker.isComplementary == @isComplementary
 363       marker.markMatchedPart(hint)
 364       if marker.matchHint(hint)
 365         marker.show()
 366         matchingMarkers.push(marker)
 367       @updateHighlightedMarkers(marker)
 368     @markHighlightedMarkers()
 369
 370     @enteredHint = hint
 371     @updateVisualFeedback(matchingMarkers)
 372     return true
 373
 374   deleteTextChar: ->
 375     return false if @enteredText == ''
 376     text = @enteredText[...-1]
 377     matchingMarkers = []
 378
 379     if text == ''
 380       @resetMarkers()
 381       matchingMarkers = @markers.filter((marker) -> marker.visible)
 382     else
 383       splitEnteredText = @splitEnteredText(text)
 384       for marker in @markers when marker.isComplementary == @isComplementary
 385         if marker.matchText(splitEnteredText)
 386           marker.show()
 387           matchingMarkers.push(marker)
 388       @setHintsForTextFilteredMarkers()
 389
 390     @enteredText = text
 391     @updateVisualFeedback(matchingMarkers)
 392     return true
 393
 394   updateVisualFeedback: (matchingMarkers) ->
 395     @visualFeedbackUpdater?(this, matchingMarkers)
 396
 397   rotateOverlapping: (forward) ->
 398     rotateOverlappingMarkers(@markers, forward)
 399
 400 # Finds all stacks of markers that overlap each other (by using `getStackFor`)
 401 # (#1), and rotates their `z-index`:es (#2), thus alternating which markers are
 402 # visible.
 403 rotateOverlappingMarkers = (originalMarkers, forward) ->
 404   # `markers` will be mutated and eventually empty.
 405   markers = originalMarkers.filter((marker) -> marker.visible)
 406
 407   # (#1)
 408   stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
 409
 410   # (#2)
 411   # Stacks of length 1 don't participate in any overlapping, and can therefore
 412   # be skipped.
 413   for stack in stacks when stack.length > 1
 414     # This sort is not required, but makes the rotation more predictable.
 415     stack.sort((a, b) ->
 416       return a.markerElement.style.zIndex - b.markerElement.style.zIndex
 417     )
 418
 419     zIndices = (marker.markerElement.style.zIndex for marker in stack)
 420     # Shift the `z-index`:es one item forward or back. The higher the `z-index`,
 421     # the more important the element. `forward` should give the next-most
 422     # important element the best `z-index` and so on.
 423     if forward
 424       zIndices.push(zIndices.shift())
 425     else
 426       zIndices.unshift(zIndices.pop())
 427
 428     for marker, index in stack
 429       marker.markerElement.style.zIndex = zIndices[index]
 430
 431   return
 432
 433 # Get an array containing `marker` and all markers that overlap `marker`, if
 434 # any, which is called a "stack". All markers in the returned stack are spliced
 435 # out from `markers`, thus mutating it.
 436 getStackFor = (marker, markers) ->
 437   stack = [marker]
 438
 439   {top, bottom, left, right} = marker.position
 440
 441   index = 0
 442   while index < markers.length
 443     nextMarker = markers[index]
 444
 445     next = nextMarker.position
 446     overlapsVertically   = (next.bottom >= top  and next.top  <= bottom)
 447     overlapsHorizontally = (next.right  >= left and next.left <= right)
 448
 449     if overlapsVertically and overlapsHorizontally
 450       # Also get all markers overlapping this one.
 451       markers.splice(index, 1)
 452       stack = stack.concat(getStackFor(nextMarker, markers))
 453     else
 454       # Continue the search.
 455       index += 1
 456
 457   return stack
 458
 459 setHint = (marker, hint) -> marker.setHint(hint)
 460
 461 # When creating hints after having filtered the markers by their text, it makes
 462 # sense to give the elements with the _smallest_ area the best hints. The idea
 463 # is that the more of the element’s text is matched, the more likely it is to be
 464 # the intended target.
 465 wrapTextFilteredMarker = (marker) ->
 466   return {marker, weight: -marker.wrapper.shape.area}
 467
 468 compareHints = (markerA, markerB, alphabet) ->
 469   lengthDiff = markerA.hint.length - markerB.hint.length
 470   return lengthDiff unless lengthDiff == 0
 471
 472   return 0 if markerA.hint == markerB.hint
 473
 474   scoresA = getHintCharScores(markerA.hint, alphabet)
 475   scoresB = getHintCharScores(markerB.hint, alphabet)
 476
 477   sumA = utils.sum(scoresA)
 478   sumB = utils.sum(scoresB)
 479   sumDiff = sumA - sumB
 480   return sumDiff unless sumDiff == 0
 481
 482   for scoreA, index in scoresA by -1
 483     scoreB = scoresB[index]
 484     scoreDiff = scoreA - scoreB
 485     return scoreDiff unless scoreDiff == 0
 486
 487   return 0
 488
 489 getHintCharScores = (hint, alphabet) ->
 490   return hint.split('').map((char) -> alphabet.indexOf(char) + 1)
 491
 492 module.exports = MarkerContainer