10 #include <_squareVisitor.h>
13 int matchNTokens(
const GArray* textTokens,
size_t textStart,
size_t textLength,
14 const GArray* searchTokens,
size_t searchStart,
size_t searchLength,
15 unsigned int numberOfWantedMatches) {
18 textStart < textLength &&
19 searchStart < searchLength &&
21 tokens_index(textTokens, textStart),
22 tokens_index(searchTokens, searchStart
27 size_t canMatch =
MIN(textLength - textStart, searchLength - searchStart);
28 size_t shouldMatch =
MIN(numberOfWantedMatches, canMatch);
29 for (
size_t i = 1; i < shouldMatch; i++) {
31 tokens_index(textTokens, i + textStart),
32 tokens_index(searchTokens, i + searchStart)))
37 return (matched == shouldMatch);
42 int lookForDiff(
const GArray* textTokens,
const GArray* searchTokens,
43 size_t iText,
size_t iSearch,
44 unsigned int maxAllowedDiff,
unsigned int minAdjacentMatches,
46 size_t searchLength = searchTokens->len;
47 size_t textLength = textTokens->len;
49 size_t searchStopAt =
MIN(iSearch + maxAllowedDiff, searchLength);
50 size_t textStopAt =
MIN(iText + maxAllowedDiff, textLength);
54 for (
unsigned int i = 0; i < SQUARE_VISITOR_LENGTH; i++) {
55 textPos = iText + squareVisitorX[i];
56 searchPos = iSearch + squareVisitorY[i];
58 if ((textPos < textStopAt) && (searchPos < searchStopAt))
59 if (matchNTokens(textTokens, textPos, textLength,
60 searchTokens, searchPos, searchLength,
63 result->search.start = searchPos;
64 result->search.length = searchPos - iSearch;
65 result->text.start = textPos;
66 result->text.length = textPos - iText;
76 size_t* additionsCounter,
size_t* removedCounter,
77 size_t* iText,
size_t* iSearch) {
80 diffCopy.text.start = *iText;
81 diffCopy.search.start = *iSearch;
83 if (diffCopy.search.length == 0)
84 diffCopy.diffType = DIFF_TYPE_ADDITION;
85 else if (diffCopy.text.length == 0)
86 diffCopy.diffType = DIFF_TYPE_REMOVAL;
88 diffCopy.diffType = DIFF_TYPE_REPLACE;
90 *iText = diff->text.start;
91 *iSearch = diff->search.start;
93 g_array_append_val(matchedInfo, diffCopy);
95 *additionsCounter += diffCopy.text.length;
96 *removedCounter += diffCopy.search.length;
101 static void applyTailDiff(GArray* matchedInfo,
103 size_t* removedCounter,
size_t* additionsCounter,
104 size_t* iText,
size_t* iSearch) {
109 .length = searchLength - (*iSearch)
118 applyDiff(&tailDiff, matchedInfo, additionsCounter, removedCounter, iText, iSearch);
121 static void initSimpleMatch(
DiffMatchInfo* simpleMatch,
size_t iText,
size_t iSearch) {
122 simpleMatch->text.start = iText;
123 simpleMatch->text.length = 0;
124 simpleMatch->search.start = iSearch;
125 simpleMatch->search.length = 0;
140 DiffResult* findMatchAsDiffs(
const GArray* textTokens,
const GArray* searchTokens,
141 size_t textStartPosition,
size_t searchStartPosition,
142 unsigned int maxAllowedDiff,
unsigned int minAdjacentMatches) {
143 size_t textLength = textTokens->len;
144 size_t searchLength = searchTokens->len;
146 if ((searchLength<=searchStartPosition) || (textLength<=textStartPosition)) {
151 result->matchedInfo = g_array_new(FALSE, FALSE,
sizeof(
DiffMatchInfo));
152 GArray* matchedInfo = result->matchedInfo;
154 size_t iText = textStartPosition;
157 size_t removedCounter = 0;
158 size_t matchedCounter = 0;
159 size_t additionsCounter = 0;
161 if (searchStartPosition > 0) {
165 .length = searchStartPosition
173 applyDiff(&licenseHeadDiff, matchedInfo, &additionsCounter, &removedCounter, &iText, &iSearch);
174 iSearch = searchStartPosition;
178 while (iText < textLength) {
179 Token* textToken = tokens_index(textTokens, iText);
180 Token* searchToken = tokens_index(searchTokens, iSearch);
181 if (tokenEquals(textToken, searchToken))
186 if (iText < textLength) {
188 simpleMatch.diffType = DIFF_TYPE_MATCH;
189 initSimpleMatch(&simpleMatch, iText, iSearch);
191 while ((iText < textLength) && (iSearch < searchLength)) {
192 Token* textToken = tokens_index(textTokens, iText);
193 Token* searchToken = tokens_index(searchTokens, iSearch);
195 if (tokenEquals(textToken, searchToken)) {
196 simpleMatch.text.length++;
197 simpleMatch.search.length++;
203 g_array_append_val(matchedInfo, simpleMatch);
204 initSimpleMatch(&simpleMatch, iText, iSearch);
207 if (lookForDiff(textTokens, searchTokens,
209 maxAllowedDiff, minAdjacentMatches,
213 &additionsCounter, &removedCounter,
216 simpleMatch.text.start = iText;
217 simpleMatch.search.start = iSearch;
223 if (simpleMatch.text.length > 0) {
224 g_array_append_val(matchedInfo, simpleMatch);
228 if ((iSearch < searchLength) && (searchLength < maxAllowedDiff + iSearch)) {
229 applyTailDiff(matchedInfo, searchLength, &removedCounter, &additionsCounter, &iText, &iSearch);
232 if (matchedCounter + removedCounter != searchLength) {
233 g_array_free(matchedInfo, TRUE);
239 printf(
"diff: (=%zu +%zu -%zu)/%zu\n", matchedCounter, additionsCounter, removedCounter, searchLength);
240 for (
size_t i=0; i<matchedInfo->len; i++) {
242 printf(
"info[%zu]: t[%zu+%zu] %s s[%zu+%zu]}\n",
247 current.search.start,
248 current.search.length
253 result->removed = removedCounter;
254 result->added = additionsCounter;
255 result->matched = matchedCounter;
260 void diffResult_free(
DiffResult* diffResult) {
261 g_array_free(diffResult->matchedInfo, TRUE);
#define MIN(a, b)
Min of two.