Completely remove the path space

The new design uses deeply nested values in the value space instead.

1 files changed, 195 insertions, 102 deletions

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