/// <summary>
        /// Override the Visit method in order to scan for redundant namespaces and compute side-effect bit.
        /// </summary>
        protected override QilNode Visit(QilNode nd) {
            if (nd != null) {
                if (this[XmlILOptimization.EliminateNamespaceDecl]) {
                    // Eliminate redundant namespaces in the tree.  Don't perform the scan on an ElementCtor which
                    // has already been marked as having a redundant namespace.
                    switch (nd.NodeType) {
                        case QilNodeType.QilExpression:
                            // Perform namespace analysis on root expression (xmlns="" is in-scope for this expression)
                            this.nmspAnalyzer.Analyze(((QilExpression) nd).Root, true);
                            break;

                        case QilNodeType.ElementCtor:
                            if (!XmlILConstructInfo.Read(nd).IsNamespaceInScope)
                                this.nmspAnalyzer.Analyze(nd, false);
                            break;

                        case QilNodeType.DocumentCtor:
                            this.nmspAnalyzer.Analyze(nd, true);
                            break;
                    }
                }
            }

            // Continue visitation
            return base.Visit(nd);
        }

        //-----------------------------------------------
        // Convenience methods
        //-----------------------------------------------

        public QilExpression QilExpression(QilNode root, QilFactory factory)
        {
            QilExpression n = new QilExpression(QilNodeType.QilExpression, root, factory);
            n.XmlType = _typeCheck.CheckQilExpression(n);
            TraceNode(n);
            return n;
        }

 public QilNode InvokeElementAvailable(QilNode n)
 {
     CheckQName(n);
     return XsltInvokeEarlyBound(QName("element-available"),
         XsltMethods.ElementAvailable, T.BooleanX, new QilNode[] { n }
     );
 }

 public QilNode ConvertReletive2Absolute(QilNode node, QilNode fixup) {
     QilDepthChecker.Check(node);
     Debug.Assert(node  != null);
     Debug.Assert(fixup != null);
     this.fixup = fixup;
     return this.Visit(node);
 }

 public QilNode InvokeIsSameNodeSort(QilNode n1, QilNode n2) {
     CheckNodeNotRtf(n1);
     CheckNodeNotRtf(n2);
     return XsltInvokeEarlyBound(QName("is-same-node-sort"),
         XsltMethods.IsSameNodeSort, T.BooleanX, new QilNode[] { n1, n2 }
     );
 }

        //-----------------------------------------------
        // QilVisitor methods (manually generated)
        //-----------------------------------------------

        /// <summary>
        /// If a reference is passed to the Visit() method, it is assumed to be the definition.
        /// This method assumes it is a reference to a definition.
        /// For example, if a Let node is visited, is it the Let definition or a reference to the
        /// the Let definition?  Without context, it is ambiguous.  This method allows a caller
        /// to disambiguate.
        /// </summary>
        protected virtual QilNode VisitAssumeReference(QilNode expr)
        {
            if (expr is QilReference)
                return VisitReference(expr);

            return Visit(expr);
        }

        /// <summary>
        /// Visit all children of "parent", replacing each child with a copy of each child.
        /// </summary>
        protected override QilNode VisitChildren(QilNode parent)
        {
            // Visit children
            for (int i = 0; i < parent.Count; i++)
            {
                QilNode child = parent[i];

                // If child is a reference,
                if (IsReference(parent, i))
                {
                    // Visit the reference and substitute its copy
                    parent[i] = VisitReference(child);

                    // If no substutition found, then use original child
                    if (parent[i] == null)
                        parent[i] = child;
                }
                else
                {
                    // Otherwise, visit the node and substitute its copy
                    parent[i] = Visit(child);
                }
            }

            return parent;
        }

        /// <summary>
        /// Visit all children of "parent".  Take care to avoid circular visits.
        /// </summary>
        protected virtual bool IsReference(QilNode parent, int childNum) {
            QilNode child = parent[childNum];

            if (child != null) {
                switch (child.NodeType) {
                    case QilNodeType.For:
                    case QilNodeType.Let:
                    case QilNodeType.Parameter:
                        // Is this a reference or a definition?
                        switch (parent.NodeType) {
                            case QilNodeType.Loop:
                            case QilNodeType.Filter:
                            case QilNodeType.Sort:
                                // Second child of these node types is a reference; first child is a definition
                                return childNum == 1;

                            case QilNodeType.GlobalVariableList:
                            case QilNodeType.GlobalParameterList:
                            case QilNodeType.FormalParameterList:
                                // All children of definition lists are definitions
                                return false;
                        }

                        // All other cases are references
                        return true;

                    case QilNodeType.Function:
                        // If parent is an Invoke node, then visit a reference to the function
                        return parent.NodeType == QilNodeType.Invoke;
                }
            }

            return false;
        }

        //-----------------------------------------------
        // QilVisitor overrides
        //-----------------------------------------------

        /// <summary>
        /// Visit all children of "parent", replacing each child with a copy of each child.
        /// </summary>
        protected override QilNode VisitChildren(QilNode parent) {
            XmlQueryType oldParentType = parent.XmlType;
            bool recalcType = false;

            // Visit children
            for (int i = 0; i < parent.Count; i++) {
                QilNode oldChild = parent[i], newChild;
                XmlQueryType oldChildType = oldChild != null ? oldChild.XmlType : null;

                // Visit child
                if (IsReference(parent, i))
                    newChild = VisitReference(oldChild);
                else
                    newChild = Visit(oldChild);

                // Only replace child and recalculate type if oldChild != newChild or oldChild.XmlType != newChild.XmlType
                if ((object) oldChild != (object) newChild || (newChild != null && (object) oldChildType != (object) newChild.XmlType)) {
                    recalcType = true;
                    parent[i] = newChild;
                }
            }

            if (recalcType)
                RecalculateType(parent, oldParentType);

            return parent;
        }

 public QilNode Replace(QilNode expr, QilReference lookFor, QilReference replaceBy)
 {
     QilDepthChecker.Check(expr);
     _lookFor = lookFor;
     _replaceBy = replaceBy;
     return VisitAssumeReference(expr);
 }

 public QilNode InvokeSystemProperty(QilNode n)
 {
     CheckQName(n);
     return XsltInvokeEarlyBound(QName("system-property"),
         XsltMethods.SystemProperty, T.Choice(T.DoubleX, T.StringX), new QilNode[] { n }
     );
 }

 public bool IsAnyType(QilNode n)
 {
     XmlQueryType xt = n.XmlType;
     bool result = !(xt.IsStrict || xt.IsNode);
     Debug.Assert(result == (xt.TypeCode == XmlTypeCode.Item || xt.TypeCode == XmlTypeCode.AnyAtomicType), "What else can it be?");
     return result;
 }

 /// <summary>
 /// Find the replacement for a node
 /// </summary>
 /// <param name="n">the node to replace</param>
 /// <returns>null if no replacement is found</returns>
 public QilNode FindReplacement(QilNode n) {
     Debug.Assert(s.Count % 2 == 0);
     for (int i = s.Count-2; i >= 0; i-=2)
         if (s[i] == n)
             return (QilNode)s[i+1];
     return null;
 }

        /// <summary>
        /// Called at the end of Visit().
        /// </summary>
        protected virtual void AfterVisit(QilNode node) {
            QilExpression qil;

            switch (node.NodeType) {
                case QilNodeType.QilExpression:
                    // Remove all global functions, variables, and parameters from scope
                    qil = (QilExpression) node;
                    foreach (QilNode func in qil.FunctionList) EndScope(func);
                    foreach (QilNode var in qil.GlobalVariableList) EndScope(var);
                    foreach (QilNode param in qil.GlobalParameterList) EndScope(param);
                    break;

                case QilNodeType.Function:
                    // Remove all formal arguments from scope
                    foreach (QilNode arg in ((QilFunction) node).Arguments) EndScope(arg);
                    break;

                case QilNodeType.Loop:
                case QilNodeType.Filter:
                case QilNodeType.Sort:
                    // Remove loop iterator in scope
                    EndScope(((QilLoop) node).Variable);
                    break;
            }
        }

        //-----------------------------------------------
        // 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;
        }

 public virtual QilNode EndBuild(QilNode result) {
     Debug.Assert(inTheBuild, "StartBuild() wasn't called");
     if (result == null) {
         // Special door to clean builder state in exception handlers
     }
     inTheBuild = false;
     return result;
 }

        /// <summary>
        /// Get OptimizerPatterns annotation for the specified node.  Lazily create if necessary.
        /// </summary>
        public static OptimizerPatterns Read(QilNode nd)
        {
            XmlILAnnotation ann = nd.Annotation as XmlILAnnotation;
            OptimizerPatterns optPatt = (ann != null) ? ann.Patterns : null;

            if (optPatt == null)
            {
                if (!nd.XmlType.MaybeMany)
                {
                    // Expressions with ZeroOrOne cardinality should always report IsDocOrderDistinct and NoContainedNodes
                    if (s_zeroOrOneDefault == null)
                    {
                        optPatt = new OptimizerPatterns();
                        optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct);
                        optPatt.AddPattern(OptimizerPatternName.SameDepth);
                        optPatt._isReadOnly = true;

                        s_zeroOrOneDefault = optPatt;
                    }
                    else
                    {
                        optPatt = s_zeroOrOneDefault;
                    }
                }
                else if (nd.XmlType.IsDod)
                {
                    if (s_dodDefault == null)
                    {
                        optPatt = new OptimizerPatterns();
                        optPatt.AddPattern(OptimizerPatternName.IsDocOrderDistinct);
                        optPatt._isReadOnly = true;

                        s_dodDefault = optPatt;
                    }
                    else
                    {
                        optPatt = s_dodDefault;
                    }
                }
                else
                {
                    if (s_maybeManyDefault == null)
                    {
                        optPatt = new OptimizerPatterns();
                        optPatt._isReadOnly = true;

                        s_maybeManyDefault = optPatt;
                    }
                    else
                    {
                        optPatt = s_maybeManyDefault;
                    }
                }
            }

            return optPatt;
        }

        /// <summary>
        /// Recursively analyze the definition of a function.
        /// </summary>
        private static void AnalyzeDefinition(QilNode nd)
        {
            Debug.Assert(XmlILConstructInfo.Read(nd).PushToWriterLast,
                         "Only need to analyze expressions which will be compiled in push mode.");

            switch (nd.NodeType)
            {
                case QilNodeType.Invoke:
                    // Invoke node can either be compiled as IteratorThenWriter, or Writer.
                    // Since IteratorThenWriter involves caching the results of the function call
                    // and iterating over them, .tailcall cannot be used
                    if (XmlILConstructInfo.Read(nd).ConstructMethod == XmlILConstructMethod.Writer)
                        OptimizerPatterns.Write(nd).AddPattern(OptimizerPatternName.TailCall);
                    break;

                case QilNodeType.Loop:
                    {
                        // Recursively analyze Loop return value
                        QilLoop ndLoop = (QilLoop)nd;
                        if (ndLoop.Variable.NodeType == QilNodeType.Let || !ndLoop.Variable.Binding.XmlType.MaybeMany)
                            AnalyzeDefinition(ndLoop.Body);
                        break;
                    }

                case QilNodeType.Sequence:
                    {
                        // Recursively analyze last expression in Sequence
                        QilList ndSeq = (QilList)nd;
                        if (ndSeq.Count > 0)
                            AnalyzeDefinition(ndSeq[ndSeq.Count - 1]);
                        break;
                    }

                case QilNodeType.Choice:
                    {
                        // Recursively analyze Choice branches
                        QilChoice ndChoice = (QilChoice)nd;
                        for (int i = 0; i < ndChoice.Branches.Count; i++)
                            AnalyzeDefinition(ndChoice.Branches[i]);
                        break;
                    }

                case QilNodeType.Conditional:
                    {
                        // Recursively analyze Conditional branches
                        QilTernary ndCond = (QilTernary)nd;
                        AnalyzeDefinition(ndCond.Center);
                        AnalyzeDefinition(ndCond.Right);
                        break;
                    }

                case QilNodeType.Nop:
                    AnalyzeDefinition(((QilUnary)nd).Child);
                    break;
            }
        }

        /// <summary>
        /// Visit all children of "parent".  By default, take care to avoid circular visits.
        /// </summary>
        protected virtual QilNode VisitChildren(QilNode parent) {
            for (int i = 0; i < parent.Count; i++) {
                // If child is a reference, then call VisitReference instead of Visit in order to avoid circular visits.
                if (IsReference(parent, i))
                    VisitReference(parent[i]);
                else
                    Visit(parent[i]);
            }

            return parent;
        }

 // transparantly passing through Union and DocOrder
 protected override QilNode Visit(QilNode n) {
     if (
         n.NodeType == QilNodeType.Union ||
         n.NodeType == QilNodeType.DocOrderDistinct ||
         n.NodeType == QilNodeType.Filter ||
         n.NodeType == QilNodeType.Loop
     ) {
         return base.Visit(n);
     }
     return n;
 }