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

**

** 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 "qxsdschemahelper_p.h"

#include "qbuiltintypes_p.h"

#include "qvaluefactory_p.h"

#include "qxsdcomplextype_p.h"

#include "qxsdmodelgroup_p.h"

#include "qxsdsimpletype_p.h"

#include "qxsdtypechecker_p.h"

QT_BEGIN_NAMESPACE

using namespace QPatternist;

/*

 * Calculates the effective total range minimum of the given @p particle as

 * described by the algorithm in the schema spec.

 */

static inline unsigned int effectiveTotalRangeMinimum(const XsdParticle::Ptr &particle)

{

    const XsdModelGroup::Ptr group = particle->term();

    if (group->compositor() == XsdModelGroup::ChoiceCompositor) {

        // @see http://www.w3.org/TR/xmlschema11-1/# cos-choice-range

        int minValue = -1;

        const XsdParticle::List particles = group->particles();

        if (particles.isEmpty())

            minValue = 0;

        for (int i = 0; i < particles.count(); ++i) {

            const XsdParticle::Ptr particle = particles.at(i);

            if (particle->term()->isElement() || particle->term()->isWildcard()) {

                if (minValue == -1) {

                    minValue = particle->minimumOccurs();

                } else {

                    minValue = qMin((unsigned int)minValue, particle->minimumOccurs());

                }

            } else if (particle->term()->isModelGroup()) {

                if (minValue == -1) {

                    minValue = effectiveTotalRangeMinimum(particle);

                } else {

                    minValue = qMin((unsigned int)minValue, effectiveTotalRangeMinimum(particle));

                }

            }

        }

        return (particle->minimumOccurs() * minValue);

    } else {

        // @see http://www.w3.org/TR/xmlschema11-1/# cos-seq-range

        unsigned int sum = 0;

        const XsdParticle::List particles = group->particles();

        for (int i = 0; i < particles.count(); ++i) {

            const XsdParticle::Ptr particle = particles.at(i);

            if (particle->term()->isElement() || particle->term()->isWildcard())

                sum += particle->minimumOccurs();

            else if (particle->term()->isModelGroup())

                sum += effectiveTotalRangeMinimum(particle);

        }

        return (particle->minimumOccurs() * sum);

    }

}

bool XsdSchemaHelper::isParticleEmptiable(const XsdParticle::Ptr &particle)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cos-group-emptiable

    if (particle->minimumOccurs() == 0)

        return true;

    if (!(particle->term()->isModelGroup()))

        return false;

    return (effectiveTotalRangeMinimum(particle) == 0);

}

bool XsdSchemaHelper::wildcardAllowsNamespaceName(const QString &nameSpace, const XsdWildcard::NamespaceConstraint::Ptr &constraint)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cvc-wildcard-namespace

    // 1

    if (constraint->variety() == XsdWildcard::NamespaceConstraint::Any)

        return true;

    // 2

    if (constraint->variety() == XsdWildcard::NamespaceConstraint::Not) { // 2.1

        if (!constraint->namespaces().contains(nameSpace)) // 2.2

            if (nameSpace != XsdWildcard::absentNamespace()) // 2.3

                return true;

    }

    // 3

    if (constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration) {

        if (constraint->namespaces().contains(nameSpace))

            return true;

    }

    return false;

}

bool XsdSchemaHelper::wildcardAllowsExpandedName(const QXmlName &name, const XsdWildcard::Ptr &wildcard, const NamePool::Ptr &namePool)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cvc-wildcard-name

    // 1

    if (!wildcardAllowsNamespaceName(namePool->stringForNamespace(name.namespaceURI()), wildcard->namespaceConstraint()))

        return false;

    // 2, 3, 4

    //TODO: we have no disallowed namespace yet

    return true;

}

// small helper function that should be available in Qt 4.6

template<class T>

static inline bool containsSet(const QSet<T> &super, const QSet<T> &sub)

{

    QSetIterator<T> it(sub);

    while (it.hasNext()) {

        if (!super.contains(it.next()))

            return false;

    }

    return true;

}

bool XsdSchemaHelper::isWildcardSubset(const XsdWildcard::Ptr &wildcard, const XsdWildcard::Ptr &otherWildcard)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cos-ns-subset

    // wildcard =^ sub

    // otherWildcard =^ super

    const XsdWildcard::NamespaceConstraint::Ptr constraint(wildcard->namespaceConstraint());

    const XsdWildcard::NamespaceConstraint::Ptr otherConstraint(otherWildcard->namespaceConstraint());

    // 1

    if (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Any)

        return true;

    // 2

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration) && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        if (containsSet<QString>(otherConstraint->namespaces(), constraint->namespaces()))

            return true;

    }

    // 3

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration) && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not)) {

        if (constraint->namespaces().intersect(otherConstraint->namespaces()).isEmpty())

            return true;

    }

    // 4

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Not) && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not)) {

        if (containsSet<QString>(constraint->namespaces(), otherConstraint->namespaces()))

            return true;

    }

    return false;

}

XsdWildcard::Ptr XsdSchemaHelper::wildcardUnion(const XsdWildcard::Ptr &wildcard, const XsdWildcard::Ptr &otherWildcard)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cos-aw-union

    XsdWildcard::Ptr unionWildcard(new XsdWildcard());

    const XsdWildcard::NamespaceConstraint::Ptr constraint(wildcard->namespaceConstraint());

    const XsdWildcard::NamespaceConstraint::Ptr otherConstraint(otherWildcard->namespaceConstraint());

    // 1

    if ((constraint->variety() == otherConstraint->variety()) &&

        (constraint->namespaces() == otherConstraint->namespaces())) {

        unionWildcard->namespaceConstraint()->setVariety(constraint->variety());

        unionWildcard->namespaceConstraint()->setNamespaces(constraint->namespaces());

        return unionWildcard;

    }

    // 2

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Any) || (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Any)) {

        unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Any);

        return unionWildcard;

    }

    // 3

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration) && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Enumeration);

        unionWildcard->namespaceConstraint()->setNamespaces(constraint->namespaces() + otherConstraint->namespaces());

        return unionWildcard;

    }

    // 4

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Not) && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not)) {

        if (constraint->namespaces() != otherConstraint->namespaces()) {

            unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Not);

            unionWildcard->namespaceConstraint()->setNamespaces(QSet<QString>() << XsdWildcard::absentNamespace());

            return unionWildcard;

        }

    }

    // 5

    QSet<QString> sSet, negatedSet;

    bool matches5 = false;

    if (((constraint->variety() == XsdWildcard::NamespaceConstraint::Not) && !constraint->namespaces().contains(XsdWildcard::absentNamespace()))

        && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        negatedSet = constraint->namespaces();

        sSet = otherConstraint->namespaces();

        matches5 = true;

    } else if (((otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not) && !otherConstraint->namespaces().contains(XsdWildcard::absentNamespace()))

        && (constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        negatedSet = otherConstraint->namespaces();

        sSet = constraint->namespaces();

        matches5 = true;

    }

    if (matches5) {

        if (sSet.contains(negatedSet.values().first()) && sSet.contains(XsdWildcard::absentNamespace())) { // 5.1

            unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Any);

            return unionWildcard;

        }

        if (sSet.contains(negatedSet.values().first()) && !sSet.contains(XsdWildcard::absentNamespace())) { // 5.2

            unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Not);

            unionWildcard->namespaceConstraint()->setNamespaces(QSet<QString>() << XsdWildcard::absentNamespace());

            return unionWildcard;

        }

        if (!sSet.contains(negatedSet.values().first()) && sSet.contains(XsdWildcard::absentNamespace())) { // 5.3

            return XsdWildcard::Ptr(); // not expressible

        }

        if (!sSet.contains(negatedSet.values().first()) && !sSet.contains(XsdWildcard::absentNamespace())) { // 5.4

            unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Not);

            unionWildcard->namespaceConstraint()->setNamespaces(negatedSet);

            return unionWildcard;

        }

    }

    // 6

    bool matches6 = false;

    if (((constraint->variety() == XsdWildcard::NamespaceConstraint::Not) && constraint->namespaces().contains(XsdWildcard::absentNamespace()))

        && (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        negatedSet = constraint->namespaces();

        sSet = otherConstraint->namespaces();

        matches6 = true;

    } else if (((otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not) && otherConstraint->namespaces().contains(XsdWildcard::absentNamespace()))

        && (constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        negatedSet = otherConstraint->namespaces();

        sSet = constraint->namespaces();

        matches6 = true;

    }

    if (matches6) {

        if (sSet.contains(XsdWildcard::absentNamespace())) { // 6.1

            unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Any);

            return unionWildcard;

        }

        if (!sSet.contains(XsdWildcard::absentNamespace())) { // 6.2

            unionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Not);

            unionWildcard->namespaceConstraint()->setNamespaces(QSet<QString>() += XsdWildcard::absentNamespace());

            return unionWildcard;

        }

    }

    return XsdWildcard::Ptr();

}

XsdWildcard::Ptr XsdSchemaHelper::wildcardIntersection(const XsdWildcard::Ptr &wildcard, const XsdWildcard::Ptr &otherWildcard)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cos-aw-intersect

    const XsdWildcard::NamespaceConstraint::Ptr constraint(wildcard->namespaceConstraint());

    const XsdWildcard::NamespaceConstraint::Ptr otherConstraint(otherWildcard->namespaceConstraint());

    const XsdWildcard::Ptr intersectionWildcard(new XsdWildcard());

    // 1

    if ((constraint->variety() == otherConstraint->variety()) &&

        (constraint->namespaces() == otherConstraint->namespaces())) {

        intersectionWildcard->namespaceConstraint()->setVariety(constraint->variety());

        intersectionWildcard->namespaceConstraint()->setNamespaces(constraint->namespaces());

        return intersectionWildcard;

    }

    // 2

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Any) &&

        (otherConstraint->variety() != XsdWildcard::NamespaceConstraint::Any)) {

        intersectionWildcard->namespaceConstraint()->setVariety(otherConstraint->variety());

        intersectionWildcard->namespaceConstraint()->setNamespaces(otherConstraint->namespaces());

        return intersectionWildcard;

    }

    // 2

    if ((constraint->variety() != XsdWildcard::NamespaceConstraint::Any) &&

        (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Any)) {

        intersectionWildcard->namespaceConstraint()->setVariety(constraint->variety());

        intersectionWildcard->namespaceConstraint()->setNamespaces(constraint->namespaces());

        return intersectionWildcard;

    }

    // 3

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Not) &&

        (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        QSet<QString> set = otherConstraint->namespaces();

        set.subtract(constraint->namespaces());

        set.remove(XsdWildcard::absentNamespace());

        intersectionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Enumeration);

        intersectionWildcard->namespaceConstraint()->setNamespaces(set);

        return intersectionWildcard;

    }

    // 3

    if ((otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not) &&

        (constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        QSet<QString> set = constraint->namespaces();

        set.subtract(otherConstraint->namespaces());

        set.remove(XsdWildcard::absentNamespace());

        intersectionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Enumeration);

        intersectionWildcard->namespaceConstraint()->setNamespaces(set);

        return intersectionWildcard;

    }

    // 4

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration) &&

        (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Enumeration)) {

        QSet<QString> set = constraint->namespaces();

        set.intersect(otherConstraint->namespaces());

        intersectionWildcard->namespaceConstraint()->setVariety(XsdWildcard::NamespaceConstraint::Enumeration);

        intersectionWildcard->namespaceConstraint()->setNamespaces(set);

        return intersectionWildcard;

    }

    // 6

    if ((constraint->variety() == XsdWildcard::NamespaceConstraint::Not) &&

        (otherConstraint->variety() == XsdWildcard::NamespaceConstraint::Not)) {

        if (!(constraint->namespaces().contains(XsdWildcard::absentNamespace())) && otherConstraint->namespaces().contains(XsdWildcard::absentNamespace())) {

            return wildcard;

        }

        if (constraint->namespaces().contains(XsdWildcard::absentNamespace()) && !(otherConstraint->namespaces().contains(XsdWildcard::absentNamespace()))) {

            return otherWildcard;

        }

    }

    // 5 as not expressible return empty wildcard

    return XsdWildcard::Ptr();

}

static SchemaType::DerivationConstraints convertBlockingConstraints(const NamedSchemaComponent::BlockingConstraints &constraints)

{

    SchemaType::DerivationConstraints result = 0;

    if (constraints & NamedSchemaComponent::RestrictionConstraint)

        result |= SchemaType::RestrictionConstraint;

    if (constraints & NamedSchemaComponent::ExtensionConstraint)

        result |= SchemaType::ExtensionConstraint;

    return result;

}

bool XsdSchemaHelper::isValidlySubstitutable(const SchemaType::Ptr &type, const SchemaType::Ptr &otherType, const SchemaType::DerivationConstraints &constraints)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#key-val-sub-type

    // 1

    if (type->isComplexType() && otherType->isComplexType()) {

        SchemaType::DerivationConstraints keywords = constraints;

        if (otherType->isDefinedBySchema())

            keywords |= convertBlockingConstraints(XsdComplexType::Ptr(otherType)->prohibitedSubstitutions());

        return isComplexDerivationOk(type, otherType, keywords);

    }

    // 2

    if (type->isComplexType() && otherType->isSimpleType()) {

        return isComplexDerivationOk(type, otherType, constraints);

    }

    // 3

    if (type->isSimpleType() && otherType->isSimpleType()) {

        return isSimpleDerivationOk(type, otherType, constraints);

    }

    return false;

}

bool XsdSchemaHelper::isSimpleDerivationOk(const SchemaType::Ptr &derivedType, const SchemaType::Ptr &baseType, const SchemaType::DerivationConstraints &constraints)

{

    // @see http://www.w3.org/TR/xmlschema11-1/#cos-st-derived-ok

    // 1

    if (derivedType == baseType)

        return true;

    // 2.1

    if ((constraints & SchemaType::RestrictionConstraint) || derivedType->wxsSuperType()->derivationConstraints() & SchemaType::RestrictionConstraint) {

        return false;

    }

    // 2.2.1

    if (derivedType->wxsSuperType() == baseType)

        return true;

    // 2.2.2

    if (derivedType->wxsSuperType() != BuiltinTypes::xsAnyType) {

        if (isSimpleDerivationOk(derivedType->wxsSuperType(), baseType, constraints))

            return true;

    }

    // 2.2.3

    if (derivedType->category() == SchemaType::SimpleTypeList || derivedType->category() == SchemaType::SimpleTypeUnion) {

        if (baseType == BuiltinTypes::xsAnySimpleType)

            return true;

    }

    // 2.2.4

    if (baseType->category() == SchemaType::SimpleTypeUnion && baseType->isDefinedBySchema()) { // 2.2.4.1

        const AnySimpleType::List memberTypes = XsdSimpleType::Ptr(baseType)->memberTypes();

        for (int i = 0; i < memberTypes.count(); ++i) {

            if (isSimpleDerivationOk(derivedType, memberTypes.at(i), constraints)) { // 2.2.4.2

                if (XsdSimpleType::Ptr(baseType)->facets().isEmpty()) { // 2.2.4.3

                    return true;

                }

            }

        }

    }

    return false;

}

bool XsdSchemaHelper::isComplexDerivationOk(const SchemaType::Ptr &derivedType, const SchemaType::Ptr &baseType, const SchemaType::DerivationConstraints &constraints)

{

    if (!derivedType)

        return false;

    // @see http://www.w3.org/TR/xmlschema11-1/#cos-ct-derived-ok

    // 1

    if (derivedType != baseType) {

        if ((derivedType->derivationMethod() == SchemaType::DerivationRestriction) && (constraints & SchemaType::RestrictionConstraint))

            return false;

        if ((derivedType->derivationMethod() == SchemaType::DerivationExtension) && (constraints & SchemaType::ExtensionConstraint))

            return false;

    }

    // 2.1

    if (derivedType == baseType)

        return true;

    // 2.2

    if (derivedType->wxsSuperType() == baseType)

        return true;

    // 2.3

    bool isOk = true;

    if (derivedType->wxsSuperType() == BuiltinTypes::xsAnyType) { // 2.3.1

        isOk = false;

    } else { // 2.3.2

        if (!derivedType->wxsSuperType())

            return false;

        if (derivedType->wxsSuperType()->isComplexType()) { // 2.3.2.1

            isOk = isComplexDerivationOk(derivedType->wxsSuperType(), baseType, constraints);

        } else { // 2.3.2.2

            isOk = isSimpleDerivationOk(derivedType->wxsSuperType(), baseType, constraints);

        }

    }

    if (isOk)

        return true;

    return false;

}

bool XsdSchemaHelper::constructAndCompare(const DerivedString<TypeString>::Ptr &operand1,