<- Back to shtanton's homepage
aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--main/command.go6
-rw-r--r--subex/main.go49
-rw-r--r--subex/parse.go18
-rw-r--r--subex/subexast.go113
-rw-r--r--subex/subexstate.go4
5 files changed, 120 insertions, 70 deletions
diff --git a/main/command.go b/main/command.go
index c7b1aa9..55c7cca 100644
--- a/main/command.go
+++ b/main/command.go
@@ -58,7 +58,7 @@ func (cmd DeletePathCommand) exec(state *ProgramState) {
state.path = nil
}
-func runSubex(state subex.SubexState, in []walk.Atom) (out []walk.Atom, error bool) {
+func runSubex(state subex.Transducer, in []walk.Atom) (out []walk.Atom, error bool) {
atomsOut, error := subex.RunTransducer(state, in)
if error {
return nil, true
@@ -67,7 +67,7 @@ func runSubex(state subex.SubexState, in []walk.Atom) (out []walk.Atom, error bo
}
type SubstituteValueCommand struct {
- subex subex.SubexState
+ subex subex.Transducer
next Command
}
func (cmd SubstituteValueCommand) exec(state *ProgramState) {
@@ -80,7 +80,7 @@ func (cmd SubstituteValueCommand) exec(state *ProgramState) {
}
type SubstitutePathCommand struct {
- subex subex.SubexState
+ subex subex.Transducer
next Command
}
func (cmd SubstitutePathCommand) exec(state *ProgramState) {
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]