// 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 Cursor_row = 0;  // screen coordinate
set<int> Visible;
int Top_of_screen = 0;  // trace coordinate
int Left_of_screen = 0;  // trace coordinate
int Last_printed_row = 0;  // screen coordinate
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';
}

void refresh_screen_rows() {  // Top_of_screen, Visible -> Trace_index
  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) {  // -> screen
  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;
}

int bg_color(int depth, int trace_index, int screen_row) {
  if (screen_row == Cursor_row) {
    if (trace_index == 0) return /*subtle grey*/240;  // ignore the zero-depth sentinel at start of trace
    if (depth > 0) return /*subtle grey*/240;
    else return /*subtle red*/88;
  }
  if (trace_index == 0) return TB_BLACK;  // ignore the zero-depth sentinel at start of trace
  if (depth == 0) return /*red*/1;
  if (depth == 1) return /*orange*/166;
  // start at black, gradually lighten at deeper levels
  return TB_BLACK + ((depth-2) % 6)*2;
}

void render_line(int screen_row, const string& s, int bg) {  // -> screen
  int col = 0;
  int color = TB_WHITE;
  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) {
    char c = ' ';
    if (col+Left_of_screen < SIZE(s))
      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, bg);
  }
}

void search_next(const string& pat) {
  for (int trace_index = get(Trace_index, Cursor_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;
    Cursor_row = 0;
    refresh_screen_rows();
    return;
  }
}

void search_previous(const string& pat) {
  for (int trace_index = get(Trace_index, Cursor_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;
    Cursor_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_curso<style>pre { line-height: 125%; }
td.linenos .normal { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
span.linenos { color: inherit; background-color: transparent; padding-left: 5px; padding-right: 5px; }
td.linenos .special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
span.linenos.special { color: #000000; background-color: #ffffc0; padding-left: 5px; padding-right: 5px; }
.highlight .hll { background-color: #ffffcc }
.highlight .c { color: #888888 } /* Comment */
.highlight .err { color: #a61717; background-color: #e3d2d2 } /* Error */
.highlight .k { color: #008800; font-weight: bold } /* Keyword */
.highlight .ch { color: #888888 } /* Comment.Hashbang */
.highlight .cm { color: #888888 } /* Comment.Multiline */
.highlight .cp { color: #cc0000; font-weight: bold } /* Comment.Preproc */
.highlight .cpf { color: #888888 } /* Comment.PreprocFile */
.highlight .c1 { color: #888888 } /* Comment.Single */
.highlight .cs { color: #cc0000; font-weight: bold; background-color: #fff0f0 } /* Comment.Special */
.highlight .gd { color: #000000; background-color: #ffdddd } /* Generic.Deleted */
.highlight .ge { font-style: italic } /* Generic.Emph */
.highlight .ges { font-weight: bold; font-style: italic } /* Generic.EmphStrong */
.highlight .gr { color: #aa0000 } /* Generic.Error */
.highlight .gh { color: #333333 } /* Generic.Heading */
.highlight .gi { color: #000000; background-color: #ddffdd } /* Generic.Inserted */
.highlight .go { color: #888888 } /* Generic.Output */
.highlight .gp { color: #555555 } /* Generic.Prompt */
.highlight .gs { font-weight: bold } /* Generic.Strong */
.highlight .gu { color: #666666 } /* Generic.Subheading */
.highlight .gt { color: #aa0000 } /* Generic.Traceback */
.highlight .kc { color: #008800; font-weight: bold } /* Keyword.Constant */
.highlight .kd { color: #008800; font-weight: bold } /* Keyword.Declaration */
.highlight .kn { color: #008800; font-weight: bold } /* Keyword.Namespace */
.highlight .kp { color: #008800 } /* Keyword.Pseudo */
.highlight .kr { color: #008800; font-weight: bold } /* Keyword.Reserved */
.highlight .kt { color: #888888; font-weight: bold } /* Keyword.Type */
.highlight .m { color: #0000DD; font-weight: bold } /* Literal.Number */
.highlight .s { color: #dd2200; background-color: #fff0f0 } /* Literal.String */
.highlight .na { color: #336699 } /* Name.Attribute */
.highlight .nb { color: #003388 } /* Name.Builtin */
.highlight .nc { color: #bb0066; font-weight: bold } /* Name.Class */
.highlight .no { color: #003366; font-weight: bold } /* Name.Constant */
.highlight .nd { color: #555555 } /* Name.Decorator */
.highlight .ne { color: #bb0066; font-weight: bold } /* Name.Exception */
.highlight .nf { color: #0066bb; font-weight: bold } /* Name.Function */
.highlight .nl { color: #336699; font-style: italic } /* Name.Label */
.highlight .nn { color: #bb0066; font-weight: bold } /* Name.Namespace */
.highlight .py { color: #336699; font-weight: bold } /* Name.Property */
.highlight .nt { color: #bb0066; font-weight: bold } /* Name.Tag */
.highlight .nv { color: #336699 } /* Name.Variable */
.highlight .ow { color: #008800 } /* Operator.Word */
.highlight .w { color: #bbbbbb } /* Text.Whitespace */
.highlight .mb { color: #0000DD; font-weight: bold } /* Literal.Number.Bin */
.highlight .mf { color: #0000DD; font-weight: bold } /* Literal.Number.Float */
.highlight .mh { color: #0000DD; font-weight: bold } /* Literal.Number.Hex */
.highlight .mi { color: #0000DD; font-weight: bold } /* Literal.Number.Integer */
.highlight .mo { color: #0000DD; font-weight: bold } /* Literal.Number.Oct */
.highlight .sa { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Affix */
.highlight .sb { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Backtick */
.highlight .sc { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Char */
.highlight .dl { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Delimiter */
.highlight .sd { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Doc */
.highlight .s2 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Double */
.highlight .se { color: #0044dd; background-color: #fff0f0 } /* Literal.String.Escape */
.highlight .sh { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Heredoc */
.highlight .si { color: #3333bb; background-color: #fff0f0 } /* Literal.String.Interpol */
.highlight .sx { color: #22bb22; background-color: #f0fff0 } /* Literal.String.Other */
.highlight .sr { color: #008800; background-color: #fff0ff } /* Literal.String.Regex */
.highlight .s1 { color: #dd2200; background-color: #fff0f0 } /* Literal.String.Single */
.highlight .ss { color: #aa6600; background-color: #fff0f0 } /* Literal.String.Symbol */
.highlight .bp { color: #003388 } /* Name.Builtin.Pseudo */
.highlight .fm { color: #0066bb; font-weight: bold } /* Name.Function.Magic */
.highlight .vc { color: #336699 } /* Name.Variable.Class */
.highlight .vg { color: #dd7700 } /* Name.Variable.Global */
.highlight .vi { color: #3333bb } /* Name.Variable.Instance */
.highlight .vm { color: #336699 } /* Name.Variable.Magic */
.highlight .il { color: #0000DD; font-weight: bold } /* Literal.Number.Integer.Long */</style><div class="highlight"><pre><span></span><span class="c1">//: Allow instructions to mention literals directly.</span>
<span class="c1">//:</span>
<span class="c1">//: This layer will transparently move them to the global segment (assumed to</span>
<span class="c1">//: always be the second segment).</span>

<span class="o">:</span><span class="p">(</span><span class="n">scenario</span><span class="w"> </span><span class="n">transform_literal_string</span><span class="p">)</span>
<span class="o">==</span><span class="w"> </span><span class="n">code</span>
<span class="n">b8</span><span class="o">/</span><span class="n">copy</span><span class="w">  </span><span class="s">&quot;test&quot;</span><span class="o">/</span><span class="n">imm32</span>
<span class="o">==</span><span class="w"> </span><span class="n">data</span><span class="w">  </span><span class="err">#</span><span class="w"> </span><span class="n">need</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">manually</span><span class="w"> </span><span class="n">create</span><span class="w"> </span><span class="k">this</span><span class="w"> </span><span class="k">for</span><span class="w"> </span><span class="n">now</span>
<span class="o">+</span><span class="n">transform</span><span class="o">:</span><span class="w"> </span><span class="o">--</span><span class="w"> </span><span class="n">move</span><span class="w"> </span><span class="n">literal</span><span class="w"> </span><span class="n">strings</span><span class="w"> </span><span class="n">to</span><span class="w"> </span><span class="n">data</span><span class="w"> </span><span class="n">segment</span>
<span class="o">+</span><span class="n">transform</span><span class="o">:</span><span class="w"> </span><span class="n">adding</span><span class="w"> </span><span class="n">global</span><span class="w"> </span><span class="n">variable</span><span class="w"> </span><span class="err">&#39;</span><span class="n">__subx_global_1</span><span class="err">&#39;</span><span class="w"> </span><span class="n">containing</span><span class="w"> </span><span class="s">&quot;test&quot;</span>
<span class="o">+</span><span class="n">transform</span><span class="o">:</span><span class="w"> </span><span class="n">instruction</span><span class="w"> </span><span class="n">after</span><span class="w"> </span><span class="n">transform</span><span class="o">:</span><span class="w"> </span><span class="err">&#39;</span><span class="n">b8</span><span class="w"> </span><span class="n">__subx_global_1</span><span class="err">&#39;</span>

<span class="c1">//: We don&#39;t rely on any transforms running in previous layers, but this layer</span>
<span class="c1">//: knows about labels and global variables and will emit them for previous</span>
<span class="c1">//: layers to transform.</span>
<span class="o">:</span><span class="p">(</span><span class="n">after</span><span class="w"> </span><span class="s">&quot;Begin Transforms&quot;</span><span class="p">)</span>
<span class="c1">//