summaryrefslogtreecommitdiff
path: root/src/xmlpatterns/schema/qxsdparticlechecker.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/xmlpatterns/schema/qxsdparticlechecker.cpp')
-rw-r--r--src/xmlpatterns/schema/qxsdparticlechecker.cpp570
1 files changed, 570 insertions, 0 deletions
diff --git a/src/xmlpatterns/schema/qxsdparticlechecker.cpp b/src/xmlpatterns/schema/qxsdparticlechecker.cpp
new file mode 100644
index 0000000..15c2afe
--- /dev/null
+++ b/src/xmlpatterns/schema/qxsdparticlechecker.cpp
@@ -0,0 +1,570 @@
+/****************************************************************************
+**
+** Copyright (C) 2008 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtXmlPatterns module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights. These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#include "qxsdparticlechecker_p.h"
+
+#include "qxsdelement_p.h"
+#include "qxsdmodelgroup_p.h"
+#include "qxsdschemahelper_p.h"
+#include "qxsdstatemachine_p.h"
+#include "qxsdstatemachinebuilder_p.h"
+#include "qxsdtypechecker_p.h"
+
+#include <QtCore/QFile>
+
+QT_BEGIN_NAMESPACE
+
+using namespace QPatternist;
+
+namespace QPatternist
+{
+ /**
+ * This template specialization is picked up by XsdStateMachine and allows us
+ * to print nice edge labels.
+ */
+ template <>
+ QString XsdStateMachine<XsdTerm::Ptr>::transitionTypeToString(XsdTerm::Ptr term) const
+ {
+ if (!term)
+ return QLatin1String("(empty)");
+
+ if (term->isElement()) {
+ return XsdElement::Ptr(term)->displayName(m_namePool);
+ } else if (term->isWildcard()) {
+ const XsdWildcard::Ptr wildcard(term);
+ return QLatin1String("(wildcard)");
+ } else {
+ return QString();
+ }
+ }
+}
+
+/**
+ * This method is used by the isUPAConform method to check whether @p term and @p otherTerm
+ * are the same resp. match each other.
+ */
+static bool termMatches(const XsdTerm::Ptr &term, const XsdTerm::Ptr &otherTerm, const NamePool::Ptr &namePool)
+{
+ if (term->isElement()) {
+ const XsdElement::Ptr element(term);
+
+ if (otherTerm->isElement()) {
+ // both, the term and the other term are elements
+
+ const XsdElement::Ptr otherElement(otherTerm);
+
+ // if they have the same name they match
+ if (element->name(namePool) == otherElement->name(namePool))
+ return true;
+
+ } else if (otherTerm->isWildcard()) {
+ // the term is an element and the other term a wildcard
+
+ const XsdWildcard::Ptr wildcard(otherTerm);
+
+ // wildcards using XsdWildcard::absentNamespace, so we have to fix that here
+ QXmlName name = element->name(namePool);
+ if (name.namespaceURI() == StandardNamespaces::empty)
+ name.setNamespaceURI(namePool->allocateNamespace(XsdWildcard::absentNamespace()));
+
+ // if the wildcards namespace constraint allows the elements name, they match
+ if (XsdSchemaHelper::wildcardAllowsExpandedName(name, wildcard, namePool))
+ return true;
+ }
+ } else if (term->isWildcard()) {
+ const XsdWildcard::Ptr wildcard(term);
+
+ if (otherTerm->isElement()) {
+ // the term is a wildcard and the other term an element
+
+ const XsdElement::Ptr otherElement(otherTerm);
+
+ // wildcards using XsdWildcard::absentNamespace, so we have to fix that here
+ QXmlName name = otherElement->name(namePool);
+ if (name.namespaceURI() == StandardNamespaces::empty)
+ name.setNamespaceURI(namePool->allocateNamespace(XsdWildcard::absentNamespace()));
+
+ // if the wildcards namespace constraint allows the elements name, they match
+ if (XsdSchemaHelper::wildcardAllowsExpandedName(name, wildcard, namePool))
+ return true;
+
+ } else if (otherTerm->isWildcard()) {
+ // both, the term and the other term are wildcards
+
+ const XsdWildcard::Ptr otherWildcard(otherTerm);
+
+ // check if the range of the wildcard overlaps.
+ const XsdWildcard::Ptr intersectionWildcard = XsdSchemaHelper::wildcardIntersection(wildcard, otherWildcard);
+ if (!intersectionWildcard ||
+ (intersectionWildcard && !(intersectionWildcard->namespaceConstraint()->variety() != XsdWildcard::NamespaceConstraint::Not && intersectionWildcard->namespaceConstraint()->namespaces().isEmpty())))
+ return true;
+ }
+ }
+
+ return false;
+}
+
+/**
+ * This method is used by the subsumes algorithm to check whether the @p derivedTerm is validly derived from the @p baseTerm.
+ *
+ * @param baseTerm The term of the base component (type or group).
+ * @param derivedTerm The term of the derived component (type or group).
+ * @param particles A hash to map the passed base and derived term to the particles they belong to.
+ * @param context The schema context.
+ * @param errorMsg The error message in the case that an error occurs.
+ */
+static bool derivedTermValid(const XsdTerm::Ptr &baseTerm, const XsdTerm::Ptr &derivedTerm, const QHash<XsdTerm::Ptr, XsdParticle::Ptr> &particles, const XsdSchemaContext::Ptr &context, QString &errorMsg)
+{
+ const NamePool::Ptr namePool(context->namePool());
+
+ // find the particles where the base and derived term belongs to
+ const XsdParticle::Ptr baseParticle = particles.value(baseTerm);
+ const XsdParticle::Ptr derivedParticle = particles.value(derivedTerm);
+
+ // check that an empty particle can not be derived from a non-empty particle
+ if (derivedParticle && baseParticle) {
+ if (XsdSchemaHelper::isParticleEmptiable(derivedParticle) && !XsdSchemaHelper::isParticleEmptiable(baseParticle)) {
+ errorMsg = QtXmlPatterns::tr("Empty particle cannot be derived from non-empty particle.");
+ return false;
+ }
+ }
+
+ if (baseTerm->isElement()) {
+ const XsdElement::Ptr element(baseTerm);
+
+ if (derivedTerm->isElement()) {
+ // if both terms are elements
+
+ const XsdElement::Ptr derivedElement(derivedTerm);
+
+ // check names are equal
+ if (element->name(namePool) != derivedElement->name(namePool)) {
+ errorMsg = QtXmlPatterns::tr("Derived particle is missing element %1.").arg(formatKeyword(element->displayName(namePool)));
+ return false;
+ }
+
+ // check value constraints are equal (if available)
+ if (element->valueConstraint() && element->valueConstraint()->variety() == XsdElement::ValueConstraint::Fixed) {
+ if (!derivedElement->valueConstraint()) {
+ errorMsg = QtXmlPatterns::tr("Derived element %1 is missing value constraint as defined in base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+
+ if (derivedElement->valueConstraint()->variety() != XsdElement::ValueConstraint::Fixed) {
+ errorMsg = QtXmlPatterns::tr("Derived element %1 has weaker value constraint than base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+
+ const QSourceLocation dummyLocation(QUrl(QLatin1String("http://dummy.org")), 1, 1);
+ const XsdTypeChecker checker(context, QVector<QXmlName>(), dummyLocation);
+ if (!checker.valuesAreEqual(element->valueConstraint()->value(), derivedElement->valueConstraint()->value(), derivedElement->type())) {
+ errorMsg = QtXmlPatterns::tr("Fixed value constraint of element %1 differs from value constraint in base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+ }
+
+ // check that a derived element can not be nillable if the base element is not nillable
+ if (!element->isNillable() && derivedElement->isNillable()) {
+ errorMsg = QtXmlPatterns::tr("Derived element %1 cannot be nillable as base element is not nillable.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+
+ // check that the constraints of the derived element are more strict then the constraints of the base element
+ const XsdElement::BlockingConstraints baseConstraints = element->disallowedSubstitutions();
+ const XsdElement::BlockingConstraints derivedConstraints = derivedElement->disallowedSubstitutions();
+ if (((baseConstraints & XsdElement::RestrictionConstraint) && !(derivedConstraints & XsdElement::RestrictionConstraint)) ||
+ ((baseConstraints & XsdElement::ExtensionConstraint) && !(derivedConstraints & XsdElement::ExtensionConstraint)) ||
+ ((baseConstraints & XsdElement::SubstitutionConstraint) && !(derivedConstraints & XsdElement::SubstitutionConstraint))) {
+ errorMsg = QtXmlPatterns::tr("Block constraints of derived element %1 must not be more weaker than in the base element.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+
+ // if the type of both elements is the same we can stop testing here
+ if (element->type()->name(namePool) == derivedElement->type()->name(namePool))
+ return true;
+
+ // check that the type of the derived element can validly derived from the type of the base element
+ if (derivedElement->type()->isSimpleType()) {
+ if (!XsdSchemaHelper::isSimpleDerivationOk(derivedElement->type(), element->type(), SchemaType::DerivationConstraints())) {
+ errorMsg = QtXmlPatterns::tr("Simple type of derived element %1 cannot be validly derived from base element.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+ } else if (derivedElement->type()->isComplexType()) {
+ if (!XsdSchemaHelper::isComplexDerivationOk(derivedElement->type(), element->type(), SchemaType::DerivationConstraints())) {
+ errorMsg = QtXmlPatterns::tr("Complex type of derived element %1 cannot be validly derived from base element.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+ }
+
+ // if both, derived and base element, have a complex type that contains a particle itself, apply the subsumes algorithm
+ // recursive on their particles
+ if (element->type()->isComplexType() && derivedElement->type()->isComplexType()) {
+ if (element->type()->isDefinedBySchema() && derivedElement->type()->isDefinedBySchema()) {
+ const XsdComplexType::Ptr baseType(element->type());
+ const XsdComplexType::Ptr derivedType(derivedElement->type());
+ if ((baseType->contentType()->variety() == XsdComplexType::ContentType::ElementOnly ||
+ baseType->contentType()->variety() == XsdComplexType::ContentType::Mixed) &&
+ (derivedType->contentType()->variety() == XsdComplexType::ContentType::ElementOnly ||
+ derivedType->contentType()->variety() == XsdComplexType::ContentType::Mixed)) {
+
+ return XsdParticleChecker::subsumes(baseType->contentType()->particle(), derivedType->contentType()->particle(), context, errorMsg);
+ }
+ }
+ }
+
+ return true;
+ } else if (derivedTerm->isWildcard()) {
+ // derive a wildcard from an element is not allowed
+ errorMsg = QtXmlPatterns::tr("Element %1 is missing in derived particle.").arg(formatKeyword(element->displayName(namePool)));
+ return false;
+ }
+ } else if (baseTerm->isWildcard()) {
+ const XsdWildcard::Ptr wildcard(baseTerm);
+
+ if (derivedTerm->isElement()) {
+ // the base term is a wildcard and derived term an element
+
+ const XsdElement::Ptr derivedElement(derivedTerm);
+
+ // wildcards using XsdWildcard::absentNamespace, so we have to fix that here
+ QXmlName name = derivedElement->name(namePool);
+ if (name.namespaceURI() == StandardNamespaces::empty)
+ name.setNamespaceURI(namePool->allocateNamespace(XsdWildcard::absentNamespace()));
+
+ // check that name of the element is allowed by the wildcards namespace constraint
+ if (!XsdSchemaHelper::wildcardAllowsExpandedName(name, wildcard, namePool)) {
+ errorMsg = QtXmlPatterns::tr("Element %1 does not match namespace constraint of wildcard in base particle.").arg(formatKeyword(derivedElement->displayName(namePool)));
+ return false;
+ }
+
+ } else if (derivedTerm->isWildcard()) {
+ // both, derived and base term are wildcards
+
+ const XsdWildcard::Ptr derivedWildcard(derivedTerm);
+
+ // check that the derived wildcard is a valid subset of the base wildcard
+ if (!XsdSchemaHelper::isWildcardSubset(derivedWildcard, wildcard)) {
+ errorMsg = QtXmlPatterns::tr("Wildcard in derived particle is not a valid subset of wildcard in base particle.");
+ return false;
+ }
+
+ if (!XsdSchemaHelper::checkWildcardProcessContents(wildcard, derivedWildcard)) {
+ errorMsg = QtXmlPatterns::tr("processContent of wildcard in derived particle is weaker than wildcard in base particle.");
+ return false;
+ }
+ }
+
+ return true;
+ }
+
+ return false;
+}
+
+typedef QHash<QXmlName, XsdElement::Ptr> ElementHash;
+
+/**
+ * Internal helper method that checks if the given @p particle contains an element with the
+ * same name and type twice.
+ */
+static bool hasDuplicatedElementsInternal(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool, ElementHash &hash, XsdElement::Ptr &conflictingElement)
+{
+ const XsdTerm::Ptr term = particle->term();
+ if (term->isElement()) {
+ const XsdElement::Ptr mainElement(term);
+ XsdElement::List substGroups = mainElement->substitutionGroups();
+ if (substGroups.isEmpty())
+ substGroups << mainElement;
+
+ for (int i = 0; i < substGroups.count(); ++i) {
+ const XsdElement::Ptr element = substGroups.at(i);
+ if (hash.contains(element->name(namePool))) {
+ if (element->type()->name(namePool) != hash.value(element->name(namePool))->type()->name(namePool)) {
+ conflictingElement = element;
+ return true;
+ }
+ } else {
+ hash.insert(element->name(namePool), element);
+ }
+ }
+ } else if (term->isModelGroup()) {
+ const XsdModelGroup::Ptr group(term);
+ const XsdParticle::List particles = group->particles();
+ for (int i = 0; i < particles.count(); ++i) {
+ if (hasDuplicatedElementsInternal(particles.at(i), namePool, hash, conflictingElement))
+ return true;
+ }
+ }
+
+ return false;
+}
+
+bool XsdParticleChecker::hasDuplicatedElements(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool, XsdElement::Ptr &conflictingElement)
+{
+ ElementHash hash;
+ return hasDuplicatedElementsInternal(particle, namePool, hash, conflictingElement);
+}
+
+bool XsdParticleChecker::isUPAConform(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool)
+{
+
+ /**
+ * In case we encounter an <xsd:all> element, don't construct a state machine, but use the approach
+ * described at http://www.w3.org/TR/xmlschema-1/#non-ambig
+ * Reason: For n elements inside the <xsd:all>, represented in the NDA, the state machine
+ * constructs n! states in the DFA, which does not scale.
+ */
+ if (particle->term()->isModelGroup()) {
+ const XsdModelGroup::Ptr group(particle->term());
+ if (group->compositor() == XsdModelGroup::AllCompositor)
+ return isUPAConformXsdAll(particle, namePool);
+ }
+
+ /**
+ * The algorithm is implemented like described in http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.2
+ */
+
+ // create a state machine for the given particle
+ XsdStateMachine<XsdTerm::Ptr> stateMachine(namePool);
+
+ XsdStateMachineBuilder builder(&stateMachine, namePool);
+ const XsdStateMachine<XsdTerm::Ptr>::StateId endState = builder.reset();
+ const XsdStateMachine<XsdTerm::Ptr>::StateId startState = builder.buildParticle(particle, endState);
+ builder.addStartState(startState);
+
+/*
+ static int counter = 0;
+ {
+ QFile file(QString("/tmp/file_upa%1.dot").arg(counter));
+ file.open(QIODevice::WriteOnly);
+ stateMachine.outputGraph(&file, "Base");
+ file.close();
+ }
+ ::system(QString("dot -Tpng /tmp/file_upa%1.dot -o/tmp/file_upa%1.png").arg(counter).toLatin1().data());
+*/
+ const XsdStateMachine<XsdTerm::Ptr> dfa = stateMachine.toDFA();
+/*
+ {
+ QFile file(QString("/tmp/file_upa%1dfa.dot").arg(counter));
+ file.open(QIODevice::WriteOnly);
+ dfa.outputGraph(&file, "Base");
+ file.close();
+ }
+ ::system(QString("dot -Tpng /tmp/file_upa%1dfa.dot -o/tmp/file_upa%1dfa.png").arg(counter).toLatin1().data());
+*/
+ const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> states = dfa.states();
+ const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > > transitions = dfa.transitions();
+
+ // the basic idea of that algorithm is to iterate over all states of that machine and check that no two edges
+ // that match on the same term leave a state, so for a given term it should always be obvious which edge to take
+ QHashIterator<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> stateIt(states);
+ while (stateIt.hasNext()) { // iterate over all states
+ stateIt.next();
+
+ // fetch all transitions the current state allows
+ const QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > currentTransitions = transitions.value(stateIt.key());
+ QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > transitionIt(currentTransitions);
+ while (transitionIt.hasNext()) { // iterate over all transitions
+ transitionIt.next();
+
+ if (transitionIt.value().size() > 1) {
+ // we have one state with two edges leaving it, that means
+ // the XsdTerm::Ptr exists twice, that is an error
+ return false;
+ }
+
+ QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > innerTransitionIt(currentTransitions);
+ while (innerTransitionIt.hasNext()) { // iterate over all transitions again, as we have to compare all transitions with all
+ innerTransitionIt.next();
+
+ if (transitionIt.key() == innerTransitionIt.key()) // do no compare with ourself
+ continue;
+
+ // use the helper method termMatches to check if both term matches
+ if (termMatches(transitionIt.key(), innerTransitionIt.key(), namePool))
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+bool XsdParticleChecker::isUPAConformXsdAll(const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool)
+{
+ /**
+ * see http://www.w3.org/TR/xmlschema-1/#non-ambig
+ */
+ const XsdModelGroup::Ptr group(particle->term());
+ const XsdParticle::List particles = group->particles();
+ const int count = particles.count();
+ for (int left = 0; left < count; ++left) {
+ for (int right = left+1; right < count; ++right) {
+ if (termMatches(particles.at(left)->term(), particles.at(right)->term(), namePool))
+ return false;
+ }
+ }
+ return true;
+}
+
+bool XsdParticleChecker::subsumes(const XsdParticle::Ptr &particle, const XsdParticle::Ptr &derivedParticle, const XsdSchemaContext::Ptr &context, QString &errorMsg)
+{
+ /**
+ * The algorithm is implemented like described in http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.3
+ */
+
+ const NamePool::Ptr namePool(context->namePool());
+
+ XsdStateMachine<XsdTerm::Ptr> baseStateMachine(namePool);
+ XsdStateMachine<XsdTerm::Ptr> derivedStateMachine(namePool);
+
+ // build up state machines for both particles
+ {
+ XsdStateMachineBuilder builder(&baseStateMachine, namePool);
+ const XsdStateMachine<XsdTerm::Ptr>::StateId endState = builder.reset();
+ const XsdStateMachine<XsdTerm::Ptr>::StateId startState = builder.buildParticle(particle, endState);
+ builder.addStartState(startState);
+
+ baseStateMachine = baseStateMachine.toDFA();
+ }
+ {
+ XsdStateMachineBuilder builder(&derivedStateMachine, namePool);
+ const XsdStateMachine<XsdTerm::Ptr>::StateId endState = builder.reset();
+ const XsdStateMachine<XsdTerm::Ptr>::StateId startState = builder.buildParticle(derivedParticle, endState);
+ builder.addStartState(startState);
+
+ derivedStateMachine = derivedStateMachine.toDFA();
+ }
+
+ QHash<XsdTerm::Ptr, XsdParticle::Ptr> particlesHash = XsdStateMachineBuilder::particleLookupMap(particle);
+ particlesHash.unite(XsdStateMachineBuilder::particleLookupMap(derivedParticle));
+
+/*
+ static int counter = 0;
+ {
+ QFile file(QString("/tmp/file_base%1.dot").arg(counter));
+ file.open(QIODevice::WriteOnly);
+ baseStateMachine.outputGraph(&file, QLatin1String("Base"));
+ file.close();
+ }
+ {
+ QFile file(QString("/tmp/file_derived%1.dot").arg(counter));
+ file.open(QIODevice::WriteOnly);
+ derivedStateMachine.outputGraph(&file, QLatin1String("Base"));
+ file.close();
+ }
+ ::system(QString("dot -Tpng /tmp/file_base%1.dot -o/tmp/file_base%1.png").arg(counter).toLatin1().data());
+ ::system(QString("dot -Tpng /tmp/file_derived%1.dot -o/tmp/file_derived%1.png").arg(counter).toLatin1().data());
+*/
+
+ const XsdStateMachine<XsdTerm::Ptr>::StateId baseStartState = baseStateMachine.startState();
+ const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> baseStates = baseStateMachine.states();
+ const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > > baseTransitions = baseStateMachine.transitions();
+
+ const XsdStateMachine<XsdTerm::Ptr>::StateId derivedStartState = derivedStateMachine.startState();
+ const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> derivedStates = derivedStateMachine.states();
+ const QHash<XsdStateMachine<XsdTerm::Ptr>::StateId, QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > > derivedTransitions = derivedStateMachine.transitions();
+
+ // @see http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.3.1
+
+ // define working set
+ QList<QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> > workSet;
+ QList<QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> > processedSet;
+
+ // 1) fill working set initially with start states
+ workSet.append(qMakePair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId>(baseStartState, derivedStartState));
+ processedSet.append(qMakePair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId>(baseStartState, derivedStartState));
+
+ while (!workSet.isEmpty()) { // while there are state sets to process
+
+ // 3) dequeue on state set
+ const QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> set = workSet.takeFirst();
+
+ const QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > derivedTrans = derivedTransitions.value(set.second);
+ QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > derivedIt(derivedTrans);
+
+ const QHash<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > baseTrans = baseTransitions.value(set.first);
+
+ while (derivedIt.hasNext()) {
+ derivedIt.next();
+
+ bool found = false;
+ QHashIterator<XsdTerm::Ptr, QVector<XsdStateMachine<XsdTerm::Ptr>::StateId> > baseIt(baseTrans);
+ while (baseIt.hasNext()) {
+ baseIt.next();
+ if (derivedTermValid(baseIt.key(), derivedIt.key(), particlesHash, context, errorMsg)) {
+ const QPair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId> endSet =
+ qMakePair<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateId>(baseIt.value().first(), derivedIt.value().first());
+ if (!processedSet.contains(endSet) && !workSet.contains(endSet)) {
+ workSet.append(endSet);
+ processedSet.append(endSet);
+ }
+
+ found = true;
+ }
+ }
+
+ if (!found) {
+ return false;
+ }
+ }
+ }
+
+ // 5)
+ QHashIterator<XsdStateMachine<XsdTerm::Ptr>::StateId, XsdStateMachine<XsdTerm::Ptr>::StateType> it(derivedStates);
+ while (it.hasNext()) {
+ it.next();
+
+ if (it.value() == XsdStateMachine<XsdTerm::Ptr>::EndState || it.value() == XsdStateMachine<XsdTerm::Ptr>::StartEndState) {
+ for (int i = 0; i < processedSet.count(); ++i) {
+ if (processedSet.at(i).second == it.key() &&
+ (baseStates.value(processedSet.at(i).first) != XsdStateMachine<XsdTerm::Ptr>::EndState &&
+ baseStates.value(processedSet.at(i).first) != XsdStateMachine<XsdTerm::Ptr>::StartEndState)) {
+ errorMsg = QtXmlPatterns::tr("Derived particle allows content that is not allowed in the base particle.");
+ return false;
+ }
+ }
+ }
+ }
+
+ return true;
+}
+
+QT_END_NAMESPACE