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