2 * LibXDiff by Davide Libenzi ( File Differential Library )
3 * Copyright (C) 2003-2006 Davide Libenzi, Johannes E. Schindelin
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Lesser General Public
7 * License as published by the Free Software Foundation; either
8 * version 2.1 of the License, or (at your option) any later version.
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Lesser General Public License for more details.
15 * You should have received a copy of the GNU Lesser General Public
16 * License along with this library; if not, write to the Free Software
17 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 * Davide Libenzi <davidel@xmailserver.org>
25 typedef struct s_xdmerge
{
26 struct s_xdmerge
*next
;
29 * 1 = no conflict, take first,
30 * 2 = no conflict, take second.
37 static int xdl_append_merge(xdmerge_t
**merge
, int mode
,
38 long i1
, long chg1
, long i2
, long chg2
)
40 xdmerge_t
*m
= *merge
;
41 if (m
&& mode
== m
->mode
&&
42 (i1
== m
->i1
+ m
->chg1
|| i2
== m
->i2
+ m
->chg2
)) {
43 m
->chg1
= i1
+ chg1
- m
->i1
;
44 m
->chg2
= i2
+ chg2
- m
->i2
;
46 m
= xdl_malloc(sizeof(xdmerge_t
));
62 static int xdl_cleanup_merge(xdmerge_t
*c
)
67 /* were there conflicts? */
68 for (; c
; c
= next_c
) {
77 static int xdl_merge_cmp_lines(xdfenv_t
*xe1
, int i1
, xdfenv_t
*xe2
, int i2
,
78 int line_count
, long flags
)
81 xrecord_t
**rec1
= xe1
->xdf2
.recs
+ i1
;
82 xrecord_t
**rec2
= xe2
->xdf2
.recs
+ i2
;
84 for (i
= 0; i
< line_count
; i
++) {
85 int result
= xdl_recmatch(rec1
[i
]->ptr
, rec1
[i
]->size
,
86 rec2
[i
]->ptr
, rec2
[i
]->size
, flags
);
93 static int xdl_recs_copy(xdfenv_t
*xe
, int i
, int count
, int add_nl
, char *dest
)
95 xrecord_t
**recs
= xe
->xdf2
.recs
+ i
;
101 for (i
= 0; i
< count
; size
+= recs
[i
++]->size
)
103 memcpy(dest
+ size
, recs
[i
]->ptr
, recs
[i
]->size
);
105 i
= recs
[count
- 1]->size
;
106 if (i
== 0 || recs
[count
- 1]->ptr
[i
- 1] != '\n') {
115 static int xdl_fill_merge_buffer(xdfenv_t
*xe1
, const char *name1
,
116 xdfenv_t
*xe2
, const char *name2
, xdmerge_t
*m
, char *dest
)
118 const int marker_size
= 7;
119 int marker1_size
= (name1
? strlen(name1
) + 1 : 0);
120 int marker2_size
= (name2
? strlen(name2
) + 1 : 0);
121 int conflict_marker_size
= 3 * (marker_size
+ 1)
122 + marker1_size
+ marker2_size
;
125 for (size
= i1
= 0; m
; m
= m
->next
) {
127 size
+= xdl_recs_copy(xe1
, i1
, m
->i1
- i1
, 0,
128 dest
? dest
+ size
: NULL
);
130 for (j
= 0; j
< marker_size
; j
++)
134 memcpy(dest
+ size
+ 1, name1
,
136 size
+= marker1_size
;
140 size
+= conflict_marker_size
;
141 size
+= xdl_recs_copy(xe1
, m
->i1
, m
->chg1
, 1,
142 dest
? dest
+ size
: NULL
);
144 for (j
= 0; j
< marker_size
; j
++)
148 size
+= xdl_recs_copy(xe2
, m
->i2
, m
->chg2
, 1,
149 dest
? dest
+ size
: NULL
);
151 for (j
= 0; j
< marker_size
; j
++)
155 memcpy(dest
+ size
+ 1, name2
,
157 size
+= marker2_size
;
161 } else if (m
->mode
== 1)
162 size
+= xdl_recs_copy(xe1
, i1
, m
->i1
+ m
->chg1
- i1
, 0,
163 dest
? dest
+ size
: NULL
);
164 else if (m
->mode
== 2)
165 size
+= xdl_recs_copy(xe2
, m
->i2
- m
->i1
+ i1
,
166 m
->i1
+ m
->chg2
- i1
, 0,
167 dest
? dest
+ size
: NULL
);
168 i1
= m
->i1
+ m
->chg1
;
170 size
+= xdl_recs_copy(xe1
, i1
, xe1
->xdf2
.nrec
- i1
, 0,
171 dest
? dest
+ size
: NULL
);
176 * Sometimes, changes are not quite identical, but differ in only a few
177 * lines. Try hard to show only these few lines as conflicting.
179 static int xdl_refine_conflicts(xdfenv_t
*xe1
, xdfenv_t
*xe2
, xdmerge_t
*m
,
180 xpparam_t
const *xpp
)
182 for (; m
; m
= m
->next
) {
185 xdchange_t
*xscr
, *x
;
186 int i1
= m
->i1
, i2
= m
->i2
;
188 /* let's handle just the conflicts */
193 * This probably does not work outside git, since
194 * we have a very simple mmfile structure.
196 t1
.ptr
= (char *)xe1
->xdf2
.recs
[m
->i1
]->ptr
;
197 t1
.size
= xe1
->xdf2
.recs
[m
->i1
+ m
->chg1
]->ptr
198 + xe1
->xdf2
.recs
[m
->i1
+ m
->chg1
]->size
- t1
.ptr
;
199 t2
.ptr
= (char *)xe2
->xdf2
.recs
[m
->i1
]->ptr
;
200 t2
.size
= xe2
->xdf2
.recs
[m
->i1
+ m
->chg1
]->ptr
201 + xe2
->xdf2
.recs
[m
->i1
+ m
->chg1
]->size
- t2
.ptr
;
202 if (xdl_do_diff(&t1
, &t2
, xpp
, &xe
) < 0)
204 if (xdl_change_compact(&xe
.xdf1
, &xe
.xdf2
, xpp
->flags
) < 0 ||
205 xdl_change_compact(&xe
.xdf2
, &xe
.xdf1
, xpp
->flags
) < 0 ||
206 xdl_build_script(&xe
, &xscr
) < 0) {
211 /* If this happens, it's a bug. */
216 m
->i1
= xscr
->i1
+ i1
;
217 m
->chg1
= xscr
->chg1
;
218 m
->i2
= xscr
->i2
+ i2
;
219 m
->chg2
= xscr
->chg2
;
221 xdmerge_t
*m2
= xdl_malloc(sizeof(xdmerge_t
));
232 m
->i1
= xscr
->i1
+ i1
;
233 m
->chg1
= xscr
->chg1
;
234 m
->i2
= xscr
->i2
+ i2
;
235 m
->chg2
= xscr
->chg2
;
244 * level == 0: mark all overlapping changes as conflict
245 * level == 1: mark overlapping changes as conflict only if not identical
246 * level == 2: analyze non-identical changes for minimal conflict set
248 * returns < 0 on error, == 0 for no conflicts, else number of conflicts
250 static int xdl_do_merge(xdfenv_t
*xe1
, xdchange_t
*xscr1
, const char *name1
,
251 xdfenv_t
*xe2
, xdchange_t
*xscr2
, const char *name2
,
252 int level
, xpparam_t
const *xpp
, mmbuffer_t
*result
) {
253 xdmerge_t
*changes
, *c
;
254 int i1
, i2
, chg1
, chg2
;
258 while (xscr1
&& xscr2
) {
261 if (xscr1
->i1
+ xscr1
->chg1
< xscr2
->i1
) {
263 i2
= xscr2
->i2
- xscr2
->i1
+ xscr1
->i1
;
266 if (xdl_append_merge(&c
, 1, i1
, chg1
, i2
, chg2
)) {
267 xdl_cleanup_merge(changes
);
273 if (xscr2
->i1
+ xscr2
->chg1
< xscr1
->i1
) {
274 i1
= xscr1
->i2
- xscr1
->i1
+ xscr2
->i1
;
278 if (xdl_append_merge(&c
, 2, i1
, chg1
, i2
, chg2
)) {
279 xdl_cleanup_merge(changes
);
285 if (level
< 1 || xscr1
->i1
!= xscr2
->i1
||
286 xscr1
->chg1
!= xscr2
->chg1
||
287 xscr1
->chg2
!= xscr2
->chg2
||
288 xdl_merge_cmp_lines(xe1
, xscr1
->i2
,
290 xscr1
->chg2
, xpp
->flags
)) {
292 int off
= xscr1
->i1
- xscr2
->i1
;
293 int ffo
= off
+ xscr1
->chg1
- xscr2
->chg1
;
301 chg1
= xscr1
->i2
+ xscr1
->chg2
- i1
;
302 chg2
= xscr2
->i2
+ xscr2
->chg2
- i2
;
307 if (xdl_append_merge(&c
, 0, i1
, chg1
, i2
, chg2
)) {
308 xdl_cleanup_merge(changes
);
313 i1
= xscr1
->i1
+ xscr1
->chg1
;
314 i2
= xscr2
->i1
+ xscr2
->chg1
;
317 xscr1
->chg1
-= i1
- i2
;
319 xscr1
->i2
+= xscr1
->chg2
;
322 } else if (i2
> i1
) {
323 xscr2
->chg1
-= i2
- i1
;
325 xscr2
->i2
+= xscr2
->chg2
;
337 i2
= xscr1
->i1
+ xe2
->xdf2
.nrec
- xe2
->xdf1
.nrec
;
340 if (xdl_append_merge(&c
, 1, i1
, chg1
, i2
, chg2
)) {
341 xdl_cleanup_merge(changes
);
349 i1
= xscr2
->i1
+ xe1
->xdf2
.nrec
- xe1
->xdf1
.nrec
;
353 if (xdl_append_merge(&c
, 2, i1
, chg1
, i2
, chg2
)) {
354 xdl_cleanup_merge(changes
);
361 /* refine conflicts */
362 if (level
> 1 && xdl_refine_conflicts(xe1
, xe2
, changes
, xpp
) < 0) {
363 xdl_cleanup_merge(changes
);
368 int size
= xdl_fill_merge_buffer(xe1
, name1
, xe2
, name2
,
370 result
->ptr
= xdl_malloc(size
);
372 xdl_cleanup_merge(changes
);
376 xdl_fill_merge_buffer(xe1
, name1
, xe2
, name2
, changes
,
379 return xdl_cleanup_merge(changes
);
382 int xdl_merge(mmfile_t
*orig
, mmfile_t
*mf1
, const char *name1
,
383 mmfile_t
*mf2
, const char *name2
,
384 xpparam_t
const *xpp
, int level
, mmbuffer_t
*result
) {
385 xdchange_t
*xscr1
, *xscr2
;
392 if (xdl_do_diff(orig
, mf1
, xpp
, &xe1
) < 0 ||
393 xdl_do_diff(orig
, mf2
, xpp
, &xe2
) < 0) {
396 if (xdl_change_compact(&xe1
.xdf1
, &xe1
.xdf2
, xpp
->flags
) < 0 ||
397 xdl_change_compact(&xe1
.xdf2
, &xe1
.xdf1
, xpp
->flags
) < 0 ||
398 xdl_build_script(&xe1
, &xscr1
) < 0) {
402 if (xdl_change_compact(&xe2
.xdf1
, &xe2
.xdf2
, xpp
->flags
) < 0 ||
403 xdl_change_compact(&xe2
.xdf2
, &xe2
.xdf1
, xpp
->flags
) < 0 ||
404 xdl_build_script(&xe2
, &xscr2
) < 0) {
409 if (xscr1
|| xscr2
) {
411 result
->ptr
= xdl_malloc(mf2
->size
);
412 memcpy(result
->ptr
, mf2
->ptr
, mf2
->size
);
413 result
->size
= mf2
->size
;
415 result
->ptr
= xdl_malloc(mf1
->size
);
416 memcpy(result
->ptr
, mf1
->ptr
, mf1
->size
);
417 result
->size
= mf1
->size
;
419 status
= xdl_do_merge(&xe1
, xscr1
, name1
,
423 xdl_free_script(xscr1
);
424 xdl_free_script(xscr2
);