//******************************************************************************************************//  DiffMatchPatch.cs - Gbtc////  Copyright © 2019, Grid Protection Alliance.  All Rights Reserved.////  Licensed to the Grid Protection Alliance (GPA) under one or more contributor license agreements. See//  the NOTICE file distributed with this work for additional information regarding copyright ownership.//  The GPA licenses this file to you under the MIT License (MIT), the "License"; you may not use this//  file except in compliance with the License. You may obtain a copy of the License at:////      http://opensource.org/licenses/MIT////  Unless agreed to in writing, the subject software distributed under the License is distributed on an//  "AS-IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. Refer to the//  License for the specific language governing permissions and limitations.////  Code Modification History://  ----------------------------------------------------------------------------------------------------//  09/17/2019 - Stephen C. Wills//       Generated original version of source code.////****************************************************************************************************** #region [ Contributor License Agreements ] /* * Diff Match and Patch * Copyright 2018 The diff-match-patch Authors. * https://github.com/google/diff-match-patch * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. * You may obtain a copy of the License at * *   http://www.apache.org/licenses/LICENSE-2.0 * * Unless required by applicable law or agreed to in writing, software * distributed under the License is distributed on an "AS IS" BASIS, * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. * See the License for the specific language governing permissions and * limitations under the License. */ #endregion using System;using System.Collections.Generic;using System.Diagnostics.CodeAnalysis;using System.Linq;using System.Text;using System.Text.RegularExpressions;using System.Web; // ReSharper disable UnusedMember.Globalnamespace GSF.Text{    internal static class CompatibilityExtensions    {        // JScript splice function        public static List<T> Splice<T>(this List<T> input, int start, int count, params T[] objects)        {            List<T> deletedRange = input.GetRange(start, count);            input.RemoveRange(start, count);            input.InsertRange(start, objects);            return deletedRange;        }         // Java substring function        public static string JavaSubstring(this string s, int begin, int end) =>            s.Substring(begin, end - begin);    }     /// <summary>    /// Class containing the diff, match and patch methods.    /// Also Contains the behavior settings.    /// </summary>    public class DiffMatchPatch    {        // Defaults.        // Set these on your DiffMatchPatch instance to override the defaults.         /// <summary>        /// Number of seconds to map a diff before giving up (0 for infinity).        /// </summary>        public float DiffTimeout = 1.0f;         /// <summary>        /// Cost of an empty edit operation in terms of edit characters.        /// </summary>        public short DiffEditCost = 4;         /// <summary>        /// At what point is no match declared (0.0 = perfection, 1.0 = very loose).        /// </summary>        public float MatchThreshold = 0.5f;         /// <summary>        /// How far to search for a match (0 = exact location, 1000+ = broad match).        /// A match this many characters away from the expected location will add        /// 1.0 to the score (0.0 is a perfect match).        /// </summary>        public int MatchDistance = 1000;         /// <summary>        /// When deleting a large block of text (over ~64 characters), how close        /// do the contents have to be to match the expected contents. (0.0 =        /// perfection, 1.0 = very loose).  Note that MatchThreshold controls        /// how closely the end points of a delete need to match.        /// </summary>        public float PatchDeleteThreshold = 0.5f;         /// <summary>        /// Chunk size for context length.        /// </summary>        public short PatchMargin = 4;         // The number of bits in an int.        private short MatchMaxBits = 32;          //  DIFF FUNCTIONS          /// <summary>        /// Find the differences between two texts.        /// Run a faster, slightly less optimal diff.        /// This method allows the 'checklines' of DiffMain() to be optional.        /// Most of the time checklines is wanted, so default to true.        /// </summary>        /// <param name="text1">Old string to be diffed</param>        /// <param name="text2">New string to be diffed</param>        /// <returns>List of Diff objects</returns>        public List<Diff> DiffMain(string text1, string text2) =>            DiffMain(text1, text2, true);         /// <summary>        /// Find the differences between two texts.        /// </summary>        /// <param name="text1">Old string to be diffed</param>        /// <param name="text2">New string to be diffed</param>        /// <param name="checklines">        /// Speedup flag.  If false, then don't run a        /// line-level diff first to identify the changed areas.        /// If true, then run a faster slightly less optimal diff.        /// </param>        /// <returns>List of Diff objects</returns>        public List<Diff> DiffMain(string text1, string text2, bool checklines)        {            // Set a deadline by which time the diff must be complete.            DateTime deadline;             if (this.DiffTimeout <= 0)                deadline = DateTime.MaxValue;            else                deadline = DateTime.Now + new TimeSpan(((long)(DiffTimeout * 1000)) * 10000);             return DiffMain(text1, text2, checklines, deadline);        }         /// <summary>        /// Find the differences between two texts.  Simplifies the problem by        /// stripping any common prefix or suffix off the texts before diffing.        /// </summary>        /// <param name="text1">Old string to be diffed</param>        /// <param name="text2">New string to be diffed</param>        /// <param name="checklines">        /// Speedup flag.  If false, then don't run a        /// line-level diff first to identify the changed areas.        /// If true, then run a faster slightly less optimal diff.        /// </param>        /// <param name="deadline">        /// Time when the diff should be complete by.  Used        /// internally for recursive calls.  Users should set DiffTimeout        /// instead.        /// </param>        /// <returns>List of Diff objects</returns>        private List<Diff> DiffMain(string text1, string text2, bool checklines, DateTime deadline)        {            // Check for null inputs not needed since null can't be passed in C#.             // Check for equality (speedup).            List<Diff> diffs;             if (text1 == text2)            {                diffs = new List<Diff>();                 if (text1.Length != 0)                    diffs.Add(new Diff(Operation.EQUAL, text1));                 return diffs;            }             // Trim off common prefix (speedup).            int commonLength = DiffCommonPrefix(text1, text2);            string commonPrefix = text1.Substring(0, commonLength);            text1 = text1.Substring(commonLength);            text2 = text2.Substring(commonLength);             // Trim off common suffix (speedup).            commonLength = DiffCommonSuffix(text1, text2);            string commonSuffix = text1.Substring(text1.Length - commonLength);            text1 = text1.Substring(0, text1.Length - commonLength);            text2 = text2.Substring(0, text2.Length - commonLength);             // Compute the diff on the middle block.            diffs = DiffCompute(text1, text2, checklines, deadline);             // Restore the prefix and suffix.            if (commonPrefix.Length != 0)                diffs.Insert(0, (new Diff(Operation.EQUAL, commonPrefix)));             if (commonSuffix.Length != 0)                diffs.Add(new Diff(Operation.EQUAL, commonSuffix));             DiffCleanupMerge(diffs);            return diffs;        }         /// <summary>        /// Find the differences between two texts.  Assumes that the texts do not        /// have any common prefix or suffix.        /// </summary>        /// <param name="text1">Old string to be diffed</param>        /// <param name="text2">New string to be diffed</param>        /// <param name="checklines">        /// Speedup flag.  If false, then don't run a        /// line-level diff first to identify the changed areas.        /// If true, then run a faster slightly less optimal diff.        /// </param>        /// <param name="deadline">Time when the diff should be complete by</param>        /// <returns>List of Diff objects</returns>        private List<Diff> DiffCompute(string text1, string text2, bool checklines, DateTime deadline)        {            List<Diff> diffs = new List<Diff>();             if (text1.Length == 0)            {                // Just add some text (speedup).                diffs.Add(new Diff(Operation.INSERT, text2));                return diffs;            }             if (text2.Length == 0)            {                // Just delete some text (speedup).                diffs.Add(new Diff(Operation.DELETE, text1));                return diffs;            }             string longText = text1.Length > text2.Length ? text1 : text2;            string shortText = text1.Length > text2.Length ? text2 : text1;            int i = longText.IndexOf(shortText, StringComparison.Ordinal);             if (i != -1)            {                // Shorter text is inside the longer text (speedup).                Operation op = (text1.Length > text2.Length)                    ? Operation.DELETE                    : Operation.INSERT;                 diffs.Add(new Diff(op, longText.Substring(0, i)));                diffs.Add(new Diff(Operation.EQUAL, shortText));                diffs.Add(new Diff(op, longText.Substring(i + shortText.Length)));                return diffs;            }             if (shortText.Length == 1)            {                // Single character string.                // After the previous speedup, the character can't be an equality.                diffs.Add(new Diff(Operation.DELETE, text1));                diffs.Add(new Diff(Operation.INSERT, text2));                return diffs;            }             // Check to see if the problem can be split in two.            string[] hm = DiffHalfMatch(text1, text2);             if (hm != null)            {                // A half-match was found, sort out the return data.                string text1A = hm[0];                string text1B = hm[1];                string text2A = hm[2];                string text2B = hm[3];                string midCommon = hm[4];                 // Send both pairs off for separate processing.                List<Diff> diffsA = DiffMain(text1A, text2A, checklines, deadline);                List<Diff> diffsB = DiffMain(text1B, text2B, checklines, deadline);                 // Merge the results.                diffs = diffsA;                diffs.Add(new Diff(Operation.EQUAL, midCommon));                diffs.AddRange(diffsB);                 return diffs;            }             if (checklines && text1.Length > 100 && text2.Length > 100)                return DiffLineMode(text1, text2, deadline);             return DiffBisect(text1, text2, deadline);        }         /// <summary>        /// Do a quick line-level diff on both strings, then rediff the parts for        /// greater accuracy. This speedup can produce non-minimal diffs.        /// </summary>        /// <param name="text1">Old string to be diffed</param>        /// <param name="text2">New string to be diffed</param>        /// <param name="deadline">Time when the diff should be complete by</param>        /// <returns>List of Diff objects</returns>        private List<Diff> DiffLineMode(string text1, string text2, DateTime deadline)        {            // Scan the text on a line-by-line basis first.            object[] a = DiffLinesToChars(text1, text2);            text1 = (string)a[0];            text2 = (string)a[1];            List<string> lineArray = (List<string>)a[2];             List<Diff> diffs = DiffMain(text1, text2, false, deadline);             // Convert the diff back to original text.            DiffCharsToLines(diffs, lineArray);             // Eliminate freak matches (e.g. blank lines)            DiffCleanupSemantic(diffs);             // Rediff any replacement blocks, this time character-by-character.            // Add a dummy entry at the end.            diffs.Add(new Diff(Operation.EQUAL, string.Empty));            int pointer = 0;            int countDelete = 0;            int countInsert = 0;            string textDelete = string.Empty;            string textInsert = string.Empty;             while (pointer < diffs.Count)            {                switch (diffs[pointer].Operation)                {                    case Operation.INSERT:                        countInsert++;                        textInsert += diffs[pointer].Text;                        break;                     case Operation.DELETE:                        countDelete++;                        textDelete += diffs[pointer].Text;                        break;                     case Operation.EQUAL:                        // Upon reaching an equality, check for prior redundancies.                        if (countDelete >= 1 && countInsert >= 1)                        {                            // Delete the offending records and add the merged ones.                            diffs.RemoveRange(pointer - countDelete - countInsert, countDelete + countInsert);                            pointer = pointer - countDelete - countInsert;                            List<Diff> subDiff = DiffMain(textDelete, textInsert, false, deadline);                            diffs.InsertRange(pointer, subDiff);                            pointer = pointer + subDiff.Count;                        }                         countInsert = 0;                        countDelete = 0;                        textDelete = string.Empty;                        textInsert = string.Empty;                        break;                }                pointer++;            }             // Remove the dummy entry at the end.            diffs.RemoveAt(diffs.Count - 1);             return diffs;        }         /// <summary>        /// <para>        /// Find the 'middle snake' of a diff, split the problem in two        /// and return the recursively constructed diff.        /// </para>        ///         /// <para>        /// See Myers 1986 paper: An O(ND) Difference Algorithm and Its Variations.        /// </para>        /// </summary>        /// <param name="text1">Old string to be diffed</param>        /// <param name="text2">New string to be diffed</param>        /// <param name="deadline">Time at which to bail if not yet complete</param>        /// <returns>List of Diff objects</returns>        [SuppressMessage("Microsoft.Maintainability", "CA1502:AvoidExcessiveComplexity")]        protected List<Diff> DiffBisect(string text1, string text2, DateTime deadline)        {            // Cache the text lengths to prevent multiple calls.            int text1Length = text1.Length;            int text2Length = text2.Length;            int maxD = (text1Length + text2Length + 1) / 2;            int vOffset = maxD;            int vLength = 2 * maxD;            int[] v1 = new int[vLength];            int[] v2 = new int[vLength];             for (int x = 0; x < vLength; x++)            {                v1[x] = -1;                v2[x] = -1;            }             v1[vOffset + 1] = 0;            v2[vOffset + 1] = 0;            int delta = text1Length - text2Length;             // If the total number of characters is odd, then the front path will            // collide with the reverse path.            bool front = (delta % 2 != 0);             // Offsets for start and end of k loop.            // Prevents mapping of space beyond the grid.            int k1Start = 0;            int k1End = 0;            int k2Start = 0;            int k2End = 0;             for (int d = 0; d < maxD; d++)            {                // Bail out if deadline is reached.                if (DateTime.Now > deadline)                    break;                 // Walk the front path one step.                for (int k1 = -d + k1Start; k1 <= d - k1End; k1 += 2)                {                    int k1Offset = vOffset + k1;                    int x1;                     if (k1 == -d || k1 != d && v1[k1Offset - 1] < v1[k1Offset + 1])                        x1 = v1[k1Offset + 1];                    else                        x1 = v1[k1Offset - 1] + 1;                     int y1 = x1 - k1;                     while (x1 < text1Length && y1 < text2Length && text1[x1] == text2[y1])                    {                        x1++;                        y1++;                    }                     v1[k1Offset] = x1;                     if (x1 > text1Length)                    {                        // Ran off the right of the graph.                        k1End += 2;                    }                    else if (y1 > text2Length)                    {                        // Ran off the bottom of the graph.                        k1Start += 2;                    }                    else if (front)                    {                        int k2Offset = vOffset + delta - k1;                         if (k2Offset >= 0 && k2Offset < vLength && v2[k2Offset] != -1)                        {                            // Mirror x2 onto top-left coordinate system.                            int x2 = text1Length - v2[k2Offset];                             if (x1 >= x2)                            {                                // Overlap detected.                                return DiffBisectSplit(text1, text2, x1, y1, deadline);                            }                        }                    }                }                 // Walk the reverse path one step.                for (int k2 = -d + k2Start; k2 <= d - k2End; k2 += 2)                {                    int k2Offset = vOffset + k2;                    int x2;                     if (k2 == -d || k2 != d && v2[k2Offset - 1] < v2[k2Offset + 1])                        x2 = v2[k2Offset + 1];                    else                        x2 = v2[k2Offset - 1] + 1;                     int y2 = x2 - k2;                     while (x2 < text1Length && y2 < text2Length && text1[text1Length - x2 - 1] == text2[text2Length - y2 - 1])                    {                        x2++;                        y2++;                    }

Lines 1–500 of 2633. Load more