aboutsummaryrefslogtreecommitdiffstats
path: root/Software/Visual_Studio/Scripting/Tango.Scripting.Editors/Highlighting/HighlightedInlineBuilder.cs
blob: ccfce3d49accc1421044c071378acac49b7586cc (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
// Copyright (c) AlphaSierraPapa for the SharpDevelop Team (for details please see \doc\copyright.txt)
// This code is distributed under the GNU LGPL (for details please see \doc\license.txt)

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Windows;
using System.Windows.Documents;
using System.Windows.Media;

namespace Tango.Scripting.Editors.Highlighting
{
	/// <summary>
	/// Takes a series of highlighting commands and stores them.
	/// Later, it can build inline objects (for use with WPF TextBlock) from the commands.
	/// </summary>
	/// <remarks>
	/// This class is not used in AvalonEdit - but it is useful for someone who wants to put a HighlightedLine
	/// into a TextBlock.
	/// In SharpDevelop, we use it to provide syntax highlighting inside the search results pad.
	/// </remarks>
	public sealed class HighlightedInlineBuilder
	{
		sealed class HighlightingState
		{
			internal Brush Foreground;
			internal Brush Background;
			internal FontFamily Family;
			internal FontWeight? Weight;
			internal FontStyle? Style;
			
			public HighlightingState Clone()
			{
				return new HighlightingState {
					Foreground = this.Foreground,
					Background = this.Background,
					Family = this.Family,
					Weight = this.Weight,
					Style = this.Style
				};
			}
		}
		
		readonly string text;
		List<int> stateChangeOffsets = new List<int>();
		List<HighlightingState> stateChanges = new List<HighlightingState>();
		
		int GetIndexForOffset(int offset)
		{
			if (offset < 0 || offset > text.Length)
				throw new ArgumentOutOfRangeException("offset");
			int index = stateChangeOffsets.BinarySearch(offset);
			if (index < 0) {
				index = ~index;
				if (offset < text.Length) {
					stateChanges.Insert(index, stateChanges[index - 1].Clone());
					stateChangeOffsets.Insert(index, offset);
				}
			}
			return index;
		}
		
		/// <summary>
		/// Creates a new HighlightedInlineBuilder instance.
		/// </summary>
		public HighlightedInlineBuilder(string text)
		{
			if (text == null)
				throw new ArgumentNullException("text");
			this.text = text;
			stateChangeOffsets.Add(0);
			stateChanges.Add(new HighlightingState());
		}
		
		HighlightedInlineBuilder(string text, int[] offsets, HighlightingState[] states)
		{
			this.text = text;
			stateChangeOffsets.AddRange(offsets);
			stateChanges.AddRange(states);
		}
		
		/// <summary>
		/// Gets the text.
		/// </summary>
		public string Text {
			get { return text; }
		}
		
		/// <summary>
		/// Applies the properties from the HighlightingColor to the specified text segment.
		/// </summary>
		public void SetHighlighting(int offset, int length, HighlightingColor color)
		{
			if (color == null)
				throw new ArgumentNullException("color");
			if (color.Foreground == null && color.FontStyle == null && color.FontWeight == null) {
				// Optimization: don't split the HighlightingState when we're not changing
				// any property. For example, the "Punctuation" color in C# is
				// empty by default.
				return;
			}
			int startIndex = GetIndexForOffset(offset);
			int endIndex = GetIndexForOffset(offset + length);
			for (int i = startIndex; i < endIndex; i++) {
				HighlightingState state = stateChanges[i];
				if (color.Foreground != null)
					state.Foreground = color.Foreground.GetBrush(null);
				if (color.Background != null)
					state.Background = color.Background.GetBrush(null);
				if (color.FontStyle != null)
					state.Style = color.FontStyle;
				if (color.FontWeight != null)
					state.Weight = color.FontWeight;
			}
		}
		
		/// <summary>
		/// Sets the foreground brush on the specified text segment.
		/// </summary>
		public void SetForeground(int offset, int length, Brush brush)
		{
			int startIndex = GetIndexForOffset(offset);
			int endIndex = GetIndexForOffset(offset + length);
			for (int i = startIndex; i < endIndex; i++) {
				stateChanges[i].Foreground = brush;
			}
		}
		
		/// <summary>
		/// Sets the background brush on the specified text segment.
		/// </summary>
		public void SetBackground(int offset, int length, Brush brush)
		{
			int startIndex = GetIndexForOffset(offset);
			int endIndex = GetIndexForOffset(offset + length);
			for (int i = startIndex; i < endIndex; i++) {
				stateChanges[i].Background = brush;
			}
		}
		
		/// <summary>
		/// Sets the font weight on the specified text segment.
		/// </summary>
		public void SetFontWeight(int offset, int length, FontWeight weight)
		{
			int startIndex = GetIndexForOffset(offset);
			int endIndex = GetIndexForOffset(offset + length);
			for (int i = startIndex; i < endIndex; i++) {
				stateChanges[i].Weight = weight;
			}
		}
		
		/// <summary>
		/// Sets the font style on the specified text segment.
		/// </summary>
		public void SetFontStyle(int offset, int length, FontStyle style)
		{
			int startIndex = GetIndexForOffset(offset);
			int endIndex = GetIndexForOffset(offset + length);
			for (int i = startIndex; i < endIndex; i++) {
				stateChanges[i].Style = style;
			}
		}
		
		/// <summary>
		/// Sets the font family on the specified text segment.
		/// </summary>
		public void SetFontFamily(int offset, int length, FontFamily family)
		{
			int startIndex = GetIndexForOffset(offset);
			int endIndex = GetIndexForOffset(offset + length);
			for (int i = startIndex; i < endIndex; i++) {
				stateChanges[i].Family = family;
			}
		}
		
		/// <summary>
		/// Creates WPF Run instances that can be used for TextBlock.Inlines.
		/// </summary>
		public Run[] CreateRuns()
		{
			Run[] runs = new Run[stateChanges.Count];
			for (int i = 0; i < runs.Length; i++) {
				int startOffset = stateChangeOffsets[i];
				int endOffset = i + 1 < stateChangeOffsets.Count ? stateChangeOffsets[i + 1] : text.Length;
				Run r = new Run(text.Substring(startOffset, endOffset - startOffset));
				HighlightingState state = stateChanges[i];
				if (state.Foreground != null)
					r.Foreground = state.Foreground;
				if (state.Background != null)
					r.Background = state.Background;
				if (state.Weight != null)
					r.FontWeight = state.Weight.Value;
				if (state.Family != null)
					r.FontFamily = state.Family;
				if (state.Style != null)
					r.FontStyle = state.Style.Value;
				runs[i] = r;
			}
			return runs;
		}
		
		/// <summary>
		/// Clones this HighlightedInlineBuilder.
		/// </summary>
		public HighlightedInlineBuilder Clone()
		{
			return new HighlightedInlineBuilder(this.text,
			                                    stateChangeOffsets.ToArray(), 
			                                    stateChanges.Select(sc => sc.Clone()).ToArray());
		}
	}
}
an>.Target = anchor2; n2.Target = anchor1; if (anchor1 == null) { // unmark n1 from deletion, mark n2 for deletion nodesToDelete.Remove(n1); MarkNodeForDelete(n2); anchor2.node = n1; } else if (anchor2 == null) { // unmark n2 from deletion, mark n1 for deletion nodesToDelete.Remove(n2); MarkNodeForDelete(n1); anchor1.node = n2; } else { anchor1.node = n2; anchor2.node = n1; } } } #endregion #region Remove or Replace text public void HandleTextChange(OffsetChangeMapEntry entry, DelayedEvents delayedEvents) { //Log("HandleTextChange(" + entry + ")"); if (entry.RemovalLength == 0) { // This is a pure insertion. // Unlike a replace with removal, a pure insertion can result in nodes at the same location // to split depending on their MovementType. // Thus, we handle this case on a separate code path // (the code below looks like it does something similar, but it can only split // the set of deletion survivors, not all nodes at an offset) InsertText(entry.Offset, entry.InsertionLength, entry.DefaultAnchorMovementIsBeforeInsertion); return; } // When handling a replacing text change, we need to: // - find all anchors in the deleted segment and delete them / move them to the appropriate // surviving side. // - adjust the segment size between the left and right side int offset = entry.Offset; int remainingRemovalLength = entry.RemovalLength; // if the text change is happening after the last anchor, we don't have to do anything if (root == null || offset >= root.totalLength) return; TextAnchorNode node = FindNode(ref offset); TextAnchorNode firstDeletionSurvivor = null; // go forward through the tree and delete all nodes in the removal segment while (node != null && offset + remainingRemovalLength > node.length) { TextAnchor anchor = (TextAnchor)node.Target; if (anchor != null && (anchor.SurviveDeletion || entry.RemovalNeverCausesAnchorDeletion)) { if (firstDeletionSurvivor == null) firstDeletionSurvivor = node; // This node should be deleted, but it wants to survive. // We'll just remove the deleted length segment, so the node will be positioned // in front of the removed segment. remainingRemovalLength -= node.length - offset; node.length = offset; offset = 0; UpdateAugmentedData(node); node = node.Successor; } else { // delete node TextAnchorNode s = node.Successor; remainingRemovalLength -= node.length; RemoveNode(node); // we already deleted the node, don't delete it twice nodesToDelete.Remove(node); if (anchor != null) anchor.OnDeleted(delayedEvents); node = s; } } // 'node' now is the first anchor after the deleted segment. // If there are no anchors after the deleted segment, 'node' is null. // firstDeletionSurvivor was set to the first node surviving deletion. // Because all non-surviving nodes up to 'node' were deleted, the node range // [firstDeletionSurvivor, node) now refers to the set of all deletion survivors. // do the remaining job of the removal if (node != null) { node.length -= remainingRemovalLength; Debug.Assert(node.length >= 0); } if (entry.InsertionLength > 0) { // we are performing a replacement if (firstDeletionSurvivor != null) { // We got deletion survivors which need to be split into BeforeInsertion // and AfterInsertion groups. // Take care that we don't regroup everything at offset, but only the deletion // survivors - from firstDeletionSurvivor (inclusive) to node (exclusive). // This ensures that nodes immediately before or after the replaced segment // stay where they are (independent from their MovementType) PerformInsertText(firstDeletionSurvivor, node, entry.InsertionLength, entry.DefaultAnchorMovementIsBeforeInsertion); } else if (node != null) { // No deletion survivors: // just perform the insertion node.length += entry.InsertionLength; } } if (node != null) { UpdateAugmentedData(node); } DeleteMarkedNodes(); } #endregion #region Node removal when TextAnchor was GC'ed void MarkNodeForDelete(TextAnchorNode node) { if (!nodesToDelete.Contains(node)) nodesToDelete.Add(node); } void DeleteMarkedNodes() { CheckProperties(); while (nodesToDelete.Count > 0) { int pos = nodesToDelete.Count - 1; TextAnchorNode n = nodesToDelete[pos]; // combine section of n with the following section TextAnchorNode s = n.Successor; if (s != null) { s.length += n.length; } RemoveNode(n); if (s != null) { UpdateAugmentedData(s); } nodesToDelete.RemoveAt(pos); CheckProperties(); } CheckProperties(); } #endregion #region FindNode /// <summary> /// Finds the node at the specified offset. /// After the method has run, offset is relative to the beginning of the returned node. /// </summary> TextAnchorNode FindNode(ref int offset) { TextAnchorNode n = root; while (true) { if (n.left != null) { if (offset < n.left.totalLength) { n = n.left; // descend into left subtree continue; } else { offset -= n.left.totalLength; // skip left subtree } } if (!n.IsAlive) MarkNodeForDelete(n); if (offset < n.length) { return n; // found correct node } else { offset -= n.length; // skip this node } if (n.right != null) { n = n.right; // descend into right subtree } else { // didn't find any node containing the offset return null; } } } #endregion #region UpdateAugmentedData void UpdateAugmentedData(TextAnchorNode n) { if (!n.IsAlive) MarkNodeForDelete(n); int totalLength = n.length; if (n.left != null) totalLength += n.left.totalLength; if (n.right != null) totalLength += n.right.totalLength; if (n.totalLength != totalLength) { n.totalLength = totalLength; if (n.parent != null) UpdateAugmentedData(n.parent); } } #endregion #region CreateAnchor public TextAnchor CreateAnchor(int offset) { Log("CreateAnchor(" + offset + ")"); TextAnchor anchor = new TextAnchor(document); anchor.node = new TextAnchorNode(anchor); if (root == null) { // creating the first text anchor root = anchor.node; root.totalLength = root.length = offset; } else if (offset >= root.totalLength) { // append anchor at end of tree anchor.node.totalLength = anchor.node.length = offset - root.totalLength; InsertAsRight(root.RightMost, anchor.node); } else { // insert anchor in middle of tree TextAnchorNode n = FindNode(ref offset); Debug.Assert(offset < n.length); // split segment 'n' at offset anchor.node.totalLength = anchor.node.length = offset; n.length -= offset; InsertBefore(n, anchor.node); } DeleteMarkedNodes(); return anchor; } void InsertBefore(TextAnchorNode node, TextAnchorNode newNode) { if (node.left == null) { InsertAsLeft(node, newNode); } else { InsertAsRight(node.left.RightMost, newNode); } } #endregion #region Red/Black Tree internal const bool RED = true; internal const bool BLACK = false; void InsertAsLeft(TextAnchorNode parentNode, TextAnchorNode newNode) { Debug.Assert(parentNode.left == null); parentNode.left = newNode; newNode.parent = parentNode; newNode.color = RED; UpdateAugmentedData(parentNode); FixTreeOnInsert(newNode); } void InsertAsRight(TextAnchorNode parentNode, TextAnchorNode newNode) { Debug.Assert(parentNode.right == null); parentNode.right = newNode; newNode.parent = parentNode; newNode.color = RED; UpdateAugmentedData(parentNode); FixTreeOnInsert(newNode); } void FixTreeOnInsert(TextAnchorNode node) { Debug.Assert(node != null); Debug.Assert(node.color == RED); Debug.Assert(node.left == null || node.left.color == BLACK); Debug.Assert(node.right == null || node.right.color == BLACK); TextAnchorNode parentNode = node.parent; if (parentNode == null) { // we inserted in the root -> the node must be black // since this is a root node, making the node black increments the number of black nodes // on all paths by one, so it is still the same for all paths. node.color = BLACK; return; } if (parentNode.color == BLACK) { // if the parent node where we inserted was black, our red node is placed correctly. // since we inserted a red node, the number of black nodes on each path is unchanged // -> the tree is still balanced return; } // parentNode is red, so there is a conflict here! // because the root is black, parentNode is not the root -> there is a grandparent node TextAnchorNode grandparentNode = parentNode.parent; TextAnchorNode uncleNode = Sibling(parentNode); if (uncleNode != null && uncleNode.color == RED) { parentNode.color = BLACK; uncleNode.color = BLACK; grandparentNode.color = RED; FixTreeOnInsert(grandparentNode); return; } // now we know: parent is red but uncle is black // First rotation: if (node == parentNode.right && parentNode == grandparentNode.left) { RotateLeft(parentNode); node = node.left; } else if (node == parentNode.left && parentNode == grandparentNode.right) { RotateRight(parentNode); node = node.right; } // because node might have changed, reassign variables: parentNode = node.parent; grandparentNode = parentNode.parent; // Now recolor a bit: parentNode.color = BLACK; grandparentNode.color = RED; // Second rotation: if (node == parentNode.left && parentNode == grandparentNode.left) { RotateRight(grandparentNode); } else { // because of the first rotation, this is guaranteed: Debug.Assert(node == parentNode.right && parentNode == grandparentNode.right); RotateLeft(grandparentNode); } } void RemoveNode(TextAnchorNode removedNode) { if (removedNode.left != null && removedNode.right != null) { // replace removedNode with it's in-order successor TextAnchorNode leftMost = removedNode.right.LeftMost; RemoveNode(leftMost); // remove leftMost from its current location // and overwrite the removedNode with it ReplaceNode(removedNode, leftMost); leftMost.left = removedNode.left; if (leftMost.left != null) leftMost.left.parent = leftMost; leftMost.right = removedNode.right; if (leftMost.right != null) leftMost.right.parent = leftMost; leftMost.color = removedNode.color; UpdateAugmentedData(leftMost); if (leftMost.parent != null) UpdateAugmentedData(leftMost.parent); return; } // now either removedNode.left or removedNode.right is null // get the remaining child TextAnchorNode parentNode = removedNode.parent; TextAnchorNode childNode = removedNode.left ?? removedNode.right; ReplaceNode(removedNode, childNode); if (parentNode != null) UpdateAugmentedData(parentNode); if (removedNode.color == BLACK) { if (childNode != null && childNode.color == RED) { childNode.color = BLACK; } else { FixTreeOnDelete(childNode, parentNode); } } } void FixTreeOnDelete(TextAnchorNode node, TextAnchorNode parentNode) { Debug.Assert(node == null || node.parent == parentNode); if (parentNode == null) return; // warning: node may be null TextAnchorNode sibling = Sibling(node, parentNode); if (sibling.color == RED) { parentNode.color = RED; sibling.color = BLACK; if (node == parentNode.left) { RotateLeft(parentNode); } else { RotateRight(parentNode); } sibling = Sibling(node, parentNode); // update value of sibling after rotation } if (parentNode.color == BLACK && sibling.color == BLACK && GetColor(sibling.left) == BLACK && GetColor(sibling.right) == BLACK) { sibling.color = RED; FixTreeOnDelete(parentNode, parentNode.parent); return; } if (parentNode.color == RED && sibling.color == BLACK && GetColor(sibling.left) == BLACK && GetColor(sibling.right) == BLACK) { sibling.color = RED; parentNode.color = BLACK; return; } if (node == parentNode.left && sibling.color == BLACK && GetColor(sibling.left) == RED && GetColor(sibling.right) == BLACK) { sibling.color = RED; sibling.left.color = BLACK; RotateRight(sibling); } else if (node == parentNode.right && sibling.color == BLACK && GetColor(sibling.right) == RED && GetColor(sibling.left) == BLACK) { sibling.color = RED; sibling.right.color = BLACK; RotateLeft(sibling); } sibling = Sibling(node, parentNode); // update value of sibling after rotation sibling.color = parentNode.color; parentNode.color = BLACK; if (node == parentNode.left) { if (sibling.right != null) { Debug.Assert(sibling.right.color == RED); sibling.right.color = BLACK; } RotateLeft(parentNode); } else { if (sibling.left != null) { Debug.Assert(sibling.left.color == RED); sibling.left.color = BLACK; } RotateRight(parentNode); } } void ReplaceNode(TextAnchorNode replacedNode, TextAnchorNode newNode) { if (replacedNode.parent == null) { Debug.Assert(replacedNode == root); root = newNode; } else { if (replacedNode.parent.left == replacedNode) replacedNode.parent.left = newNode; else replacedNode.parent.right = newNode; } if (newNode != null) { newNode.parent = replacedNode.parent; } replacedNode.parent = null; } void RotateLeft(TextAnchorNode p) { // let q be p's right child TextAnchorNode q = p.right; Debug.Assert(q != null); Debug.Assert(q.parent == p); // set q to be the new root ReplaceNode(p, q); // set p's right child to be q's left child p.right = q.left; if (p.right != null) p.right.parent = p; // set q's left child to be p q.left = p; p.parent = q; UpdateAugmentedData(p); UpdateAugmentedData(q); } void RotateRight(TextAnchorNode p) { // let q be p's left child TextAnchorNode q = p.left; Debug.Assert(q != null); Debug.Assert(q.parent == p); // set q to be the new root ReplaceNode(p, q); // set p's left child to be q's right child p.left = q.right; if (p.left != null) p.left.parent = p; // set q's right child to be p q.right = p; p.parent = q; UpdateAugmentedData(p); UpdateAugmentedData(q); } static TextAnchorNode Sibling(TextAnchorNode node) { if (node == node.parent.left) return node.parent.right; else return node.parent.left; } static TextAnchorNode Sibling(TextAnchorNode node, TextAnchorNode parentNode) { Debug.Assert(node == null || node.parent == parentNode); if (node == parentNode.left) return parentNode.right; else return parentNode.left; } static bool GetColor(TextAnchorNode node) { return node != null ? node.color : BLACK; } #endregion #region CheckProperties [Conditional("DATACONSISTENCYTEST")] internal void CheckProperties() { #if DEBUG if (root != null) { CheckProperties(root); // check red-black property: int blackCount = -1; CheckNodeProperties(root, null, RED, 0, ref blackCount); } #endif } #if DEBUG void CheckProperties(TextAnchorNode node) { int totalLength = node.length; if (node.left != null) { CheckProperties(node.left); totalLength += node.left.totalLength; } if (node.right != null) { CheckProperties(node.right); totalLength += node.right.totalLength; } Debug.Assert(node.totalLength == totalLength); } /* 1. A node is either red or black. 2. The root is black. 3. All leaves are black. (The leaves are the NIL children.) 4. Both children of every red node are black. (So every red node must have a black parent.) 5. Every simple path from a node to a descendant leaf contains the same number of black nodes. (Not counting the leaf node.) */ void CheckNodeProperties(TextAnchorNode node, TextAnchorNode parentNode, bool parentColor, int blackCount, ref int expectedBlackCount) { if (node == null) return; Debug.Assert(node.parent == parentNode); if (parentColor == RED) { Debug.Assert(node.color == BLACK); } if (node.color == BLACK) { blackCount++; } if (node.left == null && node.right == null) { // node is a leaf node: if (expectedBlackCount == -1) expectedBlackCount = blackCount; else Debug.Assert(expectedBlackCount == blackCount); } CheckNodeProperties(node.left, node, node.color, blackCount, ref expectedBlackCount); CheckNodeProperties(node.right, node, node.color, blackCount, ref expectedBlackCount); } #endif #endregion #region GetTreeAsString #if DEBUG [System.Diagnostics.CodeAnalysis.SuppressMessage("Microsoft.Performance", "CA1811:AvoidUncalledPrivateCode")] public string GetTreeAsString() { if (root == null) return "<empty tree>"; StringBuilder b = new StringBuilder(); AppendTreeToString(root, b, 0); return b.ToString(); } static void AppendTreeToString(TextAnchorNode node, StringBuilder b, int indent) { if (node.color == RED) b.Append("RED "); else b.Append("BLACK "); b.AppendLine(node.ToString()); indent += 2; if (node.left != null) { b.Append(' ', indent); b.Append("L: "); AppendTreeToString(node.left, b, indent); } if (node.right != null) { b.Append(' ', indent); b.Append("R: "); AppendTreeToString(node.right, b, indent); } } #endif #endregion } }