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  * Copyright (C) 2014-2020 Neil Brown <neil@brown.name>
   7  *
   8  *
   9  *    This program is free software; you can redistribute it and/or modify
  10  *    it under the terms of the GNU General Public License as published by
  11  *    the Free Software Foundation; either version 2 of the License, or
  12  *    (at your option) any later version.
  13  *
  14  *    This program is distributed in the hope that it will be useful,
  15  *    but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  *    GNU General Public License for more details.
  18  *
  19  *    You should have received a copy of the GNU General Public License
  20  *    along with this program.
  21  *
  22  *    Author: Neil Brown
  23  *    Email: <neil@brown.name>
  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 (wiggle_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 preceding 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 wiggle_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 preceding 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 preceding
 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 (m[j].a + k >= af.elcnt)
 230                                                 /* FIXME impossible!*/
 231                                                 break;
 232                                         if (ends_line(af.list[m[j].a+k-1])) {
 233                                                 if (firstk > m[j].al)
 234                                                         firstk = k;
 235                                                 newlines++;
 236                                                 if (newlines >= 3) {
 237                                                         k = firstk;
 238                                                         break;
 239                                                 }
 240                                         }
 241                                 }
 242                                 if (k > 0)
 243                                         m[j].hi = k;
 244                                 else if (j == 0)
 245                                         m[j].hi = firstk;
 246                                 else if (is_cutpoint(m[j], af,bf,cf))
 247                                         m[j].hi = 0;
 248                                 else
 249                                         /* no start-of-line found... */
 250                                         m[j].hi = -1;
 251                                 if (m[j].hi > 0 &&
 252                                     (m[j].type == Changed)) {
 253                                         /* this can only work if start is
 254                                          * also a line break */
 255                                         if (is_cutpoint(m[j], af,bf,cf))
 256                                                 /* ok */;
 257                                         else
 258                                                 m[j].hi = -1;
 259                                 }
 260                                 if (m[j].hi >= 0)
 261                                         break;
 262                                 m[j].in_conflict = m[i].in_conflict;
 263                         }
 264
 265                         /* now the forward search */
 266                         newlines = 0;
 267                         for (j = i+1; m[j].type != End; j++) {
 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 (m[i].a + k >= af.elcnt)
 386                                 /* FIXME this should be impossible, but
 387                                  * it happened.
 388                                  */
 389                                 break;
 390                         if (words || ends_line(af.list[m[i].a+k])) {
 391                                 if (unmatched)
 392                                         unmatched--;
 393                                 if (changed)
 394                                         changed--;
 395                                 if (extraneous)
 396                                         extraneous--;
 397                         }
 398                 }
 399         }
 400         if (!show_wiggles)
 401                 *wigglesp = wiggles;
 402         /* Now count the conflicts and wiggles */
 403         for (i = 0; m[i].type != End; i++) {
 404                 int true_conflict = 0;
 405                 if (!m[i].in_conflict)
 406                         continue;
 407
 408                 for (j = i; m[j].type != End && m[j].in_conflict; j++) {
 409                         if (m[j].in_conflict == 2)
 410                                 true_conflict = 1;
 411                         if (j > i &&
 412                             m[j].in_conflict == 1) {
 413                                 /* end of region */
 414                                 if (!m[j+1].in_conflict)
 415                                         j++;
 416                                 break;
 417                         }
 418                 }
 419                 if (true_conflict)
 420                         cnt++;
 421                 else
 422                         wiggles++;
 423                 i = j-1;
 424         }
 425         if (show_wiggles)
 426                 *wigglesp = wiggles;
 427         return cnt;
 428 }
 429
 430 struct ci wiggle_make_merger(struct file af, struct file bf, struct file cf,
 431                              struct csl *csl1, struct csl *csl2, int words,
 432                              int ignore_already, int show_wiggles)
 433 {
 434         /* find the wiggles and conflicts between csl1 and csl2
 435          */
 436         struct ci rv;
 437         int i, l;
 438         int a, b, c, c1, c2;
 439         int header_checked = -1;
 440         int header_found = 0;
 441
 442         rv.conflicts = rv.wiggles = rv.ignored = 0;
 443
 444         for (i = 0; csl1[i].len; i++)
 445                 ;
 446         l = i;
 447         for (i = 0; csl2[i].len; i++)
 448                 ;
 449         l += i;
 450         /* maybe a bit of slack at each end */
 451         l = l * 4 + 10;
 452
 453         rv.merger = wiggle_xmalloc(sizeof(struct merge)*l);
 454
 455         a = b = c = c1 = c2 = 0;
 456         i = 0;
 457         while (1) {
 458                 int match1, match2;
 459                 match1 = (a >= csl1[c1].a && b >= csl1[c1].b); /* c1 doesn't match */
 460                 match2 = (b >= csl2[c2].a && c >= csl2[c2].b);
 461
 462                 if (header_checked != c2) {
 463                         /* Check if there is a hunk header in this range */
 464                         int j;
 465                         header_found = -1;
 466                         for (j = b; j < csl2[c2].a + csl2[c2].len; j++)
 467                                 if (bf.list[j].start[0] == '\0') {
 468                                         header_found = j;
 469                                         break;
 470                                 }
 471                         header_checked = c2;
 472                 }
 473                 rv.merger[i].a = a;
 474                 rv.merger[i].b = b;
 475                 rv.merger[i].c = c;
 476                 rv.merger[i].c1 = c1;
 477                 rv.merger[i].c2 = c2;
 478                 rv.merger[i].in_conflict = 0;
 479
 480                 if (!match1 && match2) {
 481                         /* This is either Unmatched or Extraneous - probably both.
 482                          * If the match2 has a hunk-header Extraneous, it must
 483                          * align with an end-of-line in 'a', so adjust endpoint
 484                          */
 485                         int newa = csl1[c1].a;
 486                         if (header_found >= 0) {
 487                                 while (newa > a &&
 488                                        !ends_line(af.list[newa-1]))
 489                                         newa--;
 490                         }
 491                         if (a == newa && b == csl1[c1].b)
 492                                 newa = csl1[c1].a;
 493                         if (a < newa) {
 494                                 /* some unmatched text */
 495                                 rv.merger[i].type = Unmatched;
 496                                 rv.merger[i].al = newa - a;
 497                                 rv.merger[i].bl = 0;
 498                                 rv.merger[i].cl = 0;
 499                         } else {
 500                                 int newb;
 501                                 assert(b < csl1[c1].b);
 502                                 /* some Extraneous text */
 503                                 /* length is min of unmatched on left
 504                                  * and matched on right.
 505                                  * However a hunk-header must be an
 506                                  * Extraneous section by itself, so if this
 507                                  * start with one, the length is 1, and if
 508                                  * there is one in the middle, only take the
 509                                  * text up to there for now.
 510                                  */
 511                                 rv.merger[i].type = Extraneous;
 512                                 rv.merger[i].al = 0;
 513                                 newb = b +
 514                                         min(csl1[c1].b - b,
 515                                             csl2[c2].len - (b-csl2[c2].a));
 516                                 if (header_found == b) {
 517                                         newb = b + 1;
 518                                         header_checked = -1;
 519                                 } else if (header_found > b && header_found < newb) {
 520                                         newb = header_found;
 521                                         header_checked = -1;
 522                                 }
 523                                 assert(newb > b);
 524                                 rv.merger[i].cl =
 525                                         rv.merger[i].bl = newb - b;
 526                         }
 527                 } else if (match1 && !match2) {
 528                         /* some changed text
 529                          * if 'c' is currently at a suitable cut-point, then
 530                          * we can look for a triple-cut-point for start.
 531                          * Also, if csl2[c2].b isn't in a conflict, and is
 532                          * a suitable cut-point, then we could make a
 533                          * triple-cut-point for end of a conflict.
 534                          */
 535
 536                         rv.merger[i].type = Changed;
 537                         rv.merger[i].bl = min(csl1[c1].b+csl1[c1].len, csl2[c2].a) - b;
 538                         rv.merger[i].al = rv.merger[i].bl;
 539                         rv.merger[i].cl = csl2[c2].b - c;
 540                 } else if (match1 && match2) {
 541                         /* Some unchanged text
 542                          */
 543                         rv.merger[i].type = Unchanged;
 544                         rv.merger[i].bl =
 545                                 min(csl1[c1].len - (b-csl1[c1].b),
 546                                     csl2[c2].len - (b-csl2[c2].a));
 547                         rv.merger[i].al = rv.merger[i].cl =
 548                                 rv.merger[i].bl;
 549                 } else {
 550                         /* must be a conflict.
 551                          * Move a and c to next match, and b to closest of the two
 552                          */
 553                         rv.merger[i].type = Conflict;
 554                         rv.merger[i].al = csl1[c1].a - a;
 555                         rv.merger[i].cl = csl2[c2].b - c;
 556                         rv.merger[i].bl = min(csl1[c1].b, csl2[c2].a) - b;
 557                         if (ignore_already &&
 558                             check_alreadyapplied(af, cf, &rv.merger[i]))
 559                                 rv.ignored++;
 560                         else if (rv.merger[i].bl == 0 &&
 561                                  rv.merger[i].cl > 0)
 562                                 /* As the 'before' stream is empty, this
 563                                  * could look like Unmatched in the
 564                                  * original, and an insertion in the
 565                                  * diff.  Reporting it like that is
 566                                  * probably more useful that as a full
 567                                  * conflict.
 568                                  * Leave the type for the insertion as
 569                                  * Conflict (not Changed) as there is some
 570                                  * real uncertainty here, but allow the
 571                                  * original to become Unmatched.
 572                                  */
 573                                 rv.merger[i].al = 0;
 574                 }
 575                 rv.merger[i].oldtype = rv.merger[i].type;
 576                 a += rv.merger[i].al;
 577                 b += rv.merger[i].bl;
 578                 c += rv.merger[i].cl;
 579                 i++;
 580
 581                 while (csl1[c1].a + csl1[c1].len <= a && csl1[c1].len)
 582                         c1++;
 583                 assert(csl1[c1].b + csl1[c1].len >= b);
 584                 while (csl2[c2].b + csl2[c2].len <= c && csl2[c2].len)
 585                         c2++;
 586                 assert(csl2[c2].a + csl2[c2].len >= b);
 587                 if (csl1[c1].len == 0 && csl2[c2].len == 0 &&
 588                     a == csl1[c1].a && b == csl1[c1].b &&
 589                     b == csl2[c2].a && c == csl2[c2].b)
 590                         break;
 591         }
 592         rv.merger[i].type = End;
 593         rv.merger[i].oldtype = End;
 594         rv.merger[i].a = a;
 595         rv.merger[i].b = b;
 596         rv.merger[i].c = c;
 597         rv.merger[i].c1 = c1;
 598         rv.merger[i].c2 = c2;
 599         rv.merger[i].in_conflict = 0;
 600         assert(i < l);
 601
 602         /* Now revert any AlreadyApplied that aren't bounded by
 603          * Unchanged or Changed.
 604          */
 605         for (i = 0; rv.merger[i].type != End; i++) {
 606                 if (rv.merger[i].type != AlreadyApplied)
 607                         continue;
 608                 if (i > 0 && rv.merger[i-1].type != Unchanged &&
 609                     rv.merger[i-1].type != Changed)
 610                         rv.merger[i].type = Conflict;
 611                 if (rv.merger[i+1].type != Unchanged &&
 612                     rv.merger[i+1].type != Changed &&
 613                     rv.merger[i+1].type != End)
 614                         rv.merger[i].type = Conflict;
 615         }
 616         rv.conflicts = wiggle_isolate_conflicts(af, bf, cf, csl1, csl2, words,
 617                                                 rv.merger, show_wiggles, &rv.wiggles);
 618         return rv;
 619 }
 620
 621 static int printrange(FILE *out, struct file *f, int start, int len,
 622                       int offset)
 623 {
 624         int lines = 0;
 625         while (len > 0 && start < f->elcnt) {
 626                 struct elmnt e = f->list[start];
 627                 wiggle_printword(out, e);
 628                 if (e.start[e.plen-1] == '\n' &&
 629                     offset > 0)
 630                         lines++;
 631                 offset--;
 632                 start++;
 633                 len--;
 634         }
 635         return lines;
 636 }
 637
 638 static const char *conflict_types[] = {
 639         "", " border"," conflict"," wiggle" };
 640
 641 int wiggle_print_merge(FILE *out, struct file *a, struct file *b, struct file *c,
 642                        int words, struct merge *merger,
 643                        struct merge *mpos, int streampos, int offsetpos)
 644 {
 645         struct merge *m;
 646         int lineno = 1;
 647         int rv = 0;
 648         int offset = INT_MAX;
 649         int first_matched;
 650
 651         for (m = merger; m->type != End ; m++) {
 652                 struct merge *cm;
 653                 if (wiggle_do_trace)
 654                         printf("[%s: %d-%d,%d-%d,%d-%d%s(%d,%d)]\n",
 655                                m->type==Unmatched ? "Unmatched" :
 656                                m->type==Unchanged ? "Unchanged" :
 657                                m->type==Extraneous ? "Extraneous" :
 658                                m->type==Changed ? "Changed" :
 659                                m->type==AlreadyApplied ? "AlreadyApplied" :
 660                                m->type==Conflict ? "Conflict":"unknown",
 661                                m->a, m->a+m->al-1,
 662                                m->b, m->b+m->bl-1,
 663                                m->c, m->c+m->cl-1,
 664                                conflict_types[m->in_conflict],
 665                                m->lo, m->hi);
 666
 667                 while (m->in_conflict) {
 668                         /* need to print from 'hi' to 'lo' of next
 669                          * Unchanged which is < it's hi
 670                          */
 671                         int found_conflict = 0;
 672                         int st = 0, st1;
 673                         if (m->in_conflict == 1)
 674                                 st = m->hi;
 675                         st1 = st;
 676
 677                         if (m == mpos)
 678                                 offset = offsetpos;
 679                         if (m->in_conflict == 1 && m->type == Unchanged)
 680                                 lineno += printrange(out, a, m->a+m->lo, m->hi - m->lo, offset - m->lo);
 681
 682                         if (m == mpos)
 683                                 rv = lineno;
 684                         if (wiggle_do_trace)
 685                                 for (cm = m; cm->in_conflict; cm++) {
 686                                         printf("{%s: %d-%d,%d-%d,%d-%d%s(%d,%d)}%s\n",
 687                                                cm->type==Unmatched?"Unmatched":
 688                                                cm->type==Unchanged?"Unchanged":
 689                                                cm->type==Extraneous?"Extraneous":
 690                                                cm->type==Changed?"Changed":
 691                                                cm->type==AlreadyApplied?"AlreadyApplied":
 692                                                cm->type==Conflict?"Conflict":"unknown",
 693                                                cm->a, cm->a+cm->al-1,
 694                                                cm->b, cm->b+cm->bl-1,
 695                                                cm->c, cm->c+cm->cl-1,
 696                                                conflict_types[m->in_conflict],
 697                                                cm->lo, cm->hi,
 698                                                (cm->type == Extraneous &&
 699                                                 b->list[cm->b].start[0] == '\0') ?
 700                                                b->list[cm->b].start+1: ""
 701                                         );
 702                                         if (cm->in_conflict == 1 && cm != m)
 703                                                 break;
 704                                 }
 705
 706                         if (m->in_conflict == 1 &&
 707                             m[1].in_conflict == 1) {
 708                                 /* Nothing between two conflicts */
 709                                 m++;
 710                                 continue;
 711                         }
 712
 713                         fputs(words ? "<<<---" : "<<<<<<< found\n", out);
 714                         if (!words)
 715                                 lineno++;
 716                         for (cm = m; cm->in_conflict; cm++) {
 717                                 if (cm == mpos && streampos == 0)
 718                                         offset = offsetpos;
 719                                 if (cm->type == Conflict)
 720                                         found_conflict = 1;
 721                                 if (cm->in_conflict == 1 && cm != m) {
 722                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 723                                         break;
 724                                 }
 725                                 lineno += printrange(out, a, cm->a+st1, cm->al-st1, offset-st1);
 726                                 st1 = 0;
 727                                 if (cm == mpos && streampos == 0)
 728                                         rv = lineno;
 729                         }
 730                         if (cm == mpos && streampos == 0)
 731                                 rv = lineno;
 732                 restart:
 733                         fputs(words ? "|||" : "||||||| expected\n", out);
 734                         if (!words)
 735                                 lineno++;
 736                         st1 = st;
 737                         first_matched = 1;
 738                         for (cm = m; cm->in_conflict; cm++) {
 739                                 if (cm->type == Extraneous &&
 740                                     b->list[cm->b].start[0] == '\0') {
 741                                         /* This is a hunk header, skip it and possibly
 742                                          * abort this section
 743                                          */
 744                                         if (first_matched)
 745                                                 continue;
 746                                         break;
 747                                 }
 748                                 if (cm->type != Unchanged && cm->type != Unmatched)
 749                                         first_matched = 0;
 750                                 if (cm == mpos && streampos == 1)
 751                                         offset = offsetpos;
 752                                 if (cm->in_conflict == 1 && cm != m) {
 753                                         lineno += printrange(out, a, cm->a, cm->lo, offset);
 754                                         break;
 755                                 }
 756                                 lineno += printrange(out, b, cm->b+st1, cm->bl-st1, offset-st1);
 757                                 st1 = 0;
 758                                 if (cm == mpos && streampos == 1)
 759                                         rv = lineno;
 760                         }
 761                         if (cm == mpos && streampos == 1)
 762                                 rv = lineno;
 763                         fputs(words ? "===" : "=======\n", out);
 764                         if (!words)
 765                                 lineno++;
 766                         st1 = st;
 767                         first_matched = 1;
 768                         for (cm = m; cm->in_conflict; cm++) {
 769                                 if (cm->type == Extraneous &&
 770                                     b->list[cm->b].start[0] == '\0') {
 771                                         /* This is a hunk header, skip it and possibly
 772                                          * abort this section and restart.
 773                                          */
 774                                         if (first_matched)
 775                                                 continue;
 776                                         m = cm;
 777                                         /* If remaining merges are all
 778                                          * Extraneous, Unchanged, or Unmatched,
 779                                          * we don't need them.
 780                                          */
 781                                         while (cm->in_conflict > 1 &&
 782                                                (cm->type == Extraneous ||
 783                                                 cm->type == Unmatched ||
 784                                                 cm->type == Unchanged))
 785                                                 cm ++;
 786                                         if (!cm->in_conflict)
 787                                                 /* Nothing more to report */
 788                                                 break;
 789                                         if (cm->in_conflict == 1 &&
 790                                             (cm->type == Extraneous ||
 791                                              cm->type == Unmatched ||
 792                                              cm->type == Unchanged))
 793                                                 /* border between conflicts, but
 794                                                  * still nothing to report.
 795                                                  */
 796                                                 break;
 797                                         fputs(words ? ">>>" : ">>>>>>> replacement\n", out);
 798                                         fputs(words ? "<<<" : "<<<<<<< found\n", out);
 799                                         st = 0;
 800                                         goto restart;
 801                                 }
 802                                 if (cm->type != Unchanged && cm->type != Unmatched)
 803                                         first_matched = 0;
 804                                 if (cm == mpos && streampos == 2)
 805                                         offset = offsetpos;
 806                                 if (cm->in_conflict == 1 && cm != m) {
 807                                         if (cm->type == Unchanged)
 808                                                 lineno += printrange(out, a, cm->a, cm->lo, offset);
 809                                         else
 810                                                 lineno += printrange(out, c, cm->c, cm->cl, offset);
 811                                         break;
 812                                 }
 813                                 if (cm->type == Changed)
 814                                         st1 = 0; /* All of result of change must be printed */
 815                                 lineno += printrange(out, c, cm->c+st1, cm->cl-st1, offset-st1);
 816                                 st1 = 0;
 817                                 if (cm == mpos && streampos == 2)
 818                                         rv = lineno;
 819                         }
 820                         if (cm == mpos && streampos == 2)
 821                                 rv = lineno;
 822                         if (!found_conflict) {
 823                                 /* This section was wiggled in successfully,
 824                                  * but full conflict display was requested.
 825                                  * So now print out the wiggled result as well.
 826                                  */
 827                                 fputs(words ? "&&&" : "&&&&&&& resolution\n", out);
 828                                 if (!words)
 829                                         lineno++;
 830                                 st1 = st;
 831                                 for (cm = m; cm->in_conflict; cm++) {
 832                                         int last = 0;
 833                                         if (cm->in_conflict == 1 && cm != m)
 834                                                 last = 1;
 835                                         switch (cm->type) {
 836                                         case Unchanged:
 837                                         case AlreadyApplied:
 838                                         case Unmatched:
 839                                                 lineno += printrange(out, a, cm->a+st1,
 840                                                                      last ? cm->lo : cm->al-st1, offset-st1);
 841                                                 break;
 842                                         case Extraneous:
 843                                                 break;
 844                                         case Changed:
 845                                                 lineno += printrange(out, c, cm->c,
 846                                                                      last ? cm->lo : cm->cl, offset);
 847                                                 break;
 848                                         case Conflict:
 849                                         case End:
 850                                                 assert(0);
 851                                         }
 852                                         if (last)
 853                                                 break;
 854                                         st1 = 0;
 855                                 }
 856                         }
 857                         fputs(words ? "--->>>" : ">>>>>>> replacement\n", out);
 858                         if (!words)
 859                                 lineno++;
 860                         m = cm;
 861                         if (m->in_conflict == 1 && m[1].in_conflict == 0) {
 862                                 /* End of a conflict, no conflict follows */
 863                                 if (m == mpos)
 864                                         offset = offsetpos;
 865                                 if (m->type == Unchanged)
 866                                         lineno += printrange(out, a, m->a+m->lo, m->hi-m->lo, offset-m->lo);
 867                                 if (m == mpos)
 868                                         rv = lineno;
 869                                 m++;
 870                         }
 871                 }
 872
 873                 /* there is always some non-conflict after a conflict,
 874                  * unless we hit the end
 875                  */
 876                 if (m->type == End)
 877                         break;
 878
 879                 if (wiggle_do_trace) {
 880                         printf("<<%s: %d-%d,%d-%d,%d-%d%s(%d,%d)>>\n",
 881                                m->type==Unmatched?"Unmatched":
 882                                m->type==Unchanged?"Unchanged":
 883                                m->type==Extraneous?"Extraneous":
 884                                m->type==Changed?"Changed":
 885                                m->type==AlreadyApplied?"AlreadyApplied":
 886                                m->type==Conflict?"Conflict":"unknown",
 887                                m->a, m->a+m->al-1,
 888                                m->b, m->b+m->bl-1,
 889                                m->c, m->c+m->cl-1,
 890                                conflict_types[m->in_conflict],
 891                                m->lo, m->hi);
 892                 }
 893                 if (m == mpos)
 894                         offset = offsetpos;
 895
 896                 switch (m->type) {
 897                 case Unchanged:
 898                 case AlreadyApplied:
 899                 case Unmatched:
 900                         lineno += printrange(out, a, m->a, m->al, offset);
 901                         break;
 902                 case Extraneous:
 903                         break;
 904                 case Changed:
 905                         lineno += printrange(out, c, m->c, m->cl, offset);
 906                         break;
 907                 case Conflict:
 908                 case End:
 909                         assert(0);
 910                 }
 911                 if (m == mpos)
 912                         rv = lineno;
 913         }
 914         return rv;
 915 }