<- Back to shtanton's homepage
aboutsummaryrefslogtreecommitdiff
path: root/subex/main.go
blob: f8d909319413d047c2c1384d7105e6ace05699b1 (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
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
package subex

import (
	"main/walk"
)

type Transducer struct {
	storeSize    NextSlotIds
	initialState SubexState
}

// Where slots are stored
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 := 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.Value) Store {
	newStore := store.clone()
	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 {
	next NextSlotIds
	ids  map[rune]SlotId
}

func (m *SlotMap) getId(slot rune) int {
	id, exists := m.ids[slot]
	if exists {
		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.id = m.next.runes
	id.typ = RuneType
	m.next.runes++
	m.ids[slot] = id
	return id.id
}

// Compile the SubexAST into a transducer SubexState that can be run
func CompileTransducer(transducerAst SubexAST) Transducer {
	slotMap := SlotMap{
		next: NextSlotIds{
			values: 0,
			runes:  0,
		},
		ids: make(map[rune]SlotId),
	}
	initial := transducerAst.compileWith(&SubexNoneState{}, &slotMap, ValueType, ValueType)
	return Transducer{
		storeSize:    slotMap.next,
		initialState: initial,
	}
}

// An immutable stack for outputting to
type OutputStack struct {
	head walk.OutputList
	tail *OutputStack
}

func (stack OutputStack) pop() ([]walk.Value, OutputStack) {
	return stack.head.(walk.OutputValueList), *stack.tail
}
func (stack OutputStack) push(atoms []walk.Value) OutputStack {
	return OutputStack{
		head: walk.OutputValueList(atoms),
		tail: &stack,
	}
}
func (stack OutputStack) replace(atoms []walk.Value) OutputStack {
	return OutputStack{
		head: walk.OutputValueList(atoms),
		tail: stack.tail,
	}
}
func (stack OutputStack) peek() []walk.Value {
	return stack.head.(walk.OutputValueList)
}

func topAppend(outputStack OutputStack, values []walk.Value) OutputStack {
	head := outputStack.peek()
	head = append([]walk.Value{}, head...)
	head = append(head, values...)
	return outputStack.replace(head)
}

func topAppendRune(outputStack OutputStack, runes []rune) OutputStack {
	head := outputStack.head.(walk.OutputRuneList)
	head = append([]rune{}, head...)
	head = append(head, runes...)
	return OutputStack{
		head: head,
		tail: outputStack.tail,
	}
}

// Additional state that goes along with a subex state in an execution branch
type auxiliaryState struct {
	// Content of slots in this branch
	store Store
	// The output stack. At the end of the program, whatever is on top of this will be output
	// States may push or pop to the stack as they wish, creating sort of a call stack that allows states to capture the output of other states
	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
}

func (aux auxiliaryState) cloneStore() auxiliaryState {
	aux.store = aux.store.clone()
	return aux
}

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.Value) auxiliaryState {
	aux.outputStack = aux.outputStack.push(data)
	return aux
}

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) popOutputRunes() ([]rune, auxiliaryState) {
	runes := aux.outputStack.head.(walk.OutputRuneList)
	aux.outputStack = *aux.outputStack.tail
	return runes, aux
}

func (aux auxiliaryState) topAppend(values []walk.Value) auxiliaryState {
	aux.outputStack = topAppend(aux.outputStack, values)
	return aux
}

func (aux auxiliaryState) topAppendRune(runes []rune) auxiliaryState {
	aux.outputStack = topAppendRune(aux.outputStack, runes)
	return aux
}

func (aux auxiliaryState) incNest() auxiliaryState {
	aux.nesting++
	return aux
}

func (aux auxiliaryState) decNest() auxiliaryState {
	aux.nesting--
	return aux
}

type SubexBranch struct {
	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 SubexEatBranch) eat(edible walk.Edible) []SubexBranch {
	return pair.state.eat(pair.aux, edible)
}
func (pair SubexEatBranch) accepting() []OutputStack {
	return pair.state.accepting(pair.aux)
}

func equalStates(left SubexEatBranch, right SubexEatBranch) bool {
	// Only care about if they are the same pointer
	return left.state == right.state && left.aux.nesting == right.aux.nesting
}

// 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 []SubexEatBranch) []SubexEatBranch {
	uniqueStates := 0
outer:
	for _, state := range states {
		for i := 0; i < uniqueStates; i++ {
			if equalStates(state, states[i]) {
				continue outer
			}
		}
		states[uniqueStates] = state
		uniqueStates++
	}
	return states[:uniqueStates]
}

func addStates(curStates []SubexEatBranch, newStates []SubexBranch) []SubexEatBranch {
	for _, state := range newStates {
		switch s := state.state.(type) {
		case SubexEpsilonState:
			curStates = addStates(curStates, s.epsilon(state.aux))
		case SubexEatState:
			curStates = append(curStates, SubexEatBranch{
				state: s,
				aux:   state.aux,
			})
		}
	}
	return curStates
}

func processInput(states []SubexEatBranch, input walk.Edible, nesting int) []SubexEatBranch {
	newStates := make([]SubexEatBranch, 0, 2)

	for _, state := range states {
		if state.aux.nesting == nesting {
			newStates = addStates(newStates, state.eat(input))
		} else if state.aux.nesting < nesting {
			newStates = append(newStates, state)
		}
	}

	switch input := input.(type) {
	case walk.StringValue:
		for _, r := range input {
			newStates = processInput(newStates, walk.RuneEdible(r), nesting+1)
		}
		newStates = processInput(newStates, walk.StringEnd, nesting+1)
	case walk.ArrayValue:
		for _, el := range input {
			newStates = processInput(newStates, walk.NumberValue(el.Index), nesting+1)
			newStates = processInput(newStates, el.Value, nesting+1)
		}
		newStates = processInput(newStates, walk.ArrayEnd, nesting+1)
	case walk.MapValue:
		for _, el := range input {
			newStates = processInput(newStates, walk.StringValue(el.Key), nesting+1)
			newStates = processInput(newStates, el.Value, nesting+1)
		}
		newStates = processInput(newStates, walk.MapEnd, nesting+1)
	}

	newStates = pruneStates(newStates)

	return newStates
}

// Run the subex transducer
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.OutputValueList(nil),
				tail: nil,
			},
			store: Store{
				values: make([][]walk.Value, transducer.storeSize.values),
				runes:  make([][]rune, transducer.storeSize.runes),
			},
			nesting: 0,
		},
	}})

	for _, value := range input {
		if len(states) == 0 {
			break
		}

		states = processInput(states, value, 0)
	}

	for _, state := range states {
		if state.aux.nesting > 0 {
			continue
		}
		acceptingStacks := state.accepting()
		for _, stack := range acceptingStacks {
			return stack.head.(walk.OutputValueList), false
		}
	}
	return nil, true
}