Class TinyTree

java.lang.Object
net.sf.saxon.om.GenericTreeInfo
net.sf.saxon.tree.tiny.TinyTree
All Implemented Interfaces:
Source, TreeInfo, NodeVectorTree

public final class TinyTree extends GenericTreeInfo implements NodeVectorTree
A data structure to hold the contents of a tree. As the name implies, this implementation of the data model is optimized for size, and for speed of creation: it minimizes the number of Java objects used.

It can be used to represent a tree that is rooted at a document node, or one that is rooted at an element node.

From Saxon 9.7, as a consequence of bug 2220, it is used only to hold a single tree, whose root is always node number zero.

  • Field Details

    • charBuffer

      protected AppendableCharSequence charBuffer
    • commentBuffer

      protected FastStringBuffer commentBuffer
    • numberOfNodes

      protected int numberOfNodes
    • nodeKind

      public byte[] nodeKind
    • depth

      protected short[] depth
    • next

      protected int[] next
    • alpha

      protected int[] alpha
    • beta

      protected int[] beta
    • nameCode

      protected int[] nameCode
    • prior

      protected int[] prior
    • typeArray

      protected SchemaType[] typeArray
    • typedValueArray

      protected AtomicSequence[] typedValueArray
    • idRefElements

      protected IntSet idRefElements
    • idRefAttributes

      protected IntSet idRefAttributes
    • nilledElements

      protected IntSet nilledElements
    • defaultedAttributes

      protected IntSet defaultedAttributes
    • topWithinEntity

      protected IntSet topWithinEntity
    • TYPECODE_IDREF

      public static final int TYPECODE_IDREF
      See Also:
    • numberOfAttributes

      protected int numberOfAttributes
    • attParent

      protected int[] attParent
    • attCode

      protected int[] attCode
    • attValue

      protected CharSequence[] attValue
    • attTypedValue

      protected AtomicSequence[] attTypedValue
    • attType

      protected SimpleType[] attType
    • numberOfNamespaces

      protected int numberOfNamespaces
    • namespaceMaps

      protected NamespaceMap[] namespaceMaps
    • usesNamespaces

      protected boolean usesNamespaces
    • prefixPool

      protected PrefixPool prefixPool
    • entityTable

      protected HashMap<String,String[]> entityTable
    • knownBaseUris

      protected IntHashMap<String> knownBaseUris
  • Constructor Details

    • TinyTree

      public TinyTree(Configuration config, Statistics statistics)
      Create a tree with a specified initial size
      Parameters:
      config - the Saxon configuration
      statistics - the size parameters for the tree
  • Method Details

    • setConfiguration

      public void setConfiguration(Configuration config)
      Set the Configuration that contains this document
      Overrides:
      setConfiguration in class GenericTreeInfo
      Parameters:
      config - the Saxon configuration
    • getPrefixPool

      public PrefixPool getPrefixPool()
      Get the prefix pool
      Returns:
      the prefix pool
    • setCopiedFrom

      public void setCopiedFrom(NodeInfo copiedFrom)
      Declare that this tree was produced as a copy of another tree, and identify the root node of that tree
      Parameters:
      copiedFrom - the root of the tree from which this one was copied
    • getCopiedFrom

      public NodeInfo getCopiedFrom()
      Declare that this tree was produced as a copy of another tree, and identify the root node of that tree
      Returns:
      the root of the tree from which this one was copied, or null if this does not apply
    • addDocumentNode

      int addDocumentNode(TinyDocumentImpl doc)
      Add a document node to the tree. The data structure since 9.7 can only hold one tree, therefore at most one document node, which must be node zero.
      Parameters:
      doc - the document node to be added
      Returns:
      the number of the node that was added
    • addNode

      int addNode(short kind, int depth, int alpha, int beta, int nameCode)
      Add a node to the tree
      Parameters:
      kind - The kind of the node. This must be a document, element, text, comment, or processing-instruction node (not an attribute or namespace)
      depth - The depth in the tree
      alpha - Pointer to attributes or text
      beta - Pointer to namespaces or text
      nameCode - The name of the node
      Returns:
      the node number of the node that was added
    • appendChars

      void appendChars(CharSequence chars)
      Append character data to the current text node
      Parameters:
      chars - the character data to be appended
    • addTextNodeCopy

      public int addTextNodeCopy(int depth, int existingNodeNr)
      Create a new text node that is a copy of an existing text node
      Parameters:
      depth - the depth of the new node
      existingNodeNr - the node to be copied
      Returns:
      the node number of the new node
    • condense

      void condense(Statistics statistics)
      Condense the tree: release unused memory. This is done after the full tree has been built. The method makes a pragmatic judgement as to whether it is worth reclaiming space; this is only done when the constructed tree is very small compared with the space allocated.
      Parameters:
      statistics - represents the family of trees to which this tree belongs; statistics for the size of the tree are recorded in this Statistics object
    • setElementAnnotation

      void setElementAnnotation(int nodeNr, SchemaType type)
      Set the type annotation of an element node
      Parameters:
      nodeNr - the node whose type annotation is to be set
      type - the type annotation
    • getTypeAnnotation

      public int getTypeAnnotation(int nodeNr)
      Get the type annotation of a node. Applies only to document, element, text, processing instruction, and comment nodes.
      Parameters:
      nodeNr - the node whose type annotation is required
      Returns:
      the fingerprint of the type annotation for elements and attributes, otherwise undefined.
    • getSchemaType

      public SchemaType getSchemaType(int nodeNr)
      Get the type annotation of a node. Applies only to document, element, text, processing instruction, and comment nodes.
      Parameters:
      nodeNr - the node whose type annotation is required
      Returns:
      the fingerprint of the type annotation for elements and attributes, otherwise undefined.
    • getTypedValueOfElement

      public AtomicSequence getTypedValueOfElement(TinyElementImpl element) throws XPathException
      Get the typed value of an element node.
      Parameters:
      element - the element node
      Returns:
      the typed value of the node (a Value whose items are AtomicValue instances)
      Throws:
      XPathException - if a dynamic error occurs, for example if the node is an element annotated with a type that has element-only content
    • getTypedValueOfElement

      public AtomicSequence getTypedValueOfElement(int nodeNr) throws XPathException
      Get the type value of an element node, given only the node number
      Parameters:
      nodeNr - the node number of the element node
      Returns:
      the typed value of the node
      Throws:
      XPathException - if the eement has no typed value
    • getTypedValueOfAttribute

      public AtomicSequence getTypedValueOfAttribute(TinyAttributeImpl att, int nodeNr) throws XPathException
      Get the typed value of an attribute node. This method avoids materializing the attribute node if possible, but uses the attribute node supplied if it already exists.
      Parameters:
      att - the attribute node if available. If null is supplied, the attribute node will be materialized only if it is needed.
      nodeNr - the node number of the attribute node
      Returns:
      the typed value of the node
      Throws:
      XPathException - if an error is found
    • getNodeKind

      public int getNodeKind(int nodeNr)
      Get the node kind of a given node, which must be a document, element, text, comment, or processing instruction node
      Specified by:
      getNodeKind in interface NodeVectorTree
      Parameters:
      nodeNr - the node number
      Returns:
      the node kind
    • getNameCode

      public int getNameCode(int nodeNr)
      Get the nameCode for a given node, which must be a document, element, text, comment, or processing instruction node
      Parameters:
      nodeNr - the node number
      Returns:
      the name code
    • getFingerprint

      public int getFingerprint(int nodeNr)
      Get the fingerprint for a given node, which must be a document, element, text, comment, or processing instruction node
      Specified by:
      getFingerprint in interface NodeVectorTree
      Parameters:
      nodeNr - the node number
      Returns:
      the name code
    • getPrefix

      public String getPrefix(int nodeNr)
      Get the prefix for a given element node
      Parameters:
      nodeNr - the node number
      Returns:
      the prefix. Return "" for an unprefixed element node. Result is undefined for a non-element node.
    • ensurePriorIndex

      void ensurePriorIndex()
      On demand, make an index for quick access to preceding-sibling nodes
    • addAttribute

      void addAttribute(NodeInfo root, int parent, int nameCode, SimpleType type, CharSequence attValue, int properties)
      Add an attribute node to the tree
      Parameters:
      root - the root of the tree to contain the attribute
      parent - the parent element of the new attribute
      nameCode - the name code of the attribute
      type - the type annotation of the attribute
      attValue - the string value of the attribute
      properties - any special properties of the attribute (bit-significant)
    • markDefaultedAttribute

      public void markDefaultedAttribute(int attNr)
      Mark an attribute as resulting from expansion of attribute defaults
      Parameters:
      attNr - the attribute number
    • isDefaultedAttribute

      public boolean isDefaultedAttribute(int attNr)
      Ask whether an attribute results from expansion of attribute defaults
      Parameters:
      attNr - the attribute number
      Returns:
      true if this attribute resulted from expansion of default or fixed values defined in a schema. Note that this property will only be set if both the configuration properties FeatureKeys.EXPAND_ATTRIBUTE_DEFAULTS and FeatureKeys.MARK_DEFAULTED_ATTRIBUTES are set.
    • indexIDElement

      public void indexIDElement(NodeInfo root, int nodeNr)
      Index an element of type xs:ID
      Parameters:
      root - the root node of the document
      nodeNr - the element of type xs:ID
    • hasXmlSpacePreserveAttribute

      public boolean hasXmlSpacePreserveAttribute()
      Ask whether, somewhere in the tree, there is an attribute xml:space="preserve"
      Returns:
      true if some element in the tree has an xml:space attribute with the value preserve
    • addNamespaces

      void addNamespaces(int parent, NamespaceMap nsMap)
      Add a set of namespace bindings to the current element
      Parameters:
      parent - the node number of the element
      nsMap - namespace map identifying the prefix and uri
    • getNode

      public final TinyNodeImpl getNode(int nr)
      Get the node at a given position in the tree
      Specified by:
      getNode in interface NodeVectorTree
      Parameters:
      nr - the node number
      Returns:
      the node at the given position
    • getAtomizedValueOfUntypedNode

      AtomicValue getAtomizedValueOfUntypedNode(int nodeNr)
      Get the typed value of a node whose type is known to be untypedAtomic. The node must be a document, element, text, comment, or processing-instruction node, and it must have no type annotation. This method gets the typed value of a numbered node without actually instantiating the NodeInfo object, as a performance optimization.
      Parameters:
      nodeNr - the node whose typed value is required
      Returns:
      the atomic value of the node
    • getAttributeNode

      TinyAttributeImpl getAttributeNode(int nr)
      Make a (transient) attribute node from the array of attributes
      Parameters:
      nr - the node number of the attribute
      Returns:
      an attribute node
    • getAttributeAnnotation

      int getAttributeAnnotation(int nr)
      Get the type annotation of an attribute node.
      Parameters:
      nr - the node number of the attribute
      Returns:
      the fingerprint of the type annotation, or Type.UNTYPED_ATOMIC if there is no annotation
    • getAttributeType

      SimpleType getAttributeType(int nr)
      Get the type annotation of an attribute node.
      Parameters:
      nr - the node number of the attribute
      Returns:
      the fingerprint of the type annotation, or Type.UNTYPED_ATOMIC if there is no annotation
    • isIdAttribute

      public boolean isIdAttribute(int nr)
      Determine whether an attribute is an ID attribute. (The represents the is-id property in the data model)
      Parameters:
      nr - the node number of the attribute
      Returns:
      true if this is an ID attribute
    • isIdrefAttribute

      public boolean isIdrefAttribute(int nr)
      Determine whether an attribute is an IDREF/IDREFS attribute. (The represents the is-idref property in the data model)
      Parameters:
      nr - the node number of the attribute
      Returns:
      true if this is an IDREF/IDREFS attribute
    • isIdElement

      public boolean isIdElement(int nr)
      Ask whether an element is an ID element. (The represents the is-id property in the data model)
      Parameters:
      nr - the element node whose is-id property is required
      Returns:
      true if the node has the is-id property
    • isIdrefElement

      public boolean isIdrefElement(int nr)
      Ask whether an element is an IDREF/IDREFS element. (The represents the is-idref property in the data model)
      Parameters:
      nr - the element node whose is-idref property is required
      Returns:
      true if the node has the is-idref property
    • setSystemId

      void setSystemId(int seq, String uri)
      Set the system id of an element in the document. This identifies the external entity containing the node - this is not necessarily the same as the base URI.
      Parameters:
      seq - the node number
      uri - the system ID
    • setUniformBaseUri

      void setUniformBaseUri(String base)
    • getUniformBaseUri

      String getUniformBaseUri()
    • getSystemId

      public String getSystemId(int seq)
      Get the system id of an element in the document
      Parameters:
      seq - the node number of the element node
      Returns:
      the system id (base URI) of the element
    • getRootNode

      public NodeInfo getRootNode()
      Description copied from class: GenericTreeInfo
      Get the NodeInfo object representing the root of the tree (not necessarily a document node)
      Specified by:
      getRootNode in interface TreeInfo
      Overrides:
      getRootNode in class GenericTreeInfo
      Returns:
      the root node
    • setLineNumbering

      public void setLineNumbering()
      Set line numbering on
    • setLineNumber

      void setLineNumber(int sequence, int line, int column)
      Set the line number for a node. Ignored if line numbering is off.
      Parameters:
      sequence - the node number
      line - the line number to be set for the node
      column - the column number for the node
    • getLineNumber

      public int getLineNumber(int sequence)
      Get the line number for a node.
      Parameters:
      sequence - the node number
      Returns:
      the line number of the node. Return -1 if line numbering is off.
    • getColumnNumber

      public int getColumnNumber(int sequence)
      Get the column number for a node.
      Parameters:
      sequence - the node number
      Returns:
      the line number of the node. Return -1 if line numbering is off.
    • setNilled

      public void setNilled(int nodeNr)
      Set an element node to be marked as nilled
      Parameters:
      nodeNr - the node number to be marked as nilled
    • isNilled

      public boolean isNilled(int nodeNr)
      Ask whether a given node is nilled
      Parameters:
      nodeNr - the node in question (which must be an element node)
      Returns:
      true if the node has the nilled property
    • registerID

      void registerID(NodeInfo e, String id)
      Register a unique element ID. Fails if there is already an element with that ID.
      Parameters:
      e - The NodeInfo (always an element) having a particular unique ID value
      id - The unique ID value. The caller is responsible for checking that this is a valid NCName.
    • selectID

      public NodeInfo selectID(String id, boolean getParent)
      Get the element with a given ID.
      Specified by:
      selectID in interface TreeInfo
      Overrides:
      selectID in class GenericTreeInfo
      Parameters:
      id - The unique ID of the required element, previously registered using registerID()
      getParent - true if the required element is the parent of the element of type ID
      Returns:
      The NodeInfo (always an Element) for the given ID if one has been registered, otherwise null.
    • setUnparsedEntity

      void setUnparsedEntity(String name, String uri, String publicId)
      Set an unparsed entity URI associated with this document. For system use only, while building the document.
      Parameters:
      name - the name of the unparsed entity
      uri - the system identifier of the unparsed entity
      publicId - the public identifier of the unparsed entity
    • getUnparsedEntityNames

      public Iterator<String> getUnparsedEntityNames()
      Get the list of unparsed entities defined in this document
      Specified by:
      getUnparsedEntityNames in interface TreeInfo
      Overrides:
      getUnparsedEntityNames in class GenericTreeInfo
      Returns:
      an Iterator, whose items are of type String, containing the names of all unparsed entities defined in this document. If there are no unparsed entities or if the information is not available then an empty iterator is returned
    • getUnparsedEntity

      public String[] getUnparsedEntity(String name)
      Get the unparsed entity with a given nameID if there is one, or null if not. If the entity does not exist, return null.
      Specified by:
      getUnparsedEntity in interface TreeInfo
      Overrides:
      getUnparsedEntity in class GenericTreeInfo
      Parameters:
      name - the name of the entity
      Returns:
      if the entity exists, return an array of two Strings, the first holding the system ID of the entity, the second holding the public
    • getNamePool

      public NamePool getNamePool()
    • markTopWithinEntity

      public void markTopWithinEntity(int nodeNr)
    • isTopWithinEntity

      public boolean isTopWithinEntity(int nodeNr)
    • diagnosticDump

      public void diagnosticDump()
      Produce diagnostic print of main tree arrays
    • diagnosticDump

      public static void diagnosticDump(NodeInfo node)
      Create diagnostic dump of the tree containing a particular node. Designed to be called as an extension function for diagnostics.
      Parameters:
      node - the node in question
    • showSize

      public void showSize()
      Output a statistical summary to System.err
    • isTyped

      public boolean isTyped()
      Ask whether the document contains any nodes whose type annotation is anything other than UNTYPED
      Specified by:
      isTyped in interface NodeVectorTree
      Specified by:
      isTyped in interface TreeInfo
      Returns:
      true if the document contains elements whose type is other than UNTYPED
    • getNumberOfNodes

      public int getNumberOfNodes()
      Get the number of nodes in the tree, excluding attributes and namespace nodes
      Returns:
      the number of nodes.
    • getNumberOfAttributes

      public int getNumberOfAttributes()
      Get the number of attributes in the tree
      Returns:
      the number of attributes
    • getNumberOfNamespaces

      public int getNumberOfNamespaces()
      Get the number of namespace declarations in the tree
      Returns:
      the number of namespace declarations
    • getNodeKindArray

      public byte[] getNodeKindArray()
      Get the array holding node kind information
      Specified by:
      getNodeKindArray in interface NodeVectorTree
      Returns:
      an array of bytes, byte N is the node kind of node number N
    • getNodeDepthArray

      public short[] getNodeDepthArray()
      Get the array holding node depth information
      Returns:
      an array of shorts, byte N is the node depth of node number N
    • getNameCodeArray

      public int[] getNameCodeArray()
      Get the array holding node name information
      Specified by:
      getNameCodeArray in interface NodeVectorTree
      Returns:
      an array of integers, integer N is the name code of node number N
    • getTypeArray

      public SchemaType[] getTypeArray()
      Get the array holding node type information
      Returns:
      an array of integers, integer N is the type code of node number N
    • getNextPointerArray

      public int[] getNextPointerArray()
      Get the array holding next-sibling pointers
      Returns:
      an array of integers, integer N is the next-sibling pointer for node number N
    • getAlphaArray

      public int[] getAlphaArray()
      Get the array holding alpha information
      Returns:
      an array of integers, whose meaning depends on the node kind. For elements it is a pointer to the first attribute, for text, comment, and processing instruction nodes it is a pointer to the content
    • getBetaArray

      public int[] getBetaArray()
      Get the array holding beta information
      Returns:
      an array of integers, whose meaning depends on the node kind. For elements it is a pointer to the first namespace declaration
    • getCharacterBuffer

      public AppendableCharSequence getCharacterBuffer()
      Get the character buffer used to hold all the text data of the document
      Returns:
      the character buffer
    • getCommentBuffer

      public CharSequence getCommentBuffer()
      Get the character buffer used to hold all the comment data of the document
      Returns:
      the character buffer used for comments
    • getAttributeNameCodeArray

      public int[] getAttributeNameCodeArray()
      Get the array used to hold the name codes of all attributes
      Returns:
      an integer array; the Nth integer holds the attribute name code of attribute N
    • getAttributeTypeArray

      public SimpleType[] getAttributeTypeArray()
      Get the array used to hold the type codes of all attributes
      Returns:
      an integer array; the Nth integer holds the attribute type code of attribute N
    • getAttributeParentArray

      public int[] getAttributeParentArray()
      Get the array used to hold the parent pointers of all attributes
      Returns:
      an integer array; the Nth integer holds the pointer to the parent element of attribute N
    • getAttributeValueArray

      public CharSequence[] getAttributeValueArray()
      Get the array used to hold the name codes of all attributes
      Returns:
      an array of strings; the Nth string holds the string value of attribute N
    • getNamespaceBindings

      public NamespaceBinding[] getNamespaceBindings()
      Get the array used to hold the namespace declarations
      Returns:
      an array of namespace bindings
    • getNamespaceMaps

      public NamespaceMap[] getNamespaceMaps()
      Get the array used to hold the in-scope namespaces
      Returns:
      an array of namespace bindings
    • getNamespaceParentArray

      public int[] getNamespaceParentArray()
      Get the array used to hold the parent pointers of all namespace declarations
      Returns:
      an integer array; the Nth integer holds the pointer to the parent element of namespace N
    • isUsesNamespaces

      public boolean isUsesNamespaces()
      Ask whether the tree contains any namespace declarations
      Returns:
      true if there is a namespace declaration (other than the XML namespace) anywhere in the tree
    • bulkCopy

      public void bulkCopy(TinyTree source, int nodeNr, int currentDepth, int parentNodeNr)
      Bulk copy an element node from another TinyTree. Type annotations will always be stripped.
      Parameters:
      source - the source tree
      nodeNr - the element node in the source tree to be deep-copied
      currentDepth - the current depth in this tree
      parentNodeNr - the node number in this tree of the parent which the copied node will be attached to
    • getLocalNameIndex

      public Map<String,IntSet> getLocalNameIndex()
      Get (and build if necessary) an index from local names to fingerprints
      Returns:
      a Map whose keys are local names and whose values are sets of fingerprints (usually singleton sets!) of names with that local name. The index is for element names only.