merge2.c

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