]> git.gir.st - VimFx.git/blob - extension/lib/mode-hints/hints.coffee
Remove bloomfilter
[VimFx.git] / extension / lib / mode-hints / hints.coffee
1 ###
2 # Copyright Anton Khodakivskiy 2012, 2013.
3 # Copyright Simon Lydell 2013, 2014.
4 #
5 # This file is part of VimFx.
6 #
7 # VimFx is free software: you can redistribute it and/or modify
8 # it under the terms of the GNU General Public License as published by
9 # the Free Software Foundation, either version 3 of the License, or
10 # (at your option) any later version.
11 #
12 # VimFx is distributed in the hope that it will be useful,
13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 # GNU General Public License for more details.
16 #
17 # You should have received a copy of the GNU General Public License
18 # along with VimFx. If not, see <http://www.gnu.org/licenses/>.
19 ###
20
21 utils = require('../utils')
22 { Marker } = require('./marker')
23 huffman = require('n-ary-huffman')
24
25 { interfaces: Ci } = Components
26
27 HTMLDocument = Ci.nsIDOMHTMLDocument
28 XULDocument = Ci.nsIDOMXULDocument
29
30 CONTAINER_ID = 'VimFxHintMarkerContainer'
31 Z_INDEX_START = 2147480001 # The highest `z-index` used in style.css plus one.
32 # In theory, `z-index` can be infinitely large. In practice, Firefox uses a
33 # 32-bit signed integer to store it, so the maximum value is 2147483647
34 # (http://www.puidokas.com/max-z-index/). Youtube (insanely) uses 1999999999 for
35 # its top bar. So by using 2147480001 as a base, we trump that value with lots
36 # of margin, still leaving a few thousand values for markers, which should be
37 # more than enough. Hopefully no sites are crazy enough to use even higher
38 # values.
39
40
41 removeHints = (document) ->
42 document.getElementById(CONTAINER_ID)?.remove()
43
44
45 injectHints = (window) ->
46 { document } = window
47
48 { clientWidth, clientHeight } = document.documentElement
49 viewport =
50 left: 0
51 top: 0
52 right: clientWidth
53 bottom: clientHeight
54 width: clientWidth
55 height: clientHeight
56 scrollX: window.scrollX
57 scrollY: window.scrollY
58 markers = createMarkers(window, viewport)
59
60 return if markers.length == 0
61
62 # Each marker gets a unique `z-index`, so that it can be determined if a
63 # marker overlaps another. Put more important markers (higher weight) at the
64 # end, so that they get higher `z-index`, in order not to be overlapped.
65 zIndex = Z_INDEX_START
66 setZIndexes = (markers) ->
67 markers.sort((a, b) -> a.weight - b.weight)
68 for marker in markers when marker not instanceof huffman.BranchPoint
69 marker.markerElement.style.setProperty('z-index', zIndex++, 'important')
70
71 # The `markers` passed to this function have been sorted by `setZIndexes` in
72 # advance, so we can skip sorting in the `huffman.createTree` function.
73 hintChars = utils.getHintChars()
74 createHuffmanTree = (markers) ->
75 return huffman.createTree(markers, hintChars.length, {sorted: true})
76
77 semantic = []
78 unsemantic = []
79 for marker in markers
80 marker.weight = marker.elementShape.area
81 if utils.isElementClickable(marker.element)
82 semantic.push(marker)
83 else
84 unsemantic.push(marker)
85
86 # Semantic elements should always get better hints than unsemantic ones, even
87 # if they are smaller. This is achieved by putting the unsemantic elements in
88 # their own branch of the huffman tree.
89 if unsemantic.length > 0
90 if markers.length > hintChars.length
91 setZIndexes(unsemantic)
92 subTree = createHuffmanTree(unsemantic)
93 semantic.push(subTree)
94 else
95 semantic.push(unsemantic...)
96
97 setZIndexes(semantic)
98
99 tree = createHuffmanTree(semantic)
100 tree.assignCodeWords(hintChars, (marker, hint) -> marker.setHint(hint))
101
102 removeHints(document)
103 container = utils.createElement(document, 'div', {id: CONTAINER_ID})
104 document.documentElement.appendChild(container)
105
106 for marker in markers
107 container.appendChild(marker.markerElement)
108 # Must be done after the hints have been inserted into the DOM (see
109 # marker.coffee).
110 marker.setPosition(viewport)
111
112 return markers
113
114 createMarkers = (window, viewport, parents = []) ->
115 { document } = window
116 markers = []
117
118 # For now we aren't able to handle hint markers in XUL Documents :(
119 return [] unless document instanceof HTMLDocument
120
121 candidates = utils.getMarkableElements(document, {type: 'all'})
122 for element in candidates
123 shape = getElementShape(window, element, viewport, parents)
124 # If `element` has no visible shape then it shouldn’t get any marker.
125 continue unless shape
126
127 markers.push(new Marker(element, shape))
128
129 for frame in window.frames
130 rect = frame.frameElement.getBoundingClientRect() # Frames only have one.
131 continue unless isInsideViewport(rect, viewport)
132
133 # Calculate the visible part of the frame, according to the parent.
134 { clientWidth, clientHeight } = frame.document.documentElement
135 frameViewport =
136 left: Math.max(viewport.left - rect.left, 0)
137 top: Math.max(viewport.top - rect.top, 0)
138 right: clientWidth + Math.min(viewport.right - rect.right, 0)
139 bottom: clientHeight + Math.min(viewport.bottom - rect.bottom, 0)
140
141 # `.getComputedStyle()` may return `null` if the computed style isn’t
142 # availble yet. If so, consider the element not visible.
143 continue unless computedStyle = window.getComputedStyle(frame.frameElement)
144 offset =
145 left: rect.left +
146 parseFloat(computedStyle.getPropertyValue('border-left-width')) +
147 parseFloat(computedStyle.getPropertyValue('padding-left'))
148 top: rect.top +
149 parseFloat(computedStyle.getPropertyValue('border-top-width')) +
150 parseFloat(computedStyle.getPropertyValue('padding-top'))
151
152 frameMarkers = createMarkers(frame, frameViewport,
153 parents.concat({ window, offset }))
154 markers.push(frameMarkers...)
155
156 return markers
157
158 # Returns the “shape” of `element`:
159 #
160 # - `rects`: Its `.getClientRects()` rectangles.
161 # - `visibleRects`: The parts of rectangles out of the above that are inside
162 # `viewport`.
163 # - `nonCoveredPoint`: The coordinates of the first point of `element` that
164 # isn’t covered by another element (except children of `element`). It also
165 # contains the offset needed to make those coordinates relative to the top
166 # frame, as well as the rectangle that the coordinates occur in.
167 # - `area`: The area of the part of `element` that is inside `viewport`.
168 #
169 # Returns `null` if `element` is outside `viewport` or entirely covered by other
170 # elements.
171 getElementShape = (window, element, viewport, parents) ->
172 # `element.getClientRects()` returns a list of rectangles, usually just one,
173 # which is identical to the one returned by `element.getBoundingClientRect()`.
174 # However, if `element` is inline and line-wrapped, then it returns one
175 # rectangle for each line, since each line may be of different length, for
176 # example. That allows us to properly add hints to line-wrapped links.
177 rects = element.getClientRects()
178 totalArea = 0
179 visibleRects = []
180 for rect in rects when isInsideViewport(rect, viewport)
181 visibleRect = adjustRectToViewport(rect, viewport)
182 continue if visibleRect.area == 0
183 totalArea += visibleRect.area
184 visibleRects.push(visibleRect)
185
186 if visibleRects.length == 0
187 if rects.length == 1 and totalArea == 0
188 [ rect ] = rects
189 if rect.width > 0 or rect.height > 0
190 # If we get here, it means that everything inside `element` is floated
191 # and/or absolutely positioned (and that `element` hasn’t been made to
192 # “contain” the floats). For example, a link in a menu could contain a
193 # span of text floated to the left and an icon floated to the right.
194 # Those are still clickable. Therefore we return the shape of the first
195 # visible child instead. At least in that example, that’s the best bet.
196 for child in element.children
197 shape = getElementShape(window, child, viewport, parents)
198 return shape if shape
199 return null
200
201
202 # Even if `element` has a visible rect, it might be covered by other elements.
203 for visibleRect in visibleRects
204 nonCoveredPoint = getFirstNonCoveredPoint(window, viewport, element,
205 visibleRect, parents)
206 if nonCoveredPoint
207 nonCoveredPoint.rect = visibleRect
208 break
209
210 return null unless nonCoveredPoint
211
212 return {
213 rects, visibleRects, nonCoveredPoint, area: totalArea
214 }
215
216
217 MINIMUM_EDGE_DISTANCE = 4
218 isInsideViewport = (rect, viewport) ->
219 return \
220 rect.left <= viewport.right - MINIMUM_EDGE_DISTANCE and
221 rect.top <= viewport.bottom + MINIMUM_EDGE_DISTANCE and
222 rect.right >= viewport.left + MINIMUM_EDGE_DISTANCE and
223 rect.bottom >= viewport.top - MINIMUM_EDGE_DISTANCE
224
225
226 adjustRectToViewport = (rect, viewport) ->
227 # The right and bottom values are subtracted by 1 because
228 # `document.elementFromPoint(right, bottom)` does not return the element
229 # otherwise.
230 left = Math.max(rect.left, viewport.left)
231 right = Math.min(rect.right - 1, viewport.right)
232 top = Math.max(rect.top, viewport.top)
233 bottom = Math.min(rect.bottom - 1, viewport.bottom)
234
235 # Make sure that `right >= left and bottom >= top`, since we subtracted by 1
236 # above.
237 right = Math.max(right, left)
238 bottom = Math.max(bottom, top)
239
240 width = right - left
241 height = bottom - top
242 area = Math.floor(width * height)
243
244 return {
245 left, right, top, bottom
246 height, width, area
247 }
248
249
250 getFirstNonCoveredPoint = (window, viewport, element, elementRect, parents) ->
251 # Before we start we need to hack around a little problem. If `element` has
252 # `border-radius`, the corners won’t really belong to `element`, so
253 # `document.elementFromPoint()` will return whatever is behind. This will
254 # result in missing or out-of-place markers. The solution is to temporarily
255 # add a CSS class that removes `border-radius`.
256 element.classList.add('VimFxNoBorderRadius')
257
258 # Tries a point `(x + dx, y + dy)`. Returns `(x, y)` (and the frame offset)
259 # if it passes the tests. Otherwise it tries to the right of whatever is at
260 # `(x, y)`, `tryRight` times . If nothing succeeds, `false` is returned. `dx`
261 # and `dy` are used to offset the wanted point `(x, y)` while trying (see the
262 # invocations of `tryPoint` below).
263 tryPoint = (x, dx, y, dy, tryRight = 0) ->
264 elementAtPoint = window.document.elementFromPoint(x + dx, y + dy)
265 offset = {left: 0, top: 0}
266 found = false
267
268 # Ensure that `element`, or a child of `element` (anything inside an `<a>`
269 # is clickable too), really is present at (x,y). Note that this is not 100%
270 # bullet proof: Combinations of CSS can cause this check to fail, even
271 # though `element` isn’t covered. We don’t try to temporarily reset such CSS
272 # (as with `border-radius`) because of performance. Instead we rely on that
273 # some of the attempts below will work.
274 if element.contains(elementAtPoint) # Note that `a.contains(a) == true`!
275 found = true
276 # If we’re currently in a frame, there might be something on top of the
277 # frame that covers `element`. Therefore we ensure that the frame really
278 # is present at the point for each parent in `parents`.
279 currentWindow = window
280 for parent in parents by -1
281 offset.left += parent.offset.left
282 offset.top += parent.offset.top
283 elementAtPoint = parent.window.document.elementFromPoint(
284 offset.left + x + dx, offset.top + y + dy
285 )
286 unless elementAtPoint == currentWindow.frameElement
287 found = false
288 break
289 currentWindow = parent.window
290
291 if found
292 return {x, y, offset}
293 else
294 return false if elementAtPoint == null or tryRight == 0
295 rect = elementAtPoint.getBoundingClientRect()
296 x = rect.right - offset.left + 1
297 return false if x > viewport.right
298 return tryPoint(x, 0, y, 0, tryRight - 1)
299
300
301 # Try the following 3 positions, or immediately to the right of a covering
302 # element at one of those positions, in order. If all of those are covered the
303 # whole element is considered to be covered. The reasoning is:
304 #
305 # - A marker should show up as near the left edge of its visible area as
306 # possible. Having it appear to the far right (for example) is confusing.
307 # - We can’t try too many times because of performance.
308 #
309 # +-------------------------------+
310 # |1 left-top |
311 # | |
312 # |2 left-middle |
313 # | |
314 # |3 left-bottom |
315 # +-------------------------------+
316 #
317 # It is safer to try points at least one pixel into the element from the
318 # edges, hence the `+1`s and `-1`s.
319 { left, top, bottom, height } = elementRect
320 nonCoveredPoint =
321 tryPoint(left, +1, top, +1, 1) or
322 tryPoint(left, +1, top + height / 2, 0, 1) or
323 tryPoint(left, +1, bottom, -1, 1)
324
325 element.classList.remove('VimFxNoBorderRadius')
326
327 return nonCoveredPoint
328
329
330 # Finds all stacks of markers that overlap each other (by using `getStackFor`)
331 # (#1), and rotates their `z-index`:es (#2), thus alternating which markers are
332 # visible.
333 rotateOverlappingMarkers = (originalMarkers, forward) ->
334 # Shallow working copy. This is necessary since `markers` will be mutated and
335 # eventually empty.
336 markers = originalMarkers[..]
337
338 # (#1)
339 stacks = (getStackFor(markers.pop(), markers) while markers.length > 0)
340
341 # (#2)
342 # Stacks of length 1 don't participate in any overlapping, and can therefore
343 # be skipped.
344 for stack in stacks when stack.length > 1
345 # This sort is not required, but makes the rotation more predictable.
346 stack.sort((a, b) -> a.markerElement.style.zIndex -
347 b.markerElement.style.zIndex)
348
349 # Array of z-indices.
350 indexStack = (marker.markerElement.style.zIndex for marker in stack)
351 # Shift the array of indices one item forward or back.
352 if forward
353 indexStack.unshift(indexStack.pop())
354 else
355 indexStack.push(indexStack.shift())
356
357 for marker, index in stack
358 marker.markerElement.style.setProperty('z-index', indexStack[index],
359 'important')
360
361 return
362
363 # Get an array containing `marker` and all markers that overlap `marker`, if
364 # any, which is called a "stack". All markers in the returned stack are spliced
365 # out from `markers`, thus mutating it.
366 getStackFor = (marker, markers) ->
367 stack = [marker]
368
369 { top, bottom, left, right } = marker.position
370
371 index = 0
372 while index < markers.length
373 nextMarker = markers[index]
374
375 next = nextMarker.position
376 overlapsVertically = (next.bottom >= top and next.top <= bottom)
377 overlapsHorizontally = (next.right >= left and next.left <= right)
378
379 if overlapsVertically and overlapsHorizontally
380 # Also get all markers overlapping this one.
381 markers.splice(index, 1)
382 stack = stack.concat(getStackFor(nextMarker, markers))
383 else
384 # Continue the search.
385 index++
386
387 return stack
388
389
390 exports.injectHints = injectHints
391 exports.removeHints = removeHints
392 exports.rotateOverlappingMarkers = rotateOverlappingMarkers
Imprint / Impressum