File: Tagging\TagSpanIntervalTreeTests.cs
Web Access
Project: src\src\EditorFeatures\Test\Microsoft.CodeAnalysis.EditorFeatures.UnitTests.csproj (Microsoft.CodeAnalysis.EditorFeatures.UnitTests)
// 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.
 
#nullable disable
 
using System.Collections.Generic;
using System.Linq;
using Microsoft.CodeAnalysis.Collections;
using Microsoft.CodeAnalysis.Editor.Shared.Tagging;
using Microsoft.CodeAnalysis.Test.Utilities;
using Microsoft.CodeAnalysis.Text.Shared.Extensions;
using Microsoft.VisualStudio.Text;
using Microsoft.VisualStudio.Text.Tagging;
using Roslyn.Test.EditorUtilities;
using Xunit;
 
namespace Microsoft.CodeAnalysis.Editor.UnitTests.Tagging;
 
[UseExportProvider]
public class TagSpanIntervalTreeTests
{
    private static (TagSpanIntervalTree<ITextMarkerTag>, ITextBuffer) CreateTree(string text, params Span[] spans)
    {
        var exportProvider = EditorTestCompositions.Editor.ExportProviderFactory.CreateExportProvider();
        var buffer = EditorFactory.CreateBuffer(exportProvider, text);
        var tags = new SegmentedList<TagSpan<ITextMarkerTag>>(
            spans.Select(s => new TagSpan<ITextMarkerTag>(new SnapshotSpan(buffer.CurrentSnapshot, s), new TextMarkerTag(string.Empty))));
        return (new TagSpanIntervalTree<ITextMarkerTag>(buffer.CurrentSnapshot, SpanTrackingMode.EdgeInclusive, tags), buffer);
    }
 
    private static IReadOnlyList<TagSpan<TTag>> GetIntersectingSpans<TTag>(
        TagSpanIntervalTree<TTag> tree, SnapshotSpan snapshotSpan)
        where TTag : ITag
    {
        var result = new SegmentedList<TagSpan<TTag>>();
        tree.AddIntersectingTagSpans(snapshotSpan, result);
        return result;
    }
 
    [Fact]
    public void TestEmptyTree()
    {
        var (tree, buffer) = CreateTree(string.Empty);
 
        Assert.Empty(GetIntersectingSpans(tree, buffer.CurrentSnapshot.GetFullSpan()));
    }
 
    [Fact]
    public void TestSingleSpan()
    {
        var (tree, buffer) = CreateTree("Hello, World", new Span(0, 5));
 
        Assert.Equal(new Span(0, 5), GetIntersectingSpans(tree, buffer.CurrentSnapshot.GetFullSpan()).Single().Span);
    }
 
    [Fact]
    public void TestSingleIntersectingSpanAtStartWithEdit()
    {
        var (tree, buffer) = CreateTree("Hello, World", new Span(7, 5));
        buffer.Insert(0, new string('c', 100));
 
        // The span should start at 107
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 107, 0));
        Assert.Equal(new Span(107, 5), spans.Single().Span);
    }
 
    [Fact]
    public void TestSingleIntersectingSpanAtEndWithEdit()
    {
        var (tree, buffer) = CreateTree("Hello, World", new Span(7, 5));
        buffer.Insert(0, new string('c', 100));
 
        // The span should end at 112
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 112, 0));
        Assert.Equal(new Span(107, 5), spans.Single().Span);
    }
 
    [Fact]
    public void TestManySpansWithEdit()
    {
        // Create a buffer with the second half of the buffer covered with spans
        var (tree, buffer) = CreateTree(new string('c', 100), Enumerable.Range(50, count: 50).Select(s => new Span(s, 1)).ToArray());
        buffer.Insert(0, new string('c', 100));
 
        // We should have 50 spans if we start looking at just the end
        Assert.Equal(50, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 150, 50)).Count());
 
        // And we should have 26 here. We directly cover 25 spans, and we touch one more
        Assert.Equal(26, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 175, 25)).Count());
    }
 
    [Fact]
    public void TestManySpansWithEdit2()
    {
        // Cover the full buffer with spans
        var (tree, buffer) = CreateTree(new string('c', 100), Enumerable.Range(0, count: 100).Select(s => new Span(s, 1)).ToArray());
        buffer.Insert(0, new string('c', 100));
 
        // We should see one span anywhere in the beginning of the buffer, since this is edge inclusive
        Assert.Equal(1, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 0, 1)).Count());
        Assert.Equal(1, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 50, 1)).Count());
 
        // We should see two at position 100 (the first span that is now expanded, and the second of width 1)
        Assert.Equal(2, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 100, 1)).Count());
    }
 
    [Fact]
    public void TestManySpansWithDeleteAndEditAtStart()
    {
        // Cover the full buffer with spans
        var (tree, buffer) = CreateTree(new string('c', 100), Enumerable.Range(0, count: 100).Select(s => new Span(s, 1)).ToArray());
 
        buffer.Delete(new Span(0, 50));
        buffer.Insert(0, new string('c', 50));
 
        // We should see 51 spans intersecting the start. When we did the delete, we contracted 50 spans to size
        // zero, and then the insert will have expanded all of those, plus the span right next to it.
        Assert.Equal(51, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 0, 1)).Count());
    }
 
    [Fact]
    public void TestManySpansWithDeleteAndEditAtEnd()
    {
        // Cover the full buffer with spans
        var (tree, buffer) = CreateTree(new string('c', 100), Enumerable.Range(0, count: 100).Select(s => new Span(s, 1)).ToArray());
 
        buffer.Delete(new Span(50, 50));
        buffer.Insert(50, new string('c', 50));
 
        // We should see 51 spans intersecting the end. When we did the delete, we contracted 50 spans to size zero,
        // and then the insert will have expanded all of those, plus the span right next to it.
        Assert.Equal(51, GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 99, 1)).Count());
    }
 
    [Fact]
    public void TestTagSpanOrdering()
    {
        // Cover the full buffer with spans
        var (tree, buffer) = CreateTree(new string('c', 100), Enumerable.Range(0, count: 100).Select(s => new Span(s, 1)).ToArray());
 
        var lastStart = -1;
        foreach (var tag in GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, 0, buffer.CurrentSnapshot.Length)))
        {
            Assert.True(lastStart < tag.Span.Start.Position);
            lastStart = tag.Span.Start.Position;
        }
    }
 
    [Fact]
    public void TestEmptySpanIntersects1()
    {
        var (tree, buffer) = CreateTree("goo", new Span(0, 0));
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, new Span(0, 0)));
        Assert.Single(spans);
    }
 
    [Fact]
    public void TestEmptySpanIntersects2()
    {
        var (tree, buffer) = CreateTree("goo", new Span(0, 0));
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, new Span(0, "goo".Length)));
        Assert.Single(spans);
    }
 
    [Fact]
    public void TestEmptySpanIntersects3()
    {
        var (tree, buffer) = CreateTree("goo", new Span(1, 0));
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, new Span(0, 1)));
        Assert.Single(spans);
    }
 
    [Fact]
    public void TestEmptySpanIntersects4()
    {
        var (tree, buffer) = CreateTree("goo", new Span(1, 0));
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, new Span(1, 0)));
        Assert.Single(spans);
    }
 
    [Fact]
    public void TestEmptySpanIntersects5()
    {
        var (tree, buffer) = CreateTree("goo", new Span(1, 0));
        var spans = GetIntersectingSpans(tree, new SnapshotSpan(buffer.CurrentSnapshot, new Span(1, 1)));
        Assert.Single(spans);
    }
}