source: trunk/src/xmlpatterns/schema/qxsdparticlechecker.cpp@ 846

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

trunk: Merged in qt 4.7.2 sources from branches/vendor/nokia/qt.
  • Property svn:eol-style set to native
File size: 26.9 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2008 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 "qxsdparticlechecker_p.h"
43
44#include "qxsdelement_p.h"
45#include "qxsdmodelgroup_p.h"
46#include "qxsdschemahelper_p.h"
47#include "qxsdstatemachine_p.h"
48#include "qxsdstatemachinebuilder_p.h"
49#include "qxsdtypechecker_p.h"
50
51#include <QtCore/QFile>
52
53QT_BEGIN_NAMESPACE
54
55using namespace QPatternist;
56
57namespace QPatternist
58{
59 /**
60 * This template specialization is picked up by XsdStateMachine and allows us
61 * to print nice edge labels.
62 */
63 template <>
64 QString XsdStateMachine<XsdTerm::Ptr>::transitionTypeToString(XsdTerm::Ptr term) const
65 {
66 if (!term)
67 return QLatin1String("(empty)");
68
69 if (term->isElement()) {
70 return XsdElement::Ptr(term)->displayName(m_namePool);
71 } else if (term->isWildcard()) {
72 const XsdWildcard::Ptr wildcard(term);
73 return QLatin1String("(wildcard)");
74 } else {
75 return QString();
76 }
77 }
78}
79
80/**
81 * This method is used by the isUPAConform method to check whether @p term and @p otherTerm
82 * are the same resp. match each other.
83 */
84static bool termMatches(const XsdTerm::Ptr &term, const XsdTerm::Ptr &otherTerm, const NamePool::Ptr &namePool)
85{
86 if (term->isElement()) {
87 const XsdElement::Ptr element(term);
88
89 if (otherTerm->isElement()) {
90 // both, the term and the other term are elements
91
92 const XsdElement::Ptr otherElement(otherTerm);
93
94 // if they have the same name they match
95 if (element->name(namePool) == otherElement->name(namePool))
96 return true;
97
98 } else if (otherTerm->isWildcard()) {
99 // the term is an element and the other term a wildcard
100
101 const XsdWildcard::Ptr wildcard(otherTerm);
102
103 // wildcards using XsdWildcard::absentNamespace, so we have to fix that here
104 QXmlName name = element->name(namePool);
105 if (name.namespaceURI() == StandardNamespaces::empty)
106 name.setNamespaceURI(namePool->allocateNamespace(XsdWildcard::absentNamespace()));
107
108 // if the wildcards namespace constraint allows the elements name, they match
109 if (XsdSchemaHelper::wildcardAllowsExpandedName(name, wildcard, namePool))
110 return true;
111 }
112 } else if (term->isWildcard()) {
113 const XsdWildcard::Ptr wildcard(term);
114
115 if (otherTerm->isElement()) {
116 // the term is a wildcard and the other term an element
117
118 const XsdElement::Ptr otherElement(otherTerm);
119
120 // wildcards using XsdWildcard::absentNamespace, so we have to fix that here
121 QXmlName name = otherElement->name(namePool);
122 if (name.namespaceURI() == StandardNamespaces::empty)
123 name.setNamespaceURI(namePool->allocateNamespace(XsdWildcard::absentNamespace()));
124
125 // if the wildcards namespace constraint allows the elements name, they match
126 if (XsdSchemaHelper::wildcardAllowsExpandedName(name, wildcard, namePool))
127 return true;
128
129 } else if (otherTerm->isWildcard()) {
130 // both, the term and the other term are wildcards
131
132 const XsdWildcard::Ptr otherWildcard(otherTerm);
133
134 // check if the range of the wildcard overlaps.
135 const XsdWildcard::Ptr intersectionWildcard = XsdSchemaHelper::wildcardIntersection(wildcard, otherWildcard);
136 if (!intersectionWildcard ||
137 (intersectionWildcard && !(intersectionWildcard->namespaceConstraint()->variety() != XsdWildcard::NamespaceConstraint::Not && intersectionWildcard->namespaceConstraint()->namespaces().isEmpty())))
138 return true;
139 }
140 }
141
142 return false;
143}
144
145/**
146 * This method is used by the subsumes algorithm to check whether the @p derivedTerm is validly derived from the @p baseTerm.
147 *
148 * @param baseTerm The term of the base component (type or group).
149 * @param derivedTerm The term of the derived component (type or group).
150 * @param particles A hash to map the passed base and derived term to the particles they belong to.
151 * @param context The schema context.
152 * @param errorMsg The error message in the case that an error occurs.
153 */
154static bool derivedTermValid(const XsdTerm::Ptr &baseTerm, const XsdTerm::Ptr &derivedTerm, const QHash<XsdTerm::Ptr, XsdParticle::Ptr> &particles, const XsdSchemaContext::Ptr &context, QString &errorMsg)
155{
156 const NamePool::Ptr namePool(context->namePool());
157
158 // find the particles where the base and derived term belongs to
159 const XsdParticle::Ptr baseParticle = particles.value(baseTerm);
160 const XsdParticle::Ptr derivedParticle = particles.value(derivedTerm);
161
162 // check that an empty particle can not be derived from a non-empty particle
163 if (derivedParticle && baseParticle) {
164 if (XsdSchemaHelper::isParticleEmptiable(derivedParticle) && !XsdSchemaHelper::isParticleEmptiable(baseParticle)) {
165 errorMsg = QtXmlPatterns::tr("Empty particle cannot be derived from non-empty particle.");
166 return false;
167 }
168 }
169
170 if (baseTerm->isElement()) {
171 const XsdElement::Ptr element(baseTerm);
172
173 if (derivedTerm->isElement()) {
174 // if both terms are elements
175
176 const XsdElement::Ptr derivedElement(derivedTerm);
177
178 // check names are equal
179 if (element->name(namePool) != derivedElement->name(namePool)) {
180 errorMsg = QtXmlPatterns::tr("Derived particle is missing element %1.").arg(formatKeyword(element->displayName(namePool)));
181 return false;
182 }
183
184 // check value constraints are equal (if available)
185 if (element->valueConstraint() && element->valueConstraint()->variety() == XsdElement::ValueConstraint::Fixed) {
186 if (!derivedElement->valueConstraint()) {
187 errorMsg = QtXmlPatterns::tr("Derived element %1 is missing value constraint as defined in base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
188 return false;
189 }
190
191 if (derivedElement->valueConstraint()->variety() != XsdElement::ValueConstraint::Fixed) {
192 errorMsg = QtXmlPatterns::tr("Derived element %1 has weaker value constraint than base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
193 return false;
194 }
195
196 const QSourceLocation dummyLocation(QUrl(QLatin1String("http://dummy.org")), 1, 1);
197 const XsdTypeChecker checker(context, QVector<QXmlName>(), dummyLocation);
198 if (!checker.valuesAreEqual(element->valueConstraint()->value(), derivedElement->valueConstraint()->value(), derivedElement->type())) {
199 errorMsg = QtXmlPatterns::tr("Fixed value constraint of element %1 differs from value constraint in base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
200 return false;
201 }
202 }
203
204 // check that a derived element can not be nillable if the base element is not nillable
205 if (!element->isNillable() && derivedElement->isNillable()) {
206 errorMsg = QtXmlPatterns::tr("Derived element %1 cannot be nillable as base element is not nillable.").arg(formatKeyword(derivedElement->displayName(namePool)));
207 return false;
208 }
209
210 // check that the constraints of the derived element are more strict then the constraints of the base element
211 const XsdElement::BlockingConstraints baseConstraints = element->disallowedSubstitutions();
212 const XsdElement::BlockingConstraints derivedConstraints = derivedElement->disallowedSubstitutions();
213 if (((baseConstraints & XsdElement::RestrictionConstraint) && !(derivedConstraints & XsdElement::RestrictionConstraint)) ||
214 ((baseConstraints & XsdElement::ExtensionConstraint) && !(derivedConstraints & XsdElement::ExtensionConstraint)) ||
215 ((baseConstraints & XsdElement::SubstitutionConstraint) && !(derivedConstraints & XsdElement::SubstitutionConstraint))) {
216 errorMsg = QtXmlPatterns::tr("Block constraints of derived element %1 must not be more weaker than in the base element.").arg(formatKeyword(derivedElement->displayName(namePool)));
217 return false;
218 }
219
220 // if the type of both elements is the same we can stop testing here
221 if (element->type()->name(namePool) == derivedElement->type()->name(namePool))
222 return true;
223
224 // check that the type of the derived element can validly derived from the type of the base element
225 if (derivedElement->type()->isSimpleType()) {
226 if (!XsdSchemaHelper::isSimpleDerivationOk(derivedElement->type(), element->type(), SchemaType::DerivationConstraints())) {
227 errorMsg = QtXmlPatterns::tr("Simple type of derived element %1 cannot be validly derived from base element.").arg(formatKeyword(derivedElement->displayName(namePool)));
228 return false;
229 }
230 } else if (derivedElement->type()->isComplexType()) {
231 if (!XsdSchemaHelper::isComplexDerivationOk(derivedElement->type(), element->type(), SchemaType::DerivationConstraints())) {
232 errorMsg = QtXmlPatterns::tr("Complex type of derived element %1 cannot be validly derived from base element.").arg(formatKeyword(derivedElement->displayName(namePool)));
233 return false;
234 }
235 }
236
237 // if both, derived and base element, have a complex type that contains a particle itself, apply the subsumes algorithm
238 // recursive on their particles
239 if (element->type()->isComplexType() && derivedElement->type()->isComplexType()) {
240 if (element->type()->isDefinedBySchema() && derivedElement->type()->isDefinedBySchema()) {
241 const XsdComplexType::Ptr baseType(element->type());
242 const XsdComplexType::Ptr derivedType(derivedElement->type());
243 if ((baseType->contentType()->variety() == XsdComplexType::ContentType::ElementOnly ||
244 baseType->contentType()->variety() == XsdComplexType::ContentType::Mixed) &&
245 (derivedType->contentType()->variety() == XsdComplexType::ContentType::ElementOnly ||
246 derivedType->contentType()->variety() == XsdComplexType::ContentType::Mixed)) {
247
248 return XsdParticleChecker::subsumes(baseType->contentType()->particle(), derivedType->contentType()->particle(), context, errorMsg);
249 }
250 }
251 }
252
253 return true;
254 } else if (derivedTerm->isWildcard()) {
255 // derive a wildcard from an element is not allowed
256 errorMsg = QtXmlPatterns::tr("Element %1 is missing in derived particle.").arg(formatKeyword(element->displayName(namePool)));
257 return false;
258 }
259 } else if (baseTerm->isWildcard()) {
260 const XsdWildcard::Ptr wildcard(baseTerm);
261
262 if (derivedTerm->isElement()) {
263 // the base term is a wildcard and derived term an element
264
265 const XsdElement::Ptr derivedElement(derivedTerm);
266
267 // wildcards using XsdWildcard::absentNamespace, so we have to fix that here
268 QXmlName name = derivedElement->name(namePool);
269 if (name.namespaceURI() == StandardNamespaces::empty)
270 name.setNamespaceURI(namePool->allocateNamespace(XsdWildcard::absentNamespace()));
271
272 // check that name of the element is allowed by the wildcards namespace constraint
273 if (!XsdSchemaHelper::wildcardAllowsExpandedName(name, wildcard, namePool)) {
274 errorMsg = QtXmlPatterns::tr("Element %1 does not match namespace constraint of wildcard in base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
275 return false;
276 }
277
278 } else if (derivedTerm->isWildcard()) {
279 // both, derived and base term are wildcards
280
281 const XsdWildcard::Ptr derivedWildcard(derivedTerm);
282
283 // check that the derived wildcard is a valid subset of the base wildcard
284 if (!XsdSchemaHelper::isWildcardSubset(derivedWildcard, wildcard)) {
285 errorMsg = QtXmlPatterns::tr("Wildcard in derived particle is not a valid subset of wildcard in base particle.");
286 return false;
287 }
288
289 if (!XsdSchemaHelper::checkWildcardProcessContents(wildcard, derivedWildcard)) {
290 errorMsg = QtXmlPatterns::tr("processContent of wildcard in derived particle is weaker than wildcard in base particle.");
291 return false;
292 }
293 }
294
295 return true;
296 }
297
298 return false;
299}
300
301typedef QHash<QXmlName, XsdElement::Ptr> ElementHash;
302
303/**
304 * Internal helper method that checks if the given @p particle contains an element with the
305 * same name and type twice.
306 */
307static bool hasDuplicatedElementsInternal(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool, ElementHash &hash, XsdElement::Ptr &conflictingElement)
308{
309 const XsdTerm::Ptr term = particle->term();
310 if (term->isElement()) {
311 const XsdElement::Ptr mainElement(term);
312 XsdElement::List substGroups = mainElement->substitutionGroups();
313 if (substGroups.isEmpty())
314 substGroups << mainElement;
315
316 for (int i = 0; i < substGroups.count(); ++i) {
317 const XsdElement::Ptr element = substGroups.at(i);
318 if (hash.contains(element->name(namePool))) {
319 if (element->type()->name(namePool) != hash.value(element->name(namePool))->type()->name(namePool)) {
320 conflictingElement = element;
321 return true;
322 }
323 } else {
324 hash.insert(element->name(namePool), element);
325 }
326 }
327 } else if (term->isModelGroup()) {
328 const XsdModelGroup::Ptr group(term);
329 const XsdParticle::List particles = group->particles();
330 for (int i = 0; i < particles.count(); ++i) {
331 if (hasDuplicatedElementsInternal(particles.at(i), namePool, hash, conflictingElement))
332 return true;
333 }
334 }
335
336 return false;
337}
338
339bool XsdParticleChecker::hasDuplicatedElements(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool, XsdElement::Ptr &conflictingElement)
340{
341 ElementHash hash;
342 return hasDuplicatedElementsInternal(particle, namePool, hash, conflictingElement);
343}
344
345bool XsdParticleChecker::isUPAConform(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool)
346{
347
348 /**
349 * In case we encounter an <xsd:all> element, don't construct a state machine, but use the approach
350 * described at http://www.w3.org/TR/xmlschema-1/#non-ambig
351 * Reason: For n elements inside the <xsd:all>, represented in the NDA, the state machine
352 * constructs n! states in the DFA, which does not scale.
353 */
354 if (particle->term()->isModelGroup()) {
355 const XsdModelGroup::Ptr group(particle->term());
356 if (group->compositor() == XsdModelGroup::AllCompositor)
357 return isUPAConformXsdAll(particle, namePool);
358 }
359
360 /**
361 * The algorithm is implemented like described in http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.2
362 */
363
364 // create a state machine for the given particle
365 XsdStateMachine<XsdTerm::Ptr> stateMachine(namePool);
366
367 XsdStateMachineBuilder builder(&stateMachine, namePool);
368 const XsdStateMachine<XsdTerm::Ptr>::StateId endState = builder.reset();
369 const XsdStateMachine<XsdTerm::Ptr>::StateId startState = builder.buildParticle(particle, endState);
370 builder.addStartState(startState);
371
372/*
373 static int counter = 0;
374 {
375 QFile file(QString("/tmp/file_upa%1.dot").arg(counter));
376 file.open(QIODevice::WriteOnly);
377 stateMachine.outputGraph(&file, "Base");
378 file.close();
379 }
380 ::system(QString("dot -Tpng /tmp/file_upa%1.dot -o/tmp/file_upa%1.png").arg(counter).toLatin1().data());
381*/
382 const XsdStateMachine<XsdTerm::Ptr> dfa = stateMachine.toDFA();
383/*
384 {
385 QFile file(QString("/tmp/file_upa%1dfa.dot").arg(counter));
386 file.open(QIODevice::WriteOnly);
387 dfa.outputGraph(&file, "Base");
388 file.close();
389 }
390 ::system(QString("dot -Tpng /tmp/file_upa%1dfa.dot -o/tmp/file_upa%1dfa.png").arg(counter).toLatin1().data());
391*/
392 const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> states = dfa.states();
393 const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > > transitions = dfa.transitions();
394
395 // the basic idea of that algorithm is to iterate over all states of that machine and check that no two edges
396 // that match on the same term leave a state, so for a given term it should always be obvious which edge to take
397 QHashIterator<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> stateIt(states);
398 while (stateIt.hasNext()) { // iterate over all states
399 stateIt.next();
400
401 // fetch all transitions the current state allows
402 const QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > currentTransitions = transitions.value(stateIt.key());
403 QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > transitionIt(currentTransitions);
404 while (transitionIt.hasNext()) { // iterate over all transitions
405 transitionIt.next();
406
407 if (transitionIt.value().size() > 1) {
408 // we have one state with two edges leaving it, that means
409 // the XsdTerm::Ptr exists twice, that is an error
410 return false;
411 }
412
413 QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > innerTransitionIt(currentTransitions);
414 while (innerTransitionIt.hasNext()) { // iterate over all transitions again, as we have to compare all transitions with all
415 innerTransitionIt.next();
416
417 if (transitionIt.key() == innerTransitionIt.key()) // do no compare with ourself
418 continue;
419
420 // use the helper method termMatches to check if both term matches
421 if (termMatches(transitionIt.key(), innerTransitionIt.key(), namePool))
422 return false;
423 }
424 }
425 }
426
427 return true;
428}
429
430bool XsdParticleChecker::isUPAConformXsdAll(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool)
431{
432 /**
433 * see http://www.w3.org/TR/xmlschema-1/#non-ambig
434 */
435 const XsdModelGroup::Ptr group(particle->term());
436 const XsdParticle::List particles = group->particles();
437 const int count = particles.count();
438 for (int left = 0; left < count; ++left) {
439 for (int right = left+1; right < count; ++right) {
440 if (termMatches(particles.at(left)->term(), particles.at(right)->term(), namePool))
441 return false;
442 }
443 }
444 return true;
445}
446
447bool XsdParticleChecker::subsumes(const XsdParticle::Ptr &particle, const XsdParticle::Ptr &derivedParticle, const XsdSchemaContext::Ptr &context, QString &errorMsg)
448{
449 /**
450 * The algorithm is implemented like described in http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.3
451 */
452
453 const NamePool::Ptr namePool(context->namePool());
454
455 XsdStateMachine<XsdTerm::Ptr> baseStateMachine(namePool);
456 XsdStateMachine<XsdTerm::Ptr> derivedStateMachine(namePool);
457
458 // build up state machines for both particles
459 {
460 XsdStateMachineBuilder builder(&baseStateMachine, namePool);
461 const XsdStateMachine<XsdTerm::Ptr>::StateId endState = builder.reset();
462 const XsdStateMachine<XsdTerm::Ptr>::StateId startState = builder.buildParticle(particle, endState);
463 builder.addStartState(startState);
464
465 baseStateMachine = baseStateMachine.toDFA();
466 }
467 {
468 XsdStateMachineBuilder builder(&derivedStateMachine, namePool);
469 const XsdStateMachine<XsdTerm::Ptr>::StateId endState = builder.reset();
470 const XsdStateMachine<XsdTerm::Ptr>::StateId startState = builder.buildParticle(derivedParticle, endState);
471 builder.addStartState(startState);
472
473 derivedStateMachine = derivedStateMachine.toDFA();
474 }
475
476 QHash<XsdTerm::Ptr, XsdParticle::Ptr> particlesHash = XsdStateMachineBuilder::particleLookupMap(particle);
477 particlesHash.unite(XsdStateMachineBuilder::particleLookupMap(derivedParticle));
478
479/*
480 static int counter = 0;
481 {
482 QFile file(QString("/tmp/file_base%1.dot").arg(counter));
483 file.open(QIODevice::WriteOnly);
484 baseStateMachine.outputGraph(&file, QLatin1String("Base"));
485 file.close();
486 }
487 {
488 QFile file(QString("/tmp/file_derived%1.dot").arg(counter));
489 file.open(QIODevice::WriteOnly);
490 derivedStateMachine.outputGraph(&file, QLatin1String("Base"));
491 file.close();
492 }
493 ::system(QString("dot -Tpng /tmp/file_base%1.dot -o/tmp/file_base%1.png").arg(counter).toLatin1().data());
494 ::system(QString("dot -Tpng /tmp/file_derived%1.dot -o/tmp/file_derived%1.png").arg(counter).toLatin1().data());
495*/
496
497 const XsdStateMachine<XsdTerm::Ptr>::StateId baseStartState = baseStateMachine.startState();
498 const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> baseStates = baseStateMachine.states();
499 const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > > baseTransitions = baseStateMachine.transitions();
500
501 const XsdStateMachine<XsdTerm::Ptr>::StateId derivedStartState = derivedStateMachine.startState();
502 const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> derivedStates = derivedStateMachine.states();
503 const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > > derivedTransitions = derivedStateMachine.transitions();
504
505 // @see http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.3.1
506
507 // define working set
508 QList<QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> > workSet;
509 QList<QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> > processedSet;
510
511 // 1) fill working set initially with start states
512 workSet.append(qMakePair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId>(baseStartState, derivedStartState));
513 processedSet.append(qMakePair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId>(baseStartState, derivedStartState));
514
515 while (!workSet.isEmpty()) { // while there are state sets to process
516
517 // 3) dequeue on state set
518 const QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> set = workSet.takeFirst();
519
520 const QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > derivedTrans = derivedTransitions.value(set.second);
521 QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > derivedIt(derivedTrans);
522
523 const QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > baseTrans = baseTransitions.value(set.first);
524
525 while (derivedIt.hasNext()) {
526 derivedIt.next();
527
528 bool found = false;
529 QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > baseIt(baseTrans);
530 while (baseIt.hasNext()) {
531 baseIt.next();
532 if (derivedTermValid(baseIt.key(), derivedIt.key(), particlesHash, context, errorMsg)) {
533 const QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> endSet =
534 qMakePair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId>(baseIt.value().first(), derivedIt.value().first());
535 if (!processedSet.contains(endSet) && !workSet.contains(endSet)) {
536 workSet.append(endSet);
537 processedSet.append(endSet);
538 }
539
540 found = true;
541 }
542 }
543
544 if (!found) {
545 return false;
546 }
547 }
548 }
549
550 // 5)
551 QHashIterator<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> it(derivedStates);
552 while (it.hasNext()) {
553 it.next();
554
555 if (it.value() == XsdStateMachine<XsdTerm::Ptr>::EndState || it.value() == XsdStateMachine<XsdTerm::Ptr>::StartEndState) {
556 for (int i = 0; i < processedSet.count(); ++i) {
557 if (processedSet.at(i).second == it.key() &&
558 (baseStates.value(processedSet.at(i).first) != XsdStateMachine<XsdTerm::Ptr>::EndState &&
559 baseStates.value(processedSet.at(i).first) != XsdStateMachine<XsdTerm::Ptr>::StartEndState)) {
560 errorMsg = QtXmlPatterns::tr("Derived particle allows content that is not allowed in the base particle.");
561 return false;
562 }
563 }
564 }
565 }
566
567 return true;
568}
569
570QT_END_NAMESPACE
Note: See TracBrowser for help on using the repository browser.