tools/browse_trace.cc

   1 // Warning: zero automated tests
   2
   3 // Includes
   4 #include "termbox/termbox.h"
   5
   6 #include <stdlib.h>
   7 #define SIZE(X) (assert((X).size() < (1LL<<(sizeof(int)*8-2))), static_cast<int>((X).size()))
   8
   9 #include <assert.h>
  10 #include <iostream>
  11 using std::istream;
  12 using std::ostream;
  13 using std::iostream;
  14 using std::cin;
  15 using std::cout;
  16 using std::cerr;
  17 #include <iomanip>
  18 #include <string.h>
  19 #include <string>
  20 using std::string;
  21 #include <vector>
  22 using std::vector;
  23 #include <set>
  24 using std::set;
  25 #include <sstream>
  26 using std::ostringstream;
  27 #include <fstream>
  28 using std::ifstream;
  29 using std::ofstream;
  30 #include <map>
  31 using std::map;
  32 #include <utility>
  33 using std::pair;
  34 // End Includes
  35
  36 // Types
  37 struct trace_line {
  38   string contents;
  39   string label;
  40   int depth;  // 0 is 'sea level'; positive integers are progressively 'deeper' and lower level
  41   trace_line(string c, string l, int d) {
  42     contents = c;
  43     label = l;
  44     depth = d;
  45   }
  46 };
  47
  48 struct trace_stream {
  49   vector<trace_line> past_lines;
  50 };
  51
  52 enum search_direction { FORWARD, BACKWARD };
  53 // End Types
  54
  55 // from http://stackoverflow.com/questions/152643/idiomatic-c-for-reading-from-a-const-map
  56 template<typename T> typename T::mapped_type& get(T& map, typename T::key_type const& key) {
  57   typename T::iterator iter(map.find(key));
  58   assert(iter != map.end());
  59   return iter->second;
  60 }
  61 template<typename T> typename T::mapped_type const& get(const T& map, typename T::key_type const& key) {
  62   typename T::const_iterator iter(map.find(key));
  63   assert(iter != map.end());
  64   return iter->second;
  65 }
  66 template<typename T> typename T::mapped_type const& put(T& map, typename T::key_type const& key, typename T::mapped_type const& value) {
  67   // map[key] requires mapped_type to have a zero-arg (default) constructor
  68   map.insert(std::make_pair(key, value)).first->second = value;
  69   return value;
  70 }
  71 template<typename T> bool contains_key(T& map, typename T::key_type const& key) {
  72   return map.find(key) != map.end();
  73 }
  74 template<typename T> typename T::mapped_type& get_or_insert(T& map, typename T::key_type const& key) {
  75   return map[key];
  76 }
  77
  78 // Globals
  79 trace_stream* Trace_stream = NULL;
  80
  81 ofstream Trace_file;
  82 int Cursor_row = 0;  // screen coordinate
  83 set<int> Visible;
  84 int Top_of_screen = 0;  // trace coordinate
  85 int Left_of_screen = 0;  // trace coordinate
  86 int Last_printed_row = 0;  // screen coordinate
  87 map<int, int> Trace_index;  // screen row -> trace index
  88
  89 string Current_search_pattern = "";
  90 search_direction Current_search_direction = FORWARD;
  91 // End Globals
  92
  93 bool has_data(istream& in) {
  94   return in && !in.eof();
  95 }
  96
  97 void skip_whitespace_but_not_newline(istream& in) {
  98   while (true) {
  99     if (!has_data(in)) break;
 100     else if (in.peek() == '\n') break;
 101     else if (isspace(in.peek())) in.get();
 102     else break;
 103   }
 104 }
 105
 106 void load_trace(const char* filename) {
 107   ifstream tin(filename);
 108   if (!tin) {
 109     cerr << "no such file: " << filename << '\n';
 110     exit(1);
 111   }
 112   Trace_stream = new trace_stream;
 113   while (has_data(tin)) {
 114     tin >> std::noskipws;
 115       skip_whitespace_but_not_newline(tin);
 116       if (!isdigit(tin.peek())) {
 117         string dummy;
 118         getline(tin, dummy);
 119         continue;
 120       }
 121     tin >> std::skipws;
 122     int depth;
 123     tin >> depth;
 124     string label;
 125     tin >> label;
 126     if (*--label.end() == ':') label.erase(--label.end());
 127     string line;
 128     getline(tin, line);
 129     Trace_stream->past_lines.push_back(trace_line(line, label, depth));
 130   }
 131   cerr << "lines read: " << Trace_stream->past_lines.size() << '\n';
 132 }
 133
 134 void refresh_screen_rows() {  // Top_of_screen, Visible -> Trace_index
 135   int screen_row = 0, index = 0;
 136   Trace_index.clear();
 137   for (screen_row = 0, index = Top_of_screen;  screen_row < tb_height() && index < SIZE(Trace_stream->past_lines);  ++screen_row, ++index) {
 138     // skip lines without depth for now
 139     while (!contains_key(Visible, index)) {
 140       ++index;
 141       if (index >= SIZE(Trace_stream->past_lines)) goto done;
 142     }
 143     assert(index < SIZE(Trace_stream->past_lines));
 144     put(Trace_index, screen_row, index);
 145   }
 146 done:;
 147 }
 148
 149 void clear_line(int screen_row) {  // -> screen
 150   tb_set_cursor(0, screen_row);
 151   for (int col = 0;  col < tb_width();  ++col)
 152     tb_print(' ', TB_WHITE, TB_BLACK);
 153   tb_set_cursor(0, screen_row);
 154 }
 155
 156 int read_key() {
 157   tb_event event;
 158   do {
 159     tb_poll_event(&event);
 160   } while (event.type != TB_EVENT_KEY);
 161   return event.key ? event.key : event.ch;
 162 }
 163
 164 int lines_hidden(int screen_row) {
 165   assert(contains_key(Trace_index, screen_row));
 166   if (!contains_key(Trace_index, screen_row+1))
 167     return SIZE(Trace_stream->past_lines) - get(Trace_index, screen_row);
 168   else
 169     return get(Trace_index, screen_row+1) - get(Trace_index, screen_row);
 170 }
 171
 172 bool in_range(const vector<pair<size_t, size_t> >& highlight_ranges, size_t idx) {
 173   for (int i = 0;  i < SIZE(highlight_ranges);  ++i) {
 174     if (idx >= highlight_ranges.at(i).first && idx < highlight_ranges.at(i).second)
 175       return true;
 176     if (idx < highlight_ranges.at(i).second) break;
 177   }
 178   return false;
 179 }
 180
 181 vector<pair<size_t, size_t> > find_all_occurrences(const string& s, const string& pat) {
 182   vector<pair<size_t, size_t> > result;
 183   if (pat.empty()) return result;
 184   size_t idx = 0;
 185   while (true) {
 186     size_t next_idx = s.find(pat, idx);
 187     if (next_idx == string::npos) break;
 188     result.push_back(pair<size_t, size_t>(next_idx, next_idx+SIZE(pat)));
 189     idx = next_idx+SIZE(pat);
 190   }
 191   return result;
 192 }
 193
 194 int bg_color(int depth, int trace_index, int screen_row) {
 195   if (screen_row == Cursor_row) {
 196     if (trace_index == 0) return /*subtle grey*/240;  // ignore the zero-depth sentinel at start of trace
 197     if (depth > 0) return /*subtle grey*/240;
 198     else return /*subtle red*/88;
 199   }
 200   if (trace_index == 0) return TB_BLACK;  // ignore the zero-depth sentinel at start of trace
 201   if (depth == 0) return /*red*/1;
 202   if (depth == 1) return /*orange*/166;
 203   // start at black, gradually lighten at deeper levels
 204   return TB_BLACK + ((depth-2) % 6)*2;
 205 }
 206
 207 void render_line(int screen_row, const string& s, int bg) {  // -> screen
 208   int col = 0;
 209   int color = TB_WHITE;
 210   vector<pair<size_t, size_t> > highlight_ranges = find_all_occurrences(s, Current_search_pattern);
 211   tb_set_cursor(0, screen_row);
 212   for (col = 0;  col < tb_width();  ++col) {
 213     char c = ' ';
 214     if (col+Left_of_screen < SIZE(s))
 215       c = s.at(col+Left_of_screen);  // todo: unicode
 216     if (c == '\n') c = ';';  // replace newlines with semi-colons
 217     // escapes. hack: can't start a line with them.
 218     if (c == '\1') { color = /*red*/1;  continue; }
 219     if (c == '\2') { color = TB_WHITE;  continue; }
 220     if (in_range(highlight_ranges, col+Left_of_screen))
 221       tb_print(c, TB_BLACK, /*yellow*/11);
 222     else
 223       tb_print(c, color, bg);
 224   }
 225 }
 226
 227 void search_next(const string& pat) {
 228   for (int trace_index = get(Trace_index, Cursor_row)+1;  trace_index < SIZE(Trace_stream->past_lines);  ++trace_index) {
 229     if (!contains_key(Visible, trace_index)) continue;
 230     const trace_line& line = Trace_stream->past_lines.at(trace_index);
 231     if (line.label.find(pat) == string::npos && line.contents.find(pat) == string::npos) continue;
 232     Top_of_screen = trace_index;
 233     Cursor_row = 0;
 234     refresh_screen_rows();
 235     return;
 236   }
 237 }
 238
 239 void search_previous(const string& pat) {
 240   for (int trace_index = get(Trace_index, Cursor_row)-1;  trace_index >= 0;  --trace_index) {
 241     if (!contains_key(Visible, trace_index)) continue;
 242     const trace_line& line = Trace_stream->past_lines.at(trace_index);
 243     if (line.label.find(pat) == string::npos && line.contents.find(pat) == string::npos) continue;
 244     Top_of_screen = trace_index;
 245     Cursor_row = 0;
 246     refresh_screen_rows();
 247     return;
 248   }
 249 }
 250
 251 void search(const string& pat, search_direction dir) {
 252   if (dir == FORWARD) search_next(pat);
 253   else search_previous(pat);
 254 }
 255
 256 search_direction opposite(search_direction dir) {
 257   if (dir == FORWARD) return BACKWARD;
 258   else return FORWARD;
 259 }
 260
 261 bool start_search_editor(search_direction dir) {
 262   const int bottom_screen_line = tb_height()-1;
 263   // run a little editor just in the last line of the screen
 264   clear_line(bottom_screen_line);
 265   int col = 0;  // screen column of cursor on bottom line. also used to update pattern.
 266   tb_set_cursor(col, bottom_screen_line);
 267   tb_print('/', TB_WHITE, TB_BLACK);
 268   ++col;
 269   string pattern;
 270   while (true) {
 271     int key = read_key();
 272     if (key == TB_KEY_ENTER) {
 273       if (!pattern.empty()) {
 274         Current_search_pattern = pattern;
 275         Current_search_direction = dir;
 276       }
 277       return true;
 278     }
 279     else if (key == TB_KEY_ESC || key == TB_KEY_CTRL_C) {
 280       return false;
 281     }
 282     else if (key == TB_KEY_ARROW_LEFT) {
 283       if (col > /*slash*/1) {
 284         --col;
 285         tb_set_cursor(col, bottom_screen_line);
 286       }
 287     }
 288     else if (key == TB_KEY_ARROW_RIGHT) {
 289       if (col-/*slash*/1 < SIZE(pattern)) {
 290         ++col;
 291         tb_set_cursor(col, bottom_screen_line);
 292       }
 293     }
 294     else if (key == TB_KEY_HOME || key == TB_KEY_CTRL_A) {
 295       col = /*skip slash*/1;
 296       tb_set_cursor(col, bottom_screen_line);
 297     }
 298     else if (key == TB_KEY_END || key == TB_KEY_CTRL_E) {
 299       col = SIZE(pattern)+/*skip slash*/1;
 300       tb_set_cursor(col, bottom_screen_line);
 301     }
 302     else if (key == TB_KEY_BACKSPACE || key == TB_KEY_BACKSPACE2) {
 303       if (col > /*slash*/1) {
 304         assert(col <= SIZE(pattern)+1);
 305         --col;
 306         // update pattern
 307         pattern.erase(col-/*slash*/1, /*len*/1);
 308         // update screen
 309         tb_set_cursor(col, bottom_screen_line);
 310         for (int x = col;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
 311           tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
 312         tb_print(' ', TB_WHITE, TB_BLACK);
 313         tb_set_cursor(col, bottom_screen_line);
 314       }
 315     }
 316     else if (key == TB_KEY_CTRL_K) {
 317       int old_pattern_size = SIZE(pattern);
 318       pattern.erase(col-/*slash*/1, SIZE(pattern) - (col-/*slash*/1));
 319       tb_set_cursor(col, bottom_screen_line);
 320       for (int x = col;  x < old_pattern_size+/*slash*/1;  ++x)
 321         tb_print(' ', TB_WHITE, TB_BLACK);
 322       tb_set_cursor(col, bottom_screen_line);
 323     }
 324     else if (key == TB_KEY_CTRL_U) {
 325       int old_pattern_size = SIZE(pattern);
 326       pattern.erase(0, col-/*slash*/1);
 327       col = /*skip slash*/1;
 328       tb_set_cursor(col, bottom_screen_line);
 329       for (int x = /*slash*/1;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
 330         tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
 331       for (int x = SIZE(pattern)+/*slash*/1;  x < old_pattern_size+/*skip slash*/1;  ++x)
 332         tb_print(' ', TB_WHITE, TB_BLACK);
 333       tb_set_cursor(col, bottom_screen_line);
 334     }
 335     else if (key < 128) {  // ascii only
 336       // update pattern
 337       char c = static_cast<char>(key);
 338       assert(col-1 >= 0);
 339       assert(col-1 <= SIZE(pattern));
 340       pattern.insert(col-/*slash*/1, /*num*/1, c);
 341       // update screen
 342       for (int x = col;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
 343         tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
 344       ++col;
 345       tb_set_cursor(col, bottom_screen_line);
 346     }
 347   }
 348 }
 349
 350 void render() {  // Trace_index -> Last_printed_row, screen
 351   int screen_row = 0;
 352   for (screen_row = 0;  screen_row < tb_height();  ++screen_row) {
 353     if (!contains_key(Trace_index, screen_row)) break;
 354     int trace_index = get(Trace_index, screen_row);
 355     trace_line& curr_line = Trace_stream->past_lines.at(trace_index);
 356     ostringstream out;
 357     if (screen_row < tb_height()-1) {
 358       int delta = lines_hidden(screen_row);
 359       // home-brew escape sequence for red
 360       if (delta > 1) {
 361         if (delta > 999) out << static_cast<char>(1);
 362         out << std::setw(6) << delta << "| ";
 363         if (delta > 999) out << static_cast<char>(2);
 364       }
 365       else {
 366         out << "        ";
 367       }
 368     }
 369     else {
 370       out << "        ";
 371     }
 372     out << std::setw(2) << curr_line.depth << ' ' << curr_line.label << ": " << curr_line.contents;
 373     int bg = bg_color(curr_line.depth, trace_index, screen_row);
 374     render_line(screen_row, out.str(), bg);
 375   }
 376   // clear rest of screen
 377   Last_printed_row = screen_row-1;
 378   for (;  screen_row < tb_height();  ++screen_row)
 379     render_line(screen_row, "~", /*bg*/TB_BLACK);
 380   // move cursor back to display row at the end
 381   tb_set_cursor(0, Cursor_row);
 382 }
 383
 384 int main(int argc, char* argv[]) {
 385   if (argc != 2) {
 386     cerr << "Usage: browse_trace <trace file>\n";
 387     return 1;
 388   }
 389   load_trace(argv[1]);
 390   if (!Trace_stream) return 1;
 391   cerr << "computing min depth to display\n";
 392   int min_depth = 9999;
 393   for (int i = 0;  i < SIZE(Trace_stream->past_lines);  ++i) {
 394     trace_line& curr_line = Trace_stream->past_lines.at(i);
 395     if (curr_line.depth < min_depth) min_depth = curr_line.depth;
 396   }
 397   cerr << "min depth is " << min_depth << '\n';
 398   cerr << "computing lines to display\n";
 399   for (int i = 0;  i < SIZE(Trace_stream->past_lines);  ++i) {
 400     if (Trace_stream->past_lines.at(i).depth == min_depth)
 401       Visible.insert(i);
 402   }
 403   tb_init();
 404   tb_clear();
 405   Cursor_row = 0;
 406   Top_of_screen = 0;
 407   refresh_screen_rows();
 408   while (true) {
 409     render();
 410     int key = read_key();
 411     if (key == 'q' || key == 'Q' || key == TB_KEY_CTRL_C) break;
 412     if (key == 'j' || key == TB_KEY_ARROW_DOWN) {
 413       // move cursor one line down
 414       if (Cursor_row < Last_printed_row) ++Cursor_row;
 415     }
 416     else if (key == 'k' || key == TB_KEY_ARROW_UP) {
 417       // move cursor one line up
 418       if (Cursor_row > 0) --Cursor_row;
 419     }
 420     else if (key == 't') {
 421       // move cursor to top of screen
 422       Cursor_row = 0;
 423     }
 424     else if (key == 'c') {
 425       // move cursor to center of screen
 426       Cursor_row = tb_height()/2;
 427       while (!contains_key(Trace_index, Cursor_row))
 428         --Cursor_row;
 429     }
 430     else if (key == 'b') {
 431       // move cursor to bottom of screen
 432       Cursor_row = tb_height()-1;
 433       while (!contains_key(Trace_index, Cursor_row))
 434         --Cursor_row;
 435     }
 436     else if (key == 'T') {
 437       // scroll line at cursor to top of screen
 438       Top_of_screen = get(Trace_index, Cursor_row);
 439       Cursor_row = 0;
 440       refresh_screen_rows();
 441     }
 442     else if (key == 'h' || key == TB_KEY_ARROW_LEFT) {
 443       // pan screen one character left
 444       if (Left_of_screen > 0) --Left_of_screen;
 445     }
 446     else if (key == 'l' || key == TB_KEY_ARROW_RIGHT) {
 447       // pan screen one character right
 448       ++Left_of_screen;
 449     }
 450     else if (key == 'H') {
 451       // pan screen one screen-width left
 452       Left_of_screen -= (tb_width() - 5);
 453       if (Left_of_screen < 0) Left_of_screen = 0;
 454     }
 455     else if (key == 'L') {
 456       // pan screen one screen-width right
 457       Left_of_screen += (tb_width() - 5);
 458     }
 459     else if (key == 'J' || key == TB_KEY_PGDN || key == TB_KEY_CTRL_F) {
 460       // page-down
 461       if (Trace_index.find(tb_height()-1) != Trace_index.end()) {
 462         Top_of_screen = get(Trace_index, tb_height()-1) + 1;
 463         refresh_screen_rows();
 464       }
 465     }
 466     else if (key == 'K' || key == TB_KEY_PGUP || key == TB_KEY_CTRL_B) {
 467       // page-up is more convoluted
 468       for (int screen_row = tb_height();  screen_row > 0 && Top_of_screen > 0;  --screen_row) {
 469         --Top_of_screen;
 470         if (Top_of_screen <= 0) break;
 471         while (Top_of_screen > 0 && !contains_key(Visible, Top_of_screen))
 472           --Top_of_screen;
 473       }
 474       if (Top_of_screen >= 0)
 475         refresh_screen_rows();
 476     }
 477     else if (key == 'g' || key == TB_KEY_HOME) {
 478         Top_of_screen = 0;
 479         Last_printed_row = 0;
 480         Cursor_row = 0;
 481         refresh_screen_rows();
 482     }
 483     else if (key == 'G' || key == TB_KEY_END) {
 484       // go to bottom of trace; largely like page-up, interestingly
 485       Top_of_screen = SIZE(Trace_stream->past_lines)-1;
 486       for (int screen_row = tb_height();  screen_row > 0 && Top_of_screen > 0;  --screen_row) {
 487         --Top_of_screen;
 488         if (Top_of_screen <= 0) break;
 489         while (Top_of_screen > 0 && !contains_key(Visible, Top_of_screen))
 490           --Top_of_screen;
 491       }
 492       refresh_screen_rows();
 493       render();
 494       // move cursor to bottom
 495       Cursor_row = Last_printed_row;
 496       refresh_screen_rows();
 497     }
 498     else if (key == TB_KEY_CARRIAGE_RETURN) {
 499       // expand lines under current by one level
 500       assert(contains_key(Trace_index, Cursor_row));
 501       int start_index = get(Trace_index, Cursor_row);
 502       int index = 0;
 503       // simultaneously compute end_index and min_depth
 504       int min_depth = 9999;
 505       for (index = start_index+1;  index < SIZE(Trace_stream->past_lines);  ++index) {
 506         if (contains_key(Visible, index)) break;
 507         trace_line& curr_line = Trace_stream->past_lines.at(index);
 508         assert(curr_line.depth > Trace_stream->past_lines.at(start_index).depth);
 509         if (curr_line.depth < min_depth) min_depth = curr_line.depth;
 510       }
 511       int end_index = index;
 512       // mark as visible all intervening indices at min_depth
 513       for (index = start_index;  index < end_index;  ++index) {
 514         trace_line& curr_line = Trace_stream->past_lines.at(index);
 515         if (curr_line.depth == min_depth) {
 516           Visible.insert(index);
 517         }
 518       }
 519       refresh_screen_rows();
 520     }
 521     else if (key == TB_KEY_BACKSPACE || key == TB_KEY_BACKSPACE2) {
 522       // collapse all lines under current
 523       assert(contains_key(Trace_index, Cursor_row));
 524       int start_index = get(Trace_index, Cursor_row);
 525       int index = 0;
 526       // end_index is the next line at a depth same as or lower than start_index
 527       int initial_depth = Trace_stream->past_lines.at(start_index).depth;
 528       for (index = start_index+1;  index < SIZE(Trace_stream->past_lines);  ++index) {
 529         if (!contains_key(Visible, index)) continue;
 530         trace_line& curr_line = Trace_stream->past_lines.at(index);
 531         if (curr_line.depth <= initial_depth) break;
 532       }
 533       int end_index = index;
 534       // mark as visible all intervening indices at min_depth
 535       for (index = start_index+1;  index < end_index;  ++index) {
 536         Visible.erase(index);
 537       }
 538       refresh_screen_rows();
 539     }
 540     else if (key == '/') {
 541       if (start_search_editor(FORWARD))
 542         search(Current_search_pattern, Current_search_direction);
 543     }
 544     else if (key == '?') {
 545       if (start_search_editor(BACKWARD))
 546         search(Current_search_pattern, Current_search_direction);
 547     }
 548     else if (key == 'n') {
 549       if (!Current_search_pattern.empty())
 550         search(Current_search_pattern, Current_search_direction);
 551     }
 552     else if (key == 'N') {
 553       if (!Current_search_pattern.empty())
 554         search(Current_search_pattern, opposite(Current_search_direction));
 555     }
 556   }
 557   tb_clear();
 558   tb_shutdown();
 559   return 0;
 560 }