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