Refines storing and loading to use ids generated when the subex is compiled instead of the runes

4 files changed, 117 insertions, 67 deletions

diff --git a/subex/main.go b/subex/main.go
index 5aedd09..635b1de 100644
--- a/subex/main.go
+++ b/subex/main.go
@@ -4,26 +4,53 @@ import (
 	"main/walk"
 )
 
+type Transducer struct {
+	storeSize int
+	initialState SubexState
+}
+
+type StoreItem struct {}
 // Where slots are stored
-type Store map[rune][]walk.Atom
+type Store [][]walk.Atom
 // Return a new store with all the data from this one
 func (store Store) clone() Store {
-	newStore := make(Store)
-	for key, val := range store {
-		newStore[key] = val
-	}
+	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 rune, value []walk.Atom) Store {
+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) SubexState {
-	return transducerAst.compileWith(&SubexNoneState{})
+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
@@ -93,14 +120,14 @@ func pruneStates(states []SubexBranch) (newStates []SubexBranch) {
 }
 
 // Run the subex transducer
-func RunTransducer(transducer SubexState, input []walk.Atom) (output []walk.Atom, err bool) {
+func RunTransducer(transducer Transducer, input []walk.Atom) (output []walk.Atom, err bool) {
 	states := []SubexBranch{{
-		state: transducer,
+		state: transducer.initialState,
 		outputStack: OutputStack {
 			head: nil,
 			tail: nil,
 		},
-		store: make(Store),
+		store: make([][]walk.Atom, transducer.storeSize),
 	}}
 	for _, piece := range input {
 		var newStates []SubexBranch
diff --git a/subex/parse.go b/subex/parse.go
index de53e2a..746217b 100644
--- a/subex/parse.go
+++ b/subex/parse.go
@@ -159,7 +159,7 @@ func parseRepeatRange(l RuneReader) (output []ConvexRange) {
 	return output
 }
 
-func parseReplacement(l RuneReader) (output []OutputContent) {
+func parseReplacement(l RuneReader) (output []OutputContentAST) {
 	// TODO escaping
 	loop: for {
 		r := l.Next()
@@ -173,16 +173,16 @@ func parseReplacement(l RuneReader) (output []OutputContent) {
 				if slot == eof {
 					panic("Missing slot character")
 				}
-				output = append(output, OutputLoad{slot: slot})
+				output = append(output, OutputLoadAST{slot: slot})
 			case '`':
 				literals := parseNonStringLiteral(l)
 				for _, literal := range literals {
-					output = append(output, OutputAtomLiteral {literal})
+					output = append(output, OutputAtomLiteralAST {literal})
 				}
 			case '"':
-				output = append(output, OutputAtomLiteral {walk.NewAtomStringTerminal()})
+				output = append(output, OutputAtomLiteralAST {walk.NewAtomStringTerminal()})
 			default:
-				output = append(output, OutputAtomLiteral{atom: walk.NewAtomStringRune(r)})
+				output = append(output, OutputAtomLiteralAST{atom: walk.NewAtomStringRune(r)})
 		}
 	}
 	return output
@@ -296,12 +296,12 @@ func parseSubex(l RuneReader, minPower int) SubexAST {
 		case '^':
 			replacement := parseReplacement(l)
 			replacement = append(
-				[]OutputContent{OutputAtomLiteral {walk.NewAtomStringTerminal()}},
+				[]OutputContentAST{OutputAtomLiteralAST {walk.NewAtomStringTerminal()}},
 				replacement...
 			)
 			replacement = append(
 				replacement,
-				OutputAtomLiteral {walk.NewAtomStringTerminal()},
+				OutputAtomLiteralAST {walk.NewAtomStringTerminal()},
 			)
 			lhs = SubexASTOutput {replacement}
 		case '.':
@@ -320,9 +320,9 @@ func parseSubex(l RuneReader, minPower int) SubexAST {
 			lhs = SubexASTCopyAtom {walk.NewAtomStringTerminal()}
 		case '~':
 			literals := parseNonStringLiteral(l)
-			var replacement []OutputContent
+			var replacement []OutputContentAST
 			for _, literal := range literals {
-				replacement = append(replacement, OutputAtomLiteral {literal})
+				replacement = append(replacement, OutputAtomLiteralAST {literal})
 			}
 			lhs = SubexASTOutput {replacement}
 		default:
diff --git a/subex/subexast.go b/subex/subexast.go
index 92c099a..f5b1178 100644
--- a/subex/subexast.go
+++ b/subex/subexast.go
@@ -7,15 +7,15 @@ import (
 
 // A node in the AST of a subex
 type SubexAST interface {
-	compileWith(next SubexState) SubexState
+	compileWith(next SubexState, slotMap *SlotMap) SubexState
 }
 
 // Process the first subex, then the second, splitting the input text in two
 type SubexASTConcat struct {
 	First, Second SubexAST
 }
-func (ast SubexASTConcat) compileWith(next SubexState) SubexState {
-	return ast.First.compileWith(ast.Second.compileWith(next))
+func (ast SubexASTConcat) compileWith(next SubexState, slotMap *SlotMap) SubexState {
+	return ast.First.compileWith(ast.Second.compileWith(next, slotMap), slotMap)
 }
 func (ast SubexASTConcat) String() string {
 	return fmt.Sprintf("(%v)(%v)", ast.First, ast.Second)
@@ -26,12 +26,13 @@ type SubexASTStore struct {
 	Match SubexAST
 	Slot rune
 }
-func (ast SubexASTStore) compileWith(next SubexState) SubexState {
+func (ast SubexASTStore) compileWith(next SubexState, slotMap *SlotMap) SubexState {
+	id := slotMap.getId(ast.Slot)
 	return &SubexCaptureBeginState {
 		next: ast.Match.compileWith(&SubexStoreEndState {
-			slot: ast.Slot,
+			slot: id,
 			next: next,
-		}),
+		}, slotMap),
 	}
 }
 func (ast SubexASTStore) String() string {
@@ -42,10 +43,10 @@ func (ast SubexASTStore) String() string {
 type SubexASTOr struct {
 	First, Second SubexAST
 }
-func (ast SubexASTOr) compileWith(next SubexState) SubexState {
+func (ast SubexASTOr) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexGroupState {
-		ast.First.compileWith(next),
-		ast.Second.compileWith(next),
+		ast.First.compileWith(next, slotMap),
+		ast.Second.compileWith(next, slotMap),
 	}
 }
 func (ast SubexASTOr) String() string {
@@ -75,19 +76,19 @@ func (cr ConvexRange) decrement() ConvexRange {
 		return ConvexRange{cr.Start - 1, cr.End - 1}
 	}
 }
-func (cr ConvexRange) compile(content SubexAST, next SubexState) SubexState {
+func (cr ConvexRange) compile(content SubexAST, next SubexState, slotMap *SlotMap) SubexState {
 	min, _ := cr.minmax()
 	if min != 0 {
-		return content.compileWith(cr.decrement().compile(content, next))
+		return content.compileWith(cr.decrement().compile(content, next, slotMap), slotMap)
 	}
 	if cr.Start == -1 {
 		state := &SubexGroupState {nil, next}
-		state.first = content.compileWith(state)
+		state.first = content.compileWith(state, slotMap)
 		return state
 	}
 	if cr.End == -1 {
 		state := &SubexGroupState {next, nil}
-		state.second = content.compileWith(state)
+		state.second = content.compileWith(state, slotMap)
 		return state
 	}
 
@@ -95,7 +96,7 @@ func (cr ConvexRange) compile(content SubexAST, next SubexState) SubexState {
 		state := next;
 		for i := 0; i < cr.Start; i += 1 {
 			state = &SubexGroupState {
-				content.compileWith(state),
+				content.compileWith(state, slotMap),
 				next,
 			}
 		}
@@ -105,7 +106,7 @@ func (cr ConvexRange) compile(content SubexAST, next SubexState) SubexState {
 		for i := 0; i < cr.End; i += 1 {
 			state = &SubexGroupState {
 				next,
-				content.compileWith(state),
+				content.compileWith(state, slotMap),
 			}
 		}
 		return state
@@ -118,10 +119,10 @@ type SubexASTRepeat struct {
 	Content SubexAST
 	Acceptable []ConvexRange
 }
-func (ast SubexASTRepeat) compileWith(next SubexState) SubexState {
+func (ast SubexASTRepeat) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	var state SubexState = &SubexDeadState{}
 	for _, convex := range ast.Acceptable {
-		state = &SubexGroupState {state, convex.compile(ast.Content, next)}
+		state = &SubexGroupState {state, convex.compile(ast.Content, next, slotMap)}
 	}
 	return state
 }
@@ -133,7 +134,7 @@ func (ast SubexASTRepeat) String() string {
 type SubexASTCopyAtom struct {
 	Atom walk.Atom
 }
-func (ast SubexASTCopyAtom) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyAtom) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCopyAtomState{
 		atom: ast.Atom,
 		next: next,
@@ -145,7 +146,7 @@ func (ast SubexASTCopyAtom) String() string {
 
 // Read in a single atom that must be a boolean and output it unchanged
 type SubexASTCopyBool struct {}
-func (ast SubexASTCopyBool) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyBool) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCopyBoolState {next}
 }
 func (ast SubexASTCopyBool) String() string {
@@ -154,7 +155,7 @@ func (ast SubexASTCopyBool) String() string {
 
 // Read in a single atom that must be a number and output it unchanged
 type SubexASTCopyNumber struct {}
-func (ast SubexASTCopyNumber) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyNumber) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCopyNumberState {next}
 }
 func (ast SubexASTCopyNumber) String() string {
@@ -163,7 +164,7 @@ func (ast SubexASTCopyNumber) String() string {
 
 // Read in a single atom that must be a string atom and output it unchanged
 type SubexASTCopyStringAtom struct {}
-func (ast SubexASTCopyStringAtom) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyStringAtom) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCopyStringAtomState {next}
 }
 func (ast SubexASTCopyStringAtom) String() string {
@@ -173,7 +174,7 @@ func (ast SubexASTCopyStringAtom) String() string {
 // Read in a full string value and copy it out unchanged
 // # is equivalent to "_{-0}"
 type SubexASTCopyString struct {}
-func (ast SubexASTCopyString) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyString) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	stringAtomState := &SubexCopyStringAtomState {
 		next: nil,
 	}
@@ -197,9 +198,9 @@ func (ast SubexASTCopyString) String() string {
 // Read in a value and copy it out unchanged
 // , is equivalent to `null`|?|%|#|[`{}[]`]
 type SubexASTCopyValue struct {}
-func (ast SubexASTCopyValue) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyValue) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexGroupState {
-		SubexASTCopyString{}.compileWith(next),
+		SubexASTCopyString{}.compileWith(next, slotMap),
 		&SubexCopyNonStringAtomState {next},
 	}
 }
@@ -209,20 +210,42 @@ func (ast SubexASTCopyValue) String() string {
 
 // Read in any single Atom and output it unchanged
 type SubexASTCopyAny struct {}
-func (ast SubexASTCopyAny) compileWith(next SubexState) SubexState {
+func (ast SubexASTCopyAny) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCopyAnyState{next}
 }
 func (ast SubexASTCopyAny) String() string {
 	return "."
 }
 
+type OutputContentAST interface {
+	compile(slotMap *SlotMap) OutputContent
+}
+
+type OutputLoadAST struct {
+	slot rune
+}
+func (ast OutputLoadAST) compile(slotMap *SlotMap) OutputContent {
+	return OutputLoad {slotMap.getId(ast.slot)}
+}
+
+type OutputAtomLiteralAST struct {
+	atom walk.Atom
+}
+func (ast OutputAtomLiteralAST) compile(slotMap *SlotMap) OutputContent {
+	return OutputAtomLiteral {ast.atom}
+}
+
 // Output a series of Atoms without reading anything from input
 type SubexASTOutput struct {
-	Replacement []OutputContent
+	Replacement []OutputContentAST
 }
-func (ast SubexASTOutput) compileWith(next SubexState) SubexState {
+func (ast SubexASTOutput) compileWith(next SubexState, slotMap *SlotMap) SubexState {
+	var content []OutputContent
+	for _, el := range ast.Replacement {
+		content = append(content, el.compile(slotMap))
+	}
 	return &SubexOutputState{
-		content: ast.Replacement,
+		content: content,
 		next: next,
 	}
 }
@@ -234,13 +257,13 @@ func (ast SubexASTOutput) String() string {
 type SubexASTJoin struct {
 	Content, Delimiter SubexAST
 }
-func (ast SubexASTJoin) compileWith(next SubexState) SubexState {
+func (ast SubexASTJoin) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	afterContentState := &SubexGroupState {
 		nil,
 		next,
 	}
-	manyContentsState := ast.Content.compileWith(afterContentState)
-	afterContentState.first = ast.Delimiter.compileWith(manyContentsState)
+	manyContentsState := ast.Content.compileWith(afterContentState, slotMap)
+	afterContentState.first = ast.Delimiter.compileWith(manyContentsState, slotMap)
 	return &SubexGroupState {
 		manyContentsState,
 		next,
@@ -255,7 +278,7 @@ func (ast SubexASTJoin) String() string {
 type SubexASTRange struct {
 	Parts map[walk.Atom]walk.Atom
 }
-func (ast SubexASTRange) compileWith(next SubexState) SubexState {
+func (ast SubexASTRange) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexRangeState {
 		parts: ast.Parts,
 		next: next,
@@ -270,12 +293,12 @@ func (ast SubexASTRange) String() string {
 type SubexASTSum struct {
 	Content SubexAST
 }
-func (ast SubexASTSum) compileWith(next SubexState) SubexState {
+func (ast SubexASTSum) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCaptureBeginState {
 		next: ast.Content.compileWith(&SubexArithmeticEndState {
 			next: next,
 			calculate: sumValues,
-		}),
+		}, slotMap),
 	}
 }
 func (ast SubexASTSum) String() string {
@@ -286,12 +309,12 @@ func (ast SubexASTSum) String() string {
 type SubexASTProduct struct {
 	Content SubexAST
 }
-func (ast SubexASTProduct) compileWith(next SubexState) SubexState {
+func (ast SubexASTProduct) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCaptureBeginState {
 		next: ast.Content.compileWith(&SubexArithmeticEndState {
 			next: next,
 			calculate: multiplyValues,
-		}),
+		}, slotMap),
 	}
 }
 func (ast SubexASTProduct) String() string {
@@ -303,12 +326,12 @@ func (ast SubexASTProduct) String() string {
 type SubexASTNegate struct {
 	Content SubexAST
 }
-func (ast SubexASTNegate) compileWith(next SubexState) SubexState {
+func (ast SubexASTNegate) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCaptureBeginState {
 		next: ast.Content.compileWith(&SubexArithmeticEndState {
 			next: next,
 			calculate: negateValues,
-		}),
+		}, slotMap),
 	}
 }
 func (ast SubexASTNegate) String() string {
@@ -321,12 +344,12 @@ func (ast SubexASTNegate) String() string {
 type SubexASTReciprocal struct {
 	Content SubexAST
 }
-func (ast SubexASTReciprocal) compileWith(next SubexState) SubexState {
+func (ast SubexASTReciprocal) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCaptureBeginState {
 		next: ast.Content.compileWith(&SubexArithmeticEndState {
 			next: next,
 			calculate: reciprocalValues,
-		}),
+		}, slotMap),
 	}
 }
 func (ast SubexASTReciprocal) String() string {
@@ -339,12 +362,12 @@ func (ast SubexASTReciprocal) String() string {
 type SubexASTNot struct {
 	Content SubexAST
 }
-func (ast SubexASTNot) compileWith(next SubexState) SubexState {
+func (ast SubexASTNot) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCaptureBeginState {
 		next: ast.Content.compileWith(&SubexArithmeticEndState {
 			next: next,
 			calculate: notValues,
-		}),
+		}, slotMap),
 	}
 }
 func (ast SubexASTNot) String() string {
@@ -353,7 +376,7 @@ func (ast SubexASTNot) String() string {
 
 // Does nothing
 type SubexASTEmpty struct {}
-func (ast SubexASTEmpty) compileWith(next SubexState) SubexState {
+func (ast SubexASTEmpty) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return next
 }
 func (ast SubexASTEmpty) String() string {
@@ -364,9 +387,9 @@ func (ast SubexASTEmpty) String() string {
 type SubexASTDiscard struct {
 	Content SubexAST
 }
-func (ast SubexASTDiscard) compileWith(next SubexState) SubexState {
+func (ast SubexASTDiscard) compileWith(next SubexState, slotMap *SlotMap) SubexState {
 	return &SubexCaptureBeginState {
-		next: ast.Content.compileWith(&SubexDiscardState {next}),
+		next: ast.Content.compileWith(&SubexDiscardState {next}, slotMap),
 	}
 }
 func (ast SubexASTDiscard) String() string {
diff --git a/subex/subexstate.go b/subex/subexstate.go
index 56063c0..4655ef9 100644
--- a/subex/subexstate.go
+++ b/subex/subexstate.go
@@ -52,7 +52,7 @@ func (state SubexDiscardState) accepting(store Store, outputStack OutputStack) [
 // Pop the top of the OutputStack which contains the stuff outputted since the start of the store
 // This outputted data gets stored in a slot
 type SubexStoreEndState struct {
-	slot rune
+	slot int
 	next SubexState
 }
 func (state SubexStoreEndState) eat(store Store, outputStack OutputStack, char walk.Atom) []SubexBranch {
@@ -80,7 +80,7 @@ func (replacement OutputAtomLiteral) build(store Store) []walk.Atom {
 
 // An OutputContent which is a slot that is loaded from
 type OutputLoad struct {
-	slot rune
+	slot int
 }
 func (replacement OutputLoad) build(store Store) []walk.Atom {
 	return store[replacement.slot]