/*
 * Copyright (C) 2004 Apple Computer, 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 "visible_position.h"

#include "misc/htmltags.h"
#include "rendering/render_line.h"
#include "rendering/render_object.h"
#include "rendering/render_text.h"
#include "xml/dom2_rangeimpl.h"
#include "xml/dom_nodeimpl.h"
#include "xml/dom_textimpl.h"

#if APPLE_CHANGES
#include "KWQAssertions.h"
#include "KWQLogging.h"
#else
#define ASSERT(assertion) assert(assertion)
#define LOG(channel, formatAndArgs...) ((void)0)
#endif

using DOM::CharacterDataImpl;
using DOM::NodeImpl;
using DOM::offsetInCharacters;
using DOM::Position;
using DOM::Range;
using DOM::RangeImpl;
using DOM::StayInBlock;
using DOM::TextImpl;

namespace khtml {

VisiblePosition::VisiblePosition(const Position &pos, EAffinity affinity, EInitHint initHint)
{
    init(pos, initHint, affinity);
}

VisiblePosition::VisiblePosition(NodeImpl *node, long offset, EAffinity affinity, EInitHint initHint)
{
    init(Position(node, offset), initHint, affinity);
}

VisiblePosition::VisiblePosition(const VisiblePosition &other)
{
    m_deepPosition = other.m_deepPosition;
    m_affinity = other.m_affinity;
}

void VisiblePosition::init(const Position &pos, EInitHint initHint, EAffinity affinity)
{
    m_affinity = affinity;

    // A first step toward eliminating the initHint parameter.
    // For <br> 0, it's important not to move past the <br>.
    if (pos.node() && pos.node()->id() == ID_BR && pos.offset() == 0)
        initHint = INIT_UP;

    switch (initHint) {
        case INIT_UP:
            initUpstream(pos);
            break;
        case INIT_DOWN:
            initDownstream(pos);
            break;
        default:
            ASSERT_NOT_REACHED();
            break;
    }
}

void VisiblePosition::initUpstream(const Position &pos)
{
    Position deepPos = deepEquivalent(pos);

    if (isCandidate(deepPos)) {
        m_deepPosition = deepPos;
        Position next = nextVisiblePosition(deepPos);
        if (next.isNotNull()) {
            Position previous = previousVisiblePosition(next);
            if (previous.isNotNull())
                m_deepPosition = previous;
        }
    }
    else {
        Position previous = previousVisiblePosition(deepPos);
        if (previous.isNotNull()) {
            m_deepPosition = previous;
        } else {
            Position next = nextVisiblePosition(deepPos);
            if (next.isNotNull())
                m_deepPosition = next;
        }
    }
}

static bool isRenderedBR(NodeImpl *node)
{
    if (!node)
        return false;

    RenderObject *renderer = node->renderer();
    if (!renderer)
        return false;
    
    if (renderer->style()->visibility() != VISIBLE)
        return false;

    if (renderer->isBR())
        return true;

    return false;
}

void VisiblePosition::initDownstream(const Position &pos)
{
    Position deepPos = deepEquivalent(pos);

    if (isCandidate(deepPos)) {
        m_deepPosition = deepPos;
        Position previous = previousVisiblePosition(deepPos);
        if (previous.isNotNull()) {
            Position next = nextVisiblePosition(previous);
            if (next.isNotNull())
                m_deepPosition = next;
        }
    } else {
        Position next = nextVisiblePosition(deepPos);
        if (next.isNotNull()) {
            m_deepPosition = next;
        } else if (isRenderedBR(deepPos.node()) && deepPos.offset() == 1) {
            m_deepPosition = deepPos;
        } else {
            Position previous = previousVisiblePosition(deepPos);
            if (previous.isNotNull())
                m_deepPosition = previous;
        }
    }
}

VisiblePosition VisiblePosition::next() const
{
    VisiblePosition result = VisiblePosition(nextVisiblePosition(m_deepPosition), m_affinity);
    setAffinityUsingLinePosition(result);
    return result;
}

VisiblePosition VisiblePosition::previous() const
{
    VisiblePosition result =  VisiblePosition(previousVisiblePosition(m_deepPosition), DOWNSTREAM);

#ifndef NDEBUG
    // we should always be able to make the affinity DOWNSTREAM, because going previous from an
    // UPSTREAM position can never yield another UPSTREAM position (unless line wrap length is 0!).
    if (result.isNotNull() && m_affinity == UPSTREAM) {
        VisiblePosition temp = result;
        temp.setAffinity(UPSTREAM);
        ASSERT(!visiblePositionsOnDifferentLines(temp, result));
    }
#endif
    return result;
}

Position VisiblePosition::previousVisiblePosition(const Position &pos)
{
    if (pos.isNull() || atStart(pos))
        return Position();

    Position test = deepEquivalent(pos);
    Position downstreamTest = test.downstream(StayInBlock);
    bool acceptAnyVisiblePosition = !isCandidate(test);

    Position current = test;
    while (!atStart(current)) {
        current = previousPosition(current);
        if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream(StayInBlock)))) {
            return current;
        }
    }
    
    return Position();
}

Position VisiblePosition::nextVisiblePosition(const Position &pos)
{
    if (pos.isNull() || atEnd(pos))
        return Position();

    Position test = deepEquivalent(pos);
    bool acceptAnyVisiblePosition = !isCandidate(test);

    Position current = test;
    Position downstreamTest = test.downstream(StayInBlock);
    while (!atEnd(current)) {
        current = nextPosition(current);
        if (isCandidate(current) && (acceptAnyVisiblePosition || (downstreamTest != current.downstream(StayInBlock)))) {
            return current;
        }
    }
    
    return Position();
}

Position VisiblePosition::previousPosition(const Position &pos)
{
    if (pos.isNull())
        return pos;
    
    Position result;

    if (pos.offset() <= 0) {
        NodeImpl *prevNode = pos.node()->traversePreviousNode();
        if (prevNode)
            result = Position(prevNode, prevNode->maxOffset());
    }
    else {
        NodeImpl *node = pos.node();
        result = Position(node, node->previousOffset(pos.offset()));
    }
    
    return result;
}

Position VisiblePosition::nextPosition(const Position &pos)
{
    if (pos.isNull())
        return pos;
    
    Position result;

    if (pos.offset() >= pos.node()->maxOffset()) {
        NodeImpl *nextNode = pos.node()->traverseNextNode();
        if (nextNode)
            result = Position(nextNode, 0);
    }
    else {
        NodeImpl *node = pos.node();
        result = Position(node, node->nextOffset(pos.offset()));
    }
    
    return result;
}

bool VisiblePosition::atStart(const Position &pos)
{
    if (pos.isNull())
        return true;

    return pos.offset() <= 0 && pos.node()->previousLeafNode() == 0;
}

bool VisiblePosition::atEnd(const Position &pos)
{
    if (pos.isNull())
        return true;

    return pos.offset() >= pos.node()->maxOffset() && pos.node()->nextLeafNode() == 0;
}

bool VisiblePosition::isCandidate(const Position &pos)
{
    if (pos.isNull())
        return false;
        
    RenderObject *renderer = pos.node()->renderer();
    if (!renderer)
        return false;
    
    if (renderer->style()->visibility() != VISIBLE)
        return false;

    if (renderer->isReplaced())
        // return true for replaced elements
        return pos.offset() == 0 || pos.offset() == 1;

    if (renderer->isBR()) {
        if (pos.offset() == 0) {
            InlineBox* box = static_cast<RenderText*>(renderer)->firstTextBox();
            if (box) {
                // return true for offset 0 into BR element on a line by itself
                RootInlineBox* root = box->root();
                if (root)
                    return root->firstLeafChild() == box && root->lastLeafChild() == box;
            }
        }   
        return false;
    }
    
    if (renderer->isText()) {
        RenderText *textRenderer = static_cast<RenderText *>(renderer);
        for (InlineTextBox *box = textRenderer->firstTextBox(); box; box = box->nextTextBox()) {
            if (pos.offset() >= box->m_start && pos.offset() <= box->m_start + box->m_len) {
                // return true if in a text node
                return true;
            }
        }
    }
    
    if (renderer->isBlockFlow() && (!renderer->firstChild() || !pos.node()->firstChild()) && 
       (renderer->height() || pos.node()->id() == ID_BODY)) {
        // return true for offset 0 into rendered blocks that are empty of rendered kids, but have a height
        return pos.offset() == 0;
    }
    
    return false;
}

Position VisiblePosition::deepEquivalent(const Position &pos)
{
    NodeImpl *node = pos.node();