/*

 * Copyright (C) 2004, 2005, 2006, 2007 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.

 *

 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``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 COMPUTER, INC. OR

 * 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 "htmlediting.h"

#include "CharacterNames.h"

#include "Document.h"

#include "EditingText.h"

#include "HTMLBRElement.h"

#include "HTMLDivElement.h"

#include "HTMLElementFactory.h"

#include "HTMLInterchange.h"

#include "HTMLLIElement.h"

#include "HTMLNames.h"

#include "HTMLOListElement.h"

#include "HTMLUListElement.h"

#include "PositionIterator.h"

#include "RenderObject.h"

#include "Range.h"

#include "VisibleSelection.h"

#include "Text.h"

#include "TextIterator.h"

#include "VisiblePosition.h"

#include "visible_units.h"

#include <wtf/StdLibExtras.h>

#if ENABLE(WML)

#include "WMLNames.h"

#endif

using namespace std;

namespace WebCore {

using namespace HTMLNames;

// Atomic means that the node has no children, or has children which are ignored for the

// purposes of editing.

bool isAtomicNode(const Node *node)

{

    return node && (!node->hasChildNodes() || editingIgnoresContent(node));

}

// Returns true for nodes that either have no content, or have content that is ignored (skipped 

// over) while editing.  There are no VisiblePositions inside these nodes.

bool editingIgnoresContent(const Node* node)

{

    return !canHaveChildrenForEditing(node) && !node->isTextNode();

}

bool canHaveChildrenForEditing(const Node* node)

{

    return !node->hasTagName(hrTag) &&

           !node->hasTagName(brTag) &&

           !node->hasTagName(imgTag) &&

           !node->hasTagName(buttonTag) &&

           !node->hasTagName(inputTag) &&

           !node->hasTagName(textareaTag) &&

           !node->hasTagName(objectTag) &&

           !node->hasTagName(iframeTag) &&

           !node->hasTagName(embedTag) &&

           !node->hasTagName(appletTag) &&

           !node->hasTagName(selectTag) &&

           !node->hasTagName(datagridTag) &&

#if ENABLE(WML)

           !node->hasTagName(WMLNames::doTag) &&

#endif

           !node->isTextNode();

}

// Compare two positions, taking into account the possibility that one or both

// could be inside a shadow tree. Only works for non-null values.

int comparePositions(const Position& a, const Position& b)

{

    Node* nodeA = a.node();

    ASSERT(nodeA);

    Node* nodeB = b.node();

    ASSERT(nodeB);

    int offsetA = a.deprecatedEditingOffset();

    int offsetB = b.deprecatedEditingOffset();

    Node* shadowAncestorA = nodeA->shadowAncestorNode();

    if (shadowAncestorA == nodeA)

        shadowAncestorA = 0;

    Node* shadowAncestorB = nodeB->shadowAncestorNode();

    if (shadowAncestorB == nodeB)

        shadowAncestorB = 0;

    int bias = 0;

    if (shadowAncestorA != shadowAncestorB) {

        if (shadowAncestorA) {

            nodeA = shadowAncestorA;

            offsetA = 0;

            bias = 1;

        }

        if (shadowAncestorB) {

            nodeB = shadowAncestorB;

            offsetB = 0;

            bias = -1;

        }

    }

    int result = Range::compareBoundaryPoints(nodeA, offsetA, nodeB, offsetB);

    return result ? result : bias;

}

int comparePositions(const VisiblePosition& a, const VisiblePosition& b)

{

    return comparePositions(a.deepEquivalent(), b.deepEquivalent());

}

Node* highestEditableRoot(const Position& position)

{

    Node* node = position.node();

    if (!node)

        return 0;

    Node* highestRoot = editableRootForPosition(position);

    if (!highestRoot)

        return 0;

    node = highestRoot;

    while (node) {

        if (node->isContentEditable())

            highestRoot = node;

        if (node->hasTagName(bodyTag))

            break;

        node = node->parentNode();

    }

    return highestRoot;

}

Node* lowestEditableAncestor(Node* node)

{

    if (!node)

        return 0;

    Node *lowestRoot = 0;

    while (node) {

        if (node->isContentEditable())

            return node->rootEditableElement();

        if (node->hasTagName(bodyTag))

            break;

        node = node->parentNode();

    }

    return lowestRoot;

}

bool isEditablePosition(const Position& p)

{

    Node* node = p.node();

    if (!node)

        return false;

    if (node->renderer() && node->renderer()->isTable())

        node = node->parentNode();

    return node->isContentEditable();

}

bool isAtUnsplittableElement(const Position& pos)

{

    Node* node = pos.node();

    return (node == editableRootForPosition(pos) || node == enclosingNodeOfType(pos, &isTableCell));

}

bool isRichlyEditablePosition(const Position& p)

{

    Node* node = p.node();

    if (!node)

        return false;

    if (node->renderer() && node->renderer()->isTable())

        node = node->parentNode();

    return node->isContentRichlyEditable();

}

Element* editableRootForPosition(const Position& p)

{

    Node* node = p.node();

    if (!node)

        return 0;

    if (node->renderer() && node->renderer()->isTable())

        node = node->parentNode();

    return node->rootEditableElement();

}

// Finds the enclosing element until which the tree can be split.

// When a user hits ENTER, he/she won't expect this element to be split into two.

// You may pass it as the second argument of splitTreeToNode.

Element* unsplittableElementForPosition(const Position& p)

{

    // Since enclosingNodeOfType won't search beyond the highest root editable node,

    // this code works even if the closest table cell was outside of the root editable node.

    Element* enclosingCell = static_cast<Element*>(enclosingNodeOfType(p, &isTableCell, true));

    if (enclosingCell)

        return enclosingCell;

    return editableRootForPosition(p);

}

Position nextCandidate(const Position& position)

{

    PositionIterator p = position;

    while (!p.atEnd()) {

        p.increment();

        if (p.isCandidate())

            return p;

    }

    return Position();

}

Position nextVisuallyDistinctCandidate(const Position& position)

{

    Position p = position;

    Position downstreamStart = p.downstream();

    while (!p.atEndOfTree()) {

        p = p.next(Character);

        if (p.isCandidate() && p.downstream() != downstreamStart)

            return p;

    }

    return Position();

}

Position previousCandidate(const Position& position)

{

    PositionIterator p = position;

    while (!p.atStart()) {

        p.decrement();

        if (p.isCandidate())

            return p;

    }

    return Position();

}

Position previousVisuallyDistinctCandidate(const Position& position)

{

    Position p = position;

    Position downstreamStart = p.downstream();

    while (!p.atStartOfTree()) {

        p = p.previous(Character);

        if (p.isCandidate() && p.downstream() != downstreamStart)

            return p;

    }

    return Position();

}

VisiblePosition firstEditablePositionAfterPositionInRoot(const Position& position, Node* highestRoot)

{

    // position falls before highestRoot.

    if (comparePositions(position, firstDeepEditingPositionForNode(highestRoot)) == -1 && highestRoot->isContentEditable())

        return firstDeepEditingPositionForNode(highestRoot);

    Position p = position;

    if (Node* shadowAncestor = p.node()->shadowAncestorNode())

        if (shadowAncestor != p.node())

            p = lastDeepEditingPositionForNode(shadowAncestor);

    while (p.node() && !isEditablePosition(p) && p.node()->isDescendantOf(highestRoot))

        p = isAtomicNode(p.node()) ? positionInParentAfterNode(p.node()) : nextVisuallyDistinctCandidate(p);

    if (p.node() && p.node() != highestRoot && !p.node()->isDescendantOf(highestRoot))

        return VisiblePosition();

    return VisiblePosition(p);

}

VisiblePosition lastEditablePositionBeforePositionInRoot(const Position& position, Node* highestRoot)

{

    // When position falls after highestRoot, the result is easy to compute.

    if (comparePositions(position, lastDeepEditingPositionForNode(highestRoot)) == 1)

        return lastDeepEditingPositionForNode(highestRoot);

    Position p = position;

    if (Node* shadowAncestor = p.node()->shadowAncestorNode())

        if (shadowAncestor != p.node())

            p = firstDeepEditingPositionForNode(shadowAncestor);

    while (p.node() && !isEditablePosition(p) && p.node()->isDescendantOf(highestRoot))

        p = isAtomicNode(p.node()) ? positionInParentBeforeNode(p.node()) : previousVisuallyDistinctCandidate(p);

    if (p.node() && p.node() != highestRoot && !p.node()->isDescendantOf(highestRoot))

        return VisiblePosition();

    return VisiblePosition(p);

}

// FIXME: The method name, comment, and code say three different things here!

// Whether or not content before and after this node will collapse onto the same line as it.

bool isBlock(const Node* node)

{

    return node && node->renderer() && !node->renderer()->isInline();

}

// FIXME: Deploy this in all of the places where enclosingBlockFlow/enclosingBlockFlowOrTableElement are used.

// FIXME: Pass a position to this function.  The enclosing block of [table, x] for example, should be the 

// block that contains the table and not the table, and this function should be the only one responsible for 

// knowing about these kinds of special cases.

Node* enclosingBlock(Node* node)

{

    return static_cast<Element*>(enclosingNodeOfType(Position(node, 0), isBlock));

}

// Internally editing uses "invalid" positions for historical reasons.  For

// example, in <div><img /></div>, Editing might use (img, 1) for the position

// after <img>, but we have to convert that to (div, 1) before handing the

// position to a Range object.  Ideally all internal positions should

// be "range compliant" for simplicity.

Position rangeCompliantEquivalent(const Position& pos)

{

    if (pos.isNull())

        return Position();

    Node* node = pos.node();

    if (pos.deprecatedEditingOffset() <= 0) {

        if (node->parentNode() && (editingIgnoresContent(node) || isTableElement(node)))

            return positionInParentBeforeNode(node);

        return Position(node, 0);

    }

    if (node->offsetInCharacters())

        return Position(node, min(node->maxCharacterOffset(), pos.deprecatedEditingOffset()));

    int maxCompliantOffset = node->childNodeCount();

    if (pos.deprecatedEditingOffset() > maxCompliantOffset) {

        if (node->parentNode())

            return positionInParentAfterNode(node);

        // there is no other option at this point than to

        // use the highest allowed position in the node

        return Position(node, maxCompliantOffset);

    } 

    // Editing should never generate positions like this.

    if ((pos.deprecatedEditingOffset() < maxCompliantOffset) && editingIgnoresContent(node)) {

        ASSERT_NOT_REACHED();

        return node->parentNode() ? positionInParentBeforeNode(node) : Position(node, 0);

    }

    if (pos.deprecatedEditingOffset() == maxCompliantOffset && (editingIgnoresContent(node) || isTableElement(node)))

        return positionInParentAfterNode(node);

    return Position(pos);

}

Position rangeCompliantEquivalent(const VisiblePosition& vpos)

{

    return rangeCompliantEquivalent(vpos.deepEquivalent());

}

// This method is used to create positions in the DOM. It returns the maximum valid offset

// in a node.  It returns 1 for some elements even though they do not have children, which

// creates technically invalid DOM Positions.  Be sure to call rangeCompliantEquivalent

// on a Position before using it to create a DOM Range, or an exception will be thrown.

int lastOffsetForEditing(const Node* node)

{

    ASSERT(node);

    if (!node)

        return 0;

    if (node->offsetInCharacters())

        return node->maxCharacterOffset();

    if (node->hasChildNodes())

        return node->childNodeCount();

    // NOTE: This should preempt the childNodeCount for, e.g., select nodes

    if (editingIgnoresContent(node))

        return 1;

    return 0;

}

String stringWithRebalancedWhitespace(const String& string, bool startIsStartOfParagraph, bool endIsEndOfParagraph)

{

    DEFINE_STATIC_LOCAL(String, twoSpaces, ("  "));

    DEFINE_STATIC_LOCAL(String, nbsp, ("\xa0"));

    DEFINE_STATIC_LOCAL(String, pattern, (" \xa0"));

    String rebalancedString = string;

    rebalancedString.replace(noBreakSpace, ' ');

    rebalancedString.replace('\n', ' ');

    rebalancedString.replace('\t', ' ');

    rebalancedString.replace(twoSpaces, pattern);

    if (startIsStartOfParagraph && rebalancedString[0] == ' ')

        rebalancedString.replace(0, 1, nbsp);

    int end = rebalancedString.length() - 1;

    if (endIsEndOfParagraph && rebalancedString[end] == ' ')

        rebalancedString.replace(end, 1, nbsp);    

    return rebalancedString;

}

bool isTableStructureNode(const Node *node)

{

    RenderObject *r = node->renderer();

    return (r && (r->isTableCell() || r->isTableRow() || r->isTableSection() || r->isTableCol()));

}

const String& nonBreakingSpaceString()

{

    DEFINE_STATIC_LOCAL(String, nonBreakingSpaceString, (&noBreakSpace, 1));

    return nonBreakingSpaceString;

}

// FIXME: need to dump this

bool isSpecialElement(const Node *n)

{

    if (!n)

        return false;

    if (!n->isHTMLElement())

        return false;

    if (n->isLink())

        return true;

    RenderObject *renderer = n->renderer();

    if (!renderer)

        return false;

    if (renderer->style()->display() == TABLE || renderer->style()->display() == INLINE_TABLE)

        return true;

    if (renderer->style()->isFloating())

        return true;

    if (renderer->style()->position() != StaticPosition)

        return true;

    return false;

}

// Checks if a string is a valid tag for the FormatBlockCommand function of execCommand. Expects lower case strings.

bool validBlockTag(const AtomicString& blockTag)

{

    if (blockTag.isEmpty())

        return false;

    DEFINE_STATIC_LOCAL(HashSet<AtomicString>, blockTags, ());

    if (blockTags.isEmpty()) {

        blockTags.add(addressTag.localName());

        blockTags.add(articleTag.localName());

        blockTags.add(asideTag.localName());

        blockTags.add(blockquoteTag.localName());

        blockTags.add(ddTag.localName());

        blockTags.add(divTag.localName());

        blockTags.add(dlTag.localName());

        blockTags.add(dtTag.localName());

        blockTags.add(footerTag.localName());

        blockTags.add(h1Tag.localName());

        blockTags.add(h2Tag.localName());

        blockTags.add(h3Tag.localName());

        blockTags.add(h4Tag.localName());

        blockTags.add(h5Tag.localName());

        blockTags.add(h6Tag.localName());

        blockTags.add(headerTag.localName());

        blockTags.add(hgroupTag.localName());

        blockTags.add(navTag.localName());

        blockTags.add(pTag.localName());

        blockTags.add(preTag.localName());

        blockTags.add(sectionTag.localName());

    }

    return blockTags.contains(blockTag);

}

static Node* firstInSpecialElement(const Position& pos)

{

    // FIXME: This begins at pos.node(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.

    Node* rootEditableElement = pos.node()->rootEditableElement();

    for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())

        if (isSpecialElement(n)) {

            VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);

            VisiblePosition firstInElement = VisiblePosition(n, 0, DOWNSTREAM);

            if (isTableElement(n) && vPos == firstInElement.next())

                return n;

            if (vPos == firstInElement)

                return n;

        }

    return 0;

}

static Node* lastInSpecialElement(const Position& pos)

{

    // FIXME: This begins at pos.node(), which doesn't necessarily contain pos (suppose pos was [img, 0]).  See <rdar://problem/5027702>.

    Node* rootEditableElement = pos.node()->rootEditableElement();

    for (Node* n = pos.node(); n && n->rootEditableElement() == rootEditableElement; n = n->parentNode())

        if (isSpecialElement(n)) {

            VisiblePosition vPos = VisiblePosition(pos, DOWNSTREAM);

            VisiblePosition lastInElement = VisiblePosition(n, n->childNodeCount(), DOWNSTREAM);

            if (isTableElement(n) && vPos == lastInElement.previous())

                return n;

            if (vPos == lastInElement)

                return n;