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
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
package subex
import (
"os"
"fmt"
"bufio"
"main/walk"
"strings"
)
// A part of an insertion, either an Atom or a slot from which to load
// TODO rename this
type TransducerOutput interface {
// Given the current store, return the []Atom produced by the TransducerOutput
build(Store) []walk.Atom
}
// A TransducerOutput which is just an Atom literal
type TransducerReplacementAtom struct {
atom walk.Atom
}
func (replacement TransducerReplacementAtom) build(store Store) []walk.Atom {
return []walk.Atom{replacement.atom}
}
// TODO should be a single field called slot with a type of rune
// A TransducerOutput which is a slot that is loaded from
type TransducerReplacementLoad struct {
atom walk.Atom
}
func (replacement TransducerReplacementLoad) build(store Store) []walk.Atom {
return store[replacement.atom]
}
// Where slots are stored
// TODO should map from runes as only runes can be slots
type Store map[walk.Atom][]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
}
return newStore
}
// Return a copy of this store but with an additional slot set
func (store Store) withValue(key walk.Atom, value []walk.Atom) Store {
newStore := store.clone()
newStore[key] = value
return newStore
}
// Compile the SubexAST into a transducer SubexState that can be run
func CompileTransducer(transducerAst SubexAST) SubexState {
return transducerAst.compileWith(SubexNoneState{})
}
// One branch of subex execution
type SubexBranch struct {
// Content of slots in this branch
store Store
// State in this branch
state SubexState
// Output so far in this branch
output []walk.Atom
}
// Read a single character and return all the branches resulting from this branch consuming it
func (pair SubexBranch) eat(char walk.Atom) []SubexBranch {
states := pair.state.eat(pair.store, char)
for i := range states {
states[i].output = walk.ConcatData(pair.output, states[i].output)
}
return states
}
func (pair SubexBranch) accepting() [][]walk.Atom {
return pair.state.accepting(pair.store)
}
func equalStates(left SubexBranch, right SubexBranch) bool {
// Only care about if they are the same pointer
return left.state == right.state
}
// 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) (newStates []SubexBranch) {
outer: for _, state := range states {
for _, newState := range newStates {
if equalStates(state, newState) {
continue outer
}
}
newStates = append(newStates, state)
}
return newStates
}
// Run the subex transducer
func RunTransducer(transducer SubexState, input <-chan walk.Atom) (output []walk.Atom, err bool) {
states := []SubexBranch{{
state: transducer,
output: nil,
store: make(Store),
}}
for piece := range input {
var newStates []SubexBranch
for _, state := range states {
newStates = append(newStates, state.eat(piece)...)
}
states = pruneStates(newStates)
}
for _, state := range states {
outputEnds := state.accepting()
for _, outputEnd := range outputEnds {
return walk.ConcatData(state.output, outputEnd), false
}
}
return nil, true
}
func Main() {
if len(os.Args) != 2 {
panic("Expected: program [subex]")
}
stdin := bufio.NewReader(os.Stdin);
jsonStream := walk.Json(stdin);
var tokens []walk.WalkValue;
for token := range jsonStream {
tokens = append(tokens, token.Value);
}
program := os.Args[1]
ast := Parse(program)
transducer := CompileTransducer(ast)
pieces := make(chan walk.Atom)
go func(out chan<- walk.Atom, input []walk.WalkValue) {
for _, value := range input {
value.Pieces(out)
}
close(out)
}(pieces, tokens)
output, err := RunTransducer(transducer, pieces)
if !err {
dataIn := make(chan walk.Atom)
go func(out chan<- walk.Atom, in []walk.Atom) {
for _, atom := range in {
out<-atom
}
close(out)
}(dataIn, output)
valueOut := make(chan walk.WalkValue)
go func(out chan<- walk.WalkValue, in <-chan walk.Atom) {
for {
atom, hasAtom := <-in
if !hasAtom {
break
}
switch v := atom.(type) {
case walk.TerminalValue:
out<-v
continue
case walk.ValueNull:
out<-v
continue
case walk.ValueBool:
out<-v
continue
case walk.ValueNumber:
out<-v
continue
case rune:
panic("Error! Rune output by subex but not in a string")
case walk.EndString:
panic("Error! subex output an EndString before BeginString")
case walk.StartString:
default:
panic("Unknown atom type")
}
// Handle string start
var builder strings.Builder
loop: for {
atom, hasAtom := <-in
if !hasAtom {
panic("Missing EndString")
}
switch v := atom.(type) {
case walk.EndString:
break loop
case rune:
builder.WriteRune(v)
default:
panic("Invalid atom in string")
}
}
out<-walk.ValueString(builder.String())
}
close(out)
}(valueOut, dataIn)
for value := range valueOut {
fmt.Println(value)
}
} else {
fmt.Println("Error")
}
}
|
