package subex import ( "main/walk" ) // A state of execution for the transducer type SubexState interface { // Eat a Atom and transition to any number of new states eat(store Store, char walk.Atom) []SubexBranch // Find accepting states reachable through epsilon transitions and return their outputs 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 } func (state SubexGroupState) eat(store Store, char walk.Atom) []SubexBranch { otherStore := store.clone() return append(state.first.eat(store, char), state.second.eat(otherStore, char)...) } 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 { match SubexState slot rune next SubexState toStore []walk.Atom } 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, } } 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) { return acceptChild(state, store) } // 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 } // An OutputContent which is just an Atom literal type OutputAtomLiteral struct { atom walk.Atom } func (replacement OutputAtomLiteral) build(store Store) []walk.Atom { return []walk.Atom{replacement.atom} } // An OutputContent which is a slot that is loaded from type OutputLoad struct { slot rune } func (replacement OutputLoad) build(store Store) []walk.Atom { return store[replacement.slot] } // Don't read in anything, just output the series of data and slots specified type SubexOutputState struct { content []OutputContent 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 for _, part := range state.content { result = append(result, part.build(store)...) } return result } func (state SubexOutputState) eat(store Store, char walk.Atom) []SubexBranch { content := state.build(store) nextStates := state.next.eat(store, char) for i := range nextStates { nextStates[i].output = walk.ConcatData(content, nextStates[i].output) } return nextStates } func (state SubexOutputState) accepting(store Store) [][]walk.Atom { content := state.build(store) outputs := state.next.accepting(store) for i := range outputs { outputs[i] = walk.ConcatData(content, outputs[i]) } return outputs } // A final state, transitions to nothing but is accepting type SubexNoneState struct {} func (state SubexNoneState) eat(store Store, char walk.Atom) []SubexBranch { return nil } func (state SubexNoneState) accepting(store Store) [][]walk.Atom { return [][]walk.Atom{nil} } // A dead end state, handy for making internals work nicer but technically redundant type SubexDeadState struct {} func (state SubexDeadState) eat(store Store, char walk.Atom) []SubexBranch { return nil } func (state SubexDeadState) accepting (store Store) [][]walk.Atom { return nil } // Read in a specific Atom and output it type SubexCopyAtomState struct { atom walk.Atom next SubexState } func (state SubexCopyAtomState) eat(store Store, char walk.Atom) []SubexBranch { // TODO can I compare Atom values with == ? if char == state.atom { return []SubexBranch{{ state: state.next, output: []walk.Atom{char}, store: store, }} } return nil } func (state SubexCopyAtomState) accepting(store Store) [][]walk.Atom { return nil } // Read in any Atom and output it type SubexCopyAnyState struct { next SubexState } func (state SubexCopyAnyState) eat(store Store, char walk.Atom) []SubexBranch { return []SubexBranch{{ state: state.next, output: []walk.Atom{char}, store: store, }} } func (state SubexCopyAnyState) accepting(store Store) [][]walk.Atom { 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 type SubexRangeState struct { parts map[walk.Atom]walk.Atom next SubexState } func (state SubexRangeState) eat(store Store, char walk.Atom) []SubexBranch { out, exists := state.parts[char] if !exists { return nil } else { return []SubexBranch{{ state: state.next, output: []walk.Atom{out}, store: store, }} } } func (state SubexRangeState) accepting(store Store) [][]walk.Atom { return nil } func sumValues(values []walk.Atom) walk.ValueNumber { var sum float64 = 0 for _, value := range values { switch v := value.(type) { case walk.ValueBool: if (bool(v)) { sum += 1 } case walk.ValueNumber: sum += float64(v) case rune: if '0' <= v && v <= '9' { sum += float64(v - '0') } default: } } return walk.ValueNumber(sum) } // Run the inputState machine and sum any values output, output the sum // Cast non numbers into numbers, ignore anything uncastable type SubexSumState struct { inputState SubexState next SubexState sum walk.ValueNumber } 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) 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) }