]> git.gir.st - VimFx.git/blob - extension/lib/hints.coffee
Fix #60: Give the same hint to links with the same URL
[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 utils = require('./utils')
22 huffman = require('n-ary-huffman')
23
24 { interfaces: Ci } = Components
25
26 XULDocument = Ci.nsIDOMXULDocument
27
28 injectHints = (rootWindow, window, filter) ->
29 {
30 clientWidth, clientHeight # Viewport size excluding scrollbars, usually.
31 scrollWidth, scrollHeight
32 } = window.document.documentElement
33 { innerWidth, innerHeight } = window # Viewport size including scrollbars.
34 # We don’t want markers to cover the scrollbars, so we should use
35 # `clientWidth` and `clientHeight`. However, when there are no scrollbars
36 # those might be too small. Then we use `innerWidth` and `innerHeight`.
37 width = if scrollWidth > innerWidth then clientWidth else innerWidth
38 height = if scrollHeight > innerHeight then clientHeight else innerHeight
39 viewport = {
40 left: 0
41 top: 0
42 right: width
43 bottom: height
44 width
45 height
46 }
47
48 groups = {semantic: [], unsemantic: [], combined: []}
49 createMarkers(window, viewport, groups, filter)
50 { semantic, unsemantic, combined } = groups
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 (usually 0).
64 zIndex += marker.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 = utils.getHintChars()
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 latter 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 } = marker
94 marker.markerElement.style.zIndex = parent.markerElement.style.zIndex++
95 marker.setHint(parent.hint)
96 markers.push(combined...)
97
98 container = rootWindow.document.createElement('box')
99 container.classList.add('VimFxMarkersContainer')
100 rootWindow.gBrowser.mCurrentBrowser.parentNode.appendChild(container)
101
102 for marker in markers
103 container.appendChild(marker.markerElement)
104 # Must be done after the hints have been inserted into the DOM (see
105 # marker.coffee).
106 marker.setPosition(viewport)
107
108 return [markers, container]
109
110 # `filter` is a function that is given every element in every frame of the page.
111 # It should return new `Marker`s for markable elements and a falsy value for all
112 # other elements. All returned `Marker`s are added to `groups`. `groups` is
113 # modified instead of using return values to avoid array concatenation for each
114 # frame. It might sound expensive to go through _every_ element, but that’s
115 # actually what other methods like using XPath or CSS selectors would need to do
116 # anyway behind the scenes.
117 createMarkers = (window, viewport, groups, filter, parents = []) ->
118 { document } = window
119
120 localGetElementShape = getElementShape.bind(null, window, viewport, parents)
121 for element in utils.getAllElements(document)
122 continue unless marker = filter(element, localGetElementShape)
123 if marker.parent
124 groups.combined.push(marker)
125 else if marker.semantic
126 groups.semantic.push(marker)
127 else
128 groups.unsemantic.push(marker)
129
130 for frame in window.frames
131 rect = frame.frameElement.getBoundingClientRect() # Frames only have one.
132 continue unless isInsideViewport(rect, viewport)
133
134 # Calculate the visible part of the frame, according to the parent.
135 { clientWidth, clientHeight } = frame.document.documentElement
136 frameViewport =
137 left: Math.max(viewport.left - rect.left, 0)
138 top: Math.max(viewport.top - rect.top, 0)
139 right: clientWidth + Math.min(viewport.right - rect.right, 0)
140 bottom: clientHeight + Math.min(viewport.bottom - rect.bottom, 0)
141
142 # `.getComputedStyle()` may return `null` if the computed style isn’t
143 # availble yet. If so, consider the element not visible.
144 continue unless computedStyle = window.getComputedStyle(frame.frameElement)
145 offset =
146 left: rect.left +
147 parseFloat(computedStyle.getPropertyValue('border-left-width')) +
148 parseFloat(computedStyle.getPropertyValue('padding-left'))
149 top: rect.top +
150 parseFloat(computedStyle.getPropertyValue('border-top-width')) +
151 parseFloat(computedStyle.getPropertyValue('padding-top'))
152
153 createMarkers(frame, frameViewport, groups, filter,
154 parents.concat({ window, offset }))
155
156 return
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, viewport, parents, element) ->
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, viewport, parents, child)
198 return shape if shape
199 return null
200
201 # Even if `element` has a visible rect, it might be covered by other elements.
202 for visibleRect in visibleRects
203 nonCoveredPoint = getFirstNonCoveredPoint(window, viewport, element,
204 visibleRect, parents)
205 if nonCoveredPoint
206 nonCoveredPoint.rect = visibleRect
207 break
208
209 return null unless nonCoveredPoint
210
211 return {
212 rects, visibleRects, nonCoveredPoint, area: totalArea
213 }
214
215
216 MINIMUM_EDGE_DISTANCE = 4
217 isInsideViewport = (rect, viewport) ->
218 return \
219 rect.left <= viewport.right - MINIMUM_EDGE_DISTANCE and
220 rect.top <= viewport.bottom + MINIMUM_EDGE_DISTANCE and
221 rect.right >= viewport.left + MINIMUM_EDGE_DISTANCE and
222 rect.bottom >= viewport.top - MINIMUM_EDGE_DISTANCE
223
224
225 adjustRectToViewport = (rect, viewport) ->
226 # The right and bottom values are subtracted by 1 because
227 # `document.elementFromPoint(right, bottom)` does not return the element
228 # otherwise.
229 left = Math.max(rect.left, viewport.left)
230 right = Math.min(rect.right - 1, viewport.right)
231 top = Math.max(rect.top, viewport.top)
232 bottom = Math.min(rect.bottom - 1, viewport.bottom)
233
234 # Make sure that `right >= left and bottom >= top`, since we subtracted by 1
235 # above.
236 right = Math.max(right, left)
237 bottom = Math.max(bottom, top)
238
239 width = right - left
240 height = bottom - top
241 area = Math.floor(width * height)
242
243 return {
244 left, right, top, bottom
245 height, width, area
246 }
247
248
249 getFirstNonCoveredPoint = (window, viewport, element, elementRect, parents) ->
250 # Before we start we need to hack around a little problem. If `element` has
251 # `border-radius`, the corners won’t really belong to `element`, so
252 # `document.elementFromPoint()` will return whatever is behind. This will
253 # result in missing or out-of-place markers. The solution is to temporarily
254 # add a CSS class that removes `border-radius`.
255 element.classList.add('VimFxNoBorderRadius')
256
257 # Tries a point `(x + dx, y + dy)`. Returns `(x, y)` (and the frame offset)
258 # if it passes the tests. Otherwise it tries to the right of whatever is at
259 # `(x, y)`, `tryRight` times . If nothing succeeds, `false` is returned. `dx`
260 # and `dy` are used to offset the wanted point `(x, y)` while trying (see the
261 # invocations of `tryPoint` below).
262 tryPoint = (x, dx, y, dy, tryRight = 0) ->
263 elementAtPoint = window.document.elementFromPoint(x + dx, y + dy)
264 offset = {left: 0, top: 0}
265 found = false
266
267 # Ensure that `element`, or a child of `element` (anything inside an `<a>`
268 # is clickable too), really is present at (x,y). Note that this is not 100%
269 # bullet proof: Combinations of CSS can cause this check to fail, even
270 # though `element` isn’t covered. We don’t try to temporarily reset such CSS
271 # (as with `border-radius`) because of performance. Instead we rely on that
272 # some of the attempts below will work.
273 if element.contains(elementAtPoint) or # Note that `a.contains(a) == true`!
274 (window.document instanceof XULDocument and
275 getClosestNonAnonymousParent(element) == elementAtPoint)
276 found = true
277 # If we’re currently in a frame, there might be something on top of the
278 # frame that covers `element`. Therefore we ensure that the frame really
279 # is present at the point for each parent in `parents`.
280 currentWindow = window
281 for parent in parents by -1
282 offset.left += parent.offset.left
283 offset.top += parent.offset.top
284 elementAtPoint = parent.window.document.elementFromPoint(
285 offset.left + x + dx, offset.top + y + dy
286 )
287 unless elementAtPoint == currentWindow.frameElement
288 found = false
289 break
290 currentWindow = parent.window
291
292 if found
293 return {x, y, offset}
294 else
295 return false if elementAtPoint == null or tryRight == 0
296 rect = elementAtPoint.getBoundingClientRect()
297 x = rect.right - offset.left + 1
298 return false if x > viewport.right
299 return tryPoint(x, 0, y, 0, tryRight - 1)
300
301
302 # Try the following 3 positions, or immediately to the right of a covering
303 # element at one of those positions, in order. If all of those are covered the
304 # whole element is considered to be covered. The reasoning is:
305 #
306 # - A marker should show up as near the left edge of its visible area as
307 # possible. Having it appear to the far right (for example) is confusing.
308 # - We can’t try too many times because of performance.
309 #
310 # +-------------------------------+
311 # |1 left-top |
312 # | |
313 # |2 left-middle |
314 # | |
315 # |3 left-bottom |
316 # +-------------------------------+
317 #
318 # It is safer to try points at least one pixel into the element from the
319 # edges, hence the `+1`s and `-1`s.
320 { left, top, bottom, height } = elementRect
321 nonCoveredPoint =
322 tryPoint(left, +1, top, +1, 1) or
323 tryPoint(left, +1, top + height / 2, 0, 1) or
324 tryPoint(left, +1, bottom, -1, 1)
325
326 element.classList.remove('VimFxNoBorderRadius')
327
328 return nonCoveredPoint
329
330 # In XUL documents there are “anonymous” elements, whose node names start with
331 # `xul:` or `html:`. These are not never returned by `document.elementFromPoint`
332 # but their closest non-anonymous parents are.
333 getClosestNonAnonymousParent = (element) ->
334 element = element.parentNode while element.prefix?
335 return element
336
337 exports.injectHints = injectHints
Imprint / Impressum