diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/GNUmakefile | 32 | ||||
| -rw-r--r-- | lib/diff_atomize_text.c | 197 | ||||
| -rw-r--r-- | lib/diff_debug.h | 226 | ||||
| -rw-r--r-- | lib/diff_internal.h | 157 | ||||
| -rw-r--r-- | lib/diff_main.c | 663 | ||||
| -rw-r--r-- | lib/diff_myers.c | 1425 | ||||
| -rw-r--r-- | lib/diff_output.c | 371 | ||||
| -rw-r--r-- | lib/diff_output_edscript.c | 190 | ||||
| -rw-r--r-- | lib/diff_output_plain.c | 246 | ||||
| -rw-r--r-- | lib/diff_output_unidiff.c | 602 | ||||
| -rw-r--r-- | lib/diff_patience.c | 647 |
11 files changed, 4756 insertions, 0 deletions
diff --git a/lib/GNUmakefile b/lib/GNUmakefile new file mode 100644 index 000000000000..cb35f757e09d --- /dev/null +++ b/lib/GNUmakefile @@ -0,0 +1,32 @@ +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 \ + $(END) + +# Compat sources +VPATH= $(CURDIR)/../compat +SRCS+= getprogname_linux.c reallocarray.c recallocarray.c merge.c \ + strlcat.c +CFLAGS+= -I$(CURDIR)/../compat/include + +OBJS = $(SRCS:.c=.o) + +libdiff.a: $(OBJS) + ar rcs $@ $^ + +CFLAGS += -fsanitize=address -fsanitize=undefined -g -O3 +CFLAGS += -Wstrict-prototypes -Wunused-variable -Wuninitialized + +%.o: %.c ./*.h ../include/*.h + gcc $(CFLAGS) -I../include -o $@ -c $< + +.PHONY: clean +clean: + -rm $(OBJS) + -rm libdiff.a diff --git a/lib/diff_atomize_text.c b/lib/diff_atomize_text.c new file mode 100644 index 000000000000..32023105af94 --- /dev/null +++ b/lib/diff_atomize_text.c @@ -0,0 +1,197 @@ +/* Split source by line breaks, and calculate a simplistic checksum. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <errno.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <unistd.h> +#include <ctype.h> + +#include <arraylist.h> +#include <diff_main.h> + +#include "diff_internal.h" +#include "diff_debug.h" + +unsigned int +diff_atom_hash_update(unsigned int hash, unsigned char atom_byte) +{ + return hash * 23 + atom_byte; +} + +static int +diff_data_atomize_text_lines_fd(struct diff_data *d) +{ + off_t pos = 0; + const off_t end = pos + d->len; + unsigned int array_size_estimate = d->len / 50; + unsigned int pow2 = 1; + bool ignore_whitespace = (d->diff_flags & DIFF_FLAG_IGNORE_WHITESPACE); + bool embedded_nul = false; + + while (array_size_estimate >>= 1) + pow2++; + + ARRAYLIST_INIT(d->atoms, 1 << pow2); + + if (fseek(d->root->f, 0L, SEEK_SET) == -1) + return errno; + + while (pos < end) { + off_t line_end = pos; + unsigned int hash = 0; + unsigned char buf[512]; + size_t r, i; + struct diff_atom *atom; + int eol = 0; + + while (eol == 0 && line_end < end) { + r = fread(buf, sizeof(char), sizeof(buf), d->root->f); + if (r == 0 && ferror(d->root->f)) + return EIO; + i = 0; + while (eol == 0 && i < r) { + if (buf[i] != '\r' && buf[i] != '\n') { + if (!ignore_whitespace + || !isspace((unsigned char)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 EIO; + 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((unsigned char)*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/lib/diff_debug.h b/lib/diff_debug.h new file mode 100644 index 000000000000..4b7ec8090638 --- /dev/null +++ b/lib/diff_debug.h @@ -0,0 +1,226 @@ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#define DEBUG 0 + +#if DEBUG +#include <stdio.h> +#include <unistd.h> +#define print(args...) fprintf(stderr, ##args) +#define debug print +#define debug_dump dump +#define debug_dump_atom dump_atom +#define debug_dump_atoms dump_atoms + +static inline void +print_atom_byte(unsigned char c) { + if (c == '\r') + print("\\r"); + else if (c == '\n') + print("\\n"); + else if ((c < 32 || c >= 127) && (c != '\t')) + print("\\x%02x", c); + else + print("%c", c); +} + +static inline void +dump_atom(const struct diff_data *left, const struct diff_data *right, + const struct diff_atom *atom) +{ + if (!atom) { + print("NULL atom\n"); + return; + } + if (left) + print(" %3u '", diff_atom_root_idx(left, atom)); + + if (atom->at == NULL) { + off_t remain = atom->len; + if (fseek(atom->root->f, atom->pos, SEEK_SET) == -1) + abort(); /* cannot return error */ + while (remain > 0) { + char buf[16]; + size_t r; + int i; + r = fread(buf, 1, MIN(remain, sizeof(buf)), + atom->root->f); + if (r == 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/lib/diff_internal.h b/lib/diff_internal.h new file mode 100644 index 000000000000..46bbadf3cb64 --- /dev/null +++ b/lib/diff_internal.h @@ -0,0 +1,157 @@ +/* Generic infrastructure to implement various diff algorithms. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#ifndef MAX +#define MAX(A,B) ((A)>(B)?(A):(B)) +#endif +#ifndef MIN +#define MIN(A,B) ((A)<(B)?(A):(B)) +#endif + +static inline bool +diff_range_empty(const struct diff_range *r) +{ + return r->start == r->end; +} + +static inline bool +diff_ranges_touch(const struct diff_range *a, const struct diff_range *b) +{ + return (a->end >= b->start) && (a->start <= b->end); +} + +static inline void +diff_ranges_merge(struct diff_range *a, const struct diff_range *b) +{ + *a = (struct diff_range){ + .start = MIN(a->start, b->start), + .end = MAX(a->end, b->end), + }; +} + +static inline int +diff_range_len(const struct diff_range *r) +{ + if (!r) + return 0; + return r->end - r->start; +} + +/* 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 + +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); + +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/lib/diff_main.c b/lib/diff_main.c new file mode 100644 index 000000000000..e64b1320e553 --- /dev/null +++ b/lib/diff_main.c @@ -0,0 +1,663 @@ +/* Generic infrastructure to implement various diff algorithms (implementation). */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + + +#include <sys/queue.h> +#include <ctype.h> +#include <errno.h> +#include <stdint.h> +#include <stdlib.h> +#include <stdbool.h> +#include <stdio.h> +#include <string.h> +#include <limits.h> +#include <unistd.h> + +#include <assert.h> + +#include <arraylist.h> +#include <diff_main.h> + +#include "diff_internal.h" +#include "diff_debug.h" + +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; +} + +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 EIO; + 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((unsigned char)cl) && il < left_len) { + il++; + continue; + } + if (isspace((unsigned char)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((unsigned char)cl)) + return 1; + } + while (ir < right_len) { + unsigned char cr = right[ir++]; + if (!isspace((unsigned char)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_result_contains_printable_chunks(struct diff_result *result) +{ + struct diff_chunk *c; + enum diff_chunk_type t; + int i; + + for (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/lib/diff_myers.c b/lib/diff_myers.c new file mode 100644 index 000000000000..c886d1a28586 --- /dev/null +++ b/lib/diff_myers.c @@ -0,0 +1,1425 @@ +/* Myers diff algorithm implementation, invented by Eugene W. Myers [1]. + * Implementations of both the Myers Divide Et Impera (using linear space) + * and the canonical Myers algorithm (using quadratic space). */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <stdbool.h> +#include <stdint.h> +#include <stdlib.h> +#include <string.h> +#include <stdio.h> +#include <errno.h> + +#include <arraylist.h> +#include <diff_main.h> + +#include "diff_internal.h" +#include "diff_debug.h" + +/* Myers' diff algorithm [1] is nicely explained in [2]. + * [1] http://www.xmailserver.org/diff2.pdf + * [2] https://blog.jcoglan.com/2017/02/12/the-myers-diff-algorithm-part-1/ ff. + * + * Myers approaches finding the smallest diff as a graph problem. + * The crux is that the original algorithm requires quadratic amount of memory: + * both sides' lengths added, and that squared. So if we're diffing lines of + * text, two files with 1000 lines each would blow up to a matrix of about + * 2000 * 2000 ints of state, about 16 Mb of RAM to figure out 2 kb of text. + * The solution is using Myers' "divide and conquer" extension algorithm, which + * does the original traversal from both ends of the files to reach a middle + * where these "snakes" touch, hence does not need to backtrace the traversal, + * and so gets away with only keeping a single column of that huge state matrix + * in memory. + */ + +struct diff_box { + unsigned int left_start; + unsigned int left_end; + unsigned int right_start; + unsigned int right_end; +}; + +/* If the two contents of a file are A B C D E and X B C Y, + * the Myers diff graph looks like: + * + * k0 k1 + * \ \ + * k-1 0 1 2 3 4 5 + * \ A B C D E + * 0 o-o-o-o-o-o + * X | | | | | | + * 1 o-o-o-o-o-o + * B | |\| | | | + * 2 o-o-o-o-o-o + * C | | |\| | | + * 3 o-o-o-o-o-o + * Y | | | | | |\ + * 4 o-o-o-o-o-o c1 + * \ \ + * c-1 c0 + * + * Moving right means delete an atom from the left-hand-side, + * Moving down means add an atom from the right-hand-side. + * Diagonals indicate identical atoms on both sides, the challenge is to use as + * many diagonals as possible. + * + * The original Myers algorithm walks all the way from the top left to the + * bottom right, remembers all steps, and then backtraces to find the shortest + * path. However, that requires keeping the entire graph in memory, which needs + * quadratic space. + * + * Myers adds a variant that uses linear space -- note, not linear time, only + * linear space: walk forward and backward, find a meeting point in the middle, + * and recurse on the two separate sections. This is called "divide and + * conquer". + * + * d: the step number, starting with 0, a.k.a. the distance from the starting + * point. + * k: relative index in the state array for the forward scan, indicating on + * which diagonal through the diff graph we currently are. + * c: relative index in the state array for the backward scan, indicating the + * diagonal number from the bottom up. + * + * The "divide and conquer" traversal through the Myers graph looks like this: + * + * | d= 0 1 2 3 2 1 0 + * ----+-------------------------------------------- + * k= | c= + * 4 | 3 + * | + * 3 | 3,0 5,2 2 + * | / \ + * 2 | 2,0 5,3 1 + * | / \ + * 1 | 1,0 4,3 >= 4,3 5,4<-- 0 + * | / / \ / + * 0 | -->0,0 3,3 4,4 -1 + * | \ / / + * -1 | 0,1 1,2 3,4 -2 + * | \ / + * -2 | 0,2 -3 + * | \ + * | 0,3 + * | forward-> <-backward + * + * x,y pairs here are the coordinates in the Myers graph: + * x = atom index in left-side source, y = atom index in the right-side source. + * + * Only one forward column and one backward column are kept in mem, each need at + * most left.len + 1 + right.len items. Note that each d step occupies either + * the even or the odd items of a column: if e.g. the previous column is in the + * odd items, the next column is formed in the even items, without overwriting + * the previous column's results. + * + * Also note that from the diagonal index k and the x coordinate, the y + * coordinate can be derived: + * y = x - k + * Hence the state array only needs to keep the x coordinate, i.e. the position + * in the left-hand file, and the y coordinate, i.e. position in the right-hand + * file, is derived from the index in the state array. + * + * The two traces meet at 4,3, the first step (here found in the forward + * traversal) where a forward position is on or past a backward traced position + * on the same diagonal. + * + * This divides the problem space into: + * + * 0 1 2 3 4 5 + * A B C D E + * 0 o-o-o-o-o + * X | | | | | + * 1 o-o-o-o-o + * B | |\| | | + * 2 o-o-o-o-o + * C | | |\| | + * 3 o-o-o-o-*-o *: forward and backward meet here + * Y | | + * 4 o-o + * + * Doing the same on each section lead to: + * + * 0 1 2 3 4 5 + * A B C D E + * 0 o-o + * X | | + * 1 o-b b: backward d=1 first reaches here (sliding up the snake) + * B \ f: then forward d=2 reaches here (sliding down the snake) + * 2 o As result, the box from b to f is found to be identical; + * C \ leaving a top box from 0,0 to 1,1 and a bottom trivial + * 3 f-o tail 3,3 to 4,3. + * + * 3 o-* + * Y | + * 4 o *: forward and backward meet here + * + * and solving the last top left box gives: + * + * 0 1 2 3 4 5 + * A B C D E -A + * 0 o-o +X + * X | B + * 1 o C + * B \ -D + * 2 o -E + * C \ +Y + * 3 o-o-o + * Y | + * 4 o + * + */ + +#define xk_to_y(X, K) ((X) - (K)) +#define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA)) +#define k_to_c(K, DELTA) ((K) + (DELTA)) +#define c_to_k(C, DELTA) ((C) - (DELTA)) + +/* Do one forwards step in the "divide and conquer" graph traversal. + * left: the left side to diff. + * right: the right side to diff against. + * kd_forward: the traversal state for forwards traversal, modified by this + * function. + * This is carried over between invocations with increasing d. + * kd_forward points at the center of the state array, allowing + * negative indexes. + * kd_backward: the traversal state for backwards traversal, to find a meeting + * point. + * Since forwards is done first, kd_backward will be valid for d - + * 1, not d. + * kd_backward points at the center of the state array, allowing + * negative indexes. + * d: Step or distance counter, indicating for what value of d the kd_forward + * should be populated. + * For d == 0, kd_forward[0] is initialized, i.e. the first invocation should + * be for d == 0. + * meeting_snake: resulting meeting point, if any. + * Return true when a meeting point has been identified. + */ +static int +diff_divide_myers_forward(bool *found_midpoint, + struct diff_data *left, struct diff_data *right, + int *kd_forward, int *kd_backward, int d, + struct diff_box *meeting_snake) +{ + int delta = (int)right->atoms.len - (int)left->atoms.len; + int k; + int x; + int prev_x; + int prev_y; + int x_before_slide; + *found_midpoint = false; + + for (k = d; k >= -d; k -= 2) { + if (k < -(int)right->atoms.len || k > (int)left->atoms.len) { + /* This diagonal is completely outside of the Myers + * graph, don't calculate it. */ + if (k < 0) { + /* We are traversing negatively, and already + * below the entire graph, nothing will come of + * this. */ + debug(" break\n"); + break; + } + debug(" continue\n"); + continue; + } + if (d == 0) { + /* This is the initializing step. There is no prev_k + * yet, get the initial x from the top left of the Myers + * graph. */ + x = 0; + prev_x = x; + prev_y = xk_to_y(x, k); + } + /* Favoring "-" lines first means favoring moving rightwards in + * the Myers graph. + * For this, all k should derive from k - 1, only the bottom + * most k derive from k + 1: + * + * | d= 0 1 2 + * ----+---------------- + * k= | + * 2 | 2,0 <-- from prev_k = 2 - 1 = 1 + * | / + * 1 | 1,0 + * | / + * 0 | -->0,0 3,3 + * | \\ / + * -1 | 0,1 <-- bottom most for d=1 from + * | \\ prev_k = -1 + 1 = 0 + * -2 | 0,2 <-- bottom most for d=2 from + * prev_k = -2 + 1 = -1 + * + * Except when a k + 1 from a previous run already means a + * further advancement in the graph. + * If k == d, there is no k + 1 and k - 1 is the only option. + * If k < d, use k + 1 in case that yields a larger x. Also use + * k + 1 if k - 1 is outside the graph. + */ + else if (k > -d + && (k == d + || (k - 1 >= -(int)right->atoms.len + && kd_forward[k - 1] >= kd_forward[k + 1]))) { + /* Advance from k - 1. + * From position prev_k, step to the right in the Myers + * graph: x += 1. + */ + int prev_k = k - 1; + prev_x = kd_forward[prev_k]; + prev_y = xk_to_y(prev_x, prev_k); + x = prev_x + 1; + } else { + /* The bottom most one. + * From position prev_k, step to the bottom in the Myers + * graph: y += 1. + * Incrementing y is achieved by decrementing k while + * keeping the same x. + * (since we're deriving y from y = x - k). + */ + int prev_k = k + 1; + prev_x = kd_forward[prev_k]; + prev_y = xk_to_y(prev_x, prev_k); + x = prev_x; + } + + x_before_slide = x; + /* Slide down any snake that we might find here. */ + while (x < left->atoms.len && xk_to_y(x, k) < right->atoms.len) { + bool same; + int r = diff_atom_same(&same, + &left->atoms.head[x], + &right->atoms.head[ + xk_to_y(x, k)]); + if (r) + return r; + if (!same) + break; + x++; + } + kd_forward[k] = x; +#if 0 + if (x_before_slide != x) { + debug(" down %d similar lines\n", x - x_before_slide); + } + +#if DEBUG + { + int fi; + for (fi = d; fi >= k; fi--) { + debug("kd_forward[%d] = (%d, %d)\n", fi, + kd_forward[fi], kd_forward[fi] - fi); + } + } +#endif +#endif + + if (x < 0 || x > left->atoms.len + || xk_to_y(x, k) < 0 || xk_to_y(x, k) > right->atoms.len) + continue; + + /* Figured out a new forwards traversal, see if this has gone + * onto or even past a preceding backwards traversal. + * + * If the delta in length is odd, then d and backwards_d hit the + * same state indexes: + * | d= 0 1 2 1 0 + * ----+---------------- ---------------- + * k= | c= + * 4 | 3 + * | + * 3 | 2 + * | same + * 2 | 2,0====5,3 1 + * | / \ + * 1 | 1,0 5,4<-- 0 + * | / / + * 0 | -->0,0 3,3====4,4 -1 + * | \ / + * -1 | 0,1 -2 + * | \ + * -2 | 0,2 -3 + * | + * + * If the delta is even, they end up off-by-one, i.e. on + * different diagonals: + * + * | d= 0 1 2 1 0 + * ----+---------------- ---------------- + * | c= + * 3 | 3 + * | + * 2 | 2,0 off 2 + * | / \\ + * 1 | 1,0 4,3 1 + * | / // \ + * 0 | -->0,0 3,3 4,4<-- 0 + * | \ / / + * -1 | 0,1 3,4 -1 + * | \ // + * -2 | 0,2 -2 + * | + * + * So in the forward path, we can only match up diagonals when + * the delta is odd. + */ + if ((delta & 1) == 0) + continue; + /* Forwards is done first, so the backwards one was still at + * d - 1. Can't do this for d == 0. */ + int backwards_d = d - 1; + if (backwards_d < 0) + continue; + + /* If both sides have the same length, forward and backward + * start on the same diagonal, meaning the backwards state index + * c == k. + * As soon as the lengths are not the same, the backwards + * traversal starts on a different diagonal, and c = k shifted + * by the difference in length. + */ + int c = k_to_c(k, delta); + + /* When the file sizes are very different, the traversal trees + * start on far distant diagonals. + * They don't necessarily meet straight on. See whether this + * forward value is on a diagonal that is also valid in + * kd_backward[], and match them if so. */ + if (c >= -backwards_d && c <= backwards_d) { + /* Current k is on a diagonal that exists in + * kd_backward[]. If the two x positions have met or + * passed (forward walked onto or past backward), then + * we've found a midpoint / a mid-box. + * + * When forwards and backwards traversals meet, the + * endpoints of the mid-snake are not the two points in + * kd_forward and kd_backward, but rather the section + * that was slid (if any) of the current + * forward/backward traversal only. + * + * For example: + * + * o + * \ + * o + * \ + * o + * \ + * o + * \ + * X o o + * | | | + * o-o-o o + * \| + * M + * \ + * o + * \ + * A o + * | | + * o-o-o + * + * The forward traversal reached M from the top and slid + * downwards to A. The backward traversal already + * reached X, which is not a straight line from M + * anymore, so picking a mid-snake from M to X would + * yield a mistake. + * + * The correct mid-snake is between M and A. M is where + * the forward traversal hit the diagonal that the + * backward traversal has already passed, and A is what + * it reaches when sliding down identical lines. + */ + int backward_x = kd_backward[c]; + if (x >= backward_x) { + if (x_before_slide != x) { + /* met after sliding up a mid-snake */ + *meeting_snake = (struct diff_box){ + .left_start = x_before_slide, + .left_end = x, + .right_start = xc_to_y(x_before_slide, + c, delta), + .right_end = xk_to_y(x, k), + }; + } else { + /* met after a side step, non-identical + * line. Mark that as box divider + * instead. This makes sure that + * myers_divide never returns the same + * box that came as input, avoiding + * "infinite" looping. */ + *meeting_snake = (struct diff_box){ + .left_start = prev_x, + .left_end = x, + .right_start = prev_y, + .right_end = xk_to_y(x, k), + }; + } + debug("HIT x=(%u,%u) - y=(%u,%u)\n", + meeting_snake->left_start, + meeting_snake->right_start, + meeting_snake->left_end, + meeting_snake->right_end); + debug_dump_myers_graph(left, right, NULL, + kd_forward, d, + kd_backward, d-1); + *found_midpoint = true; + return 0; + } + } + } + + return 0; +} + +/* Do one backwards step in the "divide and conquer" graph traversal. + * left: the left side to diff. + * right: the right side to diff against. + * kd_forward: the traversal state for forwards traversal, to find a meeting + * point. + * Since forwards is done first, after this, both kd_forward and + * kd_backward will be valid for d. + * kd_forward points at the center of the state array, allowing + * negative indexes. + * kd_backward: the traversal state for backwards traversal, to find a meeting + * point. + * This is carried over between invocations with increasing d. + * kd_backward points at the center of the state array, allowing + * negative indexes. + * d: Step or distance counter, indicating for what value of d the kd_backward + * should be populated. + * Before the first invocation, kd_backward[0] shall point at the bottom + * right of the Myers graph (left.len, right.len). + * The first invocation will be for d == 1. + * meeting_snake: resulting meeting point, if any. + * Return true when a meeting point has been identified. + */ +static int +diff_divide_myers_backward(bool *found_midpoint, + struct diff_data *left, struct diff_data *right, + int *kd_forward, int *kd_backward, int d, + struct diff_box *meeting_snake) +{ + int delta = (int)right->atoms.len - (int)left->atoms.len; + int c; + int x; + int prev_x; + int prev_y; + int x_before_slide; + + *found_midpoint = false; + + for (c = d; c >= -d; c -= 2) { + if (c < -(int)left->atoms.len || c > (int)right->atoms.len) { + /* This diagonal is completely outside of the Myers + * graph, don't calculate it. */ + if (c < 0) { + /* We are traversing negatively, and already + * below the entire graph, nothing will come of + * this. */ + break; + } + continue; + } + if (d == 0) { + /* This is the initializing step. There is no prev_c + * yet, get the initial x from the bottom right of the + * Myers graph. */ + x = left->atoms.len; + prev_x = x; + prev_y = xc_to_y(x, c, delta); + } + /* Favoring "-" lines first means favoring moving rightwards in + * the Myers graph. + * For this, all c should derive from c - 1, only the bottom + * most c derive from c + 1: + * + * 2 1 0 + * --------------------------------------------------- + * c= + * 3 + * + * from prev_c = c - 1 --> 5,2 2 + * \ + * 5,3 1 + * \ + * 4,3 5,4<-- 0 + * \ / + * bottom most for d=1 from c + 1 --> 4,4 -1 + * / + * bottom most for d=2 --> 3,4 -2 + * + * Except when a c + 1 from a previous run already means a + * further advancement in the graph. + * If c == d, there is no c + 1 and c - 1 is the only option. + * If c < d, use c + 1 in case that yields a larger x. + * Also use c + 1 if c - 1 is outside the graph. + */ + else if (c > -d && (c == d + || (c - 1 >= -(int)right->atoms.len + && kd_backward[c - 1] <= kd_backward[c + 1]))) { + /* A top one. + * From position prev_c, step upwards in the Myers + * graph: y -= 1. + * Decrementing y is achieved by incrementing c while + * keeping the same x. (since we're deriving y from + * y = x - c + delta). + */ + int prev_c = c - 1; + prev_x = kd_backward[prev_c]; + prev_y = xc_to_y(prev_x, prev_c, delta); + x = prev_x; + } else { + /* The bottom most one. + * From position prev_c, step to the left in the Myers + * graph: x -= 1. + */ + int prev_c = c + 1; + prev_x = kd_backward[prev_c]; + prev_y = xc_to_y(prev_x, prev_c, delta); + x = prev_x - 1; + } + + /* Slide up any snake that we might find here (sections of + * identical lines on both sides). */ +#if 0 + debug("c=%d x-1=%d Yb-1=%d-1=%d\n", c, x-1, xc_to_y(x, c, + delta), + xc_to_y(x, c, delta)-1); + if (x > 0) { + debug(" l="); + debug_dump_atom(left, right, &left->atoms.head[x-1]); + } + if (xc_to_y(x, c, delta) > 0) { + debug(" r="); + debug_dump_atom(right, left, + &right->atoms.head[xc_to_y(x, c, delta)-1]); + } +#endif + x_before_slide = x; + while (x > 0 && xc_to_y(x, c, delta) > 0) { + bool same; + int r = diff_atom_same(&same, + &left->atoms.head[x-1], + &right->atoms.head[ + xc_to_y(x, c, delta)-1]); + if (r) + return r; + if (!same) + break; + x--; + } + kd_backward[c] = x; +#if 0 + if (x_before_slide != x) { + debug(" up %d similar lines\n", x_before_slide - x); + } + + if (DEBUG) { + int fi; + for (fi = d; fi >= c; fi--) { + debug("kd_backward[%d] = (%d, %d)\n", + fi, + kd_backward[fi], + kd_backward[fi] - fi + delta); + } + } +#endif + + if (x < 0 || x > left->atoms.len + || xc_to_y(x, c, delta) < 0 + || xc_to_y(x, c, delta) > right->atoms.len) + continue; + + /* Figured out a new backwards traversal, see if this has gone + * onto or even past a preceding forwards traversal. + * + * If the delta in length is even, then d and backwards_d hit + * the same state indexes -- note how this is different from in + * the forwards traversal, because now both d are the same: + * + * | d= 0 1 2 2 1 0 + * ----+---------------- -------------------- + * k= | c= + * 4 | + * | + * 3 | 3 + * | same + * 2 | 2,0====5,2 2 + * | / \ + * 1 | 1,0 5,3 1 + * | / / \ + * 0 | -->0,0 3,3====4,3 5,4<-- 0 + * | \ / / + * -1 | 0,1 4,4 -1 + * | \ + * -2 | 0,2 -2 + * | + * -3 + * If the delta is odd, they end up off-by-one, i.e. on + * different diagonals. + * So in the backward path, we can only match up diagonals when + * the delta is even. + */ + if ((delta & 1) != 0) + continue; + /* Forwards was done first, now both d are the same. */ + int forwards_d = d; + + /* As soon as the lengths are not the same, the + * backwards traversal starts on a different diagonal, + * and c = k shifted by the difference in length. + */ + int k = c_to_k(c, delta); + + /* When the file sizes are very different, the traversal trees + * start on far distant diagonals. + * They don't necessarily meet straight on. See whether this + * backward value is also on a valid diagonal in kd_forward[], + * and match them if so. */ + if (k >= -forwards_d && k <= forwards_d) { + /* Current c is on a diagonal that exists in + * kd_forward[]. If the two x positions have met or + * passed (backward walked onto or past forward), then + * we've found a midpoint / a mid-box. + * + * When forwards and backwards traversals meet, the + * endpoints of the mid-snake are not the two points in + * kd_forward and kd_backward, but rather the section + * that was slid (if any) of the current + * forward/backward traversal only. + * + * For example: + * + * o-o-o + * | | + * o A + * | \ + * o o + * \ + * M + * |\ + * o o-o-o + * | | | + * o o X + * \ + * o + * \ + * o + * \ + * o + * + * The backward traversal reached M from the bottom and + * slid upwards. The forward traversal already reached + * X, which is not a straight line from M anymore, so + * picking a mid-snake from M to X would yield a + * mistake. + * + * The correct mid-snake is between M and A. M is where + * the backward traversal hit the diagonal that the + * forwards traversal has already passed, and A is what + * it reaches when sliding up identical lines. + */ + + int forward_x = kd_forward[k]; + if (forward_x >= x) { + if (x_before_slide != x) { + /* met after sliding down a mid-snake */ + *meeting_snake = (struct diff_box){ + .left_start = x, + .left_end = x_before_slide, + .right_start = xc_to_y(x, c, delta), + .right_end = xk_to_y(x_before_slide, k), + }; + } else { + /* met after a side step, non-identical + * line. Mark that as box divider + * instead. This makes sure that + * myers_divide never returns the same + * box that came as input, avoiding + * "infinite" looping. */ + *meeting_snake = (struct diff_box){ + .left_start = x, + .left_end = prev_x, + .right_start = xc_to_y(x, c, delta), + .right_end = prev_y, + }; + } + debug("HIT x=%u,%u - y=%u,%u\n", + meeting_snake->left_start, + meeting_snake->right_start, + meeting_snake->left_end, + meeting_snake->right_end); + debug_dump_myers_graph(left, right, NULL, + kd_forward, d, + kd_backward, d); + *found_midpoint = true; + return 0; + } + } + } + return 0; +} + +/* Integer square root approximation */ +static int +shift_sqrt(int val) +{ + int i; + for (i = 1; val > 0; val >>= 2) + i <<= 1; + return i; +} + +#define DIFF_EFFORT_MIN 1024 + +/* Myers "Divide et Impera": tracing forwards from the start and backwards from + * the end to find a midpoint that divides the problem into smaller chunks. + * Requires only linear amounts of memory. */ +int +diff_algo_myers_divide(const struct diff_algo_config *algo_config, + struct diff_state *state) +{ + int rc = ENOMEM; + struct diff_data *left = &state->left; + struct diff_data *right = &state->right; + int *kd_buf; + + debug("\n** %s\n", __func__); + debug("left:\n"); + debug_dump(left); + debug("right:\n"); + debug_dump(right); + + /* Allocate two columns of a Myers graph, one for the forward and one + * for the backward traversal. */ + unsigned int max = left->atoms.len + right->atoms.len; + size_t kd_len = max + 1; + size_t kd_buf_size = kd_len << 1; + + if (state->kd_buf_size < kd_buf_size) { + kd_buf = reallocarray(state->kd_buf, kd_buf_size, + sizeof(int)); + if (!kd_buf) + return ENOMEM; + state->kd_buf = kd_buf; + state->kd_buf_size = kd_buf_size; + } else + kd_buf = state->kd_buf; + int i; + for (i = 0; i < kd_buf_size; i++) + kd_buf[i] = -1; + int *kd_forward = kd_buf; + int *kd_backward = kd_buf + kd_len; + int max_effort = shift_sqrt(max/2); + + if (max_effort < DIFF_EFFORT_MIN) + max_effort = DIFF_EFFORT_MIN; + + /* The 'k' axis in Myers spans positive and negative indexes, so point + * the kd to the middle. + * It is then possible to index from -max/2 .. max/2. */ + kd_forward += max/2; + kd_backward += max/2; + + int d; + struct diff_box mid_snake = {}; + bool found_midpoint = false; + for (d = 0; d <= (max/2); d++) { + int r; + r = diff_divide_myers_forward(&found_midpoint, left, right, + kd_forward, kd_backward, d, + &mid_snake); + if (r) + return r; + if (found_midpoint) + break; + r = diff_divide_myers_backward(&found_midpoint, left, right, + kd_forward, kd_backward, d, + &mid_snake); + if (r) + return r; + if (found_midpoint) + break; + + /* Limit the effort spent looking for a mid snake. If files have + * very few lines in common, the effort spent to find nice mid + * snakes is just not worth it, the diff result will still be + * essentially minus everything on the left, plus everything on + * the right, with a few useless matches here and there. */ + if (d > max_effort) { + /* pick the furthest reaching point from + * kd_forward and kd_backward, and use that as a + * midpoint, to not step into another diff algo + * recursion with unchanged box. */ + int delta = (int)right->atoms.len - (int)left->atoms.len; + int x = 0; + int y; + int i; + int best_forward_i = 0; + int best_forward_distance = 0; + int best_backward_i = 0; + int best_backward_distance = 0; + int distance; + int best_forward_x; + int best_forward_y; + int best_backward_x; + int best_backward_y; + + debug("~~~ HIT d = %d > max_effort = %d\n", d, max_effort); + debug_dump_myers_graph(left, right, NULL, + kd_forward, d, + kd_backward, d); + + for (i = d; i >= -d; i -= 2) { + if (i >= -(int)right->atoms.len && i <= (int)left->atoms.len) { + x = kd_forward[i]; + y = xk_to_y(x, i); + distance = x + y; + if (distance > best_forward_distance) { + best_forward_distance = distance; + best_forward_i = i; + } + } + + if (i >= -(int)left->atoms.len && i <= (int)right->atoms.len) { + x = kd_backward[i]; + y = xc_to_y(x, i, delta); + distance = (right->atoms.len - x) + + (left->atoms.len - y); + if (distance >= best_backward_distance) { + best_backward_distance = distance; + best_backward_i = i; + } + } + } + + /* The myers-divide didn't meet in the middle. We just + * figured out the places where the forward path + * advanced the most, and the backward path advanced the + * most. Just divide at whichever one of those two is better. + * + * o-o + * | + * o + * \ + * o + * \ + * F <-- cut here + * + * + * + * or here --> B + * \ + * o + * \ + * o + * | + * o-o + */ + best_forward_x = kd_forward[best_forward_i]; + best_forward_y = xk_to_y(best_forward_x, best_forward_i); + best_backward_x = kd_backward[best_backward_i]; + best_backward_y = xc_to_y(best_backward_x, best_backward_i, delta); + + if (best_forward_distance >= best_backward_distance) { + x = best_forward_x; + y = best_forward_y; + } else { + x = best_backward_x; + y = best_backward_y; + } + + debug("max_effort cut at x=%d y=%d\n", x, y); + if (x < 0 || y < 0 + || x > left->atoms.len || y > right->atoms.len) + break; + + found_midpoint = true; + mid_snake = (struct diff_box){ + .left_start = x, + .left_end = x, + .right_start = y, + .right_end = y, + }; + break; + } + } + + if (!found_midpoint) { + /* Divide and conquer failed to find a meeting point. Use the + * fallback_algo defined in the algo_config (leave this to the + * caller). This is just paranoia/sanity, we normally should + * always find a midpoint. + */ + debug(" no midpoint \n"); + rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK; + goto return_rc; + } else { + debug(" mid snake L: %u to %u of %u R: %u to %u of %u\n", + mid_snake.left_start, mid_snake.left_end, left->atoms.len, + mid_snake.right_start, mid_snake.right_end, + right->atoms.len); + + /* Section before the mid-snake. */ + debug("Section before the mid-snake\n"); + + struct diff_atom *left_atom = &left->atoms.head[0]; + unsigned int left_section_len = mid_snake.left_start; + struct diff_atom *right_atom = &right->atoms.head[0]; + unsigned int right_section_len = mid_snake.right_start; + + if (left_section_len && right_section_len) { + /* Record an unsolved chunk, the caller will apply + * inner_algo() on this chunk. */ + if (!diff_state_add_chunk(state, false, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto return_rc; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto return_rc; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, + right_section_len)) + goto return_rc; + } + /* else: left_section_len == 0 and right_section_len == 0, i.e. + * nothing before the mid-snake. */ + + if (mid_snake.left_end > mid_snake.left_start + || mid_snake.right_end > mid_snake.right_start) { + /* The midpoint is a section of identical data on both + * sides, or a certain differing line: that section + * immediately becomes a solved chunk. */ + debug("the mid-snake\n"); + if (!diff_state_add_chunk(state, true, + &left->atoms.head[mid_snake.left_start], + mid_snake.left_end - mid_snake.left_start, + &right->atoms.head[mid_snake.right_start], + mid_snake.right_end - mid_snake.right_start)) + goto return_rc; + } + + /* Section after the mid-snake. */ + debug("Section after the mid-snake\n"); + debug(" left_end %u right_end %u\n", + mid_snake.left_end, mid_snake.right_end); + debug(" left_count %u right_count %u\n", + left->atoms.len, right->atoms.len); + left_atom = &left->atoms.head[mid_snake.left_end]; + left_section_len = left->atoms.len - mid_snake.left_end; + right_atom = &right->atoms.head[mid_snake.right_end]; + right_section_len = right->atoms.len - mid_snake.right_end; + + if (left_section_len && right_section_len) { + /* Record an unsolved chunk, the caller will apply + * inner_algo() on this chunk. */ + if (!diff_state_add_chunk(state, false, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto return_rc; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto return_rc; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, + right_section_len)) + goto return_rc; + } + /* else: left_section_len == 0 and right_section_len == 0, i.e. + * nothing after the mid-snake. */ + } + + rc = DIFF_RC_OK; + +return_rc: + debug("** END %s\n", __func__); + return rc; +} + +/* Myers Diff tracing from the start all the way through to the end, requiring + * quadratic amounts of memory. This can fail if the required space surpasses + * algo_config->permitted_state_size. */ +int +diff_algo_myers(const struct diff_algo_config *algo_config, + struct diff_state *state) +{ + /* do a diff_divide_myers_forward() without a _backward(), so that it + * walks forward across the entire files to reach the end. Keep each + * run's state, and do a final backtrace. */ + int rc = ENOMEM; + struct diff_data *left = &state->left; + struct diff_data *right = &state->right; + int *kd_buf; + + debug("\n** %s\n", __func__); + debug("left:\n"); + debug_dump(left); + debug("right:\n"); + debug_dump(right); + debug_dump_myers_graph(left, right, NULL, NULL, 0, NULL, 0); + + /* Allocate two columns of a Myers graph, one for the forward and one + * for the backward traversal. */ + unsigned int max = left->atoms.len + right->atoms.len; + size_t kd_len = max + 1 + max; + size_t kd_buf_size = kd_len * kd_len; + size_t kd_state_size = kd_buf_size * sizeof(int); + debug("state size: %zu\n", kd_state_size); + if (kd_buf_size < kd_len /* overflow? */ + || (SIZE_MAX / kd_len ) < kd_len + || kd_state_size > algo_config->permitted_state_size) { + debug("state size %zu > permitted_state_size %zu, use fallback_algo\n", + kd_state_size, algo_config->permitted_state_size); + return DIFF_RC_USE_DIFF_ALGO_FALLBACK; + } + + if (state->kd_buf_size < kd_buf_size) { + kd_buf = reallocarray(state->kd_buf, kd_buf_size, + sizeof(int)); + if (!kd_buf) + return ENOMEM; + state->kd_buf = kd_buf; + state->kd_buf_size = kd_buf_size; + } else + kd_buf = state->kd_buf; + + int i; + for (i = 0; i < kd_buf_size; i++) + kd_buf[i] = -1; + + /* The 'k' axis in Myers spans positive and negative indexes, so point + * the kd to the middle. + * It is then possible to index from -max .. max. */ + int *kd_origin = kd_buf + max; + int *kd_column = kd_origin; + + int d; + int backtrack_d = -1; + int backtrack_k = 0; + int k; + int x, y; + for (d = 0; d <= max; d++, kd_column += kd_len) { + debug("-- %s d=%d\n", __func__, d); + + for (k = d; k >= -d; k -= 2) { + if (k < -(int)right->atoms.len + || k > (int)left->atoms.len) { + /* This diagonal is completely outside of the + * Myers graph, don't calculate it. */ + if (k < -(int)right->atoms.len) + debug(" %d k <" + " -(int)right->atoms.len %d\n", + k, -(int)right->atoms.len); + else + debug(" %d k > left->atoms.len %d\n", k, + left->atoms.len); + if (k < 0) { + /* We are traversing negatively, and + * already below the entire graph, + * nothing will come of this. */ + debug(" break\n"); + break; + } + debug(" continue\n"); + continue; + } + + if (d == 0) { + /* This is the initializing step. There is no + * prev_k yet, get the initial x from the top + * left of the Myers graph. */ + x = 0; + } else { + int *kd_prev_column = kd_column - kd_len; + + /* Favoring "-" lines first means favoring + * moving rightwards in the Myers graph. + * For this, all k should derive from k - 1, + * only the bottom most k derive from k + 1: + * + * | d= 0 1 2 + * ----+---------------- + * k= | + * 2 | 2,0 <-- from + * | / prev_k = 2 - 1 = 1 + * 1 | 1,0 + * | / + * 0 | -->0,0 3,3 + * | \\ / + * -1 | 0,1 <-- bottom most for d=1 + * | \\ from prev_k = -1+1 = 0 + * -2 | 0,2 <-- bottom most for + * d=2 from + * prev_k = -2+1 = -1 + * + * Except when a k + 1 from a previous run + * already means a further advancement in the + * graph. + * If k == d, there is no k + 1 and k - 1 is the + * only option. + * If k < d, use k + 1 in case that yields a + * larger x. Also use k + 1 if k - 1 is outside + * the graph. + */ + if (k > -d + && (k == d + || (k - 1 >= -(int)right->atoms.len + && kd_prev_column[k - 1] + >= kd_prev_column[k + 1]))) { + /* Advance from k - 1. + * From position prev_k, step to the + * right in the Myers graph: x += 1. + */ + int prev_k = k - 1; + int prev_x = kd_prev_column[prev_k]; + x = prev_x + 1; + } else { + /* The bottom most one. + * From position prev_k, step to the + * bottom in the Myers graph: y += 1. + * Incrementing y is achieved by + * decrementing k while keeping the same + * x. (since we're deriving y from y = + * x - k). + */ + int prev_k = k + 1; + int prev_x = kd_prev_column[prev_k]; + x = prev_x; + } + } + + /* Slide down any snake that we might find here. */ + while (x < left->atoms.len + && xk_to_y(x, k) < right->atoms.len) { + bool same; + int r = diff_atom_same(&same, + &left->atoms.head[x], + &right->atoms.head[ + xk_to_y(x, k)]); + if (r) + return r; + if (!same) + break; + x++; + } + kd_column[k] = x; + + if (x == left->atoms.len + && xk_to_y(x, k) == right->atoms.len) { + /* Found a path */ + backtrack_d = d; + backtrack_k = k; + debug("Reached the end at d = %d, k = %d\n", + backtrack_d, backtrack_k); + break; + } + } + + if (backtrack_d >= 0) + break; + } + + debug_dump_myers_graph(left, right, kd_origin, NULL, 0, NULL, 0); + + /* backtrack. A matrix spanning from start to end of the file is ready: + * + * | d= 0 1 2 3 4 + * ----+--------------------------------- + * k= | + * 3 | + * | + * 2 | 2,0 + * | / + * 1 | 1,0 4,3 + * | / / \ + * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, backtrack_k = 0 + * | \ / \ + * -1 | 0,1 3,4 + * | \ + * -2 | 0,2 + * | + * + * From (4,4) backwards, find the previous position that is the largest, and remember it. + * + */ + for (d = backtrack_d, k = backtrack_k; d >= 0; d--) { + x = kd_column[k]; + y = xk_to_y(x, k); + + /* When the best position is identified, remember it for that + * kd_column. + * That kd_column is no longer needed otherwise, so just + * re-purpose kd_column[0] = x and kd_column[1] = y, + * so that there is no need to allocate more memory. + */ + kd_column[0] = x; + kd_column[1] = y; + debug("Backtrack d=%d: xy=(%d, %d)\n", + d, kd_column[0], kd_column[1]); + + /* Don't access memory before kd_buf */ + if (d == 0) + break; + int *kd_prev_column = kd_column - kd_len; + + /* When y == 0, backtracking downwards (k-1) is the only way. + * When x == 0, backtracking upwards (k+1) is the only way. + * + * | d= 0 1 2 3 4 + * ----+--------------------------------- + * k= | + * 3 | + * | ..y == 0 + * 2 | 2,0 + * | / + * 1 | 1,0 4,3 + * | / / \ + * 0 | -->0,0 3,3 4,4 --> backtrack_d = 4, + * | \ / \ backtrack_k = 0 + * -1 | 0,1 3,4 + * | \ + * -2 | 0,2__ + * | x == 0 + */ + if (y == 0 + || (x > 0 + && kd_prev_column[k - 1] >= kd_prev_column[k + 1])) { + k = k - 1; + debug("prev k=k-1=%d x=%d y=%d\n", + k, kd_prev_column[k], + xk_to_y(kd_prev_column[k], k)); + } else { + k = k + 1; + debug("prev k=k+1=%d x=%d y=%d\n", + k, kd_prev_column[k], + xk_to_y(kd_prev_column[k], k)); + } + kd_column = kd_prev_column; + } + + /* Forwards again, this time recording the diff chunks. + * Definitely start from 0,0. kd_column[0] may actually point to the + * bottom of a snake starting at 0,0 */ + x = 0; + y = 0; + + kd_column = kd_origin; + for (d = 0; d <= backtrack_d; d++, kd_column += kd_len) { + int next_x = kd_column[0]; + int next_y = kd_column[1]; + debug("Forward track from xy(%d,%d) to xy(%d,%d)\n", + x, y, next_x, next_y); + + struct diff_atom *left_atom = &left->atoms.head[x]; + int left_section_len = next_x - x; + struct diff_atom *right_atom = &right->atoms.head[y]; + int right_section_len = next_y - y; + + rc = ENOMEM; + if (left_section_len && right_section_len) { + /* This must be a snake slide. + * Snake slides have a straight line leading into them + * (except when starting at (0,0)). Find out whether the + * lead-in is horizontal or vertical: + * + * left + * ----------> + * | + * r| o-o o + * i| \ | + * g| o o + * h| \ \ + * t| o o + * v + * + * If left_section_len > right_section_len, the lead-in + * is horizontal, meaning first remove one atom from the + * left before sliding down the snake. + * If right_section_len > left_section_len, the lead-in + * is vetical, so add one atom from the right before + * sliding down the snake. */ + if (left_section_len == right_section_len + 1) { + if (!diff_state_add_chunk(state, true, + left_atom, 1, + right_atom, 0)) + goto return_rc; + left_atom++; + left_section_len--; + } else if (right_section_len == left_section_len + 1) { + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, 1)) + goto return_rc; + right_atom++; + right_section_len--; + } else if (left_section_len != right_section_len) { + /* The numbers are making no sense. Should never + * happen. */ + rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK; + goto return_rc; + } + + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto return_rc; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto return_rc; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, + right_section_len)) + goto return_rc; + } + + x = next_x; + y = next_y; + } + + rc = DIFF_RC_OK; + +return_rc: + debug("** END %s rc=%d\n", __func__, rc); + return rc; +} diff --git a/lib/diff_output.c b/lib/diff_output.c new file mode 100644 index 000000000000..7ac63bb6c433 --- /dev/null +++ b/lib/diff_output.c @@ -0,0 +1,371 @@ +/* Common parts for printing diff output */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <ctype.h> +#include <errno.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <unistd.h> + +#include <arraylist.h> +#include <diff_main.h> +#include <diff_output.h> + +#include "diff_internal.h" + +static int +get_atom_byte(int *ch, struct diff_atom *atom, off_t off) +{ + off_t cur; + + if (atom->at != NULL) { + *ch = atom->at[off]; + return 0; + } + + cur = ftello(atom->root->f); + if (cur == -1) + return errno; + + if (cur != atom->pos + off && + fseeko(atom->root->f, atom->pos + off, SEEK_SET) == -1) + return errno; + + *ch = fgetc(atom->root->f); + if (*ch == EOF && ferror(atom->root->f)) + return errno; + + return 0; +} + +#define DIFF_OUTPUT_BUF_SIZE 512 + +int +diff_output_lines(struct diff_output_info *outinfo, FILE *dest, + const char *prefix, struct diff_atom *start_atom, + unsigned int count) +{ + struct diff_atom *atom; + off_t outoff = 0, *offp; + uint8_t *typep; + int rc; + + if (outinfo && outinfo->line_offsets.len > 0) { + unsigned int idx = outinfo->line_offsets.len - 1; + outoff = outinfo->line_offsets.head[idx]; + } + + foreach_diff_atom(atom, start_atom, count) { + off_t outlen = 0; + int i, ch, nbuf = 0; + unsigned int len = atom->len; + unsigned char buf[DIFF_OUTPUT_BUF_SIZE + 1 /* '\n' */]; + size_t n; + + n = strlcpy(buf, prefix, sizeof(buf)); + if (n >= DIFF_OUTPUT_BUF_SIZE) /* leave room for '\n' */ + return ENOBUFS; + nbuf += n; + + if (len) { + rc = get_atom_byte(&ch, atom, len - 1); + if (rc) + return rc; + if (ch == '\n') + len--; + } + + 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((unsigned char)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) +{ + 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/lib/diff_output_edscript.c b/lib/diff_output_edscript.c new file mode 100644 index 000000000000..42d4d5b39ef5 --- /dev/null +++ b/lib/diff_output_edscript.c @@ -0,0 +1,190 @@ +/* Produce ed(1) script output from a diff_result. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * Copyright (c) 2020 Stefan Sperling <stsp@openbsd.org> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <errno.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <stdbool.h> + +#include <arraylist.h> +#include <diff_main.h> +#include <diff_output.h> + +#include "diff_internal.h" + +static int +output_edscript_chunk(struct diff_output_info *outinfo, + FILE *dest, const struct diff_input_info *info, + const struct diff_result *result, + struct diff_chunk_context *cc) +{ + off_t outoff = 0, *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%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 */ + 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; + } + + 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; + + 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; + } + + 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); + continue; + } + + rc = output_edscript_chunk(outinfo, dest, info, result, &cc); + if (rc != DIFF_RC_OK) + return rc; + cc = next; + } + + if (!diff_chunk_context_empty(&cc)) + return output_edscript_chunk(outinfo, dest, info, result, &cc); + return DIFF_RC_OK; +} diff --git a/lib/diff_output_plain.c b/lib/diff_output_plain.c new file mode 100644 index 000000000000..7b0082bd1b84 --- /dev/null +++ b/lib/diff_output_plain.c @@ -0,0 +1,246 @@ +/* Output all lines of a diff_result. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <errno.h> +#include <stdint.h> +#include <stdio.h> +#include <stdbool.h> +#include <stdlib.h> + +#include <arraylist.h> +#include <diff_main.h> +#include <diff_output.h> + +#include "diff_internal.h" + +static int +output_plain_chunk(struct diff_output_info *outinfo, + FILE *dest, const struct diff_input_info *info, + const struct diff_result *result, + struct diff_chunk_context *cc, off_t *outoff, bool headers_only) +{ + 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; !headers_only && 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, int hunk_headers_only) +{ + 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, hunk_headers_only); + 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, hunk_headers_only); + return DIFF_RC_OK; +} diff --git a/lib/diff_output_unidiff.c b/lib/diff_output_unidiff.c new file mode 100644 index 000000000000..d480a022a9a7 --- /dev/null +++ b/lib/diff_output_unidiff.c @@ -0,0 +1,602 @@ +/* Produce a unidiff output from a diff_result. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <errno.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <assert.h> + +#include <arraylist.h> +#include <diff_main.h> +#include <diff_output.h> + +#include "diff_internal.h" +#include "diff_debug.h" + +off_t +diff_chunk_get_left_start_pos(const struct diff_chunk *c) +{ + return c->left_start->pos; +} + +off_t +diff_chunk_get_right_start_pos(const struct diff_chunk *c) +{ + return c->right_start->pos; +} + +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) +{ + 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); + 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; + + if (cc->left.end == result->left->atoms.len) { + 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); +} + +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); + 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); + diff_output_unidiff_state_free(state); + return DIFF_RC_OK; +} diff --git a/lib/diff_patience.c b/lib/diff_patience.c new file mode 100644 index 000000000000..a06df2c36c9d --- /dev/null +++ b/lib/diff_patience.c @@ -0,0 +1,647 @@ +/* Implementation of the Patience Diff algorithm invented by Bram Cohen: + * Divide a diff problem into smaller chunks by an LCS (Longest Common Sequence) + * of common-unique lines. */ +/* + * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de> + * + * Permission to use, copy, modify, and distribute this software for any + * purpose with or without fee is hereby granted, provided that the above + * copyright notice and this permission notice appear in all copies. + * + * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES + * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR + * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES + * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN + * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF + * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE. + */ + +#include <assert.h> +#include <errno.h> +#include <stdbool.h> +#include <stdint.h> +#include <stdio.h> +#include <stdlib.h> + +#include <arraylist.h> +#include <diff_main.h> + +#include "diff_internal.h" +#include "diff_debug.h" + +/* Algorithm to find unique lines: + * 0: stupidly iterate atoms + * 1: qsort + * 2: mergesort + */ +#define UNIQUE_STRATEGY 1 + +/* Per-atom state for the Patience Diff algorithm */ +struct atom_patience { +#if UNIQUE_STRATEGY == 0 + bool unique_here; +#endif + bool unique_in_both; + struct diff_atom *pos_in_other; + struct diff_atom *prev_stack; + struct diff_range identical_lines; +}; + +/* A diff_atom has a backpointer to the root diff_data. That points to the + * current diff_data, a possibly smaller section of the root. That current + * diff_data->algo_data is a pointer to an array of struct atom_patience. The + * atom's index in current diff_data gives the index in the atom_patience array. + */ +#define PATIENCE(ATOM) \ + (((struct atom_patience*)((ATOM)->root->current->algo_data))\ + [diff_atom_idx((ATOM)->root->current, ATOM)]) + +#if UNIQUE_STRATEGY == 0 + +/* Stupid iteration and comparison of all atoms */ +static int +diff_atoms_mark_unique(struct diff_data *d, unsigned int *unique_count) +{ + struct diff_atom *i; + unsigned int count = 0; + diff_data_foreach_atom(i, d) { + PATIENCE(i).unique_here = true; + PATIENCE(i).unique_in_both = true; + count++; + } + diff_data_foreach_atom(i, d) { + struct diff_atom *j; + + if (!PATIENCE(i).unique_here) + continue; + + diff_data_foreach_atom_from(i + 1, j, d) { + bool same; + int r = diff_atom_same(&same, i, j); + if (r) + return r; + if (!same) + continue; + if (PATIENCE(i).unique_here) { + PATIENCE(i).unique_here = false; + PATIENCE(i).unique_in_both = false; + count--; + } + PATIENCE(j).unique_here = false; + PATIENCE(j).unique_in_both = false; + count--; + } + } + if (unique_count) + *unique_count = count; + return 0; +} + +/* Mark those lines as PATIENCE(atom).unique_in_both = true that appear exactly + * once in each side. */ +static int +diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right, + unsigned int *unique_in_both_count) +{ + /* Derive the final unique_in_both count without needing an explicit + * iteration. So this is just some optimiziation to save one iteration + * in the end. */ + unsigned int unique_in_both; + int r; + + r = diff_atoms_mark_unique(left, &unique_in_both); + if (r) + return r; + r = diff_atoms_mark_unique(right, NULL); + if (r) + return r; + + debug("unique_in_both %u\n", unique_in_both); + + struct diff_atom *i; + diff_data_foreach_atom(i, left) { + if (!PATIENCE(i).unique_here) + continue; + struct diff_atom *j; + int found_in_b = 0; + diff_data_foreach_atom(j, right) { + bool same; + int r = diff_atom_same(&same, i, j); + if (r) + return r; + if (!same) + continue; + if (!PATIENCE(j).unique_here) { + found_in_b = 2; /* or more */ + break; + } else { + found_in_b = 1; + PATIENCE(j).pos_in_other = i; + PATIENCE(i).pos_in_other = j; + } + } + + if (found_in_b == 0 || found_in_b > 1) { + PATIENCE(i).unique_in_both = false; + unique_in_both--; + debug("unique_in_both %u (%d) ", unique_in_both, + found_in_b); + debug_dump_atom(left, NULL, i); + } + } + + /* Still need to unmark right[*]->patience.unique_in_both for atoms that + * don't exist in left */ + diff_data_foreach_atom(i, right) { + if (!PATIENCE(i).unique_here + || !PATIENCE(i).unique_in_both) + continue; + struct diff_atom *j; + bool found_in_a = false; + diff_data_foreach_atom(j, left) { + bool same; + int r; + if (!PATIENCE(j).unique_in_both) + continue; + r = diff_atom_same(&same, i, j); + if (r) + return r; + if (!same) + continue; + found_in_a = true; + break; + } + + if (!found_in_a) + PATIENCE(i).unique_in_both = false; + } + + if (unique_in_both_count) + *unique_in_both_count = unique_in_both; + return 0; +} + +#else /* UNIQUE_STRATEGY != 0 */ + +/* Use an optimized sorting algorithm (qsort, mergesort) to find unique lines */ + +static int diff_atoms_compar(const void *_a, const void *_b) +{ + const struct diff_atom *a = *(struct diff_atom**)_a; + const struct diff_atom *b = *(struct diff_atom**)_b; + int cmp; + int rc = 0; + + /* If there's been an error (e.g. I/O error) in a previous compar, we + * have no way to abort the sort but just report the rc and stop + * comparing. Make sure to catch errors on either side. If atoms are + * from more than one diff_data, make sure the error, if any, spreads + * to all of them, so we can cut short all future comparisons. */ + if (a->root->err) + rc = a->root->err; + if (b->root->err) + rc = b->root->err; + if (rc) { + a->root->err = rc; + b->root->err = rc; + /* just return 'equal' to not swap more positions */ + return 0; + } + + /* Sort by the simplistic hash */ + if (a->hash < b->hash) + return -1; + if (a->hash > b->hash) + return 1; + + /* If hashes are the same, the lines may still differ. Do a full cmp. */ + rc = diff_atom_cmp(&cmp, a, b); + + if (rc) { + /* Mark the I/O error so that the caller can find out about it. + * For the case atoms are from more than one diff_data, mark in + * both. */ + a->root->err = rc; + if (a->root != b->root) + b->root->err = rc; + return 0; + } + + return cmp; +} + +/* Sort an array of struct diff_atom* in-place. */ +static int diff_atoms_sort(struct diff_atom *atoms[], + size_t atoms_count) +{ +#if UNIQUE_STRATEGY == 1 + qsort(atoms, atoms_count, sizeof(struct diff_atom*), diff_atoms_compar); +#else + mergesort(atoms, atoms_count, sizeof(struct diff_atom*), + diff_atoms_compar); +#endif + return atoms[0]->root->err; +} + +static int +diff_atoms_mark_unique_in_both(struct diff_data *left, struct diff_data *right, + unsigned int *unique_in_both_count_p) +{ + struct diff_atom *a; + struct diff_atom *b; + struct diff_atom **all_atoms; + unsigned int len = 0; + unsigned int i; + unsigned int unique_in_both_count = 0; + int rc; + + all_atoms = calloc(left->atoms.len + right->atoms.len, + sizeof(struct diff_atom *)); + if (all_atoms == NULL) + return ENOMEM; + + left->err = 0; + right->err = 0; + left->root->err = 0; + right->root->err = 0; + diff_data_foreach_atom(a, left) { + all_atoms[len++] = a; + } + diff_data_foreach_atom(b, right) { + all_atoms[len++] = b; + } + + rc = diff_atoms_sort(all_atoms, len); + if (rc) + goto free_and_exit; + + /* Now we have a sorted array of atom pointers. All similar lines are + * adjacent. Walk through the array and mark those that are unique on + * each side, but exist once in both sources. */ + for (i = 0; i < len; i++) { + bool same; + unsigned int next_differing_i; + unsigned int last_identical_i; + unsigned int j; + unsigned int count_first_side = 1; + unsigned int count_other_side = 0; + a = all_atoms[i]; + debug("a: "); + debug_dump_atom(a->root, NULL, a); + + /* Do as few diff_atom_cmp() as possible: first walk forward + * only using the cheap hash as indicator for differing atoms; + * then walk backwards until hitting an identical atom. */ + for (next_differing_i = i + 1; next_differing_i < len; + next_differing_i++) { + b = all_atoms[next_differing_i]; + if (a->hash != b->hash) + break; + } + for (last_identical_i = next_differing_i - 1; + last_identical_i > i; + last_identical_i--) { + b = all_atoms[last_identical_i]; + rc = diff_atom_same(&same, a, b); + if (rc) + goto free_and_exit; + if (same) + break; + } + next_differing_i = last_identical_i + 1; + + for (j = i+1; j < next_differing_i; j++) { + b = all_atoms[j]; + /* A following atom is the same. See on which side the + * repetition counts. */ + if (a->root == b->root) + count_first_side ++; + else + count_other_side ++; + debug("b: "); + debug_dump_atom(b->root, NULL, b); + debug(" count_first_side=%d count_other_side=%d\n", + count_first_side, count_other_side); + } + + /* Counted a section of similar atoms, put the results back to + * the atoms. */ + if ((count_first_side == 1) + && (count_other_side == 1)) { + b = all_atoms[i+1]; + PATIENCE(a).unique_in_both = true; + PATIENCE(a).pos_in_other = b; + PATIENCE(b).unique_in_both = true; + PATIENCE(b).pos_in_other = a; + unique_in_both_count++; + } + + /* j now points at the first atom after 'a' that is not + * identical to 'a'. j is always > i. */ + i = j - 1; + } + *unique_in_both_count_p = unique_in_both_count; + rc = 0; +free_and_exit: + free(all_atoms); + return rc; +} +#endif /* UNIQUE_STRATEGY != 0 */ + +/* binary search to find the stack to put this atom "card" on. */ +static int +find_target_stack(struct diff_atom *atom, + struct diff_atom **patience_stacks, + unsigned int patience_stacks_count) +{ + unsigned int lo = 0; + unsigned int hi = patience_stacks_count; + while (lo < hi) { + unsigned int mid = (lo + hi) >> 1; + + if (PATIENCE(patience_stacks[mid]).pos_in_other + < PATIENCE(atom).pos_in_other) + lo = mid + 1; + else + hi = mid; + } + return lo; +} + +/* Among the lines that appear exactly once in each side, find the longest + * streak that appear in both files in the same order (with other stuff allowed + * to interleave). Use patience sort for that, as in the Patience Diff + * algorithm. + * See https://bramcohen.livejournal.com/73318.html and, for a much more + * detailed explanation, + * https://blog.jcoglan.com/2017/09/19/the-patience-diff-algorithm/ */ +int +diff_algo_patience(const struct diff_algo_config *algo_config, + struct diff_state *state) +{ + int rc; + struct diff_data *left = &state->left; + struct diff_data *right = &state->right; + struct atom_patience *atom_patience_left = + calloc(left->atoms.len, sizeof(struct atom_patience)); + struct atom_patience *atom_patience_right = + calloc(right->atoms.len, sizeof(struct atom_patience)); + unsigned int unique_in_both_count; + struct diff_atom **lcs = NULL; + + debug("\n** %s\n", __func__); + + left->root->current = left; + right->root->current = right; + left->algo_data = atom_patience_left; + right->algo_data = atom_patience_right; + + /* Find those lines that appear exactly once in 'left' and exactly once + * in 'right'. */ + rc = diff_atoms_mark_unique_in_both(left, right, &unique_in_both_count); + if (rc) + goto free_and_exit; + + debug("unique_in_both_count %u\n", unique_in_both_count); + debug("left:\n"); + debug_dump(left); + debug("right:\n"); + debug_dump(right); + + if (!unique_in_both_count) { + /* Cannot apply Patience, tell the caller to use fallback_algo + * instead. */ + rc = DIFF_RC_USE_DIFF_ALGO_FALLBACK; + goto free_and_exit; + } + + rc = ENOMEM; + + /* An array of Longest Common Sequence is the result of the below + * subscope: */ + unsigned int lcs_count = 0; + struct diff_atom *lcs_tail = NULL; + + { + /* This subscope marks the lifetime of the atom_pointers + * allocation */ + + /* One chunk of storage for atom pointers */ + struct diff_atom **atom_pointers; + atom_pointers = recallocarray(NULL, 0, unique_in_both_count * 2, + sizeof(struct diff_atom*)); + if (atom_pointers == NULL) + return ENOMEM; + /* Half for the list of atoms that still need to be put on + * stacks */ + struct diff_atom **uniques = atom_pointers; + + /* Half for the patience sort state's "card stacks" -- we + * remember only each stack's topmost "card" */ + struct diff_atom **patience_stacks; + patience_stacks = atom_pointers + unique_in_both_count; + unsigned int patience_stacks_count = 0; + + /* Take all common, unique items from 'left' ... */ + + struct diff_atom *atom; + struct diff_atom **uniques_end = uniques; + diff_data_foreach_atom(atom, left) { + if (!PATIENCE(atom).unique_in_both) + continue; + *uniques_end = atom; + uniques_end++; + } + + /* ...and sort them to the order found in 'right'. + * The idea is to find the leftmost stack that has a higher line + * number and add it to the stack's top. + * If there is no such stack, open a new one on the right. The + * line number is derived from the atom*, which are array items + * and hence reflect the relative position in the source file. + * So we got the common-uniques from 'left' and sort them + * according to PATIENCE(atom).pos_in_other. */ + unsigned int i; + for (i = 0; i < unique_in_both_count; i++) { + atom = uniques[i]; + unsigned int target_stack; + target_stack = find_target_stack(atom, patience_stacks, + patience_stacks_count); + assert(target_stack <= patience_stacks_count); + patience_stacks[target_stack] = atom; + if (target_stack == patience_stacks_count) + patience_stacks_count++; + + /* Record a back reference to the next stack on the + * left, which will form the final longest sequence + * later. */ + PATIENCE(atom).prev_stack = target_stack ? + patience_stacks[target_stack - 1] : NULL; + + { + int xx; + for (xx = 0; xx < patience_stacks_count; xx++) { + debug(" %s%d", + (xx == target_stack) ? ">" : "", + diff_atom_idx(right, + PATIENCE(patience_stacks[xx]).pos_in_other)); + } + debug("\n"); + } + } + + /* backtrace through prev_stack references to form the final + * longest common sequence */ + lcs_tail = patience_stacks[patience_stacks_count - 1]; + lcs_count = patience_stacks_count; + + /* uniques and patience_stacks are no longer needed. + * Backpointers are in PATIENCE(atom).prev_stack */ + free(atom_pointers); + } + + lcs = recallocarray(NULL, 0, lcs_count, sizeof(struct diff_atom*)); + struct diff_atom **lcs_backtrace_pos = &lcs[lcs_count - 1]; + struct diff_atom *atom; + for (atom = lcs_tail; atom; atom = PATIENCE(atom).prev_stack, lcs_backtrace_pos--) { + assert(lcs_backtrace_pos >= lcs); + *lcs_backtrace_pos = atom; + } + + unsigned int i; + if (DEBUG) { + debug("\npatience LCS:\n"); + for (i = 0; i < lcs_count; i++) { + debug("\n L "); debug_dump_atom(left, right, lcs[i]); + debug(" R "); debug_dump_atom(right, left, + PATIENCE(lcs[i]).pos_in_other); + } + } + + + /* TODO: For each common-unique line found (now listed in lcs), swallow + * lines upwards and downwards that are identical on each side. Requires + * a way to represent atoms being glued to adjacent atoms. */ + + debug("\ntraverse LCS, possibly recursing:\n"); + + /* Now we have pinned positions in both files at which it makes sense to + * divide the diff problem into smaller chunks. Go into the next round: + * look at each section in turn, trying to again find common-unique + * lines in those smaller sections. As soon as no more are found, the + * remaining smaller sections are solved by Myers. */ + /* left_pos and right_pos are indexes in left/right->atoms.head until + * which the atoms are already handled (added to result chunks). */ + unsigned int left_pos = 0; + unsigned int right_pos = 0; + for (i = 0; i <= lcs_count; i++) { + struct diff_atom *atom; + struct diff_atom *atom_r; + /* left_idx and right_idx are indexes of the start of this + * section of identical lines on both sides. + * left_pos marks the index of the first still unhandled line, + * left_idx is the start of an identical section some way + * further down, and this loop adds an unsolved chunk of + * [left_pos..left_idx[ and a solved chunk of + * [left_idx..identical_lines.end[. */ + unsigned int left_idx; + unsigned int right_idx; + + debug("iteration %u of %u left_pos %u right_pos %u\n", + i, lcs_count, left_pos, right_pos); + + if (i < lcs_count) { + atom = lcs[i]; + atom_r = PATIENCE(atom).pos_in_other; + debug("lcs[%u] = left[%u] = right[%u]\n", i, + diff_atom_idx(left, atom), diff_atom_idx(right, atom_r)); + left_idx = diff_atom_idx(left, atom); + right_idx = diff_atom_idx(right, atom_r); + } else { + /* There are no more identical lines until the end of + * left and right. */ + atom = NULL; + atom_r = NULL; + left_idx = left->atoms.len; + right_idx = right->atoms.len; + } + + /* 'atom' (if not NULL) now marks an atom that matches on both + * sides according to patience-diff (a common-unique identical + * atom in both files). + * Handle the section before and the atom itself; the section + * after will be handled by the next loop iteration -- note that + * i loops to last element + 1 ("i <= lcs_count"), so that there + * will be another final iteration to pick up the last remaining + * items after the last LCS atom. + */ + + debug("iteration %u left_pos %u left_idx %u" + " right_pos %u right_idx %u\n", + i, left_pos, left_idx, right_pos, right_idx); + + /* Section before the matching atom */ + struct diff_atom *left_atom = &left->atoms.head[left_pos]; + unsigned int left_section_len = left_idx - left_pos; + + struct diff_atom *right_atom = &(right->atoms.head[right_pos]); + unsigned int right_section_len = right_idx - right_pos; + + if (left_section_len && right_section_len) { + /* Record an unsolved chunk, the caller will apply + * inner_algo() on this chunk. */ + if (!diff_state_add_chunk(state, false, + left_atom, left_section_len, + right_atom, + right_section_len)) + goto free_and_exit; + } else if (left_section_len && !right_section_len) { + /* Only left atoms and none on the right, they form a + * "minus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, left_section_len, + right_atom, 0)) + goto free_and_exit; + } else if (!left_section_len && right_section_len) { + /* No left atoms, only atoms on the right, they form a + * "plus" chunk, then. */ + if (!diff_state_add_chunk(state, true, + left_atom, 0, + right_atom, right_section_len)) + goto free_and_exit; + } + /* else: left_section_len == 0 and right_section_len == 0, i.e. + * nothing here. */ + + /* The atom found to match on both sides forms a chunk of equals + * on each side. In the very last iteration of this loop, there + * is no matching atom, we were just cleaning out the remaining + * lines. */ + if (atom) { + void *ok; + ok = diff_state_add_chunk(state, true, + atom, 1, + PATIENCE(atom).pos_in_other, 1); + if (!ok) + goto free_and_exit; + } + left_pos = left_idx + 1; + right_pos = right_idx + 1; + debug("end of iteration %u left_pos %u left_idx %u" + " right_pos %u right_idx %u\n", + i, left_pos, left_idx, right_pos, right_idx); + } + debug("** END %s\n", __func__); + + rc = DIFF_RC_OK; + +free_and_exit: + left->root->current = NULL; + right->root->current = NULL; + free(atom_patience_left); + free(atom_patience_right); + if (lcs) + free(lcs); + return rc; +} |