extension/lib/marker-container.coffee

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