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
68using namespace std;
69
70namespace WebCore {
71
72using namespace HTMLNames;
73
74AccessibilityObject::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
85AccessibilityObject::~AccessibilityObject()
86{
87    ASSERT(isDetached());
88}
89
90void 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
101bool AccessibilityObject::isDetached() const
102{
103#if HAVE(ACCESSIBILITY)
104    return !wrapper();
105#else
106    return true;
107#endif
108}
109
110bool 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
244bool 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
260bool AccessibilityObject::isAccessibilityTextSearchMatch(AccessibilityObject* axObject, AccessibilitySearchCriteria* criteria)
261{
262    if (!axObject || !criteria)
263        return false;
264
265    return axObject->accessibilityObjectContainsText(criteria->searchText);
266}
267
268bool 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
278bool AccessibilityObject::isBlockquote() const
279{
280    return node() && node()->hasTagName(blockquoteTag);
281}
282
283bool 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
295bool AccessibilityObject::isARIATextControl() const
296{
297    return ariaRoleAttribute() == TextAreaRole || ariaRoleAttribute() == TextFieldRole;
298}
299
300bool 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
313bool 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
353int 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
364AccessibilityObject* AccessibilityObject::parentObjectUnignored() const
365{
366    AccessibilityObject* parent;
367    for (parent = parentObject(); parent && parent->accessibilityIsIgnored(); parent = parent->parentObject()) {
368    }
369
370    return parent;
371}
372
373AccessibilityObject* 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
400static 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
419static 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.
453bool 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
466void 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
523bool AccessibilityObject::isARIAInput(AccessibilityRole ariaRole)
524{
525    return ariaRole == RadioButtonRole || ariaRole == CheckBoxRole || ariaRole == TextFieldRole;
526}
527
528bool AccessibilityObject::isARIAControl(AccessibilityRole ariaRole)
529{
530    return isARIAInput(ariaRole) || ariaRole == TextAreaRole || ariaRole == ButtonRole
531    || ariaRole == ComboBoxRole || ariaRole == SliderRole;
532}
533
534bool 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
547IntPoint AccessibilityObject::clickPoint()
548{
549    LayoutRect rect = elementRect();
550    return roundedIntPoint(LayoutPoint(rect.x() + rect.width() / 2, rect.y() + rect.height() / 2));
551}
552
553IntRect 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
575bool 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
588Frame* AccessibilityObject::mainFrame() const
589{
590    Document* document = topDocument();
591    if (!document)
592        return 0;
593
594    Page* page = document->page();
595    if (!page)
596        return 0;
597
598    return page->mainFrame();
599}
600
601Document* AccessibilityObject::topDocument() const
602{
603    if (!document())
604        return 0;
605    return document()->topDocument();
606}
607
608String AccessibilityObject::language() const
609{
610    const AtomicString& lang = getAttribute(langAttr);
611    if (!lang.isEmpty())
612        return lang;
613
614    AccessibilityObject* parent = parentObject();
615
616    // as a last resort, fall back to the content language specified in the meta tag
617    if (!parent) {
618        Document* doc = document();
619        if (doc)
620            return doc->contentLanguage();
621        return nullAtom;
622    }
623
624    return parent->language();
625}
626
627VisiblePositionRange AccessibilityObject::visiblePositionRangeForUnorderedPositions(const VisiblePosition& visiblePos1, const VisiblePosition& visiblePos2) const
628{
629    if (visiblePos1.isNull() || visiblePos2.isNull())
630        return VisiblePositionRange();
631
632    VisiblePosition startPos;
633    VisiblePosition endPos;
634    bool alreadyInOrder;
635
636    // upstream is ordered before downstream for the same position
637    if (visiblePos1 == visiblePos2 && visiblePos2.affinity() == UPSTREAM)
638        alreadyInOrder = false;
639
640    // use selection order to see if the positions are in order
641    else
642        alreadyInOrder = VisibleSelection(visiblePos1, visiblePos2).isBaseFirst();
643
644    if (alreadyInOrder) {
645        startPos = visiblePos1;
646        endPos = visiblePos2;
647    } else {
648        startPos = visiblePos2;
649        endPos = visiblePos1;
650    }
651
652    return VisiblePositionRange(startPos, endPos);
653}
654
655VisiblePositionRange AccessibilityObject::positionOfLeftWord(const VisiblePosition& visiblePos) const
656{
657    VisiblePosition startPosition = startOfWord(visiblePos, LeftWordIfOnBoundary);
658    VisiblePosition endPosition = endOfWord(startPosition);
659    return VisiblePositionRange(startPosition, endPosition);
660}
661
662VisiblePositionRange AccessibilityObject::positionOfRightWord(const VisiblePosition& visiblePos) const
663{
664    VisiblePosition startPosition = startOfWord(visiblePos, RightWordIfOnBoundary);
665    VisiblePosition endPosition = endOfWord(startPosition);
666    return VisiblePositionRange(startPosition, endPosition);
667}
668
669static VisiblePosition updateAXLineStartForVisiblePosition(const VisiblePosition& visiblePosition)
670{
671    // A line in the accessibility sense should include floating objects, such as aligned image, as part of a line.
672    // So let's update the position to include that.
673    VisiblePosition tempPosition;
674    VisiblePosition startPosition = visiblePosition;
675    while (true) {
676        tempPosition = startPosition.previous();
677        if (tempPosition.isNull())
678            break;
679        Position p = tempPosition.deepEquivalent();
680        RenderObject* renderer = p.deprecatedNode()->renderer();
681        if (!renderer || (renderer->isRenderBlock() && !p.deprecatedEditingOffset()))
682            break;
683        if (!RenderedPosition(tempPosition).isNull())
684            break;
685        startPosition = tempPosition;
686    }
687
688    return startPosition;
689}
690
691VisiblePositionRange AccessibilityObject::leftLineVisiblePositionRange(const VisiblePosition& visiblePos) const
692{
693    if (visiblePos.isNull())
694        return VisiblePositionRange();
695
696    // make a caret selection for the position before marker position (to make sure
697    // we move off of a line start)
698    VisiblePosition prevVisiblePos = visiblePos.previous();
699    if (prevVisiblePos.isNull())
700        return VisiblePositionRange();
701
702    VisiblePosition startPosition = startOfLine(prevVisiblePos);
703
704    // keep searching for a valid line start position.  Unless the VisiblePosition is at the very beginning, there should
705    // always be a valid line range.  However, startOfLine will return null for position next to a floating object,
706    // since floating object doesn't really belong to any line.
707    // This check will reposition the marker before the floating object, to ensure we get a line start.
708    if (startPosition.isNull()) {
709        while (startPosition.isNull() && prevVisiblePos.isNotNull()) {
710            prevVisiblePos = prevVisiblePos.previous();
711            startPosition = startOfLine(prevVisiblePos);
712        }
713    } else
714        startPosition = updateAXLineStartForVisiblePosition(startPosition);
715
716    VisiblePosition endPosition = endOfLine(prevVisiblePos);
717    return VisiblePositionRange(startPosition, endPosition);
718}
719
720VisiblePositionRange AccessibilityObject::rightLineVisiblePositionRange(const VisiblePosition& visiblePos) const
721{
722    if (visiblePos.isNull())
723        return VisiblePositionRange();
724
725    // make sure we move off of a line end
726    VisiblePosition nextVisiblePos = visiblePos.next();
727    if (nextVisiblePos.isNull())
728        return VisiblePositionRange();
729
730    VisiblePosition startPosition = startOfLine(nextVisiblePos);
731
732    // fetch for a valid line start position
733    if (startPosition.isNull()) {
734        startPosition = visiblePos;
735        nextVisiblePos = nextVisiblePos.next();
736    } else
737        startPosition = updateAXLineStartForVisiblePosition(startPosition);
738
739    VisiblePosition endPosition = endOfLine(nextVisiblePos);
740
741    // as long as the position hasn't reached the end of the doc,  keep searching for a valid line end position
742    // Unless the VisiblePosition is at the very end, there should always be a valid line range.  However, endOfLine will
743    // return null for position by a floating object, since floating object doesn't really belong to any line.
744    // This check will reposition the marker after the floating object, to ensure we get a line end.
745    while (endPosition.isNull() && nextVisiblePos.isNotNull()) {
746        nextVisiblePos = nextVisiblePos.next();
747        endPosition = endOfLine(nextVisiblePos);
748    }
749
750    return VisiblePositionRange(startPosition, endPosition);
751}
752
753VisiblePositionRange AccessibilityObject::sentenceForPosition(const VisiblePosition& visiblePos) const
754{
755    // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)
756    // Related? <rdar://problem/3927736> Text selection broken in 8A336
757    VisiblePosition startPosition = startOfSentence(visiblePos);
758    VisiblePosition endPosition = endOfSentence(startPosition);
759    return VisiblePositionRange(startPosition, endPosition);
760}
761
762VisiblePositionRange AccessibilityObject::paragraphForPosition(const VisiblePosition& visiblePos) const
763{
764    VisiblePosition startPosition = startOfParagraph(visiblePos);
765    VisiblePosition endPosition = endOfParagraph(startPosition);
766    return VisiblePositionRange(startPosition, endPosition);
767}
768
769static VisiblePosition startOfStyleRange(const VisiblePosition& visiblePos)
770{
771    RenderObject* renderer = visiblePos.deepEquivalent().deprecatedNode()->renderer();
772    RenderObject* startRenderer = renderer;
773    RenderStyle* style = renderer->style();
774
775    // traverse backward by renderer to look for style change
776    for (RenderObject* r = renderer->previousInPreOrder(); r; r = r->previousInPreOrder()) {
777        // skip non-leaf nodes
778        if (r->firstChild())
779            continue;
780
781        // stop at style change
782        if (r->style() != style)
783            break;
784
785        // remember match
786        startRenderer = r;
787    }
788
789    return firstPositionInOrBeforeNode(startRenderer->node());
790}
791
792static VisiblePosition endOfStyleRange(const VisiblePosition& visiblePos)
793{
794    RenderObject* renderer = visiblePos.deepEquivalent().deprecatedNode()->renderer();
795    RenderObject* endRenderer = renderer;
796    RenderStyle* style = renderer->style();
797
798    // traverse forward by renderer to look for style change
799    for (RenderObject* r = renderer->nextInPreOrder(); r; r = r->nextInPreOrder()) {
800        // skip non-leaf nodes
801        if (r->firstChild())
802            continue;
803
804        // stop at style change
805        if (r->style() != style)
806            break;
807
808        // remember match
809        endRenderer = r;
810    }
811
812    return lastPositionInOrAfterNode(endRenderer->node());
813}
814
815VisiblePositionRange AccessibilityObject::styleRangeForPosition(const VisiblePosition& visiblePos) const
816{
817    if (visiblePos.isNull())
818        return VisiblePositionRange();
819
820    return VisiblePositionRange(startOfStyleRange(visiblePos), endOfStyleRange(visiblePos));
821}
822
823// NOTE: Consider providing this utility method as AX API
824VisiblePositionRange AccessibilityObject::visiblePositionRangeForRange(const PlainTextRange& range) const
825{
826    unsigned textLength = getLengthForTextRange();
827    if (range.start + range.length > textLength)
828        return VisiblePositionRange();
829
830    VisiblePosition startPosition = visiblePositionForIndex(range.start);
831    startPosition.setAffinity(DOWNSTREAM);
832    VisiblePosition endPosition = visiblePositionForIndex(range.start + range.length);
833    return VisiblePositionRange(startPosition, endPosition);
834}
835
836static bool replacedNodeNeedsCharacter(Node* replacedNode)
837{
838    // we should always be given a rendered node and a replaced node, but be safe
839    // replaced nodes are either attachments (widgets) or images
840    if (!replacedNode || !isRendererReplacedElement(replacedNode->renderer()) || replacedNode->isTextNode())
841        return false;
842
843    // create an AX object, but skip it if it is not supposed to be seen
844    AccessibilityObject* object = replacedNode->renderer()->document()->axObjectCache()->getOrCreate(replacedNode);
845    if (object->accessibilityIsIgnored())
846        return false;
847
848    return true;
849}
850
851// Finds a RenderListItem parent give a node.
852static RenderListItem* renderListItemContainerForNode(Node* node)
853{
854    for (; node; node = node->parentNode()) {
855        RenderBoxModelObject* renderer = node->renderBoxModelObject();
856        if (renderer && renderer->isListItem())
857            return toRenderListItem(renderer);
858    }
859    return 0;
860}
861
862// Returns the text associated with a list marker if this node is contained within a list item.
863String AccessibilityObject::listMarkerTextForNodeAndPosition(Node* node, const VisiblePosition& visiblePositionStart) const
864{
865    // If the range does not contain the start of the line, the list marker text should not be included.
866    if (!isStartOfLine(visiblePositionStart))
867        return String();
868
869    RenderListItem* listItem = renderListItemContainerForNode(node);
870    if (!listItem)
871        return String();
872
873    // If this is in a list item, we need to manually add the text for the list marker
874    // because a RenderListMarker does not have a Node equivalent and thus does not appear
875    // when iterating text.
876    return listItem->markerTextWithSuffix();
877}
878
879String AccessibilityObject::stringForVisiblePositionRange(const VisiblePositionRange& visiblePositionRange) const
880{
881    if (visiblePositionRange.isNull())
882        return String();
883
884    StringBuilder builder;
885    RefPtr<Range> range = makeRange(visiblePositionRange.start, visiblePositionRange.end);
886    for (TextIterator it(range.get()); !it.atEnd(); it.advance()) {
887        // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)
888        if (it.length()) {
889            // Add a textual representation for list marker text
890            String listMarkerText = listMarkerTextForNodeAndPosition(it.node(), visiblePositionRange.start);
891            if (!listMarkerText.isEmpty())
892                builder.append(listMarkerText);
893
894            it.appendTextToStringBuilder(builder);
895        } else {
896            // locate the node and starting offset for this replaced range
897            int exception = 0;
898            Node* node = it.range()->startContainer(exception);
899            ASSERT(node == it.range()->endContainer(exception));
900            int offset = it.range()->startOffset(exception);
901
902            if (replacedNodeNeedsCharacter(node->childNode(offset)))
903                builder.append(objectReplacementCharacter);
904        }
905    }
906
907    return builder.toString();
908}
909
910int AccessibilityObject::lengthForVisiblePositionRange(const VisiblePositionRange& visiblePositionRange) const
911{
912    // FIXME: Multi-byte support
913    if (visiblePositionRange.isNull())
914        return -1;
915
916    int length = 0;
917    RefPtr<Range> range = makeRange(visiblePositionRange.start, visiblePositionRange.end);
918    for (TextIterator it(range.get()); !it.atEnd(); it.advance()) {
919        // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)
920        if (it.length())
921            length += it.length();
922        else {
923            // locate the node and starting offset for this replaced range
924            int exception = 0;
925            Node* node = it.range()->startContainer(exception);
926            ASSERT(node == it.range()->endContainer(exception));
927            int offset = it.range()->startOffset(exception);
928
929            if (replacedNodeNeedsCharacter(node->childNode(offset)))
930                length++;
931        }
932    }
933
934    return length;
935}
936
937VisiblePosition AccessibilityObject::visiblePositionForBounds(const IntRect& rect, AccessibilityVisiblePositionForBounds visiblePositionForBounds) const
938{
939    if (rect.isEmpty())
940        return VisiblePosition();
941
942    Frame* mainFrame = this->mainFrame();
943    if (!mainFrame)
944        return VisiblePosition();
945
946    // FIXME: Add support for right-to-left languages.
947    IntPoint corner = (visiblePositionForBounds == FirstVisiblePositionForBounds) ? rect.minXMinYCorner() : rect.maxXMaxYCorner();
948    VisiblePosition position = mainFrame->visiblePositionForPoint(corner);
949
950    if (rect.contains(position.absoluteCaretBounds().center()))
951        return position;
952
953    // If the initial position is located outside the bounds adjust it incrementally as needed.
954    VisiblePosition nextPosition = position.next();
955    VisiblePosition previousPosition = position.previous();
956    while (nextPosition.isNotNull() || previousPosition.isNotNull()) {
957        if (rect.contains(nextPosition.absoluteCaretBounds().center()))
958            return nextPosition;
959        if (rect.contains(previousPosition.absoluteCaretBounds().center()))
960            return previousPosition;
961
962        nextPosition = nextPosition.next();
963        previousPosition = previousPosition.previous();
964    }
965
966    return VisiblePosition();
967}
968
969VisiblePosition AccessibilityObject::nextWordEnd(const VisiblePosition& visiblePos) const
970{
971    if (visiblePos.isNull())
972        return VisiblePosition();
973
974    // make sure we move off of a word end
975    VisiblePosition nextVisiblePos = visiblePos.next();
976    if (nextVisiblePos.isNull())
977        return VisiblePosition();
978
979    return endOfWord(nextVisiblePos, LeftWordIfOnBoundary);
980}
981
982VisiblePosition AccessibilityObject::previousWordStart(const VisiblePosition& visiblePos) const
983{
984    if (visiblePos.isNull())
985        return VisiblePosition();
986
987    // make sure we move off of a word start
988    VisiblePosition prevVisiblePos = visiblePos.previous();
989    if (prevVisiblePos.isNull())
990        return VisiblePosition();
991
992    return startOfWord(prevVisiblePos, RightWordIfOnBoundary);
993}
994
995VisiblePosition AccessibilityObject::nextLineEndPosition(const VisiblePosition& visiblePos) const
996{
997    if (visiblePos.isNull())
998        return VisiblePosition();
999
1000    // to make sure we move off of a line end
1001    VisiblePosition nextVisiblePos = visiblePos.next();
1002    if (nextVisiblePos.isNull())
1003        return VisiblePosition();
1004
1005    VisiblePosition endPosition = endOfLine(nextVisiblePos);
1006
1007    // as long as the position hasn't reached the end of the doc,  keep searching for a valid line end position
1008    // 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.
1009    while (endPosition.isNull() && nextVisiblePos.isNotNull()) {
1010        nextVisiblePos = nextVisiblePos.next();
1011        endPosition = endOfLine(nextVisiblePos);
1012    }
1013
1014    return endPosition;
1015}
1016
1017VisiblePosition AccessibilityObject::previousLineStartPosition(const VisiblePosition& visiblePos) const
1018{
1019    if (visiblePos.isNull())
1020        return VisiblePosition();
1021
1022    // make sure we move off of a line start
1023    VisiblePosition prevVisiblePos = visiblePos.previous();
1024    if (prevVisiblePos.isNull())
1025        return VisiblePosition();
1026
1027    VisiblePosition startPosition = startOfLine(prevVisiblePos);
1028
1029    // as long as the position hasn't reached the beginning of the doc,  keep searching for a valid line start position
1030    // 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.
1031    if (startPosition.isNull()) {
1032        while (startPosition.isNull() && prevVisiblePos.isNotNull()) {
1033            prevVisiblePos = prevVisiblePos.previous();
1034            startPosition = startOfLine(prevVisiblePos);
1035        }
1036    } else
1037        startPosition = updateAXLineStartForVisiblePosition(startPosition);
1038
1039    return startPosition;
1040}
1041
1042VisiblePosition AccessibilityObject::nextSentenceEndPosition(const VisiblePosition& visiblePos) const
1043{
1044    // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)
1045    // Related? <rdar://problem/3927736> Text selection broken in 8A336
1046    if (visiblePos.isNull())
1047        return VisiblePosition();
1048
1049    // make sure we move off of a sentence end
1050    VisiblePosition nextVisiblePos = visiblePos.next();
1051    if (nextVisiblePos.isNull())
1052        return VisiblePosition();
1053
1054    // an empty line is considered a sentence. If it's skipped, then the sentence parser will not
1055    // see this empty line.  Instead, return the end position of the empty line.
1056    VisiblePosition endPosition;
1057
1058    String lineString = plainText(makeRange(startOfLine(nextVisiblePos), endOfLine(nextVisiblePos)).get());
1059    if (lineString.isEmpty())
1060        endPosition = nextVisiblePos;
1061    else
1062        endPosition = endOfSentence(nextVisiblePos);
1063
1064    return endPosition;
1065}
1066
1067VisiblePosition AccessibilityObject::previousSentenceStartPosition(const VisiblePosition& visiblePos) const
1068{
1069    // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)
1070    // Related? <rdar://problem/3927736> Text selection broken in 8A336
1071    if (visiblePos.isNull())
1072        return VisiblePosition();
1073
1074    // make sure we move off of a sentence start
1075    VisiblePosition previousVisiblePos = visiblePos.previous();
1076    if (previousVisiblePos.isNull())
1077        return VisiblePosition();
1078
1079    // treat empty line as a separate sentence.
1080    VisiblePosition startPosition;
1081
1082    String lineString = plainText(makeRange(startOfLine(previousVisiblePos), endOfLine(previousVisiblePos)).get());
1083    if (lineString.isEmpty())
1084        startPosition = previousVisiblePos;
1085    else
1086        startPosition = startOfSentence(previousVisiblePos);
1087
1088    return startPosition;
1089}
1090
1091VisiblePosition AccessibilityObject::nextParagraphEndPosition(const VisiblePosition& visiblePos) const
1092{
1093    if (visiblePos.isNull())
1094        return VisiblePosition();
1095
1096    // make sure we move off of a paragraph end
1097    VisiblePosition nextPos = visiblePos.next();
1098    if (nextPos.isNull())
1099        return VisiblePosition();
1100
1101    return endOfParagraph(nextPos);
1102}
1103
1104VisiblePosition AccessibilityObject::previousParagraphStartPosition(const VisiblePosition& visiblePos) const
1105{
1106    if (visiblePos.isNull())
1107        return VisiblePosition();
1108
1109    // make sure we move off of a paragraph start
1110    VisiblePosition previousPos = visiblePos.previous();
1111    if (previousPos.isNull())
1112        return VisiblePosition();
1113
1114    return startOfParagraph(previousPos);
1115}
1116
1117AccessibilityObject* AccessibilityObject::accessibilityObjectForPosition(const VisiblePosition& visiblePos) const
1118{
1119    if (visiblePos.isNull())
1120        return 0;
1121
1122    RenderObject* obj = visiblePos.deepEquivalent().deprecatedNode()->renderer();
1123    if (!obj)
1124        return 0;
1125
1126    return obj->document()->axObjectCache()->getOrCreate(obj);
1127}
1128
1129#if HAVE(ACCESSIBILITY)
1130int AccessibilityObject::lineForPosition(const VisiblePosition& visiblePos) const
1131{
1132    if (visiblePos.isNull() || !node())
1133        return -1;
1134
1135    // If the position is not in the same editable region as this AX object, return -1.
1136    Node* containerNode = visiblePos.deepEquivalent().containerNode();
1137    if (!containerNode->containsIncludingShadowDOM(node()) && !node()->containsIncludingShadowDOM(containerNode))
1138        return -1;
1139
1140    int lineCount = -1;
1141    VisiblePosition currentVisiblePos = visiblePos;
1142    VisiblePosition savedVisiblePos;
1143
1144    // move up until we get to the top
1145    // FIXME: This only takes us to the top of the rootEditableElement, not the top of the
1146    // top document.
1147    do {
1148        savedVisiblePos = currentVisiblePos;
1149        VisiblePosition prevVisiblePos = previousLinePosition(currentVisiblePos, 0, HasEditableAXRole);
1150        currentVisiblePos = prevVisiblePos;
1151        ++lineCount;
1152    }  while (currentVisiblePos.isNotNull() && !(inSameLine(currentVisiblePos, savedVisiblePos)));
1153
1154    return lineCount;
1155}
1156#endif
1157
1158// NOTE: Consider providing this utility method as AX API
1159PlainTextRange AccessibilityObject::plainTextRangeForVisiblePositionRange(const VisiblePositionRange& positionRange) const
1160{
1161    int index1 = index(positionRange.start);
1162    int index2 = index(positionRange.end);
1163    if (index1 < 0 || index2 < 0 || index1 > index2)
1164        return PlainTextRange();
1165
1166    return PlainTextRange(index1, index2 - index1);
1167}
1168
1169// The composed character range in the text associated with this accessibility object that
1170// is specified by the given screen coordinates. This parameterized attribute returns the
1171// complete range of characters (including surrogate pairs of multi-byte glyphs) at the given
1172// screen coordinates.
1173// NOTE: This varies from AppKit when the point is below the last line. AppKit returns an
1174// an error in that case. We return textControl->text().length(), 1. Does this matter?
1175PlainTextRange AccessibilityObject::doAXRangeForPosition(const IntPoint& point) const
1176{
1177    int i = index(visiblePositionForPoint(point));
1178    if (i < 0)
1179        return PlainTextRange();
1180
1181    return PlainTextRange(i, 1);
1182}
1183
1184// Given a character index, the range of text associated with this accessibility object
1185// over which the style in effect at that character index applies.
1186PlainTextRange AccessibilityObject::doAXStyleRangeForIndex(unsigned index) const
1187{
1188    VisiblePositionRange range = styleRangeForPosition(visiblePositionForIndex(index, false));
1189    return plainTextRangeForVisiblePositionRange(range);
1190}
1191
1192// Given an indexed character, the line number of the text associated with this accessibility
1193// object that contains the character.
1194unsigned AccessibilityObject::doAXLineForIndex(unsigned index)
1195{
1196    return lineForPosition(visiblePositionForIndex(index, false));
1197}
1198
1199#if HAVE(ACCESSIBILITY)
1200void AccessibilityObject::updateBackingStore()
1201{
1202    // Updating the layout may delete this object.
1203    if (Document* document = this->document()) {
1204        if (!document->view()->isInLayout())
1205            document->updateLayoutIgnorePendingStylesheets();
1206    }
1207}
1208#endif
1209
1210Document* AccessibilityObject::document() const
1211{
1212    FrameView* frameView = documentFrameView();
1213    if (!frameView)
1214        return 0;
1215
1216    return frameView->frame()->document();
1217}
1218
1219Page* AccessibilityObject::page() const
1220{
1221    Document* document = this->document();
1222    if (!document)
1223        return 0;
1224    return document->page();
1225}
1226
1227FrameView* AccessibilityObject::documentFrameView() const
1228{
1229    const AccessibilityObject* object = this;
1230    while (object && !object->isAccessibilityRenderObject())
1231        object = object->parentObject();
1232
1233    if (!object)
1234        return 0;
1235
1236    return object->documentFrameView();
1237}
1238
1239#if HAVE(ACCESSIBILITY)
1240const AccessibilityObject::AccessibilityChildrenVector& AccessibilityObject::children()
1241{
1242    updateChildrenIfNecessary();
1243
1244    return m_children;
1245}
1246#endif
1247
1248void AccessibilityObject::updateChildrenIfNecessary()
1249{
1250    if (!hasChildren())
1251        addChildren();
1252}
1253
1254void AccessibilityObject::clearChildren()
1255{
1256    // Some objects have weak pointers to their parents and those associations need to be detached.
1257    size_t length = m_children.size();
1258    for (size_t i = 0; i < length; i++)
1259        m_children[i]->detachFromParent();
1260
1261    m_children.clear();
1262    m_haveChildren = false;
1263}
1264
1265AccessibilityObject* AccessibilityObject::anchorElementForNode(Node* node)
1266{
1267    RenderObject* obj = node->renderer();
1268    if (!obj)
1269        return 0;
1270
1271    RefPtr<AccessibilityObject> axObj = obj->document()->axObjectCache()->getOrCreate(obj);
1272    Element* anchor = axObj->anchorElement();
1273    if (!anchor)
1274        return 0;
1275
1276    RenderObject* anchorRenderer = anchor->renderer();
1277    if (!anchorRenderer)
1278        return 0;
1279
1280    return anchorRenderer->document()->axObjectCache()->getOrCreate(anchorRenderer);
1281}
1282
1283void AccessibilityObject::ariaTreeRows(AccessibilityChildrenVector& result)
1284{
1285    AccessibilityChildrenVector axChildren = children();
1286    unsigned count = axChildren.size();
1287    for (unsigned k = 0; k < count; ++k) {
1288        AccessibilityObject* obj = axChildren[k].get();
1289
1290        // Add tree items as the rows.
1291        if (obj->roleValue() == TreeItemRole)
1292            result.append(obj);
1293
1294        // Now see if this item also has rows hiding inside of it.
1295        obj->ariaTreeRows(result);
1296    }
1297}
1298
1299void AccessibilityObject::ariaTreeItemContent(AccessibilityChildrenVector& result)
1300{
1301    // The ARIA tree item content are the item that are not other tree items or their containing groups.
1302    AccessibilityChildrenVector axChildren = children();
1303    unsigned count = axChildren.size();
1304    for (unsigned k = 0; k < count; ++k) {
1305        AccessibilityObject* obj = axChildren[k].get();
1306        AccessibilityRole role = obj->roleValue();
1307        if (role == TreeItemRole || role == GroupRole)
1308            continue;
1309
1310        result.append(obj);
1311    }
1312}
1313
1314void AccessibilityObject::ariaTreeItemDisclosedRows(AccessibilityChildrenVector& result)
1315{
1316    AccessibilityChildrenVector axChildren = children();
1317    unsigned count = axChildren.size();
1318    for (unsigned k = 0; k < count; ++k) {
1319        AccessibilityObject* obj = axChildren[k].get();
1320
1321        // Add tree items as the rows.
1322        if (obj->roleValue() == TreeItemRole)
1323            result.append(obj);
1324        // If it's not a tree item, then descend into the group to find more tree items.
1325        else
1326            obj->ariaTreeRows(result);
1327    }
1328}
1329
1330#if HAVE(ACCESSIBILITY)
1331const String& AccessibilityObject::actionVerb() const
1332{
1333    // FIXME: Need to add verbs for select elements.
1334    DEFINE_STATIC_LOCAL(const String, buttonAction, (AXButtonActionVerb()));
1335    DEFINE_STATIC_LOCAL(const String, textFieldAction, (AXTextFieldActionVerb()));
1336    DEFINE_STATIC_LOCAL(const String, radioButtonAction, (AXRadioButtonActionVerb()));
1337    DEFINE_STATIC_LOCAL(const String, checkedCheckBoxAction, (AXCheckedCheckBoxActionVerb()));
1338    DEFINE_STATIC_LOCAL(const String, uncheckedCheckBoxAction, (AXUncheckedCheckBoxActionVerb()));
1339    DEFINE_STATIC_LOCAL(const String, linkAction, (AXLinkActionVerb()));
1340    DEFINE_STATIC_LOCAL(const String, menuListAction, (AXMenuListActionVerb()));
1341    DEFINE_STATIC_LOCAL(const String, menuListPopupAction, (AXMenuListPopupActionVerb()));
1342    DEFINE_STATIC_LOCAL(const String, listItemAction, (AXListItemActionVerb()));
1343    DEFINE_STATIC_LOCAL(const String, noAction, ());
1344
1345    switch (roleValue()) {
1346    case ButtonRole:
1347    case ToggleButtonRole:
1348        return buttonAction;
1349    case TextFieldRole:
1350    case TextAreaRole:
1351        return textFieldAction;
1352    case RadioButtonRole:
1353        return radioButtonAction;
1354    case CheckBoxRole:
1355        return isChecked() ? checkedCheckBoxAction : uncheckedCheckBoxAction;
1356    case LinkRole:
1357    case WebCoreLinkRole:
1358        return linkAction;
1359    case PopUpButtonRole:
1360        return menuListAction;
1361    case MenuListPopupRole:
1362        return menuListPopupAction;
1363    case ListItemRole:
1364        return listItemAction;
1365    default:
1366        return noAction;
1367    }
1368}
1369#endif
1370
1371bool AccessibilityObject::ariaIsMultiline() const
1372{
1373    return equalIgnoringCase(getAttribute(aria_multilineAttr), "true");
1374}
1375
1376const AtomicString& AccessibilityObject::invalidStatus() const
1377{
1378    DEFINE_STATIC_LOCAL(const AtomicString, invalidStatusFalse, ("false", AtomicString::ConstructFromLiteral));
1379
1380    // aria-invalid can return false (default), grammer, spelling, or true.
1381    const AtomicString& ariaInvalid = getAttribute(aria_invalidAttr);
1382
1383    // If empty or not present, it should return false.
1384    if (ariaInvalid.isEmpty())
1385        return invalidStatusFalse;
1386
1387    return ariaInvalid;
1388}
1389
1390bool AccessibilityObject::hasAttribute(const QualifiedName& attribute) const
1391{
1392    Node* elementNode = node();
1393    if (!elementNode)
1394        return false;
1395
1396    if (!elementNode->isElementNode())
1397        return false;
1398
1399    Element* element = toElement(elementNode);
1400    return element->fastHasAttribute(attribute);
1401}
1402
1403const AtomicString& AccessibilityObject::getAttribute(const QualifiedName& attribute) const
1404{
1405    Node* elementNode = node();
1406    if (!elementNode)
1407        return nullAtom;
1408
1409    if (!elementNode->isElementNode())
1410        return nullAtom;
1411
1412    Element* element = toElement(elementNode);
1413    return element->fastGetAttribute(attribute);
1414}
1415
1416// Lacking concrete evidence of orientation, horizontal means width > height. vertical is height > width;
1417AccessibilityOrientation AccessibilityObject::orientation() const
1418{
1419    LayoutRect bounds = elementRect();
1420    if (bounds.size().width() > bounds.size().height())
1421        return AccessibilityOrientationHorizontal;
1422    if (bounds.size().height() > bounds.size().width())
1423        return AccessibilityOrientationVertical;
1424
1425    // A tie goes to horizontal.
1426    return AccessibilityOrientationHorizontal;
1427}
1428
1429bool AccessibilityObject::isDescendantOfObject(const AccessibilityObject* axObject) const
1430{
1431    if (!axObject || !axObject->hasChildren())
1432        return false;
1433
1434    for (const AccessibilityObject* parent = parentObject(); parent; parent = parent->parentObject()) {
1435        if (parent == axObject)
1436            return true;
1437    }
1438    return false;
1439}
1440
1441bool AccessibilityObject::isAncestorOfObject(const AccessibilityObject* axObject) const
1442{
1443    if (!axObject)
1444        return false;
1445
1446    return this == axObject || axObject->isDescendantOfObject(this);
1447}
1448
1449AccessibilityObject* AccessibilityObject::firstAnonymousBlockChild() const
1450{
1451    for (AccessibilityObject* child = firstChild(); child; child = child->nextSibling()) {
1452        if (child->renderer() && child->renderer()->isAnonymousBlock())
1453            return child;
1454    }
1455    return 0;
1456}
1457
1458typedef HashMap<String, AccessibilityRole, CaseFoldingHash> ARIARoleMap;
1459
1460struct RoleEntry {
1461    String ariaRole;
1462    AccessibilityRole webcoreRole;
1463};
1464
1465static ARIARoleMap* createARIARoleMap()
1466{
1467    const RoleEntry roles[] = {
1468        { "alert", ApplicationAlertRole },
1469        { "alertdialog", ApplicationAlertDialogRole },
1470        { "application", LandmarkApplicationRole },
1471        { "article", DocumentArticleRole },
1472        { "banner", LandmarkBannerRole },
1473        { "button", ButtonRole },
1474        { "checkbox", CheckBoxRole },
1475        { "complementary", LandmarkComplementaryRole },
1476        { "contentinfo", LandmarkContentInfoRole },
1477        { "dialog", ApplicationDialogRole },
1478        { "directory", DirectoryRole },
1479        { "grid", TableRole },
1480        { "gridcell", CellRole },
1481        { "columnheader", ColumnHeaderRole },
1482        { "combobox", ComboBoxRole },
1483        { "definition", DefinitionRole },
1484        { "document", DocumentRole },
1485        { "rowheader", RowHeaderRole },
1486        { "group", GroupRole },
1487        { "heading", HeadingRole },
1488        { "img", ImageRole },
1489        { "link", WebCoreLinkRole },
1490        { "list", ListRole },
1491        { "listitem", ListItemRole },
1492        { "listbox", ListBoxRole },
1493        { "log", ApplicationLogRole },
1494        // "option" isn't here because it may map to different roles depending on the parent element's role
1495        { "main", LandmarkMainRole },
1496        { "marquee", ApplicationMarqueeRole },
1497        { "math", DocumentMathRole },
1498        { "menu", MenuRole },
1499        { "menubar", MenuBarRole },
1500        { "menuitem", MenuItemRole },
1501        { "menuitemcheckbox", MenuItemRole },
1502        { "menuitemradio", MenuItemRole },
1503        { "note", DocumentNoteRole },
1504        { "navigation", LandmarkNavigationRole },
1505        { "option", ListBoxOptionRole },
1506        { "presentation", PresentationalRole },
1507        { "progressbar", ProgressIndicatorRole },
1508        { "radio", RadioButtonRole },
1509        { "radiogroup", RadioGroupRole },
1510        { "region", DocumentRegionRole },
1511        { "row", RowRole },
1512        { "scrollbar", ScrollBarRole },
1513        { "search", LandmarkSearchRole },
1514        { "separator", SplitterRole },
1515        { "slider", SliderRole },
1516        { "spinbutton", SpinButtonRole },
1517        { "status", ApplicationStatusRole },
1518        { "tab", TabRole },
1519        { "tablist", TabListRole },
1520        { "tabpanel", TabPanelRole },
1521        { "text", StaticTextRole },
1522        { "textbox", TextAreaRole },
1523        { "timer", ApplicationTimerRole },
1524        { "toolbar", ToolbarRole },
1525        { "tooltip", UserInterfaceTooltipRole },
1526        { "tree", TreeRole },
1527        { "treegrid", TreeGridRole },
1528        { "treeitem", TreeItemRole }
1529    };
1530    ARIARoleMap* roleMap = new ARIARoleMap;
1531
1532    for (size_t i = 0; i < WTF_ARRAY_LENGTH(roles); ++i)
1533        roleMap->set(roles[i].ariaRole, roles[i].webcoreRole);
1534    return roleMap;
1535}
1536
1537AccessibilityRole AccessibilityObject::ariaRoleToWebCoreRole(const String& value)
1538{
1539    ASSERT(!value.isEmpty());
1540
1541    static const ARIARoleMap* roleMap = createARIARoleMap();
1542
1543    Vector<String> roleVector;
1544    value.split(' ', roleVector);
1545    AccessibilityRole role = UnknownRole;
1546    unsigned size = roleVector.size();
1547    for (unsigned i = 0; i < size; ++i) {
1548        String roleName = roleVector[i];
1549        role = roleMap->get(roleName);
1550        if (role)
1551            return role;
1552    }
1553
1554    return role;
1555}
1556
1557bool AccessibilityObject::hasHighlighting() const
1558{
1559    for (Node* node = this->node(); node; node = node->parentNode()) {
1560        if (node->hasTagName(markTag))
1561            return true;
1562    }
1563
1564    return false;
1565}
1566
1567const AtomicString& AccessibilityObject::placeholderValue() const
1568{
1569    const AtomicString& placeholder = getAttribute(placeholderAttr);
1570    if (!placeholder.isEmpty())
1571        return placeholder;
1572
1573    return nullAtom;
1574}
1575
1576bool AccessibilityObject::isInsideARIALiveRegion() const
1577{
1578    if (supportsARIALiveRegion())
1579        return true;
1580
1581    for (AccessibilityObject* axParent = parentObject(); axParent; axParent = axParent->parentObject()) {
1582        if (axParent->supportsARIALiveRegion())
1583            return true;
1584    }
1585
1586    return false;
1587}
1588
1589bool AccessibilityObject::supportsARIAAttributes() const
1590{
1591    return supportsARIALiveRegion()
1592        || supportsARIADragging()
1593        || supportsARIADropping()
1594        || supportsARIAFlowTo()
1595        || supportsARIAOwns()
1596        || hasAttribute(aria_labelAttr);
1597}
1598
1599bool AccessibilityObject::supportsARIALiveRegion() const
1600{
1601    const AtomicString& liveRegion = ariaLiveRegionStatus();
1602    return equalIgnoringCase(liveRegion, "polite") || equalIgnoringCase(liveRegion, "assertive");
1603}
1604
1605AccessibilityObject* AccessibilityObject::elementAccessibilityHitTest(const IntPoint& point) const
1606{
1607    // Send the hit test back into the sub-frame if necessary.
1608    if (isAttachment()) {
1609        Widget* widget = widgetForAttachmentView();
1610        // Normalize the point for the widget's bounds.
1611        if (widget && widget->isFrameView())
1612            return axObjectCache()->getOrCreate(widget)->accessibilityHitTest(IntPoint(point - widget->frameRect().location()));
1613    }
1614
1615    // Check if there are any mock elements that need to be handled.
1616    size_t count = m_children.size();
1617    for (size_t k = 0; k < count; k++) {
1618        if (m_children[k]->isMockObject() && m_children[k]->elementRect().contains(point))
1619            return m_children[k]->elementAccessibilityHitTest(point);
1620    }
1621
1622    return const_cast<AccessibilityObject*>(this);
1623}
1624
1625AXObjectCache* AccessibilityObject::axObjectCache() const
1626{
1627    Document* doc = document();
1628    if (doc)
1629        return doc->axObjectCache();
1630    return 0;
1631}
1632
1633AccessibilityObject* AccessibilityObject::focusedUIElement() const
1634{
1635    Document* doc = document();
1636    if (!doc)
1637        return 0;
1638
1639    Page* page = doc->page();
1640    if (!page)
1641        return 0;
1642
1643    return AXObjectCache::focusedUIElementForPage(page);
1644}
1645
1646AccessibilitySortDirection AccessibilityObject::sortDirection() const
1647{
1648    const AtomicString& sortAttribute = getAttribute(aria_sortAttr);
1649    if (equalIgnoringCase(sortAttribute, "ascending"))
1650        return SortDirectionAscending;
1651    if (equalIgnoringCase(sortAttribute, "descending"))
1652        return SortDirectionDescending;
1653
1654    return SortDirectionNone;
1655}
1656
1657bool AccessibilityObject::supportsRangeValue() const
1658{
1659    return isProgressIndicator()
1660        || isSlider()
1661        || isScrollbar()
1662        || isSpinButton();
1663}
1664
1665bool AccessibilityObject::supportsARIASetSize() const
1666{
1667    return hasAttribute(aria_setsizeAttr);
1668}
1669
1670bool AccessibilityObject::supportsARIAPosInSet() const
1671{
1672    return hasAttribute(aria_posinsetAttr);
1673}
1674
1675int AccessibilityObject::ariaSetSize() const
1676{
1677    return getAttribute(aria_setsizeAttr).toInt();
1678}
1679
1680int AccessibilityObject::ariaPosInSet() const
1681{
1682    return getAttribute(aria_posinsetAttr).toInt();
1683}
1684
1685bool AccessibilityObject::supportsARIAExpanded() const
1686{
1687    return !getAttribute(aria_expandedAttr).isEmpty();
1688}
1689
1690bool AccessibilityObject::isExpanded() const
1691{
1692    if (equalIgnoringCase(getAttribute(aria_expandedAttr), "true"))
1693        return true;
1694
1695    return false;
1696}
1697
1698AccessibilityButtonState AccessibilityObject::checkboxOrRadioValue() const
1699{
1700    // If this is a real checkbox or radio button, AccessibilityRenderObject will handle.
1701    // If it's an ARIA checkbox or radio, the aria-checked attribute should be used.
1702
1703    const AtomicString& result = getAttribute(aria_checkedAttr);
1704    if (equalIgnoringCase(result, "true"))
1705        return ButtonStateOn;
1706    if (equalIgnoringCase(result, "mixed"))
1707        return ButtonStateMixed;
1708
1709    return ButtonStateOff;
1710}
1711
1712// This is a 1-dimensional scroll offset helper function that's applied
1713// separately in the horizontal and vertical directions, because the
1714// logic is the same. The goal is to compute the best scroll offset
1715// in order to make an object visible within a viewport.
1716//
1717// In case the whole object cannot fit, you can specify a
1718// subfocus - a smaller region within the object that should
1719// be prioritized. If the whole object can fit, the subfocus is
1720// ignored.
1721//
1722// Example: the viewport is scrolled to the right just enough
1723// that the object is in view.
1724//   Before:
1725//   +----------Viewport---------+
1726//                         +---Object---+
1727//                         +--SubFocus--+
1728//
1729//   After:
1730//          +----------Viewport---------+
1731//                         +---Object---+
1732//                         +--SubFocus--+
1733//
1734// When constraints cannot be fully satisfied, the min
1735// (left/top) position takes precedence over the max (right/bottom).
1736//
1737// Note that the return value represents the ideal new scroll offset.
1738// This may be out of range - the calling function should clip this
1739// to the available range.
1740static int computeBestScrollOffset(int currentScrollOffset,
1741                                   int subfocusMin, int subfocusMax,
1742                                   int objectMin, int objectMax,
1743                                   int viewportMin, int viewportMax) {
1744    int viewportSize = viewportMax - viewportMin;
1745
1746    // If the focus size is larger than the viewport size, shrink it in the
1747    // direction of subfocus.
1748    if (objectMax - objectMin > viewportSize) {
1749        // Subfocus must be within focus:
1750        subfocusMin = std::max(subfocusMin, objectMin);
1751        subfocusMax = std::min(subfocusMax, objectMax);
1752
1753        // Subfocus must be no larger than the viewport size; favor top/left.
1754        if (subfocusMax - subfocusMin > viewportSize)
1755            subfocusMax = subfocusMin + viewportSize;
1756
1757        if (subfocusMin + viewportSize > objectMax)
1758            objectMin = objectMax - viewportSize;
1759        else {
1760            objectMin = subfocusMin;
1761            objectMax = subfocusMin + viewportSize;
1762        }
1763    }
1764
1765    // Exit now if the focus is already within the viewport.
1766    if (objectMin - currentScrollOffset >= viewportMin
1767        && objectMax - currentScrollOffset <= viewportMax)
1768        return currentScrollOffset;
1769
1770    // Scroll left if we're too far to the right.
1771    if (objectMax - currentScrollOffset > viewportMax)
1772        return objectMax - viewportMax;
1773
1774    // Scroll right if we're too far to the left.
1775    if (objectMin - currentScrollOffset < viewportMin)
1776        return objectMin - viewportMin;
1777
1778    ASSERT_NOT_REACHED();
1779
1780    // This shouldn't happen.
1781    return currentScrollOffset;
1782}
1783
1784bool AccessibilityObject::isOnscreen() const
1785{
1786    bool isOnscreen = true;
1787
1788    // To figure out if the element is onscreen, we start by building of a stack starting with the
1789    // element, and then include every scrollable parent in the hierarchy.
1790    Vector<const AccessibilityObject*> objects;
1791
1792    objects.append(this);
1793    for (AccessibilityObject* parentObject = this->parentObject(); parentObject; parentObject = parentObject->parentObject()) {
1794        if (parentObject->getScrollableAreaIfScrollable())
1795            objects.append(parentObject);
1796    }
1797
1798    // Now, go back through that chain and make sure each inner object is within the
1799    // visible bounds of the outer object.
1800    size_t levels = objects.size() - 1;
1801
1802    for (size_t i = levels; i >= 1; i--) {
1803        const AccessibilityObject* outer = objects[i];
1804        const AccessibilityObject* inner = objects[i - 1];
1805        const IntRect outerRect = i < levels ? pixelSnappedIntRect(outer->boundingBoxRect()) : outer->getScrollableAreaIfScrollable()->visibleContentRect();
1806        const IntRect innerRect = pixelSnappedIntRect(inner->isAccessibilityScrollView() ? inner->parentObject()->boundingBoxRect() : inner->boundingBoxRect());
1807
1808        if (!outerRect.intersects(innerRect)) {
1809            isOnscreen = false;
1810            break;
1811        }
1812    }
1813
1814    return isOnscreen;
1815}
1816
1817void AccessibilityObject::scrollToMakeVisible() const
1818{
1819    IntRect objectRect = pixelSnappedIntRect(boundingBoxRect());
1820    objectRect.setLocation(IntPoint());
1821    scrollToMakeVisibleWithSubFocus(objectRect);
1822}
1823
1824void AccessibilityObject::scrollToMakeVisibleWithSubFocus(const IntRect& subfocus) const
1825{
1826    // Search up the parent chain until we find the first one that's scrollable.
1827    AccessibilityObject* scrollParent = parentObject();
1828    ScrollableArea* scrollableArea;
1829    for (scrollableArea = 0;
1830         scrollParent && !(scrollableArea = scrollParent->getScrollableAreaIfScrollable());
1831         scrollParent = scrollParent->parentObject()) { }
1832    if (!scrollableArea)
1833        return;
1834
1835    LayoutRect objectRect = boundingBoxRect();
1836    IntPoint scrollPosition = scrollableArea->scrollPosition();
1837    IntRect scrollVisibleRect = scrollableArea->visibleContentRect();
1838
1839    int desiredX = computeBestScrollOffset(
1840        scrollPosition.x(),
1841        objectRect.x() + subfocus.x(), objectRect.x() + subfocus.maxX(),
1842        objectRect.x(), objectRect.maxX(),
1843        0, scrollVisibleRect.width());
1844    int desiredY = computeBestScrollOffset(
1845        scrollPosition.y(),
1846        objectRect.y() + subfocus.y(), objectRect.y() + subfocus.maxY(),
1847        objectRect.y(), objectRect.maxY(),
1848        0, scrollVisibleRect.height());
1849
1850    scrollParent->scrollTo(IntPoint(desiredX, desiredY));
1851
1852    // Recursively make sure the scroll parent itself is visible.
1853    if (scrollParent->parentObject())
1854        scrollParent->scrollToMakeVisible();
1855}
1856
1857void AccessibilityObject::scrollToGlobalPoint(const IntPoint& globalPoint) const
1858{
1859    // Search up the parent chain and create a vector of all scrollable parent objects
1860    // and ending with this object itself.
1861    Vector<const AccessibilityObject*> objects;
1862
1863    objects.append(this);
1864    for (AccessibilityObject* parentObject = this->parentObject(); parentObject; parentObject = parentObject->parentObject()) {
1865        if (parentObject->getScrollableAreaIfScrollable())
1866            objects.append(parentObject);
1867    }
1868
1869    objects.reverse();
1870
1871    // Start with the outermost scrollable (the main window) and try to scroll the
1872    // next innermost object to the given point.
1873    int offsetX = 0, offsetY = 0;
1874    IntPoint point = globalPoint;
1875    size_t levels = objects.size() - 1;
1876    for (size_t i = 0; i < levels; i++) {
1877        const AccessibilityObject* outer = objects[i];
1878        const AccessibilityObject* inner = objects[i + 1];
1879
1880        ScrollableArea* scrollableArea = outer->getScrollableAreaIfScrollable();
1881
1882        LayoutRect innerRect = inner->isAccessibilityScrollView() ? inner->parentObject()->boundingBoxRect() : inner->boundingBoxRect();
1883        LayoutRect objectRect = innerRect;
1884        IntPoint scrollPosition = scrollableArea->scrollPosition();
1885
1886        // Convert the object rect into local coordinates.
1887        objectRect.move(offsetX, offsetY);
1888        if (!outer->isAccessibilityScrollView())
1889            objectRect.move(scrollPosition.x(), scrollPosition.y());
1890
1891        int desiredX = computeBestScrollOffset(
1892            0,
1893            objectRect.x(), objectRect.maxX(),
1894            objectRect.x(), objectRect.maxX(),
1895            point.x(), point.x());
1896        int desiredY = computeBestScrollOffset(
1897            0,
1898            objectRect.y(), objectRect.maxY(),
1899            objectRect.y(), objectRect.maxY(),
1900            point.y(), point.y());
1901        outer->scrollTo(IntPoint(desiredX, desiredY));
1902
1903        if (outer->isAccessibilityScrollView() && !inner->isAccessibilityScrollView()) {
1904            // If outer object we just scrolled is a scroll view (main window or iframe) but the
1905            // inner object is not, keep track of the coordinate transformation to apply to
1906            // future nested calculations.
1907            scrollPosition = scrollableArea->scrollPosition();
1908            offsetX -= (scrollPosition.x() + point.x());
1909            offsetY -= (scrollPosition.y() + point.y());
1910            point.move(scrollPosition.x() - innerRect.x(),
1911                       scrollPosition.y() - innerRect.y());
1912        } else if (inner->isAccessibilityScrollView()) {
1913            // Otherwise, if the inner object is a scroll view, reset the coordinate transformation.
1914            offsetX = 0;
1915            offsetY = 0;
1916        }
1917    }
1918}
1919
1920bool AccessibilityObject::lastKnownIsIgnoredValue()
1921{
1922    if (m_lastKnownIsIgnoredValue == DefaultBehavior)
1923        m_lastKnownIsIgnoredValue = accessibilityIsIgnored() ? IgnoreObject : IncludeObject;
1924
1925    return m_lastKnownIsIgnoredValue == IgnoreObject;
1926}
1927
1928void AccessibilityObject::setLastKnownIsIgnoredValue(bool isIgnored)
1929{
1930    m_lastKnownIsIgnoredValue = isIgnored ? IgnoreObject : IncludeObject;
1931}
1932
1933void AccessibilityObject::notifyIfIgnoredValueChanged()
1934{
1935    bool isIgnored = accessibilityIsIgnored();
1936    if (lastKnownIsIgnoredValue() != isIgnored) {
1937        axObjectCache()->childrenChanged(parentObject());
1938        setLastKnownIsIgnoredValue(isIgnored);
1939    }
1940}
1941
1942bool AccessibilityObject::ariaPressedIsPresent() const
1943{
1944    return !getAttribute(aria_pressedAttr).isEmpty();
1945}
1946
1947TextIteratorBehavior AccessibilityObject::textIteratorBehaviorForTextRange() const
1948{
1949    TextIteratorBehavior behavior = TextIteratorIgnoresStyleVisibility;
1950
1951#if PLATFORM(GTK)
1952    // We need to emit replaced elements for GTK, and present
1953    // them with the 'object replacement character' (0xFFFC).
1954    behavior = static_cast<TextIteratorBehavior>(behavior | TextIteratorEmitsObjectReplacementCharacters);
1955#endif
1956
1957    return behavior;
1958}
1959
1960AccessibilityRole AccessibilityObject::buttonRoleType() const
1961{
1962    // If aria-pressed is present, then it should be exposed as a toggle button.
1963    // http://www.w3.org/TR/wai-aria/states_and_properties#aria-pressed
1964    if (ariaPressedIsPresent())
1965        return ToggleButtonRole;
1966    if (ariaHasPopup())
1967        return PopUpButtonRole;
1968    // We don't contemplate RadioButtonRole, as it depends on the input
1969    // type.
1970
1971    return ButtonRole;
1972}
1973
1974bool AccessibilityObject::isButton() const
1975{
1976    AccessibilityRole role = roleValue();
1977
1978    return role == ButtonRole || role == PopUpButtonRole || role == ToggleButtonRole;
1979}
1980
1981bool AccessibilityObject::accessibilityIsIgnoredByDefault() const
1982{
1983    return defaultObjectInclusion() == IgnoreObject;
1984}
1985
1986bool AccessibilityObject::ariaIsHidden() const
1987{
1988    if (equalIgnoringCase(getAttribute(aria_hiddenAttr), "true"))
1989        return true;
1990
1991    for (AccessibilityObject* object = parentObject(); object; object = object->parentObject()) {
1992        if (equalIgnoringCase(object->getAttribute(aria_hiddenAttr), "true"))
1993            return true;
1994    }
1995
1996    return false;
1997}
1998
1999AccessibilityObjectInclusion AccessibilityObject::defaultObjectInclusion() const
2000{
2001    if (ariaIsHidden())
2002        return IgnoreObject;
2003
2004    if (isPresentationalChildOfAriaRole())
2005        return IgnoreObject;
2006
2007    return accessibilityPlatformIncludesObject();
2008}
2009
2010bool AccessibilityObject::accessibilityIsIgnored() const
2011{
2012    AXComputedObjectAttributeCache* attributeCache = axObjectCache()->computedObjectAttributeCache();
2013    if (attributeCache) {
2014        AccessibilityObjectInclusion ignored = attributeCache->getIgnored(axObjectID());
2015        switch (ignored) {
2016        case IgnoreObject:
2017            return true;
2018        case IncludeObject:
2019            return false;
2020        case DefaultBehavior:
2021            break;
2022        }
2023    }
2024
2025    bool result = computeAccessibilityIsIgnored();
2026
2027    if (attributeCache)
2028        attributeCache->setIgnored(axObjectID(), result ? IgnoreObject : IncludeObject);
2029
2030    return result;
2031}
2032
2033} // namespace WebCore
2034