279 lines
10 KiB
C#
279 lines
10 KiB
C#
// Copyright (c) 2014 AlphaSierraPapa for the SharpDevelop Team
|
|
//
|
|
// Permission is hereby granted, free of charge, to any person obtaining a copy of this
|
|
// software and associated documentation files (the "Software"), to deal in the Software
|
|
// without restriction, including without limitation the rights to use, copy, modify, merge,
|
|
// publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons
|
|
// to whom the Software is furnished to do so, subject to the following conditions:
|
|
//
|
|
// The above copyright notice and this permission notice shall be included in all copies or
|
|
// substantial portions of the Software.
|
|
//
|
|
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED,
|
|
// INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR
|
|
// PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE
|
|
// FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR
|
|
// OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
|
|
// DEALINGS IN THE SOFTWARE.
|
|
|
|
using System;
|
|
using System.Diagnostics;
|
|
|
|
namespace Unity.CodeEditor.Document
|
|
{
|
|
/// <summary>
|
|
/// A segment that can be put into a <see cref="TextSegmentCollection{T}"/>.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// <para>
|
|
/// A <see cref="TextSegment"/> can be stand-alone or part of a <see cref="TextSegmentCollection{T}"/>.
|
|
/// If the segment is stored inside a TextSegmentCollection, its Offset and Length will be updated by that collection.
|
|
/// </para>
|
|
/// <para>
|
|
/// When the document changes, the offsets of all text segments in the TextSegmentCollection will be adjusted accordingly.
|
|
/// Start offsets move like <see cref="AnchorMovementType">AnchorMovementType.AfterInsertion</see>,
|
|
/// end offsets move like <see cref="AnchorMovementType">AnchorMovementType.BeforeInsertion</see>
|
|
/// (i.e. the segment will always stay as small as possible).</para>
|
|
/// <para>
|
|
/// If a document change causes a segment to be deleted completely, it will be reduced to length 0, but segments are
|
|
/// never automatically removed from the collection.
|
|
/// Segments with length 0 will never expand due to document changes, and they move as <c>AfterInsertion</c>.
|
|
/// </para>
|
|
/// <para>
|
|
/// Thread-safety: a TextSegmentCollection that is connected to a <see cref="TextDocument"/> may only be used on that document's owner thread.
|
|
/// A disconnected TextSegmentCollection is safe for concurrent reads, but concurrent access is not safe when there are writes.
|
|
/// Keep in mind that reading the Offset properties of a text segment inside the collection is a read access on the
|
|
/// collection; and setting an Offset property of a text segment is a write access on the collection.
|
|
/// </para>
|
|
/// </remarks>
|
|
/// <seealso cref="ISegment"/>
|
|
/// <seealso cref="AnchorSegment"/>
|
|
/// <seealso cref="TextSegmentCollection{T}"/>
|
|
internal class TextSegment : ISegment
|
|
{
|
|
internal ISegmentTree OwnerTree { get; set; }
|
|
internal TextSegment Left { get; set; }
|
|
internal TextSegment Right { get; set; }
|
|
internal TextSegment Parent { get; set; }
|
|
|
|
/// <summary>
|
|
/// The color of the segment in the red/black tree.
|
|
/// </summary>
|
|
internal bool Color { get; set; }
|
|
|
|
/// <summary>
|
|
/// The "length" of the node (distance to previous node)
|
|
/// </summary>
|
|
internal int NodeLength { get; set; }
|
|
|
|
/// <summary>
|
|
/// The total "length" of this subtree.
|
|
/// </summary>
|
|
internal int TotalNodeLength { get; set; } // totalNodeLength = nodeLength + left.totalNodeLength + right.totalNodeLength
|
|
|
|
/// <summary>
|
|
/// The length of the segment (do not confuse with nodeLength).
|
|
/// </summary>
|
|
internal int SegmentLength { get; set; }
|
|
|
|
/// <summary>
|
|
/// distanceToMaxEnd = Max(segmentLength,
|
|
/// left.distanceToMaxEnd + left.Offset - Offset,
|
|
/// left.distanceToMaxEnd + right.Offset - Offset)
|
|
/// </summary>
|
|
internal int DistanceToMaxEnd { get; set; }
|
|
|
|
int ISegment.Offset => StartOffset;
|
|
|
|
/// <summary>
|
|
/// Gets whether this segment is connected to a TextSegmentCollection and will automatically
|
|
/// update its offsets.
|
|
/// </summary>
|
|
protected bool IsConnectedToCollection => OwnerTree != null;
|
|
|
|
/// <summary>
|
|
/// Gets/Sets the start offset of the segment.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// When setting the start offset, the end offset will change, too: the Length of the segment will stay constant.
|
|
/// </remarks>
|
|
internal int StartOffset
|
|
{
|
|
get
|
|
{
|
|
// If the segment is not connected to a tree, we store the offset in "nodeLength".
|
|
// Otherwise, "nodeLength" contains the distance to the start offset of the previous node
|
|
Debug.Assert(!(OwnerTree == null && Parent != null));
|
|
Debug.Assert(!(OwnerTree == null && Left != null));
|
|
|
|
var n = this;
|
|
var offset = n.NodeLength;
|
|
if (n.Left != null)
|
|
offset += n.Left.TotalNodeLength;
|
|
while (n.Parent != null)
|
|
{
|
|
if (n == n.Parent.Right)
|
|
{
|
|
if (n.Parent.Left != null)
|
|
offset += n.Parent.Left.TotalNodeLength;
|
|
offset += n.Parent.NodeLength;
|
|
}
|
|
n = n.Parent;
|
|
}
|
|
return offset;
|
|
}
|
|
set
|
|
{
|
|
if (value < 0)
|
|
throw new ArgumentOutOfRangeException(nameof(value), "Offset must not be negative");
|
|
if (StartOffset != value)
|
|
{
|
|
// need a copy of the variable because ownerTree.Remove() sets this.ownerTree to null
|
|
var ownerTree = OwnerTree;
|
|
if (ownerTree != null)
|
|
{
|
|
ownerTree.Remove(this);
|
|
NodeLength = value;
|
|
ownerTree.Add(this);
|
|
}
|
|
else
|
|
{
|
|
NodeLength = value;
|
|
}
|
|
OnSegmentChanged();
|
|
}
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets/Sets the end offset of the segment.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// Setting the end offset will change the length, the start offset will stay constant.
|
|
/// </remarks>
|
|
public int EndOffset
|
|
{
|
|
get => StartOffset + Length;
|
|
set
|
|
{
|
|
var newLength = value - StartOffset;
|
|
if (newLength < 0)
|
|
throw new ArgumentOutOfRangeException(nameof(value), "EndOffset must be greater or equal to StartOffset");
|
|
Length = newLength;
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets/Sets the length of the segment.
|
|
/// </summary>
|
|
/// <remarks>
|
|
/// Setting the length will change the end offset, the start offset will stay constant.
|
|
/// </remarks>
|
|
public int Length
|
|
{
|
|
get => SegmentLength;
|
|
set
|
|
{
|
|
if (value < 0)
|
|
throw new ArgumentOutOfRangeException(nameof(value), "Length must not be negative");
|
|
if (SegmentLength != value)
|
|
{
|
|
SegmentLength = value;
|
|
OwnerTree?.UpdateAugmentedData(this);
|
|
OnSegmentChanged();
|
|
}
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// This method gets called when the StartOffset/Length/EndOffset properties are set.
|
|
/// It is not called when StartOffset/Length/EndOffset change due to document changes
|
|
/// </summary>
|
|
protected virtual void OnSegmentChanged()
|
|
{
|
|
}
|
|
|
|
internal TextSegment LeftMost
|
|
{
|
|
get
|
|
{
|
|
var node = this;
|
|
while (node.Left != null)
|
|
node = node.Left;
|
|
return node;
|
|
}
|
|
}
|
|
|
|
internal TextSegment RightMost
|
|
{
|
|
get
|
|
{
|
|
var node = this;
|
|
while (node.Right != null)
|
|
node = node.Right;
|
|
return node;
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the inorder successor of the node.
|
|
/// </summary>
|
|
internal TextSegment Successor
|
|
{
|
|
get
|
|
{
|
|
if (Right != null)
|
|
{
|
|
return Right.LeftMost;
|
|
}
|
|
var node = this;
|
|
TextSegment oldNode;
|
|
do
|
|
{
|
|
oldNode = node;
|
|
node = node.Parent;
|
|
// go up until we are coming out of a left subtree
|
|
} while (node != null && node.Right == oldNode);
|
|
return node;
|
|
}
|
|
}
|
|
|
|
/// <summary>
|
|
/// Gets the inorder predecessor of the node.
|
|
/// </summary>
|
|
internal TextSegment Predecessor
|
|
{
|
|
get
|
|
{
|
|
if (Left != null)
|
|
{
|
|
return Left.RightMost;
|
|
}
|
|
var node = this;
|
|
TextSegment oldNode;
|
|
do
|
|
{
|
|
oldNode = node;
|
|
node = node.Parent;
|
|
// go up until we are coming out of a right subtree
|
|
} while (node != null && node.Left == oldNode);
|
|
return node;
|
|
}
|
|
}
|
|
|
|
#if DEBUG
|
|
internal string ToDebugString()
|
|
{
|
|
return
|
|
$"[nodeLength={NodeLength} totalNodeLength={TotalNodeLength} distanceToMaxEnd={DistanceToMaxEnd} MaxEndOffset={StartOffset + DistanceToMaxEnd}]";
|
|
}
|
|
#endif
|
|
|
|
/// <inheritdoc/>
|
|
public override string ToString()
|
|
{
|
|
return $"[{GetType().Name} Offset={StartOffset} Length={Length} EndOffset={EndOffset}]";
|
|
}
|
|
}
|
|
}
|