path: root/mcs/class/referencesource/System.Xml/System/Xml/Cache/XPathNodeHelper.cs

//------------------------------------------------------------------------------
// <copyright file="XPathNodeHelper.cs" company="Microsoft">
//     Copyright (c) Microsoft Corporation.  All rights reserved.
// </copyright>                                                                
// <owner current="true" primary="true">[....]</owner>
//------------------------------------------------------------------------------
using System;
using System.Diagnostics;
using System.Text;
using System.Xml;
using System.Xml.XPath;
using System.Xml.Schema;

namespace MS.Internal.Xml.Cache {

    /// <summary>
    /// Library of XPathNode helper routines.
    /// </summary>
    internal abstract class XPathNodeHelper {

        /// <summary>
        /// Return chain of namespace nodes.  If specified node has no local namespaces, then 0 will be
        /// returned.  Otherwise, the first node in the chain is guaranteed to be a local namespace (its
        /// parent is this node).  Subsequent nodes may not have the same node as parent, so the caller will
        /// need to test the parent in order to terminate a search that processes only local namespaces.
        /// </summary>
        public static int GetLocalNamespaces(XPathNode[] pageElem, int idxElem, out XPathNode[] pageNmsp) {
            if (pageElem[idxElem].HasNamespaceDecls) {
                // Only elements have namespace nodes
                Debug.Assert(pageElem[idxElem].NodeType == XPathNodeType.Element);
                return pageElem[idxElem].Document.LookupNamespaces(pageElem, idxElem, out pageNmsp);
            }
            pageNmsp = null;
            return 0;
        }

        /// <summary>
        /// Return chain of in-scope namespace nodes for nodes of type Element.  Nodes in the chain might not
        /// have this element as their parent.  Since the xmlns:xml namespace node is always in scope, this
        /// method will never return 0 if the specified node is an element.
        /// </summary>
        public static int GetInScopeNamespaces(XPathNode[] pageElem, int idxElem, out XPathNode[] pageNmsp) {
            XPathDocument doc;

            // Only elements have namespace nodes
            if (pageElem[idxElem].NodeType == XPathNodeType.Element) {
                doc = pageElem[idxElem].Document;

                // Walk ancestors, looking for an ancestor that has at least one namespace declaration
                while (!pageElem[idxElem].HasNamespaceDecls) {
                    idxElem = pageElem[idxElem].GetParent(out pageElem);
                    if (idxElem == 0) {
                        // There are no namespace nodes declared on ancestors, so return xmlns:xml node
                        return doc.GetXmlNamespaceNode(out pageNmsp);
                    }
                }
                // Return chain of in-scope namespace nodes
                return doc.LookupNamespaces(pageElem, idxElem, out pageNmsp);
            }
            pageNmsp = null;
            return 0;
        }

        /// <summary>
        /// Return the first attribute of the specified node.  If no attribute exist, do not
        /// set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetFirstAttribute(ref XPathNode[] pageNode, ref int idxNode) {
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            if (pageNode[idxNode].HasAttribute) {
                GetChild(ref pageNode, ref idxNode);
                Debug.Assert(pageNode[idxNode].NodeType == XPathNodeType.Attribute);
                return true;
            }
            return false;
        }

        /// <summary>
        /// Return the next attribute sibling of the specified node.  If the node is not itself an
        /// attribute, or if there are no siblings, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetNextAttribute(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] page;
            int idx;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            idx = pageNode[idxNode].GetSibling(out page);
            if (idx != 0 && page[idx].NodeType == XPathNodeType.Attribute) {
                pageNode = page;
                idxNode = idx;
                return true;
            }
            return false;
        }

        /// <summary>
        /// Return the first content-typed child of the specified node.  If the node has no children, or
        /// if the node is not content-typed, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetContentChild(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            if (page[idx].HasContentChild) {
                GetChild(ref page, ref idx);

                // Skip past attribute children
                while (page[idx].NodeType == XPathNodeType.Attribute) {
                    idx = page[idx].GetSibling(out page);
                    Debug.Assert(idx != 0);
                }

                pageNode = page;
                idxNode = idx;
                return true;
            }
            return false;
        }

        /// <summary>
        /// Return the next content-typed sibling of the specified node.  If the node has no siblings, or
        /// if the node is not content-typed, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetContentSibling(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            if (!page[idx].IsAttrNmsp) {
                idx = page[idx].GetSibling(out page);
                if (idx != 0) {
                    pageNode = page;
                    idxNode = idx;
                    return true;
                }
            }
            return false;
        }

        /// <summary>
        /// Return the parent of the specified node.  If the node has no parent, do not set pageNode
        /// or idxNode and return false.
        /// </summary>
        public static bool GetParent(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            idx = page[idx].GetParent(out page);
            if (idx != 0) {
                pageNode = page;
                idxNode = idx;
                return true;
            }
            return false;
        }

        /// <summary>
        /// Return a location integer that can be easily compared with other locations from the same document
        /// in order to determine the relative document order of two nodes.
        /// </summary>
        public static int GetLocation(XPathNode[] pageNode, int idxNode) {
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");
            Debug.Assert(idxNode <= UInt16.MaxValue);
            Debug.Assert(pageNode[0].PageInfo.PageNumber <= Int16.MaxValue);
            return (pageNode[0].PageInfo.PageNumber << 16) | idxNode;
        }

        /// <summary>
        /// Return the first element child of the specified node that has the specified name.  If no such child exists,
        /// then do not set pageNode or idxNode and return false.  Assume that the localName has been atomized with respect
        /// to this document's name table, but not the namespaceName.
        /// </summary>
        public static bool GetElementChild(ref XPathNode[] pageNode, ref int idxNode, string localName, string namespaceName) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            // Only check children if at least one element child exists
            if (page[idx].HasElementChild) {
                GetChild(ref page, ref idx);
                Debug.Assert(idx != 0);

                // Find element with specified localName and namespaceName
                do {
                    if (page[idx].ElementMatch(localName, namespaceName)) {
                        pageNode = page;
                        idxNode = idx;
                        return true;
                    }
                    idx = page[idx].GetSibling(out page);
                }
                while (idx != 0);
            }
            return false;
        }

        /// <summary>
        /// Return a following sibling element of the specified node that has the specified name.  If no such
        /// sibling exists, or if the node is not content-typed, then do not set pageNode or idxNode and
        /// return false.  Assume that the localName has been atomized with respect to this document's name table,
        /// but not the namespaceName.
        /// </summary>
        public static bool GetElementSibling(ref XPathNode[] pageNode, ref int idxNode, string localName, string namespaceName) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            // Elements should not be returned as "siblings" of attributes (namespaces don't link to elements, so don't need to check them)
            if (page[idx].NodeType != XPathNodeType.Attribute) {
                while (true) {
                    idx = page[idx].GetSibling(out page);

                    if (idx == 0)
                        break;

                    if (page[idx].ElementMatch(localName, namespaceName)) {
                        pageNode = page;
                        idxNode = idx;
                        return true;
                    }
                }
            }

            return false;
        }

        /// <summary>
        /// Return the first child of the specified node that has the specified type (must be a content type).  If no such
        /// child exists, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetContentChild(ref XPathNode[] pageNode, ref int idxNode, XPathNodeType typ) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            int mask;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            // Only check children if at least one content-typed child exists
            if (page[idx].HasContentChild) {
                mask = XPathNavigator.GetContentKindMask(typ);

                GetChild(ref page, ref idx);
                do {
                    if (((1 << (int) page[idx].NodeType) & mask) != 0) {
                        // Never return attributes, as Attribute is not a content type
                        if (typ == XPathNodeType.Attribute)
                            return false;

                        pageNode = page;
                        idxNode = idx;
                        return true;
                    }

                    idx = page[idx].GetSibling(out page);
                }
                while (idx != 0);
            }

            return false;
        }

        /// <summary>
        /// Return a following sibling of the specified node that has the specified type.  If no such
        /// sibling exists, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetContentSibling(ref XPathNode[] pageNode, ref int idxNode, XPathNodeType typ) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            int mask = XPathNavigator.GetContentKindMask(typ);
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            if (page[idx].NodeType != XPathNodeType.Attribute) {
                while (true) {
                    idx = page[idx].GetSibling(out page);

                    if (idx == 0)
                        break;

                    if (((1 << (int) page[idx].NodeType) & mask) != 0) {
                        Debug.Assert(typ != XPathNodeType.Attribute && typ != XPathNodeType.Namespace);
                        pageNode = page;
                        idxNode = idx;
                        return true;
                    }
                }
            }

            return false;
        }

        /// <summary>
        /// Return the first preceding sibling of the specified node.  If no such sibling exists, then do not set
        /// pageNode or idxNode and return false.
        /// </summary>
        public static bool GetPreviousContentSibling(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] pageParent = pageNode, pagePrec, pageAnc;
            int idxParent = idxNode, idxPrec, idxAnc;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");
            Debug.Assert(pageNode[idxNode].NodeType != XPathNodeType.Attribute);

            // Since nodes are laid out in document order on pages, the algorithm is:
            //   1. Get parent of current node
            //   2. If no parent, then there is no previous sibling, so return false
            //   3. Get node that immediately precedes the current node in document order
            //   4. If preceding node is parent, then there is no previous sibling, so return false
            //   5. Walk ancestors of preceding node, until parent of current node is found
            idxParent = pageParent[idxParent].GetParent(out pageParent);
            if (idxParent != 0) {
                idxPrec = idxNode - 1;
                if (idxPrec == 0) {
                    // Need to get previous page
                    pagePrec = pageNode[0].PageInfo.PreviousPage;
                    idxPrec = pagePrec.Length - 1;
                }
                else {
                    // Previous node is on the same page
                    pagePrec = pageNode;
                }

                // If parent node is previous node, then no previous sibling
                if (idxParent == idxPrec && pageParent == pagePrec)
                    return false;

                // Find child of parent node by walking ancestor chain
                pageAnc = pagePrec;
                idxAnc = idxPrec;
                do {
                    pagePrec = pageAnc;
                    idxPrec = idxAnc;
                    idxAnc = pageAnc[idxAnc].GetParent(out pageAnc);
                    Debug.Assert(idxAnc != 0 && pageAnc != null);
                }
                while (idxAnc != idxParent || pageAnc != pageParent);

                // We found the previous sibling, but if it's an attribute node, then return false
                if (pagePrec[idxPrec].NodeType != XPathNodeType.Attribute) {
                    pageNode = pagePrec;
                    idxNode = idxPrec;
                    return true;
                }
            }

            return false;
        }

        /// <summary>
        /// Return a previous sibling element of the specified node that has the specified name.  If no such
        /// sibling exists, or if the node is not content-typed, then do not set pageNode or idxNode and
        /// return false.  Assume that the localName has been atomized with respect to this document's name table,
        /// but not the namespaceName.
        /// </summary>
        public static bool GetPreviousElementSibling(ref XPathNode[] pageNode, ref int idxNode, string localName, string namespaceName) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            if (page[idx].NodeType != XPathNodeType.Attribute) {
                while (true) {
                    if (!GetPreviousContentSibling(ref page, ref idx))
                        break;

                    if (page[idx].ElementMatch(localName, namespaceName)) {
                        pageNode = page;
                        idxNode = idx;
                        return true;
                    }
                }
            }

            return false;
        }

        /// <summary>
        /// Return a previous sibling of the specified node that has the specified type.  If no such
        /// sibling exists, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetPreviousContentSibling(ref XPathNode[] pageNode, ref int idxNode, XPathNodeType typ) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            int mask = XPathNavigator.GetContentKindMask(typ);
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            while (true) {
                if (!GetPreviousContentSibling(ref page, ref idx))
                    break;

                if (((1 << (int) page[idx].NodeType) & mask) != 0) {
                    pageNode = page;
                    idxNode = idx;
                    return true;
                }
            }

            return false;
        }

        /// <summary>
        /// Return the attribute of the specified node that has the specified name.  If no such attribute exists,
        /// then do not set pageNode or idxNode and return false.  Assume that the localName has been atomized with respect
        /// to this document's name table, but not the namespaceName.
        /// </summary>
        public static bool GetAttribute(ref XPathNode[] pageNode, ref int idxNode, string localName, string namespaceName) {
            XPathNode[] page = pageNode;
            int idx = idxNode;
            Debug.Assert(pageNode != null && idxNode != 0, "Cannot pass null argument(s)");

            // Find attribute with specified localName and namespaceName
            if (page[idx].HasAttribute) {
                GetChild(ref page, ref idx);
                do {
                    if (page[idx].NameMatch(localName, namespaceName)) {
                        pageNode = page;
                        idxNode = idx;
                        return true;
                    }
                    idx = page[idx].GetSibling(out page);
                }
                while (idx != 0 && page[idx].NodeType == XPathNodeType.Attribute);
            }

            return false;
        }

        /// <summary>
        /// Get the next non-virtual (not collapsed text, not namespaces) node that follows the specified node in document order.
        /// If no such node exists, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetFollowing(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] page = pageNode;
            int idx = idxNode;

            do {
                // Next non-virtual node is in next slot within the page
                if (++idx < page[0].PageInfo.NodeCount) {
                    pageNode = page;
                    idxNode = idx;
                    return true;
                }

                // Otherwise, start at the beginning of the next page
                page = page[0].PageInfo.NextPage;
                idx = 0;
            }
            while (page != null);

            return false;
        }

        /// <summary>
        /// Get the next element node that:
        ///   1. Follows the current node in document order (includes descendants, unlike XPath following axis)
        ///   2. Precedes the ending node in document order (if pageEnd is null, then all following nodes in the document are considered)
        ///   3. Has the specified QName
        /// If no such element exists, then do not set pageCurrent or idxCurrent and return false.
        /// Assume that the localName has been atomized with respect to this document's name table, but not the namespaceName.
        /// </summary>
        public static bool GetElementFollowing(ref XPathNode[] pageCurrent, ref int idxCurrent, XPathNode[] pageEnd, int idxEnd, string localName, string namespaceName) {
            XPathNode[] page = pageCurrent;
            int idx = idxCurrent;
            Debug.Assert(pageCurrent != null && idxCurrent != 0, "Cannot pass null argument(s)");

            // If current node is an element having a matching name,
            if (page[idx].NodeType == XPathNodeType.Element && (object) page[idx].LocalName == (object) localName) {
                // Then follow similar element name pointers
                int idxPageEnd = 0;
                int idxPageCurrent;

                if (pageEnd != null) {
                    idxPageEnd = pageEnd[0].PageInfo.PageNumber;
                    idxPageCurrent = page[0].PageInfo.PageNumber;

                    // If ending node is <= starting node in document order, then scan to end of document
                    if (idxPageCurrent > idxPageEnd || (idxPageCurrent == idxPageEnd && idx >= idxEnd))
                        pageEnd = null;
                }

                while (true) {
                    idx = page[idx].GetSimilarElement(out page);

                    if (idx == 0)
                        break;

                    // Only scan to ending node
                    if (pageEnd != null) {
                        idxPageCurrent = page[0].PageInfo.PageNumber;
                        if (idxPageCurrent > idxPageEnd)
                            break;

                        if (idxPageCurrent == idxPageEnd && idx >= idxEnd)
                            break;
                    }

                    if ((object) page[idx].LocalName == (object) localName && page[idx].NamespaceUri == namespaceName)
                        goto FoundNode;
                }

                return false;
            }

            // Since nodes are laid out in document order on pages, scan them sequentially
            // rather than following links.
            idx++;
            do {
                if ((object) page == (object) pageEnd && idx <= idxEnd) {
                    // Only scan to termination point
                    while (idx != idxEnd) {
                        if (page[idx].ElementMatch(localName, namespaceName))
                            goto FoundNode;
                        idx++;
                    }
                    break;
                }
                else {
                    // Scan all nodes in the page
                    while (idx < page[0].PageInfo.NodeCount) {
                        if (page[idx].ElementMatch(localName, namespaceName))
                            goto FoundNode;
                        idx++;
                    }
                }

                page = page[0].PageInfo.NextPage;
                idx = 1;
            }
            while (page != null);

            return false;

        FoundNode:
            // Found match
            pageCurrent = page;
            idxCurrent = idx;
            return true;
        }

        /// <summary>
        /// Get the next node that:
        ///   1. Follows the current node in document order (includes descendants, unlike XPath following axis)
        ///   2. Precedes the ending node in document order (if pageEnd is null, then all following nodes in the document are considered)
        ///   3. Has the specified XPathNodeType (but Attributes and Namespaces never match)
        /// If no such node exists, then do not set pageCurrent or idxCurrent and return false.
        /// </summary>
        public static bool GetContentFollowing(ref XPathNode[] pageCurrent, ref int idxCurrent, XPathNode[] pageEnd, int idxEnd, XPathNodeType typ) {
            XPathNode[] page = pageCurrent;
            int idx = idxCurrent;
            int mask = XPathNavigator.GetContentKindMask(typ);
            Debug.Assert(pageCurrent != null && idxCurrent != 0, "Cannot pass null argument(s)");
            Debug.Assert(typ != XPathNodeType.Text, "Text should be handled by GetTextFollowing in order to take into account collapsed text.");
            Debug.Assert(page[idx].NodeType != XPathNodeType.Attribute, "Current node should never be an attribute or namespace--caller should handle this case.");

            // Since nodes are laid out in document order on pages, scan them sequentially
            // rather than following sibling/child/parent links.
            idx++;
            do {
                if ((object) page == (object) pageEnd && idx <= idxEnd) {
                    // Only scan to termination point
                    while (idx != idxEnd) {
                        if (((1 << (int) page[idx].NodeType) & mask) != 0)
                            goto FoundNode;
                        idx++;
                    }
                    break;
                }
                else {
                    // Scan all nodes in the page
                    while (idx < page[0].PageInfo.NodeCount) {
                        if (((1 << (int) page[idx].NodeType) & mask) != 0)
                            goto FoundNode;
                        idx++;
                    }
                }

                page = page[0].PageInfo.NextPage;
                idx = 1;
            }
            while (page != null);

            return false;

        FoundNode:
            Debug.Assert(!page[idx].IsAttrNmsp, "GetContentFollowing should never return attributes or namespaces.");

            // Found match
            pageCurrent = page;
            idxCurrent = idx;
            return true;
        }

        /// <summary>
        /// Scan all nodes that follow the current node in document order, but precede the ending node in document order.
        /// Return two types of nodes with non-null text:
        ///   1. Element parents of collapsed text nodes (since it is the element parent that has the collapsed text)
        ///   2. Non-collapsed text nodes
        /// If no such node exists, then do not set pageCurrent or idxCurrent and return false.
        /// </summary>
        public static bool GetTextFollowing(ref XPathNode[] pageCurrent, ref int idxCurrent, XPathNode[] pageEnd, int idxEnd) {
            XPathNode[] page = pageCurrent;
            int idx = idxCurrent;
            Debug.Assert(pageCurrent != null && idxCurrent != 0, "Cannot pass null argument(s)");
            Debug.Assert(!page[idx].IsAttrNmsp, "Current node should never be an attribute or namespace--caller should handle this case.");

            // Since nodes are laid out in document order on pages, scan them sequentially
            // rather than following sibling/child/parent links.
            idx++;
            do {
                if ((object) page == (object) pageEnd && idx <= idxEnd) {
                    // Only scan to termination point
                    while (idx != idxEnd) {
                        if (page[idx].IsText || (page[idx].NodeType == XPathNodeType.Element && page[idx].HasCollapsedText))
                            goto FoundNode;
                        idx++;
                    }
                    break;
                }
                else {
                    // Scan all nodes in the page
                    while (idx < page[0].PageInfo.NodeCount) {
                        if (page[idx].IsText || (page[idx].NodeType == XPathNodeType.Element && page[idx].HasCollapsedText))
                            goto FoundNode;
                        idx++;
                    }
                }

                page = page[0].PageInfo.NextPage;
                idx = 1;
            }
            while (page != null);

            return false;

        FoundNode:
            // Found match
            pageCurrent = page;
            idxCurrent = idx;
            return true;
        }

        /// <summary>
        /// Get the next non-virtual (not collapsed text, not namespaces) node that follows the specified node in document order,
        /// but is not a descendant.  If no such node exists, then do not set pageNode or idxNode and return false.
        /// </summary>
        public static bool GetNonDescendant(ref XPathNode[] pageNode, ref int idxNode) {
            XPathNode[] page = pageNode;
            int idx = idxNode;

            // Get page, idx at which to end sequential scan of nodes
            do {
                // If the current node has a sibling,
                if (page[idx].HasSibling) {
                    // Then that is the first non-descendant
                    pageNode = page;
                    idxNode = page[idx].GetSibling(out pageNode);
                    return true;
                }

                // Otherwise, try finding a sibling at the parent level
                idx = page[idx].GetParent(out page);
            }
            while (idx != 0);

            return false;
        }

        /// <summary>
        /// Return the page and index of the first child (attribute or content) of the specified node.
        /// </summary>
        private static void GetChild(ref XPathNode[] pageNode, ref int idxNode) {
            Debug.Assert(pageNode[idxNode].HasAttribute || pageNode[idxNode].HasContentChild, "Caller must check HasAttribute/HasContentChild on parent before calling GetChild.");
            Debug.Assert(pageNode[idxNode].HasAttribute || !pageNode[idxNode].HasCollapsedText, "Text child is virtualized and therefore is not present in the physical node page.");

            if (++idxNode >= pageNode.Length) {
                // Child is first node on next page
                pageNode = pageNode[0].PageInfo.NextPage;
                idxNode = 1;
            }
            // Else child is next node on this page
        }
    }
}