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