Fossil SCM

Rearrange code and edit comments in diff logic, for clarity of presentation. No functional changes.

drh 2012-02-05 17:19 trunk
Commit 032da543f0932e66c0c419b6acc9e4968aa4e597
Parent d3e83cdb6414ba7…
1 file changed +76 -57
~ src/diff.c
M src/diff.c
+76 -57
--- src/diff.c
+++ src/diff.c
@@ -62,11 +62,21 @@
6262
 ** a bucket in a hash table, as follows: */
6363
 unsigned int iHash; /* 1+(first entry in the hash chain) */
6464
 };
6565
6666
 /*
67
-** A context for running a diff.
67
+** A context for running a raw diff.
68
+**
69
+** The aEdit[] array describes the raw diff. Each triple of integers in
70
+** aEdit[] means:
71
+**
72
+** (1) COPY: Number of lines aFrom and aTo have in common
73
+** (2) DELETE: Number of lines found only in aFrom
74
+** (3) INSERT: Number of lines found only in aTo
75
+**
76
+** The triples repeat until all lines of both aFrom and aTo are accounted
77
+** for.
6878
 */
6979
 typedef struct DContext DContext;
7080
 struct DContext {
7181
 int *aEdit; /* Array of copy/delete/insert triples */
7282
 int nEdit; /* Number of integers (3x num of triples) in aEdit[] */
@@ -147,13 +157,18 @@
147157
 static int same_dline(DLine *pA, DLine *pB){
148158
 return pA->h==pB->h && memcmp(pA->z,pB->z,pA->h & LENGTH_MASK)==0;
149159
 }
150160
151161
 /*
152
-** Append a single line of "diff" output to pOut.
162
+** Append a single line of context-diff output to pOut.
153163
 */
154
-static void appendDiffLine(Blob *pOut, char cPrefix, DLine *pLine, int html){
164
+static void appendDiffLine(
165
+ Blob *pOut, /* Where to write the line of output */
166
+ char cPrefix, /* One of " ", "+", or "-" */
167
+ DLine *pLine, /* The line to be output */
168
+ int html /* True if generating HTML. False for plain text */
169
+){
155170
 blob_append(pOut, &cPrefix, 1);
156171
 if( html ){
157172
 char *zHtml;
158173
 if( cPrefix=='+' ){
159174
 blob_append(pOut, "<span class=\"diffadd\">", -1);
@@ -171,12 +186,14 @@
171186
 }
172187
 blob_append(pOut, "\n", 1);
173188
 }
174189
175190
 /*
176
-** Append line numbers to the context diff output. Zero or negative numbers
177
-** are blanks.
191
+** Add two line numbers to the beginning of an output line for a context
192
+** diff. One or of the other of the two numbers might be zero, which means
193
+** to leave that number field blank. The "html" parameter means to format
194
+** the output for HTML.
178195
 */
179196
 static void appendDiffLineno(Blob *pOut, int lnA, int lnB, int html){
180197
 if( html ) blob_append(pOut, "<span class=\"diffln\">", -1);
181198
 if( lnA>0 ){
182199
 blob_appendf(pOut, "%6d ", lnA);
@@ -189,51 +206,10 @@
189206
 blob_append(pOut, " ", 8);
190207
 }
191208
 if( html ) blob_append(pOut, "</span>", -1);
192209
 }
193210
194
-/*
195
-** Expand the size of aEdit[] array to hold nEdit elements.
196
-*/
197
-static void expandEdit(DContext *p, int nEdit){
198
- p->aEdit = fossil_realloc(p->aEdit, nEdit*sizeof(int));
199
- p->nEditAlloc = nEdit;
200
-}
201
-
202
-/*
203
-** Append a new COPY/DELETE/INSERT triple.
204
-*/
205
-static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){
206
- /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
207
- if( p->nEdit>=3 ){
208
- if( p->aEdit[p->nEdit-1]==0 ){
209
- if( p->aEdit[p->nEdit-2]==0 ){
210
- p->aEdit[p->nEdit-3] += nCopy;
211
- p->aEdit[p->nEdit-2] += nDel;
212
- p->aEdit[p->nEdit-1] += nIns;
213
- return;
214
- }
215
- if( nCopy==0 ){
216
- p->aEdit[p->nEdit-2] += nDel;
217
- p->aEdit[p->nEdit-1] += nIns;
218
- return;
219
- }
220
- }
221
- if( nCopy==0 && nDel==0 ){
222
- p->aEdit[p->nEdit-1] += nIns;
223
- return;
224
- }
225
- }
226
- if( p->nEdit+3>p->nEditAlloc ){
227
- expandEdit(p, p->nEdit*2 + 15);
228
- if( p->aEdit==0 ) return;
229
- }
230
- p->aEdit[p->nEdit++] = nCopy;
231
- p->aEdit[p->nEdit++] = nDel;
232
- p->aEdit[p->nEdit++] = nIns;
233
-}
234
-
235211
236212
 /*
237213
 ** Given a diff context in which the aEdit[] array has been filled
238214
 ** in, compute a context diff into pOut.
239215
 */
@@ -290,15 +266,15 @@
290266
 }
291267
 for(i=1; i<nr; i++){
292268
 na += R[r+i*3];
293269
 nb += R[r+i*3];
294270
 }
295
- /*
296
- * If the patch changes an empty file or results in an empty file,
297
- * the block header must use 0,0 as position indicator and not 1,0.
298
- * Otherwise, patch would be confused and may reject the diff.
299
- */
271
+
272
+ /* Show the header for this block, or if we are doing a modified
273
+ ** context diff that contains line numbers, show the separate from
274
+ ** the previous block.
275
+ */
300276
 if( showLn ){
301277
 if( r==0 ){
302278
 /* Do not show a top divider */
303279
 }else if( html ){
304280
 blob_appendf(pOut, "<span class=\"diffhr\">%.80c</span>\n", '.');
@@ -305,10 +281,15 @@
305281
 }else{
306282
 blob_appendf(pOut, "%.80c\n", '.');
307283
 }
308284
 }else{
309285
 if( html ) blob_appendf(pOut, "<span class=\"diffln\">");
286
+ /*
287
+ * If the patch changes an empty file or results in an empty file,
288
+ * the block header must use 0,0 as position indicator and not 1,0.
289
+ * Otherwise, patch would be confused and may reject the diff.
290
+ */
310291
 blob_appendf(pOut,"@@ -%d,%d +%d,%d @@",
311292
 na ? a+skip+1 : 0, na,
312293
 nb ? b+skip+1 : 0, nb);
313294
 if( html ) blob_appendf(pOut, "</span>");
314295
 blob_append(pOut, "\n", 1);
@@ -521,15 +502,12 @@
521502
 }
522503
 for(i=1; i<nr; i++){
523504
 na += R[r+i*3];
524505
 nb += R[r+i*3];
525506
 }
526
- /*
527
- * If the patch changes an empty file or results in an empty file,
528
- * the block header must use 0,0 as position indicator and not 1,0.
529
- * Otherwise, patch would be confused and may reject the diff.
530
- */
507
+
508
+ /* Draw the separator between blocks */
531509
 if( r>0 ){
532510
 if( escHtml ){
533511
 blob_appendf(pOut, "<span class=\"diffhr\">%.*c</span>\n",
534512
 width*2+16, '.');
535513
 }else{
@@ -765,10 +743,51 @@
765743
 *piEY = iEYb;
766744
 }
767745
 /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n",
768746
 iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY); */
769747
 }
748
+
749
+/*
750
+** Expand the size of aEdit[] array to hold at least nEdit elements.
751
+*/
752
+static void expandEdit(DContext *p, int nEdit){
753
+ p->aEdit = fossil_realloc(p->aEdit, nEdit*sizeof(int));
754
+ p->nEditAlloc = nEdit;
755
+}
756
+
757
+/*
758
+** Append a new COPY/DELETE/INSERT triple.
759
+*/
760
+static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){
761
+ /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
762
+ if( p->nEdit>=3 ){
763
+ if( p->aEdit[p->nEdit-1]==0 ){
764
+ if( p->aEdit[p->nEdit-2]==0 ){
765
+ p->aEdit[p->nEdit-3] += nCopy;
766
+ p->aEdit[p->nEdit-2] += nDel;
767
+ p->aEdit[p->nEdit-1] += nIns;
768
+ return;
769
+ }
770
+ if( nCopy==0 ){
771
+ p->aEdit[p->nEdit-2] += nDel;
772
+ p->aEdit[p->nEdit-1] += nIns;
773
+ return;
774
+ }
775
+ }
776
+ if( nCopy==0 && nDel==0 ){
777
+ p->aEdit[p->nEdit-1] += nIns;
778
+ return;
779
+ }
780
+ }
781
+ if( p->nEdit+3>p->nEditAlloc ){
782
+ expandEdit(p, p->nEdit*2 + 15);
783
+ if( p->aEdit==0 ) return;
784
+ }
785
+ p->aEdit[p->nEdit++] = nCopy;
786
+ p->aEdit[p->nEdit++] = nDel;
787
+ p->aEdit[p->nEdit++] = nIns;
788
+}
770789
771790
 /*
772791
 ** Do a single step in the difference. Compute a sequence of
773792
 ** copy/delete/insert steps that will convert lines iS1 through iE1-1 of
774793
 ** the input into lines iS2 through iE2-1 of the output and write
@@ -798,11 +817,11 @@
798817
799818
 /* Find the longest matching segment between the two sequences */
800819
 longestCommonSequence(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);
801820
802821
 if( iEX>iSX ){
803
- /* A common segement has been found.
822
+ /* A common segment has been found.
804823
 ** Recursively diff either side of the matching segment */
805824
 diff_step(p, iS1, iSX, iS2, iSY);
806825
 if( iEX>iSX ){
807826
 appendTriple(p, iEX - iSX, 0, 0);
808827
 }
809828
--- src/diff.c
+++ src/diff.c
@@ -62,11 +62,21 @@
62 ** a bucket in a hash table, as follows: */
63 unsigned int iHash; /* 1+(first entry in the hash chain) */
64 };
65
66 /*
67 ** A context for running a diff.
 
 
 
 
 
 
 
 
 
 
68 */
69 typedef struct DContext DContext;
70 struct DContext {
71 int *aEdit; /* Array of copy/delete/insert triples */
72 int nEdit; /* Number of integers (3x num of triples) in aEdit[] */
@@ -147,13 +157,18 @@
147 static int same_dline(DLine *pA, DLine *pB){
148 return pA->h==pB->h && memcmp(pA->z,pB->z,pA->h & LENGTH_MASK)==0;
149 }
150
151 /*
152 ** Append a single line of "diff" output to pOut.
153 */
154 static void appendDiffLine(Blob *pOut, char cPrefix, DLine *pLine, int html){
 
 
 
 
 
155 blob_append(pOut, &cPrefix, 1);
156 if( html ){
157 char *zHtml;
158 if( cPrefix=='+' ){
159 blob_append(pOut, "<span class=\"diffadd\">", -1);
@@ -171,12 +186,14 @@
171 }
172 blob_append(pOut, "\n", 1);
173 }
174
175 /*
176 ** Append line numbers to the context diff output. Zero or negative numbers
177 ** are blanks.
 
 
178 */
179 static void appendDiffLineno(Blob *pOut, int lnA, int lnB, int html){
180 if( html ) blob_append(pOut, "<span class=\"diffln\">", -1);
181 if( lnA>0 ){
182 blob_appendf(pOut, "%6d ", lnA);
@@ -189,51 +206,10 @@
189 blob_append(pOut, " ", 8);
190 }
191 if( html ) blob_append(pOut, "</span>", -1);
192 }
193
194 /*
195 ** Expand the size of aEdit[] array to hold nEdit elements.
196 */
197 static void expandEdit(DContext *p, int nEdit){
198 p->aEdit = fossil_realloc(p->aEdit, nEdit*sizeof(int));
199 p->nEditAlloc = nEdit;
200 }
201
202 /*
203 ** Append a new COPY/DELETE/INSERT triple.
204 */
205 static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){
206 /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
207 if( p->nEdit>=3 ){
208 if( p->aEdit[p->nEdit-1]==0 ){
209 if( p->aEdit[p->nEdit-2]==0 ){
210 p->aEdit[p->nEdit-3] += nCopy;
211 p->aEdit[p->nEdit-2] += nDel;
212 p->aEdit[p->nEdit-1] += nIns;
213 return;
214 }
215 if( nCopy==0 ){
216 p->aEdit[p->nEdit-2] += nDel;
217 p->aEdit[p->nEdit-1] += nIns;
218 return;
219 }
220 }
221 if( nCopy==0 && nDel==0 ){
222 p->aEdit[p->nEdit-1] += nIns;
223 return;
224 }
225 }
226 if( p->nEdit+3>p->nEditAlloc ){
227 expandEdit(p, p->nEdit*2 + 15);
228 if( p->aEdit==0 ) return;
229 }
230 p->aEdit[p->nEdit++] = nCopy;
231 p->aEdit[p->nEdit++] = nDel;
232 p->aEdit[p->nEdit++] = nIns;
233 }
234
235
236 /*
237 ** Given a diff context in which the aEdit[] array has been filled
238 ** in, compute a context diff into pOut.
239 */
@@ -290,15 +266,15 @@
290 }
291 for(i=1; i<nr; i++){
292 na += R[r+i*3];
293 nb += R[r+i*3];
294 }
295 /*
296 * If the patch changes an empty file or results in an empty file,
297 * the block header must use 0,0 as position indicator and not 1,0.
298 * Otherwise, patch would be confused and may reject the diff.
299 */
300 if( showLn ){
301 if( r==0 ){
302 /* Do not show a top divider */
303 }else if( html ){
304 blob_appendf(pOut, "<span class=\"diffhr\">%.80c</span>\n", '.');
@@ -305,10 +281,15 @@
305 }else{
306 blob_appendf(pOut, "%.80c\n", '.');
307 }
308 }else{
309 if( html ) blob_appendf(pOut, "<span class=\"diffln\">");
 
 
 
 
 
310 blob_appendf(pOut,"@@ -%d,%d +%d,%d @@",
311 na ? a+skip+1 : 0, na,
312 nb ? b+skip+1 : 0, nb);
313 if( html ) blob_appendf(pOut, "</span>");
314 blob_append(pOut, "\n", 1);
@@ -521,15 +502,12 @@
521 }
522 for(i=1; i<nr; i++){
523 na += R[r+i*3];
524 nb += R[r+i*3];
525 }
526 /*
527 * If the patch changes an empty file or results in an empty file,
528 * the block header must use 0,0 as position indicator and not 1,0.
529 * Otherwise, patch would be confused and may reject the diff.
530 */
531 if( r>0 ){
532 if( escHtml ){
533 blob_appendf(pOut, "<span class=\"diffhr\">%.*c</span>\n",
534 width*2+16, '.');
535 }else{
@@ -765,10 +743,51 @@
765 *piEY = iEYb;
766 }
767 /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n",
768 iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY); */
769 }
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
770
771 /*
772 ** Do a single step in the difference. Compute a sequence of
773 ** copy/delete/insert steps that will convert lines iS1 through iE1-1 of
774 ** the input into lines iS2 through iE2-1 of the output and write
@@ -798,11 +817,11 @@
798
799 /* Find the longest matching segment between the two sequences */
800 longestCommonSequence(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);
801
802 if( iEX>iSX ){
803 /* A common segement has been found.
804 ** Recursively diff either side of the matching segment */
805 diff_step(p, iS1, iSX, iS2, iSY);
806 if( iEX>iSX ){
807 appendTriple(p, iEX - iSX, 0, 0);
808 }
809
--- src/diff.c
+++ src/diff.c
@@ -62,11 +62,21 @@
62 ** a bucket in a hash table, as follows: */
63 unsigned int iHash; /* 1+(first entry in the hash chain) */
64 };
65
66 /*
67 ** A context for running a raw diff.
68 **
69 ** The aEdit[] array describes the raw diff. Each triple of integers in
70 ** aEdit[] means:
71 **
72 ** (1) COPY: Number of lines aFrom and aTo have in common
73 ** (2) DELETE: Number of lines found only in aFrom
74 ** (3) INSERT: Number of lines found only in aTo
75 **
76 ** The triples repeat until all lines of both aFrom and aTo are accounted
77 ** for.
78 */
79 typedef struct DContext DContext;
80 struct DContext {
81 int *aEdit; /* Array of copy/delete/insert triples */
82 int nEdit; /* Number of integers (3x num of triples) in aEdit[] */
@@ -147,13 +157,18 @@
157 static int same_dline(DLine *pA, DLine *pB){
158 return pA->h==pB->h && memcmp(pA->z,pB->z,pA->h & LENGTH_MASK)==0;
159 }
160
161 /*
162 ** Append a single line of context-diff output to pOut.
163 */
164 static void appendDiffLine(
165 Blob *pOut, /* Where to write the line of output */
166 char cPrefix, /* One of " ", "+", or "-" */
167 DLine *pLine, /* The line to be output */
168 int html /* True if generating HTML. False for plain text */
169 ){
170 blob_append(pOut, &cPrefix, 1);
171 if( html ){
172 char *zHtml;
173 if( cPrefix=='+' ){
174 blob_append(pOut, "<span class=\"diffadd\">", -1);
@@ -171,12 +186,14 @@
186 }
187 blob_append(pOut, "\n", 1);
188 }
189
190 /*
191 ** Add two line numbers to the beginning of an output line for a context
192 ** diff. One or of the other of the two numbers might be zero, which means
193 ** to leave that number field blank. The "html" parameter means to format
194 ** the output for HTML.
195 */
196 static void appendDiffLineno(Blob *pOut, int lnA, int lnB, int html){
197 if( html ) blob_append(pOut, "<span class=\"diffln\">", -1);
198 if( lnA>0 ){
199 blob_appendf(pOut, "%6d ", lnA);
@@ -189,51 +206,10 @@
206 blob_append(pOut, " ", 8);
207 }
208 if( html ) blob_append(pOut, "</span>", -1);
209 }
210
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
211
212 /*
213 ** Given a diff context in which the aEdit[] array has been filled
214 ** in, compute a context diff into pOut.
215 */
@@ -290,15 +266,15 @@
266 }
267 for(i=1; i<nr; i++){
268 na += R[r+i*3];
269 nb += R[r+i*3];
270 }
271
272 /* Show the header for this block, or if we are doing a modified
273 ** context diff that contains line numbers, show the separate from
274 ** the previous block.
275 */
276 if( showLn ){
277 if( r==0 ){
278 /* Do not show a top divider */
279 }else if( html ){
280 blob_appendf(pOut, "<span class=\"diffhr\">%.80c</span>\n", '.');
@@ -305,10 +281,15 @@
281 }else{
282 blob_appendf(pOut, "%.80c\n", '.');
283 }
284 }else{
285 if( html ) blob_appendf(pOut, "<span class=\"diffln\">");
286 /*
287 * If the patch changes an empty file or results in an empty file,
288 * the block header must use 0,0 as position indicator and not 1,0.
289 * Otherwise, patch would be confused and may reject the diff.
290 */
291 blob_appendf(pOut,"@@ -%d,%d +%d,%d @@",
292 na ? a+skip+1 : 0, na,
293 nb ? b+skip+1 : 0, nb);
294 if( html ) blob_appendf(pOut, "</span>");
295 blob_append(pOut, "\n", 1);
@@ -521,15 +502,12 @@
502 }
503 for(i=1; i<nr; i++){
504 na += R[r+i*3];
505 nb += R[r+i*3];
506 }
507
508 /* Draw the separator between blocks */
 
 
 
509 if( r>0 ){
510 if( escHtml ){
511 blob_appendf(pOut, "<span class=\"diffhr\">%.*c</span>\n",
512 width*2+16, '.');
513 }else{
@@ -765,10 +743,51 @@
743 *piEY = iEYb;
744 }
745 /* printf("LCS(%d..%d/%d..%d) = %d..%d/%d..%d\n",
746 iS1, iE1, iS2, iE2, *piSX, *piEX, *piSY, *piEY); */
747 }
748
749 /*
750 ** Expand the size of aEdit[] array to hold at least nEdit elements.
751 */
752 static void expandEdit(DContext *p, int nEdit){
753 p->aEdit = fossil_realloc(p->aEdit, nEdit*sizeof(int));
754 p->nEditAlloc = nEdit;
755 }
756
757 /*
758 ** Append a new COPY/DELETE/INSERT triple.
759 */
760 static void appendTriple(DContext *p, int nCopy, int nDel, int nIns){
761 /* printf("APPEND %d/%d/%d\n", nCopy, nDel, nIns); */
762 if( p->nEdit>=3 ){
763 if( p->aEdit[p->nEdit-1]==0 ){
764 if( p->aEdit[p->nEdit-2]==0 ){
765 p->aEdit[p->nEdit-3] += nCopy;
766 p->aEdit[p->nEdit-2] += nDel;
767 p->aEdit[p->nEdit-1] += nIns;
768 return;
769 }
770 if( nCopy==0 ){
771 p->aEdit[p->nEdit-2] += nDel;
772 p->aEdit[p->nEdit-1] += nIns;
773 return;
774 }
775 }
776 if( nCopy==0 && nDel==0 ){
777 p->aEdit[p->nEdit-1] += nIns;
778 return;
779 }
780 }
781 if( p->nEdit+3>p->nEditAlloc ){
782 expandEdit(p, p->nEdit*2 + 15);
783 if( p->aEdit==0 ) return;
784 }
785 p->aEdit[p->nEdit++] = nCopy;
786 p->aEdit[p->nEdit++] = nDel;
787 p->aEdit[p->nEdit++] = nIns;
788 }
789
790 /*
791 ** Do a single step in the difference. Compute a sequence of
792 ** copy/delete/insert steps that will convert lines iS1 through iE1-1 of
793 ** the input into lines iS2 through iE2-1 of the output and write
@@ -798,11 +817,11 @@
817
818 /* Find the longest matching segment between the two sequences */
819 longestCommonSequence(p, iS1, iE1, iS2, iE2, &iSX, &iEX, &iSY, &iEY);
820
821 if( iEX>iSX ){
822 /* A common segment has been found.
823 ** Recursively diff either side of the matching segment */
824 diff_step(p, iS1, iSX, iS2, iSY);
825 if( iEX>iSX ){
826 appendTriple(p, iEX - iSX, 0, 0);
827 }
828

Keyboard Shortcuts

Open search /
Next entry (timeline) j
Previous entry (timeline) k
Open focused entry Enter
Show this help ?
Toggle theme Top nav button