QPatternist::XsdParticleChecker Class Reference

A helper class to check validity of particles. More...

#include <qxsdparticlechecker_p.h>

Static Public Functions
static bool	hasDuplicatedElements (const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool, XsdElement::Ptr &conflictingElement)
static bool	isUPAConform (const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool)
static bool	isUPAConformXsdAll (const XsdParticle::Ptr &particle, const NamePool::Ptr &namePool)
static bool	subsumes (const XsdParticle::Ptr &particle, const XsdParticle::Ptr &derivedParticle, const XsdSchemaContext::Ptr &context, QString &errorMsg)

Detailed Description

A helper class to check validity of particles.

Author

Tobias Koenig tobia.nosp@m.s.ko.nosp@m.enig@.nosp@m.noki.nosp@m.a.com

Definition at line 72 of file qxsdparticlechecker_p.h.

Functions

hasDuplicatedElements()

bool XsdParticleChecker::hasDuplicatedElements ( const XsdParticle::Ptr &  particle, const NamePool::Ptr &  namePool, XsdElement::Ptr &  conflictingElement  )

static

Checks whether the given particle has two or more element declarations with the same name but different type definitions.

Definition at line 339 of file qxsdparticlechecker.cpp.

Referenced by QPatternist::XsdSchemaChecker::checkComplexTypeConstraints().

{
    ElementHash hash;
    return hasDuplicatedElementsInternal(particle, namePool, hash, conflictingElement);
}

isUPAConform()

bool XsdParticleChecker::isUPAConform ( const XsdParticle::Ptr &  particle, const NamePool::Ptr &  namePool  )

static

Checks whether the given particle is valid according the UPA (http://www.w3.org/TR/xmlschema-1/#cos-nonambig) constraint.

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.

The algorithm is implemented like described in http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.2

Definition at line 345 of file qxsdparticlechecker.cpp.

Referenced by QPatternist::XsdSchemaChecker::checkComplexTypeConstraints().

{

    if (particle->term()->isModelGroup()) {
        const XsdModelGroup::Ptr group(particle->term());
        if (group->compositor() == XsdModelGroup::AllCompositor)
            return isUPAConformXsdAll(particle, namePool);
    }

    // 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;
}

isUPAConformXsdAll()

bool XsdParticleChecker::isUPAConformXsdAll ( const XsdParticle::Ptr &  particle, const NamePool::Ptr &  namePool  )

static

Checks whether the given particle, which must be an xsd:all element, is valid according the UPA (http://www.w3.org/TR/xmlschema-1/#cos-nonambig) constraint. For xsd:all elements, we do not want to construct a state machine.

see http://www.w3.org/TR/xmlschema-1/#non-ambig

Definition at line 430 of file qxsdparticlechecker.cpp.

Referenced by isUPAConform().

{
    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;
}

subsumes()

bool XsdParticleChecker::subsumes ( const XsdParticle::Ptr &  particle, const XsdParticle::Ptr &  derivedParticle, const XsdSchemaContext::Ptr &  context, QString &  errorMsg  )

static

Checks whether the given particle subsumes the given derivedParticle. (http://www.w3.org/TR/xmlschema-1/#cos-particle-restrict)

The algorithm is implemented like described in http://www.ltg.ed.ac.uk/~ht/XML_Europe_2003.html#S2.3

Definition at line 447 of file qxsdparticlechecker.cpp.

Referenced by QPatternist::XsdSchemaChecker::checkComplexTypeConstraints(), QPatternist::XsdSchemaResolver::checkRedefinedGroups(), and derivedTermValid().

{
    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;
}

---

The documentation for this class was generated from the following files:

• /src/xmlpatterns/schema/qxsdparticlechecker_p.h
• /src/xmlpatterns/schema/qxsdparticlechecker.cpp