1 e4464189 2020-09-20 stsp /*
  2 e4464189 2020-09-20 stsp  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  3 e4464189 2020-09-20 stsp  *
  4 e4464189 2020-09-20 stsp  * Permission to use, copy, modify, and distribute this software for any
  5 e4464189 2020-09-20 stsp  * purpose with or without fee is hereby granted, provided that the above
  6 e4464189 2020-09-20 stsp  * copyright notice and this permission notice appear in all copies.
  7 e4464189 2020-09-20 stsp  *
  8 e4464189 2020-09-20 stsp  * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
  9 e4464189 2020-09-20 stsp  * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 10 e4464189 2020-09-20 stsp  * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 11 e4464189 2020-09-20 stsp  * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 12 e4464189 2020-09-20 stsp  * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 13 e4464189 2020-09-20 stsp  * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 14 e4464189 2020-09-20 stsp  * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 15 e4464189 2020-09-20 stsp  */
 16 e4464189 2020-09-20 stsp 
 17 5e241379 2020-10-06 stsp #define DEBUG 0
 18 e4464189 2020-09-20 stsp 
 19 e4464189 2020-09-20 stsp #if DEBUG
 20 e4464189 2020-09-20 stsp #include <stdio.h>
 21 e4464189 2020-09-20 stsp #include <unistd.h>
 22 e4464189 2020-09-20 stsp #define print(args...) fprintf(stderr, ##args)
 23 e4464189 2020-09-20 stsp #define debug print
 24 e4464189 2020-09-20 stsp #define debug_dump dump
 25 e4464189 2020-09-20 stsp #define debug_dump_atom dump_atom
 26 e4464189 2020-09-20 stsp #define debug_dump_atoms dump_atoms
 27 e4464189 2020-09-20 stsp 
 28 e4464189 2020-09-20 stsp static inline void
 29 e4464189 2020-09-20 stsp print_atom_byte(unsigned char c) {
 30 e4464189 2020-09-20 stsp 	if (c == '\r')
 31 e4464189 2020-09-20 stsp 		print("\\r");
 32 e4464189 2020-09-20 stsp 	else if (c == '\n')
 33 e4464189 2020-09-20 stsp 		print("\\n");
 34 e4464189 2020-09-20 stsp 	else if ((c < 32 || c >= 127) && (c != '\t'))
 35 e4464189 2020-09-20 stsp 		print("\\x%02x", c);
 36 e4464189 2020-09-20 stsp 	else
 37 e4464189 2020-09-20 stsp 		print("%c", c);
 38 e4464189 2020-09-20 stsp }
 39 e4464189 2020-09-20 stsp 
 40 e4464189 2020-09-20 stsp static inline void
 41 e4464189 2020-09-20 stsp dump_atom(const struct diff_data *left, const struct diff_data *right,
 42 e4464189 2020-09-20 stsp 	  const struct diff_atom *atom)
 43 e4464189 2020-09-20 stsp {
 44 e4464189 2020-09-20 stsp 	if (!atom) {
 45 e4464189 2020-09-20 stsp 		print("NULL atom\n");
 46 e4464189 2020-09-20 stsp 		return;
 47 e4464189 2020-09-20 stsp 	}
 48 e4464189 2020-09-20 stsp 	if (left)
 49 2a1b94d0 2020-09-26 stsp 		print(" %3u", diff_atom_root_idx(left, atom));
 50 e4464189 2020-09-20 stsp 	if (right && atom->patience.pos_in_other)
 51 2a1b94d0 2020-09-26 stsp 		print(" %3u",
 52 e4464189 2020-09-20 stsp 		      diff_atom_root_idx(right, atom->patience.pos_in_other));
 53 e4464189 2020-09-20 stsp 
 54 e4464189 2020-09-20 stsp 	print(" %s%s '",
 55 e4464189 2020-09-20 stsp 	      atom->patience.unique_here ? "u" : " ",
 56 e4464189 2020-09-20 stsp 	      atom->patience.unique_in_both ? "c" : " ");
 57 e4464189 2020-09-20 stsp 	if (atom->at == NULL) {
 58 e4464189 2020-09-20 stsp 		off_t remain = atom->len;
 59 2a1b94d0 2020-09-26 stsp 		if (fseek(atom->d->root->f, atom->pos, SEEK_SET) == -1)
 60 e4464189 2020-09-20 stsp 			abort(); /* cannot return error */
 61 e4464189 2020-09-20 stsp 		while (remain > 0) {
 62 e4464189 2020-09-20 stsp 			char buf[16];
 63 2a1b94d0 2020-09-26 stsp 			size_t r;
 64 e4464189 2020-09-20 stsp 			int i;
 65 2a1b94d0 2020-09-26 stsp 			r = fread(buf, 1, MIN(remain, sizeof(buf)),
 66 2a1b94d0 2020-09-26 stsp 			    atom->d->root->f);
 67 e4464189 2020-09-20 stsp 			if (r == -1)
 68 e4464189 2020-09-20 stsp 				abort(); /* cannot return error */
 69 e4464189 2020-09-20 stsp 			if (r == 0)
 70 e4464189 2020-09-20 stsp 				break;
 71 e4464189 2020-09-20 stsp 			remain -= r;
 72 e4464189 2020-09-20 stsp 			for (i = 0; i < r; i++)
 73 e4464189 2020-09-20 stsp 				print_atom_byte(buf[i]);
 74 e4464189 2020-09-20 stsp 		}
 75 e4464189 2020-09-20 stsp 	} else {
 76 e4464189 2020-09-20 stsp 		const char *s;
 77 e4464189 2020-09-20 stsp 		for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
 78 e4464189 2020-09-20 stsp 			print_atom_byte(*s);
 79 e4464189 2020-09-20 stsp 	}
 80 e4464189 2020-09-20 stsp 	print("'\n");
 81 e4464189 2020-09-20 stsp }
 82 e4464189 2020-09-20 stsp 
 83 e4464189 2020-09-20 stsp static inline void
 84 e4464189 2020-09-20 stsp dump_atoms(const struct diff_data *d, struct diff_atom *atom,
 85 e4464189 2020-09-20 stsp 	   unsigned int count)
 86 e4464189 2020-09-20 stsp {
 87 e4464189 2020-09-20 stsp 	if (count > 42) {
 88 e4464189 2020-09-20 stsp 		dump_atoms(d, atom, 20);
 89 e4464189 2020-09-20 stsp 		print("[%u lines skipped]\n", count - 20 - 20);
 90 e4464189 2020-09-20 stsp 		dump_atoms(d, atom + count - 20, 20);
 91 e4464189 2020-09-20 stsp 		return;
 92 e4464189 2020-09-20 stsp 	} else {
 93 e4464189 2020-09-20 stsp 		struct diff_atom *i;
 94 e4464189 2020-09-20 stsp 		foreach_diff_atom(i, atom, count) {
 95 e4464189 2020-09-20 stsp 			dump_atom(d, NULL, i);
 96 e4464189 2020-09-20 stsp 		}
 97 e4464189 2020-09-20 stsp 	}
 98 e4464189 2020-09-20 stsp }
 99 e4464189 2020-09-20 stsp 
100 e4464189 2020-09-20 stsp static inline void
101 e4464189 2020-09-20 stsp dump(struct diff_data *d)
102 e4464189 2020-09-20 stsp {
103 e4464189 2020-09-20 stsp 	dump_atoms(d, d->atoms.head, d->atoms.len);
104 e4464189 2020-09-20 stsp }
105 e4464189 2020-09-20 stsp 
106 e4464189 2020-09-20 stsp /* kd is a quadratic space myers matrix from the original Myers algorithm.
107 e4464189 2020-09-20 stsp  * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
108 e4464189 2020-09-20 stsp  * Divide algorithm.
109 e4464189 2020-09-20 stsp  */
110 e4464189 2020-09-20 stsp static inline void
111 e4464189 2020-09-20 stsp dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
112 e4464189 2020-09-20 stsp 		 int *kd, int *kd_forward, int kd_forward_d,
113 e4464189 2020-09-20 stsp 		 int *kd_backward, int kd_backward_d)
114 e4464189 2020-09-20 stsp {
115 e4464189 2020-09-20 stsp 	#define COLOR_YELLOW "\033[1;33m"
116 e4464189 2020-09-20 stsp 	#define COLOR_GREEN "\033[1;32m"
117 e4464189 2020-09-20 stsp 	#define COLOR_BLUE "\033[1;34m"
118 e4464189 2020-09-20 stsp 	#define COLOR_RED "\033[1;31m"
119 e4464189 2020-09-20 stsp 	#define COLOR_END "\033[0;m"
120 e4464189 2020-09-20 stsp 	int x;
121 e4464189 2020-09-20 stsp 	int y;
122 e4464189 2020-09-20 stsp 	print("   ");
123 e4464189 2020-09-20 stsp 	for (x = 0; x <= l->atoms.len; x++)
124 e4464189 2020-09-20 stsp 		print("%2d", x % 100);
125 e4464189 2020-09-20 stsp 	print("\n");
126 e4464189 2020-09-20 stsp 
127 e4464189 2020-09-20 stsp 	for (y = 0; y <= r->atoms.len; y++) {
128 e4464189 2020-09-20 stsp 		print("%3d ", y);
129 e4464189 2020-09-20 stsp 		for (x = 0; x <= l->atoms.len; x++) {
130 e4464189 2020-09-20 stsp 
131 e4464189 2020-09-20 stsp 			/* print d advancements from kd, if any. */
132 e4464189 2020-09-20 stsp 			char label = 'o';
133 e4464189 2020-09-20 stsp 			char *color = NULL;
134 e4464189 2020-09-20 stsp 			if (kd) {
135 e4464189 2020-09-20 stsp 				int max = l->atoms.len + r->atoms.len;
136 e4464189 2020-09-20 stsp 				size_t kd_len = max + 1 + max;
137 e4464189 2020-09-20 stsp 				int *kd_pos = kd;
138 e4464189 2020-09-20 stsp 				int di;
139 e4464189 2020-09-20 stsp #define xk_to_y(X, K) ((X) - (K))
140 e4464189 2020-09-20 stsp 				for (di = 0; di < max; di++) {
141 e4464189 2020-09-20 stsp 					int ki;
142 e4464189 2020-09-20 stsp 					for (ki = di; ki >= -di; ki -= 2) {
143 e4464189 2020-09-20 stsp 						if (x != kd_pos[ki]
144 e4464189 2020-09-20 stsp 						    || y != xk_to_y(x, ki))
145 e4464189 2020-09-20 stsp 							continue;
146 e4464189 2020-09-20 stsp 						label = '0' + (di % 10);
147 e4464189 2020-09-20 stsp 						color = COLOR_YELLOW;
148 e4464189 2020-09-20 stsp 						break;
149 e4464189 2020-09-20 stsp 					}
150 e4464189 2020-09-20 stsp 					if (label != 'o')
151 e4464189 2020-09-20 stsp 						break;
152 e4464189 2020-09-20 stsp 					kd_pos += kd_len;
153 e4464189 2020-09-20 stsp 				}
154 e4464189 2020-09-20 stsp 			}
155 e4464189 2020-09-20 stsp 			if (kd_forward && kd_forward_d >= 0) {
156 e4464189 2020-09-20 stsp #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
157 e4464189 2020-09-20 stsp 				int ki;
158 e4464189 2020-09-20 stsp 				for (ki = kd_forward_d;
159 e4464189 2020-09-20 stsp 				     ki >= -kd_forward_d;
160 e4464189 2020-09-20 stsp 				     ki -= 2) {
161 e4464189 2020-09-20 stsp 					if (x != kd_forward[ki])
162 e4464189 2020-09-20 stsp 						continue;
163 e4464189 2020-09-20 stsp 					if (y != xk_to_y(x, ki))
164 e4464189 2020-09-20 stsp 						continue;
165 e4464189 2020-09-20 stsp 					label = 'F';
166 e4464189 2020-09-20 stsp 					color = COLOR_GREEN;
167 e4464189 2020-09-20 stsp 					break;
168 e4464189 2020-09-20 stsp 				}
169 e4464189 2020-09-20 stsp 			}
170 e4464189 2020-09-20 stsp 			if (kd_backward && kd_backward_d >= 0) {
171 e4464189 2020-09-20 stsp 				int delta = (int)r->atoms.len
172 e4464189 2020-09-20 stsp 					    - (int)l->atoms.len;
173 e4464189 2020-09-20 stsp 				int ki;
174 e4464189 2020-09-20 stsp 				for (ki = kd_backward_d;
175 e4464189 2020-09-20 stsp 				     ki >= -kd_backward_d;
176 e4464189 2020-09-20 stsp 				     ki -= 2) {
177 e4464189 2020-09-20 stsp 					if (x != kd_backward[ki])
178 e4464189 2020-09-20 stsp 						continue;
179 e4464189 2020-09-20 stsp 					if (y != xc_to_y(x, ki, delta))
180 e4464189 2020-09-20 stsp 						continue;
181 e4464189 2020-09-20 stsp 					if (label == 'o') {
182 e4464189 2020-09-20 stsp 						label = 'B';
183 e4464189 2020-09-20 stsp 						color = COLOR_BLUE;
184 e4464189 2020-09-20 stsp 					} else {
185 e4464189 2020-09-20 stsp 						label = 'X';
186 e4464189 2020-09-20 stsp 						color = COLOR_RED;
187 e4464189 2020-09-20 stsp 					}
188 e4464189 2020-09-20 stsp 					break;
189 e4464189 2020-09-20 stsp 				}
190 e4464189 2020-09-20 stsp 			}
191 e4464189 2020-09-20 stsp 			if (color)
192 e4464189 2020-09-20 stsp 				print("%s", color);
193 e4464189 2020-09-20 stsp 			print("%c", label);
194 e4464189 2020-09-20 stsp 			if (color)
195 e4464189 2020-09-20 stsp 				print("%s", COLOR_END);
196 e4464189 2020-09-20 stsp 			if (x < l->atoms.len)
197 e4464189 2020-09-20 stsp 				print("-");
198 e4464189 2020-09-20 stsp 		}
199 e4464189 2020-09-20 stsp 		print("\n");
200 e4464189 2020-09-20 stsp 		if (y == r->atoms.len)
201 e4464189 2020-09-20 stsp 			break;
202 e4464189 2020-09-20 stsp 
203 e4464189 2020-09-20 stsp 		print("    ");
204 e4464189 2020-09-20 stsp 		for (x = 0; x < l->atoms.len; x++) {
205 2a1b94d0 2020-09-26 stsp 			bool same;
206 2a1b94d0 2020-09-26 stsp 			diff_atom_same(&same, &l->atoms.head[x],
207 2a1b94d0 2020-09-26 stsp 			    &r->atoms.head[y]);
208 2a1b94d0 2020-09-26 stsp 			if (same)
209 e4464189 2020-09-20 stsp 				print("|\\");
210 e4464189 2020-09-20 stsp 			else
211 e4464189 2020-09-20 stsp 				print("| ");
212 e4464189 2020-09-20 stsp 		}
213 e4464189 2020-09-20 stsp 		print("|\n");
214 e4464189 2020-09-20 stsp 	}
215 e4464189 2020-09-20 stsp }
216 e4464189 2020-09-20 stsp 
217 e4464189 2020-09-20 stsp static inline void
218 e4464189 2020-09-20 stsp debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
219 e4464189 2020-09-20 stsp 		       int *kd, int *kd_forward, int kd_forward_d,
220 e4464189 2020-09-20 stsp 		       int *kd_backward, int kd_backward_d)
221 e4464189 2020-09-20 stsp {
222 e4464189 2020-09-20 stsp 	if (l->atoms.len > 99 || r->atoms.len > 99)
223 e4464189 2020-09-20 stsp 		return;
224 e4464189 2020-09-20 stsp 	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
225 e4464189 2020-09-20 stsp 			 kd_backward, kd_backward_d);
226 e4464189 2020-09-20 stsp }
227 e4464189 2020-09-20 stsp 
228 e4464189 2020-09-20 stsp #else
229 e4464189 2020-09-20 stsp #define debug(args...)
230 e4464189 2020-09-20 stsp #define debug_dump(args...)
231 e4464189 2020-09-20 stsp #define debug_dump_atom(args...)
232 e4464189 2020-09-20 stsp #define debug_dump_atoms(args...)
233 e4464189 2020-09-20 stsp #define debug_dump_myers_graph(args...)
234 e4464189 2020-09-20 stsp #endif