1 /****************************************************************************

     2 **

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

     4 ** All rights reserved.

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

     6 **

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

     8 **

     9 ** $QT_BEGIN_LICENSE:LGPL$

    10 ** No Commercial Usage

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

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

    13 ** contained in the Technology Preview License Agreement accompanying

    14 ** this package.

    15 **

    16 ** GNU Lesser General Public License Usage

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

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

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

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

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

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

    23 **

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

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

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

    27 **

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

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

    30 **

    31 **

    32 **

    33 **

    34 **

    35 **

    36 **

    37 **

    38 ** $QT_END_LICENSE$

    39 **

    40 ****************************************************************************/

    41 

    42 //

    43 //  W A R N I N G

    44 //  -------------

    45 //

    46 // This file is not part of the Qt API.  It exists purely as an

    47 // implementation detail.  This header file may change from version to

    48 // version without notice, or even be removed.

    49 //

    50 // We mean it.

    51 

    52 #ifndef Patternist_AccelTree_H

    53 #define Patternist_AccelTree_H

    54 

    55 #include <QHash>

    56 #include <QUrl>

    57 #include <QVector>

    58 #include <QXmlName>

    59 

    60 #include "qitem_p.h"

    61 #include "qnamepool_p.h"

    62 

    63 QT_BEGIN_HEADER

    64 

    65 QT_BEGIN_NAMESPACE

    66 

    67 namespace QPatternist

    68 {

    69     template<bool> class AccelTreeBuilder;

    70 

    71     /**

    72      * @short Stores an XML document using the XPath Accelerator scheme, also

    73      * known as pre/post numbering.

    74      *

    75      * Working on this code will be destructive without a proper understanding of

    76      * the Accelerator scheme, so do check out the links. We don't implement any form

    77      * of staircase join, although that is only due to time constraints.

    78      *

    79      * @author Frans Englich <frans.englich@nokia.com>

    80      * @see <a href="http://www.pathfinder-xquery.org/?q=research/xpath-accel">XPath

    81      * Accelerator</a>

    82      * @see <a href="http://www.pathfinder-xquery.org/files/xpath-accel.pdf">Accelerating

    83      * XPath Location Steps, Torsten Grust</a>

    84      * @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:

    85      * Teach a Relational DBMS to Watch its (Axis) Steps</a>

    86      * @see <a href="http://ftp.cwi.nl/CWIreports/INS/INS-E0510.pdf">Loop-lifted

    87      * staircase join: from XPath to XQuery, Torsten Grust</a>

    88      * @see <a href="http://englich.wordpress.com/2007/01/09/xmlstat/">xmlstat, Frans Englich</a>

    89      * @see <a href"http://www.inf.uni-konstanz.de/dbis/publications/download/accelerating-locsteps.pdf">Accelerating

    90      * XPath Evaluation in Any RDBMS, Torsten Grust</a>

    91      */

    92     class AccelTree : public QAbstractXmlNodeModel

    93     {

    94         friend class AccelTreePrivate;

    95     public:

    96         using QAbstractXmlNodeModel::createIndex;

    97 

    98         typedef QExplicitlySharedDataPointer<AccelTree> Ptr;

    99         typedef qint32 PreNumber;

   100         typedef PreNumber PostNumber;

   101         typedef qint8 Depth;

   102 

   103         AccelTree(const QUrl &docURI, const QUrl &bURI);

   104 

   105         /**

   106          * @short Houses data for a node, and that all node kinds have.

   107          *

   108          * BasicNodeData is internal to the Accel tree implementation, and is

   109          * only used by those classes.

   110          *

   111          * @author Frans Englich <frans.englich@nokia.com>

   112          * @todo Can't m_kind be coded somewhere else? If m_name is invalid,

   113          * its bits can be used to distinguish the node types that doesn't have

   114          * names, and for elements, attributes and processing instructions, we need

   115          * two bits, somewhere. Attributes and processing instructions can't have a

   116          * size, is that of help? There's also certain rules for the names. For instance,

   117          * a processing instruction will never have a prefix nor namespace. Neither

   118          * will an attribute node have a default, non-empty namespace, right?

   119          * @todo Compress text nodes, add general support for it in Patternist.

   120          */

   121         class BasicNodeData

   122         {

   123         public:

   124             /* No need to initialize the members. See AccelTreeBuilder. */

   125             inline BasicNodeData()

   126             {

   127             }

   128 

   129             inline BasicNodeData(const PreNumber aDepth,

   130                                  const PreNumber aParent,

   131                                  const QXmlNodeModelIndex::NodeKind k,

   132                                  const PreNumber s,

   133                                  const QXmlName n = QXmlName()) : m_parent(aParent)

   134                                                                 , m_size(s)

   135                                                                 , m_name(n)

   136                                                                 , m_depth(aDepth)

   137                                                                 , m_kind(k)

   138             {

   139             }

   140 

   141             inline Depth depth() const

   142             {

   143                 return m_depth;

   144             }

   145 

   146             inline PreNumber parent() const

   147             {

   148                 return m_parent;

   149             }

   150 

   151             /**

   152              * @see AccelTree::size()

   153              */

   154             inline PreNumber size() const

   155             {

   156                 /* Remember that we use the m_size to signal compression if

   157                  * we're a text node. */

   158                 if(m_kind == QXmlNodeModelIndex::Text)

   159                     return 0;

   160                 else

   161                     return m_size;

   162             }

   163 

   164             inline void setSize(const PreNumber aSize)

   165             {

   166                 m_size = aSize;

   167             }

   168 

   169             inline QXmlNodeModelIndex::NodeKind kind() const

   170             {

   171                 return m_kind;

   172             }

   173 

   174             inline QXmlName name() const

   175             {

   176                 return m_name;

   177             }

   178 

   179             inline bool isCompressed() const

   180             {

   181                 Q_ASSERT_X(m_kind == QXmlNodeModelIndex::Text, Q_FUNC_INFO,

   182                            "Currently, only text nodes are compressed.");

   183                 /* Note, we don't call size() here, since it has logic for text

   184                  * nodes. */

   185                 return m_size == IsCompressed;

   186             }

   187 

   188         private:

   189             /**

   190              * This is the pre number of the parent.

   191              */

   192             PreNumber                       m_parent;

   193 

   194             /**

   195              * This is the count of children this node has.

   196              *

   197              * In the case of a text node, which cannot have children,

   198              * it is set to IsCompressed, if the content has been the result

   199              * of CompressedWhitespace::compress(). If it's not compressed,

   200              * it is zero.

   201              */

   202             PreNumber                       m_size;

   203 

   204             /**

   205              * For text nodes, and less importantly, comments,

   206              * this variable is not used.

   207              */

   208             QXmlName                        m_name;

   209 

   210             Depth                           m_depth;

   211 

   212             /**

   213              * Technically it is sufficient with 7 bits. However, at least MSVC

   214              * 2005 miscompiles it such that QXmlNodeModelIndex::Text becomes

   215              * -64 instead of 64 with hilarious crashes as result.

   216              *

   217              * Fortunately this extra bit would be padded anyway.

   218              */

   219             QXmlNodeModelIndex::NodeKind    m_kind : 8;

   220         };

   221 

   222         virtual QUrl baseUri(const QXmlNodeModelIndex &ni) const;

   223         virtual QUrl documentUri(const QXmlNodeModelIndex &ni) const;

   224         virtual QXmlNodeModelIndex::NodeKind kind(const QXmlNodeModelIndex &ni) const;

   225         virtual QXmlNodeModelIndex::DocumentOrder compareOrder(const QXmlNodeModelIndex &ni1,

   226                                                                const QXmlNodeModelIndex &ni2) const;

   227 

   228         /**

   229          * @short Returns the root node.

   230          *

   231          * This function does not use @p n, so a default constructed

   232          * QXmlNodeModelIndex may be passed.

   233          */

   234         virtual QXmlNodeModelIndex root(const QXmlNodeModelIndex &n) const;

   235 

   236         virtual QXmlNodeModelIndex parent(const QXmlNodeModelIndex &ni) const;

   237         virtual QXmlNodeModelIndex::Iterator::Ptr iterate(const QXmlNodeModelIndex &ni,

   238                                                           QXmlNodeModelIndex::Axis axis) const;

   239         virtual QXmlName name(const QXmlNodeModelIndex &ni) const;

   240         virtual QVector<QXmlName> namespaceBindings(const QXmlNodeModelIndex &n) const;

   241         virtual void sendNamespaces(const QXmlNodeModelIndex &n,

   242                                     QAbstractXmlReceiver *const receiver) const;

   243         virtual QString stringValue(const QXmlNodeModelIndex &n) const;

   244         virtual QVariant typedValue(const QXmlNodeModelIndex &n) const;

   245         virtual Item::Iterator::Ptr sequencedTypedValue(const QXmlNodeModelIndex &n) const;

   246         virtual ItemType::Ptr type(const QXmlNodeModelIndex &ni) const;

   247         virtual QXmlNodeModelIndex elementById(const QXmlName &id) const;

   248         virtual QVector<QXmlNodeModelIndex> nodesByIdref(const QXmlName &idref) const;

   249         virtual void copyNodeTo(const QXmlNodeModelIndex &node,

   250                                 QAbstractXmlReceiver *const receiver,

   251                                 const NodeCopySettings &settings) const;

   252 

   253         friend class AccelTreeBuilder<false>;

   254         friend class AccelTreeBuilder<true>;

   255 

   256         enum Constants

   257         {

   258             IsCompressed = 1

   259         };

   260 

   261         /**

   262          * The key is the pre number of an element, and the value is a vector

   263          * containing the namespace declarations being declared on that

   264          * element. Therefore, it does not reflect the namespaces being in

   265          * scope for that element. For that, a walk along axis ancestor is

   266          * necessary.

   267          */

   268         QHash<PreNumber, QVector<QXmlName> > namespaces;

   269 

   270         /**

   271          * Stores data for nodes. The QHash's value is the data of the processing instruction, and the

   272          * content of a text node or comment.

   273          */

   274         QHash<PreNumber, QString> data;

   275 

   276         QVector<BasicNodeData> basicData;

   277         QHash<PreNumber, QPair<qint64, qint64> > sourcePositions;

   278 

   279         inline QUrl documentUri() const

   280         {

   281             return m_documentURI;

   282         }

   283 

   284         inline QUrl baseUri() const

   285         {

   286             return m_baseURI;

   287         }

   288 

   289         /**

   290          * @short Returns @c true if the node identified by @p pre has child

   291          * nodes(in the sense of the XDM), but also if it has namespace nodes,

   292          * or attribute nodes.

   293          */

   294         inline bool hasChildren(const PreNumber pre) const

   295         {

   296             return basicData.at(pre).size() > 0;

   297         }

   298 

   299         /**

   300          * @short Returns the parent node of @p pre.

   301          *

   302          * If @p pre parent doesn't have a parent node, the return value is

   303          * undefined.

   304          *

   305          * @see hasParent()

   306          */

   307         inline PreNumber parent(const PreNumber pre) const

   308         {

   309             return basicData.at(pre).parent();

   310         }

   311 

   312         inline bool hasParent(const PreNumber pre) const

   313         {

   314             return basicData.at(pre).depth() > 0;

   315         }

   316 

   317         inline bool hasFollowingSibling(const PreNumber pre) const

   318         {

   319             return pre < maximumPreNumber();

   320         }

   321 

   322         inline PostNumber postNumber(const PreNumber pre) const

   323         {

   324             const BasicNodeData &b = basicData.at(pre);

   325             return pre + b.size() - b.depth();

   326         }

   327 

   328         inline QXmlNodeModelIndex::NodeKind kind(const PreNumber pre) const

   329         {

   330             return basicData.at(pre).kind();

   331         }

   332 

   333         inline PreNumber maximumPreNumber() const

   334         {

   335             return basicData.count() - 1;

   336         }

   337 

   338         inline PreNumber toPreNumber(const QXmlNodeModelIndex n) const

   339         {

   340             return n.data();

   341         }

   342 

   343         inline PreNumber size(const PreNumber pre) const

   344         {

   345             Q_ASSERT_X(basicData.at(pre).size() != -1, Q_FUNC_INFO,

   346                        "The size cannot be -1. That means an uninitialized value is attempted to be used.");

   347             return basicData.at(pre).size();

   348         }

   349 

   350         inline Depth depth(const PreNumber pre) const

   351         {

   352             return basicData.at(pre).depth();

   353         }

   354 

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

   356 

   357         inline QXmlName name(const PreNumber pre) const

   358         {

   359             return basicData.at(pre).name();

   360         }

   361 

   362         inline bool isCompressed(const PreNumber pre) const

   363         {

   364             return basicData.at(pre).isCompressed();

   365         }

   366 

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

   368 

   369         QUrl m_documentURI;

   370         QUrl m_baseURI;

   371 

   372     protected:

   373         virtual QXmlNodeModelIndex nextFromSimpleAxis(QAbstractXmlNodeModel::SimpleAxis,

   374                                                       const QXmlNodeModelIndex&) const;

   375         virtual QVector<QXmlNodeModelIndex> attributes(const QXmlNodeModelIndex &element) const;

   376 

   377     private:

   378         /**

   379          * Returns the source location for the object with the given @p index.

   380          */

   381         QSourceLocation sourceLocation(const QXmlNodeModelIndex &index) const;

   382 

   383         /**

   384          * Copies the children of @p node to @p receiver.

   385          */

   386         inline void copyChildren(const QXmlNodeModelIndex &node,

   387                                  QAbstractXmlReceiver *const receiver,

   388                                  const NodeCopySettings &settings) const;

   389 

   390         /**

   391          * The key is the xml:id value, and the value is the element

   392          * with that value.

   393          */

   394         QHash<QXmlName::LocalNameCode, PreNumber> m_IDs;

   395     };

   396 }

   397 

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

   399 

   400 QT_END_NAMESPACE

   401 

   402 QT_END_HEADER

   403 

   404 #endif