/*
 * bf.cc -- Evolvable Brainfuck Virtual Machine
 *
 # 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"


//////////////###########################################
//////////////###########################################
//////////////###########################################
//////////////###########################################

#define BF_OUT_SIZE	256		// TODO unhack
#define BF_TAPE_SIZE	(256*256)

#define OPEN(C)		((C)=='[')
#define CLOSE(C)	((C)==']')

namespace Brainfuck {
using namespace Li;
using Li::uint;


extern "C" void Test_bf_compile_0(void); // a.k.a. TEST(bf_compile_0) ; friend to be
extern "C" void Test_bf_compile_5(void); // a.k.a. TEST(bf_compile_5) ; friend to be


class Brainfuck {
	friend void Test_bf_compile_0(void);
	friend void Test_bf_compile_5(void);

	typedef unsigned int uint;

	Link<MachineIO> bf_io;
	const char* program;
	int* compiled;
	Number tape[BF_TAPE_SIZE];

	uint pc;
	uint plen;
	uint tapeP;
	uint maxsteps;

	Number accumulator;  // extension by strick

	Brainfuck(const Brainfuck&); // do not duplicate
	void operator=(const Brainfuck&); // do not duplicate
public:
	Brainfuck(const char* _program, Link<MachineIO>, int _maxsteps);
	~Brainfuck();
	void	run();
	void	compile();
};

void Brainfuck::run()
{
	if (!compiled) compile();

	pc= 0;
	tapeP= 0;

	uint counter=0;

	while (pc < plen) {
		++counter;
		if (counter > maxsteps) return;

		Number& TAPE= tape[tapeP]; // abbrev

		switch (program[pc]) {

	 	  case '<': {
			tapeP = (tapeP + compiled[pc]*(BF_TAPE_SIZE-1)) % BF_TAPE_SIZE;
			pc += compiled[pc];
			continue;
		  } break;

	 	  case '>': {
			tapeP = (tapeP + compiled[pc]) % BF_TAPE_SIZE;
			pc += compiled[pc];
			continue;
		  } break;

	 	  case '-': {
			TAPE -= compiled[pc];
			pc += compiled[pc];
			continue;
		  } break;

	 	  case '+': {
			TAPE += compiled[pc];
			pc += compiled[pc];
			continue;
		  } break;

	 	  case ',': {
			// INPUTS NOT IMPLEMENTED -- just set tape to 0.
			TAPE = 0;
		  } break;

	 	  case '.': {
			bf_io->putnum( TAPE );
		  } break;

	 	  case '[': {
			if ( 0 == TAPE ) {
				pc += compiled[pc];
				continue;
			}
		  } break;

	 	  case ']': {
			if (compiled[pc]) {
				pc -= (compiled[pc]-1);
			} else {
				pc= 0;
			}
			continue;
		  } break;

	// EXTENSIONS by strick
		  // Unary operations on TAPE

	 	  case 'S': {	// Sign
			TAPE = TAPE<0 ? -1 : TAPE>0 ? +1 : 0;
		  } break;
	 	  case 'N': {	// Negate
			TAPE = - TAPE;
		  } break;

		  // Operations involving accumulator

	 	  case 'G': {	// Get
			accumulator = TAPE;
		  } break;
	 	  case 'P': {	// Put
			TAPE = accumulator;
		  } break;
	 	  case 'A': {	// Add
			accumulator += TAPE;
		  } break;
	 	  case 'M': {	// Multiply
			accumulator *= TAPE;
		  } break;
	// end EXTENSIONS by strick

		}

		++pc;  // for clauses that dont set pc and continue
	}

}


Brainfuck::Brainfuck(const char* _program, Link<MachineIO> _io, int _maxsteps)
	: bf_io (_io)
	, program (_program)
	, compiled (0)
	, pc (0)
	, plen (0)
	, tapeP (0)
	, maxsteps (_maxsteps)
	, accumulator (0)
{
	memset( tape, 0, sizeof tape );
	plen= strlen(program);
}

Brainfuck::~Brainfuck()
{
	if (compiled) free(compiled);
}

void Brainfuck::compile()
{
	compiled= (int*)malloc( plen*sizeof(int) );

	memset( compiled, 0, plen*sizeof(int) ); // N.B. required for unmatched ')'


	for (uint p= 0; p<plen; /**/ ) {


		if ( OPEN(program[p]) ) {
			uint lev= 1;
			uint q;
			for ( q= p+1; q<plen && lev>0 ; ++q ) {
				if ( OPEN(program[q]) ) {
					++lev;
				} else if ( CLOSE(program[q]) ) {
					--lev;
				}
			}
			compiled[p]= q-p; // points past matching close ], or at EOS
			if ( lev==0 ) {
				compiled[q-1]= q-p; // points back
			}
			++p;
				
				

			
		} else if ( CLOSE(program[p]) ) {
			// nothing: the OPEN set it.
			++p;
			
		} else {
			// look ahead: how many repetitions?
			uint q;
			for ( q= p+1; program[p]==program[q]; ++q ) 
				continue;
			compiled[p]= q-p;
			p= q;
		}
	}
}

		TEST(bf_compile_0) 
		{
			Link<MachineIO> io= new MachineIO( Language::Find("bf")->defaultParams() );
			Brainfuck bf0("<<<[[+++]---]>>>", io, 9999);
			bf0.compile();

			Assert( 3 == bf0.compiled[0] );
			Assert( 10 == bf0.compiled[3] ); // ([+++]---)
			Assert( 5 == bf0.compiled[4] ); // [+++]
			Assert( 3 == bf0.compiled[5] ); // +++
			Assert( 5 == bf0.compiled[8] ); // [+++]
			Assert( 3 == bf0.compiled[9] ); // ---
			Assert( 10 == bf0.compiled[12] );
			Assert( 3 == bf0.compiled[13] );
		}

		TEST(bf_compile_5) 
		{
			Link<MachineIO> io= new MachineIO( Language::Find("bf")->defaultParams() );
			Brainfuck bf5("[+.", io, 9999);
			bf5.compile();
			Assert( 3 == bf5.compiled[0] );
		}

static void runBrainfuckAndAssertStringEqualsNumbers( const char* program, uint expectedSize, const char* s )
{
	Link<MachineIO> io= new MachineIO( Language::Find("bf")->defaultParams() );
	Brainfuck bf(program, io, 9999);

	try {
		bf.run();
	} catch (exception& ex) {
		AssertStrEq( "ENOUGH_OUTPUT", ex.what() );
	} 
	const vector<Number> &v = io->m_outputs->vec;

	AssertEq( expectedSize, (uint) v.size() );
	uint n= strlen(s);

	for (uint i=0; i<n; i++) {
		uint x= 255 & s[i]; // truncate to unsigned byte
		AssertEq( x, (uint)v[i] );
	}
}

		TEST(bf_1) 
		{
			// Keep one test old-style, to test different paths.
			Link<MachineIO> io= new MachineIO( Language::Find("bf")->defaultParams() );

			Brainfuck bf1("+.+.+.", io, 9999);
			bf1.run();

			Link<Numbers> expect = new Numbers();
			expect->vec.push_back(1);
			expect->vec.push_back(2);
			expect->vec.push_back(3);

			AssertStrEq( ToString(expect->vec), ToString(io->m_outputs->vec) );
		}
		TEST(bf_2) {
			runBrainfuckAndAssertStringEqualsNumbers( "+++[.-]", 3, "\3\2\1" );
		}
		TEST(bf_3) {
			runBrainfuckAndAssertStringEqualsNumbers( "+++>++>+.<.<.", 3, "\1\2\3" );
		}
		TEST(bf_4) {
			runBrainfuckAndAssertStringEqualsNumbers( "+.]", 256, "\1\2\3\4\5" );
		}
		TEST(bf_5) {
			runBrainfuckAndAssertStringEqualsNumbers( "+.[.-[+.", 2, "\1\1" );
		}
		TEST(bf_6) {
			runBrainfuckAndAssertStringEqualsNumbers( "+[.+]", 256, "\1\2\3\4\5" );
		}
		TEST(bf_7) {
			runBrainfuckAndAssertStringEqualsNumbers( "+[]", 0, "" );
		}



static void Bf_Eval(const char* program, Machine* mach, int maxsteps)
{
	Brainfuck bf(program,mach,maxsteps);
	bf.compile();
	bf.run();
}

/////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////


////
////  Brainf**k Language & Machine
////
////	One instance of the Language is good for all time.
////
////	A new machine is created for every eval.


class BfMachine : public Machine {
protected:
	virtual ~BfMachine();
	virtual void eval_virtual( );

public:
	BfMachine(Link<Params> p, Link<Creature> c ) : Machine(p,c) {}


};
BfMachine::~BfMachine() {}

class BfaMachine : public BfMachine {
protected:
	virtual ~BfaMachine();

public:
	BfaMachine(Link<Params> p, Link<Creature> c ) : BfMachine(p,c) {}


};
BfaMachine::~BfaMachine() {}


class BfLanguage : public Language {

private:
	// private singleton, only used via Find()
	BfLanguage() : Language("bf") {}

	static BfLanguage Singleton;

public:
	BfLanguage(char* subLanguageName) : Language(subLanguageName) {}
	virtual Link<Params> defaultParams( );
	virtual Link<Machine> createMachine( Link<Params> p, Link<Creature> c );

} BfLanguage::Singleton;

class BfaLanguage : public BfLanguage {

private:
	// private singleton, only used via Find()
	BfaLanguage() : BfLanguage("bfa") {}

	static BfaLanguage Singleton;

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

} BfaLanguage::Singleton;


Link<Machine> BfLanguage::createMachine( Link<Params> p, Link<Creature> c )
{
	return new BfMachine( p, c );
}
Link<Machine> BfaLanguage::createMachine( Link<Params> p, Link<Creature> c )
{
	return new BfaMachine( p, c );
}

Link<Params> BfLanguage::defaultParams( )
{
	Link<Params> p= Language::defaultParams();
	p->creatureAlphabet = "[]+-<>,.";
	return p;
}
Link<Params> BfaLanguage::defaultParams( )
{
	Link<Params> p= Language::defaultParams();
	p->creatureAlphabet = "[]+-<>,.SNGPAM";
	return p;
}


void BfMachine::eval_virtual( )
{
	const char* prog= m_creature->sourceCode.c_str();

	Bf_Eval( prog, this, 99999/*maxsteps*/ );
}

TEST(bf1) {
	Language* lang= Language::Find("bf");
	Link<Params> pp= lang->defaultParams();

	Creature* prog= new Creature("+++.", lang);

	Link<Machine> mach= lang->createMachine( pp, prog );
	mach->eval();

	Link<Numbers> expect = new Numbers();
	expect->vec.push_back(3);

	AssertStrEq( ToString(expect->vec), ToString(mach->m_outputs->vec) );
	AssertEq( 1u, mach->m_outputs->vec.size() );
	AssertEq( 3, mach->m_outputs->vec.at(0) );
}


}//Li