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, see
17 * <http://www.gnu.org/licenses/>.
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.
31 * 3 = no conflict, take both.
35 * These point at the respective postimages. E.g. <i1,chg1> is
36 * how side #1 wants to change the common ancestor; if there is no
37 * overlap, lines before i1 in the postimage of side #1 appear
38 * in the merge result as a region touched by neither side.
43 * These point at the preimage; of course there is just one
44 * preimage, that is from the shared common ancestor.
50 static int xdl_append_merge(xdmerge_t
**merge
, int mode
,
55 xdmerge_t
*m
= *merge
;
56 if (m
&& (i1
<= m
->i1
+ m
->chg1
|| i2
<= m
->i2
+ m
->chg2
)) {
59 m
->chg0
= i0
+ chg0
- m
->i0
;
60 m
->chg1
= i1
+ chg1
- m
->i1
;
61 m
->chg2
= i2
+ chg2
- m
->i2
;
63 m
= xdl_malloc(sizeof(xdmerge_t
));
81 static int xdl_cleanup_merge(xdmerge_t
*c
)
86 /* were there conflicts? */
87 for (; c
; c
= next_c
) {
96 static int xdl_merge_cmp_lines(xdfenv_t
*xe1
, int i1
, xdfenv_t
*xe2
, int i2
,
97 int line_count
, long flags
)
100 xrecord_t
**rec1
= xe1
->xdf2
.recs
+ i1
;
101 xrecord_t
**rec2
= xe2
->xdf2
.recs
+ i2
;
103 for (i
= 0; i
< line_count
; i
++) {
104 int result
= xdl_recmatch(rec1
[i
]->ptr
, rec1
[i
]->size
,
105 rec2
[i
]->ptr
, rec2
[i
]->size
, flags
);
112 static int xdl_recs_copy_0(size_t *out
, int use_orig
, xdfenv_t
*xe
, int i
, int count
, int needs_cr
, int add_nl
, char *dest
)
119 recs
= (use_orig
? xe
->xdf1
.recs
: xe
->xdf2
.recs
) + i
;
124 for (i
= 0; i
< count
; ) {
126 memcpy(dest
+ size
, recs
[i
]->ptr
, recs
[i
]->size
);
128 GITERR_CHECK_ALLOC_ADD(&size
, size
, recs
[i
++]->size
);
132 i
= recs
[count
- 1]->size
;
133 if (i
== 0 || recs
[count
- 1]->ptr
[i
- 1] != '\n') {
137 GITERR_CHECK_ALLOC_ADD(&size
, size
, 1);
143 GITERR_CHECK_ALLOC_ADD(&size
, size
, 1);
151 static int xdl_recs_copy(size_t *out
, xdfenv_t
*xe
, int i
, int count
, int needs_cr
, int add_nl
, char *dest
)
153 return xdl_recs_copy_0(out
, 0, xe
, i
, count
, needs_cr
, add_nl
, dest
);
156 static int xdl_orig_copy(size_t *out
, xdfenv_t
*xe
, int i
, int count
, int needs_cr
, int add_nl
, char *dest
)
158 return xdl_recs_copy_0(out
, 1, xe
, i
, count
, needs_cr
, add_nl
, dest
);
162 * Returns 1 if the i'th line ends in CR/LF (if it is the last line and
163 * has no eol, the preceding line, if any), 0 if it ends in LF-only, and
164 * -1 if the line ending cannot be determined.
166 static int is_eol_crlf(xdfile_t
*file
, int i
)
170 if (i
< file
->nrec
- 1)
171 /* All lines before the last *must* end in LF */
172 return (size
= file
->recs
[i
]->size
) > 1 &&
173 file
->recs
[i
]->ptr
[size
- 2] == '\r';
175 /* Cannot determine eol style from empty file */
177 if ((size
= file
->recs
[i
]->size
) &&
178 file
->recs
[i
]->ptr
[size
- 1] == '\n')
179 /* Last line; ends in LF; Is it CR/LF? */
181 file
->recs
[i
]->ptr
[size
- 2] == '\r';
183 /* The only line has no eol */
185 /* Determine eol from second-to-last line */
186 return (size
= file
->recs
[i
- 1]->size
) > 1 &&
187 file
->recs
[i
- 1]->ptr
[size
- 2] == '\r';
190 static int is_cr_needed(xdfenv_t
*xe1
, xdfenv_t
*xe2
, xdmerge_t
*m
)
194 /* Match post-images' preceding, or first, lines' end-of-line style */
195 needs_cr
= is_eol_crlf(&xe1
->xdf2
, m
->i1
? m
->i1
- 1 : 0);
197 needs_cr
= is_eol_crlf(&xe2
->xdf2
, m
->i2
? m
->i2
- 1 : 0);
198 /* Look at pre-image's first line, unless we already settled on LF */
200 needs_cr
= is_eol_crlf(&xe1
->xdf1
, 0);
201 /* If still undecided, use LF-only */
202 return needs_cr
< 0 ? 0 : needs_cr
;
205 static int fill_conflict_hunk(size_t *out
, xdfenv_t
*xe1
, const char *name1
,
206 xdfenv_t
*xe2
, const char *name2
,
208 size_t size
, int i
, int style
,
209 xdmerge_t
*m
, char *dest
, int marker_size
)
211 int marker1_size
= (name1
? (int)strlen(name1
) + 1 : 0);
212 int marker2_size
= (name2
? (int)strlen(name2
) + 1 : 0);
213 int marker3_size
= (name3
? (int)strlen(name3
) + 1 : 0);
214 int needs_cr
= is_cr_needed(xe1
, xe2
, m
);
219 if (marker_size
<= 0)
220 marker_size
= DEFAULT_CONFLICT_MARKER_SIZE
;
222 /* Before conflicting part */
223 if (xdl_recs_copy(&copied
, xe1
, i
, m
->i1
- i
, 0, 0,
224 dest
? dest
+ size
: NULL
) < 0)
227 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
230 GITERR_CHECK_ALLOC_ADD5(&size
, size
, marker_size
, 1, needs_cr
, marker1_size
);
232 memset(dest
+ size
, '<', marker_size
);
236 memcpy(dest
+ size
+ 1, name1
, marker1_size
- 1);
237 size
+= marker1_size
;
244 /* Postimage from side #1 */
245 if (xdl_recs_copy(&copied
, xe1
, m
->i1
, m
->chg1
, needs_cr
, 1,
246 dest
? dest
+ size
: NULL
) < 0)
249 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
251 if (style
== XDL_MERGE_DIFF3
) {
252 /* Shared preimage */
254 GITERR_CHECK_ALLOC_ADD5(&size
, size
, marker_size
, 1, needs_cr
, marker3_size
);
256 memset(dest
+ size
, '|', marker_size
);
260 memcpy(dest
+ size
+ 1, name3
, marker3_size
- 1);
261 size
+= marker3_size
;
268 if (xdl_orig_copy(&copied
, xe1
, m
->i0
, m
->chg0
, needs_cr
, 1,
269 dest
? dest
+ size
: NULL
) < 0)
271 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
275 GITERR_CHECK_ALLOC_ADD4(&size
, size
, marker_size
, 1, needs_cr
);
277 memset(dest
+ size
, '=', marker_size
);
284 /* Postimage from side #2 */
286 if (xdl_recs_copy(&copied
, xe2
, m
->i2
, m
->chg2
, needs_cr
, 1,
287 dest
? dest
+ size
: NULL
) < 0)
289 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
292 GITERR_CHECK_ALLOC_ADD5(&size
, size
, marker_size
, 1, needs_cr
, marker2_size
);
294 memset(dest
+ size
, '>', marker_size
);
298 memcpy(dest
+ size
+ 1, name2
, marker2_size
- 1);
299 size
+= marker2_size
;
310 static int xdl_fill_merge_buffer(size_t *out
,
311 xdfenv_t
*xe1
, const char *name1
,
312 xdfenv_t
*xe2
, const char *name2
,
313 const char *ancestor_name
,
315 xdmerge_t
*m
, char *dest
, int style
,
323 for (size
= i
= 0; m
; m
= m
->next
) {
324 if (favor
&& !m
->mode
)
328 if (fill_conflict_hunk(&size
, xe1
, name1
, xe2
, name2
,
330 size
, i
, style
, m
, dest
,
334 else if (m
->mode
& 3) {
335 /* Before conflicting part */
336 if (xdl_recs_copy(&copied
, xe1
, i
, m
->i1
- i
, 0, 0,
337 dest
? dest
+ size
: NULL
) < 0)
339 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
341 /* Postimage from side #1 */
343 int needs_cr
= is_cr_needed(xe1
, xe2
, m
);
345 if (xdl_recs_copy(&copied
, xe1
, m
->i1
, m
->chg1
, needs_cr
, (m
->mode
& 2),
346 dest
? dest
+ size
: NULL
) < 0)
348 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
351 /* Postimage from side #2 */
353 if (xdl_recs_copy(&copied
, xe2
, m
->i2
, m
->chg2
, 0, 0,
354 dest
? dest
+ size
: NULL
) < 0)
356 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
363 if (xdl_recs_copy(&copied
, xe1
, i
, xe1
->xdf2
.nrec
- i
, 0, 0,
364 dest
? dest
+ size
: NULL
) < 0)
366 GITERR_CHECK_ALLOC_ADD(&size
, size
, copied
);
373 * Sometimes, changes are not quite identical, but differ in only a few
374 * lines. Try hard to show only these few lines as conflicting.
376 static int xdl_refine_conflicts(xdfenv_t
*xe1
, xdfenv_t
*xe2
, xdmerge_t
*m
,
377 xpparam_t
const *xpp
)
379 for (; m
; m
= m
->next
) {
382 xdchange_t
*xscr
, *x
;
383 int i1
= m
->i1
, i2
= m
->i2
;
385 /* let's handle just the conflicts */
389 /* no sense refining a conflict when one side is empty */
390 if (m
->chg1
== 0 || m
->chg2
== 0)
394 * This probably does not work outside git, since
395 * we have a very simple mmfile structure.
397 t1
.ptr
= (char *)xe1
->xdf2
.recs
[m
->i1
]->ptr
;
398 t1
.size
= xe1
->xdf2
.recs
[m
->i1
+ m
->chg1
- 1]->ptr
399 + xe1
->xdf2
.recs
[m
->i1
+ m
->chg1
- 1]->size
- t1
.ptr
;
400 t2
.ptr
= (char *)xe2
->xdf2
.recs
[m
->i2
]->ptr
;
401 t2
.size
= xe2
->xdf2
.recs
[m
->i2
+ m
->chg2
- 1]->ptr
402 + xe2
->xdf2
.recs
[m
->i2
+ m
->chg2
- 1]->size
- t2
.ptr
;
403 if (xdl_do_diff(&t1
, &t2
, xpp
, &xe
) < 0)
405 if (xdl_change_compact(&xe
.xdf1
, &xe
.xdf2
, xpp
->flags
) < 0 ||
406 xdl_change_compact(&xe
.xdf2
, &xe
.xdf1
, xpp
->flags
) < 0 ||
407 xdl_build_script(&xe
, &xscr
) < 0) {
412 /* If this happens, the changes are identical. */
418 m
->i1
= xscr
->i1
+ i1
;
419 m
->chg1
= xscr
->chg1
;
420 m
->i2
= xscr
->i2
+ i2
;
421 m
->chg2
= xscr
->chg2
;
423 xdmerge_t
*m2
= xdl_malloc(sizeof(xdmerge_t
));
434 m
->i1
= xscr
->i1
+ i1
;
435 m
->chg1
= xscr
->chg1
;
436 m
->i2
= xscr
->i2
+ i2
;
437 m
->chg2
= xscr
->chg2
;
445 static int line_contains_alnum(const char *ptr
, long size
)
448 if (isalnum((unsigned char)*(ptr
++)))
453 static int lines_contain_alnum(xdfenv_t
*xe
, int i
, int chg
)
455 for (; chg
; chg
--, i
++)
456 if (line_contains_alnum(xe
->xdf2
.recs
[i
]->ptr
,
457 xe
->xdf2
.recs
[i
]->size
))
463 * This function merges m and m->next, marking everything between those hunks
464 * as conflicting, too.
466 static void xdl_merge_two_conflicts(xdmerge_t
*m
)
468 xdmerge_t
*next_m
= m
->next
;
469 m
->chg1
= next_m
->i1
+ next_m
->chg1
- m
->i1
;
470 m
->chg2
= next_m
->i2
+ next_m
->chg2
- m
->i2
;
471 m
->next
= next_m
->next
;
476 * If there are less than 3 non-conflicting lines between conflicts,
477 * it appears simpler -- because it takes up less (or as many) lines --
478 * if the lines are moved into the conflicts.
480 static int xdl_simplify_non_conflicts(xdfenv_t
*xe1
, xdmerge_t
*m
,
481 int simplify_if_no_alnum
)
488 xdmerge_t
*next_m
= m
->next
;
494 begin
= m
->i1
+ m
->chg1
;
497 if (m
->mode
!= 0 || next_m
->mode
!= 0 ||
499 (!simplify_if_no_alnum
||
500 lines_contain_alnum(xe1
, begin
, end
- begin
)))) {
504 xdl_merge_two_conflicts(m
);
510 * level == 0: mark all overlapping changes as conflict
511 * level == 1: mark overlapping changes as conflict only if not identical
512 * level == 2: analyze non-identical changes for minimal conflict set
513 * level == 3: analyze non-identical changes for minimal conflict set, but
514 * treat hunks not containing any letter or number as conflicting
516 * returns < 0 on error, == 0 for no conflicts, else number of conflicts
518 static int xdl_do_merge(xdfenv_t
*xe1
, xdchange_t
*xscr1
,
519 xdfenv_t
*xe2
, xdchange_t
*xscr2
,
520 xmparam_t
const *xmp
, mmbuffer_t
*result
)
522 xdmerge_t
*changes
, *c
;
523 xpparam_t
const *xpp
= &xmp
->xpp
;
524 const char *const ancestor_name
= xmp
->ancestor
;
525 const char *const name1
= xmp
->file1
;
526 const char *const name2
= xmp
->file2
;
527 int i0
, i1
, i2
, chg0
, chg1
, chg2
;
528 int level
= xmp
->level
;
529 int style
= xmp
->style
;
530 int favor
= xmp
->favor
;
532 if (style
== XDL_MERGE_DIFF3
) {
534 * "diff3 -m" output does not make sense for anything
535 * more aggressive than XDL_MERGE_EAGER.
537 if (XDL_MERGE_EAGER
< level
)
538 level
= XDL_MERGE_EAGER
;
543 while (xscr1
&& xscr2
) {
546 if (xscr1
->i1
+ xscr1
->chg1
< xscr2
->i1
) {
549 i2
= xscr2
->i2
- xscr2
->i1
+ xscr1
->i1
;
553 if (xdl_append_merge(&c
, 1,
554 i0
, chg0
, i1
, chg1
, i2
, chg2
)) {
555 xdl_cleanup_merge(changes
);
561 if (xscr2
->i1
+ xscr2
->chg1
< xscr1
->i1
) {
563 i1
= xscr1
->i2
- xscr1
->i1
+ xscr2
->i1
;
568 if (xdl_append_merge(&c
, 2,
569 i0
, chg0
, i1
, chg1
, i2
, chg2
)) {
570 xdl_cleanup_merge(changes
);
576 if (level
== XDL_MERGE_MINIMAL
|| xscr1
->i1
!= xscr2
->i1
||
577 xscr1
->chg1
!= xscr2
->chg1
||
578 xscr1
->chg2
!= xscr2
->chg2
||
579 xdl_merge_cmp_lines(xe1
, xscr1
->i2
,
581 xscr1
->chg2
, xpp
->flags
)) {
583 int off
= xscr1
->i1
- xscr2
->i1
;
584 int ffo
= off
+ xscr1
->chg1
- xscr2
->chg1
;
595 chg0
= xscr1
->i1
+ xscr1
->chg1
- i0
;
596 chg1
= xscr1
->i2
+ xscr1
->chg2
- i1
;
597 chg2
= xscr2
->i2
+ xscr2
->chg2
- i2
;
603 if (xdl_append_merge(&c
, 0,
604 i0
, chg0
, i1
, chg1
, i2
, chg2
)) {
605 xdl_cleanup_merge(changes
);
610 i1
= xscr1
->i1
+ xscr1
->chg1
;
611 i2
= xscr2
->i1
+ xscr2
->chg1
;
623 i2
= xscr1
->i1
+ xe2
->xdf2
.nrec
- xe2
->xdf1
.nrec
;
627 if (xdl_append_merge(&c
, 1,
628 i0
, chg0
, i1
, chg1
, i2
, chg2
)) {
629 xdl_cleanup_merge(changes
);
638 i1
= xscr2
->i1
+ xe1
->xdf2
.nrec
- xe1
->xdf1
.nrec
;
643 if (xdl_append_merge(&c
, 2,
644 i0
, chg0
, i1
, chg1
, i2
, chg2
)) {
645 xdl_cleanup_merge(changes
);
652 /* refine conflicts */
653 if (XDL_MERGE_ZEALOUS
<= level
&&
654 (xdl_refine_conflicts(xe1
, xe2
, changes
, xpp
) < 0 ||
655 xdl_simplify_non_conflicts(xe1
, changes
,
656 XDL_MERGE_ZEALOUS
< level
) < 0)) {
657 xdl_cleanup_merge(changes
);
662 int marker_size
= xmp
->marker_size
;
665 if (xdl_fill_merge_buffer(&size
, xe1
, name1
, xe2
, name2
,
667 favor
, changes
, NULL
, style
,
671 result
->ptr
= xdl_malloc(size
);
673 xdl_cleanup_merge(changes
);
677 if (xdl_fill_merge_buffer(&size
, xe1
, name1
, xe2
, name2
,
678 ancestor_name
, favor
, changes
,
679 result
->ptr
, style
, marker_size
) < 0)
682 return xdl_cleanup_merge(changes
);
685 int xdl_merge(mmfile_t
*orig
, mmfile_t
*mf1
, mmfile_t
*mf2
,
686 xmparam_t
const *xmp
, mmbuffer_t
*result
)
688 xdchange_t
*xscr1
, *xscr2
;
691 xpparam_t
const *xpp
= &xmp
->xpp
;
696 if (xdl_do_diff(orig
, mf1
, xpp
, &xe1
) < 0) {
699 if (xdl_do_diff(orig
, mf2
, xpp
, &xe2
) < 0) {
703 if (xdl_change_compact(&xe1
.xdf1
, &xe1
.xdf2
, xpp
->flags
) < 0 ||
704 xdl_change_compact(&xe1
.xdf2
, &xe1
.xdf1
, xpp
->flags
) < 0 ||
705 xdl_build_script(&xe1
, &xscr1
) < 0) {
709 if (xdl_change_compact(&xe2
.xdf1
, &xe2
.xdf2
, xpp
->flags
) < 0 ||
710 xdl_change_compact(&xe2
.xdf2
, &xe2
.xdf1
, xpp
->flags
) < 0 ||
711 xdl_build_script(&xe2
, &xscr2
) < 0) {
712 xdl_free_script(xscr1
);
719 result
->ptr
= xdl_malloc(mf2
->size
);
720 memcpy(result
->ptr
, mf2
->ptr
, mf2
->size
);
721 result
->size
= mf2
->size
;
723 result
->ptr
= xdl_malloc(mf1
->size
);
724 memcpy(result
->ptr
, mf1
->ptr
, mf1
->size
);
725 result
->size
= mf1
->size
;
727 status
= xdl_do_merge(&xe1
, xscr1
,
731 xdl_free_script(xscr1
);
732 xdl_free_script(xscr2
);