// Abstract syntax, interpretation and compilation 
// for arithmetic expressions
// sestoft@itu.dk 2007-03-12

// Compile with 

using System;
using System.Collections.Generic;
using System.IO;

namespace Expressions {
  class MainProgram {
    static void Main(string[] args) {
      if (args.Length == 2) {
        Scanner scanner = new Scanner(args[0]);
        Parser parser = new Parser(scanner);
        parser.Parse();
        switch (args[1]) {
          case "run":
            REnv renv = new REnv();
            renv.AllocateLocal("abc");
            renv.GetVariable("abc").value = 17;
            Console.WriteLine(parser.expression.Eval(renv));
            return;
          case "check":
            TEnv tenv = new TEnv();
            tenv.DeclareLocal("abc", Type.intType);
            parser.expression.Check(tenv);
            return;
          case "compile":
            CEnv cenv = new CEnv();
            cenv.DeclareLocal("abc");
            Generator gen = new Generator();
            gen.Emit(new CSTI(17));
            parser.expression.Compile(cenv, gen);
            gen.Emit(Instruction.PRINTI);
            gen.Emit(Instruction.STOP);
            gen.PrintCode();
            int[] bytecode = gen.ToBytecode();
            using (TextWriter wr = new StreamWriter("a.out")) {
              foreach (int b in bytecode) {
                wr.Write(b);
                wr.Write(" ");
              }
            }
            return;
        }
      } 
      Console.WriteLine("Usage: Expressions <expression.txt> [run|check|compile]");
    }
  }

  // Expression abstract syntax

  public abstract class Expression {
    abstract public int Eval(REnv env);
    abstract public Type Check(TEnv env);
    abstract public void Compile(CEnv env, Generator gen);
  }

  public class Constant : Expression {
    private readonly int value;
    private readonly Type type;

    public Constant(int value, Type type) {
      this.value = value;
      this.type = type;
    }

    public override int Eval(REnv env) {
      return value;
    }

    public override Type Check(TEnv env) {
      return type;
    }

    public override void Compile(CEnv env, Generator gen) {
      gen.Emit(new CSTI(value));
    }
  }

  public class Variable : Expression {
    private readonly String name;

    public Variable(String name) {
      this.name = name;
    }

    public override int Eval(REnv env) {
      return env.GetVariable(name).value;
    }

    public override Type Check(TEnv env) {
      return env.GetVariable(name);
    }

    public override void Compile(CEnv env, Generator gen) {
      env.CompileVariable(gen, name);
      gen.Emit(Instruction.LDI);
    }
  }

  public enum Operator {
    Add, Sub, Mul, Div, Neg, Eq, Ne, Lt, Le, Gt, Ge, Not, Bad
  }

  public class BinOp : Expression {
    private readonly Operator op;
    private readonly Expression e1, e2;

    public BinOp(Operator op, Expression e1, Expression e2) {
      this.op = op;
      this.e1 = e1;
      this.e2 = e2;
    }

    public override int Eval(REnv env) {
      int v1 = e1.Eval(env);
      int v2 = e2.Eval(env);
      switch (op) {
        case Operator.Add:
          return v1 + v2;
        case Operator.Div:
          return v1 / v2;
        case Operator.Mul:
          return v1 * v2;
        case Operator.Sub:
          return v1 - v2;
        case Operator.Eq:
          return v1 == v2 ? 1 : 0;
        case Operator.Ne:
          return v1 != v2 ? 1 : 0;
        case Operator.Lt:
          return v1 < v2 ? 1 : 0;
        case Operator.Le:
          return v1 <= v2 ? 1 : 0;
        case Operator.Gt:
          return v1 > v2 ? 1 : 0;
        case Operator.Ge:
          return v1 >= v2 ? 1 : 0;
        default:
          throw new Exception("Unknown binary operator: " + op);
      }
    }

    public override Type Check(TEnv env) {
      Type t1 = e1.Check(env);
      Type t2 = e2.Check(env);
      switch (op) {
        case Operator.Add:
        case Operator.Div:
        case Operator.Mul:
        case Operator.Sub:
          if (t1 == Type.intType && t2 == Type.intType)
            return Type.intType;
          else
            throw new TypeException("Arguments to + - * / must be int");
        case Operator.Eq:
        case Operator.Ge:
        case Operator.Gt:
        case Operator.Le:
        case Operator.Lt:
        case Operator.Ne:
          if (t1 == Type.intType && t2 == Type.intType)
            return Type.boolType;
          else
            throw new TypeException("Arguments to == >= > <= < != must be int");
        default:
          throw new Exception("Unknown binary operator: " + op);
      }
    }

    public override void Compile(CEnv env, Generator gen) {
      e1.Compile(env, gen);
      env.PushTemporary();
      e2.Compile(env, gen);
      switch (op) {
        case Operator.Add:
          gen.Emit(Instruction.ADD);
          break;
        case Operator.Div:
          gen.Emit(Instruction.DIV);
          break;
        case Operator.Mul:
          gen.Emit(Instruction.MUL);
          break;
        case Operator.Sub:
          gen.Emit(Instruction.SUB);
          break;
        case Operator.Eq:
          gen.Emit(Instruction.EQ);
          break;
        case Operator.Ne:
          gen.Emit(Instruction.EQ);
          gen.Emit(Instruction.NOT);
          break;
        case Operator.Ge:
          gen.Emit(Instruction.LT);
          gen.Emit(Instruction.NOT);
          break;
        case Operator.Gt:
          gen.Emit(Instruction.SWAP);
          gen.Emit(Instruction.LT);
          break;
        case Operator.Le:
          gen.Emit(Instruction.SWAP);
          gen.Emit(Instruction.LT);
          gen.Emit(Instruction.NOT);
          break;
        case Operator.Lt:
          gen.Emit(Instruction.LT);
          break;
        default:
          throw new Exception("Unknown binary operator: " + op);
      }
      env.PopTemporary();
    }
  }

  public class UnOp : Expression {
    private readonly Operator op;
    private readonly Expression e1;

    public UnOp(Operator op, Expression e1) {
      this.op = op;
      this.e1 = e1;
    }

    public override int Eval(REnv env) {
      int v1 = e1.Eval(env);
      switch (op) {
        case Operator.Not:
          return v1 == 0 ? 1 : 0;
        case Operator.Neg:
          return -v1;
        default:
          throw new Exception("Unknown unary operator: " + op);
      }
    }

    public override Type Check(TEnv env) {
      Type t1 = e1.Check(env);
      switch (op) {
        case Operator.Neg:
          if (t1 == Type.intType)
            return Type.intType;
          else
            throw new TypeException("Argument to - must be int");
        case Operator.Not:
          if (t1 == Type.boolType)
            return Type.boolType;
          else
            throw new TypeException("Argument to ! must be bool");
        default:
          throw new Exception("Unknown unary operator: " + op);
      }
    }

    public override void Compile(CEnv env, Generator gen) {
      e1.Compile(env, gen);
      switch (op) {
        case Operator.Not:
          gen.Emit(Instruction.NOT);
          break;
        case Operator.Neg:
          gen.Emit(new CSTI(0));
          gen.Emit(Instruction.SWAP);
          gen.Emit(Instruction.SUB);
          break;
        default:
          throw new Exception("Unknown unary operator: " + op);
      }
    }
  }

  // Runtime environments
  // Map a variable name to a Storage object that can hold an int
  // The environment is a stack because of nested scopes

  public class REnv {
    private readonly Stack<Pair<String, Storage>> locals;

    public REnv() {
      locals = new Stack<Pair<String, Storage>>();
    }

    // Find variable in innermost local scope
    public Storage GetVariable(String name) {
      foreach (Pair<String, Storage> variable in locals)
        if (variable.Fst == name)
          return variable.Snd;
      throw new Exception("Unbound variable: " + name);
    }

    // Allocate variable
    public void AllocateLocal(String name) {
      locals.Push(new Pair<String, Storage>(name, new Storage()));
    }

    public void PopEnv() {
      locals.Pop();
    }
  }

  // Runtime storage for a local (int or bool) variable

  public class Storage {
    public int value = 0;
  }

  public struct Pair<T,U> {
    public readonly T Fst;
    public readonly U Snd;

    public Pair(T fst, U snd) {
      this.Fst = fst;
      this.Snd = snd;
    }
  }

  // Types 

  abstract public class Type {
    public static readonly Type intType = new PrimitiveType("int");
    public static readonly Type boolType = new PrimitiveType("bool");
    public static readonly Type errorType = new PrimitiveType("*ERROR*");
  }

  public class PrimitiveType : Type {
    public readonly String name;

    public PrimitiveType(String name) {
      this.name = name;
    }
  }

  // Type checking environments
  // Map a variable name to a Type
  // The environment is a stack because of a nested scopes

  public class TEnv {
    private readonly Stack<Pair<String, Type>> locals;

    public TEnv() {
      locals = new Stack<Pair<String, Type>>();
    }

    public void PushEnv() {
      locals.Push(new Pair<String, Type>());
    }

    public void PopEnv() {
      locals.Pop();
    }

    public void DeclareLocal(String name, Type type) {
      locals.Push(new Pair<String, Type>(name, type));
    }

    public Type GetVariable(String name) {
      foreach (Pair<String, Type> variable in locals)
        if (variable.Fst == name)
          return variable.Snd;
      throw new Exception("Unbound variable: " + name);
    }
  }

  // Compilation environments
  // An implicit map from string to offset (distance from stack top)
  // The environment is a stack because of nested scopes

  public class CEnv {
    private readonly Stack<String> locals;

    public CEnv() {
      locals = new Stack<String>();
    }

    public void PopEnv() {
      locals.Pop();
    }

    public void DeclareLocal(String name) {
      locals.Push(name);
    }

    public void PushTemporary() {
      locals.Push("_ temporary _");
    }

    public void PopTemporary() {
      String s = locals.Pop();
      if (s != "_ temporary _")
        throw new Exception("Internal problem: popping non-temporary");
    }

    public void CompileVariable(Generator gen, String name) {
      int offset = 0;
      foreach (String variableName in locals) {
        if (variableName == name) {
          gen.Emit(Instruction.GETSP);
          gen.Emit(new CSTI(offset));
          gen.Emit(Instruction.SUB);
          return;
        } else
          offset++;
      }
      throw new Exception("Undeclared variable: " + name);
    }
  }

  // Exceptions

  class TypeException : Exception {
    public TypeException(String msg) : base(msg) { }
  }

  // Code generation

  public class Generator {
    private readonly List<Instruction> instructions;

    public Generator() {
      instructions = new List<Instruction>();
    }

    public void Emit(Instruction instr) {
      instructions.Add(instr);
    }

    public int[] ToBytecode() {
      List<int> bytecode = new List<int>();
      foreach (Instruction instr in instructions)
        instr.ToBytecode(bytecode);
      return bytecode.ToArray();
    }

    public void PrintCode() {
      foreach (Instruction instr in instructions)
        Console.WriteLine(instr);
    }
  }

  public abstract class Instruction {
    public readonly Opcode opcode;
    public static readonly Instruction
      ADD = new SimpleInstruction(Opcode.ADD),
      SUB = new SimpleInstruction(Opcode.SUB),
      MUL = new SimpleInstruction(Opcode.MUL),
      DIV = new SimpleInstruction(Opcode.DIV),
      MOD = new SimpleInstruction(Opcode.MOD),
      EQ = new SimpleInstruction(Opcode.EQ),
      LT = new SimpleInstruction(Opcode.LT),
      NOT = new SimpleInstruction(Opcode.NOT),
      DUP = new SimpleInstruction(Opcode.DUP),
      SWAP = new SimpleInstruction(Opcode.SWAP),
      LDI = new SimpleInstruction(Opcode.LDI),
      STI = new SimpleInstruction(Opcode.STI),
      GETBP = new SimpleInstruction(Opcode.GETBP),
      GETSP = new SimpleInstruction(Opcode.GETSP),
      PRINTC = new SimpleInstruction(Opcode.PRINTC),
      PRINTI = new SimpleInstruction(Opcode.PRINTI),
      READ = new SimpleInstruction(Opcode.READ),
      LDARGS = new SimpleInstruction(Opcode.LDARGS),
      STOP = new SimpleInstruction(Opcode.STOP);

    public Instruction(Opcode opcode) {
      this.opcode = opcode;
    }

    public abstract int Size { get; }

    public abstract void ToBytecode(List<int> bytecode);

    public override string ToString() {
      return opcode.ToString();
    }
  }

  public class SimpleInstruction : Instruction {
    public SimpleInstruction(Opcode opcode) : base(opcode) { }

    public override int Size {
      get { return 1; }
    }

    public override void ToBytecode(List<int> bytecode) {
      bytecode.Add((int)opcode);
    }

    public override string ToString() {
      return opcode.ToString();
    }
  }

  public class IntArgInstr : Instruction {
    public readonly int argument;

    public IntArgInstr(Opcode opcode, int argument)
      : base(opcode) {
      this.argument = argument;
    }

    public override int Size {
      get { return 2; }
    }

    public override void ToBytecode(List<int> bytecode) {
      bytecode.Add((int)opcode);
      bytecode.Add(argument);
    }

    public override string ToString() {
      return base.ToString() + " " + argument.ToString();
    }
  }

  public class CSTI : IntArgInstr {
    public CSTI(int argument) : base(Opcode.CSTI, argument) { }
  }

  public class INCSP : IntArgInstr {
    public INCSP(int argument) : base(Opcode.INCSP, argument) { }
  }

  public enum Opcode {
    LABEL = -1, // Unused
    CSTI, ADD, SUB, MUL, DIV, MOD, EQ, LT, NOT,
    DUP, SWAP, LDI, STI, GETBP, GETSP, INCSP,
    GOTO, IFZERO, IFNZRO, CALL, TCALL, RET,
    PRINTI, PRINTC, READ, LDARGS,
    STOP
  }
}