From e84cf4ec822c32b4de5098353db2dab700b92bfa Mon Sep 17 00:00:00 2001 From: Charlie Stanton Date: Tue, 18 Apr 2023 16:35:47 +0100 Subject: Refactors store and sum states to use the new SubexParentState for states that run machines within themselves --- subex/subexstate.go | 157 ++++++++++++++++++++++++++++++++++------------------ 1 file changed, 104 insertions(+), 53 deletions(-) (limited to 'subex') diff --git a/subex/subexstate.go b/subex/subexstate.go index f027f78..62e9d1a 100644 --- a/subex/subexstate.go +++ b/subex/subexstate.go @@ -12,6 +12,20 @@ type SubexState interface { accepting(store Store) [][]walk.Atom } +type SubexParentState interface { + SubexState + // Get the child + child() SubexState + // The child outputted output, what should be passed as accumulator data into the next version of the parent state + nextAcc(output []walk.Atom) interface{} + // Given the final accumulated data, run the next state after the parent, immutably borrows store + feedNext(acc interface{}, store Store, char walk.Atom) []SubexBranch + // Given the final accumulated data, get the accepted outputs from the next state, immutably borrows store + acceptNext(acc interface{}, store Store) [][]walk.Atom + // Given the next child and next accumulator data, generate the next parent + nextParent(child SubexState, acc interface{}) SubexState +} + // Try first, if it fails then try second type SubexGroupState struct { first, second SubexState @@ -24,6 +38,37 @@ func (state SubexGroupState) accepting(store Store) [][]walk.Atom { return append(state.first.accepting(store), state.second.accepting(store)...) } +// Helper so states that are actually collections of states distinguished by a child state +// can pass eaten characters on to their children more easily +func feedChild(parent SubexParentState, store Store, char walk.Atom) (nextStates []SubexBranch) { + child := parent.child() + accepteds := child.accepting(store) + for _, accepted := range accepteds { + acc := parent.nextAcc(accepted) + nextStates = append(nextStates, parent.feedNext(acc, store, char)...) + } + nextChildren := child.eat(store, char) + for _, nextChild := range nextChildren { + acc := parent.nextAcc(nextChild.output) + nextStates = append(nextStates, SubexBranch{ + state: parent.nextParent(nextChild.state, acc), + output: nil, + store: nextChild.store, + }) + } + return nextStates +} + +func acceptChild(parent SubexParentState, store Store) (outputs [][]walk.Atom) { + child := parent.child() + accepteds := child.accepting(store) + for _, accepted := range accepteds { + acc := parent.nextAcc(accepted) + outputs = append(outputs, parent.acceptNext(acc, store)...) + } + return outputs +} + // Run the match machine and store the output in a slot for later use // Output nothing type SubexStoreState struct { @@ -32,34 +77,36 @@ type SubexStoreState struct { next SubexState toStore []walk.Atom } -func (state SubexStoreState) eat(store Store, char walk.Atom) (nextStates []SubexBranch) { - acceptedOutputs := state.match.accepting(store) - for _, acceptedOutput := range acceptedOutputs { - nextStore := store.withValue(state.slot, walk.ConcatData(state.toStore, acceptedOutput)) - nextStates = append(nextStates, state.next.eat(nextStore.clone(), char)...) - } - nextMatchStates := state.match.eat(store.clone(), char) - for _, matchState := range nextMatchStates { - nextStates = append(nextStates, SubexBranch { - state: &SubexStoreState { - match: matchState.state, - slot: state.slot, - next: state.next, - toStore: walk.ConcatData(state.toStore, matchState.output), - }, - output: nil, - store: matchState.store, - }) +func (state SubexStoreState) child() SubexState { + return state.match +} +func (state SubexStoreState) nextAcc(output []walk.Atom) interface{} { + return walk.ConcatData(state.toStore, output) +} +func (state SubexStoreState) feedNext(acc interface{}, store Store, char walk.Atom) []SubexBranch { + toStore := acc.([]walk.Atom) + nextStore := store.withValue(state.slot, toStore) + return state.next.eat(nextStore, char) +} +func (state SubexStoreState) acceptNext(acc interface{}, store Store) [][]walk.Atom { + toStore := acc.([]walk.Atom) + nextStore := store.withValue(state.slot, toStore) + return state.next.accepting(nextStore) +} +func (state SubexStoreState) nextParent(match SubexState, acc interface{}) SubexState { + toStore := acc.([]walk.Atom) + return &SubexStoreState { + match: match, + slot: state.slot, + next: state.next, + toStore: toStore, } - return nextStates +} +func (state SubexStoreState) eat(store Store, char walk.Atom) (nextStates []SubexBranch) { + return feedChild(state, store, char) } func (state SubexStoreState) accepting(store Store) (outputs [][]walk.Atom) { - acceptedOutputs := state.match.accepting(store) - for _, acceptedOutput := range acceptedOutputs { - nextStore := store.withValue(state.slot, walk.ConcatData(state.toStore, acceptedOutput)) - outputs = append(outputs, state.next.accepting(nextStore)...) - } - return outputs + return acceptChild(state, store) } // A part of an output literal, either an Atom or a slot from which to load @@ -216,37 +263,41 @@ type SubexSumState struct { next SubexState sum walk.ValueNumber } -func (state SubexSumState) eat(store Store, char walk.Atom) (nextStates []SubexBranch) { - acceptedOutputs := state.inputState.accepting(store) - for _, acceptedOutput := range acceptedOutputs { - nextNextStates := state.next.eat(store.clone(), char) - for i := range nextNextStates { - nextNextStates[i].output = walk.ConcatData([]walk.Atom{sumValues(append(acceptedOutput, state.sum))}, nextNextStates[i].output) - } - nextStates = append(nextStates, nextNextStates...) - } - nextInputStates := state.inputState.eat(store.clone(), char) - for _, inputState := range nextInputStates { - nextStates = append(nextStates, SubexBranch { - state: &SubexSumState { - inputState: inputState.state, - next: state.next, - sum: sumValues(append(inputState.output, state.sum)), - }, - output: nil, - store: inputState.store, - }) +func (state SubexSumState) child() SubexState { + return state.inputState +} +func (state SubexSumState) nextAcc(output []walk.Atom) interface{} { + return sumValues(append(output, state.sum)) +} +func (state SubexSumState) feedNext(acc interface{}, store Store, char walk.Atom) []SubexBranch { + total := acc.(walk.ValueNumber) + output := []walk.Atom{total} + nextStates := state.next.eat(store.clone(), char) + for i := range nextStates { + nextStates[i].output = walk.ConcatData(output, nextStates[i].output) } return nextStates } -func (state SubexSumState) accepting(store Store) (outputs [][]walk.Atom) { - acceptedOutputs := state.inputState.accepting(store) - for _, acceptedOutput := range acceptedOutputs { - nextOutputs := state.next.accepting(store.clone()) - for i := range nextOutputs { - nextOutputs[i] = walk.ConcatData([]walk.Atom{sumValues(append(acceptedOutput, state.sum))}, nextOutputs[i]) - } - outputs = append(outputs, nextOutputs...) +func (state SubexSumState) acceptNext(acc interface{}, store Store) [][]walk.Atom { + total := acc.(walk.ValueNumber) + output := []walk.Atom{total} + outputs := state.next.accepting(store.clone()) + for i := range outputs { + outputs[i] = walk.ConcatData(output, outputs[i]) } return outputs } +func (state SubexSumState) nextParent(child SubexState, acc interface{}) SubexState { + sum := acc.(walk.ValueNumber) + return &SubexSumState { + inputState: child, + next: state.next, + sum: sum, + } +} +func (state SubexSumState) eat(store Store, char walk.Atom) (nextStates []SubexBranch) { + return feedChild(state, store, char) +} +func (state SubexSumState) accepting(store Store) (outputs [][]walk.Atom) { + return acceptChild(state, store) +} -- cgit v1.2.3