interpreter.c

#line __LINE__ "interpreter.c" // don't display full path in assert in VS
#include "crt.h"
#include "array.h"
#include "macros.h"
#include "rbtree.h"

typedef enum{NOPROGRAM,NORMAL,TERMINATED,ERROR} estate;
extern estate state;
extern char errortext[];

// order is important, used in dot_sorter
typedef enum{ down, right, left, up } edir;
enum{ NONE }; // for Command::type

// Important: bitfields must be unsigned, otherwise will get negative values, which is a problem for dir.
// If one of the bitfields is int or enum sizeof(Dot) will be 4 in VS, see https://msdn.microsoft.com/en-us/library/1d48zaa8.aspx
typedef struct Dot Dot;
struct Dot
{
	byte bit:1; // Zero or One
	byte dir:2; // left, right, up or down

	// the following flags are used temporarily inside step
	// after step() is finished all dots have generated/blocked/moved flags set to false and all dots with `destroy` flag are deleted
	byte moved:1;     // used in move_dots
	byte generated:1; // indicates that a dot has been generated by one of :=+_v commands
	byte blocked:1;   // indicates that a dot is blocked from moving according to rule 2.5
	byte destroy:1;   // indicates that a dot will be destroyed (used in handling of dot-dot collisions)
};
c_assert(sizeof(Dot)==1); // important, there are 8 dots in a slot

typedef struct Generator Generator;
struct Generator // ':'
{
	bool on;  // enabled/disabled
	byte bit; // generates Zeros/Ones
};

typedef struct Bar Bar;
struct Bar // '|'
{
	byte state; // '#' or up or down
};

typedef struct Command Command;
struct Command
{
	char type; // NONE, #| :=+ _$^v
	union{
		Generator gen; // type == ':'
		Bar bar;       // type == '|'
	};
};
c_assert(sizeof(Command)==3); // not so important, can be reduced to 2 bytes easily

#define MAXDOTS 8 // todo: explain why 8
typedef struct Slot Slot;
struct Slot
{
	RB_ENTRY(Slot) entry;
	int x;
	int y;

	Command cmd;
	byte ndots;
	Dot dots[MAXDOTS];
	bool create_hash; // used temporarily inside step; true if # will be created in this slot because of dots collision
};

/*
=================== How it was before: ===================

	code = calloc(width*height, sizeof(Slot)); // in readcode
 
	...

	// in other places:

 	for(int y=0; y < height; y++)
	for(int x=0; x < width;  x++)
	{
		Slot* slot = &code[x+y*width];
		...
	}

=================== How it is now: =======================

	RB_INSERT(Code, &code, slot); // in readcode
 
	...

	// in other places:

	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		...
	}

========================================================== 

 With previous approach performance was not enough for polyglot 233 - exec time about 1 min.
 I think problem was that code array was too sparse, invalidated cache too often.
 For example very simple dot_count() function executed for ~20ms.
 So I switched to using red-black tree with key = x+y*width, exec time is 600 ms for polyglot 233 now.

*/
typedef struct Code Code;
RB_HEAD(Code, Slot);
Code code;
int width, height;

//cannot use width in slots_order because RB_INSERT in readcode would work incorrectly
//#define POS(slot) ((slot)->x + (slot)->y * width)

int slots_order(const Slot* a, const Slot* b)
{
	//return POS(a) - POS(b);
	int dy = a->y - b->y;
	int dx = a->x - b->x;
	return dy ? dy : dx;
}

RB_GENERATE(Code, Slot, entry, slots_order)

bool loadfile(char* filename);
bool loadcode(char* str);

bool step();
char* getframe();
// returns whole program state as one big string
// intended for use by dobweb, but can be used by any other client
// one string is easier to pass to js
// state(noprogram|normal|terminated|error) \f errortext \f err_x \f err_y \f breakpoints \f width \f height \f number-of-dots \f number-of-generators \f number-of-active-generators \f number-of-inputs \f reached-end-of-input \f frame-number \f frame-content \f fifo
/* 
[0]  state(noprogram|normal|terminated|error) 
[1]  errortext
[2]  err_x
[3]  err_y
[4]  breakpoints 
[5]  width 
[6]  height 
[7]  number-of-dots 
[8]  number-of-generators 
[9]  number-of-active-generators 
[10] number-of-inputs 
[11] reached-end-of-input 
[12] frame-number
[13] frame-content 
[14] fifo
*/
// getstate and functions it calls must not use asserts - dobweb does not have protection from this
char* getstate();

// implementation is provided by interpreter frontend (dobcon/dobgui/dobweb)
// this function may block until some more input is available if called from console
// if it returned false it means that eof was reached, it will not be called again for current program
bool input(byte* bit);
// this callback is used to clear input buffer
// frontend must have some input buffer because OS input is bytewise and DOBELA input is bitwise
// it is useful only when loadcode/loadfile are called several times (like in dobweb/dobgui, but not dobcon)
void clear_input_buffer();

// implementation is provided by interpreter frontend
// note: output is in bytes, unlike input
// bytes is null-terminated, but may contain null bytes
// count does not include null terminator
void output(byte* bytes, int count);

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

typedef struct Pos{int x,y;} Pos;
array_of(Pos) inputs;
int curinput; // index in inputs
// input reached eof?
bool input_eof = false;
int frame;

// program execution state
// NOPROGRAM - initial state before calling loadfile/loadcode
// NOPROGRAM -> NORMAL or ERROR
// NORMAL - state after loadfile/loadcode if it was successful and after step() if there is no error and program is not terminated
// NORMAL -> NORMAL or TERMINATED or ERROR
// TERMINATED - after step() if program was terminated; loadfile/loadcode is needed to get to NORMAL state
// TERMINATED -> NORMAL or ERROR
// ERROR - after loadfile/loadcode/step failed; loadfile/loadcode is needed to get to NORMAL state
// ERROR -> NORMAL or ERROR
estate state = NOPROGRAM;
char errortext[1024];
int err_x=-1, err_y=-1;
// named ERR to avoid name clash with dobcon.c error() and estate::ERROR
#define ERR(x,y,msg, ...) (snprintf(errortext, countof(errortext)-1, msg, __VA_ARGS__), state = ERROR, err_x=x, err_y=y)


#define DX(dir) ((dir) == left ? -1 : (dir) == right ? 1 : 0)
#define DY(dir) ((dir) == up   ? -1 : (dir) == down  ? 1 : 0)
#define opposite(dir) ((dir) == left ? right : (dir) == right ? left : (dir) == up ? down : up) // turn 180 degrees

#define xyok(x,y) ( (x) >= 0 && (x) < width && (y) >= 0 && (y) < height )

// turn 90 degrees clockwise or counter-clockwise
edir turn(edir dir, bool clockwise)
{
	if  (dir == right) dir = clockwise ? down : up;
	elif(dir == left)  dir = clockwise ? up : down;
	elif(dir == down)  dir = clockwise ? left : right;
	elif(dir == up)    dir = clockwise ? right : left;
	else assert(0 && "Invalid direction");
	return dir;
}

void add_dot(Slot* slot, Dot dot)
{
	assert(slot->ndots < MAXDOTS);
	slot->dots[slot->ndots] = dot;
	slot->ndots++;
}

void remove_dot(Slot* slot, int i)
{
	assert(i >= 0 && i < slot->ndots);
	slot->ndots--;
	if(slot->ndots == 0) return;
	memmove( &slot->dots[i], &slot->dots[i+1], sizeof(Dot) * (slot->ndots - i) );
}

void* __new_tmp;
#define new(type, ...) (__new_tmp=malloc(sizeof(type)), *(type*)__new_tmp=(type)__VA_ARGS__, (type*)__new_tmp)

// helper for readcode
Slot* create_slot(int x, int y, char ch)
{
	switch(ch)
	{
	case '.':
	case ',':
		{
			Slot* slot = new(Slot, {.x=x, .y=y});
			Dot dot = {.bit=(ch=='.'), .dir=right};
			add_dot(slot, dot);
			return slot;
		}
	case '|': return new(Slot, {.x=x, .y=y, .cmd={.type='|', .bar.state='#'}});
	case ':': return new(Slot, {.x=x, .y=y, .cmd={.type=':', .gen={.on=1, .bit=1}}}); // By default, the emission setting is enabled and it outputs Ones.
	case '#':
	case '=':
	case '+':
	case '_':
	case '$':
	case '^':
	case 'v': return new(Slot, {.x=x, .y=y, .cmd={.type=ch}});
	default:  return 0;
	}
}

// str is null-terminated
bool readcode(char* str)
{
	str_array lines = split(str, '\n');

	width = 0;
	height = lines.count;
	for(int y=0; y < height; y++)
	{
		char* line = lines.data[y];
		int len = strlen(line);
		if(len > 0 && line[len-1] == '\r' && y != height-1) line[len] = 0, len--; // last line ends with \0, not \n, hence y != height-1
		if(width < len) width = len;
		
		for(int x=0; x < len;  x++)
		{
			Slot* slot = create_slot(x, y, line[x]);
			if(!slot) continue;
			RB_INSERT(Code, &code, slot);
			if(slot->cmd.type == '_') add_elem(inputs, ((Pos){x,y}));
		}
	}

	delete_ptr_array(lines);

	//if(width == 0) { error("Program must have at least one column"); return false; }
	//assert(height > 0); // even empty program has one line

	state = NORMAL;
	return true;
}

void clear_fifo();
void delete_code();


// loadcode() may be called several times
bool loadcode(char* str)
{
	frame = 0;
	width = height = 0;
	delete_code();

	*errortext = 0;
	err_x = -1;
	err_y = -1;

	delete_array(inputs);
	curinput = 0;
	clear_input_buffer();
	input_eof = false;

	clear_fifo();

	return readcode(str);
}

// loadfile() may be called several times
bool loadfile(char* filename)
{
	char* str = readfile(filename, 0);
	if(!str) { ERR(-1,-1,"Cannot read file %s", filename); return false; }

	bool b = loadcode(str);

	free(str);
	return b;
}

char* getframe()
{
	static char* strframe;

	// +1: \n for all lines except last, \0 for last line
	strframe = realloc(strframe, (width+1)*height);
	memset(strframe, ' ', (width+1)*height);

	for(int y=0; y < height; y++) strframe[width+y*(width+1)] = '\n';
	strframe[(width+1)*height - 1] = 0;

	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		int x = slot->x;
		int y = slot->y;

		// cannot use assert here, see comment for getstate()
		// this assertion fails for spec-tests\invalid-cmd-chain-1
		//assert( (slot.cmd.type == NONE && (slot.ndots == 0 || slot.ndots == 1)) || 
		//		(slot.cmd.type != NONE && slot.ndots == 0) );

		if(slot->cmd.type == NONE)
			strframe[x+y*(width+1)] = slot->ndots == 0 ? ' ' : slot->dots[0].bit ? '.' : ',';
		else
			strframe[x+y*(width+1)] = slot->cmd.type;
	}

/*	//                                 \n        \0
	strframe = realloc(strframe, (width+1)*height+1);
	strframe[(width+1)*height] = 0;

	for(int y=0; y < height; y++)
	{
		for(int x=0; x < width;  x++)
		{
			Slot slot = code[x+y*width];

			// cannot use assert here, see comment for getstate() in interpreter.h
			// this assertion fails for spec-tests\invalid-cmd-chain-1
			//assert( (slot.cmd.type == NONE && (slot.ndots == 0 || slot.ndots == 1)) || 
			//		(slot.cmd.type != NONE && slot.ndots == 0) );

			if(slot.cmd.type == NONE)
				strframe[x+y*(width+1)] = slot.ndots == 0 ? ' ' : slot.dots[0].bit ? '.' : ',';
			else
				strframe[x+y*(width+1)] = slot.cmd.type;
		}
		// need to have same amount of lines as in the code, so last \n is not added
		strframe[width+y*(width+1)] = y == height-1 ? 0 : '\n';
	}
*/
	return strframe;
}

char* get_state_str()
{
	switch(state)
	{
	case NOPROGRAM:  return "noprogram";
	case NORMAL:     return "normal";
	case TERMINATED: return "terminated";
	case ERROR:      return "error";
	default: return "<invalid>"; // cannot use assert here, see comment for getstate()
	}
}

// dot_count must not have asserts because it is called from getstate
int dot_count()
{
	int n = 0;
	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		// using != 0 gives less confusing results when dot_count is called (indirectly by getstate) after error in command chain
		n += slot->ndots != 0;
		//dbg++;
		//printf("x=%03d y=%03d\n", slot->x, slot->y);
	}
	//printf("n=%d slots=%d\n",n,dbg);
	return n;
}

// generator_count must not have asserts because it is called from getstate
void generator_count(int* all_generators, int* active_generators)
{
	*all_generators = 0;
	*active_generators = 0;

	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		if(slot->cmd.type == ':')
		{
			(*all_generators)++;
			*active_generators += slot->cmd.gen.on;
		}
	}
}

char* get_fifo_str();

// see comment for declaration
char* getstate()
{
	static char* strstate;
	char* _state = get_state_str();
	char* breakpoints = ""; // not implemented
	char numbers[1024] = {0};
	int all_generators, active_generators;
	generator_count(&all_generators, &active_generators);
	snprintf(numbers, countof(numbers)-1, "%d\f%d\f%d\f%d\f%d\f%d\f%d\f%d", width, height, dot_count(), all_generators, active_generators, inputs.count, input_eof, frame);
	char* strframe = getframe();
	char* strfifo = get_fifo_str();

	int len = strlen(_state)+1+strlen(errortext)+1+strlen(breakpoints)+1+strlen(numbers)+1+strlen(strframe)+1+strlen(strfifo);
	strstate = realloc(strstate, len+100);
	snprintf(strstate, len+100-1, "%s\f%s\f%d\f%d\f%s\f%s\f%s\f%s", _state, errortext, err_x, err_y, breakpoints, numbers, strframe, strfifo);
	return strstate;
}

// copies everything except dots to code2
/*void copy_static_code()
{
	memset(code2, 0, width*height*sizeof(Slot));

	for(int y=0; y < height; y++)
	for(int x=0; x < width;  x++)
	{
		int pos = x+y*width;
		Slot slot = code[pos];
		code2[pos].cmd = slot.cmd;

		if(slot.cmd.type != NONE)
		{
			// at this point slot must contain either command or dot (or neither) but not both
			assert(slot.ndots == 0);
		}
	}
}*/

// note: code that locates slot in rbtree executes twice - in RB_FIND and RB_INSERT
//       it can be done once, but then we'll have to call `new` in each get_slot (not just when slot not found)
Slot* get_slot(int x, int y)
{
	assert(xyok(x,y));

	Slot dummy = {.x=x, .y=y};
	Slot* slot = RB_FIND(Code, &code, &dummy);
	if(!slot)
	{
		slot = new(Slot, {.x=x, .y=y}); // create empty slot
		RB_INSERT(Code, &code, slot);
	}
	return slot;
}

// each dot is represented by one byte
// dots are enqueued at the start of array and dequeued from the end
array_of(byte) fifo;

void enqueue(byte bit)
{
	insert_elem(fifo, 0, bit);
}

bool dequeue(byte* bit)
{
	if(!fifo.count) return false;
	*bit = fifo.data[fifo.count-1];
	remove_elem(fifo, fifo.count-1);
	return true;
}

void clear_fifo()
{
	delete_array(fifo);
}

// get_fifo_str must not have asserts because it is called from getstate
char* get_fifo_str()
{
	static char* fifo_str;
	fifo_str = realloc(fifo_str, fifo.count + 1);
	for(int i=0; i < fifo.count; i++) fifo_str[i] = fifo.data[i] ? '.' : ',';
	fifo_str[fifo.count] = 0;
	return fifo_str;
}

bool exec_command_or_add_dot(Slot* slot, Dot dot);

// Functions of exec_* family execute only collisions of dots with commands.
// Commands that emit dots regardless of colliding dots (: and _) are handled separately in execute_commands().

// '#' or '|'
// '#' retract, turn 90 deg, exec command in that slot or place dot in a new slot
// note: r.=| creates , moving left regardless of state of | - see rule 3.7.2
bool exec_wall(Slot* slot, Dot dot)
{
	int x = slot->x;
	int y = slot->y;
	Command* cmd = &slot->cmd;

	if(cmd->type == '|' && (dot.dir == up || dot.dir == down))
	{
		cmd->bar.state = dot.dir;
		return true;
	}

	// retract
	edir back = opposite(dot.dir);
	x += DX(back);
	y += DY(back);

	// If a dot would be created on top of a # or |, it is destroyed instead. Except when it is created by '='.
	if(dot.generated)
	{
		if(get_slot(x,y)->cmd.type == '=')
		{
			// go back one more step - don't execute this `=` second time
			x += DX(back);
			y += DY(back);
			dot.dir = back;
			assert(xyok(x,y));
			return exec_command_or_add_dot(get_slot(x,y), dot);
		}
		// else discard the dot
		return true;
	}

	if(cmd->type == '|' && cmd->bar.state != '#')
		dot.dir = cmd->bar.state;
	else // cmd->type == '#' || (cmd->type == '|' && cmd->bar.state == '#')
		dot.dir = turn(dot.dir, !dot.bit); // Zeroes turn 90 degrees clockwise, Ones turn 90 degrees counter-clockwise.

	x += DX(dot.dir);
	y += DY(dot.dir);

	if(!xyok(x,y)) return true; // out of bounds, do nothing (dot is destroyed)

	return exec_command_or_add_dot( get_slot(x,y), dot );
}

// '='
bool exec_equ(Slot* slot, Dot dot)
{
	int x = slot->x;
	int y = slot->y;

	dot.bit = !dot.bit;
	dot.generated = true;
	
	x += DX(dot.dir);
	y += DY(dot.dir);

	if(!xyok(x,y)) return true; // out of bounds, do nothing (dot is destroyed)
	
	return exec_command_or_add_dot( get_slot(x,y), dot );
}

// ':'
// this function only handles colliding dots, dot generation is performed in step()
bool exec_colon(Slot* slot, Dot dot)
{
	assert(slot->cmd.type == ':');
	Generator* gen = &slot->cmd.gen;

	if(dot.dir == down) // If struck from above, its emission setting is toggled.
		gen->on = !gen->on;
	elif(dot.dir == up) // If struck from below, its dot type is toggled
		gen->bit = !gen->bit;

	return true;
}

// '+'
bool exec_plus(Slot* slot, Dot dot)
{
	int x0 = slot->x;
	int y0 = slot->y;
	int x,y;

	dot.generated = true;

	if(dot.dir == left || dot.dir == right)
	{
		dot.dir = up;
		x = x0 + DX(dot.dir);
		y = y0 + DY(dot.dir);
		if(xyok(x,y) && !exec_command_or_add_dot( get_slot(x,y), dot )) return false;
		
		dot.dir = down;
		x = x0 + DX(dot.dir);
		y = y0 + DY(dot.dir);
		if(xyok(x,y) && !exec_command_or_add_dot( get_slot(x,y), dot )) return false;
	}
	else
	{
		dot.dir = left;
		x = x0 + DX(dot.dir);
		y = y0 + DY(dot.dir);
		if(xyok(x,y) && !exec_command_or_add_dot( get_slot(x,y), dot )) return false;
		
		dot.dir = right;
		x = x0 + DX(dot.dir);
		y = y0 + DY(dot.dir);
		if(xyok(x,y) && !exec_command_or_add_dot( get_slot(x,y), dot )) return false;
	}
	return true;
}

// '^'
bool exec_circumflex(Slot* _, Dot dot)
{
	// hit from below - The global FIFO is output to the standard output stream (in FIFO order) and then cleared.
	if(dot.dir == up)
	{
		if(!fifo.count) return true;

		// it will be deleted, so it's ok to reverse inplace
		reverse_array(fifo);

		int len = (fifo.count+7)/8; // bit count -> byte count
		char* str = calloc(len+1,1); // str is null-terminated, but may contain null bytes inside
		
		// last_index + 1 == length:   (fifo.count-1)/8 + 1 == (fifo.count+7)/8
		for(int i=0; i < fifo.count; i++) str[i/8] |= fifo.data[i] << (i%8);

		// fifo is currently in incorrect state (reversed), so call clear_fifo before output callback to handle unlikely situation
		// when frontend tries to read fifo from output callback (eg. using get_fifo_str or getstate function)
		clear_fifo();
		output(str, len);
		free(str);
	}
	// hit from above - The global FIFO is emptied.
	elif(dot.dir == down)
	{
		clear_fifo();
	}
	// hit from left - All generators have their emission setting toggled.
	elif(dot.dir == right)
	{
		Slot* slot;
		RB_FOREACH(slot, Code, &code)
		{
			if(slot->cmd.type == ':') slot->cmd.gen.on = !slot->cmd.gen.on;
		}
	}
	// hit from right - All generators have their dot type toggled.
	else//(dot.dir == left)
	{
		Slot* slot;
		RB_FOREACH(slot, Code, &code)
		{
			if(slot->cmd.type == ':') slot->cmd.gen.bit = !slot->cmd.gen.bit;
		}
	}
	return true;
}

// 'v'
bool exec_v(Slot* slot, Dot dot)
{
	int x = slot->x;
	int y = slot->y;

	byte bit;
	if(!dequeue(&bit)) return true;
	if(dot.dir != up)
	{
		dot.bit = bit;
		dot.generated = true;
		
		x += DX(dot.dir);
		y += DY(dot.dir);

		if(!xyok(x,y)) return true; // out of bounds, do nothing (dot is destroyed)
		
		return exec_command_or_add_dot( get_slot(x,y), dot );
	}
	return true;
}

int level; // should be zeroed before every top-level call of exec_command_or_add_dot() - see step()

// if there is a command at (x,y) then this command is executed on the dot
// if there is no command at (x,y) then the dot is added to slot (x,y)
bool exec_command_or_add_dot(Slot* slot, Dot dot)
{
	if(level++ > 256) // simple protection from eternal recursion
	{
		int x = slot->x;
		int y = slot->y;
		ERR(x,y,"Eternal loop in command chain at %d:%d.", y+1, x+1);
		// this error is propagated to high level (step() function) through returns of false
		// no further processing will be done
		return false;
	}

	switch(slot->cmd.type)
	{
	case '#': 
	case '|': return exec_wall(slot, dot);
	case '=': return exec_equ(slot, dot);
	case ':': return exec_colon(slot, dot);
	case '+': return exec_plus(slot, dot);
	case '_':
		// Just destroy the dot, see rule 1.8. This code executes when _ is part of command chain. 
		// The situation when non-generated dot collides with _ is handled in execute_commands.
		return true; 
	case '$': enqueue(dot.bit); return true;
	case '^': return exec_circumflex(slot, dot);
	case 'v': return exec_v(slot, dot);
	
	case NONE: add_dot(slot, dot); return true;
	}

	assert(0);
	return false; // should never reach here
}

void retract_low_priority_dots();

// helper for step()
void move_dots()
{
	// Important: we modify rbtree while iterating through it.
	// It should not cause problems because we only add new slots, we don't remove slots (get_slot).
	// When dot moves out of a slot it leaves empty slot behind (remove_dot).
	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		if(slot->ndots == 0) continue;
		int x = slot->x;
		int y = slot->y;

		bool dot_handled = false;
		for(int i=0; i < slot->ndots; )
		{
			Dot dot = slot->dots[i];
			if(dot.moved) { i++; continue; }

			assert(!dot_handled); // slot must contain only one dot that is not moved
			dot_handled = true;

			remove_dot(slot, i);

			int dx = DX(dot.dir);
			int dy = DY(dot.dir);

			if(!xyok(x+dx, y+dy)) continue; // if out of bounds do not add dot to newslot, so it is destroyed

			Slot* newslot = get_slot(x+dx, y+dy);
			dot.moved = true;
			add_dot(newslot, dot);
		}
	}

	retract_low_priority_dots();
}


// helper for execute_commands()
bool handle_input(Slot* slot, bool* done)
{
	int x = slot->x;
	int y = slot->y;

	// input reached eof, nothing to do
	if(input_eof) return true;

	if(inputs.count > 1) // multi input
	{
		Pos cur = inputs.data[curinput];
		if(cur.x == x && cur.y == y)
		{
			byte bit;
			if(input(&bit))
			{
				Dot dot = {.bit = bit, .dir = down, .generated = true};
				if(xyok(x,y+1) && !exec_command_or_add_dot( get_slot(x,y+1), dot )) return false;
				if(++curinput == inputs.count) curinput = 0;
			}
			else
				input_eof = true;
			*done = true;
		}
	}
	elif(frame%2 == 0)
	{
		assert(inputs.count == 1 && inputs.data[0].x == x && inputs.data[0].y == y);
		byte bit;
		if(input(&bit))
		{
			Dot dot = {.bit = bit, .dir = down, .generated = true};
			if(xyok(x,y+1) && !exec_command_or_add_dot( get_slot(x,y+1), dot )) return false;
		}
		else
			input_eof = true;
	}
	return true;
}


// sort dots occupying same slot
// first dots that come from above (dir == down)
// then  dots that come from left  (dir == right)
// then  dots that come from right (dir == left)
// then  dots that come from below (dir == up)
// note: if there are several dots that came from the same direction their order is unspecified (may be arbitrary)
//       it doesn't matter because they both will be destryed in abnormal collision
//       dot_sorter is not used for dots that exist only inside command chain, like in spec-tests\two-dots-one-dir-inside-cmd-chain
//       order in that situation is determined by order of processing commands
int dot_sorter(Dot* dot0, Dot* dot1)
{
	return dot0->dir - dot1->dir;
}

// helper for step()
bool execute_commands()
{
	bool done_input = false;

	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		// process only slots with commands
		if(slot->cmd.type == NONE) continue;

		// handle input
		if(slot->cmd.type == '_')
		{
			slot->ndots = 0; // rule 1.8, see also exec_command_or_add_dot
			// done_input == true: there are several inputs and one of them has been already handled in this step
			if(done_input) continue;
			level = 0; // handle_input calls exec_command_or_add_dot
			if(!handle_input(slot, &done_input)) return false;
			continue;
		}

		// dots need to be sorted because they should be executed in correct (reading) order
		// dots on step 1 (move_dots) were processed in reading order, but at this point some command may already have been executed, 
		// which may mess the order - see spec-tests\exec-order-test
		qsort(slot->dots, slot->ndots, sizeof(Dot), (int(*)(const void*, const void*))dot_sorter);
	
		// special handling for generator: ensure that colliding dots and dot generation occur in correct order (reading order)
		if(slot->cmd.type == ':')
		{
			// 1) process dots coming from above and from left
			while(slot->ndots != 0 && (slot->dots[0].dir == down || slot->dots[0].dir == right))
			{
				Dot dot = slot->dots[0];
				remove_dot(slot, 0);
				// exec_colon doesn't call exec_command_or_add_dot, no need to level = 0;
				exec_colon(slot, dot);
			}

			// 2) generate a dot
			if(slot->cmd.gen.on)
			{
				int x = slot->x;
				int y = slot->y;
				Dot dot = {.bit = slot->cmd.gen.bit, .dir = right, .generated = true};
				level = 0;
				if(xyok(x+1,y) && !exec_command_or_add_dot( get_slot(x+1,y), dot )) return false;
			}

			// 3) process dots coming from right and from below
			while(slot->ndots != 0 && (slot->dots[0].dir == left || slot->dots[0].dir == up))
			{
				Dot dot = slot->dots[0];
				remove_dot(slot, 0);
				exec_colon(slot, dot);
			}

			assert(slot->ndots == 0);
			continue;
		}
	
		while(slot->ndots)
		{
			Dot dot = slot->dots[0];
			remove_dot(slot, 0);
			level = 0;
			if(!exec_command_or_add_dot(slot, dot)) return false;
		}
	}
	return true;
}

void warning(char* msg, ...){} // stub
#define dot_to_string(dot) ""  // stub

// return index of the first dot in slot for which pred is true
// return -1 if no such dot found
int find_dot(Slot* slot, bool (*pred)(Dot dot))
{
	for(int i = 0; i < slot->ndots; i++)
	{
		if(pred(slot->dots[i])) return i;
	}
	return -1;
}


bool is_nonblocked_down(Dot dot) { return !dot.blocked && dot.dir == down; }
bool is_nonblocked_left_or_right(Dot dot) { return !dot.blocked && (dot.dir == left || dot.dir == right); }

// Note that we don't retract low priority dot if high priority dot itself is blocked from moving.
// According to rule 2.6 such dots should collide, I call it "abnormal collision".
// Test case: spec-tests\chain-of-dots-blocked-from-moving
//
// retract_low_priority_dots was previously called from handle_dot_collisions (ie. after execute_commands), hence
// the checks for dot.generated; these checks are redundant now
void retract_low_priority_dots()
{
	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		int x = slot->x;
		int y = slot->y;

		// there should be no dots over commands at this stage
		// -no, now retract_low_priority_dots is called right after all dots moved, so there can be dots over commands
		//assert(!(slot->cmd.type != NONE && slot->ndots != 0));
		// process only slots with multiple dots without commands
		if(slot->ndots <= 1 || slot->cmd.type != NONE) continue;

		// if there are nonblocked dots in the slot that came from above retract all the dots that came from left and right
		if(find_dot(slot, is_nonblocked_down) != -1)
		{
			for(int i=0; i < slot->ndots; )
			{
				Dot dot = slot->dots[i];
				// if dot is generated then it is abnormal collision (rule 2.5.1), it will be handled later
				if((dot.dir == left || dot.dir == right) && !dot.generated)
				{
					remove_dot(slot, i);
					edir back = opposite(dot.dir);
					int x1 = x+DX(back);
					int y1 = y+DY(back);
					assert(xyok(x1,y1));
					dot.blocked = true;
					add_dot(get_slot(x1,y1), dot);
				}
				else
					i++;
			}
		}
		// else: there are no nonblocked dots in the slot that came from above
		// if there are nonblocked dots in the slot that came from left or right then retract all the dots that came from below (dot.dir == up)
		elif(find_dot(slot, is_nonblocked_left_or_right) != -1)
		{
			for(int i=0; i < slot->ndots; )
			{
				Dot dot = slot->dots[i];
				// if dot is generated then it is abnormal collision (rule 2.5.1), it will be handled later
				if(dot.dir == up && !dot.generated)
				{
					remove_dot(slot, i);
					edir back = opposite(dot.dir);
					int x1 = x+DX(back);
					int y1 = y+DY(back);
					assert(xyok(x1,y1));
					dot.blocked = true;
					add_dot(get_slot(x1,y1), dot);
				}
				else
					i++;
			}
		}//elif
	}//for
}


// `normal` dot here means nonblocked and nongenerated
bool is_normal_left (Dot dot) { return !dot.blocked && !dot.generated && dot.dir == left;  }
bool is_normal_right(Dot dot) { return !dot.blocked && !dot.generated && dot.dir == right; }
bool is_normal_up   (Dot dot) { return !dot.blocked && !dot.generated && dot.dir == up;    }
bool is_normal_down (Dot dot) { return !dot.blocked && !dot.generated && dot.dir == down;  }

// helper for step()
/*
Slot:
---1---
|     |
|     |
2  3  4
|     |
|     |
---5---
Order of handling collisions:
(1) pass-over collision through upper edge (dot.dir == down) - should never happen, should already be handled by upper slot
(2) pass-over collision through left edge (dot.dir == right) - should never happen, should already be handled by left slot
 3. same-slot collision
 3.1 handle dots that came from above (dot.dir == down) (there can be multiple slots that came from one direction - see spec-tests\gen-test-2-dots-from-one-side)
 3.2 handle dots that came from left (dot.dir == right)
 3.3 handle dots that came from right (dot.dir == left)
 3.4 handle dots that came from below (dot.dir == up)
  - no, handle all of them simultaneously
 4. pass-over collision through right edge (dot.dir == left)
 5. pass-over collision through lower edge (dot.dir == up)
*/
void handle_dot_collisions()
{
	// now detect all collisions at once without destroying any dots (but note: some dots were already destroyed in retract_low_priority_dots)
	//  - not true, generated and blocked dots can be safely destroyed here because they don't participate in pass-over collisions
	// this is done to achieve consistent behavior in this situation: spec-tests\collision-test-one-line
	Slot* slot;
	RB_FOREACH(slot, Code, &code)
	{
		int x = slot->x;
		int y = slot->y;
		int i,ii;
		int x1,y1;
		Slot* slot1;

		// process only slots with dots
		if(slot->ndots == 0) continue;
		// there should be no dots over commands at this stage
		// checking here again because dot retraction may have messed things up
		assert(slot->cmd.type == NONE);

		// 3. same-slot collision
		// at this point we still may have dots in the same slot with same or perpendicular directions (abnormal collision, rule 2.6, example: spec-tests\chain-of-dots-blocked-from-moving), 
		// as well as with opposite directions (normal same-slot collision)
		// posible variants:
		// 1) head-on collision of two normal dots of the same type (Zero and Zero or One and One)
		//    result: destroy both dots, create hash
		// 2) head-on collision of two normal dots of different types
		//    result: destroy both dots
		// 3) abnormal collision of two dots generated by the same command
		//    result: destroy one of the dots, create hash
		// 4) abnormal collision with a blocked dot according to rule 2.6
		//    result: destroy both dots, create hash
		// 5) abnormal collision of a generated dot and a dot of higher priority moving in perpendicular direction
		//    result: destroy both dots, create hash
		//
		if(slot->ndots >= 2)
		{
			Dot dot0 = slot->dots[0];
			Dot dot1 = slot->dots[1];
			// detect head-on collision of two dots
			// head-on collision of two dots of different types is the only type of same-slot collision when hash is not created
			if(slot->ndots == 2 && dot0.dir == opposite(dot1.dir))
			{
				// head-on collision with a blocked dot is not possible
				// if blocked dot is moving left or right than the dot moving in opposite direction is also blocked
				// if blocked dot is moving up then head-on collision is happening with the dot moving down, so dots moving left and right are blocked,
				// so the dot moving up cannot be blocked
				assert(!dot0.blocked && !dot1.blocked);
				// note: one or both of the dots may be generated
				// note: create_hash may already be set by handling pass-over collision in upper or left slot, so using |= here
				slot->create_hash |= (dot0.bit == dot1.bit);
			}
			// if after retract_low_priority_dots there are more than two dots in a slot or
			// two dots with the same or perpendicular directions
			// then it is definitely an abnormal collision
			else
				slot->create_hash = true;
	
			for(int i=0; i < slot->ndots; i++)
				slot->dots[i].destroy = true;
 		}
		// note: a dot can participate both in same-slot and pass-over collisions simultaneously

		// pass-over collision can happen only with "normal" dots (nonblocked and nongenerated)
		// 4. pass-over collision through right edge
		x1 = x+1;
		y1 = y;
		slot1 = xyok(x1,y1) ? get_slot(x1,y1) : 0;
		if( slot1 != 0 &&
			// if there is a normal dot in this slot that moves left (there can be only one such dot) ...
			(i=find_dot(slot, is_normal_left)) != -1 && 
			// ... and there is a dot in right adjacent slot that moves right (there can be only one such dot) ...
			(ii=find_dot(slot1, is_normal_right)) != -1 )
		{
			Dot* dot0 = &slot->dots[i];
			Dot* dot1 = &slot1->dots[ii];
			
			// ... and these dots are of the same type
			if(dot0->bit == dot1->bit)
				(!dot0->bit ? slot : slot1)->create_hash = true;
	
			dot0->destroy = true;
			dot1->destroy = true;
		}
		
		// 5. pass-over collision through lower edge
		x1 = x;
		y1 = y+1;
		slot1 = xyok(x1,y1) ? get_slot(x1,y1) : 0;
		if( slot1 != 0 &&
			(i=find_dot(slot, is_normal_up)) != -1 && 
			(ii=find_dot(slot1, is_normal_down)) != -1 )
		{
			Dot* dot0 = &slot->dots[i];
			Dot* dot1 = &slot1->dots[ii];
			
			if(dot0->bit == dot1->bit)
				(!dot0->bit ? slot : slot1)->create_hash = true;
	
			dot0->destroy = true;
			dot1->destroy = true;
		}
	}

	// final step: delete all dots that participated in collisions and create hashes where necessary
	RB_FOREACH(slot, Code, &code)
	{
		for(int i=0; i<slot->ndots; )
		{
			if(slot->dots[i].destroy)
				remove_dot(slot, i);
			else
				i++;
		}

		if(slot->create_hash)
		{
			assert(slot->cmd.type == NONE);
			slot->cmd.type = '#';
			slot->create_hash = false;
		}

		assert(slot->ndots <= 1);
		assert(!(slot->cmd.type != NONE && slot->ndots != 0));
	}
}


void cleanup()
{
	Slot* slot = RB_MIN(Code, &code);
	while(slot)
	{
		Slot* next = RB_NEXT(Code, &code, slot);
		// delete empty slots for performance
		// keep number of slots low, otherwise it reaches 30000 at the end of executing polyglot 233 and all stages become slow
		if(slot->cmd.type == NONE && slot->ndots == 0)
		{
			Slot* rem = RB_REMOVE(Code, &code, slot);
			assert(rem == slot);
			free(slot);
		}
		// clear temporary flags of all dots
		elif(slot->ndots != 0)
		{
			assert(slot->ndots == 1);
			Dot* dot = &slot->dots[0];
			dot->generated = dot->blocked = dot->moved = false;
			assert(!dot->destroy);
		}
		slot = next;
	}
}

void delete_code()
{
	Slot* slot = RB_MIN(Code, &code);
	while(slot)
	{
		Slot* next = RB_NEXT(Code, &code, slot);

		Slot* rem = RB_REMOVE(Code, &code, slot);
		assert(rem == slot);
		free(slot);

		slot = next;
	}
}

// see impl.txt
bool step()
{
	// if state is NOPROGRAM/TERMINATED/ERROR there is nothing to do,
	// loadfile/loadcode needs to be called to get to NORMAL state
	if(state != NORMAL) return false;

	// 1. Move all dots. Some of them will end up on each other or on some commands.
	move_dots();
	
	// 2. Execute all commands in reading order. Purpose of this step is get rid of all dots that are on commands.
	//    And also execute generating commands : and _
	//    If execute_commands() returned false then state was changed to ERROR, see exec_command_or_add_dot()
	if(!execute_commands()) return false;

	// 3. Handle dot-dot collisions.
	handle_dot_collisions();

	// 4. clear temporary flags in all dots, delete empty slots
	cleanup();

	frame++;

	// 5. determine whether program is terminated or not, see rule 3.4
	state = ((inputs.count == 0 || input_eof) && dot_count() == 0 ? TERMINATED : NORMAL);
	return state == NORMAL;
}