/// <summary>
        /// Create an XmlQueryType from an Xsd simple type (where variety can be Atomic, List, or Union).
        /// </summary>
        /// <param name="schemaType">the simple Xsd schema type of the atomic value</param>
        /// <param name="isStrict">true if the dynamic type is guaranteed to match the static type exactly</param>
        /// <returns>the atomic value type</returns>
        public static XmlQueryType Type(XmlSchemaSimpleType schemaType, bool isStrict) {
            if (schemaType.Datatype.Variety == XmlSchemaDatatypeVariety.Atomic) {
                // We must special-case xs:anySimpleType because it is broken in Xsd and is sometimes treated as
                // an atomic value and sometimes as a list value.  In XQuery, it always maps to xdt:anyAtomicType*.
                if (schemaType == DatatypeImplementation.AnySimpleType)
                    return AnyAtomicTypeS;

                return ItemType.Create(schemaType, isStrict);
            }

            // Skip restrictions. It is safe to do that because this is a list or union, so it's not a build in type
            while (schemaType.DerivedBy == XmlSchemaDerivationMethod.Restriction)
                schemaType = (XmlSchemaSimpleType) schemaType.BaseXmlSchemaType;

            // Convert Xsd list
            if (schemaType.DerivedBy == XmlSchemaDerivationMethod.List)
                return PrimeProduct(Type(((XmlSchemaSimpleTypeList) schemaType.Content).BaseItemType, isStrict), XmlQueryCardinality.ZeroOrMore);

            // Convert Xsd union
            Debug.Assert(schemaType.DerivedBy == XmlSchemaDerivationMethod.Union);
            XmlSchemaSimpleType[] baseMemberTypes = ((XmlSchemaSimpleTypeUnion) schemaType.Content).BaseMemberTypes;
            XmlQueryType[] queryMemberTypes = new XmlQueryType[baseMemberTypes.Length];

            for (int i = 0; i < baseMemberTypes.Length; i++)
                queryMemberTypes[i] = Type(baseMemberTypes[i], isStrict);

            return Choice(queryMemberTypes);
        }

        //-----------------------------------------------
        // Constructor
        //-----------------------------------------------

        /// <summary>
        /// Construct a node
        /// </summary>
        public QilFunction(QilNodeType nodeType, QilNode arguments, QilNode definition, QilNode sideEffects, XmlQueryType resultType)
            : base(nodeType) {
            this.arguments = arguments;
            this.definition = definition;
            this.sideEffects = sideEffects;
            this.xmlType = resultType;
        }

        //-----------------------------------------------
        // QilReplaceVisitor methods
        //-----------------------------------------------

        /// <summary>
        /// Once children have been replaced, the Xml type is recalculated.
        /// </summary>
        protected virtual void RecalculateType(QilNode node, XmlQueryType oldType) {
            XmlQueryType newType;

            newType = f.TypeChecker.Check(node);

            // Note the use of AtMost to account for cases when folding of Error nodes in the graph cause
            // cardinality to be recalculated.
            // For example, (Sequence (TextCtor (Error "error")) (Int32 1)) => (Sequence (Error "error") (Int32 1))
            // In this case, cardinality has gone from More to One
            Debug.Assert(newType.IsSubtypeOf(XmlQueryTypeFactory.AtMost(oldType, oldType.Cardinality)), "Replace shouldn't relax original type");

            node.XmlType = newType;
        }

        /// <summary>
        /// Return the default Clr data type that will be used to store instances of the QilNode's type.
        /// </summary>
        public static Type GetStorageType(XmlQueryType qyTyp) {
            Type storageType;

            if (qyTyp.IsSingleton) {
                storageType = TypeCodeToStorage[(int) qyTyp.TypeCode];

                // Non-strict items must store the type along with the value, so use XPathItem
                if (!qyTyp.IsStrict && storageType != typeof(XPathNavigator))
                    return typeof(XPathItem);
            }
            else {
                storageType = TypeCodeToCachedStorage[(int) qyTyp.TypeCode];

                // Non-strict items must store the type along with the value, so use XPathItem
                if (!qyTyp.IsStrict && storageType != typeof(IList<XPathNavigator>))
                    return typeof(IList<XPathItem>);
            }

            return storageType;
        }

        private XmlQueryType DistinctType(XmlQueryType type) {
            if (type.Cardinality == XmlQueryCardinality.More)
                return XmlQueryTypeFactory.PrimeProduct(type, XmlQueryCardinality.OneOrMore);

            if (type.Cardinality == XmlQueryCardinality.NotOne)
                return XmlQueryTypeFactory.PrimeProduct(type, XmlQueryCardinality.ZeroOrMore);

            return type;
        }

 /// <summary>
 ///  Descend though the content model
 /// </summary>
 private XmlQueryCardinality AddChildParticle(List<XmlQueryType> list, XmlSchemaParticle particle, XmlQueryType filter) {
     XmlQueryCardinality card = XmlQueryCardinality.None;
     XmlSchemaElement element = particle as XmlSchemaElement;
     if (element != null) {
         // Single element
         card = AddFilteredPrime(list, CreateElementType(element), filter);
     }
     else {
         // XmlSchemaAny matches more then one element
         XmlSchemaAny any = particle as XmlSchemaAny;
         if (any != null) {
             XmlSchemaType elementSchemaType = any.ProcessContentsCorrect == XmlSchemaContentProcessing.Skip ? XmlSchemaComplexType.UntypedAnyType : XmlSchemaComplexType.AnyType;
             switch (any.NamespaceList.Type) {
             case NamespaceList.ListType.Set:
                 // Add a separate type for each namespace in the list
                 foreach (string ns in any.NamespaceList.Enumerate) {
                     card |= AddFilteredPrime(list, CreateElementType(ns, false, elementSchemaType), filter);
                 }
                 break;
             case NamespaceList.ListType.Other:
                 // Add ##other
                 card = AddFilteredPrime(list, CreateElementType(any.NamespaceList.Excluded, true, elementSchemaType), filter);
                 break;
             case NamespaceList.ListType.Any:
             default:
                 // Add ##any
                 card = AddFilteredPrime(list, any.ProcessContentsCorrect == XmlSchemaContentProcessing.Skip ? UntypedElement : Element, filter);
                 break;
             }
         }
         else {
             //  recurse into particle group
             XmlSchemaGroupBase group = particle as XmlSchemaGroupBase;
             if (group.Items.Count != 0) {
                 if (particle is XmlSchemaChoice) {
                     foreach (XmlSchemaParticle p in group.Items) {
                         card |= AddChildParticle(list, p, filter);
                     }
                 }
                 else { // Sequence and  All
                     foreach (XmlSchemaParticle p in group.Items) {
                         card += AddChildParticle(list, p, filter);
                     }
                 }
             }
         }
     }
     return card * CardinalityOfParticle(particle);
 }

 private void CheckXmlType(QilNode node, XmlQueryType xmlType) {
     Check(node.XmlType.IsSubtypeOf(xmlType), node, "Node's type " + node.XmlType + " is not a subtype of " + xmlType);
 }

 public QilNode XsltInvokeEarlyBound(QilNode name, MethodInfo d, XmlQueryType t, IList<QilNode> args) {
     QilList list = f.ActualParameterList();
     list.Add(args);
     return f.XsltInvokeEarlyBound(name, f.LiteralObject(d), list, t);
 }

        /// <summary>
        /// Each XmlQueryType has multiple legal CLR representations.  Ensure that all items returned by this iterator are in
        /// the Clr representation specified by "storageTypeDest".
        /// </summary>
        public void EnsureItemStorageType(XmlQueryType xmlType, Type storageTypeDest) {
            // If source type = destination type, then done
            if (this.storage.ItemStorageType == storageTypeDest)
                goto SetStorageType;

            Debug.Assert(this.storage.ItemStorageType == typeof(XPathItem) || storageTypeDest == typeof(XPathItem),
                         "EnsureItemStorageType must convert to or from Item");

            // If items are cached,
            if (this.storage.IsCached) {
                // Check for special case of IList<XPathNavigator> -> IList<XPathItem>
                if (this.storage.ItemStorageType == typeof(XPathNavigator)) {
                    EnsureStack();
                    this.helper.Call(XmlILMethods.NavsToItems);
                    goto SetStorageType;
                }

                // Check for special case of IList<XPathItem> -> IList<XPathNavigator>
                if (storageTypeDest == typeof(XPathNavigator)) {
                    EnsureStack();
                    this.helper.Call(XmlILMethods.ItemsToNavs);
                    goto SetStorageType;
                }
            }

            // Iterate over each item, and convert each to the destination type
            EnsureStackNoCache();

            // If source type is Item,
            if (this.storage.ItemStorageType == typeof(XPathItem)) {
                // Then downcast to Navigator
                if (storageTypeDest == typeof(XPathNavigator)) {
                    this.helper.Emit(OpCodes.Castclass, typeof(XPathNavigator));
                }
                else {
                    // Call ValueAs methods for atomic types
                    this.helper.CallValueAs(storageTypeDest);
                }
                goto SetStorageType;
            }
            else if (this.storage.ItemStorageType == typeof(XPathNavigator)) {
                // No-op if converting from XPathNavigator to XPathItem
                Debug.Assert(storageTypeDest == typeof(XPathItem), "Must be converting from XPathNavigator to XPathItem");
                goto SetStorageType;
            }

            // Destination type must be item, so generate code to create an XmlAtomicValue
            this.helper.LoadInteger(this.helper.StaticData.DeclareXmlType(xmlType));
            this.helper.LoadQueryRuntime();
            this.helper.Call(XmlILMethods.StorageMethods[this.storage.ItemStorageType].ToAtomicValue);

        SetStorageType:
            this.storage = this.storage.ToStorageType(storageTypeDest);
        }

 //-----------------------------------------------
 // function definition and invocation
 //-----------------------------------------------
 public QilFunction Function(QilList args, QilNode sideEffects, XmlQueryType resultType) {
     Debug.Assert(args.NodeType == QilNodeType.FormalParameterList);
     return f.Function(args, sideEffects, resultType);
 }

 //-----------------------------------------------
 // Type operators
 //-----------------------------------------------
 public QilNode TypeAssert(QilNode expr, XmlQueryType t) {
     return f.TypeAssert(expr, t);
 }

 private XmlQueryCardinality AddElementOrTextDescendants(List<XmlQueryType> list,
     Dictionary<XmlQualifiedName, XmlQueryCardinality> allTypes, XmlSchemaType sourceSchemaType, XmlQueryType filter) {
     XmlQueryCardinality card = XmlQueryCardinality.None;
     if (sourceSchemaType == XmlSchemaComplexType.UntypedAnyType) {
         card = AddFilteredPrime(list, UntypedElement, filter) * XmlQueryCardinality.ZeroOrMore;
         card += AddFilteredPrime(list, Text, filter);
     }
     else if (sourceSchemaType.Datatype != null) {
         // Text is the only child node simple content of complext type
         card = AddFilteredPrime(list, Text, filter, true) * XmlQueryCardinality.ZeroOrOne;
     }
     else {
         // Complex content
         XmlSchemaComplexType complexType = (XmlSchemaComplexType)sourceSchemaType;
         if (complexType.QualifiedName.IsEmpty || !allTypes.TryGetValue(complexType.QualifiedName, out card)) {
             allTypes[complexType.QualifiedName] = XmlQueryCardinality.ZeroOrMore; // take care of left recursion
             card = AddDescendantParticle(list, allTypes, complexType.ContentTypeParticle, filter);
             allTypes[complexType.QualifiedName] = card;  //set correct card
             if (complexType.ContentType == XmlSchemaContentType.Mixed) {
                 card += AddFilteredPrime(list, Text, filter);
             }
         }
     }
     return card;
 }

 /// <summary>
 /// Construct the union of two XmlQueryTypes
 /// </summary>
 /// <param name="left">the left type</param>
 /// <param name="right">the right type</param>
 /// <returns>the union type</returns>
 public static XmlQueryType Choice(XmlQueryType left, XmlQueryType right) {
     return SequenceType.Create(ChoiceType.Create(PrimeChoice(new List<XmlQueryType>(left), right)), left.Cardinality | right.Cardinality);
 }

        /// <summary>
        /// Adds itemType to a union. Returns false if new item is a subtype of one of the types in the list.
        /// </summary>
        private static void AddItemToChoice(List<XmlQueryType> accumulator, XmlQueryType itemType) {
            Debug.Assert(itemType.IsSingleton, "All types should be prime.");

            bool addToList = true;
            for (int i = 0; i < accumulator.Count; i++) {
                // If new prime is a subtype of existing prime, don't add it to the union
                if (itemType.IsSubtypeOf(accumulator[i])) {
                    return;
                }

                // If new prime is a subtype of existing prime, then replace the existing prime with new prime
                if (accumulator[i].IsSubtypeOf(itemType)) {
                    if (addToList) {
                        addToList = false;
                        accumulator[i] = itemType;
                    }
                    else {
                        accumulator.RemoveAt(i);
                        i --;
                    }
                }
            }

            if (addToList) {
                accumulator.Add(itemType);
            }
        }

            /// <summary>
            /// Construct arrays of built-in types.
            /// </summary>
            static ItemType() {
            #if DEBUG
                Array arrEnum = Enum.GetValues(typeof(XmlTypeCode));
                Debug.Assert((XmlTypeCode) arrEnum.GetValue(arrEnum.Length - 1) == XmlTypeCode.DayTimeDuration,
                             "DayTimeDuration is no longer the last item in XmlTypeCode.  This code expects it to be.");
            #endif

                int typeCount = (int) XmlTypeCode.DayTimeDuration + 1;

                BuiltInItemTypes = new XmlQueryType[typeCount];
                BuiltInItemTypesStrict = new XmlQueryType[typeCount];

                for (int i = 0; i < typeCount; i++) {
                    XmlTypeCode typeCode = (XmlTypeCode)i;

                    switch ((XmlTypeCode) i) {
                        case XmlTypeCode.None:
                            BuiltInItemTypes[i] = ChoiceType.None;
                            BuiltInItemTypesStrict[i] = ChoiceType.None;
                            continue;

                        case XmlTypeCode.Item:
                        case XmlTypeCode.Node:
                            BuiltInItemTypes[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, XmlSchemaComplexType.AnyType, false, false, false);
                            BuiltInItemTypesStrict[i] = BuiltInItemTypes[i];
                            break;

                        case XmlTypeCode.Document:
                        case XmlTypeCode.Element:
                        case XmlTypeCode.Namespace:
                        case XmlTypeCode.ProcessingInstruction:
                        case XmlTypeCode.Comment:
                        case XmlTypeCode.Text:
                            BuiltInItemTypes[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, XmlSchemaComplexType.AnyType, false, false, true);
                            BuiltInItemTypesStrict[i] = BuiltInItemTypes[i];
                            break;

                        case XmlTypeCode.Attribute:
                            BuiltInItemTypes[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, DatatypeImplementation.AnySimpleType, false, false, true);
                            BuiltInItemTypesStrict[i] = BuiltInItemTypes[i];
                            break;

                        case XmlTypeCode.AnyAtomicType:
                            BuiltInItemTypes[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, DatatypeImplementation.AnyAtomicType, false, false, true);
                            BuiltInItemTypesStrict[i] = BuiltInItemTypes[i];
                            break;

                        case XmlTypeCode.UntypedAtomic:
                            // xdt:untypedAtomic is sealed, and therefore always strict
                            BuiltInItemTypes[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, DatatypeImplementation.UntypedAtomicType, false, true, true);
                            BuiltInItemTypesStrict[i] = BuiltInItemTypes[i];
                            break;

                        default:
                            XmlSchemaType builtInType = XmlSchemaType.GetBuiltInSimpleType(typeCode);
                            BuiltInItemTypes[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, builtInType, false, false, true);
                            BuiltInItemTypesStrict[i] = new ItemType(typeCode, XmlQualifiedNameTest.Wildcard, builtInType, false, true, true);
                            break;
                    }
                }

                UntypedDocument = new ItemType(XmlTypeCode.Document, XmlQualifiedNameTest.Wildcard, XmlSchemaComplexType.UntypedAnyType, false, false, true);
                UntypedElement = new ItemType(XmlTypeCode.Element, XmlQualifiedNameTest.Wildcard, XmlSchemaComplexType.UntypedAnyType, false, false, true);
                UntypedAttribute = new ItemType(XmlTypeCode.Attribute, XmlQualifiedNameTest.Wildcard, DatatypeImplementation.UntypedAtomicType, false, false, true);
                NodeNotRtf = new ItemType(XmlTypeCode.Node, XmlQualifiedNameTest.Wildcard, XmlSchemaComplexType.AnyType, false, false, true);

                SpecialBuiltInItemTypes = new XmlQueryType[4] { UntypedDocument, UntypedElement, UntypedAttribute, NodeNotRtf };
            }

        /// <summary>
        /// Construct the intersection of two lists of prime XmlQueryTypes.
        /// </summary>
        private XmlQueryType IntersectItemTypes(XmlQueryType left, XmlQueryType right) {
            Debug.Assert(left.Count == 1 && left.IsSingleton, "left should be an item");
            Debug.Assert(right.Count == 1 && right.IsSingleton, "right should be an item");
            if (left.TypeCode == right.TypeCode && (left.NodeKinds & (XmlNodeKindFlags.Document | XmlNodeKindFlags.Element | XmlNodeKindFlags.Attribute)) != 0) {
                if (left.TypeCode == XmlTypeCode.Node) {
                    return left;
                }
                // Intersect name tests
                XmlQualifiedNameTest nameTest = left.NameTest.Intersect(right.NameTest);

                // Intersect types
                XmlSchemaType type = XmlSchemaType.IsDerivedFrom(left.SchemaType, right.SchemaType, /* except:*/XmlSchemaDerivationMethod.Empty) ? left.SchemaType :
                    XmlSchemaType.IsDerivedFrom(right.SchemaType, left.SchemaType, /* except:*/XmlSchemaDerivationMethod.Empty) ? right.SchemaType : null;
                bool isNillable = left.IsNillable && right.IsNillable;

                if ((object)nameTest == (object)left.NameTest && type == left.SchemaType && isNillable == left.IsNillable) {
                    // left is a subtype of right return left
                    return left;
                }
                else if ((object)nameTest == (object)right.NameTest && type == right.SchemaType && isNillable == right.IsNillable) {
                    // right is a subtype of left return right
                    return right;
                }
                else if (nameTest != null && type != null) {
                    // create a new type
                    return ItemType.Create(left.TypeCode, nameTest, type, isNillable);
                }
            }
            else if (left.IsSubtypeOf(right)) {
                // left is a subset of right, so left is in the intersection
                return left;
            }
            else if (right.IsSubtypeOf(left)) {
                // right is a subset of left, so right is in the intersection
                return right;
            }
            return None;
        }

        private XmlQueryCardinality AddFilteredPrime(List<XmlQueryType> list, XmlQueryType source, XmlQueryType filter, bool forseSingle) {
            Debug.Assert(source.IsNode && source.IsSingleton);
            Debug.Assert(filter.IsNode && filter.IsSingleton);

            // Intersect types
            XmlQueryType intersection = IntersectItemTypes(source, filter);
            if ((object)intersection == (object)None) {
                return XmlQueryCardinality.Zero;
            }
            AddItemToChoice(list, intersection);
            // In the case of forseSingle - filtering all nodes behave as singletones
            XmlTypeCode typeCode = (forseSingle ? XmlTypeCode.Node : intersection.TypeCode);
            switch (typeCode) {
            case XmlTypeCode.Node:
            case XmlTypeCode.Document:
            case XmlTypeCode.Element:
                // Filter can result in empty sequence if filter is not wider then source
                if (intersection == source)
                    return XmlQueryCardinality.One;
                else
                    return  XmlQueryCardinality.ZeroOrOne;

            case XmlTypeCode.Attribute:
                    // wildcard attribute matches more then one node
                if (!intersection.NameTest.IsSingleName)
                    return XmlQueryCardinality.ZeroOrMore;
                else if (intersection == source)
                    return XmlQueryCardinality.One;
                else
                    return  XmlQueryCardinality.ZeroOrOne;
            case XmlTypeCode.Comment:
            case XmlTypeCode.Text:
            case XmlTypeCode.ProcessingInstruction:
            case XmlTypeCode.Namespace:
                return XmlQueryCardinality.ZeroOrMore;

            default:
                Debug.Assert(false);
                return XmlQueryCardinality.None;
            }
        }

 public QilParameter Parameter(XmlQueryType t) {
     return f.Parameter(t);
 }

            /// <summary>
            /// Create sequence type from prime and cardinality.
            /// </summary>
            public static XmlQueryType Create(XmlQueryType prime, XmlQueryCardinality card) {
                Debug.Assert(prime != null, "SequenceType can only modify the cardinality of a non-null XmlQueryType.");
                Debug.Assert(prime.IsSingleton, "Prime type must have cardinality one.");

                if (prime.TypeCode == XmlTypeCode.None) {
                    // If cardinality includes zero, then return (None, Zero), else return (None, None).
                    return XmlQueryCardinality.Zero <= card ? Zero : None;
                }

                // Normalize sequences with these cardinalities: None, Zero, One

                if (card == XmlQueryCardinality.None) {
                    return None;
                }
                else if (card == XmlQueryCardinality.Zero) {
                    return Zero;
                }
                else if (card == XmlQueryCardinality.One) {
                    return prime;
                }

                return new SequenceType(prime, card);
            }

 /// <summary>
 /// Private constructor.  Create methods should be used to create instances.
 /// </summary>
 private SequenceType(XmlQueryType prime, XmlQueryCardinality card) {
     this.prime = prime;
     this.card = card;
 }