From d9a9f23d0b3f1676d5656b76301341c0037d15b7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Dag-Erling=20Sm=C3=B8rgrav?= 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.h | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-) (limited to 'usr.bin/diff/diff.h') diff --git a/usr.bin/diff/diff.h b/usr.bin/diff/diff.h index 214ff77a362f..679b95e7ca94 100644 --- a/usr.bin/diff/diff.h +++ b/usr.bin/diff/diff.h @@ -51,6 +51,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 @@ -73,6 +81,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 */ @@ -98,8 +109,9 @@ struct excludes { }; 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 bool diff_algorithm_set; extern int tabsize, width; extern char *start, *ifdefname, *diffargs, *label[2]; extern char *ignore_pats, *most_recent_pat; @@ -110,5 +122,7 @@ extern struct excludes *excludes_list; extern regex_t ignore_re, most_recent_re; int diffreg(char *, char *, int, int); +int diffreg_new(char *, char *, int, int); +bool can_libdiff(int); void diffdir(char *, char *, int); void print_status(int, char *, char *, const char *); -- cgit v1.2.3