import "io"

manifest { htsize = 100 }

let htable = vec(htsize);

let hash(s) be
{ let h = 93291, i = 0;
  while true do
  { let c = byte i of s;
    if c = 0 then break;
    h := h * 69 + c;
    i +:= 1 }
  resultis (h bitand 0x7FFFFFFF) rem htsize }

let streql(s, t) be
{ let i = 0;
  while true do
  { let a = byte i of s, b = byte i of t;
    if a /= b then resultis false;
    if a = 0 then resultis true;
    i +:= 1; } }

manifest
{ he_string = 0, he_decl = 1, he_next = 2, sizeof_he = 3 }

let id(s) be
{ let h = hash(s);
  let p = htable ! h;
  while p /= nil do
  { if streql(s, p!he_string) then
      resultis p;
    p := p!he_next }
  p := newvec(sizeof_he);
  p!he_string := s;
  p!he_decl := nil;
  p!he_next := htable!h;
  htable!h := p;
  resultis p }

manifest
{ nd_size = 0, nd_type = 1 }

let n(a) be
{ let len = numbargs();
  let p = newvec(len + 1);
  let arg = @a;
  p!nd_size := len;
  for i = 0 to len-1 do
    p!(i+1) := arg!i;
  resultis p }

let pind(s, n) be
{ for i = 1 to n do
    outch(' ');
  outs(s) }

manifest
{ NT_LET = 1, NT_ASSIGN = 2, NT_NUMBER = 3, NT_VAR = 4, NT_SEQ = 5, NT_IF = 6, NT_WHILE = 7,
  NT_ADD = 8, NT_SUB = 9, NT_MUL = 10, NT_DIV = 11, NT_EQUAL = 12, NT_LESS = 13, NT_LESSEQ = 14 }

let num_local = 0;

let print_op(n, rega, regb) be
{ switchon n!nd_type into
  { case NT_ADD:
      out("    ADD   r%d, r%d\n", rega, regb);
      endcase;
    case NT_SUB:
      out("    SUB   r%d, r%d\n", rega, regb);
      endcase;
    case NT_MUL:
      out("    MUL   r%d, r%d\n", rega, regb);
      endcase;
    case NT_DIV:
      out("    DIV   r%d, r%d\n", rega, regb);
      endcase;
    default:
      out("print_op given %d\n", n!nd_type); } }

let printexpr(n) be
{ outs("( ");
  print(n!2, 0);
  switchon n!nd_type into
  { case NT_ADD:
      outs(" + ");
      endcase;
    case NT_SUB:
      outs(" - ");
      endcase;
    case NT_MUL:
      outs(" * ");
      endcase;
    case NT_DIV:
      outs(" / ");
      endcase;
    case NT_EQUAL:
      outs(" = ");
      endcase;
    case NT_LESS:
      outs(" < ");
      endcase;
    case NT_LESSEQ:
      outs(" < ");
      endcase; }
  print(n!3, 0);
  outs(" )") }

and print(n, ind) be
{ switchon n!nd_type into
  { case NT_LET:
    { pind("LET", ind);
      out(" %s", n!2!he_string);
      for i = 3 to n!nd_size do
        out(", %s", n!i!he_string);
      outs(";\n");
      endcase }
    case NT_ASSIGN:
    { pind("", ind);
      print(n!2, ind);
      outs(" := ");
      print(n!3, ind);
      outs(";\n");
      endcase }
    case NT_NUMBER:
    { outno(n!2);
      endcase }
    case NT_VAR:
    { out("%s", n!2!he_string);
      endcase }
    case NT_SEQ:
    { pind("{\n", ind);
      for i = 2 to n!nd_size do
        print(n!i, ind+3);
      pind("}\n", ind);
      endcase }
    case NT_IF:
    { pind("IF ", ind);
      print(n!2, ind);
      outs(" THEN\n");
      print(n!3, ind+3);
      endcase }
    case NT_WHILE:
    { pind("WHILE ", ind);
      print(n!2, ind);
      outs(" DO\n");
      print(n!3, ind+3);
      endcase }
    case NT_ADD: case NT_SUB: case NT_MUL: case NT_DIV: case NT_EQUAL: case NT_LESS:
    case NT_LESSEQ:
    { printexpr(n);
      endcase }
    default:
    { out("Unknown node type %d\n", n!nd_type);
      endcase } } }

and codegen_expr(n, reg) be
{ switchon n!nd_type into
  { case NT_NUMBER:
    { out("    LOAD  R%d, %d\n", reg, n!2);
      endcase }
    case NT_VAR:
    { out("    LOAD  R%d, [FP-%d]\n", reg, n!2!he_decl);
      endcase }
    case NT_ADD: case NT_SUB: case NT_MUL: case NT_DIV: case NT_EQUAL: case NT_LESS:
    case NT_LESSEQ:
    { codegen_expr(n!2, reg);
      codegen_expr(n!3, reg+1);
      print_op(n, reg, reg+1);
      endcase }
    default:
    { out("Unknown node type %d\n", n!nd_type);
      endcase } } }

and codegen_dest(n) be
{ switchon n!nd_type into
  { case NT_VAR:
    { out("[FP-%d]\n", n!2!he_decl);
      endcase }
    default:
    { out("Unknown node type %d\n", n!nd_type);
      endcase } } }

and codegen_jump_false(n, lab) be
{ out("// jump if false to L%d\n", lab); }

and codegen_stmt(n) be
{ let ind = 0;
  static { labels = 0 }
  outch('\n');
  switchon n!nd_type into
  { case NT_LET:
    { let total = 0;
      outs("    LOAD  FP, SP\n");
      for i = 2 to n!nd_size do
      { num_local +:= 1;
        out("declaring %s as FP-%d\n", n!i!he_string, num_local);
        n!i!he_decl := num_local;
        total +:= 1; }
      out("    SUB   SP, %d\n", total);
      endcase }
    case NT_ASSIGN:
    { codegen_expr(n!3, 1);
      out("    STORE R1, ");
      codegen_dest(n!2);
      endcase }
    case NT_SEQ:
    { for i = 2 to n!nd_size do
        codegen_stmt(n!i);
      endcase }
    case NT_IF:
    { pind("IF ", ind);
      print(n!2, ind);
      outs(" THEN\n");
      print(n!3, ind+3);
      endcase }
    case NT_WHILE:
    { let endlabel, looplabel;
      looplabel := labels + 1;
      endlabel := labels + 2;
      labels +:= 2;
      out("L%d:", looplabel);     // loop back label
      codegen_jump_false(n!2, endlabel);
      codegen_stmt(n!3);
      out("    JUMP  L%d\n", looplabel);
      out("L%d:\n", endlabel);
      endcase }
    default:
    { out("Unknown node type %d\n", n!nd_type);
      endcase } } }

let run() be
{
  let s1 = n(NT_LET, id("n"), id("fac"), id("i"));
  let s2 = n(NT_ASSIGN, n(NT_VAR, id("n")),
                        n(NT_NUMBER, 7));
  let s3 = n(NT_ASSIGN, n(NT_VAR, id("fac")),
                        n(NT_NUMBER, 1));
  let s4 = n(NT_ASSIGN, n(NT_VAR, id("i")),
                        n(NT_NUMBER, 1));
  let s5 = n(NT_ASSIGN, n(NT_VAR, id("fac")),
                        n(NT_MUL, n(NT_VAR, id("fac")),
                                  n(NT_VAR, id("i"))));
  let s6 = n(NT_ASSIGN, n(NT_VAR, id("i")),
                        n(NT_ADD, n(NT_VAR, id("i")),
                                  n(NT_NUMBER, 1)));
  let s7 = n(NT_WHILE, n(NT_LESSEQ, n(NT_VAR, id("i")),
                                    n(NT_VAR, id("n"))),
                       n(NT_SEQ, s5, s6));
  let s = n(NT_SEQ, s1, s2, s3, s4, s7);
  print(s, 0);
  codegen_stmt(s) }

let start() be
{ let heap = vec(10000);
  init(heap, 10000);
  for i = 0 to htsize-1 do
    htable!i := nil;
  run() }

/*
  let s1 = n(NT_LET, id("x"), id("y"));
  let s2 = n(NT_ASSIGN, n(NT_VAR, id("x")),
                        n(NT_NUMBER, 123));
  let s3 = n(NT_ASSIGN, n(NT_VAR, id("y")),
                        n(NT_MUL, n(NT_ADD, n(NT_VAR, id("x")),
                                            n(NT_NUMBER, 1)),
                                  n(NT_SUB, n(NT_VAR, id("x")),
                                            n(NT_NUMBER, 2))));
  let s = n(NT_SEQ, s1, s2, s3);

*/