sf2xed/sf2xed.py

#!/usr/bin/env python3
import enum
import sys
from collections import namedtuple

class actions(enum.Enum):
	change, left, right, nothing = range(4)

State = namedtuple('State', ['action', 'transitions', 'reachable'])

class SFParseError(Exception): pass

def parse_smallfuck(s):
	def parse(s, index = 0, in_loop = False):
		parsed = []
		while True:
			assert index <= len(s)
			if index == len(s):
				if in_loop:
					raise SFParseError('Unexpected end of text (expected "]")')
				else:
					break

			c = s[index]
			index += 1

			if c == ']':
				if in_loop:
					break
				else:
					raise SFParseError('Unexpected "]"')

			elif c == '[':
				loop, index = parse(s, index, True)
				parsed.append(loop)

			elif c in ['<', '>', '*']:
				parsed.append(c)

		return parsed, index

	parsed, index = parse(s)
	return parsed

def turingify(parsed):
	states = []
	def add_state(action, transitions):
		nonlocal states
		assert action in actions
		assert len(transitions) == 2

		index = len(states)
		states.append(State(action, transitions, [False, False]))

		return index

	def worker(parsed, end = None):
		nonlocal states

		while len(parsed) > 0:
			c = parsed[-1]
			parsed = parsed[:-1]

			if type(c) == list:
				loop_test = add_state(actions.nothing, [end, None])
				loop_body = worker(c, loop_test)
				# We want the loop to repeat if the cell is set
				states[loop_test].transitions[1] = loop_body
				end = loop_test

			elif c == '*':
				end = add_state(actions.change, [end, end])

			elif c == '<':
				end = add_state(actions.left, [end, end])

			elif c == '>':
				end = add_state(actions.right, [end, end])

			else:
				assert not "Unreachable"

		return end

	return worker(parsed), states

def prettyprint_states(states):
	for i in range(len(states)):
		state = states[i]
		action = {actions.change: '* ', actions.left: '< ', actions.right: '> ', actions.nothing: ''}[state.action]
		if state.reachable == [True, True]:
			reachable = '(*)'
		elif state.reachable == [True, False]:
			reachable = '(0)'
		elif state.reachable == [False, True]:
			reachable = '(1)'
		elif state.reachable == [False, False]:
			reachable = '(!)'
		else:
			reachable = ''
		print('%4i%s: %s%s' % (i, reachable, action, state.transitions))

def reachability(start, states):
	def copy_state(index):
		state = states[index]
		action = state.action
		transitions = state.transitions[:]
		reachable = [False if i is None else i for i in state.reachable]
		return State(action, transitions, reachable)

	# Since we always end up with start at index 0, no need to create processed_start
	processed = [copy_state(start)]
	processed[0].reachable[0] = True
	processed[0].reachable[1] = True
	translations = {start: 0}

	processed_sweep = 0
	while processed_sweep < len(processed):
		for i in range(len(processed[processed_sweep].transitions)):
			index_states = processed[processed_sweep].transitions[i]

			# Nothing to be done if we point to halt state
			if index_states is None:
				continue

			# Copy the state to processed if it isn't already there
			if index_states not in translations:
				index_processed = len(processed)
				processed.append(copy_state(index_states))
				translations[index_states] = index_processed

			# Fix transition to the state
			processed[processed_sweep].transitions[i] = translations[index_states]

			# Mark how we got to the state
			processed[translations[index_states]].reachable[i] = True

		processed_sweep += 1

	return processed

def string_id(state, value, processed):
	def intlog(num, base):
		# This is floor(log_{base} num)
		assert num > 0
		result = 0
		while num > base - 1:
			num = num // base
			result += 1
		return result

	assert value == 0 or value == 1
	assert state is None or 0 <= state < len(processed)

	# One for each (cell value, state) combination and one for the cell values without a state
	max_num = 2 * len(processed) + 2 - 1
	# Base 62 because we have 0-9A-Za-y, +1 because the intlog is one less than the digits needed
	width = intlog(max_num, 61) + 1

	if state is not None:
		num = 2 * (state + 1) + value
	else:
		num = value

	digits = []

	while num > 0:
		digit = num % 61
		num = num // 61

		if digit < 10:
			digits.append(chr(ord('0') + digit))
		elif digit < 36:
			digits.append(chr(ord('A') + digit - 10))
		else:
			digits.append(chr(ord('a') + digit - 36))

	string = ''.join(reversed(digits))

	# Pad to width
	string = '0' * (width - len(string)) + string

	return string

def create_replacements(processed):
	replacements = []

	for index in range(len(processed)):
		state = processed[index]

		if state.action == actions.nothing:
			for value in [0, 1]:
				if state.reachable[value]:
					start = string_id(index, value, processed)
					end = string_id(state.transitions[value], value, processed)
					replacements.append((start, end))

		elif state.action == actions.change:
			for original_value in [0, 1]:
				if state.reachable[original_value]:
					changed_value = original_value ^ 1
					start = string_id(index, original_value, processed)
					end = string_id(state.transitions[changed_value], changed_value, processed)
					replacements.append((start, end))

		elif state.action == actions.left:
			for this_value in [0, 1]:
				if state.reachable[this_value]:
					for left_value in [0, 1]:
						this_start = string_id(index, this_value, processed)
						left_start = string_id(None, left_value, processed)
						start = '%s %s' % (left_start, this_start)

						this_end = string_id(None, this_value, processed)
						left_end = string_id(state.transitions[left_value], left_value, processed)
						end = '%s %s' % (left_end, this_end)

						replacements.append((start, end))

		elif state.action == actions.right:
			for this_value in [0, 1]:
				if state.reachable[this_value]:
					for right_value in [0, 1, None]:
						this_start = string_id(index, this_value, processed)
						if right_value is not None:
							right_start = string_id(None, right_value, processed)
						else:
							right_start = 'z'
						start = '%s %s' % (this_start, right_start)

						this_end = string_id(None, this_value, processed)
						if right_value is not None:
							right_end = string_id(state.transitions[right_value], right_value, processed)
						else:
							right_end = string_id(state.transitions[0], 0, processed) + ' z'
						end = '%s %s' % (this_end, right_end)

						replacements.append((start, end))

		else:
			assert not "Unreachable"

	return replacements

def xedify(replacements):
	replaced = '|'.join(start for start, end in replacements)
	replacement = '|'.join(end for start, end in replacements)

	return 'x/%s/%s/' % (replaced, replacement)

def process_tape(tape, processed):
	assert all(i in ['0', '1', '^0', '^1'] for i in tape)
	processed_tape = []
	for i in tape:
		if i == '0':
			processed_tape.append(string_id(None, 0, processed))
		elif i == '1':
			processed_tape.append(string_id(None, 1, processed))
		elif i == '^0':
			processed_tape.append(string_id(0, 0, processed))
		elif i == '^1':
			processed_tape.append(string_id(0, 1, processed))
		else:
			assert not "Unreachable"

	return ' '.join(processed_tape) + ' z'

def run_replacements(replacements, processed_tape):
	while True:
		made_replacement = False
		for start, end in replacements:
			if start in processed_tape:
				processed_tape = processed_tape.replace(start, end)
				made_replacement = True
				break

		if not made_replacement:
			break

		print(processed_tape)

def main():
	if len(sys.argv) == 2 and sys.argv[1] == '-r':
		run = True
	else:
		run = False

	program = input('program: ')

	start_noreachability, states_noreachability = turingify(parse_smallfuck(program))
	processed = reachability(start_noreachability, states_noreachability)

	replacements = create_replacements(processed)
	print(xedify(replacements))

	print('\nSend empty to exit. ^0/^1 for initial tape head position')
	while True:
		tape = input('tape: ')
		if tape == '': break
		tape = tape.split(' ')
		processed_tape = process_tape(tape, processed)
		print(processed_tape)

		if run:
			run_replacements(replacements, processed_tape)

if __name__ == '__main__':
	main()