5800 - move `browse_trace` to `tools/` dir

1 files changed, 547 insertions, 0 deletions

diff --git a/tools/browse_trace.cc b/tools/browse_trace.cc
new file mode 100644
index 00000000..b15da9c8
--- /dev/null
+++ b/tools/browse_trace.cc
@@ -0,0 +1,547 @@
+// Warning: zero automated tests
+
+// Includes
+#include "termbox/termbox.h"
+
+#include <stdlib.h>
+#define SIZE(X) (assert((X).size() < (1LL<<(sizeof(int)*8-2))), static_cast<int>((X).size()))
+
+#include <assert.h>
+#include <iostream>
+using std::istream;
+using std::ostream;
+using std::iostream;
+using std::cin;
+using std::cout;
+using std::cerr;
+#include <iomanip>
+#include <string.h>
+#include <string>
+using std::string;
+#include <vector>
+using std::vector;
+#include <set>
+using std::set;
+#include <sstream>
+using std::ostringstream;
+#include <fstream>
+using std::ifstream;
+using std::ofstream;
+#include <map>
+using std::map;
+#include <utility>
+using std::pair;
+// End Includes
+
+// Types
+struct trace_line {
+  string contents;
+  string label;
+  int depth;  // 0 is 'sea level'; positive integers are progressively 'deeper' and lower level
+  trace_line(string c, string l, int d) {
+    contents = c;
+    label = l;
+    depth = d;
+  }
+};
+
+struct trace_stream {
+  vector<trace_line> past_lines;
+};
+
+enum search_direction { FORWARD, BACKWARD };
+// End Types
+
+// from http://stackoverflow.com/questions/152643/idiomatic-c-for-reading-from-a-const-map
+template<typename T> typename T::mapped_type& get(T& map, typename T::key_type const& key) {
+  typename T::iterator iter(map.find(key));
+  assert(iter != map.end());
+  return iter->second;
+}
+template<typename T> typename T::mapped_type const& get(const T& map, typename T::key_type const& key) {
+  typename T::const_iterator iter(map.find(key));
+  assert(iter != map.end());
+  return iter->second;
+}
+template<typename T> typename T::mapped_type const& put(T& map, typename T::key_type const& key, typename T::mapped_type const& value) {
+  // map[key] requires mapped_type to have a zero-arg (default) constructor
+  map.insert(std::make_pair(key, value)).first->second = value;
+  return value;
+}
+template<typename T> bool contains_key(T& map, typename T::key_type const& key) {
+  return map.find(key) != map.end();
+}
+template<typename T> typename T::mapped_type& get_or_insert(T& map, typename T::key_type const& key) {
+  return map[key];
+}
+
+// Globals
+trace_stream* Trace_stream = NULL;
+
+ofstream Trace_file;
+int Display_row = 0;
+int Display_column = 0;
+set<int> Visible;
+int Top_of_screen = 0;
+int Left_of_screen = 0;
+int Last_printed_row = 0;
+map<int, int> Trace_index;  // screen row -> trace index
+
+string Current_search_pattern = "";
+search_direction Current_search_direction = FORWARD;
+// End Globals
+
+bool has_data(istream& in) {
+  return in && !in.eof();
+}
+
+void skip_whitespace_but_not_newline(istream& in) {
+  while (true) {
+    if (!has_data(in)) break;
+    else if (in.peek() == '\n') break;
+    else if (isspace(in.peek())) in.get();
+    else break;
+  }
+}
+
+void load_trace(const char* filename) {
+  ifstream tin(filename);
+  if (!tin) {
+    cerr << "no such file: " << filename << '\n';
+    exit(1);
+  }
+  Trace_stream = new trace_stream;
+  while (has_data(tin)) {
+    tin >> std::noskipws;
+      skip_whitespace_but_not_newline(tin);
+      if (!isdigit(tin.peek())) {
+        string dummy;
+        getline(tin, dummy);
+        continue;
+      }
+    tin >> std::skipws;
+    int depth;
+    tin >> depth;
+    string label;
+    tin >> label;
+    if (*--label.end() == ':') label.erase(--label.end());
+    string line;
+    getline(tin, line);
+    Trace_stream->past_lines.push_back(trace_line(line, label, depth));
+  }
+  cerr << "lines read: " << Trace_stream->past_lines.size() << '\n';
+}
+
+// update Trace_indices for each screen_row on the basis of Top_of_screen and Visible
+void refresh_screen_rows() {
+  int screen_row = 0, index = 0;
+  Trace_index.clear();
+  for (screen_row = 0, index = Top_of_screen;  screen_row < tb_height() && index < SIZE(Trace_stream->past_lines);  ++screen_row, ++index) {
+    // skip lines without depth for now
+    while (!contains_key(Visible, index)) {
+      ++index;
+      if (index >= SIZE(Trace_stream->past_lines)) goto done;
+    }
+    assert(index < SIZE(Trace_stream->past_lines));
+    put(Trace_index, screen_row, index);
+  }
+done:;
+}
+
+void clear_line(int screen_row) {
+  tb_set_cursor(0, screen_row);
+  for (int col = 0;  col < tb_width();  ++col)
+    tb_print(' ', TB_WHITE, TB_BLACK);
+  tb_set_cursor(0, screen_row);
+}
+
+int read_key() {
+  tb_event event;
+  do {
+    tb_poll_event(&event);
+  } while (event.type != TB_EVENT_KEY);
+  return event.key ? event.key : event.ch;
+}
+
+int lines_hidden(int screen_row) {
+  assert(contains_key(Trace_index, screen_row));
+  if (!contains_key(Trace_index, screen_row+1))
+    return SIZE(Trace_stream->past_lines) - get(Trace_index, screen_row);
+  else
+    return get(Trace_index, screen_row+1) - get(Trace_index, screen_row);
+}
+
+bool in_range(const vector<pair<size_t, size_t> >& highlight_ranges, size_t idx) {
+  for (int i = 0;  i < SIZE(highlight_ranges);  ++i) {
+    if (idx >= highlight_ranges.at(i).first && idx < highlight_ranges.at(i).second)
+      return true;
+    if (idx < highlight_ranges.at(i).second) break;
+  }
+  return false;
+}
+
+vector<pair<size_t, size_t> > find_all_occurrences(const string& s, const string& pat) {
+  vector<pair<size_t, size_t> > result;
+  if (pat.empty()) return result;
+  size_t idx = 0;
+  while (true) {
+    size_t next_idx = s.find(pat, idx);
+    if (next_idx == string::npos) break;
+    result.push_back(pair<size_t, size_t>(next_idx, next_idx+SIZE(pat)));
+    idx = next_idx+SIZE(pat);
+  }
+  return result;
+}
+
+void render_line(int screen_row, const string& s, bool cursor_line) {
+  int col = 0;
+  int color = TB_WHITE;
+  int background_color = cursor_line ? /*subtle grey*/240 : TB_BLACK;
+  vector<pair<size_t, size_t> > highlight_ranges = find_all_occurrences(s, Current_search_pattern);
+  tb_set_cursor(0, screen_row);
+  for (col = 0;  col < tb_width() && col+Left_of_screen < SIZE(s);  ++col) {
+    char c = s.at(col+Left_of_screen);  // todo: unicode
+    if (c == '\n') c = ';';  // replace newlines with semi-colons
+    // escapes. hack: can't start a line with them.
+    if (c == '\1') { color = /*red*/1;  continue; }
+    if (c == '\2') { color = TB_WHITE;  continue; }
+    if (in_range(highlight_ranges, col+Left_of_screen))
+      tb_print(c, TB_BLACK, /*yellow*/11);
+    else
+      tb_print(c, color, background_color);
+  }
+  for (;  col < tb_width();  ++col)
+    tb_print(' ', TB_WHITE, background_color);
+}
+
+void search_next(const string& pat) {
+  for (int trace_index = get(Trace_index, Display_row)+1;  trace_index < SIZE(Trace_stream->past_lines);  ++trace_index) {
+    if (!contains_key(Visible, trace_index)) continue;
+    const trace_line& line = Trace_stream->past_lines.at(trace_index);
+    if (line.label.find(pat) == string::npos && line.contents.find(pat) == string::npos) continue;
+    Top_of_screen = trace_index;
+    Display_row = 0;
+    refresh_screen_rows();
+    return;
+  }
+}
+
+void search_previous(const string& pat) {
+  for (int trace_index = get(Trace_index, Display_row)-1;  trace_index >= 0;  --trace_index) {
+    if (!contains_key(Visible, trace_index)) continue;
+    const trace_line& line = Trace_stream->past_lines.at(trace_index);
+    if (line.label.find(pat) == string::npos && line.contents.find(pat) == string::npos) continue;
+    Top_of_screen = trace_index;
+    Display_row = 0;
+    refresh_screen_rows();
+    return;
+  }
+}
+
+void search(const string& pat, search_direction dir) {
+  if (dir == FORWARD) search_next(pat);
+  else search_previous(pat);
+}
+
+search_direction opposite(search_direction dir) {
+  if (dir == FORWARD) return BACKWARD;
+  else return FORWARD;
+}
+
+bool start_search_editor(search_direction dir) {
+  const int bottom_screen_line = tb_height()-1;
+  // run a little editor just in the last line of the screen
+  clear_line(bottom_screen_line);
+  int col = 0;  // screen column of cursor on bottom line. also used to update pattern.
+  tb_set_cursor(col, bottom_screen_line);
+  tb_print('/', TB_WHITE, TB_BLACK);
+  ++col;
+  string pattern;
+  while (true) {
+    int key = read_key();
+    if (key == TB_KEY_ENTER) {
+      if (!pattern.empty()) {
+        Current_search_pattern = pattern;
+        Current_search_direction = dir;
+      }
+      return true;
+    }
+    else if (key == TB_KEY_ESC || key == TB_KEY_CTRL_C) {
+      return false;
+    }
+    else if (key == TB_KEY_ARROW_LEFT) {
+      if (col > /*slash*/1) {
+        --col;
+        tb_set_cursor(col, bottom_screen_line);
+      }
+    }
+    else if (key == TB_KEY_ARROW_RIGHT) {
+      if (col-/*slash*/1 < SIZE(pattern)) {
+        ++col;
+        tb_set_cursor(col, bottom_screen_line);
+      }
+    }
+    else if (key == TB_KEY_HOME || key == TB_KEY_CTRL_A) {
+      col = /*skip slash*/1;
+      tb_set_cursor(col, bottom_screen_line);
+    }
+    else if (key == TB_KEY_END || key == TB_KEY_CTRL_E) {
+      col = SIZE(pattern)+/*skip slash*/1;
+      tb_set_cursor(col, bottom_screen_line);
+    }
+    else if (key == TB_KEY_BACKSPACE || key == TB_KEY_BACKSPACE2) {
+      if (col > /*slash*/1) {
+        assert(col <= SIZE(pattern)+1);
+        --col;
+        // update pattern
+        pattern.erase(col-/*slash*/1, /*len*/1);
+        // update screen
+        tb_set_cursor(col, bottom_screen_line);
+        for (int x = col;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
+          tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
+        tb_print(' ', TB_WHITE, TB_BLACK);
+        tb_set_cursor(col, bottom_screen_line);
+      }
+    }
+    else if (key == TB_KEY_CTRL_K) {
+      int old_pattern_size = SIZE(pattern);
+      pattern.erase(col-/*slash*/1, SIZE(pattern) - (col-/*slash*/1));
+      tb_set_cursor(col, bottom_screen_line);
+      for (int x = col;  x < old_pattern_size+/*slash*/1;  ++x)
+        tb_print(' ', TB_WHITE, TB_BLACK);
+      tb_set_cursor(col, bottom_screen_line);
+    }
+    else if (key == TB_KEY_CTRL_U) {
+      int old_pattern_size = SIZE(pattern);
+      pattern.erase(0, col-/*slash*/1);
+      col = /*skip slash*/1;
+      tb_set_cursor(col, bottom_screen_line);
+      for (int x = /*slash*/1;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
+        tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
+      for (int x = SIZE(pattern)+/*slash*/1;  x < old_pattern_size+/*skip slash*/1;  ++x)
+        tb_print(' ', TB_WHITE, TB_BLACK);
+      tb_set_cursor(col, bottom_screen_line);
+    }
+    else if (key < 128) {  // ascii only
+      // update pattern
+      char c = static_cast<char>(key);
+      assert(col-1 >= 0);
+      assert(col-1 <= SIZE(pattern));
+      pattern.insert(col-/*slash*/1, /*num*/1, c);
+      // update screen
+      for (int x = col;  x < SIZE(pattern)+/*skip slash*/1;  ++x)
+        tb_print(pattern.at(x-/*slash*/1), TB_WHITE, TB_BLACK);
+      ++col;
+      tb_set_cursor(col, bottom_screen_line);
+    }
+  }
+}
+
+void render() {
+  int screen_row = 0;
+  for (screen_row = 0;  screen_row < tb_height();  ++screen_row) {
+    if (!contains_key(Trace_index, screen_row)) break;
+    trace_line& curr_line = Trace_stream->past_lines.at(get(Trace_index, screen_row));
+    ostringstream out;
+    if (screen_row < tb_height()-1) {
+      int delta = lines_hidden(screen_row);
+      // home-brew escape sequence for red
+      if (delta > 1) {
+        if (delta > 999) out << static_cast<char>(1);
+        out << std::setw(6) << delta << "| ";
+        if (delta > 999) out << static_cast<char>(2);
+      }
+      else {
+        out << "        ";
+      }
+    }
+    else {
+      out << "        ";
+    }
+    out << std::setw(4) << curr_line.depth << ' ' << curr_line.label << ": " << curr_line.contents;
+    render_line(screen_row, out.str(), screen_row == Display_row);
+  }
+  // clear rest of screen
+  Last_printed_row = screen_row-1;
+  for (;  screen_row < tb_height();  ++screen_row)
+    render_line(screen_row, "~", /*cursor_line?*/false);
+  // move cursor back to display row at the end
+  tb_set_cursor(0, Display_row);
+}
+
+int main(int argc, char* argv[]) {
+  if (argc != 2) {
+    cerr << "Usage: browse_trace <trace file>\n";
+    return 1;
+  }
+  load_trace(argv[1]);
+  if (!Trace_stream) return 1;
+  cerr << "computing min depth to display\n";
+  int min_depth = 9999;
+  for (int i = 0;  i < SIZE(Trace_stream->past_lines);  ++i) {
+    trace_line& curr_line = Trace_stream->past_lines.at(i);
+    if (curr_line.depth < min_depth) min_depth = curr_line.depth;
+  }
+  cerr << "min depth is " << min_depth << '\n';
+  cerr << "computing lines to display\n";
+  for (int i = 0;  i < SIZE(Trace_stream->past_lines);  ++i) {
+    if (Trace_stream->past_lines.at(i).depth == min_depth)
+      Visible.insert(i);
+  }
+  tb_init();
+  tb_clear();
+  Display_row = Display_column = 0;
+  Top_of_screen = 0;
+  refresh_screen_rows();
+  while (true) {
+    render();
+    int key = read_key();
+    if (key == 'q' || key == 'Q' || key == TB_KEY_CTRL_C) break;
+    if (key == 'j' || key == TB_KEY_ARROW_DOWN) {
+      // move cursor one line down
+      if (Display_row < Last_printed_row) ++Display_row;
+    }
+    else if (key == 'k' || key == TB_KEY_ARROW_UP) {
+      // move cursor one line up
+      if (Display_row > 0) --Display_row;
+    }
+    else if (key == 't') {
+      // move cursor to top of screen
+      Display_row = 0;
+    }
+    else if (key == 'c') {
+      // move cursor to center of screen
+      Display_row = tb_height()/2;
+      while (!contains_key(Trace_index, Display_row))
+        --Display_row;
+    }
+    else if (key == 'b') {
+      // move cursor to bottom of screen
+      Display_row = tb_height()-1;
+      while (!contains_key(Trace_index, Display_row))
+        --Display_row;
+    }
+    else if (key == 'T') {
+      // scroll line at cursor to top of screen
+      Top_of_screen = get(Trace_index, Display_row);
+      Display_row = 0;
+      refresh_screen_rows();
+    }
+    else if (key == 'h' || key == TB_KEY_ARROW_LEFT) {
+      // pan screen one character left
+      if (Left_of_screen > 0) --Left_of_screen;
+    }
+    else if (key == 'l' || key == TB_KEY_ARROW_RIGHT) {
+      // pan screen one character right
+      ++Left_of_screen;
+    }
+    else if (key == 'H') {
+      // pan screen one screen-width left
+      Left_of_screen -= (tb_width() - 5);
+      if (Left_of_screen < 0) Left_of_screen = 0;
+    }
+    else if (key == 'L') {
+      // pan screen one screen-width right
+      Left_of_screen += (tb_width() - 5);
+    }
+    else if (key == 'J' || key == TB_KEY_PGDN || key == TB_KEY_CTRL_F) {
+      // page-down
+      if (Trace_index.find(tb_height()-1) != Trace_index.end()) {
+        Top_of_screen = get(Trace_index, tb_height()-1) + 1;
+        refresh_screen_rows();
+      }
+    }
+    else if (key == 'K' || key == TB_KEY_PGUP || key == TB_KEY_CTRL_B) {
+      // page-up is more convoluted
+      for (int screen_row = tb_height();  screen_row > 0 && Top_of_screen > 0;  --screen_row) {
+        --Top_of_screen;
+        if (Top_of_screen <= 0) break;
+        while (Top_of_screen > 0 && !contains_key(Visible, Top_of_screen))
+          --Top_of_screen;
+      }
+      if (Top_of_screen >= 0)
+        refresh_screen_rows();
+    }
+    else if (key == 'g' || key == TB_KEY_HOME) {
+        Top_of_screen = 0;
+        Last_printed_row = 0;
+        Display_row = 0;
+        refresh_screen_rows();
+    }
+    else if (key == 'G' || key == TB_KEY_END) {
+      // go to bottom of screen; largely like page-up, interestingly
+      Top_of_screen = SIZE(Trace_stream->past_lines)-1;
+      for (int screen_row = tb_height();  screen_row > 0 && Top_of_screen > 0;  --screen_row) {
+        --Top_of_screen;
+        if (Top_of_screen <= 0) break;
+        while (Top_of_screen > 0 && !contains_key(Visible, Top_of_screen))
+          --Top_of_screen;
+      }
+      refresh_screen_rows();
+      // move cursor to bottom
+      Display_row = Last_printed_row;
+      refresh_screen_rows();
+    }
+    else if (key == TB_KEY_CARRIAGE_RETURN) {
+      // expand lines under current by one level
+      assert(contains_key(Trace_index, Display_row));
+      int start_index = get(Trace_index, Display_row);
+      int index = 0;
+      // simultaneously compute end_index and min_depth
+      int min_depth = 9999;
+      for (index = start_index+1;  index < SIZE(Trace_stream->past_lines);  ++index) {
+        if (contains_key(Visible, index)) break;
+        trace_line& curr_line = Trace_stream->past_lines.at(index);
+        assert(curr_line.depth > Trace_stream->past_lines.at(start_index).depth);
+        if (curr_line.depth < min_depth) min_depth = curr_line.depth;
+      }
+      int end_index = index;
+      // mark as visible all intervening indices at min_depth
+      for (index = start_index;  index < end_index;  ++index) {
+        trace_line& curr_line = Trace_stream->past_lines.at(index);
+        if (curr_line.depth == min_depth) {
+          Visible.insert(index);
+        }
+      }
+      refresh_screen_rows();
+    }
+    else if (key == TB_KEY_BACKSPACE || key == TB_KEY_BACKSPACE2) {
+      // collapse all lines under current
+      assert(contains_key(Trace_index, Display_row));
+      int start_index = get(Trace_index, Display_row);
+      int index = 0;
+      // end_index is the next line at a depth same as or lower than start_index
+      int initial_depth = Trace_stream->past_lines.at(start_index).depth;
+      for (index = start_index+1;  index < SIZE(Trace_stream->past_lines);  ++index) {
+        if (!contains_key(Visible, index)) continue;
+        trace_line& curr_line = Trace_stream->past_lines.at(index);
+        if (curr_line.depth <= initial_depth) break;
+      }
+      int end_index = index;
+      // mark as visible all intervening indices at min_depth
+      for (index = start_index+1;  index < end_index;  ++index) {
+        Visible.erase(index);
+      }
+      refresh_screen_rows();
+    }
+    else if (key == '/') {
+      if (start_search_editor(FORWARD))
+        search(Current_search_pattern, Current_search_direction);
+    }
+    else if (key == '?') {
+      if (start_search_editor(BACKWARD))
+        search(Current_search_pattern, Current_search_direction);
+    }
+    else if (key == 'n') {
+      if (!Current_search_pattern.empty())
+        search(Current_search_pattern, Current_search_direction);
+    }
+    else if (key == 'N') {
+      if (!Current_search_pattern.empty())
+        search(Current_search_pattern, opposite(Current_search_direction));
+    }
+  }
+  tb_clear();
+  tb_shutdown();
+  return 0;
+}