1 /*
2 Author: Daniele Fognini, Andreas Wuerl
3 Copyright (C) 2013-2014, Siemens AG
4 
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License
7 version 2 as published by the Free Software Foundation.
8 
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12 GNU General Public License for more details.
13 
14 You should have received a copy of the GNU General Public License along
15 with this program; if not, write to the Free Software Foundation, Inc.,
16 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301, USA.
17  */
18 #include <stdlib.h>
19 #include <stdio.h>
20 #include <CUnit/CUnit.h>
21 #include <glib.h>
22 #include <stdarg.h>
23 
24 #include "hash.h"
25 #include "string_operations.h"
26 #include "diff.h"
27 #include "match.h"
28 #include "monk.h"
29 
token_search_diff(char * text,char * search,unsigned int maxAllowedDiff,size_t expectedMatchCount,size_t expectedAdditionsCount,size_t expectedRemovalsCount,...)30 int token_search_diff(char* text, char* search, unsigned int maxAllowedDiff,
31         size_t expectedMatchCount, size_t expectedAdditionsCount, size_t expectedRemovalsCount, ...) {
32 
33   int result;
34   result = 0;
35 
36   char* textCopy = g_strdup(text);
37   char* searchCopy = g_strdup(search);
38 
39   GArray* tokenizedText = tokenize(textCopy, "^");
40   GArray* tokenizedSearch = tokenize(searchCopy, "^");
41 
42   GArray* matched = g_array_new(TRUE, FALSE, sizeof (size_t));
43   GArray* additions = g_array_new(TRUE, FALSE, sizeof (size_t));
44   GArray* removals = g_array_new(TRUE, FALSE, sizeof (size_t));
45 
46   size_t textStartPosition = 0;
47   DiffResult* diffResult = findMatchAsDiffs(tokenizedText, tokenizedSearch, textStartPosition, 0, maxAllowedDiff, 1);
48   if(expectedAdditionsCount + expectedMatchCount + expectedRemovalsCount == 0) {
49     CU_ASSERT_PTR_NULL(diffResult);
50     result = diffResult != NULL;
51     goto end;
52   } else {
53     CU_ASSERT_PTR_NOT_NULL(diffResult);
54     if (!diffResult) {
55       printf("null result unexpected\n");
56       result = 0;
57       goto end;
58     }
59   }
60   GArray* matchedInfo = diffResult->matchedInfo;
61 
62   size_t matchedCount = 0;
63   size_t additionCount = 0;
64   size_t removalCount = 0;
65 
66   for (size_t i=0; i<matchedInfo->len; i++) {
67     DiffMatchInfo diffInfo = g_array_index(matchedInfo, DiffMatchInfo, i);
68     if (strcmp(diffInfo.diffType, DIFF_TYPE_ADDITION) == 0) {
69       additionCount += diffInfo.text.length;
70       for (size_t j=diffInfo.text.start;
71            j<diffInfo.text.start + diffInfo.text.length;
72            j++)
73         g_array_append_val(additions, j);
74     }
75     if (strcmp(diffInfo.diffType, DIFF_TYPE_MATCH) == 0) {
76       for (size_t j=diffInfo.text.start;
77            j<diffInfo.text.start + diffInfo.text.length;
78            j++)
79         g_array_append_val(matched, j);
80        matchedCount += diffInfo.text.length;
81     }
82     if (strcmp(diffInfo.diffType, DIFF_TYPE_REMOVAL) == 0) {
83       g_array_append_val(removals, diffInfo.text.start);
84       removalCount ++;
85     }
86     if (strcmp(diffInfo.diffType, DIFF_TYPE_REPLACE) == 0) {
87       additionCount += diffInfo.text.length;
88       for (size_t j=diffInfo.text.start;
89            j<diffInfo.text.start + diffInfo.text.length;
90            j++)
91         g_array_append_val(additions, j);
92       removalCount++;
93       g_array_append_val(removals, diffInfo.text.start);
94     }
95   }
96   CU_ASSERT_EQUAL(matchedCount, expectedMatchCount);
97   CU_ASSERT_EQUAL(additionCount, expectedAdditionsCount);
98   CU_ASSERT_EQUAL(removalCount, expectedRemovalsCount);
99   CU_ASSERT_EQUAL(matched->len, expectedMatchCount);
100   CU_ASSERT_EQUAL(additions->len, expectedAdditionsCount);
101   CU_ASSERT_EQUAL(removals->len, expectedRemovalsCount);
102 
103   va_list argptr;
104   va_start(argptr, expectedRemovalsCount);
105 
106   if (expectedMatchCount == matchedCount) {
107     if (expectedAdditionsCount == additionCount) {
108       if (expectedRemovalsCount == removalCount) {
109         size_t i;
110         size_t actual;
111         size_t expected;
112         for (i = 0; i < expectedMatchCount; i++) {
113           expected = va_arg(argptr, int);
114           actual = g_array_index(matched, size_t, i);
115           CU_ASSERT_EQUAL(actual, expected);
116           if (actual != expected) {
117             printf("ASSERT ERROR: findMatchAsDiffs(\"%s\", \"%s\"):\n", text, search);
118             printf("matched[%ld] == %ld != %ld\n", i, actual, expected);
119             goto end;
120           }
121         }
122         for (i = 0; i < expectedAdditionsCount; i++) {
123           expected = va_arg(argptr, int);
124           actual = g_array_index(additions, size_t, i);
125           CU_ASSERT_EQUAL(actual, expected);
126           if (actual != expected) {
127             printf("ASSERT ERROR: findMatchAsDiffs(\"%s\", \"%s\"):\n", text, search);
128             printf("additions[%ld] == %ld != %ld\n", i, actual, expected);
129             goto end;
130           }
131         }
132         for (i = 0; i < expectedRemovalsCount; i++) {
133           expected = va_arg(argptr, int);
134           actual = g_array_index(removals, size_t, i);
135           CU_ASSERT_EQUAL(actual, expected);
136           if (actual != expected) {
137             printf("ASSERT ERROR: findMatchAsDiffs(\"%s\", \"%s\"):\n", text, search);
138             printf("removals[%ld] == %ld != %ld\n", i, actual, expected);
139             goto end;
140           }
141         }
142       } else
143         printf("ASSERT ERROR: findMatchAsDiffs(\"%s\", \"%s\"): removals(%zu) != expected(%ld)\n",
144               text, search, removalCount, expectedRemovalsCount);
145     } else
146       printf("ASSERT ERROR: findMatchAsDiffs(\"%s\", \"%s\"): additions(%zu) != expected(%ld)\n",
147             text, search, additionCount, expectedAdditionsCount);
148   } else
149     printf("ASSERT ERROR: findMatchAsDiffs(\"%s\", \"%s\"): matched(%zu) != expected(%ld)\n",
150           text, search, matchedCount, expectedMatchCount);
151 
152   result = 1;
153 end:
154 
155   va_end(argptr);
156 
157   if (diffResult)
158     diffResult_free(diffResult);
159   g_array_free(matched, TRUE);
160   g_array_free(additions, TRUE);
161   g_array_free(removals, TRUE);
162 
163   g_array_free(tokenizedText, TRUE);
164   g_array_free(tokenizedSearch, TRUE);
165 
166   g_free(textCopy);
167   g_free(searchCopy);
168 
169   return result;
170 }
171 
test_token_search_diffs()172 void test_token_search_diffs() {
173   // simple matches
174   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^foo^^bar^", "one",
175           5,
176           1, 0, 0,
177           0));
178   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^foo^^bar^", "bar",
179           5,
180           1, 0, 0,
181           4));
182   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^foo^^bar^", "two",
183           5,
184           1, 0, 0,
185           1));
186   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^foo^^bar^", "3^foo",
187           5,
188           2, 0, 0,
189           2, 3));
190   CU_ASSERT_FALSE(token_search_diff("^one^^two^^3^^foo^^bar^", "",
191           5,
192           0, 0, 0));
193 
194   // not matches
195   CU_ASSERT_FALSE(token_search_diff("^one^^two^^3^^foo^^bar^", "one^^foo^^bar^^3",
196           2,
197           0, 0, 0));
198   CU_ASSERT_FALSE(token_search_diff("^one^^two^^3^^bar", "one^^3^3^^bar^^z^d^5",
199           2,
200           0, 0, 0));
201   CU_ASSERT_FALSE(token_search_diff("one^two^^three^^bas", "one^^3^3^^bar^^z",
202           2,
203           0, 0, 0));
204 
205   // simple additions
206   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^foo^^bar^", "one^^foo^^bar",
207           5,
208           3, 2, 0,
209           0, 3, 4, // matched
210           1, 2 // additions
211           ));
212 
213   // simple removals
214   CU_ASSERT_TRUE(token_search_diff("^one^^3^^bar^z", "one^^3^3^^5^^bar^^y^^z",
215           5,
216           4, 0, 2,
217           0, 1, 2, 3, // matched
218           2, 3 // removals
219           ));
220 
221   // mixed additions and removals
222   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^bar^z", "one^^3^3^^bar^^z",
223           5,
224           4, 1, 1,
225           0, 2, 3, 4, // matched
226           1, // additions
227           3 // removals
228           ));
229 
230   CU_ASSERT_TRUE(token_search_diff("^one^^two^^1^2^3^4^5^z", "one^^1^2^3^4^5^4^z",
231           5,
232           7, 1, 1,
233           0, 2, 3, 4, 5, 6, 7, // matched
234           1, // additions
235           7 // removals
236           ));
237 
238   CU_ASSERT_TRUE(token_search_diff("^one^^3^^bar^5^e", "one^^3^bar^^4^e",
239           5,
240           4, 1, 1,
241           0, 1, 2, 4, // matched
242           3, // additions
243           3 // removals
244           ));
245 
246   CU_ASSERT_TRUE(token_search_diff("^one^^3^^bar^5^z", "one^^3^bar^^4^a^^z",
247           5,
248           4, 1, 1,
249           0, 1, 2, 4, // matched
250           3, // additions
251           3 // removals
252           ));
253 
254   CU_ASSERT_TRUE(token_search_diff("^one^^3^^bar^5^6^z", "one^^3^bar^^4^^z",
255           5,
256           4, 2, 1,
257           0, 1, 2, 5, // matched
258           3, 4, // additions
259           3 // removals
260           ));
261 
262   CU_ASSERT_TRUE(token_search_diff("^one^^two^^3^^bar", "one^^3^3^^bar^^z",
263           2,
264           3, 1, 2,
265           0, 2, 3, // matched
266           1, // additions
267           3, 4 // removals
268           ));
269 
270   // simple replace
271   CU_ASSERT_TRUE(token_search_diff("^foo^^one^two^three^^bar", "foo^1^two^three^bar",
272           5,
273           4, 1, 1,
274           0, 2, 3, 4, // matched
275           1, 1, // additions
276           1 // removals
277           ));
278 
279   CU_ASSERT_TRUE(token_search_diff("^foo^^one^bar^two^three^^bar", "foo^1^two^three^bar",
280           5,
281           4, 2, 1,
282           0, 3, 4, 5, // matched
283           1, 2, // additions
284           1 // removals
285           ));
286 
287   CU_ASSERT_TRUE(token_search_diff("^foo^^one^two^three^^bar", "foo^1^2^two^three^bar",
288           5,
289           4, 1, 1,
290           0, 2, 3, 4, // matched
291           1, // additions
292           1 // removals
293           ));
294 }
295 
token_search(char * text,char * search,size_t expectedStart)296 int token_search(char* text, char* search, size_t expectedStart) {
297   char* textCopy = g_strdup(text);
298   char* searchCopy = g_strdup(search);
299 
300   GArray* tokenizedText = tokenize(textCopy, "^");
301   GArray* tokenizedSearch = tokenize(searchCopy, "^");
302 
303   size_t matchStart = 0;
304   size_t textStartPosition = 0;
305   DiffResult* diffResult = findMatchAsDiffs(tokenizedText, tokenizedSearch, textStartPosition, 0, 0, 1);
306 
307   int matched = 0;
308 
309   if (diffResult) {
310     matched = diffResult->matchedInfo->len == 1;
311     matchStart = g_array_index(diffResult->matchedInfo, DiffPoint, 0).start;
312     diffResult_free(diffResult);
313   }
314   CU_ASSERT_EQUAL(expectedStart, matchStart);
315 
316   g_array_free(tokenizedText, TRUE);
317   g_array_free(tokenizedSearch, TRUE);
318   g_free(textCopy);
319   g_free(searchCopy);
320 
321   return matched;
322 }
323 
test_token_search()324 void test_token_search() {
325   CU_ASSERT_TRUE(token_search("^one^^two^^3^^foo^^bar^", "one", 0));
326   CU_ASSERT_TRUE(token_search("^one^^two^^3^^foo^^bar^", "bar", 4));
327   CU_ASSERT_TRUE(token_search("^one^^two^^3^^foo^^bar^", "two", 1));
328   CU_ASSERT_TRUE(token_search("^one^^two^^3^^foo^^bar^", "3^foo", 2));
329 
330   CU_ASSERT_FALSE(token_search("^^", "one", 0));
331   CU_ASSERT_FALSE(token_search("^one^", "^^", 0));
332 
333   CU_ASSERT_FALSE(token_search("^one^^two^^3^^foo^^bar^", "3^^foo^two", 0));
334 
335   CU_ASSERT_FALSE(token_search("^3^one^^two^^3^^foo^^bar^", "3^^foo", 0));
336   CU_ASSERT_TRUE(token_search("one^^two^^3^^foo^^bar^", "3^^foo", 2));
337 }
338 
test_matchNTokens()339 void test_matchNTokens(){
340   char* text = g_strdup("a.b.c.d.e.f.g");
341   char* search = g_strdup("a.b.c.d.E.E.f.g");
342 
343   GArray* textTokens = tokenize(text,".");
344   GArray* searchTokens = tokenize(search,".");
345 
346   CU_ASSERT_TRUE(matchNTokens(textTokens, 1, textTokens->len,
347                               searchTokens, 1, searchTokens->len,
348                               2));
349 
350   CU_ASSERT_TRUE(matchNTokens(textTokens, 5, textTokens->len,
351                               searchTokens, 6, searchTokens->len,
352                               1));
353 
354   CU_ASSERT_FALSE(matchNTokens(textTokens, 1, textTokens->len,
355                               searchTokens, 1, searchTokens->len,
356                               7));
357 
358   g_array_free(textTokens, TRUE);
359   g_array_free(searchTokens, TRUE);
360   g_free(text);
361   g_free(search);
362 }
363 
test_matchNTokensCorners()364 void test_matchNTokensCorners(){
365   char* empty = g_strdup("....");
366   char* search = g_strdup("a.b.c.d.E.E.f.g");
367 
368   GArray* emptyTokens = tokenize(empty,".");
369   GArray* secondTokens = tokenize(search,".");
370 
371   CU_ASSERT_FALSE(matchNTokens(emptyTokens, 0, emptyTokens->len,
372                               secondTokens, 1, secondTokens->len,
373                               2));
374 
375   CU_ASSERT_FALSE(matchNTokens(emptyTokens, 5, emptyTokens->len,
376                               secondTokens, 6, secondTokens->len,
377                               1));
378 
379   CU_ASSERT_FALSE(matchNTokens(secondTokens, 0, secondTokens->len,
380                               emptyTokens, 0, emptyTokens->len,
381                               1));
382 
383   g_array_free(emptyTokens, TRUE);
384   g_array_free(secondTokens, TRUE);
385   g_free(empty);
386   g_free(search);
387 }
388 
_test_lookForAdditions(char * text,char * search,int textPosition,int searchPosition,int maxAllowedDiff,int minTrailingMatches,int expectedTextPosition,int expectedSearchPosition)389 int _test_lookForAdditions(char* text, char* search,
390         int textPosition, int searchPosition, int maxAllowedDiff, int minTrailingMatches,
391         int expectedTextPosition, int expectedSearchPosition) {
392   char* testText = g_strdup(text);
393   char* testSearch = g_strdup(search);
394 
395   GArray* textTokens = tokenize(testText, "^");
396   GArray* searchTokens = tokenize(testSearch, "^");
397 
398   DiffMatchInfo result;
399   int ret = lookForDiff(textTokens, searchTokens,
400           textPosition, searchPosition, maxAllowedDiff, minTrailingMatches,
401           &result);
402 
403   if (ret) {
404     if (result.search.start != expectedSearchPosition) {
405       printf("adds(%s,%s): result.search.start == %zu != %d\n", text, search,
406              result.search.start, expectedSearchPosition);
407     }
408     if (result.text.start != expectedTextPosition) {
409       printf("adds(%s,%s): result.text.start == %zu != %d\n", text, search,
410              result.text.start, expectedTextPosition);
411     }
412 
413     CU_ASSERT_TRUE(result.search.start == expectedSearchPosition);
414     CU_ASSERT_TRUE(result.text.start == expectedTextPosition);
415   }
416 
417   g_array_free(textTokens, TRUE);
418   g_array_free(searchTokens, TRUE);
419   g_free(testText);
420   g_free(testSearch);
421 
422   return ret;
423 }
424 
_test_lookForRemovals(char * text,char * search,int textPosition,int searchPosition,int maxAllowedDiff,int minTrailingMatches,int expectedTextPosition,int expectedSearchPosition)425 int _test_lookForRemovals(char* text, char* search,
426         int textPosition, int searchPosition, int maxAllowedDiff, int minTrailingMatches,
427         int expectedTextPosition, int expectedSearchPosition) {
428   char* testText = g_strdup(text);
429   char* testSearch = g_strdup(search);
430 
431   GArray* textTokens = tokenize(testText, "^");
432   GArray* searchTokens = tokenize(testSearch, "^");
433 
434   DiffMatchInfo result;
435   int ret = lookForDiff(textTokens, searchTokens,
436           textPosition, searchPosition, maxAllowedDiff, minTrailingMatches,
437           &result);
438 
439   if (ret) {
440     if (result.search.start != expectedSearchPosition) {
441       printf("rems(%s,%s): result.search.start == %zu != %d\n", text, search,
442              result.search.start, expectedSearchPosition);
443     }
444     if (result.text.start != expectedTextPosition) {
445       printf("rems(%s,%s): result.text.start == %zu != %d\n", text, search,
446              result.text.start, expectedTextPosition);
447     }
448 
449     CU_ASSERT_TRUE(result.search.start == expectedSearchPosition);
450     CU_ASSERT_TRUE(result.text.start == expectedTextPosition);
451   }
452 
453   g_array_free(textTokens, TRUE);
454   g_array_free(searchTokens, TRUE);
455   g_free(testText);
456   g_free(testSearch);
457   return ret;
458 }
459 
test_lookForReplacesNotOverflowing()460 void test_lookForReplacesNotOverflowing() {
461   int max = MAX_ALLOWED_DIFF_LENGTH+1;
462   int length = max + 1;
463   char* testText = malloc((length)*2+1);
464   char* testSearch = malloc((length)*2+1);
465 
466   char* ptr1 =testSearch;
467   char* ptr2 =testText;
468   for (int i = 0; i<length; i++) {
469     *ptr1='a';
470     *ptr2='b';
471     ptr1++;
472     ptr2++;
473     *ptr1='^';
474     *ptr2='^';
475     ptr1++;
476     ptr2++;
477   }
478   int matchPosition = length;
479   *(testSearch + 2*(matchPosition-1))='m';
480   *(testText + 2)='m';
481   *ptr1 = '\0';
482   *ptr2 = '\0';
483 
484   GArray* textTokens = tokenize(testText, "^");
485   GArray* searchTokens = tokenize(testSearch, "^");
486 
487   DiffMatchInfo result;
488   CU_ASSERT_FALSE(lookForDiff(textTokens, searchTokens,
489                               0, 0, max, 1, &result));
490 
491   g_array_free(textTokens, TRUE);
492   g_array_free(searchTokens, TRUE);
493   free(testText);
494   free(testSearch);
495 }
496 
_test_lookForReplaces(char * text,char * search,int textPosition,int searchPosition,int maxAllowedDiff,int minTrailingMatches,int expectedTextPosition,int expectedSearchPosition)497 int _test_lookForReplaces(char* text, char* search,
498         int textPosition, int searchPosition, int maxAllowedDiff, int minTrailingMatches,
499         int expectedTextPosition, int expectedSearchPosition) {
500   char* testText = g_strdup(text);
501   char* testSearch = g_strdup(search);
502 
503   GArray* textTokens = tokenize(testText, "^");
504   GArray* searchTokens = tokenize(testSearch, "^");
505 
506   DiffMatchInfo result;
507   int ret = lookForDiff(textTokens, searchTokens,
508           textPosition, searchPosition, maxAllowedDiff, minTrailingMatches, &result);
509 
510   if (ret) {
511     if (result.search.start != expectedSearchPosition) {
512       printf("replS(%s,%s): result.search.start == %zu != %d\n", text, search,
513              result.search.start, expectedSearchPosition);
514     }
515     if (result.text.start != expectedTextPosition) {
516       printf("replS(%s,%s): result.text.start == %zu != %d\n", text, search,
517              result.text.start, expectedTextPosition);
518     }
519 
520     CU_ASSERT_TRUE(result.search.start == expectedSearchPosition);
521     CU_ASSERT_TRUE(result.text.start == expectedTextPosition);
522   }
523 
524   g_array_free(textTokens, TRUE);
525   g_array_free(searchTokens, TRUE);
526   g_free(testText);
527   g_free(testSearch);
528 
529   return ret;
530 }
531 
test_lookForAdditions()532 void test_lookForAdditions() {
533   CU_ASSERT_TRUE(_test_lookForAdditions(
534           "one^two",
535           "two",
536           0, 0, 5, 1,
537           1, 0));
538 
539   CU_ASSERT_FALSE(_test_lookForAdditions(
540           "one^two^three^four^five",
541           "five",
542           0, 0, 2, 1,
543           0, 0));
544 
545   CU_ASSERT_FALSE(_test_lookForAdditions(
546           "one^two^three^four",
547           "one",
548           1, 0, 6, 1,
549           1, 0));
550 
551   CU_ASSERT_TRUE(_test_lookForAdditions(
552           "1^d^a^test_starts_here^two^three",
553           "v^test_starts_here^^three",
554           4, 2, 5, 1,
555           5, 2));
556 
557   CU_ASSERT_FALSE(_test_lookForAdditions(
558           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
559           "v^test_starts_here^^eight",
560           4, 2, 10, 1,
561           4, 2));
562 
563   CU_ASSERT_FALSE(_test_lookForAdditions(
564           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
565           "v^test_starts_here^^seven",
566           4, 2, 2, 1,
567           4, 2));
568 }
569 
test_lookForRemovals()570 void test_lookForRemovals() {
571   CU_ASSERT_TRUE(_test_lookForRemovals(
572           "two",
573           "one^two",
574           0, 0, 5, 1,
575           0, 1));
576 
577   CU_ASSERT_FALSE(_test_lookForRemovals(
578           "five",
579           "one^two^three^four^five",
580           0, 0, 2, 1,
581           0, 0));
582 
583   CU_ASSERT_FALSE(_test_lookForRemovals(
584           "five",
585           "five^two^three^four^five",
586           0, 1, 2, 1,
587           0, 1));
588 
589   CU_ASSERT_TRUE(_test_lookForRemovals(
590           "1^d^a^test_starts_here^three",
591           "v^test_starts_here^two^three",
592           4, 2, 5, 1,
593           4, 3));
594 
595   CU_ASSERT_FALSE(_test_lookForRemovals(
596           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
597           "v^test_starts_here^^eight",
598           4, 2, 10, 1,
599           4, 2));
600 
601   CU_ASSERT_FALSE(_test_lookForRemovals(
602           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
603           "v^test_starts_here^^seven",
604           4, 2, 2, 1,
605           4, 2));
606 }
607 
test_lookForReplaces1()608 void test_lookForReplaces1() {
609   CU_ASSERT_TRUE(_test_lookForReplaces(
610           "one^two",
611           "eins^two",
612           0, 0, 5, 1,
613           1, 1));
614 
615   CU_ASSERT_TRUE(_test_lookForReplaces(
616           "one^two^three",
617           "eins^three",
618           0, 0, 5, 1,
619           2, 1));
620 
621   CU_ASSERT_FALSE(_test_lookForReplaces(
622           "one^two^three^four^five",
623           "eins^five",
624           0, 0, 2, 1,
625           0, 0));
626 
627   CU_ASSERT_TRUE(_test_lookForReplaces(
628           "1^d^a^test_starts_here^one^three",
629           "v^test_starts_here^two^three",
630           4, 2, 5, 1,
631           5, 3));
632 
633   CU_ASSERT_FALSE(_test_lookForReplaces(
634           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
635           "v^test_starts_here^^eight",
636           4, 2, 10, 1,
637           4, 2));
638 
639   CU_ASSERT_FALSE(_test_lookForReplaces(
640           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
641           "v^test_starts_here^^seven",
642           4, 2, 2, 1,
643           4, 2));
644 
645   CU_ASSERT_TRUE(_test_lookForReplaces(
646           "one^two",
647           "eins^two",
648           0, 0, 5, 1,
649           1, 1));
650 
651   CU_ASSERT_TRUE(_test_lookForReplaces(
652           "one^three",
653           "eins^zwei^three",
654           0, 0, 5, 1,
655           1, 2));
656 
657   CU_ASSERT_FALSE(_test_lookForReplaces(
658           "one^five",
659           "eins^zwei^drei^vier^five",
660           0, 0, 2, 1,
661           0, 0));
662 
663   CU_ASSERT_TRUE(_test_lookForReplaces(
664           "1^d^a^test_starts_here^one^three",
665           "v^test_starts_here^two^three",
666           4, 2, 5, 1,
667           5, 3));
668 
669   CU_ASSERT_FALSE(_test_lookForReplaces(
670           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
671           "v^test_starts_here^^eight",
672           4, 2, 10, 1,
673           4, 2));
674 
675   CU_ASSERT_FALSE(_test_lookForReplaces(
676           "1^d^a^test_starts_here^two^three^four^five^six^seven^",
677           "v^test_starts_here^^seven",
678           4, 2, 2, 1,
679           4, 2));
680 }
681 
test_lookForReplaces2()682 void test_lookForReplaces2() {
683   //some tests in which replace search order is important
684   CU_ASSERT_TRUE(_test_lookForReplaces(
685           "0^a^a^a^1^2^3^4^1^5",
686           "0^b^b^b^4^1^5",
687           3, 3, 5, 1,
688           4, 5)); // match token is "1"
689   CU_ASSERT_FALSE(token_search_diff(
690           "0^a^a^a^1^2^3^4^1^5",
691           "0^b^b^b^4^1^5",
692           3,
693           0, 0, 0));
694 }
695 
696 CU_TestInfo diff_testcases[] = {
697   {"Testing token search:", test_token_search},
698   {"Testing token diff functions, additions:", test_lookForAdditions},
699   {"Testing token diff functions, removals:", test_lookForRemovals},
700   {"Testing token diff functions, replaces:", test_lookForReplaces1},
701   {"Testing token diff functions, replaces complex cases:", test_lookForReplaces2},
702   {"Testing token diff functions, replaces correctly handles max diff: ", test_lookForReplacesNotOverflowing},
703   {"Testing token diff functions, matchNTokens:", test_matchNTokens},
704   {"Testing token diff functions, matchNTokens corner cases:", test_matchNTokensCorners},
705   {"Testing token search_diffs:", test_token_search_diffs},
706   CU_TEST_INFO_NULL
707 };
708