1 # This file manages a collection of hint markers. This involves creating them,
2 # assigning hints to them and matching them against pressed keys.
4 huffman = require('n-ary-huffman')
5 Marker = require('./marker')
6 utils = require('./utils')
8 CONTAINER_ID = 'VimFxMarkersContainer'
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
17 constructor: (options) ->
20 @getComplementaryWrappers
23 @minWeightDiff = 10 # Pixels of area.
26 [@primaryHintChars, @secondaryHintChars] = hintChars.split(' ')
27 @alphabet = @primaryHintChars + @secondaryHintChars
31 @isComplementary = false
32 @complementaryState = 'NOT_REQUESTED'
34 @visualFeedbackUpdater = null
38 @highlightedMarkers = []
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')
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).
50 window.document.getElementById(CONTAINER_ID)?.remove()
53 MarkerContainer.remove(@window)
62 @resetHighlightedMarkers()
63 for marker in @markers
64 if marker.isComplementary == @isComplementary
66 @updateHighlightedMarkers(marker)
69 @markHighlightedMarkers()
71 resetHighlightedMarkers: ({visuallyOnly = false} = {}) ->
72 marker.markHighlighted(false) for marker in @highlightedMarkers
73 @highlightedMarkers = [] unless visuallyOnly
75 markHighlightedMarkers: ->
76 marker.markHighlighted(true) for marker in @highlightedMarkers
79 updateHighlightedMarkers: (marker) ->
80 return unless marker.visible
82 if @highlightedMarkers.length == 0
83 @highlightedMarkers = [marker]
86 [firstHighlightedMarker] = @highlightedMarkers
87 comparison = compareHints(marker, firstHighlightedMarker, @alphabet)
89 if comparison == 0 and firstHighlightedMarker.visible
90 @highlightedMarkers.push(marker)
93 if comparison < 0 or not firstHighlightedMarker.visible
94 @highlightedMarkers = [marker]
97 createHuffmanTree: (markers, options = {}) ->
98 return huffman.createTree(
102 compare: compareWeights.bind(null, @minWeightDiff)
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
110 injectHints: (wrappers, viewport, pass) ->
111 markers = Array(wrappers.length)
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)
123 for wrapper, index in wrappers
124 marker = new Marker({
125 wrapper, document: @window.document, viewport, zoom
126 isComplementary: (pass == 'complementary')
128 markers[index] = marker
129 markerMap[wrapper.elementIndex] = marker
130 if marker.isComplementary != @isComplementary or @enteredHint != ''
134 markers.filter((marker) -> not marker.wrapper.parentIndex?)
135 prefixes = switch pass
139 @primaryHintChars[@markers.length..] + @secondaryHintChars
142 diff = @alphabet.length - prefixes.length
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
150 nonCombinedMarkers.concat(Array(diff).fill({weight: Infinity}))
152 # Otherwise, nothing needs to be done. Simply use as many prefixes as
153 # needed (and ignore any remaining ones).
156 tree = @createHuffmanTree(paddedMarkers)
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)
164 setHint(node, prefix)
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)
175 @resetHighlightedMarkers({visuallyOnly: true})
176 for marker in markers
177 marker.markerElement.style.zIndex = zIndex
180 if marker.wrapper.parentIndex?
181 parent = markerMap[marker.wrapper.parentIndex]
182 marker.setHint(parent.hint)
184 @updateHighlightedMarkers(marker)
185 @markHighlightedMarkers()
187 fragment = @window.document.createDocumentFragment()
188 fragment.appendChild(marker.markerElement) for marker in markers
189 @container.appendChild(fragment)
191 # Must be done after the hints have been inserted into the DOM (see
192 # `Marker::setPosition`).
193 marker.setPosition() for marker in markers
195 @markers.push(markers...)
196 Object.assign(@markerMap, markerMap)
198 if @enteredText != ''
199 [matchingMarkers, nonMatchingMarkers] = @matchText(@enteredText)
200 marker.hide() for marker in nonMatchingMarkers
201 @setHintsForTextFilteredMarkers()
202 @updateVisualFeedback(matchingMarkers)
204 setHintsForTextFilteredMarkers: ->
207 visibleParentMap = {}
209 visibleMarkers = @markers.filter((marker) -> marker.visible)
211 for marker in visibleMarkers
212 wrappedMarker = wrapTextFilteredMarker(marker)
213 {parentIndex} = marker.wrapper
216 parent = @markerMap[parentIndex]
218 when parentIndex of visibleParentMap
219 combined.push(wrappedMarker)
221 visibleParentMap[parentIndex] = wrapTextFilteredMarker(parent)
222 combined.push(wrappedMarker)
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)
229 markers.push(wrappedMarker)
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)
242 tree = @createHuffmanTree(markers, {sorted: true})
243 tree.assignCodeWords(@alphabet, ({marker}, hint) -> marker.setHint(hint))
245 for {marker} in combined
246 {marker: parent} = visibleParentMap[marker.wrapper.parentIndex]
247 marker.setHint(parent.hint)
249 @resetHighlightedMarkers()
250 for {marker} in markers.concat(combined)
251 @updateHighlightedMarkers(marker)
252 marker.refreshPosition()
253 @markHighlightedMarkers()
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')
269 @updateVisualFeedback([])
271 @isComplementary = false
272 @complementaryState = 'NOT_FOUND'
276 @isComplementary = not @isComplementary
277 unless @complementaryState == 'PENDING'
279 @updateVisualFeedback([])
283 nonMatchingMarkers = []
285 for marker in @markers when marker.visible
286 if marker.matchHint(hint)
287 matchingMarkers.push(marker)
289 nonMatchingMarkers.push(marker)
291 return [matchingMarkers, nonMatchingMarkers]
295 nonMatchingMarkers = []
297 splitEnteredText = @splitEnteredText(text)
298 for marker in @markers when marker.visible
299 if marker.matchText(splitEnteredText)
300 matchingMarkers.push(marker)
302 nonMatchingMarkers.push(marker)
304 return [matchingMarkers, nonMatchingMarkers]
306 splitEnteredText: (text = @enteredText) ->
307 return text.trim().split(SPACE)
309 isHintChar: (char) ->
310 return (@enteredHint != '' or char in @alphabet)
312 addChar: (char, isHintChar = null) ->
313 @isComplementary = false if @complementaryState == 'PENDING'
314 isHintChar ?= @isHintChar(char)
315 hint = @enteredHint + char
316 text = @enteredText + char.toLowerCase()
318 if not isHintChar and char == SPACE
319 matchingMarkers = @markers.filter((marker) -> marker.visible)
320 unless @enteredText == '' or @enteredText.endsWith(SPACE)
322 @updateVisualFeedback(matchingMarkers)
323 return matchingMarkers
325 [matchingMarkers, nonMatchingMarkers] =
331 return nonMatchingMarkers if matchingMarkers.length == 0
333 marker.hide() for marker in nonMatchingMarkers
337 @resetHighlightedMarkers()
338 for marker in matchingMarkers
339 marker.markMatchedPart(hint)
340 @updateHighlightedMarkers(marker)
341 @markHighlightedMarkers()
344 @setHintsForTextFilteredMarkers() unless nonMatchingMarkers.length == 0
346 @updateVisualFeedback(matchingMarkers)
347 return matchingMarkers
350 @isComplementary = false if @complementaryState == 'PENDING'
351 return @deleteHintChar() or @deleteTextChar()
354 return false if @enteredHint == ''
355 hint = @enteredHint[...-1]
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)
364 matchingMarkers.push(marker)
365 @updateHighlightedMarkers(marker)
366 @markHighlightedMarkers()
369 @updateVisualFeedback(matchingMarkers)
370 return matchingMarkers
373 return false if @enteredText == ''
374 text = @enteredText[...-1]
379 matchingMarkers = @markers.filter((marker) -> marker.visible)
381 splitEnteredText = @splitEnteredText(text)
382 for marker in @markers when marker.isComplementary == @isComplementary
383 if marker.matchText(splitEnteredText)
385 matchingMarkers.push(marker)
386 @setHintsForTextFilteredMarkers()
389 @updateVisualFeedback(matchingMarkers)
390 return matchingMarkers
392 updateVisualFeedback: (matchingMarkers) ->
393 @visualFeedbackUpdater?(this, matchingMarkers)
395 rotateOverlapping: (forward) ->
396 rotateOverlappingMarkers(@markers, forward)
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
401 rotateOverlappingMarkers = (originalMarkers, forward) ->
402 # `markers` will be mutated and eventually empty.
403 markers = originalMarkers.filter((marker) -> marker.visible)
406 stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
409 # Stacks of length 1 don't participate in any overlapping, and can therefore
411 for stack in stacks when stack.length > 1
412 # This sort is not required, but makes the rotation more predictable.
414 return a.markerElement.style.zIndex - b.markerElement.style.zIndex
417 [first, middle..., last] =
418 (marker.markerElement.style.zIndex for marker in stack)
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.
425 [middle..., last, first]
427 [last, first, middle...]
429 for marker, index in stack
430 marker.markerElement.style.zIndex = zIndices[index]
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) ->
441 while index < markers.length
442 nextMarker = markers[index]
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))
449 # Continue the search.
454 setHint = (marker, hint) -> marker.setHint(hint)
456 wrapTextFilteredMarker = (marker) ->
457 return {marker, weight: 1}
459 compareHints = (markerA, markerB, alphabet) ->
460 lengthDiff = markerA.hint.length - markerB.hint.length
461 return lengthDiff unless lengthDiff == 0
463 return 0 if markerA.hint == markerB.hint
465 scoresA = getHintCharScores(markerA.hint, alphabet)
466 scoresB = getHintCharScores(markerB.hint, alphabet)
468 sumA = utils.sum(scoresA)
469 sumB = utils.sum(scoresB)
470 sumDiff = sumA - sumB
471 return sumDiff unless sumDiff == 0
473 for scoreA, index in scoresA by -1
474 scoreB = scoresB[index]
475 scoreDiff = scoreA - scoreB
476 return scoreDiff unless scoreDiff == 0
480 getHintCharScores = (hint, alphabet) ->
481 return hint.split('').map((char) -> alphabet.indexOf(char) + 1)
483 compareWeights = (minDiff, a, b) ->
484 diff = a.weight - b.weight
485 if a instanceof huffman.BranchPoint or b instanceof huffman.BranchPoint
489 when diff <= -minDiff
496 module.exports = MarkerContainer