/****************************************************************************

**

** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).

** All rights reserved.

** Contact: Nokia Corporation (qt-info@nokia.com)

**

** This file is part of the QtXmlPatterns module of the Qt Toolkit.

**

** $QT_BEGIN_LICENSE:LGPL$

** No Commercial Usage

** This file contains pre-release code and may not be distributed.

** You may use this file in accordance with the terms and conditions

** contained in the Technology Preview License Agreement accompanying

** this package.

**

** GNU Lesser General Public License Usage

** Alternatively, this file may be used under the terms of the GNU Lesser

** General Public License version 2.1 as published by the Free Software

** Foundation and appearing in the file LICENSE.LGPL included in the

** packaging of this file.  Please review the following information to

** ensure the GNU Lesser General Public License version 2.1 requirements

** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.

**

** In addition, as a special exception, Nokia gives you certain additional

** rights.  These rights are described in the Nokia Qt LGPL Exception

** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.

**

** If you have questions regarding the use of this file, please contact

** Nokia at qt-info@nokia.com.

**

**

**

**

**

**

**

**

** $QT_END_LICENSE$

**

****************************************************************************/

#include <QStack>

#include "qabstractxmlreceiver.h"

#include "qabstractxmlnodemodel_p.h"

#include "qacceliterators_p.h"

#include "qacceltree_p.h"

#include "qatomicstring_p.h"

#include "qcommonvalues_p.h"

#include "qcompressedwhitespace_p.h"

#include "qdebug_p.h"

#include "quntypedatomic_p.h"

#include "qxpathhelper_p.h"

QT_BEGIN_NAMESPACE

using namespace QPatternist;

namespace QPatternist {

    class AccelTreePrivate : public QAbstractXmlNodeModelPrivate

    {

        public:

            AccelTreePrivate(AccelTree *accelTree)

                : m_accelTree(accelTree)

            {

            }

            virtual QSourceLocation sourceLocation(const QXmlNodeModelIndex &index) const

            {

                return m_accelTree->sourceLocation(index);

            }

        private:

            AccelTree *m_accelTree;

    };

}

AccelTree::AccelTree(const QUrl &docURI, const QUrl &bURI)

     : QAbstractXmlNodeModel(new AccelTreePrivate(this))

     , m_documentURI(docURI)

     , m_baseURI(bURI)

{

    /* Pre-allocate at least a little bit. */

    // TODO. Do it according to what an average 4 KB doc contains.

    basicData.reserve(100);

    data.reserve(30);

}

void AccelTree::printStats(const NamePool::Ptr &np) const

{

    Q_ASSERT(np);

#ifdef QT_NO_DEBUG

    Q_UNUSED(np); /* Needed when compiling in release mode. */

#else

    const int len = basicData.count();

    pDebug() << "AccelTree stats for" << (m_documentURI.isEmpty() ? QString::fromLatin1("<empty URI>") : m_documentURI.toString());

    pDebug() << "Maximum pre number:" << maximumPreNumber();

    pDebug() << "+---------------+-------+-------+---------------+-------+--------------+-------+";

    pDebug() << "| Pre number    | Depth | Size  | Post Number   | Kind  | Name         | Value |";

    pDebug() << "+---------------+-------+-------+---------------+-------+--------------+-------+";

    for(int i = 0; i < len; ++i)

    {

        const BasicNodeData &v = basicData.at(i);

        pDebug() << '|' << i

                 << "\t\t|" << v.depth()

                 << "\t|" << v.size()

                 << "\t|" << postNumber(i)

                 << "\t|" << v.kind()

                 << "\t\t|" << (v.name().isNull() ? QString::fromLatin1("(none)") : np->displayName(v.name()))

                 << "\t\t|" << ((v.kind() == QXmlNodeModelIndex::Text && isCompressed(i)) ? CompressedWhitespace::decompress(data.value(i))

                                                                                          : data.value(i))

                 << "\t|";

        /*

        pDebug() << '|' << QString().arg(i, 14)

                 << '|' << QString().arg(v.depth(), 6)

                 << '|' << QString().arg(v.size(), 6)

                 << '|' << QString().arg(postNumber(i), 14)

                 << '|' << QString().arg(v.kind(), 6)

                 << '|';

                 */

    }

    pDebug() << "+---------------+-------+-------+---------------+-------+--------------+";

    pDebug() << "Namespaces(" << namespaces.count() << "):";

    QHashIterator<PreNumber, QVector<QXmlName> > it(namespaces);

    while(it.hasNext())

    {

        it.next();

        pDebug() << "PreNumber: " << QString::number(it.key());

        for(int i = 0; i < it.value().count(); ++i)

            pDebug() << "\t\t" << np->stringForPrefix(it.value().at(i).prefix()) << " = " << np->stringForNamespace(it.value().at(i).namespaceURI());

    }

#endif

}

QUrl AccelTree::baseUri(const QXmlNodeModelIndex &ni) const

{

    switch(kind(toPreNumber(ni)))

    {

        case QXmlNodeModelIndex::Document:

            return baseUri();

        case QXmlNodeModelIndex::Element:

        {

            const QXmlNodeModelIndex::Iterator::Ptr it(iterate(ni, QXmlNodeModelIndex::AxisAttribute));

            QXmlNodeModelIndex next(it->next());

            while(!next.isNull())

            {

                if(next.name() == QXmlName(StandardNamespaces::xml, StandardLocalNames::base))

                {

                    const QUrl candidate(next.stringValue());

                    //  TODO. The xml:base spec says to do URI escaping here.

                    if(!candidate.isValid())

                        return QUrl();

                    else if(candidate.isRelative())

                    {

                        const QXmlNodeModelIndex par(parent(ni));

                        if(par.isNull())

                            return baseUri().resolved(candidate);

                        else

                            return par.baseUri().resolved(candidate);

                    }

                    else

                        return candidate;

                }

                next = it->next();

            }

            /* We have no xml:base-attribute. Can any parent supply us a base URI? */

            const QXmlNodeModelIndex par(parent(ni));

            if(par.isNull())

                return baseUri();

            else

                return par.baseUri();

        }

        case QXmlNodeModelIndex::ProcessingInstruction:

        /* Fallthrough. */

        case QXmlNodeModelIndex::Comment:

        /* Fallthrough. */

        case QXmlNodeModelIndex::Attribute:

        /* Fallthrough. */

        case QXmlNodeModelIndex::Text:

        {

            const QXmlNodeModelIndex par(ni.iterate(QXmlNodeModelIndex::AxisParent)->next());

            if(par.isNull())

                return QUrl();

            else

                return par.baseUri();

        }

        case QXmlNodeModelIndex::Namespace:

            return QUrl();

    }

    Q_ASSERT_X(false, Q_FUNC_INFO, "This line is never supposed to be reached.");

    return QUrl();

}

QUrl AccelTree::documentUri(const QXmlNodeModelIndex &ni) const

{

    if(kind(toPreNumber(ni)) == QXmlNodeModelIndex::Document)

        return documentUri();

    else

        return QUrl();

}

QXmlNodeModelIndex::NodeKind AccelTree::kind(const QXmlNodeModelIndex &ni) const

{

    return kind(toPreNumber(ni));

}

QXmlNodeModelIndex::DocumentOrder AccelTree::compareOrder(const QXmlNodeModelIndex &ni1,

                                                          const QXmlNodeModelIndex &ni2) const

{

    Q_ASSERT_X(ni1.model() == ni2.model(), Q_FUNC_INFO,

               "The API docs guarantees the two nodes are from the same model");

    const PreNumber p1 = ni1.data();

    const PreNumber p2 = ni2.data();

    if(p1 == p2)

        return QXmlNodeModelIndex::Is;

    else if(p1 < p2)

        return QXmlNodeModelIndex::Precedes;

    else

        return QXmlNodeModelIndex::Follows;

}

QXmlNodeModelIndex AccelTree::root(const QXmlNodeModelIndex &) const

{

    return createIndex(qint64(0));

}

QXmlNodeModelIndex AccelTree::parent(const QXmlNodeModelIndex &ni) const

{

    const AccelTree::PreNumber p = basicData.at(toPreNumber(ni)).parent();

    if(p == -1)

        return QXmlNodeModelIndex();

    else

        return createIndex(p);

}

QXmlNodeModelIndex::Iterator::Ptr AccelTree::iterate(const QXmlNodeModelIndex &ni,

                                                     QXmlNodeModelIndex::Axis axis) const

{

    const PreNumber preNumber = toPreNumber(ni);

    switch(axis)

    {

        case QXmlNodeModelIndex::AxisChildOrTop:

        {

            if(!hasParent(preNumber))

            {

                switch(kind(preNumber))

                {

                    case QXmlNodeModelIndex::Comment:

                    /* Fallthrough. */

                    case QXmlNodeModelIndex::ProcessingInstruction:

                    /* Fallthrough. */

                    case QXmlNodeModelIndex::Element:

                    /* Fallthrough. */

                    case QXmlNodeModelIndex::Text:

                        return makeSingletonIterator(ni);

                    case QXmlNodeModelIndex::Attribute:

                    /* Fallthrough. */

                    case QXmlNodeModelIndex::Document:

                    /* Fallthrough. */

                    case QXmlNodeModelIndex::Namespace:

                        /* Do nothing. */;

                }

            }

            /* Else, fallthrough to AxisChild. */

        }

        case QXmlNodeModelIndex::AxisChild:

        {

            if(hasChildren(preNumber))

                return QXmlNodeModelIndex::Iterator::Ptr(new ChildIterator(this, preNumber));

            else

                return makeEmptyIterator<QXmlNodeModelIndex>();

        }

        case QXmlNodeModelIndex::AxisAncestor:

        {

            if(hasParent(preNumber))

                return QXmlNodeModelIndex::Iterator::Ptr(new AncestorIterator<false>(this, preNumber));

            else

                return makeEmptyIterator<QXmlNodeModelIndex>();

        }

        case QXmlNodeModelIndex::AxisAncestorOrSelf:

            return QXmlNodeModelIndex::Iterator::Ptr(new AncestorIterator<true>(this, preNumber));

        case QXmlNodeModelIndex::AxisParent:

        {

            if(hasParent(preNumber))

                return makeSingletonIterator(createIndex(parent(preNumber)));

            else

                return makeEmptyIterator<QXmlNodeModelIndex>();

        }

        case QXmlNodeModelIndex::AxisDescendant:

        {

            if(hasChildren(preNumber))

                return QXmlNodeModelIndex::Iterator::Ptr(new DescendantIterator<false>(this, preNumber));

            else

                return makeEmptyIterator<QXmlNodeModelIndex>();

        }

        case QXmlNodeModelIndex::AxisDescendantOrSelf:

            return QXmlNodeModelIndex::Iterator::Ptr(new DescendantIterator<true>(this, preNumber));

        case QXmlNodeModelIndex::AxisFollowing:

        {

            if(preNumber == maximumPreNumber())

                return makeEmptyIterator<QXmlNodeModelIndex>();

            else

                return QXmlNodeModelIndex::Iterator::Ptr(new FollowingIterator(this, preNumber));

        }

        case QXmlNodeModelIndex::AxisAttributeOrTop:

        {

            if(!hasParent(preNumber) && kind(preNumber) == QXmlNodeModelIndex::Attribute)

                return makeSingletonIterator(ni);

            /* Else, falthrough to AxisAttribute. */

        }

        case QXmlNodeModelIndex::AxisAttribute:

        {

            if(hasChildren(preNumber) && kind(preNumber + 1) == QXmlNodeModelIndex::Attribute)

                return QXmlNodeModelIndex::Iterator::Ptr(new AttributeIterator(this, preNumber));

            else

                return makeEmptyIterator<QXmlNodeModelIndex>();

        }

        case QXmlNodeModelIndex::AxisPreceding:

        {

            if(preNumber == 0)

                return makeEmptyIterator<QXmlNodeModelIndex>();

            else

                return QXmlNodeModelIndex::Iterator::Ptr(new PrecedingIterator(this, preNumber));

        }

        case QXmlNodeModelIndex::AxisSelf:

            return makeSingletonIterator(createIndex(toPreNumber(ni)));

        case QXmlNodeModelIndex::AxisFollowingSibling:

        {

            if(preNumber == maximumPreNumber())

                return makeEmptyIterator<QXmlNodeModelIndex>();

            else

                return QXmlNodeModelIndex::Iterator::Ptr(new SiblingIterator<true>(this, preNumber));

        }

        case QXmlNodeModelIndex::AxisPrecedingSibling:

        {

            if(preNumber == 0)

                return makeEmptyIterator<QXmlNodeModelIndex>();

            else

                return QXmlNodeModelIndex::Iterator::Ptr(new SiblingIterator<false>(this, preNumber));

        }

        case QXmlNodeModelIndex::AxisNamespace:

            return makeEmptyIterator<QXmlNodeModelIndex>();

    }

    Q_ASSERT(false);

    return QXmlNodeModelIndex::Iterator::Ptr();

}

QXmlNodeModelIndex AccelTree::nextFromSimpleAxis(QAbstractXmlNodeModel::SimpleAxis,

                                                 const QXmlNodeModelIndex&) const

{

    Q_ASSERT_X(false, Q_FUNC_INFO, "This function is not supposed to be called.");

    return QXmlNodeModelIndex();

}

QVector<QXmlNodeModelIndex> AccelTree::attributes(const QXmlNodeModelIndex &element) const

{

    Q_ASSERT_X(false, Q_FUNC_INFO, "This function is not supposed to be called.");

    Q_UNUSED(element);

    return QVector<QXmlNodeModelIndex>();

}

QXmlName AccelTree::name(const QXmlNodeModelIndex &ni) const

{

    /* If this node type does not have a name(for instance, it's a comment)

     * we will return the default constructed value, which is conformant with

     * this function's contract. */

    return name(toPreNumber(ni));

}

QVector<QXmlName> AccelTree::namespaceBindings(const QXmlNodeModelIndex &ni) const

{

    /* We get a hold of the ancestor, and loop them in reverse document

     * order(first the parent, then the parent's parent, etc). As soon

     * we find a binding that hasn't already been added, we add it to the

     * result list. In that way, declarations appearing further down override

     * those further up. */

    const PreNumber preNumber = toPreNumber(ni);

    const QXmlNodeModelIndex::Iterator::Ptr it(new AncestorIterator<true>(this, preNumber));

    QVector<QXmlName> result;

    QXmlNodeModelIndex n(it->next());

    /* Whether xmlns="" has been encountered. */

    bool hasUndeclaration = false;

    while(!n.isNull())

    {

        const QVector<QXmlName> &forNode = namespaces.value(toPreNumber(n));

        const int len = forNode.size();

        bool stopInheritance = false;

        for(int i = 0; i < len; ++i)

        {

            const QXmlName &nsb = forNode.at(i);

            if(nsb.namespaceURI() == StandardNamespaces::StopNamespaceInheritance)

            {

                stopInheritance = true;

                continue;

            }

            if(nsb.prefix() == StandardPrefixes::empty &&

               nsb.namespaceURI() == StandardNamespaces::empty)

            {

                hasUndeclaration = true;

                continue;

            }

            if(!hasPrefix(result, nsb.prefix()))

            {

                /* We've already encountered an undeclaration, so we're supposed to skip

                 * them. */

                if(hasUndeclaration && nsb.prefix() == StandardPrefixes::empty)

                    continue;

                else

                    result.append(nsb);

            }

        }

        if(stopInheritance)

            break;

        else

            n = it->next();

    }

    result.append(QXmlName(StandardNamespaces::xml, StandardLocalNames::empty, StandardPrefixes::xml));

    return result;

}

void AccelTree::sendNamespaces(const QXmlNodeModelIndex &n,

                               QAbstractXmlReceiver *const receiver) const

{

    Q_ASSERT(n.kind() == QXmlNodeModelIndex::Element);

    const QXmlNodeModelIndex::Iterator::Ptr it(iterate(n, QXmlNodeModelIndex::AxisAncestorOrSelf));

    QXmlNodeModelIndex next(it->next());

    QVector<QXmlName::PrefixCode> alreadySent;

    while(!next.isNull())

    {

        const PreNumber preNumber = toPreNumber(next);

        const QVector<QXmlName> &nss = namespaces.value(preNumber);

        /* This is by far the most common case. */

        if(nss.isEmpty())

        {

            next = it->next();

            continue;

        }

        const int len = nss.count();

        bool stopInheritance = false;

        for(int i = 0; i < len; ++i)

        {

            const QXmlName &name = nss.at(i);

            if(name.namespaceURI() == StandardNamespaces::StopNamespaceInheritance)

            {

                stopInheritance = true;

                continue;

            }

            if(!alreadySent.contains(name.prefix()))

            {

                alreadySent.append(name.prefix());

                receiver->namespaceBinding(name);

            }

        }

        if(stopInheritance)

            break;

        else

            next = it->next();

    }

}

QString AccelTree::stringValue(const QXmlNodeModelIndex &ni) const

{

    const PreNumber preNumber = toPreNumber(ni);

    switch(kind(preNumber))

    {

        case QXmlNodeModelIndex::Element:

        {

            /* Concatenate all text nodes that are descendants of this node. */

            if(!hasChildren(preNumber))

                return QString();

            const AccelTree::PreNumber stop = preNumber + size(preNumber);

            AccelTree::PreNumber pn = preNumber + 1; /* Jump over ourselves. */

            QString result;

            for(; pn <= stop; ++pn)

            {

                if(kind(pn) == QXmlNodeModelIndex::Text)

                {

                    if(isCompressed(pn))

                        result += CompressedWhitespace::decompress(data.value(pn));

                    else

                        result += data.value(pn);

                }

            }

            return result;

        }

        case QXmlNodeModelIndex::Text:

        {

            if(isCompressed(preNumber))