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