source: trunk/src/xmlpatterns/acceltree/qacceltree.cpp@ 651

Last change on this file since 651 was 651, checked in by Dmitry A. Kuminov, 15 years ago

trunk: Merged in qt 4.6.2 sources.
File size: 25.7 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation ([email protected])
6**
7** This file is part of the QtXmlPatterns module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
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** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you have questions regarding the use of this file, please contact
37** Nokia at [email protected].
38** $QT_END_LICENSE$
39**
40****************************************************************************/
41
42#include <QStack>
43
44#include "qabstractxmlreceiver.h"
45#include "qabstractxmlnodemodel_p.h"
46#include "qacceliterators_p.h"
47#include "qacceltree_p.h"
48#include "qatomicstring_p.h"
49#include "qcommonvalues_p.h"
50#include "qcompressedwhitespace_p.h"
51#include "qdebug_p.h"
52#include "quntypedatomic_p.h"
53#include "qxpathhelper_p.h"
54
55QT_BEGIN_NAMESPACE
56
57using namespace QPatternist;
58
59namespace QPatternist {
60
61 class AccelTreePrivate : public QAbstractXmlNodeModelPrivate
62 {
63 public:
64 AccelTreePrivate(AccelTree *accelTree)
65 : m_accelTree(accelTree)
66 {
67 }
68
69 virtual QSourceLocation sourceLocation(const QXmlNodeModelIndex &index) const
70 {
71 return m_accelTree->sourceLocation(index);
72 }
73
74 private:
75 AccelTree *m_accelTree;
76 };
77}
78
79AccelTree::AccelTree(const QUrl &docURI, const QUrl &bURI)
80 : QAbstractXmlNodeModel(new AccelTreePrivate(this))
81 , m_documentURI(docURI)
82 , m_baseURI(bURI)
83{
84 /* Pre-allocate at least a little bit. */
85 // TODO. Do it according to what an average 4 KB doc contains.
86 basicData.reserve(100);
87 data.reserve(30);
88}
89
90void AccelTree::printStats(const NamePool::Ptr &np) const
91{
92 Q_ASSERT(np);
93#ifdef QT_NO_DEBUG
94 Q_UNUSED(np); /* Needed when compiling in release mode. */
95#else
96 const int len = basicData.count();
97
98 pDebug() << "AccelTree stats for" << (m_documentURI.isEmpty() ? QString::fromLatin1("<empty URI>") : m_documentURI.toString());
99 pDebug() << "Maximum pre number:" << maximumPreNumber();
100 pDebug() << "+---------------+-------+-------+---------------+-------+--------------+-------+";
101 pDebug() << "| Pre number | Depth | Size | Post Number | Kind | Name | Value |";
102 pDebug() << "+---------------+-------+-------+---------------+-------+--------------+-------+";
103 for(int i = 0; i < len; ++i)
104 {
105 const BasicNodeData &v = basicData.at(i);
106 pDebug() << '|' << i
107 << "\t\t|" << v.depth()
108 << "\t|" << v.size()
109 << "\t|" << postNumber(i)
110 << "\t|" << v.kind()
111 << "\t\t|" << (v.name().isNull() ? QString::fromLatin1("(none)") : np->displayName(v.name()))
112 << "\t\t|" << ((v.kind() == QXmlNodeModelIndex::Text && isCompressed(i)) ? CompressedWhitespace::decompress(data.value(i))
113 : data.value(i))
114 << "\t|";
115 /*
116 pDebug() << '|' << QString().arg(i, 14)
117 << '|' << QString().arg(v.depth(), 6)
118 << '|' << QString().arg(v.size(), 6)
119 << '|' << QString().arg(postNumber(i), 14)
120 << '|' << QString().arg(v.kind(), 6)
121 << '|';
122 */
123 }
124 pDebug() << "+---------------+-------+-------+---------------+-------+--------------+";
125 pDebug() << "Namespaces(" << namespaces.count() << "):";
126
127 QHashIterator<PreNumber, QVector<QXmlName> > it(namespaces);
128 while(it.hasNext())
129 {
130 it.next();
131
132 pDebug() << "PreNumber: " << QString::number(it.key());
133 for(int i = 0; i < it.value().count(); ++i)
134 pDebug() << "\t\t" << np->stringForPrefix(it.value().at(i).prefix()) << " = " << np->stringForNamespace(it.value().at(i).namespaceURI());
135 }
136
137#endif
138}
139
140QUrl AccelTree::baseUri(const QXmlNodeModelIndex &ni) const
141{
142 switch(kind(toPreNumber(ni)))
143 {
144 case QXmlNodeModelIndex::Document:
145 return baseUri();
146 case QXmlNodeModelIndex::Element:
147 {
148 const QXmlNodeModelIndex::Iterator::Ptr it(iterate(ni, QXmlNodeModelIndex::AxisAttribute));
149 QXmlNodeModelIndex next(it->next());
150
151 while(!next.isNull())
152 {
153 if(next.name() == QXmlName(StandardNamespaces::xml, StandardLocalNames::base))
154 {
155 const QUrl candidate(next.stringValue());
156 // TODO. The xml:base spec says to do URI escaping here.
157
158 if(!candidate.isValid())
159 return QUrl();
160 else if(candidate.isRelative())
161 {
162 const QXmlNodeModelIndex par(parent(ni));
163
164 if(par.isNull())
165 return baseUri().resolved(candidate);
166 else
167 return par.baseUri().resolved(candidate);
168 }
169 else
170 return candidate;
171 }
172
173 next = it->next();
174 }
175
176 /* We have no xml:base-attribute. Can any parent supply us a base URI? */
177 const QXmlNodeModelIndex par(parent(ni));
178
179 if(par.isNull())
180 return baseUri();
181 else
182 return par.baseUri();
183 }
184 case QXmlNodeModelIndex::ProcessingInstruction:
185 /* Fallthrough. */
186 case QXmlNodeModelIndex::Comment:
187 /* Fallthrough. */
188 case QXmlNodeModelIndex::Attribute:
189 /* Fallthrough. */
190 case QXmlNodeModelIndex::Text:
191 {
192 const QXmlNodeModelIndex par(ni.iterate(QXmlNodeModelIndex::AxisParent)->next());
193 if(par.isNull())
194 return QUrl();
195 else
196 return par.baseUri();
197 }
198 case QXmlNodeModelIndex::Namespace:
199 return QUrl();
200 }
201
202 Q_ASSERT_X(false, Q_FUNC_INFO, "This line is never supposed to be reached.");
203 return QUrl();
204}
205
206QUrl AccelTree::documentUri(const QXmlNodeModelIndex &ni) const
207{
208 if(kind(toPreNumber(ni)) == QXmlNodeModelIndex::Document)
209 return documentUri();
210 else
211 return QUrl();
212}
213
214QXmlNodeModelIndex::NodeKind AccelTree::kind(const QXmlNodeModelIndex &ni) const
215{
216 return kind(toPreNumber(ni));
217}
218
219QXmlNodeModelIndex::DocumentOrder AccelTree::compareOrder(const QXmlNodeModelIndex &ni1,
220 const QXmlNodeModelIndex &ni2) const
221{
222 Q_ASSERT_X(ni1.model() == ni2.model(), Q_FUNC_INFO,
223 "The API docs guarantees the two nodes are from the same model");
224
225 const PreNumber p1 = ni1.data();
226 const PreNumber p2 = ni2.data();
227
228 if(p1 == p2)
229 return QXmlNodeModelIndex::Is;
230 else if(p1 < p2)
231 return QXmlNodeModelIndex::Precedes;
232 else
233 return QXmlNodeModelIndex::Follows;
234}
235
236QXmlNodeModelIndex AccelTree::root(const QXmlNodeModelIndex &) const
237{
238 return createIndex(qint64(0));
239}
240
241QXmlNodeModelIndex AccelTree::parent(const QXmlNodeModelIndex &ni) const
242{
243 const AccelTree::PreNumber p = basicData.at(toPreNumber(ni)).parent();
244
245 if(p == -1)
246 return QXmlNodeModelIndex();
247 else
248 return createIndex(p);
249}
250
251QXmlNodeModelIndex::Iterator::Ptr AccelTree::iterate(const QXmlNodeModelIndex &ni,
252 QXmlNodeModelIndex::Axis axis) const
253{
254 const PreNumber preNumber = toPreNumber(ni);
255
256 switch(axis)
257 {
258 case QXmlNodeModelIndex::AxisChildOrTop:
259 {
260 if(!hasParent(preNumber))
261 {
262 switch(kind(preNumber))
263 {
264 case QXmlNodeModelIndex::Comment:
265 /* Fallthrough. */
266 case QXmlNodeModelIndex::ProcessingInstruction:
267 /* Fallthrough. */
268 case QXmlNodeModelIndex::Element:
269 /* Fallthrough. */
270 case QXmlNodeModelIndex::Text:
271 return makeSingletonIterator(ni);
272 case QXmlNodeModelIndex::Attribute:
273 /* Fallthrough. */
274 case QXmlNodeModelIndex::Document:
275 /* Fallthrough. */
276 case QXmlNodeModelIndex::Namespace:
277 /* Do nothing. */;
278 }
279 }
280 /* Else, fallthrough to AxisChild. */
281 }
282 case QXmlNodeModelIndex::AxisChild:
283 {
284 if(hasChildren(preNumber))
285 return QXmlNodeModelIndex::Iterator::Ptr(new ChildIterator(this, preNumber));
286 else
287 return makeEmptyIterator<QXmlNodeModelIndex>();
288 }
289 case QXmlNodeModelIndex::AxisAncestor:
290 {
291 if(hasParent(preNumber))
292 return QXmlNodeModelIndex::Iterator::Ptr(new AncestorIterator<false>(this, preNumber));
293 else
294 return makeEmptyIterator<QXmlNodeModelIndex>();
295 }
296 case QXmlNodeModelIndex::AxisAncestorOrSelf:
297 return QXmlNodeModelIndex::Iterator::Ptr(new AncestorIterator<true>(this, preNumber));
298 case QXmlNodeModelIndex::AxisParent:
299 {
300 if(hasParent(preNumber))
301 return makeSingletonIterator(createIndex(parent(preNumber)));
302 else
303 return makeEmptyIterator<QXmlNodeModelIndex>();
304 }
305 case QXmlNodeModelIndex::AxisDescendant:
306 {
307 if(hasChildren(preNumber))
308 return QXmlNodeModelIndex::Iterator::Ptr(new DescendantIterator<false>(this, preNumber));
309 else
310 return makeEmptyIterator<QXmlNodeModelIndex>();
311 }
312 case QXmlNodeModelIndex::AxisDescendantOrSelf:
313 return QXmlNodeModelIndex::Iterator::Ptr(new DescendantIterator<true>(this, preNumber));
314 case QXmlNodeModelIndex::AxisFollowing:
315 {
316 if(preNumber == maximumPreNumber())
317 return makeEmptyIterator<QXmlNodeModelIndex>();
318 else
319 return QXmlNodeModelIndex::Iterator::Ptr(new FollowingIterator(this, preNumber));
320 }
321 case QXmlNodeModelIndex::AxisAttributeOrTop:
322 {
323 if(!hasParent(preNumber) && kind(preNumber) == QXmlNodeModelIndex::Attribute)
324 return makeSingletonIterator(ni);
325 /* Else, falthrough to AxisAttribute. */
326 }
327 case QXmlNodeModelIndex::AxisAttribute:
328 {
329 if(hasChildren(preNumber) && kind(preNumber + 1) == QXmlNodeModelIndex::Attribute)
330 return QXmlNodeModelIndex::Iterator::Ptr(new AttributeIterator(this, preNumber));
331 else
332 return makeEmptyIterator<QXmlNodeModelIndex>();
333 }
334 case QXmlNodeModelIndex::AxisPreceding:
335 {
336 if(preNumber == 0)
337 return makeEmptyIterator<QXmlNodeModelIndex>();
338 else
339 return QXmlNodeModelIndex::Iterator::Ptr(new PrecedingIterator(this, preNumber));
340 }
341 case QXmlNodeModelIndex::AxisSelf:
342 return makeSingletonIterator(createIndex(toPreNumber(ni)));
343 case QXmlNodeModelIndex::AxisFollowingSibling:
344 {
345 if(preNumber == maximumPreNumber())
346 return makeEmptyIterator<QXmlNodeModelIndex>();
347 else
348 return QXmlNodeModelIndex::Iterator::Ptr(new SiblingIterator<true>(this, preNumber));
349 }
350 case QXmlNodeModelIndex::AxisPrecedingSibling:
351 {
352 if(preNumber == 0)
353 return makeEmptyIterator<QXmlNodeModelIndex>();
354 else
355 return QXmlNodeModelIndex::Iterator::Ptr(new SiblingIterator<false>(this, preNumber));
356 }
357 case QXmlNodeModelIndex::AxisNamespace:
358 return makeEmptyIterator<QXmlNodeModelIndex>();
359 }
360
361 Q_ASSERT(false);
362 return QXmlNodeModelIndex::Iterator::Ptr();
363}
364
365QXmlNodeModelIndex AccelTree::nextFromSimpleAxis(QAbstractXmlNodeModel::SimpleAxis,
366 const QXmlNodeModelIndex&) const
367{
368 Q_ASSERT_X(false, Q_FUNC_INFO, "This function is not supposed to be called.");
369 return QXmlNodeModelIndex();
370}
371
372QVector<QXmlNodeModelIndex> AccelTree::attributes(const QXmlNodeModelIndex &element) const
373{
374 Q_ASSERT_X(false, Q_FUNC_INFO, "This function is not supposed to be called.");
375 Q_UNUSED(element);
376 return QVector<QXmlNodeModelIndex>();
377}
378
379QXmlName AccelTree::name(const QXmlNodeModelIndex &ni) const
380{
381 /* If this node type does not have a name(for instance, it's a comment)
382 * we will return the default constructed value, which is conformant with
383 * this function's contract. */
384 return name(toPreNumber(ni));
385}
386
387QVector<QXmlName> AccelTree::namespaceBindings(const QXmlNodeModelIndex &ni) const
388{
389 /* We get a hold of the ancestor, and loop them in reverse document
390 * order(first the parent, then the parent's parent, etc). As soon
391 * we find a binding that hasn't already been added, we add it to the
392 * result list. In that way, declarations appearing further down override
393 * those further up. */
394
395 const PreNumber preNumber = toPreNumber(ni);
396
397 const QXmlNodeModelIndex::Iterator::Ptr it(new AncestorIterator<true>(this, preNumber));
398 QVector<QXmlName> result;
399 QXmlNodeModelIndex n(it->next());
400
401 /* Whether xmlns="" has been encountered. */
402 bool hasUndeclaration = false;
403
404 while(!n.isNull())
405 {
406 const QVector<QXmlName> &forNode = namespaces.value(toPreNumber(n));
407 const int len = forNode.size();
408 bool stopInheritance = false;
409
410 for(int i = 0; i < len; ++i)
411 {
412 const QXmlName &nsb = forNode.at(i);
413
414 if(nsb.namespaceURI() == StandardNamespaces::StopNamespaceInheritance)
415 {
416 stopInheritance = true;
417 continue;
418 }
419
420 if(nsb.prefix() == StandardPrefixes::empty &&
421 nsb.namespaceURI() == StandardNamespaces::empty)
422 {
423 hasUndeclaration = true;
424 continue;
425 }
426
427 if(!hasPrefix(result, nsb.prefix()))
428 {
429 /* We've already encountered an undeclaration, so we're supposed to skip
430 * them. */
431 if(hasUndeclaration && nsb.prefix() == StandardPrefixes::empty)
432 continue;
433 else
434 result.append(nsb);
435 }
436 }
437
438 if(stopInheritance)
439 break;
440 else
441 n = it->next();
442 }
443
444 result.append(QXmlName(StandardNamespaces::xml, StandardLocalNames::empty, StandardPrefixes::xml));
445
446 return result;
447}
448
449void AccelTree::sendNamespaces(const QXmlNodeModelIndex &n,
450 QAbstractXmlReceiver *const receiver) const
451{
452 Q_ASSERT(n.kind() == QXmlNodeModelIndex::Element);
453
454 const QXmlNodeModelIndex::Iterator::Ptr it(iterate(n, QXmlNodeModelIndex::AxisAncestorOrSelf));
455 QXmlNodeModelIndex next(it->next());
456 QVector<QXmlName::PrefixCode> alreadySent;
457
458 while(!next.isNull())
459 {
460 const PreNumber preNumber = toPreNumber(next);
461
462 const QVector<QXmlName> &nss = namespaces.value(preNumber);
463
464 /* This is by far the most common case. */
465 if(nss.isEmpty())
466 {
467 next = it->next();
468 continue;
469 }
470
471 const int len = nss.count();
472 bool stopInheritance = false;
473
474 for(int i = 0; i < len; ++i)
475 {
476 const QXmlName &name = nss.at(i);
477
478 if(name.namespaceURI() == StandardNamespaces::StopNamespaceInheritance)
479 {
480 stopInheritance = true;
481 continue;
482 }
483
484 if(!alreadySent.contains(name.prefix()))
485 {
486 alreadySent.append(name.prefix());
487 receiver->namespaceBinding(name);
488 }
489 }
490
491 if(stopInheritance)
492 break;
493 else
494 next = it->next();
495 }
496}
497
498QString AccelTree::stringValue(const QXmlNodeModelIndex &ni) const
499{
500 const PreNumber preNumber = toPreNumber(ni);
501
502 switch(kind(preNumber))
503 {
504 case QXmlNodeModelIndex::Element:
505 {
506 /* Concatenate all text nodes that are descendants of this node. */
507 if(!hasChildren(preNumber))
508 return QString();
509
510 const AccelTree::PreNumber stop = preNumber + size(preNumber);
511 AccelTree::PreNumber pn = preNumber + 1; /* Jump over ourselves. */
512 QString result;
513
514 for(; pn <= stop; ++pn)
515 {
516 if(kind(pn) == QXmlNodeModelIndex::Text)
517 {
518 if(isCompressed(pn))
519 result += CompressedWhitespace::decompress(data.value(pn));
520 else
521 result += data.value(pn);
522 }
523 }
524
525 return result;
526 }
527 case QXmlNodeModelIndex::Text:
528 {
529 if(isCompressed(preNumber))
530 return CompressedWhitespace::decompress(data.value(preNumber));
531 /* Else, fallthrough. It's not compressed so use it as it is. */
532 }
533 case QXmlNodeModelIndex::Attribute:
534 /* Fallthrough */
535 case QXmlNodeModelIndex::ProcessingInstruction:
536 /* Fallthrough */
537 case QXmlNodeModelIndex::Comment:
538 return data.value(preNumber);
539 case QXmlNodeModelIndex::Document:
540 {
541 /* Concatenate all text nodes in the whole document. */
542
543 QString result;
544 // Perhaps we can QString::reserve() the result based on the size?
545 const AccelTree::PreNumber max = maximumPreNumber();
546
547 for(AccelTree::PreNumber i = 0; i <= max; ++i)
548 {
549 if(kind(i) == QXmlNodeModelIndex::Text)
550 {
551 if(isCompressed(i))
552 result += CompressedWhitespace::decompress(data.value(i));
553 else
554 result += data.value(i);
555 }
556 }
557
558 return result;
559 }
560 default:
561 {
562 Q_ASSERT_X(false, Q_FUNC_INFO,
563 "A node type that doesn't exist in the XPath Data Model was encountered.");
564 return QString(); /* Dummy, silence compiler warning. */
565 }
566 }
567}
568
569QVariant AccelTree::typedValue(const QXmlNodeModelIndex &n) const
570{
571 return stringValue(n);
572}
573
574bool AccelTree::hasPrefix(const QVector<QXmlName> &nbs, const QXmlName::PrefixCode prefix)
575{
576 const int size = nbs.size();
577
578 for(int i = 0; i < size; ++i)
579 {
580 if(nbs.at(i).prefix() == prefix)
581 return true;
582 }
583
584 return false;
585}
586
587ItemType::Ptr AccelTree::type(const QXmlNodeModelIndex &ni) const
588{
589 /* kind() is manually inlined here to avoid a virtual call. */
590 return XPathHelper::typeFromKind(basicData.at(toPreNumber(ni)).kind());
591}
592
593Item::Iterator::Ptr AccelTree::sequencedTypedValue(const QXmlNodeModelIndex &n) const
594{
595 const PreNumber preNumber = toPreNumber(n);
596
597 switch(kind(preNumber))
598 {