2 # Copyright Simon Lydell 2013, 2014, 2015, 2016.
4 # This file is part of VimFx.
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.
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.
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/>.
20 # This file manages a collection of hint markers. This involves creating them,
21 # assigning hints to them and matching them against pressed keys.
23 huffman = require('n-ary-huffman')
24 Marker = require('./marker')
25 utils = require('./utils')
27 CONTAINER_ID = 'VimFxMarkersContainer'
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
36 constructor: (options) ->
39 @getComplementaryWrappers
42 @minWeightDiff = 10 # Pixels of area.
45 [@primaryHintChars, @secondaryHintChars] = hintChars.split(' ')
46 @alphabet = @primaryHintChars + @secondaryHintChars
50 @isComplementary = false
51 @complementaryState = 'NOT_REQUESTED'
53 @visualFeedbackUpdater = null
57 @highlightedMarkers = []
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')
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).
69 window.document.getElementById(CONTAINER_ID)?.remove()
72 MarkerContainer.remove(@window)
81 @resetHighlightedMarkers()
82 for marker in @markers
83 if marker.isComplementary == @isComplementary
85 @updateHighlightedMarkers(marker)
88 @markHighlightedMarkers()
90 resetHighlightedMarkers: ->
91 marker.markHighlighted(false) for marker in @highlightedMarkers
92 @highlightedMarkers = []
94 markHighlightedMarkers: ->
95 marker.markHighlighted(true) for marker in @highlightedMarkers
98 updateHighlightedMarkers: (marker) ->
99 return unless marker.visible
101 if @highlightedMarkers.length == 0
102 @highlightedMarkers = [marker]
105 [firstHighlightedMarker] = @highlightedMarkers
106 comparison = compareHints(marker, firstHighlightedMarker, @alphabet)
108 if comparison == 0 and firstHighlightedMarker.visible
109 @highlightedMarkers.push(marker)
112 if comparison < 0 or not firstHighlightedMarker.visible
113 @highlightedMarkers = [marker]
116 createHuffmanTree: (markers, options = {}) ->
117 return huffman.createTree(
121 compare: compareWeights.bind(null, @minWeightDiff)
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
129 injectHints: (wrappers, viewport, pass) ->
130 markers = Array(wrappers.length)
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)
142 for wrapper, index in wrappers
143 marker = new Marker({
144 wrapper, document: @window.document, viewport, zoom
145 isComplementary: (pass == 'complementary')
147 markers[index] = marker
148 markerMap[wrapper.elementIndex] = marker
149 if marker.isComplementary != @isComplementary or @enteredHint != ''
153 markers.filter((marker) -> not marker.wrapper.parentIndex?)
154 prefixes = switch pass
158 @primaryHintChars[@markers.length..] + @secondaryHintChars
161 diff = @alphabet.length - prefixes.length
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
169 nonCombinedMarkers.concat(Array(diff).fill({weight: Infinity}))
171 # Otherwise, nothing needs to be done. Simply use as many prefixes as
172 # needed (and ignore any remaining ones).
175 tree = @createHuffmanTree(paddedMarkers)
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)
183 setHint(node, prefix)
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
197 if marker.wrapper.parentIndex?
198 parent = markerMap[marker.wrapper.parentIndex]
199 marker.setHint(parent.hint)
201 @updateHighlightedMarkers(marker)
203 @markHighlightedMarkers()
205 fragment = @window.document.createDocumentFragment()
206 fragment.appendChild(marker.markerElement) for marker in markers
207 @container.appendChild(fragment)
209 # Must be done after the hints have been inserted into the DOM (see
210 # `Marker::setPosition`).
211 marker.setPosition() for marker in markers
213 @markers.push(markers...)
214 Object.assign(@markerMap, markerMap)
216 if @enteredText != ''
217 [matchingMarkers, nonMatchingMarkers] = @matchText(@enteredText)
218 marker.hide() for marker in nonMatchingMarkers
219 @setHintsForTextFilteredMarkers()
220 @updateVisualFeedback(matchingMarkers)
222 setHintsForTextFilteredMarkers: ->
225 visibleParentMap = {}
227 visibleMarkers = @markers.filter((marker) -> marker.visible)
229 for marker in visibleMarkers
230 wrappedMarker = wrapTextFilteredMarker(marker)
231 {parentIndex} = marker.wrapper
234 parent = @markerMap[parentIndex]
236 when parentIndex of visibleParentMap
237 combined.push(wrappedMarker)
239 visibleParentMap[parentIndex] = wrapTextFilteredMarker(parent)
240 combined.push(wrappedMarker)
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)
247 markers.push(wrappedMarker)
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)
260 tree = @createHuffmanTree(markers, {sorted: true})
261 tree.assignCodeWords(@alphabet, ({marker}, hint) -> marker.setHint(hint))
263 for {marker} in combined
264 {marker: parent} = visibleParentMap[marker.wrapper.parentIndex]
265 marker.setHint(parent.hint)
267 @resetHighlightedMarkers()
268 for {marker} in markers.concat(combined)
269 @updateHighlightedMarkers(marker)
270 marker.refreshPosition()
271 @markHighlightedMarkers()
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')
287 @updateVisualFeedback([])
289 @isComplementary = false
290 @complementaryState = 'NOT_FOUND'
294 @isComplementary = not @isComplementary
295 unless @complementaryState == 'PENDING'
297 @updateVisualFeedback([])
301 nonMatchingMarkers = []
303 for marker in @markers when marker.visible
304 if marker.matchHint(hint)
305 matchingMarkers.push(marker)
307 nonMatchingMarkers.push(marker)
309 return [matchingMarkers, nonMatchingMarkers]
313 nonMatchingMarkers = []
315 splitEnteredText = @splitEnteredText(text)
316 for marker in @markers when marker.visible
317 if marker.matchText(splitEnteredText)
318 matchingMarkers.push(marker)
320 nonMatchingMarkers.push(marker)
322 return [matchingMarkers, nonMatchingMarkers]
324 splitEnteredText: (text = @enteredText) ->
325 return text.trim().split(SPACE)
327 isHintChar: (char) ->
328 return (@enteredHint != '' or char in @alphabet)
330 addChar: (char, isHintChar = null) ->
331 @isComplementary = false if @complementaryState == 'PENDING'
332 isHintChar ?= @isHintChar(char)
333 hint = @enteredHint + char
334 text = @enteredText + char.toLowerCase()
336 if not isHintChar and char == SPACE
337 matchingMarkers = @markers.filter((marker) -> marker.visible)
338 unless @enteredText == '' or @enteredText.endsWith(SPACE)
340 @updateVisualFeedback(matchingMarkers)
341 return matchingMarkers
343 [matchingMarkers, nonMatchingMarkers] =
349 return nonMatchingMarkers if matchingMarkers.length == 0
351 marker.hide() for marker in nonMatchingMarkers
355 @resetHighlightedMarkers()
356 for marker in matchingMarkers
357 marker.markMatchedPart(hint)
358 @updateHighlightedMarkers(marker)
359 @markHighlightedMarkers()
362 @setHintsForTextFilteredMarkers() unless nonMatchingMarkers.length == 0
364 @updateVisualFeedback(matchingMarkers)
365 return matchingMarkers
368 @isComplementary = false if @complementaryState == 'PENDING'
369 return @deleteHintChar() or @deleteTextChar()
372 return false if @enteredHint == ''
373 hint = @enteredHint[...-1]
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)
382 matchingMarkers.push(marker)
383 @updateHighlightedMarkers(marker)
384 @markHighlightedMarkers()
387 @updateVisualFeedback(matchingMarkers)
388 return matchingMarkers
391 return false if @enteredText == ''
392 text = @enteredText[...-1]
397 matchingMarkers = @markers.filter((marker) -> marker.visible)
399 splitEnteredText = @splitEnteredText(text)
400 for marker in @markers when marker.isComplementary == @isComplementary
401 if marker.matchText(splitEnteredText)
403 matchingMarkers.push(marker)
404 @setHintsForTextFilteredMarkers()
407 @updateVisualFeedback(matchingMarkers)
408 return matchingMarkers
410 updateVisualFeedback: (matchingMarkers) ->
411 @visualFeedbackUpdater?(this, matchingMarkers)
413 rotateOverlapping: (forward) ->
414 rotateOverlappingMarkers(@markers, forward)
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
419 rotateOverlappingMarkers = (originalMarkers, forward) ->
420 # `markers` will be mutated and eventually empty.
421 markers = originalMarkers.filter((marker) -> marker.visible)
424 stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
427 # Stacks of length 1 don't participate in any overlapping, and can therefore
429 for stack in stacks when stack.length > 1
430 # This sort is not required, but makes the rotation more predictable.
432 return a.markerElement.style.zIndex - b.markerElement.style.zIndex
435 zIndices = (marker.markerElement.style.zIndex for marker in stack)
436 # Shift the `z-index`:es one item forward or back. The higher the `z-index`,
437 # the more important the element. `forward` should give the next-most
438 # important element the best `z-index` and so on.
440 zIndices.push(zIndices.shift())
442 zIndices.unshift(zIndices.pop())
444 for marker, index in stack
445 marker.markerElement.style.zIndex = zIndices[index]
449 # Get an array containing `marker` and all markers that overlap `marker`, if
450 # any, which is called a "stack". All markers in the returned stack are spliced
451 # out from `markers`, thus mutating it.
452 getStackFor = (marker, markers) ->
455 {top, bottom, left, right} = marker.position
458 while index < markers.length
459 nextMarker = markers[index]
461 next = nextMarker.position
462 overlapsVertically = (next.bottom >= top and next.top <= bottom)
463 overlapsHorizontally = (next.right >= left and next.left <= right)
465 if overlapsVertically and overlapsHorizontally
466 # Also get all markers overlapping this one.
467 markers.splice(index, 1)
468 stack = stack.concat(getStackFor(nextMarker, markers))
470 # Continue the search.
475 setHint = (marker, hint) -> marker.setHint(hint)
477 wrapTextFilteredMarker = (marker) ->
478 return {marker, weight: 1}
480 compareHints = (markerA, markerB, alphabet) ->
481 lengthDiff = markerA.hint.length - markerB.hint.length
482 return lengthDiff unless lengthDiff == 0
484 return 0 if markerA.hint == markerB.hint
486 scoresA = getHintCharScores(markerA.hint, alphabet)
487 scoresB = getHintCharScores(markerB.hint, alphabet)
489 sumA = utils.sum(scoresA)
490 sumB = utils.sum(scoresB)
491 sumDiff = sumA - sumB
492 return sumDiff unless sumDiff == 0
494 for scoreA, index in scoresA by -1
495 scoreB = scoresB[index]
496 scoreDiff = scoreA - scoreB
497 return scoreDiff unless scoreDiff == 0
501 getHintCharScores = (hint, alphabet) ->
502 return hint.split('').map((char) -> alphabet.indexOf(char) + 1)
504 compareWeights = (minDiff, a, b) ->
505 diff = a.weight - b.weight
506 if a instanceof huffman.BranchPoint or b instanceof huffman.BranchPoint
510 when diff <= -minDiff
517 module.exports = MarkerContainer