OpenShot Audio Library | OpenShotAudio 0.4.0
 
Loading...
Searching...
No Matches
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
23namespace juce
24{
25
26struct 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
199TextDiff::TextDiff (const String& original, const String& target)
200{
201 TextDiffHelpers::diffSkippingCommonStart (*this, original, target);
202}
203
205{
206 for (auto& c : changes)
207 text = c.appliedTo (text);
208
209 return text;
210}
211
212bool TextDiff::Change::isDeletion() const noexcept
213{
214 return insertedText.isEmpty();
215}
216
217String 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
227class DiffTests final : public UnitTest
228{
229public:
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
285static DiffTests diffTests;
286
287#endif
288
289} // namespace juce
int nextInt() noexcept
TextDiff(const String &original, const String &target)
Array< Change > changes
String appliedTo(String text) const
String appliedTo(const String &original) const noexcept
bool isDeletion() const noexcept