/****************************************************************************
**
** 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$
**
****************************************************************************/
//
// 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 Q_AUTOTEST_EXPORT 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