#include "diff.h"
#include <cmpbuf.h>
#include <error.h>
#include <regex.h>
#include <xalloc.h>
static lin *xvec, *yvec;
static lin *fdiag;
static lin *bdiag;
static lin too_expensive;
#define SNAKE_LIMIT 20
struct partition
{
lin xmid, ymid;
bool lo_minimal;
bool hi_minimal;
};
static lin
diag (lin xoff, lin xlim, lin yoff, lin ylim, bool find_minimal,
struct partition *part)
{
lin *const fd = fdiag;
lin *const bd = bdiag;
lin const *const xv = xvec;
lin const *const yv = yvec;
lin const dmin = xoff - ylim;
lin const dmax = xlim - yoff;
lin const fmid = xoff - yoff;
lin const bmid = xlim - ylim;
lin fmin = fmid, fmax = fmid;
lin bmin = bmid, bmax = bmid;
lin c;
bool odd = (fmid - bmid) & 1;
fd[fmid] = xoff;
bd[bmid] = xlim;
for (c = 1;; ++c)
{
lin d;
bool big_snake = 0;
fmin > dmin ? fd[--fmin - 1] = -1 : ++fmin;
fmax < dmax ? fd[++fmax + 1] = -1 : --fmax;
for (d = fmax; d >= fmin; d -= 2)
{
lin x, y, oldx, tlo = fd[d - 1], thi = fd[d + 1];
if (tlo >= thi)
x = tlo + 1;
else
x = thi;
oldx = x;
y = x - d;
while (x < xlim && y < ylim && xv[x] == yv[y])
++x, ++y;
if (x - oldx > SNAKE_LIMIT)
big_snake = 1;
fd[d] = x;
if (odd && bmin <= d && d <= bmax && bd[d] <= x)
{
part->xmid = x;
part->ymid = y;
part->lo_minimal = part->hi_minimal = 1;
return 2 * c - 1;
}
}
bmin > dmin ? bd[--bmin - 1] = LIN_MAX : ++bmin;
bmax < dmax ? bd[++bmax + 1] = LIN_MAX : --bmax;
for (d = bmax; d >= bmin; d -= 2)
{
lin x, y, oldx, tlo = bd[d - 1], thi = bd[d + 1];
if (tlo < thi)
x = tlo;
else
x = thi - 1;
oldx = x;
y = x - d;
while (x > xoff && y > yoff && xv[x - 1] == yv[y - 1])
--x, --y;
if (oldx - x > SNAKE_LIMIT)
big_snake = 1;
bd[d] = x;
if (!odd && fmin <= d && d <= fmax && x <= fd[d])
{
part->xmid = x;
part->ymid = y;
part->lo_minimal = part->hi_minimal = 1;
return 2 * c;
}
}
if (find_minimal)
continue;
if (200 < c && big_snake && speed_large_files)
{
lin best;
best = 0;
for (d = fmax; d >= fmin; d -= 2)
{
lin dd = d - fmid;
lin x = fd[d];
lin y = x - d;
lin v = (x - xoff) * 2 - dd;
if (v > 12 * (c + (dd < 0 ? -dd : dd)))
{
if (v > best
&& xoff + SNAKE_LIMIT <= x && x < xlim
&& yoff + SNAKE_LIMIT <= y && y < ylim)
{
int k;
for (k = 1; xv[x - k] == yv[y - k]; k++)
if (k == SNAKE_LIMIT)
{
best = v;
part->xmid = x;
part->ymid = y;
break;
}
}
}
}
if (best > 0)
{
part->lo_minimal = 1;
part->hi_minimal = 0;
return 2 * c - 1;
}
best = 0;
for (d = bmax; d >= bmin; d -= 2)
{
lin dd = d - bmid;
lin x = bd[d];
lin y = x - d;
lin v = (xlim - x) * 2 + dd;
if (v > 12 * (c + (dd < 0 ? -dd : dd)))
{
if (v > best
&& xoff < x && x <= xlim - SNAKE_LIMIT
&& yoff < y && y <= ylim - SNAKE_LIMIT)
{
int k;
for (k = 0; xv[x + k] == yv[y + k]; k++)
if (k == SNAKE_LIMIT - 1)
{
best = v;
part->xmid = x;
part->ymid = y;
break;
}
}
}
}
if (best > 0)
{
part->lo_minimal = 0;
part->hi_minimal = 1;
return 2 * c - 1;
}
}
if (c >= too_expensive)
{
lin fxybest, fxbest;
lin bxybest, bxbest;
fxbest = bxbest = 0;
fxybest = -1;
for (d = fmax; d >= fmin; d -= 2)
{
lin x = MIN (fd[d], xlim);
lin y = x - d;
if (ylim < y)
x = ylim + d, y = ylim;
if (fxybest < x + y)
{
fxybest = x + y;
fxbest = x;
}
}
bxybest = LIN_MAX;
for (d = bmax; d >= bmin; d -= 2)
{
lin x = MAX (xoff, bd[d]);
lin y = x - d;
if (y < yoff)
x = yoff + d, y = yoff;
if (x + y < bxybest)
{
bxybest = x + y;
bxbest = x;
}
}
if ((xlim + ylim) - bxybest < fxybest - (xoff + yoff))
{
part->xmid = fxbest;
part->ymid = fxybest - fxbest;
part->lo_minimal = 1;
part->hi_minimal = 0;
}
else
{
part->xmid = bxbest;
part->ymid = bxybest - bxbest;
part->lo_minimal = 0;
part->hi_minimal = 1;
}
return 2 * c - 1;
}
}
}
static void
compareseq (lin xoff, lin xlim, lin yoff, lin ylim, bool find_minimal)
{
lin * const xv = xvec;
lin * const yv = yvec;
while (xoff < xlim && yoff < ylim && xv[xoff] == yv[yoff])
++xoff, ++yoff;
while (xlim > xoff && ylim > yoff && xv[xlim - 1] == yv[ylim - 1])
--xlim, --ylim;
if (xoff == xlim)
while (yoff < ylim)
files[1].changed[files[1].realindexes[yoff++]] = 1;
else if (yoff == ylim)
while (xoff < xlim)
files[0].changed[files[0].realindexes[xoff++]] = 1;
else
{
lin c;
struct partition part;
c = diag (xoff, xlim, yoff, ylim, find_minimal, &part);
if (c == 1)
{
abort ();
#if 0
if (part.xmid - part.ymid < xoff - yoff)
files[1].changed[files[1].realindexes[part.ymid - 1]] = 1;
else
files[0].changed[files[0].realindexes[part.xmid]] = 1;
#endif
}
else
{
compareseq (xoff, part.xmid, yoff, part.ymid, part.lo_minimal);
compareseq (part.xmid, xlim, part.ymid, ylim, part.hi_minimal);
}
}
}
static void
discard_confusing_lines (struct file_data filevec[])
{
int f;
lin i;
char *discarded[2];
lin *equiv_count[2];
lin *p;
p = xmalloc ((filevec[0].buffered_lines + filevec[1].buffered_lines)
* (2 * sizeof *p));
for (f = 0; f < 2; f++)
{
filevec[f].undiscarded = p; p += filevec[f].buffered_lines;
filevec[f].realindexes = p; p += filevec[f].buffered_lines;
}
p = zalloc (filevec[0].equiv_max * (2 * sizeof *p));
equiv_count[0] = p;
equiv_count[1] = p + filevec[0].equiv_max;
for (i = 0; i < filevec[0].buffered_lines; ++i)
++equiv_count[0][filevec[0].equivs[i]];
for (i = 0; i < filevec[1].buffered_lines; ++i)
++equiv_count[1][filevec[1].equivs[i]];
discarded[0] = zalloc (filevec[0].buffered_lines
+ filevec[1].buffered_lines);
discarded[1] = discarded[0] + filevec[0].buffered_lines;
for (f = 0; f < 2; f++)
{
size_t end = filevec[f].buffered_lines;
char *discards = discarded[f];
lin *counts = equiv_count[1 - f];
lin *equivs = filevec[f].equivs;
size_t many = 5;
size_t tem = end / 64;
while ((tem = tem >> 2) > 0)
many *= 2;
for (i = 0; i < end; i++)
{
lin nmatch;
if (equivs[i] == 0)
continue;
nmatch = counts[equivs[i]];
if (nmatch == 0)
discards[i] = 1;
else if (nmatch > many)
discards[i] = 2;
}
}
for (f = 0; f < 2; f++)
{
lin end = filevec[f].buffered_lines;
register char *discards = discarded[f];
for (i = 0; i < end; i++)
{
if (discards[i] == 2)
discards[i] = 0;
else if (discards[i] != 0)
{
register lin j;
lin length;
lin provisional = 0;
for (j = i; j < end; j++)
{
if (discards[j] == 0)
break;
if (discards[j] == 2)
++provisional;
}
while (j > i && discards[j - 1] == 2)
discards[--j] = 0, --provisional;
length = j - i;
if (provisional * 4 > length)
{
while (j > i)
if (discards[--j] == 2)
discards[j] = 0;
}
else
{
register lin consec;
lin minimum = 1;
lin tem = length >> 2;
while (0 < (tem >>= 2))
minimum <<= 1;
minimum++;
for (j = 0, consec = 0; j < length; j++)
if (discards[i + j] != 2)
consec = 0;
else if (minimum == ++consec)
j -= consec;
else if (minimum < consec)
discards[i + j] = 0;
for (j = 0, consec = 0; j < length; j++)
{
if (j >= 8 && discards[i + j] == 1)
break;
if (discards[i + j] == 2)
consec = 0, discards[i + j] = 0;
else if (discards[i + j] == 0)
consec = 0;
else
consec++;
if (consec == 3)
break;
}
i += length - 1;
for (j = 0, consec = 0; j < length; j++)
{
if (j >= 8 && discards[i - j] == 1)
break;
if (discards[i - j] == 2)
consec = 0, discards[i - j] = 0;
else if (discards[i - j] == 0)
consec = 0;
else
consec++;
if (consec == 3)
break;
}
}
}
}
}
for (f = 0; f < 2; f++)
{
char *discards = discarded[f];
lin end = filevec[f].buffered_lines;
lin j = 0;
for (i = 0; i < end; ++i)
if (minimal || discards[i] == 0)
{
filevec[f].undiscarded[j] = filevec[f].equivs[i];
filevec[f].realindexes[j++] = i;
}
else
filevec[f].changed[i] = 1;
filevec[f].nondiscarded_lines = j;
}
free (discarded[0]);
free (equiv_count[0]);
}
static void
shift_boundaries (struct file_data filevec[])
{
int f;
for (f = 0; f < 2; f++)
{
bool *changed = filevec[f].changed;
bool const *other_changed = filevec[1 - f].changed;
lin const *equivs = filevec[f].equivs;
lin i = 0;
lin j = 0;
lin i_end = filevec[f].buffered_lines;
while (1)
{
lin runlength, start, corresponding;
while (i < i_end && !changed[i])
{
while (other_changed[j++])
continue;
i++;
}
if (i == i_end)
break;
start = i;
while (changed[++i])
continue;
while (other_changed[j])
j++;
do
{
runlength = i - start;
while (start && equivs[start - 1] == equivs[i - 1])
{
changed[--start] = 1;
changed[--i] = 0;
while (changed[start - 1])
start--;
while (other_changed[--j])
continue;
}
corresponding = other_changed[j - 1] ? i : i_end;
while (i != i_end && equivs[start] == equivs[i])
{
changed[start++] = 0;
changed[i++] = 1;
while (changed[i])
i++;
while (other_changed[++j])
corresponding = i;
}
}
while (runlength != i - start);
while (corresponding < i)
{
changed[--start] = 1;
changed[--i] = 0;
while (other_changed[--j])
continue;
}
}
}
}
static struct change *
add_change (lin line0, lin line1, lin deleted, lin inserted,
struct change *old)
{
struct change *new = xmalloc (sizeof *new);
new->line0 = line0;
new->line1 = line1;
new->inserted = inserted;
new->deleted = deleted;
new->link = old;
return new;
}
static struct change *
build_reverse_script (struct file_data const filevec[])
{
struct change *script = 0;
bool *changed0 = filevec[0].changed;
bool *changed1 = filevec[1].changed;
lin len0 = filevec[0].buffered_lines;
lin len1 = filevec[1].buffered_lines;
lin i0 = 0, i1 = 0;
while (i0 < len0 || i1 < len1)
{
if (changed0[i0] | changed1[i1])
{
lin line0 = i0, line1 = i1;
while (changed0[i0]) ++i0;
while (changed1[i1]) ++i1;
script = add_change (line0, line1, i0 - line0, i1 - line1, script);
}
i0++, i1++;
}
return script;
}
static struct change *
build_script (struct file_data const filevec[])
{
struct change *script = 0;
bool *changed0 = filevec[0].changed;
bool *changed1 = filevec[1].changed;
lin i0 = filevec[0].buffered_lines, i1 = filevec[1].buffered_lines;
while (i0 >= 0 || i1 >= 0)
{
if (changed0[i0 - 1] | changed1[i1 - 1])
{
lin line0 = i0, line1 = i1;
while (changed0[i0 - 1]) --i0;
while (changed1[i1 - 1]) --i1;
script = add_change (i0, i1, line0 - i0, line1 - i1, script);
}
i0--, i1--;
}
return script;
}
static int
briefly_report (int changes, struct file_data const filevec[])
{
if (changes)
{
char const *label0 = file_label[0] ? file_label[0] : filevec[0].name;
char const *label1 = file_label[1] ? file_label[1] : filevec[1].name;
if (brief)
message ("Files %s and %s differ\n", label0, label1);
else
{
message ("Binary files %s and %s differ\n", label0, label1);
changes = 2;
}
}
return changes;
}
int
diff_2_files (struct comparison *cmp)
{
lin diags;
int f;
struct change *e, *p;
struct change *script;
int changes;
if (read_files (cmp->file, files_can_be_treated_as_binary))
{
if (cmp->file[0].stat.st_size != cmp->file[1].stat.st_size
&& (cmp->file[0].desc < 0 || S_ISREG (cmp->file[0].stat.st_mode))
&& (cmp->file[1].desc < 0 || S_ISREG (cmp->file[1].stat.st_mode)))
changes = 1;
else if (cmp->file[0].desc == cmp->file[1].desc)
changes = 0;
else
{
size_t lcm_max = PTRDIFF_MAX - 1;
size_t buffer_size =
buffer_lcm (sizeof (word),
buffer_lcm (STAT_BLOCKSIZE (cmp->file[0].stat),
STAT_BLOCKSIZE (cmp->file[1].stat),
lcm_max),
lcm_max);
for (f = 0; f < 2; f++)
cmp->file[f].buffer = xrealloc (cmp->file[f].buffer, buffer_size);
for (;; cmp->file[0].buffered = cmp->file[1].buffered = 0)
{
for (f = 0; f < 2; f++)
if (0 <= cmp->file[f].desc)
file_block_read (&cmp->file[f],
buffer_size - cmp->file[f].buffered);
if (cmp->file[0].buffered != cmp->file[1].buffered
|| memcmp (cmp->file[0].buffer,
cmp->file[1].buffer,
cmp->file[0].buffered))
{
changes = 1;
break;
}
if (cmp->file[0].buffered != buffer_size)
{
changes = 0;
break;
}
}
}
changes = briefly_report (changes, cmp->file);
}
else
{
size_t s = cmp->file[0].buffered_lines + cmp->file[1].buffered_lines + 4;
bool *flag_space = zalloc (s * sizeof *flag_space);
cmp->file[0].changed = flag_space + 1;
cmp->file[1].changed = flag_space + cmp->file[0].buffered_lines + 3;
discard_confusing_lines (cmp->file);
xvec = cmp->file[0].undiscarded;
yvec = cmp->file[1].undiscarded;
diags = (cmp->file[0].nondiscarded_lines
+ cmp->file[1].nondiscarded_lines + 3);
fdiag = xmalloc (diags * (2 * sizeof *fdiag));
bdiag = fdiag + diags;
fdiag += cmp->file[1].nondiscarded_lines + 1;
bdiag += cmp->file[1].nondiscarded_lines + 1;
too_expensive = 1;
for (; diags != 0; diags >>= 2)
too_expensive <<= 1;
too_expensive = MAX (256, too_expensive);
files[0] = cmp->file[0];
files[1] = cmp->file[1];
compareseq (0, cmp->file[0].nondiscarded_lines,
0, cmp->file[1].nondiscarded_lines, minimal);
free (fdiag - (cmp->file[1].nondiscarded_lines + 1));
shift_boundaries (cmp->file);
if (output_style == OUTPUT_ED)
script = build_reverse_script (cmp->file);
else
script = build_script (cmp->file);
if (ignore_blank_lines || ignore_regexp.fastmap)
{
struct change *next = script;
changes = 0;
while (next && changes == 0)
{
struct change *this, *end;
lin first0, last0, first1, last1;
this = next;
end = find_change (next);
next = end->link;
end->link = 0;
if (analyze_hunk (this, &first0, &last0, &first1, &last1))
changes = 1;
end->link = next;
}
}
else
changes = (script != 0);
if (brief)
changes = briefly_report (changes, cmp->file);
else
{
if (changes | !no_diff_means_no_output)
{
setup_output (file_label[0] ? file_label[0] : cmp->file[0].name,
file_label[1] ? file_label[1] : cmp->file[1].name,
cmp->parent != 0);
switch (output_style)
{
case OUTPUT_CONTEXT:
print_context_script (script, 0);
break;
case OUTPUT_UNIFIED:
print_context_script (script, 1);
break;
case OUTPUT_ED:
print_ed_script (script);
break;
case OUTPUT_FORWARD_ED:
pr_forward_ed_script (script);
break;
case OUTPUT_RCS:
print_rcs_script (script);
break;
case OUTPUT_NORMAL:
print_normal_script (script);
break;
case OUTPUT_IFDEF:
print_ifdef_script (script);
break;
case OUTPUT_SDIFF:
print_sdiff_script (script);
break;
default:
abort ();
}
finish_output ();
}
}
free (cmp->file[0].undiscarded);
free (flag_space);
for (f = 0; f < 2; f++)
{
free (cmp->file[f].equivs);
free (cmp->file[f].linbuf + cmp->file[f].linbuf_base);
}
for (e = script; e; e = p)
{
p = e->link;
free (e);
}
if (! ROBUST_OUTPUT_STYLE (output_style))
for (f = 0; f < 2; ++f)
if (cmp->file[f].missing_newline)
{
error (0, 0, "%s: %s\n",
file_label[f] ? file_label[f] : cmp->file[f].name,
_("No newline at end of file"));
changes = 2;
}
}
if (cmp->file[0].buffer != cmp->file[1].buffer)
free (cmp->file[0].buffer);
free (cmp->file[1].buffer);
return changes;
}