]> git.gir.st - VimFx.git/blob - extension/lib/hints.coffee
Fix blacklisting on already loaded tabs
[VimFx.git] / extension / lib / 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 # This file contains functions for getting markable elements, and related data,
22 # as well as for creating and inserting markers for markable elements.
23
24 huffman = require('n-ary-huffman')
25 { Marker } = require('./marker')
26 utils = require('./utils')
27
28 CONTAINER_ID = 'VimFxMarkersContainer'
29
30 Element = Ci.nsIDOMElement
31 XULDocument = Ci.nsIDOMXULDocument
32
33 # Create `Marker`s for every element (represented by a regular object of data
34 # about the element—a “wrapper,” a stand-in for the real element, which is only
35 # accessible in frame scripts) in `wrappers`, and insert them into `window`.
36 injectHints = (window, wrappers, viewport, options) ->
37 semantic = []
38 unsemantic = []
39 combined = []
40 markerMap = {}
41
42 for wrapper in wrappers
43 marker = new Marker(wrapper, window.document)
44 group = switch
45 when wrapper.parentIndex? then combined
46 when wrapper.semantic then semantic
47 else unsemantic
48 group.push(marker)
49 markerMap[wrapper.elementIndex] = marker
50
51 markers = semantic.concat(unsemantic)
52
53 return [[], null] if markers.length == 0
54
55 # Each marker gets a unique `z-index`, so that it can be determined if a
56 # marker overlaps another. Put more important markers (higher weight) at the
57 # end, so that they get higher `z-index`, in order not to be overlapped.
58 zIndex = 0
59 setZIndexes = (markers) ->
60 markers.sort((a, b) -> a.weight - b.weight)
61 for marker in markers when marker not instanceof huffman.BranchPoint
62 marker.markerElement.style.zIndex = zIndex++
63 # Add `z-index` space for all the children of the marker.
64 zIndex += marker.wrapper.numChildren if marker.wrapper.numChildren?
65
66 # The `markers` passed to this function have been sorted by `setZIndexes` in
67 # advance, so we can skip sorting in the `huffman.createTree` function.
68 hintChars = options.hint_chars
69 createHuffmanTree = (markers) ->
70 return huffman.createTree(markers, hintChars.length, {sorted: true})
71
72 # Semantic elements should always get better hints and higher `z-index`:es
73 # than unsemantic ones, even if they are smaller. The former is achieved by
74 # putting the unsemantic elements in their own branch of the huffman tree.
75 if unsemantic.length > 0
76 if markers.length > hintChars.length
77 setZIndexes(unsemantic)
78 subTree = createHuffmanTree(unsemantic)
79 semantic.push(subTree)
80 else
81 semantic.push(unsemantic...)
82
83 setZIndexes(semantic)
84
85 tree = createHuffmanTree(semantic)
86 tree.assignCodeWords(hintChars, (marker, hint) -> marker.setHint(hint))
87
88 # Markers for links with the same href can be combined to use the same hint.
89 # They should all have the same `z-index` (because they all have the same
90 # combined weight), but in case any of them cover another they still get a
91 # unique `z-index` (space for this was added in `setZIndexes`).
92 for marker in combined
93 parent = markerMap[marker.wrapper.parentIndex]
94 marker.markerElement.style.zIndex = parent.markerElement.style.zIndex++
95 marker.setHint(parent.hint)
96 markers.push(combined...)
97
98 container = window.document.createElement('box')
99 container.id = CONTAINER_ID
100 window.gBrowser.mCurrentBrowser.parentNode.appendChild(container)
101
102 zoom = window.ZoomManager.getZoomForBrowser(window.gBrowser.selectedBrowser)
103 for marker in markers
104 container.appendChild(marker.markerElement)
105 # Must be done after the hints have been inserted into the DOM (see
106 # marker.coffee).
107 marker.setPosition(viewport, zoom)
108
109 return [markers, container]
110
111
112 getMarkableElementsAndViewport = (window, filter) ->
113 {
114 clientWidth, clientHeight # Viewport size excluding scrollbars, usually.
115 scrollWidth, scrollHeight
116 } = window.document.documentElement
117 { innerWidth, innerHeight } = window # Viewport size including scrollbars.
118 # We don’t want markers to cover the scrollbars, so we should use
119 # `clientWidth` and `clientHeight`. However, when there are no scrollbars
120 # those might be too small. Then we use `innerWidth` and `innerHeight`.
121 width = if scrollWidth > innerWidth then clientWidth else innerWidth
122 height = if scrollHeight > innerHeight then clientHeight else innerHeight
123 viewport = {
124 left: 0
125 top: 0
126 right: width
127 bottom: height
128 width
129 height
130 }
131
132 wrappers = []
133 getMarkableElements(window, viewport, wrappers, filter)
134 return {wrappers, viewport}
135
136 # `filter` is a function that is given every element in every frame of the page.
137 # It should return wrapper objects for markable elements and a falsy value for
138 # all other elements. All returned wrappers are added to `wrappers`. `wrappers`
139 # is modified instead of using return values to avoid array concatenation for
140 # each frame. It might sound expensive to go through _every_ element, but that’s
141 # actually what other methods like using XPath or CSS selectors would need to do
142 # anyway behind the scenes.
143 getMarkableElements = (window, viewport, wrappers, filter, parents = []) ->
144 { document } = window
145
146 localGetElementShape = getElementShape.bind(null, window, viewport, parents)
147 for element in getElements(document, viewport) when element instanceof Element
148 continue unless wrapper = filter(element, localGetElementShape)
149 wrappers.push(wrapper)
150
151 for frame in window.frames
152 rect = frame.frameElement.getBoundingClientRect() # Frames only have one.
153 continue unless isInsideViewport(rect, viewport)
154
155 # Calculate the visible part of the frame, according to the parent.
156 { clientWidth, clientHeight } = frame.document.documentElement
157 frameViewport =
158 left: Math.max(viewport.left - rect.left, 0)
159 top: Math.max(viewport.top - rect.top, 0)
160 right: clientWidth + Math.min(viewport.right - rect.right, 0)
161 bottom: clientHeight + Math.min(viewport.bottom - rect.bottom, 0)
162
163 # `.getComputedStyle()` may return `null` if the computed style isn’t
164 # availble yet. If so, consider the element not visible.
165 continue unless computedStyle = window.getComputedStyle(frame.frameElement)
166 offset =
167 left: rect.left +
168 parseFloat(computedStyle.getPropertyValue('border-left-width')) +
169 parseFloat(computedStyle.getPropertyValue('padding-left'))
170 top: rect.top +
171 parseFloat(computedStyle.getPropertyValue('border-top-width')) +
172 parseFloat(computedStyle.getPropertyValue('padding-top'))
173
174 getMarkableElements(frame, frameViewport, wrappers, filter,
175 parents.concat({ window, offset }))
176
177 return
178
179 # Returns a suitable set of elements in `document` that could possibly get
180 # markers.
181 getElements = (document, viewport) ->
182 # In XUL documents we have to resort to get every single element in the entire
183 # document, because there are lots of complicated “anonymous” elements, which
184 # `windowUtils.nodesFromRect()` does not catch.
185 if document instanceof XULDocument
186 elements = []
187 getAllRegular = (element) ->
188 for child in element.getElementsByTagName('*')
189 elements.push(child)
190 getAllAnonymous(child)
191 return
192 getAllAnonymous = (element) ->
193 for child in document.getAnonymousNodes(element) or []
194 continue unless child instanceof Element
195 elements.push(child)
196 getAllRegular(child)
197 return
198 getAllRegular(document.documentElement)
199 return elements
200 # In other documents we can use a super-fast Firefox API to get all elements
201 # in the viewport.
202 else
203 windowUtils = document.defaultView
204 .QueryInterface(Ci.nsIInterfaceRequestor)
205 .getInterface(Ci.nsIDOMWindowUtils)
206 return windowUtils.nodesFromRect(
207 viewport.left, viewport.top, # Rect coordinates, relative to the viewport.
208 # Distances to expand in all directions: top, right, bottom, left.
209 0, viewport.right, viewport.bottom, 0,
210 true, # Unsure what this does. Toggling it seems to make no difference.
211 true # Ensure that the list of matching elements is fully up to date.
212 )
213
214 # Returns the “shape” of `element`:
215 #
216 # - `nonCoveredPoint`: The coordinates of the first point of `element` that
217 # isn’t covered by another element (except children of `element`). It also
218 # contains the offset needed to make those coordinates relative to the top
219 # frame, as well as the rectangle that the coordinates occur in.
220 # - `area`: The area of the part of `element` that is inside `viewport`.
221 #
222 # Returns `null` if `element` is outside `viewport` or entirely covered by other
223 # elements.
224 getElementShape = (window, viewport, parents, element) ->
225 # `element.getClientRects()` returns a list of rectangles, usually just one,
226 # which is identical to the one returned by `element.getBoundingClientRect()`.
227 # However, if `element` is inline and line-wrapped, then it returns one
228 # rectangle for each line, since each line may be of different length, for
229 # example. That allows us to properly add hints to line-wrapped links.
230 rects = element.getClientRects()
231 totalArea = 0
232 visibleRects = []
233 # The `isInsideViewport` check is not needed in HTML documents, but in XUL
234 # documents (see `getElements()`). However, there seems to be no performance
235 # gain in not running the check in HTML documents, so let’s keep it simple.
236 for rect in rects when isInsideViewport(rect, viewport)
237 visibleRect = adjustRectToViewport(rect, viewport)
238 continue if visibleRect.area == 0
239 totalArea += visibleRect.area
240 visibleRects.push(visibleRect)
241
242 if visibleRects.length == 0
243 if rects.length == 1 and totalArea == 0
244 [ rect ] = rects
245 if rect.width > 0 or rect.height > 0
246 # If we get here, it means that everything inside `element` is floated
247 # and/or absolutely positioned (and that `element` hasn’t been made to
248 # “contain” the floats). For example, a link in a menu could contain a
249 # span of text floated to the left and an icon floated to the right.
250 # Those are still clickable. Therefore we return the shape of the first
251 # visible child instead. At least in that example, that’s the best bet.
252 for child in element.children
253 shape = getElementShape(window, viewport, parents, child)
254 return shape if shape
255 return null
256
257 # Even if `element` has a visible rect, it might be covered by other elements.
258 for visibleRect in visibleRects
259 nonCoveredPoint = getFirstNonCoveredPoint(window, viewport, element,
260 visibleRect, parents)
261 if nonCoveredPoint
262 nonCoveredPoint.rect = visibleRect
263 break
264
265 return null unless nonCoveredPoint
266
267 return {
268 nonCoveredPoint, area: totalArea
269 }
270
271
272 MINIMUM_EDGE_DISTANCE = 4
273 isInsideViewport = (rect, viewport) ->
274 return \
275 rect.left <= viewport.right - MINIMUM_EDGE_DISTANCE and
276 rect.top <= viewport.bottom + MINIMUM_EDGE_DISTANCE and
277 rect.right >= viewport.left + MINIMUM_EDGE_DISTANCE and
278 rect.bottom >= viewport.top - MINIMUM_EDGE_DISTANCE
279
280
281 adjustRectToViewport = (rect, viewport) ->
282 # The right and bottom values are subtracted by 1 because
283 # `document.elementFromPoint(right, bottom)` does not return the element
284 # otherwise.
285 left = Math.max(rect.left, viewport.left)
286 right = Math.min(rect.right - 1, viewport.right)
287 top = Math.max(rect.top, viewport.top)
288 bottom = Math.min(rect.bottom - 1, viewport.bottom)
289
290 # Make sure that `right >= left and bottom >= top`, since we subtracted by 1
291 # above.
292 right = Math.max(right, left)
293 bottom = Math.max(bottom, top)
294
295 width = right - left
296 height = bottom - top
297 area = Math.floor(width * height)
298
299 return {
300 left, right, top, bottom
301 height, width, area
302 }
303
304
305 getFirstNonCoveredPoint = (window, viewport, element, elementRect, parents) ->
306 # Tries a point `(x + dx, y + dy)`. Returns `(x, y)` (and the frame offset)
307 # if it passes the tests. Otherwise it tries to the right of whatever is at
308 # `(x, y)`, `tryRight` times . If nothing succeeds, `false` is returned. `dx`
309 # and `dy` are used to offset the wanted point `(x, y)` while trying (see the
310 # invocations of `tryPoint` below).
311 tryPoint = (x, dx, y, dy, tryRight = 0) ->
312 elementAtPoint = window.document.elementFromPoint(x + dx, y + dy)
313 offset = {left: 0, top: 0}
314 found = false
315
316 # Ensure that `element`, or a child of `element` (anything inside an `<a>`
317 # is clickable too), really is present at (x,y). Note that this is not 100%
318 # bullet proof: Combinations of CSS can cause this check to fail, even
319 # though `element` isn’t covered. We don’t try to temporarily reset such CSS
320 # because of performance. Instead we rely on that some of the attempts below
321 # will work.
322 if element.contains(elementAtPoint) or # Note that `a.contains(a) == true`!
323 (window.document instanceof XULDocument and
324 getClosestNonAnonymousParent(element) == elementAtPoint)
325 found = true
326 # If we’re currently in a frame, there might be something on top of the
327 # frame that covers `element`. Therefore we ensure that the frame really
328 # is present at the point for each parent in `parents`.
329 currentWindow = window
330 for parent in parents by -1
331 offset.left += parent.offset.left
332 offset.top += parent.offset.top
333 elementAtPoint = parent.window.document.elementFromPoint(
334 offset.left + x + dx, offset.top + y + dy
335 )
336 unless elementAtPoint == currentWindow.frameElement
337 found = false
338 break
339 currentWindow = parent.window
340
341 if found
342 return {x, y, offset}
343 else
344 return false if elementAtPoint == null or tryRight == 0
345 rect = elementAtPoint.getBoundingClientRect()
346 x = rect.right - offset.left + 1
347 return false if x > viewport.right
348 return tryPoint(x, 0, y, 0, tryRight - 1)
349
350
351 # Try the left-middle point, or immediately to the right of a covering element
352 # at that point. If both of those are covered the whole element is considered
353 # to be covered. The reasoning is:
354 #
355 # - A marker should show up as near the left edge of its visible area as
356 # possible. Having it appear to the far right (for example) is confusing.
357 # - We can’t try too many times because of performance.
358 # - We used to try left-top first, but if `element` has `border-radius`, the
359 # corners won’t really belong to `element`, so `document.elementFromPoint()`
360 # will return whatever is behind. This will result in missing or
361 # out-of-place markers. The solution is to temporarily add a CSS class that
362 # removes `border-radius`, but that turned out to be rather slow, making it
363 # not worth it. Usually you don’t see the difference between left-top and
364 # left-middle, because links are usually not that high.
365 # - We used to try left-bottom as well, but that is so rare that it’s not
366 # worth it.
367 #
368 # It is safer to try points at least one pixel into the element from the
369 # edges, hence the `+1`.
370 { left, top, bottom, height } = elementRect
371 nonCoveredPoint = tryPoint(left, +1, Math.floor(top + height / 2), 0, 1)
372
373 return nonCoveredPoint
374
375 # In XUL documents there are “anonymous” elements, whose node names start with
376 # `xul:` or `html:`. These are never returned by `document.elementFromPoint` but
377 # their closest non-anonymous parents are.
378 getClosestNonAnonymousParent = (element) ->
379 element = element.parentNode while element.prefix?
380 return element
381
382 module.exports = {
383 injectHints
384 getMarkableElementsAndViewport
385 }
Imprint / Impressum