Blame

Date:
Message:
debug: myers graph dump tweaks In debug output: fix some indents, fix printing of max state size, in myers graph, limit x axis labels to 2 digits, print colored markers of current myers graph positions, also print myers-divide positions in myers graph.
Actions:
History | Blob | Raw File
  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 3b0f3d61 2020-01-22 neels static inline void dump_atom(const struct diff_data *left, const struct diff_data *right, const struct diff_atom *atom)

 30 3b0f3d61 2020-01-22 neels {

 31 3b0f3d61 2020-01-22 neels 	if (!atom) {

 32 3b0f3d61 2020-01-22 neels 		print("NULL atom\n");

 33 3b0f3d61 2020-01-22 neels 		return;

 34 3b0f3d61 2020-01-22 neels 	}

 35 3b0f3d61 2020-01-22 neels 	if (left)

 36 3b0f3d61 2020-01-22 neels 		print(" %3ld", diff_atom_root_idx(left, atom));

 37 3b0f3d61 2020-01-22 neels 	if (right && atom->patience.pos_in_other)

 38 3b0f3d61 2020-01-22 neels 		print(" %3ld", diff_atom_root_idx(right, atom->patience.pos_in_other));

 39 3b0f3d61 2020-01-22 neels 

 40 3b0f3d61 2020-01-22 neels 	print(" %s%s '", atom->patience.unique_here ? "u" : " ", atom->patience.unique_in_both ? "c" : " ");

 41 3b0f3d61 2020-01-22 neels 	const char *s;

 42 3b0f3d61 2020-01-22 neels 	for (s = atom->at; s < (const char*)(atom->at + atom->len); s++) {

 43 3b0f3d61 2020-01-22 neels 		if (*s == '\r')

 44 3b0f3d61 2020-01-22 neels 			print("\\r");

 45 3b0f3d61 2020-01-22 neels 		else if (*s == '\n')

 46 3b0f3d61 2020-01-22 neels 			print("\\n");

 47 fbd55577 2020-01-27 neels 		else if ((*s < 32 || *s >= 127) && (*s != '\t'))

 48 3b0f3d61 2020-01-22 neels 			print("\\x%02x", *s);

 49 3b0f3d61 2020-01-22 neels 		else

 50 3b0f3d61 2020-01-22 neels 			print("%c", *s);

 51 3b0f3d61 2020-01-22 neels 	}

 52 3b0f3d61 2020-01-22 neels 	print("'\n");

 53 3b0f3d61 2020-01-22 neels }

 54 3b0f3d61 2020-01-22 neels 

 55 3b0f3d61 2020-01-22 neels static inline void dump_atoms(const struct diff_data *d, struct diff_atom *atom, unsigned int count)

 56 3b0f3d61 2020-01-22 neels {

 57 13b15273 2020-01-27 neels 	if (count > 42) {

 58 13b15273 2020-01-27 neels 		dump_atoms(d, atom, 20);

 59 13b15273 2020-01-27 neels 		print("[%u lines skipped]\n", count - 20 - 20);

 60 13b15273 2020-01-27 neels 		dump_atoms(d, atom + count - 20, 20);

 61 13b15273 2020-01-27 neels 		return;

 62 13b15273 2020-01-27 neels 	} else {

 63 13b15273 2020-01-27 neels 		struct diff_atom *i;

 64 13b15273 2020-01-27 neels 		foreach_diff_atom(i, atom, count) {

 65 13b15273 2020-01-27 neels 			dump_atom(d, NULL, i);

 66 13b15273 2020-01-27 neels 		}

 67 3b0f3d61 2020-01-22 neels 	}

 68 3b0f3d61 2020-01-22 neels }

 69 3b0f3d61 2020-01-22 neels 

 70 3b0f3d61 2020-01-22 neels static inline void dump(struct diff_data *d)

 71 3b0f3d61 2020-01-22 neels {

 72 3b0f3d61 2020-01-22 neels 	dump_atoms(d, d->atoms.head, d->atoms.len);

 73 3b0f3d61 2020-01-22 neels }

 74 3b0f3d61 2020-01-22 neels 

 75 50198b5f 2020-05-05 neels /* kd is a quadratic space myers matrix from the original Myers algorithm.

 76 50198b5f 2020-05-05 neels  * kd_forward and kd_backward are linear slices of a myers matrix from the Myers Divide algorithm.

 77 50198b5f 2020-05-05 neels  */

 78 3b0f3d61 2020-01-22 neels static inline void dump_myers_graph(const struct diff_data *l, const struct diff_data *r,

 79 50198b5f 2020-05-05 neels 				    int *kd, int *kd_forward, int kd_forward_d, int *kd_backward, int kd_backward_d)

 80 3b0f3d61 2020-01-22 neels {

 81 50198b5f 2020-05-05 neels 	#define COLOR_YELLOW "\033[1;33m"

 82 50198b5f 2020-05-05 neels 	#define COLOR_GREEN "\033[1;32m"

 83 50198b5f 2020-05-05 neels 	#define COLOR_BLUE "\033[1;34m"

 84 50198b5f 2020-05-05 neels 	#define COLOR_RED "\033[1;31m"

 85 50198b5f 2020-05-05 neels 	#define COLOR_END "\033[0;m"

 86 3b0f3d61 2020-01-22 neels 	int x;

 87 3b0f3d61 2020-01-22 neels 	int y;

 88 50198b5f 2020-05-05 neels 	print("   ");

 89 3b0f3d61 2020-01-22 neels 	for (x = 0; x <= l->atoms.len; x++)

 90 50198b5f 2020-05-05 neels 		print("%2d", x % 100);

 91 3b0f3d61 2020-01-22 neels 	print("\n");

 92 3b0f3d61 2020-01-22 neels 

 93 3b0f3d61 2020-01-22 neels 	for (y = 0; y <= r->atoms.len; y++) {

 94 50198b5f 2020-05-05 neels 		print("%3d ", y);

 95 3b0f3d61 2020-01-22 neels 		for (x = 0; x <= l->atoms.len; x++) {

 96 3b0f3d61 2020-01-22 neels 

 97 3b0f3d61 2020-01-22 neels 			/* print d advancements from kd, if any. */

 98 50198b5f 2020-05-05 neels 			char label = 'o';

 99 50198b5f 2020-05-05 neels 			char *color = NULL;

100 3b0f3d61 2020-01-22 neels 			if (kd) {

101 3b0f3d61 2020-01-22 neels 				int max = l->atoms.len + r->atoms.len;

102 3b0f3d61 2020-01-22 neels 				size_t kd_len = max + 1 + max;

103 3b0f3d61 2020-01-22 neels 				int *kd_pos = kd;

104 3b0f3d61 2020-01-22 neels 				int di;

105 3b0f3d61 2020-01-22 neels #define xk_to_y(X, K) ((X) - (K))

106 3b0f3d61 2020-01-22 neels 				for (di = 0; di < max; di++) {

107 3b0f3d61 2020-01-22 neels 					int ki;

108 3b0f3d61 2020-01-22 neels 					for (ki = di; ki >= -di; ki -= 2) {

109 50198b5f 2020-05-05 neels 						if (x != kd_pos[ki]

110 50198b5f 2020-05-05 neels 						    || y != xk_to_y(x, ki))

111 50198b5f 2020-05-05 neels 							continue;

112 50198b5f 2020-05-05 neels 						label = '0' + (di % 10);

113 50198b5f 2020-05-05 neels 						color = COLOR_YELLOW;

114 50198b5f 2020-05-05 neels 						break;

115 3b0f3d61 2020-01-22 neels 					}

116 50198b5f 2020-05-05 neels 					if (label != 'o')

117 3b0f3d61 2020-01-22 neels 						break;

118 3b0f3d61 2020-01-22 neels 					kd_pos += kd_len;

119 3b0f3d61 2020-01-22 neels 				}

120 3b0f3d61 2020-01-22 neels 			}

121 50198b5f 2020-05-05 neels 			if (kd_forward && kd_forward_d >= 0) {

122 50198b5f 2020-05-05 neels 				int max = l->atoms.len + r->atoms.len;

123 50198b5f 2020-05-05 neels 				size_t kd_len = max + 1 + max;

124 50198b5f 2020-05-05 neels 				int di;

125 50198b5f 2020-05-05 neels #define xc_to_y(X, C, DELTA) ((X) - (C) + (DELTA))

126 50198b5f 2020-05-05 neels 				int delta = (int)r->atoms.len - (int)l->atoms.len;

127 50198b5f 2020-05-05 neels 				int ki;

128 50198b5f 2020-05-05 neels 				for (ki = kd_forward_d; ki >= -kd_forward_d; ki -= 2) {

129 50198b5f 2020-05-05 neels 					if (x != kd_forward[ki])

130 50198b5f 2020-05-05 neels 						continue;

131 50198b5f 2020-05-05 neels 					if (y != xk_to_y(x, ki))

132 50198b5f 2020-05-05 neels 						continue;

133 50198b5f 2020-05-05 neels 					label = 'F';

134 50198b5f 2020-05-05 neels 					color = COLOR_GREEN;

135 50198b5f 2020-05-05 neels 					break;

136 50198b5f 2020-05-05 neels 				}

137 50198b5f 2020-05-05 neels 			}

138 50198b5f 2020-05-05 neels 			if (kd_backward && kd_backward_d >= 0) {

139 50198b5f 2020-05-05 neels 				int max = l->atoms.len + r->atoms.len;

140 50198b5f 2020-05-05 neels 				size_t kd_len = max + 1 + max;

141 50198b5f 2020-05-05 neels 				int di;

142 50198b5f 2020-05-05 neels 				int delta = (int)r->atoms.len - (int)l->atoms.len;

143 50198b5f 2020-05-05 neels 				int ki;

144 50198b5f 2020-05-05 neels 				for (ki = kd_backward_d; ki >= -kd_backward_d; ki -= 2) {

145 50198b5f 2020-05-05 neels 					if (x != kd_backward[ki])

146 50198b5f 2020-05-05 neels 						continue;

147 50198b5f 2020-05-05 neels 					if (y != xc_to_y(x, ki, delta))

148 50198b5f 2020-05-05 neels 						continue;

149 50198b5f 2020-05-05 neels 					if (label == 'o') {

150 50198b5f 2020-05-05 neels 						label = 'B';

151 50198b5f 2020-05-05 neels 						color = COLOR_BLUE;

152 50198b5f 2020-05-05 neels 					} else {

153 50198b5f 2020-05-05 neels 						label = 'X';

154 50198b5f 2020-05-05 neels 						color = COLOR_RED;

155 50198b5f 2020-05-05 neels 					}

156 50198b5f 2020-05-05 neels 					break;

157 50198b5f 2020-05-05 neels 				}

158 50198b5f 2020-05-05 neels 			}

159 50198b5f 2020-05-05 neels 			if (color)

160 50198b5f 2020-05-05 neels 				print("%s", color);

161 50198b5f 2020-05-05 neels 			print("%c", label);

162 50198b5f 2020-05-05 neels 			if (color)

163 50198b5f 2020-05-05 neels 				print("%s", COLOR_END);

164 50198b5f 2020-05-05 neels 			if (x < l->atoms.len)

165 3b0f3d61 2020-01-22 neels 				print("-");

166 3b0f3d61 2020-01-22 neels 		}

167 3b0f3d61 2020-01-22 neels 		print("\n");

168 3b0f3d61 2020-01-22 neels 		if (y == r->atoms.len)

169 3b0f3d61 2020-01-22 neels 			break;

170 3b0f3d61 2020-01-22 neels 

171 50198b5f 2020-05-05 neels 		print("    ");

172 3b0f3d61 2020-01-22 neels 		for (x = 0; x < l->atoms.len; x++) {

173 3b0f3d61 2020-01-22 neels 			if (diff_atom_same(&l->atoms.head[x], &r->atoms.head[y]))

174 3b0f3d61 2020-01-22 neels 				print("|\\");

175 3b0f3d61 2020-01-22 neels 			else

176 3b0f3d61 2020-01-22 neels 				print("| ");

177 3b0f3d61 2020-01-22 neels 		}

178 3b0f3d61 2020-01-22 neels 		print("|\n");

179 3b0f3d61 2020-01-22 neels 	}

180 3b0f3d61 2020-01-22 neels }

181 3b0f3d61 2020-01-22 neels 

182 72057b70 2020-01-27 neels static inline void debug_dump_myers_graph(const struct diff_data *l, const struct diff_data *r,

183 50198b5f 2020-05-05 neels 				    int *kd, int *kd_forward, int kd_forward_d, int *kd_backward, int kd_backward_d)

184 72057b70 2020-01-27 neels {

185 72057b70 2020-01-27 neels 	if (l->atoms.len > 99 || r->atoms.len > 99)

186 72057b70 2020-01-27 neels 		return;

187 50198b5f 2020-05-05 neels 	dump_myers_graph(l, r, kd, kd_forward, kd_forward_d, kd_backward, kd_backward_d);

188 72057b70 2020-01-27 neels }

189 72057b70 2020-01-27 neels 

190 3b0f3d61 2020-01-22 neels #else

191 3b0f3d61 2020-01-22 neels #define debug(args...)

192 3b0f3d61 2020-01-22 neels #define debug_dump(args...)

193 3b0f3d61 2020-01-22 neels #define debug_dump_atom(args...)

194 3b0f3d61 2020-01-22 neels #define debug_dump_atoms(args...)

195 3b0f3d61 2020-01-22 neels #define debug_dump_myers_graph(args...)

196 3b0f3d61 2020-01-22 neels #endif