From 8cf10efe3b5a1bcc70bc6e5590ee63fd5eb00c5b Mon Sep 17 00:00:00 2001 From: Charlie Stanton Date: Wed, 19 Jul 2023 11:57:59 +0100 Subject: Huge refactor to a more value based system, doing away with terminals. Also introduces unit testing --- subex/subexstate.go | 362 +++++++++++++++++++++++++++++----------------------- 1 file changed, 204 insertions(+), 158 deletions(-) (limited to 'subex/subexstate.go') 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()) } -- cgit v1.2.3