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 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 + * + * 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 +#include +#include +#include + +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include "diff.h" +#include +#include +#include + +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 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 + * + * 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 + * + * 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 +#include +#include +#include +#include +#include +#include + +#include +#include + +#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 + * + * 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 +#include +#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 + * + * 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 + * + * 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 + * + * 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 +#include +#include +#include +#include +#include +#include +#include +#include +#include + +#include + +#include +#include + +#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 + * + * 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 +#include +#include +#include +#include +#include + +#include +#include + +#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 + * + * 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 + * + * 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 +#include +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +#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 + * Copyright (c) 2020 Stefan Sperling + * + * 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 +#include +#include +#include +#include + +#include +#include +#include + +#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 + * + * 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 +#include +#include +#include +#include + +#include +#include +#include + +#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 + * + * 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 +#include +#include +#include +#include +#include +#include + +#include +#include +#include + +#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 + * + * 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 +#include +#include +#include +#include +#include + +#include +#include + +#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 + * + * 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 +#include +#include +#include +#include + +/* + * 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 + +#ifndef DIFFCOMPAT_STDLIB_H +#define DIFFCOMPAT_STDLIB_H + +#include +#include + +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" }