Fossil SCM

More improvements to the 3-way merge algorithm.

drh 2009-03-21 14:12 trunk
Commit 83566f24241a01bedbf89d8ca068c7c1b926b4f0
Parent 434830cc0012516…
1 file changed +154 -157
~ src/merge3.c
M src/merge3.c
+154 -157
--- src/merge3.c
+++ src/merge3.c
@@ -32,44 +32,102 @@
3232
 #else
3333
 #define DEBUG(X)
3434
 #define ISDEBUG 0
3535
 #endif
3636
37
-/*
38
-** Opcodes.
39
-**
40
-** Values are important here. The text_diff() function returns an array
41
-** of triples of integers where within each triple, the 0 element is
42
-** the number of lines to copy, the 1 element is the number of lines to
43
-** delete and the 2 element is the number of lines to insert. The CPY,
44
-** DEL, and INS opcodes must correspond to these indices.
45
-*/
46
-#define CPY 0
47
-#define DEL 1
48
-#define INS 2
49
-#define END 3
50
-#define UNK 4
51
-
52
-/*
53
-** Compare a single line of text from pV1 and pV2. If the lines
37
+/* The minimum of two integers */
38
+#define min(A,B) (A<B?A:B)
39
+
40
+/*
41
+** Compare N lines of text from pV1 and pV2. If the lines
5442
 ** are the same, return true. Return false if they are different.
5543
 **
5644
 ** The cursor on both pV1 and pV2 is unchanged.
5745
 */
58
-static int sameLine(Blob *pV1, Blob *pV2){
46
+static int sameLines(Blob *pV1, Blob *pV2, int N){
5947
 char *z1, *z2;
6048
 int i;
6149
50
+ if( N==0 ) return 1;
6251
 z1 = &blob_buffer(pV1)[blob_tell(pV1)];
6352
 z2 = &blob_buffer(pV2)[blob_tell(pV2)];
64
- for(i=0; z1[i]!='\n' && z1[i]==z2[i]; i++){}
65
- return z2[i]=='\n' || (z2[i]=='\r' && z2[i+1]=='\n')
66
- || (z1[i]=='\r' && z2[i]=='\n' && z1[i+1]=='\n');
53
+ for(i=0; z1[i]==z2[i]; i++){
54
+ if( z1[i]=='\n' ){
55
+ N--;
56
+ if( N==0 ) return 1;
57
+ }
58
+ }
59
+ return 0;
60
+}
61
+
62
+/*
63
+** Look at the next edit triple in both aC1 and aC2. If they describe
64
+** an identical edit, then return 1. If the edits are different,
65
+** return 0.
66
+*/
67
+static int sameEdit(int *aC1, int *aC2, Blob *pV1, Blob *pV2){
68
+ if( aC1[0]!=aC2[0] ) return 0;
69
+ if( aC1[1]!=aC2[1] ) return 0;
70
+ if( aC1[2]!=aC2[2] ) return 0;
71
+ if( sameLines(pV1, pV2, aC1[2]) ) return 1;
72
+ return 0;
73
+}
74
+
75
+/*
76
+** The aC[] array contains triples of integers. Within each triple, the
77
+** elements are:
78
+**
79
+** (0) The number of lines to copy
80
+** (1) The number of lines to delete
81
+** (2) The number of liens to insert
82
+**
83
+** Suppose we want to advance over sz lines of the pivot. This routine
84
+** returns true if that advance would land us on a copy operation. It
85
+** returns false if the advance would end on a delete.
86
+*/
87
+static int ends_at_CPY(int *aC, int sz){
88
+ while( sz>0 && (aC[0]>0 || aC[1]>0 || aC[2]>0) ){
89
+ if( aC[0]>=sz ) return 1;
90
+ sz -= aC[0];
91
+ if( aC[1]>sz ) return 0;
92
+ sz -= aC[1];
93
+ aC += 3;
94
+ }
95
+ return 1;
96
+}
97
+
98
+/*
99
+** pSrc contains an edited file where aC[] describes the edit. Part of
100
+** pSrc has already been output. This routine outputs additional lines
101
+** of pSrc - lines that correspond to the next sz lines of the original
102
+** unedited file.
103
+**
104
+** The aC[] array is updated and the new index into aC[] is returned.
105
+*/
106
+static int output_one_side(
107
+ Blob *pOut, /* Write to this blob */
108
+ Blob *pSrc, /* The edited file that is to be copied to pOut */
109
+ int *aC, /* Array of integer triples describing the edit */
110
+ int i, /* Index in aC[] of current location in pSrc */
111
+ int sz /* Number of lines in unedited source to output */
112
+){
113
+ while( sz>0 ){
114
+ if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
115
+ if( aC[i]>sz ){
116
+ blob_copy_lines(pOut, pSrc, sz);
117
+ aC[i] -= sz;
118
+ break;
119
+ }
120
+ blob_copy_lines(pOut, pSrc, aC[i]);
121
+ blob_copy_lines(pOut, pSrc, aC[i+2]);
122
+ sz -= aC[i] + aC[i+1];
123
+ i += 3;
124
+ }
125
+ return i;
67126
 }
68127
69
-/* The minimum of two integers */
70
-#define min(A,B) (A<B?A:B)
128
+
71129
72130
 /*
73131
 ** Do a three-way merge. Initialize pOut to contain the result.
74132
 **
75133
 ** The merge is an edit against pV2. Both pV1 and pV2 have a
@@ -83,23 +141,17 @@
83141
 */
84142
 int blob_merge(Blob *pPivot, Blob *pV1, Blob *pV2, Blob *pOut){
85143
 int *aC1; /* Changes from pPivot to pV1 */
86144
 int *aC2; /* Changes from pPivot to pV2 */
87145
 int i1, i2; /* Index into aC1[] and aC2[] */
88
- int op1, op2; /* Opcode for aC1[] and aC2[] */
89
- int n1, n2; /* Counts for op1 and op2 */
90
- int mn; /* Minimum count of op1 and op2 */
146
+ int nCpy, nDel, nIns; /* Number of lines to copy, delete, or insert */
91147
 int limit1, limit2; /* Sizes of aC1[] and aC2[] */
92148
 int nConflict = 0; /* Number of merge conflicts seen so far */
93149
 static const char zBegin[] = ">>>>>>> BEGIN MERGE CONFLICT\n";
94150
 static const char zMid[] = "============================\n";
95151
 static const char zEnd[] = "<<<<<<< END MERGE CONFLICT\n";
96152
97
-#if ISDEBUG
98
- static const char *zOp[] = { "CPY", "DEL", "INS", "END", "UNK" };
99
-#endif
100
-
101153
 /* Compute the edits that occur from pPivot => pV1 and pPivot => pV2 */
102154
 aC1 = text_diff(pPivot, pV1, 0, 0);
103155
 aC2 = text_diff(pPivot, pV2, 0, 0);
104156
 if( aC2==0 || aC2==0 ){
105157
 free(aC1);
@@ -125,137 +177,82 @@
125177
 for(i2=0; i2<limit2; i2+=3){
126178
 printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
127179
 }
128180
 )
129181
130
- op1 = op2 = UNK;
131
- i1 = i2 = -1;
132
- n1 = n2 = 0;
133
- while(1){
134
- if( op1==UNK ){
135
- if( n1 ){
136
- op1 = i1 % 3;
137
- }else{
138
- i1++;
139
- while( i1<limit1 && aC1[i1]==0 ){ i1++; }
140
- if( i1>=limit1 ){
141
- op1 = END;
142
- }else{
143
- op1 = i1 % 3;
144
- n1 = aC1[i1];
145
- }
146
- }
147
- }
148
- if( op2==UNK ){
149
- if( n2 ){
150
- op2 = i2 % 3;
151
- }else{
152
- i2++;
153
- while( i2<limit2 && aC2[i2]==0 ){ i2++; }
154
- if( i2>=limit2 ){
155
- op2 = END;
156
- }else{
157
- op2 = i2 % 3;
158
- n2 = aC2[i2];
159
- }
160
- }
161
- }
162
- DEBUG( printf("op1=%s(%d) op2=%s(%d)\n", zOp[op1], n1, zOp[op2], n2); )
163
- if( op1==END ){
164
- if( op2==INS ){
165
- DEBUG( printf("INSERT %d FROM 2\n", n2); )
166
- blob_copy_lines(pOut, pV2, n2);
167
- }
168
- break;
169
- }else if( op2==END ){
170
- if( op1==INS ){
171
- DEBUG( printf("INSERT %d FROM 1\n", n1); )
172
- blob_copy_lines(pOut, pV1, n1);
173
- }
174
- break;
175
- }else if( op1==CPY && op2==CPY ){
176
- mn = min(n1,n2);
177
- DEBUG( printf("COPY %d\n", mn); )
178
- blob_copy_lines(pOut, pPivot, mn);
179
- blob_copy_lines(0, pV1, mn);
180
- blob_copy_lines(0, pV2, mn);
181
- n1 -= mn;
182
- n2 -= mn;
183
- op1 = op2 = UNK;
184
- }else if( op1==DEL && op2==DEL ){
185
- mn = min(n1,n2);
186
- DEBUG( printf("SKIP %d both\n", mn); )
187
- blob_copy_lines(0, pPivot, mn);
188
- n1 -= mn;
189
- n2 -= mn;
190
- op1 = op2 = UNK;
191
- }else if( op1==INS && op2==INS && sameLine(pV1, pV2) ){
192
- DEBUG( printf("DUPLICATE INSERT\n"); )
193
- blob_copy_lines(pOut, pV2, 1);
194
- blob_copy_lines(0, pV1, 1);
195
- n1--;
196
- n2--;
197
- op1 = op2 = UNK;
198
- }else if( op1==CPY && op2==DEL ){
199
- mn = min(n1,n2);
200
- DEBUG( printf("SKIP %d two\n", mn); )
201
- blob_copy_lines(0, pPivot, mn);
202
- blob_copy_lines(0, pV1, mn);
203
- n1 -= mn;
204
- n2 -= mn;
205
- op1 = op2 = UNK;
206
- }else if( op2==CPY && op1==DEL ){
207
- mn = min(n1,n2);
208
- DEBUG( printf("SKIP %d one\n", mn); )
209
- blob_copy_lines(0, pPivot, mn);
210
- blob_copy_lines(0, pV2, mn);
211
- n2 -= mn;
212
- n1 -= mn;
213
- op1 = op2 = UNK;
214
- }else if( op1==CPY && op2==INS ){
215
- DEBUG( printf("INSERT %d two\n", n2); )
216
- blob_copy_lines(pOut, pV2, n2);
217
- n2 = 0;
218
- op2 = UNK;
219
- }else if( op2==CPY && op1==INS ){
220
- DEBUG( printf("INSERT %d one\n", n1); )
221
- blob_copy_lines(pOut, pV1, n1);
222
- n1 = 0;
223
- op1 = UNK;
224
- }else{
225
- int toSkip = 0;
226
- nConflict++;
227
- DEBUG( printf("CONFLICT\n"); )
228
- blob_appendf(pOut, zBegin);
229
- if( op1==DEL ){
230
- toSkip = n1;
231
- i1++;
232
- if( aC1[i1] ){
233
- blob_copy_lines(pOut, pV1, aC1[i1]);
234
- }
235
- }else{
236
- blob_copy_lines(pOut, pV1, n1);
237
- }
238
- n1 = 0;
239
- op1 = UNK;
240
- blob_appendf(pOut, zMid);
241
- if( op2==DEL ){
242
- blob_copy_lines(0, pPivot, n2);
243
- i2++;
244
- if( aC2[i2] ){
245
- blob_copy_lines(pOut, pV2, aC2[i2]);
246
- }
247
- }else{
248
- blob_copy_lines(pOut, pV2, n2);
249
- }
250
- if( toSkip ){
251
- blob_copy_lines(0, pPivot, toSkip);
252
- }
253
- n2 = 0;
254
- op2 = UNK;
255
- blob_appendf(pOut, zEnd);
256
- }
182
+ i1 = i2 = 0;
183
+ while( i1<limit1 && i2<limit2 ){
184
+ DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
185
+ i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
186
+ i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
187
+
188
+ if( aC1[i1]>0 && aC2[i2]>0 ){
189
+ nCpy = min(aC1[i1], aC2[i2]);
190
+ DEBUG( printf("COPY %d\n", nCpy); )
191
+ blob_copy_lines(pOut, pPivot, nCpy);
192
+ blob_copy_lines(0, pV1, nCpy);
193
+ blob_copy_lines(0, pV2, nCpy);
194
+ aC1[i1] -= nCpy;
195
+ aC2[i2] -= nCpy;
196
+ }else
197
+ if( aC1[i1] >= aC2[i2+1] && aC2[i2+1]+aC2[i2+2]>0 ){
198
+ nDel = aC2[i2+1];
199
+ nIns = aC2[i2+2];
200
+ DEBUG( printf("EDIT -%d+%d left\n", nDel, nIns); )
201
+ blob_copy_lines(0, pPivot, nDel);
202
+ blob_copy_lines(0, pV1, nDel);
203
+ blob_copy_lines(pOut, pV2, nIns);
204
+ aC1[i1] -= nDel;
205
+ i2 += 3;
206
+ }else
207
+ if( aC2[i2] >= aC1[i1+1] && aC1[i1+1]+aC1[i1+2]>0 ){
208
+ nDel = aC1[i1+1];
209
+ nIns = aC1[i1+2];
210
+ DEBUG( printf("EDIT -%d+%d right\n", nDel, nIns); )
211
+ blob_copy_lines(0, pPivot, nDel);
212
+ blob_copy_lines(0, pV2, nDel);
213
+ blob_copy_lines(pOut, pV1, nIns);
214
+ aC2[i2] -= nDel;
215
+ i1 += 3;
216
+ }else
217
+ if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){
218
+ assert( aC1[i1]==0 );
219
+ nDel = aC1[i1+1];
220
+ nIns = aC1[i1+2];
221
+ DEBUG( printf("EDIT -%d+%d both\n", nDel, nIns); )
222
+ blob_copy_lines(0, pPivot, nDel);
223
+ blob_copy_lines(pOut, pV1, nIns);
224
+ blob_copy_lines(0, pV2, nIns);
225
+ i1 += 3;
226
+ i2 += 3;
227
+ }else
228
+ {
229
+ int sz = 1; /* Size of the conflict in lines */
230
+ nConflict++;
231
+ while( !ends_at_CPY(&aC1[i1], sz) || !ends_at_CPY(&aC2[i2], sz) ){
232
+ sz++;
233
+ }
234
+ DEBUG( printf("CONFLICT %d\n", sz); )
235
+ blob_appendf(pOut, zBegin);
236
+ i1 = output_one_side(pOut, pV1, aC1, i1, sz);
237
+ blob_appendf(pOut, zMid);
238
+ i2 = output_one_side(pOut, pV2, aC2, i2, sz);
239
+ blob_appendf(pOut, zEnd);
240
+ blob_copy_lines(0, pPivot, sz);
241
+ }
242
+ if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
243
+ if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3;
244
+ }
245
+ DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
246
+ i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
247
+ i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
248
+ if( i1<limit1 && aC1[i1+2]>0 ){
249
+ DEBUG( printf("INSERT +%d left\n", aC1[i1+2]); )
250
+ blob_copy_lines(pOut, pV1, aC1[i1+2]);
251
+ }else if( i2<limit2 && aC2[i2+2]>0 ){
252
+ DEBUG( printf("INSERT +%d right\n", aC2[i2+2]); )
253
+ blob_copy_lines(pOut, pV2, aC2[i2+2]);
257254
 }
258255
259256
 free(aC1);
260257
 free(aC2);
261258
 return nConflict;
262259
--- src/merge3.c
+++ src/merge3.c
@@ -32,44 +32,102 @@
32 #else
33 #define DEBUG(X)
34 #define ISDEBUG 0
35 #endif
36
37 /*
38 ** Opcodes.
39 **
40 ** Values are important here. The text_diff() function returns an array
41 ** of triples of integers where within each triple, the 0 element is
42 ** the number of lines to copy, the 1 element is the number of lines to
43 ** delete and the 2 element is the number of lines to insert. The CPY,
44 ** DEL, and INS opcodes must correspond to these indices.
45 */
46 #define CPY 0
47 #define DEL 1
48 #define INS 2
49 #define END 3
50 #define UNK 4
51
52 /*
53 ** Compare a single line of text from pV1 and pV2. If the lines
54 ** are the same, return true. Return false if they are different.
55 **
56 ** The cursor on both pV1 and pV2 is unchanged.
57 */
58 static int sameLine(Blob *pV1, Blob *pV2){
59 char *z1, *z2;
60 int i;
61
 
62 z1 = &blob_buffer(pV1)[blob_tell(pV1)];
63 z2 = &blob_buffer(pV2)[blob_tell(pV2)];
64 for(i=0; z1[i]!='\n' && z1[i]==z2[i]; i++){}
65 return z2[i]=='\n' || (z2[i]=='\r' && z2[i+1]=='\n')
66 || (z1[i]=='\r' && z2[i]=='\n' && z1[i+1]=='\n');
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
67 }
68
69 /* The minimum of two integers */
70 #define min(A,B) (A<B?A:B)
71
72 /*
73 ** Do a three-way merge. Initialize pOut to contain the result.
74 **
75 ** The merge is an edit against pV2. Both pV1 and pV2 have a
@@ -83,23 +141,17 @@
83 */
84 int blob_merge(Blob *pPivot, Blob *pV1, Blob *pV2, Blob *pOut){
85 int *aC1; /* Changes from pPivot to pV1 */
86 int *aC2; /* Changes from pPivot to pV2 */
87 int i1, i2; /* Index into aC1[] and aC2[] */
88 int op1, op2; /* Opcode for aC1[] and aC2[] */
89 int n1, n2; /* Counts for op1 and op2 */
90 int mn; /* Minimum count of op1 and op2 */
91 int limit1, limit2; /* Sizes of aC1[] and aC2[] */
92 int nConflict = 0; /* Number of merge conflicts seen so far */
93 static const char zBegin[] = ">>>>>>> BEGIN MERGE CONFLICT\n";
94 static const char zMid[] = "============================\n";
95 static const char zEnd[] = "<<<<<<< END MERGE CONFLICT\n";
96
97 #if ISDEBUG
98 static const char *zOp[] = { "CPY", "DEL", "INS", "END", "UNK" };
99 #endif
100
101 /* Compute the edits that occur from pPivot => pV1 and pPivot => pV2 */
102 aC1 = text_diff(pPivot, pV1, 0, 0);
103 aC2 = text_diff(pPivot, pV2, 0, 0);
104 if( aC2==0 || aC2==0 ){
105 free(aC1);
@@ -125,137 +177,82 @@
125 for(i2=0; i2<limit2; i2+=3){
126 printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
127 }
128 )
129
130 op1 = op2 = UNK;
131 i1 = i2 = -1;
132 n1 = n2 = 0;
133 while(1){
134 if( op1==UNK ){
135 if( n1 ){
136 op1 = i1 % 3;
137 }else{
138 i1++;
139 while( i1<limit1 && aC1[i1]==0 ){ i1++; }
140 if( i1>=limit1 ){
141 op1 = END;
142 }else{
143 op1 = i1 % 3;
144 n1 = aC1[i1];
145 }
146 }
147 }
148 if( op2==UNK ){
149 if( n2 ){
150 op2 = i2 % 3;
151 }else{
152 i2++;
153 while( i2<limit2 && aC2[i2]==0 ){ i2++; }
154 if( i2>=limit2 ){
155 op2 = END;
156 }else{
157 op2 = i2 % 3;
158 n2 = aC2[i2];
159 }
160 }
161 }
162 DEBUG( printf("op1=%s(%d) op2=%s(%d)\n", zOp[op1], n1, zOp[op2], n2); )
163 if( op1==END ){
164 if( op2==INS ){
165 DEBUG( printf("INSERT %d FROM 2\n", n2); )
166 blob_copy_lines(pOut, pV2, n2);
167 }
168 break;
169 }else if( op2==END ){
170 if( op1==INS ){
171 DEBUG( printf("INSERT %d FROM 1\n", n1); )
172 blob_copy_lines(pOut, pV1, n1);
173 }
174 break;
175 }else if( op1==CPY && op2==CPY ){
176 mn = min(n1,n2);
177 DEBUG( printf("COPY %d\n", mn); )
178 blob_copy_lines(pOut, pPivot, mn);
179 blob_copy_lines(0, pV1, mn);
180 blob_copy_lines(0, pV2, mn);
181 n1 -= mn;
182 n2 -= mn;
183 op1 = op2 = UNK;
184 }else if( op1==DEL && op2==DEL ){
185 mn = min(n1,n2);
186 DEBUG( printf("SKIP %d both\n", mn); )
187 blob_copy_lines(0, pPivot, mn);
188 n1 -= mn;
189 n2 -= mn;
190 op1 = op2 = UNK;
191 }else if( op1==INS && op2==INS && sameLine(pV1, pV2) ){
192 DEBUG( printf("DUPLICATE INSERT\n"); )
193 blob_copy_lines(pOut, pV2, 1);
194 blob_copy_lines(0, pV1, 1);
195 n1--;
196 n2--;
197 op1 = op2 = UNK;
198 }else if( op1==CPY && op2==DEL ){
199 mn = min(n1,n2);
200 DEBUG( printf("SKIP %d two\n", mn); )
201 blob_copy_lines(0, pPivot, mn);
202 blob_copy_lines(0, pV1, mn);
203 n1 -= mn;
204 n2 -= mn;
205 op1 = op2 = UNK;
206 }else if( op2==CPY && op1==DEL ){
207 mn = min(n1,n2);
208 DEBUG( printf("SKIP %d one\n", mn); )
209 blob_copy_lines(0, pPivot, mn);
210 blob_copy_lines(0, pV2, mn);
211 n2 -= mn;
212 n1 -= mn;
213 op1 = op2 = UNK;
214 }else if( op1==CPY && op2==INS ){
215 DEBUG( printf("INSERT %d two\n", n2); )
216 blob_copy_lines(pOut, pV2, n2);
217 n2 = 0;
218 op2 = UNK;
219 }else if( op2==CPY && op1==INS ){
220 DEBUG( printf("INSERT %d one\n", n1); )
221 blob_copy_lines(pOut, pV1, n1);
222 n1 = 0;
223 op1 = UNK;
224 }else{
225 int toSkip = 0;
226 nConflict++;
227 DEBUG( printf("CONFLICT\n"); )
228 blob_appendf(pOut, zBegin);
229 if( op1==DEL ){
230 toSkip = n1;
231 i1++;
232 if( aC1[i1] ){
233 blob_copy_lines(pOut, pV1, aC1[i1]);
234 }
235 }else{
236 blob_copy_lines(pOut, pV1, n1);
237 }
238 n1 = 0;
239 op1 = UNK;
240 blob_appendf(pOut, zMid);
241 if( op2==DEL ){
242 blob_copy_lines(0, pPivot, n2);
243 i2++;
244 if( aC2[i2] ){
245 blob_copy_lines(pOut, pV2, aC2[i2]);
246 }
247 }else{
248 blob_copy_lines(pOut, pV2, n2);
249 }
250 if( toSkip ){
251 blob_copy_lines(0, pPivot, toSkip);
252 }
253 n2 = 0;
254 op2 = UNK;
255 blob_appendf(pOut, zEnd);
256 }
257 }
258
259 free(aC1);
260 free(aC2);
261 return nConflict;
262
--- src/merge3.c
+++ src/merge3.c
@@ -32,44 +32,102 @@
32 #else
33 #define DEBUG(X)
34 #define ISDEBUG 0
35 #endif
36
37 /* The minimum of two integers */
38 #define min(A,B) (A<B?A:B)
39
40 /*
41 ** Compare N lines of text from pV1 and pV2. If the lines
 
 
 
 
 
 
 
 
 
 
 
 
42 ** are the same, return true. Return false if they are different.
43 **
44 ** The cursor on both pV1 and pV2 is unchanged.
45 */
46 static int sameLines(Blob *pV1, Blob *pV2, int N){
47 char *z1, *z2;
48 int i;
49
50 if( N==0 ) return 1;
51 z1 = &blob_buffer(pV1)[blob_tell(pV1)];
52 z2 = &blob_buffer(pV2)[blob_tell(pV2)];
53 for(i=0; z1[i]==z2[i]; i++){
54 if( z1[i]=='\n' ){
55 N--;
56 if( N==0 ) return 1;
57 }
58 }
59 return 0;
60 }
61
62 /*
63 ** Look at the next edit triple in both aC1 and aC2. If they describe
64 ** an identical edit, then return 1. If the edits are different,
65 ** return 0.
66 */
67 static int sameEdit(int *aC1, int *aC2, Blob *pV1, Blob *pV2){
68 if( aC1[0]!=aC2[0] ) return 0;
69 if( aC1[1]!=aC2[1] ) return 0;
70 if( aC1[2]!=aC2[2] ) return 0;
71 if( sameLines(pV1, pV2, aC1[2]) ) return 1;
72 return 0;
73 }
74
75 /*
76 ** The aC[] array contains triples of integers. Within each triple, the
77 ** elements are:
78 **
79 ** (0) The number of lines to copy
80 ** (1) The number of lines to delete
81 ** (2) The number of liens to insert
82 **
83 ** Suppose we want to advance over sz lines of the pivot. This routine
84 ** returns true if that advance would land us on a copy operation. It
85 ** returns false if the advance would end on a delete.
86 */
87 static int ends_at_CPY(int *aC, int sz){
88 while( sz>0 && (aC[0]>0 || aC[1]>0 || aC[2]>0) ){
89 if( aC[0]>=sz ) return 1;
90 sz -= aC[0];
91 if( aC[1]>sz ) return 0;
92 sz -= aC[1];
93 aC += 3;
94 }
95 return 1;
96 }
97
98 /*
99 ** pSrc contains an edited file where aC[] describes the edit. Part of
100 ** pSrc has already been output. This routine outputs additional lines
101 ** of pSrc - lines that correspond to the next sz lines of the original
102 ** unedited file.
103 **
104 ** The aC[] array is updated and the new index into aC[] is returned.
105 */
106 static int output_one_side(
107 Blob *pOut, /* Write to this blob */
108 Blob *pSrc, /* The edited file that is to be copied to pOut */
109 int *aC, /* Array of integer triples describing the edit */
110 int i, /* Index in aC[] of current location in pSrc */
111 int sz /* Number of lines in unedited source to output */
112 ){
113 while( sz>0 ){
114 if( aC[i]==0 && aC[i+1]==0 && aC[i+2]==0 ) break;
115 if( aC[i]>sz ){
116 blob_copy_lines(pOut, pSrc, sz);
117 aC[i] -= sz;
118 break;
119 }
120 blob_copy_lines(pOut, pSrc, aC[i]);
121 blob_copy_lines(pOut, pSrc, aC[i+2]);
122 sz -= aC[i] + aC[i+1];
123 i += 3;
124 }
125 return i;
126 }
127
128
 
129
130 /*
131 ** Do a three-way merge. Initialize pOut to contain the result.
132 **
133 ** The merge is an edit against pV2. Both pV1 and pV2 have a
@@ -83,23 +141,17 @@
141 */
142 int blob_merge(Blob *pPivot, Blob *pV1, Blob *pV2, Blob *pOut){
143 int *aC1; /* Changes from pPivot to pV1 */
144 int *aC2; /* Changes from pPivot to pV2 */
145 int i1, i2; /* Index into aC1[] and aC2[] */
146 int nCpy, nDel, nIns; /* Number of lines to copy, delete, or insert */
 
 
147 int limit1, limit2; /* Sizes of aC1[] and aC2[] */
148 int nConflict = 0; /* Number of merge conflicts seen so far */
149 static const char zBegin[] = ">>>>>>> BEGIN MERGE CONFLICT\n";
150 static const char zMid[] = "============================\n";
151 static const char zEnd[] = "<<<<<<< END MERGE CONFLICT\n";
152
 
 
 
 
153 /* Compute the edits that occur from pPivot => pV1 and pPivot => pV2 */
154 aC1 = text_diff(pPivot, pV1, 0, 0);
155 aC2 = text_diff(pPivot, pV2, 0, 0);
156 if( aC2==0 || aC2==0 ){
157 free(aC1);
@@ -125,137 +177,82 @@
177 for(i2=0; i2<limit2; i2+=3){
178 printf("c2: %4d %4d %4d\n", aC2[i2], aC2[i2+1], aC2[i2+2]);
179 }
180 )
181
182 i1 = i2 = 0;
183 while( i1<limit1 && i2<limit2 ){
184 DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
185 i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
186 i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
187
188 if( aC1[i1]>0 && aC2[i2]>0 ){
189 nCpy = min(aC1[i1], aC2[i2]);
190 DEBUG( printf("COPY %d\n", nCpy); )
191 blob_copy_lines(pOut, pPivot, nCpy);
192 blob_copy_lines(0, pV1, nCpy);
193 blob_copy_lines(0, pV2, nCpy);
194 aC1[i1] -= nCpy;
195 aC2[i2] -= nCpy;
196 }else
197 if( aC1[i1] >= aC2[i2+1] && aC2[i2+1]+aC2[i2+2]>0 ){
198 nDel = aC2[i2+1];
199 nIns = aC2[i2+2];
200 DEBUG( printf("EDIT -%d+%d left\n", nDel, nIns); )
201 blob_copy_lines(0, pPivot, nDel);
202 blob_copy_lines(0, pV1, nDel);
203 blob_copy_lines(pOut, pV2, nIns);
204 aC1[i1] -= nDel;
205 i2 += 3;
206 }else
207 if( aC2[i2] >= aC1[i1+1] && aC1[i1+1]+aC1[i1+2]>0 ){
208 nDel = aC1[i1+1];
209 nIns = aC1[i1+2];
210 DEBUG( printf("EDIT -%d+%d right\n", nDel, nIns); )
211 blob_copy_lines(0, pPivot, nDel);
212 blob_copy_lines(0, pV2, nDel);
213 blob_copy_lines(pOut, pV1, nIns);
214 aC2[i2] -= nDel;
215 i1 += 3;
216 }else
217 if( sameEdit(&aC1[i1], &aC2[i2], pV1, pV2) ){
218 assert( aC1[i1]==0 );
219 nDel = aC1[i1+1];
220 nIns = aC1[i1+2];
221 DEBUG( printf("EDIT -%d+%d both\n", nDel, nIns); )
222 blob_copy_lines(0, pPivot, nDel);
223 blob_copy_lines(pOut, pV1, nIns);
224 blob_copy_lines(0, pV2, nIns);
225 i1 += 3;
226 i2 += 3;
227 }else
228 {
229 int sz = 1; /* Size of the conflict in lines */
230 nConflict++;
231 while( !ends_at_CPY(&aC1[i1], sz) || !ends_at_CPY(&aC2[i2], sz) ){
232 sz++;
233 }
234 DEBUG( printf("CONFLICT %d\n", sz); )
235 blob_appendf(pOut, zBegin);
236 i1 = output_one_side(pOut, pV1, aC1, i1, sz);
237 blob_appendf(pOut, zMid);
238 i2 = output_one_side(pOut, pV2, aC2, i2, sz);
239 blob_appendf(pOut, zEnd);
240 blob_copy_lines(0, pPivot, sz);
241 }
242 if( i1<limit1 && aC1[i1]==0 && aC1[i1+1]==0 && aC1[i1+2]==0 ) i1+=3;
243 if( i2<limit2 && aC2[i2]==0 && aC2[i2+1]==0 && aC2[i2+2]==0 ) i2+=3;
244 }
245 DEBUG( printf("%d: %2d %2d %2d %d: %2d %2d %2d\n",
246 i1/3, aC1[i1], aC1[i1+1], aC1[i1+2],
247 i2/3, aC2[i2], aC2[i2+1], aC2[i2+2]); )
248 if( i1<limit1 && aC1[i1+2]>0 ){
249 DEBUG( printf("INSERT +%d left\n", aC1[i1+2]); )
250 blob_copy_lines(pOut, pV1, aC1[i1+2]);
251 }else if( i2<limit2 && aC2[i2+2]>0 ){
252 DEBUG( printf("INSERT +%d right\n", aC2[i2+2]); )
253 blob_copy_lines(pOut, pV2, aC2[i2+2]);
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
254 }
255
256 free(aC1);
257 free(aC2);
258 return nConflict;
259

Keyboard Shortcuts

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