/*

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

#include "HTMLNames.h"

#include "htmlediting.h"

#include "InlineTextBox.h"

#include "Position.h"

#include "Range.h"

#include "RenderTableCell.h"

#include "RenderTableRow.h"

#include "visible_units.h"

using namespace std;

using namespace WTF::Unicode;

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.

class CircularSearchBuffer : Noncopyable {

public:

    CircularSearchBuffer(const String& target, bool isCaseSensitive);

    void clear() { m_cursor = 0; m_isBufferFull = false; }

    void append(UChar);

    bool isMatch() const;

    unsigned length() const;

private:

    void append(UChar, bool isCharacterStart);

    String m_target;

    bool m_isCaseSensitive;

    Vector<UChar> m_characterBuffer;

    Vector<bool> m_isCharacterStartBuffer;

    bool m_isBufferFull;

    unsigned m_cursor;

};

// --------

TextIterator::TextIterator() : m_startContainer(0), m_startOffset(0), m_endContainer(0), m_endOffset(0), m_positionNode(0), m_lastCharacter(0)

{

}

TextIterator::TextIterator(const Range* r, bool emitForSelectionPreservation) 

    : m_startContainer(0) 

    , m_startOffset(0)

    , m_endContainer(0)

    , m_endOffset(0)

    , m_positionNode(0)

    , m_emitForSelectionPreservation(emitForSelectionPreservation)

{

    if (!r)

        return;

    ExceptionCode ec = 0;

    // get and validate the range endpoints

    Node *startContainer = r->startContainer(ec);

    int startOffset = r->startOffset(ec);

    Node *endContainer = r->endContainer(ec);

    int endOffset = r->endOffset(ec);

    if (ec != 0)

        return;

    // 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->startNode();

    if (m_node == 0)

        return;

    m_offset = m_node == m_startContainer ? m_startOffset : 0;

    m_handledNode = false;

    m_handledChildren = false;

    // calculate first out of bounds node

    m_pastEndNode = r->pastEndNode();

    // initialize node processing state

    m_needAnotherNewline = false;

    m_textBox = 0;

    // initialize record of previous node processing

    m_haveEmitted = 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_needAnotherNewline) {

        // emit the newline, with position a collapsed range at the end of current node.

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

        m_needAnotherNewline = 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->element() && renderer->element()->isControl())))

                    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;

                while (!next && m_node->parentNode()) {

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

                        return;

                    bool haveRenderer = m_node->renderer();

                    m_node = m_node->parentNode();

                    if (haveRenderer)

                        exitNode();

                    if (m_positionNode) {

                        m_handledNode = true;

                        m_handledChildren = true;

                        return;

                    }

                    next = m_node->nextSibling();

                }

            }

        }

        // set the new current node

        m_node = next;

        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()

{

    RenderText* renderer = static_cast<RenderText*>(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[0] : renderer->firstTextBox();

    handleTextBox();

    return true;

}

void TextIterator::handleTextBox()

{    

    RenderText *renderer = static_cast<RenderText *>(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->m_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) {

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

            return;

        }

        int textBoxEnd = textBoxStart + m_textBox->m_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;

                m_offset = subrunEnd;

                emitText(m_node, runStart, subrunEnd);

            }

            // If we are doing a subrun that doesn't go to the end of the text box,

            // come back again to finish handling this text box; don't advance to the next one.

            if (m_positionEndOffset < textBoxEnd)

                return;

            // Advance and return

            int nextRunStart = nextTextBox ? nextTextBox->m_start : str.length();

            if (nextRunStart > runEnd)

                m_lastTextNodeEndedWithCollapsedSpace = true; // collapsed space between runs or at the end

            m_textBox = nextTextBox;

            if (renderer->containsReversedText())

                ++m_sortedTextBoxesPosition;

            return;

        }

        // Advance and continue

        m_textBox = nextTextBox;

        if (renderer->containsReversedText())

            ++m_sortedTextBoxesPosition;

    }

}

bool TextIterator::handleReplacedElement()

{

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

        return false;

    if (m_lastTextNodeEndedWithCollapsedSpace) {

        emitCharacter(' ', m_lastTextNode->parentNode(), m_lastTextNode, 1, 1);

        return false;

    }

    m_haveEmitted = true;

    if (m_emitForSelectionPreservation) {

        // We want replaced elements to behave like punctuation for boundary 

        // finding, and to simply take up space for the selection preservation 

        // code in moveParagraphs, so we use a comma.

        emitCharacter(',', m_node->parentNode(), m_node, 0, 1);

        return true;

    }

    m_positionNode = m_node->parentNode();

    m_positionOffsetBaseNode = m_node;

    m_positionStartOffset = 0;

    m_positionEndOffset = 1;

    m_textCharacters = 0;

    m_textLength = 0;

    m_lastCharacter = 0;

    return true;

}

static bool isTableCell(Node* node)

{

    RenderObject* r = node->renderer();

    if (!r)

        return node->hasTagName(tdTag) || node->hasTagName(thTag);

    return r->isTableCell();

}

static bool shouldEmitTabBeforeNode(Node* node)

{

    RenderObject* r = node->renderer();

    // Table cells are delimited by tabs.

    if (!r || !isTableCell(node))

        return false;

    // Want a tab before every cell other than the first one

    RenderTableCell* rc = static_cast<RenderTableCell*>(r);

    RenderTable* t = rc->table();

    return t && (t->cellBefore(rc) || t->cellAbove(rc));

}

static bool shouldEmitNewlineForNode(Node* node)

{

    // br elements are represented by a single newline.

    RenderObject* r = node->renderer();

    if (!r)

        return node->hasTagName(brTag);

    return r->isBR();

}

static bool shouldEmitNewlinesBeforeAndAfterNode(Node* node)

{

    // Block flow (versus inline flow) is represented by having

    // a newline both before and after the element.

    RenderObject* r = node->renderer();

    if (!r) {

        return (node->hasTagName(blockquoteTag)

                || node->hasTagName(ddTag)

                || node->hasTagName(divTag)

                || node->hasTagName(dlTag)

                || node->hasTagName(dtTag)

                || node->hasTagName(h1Tag)

                || node->hasTagName(h2Tag)

                || node->hasTagName(h3Tag)

                || node->hasTagName(h4Tag)

                || node->hasTagName(h5Tag)

                || node->hasTagName(h6Tag)

                || node->hasTagName(hrTag)

                || node->hasTagName(liTag)

                || node->hasTagName(listingTag)

                || node->hasTagName(olTag)

                || node->hasTagName(pTag)

                || node->hasTagName(preTag)

                || node->hasTagName(trTag)

                || node->hasTagName(ulTag));

    }

    // Need to make an exception for table cells, because they are blocks, but we

    // want them tab-delimited rather than having newlines before and after.

    if (isTableCell(node))

        return false;

    // Need to make an exception for table row elements, because they are neither

    // "inline" or "RenderBlock", but we want newlines for them.

    if (r->isTableRow()) {

        RenderTable* t = static_cast<RenderTableRow*>(r)->table();

        if (t && !t->isInline())

            return true;

    }

    return !r->isInline() && r->isRenderBlock() && !r->isFloatingOrPositioned() && !r->isBody();

}

static bool shouldEmitNewlineAfterNode(Node* node)

{

    // FIXME: It should be better but slower to create a VisiblePosition here.

    if (!shouldEmitNewlinesBeforeAndAfterNode(node))

        return false;

    // Check if this is the very last renderer in the document.

    // If so, then we should not emit a newline.

    while ((node = node->traverseNextSibling()))

        if (node->renderer())

            return true;

    return false;

}

static bool shouldEmitNewlineBeforeNode(Node* node)

{

    return shouldEmitNewlinesBeforeAndAfterNode(node); 

}

static bool shouldEmitExtraNewlineForNode(Node* node)

{

    // When there is a significant collapsed bottom margin, emit an extra

    // newline for a more realistic result.  We end up getting the right

    // result even without margin collapsing. For example: <div><p>text</p></div>

    // will work right even if both the <div> and the <p> have bottom margins.

    RenderObject* r = node->renderer();

    if (!r)

        return false;

    // NOTE: We only do this for a select set of nodes, and fwiw WinIE appears

    // not to do this at all

    if (node->hasTagName(h1Tag)

        || node->hasTagName(h2Tag)

        || node->hasTagName(h3Tag)

        || node->hasTagName(h4Tag)

        || node->hasTagName(h5Tag)

        || node->hasTagName(h6Tag)

        || node->hasTagName(pTag)) {

        RenderStyle* style = r->style();

        if (style) {

            int bottomMargin = r->collapsedMarginBottom();

            int fontSize = style->fontDescription().computedPixelSize();

            if (bottomMargin * 2 >= fontSize)

                return true;

        }

    }

    return false;

}

bool TextIterator::shouldRepresentNodeOffsetZero()

{

    if (m_emitForSelectionPreservation && m_node->renderer() && m_node->renderer()->isTable())

        return true;

    // Leave element positioned flush with start of a paragraph

    // (e.g. do not insert tab before a table cell at the start of a paragraph)

    if (m_lastCharacter == '\n')

        return false;

    // Otherwise, show the position if we have emitted any characters

    if (m_haveEmitted)

        return true;

    // We've not emitted anything yet. Generally, there is no need for any positioning then.

    // The only exception is when the element is visually not in the same line as

    // the start of the range (e.g. the range starts at the end of the previous paragraph).

    // NOTE: Creating VisiblePositions and comparing them is relatively expensive, so we

    // make quicker checks to possibly avoid that. Another check that we could make is

    // is whether the inline vs block flow changed since the previous visible element.

    // I think we're already in a special enough case that that won't be needed, tho.

    // If we are at the start, obviously no newline is needed.

    if (m_node == m_startContainer)

        return false;

    // If we are outside the start container's subtree, assume we need a newline.