From 080a24e894f125d4f1741cfdcba7cb722304d209 Mon Sep 17 00:00:00 2001 From: Charlie Stanton Date: Fri, 29 Mar 2024 09:49:26 +0000 Subject: Completely remove the path space The new design uses deeply nested values in the value space instead. --- subex/main.go | 297 ++++++++++++++++++++++++++++++++++++++-------------------- 1 file changed, 195 insertions(+), 102 deletions(-) (limited to 'subex/main.go') diff --git a/subex/main.go b/subex/main.go index e2cec0b..86a8d41 100644 --- a/subex/main.go +++ b/subex/main.go @@ -5,50 +5,96 @@ import ( ) type Transducer struct { - storeSize int + storeSize NextSlotIds initialState SubexState } -type StoreItem struct {} // Where slots are stored -type Store []walk.OutputList +type Store struct { + values [][]walk.Value + runes [][]rune +} + // Return a new store with all the data from this one func (store Store) clone() Store { - newStore := make([]walk.OutputList, len(store)) - copy(newStore, store) + newStore := Store{ + values: make([][]walk.Value, len(store.values)), + runes: make([][]rune, len(store.runes)), + } + copy(newStore.values, store.values) + copy(newStore.runes, store.runes) return newStore } + // Return a copy of this store but with an additional slot set -func (store Store) withValue(key int, value walk.OutputList) Store { +func (store Store) withValue(key int, value []walk.Value) Store { newStore := store.clone() - newStore[key] = value + newStore.values[key] = value return newStore } +func (store Store) withRunes(key int, runes []rune) Store { + newStore := store.clone() + newStore.runes[key] = runes + return newStore +} + +type SlotId struct { + id int + typ Type +} + +type NextSlotIds struct { + values int + runes int +} + type SlotMap struct { - nextId int - ids map[rune]int + next NextSlotIds + ids map[rune]SlotId } + func (m *SlotMap) getId(slot rune) int { id, exists := m.ids[slot] if exists { - return id + if id.typ != ValueType { + panic("Slot with wrong type used") + } + return id.id + } + id.id = m.next.values + id.typ = ValueType + m.next.values++ + m.ids[slot] = id + return id.id +} +func (m *SlotMap) getRuneId(slot rune) int { + id, exists := m.ids[slot] + if exists { + if id.typ != RuneType { + panic("Slot with wrong type used") + } + return id.id } - id = m.nextId - m.nextId++ + id.id = m.next.runes + id.typ = RuneType + m.next.runes++ m.ids[slot] = id - return id + return id.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), + slotMap := SlotMap{ + next: NextSlotIds{ + values: 0, + runes: 0, + }, + ids: make(map[rune]SlotId), } - initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap, false) - return Transducer { - storeSize: slotMap.nextId, + initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap, ValueType, ValueType) + return Transducer{ + storeSize: slotMap.next, initialState: initial, } } @@ -58,46 +104,44 @@ type OutputStack struct { head walk.OutputList tail *OutputStack } -func (stack OutputStack) pop() (walk.OutputList, OutputStack) { - return stack.head, *stack.tail + +func (stack OutputStack) pop() ([]walk.Value, OutputStack) { + return stack.head.(walk.OutputValueList), *stack.tail } -func (stack OutputStack) push(atoms walk.OutputList) OutputStack { - return OutputStack { - head: atoms, +func (stack OutputStack) push(atoms []walk.Value) OutputStack { + return OutputStack{ + head: walk.OutputValueList(atoms), tail: &stack, } } -func (stack OutputStack) replace(atoms walk.OutputList) OutputStack { - return OutputStack { - head: atoms, +func (stack OutputStack) replace(atoms []walk.Value) OutputStack { + return OutputStack{ + head: walk.OutputValueList(atoms), tail: stack.tail, } } -func (stack OutputStack) peek() walk.OutputList { - return stack.head +func (stack OutputStack) peek() []walk.Value { + return stack.head.(walk.OutputValueList) } func topAppend(outputStack OutputStack, values []walk.Value) OutputStack { - head, isValues := outputStack.peek().(walk.ValueList) - if !isValues { - panic("Tried to append a value to an output of non-values") - } - head = append(walk.ValueList{}, head...) + head := outputStack.peek() + head = append([]walk.Value{}, head...) head = append(head, values...) return outputStack.replace(head) } -func topAppendRunes(outputStack OutputStack, runes walk.RuneList) OutputStack { - head, isRunes := outputStack.peek().(walk.RuneList) - if !isRunes { - panic("Tried to append runes to a non-rune list") - } - head = append(walk.RuneList{}, head...) +func topAppendRune(outputStack OutputStack, runes []rune) OutputStack { + head := outputStack.head.(walk.OutputRuneList) + head = append([]rune{}, head...) head = append(head, runes...) - return outputStack.replace(head) + return OutputStack{ + head: head, + tail: outputStack.tail, + } } -// Addition state that goes along with a subex state in an execution branch +// Additional state that goes along with a subex state in an execution branch type auxiliaryState struct { // Content of slots in this branch store Store @@ -114,29 +158,49 @@ func (aux auxiliaryState) cloneStore() auxiliaryState { return aux } -func (aux auxiliaryState) withValue(slot int, value walk.OutputList) auxiliaryState { +func (aux auxiliaryState) withValue(slot int, value []walk.Value) auxiliaryState { aux.store = aux.store.withValue(slot, value) return aux } -func (aux auxiliaryState) pushOutput(data walk.OutputList) auxiliaryState { +func (aux auxiliaryState) pushOutput(data []walk.Value) auxiliaryState { aux.outputStack = aux.outputStack.push(data) return aux } -func (aux auxiliaryState) popOutput() (walk.OutputList, auxiliaryState) { +func (aux auxiliaryState) pushOutputRunes(runes []rune) auxiliaryState { + tail := aux.outputStack + aux.outputStack = OutputStack{ + head: walk.OutputRuneList(runes), + tail: &tail, + } + return aux +} + +func (aux auxiliaryState) popDiscardOutput() auxiliaryState { + aux.outputStack = *aux.outputStack.tail + return aux +} + +func (aux auxiliaryState) popOutput() ([]walk.Value, auxiliaryState) { data, output := aux.outputStack.pop() aux.outputStack = output return data, aux } -func (aux auxiliaryState) topAppend(values walk.OutputList) auxiliaryState { - switch output := values.(type) { - case walk.ValueList: - aux.outputStack = topAppend(aux.outputStack, output) - case walk.RuneList: - aux.outputStack = topAppendRunes(aux.outputStack, output) - } +func (aux auxiliaryState) popOutputRunes() ([]rune, auxiliaryState) { + runes := aux.outputStack.head.(walk.OutputRuneList) + aux.outputStack = *aux.outputStack.tail + return runes, aux +} + +func (aux auxiliaryState) topAppend(values []walk.Value) auxiliaryState { + aux.outputStack = topAppend(aux.outputStack, values) + return aux +} + +func (aux auxiliaryState) topAppendRune(runes []rune) auxiliaryState { + aux.outputStack = topAppendRune(aux.outputStack, runes) return aux } @@ -150,31 +214,38 @@ func (aux auxiliaryState) decNest() auxiliaryState { return aux } -// One branch of subex execution type SubexBranch struct { - // State in this branch state SubexState + aux auxiliaryState +} + +// One branch of subex execution +type SubexEatBranch struct { + // State in this branch + state SubexEatState // Axiliary state aux auxiliaryState } + // Read a single character and return all the branches resulting from this branch consuming it -func (pair SubexBranch) eat(char walk.Edible) []SubexBranch { - return pair.state.eat(pair.aux, char) +func (pair SubexEatBranch) eat(edible walk.Edible) []SubexBranch { + return pair.state.eat(pair.aux, edible) } -func (pair SubexBranch) accepting() []OutputStack { +func (pair SubexEatBranch) accepting() []OutputStack { return pair.state.accepting(pair.aux) } -func equalStates(left SubexBranch, right SubexBranch) bool { +func equalStates(left SubexEatBranch, right SubexEatBranch) bool { // Only care about if they are the same pointer return left.state == right.state && left.aux.nesting == right.aux.nesting } // 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 { +func pruneStates(states []SubexEatBranch) []SubexEatBranch { uniqueStates := 0 - outer: for _, state := range states { +outer: + for _, state := range states { for i := 0; i < uniqueStates; i++ { if equalStates(state, states[i]) { continue outer @@ -186,68 +257,90 @@ func pruneStates(states []SubexBranch) []SubexBranch { return states[:uniqueStates] } -func processInput(states []SubexBranch, input walk.StructureIter, nesting int) []SubexBranch { - if len(states) == 0 { - return states - } - var tmp []SubexBranch - newStates := make([]SubexBranch, 0, 2) - for { - piece := input.Next() - if piece == nil { - break +func addStates(curStates []SubexEatBranch, newStates []SubexBranch) []SubexEatBranch { + for _, state := range newStates { + switch s := state.state.(type) { + case SubexEpsilonState: + curStates = addStates(curStates, s.epsilon(state.aux)) + case SubexEatState: + curStates = append(curStates, SubexEatBranch{ + state: s, + aux: state.aux, + }) } + } + return curStates +} - // TODO: break if there are no states at this nesting level left - // TODO: What to do if there are remaining nested states after all pieces have been used? - for _, state := range states { - if state.aux.nesting == nesting { - newStates = append(newStates, state.eat(piece)...) - } else { - newStates = append(newStates, state) - } - } +func processInput(states []SubexEatBranch, input walk.Edible, nesting int) []SubexEatBranch { + newStates := make([]SubexEatBranch, 0, 2) - structure, isStructure := piece.(walk.Structure) - if isStructure { - iter := structure.Iter() - newStates = processInput(newStates, iter, nesting + 1) + for _, state := range states { + // TODO: What if nesting is changed by an epsilon state? + if state.aux.nesting == nesting { + newStates = addStates(newStates, state.eat(input)) + } else if state.aux.nesting < nesting { + newStates = append(newStates, state) } + } - tmp = states - states = pruneStates(newStates) - newStates = tmp[:0] - if len(states) == 0 { - return states + switch input := input.(type) { + case walk.StringValue: + for _, r := range input { + newStates = processInput(newStates, walk.RuneEdible(r), nesting+1) } + newStates = processInput(newStates, walk.StringEnd, nesting+1) + case walk.ArrayValue: + for _, el := range input { + newStates = processInput(newStates, walk.NumberValue(el.Index), nesting+1) + newStates = processInput(newStates, el.Value, nesting+1) + } + newStates = processInput(newStates, walk.ArrayEnd, nesting+1) + case walk.MapValue: + for _, el := range input { + newStates = processInput(newStates, walk.StringValue(el.Key), nesting+1) + newStates = processInput(newStates, el.Value, nesting+1) + } + newStates = processInput(newStates, walk.MapEnd, nesting+1) } - return states + + newStates = pruneStates(newStates) + + return newStates } // Run the subex transducer -func RunTransducer(transducer Transducer, input walk.ValueList) (output []walk.Value, err bool) { - states := []SubexBranch{{ +func RunTransducer(transducer Transducer, input []walk.Value) (output []walk.Value, err bool) { + states := addStates(nil, []SubexBranch{{ state: transducer.initialState, - aux: auxiliaryState { - outputStack: OutputStack { - head: walk.ValueList{}, + aux: auxiliaryState{ + outputStack: OutputStack{ + head: walk.OutputValueList(nil), tail: nil, }, - store: make([]walk.OutputList, transducer.storeSize), + store: Store{ + values: make([][]walk.Value, transducer.storeSize.values), + runes: make([][]rune, transducer.storeSize.runes), + }, nesting: 0, }, - }} + }}) + + for _, value := range input { + if len(states) == 0 { + break + } - states = processInput(states, walk.NewValueIter(input), 0) + states = processInput(states, value, 0) + } for _, state := range states { + if state.aux.nesting > 0 { + continue + } acceptingStacks := state.accepting() for _, stack := range acceptingStacks { - output, isValues := stack.head.(walk.ValueList) - if !isValues { - panic("Tried to output a non-values list") - } - return output, false + return stack.head.(walk.OutputValueList), false } } return nil, true -- cgit v1.2.3