/*

 * Copyright (C) 2008, 2009 Apple Inc. All rights reserved.

 *

 * Redistribution and use in source and binary forms, with or without

 * modification, are permitted provided that the following conditions

 * are met:

 *

 * 1.  Redistributions of source code must retain the above copyright

 *     notice, this list of conditions and the following disclaimer.

 * 2.  Redistributions in binary form must reproduce the above copyright

 *     notice, this list of conditions and the following disclaimer in the

 *     documentation and/or other materials provided with the distribution.

 * 3.  Neither the name of Apple Computer, Inc. ("Apple") nor the names of

 *     its contributors may be used to endorse or promote products derived

 *     from this software without specific prior written permission.

 *

 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY

 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED

 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY

 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES

 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;

 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF

 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

 */

#include "config.h"

#include "AccessibilityObject.h"

#include "AXObjectCache.h"

#include "AccessibilityRenderObject.h"

#include "CharacterNames.h"

#include "FloatRect.h"

#include "FocusController.h"

#include "Frame.h"

#include "FrameLoader.h"

#include "LocalizedStrings.h"

#include "NodeList.h"

#include "NotImplemented.h"

#include "Page.h"

#include "RenderImage.h"

#include "RenderListItem.h"

#include "RenderListMarker.h"

#include "RenderMenuList.h"

#include "RenderTextControl.h"

#include "RenderTheme.h"

#include "RenderView.h"

#include "RenderWidget.h"

#include "SelectionController.h"

#include "TextIterator.h"

#include "htmlediting.h"

#include "visible_units.h"

#include <wtf/StdLibExtras.h>

using namespace std;

namespace WebCore {

using namespace HTMLNames;

AccessibilityObject::AccessibilityObject()

    : m_id(0)

    , m_haveChildren(false)

    , m_role(UnknownRole)

#if PLATFORM(GTK)

    , m_wrapper(0)

#endif

{

}

AccessibilityObject::~AccessibilityObject()

{

    ASSERT(isDetached());

}

void AccessibilityObject::detach()

{

#if HAVE(ACCESSIBILITY)

    setWrapper(0);

#endif    

}

AccessibilityObject* AccessibilityObject::parentObjectUnignored() const

{

    AccessibilityObject* parent;

    for (parent = parentObject(); parent && parent->accessibilityIsIgnored(); parent = parent->parentObject()) {

    }

    return parent;

}

AccessibilityObject* AccessibilityObject::firstAccessibleObjectFromNode(const Node* node)

{

    ASSERT(AXObjectCache::accessibilityEnabled());

    if (!node)

        return 0;

    Document* document = node->document();

    if (!document)

        return 0;

    AXObjectCache* cache = document->axObjectCache();

    AccessibilityObject* accessibleObject = cache->getOrCreate(node->renderer());

    while (accessibleObject && accessibleObject->accessibilityIsIgnored()) {

        node = node->traverseNextNode();

        while (node && !node->renderer())

            node = node->traverseNextSibling();

        if (!node)

            return 0;

        accessibleObject = cache->getOrCreate(node->renderer());

    }

    return accessibleObject;

}

bool AccessibilityObject::isARIAInput(AccessibilityRole ariaRole)

{

    return ariaRole == RadioButtonRole || ariaRole == CheckBoxRole || ariaRole == TextFieldRole;

}    

bool AccessibilityObject::isARIAControl(AccessibilityRole ariaRole)

{

    return isARIAInput(ariaRole) || ariaRole == TextAreaRole || ariaRole == ButtonRole 

    || ariaRole == ComboBoxRole || ariaRole == SliderRole; 

}

IntPoint AccessibilityObject::clickPoint() const

{

    IntRect rect = elementRect();

    return IntPoint(rect.x() + rect.width() / 2, rect.y() + rect.height() / 2);

}

bool AccessibilityObject::press() const

{

    Element* actionElem = actionElement();

    if (!actionElem)

        return false;

    if (Frame* f = actionElem->document()->frame())

        f->loader()->resetMultipleFormSubmissionProtection();

    actionElem->accessKeyAction(true);

    return true;

}

String AccessibilityObject::language() const

{

    const AtomicString& lang = getAttribute(langAttr);

    if (!lang.isEmpty())

        return lang;

    AccessibilityObject* parent = parentObject();

    // as a last resort, fall back to the content language specified in the meta tag

    if (!parent) {

        Document* doc = document();

        if (doc)

            return doc->contentLanguage();

        return nullAtom;

    }

    return parent->language();

}

VisiblePositionRange AccessibilityObject::visiblePositionRangeForUnorderedPositions(const VisiblePosition& visiblePos1, const VisiblePosition& visiblePos2) const

{

    if (visiblePos1.isNull() || visiblePos2.isNull())

        return VisiblePositionRange();

    VisiblePosition startPos;

    VisiblePosition endPos;

    bool alreadyInOrder;

    // upstream is ordered before downstream for the same position

    if (visiblePos1 == visiblePos2 && visiblePos2.affinity() == UPSTREAM)

        alreadyInOrder = false;

    // use selection order to see if the positions are in order

    else

        alreadyInOrder = VisibleSelection(visiblePos1, visiblePos2).isBaseFirst();

    if (alreadyInOrder) {

        startPos = visiblePos1;

        endPos = visiblePos2;

    } else {

        startPos = visiblePos2;

        endPos = visiblePos1;

    }

    return VisiblePositionRange(startPos, endPos);

}

VisiblePositionRange AccessibilityObject::positionOfLeftWord(const VisiblePosition& visiblePos) const

{

    VisiblePosition startPosition = startOfWord(visiblePos, LeftWordIfOnBoundary);

    VisiblePosition endPosition = endOfWord(startPosition);

    return VisiblePositionRange(startPosition, endPosition);

}

VisiblePositionRange AccessibilityObject::positionOfRightWord(const VisiblePosition& visiblePos) const

{

    VisiblePosition startPosition = startOfWord(visiblePos, RightWordIfOnBoundary);

    VisiblePosition endPosition = endOfWord(startPosition);

    return VisiblePositionRange(startPosition, endPosition);

}

static VisiblePosition updateAXLineStartForVisiblePosition(const VisiblePosition& visiblePosition)

{

    // A line in the accessibility sense should include floating objects, such as aligned image, as part of a line.

    // So let's update the position to include that.

    VisiblePosition tempPosition;

    VisiblePosition startPosition = visiblePosition;

    Position p;

    RenderObject* renderer;

    while (true) {

        tempPosition = startPosition.previous();

        if (tempPosition.isNull())

            break;

        p = tempPosition.deepEquivalent();

        if (!p.node())

            break;

        renderer = p.node()->renderer();

        if (!renderer || (renderer->isRenderBlock() && !p.deprecatedEditingOffset()))

            break;

        InlineBox* box;

        int ignoredCaretOffset;

        p.getInlineBoxAndOffset(tempPosition.affinity(), box, ignoredCaretOffset);

        if (box)

            break;

        startPosition = tempPosition;

    }

    return startPosition;

}

VisiblePositionRange AccessibilityObject::leftLineVisiblePositionRange(const VisiblePosition& visiblePos) const

{

    if (visiblePos.isNull())

        return VisiblePositionRange();

    // make a caret selection for the position before marker position (to make sure

    // we move off of a line start)

    VisiblePosition prevVisiblePos = visiblePos.previous();

    if (prevVisiblePos.isNull())

        return VisiblePositionRange();

    VisiblePosition startPosition = startOfLine(prevVisiblePos);

    // keep searching for a valid line start position.  Unless the VisiblePosition is at the very beginning, there should

    // always be a valid line range.  However, startOfLine will return null for position next to a floating object,

    // since floating object doesn't really belong to any line.

    // This check will reposition the marker before the floating object, to ensure we get a line start.

    if (startPosition.isNull()) {

        while (startPosition.isNull() && prevVisiblePos.isNotNull()) {

            prevVisiblePos = prevVisiblePos.previous();

            startPosition = startOfLine(prevVisiblePos);

        }

    } else

        startPosition = updateAXLineStartForVisiblePosition(startPosition);

    VisiblePosition endPosition = endOfLine(prevVisiblePos);

    return VisiblePositionRange(startPosition, endPosition);

}

VisiblePositionRange AccessibilityObject::rightLineVisiblePositionRange(const VisiblePosition& visiblePos) const

{

    if (visiblePos.isNull())

        return VisiblePositionRange();

    // make sure we move off of a line end

    VisiblePosition nextVisiblePos = visiblePos.next();

    if (nextVisiblePos.isNull())

        return VisiblePositionRange();

    VisiblePosition startPosition = startOfLine(nextVisiblePos);

    // fetch for a valid line start position

    if (startPosition.isNull()) {

        startPosition = visiblePos;

        nextVisiblePos = nextVisiblePos.next();

    } else

        startPosition = updateAXLineStartForVisiblePosition(startPosition);

    VisiblePosition endPosition = endOfLine(nextVisiblePos);

    // as long as the position hasn't reached the end of the doc,  keep searching for a valid line end position

    // Unless the VisiblePosition is at the very end, there should always be a valid line range.  However, endOfLine will

    // return null for position by a floating object, since floating object doesn't really belong to any line.

    // This check will reposition the marker after the floating object, to ensure we get a line end.

    while (endPosition.isNull() && nextVisiblePos.isNotNull()) {

        nextVisiblePos = nextVisiblePos.next();

        endPosition = endOfLine(nextVisiblePos);

    }

    return VisiblePositionRange(startPosition, endPosition);

}

VisiblePositionRange AccessibilityObject::sentenceForPosition(const VisiblePosition& visiblePos) const

{

    // FIXME: FO 2 IMPLEMENT (currently returns incorrect answer)

    // Related? <rdar://problem/3927736> Text selection broken in 8A336

    VisiblePosition startPosition = startOfSentence(visiblePos);

    VisiblePosition endPosition = endOfSentence(startPosition);

    return VisiblePositionRange(startPosition, endPosition);

}

VisiblePositionRange AccessibilityObject::paragraphForPosition(const VisiblePosition& visiblePos) const

{

    VisiblePosition startPosition = startOfParagraph(visiblePos);

    VisiblePosition endPosition = endOfParagraph(startPosition);

    return VisiblePositionRange(startPosition, endPosition);

}

static VisiblePosition startOfStyleRange(const VisiblePosition visiblePos)

{

    RenderObject* renderer = visiblePos.deepEquivalent().node()->renderer();

    RenderObject* startRenderer = renderer;

    RenderStyle* style = renderer->style();

    // traverse backward by renderer to look for style change

    for (RenderObject* r = renderer->previousInPreOrder(); r; r = r->previousInPreOrder()) {

        // skip non-leaf nodes

        if (r->firstChild())

            continue;

        // stop at style change

        if (r->style() != style)

            break;

        // remember match

        startRenderer = r;

    }

    return VisiblePosition(startRenderer->node(), 0, VP_DEFAULT_AFFINITY);

}

static VisiblePosition endOfStyleRange(const VisiblePosition& visiblePos)

{

    RenderObject* renderer = visiblePos.deepEquivalent().node()->renderer();

    RenderObject* endRenderer = renderer;

    RenderStyle* style = renderer->style();

    // traverse forward by renderer to look for style change

    for (RenderObject* r = renderer->nextInPreOrder(); r; r = r->nextInPreOrder()) {

        // skip non-leaf nodes

        if (r->firstChild())

            continue;

        // stop at style change

        if (r->style() != style)

            break;

        // remember match

        endRenderer = r;

    }

    return lastDeepEditingPositionForNode(endRenderer->node());

}

VisiblePositionRange AccessibilityObject::styleRangeForPosition(const VisiblePosition& visiblePos) const

{

    if (visiblePos.isNull())

        return VisiblePositionRange();

    return VisiblePositionRange(startOfStyleRange(visiblePos), endOfStyleRange(visiblePos));

}

// NOTE: Consider providing this utility method as AX API

VisiblePositionRange AccessibilityObject::visiblePositionRangeForRange(const PlainTextRange& range) const

{

    if (range.start + range.length > text().length())

        return VisiblePositionRange();

    VisiblePosition startPosition = visiblePositionForIndex(range.start);

    startPosition.setAffinity(DOWNSTREAM);

    VisiblePosition endPosition = visiblePositionForIndex(range.start + range.length);

    return VisiblePositionRange(startPosition, endPosition);

}

static bool replacedNodeNeedsCharacter(Node* replacedNode)

{

    // we should always be given a rendered node and a replaced node, but be safe

    // replaced nodes are either attachments (widgets) or images

    if (!replacedNode || !replacedNode->renderer() || !replacedNode->renderer()->isReplaced() || replacedNode->isTextNode())

        return false;

    // create an AX object, but skip it if it is not supposed to be seen

    AccessibilityObject* object = replacedNode->renderer()->document()->axObjectCache()->getOrCreate(replacedNode->renderer());

    if (object->accessibilityIsIgnored())

        return false;

    return true;

}

// Finds a RenderListItem parent give a node.

static RenderListItem* renderListItemContainerForNode(Node* node)

{

    for (Node* stringNode = node; stringNode; stringNode = stringNode->parent()) {

        RenderObject* renderObject = stringNode->renderer();

        if (!renderObject || !renderObject->isListItem())

            continue;

        return toRenderListItem(renderObject);

    }

    return 0;

}

// Returns the text associated with a list marker if this node is contained within a list item.

String AccessibilityObject::listMarkerTextForNodeAndPosition(Node* node, const VisiblePosition& visiblePositionStart) const

{

    // If the range does not contain the start of the line, the list marker text should not be included.

    if (!isStartOfLine(visiblePositionStart))

        return String();

    RenderListItem* listItem = renderListItemContainerForNode(node);

    if (!listItem)

        return String();

    // If this is in a list item, we need to manually add the text for the list marker 

    // because a RenderListMarker does not have a Node equivalent and thus does not appear

    // when iterating text.

    const String& markerText = listItem->markerText();

    if (markerText.isEmpty())

        return String();

    // Append text, plus the period that follows the text.

    // FIXME: Not all list marker styles are followed by a period, but this

    // sounds much better when there is a synthesized pause because of a period.

    Vector<UChar> resultVector;

    resultVector.append(markerText.characters(), markerText.length());

    resultVector.append('.');

    resultVector.append(' ');

    return String::adopt(resultVector);

}

String AccessibilityObject::stringForVisiblePositionRange(const VisiblePositionRange& visiblePositionRange) const

{

    if (visiblePositionRange.isNull())

        return String();

    Vector<UChar> resultVector;

    RefPtr<Range> range = makeRange(visiblePositionRange.start, visiblePositionRange.end);

    for (TextIterator it(range.get()); !it.atEnd(); it.advance()) {

        // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)

        if (it.length()) {

            // Add a textual representation for list marker text

            String listMarkerText = listMarkerTextForNodeAndPosition(it.node(), visiblePositionRange.start);

            if (!listMarkerText.isEmpty())

                resultVector.append(listMarkerText.characters(), listMarkerText.length());

            resultVector.append(it.characters(), it.length());

        } else {

            // locate the node and starting offset for this replaced range

            int exception = 0;

            Node* node = it.range()->startContainer(exception);

            ASSERT(node == it.range()->endContainer(exception));

            int offset = it.range()->startOffset(exception);

            if (replacedNodeNeedsCharacter(node->childNode(offset)))

                resultVector.append(objectReplacementCharacter);

        }

    }

    return String::adopt(resultVector);

}

int AccessibilityObject::lengthForVisiblePositionRange(const VisiblePositionRange& visiblePositionRange) const

{

    // FIXME: Multi-byte support

    if (visiblePositionRange.isNull())

        return -1;

    int length = 0;

    RefPtr<Range> range = makeRange(visiblePositionRange.start, visiblePositionRange.end);

    for (TextIterator it(range.get()); !it.atEnd(); it.advance()) {

        // non-zero length means textual node, zero length means replaced node (AKA "attachments" in AX)

        if (it.length())

            length += it.length();

        else {

            // locate the node and starting offset for this replaced range

            int exception = 0;

            Node* node = it.range()->startContainer(exception);

            ASSERT(node == it.range()->endContainer(exception));

            int offset = it.range()->startOffset(exception);

            if (replacedNodeNeedsCharacter(node->childNode(offset)))

                length++;

        }

    }

    return length;

}

VisiblePosition AccessibilityObject::nextWordEnd(const VisiblePosition& visiblePos) const

{

    if (visiblePos.isNull())

        return VisiblePosition();

    // make sure we move off of a word end

    VisiblePosition nextVisiblePos = visiblePos.next();

    if (nextVisiblePos.isNull())

        return VisiblePosition();

    return endOfWord(nextVisiblePos, LeftWordIfOnBoundary);

}

VisiblePosition AccessibilityObject::previousWordStart(const VisiblePosition& visiblePos) const

{

    if (visiblePos.isNull())

        return VisiblePosition();

    // make sure we move off of a word start

    VisiblePosition prevVisiblePos = visiblePos.previous();

    if (prevVisiblePos.isNull())

        return VisiblePosition();

    return startOfWord(prevVisiblePos, RightWordIfOnBoundary);

}

VisiblePosition AccessibilityObject::nextLineEndPosition(const VisiblePosition& visiblePos) const

{