1 3b0f3d61 2020-01-22 neels /*
  2 3b0f3d61 2020-01-22 neels  * Copyright (c) 2020 Neels Hofmeyr <neels@hofmeyr.de>
  3 3b0f3d61 2020-01-22 neels  *
  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.
  7 3b0f3d61 2020-01-22 neels  *
  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.
 15 3b0f3d61 2020-01-22 neels  */
 16 3b0f3d61 2020-01-22 neels 
 17 3b0f3d61 2020-01-22 neels #pragma once
 18 3b0f3d61 2020-01-22 neels 
 19 3b0f3d61 2020-01-22 neels #define DEBUG 0
 20 3b0f3d61 2020-01-22 neels 
 21 3b0f3d61 2020-01-22 neels #if DEBUG
 22 3b0f3d61 2020-01-22 neels #include <stdio.h>
 23 3b0f3d61 2020-01-22 neels #define print(args...) fprintf(stderr, ##args)
 24 3b0f3d61 2020-01-22 neels #define debug print
 25 3b0f3d61 2020-01-22 neels #define debug_dump dump
 26 3b0f3d61 2020-01-22 neels #define debug_dump_atom dump_atom
 27 3b0f3d61 2020-01-22 neels #define debug_dump_atoms dump_atoms
 28 3b0f3d61 2020-01-22 neels 
 29 61a7b578 2020-05-06 neels static inline void
 30 61a7b578 2020-05-06 neels dump_atom(const struct diff_data *left, const struct diff_data *right, const struct diff_atom *atom)
 31 3b0f3d61 2020-01-22 neels {
 32 3b0f3d61 2020-01-22 neels 	if (!atom) {
 33 3b0f3d61 2020-01-22 neels 		print("NULL atom\n");
 34 3b0f3d61 2020-01-22 neels 		return;
 35 3b0f3d61 2020-01-22 neels 	}
 36 3b0f3d61 2020-01-22 neels 	if (left)
 37 3b0f3d61 2020-01-22 neels 		print(" %3ld", diff_atom_root_idx(left, atom));
 38 3b0f3d61 2020-01-22 neels 	if (right && atom->patience.pos_in_other)
 39 3b0f3d61 2020-01-22 neels 		print(" %3ld", diff_atom_root_idx(right, atom->patience.pos_in_other));
 40 3b0f3d61 2020-01-22 neels 
 41 3b0f3d61 2020-01-22 neels 	print(" %s%s '", atom->patience.unique_here ? "u" : " ", atom->patience.unique_in_both ? "c" : " ");
 42 3b0f3d61 2020-01-22 neels 	const char *s;
 43 3b0f3d61 2020-01-22 neels 	for (s = atom->at; s < (const char*)(atom->at + atom->len); s++) {
 44 3b0f3d61 2020-01-22 neels 		if (*s == '\r')
 45 3b0f3d61 2020-01-22 neels 			print("\\r");
 46 3b0f3d61 2020-01-22 neels 		else if (*s == '\n')
 47 3b0f3d61 2020-01-22 neels 			print("\\n");
 48 fbd55577 2020-01-27 neels 		else if ((*s < 32 || *s >= 127) && (*s != '\t'))
 49 3b0f3d61 2020-01-22 neels 			print("\\x%02x", *s);
 50 3b0f3d61 2020-01-22 neels 		else
 51 3b0f3d61 2020-01-22 neels 			print("%c", *s);
 52 3b0f3d61 2020-01-22 neels 	}
 53 3b0f3d61 2020-01-22 neels 	print("'\n");
 54 3b0f3d61 2020-01-22 neels }
 55 3b0f3d61 2020-01-22 neels 
 56 61a7b578 2020-05-06 neels static inline void
 57 61a7b578 2020-05-06 neels dump_atoms(const struct diff_data *d, struct diff_atom *atom, unsigned int count)
 58 3b0f3d61 2020-01-22 neels {
 59 13b15273 2020-01-27 neels 	if (count > 42) {
 60 13b15273 2020-01-27 neels 		dump_atoms(d, atom, 20);
 61 13b15273 2020-01-27 neels 		print("[%u lines skipped]\n", count - 20 - 20);
 62 13b15273 2020-01-27 neels 		dump_atoms(d, atom + count - 20, 20);
 63 13b15273 2020-01-27 neels 		return;
 64 13b15273 2020-01-27 neels 	} else {
 65 13b15273 2020-01-27 neels 		struct diff_atom *i;
 66 13b15273 2020-01-27 neels 		foreach_diff_atom(i, atom, count) {
 67 13b15273 2020-01-27 neels 			dump_atom(d, NULL, i);
 68 13b15273 2020-01-27 neels 		}
 69 3b0f3d61 2020-01-22 neels 	}
 70 3b0f3d61 2020-01-22 neels }
 71 3b0f3d61 2020-01-22 neels 
 72 61a7b578 2020-05-06 neels static inline void
 73 61a7b578 2020-05-06 neels dump(struct diff_data *d)
 74 3b0f3d61 2020-01-22 neels {
 75 3b0f3d61 2020-01-22 neels 	dump_atoms(d, d->atoms.head, d->atoms.len);
 76 3b0f3d61 2020-01-22 neels }
 77 3b0f3d61 2020-01-22 neels 
 78 50198b5f 2020-05-05 neels /* kd is a quadratic space myers matrix from the original Myers algorithm.
 79 50198b5f 2020-05-05 neels  * kd_forward and kd_backward are linear slices of a myers matrix from the Myers Divide algorithm.
 80 50198b5f 2020-05-05 neels  */
 81 61a7b578 2020-05-06 neels static inline void
 82 61a7b578 2020-05-06 neels dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
 83 61a7b578 2020-05-06 neels 		 int *kd, int *kd_forward, int kd_forward_d, int *kd_backward, int kd_backward_d)
 84 3b0f3d61 2020-01-22 neels {
 85 50198b5f 2020-05-05 neels 	#define COLOR_YELLOW "\033[1;33m"
 86 50198b5f 2020-05-05 neels 	#define COLOR_GREEN "\033[1;32m"
 87 50198b5f 2020-05-05 neels 	#define COLOR_BLUE "\033[1;34m"
 88 50198b5f 2020-05-05 neels 	#define COLOR_RED "\033[1;31m"
 89 50198b5f 2020-05-05 neels 	#define COLOR_END "\033[0;m"
 90 3b0f3d61 2020-01-22 neels 	int x;
 91 3b0f3d61 2020-01-22 neels 	int y;
 92 50198b5f 2020-05-05 neels 	print("   ");
 93 3b0f3d61 2020-01-22 neels 	for (x = 0; x <= l->atoms.len; x++)
 94 50198b5f 2020-05-05 neels 		print("%2d", x % 100);
 95 3b0f3d61 2020-01-22 neels 	print("\n");
 96 3b0f3d61 2020-01-22 neels 
 97 3b0f3d61 2020-01-22 neels 	for (y = 0; y <= r->atoms.len; y++) {
 98 50198b5f 2020-05-05 neels 		print("%3d ", y);
 99 3b0f3d61 2020-01-22 neels 		for (x = 0; x <= l->atoms.len; x++) {
100 3b0f3d61 2020-01-22 neels 
101 3b0f3d61 2020-01-22 neels 			/* print d advancements from kd, if any. */
102 50198b5f 2020-05-05 neels 			char label = 'o';
103 50198b5f 2020-05-05 neels 			char *color = NULL;
104 3b0f3d61 2020-01-22 neels 			if (kd) {
105 3b0f3d61 2020-01-22 neels 				int max = l->atoms.len + r->atoms.len;
106 3b0f3d61 2020-01-22 neels 				size_t kd_len = max + 1 + max;
107 3b0f3d61 2020-01-22 neels 				int *kd_pos = kd;
108 3b0f3d61 2020-01-22 neels 				int di;
109 3b0f3d61 2020-01-22 neels #define xk_to_y(X, K) ((X) - (K))
110 3b0f3d61 2020-01-22 neels 				for (di = 0; di < max; di++) {
111 3b0f3d61 2020-01-22 neels 					int ki;
112 3b0f3d61 2020-01-22 neels 					for (ki = di; ki >= -di; ki -= 2) {
113 50198b5f 2020-05-05 neels 						if (x != kd_pos[ki]
114 50198b5f 2020-05-05 neels 						    || y != xk_to_y(x, ki))
115 50198b5f 2020-05-05 neels 							continue;
116 50198b5f 2020-05-05 neels 						label = '0' + (di % 10);
117 50198b5f 2020-05-05 neels 						color = COLOR_YELLOW;
118 50198b5f 2020-05-05 neels 						break;
119 3b0f3d61 2020-01-22 neels 					}
120 50198b5f 2020-05-05 neels 					if (label != 'o')
121 3b0f3d61 2020-01-22 neels 						break;
122 3b0f3d61 2020-01-22 neels 					kd_pos += kd_len;
123 3b0f3d61 2020-01-22 neels 				}
124 3b0f3d61 2020-01-22 neels 			}
125 50198b5f 2020-05-05 neels 			if (kd_forward && kd_forward_d >= 0) {
126 50198b5f 2020-05-05 neels 				int max = l->atoms.len + r->atoms.len;
127 50198b5f 2020-05-05 neels 				size_t kd_len = max + 1 + max;
128 50198b5f 2020-05-05 neels 				int di;
129 50198b5f 2020-05-05 neels #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
130 50198b5f 2020-05-05 neels 				int delta = (int)r->atoms.len - (int)l->atoms.len;
131 50198b5f 2020-05-05 neels 				int ki;
132 50198b5f 2020-05-05 neels 				for (ki = kd_forward_d; ki >= -kd_forward_d; ki -= 2) {
133 50198b5f 2020-05-05 neels 					if (x != kd_forward[ki])
134 50198b5f 2020-05-05 neels 						continue;
135 50198b5f 2020-05-05 neels 					if (y != xk_to_y(x, ki))
136 50198b5f 2020-05-05 neels 						continue;
137 50198b5f 2020-05-05 neels 					label = 'F';
138 50198b5f 2020-05-05 neels 					color = COLOR_GREEN;
139 50198b5f 2020-05-05 neels 					break;
140 50198b5f 2020-05-05 neels 				}
141 50198b5f 2020-05-05 neels 			}
142 50198b5f 2020-05-05 neels 			if (kd_backward && kd_backward_d >= 0) {
143 50198b5f 2020-05-05 neels 				int max = l->atoms.len + r->atoms.len;
144 50198b5f 2020-05-05 neels 				size_t kd_len = max + 1 + max;
145 50198b5f 2020-05-05 neels 				int di;
146 50198b5f 2020-05-05 neels 				int delta = (int)r->atoms.len - (int)l->atoms.len;
147 50198b5f 2020-05-05 neels 				int ki;
148 50198b5f 2020-05-05 neels 				for (ki = kd_backward_d; ki >= -kd_backward_d; ki -= 2) {
149 50198b5f 2020-05-05 neels 					if (x != kd_backward[ki])
150 50198b5f 2020-05-05 neels 						continue;
151 50198b5f 2020-05-05 neels 					if (y != xc_to_y(x, ki, delta))
152 50198b5f 2020-05-05 neels 						continue;
153 50198b5f 2020-05-05 neels 					if (label == 'o') {
154 50198b5f 2020-05-05 neels 						label = 'B';
155 50198b5f 2020-05-05 neels 						color = COLOR_BLUE;
156 50198b5f 2020-05-05 neels 					} else {
157 50198b5f 2020-05-05 neels 						label = 'X';
158 50198b5f 2020-05-05 neels 						color = COLOR_RED;
159 50198b5f 2020-05-05 neels 					}
160 50198b5f 2020-05-05 neels 					break;
161 50198b5f 2020-05-05 neels 				}
162 50198b5f 2020-05-05 neels 			}
163 50198b5f 2020-05-05 neels 			if (color)
164 50198b5f 2020-05-05 neels 				print("%s", color);
165 50198b5f 2020-05-05 neels 			print("%c", label);
166 50198b5f 2020-05-05 neels 			if (color)
167 50198b5f 2020-05-05 neels 				print("%s", COLOR_END);
168 50198b5f 2020-05-05 neels 			if (x < l->atoms.len)
169 3b0f3d61 2020-01-22 neels 				print("-");
170 3b0f3d61 2020-01-22 neels 		}
171 3b0f3d61 2020-01-22 neels 		print("\n");
172 3b0f3d61 2020-01-22 neels 		if (y == r->atoms.len)
173 3b0f3d61 2020-01-22 neels 			break;
174 3b0f3d61 2020-01-22 neels 
175 50198b5f 2020-05-05 neels 		print("    ");
176 3b0f3d61 2020-01-22 neels 		for (x = 0; x < l->atoms.len; x++) {
177 3b0f3d61 2020-01-22 neels 			if (diff_atom_same(&l->atoms.head[x], &r->atoms.head[y]))
178 3b0f3d61 2020-01-22 neels 				print("|\\");
179 3b0f3d61 2020-01-22 neels 			else
180 3b0f3d61 2020-01-22 neels 				print("| ");
181 3b0f3d61 2020-01-22 neels 		}
182 3b0f3d61 2020-01-22 neels 		print("|\n");
183 3b0f3d61 2020-01-22 neels 	}
184 3b0f3d61 2020-01-22 neels }
185 3b0f3d61 2020-01-22 neels 
186 61a7b578 2020-05-06 neels static inline void
187 61a7b578 2020-05-06 neels debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
188 61a7b578 2020-05-06 neels 		       int *kd, int *kd_forward, int kd_forward_d, int *kd_backward, int kd_backward_d)
189 72057b70 2020-01-27 neels {
190 72057b70 2020-01-27 neels 	if (l->atoms.len > 99 || r->atoms.len > 99)
191 72057b70 2020-01-27 neels 		return;
192 50198b5f 2020-05-05 neels 	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d, kd_backward, kd_backward_d);
193 72057b70 2020-01-27 neels }
194 72057b70 2020-01-27 neels 
195 3b0f3d61 2020-01-22 neels #else
196 3b0f3d61 2020-01-22 neels #define debug(args...)
197 3b0f3d61 2020-01-22 neels #define debug_dump(args...)
198 3b0f3d61 2020-01-22 neels #define debug_dump_atom(args...)
199 3b0f3d61 2020-01-22 neels #define debug_dump_atoms(args...)
200 3b0f3d61 2020-01-22 neels #define debug_dump_myers_graph(args...)
201 3b0f3d61 2020-01-22 neels #endif