1 fe621944 2020-11-10 stsp /*
  2 fe621944 2020-11-10 stsp  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  3 fe621944 2020-11-10 stsp  *
  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.
  7 fe621944 2020-11-10 stsp  *
  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.
 15 fe621944 2020-11-10 stsp  */
 16 fe621944 2020-11-10 stsp 
 17 fe621944 2020-11-10 stsp #define DEBUG 0
 18 fe621944 2020-11-10 stsp 
 19 fe621944 2020-11-10 stsp #if DEBUG
 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
 27 fe621944 2020-11-10 stsp 
 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);
 36 fe621944 2020-11-10 stsp 	else
 37 fe621944 2020-11-10 stsp 		print("%c", c);
 38 fe621944 2020-11-10 stsp }
 39 fe621944 2020-11-10 stsp 
 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)
 43 fe621944 2020-11-10 stsp {
 44 fe621944 2020-11-10 stsp 	if (!atom) {
 45 fe621944 2020-11-10 stsp 		print("NULL atom\n");
 46 fe621944 2020-11-10 stsp 		return;
 47 fe621944 2020-11-10 stsp 	}
 48 fe621944 2020-11-10 stsp 	if (left)
 49 fe621944 2020-11-10 stsp 		print(" %3u '", diff_atom_root_idx(left, atom));
 50 fe621944 2020-11-10 stsp 
 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];
 57 fe621944 2020-11-10 stsp 			size_t r;
 58 fe621944 2020-11-10 stsp 			int i;
 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 == 0)
 62 fe621944 2020-11-10 stsp 				break;
 63 fe621944 2020-11-10 stsp 			remain -= r;
 64 fe621944 2020-11-10 stsp 			for (i = 0; i < r; i++)
 65 fe621944 2020-11-10 stsp 				print_atom_byte(buf[i]);
 66 fe621944 2020-11-10 stsp 		}
 67 fe621944 2020-11-10 stsp 	} else {
 68 fe621944 2020-11-10 stsp 		const char *s;
 69 fe621944 2020-11-10 stsp 		for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
 70 fe621944 2020-11-10 stsp 			print_atom_byte(*s);
 71 fe621944 2020-11-10 stsp 	}
 72 fe621944 2020-11-10 stsp 	print("'\n");
 73 fe621944 2020-11-10 stsp }
 74 fe621944 2020-11-10 stsp 
 75 fe621944 2020-11-10 stsp static inline void
 76 fe621944 2020-11-10 stsp dump_atoms(const struct diff_data *d, struct diff_atom *atom,
 77 fe621944 2020-11-10 stsp 	   unsigned int count)
 78 fe621944 2020-11-10 stsp {
 79 fe621944 2020-11-10 stsp 	if (count > 42) {
 80 fe621944 2020-11-10 stsp 		dump_atoms(d, atom, 20);
 81 fe621944 2020-11-10 stsp 		print("[%u lines skipped]\n", count - 20 - 20);
 82 fe621944 2020-11-10 stsp 		dump_atoms(d, atom + count - 20, 20);
 83 fe621944 2020-11-10 stsp 		return;
 84 fe621944 2020-11-10 stsp 	} else {
 85 fe621944 2020-11-10 stsp 		struct diff_atom *i;
 86 fe621944 2020-11-10 stsp 		foreach_diff_atom(i, atom, count) {
 87 fe621944 2020-11-10 stsp 			dump_atom(d, NULL, i);
 88 fe621944 2020-11-10 stsp 		}
 89 fe621944 2020-11-10 stsp 	}
 90 fe621944 2020-11-10 stsp }
 91 fe621944 2020-11-10 stsp 
 92 fe621944 2020-11-10 stsp static inline void
 93 fe621944 2020-11-10 stsp dump(struct diff_data *d)
 94 fe621944 2020-11-10 stsp {
 95 fe621944 2020-11-10 stsp 	dump_atoms(d, d->atoms.head, d->atoms.len);
 96 fe621944 2020-11-10 stsp }
 97 fe621944 2020-11-10 stsp 
 98 fe621944 2020-11-10 stsp /* kd is a quadratic space myers matrix from the original Myers algorithm.
 99 fe621944 2020-11-10 stsp  * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
100 fe621944 2020-11-10 stsp  * Divide algorithm.
101 fe621944 2020-11-10 stsp  */
102 fe621944 2020-11-10 stsp static inline void
103 fe621944 2020-11-10 stsp dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
104 fe621944 2020-11-10 stsp 		 int *kd, int *kd_forward, int kd_forward_d,
105 fe621944 2020-11-10 stsp 		 int *kd_backward, int kd_backward_d)
106 fe621944 2020-11-10 stsp {
107 fe621944 2020-11-10 stsp 	#define COLOR_YELLOW "\033[1;33m"
108 fe621944 2020-11-10 stsp 	#define COLOR_GREEN "\033[1;32m"
109 fe621944 2020-11-10 stsp 	#define COLOR_BLUE "\033[1;34m"
110 fe621944 2020-11-10 stsp 	#define COLOR_RED "\033[1;31m"
111 fe621944 2020-11-10 stsp 	#define COLOR_END "\033[0;m"
112 fe621944 2020-11-10 stsp 	int x;
113 fe621944 2020-11-10 stsp 	int y;
114 fe621944 2020-11-10 stsp 	print("   ");
115 fe621944 2020-11-10 stsp 	for (x = 0; x <= l->atoms.len; x++)
116 fe621944 2020-11-10 stsp 		print("%2d", x % 100);
117 fe621944 2020-11-10 stsp 	print("\n");
118 fe621944 2020-11-10 stsp 
119 fe621944 2020-11-10 stsp 	for (y = 0; y <= r->atoms.len; y++) {
120 fe621944 2020-11-10 stsp 		print("%3d ", y);
121 fe621944 2020-11-10 stsp 		for (x = 0; x <= l->atoms.len; x++) {
122 fe621944 2020-11-10 stsp 
123 fe621944 2020-11-10 stsp 			/* print d advancements from kd, if any. */
124 fe621944 2020-11-10 stsp 			char label = 'o';
125 fe621944 2020-11-10 stsp 			char *color = NULL;
126 fe621944 2020-11-10 stsp 			if (kd) {
127 fe621944 2020-11-10 stsp 				int max = l->atoms.len + r->atoms.len;
128 fe621944 2020-11-10 stsp 				size_t kd_len = max + 1 + max;
129 fe621944 2020-11-10 stsp 				int *kd_pos = kd;
130 fe621944 2020-11-10 stsp 				int di;
131 fe621944 2020-11-10 stsp #define xk_to_y(X, K) ((X) - (K))
132 fe621944 2020-11-10 stsp 				for (di = 0; di < max; di++) {
133 fe621944 2020-11-10 stsp 					int ki;
134 fe621944 2020-11-10 stsp 					for (ki = di; ki >= -di; ki -= 2) {
135 fe621944 2020-11-10 stsp 						if (x != kd_pos[ki]
136 fe621944 2020-11-10 stsp 						    || y != xk_to_y(x, ki))
137 fe621944 2020-11-10 stsp 							continue;
138 fe621944 2020-11-10 stsp 						label = '0' + (di % 10);
139 fe621944 2020-11-10 stsp 						color = COLOR_YELLOW;
140 fe621944 2020-11-10 stsp 						break;
141 fe621944 2020-11-10 stsp 					}
142 fe621944 2020-11-10 stsp 					if (label != 'o')
143 fe621944 2020-11-10 stsp 						break;
144 fe621944 2020-11-10 stsp 					kd_pos += kd_len;
145 fe621944 2020-11-10 stsp 				}
146 fe621944 2020-11-10 stsp 			}
147 fe621944 2020-11-10 stsp 			if (kd_forward && kd_forward_d >= 0) {
148 fe621944 2020-11-10 stsp #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
149 fe621944 2020-11-10 stsp 				int ki;
150 fe621944 2020-11-10 stsp 				for (ki = kd_forward_d;
151 fe621944 2020-11-10 stsp 				     ki >= -kd_forward_d;
152 fe621944 2020-11-10 stsp 				     ki -= 2) {
153 fe621944 2020-11-10 stsp 					if (x != kd_forward[ki])
154 fe621944 2020-11-10 stsp 						continue;
155 fe621944 2020-11-10 stsp 					if (y != xk_to_y(x, ki))
156 fe621944 2020-11-10 stsp 						continue;
157 fe621944 2020-11-10 stsp 					label = 'F';
158 fe621944 2020-11-10 stsp 					color = COLOR_GREEN;
159 fe621944 2020-11-10 stsp 					break;
160 fe621944 2020-11-10 stsp 				}
161 fe621944 2020-11-10 stsp 			}
162 fe621944 2020-11-10 stsp 			if (kd_backward && kd_backward_d >= 0) {
163 fe621944 2020-11-10 stsp 				int delta = (int)r->atoms.len
164 fe621944 2020-11-10 stsp 					    - (int)l->atoms.len;
165 fe621944 2020-11-10 stsp 				int ki;
166 fe621944 2020-11-10 stsp 				for (ki = kd_backward_d;
167 fe621944 2020-11-10 stsp 				     ki >= -kd_backward_d;
168 fe621944 2020-11-10 stsp 				     ki -= 2) {
169 fe621944 2020-11-10 stsp 					if (x != kd_backward[ki])
170 fe621944 2020-11-10 stsp 						continue;
171 fe621944 2020-11-10 stsp 					if (y != xc_to_y(x, ki, delta))
172 fe621944 2020-11-10 stsp 						continue;
173 fe621944 2020-11-10 stsp 					if (label == 'o') {
174 fe621944 2020-11-10 stsp 						label = 'B';
175 fe621944 2020-11-10 stsp 						color = COLOR_BLUE;
176 fe621944 2020-11-10 stsp 					} else {
177 fe621944 2020-11-10 stsp 						label = 'X';
178 fe621944 2020-11-10 stsp 						color = COLOR_RED;
179 fe621944 2020-11-10 stsp 					}
180 fe621944 2020-11-10 stsp 					break;
181 fe621944 2020-11-10 stsp 				}
182 fe621944 2020-11-10 stsp 			}
183 fe621944 2020-11-10 stsp 			if (color)
184 fe621944 2020-11-10 stsp 				print("%s", color);
185 fe621944 2020-11-10 stsp 			print("%c", label);
186 fe621944 2020-11-10 stsp 			if (color)
187 fe621944 2020-11-10 stsp 				print("%s", COLOR_END);
188 fe621944 2020-11-10 stsp 			if (x < l->atoms.len)
189 fe621944 2020-11-10 stsp 				print("-");
190 fe621944 2020-11-10 stsp 		}
191 fe621944 2020-11-10 stsp 		print("\n");
192 fe621944 2020-11-10 stsp 		if (y == r->atoms.len)
193 fe621944 2020-11-10 stsp 			break;
194 fe621944 2020-11-10 stsp 
195 fe621944 2020-11-10 stsp 		print("    ");
196 fe621944 2020-11-10 stsp 		for (x = 0; x < l->atoms.len; x++) {
197 fe621944 2020-11-10 stsp 			bool same;
198 fe621944 2020-11-10 stsp 			diff_atom_same(&same, &l->atoms.head[x],
199 fe621944 2020-11-10 stsp 			    &r->atoms.head[y]);
200 fe621944 2020-11-10 stsp 			if (same)
201 fe621944 2020-11-10 stsp 				print("|\\");
202 fe621944 2020-11-10 stsp 			else
203 fe621944 2020-11-10 stsp 				print("| ");
204 fe621944 2020-11-10 stsp 		}
205 fe621944 2020-11-10 stsp 		print("|\n");
206 fe621944 2020-11-10 stsp 	}
207 fe621944 2020-11-10 stsp }
208 fe621944 2020-11-10 stsp 
209 fe621944 2020-11-10 stsp static inline void
210 fe621944 2020-11-10 stsp debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
211 fe621944 2020-11-10 stsp 		       int *kd, int *kd_forward, int kd_forward_d,
212 fe621944 2020-11-10 stsp 		       int *kd_backward, int kd_backward_d)
213 fe621944 2020-11-10 stsp {
214 fe621944 2020-11-10 stsp 	if (l->atoms.len > 99 || r->atoms.len > 99)
215 fe621944 2020-11-10 stsp 		return;
216 fe621944 2020-11-10 stsp 	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
217 fe621944 2020-11-10 stsp 			 kd_backward, kd_backward_d);
218 fe621944 2020-11-10 stsp }
219 fe621944 2020-11-10 stsp 
220 fe621944 2020-11-10 stsp #else
221 fe621944 2020-11-10 stsp #define debug(args...)
222 fe621944 2020-11-10 stsp #define debug_dump(args...)
223 fe621944 2020-11-10 stsp #define debug_dump_atom(args...)
224 fe621944 2020-11-10 stsp #define debug_dump_atoms(args...)
225 fe621944 2020-11-10 stsp #define debug_dump_myers_graph(args...)
226 fe621944 2020-11-10 stsp #endif