28 enum { minLengthToMatch = 3,
29 maxComplexity = 16 * 1024 * 1024 };
33 StringRegion (
const String& s) noexcept
34 : text (s.getCharPointer()), start (0), length (s.length()) {}
36 StringRegion (String::CharPointerType t,
int s,
int len) noexcept
37 : text (t), start (s), length (len) {}
39 void incrementStart() noexcept { ++text; ++start; --length; }
41 String::CharPointerType text;
45 static void addInsertion (TextDiff& td, String::CharPointerType text,
int index,
int length)
48 c.insertedText = String (text, (
size_t) length);
54 static void addDeletion (TextDiff& td,
int index,
int length)
62 static void diffSkippingCommonStart (TextDiff& td, StringRegion a, StringRegion b)
69 if (ca != cb || ca == 0)
76 diffRecursively (td, a, b);
79 static void diffRecursively (TextDiff& td, StringRegion a, StringRegion b)
81 int indexA = 0, indexB = 0;
82 auto len = findLongestCommonSubstring (a.text, a.length, indexA,
83 b.text, b.length, indexB);
85 if (len >= minLengthToMatch)
87 if (indexA > 0 && indexB > 0)
88 diffSkippingCommonStart (td, StringRegion (a.text, a.start, indexA),
89 StringRegion (b.text, b.start, indexB));
91 addDeletion (td, b.start, indexA);
93 addInsertion (td, b.text, b.start, indexB);
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));
100 if (a.length > 0) addDeletion (td, b.start, a.length);
101 if (b.length > 0) addInsertion (td, b.text, b.start, b.length);
105 static int findLongestCommonSubstring (String::CharPointerType a,
const int lenA,
int& indexInA,
106 String::CharPointerType b,
const int lenB,
int& indexInB)
noexcept
108 if (lenA == 0 || lenB == 0)
111 if (lenA * lenB > maxComplexity)
112 return findCommonSuffix (a, lenA, indexInA,
115 auto scratchSpace =
sizeof (int) * (2 + 2 * (
size_t) lenB);
117 if (scratchSpace < 4096)
119 auto* scratch = (
int*) alloca (scratchSpace);
120 return findLongestCommonSubstring (a, lenA, indexInA, b, lenB, indexInB, scratchSpace, scratch);
123 HeapBlock<int> scratch (scratchSpace);
124 return findLongestCommonSubstring (a, lenA, indexInA, b, lenB, indexInB, scratchSpace, scratch);
127 static int findLongestCommonSubstring (String::CharPointerType a,
const int lenA,
int& indexInA,
128 String::CharPointerType b,
const int lenB,
int& indexInB,
129 const size_t scratchSpace,
int*
const lines)
noexcept
131 zeromem (lines, scratchSpace);
134 auto* l1 = l0 + lenB + 1;
136 int loopsWithoutImprovement = 0;
139 for (
int i = 0; i < lenA; ++i)
141 auto ca = a.getAndAdvance();
144 for (
int j = 0; j < lenB; ++j)
146 if (ca != b2.getAndAdvance())
152 auto len = l0[j] + 1;
155 if (len > bestLength)
157 loopsWithoutImprovement = 0;
165 if (++loopsWithoutImprovement > 100)
171 indexInA -= bestLength - 1;
172 indexInB -= bestLength - 1;
176 static int findCommonSuffix (String::CharPointerType a,
int lenA,
int& indexInA,
177 String::CharPointerType b,
int lenB,
int& indexInB)
noexcept
183 while (length < lenA && length < lenB && *a == *b)
190 indexInA = lenA - length;
191 indexInB = lenB - length;
198 TextDiffHelpers::diffSkippingCommonStart (*
this,
original, target);
204 text =
c.appliedTo (text);
228 :
UnitTest (
"TextDiff class", UnitTestCategories::text)
233 juce_wchar buffer[500] = { 0 };
235 for (
int i = r.
nextInt (numElementsInArray (buffer) - 1); --i >= 0;)
241 buffer[i] = (juce_wchar) (1 + r.
nextInt (0x10ffff - 1));
243 while (! CharPointer_UTF16::canRepresent (buffer[i]));
246 buffer[i] = (juce_wchar) (
'a' + r.
nextInt (3));
249 return CharPointer_UTF32 (buffer);
252 void testDiff (
const String& a,
const String& b)
254 TextDiff diff (a, b);
255 auto result = diff.appliedTo (a);
256 expectEquals (result, b);
259 void runTest()
override
261 beginTest (
"TextDiff");
263 auto r = getRandom();
265 testDiff (String(), String());
266 testDiff (
"x", String());
267 testDiff (String(),
"x");
270 testDiff (
"xxx",
"x");
271 testDiff (
"x",
"xxx");
273 for (
int i = 1000; --i >= 0;)
275 auto s = createString (r);
276 testDiff (s, createString (r));
277 testDiff (s + createString (r), s + createString (r));
282static DiffTests diffTests;
bool isEmpty() const noexcept
String replaceSection(int startIndex, int numCharactersToReplace, StringRef stringToInsert) const
TextDiff(const String &original, const String &target)
String appliedTo(String text) const
String appliedTo(const String &original) const noexcept
bool isDeletion() const noexcept