2 * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4 * Permission to use, copy, modify, and distribute this software for any
5 * purpose with or without fee is hereby granted, provided that the above
6 * copyright notice and this permission notice appear in all copies.
8 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
22 #define print(args...) fprintf(stderr, ##args)
24 #define debug_dump dump
25 #define debug_dump_atom dump_atom
26 #define debug_dump_atoms dump_atoms
29 print_atom_byte(unsigned char c) {
34 else if ((c < 32 || c >= 127) && (c != '\t'))
41 dump_atom(const struct diff_data *left, const struct diff_data *right,
42 const struct diff_atom *atom)
49 print(" %3ld", diff_atom_root_idx(left, atom));
50 if (right && atom->patience.pos_in_other)
52 diff_atom_root_idx(right, atom->patience.pos_in_other));
55 atom->patience.unique_here ? "u" : " ",
56 atom->patience.unique_in_both ? "c" : " ");
57 if (atom->at == NULL) {
58 unsigned long long total = 0;
59 off_t remain = atom->len;
60 if (lseek(atom->d->root->fd, atom->pos, SEEK_SET) == -1)
61 abort(); /* cannot return error */
66 r = read(atom->d->root->fd, buf,
67 MIN(remain, sizeof(buf)));
69 abort(); /* cannot return error */
73 for (i = 0; i < r; i++)
74 print_atom_byte(buf[i]);
78 for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
85 dump_atoms(const struct diff_data *d, struct diff_atom *atom,
89 dump_atoms(d, atom, 20);
90 print("[%u lines skipped]\n", count - 20 - 20);
91 dump_atoms(d, atom + count - 20, 20);
95 foreach_diff_atom(i, atom, count) {
96 dump_atom(d, NULL, i);
102 dump(struct diff_data *d)
104 dump_atoms(d, d->atoms.head, d->atoms.len);
107 /* kd is a quadratic space myers matrix from the original Myers algorithm.
108 * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
112 dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
113 int *kd, int *kd_forward, int kd_forward_d,
114 int *kd_backward, int kd_backward_d)
116 #define COLOR_YELLOW "\033[1;33m"
117 #define COLOR_GREEN "\033[1;32m"
118 #define COLOR_BLUE "\033[1;34m"
119 #define COLOR_RED "\033[1;31m"
120 #define COLOR_END "\033[0;m"
124 for (x = 0; x <= l->atoms.len; x++)
125 print("%2d", x % 100);
128 for (y = 0; y <= r->atoms.len; y++) {
130 for (x = 0; x <= l->atoms.len; x++) {
132 /* print d advancements from kd, if any. */
136 int max = l->atoms.len + r->atoms.len;
137 size_t kd_len = max + 1 + max;
140 #define xk_to_y(X, K) ((X) - (K))
141 for (di = 0; di < max; di++) {
143 for (ki = di; ki >= -di; ki -= 2) {
145 || y != xk_to_y(x, ki))
147 label = '0' + (di % 10);
148 color = COLOR_YELLOW;
156 if (kd_forward && kd_forward_d >= 0) {
157 int max = l->atoms.len + r->atoms.len;
158 size_t kd_len = max + 1 + max;
160 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
161 int delta = (int)r->atoms.len
164 for (ki = kd_forward_d;
167 if (x != kd_forward[ki])
169 if (y != xk_to_y(x, ki))
176 if (kd_backward && kd_backward_d >= 0) {
177 int max = l->atoms.len + r->atoms.len;
178 size_t kd_len = max + 1 + max;
180 int delta = (int)r->atoms.len
183 for (ki = kd_backward_d;
184 ki >= -kd_backward_d;
186 if (x != kd_backward[ki])
188 if (y != xc_to_y(x, ki, delta))
204 print("%s", COLOR_END);
205 if (x < l->atoms.len)
209 if (y == r->atoms.len)
213 for (x = 0; x < l->atoms.len; x++) {
214 if (diff_atom_same(&l->atoms.head[x],
225 debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
226 int *kd, int *kd_forward, int kd_forward_d,
227 int *kd_backward, int kd_backward_d)
229 if (l->atoms.len > 99 || r->atoms.len > 99)
231 dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
232 kd_backward, kd_backward_d);
236 #define debug(args...)
237 #define debug_dump(args...)
238 #define debug_dump_atom(args...)
239 #define debug_dump_atoms(args...)
240 #define debug_dump_myers_graph(args...)