content: /*
   *  This file is part of AndroidIDE.
   *
   *  AndroidIDE is free software: you can redistribute it and/or modify
   *  it under the terms of the GNU General Public License as published by
   *  the Free Software Foundation, either version 3 of the License, or
   *  (at your option) any later version.
   *
   *  AndroidIDE is distributed in the hope that it will be useful,
   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   *  GNU General Public License for more details.
   *
   *  You should have received a copy of the GNU General Public License
   *   along with AndroidIDE.  If not, see <https://www.gnu.org/licenses/>.
   */
  
  /*
   * 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 jaxp.sun.org.apache.xerces.internal.impl.xs;
  
  import java.util.Collections;
  import java.util.Comparator;
  import java.util.Vector;
  
  import jaxp.sun.org.apache.xerces.internal.impl.XMLErrorReporter;
  import jaxp.sun.org.apache.xerces.internal.impl.dv.InvalidDatatypeValueException;
  import jaxp.sun.org.apache.xerces.internal.impl.dv.ValidatedInfo;
  import jaxp.sun.org.apache.xerces.internal.impl.dv.ValidationContext;
  import jaxp.sun.org.apache.xerces.internal.impl.dv.XSSimpleType;
  import jaxp.sun.org.apache.xerces.internal.impl.xs.models.CMBuilder;
  import jaxp.sun.org.apache.xerces.internal.impl.xs.models.XSCMValidator;
  import jaxp.sun.org.apache.xerces.internal.impl.xs.util.SimpleLocator;
  import jaxp.sun.org.apache.xerces.internal.impl.xs.util.XSObjectListImpl;
  import jaxp.sun.org.apache.xerces.internal.util.SymbolHash;
  import jaxp.sun.org.apache.xerces.internal.xs.XSConstants;
  import jaxp.sun.org.apache.xerces.internal.xs.XSObjectList;
  import jaxp.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
  