// Copyright (C) 2008 Chris Double.
// 
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
// 
// 1. Redistributions of source code must retain the above copyright notice,
//    this list of conditions and the following disclaimer.
// 
// 2. Redistributions in binary form must reproduce the above copyright notice,
//    this list of conditions and the following disclaimer in the documentation
//    and/or other materials provided with the distribution.
// 
// THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES,
// INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
// FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
// DEVELOPERS AND CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
// PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
// OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
// WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
// OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
// ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
function TokenNumber(v) {
  this.type = "Number";
  this.value = v;
  return this;
}

TokenNumber.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenNumber.prototype.isTrue = function() {
  return this.value.compare(0) != 0;
}

TokenNumber.prototype.pretty = function(r) {
  r.push(this.value);
}

TokenNumber.prototype.toString = function() {
  var r = [];
  this.pretty(r);
  return r.join("");
}

TokenNumber.prototype.equals = function(rhs) {
  return this.value.compare(rhs.value) == 0;
}

function TokenWord(v) {
  this.type = "Word";
  this.value = v;
  return this;
}

TokenWord.prototype.evalWord = function(xy) {
  var x = xy.x;
  var y = xy.y;
  switch(this.value) {
    case "if":
      var b = x[x.length-3];
      var iftrue = x[x.length-2];
      var iffalse = x[x.length-1];
      x.length = x.length-3;
      y.enqueueHeads(b.isTrue() ? iftrue.value : iffalse.value);
      break;
    case "true?": 
      x[x.length-1] = x[x.length-1].isTrue() ? new TokenBoolean(true) : new TokenBoolean(false);
      break;
    case "false?":
      x[x.length-1] = x[x.length-1].isTrue() ? new TokenBoolean(false) : new TokenBoolean(true);
      break; 
    case "true":
      x.push(new TokenBoolean(true));
      break;
    case "false":
      x.push(new TokenBoolean(false));
      break;
    case "=":
      var lhs = x[x.length-2];
      var rhs = x[x.length-1];
      x.length = x.length-1;
      x[x.length-1] = new TokenBoolean(lhs.equals(rhs));
      break;
    case ",":
      var list1 = x[x.length-2].value;
      var list2 = x[x.length-1].value;
      x[x.length-2] = new TokenList(list1.concat(list2));
      x.length = x.length - 1;
      break;
    case "`":
      var e = x.pop();
      if (e.type == "List" || e.type == "Quot")
       x.push(e.value[0]);
      else
       x.push(new TokenList([e])); 
      break;
    case "=>":
      y.enqueue(x.pop());
      break;
    case "<=":
      x.push(y.dequeueTail());
      break;
    case "->":
      y.fromArray(x.pop().value.slice(0));
      break;
    case "<-":
      xy.x = x.pop().value.slice(0);
      break;
    case "iota":
    case "!:":
      var r = [];
      var n = x[x.length-1].value;
      for(var i=new BigNumber(0); i.compare(n) < 0; i=i.add(1)) {
        r.push(new TokenNumber(i));
      }
      x[x.length-1] = new TokenList(r);
      break;
    case "list?":
    case "@:":
      var o = x[x.length-1];
      x[x.length-1] = new TokenNumber(new BigNumber(o.type == "List" || o.type == "Quot" ? 0 : 1));  
      break;
    case "length":
    case "#:":
      x[x.length-1] = new TokenNumber(x[x.length-1].value.length);
      break;
    case "negate":
    case "-:":
      x[x.length-1] = new TokenNumber(x[x.length-1].value.negate()); 
      break;
    case "reverse":
    case "|:":
      x[x.length-1] = new TokenList(x[x.length-1].value.reverse());
      break;
    case "first":
    case "*:":
      x[x.length-1] = x[x.length-1].value[0];
      break;
    case "head":
    case "#":
      var len = x.length;
      var seq = x[len-1];
      var n = x[len-2];
      x[len-2] = new TokenList(n.value.compare(0) < 0 ? seq.value.slice(n.value) : seq.value.slice(0,n.value));
      x.length = len-1;
      break;
    case "tail":
    case "_":
      var len = x.length;
      var seq = x[len-1];
      var n = x[len-2];
      x[len-2] = new TokenList(n.value.compare(0) < 0 ? seq.value.slice(0, new BigNumber(seq.value.length).add(n.value)) : seq.value.slice(n.value));
      x.length = len-1;
      break;
 
    case "+":
      var len = x.length;
      x[len-2] = new TokenNumber(x[len-2].value.add(x[len-1].value));
      x.length = len-1;
      break;
    case "-":
      var len = x.length;
      x[len-2] = new TokenNumber(x[len-2].value.subtract(x[len-1].value));
      x.length = len-1;
      break;
    case "*":
      var len = x.length;
      x[len-2] = new TokenNumber(x[len-2].value.multiply(x[len-1].value));
      x.length = len-1;
     break;
    case "%":
      var len = x.length;
      x[len-2] = new TokenNumber(x[len-2].value.divide(x[len-1].value));
      x.length = len-1;
     break;
 
    case "source":
      var word = x.pop().value;
      var def = xy.env[word];
      y.enqueueHead(def);
      break;
    default:
      var w = xy.env[this.value];
      if (w)
        y.enqueueHeads(w.value);
      else
        x.push(this); 
      break;
  }
}

TokenWord.prototype.isTrue = function() {
  return true;
}
 
TokenWord.prototype.eval1 = function(xy) {
  if (xy.isDefineMode()) {
    xy.x.push(this);
    return;
  }

  switch(this.value) {
    case "\\":
      xy.x.push(xy.y.dequeue());
      break;

    case "/":
      var x = xy.x.pop();
      var q = x.type == "Word" ? xy.env[x.value].value : x.value;
      xy.y.enqueueHeads(q);
      break;

    default:
      if (xy.isQuotMode())
        xy.x.push(this);
      else
        this.evalWord(xy);
      break;
  }
}

TokenWord.prototype.pretty = function(r) {
  r.push(this.value);
}

TokenWord.prototype.toString = TokenNumber.prototype.toString;
TokenWord.prototype.equals = function(rhs) {
  return this.value == rhs.value;
}


function TokenString(v) {
  this.type = "String";
  this.value = v;
  return this;
}

TokenString.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenString.prototype.isTrue = function() {
  return this.value != "";
}
 
TokenString.prototype.pretty = function(r) {
  r.push('"', this.value, '"');
}

TokenString.prototype.toString = TokenNumber.prototype.toString;
TokenString.prototype.equals = TokenWord.prototype.equals;

function TokenBoolean(v) {
  this.type = "Boolean";
  this.value = v;
  return this;
}

TokenBoolean.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenBoolean.prototype.isTrue = function() {
  return this.value;
}
 
TokenBoolean.prototype.pretty = function(r) {
  r.push(this.value ? "true" : "false");
}

TokenBoolean.prototype.toString = TokenNumber.prototype.toString;
TokenBoolean.prototype.equals = TokenWord.prototype.equals;

function TokenQuotOpen() {
  this.type = "QuotOpen";
}

TokenQuotOpen.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenQuotOpen.prototype.pretty = function(r) {
  r.push("[");
}

TokenQuotOpen.prototype.toString = TokenNumber.prototype.toString;
TokenQuotOpen.prototype.equals = function(rhs) { return true; }

function TokenQuotClose() {
  this.type = "QuotClose";
}

TokenQuotClose.prototype.eval1 = function(xy) {
  var x = xy.x;
  for(var i=x.length-1; i >= 0; --i) {
    if (x[i].type == "QuotOpen")
      break;
  }
  if (i < 0)
    x.push(this);
  else {
    var quot = new TokenList(x.slice(i+1));
    x.length = i;
    xy.y.enqueueHead(quot);
 }
}

TokenQuotClose.prototype.pretty = function(r) {
  r.push("]");
}

TokenQuotClose.prototype.toString = TokenNumber.prototype.toString;
TokenQuotClose.prototype.equals = function(rhs) { return true; }

function TokenListOpen() {
  this.type = "ListOpen";
}

TokenListOpen.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenListOpen.prototype.pretty = function(r) {
  r.push("[");
}

TokenListOpen.prototype.toString = TokenNumber.prototype.toString;
TokenListOpen.prototype.equals = function(rhs) { return true; }

function TokenListClose() {
  this.type = "ListClose";
}

TokenListClose.prototype.eval1 = function(xy) {
  var x = xy.x;
  for(var i=x.length-1; i >= 0; --i) {
    if (x[i].type == "ListOpen")
      break;
  }
  if (i < 0)
    x.push(this);
  else {
    var quot = new TokenList(x.slice(i+1));
    x.length = i;
    xy.y.enqueueHead(quot);
 }
}

TokenListClose.prototype.pretty = function(r) {
  r.push("]");
}

TokenListClose.prototype.toString = TokenNumber.prototype.toString;
TokenListClose.prototype.equals = function() { return true; }

function TokenList(v) {
  this.type = "List";
  this.value = v;
}

TokenList.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenList.prototype.isTrue = function() {
  return this.value.length != 0;
}
 
TokenList.prototype.pretty = function(r) {
  r.push("[ ");
  for(var i=0; i < this.value.length; ++i) {
    this.value[i].pretty(r);
    r.push(" ");
  }
  r.push("]");
}

TokenList.prototype.toString = TokenNumber.prototype.toString;
TokenList.prototype.equals = function(rhs) {
  if(rhs.type != "List")
    return false;

  if(this.value.length != rhs.value.length)
    return false;

  for(var i=0; i < this.value.length; ++i)
    if (!this.value[i].equals(rhs.value[i]))
      return false;

  return true;
}

function TokenDefine() {
  this.type = "Define";
}

TokenDefine.prototype.eval1 = function(xy) {
  var x = xy.x;
  for(var i=x.length-1; i >= 0; --i) {
    if (x[i].type == "DefineStart")
      break;
  }
  if (i < 0)
    x.push(new TokenDefineStart());
  else {
    var name = x[i+1].value;
    var quot = new TokenList(x.slice(i+2));
    x.length = i;
    xy.env[name] = quot;
 }
}

TokenDefine.prototype.isTrue = function() {
  return true;
}
 
TokenDefine.prototype.pretty = function(r) {
  r.push(";");
}

TokenDefine.prototype.toString = TokenNumber.prototype.toString;
TokenDefine.prototype.equals  = function(rhs) { return true; }

function TokenDefineStart() {
  this.type = "DefineStart";
}

TokenDefineStart.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenDefineStart.prototype.pretty = function(r) {
  r.push(";");
}

TokenDefineStart.prototype.toString = TokenNumber.prototype.toString;
TokenDefineStart.prototype.equals = function(rhs) { return true; }


function TokenPatternOpen() {
  this.type = "PatternOpen";
}

TokenPatternOpen.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenPatternOpen.prototype.pretty = function(r) {
  r.push("{");
}

TokenPatternOpen.prototype.toString = TokenNumber.prototype.toString;
TokenPatternOpen.prototype.equals = function(rhs) { return true; }


function TokenPatternClose() {
  this.type = "PatternClose";
}

TokenPatternClose.prototype.eval1 = function(xy) {
  if (xy.isQuotMode()) {
    xy.x.push(this);
    return;
  }
  var x = xy.x;
  for(var i=x.length-1; i >= 0; --i) {
    if (x[i].type == "PatternOpen")
      break;
  }
  if (i < 0)
    x.push(this);
  else {
    var pattern = x.slice(i+1);
    x.length = i;
    var values = xy.processPattern(pattern[0]); 
    values["_x"] = new TokenList(xy.x.slice(0));
    values["_y"] = new TokenList(xy.y.toArray().slice(0));
    var z = [ new TokenPatternOpen() ];
    for (var i=0; i < pattern.length; ++i)
      z.push(pattern[i]);
    z.push(new TokenPatternClose());
    z.push(new TokenWord("/"));
    values["_z"] = new TokenList(z);
    var quot = xy.replacePattern(values, new TokenList(pattern.slice(1)));
    xy.y.enqueueHeads(quot.value);
 }
}

TokenPatternClose.prototype.pretty = function(r) {
  r.push("}");
}

TokenPatternClose.prototype.toString = TokenNumber.prototype.toString;
TokenPatternClose.prototype.equals = function(rhs) { return true; }

function TokenForeign(v, f) {
  this.type = "Foreign";
  this.value = v;
  this.func = f;
}

TokenForeign.prototype.eval1 = function(xy) {
  this.func(xy);
}

TokenForeign.prototype.isTrue = function() {
  return true;
}
 
TokenForeign.prototype.pretty = function(r) {
  r.push(this.value);
}

TokenForeign.prototype.toString = TokenNumber.prototype.toString;
TokenForeign.prototype.equals = function(rhs) {
  return this.func == rhs.func && this.value == rhs.value;
}

function TokenJavaScript(obj) {
  this.type = "JavaScript";
  this.value = obj;
}

TokenJavaScript.prototype.eval1 = function(xy) {
  xy.x.push(this);
}

TokenJavaScript.prototype.isTrue = function() {
  return true;
}
 
TokenJavaScript.prototype.toString = TokenNumber.prototype.toString;
TokenJavaScript.prototype.pretty = function(r) {
  var v = this.value;
  var s;
  if (v == undefined)
    s = "undefined";
  else if(v == null)
    s = "null";
  else
    s = v.toString();

  r.push("js(");
  r.push(s);
  r.push(")");
}

TokenJavaScript.prototype.equals = function(rhs) {
  return this.value == rhs.value;
}

// Convert the string into an array of XY tokens
function tokenize(s) {
  return s.match(/([\\\[\]\{\}\(;\)])|([a-zA-Z][^\[\]\{\}\(;\)\s]*)|([0-9]+(\.[0-9]*)?)\s|(\"[^\"]*\")|([^\\\[\]\{\}\(;\)\s]+)/g);
}

// Given an array of XY tokens, return the AST.
function parse(tokens) {
  var ast = [];
  for(var i=0; i < tokens.length; ++i) {
    var token = tokens[i];
    if(token.match(/"[^"]*"/)) // String
      ast.push(new TokenString(token.substr(1,token.length-2)));
    else if(token.match(/[0-9]+(\.[0-9]*)?\s/)) // Number
      ast.push(new TokenNumber(new BigNumber(token)));
    else if(token == "{") // Pattern
      ast.push(new TokenPatternOpen());
    else if(token == "}") // Pattern
      ast.push(new TokenPatternClose());
    else if(token == "[") // Quot
      ast.push(new TokenQuotOpen());
    else if(token == "]") // Quot
      ast.push(new TokenQuotClose());
    else if(token == "(") // List
      ast.push(new TokenListOpen());
    else if(token == ")") // List
      ast.push(new TokenListClose());
    else if(token == ";") // Define
      ast.push(new TokenDefine());
    else 
      ast.push(new TokenWord(token));
  }
  return ast;
}

function XY(env, x, y) {
  this.env = env;
  this.x = x;
  this.y = y;
}

XY.prototype.toString = function() {
  return uneval({ env: this.env, x: this.x, y: this.y.toArray()});
}

XY.prototype.isQuotMode = function() {
  var x = this.x;
  for(var i=x.length-1; i >= 0; --i) {
    if (x[i].type == "QuotOpen" || x[i].type == "DefineStart")
      return true;
  }
  return false;
}

XY.prototype.isDefineMode = function() {
  var x = this.x;
  for(var i=x.length-1; i >= 0; --i) {
    if (x[i].type == "DefineStart" || x[i].type == "PatternOpen")
      return true;
  }
  return false;
}

XY.prototype.eval1 = function() {
  var v = this.y.dequeue();
  v.eval1(this);
  return this;
}

function match(r, obj, pattern, sequence, index) {
  if ((obj instanceof TokenList) &&
      (pattern instanceof TokenList)) {
    for(var i=0; i < pattern.value.length; ++i)
      match(r, obj.value[i], pattern.value[i], obj, i);
  } 
  else if(pattern instanceof TokenWord) {
    if (pattern.value.toUpperCase() == pattern.value) {
      var v;
      v = new TokenList(sequence.value.slice(index));
      r[pattern.value] = v;
    }
    else
      r[pattern.value] = obj;
  }
}

XY.prototype.processPattern = function(pattern) {
  var r = {};
  if (pattern instanceof TokenList) {
    var stack = this.x.slice(this.x.length - pattern.value.length);
    match(r, new TokenList(stack), pattern);
    this.x.length -= pattern.value.length;
  }
  else {
    match(r, this.x[this.x.length-1], pattern);
    this.x.length -= 1;
  }
 return r;
}

function replace(r, values, obj) {
  if (obj instanceof TokenList) {
    var r2 = [];
    for (var i=0; i < obj.value.length; ++i)
     replace(r2, values, obj.value[i]);
    r.push(new TokenList(r2));
  }
  else if(obj instanceof TokenWord) {
    if(values[obj.value])
      r.push(values[obj.value]);
    else
      r.push(obj);
  }
  else {
    r.push(obj);
  }
}

XY.prototype.replacePattern = function(values, quot) {
  var r = [];
  replace(r, values, quot);
  return r[0];
}

XY.prototype.prettyX = function() {
  var r = [];
  for(var i=0; i < this.x.length; ++i)
    this.x[i].pretty(r);
  return r.join(" ");
}

XY.prototype.prettyY = function() {
  var r = [];
  var y = this.y.toArray();
  for(var i=0; i < y.length; ++i)
    y[i].pretty(r);
  return r.join(" ");
}

function parseXY(str) {
  var ast = parse(tokenize(str));
  var queue = new Queue();
  for(var i=0; i < ast.length; ++i)
    queue.enqueue(ast[i]);
  return new XY({}, [], queue);
}

function xyeval(str) {
  var xy = parseXY(str);
  while (xy.y.getSize() != 0)
    xy.eval1();

  return xy.prettyX();
}