Page MenuHomeFreeBSD
Files F161899691

D36860.id111338.diff
No OneTemporary
Actions

D36860.id111338.diff
View Options

diff --git a/share/mk/src.libnames.mk b/share/mk/src.libnames.mk
--- a/share/mk/src.libnames.mk
+++ b/share/mk/src.libnames.mk
@@ -44,6 +44,7 @@
bsnmptools \
c_nossp_pic \
cron \
+ diff \
elftc \
fifolog \
ifconfig \
@@ -532,6 +533,9 @@
LIBELFTCDIR= ${_LIB_OBJTOP}/lib/libelftc
LIBELFTC?= ${LIBELFTCDIR}/libelftc${PIE_SUFFIX}.a
+LIBDIFFDIR= ${_LIB_OBJTOP}/usr.bin/diff/lib
+LIBDIFF?= ${LIBDIFFDIR}/libdiff${PIE_SUFFIX}.a
+
LIBLUADIR= ${_LIB_OBJTOP}/lib/liblua
LIBLUA?= ${LIBLUADIR}/liblua${PIE_SUFFIX}.a
diff --git a/usr.bin/diff/Makefile b/usr.bin/diff/Makefile
--- a/usr.bin/diff/Makefile
+++ b/usr.bin/diff/Makefile
@@ -3,8 +3,10 @@
.include <src.opts.mk>
PROG= diff
-SRCS= diff.c diffdir.c diffreg.c xmalloc.c pr.c
-LIBADD= m
+SRCS= diff.c diffdir.c diffreg.c xmalloc.c pr.c diffreg_new.c
+
+LIBADD= m diff
+CFLAGS+= -I${.CURDIR} -I${.CURDIR}/lib
HAS_TESTS=
SUBDIR.${MK_TESTS}+= tests
diff --git a/usr.bin/diff/diff.h b/usr.bin/diff/diff.h
--- a/usr.bin/diff/diff.h
+++ b/usr.bin/diff/diff.h
@@ -54,6 +54,14 @@
#define D_UNSET -2
+/*
+ * Algorithms
+ */
+
+#define D_DIFFNONE 0
+#define D_DIFFSTONE 1 /* Stone or 'old diff' algorithm */
+#define D_DIFFMYERS 2 /* Myers diff algorithm */
+#define D_DIFFPATIENCE 3 /* Patience diff algorithm */
/*
* Output flags
@@ -76,6 +84,9 @@
#define D_SKIPBLANKLINES 0x800 /* Skip blank lines */
#define D_MATCHLAST 0x1000 /* Display last line matching provided regex */
+/* Features supported by new algorithms */
+#define D_NEWALGO_FLAGS (D_FORCEASCII | D_PROTOTYPE | D_IGNOREBLANKS)
+
/*
* Status values for print_status() and diffreg() return values
*/
@@ -101,8 +112,8 @@
};
extern bool lflag, Nflag, Pflag, rflag, sflag, Tflag, cflag;
-extern bool ignore_file_case, suppress_common, color, noderef;
-extern int diff_format, diff_context, status;
+extern bool ignore_file_case, suppress_common, color, noderef, algorithm_set;
+extern int diff_format, diff_context, diff_algorithm, status;
extern int tabsize, width;
extern char *start, *ifdefname, *diffargs, *label[2];
extern char *ignore_pats, *most_recent_pat;
@@ -113,5 +124,6 @@
extern regex_t ignore_re, most_recent_re;
int diffreg(char *, char *, int, int);
+int diffreg_new(char *, char *, int, int);
void diffdir(char *, char *, int);
void print_status(int, char *, char *, const char *);
diff --git a/usr.bin/diff/diff.1 b/usr.bin/diff/diff.1
--- a/usr.bin/diff/diff.1
+++ b/usr.bin/diff/diff.1
@@ -30,7 +30,7 @@
.\" @(#)diff.1 8.1 (Berkeley) 6/30/93
.\" $FreeBSD$
.\"
-.Dd March 10, 2022
+.Dd October 3, 2022
.Dt DIFF 1
.Os
.Sh NAME
@@ -43,6 +43,7 @@
.Fl c | e | f |
.Fl n | q | u | y
.Oc
+.Op Fl A Ar algo | Fl -algorithm Ar algo
.Op Fl -brief
.Op Fl -color Ns = Ns Ar when
.Op Fl -changed-group-format Ar GFMT
@@ -70,6 +71,7 @@
.Ar file1 file2
.Nm diff
.Op Fl aBbdilpTtw
+.Op Fl A Ar algo | Fl -algorithm Ar algo
.Op Fl I Ar pattern | Fl -ignore-matching-lines Ar pattern
.Op Fl F Ar pattern | Fl -show-function-line Ar pattern
.Op Fl L Ar label | Fl -label Ar label
@@ -98,6 +100,7 @@
.Ar file1 file2
.Nm diff
.Op Fl aBbdiltw
+.Op Fl A Ar algo | Fl -algorithm Ar algo
.Op Fl I Ar pattern | Fl -ignore-matching-lines Ar pattern
.Op Fl -brief
.Op Fl -color Ns = Ns Ar when
@@ -124,6 +127,7 @@
.Ar file1 file2
.Nm diff
.Op Fl aBbdilpTtw
+.Op Fl A Ar algo | Fl -algorithm Ar algo
.Op Fl I Ar pattern | Fl -ignore-matching-lines Ar pattern
.Op Fl F Ar pattern | Fl -show-function-line Ar pattern
.Op Fl L Ar label | Fl -label Ar label
@@ -156,6 +160,7 @@
.Fl c | e | f |
.Fl n | q | u
.Oc
+.Op Fl A Ar algo | Fl -algorithm Ar algo
.Op Fl -brief
.Op Fl -color Ns = Ns Ar when
.Op Fl -changed-group-format Ar GFMT
@@ -334,6 +339,34 @@
.Pp
Comparison options:
.Bl -tag -width Ds
+.It Fl A Ar algo, Fl -algorithm Ar algo
+Select the algorithm to be used when comparing files.
+.Nm
+supports 3 algorithms:
+.Pp
+.Bl -tag -width Ds -compact
+.It Cm myers
+Myers diff algorithm performs a O(ND) comparison between the two files.
+An optimisation is present when worst case files are detected it causes the
+Myers algorithm to bails out and produces correct, but non-optimal diff output.
+.It Cm patience
+The patience variant of the Myers algorithm, this variant attempts to create
+more aesthetically pleasing diff output by logically grouping lines.
+.It Cm stone
+The Stone algorithm looks for the longest common subsequence between compared files.
+Stone encounters worst case performance when there are long common subsequences.
+In large files this can lead to a significant performance impact.
+The Stone algorithm is maintained for compatibility.
+.El
+.Pp
+With no argument
+.Nm
+defaults the diff algorithm to Myers, but will fall back to the Stone
+algorithm if the input or output options are not supported by libdiff.
+If the algorithm is selected
+.Nm
+will not fallback if the algorithm cannot be supported and will instead return
+an error.
.It Fl a -text
Treat all files as ASCII text.
Normally
@@ -742,3 +775,6 @@
.Nm
command appeared in
.At v6 .
+.Pp
+libdiff was imported from the Game of Trees version control system and the
+default algorithm was changed to Myers in FreeBSD 14.
diff --git a/usr.bin/diff/diff.c b/usr.bin/diff/diff.c
--- a/usr.bin/diff/diff.c
+++ b/usr.bin/diff/diff.c
@@ -40,9 +40,9 @@
static const char diff_version[] = "FreeBSD diff 20220309";
bool lflag, Nflag, Pflag, rflag, sflag, Tflag, cflag;
-bool ignore_file_case, suppress_common, color, noderef;
+bool ignore_file_case, suppress_common, color, noderef, algorithm_set;
static bool help = false;
-int diff_format, diff_context, status;
+int diff_format, diff_context, diff_algorithm, status;
int tabsize = 8, width = 130;
static int colorflag = COLORFLAG_NEVER;
char *start, *ifdefname, *diffargs, *label[2];
@@ -53,7 +53,17 @@
struct excludes *excludes_list;
regex_t ignore_re, most_recent_re;
-#define OPTIONS "0123456789aBbC:cdD:efF:HhI:iL:lnNPpqrS:sTtU:uwW:X:x:y"
+static struct algorithm {
+ const char *name;
+ int id;
+} algorithms[] = {
+ {"stone", D_DIFFSTONE},
+ {"myers", D_DIFFMYERS},
+ {"patience", D_DIFFPATIENCE},
+ {NULL, D_DIFFNONE}
+};
+
+#define OPTIONS "0123456789A:aBbC:cdD:efF:HhI:iL:lnNPpqrS:sTtU:uwW:X:x:y"
enum {
OPT_TSIZE = CHAR_MAX + 1,
OPT_STRIPCR,
@@ -70,6 +80,7 @@
};
static struct option longopts[] = {
+ { "algorithm", required_argument, 0, 'A' },
{ "text", no_argument, 0, 'a' },
{ "ignore-space-change", no_argument, 0, 'b' },
{ "context", optional_argument, 0, 'C' },
@@ -141,6 +152,7 @@
newarg = 1;
diff_context = 3;
diff_format = D_UNSET;
+ diff_algorithm = D_DIFFMYERS;
#define FORMAT_MISMATCHED(type) \
(diff_format != D_UNSET && diff_format != (type))
while ((ch = getopt_long(argc, argv, OPTIONS, longopts, NULL)) != -1) {
@@ -155,6 +167,21 @@
usage();
diff_context = (diff_context * 10) + (ch - '0');
break;
+ case 'A':
+ algorithm_set = true;
+ diff_algorithm = D_DIFFNONE;
+ for (struct algorithm *a = algorithms; a->name;a++) {
+ if(strcasecmp(optarg, a->name) == 0) {
+ diff_algorithm = a->id;
+ break;
+ }
+ }
+
+ if (diff_algorithm == D_DIFFNONE) {
+ printf("unknown algorithm: %s\n", optarg);
+ usage();
+ }
+ break;
case 'a':
dflags |= D_FORCEASCII;
break;
diff --git a/usr.bin/diff/diffreg.c b/usr.bin/diff/diffreg.c
--- a/usr.bin/diff/diffreg.c
+++ b/usr.bin/diff/diffreg.c
@@ -172,6 +172,7 @@
enum readhash { RH_BINARY, RH_OK, RH_EOF };
#define MIN_PAD 1
+static int diffreg_stone(char *, char *, int, int);
static FILE *opentemp(const char *);
static void output(char *, FILE *, char *, FILE *, int);
static void check(FILE *, FILE *, int);
@@ -228,6 +229,45 @@
static int lastline;
static int lastmatchline;
+int
+diffreg(char *file1, char *file2, int flags, int capsicum)
+{
+ /* First check if have picked the stone algorithm. */
+ if (diff_algorithm == D_DIFFSTONE)
+ return diffreg_stone(file1, file2, flags, capsicum);
+
+ /*
+ * We can't use fifos with libdiff yet. DO NOT fallback to stone if we
+ * selected the algorithm explicitly.
+ */
+ if (S_ISFIFO(stb1.st_mode) || S_ISFIFO(stb2.st_mode)) {
+ if (algorithm_set)
+ err(2, "unable to use selected algorithm with requested options");
+ else
+ return diffreg_stone(file1, file2, flags, capsicum);
+ }
+
+ /* Is this one of the supported input/output modes for diffreg_new? */
+ if ((flags == 0 || !(flags & ~D_NEWALGO_FLAGS)) && (
+ diff_format == D_NORMAL ||
+#if 0
+ diff_format == D_EDIT ||
+#endif
+ diff_format == D_UNIFIED) &&
+ (diff_algorithm == D_DIFFMYERS || diff_algorithm == D_DIFFPATIENCE)) {
+ return diffreg_new(file1, file2, flags, capsicum);
+ }
+ /*
+ * If the algorithm was set explicitly and we can't support it DO NOT
+ * fallback to stone.
+ */
+ if (algorithm_set)
+ err(2, "unable to use selected algorithm with requested options");
+
+ /* Fallback to using stone. */
+ return diffreg_stone(file1, file2, flags, capsicum);
+}
+
static int
clow2low(int c)
{
@@ -243,7 +283,7 @@
}
int
-diffreg(char *file1, char *file2, int flags, int capsicum)
+diffreg_stone(char *file1, char *file2, int flags, int capsicum)
{
FILE *f1, *f2;
int i, rval;
diff --git a/usr.bin/diff/diffreg_new.c b/usr.bin/diff/diffreg_new.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/diffreg_new.c
@@ -0,0 +1,295 @@
+/*
+ * Copyright (c) 2018 Martin Pieuchot
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <sys/capsicum.h>
+#include <sys/mman.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+
+#include <capsicum_helpers.h>
+#include <err.h>
+#include <fcntl.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <string.h>
+#include <unistd.h>
+
+#include "diff.h"
+#include <arraylist.h>
+#include <diff_main.h>
+#include <diff_output.h>
+
+const char *format_label(const char *, struct stat *);
+
+enum diffreg_algo {
+ DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE = 0,
+ DIFFREG_ALGO_MYERS_THEN_PATIENCE = 1,
+ DIFFREG_ALGO_PATIENCE = 2,
+ DIFFREG_ALGO_NONE = 3,
+};
+
+int diffreg_new(char *, char *, int, int);
+FILE * openfile(const char *, char **, struct stat *);
+
+static const struct diff_algo_config myers_then_patience;
+static const struct diff_algo_config myers_then_myers_divide;
+static const struct diff_algo_config patience;
+static const struct diff_algo_config myers_divide;
+
+static const struct diff_algo_config myers_then_patience = (struct diff_algo_config){
+ .impl = diff_algo_myers,
+ .permitted_state_size = 1024 * 1024 * sizeof(int),
+ .fallback_algo = &patience,
+};
+
+static const struct diff_algo_config myers_then_myers_divide =
+ (struct diff_algo_config){
+ .impl = diff_algo_myers,
+ .permitted_state_size = 1024 * 1024 * sizeof(int),
+ .fallback_algo = &myers_divide,
+};
+
+static const struct diff_algo_config patience = (struct diff_algo_config){
+ .impl = diff_algo_patience,
+ /* After subdivision, do Patience again: */
+ .inner_algo = &patience,
+ /* If subdivision failed, do Myers Divide et Impera: */
+ .fallback_algo = &myers_then_myers_divide,
+};
+
+static const struct diff_algo_config myers_divide = (struct diff_algo_config){
+ .impl = diff_algo_myers_divide,
+ /* When division succeeded, start from the top: */
+ .inner_algo = &myers_then_myers_divide,
+ /* (fallback_algo = NULL implies diff_algo_none). */
+};
+
+static const struct diff_algo_config no_algo = (struct diff_algo_config){
+ .impl = diff_algo_none,
+};
+
+/* If the state for a forward-Myers is small enough, use Myers, otherwise first
+ * do a Myers-divide. */
+static const struct diff_config diff_config_myers_then_myers_divide = {
+ .atomize_func = diff_atomize_text_by_line,
+ .algo = &myers_then_myers_divide,
+};
+
+/* If the state for a forward-Myers is small enough, use Myers, otherwise first
+ * do a Patience. */
+static const struct diff_config diff_config_myers_then_patience = {
+ .atomize_func = diff_atomize_text_by_line,
+ .algo = &myers_then_patience,
+};
+
+/* Directly force Patience as a first divider of the source file. */
+static const struct diff_config diff_config_patience = {
+ .atomize_func = diff_atomize_text_by_line,
+ .algo = &patience,
+};
+
+/* Directly force Patience as a first divider of the source file. */
+static const struct diff_config diff_config_no_algo = {
+ .atomize_func = diff_atomize_text_by_line,
+};
+
+const char *
+format_label(const char *oldlabel, struct stat *stb)
+{
+ const char *time_format = "%Y-%m-%d %H:%M:%S";
+ char *newlabel;
+ char buf[256];
+ char end[10];
+ struct tm tm, *tm_ptr;
+ int nsec = stb->st_mtim.tv_nsec;
+ size_t newlabellen, timelen, endlen;
+ tm_ptr = localtime_r(&stb->st_mtime, &tm);
+
+ timelen = strftime(buf, 256, time_format, tm_ptr);
+ endlen = strftime(end, 10, "%z", tm_ptr);
+
+ /*
+ * The new label is the length of the time, old label, timezone,
+ * 9 characters for nanoseconds, and 4 characters for a period
+ * and for formatting.
+ */
+ newlabellen = timelen + strlen(oldlabel) + endlen + 9 + 4;
+ newlabel = calloc(newlabellen, sizeof(char));
+
+ snprintf(newlabel, newlabellen ,"%s\t%s.%.9d %s\n",
+ oldlabel, buf, nsec, end);
+
+ return newlabel;
+}
+
+int
+diffreg_new(char *file1, char *file2, int flags, int capsicum)
+{
+ char *str1, *str2;
+ FILE *f1, *f2;
+ struct stat st1, st2;
+ struct diff_input_info info;
+ struct diff_data left = {}, right = {};
+ struct diff_result *result = NULL;
+ bool force_text, have_binary;
+ int rc, atomizer_flags, rflags, diff_flags = 0;
+ int context_lines = diff_context;
+ const struct diff_config *cfg;
+ enum diffreg_algo algo;
+ cap_rights_t rights_ro;
+
+ algo = DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE;
+
+ switch (algo) {
+ default:
+ case DIFFREG_ALGO_MYERS_THEN_MYERS_DIVIDE:
+ cfg = &diff_config_myers_then_myers_divide;
+ break;
+ case DIFFREG_ALGO_MYERS_THEN_PATIENCE:
+ cfg = &diff_config_myers_then_patience;
+ break;
+ case DIFFREG_ALGO_PATIENCE:
+ cfg = &diff_config_patience;
+ break;
+ case DIFFREG_ALGO_NONE:
+ cfg = &diff_config_no_algo;
+ break;
+ }
+
+ f1 = openfile(file1, &str1, &st1);
+ f2 = openfile(file2, &str2, &st2);
+
+ if (capsicum) {
+ cap_rights_init(&rights_ro, CAP_READ, CAP_FSTAT, CAP_SEEK);
+ if (caph_rights_limit(fileno(f1), &rights_ro) < 0)
+ err(2, "unable to limit rights on: %s", file1);
+ if (caph_rights_limit(fileno(f2), &rights_ro) < 0)
+ err(2, "unable to limit rights on: %s", file2);
+ if (fileno(f1) == STDIN_FILENO || fileno(f2) == STDIN_FILENO) {
+ /* stdin has already been limited */
+ if (caph_limit_stderr() == -1)
+ err(2, "unable to limit stderr");
+ if (caph_limit_stdout() == -1)
+ err(2, "unable to limit stdout");
+ } else if (caph_limit_stdio() == -1)
+ err(2, "unable to limit stdio");
+ caph_cache_catpages();
+ caph_cache_tzdata();
+ if (caph_enter() < 0)
+ err(2, "unable to enter capability mode");
+ }
+
+ /*
+ * If we have been given a label use that for the paths, if not format
+ * the path with the files modification time.
+ */
+ info.flags = 0;
+ info.left_path = (label[0] != NULL) ?
+ label[0] : format_label(file1, &stb1);
+ info.right_path = (label[1] != NULL) ?
+ label[1] : format_label(file2, &stb2);
+
+ if (flags & D_FORCEASCII)
+ diff_flags |= DIFF_FLAG_FORCE_TEXT_DATA;
+ if (flags & D_IGNOREBLANKS)
+ diff_flags |= DIFF_FLAG_IGNORE_WHITESPACE;
+ if (flags & D_PROTOTYPE)
+ diff_flags |= DIFF_FLAG_SHOW_PROTOTYPES;
+
+ rc = diff_atomize_file(&left, cfg, f1, str1, st1.st_size, diff_flags);
+ if (rc)
+ goto done;
+ rc = diff_atomize_file(&right, cfg, f2, str2, st2.st_size, diff_flags);
+ if (rc)
+ goto done;
+
+ result = diff_main(cfg, &left, &right);
+ if (result->rc != DIFF_RC_OK) {
+ rc = D_ERROR;
+ status |= 2;
+ goto done;
+ }
+ /*
+ * If there wasn't an error, but we don't have any printable chunks
+ * then the files must match.
+ */
+ if (!diff_printable_chunks(result)) {
+ rc = D_SAME;
+ goto done;
+ }
+
+ atomizer_flags = (result->left->atomizer_flags | result->right->atomizer_flags);
+ rflags = (result->left->root->diff_flags | result->right->root->diff_flags);
+ force_text = (rflags & DIFF_FLAG_FORCE_TEXT_DATA);
+ have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA);
+
+ if (have_binary && !force_text) {
+ rc = D_BINARY;
+ status |= 1;
+ goto done;
+ }
+
+ if (diff_format == D_NORMAL) {
+ rc = diff_output_plain(NULL, stdout, &info, result);
+ } else if (diff_format == D_EDIT) {
+ rc = diff_output_edscript(NULL, stdout, &info, result);
+ } else {
+ rc = diff_output_unidiff(NULL, stdout, &info, result,
+ context_lines);
+ }
+ if (rc != DIFF_RC_OK) {
+ rc = D_ERROR;
+ status |= 2;
+ } else {
+ status |= 1;
+ }
+done:
+ diff_result_free(result);
+ diff_data_free(&left);
+ diff_data_free(&right);
+ if (str1)
+ munmap(str1, st1.st_size);
+ if (str2)
+ munmap(str2, st2.st_size);
+ fclose(f1);
+ fclose(f2);
+
+ return rc;
+}
+
+FILE *
+openfile(const char *path, char **p, struct stat *st)
+{
+ FILE *f = NULL;
+
+ f = fopen(path, "r");
+ if (f == NULL)
+ err(2, "%s", path);
+
+ if (fstat(fileno(f), st) == -1)
+ err(2, "%s", path);
+
+#ifndef DIFF_NO_MMAP
+ *p = mmap(NULL, st->st_size, PROT_READ, MAP_PRIVATE, fileno(f), 0);
+ if (*p == MAP_FAILED)
+#endif
+ *p = NULL; /* fall back on file I/O */
+
+ return f;
+}
diff --git a/usr.bin/diff/lib/Makefile b/usr.bin/diff/lib/Makefile
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/Makefile
@@ -0,0 +1,15 @@
+# $FreeBSD$
+
+LIB= diff
+INTERNALLIB= # API not published or supported.
+
+SRCS= diff_atomize_text.c diff_main.c diff_myers.c \
+ diff_patience.c diff_output.c diff_output_plain.c \
+ diff_output_unidiff.c diff_output_edscript.c recallocarray.c
+
+WARNS=
+CFLAGS+= -I${.CURDIR}
+
+#NO_WMISSING_VARIABLE_DECLARATIONS=
+
+.include <bsd.lib.mk>
diff --git a/usr.bin/diff/lib/arraylist.h b/usr.bin/diff/lib/arraylist.h
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/arraylist.h
@@ -0,0 +1,120 @@
+/* Auto-reallocating array for arbitrary member types. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+
+/* Usage:
+ *
+ * ARRAYLIST(any_type_t) list;
+ * // OR
+ * typedef ARRAYLIST(any_type_t) any_type_list_t;
+ * any_type_list_t list;
+ *
+ * // pass the number of (at first unused) members to add on each realloc:
+ * ARRAYLIST_INIT(list, 128);
+ * any_type_t *x;
+ * while (bar) {
+ * // This enlarges the allocated array as needed;
+ * // list.head may change due to realloc:
+ * ARRAYLIST_ADD(x, list);
+ * if (!x)
+ * return ENOMEM;
+ * *x = random_foo_value;
+ * }
+ * for (i = 0; i < list.len; i++)
+ * printf("%s", foo_to_str(list.head[i]));
+ * ARRAYLIST_FREE(list);
+ */
+#define ARRAYLIST(MEMBER_TYPE) \
+ struct { \
+ MEMBER_TYPE *head; \
+ MEMBER_TYPE *p; \
+ unsigned int len; \
+ unsigned int allocated; \
+ unsigned int alloc_blocksize; \
+ }
+
+#define ARRAYLIST_INIT(ARRAY_LIST, ALLOC_BLOCKSIZE) do { \
+ (ARRAY_LIST).head = NULL; \
+ (ARRAY_LIST).len = 0; \
+ (ARRAY_LIST).allocated = 0; \
+ (ARRAY_LIST).alloc_blocksize = ALLOC_BLOCKSIZE; \
+ } while(0)
+
+#define ARRAYLIST_ADD(NEW_ITEM_P, ARRAY_LIST) do { \
+ if ((ARRAY_LIST).len && !(ARRAY_LIST).allocated) { \
+ NEW_ITEM_P = NULL; \
+ break; \
+ } \
+ if ((ARRAY_LIST).head == NULL \
+ || (ARRAY_LIST).allocated < (ARRAY_LIST).len + 1) { \
+ (ARRAY_LIST).p = recallocarray((ARRAY_LIST).head, \
+ (ARRAY_LIST).len, \
+ (ARRAY_LIST).allocated + \
+ ((ARRAY_LIST).allocated ? \
+ (ARRAY_LIST).allocated / 2 : \
+ (ARRAY_LIST).alloc_blocksize ? : 8), \
+ sizeof(*(ARRAY_LIST).head)); \
+ if ((ARRAY_LIST).p == NULL) { \
+ NEW_ITEM_P = NULL; \
+ break; \
+ } \
+ (ARRAY_LIST).allocated += \
+ (ARRAY_LIST).allocated ? \
+ (ARRAY_LIST).allocated / 2 : \
+ (ARRAY_LIST).alloc_blocksize ? : 8, \
+ (ARRAY_LIST).head = (ARRAY_LIST).p; \
+ (ARRAY_LIST).p = NULL; \
+ }; \
+ if ((ARRAY_LIST).head == NULL \
+ || (ARRAY_LIST).allocated < (ARRAY_LIST).len + 1) { \
+ NEW_ITEM_P = NULL; \
+ break; \
+ } \
+ (NEW_ITEM_P) = &(ARRAY_LIST).head[(ARRAY_LIST).len]; \
+ (ARRAY_LIST).len++; \
+ } while (0)
+
+#define ARRAYLIST_INSERT(NEW_ITEM_P, ARRAY_LIST, AT_IDX) do { \
+ int _at_idx = (AT_IDX); \
+ ARRAYLIST_ADD(NEW_ITEM_P, ARRAY_LIST); \
+ if ((NEW_ITEM_P) \
+ && _at_idx >= 0 \
+ && _at_idx < (ARRAY_LIST).len) { \
+ memmove(&(ARRAY_LIST).head[_at_idx + 1], \
+ &(ARRAY_LIST).head[_at_idx], \
+ ((ARRAY_LIST).len - 1 - _at_idx) \
+ * sizeof(*(ARRAY_LIST).head)); \
+ (NEW_ITEM_P) = &(ARRAY_LIST).head[_at_idx]; \
+ }; \
+ } while (0)
+
+#define ARRAYLIST_CLEAR(ARRAY_LIST) \
+ (ARRAY_LIST).len = 0
+
+#define ARRAYLIST_FREE(ARRAY_LIST) \
+ do { \
+ if ((ARRAY_LIST).head && (ARRAY_LIST).allocated) \
+ free((ARRAY_LIST).head); \
+ ARRAYLIST_INIT(ARRAY_LIST, (ARRAY_LIST).alloc_blocksize); \
+ } while(0)
+
+#define ARRAYLIST_FOREACH(ITEM_P, ARRAY_LIST) \
+ for ((ITEM_P) = (ARRAY_LIST).head; \
+ (ITEM_P) - (ARRAY_LIST).head < (ARRAY_LIST).len; \
+ (ITEM_P)++)
+
+#define ARRAYLIST_IDX(ITEM_P, ARRAY_LIST) ((ITEM_P) - (ARRAY_LIST).head)
diff --git a/usr.bin/diff/lib/diff_atomize_text.c b/usr.bin/diff/lib/diff_atomize_text.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_atomize_text.c
@@ -0,0 +1,197 @@
+/* Split source by line breaks, and calculate a simplistic checksum. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <ctype.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+
+#include "diff_internal.h"
+#include "diff_debug.h"
+
+unsigned int
+diff_atom_hash_update(unsigned int hash, unsigned char atom_byte)
+{
+ return hash * 23 + atom_byte;
+}
+
+static int
+diff_data_atomize_text_lines_fd(struct diff_data *d)
+{
+ off_t pos = 0;
+ const off_t end = pos + d->len;
+ unsigned int array_size_estimate = d->len / 50;
+ unsigned int pow2 = 1;
+ bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE);
+ bool embedded_nul = false;
+
+ while (array_size_estimate >>= 1)
+ pow2++;
+
+ ARRAYLIST_INIT(d->atoms, 1 << pow2);
+
+ if (fseek(d->root->f, 0L, SEEK_SET) == -1)
+ return errno;
+
+ while (pos < end) {
+ off_t line_end = pos;
+ unsigned int hash = 0;
+ unsigned char buf[512];
+ size_t r, i;
+ struct diff_atom *atom;
+ int eol = 0;
+
+ while (eol == 0 && line_end < end) {
+ r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
+ if (r == 0 && ferror(d->root->f))
+ return errno;
+ i = 0;
+ while (eol == 0 && i < r) {
+ if (buf[i] != '\r' && buf[i] != '\n') {
+ if (!ignore_whitespace
+ || !isspace(buf[i]))
+ hash = diff_atom_hash_update(
+ hash, buf[i]);
+ if (buf[i] == '\0')
+ embedded_nul = true;
+ line_end++;
+ } else
+ eol = buf[i];
+ i++;
+ }
+ }
+
+ /* When not at the end of data, the line ending char ('\r' or
+ * '\n') must follow */
+ if (line_end < end)
+ line_end++;
+ /* If that was an '\r', also pull in any following '\n' */
+ if (line_end < end && eol == '\r') {
+ if (fseeko(d->root->f, line_end, SEEK_SET) == -1)
+ return errno;
+ r = fread(buf, sizeof(char), sizeof(buf), d->root->f);
+ if (r == 0 && ferror(d->root->f))
+ return errno;
+ if (r > 0 && buf[0] == '\n')
+ line_end++;
+ }
+
+ /* Record the found line as diff atom */
+ ARRAYLIST_ADD(atom, d->atoms);
+ if (!atom)
+ return ENOMEM;
+
+ *atom = (struct diff_atom){
+ .root = d,
+ .pos = pos,
+ .at = NULL, /* atom data is not memory-mapped */
+ .len = line_end - pos,
+ .hash = hash,
+ };
+
+ /* Starting point for next line: */
+ pos = line_end;
+ if (fseeko(d->root->f, pos, SEEK_SET) == -1)
+ return errno;
+ }
+
+ /* File are considered binary if they contain embedded '\0' bytes. */
+ if (embedded_nul)
+ d->atomizer_flags |= DIFF_ATOMIZER_FOUND_BINARY_DATA;
+
+ return DIFF_RC_OK;
+}
+
+static int
+diff_data_atomize_text_lines_mmap(struct diff_data *d)
+{
+ const uint8_t *pos = d->data;
+ const uint8_t *end = pos + d->len;
+ bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE);
+ bool embedded_nul = false;
+ unsigned int array_size_estimate = d->len / 50;
+ unsigned int pow2 = 1;
+ while (array_size_estimate >>= 1)
+ pow2++;
+
+ ARRAYLIST_INIT(d->atoms, 1 << pow2);
+
+ while (pos < end) {
+ const uint8_t *line_end = pos;
+ unsigned int hash = 0;
+
+ while (line_end < end && *line_end != '\r' && *line_end != '\n') {
+ if (!ignore_whitespace
+ || !isspace(*line_end))
+ hash = diff_atom_hash_update(hash, *line_end);
+ if (*line_end == '\0')
+ embedded_nul = true;
+ line_end++;
+ }
+
+ /* When not at the end of data, the line ending char ('\r' or
+ * '\n') must follow */
+ if (line_end < end && *line_end == '\r')
+ line_end++;
+ if (line_end < end && *line_end == '\n')
+ line_end++;
+
+ /* Record the found line as diff atom */
+ struct diff_atom *atom;
+ ARRAYLIST_ADD(atom, d->atoms);
+ if (!atom)
+ return ENOMEM;
+
+ *atom = (struct diff_atom){
+ .root = d,
+ .pos = (off_t)(pos - d->data),
+ .at = pos,
+ .len = line_end - pos,
+ .hash = hash,
+ };
+
+ /* Starting point for next line: */
+ pos = line_end;
+ }
+
+ /* File are considered binary if they contain embedded '\0' bytes. */
+ if (embedded_nul)
+ d->atomizer_flags |= DIFF_ATOMIZER_FOUND_BINARY_DATA;
+
+ return DIFF_RC_OK;
+}
+
+static int
+diff_data_atomize_text_lines(struct diff_data *d)
+{
+ if (d->data == NULL)
+ return diff_data_atomize_text_lines_fd(d);
+ else
+ return diff_data_atomize_text_lines_mmap(d);
+}
+
+int
+diff_atomize_text_by_line(void *func_data, struct diff_data *d)
+{
+ return diff_data_atomize_text_lines(d);
+}
diff --git a/usr.bin/diff/lib/diff_debug.h b/usr.bin/diff/lib/diff_debug.h
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_debug.h
@@ -0,0 +1,228 @@
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#define DEBUG 0
+
+#if DEBUG
+#include <stdio.h>
+#include <unistd.h>
+#define print(args...) fprintf(stderr, ##args)
+#define debug print
+#define debug_dump dump
+#define debug_dump_atom dump_atom
+#define debug_dump_atoms dump_atoms
+
+static inline void
+print_atom_byte(unsigned char c) {
+ if (c == '\r')
+ print("\\r");
+ else if (c == '\n')
+ print("\\n");
+ else if ((c < 32 || c >= 127) && (c != '\t'))
+ print("\\x%02x", c);
+ else
+ print("%c", c);
+}
+
+static inline void
+dump_atom(const struct diff_data *left, const struct diff_data *right,
+ const struct diff_atom *atom)
+{
+ if (!atom) {
+ print("NULL atom\n");
+ return;
+ }
+ if (left)
+ print(" %3u '", diff_atom_root_idx(left, atom));
+
+ if (atom->at == NULL) {
+ off_t remain = atom->len;
+ if (fseek(atom->root->f, atom->pos, SEEK_SET) == -1)
+ abort(); /* cannot return error */
+ while (remain > 0) {
+ char buf[16];
+ size_t r;
+ int i;
+ r = fread(buf, 1, MIN(remain, sizeof(buf)),
+ atom->root->f);
+ if (r == -1)
+ abort(); /* cannot return error */
+ if (r == 0)
+ break;
+ remain -= r;
+ for (i = 0; i < r; i++)
+ print_atom_byte(buf[i]);
+ }
+ } else {
+ const char *s;
+ for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
+ print_atom_byte(*s);
+ }
+ print("'\n");
+}
+
+static inline void
+dump_atoms(const struct diff_data *d, struct diff_atom *atom,
+ unsigned int count)
+{
+ if (count > 42) {
+ dump_atoms(d, atom, 20);
+ print("[%u lines skipped]\n", count - 20 - 20);
+ dump_atoms(d, atom + count - 20, 20);
+ return;
+ } else {
+ struct diff_atom *i;
+ foreach_diff_atom(i, atom, count) {
+ dump_atom(d, NULL, i);
+ }
+ }
+}
+
+static inline void
+dump(struct diff_data *d)
+{
+ dump_atoms(d, d->atoms.head, d->atoms.len);
+}
+
+/* kd is a quadratic space myers matrix from the original Myers algorithm.
+ * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
+ * Divide algorithm.
+ */
+static inline void
+dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
+ int *kd, int *kd_forward, int kd_forward_d,
+ int *kd_backward, int kd_backward_d)
+{
+ #define COLOR_YELLOW "\033[1;33m"
+ #define COLOR_GREEN "\033[1;32m"
+ #define COLOR_BLUE "\033[1;34m"
+ #define COLOR_RED "\033[1;31m"
+ #define COLOR_END "\033[0;m"
+ int x;
+ int y;
+ print(" ");
+ for (x = 0; x <= l->atoms.len; x++)
+ print("%2d", x % 100);
+ print("\n");
+
+ for (y = 0; y <= r->atoms.len; y++) {
+ print("%3d ", y);
+ for (x = 0; x <= l->atoms.len; x++) {
+
+ /* print d advancements from kd, if any. */
+ char label = 'o';
+ char *color = NULL;
+ if (kd) {
+ int max = l->atoms.len + r->atoms.len;
+ size_t kd_len = max + 1 + max;
+ int *kd_pos = kd;
+ int di;
+#define xk_to_y(X, K) ((X) - (K))
+ for (di = 0; di < max; di++) {
+ int ki;
+ for (ki = di; ki >= -di; ki -= 2) {
+ if (x != kd_pos[ki]
+ || y != xk_to_y(x, ki))
+ continue;
+ label = '0' + (di % 10);
+ color = COLOR_YELLOW;
+ break;
+ }
+ if (label != 'o')
+ break;
+ kd_pos += kd_len;
+ }
+ }
+ if (kd_forward && kd_forward_d >= 0) {
+#define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
+ int ki;
+ for (ki = kd_forward_d;
+ ki >= -kd_forward_d;
+ ki -= 2) {
+ if (x != kd_forward[ki])
+ continue;
+ if (y != xk_to_y(x, ki))
+ continue;
+ label = 'F';
+ color = COLOR_GREEN;
+ break;
+ }
+ }
+ if (kd_backward && kd_backward_d >= 0) {
+ int delta = (int)r->atoms.len
+ - (int)l->atoms.len;
+ int ki;
+ for (ki = kd_backward_d;
+ ki >= -kd_backward_d;
+ ki -= 2) {
+ if (x != kd_backward[ki])
+ continue;
+ if (y != xc_to_y(x, ki, delta))
+ continue;
+ if (label == 'o') {
+ label = 'B';
+ color = COLOR_BLUE;
+ } else {
+ label = 'X';
+ color = COLOR_RED;
+ }
+ break;
+ }
+ }
+ if (color)
+ print("%s", color);
+ print("%c", label);
+ if (color)
+ print("%s", COLOR_END);
+ if (x < l->atoms.len)
+ print("-");
+ }
+ print("\n");
+ if (y == r->atoms.len)
+ break;
+
+ print(" ");
+ for (x = 0; x < l->atoms.len; x++) {
+ bool same;
+ diff_atom_same(&same, &l->atoms.head[x],
+ &r->atoms.head[y]);
+ if (same)
+ print("|\\");
+ else
+ print("| ");
+ }
+ print("|\n");
+ }
+}
+
+static inline void
+debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
+ int *kd, int *kd_forward, int kd_forward_d,
+ int *kd_backward, int kd_backward_d)
+{
+ if (l->atoms.len > 99 || r->atoms.len > 99)
+ return;
+ dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
+ kd_backward, kd_backward_d);
+}
+
+#else
+#define debug(args...)
+#define debug_dump(args...)
+#define debug_dump_atom(args...)
+#define debug_dump_atoms(args...)
+#define debug_dump_myers_graph(args...)
+#endif
diff --git a/usr.bin/diff/lib/diff_internal.h b/usr.bin/diff/lib/diff_internal.h
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_internal.h
@@ -0,0 +1,187 @@
+/* Generic infrastructure to implement various diff algorithms. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#ifndef MAX
+#define MAX(A,B) ((A)>(B)?(A):(B))
+#endif
+#ifndef MIN
+#define MIN(A,B) ((A)<(B)?(A):(B))
+#endif
+
+static inline bool
+diff_range_empty(const struct diff_range *r)
+{
+ return r->start == r->end;
+}
+
+static inline bool
+diff_ranges_touch(const struct diff_range *a, const struct diff_range *b)
+{
+ return (a->end >= b->start) && (a->start <= b->end);
+}
+
+static inline void
+diff_ranges_merge(struct diff_range *a, const struct diff_range *b)
+{
+ *a = (struct diff_range){
+ .start = MIN(a->start, b->start),
+ .end = MAX(a->end, b->end),
+ };
+}
+
+static inline int
+diff_range_len(const struct diff_range *r)
+{
+ if (!r)
+ return 0;
+ return r->end - r->start;
+}
+
+/* List of all possible return codes of a diff invocation. */
+#define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
+#define DIFF_RC_OK 0
+/* Any positive return values are errno values from sys/errno.h */
+
+/* Indicate whether two given diff atoms match. */
+int
+diff_atom_same(bool *same,
+ const struct diff_atom *left,
+ const struct diff_atom *right);
+
+/* A diff chunk represents a set of atoms on the left and/or a set of atoms on
+ * the right.
+ *
+ * If solved == false:
+ * The diff algorithm has divided the source file, and this is a chunk that the
+ * inner_algo should run on next.
+ * The lines on the left should be diffed against the lines on the right.
+ * (If there are no left lines or no right lines, it implies solved == true,
+ * because there is nothing to diff.)
+ *
+ * If solved == true:
+ * If there are only left atoms, it is a chunk removing atoms from the left ("a
+ * minus chunk").
+ * If there are only right atoms, it is a chunk adding atoms from the right ("a
+ * plus chunk").
+ * If there are both left and right lines, it is a chunk of equal content on
+ * both sides, and left_count == right_count:
+ *
+ * - foo }
+ * - bar }-- diff_chunk{ left_start = &left.atoms.head[0], left_count = 3,
+ * - baz } right_start = NULL, right_count = 0 }
+ * moo }
+ * goo }-- diff_chunk{ left_start = &left.atoms.head[3], left_count = 3,
+ * zoo } right_start = &right.atoms.head[0], right_count = 3 }
+ * +loo }
+ * +roo }-- diff_chunk{ left_start = NULL, left_count = 0,
+ * +too } right_start = &right.atoms.head[3], right_count = 3 }
+ *
+ */
+struct diff_chunk {
+ bool solved;
+ struct diff_atom *left_start;
+ unsigned int left_count;
+ struct diff_atom *right_start;
+ unsigned int right_count;
+};
+
+#define DIFF_RESULT_ALLOC_BLOCKSIZE 128
+
+enum diff_chunk_type {
+ CHUNK_EMPTY,
+ CHUNK_PLUS,
+ CHUNK_MINUS,
+ CHUNK_SAME,
+ CHUNK_ERROR,
+};
+
+static inline enum diff_chunk_type
+diff_chunk_type(const struct diff_chunk *chunk)
+{
+ if (!chunk->left_count && !chunk->right_count)
+ return CHUNK_EMPTY;
+ if (!chunk->solved)
+ return CHUNK_ERROR;
+ if (!chunk->right_count)
+ return CHUNK_MINUS;
+ if (!chunk->left_count)
+ return CHUNK_PLUS;
+ if (chunk->left_count != chunk->right_count)
+ return CHUNK_ERROR;
+ return CHUNK_SAME;
+}
+
+struct diff_chunk_context;
+
+bool
+diff_chunk_context_empty(const struct diff_chunk_context *cc);
+
+bool
+diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
+ const struct diff_chunk_context *other);
+
+void
+diff_chunk_contexts_merge(struct diff_chunk_context *cc,
+ const struct diff_chunk_context *other);
+
+struct diff_state {
+ /* The final result passed to the original diff caller. */
+ struct diff_result *result;
+
+ /* The root diff_data is in result->left,right, these are (possibly)
+ * subsections of the root data. */
+ struct diff_data left;
+ struct diff_data right;
+
+ unsigned int recursion_depth_left;
+
+ /* Remaining chunks from one diff algorithm pass, if any solved == false
+ * chunks came up. */
+ diff_chunk_arraylist_t temp_result;
+
+ /* State buffer used by Myers algorithm. */
+ int *kd_buf;
+ size_t kd_buf_size; /* in units of sizeof(int), not bytes */
+};
+
+struct diff_chunk *diff_state_add_chunk(struct diff_state *state, bool solved,
+ struct diff_atom *left_start,
+ unsigned int left_count,
+ struct diff_atom *right_start,
+ unsigned int right_count);
+
+struct diff_output_info;
+
+int diff_output_lines(struct diff_output_info *output_info, FILE *dest,
+ const char *prefix, struct diff_atom *start_atom,
+ unsigned int count);
+
+int diff_output_trailing_newline_msg(struct diff_output_info *outinfo,
+ FILE *dest,
+ const struct diff_chunk *c);
+#define DIFF_FUNCTION_CONTEXT_SIZE 55
+int diff_output_match_function_prototype(char *prototype, size_t prototype_size,
+ int *last_prototype_idx,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc,
+ unsigned int ncontext);
+
+struct diff_output_info *diff_output_info_alloc(void);
+
+void
+diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
+ struct diff_atom *from_atom, unsigned int atoms_count);
diff --git a/usr.bin/diff/lib/diff_main.h b/usr.bin/diff/lib/diff_main.h
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_main.h
@@ -0,0 +1,254 @@
+/* Generic infrastructure to implement various diff algorithms. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+struct diff_range {
+ int start;
+ int end;
+};
+
+/* List of all possible return codes of a diff invocation. */
+#define DIFF_RC_USE_DIFF_ALGO_FALLBACK -1
+#define DIFF_RC_OK 0
+/* Any positive return values are errno values from sys/errno.h */
+
+struct diff_atom {
+ struct diff_data *root; /* back pointer to root diff data */
+
+ off_t pos; /* if not memory-mapped */
+ const uint8_t *at; /* if memory-mapped */
+ off_t len;
+
+ /* This hash is just a very cheap speed up for finding *mismatching*
+ * atoms. When hashes match, we still need to compare entire atoms to
+ * find out whether they are indeed identical or not.
+ * Calculated over all atom bytes with diff_atom_hash_update(). */
+ unsigned int hash;
+};
+
+/* Mix another atom_byte into the provided hash value and return the result.
+ * The hash value passed in for the first byte of the atom must be zero. */
+unsigned int
+diff_atom_hash_update(unsigned int hash, unsigned char atom_byte);
+
+/* Compare two atoms for equality. Return 0 on success, or errno on failure.
+ * Set cmp to -1, 0, or 1, just like strcmp(). */
+int
+diff_atom_cmp(int *cmp,
+ const struct diff_atom *left,
+ const struct diff_atom *right);
+
+
+/* The atom's index in the entire file. For atoms divided by lines of text, this
+ * yields the line number (starting with 0). Also works for diff_data that
+ * reference only a subsection of a file, always reflecting the global position
+ * in the file (and not the relative position within the subsection). */
+#define diff_atom_root_idx(DIFF_DATA, ATOM) \
+ ((ATOM) && ((ATOM) >= (DIFF_DATA)->root->atoms.head) \
+ ? (unsigned int)((ATOM) - ((DIFF_DATA)->root->atoms.head)) \
+ : (DIFF_DATA)->root->atoms.len)
+
+/* The atom's index within DIFF_DATA. For atoms divided by lines of text, this
+ * yields the line number (starting with 0). */
+#define diff_atom_idx(DIFF_DATA, ATOM) \
+ ((ATOM) && ((ATOM) >= (DIFF_DATA)->atoms.head) \
+ ? (unsigned int)((ATOM) - ((DIFF_DATA)->atoms.head)) \
+ : (DIFF_DATA)->atoms.len)
+
+#define foreach_diff_atom(ATOM, FIRST_ATOM, COUNT) \
+ for ((ATOM) = (FIRST_ATOM); \
+ (ATOM) \
+ && ((ATOM) >= (FIRST_ATOM)) \
+ && ((ATOM) - (FIRST_ATOM) < (COUNT)); \
+ (ATOM)++)
+
+#define diff_data_foreach_atom(ATOM, DIFF_DATA) \
+ foreach_diff_atom(ATOM, (DIFF_DATA)->atoms.head, (DIFF_DATA)->atoms.len)
+
+#define diff_data_foreach_atom_from(FROM, ATOM, DIFF_DATA) \
+ for ((ATOM) = (FROM); \
+ (ATOM) \
+ && ((ATOM) >= (DIFF_DATA)->atoms.head) \
+ && ((ATOM) - (DIFF_DATA)->atoms.head < (DIFF_DATA)->atoms.len); \
+ (ATOM)++)
+
+#define diff_data_foreach_atom_backwards_from(FROM, ATOM, DIFF_DATA) \
+ for ((ATOM) = (FROM); \
+ (ATOM) \
+ && ((ATOM) >= (DIFF_DATA)->atoms.head) \
+ && ((ATOM) - (DIFF_DATA)->atoms.head >= 0); \
+ (ATOM)--)
+
+/* For each file, there is a "root" struct diff_data referencing the entire
+ * file, which the atoms are parsed from. In recursion of diff algorithm, there
+ * may be "child" struct diff_data only referencing a subsection of the file,
+ * re-using the atoms parsing. For "root" structs, atoms_allocated will be
+ * nonzero, indicating that the array of atoms is owned by that struct. For
+ * "child" structs, atoms_allocated == 0, to indicate that the struct is
+ * referencing a subset of atoms. */
+struct diff_data {
+ FILE *f; /* if root diff_data and not memory-mapped */
+ off_t pos; /* if not memory-mapped */
+ const uint8_t *data; /* if memory-mapped */
+ off_t len;
+
+ int atomizer_flags;
+ ARRAYLIST(struct diff_atom) atoms;
+ struct diff_data *root;
+ struct diff_data *current;
+ void *algo_data;
+
+ int diff_flags;
+
+ int err;
+};
+
+/* Flags set by file atomizer. */
+#define DIFF_ATOMIZER_FOUND_BINARY_DATA 0x00000001
+
+/* Flags set by caller of diff_main(). */
+#define DIFF_FLAG_IGNORE_WHITESPACE 0x00000001
+#define DIFF_FLAG_SHOW_PROTOTYPES 0x00000002
+#define DIFF_FLAG_FORCE_TEXT_DATA 0x00000004
+
+void diff_data_free(struct diff_data *diff_data);
+
+struct diff_chunk;
+typedef ARRAYLIST(struct diff_chunk) diff_chunk_arraylist_t;
+
+struct diff_result {
+ int rc;
+
+ /*
+ * Pointers to diff data passed in via diff_main.
+ * Do not free these diff_data before freeing the diff_result struct.
+ */
+ struct diff_data *left;
+ struct diff_data *right;
+
+ diff_chunk_arraylist_t chunks;
+};
+
+struct diff_state;
+
+/* Signature of a utility function to divide a file into diff atoms.
+ * An example is diff_atomize_text_by_line() in diff_atomize_text.c.
+ *
+ * func_data: context pointer (free to be used by implementation).
+ * d: struct diff_data with d->data and d->len already set up, and
+ * d->atoms to be created and d->atomizer_flags to be set up.
+ */
+typedef int (*diff_atomize_func_t)(void *func_data, struct diff_data *d);
+
+extern int diff_atomize_text_by_line(void *func_data, struct diff_data *d);
+
+struct diff_algo_config;
+typedef int (*diff_algo_impl_t)(
+ const struct diff_algo_config *algo_config, struct diff_state *state);
+
+/* Form a result with all left-side removed and all right-side added, i.e. no
+ * actual diff algorithm involved. */
+int diff_algo_none(const struct diff_algo_config *algo_config,
+ struct diff_state *state);
+
+/* Myers Diff tracing from the start all the way through to the end, requiring
+ * quadratic amounts of memory. This can fail if the required space surpasses
+ * algo_config->permitted_state_size. */
+extern int diff_algo_myers(const struct diff_algo_config *algo_config,
+ struct diff_state *state);
+
+/* Myers "Divide et Impera": tracing forwards from the start and backwards from
+ * the end to find a midpoint that divides the problem into smaller chunks.
+ * Requires only linear amounts of memory. */
+extern int diff_algo_myers_divide(
+ const struct diff_algo_config *algo_config, struct diff_state *state);
+
+/* Patience Diff algorithm, which divides a larger diff into smaller chunks. For
+ * very specific scenarios, it may lead to a complete diff result by itself, but
+ * needs a fallback algo to solve chunks that don't have common-unique atoms. */
+extern int diff_algo_patience(
+ const struct diff_algo_config *algo_config, struct diff_state *state);
+
+/* Diff algorithms to use, possibly nested. For example:
+ *
+ * struct diff_algo_config myers, patience, myers_divide;
+ *
+ * myers = (struct diff_algo_config){
+ * .impl = diff_algo_myers,
+ * .permitted_state_size = 32 * 1024 * 1024,
+ * // When too large, do diff_algo_patience:
+ * .fallback_algo = &patience,
+ * };
+ *
+ * const struct diff_algo_config patience = (struct diff_algo_config){
+ * .impl = diff_algo_patience,
+ * // After subdivision, do Patience again:
+ * .inner_algo = &patience,
+ * // If subdivision failed, do Myers Divide et Impera:
+ * .fallback_algo = &myers_then_myers_divide,
+ * };
+ *
+ * const struct diff_algo_config myers_divide = (struct diff_algo_config){
+ * .impl = diff_algo_myers_divide,
+ * // When division succeeded, start from the top:
+ * .inner_algo = &myers_then_myers_divide,
+ * // (fallback_algo = NULL implies diff_algo_none).
+ * };
+ * struct diff_config config = {
+ * .algo = &myers,
+ * ...
+ * };
+ * diff_main(&config, ...);
+ */
+struct diff_algo_config {
+ diff_algo_impl_t impl;
+
+ /* Fail this algo if it would use more than this amount of memory, and
+ * instead use fallback_algo (diff_algo_myers). permitted_state_size ==
+ * 0 means no limitation. */
+ size_t permitted_state_size;
+
+ /* For algorithms that divide into smaller chunks, use this algorithm to
+ * solve the divided chunks. */
+ const struct diff_algo_config *inner_algo;
+
+ /* If the algorithm fails (e.g. diff_algo_myers_if_small needs too large
+ * state, or diff_algo_patience can't find any common-unique atoms),
+ * then use this algorithm instead. */
+ const struct diff_algo_config *fallback_algo;
+};
+
+struct diff_config {
+ diff_atomize_func_t atomize_func;
+ void *atomize_func_data;
+
+ const struct diff_algo_config *algo;
+
+ /* How deep to step into subdivisions of a source file, a paranoia /
+ * safety measure to guard against infinite loops through diff
+ * algorithms. When the maximum recursion is reached, employ
+ * diff_algo_none (i.e. remove all left atoms and add all right atoms).
+ */
+ unsigned int max_recursion_depth;
+};
+
+int diff_atomize_file(struct diff_data *d, const struct diff_config *config,
+ FILE *f, const uint8_t *data, off_t len, int diff_flags);
+struct diff_result *diff_main(const struct diff_config *config,
+ struct diff_data *left,
+ struct diff_data *right);
+void diff_result_free(struct diff_result *result);
+int diff_printable_chunks(struct diff_result *result);
diff --git a/usr.bin/diff/lib/diff_main.c b/usr.bin/diff/lib/diff_main.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_main.c
@@ -0,0 +1,647 @@
+/* Generic infrastructure to implement various diff algorithms (implementation). */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+
+#include <sys/queue.h>
+#include <ctype.h>
+#include <errno.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdbool.h>
+#include <stdio.h>
+#include <string.h>
+#include <limits.h>
+#include <unistd.h>
+
+#include <assert.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+
+#include "diff_internal.h"
+#include "diff_debug.h"
+
+static int
+read_at(FILE *f, off_t at_pos, unsigned char *buf, size_t len)
+{
+ int r;
+ if (fseeko(f, at_pos, SEEK_SET) == -1)
+ return errno;
+ r = fread(buf, sizeof(char), len, f);
+ if ((r == 0 || r < len) && ferror(f))
+ return errno;
+ if (r != len)
+ return EIO;
+ return 0;
+}
+
+static int
+buf_cmp(const unsigned char *left, size_t left_len,
+ const unsigned char *right, size_t right_len,
+ bool ignore_whitespace)
+{
+ int cmp;
+
+ if (ignore_whitespace) {
+ int il = 0, ir = 0;
+ while (il < left_len && ir < right_len) {
+ unsigned char cl = left[il];
+ unsigned char cr = right[ir];
+
+ if (isspace(cl) && il < left_len) {
+ il++;
+ continue;
+ }
+ if (isspace(cr) && ir < right_len) {
+ ir++;
+ continue;
+ }
+
+ if (cl > cr)
+ return 1;
+ if (cr > cl)
+ return -1;
+ il++;
+ ir++;
+ }
+ while (il < left_len) {
+ unsigned char cl = left[il++];
+ if (!isspace(cl))
+ return 1;
+ }
+ while (ir < right_len) {
+ unsigned char cr = right[ir++];
+ if (!isspace(cr))
+ return -1;
+ }
+
+ return 0;
+ }
+
+ cmp = memcmp(left, right, MIN(left_len, right_len));
+ if (cmp)
+ return cmp;
+ if (left_len == right_len)
+ return 0;
+ return (left_len > right_len) ? 1 : -1;
+}
+
+int
+diff_atom_cmp(int *cmp,
+ const struct diff_atom *left,
+ const struct diff_atom *right)
+{
+ off_t remain_left, remain_right;
+ int flags = (left->root->diff_flags | right->root->diff_flags);
+ bool ignore_whitespace = (flags & DIFF_FLAG_IGNORE_WHITESPACE);
+
+ if (!left->len && !right->len) {
+ *cmp = 0;
+ return 0;
+ }
+ if (!ignore_whitespace) {
+ if (!right->len) {
+ *cmp = 1;
+ return 0;
+ }
+ if (!left->len) {
+ *cmp = -1;
+ return 0;
+ }
+ }
+
+ if (left->at != NULL && right->at != NULL) {
+ *cmp = buf_cmp(left->at, left->len, right->at, right->len,
+ ignore_whitespace);
+ return 0;
+ }
+
+ remain_left = left->len;
+ remain_right = right->len;
+ while (remain_left > 0 || remain_right > 0) {
+ const size_t chunksz = 8192;
+ unsigned char buf_left[chunksz], buf_right[chunksz];
+ const uint8_t *p_left, *p_right;
+ off_t n_left, n_right;
+ ssize_t r;
+
+ if (!remain_right) {
+ *cmp = 1;
+ return 0;
+ }
+ if (!remain_left) {
+ *cmp = -1;
+ return 0;
+ }
+
+ n_left = MIN(chunksz, remain_left);
+ n_right = MIN(chunksz, remain_right);
+
+ if (left->at == NULL) {
+ r = read_at(left->root->f,
+ left->pos + (left->len - remain_left),
+ buf_left, n_left);
+ if (r) {
+ *cmp = 0;
+ return r;
+ }
+ p_left = buf_left;
+ } else {
+ p_left = left->at + (left->len - remain_left);
+ }
+
+ if (right->at == NULL) {
+ r = read_at(right->root->f,
+ right->pos + (right->len - remain_right),
+ buf_right, n_right);
+ if (r) {
+ *cmp = 0;
+ return r;
+ }
+ p_right = buf_right;
+ } else {
+ p_right = right->at + (right->len - remain_right);
+ }
+
+ r = buf_cmp(p_left, n_left, p_right, n_right,
+ ignore_whitespace);
+ if (r) {
+ *cmp = r;
+ return 0;
+ }
+
+ remain_left -= n_left;
+ remain_right -= n_right;
+ }
+
+ *cmp = 0;
+ return 0;
+}
+
+int
+diff_atom_same(bool *same,
+ const struct diff_atom *left,
+ const struct diff_atom *right)
+{
+ int cmp;
+ int r;
+ if (left->hash != right->hash) {
+ *same = false;
+ return 0;
+ }
+ r = diff_atom_cmp(&cmp, left, right);
+ if (r) {
+ *same = true;
+ return r;
+ }
+ *same = (cmp == 0);
+ return 0;
+}
+
+static struct diff_chunk *
+diff_state_add_solved_chunk(struct diff_state *state,
+ const struct diff_chunk *chunk)
+{
+ diff_chunk_arraylist_t *result;
+ struct diff_chunk *new_chunk;
+ enum diff_chunk_type last_t;
+ enum diff_chunk_type new_t;
+ struct diff_chunk *last;
+
+ /* Append to solved chunks; make sure that adjacent chunks of same type are combined, and that a minus chunk
+ * never directly follows a plus chunk. */
+ result = &state->result->chunks;
+
+ last_t = result->len ? diff_chunk_type(&result->head[result->len - 1])
+ : CHUNK_EMPTY;
+ new_t = diff_chunk_type(chunk);
+
+ debug("ADD %s chunk #%u:\n", chunk->solved ? "solved" : "UNSOLVED",
+ result->len);
+ debug("L\n");
+ debug_dump_atoms(&state->left, chunk->left_start, chunk->left_count);
+ debug("R\n");
+ debug_dump_atoms(&state->right, chunk->right_start, chunk->right_count);
+
+ if (result->len) {
+ last = &result->head[result->len - 1];
+ assert(chunk->left_start
+ == last->left_start + last->left_count);
+ assert(chunk->right_start
+ == last->right_start + last->right_count);
+ }
+
+ if (new_t == last_t) {
+ new_chunk = &result->head[result->len - 1];
+ new_chunk->left_count += chunk->left_count;
+ new_chunk->right_count += chunk->right_count;
+ debug(" - added chunk touches previous one of same type, joined:\n");
+ debug("L\n");
+ debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
+ debug("R\n");
+ debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
+ } else if (last_t == CHUNK_PLUS && new_t == CHUNK_MINUS) {
+ enum diff_chunk_type prev_last_t =
+ result->len > 1 ?
+ diff_chunk_type(&result->head[result->len - 2])
+ : CHUNK_EMPTY;
+ /* If a minus-chunk follows a plus-chunk, place it above the plus-chunk->
+ * Is the one before that also a minus? combine. */
+ if (prev_last_t == CHUNK_MINUS) {
+ new_chunk = &result->head[result->len - 2];
+ new_chunk->left_count += chunk->left_count;
+ new_chunk->right_count += chunk->right_count;
+
+ debug(" - added minus-chunk follows plus-chunk,"
+ " put before that plus-chunk and joined"
+ " with preceding minus-chunk:\n");
+ debug("L\n");
+ debug_dump_atoms(&state->left, new_chunk->left_start, new_chunk->left_count);
+ debug("R\n");
+ debug_dump_atoms(&state->right, new_chunk->right_start, new_chunk->right_count);
+ } else {
+ ARRAYLIST_INSERT(new_chunk, *result, result->len - 1);
+ if (!new_chunk)
+ return NULL;
+ *new_chunk = *chunk;
+
+ /* The new minus chunk indicates to which position on
+ * the right it corresponds, even though it doesn't add
+ * any lines on the right. By moving above a plus chunk,
+ * that position on the right has shifted. */
+ last = &result->head[result->len - 1];
+ new_chunk->right_start = last->right_start;
+
+ debug(" - added minus-chunk follows plus-chunk,"
+ " put before that plus-chunk\n");
+ }
+
+ /* That last_t == CHUNK_PLUS indicates to which position on the
+ * left it corresponds, even though it doesn't add any lines on
+ * the left. By inserting/extending the prev_last_t ==
+ * CHUNK_MINUS, that position on the left has shifted. */
+ last = &result->head[result->len - 1];
+ last->left_start = new_chunk->left_start
+ + new_chunk->left_count;
+
+ } else {
+
+ ARRAYLIST_ADD(new_chunk, *result);
+ if (!new_chunk)
+ return NULL;
+ *new_chunk = *chunk;
+ }
+ return new_chunk;
+}
+
+/* Even if a left or right side is empty, diff output may need to know the
+ * position in that file.
+ * So left_start or right_start must never be NULL -- pass left_count or
+ * right_count as zero to indicate staying at that position without consuming
+ * any lines. */
+struct diff_chunk *
+diff_state_add_chunk(struct diff_state *state, bool solved,
+ struct diff_atom *left_start, unsigned int left_count,
+ struct diff_atom *right_start, unsigned int right_count)
+{
+ struct diff_chunk *new_chunk;
+ struct diff_chunk chunk = {
+ .solved = solved,
+ .left_start = left_start,
+ .left_count = left_count,
+ .right_start = right_start,
+ .right_count = right_count,
+ };
+
+ /* An unsolved chunk means store as intermediate result for later
+ * re-iteration.
+ * If there already are intermediate results, that means even a
+ * following solved chunk needs to go to intermediate results, so that
+ * it is later put in the final correct position in solved chunks.
+ */
+ if (!solved || state->temp_result.len) {
+ /* Append to temp_result */
+ debug("ADD %s chunk to temp result:\n",
+ chunk.solved ? "solved" : "UNSOLVED");
+ debug("L\n");
+ debug_dump_atoms(&state->left, left_start, left_count);
+ debug("R\n");
+ debug_dump_atoms(&state->right, right_start, right_count);
+ ARRAYLIST_ADD(new_chunk, state->temp_result);
+ if (!new_chunk)
+ return NULL;
+ *new_chunk = chunk;
+ return new_chunk;
+ }
+
+ return diff_state_add_solved_chunk(state, &chunk);
+}
+
+static void
+diff_data_init_root(struct diff_data *d, FILE *f, const uint8_t *data,
+ unsigned long long len, int diff_flags)
+{
+ *d = (struct diff_data){
+ .f = f,
+ .pos = 0,
+ .data = data,
+ .len = len,
+ .root = d,
+ .diff_flags = diff_flags,
+ };
+}
+
+void
+diff_data_init_subsection(struct diff_data *d, struct diff_data *parent,
+ struct diff_atom *from_atom, unsigned int atoms_count)
+{
+ struct diff_atom *last_atom;
+
+ debug("diff_data %p parent %p from_atom %p atoms_count %u\n",
+ d, parent, from_atom, atoms_count);
+ debug(" from_atom ");
+ debug_dump_atom(parent, NULL, from_atom);
+
+ if (atoms_count == 0) {
+ *d = (struct diff_data){
+ .f = NULL,
+ .pos = 0,
+ .data = NULL,
+ .len = 0,
+ .root = parent->root,
+ .atoms.head = NULL,
+ .atoms.len = atoms_count,
+ };
+
+ return;
+ }
+
+ last_atom = from_atom + atoms_count - 1;
+ *d = (struct diff_data){
+ .f = NULL,
+ .pos = from_atom->pos,
+ .data = from_atom->at,
+ .len = (last_atom->pos + last_atom->len) - from_atom->pos,
+ .root = parent->root,
+ .atoms.head = from_atom,
+ .atoms.len = atoms_count,
+ };
+
+ debug("subsection:\n");
+ debug_dump(d);
+}
+
+void
+diff_data_free(struct diff_data *diff_data)
+{
+ if (!diff_data)
+ return;
+ if (diff_data->atoms.allocated)
+ ARRAYLIST_FREE(diff_data->atoms);
+}
+
+int
+diff_algo_none(const struct diff_algo_config *algo_config,
+ struct diff_state *state)
+{
+ debug("\n** %s\n", __func__);
+ debug("left:\n");
+ debug_dump(&state->left);
+ debug("right:\n");
+ debug_dump(&state->right);
+ debug_dump_myers_graph(&state->left, &state->right, NULL, NULL, 0, NULL,
+ 0);
+
+ /* Add a chunk of equal lines, if any */
+ struct diff_atom *l = state->left.atoms.head;
+ unsigned int l_len = state->left.atoms.len;
+ struct diff_atom *r = state->right.atoms.head;
+ unsigned int r_len = state->right.atoms.len;
+ unsigned int equal_atoms_start = 0;
+ unsigned int equal_atoms_end = 0;
+ unsigned int l_idx = 0;
+ unsigned int r_idx = 0;
+
+ while (equal_atoms_start < l_len
+ && equal_atoms_start < r_len) {
+ int err;
+ bool same;
+ err = diff_atom_same(&same, &l[equal_atoms_start],
+ &r[equal_atoms_start]);
+ if (err)
+ return err;
+ if (!same)
+ break;
+ equal_atoms_start++;
+ }
+ while (equal_atoms_end < (l_len - equal_atoms_start)
+ && equal_atoms_end < (r_len - equal_atoms_start)) {
+ int err;
+ bool same;
+ err = diff_atom_same(&same, &l[l_len - 1 - equal_atoms_end],
+ &r[r_len - 1 - equal_atoms_end]);
+ if (err)
+ return err;
+ if (!same)
+ break;
+ equal_atoms_end++;
+ }
+
+ /* Add a chunk of equal lines at the start */
+ if (equal_atoms_start) {
+ if (!diff_state_add_chunk(state, true,
+ l, equal_atoms_start,
+ r, equal_atoms_start))
+ return ENOMEM;
+ l_idx += equal_atoms_start;
+ r_idx += equal_atoms_start;
+ }
+
+ /* Add a "minus" chunk with all lines from the left. */
+ if (equal_atoms_start + equal_atoms_end < l_len) {
+ unsigned int add_len = l_len - equal_atoms_start - equal_atoms_end;
+ if (!diff_state_add_chunk(state, true,
+ &l[l_idx], add_len,
+ &r[r_idx], 0))
+ return ENOMEM;
+ l_idx += add_len;
+ }
+
+ /* Add a "plus" chunk with all lines from the right. */
+ if (equal_atoms_start + equal_atoms_end < r_len) {
+ unsigned int add_len = r_len - equal_atoms_start - equal_atoms_end;
+ if (!diff_state_add_chunk(state, true,
+ &l[l_idx], 0,
+ &r[r_idx], add_len))
+ return ENOMEM;
+ r_idx += add_len;
+ }
+
+ /* Add a chunk of equal lines at the end */
+ if (equal_atoms_end) {
+ if (!diff_state_add_chunk(state, true,
+ &l[l_idx], equal_atoms_end,
+ &r[r_idx], equal_atoms_end))
+ return ENOMEM;
+ }
+
+ return DIFF_RC_OK;
+}
+
+static int
+diff_run_algo(const struct diff_algo_config *algo_config,
+ struct diff_state *state)
+{
+ int rc;
+
+ if (!algo_config || !algo_config->impl
+ || !state->recursion_depth_left
+ || !state->left.atoms.len || !state->right.atoms.len) {
+ debug("Fall back to diff_algo_none():%s%s%s\n",
+ (!algo_config || !algo_config->impl) ? " no-cfg" : "",
+ (!state->recursion_depth_left) ? " max-depth" : "",
+ (!state->left.atoms.len || !state->right.atoms.len)?
+ " trivial" : "");
+ return diff_algo_none(algo_config, state);
+ }
+
+ ARRAYLIST_FREE(state->temp_result);
+ ARRAYLIST_INIT(state->temp_result, DIFF_RESULT_ALLOC_BLOCKSIZE);
+ rc = algo_config->impl(algo_config, state);
+ switch (rc) {
+ case DIFF_RC_USE_DIFF_ALGO_FALLBACK:
+ debug("Got DIFF_RC_USE_DIFF_ALGO_FALLBACK (%p)\n",
+ algo_config->fallback_algo);
+ rc = diff_run_algo(algo_config->fallback_algo, state);
+ goto return_rc;
+
+ case DIFF_RC_OK:
+ /* continue below */
+ break;
+
+ default:
+ /* some error happened */
+ goto return_rc;
+ }
+
+ /* Pick up any diff chunks that are still unsolved and feed to
+ * inner_algo. inner_algo will solve unsolved chunks and append to
+ * result, and subsequent solved chunks on this level are then appended
+ * to result afterwards. */
+ int i;
+ for (i = 0; i < state->temp_result.len; i++) {
+ struct diff_chunk *c = &state->temp_result.head[i];
+ if (c->solved) {
+ diff_state_add_solved_chunk(state, c);
+ continue;
+ }
+
+ /* c is an unsolved chunk, feed to inner_algo */
+ struct diff_state inner_state = {
+ .result = state->result,
+ .recursion_depth_left = state->recursion_depth_left - 1,
+ .kd_buf = state->kd_buf,
+ .kd_buf_size = state->kd_buf_size,
+ };
+ diff_data_init_subsection(&inner_state.left, &state->left,
+ c->left_start, c->left_count);
+ diff_data_init_subsection(&inner_state.right, &state->right,
+ c->right_start, c->right_count);
+
+ rc = diff_run_algo(algo_config->inner_algo, &inner_state);
+ state->kd_buf = inner_state.kd_buf;
+ state->kd_buf_size = inner_state.kd_buf_size;
+ if (rc != DIFF_RC_OK)
+ goto return_rc;
+ }
+
+ rc = DIFF_RC_OK;
+return_rc:
+ ARRAYLIST_FREE(state->temp_result);
+ return rc;
+}
+
+int
+diff_atomize_file(struct diff_data *d,
+ const struct diff_config *config,
+ FILE *f, const uint8_t *data, off_t len, int diff_flags)
+{
+ if (!config->atomize_func)
+ return EINVAL;
+
+ diff_data_init_root(d, f, data, len, diff_flags);
+
+ return config->atomize_func(config->atomize_func_data, d);
+
+}
+
+struct diff_result *
+diff_main(const struct diff_config *config, struct diff_data *left,
+ struct diff_data *right)
+{
+ struct diff_result *result = malloc(sizeof(struct diff_result));
+ if (!result)
+ return NULL;
+
+ *result = (struct diff_result){};
+ result->left = left;
+ result->right = right;
+
+ struct diff_state state = {
+ .result = result,
+ .recursion_depth_left = config->max_recursion_depth ?
+ config->max_recursion_depth : UINT_MAX,
+ .kd_buf = NULL,
+ .kd_buf_size = 0,
+ };
+ diff_data_init_subsection(&state.left, left,
+ left->atoms.head,
+ left->atoms.len);
+ diff_data_init_subsection(&state.right, right,
+ right->atoms.head,
+ right->atoms.len);
+
+ result->rc = diff_run_algo(config->algo, &state);
+ free(state.kd_buf);
+
+ return result;
+}
+
+void
+diff_result_free(struct diff_result *result)
+{
+ if (!result)
+ return;
+ ARRAYLIST_FREE(result->chunks);
+ free(result);
+}
+
+int
+diff_printable_chunks(struct diff_result *result)
+{
+ struct diff_chunk *c;
+ enum diff_chunk_type t;
+
+ for (int i = 0; i < result->chunks.len; i++) {
+ c = &result->chunks.head[i];
+ t = diff_chunk_type(c);
+ if (t == CHUNK_MINUS || t == CHUNK_PLUS)
+ return 1;
+ }
+
+ return 0;
+}
diff --git a/usr.bin/diff/lib/diff_myers.c b/usr.bin/diff/lib/diff_myers.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_myers.c
@@ -0,0 +1,1425 @@
+/* Myers diff algorithm implementation, invented by Eugene W. Myers [1].
+ * Implementations of both the Myers Divide Et Impera (using linear space)
+ * and the canonical Myers algorithm (using quadratic space). */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <stdio.h>
+#include <errno.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+
+#include "diff_internal.h"
+#include "diff_debug.h"
+
+/* Myers' diff algorithm [1] is nicely explained in [2].
+ * [1] http://www.xmailserver.org/diff2.pdf
+ * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff.
+ *
+ * Myers approaches finding the smallest diff as a graph problem.
+ * The crux is that the original algorithm requires quadratic amount of memory:
+ * both sides' lengths added, and that squared. So if we're diffing lines of
+ * text, two files with 1000 lines each would blow up to a matrix of about
+ * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text.
+ * The solution is using Myers' "divide and conquer" extension algorithm, which
+ * does the original traversal from both ends of the files to reach a middle
+ * where these "snakes" touch, hence does not need to backtrace the traversal,
+ * and so gets away with only keeping a single column of that huge state matrix
+ * in memory.
+ */
+
+struct diff_box {
+ unsigned int left_start;
+ unsigned int left_end;
+ unsigned int right_start;
+ unsigned int right_end;
+};
+
+/* If the two contents of a file are A B C D E and X B C Y,
+ * the Myers diff graph looks like:
+ *
+ * k0 k1
+ * \ \
+ * k-1 0 1 2 3 4 5
+ * \ A B C D E
+ * 0 o-o-o-o-o-o
+ * X | | | | | |
+ * 1 o-o-o-o-o-o
+ * B | |\| | | |
+ * 2 o-o-o-o-o-o
+ * C | | |\| | |
+ * 3 o-o-o-o-o-o
+ * Y | | | | | |\
+ * 4 o-o-o-o-o-o c1
+ * \ \
+ * c-1 c0
+ *
+ * Moving right means delete an atom from the left-hand-side,
+ * Moving down means add an atom from the right-hand-side.
+ * Diagonals indicate identical atoms on both sides, the challenge is to use as
+ * many diagonals as possible.
+ *
+ * The original Myers algorithm walks all the way from the top left to the
+ * bottom right, remembers all steps, and then backtraces to find the shortest
+ * path. However, that requires keeping the entire graph in memory, which needs
+ * quadratic space.
+ *
+ * Myers adds a variant that uses linear space -- note, not linear time, only
+ * linear space: walk forward and backward, find a meeting point in the middle,
+ * and recurse on the two separate sections. This is called "divide and
+ * conquer".
+ *
+ * d: the step number, starting with 0, a.k.a. the distance from the starting
+ * point.
+ * k: relative index in the state array for the forward scan, indicating on
+ * which diagonal through the diff graph we currently are.
+ * c: relative index in the state array for the backward scan, indicating the
+ * diagonal number from the bottom up.
+ *
+ * The "divide and conquer" traversal through the Myers graph looks like this:
+ *
+ * | d= 0 1 2 3 2 1 0
+ * ----+--------------------------------------------
+ * k= | c=
+ * 4 | 3
+ * |
+ * 3 | 3,0 5,2 2
+ * | / \
+ * 2 | 2,0 5,3 1
+ * | / \
+ * 1 | 1,0 4,3 >= 4,3 5,4<-- 0
+ * | / / \ /
+ * 0 | -->0,0 3,3 4,4 -1
+ * | \ / /
+ * -1 | 0,1 1,2 3,4 -2
+ * | \ /
+ * -2 | 0,2 -3
+ * | \
+ * | 0,3
+ * | forward-> <-backward
+ *
+ * x,y pairs here are the coordinates in the Myers graph:
+ * x = atom index in left-side source, y = atom index in the right-side source.
+ *
+ * Only one forward column and one backward column are kept in mem, each need at
+ * most left.len + 1 + right.len items. Note that each d step occupies either
+ * the even or the odd items of a column: if e.g. the previous column is in the
+ * odd items, the next column is formed in the even items, without overwriting
+ * the previous column's results.
+ *
+ * Also note that from the diagonal index k and the x coordinate, the y
+ * coordinate can be derived:
+ * y = x - k
+ * Hence the state array only needs to keep the x coordinate, i.e. the position
+ * in the left-hand file, and the y coordinate, i.e. position in the right-hand
+ * file, is derived from the index in the state array.
+ *
+ * The two traces meet at 4,3, the first step (here found in the forward
+ * traversal) where a forward position is on or past a backward traced position
+ * on the same diagonal.
+ *
+ * This divides the problem space into:
+ *
+ * 0 1 2 3 4 5
+ * A B C D E
+ * 0 o-o-o-o-o
+ * X | | | | |
+ * 1 o-o-o-o-o
+ * B | |\| | |
+ * 2 o-o-o-o-o
+ * C | | |\| |
+ * 3 o-o-o-o-*-o *: forward and backward meet here
+ * Y | |
+ * 4 o-o
+ *
+ * Doing the same on each section lead to:
+ *
+ * 0 1 2 3 4 5
+ * A B C D E
+ * 0 o-o
+ * X | |
+ * 1 o-b b: backward d=1 first reaches here (sliding up the snake)
+ * B \ f: then forward d=2 reaches here (sliding down the snake)
+ * 2 o As result, the box from b to f is found to be identical;
+ * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial
+ * 3 f-o tail 3,3 to 4,3.
+ *
+ * 3 o-*
+ * Y |
+ * 4 o *: forward and backward meet here
+ *
+ * and solving the last top left box gives:
+ *
+ * 0 1 2 3 4 5
+ * A B C D E -A
+ * 0 o-o +X
+ * X | B
+ * 1 o C
+ * B \ -D
+ * 2 o -E
+ * C \ +Y
+ * 3 o-o-o
+ * Y |
+ * 4 o
+ *
+ */
+
+#define xk_to_y(X, K) ((X) - (K))
+#define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
+#define k_to_c(K, DELTA) ((K) + (DELTA))
+#define c_to_k(C, DELTA) ((C) - (DELTA))
+
+/* Do one forwards step in the "divide and conquer" graph traversal.
+ * left: the left side to diff.
+ * right: the right side to diff against.
+ * kd_forward: the traversal state for forwards traversal, modified by this
+ * function.
+ * This is carried over between invocations with increasing d.
+ * kd_forward points at the center of the state array, allowing
+ * negative indexes.
+ * kd_backward: the traversal state for backwards traversal, to find a meeting
+ * point.
+ * Since forwards is done first, kd_backward will be valid for d -
+ * 1, not d.
+ * kd_backward points at the center of the state array, allowing
+ * negative indexes.
+ * d: Step or distance counter, indicating for what value of d the kd_forward
+ * should be populated.
+ * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should
+ * be for d == 0.
+ * meeting_snake: resulting meeting point, if any.
+ * Return true when a meeting point has been identified.
+ */
+static int
+diff_divide_myers_forward(bool *found_midpoint,
+ struct diff_data *left, struct diff_data *right,
+ int *kd_forward, int *kd_backward, int d,
+ struct diff_box *meeting_snake)
+{
+ int delta = (int)right->atoms.len - (int)left->atoms.len;
+ int k;
+ int x;
+ int prev_x;
+ int prev_y;
+ int x_before_slide;
+ *found_midpoint = false;
+
+ for (k = d; k >= -d; k -= 2) {
+ if (k < -(int)right->atoms.len || k > (int)left->atoms.len) {
+ /* This diagonal is completely outside of the Myers
+ * graph, don't calculate it. */
+ if (k < 0) {
+ /* We are traversing negatively, and already
+ * below the entire graph, nothing will come of
+ * this. */
+ debug(" break\n");
+ break;
+ }
+ debug(" continue\n");
+ continue;
+ }
+ if (d == 0) {
+ /* This is the initializing step. There is no prev_k
+ * yet, get the initial x from the top left of the Myers
+ * graph. */
+ x = 0;
+ prev_x = x;
+ prev_y = xk_to_y(x, k);
+ }
+ /* Favoring "-" lines first means favoring moving rightwards in
+ * the Myers graph.
+ * For this, all k should derive from k - 1, only the bottom
+ * most k derive from k + 1:
+ *
+ * | d= 0 1 2
+ * ----+----------------
+ * k= |
+ * 2 | 2,0 <-- from prev_k = 2 - 1 = 1
+ * | /
+ * 1 | 1,0
+ * | /
+ * 0 | -->0,0 3,3
+ * | \\ /
+ * -1 | 0,1 <-- bottom most for d=1 from
+ * | \\ prev_k = -1 + 1 = 0
+ * -2 | 0,2 <-- bottom most for d=2 from
+ * prev_k = -2 + 1 = -1
+ *
+ * Except when a k + 1 from a previous run already means a
+ * further advancement in the graph.
+ * If k == d, there is no k + 1 and k - 1 is the only option.
+ * If k < d, use k + 1 in case that yields a larger x. Also use
+ * k + 1 if k - 1 is outside the graph.
+ */
+ else if (k > -d
+ && (k == d
+ || (k - 1 >= -(int)right->atoms.len
+ && kd_forward[k - 1] >= kd_forward[k + 1]))) {
+ /* Advance from k - 1.
+ * From position prev_k, step to the right in the Myers
+ * graph: x += 1.
+ */
+ int prev_k = k - 1;
+ prev_x = kd_forward[prev_k];
+ prev_y = xk_to_y(prev_x, prev_k);
+ x = prev_x + 1;
+ } else {
+ /* The bottom most one.
+ * From position prev_k, step to the bottom in the Myers
+ * graph: y += 1.
+ * Incrementing y is achieved by decrementing k while
+ * keeping the same x.
+ * (since we're deriving y from y = x - k).
+ */
+ int prev_k = k + 1;
+ prev_x = kd_forward[prev_k];
+ prev_y = xk_to_y(prev_x, prev_k);
+ x = prev_x;
+ }
+
+ x_before_slide = x;
+ /* Slide down any snake that we might find here. */
+ while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) {
+ bool same;
+ int r = diff_atom_same(&same,
+ &left->atoms.head[x],
+ &right->atoms.head[
+ xk_to_y(x, k)]);
+ if (r)
+ return r;
+ if (!same)
+ break;
+ x++;
+ }
+ kd_forward[k] = x;
+#if 0
+ if (x_before_slide != x) {
+ debug(" down %d similar lines\n", x - x_before_slide);
+ }
+
+#if DEBUG
+ {
+ int fi;
+ for (fi = d; fi >= k; fi--) {
+ debug("kd_forward[%d] = (%d, %d)\n", fi,
+ kd_forward[fi], kd_forward[fi] - fi);
+ }
+ }
+#endif
+#endif
+
+ if (x < 0 || x > left->atoms.len
+ || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len)
+ continue;
+
+ /* Figured out a new forwards traversal, see if this has gone
+ * onto or even past a preceding backwards traversal.
+ *
+ * If the delta in length is odd, then d and backwards_d hit the
+ * same state indexes:
+ * | d= 0 1 2 1 0
+ * ----+---------------- ----------------
+ * k= | c=
+ * 4 | 3
+ * |
+ * 3 | 2
+ * | same
+ * 2 | 2,0====5,3 1
+ * | / \
+ * 1 | 1,0 5,4<-- 0
+ * | / /
+ * 0 | -->0,0 3,3====4,4 -1
+ * | \ /
+ * -1 | 0,1 -2
+ * | \
+ * -2 | 0,2 -3
+ * |
+ *
+ * If the delta is even, they end up off-by-one, i.e. on
+ * different diagonals:
+ *
+ * | d= 0 1 2 1 0
+ * ----+---------------- ----------------
+ * | c=
+ * 3 | 3
+ * |
+ * 2 | 2,0 off 2
+ * | / \\
+ * 1 | 1,0 4,3 1
+ * | / // \
+ * 0 | -->0,0 3,3 4,4<-- 0
+ * | \ / /
+ * -1 | 0,1 3,4 -1
+ * | \ //
+ * -2 | 0,2 -2
+ * |
+ *
+ * So in the forward path, we can only match up diagonals when
+ * the delta is odd.
+ */
+ if ((delta & 1) == 0)
+ continue;
+ /* Forwards is done first, so the backwards one was still at
+ * d - 1. Can't do this for d == 0. */
+ int backwards_d = d - 1;
+ if (backwards_d < 0)
+ continue;
+
+ /* If both sides have the same length, forward and backward
+ * start on the same diagonal, meaning the backwards state index
+ * c == k.
+ * As soon as the lengths are not the same, the backwards
+ * traversal starts on a different diagonal, and c = k shifted
+ * by the difference in length.
+ */
+ int c = k_to_c(k, delta);
+
+ /* When the file sizes are very different, the traversal trees
+ * start on far distant diagonals.
+ * They don't necessarily meet straight on. See whether this
+ * forward value is on a diagonal that is also valid in
+ * kd_backward[], and match them if so. */
+ if (c >= -backwards_d && c <= backwards_d) {
+ /* Current k is on a diagonal that exists in
+ * kd_backward[]. If the two x positions have met or
+ * passed (forward walked onto or past backward), then
+ * we've found a midpoint / a mid-box.
+ *
+ * When forwards and backwards traversals meet, the
+ * endpoints of the mid-snake are not the two points in
+ * kd_forward and kd_backward, but rather the section
+ * that was slid (if any) of the current
+ * forward/backward traversal only.
+ *
+ * For example:
+ *
+ * o
+ * \
+ * o
+ * \
+ * o
+ * \
+ * o
+ * \
+ * X o o
+ * | | |
+ * o-o-o o
+ * \|
+ * M
+ * \
+ * o
+ * \
+ * A o
+ * | |
+ * o-o-o
+ *
+ * The forward traversal reached M from the top and slid
+ * downwards to A. The backward traversal already
+ * reached X, which is not a straight line from M
+ * anymore, so picking a mid-snake from M to X would
+ * yield a mistake.
+ *
+ * The correct mid-snake is between M and A. M is where
+ * the forward traversal hit the diagonal that the
+ * backward traversal has already passed, and A is what
+ * it reaches when sliding down identical lines.
+ */
+ int backward_x = kd_backward[c];
+ if (x >= backward_x) {
+ if (x_before_slide != x) {
+ /* met after sliding up a mid-snake */
+ *meeting_snake = (struct diff_box){
+ .left_start = x_before_slide,
+ .left_end = x,
+ .right_start = xc_to_y(x_before_slide,
+ c, delta),
+ .right_end = xk_to_y(x, k),
+ };
+ } else {
+ /* met after a side step, non-identical
+ * line. Mark that as box divider
+ * instead. This makes sure that
+ * myers_divide never returns the same
+ * box that came as input, avoiding
+ * "infinite" looping. */
+ *meeting_snake = (struct diff_box){
+ .left_start = prev_x,
+ .left_end = x,
+ .right_start = prev_y,
+ .right_end = xk_to_y(x, k),
+ };
+ }
+ debug("HIT x=(%u,%u) - y=(%u,%u)\n",
+ meeting_snake->left_start,
+ meeting_snake->right_start,
+ meeting_snake->left_end,
+ meeting_snake->right_end);
+ debug_dump_myers_graph(left, right, NULL,
+ kd_forward, d,
+ kd_backward, d-1);
+ *found_midpoint = true;
+ return 0;
+ }
+ }
+ }
+
+ return 0;
+}
+
+/* Do one backwards step in the "divide and conquer" graph traversal.
+ * left: the left side to diff.
+ * right: the right side to diff against.
+ * kd_forward: the traversal state for forwards traversal, to find a meeting
+ * point.
+ * Since forwards is done first, after this, both kd_forward and
+ * kd_backward will be valid for d.
+ * kd_forward points at the center of the state array, allowing
+ * negative indexes.
+ * kd_backward: the traversal state for backwards traversal, to find a meeting
+ * point.
+ * This is carried over between invocations with increasing d.
+ * kd_backward points at the center of the state array, allowing
+ * negative indexes.
+ * d: Step or distance counter, indicating for what value of d the kd_backward
+ * should be populated.
+ * Before the first invocation, kd_backward[0] shall point at the bottom
+ * right of the Myers graph (left.len, right.len).
+ * The first invocation will be for d == 1.
+ * meeting_snake: resulting meeting point, if any.
+ * Return true when a meeting point has been identified.
+ */
+static int
+diff_divide_myers_backward(bool *found_midpoint,
+ struct diff_data *left, struct diff_data *right,
+ int *kd_forward, int *kd_backward, int d,
+ struct diff_box *meeting_snake)
+{
+ int delta = (int)right->atoms.len - (int)left->atoms.len;
+ int c;
+ int x;
+ int prev_x;
+ int prev_y;
+ int x_before_slide;
+
+ *found_midpoint = false;
+
+ for (c = d; c >= -d; c -= 2) {
+ if (c < -(int)left->atoms.len || c > (int)right->atoms.len) {
+ /* This diagonal is completely outside of the Myers
+ * graph, don't calculate it. */
+ if (c < 0) {
+ /* We are traversing negatively, and already
+ * below the entire graph, nothing will come of
+ * this. */
+ break;
+ }
+ continue;
+ }
+ if (d == 0) {
+ /* This is the initializing step. There is no prev_c
+ * yet, get the initial x from the bottom right of the
+ * Myers graph. */
+ x = left->atoms.len;
+ prev_x = x;
+ prev_y = xc_to_y(x, c, delta);
+ }
+ /* Favoring "-" lines first means favoring moving rightwards in
+ * the Myers graph.
+ * For this, all c should derive from c - 1, only the bottom
+ * most c derive from c + 1:
+ *
+ * 2 1 0
+ * ---------------------------------------------------
+ * c=
+ * 3
+ *
+ * from prev_c = c - 1 --> 5,2 2
+ * \
+ * 5,3 1
+ * \
+ * 4,3 5,4<-- 0
+ * \ /
+ * bottom most for d=1 from c + 1 --> 4,4 -1
+ * /
+ * bottom most for d=2 --> 3,4 -2
+ *
+ * Except when a c + 1 from a previous run already means a
+ * further advancement in the graph.
+ * If c == d, there is no c + 1 and c - 1 is the only option.
+ * If c < d, use c + 1 in case that yields a larger x.
+ * Also use c + 1 if c - 1 is outside the graph.
+ */
+ else if (c > -d && (c == d
+ || (c - 1 >= -(int)right->atoms.len
+ && kd_backward[c - 1] <= kd_backward[c + 1]))) {
+ /* A top one.
+ * From position prev_c, step upwards in the Myers
+ * graph: y -= 1.
+ * Decrementing y is achieved by incrementing c while
+ * keeping the same x. (since we're deriving y from
+ * y = x - c + delta).
+ */
+ int prev_c = c - 1;
+ prev_x = kd_backward[prev_c];
+ prev_y = xc_to_y(prev_x, prev_c, delta);
+ x = prev_x;
+ } else {
+ /* The bottom most one.
+ * From position prev_c, step to the left in the Myers
+ * graph: x -= 1.
+ */
+ int prev_c = c + 1;
+ prev_x = kd_backward[prev_c];
+ prev_y = xc_to_y(prev_x, prev_c, delta);
+ x = prev_x - 1;
+ }
+
+ /* Slide up any snake that we might find here (sections of
+ * identical lines on both sides). */
+#if 0
+ debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c,
+ delta),
+ xc_to_y(x, c, delta)-1);
+ if (x > 0) {
+ debug(" l=");
+ debug_dump_atom(left, right, &left->atoms.head[x-1]);
+ }
+ if (xc_to_y(x, c, delta) > 0) {
+ debug(" r=");
+ debug_dump_atom(right, left,
+ &right->atoms.head[xc_to_y(x, c, delta)-1]);
+ }
+#endif
+ x_before_slide = x;
+ while (x > 0 && xc_to_y(x, c, delta) > 0) {
+ bool same;
+ int r = diff_atom_same(&same,
+ &left->atoms.head[x-1],
+ &right->atoms.head[
+ xc_to_y(x, c, delta)-1]);
+ if (r)
+ return r;
+ if (!same)
+ break;
+ x--;
+ }
+ kd_backward[c] = x;
+#if 0
+ if (x_before_slide != x) {
+ debug(" up %d similar lines\n", x_before_slide - x);
+ }
+
+ if (DEBUG) {
+ int fi;
+ for (fi = d; fi >= c; fi--) {
+ debug("kd_backward[%d] = (%d, %d)\n",
+ fi,
+ kd_backward[fi],
+ kd_backward[fi] - fi + delta);
+ }
+ }
+#endif
+
+ if (x < 0 || x > left->atoms.len
+ || xc_to_y(x, c, delta) < 0
+ || xc_to_y(x, c, delta) > right->atoms.len)
+ continue;
+
+ /* Figured out a new backwards traversal, see if this has gone
+ * onto or even past a preceding forwards traversal.
+ *
+ * If the delta in length is even, then d and backwards_d hit
+ * the same state indexes -- note how this is different from in
+ * the forwards traversal, because now both d are the same:
+ *
+ * | d= 0 1 2 2 1 0
+ * ----+---------------- --------------------
+ * k= | c=
+ * 4 |
+ * |
+ * 3 | 3
+ * | same
+ * 2 | 2,0====5,2 2
+ * | / \
+ * 1 | 1,0 5,3 1
+ * | / / \
+ * 0 | -->0,0 3,3====4,3 5,4<-- 0
+ * | \ / /
+ * -1 | 0,1 4,4 -1
+ * | \
+ * -2 | 0,2 -2
+ * |
+ * -3
+ * If the delta is odd, they end up off-by-one, i.e. on
+ * different diagonals.
+ * So in the backward path, we can only match up diagonals when
+ * the delta is even.
+ */
+ if ((delta & 1) != 0)
+ continue;
+ /* Forwards was done first, now both d are the same. */
+ int forwards_d = d;
+
+ /* As soon as the lengths are not the same, the
+ * backwards traversal starts on a different diagonal,
+ * and c = k shifted by the difference in length.
+ */
+ int k = c_to_k(c, delta);
+
+ /* When the file sizes are very different, the traversal trees
+ * start on far distant diagonals.
+ * They don't necessarily meet straight on. See whether this
+ * backward value is also on a valid diagonal in kd_forward[],
+ * and match them if so. */
+ if (k >= -forwards_d && k <= forwards_d) {
+ /* Current c is on a diagonal that exists in
+ * kd_forward[]. If the two x positions have met or
+ * passed (backward walked onto or past forward), then
+ * we've found a midpoint / a mid-box.
+ *
+ * When forwards and backwards traversals meet, the
+ * endpoints of the mid-snake are not the two points in
+ * kd_forward and kd_backward, but rather the section
+ * that was slid (if any) of the current
+ * forward/backward traversal only.
+ *
+ * For example:
+ *
+ * o-o-o
+ * | |
+ * o A
+ * | \
+ * o o
+ * \
+ * M
+ * |\
+ * o o-o-o
+ * | | |
+ * o o X
+ * \
+ * o
+ * \
+ * o
+ * \
+ * o
+ *
+ * The backward traversal reached M from the bottom and
+ * slid upwards. The forward traversal already reached
+ * X, which is not a straight line from M anymore, so
+ * picking a mid-snake from M to X would yield a
+ * mistake.
+ *
+ * The correct mid-snake is between M and A. M is where
+ * the backward traversal hit the diagonal that the
+ * forwards traversal has already passed, and A is what
+ * it reaches when sliding up identical lines.
+ */
+
+ int forward_x = kd_forward[k];
+ if (forward_x >= x) {
+ if (x_before_slide != x) {
+ /* met after sliding down a mid-snake */
+ *meeting_snake = (struct diff_box){
+ .left_start = x,
+ .left_end = x_before_slide,
+ .right_start = xc_to_y(x, c, delta),
+ .right_end = xk_to_y(x_before_slide, k),
+ };
+ } else {
+ /* met after a side step, non-identical
+ * line. Mark that as box divider
+ * instead. This makes sure that
+ * myers_divide never returns the same
+ * box that came as input, avoiding
+ * "infinite" looping. */
+ *meeting_snake = (struct diff_box){
+ .left_start = x,
+ .left_end = prev_x,
+ .right_start = xc_to_y(x, c, delta),
+ .right_end = prev_y,
+ };
+ }
+ debug("HIT x=%u,%u - y=%u,%u\n",
+ meeting_snake->left_start,
+ meeting_snake->right_start,
+ meeting_snake->left_end,
+ meeting_snake->right_end);
+ debug_dump_myers_graph(left, right, NULL,
+ kd_forward, d,
+ kd_backward, d);
+ *found_midpoint = true;
+ return 0;
+ }
+ }
+ }
+ return 0;
+}
+
+/* Integer square root approximation */
+static int
+shift_sqrt(int val)
+{
+ int i;
+ for (i = 1; val > 0; val >>= 2)
+ i <<= 1;
+ return i;
+}
+
+#define DIFF_EFFORT_MIN 1024
+
+/* Myers "Divide et Impera": tracing forwards from the start and backwards from
+ * the end to find a midpoint that divides the problem into smaller chunks.
+ * Requires only linear amounts of memory. */
+int
+diff_algo_myers_divide(const struct diff_algo_config *algo_config,
+ struct diff_state *state)
+{
+ int rc = ENOMEM;
+ struct diff_data *left = &state->left;
+ struct diff_data *right = &state->right;
+ int *kd_buf;
+
+ debug("\n** %s\n", __func__);
+ debug("left:\n");
+ debug_dump(left);
+ debug("right:\n");
+ debug_dump(right);
+
+ /* Allocate two columns of a Myers graph, one for the forward and one
+ * for the backward traversal. */
+ unsigned int max = left->atoms.len + right->atoms.len;
+ size_t kd_len = max + 1;
+ size_t kd_buf_size = kd_len << 1;
+
+ if (state->kd_buf_size < kd_buf_size) {
+ kd_buf = reallocarray(state->kd_buf, kd_buf_size,
+ sizeof(int));
+ if (!kd_buf)
+ return ENOMEM;
+ state->kd_buf = kd_buf;
+ state->kd_buf_size = kd_buf_size;
+ } else
+ kd_buf = state->kd_buf;
+ int i;
+ for (i = 0; i < kd_buf_size; i++)
+ kd_buf[i] = -1;
+ int *kd_forward = kd_buf;
+ int *kd_backward = kd_buf + kd_len;
+ int max_effort = shift_sqrt(max/2);
+
+ if (max_effort < DIFF_EFFORT_MIN)
+ max_effort = DIFF_EFFORT_MIN;
+
+ /* The 'k' axis in Myers spans positive and negative indexes, so point
+ * the kd to the middle.
+ * It is then possible to index from -max/2 .. max/2. */
+ kd_forward += max/2;
+ kd_backward += max/2;
+
+ int d;
+ struct diff_box mid_snake = {};
+ bool found_midpoint = false;
+ for (d = 0; d <= (max/2); d++) {
+ int r;
+ r = diff_divide_myers_forward(&found_midpoint, left, right,
+ kd_forward, kd_backward, d,
+ &mid_snake);
+ if (r)
+ return r;
+ if (found_midpoint)
+ break;
+ r = diff_divide_myers_backward(&found_midpoint, left, right,
+ kd_forward, kd_backward, d,
+ &mid_snake);
+ if (r)
+ return r;
+ if (found_midpoint)
+ break;
+
+ /* Limit the effort spent looking for a mid snake. If files have
+ * very few lines in common, the effort spent to find nice mid
+ * snakes is just not worth it, the diff result will still be
+ * essentially minus everything on the left, plus everything on
+ * the right, with a few useless matches here and there. */
+ if (d > max_effort) {
+ /* pick the furthest reaching point from
+ * kd_forward and kd_backward, and use that as a
+ * midpoint, to not step into another diff algo
+ * recursion with unchanged box. */
+ int delta = (int)right->atoms.len - (int)left->atoms.len;
+ int x = 0;
+ int y;
+ int i;
+ int best_forward_i = 0;
+ int best_forward_distance = 0;
+ int best_backward_i = 0;
+ int best_backward_distance = 0;
+ int distance;
+ int best_forward_x;
+ int best_forward_y;
+ int best_backward_x;
+ int best_backward_y;
+
+ debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort);
+ debug_dump_myers_graph(left, right, NULL,
+ kd_forward, d,
+ kd_backward, d);
+
+ for (i = d; i >= -d; i -= 2) {
+ if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) {
+ x = kd_forward[i];
+ y = xk_to_y(x, i);
+ distance = x + y;
+ if (distance > best_forward_distance) {
+ best_forward_distance = distance;
+ best_forward_i = i;
+ }
+ }
+
+ if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) {
+ x = kd_backward[i];
+ y = xc_to_y(x, i, delta);
+ distance = (right->atoms.len - x)
+ + (left->atoms.len - y);
+ if (distance >= best_backward_distance) {
+ best_backward_distance = distance;
+ best_backward_i = i;
+ }
+ }
+ }
+
+ /* The myers-divide didn't meet in the middle. We just
+ * figured out the places where the forward path
+ * advanced the most, and the backward path advanced the
+ * most. Just divide at whichever one of those two is better.
+ *
+ * o-o
+ * |
+ * o
+ * \
+ * o
+ * \
+ * F <-- cut here
+ *
+ *
+ *
+ * or here --> B
+ * \
+ * o
+ * \
+ * o
+ * |
+ * o-o
+ */
+ best_forward_x = kd_forward[best_forward_i];
+ best_forward_y = xk_to_y(best_forward_x, best_forward_i);
+ best_backward_x = kd_backward[best_backward_i];
+ best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta);
+
+ if (best_forward_distance >= best_backward_distance) {
+ x = best_forward_x;
+ y = best_forward_y;
+ } else {
+ x = best_backward_x;
+ y = best_backward_y;
+ }
+
+ debug("max_effort cut at x=%d y=%d\n", x, y);
+ if (x < 0 || y < 0
+ || x > left->atoms.len || y > right->atoms.len)
+ break;
+
+ found_midpoint = true;
+ mid_snake = (struct diff_box){
+ .left_start = x,
+ .left_end = x,
+ .right_start = y,
+ .right_end = y,
+ };
+ break;
+ }
+ }
+
+ if (!found_midpoint) {
+ /* Divide and conquer failed to find a meeting point. Use the
+ * fallback_algo defined in the algo_config (leave this to the
+ * caller). This is just paranoia/sanity, we normally should
+ * always find a midpoint.
+ */
+ debug(" no midpoint \n");
+ rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
+ goto return_rc;
+ } else {
+ debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n",
+ mid_snake.left_start, mid_snake.left_end, left->atoms.len,
+ mid_snake.right_start, mid_snake.right_end,
+ right->atoms.len);
+
+ /* Section before the mid-snake. */
+ debug("Section before the mid-snake\n");
+
+ struct diff_atom *left_atom = &left->atoms.head[0];
+ unsigned int left_section_len = mid_snake.left_start;
+ struct diff_atom *right_atom = &right->atoms.head[0];
+ unsigned int right_section_len = mid_snake.right_start;
+
+ if (left_section_len && right_section_len) {
+ /* Record an unsolved chunk, the caller will apply
+ * inner_algo() on this chunk. */
+ if (!diff_state_add_chunk(state, false,
+ left_atom, left_section_len,
+ right_atom,
+ right_section_len))
+ goto return_rc;
+ } else if (left_section_len && !right_section_len) {
+ /* Only left atoms and none on the right, they form a
+ * "minus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, left_section_len,
+ right_atom, 0))
+ goto return_rc;
+ } else if (!left_section_len && right_section_len) {
+ /* No left atoms, only atoms on the right, they form a
+ * "plus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, 0,
+ right_atom,
+ right_section_len))
+ goto return_rc;
+ }
+ /* else: left_section_len == 0 and right_section_len == 0, i.e.
+ * nothing before the mid-snake. */
+
+ if (mid_snake.left_end > mid_snake.left_start
+ || mid_snake.right_end > mid_snake.right_start) {
+ /* The midpoint is a section of identical data on both
+ * sides, or a certain differing line: that section
+ * immediately becomes a solved chunk. */
+ debug("the mid-snake\n");
+ if (!diff_state_add_chunk(state, true,
+ &left->atoms.head[mid_snake.left_start],
+ mid_snake.left_end - mid_snake.left_start,
+ &right->atoms.head[mid_snake.right_start],
+ mid_snake.right_end - mid_snake.right_start))
+ goto return_rc;
+ }
+
+ /* Section after the mid-snake. */
+ debug("Section after the mid-snake\n");
+ debug(" left_end %u right_end %u\n",
+ mid_snake.left_end, mid_snake.right_end);
+ debug(" left_count %u right_count %u\n",
+ left->atoms.len, right->atoms.len);
+ left_atom = &left->atoms.head[mid_snake.left_end];
+ left_section_len = left->atoms.len - mid_snake.left_end;
+ right_atom = &right->atoms.head[mid_snake.right_end];
+ right_section_len = right->atoms.len - mid_snake.right_end;
+
+ if (left_section_len && right_section_len) {
+ /* Record an unsolved chunk, the caller will apply
+ * inner_algo() on this chunk. */
+ if (!diff_state_add_chunk(state, false,
+ left_atom, left_section_len,
+ right_atom,
+ right_section_len))
+ goto return_rc;
+ } else if (left_section_len && !right_section_len) {
+ /* Only left atoms and none on the right, they form a
+ * "minus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, left_section_len,
+ right_atom, 0))
+ goto return_rc;
+ } else if (!left_section_len && right_section_len) {
+ /* No left atoms, only atoms on the right, they form a
+ * "plus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, 0,
+ right_atom,
+ right_section_len))
+ goto return_rc;
+ }
+ /* else: left_section_len == 0 and right_section_len == 0, i.e.
+ * nothing after the mid-snake. */
+ }
+
+ rc = DIFF_RC_OK;
+
+return_rc:
+ debug("** END %s\n", __func__);
+ return rc;
+}
+
+/* Myers Diff tracing from the start all the way through to the end, requiring
+ * quadratic amounts of memory. This can fail if the required space surpasses
+ * algo_config->permitted_state_size. */
+int
+diff_algo_myers(const struct diff_algo_config *algo_config,
+ struct diff_state *state)
+{
+ /* do a diff_divide_myers_forward() without a _backward(), so that it
+ * walks forward across the entire files to reach the end. Keep each
+ * run's state, and do a final backtrace. */
+ int rc = ENOMEM;
+ struct diff_data *left = &state->left;
+ struct diff_data *right = &state->right;
+ int *kd_buf;
+
+ debug("\n** %s\n", __func__);
+ debug("left:\n");
+ debug_dump(left);
+ debug("right:\n");
+ debug_dump(right);
+ debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0);
+
+ /* Allocate two columns of a Myers graph, one for the forward and one
+ * for the backward traversal. */
+ unsigned int max = left->atoms.len + right->atoms.len;
+ size_t kd_len = max + 1 + max;
+ size_t kd_buf_size = kd_len * kd_len;
+ size_t kd_state_size = kd_buf_size * sizeof(int);
+ debug("state size: %zu\n", kd_state_size);
+ if (kd_buf_size < kd_len /* overflow? */
+ || (SIZE_MAX / kd_len ) < kd_len
+ || kd_state_size > algo_config->permitted_state_size) {
+ debug("state size %zu > permitted_state_size %zu, use fallback_algo\n",
+ kd_state_size, algo_config->permitted_state_size);
+ return DIFF_RC_USE_DIFF_ALGO_FALLBACK;
+ }
+
+ if (state->kd_buf_size < kd_buf_size) {
+ kd_buf = reallocarray(state->kd_buf, kd_buf_size,
+ sizeof(int));
+ if (!kd_buf)
+ return ENOMEM;
+ state->kd_buf = kd_buf;
+ state->kd_buf_size = kd_buf_size;
+ } else
+ kd_buf = state->kd_buf;
+
+ int i;
+ for (i = 0; i < kd_buf_size; i++)
+ kd_buf[i] = -1;
+
+ /* The 'k' axis in Myers spans positive and negative indexes, so point
+ * the kd to the middle.
+ * It is then possible to index from -max .. max. */
+ int *kd_origin = kd_buf + max;
+ int *kd_column = kd_origin;
+
+ int d;
+ int backtrack_d = -1;
+ int backtrack_k = 0;
+ int k;
+ int x, y;
+ for (d = 0; d <= max; d++, kd_column += kd_len) {
+ debug("-- %s d=%d\n", __func__, d);
+
+ for (k = d; k >= -d; k -= 2) {
+ if (k < -(int)right->atoms.len
+ || k > (int)left->atoms.len) {
+ /* This diagonal is completely outside of the
+ * Myers graph, don't calculate it. */
+ if (k < -(int)right->atoms.len)
+ debug(" %d k <"
+ " -(int)right->atoms.len %d\n",
+ k, -(int)right->atoms.len);
+ else
+ debug(" %d k > left->atoms.len %d\n", k,
+ left->atoms.len);
+ if (k < 0) {
+ /* We are traversing negatively, and
+ * already below the entire graph,
+ * nothing will come of this. */
+ debug(" break\n");
+ break;
+ }
+ debug(" continue\n");
+ continue;
+ }
+
+ if (d == 0) {
+ /* This is the initializing step. There is no
+ * prev_k yet, get the initial x from the top
+ * left of the Myers graph. */
+ x = 0;
+ } else {
+ int *kd_prev_column = kd_column - kd_len;
+
+ /* Favoring "-" lines first means favoring
+ * moving rightwards in the Myers graph.
+ * For this, all k should derive from k - 1,
+ * only the bottom most k derive from k + 1:
+ *
+ * | d= 0 1 2
+ * ----+----------------
+ * k= |
+ * 2 | 2,0 <-- from
+ * | / prev_k = 2 - 1 = 1
+ * 1 | 1,0
+ * | /
+ * 0 | -->0,0 3,3
+ * | \\ /
+ * -1 | 0,1 <-- bottom most for d=1
+ * | \\ from prev_k = -1+1 = 0
+ * -2 | 0,2 <-- bottom most for
+ * d=2 from
+ * prev_k = -2+1 = -1
+ *
+ * Except when a k + 1 from a previous run
+ * already means a further advancement in the
+ * graph.
+ * If k == d, there is no k + 1 and k - 1 is the
+ * only option.
+ * If k < d, use k + 1 in case that yields a
+ * larger x. Also use k + 1 if k - 1 is outside
+ * the graph.
+ */
+ if (k > -d
+ && (k == d
+ || (k - 1 >= -(int)right->atoms.len
+ && kd_prev_column[k - 1]
+ >= kd_prev_column[k + 1]))) {
+ /* Advance from k - 1.
+ * From position prev_k, step to the
+ * right in the Myers graph: x += 1.
+ */
+ int prev_k = k - 1;
+ int prev_x = kd_prev_column[prev_k];
+ x = prev_x + 1;
+ } else {
+ /* The bottom most one.
+ * From position prev_k, step to the
+ * bottom in the Myers graph: y += 1.
+ * Incrementing y is achieved by
+ * decrementing k while keeping the same
+ * x. (since we're deriving y from y =
+ * x - k).
+ */
+ int prev_k = k + 1;
+ int prev_x = kd_prev_column[prev_k];
+ x = prev_x;
+ }
+ }
+
+ /* Slide down any snake that we might find here. */
+ while (x < left->atoms.len
+ && xk_to_y(x, k) < right->atoms.len) {
+ bool same;
+ int r = diff_atom_same(&same,
+ &left->atoms.head[x],
+ &right->atoms.head[
+ xk_to_y(x, k)]);
+ if (r)
+ return r;
+ if (!same)
+ break;
+ x++;
+ }
+ kd_column[k] = x;
+
+ if (x == left->atoms.len
+ && xk_to_y(x, k) == right->atoms.len) {
+ /* Found a path */
+ backtrack_d = d;
+ backtrack_k = k;
+ debug("Reached the end at d = %d, k = %d\n",
+ backtrack_d, backtrack_k);
+ break;
+ }
+ }
+
+ if (backtrack_d >= 0)
+ break;
+ }
+
+ debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0);
+
+ /* backtrack. A matrix spanning from start to end of the file is ready:
+ *
+ * | d= 0 1 2 3 4
+ * ----+---------------------------------
+ * k= |
+ * 3 |
+ * |
+ * 2 | 2,0
+ * | /
+ * 1 | 1,0 4,3
+ * | / / \
+ * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0
+ * | \ / \
+ * -1 | 0,1 3,4
+ * | \
+ * -2 | 0,2
+ * |
+ *
+ * From (4,4) backwards, find the previous position that is the largest, and remember it.
+ *
+ */
+ for (d = backtrack_d, k = backtrack_k; d >= 0; d--) {
+ x = kd_column[k];
+ y = xk_to_y(x, k);
+
+ /* When the best position is identified, remember it for that
+ * kd_column.
+ * That kd_column is no longer needed otherwise, so just
+ * re-purpose kd_column[0] = x and kd_column[1] = y,
+ * so that there is no need to allocate more memory.
+ */
+ kd_column[0] = x;
+ kd_column[1] = y;
+ debug("Backtrack d=%d: xy=(%d, %d)\n",
+ d, kd_column[0], kd_column[1]);
+
+ /* Don't access memory before kd_buf */
+ if (d == 0)
+ break;
+ int *kd_prev_column = kd_column - kd_len;
+
+ /* When y == 0, backtracking downwards (k-1) is the only way.
+ * When x == 0, backtracking upwards (k+1) is the only way.
+ *
+ * | d= 0 1 2 3 4
+ * ----+---------------------------------
+ * k= |
+ * 3 |
+ * | ..y == 0
+ * 2 | 2,0
+ * | /
+ * 1 | 1,0 4,3
+ * | / / \
+ * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4,
+ * | \ / \ backtrack_k = 0
+ * -1 | 0,1 3,4
+ * | \
+ * -2 | 0,2__
+ * | x == 0
+ */
+ if (y == 0
+ || (x > 0
+ && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) {
+ k = k - 1;
+ debug("prev k=k-1=%d x=%d y=%d\n",
+ k, kd_prev_column[k],
+ xk_to_y(kd_prev_column[k], k));
+ } else {
+ k = k + 1;
+ debug("prev k=k+1=%d x=%d y=%d\n",
+ k, kd_prev_column[k],
+ xk_to_y(kd_prev_column[k], k));
+ }
+ kd_column = kd_prev_column;
+ }
+
+ /* Forwards again, this time recording the diff chunks.
+ * Definitely start from 0,0. kd_column[0] may actually point to the
+ * bottom of a snake starting at 0,0 */
+ x = 0;
+ y = 0;
+
+ kd_column = kd_origin;
+ for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) {
+ int next_x = kd_column[0];
+ int next_y = kd_column[1];
+ debug("Forward track from xy(%d,%d) to xy(%d,%d)\n",
+ x, y, next_x, next_y);
+
+ struct diff_atom *left_atom = &left->atoms.head[x];
+ int left_section_len = next_x - x;
+ struct diff_atom *right_atom = &right->atoms.head[y];
+ int right_section_len = next_y - y;
+
+ rc = ENOMEM;
+ if (left_section_len && right_section_len) {
+ /* This must be a snake slide.
+ * Snake slides have a straight line leading into them
+ * (except when starting at (0,0)). Find out whether the
+ * lead-in is horizontal or vertical:
+ *
+ * left
+ * ---------->
+ * |
+ * r| o-o o
+ * i| \ |
+ * g| o o
+ * h| \ \
+ * t| o o
+ * v
+ *
+ * If left_section_len > right_section_len, the lead-in
+ * is horizontal, meaning first remove one atom from the
+ * left before sliding down the snake.
+ * If right_section_len > left_section_len, the lead-in
+ * is vetical, so add one atom from the right before
+ * sliding down the snake. */
+ if (left_section_len == right_section_len + 1) {
+ if (!diff_state_add_chunk(state, true,
+ left_atom, 1,
+ right_atom, 0))
+ goto return_rc;
+ left_atom++;
+ left_section_len--;
+ } else if (right_section_len == left_section_len + 1) {
+ if (!diff_state_add_chunk(state, true,
+ left_atom, 0,
+ right_atom, 1))
+ goto return_rc;
+ right_atom++;
+ right_section_len--;
+ } else if (left_section_len != right_section_len) {
+ /* The numbers are making no sense. Should never
+ * happen. */
+ rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
+ goto return_rc;
+ }
+
+ if (!diff_state_add_chunk(state, true,
+ left_atom, left_section_len,
+ right_atom,
+ right_section_len))
+ goto return_rc;
+ } else if (left_section_len && !right_section_len) {
+ /* Only left atoms and none on the right, they form a
+ * "minus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, left_section_len,
+ right_atom, 0))
+ goto return_rc;
+ } else if (!left_section_len && right_section_len) {
+ /* No left atoms, only atoms on the right, they form a
+ * "plus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, 0,
+ right_atom,
+ right_section_len))
+ goto return_rc;
+ }
+
+ x = next_x;
+ y = next_y;
+ }
+
+ rc = DIFF_RC_OK;
+
+return_rc:
+ debug("** END %s rc=%d\n", __func__, rc);
+ return rc;
+}
diff --git a/usr.bin/diff/lib/diff_output.h b/usr.bin/diff/lib/diff_output.h
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_output.h
@@ -0,0 +1,109 @@
+/* Diff output generators and invocation shims. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+struct diff_input_info {
+ const char *left_path;
+ const char *right_path;
+
+ /* Set by caller of diff_output_* functions. */
+ int flags;
+#define DIFF_INPUT_LEFT_NONEXISTENT 0x00000001
+#define DIFF_INPUT_RIGHT_NONEXISTENT 0x00000002
+};
+
+struct diff_output_info {
+ /*
+ * Byte offset to each line in the generated output file.
+ * The total number of lines in the file is line_offsets.len - 1.
+ * The last offset in this array corresponds to end-of-file.
+ */
+ ARRAYLIST(off_t) line_offsets;
+ /*
+ * Type (i.e., context, minus, plus) of each line generated by the diff.
+ * nb. 0x00 to 0x3b reserved for client-defined line types.
+ */
+ ARRAYLIST(uint8_t) line_types;
+#define DIFF_LINE_HUNK 0x3c
+#define DIFF_LINE_MINUS 0x3d
+#define DIFF_LINE_PLUS 0x3e
+#define DIFF_LINE_CONTEXT 0x3f
+#define DIFF_LINE_NONE 0x40 /* binary or no EOF newline msg, etc. */
+};
+
+void diff_output_info_free(struct diff_output_info *output_info);
+
+struct diff_chunk_context {
+ struct diff_range chunk;
+ struct diff_range left, right;
+};
+
+int diff_output_plain(struct diff_output_info **output_info, FILE *dest,
+ const struct diff_input_info *info,
+ const struct diff_result *result);
+int diff_output_unidiff(struct diff_output_info **output_info,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result,
+ unsigned int context_lines);
+int diff_output_edscript(struct diff_output_info **output_info,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result);
+int diff_chunk_get_left_start(const struct diff_chunk *c,
+ const struct diff_result *r,
+ int context_lines);
+int diff_chunk_get_left_end(const struct diff_chunk *c,
+ const struct diff_result *r,
+ int context_lines);
+int diff_chunk_get_right_start(const struct diff_chunk *c,
+ const struct diff_result *r,
+ int context_lines);
+int diff_chunk_get_right_end(const struct diff_chunk *c,
+ const struct diff_result *r,
+ int context_lines);
+struct diff_chunk *diff_chunk_get(const struct diff_result *r, int chunk_idx);
+int diff_chunk_get_left_count(struct diff_chunk *c);
+int diff_chunk_get_right_count(struct diff_chunk *c);
+void diff_chunk_context_get(struct diff_chunk_context *cc,
+ const struct diff_result *r,
+ int chunk_idx, int context_lines);
+void diff_chunk_context_load_change(struct diff_chunk_context *cc,
+ int *nchunks_used,
+ struct diff_result *result,
+ int start_chunk_idx,
+ int context_lines);
+
+struct diff_output_unidiff_state;
+struct diff_output_unidiff_state *diff_output_unidiff_state_alloc(void);
+void diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state);
+void diff_output_unidiff_state_free(struct diff_output_unidiff_state *state);
+int diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
+ struct diff_output_unidiff_state *state,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc);
+int diff_output_chunk_left_version(struct diff_output_info **output_info,
+ FILE *dest,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc);
+int diff_output_chunk_right_version(struct diff_output_info **output_info,
+ FILE *dest,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc);
+
+const char *diff_output_get_label_left(const struct diff_input_info *info);
+const char *diff_output_get_label_right(const struct diff_input_info *info);
diff --git a/usr.bin/diff/lib/diff_output.c b/usr.bin/diff/lib/diff_output.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_output.c
@@ -0,0 +1,379 @@
+/* Common parts for printing diff output */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <ctype.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <unistd.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+#include <diff_output.h>
+
+#include "diff_internal.h"
+
+static int
+get_atom_byte(int *ch, struct diff_atom *atom, off_t off)
+{
+ off_t cur;
+
+ if (atom->at != NULL) {
+ *ch = atom->at[off];
+ return 0;
+ }
+
+ cur = ftello(atom->root->f);
+ if (cur == -1)
+ return errno;
+
+ if (cur != atom->pos + off &&
+ fseeko(atom->root->f, atom->pos + off, SEEK_SET) == -1)
+ return errno;
+
+ *ch = fgetc(atom->root->f);
+ if (*ch == EOF && ferror(atom->root->f))
+ return errno;
+
+ return 0;
+}
+
+#define DIFF_OUTPUT_BUF_SIZE 512
+
+int
+diff_output_lines(struct diff_output_info *outinfo, FILE *dest,
+ const char *prefix, struct diff_atom *start_atom,
+ unsigned int count)
+{
+ struct diff_atom *atom;
+ off_t outoff = 0, *offp;
+ uint8_t *typep;
+ int rc;
+
+ if (outinfo && outinfo->line_offsets.len > 0) {
+ unsigned int idx = outinfo->line_offsets.len - 1;
+ outoff = outinfo->line_offsets.head[idx];
+ }
+
+ foreach_diff_atom(atom, start_atom, count) {
+ off_t outlen = 0;
+ int i, ch, nbuf = 0;
+ unsigned int len = atom->len;
+ unsigned char buf[DIFF_OUTPUT_BUF_SIZE + 1 /* '\n' */];
+ size_t n;
+
+ n = strlcpy(buf, prefix, sizeof(buf));
+ if (n >= DIFF_OUTPUT_BUF_SIZE) /* leave room for '\n' */
+ return ENOBUFS;
+ nbuf += n;
+
+ if (len) {
+ rc = get_atom_byte(&ch, atom, len - 1);
+ if (rc)
+ return rc;
+ if (ch == '\n')
+ len--;
+ if (len) {
+ rc = get_atom_byte(&ch, atom, len - 1);
+ if (rc)
+ return rc;
+ if (ch == '\r')
+ len--;
+ }
+ }
+
+ for (i = 0; i < len; i++) {
+ rc = get_atom_byte(&ch, atom, i);
+ if (rc)
+ return rc;
+ if (nbuf >= DIFF_OUTPUT_BUF_SIZE) {
+ rc = fwrite(buf, 1, nbuf, dest);
+ if (rc != nbuf)
+ return errno;
+ outlen += rc;
+ nbuf = 0;
+ }
+ buf[nbuf++] = ch;
+ }
+ buf[nbuf++] = '\n';
+ rc = fwrite(buf, 1, nbuf, dest);
+ if (rc != nbuf)
+ return errno;
+ outlen += rc;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += outlen;
+ *offp = outoff;
+ ARRAYLIST_ADD(typep, outinfo->line_types);
+ if (typep == NULL)
+ return ENOMEM;
+ *typep = *prefix == ' ' ? DIFF_LINE_CONTEXT :
+ *prefix == '-' ? DIFF_LINE_MINUS :
+ *prefix == '+' ? DIFF_LINE_PLUS : DIFF_LINE_NONE;
+ }
+ }
+
+ return DIFF_RC_OK;
+}
+
+int
+diff_output_chunk_left_version(struct diff_output_info **output_info,
+ FILE *dest,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc)
+{
+ int rc, c_idx;
+ struct diff_output_info *outinfo = NULL;
+
+ if (diff_range_empty(&cc->left))
+ return DIFF_RC_OK;
+
+ if (output_info) {
+ *output_info = diff_output_info_alloc();
+ if (*output_info == NULL)
+ return ENOMEM;
+ outinfo = *output_info;
+ }
+
+ /* Write out all chunks on the left side. */
+ for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
+ const struct diff_chunk *c = &result->chunks.head[c_idx];
+
+ if (c->left_count) {
+ rc = diff_output_lines(outinfo, dest, "",
+ c->left_start, c->left_count);
+ if (rc)
+ return rc;
+ }
+ }
+
+ return DIFF_RC_OK;
+}
+
+int
+diff_output_chunk_right_version(struct diff_output_info **output_info,
+ FILE *dest,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc)
+{
+ int rc, c_idx;
+ struct diff_output_info *outinfo = NULL;
+
+ if (diff_range_empty(&cc->right))
+ return DIFF_RC_OK;
+
+ if (output_info) {
+ *output_info = diff_output_info_alloc();
+ if (*output_info == NULL)
+ return ENOMEM;
+ outinfo = *output_info;
+ }
+
+ /* Write out all chunks on the right side. */
+ for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
+ const struct diff_chunk *c = &result->chunks.head[c_idx];
+
+ if (c->right_count) {
+ rc = diff_output_lines(outinfo, dest, "", c->right_start,
+ c->right_count);
+ if (rc)
+ return rc;
+ }
+ }
+
+ return DIFF_RC_OK;
+}
+
+int
+diff_output_trailing_newline_msg(struct diff_output_info *outinfo, FILE *dest,
+ const struct diff_chunk *c)
+{
+ enum diff_chunk_type chunk_type = diff_chunk_type(c);
+ struct diff_atom *atom, *start_atom;
+ unsigned int atom_count;
+ int rc, ch;
+ off_t outoff = 0, *offp;
+ uint8_t *typep;
+
+
+ if (chunk_type == CHUNK_MINUS || chunk_type == CHUNK_SAME) {
+ start_atom = c->left_start;
+ atom_count = c->left_count;
+ } else if (chunk_type == CHUNK_PLUS) {
+ start_atom = c->right_start;
+ atom_count = c->right_count;
+ } else
+ return EINVAL;
+
+ /* Locate the last atom. */
+ if (atom_count == 0)
+ return EINVAL;
+ atom = &start_atom[atom_count - 1];
+
+ rc = get_atom_byte(&ch, atom, atom->len - 1);
+ if (rc != DIFF_RC_OK)
+ return rc;
+
+ if (ch != '\n') {
+ if (outinfo && outinfo->line_offsets.len > 0) {
+ unsigned int idx = outinfo->line_offsets.len - 1;
+ outoff = outinfo->line_offsets.head[idx];
+ }
+ rc = fprintf(dest, "\\ No newline at end of file\n");
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = outoff;
+ ARRAYLIST_ADD(typep, outinfo->line_types);
+ if (typep == NULL)
+ return ENOMEM;
+ *typep = DIFF_LINE_NONE;
+ }
+ }
+
+ return DIFF_RC_OK;
+}
+
+static bool
+is_function_prototype(unsigned char ch)
+{
+ return (isalpha(ch) || ch == '_' || ch == '$' ||
+ ch == '-' || ch == '+');
+}
+
+#define begins_with(s, pre) (strncmp(s, pre, sizeof(pre)-1) == 0)
+
+int
+diff_output_match_function_prototype(char *prototype, size_t prototype_size,
+ int *last_prototype_idx, const struct diff_result *result,
+ const struct diff_chunk_context *cc, unsigned int ncontext)
+{
+ struct diff_atom *start_atom, *atom;
+ const struct diff_data *data;
+ unsigned char buf[DIFF_FUNCTION_CONTEXT_SIZE];
+ const char *state = NULL;
+ int rc, i, ch;
+
+ if (result->left->atoms.len > 0 && cc->left.start > 0) {
+ data = result->left;
+ start_atom = &data->atoms.head[cc->left.start - 1];
+ } else
+ return DIFF_RC_OK;
+
+ diff_data_foreach_atom_backwards_from(start_atom, atom, data) {
+ int atom_idx = diff_atom_root_idx(data, atom);
+ if (atom_idx < *last_prototype_idx)
+ break;
+ rc = get_atom_byte(&ch, atom, 0);
+ if (rc)
+ return rc;
+ buf[0] = (unsigned char)ch;
+ if (!is_function_prototype(buf[0]))
+ continue;
+ for (i = 1; i < atom->len && i < sizeof(buf) - 1; i++) {
+ rc = get_atom_byte(&ch, atom, i);
+ if (rc)
+ return rc;
+ if (ch == '\n')
+ break;
+ buf[i] = (unsigned char)ch;
+ }
+ buf[i] = '\0';
+ if (begins_with(buf, "private:")) {
+ if (!state)
+ state = " (private)";
+ } else if (begins_with(buf, "protected:")) {
+ if (!state)
+ state = " (protected)";
+ } else if (begins_with(buf, "public:")) {
+ if (!state)
+ state = " (public)";
+ } else {
+ if (state) /* don't care about truncation */
+ strlcat(buf, state, sizeof(buf));
+ strlcpy(prototype, buf, prototype_size);
+ break;
+ }
+ }
+
+ *last_prototype_idx = diff_atom_root_idx(data, start_atom);
+ return DIFF_RC_OK;
+}
+
+struct diff_output_info *
+diff_output_info_alloc(void)
+{
+ struct diff_output_info *output_info;
+ off_t *offp;
+ uint8_t *typep;
+
+ output_info = malloc(sizeof(*output_info));
+ if (output_info != NULL) {
+ ARRAYLIST_INIT(output_info->line_offsets, 128);
+ ARRAYLIST_ADD(offp, output_info->line_offsets);
+ if (offp == NULL) {
+ diff_output_info_free(output_info);
+ return NULL;
+ }
+ *offp = 0;
+ ARRAYLIST_INIT(output_info->line_types, 128);
+ ARRAYLIST_ADD(typep, output_info->line_types);
+ if (typep == NULL) {
+ diff_output_info_free(output_info);
+ return NULL;
+ }
+ *typep = DIFF_LINE_NONE;
+ }
+ return output_info;
+}
+
+void
+diff_output_info_free(struct diff_output_info *output_info)
+{
+ ARRAYLIST_FREE(output_info->line_offsets);
+ ARRAYLIST_FREE(output_info->line_types);
+ free(output_info);
+}
+
+const char *
+diff_output_get_label_left(const struct diff_input_info *info)
+{
+ if (info->flags & DIFF_INPUT_LEFT_NONEXISTENT)
+ return "/dev/null";
+
+ return info->left_path ? info->left_path : "a";
+}
+
+const char *
+diff_output_get_label_right(const struct diff_input_info *info)
+{
+ if (info->flags & DIFF_INPUT_RIGHT_NONEXISTENT)
+ return "/dev/null";
+
+ return info->right_path ? info->right_path : "b";
+}
diff --git a/usr.bin/diff/lib/diff_output_edscript.c b/usr.bin/diff/lib/diff_output_edscript.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_output_edscript.c
@@ -0,0 +1,219 @@
+/* Produce ed(1) script output from a diff_result. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ * Copyright (c) 2020 Stefan Sperling <stsp@openbsd.org>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <stdbool.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+#include <diff_output.h>
+
+#include "diff_internal.h"
+
+static int
+output_edscript_chunk(struct diff_output_info *outinfo,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result,
+ struct diff_chunk_context *cc, off_t *outoff)
+{
+ off_t *offp;
+ int left_start, left_len, right_start, right_len;
+ int rc;
+
+ left_len = cc->left.end - cc->left.start;
+ if (left_len < 0)
+ return EINVAL;
+ else if (result->left->atoms.len == 0)
+ left_start = 0;
+ else if (left_len == 0 && cc->left.start > 0)
+ left_start = cc->left.start;
+ else if (cc->left.end > 0)
+ left_start = cc->left.start + 1;
+ else
+ left_start = cc->left.start;
+
+ right_len = cc->right.end - cc->right.start;
+ if (right_len < 0)
+ return EINVAL;
+ else if (result->right->atoms.len == 0)
+ right_start = 0;
+ else if (right_len == 0 && cc->right.start > 0)
+ right_start = cc->right.start;
+ else if (cc->right.end > 0)
+ right_start = cc->right.start + 1;
+ else
+ right_start = cc->right.start;
+
+ if (left_len == 0) {
+ /* addition */
+ if (right_len == 1) {
+ rc = fprintf(dest, "%da\n", left_start);
+ } else {
+ rc = fprintf(dest, "%da\n", left_start);
+ }
+ } else if (right_len == 0) {
+ /* deletion */
+ if (left_len == 1) {
+ rc = fprintf(dest, "%dd\n", left_start);
+ } else {
+ rc = fprintf(dest, "%d,%dd\n", left_start,
+ cc->left.end);
+ }
+ } else {
+ /* change */
+ if (left_len == 1) {
+ rc = fprintf(dest, "%dc\n", left_start);
+ } else {
+ rc = fprintf(dest, "%d,%dc\n", left_start, cc->left.end);
+ }
+ }
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ *outoff += rc;
+ *offp = *outoff;
+ }
+
+ /* Now write out the new lines in all the joined chunks. */
+ int c_idx;
+ for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
+ const struct diff_chunk *c = &result->chunks.head[c_idx];
+ if (c->left_count && !c->right_count)
+ continue;
+ if (c->right_count && !c->left_count) {
+ rc = diff_output_lines(outinfo, dest,
+ c->solved ? "" : "?",
+ c->right_start, c->right_count);
+ if (rc != DIFF_RC_OK)
+ return rc;
+
+ rc = fprintf(dest, ".\n");
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = *outoff;
+ }
+ }
+ if (cc->chunk.end == result->chunks.len) {
+ rc = diff_output_trailing_newline_msg(outinfo, dest, c);
+ if (rc != DIFF_RC_OK)
+ return rc;
+ }
+ }
+
+ return DIFF_RC_OK;
+}
+
+int
+diff_output_edscript(struct diff_output_info **output_info,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result)
+{
+ struct diff_output_info *outinfo = NULL;
+ struct diff_chunk_context cc = {};
+ int atomizer_flags = (result->left->atomizer_flags|
+ result->right->atomizer_flags);
+ int flags = (result->left->root->diff_flags |
+ result->right->root->diff_flags);
+ bool force_text = (flags & DIFF_FLAG_FORCE_TEXT_DATA);
+ bool have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA);
+ int i, rc;
+ off_t outoff = 0, *offp;
+
+ if (!result)
+ return EINVAL;
+ if (result->rc != DIFF_RC_OK)
+ return result->rc;
+
+ if (output_info) {
+ *output_info = diff_output_info_alloc();
+ if (*output_info == NULL)
+ return ENOMEM;
+ outinfo = *output_info;
+ }
+
+ if (have_binary && !force_text) {
+ for (i = 0; i < result->chunks.len; i++) {
+ struct diff_chunk *c = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(c);
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS)
+ continue;
+
+ fprintf(dest, "Binary files %s and %s differ\n",
+ diff_output_get_label_left(info),
+ diff_output_get_label_right(info));
+ break;
+ }
+
+ return DIFF_RC_OK;
+ }
+
+ /*
+ * Changes in an ed script are in reverse order, the last change to the
+ * file has to be made first to keep state while making edits.
+ */
+ for (i = result->chunks.len-1; i >= 0 ; i--) {
+ struct diff_chunk *chunk = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(chunk);
+ struct diff_chunk_context next;
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS)
+ continue;
+
+ if (diff_chunk_context_empty(&cc)) {
+ /* Note down the start point, any number of subsequent
+ * chunks may be joined up to this chunk by being
+ * directly adjacent. */
+ diff_chunk_context_get(&cc, result, i, 0);
+ continue;
+ }
+
+ /* There already is a previous chunk noted down for being
+ * printed. Does it join up with this one? */
+ diff_chunk_context_get(&next, result, i, 0);
+
+ if (diff_chunk_contexts_touch(&cc, &next)) {
+ /* This next context touches or overlaps the previous
+ * one, join. */
+ diff_chunk_contexts_merge(&cc, &next);
+ continue;
+ }
+
+ rc = output_edscript_chunk(outinfo, dest, info, result, &cc,
+ &outoff);
+ if (rc != DIFF_RC_OK)
+ return rc;
+ cc = next;
+ }
+
+ if (!diff_chunk_context_empty(&cc))
+ return output_edscript_chunk(outinfo, dest, info, result, &cc,
+ &outoff);
+ return DIFF_RC_OK;
+}
diff --git a/usr.bin/diff/lib/diff_output_plain.c b/usr.bin/diff/lib/diff_output_plain.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_output_plain.c
@@ -0,0 +1,245 @@
+/* Output all lines of a diff_result. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+#include <diff_output.h>
+
+#include "diff_internal.h"
+
+static int
+output_plain_chunk(struct diff_output_info *outinfo,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result,
+ struct diff_chunk_context *cc, off_t *outoff)
+{
+ off_t *offp;
+ int left_start, left_len, right_start, right_len;
+ int rc;
+ bool change = false;
+
+ left_len = cc->left.end - cc->left.start;
+ if (left_len < 0)
+ return EINVAL;
+ else if (result->left->atoms.len == 0)
+ left_start = 0;
+ else if (left_len == 0 && cc->left.start > 0)
+ left_start = cc->left.start;
+ else if (cc->left.end > 0)
+ left_start = cc->left.start + 1;
+ else
+ left_start = cc->left.start;
+
+ right_len = cc->right.end - cc->right.start;
+ if (right_len < 0)
+ return EINVAL;
+ else if (result->right->atoms.len == 0)
+ right_start = 0;
+ else if (right_len == 0 && cc->right.start > 0)
+ right_start = cc->right.start;
+ else if (cc->right.end > 0)
+ right_start = cc->right.start + 1;
+ else
+ right_start = cc->right.start;
+
+ if (left_len == 0) {
+ /* addition */
+ if (right_len == 1) {
+ rc = fprintf(dest, "%da%d\n", left_start, right_start);
+ } else {
+ rc = fprintf(dest, "%da%d,%d\n", left_start,
+ right_start, cc->right.end);
+ }
+ } else if (right_len == 0) {
+ /* deletion */
+ if (left_len == 1) {
+ rc = fprintf(dest, "%dd%d\n", left_start,
+ right_start);
+ } else {
+ rc = fprintf(dest, "%d,%dd%d\n", left_start,
+ cc->left.end, right_start);
+ }
+ } else {
+ /* change */
+ change = true;
+ if (left_len == 1 && right_len == 1) {
+ rc = fprintf(dest, "%dc%d\n", left_start, right_start);
+ } else if (left_len == 1) {
+ rc = fprintf(dest, "%dc%d,%d\n", left_start,
+ right_start, cc->right.end);
+ } else if (right_len == 1) {
+ rc = fprintf(dest, "%d,%dc%d\n", left_start,
+ cc->left.end, right_start);
+ } else {
+ rc = fprintf(dest, "%d,%dc%d,%d\n", left_start,
+ cc->left.end, right_start, cc->right.end);
+ }
+ }
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ *outoff += rc;
+ *offp = *outoff;
+ }
+
+ /*
+ * Now write out all the joined chunks.
+ *
+ * If the hunk denotes a change, it will come in the form of a deletion
+ * chunk followed by a addition chunk. Print a marker to break up the
+ * additions and deletions when this happens.
+ */
+ int c_idx;
+ for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
+ const struct diff_chunk *c = &result->chunks.head[c_idx];
+ if (c->left_count && !c->right_count)
+ rc = diff_output_lines(outinfo, dest,
+ c->solved ? "< " : "?",
+ c->left_start, c->left_count);
+ else if (c->right_count && !c->left_count) {
+ if (change) {
+ rc = fprintf(dest, "---\n");
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp,
+ outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ *outoff += rc;
+ *offp = *outoff;
+ }
+ }
+ rc = diff_output_lines(outinfo, dest,
+ c->solved ? "> " : "?",
+ c->right_start, c->right_count);
+ }
+ if (rc)
+ return rc;
+ if (cc->chunk.end == result->chunks.len) {
+ rc = diff_output_trailing_newline_msg(outinfo, dest, c);
+ if (rc != DIFF_RC_OK)
+ return rc;
+ }
+ }
+
+ return DIFF_RC_OK;
+}
+
+int
+diff_output_plain(struct diff_output_info **output_info,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result)
+{
+ struct diff_output_info *outinfo = NULL;
+ struct diff_chunk_context cc = {};
+ int atomizer_flags = (result->left->atomizer_flags|
+ result->right->atomizer_flags);
+ int flags = (result->left->root->diff_flags |
+ result->right->root->diff_flags);
+ bool force_text = (flags & DIFF_FLAG_FORCE_TEXT_DATA);
+ bool have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA);
+ int i, rc;
+ off_t outoff = 0, *offp;
+
+ if (!result)
+ return EINVAL;
+ if (result->rc != DIFF_RC_OK)
+ return result->rc;
+
+ if (output_info) {
+ *output_info = diff_output_info_alloc();
+ if (*output_info == NULL)
+ return ENOMEM;
+ outinfo = *output_info;
+ }
+
+ if (have_binary && !force_text) {
+ for (i = 0; i < result->chunks.len; i++) {
+ struct diff_chunk *c = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(c);
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS)
+ continue;
+
+ rc = fprintf(dest, "Binary files %s and %s differ\n",
+ diff_output_get_label_left(info),
+ diff_output_get_label_right(info));
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = outoff;
+ }
+ break;
+ }
+
+ return DIFF_RC_OK;
+ }
+
+ for (i = 0; i < result->chunks.len; i++) {
+ struct diff_chunk *chunk = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(chunk);
+ struct diff_chunk_context next;
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS)
+ continue;
+
+ if (diff_chunk_context_empty(&cc)) {
+ /* Note down the start point, any number of subsequent
+ * chunks may be joined up to this chunk by being
+ * directly adjacent. */
+ diff_chunk_context_get(&cc, result, i, 0);
+ continue;
+ }
+
+ /* There already is a previous chunk noted down for being
+ * printed. Does it join up with this one? */
+ diff_chunk_context_get(&next, result, i, 0);
+
+ if (diff_chunk_contexts_touch(&cc, &next)) {
+ /* This next context touches or overlaps the previous
+ * one, join. */
+ diff_chunk_contexts_merge(&cc, &next);
+ /* When we merge the last chunk we can end up with one
+ * hanging chunk and have to come back for it after the
+ * loop */
+ continue;
+ }
+ rc = output_plain_chunk(outinfo, dest, info, result, &cc,
+ &outoff);
+ if (rc != DIFF_RC_OK)
+ return rc;
+ cc = next;
+ }
+ if (!diff_chunk_context_empty(&cc))
+ return output_plain_chunk(outinfo, dest, info, result, &cc,
+ &outoff);
+ return DIFF_RC_OK;
+}
diff --git a/usr.bin/diff/lib/diff_output_unidiff.c b/usr.bin/diff/lib/diff_output_unidiff.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_output_unidiff.c
@@ -0,0 +1,588 @@
+/* Produce a unidiff output from a diff_result. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+#include <diff_output.h>
+
+#include "diff_internal.h"
+#include "diff_debug.h"
+
+bool
+diff_chunk_context_empty(const struct diff_chunk_context *cc)
+{
+ return diff_range_empty(&cc->chunk);
+}
+
+int
+diff_chunk_get_left_start(const struct diff_chunk *c,
+ const struct diff_result *r, int context_lines)
+{
+ int left_start = diff_atom_root_idx(r->left, c->left_start);
+ return MAX(0, left_start - context_lines);
+}
+
+int
+diff_chunk_get_left_end(const struct diff_chunk *c,
+ const struct diff_result *r, int context_lines)
+{
+ int left_start = diff_chunk_get_left_start(c, r, 0);
+ return MIN(r->left->atoms.len,
+ left_start + c->left_count + context_lines);
+}
+
+int
+diff_chunk_get_right_start(const struct diff_chunk *c,
+ const struct diff_result *r, int context_lines)
+{
+ int right_start = diff_atom_root_idx(r->right, c->right_start);
+ return MAX(0, right_start - context_lines);
+}
+
+int
+diff_chunk_get_right_end(const struct diff_chunk *c,
+ const struct diff_result *r, int context_lines)
+{
+ int right_start = diff_chunk_get_right_start(c, r, 0);
+ return MIN(r->right->atoms.len,
+ right_start + c->right_count + context_lines);
+}
+
+struct diff_chunk *
+diff_chunk_get(const struct diff_result *r, int chunk_idx)
+{
+ return &r->chunks.head[chunk_idx];
+}
+
+int
+diff_chunk_get_left_count(struct diff_chunk *c)
+{
+ return c->left_count;
+}
+
+int
+diff_chunk_get_right_count(struct diff_chunk *c)
+{
+ return c->right_count;
+}
+
+void
+diff_chunk_context_get(struct diff_chunk_context *cc, const struct diff_result *r,
+ int chunk_idx, int context_lines)
+{
+ const struct diff_chunk *c = &r->chunks.head[chunk_idx];
+ int left_start = diff_chunk_get_left_start(c, r, context_lines);
+ int left_end = diff_chunk_get_left_end(c, r, context_lines);
+ int right_start = diff_chunk_get_right_start(c, r, context_lines);
+ int right_end = diff_chunk_get_right_end(c, r, context_lines);
+
+ *cc = (struct diff_chunk_context){
+ .chunk = {
+ .start = chunk_idx,
+ .end = chunk_idx + 1,
+ },
+ .left = {
+ .start = left_start,
+ .end = left_end,
+ },
+ .right = {
+ .start = right_start,
+ .end = right_end,
+ },
+ };
+}
+
+bool
+diff_chunk_contexts_touch(const struct diff_chunk_context *cc,
+ const struct diff_chunk_context *other)
+{
+ return diff_ranges_touch(&cc->chunk, &other->chunk)
+ || diff_ranges_touch(&cc->left, &other->left)
+ || diff_ranges_touch(&cc->right, &other->right);
+}
+
+void
+diff_chunk_contexts_merge(struct diff_chunk_context *cc,
+ const struct diff_chunk_context *other)
+{
+ diff_ranges_merge(&cc->chunk, &other->chunk);
+ diff_ranges_merge(&cc->left, &other->left);
+ diff_ranges_merge(&cc->right, &other->right);
+}
+
+void
+diff_chunk_context_load_change(struct diff_chunk_context *cc,
+ int *nchunks_used,
+ struct diff_result *result,
+ int start_chunk_idx,
+ int context_lines)
+{
+ int i;
+ int seen_minus = 0, seen_plus = 0;
+
+ if (nchunks_used)
+ *nchunks_used = 0;
+
+ for (i = start_chunk_idx; i < result->chunks.len; i++) {
+ struct diff_chunk *chunk = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(chunk);
+ struct diff_chunk_context next;
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS) {
+ if (nchunks_used)
+ (*nchunks_used)++;
+ if (seen_minus || seen_plus)
+ break;
+ else
+ continue;
+ } else if (t == CHUNK_MINUS)
+ seen_minus = 1;
+ else if (t == CHUNK_PLUS)
+ seen_plus = 1;
+
+ if (diff_chunk_context_empty(cc)) {
+ /* Note down the start point, any number of subsequent
+ * chunks may be joined up to this chunk by being
+ * directly adjacent. */
+ diff_chunk_context_get(cc, result, i, context_lines);
+ if (nchunks_used)
+ (*nchunks_used)++;
+ continue;
+ }
+
+ /* There already is a previous chunk noted down for being
+ * printed. Does it join up with this one? */
+ diff_chunk_context_get(&next, result, i, context_lines);
+
+ if (diff_chunk_contexts_touch(cc, &next)) {
+ /* This next context touches or overlaps the previous
+ * one, join. */
+ diff_chunk_contexts_merge(cc, &next);
+ if (nchunks_used)
+ (*nchunks_used)++;
+ continue;
+ } else
+ break;
+ }
+}
+
+struct diff_output_unidiff_state {
+ bool header_printed;
+ char prototype[DIFF_FUNCTION_CONTEXT_SIZE];
+ int last_prototype_idx;
+};
+
+struct diff_output_unidiff_state *
+diff_output_unidiff_state_alloc(void)
+{
+ struct diff_output_unidiff_state *state;
+
+ state = calloc(1, sizeof(struct diff_output_unidiff_state));
+ if (state != NULL)
+ diff_output_unidiff_state_reset(state);
+ return state;
+}
+
+void
+diff_output_unidiff_state_reset(struct diff_output_unidiff_state *state)
+{
+ state->header_printed = false;
+ memset(state->prototype, 0, sizeof(state->prototype));
+ state->last_prototype_idx = 0;
+}
+
+void
+diff_output_unidiff_state_free(struct diff_output_unidiff_state *state)
+{
+ free(state);
+}
+
+static int
+output_unidiff_chunk(struct diff_output_info *outinfo, FILE *dest,
+ struct diff_output_unidiff_state *state,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ bool print_header, bool show_function_prototypes,
+ const struct diff_chunk_context *cc, unsigned int ncontext)
+{
+ int rc, left_start, left_len, right_start, right_len;
+ off_t outoff = 0, *offp;
+ uint8_t *typep;
+
+ if (diff_range_empty(&cc->left) && diff_range_empty(&cc->right))
+ return DIFF_RC_OK;
+
+ if (outinfo && outinfo->line_offsets.len > 0) {
+ unsigned int idx = outinfo->line_offsets.len - 1;
+ outoff = outinfo->line_offsets.head[idx];
+ }
+
+ if (print_header && !(state->header_printed)) {
+ rc = fprintf(dest, "--- %s\n",
+ diff_output_get_label_left(info));
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = outoff;
+ ARRAYLIST_ADD(typep, outinfo->line_types);
+ if (typep == NULL)
+ return ENOMEM;
+ *typep = DIFF_LINE_MINUS;
+ }
+ rc = fprintf(dest, "+++ %s\n",
+ diff_output_get_label_right(info));
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = outoff;
+ ARRAYLIST_ADD(typep, outinfo->line_types);
+ if (typep == NULL)
+ return ENOMEM;
+ *typep = DIFF_LINE_PLUS;
+ }
+ state->header_printed = true;
+ }
+
+ left_len = cc->left.end - cc->left.start;
+ if (result->left->atoms.len == 0)
+ left_start = 0;
+ else if (left_len == 0 && cc->left.start > 0)
+ left_start = cc->left.start;
+ else
+ left_start = cc->left.start + 1;
+
+ right_len = cc->right.end - cc->right.start;
+ if (result->right->atoms.len == 0)
+ right_start = 0;
+ else if (right_len == 0 && cc->right.start > 0)
+ right_start = cc->right.start;
+ else
+ right_start = cc->right.start + 1;
+
+ if (show_function_prototypes) {
+ rc = diff_output_match_function_prototype(state->prototype,
+ sizeof(state->prototype), &state->last_prototype_idx,
+ result, cc, ncontext);
+ if (rc)
+ return rc;
+ }
+
+ if (left_len == 1 && right_len == 1) {
+ rc = fprintf(dest, "@@ -%d +%d @@%s%s\n",
+ left_start, right_start,
+ state->prototype[0] ? " " : "",
+ state->prototype[0] ? state->prototype : "");
+ } else if (left_len == 1 && right_len != 1) {
+ rc = fprintf(dest, "@@ -%d +%d,%d @@%s%s\n",
+ left_start, right_start, right_len,
+ state->prototype[0] ? " " : "",
+ state->prototype[0] ? state->prototype : "");
+ } else if (left_len != 1 && right_len == 1) {
+ rc = fprintf(dest, "@@ -%d,%d +%d @@%s%s\n",
+ left_start, left_len, right_start,
+ state->prototype[0] ? " " : "",
+ state->prototype[0] ? state->prototype : "");
+ } else {
+ rc = fprintf(dest, "@@ -%d,%d +%d,%d @@%s%s\n",
+ left_start, left_len, right_start, right_len,
+ state->prototype[0] ? " " : "",
+ state->prototype[0] ? state->prototype : "");
+ }
+ if (rc < 0)
+ return errno;
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = outoff;
+ ARRAYLIST_ADD(typep, outinfo->line_types);
+ if (typep == NULL)
+ return ENOMEM;
+ *typep = DIFF_LINE_HUNK;
+ }
+
+ /* Got the absolute line numbers where to start printing, and the index
+ * of the interesting (non-context) chunk.
+ * To print context lines above the interesting chunk, nipping on the
+ * previous chunk index may be necessary.
+ * It is guaranteed to be only context lines where left == right, so it
+ * suffices to look on the left. */
+ const struct diff_chunk *first_chunk;
+ int chunk_start_line;
+ first_chunk = &result->chunks.head[cc->chunk.start];
+ chunk_start_line = diff_atom_root_idx(result->left,
+ first_chunk->left_start);
+ if (cc->left.start < chunk_start_line) {
+ rc = diff_output_lines(outinfo, dest, " ",
+ &result->left->atoms.head[cc->left.start],
+ chunk_start_line - cc->left.start);
+ if (rc)
+ return rc;
+ }
+
+ /* Now write out all the joined chunks and contexts between them */
+ int c_idx;
+ for (c_idx = cc->chunk.start; c_idx < cc->chunk.end; c_idx++) {
+ const struct diff_chunk *c = &result->chunks.head[c_idx];
+
+ if (c->left_count && c->right_count)
+ rc = diff_output_lines(outinfo, dest,
+ c->solved ? " " : "?",
+ c->left_start, c->left_count);
+ else if (c->left_count && !c->right_count)
+ rc = diff_output_lines(outinfo, dest,
+ c->solved ? "-" : "?",
+ c->left_start, c->left_count);
+ else if (c->right_count && !c->left_count)
+ rc = diff_output_lines(outinfo, dest,
+ c->solved ? "+" : "?",
+ c->right_start, c->right_count);
+ if (rc)
+ return rc;
+
+ if (cc->chunk.end == result->chunks.len) {
+ rc = diff_output_trailing_newline_msg(outinfo, dest, c);
+ if (rc != DIFF_RC_OK)
+ return rc;
+ }
+ }
+
+ /* Trailing context? */
+ const struct diff_chunk *last_chunk;
+ int chunk_end_line;
+ last_chunk = &result->chunks.head[cc->chunk.end - 1];
+ chunk_end_line = diff_atom_root_idx(result->left,
+ last_chunk->left_start
+ + last_chunk->left_count);
+ if (cc->left.end > chunk_end_line) {
+ rc = diff_output_lines(outinfo, dest, " ",
+ &result->left->atoms.head[chunk_end_line],
+ cc->left.end - chunk_end_line);
+ if (rc)
+ return rc;
+
+ rc = diff_output_trailing_newline_msg(outinfo, dest,
+ &result->chunks.head[result->chunks.len - 1]);
+ if (rc != DIFF_RC_OK)
+ return rc;
+ }
+
+ return DIFF_RC_OK;
+}
+
+int
+diff_output_unidiff_chunk(struct diff_output_info **output_info, FILE *dest,
+ struct diff_output_unidiff_state *state,
+ const struct diff_input_info *info,
+ const struct diff_result *result,
+ const struct diff_chunk_context *cc)
+{
+ struct diff_output_info *outinfo = NULL;
+ int flags = (result->left->root->diff_flags |
+ result->right->root->diff_flags);
+ bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
+
+ if (output_info) {
+ *output_info = diff_output_info_alloc();
+ if (*output_info == NULL)
+ return ENOMEM;
+ outinfo = *output_info;
+ }
+
+ return output_unidiff_chunk(outinfo, dest, state, info,
+ result, false, show_function_prototypes, cc, 0);
+}
+
+int
+diff_output_unidiff(struct diff_output_info **output_info,
+ FILE *dest, const struct diff_input_info *info,
+ const struct diff_result *result,
+ unsigned int context_lines)
+{
+ struct diff_output_unidiff_state *state;
+ struct diff_chunk_context cc = {};
+ struct diff_output_info *outinfo = NULL;
+ int atomizer_flags = (result->left->atomizer_flags|
+ result->right->atomizer_flags);
+ int flags = (result->left->root->diff_flags |
+ result->right->root->diff_flags);
+ bool show_function_prototypes = (flags & DIFF_FLAG_SHOW_PROTOTYPES);
+ bool force_text = (flags & DIFF_FLAG_FORCE_TEXT_DATA);
+ bool have_binary = (atomizer_flags & DIFF_ATOMIZER_FOUND_BINARY_DATA);
+ off_t outoff = 0, *offp;
+ uint8_t *typep;
+ int rc, i;
+
+ if (!result)
+ return EINVAL;
+ if (result->rc != DIFF_RC_OK)
+ return result->rc;
+
+ if (output_info) {
+ *output_info = diff_output_info_alloc();
+ if (*output_info == NULL)
+ return ENOMEM;
+ outinfo = *output_info;
+ }
+
+ if (have_binary && !force_text) {
+ for (i = 0; i < result->chunks.len; i++) {
+ struct diff_chunk *c = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(c);
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS)
+ continue;
+
+ if (outinfo && outinfo->line_offsets.len > 0) {
+ unsigned int idx =
+ outinfo->line_offsets.len - 1;
+ outoff = outinfo->line_offsets.head[idx];
+ }
+
+ rc = fprintf(dest, "Binary files %s and %s differ\n",
+ diff_output_get_label_left(info),
+ diff_output_get_label_right(info));
+ if (outinfo) {
+ ARRAYLIST_ADD(offp, outinfo->line_offsets);
+ if (offp == NULL)
+ return ENOMEM;
+ outoff += rc;
+ *offp = outoff;
+ ARRAYLIST_ADD(typep, outinfo->line_types);
+ if (typep == NULL)
+ return ENOMEM;
+ *typep = DIFF_LINE_NONE;
+ }
+ break;
+ }
+
+ return DIFF_RC_OK;
+ }
+
+ state = diff_output_unidiff_state_alloc();
+ if (state == NULL) {
+ if (output_info) {
+ diff_output_info_free(*output_info);
+ *output_info = NULL;
+ }
+ return ENOMEM;
+ }
+
+#if DEBUG
+ unsigned int check_left_pos, check_right_pos;
+ check_left_pos = 0;
+ check_right_pos = 0;
+ for (i = 0; i < result->chunks.len; i++) {
+ struct diff_chunk *c = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(c);
+
+ debug("[%d] %s lines L%d R%d @L %d @R %d\n",
+ i, (t == CHUNK_MINUS ? "minus" :
+ (t == CHUNK_PLUS ? "plus" :
+ (t == CHUNK_SAME ? "same" : "?"))),
+ c->left_count,
+ c->right_count,
+ c->left_start ? diff_atom_root_idx(result->left, c->left_start) : -1,
+ c->right_start ? diff_atom_root_idx(result->right, c->right_start) : -1);
+ assert(check_left_pos == diff_atom_root_idx(result->left, c->left_start));
+ assert(check_right_pos == diff_atom_root_idx(result->right, c->right_start));
+ check_left_pos += c->left_count;
+ check_right_pos += c->right_count;
+
+ }
+ assert(check_left_pos == result->left->atoms.len);
+ assert(check_right_pos == result->right->atoms.len);
+#endif
+
+ for (i = 0; i < result->chunks.len; i++) {
+ struct diff_chunk *c = &result->chunks.head[i];
+ enum diff_chunk_type t = diff_chunk_type(c);
+ struct diff_chunk_context next;
+
+ if (t != CHUNK_MINUS && t != CHUNK_PLUS)
+ continue;
+
+ if (diff_chunk_context_empty(&cc)) {
+ /* These are the first lines being printed.
+ * Note down the start point, any number of subsequent
+ * chunks may be joined up to this unidiff chunk by
+ * context lines or by being directly adjacent. */
+ diff_chunk_context_get(&cc, result, i, context_lines);
+ debug("new chunk to be printed:"
+ " chunk %d-%d left %d-%d right %d-%d\n",
+ cc.chunk.start, cc.chunk.end,
+ cc.left.start, cc.left.end,
+ cc.right.start, cc.right.end);
+ continue;
+ }
+
+ /* There already is a previous chunk noted down for being
+ * printed. Does it join up with this one? */
+ diff_chunk_context_get(&next, result, i, context_lines);
+ debug("new chunk to be printed:"
+ " chunk %d-%d left %d-%d right %d-%d\n",
+ next.chunk.start, next.chunk.end,
+ next.left.start, next.left.end,
+ next.right.start, next.right.end);
+
+ if (diff_chunk_contexts_touch(&cc, &next)) {
+ /* This next context touches or overlaps the previous
+ * one, join. */
+ diff_chunk_contexts_merge(&cc, &next);
+ debug("new chunk to be printed touches previous chunk,"
+ " now: left %d-%d right %d-%d\n",
+ cc.left.start, cc.left.end,
+ cc.right.start, cc.right.end);
+ continue;
+ }
+
+ /* No touching, so the previous context is complete with a gap
+ * between it and this next one. Print the previous one and
+ * start fresh here. */
+ debug("new chunk to be printed does not touch previous chunk;"
+ " print left %d-%d right %d-%d\n",
+ cc.left.start, cc.left.end, cc.right.start, cc.right.end);
+ output_unidiff_chunk(outinfo, dest, state, info, result,
+ true, show_function_prototypes, &cc, context_lines);
+ cc = next;
+ debug("new unprinted chunk is left %d-%d right %d-%d\n",
+ cc.left.start, cc.left.end, cc.right.start, cc.right.end);
+ }
+
+ if (!diff_chunk_context_empty(&cc))
+ output_unidiff_chunk(outinfo, dest, state, info, result,
+ true, show_function_prototypes, &cc, context_lines);
+ diff_output_unidiff_state_free(state);
+ return DIFF_RC_OK;
+}
diff --git a/usr.bin/diff/lib/diff_patience.c b/usr.bin/diff/lib/diff_patience.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/diff_patience.c
@@ -0,0 +1,647 @@
+/* Implementation of the Patience Diff algorithm invented by Bram Cohen:
+ * Divide a diff problem into smaller chunks by an LCS (Longest Common Sequence)
+ * of common-unique lines. */
+/*
+ * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <assert.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#include <arraylist.h>
+#include <diff_main.h>
+
+#include "diff_internal.h"
+#include "diff_debug.h"
+
+/* Algorithm to find unique lines:
+ * 0: stupidly iterate atoms
+ * 1: qsort
+ * 2: mergesort
+ */
+#define UNIQUE_STRATEGY 1
+
+/* Per-atom state for the Patience Diff algorithm */
+struct atom_patience {
+#if UNIQUE_STRATEGY == 0
+ bool unique_here;
+#endif
+ bool unique_in_both;
+ struct diff_atom *pos_in_other;
+ struct diff_atom *prev_stack;
+ struct diff_range identical_lines;
+};
+
+/* A diff_atom has a backpointer to the root diff_data. That points to the
+ * current diff_data, a possibly smaller section of the root. That current
+ * diff_data->algo_data is a pointer to an array of struct atom_patience. The
+ * atom's index in current diff_data gives the index in the atom_patience array.
+ */
+#define PATIENCE(ATOM) \
+ (((struct atom_patience*)((ATOM)->root->current->algo_data))\
+ [diff_atom_idx((ATOM)->root->current, ATOM)])
+
+#if UNIQUE_STRATEGY == 0
+
+/* Stupid iteration and comparison of all atoms */
+static int
+diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count)
+{
+ struct diff_atom *i;
+ unsigned int count = 0;
+ diff_data_foreach_atom(i, d) {
+ PATIENCE(i).unique_here = true;
+ PATIENCE(i).unique_in_both = true;
+ count++;
+ }
+ diff_data_foreach_atom(i, d) {
+ struct diff_atom *j;
+
+ if (!PATIENCE(i).unique_here)
+ continue;
+
+ diff_data_foreach_atom_from(i + 1, j, d) {
+ bool same;
+ int r = diff_atom_same(&same, i, j);
+ if (r)
+ return r;
+ if (!same)
+ continue;
+ if (PATIENCE(i).unique_here) {
+ PATIENCE(i).unique_here = false;
+ PATIENCE(i).unique_in_both = false;
+ count--;
+ }
+ PATIENCE(j).unique_here = false;
+ PATIENCE(j).unique_in_both = false;
+ count--;
+ }
+ }
+ if (unique_count)
+ *unique_count = count;
+ return 0;
+}
+
+/* Mark those lines as PATIENCE(atom).unique_in_both = true that appear exactly
+ * once in each side. */
+static int
+diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
+ unsigned int *unique_in_both_count)
+{
+ /* Derive the final unique_in_both count without needing an explicit
+ * iteration. So this is just some optimiziation to save one iteration
+ * in the end. */
+ unsigned int unique_in_both;
+ int r;
+
+ r = diff_atoms_mark_unique(left, &unique_in_both);
+ if (r)
+ return r;
+ r = diff_atoms_mark_unique(right, NULL);
+ if (r)
+ return r;
+
+ debug("unique_in_both %u\n", unique_in_both);
+
+ struct diff_atom *i;
+ diff_data_foreach_atom(i, left) {
+ if (!PATIENCE(i).unique_here)
+ continue;
+ struct diff_atom *j;
+ int found_in_b = 0;
+ diff_data_foreach_atom(j, right) {
+ bool same;
+ int r = diff_atom_same(&same, i, j);
+ if (r)
+ return r;
+ if (!same)
+ continue;
+ if (!PATIENCE(j).unique_here) {
+ found_in_b = 2; /* or more */
+ break;
+ } else {
+ found_in_b = 1;
+ PATIENCE(j).pos_in_other = i;
+ PATIENCE(i).pos_in_other = j;
+ }
+ }
+
+ if (found_in_b == 0 || found_in_b > 1) {
+ PATIENCE(i).unique_in_both = false;
+ unique_in_both--;
+ debug("unique_in_both %u (%d) ", unique_in_both,
+ found_in_b);
+ debug_dump_atom(left, NULL, i);
+ }
+ }
+
+ /* Still need to unmark right[*]->patience.unique_in_both for atoms that
+ * don't exist in left */
+ diff_data_foreach_atom(i, right) {
+ if (!PATIENCE(i).unique_here
+ || !PATIENCE(i).unique_in_both)
+ continue;
+ struct diff_atom *j;
+ bool found_in_a = false;
+ diff_data_foreach_atom(j, left) {
+ bool same;
+ int r;
+ if (!PATIENCE(j).unique_in_both)
+ continue;
+ r = diff_atom_same(&same, i, j);
+ if (r)
+ return r;
+ if (!same)
+ continue;
+ found_in_a = true;
+ break;
+ }
+
+ if (!found_in_a)
+ PATIENCE(i).unique_in_both = false;
+ }
+
+ if (unique_in_both_count)
+ *unique_in_both_count = unique_in_both;
+ return 0;
+}
+
+#else /* UNIQUE_STRATEGY != 0 */
+
+/* Use an optimized sorting algorithm (qsort, mergesort) to find unique lines */
+
+static int diff_atoms_compar(const void *_a, const void *_b)
+{
+ const struct diff_atom *a = *(struct diff_atom**)_a;
+ const struct diff_atom *b = *(struct diff_atom**)_b;
+ int cmp;
+ int rc = 0;
+
+ /* If there's been an error (e.g. I/O error) in a previous compar, we
+ * have no way to abort the sort but just report the rc and stop
+ * comparing. Make sure to catch errors on either side. If atoms are
+ * from more than one diff_data, make sure the error, if any, spreads
+ * to all of them, so we can cut short all future comparisons. */
+ if (a->root->err)
+ rc = a->root->err;
+ if (b->root->err)
+ rc = b->root->err;
+ if (rc) {
+ a->root->err = rc;
+ b->root->err = rc;
+ /* just return 'equal' to not swap more positions */
+ return 0;
+ }
+
+ /* Sort by the simplistic hash */
+ if (a->hash < b->hash)
+ return -1;
+ if (a->hash > b->hash)
+ return 1;
+
+ /* If hashes are the same, the lines may still differ. Do a full cmp. */
+ rc = diff_atom_cmp(&cmp, a, b);
+
+ if (rc) {
+ /* Mark the I/O error so that the caller can find out about it.
+ * For the case atoms are from more than one diff_data, mark in
+ * both. */
+ a->root->err = rc;
+ if (a->root != b->root)
+ b->root->err = rc;
+ return 0;
+ }
+
+ return cmp;
+}
+
+/* Sort an array of struct diff_atom* in-place. */
+static int diff_atoms_sort(struct diff_atom *atoms[],
+ size_t atoms_count)
+{
+#if UNIQUE_STRATEGY == 1
+ qsort(atoms, atoms_count, sizeof(struct diff_atom*), diff_atoms_compar);
+#else
+ mergesort(atoms, atoms_count, sizeof(struct diff_atom*),
+ diff_atoms_compar);
+#endif
+ return atoms[0]->root->err;
+}
+
+static int
+diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right,
+ unsigned int *unique_in_both_count_p)
+{
+ struct diff_atom *a;
+ struct diff_atom *b;
+ struct diff_atom **all_atoms;
+ unsigned int len = 0;
+ unsigned int i;
+ unsigned int unique_in_both_count = 0;
+ int rc;
+
+ all_atoms = calloc(left->atoms.len + right->atoms.len,
+ sizeof(struct diff_atom *));
+ if (all_atoms == NULL)
+ return ENOMEM;
+
+ left->err = 0;
+ right->err = 0;
+ left->root->err = 0;
+ right->root->err = 0;
+ diff_data_foreach_atom(a, left) {
+ all_atoms[len++] = a;
+ }
+ diff_data_foreach_atom(b, right) {
+ all_atoms[len++] = b;
+ }
+
+ rc = diff_atoms_sort(all_atoms, len);
+ if (rc)
+ goto free_and_exit;
+
+ /* Now we have a sorted array of atom pointers. All similar lines are
+ * adjacent. Walk through the array and mark those that are unique on
+ * each side, but exist once in both sources. */
+ for (i = 0; i < len; i++) {
+ bool same;
+ unsigned int next_differing_i;
+ unsigned int last_identical_i;
+ unsigned int j;
+ unsigned int count_first_side = 1;
+ unsigned int count_other_side = 0;
+ a = all_atoms[i];
+ debug("a: ");
+ debug_dump_atom(a->root, NULL, a);
+
+ /* Do as few diff_atom_cmp() as possible: first walk forward
+ * only using the cheap hash as indicator for differing atoms;
+ * then walk backwards until hitting an identical atom. */
+ for (next_differing_i = i + 1; next_differing_i < len;
+ next_differing_i++) {
+ b = all_atoms[next_differing_i];
+ if (a->hash != b->hash)
+ break;
+ }
+ for (last_identical_i = next_differing_i - 1;
+ last_identical_i > i;
+ last_identical_i--) {
+ b = all_atoms[last_identical_i];
+ rc = diff_atom_same(&same, a, b);
+ if (rc)
+ goto free_and_exit;
+ if (same)
+ break;
+ }
+ next_differing_i = last_identical_i + 1;
+
+ for (j = i+1; j < next_differing_i; j++) {
+ b = all_atoms[j];
+ /* A following atom is the same. See on which side the
+ * repetition counts. */
+ if (a->root == b->root)
+ count_first_side ++;
+ else
+ count_other_side ++;
+ debug("b: ");
+ debug_dump_atom(b->root, NULL, b);
+ debug(" count_first_side=%d count_other_side=%d\n",
+ count_first_side, count_other_side);
+ }
+
+ /* Counted a section of similar atoms, put the results back to
+ * the atoms. */
+ if ((count_first_side == 1)
+ && (count_other_side == 1)) {
+ b = all_atoms[i+1];
+ PATIENCE(a).unique_in_both = true;
+ PATIENCE(a).pos_in_other = b;
+ PATIENCE(b).unique_in_both = true;
+ PATIENCE(b).pos_in_other = a;
+ unique_in_both_count++;
+ }
+
+ /* j now points at the first atom after 'a' that is not
+ * identical to 'a'. j is always > i. */
+ i = j - 1;
+ }
+ *unique_in_both_count_p = unique_in_both_count;
+ rc = 0;
+free_and_exit:
+ free(all_atoms);
+ return rc;
+}
+#endif /* UNIQUE_STRATEGY != 0 */
+
+/* binary search to find the stack to put this atom "card" on. */
+static int
+find_target_stack(struct diff_atom *atom,
+ struct diff_atom **patience_stacks,
+ unsigned int patience_stacks_count)
+{
+ unsigned int lo = 0;
+ unsigned int hi = patience_stacks_count;
+ while (lo < hi) {
+ unsigned int mid = (lo + hi) >> 1;
+
+ if (PATIENCE(patience_stacks[mid]).pos_in_other
+ < PATIENCE(atom).pos_in_other)
+ lo = mid + 1;
+ else
+ hi = mid;
+ }
+ return lo;
+}
+
+/* Among the lines that appear exactly once in each side, find the longest
+ * streak that appear in both files in the same order (with other stuff allowed
+ * to interleave). Use patience sort for that, as in the Patience Diff
+ * algorithm.
+ * See https://bramcohen.livejournal.com/73318.html and, for a much more
+ * detailed explanation,
+ * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */
+int
+diff_algo_patience(const struct diff_algo_config *algo_config,
+ struct diff_state *state)
+{
+ int rc;
+ struct diff_data *left = &state->left;
+ struct diff_data *right = &state->right;
+ struct atom_patience *atom_patience_left =
+ calloc(left->atoms.len, sizeof(struct atom_patience));
+ struct atom_patience *atom_patience_right =
+ calloc(right->atoms.len, sizeof(struct atom_patience));
+ unsigned int unique_in_both_count;
+ struct diff_atom **lcs = NULL;
+
+ debug("\n** %s\n", __func__);
+
+ left->root->current = left;
+ right->root->current = right;
+ left->algo_data = atom_patience_left;
+ right->algo_data = atom_patience_right;
+
+ /* Find those lines that appear exactly once in 'left' and exactly once
+ * in 'right'. */
+ rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count);
+ if (rc)
+ goto free_and_exit;
+
+ debug("unique_in_both_count %u\n", unique_in_both_count);
+ debug("left:\n");
+ debug_dump(left);
+ debug("right:\n");
+ debug_dump(right);
+
+ if (!unique_in_both_count) {
+ /* Cannot apply Patience, tell the caller to use fallback_algo
+ * instead. */
+ rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK;
+ goto free_and_exit;
+ }
+
+ rc = ENOMEM;
+
+ /* An array of Longest Common Sequence is the result of the below
+ * subscope: */
+ unsigned int lcs_count = 0;
+ struct diff_atom *lcs_tail = NULL;
+
+ {
+ /* This subscope marks the lifetime of the atom_pointers
+ * allocation */
+
+ /* One chunk of storage for atom pointers */
+ struct diff_atom **atom_pointers;
+ atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2,
+ sizeof(struct diff_atom*));
+ if (atom_pointers == NULL)
+ return ENOMEM;
+ /* Half for the list of atoms that still need to be put on
+ * stacks */
+ struct diff_atom **uniques = atom_pointers;
+
+ /* Half for the patience sort state's "card stacks" -- we
+ * remember only each stack's topmost "card" */
+ struct diff_atom **patience_stacks;
+ patience_stacks = atom_pointers + unique_in_both_count;
+ unsigned int patience_stacks_count = 0;
+
+ /* Take all common, unique items from 'left' ... */
+
+ struct diff_atom *atom;
+ struct diff_atom **uniques_end = uniques;
+ diff_data_foreach_atom(atom, left) {
+ if (!PATIENCE(atom).unique_in_both)
+ continue;
+ *uniques_end = atom;
+ uniques_end++;
+ }
+
+ /* ...and sort them to the order found in 'right'.
+ * The idea is to find the leftmost stack that has a higher line
+ * number and add it to the stack's top.
+ * If there is no such stack, open a new one on the right. The
+ * line number is derived from the atom*, which are array items
+ * and hence reflect the relative position in the source file.
+ * So we got the common-uniques from 'left' and sort them
+ * according to PATIENCE(atom).pos_in_other. */
+ unsigned int i;
+ for (i = 0; i < unique_in_both_count; i++) {
+ atom = uniques[i];
+ unsigned int target_stack;
+ target_stack = find_target_stack(atom, patience_stacks,
+ patience_stacks_count);
+ assert(target_stack <= patience_stacks_count);
+ patience_stacks[target_stack] = atom;
+ if (target_stack == patience_stacks_count)
+ patience_stacks_count++;
+
+ /* Record a back reference to the next stack on the
+ * left, which will form the final longest sequence
+ * later. */
+ PATIENCE(atom).prev_stack = target_stack ?
+ patience_stacks[target_stack - 1] : NULL;
+
+ {
+ int xx;
+ for (xx = 0; xx < patience_stacks_count; xx++) {
+ debug(" %s%d",
+ (xx == target_stack) ? ">" : "",
+ diff_atom_idx(right,
+ PATIENCE(patience_stacks[xx]).pos_in_other));
+ }
+ debug("\n");
+ }
+ }
+
+ /* backtrace through prev_stack references to form the final
+ * longest common sequence */
+ lcs_tail = patience_stacks[patience_stacks_count - 1];
+ lcs_count = patience_stacks_count;
+
+ /* uniques and patience_stacks are no longer needed.
+ * Backpointers are in PATIENCE(atom).prev_stack */
+ free(atom_pointers);
+ }
+
+ lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*));
+ struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1];
+ struct diff_atom *atom;
+ for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) {
+ assert(lcs_backtrace_pos >= lcs);
+ *lcs_backtrace_pos = atom;
+ }
+
+ unsigned int i;
+ if (DEBUG) {
+ debug("\npatience LCS:\n");
+ for (i = 0; i < lcs_count; i++) {
+ debug("\n L "); debug_dump_atom(left, right, lcs[i]);
+ debug(" R "); debug_dump_atom(right, left,
+ PATIENCE(lcs[i]).pos_in_other);
+ }
+ }
+
+
+ /* TODO: For each common-unique line found (now listed in lcs), swallow
+ * lines upwards and downwards that are identical on each side. Requires
+ * a way to represent atoms being glued to adjacent atoms. */
+
+ debug("\ntraverse LCS, possibly recursing:\n");
+
+ /* Now we have pinned positions in both files at which it makes sense to
+ * divide the diff problem into smaller chunks. Go into the next round:
+ * look at each section in turn, trying to again find common-unique
+ * lines in those smaller sections. As soon as no more are found, the
+ * remaining smaller sections are solved by Myers. */
+ /* left_pos and right_pos are indexes in left/right->atoms.head until
+ * which the atoms are already handled (added to result chunks). */
+ unsigned int left_pos = 0;
+ unsigned int right_pos = 0;
+ for (i = 0; i <= lcs_count; i++) {
+ struct diff_atom *atom;
+ struct diff_atom *atom_r;
+ /* left_idx and right_idx are indexes of the start of this
+ * section of identical lines on both sides.
+ * left_pos marks the index of the first still unhandled line,
+ * left_idx is the start of an identical section some way
+ * further down, and this loop adds an unsolved chunk of
+ * [left_pos..left_idx[ and a solved chunk of
+ * [left_idx..identical_lines.end[. */
+ unsigned int left_idx;
+ unsigned int right_idx;
+
+ debug("iteration %u of %u left_pos %u right_pos %u\n",
+ i, lcs_count, left_pos, right_pos);
+
+ if (i < lcs_count) {
+ atom = lcs[i];
+ atom_r = PATIENCE(atom).pos_in_other;
+ debug("lcs[%u] = left[%u] = right[%u]\n", i,
+ diff_atom_idx(left, atom), diff_atom_idx(right, atom_r));
+ left_idx = diff_atom_idx(left, atom);
+ right_idx = diff_atom_idx(right, atom_r);
+ } else {
+ /* There are no more identical lines until the end of
+ * left and right. */
+ atom = NULL;
+ atom_r = NULL;
+ left_idx = left->atoms.len;
+ right_idx = right->atoms.len;
+ }
+
+ /* 'atom' (if not NULL) now marks an atom that matches on both
+ * sides according to patience-diff (a common-unique identical
+ * atom in both files).
+ * Handle the section before and the atom itself; the section
+ * after will be handled by the next loop iteration -- note that
+ * i loops to last element + 1 ("i <= lcs_count"), so that there
+ * will be another final iteration to pick up the last remaining
+ * items after the last LCS atom.
+ */
+
+ debug("iteration %u left_pos %u left_idx %u"
+ " right_pos %u right_idx %u\n",
+ i, left_pos, left_idx, right_pos, right_idx);
+
+ /* Section before the matching atom */
+ struct diff_atom *left_atom = &left->atoms.head[left_pos];
+ unsigned int left_section_len = left_idx - left_pos;
+
+ struct diff_atom *right_atom = &(right->atoms.head[right_pos]);
+ unsigned int right_section_len = right_idx - right_pos;
+
+ if (left_section_len && right_section_len) {
+ /* Record an unsolved chunk, the caller will apply
+ * inner_algo() on this chunk. */
+ if (!diff_state_add_chunk(state, false,
+ left_atom, left_section_len,
+ right_atom,
+ right_section_len))
+ goto free_and_exit;
+ } else if (left_section_len && !right_section_len) {
+ /* Only left atoms and none on the right, they form a
+ * "minus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, left_section_len,
+ right_atom, 0))
+ goto free_and_exit;
+ } else if (!left_section_len && right_section_len) {
+ /* No left atoms, only atoms on the right, they form a
+ * "plus" chunk, then. */
+ if (!diff_state_add_chunk(state, true,
+ left_atom, 0,
+ right_atom, right_section_len))
+ goto free_and_exit;
+ }
+ /* else: left_section_len == 0 and right_section_len == 0, i.e.
+ * nothing here. */
+
+ /* The atom found to match on both sides forms a chunk of equals
+ * on each side. In the very last iteration of this loop, there
+ * is no matching atom, we were just cleaning out the remaining
+ * lines. */
+ if (atom) {
+ void *ok;
+ ok = diff_state_add_chunk(state, true,
+ atom, 1,
+ PATIENCE(atom).pos_in_other, 1);
+ if (!ok)
+ goto free_and_exit;
+ }
+ left_pos = left_idx + 1;
+ right_pos = right_idx + 1;
+ debug("end of iteration %u left_pos %u left_idx %u"
+ " right_pos %u right_idx %u\n",
+ i, left_pos, left_idx, right_pos, right_idx);
+ }
+ debug("** END %s\n", __func__);
+
+ rc = DIFF_RC_OK;
+
+free_and_exit:
+ left->root->current = NULL;
+ right->root->current = NULL;
+ free(atom_patience_left);
+ free(atom_patience_right);
+ if (lcs)
+ free(lcs);
+ return rc;
+}
diff --git a/usr.bin/diff/lib/recallocarray.c b/usr.bin/diff/lib/recallocarray.c
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/recallocarray.c
@@ -0,0 +1,80 @@
+/* $OpenBSD: recallocarray.c,v 1.1 2017/03/06 18:44:21 otto Exp $ */
+/*
+ * Copyright (c) 2008, 2017 Otto Moerbeek <otto@drijf.net>
+ *
+ * Permission to use, copy, modify, and distribute this software for any
+ * purpose with or without fee is hereby granted, provided that the above
+ * copyright notice and this permission notice appear in all copies.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
+ * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
+ * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
+ * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
+ * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
+ * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
+ * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
+ */
+
+#include <errno.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+#include <unistd.h>
+
+/*
+ * This is sqrt(SIZE_MAX+1), as s1*s2 <= SIZE_MAX
+ * if both s1 < MUL_NO_OVERFLOW and s2 < MUL_NO_OVERFLOW
+ */
+#define MUL_NO_OVERFLOW ((size_t)1 << (sizeof(size_t) * 4))
+
+void *
+recallocarray(void *ptr, size_t oldnmemb, size_t newnmemb, size_t size)
+{
+ size_t oldsize, newsize;
+ void *newptr;
+
+ if (ptr == NULL)
+ return calloc(newnmemb, size);
+
+ if ((newnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
+ newnmemb > 0 && SIZE_MAX / newnmemb < size) {
+ errno = ENOMEM;
+ return NULL;
+ }
+ newsize = newnmemb * size;
+
+ if ((oldnmemb >= MUL_NO_OVERFLOW || size >= MUL_NO_OVERFLOW) &&
+ oldnmemb > 0 && SIZE_MAX / oldnmemb < size) {
+ errno = EINVAL;
+ return NULL;
+ }
+ oldsize = oldnmemb * size;
+
+ /*
+ * Don't bother too much if we're shrinking just a bit,
+ * we do not shrink for series of small steps, oh well.
+ */
+ if (newsize <= oldsize) {
+ size_t d = oldsize - newsize;
+
+ if (d < oldsize / 2 && d < getpagesize()) {
+ memset((char *)ptr + newsize, 0, d);
+ return ptr;
+ }
+ }
+
+ newptr = malloc(newsize);
+ if (newptr == NULL)
+ return NULL;
+
+ if (newsize > oldsize) {
+ memcpy(newptr, ptr, oldsize);
+ memset((char *)newptr + oldsize, 0, newsize - oldsize);
+ } else
+ memcpy(newptr, ptr, newsize);
+
+ explicit_bzero(ptr, oldsize);
+ free(ptr);
+
+ return newptr;
+}
diff --git a/usr.bin/diff/lib/stdlib.h b/usr.bin/diff/lib/stdlib.h
new file mode 100644
--- /dev/null
+++ b/usr.bin/diff/lib/stdlib.h
@@ -0,0 +1,20 @@
+/*
+ * stdlib.h compatibility shim
+ * Public domain
+ */
+
+#include_next <stdlib.h>
+
+#ifndef DIFFCOMPAT_STDLIB_H
+#define DIFFCOMPAT_STDLIB_H
+
+#include <sys/types.h>
+#include <stdint.h>
+
+const char * getprogname(void);
+
+void *reallocarray(void *, size_t, size_t);
+void *recallocarray(void *, size_t, size_t, size_t);
+int mergesort(void *, size_t, size_t, int (*cmp)(const void *, const void *));
+
+#endif
diff --git a/usr.bin/diff/tests/diff_test.sh b/usr.bin/diff/tests/diff_test.sh
--- a/usr.bin/diff/tests/diff_test.sh
+++ b/usr.bin/diff/tests/diff_test.sh
@@ -290,7 +290,7 @@
"$(atf_get_srcdir)/functionname.in" "$(atf_get_srcdir)/functionname_objcm.in"
atf_check -o file:$(atf_get_srcdir)/functionname_objcclassm.out -s exit:1 \
- diff -u -p -L functionname.in -L functionname_objcclassm.in \
+ diff -A stone -u -p -L functionname.in -L functionname_objcclassm.in \
"$(atf_get_srcdir)/functionname.in" "$(atf_get_srcdir)/functionname_objcclassm.in"
}

File Metadata

Mime Type
text/plain
Expires
Wed, Jul 8, 8:34 PM (10 h, 5 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
34859025
Default Alt Text
D36860.id111338.diff (179 KB)

Event Timeline