2 3b0f3d61 2020-01-22 neels * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4 3b0f3d61 2020-01-22 neels * Permission to use, copy, modify, and distribute this software for any
5 3b0f3d61 2020-01-22 neels * purpose with or without fee is hereby granted, provided that the above
6 3b0f3d61 2020-01-22 neels * copyright notice and this permission notice appear in all copies.
8 3b0f3d61 2020-01-22 neels * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 3b0f3d61 2020-01-22 neels * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 3b0f3d61 2020-01-22 neels * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 3b0f3d61 2020-01-22 neels * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 3b0f3d61 2020-01-22 neels * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 3b0f3d61 2020-01-22 neels * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 3b0f3d61 2020-01-22 neels * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 3b0f3d61 2020-01-22 neels #define DEBUG 0
20 3b0f3d61 2020-01-22 neels #include <stdio.h>
21 c6eecea3 2020-07-26 stsp #include <unistd.h>
22 3b0f3d61 2020-01-22 neels #define print(args...) fprintf(stderr, ##args)
23 3b0f3d61 2020-01-22 neels #define debug print
24 3b0f3d61 2020-01-22 neels #define debug_dump dump
25 3b0f3d61 2020-01-22 neels #define debug_dump_atom dump_atom
26 3b0f3d61 2020-01-22 neels #define debug_dump_atoms dump_atoms
28 61a7b578 2020-05-06 neels static inline void
29 c6eecea3 2020-07-26 stsp print_atom_byte(unsigned char c) {
30 c6eecea3 2020-07-26 stsp if (c == '\r')
31 c6eecea3 2020-07-26 stsp print("\\r");
32 c6eecea3 2020-07-26 stsp else if (c == '\n')
33 c6eecea3 2020-07-26 stsp print("\\n");
34 c6eecea3 2020-07-26 stsp else if ((c < 32 || c >= 127) && (c != '\t'))
35 c6eecea3 2020-07-26 stsp print("\\x%02x", c);
37 c6eecea3 2020-07-26 stsp print("%c", c);
40 c6eecea3 2020-07-26 stsp static inline void
41 0d27172a 2020-05-06 neels dump_atom(const struct diff_data *left, const struct diff_data *right,
42 0d27172a 2020-05-06 neels const struct diff_atom *atom)
44 3b0f3d61 2020-01-22 neels if (!atom) {
45 3b0f3d61 2020-01-22 neels print("NULL atom\n");
49 3b0f3d61 2020-01-22 neels print(" %3ld", diff_atom_root_idx(left, atom));
50 3b0f3d61 2020-01-22 neels if (right && atom->patience.pos_in_other)
51 0d27172a 2020-05-06 neels print(" %3ld",
52 0d27172a 2020-05-06 neels diff_atom_root_idx(right, atom->patience.pos_in_other));
54 0d27172a 2020-05-06 neels print(" %s%s '",
55 0d27172a 2020-05-06 neels atom->patience.unique_here ? "u" : " ",
56 0d27172a 2020-05-06 neels atom->patience.unique_in_both ? "c" : " ");
57 c6eecea3 2020-07-26 stsp if (atom->at == NULL) {
58 c6eecea3 2020-07-26 stsp unsigned long long total = 0;
59 c6eecea3 2020-07-26 stsp off_t remain = atom->len;
60 c6eecea3 2020-07-26 stsp if (lseek(atom->d->root->fd, atom->pos, SEEK_SET) == -1)
61 c6eecea3 2020-07-26 stsp abort(); /* cannot return error */
62 c6eecea3 2020-07-26 stsp while (remain > 0) {
63 c6eecea3 2020-07-26 stsp char buf[16];
66 c6eecea3 2020-07-26 stsp r = read(atom->d->root->fd, buf,
67 c6eecea3 2020-07-26 stsp MIN(remain, sizeof(buf)));
68 c6eecea3 2020-07-26 stsp if (r == -1)
69 c6eecea3 2020-07-26 stsp abort(); /* cannot return error */
72 c6eecea3 2020-07-26 stsp remain -= r;
73 c6eecea3 2020-07-26 stsp for (i = 0; i < r; i++)
74 c6eecea3 2020-07-26 stsp print_atom_byte(buf[i]);
77 c6eecea3 2020-07-26 stsp const char *s;
78 c6eecea3 2020-07-26 stsp for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
79 c6eecea3 2020-07-26 stsp print_atom_byte(*s);
81 3b0f3d61 2020-01-22 neels print("'\n");
84 61a7b578 2020-05-06 neels static inline void
85 0d27172a 2020-05-06 neels dump_atoms(const struct diff_data *d, struct diff_atom *atom,
86 0d27172a 2020-05-06 neels unsigned int count)
88 13b15273 2020-01-27 neels if (count > 42) {
89 13b15273 2020-01-27 neels dump_atoms(d, atom, 20);
90 13b15273 2020-01-27 neels print("[%u lines skipped]\n", count - 20 - 20);
91 13b15273 2020-01-27 neels dump_atoms(d, atom + count - 20, 20);
94 13b15273 2020-01-27 neels struct diff_atom *i;
95 13b15273 2020-01-27 neels foreach_diff_atom(i, atom, count) {
96 13b15273 2020-01-27 neels dump_atom(d, NULL, i);
101 61a7b578 2020-05-06 neels static inline void
102 61a7b578 2020-05-06 neels dump(struct diff_data *d)
104 3b0f3d61 2020-01-22 neels dump_atoms(d, d->atoms.head, d->atoms.len);
107 50198b5f 2020-05-05 neels /* kd is a quadratic space myers matrix from the original Myers algorithm.
108 0d27172a 2020-05-06 neels * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
109 0d27172a 2020-05-06 neels * Divide algorithm.
111 61a7b578 2020-05-06 neels static inline void
112 61a7b578 2020-05-06 neels dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
113 0d27172a 2020-05-06 neels int *kd, int *kd_forward, int kd_forward_d,
114 0d27172a 2020-05-06 neels int *kd_backward, int kd_backward_d)
116 50198b5f 2020-05-05 neels #define COLOR_YELLOW "\033[1;33m"
117 50198b5f 2020-05-05 neels #define COLOR_GREEN "\033[1;32m"
118 50198b5f 2020-05-05 neels #define COLOR_BLUE "\033[1;34m"
119 50198b5f 2020-05-05 neels #define COLOR_RED "\033[1;31m"
120 50198b5f 2020-05-05 neels #define COLOR_END "\033[0;m"
123 50198b5f 2020-05-05 neels print(" ");
124 3b0f3d61 2020-01-22 neels for (x = 0; x <= l->atoms.len; x++)
125 50198b5f 2020-05-05 neels print("%2d", x % 100);
126 3b0f3d61 2020-01-22 neels print("\n");
128 3b0f3d61 2020-01-22 neels for (y = 0; y <= r->atoms.len; y++) {
129 50198b5f 2020-05-05 neels print("%3d ", y);
130 3b0f3d61 2020-01-22 neels for (x = 0; x <= l->atoms.len; x++) {
132 3b0f3d61 2020-01-22 neels /* print d advancements from kd, if any. */
133 50198b5f 2020-05-05 neels char label = 'o';
134 50198b5f 2020-05-05 neels char *color = NULL;
136 3b0f3d61 2020-01-22 neels int max = l->atoms.len + r->atoms.len;
137 3b0f3d61 2020-01-22 neels size_t kd_len = max + 1 + max;
138 3b0f3d61 2020-01-22 neels int *kd_pos = kd;
140 3b0f3d61 2020-01-22 neels #define xk_to_y(X, K) ((X) - (K))
141 3b0f3d61 2020-01-22 neels for (di = 0; di < max; di++) {
143 3b0f3d61 2020-01-22 neels for (ki = di; ki >= -di; ki -= 2) {
144 50198b5f 2020-05-05 neels if (x != kd_pos[ki]
145 50198b5f 2020-05-05 neels || y != xk_to_y(x, ki))
147 50198b5f 2020-05-05 neels label = '0' + (di % 10);
148 50198b5f 2020-05-05 neels color = COLOR_YELLOW;
151 50198b5f 2020-05-05 neels if (label != 'o')
153 3b0f3d61 2020-01-22 neels kd_pos += kd_len;
156 50198b5f 2020-05-05 neels if (kd_forward && kd_forward_d >= 0) {
157 50198b5f 2020-05-05 neels int max = l->atoms.len + r->atoms.len;
158 50198b5f 2020-05-05 neels size_t kd_len = max + 1 + max;
160 50198b5f 2020-05-05 neels #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
161 0d27172a 2020-05-06 neels int delta = (int)r->atoms.len
162 0d27172a 2020-05-06 neels - (int)l->atoms.len;
164 0d27172a 2020-05-06 neels for (ki = kd_forward_d;
165 0d27172a 2020-05-06 neels ki >= -kd_forward_d;
166 0d27172a 2020-05-06 neels ki -= 2) {
167 50198b5f 2020-05-05 neels if (x != kd_forward[ki])
169 50198b5f 2020-05-05 neels if (y != xk_to_y(x, ki))
171 50198b5f 2020-05-05 neels label = 'F';
172 50198b5f 2020-05-05 neels color = COLOR_GREEN;
176 50198b5f 2020-05-05 neels if (kd_backward && kd_backward_d >= 0) {
177 50198b5f 2020-05-05 neels int max = l->atoms.len + r->atoms.len;
178 50198b5f 2020-05-05 neels size_t kd_len = max + 1 + max;
180 0d27172a 2020-05-06 neels int delta = (int)r->atoms.len
181 0d27172a 2020-05-06 neels - (int)l->atoms.len;
183 0d27172a 2020-05-06 neels for (ki = kd_backward_d;
184 0d27172a 2020-05-06 neels ki >= -kd_backward_d;
185 0d27172a 2020-05-06 neels ki -= 2) {
186 50198b5f 2020-05-05 neels if (x != kd_backward[ki])
188 50198b5f 2020-05-05 neels if (y != xc_to_y(x, ki, delta))
190 50198b5f 2020-05-05 neels if (label == 'o') {
191 50198b5f 2020-05-05 neels label = 'B';
192 50198b5f 2020-05-05 neels color = COLOR_BLUE;
194 50198b5f 2020-05-05 neels label = 'X';
195 50198b5f 2020-05-05 neels color = COLOR_RED;
200 50198b5f 2020-05-05 neels if (color)
201 50198b5f 2020-05-05 neels print("%s", color);
202 50198b5f 2020-05-05 neels print("%c", label);
203 50198b5f 2020-05-05 neels if (color)
204 50198b5f 2020-05-05 neels print("%s", COLOR_END);
205 50198b5f 2020-05-05 neels if (x < l->atoms.len)
206 3b0f3d61 2020-01-22 neels print("-");
208 3b0f3d61 2020-01-22 neels print("\n");
209 3b0f3d61 2020-01-22 neels if (y == r->atoms.len)
212 50198b5f 2020-05-05 neels print(" ");
213 3b0f3d61 2020-01-22 neels for (x = 0; x < l->atoms.len; x++) {
214 0d27172a 2020-05-06 neels if (diff_atom_same(&l->atoms.head[x],
215 0d27172a 2020-05-06 neels &r->atoms.head[y]))
216 3b0f3d61 2020-01-22 neels print("|\\");
218 3b0f3d61 2020-01-22 neels print("| ");
220 3b0f3d61 2020-01-22 neels print("|\n");
224 61a7b578 2020-05-06 neels static inline void
225 61a7b578 2020-05-06 neels debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
226 0d27172a 2020-05-06 neels int *kd, int *kd_forward, int kd_forward_d,
227 0d27172a 2020-05-06 neels int *kd_backward, int kd_backward_d)
229 72057b70 2020-01-27 neels if (l->atoms.len > 99 || r->atoms.len > 99)
231 0d27172a 2020-05-06 neels dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
232 0d27172a 2020-05-06 neels kd_backward, kd_backward_d);
236 3b0f3d61 2020-01-22 neels #define debug(args...)
237 3b0f3d61 2020-01-22 neels #define debug_dump(args...)
238 3b0f3d61 2020-01-22 neels #define debug_dump_atom(args...)
239 3b0f3d61 2020-01-22 neels #define debug_dump_atoms(args...)
240 3b0f3d61 2020-01-22 neels #define debug_dump_myers_graph(args...)