op public repos

Blame

Date:: Tue Nov 10 22:54:37 2020 UTC
Message:: merge new diff implementation from the git.gameoftrees.org diff.git repository This new diff implementation was started by Neels Hofmeyr during the u2k20 hackathon and now replaces diffreg.c code lifted from the OpenBSD base system. The integration of this code into Got was done by me. Got now uses the patience diff algorithm by default. The diff.git repository will remain the primary repository for the diff code, which already compiles and runs on other operating systems such as Linux. Any fixes and improvements for files inherited from the diff.git repository should be written against that repository and synced to got.git afterwards.
Actions:: History | Blob | Raw File
  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 == -1)
 62 fe621944 2020-11-10 stsp 				abort(); /* cannot return error */
 63 fe621944 2020-11-10 stsp 			if (r == 0)
 64 fe621944 2020-11-10 stsp 				break;
 65 fe621944 2020-11-10 stsp 			remain -= r;
 66 fe621944 2020-11-10 stsp 			for (i = 0; i < r; i++)
 67 fe621944 2020-11-10 stsp 				print_atom_byte(buf[i]);
 68 fe621944 2020-11-10 stsp 		}
 69 fe621944 2020-11-10 stsp 	} else {
 70 fe621944 2020-11-10 stsp 		const char *s;
 71 fe621944 2020-11-10 stsp 		for (s = atom->at; s < (const char*)(atom->at + atom->len); s++)
 72 fe621944 2020-11-10 stsp 			print_atom_byte(*s);
 73 fe621944 2020-11-10 stsp 	}
 74 fe621944 2020-11-10 stsp 	print("'\n");
 75 fe621944 2020-11-10 stsp }
 76 fe621944 2020-11-10 stsp 
 77 fe621944 2020-11-10 stsp static inline void
 78 fe621944 2020-11-10 stsp dump_atoms(const struct diff_data *d, struct diff_atom *atom,
 79 fe621944 2020-11-10 stsp 	   unsigned int count)
 80 fe621944 2020-11-10 stsp {
 81 fe621944 2020-11-10 stsp 	if (count > 42) {
 82 fe621944 2020-11-10 stsp 		dump_atoms(d, atom, 20);
 83 fe621944 2020-11-10 stsp 		print("[%u lines skipped]\n", count - 20 - 20);
 84 fe621944 2020-11-10 stsp 		dump_atoms(d, atom + count - 20, 20);
 85 fe621944 2020-11-10 stsp 		return;
 86 fe621944 2020-11-10 stsp 	} else {
 87 fe621944 2020-11-10 stsp 		struct diff_atom *i;
 88 fe621944 2020-11-10 stsp 		foreach_diff_atom(i, atom, count) {
 89 fe621944 2020-11-10 stsp 			dump_atom(d, NULL, i);
 90 fe621944 2020-11-10 stsp 		}
 91 fe621944 2020-11-10 stsp 	}
 92 fe621944 2020-11-10 stsp }
 93 fe621944 2020-11-10 stsp 
 94 fe621944 2020-11-10 stsp static inline void
 95 fe621944 2020-11-10 stsp dump(struct diff_data *d)
 96 fe621944 2020-11-10 stsp {
 97 fe621944 2020-11-10 stsp 	dump_atoms(d, d->atoms.head, d->atoms.len);
 98 fe621944 2020-11-10 stsp }
 99 fe621944 2020-11-10 stsp 
100 fe621944 2020-11-10 stsp /* kd is a quadratic space myers matrix from the original Myers algorithm.
101 fe621944 2020-11-10 stsp  * kd_forward and kd_backward are linear slices of a myers matrix from the Myers
102 fe621944 2020-11-10 stsp  * Divide algorithm.
103 fe621944 2020-11-10 stsp  */
104 fe621944 2020-11-10 stsp static inline void
105 fe621944 2020-11-10 stsp dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
106 fe621944 2020-11-10 stsp 		 int *kd, int *kd_forward, int kd_forward_d,
107 fe621944 2020-11-10 stsp 		 int *kd_backward, int kd_backward_d)
108 fe621944 2020-11-10 stsp {
109 fe621944 2020-11-10 stsp 	#define COLOR_YELLOW "\033[1;33m"
110 fe621944 2020-11-10 stsp 	#define COLOR_GREEN "\033[1;32m"
111 fe621944 2020-11-10 stsp 	#define COLOR_BLUE "\033[1;34m"
112 fe621944 2020-11-10 stsp 	#define COLOR_RED "\033[1;31m"
113 fe621944 2020-11-10 stsp 	#define COLOR_END "\033[0;m"
114 fe621944 2020-11-10 stsp 	int x;
115 fe621944 2020-11-10 stsp 	int y;
116 fe621944 2020-11-10 stsp 	print("   ");
117 fe621944 2020-11-10 stsp 	for (x = 0; x <= l->atoms.len; x++)
118 fe621944 2020-11-10 stsp 		print("%2d", x % 100);
119 fe621944 2020-11-10 stsp 	print("\n");
120 fe621944 2020-11-10 stsp 
121 fe621944 2020-11-10 stsp 	for (y = 0; y <= r->atoms.len; y++) {
122 fe621944 2020-11-10 stsp 		print("%3d ", y);
123 fe621944 2020-11-10 stsp 		for (x = 0; x <= l->atoms.len; x++) {
124 fe621944 2020-11-10 stsp 
125 fe621944 2020-11-10 stsp 			/* print d advancements from kd, if any. */
126 fe621944 2020-11-10 stsp 			char label = 'o';
127 fe621944 2020-11-10 stsp 			char *color = NULL;
128 fe621944 2020-11-10 stsp 			if (kd) {
129 fe621944 2020-11-10 stsp 				int max = l->atoms.len + r->atoms.len;
130 fe621944 2020-11-10 stsp 				size_t kd_len = max + 1 + max;
131 fe621944 2020-11-10 stsp 				int *kd_pos = kd;
132 fe621944 2020-11-10 stsp 				int di;
133 fe621944 2020-11-10 stsp #define xk_to_y(X, K) ((X) - (K))
134 fe621944 2020-11-10 stsp 				for (di = 0; di < max; di++) {
135 fe621944 2020-11-10 stsp 					int ki;
136 fe621944 2020-11-10 stsp 					for (ki = di; ki >= -di; ki -= 2) {
137 fe621944 2020-11-10 stsp 						if (x != kd_pos[ki]
138 fe621944 2020-11-10 stsp 						    || y != xk_to_y(x, ki))
139 fe621944 2020-11-10 stsp 							continue;
140 fe621944 2020-11-10 stsp 						label = '0' + (di % 10);
141 fe621944 2020-11-10 stsp 						color = COLOR_YELLOW;
142 fe621944 2020-11-10 stsp 						break;
143 fe621944 2020-11-10 stsp 					}
144 fe621944 2020-11-10 stsp 					if (label != 'o')
145 fe621944 2020-11-10 stsp 						break;
146 fe621944 2020-11-10 stsp 					kd_pos += kd_len;
147 fe621944 2020-11-10 stsp 				}
148 fe621944 2020-11-10 stsp 			}
149 fe621944 2020-11-10 stsp 			if (kd_forward && kd_forward_d >= 0) {
150 fe621944 2020-11-10 stsp #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))
151 fe621944 2020-11-10 stsp 				int ki;
152 fe621944 2020-11-10 stsp 				for (ki = kd_forward_d;
153 fe621944 2020-11-10 stsp 				     ki >= -kd_forward_d;
154 fe621944 2020-11-10 stsp 				     ki -= 2) {
155 fe621944 2020-11-10 stsp 					if (x != kd_forward[ki])
156 fe621944 2020-11-10 stsp 						continue;
157 fe621944 2020-11-10 stsp 					if (y != xk_to_y(x, ki))
158 fe621944 2020-11-10 stsp 						continue;
159 fe621944 2020-11-10 stsp 					label = 'F';
160 fe621944 2020-11-10 stsp 					color = COLOR_GREEN;
161 fe621944 2020-11-10 stsp 					break;
162 fe621944 2020-11-10 stsp 				}
163 fe621944 2020-11-10 stsp 			}
164 fe621944 2020-11-10 stsp 			if (kd_backward && kd_backward_d >= 0) {
165 fe621944 2020-11-10 stsp 				int delta = (int)r->atoms.len
166 fe621944 2020-11-10 stsp 					    - (int)l->atoms.len;
167 fe621944 2020-11-10 stsp 				int ki;
168 fe621944 2020-11-10 stsp 				for (ki = kd_backward_d;
169 fe621944 2020-11-10 stsp 				     ki >= -kd_backward_d;
170 fe621944 2020-11-10 stsp 				     ki -= 2) {
171 fe621944 2020-11-10 stsp 					if (x != kd_backward[ki])
172 fe621944 2020-11-10 stsp 						continue;
173 fe621944 2020-11-10 stsp 					if (y != xc_to_y(x, ki, delta))
174 fe621944 2020-11-10 stsp 						continue;
175 fe621944 2020-11-10 stsp 					if (label == 'o') {
176 fe621944 2020-11-10 stsp 						label = 'B';
177 fe621944 2020-11-10 stsp 						color = COLOR_BLUE;
178 fe621944 2020-11-10 stsp 					} else {
179 fe621944 2020-11-10 stsp 						label = 'X';
180 fe621944 2020-11-10 stsp 						color = COLOR_RED;
181 fe621944 2020-11-10 stsp 					}
182 fe621944 2020-11-10 stsp 					break;
183 fe621944 2020-11-10 stsp 				}
184 fe621944 2020-11-10 stsp 			}
185 fe621944 2020-11-10 stsp 			if (color)
186 fe621944 2020-11-10 stsp 				print("%s", color);
187 fe621944 2020-11-10 stsp 			print("%c", label);
188 fe621944 2020-11-10 stsp 			if (color)
189 fe621944 2020-11-10 stsp 				print("%s", COLOR_END);
190 fe621944 2020-11-10 stsp 			if (x < l->atoms.len)
191 fe621944 2020-11-10 stsp 				print("-");
192 fe621944 2020-11-10 stsp 		}
193 fe621944 2020-11-10 stsp 		print("\n");
194 fe621944 2020-11-10 stsp 		if (y == r->atoms.len)
195 fe621944 2020-11-10 stsp 			break;
196 fe621944 2020-11-10 stsp 
197 fe621944 2020-11-10 stsp 		print("    ");
198 fe621944 2020-11-10 stsp 		for (x = 0; x < l->atoms.len; x++) {
199 fe621944 2020-11-10 stsp 			bool same;
200 fe621944 2020-11-10 stsp 			diff_atom_same(&same, &l->atoms.head[x],
201 fe621944 2020-11-10 stsp 			    &r->atoms.head[y]);
202 fe621944 2020-11-10 stsp 			if (same)
203 fe621944 2020-11-10 stsp 				print("|\\");
204 fe621944 2020-11-10 stsp 			else
205 fe621944 2020-11-10 stsp 				print("| ");
206 fe621944 2020-11-10 stsp 		}
207 fe621944 2020-11-10 stsp 		print("|\n");
208 fe621944 2020-11-10 stsp 	}
209 fe621944 2020-11-10 stsp }
210 fe621944 2020-11-10 stsp 
211 fe621944 2020-11-10 stsp static inline void
212 fe621944 2020-11-10 stsp debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,
213 fe621944 2020-11-10 stsp 		       int *kd, int *kd_forward, int kd_forward_d,
214 fe621944 2020-11-10 stsp 		       int *kd_backward, int kd_backward_d)
215 fe621944 2020-11-10 stsp {
216 fe621944 2020-11-10 stsp 	if (l->atoms.len > 99 || r->atoms.len > 99)
217 fe621944 2020-11-10 stsp 		return;
218 fe621944 2020-11-10 stsp 	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d,
219 fe621944 2020-11-10 stsp 			 kd_backward, kd_backward_d);
220 fe621944 2020-11-10 stsp }
221 fe621944 2020-11-10 stsp 
222 fe621944 2020-11-10 stsp #else
223 fe621944 2020-11-10 stsp #define debug(args...)
224 fe621944 2020-11-10 stsp #define debug_dump(args...)
225 fe621944 2020-11-10 stsp #define debug_dump_atom(args...)
226 fe621944 2020-11-10 stsp #define debug_dump_atoms(args...)
227 fe621944 2020-11-10 stsp #define debug_dump_myers_graph(args...)
228 fe621944 2020-11-10 stsp #endif