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