package subex import ( "main/walk" ) type Transducer struct { storeSize int initialState SubexState } type StoreItem struct {} // Where slots are stored type Store [][]walk.Atom // Return a new store with all the data from this one func (store Store) clone() Store { newStore := make([][]walk.Atom, 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.Atom) 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) return Transducer { storeSize: slotMap.nextId, initialState: initial, } } // An immutable stack for outputting to type OutputStack struct { head []walk.Atom tail *OutputStack } func (stack OutputStack) pop() ([]walk.Atom, OutputStack) { return stack.head, *stack.tail } func (stack OutputStack) push(atoms []walk.Atom) OutputStack { return OutputStack { head: atoms, tail: &stack, } } func (stack OutputStack) replace(atoms []walk.Atom) OutputStack { return OutputStack { head: atoms, tail: stack.tail, } } func (stack OutputStack) peek() []walk.Atom { return stack.head } func topAppend(outputStack OutputStack, atoms []walk.Atom) OutputStack { head := outputStack.peek() return outputStack.replace(walk.ConcatData(head, atoms)) } // One branch of subex execution type SubexBranch struct { // Content of slots in this branch store Store // State in this branch state SubexState // 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 } // Read a single character and return all the branches resulting from this branch consuming it func (pair SubexBranch) eat(char walk.Atom) []SubexBranch { return pair.state.eat(pair.store, pair.outputStack, char) } func (pair SubexBranch) accepting() []OutputStack { return pair.state.accepting(pair.store, pair.outputStack) } func equalStates(left SubexBranch, right SubexBranch) bool { // Only care about if they are the same pointer return left.state == right.state } // 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] } // Run the subex transducer func RunTransducer(transducer Transducer, input []walk.Atom) (output []walk.Atom, err bool) { states := []SubexBranch{{ state: transducer.initialState, outputStack: OutputStack { head: nil, tail: nil, }, store: make([][]walk.Atom, transducer.storeSize), }} for _, piece := range input { var newStates []SubexBranch for _, state := range states { newStates = append(newStates, state.eat(piece)...) } states = pruneStates(newStates) if len(states) == 0 { return nil, true } } for _, state := range states { acceptingStacks := state.accepting() for _, stack := range acceptingStacks { output := stack.head return output, false } } return nil, true }