Add "VisibleOnly" key to search predicate
[WebKit-https.git] / Source / WebCore / accessibility / AccessibilityObject.cpp
1 /*
2  * Copyright (C) 2008, 2009, 2011 Apple Inc. All rights reserved.
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * 1.  Redistributions of source code must retain the above copyright
9  *     notice, this list of conditions and the following disclaimer.
10  * 2.  Redistributions in binary form must reproduce the above copyright
11  *     notice, this list of conditions and the following disclaimer in the
12  *     documentation and/or other materials provided with the distribution.
13  * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of
14  *     its contributors may be used to endorse or promote products derived
15  *     from this software without specific prior written permission.
16  *
17  * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY
18  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
19  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
20  * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY
21  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
22  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
23  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
24  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27  */
28
29 #include "config.h"
30 #include "AccessibilityObject.h"
31
32 #include "AXObjectCache.h"
33 #include "AccessibilityRenderObject.h"
34 #include "AccessibilityTable.h"
35 #include "Editor.h"
36 #include "FloatRect.h"
37 #include "FocusController.h"
38 #include "Frame.h"
39 #include "FrameLoader.h"
40 #include "FrameSelection.h"
41 #include "HTMLNames.h"
42 #include "LocalizedStrings.h"
43 #include "NodeList.h"
44 #include "NodeTraversal.h"
45 #include "NotImplemented.h"
46 #include "Page.h"
47 #include "RenderImage.h"
48 #include "RenderListItem.h"
49 #include "RenderListMarker.h"
50 #include "RenderMenuList.h"
51 #include "RenderTextControl.h"
52 #include "RenderTheme.h"
53 #include "RenderView.h"
54 #include "RenderWidget.h"
55 #include "RenderedPosition.h"
56 #include "Settings.h"
57 #include "TextCheckerClient.h"
58 #include "TextCheckingHelper.h"
59 #include "TextIterator.h"
60 #include "UserGestureIndicator.h"
61 #include "VisibleUnits.h"
62 #include "htmlediting.h"
63 #include <wtf/StdLibExtras.h>
64 #include <wtf/text/StringBuilder.h>
65 #include <wtf/text/WTFString.h>
66 #include <wtf/unicode/CharacterNames.h>
67
68 using namespace std;
69
70 namespace WebCore {
71
72 using namespace HTMLNames;
73
74 AccessibilityObject::AccessibilityObject()
75     : m_id(0)
76     , m_haveChildren(false)
77     , m_role(UnknownRole)
78     , m_lastKnownIsIgnoredValue(DefaultBehavior)
79 #if PLATFORM(GTK) || (PLATFORM(EFL) && HAVE(ACCESSIBILITY))
80     , m_wrapper(0)
81 #endif
82 {
83 }
84
85 AccessibilityObject::~AccessibilityObject()
86 {
87     ASSERT(isDetached());
88 }
89
90 void AccessibilityObject::detach()
91 {
92     // Clear any children and call detachFromParent on them so that
93     // no children are left with dangling pointers to their parent.
94     clearChildren();
95
96 #if HAVE(ACCESSIBILITY)
97     setWrapper(0);
98 #endif
99 }
100
101 bool AccessibilityObject::isDetached() const
102 {
103 #if HAVE(ACCESSIBILITY)
104     return !wrapper();
105 #else
106     return true;
107 #endif
108 }
109
110 bool AccessibilityObject::isAccessibilityObjectSearchMatchAtIndex(AccessibilityObject* axObject, AccessibilitySearchCriteria* criteria, size_t index)
111 {
112     switch (criteria->searchKeys[index]) {
113     // The AnyTypeSearchKey matches any non-null AccessibilityObject.
114     case AnyTypeSearchKey:
115         return true;
116         
117     case BlockquoteSameLevelSearchKey:
118         return criteria->startObject
119             && axObject->isBlockquote()
120             && axObject->blockquoteLevel() == criteria->startObject->blockquoteLevel();
121         
122     case BlockquoteSearchKey:
123         return axObject->isBlockquote();
124         
125     case BoldFontSearchKey:
126         return axObject->hasBoldFont();
127         
128     case ButtonSearchKey:
129         return axObject->isButton();
130         
131     case CheckBoxSearchKey:
132         return axObject->isCheckbox();
133         
134     case ControlSearchKey:
135         return axObject->isControl();
136         
137     case DifferentTypeSearchKey:
138         return criteria->startObject
139             && axObject->roleValue() != criteria->startObject->roleValue();
140         
141     case FontChangeSearchKey:
142         return criteria->startObject
143             && !axObject->hasSameFont(criteria->startObject->renderer());
144         
145     case FontColorChangeSearchKey:
146         return criteria->startObject
147             && !axObject->hasSameFontColor(criteria->startObject->renderer());
148         
149     case FrameSearchKey:
150         return axObject->isWebArea();
151         
152     case GraphicSearchKey:
153         return axObject->isImage();
154         
155     case HeadingLevel1SearchKey:
156         return axObject->headingLevel() == 1;
157         
158     case HeadingLevel2SearchKey:
159         return axObject->headingLevel() == 2;
160         
161     case HeadingLevel3SearchKey:
162         return axObject->headingLevel() == 3;
163         
164     case HeadingLevel4SearchKey:
165         return axObject->headingLevel() == 4;
166         
167     case HeadingLevel5SearchKey:
168         return axObject->headingLevel() == 5;
169         
170     case HeadingLevel6SearchKey:
171         return axObject->headingLevel() == 6;
172         
173     case HeadingSameLevelSearchKey:
174         return criteria->startObject
175             && axObject->isHeading()
176             && axObject->headingLevel() == criteria->startObject->headingLevel();
177         
178     case HeadingSearchKey:
179         return axObject->isHeading();
180     
181     case HighlightedSearchKey:
182         return axObject->hasHighlighting();
183             
184     case ItalicFontSearchKey:
185         return axObject->hasItalicFont();
186         
187     case LandmarkSearchKey:
188         return axObject->isLandmark();
189         
190     case LinkSearchKey:
191         return axObject->isLink();
192         
193     case ListSearchKey:
194         return axObject->isList();
195         
196     case LiveRegionSearchKey:
197         return axObject->supportsARIALiveRegion();
198         
199     case MisspelledWordSearchKey:
200         return axObject->hasMisspelling();
201         
202     case PlainTextSearchKey:
203         return axObject->hasPlainText();
204         
205     case RadioGroupSearchKey:
206         return axObject->isRadioGroup();
207         
208     case SameTypeSearchKey:
209         return criteria->startObject
210             && axObject->roleValue() == criteria->startObject->roleValue();
211         
212     case StaticTextSearchKey:
213         return axObject->isStaticText();
214         
215     case StyleChangeSearchKey:
216         return criteria->startObject
217             && !axObject->hasSameStyle(criteria->startObject->renderer());
218         
219     case TableSameLevelSearchKey:
220         return criteria->startObject
221             && axObject->isAccessibilityTable()
222             && axObject->tableLevel() == criteria->startObject->tableLevel();
223         
224     case TableSearchKey:
225         return axObject->isAccessibilityTable();
226         
227     case TextFieldSearchKey:
228         return axObject->isTextControl();
229         
230     case UnderlineSearchKey:
231         return axObject->hasUnderline();
232         
233     case UnvisitedLinkSearchKey:
234         return axObject->isUnvisited();
235         
236     case VisitedLinkSearchKey:
237         return axObject->isVisited();
238         
239     default:
240         return false;
241     }
242 }
243
244 bool AccessibilityObject::isAccessibilityObjectSearchMatch(AccessibilityObject* axObject, AccessibilitySearchCriteria* criteria)
245 {
246     if (!axObject || !criteria)
247         return false;
248     
249     size_t length = criteria->searchKeys.size();
250     for (size_t i = 0; i < length; ++i) {
251         if (isAccessibilityObjectSearchMatchAtIndex(axObject, criteria, i)) {
252             if (criteria->visibleOnly && !axObject->isOnscreen())
253                 return false;
254             return true;
255         }
256     }
257     return false;
258 }
259
260 bool AccessibilityObject::isAccessibilityTextSearchMatch(AccessibilityObject* axObject, AccessibilitySearchCriteria* criteria)
261 {
262     if (!axObject || !criteria)
263         return false;
264     
265     return axObject->accessibilityObjectContainsText(criteria->searchText);
266 }
267
268 bool AccessibilityObject::accessibilityObjectContainsText(String* text) const
269 {
270     // If text is null or empty we return true.
271     return !text
272         || text->isEmpty()
273         || title().contains(*text, false)
274         || accessibilityDescription().contains(*text, false)
275         || stringValue().contains(*text, false);
276 }
277
278 bool AccessibilityObject::isBlockquote() const
279 {
280     return node() && node()->hasTagName(blockquoteTag);
281 }
282
283 bool AccessibilityObject::isTextControl() const
284 {
285     switch (roleValue()) {
286     case TextAreaRole:
287     case TextFieldRole:
288     case ComboBoxRole:
289         return true;
290     default:
291         return false;
292     }
293 }
294     
295 bool AccessibilityObject::isARIATextControl() const
296 {
297     return ariaRoleAttribute() == TextAreaRole || ariaRoleAttribute() == TextFieldRole;
298 }
299
300 bool AccessibilityObject::isLandmark() const
301 {
302     AccessibilityRole role = roleValue();
303     
304     return role == LandmarkApplicationRole
305         || role == LandmarkBannerRole
306         || role == LandmarkComplementaryRole
307         || role == LandmarkContentInfoRole
308         || role == LandmarkMainRole
309         || role == LandmarkNavigationRole
310         || role == LandmarkSearchRole;
311 }
312
313 bool AccessibilityObject::hasMisspelling() const
314 {
315     if (!node())
316         return false;
317     
318     Document* document = node()->document();
319     if (!document)
320         return false;
321     
322     Frame* frame = document->frame();
323     if (!frame)
324         return false;
325     
326     Editor& editor = frame->editor();
327     
328     TextCheckerClient* textChecker = editor.textChecker();
329     if (!textChecker)
330         return false;
331     
332     const UChar* chars = stringValue().characters();
333     int charsLength = stringValue().length();
334     bool isMisspelled = false;
335
336     if (unifiedTextCheckerEnabled(frame)) {
337         Vector<TextCheckingResult> results;
338         checkTextOfParagraph(textChecker, chars, charsLength, TextCheckingTypeSpelling, results);
339         if (!results.isEmpty())
340             isMisspelled = true;
341         return isMisspelled;
342     }
343
344     int misspellingLength = 0;
345     int misspellingLocation = -1;
346     textChecker->checkSpellingOfString(chars, charsLength, &misspellingLocation, &misspellingLength);
347     if (misspellingLength || misspellingLocation != -1)
348         isMisspelled = true;
349     
350     return isMisspelled;
351 }
352
353 int AccessibilityObject::blockquoteLevel() const
354 {
355     int level = 0;
356     for (Node* elementNode = node(); elementNode; elementNode = elementNode->parentNode()) {
357         if (elementNode->hasTagName(blockquoteTag))
358             ++level;
359     }
360     
361     return level;
362 }
363
364 AccessibilityObject* AccessibilityObject::parentObjectUnignored() const
365 {
366     AccessibilityObject* parent;
367     for (parent = parentObject(); parent && parent->accessibilityIsIgnored(); parent = parent->parentObject()) {
368     }
369     
370     return parent;
371 }
372
373 AccessibilityObject* AccessibilityObject::firstAccessibleObjectFromNode(const Node* node)
374 {
375     if (!node)
376         return 0;
377
378     Document* document = node->document();
379     if (!document)
380         return 0;
381
382     AXObjectCache* cache = document->axObjectCache();
383
384     AccessibilityObject* accessibleObject = cache->getOrCreate(node->renderer());
385     while (accessibleObject && accessibleObject->accessibilityIsIgnored()) {
386         node = NodeTraversal::next(node);
387
388         while (node && !node->renderer())
389             node = NodeTraversal::nextSkippingChildren(node);
390
391         if (!node)
392             return 0;
393
394         accessibleObject = cache->getOrCreate(node->renderer());
395     }
396
397     return accessibleObject;
398 }
399
400 static void appendAccessibilityObject(AccessibilityObject* object, AccessibilityObject::AccessibilityChildrenVector& results)
401 {
402     // Find the next descendant of this attachment object so search can continue through frames.
403     if (object->isAttachment()) {
404         Widget* widget = object->widgetForAttachmentView();
405         if (!widget || !widget->isFrameView())
406             return;
407         
408         Document* doc = toFrameView(widget)->frame()->document();
409         if (!doc || !doc->renderer())
410             return;
411         
412         object = object->axObjectCache()->getOrCreate(doc);
413     }
414
415     if (object)
416         results.append(object);
417 }
418     
419 static void appendChildrenToArray(AccessibilityObject* object, bool isForward, AccessibilityObject* startObject, AccessibilityObject::AccessibilityChildrenVector& results)
420 {
421     AccessibilityObject::AccessibilityChildrenVector searchChildren;
422     // A table's children includes elements whose own children are also the table's children (due to the way the Mac exposes tables).
423     // The rows from the table should be queried, since those are direct descendants of the table, and they contain content.
424     if (object->isAccessibilityTable())
425         searchChildren = toAccessibilityTable(object)->rows();
426     else
427         searchChildren = object->children();
428
429     size_t childrenSize = searchChildren.size();
430
431     size_t startIndex = isForward ? childrenSize : 0;
432     size_t endIndex = isForward ? 0 : childrenSize;
433
434     size_t searchPosition = startObject ? searchChildren.find(startObject) : WTF::notFound;
435     if (searchPosition != WTF::notFound) {
436         if (isForward)
437             endIndex = searchPosition + 1;
438         else
439             endIndex = searchPosition;
440     }
441
442     // This is broken into two statements so that it's easier read.
443     if (isForward) {
444         for (size_t i = startIndex; i > endIndex; i--)
445             appendAccessibilityObject(searchChildren.at(i - 1).get(), results);
446     } else {
447         for (size_t i = startIndex; i < endIndex; i++)
448             appendAccessibilityObject(searchChildren.at(i).get(), results);
449     }
450 }
451
452 // Returns true if the number of results is now >= the number of results desired.
453 bool AccessibilityObject::objectMatchesSearchCriteriaWithResultLimit(AccessibilityObject* object, AccessibilitySearchCriteria* criteria, AccessibilityChildrenVector& results)
454 {
455     if (isAccessibilityObjectSearchMatch(object, criteria) && isAccessibilityTextSearchMatch(object, criteria)) {
456         results.append(object);
457         
458         // Enough results were found to stop searching.
459         if (results.size() >= criteria->resultsLimit)
460             return true;
461     }
462     
463     return false;
464 }
465
466 void AccessibilityObject::findMatchingObjects(AccessibilitySearchCriteria* criteria, AccessibilityChildrenVector& results)
467 {
468     ASSERT(criteria);
469     
470     if (!criteria)
471         return;
472
473     axObjectCache()->startCachingComputedObjectAttributesUntilTreeMutates();
474
475     // This search mechanism only searches the elements before/after the starting object.
476     // It does this by stepping up the parent chain and at each level doing a DFS.
477     
478     // If there's no start object, it means we want to search everything.
479     AccessibilityObject* startObject = criteria->startObject;
480     if (!startObject)
481         startObject = this;
482     
483     bool isForward = criteria->searchDirection == SearchDirectionNext;
484     
485     // In the first iteration of the loop, it will examine the children of the start object for matches.
486     // However, when going backwards, those children should not be considered, so the loop is skipped ahead.
487     AccessibilityObject* previousObject = 0;
488     if (!isForward) {
489         previousObject = startObject;
490         startObject = startObject->parentObjectUnignored();
491     }
492     
493     // The outer loop steps up the parent chain each time (unignored is important here because otherwise elements would be searched twice)
494     for (AccessibilityObject* stopSearchElement = parentObjectUnignored(); startObject != stopSearchElement; startObject = startObject->parentObjectUnignored()) {
495
496         // Only append the children after/before the previous element, so that the search does not check elements that are 
497         // already behind/ahead of start element.
498         AccessibilityChildrenVector searchStack;
499         appendChildrenToArray(startObject, isForward, previousObject, searchStack);
500
501         // This now does a DFS at the current level of the parent.
502         while (!searchStack.isEmpty()) {
503             AccessibilityObject* searchObject = searchStack.last().get();
504             searchStack.removeLast();
505             
506             if (objectMatchesSearchCriteriaWithResultLimit(searchObject, criteria, results))
507                 break;
508             
509             appendChildrenToArray(searchObject, isForward, 0, searchStack);
510         }
511         
512         if (results.size() >= criteria->resultsLimit)
513             break;
514
515         // When moving backwards, the parent object needs to be checked, because technically it's "before" the starting element.
516         if (!isForward && objectMatchesSearchCriteriaWithResultLimit(startObject, criteria, results))
517             break;
518
519         previousObject = startObject;
520     }
521 }
522
523 bool AccessibilityObject::isARIAInput(AccessibilityRole ariaRole)
524 {
525     return ariaRole == RadioButtonRole || ariaRole == CheckBoxRole || ariaRole == TextFieldRole;
526 }    
527     
528 bool AccessibilityObject::isARIAControl(AccessibilityRole ariaRole)
529 {
530     return isARIAInput(ariaRole) || ariaRole == TextAreaRole || ariaRole == ButtonRole 
531     || ariaRole == ComboBoxRole || ariaRole == SliderRole; 
532 }
533     
534 bool AccessibilityObject::isRangeControl() const
535 {
536     switch (roleValue()) {
537     case ProgressIndicatorRole:
538     case SliderRole:
539     case ScrollBarRole:
540     case SpinButtonRole:
541         return true;
542     default:
543         return false;
544     }
545 }
546
547 IntPoint AccessibilityObject::clickPoint()
548 {
549     LayoutRect rect = elementRect();
550     return roundedIntPoint(LayoutPoint(rect.x() + rect.width() / 2, rect.y() + rect.height() / 2));
551 }
552
553 IntRect AccessibilityObject::boundingBoxForQuads(RenderObject* obj, const Vector<FloatQuad>& quads)
554 {
555     ASSERT(obj);
556     if (!obj)
557         return IntRect();
558     
559     size_t count = quads.size();
560     if (!count)
561         return IntRect();
562     
563     IntRect result;
564     for (size_t i = 0; i < count; ++i) {
565         IntRect r = quads[i].enclosingBoundingBox();
566         if (!r.isEmpty()) {
567             if (obj->style()->hasAppearance())
568                 obj->theme()->adjustRepaintRect(obj, r);
569             result.unite(r);
570         }
571     }
572     return result;
573 }
574     
575 bool AccessibilityObject::press() const
576 {
577     Element* actionElem = actionElement();
578     if (!actionElem)
579         return false;
580     if (Frame* f = actionElem->document()->frame())
581         f->loader()->resetMultipleFormSubmissionProtection();
582     
583     UserGestureIndicator gestureIndicator(DefinitelyProcessingNewUserGesture);
584     actionElem->accessKeyAction(true);
585     return true;
586 }
587     
588 String AccessibilityObject::language() const
589 {
590     const AtomicString& lang = getAttribute(langAttr);
591     if (!lang.isEmpty())
592         return lang;
593
594     AccessibilityObject* parent = parentObject();
595     
596     // as a last resort, fall back to the content language specified in the meta tag
597     if (!parent) {
598         Document* doc = document();
599         if (doc)
600             return doc->contentLanguage();
601         return nullAtom;
602     }
603     
604     return parent->language();
605 }
606     
607 VisiblePositionRange AccessibilityObject::visiblePositionRangeForUnorderedPositions(const VisiblePosition& visiblePos1, const VisiblePosition& visiblePos2) const
608 {
609     if (visiblePos1.isNull() || visiblePos2.isNull())
610         return VisiblePositionRange();
611
612     VisiblePosition startPos;
613     VisiblePosition endPos;
614     bool alreadyInOrder;
615
616     // upstream is ordered before downstream for the same position
617     if (visiblePos1 == visiblePos2 && visiblePos2.affinity() == UPSTREAM)
618         alreadyInOrder = false;
619
620     // use selection order to see if the positions are in order
621     else
622         alreadyInOrder = VisibleSelection(visiblePos1, visiblePos2).isBaseFirst();
623
624     if (alreadyInOrder) {
625         startPos = visiblePos1;
626         endPos = visiblePos2;
627     } else {
628         startPos = visiblePos2;
629         endPos = visiblePos1;
630     }
631
632     return VisiblePositionRange(startPos, endPos);
633 }
634
635 VisiblePositionRange AccessibilityObject::positionOfLeftWord(const VisiblePosition& visiblePos) const
636 {
637     VisiblePosition startPosition = startOfWord(visiblePos, LeftWordIfOnBoundary);
638     VisiblePosition endPosition = endOfWord(startPosition);
639     return VisiblePositionRange(startPosition, endPosition);
640 }
641
642 VisiblePositionRange AccessibilityObject::positionOfRightWord(const VisiblePosition& visiblePos) const
643 {
644     VisiblePosition startPosition = startOfWord(visiblePos, RightWordIfOnBoundary);
645     VisiblePosition endPosition = endOfWord(startPosition);
646     return VisiblePositionRange(startPosition, endPosition);
647 }
648
649 static VisiblePosition updateAXLineStartForVisiblePosition(const VisiblePosition& visiblePosition)
650 {
651     // A line in the accessibility sense should include floating objects, such as aligned image, as part of a line.
652     // So let's update the position to include that.
653     VisiblePosition tempPosition;
654     VisiblePosition startPosition = visiblePosition;
655     while (true) {
656         tempPosition = startPosition.previous();
657         if (tempPosition.isNull())
658             break;
659         Position p = tempPosition.deepEquivalent();
660         RenderObject* renderer = p.deprecatedNode()->renderer();
661         if (!renderer || (renderer->isRenderBlock() && !p.deprecatedEditingOffset()))
662             break;
663         if (!RenderedPosition(tempPosition).isNull())
664             break;
665         startPosition = tempPosition;
666     }
667
668     return startPosition;
669 }
670
671 VisiblePositionRange AccessibilityObject::leftLineVisiblePositionRange(const VisiblePosition& visiblePos) const
672 {
673     if (visiblePos.isNull())
674         return VisiblePositionRange();
675
676     // make a caret selection for the position before marker position (to make sure
677     // we move off of a line start)
678     VisiblePosition prevVisiblePos = visiblePos.previous();
679     if (prevVisiblePos.isNull())
680         return VisiblePositionRange();
681
682     VisiblePosition startPosition = startOfLine(prevVisiblePos);
683
684     // keep searching for a valid line start position.  Unless the VisiblePosition is at the very beginning, there should
685     // always be a valid line range.  However, startOfLine will return null for position next to a floating object,
686     // since floating object doesn't really belong to any line.
687     // This check will reposition the marker before the floating object, to ensure we get a line start.
688     if (startPosition.isNull()) {
689         while (startPosition.isNull() && prevVisiblePos.isNotNull()) {
690             prevVisiblePos = prevVisiblePos.previous();
691             startPosition = startOfLine(prevVisiblePos);
692         }
693     } else
694         startPosition = updateAXLineStartForVisiblePosition(startPosition);
695
696     VisiblePosition endPosition = endOfLine(prevVisiblePos);
697     return VisiblePositionRange(startPosition, endPosition);
698 }
699
700 VisiblePositionRange AccessibilityObject::rightLineVisiblePositionRange(const VisiblePosition& visiblePos) const
701 {
702     if (visiblePos.isNull())
703         return VisiblePositionRange();
704
705     // make sure we move off of a line end
706     VisiblePosition nextVisiblePos = visiblePos.next();
707     if (nextVisiblePos.isNull())
708         return VisiblePositionRange();
709
710     VisiblePosition startPosition = startOfLine(nextVisiblePos);
711
712     // fetch for a valid line start position
713     if (startPosition.isNull()) {
714         startPosition = visiblePos;
715         nextVisiblePos = nextVisiblePos.next();
716     } else
717         startPosition = updateAXLineStartForVisiblePosition(startPosition);
718
719     VisiblePosition endPosition = endOfLine(nextVisiblePos);
720
721     // as long as the position hasn't reached the end of the doc,  keep searching for a valid line end position
722     // Unless the VisiblePosition is at the very end, there should always be a valid line range.  However, endOfLine will
723     // return null for position by a floating object, since floating object doesn't really belong to any line.
724     // This check will reposition the marker after the floating object, to ensure we get a line end.
725     while (endPosition.isNull() && nextVisiblePos.isNotNull()) {
726         nextVisiblePos = nextVisiblePos.next();
727         endPosition = endOfLine(nextVisiblePos);
728     }
729
730     return VisiblePositionRange(startPosition, endPosition);
731 }
732
733 VisiblePositionRange AccessibilityObject::sentenceForPosition(const VisiblePosition& visiblePos) const
734 {
735     // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)
736     // Related? <rdar://problem/3927736> Text selection broken in 8A336
737     VisiblePosition startPosition = startOfSentence(visiblePos);
738     VisiblePosition endPosition = endOfSentence(startPosition);
739     return VisiblePositionRange(startPosition, endPosition);
740 }
741
742 VisiblePositionRange AccessibilityObject::paragraphForPosition(const VisiblePosition& visiblePos) const
743 {
744     VisiblePosition startPosition = startOfParagraph(visiblePos);
745     VisiblePosition endPosition = endOfParagraph(startPosition);
746     return VisiblePositionRange(startPosition, endPosition);
747 }
748
749 static VisiblePosition startOfStyleRange(const VisiblePosition& visiblePos)
750 {
751     RenderObject* renderer = visiblePos.deepEquivalent().deprecatedNode()->renderer();
752     RenderObject* startRenderer = renderer;
753     RenderStyle* style = renderer->style();
754
755     // traverse backward by renderer to look for style change
756     for (RenderObject* r = renderer->previousInPreOrder(); r; r = r->previousInPreOrder()) {
757         // skip non-leaf nodes
758         if (r->firstChild())
759             continue;
760
761         // stop at style change
762         if (r->style() != style)
763             break;
764
765         // remember match
766         startRenderer = r;
767     }
768
769     return firstPositionInOrBeforeNode(startRenderer->node());
770 }
771
772 static VisiblePosition endOfStyleRange(const VisiblePosition& visiblePos)
773 {
774     RenderObject* renderer = visiblePos.deepEquivalent().deprecatedNode()->renderer();
775     RenderObject* endRenderer = renderer;
776     RenderStyle* style = renderer->style();
777
778     // traverse forward by renderer to look for style change
779     for (RenderObject* r = renderer->nextInPreOrder(); r; r = r->nextInPreOrder()) {
780         // skip non-leaf nodes
781         if (r->firstChild())
782             continue;
783
784         // stop at style change
785         if (r->style() != style)
786             break;
787
788         // remember match
789         endRenderer = r;
790     }
791
792     return lastPositionInOrAfterNode(endRenderer->node());
793 }
794
795 VisiblePositionRange AccessibilityObject::styleRangeForPosition(const VisiblePosition& visiblePos) const
796 {
797     if (visiblePos.isNull())
798         return VisiblePositionRange();
799
800     return VisiblePositionRange(startOfStyleRange(visiblePos), endOfStyleRange(visiblePos));
801 }
802
803 // NOTE: Consider providing this utility method as AX API
804 VisiblePositionRange AccessibilityObject::visiblePositionRangeForRange(const PlainTextRange& range) const
805 {
806     unsigned textLength = getLengthForTextRange();
807     if (range.start + range.length > textLength)
808         return VisiblePositionRange();
809
810     VisiblePosition startPosition = visiblePositionForIndex(range.start);
811     startPosition.setAffinity(DOWNSTREAM);
812     VisiblePosition endPosition = visiblePositionForIndex(range.start + range.length);
813     return VisiblePositionRange(startPosition, endPosition);
814 }
815
816 static bool replacedNodeNeedsCharacter(Node* replacedNode)
817 {
818     // we should always be given a rendered node and a replaced node, but be safe
819     // replaced nodes are either attachments (widgets) or images
820     if (!replacedNode || !replacedNode->renderer() || !replacedNode->renderer()->isReplaced() || replacedNode->isTextNode())
821         return false;
822
823     // create an AX object, but skip it if it is not supposed to be seen
824     AccessibilityObject* object = replacedNode->renderer()->document()->axObjectCache()->getOrCreate(replacedNode);
825     if (object->accessibilityIsIgnored())
826         return false;
827
828     return true;
829 }
830
831 // Finds a RenderListItem parent give a node.
832 static RenderListItem* renderListItemContainerForNode(Node* node)
833 {
834     for (; node; node = node->parentNode()) {
835         RenderBoxModelObject* renderer = node->renderBoxModelObject();
836         if (renderer && renderer->isListItem())
837             return toRenderListItem(renderer);
838     }
839     return 0;
840 }
841     
842 // Returns the text associated with a list marker if this node is contained within a list item.
843 String AccessibilityObject::listMarkerTextForNodeAndPosition(Node* node, const VisiblePosition& visiblePositionStart) const
844 {
845     // If the range does not contain the start of the line, the list marker text should not be included.
846     if (!isStartOfLine(visiblePositionStart))
847         return String();
848
849     RenderListItem* listItem = renderListItemContainerForNode(node);
850     if (!listItem)
851         return String();
852         
853     // If this is in a list item, we need to manually add the text for the list marker 
854     // because a RenderListMarker does not have a Node equivalent and thus does not appear
855     // when iterating text.
856     return listItem->markerTextWithSuffix();
857 }
858     
859 String AccessibilityObject::stringForVisiblePositionRange(const VisiblePositionRange& visiblePositionRange) const
860 {
861     if (visiblePositionRange.isNull())
862         return String();
863
864     StringBuilder builder;
865     RefPtr<Range> range = makeRange(visiblePositionRange.start, visiblePositionRange.end);
866     for (TextIterator it(range.get()); !it.atEnd(); it.advance()) {
867         // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)
868         if (it.length()) {
869             // Add a textual representation for list marker text
870             String listMarkerText = listMarkerTextForNodeAndPosition(it.node(), visiblePositionRange.start);
871             if (!listMarkerText.isEmpty())
872                 builder.append(listMarkerText);
873
874             it.appendTextToStringBuilder(builder);
875         } else {
876             // locate the node and starting offset for this replaced range
877             int exception = 0;
878             Node* node = it.range()->startContainer(exception);
879             ASSERT(node == it.range()->endContainer(exception));
880             int offset = it.range()->startOffset(exception);
881
882             if (replacedNodeNeedsCharacter(node->childNode(offset)))
883                 builder.append(objectReplacementCharacter);
884         }
885     }
886
887     return builder.toString();
888 }
889
890 int AccessibilityObject::lengthForVisiblePositionRange(const VisiblePositionRange& visiblePositionRange) const
891 {
892     // FIXME: Multi-byte support
893     if (visiblePositionRange.isNull())
894         return -1;
895     
896     int length = 0;
897     RefPtr<Range> range = makeRange(visiblePositionRange.start, visiblePositionRange.end);
898     for (TextIterator it(range.get()); !it.atEnd(); it.advance()) {
899         // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)
900         if (it.length())
901             length += it.length();
902         else {
903             // locate the node and starting offset for this replaced range
904             int exception = 0;
905             Node* node = it.range()->startContainer(exception);
906             ASSERT(node == it.range()->endContainer(exception));
907             int offset = it.range()->startOffset(exception);
908
909             if (replacedNodeNeedsCharacter(node->childNode(offset)))
910                 length++;
911         }
912     }
913     
914     return length;
915 }
916
917 VisiblePosition AccessibilityObject::nextWordEnd(const VisiblePosition& visiblePos) const
918 {
919     if (visiblePos.isNull())
920         return VisiblePosition();
921
922     // make sure we move off of a word end
923     VisiblePosition nextVisiblePos = visiblePos.next();
924     if (nextVisiblePos.isNull())
925         return VisiblePosition();
926
927     return endOfWord(nextVisiblePos, LeftWordIfOnBoundary);
928 }
929
930 VisiblePosition AccessibilityObject::previousWordStart(const VisiblePosition& visiblePos) const
931 {
932     if (visiblePos.isNull())
933         return VisiblePosition();
934
935     // make sure we move off of a word start
936     VisiblePosition prevVisiblePos = visiblePos.previous();
937     if (prevVisiblePos.isNull())
938         return VisiblePosition();
939
940     return startOfWord(prevVisiblePos, RightWordIfOnBoundary);
941 }
942
943 VisiblePosition AccessibilityObject::nextLineEndPosition(const VisiblePosition& visiblePos) const
944 {
945     if (visiblePos.isNull())
946         return VisiblePosition();
947
948     // to make sure we move off of a line end
949     VisiblePosition nextVisiblePos = visiblePos.next();
950     if (nextVisiblePos.isNull())
951         return VisiblePosition();
952
953     VisiblePosition endPosition = endOfLine(nextVisiblePos);
954
955     // as long as the position hasn't reached the end of the doc,  keep searching for a valid line end position
956     // There are cases like when the position is next to a floating object that'll return null for end of line. This code will avoid returning null.
957     while (endPosition.isNull() && nextVisiblePos.isNotNull()) {
958         nextVisiblePos = nextVisiblePos.next();
959         endPosition = endOfLine(nextVisiblePos);
960     }
961
962     return endPosition;
963 }
964
965 VisiblePosition AccessibilityObject::previousLineStartPosition(const VisiblePosition& visiblePos) const
966 {
967     if (visiblePos.isNull())
968         return VisiblePosition();
969
970     // make sure we move off of a line start
971     VisiblePosition prevVisiblePos = visiblePos.previous();
972     if (prevVisiblePos.isNull())
973         return VisiblePosition();
974
975     VisiblePosition startPosition = startOfLine(prevVisiblePos);
976
977     // as long as the position hasn't reached the beginning of the doc,  keep searching for a valid line start position
978     // There are cases like when the position is next to a floating object that'll return null for start of line. This code will avoid returning null.
979     if (startPosition.isNull()) {
980         while (startPosition.isNull() && prevVisiblePos.isNotNull()) {
981             prevVisiblePos = prevVisiblePos.previous();
982             startPosition = startOfLine(prevVisiblePos);
983         }
984     } else
985         startPosition = updateAXLineStartForVisiblePosition(startPosition);
986
987     return startPosition;
988 }
989
990 VisiblePosition AccessibilityObject::nextSentenceEndPosition(const VisiblePosition& visiblePos) const
991 {
992     // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)
993     // Related? <rdar://problem/3927736> Text selection broken in 8A336
994     if (visiblePos.isNull())
995         return VisiblePosition();
996
997     // make sure we move off of a sentence end
998     VisiblePosition nextVisiblePos = visiblePos.next();
999     if (nextVisiblePos.isNull())
1000         return VisiblePosition();
1001
1002     // an empty line is considered a sentence. If it's skipped, then the sentence parser will not
1003     // see this empty line.  Instead, return the end position of the empty line.
1004     VisiblePosition endPosition;
1005     
1006     String lineString = plainText(makeRange(startOfLine(nextVisiblePos), endOfLine(nextVisiblePos)).get());
1007     if (lineString.isEmpty())
1008         endPosition = nextVisiblePos;
1009     else
1010         endPosition = endOfSentence(nextVisiblePos);
1011
1012     return endPosition;
1013 }
1014
1015 VisiblePosition AccessibilityObject::previousSentenceStartPosition(const VisiblePosition& visiblePos) const
1016 {
1017     // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)
1018     // Related? <rdar://problem/3927736> Text selection broken in 8A336
1019     if (visiblePos.isNull())
1020         return VisiblePosition();
1021
1022     // make sure we move off of a sentence start
1023     VisiblePosition previousVisiblePos = visiblePos.previous();
1024     if (previousVisiblePos.isNull())
1025         return VisiblePosition();
1026
1027     // treat empty line as a separate sentence.
1028     VisiblePosition startPosition;
1029     
1030     String lineString = plainText(makeRange(startOfLine(previousVisiblePos), endOfLine(previousVisiblePos)).get());
1031     if (lineString.isEmpty())
1032         startPosition = previousVisiblePos;
1033     else
1034         startPosition = startOfSentence(previousVisiblePos);
1035
1036     return startPosition;
1037 }
1038
1039 VisiblePosition AccessibilityObject::nextParagraphEndPosition(const VisiblePosition& visiblePos) const
1040 {
1041     if (visiblePos.isNull())
1042         return VisiblePosition();
1043
1044     // make sure we move off of a paragraph end
1045     VisiblePosition nextPos = visiblePos.next();
1046     if (nextPos.isNull())
1047         return VisiblePosition();
1048
1049     return endOfParagraph(nextPos);
1050 }
1051
1052 VisiblePosition AccessibilityObject::previousParagraphStartPosition(const VisiblePosition& visiblePos) const
1053 {
1054     if (visiblePos.isNull())
1055         return VisiblePosition();
1056
1057     // make sure we move off of a paragraph start
1058     VisiblePosition previousPos = visiblePos.previous();
1059     if (previousPos.isNull())
1060         return VisiblePosition();
1061
1062     return startOfParagraph(previousPos);
1063 }
1064
1065 AccessibilityObject* AccessibilityObject::accessibilityObjectForPosition(const VisiblePosition& visiblePos) const
1066 {
1067     if (visiblePos.isNull())
1068         return 0;
1069
1070     RenderObject* obj = visiblePos.deepEquivalent().deprecatedNode()->renderer();
1071     if (!obj)
1072         return 0;
1073
1074     return obj->document()->axObjectCache()->getOrCreate(obj);
1075 }
1076
1077 #if HAVE(ACCESSIBILITY)
1078 int AccessibilityObject::lineForPosition(const VisiblePosition& visiblePos) const
1079 {
1080     if (visiblePos.isNull() || !node())
1081         return -1;
1082
1083     // If the position is not in the same editable region as this AX object, return -1.
1084     Node* containerNode = visiblePos.deepEquivalent().containerNode();
1085     if (!containerNode->containsIncludingShadowDOM(node()) && !node()->containsIncludingShadowDOM(containerNode))
1086         return -1;
1087
1088     int lineCount = -1;
1089     VisiblePosition currentVisiblePos = visiblePos;
1090     VisiblePosition savedVisiblePos;
1091
1092     // move up until we get to the top
1093     // FIXME: This only takes us to the top of the rootEditableElement, not the top of the
1094     // top document.
1095     do {
1096         savedVisiblePos = currentVisiblePos;
1097         VisiblePosition prevVisiblePos = previousLinePosition(currentVisiblePos, 0, HasEditableAXRole);
1098         currentVisiblePos = prevVisiblePos;
1099         ++lineCount;
1100     }  while (currentVisiblePos.isNotNull() && !(inSameLine(currentVisiblePos, savedVisiblePos)));
1101
1102     return lineCount;
1103 }
1104 #endif
1105
1106 // NOTE: Consider providing this utility method as AX API
1107 PlainTextRange AccessibilityObject::plainTextRangeForVisiblePositionRange(const VisiblePositionRange& positionRange) const
1108 {
1109     int index1 = index(positionRange.start);
1110     int index2 = index(positionRange.end);
1111     if (index1 < 0 || index2 < 0 || index1 > index2)
1112         return PlainTextRange();
1113
1114     return PlainTextRange(index1, index2 - index1);
1115 }
1116
1117 // The composed character range in the text associated with this accessibility object that
1118 // is specified by the given screen coordinates. This parameterized attribute returns the
1119 // complete range of characters (including surrogate pairs of multi-byte glyphs) at the given
1120 // screen coordinates.
1121 // NOTE: This varies from AppKit when the point is below the last line. AppKit returns an
1122 // an error in that case. We return textControl->text().length(), 1. Does this matter?
1123 PlainTextRange AccessibilityObject::doAXRangeForPosition(const IntPoint& point) const
1124 {
1125     int i = index(visiblePositionForPoint(point));
1126     if (i < 0)
1127         return PlainTextRange();
1128
1129     return PlainTextRange(i, 1);
1130 }
1131
1132 // Given a character index, the range of text associated with this accessibility object
1133 // over which the style in effect at that character index applies.
1134 PlainTextRange AccessibilityObject::doAXStyleRangeForIndex(unsigned index) const
1135 {
1136     VisiblePositionRange range = styleRangeForPosition(visiblePositionForIndex(index, false));
1137     return plainTextRangeForVisiblePositionRange(range);
1138 }
1139
1140 // Given an indexed character, the line number of the text associated with this accessibility
1141 // object that contains the character.
1142 unsigned AccessibilityObject::doAXLineForIndex(unsigned index)
1143 {
1144     return lineForPosition(visiblePositionForIndex(index, false));
1145 }
1146
1147 #if HAVE(ACCESSIBILITY)
1148 void AccessibilityObject::updateBackingStore()
1149 {
1150     // Updating the layout may delete this object.
1151     if (Document* document = this->document())
1152         document->updateLayoutIgnorePendingStylesheets();
1153 }
1154 #endif
1155
1156 Document* AccessibilityObject::document() const
1157 {
1158     FrameView* frameView = documentFrameView();
1159     if (!frameView)
1160         return 0;
1161     
1162     return frameView->frame()->document();
1163 }
1164     
1165 Page* AccessibilityObject::page() const
1166 {
1167     Document* document = this->document();
1168     if (!document)
1169         return 0;
1170     return document->page();
1171 }
1172
1173 FrameView* AccessibilityObject::documentFrameView() const 
1174
1175     const AccessibilityObject* object = this;
1176     while (object && !object->isAccessibilityRenderObject()) 
1177         object = object->parentObject();
1178         
1179     if (!object)
1180         return 0;
1181
1182     return object->documentFrameView();
1183 }
1184
1185 #if HAVE(ACCESSIBILITY)
1186 const AccessibilityObject::AccessibilityChildrenVector& AccessibilityObject::children()
1187 {
1188     updateChildrenIfNecessary();
1189
1190     return m_children;
1191 }
1192 #endif
1193
1194 void AccessibilityObject::updateChildrenIfNecessary()
1195 {
1196     if (!hasChildren())
1197         addChildren();    
1198 }
1199     
1200 void AccessibilityObject::clearChildren()
1201 {
1202     // Some objects have weak pointers to their parents and those associations need to be detached.
1203     size_t length = m_children.size();
1204     for (size_t i = 0; i < length; i++)
1205         m_children[i]->detachFromParent();
1206     
1207     m_children.clear();
1208     m_haveChildren = false;
1209 }
1210
1211 AccessibilityObject* AccessibilityObject::anchorElementForNode(Node* node)
1212 {
1213     RenderObject* obj = node->renderer();
1214     if (!obj)
1215         return 0;
1216     
1217     RefPtr<AccessibilityObject> axObj = obj->document()->axObjectCache()->getOrCreate(obj);
1218     Element* anchor = axObj->anchorElement();
1219     if (!anchor)
1220         return 0;
1221     
1222     RenderObject* anchorRenderer = anchor->renderer();
1223     if (!anchorRenderer)
1224         return 0;
1225     
1226     return anchorRenderer->document()->axObjectCache()->getOrCreate(anchorRenderer);
1227 }
1228     
1229 void AccessibilityObject::ariaTreeRows(AccessibilityChildrenVector& result)
1230 {
1231     AccessibilityChildrenVector axChildren = children();
1232     unsigned count = axChildren.size();
1233     for (unsigned k = 0; k < count; ++k) {
1234         AccessibilityObject* obj = axChildren[k].get();
1235         
1236         // Add tree items as the rows.
1237         if (obj->roleValue() == TreeItemRole) 
1238             result.append(obj);
1239
1240         // Now see if this item also has rows hiding inside of it.
1241         obj->ariaTreeRows(result);
1242     }
1243 }
1244     
1245 void AccessibilityObject::ariaTreeItemContent(AccessibilityChildrenVector& result)
1246 {
1247     // The ARIA tree item content are the item that are not other tree items or their containing groups.
1248     AccessibilityChildrenVector axChildren = children();
1249     unsigned count = axChildren.size();
1250     for (unsigned k = 0; k < count; ++k) {
1251         AccessibilityObject* obj = axChildren[k].get();
1252         AccessibilityRole role = obj->roleValue();
1253         if (role == TreeItemRole || role == GroupRole)
1254             continue;
1255         
1256         result.append(obj);
1257     }
1258 }
1259
1260 void AccessibilityObject::ariaTreeItemDisclosedRows(AccessibilityChildrenVector& result)
1261 {
1262     AccessibilityChildrenVector axChildren = children();
1263     unsigned count = axChildren.size();
1264     for (unsigned k = 0; k < count; ++k) {
1265         AccessibilityObject* obj = axChildren[k].get();
1266         
1267         // Add tree items as the rows.
1268         if (obj->roleValue() == TreeItemRole)
1269             result.append(obj);
1270         // If it's not a tree item, then descend into the group to find more tree items.
1271         else 
1272             obj->ariaTreeRows(result);
1273     }    
1274 }
1275
1276 #if HAVE(ACCESSIBILITY)
1277 const String& AccessibilityObject::actionVerb() const
1278 {
1279     // FIXME: Need to add verbs for select elements.
1280     DEFINE_STATIC_LOCAL(const String, buttonAction, (AXButtonActionVerb()));
1281     DEFINE_STATIC_LOCAL(const String, textFieldAction, (AXTextFieldActionVerb()));
1282     DEFINE_STATIC_LOCAL(const String, radioButtonAction, (AXRadioButtonActionVerb()));
1283     DEFINE_STATIC_LOCAL(const String, checkedCheckBoxAction, (AXCheckedCheckBoxActionVerb()));
1284     DEFINE_STATIC_LOCAL(const String, uncheckedCheckBoxAction, (AXUncheckedCheckBoxActionVerb()));
1285     DEFINE_STATIC_LOCAL(const String, linkAction, (AXLinkActionVerb()));
1286     DEFINE_STATIC_LOCAL(const String, menuListAction, (AXMenuListActionVerb()));
1287     DEFINE_STATIC_LOCAL(const String, menuListPopupAction, (AXMenuListPopupActionVerb()));
1288     DEFINE_STATIC_LOCAL(const String, noAction, ());
1289
1290     switch (roleValue()) {
1291     case ButtonRole:
1292     case ToggleButtonRole:
1293         return buttonAction;
1294     case TextFieldRole:
1295     case TextAreaRole:
1296         return textFieldAction;
1297     case RadioButtonRole:
1298         return radioButtonAction;
1299     case CheckBoxRole:
1300         return isChecked() ? checkedCheckBoxAction : uncheckedCheckBoxAction;
1301     case LinkRole:
1302     case WebCoreLinkRole:
1303         return linkAction;
1304     case PopUpButtonRole:
1305         return menuListAction;
1306     case MenuListPopupRole:
1307         return menuListPopupAction;
1308     default:
1309         return noAction;
1310     }
1311 }
1312 #endif
1313
1314 bool AccessibilityObject::ariaIsMultiline() const
1315 {
1316     return equalIgnoringCase(getAttribute(aria_multilineAttr), "true");
1317 }
1318
1319 const AtomicString& AccessibilityObject::invalidStatus() const
1320 {
1321     DEFINE_STATIC_LOCAL(const AtomicString, invalidStatusFalse, ("false", AtomicString::ConstructFromLiteral));
1322     
1323     // aria-invalid can return false (default), grammer, spelling, or true.
1324     const AtomicString& ariaInvalid = getAttribute(aria_invalidAttr);
1325     
1326     // If empty or not present, it should return false.
1327     if (ariaInvalid.isEmpty())
1328         return invalidStatusFalse;
1329     
1330     return ariaInvalid;
1331 }
1332  
1333 bool AccessibilityObject::hasAttribute(const QualifiedName& attribute) const
1334 {
1335     Node* elementNode = node();
1336     if (!elementNode)
1337         return false;
1338     
1339     if (!elementNode->isElementNode())
1340         return false;
1341     
1342     Element* element = toElement(elementNode);
1343     return element->fastHasAttribute(attribute);
1344 }
1345     
1346 const AtomicString& AccessibilityObject::getAttribute(const QualifiedName& attribute) const
1347 {
1348     Node* elementNode = node();
1349     if (!elementNode)
1350         return nullAtom;
1351     
1352     if (!elementNode->isElementNode())
1353         return nullAtom;
1354     
1355     Element* element = toElement(elementNode);
1356     return element->fastGetAttribute(attribute);
1357 }
1358     
1359 // Lacking concrete evidence of orientation, horizontal means width > height. vertical is height > width;
1360 AccessibilityOrientation AccessibilityObject::orientation() const
1361 {
1362     LayoutRect bounds = elementRect();
1363     if (bounds.size().width() > bounds.size().height())
1364         return AccessibilityOrientationHorizontal;
1365     if (bounds.size().height() > bounds.size().width())
1366         return AccessibilityOrientationVertical;
1367
1368     // A tie goes to horizontal.
1369     return AccessibilityOrientationHorizontal;
1370 }    
1371
1372 bool AccessibilityObject::isDescendantOfObject(const AccessibilityObject* axObject) const
1373 {
1374     if (!axObject || !axObject->hasChildren())
1375         return false;
1376
1377     for (const AccessibilityObject* parent = parentObject(); parent; parent = parent->parentObject()) {
1378         if (parent == axObject)
1379             return true;
1380     }
1381     return false;
1382 }
1383
1384 bool AccessibilityObject::isAncestorOfObject(const AccessibilityObject* axObject) const
1385 {
1386     if (!axObject)
1387         return false;
1388
1389     return this == axObject || axObject->isDescendantOfObject(this);
1390 }
1391
1392 AccessibilityObject* AccessibilityObject::firstAnonymousBlockChild() const
1393 {
1394     for (AccessibilityObject* child = firstChild(); child; child = child->nextSibling()) {
1395         if (child->renderer() && child->renderer()->isAnonymousBlock())
1396             return child;
1397     }
1398     return 0;
1399 }
1400
1401 typedef HashMap<String, AccessibilityRole, CaseFoldingHash> ARIARoleMap;
1402
1403 struct RoleEntry {
1404     String ariaRole;
1405     AccessibilityRole webcoreRole;
1406 };
1407
1408 static ARIARoleMap* createARIARoleMap()
1409 {
1410     const RoleEntry roles[] = {
1411         { "alert", ApplicationAlertRole },
1412         { "alertdialog", ApplicationAlertDialogRole },
1413         { "application", LandmarkApplicationRole },
1414         { "article", DocumentArticleRole },
1415         { "banner", LandmarkBannerRole },
1416         { "button", ButtonRole },
1417         { "checkbox", CheckBoxRole },
1418         { "complementary", LandmarkComplementaryRole },
1419         { "contentinfo", LandmarkContentInfoRole },
1420         { "dialog", ApplicationDialogRole },
1421         { "directory", DirectoryRole },
1422         { "grid", TableRole },
1423         { "gridcell", CellRole },
1424         { "columnheader", ColumnHeaderRole },
1425         { "combobox", ComboBoxRole },
1426         { "definition", DefinitionRole },
1427         { "document", DocumentRole },
1428         { "rowheader", RowHeaderRole },
1429         { "group", GroupRole },
1430         { "heading", HeadingRole },
1431         { "img", ImageRole },
1432         { "link", WebCoreLinkRole },
1433         { "list", ListRole },        
1434         { "listitem", ListItemRole },        
1435         { "listbox", ListBoxRole },
1436         { "log", ApplicationLogRole },
1437         // "option" isn't here because it may map to different roles depending on the parent element's role
1438         { "main", LandmarkMainRole },
1439         { "marquee", ApplicationMarqueeRole },
1440         { "math", DocumentMathRole },
1441         { "menu", MenuRole },
1442         { "menubar", MenuBarRole },
1443         { "menuitem", MenuItemRole },
1444         { "menuitemcheckbox", MenuItemRole },
1445         { "menuitemradio", MenuItemRole },
1446         { "note", DocumentNoteRole },
1447         { "navigation", LandmarkNavigationRole },
1448         { "option", ListBoxOptionRole },
1449         { "presentation", PresentationalRole },
1450         { "progressbar", ProgressIndicatorRole },
1451         { "radio", RadioButtonRole },
1452         { "radiogroup", RadioGroupRole },
1453         { "region", DocumentRegionRole },
1454         { "row", RowRole },
1455         { "scrollbar", ScrollBarRole },
1456         { "search", LandmarkSearchRole },
1457         { "separator", SplitterRole },
1458         { "slider", SliderRole },
1459         { "spinbutton", SpinButtonRole },
1460         { "status", ApplicationStatusRole },
1461         { "tab", TabRole },
1462         { "tablist", TabListRole },
1463         { "tabpanel", TabPanelRole },
1464         { "text", StaticTextRole },
1465         { "textbox", TextAreaRole },
1466         { "timer", ApplicationTimerRole },
1467         { "toolbar", ToolbarRole },
1468         { "tooltip", UserInterfaceTooltipRole },
1469         { "tree", TreeRole },
1470         { "treegrid", TreeGridRole },
1471         { "treeitem", TreeItemRole }
1472     };
1473     ARIARoleMap* roleMap = new ARIARoleMap;
1474
1475     for (size_t i = 0; i < WTF_ARRAY_LENGTH(roles); ++i)
1476         roleMap->set(roles[i].ariaRole, roles[i].webcoreRole);
1477     return roleMap;
1478 }
1479
1480 AccessibilityRole AccessibilityObject::ariaRoleToWebCoreRole(const String& value)
1481 {
1482     ASSERT(!value.isEmpty());
1483     
1484     static const ARIARoleMap* roleMap = createARIARoleMap();
1485
1486     Vector<String> roleVector;
1487     value.split(' ', roleVector);
1488     AccessibilityRole role = UnknownRole;
1489     unsigned size = roleVector.size();
1490     for (unsigned i = 0; i < size; ++i) {
1491         String roleName = roleVector[i];
1492         role = roleMap->get(roleName);
1493         if (role)
1494             return role;
1495     }
1496     
1497     return role;
1498 }
1499
1500 bool AccessibilityObject::hasHighlighting() const
1501 {
1502     for (Node* node = this->node(); node; node = node->parentNode()) {
1503         if (node->hasTagName(markTag))
1504             return true;
1505     }
1506     
1507     return false;
1508 }
1509
1510 const AtomicString& AccessibilityObject::placeholderValue() const
1511 {
1512     const AtomicString& placeholder = getAttribute(placeholderAttr);
1513     if (!placeholder.isEmpty())
1514         return placeholder;
1515     
1516     return nullAtom;
1517 }
1518     
1519 bool AccessibilityObject::isInsideARIALiveRegion() const
1520 {
1521     if (supportsARIALiveRegion())
1522         return true;
1523     
1524     for (AccessibilityObject* axParent = parentObject(); axParent; axParent = axParent->parentObject()) {
1525         if (axParent->supportsARIALiveRegion())
1526             return true;
1527     }
1528     
1529     return false;
1530 }
1531
1532 bool AccessibilityObject::supportsARIAAttributes() const
1533 {
1534     return supportsARIALiveRegion()
1535         || supportsARIADragging()
1536         || supportsARIADropping()
1537         || supportsARIAFlowTo()
1538         || supportsARIAOwns()
1539         || hasAttribute(aria_labelAttr);
1540 }
1541     
1542 bool AccessibilityObject::supportsARIALiveRegion() const
1543 {
1544     const AtomicString& liveRegion = ariaLiveRegionStatus();
1545     return equalIgnoringCase(liveRegion, "polite") || equalIgnoringCase(liveRegion, "assertive");
1546 }
1547
1548 AccessibilityObject* AccessibilityObject::elementAccessibilityHitTest(const IntPoint& point) const
1549
1550     // Send the hit test back into the sub-frame if necessary.
1551     if (isAttachment()) {
1552         Widget* widget = widgetForAttachmentView();
1553         // Normalize the point for the widget's bounds.
1554         if (widget && widget->isFrameView())
1555             return axObjectCache()->getOrCreate(widget)->accessibilityHitTest(IntPoint(point - widget->frameRect().location()));
1556     }
1557     
1558     // Check if there are any mock elements that need to be handled.
1559     size_t count = m_children.size();
1560     for (size_t k = 0; k < count; k++) {
1561         if (m_children[k]->isMockObject() && m_children[k]->elementRect().contains(point))
1562             return m_children[k]->elementAccessibilityHitTest(point);
1563     }
1564
1565     return const_cast<AccessibilityObject*>(this); 
1566 }
1567     
1568 AXObjectCache* AccessibilityObject::axObjectCache() const
1569 {
1570     Document* doc = document();
1571     if (doc)
1572         return doc->axObjectCache();
1573     return 0;
1574 }
1575     
1576 AccessibilityObject* AccessibilityObject::focusedUIElement() const
1577 {
1578     Document* doc = document();
1579     if (!doc)
1580         return 0;
1581     
1582     Page* page = doc->page();
1583     if (!page)
1584         return 0;
1585     
1586     return AXObjectCache::focusedUIElementForPage(page);
1587 }
1588     
1589 AccessibilitySortDirection AccessibilityObject::sortDirection() const
1590 {
1591     const AtomicString& sortAttribute = getAttribute(aria_sortAttr);
1592     if (equalIgnoringCase(sortAttribute, "ascending"))
1593         return SortDirectionAscending;
1594     if (equalIgnoringCase(sortAttribute, "descending"))
1595         return SortDirectionDescending;
1596     
1597     return SortDirectionNone;
1598 }
1599
1600 bool AccessibilityObject::supportsRangeValue() const
1601 {
1602     return isProgressIndicator()
1603         || isSlider()
1604         || isScrollbar()
1605         || isSpinButton();
1606 }
1607     
1608 bool AccessibilityObject::supportsARIASetSize() const
1609 {
1610     return hasAttribute(aria_setsizeAttr);
1611 }
1612
1613 bool AccessibilityObject::supportsARIAPosInSet() const
1614 {
1615     return hasAttribute(aria_posinsetAttr);
1616 }
1617     
1618 int AccessibilityObject::ariaSetSize() const
1619 {
1620     return getAttribute(aria_setsizeAttr).toInt();
1621 }
1622
1623 int AccessibilityObject::ariaPosInSet() const
1624 {
1625     return getAttribute(aria_posinsetAttr).toInt();
1626 }
1627     
1628 bool AccessibilityObject::supportsARIAExpanded() const
1629 {
1630     return !getAttribute(aria_expandedAttr).isEmpty();
1631 }
1632     
1633 bool AccessibilityObject::isExpanded() const
1634 {
1635     if (equalIgnoringCase(getAttribute(aria_expandedAttr), "true"))
1636         return true;
1637     
1638     return false;  
1639 }
1640     
1641 AccessibilityButtonState AccessibilityObject::checkboxOrRadioValue() const
1642 {
1643     // If this is a real checkbox or radio button, AccessibilityRenderObject will handle.
1644     // If it's an ARIA checkbox or radio, the aria-checked attribute should be used.
1645
1646     const AtomicString& result = getAttribute(aria_checkedAttr);
1647     if (equalIgnoringCase(result, "true"))
1648         return ButtonStateOn;
1649     if (equalIgnoringCase(result, "mixed"))
1650         return ButtonStateMixed;
1651     
1652     return ButtonStateOff;
1653 }
1654
1655 // This is a 1-dimensional scroll offset helper function that's applied
1656 // separately in the horizontal and vertical directions, because the
1657 // logic is the same. The goal is to compute the best scroll offset
1658 // in order to make an object visible within a viewport.
1659 //
1660 // In case the whole object cannot fit, you can specify a
1661 // subfocus - a smaller region within the object that should
1662 // be prioritized. If the whole object can fit, the subfocus is
1663 // ignored.
1664 //
1665 // Example: the viewport is scrolled to the right just enough
1666 // that the object is in view.
1667 //   Before:
1668 //   +----------Viewport---------+
1669 //                         +---Object---+
1670 //                         +--SubFocus--+
1671 //
1672 //   After:
1673 //          +----------Viewport---------+
1674 //                         +---Object---+
1675 //                         +--SubFocus--+
1676 //
1677 // When constraints cannot be fully satisfied, the min
1678 // (left/top) position takes precedence over the max (right/bottom).
1679 //
1680 // Note that the return value represents the ideal new scroll offset.
1681 // This may be out of range - the calling function should clip this
1682 // to the available range.
1683 static int computeBestScrollOffset(int currentScrollOffset,
1684                                    int subfocusMin, int subfocusMax,
1685                                    int objectMin, int objectMax,
1686                                    int viewportMin, int viewportMax) {
1687     int viewportSize = viewportMax - viewportMin;
1688
1689     // If the focus size is larger than the viewport size, shrink it in the
1690     // direction of subfocus.
1691     if (objectMax - objectMin > viewportSize) {
1692         // Subfocus must be within focus:
1693         subfocusMin = std::max(subfocusMin, objectMin);
1694         subfocusMax = std::min(subfocusMax, objectMax);
1695
1696         // Subfocus must be no larger than the viewport size; favor top/left.
1697         if (subfocusMax - subfocusMin > viewportSize)
1698             subfocusMax = subfocusMin + viewportSize;
1699
1700         if (subfocusMin + viewportSize > objectMax)
1701             objectMin = objectMax - viewportSize;
1702         else {
1703             objectMin = subfocusMin;
1704             objectMax = subfocusMin + viewportSize;
1705         }
1706     }
1707
1708     // Exit now if the focus is already within the viewport.
1709     if (objectMin - currentScrollOffset >= viewportMin
1710         && objectMax - currentScrollOffset <= viewportMax)
1711         return currentScrollOffset;
1712
1713     // Scroll left if we're too far to the right.
1714     if (objectMax - currentScrollOffset > viewportMax)
1715         return objectMax - viewportMax;
1716
1717     // Scroll right if we're too far to the left.
1718     if (objectMin - currentScrollOffset < viewportMin)
1719         return objectMin - viewportMin;
1720
1721     ASSERT_NOT_REACHED();
1722
1723     // This shouldn't happen.
1724     return currentScrollOffset;
1725 }
1726
1727 bool AccessibilityObject::isOnscreen() const
1728 {   
1729     bool isOnscreen = true;
1730
1731     // To figure out if the element is onscreen, we start by building of a stack starting with the
1732     // element, and then include every scrollable parent in the hierarchy.
1733     Vector<const AccessibilityObject*> objects;
1734     
1735     objects.append(this);
1736     for (AccessibilityObject* parentObject = this->parentObject(); parentObject; parentObject = parentObject->parentObject()) {
1737         if (parentObject->getScrollableAreaIfScrollable())
1738             objects.append(parentObject);
1739     }
1740
1741     // Now, go back through that chain and make sure each inner object is within the
1742     // visible bounds of the outer object.
1743     size_t levels = objects.size() - 1;
1744     
1745     for (size_t i = levels; i >= 1; i--) {
1746         const AccessibilityObject* outer = objects[i];
1747         const AccessibilityObject* inner = objects[i - 1];
1748         const IntRect outerRect = i < levels ? pixelSnappedIntRect(outer->boundingBoxRect()) : outer->getScrollableAreaIfScrollable()->visibleContentRect();
1749         const IntRect innerRect = pixelSnappedIntRect(inner->isAccessibilityScrollView() ? inner->parentObject()->boundingBoxRect() : inner->boundingBoxRect());
1750         
1751         if (!outerRect.intersects(innerRect)) {
1752             isOnscreen = false;
1753             break;
1754         }
1755     }
1756     
1757     return isOnscreen;
1758 }
1759
1760 void AccessibilityObject::scrollToMakeVisible() const
1761 {
1762     IntRect objectRect = pixelSnappedIntRect(boundingBoxRect());
1763     objectRect.setLocation(IntPoint());
1764     scrollToMakeVisibleWithSubFocus(objectRect);
1765 }
1766
1767 void AccessibilityObject::scrollToMakeVisibleWithSubFocus(const IntRect& subfocus) const
1768 {
1769     // Search up the parent chain until we find the first one that's scrollable.
1770     AccessibilityObject* scrollParent = parentObject();
1771     ScrollableArea* scrollableArea;
1772     for (scrollableArea = 0;
1773          scrollParent && !(scrollableArea = scrollParent->getScrollableAreaIfScrollable());
1774          scrollParent = scrollParent->parentObject()) { }
1775     if (!scrollableArea)
1776         return;
1777
1778     LayoutRect objectRect = boundingBoxRect();
1779     IntPoint scrollPosition = scrollableArea->scrollPosition();
1780     IntRect scrollVisibleRect = scrollableArea->visibleContentRect();
1781
1782     int desiredX = computeBestScrollOffset(
1783         scrollPosition.x(),
1784         objectRect.x() + subfocus.x(), objectRect.x() + subfocus.maxX(),
1785         objectRect.x(), objectRect.maxX(),
1786         0, scrollVisibleRect.width());
1787     int desiredY = computeBestScrollOffset(
1788         scrollPosition.y(),
1789         objectRect.y() + subfocus.y(), objectRect.y() + subfocus.maxY(),
1790         objectRect.y(), objectRect.maxY(),
1791         0, scrollVisibleRect.height());
1792
1793     scrollParent->scrollTo(IntPoint(desiredX, desiredY));
1794
1795     // Recursively make sure the scroll parent itself is visible.
1796     if (scrollParent->parentObject())
1797         scrollParent->scrollToMakeVisible();
1798 }
1799
1800 void AccessibilityObject::scrollToGlobalPoint(const IntPoint& globalPoint) const
1801 {
1802     // Search up the parent chain and create a vector of all scrollable parent objects
1803     // and ending with this object itself.
1804     Vector<const AccessibilityObject*> objects;
1805
1806     objects.append(this);
1807     for (AccessibilityObject* parentObject = this->parentObject(); parentObject; parentObject = parentObject->parentObject()) {
1808         if (parentObject->getScrollableAreaIfScrollable())
1809             objects.append(parentObject);
1810     }
1811
1812     objects.reverse();
1813
1814     // Start with the outermost scrollable (the main window) and try to scroll the
1815     // next innermost object to the given point.
1816     int offsetX = 0, offsetY = 0;
1817     IntPoint point = globalPoint;
1818     size_t levels = objects.size() - 1;
1819     for (size_t i = 0; i < levels; i++) {
1820         const AccessibilityObject* outer = objects[i];
1821         const AccessibilityObject* inner = objects[i + 1];
1822
1823         ScrollableArea* scrollableArea = outer->getScrollableAreaIfScrollable();
1824
1825         LayoutRect innerRect = inner->isAccessibilityScrollView() ? inner->parentObject()->boundingBoxRect() : inner->boundingBoxRect();
1826         LayoutRect objectRect = innerRect;
1827         IntPoint scrollPosition = scrollableArea->scrollPosition();
1828
1829         // Convert the object rect into local coordinates.
1830         objectRect.move(offsetX, offsetY);
1831         if (!outer->isAccessibilityScrollView())
1832             objectRect.move(scrollPosition.x(), scrollPosition.y());
1833
1834         int desiredX = computeBestScrollOffset(
1835             0,
1836             objectRect.x(), objectRect.maxX(),
1837             objectRect.x(), objectRect.maxX(),
1838             point.x(), point.x());
1839         int desiredY = computeBestScrollOffset(
1840             0,
1841             objectRect.y(), objectRect.maxY(),
1842             objectRect.y(), objectRect.maxY(),
1843             point.y(), point.y());
1844         outer->scrollTo(IntPoint(desiredX, desiredY));
1845
1846         if (outer->isAccessibilityScrollView() && !inner->isAccessibilityScrollView()) {
1847             // If outer object we just scrolled is a scroll view (main window or iframe) but the
1848             // inner object is not, keep track of the coordinate transformation to apply to
1849             // future nested calculations.
1850             scrollPosition = scrollableArea->scrollPosition();
1851             offsetX -= (scrollPosition.x() + point.x());
1852             offsetY -= (scrollPosition.y() + point.y());
1853             point.move(scrollPosition.x() - innerRect.x(),
1854                        scrollPosition.y() - innerRect.y());
1855         } else if (inner->isAccessibilityScrollView()) {
1856             // Otherwise, if the inner object is a scroll view, reset the coordinate transformation.
1857             offsetX = 0;
1858             offsetY = 0;
1859         }
1860     }
1861 }
1862
1863 bool AccessibilityObject::lastKnownIsIgnoredValue()
1864 {
1865     if (m_lastKnownIsIgnoredValue == DefaultBehavior)
1866         m_lastKnownIsIgnoredValue = accessibilityIsIgnored() ? IgnoreObject : IncludeObject;
1867
1868     return m_lastKnownIsIgnoredValue == IgnoreObject;
1869 }
1870
1871 void AccessibilityObject::setLastKnownIsIgnoredValue(bool isIgnored)
1872 {
1873     m_lastKnownIsIgnoredValue = isIgnored ? IgnoreObject : IncludeObject;
1874 }
1875
1876 void AccessibilityObject::notifyIfIgnoredValueChanged()
1877 {
1878     bool isIgnored = accessibilityIsIgnored();
1879     if (lastKnownIsIgnoredValue() != isIgnored) {
1880         axObjectCache()->childrenChanged(parentObject());
1881         setLastKnownIsIgnoredValue(isIgnored);
1882     }
1883 }
1884
1885 bool AccessibilityObject::ariaPressedIsPresent() const
1886 {
1887     return !getAttribute(aria_pressedAttr).isEmpty();
1888 }
1889
1890 TextIteratorBehavior AccessibilityObject::textIteratorBehaviorForTextRange() const
1891 {
1892     TextIteratorBehavior behavior = TextIteratorIgnoresStyleVisibility;
1893     
1894 #if PLATFORM(GTK)
1895     // We need to emit replaced elements for GTK, and present
1896     // them with the 'object replacement character' (0xFFFC).
1897     behavior = static_cast<TextIteratorBehavior>(behavior | TextIteratorEmitsObjectReplacementCharacters);
1898 #endif
1899     
1900     return behavior;
1901 }
1902     
1903 AccessibilityRole AccessibilityObject::buttonRoleType() const
1904 {
1905     // If aria-pressed is present, then it should be exposed as a toggle button.
1906     // http://www.w3.org/TR/wai-aria/states_and_properties#aria-pressed
1907     if (ariaPressedIsPresent())
1908         return ToggleButtonRole;
1909     if (ariaHasPopup())
1910         return PopUpButtonRole;
1911     // We don't contemplate RadioButtonRole, as it depends on the input
1912     // type.
1913
1914     return ButtonRole;
1915 }
1916
1917 bool AccessibilityObject::isButton() const
1918 {
1919     AccessibilityRole role = roleValue();
1920
1921     return role == ButtonRole || role == PopUpButtonRole || role == ToggleButtonRole;
1922 }
1923
1924 bool AccessibilityObject::accessibilityIsIgnoredByDefault() const
1925 {
1926     return defaultObjectInclusion() == IgnoreObject;
1927 }
1928
1929 bool AccessibilityObject::ariaIsHidden() const
1930 {
1931     if (equalIgnoringCase(getAttribute(aria_hiddenAttr), "true"))
1932         return true;
1933     
1934     for (AccessibilityObject* object = parentObject(); object; object = object->parentObject()) {
1935         if (equalIgnoringCase(object->getAttribute(aria_hiddenAttr), "true"))
1936             return true;
1937     }
1938     
1939     return false;
1940 }
1941
1942 AccessibilityObjectInclusion AccessibilityObject::defaultObjectInclusion() const
1943 {
1944     if (ariaIsHidden())
1945         return IgnoreObject;
1946     
1947     if (isPresentationalChildOfAriaRole())
1948         return IgnoreObject;
1949     
1950     return accessibilityPlatformIncludesObject();
1951 }
1952     
1953 bool AccessibilityObject::accessibilityIsIgnored() const
1954 {
1955     AXComputedObjectAttributeCache* attributeCache = axObjectCache()->computedObjectAttributeCache();
1956     if (attributeCache) {
1957         AccessibilityObjectInclusion ignored = attributeCache->getIgnored(axObjectID());
1958         switch (ignored) {
1959         case IgnoreObject:
1960             return true;
1961         case IncludeObject:
1962             return false;
1963         case DefaultBehavior:
1964             break;
1965         }
1966     }
1967
1968     bool result = computeAccessibilityIsIgnored();
1969
1970     if (attributeCache)
1971         attributeCache->setIgnored(axObjectID(), result ? IgnoreObject : IncludeObject);
1972
1973     return result;
1974 }
1975
1976 } // namespace WebCore