/*

 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010 Apple Inc. All rights reserved.

 * Copyright (C) 2005 Alexey Proskuryakov.

 *

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

#include "CharacterNames.h"

#include "Document.h"

#include "HTMLElement.h"

#include "HTMLNames.h"

#include "htmlediting.h"

#include "InlineTextBox.h"

#include "Range.h"

#include "RenderTableCell.h"

#include "RenderTableRow.h"

#include "RenderTextControl.h"

#include "VisiblePosition.h"

#include "visible_units.h"

#if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION

#include "TextBreakIteratorInternalICU.h"

#include <unicode/usearch.h>

#endif

using namespace WTF::Unicode;

using namespace std;

namespace WebCore {

using namespace HTMLNames;

// Buffer that knows how to compare with a search target.

// Keeps enough of the previous text to be able to search in the future, but no more.

// Non-breaking spaces are always equal to normal spaces.

// Case folding is also done if <isCaseSensitive> is false.

class SearchBuffer : public Noncopyable {

public:

    SearchBuffer(const String& target, bool isCaseSensitive);

    ~SearchBuffer();

    // Returns number of characters appended; guaranteed to be in the range [1, length].

    size_t append(const UChar*, size_t length);

    void reachedBreak();

    // Result is the size in characters of what was found.

    // And <startOffset> is the number of characters back to the start of what was found.

    size_t search(size_t& startOffset);

    bool atBreak() const;

#if USE(ICU_UNICODE) && !UCONFIG_NO_COLLATION

private:

    bool isBadMatch(const UChar*, size_t length) const;

    String m_target;

    Vector<UChar> m_buffer;

    size_t m_overlap;

    bool m_atBreak;

    bool m_targetRequiresKanaWorkaround;

    Vector<UChar> m_normalizedTarget;

    mutable Vector<UChar> m_normalizedMatch;

#else

private:

    void append(UChar, bool isCharacterStart);

    size_t length() const;

    String m_target;

    bool m_isCaseSensitive;

    Vector<UChar> m_buffer;

    Vector<bool> m_isCharacterStartBuffer;

    bool m_isBufferFull;

    size_t m_cursor;

#endif

};

// --------

static const unsigned bitsInWord = sizeof(unsigned) * 8;

static const unsigned bitInWordMask = bitsInWord - 1;

BitStack::BitStack()

    : m_size(0)

{

}

void BitStack::push(bool bit)

{

    unsigned index = m_size / bitsInWord;

    unsigned shift = m_size & bitInWordMask;

    if (!shift && index == m_words.size()) {

        m_words.grow(index + 1);

        m_words[index] = 0;

    }

    unsigned& word = m_words[index];

    unsigned mask = 1U << shift;

    if (bit)

        word |= mask;

    else

        word &= ~mask;

    ++m_size;

}

void BitStack::pop()

{

    if (m_size)

        --m_size;

}

bool BitStack::top() const

{

    if (!m_size)

        return false;

    unsigned shift = (m_size - 1) & bitInWordMask;

    return m_words.last() & (1U << shift);

}

unsigned BitStack::size() const

{

    return m_size;

}

// --------

static inline Node* parentCrossingShadowBoundaries(Node* node)

{

    if (Node* parent = node->parentNode())

        return parent;

    return node->shadowParentNode();

}

#if !ASSERT_DISABLED

static unsigned depthCrossingShadowBoundaries(Node* node)

{

    unsigned depth = 0;

    for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))

        ++depth;

    return depth;

}

#endif

// This function is like Range::pastLastNode, except for the fact that it can climb up out of shadow trees.

static Node* nextInPreOrderCrossingShadowBoundaries(Node* rangeEndContainer, int rangeEndOffset)

{

    if (!rangeEndContainer)

        return 0;

    if (rangeEndOffset >= 0 && !rangeEndContainer->offsetInCharacters()) {

        if (Node* next = rangeEndContainer->childNode(rangeEndOffset))

            return next;

    }

    for (Node* node = rangeEndContainer; node; node = parentCrossingShadowBoundaries(node)) {

        if (Node* next = node->nextSibling())

            return next;

    }

    return 0;

}

static Node* previousInPostOrderCrossingShadowBoundaries(Node* rangeStartContainer, int rangeStartOffset)

{

    if (!rangeStartContainer)

        return 0;

    if (rangeStartOffset > 0 && !rangeStartContainer->offsetInCharacters()) {

        if (Node* previous = rangeStartContainer->childNode(rangeStartOffset - 1))

            return previous;

    }

    for (Node* node = rangeStartContainer; node; node = parentCrossingShadowBoundaries(node)) {

        if (Node* previous = node->previousSibling())

            return previous;

    }

    return 0;

}

// --------

static inline bool fullyClipsContents(Node* node)

{

    RenderObject* renderer = node->renderer();

    if (!renderer || !renderer->isBox() || !renderer->hasOverflowClip())

        return false;

    return toRenderBox(renderer)->size().isEmpty();

}

static inline bool ignoresContainerClip(Node* node)

{

    RenderObject* renderer = node->renderer();

    if (!renderer || renderer->isText())

        return false;

    EPosition position = renderer->style()->position();

    return position == AbsolutePosition || position == FixedPosition;

}

static void pushFullyClippedState(BitStack& stack, Node* node)

{

    ASSERT(stack.size() == depthCrossingShadowBoundaries(node));

    // Push true if this node full clips its contents, or if a parent already has fully

    // clipped and this is not a node that ignores its container's clip.

    stack.push(fullyClipsContents(node) || (stack.top() && !ignoresContainerClip(node)));

}

static void setUpFullyClippedStack(BitStack& stack, Node* node)

{

    // Put the nodes in a vector so we can iterate in reverse order.

    Vector<Node*, 100> ancestry;

    for (Node* parent = parentCrossingShadowBoundaries(node); parent; parent = parentCrossingShadowBoundaries(parent))

        ancestry.append(parent);

    // Call pushFullyClippedState on each node starting with the earliest ancestor.

    size_t size = ancestry.size();

    for (size_t i = 0; i < size; ++i)

        pushFullyClippedState(stack, ancestry[size - i - 1]);

    pushFullyClippedState(stack, node);

    ASSERT(stack.size() == 1 + depthCrossingShadowBoundaries(node));

}

// --------

TextIterator::TextIterator()

    : m_startContainer(0)

    , m_startOffset(0)

    , m_endContainer(0)

    , m_endOffset(0)

    , m_positionNode(0)

    , m_textCharacters(0)

    , m_textLength(0)

    , m_lastCharacter(0)

    , m_emitsCharactersBetweenAllVisiblePositions(false)

    , m_entersTextControls(false)

    , m_emitsTextWithoutTranscoding(false)

{

}

TextIterator::TextIterator(const Range* r, TextIteratorBehavior behavior)

    : m_startContainer(0)

    , m_startOffset(0)

    , m_endContainer(0)

    , m_endOffset(0)

    , m_positionNode(0)

    , m_textCharacters(0)

    , m_textLength(0)

    , m_emitsCharactersBetweenAllVisiblePositions(behavior & TextIteratorEmitsCharactersBetweenAllVisiblePositions)

    , m_entersTextControls(behavior & TextIteratorEntersTextControls)

    , m_emitsTextWithoutTranscoding(behavior & TextIteratorEmitsTextsWithoutTranscoding)

{

    if (!r)

        return;

    // get and validate the range endpoints

    Node* startContainer = r->startContainer();

    if (!startContainer)

        return;

    int startOffset = r->startOffset();

    Node* endContainer = r->endContainer();

    int endOffset = r->endOffset();

    // Callers should be handing us well-formed ranges. If we discover that this isn't

    // the case, we could consider changing this assertion to an early return.

    ASSERT(r->boundaryPointsValid());

    // remember range - this does not change

    m_startContainer = startContainer;

    m_startOffset = startOffset;

    m_endContainer = endContainer;

    m_endOffset = endOffset;

    // set up the current node for processing

    m_node = r->firstNode();

    if (!m_node)

        return;

    setUpFullyClippedStack(m_fullyClippedStack, m_node);

    m_offset = m_node == m_startContainer ? m_startOffset : 0;

    m_handledNode = false;

    m_handledChildren = false;

    // calculate first out of bounds node

    m_pastEndNode = nextInPreOrderCrossingShadowBoundaries(endContainer, endOffset);

    // initialize node processing state

    m_needsAnotherNewline = false;

    m_textBox = 0;

    // initialize record of previous node processing

    m_hasEmitted = false;

    m_lastTextNode = 0;

    m_lastTextNodeEndedWithCollapsedSpace = false;

    m_lastCharacter = 0;

#ifndef NDEBUG

    // need this just because of the assert in advance()

    m_positionNode = m_node;

#endif

    // identify the first run

    advance();

}

void TextIterator::advance()

{

    // reset the run information

    m_positionNode = 0;

    m_textLength = 0;

    // handle remembered node that needed a newline after the text node's newline

    if (m_needsAnotherNewline) {

        // Emit the extra newline, and position it *inside* m_node, after m_node's 

        // contents, in case it's a block, in the same way that we position the first 

        // newline.  The range for the emitted newline should start where the line 

        // break begins.

        // FIXME: It would be cleaner if we emitted two newlines during the last 

        // iteration, instead of using m_needsAnotherNewline.

        Node* baseNode = m_node->lastChild() ? m_node->lastChild() : m_node;

        emitCharacter('\n', baseNode->parentNode(), baseNode, 1, 1);

        m_needsAnotherNewline = false;

        return;

    }

    // handle remembered text box

    if (m_textBox) {

        handleTextBox();

        if (m_positionNode)

            return;

    }

    while (m_node && m_node != m_pastEndNode) {

        // if the range ends at offset 0 of an element, represent the

        // position, but not the content, of that element e.g. if the

        // node is a blockflow element, emit a newline that

        // precedes the element

        if (m_node == m_endContainer && m_endOffset == 0) {

            representNodeOffsetZero();

            m_node = 0;

            return;

        }

        RenderObject* renderer = m_node->renderer();

        if (!renderer) {

            m_handledNode = true;

            m_handledChildren = true;

        } else {

            // handle current node according to its type

            if (!m_handledNode) {

                if (renderer->isText() && m_node->nodeType() == Node::TEXT_NODE) // FIXME: What about CDATA_SECTION_NODE?

                    m_handledNode = handleTextNode();

                else if (renderer && (renderer->isImage() || renderer->isWidget() ||

                         (renderer->node() && renderer->node()->isElementNode() &&

                          static_cast<Element*>(renderer->node())->isFormControlElement())))

                    m_handledNode = handleReplacedElement();

                else

                    m_handledNode = handleNonTextNode();

                if (m_positionNode)

                    return;

            }

        }

        // find a new current node to handle in depth-first manner,

        // calling exitNode() as we come back thru a parent node

        Node* next = m_handledChildren ? 0 : m_node->firstChild();

        m_offset = 0;

        if (!next) {

            next = m_node->nextSibling();

            if (!next) {

                bool pastEnd = m_node->traverseNextNode() == m_pastEndNode;

                Node* parentNode = parentCrossingShadowBoundaries(m_node);

                while (!next && parentNode) {

                    if ((pastEnd && parentNode == m_endContainer) || m_endContainer->isDescendantOf(parentNode))

                        return;

                    bool haveRenderer = m_node->renderer();

                    m_node = parentNode;

                    m_fullyClippedStack.pop();

                    parentNode = parentCrossingShadowBoundaries(m_node);

                    if (haveRenderer)

                        exitNode();

                    if (m_positionNode) {

                        m_handledNode = true;

                        m_handledChildren = true;

                        return;

                    }

                    next = m_node->nextSibling();

                }

            }

            m_fullyClippedStack.pop();            

        }

        // set the new current node

        m_node = next;

        if (m_node)

            pushFullyClippedState(m_fullyClippedStack, m_node);

        m_handledNode = false;

        m_handledChildren = false;

        // how would this ever be?

        if (m_positionNode)

            return;

    }

}

static inline bool compareBoxStart(const InlineTextBox* first, const InlineTextBox* second)

{

    return first->start() < second->start();

}

bool TextIterator::handleTextNode()

{

    if (m_fullyClippedStack.top())

        return false;

    RenderText* renderer = toRenderText(m_node->renderer());

    if (renderer->style()->visibility() != VISIBLE)

        return false;

    m_lastTextNode = m_node;

    String str = renderer->text();

    // handle pre-formatted text

    if (!renderer->style()->collapseWhiteSpace()) {

        int runStart = m_offset;

        if (m_lastTextNodeEndedWithCollapsedSpace) {

            emitCharacter(' ', m_node, 0, runStart, runStart);

            return false;

        }

        int strLength = str.length();

        int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;

        int runEnd = min(strLength, end);

        if (runStart >= runEnd)

            return true;

        emitText(m_node, runStart, runEnd);

        return true;

    }

    if (!renderer->firstTextBox() && str.length() > 0) {

        m_lastTextNodeEndedWithCollapsedSpace = true; // entire block is collapsed space

        return true;

    }

    // Used when text boxes are out of order (Hebrew/Arabic w/ embeded LTR text)

    if (renderer->containsReversedText()) {

        m_sortedTextBoxes.clear();

        for (InlineTextBox* textBox = renderer->firstTextBox(); textBox; textBox = textBox->nextTextBox()) {

            m_sortedTextBoxes.append(textBox);

        }

        std::sort(m_sortedTextBoxes.begin(), m_sortedTextBoxes.end(), compareBoxStart); 

        m_sortedTextBoxesPosition = 0;

    }

    m_textBox = renderer->containsReversedText() ? (m_sortedTextBoxes.isEmpty() ? 0 : m_sortedTextBoxes[0]) : renderer->firstTextBox();

    handleTextBox();

    return true;

}

void TextIterator::handleTextBox()

{    

    RenderText* renderer = toRenderText(m_node->renderer());

    String str = renderer->text();

    int start = m_offset;

    int end = (m_node == m_endContainer) ? m_endOffset : INT_MAX;

    while (m_textBox) {

        int textBoxStart = m_textBox->start();

        int runStart = max(textBoxStart, start);

        // Check for collapsed space at the start of this run.

        InlineTextBox* firstTextBox = renderer->containsReversedText() ? m_sortedTextBoxes[0] : renderer->firstTextBox();

        bool needSpace = m_lastTextNodeEndedWithCollapsedSpace

            || (m_textBox == firstTextBox && textBoxStart == runStart && runStart > 0);

        if (needSpace && !isCollapsibleWhitespace(m_lastCharacter) && m_lastCharacter) {

            if (m_lastTextNode == m_node && runStart > 0 && str[runStart - 1] == ' ') {

                unsigned spaceRunStart = runStart - 1;

                while (spaceRunStart > 0 && str[spaceRunStart - 1] == ' ')

                    --spaceRunStart;

                emitText(m_node, spaceRunStart, spaceRunStart + 1);

            } else

                emitCharacter(' ', m_node, 0, runStart, runStart);

            return;

        }

        int textBoxEnd = textBoxStart + m_textBox->len();

        int runEnd = min(textBoxEnd, end);

        // Determine what the next text box will be, but don't advance yet

        InlineTextBox* nextTextBox = 0;

        if (renderer->containsReversedText()) {

            if (m_sortedTextBoxesPosition + 1 < m_sortedTextBoxes.size())

                nextTextBox = m_sortedTextBoxes[m_sortedTextBoxesPosition + 1];

        } else 

            nextTextBox = m_textBox->nextTextBox();

        if (runStart < runEnd) {

            // Handle either a single newline character (which becomes a space),

            // or a run of characters that does not include a newline.

            // This effectively translates newlines to spaces without copying the text.

            if (str[runStart] == '\n') {

                emitCharacter(' ', m_node, 0, runStart, runStart + 1);

                m_offset = runStart + 1;

            } else {

                int subrunEnd = str.find('\n', runStart);

                if (subrunEnd == -1 || subrunEnd > runEnd)

                    subrunEnd = runEnd;