File: System\Windows\Documents\TextTreeTextNode.cs
Web Access
Project: src\src\Microsoft.DotNet.Wpf\src\PresentationFramework\PresentationFramework.csproj (PresentationFramework)
// Licensed to the .NET Foundation under one or more agreements.
// The .NET Foundation licenses this file to you under the MIT license.
// See the LICENSE file in the project root for more information.
 
//
// Description: A TextContainer node representing a run of text.
//
 
using System;
using MS.Internal;
 
namespace System.Windows.Documents
{
    // Runs of text are represented internally by TextTreeTextNodes.
    //
    // Text nodes are regularly "split" -- broken in half -- when a
    // TextPointer needs to reference a character within the node's run.
    // We track a reference counts of the number of positions referencing a
    // text node so that we can later merge it back again when no TextPositions
    // reference it.
    //
    // Unlike other nodes, TextTreeTextNode may only ever be referenced on a
    // single edge by TextPositions.  This is necessary to ensure that we
    // can split a text node any time a TextPositions needs to reference a
    // character within the node.  With at most one edge referenced we are free
    // to create a new node covering the unreferenced edge without disturbing
    // any TextPositoins referencing the original node.
    //
    // Unlike all other nodes, text nodes may occasionally have zero symbol counts.
    // This happens when a TextPointer wants to reference a node edge, but
    // the node's other edge is already referenced by someone else.  In this case,
    // we split the text node, adding a zero-width node just for the
    // TextPointer's use.
    internal class TextTreeTextNode : TextTreeNode
    {
        //------------------------------------------------------
        //
        //  Constructors
        //
        //------------------------------------------------------
 
        #region Constructors
 
        // Creates a new TextTreeTextNode instance.
        internal TextTreeTextNode()
        {
            _symbolOffsetCache = -1;
        }
 
        #endregion Constructors
 
        //------------------------------------------------------
        //
        //  Public Methods
        //
        //------------------------------------------------------
 
        #region Public Methods
 
#if DEBUG
        // Debug-only ToString override.
        public override string ToString()
        {
            return ("TextNode Id=" + this.DebugId + " SymbolCount=" + _symbolCount);
        }
#endif // DEBUG
 
        #endregion Public Methods
 
        //------------------------------------------------------
        //
        //  Internal Methods
        //
        //------------------------------------------------------
 
        #region Internal Methods
 
        // Returns a shallow copy of this node.
        // Returns null if this node has a zero symbol count --
        // a clone would have no references, so there's no point
        // in allocating one.
        internal override TextTreeNode Clone()
        {
            TextTreeTextNode clone;
 
            clone = null;
 
            if (_symbolCount > 0)
            {
                clone = new TextTreeTextNode();
                clone._symbolCount = _symbolCount;
            }
 
            return clone;
        }
 
        // Returns the TextPointerContext of the node.
        internal override TextPointerContext GetPointerContext(LogicalDirection direction)
        {
            return TextPointerContext.Text;
        }
 
        // Increments a count of the number of TextPositions and TextNavigators
        // referencing this node.  Called when positions are created or moved.
        // Returns the actual node referenced -- a new node will be created if
        // there are already references to this node's other edge.
        internal override TextTreeNode IncrementReferenceCount(ElementEdge edge, int delta)
        {
            TextTreeTextNode node;
            TextTreeTextNode mergeNode;
 
            Invariant.Assert(delta >= 0);
            Invariant.Assert(edge == ElementEdge.BeforeStart || edge == ElementEdge.AfterEnd, "Bad edge ref to TextTreeTextNode!");
 
            if (delta == 0)
            {
                return this;
            }
 
            if (_positionRefCount > 0 && edge != _referencedEdge)
            {
                // We need to split off a node to cover the new edge.
                node = Split(edge == ElementEdge.BeforeStart ? 0 : _symbolCount, edge);
 
                node._referencedEdge = edge;
                node._positionRefCount += delta;
 
                // It's possible we need to merge a neighbor node.
                // This happens when someone calls TextContainer.GetNodeAndEdgeAtOffset,
                // which splits a text node into two non-empty nodes.  We can't merge
                // immediately, because we don't know which of the two nodes will
                // get an additional ref.
                // If the unreferenced node of the pair gets the new reference,
                // there no possibility for a merge.  Otherwise, we have to split
                // again on the already referenced node and end up here.
                if (edge == ElementEdge.BeforeStart)
                {
                    // If node B has no references it can merge with node A.
                    // <A ""/><B "x"/><newNode ""/><this "x".>
                    mergeNode = node.GetPreviousNode() as TextTreeTextNode;
                }
                else
                {
                    // If node A has no references it can merge with node B.
                    // <this "x"/><newNode ""/><A "x"/><B ""/>
                    mergeNode = node.GetNextNode() as TextTreeTextNode;
                }
                if (mergeNode != null && mergeNode._positionRefCount == 0)
                {
                    mergeNode.Merge();
                }
            }
            else
            {
                node = this;
                _referencedEdge = edge;
                _positionRefCount += delta;
            }
 
            return node;
        }
 
        // Decrements a count of the number of TextPositions and TextNavigators
        // referencing this node.
        // This method attempts to merge adjacent TextTreeTextNodes when the ref count
        // transitions from 1 to 0.
        //
        // Be careful!  This can modify the tree, removing
        // TextTreeTextNodes.
        internal override void DecrementReferenceCount(ElementEdge edge)
        {
            Invariant.Assert(edge == _referencedEdge, "Bad edge decrement!");
 
            _positionRefCount--;
            Invariant.Assert(_positionRefCount >= 0, "Bogus PositionRefCount! ");
 
            // If the ref count drops to zero, we may be able to merge this node with an adjacent one.            
            if (_positionRefCount == 0)
            {
                Merge();
            }
        }
 
        // Splits this node into two adjacent nodes.
        // Returns the node which contains the original requested edge
        // (e.g., if edge == ElementEdge.BeforeStart, this method returns the
        // preceding node, if edge == ElementEdge.AfterEnd, it returns the
        // following node).
        internal TextTreeTextNode Split(int localOffset, ElementEdge edge)
        {
            TextTreeTextNode newNode;
            TextTreeTextNode edgeNode;
            ElementEdge newNodeEdge;
 
            Invariant.Assert(_symbolCount > 0, "Splitting a zero-width TextNode!");
            Invariant.Assert(localOffset >= 0 && localOffset <= _symbolCount, "Bad localOffset!");
            Invariant.Assert(edge == ElementEdge.BeforeStart || edge == ElementEdge.AfterEnd, "Bad edge parameter!");
 
#if DEBUG
            if (localOffset == 0)
            {
                TextTreeNode previousNode;
 
                Invariant.Assert(edge == ElementEdge.BeforeStart, "Unexpected edge!");
                Invariant.Assert(edge != _referencedEdge, "Splitting at referenced edge!");
 
                previousNode = (TextTreeNode)GetPreviousNode();
                Invariant.Assert(previousNode == null || previousNode.SymbolCount > 0 || previousNode.AfterEndReferenceCount,
                             "Found preceding zero-width text node inside Split!");
            }
            else if (localOffset == _symbolCount)
            {
                TextTreeNode nextNode;
 
                Invariant.Assert(edge == ElementEdge.AfterEnd, "Unexpected edge!");
                Invariant.Assert(edge != _referencedEdge, "Splitting at referenced edge!");
 
                nextNode = (TextTreeNode)GetNextNode();
                Invariant.Assert(nextNode == null || nextNode.SymbolCount > 0 || nextNode.BeforeStartReferenceCount,
                             "Found following zero-width text node inside Split! (2)");
            }
#endif // DEBUG
 
            newNode = new TextTreeTextNode();
            newNode._generation = _generation;
 
            // Splay this node to the root so we don't corrupt any LeftSymbolCounts
            // of ancestor nodes when we fixup _symbolCount below.
            Splay();
 
            if (_positionRefCount > 0 && _referencedEdge == ElementEdge.BeforeStart)
            {
                // New node is the following node.
                newNode._symbolOffsetCache = (_symbolOffsetCache == -1) ? -1 : _symbolOffsetCache + localOffset;
                newNode._symbolCount = _symbolCount - localOffset;
 
                _symbolCount = localOffset;
 
                newNodeEdge = ElementEdge.AfterEnd;
 
                edgeNode = (edge == ElementEdge.BeforeStart) ? this : newNode;
            }
            else
            {
                // New node is the preceding node.
                newNode._symbolOffsetCache = _symbolOffsetCache;
                newNode._symbolCount = localOffset;
 
                _symbolOffsetCache = (_symbolOffsetCache == -1) ? -1 : _symbolOffsetCache + localOffset;
                _symbolCount -= localOffset;
 
                newNodeEdge = ElementEdge.BeforeStart;
 
                edgeNode = (edge == ElementEdge.BeforeStart) ? newNode : this;
            }
 
            Invariant.Assert(_symbolCount >= 0);
            Invariant.Assert(newNode._symbolCount >= 0);
 
            newNode.InsertAtNode(this, newNodeEdge);
 
            return edgeNode;            
        }
 
        #endregion Internal methods
 
        //------------------------------------------------------
        //
        //  Internal Properties
        //
        //------------------------------------------------------
 
        #region Internal Properties
 
        // If this node is a local root, then ParentNode contains it.
        // Otherwise, this is the node parenting this node within its tree.
        internal override SplayTreeNode ParentNode
        {
            get
            {
                return _parentNode;
            }
            
            set
            {
                _parentNode = (TextTreeNode)value;
            }
        }
 
        // TextTreeTextNode never has contained nodes.
        internal override SplayTreeNode ContainedNode
        {
            get
            {
                return null;
            }
            
            set
            {
                Invariant.Assert(false, "Can't set child on a TextTreeTextNode!");
            }
        }
 
        // Count of symbols of all siblings preceding this node.
        internal override int LeftSymbolCount
        {
            get
            {
                return _leftSymbolCount;
            }
 
            set
            {
                _leftSymbolCount = value;
            }
        }
 
        // Count of chars of all siblings preceding this node.
        internal override int LeftCharCount
        {
            get
            {
                return _leftCharCount;
            }
 
            set
            {
                _leftCharCount = value;
            }
        }
 
        // Left child node in a sibling tree.
        internal override SplayTreeNode LeftChildNode
        {
            get
            {
                return _leftChildNode;
            }
            
            set
            {
                _leftChildNode = (TextTreeNode)value;
            }
        }
 
        // Right child node in a sibling tree.
        internal override SplayTreeNode RightChildNode
        {
            get
            {
                return _rightChildNode;
            }
            
            set
            {
                _rightChildNode = (TextTreeNode)value;
            }
        }
 
        // The TextContainer's generation when SymbolOffsetCache was last updated.
        // If the current generation doesn't match TextContainer.Generation, then
        // SymbolOffsetCache is invalid.
        internal override uint Generation
        {
            get
            {
                return _generation;
            }
            
            set
            {
                _generation = value;
            }
        }
 
        // Cached symbol offset.
        internal override int SymbolOffsetCache
        {
            get
            {
                return _symbolOffsetCache;
            }
            
            set
            {
                _symbolOffsetCache = value;
            }
        }
 
        // Count of symbols covered by this node.
        internal override int SymbolCount
        {
            get
            {
                return _symbolCount;
            }
            
            set
            {
                _symbolCount = value;
            }
        }
 
        // Count of chars covered by this node.
        internal override int IMECharCount
        {
            get
            {
                return this.SymbolCount;
            }
 
            set
            {
                // Tracked redundently by _symbolCount.
            }
        }
 
        // Count of TextPositions referencing the node's BeforeStart edge.
        internal override bool BeforeStartReferenceCount
        {
            get
            {
                return _referencedEdge == ElementEdge.BeforeStart ? _positionRefCount > 0 : false;
            }
 
            set
            {
                Invariant.Assert(false, "Can't set TextTreeTextNode ref counts directly!");
            }
        }
 
        // Count of TextPositions referencing the node's AfterStart edge.
        // Since text nodes don't have an AfterStart edge, this is always zero.
        internal override bool AfterStartReferenceCount
        {
            get
            {
                return false;
            }
 
            set
            {
                Invariant.Assert(false, "Text nodes don't have an AfterStart edge!");
            }
        }
 
        // Count of TextPositions referencing the node's BeforeEnd edge.
        // Since text nodes don't have an BeforeEnd edge, this is always zero.
        internal override bool BeforeEndReferenceCount
        {
            get
            {
                return false;
            }
 
            set
            {
                Invariant.Assert(false, "Text nodes don't have a BeforeEnd edge!");
            }
        }
 
        // Count of TextPositions referencing the node's AfterEnd edge.
        internal override bool AfterEndReferenceCount
        {
            get
            {
                return _referencedEdge == ElementEdge.AfterEnd ? _positionRefCount > 0 : false;
            }
 
            set
            {
                Invariant.Assert(false, "Can't set TextTreeTextNode ref counts directly!");
            }
        }
 
        #endregion Internal Properties
 
        //------------------------------------------------------
        //
        //  Private Methods
        //
        //------------------------------------------------------
 
        #region Private Methods
 
        // Attempts to merge this node with adjacent TextTreeTextNodes.
        // Called when the position ref counts drops from 1 to 0.
        private void Merge()
        {
            TextTreeTextNode previousNode;
            TextTreeTextNode nextNode;
 
            Invariant.Assert(_positionRefCount == 0, "Inappropriate Merge call!");
            
            // Check the previous node.
            previousNode = GetPreviousNode() as TextTreeTextNode;
 
            if (previousNode != null &&
                (previousNode._positionRefCount == 0 || previousNode._referencedEdge == ElementEdge.BeforeStart))
            {
                // The previous node must take the place of this one, since previous
                // may still have references.
                Remove();
                // null _parentNode out so that if there's a bug and someone still references this node we'll hear about it.
                _parentNode = null;
                previousNode.Splay();
 
                previousNode._symbolCount += _symbolCount;
            }
            else
            {
                previousNode = this;
            }
            
            // Check the following node.
            nextNode = previousNode.GetNextNode() as TextTreeTextNode;
 
            if (nextNode != null)
            {
                if (previousNode._positionRefCount == 0 &&
                    (nextNode._positionRefCount == 0 || (nextNode._referencedEdge == ElementEdge.AfterEnd)))
                {
                    // nextNode must take the place of previousNode, since nextNode
                    // may still have references.
                    previousNode.Remove();
                    // null _parentNode out so that if there's a bug and someone still references this node we'll hear about it.
                    previousNode._parentNode = null;
                    nextNode.Splay();
 
                    if (nextNode._symbolOffsetCache != -1)
                    {
                        nextNode._symbolOffsetCache -= previousNode._symbolCount;
                    }
                    nextNode._symbolCount += previousNode._symbolCount;
                }
                else if ((previousNode._positionRefCount == 0 || previousNode._referencedEdge == ElementEdge.BeforeStart) &&
                         nextNode._positionRefCount == 0)
                {
                    // The previous node must take the place of next one, since previousNode
                    // may still have references.
                    nextNode.Remove();
                    // null _parentNode out so that if there's a bug and someone still references this node we'll hear about it.
                    nextNode._parentNode = null;
                    previousNode.Splay();
 
                    previousNode._symbolCount += nextNode._symbolCount;
                }
            }
        }
 
        #endregion Private methods
 
        //------------------------------------------------------
        //
        //  Private Fields
        //
        //------------------------------------------------------
 
        #region Private Fields
 
        // Count of symbols of all siblings preceding this node.
        private int _leftSymbolCount;
 
        // Count of chars of all siblings preceding this node.
        private int _leftCharCount;
 
        // If this node is a local root, then ParentNode contains it.
        // Otherwise, this is the node parenting this node within its tree.
        private TextTreeNode _parentNode;
 
        // Left child node in a sibling tree.
        private TextTreeNode _leftChildNode;
 
        // Right child node in a sibling tree.
        private TextTreeNode _rightChildNode; // we could combine with _parentNode, if we can accept the increased complexity.
 
        // The TextContainer's generation when SymbolOffsetCache was last updated.
        // If the current generation doesn't match TextContainer.Generation, then
        // SymbolOffsetCache is invalid.
        private uint _generation;
 
        // Cached symbol offset.
        private int _symbolOffsetCache;
 
        // Count of symbols/chars covered by this node.
        private int _symbolCount;
 
        // The number of TextPositions referencing an edge of this node.
        // If _positionRefCount is zero, it's safe to merge with surrouding nodes.
        // we could combine _positionRefCount and _referencedEdge into a lazy allocated structure.
        // this can bit a single bitflag, we don't need 32 bits.
        private int _positionRefCount;
 
        // The edge referenced by one or more TextPositions.
        // Only valid when _positionRefCount > 0.
        private ElementEdge _referencedEdge;
 
        #endregion Private Fields
    }
}