<- Back to shtanton's homepage
aboutsummaryrefslogtreecommitdiff
path: root/subex/subexstate.go
blob: 12ace426894ba9b854e03d71114b0f3ab163e31a (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
package subex

import (
	"main/walk"
)

// A state of execution for the transducer
type SubexState interface {
	// Eat a Atom and transition to any number of new states
	eat(store Store, char walk.Atom) []SubexBranch
	// Find accepting states reachable through epsilon transitions and return their outputs
	accepting(store Store) [][]walk.Atom
}

// Try first, if it fails then try second
type SubexGroupState struct {
	first, second SubexState
}
func (state SubexGroupState) eat(store Store, char walk.Atom) []SubexBranch {
	otherStore := store.clone()
	return append(state.first.eat(store, char), state.second.eat(otherStore, char)...)
}
func (state SubexGroupState) accepting(store Store) [][]walk.Atom {
	return append(state.first.accepting(store), state.second.accepting(store)...)
}

// Run the match machine and store the output in a slot for later use
// Output nothing
type SubexStoreState struct {
	match SubexState
	slot rune
	next SubexState
	toStore []walk.Atom
}
func (state SubexStoreState) eat(store Store, char walk.Atom) (nextStates []SubexBranch) {
	acceptedOutputs := state.match.accepting(store)
	for _, acceptedOutput := range acceptedOutputs {
		nextStore := store.withValue(state.slot, walk.ConcatData(state.toStore, acceptedOutput))
		nextStates = append(nextStates, state.next.eat(nextStore.clone(), char)...)
	}
	nextMatchStates := state.match.eat(store.clone(), char)
	for _, matchState := range nextMatchStates {
		nextStates = append(nextStates, SubexBranch {
			state: SubexStoreState {
				match: matchState.state,
				slot: state.slot,
				next: state.next,
				toStore: walk.ConcatData(state.toStore, matchState.output),
			},
			output: nil,
			store: store.clone(),
		})
	}
	return nextStates
}
func (state SubexStoreState) accepting(store Store) (outputs [][]walk.Atom) {
	acceptedOutputs := state.match.accepting(store)
	for _, acceptedOutput := range acceptedOutputs {
		nextStore := store.withValue(state.slot, walk.ConcatData(state.toStore, acceptedOutput))
		outputs = append(outputs, state.next.accepting(nextStore)...)
	}
	return outputs
}

// Don't read in anything, just output the series of data and slots specified
type SubexOutputState struct {
	content []TransducerOutput
	next SubexState
}
// Given a store, return what is outputted by an epsilon transition from this state
func (state SubexOutputState) build(store Store) []walk.Atom {
	var result []walk.Atom
	for _, part := range state.content {
		result = append(result, part.build(store)...)
	}
	return result
}
func (state SubexOutputState) eat(store Store, char walk.Atom) []SubexBranch {
	content := state.build(store)
	nextStates := state.next.eat(store, char)
	for i := range nextStates {
		nextStates[i].output = walk.ConcatData(content, nextStates[i].output)
	}
	return nextStates
}
func (state SubexOutputState) accepting(store Store) [][]walk.Atom {
	content := state.build(store)
	outputs := state.next.accepting(store)
	for i := range outputs {
		outputs[i] = walk.ConcatData(content, outputs[i])
	}
	return outputs
}

// A final state, transitions to nothing but is accepting
type SubexNoneState struct {}
func (state SubexNoneState) eat(store Store, char walk.Atom) []SubexBranch {
	return nil
}
func (state SubexNoneState) accepting(store Store) [][]walk.Atom {
	return [][]walk.Atom{nil}
}

// Read in a specific Atom and output it
type SubexCopyAtomState struct {
	atom walk.Atom
	next SubexState
}
func (state SubexCopyAtomState) eat(store Store, char walk.Atom) []SubexBranch {
	// TODO can I compare Atom values with == ?
	if char == state.atom {
		return []SubexBranch{{
			state: state.next,
			output: []walk.Atom{char},
			store: store,
		}}
	}
	return nil
}
func (state SubexCopyAtomState) accepting(store Store) [][]walk.Atom {
	return nil
}

// Read in any Atom and output it
type SubexCopyAnyState struct {
	next SubexState
}
func (state SubexCopyAnyState) eat(store Store, char walk.Atom) []SubexBranch {
	return []SubexBranch{{
		state: state.next,
		output: []walk.Atom{char},
		store: store,
	}}
}
func (state SubexCopyAnyState) accepting(store Store) [][]walk.Atom {
	return nil
}

// Read in an Atom and apply a map to generate an Atom to output
// If the input isn't in the map transition to nothing
type SubexRangeState struct {
	parts map[walk.Atom]walk.Atom
	next SubexState
}
func (state SubexRangeState) eat(store Store, char walk.Atom) []SubexBranch {
	out, exists := state.parts[char]
	if !exists {
		return nil
	} else {
		return []SubexBranch{{
			state: state.next,
			output: []walk.Atom{out},
			store: store,
		}}
	}
}
func (state SubexRangeState) accepting(store Store) [][]walk.Atom {
	return nil
}