From d9a9f23d0b3f1676d5656b76301341c0037d15b7 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Dag-Erling=20Sm=C3=B8rgrav?= <des@FreeBSD.org>
Date: Wed, 27 Mar 2024 11:03:33 +0100
Subject: diff: Integrate libdiff from OpenBSD GoT.

This adds support for two new diff algorithms, Myers diff and Patience
diff.

These algorithms perform a different form of search compared to the
classic Stone algorithm and support escapes when worst case scenarios
are encountered.

Add the -A flag to allow selection of the algorithm, but default to
using the new Myers diff implementation.

The libdiff implementation currently only supports a subset of input and
output options supported by diff.  When these options are used, but the
algorithm is not selected, automatically fallback to the classic Stone
algorithm until support for these modes can be added.

Based on work originally done by thj@ with contributions from kevans@.

Sponsored by:	Klara, Inc.
Reviewed by:	thj
Differential Revision:	https://reviews.freebsd.org/D44302
---
 usr.bin/diff/diff.c | 50 ++++++++++++++++++++++++++++++++++++++++++--------
 1 file changed, 42 insertions(+), 8 deletions(-)

(limited to 'usr.bin/diff/diff.c')

diff --git a/usr.bin/diff/diff.c b/usr.bin/diff/diff.c
index d947c1e01705..15ebbca28bd7 100644
--- a/usr.bin/diff/diff.c
+++ b/usr.bin/diff/diff.c
@@ -20,7 +20,6 @@
  * Materiel Command, USAF, under agreement number F39502-99-1-0512.
  */
 
-#include <sys/cdefs.h>
 #include <sys/stat.h>
 
 #include <ctype.h>
@@ -36,11 +35,12 @@
 #include "diff.h"
 #include "xmalloc.h"
 
-static const char diff_version[] = "FreeBSD diff 20220309";
+static const char diff_version[] = "FreeBSD diff 20240307";
 bool	 lflag, Nflag, Pflag, rflag, sflag, Tflag, cflag;
 bool	 ignore_file_case, suppress_common, color, noderef;
 static bool help = false;
-int	 diff_format, diff_context, status;
+int	 diff_format, diff_context, diff_algorithm, status;
+bool	 diff_algorithm_set;
 int	 tabsize = 8, width = 130;
 static int	colorflag = COLORFLAG_NEVER;
 char	*start, *ifdefname, *diffargs, *label[2];
@@ -51,7 +51,17 @@ struct stat stb1, stb2;
 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,
@@ -68,6 +78,7 @@ enum {
 };
 
 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' },
@@ -139,6 +150,8 @@ main(int argc, char **argv)
 	newarg = 1;
 	diff_context = 3;
 	diff_format = D_UNSET;
+	diff_algorithm = D_DIFFMYERS;
+	diff_algorithm_set = false;
 #define	FORMAT_MISMATCHED(type)	\
 	(diff_format != D_UNSET && diff_format != (type))
 	while ((ch = getopt_long(argc, argv, OPTIONS, longopts, NULL)) != -1) {
@@ -153,6 +166,21 @@ main(int argc, char **argv)
 				usage();
 			diff_context = (diff_context * 10) + (ch - '0');
 			break;
+		case 'A':
+			diff_algorithm = D_DIFFNONE;
+			for (struct algorithm *a = algorithms; a->name;a++) {
+				if(strcasecmp(optarg, a->name) == 0) {
+					diff_algorithm = a->id;
+					diff_algorithm_set = true;
+					break;
+				}
+			}
+
+			if (diff_algorithm == D_DIFFNONE) {
+				printf("unknown algorithm: %s\n", optarg);
+				usage();
+			}
+			break;
 		case 'a':
 			dflags |= D_FORCEASCII;
 			break;
@@ -276,8 +304,10 @@ main(int argc, char **argv)
 			break;
 		case 'W':
 			width = (int) strtonum(optarg, 1, INT_MAX, &errstr);
-			if (errstr)
-				errx(1, "width is %s: %s", errstr, optarg);
+			if (errstr) {
+				warnx("Invalid argument for width");
+				usage();
+			}
 			break;
 		case 'X':
 			read_excludes_file(optarg);
@@ -315,8 +345,10 @@ main(int argc, char **argv)
 			break;
 		case OPT_TSIZE:
 			tabsize = (int) strtonum(optarg, 1, INT_MAX, &errstr);
-			if (errstr)
-				errx(1, "tabsize is %s: %s", errstr, optarg);
+			if (errstr) {
+				warnx("Invalid argument for tabsize");
+				usage();
+			}
 			break;
 		case OPT_STRIPCR:
 			dflags |= D_STRIPCR;
@@ -437,6 +469,8 @@ main(int argc, char **argv)
 		print_status(diffreg(argv[0], argv[1], dflags, 1), argv[0],
 		    argv[1], "");
 	}
+	if (fflush(stdout) != 0)
+		err(2, "stdout");
 	exit(status);
 }
 
-- 
cgit v1.2.3