src/xmlpatterns/acceltree/qacceltree_p.h

   1 /****************************************************************************
   2 **
   3 ** Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies).
   4 ** Contact: http://www.qt-project.org/
   5 **
   6 ** This file is part of the QtXmlPatterns module of the Qt Toolkit.
   7 **
   8 ** $QT_BEGIN_LICENSE:LGPL$
   9 ** GNU Lesser General Public License Usage
  10 ** This file may be used under the terms of the GNU Lesser General Public
  11 ** License version 2.1 as published by the Free Software Foundation and
  12 ** appearing in the file LICENSE.LGPL included in the packaging of this
  13 ** file. Please review the following information to ensure the GNU Lesser
  14 ** General Public License version 2.1 requirements will be met:
  15 ** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
  16 **
  17 ** In addition, as a special exception, Nokia gives you certain additional
  18 ** rights. These rights are described in the Nokia Qt LGPL Exception
  19 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
  20 **
  21 ** GNU General Public License Usage
  22 ** Alternatively, this file may be used under the terms of the GNU General
  23 ** Public License version 3.0 as published by the Free Software Foundation
  24 ** and appearing in the file LICENSE.GPL included in the packaging of this
  25 ** file. Please review the following information to ensure the GNU General
  26 ** Public License version 3.0 requirements will be met:
  27 ** http://www.gnu.org/copyleft/gpl.html.
  28 **
  29 ** Other Usage
  30 ** Alternatively, this file may be used in accordance with the terms and
  31 ** conditions contained in a signed written agreement between you and Nokia.
  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 <private/qitem_p.h>
  61 #include <private/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 Q_AUTOTEST_EXPORT 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