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

source code of qtxmlpatterns/src/xmlpatterns/schema/qxsdparticlechecker.cpp