/*
 * reserved comment block
 * DO NOT REMOVE OR ALTER!
 */
/*
 * Copyright 1999-2004 The Apache Software Foundation.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.sun.org.apache.xerces.internal.impl.xs;

import java.util.Collections;
import java.util.Comparator;
import java.util.Vector;

import com.sun.org.apache.xerces.internal.impl.XMLErrorReporter;
import com.sun.org.apache.xerces.internal.impl.dv.InvalidDatatypeValueException;
import com.sun.org.apache.xerces.internal.impl.dv.ValidatedInfo;
import com.sun.org.apache.xerces.internal.impl.dv.ValidationContext;
import com.sun.org.apache.xerces.internal.impl.dv.XSSimpleType;
import com.sun.org.apache.xerces.internal.impl.xs.models.CMBuilder;
import com.sun.org.apache.xerces.internal.impl.xs.models.XSCMValidator;
import com.sun.org.apache.xerces.internal.impl.xs.util.SimpleLocator;
import com.sun.org.apache.xerces.internal.impl.xs.util.XSObjectListImpl;
import com.sun.org.apache.xerces.internal.util.SymbolHash;
import com.sun.org.apache.xerces.internal.xs.XSConstants;
import com.sun.org.apache.xerces.internal.xs.XSObjectList;
import com.sun.org.apache.xerces.internal.xs.XSTypeDefinition;

/**
 * Constaints shared by traversers and validator
 *
 * @xerces.internal
 *
 * @author Sandy Gao, IBM
 *
 * @version $Id: XSConstraints.java,v 1.7 2010-11-01 04:39:55 joehw Exp $
 */
public class XSConstraints {

    // IHR: Visited on 2006-11-17
    // Added a boolean return value to particleValidRestriction (it was a void function)
    // to help the checkRecurseLax to know when expansion has happened and no order is required
    // (IHR@xbrl.org) (Ignacio@Hernandez-Ros.com)

    static final int OCCURRENCE_UNKNOWN = SchemaSymbols.OCCURRENCE_UNBOUNDED-1;
    static final XSSimpleType STRING_TYPE = (XSSimpleType)SchemaGrammar.SG_SchemaNS.getGlobalTypeDecl(SchemaSymbols.ATTVAL_STRING);

    private static XSParticleDecl fEmptyParticle = null;
    public static XSParticleDecl getEmptySequence() {
        if (fEmptyParticle == null) {
            XSModelGroupImpl group = new XSModelGroupImpl();
            group.fCompositor = XSModelGroupImpl.MODELGROUP_SEQUENCE;
            group.fParticleCount = 0;
            group.fParticles = null;
            group.fAnnotations = XSObjectListImpl.EMPTY_LIST;
            XSParticleDecl particle = new XSParticleDecl();
            particle.fType = XSParticleDecl.PARTICLE_MODELGROUP;
            particle.fValue = group;
            particle.fAnnotations = XSObjectListImpl.EMPTY_LIST;
            fEmptyParticle = particle;
        }
        return fEmptyParticle;
    }

    private static final Comparator ELEMENT_PARTICLE_COMPARATOR = new Comparator() {

        public int compare(Object o1, Object o2) {
            XSParticleDecl pDecl1 = (XSParticleDecl) o1;
            XSParticleDecl pDecl2 = (XSParticleDecl) o2;
            XSElementDecl decl1 = (XSElementDecl) pDecl1.fValue;
            XSElementDecl decl2 = (XSElementDecl) pDecl2.fValue;

            String namespace1 = decl1.getNamespace();
            String namespace2 = decl2.getNamespace();
            String name1 = decl1.getName();
            String name2 = decl2.getName();

            boolean sameNamespace = (namespace1 == namespace2);
            int namespaceComparison = 0;

            if (!sameNamespace) {
                if (namespace1 != null) {
                    if (namespace2 != null){
                        namespaceComparison = namespace1.compareTo(namespace2);
                    }
                    else {
                        namespaceComparison = 1;
                    }
                }
                else {
                    namespaceComparison = -1;
                }
            }
            //This assumes that the names are never null.
            return namespaceComparison != 0 ? namespaceComparison : name1.compareTo(name2);
        }
    };

    /**
     * check whether derived is valid derived from base, given a subset
     * of {restriction, extension}.B
     */
    public static boolean checkTypeDerivationOk(XSTypeDefinition derived, XSTypeDefinition base, short block) {
        // if derived is anyType, then it's valid only if base is anyType too
        if (derived == SchemaGrammar.fAnyType)
            return derived == base;
        // if derived is anySimpleType, then it's valid only if the base
        // is ur-type
        if (derived == SchemaGrammar.fAnySimpleType) {
            return (base == SchemaGrammar.fAnyType ||
                    base == SchemaGrammar.fAnySimpleType);
        }

        // if derived is simple type
        if (derived.getTypeCategory() == XSTypeDefinition.SIMPLE_TYPE) {
            // if base is complex type
            if (base.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
                // if base is anyType, change base to anySimpleType,
                // otherwise, not valid
                if (base == SchemaGrammar.fAnyType)
                    base = SchemaGrammar.fAnySimpleType;
                else
                    return false;
            }
            return checkSimpleDerivation((XSSimpleType)derived,
                    (XSSimpleType)base, block);
        }
        else {
            return checkComplexDerivation((XSComplexTypeDecl)derived, base, block);
        }
    }

    /**
     * check whether simple type derived is valid derived from base,
     * given a subset of {restriction, extension}.
     */
    public static boolean checkSimpleDerivationOk(XSSimpleType derived, XSTypeDefinition base, short block) {
        // if derived is anySimpleType, then it's valid only if the base
        // is ur-type
        if (derived == SchemaGrammar.fAnySimpleType) {
            return (base == SchemaGrammar.fAnyType ||
                    base == SchemaGrammar.fAnySimpleType);
        }

        // if base is complex type
        if (base.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
            // if base is anyType, change base to anySimpleType,
            // otherwise, not valid
            if (base == SchemaGrammar.fAnyType)
                base = SchemaGrammar.fAnySimpleType;
            else
                return false;
        }
        return checkSimpleDerivation((XSSimpleType)derived,
                (XSSimpleType)base, block);
    }

    /**
     * check whether complex type derived is valid derived from base,
     * given a subset of {restriction, extension}.
     */
    public static boolean checkComplexDerivationOk(XSComplexTypeDecl derived, XSTypeDefinition base, short block) {
        // if derived is anyType, then it's valid only if base is anyType too
        if (derived == SchemaGrammar.fAnyType)
            return derived == base;
        return checkComplexDerivation((XSComplexTypeDecl)derived, base, block);
    }

    /**
     * Note: this will be a private method, and it assumes that derived is not
     *       anySimpleType, and base is not anyType. Another method will be
     *       introduced for public use, which will call this method.
     */
    private static boolean checkSimpleDerivation(XSSimpleType derived, XSSimpleType base, short block) {
        // 1 They are the same type definition.
        if (derived == base)
            return true;

        // 2 All of the following must be true:
        // 2.1 restriction is not in the subset, or in the {final} of its own {base type definition};
        if ((block & XSConstants.DERIVATION_RESTRICTION) != 0 ||
                (derived.getBaseType().getFinal() & XSConstants.DERIVATION_RESTRICTION) != 0) {
            return false;
        }

        // 2.2 One of the following must be true:
        // 2.2.1 D's base type definition is B.
        XSSimpleType directBase = (XSSimpleType)derived.getBaseType();
        if (directBase == base)
            return true;

        // 2.2.2 D's base type definition is not the simple ur-type definition and is validly derived from B given the subset, as defined by this constraint.
        if (directBase != SchemaGrammar.fAnySimpleType &&
                checkSimpleDerivation(directBase, base, block)) {
            return true;
        }

        // 2.2.3 D's {variety} is list or union and B is the simple ur-type definition.
        if ((derived.getVariety() == XSSimpleType.VARIETY_LIST ||
                derived.getVariety() == XSSimpleType.VARIETY_UNION) &&
                base == SchemaGrammar.fAnySimpleType) {
            return true;
        }

        // 2.2.4 B's {variety} is union and D is validly derived from a type definition in B's {member type definitions} given the subset, as defined by this constraint.
        if (base.getVariety() == XSSimpleType.VARIETY_UNION) {
            XSObjectList subUnionMemberDV = base.getMemberTypes();
            int subUnionSize = subUnionMemberDV.getLength();
            for (int i=0; i<subUnionSize; i++) {
                base = (XSSimpleType)subUnionMemberDV.item(i);
                if (checkSimpleDerivation(derived, base, block))
                    return true;
            }
        }

        return false;
    }

    /**
     * Note: this will be a private method, and it assumes that derived is not
     *       anyType. Another method will be introduced for public use,
     *       which will call this method.
     */
    private static boolean checkComplexDerivation(XSComplexTypeDecl derived, XSTypeDefinition base, short block) {
        // 2.1 B and D must be the same type definition.
        if (derived == base)
            return true;

        // 1 If B and D are not the same type definition, then the {derivation method} of D must not be in the subset.
        if ((derived.fDerivedBy & block) != 0)
            return false;

        // 2 One of the following must be true:
        XSTypeDefinition directBase = derived.fBaseType;
        // 2.2 B must be D's {base type definition}.
        if (directBase == base)
            return true;

        // 2.3 All of the following must be true:
        // 2.3.1 D's {base type definition} must not be the ur-type definition.
        if (directBase == SchemaGrammar.fAnyType ||
                directBase == SchemaGrammar.fAnySimpleType) {
            return false;
        }

        // 2.3.2 The appropriate case among the following must be true:
        // 2.3.2.1 If D's {base type definition} is complex, then it must be validly derived from B given the subset as defined by this constraint.
        if (directBase.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE)
            return checkComplexDerivation((XSComplexTypeDecl)directBase, base, block);

        // 2.3.2.2 If D's {base type definition} is simple, then it must be validly derived from B given the subset as defined in Type Derivation OK (Simple) (3.14.6).
        if (directBase.getTypeCategory() == XSTypeDefinition.SIMPLE_TYPE) {
            // if base is complex type
            if (base.getTypeCategory() == XSTypeDefinition.COMPLEX_TYPE) {
                // if base is anyType, change base to anySimpleType,
                // otherwise, not valid
                if (base == SchemaGrammar.fAnyType)
                    base = SchemaGrammar.fAnySimpleType;
                else
                    return false;
            }
            return checkSimpleDerivation((XSSimpleType)directBase,
                    (XSSimpleType)base, block);
        }

        return false;
    }

    /**
     * check whether a value is a valid default for some type
     * returns the compiled form of the value
     * The parameter value could be either a String or a ValidatedInfo object
     */
    public static Object ElementDefaultValidImmediate(XSTypeDefinition type, String value, ValidationContext context, ValidatedInfo vinfo) {

        XSSimpleType dv = null;

        // e-props-correct
        // For a string to be a valid default with respect to a type definition the appropriate case among the following must be true:
        // 1 If the type definition is a simple type definition, then the string must be valid with respect to that definition as defined by String Valid (3.14.4).
        if (type.getTypeCategory() == XSTypeDefinition.SIMPLE_TYPE) {
            dv = (XSSimpleType)type;
        }

        // 2 If the type definition is a complex type definition, then all of the following must be true:
        else {
            // 2.1 its {content type} must be a simple type definition or mixed.
            XSComplexTypeDecl ctype = (XSComplexTypeDecl)type;
            // 2.2 The appropriate case among the following must be true:
            // 2.2.1 If the {content type} is a simple type definition, then the string must be valid with respect to that simple type definition as defined by String Valid (3.14.4).
            if (ctype.fContentType == XSComplexTypeDecl.CONTENTTYPE_SIMPLE) {
                dv = ctype.fXSSimpleType;
            }
            // 2.2.2 If the {content type} is mixed, then the {content type}'s particle must be emptiable as defined by Particle Emptiable (3.9.6).
            else if (ctype.fContentType == XSComplexTypeDecl.CONTENTTYPE_MIXED) {
                if (!((XSParticleDecl)ctype.getParticle()).emptiable())
                    return null;
            }
            else {
                return null;
            }
        }

        // get the simple type declaration, and validate
        Object actualValue = null;
        if (dv == null) {
            // complex type with mixed. to make sure that we store correct
            // information in vinfo and return the correct value, we use
            // "string" type for validation
            dv = STRING_TYPE;
        }
        try {
            // validate the original lexical rep, and set the actual value
            actualValue = dv.validate(value, context, vinfo);
            // validate the canonical lexical rep
            if (vinfo != null)
                actualValue = dv.validate(vinfo.stringValue(), context, vinfo);
        } catch (InvalidDatatypeValueException ide) {
            return null;
        }

        return actualValue;
    }

    static void reportSchemaError(XMLErrorReporter errorReporter,
            SimpleLocator loc,
            String key, Object[] args) {
        if (loc != null) {
            errorReporter.reportError(loc, XSMessageFormatter.SCHEMA_DOMAIN,
                    key, args, XMLErrorReporter.SEVERITY_ERROR);
        }
        else {
            errorReporter.reportError(XSMessageFormatter.SCHEMA_DOMAIN,
                    key, args, XMLErrorReporter.SEVERITY_ERROR);
        }
    }

    /**
     * used to check the 3 constraints against each complex type
     * (should be each model group):
     * Unique Particle Attribution, Particle Derivation (Restriction),
     * Element Declrations Consistent.
     */
    public static void fullSchemaChecking(XSGrammarBucket grammarBucket,
            SubstitutionGroupHandler SGHandler,
            CMBuilder cmBuilder,
            XMLErrorReporter errorReporter) {
        // get all grammars, and put all substitution group information
        // in the substitution group handler
        SchemaGrammar[] grammars = grammarBucket.getGrammars();
        for (int i = grammars.length-1; i >= 0; i--) {
            SGHandler.addSubstitutionGroup(grammars[i].getSubstitutionGroups());
        }

        XSParticleDecl fakeDerived = new XSParticleDecl();
        XSParticleDecl fakeBase = new XSParticleDecl();
        fakeDerived.fType = XSParticleDecl.PARTICLE_MODELGROUP;
        fakeBase.fType = XSParticleDecl.PARTICLE_MODELGROUP;
        // before worrying about complexTypes, let's get
        // groups redefined by restriction out of the way.
        for (int g = grammars.length-1; g >= 0; g--) {
            XSGroupDecl [] redefinedGroups = grammars[g].getRedefinedGroupDecls();
            SimpleLocator [] rgLocators = grammars[g].getRGLocators();
            for(int i=0; i<redefinedGroups.length; ) {
                XSGroupDecl derivedGrp = redefinedGroups[i++];
                XSModelGroupImpl derivedMG = derivedGrp.fModelGroup;
                XSGroupDecl baseGrp = redefinedGroups[i++];
                XSModelGroupImpl baseMG = baseGrp.fModelGroup;
                fakeDerived.fValue = derivedMG;
                fakeBase.fValue = baseMG;
                if(baseMG == null) {
                    if(derivedMG != null) { // can't be a restriction!
                        reportSchemaError(errorReporter, rgLocators[i/2-1],
                                "src-redefine.6.2.2",
                                new Object[]{derivedGrp.fName, "rcase-Recurse.2"});
                    }
                } else if (derivedMG == null) {
                    if (!fakeBase.emptiable()) {
                        reportSchemaError(errorReporter, rgLocators[i/2-1],
                                "src-redefine.6.2.2",
                                new Object[]{derivedGrp.fName, "rcase-Recurse.2"});
                    }
                } else {
                    try {
                        particleValidRestriction(fakeDerived, SGHandler, fakeBase, SGHandler);
                    } catch (XMLSchemaException e) {
                        String key = e.getKey();
                        reportSchemaError(errorReporter, rgLocators[i/2-1],
                                key,
                                e.getArgs());
                        reportSchemaError(errorReporter, rgLocators[i/2-1],
                                "src-redefine.6.2.2",
                                new Object[]{derivedGrp.fName, key});
                    }
                }
            }
        }

        // for each complex type, check the 3 constraints.
        // types need to be checked
        XSComplexTypeDecl[] types;
        SimpleLocator [] ctLocators;
        // to hold the errors
        // REVISIT: do we want to report all errors? or just one?
        //XMLSchemaError1D errors = new XMLSchemaError1D();
        // whether need to check this type again;
        // whether only do UPA checking
        boolean further, fullChecked;
        // if do all checkings, how many need to be checked again.
        int keepType;
        // i: grammar; j: type; k: error
        // for all grammars
        SymbolHash elemTable = new SymbolHash();
        for (int i = grammars.length-1, j; i >= 0; i--) {
            // get whether to skip EDC, and types need to be checked
            keepType = 0;
            fullChecked = grammars[i].fFullChecked;
            types = grammars[i].getUncheckedComplexTypeDecls();
            ctLocators = grammars[i].getUncheckedCTLocators();
            // for each type
            for (j = 0; j < types.length; j++) {
                // if we've already full-checked this grammar, then
                // skip the EDC constraint
                if (!fullChecked) {
                    // 1. Element Decl Consistent
                    if (types[j].fParticle!=null) {
                        elemTable.clear();
                        try {
                            checkElementDeclsConsistent(types[j], types[j].fParticle,
                                    elemTable, SGHandler);
                        }
                        catch (XMLSchemaException e) {
                            reportSchemaError(errorReporter, ctLocators[j],
                                    e.getKey(),
                                    e.getArgs());
                        }
                    }
                }

                // 2. Particle Derivation

                if (types[j].fBaseType != null &&
                        types[j].fBaseType != SchemaGrammar.fAnyType &&
                        types[j].fDerivedBy == XSConstants.DERIVATION_RESTRICTION &&
                        (types[j].fBaseType instanceof XSComplexTypeDecl)) {

                    XSParticleDecl derivedParticle=types[j].fParticle;
                    XSParticleDecl baseParticle=
                        ((XSComplexTypeDecl)(types[j].fBaseType)).fParticle;
                    if (derivedParticle==null) {
                        if (baseParticle!=null && !baseParticle.emptiable()) {
                            reportSchemaError(errorReporter,ctLocators[j],
                                    "derivation-ok-restriction.5.3.2",
                                    new Object[]{types[j].fName, types[j].fBaseType.getName()});
                        }
                    }
                    else if (baseParticle!=null) {
                        try {
                            particleValidRestriction(types[j].fParticle,
                                    SGHandler,
                                    ((XSComplexTypeDecl)(types[j].fBaseType)).fParticle,
                                    SGHandler);
                        } catch (XMLSchemaException e) {
                            reportSchemaError(errorReporter, ctLocators[j],
                                    e.getKey(),
                                    e.getArgs());
                            reportSchemaError(errorReporter, ctLocators[j],
                                    "derivation-ok-restriction.5.4.2",
                                    new Object[]{types[j].fName});
                        }
                    }
                    else {
                        reportSchemaError(errorReporter, ctLocators[j],
                                "derivation-ok-restriction.5.4.2",
                                new Object[]{types[j].fName});
                    }
                }
                // 3. UPA
                // get the content model and check UPA
                XSCMValidator cm = types[j].getContentModel(cmBuilder);
                further = false;
                if (cm != null) {
                    try {
                        further = cm.checkUniqueParticleAttribution(SGHandler);
                    } catch (XMLSchemaException e) {
                        reportSchemaError(errorReporter, ctLocators[j],
                                e.getKey(),
                                e.getArgs());
                    }
                }
                // now report all errors
                // REVISIT: do we want to report all errors? or just one?
                /*for (k = errors.getErrorCodeNum()-1; k >= 0; k--) {
                    reportSchemaError(errorReporter, ctLocators[j],
                                      errors.getErrorCode(k),
                                      errors.getArgs(k));
                }*/

                // if we are doing all checkings, and this one needs further
                // checking, store it in the type array.
                if (!fullChecked && further)
                    types[keepType++] = types[j];

                // clear errors for the next type.
                // REVISIT: do we want to report all errors? or just one?
                //errors.clear();
            }
            // we've done with the types in this grammar. if we are checking
            // all constraints, need to trim type array to a proper size:
            // only contain those need further checking.
            // and mark this grammar that it only needs UPA checking.
            if (!fullChecked) {
                grammars[i].setUncheckedTypeNum(keepType);
                grammars[i].fFullChecked = true;
            }
        }
    }

    /*
       Check that a given particle is a valid restriction of a base particle.
     */

    public static void checkElementDeclsConsistent(XSComplexTypeDecl type,
            XSParticleDecl particle,
            SymbolHash elemDeclHash,
            SubstitutionGroupHandler sgHandler)
        throws XMLSchemaException {

        // check for elements in the tree with the same name and namespace

        int pType = particle.fType;

        if (pType == XSParticleDecl.PARTICLE_WILDCARD)
            return;

        if (pType == XSParticleDecl.PARTICLE_ELEMENT) {
            XSElementDecl elem = (XSElementDecl)(particle.fValue);
            findElemInTable(type, elem, elemDeclHash);

            if (elem.fScope == XSConstants.SCOPE_GLOBAL) {
                // Check for subsitution groups.
                XSElementDecl[] subGroup = sgHandler.getSubstitutionGroup(elem);
                for (int i = 0; i < subGroup.length; i++) {
                    findElemInTable(type, subGroup[i], elemDeclHash);
                }
            }
            return;
        }

        XSModelGroupImpl group = (XSModelGroupImpl)particle.fValue;
        for (int i = 0; i < group.fParticleCount; i++)
            checkElementDeclsConsistent(type, group.fParticles[i], elemDeclHash, sgHandler);
    }

    public static void findElemInTable(XSComplexTypeDecl type, XSElementDecl elem,
            SymbolHash elemDeclHash)
        throws XMLSchemaException {

        // How can we avoid this concat?  LM.
        String name = elem.fName + "," + elem.fTargetNamespace;

        XSElementDecl existingElem = null;
        if ((existingElem = (XSElementDecl)(elemDeclHash.get(name))) == null) {
            // just add it in
            elemDeclHash.put(name, elem);
        }
        else {
            // If this is the same check element, we're O.K.
            if (elem == existingElem)
                return;

            if (elem.fType != existingElem.fType) {
                // Types are not the same
                throw new XMLSchemaException("cos-element-consistent",
                        new Object[] {type.fName, elem.fName});

            }
        }
    }

    // Check that a given particle is a valid restriction of a base particle.
    //
    // IHR: 2006/11/17
    // Returns a boolean indicating if there has been expansion of substitution group
    // in the bParticle.
    // With this information the checkRecurseLax function knows when is
    // to keep the order and when to ignore it.
    private static boolean particleValidRestriction(XSParticleDecl dParticle,
            SubstitutionGroupHandler dSGHandler,
            XSParticleDecl bParticle,
            SubstitutionGroupHandler bSGHandler)
        throws XMLSchemaException {
        return particleValidRestriction(dParticle, dSGHandler, bParticle, bSGHandler, true);
    }

    private static boolean particleValidRestriction(XSParticleDecl dParticle,
            SubstitutionGroupHandler dSGHandler,
            XSParticleDecl bParticle,
            SubstitutionGroupHandler bSGHandler,
            boolean checkWCOccurrence)
        throws XMLSchemaException {

        Vector dChildren = null;
        Vector bChildren = null;
        int dMinEffectiveTotalRange=OCCURRENCE_UNKNOWN;
        int dMaxEffectiveTotalRange=OCCURRENCE_UNKNOWN;

        // By default there has been no expansion
        boolean bExpansionHappened = false;

        // Check for empty particles.   If either base or derived particle is empty,
        // (and the other isn't) it's an error.
        if (dParticle.isEmpty() && !bParticle.emptiable()) {
            throw new XMLSchemaException("cos-particle-restrict.a", null);
        }
        else if (!dParticle.isEmpty() && bParticle.isEmpty()) {
            throw new XMLSchemaException("cos-particle-restrict.b", null);
        }

        //
        // Do setup prior to invoking the Particle (Restriction) cases.
        // This involves:
        //   - removing pointless occurrences for groups, and retrieving a vector of
        //     non-pointless children
        //   - turning top-level elements with substitution groups into CHOICE groups.
        //

        short dType = dParticle.fType;
        //
        // Handle pointless groups for the derived particle
        //
        if (dType == XSParticleDecl.PARTICLE_MODELGROUP) {
            dType = ((XSModelGroupImpl)dParticle.fValue).fCompositor;

            // Find a group, starting with this particle, with more than 1 child.   There
            // may be none, and the particle of interest trivially becomes an element or
            // wildcard.
            XSParticleDecl dtmp = getNonUnaryGroup(dParticle);
            if (dtmp != dParticle) {
                // Particle has been replaced.   Retrieve new type info.
                dParticle = dtmp;
                dType = dParticle.fType;
                if (dType == XSParticleDecl.PARTICLE_MODELGROUP)
                    dType = ((XSModelGroupImpl)dParticle.fValue).fCompositor;
            }

            // Fill in a vector with the children of the particle, removing any
            // pointless model groups in the process.
            dChildren = removePointlessChildren(dParticle);
        }

        int dMinOccurs = dParticle.fMinOccurs;
        int dMaxOccurs = dParticle.fMaxOccurs;

        //
        // For elements which are the heads of substitution groups, treat as CHOICE
        //
        if (dSGHandler != null && dType == XSParticleDecl.PARTICLE_ELEMENT) {
            XSElementDecl dElement = (XSElementDecl)dParticle.fValue;

            if (dElement.fScope == XSConstants.SCOPE_GLOBAL) {
                // Check for subsitution groups.   Treat any element that has a
                // subsitution group as a choice.   Fill in the children vector with the
                // members of the substitution group
                XSElementDecl[] subGroup = dSGHandler.getSubstitutionGroup(dElement);
                if (subGroup.length >0 ) {
                    // Now, set the type to be CHOICE.  The "group" will have the same
                    // occurrence information as the original particle.
                    dType = XSModelGroupImpl.MODELGROUP_CHOICE;
                    dMinEffectiveTotalRange = dMinOccurs;
                    dMaxEffectiveTotalRange = dMaxOccurs;

                    // Fill in the vector of children
                    dChildren = new Vector(subGroup.length+1);
                    for (int i = 0; i < subGroup.length; i++) {
                        addElementToParticleVector(dChildren, subGroup[i]);
                    }
                    addElementToParticleVector(dChildren, dElement);
                    Collections.sort(dChildren, ELEMENT_PARTICLE_COMPARATOR);

                    // Set the handler to null, to indicate that we've finished handling
                    // substitution groups for this particle.
                    dSGHandler = null;
                }
            }
        }

        short bType = bParticle.fType;
        //
        // Handle pointless groups for the base particle
        //
        if (bType == XSParticleDecl.PARTICLE_MODELGROUP) {
            bType = ((XSModelGroupImpl)bParticle.fValue).fCompositor;

            // Find a group, starting with this particle, with more than 1 child.   There
            // may be none, and the particle of interest trivially becomes an element or
            // wildcard.
            XSParticleDecl btmp = getNonUnaryGroup(bParticle);
            if (btmp != bParticle) {
                // Particle has been replaced.   Retrieve new type info.
                bParticle = btmp;
                bType = bParticle.fType;
                if (bType == XSParticleDecl.PARTICLE_MODELGROUP)
                    bType = ((XSModelGroupImpl)bParticle.fValue).fCompositor;
            }

            // Fill in a vector with the children of the particle, removing any
            // pointless model groups in the process.
            bChildren = removePointlessChildren(bParticle);
        }

        int bMinOccurs = bParticle.fMinOccurs;
        int bMaxOccurs = bParticle.fMaxOccurs;

        if (bSGHandler != null && bType == XSParticleDecl.PARTICLE_ELEMENT) {
            XSElementDecl bElement = (XSElementDecl)bParticle.fValue;

            if (bElement.fScope == XSConstants.SCOPE_GLOBAL) {
                // Check for subsitution groups.   Treat any element that has a
                // subsitution group as a choice.   Fill in the children vector with the
                // members of the substitution group
                XSElementDecl[] bsubGroup = bSGHandler.getSubstitutionGroup(bElement);
                if (bsubGroup.length >0 ) {
                    // Now, set the type to be CHOICE
                    bType = XSModelGroupImpl.MODELGROUP_CHOICE;

                    bChildren = new Vector(bsubGroup.length+1);
                    for (int i = 0; i < bsubGroup.length; i++) {
                        addElementToParticleVector(bChildren, bsubGroup[i]);
                    }
                    addElementToParticleVector(bChildren, bElement);
                    Collections.sort(bChildren, ELEMENT_PARTICLE_COMPARATOR);
                    // Set the handler to null, to indicate that we've finished handling
                    // substitution groups for this particle.
                    bSGHandler = null;

                    // if we are here expansion of bParticle happened
                    bExpansionHappened = true;
                }
            }
        }

        //
        // O.K. - Figure out which particle derivation rule applies and call it
        //
        switch (dType) {
            case XSParticleDecl.PARTICLE_ELEMENT:
            {
                switch (bType) {

                    // Elt:Elt NameAndTypeOK
                    case XSParticleDecl.PARTICLE_ELEMENT:
                    {
                        checkNameAndTypeOK((XSElementDecl)dParticle.fValue,dMinOccurs,dMaxOccurs,
                                (XSElementDecl)bParticle.fValue,bMinOccurs,bMaxOccurs);
                        return bExpansionHappened;
                    }

                    // Elt:Any NSCompat
                    case XSParticleDecl.PARTICLE_WILDCARD:
                    {
                        checkNSCompat((XSElementDecl)dParticle.fValue,dMinOccurs,dMaxOccurs,
                                (XSWildcardDecl)bParticle.fValue,bMinOccurs,bMaxOccurs,
                                checkWCOccurrence);
                        return bExpansionHappened;
                    }

                    // Elt:All RecurseAsIfGroup
                    case XSModelGroupImpl.MODELGROUP_CHOICE:
                    {
                        // Treat the element as if it were in a group of the same type
                        // as the base Particle
                        dChildren = new Vector();
                        dChildren.addElement(dParticle);

                        checkRecurseLax(dChildren, 1, 1, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }
                    case XSModelGroupImpl.MODELGROUP_SEQUENCE:
                    case XSModelGroupImpl.MODELGROUP_ALL:
                    {
                        // Treat the element as if it were in a group of the same type
                        // as the base Particle
                        dChildren = new Vector();
                        dChildren.addElement(dParticle);

                        checkRecurse(dChildren, 1, 1, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }

                    default:
                    {
                        throw new XMLSchemaException("Internal-Error",
                                new Object[]{"in particleValidRestriction"});
                    }
                }
            }

            case XSParticleDecl.PARTICLE_WILDCARD:
            {
                switch (bType) {

                    // Any:Any NSSubset
                    case XSParticleDecl.PARTICLE_WILDCARD:
                    {
                        checkNSSubset((XSWildcardDecl)dParticle.fValue, dMinOccurs, dMaxOccurs,
                                (XSWildcardDecl)bParticle.fValue, bMinOccurs, bMaxOccurs);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_CHOICE:
                    case XSModelGroupImpl.MODELGROUP_SEQUENCE:
                    case XSModelGroupImpl.MODELGROUP_ALL:
                    case XSParticleDecl.PARTICLE_ELEMENT:
                    {
                        throw new XMLSchemaException("cos-particle-restrict.2",
                                new Object[]{"any:choice,sequence,all,elt"});
                    }

                    default:
                    {
                        throw new XMLSchemaException("Internal-Error",
                                new Object[]{"in particleValidRestriction"});
                    }
                }
            }

            case XSModelGroupImpl.MODELGROUP_ALL:
            {
                switch (bType) {

                    // All:Any NSRecurseCheckCardinality
                    case XSParticleDecl.PARTICLE_WILDCARD:
                    {
                        if (dMinEffectiveTotalRange == OCCURRENCE_UNKNOWN)
                            dMinEffectiveTotalRange = dParticle.minEffectiveTotalRange();
                        if (dMaxEffectiveTotalRange == OCCURRENCE_UNKNOWN)
                            dMaxEffectiveTotalRange = dParticle.maxEffectiveTotalRange();

                        checkNSRecurseCheckCardinality(dChildren, dMinEffectiveTotalRange,
                                dMaxEffectiveTotalRange,
                                dSGHandler,
                                bParticle,bMinOccurs,bMaxOccurs,
                                checkWCOccurrence);

                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_ALL:
                    {
                        checkRecurse(dChildren, dMinOccurs, dMaxOccurs, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_CHOICE:
                    case XSModelGroupImpl.MODELGROUP_SEQUENCE:
                    case XSParticleDecl.PARTICLE_ELEMENT:
                    {
                        throw new XMLSchemaException("cos-particle-restrict.2",
                                new Object[]{"all:choice,sequence,elt"});
                    }

                    default:
                    {
                        throw new XMLSchemaException("Internal-Error",
                                new Object[]{"in particleValidRestriction"});
                    }
                }
            }

            case XSModelGroupImpl.MODELGROUP_CHOICE:
            {
                switch (bType) {

                    // Choice:Any NSRecurseCheckCardinality
                    case XSParticleDecl.PARTICLE_WILDCARD:
                    {
                        if (dMinEffectiveTotalRange == OCCURRENCE_UNKNOWN)
                            dMinEffectiveTotalRange = dParticle.minEffectiveTotalRange();
                        if (dMaxEffectiveTotalRange == OCCURRENCE_UNKNOWN)
                            dMaxEffectiveTotalRange = dParticle.maxEffectiveTotalRange();

                        checkNSRecurseCheckCardinality(dChildren, dMinEffectiveTotalRange,
                                dMaxEffectiveTotalRange,
                                dSGHandler,
                                bParticle,bMinOccurs,bMaxOccurs,
                                checkWCOccurrence);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_CHOICE:
                    {
                        checkRecurseLax(dChildren, dMinOccurs, dMaxOccurs, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_ALL:
                    case XSModelGroupImpl.MODELGROUP_SEQUENCE:
                    case XSParticleDecl.PARTICLE_ELEMENT:
                    {
                        throw new XMLSchemaException("cos-particle-restrict.2",
                                new Object[]{"choice:all,sequence,elt"});
                    }

                    default:
                    {
                        throw new XMLSchemaException("Internal-Error",
                                new Object[]{"in particleValidRestriction"});
                    }
                }
            }


            case XSModelGroupImpl.MODELGROUP_SEQUENCE:
            {
                switch (bType) {

                    // Choice:Any NSRecurseCheckCardinality
                    case XSParticleDecl.PARTICLE_WILDCARD:
                    {
                        if (dMinEffectiveTotalRange == OCCURRENCE_UNKNOWN)
                            dMinEffectiveTotalRange = dParticle.minEffectiveTotalRange();
                        if (dMaxEffectiveTotalRange == OCCURRENCE_UNKNOWN)
                            dMaxEffectiveTotalRange = dParticle.maxEffectiveTotalRange();

                        checkNSRecurseCheckCardinality(dChildren, dMinEffectiveTotalRange,
                                dMaxEffectiveTotalRange,
                                dSGHandler,
                                bParticle,bMinOccurs,bMaxOccurs,
                                checkWCOccurrence);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_ALL:
                    {
                        checkRecurseUnordered(dChildren, dMinOccurs, dMaxOccurs, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_SEQUENCE:
                    {
                        checkRecurse(dChildren, dMinOccurs, dMaxOccurs, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }

                    case XSModelGroupImpl.MODELGROUP_CHOICE:
                    {
                        int min1 = dMinOccurs * dChildren.size();
                        int max1 = (dMaxOccurs == SchemaSymbols.OCCURRENCE_UNBOUNDED)?
                                dMaxOccurs : dMaxOccurs * dChildren.size();
                        checkMapAndSum(dChildren, min1, max1, dSGHandler,
                                bChildren, bMinOccurs, bMaxOccurs, bSGHandler);
                        return bExpansionHappened;
                    }

                    case XSParticleDecl.PARTICLE_ELEMENT:
                    {
                        throw new XMLSchemaException("cos-particle-restrict.2",
                                new Object[]{"seq:elt"});
                    }

                    default:
                    {
                        throw new XMLSchemaException("Internal-Error",
                                new Object[]{"in particleValidRestriction"});
                    }
                }
            }

        }

        return bExpansionHappened;
    }

    private static void addElementToParticleVector (Vector v, XSElementDecl d)  {

        XSParticleDecl p = new XSParticleDecl();
        p.fValue = d;
        p.fType = XSParticleDecl.PARTICLE_ELEMENT;
        v.addElement(p);

    }

    private static XSParticleDecl getNonUnaryGroup(XSParticleDecl p) {

        if (p.fType == XSParticleDecl.PARTICLE_ELEMENT ||
                p.fType == XSParticleDecl.PARTICLE_WILDCARD)
            return p;

        if (p.fMinOccurs==1 && p.fMaxOccurs==1 &&
                p.fValue!=null && ((XSModelGroupImpl)p.fValue).fParticleCount == 1)
            return getNonUnaryGroup(((XSModelGroupImpl)p.fValue).fParticles[0]);
        else
            return p;
    }

    private static Vector removePointlessChildren(XSParticleDecl p)  {

        if (p.fType == XSParticleDecl.PARTICLE_ELEMENT ||
                p.fType == XSParticleDecl.PARTICLE_WILDCARD)
            return null;

        Vector children = new Vector();

        XSModelGroupImpl group = (XSModelGroupImpl)p.fValue;
        for (int i = 0; i < group.fParticleCount; i++)
            gatherChildren(group.fCompositor, group.fParticles[i], children);

        return children;
    }


    private static void gatherChildren(int parentType, XSParticleDecl p, Vector children) {

        int min = p.fMinOccurs;
        int max = p.fMaxOccurs;
        int type = p.fType;
        if (type == XSParticleDecl.PARTICLE_MODELGROUP)
            type = ((XSModelGroupImpl)p.fValue).fCompositor;

        if (type == XSParticleDecl.PARTICLE_ELEMENT ||
                type== XSParticleDecl.PARTICLE_WILDCARD) {
            children.addElement(p);
            return;
        }

        if (! (min==1 && max==1)) {
            children.addElement(p);
        }
        else if (parentType == type) {
            XSModelGroupImpl group = (XSModelGroupImpl)p.fValue;
            for (int i = 0; i < group.fParticleCount; i++)
                gatherChildren(type, group.fParticles[i], children);
        }
        else if (!p.isEmpty()) {
            children.addElement(p);
        }

    }

    private static void checkNameAndTypeOK(XSElementDecl dElement, int dMin, int dMax,
            XSElementDecl bElement, int bMin, int bMax)
        throws XMLSchemaException {


        //
        // Check that the names are the same
        //
        if (dElement.fName != bElement.fName ||
                dElement.fTargetNamespace != bElement.fTargetNamespace) {
            throw new XMLSchemaException(
                    "rcase-NameAndTypeOK.1",new Object[]{dElement.fName,
                            dElement.fTargetNamespace, bElement.fName, bElement.fTargetNamespace});
        }

        //
        // Check nillable
        //
        if (!bElement.getNillable() && dElement.getNillable()) {
            throw new XMLSchemaException("rcase-NameAndTypeOK.2",
                    new Object[]{dElement.fName});
        }

        //
        // Check occurrence range
        //
        if (!checkOccurrenceRange(dMin, dMax, bMin, bMax)) {
            throw new XMLSchemaException("rcase-NameAndTypeOK.3",
                    new Object[]{
                    dElement.fName,
                    Integer.toString(dMin),
                    dMax==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(dMax),
                            Integer.toString(bMin),
                            bMax==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(bMax)});
        }

        //
        // Check for consistent fixed values
        //
        if (bElement.getConstraintType() == XSConstants.VC_FIXED) {
            // derived one has to have a fixed value
            if (dElement.getConstraintType() != XSConstants.VC_FIXED) {
                throw new XMLSchemaException("rcase-NameAndTypeOK.4.a",
                        new Object[]{dElement.fName, bElement.fDefault.stringValue()});
            }

            // get simple type
            boolean isSimple = false;
            if (dElement.fType.getTypeCategory() == XSTypeDefinition.SIMPLE_TYPE ||
                    ((XSComplexTypeDecl)dElement.fType).fContentType == XSComplexTypeDecl.CONTENTTYPE_SIMPLE) {
                isSimple = true;
            }

            // if there is no simple type, then compare based on string
            if (!isSimple && !bElement.fDefault.normalizedValue.equals(dElement.fDefault.normalizedValue) ||
                    isSimple && !bElement.fDefault.actualValue.equals(dElement.fDefault.actualValue)) {
                throw new XMLSchemaException("rcase-NameAndTypeOK.4.b",
                        new Object[]{dElement.fName,
                        dElement.fDefault.stringValue(),
                        bElement.fDefault.stringValue()});
            }
        }

        //
        // Check identity constraints
        //
        checkIDConstraintRestriction(dElement, bElement);

        //
        // Check for disallowed substitutions
        //
        int blockSet1 = dElement.fBlock;
        int blockSet2 = bElement.fBlock;
        if (((blockSet1 & blockSet2)!=blockSet2) ||
                (blockSet1==XSConstants.DERIVATION_NONE && blockSet2!=XSConstants.DERIVATION_NONE))
            throw new XMLSchemaException("rcase-NameAndTypeOK.6",
                    new Object[]{dElement.fName});


        //
        // Check that the derived element's type is derived from the base's.
        //
        if (!checkTypeDerivationOk(dElement.fType, bElement.fType,
                (short)(XSConstants.DERIVATION_EXTENSION|XSConstants.DERIVATION_LIST|XSConstants.DERIVATION_UNION))) {
            throw new XMLSchemaException("rcase-NameAndTypeOK.7",
                    new Object[]{dElement.fName, dElement.fType.getName(), bElement.fType.getName()});
        }

    }


    private static void checkIDConstraintRestriction(XSElementDecl derivedElemDecl,
            XSElementDecl baseElemDecl)
        throws XMLSchemaException {
        // TODO
    } // checkIDConstraintRestriction


    private static boolean checkOccurrenceRange(int min1, int max1, int min2, int max2) {

        if ((min1 >= min2) &&
                ((max2==SchemaSymbols.OCCURRENCE_UNBOUNDED) ||
                        (max1!=SchemaSymbols.OCCURRENCE_UNBOUNDED && max1<=max2)))
            return true;
        else
            return false;
    }

    private static void checkNSCompat(XSElementDecl elem, int min1, int max1,
            XSWildcardDecl wildcard, int min2, int max2,
            boolean checkWCOccurrence)
        throws XMLSchemaException {

        // check Occurrence ranges
        if (checkWCOccurrence && !checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-NSCompat.2",
                    new Object[]{
                    elem.fName,
                    Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                            Integer.toString(min2),
                            max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        // check wildcard allows namespace of element
        if (!wildcard.allowNamespace(elem.fTargetNamespace))  {
            throw new XMLSchemaException("rcase-NSCompat.1",
                    new Object[]{elem.fName,elem.fTargetNamespace});
        }

    }

    private static void checkNSSubset(XSWildcardDecl dWildcard, int min1, int max1,
            XSWildcardDecl bWildcard, int min2, int max2)
        throws XMLSchemaException {

        // check Occurrence ranges
        if (!checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-NSSubset.2", new Object[]{
                    Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                            Integer.toString(min2),
                            max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        // check wildcard subset
        if (!dWildcard.isSubsetOf(bWildcard)) {
            throw new XMLSchemaException("rcase-NSSubset.1", null);
        }

        if (dWildcard.weakerProcessContents(bWildcard)) {
            throw new XMLSchemaException("rcase-NSSubset.3",
                    new Object[]{dWildcard.getProcessContentsAsString(),
                    bWildcard.getProcessContentsAsString()});
        }

    }


    private static void checkNSRecurseCheckCardinality(Vector children, int min1, int max1,
            SubstitutionGroupHandler dSGHandler,
            XSParticleDecl wildcard, int min2, int max2,
            boolean checkWCOccurrence)
        throws XMLSchemaException {


        // check Occurrence ranges
        if (checkWCOccurrence && !checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-NSRecurseCheckCardinality.2", new Object[]{
                    Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                            Integer.toString(min2),
                            max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        // Check that each member of the group is a valid restriction of the wildcard
        int count = children.size();
        try {
            for (int i = 0; i < count; i++) {
                XSParticleDecl particle1 = (XSParticleDecl)children.elementAt(i);
                particleValidRestriction(particle1, dSGHandler, wildcard, null, false);

            }
        }
        // REVISIT: should we really just ignore original cause of this error?
        //          how can we report it?
        catch (XMLSchemaException e) {
            throw new XMLSchemaException("rcase-NSRecurseCheckCardinality.1", null);
        }

    }

    private static void checkRecurse(Vector dChildren, int min1, int max1,
            SubstitutionGroupHandler dSGHandler,
            Vector bChildren, int min2, int max2,
            SubstitutionGroupHandler bSGHandler)
        throws XMLSchemaException {

        // check Occurrence ranges
        if (!checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-Recurse.1", new Object[]{
                    Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                    Integer.toString(min2),
                    max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        int count1= dChildren.size();
        int count2= bChildren.size();

        int current = 0;
        label: for (int i = 0; i<count1; i++) {

            XSParticleDecl particle1 = (XSParticleDecl)dChildren.elementAt(i);
            for (int j = current; j<count2; j++) {
                XSParticleDecl particle2 = (XSParticleDecl)bChildren.elementAt(j);
                current +=1;
                try {
                    particleValidRestriction(particle1, dSGHandler, particle2, bSGHandler);
                    continue label;
                }
                catch (XMLSchemaException e) {
                    if (!particle2.emptiable())
                        throw new XMLSchemaException("rcase-Recurse.2", null);
                }
            }
            throw new XMLSchemaException("rcase-Recurse.2", null);
        }

        // Now, see if there are some elements in the base we didn't match up
        for (int j=current; j < count2; j++) {
            XSParticleDecl particle2 = (XSParticleDecl)bChildren.elementAt(j);
            if (!particle2.emptiable()) {
                throw new XMLSchemaException("rcase-Recurse.2", null);
            }
        }

    }

    private static void checkRecurseUnordered(Vector dChildren, int min1, int max1,
            SubstitutionGroupHandler dSGHandler,
            Vector bChildren, int min2, int max2,
            SubstitutionGroupHandler bSGHandler)
        throws XMLSchemaException {


        // check Occurrence ranges
        if (!checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-RecurseUnordered.1", new Object[]{
                    Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                    Integer.toString(min2),
                    max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        int count1= dChildren.size();
        int count2 = bChildren.size();

        boolean foundIt[] = new boolean[count2];

        label: for (int i = 0; i<count1; i++) {
            XSParticleDecl particle1 = (XSParticleDecl)dChildren.elementAt(i);

            for (int j = 0; j<count2; j++) {
                XSParticleDecl particle2 = (XSParticleDecl)bChildren.elementAt(j);
                try {
                    particleValidRestriction(particle1, dSGHandler, particle2, bSGHandler);
                    if (foundIt[j])
                        throw new XMLSchemaException("rcase-RecurseUnordered.2", null);
                    else
                        foundIt[j]=true;

                    continue label;
                }
                catch (XMLSchemaException e) {
                }
            }
            // didn't find a match.  Detect an error
            throw new XMLSchemaException("rcase-RecurseUnordered.2", null);
        }

        // Now, see if there are some elements in the base we didn't match up
        for (int j=0; j < count2; j++) {
            XSParticleDecl particle2 = (XSParticleDecl)bChildren.elementAt(j);
            if (!foundIt[j] && !particle2.emptiable()) {
                throw new XMLSchemaException("rcase-RecurseUnordered.2", null);
            }
        }

    }

    private static void checkRecurseLax(Vector dChildren, int min1, int max1,
            SubstitutionGroupHandler dSGHandler,
            Vector bChildren, int min2, int max2,
            SubstitutionGroupHandler  bSGHandler)
        throws XMLSchemaException {

        // check Occurrence ranges
        if (!checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-RecurseLax.1", new Object[]{
                    Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                            Integer.toString(min2),
                            max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        int count1= dChildren.size();
        int count2 = bChildren.size();

        int current = 0;
        label: for (int i = 0; i<count1; i++) {

            XSParticleDecl particle1 = (XSParticleDecl)dChildren.elementAt(i);
            for (int j = current; j<count2; j++) {
                XSParticleDecl particle2 = (XSParticleDecl)bChildren.elementAt(j);
                current +=1;
                try {
                    // IHR: go back one element on b list because the next element may match
                    // this as well.
                    if (particleValidRestriction(particle1, dSGHandler, particle2, bSGHandler))
                        current--;
                    continue label;
                }
                catch (XMLSchemaException e) {
                }
            }
            // didn't find a match.  Detect an error
            throw new XMLSchemaException("rcase-RecurseLax.2", null);

        }

    }

    private static void checkMapAndSum(Vector dChildren, int min1, int max1,
            SubstitutionGroupHandler dSGHandler,
            Vector bChildren, int min2, int max2,
            SubstitutionGroupHandler bSGHandler)
        throws XMLSchemaException {

        // See if the sequence group is a valid restriction of the choice

        // Here is an example of a valid restriction:
        //   <choice minOccurs="2">
        //       <a/>
        //       <b/>
        //       <c/>
        //   </choice>
        //
        //   <sequence>
        //        <b/>
        //        <a/>
        //   </sequence>

        // check Occurrence ranges
        if (!checkOccurrenceRange(min1,max1,min2,max2)) {
            throw new XMLSchemaException("rcase-MapAndSum.2",
                    new Object[]{Integer.toString(min1),
                    max1==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max1),
                            Integer.toString(min2),
                            max2==SchemaSymbols.OCCURRENCE_UNBOUNDED?"unbounded":Integer.toString(max2)});
        }

        int count1 = dChildren.size();
        int count2 = bChildren.size();

        label: for (int i = 0; i<count1; i++) {

            XSParticleDecl particle1 = (XSParticleDecl)dChildren.elementAt(i);
            for (int j = 0; j<count2; j++) {
                XSParticleDecl particle2 = (XSParticleDecl)bChildren.elementAt(j);
                try {
                    particleValidRestriction(particle1, dSGHandler, particle2, bSGHandler);
                    continue label;
                }
                catch (XMLSchemaException e) {
                }
            }
            // didn't find a match.  Detect an error
            throw new XMLSchemaException("rcase-MapAndSum.1", null);
        }
    }
    // to check whether two element overlap, as defined in constraint UPA
    public static boolean overlapUPA(XSElementDecl element1,
            XSElementDecl element2,
            SubstitutionGroupHandler sgHandler) {
        // if the two element have the same name and namespace,
        if (element1.fName == element2.fName &&
                element1.fTargetNamespace == element2.fTargetNamespace) {
            return true;
        }

        // or if there is an element decl in element1's substitution group,
        // who has the same name/namespace with element2
        XSElementDecl[] subGroup = sgHandler.getSubstitutionGroup(element1);
        for (int i = subGroup.length-1; i >= 0; i--) {
            if (subGroup[i].fName == element2.fName &&
                    subGroup[i].fTargetNamespace == element2.fTargetNamespace) {
                return true;
            }
        }

        // or if there is an element decl in element2's substitution group,
        // who has the same name/namespace with element1
        subGroup = sgHandler.getSubstitutionGroup(element2);
        for (int i = subGroup.length-1; i >= 0; i--) {
            if (subGroup[i].fName == element1.fName &&
                    subGroup[i].fTargetNamespace == element1.fTargetNamespace) {
                return true;
            }
        }

        return false;
    }

    // to check whether an element overlaps with a wildcard,
    // as defined in constraint UPA
    public static boolean overlapUPA(XSElementDecl element,
            XSWildcardDecl wildcard,
            SubstitutionGroupHandler sgHandler) {
        // if the wildcard allows the element
        if (wildcard.allowNamespace(element.fTargetNamespace))
            return true;

        // or if the wildcard allows any element in the substitution group
        XSElementDecl[] subGroup = sgHandler.getSubstitutionGroup(element);
        for (int i = subGroup.length-1; i >= 0; i--) {
            if (wildcard.allowNamespace(subGroup[i].fTargetNamespace))
                return true;
        }

        return false;
    }

    public static boolean overlapUPA(XSWildcardDecl wildcard1,
            XSWildcardDecl wildcard2) {
        // if the intersection of the two wildcard is not empty list
        XSWildcardDecl intersect = wildcard1.performIntersectionWith(wildcard2, wildcard1.fProcessContents);
        if (intersect == null ||
                intersect.fType != XSWildcardDecl.NSCONSTRAINT_LIST ||
                intersect.fNamespaceList.length != 0) {
            return true;
        }

        return false;
    }

    // call one of the above methods according to the type of decls
    public static boolean overlapUPA(Object decl1, Object decl2,
            SubstitutionGroupHandler sgHandler) {
        if (decl1 instanceof XSElementDecl) {
            if (decl2 instanceof XSElementDecl) {
                return overlapUPA((XSElementDecl)decl1,
                        (XSElementDecl)decl2,
                        sgHandler);
            }
            else {
                return overlapUPA((XSElementDecl)decl1,
                        (XSWildcardDecl)decl2,
                        sgHandler);
            }
        }
        else {
            if (decl2 instanceof XSElementDecl) {
                return overlapUPA((XSElementDecl)decl2,
                        (XSWildcardDecl)decl1,
                        sgHandler);
            }
            else {
                return overlapUPA((XSWildcardDecl)decl1,
                        (XSWildcardDecl)decl2);
            }
        }
    }

} // class XSContraints