source/modules/juce_core/text/juce_TextDiff.cpp

   1 /*
   2   ==============================================================================
   3
   4    This file is part of the JUCE library.
   5    Copyright (c) 2022 - Raw Material Software Limited
   6
   7    JUCE is an open source library subject to commercial or open-source
   8    licensing.
   9
  10    The code included in this file is provided under the terms of the ISC license
  11    http://www.isc.org/downloads/software-support-policy/isc-license. Permission
  12    To use, copy, modify, and/or distribute this software for any purpose with or
  13    without fee is hereby granted provided that the above copyright notice and
  14    this permission notice appear in all copies.
  15
  16    JUCE IS PROVIDED "AS IS" WITHOUT ANY WARRANTY, AND ALL WARRANTIES, WHETHER
  17    EXPRESSED OR IMPLIED, INCLUDING MERCHANTABILITY AND FITNESS FOR PURPOSE, ARE
  18    DISCLAIMED.
  19
  20   ==============================================================================
  21 */
  22
  23 namespace juce
  24 {
  25
  26 struct TextDiffHelpers
  27 {
  28     enum { minLengthToMatch = 3,
  29            maxComplexity = 16 * 1024 * 1024 };
  30
  31     struct StringRegion
  32     {
  33         StringRegion (const String& s) noexcept
  34             : text (s.getCharPointer()), start (0), length (s.length()) {}
  35
  36         StringRegion (String::CharPointerType t, int s, int len) noexcept
  37             : text (t), start (s), length (len) {}
  38
  39         void incrementStart() noexcept  { ++text; ++start; --length; }
  40
  41         String::CharPointerType text;
  42         int start, length;
  43     };
  44
  45     static void addInsertion (TextDiff& td, String::CharPointerType text, int index, int length)
  46     {
  47         TextDiff::Change c;
  48         c.insertedText = String (text, (size_t) length);
  49         c.start = index;
  50         c.length = 0;
  51         td.changes.add (c);
  52     }
  53
  54     static void addDeletion (TextDiff& td, int index, int length)
  55     {
  56         TextDiff::Change c;
  57         c.start = index;
  58         c.length = length;
  59         td.changes.add (c);
  60     }
  61
  62     static void diffSkippingCommonStart (TextDiff& td, StringRegion a, StringRegion b)
  63     {
  64         for (;;)
  65         {
  66             auto ca = *a.text;
  67             auto cb = *b.text;
  68
  69             if (ca != cb || ca == 0)
  70                 break;
  71
  72             a.incrementStart();
  73             b.incrementStart();
  74         }
  75
  76         diffRecursively (td, a, b);
  77     }
  78
  79     static void diffRecursively (TextDiff& td, StringRegion a, StringRegion b)
  80     {
  81         int indexA = 0, indexB = 0;
  82         auto len = findLongestCommonSubstring (a.text, a.length, indexA,
  83                                                b.text, b.length, indexB);
  84
  85         if (len >= minLengthToMatch)
  86         {
  87             if (indexA > 0 && indexB > 0)
  88                 diffSkippingCommonStart (td, StringRegion (a.text, a.start, indexA),
  89                                              StringRegion (b.text, b.start, indexB));
  90             else if (indexA > 0)
  91                 addDeletion (td, b.start, indexA);
  92             else if (indexB > 0)
  93                 addInsertion (td, b.text, b.start, indexB);
  94
  95             diffRecursively (td, StringRegion (a.text + (indexA + len), a.start + indexA + len, a.length - indexA - len),
  96                                  StringRegion (b.text + (indexB + len), b.start + indexB + len, b.length - indexB - len));
  97         }
  98         else
  99         {
 100             if (a.length > 0)   addDeletion (td, b.start, a.length);
 101             if (b.length > 0)   addInsertion (td, b.text, b.start, b.length);
 102         }
 103     }
 104
 105     static int findLongestCommonSubstring (String::CharPointerType a, const int lenA, int& indexInA,
 106                                            String::CharPointerType b, const int lenB, int& indexInB) noexcept
 107     {
 108         if (lenA == 0 || lenB == 0)
 109             return 0;
 110
 111         if (lenA * lenB > maxComplexity)
 112             return findCommonSuffix (a, lenA, indexInA,
 113                                      b, lenB, indexInB);
 114
 115         auto scratchSpace = sizeof (int) * (2 + 2 * (size_t) lenB);
 116
 117         if (scratchSpace < 4096)
 118         {
 119             JUCE_BEGIN_IGNORE_WARNINGS_MSVC (6255)
 120             auto* scratch = (int*) alloca (scratchSpace);
 121             JUCE_END_IGNORE_WARNINGS_MSVC
 122
 123             return findLongestCommonSubstring (a, lenA, indexInA, b, lenB, indexInB, scratchSpace, scratch);
 124         }
 125
 126         HeapBlock<int> scratch (scratchSpace);
 127         return findLongestCommonSubstring (a, lenA, indexInA, b, lenB, indexInB, scratchSpace, scratch);
 128     }
 129
 130     static int findLongestCommonSubstring (String::CharPointerType a, const int lenA, int& indexInA,
 131                                            String::CharPointerType b, const int lenB, int& indexInB,
 132                                            const size_t scratchSpace, int* const lines) noexcept
 133     {
 134         zeromem (lines, scratchSpace);
 135
 136         auto* l0 = lines;
 137         auto* l1 = l0 + lenB + 1;
 138
 139         int loopsWithoutImprovement = 0;
 140         int bestLength = 0;
 141
 142         for (int i = 0; i < lenA; ++i)
 143         {
 144             auto ca = a.getAndAdvance();
 145             auto b2 = b;
 146
 147             for (int j = 0; j < lenB; ++j)
 148             {
 149                 if (ca != b2.getAndAdvance())
 150                 {
 151                     l1[j + 1] = 0;
 152                 }
 153                 else
 154                 {
 155                     auto len = l0[j] + 1;
 156                     l1[j + 1] = len;
 157
 158                     if (len > bestLength)
 159                     {
 160                         loopsWithoutImprovement = 0;
 161                         bestLength = len;
 162                         indexInA = i;
 163                         indexInB = j;
 164                     }
 165                 }
 166             }
 167
 168             if (++loopsWithoutImprovement > 100)
 169                 break;
 170
 171             std::swap (l0, l1);
 172         }
 173
 174         indexInA -= bestLength - 1;
 175         indexInB -= bestLength - 1;
 176         return bestLength;
 177     }
 178
 179     static int findCommonSuffix (String::CharPointerType a, int lenA, int& indexInA,
 180                                  String::CharPointerType b, int lenB, int& indexInB) noexcept
 181     {
 182         int length = 0;
 183         a += lenA - 1;
 184         b += lenB - 1;
 185
 186         while (length < lenA && length < lenB && *a == *b)
 187         {
 188             --a;
 189             --b;
 190             ++length;
 191         }
 192
 193         indexInA = lenA - length;
 194         indexInB = lenB - length;
 195         return length;
 196     }
 197 };
 198
 199 TextDiff::TextDiff (const String& original, const String& target)
 200 {
 201     TextDiffHelpers::diffSkippingCommonStart (*this, original, target);
 202 }
 203
 204 String TextDiff::appliedTo (String text) const
 205 {
 206     for (auto& c : changes)
 207         text = c.appliedTo (text);
 208
 209     return text;
 210 }
 211
 212 bool TextDiff::Change::isDeletion() const noexcept
 213 {
 214     return insertedText.isEmpty();
 215 }
 216
 217 String TextDiff::Change::appliedTo (const String& text) const noexcept
 218 {
 219     return text.replaceSection (start, length, insertedText);
 220 }
 221
 222
 223 //==============================================================================
 224 //==============================================================================
 225 #if JUCE_UNIT_TESTS
 226
 227 class DiffTests  : public UnitTest
 228 {
 229 public:
 230     DiffTests()
 231         : UnitTest ("TextDiff class", UnitTestCategories::text)
 232     {}
 233
 234     static String createString (Random& r)
 235     {
 236         juce_wchar buffer[500] = { 0 };
 237
 238         for (int i = r.nextInt (numElementsInArray (buffer) - 1); --i >= 0;)
 239         {
 240             if (r.nextInt (10) == 0)
 241             {
 242                 do
 243                 {
 244                     buffer[i] = (juce_wchar) (1 + r.nextInt (0x10ffff - 1));
 245                 }
 246                 while (! CharPointer_UTF16::canRepresent (buffer[i]));
 247             }
 248             else
 249                 buffer[i] = (juce_wchar) ('a' + r.nextInt (3));
 250         }
 251
 252         return CharPointer_UTF32 (buffer);
 253     }
 254
 255     void testDiff (const String& a, const String& b)
 256     {
 257         TextDiff diff (a, b);
 258         auto result = diff.appliedTo (a);
 259         expectEquals (result, b);
 260     }
 261
 262     void runTest() override
 263     {
 264         beginTest ("TextDiff");
 265
 266         auto r = getRandom();
 267
 268         testDiff (String(), String());
 269         testDiff ("x", String());
 270         testDiff (String(), "x");
 271         testDiff ("x", "x");
 272         testDiff ("x", "y");
 273         testDiff ("xxx", "x");
 274         testDiff ("x", "xxx");
 275
 276         for (int i = 1000; --i >= 0;)
 277         {
 278             auto s = createString (r);
 279             testDiff (s, createString (r));
 280             testDiff (s + createString (r), s + createString (r));
 281         }
 282     }
 283 };
 284
 285 static DiffTests diffTests;
 286
 287 #endif
 288
 289 } // namespace juce