Huge refactor to a more value based system, doing away with terminals. Also introduces unit testing

1 files changed, 204 insertions, 158 deletions

diff --git a/subex/subexstate.go b/subex/subexstate.go
index 7ecff0c..7ffd592 100644
--- a/subex/subexstate.go
+++ b/subex/subexstate.go
@@ -1,5 +1,8 @@
 package subex
 
+// TODO: Simplify this implementation by combining similar states into one type
+// e.g. Combine all of the copy states into a single type that has a filter function
+
 import (
 	"main/walk"
 )
@@ -7,21 +10,58 @@ import (
 // A state of execution for the transducer
 type SubexState interface {
 	// Eat a Atom and transition to any number of new states
-	eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch
+	eat(aux auxiliaryState, char walk.Edible) []SubexBranch
 	// Find accepting states reachable through epsilon transitions and return their outputs
-	accepting(store Store, outputStack OutputStack) []OutputStack
+	accepting(aux auxiliaryState) []OutputStack
 }
 
 // Try first, if it fails then try second
 type SubexGroupState struct {
 	first, second SubexState
 }
-func (state SubexGroupState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	otherStore := store.clone()
-	return append(state.first.eat(store, outputStack, char), state.second.eat(otherStore, outputStack, char)...)
+func (state SubexGroupState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	otherAux := aux.cloneStore()
+	return append(state.first.eat(aux, char), state.second.eat(otherAux, char)...)
+}
+func (state SubexGroupState) accepting(aux auxiliaryState) []OutputStack {
+	otherAux := aux.cloneStore()
+	return append(state.first.accepting(aux), state.second.accepting(otherAux)...)
+}
+
+type SubexCopyState struct {
+	next SubexState
+	filter valueFilter
+}
+func (state SubexCopyState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	value, isValue := edible.(walk.Value)
+	if !isValue || !state.filter.valueFilter(value) {
+		return nil
+	}
+	return []SubexBranch{{
+		state: state.next,
+		aux: aux.topAppend(walk.ValueList{value}),
+	}}
+}
+func (state SubexCopyState) accepting(aux auxiliaryState) []OutputStack {
+	return nil
+}
+
+type SubexCopyRuneState struct {
+	next SubexState
+	filter runeFilter
+}
+func (state SubexCopyRuneState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	r, isRune := edible.(walk.StringRuneAtom)
+	if !isRune || !state.filter.runeFilter(r) {
+		return nil
+	}
+	return []SubexBranch{{
+		state: state.next,
+		aux: aux.topAppend(walk.RuneList{r}),
+	}}
 }
-func (state SubexGroupState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return append(state.first.accepting(store, outputStack), state.second.accepting(store, outputStack)...)
+func (state SubexCopyRuneState) accepting(aux auxiliaryState) []OutputStack {
+	return nil
 }
 
 // Just pushes to the OutputStack and hands over to the next state
@@ -29,24 +69,37 @@ func (state SubexGroupState) accepting(store Store, outputStack OutputStack) []O
 type SubexCaptureBeginState struct {
 	next SubexState
 }
-func (state SubexCaptureBeginState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	return state.next.eat(store, outputStack.push(nil), char)
+func (state SubexCaptureBeginState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	return state.next.eat(aux.pushOutput(walk.ValueList{}), char)
+}
+func (state SubexCaptureBeginState) accepting(aux auxiliaryState) []OutputStack {
+	return state.next.accepting(aux.pushOutput(walk.ValueList{}))
 }
-func (state SubexCaptureBeginState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return state.next.accepting(store, outputStack.push(nil))
+func (state SubexCaptureBeginState) String() string {
+	return "CaptureBeginState"
+}
+
+type SubexCaptureRunesBeginState struct {
+	next SubexState
+}
+func (state SubexCaptureRunesBeginState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	return state.next.eat(aux.pushOutput(walk.RuneList{}), char)
+}
+func (state SubexCaptureRunesBeginState) accepting(aux auxiliaryState) []OutputStack {
+	return state.next.accepting(aux.pushOutput(walk.RuneList{}))
 }
 
 // Discard the top of the OutputStack
 type SubexDiscardState struct {
 	next SubexState
 }
-func (state SubexDiscardState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	_, newStack := outputStack.pop()
-	return state.next.eat(store, newStack, char)
+func (state SubexDiscardState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	_, newAux := aux.popOutput()
+	return state.next.eat(newAux, char)
 }
-func (state SubexDiscardState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	_, newStack := outputStack.pop()
-	return state.next.accepting(store, newStack)
+func (state SubexDiscardState) accepting(aux auxiliaryState) []OutputStack {
+	_, newAux := aux.popOutput()
+	return state.next.accepting(newAux)
 }
 
 // Pop the top of the OutputStack which contains the stuff outputted since the start of the store
@@ -55,35 +108,41 @@ type SubexStoreEndState struct {
 	slot int
 	next SubexState
 }
-func (state SubexStoreEndState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	toStore, newStack := outputStack.pop()
-	return state.next.eat(store.withValue(state.slot, toStore), newStack, char)
+func (state SubexStoreEndState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	toStore, aux := aux.popOutput()
+	aux = aux.withValue(state.slot, toStore)
+	return state.next.eat(aux, char)
 }
-func (state SubexStoreEndState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	toStore, newStack := outputStack.pop()
-	return state.next.accepting(store.withValue(state.slot, toStore), newStack)
+func (state SubexStoreEndState) accepting(aux auxiliaryState) []OutputStack {
+	toStore, aux := aux.popOutput()
+	aux = aux.withValue(state.slot, toStore)
+	return state.next.accepting(aux)
 }
 
 // A part of an output literal, either an Atom or a slot from which to load
 type OutputContent interface {
 	// Given the current store, return the []Atom produced by the TransducerOutput
-	build(Store) []walk.Atom
+	build(Store) walk.ValueList
 }
 
 // An OutputContent which is just an Atom literal
 type OutputAtomLiteral struct {
-	atom walk.Atom
+	atom walk.Value
 }
-func (replacement OutputAtomLiteral) build(store Store) []walk.Atom {
-	return []walk.Atom{replacement.atom}
+func (replacement OutputAtomLiteral) build(store Store) walk.ValueList {
+	return walk.ValueList{replacement.atom}
 }
 
 // An OutputContent which is a slot that is loaded from
 type OutputLoad struct {
 	slot int
 }
-func (replacement OutputLoad) build(store Store) []walk.Atom {
-	return store[replacement.slot]
+func (replacement OutputLoad) build(store Store) walk.ValueList {
+	values, isValues := store[replacement.slot].(walk.ValueList)
+	if !isValues {
+		panic("Tried to output non-values list")
+	}
+	return values
 }
 
 // Don't read in anything, just output the series of data and slots specified
@@ -92,189 +151,176 @@ type SubexOutputState struct {
 	next SubexState
 }
 // Given a store, return what is outputted by an epsilon transition from this state
-func (state SubexOutputState) build(store Store) []walk.Atom {
-	var result []walk.Atom
+// TODO: separate into buildValues and buildRunes
+func (state SubexOutputState) build(store Store) walk.ValueList {
+	var result walk.ValueList
 	for _, part := range state.content {
 		result = append(result, part.build(store)...)
 	}
 	return result
 }
-func (state SubexOutputState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	content := state.build(store)
-	nextStates := state.next.eat(store, topAppend(outputStack, content), char)
+func (state SubexOutputState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	content := state.build(aux.store)
+	nextStates := state.next.eat(aux.topAppend(content), char)
 	return nextStates
 }
-func (state SubexOutputState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	content := state.build(store)
-	outputStacks := state.next.accepting(store, topAppend(outputStack, content))
+func (state SubexOutputState) accepting(aux auxiliaryState) []OutputStack {
+	content := state.build(aux.store)
+	outputStacks := state.next.accepting(aux.topAppend(content))
 	return outputStacks
 }
 
 // A final state, transitions to nothing but is accepting
 type SubexNoneState struct {}
-func (state SubexNoneState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
+func (state SubexNoneState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
 	return nil
 }
-func (state SubexNoneState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return []OutputStack{outputStack}
+func (state SubexNoneState) accepting(aux auxiliaryState) []OutputStack {
+	return []OutputStack{aux.outputStack}
 }
 
 // A dead end state, handy for making internals work nicer but technically redundant
 type SubexDeadState struct {}
-func (state SubexDeadState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
+func (state SubexDeadState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
 	return nil
 }
-func (state SubexDeadState) accepting (store Store, outputStack OutputStack) []OutputStack {
+func (state SubexDeadState) accepting (aux auxiliaryState) []OutputStack {
 	return nil
 }
 
-// Read in a specific Atom and output it
-type SubexCopyAtomState struct {
-	atom walk.Atom
-	next SubexState
-}
-func (state SubexCopyAtomState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	// TODO can I compare Atom values with == ?
-	if char == state.atom {
-		return []SubexBranch{{
-			state: state.next,
-			outputStack: topAppend(outputStack, []walk.Atom{char}),
-			store: store,
-		}}
-	}
-	return nil
-}
-func (state SubexCopyAtomState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return nil
-}
+// Read in an Atom and apply a map to generate an Atom to output
+// If the input isn't in the map transition to nothing
+// TODO
+// type SubexRangeState struct {
+// 	parts map[walk.Atom]walk.Atom
+// 	next SubexState
+// }
+// func (state SubexRangeState) eat(aux auxiliaryState, char walk.Atom) []SubexBranch {
+// 	out, exists := state.parts[char]
+// 	if !exists {
+// 		return nil
+// 	} else {
+// 		return []SubexBranch{{
+// 			state: state.next,
+// 			outputStack: topAppend(outputStack, []walk.Atom{out}),
+// 			store: store,
+// 		}}
+// 	}
+// }
+// func (state SubexRangeState) accepting(aux auxiliaryState) []OutputStack {
+// 	return nil
+// }
 
-// Read in a boolean atom and output it
-type SubexCopyBoolState struct {
-	next SubexState
-}
-func (state SubexCopyBoolState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	if char.Typ == walk.AtomBool {
-		return []SubexBranch{{
-			state: state.next,
-			outputStack: topAppend(outputStack, []walk.Atom{char}),
-			store: store,
-		}}
-	}
-	return nil
-}
-func (state SubexCopyBoolState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return nil
-}
 
-// Read in a number atom and output it
-type SubexCopyNumberState struct {
+type SubexArithmeticEndState struct {
 	next SubexState
+	calculate func(walk.ValueList) (walk.ValueList, error)
 }
-func (state SubexCopyNumberState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	if char.Typ == walk.AtomNumber {
-		return []SubexBranch{{
-			state: state.next,
-			outputStack: topAppend(outputStack, []walk.Atom{char}),
-			store: store,
-		}}
+func (state SubexArithmeticEndState) eat(aux auxiliaryState, char walk.Edible) []SubexBranch {
+	toCompute, aux := aux.popOutput()
+	values, isValues := toCompute.(walk.ValueList)
+	if !isValues {
+		panic("Tried to do arithmetic on non-values")
 	}
-	return nil
-}
-func (state SubexCopyNumberState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return nil
-}
-
-// Read in a string atom and output it
-type SubexCopyStringAtomState struct {
-	next SubexState
-}
-func (state SubexCopyStringAtomState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	if char.Typ == walk.AtomStringRune {
-		return []SubexBranch{{
-			state: state.next,
-			outputStack: topAppend(outputStack, []walk.Atom{char}),
-			store: store,
-		}}
+	result, err := state.calculate(values)
+	if err != nil {
+		return nil
 	}
-	return nil
+	return state.next.eat(aux.topAppend(result), char)
 }
-func (state SubexCopyStringAtomState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return nil
+func (state SubexArithmeticEndState) accepting(aux auxiliaryState) []OutputStack {
+	toCompute, aux := aux.popOutput()
+	values, isValues := toCompute.(walk.ValueList)
+	if !isValues {
+		panic("Tried to do arithmetic on non-values")
+	}
+	result, err := state.calculate(values)
+	if err != nil {
+		return nil
+	}
+	return state.next.accepting(aux.topAppend(result))
 }
 
-// Read in an atom and copy it out as long as it is not part of a string
-type SubexCopyNonStringNonTerminalAtomState struct {
+type SubexDiscardTerminalState struct {
+	terminal walk.Terminal
 	next SubexState
 }
-func (state SubexCopyNonStringNonTerminalAtomState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	if char.Typ == walk.AtomStringRune || char.Typ == walk.AtomStringTerminal || char.Typ == walk.AtomTerminal {
+func (state SubexDiscardTerminalState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	if edible != state.terminal {
 		return nil
 	}
 	return []SubexBranch{{
 		state: state.next,
-		outputStack: topAppend(outputStack, []walk.Atom{char}),
-		store: store,
+		aux: aux,
 	}}
 }
-func (state SubexCopyNonStringNonTerminalAtomState) accepting(store Store, outputStack OutputStack) []OutputStack {
+func (state SubexDiscardTerminalState) accepting(aux auxiliaryState) []OutputStack {
 	return nil
 }
 
-// Read in any Atom and output it
-type SubexCopyAnyState struct {
+type SubexConstructArrayState struct {
 	next SubexState
 }
-func (state SubexCopyAnyState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	return []SubexBranch{{
-		state: state.next,
-		outputStack: topAppend(outputStack, []walk.Atom{char}),
-		store: store,
-	}}
-}
-func (state SubexCopyAnyState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return nil
+func (state SubexConstructArrayState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	outputs, aux := aux.popOutput()
+	values, isValues := outputs.(walk.ValueList)
+	if !isValues {
+		panic("Tried to create an array from non-values")
+	}
+	array := walk.ArrayStructure(values)
+	return state.next.eat(aux.topAppend(walk.ValueList{array}), edible)
+}
+func (state SubexConstructArrayState) accepting(aux auxiliaryState) []OutputStack {
+	outputs, aux := aux.popOutput()
+	values, isValues := outputs.(walk.ValueList)
+	if !isValues {
+		panic("Tried to create an array from non-values")
+	}
+	array := walk.ArrayStructure(values)
+	return state.next.accepting(aux.topAppend(walk.ValueList{array}))
 }
 
-// Read in an Atom and apply a map to generate an Atom to output
-// If the input isn't in the map transition to nothing
-type SubexRangeState struct {
-	parts map[walk.Atom]walk.Atom
+type SubexConstructStringState struct {
 	next SubexState
 }
-func (state SubexRangeState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	out, exists := state.parts[char]
-	if !exists {
-		return nil
-	} else {
-		return []SubexBranch{{
-			state: state.next,
-			outputStack: topAppend(outputStack, []walk.Atom{out}),
-			store: store,
-		}}
+func (state SubexConstructStringState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	outputs, aux := aux.popOutput()
+	runes, isRunes := outputs.(walk.RuneList)
+	if !isRunes {
+		panic("Tried to create a string from non-runes")
 	}
-}
-func (state SubexRangeState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	return nil
+	s := walk.StringStructure(runes)
+	return state.next.eat(aux.topAppend(walk.ValueList{s}), edible)
+}
+func (state SubexConstructStringState) accepting(aux auxiliaryState) []OutputStack {
+	outputs, aux := aux.popOutput()
+	runes, isRunes := outputs.(walk.RuneList)
+	if !isRunes {
+		panic("Tried to create a string from non-runes")
+	}
+	s := walk.StringStructure(runes)
+	return state.next.accepting(aux.topAppend(walk.ValueList{s}))
 }
 
+type SubexIncrementNestState struct {
+	next SubexState
+}
+func (state SubexIncrementNestState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	return state.next.eat(aux.incNest(), edible)
+}
+func (state SubexIncrementNestState) accepting(aux auxiliaryState) []OutputStack {
+	return state.next.accepting(aux.incNest())
+}
+func (state SubexIncrementNestState) String() string {
+	return "IncrementNestState"
+}
 
-type SubexArithmeticEndState struct {
+type SubexDecrementNestState struct {
 	next SubexState
-	calculate func([]walk.Atom) ([]walk.Atom, error)
 }
-func (state SubexArithmeticEndState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
-	toCompute, newStack := outputStack.pop()
-	result, err := state.calculate(toCompute)
-	if err != nil {
-		return nil
-	}
-	return state.next.eat(store, topAppend(newStack, result), char)
+func (state SubexDecrementNestState) eat(aux auxiliaryState, edible walk.Edible) []SubexBranch {
+	return state.next.eat(aux.decNest(), edible)
 }
-func (state SubexArithmeticEndState) accepting(store Store, outputStack OutputStack) []OutputStack {
-	toCompute, newStack := outputStack.pop()
-	result, err := state.calculate(toCompute)
-	if err != nil {
-		return nil
-	}
-	return state.next.accepting(store, topAppend(newStack, result))
+func (state SubexDecrementNestState) accepting(aux auxiliaryState) []OutputStack {
+	return state.next.accepting(aux.decNest())
 }