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