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 | |
51 | QT_BEGIN_NAMESPACE |
52 | |
53 | using namespace QPatternist; |
54 | |
55 | namespace 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 | */ |
82 | static 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 | */ |
152 | static 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 | |
299 | typedef 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 | */ |
305 | static 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 | |
337 | bool 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 | |
343 | bool 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 | |
420 | bool 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 | |
437 | bool 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 | |
553 | QT_END_NAMESPACE |
554 | |