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 28 static inline void 29 print_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 40 static inline void 41 dump_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 75 static inline void 76 dump_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 92 static inline void 93 dump(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 */ 102 static inline void 103 dump_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 209 static inline void 210 debug_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