28 enum { minLengthToMatch = 3,
29 maxComplexity = 16 * 1024 * 1024 };
37 : text (t), start (s), length (len) {}
39 void incrementStart() noexcept { ++text; ++start; --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);
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);
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;
183 while (length < lenA && length < lenB && *a == *b)
190 indexInA = lenA - length;
191 indexInB = lenB - length;
198 TextDiffHelpers::diffSkippingCommonStart (*
this, original, target);
216 return text.replaceSection (start, length, insertedText);
226 DiffTests() :
UnitTest (
"TextDiff class",
"Text") {}
230 juce_wchar buffer[500] = { 0 };
232 for (
int i = r.
nextInt (numElementsInArray (buffer) - 1); --i >= 0;)
238 buffer[i] = (juce_wchar) (1 + r.
nextInt (0x10ffff - 1));
243 buffer[i] = (juce_wchar) (
'a' + r.
nextInt (3));
246 return CharPointer_UTF32 (buffer);
249 void testDiff (
const String& a,
const String& b)
252 auto result = diff.appliedTo (a);
253 expectEquals (result, b);
256 void runTest()
override
258 beginTest (
"TextDiff");
260 auto r = getRandom();
262 testDiff (String(), String());
263 testDiff (
"x", String());
264 testDiff (String(),
"x");
267 testDiff (
"xxx",
"x");
268 testDiff (
"x",
"xxx");
270 for (
int i = 1000; --i >= 0;)
272 auto s = createString (r);
273 testDiff (s, createString (r));
274 testDiff (s + createString (r), s + createString (r));
279 static DiffTests diffTests;