path: root/src/xmlpatterns/acceltree/qacceltree_p.h

/****************************************************************************
**
** Copyright (C) 2009 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$
**
****************************************************************************/

//
//  W A R N I N G
//  -------------
//
// This file is not part of the Qt API.  It exists purely as an
// implementation detail.  This header file may change from version to
// version without notice, or even be removed.
//
// We mean it.

#ifndef Patternist_AccelTree_H
#define Patternist_AccelTree_H

#include <QHash>
#include <QUrl>
#include <QVector>
#include <QXmlName>

#include "qitem_p.h"
#include "qnamepool_p.h"

QT_BEGIN_HEADER

QT_BEGIN_NAMESPACE

namespace QPatternist
{
    template<bool> class AccelTreeBuilder;

    /**
     * @short Stores an XML document using the XPath Accelerator scheme, also
     * known as pre/post numbering.
     *
     * Working on this code will be destructive without a proper understanding of
     * the Accelerator scheme, so do check out the links. We don't implement any form
     * of staircase join, although that is only due to time constraints.
     *
     * @author Frans Englich <frans.englich@nokia.com>
     * @see <a href="http://www.pathfinder-xquery.org/?q=research/xpath-accel">XPath
     * Accelerator</a>
     * @see <a href="http://www.pathfinder-xquery.org/files/xpath-accel.pdf">Accelerating
     * XPath Location Steps, Torsten Grust</a>
     * @see <a href="http://citeseer.ist.psu.edu/cache/papers/cs/29367/http:zSzzSzwww.informatik.uni-konstanz.dezSz~grustzSzfileszSzstaircase-join.pdf/grust03staircase.pdf">Staircase Join:
     * Teach a Relational DBMS to Watch its (Axis) Steps</a>
     * @see <a href="http://ftp.cwi.nl/CWIreports/INS/INS-E0510.pdf">Loop-lifted
     * staircase join: from XPath to XQuery, Torsten Grust</a>
     * @see <a href="http://englich.wordpress.com/2007/01/09/xmlstat/">xmlstat, Frans Englich</a>
     * @see <a href"http://www.inf.uni-konstanz.de/dbis/publications/download/accelerating-locsteps.pdf">Accelerating
     * XPath Evaluation in Any RDBMS, Torsten Grust</a>
     */
    class AccelTree : public QAbstractXmlNodeModel
    {
    public:
        using QAbstractXmlNodeModel::createIndex;

        typedef QExplicitlySharedDataPointer<AccelTree> Ptr;
        typedef qint32 PreNumber;
        typedef PreNumber PostNumber;
        typedef qint8 Depth;

        inline AccelTree(const QUrl &docURI,
                         const QUrl &bURI) : 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);
        }

        /**
         * @short Houses data for a node, and that all node kinds have.
         *
         * BasicNodeData is internal to the Accel tree implementation, and is
         * only used by those classes.
         *
         * @author Frans Englich <frans.englich@nokia.com>
         * @todo Can't m_kind be coded somewhere else? If m_name is invalid,
         * its bits can be used to distinguish the node types that doesn't have
         * names, and for elements, attributes and processing instructions, we need
         * two bits, somewhere. Attributes and processing instructions can't have a
         * size, is that of help? There's also certain rules for the names. For instance,
         * a processing instruction will never have a prefix nor namespace. Neither
         * will an attribute node have a default, non-empty namespace, right?
         * @todo Compress text nodes, add general support for it in Patternist.
         */
        class BasicNodeData
        {
        public:
            /* No need to initialize the members. See AccelTreeBuilder. */
            inline BasicNodeData()
            {
            }

            inline BasicNodeData(const PreNumber aDepth,
                                 const PreNumber aParent,
                                 const QXmlNodeModelIndex::NodeKind k,
                                 const PreNumber s,
                                 const QXmlName n = QXmlName()) : m_parent(aParent)
                                                                , m_size(s)
                                                                , m_name(n)
                                                                , m_depth(aDepth)
                                                                , m_kind(k)
            {
            }

            inline Depth depth() const
            {
                return m_depth;
            }

            inline PreNumber parent() const
            {
                return m_parent;
            }

            /**
             * @see AccelTree::size()
             */
            inline PreNumber size() const
            {
                /* Remember that we use the m_size to signal compression if
                 * we're a text node. */
                if(m_kind == QXmlNodeModelIndex::Text)
                    return 0;
                else
                    return m_size;
            }

            inline void setSize(const PreNumber aSize)
            {
                m_size = aSize;
            }

            inline QXmlNodeModelIndex::NodeKind kind() const
            {
                return m_kind;
            }

            inline QXmlName name() const
            {
                return m_name;
            }

            inline bool isCompressed() const
            {
                Q_ASSERT_X(m_kind == QXmlNodeModelIndex::Text, Q_FUNC_INFO,
                           "Currently, only text nodes are compressed.");
                /* Note, we don't call size() here, since it has logic for text
                 * nodes. */
                return m_size == IsCompressed;
            }

        private:
            /**
             * This is the pre number of the parent.
             */
            PreNumber                       m_parent;

            /**
             * This is the count of children this node has.
             *
             * In the case of a text node, which cannot have children,
             * it is set to IsCompressed, if the content has been the result
             * of CompressedWhitespace::compress(). If it's not compressed,
             * it is zero.
             */
            PreNumber                       m_size;

            /**
             * For text nodes, and less importantly, comments,
             * this variable is not used.
             */
            QXmlName                        m_name;

            Depth                           m_depth;

            /**
             * Technically it is sufficient with 7 bits. However, at least MSVC
             * 2005 miscompiles it such that QXmlNodeModelIndex::Text becomes
             * -64 instead of 64 with hilarious crashes as result.
             *
             * Fortunately this extra bit would be padded anyway.
             */
            QXmlNodeModelIndex::NodeKind    m_kind : 8;
        };

        virtual QUrl baseUri(const QXmlNodeModelIndex &ni) const;
        virtual QUrl documentUri(const QXmlNodeModelIndex &ni) const;
        virtual QXmlNodeModelIndex::NodeKind kind(const QXmlNodeModelIndex &ni) const;
        virtual QXmlNodeModelIndex::DocumentOrder compareOrder(const QXmlNodeModelIndex &ni1,
                                                               const QXmlNodeModelIndex &ni2) const;

        /**
         * @short Returns the root node.
         *
         * This function does not use @p n, so a default constructed
         * QXmlNodeModelIndex may be passed.
         */
        virtual QXmlNodeModelIndex root(const QXmlNodeModelIndex &n) const;

        virtual QXmlNodeModelIndex parent(const QXmlNodeModelIndex &ni) const;
        virtual QXmlNodeModelIndex::Iterator::Ptr iterate(const QXmlNodeModelIndex &ni,
                                                          QXmlNodeModelIndex::Axis axis) const;
        virtual QXmlName name(const QXmlNodeModelIndex &ni) const;
        virtual QVector<QXmlName> namespaceBindings(const QXmlNodeModelIndex &n) const;
        virtual void sendNamespaces(const QXmlNodeModelIndex &n,
                                    QAbstractXmlReceiver *const receiver) const;
        virtual QString stringValue(const QXmlNodeModelIndex &n) const;
        virtual QVariant typedValue(const QXmlNodeModelIndex &n) const;
        virtual Item::Iterator::Ptr sequencedTypedValue(const QXmlNodeModelIndex &n) const;
        virtual ItemType::Ptr type(const QXmlNodeModelIndex &ni) const;
        virtual QXmlNodeModelIndex elementById(const QXmlName &id) const;
        virtual QVector<QXmlNodeModelIndex> nodesByIdref(const QXmlName &idref) const;
        virtual void copyNodeTo(const QXmlNodeModelIndex &node,
                                QAbstractXmlReceiver *const receiver,
                                const NodeCopySettings &settings) const;

        friend class AccelTreeBuilder<false>;
        friend class AccelTreeBuilder<true>;

        enum Constants
        {
            IsCompressed = 1
        };

        /**
         * The key is the pre number of an element, and the value is a vector
         * containing the namespace declarations being declared on that
         * element. Therefore, it does not reflect the namespaces being in
         * scope for that element. For that, a walk along axis ancestor is
         * necessary.
         */
        QHash<PreNumber, QVector<QXmlName> > namespaces;

        /**
         * Stores data for nodes. The QHash's value is the data of the processing instruction, and the
         * content of a text node or comment.
         */
        QHash<PreNumber, QString> data;

        QVector<BasicNodeData> basicData;

        inline QUrl documentUri() const
        {
            return m_documentURI;
        }

        inline QUrl baseUri() const
        {
            return m_baseURI;
        }

        /**
         * @short Returns @c true if the node identified by @p pre has child
         * nodes(in the sense of the XDM), but also if it has namespace nodes,
         * or attribute nodes.
         */
        inline bool hasChildren(const PreNumber pre) const
        {
            return basicData.at(pre).size() > 0;
        }

        /**
         * @short Returns the parent node of @p pre.
         *
         * If @p pre parent doesn't have a parent node, the return value is
         * undefined.
         *
         * @see hasParent()
         */
        inline PreNumber parent(const PreNumber pre) const
        {
            return basicData.at(pre).parent();
        }

        inline bool hasParent(const PreNumber pre) const
        {
            return basicData.at(pre).depth() > 0;
        }

        inline bool hasFollowingSibling(const PreNumber pre) const
        {
            return pre < maximumPreNumber();
        }

        inline PostNumber postNumber(const PreNumber pre) const
        {
            const BasicNodeData &b = basicData.at(pre);
            return pre + b.size() - b.depth();
        }

        inline QXmlNodeModelIndex::NodeKind kind(const PreNumber pre) const
        {
            return basicData.at(pre).kind();
        }

        inline PreNumber maximumPreNumber() const
        {
            return basicData.count() - 1;
        }

        inline PreNumber toPreNumber(const QXmlNodeModelIndex n) const
        {
            return n.data();
        }

        inline PreNumber size(const PreNumber pre) const
        {
            Q_ASSERT_X(basicData.at(pre).size() != -1, Q_FUNC_INFO,
                       "The size cannot be -1. That means an uninitialized value is attempted to be used.");
            return basicData.at(pre).size();
        }

        inline Depth depth(const PreNumber pre) const
        {
            return basicData.at(pre).depth();
        }

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

        inline QXmlName name(const PreNumber pre) const
        {
            return basicData.at(pre).name();
        }

        inline bool isCompressed(const PreNumber pre) const
        {
            return basicData.at(pre).isCompressed();
        }

        static inline bool hasPrefix(const QVector<QXmlName> &nbs, const QXmlName::PrefixCode prefix);

        QUrl m_documentURI;
        QUrl m_baseURI;

    protected:
        virtual QXmlNodeModelIndex nextFromSimpleAxis(QAbstractXmlNodeModel::SimpleAxis,
                                                      const QXmlNodeModelIndex&) const;
        virtual QVector<QXmlNodeModelIndex> attributes(const QXmlNodeModelIndex &element) const;

    private:
        /**
         * Copies the children of @p node to @p receiver.
         */
        inline void copyChildren(const QXmlNodeModelIndex &node,
                                 QAbstractXmlReceiver *const receiver,
                                 const NodeCopySettings &settings) const;

        /**
         * The key is the xml:id value, and the value is the element
         * with that value.
         */
        QHash<QXmlName::LocalNameCode, PreNumber> m_IDs;
    };
}

Q_DECLARE_TYPEINFO(QPatternist::AccelTree::BasicNodeData, Q_MOVABLE_TYPE);

QT_END_NAMESPACE

QT_END_HEADER

#endif