/*
 * joy.cc -- Evolvable Joy Virtual Machine -- a kind of Joy
 *
 # Copyright (c) 2006 Henry Strickland -- <strick> in the domain <yak.net>
 #
 # Permission is hereby granted, free of charge, to any person obtaining a
 # copy of this software and associated documentation files (the "Software"),
 # to deal in the Software without restriction, including without limitation
 # the rights to use, copy, modify, merge, publish, distribute, sublicense,
 # and/or sell copies of the Software, and to permit persons to whom the
 # Software is furnished to do so, subject to the following conditions:
 #
 # The above copyright notice and this permission notice shall be included
 # in all copies or substantial portions of the Software.
 #
 # THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 # IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 # FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 # THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
 # OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 # ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 # OTHER DEALINGS IN THE SOFTWARE.
 #
 #         (* http://www.opensource.org/licenses/mit-license.php *)
 *
 */

#include "li.h"

namespace Joy {
using namespace Li;

#define	NIL charNode(0)

class JoyMachine : public TaggedMachine {

public:
	node stk;
	node code;

	string	audit;

protected:
        virtual ~JoyMachine();
        virtual void eval_virtual( );

public:
        JoyMachine(Link<Params> p, Link<Creature> c );

	void	push(node p);
	node	pop();
	void	pop(int n);
	node	peek(int n);
	Number	popNum();
	node	popList();

	node	parse(string s, int& arrow, node z);
	node	parse(string s);

	void	evalList(node p);	// evals in reverse order!
	void	evalNode(node p);
	void	evalChar(char c);

	bool	truth(node cond) {
		// only nonpositive numbers and NIL are false.
		return not ( cond==NIL || isNum(cond) && asNum(cond)<=0 );
	}
	string toString(node); 

};



void  JoyMachine::push(node p)
{
	stk= cons( p, stk );
}

node	JoyMachine::pop()
{
	if ( isPair(stk) ) {
		node tmp= stk;
		stk= tl(tmp);
		return hd(tmp);
	} else {
		return NIL;
	}
}
void	JoyMachine::pop(int n)
{
	for (int i=0; i<n; i++) pop();
}
node	JoyMachine::peek(int n)
{
	node tmp= stk;
	for (int i=0; i<n; i++) {
		tmp= isPair(tmp) ? tl(tmp) : NIL;
	}
	return isPair(tmp) ? hd(tmp) : NIL;
}
Number	JoyMachine::popNum()
{
#ifdef SMART
	while (true) {
		node tmp= stk;
		if ( not isPair(tmp) ) return 0;  // empty stack
		stk= tl(tmp);
		node x= hd(tmp);
		if ( isNum( x ) ) return asNum(x); // found a number
	}
#else
	node p= pop();
	if ( isNum(p) ) return asNum(p);
	if ( isChar(p) ) return asChar(p);
	return 0;
#endif
}
node	JoyMachine::popList()
{
	// if top of stack is a List, pop it.
	node p= peek(0);
	if ( isPair(p) ) return pop();

	// else have mercy and look for any list in the stack
	node* prev= &stk;

	for (p= stk; p!=NIL; p=tl(p)) {
		if (isPair(hd(p))) {
			// patch stack around removed piece
			*prev = tl(p);
			return hd(p);
		}

		prev= & p->n_tl;
	}
	// else give up
	return NIL;
#if 0
#ifdef SMART
	while (true) {
		node tmp= stk;
		if ( not isPair(tmp) ) return 0;  // empty stack
		stk= tl(tmp);
		node x= hd(tmp);
		if ( isPair( x ) || x==NIL ) return x; // found a List
	}
#else
	node p= pop();
	if ( isPair(p) ) return p;
	return NIL;
#endif
#endif
}

node	JoyMachine::parse(string s, int& arrow, node z) {
	int sz= s.size();
	while (arrow < sz) {
		char c= s.at(arrow);
		++arrow;

		node x= NIL;

		if (c==']') {
			return z;
		} else if (c=='[') {
			x= parse(s, arrow, NIL);
		} else if ('0'<=c && c<='5') {
			x= numNode( c-'0' );
		} else if ('6'<=c && c<='9') {
			x= numNode( c-'9'-1 );
		} else {
			x= charNode( c );
		}

		z= cons( x, z );  // notice this builds in reverse order!
	}
	return z;
}


node	JoyMachine::parse(string s) {
	int sz= s.size();
	node z= NIL;
	int arrow= 0;

	while (arrow < sz) {
		node x= parse(s, arrow, z);
		z= (arrow<sz) ? cons( x , NIL ) : x; 
	}
	
	return z;
}

static JoyMachine* createTestJoyMachine( string programString )
{
        Language* lang= Language::Find("joy");
        Link<Params> params= lang->defaultParams();
        Link<Creature> prog= new Creature(programString, lang);

        return new JoyMachine( params, prog );
}



TEST(joy_parse_123)
{
	Link<JoyMachine> m= createTestJoyMachine("123");
	AssertEq( 3, m->llen( m->code ) );
	AssertEq( m->numNode(3), m->hd( m->code ) );
	AssertEq( m->numNode(2), m->hd(m->tl( m->code ) ));
	AssertEq( m->numNode(1), m->hd(m->tl(m->tl( m->code ) )));
	AssertEq( m->NIL       , m->tl(m->tl(m->tl( m->code ) )));
}
TEST(joy_parse_1L3)
{
	Link<JoyMachine> m= createTestJoyMachine("1[2]3");
	AssertEq( 3, m->llen( m->code ) );
	AssertEq( m->numNode(3), m->hd( m->code ) );
	AssertEq( m->numNode(2), m->hd(m->hd(m->tl( m->code ) )));
	AssertEq( m->NIL       , m->tl(m->hd(m->tl( m->code ) )));
	AssertEq( m->numNode(1), m->hd(m->tl(m->tl( m->code ) )));
	AssertEq( m->NIL       , m->tl(m->tl(m->tl( m->code ) )));
}
TEST(joy_parse_L3)
{
	Link<JoyMachine> m= createTestJoyMachine("12]3");
	AssertEq( 2, m->llen( m->code ) );
	AssertEq( m->numNode(3), m->hd( m->code ) );
	AssertEq( m->numNode(2), m->hd(m->hd(m->tl( m->code ) )));
	AssertEq( m->numNode(1), m->hd(m->tl(m->hd(m->tl( m->code ) ))));
	AssertEq( m->NIL       , m->tl(m->tl(m->hd(m->tl( m->code ) ))));
}
TEST(joy_add)
{
	Link<JoyMachine> m= createTestJoyMachine("25+");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(7), m->hd(m->stk) );
}
TEST(joy_mul)
{
	Link<JoyMachine> m= createTestJoyMachine("25+2*");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(14), m->hd(m->stk) );
}
TEST(joy_negate)
{
	Link<JoyMachine> m= createTestJoyMachine("25+2*-");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(-14), m->hd(m->stk) );
}

TEST(joy_if_true)
{
	Link<JoyMachine> m= createTestJoyMachine("[3][44*][55*]?");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(16), m->hd(m->stk) );
}
TEST(joy_if_false)
{
	Link<JoyMachine> m= createTestJoyMachine("[3-][44*][55*]?");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(25), m->hd(m->stk) );
}
TEST(joy_chars_are_true)
{
	Link<JoyMachine> m= createTestJoyMachine("[\1][44*][55*]?");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(16), m->hd(m->stk) );
}
TEST(joy_lists_are_true)
{
	Link<JoyMachine> m= createTestJoyMachine("[[abc]][44*][55*]?");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(16), m->hd(m->stk) );
}
TEST(joy_null_list_is_false)
{
	Link<JoyMachine> m= createTestJoyMachine("[[]][44*][55*]?");
	m->eval();
	AssertEq( 1, m->llen(m->stk) );
	AssertEq( m->numNode(25), m->hd(m->stk) );
}

void JoyMachine::evalList(node p)
{
	EvalCounter(this);

	// since parse() builds list in reverse order, eval in reverse order!
	if ( isPair(p) ) {
		evalList( tl(p) );
		evalNode( hd(p) );
	}
	// ELSE: END OF LIST, do nothing.
}

string JoyMachine::toString(node p) {
	if ( isNum(p) ) {
		return ToString( asNum(p) );
	} else if ( isChar(p) ) {
		//char buf[2]; buf[0]= asChar(p); buf[1]=0;
		//return string("'") + buf + string("'");
		return string("'") + ToString( (int)asChar(p) ) + string("'");
	} else {
		return "[]";
	}
}
void JoyMachine::evalNode(node p)
{
	if ( isChar(p) ) {
		evalChar( asChar(p) );  // chars are interpreted
	} else {
if (audit.size()>0) audit.push_back( isNum(p) ? '#' : '`' );
		push(p);		// all else are pushed literals
	}

  if (trace) {
	Trace(stderr, "           : ");
	for (node p= stk; p!=NIL; p= tl(p)) {
		string x= toString( hd(p) );
		Trace(stderr, "%s, ", x.c_str() );
	}
	Trace(stderr, "\n");
  }
}
void JoyMachine::evalChar(char c)
{
if (audit.size()>0) audit.push_back(c);

	switch (c) {
	  case ' ': {
		// Let space be NOP -- might be useful in hand-written formatting
	  } break;
	  case '+': {
		Number y= popNum();
		Number x= popNum();
		Number z= x+y;
Trace(stderr, "ADD %d + %d -> %d\n", x, y, z );
		push( numNode(z) );
	  } break;
	  case '*': {
		Number y= popNum();
		Number x= popNum();
		Number z= x*y;
Trace(stderr, "MUL %d * %d -> %d\n", x, y, z );
		push( numNode(z) );
	  } break;
	  case '-': {
		Number y= popNum();
		Number z= (-y);
Trace(stderr, "NEGATE  - %d -> %d\n", y, z );
		push( numNode(z) );
	  } break;
	  case 's': {
		Number y= popNum();
		Number z= y+1;
Trace(stderr, "SUCC  %d -> %d\n", y, z );
		push( numNode(z) );
	  } break;
	  case 'p': {
		Number y= popNum();
		Number z= y-1;
Trace(stderr, "PREV  %d -> %d\n", y, z );
		push( numNode(z) );
	  } break;
	  case '.': {
		Number y= popNum();
Trace(stderr, "PUT NUM  %d\n", y );
		putnum( y );
	  } break;
	  case 'D': {	// D == dup
		node x= peek(0);
Trace(stderr, "DUP %0xx -> %0xx %0xx\n", x, x, x );
		push( x );
	  } break;
	  case 'P': {	// P == pop
		node x= pop();
Trace(stderr, "POP %0xx ->  -\n", x );
	  } break;


// Simulate Globals 'a' 'b' 'c' 'A' 'B' 'C' 
	  case 'a':
	  case 'b':
	  case 'c': {	// peek down 1, 2, 3
		int n= c-'a'+1;
		node x= peek(n);
		push(x);
Trace(stderr, "PEEK %d ->  %0xx\n", n, x );
	  } break;
	  case 'A':
	  case 'B':
	  case 'C': {	// poke down 1, 2, 3
		node tmps[29];
		int n= c-'A'+1;
		n= (n<1) ? 1 : n;
		n= (n>26) ? 26 : n;
		node x= pop();
		for (int i=0; i<n; i++) { tmps[i]= pop(); }
		pop();
		push(x);
		for (int i=n-1; i>=0; i--) { push(tmps[i]); }
		push(x);
Trace(stderr, "POKE %d ->  \n", n, x );
	  } break;


	  case '|': {	// | == roll
		node z= pop();
		node y= pop();
		node x= pop();
Trace(stderr, "ROLL %0xx %0xx %0xx\n", z, y, x );
		push(z);
		push(x);
		push(y);
	  } break;
	  case '~': {	// ~ == swap
		node y= pop();
		node x= pop();
Trace(stderr, "SWAP %0xx %0xx -> %0xx %0xx\n", x, y, y, x );
		push(y);
		push(x);
	  } break;
	  case '^': {	// ^ == dip
		node code= popList();
		node saved= pop();
Trace(stderr, "DIP %0xx %0xx ->  ?\n", saved, code); 
		evalList( code );
		push(saved);
	  } break;

	  case '?': {  // ifte:  IF THEN ELSE:   ( condClause thenClause elseClause -> ) // restore stack after condClause is evalled
br("if");
		node elseClause= popList();
		node thenClause= popList();
		node condClause= popList();

		node tmp= stk;		// save stack
		evalList(condClause);
		node cond= pop();
		stk= tmp;		// restore stack

		if ( truth(cond) ) {
Trace(stderr, "IF   ->  True\n"); 
			evalList(thenClause);
		} else {
Trace(stderr, "IF   ->  False\n"); 
			evalList(elseClause);
		}

	  } break;

	  case '@': {  // while:  ( condClause block ->  )  // while condClause is true (restoring stack), evalute block
br("while");

// Normal Joy While
		node block= popList();
		node condClause= popList();
int i= 0;
		while (true) {

Trace(stderr, "WHILE  ... #%d\n", i); 
			node tmp= stk;		// save stack
			evalList(condClause);
			node cond= pop();
			stk= tmp;		// restore stack

			if ( not truth(cond) ) break;

Trace(stderr, "       ... ... #%d\n", i); 
			evalList(block);
			++i;
		}
	  } break;
	  case '#': {  // Minimalist While:  ( block ->  )  // while peek(0) is true, evaluate block
br("while");

// Minimal Joy While
		node block= popList();
		node x = peek(0);
int i= 0;
		while (truth(x)) {

Trace(stderr, "WHILE'#' ... i=%d\n", i); 
			evalList(block);
			/////////////////////// OHNO /;///// node x = peek(0);
			x = peek(0);
			++i;
		}
	  } break;
	  case '%': {  // loop:  ( ntimes block -> ) // block evaled with num pushed on stack
// Counting Down Loop
		Number times= popNum();
		node block= popList();
		//node tmp= stk;		// save stack

		for (int i= times; i>0; i--) {

Trace(stderr, "LOOP  ... %d/%d\n", i, times); 
			//stk= tmp;		// restore stack
			push( numNode(i) );
			evalList(block);
		}
		//stk= tmp;		// restore stack

	  } break;

	  default:
		push( charNode(c) );	// all else is pushed literal
	}
}


JoyMachine::~JoyMachine() 
{
//fprintf(stderr, " CODE   %s\n", m_creature->sourceCode.c_str() );
Trace(stderr, "AUDIT %s\n", audit.c_str() );
string outs= ToString( m_outputs->vec );
Trace(stderr, "OUT   %s\n", outs.c_str() );
}

JoyMachine::JoyMachine( Link<Params> p, Link<Creature> c )
	: TaggedMachine(p,c) 
	, stk(NIL)
	, code( parse(c->sourceCode) )
	, audit( " " )
{
Trace(stderr, " CODE   %s\n", m_creature->sourceCode.c_str() );
}


  void
JoyMachine::eval_virtual()
{
	evalList( code );
}

//////////////////  Joy  Language  ////////////////////////////////

class JoyLanguage : public Language {

private:
        // private singleton, only used via Find()
        JoyLanguage() : Language("joy") {}

        static JoyLanguage Singleton;

public:
        virtual Link<Params> defaultParams( );
        virtual Link<Machine> createMachine( Link<Params> p, Link<Creature> c );

#ifdef BALANCE
        virtual Link<Creature> createRandomCreature( Params* p );

        virtual Link<Creature> mutate( Params* p, Creature* );
        virtual void cross( Params* p, Creature* c1, Creature* c2, CreatureLink& newc1, CreatureLink& newc2 );
        Link<Creature> mutateUntilBalanced( Params* p, Link<Creature> );
#endif

} JoyLanguage::Singleton;


Link<Params> JoyLanguage::defaultParams( )
{
        Link<Params> p= Language::defaultParams();
        p->creatureAlphabet = "01259[][]+*-?@.DP~^";
        p->creatureAlphabet = "0125[][]+*-?@.D~^";
        p->creatureAlphabet = "0125[][]+*-.D~^%";


        const char* ALPHABET_10 = "[D.s]#+~|^";
        //const char* ALPHABET_13 = "[D.sp]#+-*~|^";
        p->creatureAlphabet = ALPHABET_10;

// // SIMULATE_GLOBALS
//        p->creatureAlphabet += "abAB";
// //
        return p;
}
Link<Machine> JoyLanguage::createMachine( Link<Params> p, Link<Creature> c )
{
        return new JoyMachine( p, c );
}

#ifdef BALANCE
int NotBalanced(string s)
{
	size_t len= s.size();

	int badness= 0;
	int level= 0;
	for (int i=0; i<len; i++) {
		char c= s[i];
		if (c=='[') {
			++level;
		} else if (c==']') {
			--level; 
			if (level<0) { ++badness; level=0; }
		}
	}
	if (level>0) badness += level;
	return badness;
}

TEST(NotBalanced) 
{
	AssertEq( 0, NotBalanced("ab[ cd [ef] [] g]h") );
	AssertEq( 1, NotBalanced("[ab[ cd [ef] [] g]h") );
	AssertEq( 1, NotBalanced("]ab[ cd [ef] [] g]h") );
	AssertEq( 2, NotBalanced("][ab[ cd [ef] [] g]h") );
	AssertEq( 2, NotBalanced("ab[ cd [ef] [] g]h ]]") );

	AssertEq( 3, NotBalanced("]]]") );
	AssertEq( 3, NotBalanced("[[[") );

	AssertEq( 2, NotBalanced("][]]") );
	AssertEq( 2, NotBalanced("[[][") );
}


Link<Creature> JoyLanguage::mutateUntilBalanced(Params* params, Link<Creature> cre)
{
//	Say(stderr, "  // FROM %d ", NotBalanced( cre->sourceCode ) );
	int i;
	for (i=0; i<1000; i++) {

		int badness= NotBalanced( cre->sourceCode );
		if ( not badness ) break;

		Link<Creature> tmp= Language::mutate( params, cre );
		int tmpBadness= NotBalanced( tmp->sourceCode );
		
		if ( tmpBadness < badness ) cre= tmp;  // keep better mutation
	}

//	Say(stderr, "TO %d   i=%d\n", NotBalanced( cre->sourceCode ), i );
	return cre;
}
Link<Creature> JoyLanguage::mutate(Params* params, Creature* cre)
{
	Link<Creature> tmp= Language::mutate( params, cre );

	return mutateUntilBalanced(params, tmp);
}
Link<Creature> JoyLanguage::createRandomCreature( Params* params )
{
	Link<Creature> tmp= Language::createRandomCreature( params );

	return mutateUntilBalanced(params, tmp);
}

void JoyLanguage::cross( Params* params, Creature* c1, Creature* c2, CreatureLink& newc1, CreatureLink& newc2 )
{
	Language::cross( params, c1, c2, newc1, newc2 );

	newc1= mutateUntilBalanced(params, newc1);
	newc2= mutateUntilBalanced(params, newc2);
}
#endif
////////////////////////  TESTING  /////////////////////////////////////



} //Joy
//END