From fa750707cd3dd44bcbf59d9271d389c92b293621 Mon Sep 17 00:00:00 2001
From: Charlie Stanton <charlie@shtanton.xyz>
Date: Mon, 24 Apr 2023 19:28:48 +0100
Subject: Simplify the OutputStack, improves performance by simplifying from an
 interface to a single struct

---
 subex/main.go | 46 +++++++++++++++++++++-------------------------
 1 file changed, 21 insertions(+), 25 deletions(-)

diff --git a/subex/main.go b/subex/main.go
index c1718a4..5aedd09 100644
--- a/subex/main.go
+++ b/subex/main.go
@@ -27,39 +27,32 @@ func CompileTransducer(transducerAst SubexAST) SubexState {
 }
 
 // An immutable stack for outputting to
-type OutputStack interface {
-	pop() ([]walk.Atom, OutputStack)
-	push(atoms []walk.Atom) OutputStack
+type OutputStack struct {
+	head []walk.Atom
+	tail *OutputStack
 }
-
-type OutputStackNil struct {}
-func (stack OutputStackNil) pop() ([]walk.Atom, OutputStack) {
-	panic("Tried to pop from an empty OutputStack")
+func (stack OutputStack) pop() ([]walk.Atom, OutputStack) {
+	return stack.head, *stack.tail
 }
-func (stack OutputStackNil) push(atoms []walk.Atom) OutputStack {
-	return &OutputStackCons {
+func (stack OutputStack) push(atoms []walk.Atom) OutputStack {
+	return OutputStack {
 		head: atoms,
-		tail: stack,
+		tail: &stack,
 	}
 }
-
-type OutputStackCons struct {
-	head []walk.Atom
-	tail OutputStack
-}
-func (stack OutputStackCons) pop() ([]walk.Atom, OutputStack) {
-	return stack.head, stack.tail
-}
-func (stack OutputStackCons) push(atoms []walk.Atom) OutputStack {
-	return &OutputStackCons {
+func (stack OutputStack) replace(atoms []walk.Atom) OutputStack {
+	return OutputStack {
 		head: atoms,
-		tail: stack,
+		tail: stack.tail,
 	}
 }
+func (stack OutputStack) peek() []walk.Atom {
+	return stack.head
+}
 
 func topAppend(outputStack OutputStack, atoms []walk.Atom) OutputStack {
-	head, tail := outputStack.pop()
-	return tail.push(walk.ConcatData(head, atoms))
+	head := outputStack.peek()
+	return outputStack.replace(walk.ConcatData(head, atoms))
 }
 
 // One branch of subex execution
@@ -103,7 +96,10 @@ func pruneStates(states []SubexBranch) (newStates []SubexBranch) {
 func RunTransducer(transducer SubexState, input []walk.Atom) (output []walk.Atom, err bool) {
 	states := []SubexBranch{{
 		state: transducer,
-		outputStack: OutputStackNil{}.push(nil),
+		outputStack: OutputStack {
+			head: nil,
+			tail: nil,
+		},
 		store: make(Store),
 	}}
 	for _, piece := range input {
@@ -119,7 +115,7 @@ func RunTransducer(transducer SubexState, input []walk.Atom) (output []walk.Atom
 	for _, state := range states {
 		acceptingStacks := state.accepting()
 		for _, stack := range acceptingStacks {
-			output, _ := stack.pop()
+			output := stack.head
 			return output, false
 		}
 	}
-- 
cgit v1.2.3