--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/src/xmlpatterns/acceltree/qacceltree_p.h Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,404 @@
+/****************************************************************************
+**
+** 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
+ {
+ friend class AccelTreePrivate;
+ public:
+ using QAbstractXmlNodeModel::createIndex;
+
+ typedef QExplicitlySharedDataPointer<AccelTree> Ptr;
+ typedef qint32 PreNumber;
+ typedef PreNumber PostNumber;
+ typedef qint8 Depth;
+
+ AccelTree(const QUrl &docURI, const QUrl &bURI);
+
+ /**
+ * @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;
+ QHash<PreNumber, QPair<qint64, qint64> > sourcePositions;
+
+ 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:
+ /**
+ * Returns the source location for the object with the given @p index.
+ */
+ QSourceLocation sourceLocation(const QXmlNodeModelIndex &index) const;
+
+ /**
+ * 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