lib/diff_debug.h

   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