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 preceeding 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 preceeding 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 preceeding
 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 (ends_line(af.list[m[j].a+k-1])) {
 229                                                 if (firstk > m[j].al)
 230                                                         firstk = k;
 231                                                 newlines++;
 232                                                 if (newlines >= 3) {
 233                                                         k = firstk;
 234                                                         break;
 235                                                 }
 236                                         }
 237                                 if (k > 0)
 238                                         m[j].hi = k;
 239                                 else if (j == 0)
 240                                         m[j].hi = firstk;
 241                                 else if (is_cutpoint(m[j], af,bf,cf))
 242                                         m[j].hi = 0;
 243                                 else
 244                                         /* no start-of-line found... */
 245                                         m[j].hi = -1;
 246                                 if (m[j].hi > 0 &&
 247                                     (m[j].type == Changed)) {
 248                                         /* this can only work if start is
 249                                          * also a line break */
 250                                         if (is_cutpoint(m[j], af,bf,cf))
 251                                                 /* ok */;
 252                                         else
 253                                                 m[j].hi = -1;
 254                                 }
 255                                 if (m[j].hi >= 0)
 256                                         break;
 257                                 m[j].in_conflict = m[i].in_conflict;
 258                         }
 259
 260                         /* now the forward search */
 261                         newlines = 0;
 262                         for (j = i+1; m[j].type != End; j++) {
 263                                 if (m[j].type == Extraneous &&
 264                                     bf.list[m[j].b].start[0] == '\0')
 265                                         /* hunk header - not conflict any more */
 266                                         break;
 267                                 if (m[j].type == Extraneous) {
 268                                         for (k = 0; k < m[j].bl; k++)
 269                                                 if (ends_line(bf.list[m[j].b+k]))
 270                                                         newlines++;
 271                                 }
 272                                 if (m[j].type != Unchanged &&
 273                                     m[j].type != Changed) {
 274                                         if (m[j].type == Conflict)
 275                                                 m[j].in_conflict = 2;
 276                                         else
 277                                                 m[j].in_conflict = m[i].in_conflict;
 278                                         continue;
 279                                 }
 280                                 m[j].in_conflict = 1;
 281                                 m[j].hi = m[j].al;
 282                                 if (words) {
 283                                         m[j].lo = 0;
 284                                         break;
 285                                 }
 286                                 /* need to find a line-break, which might be at
 287                                  * the very beginning, or might be after the
 288                                  * first newline - if there is one
 289                                  */
 290                                 if (is_cutpoint(m[j], af,bf,cf))
 291                                         m[j].lo = 0;
 292                                 else {
 293                                         /* If we find enough newlines in this section,
 294                                          * then we only really need 1, but would rather
 295                                          * it wasn't the first one.  'firstk' allows us
 296                                          * to track which newline we actually use
 297                                          */
 298                                         int firstk = -1;
 299                                         for (k = 0 ; k < m[j].al ; k++)
 300                                                 if (ends_line(af.list[m[j].a+k])) {
 301                                                         if (firstk < 0)
 302                                                                 firstk = k;
 303                                                         newlines++;
 304                                                         if (newlines >= 3) {
 305                                                                 k = firstk;
 306                                                                 break;
 307                                                         }
 308                                                 }
 309                                         if (newlines < 3 &&
 310                                             m[j+1].type  == End)
 311                                                 /* Hit end of file, pretend we found 3 newlines. */
 312                                                 k = firstk;
 313
 314                                         if (firstk >= 0 &&
 315                                             m[j+1].type == Unmatched) {
 316                                                 /* If this Unmatched exceeds 3 lines, just stop here */
 317                                                 int p;
 318                                                 int nl = 0;
 319                                                 for (p = 0; p < m[j+1].al ; p++)
 320                                                         if (ends_line(af.list[m[j+1].a+p])) {
 321                                                                 nl++;
 322                                                                 if (nl > 3)
 323                                                                         break;
 324                                                         }
 325                                                 if (nl > 3)
 326                                                         k = firstk;
 327                                         }
 328                                         if (k < m[j].al)
 329                                                 m[j].lo = k+1;
 330                                         else
 331                                                 /* no start-of-line found */
 332                                                 m[j].lo = m[j].al+1;
 333                                 }
 334                                 if (m[j].lo <= m[j].al+1 &&
 335                                     (m[j].type == Changed)) {
 336                                         /* this can only work if the end is a line break */
 337                                         if (is_cutpoint(m[j+1], af,bf,cf))
 338                                                 /* ok */;
 339                                         else
 340                                                 m[j].lo = m[j].al+1;
 341                                 }
 342                                 if (m[j].lo < m[j].al+1)
 343                                         break;
 344                                 m[j].in_conflict = m[i].in_conflict;
 345                         }
 346                         if (m[j-1].in_conflict == 1)
 347                                 i = j - 1;
 348                         else
 349                                 /* A hunk header bordered the conflict */
 350                                 i = j;
 351
 352                         /* If any of the merges are Changed or Conflict,
 353                          * then this really is a Conflict or Wiggle.
 354                          * If not they are just Unchanged, Unmatched,
 355                          * Extraneous or AlreadyApplied, and so don't
 356                          * really count.
 357                          * Note that the first/last merges (in_conflict==1)
 358                          * can be Changed and so much be check separately.
 359                          */
 360                         if (m[j].type == Changed)
 361                                 goto out;
 362                         for (j = i-1; j >= 0 && m[j].in_conflict > 1; j--)
 363                                 if (m[j].type == Changed || m[j].type == Conflict)
 364                                         goto out;
 365                         if (j >= 0 && m[j].type == Changed)
 366                                 goto out;
 367                         /* False alarm, no real conflict/wiggle here as
 368                          * nothing changed. */
 369                         if (j < 0)
 370                                 j = 0;
 371                         if (m[j].in_conflict == 1) {
 372                                 m[j].hi = m[j].al;
 373                                 if (m[j].lo == 0)
 374                                         m[j].in_conflict = 0;
 375                                 j++;
 376                         }
 377                         while (j <= i)
 378                                 m[j++].in_conflict = 0;
 379                 out:
 380                         if (m[i].type == End)
 381                                 break;
 382                 }
 383                 for (k = 1; k < m[i].al; k++)
 384                         if (words || ends_line(af.list[m[i].a+k])) {
 385                                 if (unmatched)
 386                                         unmatched--;
 387                                 if (changed)
 388                                         changed--;
 389                                 if (extraneous)
 390                                         extraneous--;
 391                         }
 392         }
 393         if (!show_wiggles)
 394                 *wigglesp = wiggles;
 395         /* Now count the conflicts and wiggles */
 396         for (i = 0; m[i].type != End; i++) {
 397                 int true_conflict = 0;
 398                 if (!m[i].in_conflict)
 399                         continue;
 400
 401                 for (j = i; m[j].type != End && m[j].in_conflict; j++) {
 402                         if (m[j].in_conflict == 2)
 403                                 true_conflict = 1;
 404                         if (j > i &&
 405                             m[j].in_conflict == 1) {
 406                                 /* end of region */
 407                                 if (!m[j+1].in_conflict)
 408                                         j++;
 409                                 break;
 410                         }
 411                 }
 412                 if (true_conflict)
 413                         cnt++;
 414                 else
 415                         wiggles++;
 416                 i = j-1;
 417         }
 418         if (show_wiggles)
 419                 *wigglesp = wiggles;
 420         return cnt;
 421 }
 422
 423 struct ci make_merger(struct file af, struct file bf, struct file cf,
 424                       struct csl *csl1, struct csl *csl2, int words,
 425                       int ignore_already, int show_wiggles)
 426 {
 427         /* find the wiggles and conflicts between csl1 and csl2
 428          */
 429         struct ci rv;
 430         int i, l;
 431         int a, b, c, c1, c2;
 432         int header_checked = -1;
 433         int header_found = 0;
 434
 435         rv.conflicts = rv.wiggles = rv.ignored = 0;
 436
 437         for (i = 0; csl1[i].len; i++)
 438                 ;
 439         l = i;
 440         for (i = 0; csl2[i].len; i++)
 441                 ;
 442         l += i;
 443         /* maybe a bit of slack at each end */
 444         l = l * 4 + 10;
 445
 446         rv.merger = xmalloc(sizeof(struct merge)*l);
 447
 448         a = b = c = c1 = c2 = 0;
 449         i = 0;
 450         while (1) {
 451                 int match1, match2;
 452                 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
 453                 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
 454
 455                 if (header_checked != c2) {
 456                         /* Check if there is a hunk header in this range */
 457                         int j;
 458                         header_found = -1;
 459                         for (j = b; j < csl2[c2].a + csl2[c2].len; j++)
 460                                 if (bf.list[j].start[0] == '\0') {
 461                                         header_found = j;
 462                                         break;
 463                                 }
 464                         header_checked = c2;
 465                 }
 466                 rv.merger[i].a = a;
 467                 rv.merger[i].b = b;
 468                 rv.merger[i].c = c;
 469                 rv.merger[i].c1 = c1;
 470                 rv.merger[i].c2 = c2;
 471                 rv.merger[i].in_conflict = 0;
 472
 473                 if (!match1 && match2) {
 474                         /* This is either Unmatched or Extraneous - probably both.
 475                          * If the match2 has a hunk-header Extraneous, it must
 476                          * align with an end-of-line in 'a', so adjust endpoint
 477                          */
 478                         int newa = csl1[c1].a;
 479                         if (header_found >= 0) {
 480                                 while (newa > a &&
 481                                        !ends_line(af.list[newa-1]))
 482                                         newa--;
 483                         }
 484                         if (a == newa && b == csl1[c1].b)
 485                                 newa = csl1[c1].a;
 486                         if (a < newa) {
 487                                 /* some unmatched text */
 488                                 rv.merger[i].type = Unmatched;
 489                                 rv.merger[i].al = newa - a;
 490                                 rv.merger[i].bl = 0;
 491                                 rv.merger[i].cl = 0;
 492                         } else {
 493                                 int newb;
 494                                 assert(b < csl1[c1].b);
 495                                 /* some Extraneous text */
 496                                 /* length is min of unmatched on left
 497                                  * and matched on right.
 498                                  * However a hunk-header must be an
 499                                  * Extraneous section by itself, so if this
 500                                  * start with one, the length is 1, and if
 501                                  * there is one in the middle, only take the
 502                                  * text up to there for now.
 503                                  */
 504                                 rv.merger[i].type = Extraneous;
 505                                 rv.merger[i].al = 0;
 506                                 newb = b +
 507                                         min(csl1[c1].b - b,
 508                                             csl2[c2].len - (b-csl2[c2].a));
 509                                 if (header_found == b) {
 510                                         newb = b + 1;
 511                                         header_checked = -1;
 512                                 } else if (header_found > b && header_found < newb) {
 513                                         newb = header_found;
 514                                         header_checked = -1;
 515                                 }
 516                                 assert(newb > b);
 517                                 rv.merger[i].cl =
 518                                         rv.merger[i].bl = newb - b;
 519                         }
 520                 } else if (match1 && !match2) {
 521                         /* some changed text
 522                          * if 'c' is currently at a suitable cut-point, then
 523                          * we can look for a triple-cut-point for start.
 524                          * Also, if csl2[c2].b isn't in a conflict, and is
 525                          * a suitable cut-point, then we could make a
 526                          * triple-cut-point for end of a conflict.
 527                          */
 528
 529                         rv.merger[i].type = Changed;
 530                         rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
 531                         rv.merger[i].al = rv.merger[i].bl;
 532                         rv.merger[i].cl = csl2[c2].b - c;
 533                 } else if (match1 && match2) {
 534                         /* Some unchanged text
 535                          */
 536                         rv.merger[i].type = Unchanged;
 537                         rv.merger[i].bl =
 538                                 min(csl1[c1].len - (b-csl1[c1].b),
 539                                     csl2[c2].len - (b-csl2[c2].a));
 540                         rv.merger[i].al = rv.merger[i].cl =
 541                                 rv.merger[i].bl;
 542                 } else {
 543                         /* must be a conflict.
 544                          * Move a and c to next match, and b to closest of the two
 545                          */
 546                         rv.merger[i].type = Conflict;
 547                         rv.merger[i].al = csl1[c1].a - a;
 548                         rv.merger[i].cl = csl2[c2].b - c;
 549                         rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
 550                         if (ignore_already &&
 551                             check_alreadyapplied(af, cf, &rv.merger[i]))
 552                                 rv.ignored++;
 553                         else if (rv.merger[i].bl == 0 &&
 554                                  rv.merger[i].cl > 0)
 555                                 /* As the 'before' stream is empty, this
 556                                  * could look like Unmatched in the
 557                                  * original, and an insertion in the
 558                                  * diff.  Reporting it like that is
 559                                  * probably more useful that as a full
 560                                  * conflict.
 561                                  * Leave the type for the insertion as
 562                                  * Conflict (not Changed) as there is some
 563                                  * real uncertainty here, but allow the
 564                                  * original to become Unmatched.
 565                                  */
 566                                 rv.merger[i].al = 0;
 567                 }
 568                 rv.merger[i].oldtype = rv.merger[i].type;
 569                 a += rv.merger[i].al;
 570                 b += rv.merger[i].bl;
 571                 c += rv.merger[i].cl;
 572                 i++;
 573
 574                 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
 575                         c1++;
 576                 assert(csl1[c1].b + csl1[c1].len >= b);
 577                 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
 578                         c2++;
 579                 assert(csl2[c2].a + csl2[c2].len >= b);
 580                 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
 581                     a == csl1[c1].a && b == csl1[c1].b &&
 582                     b == csl2[c2].a && c == csl2[c2].b)
 583                         break;
 584         }
 585         rv.merger[i].type = End;
 586         rv.merger[i].oldtype = End;
 587         rv.merger[i].a = a;
 588         rv.merger[i].b = b;
 589         rv.merger[i].c = c;
 590         rv.merger[i].c1 = c1;
 591         rv.merger[i].c2 = c2;
 592         rv.merger[i].in_conflict = 0;
 593         assert(i < l);
 594
 595         /* Now revert any AlreadyApplied that aren't bounded by
 596          * Unchanged or Changed.
 597          */
 598         for (i = 0; rv.merger[i].type != End; i++) {
 599                 if (rv.merger[i].type != AlreadyApplied)
 600                         continue;
 601                 if (i > 0 && rv.merger[i-1].type != Unchanged &&
 602                     rv.merger[i-1].type != Changed)
 603                         rv.merger[i].type = Conflict;
 604                 if (rv.merger[i+1].type != Unchanged &&
 605                     rv.merger[i+1].type != Changed &&
 606                     rv.merger[i+1].type != End)
 607                         rv.merger[i].type = Conflict;
 608         }
 609         rv.conflicts = isolate_conflicts(af, bf, cf, csl1, csl2, words,
 610                                          rv.merger, show_wiggles, &rv.wiggles);
 611         return rv;
 612 }
 613
 614 static int printrange(FILE *out, struct file *f, int start, int len,
 615                       int offset)
 616 {
 617         int lines = 0;
 618         while (len > 0) {
 619                 struct elmnt e = f->list[start];
 620                 printword(out, e);
 621                 if (e.start[e.plen-1] == '\n' &&
 622                     offset > 0)
 623                         lines++;
 624                 offset--;
 625                 start++;
 626                 len--;
 627         }
 628         return lines;
 629 }
 630
 631 int print_merge(FILE *out, struct file *a, struct file *b, struct file *c,
 632                 int words, struct merge *merger,
 633                 struct merge *mpos, int streampos, int offsetpos)
 634 {
 635         struct merge *m;
 636         int lineno = 1;
 637         int rv = 0;
 638         int offset = INT_MAX;
 639
 640         for (m = merger; m->type != End ; m++) {
 641                 struct merge *cm;
 642                 if (do_trace)
 643                         printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
 644                                m->type==Unmatched ? "Unmatched" :
 645                                m->type==Unchanged ? "Unchanged" :
 646                                m->type==Extraneous ? "Extraneous" :
 647                                m->type==Changed ? "Changed" :
 648                                m->type==AlreadyApplied ? "AlreadyApplied" :
 649                                m->type==Conflict ? "Conflict":"unknown",
 650                                m->a, m->a+m->al-1,
 651                                m->b, m->b+m->bl-1,
 652                                m->c, m->c+m->cl-1,
 653                                m->in_conflict ? " in_conflict" : "",
 654                                m->lo, m->hi);
 655
 656                 while (m->in_conflict) {
 657                         /* need to print from 'hi' to 'lo' of next
 658                          * Unchanged which is < it's hi
 659                          */
 660                         int found_conflict = 0;
 661                         int st = 0, st1;
 662                         if (m->in_conflict == 1)
 663                                 st = m->hi;
 664                         st1 = st;
 665
 666                         if (m == mpos)
 667                                 offset = offsetpos;
 668                         if (m->in_conflict == 1 && m->type == Unchanged)
 669                                 lineno += printrange(out, a, m->a+m->lo, m->hi - m->lo, offset - m->lo);
 670
 671                         if (m == mpos)
 672                                 rv = lineno;
 673                         if (do_trace)
 674                                 for (cm = m; cm->in_conflict; cm++) {
 675                                         printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}\n",
 676                                                cm->type==Unmatched?"Unmatched":
 677                                                cm->type==Unchanged?"Unchanged":
 678                                                cm->type==Extraneous?"Extraneous":
 679                                                cm->type==Changed?"Changed":
 680                                                cm->type==AlreadyApplied?"AlreadyApplied":
 681                                                cm->type==Conflict?"Conflict":"unknown",
 682                                                cm->a, cm->a+cm->al-1,
 683                                                cm->b, cm->b+cm->bl-1,
 684                                                cm->c, cm->c+cm->cl-1,
 685                                                cm->in_conflict ? " in_conflict" : "",
 686                                                cm->lo, cm->hi);
 687                                         if (cm->in_conflict == 1 && cm != m)
 688                                                 break;
 689                                 }
 690
 691                         if (m->in_conflict == 1 &&
 692                             m[1].in_conflict == 1) {
 693                                 /* Nothing between two conflicts */
 694                                 m++;
 695                                 continue;
 696                         }
 697
 698                         fputs(words ? "<<<---" : "<<<<<<< found\n", out);
 699                         if (!words)
 700                                 lineno++;
 701                         for (cm = m; cm->in_conflict; cm++) {
 702                                 if (cm == mpos && streampos == 0)
 703                                         offset = offsetpos;
 704                                 if (cm->type == Conflict)
 705                                         found_conflict = 1;
 706                                 if (cm->in_conflict == 1 && cm != m) {
 707                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 708                                         break;
 709                                 }
 710                                 lineno += printrange(out, a, cm->a+st1, cm->al-st1, offset-st1);
 711                                 st1 = 0;
 712                                 if (cm == mpos && streampos == 0)
 713                                         rv = lineno;
 714                         }
 715                         if (cm == mpos && streampos == 0)
 716                                 rv = lineno;
 717                         fputs(words ? "|||" : "||||||| expected\n", out);
 718                         if (!words)
 719                                 lineno++;
 720                         st1 = st;
 721                         for (cm = m; cm->in_conflict; cm++) {
 722                                 if (cm == mpos && streampos == 1)
 723                                         offset = offsetpos;
 724                                 if (cm->in_conflict == 1 && cm != m) {
 725                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 726                                         break;
 727                                 }
 728                                 lineno += printrange(out, b, cm->b+st1, cm->bl-st1, offset-st1);
 729                                 st1 = 0;
 730                                 if (cm == mpos && streampos == 1)
 731                                         rv = lineno;
 732                         }
 733                         if (cm == mpos && streampos == 1)
 734                                 rv = lineno;
 735                         fputs(words ? "===" : "=======\n", out);
 736                         if (!words)
 737                                 lineno++;
 738                         st1 = st;
 739                         for (cm = m; cm->in_conflict; cm++) {
 740                                 if (cm == mpos && streampos == 2)
 741                                         offset = offsetpos;
 742                                 if (cm->in_conflict == 1 && cm != m) {
 743                                         if (cm->type == Unchanged)
 744                                                 lineno += printrange(out, a, cm->a, cm->lo, offset);
 745                                         else
 746                                                 lineno += printrange(out, c, cm->c, cm->cl, offset);
 747                                         break;
 748                                 }
 749                                 if (cm->type == Changed)
 750                                         st1 = 0; /* All of result of change must be printed */
 751                                 lineno += printrange(out, c, cm->c+st1, cm->cl-st1, offset-st1);
 752                                 st1 = 0;
 753                                 if (cm == mpos && streampos == 2)
 754                                         rv = lineno;
 755                         }
 756                         if (cm == mpos && streampos == 2)
 757                                 rv = lineno;
 758                         if (!found_conflict) {
 759                                 /* This section was wiggled in successfully,
 760                                  * but full conflict display was requested.
 761                                  * So now print out the wiggled result as well.
 762                                  */
 763                                 fputs(words ? "&&&" : "&&&&&&& resolution\n", out);
 764                                 if (!words)
 765                                         lineno++;
 766                                 st1 = st;
 767                                 for (cm = m; cm->in_conflict; cm++) {
 768                                         int last = 0;
 769                                         if (cm->in_conflict == 1 && cm != m)
 770                                                 last = 1;
 771                                         switch (cm->type) {
 772                                         case Unchanged:
 773                                         case AlreadyApplied:
 774                                         case Unmatched:
 775                                                 lineno += printrange(out, a, cm->a+st1,
 776                                                                      last ? cm->lo : cm->al-st1, offset-st1);
 777                                                 break;
 778                                         case Extraneous:
 779                                                 break;
 780                                         case Changed:
 781                                                 lineno += printrange(out, c, cm->c,
 782                                                                      last ? cm->lo : cm->cl, offset);
 783                                                 break;
 784                                         case Conflict:
 785                                         case End:
 786                                                 assert(0);
 787                                         }
 788                                         if (last)
 789                                                 break;
 790                                         st1 = 0;
 791                                 }
 792                         }
 793                         fputs(words ? "--->>>" : ">>>>>>> replacement\n", out);
 794                         if (!words)
 795                                 lineno++;
 796                         m = cm;
 797                         if (m->in_conflict == 1 && m[1].in_conflict == 0) {
 798                                 /* End of a conflict, no conflict follows */
 799                                 if (m == mpos)
 800                                         offset = offsetpos;
 801                                 if (m->type == Unchanged)
 802                                         lineno += printrange(out, a, m->a+m->lo, m->hi-m->lo, offset-m->lo);
 803                                 if (m == mpos)
 804                                         rv = lineno;
 805                                 m++;
 806                         }
 807                 }
 808
 809                 /* there is always some non-conflict after a conflict,
 810                  * unless we hit the end
 811                  */
 812                 if (m->type == End)
 813                         break;
 814
 815                 if (do_trace) {
 816                         printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
 817                                m->type==Unmatched?"Unmatched":
 818                                m->type==Unchanged?"Unchanged":
 819                                m->type==Extraneous?"Extraneous":
 820                                m->type==Changed?"Changed":
 821                                m->type==AlreadyApplied?"AlreadyApplied":
 822                                m->type==Conflict?"Conflict":"unknown",
 823                                m->a, m->a+m->al-1,
 824                                m->b, m->b+m->bl-1,
 825                                m->c, m->c+m->cl-1,
 826                                m->in_conflict ? " in_conflict" : "",
 827                                m->lo, m->hi);
 828                 }
 829                 if (m == mpos)
 830                         offset = offsetpos;
 831
 832                 switch (m->type) {
 833                 case Unchanged:
 834                 case AlreadyApplied:
 835                 case Unmatched:
 836                         lineno += printrange(out, a, m->a, m->al, offset);
 837                         break;
 838                 case Extraneous:
 839                         break;
 840                 case Changed:
 841                         lineno += printrange(out, c, m->c, m->cl, offset);
 842                         break;
 843                 case Conflict:
 844                 case End:
 845                         assert(0);
 846                 }
 847                 if (m == mpos)
 848                         rv = lineno;
 849         }
 850         return rv;
 851 }
 852
 853 int save_merge(struct file a, struct file b, struct file c,
 854                struct merge *merger, char *file, int backup)
 855 {
 856         char *replacename = xmalloc(strlen(file) + 20);
 857         char *orignew = xmalloc(strlen(file) + 20);
 858         int fd;
 859         FILE *outfile;
 860         int err = 0;
 861         int lineno = 0;
 862         strcpy(replacename, file);
 863         strcat(replacename, "XXXXXX");
 864         strcpy(orignew, file);
 865         strcat(orignew, ".porig");
 866
 867         fd = mkstemp(replacename);
 868         if (fd < 0) {
 869                 err = -1;
 870                 goto out;
 871         }
 872         outfile = fdopen(fd, "w");
 873         lineno = print_merge(outfile, &a, &b, &c, 0, merger,
 874                              NULL, 0, 0);
 875         fclose(outfile);
 876         if (backup && rename(file, orignew) != 0)
 877                 err = -2;
 878         else if (rename(replacename, file) != 0)
 879                 err = -2;
 880
 881 out:
 882         free(replacename);
 883         free(orignew);
 884         return err < 0 ? err : lineno;
 885 }
 886
 887 int save_tmp_merge(struct file a, struct file b, struct file c,
 888                    struct merge *merger, char **filep,
 889                    struct merge *mpos, int streampos, int offsetpos)
 890 {
 891         int fd;
 892         FILE *outfile;
 893         char *dir, *fname;
 894         int lineno;
 895         int suffix = 0;
 896
 897         if (!*filep) {
 898                 dir = getenv("TMPDIR");
 899                 if (!dir)
 900                         dir = "/tmp";
 901
 902                 asprintf(&fname, "%s/wiggle-tmp-XXXXXX", dir);
 903         } else {
 904                 char *base;
 905                 dir = *filep;
 906                 base = strrchr(dir, '/');
 907                 if (base)
 908                         base++;
 909                 else
 910                         base = dir;
 911                 asprintf(&fname, "%.*stmp-XXXXXX-%s", (int)(base-dir), dir, base);
 912                 suffix = strlen(base)+1;
 913         }
 914         fd = mkstemps(fname, suffix);
 915
 916         if (fd < 0) {
 917                 free(fname);
 918                 *filep = NULL;
 919                 return -1;
 920         }
 921         outfile = fdopen(fd, "w");
 922         lineno = print_merge(outfile, &a, &b, &c, 0, merger,
 923                              mpos, streampos, offsetpos);
 924         fclose(outfile);
 925         *filep = fname;
 926         return lineno;
 927 }