From fab28489f34db091c4f17f379e0c5d5e8024841e Mon Sep 17 00:00:00 2001 From: Neil Brown Date: Sun, 28 Aug 2011 17:59:57 +1000 Subject: [PATCH] Remove merge.c It hasn't been used for a while Signed-off-by: NeilBrown --- Makefile | 4 +- merge.c | 899 ------------------------------------------------------- 2 files changed, 2 insertions(+), 901 deletions(-) delete mode 100644 merge.c diff --git a/Makefile b/Makefile index a53e19c..6945c1e 100644 --- a/Makefile +++ b/Makefile @@ -17,8 +17,8 @@ LDLIBS = -lncurses all: wiggle wiggle.man test wiggle : wiggle.o load.o split.o extract.o diff.o bestmatch.o ReadMe.o \ - merge.o merge2.o vpatch.o -wiggle.o load.o split.o extract.o diff.o bestmatch.o ReadMe.o merge.o \ + merge2.o vpatch.o +wiggle.o load.o split.o extract.o diff.o bestmatch.o ReadMe.o \ merge2.o vpatch.o : wiggle.h test: wiggle dotest diff --git a/merge.c b/merge.c deleted file mode 100644 index 6998d82..0000000 --- a/merge.c +++ /dev/null @@ -1,899 +0,0 @@ -/* - * wiggle - apply rejected patches - * - * Copyright (C) 2003 Neil Brown - * - * - * This program is free software; you can redistribute it and/or modify - * it under the terms of the GNU General Public License as published by - * the Free Software Foundation; either version 2 of the License, or - * (at your option) any later version. - * - * This program is distributed in the hope that it will be useful, - * but WITHOUT ANY WARRANTY; without even the implied warranty of - * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the - * GNU General Public License for more details. - * - * You should have received a copy of the GNU General Public License - * along with this program; if not, write to the Free Software Foundation, Inc., - * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - * - * Author: Neil Brown - * Email: - */ - - -/* - * This file contains routines use to create a merge. - * The core process is to take two coincidence lists, A-B and B-C, - * which identify coincidences and, but ommission, changes, and - * to apply to replace every part of A that matches B with the - * part of C that aligns with that part of B. In the case where - * a B-C difference does not align completely with an A-B coincidence, - * we have a conflict. - * - * Throught the processing of merges we need a concept of a position in the - * overall merge. This is represented by an index into one of the files, and - * and indicator as to which file. - * If the point is in: - * A - then it is an unmatched part of A, before a coincidence. - * B - then it is in a section where A matches B and B matches C. - * C - then it is in an unmatched part of C, but the corresponding part - * of B completely coincides with A. - * With each position we keep indexes into the coincidence lists for - * the containing or next coincidence in each. - * - * - * The first stage of merge processing is to identify conflicts. - * A conflict is identified by a start point and an end point. - * The first approximation for the start point is the end - * of the last A-B coincidence that starts before the B start - * of the B-C difference that causes the conflict. - - * - * We have a concept of a 'point' - * The start and end of the file are each points. - * Also the start and end of any conflict is a point. - * Outside of a conflict, we can move points forwards or backwards - * through the merger. Inside a conflict movement is not well defined. - * Any point is 'forward looking' or 'backward looking'. - * A forward looking point can be moved forward but not backward. - * A backward looking point can be moved backward, not forward. - * - * If a forward looking point is a tri-point, in a double-coincidence, - * then c1/c2 will be set to the furthest forward double coincidence that is before - * or contains the point, thus it well-defines the start of a double coincidence - * or that end of a conflict. - * inversely, a BL point well-defines the end of a DC or start of a conflict. - * - * The start of a conflict is a backward looking point. - * The end of a conflict is a forward looking point. - * - * In normal (Word/line) mode, we move the boundaries of a conflict out - * until they are at end-of-line. - * When moving forward, this is until we cross over a newline word. - * When moving backward, this is until one step before crossing over - * a newline word, so we need to remember our last position. - * - * Away from a conflict, every point can be clearly defined as a - * location either in A or in C. The 'point' is immediately before - * the word at that location. - * At the end of a conflict, this is still well defined as the 'next word' - * is outside a conflict. - * At the start of a conflict this may not be well defined as there may not - * be a clear 'next' word. We choose the point the would be reached by - * the step-forward algorithm so that it is easy to test if at start-of-conflict. - * - * A conflict is always bounded by a double coincidence. i.e. the word before a conflict - * is the same in all 3 texts, and the word after a conflict is the same in all - * 3 texts. To allow for conflicts at start and end of file, we consider the - * start and end of the three texts to each be double co-incidences. - * - * Each double co-incidence has a start and an end. When we find a conflict, it - * is taken to extend from the end of the previous double coincidence to the - * start of the next double co-incidence. - * Between conflicts we can mergers which can be printed simply be advancing the start - * point and printing each word as we go. - * - * The double co-incidence at the start begins forward-looking A=0 or C=0, - * depending on which word is first, and ends at backward-looking A=0. - * The double co-incidence at the end begins at forward-looking - * C=max and ends at backward looking A=max or C=max depending on which - * would be the last word. - * - * Each point is defined by a flag "in_a" which is true if the point is in A, - * and index 'pos' which gives the position in A or C depending on "in_a", and - * an index into each co-incidence list, c1 and c2. - * - * For forward looking points: - * if in_a: - * c1 is the first co-incidence that ends after pos. - or is tail co-incidence. - * c2 is the first co-incidence that ends at or after c1.b - * if in_c: - * c2 is the first co-incidence that ends after pos - or is tail co-incidence. - * c1 is the first co-incidence that ends at or after c2.a - * - * For a backward looking point: - * if in_a: - * c1 is the last co-incidence that starts before pos, or -1 - * c2 is the last co-incidence that starts at or before c1.b - * if in_c: - * c2 is the last co-incidence that starts before pos, or -1 - * c1 is the last co-incidence that .. lines up properly. - * - * To advance a point we increment pos, then - * if in_a and at start of c1 - * slide up to c and if at end of c2, advance c2, then c1 and repeat - * if in_c and within c2 and corresponding a at end of c1, and c1->len != 0 - * slide down to a, increment c1 and advance c2, then repeat. - * - * To retreat a backward facing point - * if in_a and at end of c1 and c1!=-1, - * slide up to c and if at start of c2, retreat c2, thenc 1, and repeat - * if in_c and within c2 and corresponding a at start of c1 - * slide down to a, decrement c1 and retreat c2, then repeat. - * Then decrement pos. - * - * We never actually compare points for ordering. We should 'know' the likely order - * and only compare equal or not. This can be tested independant of direction, - * and done by simply comparing in_a and pos. - */ - - -/* Each point involves a location in each of A, B, and C. - * There is a conflict for each change in B-C where the B section - * is not wholey contained in an A-B co-incidence. - * The start point of a conflict is determined as: - * C is the end of the C side of the previous B-C coincidence (or - * start of file - * B is the end of the B side of the matching A-B coincidence if - * the point is in an A-B coincidence, or the end of the previous - * A-B coincidence of not. - * As B moves backwards searching for an A-B coincidence, if it enters - * a B-C coincidence, C is moved backwards too. - * A is the matching point to B in the A-B coincidence that B is in. - * - * The end point of a conflict is determined in a similar way, - * except that B is in a coincidence that is at, or *follows* the - * end of the next B-C coincidence. - * - * Once these coincidences have been enumerated, the endpoints are - * optionally moved to be at start-of-line. The start point is moved - * backwards and the endpoint forwards. The endofline must be in an - * A-B coincidence and may be in C if there is also a B-C coincidence. - * - * The next step is to merge adjacent conflicts where the B point - * from one overlaps the next. - * - */ -#include -#include -#include "wiggle.h" - -/* A point is somewhere either in_a or not in_a (in which case, in C). - * if in_a, c1 points to the next a-b coincidence strictly after pos - * c2 points to the b-c coincidence that contains (possibly as end point) or follows c1.b - * if !in_a, c2 points to the b-c coincidence that contains (possibly as endpoint) or follows pos - * c1 points to the a-b coincidence that contains c2.b - * - * A point is not well defined inside a conflict, Though it is at the - * 'start' and 'end' of a conflict. - * - * At the start of the file c1 and c2 will be the firsts match in A-B and B-C - * If [c1]->a is 0, then !in_a and pos is [c2]->b+x where x is - * chosen such that [c1]->b == [c2]->a+x and x < [c2]->len. If such choice - * is not possible, there is a conflict at the start of the file and so we choose - * a point as if [c1]->a were not 0. - * - * If [c1]->a is not 0, then in_a and pos == 0. - * - * To find the start of file, we set in_a and pos==-1, and advance one step. - * - * At the end of the file, c1 will be the EOF match in A-B, c2 will be the - * EOF match in B-C, !in_a and pos == [c2]->b - */ -struct point { - int pos, in_a; - int c1, c2; -}; - - -static int tripoint(struct point *here, - struct csl *c1, struct csl *c2, - int *a, int *b, int *c) -{ - /* find a, b, and c for 'here'. - * If any are not well defined, return 0. - */ - c1 += here->c1; - c2 += here->c2; - - if (here->in_a) { - *a = here->pos; - - if (here->c1 < 0) { - if (*a) - return 0; - *b = 0; - } else if (c1->a <= *a && c1->a+c1->len >= *a) - *b = c1->b + (*a - c1->a); - else - return 0; - - if (here->c2 < 0) { - if (*b) - return 0; - *c = 0; - } else if (c2->a <= *b && c2->a + c2->len >= *b) - *c = c2->b + *b - c2->a; - else - return 0; - } else { - *c = here->pos; - - if (here->c2 < 0) { - if (*c) - return 0; - *b = 0; - } else if (c2->b <= *c && c2->b + c2->len >= *c) - *b = c2->a + *c - c2->b; - else - return 0; - - - if (here->c1 < 0) { - if (*b) - return 0; - *a = 0; - } else if (c1->b <= *b && c1->b + c1->len >= *b) - *a = c1->a + *b - c1->b; - else - return 0; - } - return 1; -} - -static int retreat(struct csl *c1, struct csl *c2, struct point *p) -{ - int a, b, c; - int slid = 0; - - retry: - if (p->in_a) { - /* retreat c1 to first coincidence containing or after pos */ - a = p->pos; - while ((p->c1 == 0 && a == 0) || - (p->c1 > 0 && c1[p->c1-1].a + c1[p->c1-1].len >= a)) { - if (!slid) - if (a >= c1[p->c1].a) - break; - p->c1--; - } - - /* if we aren't in a co-incidence, just return */ - if (p->c1 >= 0 && - c1[p->c1].a > a) - return 1; - - /* retreat c2 to first coincidence containing or after pos->b */ - if (p->c1 == -1) - b = 0; - else - b = c1[p->c1].b + a - c1[p->c1].a; - while ((p->c2 == 0 && b == 0) || - (p->c1 > 0 && c2[p->c2-1].a + c2[p->c2-1].len >= b)) { - if (!slid) - if (b >= c2[p->c2].a) - break; - p->c2--; - } - - /* check if this is a conflict */ - if ((p->c2 >= 0 && c2[p->c2].a > b)) - return 2; - - if (p->c2 == -1) - c = 0; - else - c = c2[p->c2].b + b - c2[p->c2].a; - - /* ok, this is the furthest backward double coincidence - * if we are not at the start of the A-B coincidence, - * slip up to C - */ - if (p->c1 >= 0 && a > c1[p->c1].a) { - p->in_a = 0; - p->pos = c; - slid = 1; - goto retry; - } - } else { - /* retreat c2 to first coincidence containing or after pos */ - c = p->pos; - while ((p->c2 == 0 && c == 0) || - (p->c2 > 0 && c2[p->c2-1].b + c2[p->c2-1].len >= c)) { - if (!slid) - if (c >= c2[p->c2].b) - break; - p->c2--; - } - - /* if we aren't in a coincidence, return */ - if (p->c2 >= 0 && - c2[p->c2].b > c) - return 1; - - /* retreat c1 to first coincidence containing or afer pos->b */ - if (p->c2 == -1) - b = 0; - else - b = c2[p->c2].a + c - c2[p->c2].b; - while ((p->c1 == 0 && b == 0) || - (p->c1 > 0 && c1[p->c1-1].b + c1[p->c1-1].len >= b)) { - if (!slid) - if (b >= c1[p->c1].b) - break; - p->c1--; - } - - /* check if this is a conflict */ - if ((p->c1 >= 0 && c1[p->c1].b > b)) - return 2; - - if (p->c1 == -1) - a = 0; - else - a = c1[p->c1].a + b - c1[p->c1].b; - - /* ok, this is the furthest backward double coincidence - * if we are at the start of the A-B coincidence, slide down to A - */ - if (p->c1 == -1 || - a == c1[p->c1].a) { - p->in_a = 1; - p->pos = a; - slid = 1; - goto retry; - } - } - if (p->pos == 0) - return 0; /* StartOfFile */ - - if (!slid) { - slid = 1; - goto retry; - } - - return 1; -} - -static int advance(struct csl *c1, struct csl *c2, struct point *p) -{ - int a, b, c; - int slid = 0; - /* make next char at point is the 'right' one, either in a or c. - * This might involve move p->c1 and p->c2 forward - * and changing pos/in_a to an 'equivalent' point - */ -/* - if (!p->in_a && c2[p->c2].b == p->pos && c2[p->c2].len == 0) - return 0; / * at end of file * / -*/ - retry: - if (p->in_a) { - /* advance c1 to last coincidence containing or before pos */ - a = p->pos; - while ((p->c1 == -1 || c1[p->c1].len) && - c1[p->c1+1].a <= a) { - if (!slid) - if ((p->c1 == -1 && a == 0) || - (p->c1 >= 0 && a <= c1[p->c1].a+c1[p->c1].len)) - break; - p->c1++; - } - - /* if we aren't in a co-incidence, just return */ - if (p->c1 == -1 || c1[p->c1].a+c1[p->c1].len < a) - return 1; - - /* advance c2 to last coincidence containing or before pos->b */ - b = c1[p->c1].b + a - c1[p->c1].a; - while ((p->c2 == -1 || c2[p->c2].len) && - c2[p->c2+1].a <= b) { - if (!slid) - if ((p->c2 == -1 && b == 0) || - (p->c2 >= 0 && b <= c2[p->c2].a+c2[p->c2].len)) - break; - p->c2++; - } - - /* check if this is a conflict */ - if ((p->c2 == -1 && b > 0) || - (p->c2 >= 0 && c2[p->c2].a + c2[p->c2].len < b)) - return 2; - - if (p->c2 == -1) - c = 0; - else - c = c2[p->c2].b + b - c2[p->c2].a; - - /* Ok, this is the furthest forward double coincidence - * If we are at eof, or the next char is in the coincidence - * slip up to c - */ - if (c1[p->c1].len == 0 || - a < c1[p->c1].a + c1[p->c1].len) { - p->in_a = 0; - /* - * if we've slid, make sure not to skip over - * the stuff in c2. - */ - if (slid && p->c2 != -1 && c2[p->c2].a == b && - c2[p->c2].b > c2[p->c2].a) { - c -= c2[p->c2].b - c2[p->c2].a; - } - - p->pos = c; - slid = 1; - goto retry; - } - } else { - /* advance c2 to last coincidence containing or before pos */ - c = p->pos; - while ((p->c2 == -1 || c2[p->c2].len) && - c2[p->c2+1].b <= c) { - if (!slid) - if ((p->c2 == -1 && c == 0) || - (p->c2 >= 0 && c <= c2[p->c2].b+c2[p->c2].len)) - break; - p->c2++; - } - - /* if we aren't in a co-incidence then just return */ - if (p->c2 == -1 || c2[p->c2].b+c2[p->c2].len < c) - return 1; - - /* advance c1 to last coincidence containing or before pos->b */ - b = c2[p->c2].a + c - c2[p->c2].b; - while ((p->c1 == -1 || c1[p->c1].len) && - c1[p->c1+1].b <= b) { - if (!slid) - if ((p->c1 == -1 && b == 0) || - (p->c1 >= 0 && b <= c1[p->c1].b+c1[p->c1].len)) - break; - p->c1++; - } - - /* check if this is a conflict */ - if (p->c1 == -1 || c1[p->c1].b + c1[p->c1].len < b) - return 2; - - a = c1[p->c1].a + b - c1[p->c1].b; - - /* ok, this is the furthest forward double coincidence - * If it is the end of an A-B coincidence but not EOF, - * slide down to A - */ - if (a == c1[p->c1].a + c1[p->c1].len && - c1[p->c1].len) { - p->in_a = 1; - p->pos = a; - slid = 1; - goto retry; - } - } - if (!p->in_a && c2[p->c2].b == p->pos && c2[p->c2].len == 0) - return 0; /* at end of file */ - if (!slid) { - slid = 1; - goto retry; - } - return 1; -} - -static int point_crossed(struct point first, struct point second, - struct csl *cs1, struct csl *cs2) -{ - int a1, b1, c1; - int a2, b2, c2; - - if (tripoint(&first, cs1, cs2, &a1, &b1, &c1) && - tripoint(&second, cs1, cs2, &a2, &b2, &c2)) - return a1 >= a2 && b1 >= b2 && c1 >= c2; - return 0; -/* - return first.in_a == second.in_a && - first.pos == second.pos; -*/ -} - - -static void print_merger(FILE *out, struct file *a, struct file *c, - struct csl *cs1, struct csl *cs2, - struct point start, struct point end) -{ - while (!point_crossed(start, end, cs1, cs2)) { -#if 0 - printf("%c %d (%d,%d)\n", start.in_a ? 'A' : 'C', start.pos, - start.c1, start.c2); -#endif - if (start.in_a) - printword(out, a->list[start.pos]); - else - printword(out, c->list[start.pos]); - fflush(out); /* DEBUG */ - - start.pos++; - if (point_crossed(start, end, cs1, cs2)) - break; - advance(cs1, cs2, &start); - - } -} - -static inline int at_sol(struct file *f, int i) -{ - return i == 0 || i == f->elcnt || - ends_line(f->list[i-1]); -} - -static void print_range(FILE *out, struct file *f, int start, int end) -{ - for (; start < end ; start++) - printword(out, f->list[start]); -} - -static int print_conflict(FILE *out, struct file *a, struct file *b, struct file *c, - struct csl *c1, struct csl *c2, - struct point start, struct point end, - int words) -{ - int astart, bstart, cstart; - int aend, bend, cend; - int bi; - -#if 0 - if (point_same(start, end)) - return 0; /* no conflict here !! */ -#endif - if (!tripoint(&start, c1, c2, &astart, &bstart, &cstart)) - abort(); - if (!tripoint(&end, c1, c2, &aend, &bend, &cend)) - abort(); - - - /* Now contract the conflict if possible, but insist on - * an end-of-line boundary unless 'words'. - */ - /* first contract leading removed text. - * so <<<--- X 1 ||| X 2 === 3 --->>> becomes <<<--- 1 ||| 2 === 3 --->>> - */ - bi = bstart; - while (bi < bend && start.c1 >= 0 && bi >= c1[start.c1].b && bi < c1[start.c1].b + c1[start.c1].len) { - bi++; - if (words || at_sol(b, bi)) { - astart += bi-bstart; - bstart = bi; - } - } - /* and contract trailing removed text */ - bi = bend; - while (bi > bstart && bi > c1[end.c1].b) { - bi--; - if (words || at_sol(b, bi)) { - aend -= bend-bi; - bend = bi; - } - } - - /* now contract leading unmatched text so - * <<<--- 1 ||| X 2 === X 3 --->>> becomes <<<--- 1 ||| 2 === 3 --->>> - */ - bi = bstart; - while (bi < bend && start.c2 >= 0 && bi >= c2[start.c2].a && bi < c2[start.c2].a + c2[start.c2].len) { - bi++; - if (words || at_sol(b, bi)) { - cstart += bi-bstart; - bstart = bi; - } - } - /* and trailing unmatched */ - bi = bend; - while (bi > bstart && bi > c2[end.c2].a) { - bi--; - if (words || at_sol(b, bi)) { - cend -= bend-bi; - bend = bi; - } - } - if (astart >= aend && bstart >= bend && cstart >= cend) - return 0; - - fputs(words ? "<<<---" : "<<<<<<<\n", out); - print_range(out, a, astart, aend); - fputs(words ? "|||" : "|||||||\n", out); - print_range(out, b, bstart, bend); - fputs(words ? "===" : "=======\n", out); - print_range(out, c, cstart, cend); - fputs(words ? "--->>>" : ">>>>>>>\n", out); - return 1; -} - -static int end_of_file(struct point p, struct csl *c1, struct csl *c2) -{ - return advance(c1, c2, &p) == 0; -} - -static int next_conflict(struct point here, - struct csl *start_c1, struct csl *start_c2, - struct point *start, struct point *end) -{ - /* We want to find the start and end of the 'next' conflict. - * There may not be another conflict, in which case set start and - * end to the end of the files. - * The start and end of a conflict must be the end and start of - * regions where A matches B and B matches C - except for - * The start which might be the start of the file. - * 'here' is a potentially valid starting point. Any other starting - * point must be the end of a double coincidence. - * - * So we walk c1 and c2 looking for double coincidences and conflicts. - * When we find a conflict, we remember the fact. - * When we find a double coincidence we: - * Set 'end' to the start of the DC. - * If conflict-found - return. - * Set 'start' to the end of the DC. - * If the DC was EOF, start will == end == EOF, and we return. - * - * A double coincidence is easily detected by just looking at a single - * entry in c1 and c2. If - * c1->b+c1->len > c2->a && c2->a+c2->len > c1->b - * || c1->len == c2->len == 0 - * then we have a double coincidence. - * - * A conflict is detected when stepping forward. - * If we step c2 forward and the new coincidence is beyond or at the - * end of c1, or we step forward c1 and it's start is beyond or at the end of c2, - * then that is a conflict. - * Also, we can detect a conflict at start-of-file (here.in_a, here.pos==0) if - * c2 doesn't start at 0. - * - * 'here' is significant only for its c1/c2 values. They will contain a - * double coincidence, though it might be start-of-file. - * start must be set to a backward-looking point at the end of a double-coincidence - * and end to a forward-looking point and the start of a double-coincidence - */ - - - int conflict_found = 0; - struct csl *c1 = start_c1; - struct csl *c2 = start_c2; - - - c1 += here.c1; - c2 += here.c2; - - *start = here; - - while (1) { - /* Step one of c1 or c2 forward - * depending on which ends earlier. - * Watch to see if we are stepping over a conflict. - */ - if (c2 < start_c2) { - /* start-of-file. - * Move both c1 and c2 forward. - * - * We have a conflict iff new c1->b > 0 and c2->a > 0 - * or c1->b >0 && c2->b > 0 - */ - c1++; c2++; - if (c1->b > 0 && - (c2->a > 0 || c2->b > 0)) - conflict_found = 1; - if (c2->a+c2->len < c1->b) - conflict_found = 1; - } else if (c1->b+c1->len == c2->a+c2->len) { - /* both coincidences end at same place. There is - * a conflict if there is a gap in c1->b or - * c2->a has no gap but c2->b does (implying insertion - * at undefined location - */ - if (c1->len && c2->len) { - if (c1[1].b > c1->b + c1->len || - (c2[1].a == c2->a + c2->len && - c2[1].b > c2->b + c2->len)) - conflict_found = 1; - } - if (c1->len) - c1++; - if (c2->len) - c2++; - } else if (c2->len == 0 || - (c1->len && c1->b+c1->len < c2->a+c2->len)) { - /* c1 ends earlier. If the new start of c1 is - * beyond the current end of c2, we have a conflict - */ - c1++; - if (c1->b > c2->a+c2->len) - conflict_found = 1; - } else { - /* c2 ends earlier. If the new start of c2 is - * beyond the end of c1, we have a conflict. - * Also if the new start of c2 is at the end of c1, - * and the old end of c2 is also at end of c1, - * then have a conflict, as long as there was actually - * something inserted there... - */ - c2++; - if (c2->a > c1->b+c1->len) - conflict_found = 1; - } - if ((c1->len == 0 && c2->len == 0) || - (c1->b+c1->len >= c2->a && c2->a+c2->len >= c1->b) - ) { - /* double coincidence ! - * It starts at max of c1->b and c2->a, in c - * and ends at min of c1->b+len (in a), c2->a+len (in c) - */ - end->c1 = c1-start_c1; - end->c2 = c2-start_c2; - - if (conflict_found) { - /* end->c1/c2 holds the end of the conflict, - * and start->c1/c2 holds the start - * We need to set in_a and pos for each - * so that start is backward-looking and the end - * of a double-coincidence, and end is forward-looking - * at the start of a double-coincidence. - */ - - c1 = start_c1; - c2 = start_c2; - - if (start->c1 == -1) { - start->in_a = 1; - start->pos = 0; - } else if (c1[start->c1].b+c1[start->c1].len <= - c2[start->c2].a+c2[start->c2].len) { - start->in_a = 1; - start->pos = c1[start->c1].a+c1[start->c1].len; - } else { - start->in_a = 0; - start->pos = c2[start->c2].b+c2[start->c2].len; - } - retreat(c1, c2, start); - - if (c1[end->c1].b <= c2[end->c2].a) { - end->in_a = 0; - end->pos = c2[end->c2].b; - } else { - end->in_a = 0; - end->pos = c2[end->c2].b + - c1[end->c1].b - c2[end->c2].a; - } - advance(c1, c2, end); - return 1; - } - start->c1 = c1-start_c1; - start->c2 = c2-start_c2; - - if (c1->len == 0 && c2->len == 0) { - /* eof and no conflict found. - * set start and end to eof - */ - start->in_a = end->in_a = 0; - start->pos = end->pos = c2->b; - return 0; - } - } - } -} - -static int already_applied(struct csl *cs1, struct csl *cs2, - struct point start, struct point end, - struct file *a, struct file *b, struct file *c) -{ - /* check if this conflict reflects and already-applied change - * i.e. the section in a matches the section in b - */ - int a1, b1, c1; - int a2, b2, c2; - - if (!tripoint(&start, cs1, cs2, &a1, &b1, &c1)) - abort(); - if (!tripoint(&end, cs1, cs2, &a2, &b2, &c2)) - abort(); - if (a1 == a2 && b1 == b2) - return 0; - if ((a2-a1) != (c2-c1)) - return 0; - - while (a1 < a2) { - if (!match(&a->list[a1], &c->list[c1])) - return 0; - a1++; - c1++; - } - return 1; -} - -static int Startofline(struct point p, struct csl *cs1, struct csl *cs2, - struct file *a, struct file *b, struct file *c) -{ - int a1, b1, c1; - return - tripoint(&p, cs1, cs2, &a1, &b1, &c1) && - at_sol(a, a1) && at_sol(b, b1) && at_sol(c, c1); - -} - -struct ci print_merge(FILE *out, struct file *a, struct file *b, struct file *c, - struct csl *c1, struct csl *c2, - int words) -{ - struct point start_last, end_last, start_next, end_next; - - struct ci rv; - rv.ignored = rv.conflicts = 0; - -#if 0 - { int i; - for (i = 0; c1[i].len; i++) - printf("%2d c1 %d:%d %d\n", i, c1[i].a, c1[i].b, c1[i].len); - printf("%2d c1 %d:%d END\n", i, c1[i].a, c1[i].b); - for (i = 0; c2[i].len; i++) - printf("%2d c2 %d:%d %d\n", i, c2[i].a, c2[i].b, c2[i].len); - printf("%2d c2 %d:%d END\n", i, c2[i].a, c2[i].b); - } -#endif - /* end_last is a forward looking point */ - end_last.pos = 0; - end_last.in_a = 1; - end_last.c1 = end_last.c2 = -1; - advance(c1, c2, &end_last); - - /* start_last is a backward looking point */ - start_last.pos = 0; - start_last.in_a = 1; - start_last.c1 = start_last.c2 = 0; - retreat(c1, c2, &start_last); - - while (!end_of_file(end_last, c1, c2)) { - next_conflict(end_last, c1, c2, &start_next, &end_next); - while (already_applied(c1, c2, start_next, end_next, a, b, c)) { - rv.ignored++; - next_conflict(end_next, c1, c2, &start_next, &end_next); - } -#if 0 - printf("start %d %d (%d,%d) end %d %d (%d,%d)\n", - start_next.in_a, start_next.pos, start_next.c1, start_next.c2, - end_next.in_a, end_next.pos, end_next.c1, end_next.c2); -#endif - while (!point_crossed(end_last, start_next, c1, c2) && - !(words || Startofline(end_last, c1, c2, a, b, c))) { - end_last.pos++; - advance(c1, c2, &end_last); - } - - while (!point_crossed(end_last, start_next, c1, c2) && - !(words || Startofline(start_next, c1, c2, a, b, c))) { - start_next.pos--; - retreat(c1, c2, &start_next); - } - - if (point_crossed(end_last, start_next, c1, c2)) { - end_last = end_next; - continue; - } - if (print_conflict(out, a, b, c, c1, c2, start_last, end_last, words)) - rv.conflicts++; - - print_merger(out, a, c, c1, c2, end_last, start_next); - start_last = start_next; - end_last = end_next; - } - if (print_conflict(out, a, b, c, c1, c2, start_last, end_last, words)) - rv.conflicts++; - return rv; -} -- 2.39.5