1170754Sdelphij/* Analyze file differences for GNU DIFF. 2170754Sdelphij 3170754Sdelphij Copyright (C) 1988, 1989, 1992, 1993, 1994, 1995, 1998, 2001, 2002, 4170754Sdelphij 2004 Free Software Foundation, Inc. 5170754Sdelphij 6170754Sdelphij This file is part of GNU DIFF. 7170754Sdelphij 8170754Sdelphij GNU DIFF is free software; you can redistribute it and/or modify 9170754Sdelphij it under the terms of the GNU General Public License as published by 10170754Sdelphij the Free Software Foundation; either version 2, or (at your option) 11170754Sdelphij any later version. 12170754Sdelphij 13170754Sdelphij GNU DIFF is distributed in the hope that it will be useful, 14170754Sdelphij but WITHOUT ANY WARRANTY; without even the implied warranty of 15170754Sdelphij MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16170754Sdelphij GNU General Public License for more details. 17170754Sdelphij 18170754Sdelphij You should have received a copy of the GNU General Public License 19170754Sdelphij along with this program; see the file COPYING. 20170754Sdelphij If not, write to the Free Software Foundation, 21170754Sdelphij 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ 22170754Sdelphij 23170754Sdelphij/* The basic algorithm is described in: 24170754Sdelphij "An O(ND) Difference Algorithm and its Variations", Eugene Myers, 25170754Sdelphij Algorithmica Vol. 1 No. 2, 1986, pp. 251-266; 26170754Sdelphij see especially section 4.2, which describes the variation used below. 27170754Sdelphij Unless the --minimal option is specified, this code uses the TOO_EXPENSIVE 28170754Sdelphij heuristic, by Paul Eggert, to limit the cost to O(N**1.5 log N) 29170754Sdelphij at the price of producing suboptimal output for large inputs with 30170754Sdelphij many differences. 31170754Sdelphij 32170754Sdelphij The basic algorithm was independently discovered as described in: 33170754Sdelphij "Algorithms for Approximate String Matching", E. Ukkonen, 34170754Sdelphij Information and Control Vol. 64, 1985, pp. 100-118. */ 35170754Sdelphij 36170754Sdelphij#include "diff.h" 37170754Sdelphij#include <cmpbuf.h> 38170754Sdelphij#include <error.h> 39170754Sdelphij#include <file-type.h> 40170754Sdelphij#include <xalloc.h> 41170754Sdelphij 42170754Sdelphijstatic lin *xvec, *yvec; /* Vectors being compared. */ 43170754Sdelphijstatic lin *fdiag; /* Vector, indexed by diagonal, containing 44170754Sdelphij 1 + the X coordinate of the point furthest 45170754Sdelphij along the given diagonal in the forward 46170754Sdelphij search of the edit matrix. */ 47170754Sdelphijstatic lin *bdiag; /* Vector, indexed by diagonal, containing 48170754Sdelphij the X coordinate of the point furthest 49170754Sdelphij along the given diagonal in the backward 50170754Sdelphij search of the edit matrix. */ 51170754Sdelphijstatic lin too_expensive; /* Edit scripts longer than this are too 52170754Sdelphij expensive to compute. */ 53170754Sdelphij 54170754Sdelphij#define SNAKE_LIMIT 20 /* Snakes bigger than this are considered `big'. */ 55170754Sdelphij 56170754Sdelphijstruct partition 57170754Sdelphij{ 58170754Sdelphij lin xmid, ymid; /* Midpoints of this partition. */ 59170754Sdelphij bool lo_minimal; /* Nonzero if low half will be analyzed minimally. */ 60170754Sdelphij bool hi_minimal; /* Likewise for high half. */ 61170754Sdelphij}; 62170754Sdelphij 63170754Sdelphij/* Find the midpoint of the shortest edit script for a specified 64170754Sdelphij portion of the two files. 65170754Sdelphij 66170754Sdelphij Scan from the beginnings of the files, and simultaneously from the ends, 67170754Sdelphij doing a breadth-first search through the space of edit-sequence. 68170754Sdelphij When the two searches meet, we have found the midpoint of the shortest 69170754Sdelphij edit sequence. 70170754Sdelphij 71170754Sdelphij If FIND_MINIMAL is nonzero, find the minimal edit script regardless 72170754Sdelphij of expense. Otherwise, if the search is too expensive, use 73170754Sdelphij heuristics to stop the search and report a suboptimal answer. 74170754Sdelphij 75170754Sdelphij Set PART->(xmid,ymid) to the midpoint (XMID,YMID). The diagonal number 76170754Sdelphij XMID - YMID equals the number of inserted lines minus the number 77170754Sdelphij of deleted lines (counting only lines before the midpoint). 78170754Sdelphij 79170754Sdelphij Set PART->lo_minimal to true iff the minimal edit script for the 80170754Sdelphij left half of the partition is known; similarly for PART->hi_minimal. 81170754Sdelphij 82170754Sdelphij This function assumes that the first lines of the specified portions 83170754Sdelphij of the two files do not match, and likewise that the last lines do not 84170754Sdelphij match. The caller must trim matching lines from the beginning and end 85170754Sdelphij of the portions it is going to specify. 86170754Sdelphij 87170754Sdelphij If we return the "wrong" partitions, 88170754Sdelphij the worst this can do is cause suboptimal diff output. 89170754Sdelphij It cannot cause incorrect diff output. */ 90170754Sdelphij 91170754Sdelphijstatic void 92170754Sdelphijdiag (lin xoff, lin xlim, lin yoff, lin ylim, bool find_minimal, 93170754Sdelphij struct partition *part) 94170754Sdelphij{ 95170754Sdelphij lin *const fd = fdiag; /* Give the compiler a chance. */ 96170754Sdelphij lin *const bd = bdiag; /* Additional help for the compiler. */ 97170754Sdelphij lin const *const xv = xvec; /* Still more help for the compiler. */ 98170754Sdelphij lin const *const yv = yvec; /* And more and more . . . */ 99170754Sdelphij lin const dmin = xoff - ylim; /* Minimum valid diagonal. */ 100170754Sdelphij lin const dmax = xlim - yoff; /* Maximum valid diagonal. */ 101170754Sdelphij lin const fmid = xoff - yoff; /* Center diagonal of top-down search. */ 102170754Sdelphij lin const bmid = xlim - ylim; /* Center diagonal of bottom-up search. */ 103170754Sdelphij lin fmin = fmid, fmax = fmid; /* Limits of top-down search. */ 104170754Sdelphij lin bmin = bmid, bmax = bmid; /* Limits of bottom-up search. */ 105170754Sdelphij lin c; /* Cost. */ 106170754Sdelphij bool odd = (fmid - bmid) & 1; /* True if southeast corner is on an odd 107170754Sdelphij diagonal with respect to the northwest. */ 108170754Sdelphij 109170754Sdelphij fd[fmid] = xoff; 110170754Sdelphij bd[bmid] = xlim; 111170754Sdelphij 112170754Sdelphij for (c = 1;; ++c) 113170754Sdelphij { 114170754Sdelphij lin d; /* Active diagonal. */ 115170754Sdelphij bool big_snake = false; 116170754Sdelphij 117170754Sdelphij /* Extend the top-down search by an edit step in each diagonal. */ 118170754Sdelphij fmin > dmin ? fd[--fmin - 1] = -1 : ++fmin; 119170754Sdelphij fmax < dmax ? fd[++fmax + 1] = -1 : --fmax; 120170754Sdelphij for (d = fmax; d >= fmin; d -= 2) 121170754Sdelphij { 122170754Sdelphij lin x, y, oldx, tlo = fd[d - 1], thi = fd[d + 1]; 123170754Sdelphij 124170754Sdelphij if (tlo >= thi) 125170754Sdelphij x = tlo + 1; 126170754Sdelphij else 127170754Sdelphij x = thi; 128170754Sdelphij oldx = x; 129170754Sdelphij y = x - d; 130170754Sdelphij while (x < xlim && y < ylim && xv[x] == yv[y]) 131170754Sdelphij ++x, ++y; 132170754Sdelphij if (x - oldx > SNAKE_LIMIT) 133170754Sdelphij big_snake = true; 134170754Sdelphij fd[d] = x; 135170754Sdelphij if (odd && bmin <= d && d <= bmax && bd[d] <= x) 136170754Sdelphij { 137170754Sdelphij part->xmid = x; 138170754Sdelphij part->ymid = y; 139170754Sdelphij part->lo_minimal = part->hi_minimal = true; 140170754Sdelphij return; 141170754Sdelphij } 142170754Sdelphij } 143170754Sdelphij 144170754Sdelphij /* Similarly extend the bottom-up search. */ 145170754Sdelphij bmin > dmin ? bd[--bmin - 1] = LIN_MAX : ++bmin; 146170754Sdelphij bmax < dmax ? bd[++bmax + 1] = LIN_MAX : --bmax; 147170754Sdelphij for (d = bmax; d >= bmin; d -= 2) 148170754Sdelphij { 149170754Sdelphij lin x, y, oldx, tlo = bd[d - 1], thi = bd[d + 1]; 150170754Sdelphij 151170754Sdelphij if (tlo < thi) 152170754Sdelphij x = tlo; 153170754Sdelphij else 154170754Sdelphij x = thi - 1; 155170754Sdelphij oldx = x; 156170754Sdelphij y = x - d; 157170754Sdelphij while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1]) 158170754Sdelphij --x, --y; 159170754Sdelphij if (oldx - x > SNAKE_LIMIT) 160170754Sdelphij big_snake = true; 161170754Sdelphij bd[d] = x; 162170754Sdelphij if (!odd && fmin <= d && d <= fmax && x <= fd[d]) 163170754Sdelphij { 164170754Sdelphij part->xmid = x; 165170754Sdelphij part->ymid = y; 166170754Sdelphij part->lo_minimal = part->hi_minimal = true; 167170754Sdelphij return; 168170754Sdelphij } 169170754Sdelphij } 170170754Sdelphij 171170754Sdelphij if (find_minimal) 172170754Sdelphij continue; 173170754Sdelphij 174170754Sdelphij /* Heuristic: check occasionally for a diagonal that has made 175170754Sdelphij lots of progress compared with the edit distance. 176170754Sdelphij If we have any such, find the one that has made the most 177170754Sdelphij progress and return it as if it had succeeded. 178170754Sdelphij 179170754Sdelphij With this heuristic, for files with a constant small density 180170754Sdelphij of changes, the algorithm is linear in the file size. */ 181170754Sdelphij 182170754Sdelphij if (200 < c && big_snake && speed_large_files) 183170754Sdelphij { 184170754Sdelphij lin best = 0; 185170754Sdelphij 186170754Sdelphij for (d = fmax; d >= fmin; d -= 2) 187170754Sdelphij { 188170754Sdelphij lin dd = d - fmid; 189170754Sdelphij lin x = fd[d]; 190170754Sdelphij lin y = x - d; 191170754Sdelphij lin v = (x - xoff) * 2 - dd; 192170754Sdelphij if (v > 12 * (c + (dd < 0 ? -dd : dd))) 193170754Sdelphij { 194170754Sdelphij if (v > best 195170754Sdelphij && xoff + SNAKE_LIMIT <= x && x < xlim 196170754Sdelphij && yoff + SNAKE_LIMIT <= y && y < ylim) 197170754Sdelphij { 198170754Sdelphij /* We have a good enough best diagonal; 199170754Sdelphij now insist that it end with a significant snake. */ 200170754Sdelphij int k; 201170754Sdelphij 202170754Sdelphij for (k = 1; xv[x - k] == yv[y - k]; k++) 203170754Sdelphij if (k == SNAKE_LIMIT) 204170754Sdelphij { 205170754Sdelphij best = v; 206170754Sdelphij part->xmid = x; 207170754Sdelphij part->ymid = y; 208170754Sdelphij break; 209170754Sdelphij } 210170754Sdelphij } 211170754Sdelphij } 212170754Sdelphij } 213170754Sdelphij if (best > 0) 214170754Sdelphij { 215170754Sdelphij part->lo_minimal = true; 216170754Sdelphij part->hi_minimal = false; 217170754Sdelphij return; 218170754Sdelphij } 219170754Sdelphij 220170754Sdelphij best = 0; 221170754Sdelphij for (d = bmax; d >= bmin; d -= 2) 222170754Sdelphij { 223170754Sdelphij lin dd = d - bmid; 224170754Sdelphij lin x = bd[d]; 225170754Sdelphij lin y = x - d; 226170754Sdelphij lin v = (xlim - x) * 2 + dd; 227170754Sdelphij if (v > 12 * (c + (dd < 0 ? -dd : dd))) 228170754Sdelphij { 229170754Sdelphij if (v > best 230170754Sdelphij && xoff < x && x <= xlim - SNAKE_LIMIT 231170754Sdelphij && yoff < y && y <= ylim - SNAKE_LIMIT) 232170754Sdelphij { 233170754Sdelphij /* We have a good enough best diagonal; 234170754Sdelphij now insist that it end with a significant snake. */ 235170754Sdelphij int k; 236170754Sdelphij 237170754Sdelphij for (k = 0; xv[x + k] == yv[y + k]; k++) 238170754Sdelphij if (k == SNAKE_LIMIT - 1) 239170754Sdelphij { 240170754Sdelphij best = v; 241170754Sdelphij part->xmid = x; 242170754Sdelphij part->ymid = y; 243170754Sdelphij break; 244170754Sdelphij } 245170754Sdelphij } 246170754Sdelphij } 247170754Sdelphij } 248170754Sdelphij if (best > 0) 249170754Sdelphij { 250170754Sdelphij part->lo_minimal = false; 251170754Sdelphij part->hi_minimal = true; 252170754Sdelphij return; 253170754Sdelphij } 254170754Sdelphij } 255170754Sdelphij 256170754Sdelphij /* Heuristic: if we've gone well beyond the call of duty, 257170754Sdelphij give up and report halfway between our best results so far. */ 258170754Sdelphij if (c >= too_expensive) 259170754Sdelphij { 260170754Sdelphij lin fxybest, fxbest; 261170754Sdelphij lin bxybest, bxbest; 262170754Sdelphij 263170754Sdelphij fxbest = bxbest = 0; /* Pacify `gcc -Wall'. */ 264170754Sdelphij 265170754Sdelphij /* Find forward diagonal that maximizes X + Y. */ 266170754Sdelphij fxybest = -1; 267170754Sdelphij for (d = fmax; d >= fmin; d -= 2) 268170754Sdelphij { 269170754Sdelphij lin x = MIN (fd[d], xlim); 270170754Sdelphij lin y = x - d; 271170754Sdelphij if (ylim < y) 272170754Sdelphij x = ylim + d, y = ylim; 273170754Sdelphij if (fxybest < x + y) 274170754Sdelphij { 275170754Sdelphij fxybest = x + y; 276170754Sdelphij fxbest = x; 277170754Sdelphij } 278170754Sdelphij } 279170754Sdelphij 280170754Sdelphij /* Find backward diagonal that minimizes X + Y. */ 281170754Sdelphij bxybest = LIN_MAX; 282170754Sdelphij for (d = bmax; d >= bmin; d -= 2) 283170754Sdelphij { 284170754Sdelphij lin x = MAX (xoff, bd[d]); 285170754Sdelphij lin y = x - d; 286170754Sdelphij if (y < yoff) 287170754Sdelphij x = yoff + d, y = yoff; 288170754Sdelphij if (x + y < bxybest) 289170754Sdelphij { 290170754Sdelphij bxybest = x + y; 291170754Sdelphij bxbest = x; 292170754Sdelphij } 293170754Sdelphij } 294170754Sdelphij 295170754Sdelphij /* Use the better of the two diagonals. */ 296170754Sdelphij if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff)) 297170754Sdelphij { 298170754Sdelphij part->xmid = fxbest; 299170754Sdelphij part->ymid = fxybest - fxbest; 300170754Sdelphij part->lo_minimal = true; 301170754Sdelphij part->hi_minimal = false; 302170754Sdelphij } 303170754Sdelphij else 304170754Sdelphij { 305170754Sdelphij part->xmid = bxbest; 306170754Sdelphij part->ymid = bxybest - bxbest; 307170754Sdelphij part->lo_minimal = false; 308170754Sdelphij part->hi_minimal = true; 309170754Sdelphij } 310170754Sdelphij return; 311170754Sdelphij } 312170754Sdelphij } 313170754Sdelphij} 314170754Sdelphij 315170754Sdelphij/* Compare in detail contiguous subsequences of the two files 316170754Sdelphij which are known, as a whole, to match each other. 317170754Sdelphij 318170754Sdelphij The results are recorded in the vectors files[N].changed, by 319170754Sdelphij storing 1 in the element for each line that is an insertion or deletion. 320170754Sdelphij 321170754Sdelphij The subsequence of file 0 is [XOFF, XLIM) and likewise for file 1. 322170754Sdelphij 323170754Sdelphij Note that XLIM, YLIM are exclusive bounds. 324170754Sdelphij All line numbers are origin-0 and discarded lines are not counted. 325170754Sdelphij 326170754Sdelphij If FIND_MINIMAL, find a minimal difference no matter how 327170754Sdelphij expensive it is. */ 328170754Sdelphij 329170754Sdelphijstatic void 330170754Sdelphijcompareseq (lin xoff, lin xlim, lin yoff, lin ylim, bool find_minimal) 331170754Sdelphij{ 332170754Sdelphij lin const *xv = xvec; /* Help the compiler. */ 333170754Sdelphij lin const *yv = yvec; 334170754Sdelphij 335170754Sdelphij /* Slide down the bottom initial diagonal. */ 336170754Sdelphij while (xoff < xlim && yoff < ylim && xv[xoff] == yv[yoff]) 337170754Sdelphij ++xoff, ++yoff; 338170754Sdelphij /* Slide up the top initial diagonal. */ 339170754Sdelphij while (xlim > xoff && ylim > yoff && xv[xlim - 1] == yv[ylim - 1]) 340170754Sdelphij --xlim, --ylim; 341170754Sdelphij 342170754Sdelphij /* Handle simple cases. */ 343170754Sdelphij if (xoff == xlim) 344170754Sdelphij while (yoff < ylim) 345170754Sdelphij files[1].changed[files[1].realindexes[yoff++]] = 1; 346170754Sdelphij else if (yoff == ylim) 347170754Sdelphij while (xoff < xlim) 348170754Sdelphij files[0].changed[files[0].realindexes[xoff++]] = 1; 349170754Sdelphij else 350170754Sdelphij { 351170754Sdelphij struct partition part; 352170754Sdelphij 353170754Sdelphij /* Find a point of correspondence in the middle of the files. */ 354170754Sdelphij diag (xoff, xlim, yoff, ylim, find_minimal, &part); 355170754Sdelphij 356170754Sdelphij /* Use the partitions to split this problem into subproblems. */ 357170754Sdelphij compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal); 358170754Sdelphij compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal); 359170754Sdelphij } 360170754Sdelphij} 361170754Sdelphij 362170754Sdelphij/* Discard lines from one file that have no matches in the other file. 363170754Sdelphij 364170754Sdelphij A line which is discarded will not be considered by the actual 365170754Sdelphij comparison algorithm; it will be as if that line were not in the file. 366170754Sdelphij The file's `realindexes' table maps virtual line numbers 367170754Sdelphij (which don't count the discarded lines) into real line numbers; 368170754Sdelphij this is how the actual comparison algorithm produces results 369170754Sdelphij that are comprehensible when the discarded lines are counted. 370170754Sdelphij 371170754Sdelphij When we discard a line, we also mark it as a deletion or insertion 372170754Sdelphij so that it will be printed in the output. */ 373170754Sdelphij 374170754Sdelphijstatic void 375170754Sdelphijdiscard_confusing_lines (struct file_data filevec[]) 376170754Sdelphij{ 377170754Sdelphij int f; 378170754Sdelphij lin i; 379170754Sdelphij char *discarded[2]; 380170754Sdelphij lin *equiv_count[2]; 381170754Sdelphij lin *p; 382170754Sdelphij 383170754Sdelphij /* Allocate our results. */ 384170754Sdelphij p = xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines) 385170754Sdelphij * (2 * sizeof *p)); 386170754Sdelphij for (f = 0; f < 2; f++) 387170754Sdelphij { 388170754Sdelphij filevec[f].undiscarded = p; p += filevec[f].buffered_lines; 389170754Sdelphij filevec[f].realindexes = p; p += filevec[f].buffered_lines; 390170754Sdelphij } 391170754Sdelphij 392170754Sdelphij /* Set up equiv_count[F][I] as the number of lines in file F 393170754Sdelphij that fall in equivalence class I. */ 394170754Sdelphij 395170754Sdelphij p = zalloc (filevec[0].equiv_max * (2 * sizeof *p)); 396170754Sdelphij equiv_count[0] = p; 397170754Sdelphij equiv_count[1] = p + filevec[0].equiv_max; 398170754Sdelphij 399170754Sdelphij for (i = 0; i < filevec[0].buffered_lines; ++i) 400170754Sdelphij ++equiv_count[0][filevec[0].equivs[i]]; 401170754Sdelphij for (i = 0; i < filevec[1].buffered_lines; ++i) 402170754Sdelphij ++equiv_count[1][filevec[1].equivs[i]]; 403170754Sdelphij 404170754Sdelphij /* Set up tables of which lines are going to be discarded. */ 405170754Sdelphij 406170754Sdelphij discarded[0] = zalloc (filevec[0].buffered_lines 407170754Sdelphij + filevec[1].buffered_lines); 408170754Sdelphij discarded[1] = discarded[0] + filevec[0].buffered_lines; 409170754Sdelphij 410170754Sdelphij /* Mark to be discarded each line that matches no line of the other file. 411170754Sdelphij If a line matches many lines, mark it as provisionally discardable. */ 412170754Sdelphij 413170754Sdelphij for (f = 0; f < 2; f++) 414170754Sdelphij { 415170754Sdelphij size_t end = filevec[f].buffered_lines; 416170754Sdelphij char *discards = discarded[f]; 417170754Sdelphij lin *counts = equiv_count[1 - f]; 418170754Sdelphij lin *equivs = filevec[f].equivs; 419170754Sdelphij size_t many = 5; 420170754Sdelphij size_t tem = end / 64; 421170754Sdelphij 422170754Sdelphij /* Multiply MANY by approximate square root of number of lines. 423170754Sdelphij That is the threshold for provisionally discardable lines. */ 424170754Sdelphij while ((tem = tem >> 2) > 0) 425170754Sdelphij many *= 2; 426170754Sdelphij 427170754Sdelphij for (i = 0; i < end; i++) 428170754Sdelphij { 429170754Sdelphij lin nmatch; 430170754Sdelphij if (equivs[i] == 0) 431170754Sdelphij continue; 432170754Sdelphij nmatch = counts[equivs[i]]; 433170754Sdelphij if (nmatch == 0) 434170754Sdelphij discards[i] = 1; 435170754Sdelphij else if (nmatch > many) 436170754Sdelphij discards[i] = 2; 437170754Sdelphij } 438170754Sdelphij } 439170754Sdelphij 440170754Sdelphij /* Don't really discard the provisional lines except when they occur 441170754Sdelphij in a run of discardables, with nonprovisionals at the beginning 442170754Sdelphij and end. */ 443170754Sdelphij 444170754Sdelphij for (f = 0; f < 2; f++) 445170754Sdelphij { 446170754Sdelphij lin end = filevec[f].buffered_lines; 447170754Sdelphij register char *discards = discarded[f]; 448170754Sdelphij 449170754Sdelphij for (i = 0; i < end; i++) 450170754Sdelphij { 451170754Sdelphij /* Cancel provisional discards not in middle of run of discards. */ 452170754Sdelphij if (discards[i] == 2) 453170754Sdelphij discards[i] = 0; 454170754Sdelphij else if (discards[i] != 0) 455170754Sdelphij { 456170754Sdelphij /* We have found a nonprovisional discard. */ 457170754Sdelphij register lin j; 458170754Sdelphij lin length; 459170754Sdelphij lin provisional = 0; 460170754Sdelphij 461170754Sdelphij /* Find end of this run of discardable lines. 462170754Sdelphij Count how many are provisionally discardable. */ 463170754Sdelphij for (j = i; j < end; j++) 464170754Sdelphij { 465170754Sdelphij if (discards[j] == 0) 466170754Sdelphij break; 467170754Sdelphij if (discards[j] == 2) 468170754Sdelphij ++provisional; 469170754Sdelphij } 470170754Sdelphij 471170754Sdelphij /* Cancel provisional discards at end, and shrink the run. */ 472170754Sdelphij while (j > i && discards[j - 1] == 2) 473170754Sdelphij discards[--j] = 0, --provisional; 474170754Sdelphij 475170754Sdelphij /* Now we have the length of a run of discardable lines 476170754Sdelphij whose first and last are not provisional. */ 477170754Sdelphij length = j - i; 478170754Sdelphij 479170754Sdelphij /* If 1/4 of the lines in the run are provisional, 480170754Sdelphij cancel discarding of all provisional lines in the run. */ 481170754Sdelphij if (provisional * 4 > length) 482170754Sdelphij { 483170754Sdelphij while (j > i) 484170754Sdelphij if (discards[--j] == 2) 485170754Sdelphij discards[j] = 0; 486170754Sdelphij } 487170754Sdelphij else 488170754Sdelphij { 489170754Sdelphij register lin consec; 490170754Sdelphij lin minimum = 1; 491170754Sdelphij lin tem = length >> 2; 492170754Sdelphij 493170754Sdelphij /* MINIMUM is approximate square root of LENGTH/4. 494170754Sdelphij A subrun of two or more provisionals can stand 495170754Sdelphij when LENGTH is at least 16. 496170754Sdelphij A subrun of 4 or more can stand when LENGTH >= 64. */ 497170754Sdelphij while (0 < (tem >>= 2)) 498170754Sdelphij minimum <<= 1; 499170754Sdelphij minimum++; 500170754Sdelphij 501170754Sdelphij /* Cancel any subrun of MINIMUM or more provisionals 502170754Sdelphij within the larger run. */ 503170754Sdelphij for (j = 0, consec = 0; j < length; j++) 504170754Sdelphij if (discards[i + j] != 2) 505170754Sdelphij consec = 0; 506170754Sdelphij else if (minimum == ++consec) 507170754Sdelphij /* Back up to start of subrun, to cancel it all. */ 508170754Sdelphij j -= consec; 509170754Sdelphij else if (minimum < consec) 510170754Sdelphij discards[i + j] = 0; 511170754Sdelphij 512170754Sdelphij /* Scan from beginning of run 513170754Sdelphij until we find 3 or more nonprovisionals in a row 514170754Sdelphij or until the first nonprovisional at least 8 lines in. 515170754Sdelphij Until that point, cancel any provisionals. */ 516170754Sdelphij for (j = 0, consec = 0; j < length; j++) 517170754Sdelphij { 518170754Sdelphij if (j >= 8 && discards[i + j] == 1) 519170754Sdelphij break; 520170754Sdelphij if (discards[i + j] == 2) 521170754Sdelphij consec = 0, discards[i + j] = 0; 522170754Sdelphij else if (discards[i + j] == 0) 523170754Sdelphij consec = 0; 524170754Sdelphij else 525170754Sdelphij consec++; 526170754Sdelphij if (consec == 3) 527170754Sdelphij break; 528170754Sdelphij } 529170754Sdelphij 530170754Sdelphij /* I advances to the last line of the run. */ 531170754Sdelphij i += length - 1; 532170754Sdelphij 533170754Sdelphij /* Same thing, from end. */ 534170754Sdelphij for (j = 0, consec = 0; j < length; j++) 535170754Sdelphij { 536170754Sdelphij if (j >= 8 && discards[i - j] == 1) 537170754Sdelphij break; 538170754Sdelphij if (discards[i - j] == 2) 539170754Sdelphij consec = 0, discards[i - j] = 0; 540170754Sdelphij else if (discards[i - j] == 0) 541170754Sdelphij consec = 0; 542170754Sdelphij else 543170754Sdelphij consec++; 544170754Sdelphij if (consec == 3) 545170754Sdelphij break; 546170754Sdelphij } 547170754Sdelphij } 548170754Sdelphij } 549170754Sdelphij } 550170754Sdelphij } 551170754Sdelphij 552170754Sdelphij /* Actually discard the lines. */ 553170754Sdelphij for (f = 0; f < 2; f++) 554170754Sdelphij { 555170754Sdelphij char *discards = discarded[f]; 556170754Sdelphij lin end = filevec[f].buffered_lines; 557170754Sdelphij lin j = 0; 558170754Sdelphij for (i = 0; i < end; ++i) 559170754Sdelphij if (minimal || discards[i] == 0) 560170754Sdelphij { 561170754Sdelphij filevec[f].undiscarded[j] = filevec[f].equivs[i]; 562170754Sdelphij filevec[f].realindexes[j++] = i; 563170754Sdelphij } 564170754Sdelphij else 565170754Sdelphij filevec[f].changed[i] = 1; 566170754Sdelphij filevec[f].nondiscarded_lines = j; 567170754Sdelphij } 568170754Sdelphij 569170754Sdelphij free (discarded[0]); 570170754Sdelphij free (equiv_count[0]); 571170754Sdelphij} 572170754Sdelphij 573170754Sdelphij/* Adjust inserts/deletes of identical lines to join changes 574170754Sdelphij as much as possible. 575170754Sdelphij 576170754Sdelphij We do something when a run of changed lines include a 577170754Sdelphij line at one end and have an excluded, identical line at the other. 578170754Sdelphij We are free to choose which identical line is included. 579170754Sdelphij `compareseq' usually chooses the one at the beginning, 580170754Sdelphij but usually it is cleaner to consider the following identical line 581170754Sdelphij to be the "change". */ 582170754Sdelphij 583170754Sdelphijstatic void 584170754Sdelphijshift_boundaries (struct file_data filevec[]) 585170754Sdelphij{ 586170754Sdelphij int f; 587170754Sdelphij 588170754Sdelphij for (f = 0; f < 2; f++) 589170754Sdelphij { 590170754Sdelphij char *changed = filevec[f].changed; 591170754Sdelphij char *other_changed = filevec[1 - f].changed; 592170754Sdelphij lin const *equivs = filevec[f].equivs; 593170754Sdelphij lin i = 0; 594170754Sdelphij lin j = 0; 595170754Sdelphij lin i_end = filevec[f].buffered_lines; 596170754Sdelphij 597170754Sdelphij while (1) 598170754Sdelphij { 599170754Sdelphij lin runlength, start, corresponding; 600170754Sdelphij 601170754Sdelphij /* Scan forwards to find beginning of another run of changes. 602170754Sdelphij Also keep track of the corresponding point in the other file. */ 603170754Sdelphij 604170754Sdelphij while (i < i_end && !changed[i]) 605170754Sdelphij { 606170754Sdelphij while (other_changed[j++]) 607170754Sdelphij continue; 608170754Sdelphij i++; 609170754Sdelphij } 610170754Sdelphij 611170754Sdelphij if (i == i_end) 612170754Sdelphij break; 613170754Sdelphij 614170754Sdelphij start = i; 615170754Sdelphij 616170754Sdelphij /* Find the end of this run of changes. */ 617170754Sdelphij 618170754Sdelphij while (changed[++i]) 619170754Sdelphij continue; 620170754Sdelphij while (other_changed[j]) 621170754Sdelphij j++; 622170754Sdelphij 623170754Sdelphij do 624170754Sdelphij { 625170754Sdelphij /* Record the length of this run of changes, so that 626170754Sdelphij we can later determine whether the run has grown. */ 627170754Sdelphij runlength = i - start; 628170754Sdelphij 629170754Sdelphij /* Move the changed region back, so long as the 630170754Sdelphij previous unchanged line matches the last changed one. 631170754Sdelphij This merges with previous changed regions. */ 632170754Sdelphij 633170754Sdelphij while (start && equivs[start - 1] == equivs[i - 1]) 634170754Sdelphij { 635170754Sdelphij changed[--start] = 1; 636170754Sdelphij changed[--i] = 0; 637170754Sdelphij while (changed[start - 1]) 638170754Sdelphij start--; 639170754Sdelphij while (other_changed[--j]) 640170754Sdelphij continue; 641170754Sdelphij } 642170754Sdelphij 643170754Sdelphij /* Set CORRESPONDING to the end of the changed run, at the last 644170754Sdelphij point where it corresponds to a changed run in the other file. 645170754Sdelphij CORRESPONDING == I_END means no such point has been found. */ 646170754Sdelphij corresponding = other_changed[j - 1] ? i : i_end; 647170754Sdelphij 648170754Sdelphij /* Move the changed region forward, so long as the 649170754Sdelphij first changed line matches the following unchanged one. 650170754Sdelphij This merges with following changed regions. 651170754Sdelphij Do this second, so that if there are no merges, 652170754Sdelphij the changed region is moved forward as far as possible. */ 653170754Sdelphij 654170754Sdelphij while (i != i_end && equivs[start] == equivs[i]) 655170754Sdelphij { 656170754Sdelphij changed[start++] = 0; 657170754Sdelphij changed[i++] = 1; 658170754Sdelphij while (changed[i]) 659170754Sdelphij i++; 660170754Sdelphij while (other_changed[++j]) 661170754Sdelphij corresponding = i; 662170754Sdelphij } 663170754Sdelphij } 664170754Sdelphij while (runlength != i - start); 665170754Sdelphij 666170754Sdelphij /* If possible, move the fully-merged run of changes 667170754Sdelphij back to a corresponding run in the other file. */ 668170754Sdelphij 669170754Sdelphij while (corresponding < i) 670170754Sdelphij { 671170754Sdelphij changed[--start] = 1; 672170754Sdelphij changed[--i] = 0; 673170754Sdelphij while (other_changed[--j]) 674170754Sdelphij continue; 675170754Sdelphij } 676170754Sdelphij } 677170754Sdelphij } 678170754Sdelphij} 679170754Sdelphij 680170754Sdelphij/* Cons an additional entry onto the front of an edit script OLD. 681170754Sdelphij LINE0 and LINE1 are the first affected lines in the two files (origin 0). 682170754Sdelphij DELETED is the number of lines deleted here from file 0. 683170754Sdelphij INSERTED is the number of lines inserted here in file 1. 684170754Sdelphij 685170754Sdelphij If DELETED is 0 then LINE0 is the number of the line before 686170754Sdelphij which the insertion was done; vice versa for INSERTED and LINE1. */ 687170754Sdelphij 688170754Sdelphijstatic struct change * 689170754Sdelphijadd_change (lin line0, lin line1, lin deleted, lin inserted, 690170754Sdelphij struct change *old) 691170754Sdelphij{ 692170754Sdelphij struct change *new = xmalloc (sizeof *new); 693170754Sdelphij 694170754Sdelphij new->line0 = line0; 695170754Sdelphij new->line1 = line1; 696170754Sdelphij new->inserted = inserted; 697170754Sdelphij new->deleted = deleted; 698170754Sdelphij new->link = old; 699170754Sdelphij return new; 700170754Sdelphij} 701170754Sdelphij 702170754Sdelphij/* Scan the tables of which lines are inserted and deleted, 703170754Sdelphij producing an edit script in reverse order. */ 704170754Sdelphij 705170754Sdelphijstatic struct change * 706170754Sdelphijbuild_reverse_script (struct file_data const filevec[]) 707170754Sdelphij{ 708170754Sdelphij struct change *script = 0; 709170754Sdelphij char *changed0 = filevec[0].changed; 710170754Sdelphij char *changed1 = filevec[1].changed; 711170754Sdelphij lin len0 = filevec[0].buffered_lines; 712170754Sdelphij lin len1 = filevec[1].buffered_lines; 713170754Sdelphij 714170754Sdelphij /* Note that changedN[len0] does exist, and is 0. */ 715170754Sdelphij 716170754Sdelphij lin i0 = 0, i1 = 0; 717170754Sdelphij 718170754Sdelphij while (i0 < len0 || i1 < len1) 719170754Sdelphij { 720170754Sdelphij if (changed0[i0] | changed1[i1]) 721170754Sdelphij { 722170754Sdelphij lin line0 = i0, line1 = i1; 723170754Sdelphij 724170754Sdelphij /* Find # lines changed here in each file. */ 725170754Sdelphij while (changed0[i0]) ++i0; 726170754Sdelphij while (changed1[i1]) ++i1; 727170754Sdelphij 728170754Sdelphij /* Record this change. */ 729170754Sdelphij script = add_change (line0, line1, i0 - line0, i1 - line1, script); 730170754Sdelphij } 731170754Sdelphij 732170754Sdelphij /* We have reached lines in the two files that match each other. */ 733170754Sdelphij i0++, i1++; 734170754Sdelphij } 735170754Sdelphij 736170754Sdelphij return script; 737170754Sdelphij} 738170754Sdelphij 739170754Sdelphij/* Scan the tables of which lines are inserted and deleted, 740170754Sdelphij producing an edit script in forward order. */ 741170754Sdelphij 742170754Sdelphijstatic struct change * 743170754Sdelphijbuild_script (struct file_data const filevec[]) 744170754Sdelphij{ 745170754Sdelphij struct change *script = 0; 746170754Sdelphij char *changed0 = filevec[0].changed; 747170754Sdelphij char *changed1 = filevec[1].changed; 748170754Sdelphij lin i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines; 749170754Sdelphij 750170754Sdelphij /* Note that changedN[-1] does exist, and is 0. */ 751170754Sdelphij 752170754Sdelphij while (i0 >= 0 || i1 >= 0) 753170754Sdelphij { 754170754Sdelphij if (changed0[i0 - 1] | changed1[i1 - 1]) 755170754Sdelphij { 756170754Sdelphij lin line0 = i0, line1 = i1; 757170754Sdelphij 758170754Sdelphij /* Find # lines changed here in each file. */ 759170754Sdelphij while (changed0[i0 - 1]) --i0; 760170754Sdelphij while (changed1[i1 - 1]) --i1; 761170754Sdelphij 762170754Sdelphij /* Record this change. */ 763170754Sdelphij script = add_change (i0, i1, line0 - i0, line1 - i1, script); 764170754Sdelphij } 765170754Sdelphij 766170754Sdelphij /* We have reached lines in the two files that match each other. */ 767170754Sdelphij i0--, i1--; 768170754Sdelphij } 769170754Sdelphij 770170754Sdelphij return script; 771170754Sdelphij} 772170754Sdelphij 773170754Sdelphij/* If CHANGES, briefly report that two files differed. 774170754Sdelphij Return 2 if trouble, CHANGES otherwise. */ 775170754Sdelphijstatic int 776170754Sdelphijbriefly_report (int changes, struct file_data const filevec[]) 777170754Sdelphij{ 778170754Sdelphij if (changes) 779170754Sdelphij { 780170754Sdelphij char const *label0 = file_label[0] ? file_label[0] : filevec[0].name; 781170754Sdelphij char const *label1 = file_label[1] ? file_label[1] : filevec[1].name; 782170754Sdelphij message ("Files %s and %s differ\n", label0, label1); 783170754Sdelphij if (! brief) 784170754Sdelphij changes = 2; 785170754Sdelphij } 786170754Sdelphij 787170754Sdelphij return changes; 788170754Sdelphij} 789170754Sdelphij 790170754Sdelphij/* Report the differences of two files. */ 791170754Sdelphijint 792170754Sdelphijdiff_2_files (struct comparison *cmp) 793170754Sdelphij{ 794170754Sdelphij lin diags; 795170754Sdelphij int f; 796170754Sdelphij struct change *e, *p; 797170754Sdelphij struct change *script; 798170754Sdelphij int changes; 799170754Sdelphij 800170754Sdelphij 801170754Sdelphij /* If we have detected that either file is binary, 802170754Sdelphij compare the two files as binary. This can happen 803170754Sdelphij only when the first chunk is read. 804170754Sdelphij Also, --brief without any --ignore-* options means 805170754Sdelphij we can speed things up by treating the files as binary. */ 806170754Sdelphij 807170754Sdelphij if (read_files (cmp->file, files_can_be_treated_as_binary)) 808170754Sdelphij { 809170754Sdelphij /* Files with different lengths must be different. */ 810170754Sdelphij if (cmp->file[0].stat.st_size != cmp->file[1].stat.st_size 811170754Sdelphij && (cmp->file[0].desc < 0 || S_ISREG (cmp->file[0].stat.st_mode)) 812170754Sdelphij && (cmp->file[1].desc < 0 || S_ISREG (cmp->file[1].stat.st_mode))) 813170754Sdelphij changes = 1; 814170754Sdelphij 815170754Sdelphij /* Standard input equals itself. */ 816170754Sdelphij else if (cmp->file[0].desc == cmp->file[1].desc) 817170754Sdelphij changes = 0; 818170754Sdelphij 819170754Sdelphij else 820170754Sdelphij /* Scan both files, a buffer at a time, looking for a difference. */ 821170754Sdelphij { 822170754Sdelphij /* Allocate same-sized buffers for both files. */ 823170754Sdelphij size_t lcm_max = PTRDIFF_MAX - 1; 824170754Sdelphij size_t buffer_size = 825170754Sdelphij buffer_lcm (sizeof (word), 826170754Sdelphij buffer_lcm (STAT_BLOCKSIZE (cmp->file[0].stat), 827170754Sdelphij STAT_BLOCKSIZE (cmp->file[1].stat), 828170754Sdelphij lcm_max), 829170754Sdelphij lcm_max); 830170754Sdelphij for (f = 0; f < 2; f++) 831170754Sdelphij cmp->file[f].buffer = xrealloc (cmp->file[f].buffer, buffer_size); 832170754Sdelphij 833170754Sdelphij for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0) 834170754Sdelphij { 835170754Sdelphij /* Read a buffer's worth from both files. */ 836170754Sdelphij for (f = 0; f < 2; f++) 837170754Sdelphij if (0 <= cmp->file[f].desc) 838170754Sdelphij file_block_read (&cmp->file[f], 839170754Sdelphij buffer_size - cmp->file[f].buffered); 840170754Sdelphij 841170754Sdelphij /* If the buffers differ, the files differ. */ 842170754Sdelphij if (cmp->file[0].buffered != cmp->file[1].buffered 843170754Sdelphij || memcmp (cmp->file[0].buffer, 844170754Sdelphij cmp->file[1].buffer, 845170754Sdelphij cmp->file[0].buffered)) 846170754Sdelphij { 847170754Sdelphij changes = 1; 848170754Sdelphij break; 849170754Sdelphij } 850170754Sdelphij 851170754Sdelphij /* If we reach end of file, the files are the same. */ 852170754Sdelphij if (cmp->file[0].buffered != buffer_size) 853170754Sdelphij { 854170754Sdelphij changes = 0; 855170754Sdelphij break; 856170754Sdelphij } 857170754Sdelphij } 858170754Sdelphij } 859170754Sdelphij 860170754Sdelphij changes = briefly_report (changes, cmp->file); 861170754Sdelphij } 862170754Sdelphij else 863170754Sdelphij { 864170754Sdelphij /* Allocate vectors for the results of comparison: 865170754Sdelphij a flag for each line of each file, saying whether that line 866170754Sdelphij is an insertion or deletion. 867170754Sdelphij Allocate an extra element, always 0, at each end of each vector. */ 868170754Sdelphij 869170754Sdelphij size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4; 870170754Sdelphij char *flag_space = zalloc (s); 871170754Sdelphij cmp->file[0].changed = flag_space + 1; 872170754Sdelphij cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3; 873170754Sdelphij 874170754Sdelphij /* Some lines are obviously insertions or deletions 875170754Sdelphij because they don't match anything. Detect them now, and 876170754Sdelphij avoid even thinking about them in the main comparison algorithm. */ 877170754Sdelphij 878170754Sdelphij discard_confusing_lines (cmp->file); 879170754Sdelphij 880170754Sdelphij /* Now do the main comparison algorithm, considering just the 881170754Sdelphij undiscarded lines. */ 882170754Sdelphij 883170754Sdelphij xvec = cmp->file[0].undiscarded; 884170754Sdelphij yvec = cmp->file[1].undiscarded; 885170754Sdelphij diags = (cmp->file[0].nondiscarded_lines 886170754Sdelphij + cmp->file[1].nondiscarded_lines + 3); 887170754Sdelphij fdiag = xmalloc (diags * (2 * sizeof *fdiag)); 888170754Sdelphij bdiag = fdiag + diags; 889170754Sdelphij fdiag += cmp->file[1].nondiscarded_lines + 1; 890170754Sdelphij bdiag += cmp->file[1].nondiscarded_lines + 1; 891170754Sdelphij 892170754Sdelphij /* Set TOO_EXPENSIVE to be approximate square root of input size, 893170754Sdelphij bounded below by 256. */ 894170754Sdelphij too_expensive = 1; 895170754Sdelphij for (; diags != 0; diags >>= 2) 896170754Sdelphij too_expensive <<= 1; 897170754Sdelphij too_expensive = MAX (256, too_expensive); 898170754Sdelphij 899170754Sdelphij files[0] = cmp->file[0]; 900170754Sdelphij files[1] = cmp->file[1]; 901170754Sdelphij 902170754Sdelphij compareseq (0, cmp->file[0].nondiscarded_lines, 903170754Sdelphij 0, cmp->file[1].nondiscarded_lines, minimal); 904170754Sdelphij 905170754Sdelphij free (fdiag - (cmp->file[1].nondiscarded_lines + 1)); 906170754Sdelphij 907170754Sdelphij /* Modify the results slightly to make them prettier 908170754Sdelphij in cases where that can validly be done. */ 909170754Sdelphij 910170754Sdelphij shift_boundaries (cmp->file); 911170754Sdelphij 912170754Sdelphij /* Get the results of comparison in the form of a chain 913170754Sdelphij of `struct change's -- an edit script. */ 914170754Sdelphij 915170754Sdelphij if (output_style == OUTPUT_ED) 916170754Sdelphij script = build_reverse_script (cmp->file); 917170754Sdelphij else 918170754Sdelphij script = build_script (cmp->file); 919170754Sdelphij 920170754Sdelphij /* Set CHANGES if we had any diffs. 921170754Sdelphij If some changes are ignored, we must scan the script to decide. */ 922170754Sdelphij if (ignore_blank_lines || ignore_regexp.fastmap) 923170754Sdelphij { 924170754Sdelphij struct change *next = script; 925170754Sdelphij changes = 0; 926170754Sdelphij 927170754Sdelphij while (next && changes == 0) 928170754Sdelphij { 929170754Sdelphij struct change *this, *end; 930170754Sdelphij lin first0, last0, first1, last1; 931170754Sdelphij 932170754Sdelphij /* Find a set of changes that belong together. */ 933170754Sdelphij this = next; 934170754Sdelphij end = find_change (next); 935170754Sdelphij 936170754Sdelphij /* Disconnect them from the rest of the changes, making them 937170754Sdelphij a hunk, and remember the rest for next iteration. */ 938170754Sdelphij next = end->link; 939170754Sdelphij end->link = 0; 940170754Sdelphij 941170754Sdelphij /* Determine whether this hunk is really a difference. */ 942170754Sdelphij if (analyze_hunk (this, &first0, &last0, &first1, &last1)) 943170754Sdelphij changes = 1; 944170754Sdelphij 945170754Sdelphij /* Reconnect the script so it will all be freed properly. */ 946170754Sdelphij end->link = next; 947170754Sdelphij } 948170754Sdelphij } 949170754Sdelphij else 950170754Sdelphij changes = (script != 0); 951170754Sdelphij 952170754Sdelphij if (brief) 953170754Sdelphij changes = briefly_report (changes, cmp->file); 954170754Sdelphij else 955170754Sdelphij { 956170754Sdelphij if (changes | !no_diff_means_no_output) 957170754Sdelphij { 958170754Sdelphij /* Record info for starting up output, 959170754Sdelphij to be used if and when we have some output to print. */ 960170754Sdelphij setup_output (file_label[0] ? file_label[0] : cmp->file[0].name, 961170754Sdelphij file_label[1] ? file_label[1] : cmp->file[1].name, 962170754Sdelphij cmp->parent != 0); 963170754Sdelphij 964170754Sdelphij switch (output_style) 965170754Sdelphij { 966170754Sdelphij case OUTPUT_CONTEXT: 967170754Sdelphij print_context_script (script, false); 968170754Sdelphij break; 969170754Sdelphij 970170754Sdelphij case OUTPUT_UNIFIED: 971170754Sdelphij print_context_script (script, true); 972170754Sdelphij break; 973170754Sdelphij 974170754Sdelphij case OUTPUT_ED: 975170754Sdelphij print_ed_script (script); 976170754Sdelphij break; 977170754Sdelphij 978170754Sdelphij case OUTPUT_FORWARD_ED: 979170754Sdelphij pr_forward_ed_script (script); 980170754Sdelphij break; 981170754Sdelphij 982170754Sdelphij case OUTPUT_RCS: 983170754Sdelphij print_rcs_script (script); 984170754Sdelphij break; 985170754Sdelphij 986170754Sdelphij case OUTPUT_NORMAL: 987170754Sdelphij print_normal_script (script); 988170754Sdelphij break; 989170754Sdelphij 990170754Sdelphij case OUTPUT_IFDEF: 991170754Sdelphij print_ifdef_script (script); 992170754Sdelphij break; 993170754Sdelphij 994170754Sdelphij case OUTPUT_SDIFF: 995170754Sdelphij print_sdiff_script (script); 996170754Sdelphij break; 997170754Sdelphij 998170754Sdelphij default: 999170754Sdelphij abort (); 1000170754Sdelphij } 1001170754Sdelphij 1002170754Sdelphij finish_output (); 1003170754Sdelphij } 1004170754Sdelphij } 1005170754Sdelphij 1006170754Sdelphij free (cmp->file[0].undiscarded); 1007170754Sdelphij 1008170754Sdelphij free (flag_space); 1009170754Sdelphij 1010170754Sdelphij for (f = 0; f < 2; f++) 1011170754Sdelphij { 1012170754Sdelphij free (cmp->file[f].equivs); 1013170754Sdelphij free (cmp->file[f].linbuf + cmp->file[f].linbuf_base); 1014170754Sdelphij } 1015170754Sdelphij 1016170754Sdelphij for (e = script; e; e = p) 1017170754Sdelphij { 1018170754Sdelphij p = e->link; 1019170754Sdelphij free (e); 1020170754Sdelphij } 1021170754Sdelphij 1022170754Sdelphij if (! ROBUST_OUTPUT_STYLE (output_style)) 1023170754Sdelphij for (f = 0; f < 2; ++f) 1024170754Sdelphij if (cmp->file[f].missing_newline) 1025170754Sdelphij { 1026170754Sdelphij error (0, 0, "%s: %s\n", 1027170754Sdelphij file_label[f] ? file_label[f] : cmp->file[f].name, 1028170754Sdelphij _("No newline at end of file")); 1029170754Sdelphij changes = 2; 1030170754Sdelphij } 1031170754Sdelphij } 1032170754Sdelphij 1033170754Sdelphij if (cmp->file[0].buffer != cmp->file[1].buffer) 1034170754Sdelphij free (cmp->file[0].buffer); 1035170754Sdelphij free (cmp->file[1].buffer); 1036170754Sdelphij 1037170754Sdelphij return changes; 1038170754Sdelphij} 1039