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)
69 if (ca != cb || ca == 0)
76 diffRecursively (td, a, 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),
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);
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)
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);
203 for (
auto& c : changes)
204 text = c.appliedTo (text);
211 return insertedText.isEmpty();
216 return text.replaceSection (start, length, insertedText);
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));
246 buffer[i] = (juce_wchar) (
'a' + r.
nextInt (3));
256 expectEquals (result, b);
259 void runTest()
override 261 beginTest (
"TextDiff");
263 auto r = getRandom();
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));
282 static DiffTests diffTests;
TextDiff(const String &original, const String &target)
Creates a set of diffs for converting the original string into the target.
int nextInt() noexcept
Returns the next random 32 bit integer.
static bool canRepresent(juce_wchar character) noexcept
Returns true if the given unicode character can be represented in this encoding.
CharPointerType getCharPointer() const noexcept
Returns the character pointer currently being used to store this string.
String insertedText
If this change is a deletion, this string will be empty; otherwise, it'll be the text that should be ...
int length
If this change is a deletion, this specifies the number of characters to delete.
This is a base class for classes that perform a unit test.
Calculates and applies a sequence of changes to convert one text string into another.
Wraps a pointer to a null-terminated UTF-32 character string, and provides various methods to operate...
String appliedTo(const String &original) const noexcept
Returns the result of applying this change to a string.
juce_wchar getAndAdvance() noexcept
Returns the character that this pointer is currently pointing to, and then advances the pointer to po...
int start
Specifies the character index in a string at which text should be inserted or deleted.
bool isDeletion() const noexcept
Returns true if this change is a deletion, or false for an insertion.
Describes a change, which can be either an insertion or deletion.
String appliedTo(String text) const
Applies this sequence of changes to the original string, producing the target string that was specifi...
A random number generator.
int length() const noexcept
Returns the number of characters in the string.
Array< Change > changes
The list of changes required to perform the transformation.
Wraps a pointer to a null-terminated UTF-8 character string, and provides various methods to operate ...