/****************************************************************************

**

** 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)

{

    /**

     * 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::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 &&