src/Workspaces/CoreTest/Differencing/LongestCommonSubsequenceTests.cs - main - githubmirror/roslyn

src/Workspaces/CoreTest/Differencing/LongestCommonSubsequenceTests.cs
335 строк10 KB
Cyrus Najmabadi
Use implicit object creation expressions
13 сен 2025, 01:48
13 сен 2025, 01:484c6a36a
// 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.

using System;
using System.Collections.Generic;
using System.Text;
using Xunit;

namespace Microsoft.CodeAnalysis.Differencing.UnitTests;

public sealed class LongestCommonSubsequenceTests
{
    private readonly LongestCommonSubsequenceString lcs = new();

    private sealed class LongestCommonSubsequenceString : LongestCommonSubsequence<string>
    {
        protected override bool ItemsEqual(string oldSequence, int oldIndex, string newSequence, int newIndex)
            => oldSequence[oldIndex] == newSequence[newIndex];

        public IEnumerable<KeyValuePair<int, int>> GetMatchingPairs(string oldSequence, string newSequence)
            => GetMatchingPairs(oldSequence, oldSequence.Length, newSequence, newSequence.Length);

        public IEnumerable<SequenceEdit> GetEdits(string oldSequence, string newSequence)
            => GetEdits(oldSequence, oldSequence.Length, newSequence, newSequence.Length);

        public double ComputeDistance(string oldSequence, string newSequence)
            => ComputeDistance(oldSequence, oldSequence.Length, newSequence, newSequence.Length);
    }

    private static void VerifyMatchingPairs(IEnumerable<KeyValuePair<int, int>> actualPairs, string expectedPairsStr)
    {
        var sb = new StringBuilder(expectedPairsStr.Length);
        foreach (var actPair in actualPairs)
        {
            sb.AppendFormat("[{0},{1}]", actPair.Key, actPair.Value);
        }

        var actualPairsStr = sb.ToString();
        Assert.Equal(expectedPairsStr, actualPairsStr);
    }

    private static void VerifyEdits(string oldStr, string newStr, IEnumerable<SequenceEdit> edits)
    {
        var oldChars = oldStr.ToCharArray();
        var newChars = new char[newStr.Length];

        foreach (var edit in edits)
        {
            Assert.True(edit.Kind is EditKind.Delete or EditKind.Insert or EditKind.Update);
            switch (edit.Kind)
            {
                case EditKind.Delete:
                    Assert.True(edit.OldIndex < oldStr.Length);
                    oldChars[edit.OldIndex] = '\0';
                    break;

                case EditKind.Insert:
                    Assert.True(edit.NewIndex < newStr.Length);
                    newChars[edit.NewIndex] = newStr[edit.NewIndex];
                    break;

                case EditKind.Update:
                    Assert.True(edit.OldIndex < oldStr.Length);
                    Assert.True(edit.NewIndex < newStr.Length);
                    newChars[edit.NewIndex] = oldStr[edit.OldIndex];
                    oldChars[edit.OldIndex] = '\0';
                    break;
            }
        }

        var editedStr = new String(newChars);
        Assert.Equal(editedStr, newStr);

        Array.ForEach(oldChars, (c) => { Assert.Equal('\0', c); });
    }

    [Fact]
    public void EmptyStrings()
    {
        var str1 = "";
        var str2 = "";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.0, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void InsertToEmpty()
    {
        var str1 = "";
        var str2 = "ABC";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(1.0, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void InsertAtBeginning()
    {
        var str1 = "ABC";
        var str2 = "XYZABC";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[2,5][1,4][0,3]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.5, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void InsertAtEnd()
    {
        var str1 = "ABC";
        var str2 = "ABCXYZ";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[2,2][1,1][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.5, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void InsertInMidlle()
    {
        var str1 = "ABC";
        var str2 = "ABXYC";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[2,4][1,1][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.4, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void DeleteToEmpty()
    {
        var str1 = "ABC";
        var str2 = "";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(1.0, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void DeleteAtBeginning()
    {
        var str1 = "ABCD";
        var str2 = "C";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[2,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.75, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void DeleteAtEnd()
    {
        var str1 = "ABCD";
        var str2 = "AB";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[1,1][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.5, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void DeleteInMiddle()
    {
        var str1 = "ABCDE";
        var str2 = "ADE";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[4,2][3,1][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.4, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void ReplaceAll()
    {
        var str1 = "ABC";
        var str2 = "XYZ";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(1.0, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void ReplaceAtBeginning()
    {
        var str1 = "ABCD";
        var str2 = "XYD";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[3,2]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.75, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void ReplaceAtEnd()
    {
        var str1 = "ABCD";
        var str2 = "ABXYZ";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[1,1][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.6, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void ReplaceInMiddle()
    {
        var str1 = "ABCDE";
        var str2 = "AXDE";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[4,3][3,2][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.4, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void Combination1()
    {
        var str1 = "ABBCDEFIJ";
        var str2 = "AABDEEGH";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[5,4][4,3][1,2][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.556, lcs.ComputeDistance(str1, str2), precision: 3);
    }

    [Fact]
    public void Combination2()
    {
        var str1 = "AAABBCCDDD";
        var str2 = "ABXCD";

        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[7,4][5,3][3,1][0,0]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.6, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void Combination3()
    {
        var str1 = "ABCABBA";
        var str2 = "CBABAC";

        // 2 possible matches:
        // "[6,4][4,3][3,2][1,1]" <- this one is backwards compatible
        // "[6,4][4,3][3,2][2,0]"
        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[6,4][4,3][3,2][1,1]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.429, lcs.ComputeDistance(str1, str2), precision: 3);
    }

    [Fact]
    public void Reorder1()
    {
        var str1 = "AB";
        var str2 = "BA";

        // 2 possible matches:
        // "[0,1]" <- this one is backwards compatible
        // "[1,0]"
        VerifyMatchingPairs(lcs.GetMatchingPairs(str1, str2), "[0,1]");

        VerifyEdits(str1, str2, lcs.GetEdits(str1, str2));

        Assert.Equal(0.5, lcs.ComputeDistance(str1, str2));
    }

    [Fact]
    public void LongString()
    {
        var s = "A";

        var x9 = new string('x', 9);
        var x10 = new string('x', 10);
        var x99 = new string('x', 99);
        var x1000 = new string('x', 1000);

        var y1000 = new string('y', 1000);

        var sx9 = s + x9;
        var sx99 = s + x99;
        var sx1000 = s + new string('x', 1000);
        var sx100000000 = s + new string('x', 100000000);

        Assert.Equal(0.900, lcs.ComputeDistance(s, sx9), precision: 3);
        Assert.Equal(0.990, lcs.ComputeDistance(s, sx99), precision: 3);
        Assert.Equal(1.000, lcs.ComputeDistance(s, sx1000), precision: 3);
        Assert.Equal(1.000, lcs.ComputeDistance(s, sx100000000), precision: 3);

        Assert.Equal(0.900, lcs.ComputeDistance(sx9, s), precision: 3);
        Assert.Equal(0.990, lcs.ComputeDistance(sx99, s), precision: 3);
        Assert.Equal(1.000, lcs.ComputeDistance(sx1000, s), precision: 3);
        Assert.Equal(1.000, lcs.ComputeDistance(sx100000000, s), precision: 3);

        Assert.Equal(1.000, lcs.ComputeDistance(x10 + y1000, x10), precision: 3);
        Assert.Equal(0.5, lcs.ComputeDistance(x1000 + y1000, x1000), precision: 3);
    }
}