1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtXmlPatterns module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40//
41// W A R N I N G
42// -------------
43//
44// This file is not part of the Qt API. It exists purely as an
45// implementation detail. This header file may change from version to
46// version without notice, or even be removed.
47//
48// We mean it.
49
50#ifndef Patternist_AccelTree_H
51#define Patternist_AccelTree_H
52
53#include <QHash>
54#include <QUrl>
55#include <QVector>
56#include <QXmlName>
57
58#include <private/qitem_p.h>
59#include <private/qnamepool_p.h>
60
61QT_BEGIN_NAMESPACE
62
63namespace QPatternist
64{
65 template<bool> class AccelTreeBuilder;
66
67 /**
68 * @short Stores an XML document using the XPath Accelerator scheme, also
69 * known as pre/post numbering.
70 *
71 * Working on this code will be destructive without a proper understanding of
72 * the Accelerator scheme, so do check out the links. We don't implement any form
73 * of staircase join, although that is only due to time constraints.
74 *
75 * @author Frans Englich <frans.englich@nokia.com>
76 * @see <a href="http://www.pathfinder-xquery.org/?q=research/xpath-accel">XPath
77 * Accelerator</a>
78 * @see <a href="http://www.pathfinder-xquery.org/files/xpath-accel.pdf">Accelerating
79 * XPath Location Steps, Torsten Grust</a>
80 * @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:
81 * Teach a Relational DBMS to Watch its (Axis) Steps</a>
82 * @see <a href="http://ftp.cwi.nl/CWIreports/INS/INS-E0510.pdf">Loop-lifted
83 * staircase join: from XPath to XQuery, Torsten Grust</a>
84 * @see <a href="http://englich.wordpress.com/2007/01/09/xmlstat/">xmlstat, Frans Englich</a>
85 * @see <a href"http://www.inf.uni-konstanz.de/dbis/publications/download/accelerating-locsteps.pdf">Accelerating
86 * XPath Evaluation in Any RDBMS, Torsten Grust</a>
87 */
88 class Q_AUTOTEST_EXPORT AccelTree : public QAbstractXmlNodeModel
89 {
90 friend class AccelTreePrivate;
91 public:
92 using QAbstractXmlNodeModel::createIndex;
93
94 typedef QExplicitlySharedDataPointer<AccelTree> Ptr;
95 typedef qint32 PreNumber;
96 typedef PreNumber PostNumber;
97 typedef qint8 Depth;
98
99 AccelTree(const QUrl &docURI, const QUrl &bURI);
100
101 /**
102 * @short Houses data for a node, and that all node kinds have.
103 *
104 * BasicNodeData is internal to the Accel tree implementation, and is
105 * only used by those classes.
106 *
107 * @author Frans Englich <frans.englich@nokia.com>
108 * @todo Can't m_kind be coded somewhere else? If m_name is invalid,
109 * its bits can be used to distinguish the node types that doesn't have
110 * names, and for elements, attributes and processing instructions, we need
111 * two bits, somewhere. Attributes and processing instructions can't have a
112 * size, is that of help? There's also certain rules for the names. For instance,
113 * a processing instruction will never have a prefix nor namespace. Neither
114 * will an attribute node have a default, non-empty namespace, right?
115 * @todo Compress text nodes, add general support for it in Patternist.
116 */
117 class BasicNodeData
118 {
119 public:
120 /* No need to initialize the members. See AccelTreeBuilder. */
121 inline BasicNodeData()
122 {
123 }
124
125 inline BasicNodeData(const PreNumber aDepth,
126 const PreNumber aParent,
127 const QXmlNodeModelIndex::NodeKind k,
128 const PreNumber s,
129 const QXmlName n = QXmlName()) : m_parent(aParent)
130 , m_size(s)
131 , m_name(n)
132 , m_depth(aDepth)
133 , m_kind(k)
134 {
135 }
136
137 inline Depth depth() const
138 {
139 return m_depth;
140 }
141
142 inline PreNumber parent() const
143 {
144 return m_parent;
145 }
146
147 /**
148 * @see AccelTree::size()
149 */
150 inline PreNumber size() const
151 {
152 /* Remember that we use the m_size to signal compression if
153 * we're a text node. */
154 if(m_kind == QXmlNodeModelIndex::Text)
155 return 0;
156 else
157 return m_size;
158 }
159
160 inline void setSize(const PreNumber aSize)
161 {
162 m_size = aSize;
163 }
164
165 inline QXmlNodeModelIndex::NodeKind kind() const
166 {
167 return m_kind;
168 }
169
170 inline QXmlName name() const
171 {
172 return m_name;
173 }
174
175 inline bool isCompressed() const
176 {
177 Q_ASSERT_X(m_kind == QXmlNodeModelIndex::Text, Q_FUNC_INFO,
178 "Currently, only text nodes are compressed.");
179 /* Note, we don't call size() here, since it has logic for text
180 * nodes. */
181 return m_size == IsCompressed;
182 }
183
184 private:
185 /**
186 * This is the pre number of the parent.
187 */
188 PreNumber m_parent;
189
190 /**
191 * This is the count of children this node has.
192 *
193 * In the case of a text node, which cannot have children,
194 * it is set to IsCompressed, if the content has been the result
195 * of CompressedWhitespace::compress(). If it's not compressed,
196 * it is zero.
197 */
198 PreNumber m_size;
199
200 /**
201 * For text nodes, and less importantly, comments,
202 * this variable is not used.
203 */
204 QXmlName m_name;
205
206 Depth m_depth;
207
208 /**
209 * Technically it is sufficient with 7 bits. However, at least MSVC
210 * 2005 miscompiles it such that QXmlNodeModelIndex::Text becomes
211 * -64 instead of 64 with hilarious crashes as result.
212 *
213 * Fortunately this extra bit would be padded anyway.
214 */
215 QXmlNodeModelIndex::NodeKind m_kind : 8;
216 };
217
218 virtual QUrl baseUri(const QXmlNodeModelIndex &ni) const;
219 virtual QUrl documentUri(const QXmlNodeModelIndex &ni) const;
220 virtual QXmlNodeModelIndex::NodeKind kind(const QXmlNodeModelIndex &ni) const;
221 virtual QXmlNodeModelIndex::DocumentOrder compareOrder(const QXmlNodeModelIndex &ni1,
222 const QXmlNodeModelIndex &ni2) const;
223
224 /**
225 * @short Returns the root node.
226 *
227 * This function does not use @p n, so a default constructed
228 * QXmlNodeModelIndex may be passed.
229 */
230 virtual QXmlNodeModelIndex root(const QXmlNodeModelIndex &n) const;
231
232 virtual QXmlNodeModelIndex parent(const QXmlNodeModelIndex &ni) const;
233 virtual QXmlNodeModelIndex::Iterator::Ptr iterate(const QXmlNodeModelIndex &ni,
234 QXmlNodeModelIndex::Axis axis) const;
235 virtual QXmlName name(const QXmlNodeModelIndex &ni) const;
236 virtual QVector<QXmlName> namespaceBindings(const QXmlNodeModelIndex &n) const;
237 virtual void sendNamespaces(const QXmlNodeModelIndex &n,
238 QAbstractXmlReceiver *const receiver) const;
239 virtual QString stringValue(const QXmlNodeModelIndex &n) const;
240 virtual QVariant typedValue(const QXmlNodeModelIndex &n) const;
241 virtual Item::Iterator::Ptr sequencedTypedValue(const QXmlNodeModelIndex &n) const;
242 virtual ItemType::Ptr type(const QXmlNodeModelIndex &ni) const;
243 virtual QXmlNodeModelIndex elementById(const QXmlName &id) const;
244 virtual QVector<QXmlNodeModelIndex> nodesByIdref(const QXmlName &idref) const;
245 virtual void copyNodeTo(const QXmlNodeModelIndex &node,
246 QAbstractXmlReceiver *const receiver,
247 const NodeCopySettings &settings) const;
248
249 friend class AccelTreeBuilder<false>;
250 friend class AccelTreeBuilder<true>;
251
252 enum Constants
253 {
254 IsCompressed = 1
255 };
256
257 /**
258 * The key is the pre number of an element, and the value is a vector
259 * containing the namespace declarations being declared on that
260 * element. Therefore, it does not reflect the namespaces being in
261 * scope for that element. For that, a walk along axis ancestor is
262 * necessary.
263 */
264 QHash<PreNumber, QVector<QXmlName> > namespaces;
265
266 /**
267 * Stores data for nodes. The QHash's value is the data of the processing instruction, and the
268 * content of a text node or comment.
269 */
270 QHash<PreNumber, QString> data;
271
272 QVector<BasicNodeData> basicData;
273 QHash<PreNumber, QPair<qint64, qint64> > sourcePositions;
274
275 inline QUrl documentUri() const
276 {
277 return m_documentURI;
278 }
279
280 inline QUrl baseUri() const
281 {
282 return m_baseURI;
283 }
284
285 /**
286 * @short Returns @c true if the node identified by @p pre has child
287 * nodes(in the sense of the XDM), but also if it has namespace nodes,
288 * or attribute nodes.
289 */
290 inline bool hasChildren(const PreNumber pre) const
291 {
292 return basicData.at(i: pre).size() > 0;
293 }
294
295 /**
296 * @short Returns the parent node of @p pre.
297 *
298 * If @p pre parent doesn't have a parent node, the return value is
299 * undefined.
300 *
301 * @see hasParent()
302 */
303 inline PreNumber parent(const PreNumber pre) const
304 {
305 return basicData.at(i: pre).parent();
306 }
307
308 inline bool hasParent(const PreNumber pre) const
309 {
310 return basicData.at(i: pre).depth() > 0;
311 }
312
313 inline bool hasFollowingSibling(const PreNumber pre) const
314 {
315 return pre < maximumPreNumber();
316 }
317
318 inline PostNumber postNumber(const PreNumber pre) const
319 {
320 const BasicNodeData &b = basicData.at(i: pre);
321 return pre + b.size() - b.depth();
322 }
323
324 inline QXmlNodeModelIndex::NodeKind kind(const PreNumber pre) const
325 {
326 return basicData.at(i: pre).kind();
327 }
328
329 inline PreNumber maximumPreNumber() const
330 {
331 return basicData.count() - 1;
332 }
333
334 inline PreNumber toPreNumber(const QXmlNodeModelIndex n) const
335 {
336 return n.data();
337 }
338
339 inline PreNumber size(const PreNumber pre) const
340 {
341 Q_ASSERT_X(basicData.at(pre).size() != -1, Q_FUNC_INFO,
342 "The size cannot be -1. That means an uninitialized value is attempted to be used.");
343 return basicData.at(i: pre).size();
344 }
345
346 inline Depth depth(const PreNumber pre) const
347 {
348 return basicData.at(i: pre).depth();
349 }
350
351 void printStats(const NamePool::Ptr &np) const;
352
353 inline QXmlName name(const PreNumber pre) const
354 {
355 return basicData.at(i: pre).name();
356 }
357
358 inline bool isCompressed(const PreNumber pre) const
359 {
360 return basicData.at(i: pre).isCompressed();
361 }
362
363 static inline bool hasPrefix(const QVector<QXmlName> &nbs, const QXmlName::PrefixCode prefix);
364
365 QUrl m_documentURI;
366 QUrl m_baseURI;
367
368 protected:
369 virtual QXmlNodeModelIndex nextFromSimpleAxis(QAbstractXmlNodeModel::SimpleAxis,
370 const QXmlNodeModelIndex&) const;
371 virtual QVector<QXmlNodeModelIndex> attributes(const QXmlNodeModelIndex &element) const;
372
373 private:
374 /**
375 * Returns the source location for the object with the given @p index.
376 */
377 QSourceLocation sourceLocation(const QXmlNodeModelIndex &index) const;
378
379 /**
380 * Copies the children of @p node to @p receiver.
381 */
382 inline void copyChildren(const QXmlNodeModelIndex &node,
383 QAbstractXmlReceiver *const receiver,
384 const NodeCopySettings &settings) const;
385
386 /**
387 * The key is the xml:id value, and the value is the element
388 * with that value.
389 */
390 QHash<QXmlName::LocalNameCode, PreNumber> m_IDs;
391 };
392}
393
394Q_DECLARE_TYPEINFO(QPatternist::AccelTree::BasicNodeData, Q_MOVABLE_TYPE);
395
396QT_END_NAMESPACE
397
398#endif
399

source code of qtxmlpatterns/src/xmlpatterns/acceltree/qacceltree_p.h