|
//------------------------------------------------------------------------------
// <copyright file="XPathNode.cs" company="Microsoft">
// Copyright (c) Microsoft Corporation. All rights reserved.
// </copyright>
// <owner current="true" primary="true">Microsoft</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>
/// Implementation of a Node in the XPath/XQuery data model.
/// 1. All nodes are stored in variable-size pages (max 65536 nodes/page) of XPathNode structures.
/// 2. Pages are sequentially numbered. Nodes are allocated in strict document order.
/// 3. Node references take the form of a (page, index) pair.
/// 4. Each node explicitly stores a parent and a sibling reference.
/// 5. If a node has one or more attributes and/or non-collapsed content children, then its first
/// child is stored in the next slot. If the node is in the last slot of a page, then its first
/// child is stored in the first slot of the next page.
/// 6. Attributes are linked together at the start of the child list.
/// 7. Namespaces are allocated in totally separate pages. Elements are associated with
/// declared namespaces via a hashtable map in the document.
/// 8. Name parts are always non-null (string.Empty for nodes without names)
/// 9. XPathNodeInfoAtom contains all information that is common to many nodes in a
/// document, and therefore is atomized to save space. This includes the document, the name,
/// the child, sibling, parent, and value pages, and the schema type.
/// 10. The node structure is 20 bytes in length. Out-of-line overhead is typically 2-4 bytes per node.
/// </summary>
internal struct XPathNode {
private XPathNodeInfoAtom info; // Atomized node information
private ushort idxSibling; // Page index of sibling node
private ushort idxParent; // Page index of parent node
private ushort idxSimilar; // Page index of next node in document order that has local name with same hashcode
private ushort posOffset; // Line position offset of node (added to LinePositionBase)
private uint props; // Node properties (broken down into bits below)
private string value; // String value of node
private const uint NodeTypeMask = 0xF;
private const uint HasAttributeBit = 0x10;
private const uint HasContentChildBit = 0x20;
private const uint HasElementChildBit = 0x40;
private const uint HasCollapsedTextBit = 0x80;
private const uint AllowShortcutTagBit = 0x100; // True if this is an element that allows shortcut tag syntax
private const uint HasNmspDeclsBit = 0x200; // True if this is an element with namespace declarations declared on it
private const uint LineNumberMask = 0x00FFFC00; // 14 bits for line number offset (0 - 16K)
private const int LineNumberShift = 10;
private const int CollapsedPositionShift = 24; // 8 bits for collapsed text position offset (0 - 256)
#if DEBUG
public const int MaxLineNumberOffset = 0x20;
public const int MaxLinePositionOffset = 0x20;
public const int MaxCollapsedPositionOffset = 0x10;
#else
public const int MaxLineNumberOffset = 0x3FFF;
public const int MaxLinePositionOffset = 0xFFFF;
public const int MaxCollapsedPositionOffset = 0xFF;
#endif
/// <summary>
/// Returns the type of this node
/// </summary>
public XPathNodeType NodeType {
get { return (XPathNodeType) (this.props & NodeTypeMask); }
}
/// <summary>
/// Returns the namespace prefix of this node. If this node has no prefix, then the empty string
/// will be returned (never null).
/// </summary>
public string Prefix {
get { return this.info.Prefix; }
}
/// <summary>
/// Returns the local name of this node. If this node has no name, then the empty string
/// will be returned (never null).
/// </summary>
public string LocalName {
get { return this.info.LocalName; }
}
/// <summary>
/// Returns the name of this node. If this node has no name, then the empty string
/// will be returned (never null).
/// </summary>
public string Name {
get {
if (Prefix.Length == 0) {
return LocalName;
}
else {
return string.Concat(Prefix, ":", LocalName);
}
}
}
/// <summary>
/// Returns the namespace part of this node's name. If this node has no name, then the empty string
/// will be returned (never null).
/// </summary>
public string NamespaceUri {
get { return this.info.NamespaceUri; }
}
/// <summary>
/// Returns this node's document.
/// </summary>
public XPathDocument Document {
get { return this.info.Document; }
}
/// <summary>
/// Returns this node's base Uri. This is string.Empty for all node kinds except Element, Root, and PI.
/// </summary>
public string BaseUri {
get { return this.info.BaseUri; }
}
/// <summary>
/// Returns this node's source line number.
/// </summary>
public int LineNumber {
get { return this.info.LineNumberBase + (int) ((this.props & LineNumberMask) >> LineNumberShift); }
}
/// <summary>
/// Return this node's source line position.
/// </summary>
public int LinePosition {
get { return this.info.LinePositionBase + (int) this.posOffset; }
}
/// <summary>
/// If this node is an element with collapsed text, then return the source line position of the node (the
/// source line number is the same as LineNumber).
/// </summary>
public int CollapsedLinePosition {
get {
Debug.Assert(HasCollapsedText, "Do not call CollapsedLinePosition unless HasCollapsedText is true.");
return LinePosition + (int) (this.props >> CollapsedPositionShift);
}
}
/// <summary>
/// Returns information about the node page. Only the 0th node on each page has this property defined.
/// </summary>
public XPathNodePageInfo PageInfo {
get { return this.info.PageInfo; }
}
/// <summary>
/// Returns the root node of the current document. This always succeeds.
/// </summary>
public int GetRoot(out XPathNode[] pageNode) {
return this.info.Document.GetRootNode(out pageNode);
}
/// <summary>
/// Returns the parent of this node. If this node has no parent, then 0 is returned.
/// </summary>
public int GetParent(out XPathNode[] pageNode) {
pageNode = this.info.ParentPage;
return this.idxParent;
}
/// <summary>
/// Returns the next sibling of this node. If this node has no next sibling, then 0 is returned.
/// </summary>
public int GetSibling(out XPathNode[] pageNode) {
pageNode = this.info.SiblingPage;
return this.idxSibling;
}
/// <summary>
/// Returns the next element in document order that has the same local name hashcode as this element.
/// If there are no similar elements, then 0 is returned.
/// </summary>
public int GetSimilarElement(out XPathNode[] pageNode) {
pageNode = this.info.SimilarElementPage;
return this.idxSimilar;
}
/// <summary>
/// Returns true if this node's name matches the specified localName and namespaceName. Assume
/// that localName has been atomized, but namespaceName has not.
/// </summary>
public bool NameMatch(string localName, string namespaceName) {
Debug.Assert(localName == null || (object) Document.NameTable.Get(localName) == (object) localName, "localName must be atomized.");
return (object) this.info.LocalName == (object) localName &&
this.info.NamespaceUri == namespaceName;
}
/// <summary>
/// Returns true if this is an Element node with a name that matches the specified localName and
/// namespaceName. Assume that localName has been atomized, but namespaceName has not.
/// </summary>
public bool ElementMatch(string localName, string namespaceName) {
Debug.Assert(localName == null || (object) Document.NameTable.Get(localName) == (object) localName, "localName must be atomized.");
return NodeType == XPathNodeType.Element &&
(object) this.info.LocalName == (object) localName &&
this.info.NamespaceUri == namespaceName;
}
/// <summary>
/// Return true if this node is an xmlns:xml node.
/// </summary>
public bool IsXmlNamespaceNode {
get {
string localName = this.info.LocalName;
return NodeType == XPathNodeType.Namespace && localName.Length == 3 && localName == "xml";
}
}
/// <summary>
/// Returns true if this node has a sibling.
/// </summary>
public bool HasSibling {
get { return this.idxSibling != 0; }
}
/// <summary>
/// Returns true if this node has a collapsed text node as its only content-typed child.
/// </summary>
public bool HasCollapsedText {
get { return (this.props & HasCollapsedTextBit) != 0; }
}
/// <summary>
/// Returns true if this node has at least one attribute.
/// </summary>
public bool HasAttribute {
get { return (this.props & HasAttributeBit) != 0; }
}
/// <summary>
/// Returns true if this node has at least one content-typed child (attributes and namespaces
/// don't count).
/// </summary>
public bool HasContentChild {
get { return (this.props & HasContentChildBit) != 0; }
}
/// <summary>
/// Returns true if this node has at least one element child.
/// </summary>
public bool HasElementChild {
get { return (this.props & HasElementChildBit) != 0; }
}
/// <summary>
/// Returns true if this is an attribute or namespace node.
/// </summary>
public bool IsAttrNmsp {
get {
XPathNodeType xptyp = NodeType;
return xptyp == XPathNodeType.Attribute || xptyp == XPathNodeType.Namespace;
}
}
/// <summary>
/// Returns true if this is a text or whitespace node.
/// </summary>
public bool IsText {
get { return XPathNavigator.IsText(NodeType); }
}
/// <summary>
/// Returns true if this node has local namespace declarations associated with it. Since all
/// namespace declarations are stored out-of-line in the owner Document, this property
/// can be consulted in order to avoid a lookup in the common case where this node has no
/// local namespace declarations.
/// </summary>
public bool HasNamespaceDecls {
get { return (this.props & HasNmspDeclsBit) != 0; }
set {
if (value) this.props |= HasNmspDeclsBit;
else unchecked { this.props &= (byte) ~((uint) HasNmspDeclsBit); }
}
}
/// <summary>
/// Returns true if this node is an empty element that allows shortcut tag syntax.
/// </summary>
public bool AllowShortcutTag {
get { return (this.props & AllowShortcutTagBit) != 0; }
}
/// <summary>
/// Cached hashcode computed over the local name of this element.
/// </summary>
public int LocalNameHashCode {
get { return this.info.LocalNameHashCode; }
}
/// <summary>
/// Return the precomputed String value of this node (null if no value exists, i.e. document node, element node with complex content, etc).
/// </summary>
public string Value {
get { return this.value; }
}
//-----------------------------------------------
// Node construction
//-----------------------------------------------
/// <summary>
/// Constructs the 0th XPathNode in each page, which contains only page information.
/// </summary>
public void Create(XPathNodePageInfo pageInfo) {
this.info = new XPathNodeInfoAtom(pageInfo);
}
/// <summary>
/// Constructs a XPathNode. Later, the idxSibling and value fields may be fixed up.
/// </summary>
public void Create(XPathNodeInfoAtom info, XPathNodeType xptyp, int idxParent) {
Debug.Assert(info != null && idxParent <= UInt16.MaxValue);
this.info = info;
this.props = (uint) xptyp;
this.idxParent = (ushort) idxParent;
}
/// <summary>
/// Set this node's line number information.
/// </summary>
public void SetLineInfoOffsets(int lineNumOffset, int linePosOffset) {
Debug.Assert(lineNumOffset >= 0 && lineNumOffset <= MaxLineNumberOffset, "Line number offset too large or small: " + lineNumOffset);
Debug.Assert(linePosOffset >= 0 && linePosOffset <= MaxLinePositionOffset, "Line position offset too large or small: " + linePosOffset);
this.props |= ((uint) lineNumOffset << LineNumberShift);
this.posOffset = (ushort) linePosOffset;
}
/// <summary>
/// Set the position offset of this element's collapsed text.
/// </summary>
public void SetCollapsedLineInfoOffset(int posOffset) {
Debug.Assert(posOffset >= 0 && posOffset <= MaxCollapsedPositionOffset, "Collapsed text line position offset too large or small: " + posOffset);
this.props |= ((uint) posOffset << CollapsedPositionShift);
}
/// <summary>
/// Set this node's value.
/// </summary>
public void SetValue(string value) {
this.value = value;
}
/// <summary>
/// Create an empty element value.
/// </summary>
public void SetEmptyValue(bool allowShortcutTag) {
Debug.Assert(NodeType == XPathNodeType.Element);
this.value = string.Empty;
if (allowShortcutTag)
this.props |= AllowShortcutTagBit;
}
/// <summary>
/// Create a collapsed text node on this element having the specified value.
/// </summary>
public void SetCollapsedValue(string value) {
Debug.Assert(NodeType == XPathNodeType.Element);
this.value = value;
this.props |= HasContentChildBit | HasCollapsedTextBit;
}
/// <summary>
/// This method is called when a new child is appended to this node's list of attributes and children.
/// The type of the new child is used to determine how various parent properties should be set.
/// </summary>
public void SetParentProperties(XPathNodeType xptyp) {
if (xptyp == XPathNodeType.Attribute) {
this.props |= HasAttributeBit;
}
else {
this.props |= HasContentChildBit;
if (xptyp == XPathNodeType.Element)
this.props |= HasElementChildBit;
}
}
/// <summary>
/// Link this node to its next sibling. If "pageSibling" is different than the one stored in the InfoAtom, re-atomize.
/// </summary>
public void SetSibling(XPathNodeInfoTable infoTable, XPathNode[] pageSibling, int idxSibling) {
Debug.Assert(pageSibling != null && idxSibling != 0 && idxSibling <= UInt16.MaxValue, "Bad argument");
Debug.Assert(this.idxSibling == 0, "SetSibling should not be called more than once.");
this.idxSibling = (ushort) idxSibling;
if (pageSibling != this.info.SiblingPage) {
// Re-atomize the InfoAtom
this.info = infoTable.Create(this.info.LocalName, this.info.NamespaceUri, this.info.Prefix, this.info.BaseUri,
this.info.ParentPage, pageSibling, this.info.SimilarElementPage,
this.info.Document, this.info.LineNumberBase, this.info.LinePositionBase);
}
}
/// <summary>
/// Link this element to the next element in document order that shares a local name having the same hash code.
/// If "pageSimilar" is different than the one stored in the InfoAtom, re-atomize.
/// </summary>
public void SetSimilarElement(XPathNodeInfoTable infoTable, XPathNode[] pageSimilar, int idxSimilar) {
Debug.Assert(pageSimilar != null && idxSimilar != 0 && idxSimilar <= UInt16.MaxValue, "Bad argument");
Debug.Assert(this.idxSimilar == 0, "SetSimilarElement should not be called more than once.");
this.idxSimilar = (ushort) idxSimilar;
if (pageSimilar != this.info.SimilarElementPage) {
// Re-atomize the InfoAtom
this.info = infoTable.Create(this.info.LocalName, this.info.NamespaceUri, this.info.Prefix, this.info.BaseUri,
this.info.ParentPage, this.info.SiblingPage, pageSimilar,
this.info.Document, this.info.LineNumberBase, this.info.LinePositionBase);
}
}
}
/// <summary>
/// A reference to a XPathNode is composed of two values: the page on which the node is located, and the node's
/// index in the page.
/// </summary>
internal struct XPathNodeRef {
private XPathNode[] page;
private int idx;
public static XPathNodeRef Null {
get { return new XPathNodeRef(); }
}
public XPathNodeRef(XPathNode[] page, int idx) {
this.page = page;
this.idx = idx;
}
public bool IsNull {
get { return this.page == null; }
}
public XPathNode[] Page {
get { return this.page; }
}
public int Index {
get { return this.idx; }
}
public override int GetHashCode() {
return XPathNodeHelper.GetLocation(this.page, this.idx);
}
}
}
|