1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 #include "Pivot.h"
7
8 #include "AccIterator.h"
9 #include "Accessible.h"
10 #include "DocAccessible.h"
11 #include "nsAccessibilityService.h"
12 #include "nsAccUtils.h"
13
14 #include "mozilla/dom/ChildIterator.h"
15 #include "mozilla/dom/Element.h"
16
17 using namespace mozilla;
18 using namespace mozilla::a11y;
19
20 ////////////////////////////////////////////////////////////////////////////////
21 // Pivot
22 ////////////////////////////////////////////////////////////////////////////////
23
Pivot(Accessible * aRoot)24 Pivot::Pivot(Accessible* aRoot) : mRoot(aRoot) { MOZ_COUNT_CTOR(Pivot); }
25
~Pivot()26 Pivot::~Pivot() { MOZ_COUNT_DTOR(Pivot); }
27
AdjustStartPosition(Accessible * aAnchor,PivotRule & aRule,uint16_t * aFilterResult)28 Accessible* Pivot::AdjustStartPosition(Accessible* aAnchor, PivotRule& aRule,
29 uint16_t* aFilterResult) {
30 Accessible* matched = aAnchor;
31 *aFilterResult = aRule.Match(aAnchor);
32
33 if (aAnchor != mRoot) {
34 for (Accessible* temp = aAnchor->Parent(); temp && temp != mRoot;
35 temp = temp->Parent()) {
36 uint16_t filtered = aRule.Match(temp);
37 if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) {
38 *aFilterResult = filtered;
39 matched = temp;
40 }
41 }
42 }
43
44 return matched;
45 }
46
SearchBackward(Accessible * aAnchor,PivotRule & aRule,bool aSearchCurrent)47 Accessible* Pivot::SearchBackward(Accessible* aAnchor, PivotRule& aRule,
48 bool aSearchCurrent) {
49 // Initial position could be unset, in that case return null.
50 if (!aAnchor) {
51 return nullptr;
52 }
53
54 uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
55
56 Accessible* accessible = AdjustStartPosition(aAnchor, aRule, &filtered);
57
58 if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)) {
59 return accessible;
60 }
61
62 while (accessible != mRoot) {
63 Accessible* parent = accessible->Parent();
64 int32_t idxInParent = accessible->IndexInParent();
65 while (idxInParent > 0) {
66 if (!(accessible = parent->GetChildAt(--idxInParent))) {
67 continue;
68 }
69
70 filtered = aRule.Match(accessible);
71
72 Accessible* lastChild = nullptr;
73 while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
74 (lastChild = accessible->LastChild())) {
75 parent = accessible;
76 accessible = lastChild;
77 idxInParent = accessible->IndexInParent();
78 filtered = aRule.Match(accessible);
79 }
80
81 if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
82 return accessible;
83 }
84 }
85
86 if (!(accessible = parent)) {
87 break;
88 }
89
90 filtered = aRule.Match(accessible);
91
92 if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
93 return accessible;
94 }
95 }
96
97 return nullptr;
98 }
99
SearchForward(Accessible * aAnchor,PivotRule & aRule,bool aSearchCurrent)100 Accessible* Pivot::SearchForward(Accessible* aAnchor, PivotRule& aRule,
101 bool aSearchCurrent) {
102 // Initial position could be not set, in that case begin search from root.
103 Accessible* accessible = aAnchor ? aAnchor : mRoot;
104
105 uint16_t filtered = nsIAccessibleTraversalRule::FILTER_IGNORE;
106 accessible = AdjustStartPosition(accessible, aRule, &filtered);
107 if (aSearchCurrent && (filtered & nsIAccessibleTraversalRule::FILTER_MATCH)) {
108 return accessible;
109 }
110
111 while (true) {
112 Accessible* firstChild = nullptr;
113 while (!(filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) &&
114 (firstChild = accessible->FirstChild())) {
115 accessible = firstChild;
116 filtered = aRule.Match(accessible);
117
118 if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
119 return accessible;
120 }
121 }
122
123 Accessible* sibling = nullptr;
124 Accessible* temp = accessible;
125 do {
126 if (temp == mRoot) {
127 break;
128 }
129
130 sibling = temp->NextSibling();
131
132 if (sibling) {
133 break;
134 }
135 } while ((temp = temp->Parent()));
136
137 if (!sibling) {
138 break;
139 }
140
141 accessible = sibling;
142 filtered = aRule.Match(accessible);
143 if (filtered & nsIAccessibleTraversalRule::FILTER_MATCH) {
144 return accessible;
145 }
146 }
147
148 return nullptr;
149 }
150
SearchForText(Accessible * aAnchor,bool aBackward)151 HyperTextAccessible* Pivot::SearchForText(Accessible* aAnchor, bool aBackward) {
152 Accessible* accessible = aAnchor;
153 while (true) {
154 Accessible* child = nullptr;
155
156 while ((child = (aBackward ? accessible->LastChild()
157 : accessible->FirstChild()))) {
158 accessible = child;
159 if (child->IsHyperText()) {
160 return child->AsHyperText();
161 }
162 }
163
164 Accessible* sibling = nullptr;
165 Accessible* temp = accessible;
166 do {
167 if (temp == mRoot) {
168 break;
169 }
170
171 // Unlike traditional pre-order traversal we revisit the parent
172 // nodes when we go up the tree. This is because our starting point
173 // may be a subtree or a leaf. If it's parent matches, it should
174 // take precedent over a sibling.
175 if (temp != aAnchor && temp->IsHyperText()) {
176 return temp->AsHyperText();
177 }
178
179 if (sibling) {
180 break;
181 }
182
183 sibling = aBackward ? temp->PrevSibling() : temp->NextSibling();
184 } while ((temp = temp->Parent()));
185
186 if (!sibling) {
187 break;
188 }
189
190 accessible = sibling;
191 if (accessible->IsHyperText()) {
192 return accessible->AsHyperText();
193 }
194 }
195
196 return nullptr;
197 }
198
Next(Accessible * aAnchor,PivotRule & aRule,bool aIncludeStart)199 Accessible* Pivot::Next(Accessible* aAnchor, PivotRule& aRule,
200 bool aIncludeStart) {
201 return SearchForward(aAnchor, aRule, aIncludeStart);
202 }
203
Prev(Accessible * aAnchor,PivotRule & aRule,bool aIncludeStart)204 Accessible* Pivot::Prev(Accessible* aAnchor, PivotRule& aRule,
205 bool aIncludeStart) {
206 return SearchBackward(aAnchor, aRule, aIncludeStart);
207 }
208
First(PivotRule & aRule)209 Accessible* Pivot::First(PivotRule& aRule) {
210 return SearchForward(mRoot, aRule, true);
211 }
212
Last(PivotRule & aRule)213 Accessible* Pivot::Last(PivotRule& aRule) {
214 Accessible* lastAccessible = mRoot;
215
216 // First go to the last accessible in pre-order
217 while (lastAccessible->HasChildren()) {
218 lastAccessible = lastAccessible->LastChild();
219 }
220
221 // Search backwards from last accessible and find the last occurrence in the
222 // doc
223 return SearchBackward(lastAccessible, aRule, true);
224 }
225
NextText(Accessible * aAnchor,int32_t * aStartOffset,int32_t * aEndOffset,int32_t aBoundaryType)226 Accessible* Pivot::NextText(Accessible* aAnchor, int32_t* aStartOffset,
227 int32_t* aEndOffset, int32_t aBoundaryType) {
228 int32_t tempStart = *aStartOffset, tempEnd = *aEndOffset;
229 Accessible* tempPosition = aAnchor;
230
231 // if we're starting on a text leaf, translate the offsets to the
232 // HyperTextAccessible parent and start from there.
233 if (aAnchor->IsTextLeaf() && aAnchor->Parent() &&
234 aAnchor->Parent()->IsHyperText()) {
235 HyperTextAccessible* text = aAnchor->Parent()->AsHyperText();
236 tempPosition = text;
237 int32_t childOffset = text->GetChildOffset(aAnchor);
238 if (tempEnd == -1) {
239 tempStart = 0;
240 tempEnd = 0;
241 }
242 tempStart += childOffset;
243 tempEnd += childOffset;
244 }
245
246 while (true) {
247 MOZ_ASSERT(tempPosition);
248 Accessible* curPosition = tempPosition;
249 HyperTextAccessible* text = nullptr;
250 // Find the nearest text node using a preorder traversal starting from
251 // the current node.
252 if (!(text = tempPosition->AsHyperText())) {
253 text = SearchForText(tempPosition, false);
254 if (!text) {
255 return nullptr;
256 }
257
258 if (text != curPosition) {
259 tempStart = tempEnd = -1;
260 }
261 tempPosition = text;
262 }
263
264 // If the search led to the parent of the node we started on (e.g. when
265 // starting on a text leaf), start the text movement from the end of that
266 // node, otherwise we just default to 0.
267 if (tempEnd == -1) {
268 tempEnd =
269 text == curPosition->Parent() ? text->GetChildOffset(curPosition) : 0;
270 }
271
272 // If there's no more text on the current node, try to find the next text
273 // node; if there isn't one, bail out.
274 if (tempEnd == static_cast<int32_t>(text->CharacterCount())) {
275 if (tempPosition == mRoot) {
276 return nullptr;
277 }
278
279 // If we're currently sitting on a link, try move to either the next
280 // sibling or the parent, whichever is closer to the current end
281 // offset. Otherwise, do a forward search for the next node to land on
282 // (we don't do this in the first case because we don't want to go to the
283 // subtree).
284 Accessible* sibling = tempPosition->NextSibling();
285 if (tempPosition->IsLink()) {
286 if (sibling && sibling->IsLink()) {
287 tempStart = tempEnd = -1;
288 tempPosition = sibling;
289 } else {
290 tempStart = tempPosition->StartOffset();
291 tempEnd = tempPosition->EndOffset();
292 tempPosition = tempPosition->Parent();
293 }
294 } else {
295 tempPosition = SearchForText(tempPosition, false);
296 if (!tempPosition) {
297 return nullptr;
298 }
299
300 tempStart = tempEnd = -1;
301 }
302 continue;
303 }
304
305 AccessibleTextBoundary startBoundary, endBoundary;
306 switch (aBoundaryType) {
307 case nsIAccessiblePivot::CHAR_BOUNDARY:
308 startBoundary = nsIAccessibleText::BOUNDARY_CHAR;
309 endBoundary = nsIAccessibleText::BOUNDARY_CHAR;
310 break;
311 case nsIAccessiblePivot::WORD_BOUNDARY:
312 startBoundary = nsIAccessibleText::BOUNDARY_WORD_START;
313 endBoundary = nsIAccessibleText::BOUNDARY_WORD_END;
314 break;
315 case nsIAccessiblePivot::LINE_BOUNDARY:
316 startBoundary = nsIAccessibleText::BOUNDARY_LINE_START;
317 endBoundary = nsIAccessibleText::BOUNDARY_LINE_END;
318 break;
319 default:
320 return nullptr;
321 }
322
323 nsAutoString unusedText;
324 int32_t newStart = 0, newEnd = 0, currentEnd = tempEnd;
325 text->TextAtOffset(tempEnd, endBoundary, &newStart, &tempEnd, unusedText);
326 text->TextBeforeOffset(tempEnd, startBoundary, &newStart, &newEnd,
327 unusedText);
328 int32_t potentialStart = newEnd == tempEnd ? newStart : newEnd;
329 tempStart = potentialStart > tempStart ? potentialStart : currentEnd;
330
331 // The offset range we've obtained might have embedded characters in it,
332 // limit the range to the start of the first occurrence of an embedded
333 // character.
334 Accessible* childAtOffset = nullptr;
335 for (int32_t i = tempStart; i < tempEnd; i++) {
336 childAtOffset = text->GetChildAtOffset(i);
337 if (childAtOffset && childAtOffset->IsHyperText()) {
338 tempEnd = i;
339 break;
340 }
341 }
342 // If there's an embedded character at the very start of the range, we
343 // instead want to traverse into it. So restart the movement with
344 // the child as the starting point.
345 if (childAtOffset && childAtOffset->IsHyperText() &&
346 tempStart == static_cast<int32_t>(childAtOffset->StartOffset())) {
347 tempPosition = childAtOffset;
348 tempStart = tempEnd = -1;
349 continue;
350 }
351
352 *aStartOffset = tempStart;
353 *aEndOffset = tempEnd;
354
355 MOZ_ASSERT(tempPosition);
356 return tempPosition;
357 }
358 }
359
PrevText(Accessible * aAnchor,int32_t * aStartOffset,int32_t * aEndOffset,int32_t aBoundaryType)360 Accessible* Pivot::PrevText(Accessible* aAnchor, int32_t* aStartOffset,
361 int32_t* aEndOffset, int32_t aBoundaryType) {
362 int32_t tempStart = *aStartOffset, tempEnd = *aEndOffset;
363 Accessible* tempPosition = aAnchor;
364
365 // if we're starting on a text leaf, translate the offsets to the
366 // HyperTextAccessible parent and start from there.
367 if (aAnchor->IsTextLeaf() && aAnchor->Parent() &&
368 aAnchor->Parent()->IsHyperText()) {
369 HyperTextAccessible* text = aAnchor->Parent()->AsHyperText();
370 tempPosition = text;
371 int32_t childOffset = text->GetChildOffset(aAnchor);
372 if (tempStart == -1) {
373 tempStart = nsAccUtils::TextLength(aAnchor);
374 tempEnd = tempStart;
375 }
376 tempStart += childOffset;
377 tempEnd += childOffset;
378 }
379
380 while (true) {
381 MOZ_ASSERT(tempPosition);
382
383 Accessible* curPosition = tempPosition;
384 HyperTextAccessible* text;
385 // Find the nearest text node using a reverse preorder traversal starting
386 // from the current node.
387 if (!(text = tempPosition->AsHyperText())) {
388 text = SearchForText(tempPosition, true);
389 if (!text) {
390 return nullptr;
391 }
392
393 if (text != curPosition) {
394 tempStart = tempEnd = -1;
395 }
396 tempPosition = text;
397 }
398
399 // If the search led to the parent of the node we started on (e.g. when
400 // starting on a text leaf), start the text movement from the end offset
401 // of that node. Otherwise we just default to the last offset in the parent.
402 if (tempStart == -1) {
403 if (tempPosition != curPosition && text == curPosition->Parent()) {
404 tempStart = text->GetChildOffset(curPosition) +
405 nsAccUtils::TextLength(curPosition);
406 } else {
407 tempStart = text->CharacterCount();
408 }
409 }
410
411 // If there's no more text on the current node, try to find the previous
412 // text node; if there isn't one, bail out.
413 if (tempStart == 0) {
414 if (tempPosition == mRoot) {
415 return nullptr;
416 }
417
418 // If we're currently sitting on a link, try move to either the previous
419 // sibling or the parent, whichever is closer to the current end
420 // offset. Otherwise, do a forward search for the next node to land on
421 // (we don't do this in the first case because we don't want to go to the
422 // subtree).
423 Accessible* sibling = tempPosition->PrevSibling();
424 if (tempPosition->IsLink()) {
425 if (sibling && sibling->IsLink()) {
426 HyperTextAccessible* siblingText = sibling->AsHyperText();
427 tempStart = tempEnd =
428 siblingText ? siblingText->CharacterCount() : -1;
429 tempPosition = sibling;
430 } else {
431 tempStart = tempPosition->StartOffset();
432 tempEnd = tempPosition->EndOffset();
433 tempPosition = tempPosition->Parent();
434 }
435 } else {
436 HyperTextAccessible* tempText = SearchForText(tempPosition, true);
437 if (!tempText) {
438 return nullptr;
439 }
440
441 tempPosition = tempText;
442 tempStart = tempEnd = tempText->CharacterCount();
443 }
444 continue;
445 }
446
447 AccessibleTextBoundary startBoundary, endBoundary;
448 switch (aBoundaryType) {
449 case nsIAccessiblePivot::CHAR_BOUNDARY:
450 startBoundary = nsIAccessibleText::BOUNDARY_CHAR;
451 endBoundary = nsIAccessibleText::BOUNDARY_CHAR;
452 break;
453 case nsIAccessiblePivot::WORD_BOUNDARY:
454 startBoundary = nsIAccessibleText::BOUNDARY_WORD_START;
455 endBoundary = nsIAccessibleText::BOUNDARY_WORD_END;
456 break;
457 case nsIAccessiblePivot::LINE_BOUNDARY:
458 startBoundary = nsIAccessibleText::BOUNDARY_LINE_START;
459 endBoundary = nsIAccessibleText::BOUNDARY_LINE_END;
460 break;
461 default:
462 return nullptr;
463 }
464
465 nsAutoString unusedText;
466 int32_t newStart = 0, newEnd = 0, currentStart = tempStart,
467 potentialEnd = 0;
468 text->TextBeforeOffset(tempStart, startBoundary, &newStart, &newEnd,
469 unusedText);
470 if (newStart < tempStart) {
471 tempStart = newEnd >= currentStart ? newStart : newEnd;
472 } else {
473 // XXX: In certain odd cases newStart is equal to tempStart
474 text->TextBeforeOffset(tempStart - 1, startBoundary, &newStart,
475 &tempStart, unusedText);
476 }
477 text->TextAtOffset(tempStart, endBoundary, &newStart, &potentialEnd,
478 unusedText);
479 tempEnd = potentialEnd < tempEnd ? potentialEnd : currentStart;
480
481 // The offset range we've obtained might have embedded characters in it,
482 // limit the range to the start of the last occurrence of an embedded
483 // character.
484 Accessible* childAtOffset = nullptr;
485 for (int32_t i = tempEnd - 1; i >= tempStart; i--) {
486 childAtOffset = text->GetChildAtOffset(i);
487 if (childAtOffset && !childAtOffset->IsText()) {
488 tempStart = childAtOffset->EndOffset();
489 break;
490 }
491 }
492 // If there's an embedded character at the very end of the range, we
493 // instead want to traverse into it. So restart the movement with
494 // the child as the starting point.
495 if (childAtOffset && !childAtOffset->IsText() &&
496 tempEnd == static_cast<int32_t>(childAtOffset->EndOffset())) {
497 tempPosition = childAtOffset;
498 tempStart = tempEnd = childAtOffset->AsHyperText()->CharacterCount();
499 continue;
500 }
501
502 *aStartOffset = tempStart;
503 *aEndOffset = tempEnd;
504
505 MOZ_ASSERT(tempPosition);
506 return tempPosition;
507 }
508 }
509
AtPoint(int32_t aX,int32_t aY,PivotRule & aRule)510 Accessible* Pivot::AtPoint(int32_t aX, int32_t aY, PivotRule& aRule) {
511 Accessible* match = nullptr;
512 Accessible* child = mRoot->ChildAtPoint(aX, aY, Accessible::eDeepestChild);
513 while (child && mRoot != child) {
514 uint16_t filtered = aRule.Match(child);
515
516 // Ignore any matching nodes that were below this one
517 if (filtered & nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE) {
518 match = nullptr;
519 }
520
521 // Match if no node below this is a match
522 if ((filtered & nsIAccessibleTraversalRule::FILTER_MATCH) && !match) {
523 nsIntRect childRect = child->Bounds();
524 // Double-check child's bounds since the deepest child may have been out
525 // of bounds. This assures we don't return a false positive.
526 if (childRect.Contains(aX, aY)) {
527 match = child;
528 }
529 }
530
531 child = child->Parent();
532 }
533
534 return match;
535 }
536
537 // Role Rule
538
PivotRoleRule(mozilla::a11y::role aRole)539 PivotRoleRule::PivotRoleRule(mozilla::a11y::role aRole) : mRole(aRole) {}
540
Match(Accessible * aAccessible)541 uint16_t PivotRoleRule::Match(Accessible* aAccessible) {
542 uint16_t result = nsIAccessibleTraversalRule::FILTER_IGNORE;
543
544 if (nsAccUtils::MustPrune(aAccessible)) {
545 result |= nsIAccessibleTraversalRule::FILTER_IGNORE_SUBTREE;
546 }
547
548 if (aAccessible->Role() == mRole) {
549 result |= nsIAccessibleTraversalRule::FILTER_MATCH;
550 }
551
552 return result;
553 }
554