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

using M17N;
using M17N.Core;

namespace M17N.Core
{
  public class MExpression
  {
    private static MSymbol Mvarref = "symbol-value";
    private static MSymbol Mdefun = "defun";
    private static MSymbol Mcond = "cond";
    private static MSymbol Mprogn = "progn";
    private static MSymbol Mwhen = "when";

    public class Domain
    {
      private Domain parent;
      internal MPlist functions = new MPlist ();
      internal MPlist bindings = new MPlist ();
      private Stack<MPlist> boundaries = new Stack<MPlist> ();
      internal Translator translator;
      public object context;

      internal Domain ()
      {
	boundaries.Push (bindings);
      }

      public Domain (object context) : this (basic, context) { }

      public Domain (Domain parent, object context)
      {
	this.parent = parent;
	this.context = context;
	boundaries.Push (bindings);
      }

      public void AddTranslator (Translator translator)
      {
	if (this.translator == null)
	  this.translator = translator;
	else
	  this.translator += translator;
      }

      public void Bind (MSymbol sym, object value)
      {
	bindings = bindings.Cons (sym, value);
      }

      public MPlist SetBoundary ()
      {
	boundaries.Push (bindings);
	return bindings;
      }

      public void UnboundTo (MPlist boundary)
      {
	while (boundary != boundaries.Pop ());
	while (bindings != boundary)
	  bindings = bindings.next;
      }

      public void Defun (string name, Builtin builtin, int min_arg, int max_arg)
      {
	Defun (name, builtin, min_arg, max_arg, false);
      }

      public void Defun (string name, Builtin builtin, int min_arg, int max_arg,
			 bool specialp)
      {
	MSymbol sym = name;
	Function func = (Function) functions.Get (sym);

	if (func != null)
	  {
	    if (func.min_arg < min_arg || func.max_arg > max_arg)
	      throw new Exception ("Incompatible argument numbers to override: "
				   + name);
	    func.builtin = builtin;
	    func.lambda = null;
	    func.min_arg = min_arg;
	    func.max_arg = max_arg;
	    func.specialp = specialp;
	  }
	else
	  {
	    func = new Function (sym, builtin, min_arg, max_arg, specialp);
	    functions = functions.Cons (sym, func);
	  }
      }

      public void Defun (MSymbol sym, MPlist args, MPlist body)
      {
	Function func = (Function) functions.Get (sym);

	if (func != null)
	  {
	    int nargs = args == null ? 0 : args.Count;

	    if (func.min_arg < nargs || func.max_arg > nargs)
	      throw new Exception ("Incompatible argument numbers to override: "
				   + sym);
	    func.lambda.SetArgs (args);
	    func.lambda.SetBody (body, this);
	    func.builtin = null;
	  }
	else
	  {
	    func = new Function (sym, args, body, this);
	    functions = functions.Cons (sym, func);
	  }	    
      }

      public void Defun (XmlNode node)
      {
	MSymbol sym = node.Attributes["id"].Value;
	Function func = (Function) functions.Get (sym);

	if (func != null)
	  {
	    XmlNode args = node.FirstChild;
	    int nargs = args.Name == "args" ? args.ChildNodes.Count : 0;

	    if (func.min_arg < nargs || func.max_arg > nargs)
	      throw new Exception ("Incompatible argument numbers to override: "
				   + sym);
	    func.lambda.Set (node, this);
	    func.builtin = null;
	  }
	else
	  {
	    func = new Function (sym, node, this);
	    functions = functions.Cons (sym, func);
	  }	    
      }

      internal Function GetFunc (MSymbol name)
      {
	Function func = (Function) functions.Get (name);

	if (func == null)
	  {
	    if (parent != null)
	      return parent.GetFunc (name);
	    throw new Exception ("Unknown function: " + name);
	  }
	return func;
      }

      public bool CopyFunc (Domain domain, MSymbol name)
      {
	Function func = (Function) functions.Get (name);
	if (func == null)
	  return false;
	domain.functions = domain.functions.Cons (name, func);
	return true;
      }

      public void CopyFunc (Domain domain)
      {
	foreach (MPlist p in functions)
	  domain.functions = domain.functions.Cons (p.key, p.val);
      }

      public object GetValue (MSymbol name)
      {
	MPlist slot = bindings.Find (name);

	if (slot == null)
	  {
	    if (parent != null)
	      return parent.GetValue (name);
	    throw new Exception ("Unbound variable: " + name);
	  }
	return slot.val;
      }

      public object SetValue (MSymbol name, object val)
      {
	MPlist boundary = boundaries.Peek ();

	for (MPlist plist = bindings; plist != boundary; plist = plist.next)
	  if (plist.key == name)
	    {
	      plist.val = val;
	      return val;
	    }
	bindings = bindings.Cons (name, val);
	return val;
      }

      public bool IsBound (MSymbol name)
      {
	return (bindings.Find (name) != null);
      }

      public void Translate (MPlist plist)
      {
	if (parent != null)
	  parent.Translate (plist);
	if (translator != null)
	  for (MPlist p = plist; ! p.IsEmpty; p = p.next)
	    translator (p, this);
      }

      public override string ToString ()
      {
	string str = "<(functions";
	foreach (MPlist p in functions)
	  str += " " + p.key;
	str += ") (bindings " + bindings + ")";
	if (context != null)
	  str += " (" + context + ")";
	str += ">";
	return str;
      }
    }

    public delegate object Builtin (MExpression[] args, Domain domain);
    public delegate void Translator (MPlist plist, Domain domain);

    internal class Function
    {
      internal class Lambda
      {
	internal MSymbol[] args;
	internal MExpression[] body;

	public Lambda (MPlist args, MPlist body, Domain domain)
	{
	  SetArgs (args);
	  SetBody (body, domain);
	}

	public Lambda (XmlNode node, Domain domain)
	{
	  Set (node, domain);
	}

	public void SetArgs (MPlist args)
	{
	  int len = args == null ? 0 : args.Count;

	  if (this.args == null)
	    this.args = new MSymbol[len];
	  for (int i = 0; i < len; i++, args = args.next)
	    this.args[i] = args.Symbol;
	}

	public void SetBody (MPlist body, Domain domain)
	{
	  int len = body == null ? 0 : body.Count;
	  if (this.body == null)
	    this.body = new MExpression[len];
	  for (int i = 0; i < len; i++, body = body.next)
	    {
	      domain.Translate (body);
	      this.body[i] = new MExpression (body.key, body.val, domain);
	    }
	}

	public void Set (XmlNode node, Domain domain)
	{
	  XmlNodeList body = node.ChildNodes;
	  int idx = 0;

	  if (body[0].Name == "args")
	    {
	      XmlNodeList args = body[0].ChildNodes;
	      if (this.args == null)
		this.args = new MSymbol[args.Count];
	      for (int i = 0; i < args.Count; i++)
		this.args[i] = args[i].InnerText;
	      idx++;
	    }
	  else if (this.args == null)
	    this.args = new MSymbol[0];
	  if (this.body == null)
	    this.body = new MExpression[body.Count - idx];
	  for (int i = 0; idx < body.Count; i++, idx++)
	    this.body[i] = new MExpression (body[idx], domain);
	}
      }

      public readonly MSymbol Name;
      public Builtin builtin;
      public int min_arg, max_arg;
      internal Lambda lambda;
      public bool specialp = false;

      internal static Function ignore, varref, block;

      public Function (MSymbol name, Builtin builtin,
		       int min_arg, int max_arg, bool specialp)
      {
	Name = name;
	this.builtin = builtin;
	this.min_arg = min_arg;
	this.max_arg = max_arg;
	this.specialp = specialp;
      }

      internal Function (MSymbol name, MPlist args, MPlist body,
			 Domain domain)
      {
	Name = name;
	lambda = new Lambda (args, body, domain);
	this.min_arg = this.max_arg = lambda.args.Length;
      }

      internal Function (MSymbol name, XmlNode node, Domain domain)
      {
	Name = name;
	lambda = new Lambda (node, domain);
	this.min_arg = this.max_arg = lambda.args.Length;
      }

      private Function ()
      {
	Name = MSymbol.nil;
      }

      static Function ()
      {
	ignore = new Function ();
	varref = new Function (Mvarref, get_value, 1, 1, true);
	block = new Function (Mprogn, progn, 0, -1, true);
      }

      private static object get_value (MExpression[] args, Domain domain)
      {
	return domain.GetValue ((MSymbol) args[0].val);
      }

      public object Call (MExpression[] args, Domain domain)
      {
	if (builtin != null)
	  {
	    if (! specialp)
	      foreach (MExpression e in args)
		e.Eval (domain);
	    return builtin (args, domain);
	  }
	if (lambda == null)
	  return null;
	MPlist orig_bindings = domain.bindings;
	object result = false;
	try {
	  int i = 0;
	  foreach (MSymbol arg in lambda.args)
	    domain.Bind (arg, args[i++].Eval (domain));
	  foreach (MExpression e in lambda.body)
	    result = e.Eval (domain);
	} finally {
	  domain.bindings = orig_bindings;
	}
	return result;
      }
    }

    private static Domain basic;

    static MExpression ()
    {
      basic = new Domain ();

      basic.Defun ("set", set_value, 2, 2, true);
      basic.Defun ("=", set_value, 2, 2, true);
      basic.Defun ("!", not, 1, 1, false);
      basic.Defun ("+", plus, 2, -1, false);
      basic.Defun ("*", multi, 2, -1, false);
      basic.Defun ("-", minus, 1, -1, false);
      basic.Defun ("/", divide, 2, -1, false);
      basic.Defun ("%", percent, 2, -1, false);
      basic.Defun ("|", logior, 2, -1, false);
      basic.Defun ("&", logand, 2, -1, false);
      basic.Defun ("+=", pluseq, 2, -1, true);
      basic.Defun ("*=", multieq, 2, -1, true);
      basic.Defun ("-=", minuseq, 2, -1, true);
      basic.Defun ("/=", divideeq, 2, -1, true);
      basic.Defun ("%=", percenteq, 2, -1, true);
      basic.Defun ("|=", logioreq, 2, -1, true);
      basic.Defun ("&=", logandeq, 2, -1, true);
      basic.Defun ("<<", lshift, 2, 2, false);
      basic.Defun (">>", rshift, 2, 2, false);
      basic.Defun ("<<=", lshifteq, 2, 2, true);
      basic.Defun (">>=", rshifteq, 2, 2, true);
      basic.Defun ("==", eq, 2, -1, false);
      basic.Defun ("!=", noteq, 2, 2, false);
      basic.Defun ("<", less, 2, -1, false);
      basic.Defun ("<=", lesseq, 2, -1, false);
      basic.Defun (">", more, 2, -1, false);
      basic.Defun (">=", moreeq, 2, -1, false);
      basic.Defun ("progn", progn, 0, -1, true);
      basic.Defun ("if", ifclause, 2, -1, true);
      basic.Defun ("when", whenclause, 1, -1, true);
      basic.Defun ("while", whileclause, 1, -1, true);

      basic.AddTranslator (new Translator (translate_cond));
    }

    private static object set_value (MExpression[] args, Domain domain)
    {
      return domain.SetValue ((MSymbol) args[0].args[0].val,
			      args[1].Eval (domain));
    }

    private static object not (MExpression[] args, Domain domain)
    {
      if (args[0].val is int)
	return (int) args[0].val == 0;
      if (args[0].val is bool)
	return ! ((bool) args[0].val);
      return true;
    }

    private static object plus (MExpression[] args, Domain domain)
    {
      if (args[0].val is int)
	{
	  int n = 0;
	  foreach (MExpression e in args)
	    n += (int) e.val;
	  return n;
	}
      else if (args[0].val is MText)
	{
	  MText mt = new MText ();
	  foreach (MExpression e in args)
	    mt += (MText) e.val;
	  return mt;
	}
      throw new Exception ("Not an integer nor MText: " + args[0].val);
    }

      private static object multi (MExpression[] args, Domain domain)
      {
	int n = 1;
	foreach (MExpression e in args)
	  n *= (int) e.val;
	return n;
      }

      private static object minus (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;
	if (args.Length == 1)
	  return - n;
	for (int i = 1; i < args.Length; i++)
	  n -= (int) args[i].val;
	return n;
      }

      private static object divide (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;
	for (int i = 1; i < args.Length; i++)
	  n /= (int) args[i].val;
	return n;
      }

      private static object percent (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;
	for (int i = 1; i < args.Length; i++)
	  n %= (int) args[i].val;
	return n;
      }

      private static object logior (MExpression[] args, Domain domain)
      {
	int n = 0;
	foreach (MExpression e in args)
	  n |= (int) e.val;
	return n;
      }

      private static object logand (MExpression[] args, Domain domain)
      {
	int n = 0;
	foreach (MExpression e in args)
	  n &= (int) e.val;
	return n;
      }

      private static object pluseq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	object val = domain.GetValue (sym);

	if (val is int)
	  {
	    int n = (int) val;
	    for (int i = 1; i < args.Length; i++)
	      n += (int) args[i].Eval (domain);
	    val = n;
	  }
	else if (val is MText)
	  {
	    MText mt = (MText) val;
	    for (int i = 1; i < args.Length; i++)
	      mt.Cat ((MText) args[i].Eval (domain));
	    val = mt;
	  }
	domain.SetValue (sym, val);
	return val;
      }

      private static object multieq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	for (int i = 1; i < args.Length; i++)
	  n *= (int) args[i].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object minuseq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	for (int i = 1; i < args.Length; i++)
	  n -= (int) args[i].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object divideeq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	for (int i = 1; i < args.Length; i++)
	  n /= (int) args[i].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object percenteq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	for (int i = 1; i < args.Length; i++)
	  n %= (int) args[i].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object logioreq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	for (int i = 1; i < args.Length; i++)
	  n |= (int) args[i].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object logandeq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	for (int i = 1; i < args.Length; i++)
	  n &= (int) args[i].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object lshift (MExpression[] args, Domain domain)
      {
	return (int) args[0].val << (int) args[1].val;
      }

      private static object lshifteq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	n <<= (int) args[1].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object rshift (MExpression[] args, Domain domain)
      {
	return (int) args[0].val >> (int) args[1].val;
      }

      private static object rshifteq (MExpression[] args, Domain domain)
      {
	MSymbol sym = (MSymbol) args[0].args[0].val;
	int n = (int) domain.GetValue (sym);

	n >>= (int) args[1].Eval (domain);
	return domain.SetValue (sym, (object) n);
      }

      private static object eq (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;

	for (int i = 1; i < args.Length; i++)
	  if (n != (int) args[i].val)
	    return false;
	return true;
      }

      private static object noteq (MExpression[] args, Domain domain)
      {
	return ((int) args[0].val != (int) args[1].val);
      }

      private static object less (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;

	for (int i = 1; i < args.Length; i++)
	  {
	    int n1 = (int) args[i].val;
	    if (n >= n1)
	      return false;
	    n = n1;
	  }
	return true;
      }

      private static object lesseq (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;
	for (int i = 1; i < args.Length; i++)
	  {
	    int n1 = (int) args[i].val;
	    if (n > n1)
	      return false;
	    n = n1;
	  }
	return true;
      }

      private static object more (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;
	for (int i = 1; i < args.Length; i++)
	  {
	    int n1 = (int) args[i].val;
	    if (n <= n1)
	      return false;
	    n = n1;
	  }
	return true;
      }

      private static object moreeq (MExpression[] args, Domain domain)
      {
	int n = (int) args[0].val;
	for (int i = 1; i < args.Length; i++)
	  {
	    int n1 = (int) args[i].val;
	    if (n < n1)
	      return false;
	    n = n1;
	  }
	return true;
      }

      private static object progn (MExpression[] args, Domain domain)
      {
	object result = false;

	foreach (MExpression e in args)
	  result = e.Eval (domain);
	return result;
      }

      private static bool check_condition (MExpression condition, Domain domain)
      {
	object result = condition.Eval (domain);
	return (result is bool ? (bool) result
		: result is int ? ((int) result) != 0
		: true);
      }

      private static object ifclause (MExpression[] args, Domain domain)
      {
	object result = false;

	if (check_condition (args[0], domain))
	  result = args[1].Eval (domain);
	else
	  for (int i = 2; i < args.Length; i++)
	    result = args[i].Eval (domain);
	return result;
      }

      private static object whenclause (MExpression[] args, Domain domain)
      {
	object result = false;

	if (check_condition (args[0], domain))
	  for (int i = 1; i < args.Length; i++)
	    result = args[i].Eval (domain);
	return result;
      }

      private static object whileclause (MExpression[] args, Domain domain)
      {
	while (check_condition (args[0], domain))
	  for (int i = 1; i < args.Length; i++)
	    args[i].Eval (domain);
	return false;
      }

    // (cond (COND1 ...) (COND2 ...) ...)
    //   => (cond (when COND1 ...) (when COND2 ...) ...)
    private static void translate_cond (MPlist plist, Domain domain)
    {
      if (plist.IsPlist)
	{
	  plist = plist.Plist;
	  if (plist.IsSymbol && plist.Symbol == Mcond)
	    {
	      plist.val = Mprogn;
	      for (plist = plist.next; ! plist.IsEmpty; plist = plist.next)
		{
		  if (! plist.IsPlist)
		    throw new Exception ("Invalid cond form: " + plist);
		  plist.Plist.Push (MSymbol.symbol, Mwhen);
		}		
	    }
	}
    }

    private Function function;
    private MExpression[] args;
    private object val;

    public MExpression[] Args { get { return args; } }
    public object Val { get { return val; } }

    private MExpression (object val)
    {
      this.val = val;
    }

    // EXPR = SYMBOL | MTEXT | INTEGER | FUNCALL | PROGN
    // FUNCALL = '(' SYMBOL EXPR* ')'
    // PROGN = '(' EXPR * ')'
    private MExpression (MSymbol key, object val, Domain domain)
    {
      if (key == MSymbol.symbol)
	{
	  function = Function.varref;
	  args = new MExpression[1];
	  args[0] = new MExpression (val);
	}
      else if (key == MSymbol.integer
	       || key == MSymbol.mtext)
	{
	  this.val = val;
	}
      else if (key == MSymbol.plist)
	{
	  MPlist p = (MPlist) val;

	  if (p.IsSymbol)
	    {
	      MSymbol sym = p.Symbol;

	      if (sym == Mdefun)
		{
		  p = p.next;
		  if (! p.IsSymbol)
		    throw new Exception ("Invalid function argument: "
					 + p.val);
		  sym = p.Symbol;
		  p = p.next;
		  if (! p.IsPlist)
		    throw new Exception ("Invalid function argument: "
					 + p.val);
		  domain.Defun (sym, p.Plist, p.next);
		  // This Mexpression is just a dummy.
		}
	      else
		{
		  function = domain.GetFunc (sym);
		  p = p.next;
		  int nargs = p.Count;
		  if (nargs < function.min_arg
		      || (function.max_arg >= 0 && nargs > function.max_arg))
		    throw new Exception ("Invalid number of arguments to: "
					 + sym + " " + nargs);
		  args = new MExpression[nargs];
		  for (int i = 0; i < nargs; i++, p = p.next)
		    {
		      domain.Translate (p);
		      args[i] = new MExpression (p.key, p.val, domain);
		    }
		}
	    }
	  else
	    {
	      args = new MExpression[1];
	      args[0] = new MExpression (p, domain);
	    }
	}
      else
	throw new Exception ("Invalid expression: " + key + ":" + val);
    }

    public MExpression (MPlist plist, Domain domain)
    {
      function = Function.block;
      args = new MExpression[plist.Count];
      for (int i = 0; ! plist.IsEmpty; i++, plist = plist.next)
	{
	  domain.Translate (plist);
	  args[i] = new MExpression (plist.key, plist.val, domain);
	}
    }

    public MExpression (XmlNode node, Domain domain)
    {
      MSymbol sym = node.Name;

      function = domain.GetFunc (sym);

      XmlAttributeCollection attrs = node.Attributes;

      int nargs = attrs.Count + node.ChildNodes.Count;
      if (nargs < function.min_arg
	  || (function.max_arg >= 0 && nargs > function.max_arg))
	throw new Exception ("Invalid number of arguments: " + node.InnerXml);
      args = new MExpression[nargs];
      int i;
      for (i = 0; i < attrs.Count; i++)
	{
	  string str = sttrs[i].Value;

	}
    }

    public object Eval (Domain domain)
    {
      if (function == null)
	{
	  if (val is MSymbol)
	    val = domain.GetValue ((MSymbol) val);
	}
      else
	val = function.Call (args, domain);
      return val;
    }

    public override string ToString ()
    {
      string str;

      if (function != null)
	{
	  str = "(" + function.Name.Name;
	  if (args != null)
	    foreach (MExpression e in args)
	      str += " " + e.ToString ();
	  str += ")";
	}
      else if (val != null)
	{
	  if (val is MText)
	    str = "\"" + (string) ((MText) val) + "\"";
	  else
	    str = val.ToString ();
	}
      else
	str = "()";
      return str;
    }
  }
}