2 fe621944 2020-11-10 stsp * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
4 fe621944 2020-11-10 stsp * Permission to use, copy, modify, and distribute this software for any
5 fe621944 2020-11-10 stsp * purpose with or without fee is hereby granted, provided that the above
6 fe621944 2020-11-10 stsp * copyright notice and this permission notice appear in all copies.
8 fe621944 2020-11-10 stsp * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
9 fe621944 2020-11-10 stsp * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
10 fe621944 2020-11-10 stsp * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
11 fe621944 2020-11-10 stsp * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
12 fe621944 2020-11-10 stsp * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
13 fe621944 2020-11-10 stsp * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
14 fe621944 2020-11-10 stsp * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
17 fe621944 2020-11-10 stsp #define DEBUG 0
20 fe621944 2020-11-10 stsp #include <stdio.h>
21 fe621944 2020-11-10 stsp #include <unistd.h>
22 fe621944 2020-11-10 stsp #define print(args...) fprintf(stderr, ##args)
23 fe621944 2020-11-10 stsp #define debug print
24 fe621944 2020-11-10 stsp #define debug_dump dump
25 fe621944 2020-11-10 stsp #define debug_dump_atom dump_atom
26 fe621944 2020-11-10 stsp #define debug_dump_atoms dump_atoms
28 fe621944 2020-11-10 stsp static inline void
29 fe621944 2020-11-10 stsp print_atom_byte(unsigned char c) {
30 fe621944 2020-11-10 stsp if (c == '\r')
31 fe621944 2020-11-10 stsp print("\\r");
32 fe621944 2020-11-10 stsp else if (c == '\n')
33 fe621944 2020-11-10 stsp print("\\n");
34 fe621944 2020-11-10 stsp else if ((c < 32 || c >= 127) && (c != '\t'))
35 fe621944 2020-11-10 stsp print("\\x%02x", c);
37 fe621944 2020-11-10 stsp print("%c", c);
40 fe621944 2020-11-10 stsp static inline void
41 fe621944 2020-11-10 stsp dump_atom(const struct diff_data *left, const struct diff_data *right,
42 fe621944 2020-11-10 stsp const struct diff_atom *atom)
44 fe621944 2020-11-10 stsp if (!atom) {
45 fe621944 2020-11-10 stsp print("NULL atom\n");
49 fe621944 2020-11-10 stsp print(" %3u '", diff_atom_root_idx(left, atom));
51 fe621944 2020-11-10 stsp if (atom->at == NULL) {
52 fe621944 2020-11-10 stsp off_t remain = atom->len;
53 fe621944 2020-11-10 stsp if (fseek(atom->root->f, atom->pos, SEEK_SET) == -1)
54 fe621944 2020-11-10 stsp abort(); /* cannot return error */
55 fe621944 2020-11-10 stsp while (remain > 0) {
56 fe621944 2020-11-10 stsp char buf[16];
59 fe621944 2020-11-10 stsp r = fread(buf, 1, MIN(remain, sizeof(buf)),
60 fe621944 2020-11-10 stsp atom->root->f);
61 fe621944 2020-11-10 stsp if (r == -1)
62 fe621944 2020-11-10 stsp abort(); /* cannot return error */
65 fe621944 2020-11-10 stsp remain -= r;
66 fe621944 2020-11-10 stsp for (i = 0; i < r; i++)
67 fe621944 2020-11-10 stsp print_atom_byte(buf[i]);
70 fe621944 2020-11-10 stsp const char *s;
71 fe621944 2020-11-10 stsp for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
72 fe621944 2020-11-10 stsp print_atom_byte(*s);
74 fe621944 2020-11-10 stsp print("'\n");
77 fe621944 2020-11-10 stsp static inline void
78 fe621944 2020-11-10 stsp dump_atoms(const struct diff_data *d, struct diff_atom *atom,
79 fe621944 2020-11-10 stsp unsigned int count)
81 fe621944 2020-11-10 stsp if (count > 42) {
82 fe621944 2020-11-10 stsp dump_atoms(d, atom, 20);
83 fe621944 2020-11-10 stsp print("[%u lines skipped]\n", count - 20 - 20);
84 fe621944 2020-11-10 stsp dump_atoms(d, atom + count - 20, 20);
87 fe621944 2020-11-10 stsp struct diff_atom *i;
88 fe621944 2020-11-10 stsp foreach_diff_atom(i, atom, count) {
89 fe621944 2020-11-10 stsp dump_atom(d, NULL, i);
94 fe621944 2020-11-10 stsp static inline void
95 fe621944 2020-11-10 stsp dump(struct diff_data *d)
97 fe621944 2020-11-10 stsp dump_atoms(d, d->atoms.head, d->atoms.len);
100 fe621944 2020-11-10 stsp /* kd is a quadratic space myers matrix from the original Myers algorithm.
101 fe621944 2020-11-10 stsp * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
102 fe621944 2020-11-10 stsp * Divide algorithm.
104 fe621944 2020-11-10 stsp static inline void
105 fe621944 2020-11-10 stsp dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
106 fe621944 2020-11-10 stsp int *kd, int *kd_forward, int kd_forward_d,
107 fe621944 2020-11-10 stsp int *kd_backward, int kd_backward_d)
109 fe621944 2020-11-10 stsp #define COLOR_YELLOW "\033[1;33m"
110 fe621944 2020-11-10 stsp #define COLOR_GREEN "\033[1;32m"
111 fe621944 2020-11-10 stsp #define COLOR_BLUE "\033[1;34m"
112 fe621944 2020-11-10 stsp #define COLOR_RED "\033[1;31m"
113 fe621944 2020-11-10 stsp #define COLOR_END "\033[0;m"
116 fe621944 2020-11-10 stsp print(" ");
117 fe621944 2020-11-10 stsp for (x = 0; x <= l->atoms.len; x++)
118 fe621944 2020-11-10 stsp print("%2d", x % 100);
119 fe621944 2020-11-10 stsp print("\n");
121 fe621944 2020-11-10 stsp for (y = 0; y <= r->atoms.len; y++) {
122 fe621944 2020-11-10 stsp print("%3d ", y);
123 fe621944 2020-11-10 stsp for (x = 0; x <= l->atoms.len; x++) {
125 fe621944 2020-11-10 stsp /* print d advancements from kd, if any. */
126 fe621944 2020-11-10 stsp char label = 'o';
127 fe621944 2020-11-10 stsp char *color = NULL;
129 fe621944 2020-11-10 stsp int max = l->atoms.len + r->atoms.len;
130 fe621944 2020-11-10 stsp size_t kd_len = max + 1 + max;
131 fe621944 2020-11-10 stsp int *kd_pos = kd;
133 fe621944 2020-11-10 stsp #define xk_to_y(X, K) ((X) - (K))
134 fe621944 2020-11-10 stsp for (di = 0; di < max; di++) {
136 fe621944 2020-11-10 stsp for (ki = di; ki >= -di; ki -= 2) {
137 fe621944 2020-11-10 stsp if (x != kd_pos[ki]
138 fe621944 2020-11-10 stsp || y != xk_to_y(x, ki))
140 fe621944 2020-11-10 stsp label = '0' + (di % 10);
141 fe621944 2020-11-10 stsp color = COLOR_YELLOW;
144 fe621944 2020-11-10 stsp if (label != 'o')
146 fe621944 2020-11-10 stsp kd_pos += kd_len;
149 fe621944 2020-11-10 stsp if (kd_forward && kd_forward_d >= 0) {
150 fe621944 2020-11-10 stsp #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
152 fe621944 2020-11-10 stsp for (ki = kd_forward_d;
153 fe621944 2020-11-10 stsp ki >= -kd_forward_d;
155 fe621944 2020-11-10 stsp if (x != kd_forward[ki])
157 fe621944 2020-11-10 stsp if (y != xk_to_y(x, ki))
159 fe621944 2020-11-10 stsp label = 'F';
160 fe621944 2020-11-10 stsp color = COLOR_GREEN;
164 fe621944 2020-11-10 stsp if (kd_backward && kd_backward_d >= 0) {
165 fe621944 2020-11-10 stsp int delta = (int)r->atoms.len
166 fe621944 2020-11-10 stsp - (int)l->atoms.len;
168 fe621944 2020-11-10 stsp for (ki = kd_backward_d;
169 fe621944 2020-11-10 stsp ki >= -kd_backward_d;
171 fe621944 2020-11-10 stsp if (x != kd_backward[ki])
173 fe621944 2020-11-10 stsp if (y != xc_to_y(x, ki, delta))
175 fe621944 2020-11-10 stsp if (label == 'o') {
176 fe621944 2020-11-10 stsp label = 'B';
177 fe621944 2020-11-10 stsp color = COLOR_BLUE;
179 fe621944 2020-11-10 stsp label = 'X';
180 fe621944 2020-11-10 stsp color = COLOR_RED;
186 fe621944 2020-11-10 stsp print("%s", color);
187 fe621944 2020-11-10 stsp print("%c", label);
189 fe621944 2020-11-10 stsp print("%s", COLOR_END);
190 fe621944 2020-11-10 stsp if (x < l->atoms.len)
191 fe621944 2020-11-10 stsp print("-");
193 fe621944 2020-11-10 stsp print("\n");
194 fe621944 2020-11-10 stsp if (y == r->atoms.len)
197 fe621944 2020-11-10 stsp print(" ");
198 fe621944 2020-11-10 stsp for (x = 0; x < l->atoms.len; x++) {
200 fe621944 2020-11-10 stsp diff_atom_same(&same, &l->atoms.head[x],
201 fe621944 2020-11-10 stsp &r->atoms.head[y]);
203 fe621944 2020-11-10 stsp print("|\\");
205 fe621944 2020-11-10 stsp print("| ");
207 fe621944 2020-11-10 stsp print("|\n");
211 fe621944 2020-11-10 stsp static inline void
212 fe621944 2020-11-10 stsp debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
213 fe621944 2020-11-10 stsp int *kd, int *kd_forward, int kd_forward_d,
214 fe621944 2020-11-10 stsp int *kd_backward, int kd_backward_d)
216 fe621944 2020-11-10 stsp if (l->atoms.len > 99 || r->atoms.len > 99)
218 fe621944 2020-11-10 stsp dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
219 fe621944 2020-11-10 stsp kd_backward, kd_backward_d);
223 fe621944 2020-11-10 stsp #define debug(args...)
224 fe621944 2020-11-10 stsp #define debug_dump(args...)
225 fe621944 2020-11-10 stsp #define debug_dump_atom(args...)
226 fe621944 2020-11-10 stsp #define debug_dump_atoms(args...)
227 fe621944 2020-11-10 stsp #define debug_dump_myers_graph(args...)