merge2.c

   1 /*
   2  * wiggle - apply rejected patches
   3  *
   4  * Copyright (C) 2005 Neil Brown <neilb@cse.unsw.edu.au>
   5  *
   6  *
   7  *    This program is free software; you can redistribute it and/or modify
   8  *    it under the terms of the GNU General Public License as published by
   9  *    the Free Software Foundation; either version 2 of the License, or
  10  *    (at your option) any later version.
  11  *
  12  *    This program is distributed in the hope that it will be useful,
  13  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  *    GNU General Public License for more details.
  16  *
  17  *    You should have received a copy of the GNU General Public License
  18  *    along with this program; if not, write to the Free Software
  19  *    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21  *    Author: Neil Brown
  22  *    Email: <neilb@cse.unsw.edu.au>
  23  *    Paper: Neil Brown
  24  *           School of Computer Science and Engineering
  25  *           The University of New South Wales
  26  *           Sydney, 2052
  27  *           Australia
  28  */
  29
  30 #include "wiggle.h"
  31 #include <stdlib.h>
  32 #include <malloc.h>
  33
  34 /*
  35  * Second attempt at merging....
  36  *
  37  * We want to create a mergelist which identifies 'orig' and 'after'
  38  * sections (from a and c) and conflicts (which are ranges of a,b,c which
  39  * all don't match).
  40  * It is also helpful to differentiate 'orig' sections that aren't
  41  * matched in 'b' with orig sections that are.
  42  * To help with highlighting, it will be useful to know where
  43  * the conflicts match the csl lists.
  44  *
  45  * This can all be achieved with a list of (a,b,c,c1,c1) 5-tuples.
  46  * If two consecutive differ in more than one of a,b,c, it is a
  47  * conflict.
  48  * If only 'a' differ, it is un-matched original.
  49  * If only 'b' differ, it is matched, unchanged original
  50  * If only 'c' differ, it is 1
  51  */
  52
  53 static inline int min(int a, int b)
  54 {
  55         return a<b?a:b;
  56 }
  57 static inline void assert(int a)
  58 {
  59         if (!a) abort();
  60 }
  61
  62 int check_alreadyapplied(struct file af, struct file cf,
  63                           struct merge *m)
  64 {
  65         int i;
  66         if (m->al != m->cl)
  67                 return 0;
  68         for (i=0; i<m->al; i++) {
  69                 if (af.list[m->a+i].len != cf.list[m->c+i].len)
  70                         return 0;
  71                 if (strncmp(af.list[m->a+i].start,
  72                             cf.list[m->c+i].start,
  73                             af.list[m->a+i].len)!= 0)
  74                         return 0;
  75         }
  76 #if 0
  77         printf("already applied %d,%d,%d - %d,%d,%d\n",
  78                m->a,m->b,m->c,m->al,m->bl,m->cl);
  79         printf(" %.10s - %.10s\n", af.list[m->a].start,
  80                cf.list[m->c].start);
  81 #endif
  82         m->type = AlreadyApplied;
  83         return 1;
  84 }
  85
  86 inline int isolate_conflicts(struct file af, struct file bf, struct file cf,
  87                               struct csl *csl1, struct csl *csl2, int words,
  88                               struct merge *m)
  89 {
  90         /* A conflict indicates that something is definitely wrong
  91          * and so we need to be a bit suspicious of nearby apparent matches.
  92          * To display a conflict effectively we expands it's effect to
  93          * include any Extraneous, Unmatched or Changed text.
  94          * Also, unless 'words', we need to include any partial lines
  95          * in the Unchanged text that forms the border of a conflict.
  96          *
  97          */
  98         int i,j,k;
  99         int cnt = 0;
 100
 101         for (i=0; m[i].type != End; i++)
 102                 if (m[i].type == Conflict) {
 103                         /* We have a conflict here.
 104                          * First search backwards for an Unchanged marking
 105                          * things as in_conflict.  Then find the
 106                          * cut-point in the Unchanged.  If there isn't one,
 107                          * keep looking.
 108                          *
 109                          * Then search forward doing the same thing.
 110                          */
 111                         cnt++;
 112                         m[i].in_conflict = 1;
 113                         j = i;
 114                         while (--j >= 0) {
 115                                 if (!m[j].in_conflict) {
 116                                         m[j].in_conflict = 1;
 117                                         m[j].lo = 0;
 118                                 }
 119                                 if (m[j].type == Unchanged || m[j].type == Changed) {
 120                                         if (words) {
 121                                                 m[j].hi = m[j].al;
 122                                                 break;
 123                                         }
 124                                         /* need to find the last line-break, which
 125                                          * might be after the last newline, if there
 126                                          * is one, or might be at the start
 127                                          */
 128                                         for (k=m[j].al; k>0; k--)
 129                                                 if (ends_line(af.list[m[j].a+k-1]))
 130                                                         break;
 131                                         if (k>0) {
 132                                                 m[j].hi = k;
 133                                                 break;
 134                                         }
 135                                         if ((m[j].a == 0 || ends_line(af.list[m[j].a-1])) &&
 136                                             (m[j].b == 0 || ends_line(bf.list[m[j].b-1])) &&
 137                                             (m[j].c == 0 || ends_line(cf.list[m[j].c-1]))){
 138                                                 m[j].hi = 0;
 139                                                 break;
 140                                         }
 141                                         /* no start-of-line found... */
 142                                         m[j].hi = -1;
 143                                 }
 144                         }
 145                         /* now the forward search */
 146                         for (j=i+1; m[j].type != End; j++) {
 147                                 m[j].in_conflict = 1;
 148                                 if (m[j].type == Unchanged || m[j].type == Changed) {
 149                                         m[j].hi = m[j].al;
 150                                         if (words) {
 151                                                 m[j].lo = 0;
 152                                                 break;
 153                                         }
 154                                         /* need to find a line-break, which might be at
 155                                          * the very beginning, or might be after the
 156                                          * first newline - if there is one
 157                                          */
 158                                         if ((m[j].a == 0 || ends_line(af.list[m[j].a-1])) &&
 159                                             (m[j].b == 0 || ends_line(bf.list[m[j].b-1])) &&
 160                                             (m[j].c == 0 || ends_line(cf.list[m[j].c-1]))){
 161                                                 m[j].lo = 0;
 162                                                 break;
 163                                         }
 164                                         for (k=0; k<m[j].al; k++)
 165                                                 if (ends_line(af.list[m[j].a+k]))
 166                                                         break;
 167                                         if (k<m[j].al) {
 168                                                 m[j].lo = k+1;
 169                                                 break;
 170                                         }
 171                                         /* no start-of-line found */
 172                                         m[j].lo = m[j].al+1;
 173                                 }
 174                         }
 175                         i = j;
 176                 }
 177         return cnt;
 178 }
 179
 180
 181 struct ci make_merger(struct file af, struct file bf, struct file cf,
 182                       struct csl *csl1, struct csl *csl2, int words)
 183 {
 184         /* find the wiggles and conflicts between csl1 and csl2
 185          */
 186         struct ci rv;
 187         int i,l;
 188         int a,b,c,c1,c2;
 189         int wiggle_found = 0;
 190
 191         rv.conflicts = rv.wiggles = rv.ignored = 0;
 192
 193         for (i=0; csl1[i].len; i++);
 194         l = i;
 195         for (i=0; csl2[i].len; i++);
 196         l += i;
 197         /* maybe a bit of slack at each end */
 198         l = l* 4 + 10;
 199
 200         rv.merger = malloc(sizeof(struct merge)*l);
 201         if (!rv.merger)
 202                 return rv;
 203
 204         a=b=c=c1=c2 = 0;
 205         i = 0;
 206         while (1) {
 207                 int match1, match2;
 208                 match1 = (a>=csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
 209                 match2 = (b>=csl2[c2].a && c >= csl2[c2].b);
 210
 211                 rv.merger[i].a = a;
 212                 rv.merger[i].b = b;
 213                 rv.merger[i].c = c;
 214                 rv.merger[i].c1 = c1;
 215                 rv.merger[i].c2 = c2;
 216                 rv.merger[i].in_conflict = 0;
 217
 218                 if (!match1 && match2) {
 219                         if (a < csl1[c1].a) {
 220                                 /* some unmatched text */
 221                                 rv.merger[i].type = Unmatched;
 222                                 rv.merger[i].al = csl1[c1].a - a;
 223                                 rv.merger[i].bl = 0;
 224                                 rv.merger[i].cl = 0;
 225                                 wiggle_found ++;
 226                         } else {
 227                                 int newb;
 228                                 int j;
 229                                 assert(b<csl1[c1].b);
 230                                 /* some Extraneous text */
 231                                 /* length is min of unmatched on left
 232                                  * and matched on right
 233                                  */
 234                                 rv.merger[i].type = Extraneous;
 235                                 rv.merger[i].al = 0;
 236                                 rv.merger[i].cl =
 237                                         rv.merger[i].bl =
 238                                         min(csl1[c1].b - b,
 239                                             csl2[c2].len - (b-csl2[c2].a));
 240                                 newb = b+rv.merger[i].bl;
 241                                 for (j=b; j<newb; j++) {
 242                                         if (bf.list[j].start[0] == '\0') {
 243                                                 if (wiggle_found > 1)
 244                                                         rv.wiggles++;
 245                                                 wiggle_found = 0;
 246                                         } else
 247                                                 wiggle_found ++;
 248                                 }
 249                         }
 250                 } else if (match1 && !match2) {
 251                         /* some changed text
 252                          * if 'c' is currently at a suitable cut-point, then
 253                          * we can look for a triple-cut-point for start.
 254                          * Also, if csl2[c2].b isn't in a conflict, and is
 255                          * a suitable cut-point, then we could make a
 256                          * triple-cut-point for end of a conflict.
 257                          */
 258
 259                         rv.merger[i].type = Changed;
 260                         rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
 261                         rv.merger[i].al = rv.merger[i].bl;
 262                         rv.merger[i].cl = csl2[c2].b - c;
 263                 } else if (match1 && match2) {
 264                         /* Some unchanged text
 265                          */
 266                         rv.merger[i].type = Unchanged;
 267                         rv.merger[i].bl =
 268                                 min(csl1[c1].len - (b-csl1[c1].b),
 269                                     csl2[c2].len - (b-csl2[c2].a));
 270                         rv.merger[i].al = rv.merger[i].cl =
 271                                 rv.merger[i].bl;
 272                 } else {
 273                         /* must be a conflict.
 274                          * Move a and c to next match, and b to closest of the two
 275                          */
 276                         rv.merger[i].type = Conflict;
 277                         rv.merger[i].al = csl1[c1].a - a;
 278                         rv.merger[i].cl = csl2[c2].b - c;
 279                         rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
 280                         if (check_alreadyapplied(af,cf,&rv.merger[i]))
 281                                 rv.ignored ++;
 282                 }
 283                 a += rv.merger[i].al;
 284                 b += rv.merger[i].bl;
 285                 c += rv.merger[i].cl;
 286                 i++;
 287
 288                 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len) c1++;
 289                 assert(csl1[c1].b + csl1[c1].len >= b);
 290                 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len) c2++;
 291                 assert(csl2[c2].a + csl2[c2].len >= b);
 292                 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
 293                     a == csl1[c1].a && b == csl1[c1].b &&
 294                     b == csl2[c2].a && c == csl2[c2].b)
 295                         break;
 296         }
 297         rv.merger[i].type = End;
 298         rv.merger[i].in_conflict = 0;
 299         rv.conflicts = isolate_conflicts(af,bf,cf,csl1,csl2,words,rv.merger);
 300         if (wiggle_found)
 301                 rv.wiggles++;
 302         return rv;
 303 }
 304
 305 void printrange(FILE *out, struct file *f, int start, int len)
 306 {
 307         while (len> 0) {
 308                 printword(out, f->list[start]);
 309                 start++;
 310                 len--;
 311         }
 312 }
 313
 314 struct ci print_merge2(FILE *out, struct file *a, struct file *b, struct file *c,
 315                  struct csl *c1, struct csl *c2,
 316                  int words)
 317 {
 318         struct ci rv = make_merger(*a, *b, *c, c1, c2, words);
 319         struct merge *m;
 320
 321         for (m=rv.merger; m->type != End ; m++) {
 322                 struct merge *cm;
 323 #if 1
 324                 static int v= -1;
 325                 if (v == -1) {
 326                         if (getenv("WiggleVerbose"))
 327                                 v = 1;
 328                         else
 329                                 v = 0;
 330                 }
 331                 if (v)
 332                 printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
 333                        m->type==Unmatched?"Unmatched":
 334                        m->type==Unchanged?"Unchanged":
 335                        m->type==Extraneous?"Extraneous":
 336                        m->type==Changed?"Changed":
 337                        m->type==AlreadyApplied?"AlreadyApplied":
 338                        m->type==Conflict?"Conflict":"unknown",
 339                        m->a, m->a+m->al-1,
 340                        m->b, m->b+m->bl-1,
 341                        m->c, m->c+m->cl-1, m->in_conflict?" in_conflict":"",
 342                        m->lo, m->hi);
 343 #endif
 344                 while (m->in_conflict) {
 345                         /* need to print from 'hi' to 'lo' of next
 346                          * Unchanged which is < it's hi
 347                          */
 348                         int st = m->hi;
 349
 350                         if (m->type == Unchanged)
 351                                 printrange(out, a, m->a+m->lo, m->hi - m->lo);
 352                         else
 353                                 printrange(out, c, m->c, m->cl);
 354
 355 #if 1
 356                 if (v)
 357                         for (cm=m; cm->in_conflict; cm++) {
 358                                 printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}\n",
 359                                        cm->type==Unmatched?"Unmatched":
 360                                        cm->type==Unchanged?"Unchanged":
 361                                        cm->type==Extraneous?"Extraneous":
 362                                        cm->type==Changed?"Changed":
 363                                        cm->type==AlreadyApplied?"AlreadyApplied":
 364                                        cm->type==Conflict?"Conflict":"unknown",
 365                                        cm->a, cm->a+cm->al-1,
 366                                        cm->b, cm->b+cm->bl-1,
 367                                        cm->c, cm->c+cm->cl-1, cm->in_conflict?" in_conflict":"",
 368                                        cm->lo, cm->hi);
 369                                 if (cm->type == Unchanged && cm != m && cm->lo < cm->hi)
 370                                         break;
 371                         }
 372 #endif
 373
 374                         fputs(words?"<<<---":"<<<<<<<\n", out);
 375                         for (cm=m; cm->in_conflict; cm++) {
 376                                 if ((cm->type == Unchanged || cm->type == Changed) && cm != m && cm->lo < cm->hi) {
 377                                         printrange(out, a, cm->a, cm->lo);
 378                                         break;
 379                                 }
 380                                 printrange(out, a, cm->a+st, cm->al-st);
 381                                 st = 0;
 382                         }
 383                         fputs(words?"|||":"|||||||\n", out);
 384                         st = m->hi;
 385                         for (cm=m; cm->in_conflict; cm++) {
 386                                 if ((cm->type == Unchanged || cm->type == Changed) && cm != m && cm->lo < cm->hi) {
 387                                         printrange(out, b, cm->b, cm->lo);
 388                                         break;
 389                                 }
 390                                 printrange(out, b, cm->b+st, cm->bl-st);
 391                                 st = 0;
 392                         }
 393                         fputs(words?"===":"=======\n", out);
 394                         st = m->hi;
 395                         for (cm=m; cm->in_conflict; cm++) {
 396                                 if ((cm->type == Unchanged || cm->type == Changed) && cm != m && cm->lo < cm->hi) {
 397                                         if (cm->type == Unchanged)
 398                                                 printrange(out, c, cm->c, cm->lo);
 399                                         break;
 400                                 }
 401                                 printrange(out, c, cm->c+st, cm->cl-st);
 402                                 st = 0;
 403                         }
 404                         fputs(words?"--->>>":">>>>>>>\n", out);
 405                         m = cm;
 406                         if (m->type == Unchanged && m->in_conflict && m->hi >= m->al) {
 407                                 printrange(out, a, m->a+m->lo, m->hi-m->lo);
 408                                 m++;
 409                         }
 410                 }
 411
 412                 /* there is always some non-conflict after a conflict,
 413                  * unless we hit the end
 414                  */
 415                 if (m->type == End)
 416                         break;
 417                 switch(m->type) {
 418                 case Unchanged:
 419                 case AlreadyApplied:
 420                 case Unmatched:
 421                         printrange(out, a, m->a, m->al);
 422                         break;
 423                 case Extraneous:
 424                         break;
 425                 case Changed:
 426                         printrange(out, c, m->c, m->cl);
 427                         break;
 428                 case Conflict:
 429                 case End: assert(0);
 430                 }
 431         }
 432         return rv;
 433 }