|
996
|
1 /*
|
|
|
2 * gearlance bfjoust interpreter; based on cranklance, itself based on
|
|
|
3 * chainlance.
|
|
|
4 *
|
|
|
5 * Copyright 2011 Heikki Kallasjoki. All rights reserved.
|
|
|
6 *
|
|
|
7 * Redistribution and use in source and binary forms, with or without
|
|
|
8 * modification, are permitted provided that the following conditions
|
|
|
9 * are met:
|
|
|
10 *
|
|
|
11 * 1. Redistributions of source code must retain the above copyright
|
|
|
12 * notice, this list of conditions and the following disclaimer.
|
|
|
13 *
|
|
|
14 * 2. Redistributions in binary form must reproduce the above
|
|
|
15 * copyright notice, this list of conditions and the following
|
|
|
16 * disclaimer in the documentation and/or other materials provided
|
|
|
17 * with the distribution.
|
|
|
18 *
|
|
|
19 * THIS SOFTWARE IS PROVIDED BY HEIKKI KALLASJOKI ``AS IS'' AND ANY
|
|
|
20 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
|
|
|
21 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
|
|
|
22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL HEIKKI KALLASJOKI OR
|
|
|
23 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
|
|
|
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
|
|
|
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
|
|
|
26 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
|
|
|
27 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
|
|
|
28 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
|
|
|
29 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
|
|
|
30 * SUCH DAMAGE.
|
|
|
31 *
|
|
|
32 * The views and conclusions contained in the software and
|
|
|
33 * documentation are those of the authors and should not be
|
|
|
34 * interpreted as representing official policies, either expressed or
|
|
|
35 * implied, of Heikki Kallasjoki.
|
|
|
36 */
|
|
|
37
|
|
|
38 #include <fcntl.h>
|
|
|
39 #include <setjmp.h>
|
|
|
40 #include <stdarg.h>
|
|
|
41 #include <stdio.h>
|
|
|
42 #include <stdlib.h>
|
|
|
43 #include <string.h>
|
|
|
44 #include <sys/types.h>
|
|
|
45 #include <sys/stat.h>
|
|
|
46 #include <unistd.h>
|
|
|
47
|
|
|
48 #define MAXCYCLES 100000
|
|
|
49 #define MAXNEST 256
|
|
|
50
|
|
|
51 #define MINTAPE 10
|
|
|
52 #define MAXTAPE 30
|
|
|
53
|
|
|
54 /* #define TRACE 1 */
|
|
|
55
|
|
|
56 static int scores[2][MAXTAPE+1];
|
|
|
57
|
|
|
58 /* types */
|
|
|
59
|
|
|
60 enum optype
|
|
|
61 {
|
|
|
62 OP_INC, OP_DEC,
|
|
|
63 OP_LEFT, OP_RIGHT,
|
|
|
64 OP_WAIT,
|
|
|
65 OP_LOOP1, OP_LOOP2,
|
|
|
66 OP_REP1, OP_REP2,
|
|
|
67 OP_INNER1, OP_INNER2
|
|
|
68 };
|
|
|
69
|
|
|
70 struct op
|
|
|
71 {
|
|
|
72 enum optype type;
|
|
|
73 int match; /* offset of matching delimiter for [({ })] pairs */
|
|
|
74 int inner; /* extra links between matched ( .. { and } .. ) */
|
|
|
75 int count; /* static repetition count for the ({}) instructions */
|
|
|
76 };
|
|
|
77
|
|
|
78 struct oplist
|
|
|
79 {
|
|
|
80 int len, size;
|
|
|
81 struct op *ops;
|
|
|
82 };
|
|
|
83
|
|
|
84 /* generic helpers */
|
|
|
85
|
|
|
86 static void die(const char *fmt, ...);
|
|
|
87 static void fail(const char *fmt, ...);
|
|
|
88
|
|
|
89 static char fail_msg[256];
|
|
|
90 static jmp_buf fail_buf;
|
|
|
91
|
|
|
92 static void *smalloc(size_t size);
|
|
|
93 static void *srealloc(void *ptr, size_t size);
|
|
|
94
|
|
|
95 static int sopen(const char *fname);
|
|
|
96
|
|
|
97 /* oplist handling */
|
|
|
98
|
|
|
99 static struct oplist *opl_new(void);
|
|
|
100 static void opl_free(struct oplist *o);
|
|
|
101 static void opl_append(struct oplist *o, enum optype type);
|
|
|
102 static void opl_del(struct oplist *o, int start, int end);
|
|
|
103
|
|
|
104 /* parsing and preprocessing */
|
|
|
105
|
|
|
106 static struct oplist *parse(int fd);
|
|
|
107
|
|
|
108 /* actual interpretation */
|
|
|
109
|
|
|
110 static void run(struct oplist *opsA, struct oplist *opsB);
|
|
|
111
|
|
|
112 /* main application */
|
|
|
113
|
|
|
114 int main(int argc, char *argv[])
|
|
|
115 {
|
|
|
116 /* check args */
|
|
|
117
|
|
|
118 if (argc < 3)
|
|
|
119 {
|
|
|
120 fprintf(stderr, "usage: %s prog1.bfjoust prog2.bfjoust [score pid]\n", argv[0]);
|
|
|
121 return 1;
|
|
|
122 }
|
|
|
123
|
|
|
124 printf("%s vs %s\n", argv[1], argv[2]);
|
|
|
125
|
|
|
126 /* parse competitors */
|
|
|
127
|
|
|
128 int fdA = sopen(argv[1]), fdB = sopen(argv[2]);
|
|
|
129
|
|
|
130 if (setjmp(fail_buf))
|
|
|
131 {
|
|
|
132 printf("parse error: %s\n\n", fail_msg);
|
|
|
133 return 1;
|
|
|
134 }
|
|
|
135
|
|
|
136 struct oplist *opsA = parse(fdA), *opsB = parse(fdB);
|
|
|
137
|
|
|
138 /* for debuggin purposes, dump out the parse */
|
|
|
139
|
|
|
140 #if 0
|
|
|
141 unsigned char opchars[] = {
|
|
|
142 [OP_INC] = '+', [OP_DEC] = '-', [OP_LEFT] = '<', [OP_RIGHT] = '>',
|
|
|
143 [OP_WAIT] = '.', [OP_LOOP1] = '[', [OP_LOOP2] = ']',
|
|
|
144 [OP_REP1] = '(', [OP_REP2] = ')', [OP_INNER1] = '{', [OP_INNER2] = '}'
|
|
|
145 };
|
|
|
146 for (int at = 0; at < opsA->len; at++)
|
|
|
147 {
|
|
|
148 struct op *op = &opsA->ops[at];
|
|
|
149 printf("%3d: %c (%-2d {%-2d *%-2d\n", at, opchars[op->type], op->match, op->inner, op->count);
|
|
|
150 }
|
|
|
151 return 0;
|
|
|
152 #endif
|
|
|
153
|
|
|
154 /* run them */
|
|
|
155
|
|
|
156 run(opsA, opsB);
|
|
|
157
|
|
|
158 /* summarize results */
|
|
|
159
|
|
|
160 int score = 0;
|
|
|
161
|
|
|
162 for (int pol = 0; pol < 2; pol++)
|
|
|
163 {
|
|
|
164 for (int tlen = MINTAPE; tlen <= MAXTAPE; tlen++)
|
|
|
165 {
|
|
|
166 putchar(scores[pol][tlen] ? (scores[pol][tlen] > 0 ? '<' : '>') : 'X');
|
|
|
167 score += scores[pol][tlen];
|
|
|
168 }
|
|
|
169 putchar(' ');
|
|
|
170 }
|
|
|
171
|
|
|
172 /* score is also output to a pid */
|
|
|
173 if (argc >= 4) {
|
|
|
174 write(atoi(argv[3]), &score, sizeof(int));
|
|
|
175 }
|
|
|
176
|
|
|
177 printf("%d\n", score);
|
|
|
178
|
|
|
179 if (score < 0) {
|
|
|
180 printf("%s wins.\n\n", argv[1]);
|
|
|
181 } else if (score > 0) {
|
|
|
182 printf("%s wins.\n\n", argv[2]);
|
|
|
183 } else {
|
|
|
184 printf("Tie.\n\n");
|
|
|
185 }
|
|
|
186
|
|
|
187 opl_free(opsA);
|
|
|
188 opl_free(opsB);
|
|
|
189
|
|
|
190 return 0;
|
|
|
191 }
|
|
|
192
|
|
|
193 /* actual interpretation, impl */
|
|
|
194
|
|
|
195 static unsigned char tape[MAXTAPE];
|
|
|
196
|
|
|
197 static void run(struct oplist *opsA, struct oplist *opsB)
|
|
|
198 {
|
|
|
199 struct op *oplA = opsA->ops, *oplB = opsB->ops;
|
|
|
200
|
|
|
201 /* convert opcode types into pointers for both progs */
|
|
|
202
|
|
|
203 void **opcA = smalloc((opsA->len+1) * sizeof *opcA);
|
|
|
204 void **opcB = smalloc((opsB->len+1) * sizeof *opcB);
|
|
|
205
|
|
|
206 for (int at = 0; at < opsA->len; at++)
|
|
|
207 {
|
|
|
208 struct op *op = &oplA[at];
|
|
|
209 void **opc = &opcA[at];
|
|
|
210 switch (op->type)
|
|
|
211 {
|
|
|
212 case OP_INC: *opc = &&op_incA; break;
|
|
|
213 case OP_DEC: *opc = &&op_decA; break;
|
|
|
214 case OP_LEFT: *opc = &&op_leftA; break;
|
|
|
215 case OP_RIGHT: *opc = &&op_rightA; break;
|
|
|
216 case OP_WAIT: *opc = &&op_waitA; break;
|
|
|
217 case OP_LOOP1: *opc = &&op_loop1A; break;
|
|
|
218 case OP_LOOP2: *opc = &&op_loop2A; break;
|
|
|
219 case OP_REP1: *opc = &&op_rep1A; break;
|
|
|
220 case OP_REP2:
|
|
|
221 if (op->inner != -1) *opc = &&op_irep2A;
|
|
|
222 else *opc = &&op_rep2A;
|
|
|
223 break;
|
|
|
224 case OP_INNER1: *opc = &&op_inner1A; break;
|
|
|
225 case OP_INNER2: *opc = &&op_inner2A; break;
|
|
|
226 }
|
|
|
227 }
|
|
|
228
|
|
|
229 opcA[opsA->len] = &&op_doneA;
|
|
|
230
|
|
|
231 for (int at = 0; at < opsB->len; at++)
|
|
|
232 {
|
|
|
233 struct op *op = &oplB[at];
|
|
|
234 void **opc = &opcB[at];
|
|
|
235 switch (op->type)
|
|
|
236 {
|
|
|
237 case OP_INC: *opc = &&op_incB; break;
|
|
|
238 case OP_DEC: *opc = &&op_decB; break;
|
|
|
239 case OP_LEFT: *opc = &&op_leftB; break;
|
|
|
240 case OP_RIGHT: *opc = &&op_rightB; break;
|
|
|
241 case OP_WAIT: *opc = &&op_waitB; break;
|
|
|
242 case OP_LOOP1: *opc = &&op_loop1B; break;
|
|
|
243 case OP_LOOP2: *opc = &&op_loop2B; break;
|
|
|
244 case OP_REP1: *opc = &&op_rep1B; break;
|
|
|
245 case OP_REP2:
|
|
|
246 if (op->inner != -1) *opc = &&op_irep2B;
|
|
|
247 else *opc = &&op_rep2B;
|
|
|
248 break;
|
|
|
249 case OP_INNER1: *opc = &&op_inner1B; break;
|
|
|
250 case OP_INNER2: *opc = &&op_inner2B; break;
|
|
|
251 }
|
|
|
252 }
|
|
|
253
|
|
|
254 opcB[opsB->len] = &&nextcycle; /* a slight shortcut */
|
|
|
255
|
|
|
256 /* state-holding variables */
|
|
|
257
|
|
|
258 static int repStackA[MAXNEST], repStackB[MAXNEST];
|
|
|
259
|
|
|
260 int ipA = 0, ipB = 0;
|
|
|
261 unsigned char *ptrA = 0, *ptrB = 0, bcache = 0;
|
|
|
262 int repA = 0, repB = 0, *repSA = 0, *repSB = 0;
|
|
|
263 int deathsA = 0, deathsB = 0;
|
|
|
264 int cycles = 0;
|
|
|
265 int score = 0;
|
|
|
266
|
|
|
267 /* execute with all tape lenghts and both relative polarities */
|
|
|
268
|
|
|
269 #define EXECUTE_ALL(sym, pol) \
|
|
|
270 ret = &&sym; \
|
|
|
271 for (tapesize = MINTAPE; tapesize <= MAXTAPE; tapesize++) \
|
|
|
272 { \
|
|
|
273 ipA = 0, ipB = 0; \
|
|
|
274 \
|
|
|
275 memset(tape, 0, tapesize); \
|
|
|
276 ptrA = &tape[0], ptrB = &tape[tapesize-1]; \
|
|
|
277 *ptrA = 128, *ptrB = 128; bcache = 128; \
|
|
|
278 \
|
|
|
279 repSA = repStackA, repSB = repStackB; \
|
|
|
280 deathsA = 0, deathsB = 0; \
|
|
|
281 \
|
|
|
282 cycles = MAXCYCLES; \
|
|
|
283 \
|
|
|
284 score = 0; \
|
|
|
285 goto *opcA[0]; \
|
|
|
286 sym: \
|
|
|
287 scores[pol][tapesize] = score; \
|
|
|
288 }
|
|
|
289
|
|
|
290 void *ret;
|
|
|
291 int tapesize = 0;
|
|
|
292
|
|
|
293 EXECUTE_ALL(done_normal, 0);
|
|
|
294
|
|
|
295 for (int at = 0; at < opsB->len; at++)
|
|
|
296 {
|
|
|
297 enum optype op = oplB[at].type;
|
|
|
298 if (op == OP_INC) opcB[at] = &&op_decB;
|
|
|
299 else if (op == OP_DEC) opcB[at] = &&op_incB;
|
|
|
300 }
|
|
|
301
|
|
|
302 EXECUTE_ALL(done_flipped, 1);
|
|
|
303
|
|
|
304 free(opcA);
|
|
|
305 free(opcB);
|
|
|
306 return;
|
|
|
307
|
|
|
308 /* actual core */
|
|
|
309
|
|
|
310 #define NEXTA ipA++; goto *opcB[ipB]
|
|
|
311 #define NEXTB ipB++; goto nextcycle
|
|
|
312
|
|
|
313 /* #define TRACE 1 */
|
|
|
314
|
|
|
315 nextcycle:
|
|
|
316 cycles--;
|
|
|
317
|
|
|
318 if (!tape[0]) deathsA++; else if (deathsA == 1) deathsA = 0;
|
|
|
319 if (!tape[tapesize-1]) deathsB++; else if (deathsB == 1) deathsB = 0;
|
|
|
320
|
|
|
321 #ifdef TRACE
|
|
|
322 printf("%6d: ", MAXCYCLES-cycles);
|
|
|
323 for (int i = 0; i < tapesize; i++)
|
|
|
324 printf("%c%02x ",
|
|
|
325 (ptrA - tape) == i
|
|
|
326 ? ((ptrB - tape) == i ? 'X' : 'A')
|
|
|
327 : ((ptrB - tape) == i ? 'B' : ' '),
|
|
|
328 tape[i]);
|
|
|
329 printf(" dA %d dB %d ipA %d ipB %d\n", deathsA, deathsB, ipA, ipB);
|
|
|
330 #endif
|
|
|
331
|
|
|
332 if (deathsA >= 2 && deathsB >= 2)
|
|
|
333 goto *ret;
|
|
|
334 else if (deathsA >= 2)
|
|
|
335 {
|
|
|
336 score++;
|
|
|
337 goto *ret;
|
|
|
338 }
|
|
|
339 else if (deathsB >= 2)
|
|
|
340 {
|
|
|
341 score--;
|
|
|
342 goto *ret;
|
|
|
343 }
|
|
|
344
|
|
|
345 if (!cycles)
|
|
|
346 goto *ret;
|
|
|
347
|
|
|
348 bcache = *ptrB;
|
|
|
349 goto *opcA[ipA];
|
|
|
350
|
|
|
351 fallA:
|
|
|
352 deathsA = 2;
|
|
|
353 goto *opcB[ipB];
|
|
|
354
|
|
|
355 fallB:
|
|
|
356 if (!tape[0]) deathsA++;
|
|
|
357 if (deathsA >= 2)
|
|
|
358 goto *ret;
|
|
|
359 score--;
|
|
|
360 goto *ret;
|
|
|
361
|
|
|
362 op_incA:
|
|
|
363 (*ptrA)++;
|
|
|
364 NEXTA;
|
|
|
365 op_incB:
|
|
|
366 (*ptrB)++;
|
|
|
367 NEXTB;
|
|
|
368 op_decA:
|
|
|
369 (*ptrA)--;
|
|
|
370 NEXTA;
|
|
|
371 op_decB:
|
|
|
372 (*ptrB)--;
|
|
|
373 NEXTB;
|
|
|
374
|
|
|
375 op_leftA:
|
|
|
376 ptrA--;
|
|
|
377 if (ptrA < tape) goto fallA;
|
|
|
378 NEXTA;
|
|
|
379 op_leftB:
|
|
|
380 ptrB++;
|
|
|
381 if (ptrB >= &tape[tapesize]) goto fallB;
|
|
|
382 NEXTB;
|
|
|
383 op_rightA:
|
|
|
384 ptrA++;
|
|
|
385 if (ptrA >= &tape[tapesize]) goto fallA;
|
|
|
386 NEXTA;
|
|
|
387 op_rightB:
|
|
|
388 ptrB--;
|
|
|
389 if (ptrB < tape) goto fallB;
|
|
|
390 NEXTB;
|
|
|
391
|
|
|
392 op_waitA:
|
|
|
393 NEXTA;
|
|
|
394 op_waitB:
|
|
|
395 NEXTB;
|
|
|
396
|
|
|
397 op_loop1A:
|
|
|
398 if (!*ptrA) ipA = oplA[ipA].match;
|
|
|
399 NEXTA;
|
|
|
400 op_loop1B:
|
|
|
401 if (!bcache) ipB = oplB[ipB].match;
|
|
|
402 NEXTB;
|
|
|
403 op_loop2A:
|
|
|
404 if (*ptrA) ipA = oplA[ipA].match;
|
|
|
405 NEXTA;
|
|
|
406 op_loop2B:
|
|
|
407 if (bcache) ipB = oplB[ipB].match;
|
|
|
408 NEXTB;
|
|
|
409
|
|
|
410 /* simple (..) repeats with no corresponding {..} block */
|
|
|
411
|
|
|
412 op_rep1A:
|
|
|
413 *repSA++ = repA; repA = oplA[ipA].count;
|
|
|
414 goto *opcA[++ipA];
|
|
|
415 op_rep1B:
|
|
|
416 *repSB++ = repB; repB = oplB[ipB].count;
|
|
|
417 goto *opcB[++ipB];
|
|
|
418
|
|
|
419 op_rep2A:
|
|
|
420 if (--repA) ipA = oplA[ipA].match;
|
|
|
421 else repA = *--repSA;
|
|
|
422 goto *opcA[++ipA];
|
|
|
423 op_rep2B:
|
|
|
424 if (--repB) ipB = oplB[ipB].match;
|
|
|
425 else repB = *--repSB;
|
|
|
426 goto *opcB[++ipB];
|
|
|
427
|
|
|
428 /* complex (..{ and }..) repeats; use .inner for target, count in different dirs */
|
|
|
429
|
|
|
430 op_inner1A:
|
|
|
431 if (--repA) ipA = oplA[ipA].inner;
|
|
|
432 else repA = *--repSA;
|
|
|
433 goto *opcA[++ipA];
|
|
|
434 op_inner1B:
|
|
|
435 if (--repB) ipB = oplB[ipB].inner;
|
|
|
436 else repB = *--repSB;
|
|
|
437 goto *opcB[++ipB];
|
|
|
438
|
|
|
439 op_inner2A:
|
|
|
440 *repSA++ = repA; repA = 1;
|
|
|
441 goto *opcA[++ipA];
|
|
|
442 op_inner2B:
|
|
|
443 *repSB++ = repB; repB = 1;
|
|
|
444 goto *opcB[++ipB];
|
|
|
445
|
|
|
446 op_irep2A:
|
|
|
447 if (++repA <= oplA[ipA].count) ipA = oplA[ipA].inner;
|
|
|
448 else repA = *--repSA;
|
|
|
449 goto *opcA[++ipA];
|
|
|
450 op_irep2B:
|
|
|
451 if (++repB <= oplB[ipB].count) ipB = oplB[ipB].inner;
|
|
|
452 else repB = *--repSB;
|
|
|
453 goto *opcB[++ipB];
|
|
|
454
|
|
|
455 op_doneA:
|
|
|
456 goto *opcB[ipB];
|
|
|
457 }
|
|
|
458
|
|
|
459 /* parsing and preprocessing, impl */
|
|
|
460
|
|
|
461 static int readrepc(unsigned char *buf, ssize_t bsize, int *bat, int fd)
|
|
|
462 {
|
|
|
463 /* read and parse a () count */
|
|
|
464
|
|
|
465 int at = *bat;
|
|
|
466
|
|
|
467 int nextc(void)
|
|
|
468 {
|
|
|
469 if (at < bsize)
|
|
|
470 return buf[at++];
|
|
|
471
|
|
|
472 unsigned char c;
|
|
|
473 ssize_t t = read(fd, &c, 1);
|
|
|
474 if (t < 0) die("read error");
|
|
|
475 if (t == 0) return -1;
|
|
|
476 return c;
|
|
|
477 }
|
|
|
478
|
|
|
479 int c = 0, ch;
|
|
|
480
|
|
|
481 ch = nextc();
|
|
|
482 if (ch != '*' && ch != '%')
|
|
|
483 {
|
|
|
484 /* treat garbage as ()*0 in case it's inside a comment */
|
|
|
485 buf[--at] = ch;
|
|
|
486 *bat = at-1;
|
|
|
487 return 0;
|
|
|
488 }
|
|
|
489
|
|
|
490 int neg = -1;
|
|
|
491
|
|
|
492 while (1)
|
|
|
493 {
|
|
|
494 ch = nextc();
|
|
|
495 if (ch == '-' && neg < 0)
|
|
|
496 {
|
|
|
497 neg = 1;
|
|
|
498 continue;
|
|
|
499 }
|
|
|
500 if (ch < '0' || ch > '9')
|
|
|
501 break;
|
|
|
502 if (neg < 0) neg = 0;
|
|
|
503
|
|
|
504 c = c*10 + (ch - '0');
|
|
|
505 if (c > MAXCYCLES)
|
|
|
506 {
|
|
|
507 c = MAXCYCLES;
|
|
|
508 ch = 0;
|
|
|
509 break;
|
|
|
510 }
|
|
|
511 }
|
|
|
512
|
|
|
513 buf[--at] = ch;
|
|
|
514 *bat = at-1;
|
|
|
515
|
|
|
516 return neg > 0 ? -c : c;
|
|
|
517 }
|
|
|
518
|
|
|
519 static struct oplist *readops(int fd)
|
|
|
520 {
|
|
|
521 /* lexical tokenizing into initial oplist */
|
|
|
522
|
|
|
523 static unsigned char buf[65536];
|
|
|
524 struct oplist *ops = opl_new();
|
|
|
525
|
|
|
526 while (1)
|
|
|
527 {
|
|
|
528 ssize_t got = read(fd, buf, sizeof buf);
|
|
|
529 if (got < 0) die("read error");
|
|
|
530 if (got == 0) break;
|
|
|
531
|
|
|
532 for (int i = 0; i < got; i++)
|
|
|
533 {
|
|
|
534 int c;
|
|
|
535
|
|
|
536 switch (buf[i])
|
|
|
537 {
|
|
|
538 case '+': opl_append(ops, OP_INC); break;
|
|
|
539 case '-': opl_append(ops, OP_DEC); break;
|
|
|
540 case '<': opl_append(ops, OP_LEFT); break;
|
|
|
541 case '>': opl_append(ops, OP_RIGHT); break;
|
|
|
542 case '.': opl_append(ops, OP_WAIT); break;
|
|
|
543 case '[': opl_append(ops, OP_LOOP1); break;
|
|
|
544 case ']': opl_append(ops, OP_LOOP2); break;
|
|
|
545 case '(': opl_append(ops, OP_REP1); break;
|
|
|
546 case ')':
|
|
|
547 /* need to extract the count */
|
|
|
548 i++;
|
|
|
549 c = readrepc(buf, got, &i, fd);
|
|
|
550 if (c < 0) c = MAXCYCLES;
|
|
|
551 opl_append(ops, OP_REP2);
|
|
|
552 ops->ops[ops->len-1].count = c;
|
|
|
553 break;
|
|
|
554 case '{': opl_append(ops, OP_INNER1); break;
|
|
|
555 case '}': opl_append(ops, OP_INNER2); break;
|
|
|
556 }
|
|
|
557 }
|
|
|
558 }
|
|
|
559
|
|
|
560 return ops;
|
|
|
561 }
|
|
|
562
|
|
|
563 static void matchrep(struct oplist *ops)
|
|
|
564 {
|
|
|
565 /* match (..) pairs and inner {..} blocks */
|
|
|
566
|
|
|
567 int stack[MAXNEST], mstack[MAXNEST];
|
|
|
568 int depth = 0, mdepth = 0;
|
|
|
569
|
|
|
570 for (int at = 0; at < ops->len; at++)
|
|
|
571 {
|
|
|
572 struct op *op = &ops->ops[at];
|
|
|
573
|
|
|
574 switch (op->type) /* in order of occurrence */
|
|
|
575 {
|
|
|
576 case OP_REP1:
|
|
|
577 if (depth == MAXNEST) fail("maximum () nesting depth exceeded");
|
|
|
578 stack[depth++] = at;
|
|
|
579 mstack[mdepth++] = at;
|
|
|
580 op->match = -1;
|
|
|
581 op->inner = -1;
|
|
|
582 break;
|
|
|
583
|
|
|
584 case OP_INNER1:
|
|
|
585 if (depth == MAXNEST) fail("maximum {} nesting depth exceeded");
|
|
|
586 if (!mdepth) fail("encountered { without matching (");
|
|
|
587 stack[depth++] = at;
|
|
|
588 op->match = -1;
|
|
|
589 op->inner = mstack[--mdepth];
|
|
|
590 if (ops->ops[op->inner].inner != -1) fail("same ( has multiple matching {s");
|
|
|
591 ops->ops[op->inner].inner = at;
|
|
|
592 break;
|
|
|
593
|
|
|
594 case OP_INNER2:
|
|
|
595 if (!depth) fail("terminating } without a matching {");
|
|
|
596 op->match = stack[--depth];
|
|
|
597 if (ops->ops[op->match].type != OP_INNER1) fail("mismatching }");
|
|
|
598 op->inner = -1;
|
|
|
599 ops->ops[op->match].match = at;
|
|
|
600 mdepth++;
|
|
|
601 break;
|
|
|
602
|
|
|
603 case OP_REP2:
|
|
|
604 if (!depth) fail("terminating ) without a matching (");
|
|
|
605 op->match = stack[--depth];
|
|
|
606 if (ops->ops[op->match].type != OP_REP1) fail("mismatching )");
|
|
|
607 op->inner = (ops->ops[op->match].inner != -1 ? ops->ops[ops->ops[op->match].inner].match : -1);
|
|
|
608 ops->ops[op->match].match = at;
|
|
|
609 ops->ops[op->match].count = op->count;
|
|
|
610 if (op->inner != -1)
|
|
|
611 {
|
|
|
612 ops->ops[op->inner].inner = at;
|
|
|
613 ops->ops[op->inner].count = op->count;
|
|
|
614 ops->ops[ops->ops[op->inner].match].count = op->count;
|
|
|
615 }
|
|
|
616 mdepth--;
|
|
|
617 break;
|
|
|
618
|
|
|
619 default:
|
|
|
620 /* do nothing */
|
|
|
621 break;
|
|
|
622 }
|
|
|
623 }
|
|
|
624
|
|
|
625 if (depth != 0)
|
|
|
626 fail("starting ( without a matching )");
|
|
|
627 }
|
|
|
628
|
|
|
629 static void cleanrep(struct oplist *ops)
|
|
|
630 {
|
|
|
631 /* clean out (...)*0 and ()*N */
|
|
|
632
|
|
|
633 for (int at = 0; at < ops->len; at++)
|
|
|
634 {
|
|
|
635 struct op *op = &ops->ops[at];
|
|
|
636 if (op->type == OP_REP1 && op->count == 0)
|
|
|
637 {
|
|
|
638 opl_del(ops, at, op->match+1);
|
|
|
639 at--;
|
|
|
640 }
|
|
|
641 }
|
|
|
642
|
|
|
643 /* TODO: clean ()*N with a multipass thing */
|
|
|
644 }
|
|
|
645
|
|
|
646 static void matchloop(struct oplist *ops)
|
|
|
647 {
|
|
|
648 /* match [..] pairs */
|
|
|
649
|
|
|
650 int stack[MAXNEST], nstack[MAXNEST];
|
|
|
651 int depth = 0, ndepth = 0;
|
|
|
652
|
|
|
653 for (int at = 0; at < ops->len; at++)
|
|
|
654 {
|
|
|
655 struct op *op = &ops->ops[at];
|
|
|
656
|
|
|
657 switch (op->type)
|
|
|
658 {
|
|
|
659 case OP_LOOP1:
|
|
|
660 if (depth == MAXNEST) fail("maximum [] nesting depth exceeded");
|
|
|
661 stack[depth] = at;
|
|
|
662 nstack[depth] = ndepth;
|
|
|
663 op->match = -1;
|
|
|
664 depth++;
|
|
|
665 break;
|
|
|
666
|
|
|
667 case OP_REP1:
|
|
|
668 case OP_INNER2:
|
|
|
669 ndepth++;
|
|
|
670 break;
|
|
|
671
|
|
|
672 case OP_INNER1:
|
|
|
673 case OP_REP2:
|
|
|
674 if (!ndepth) fail("impossible: negative ({..}) nesting depth in [..] matching");
|
|
|
675 ndepth--;
|
|
|
676 break;
|
|
|
677
|
|
|
678 case OP_LOOP2:
|
|
|
679 if (!depth) fail("terminating ] without a matching [");
|
|
|
680 depth--;
|
|
|
681 if (ndepth != nstack[depth]) fail("[..] crossing across ({..}) levels");
|
|
|
682 op->match = stack[depth];
|
|
|
683 ops->ops[op->match].match = at;
|
|
|
684 break;
|
|
|
685
|
|
|
686 default:
|
|
|
687 /* do nothing */
|
|
|
688 break;
|
|
|
689 }
|
|
|
690 }
|
|
|
691
|
|
|
692 if (depth != 0)
|
|
|
693 fail("starting [ without a matching ]");
|
|
|
694 }
|
|
|
695
|
|
|
696 static struct oplist *parse(int fd)
|
|
|
697 {
|
|
|
698 struct oplist *ops = readops(fd);
|
|
|
699
|
|
|
700 /* handle (...) constructions first */
|
|
|
701
|
|
|
702 matchrep(ops);
|
|
|
703 cleanrep(ops);
|
|
|
704
|
|
|
705 /* handle [...] constructions now that rep/inner levels are known */
|
|
|
706
|
|
|
707 matchloop(ops);
|
|
|
708
|
|
|
709 return ops;
|
|
|
710 }
|
|
|
711
|
|
|
712 /* oplist handling, impl */
|
|
|
713
|
|
|
714 static struct oplist *opl_new(void)
|
|
|
715 {
|
|
|
716 struct oplist *o = smalloc(sizeof *o);
|
|
|
717
|
|
|
718 o->len = 0;
|
|
|
719 o->size = 32;
|
|
|
720 o->ops = smalloc(o->size * sizeof *o->ops);
|
|
|
721
|
|
|
722 return o;
|
|
|
723 }
|
|
|
724
|
|
|
725 static void opl_free(struct oplist *o)
|
|
|
726 {
|
|
|
727 free(o->ops);
|
|
|
728 free(o);
|
|
|
729 }
|
|
|
730
|
|
|
731 static void opl_append(struct oplist *o, enum optype type)
|
|
|
732 {
|
|
|
733 if (o->len == o->size)
|
|
|
734 {
|
|
|
735 o->size += o->size >> 1;
|
|
|
736 o->ops = srealloc(o->ops, o->size * sizeof *o->ops);
|
|
|
737 }
|
|
|
738
|
|
|
739 o->ops[o->len].type = type;
|
|
|
740 o->ops[o->len].match = -1;
|
|
|
741 o->ops[o->len].inner = -1;
|
|
|
742 o->ops[o->len].count = -1;
|
|
|
743 o->len++;
|
|
|
744 }
|
|
|
745
|
|
|
746 static void opl_del(struct oplist *o, int start, int end)
|
|
|
747 {
|
|
|
748 int d = end - start;
|
|
|
749 if (!d)
|
|
|
750 return;
|
|
|
751
|
|
|
752 if (end == o->len)
|
|
|
753 {
|
|
|
754 o->len = start;
|
|
|
755 return;
|
|
|
756 }
|
|
|
757
|
|
|
758 memmove(&o->ops[start], &o->ops[end], (o->len - end) * sizeof *o->ops);
|
|
|
759 o->len -= d;
|
|
|
760
|
|
|
761 for (int at = 0; at < o->len; at++)
|
|
|
762 {
|
|
|
763 struct op *op = &o->ops[at];
|
|
|
764 if (op->match >= start && op->match < end) die("opl_del: dangling ->match");
|
|
|
765 if (op->inner >= start && op->inner < end) die("opl_del: dangling ->inner");
|
|
|
766 if (op->match >= end) op->match -= d;
|
|
|
767 if (op->inner >= end) op->inner -= d;
|
|
|
768 }
|
|
|
769 }
|
|
|
770
|
|
|
771 /* generic helpers, impl */
|
|
|
772
|
|
|
773 static void die(const char *fmt, ...)
|
|
|
774 {
|
|
|
775 va_list ap;
|
|
|
776 va_start(ap, fmt);
|
|
|
777 vfprintf(stderr, fmt, ap);
|
|
|
778 va_end(ap);
|
|
|
779 fputc('\n', stderr);
|
|
|
780
|
|
|
781 exit(1);
|
|
|
782 }
|
|
|
783
|
|
|
784 static void fail(const char *fmt, ...)
|
|
|
785 {
|
|
|
786 va_list ap;
|
|
|
787 va_start(ap, fmt);
|
|
|
788 vsnprintf(fail_msg, sizeof fail_msg, fmt, ap);
|
|
|
789 va_end(ap);
|
|
|
790
|
|
|
791 longjmp(fail_buf, 1);
|
|
|
792 }
|
|
|
793
|
|
|
794 static void *smalloc(size_t size)
|
|
|
795 {
|
|
|
796 void *ptr = malloc(size);
|
|
|
797 if (!ptr) die("out of memory");
|
|
|
798 return ptr;
|
|
|
799 }
|
|
|
800
|
|
|
801 static void *srealloc(void *ptr, size_t size)
|
|
|
802 {
|
|
|
803 ptr = realloc(ptr, size);
|
|
|
804 if (!ptr) die("out of memory");
|
|
|
805 return ptr;
|
|
|
806 }
|
|
|
807
|
|
|
808 static int sopen(const char *fname)
|
|
|
809 {
|
|
|
810 int fd = open(fname, O_RDONLY);
|
|
|
811 if (fd == -1)
|
|
|
812 die("open failed: %s", fname);
|
|
|
813 return fd;
|
|
|
814 }
|
