1 /*
2  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
3  *
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.
7  *
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.
15  */
16 
17 #define DEBUG 0
18 
19 #if DEBUG
20 #include <stdio.h>
21 #include <unistd.h>
22 #define print(args...) fprintf(stderr, ##args)
23 #define debug print
24 #define debug_dump dump
25 #define debug_dump_atom dump_atom
26 #define debug_dump_atoms dump_atoms
27 
28 static inline void
29 print_atom_byte(unsigned char c) {
30 	if (c == '\r')
31 		print("\\r");
32 	else if (c == '\n')
33 		print("\\n");
34 	else if ((c < 32 || c >= 127) && (c != '\t'))
35 		print("\\x%02x", c);
36 	else
37 		print("%c", c);
38 }
39 
40 static inline void
41 dump_atom(const struct diff_data *left, const struct diff_data *right,
42 	  const struct diff_atom *atom)
43 {
44 	if (!atom) {
45 		print("NULL atom\n");
46 		return;
47 	}
48 	if (left)
49 		print(" %3u", diff_atom_root_idx(left, atom));
50 	if (right && atom->patience.pos_in_other)
51 		print(" %3u",
52 		      diff_atom_root_idx(right, atom->patience.pos_in_other));
53 
54 	print(" %s%s '",
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 (fseek(atom->d->root->f, atom->pos, SEEK_SET) == -1)
61 			abort(); /* cannot return error */
62 		while (remain > 0) {
63 			char buf[16];
64 			size_t r;
65 			int i;
66 			r = fread(buf, 1, MIN(remain, sizeof(buf)),
67 			    atom->d->root->f);
68 			if (r == -1)
69 				abort(); /* cannot return error */
70 			if (r == 0)
71 				break;
72 			remain -= r;
73 			for (i = 0; i < r; i++)
74 				print_atom_byte(buf[i]);
75 		}
76 	} else {
77 		const char *s;
78 		for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
79 			print_atom_byte(*s);
80 	}
81 	print("'\n");
82 }
83 
84 static inline void
85 dump_atoms(const struct diff_data *d, struct diff_atom *atom,
86 	   unsigned int count)
87 {
88 	if (count > 42) {
89 		dump_atoms(d, atom, 20);
90 		print("[%u lines skipped]\n", count - 20 - 20);
91 		dump_atoms(d, atom + count - 20, 20);
92 		return;
93 	} else {
94 		struct diff_atom *i;
95 		foreach_diff_atom(i, atom, count) {
96 			dump_atom(d, NULL, i);
97 		}
98 	}
99 }
100 
101 static inline void
102 dump(struct diff_data *d)
103 {
104 	dump_atoms(d, d->atoms.head, d->atoms.len);
105 }
106 
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
109  * Divide algorithm.
110  */
111 static inline void
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)
115 {
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"
121 	int x;
122 	int y;
123 	print("   ");
124 	for (x = 0; x <= l->atoms.len; x++)
125 		print("%2d", x % 100);
126 	print("\n");
127 
128 	for (y = 0; y <= r->atoms.len; y++) {
129 		print("%3d ", y);
130 		for (x = 0; x <= l->atoms.len; x++) {
131 
132 			/* print d advancements from kd, if any. */
133 			char label = 'o';
134 			char *color = NULL;
135 			if (kd) {
136 				int max = l->atoms.len + r->atoms.len;
137 				size_t kd_len = max + 1 + max;
138 				int *kd_pos = kd;
139 				int di;
140 #define xk_to_y(X, K) ((X) - (K))
141 				for (di = 0; di < max; di++) {
142 					int ki;
143 					for (ki = di; ki >= -di; ki -= 2) {
144 						if (x != kd_pos[ki]
145 						    || y != xk_to_y(x, ki))
146 							continue;
147 						label = '0' + (di % 10);
148 						color = COLOR_YELLOW;
149 						break;
150 					}
151 					if (label != 'o')
152 						break;
153 					kd_pos += kd_len;
154 				}
155 			}
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;
159 				int di;
160 #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
161 				int delta = (int)r->atoms.len
162 					    - (int)l->atoms.len;
163 				int ki;
164 				for (ki = kd_forward_d;
165 				     ki >= -kd_forward_d;
166 				     ki -= 2) {
167 					if (x != kd_forward[ki])
168 						continue;
169 					if (y != xk_to_y(x, ki))
170 						continue;
171 					label = 'F';
172 					color = COLOR_GREEN;
173 					break;
174 				}
175 			}
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;
179 				int di;
180 				int delta = (int)r->atoms.len
181 					    - (int)l->atoms.len;
182 				int ki;
183 				for (ki = kd_backward_d;
184 				     ki >= -kd_backward_d;
185 				     ki -= 2) {
186 					if (x != kd_backward[ki])
187 						continue;
188 					if (y != xc_to_y(x, ki, delta))
189 						continue;
190 					if (label == 'o') {
191 						label = 'B';
192 						color = COLOR_BLUE;
193 					} else {
194 						label = 'X';
195 						color = COLOR_RED;
196 					}
197 					break;
198 				}
199 			}
200 			if (color)
201 				print("%s", color);
202 			print("%c", label);
203 			if (color)
204 				print("%s", COLOR_END);
205 			if (x < l->atoms.len)
206 				print("-");
207 		}
208 		print("\n");
209 		if (y == r->atoms.len)
210 			break;
211 
212 		print("    ");
213 		for (x = 0; x < l->atoms.len; x++) {
214 			bool same;
215 			diff_atom_same(&same, &l->atoms.head[x],
216 			    &r->atoms.head[y]);
217 			if (same)
218 				print("|\\");
219 			else
220 				print("| ");
221 		}
222 		print("|\n");
223 	}
224 }
225 
226 static inline void
227 debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
228 		       int *kd, int *kd_forward, int kd_forward_d,
229 		       int *kd_backward, int kd_backward_d)
230 {
231 	if (l->atoms.len > 99 || r->atoms.len > 99)
232 		return;
233 	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
234 			 kd_backward, kd_backward_d);
235 }
236 
237 #else
238 #define debug(args...)
239 #define debug_dump(args...)
240 #define debug_dump_atom(args...)
241 #define debug_dump_atoms(args...)
242 #define debug_dump_myers_graph(args...)
243 #endif