File: Differencing\LongestCommonSubsequenceTests.cs
Web Access
Project: src\src\Workspaces\CoreTest\Microsoft.CodeAnalysis.Workspaces.UnitTests.csproj (Microsoft.CodeAnalysis.Workspaces.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;
using System.Text;
using Xunit;
using System.Collections.Generic;
 
namespace Microsoft.CodeAnalysis.Differencing.UnitTests
{
    public class LongestCommonSubsequenceTests
    {
        private readonly LongestCommonSubsequenceString lcs = new LongestCommonSubsequenceString();
 
        private 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);
        }
    }
}