<- Back to shtanton's homepage
aboutsummaryrefslogtreecommitdiff
path: root/subex/main.go
diff options
context:
space:
mode:
Diffstat (limited to 'subex/main.go')
-rw-r--r--subex/main.go315
1 files changed, 205 insertions, 110 deletions
diff --git a/subex/main.go b/subex/main.go
index e2cec0b..32a5cf3 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
@@ -106,7 +150,7 @@ type auxiliaryState struct {
outputStack OutputStack
// How deeply nested the current execution is inside of the overall value
// i.e. starts at zero, is incremented to one when entering an array
- nesting int
+ nesting []bool
}
func (aux auxiliaryState) cloneStore() auxiliaryState {
@@ -114,67 +158,91 @@ 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)
- }
- return aux
+func (aux auxiliaryState) popOutputRunes() ([]rune, auxiliaryState) {
+ runes := aux.outputStack.head.(walk.OutputRuneList)
+ aux.outputStack = *aux.outputStack.tail
+ return runes, aux
}
-func (aux auxiliaryState) incNest() auxiliaryState {
- aux.nesting++
+func (aux auxiliaryState) topAppend(values []walk.Value) auxiliaryState {
+ aux.outputStack = topAppend(aux.outputStack, values)
return aux
}
-func (aux auxiliaryState) decNest() auxiliaryState {
- aux.nesting--
+func (aux auxiliaryState) topAppendRune(runes []rune) auxiliaryState {
+ aux.outputStack = topAppendRune(aux.outputStack, runes)
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 {
- // Only care about if they are the same pointer
- return left.state == right.state && left.aux.nesting == right.aux.nesting
+func equalStates(left SubexEatBranch, right SubexEatBranch) bool {
+ if left.state != right.state || len(left.aux.nesting) != len(right.aux.nesting) {
+ return false
+ }
+ for i, l := range left.aux.nesting {
+ if l != right.aux.nesting[i] {
+ return false
+ }
+ }
+ return true
}
// 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 +254,95 @@ 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, nesting []bool) []SubexEatBranch {
+ for _, state := range newStates {
+ switch s := state.state.(type) {
+ case SubexEpsilonState:
+ curStates = addStates(curStates, s.epsilon(state.aux), nesting)
+ 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 []bool) []SubexEatBranch {
+ newStates := make([]SubexEatBranch, 0, 2)
+
+ for _, state := range states {
+ if len(state.aux.nesting) > len(nesting) {
+ continue
}
- structure, isStructure := piece.(walk.Structure)
- if isStructure {
- iter := structure.Iter()
- newStates = processInput(newStates, iter, nesting + 1)
+ if (len(state.aux.nesting) == len(nesting) &&
+ (len(state.aux.nesting) == 0 || len(nesting) == 0 ||
+ state.aux.nesting[len(nesting) - 1] || nesting[len(nesting) - 1])) {
+ newStates = addStates(newStates, state.eat(input), nesting)
+ } else {
+ 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), append(nesting, true))
}
+ newStates = processInput(newStates, walk.StringEnd, append(nesting, true))
+ case walk.ArrayValue:
+ for _, el := range input {
+ newStates = processInput(newStates, walk.NumberValue(el.Index), append(nesting, false))
+ newStates = processInput(newStates, el.Value, append(nesting, true))
+ }
+ newStates = processInput(newStates, walk.ArrayEnd, append(nesting, true))
+ case walk.MapValue:
+ for _, el := range input {
+ newStates = processInput(newStates, walk.StringValue(el.Key), append(nesting, false))
+ newStates = processInput(newStates, el.Value, append(nesting, true))
+ }
+ newStates = processInput(newStates, walk.MapEnd, append(nesting, true))
}
- 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),
- nesting: 0,
+ store: Store{
+ values: make([][]walk.Value, transducer.storeSize.values),
+ runes: make([][]rune, transducer.storeSize.runes),
+ },
+ nesting: nil,
},
- }}
+ }}, nil)
+
+ for _, value := range input {
+ if len(states) == 0 {
+ break
+ }
- states = processInput(states, walk.NewValueIter(input), 0)
+ states = processInput(states, value, nil)
+ }
for _, state := range states {
+ if len(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