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 = @markerMap[parentIndex]
 223         switch
 224           when parentIndex of visibleParentMap
 225             combined.push(wrappedMarker)
 226           when parent.visible
 227             visibleParentMap[parentIndex] = wrapTextFilteredMarker(parent)
 228             combined.push(wrappedMarker)
 229           else
 230             # If the parent isn’t visible, it’s because it didn’t match
 231             # `@enteredText`. If so, promote this marker as the parent.
 232             visibleParentMap[parentIndex] = wrappedMarker
 233             markers.push(wrappedMarker)
 234       else
 235         markers.push(wrappedMarker)
 236
 237     # When creating hints after having filtered the markers by their text, it
 238     # makes sense to give the elements with the shortest text the best hints.
 239     # The idea is that the more of the element’s text is matched, the more
 240     # likely it is to be the intended target. However, using the (negative) area
 241     # as weight can result in really awful hints (such as “VVVS”) for larger
 242     # elements on crowded pages like Reddit and Hackernews, which just looks
 243     # broken. Instead this is achieved by using equal weight for all markers
 244     # (see `wrapTextFilteredMarker`) and sorting the markers by area (in
 245     # ascending order) beforehand.
 246     markers.sort((a, b) -> a.marker.text.length - b.marker.text.length)
 247
 248     tree = huffman.createTree(markers, @alphabet.length, {sorted: true})
 249     tree.assignCodeWords(@alphabet, ({marker}, hint) -> marker.setHint(hint))
 250
 251     for {marker} in combined
 252       {marker: parent} = visibleParentMap[marker.wrapper.parentIndex]
 253       marker.setHint(parent.hint)
 254
 255     @resetHighlightedMarkers()
 256     for {marker} in markers.concat(combined)
 257       @updateHighlightedMarkers(marker)
 258       marker.refreshPosition()
 259     @markHighlightedMarkers()
 260
 261     return
 262
 263   toggleComplementary: ->
 264     if not @isComplementary and
 265        @complementaryState in ['NOT_REQUESTED', 'NOT_FOUND']
 266       @isComplementary = true
 267       @complementaryState = 'PENDING'
 268       @getComplementaryWrappers(({wrappers, viewport}) =>
 269         if wrappers.length > 0
 270           @complementaryState = 'FOUND'
 271           @enteredText = '' if @isComplementary
 272           @injectHints(wrappers, viewport, 'complementary')
 273           if @isComplementary
 274             @reset()
 275             @updateVisualFeedback([])
 276         else
 277           @isComplementary = false
 278           @complementaryState = 'NOT_FOUND'
 279       )
 280
 281     else
 282       @isComplementary = not @isComplementary
 283       unless @complementaryState == 'PENDING'
 284         @reset()
 285         @updateVisualFeedback([])
 286
 287   matchHint: (hint) ->
 288     matchingMarkers = []
 289     nonMatchingMarkers = []
 290
 291     for marker in @markers when marker.visible
 292       if marker.matchHint(hint)
 293         matchingMarkers.push(marker)
 294       else
 295         nonMatchingMarkers.push(marker)
 296
 297     return [matchingMarkers, nonMatchingMarkers]
 298
 299   matchText: (text) ->
 300     matchingMarkers = []
 301     nonMatchingMarkers = []
 302
 303     splitEnteredText = @splitEnteredText(text)
 304     for marker in @markers when marker.visible
 305       if marker.matchText(splitEnteredText)
 306         matchingMarkers.push(marker)
 307       else
 308         nonMatchingMarkers.push(marker)
 309
 310     return [matchingMarkers, nonMatchingMarkers]
 311
 312   splitEnteredText: (text = @enteredText) ->
 313     return text.trim().split(SPACE)
 314
 315   isHintChar: (char) ->
 316     return (@enteredHint != '' or char in @alphabet)
 317
 318   addChar: (char, isHintChar = null) ->
 319     @isComplementary = false if @complementaryState == 'PENDING'
 320     isHintChar ?= @isHintChar(char)
 321     hint = @enteredHint + char
 322     text = @enteredText + char.toLowerCase()
 323
 324     if not isHintChar and char == SPACE
 325       matchingMarkers = @markers.filter((marker) -> marker.visible)
 326       unless @enteredText == '' or @enteredText.endsWith(SPACE)
 327         @enteredText = text
 328         @updateVisualFeedback(matchingMarkers)
 329       return matchingMarkers
 330
 331     [matchingMarkers, nonMatchingMarkers] =
 332       if isHintChar
 333         @matchHint(hint)
 334       else
 335         @matchText(text)
 336
 337     return nonMatchingMarkers if matchingMarkers.length == 0
 338
 339     marker.hide() for marker in nonMatchingMarkers
 340
 341     if isHintChar
 342       @enteredHint = hint
 343       @resetHighlightedMarkers()
 344       for marker in matchingMarkers
 345         marker.markMatchedPart(hint)
 346         @updateHighlightedMarkers(marker)
 347       @markHighlightedMarkers()
 348     else
 349       @enteredText = text
 350       @setHintsForTextFilteredMarkers() unless nonMatchingMarkers.length == 0
 351
 352     @updateVisualFeedback(matchingMarkers)
 353     return matchingMarkers
 354
 355   deleteChar: ->
 356     @isComplementary = false if @complementaryState == 'PENDING'
 357     return @deleteHintChar() or @deleteTextChar()
 358
 359   deleteHintChar: ->
 360     return false if @enteredHint == ''
 361     hint = @enteredHint[...-1]
 362     matchingMarkers = []
 363
 364     @resetHighlightedMarkers()
 365     for marker in @markers when marker.isComplementary == @isComplementary
 366       marker.markMatchedPart(hint)
 367       if marker.matchHint(hint)
 368         marker.show()
 369         matchingMarkers.push(marker)
 370       @updateHighlightedMarkers(marker)
 371     @markHighlightedMarkers()
 372
 373     @enteredHint = hint
 374     @updateVisualFeedback(matchingMarkers)
 375     return true
 376
 377   deleteTextChar: ->
 378     return false if @enteredText == ''
 379     text = @enteredText[...-1]
 380     matchingMarkers = []
 381
 382     if text == ''
 383       @resetMarkers()
 384       matchingMarkers = @markers.filter((marker) -> marker.visible)
 385     else
 386       splitEnteredText = @splitEnteredText(text)
 387       for marker in @markers when marker.isComplementary == @isComplementary
 388         if marker.matchText(splitEnteredText)
 389           marker.show()
 390           matchingMarkers.push(marker)
 391       @setHintsForTextFilteredMarkers()
 392
 393     @enteredText = text
 394     @updateVisualFeedback(matchingMarkers)
 395     return true
 396
 397   updateVisualFeedback: (matchingMarkers) ->
 398     @visualFeedbackUpdater?(this, matchingMarkers)
 399
 400   rotateOverlapping: (forward) ->
 401     rotateOverlappingMarkers(@markers, forward)
 402
 403 # Finds all stacks of markers that overlap each other (by using `getStackFor`)
 404 # (#1), and rotates their `z-index`:es (#2), thus alternating which markers are
 405 # visible.
 406 rotateOverlappingMarkers = (originalMarkers, forward) ->
 407   # `markers` will be mutated and eventually empty.
 408   markers = originalMarkers.filter((marker) -> marker.visible)
 409
 410   # (#1)
 411   stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
 412
 413   # (#2)
 414   # Stacks of length 1 don't participate in any overlapping, and can therefore
 415   # be skipped.
 416   for stack in stacks when stack.length > 1
 417     # This sort is not required, but makes the rotation more predictable.
 418     stack.sort((a, b) ->
 419       return a.markerElement.style.zIndex - b.markerElement.style.zIndex
 420     )
 421
 422     zIndices = (marker.markerElement.style.zIndex for marker in stack)
 423     # Shift the `z-index`:es one item forward or back. The higher the `z-index`,
 424     # the more important the element. `forward` should give the next-most
 425     # important element the best `z-index` and so on.
 426     if forward
 427       zIndices.push(zIndices.shift())
 428     else
 429       zIndices.unshift(zIndices.pop())
 430
 431     for marker, index in stack
 432       marker.markerElement.style.zIndex = zIndices[index]
 433
 434   return
 435
 436 # Get an array containing `marker` and all markers that overlap `marker`, if
 437 # any, which is called a "stack". All markers in the returned stack are spliced
 438 # out from `markers`, thus mutating it.
 439 getStackFor = (marker, markers) ->
 440   stack = [marker]
 441
 442   {top, bottom, left, right} = marker.position
 443
 444   index = 0
 445   while index < markers.length
 446     nextMarker = markers[index]
 447
 448     next = nextMarker.position
 449     overlapsVertically   = (next.bottom >= top  and next.top  <= bottom)
 450     overlapsHorizontally = (next.right  >= left and next.left <= right)
 451
 452     if overlapsVertically and overlapsHorizontally
 453       # Also get all markers overlapping this one.
 454       markers.splice(index, 1)
 455       stack = stack.concat(getStackFor(nextMarker, markers))
 456     else
 457       # Continue the search.
 458       index += 1
 459
 460   return stack
 461
 462 setHint = (marker, hint) -> marker.setHint(hint)
 463
 464 wrapTextFilteredMarker = (marker) ->
 465   return {marker, weight: 1}
 466
 467 compareHints = (markerA, markerB, alphabet) ->
 468   lengthDiff = markerA.hint.length - markerB.hint.length
 469   return lengthDiff unless lengthDiff == 0
 470
 471   return 0 if markerA.hint == markerB.hint
 472
 473   scoresA = getHintCharScores(markerA.hint, alphabet)
 474   scoresB = getHintCharScores(markerB.hint, alphabet)
 475
 476   sumA = utils.sum(scoresA)
 477   sumB = utils.sum(scoresB)
 478   sumDiff = sumA - sumB
 479   return sumDiff unless sumDiff == 0
 480
 481   for scoreA, index in scoresA by -1
 482     scoreB = scoresB[index]
 483     scoreDiff = scoreA - scoreB
 484     return scoreDiff unless scoreDiff == 0
 485
 486   return 0
 487
 488 getHintCharScores = (hint, alphabet) ->
 489   return hint.split('').map((char) -> alphabet.indexOf(char) + 1)
 490
 491 module.exports = MarkerContainer