Initial import from the monolithic Qt.

This is the beginning of revision history for this module. If you
want to look at revision history older than this, please refer to the
Qt Git wiki for how to use Git history grafting. At the time of
writing, this wiki is located here:

http://qt.gitorious.org/qt/pages/GitIntroductionWithQt

If you have already performed the grafting and you don't see any
history beyond this commit, try running "git log" with the "--follow"
argument.

Branched from the monolithic repo, Qt master branch, at commit
896db169ea224deb96c59ce8af800d019de63f12

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