1 //: A debugging helper that lets you zoom in/out on a trace.
  2 //: Warning: this tool has zero automated tests.
  3 //:
  4 //: To try it out, first create an example trace:
  5 //:   mu --trace nqueens.mu
  6 //: Then to browse the trace, which was stored in a file called 'last_run':
  7 //:   mu browse-trace last_run
  8 //:
  9 //: You should now find yourself in a UI showing a subsequence of lines from
 10 //: the trace, each line starting with a numeric depth, and ending with a
 11 //: parenthetical count of trace lines hidden after it with greater depths.
 12 //:
 13 //: For example, this line:
 14 //:   2 app: line1 (30)
 15 //: indicates that it was logged with depth 2, and that 30 following lines
 16 //: have been hidden at a depth greater than 2.
 17 //:
 18 //: As an experiment, hidden counts of 1000 or more are in red to highlight
 19 //: where you might be particularly interested in expanding.
 20 //:
 21 //: The UI provides the following hotkeys:
 22 //:
 23 //:   `q` or `ctrl-c`: Quit.
 24 //:
 25 //:   `Enter`: 'Zoom into' this line. Expand some or all of the hidden lines
 26 //:   at the next higher level, updating parenthetical counts of hidden lines.
 27 //:
 28 //:   `Backspace`: 'Zoom out' on a line after zooming in, collapsing expanded
 29 //:   lines below by some series of <Enter> commands.
 30 //:
 31 //:   `j` or `down-arrow`: Move/scroll cursor down one line.
 32 //:   `k` or `up-arrow`: Move/scroll cursor up one line.
 33 //:   `J` or `ctrl-f` or `page-down`: Scroll cursor down one page.
 34 //:   `K` or `ctrl-b` or `page-up`: Scroll cursor up one page.
 35 //:   `h` or `left-arrow`: Scroll cursor left one character.
 36 //:   `l` or `right-arrow`: Scroll cursor right one character.
 37 //:   `H`: Scroll cursor left one screen-width.
 38 //:   `L`: Scroll cursor right one screen-width.
 39 //:
 40 //:   `g` or `home`: Move cursor to start of trace.
 41 //:   `G` or `end`: Move cursor to end of trace.
 42 //:
 43 //:   `t`: Move cursor to top line on screen.
 44 //:   `c`: Move cursor to center line on screen.
 45 //:   `b`: Move cursor to bottom line on screen.
 46 //:   `T`: Scroll line at cursor to top of screen.
 47 //:
 48 //:   `/`: Search forward for a pattern.
 49 //:   '?': Search backward for a pattern.
 50 //:   `n`: Repeat the previous '/' or '?'.
 51 //:   `N`: Repeat the previous '/' or '?' in the opposite direction.
 52 //:
 53 //:   After hitting `/`, a small editor on the bottom-most line supports the
 54 //:   following hotkeys:
 55 //:     ascii characters: add the key to the pattern.
 56 //:     `Enter`: search for the pattern.
 57 //:     `Esc` or `ctrl-c`: cancel the current search, setting the screen back
 58 //:       to its state before the search.
 59 //:     `left-arrow`: move cursor left.
 60 //:     `right-arrow`: move cursor right.
 61 //:     `ctrl-a` or `home`: move cursor to start of search pattern.
 62 //:     `ctrl-e` or `end`: move cursor to end of search pattern.
 63 //:     `ctrl-u`: clear search pattern before cursor
 64 //:     `ctrl-k`: clear search pattern at and after cursor
 65 
 66 :(before "End Primitive Recipe Declarations")
 67 _BROWSE_TRACE,
 68 :(before "End Primitive Recipe Numbers")
 69 put(Recipe_ordinal, "$browse-trace", _BROWSE_TRACE);
 70 :(before "End Primitive Recipe Checks")
 71 case _BROWSE_TRACE: {
 72   break;
 73 }
 74 :(before "End Primitive Recipe Implementations")
 75 case _BROWSE_TRACE: {
 76   start_trace_browser();
 77   break;
 78 }
 79 
 80 //: browse a trace loaded from a file
 81 :(after "Commandline Parsing")
 82 if (argc == 3 && is_equal(argv[1], "browse-trace")) {
 83   load_trace(argv[2]);
 84   start_trace_browser();
 85   return 0;
 86 }
 87 
 88 :(before "End Globals")
 89 set<int> Visible;
 90 int Top_of_screen = 0;
 91 int Left_of_screen = 0;
 92 int Last_printed_row = 0;
 93 map<int, int> Trace_index;  // screen row -> trace index
 94 string Current_search_pattern = "";
 95 :(before "End Types")
 96 enum search_direction { FORWARD, BACKWARD };
 97 :(before "End Globals")
 98 search_direction Current_search_direction = FORWARD;
 99 
100 :(code)
101 void start_trace_browser() {
102   if (!Trace_stream) return;
103   cerr << "computing min depth to display\n";
104   int min_depth = 9999;
105   for (int i = 0;  i < SIZE(Trace_stream->past_lines);  ++i) {
106     trace_line& curr_line = Trace_stream->past_lines.at(i);
107     if (curr_line.depth < min_depth) min_depth = curr_line.depth;
108   }
109   cerr << "min depth is " << min_depth << '\n';
110   cerr << "computing lines to display\n";
111   for (int i = 0;  i < SIZE(Trace_stream->past_lines);  ++i) {
112     if (Trace_stream->past_lines.at(i).depth == min_depth)
113       Visible.insert(i);
114   }
115   tb_init();
116   tb_clear();
117   Display_row = Display_column = 0;
118   Top_of_screen = 0;
119   refresh_screen_rows();
120   while (true) {
121     render();
122     int key = read_key();
123     if (key == 'q' || key == 'Q' || key == TB_KEY_CTRL_C) break;
124     if (key == 'j' || key == TB_KEY_ARROW_DOWN) {
125       // move cursor one line down
126       if (Display_row < Last_printed_row) ++Display_row;
127     }
128     else if (key == 'k' || key == TB_KEY_ARROW_UP) {
129       // move cursor one line up
130       if (Display_row > 0) --Display_row;
131     }
132     else if (key == 't') {
133       // move cursor to top of screen
134       Display_row = 0;
135     }
136     else if (key == 'c') {
137       // move cursor to center of screen
138       Display_row = tb_height()/2;
139       while (!contains_key(Trace_index, Display_row))
140         --Display_row;
141     }
142     else if (key == 'b') {
143       // move cursor to bottom of screen
144       Display_row = tb_height()-1;
145       while (!contains_key(Trace_index, Display_row))
146         --Display_row;
147     }
148     else if (key == 'T') {
149       // scroll line at cursor to top of screen
150       Top_of_screen = get(Trace_index, Display_row);
151       Display_row = 0;
152       refresh_screen_rows();
153     }
154     else if (key == 'h' || key == TB_KEY_ARROW_LEFT) {
155       // pan screen one character left
156       if (Left_of_screen > 0) --Left_of_screen;
157     }
158     else if (key == 'l' || key == TB_KEY_ARROW_RIGHT) {
159       // pan screen one character right
160       ++Left_of_screen;
161     }
162     else if (key == 'H') {
163       // pan screen one screen-width left
164       Left_of_screen -= (tb_width() - 5);
165       if (Left_of_screen < 0) Left_of_screen = 0;
166     }
167     else if (key == 'L') {
168       // pan screen one screen-width right
169       Left_of_screen += (tb_width() - 5);
170     }
171     else if (key == 'J' || key == TB_KEY_PGDN || key == TB_KEY_CTRL_F) {
172       // page-down
173       if (Trace_index.find(tb_height()-1) != Trace_index.end()) {
174         Top_of_screen = get(Trace_index, tb_height()-1) + 1;
175         refresh_screen_rows();
176       }
177     }
178     else if (key == 'K' || key == TB_KEY_PGUP || key == TB_KEY_CTRL_B) {
179       // page-up is more convoluted
180       for (int screen_row = tb_height();  screen_row > 0 && Top_of_screen > 0;  --screen_row) {
181         --Top_of_screen;
182         if (Top_of_screen <= 0) break;
183         while (Top_of_screen > 0 && !contains_key(Visible, Top_of_screen))
184           --Top_of_screen;
185       }
186       if (Top_of_screen >= 0)
187         refresh_screen_rows();
188     }
189     else if (key == 'g' || key == TB_KEY_HOME) {
190         Top_of_screen = 0;
191         Last_printed_row = 0;
192         Display_row = 0;
193         refresh_screen_rows();
194     }
195     else if (key == 'G' || key == TB_KEY_END) {
196       // go to bottom of screen; largely like page-up, interestingly
197       Top_of_screen = SIZE(Trace_stream->past_lines)-1;
198       for (int screen_row = tb_height();  screen_row > 0 && Top_of_screen > 0;  --screen_row) {
199         --Top_of_screen;
200         if (Top_of_screen <= 0) break;
201         while (Top_of_screen > 0 && !contains_key(Visible, Top_of_screen))
202           --Top_of_screen;
203       }
204       refresh_screen_rows();
205       // move cursor to bottom
206       Display_row = Last_printed_row;
207       refresh_screen_rows();
208     }
209     else if (key == TB_KEY_CARRIAGE_RETURN) {
210       // expand lines under current by one level
211       assert(contains_key(Trace_index, Display_row));
212       int start_index = get(Trace_index, Display_row);
213       int index = 0;
214       // simultaneously compute end_index and min_depth
215       int min_depth = 9999;
216       for (index = start_index+1;  index < SIZE(Trace_stream->past_lines);  ++index) {
217         if (contains_key(Visible, index)) break;
218         trace_line& curr_line = Trace_stream->past_lines.at(index);
219         assert(curr_line.depth > Trace_stream->past_lines.at(start_index).depth);
220         if (curr_line.depth < min_depth) min_depth = curr_line.depth;
221       }
222       int end_index = index;
223       // mark as visible all intervening indices at min_depth
224       for (index = start_index;  index < end_index;  ++index) {
225         trace_line& curr_line = Trace_stream->past_lines.at(index);
226         if (curr_line.depth == min_depth) {
227           Visible.insert(index);
228         }
229       }
230       refresh_screen_rows();
231     }
232     else if (key == TB_KEY_BACKSPACE || key == TB_KEY_BACKSPACE2) {
233       // collapse all lines under current
234       assert(contains_key(Trace_index, Display_row));
235       int start_index = get(Trace_index, Display_row);
236       int index = 0;
237       // end_index is the next line at a depth same as or lower than start_index
238       int initial_depth = Trace_stream->past_lines.at(start_index).depth;
239       for (index = start_index+1;  index < SIZE(Trace_stream->past_lines);  ++index) {
240         if (!contains_key(Visible, index)) continue;
241         trace_line& curr_line = Trace_stream->past_lines.at(index);
242         if (curr_line.depth <= initial_depth) break;
243       }
244       int end_index = index;
245       // mark as visible all intervening indices at min_depth
246       for (index = start_index+1;  index < end_index;  ++index) {
247         Visible.erase(index);
248       }
249       refresh_screen_rows();
250     }
251     else if (key == '/') {
252       if (start_search_editor(FORWARD))
253         search(Current_search_pattern, Current_search_direction);
254     }
255     else if (key == '?') {
256       if (start_search_editor(BACKWARD))
257         search(Current_search_pattern, Current_search_direction);
258     }
259     else if (key == 'n') {
260       if (!Current_search_pattern.empty())
261         search(Current_search_pattern, Current_search_direction);
262     }
263     else if (key == 'N') {
264       if (!Current_search_pattern.empty())
265         search(Current_search_pattern, opposite(Current_search_direction));
266     }
267   }
268   tb_shutdown();
269 }
270 
271 bool start_search_editor(search_direction dir) {
272   const int bottom_screen_line = tb_height()-1;
273   // run a little editor just in the last line of the screen
274   clear_line(bottom_screen_line);
275   int col = 0;  // screen column of cursor on bottom line. also used to update pattern.
276   tb_set_cursor(col, bottom_screen_line);
277   tb_print('/', TB_WHITE, TB_BLACK);
278   ++col;
279   string pattern;
280   while (true) {
281     int key = read_key();
282     if (key == TB_KEY_ENTER) {
283       if (!pattern.empty()) {
284         Current_search_pattern = pattern;
285         Current_search_direction = dir;
286       }
287       return true;
288     }
289     else if (key == TB_KEY_ESC || key == TB_KEY_CTRL_C) {
290       return false;
291     }
292     else if (key == TB_KEY_ARROW_LEFT) {
293       if (col > /*slash*/1) {
294         --col;
295         tb_set_cursor(col, bottom_screen_line);
296       }
297     }
298     else if (key == TB_KEY_ARROW_RIGHT) {
299       if (col-/*slash*/1 < SIZE(pattern)) {
300         ++col;
301         tb_set_cursor(col, bottom_screen_line);
302       }
303     }
304     else if (key == TB_KEY_HOME || key == TB_KEY_CTRL_A) {
305       col = /*skip slash*/1;
306       tb_set_cursor(col, bottom_screen_line);
307     }
308     else if (key == TB_KEY_END || key == TB_KEY_CTRL_E) {
309       col = SIZE(pattern)+/*skip slash*/1;
310       tb_set_cursor(col, bottom_screen_line);
311     }
312     else if (key == TB_KEY_BACKSPACE || key == TB_KEY_BACKSPACE2) {
313       if (col > /*slash*/1) {
314         assert(col <= SIZE(pattern)+1);
315         --col;
316         // update pattern
317         pattern.erase(col-/*slash*/1, /*len*/1);
318         // update screen
319         tb_set_cursor(col, bottom_screen_line);
320         for (int x = col;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
321           tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
322         tb_print(' ', TB_WHITE, TB_BLACK);
323         tb_set_cursor(col, bottom_screen_line);
324       }
325     }
326     else if (key == TB_KEY_CTRL_K) {
327       int old_pattern_size = SIZE(pattern);
328       pattern.erase(col-/*slash*/1, SIZE(pattern) - (col-/*slash*/1));
329       tb_set_cursor(col, bottom_screen_line);
330       for (int x = col;  x < old_pattern_size+/*slash*/1;  ++x)
331         tb_print(' ', TB_WHITE, TB_BLACK);
332       tb_set_cursor(col, bottom_screen_line);
333     }
334     else if (key == TB_KEY_CTRL_U) {
335       int old_pattern_size = SIZE(pattern);
336       pattern.erase(0, col-/*slash*/1);
337       col = /*skip slash*/1;
338       tb_set_cursor(col, bottom_screen_line);
339       for (int x = /*slash*/1;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
340         tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
341       for (int x = SIZE(pattern)+/*slash*/1;  x < old_pattern_size+/*skip slash*/1;  ++x)
342         tb_print(' ', TB_WHITE, TB_BLACK);
343       tb_set_cursor(col, bottom_screen_line);
344     }
345     else if (key < 128) {  // ascii only
346       // update pattern
347       char c = static_cast<char>(key);
348       assert(col-1 >= 0);
349       assert(col-1 <= SIZE(pattern));
350       pattern.insert(col-/*slash*/1, /*num*/1, c);
351       // update screen
352       for (int x = col;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
353         tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
354       ++col;
355       tb_set_cursor(col, bottom_screen_line);
356     }
357   }
358 }
359 
360 void search(const string& pat, search_direction dir) {
361   if (dir == FORWARD) search_next(pat);
362   else search_previous(pat);
363 }
364 
365 search_direction opposite(search_direction dir) {
366   if (dir == FORWARD) return BACKWARD;
367   else return FORWARD;
368 }
369 
370 void search_next(const string& pat) {
371   for (int trace_index = get(Trace_index, Display_row)+1;  trace_index < SIZE(Trace_stream->past_lines);  ++trace_index) {
372     if (!contains_key(Visible, trace_index)) continue;
373     const trace_line& line = Trace_stream->past_lines.at(trace_index);
374     if (line.label.find(pat) == string::npos && line.contents.find(pat) == string::npos) continue;
375     Top_of_screen = trace_index;
376     Display_row = 0;
377     refresh_screen_rows();
378     return;
379   }
380 }
381 
382 void search_previous(const string& pat) {
383   for (int trace_index = get(Trace_index, Display_row)-1;  trace_index >= 0;  --trace_index) {
384     if (!contains_key(Visible, trace_index)) continue;
385     const trace_line& line = Trace_stream->past_lines.at(trace_index);
386     if (line.label.find(pat) == string::npos && line.contents.find(pat) == string::npos) continue;
387     Top_of_screen = trace_index;
388     Display_row = 0;
389     refresh_screen_rows();
390     return;
391   }
392 }
393 
394 void clear_line(int screen_row) {
395   tb_set_cursor(0, screen_row);
396   for (int col = 0;  col < tb_width();  ++col)
397     tb_print(' ', TB_WHITE, TB_BLACK);
398   tb_set_cursor(0, screen_row);
399 }
400 
401 // update Trace_indices for each screen_row on the basis of Top_of_screen and Visible
402 void refresh_screen_rows() {
403   int screen_row = 0, index = 0;
404   Trace_index.clear();
405   for (screen_row = 0, index = Top_of_screen;  screen_row < tb_height() && index < SIZE(Trace_stream->past_lines);  ++screen_row, ++index) {
406     // skip lines without depth for now
407     while (!contains_key(Visible, index)) {
408       ++index;
409       if (index >= SIZE(Trace_stream->past_lines)) goto done;
410     }
411     assert(index < SIZE(Trace_stream->past_lines));
412     put(Trace_index, screen_row, index);
413   }
414 done:;
415 }
416 
417 void render() {
418   int screen_row = 0;
419   for (screen_row = 0;  screen_row < tb_height();  ++screen_row) {
420     if (!contains_key(Trace_index, screen_row)) break;
421     trace_line& curr_line = Trace_stream->past_lines.at(get(Trace_index, screen_row));
422     ostringstream out;
423     out << std::setw(4) << curr_line.depth << ' ' << curr_line.label << ": " << curr_line.contents;
424     if (screen_row < tb_height()-1) {
425       int delta = lines_hidden(screen_row);
426       // home-brew escape sequence for red
427       if (delta > 1) {
428         if (delta > 999) out << static_cast<char>(1);
429         out << " (" << delta << ")";
430         if (delta > 999) out << static_cast<char>(2);
431       }
432     }
433     render_line(screen_row, out.str(), screen_row == Display_row);
434   }
435   // clear rest of screen
436   Last_printed_row = screen_row-1;
437   for (;  screen_row < tb_height();  ++screen_row)
438     render_line(screen_row, "~", /*cursor_line?*/false);
439   // move cursor back to display row at the end
440   tb_set_cursor(0, Display_row);
441 }
442 
443 int lines_hidden(int screen_row) {
444   assert(contains_key(Trace_index, screen_row));
445   if (!contains_key(Trace_index, screen_row+1))
446     return SIZE(Trace_stream->past_lines) - get(Trace_index, screen_row);
447   else
448     return get(Trace_index, screen_row+1) - get(Trace_index, screen_row);
449 }
450 
451 void render_line(int screen_row, const string& s, bool cursor_line) {
452   int col = 0;
453   int color = TB_WHITE;
454   int background_color = cursor_line ? /*subtle grey*/240 : TB_BLACK;
455   vector<pair<size_t, size_t> > highlight_ranges = find_all_occurrences(s, Current_search_pattern);
456   tb_set_cursor(0, screen_row);
457   for (col = 0;  col < tb_width() && col+Left_of_screen < SIZE(s);  ++col) {
458     char c = s.at(col+Left_of_screen);  // todo: unicode
459     if (c == '\n') c = ';';  // replace newlines with semi-colons
460     // escapes. hack: can't start a line with them.
461     if (c == '\1') { color = /*red*/1;  c = ' '; }
462     if (c == '\2') { color = TB_WHITE;  c = ' '; }
463     if (in_range(highlight_ranges, col+Left_of_screen))
464       tb_print(c, TB_BLACK, /*yellow*/11);
465     else
466       tb_print(c, color, background_color);
467   }
468   for (;  col < tb_width();  ++col)
469     tb_print(' ', TB_WHITE, background_color);
470 }
471 
472 vector<pair<size_t, size_t> > find_all_occurrences(const string& s, const string& pat) {
473   vector<pair<size_t, size_t> > result;
474   if (pat.empty()) return result;
475   size_t idx = 0;
476   while (true) {
477     size_t next_idx = s.find(pat, idx);
478     if (next_idx == string::npos) break;
479     result.push_back(pair<size_t, size_t>(next_idx, next_idx+SIZE(pat)));
480     idx = next_idx+SIZE(pat);
481   }
482   return result;
483 }
484 
485 bool in_range(const vector<pair<size_t, size_t> >& highlight_ranges, size_t idx) {
486   for (int i = 0;  i < SIZE(highlight_ranges);  ++i) {
487     if (idx >= highlight_ranges.at(i).first && idx < highlight_ranges.at(i).second)
488       return true;
489     if (idx < highlight_ranges.at(i).second) break;
490   }
491   return false;
492 }
493 
494 void load_trace(const char* filename) {
495   ifstream tin(filename);
496   if (!tin) {
497     cerr << "no such file: " << filename << '\n';
498     exit(1);
499   }
500   Trace_stream = new trace_stream;
501   while (has_data(tin)) {
502     tin >> std::noskipws;
503       skip_whitespace_but_not_newline(tin);
504       if (!isdigit(tin.peek())) {
505         string dummy;
506         getline(tin, dummy);
507         continue;
508       }
509     tin >> std::skipws;
510     int depth;
511     tin >> depth;
512     string label;
513     tin >> label;
514     if (*--label.end() == ':') label.erase(--label.end());
515     string line;
516     getline(tin, line);
517     Trace_stream->past_lines.push_back(trace_line(depth, label, line));
518   }
519   cerr << "lines read: " << Trace_stream->past_lines.size() << '\n';
520 }
521 
522 int read_key() {
523   tb_event event;
524   do {
525     tb_poll_event(&event);
526   } while (event.type != TB_EVENT_KEY);
527   return event.key ? event.key : event.ch;
528 }