path: root/subex/main.go

package subex

import (
	"main/walk"
)

type Transducer struct {
	storeSize int
	initialState SubexState
}

type StoreItem struct {}
// Where slots are stored
type Store []walk.OutputList
// Return a new store with all the data from this one
func (store Store) clone() Store {
	newStore := make([]walk.OutputList, len(store))
	copy(newStore, store)
	return newStore
}
// Return a copy of this store but with an additional slot set
func (store Store) withValue(key int, value walk.OutputList) Store {
	newStore := store.clone()
	newStore[key] = value
	return newStore
}

type SlotMap struct {
	nextId int
	ids map[rune]int
}
func (m *SlotMap) getId(slot rune) int {
	id, exists := m.ids[slot]
	if exists {
		return id
	}
	id = m.nextId
	m.nextId++
	m.ids[slot] = id
	return id
}

// Compile the SubexAST into a transducer SubexState that can be run
func CompileTransducer(transducerAst SubexAST) Transducer {
	slotMap := SlotMap {
		nextId: 0,
		ids: make(map[rune]int),
	}
	initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap, false)
	return Transducer {
		storeSize: slotMap.nextId,
		initialState: initial,
	}
}

// An immutable stack for outputting to
type OutputStack struct {
	head walk.OutputList
	tail *OutputStack
}
func (stack OutputStack) pop() (walk.OutputList, OutputStack) {
	return stack.head, *stack.tail
}
func (stack OutputStack) push(atoms walk.OutputList) OutputStack {
	return OutputStack {
		head: atoms,
		tail: &stack,
	}
}
func (stack OutputStack) replace(atoms walk.OutputList) OutputStack {
	return OutputStack {
		head: atoms,
		tail: stack.tail,
	}
}
func (stack OutputStack) peek() walk.OutputList {
	return stack.head
}

func topAppend(outputStack OutputStack, values []walk.Value) OutputStack {
	head, isValues := outputStack.peek().(walk.ValueList)
	if !isValues {
		panic("Tried to append a value to an output of non-values")
	}
	head = append(walk.ValueList{}, head...)
	head = append(head, values...)
	return outputStack.replace(head)
}

func topAppendRunes(outputStack OutputStack, runes walk.RuneList) OutputStack {
	head, isRunes := outputStack.peek().(walk.RuneList)
	if !isRunes {
		panic("Tried to append runes to a non-rune list")
	}
	head = append(walk.RuneList{}, head...)
	head = append(head, runes...)
	return outputStack.replace(head)
}

// Addition state that goes along with a subex state in an execution branch
type auxiliaryState struct {
	// Content of slots in this branch
	store Store
	// The output stack. At the end of the program, whatever is on top of this will be output
	// States may push or pop to the stack as they wish, creating sort of a call stack that allows states to capture the output of other states
	outputStack OutputStack
	// How deeply nested the current execution is inside of the overall value
	// i.e. starts at zero, is incremented to one when entering an array
	nesting int
}

func (aux auxiliaryState) cloneStore() auxiliaryState {
	aux.store = aux.store.clone()
	return aux
}

func (aux auxiliaryState) withValue(slot int, value walk.OutputList) auxiliaryState {
	aux.store = aux.store.withValue(slot, value)
	return aux
}

func (aux auxiliaryState) pushOutput(data walk.OutputList) auxiliaryState {
	aux.outputStack = aux.outputStack.push(data)
	return aux
}

func (aux auxiliaryState) popOutput() (walk.OutputList, auxiliaryState) {
	data, output := aux.outputStack.pop()
	aux.outputStack = output
	return data, aux
}

func (aux auxiliaryState) topAppend(values walk.OutputList) auxiliaryState {
	switch output := values.(type) {
	case walk.ValueList:
		aux.outputStack = topAppend(aux.outputStack, output)
	case walk.RuneList:
		aux.outputStack = topAppendRunes(aux.outputStack, output)
	}
	return aux
}

func (aux auxiliaryState) incNest() auxiliaryState {
	aux.nesting++
	return aux
}

func (aux auxiliaryState) decNest() auxiliaryState {
	aux.nesting--
	return aux
}

// One branch of subex execution
type SubexBranch struct {
	// State in this branch
	state SubexState
	// Axiliary state
	aux auxiliaryState
}
// Read a single character and return all the branches resulting from this branch consuming it
func (pair SubexBranch) eat(char walk.Edible) []SubexBranch {
	return pair.state.eat(pair.aux, char)
}
func (pair SubexBranch) accepting() []OutputStack {
	return pair.state.accepting(pair.aux)
}

func equalStates(left SubexBranch, right SubexBranch) bool {
	// Only care about if they are the same pointer
	return left.state == right.state && left.aux.nesting == right.aux.nesting
}

// If two branches have the same state, only the first has a chance of being successful
// This function removes all of the pointless execution branches to save execution time
func pruneStates(states []SubexBranch) []SubexBranch {
	uniqueStates := 0
	outer: for _, state := range states {
		for i := 0; i < uniqueStates; i++ {
			if equalStates(state, states[i]) {
				continue outer
			}
		}
		states[uniqueStates] = state
		uniqueStates++
	}
	return states[:uniqueStates]
}

func processInput(states []SubexBranch, input walk.StructureIter, nesting int) []SubexBranch {
	if len(states) == 0 {
		return states
	}
	var tmp []SubexBranch
	newStates := make([]SubexBranch, 0, 2)
	for {
		piece := input.Next()
		if piece == nil {
			break
		}

		// TODO: break if there are no states at this nesting level left
		// TODO: What to do if there are remaining nested states after all pieces have been used?
		for _, state := range states {
			if state.aux.nesting == nesting {
				newStates = append(newStates, state.eat(piece)...)
			} else {
				newStates = append(newStates, state)
			}
		}

		structure, isStructure := piece.(walk.Structure)
		if isStructure {
			iter := structure.Iter()
			newStates = processInput(newStates, iter, nesting + 1)
		}

		tmp = states
		states = pruneStates(newStates)
		newStates = tmp[:0]
		if len(states) == 0 {
			return states
		}
	}
	return states
}

// Run the subex transducer
func RunTransducer(transducer Transducer, input walk.ValueList) (output []walk.Value, err bool) {
	states := []SubexBranch{{
		state: transducer.initialState,
		aux: auxiliaryState {
			outputStack: OutputStack {
				head: walk.ValueList{},
				tail: nil,
			},
			store: make([]walk.OutputList, transducer.storeSize),
			nesting: 0,
		},
	}}

	states = processInput(states, walk.NewValueIter(input), 0)

	for _, state := range states {
		acceptingStacks := state.accepting()
		for _, stack := range acceptingStacks {
			output, isValues := stack.head.(walk.ValueList)
			if !isValues {
				panic("Tried to output a non-values list")
			}
			return output, false
		}
	}
	return nil, true
}