merge2.c

   1 /*
   2  * wiggle - apply rejected patches
   3  *
   4  * Copyright (C) 2005 Neil Brown <neilb@cse.unsw.edu.au>
   5  * Copyright (C) 2010-2013 Neil Brown <neilb@suse.de>
   6  *
   7  *
   8  *    This program is free software; you can redistribute it and/or modify
   9  *    it under the terms of the GNU General Public License as published by
  10  *    the Free Software Foundation; either version 2 of the License, or
  11  *    (at your option) any later version.
  12  *
  13  *    This program is distributed in the hope that it will be useful,
  14  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16  *    GNU General Public License for more details.
  17  *
  18  *    You should have received a copy of the GNU General Public License
  19  *    along with this program.
  20  *
  21  *    Author: Neil Brown
  22  *    Email: <neilb@suse.de>
  23  */
  24
  25 #include "wiggle.h"
  26 #include <limits.h>
  27
  28 /*
  29  * Second attempt at merging....
  30  *
  31  * We want to create a mergelist which identifies 'orig' and 'after'
  32  * sections (from a and c) and conflicts (which are ranges of a,b,c which
  33  * all don't match).
  34  * It is also helpful to differentiate 'orig' sections that aren't
  35  * matched in 'b' with orig sections that are.
  36  * To help with highlighting, it will be useful to know where
  37  * the conflicts match the csl lists.
  38  *
  39  * This can all be achieved with a list of (a,b,c,c1,c1) 5-tuples.
  40  * If two consecutive differ in more than one of a,b,c, it is a
  41  * conflict.
  42  * If only 'a' differ, it is un-matched original.
  43  * If only 'b' differ, it is matched, unchanged original
  44  * If only 'c' differ, it is 1
  45  */
  46
  47 static inline int min(int a, int b)
  48 {
  49         return a < b ? a : b;
  50 }
  51
  52 static int check_alreadyapplied(struct file af, struct file cf,
  53                                 struct merge *m)
  54 {
  55         int i;
  56         if (m->al != m->cl)
  57                 return 0;
  58         for (i = 0; i < m->al; i++) {
  59                 if (af.list[m->a+i].len != cf.list[m->c+i].len)
  60                         return 0;
  61                 if (strncmp(af.list[m->a+i].start,
  62                             cf.list[m->c+i].start,
  63                             af.list[m->a+i].len) != 0)
  64                         return 0;
  65         }
  66         if (do_trace) {
  67                 printf("already applied %d,%d,%d - %d,%d,%d\n",
  68                        m->a, m->b, m->c, m->al, m->bl, m->cl);
  69                 printf(" %.10s - %.10s\n", af.list[m->a].start,
  70                        cf.list[m->c].start);
  71         }
  72         m->type = AlreadyApplied;
  73         return 1;
  74 }
  75
  76 /* A 'cut-point' is a location in the merger where it is reasonable
  77  * the change the mode of display - between displaying the merger
  78  * and displaying the separate streams.
  79  * A 'conflict' can only be displayed as separate stream so when
  80  * one is found, we need to find a preceding and trailing cut-point
  81  * and enlarge the conflict to that range.
  82  * A suitable location is one where all three streams are at a line-end.
  83  */
  84 static int is_cutpoint(struct merge m,
  85                        struct file af, struct file bf, struct file cf)
  86 {
  87         return ((m.a == 0 || ends_line(af.list[m.a-1])) &&
  88                 (m.b == 0 || ends_line(bf.list[m.b-1])) &&
  89                 (m.c == 0 || ends_line(cf.list[m.c-1])));
  90 }
  91
  92 int isolate_conflicts(struct file af, struct file bf, struct file cf,
  93                       struct csl *csl1, struct csl *csl2, int words,
  94                       struct merge *m, int show_wiggles,
  95                       int *wigglesp)
  96 {
  97         /* A Conflict indicates that something is definitely wrong
  98          * and so we need to be a bit suspicious of nearby apparent matches.
  99          * To display a conflict effectively we expands its effect to
 100          * include any Extraneous, Unmatched, Changed or AlreadyApplied text.
 101          * Also, unless 'words', we need to include any partial lines
 102          * in the Unchanged text that forms the border of a conflict.
 103          *
 104          * A Changed text may also border a conflict, but it can
 105          * only border one conflict (where as an Unchanged can border
 106          * a preceding and a following conflict).
 107          * The 'new' section of a Changed text appears in the
 108          * conflict as does any part of the original before
 109          * a newline.
 110          *
 111          * A hunk header (Extraneous) is never considered part of a
 112          * conflict.  It thereby can serve as a separator between
 113          * conflicts.
 114          *
 115          * Extended conflicts are marked by setting ->in_conflict in
 116          * the "struct merge".  This is '1' for an Unchanged, Changed,
 117          * or (Extraneous) hunk header which borders the conflict,
 118          * '2' for a merger which is truly in conflict, and '3' for
 119          * a merger which is causing a 'wiggle'.
 120          * When in_conflict == 1, the 'lo' and 'hi' fields indicate
 121          * how much of the 'a' file is included in the conflict, the rest
 122          * being part of the clean result.
 123          * Elements in af from m->a to m->a+m->lo are in the preceding
 124          * conflict, from m->a+m->lo to m->a+m->hi are clean, and
 125          * m->a+m->hi to m->a+m->al are in the following conflict.
 126          *
 127          * We need to ensure there is adequate context for the conflict.
 128          * So ensure there are at least 3 newlines in Extraneous or
 129          * Unchanged on both sides of a Conflict - but don't go so far
 130          * as including a hunk header.
 131          * If there are 3, and they are all in 'Unchanged' sections, then
 132          * that much context is not really needed - reduce it a bit.
 133          *
 134          * If a wiggle is adjacent to a conflict then:
 135          * - if show_wiggles is set, we just merge them
 136          * - if it is not set, we still want to count the wiggle.
 137          */
 138         int i, j, k;
 139         int cnt = 0, wiggles = 0;
 140         int in_wiggle = 0;
 141         int changed = 0;
 142         int unmatched = 0;
 143         int extraneous = 0;
 144
 145         for (i = 0; m[i].type != End; i++)
 146                 m[i].in_conflict = 0;
 147
 148         for (i = 0; m[i].type != End; i++) {
 149                 /* The '3' here is a count of newlines.  Once we find
 150                  * that many newlines of the particular type, we have escaped.
 151                  */
 152                 if (m[i].type == Changed)
 153                         changed = 3;
 154                 if (m[i].type == Unmatched)
 155                         unmatched = 3;
 156                 if (m[i].type == Extraneous && bf.list[m[i].b].start[0])
 157                         /* hunk headers don't imply wiggles, other
 158                          * extraneous text does.
 159                          */
 160                         extraneous = 3;
 161
 162                 if (m[i].type != Unchanged && changed && (unmatched || extraneous)) {
 163                         if (!in_wiggle)
 164                                 wiggles++;
 165                         in_wiggle = 1;
 166                 } else
 167                         in_wiggle = 0;
 168
 169                 if ((m[i].type == Conflict) ||
 170                     (show_wiggles && in_wiggle)) {
 171                         /* We have a conflict or wiggle here.
 172                          * First search backwards for an Unchanged marking
 173                          * things as in_conflict.  Then find the
 174                          * cut-point in the Unchanged.  If there isn't one,
 175                          * keep looking.
 176                          *
 177                          * Then search forward doing the same thing.
 178                          */
 179                         int newlines = 0;
 180                         m[i].in_conflict = m[i].type == Conflict ? 2 : 3;
 181                         j = i;
 182                         while (--j >= 0) {
 183                                 int firstk;
 184
 185                                 if (m[j].type == Extraneous &&
 186                                     bf.list[m[j].b].start[0] == '\0')
 187                                         /* hunk header - not conflict any more */
 188                                         break;
 189                                 if (m[j].in_conflict > 1)
 190                                         /* Merge the conflicts */
 191                                         break;
 192                                 if (!m[j].in_conflict) {
 193                                         m[j].in_conflict = 1;
 194                                         m[j].lo = 0;
 195                                 }
 196                                 /* Following must set m[j].hi, or set
 197                                  * in_conflict > 1
 198                                  */
 199                                 if (m[j].type == Extraneous) {
 200                                         for (k = m[j].bl; k > 0; k--)
 201                                                 if (ends_line(bf.list[m[j].b+k-1]))
 202                                                         newlines++;
 203                                 }
 204
 205                                 if (m[j].type != Unchanged &&
 206                                     m[j].type != Changed) {
 207                                         if (m[j].type == Conflict)
 208                                                 m[j].in_conflict = 2;
 209                                         else
 210                                                 m[j].in_conflict = m[i].in_conflict;
 211                                         continue;
 212                                 }
 213                                 /* If we find enough newlines in this section,
 214                                  * then we only really need 1, but would rather
 215                                  * it wasn't the first one.  'firstk' allows us
 216                                  * to track which newline we actually use
 217                                  */
 218                                 firstk = m[j].al+1;
 219                                 if (words) {
 220                                         m[j].hi = m[j].al;
 221                                         break;
 222                                 }
 223                                 /* need to find the last line-break, which
 224                                  * might be after the last newline, if there
 225                                  * is one, or might be at the start
 226                                  */
 227                                 for (k = m[j].al; k > 0; k--) {
 228                                         if (m[j].a + k >= af.elcnt)
 229                                                 /* FIXME impossible!*/
 230                                                 break;
 231                                         if (ends_line(af.list[m[j].a+k-1])) {
 232                                                 if (firstk > m[j].al)
 233                                                         firstk = k;
 234                                                 newlines++;
 235                                                 if (newlines >= 3) {
 236                                                         k = firstk;
 237                                                         break;
 238                                                 }
 239                                         }
 240                                 }
 241                                 if (k > 0)
 242                                         m[j].hi = k;
 243                                 else if (j == 0)
 244                                         m[j].hi = firstk;
 245                                 else if (is_cutpoint(m[j], af,bf,cf))
 246                                         m[j].hi = 0;
 247                                 else
 248                                         /* no start-of-line found... */
 249                                         m[j].hi = -1;
 250                                 if (m[j].hi > 0 &&
 251                                     (m[j].type == Changed)) {
 252                                         /* this can only work if start is
 253                                          * also a line break */
 254                                         if (is_cutpoint(m[j], af,bf,cf))
 255                                                 /* ok */;
 256                                         else
 257                                                 m[j].hi = -1;
 258                                 }
 259                                 if (m[j].hi >= 0)
 260                                         break;
 261                                 m[j].in_conflict = m[i].in_conflict;
 262                         }
 263
 264                         /* now the forward search */
 265                         newlines = 0;
 266                         for (j = i+1; m[j].type != End; j++) {
 267                                 if (m[j].type == Extraneous &&
 268                                     bf.list[m[j].b].start[0] == '\0')
 269                                         /* hunk header - not conflict any more */
 270                                         break;
 271                                 if (m[j].type == Extraneous) {
 272                                         for (k = 0; k < m[j].bl; k++)
 273                                                 if (ends_line(bf.list[m[j].b+k]))
 274                                                         newlines++;
 275                                 }
 276                                 if (m[j].type != Unchanged &&
 277                                     m[j].type != Changed) {
 278                                         if (m[j].type == Conflict)
 279                                                 m[j].in_conflict = 2;
 280                                         else
 281                                                 m[j].in_conflict = m[i].in_conflict;
 282                                         continue;
 283                                 }
 284                                 m[j].in_conflict = 1;
 285                                 m[j].hi = m[j].al;
 286                                 if (words) {
 287                                         m[j].lo = 0;
 288                                         break;
 289                                 }
 290                                 /* need to find a line-break, which might be at
 291                                  * the very beginning, or might be after the
 292                                  * first newline - if there is one
 293                                  */
 294                                 if (is_cutpoint(m[j], af,bf,cf))
 295                                         m[j].lo = 0;
 296                                 else {
 297                                         /* If we find enough newlines in this section,
 298                                          * then we only really need 1, but would rather
 299                                          * it wasn't the first one.  'firstk' allows us
 300                                          * to track which newline we actually use
 301                                          */
 302                                         int firstk = -1;
 303                                         for (k = 0 ; k < m[j].al ; k++)
 304                                                 if (ends_line(af.list[m[j].a+k])) {
 305                                                         if (firstk < 0)
 306                                                                 firstk = k;
 307                                                         newlines++;
 308                                                         if (newlines >= 3) {
 309                                                                 k = firstk;
 310                                                                 break;
 311                                                         }
 312                                                 }
 313                                         if (newlines < 3 &&
 314                                             m[j+1].type  == End)
 315                                                 /* Hit end of file, pretend we found 3 newlines. */
 316                                                 k = firstk;
 317
 318                                         if (firstk >= 0 &&
 319                                             m[j+1].type == Unmatched) {
 320                                                 /* If this Unmatched exceeds 3 lines, just stop here */
 321                                                 int p;
 322                                                 int nl = 0;
 323                                                 for (p = 0; p < m[j+1].al ; p++)
 324                                                         if (ends_line(af.list[m[j+1].a+p])) {
 325                                                                 nl++;
 326                                                                 if (nl > 3)
 327                                                                         break;
 328                                                         }
 329                                                 if (nl > 3)
 330                                                         k = firstk;
 331                                         }
 332                                         if (k < m[j].al)
 333                                                 m[j].lo = k+1;
 334                                         else
 335                                                 /* no start-of-line found */
 336                                                 m[j].lo = m[j].al+1;
 337                                 }
 338                                 if (m[j].lo <= m[j].al+1 &&
 339                                     (m[j].type == Changed)) {
 340                                         /* this can only work if the end is a line break */
 341                                         if (is_cutpoint(m[j+1], af,bf,cf))
 342                                                 /* ok */;
 343                                         else
 344                                                 m[j].lo = m[j].al+1;
 345                                 }
 346                                 if (m[j].lo < m[j].al+1)
 347                                         break;
 348                                 m[j].in_conflict = m[i].in_conflict;
 349                         }
 350                         if (m[j-1].in_conflict == 1)
 351                                 i = j - 1;
 352                         else
 353                                 /* A hunk header bordered the conflict */
 354                                 i = j;
 355
 356                         /* If any of the merges are Changed or Conflict,
 357                          * then this really is a Conflict or Wiggle.
 358                          * If not they are just Unchanged, Unmatched,
 359                          * Extraneous or AlreadyApplied, and so don't
 360                          * really count.
 361                          * Note that the first/last merges (in_conflict==1)
 362                          * can be Changed and so much be check separately.
 363                          */
 364                         if (m[j].type == Changed)
 365                                 goto out;
 366                         for (j = i-1; j >= 0 && m[j].in_conflict > 1; j--)
 367                                 if (m[j].type == Changed || m[j].type == Conflict)
 368                                         goto out;
 369                         if (j >= 0 && m[j].type == Changed)
 370                                 goto out;
 371                         /* False alarm, no real conflict/wiggle here as
 372                          * nothing changed. */
 373                         if (j < 0)
 374                                 j = 0;
 375                         if (m[j].in_conflict == 1) {
 376                                 m[j].hi = m[j].al;
 377                                 if (m[j].lo == 0)
 378                                         m[j].in_conflict = 0;
 379                                 j++;
 380                         }
 381                         while (j <= i)
 382                                 m[j++].in_conflict = 0;
 383                 out:
 384                         if (m[i].type == End)
 385                                 break;
 386                 }
 387                 for (k = 1; k < m[i].al; k++) {
 388                         if (m[i].a + k >= af.elcnt)
 389                                 /* FIXME this should be impossible, but
 390                                  * it happened.
 391                                  */
 392                                 break;
 393                         if (words || ends_line(af.list[m[i].a+k])) {
 394                                 if (unmatched)
 395                                         unmatched--;
 396                                 if (changed)
 397                                         changed--;
 398                                 if (extraneous)
 399                                         extraneous--;
 400                         }
 401                 }
 402         }
 403         if (!show_wiggles)
 404                 *wigglesp = wiggles;
 405         /* Now count the conflicts and wiggles */
 406         for (i = 0; m[i].type != End; i++) {
 407                 int true_conflict = 0;
 408                 if (!m[i].in_conflict)
 409                         continue;
 410
 411                 for (j = i; m[j].type != End && m[j].in_conflict; j++) {
 412                         if (m[j].in_conflict == 2)
 413                                 true_conflict = 1;
 414                         if (j > i &&
 415                             m[j].in_conflict == 1) {
 416                                 /* end of region */
 417                                 if (!m[j+1].in_conflict)
 418                                         j++;
 419                                 break;
 420                         }
 421                 }
 422                 if (true_conflict)
 423                         cnt++;
 424                 else
 425                         wiggles++;
 426                 i = j-1;
 427         }
 428         if (show_wiggles)
 429                 *wigglesp = wiggles;
 430         return cnt;
 431 }
 432
 433 struct ci make_merger(struct file af, struct file bf, struct file cf,
 434                       struct csl *csl1, struct csl *csl2, int words,
 435                       int ignore_already, int show_wiggles)
 436 {
 437         /* find the wiggles and conflicts between csl1 and csl2
 438          */
 439         struct ci rv;
 440         int i, l;
 441         int a, b, c, c1, c2;
 442         int header_checked = -1;
 443         int header_found = 0;
 444
 445         rv.conflicts = rv.wiggles = rv.ignored = 0;
 446
 447         for (i = 0; csl1[i].len; i++)
 448                 ;
 449         l = i;
 450         for (i = 0; csl2[i].len; i++)
 451                 ;
 452         l += i;
 453         /* maybe a bit of slack at each end */
 454         l = l * 4 + 10;
 455
 456         rv.merger = xmalloc(sizeof(struct merge)*l);
 457
 458         a = b = c = c1 = c2 = 0;
 459         i = 0;
 460         while (1) {
 461                 int match1, match2;
 462                 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
 463                 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
 464
 465                 if (header_checked != c2) {
 466                         /* Check if there is a hunk header in this range */
 467                         int j;
 468                         header_found = -1;
 469                         for (j = b; j < csl2[c2].a + csl2[c2].len; j++)
 470                                 if (bf.list[j].start[0] == '\0') {
 471                                         header_found = j;
 472                                         break;
 473                                 }
 474                         header_checked = c2;
 475                 }
 476                 rv.merger[i].a = a;
 477                 rv.merger[i].b = b;
 478                 rv.merger[i].c = c;
 479                 rv.merger[i].c1 = c1;
 480                 rv.merger[i].c2 = c2;
 481                 rv.merger[i].in_conflict = 0;
 482
 483                 if (!match1 && match2) {
 484                         /* This is either Unmatched or Extraneous - probably both.
 485                          * If the match2 has a hunk-header Extraneous, it must
 486                          * align with an end-of-line in 'a', so adjust endpoint
 487                          */
 488                         int newa = csl1[c1].a;
 489                         if (header_found >= 0) {
 490                                 while (newa > a &&
 491                                        !ends_line(af.list[newa-1]))
 492                                         newa--;
 493                         }
 494                         if (a == newa && b == csl1[c1].b)
 495                                 newa = csl1[c1].a;
 496                         if (a < newa) {
 497                                 /* some unmatched text */
 498                                 rv.merger[i].type = Unmatched;
 499                                 rv.merger[i].al = newa - a;
 500                                 rv.merger[i].bl = 0;
 501                                 rv.merger[i].cl = 0;
 502                         } else {
 503                                 int newb;
 504                                 assert(b < csl1[c1].b);
 505                                 /* some Extraneous text */
 506                                 /* length is min of unmatched on left
 507                                  * and matched on right.
 508                                  * However a hunk-header must be an
 509                                  * Extraneous section by itself, so if this
 510                                  * start with one, the length is 1, and if
 511                                  * there is one in the middle, only take the
 512                                  * text up to there for now.
 513                                  */
 514                                 rv.merger[i].type = Extraneous;
 515                                 rv.merger[i].al = 0;
 516                                 newb = b +
 517                                         min(csl1[c1].b - b,
 518                                             csl2[c2].len - (b-csl2[c2].a));
 519                                 if (header_found == b) {
 520                                         newb = b + 1;
 521                                         header_checked = -1;
 522                                 } else if (header_found > b && header_found < newb) {
 523                                         newb = header_found;
 524                                         header_checked = -1;
 525                                 }
 526                                 assert(newb > b);
 527                                 rv.merger[i].cl =
 528                                         rv.merger[i].bl = newb - b;
 529                         }
 530                 } else if (match1 && !match2) {
 531                         /* some changed text
 532                          * if 'c' is currently at a suitable cut-point, then
 533                          * we can look for a triple-cut-point for start.
 534                          * Also, if csl2[c2].b isn't in a conflict, and is
 535                          * a suitable cut-point, then we could make a
 536                          * triple-cut-point for end of a conflict.
 537                          */
 538
 539                         rv.merger[i].type = Changed;
 540                         rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
 541                         rv.merger[i].al = rv.merger[i].bl;
 542                         rv.merger[i].cl = csl2[c2].b - c;
 543                 } else if (match1 && match2) {
 544                         /* Some unchanged text
 545                          */
 546                         rv.merger[i].type = Unchanged;
 547                         rv.merger[i].bl =
 548                                 min(csl1[c1].len - (b-csl1[c1].b),
 549                                     csl2[c2].len - (b-csl2[c2].a));
 550                         rv.merger[i].al = rv.merger[i].cl =
 551                                 rv.merger[i].bl;
 552                 } else {
 553                         /* must be a conflict.
 554                          * Move a and c to next match, and b to closest of the two
 555                          */
 556                         rv.merger[i].type = Conflict;
 557                         rv.merger[i].al = csl1[c1].a - a;
 558                         rv.merger[i].cl = csl2[c2].b - c;
 559                         rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
 560                         if (ignore_already &&
 561                             check_alreadyapplied(af, cf, &rv.merger[i]))
 562                                 rv.ignored++;
 563                         else if (rv.merger[i].bl == 0 &&
 564                                  rv.merger[i].cl > 0)
 565                                 /* As the 'before' stream is empty, this
 566                                  * could look like Unmatched in the
 567                                  * original, and an insertion in the
 568                                  * diff.  Reporting it like that is
 569                                  * probably more useful that as a full
 570                                  * conflict.
 571                                  * Leave the type for the insertion as
 572                                  * Conflict (not Changed) as there is some
 573                                  * real uncertainty here, but allow the
 574                                  * original to become Unmatched.
 575                                  */
 576                                 rv.merger[i].al = 0;
 577                 }
 578                 rv.merger[i].oldtype = rv.merger[i].type;
 579                 a += rv.merger[i].al;
 580                 b += rv.merger[i].bl;
 581                 c += rv.merger[i].cl;
 582                 i++;
 583
 584                 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
 585                         c1++;
 586                 assert(csl1[c1].b + csl1[c1].len >= b);
 587                 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
 588                         c2++;
 589                 assert(csl2[c2].a + csl2[c2].len >= b);
 590                 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
 591                     a == csl1[c1].a && b == csl1[c1].b &&
 592                     b == csl2[c2].a && c == csl2[c2].b)
 593                         break;
 594         }
 595         rv.merger[i].type = End;
 596         rv.merger[i].oldtype = End;
 597         rv.merger[i].a = a;
 598         rv.merger[i].b = b;
 599         rv.merger[i].c = c;
 600         rv.merger[i].c1 = c1;
 601         rv.merger[i].c2 = c2;
 602         rv.merger[i].in_conflict = 0;
 603         assert(i < l);
 604
 605         /* Now revert any AlreadyApplied that aren't bounded by
 606          * Unchanged or Changed.
 607          */
 608         for (i = 0; rv.merger[i].type != End; i++) {
 609                 if (rv.merger[i].type != AlreadyApplied)
 610                         continue;
 611                 if (i > 0 && rv.merger[i-1].type != Unchanged &&
 612                     rv.merger[i-1].type != Changed)
 613                         rv.merger[i].type = Conflict;
 614                 if (rv.merger[i+1].type != Unchanged &&
 615                     rv.merger[i+1].type != Changed &&
 616                     rv.merger[i+1].type != End)
 617                         rv.merger[i].type = Conflict;
 618         }
 619         rv.conflicts = isolate_conflicts(af, bf, cf, csl1, csl2, words,
 620                                          rv.merger, show_wiggles, &rv.wiggles);
 621         return rv;
 622 }
 623
 624 static int printrange(FILE *out, struct file *f, int start, int len,
 625                       int offset)
 626 {
 627         int lines = 0;
 628         while (len > 0 && start < f->elcnt) {
 629                 struct elmnt e = f->list[start];
 630                 printword(out, e);
 631                 if (e.start[e.plen-1] == '\n' &&
 632                     offset > 0)
 633                         lines++;
 634                 offset--;
 635                 start++;
 636                 len--;
 637         }
 638         return lines;
 639 }
 640
 641 int print_merge(FILE *out, struct file *a, struct file *b, struct file *c,
 642                 int words, struct merge *merger,
 643                 struct merge *mpos, int streampos, int offsetpos)
 644 {
 645         struct merge *m;
 646         int lineno = 1;
 647         int rv = 0;
 648         int offset = INT_MAX;
 649
 650         for (m = merger; m->type != End ; m++) {
 651                 struct merge *cm;
 652                 if (do_trace)
 653                         printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
 654                                m->type==Unmatched ? "Unmatched" :
 655                                m->type==Unchanged ? "Unchanged" :
 656                                m->type==Extraneous ? "Extraneous" :
 657                                m->type==Changed ? "Changed" :
 658                                m->type==AlreadyApplied ? "AlreadyApplied" :
 659                                m->type==Conflict ? "Conflict":"unknown",
 660                                m->a, m->a+m->al-1,
 661                                m->b, m->b+m->bl-1,
 662                                m->c, m->c+m->cl-1,
 663                                m->in_conflict ? " in_conflict" : "",
 664                                m->lo, m->hi);
 665
 666                 while (m->in_conflict) {
 667                         /* need to print from 'hi' to 'lo' of next
 668                          * Unchanged which is < it's hi
 669                          */
 670                         int found_conflict = 0;
 671                         int st = 0, st1;
 672                         if (m->in_conflict == 1)
 673                                 st = m->hi;
 674                         st1 = st;
 675
 676                         if (m == mpos)
 677                                 offset = offsetpos;
 678                         if (m->in_conflict == 1 && m->type == Unchanged)
 679                                 lineno += printrange(out, a, m->a+m->lo, m->hi - m->lo, offset - m->lo);
 680
 681                         if (m == mpos)
 682                                 rv = lineno;
 683                         if (do_trace)
 684                                 for (cm = m; cm->in_conflict; cm++) {
 685                                         printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}\n",
 686                                                cm->type==Unmatched?"Unmatched":
 687                                                cm->type==Unchanged?"Unchanged":
 688                                                cm->type==Extraneous?"Extraneous":
 689                                                cm->type==Changed?"Changed":
 690                                                cm->type==AlreadyApplied?"AlreadyApplied":
 691                                                cm->type==Conflict?"Conflict":"unknown",
 692                                                cm->a, cm->a+cm->al-1,
 693                                                cm->b, cm->b+cm->bl-1,
 694                                                cm->c, cm->c+cm->cl-1,
 695                                                cm->in_conflict ? " in_conflict" : "",
 696                                                cm->lo, cm->hi);
 697                                         if (cm->in_conflict == 1 && cm != m)
 698                                                 break;
 699                                 }
 700
 701                         if (m->in_conflict == 1 &&
 702                             m[1].in_conflict == 1) {
 703                                 /* Nothing between two conflicts */
 704                                 m++;
 705                                 continue;
 706                         }
 707
 708                         fputs(words ? "<<<---" : "<<<<<<< found\n", out);
 709                         if (!words)
 710                                 lineno++;
 711                         for (cm = m; cm->in_conflict; cm++) {
 712                                 if (cm == mpos && streampos == 0)
 713                                         offset = offsetpos;
 714                                 if (cm->type == Conflict)
 715                                         found_conflict = 1;
 716                                 if (cm->in_conflict == 1 && cm != m) {
 717                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 718                                         break;
 719                                 }
 720                                 lineno += printrange(out, a, cm->a+st1, cm->al-st1, offset-st1);
 721                                 st1 = 0;
 722                                 if (cm == mpos && streampos == 0)
 723                                         rv = lineno;
 724                         }
 725                         if (cm == mpos && streampos == 0)
 726                                 rv = lineno;
 727                         fputs(words ? "|||" : "||||||| expected\n", out);
 728                         if (!words)
 729                                 lineno++;
 730                         st1 = st;
 731                         for (cm = m; cm->in_conflict; cm++) {
 732                                 if (cm == mpos && streampos == 1)
 733                                         offset = offsetpos;
 734                                 if (cm->in_conflict == 1 && cm != m) {
 735                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 736                                         break;
 737                                 }
 738                                 lineno += printrange(out, b, cm->b+st1, cm->bl-st1, offset-st1);
 739                                 st1 = 0;
 740                                 if (cm == mpos && streampos == 1)
 741                                         rv = lineno;
 742                         }
 743                         if (cm == mpos && streampos == 1)
 744                                 rv = lineno;
 745                         fputs(words ? "===" : "=======\n", out);
 746                         if (!words)
 747                                 lineno++;
 748                         st1 = st;
 749                         for (cm = m; cm->in_conflict; cm++) {
 750                                 if (cm == mpos && streampos == 2)
 751                                         offset = offsetpos;
 752                                 if (cm->in_conflict == 1 && cm != m) {
 753                                         if (cm->type == Unchanged)
 754                                                 lineno += printrange(out, a, cm->a, cm->lo, offset);
 755                                         else
 756                                                 lineno += printrange(out, c, cm->c, cm->cl, offset);
 757                                         break;
 758                                 }
 759                                 if (cm->type == Changed)
 760                                         st1 = 0; /* All of result of change must be printed */
 761                                 lineno += printrange(out, c, cm->c+st1, cm->cl-st1, offset-st1);
 762                                 st1 = 0;
 763                                 if (cm == mpos && streampos == 2)
 764                                         rv = lineno;
 765                         }
 766                         if (cm == mpos && streampos == 2)
 767                                 rv = lineno;
 768                         if (!found_conflict) {
 769                                 /* This section was wiggled in successfully,
 770                                  * but full conflict display was requested.
 771                                  * So now print out the wiggled result as well.
 772                                  */
 773                                 fputs(words ? "&&&" : "&&&&&&& resolution\n", out);
 774                                 if (!words)
 775                                         lineno++;
 776                                 st1 = st;
 777                                 for (cm = m; cm->in_conflict; cm++) {
 778                                         int last = 0;
 779                                         if (cm->in_conflict == 1 && cm != m)
 780                                                 last = 1;
 781                                         switch (cm->type) {
 782                                         case Unchanged:
 783                                         case AlreadyApplied:
 784                                         case Unmatched:
 785                                                 lineno += printrange(out, a, cm->a+st1,
 786                                                                      last ? cm->lo : cm->al-st1, offset-st1);
 787                                                 break;
 788                                         case Extraneous:
 789                                                 break;
 790                                         case Changed:
 791                                                 lineno += printrange(out, c, cm->c,
 792                                                                      last ? cm->lo : cm->cl, offset);
 793                                                 break;
 794                                         case Conflict:
 795                                         case End:
 796                                                 assert(0);
 797                                         }
 798                                         if (last)
 799                                                 break;
 800                                         st1 = 0;
 801                                 }
 802                         }
 803                         fputs(words ? "--->>>" : ">>>>>>> replacement\n", out);
 804                         if (!words)
 805                                 lineno++;
 806                         m = cm;
 807                         if (m->in_conflict == 1 && m[1].in_conflict == 0) {
 808                                 /* End of a conflict, no conflict follows */
 809                                 if (m == mpos)
 810                                         offset = offsetpos;
 811                                 if (m->type == Unchanged)
 812                                         lineno += printrange(out, a, m->a+m->lo, m->hi-m->lo, offset-m->lo);
 813                                 if (m == mpos)
 814                                         rv = lineno;
 815                                 m++;
 816                         }
 817                 }
 818
 819                 /* there is always some non-conflict after a conflict,
 820                  * unless we hit the end
 821                  */
 822                 if (m->type == End)
 823                         break;
 824
 825                 if (do_trace) {
 826                         printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
 827                                m->type==Unmatched?"Unmatched":
 828                                m->type==Unchanged?"Unchanged":
 829                                m->type==Extraneous?"Extraneous":
 830                                m->type==Changed?"Changed":
 831                                m->type==AlreadyApplied?"AlreadyApplied":
 832                                m->type==Conflict?"Conflict":"unknown",
 833                                m->a, m->a+m->al-1,
 834                                m->b, m->b+m->bl-1,
 835                                m->c, m->c+m->cl-1,
 836                                m->in_conflict ? " in_conflict" : "",
 837                                m->lo, m->hi);
 838                 }
 839                 if (m == mpos)
 840                         offset = offsetpos;
 841
 842                 switch (m->type) {
 843                 case Unchanged:
 844                 case AlreadyApplied:
 845                 case Unmatched:
 846                         lineno += printrange(out, a, m->a, m->al, offset);
 847                         break;
 848                 case Extraneous:
 849                         break;
 850                 case Changed:
 851                         lineno += printrange(out, c, m->c, m->cl, offset);
 852                         break;
 853                 case Conflict:
 854                 case End:
 855                         assert(0);
 856                 }
 857                 if (m == mpos)
 858                         rv = lineno;
 859         }
 860         return rv;
 861 }
 862
 863 int save_merge(struct file a, struct file b, struct file c,
 864                struct merge *merger, char *file, int backup)
 865 {
 866         char *replacename = xmalloc(strlen(file) + 20);
 867         char *orignew = xmalloc(strlen(file) + 20);
 868         int fd;
 869         FILE *outfile;
 870         int err = 0;
 871         int lineno = 0;
 872         strcpy(replacename, file);
 873         strcat(replacename, "XXXXXX");
 874         strcpy(orignew, file);
 875         strcat(orignew, ".porig");
 876
 877         fd = mkstemp(replacename);
 878         if (fd < 0) {
 879                 err = -1;
 880                 goto out;
 881         }
 882         outfile = fdopen(fd, "w");
 883         lineno = print_merge(outfile, &a, &b, &c, 0, merger,
 884                              NULL, 0, 0);
 885         fclose(outfile);
 886         if (backup && rename(file, orignew) != 0)
 887                 err = -2;
 888         else if (rename(replacename, file) != 0)
 889                 err = -2;
 890
 891 out:
 892         free(replacename);
 893         free(orignew);
 894         return err < 0 ? err : lineno;
 895 }
 896
 897 int save_tmp_merge(struct file a, struct file b, struct file c,
 898                    struct merge *merger, char **filep,
 899                    struct merge *mpos, int streampos, int offsetpos)
 900 {
 901         int fd;
 902         FILE *outfile;
 903         char *dir, *fname;
 904         int lineno;
 905         int suffix = 0;
 906
 907         if (!*filep) {
 908                 dir = getenv("TMPDIR");
 909                 if (!dir)
 910                         dir = "/tmp";
 911
 912                 asprintf(&fname, "%s/wiggle-tmp-XXXXXX", dir);
 913         } else {
 914                 char *base;
 915                 dir = *filep;
 916                 base = strrchr(dir, '/');
 917                 if (base)
 918                         base++;
 919                 else
 920                         base = dir;
 921                 asprintf(&fname, "%.*stmp-XXXXXX-%s", (int)(base-dir), dir, base);
 922                 suffix = strlen(base)+1;
 923         }
 924         fd = mkstemps(fname, suffix);
 925
 926         if (fd < 0) {
 927                 free(fname);
 928                 *filep = NULL;
 929                 return -1;
 930         }
 931         outfile = fdopen(fd, "w");
 932         lineno = print_merge(outfile, &a, &b, &c, 0, merger,
 933                              mpos, streampos, offsetpos);
 934         fclose(outfile);
 935         *filep = fname;
 936         return lineno;
 937 }