source: mainline/uspace/lib/bithenge/script.c@ a42d7d8

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since a42d7d8 was a42d7d8, checked in by Sean Bartell <wingedtachikoma@…>, 13 years ago

Bithenge: add fake system call errors to test error handling
  • Property mode set to 100644
File size: 34.4 KB
Line 
1/*
2 * Copyright (c) 2012 Sean Bartell
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 *
9 * - Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * - Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * - The name of the author may not be used to endorse or promote products
15 * derived from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
18 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
19 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
20 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
21 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
22 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
26 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/** @addtogroup bithenge
30 * @{
31 */
32/**
33 * @file
34 * Script parsing.
35 */
36
37#include <ctype.h>
38#include <stdio.h>
39#include <stdlib.h>
40#include "compound.h"
41#include "expression.h"
42#include "os.h"
43#include "script.h"
44#include "sequence.h"
45#include "transform.h"
46#include "tree.h"
47
48/** Tokens with more characters than this may be read incorrectly. */
49#define MAX_TOKEN_SIZE 256
50#define BUFFER_SIZE 4096
51
52/** Single-character symbols are represented by the character itself. Every
53 * other token uses one of these values: */
54typedef enum {
55 TOKEN_ERROR = -128,
56
57 TOKEN_AND,
58 TOKEN_CONCAT,
59 TOKEN_EQUALS,
60 TOKEN_EOF,
61 TOKEN_GREATER_THAN_OR_EQUAL,
62 TOKEN_IDENTIFIER,
63 TOKEN_INTEGER,
64 TOKEN_INTEGER_DIVIDE,
65 TOKEN_LEFT_ARROW,
66 TOKEN_LESS_THAN_OR_EQUAL,
67 TOKEN_NOT_EQUAL,
68 TOKEN_OR,
69
70 /* Keywords */
71 TOKEN_DO,
72 TOKEN_ELSE,
73 TOKEN_FALSE,
74 TOKEN_IF,
75 TOKEN_IN,
76 TOKEN_PARTIAL,
77 TOKEN_REPEAT,
78 TOKEN_STRUCT,
79 TOKEN_SWITCH,
80 TOKEN_TRANSFORM,
81 TOKEN_TRUE,
82 TOKEN_WHILE,
83} token_type_t;
84
85/** Singly-linked list of named transforms. */
86typedef struct transform_list {
87 char *name;
88 bithenge_transform_t *transform;
89 struct transform_list *next;
90} transform_list_t;
91
92/** State kept by the parser. */
93typedef struct {
94 /** Rather than constantly checking return values, the parser uses this
95 * to indicate whether an error has occurred. */
96 int error;
97
98 /** The list of named transforms. */
99 transform_list_t *transform_list;
100
101 /** The name of the script file. */
102 const char *filename;
103 /** The script file being read from. */
104 FILE *file;
105 /** The buffer that holds script code. There is always a '\0' after the
106 * current position to prevent reading too far. */
107 char buffer[BUFFER_SIZE];
108 /** The start position within the buffer of the next unread token. */
109 size_t buffer_pos;
110 /** The start position within the buffer of the current token. */
111 size_t old_buffer_pos;
112 /** The line number of the current token. */
113 int lineno;
114 /** Added to a buffer position to find the column number. */
115 int line_offset;
116
117 /** The type of the current token. */
118 token_type_t token;
119 union {
120 /** The value of a TOKEN_IDENTIFIER token. Unless changed to
121 * NULL, it will be freed when the next token is read. */
122 char *token_string;
123 /** The value of a TOKEN_INTEGER token. */
124 bithenge_int_t token_int;
125 };
126
127 /** The names of the current transform's parameters. */
128 char **parameter_names;
129 /** The number of parameters. */
130 int num_params;
131 /** @a parse_expression sets this when TOKEN_IN is used. */
132 bool in_node_used;
133} state_t;
134
135/** Free the previous token's data. This must be called before changing
136 * state->token. */
137static void done_with_token(state_t *state)
138{
139 if (state->token == TOKEN_IDENTIFIER)
140 free(state->token_string);
141 state->token = TOKEN_ERROR;
142}
143
144/** Note that an error has occurred if error is not EOK. */
145static void error_errno(state_t *state, int error)
146{
147 // Don't overwrite a previous error.
148 if (state->error == EOK && error != EOK) {
149 done_with_token(state);
150 state->token = TOKEN_ERROR;
151 state->error = error;
152 }
153}
154
155/** Note that a syntax error has occurred and print an error message. */
156static void syntax_error(state_t *state, const char *message)
157{
158 // Printing multiple errors is confusing.
159 if (state->error == EOK) {
160 size_t start_char = state->old_buffer_pos + state->line_offset;
161 size_t end_char = state->buffer_pos + state->line_offset;
162 size_t size = end_char - start_char;
163 fprintf(stderr, "%s:%d:", state->filename, state->lineno);
164 if (size <= 1)
165 fprintf(stderr, "%zd: ", start_char);
166 else
167 fprintf(stderr, "%zd-%zd: ", start_char, end_char - 1);
168 fprintf(stderr, "%s: \"%.*s\"\n", message, (int)size,
169 state->buffer + state->old_buffer_pos);
170 error_errno(state, EINVAL);
171 }
172}
173
174/** Ensure the buffer contains enough characters to read a token. */
175static void fill_buffer(state_t *state)
176{
177 if (state->buffer_pos + MAX_TOKEN_SIZE < BUFFER_SIZE)
178 return;
179
180 size_t empty_size = state->buffer_pos;
181 size_t used_size = BUFFER_SIZE - 1 - state->buffer_pos;
182 memmove(state->buffer, state->buffer + state->buffer_pos, used_size);
183 state->line_offset += state->buffer_pos;
184 state->buffer_pos = 0;
185
186 size_t read_size = fread(state->buffer + used_size, 1, empty_size,
187 state->file);
188 if (ferror(state->file))
189 error_errno(state, EIO);
190 state->buffer[used_size + read_size] = '\0';
191}
192
193/** Read the next token. */
194static void next_token(state_t *state)
195{
196 fill_buffer(state);
197 done_with_token(state);
198 state->old_buffer_pos = state->buffer_pos;
199 char ch = state->buffer[state->buffer_pos];
200 if (ch == '\0') {
201 state->token = TOKEN_EOF;
202 } else if (ch == '#') {
203 while (state->buffer[state->buffer_pos] != '\n'
204 && state->buffer[state->buffer_pos] != '\0') {
205 state->buffer_pos++;
206 fill_buffer(state);
207 }
208 next_token(state);
209 return;
210 } else if (isspace(ch)) {
211 // Will eventually reach the '\0' at the end
212 while (isspace(state->buffer[state->buffer_pos])) {
213 if (state->buffer[state->buffer_pos] == '\n') {
214 state->lineno++;
215 state->line_offset = -state->buffer_pos;
216 }
217 state->buffer_pos++;
218 }
219 next_token(state);
220 return;
221 } else if (isalpha(ch)) {
222 while (isalnum(state->buffer[state->buffer_pos])
223 || state->buffer[state->buffer_pos] == '_')
224 state->buffer_pos++;
225 char *value = str_ndup(state->buffer + state->old_buffer_pos,
226 state->buffer_pos - state->old_buffer_pos);
227 if (!value) {
228 error_errno(state, ENOMEM);
229 } else if (!str_cmp(value, "do")) {
230 state->token = TOKEN_DO;
231 free(value);
232 } else if (!str_cmp(value, "else")) {
233 state->token = TOKEN_ELSE;
234 free(value);
235 } else if (!str_cmp(value, "false")) {
236 state->token = TOKEN_FALSE;
237 free(value);
238 } else if (!str_cmp(value, "if")) {
239 state->token = TOKEN_IF;
240 free(value);
241 } else if (!str_cmp(value, "in")) {
242 state->token = TOKEN_IN;
243 free(value);
244 } else if (!str_cmp(value, "partial")) {
245 state->token = TOKEN_PARTIAL;
246 free(value);
247 } else if (!str_cmp(value, "repeat")) {
248 state->token = TOKEN_REPEAT;
249 free(value);
250 } else if (!str_cmp(value, "struct")) {
251 state->token = TOKEN_STRUCT;
252 free(value);
253 } else if (!str_cmp(value, "switch")) {
254 state->token = TOKEN_SWITCH;
255 free(value);
256 } else if (!str_cmp(value, "transform")) {
257 state->token = TOKEN_TRANSFORM;
258 free(value);
259 } else if (!str_cmp(value, "true")) {
260 state->token = TOKEN_TRUE;
261 free(value);
262 } else if (!str_cmp(value, "while")) {
263 state->token = TOKEN_WHILE;
264 free(value);
265 } else {
266 state->token = TOKEN_IDENTIFIER;
267 state->token_string = value;
268 }
269 } else if (isdigit(ch)) {
270 while (isdigit(state->buffer[state->buffer_pos]))
271 state->buffer_pos++;
272 state->token = TOKEN_INTEGER;
273 int rc = bithenge_parse_int(state->buffer +
274 state->old_buffer_pos, &state->token_int);
275 error_errno(state, rc);
276 } else if (ch == '<') {
277 state->token = ch;
278 state->buffer_pos++;
279 if (state->buffer[state->buffer_pos] == '-') {
280 state->buffer_pos++;
281 state->token = TOKEN_LEFT_ARROW;
282 } else if (state->buffer[state->buffer_pos] == '=') {
283 state->buffer_pos++;
284 state->token = TOKEN_LESS_THAN_OR_EQUAL;
285 }
286 } else if (ch == '>') {
287 state->token = ch;
288 state->buffer_pos++;
289 if (state->buffer[state->buffer_pos] == '=') {
290 state->buffer_pos++;
291 state->token = TOKEN_GREATER_THAN_OR_EQUAL;
292 }
293 } else if (ch == '=') {
294 state->token = ch;
295 state->buffer_pos++;
296 if (state->buffer[state->buffer_pos] == '=') {
297 state->token = TOKEN_EQUALS;
298 state->buffer_pos++;
299 }
300 } else if (ch == '/') {
301 state->token = ch;
302 state->buffer_pos++;
303 if (state->buffer[state->buffer_pos] == '/') {
304 state->token = TOKEN_INTEGER_DIVIDE;
305 state->buffer_pos++;
306 }
307 } else if (ch == '!') {
308 state->token = ch;
309 state->buffer_pos++;
310 if (state->buffer[state->buffer_pos] == '=') {
311 state->token = TOKEN_NOT_EQUAL;
312 state->buffer_pos++;
313 }
314 } else if (ch == '&') {
315 state->token = ch;
316 state->buffer_pos++;
317 if (state->buffer[state->buffer_pos] == '&') {
318 state->token = TOKEN_AND;
319 state->buffer_pos++;
320 }
321 } else if (ch == '|') {
322 state->token = ch;
323 state->buffer_pos++;
324 if (state->buffer[state->buffer_pos] == '|') {
325 state->token = TOKEN_OR;
326 state->buffer_pos++;
327 }
328 } else if (ch == '+') {
329 state->token = ch;
330 state->buffer_pos++;
331 if (state->buffer[state->buffer_pos] == '+') {
332 state->token = TOKEN_CONCAT;
333 state->buffer_pos++;
334 }
335 } else {
336 state->token = ch;
337 state->buffer_pos++;
338 }
339}
340
341/** Allocate memory and handle failure by setting the error in the state. The
342 * caller must check the state for errors before using the return value of this
343 * function. */
344static void *state_malloc(state_t *state, size_t size)
345{
346 if (state->error != EOK)
347 return NULL;
348 void *result = malloc(size);
349 if (result == NULL)
350 error_errno(state, ENOMEM);
351 return result;
352}
353
354/** Reallocate memory and handle failure by setting the error in the state. If
355 * an error occurs, the existing pointer will be returned. */
356static void *state_realloc(state_t *state, void *ptr, size_t size)
357{
358 if (state->error != EOK)
359 return ptr;
360 void *result = realloc(ptr, size);
361 if (result == NULL) {
362 error_errno(state, ENOMEM);
363 return ptr;
364 }
365 return result;
366}
367
368/** Expect and consume a certain token. If the next token is of the wrong type,
369 * an error is caused. */
370static void expect(state_t *state, token_type_t type)
371{
372 if (state->token != type) {
373 syntax_error(state, "unexpected");
374 return;
375 }
376 next_token(state);
377}
378
379/** Expect and consume an identifier token. If the next token is not an
380 * identifier, an error is caused and this function returns null. */
381static char *expect_identifier(state_t *state)
382{
383 if (state->token != TOKEN_IDENTIFIER) {
384 syntax_error(state, "unexpected (identifier expected)");
385 return NULL;
386 }
387 char *val = state->token_string;
388 state->token_string = NULL;
389 next_token(state);
390 return val;
391}
392
393/** Find a transform by name. A reference will be added to the transform.
394 * @return The found transform, or NULL if none was found. */
395static bithenge_transform_t *get_named_transform(state_t *state,
396 const char *name)
397{
398 for (transform_list_t *e = state->transform_list; e; e = e->next) {
399 if (!str_cmp(e->name, name)) {
400 bithenge_transform_inc_ref(e->transform);
401 return e->transform;
402 }
403 }
404 for (int i = 0; bithenge_primitive_transforms[i].name; i++) {
405 if (!str_cmp(bithenge_primitive_transforms[i].name, name)) {
406 bithenge_transform_t *xform =
407 bithenge_primitive_transforms[i].transform;
408 bithenge_transform_inc_ref(xform);
409 return xform;
410 }
411 }
412 return NULL;
413}
414
415/** Add a named transform. This function takes ownership of the name and a
416 * reference to the transform. If an error has occurred, either may be null. */
417static void add_named_transform(state_t *state, bithenge_transform_t *xform, char *name)
418{
419 transform_list_t *entry = state_malloc(state, sizeof(*entry));
420 if (state->error != EOK) {
421 free(name);
422 bithenge_transform_dec_ref(xform);
423 free(entry);
424 return;
425 }
426 entry->name = name;
427 entry->transform = xform;
428 entry->next = state->transform_list;
429 state->transform_list = entry;
430}
431
432static bithenge_transform_t *parse_transform(state_t *state);
433static bithenge_transform_t *parse_struct(state_t *state);
434static bithenge_expression_t *parse_expression(state_t *state);
435
436
437
438/***************** Expressions *****************/
439
440typedef enum {
441 PRECEDENCE_NONE,
442 PRECEDENCE_AND,
443 PRECEDENCE_EQUALS,
444 PRECEDENCE_COMPARE,
445 PRECEDENCE_ADD,
446 PRECEDENCE_MULTIPLY,
447} precedence_t;
448
449static bithenge_binary_op_t token_as_binary_operator(token_type_t token)
450{
451 switch ((int)token) {
452 case '+':
453 return BITHENGE_EXPRESSION_ADD;
454 case '-':
455 return BITHENGE_EXPRESSION_SUBTRACT;
456 case '*':
457 return BITHENGE_EXPRESSION_MULTIPLY;
458 case TOKEN_INTEGER_DIVIDE:
459 return BITHENGE_EXPRESSION_INTEGER_DIVIDE;
460 case '%':
461 return BITHENGE_EXPRESSION_MODULO;
462 case '<':
463 return BITHENGE_EXPRESSION_LESS_THAN;
464 case TOKEN_LESS_THAN_OR_EQUAL:
465 return BITHENGE_EXPRESSION_LESS_THAN_OR_EQUAL;
466 case '>':
467 return BITHENGE_EXPRESSION_GREATER_THAN;
468 case TOKEN_GREATER_THAN_OR_EQUAL:
469 return BITHENGE_EXPRESSION_GREATER_THAN_OR_EQUAL;
470 case TOKEN_EQUALS:
471 return BITHENGE_EXPRESSION_EQUALS;
472 case TOKEN_NOT_EQUAL:
473 return BITHENGE_EXPRESSION_NOT_EQUALS;
474 case TOKEN_AND:
475 return BITHENGE_EXPRESSION_AND;
476 case TOKEN_OR:
477 return BITHENGE_EXPRESSION_OR;
478 case TOKEN_CONCAT:
479 return BITHENGE_EXPRESSION_CONCAT;
480 default:
481 return BITHENGE_EXPRESSION_INVALID_BINARY_OP;
482 }
483}
484
485static precedence_t binary_operator_precedence(bithenge_binary_op_t op)
486{
487 switch (op) {
488 case BITHENGE_EXPRESSION_ADD: /* fallthrough */
489 case BITHENGE_EXPRESSION_SUBTRACT: /* fallthrough */
490 case BITHENGE_EXPRESSION_CONCAT:
491 return PRECEDENCE_ADD;
492 case BITHENGE_EXPRESSION_MULTIPLY: /* fallthrough */
493 case BITHENGE_EXPRESSION_INTEGER_DIVIDE: /* fallthrough */
494 case BITHENGE_EXPRESSION_MODULO:
495 return PRECEDENCE_MULTIPLY;
496 case BITHENGE_EXPRESSION_LESS_THAN: /* fallthrough */
497 case BITHENGE_EXPRESSION_LESS_THAN_OR_EQUAL: /* fallthrough */
498 case BITHENGE_EXPRESSION_GREATER_THAN: /* fallthrough */
499 case BITHENGE_EXPRESSION_GREATER_THAN_OR_EQUAL:
500 return PRECEDENCE_COMPARE;
501 case BITHENGE_EXPRESSION_EQUALS: /* fallthrough */
502 case BITHENGE_EXPRESSION_NOT_EQUALS:
503 return PRECEDENCE_EQUALS;
504 case BITHENGE_EXPRESSION_AND: /* fallthrough */
505 case BITHENGE_EXPRESSION_OR:
506 return PRECEDENCE_AND;
507 default:
508 assert(false);
509 return PRECEDENCE_NONE;
510 }
511}
512
513static bithenge_expression_t *parse_term(state_t *state)
514{
515 int rc;
516 if (state->token == TOKEN_TRUE || state->token == TOKEN_FALSE) {
517 bool val = state->token == TOKEN_TRUE;
518 next_token(state);
519 bithenge_node_t *node;
520 rc = bithenge_new_boolean_node(&node, val);
521 if (rc != EOK) {
522 error_errno(state, rc);
523 return NULL;
524 }
525
526 bithenge_expression_t *expr;
527 rc = bithenge_const_expression(&expr, node);
528 if (rc != EOK) {
529 error_errno(state, rc);
530 return NULL;
531 }
532
533 return expr;
534 } else if (state->token == TOKEN_IN) {
535 next_token(state);
536 state->in_node_used = true;
537 bithenge_expression_t *expr;
538 rc = bithenge_in_node_expression(&expr);
539 if (rc != EOK) {
540 error_errno(state, rc);
541 return NULL;
542 }
543 return expr;
544 } else if (state->token == TOKEN_INTEGER) {
545 bithenge_int_t val = state->token_int;
546 next_token(state);
547 bithenge_node_t *node;
548 rc = bithenge_new_integer_node(&node, val);
549 if (rc != EOK) {
550 error_errno(state, rc);
551 return NULL;
552 }
553
554 bithenge_expression_t *expr;
555 rc = bithenge_const_expression(&expr, node);
556 if (rc != EOK) {
557 error_errno(state, rc);
558 return NULL;
559 }
560
561 return expr;
562 } else if (state->token == TOKEN_IDENTIFIER) {
563 int i;
564 for (i = 0; i < state->num_params; i++)
565 if (!str_cmp(state->parameter_names[i],
566 state->token_string))
567 break;
568
569 if (i == state->num_params) {
570 syntax_error(state, "unknown identifier");
571 return NULL;
572 }
573
574 next_token(state);
575
576 bithenge_expression_t *expr;
577 rc = bithenge_param_expression(&expr, i);
578 if (rc != EOK) {
579 error_errno(state, rc);
580 return NULL;
581 }
582 return expr;
583 } else if (state->token == '.') {
584 next_token(state);
585
586 const char *id = expect_identifier(state);
587 bithenge_node_t *key = NULL;
588 bithenge_expression_t *expr = NULL;
589
590 if (state->error == EOK) {
591 rc = bithenge_new_string_node(&key, id, true);
592 id = NULL;
593 error_errno(state, rc);
594 }
595
596 if (state->error == EOK) {
597 rc = bithenge_scope_member_expression(&expr, key);
598 key = NULL;
599 if (rc != EOK)
600 expr = NULL;
601 error_errno(state, rc);
602 }
603
604 if (state->error != EOK) {
605 free((char *)id);
606 bithenge_node_dec_ref(key);
607 bithenge_expression_dec_ref(expr);
608 return NULL;
609 }
610
611 return expr;
612 } else if (state->token == '(') {
613 next_token(state);
614 bithenge_expression_t *expr = parse_expression(state);
615 expect(state, ')');
616 return expr;
617 } else {
618 syntax_error(state, "expression expected");
619 return NULL;
620 }
621}
622
623static bithenge_expression_t *parse_postfix_expression(state_t *state)
624{
625 int rc;
626 bithenge_expression_t *expr = parse_term(state);
627 while (state->error == EOK) {
628 if (state->token == '.') {
629 next_token(state);
630
631 const char *id = expect_identifier(state);
632
633 if (state->error != EOK) {
634 free((char *)id);
635 bithenge_expression_dec_ref(expr);
636 return NULL;
637 }
638
639 bithenge_node_t *key = NULL;
640 rc = bithenge_new_string_node(&key, id, true);
641 if (rc != EOK) {
642 error_errno(state, rc);
643 bithenge_expression_dec_ref(expr);
644 return NULL;
645 }
646
647 bithenge_expression_t *key_expr;
648 rc = bithenge_const_expression(&key_expr, key);
649 if (rc != EOK) {
650 error_errno(state, rc);
651 bithenge_expression_dec_ref(expr);
652 return NULL;
653 }
654
655 rc = bithenge_binary_expression(&expr,
656 BITHENGE_EXPRESSION_MEMBER, expr, key_expr);
657 if (rc != EOK) {
658 error_errno(state, rc);
659 return NULL;
660 }
661 } else if (state->token == '[') {
662 next_token(state);
663 bithenge_expression_t *start = parse_expression(state);
664 bool absolute_limit = false;
665 if (state->token == ',' || state->token == ':') {
666 absolute_limit = state->token == ':';
667 next_token(state);
668 bithenge_expression_t *limit = NULL;
669 if (!(state->token == ']' && absolute_limit))
670 limit = parse_expression(state);
671 expect(state, ']');
672
673 if (state->error != EOK) {
674 bithenge_expression_dec_ref(expr);
675 bithenge_expression_dec_ref(start);
676 bithenge_expression_dec_ref(limit);
677 return NULL;
678 }
679 rc = bithenge_subblob_expression(&expr, expr, start,
680 limit, absolute_limit);
681 if (rc != EOK) {
682 error_errno(state, rc);
683 return NULL;
684 }
685 } else if (state->token == ']') {
686 next_token(state);
687
688 if (state->error != EOK) {
689 bithenge_expression_dec_ref(expr);
690 bithenge_expression_dec_ref(start);
691 return NULL;
692 }
693 rc = bithenge_binary_expression(&expr,
694 BITHENGE_EXPRESSION_MEMBER, expr, start);
695 if (rc != EOK) {
696 error_errno(state, rc);
697 return NULL;
698 }
699 } else {
700 syntax_error(state, "expected ',', ':', or ']'");
701 bithenge_expression_dec_ref(expr);
702 bithenge_expression_dec_ref(start);
703 return NULL;
704 }
705 } else {
706 break;
707 }
708 }
709 return expr;
710}
711
712static bithenge_expression_t *parse_expression_precedence(state_t *state,
713 precedence_t prev_precedence)
714{
715 bithenge_expression_t *expr = parse_postfix_expression(state);
716 while (state->error == EOK) {
717 bithenge_binary_op_t op =
718 token_as_binary_operator(state->token);
719 if (op == BITHENGE_EXPRESSION_INVALID_BINARY_OP)
720 break;
721 precedence_t precedence = binary_operator_precedence(op);
722 if (precedence <= prev_precedence)
723 break;
724 next_token(state);
725
726 bithenge_expression_t *expr2 =
727 parse_expression_precedence(state, precedence);
728 if (state->error != EOK) {
729 bithenge_expression_dec_ref(expr2);
730 break;
731 }
732 int rc = bithenge_binary_expression(&expr, op, expr, expr2);
733 if (rc != EOK) {
734 expr = NULL;
735 error_errno(state, rc);
736 }
737 }
738 if (state->error != EOK) {
739 bithenge_expression_dec_ref(expr);
740 expr = NULL;
741 }
742 return expr;
743}
744
745static bithenge_expression_t *parse_expression(state_t *state)
746{
747 return parse_expression_precedence(state, PRECEDENCE_NONE);
748}
749
750
751
752/* state->token must be TOKEN_IDENTIFIER when this is called. */
753static bithenge_transform_t *parse_invocation(state_t *state)
754{
755 bithenge_transform_t *result = get_named_transform(state,
756 state->token_string);
757 if (!result)
758 syntax_error(state, "transform not found");
759 next_token(state);
760
761 bithenge_expression_t **params = NULL;
762 int num_params = 0;
763 if (state->token == '(') {
764 next_token(state);
765 while (state->error == EOK && state->token != ')') {
766 if (num_params)
767 expect(state, ',');
768 params = state_realloc(state, params,
769 (num_params + 1)*sizeof(*params));
770 if (state->error != EOK)
771 break;
772 params[num_params] = parse_expression(state);
773 num_params++;
774 }
775 expect(state, ')');
776 }
777
778 /* TODO: show correct error position */
779 if (state->error == EOK
780 && bithenge_transform_num_params(result) != num_params)
781 syntax_error(state, "incorrect number of parameters before");
782
783 if (state->error != EOK) {
784 while (num_params--)
785 bithenge_expression_dec_ref(params[num_params]);
786 free(params);
787 bithenge_transform_dec_ref(result);
788 return NULL;
789 }
790
791 if (num_params) {
792 int rc = bithenge_param_wrapper(&result, result, params);
793 if (rc != EOK) {
794 error_errno(state, rc);
795 result = NULL;
796 }
797 }
798
799 return result;
800}
801
802/** Create a transform that just produces an empty node.
803 * @param state The parser state.
804 * @return The new transform, or NULL on error. */
805static bithenge_transform_t *make_empty_transform(state_t *state)
806{
807 bithenge_node_t *node;
808 int rc = bithenge_new_empty_internal_node(&node);
809 if (rc != EOK) {
810 error_errno(state, rc);
811 return NULL;
812 }
813
814 bithenge_expression_t *expr;
815 rc = bithenge_const_expression(&expr, node);
816 if (rc != EOK) {
817 error_errno(state, rc);
818 return NULL;
819 }
820
821 bithenge_transform_t *xform;
822 rc = bithenge_inputless_transform(&xform, expr);
823 if (rc != EOK) {
824 error_errno(state, rc);
825 return NULL;
826 }
827
828 return xform;
829}
830
831static bithenge_transform_t *parse_if(state_t *state, bool in_struct)
832{
833 expect(state, TOKEN_IF);
834 expect(state, '(');
835 bithenge_expression_t *expr = parse_expression(state);
836 expect(state, ')');
837 expect(state, '{');
838 bithenge_transform_t *true_xform =
839 in_struct ? parse_struct(state) : parse_transform(state);
840 expect(state, '}');
841
842 bithenge_transform_t *false_xform = NULL;
843 if (state->token == TOKEN_ELSE) {
844 next_token(state);
845 expect(state, '{');
846 false_xform =
847 in_struct ? parse_struct(state) : parse_transform(state);
848 expect(state, '}');
849 } else {
850 if (in_struct)
851 false_xform = make_empty_transform(state);
852 else
853 syntax_error(state, "else expected");
854 }
855
856 if (state->error != EOK) {
857 bithenge_expression_dec_ref(expr);
858 bithenge_transform_dec_ref(true_xform);
859 bithenge_transform_dec_ref(false_xform);
860 return NULL;
861 }
862
863 bithenge_transform_t *if_xform;
864 int rc = bithenge_if_transform(&if_xform, expr, true_xform,
865 false_xform);
866 if (rc != EOK) {
867 error_errno(state, rc);
868 return NULL;
869 }
870 return if_xform;
871}
872
873static bithenge_transform_t *parse_switch(state_t *state, bool in_struct)
874{
875 expect(state, TOKEN_SWITCH);
876 expect(state, '(');
877 bithenge_expression_t *ref_expr = parse_expression(state);
878 expect(state, ')');
879 expect(state, '{');
880 int num = 0;
881 bithenge_expression_t **exprs = NULL;
882 bithenge_transform_t **xforms = NULL;
883 while (state->error == EOK && state->token != '}') {
884 bithenge_expression_t *expr;
885 if (state->token == TOKEN_ELSE) {
886 next_token(state);
887 bithenge_node_t *node;
888 int rc = bithenge_new_boolean_node(&node, true);
889 if (rc != EOK) {
890 error_errno(state, rc);
891 break;
892 }
893 rc = bithenge_const_expression(&expr, node);
894 if (rc != EOK) {
895 error_errno(state, rc);
896 break;
897 }
898 } else {
899 expr = parse_expression(state);
900 if (state->error == EOK) {
901 bithenge_expression_inc_ref(ref_expr);
902 int rc = bithenge_binary_expression(&expr,
903 BITHENGE_EXPRESSION_EQUALS, ref_expr,
904 expr);
905 if (rc != EOK) {
906 error_errno(state, rc);
907 break;
908 }
909 }
910 }
911
912 expect(state, ':');
913 bithenge_transform_t *xform;
914 if (in_struct) {
915 expect(state, '{');
916 xform = parse_struct(state);
917 expect(state, '}');
918 } else
919 xform = parse_transform(state);
920 expect(state, ';');
921
922 exprs = state_realloc(state, exprs,
923 sizeof(*exprs) * (num + 1));
924 xforms = state_realloc(state, xforms,
925 sizeof(*xforms) * (num + 1));
926 if (state->error != EOK) {
927 bithenge_expression_dec_ref(expr);
928 bithenge_transform_dec_ref(xform);
929 break;
930 }
931
932 exprs[num] = expr;
933 xforms[num] = xform;
934 num++;
935 }
936 bithenge_expression_dec_ref(ref_expr);
937
938 bithenge_transform_t *switch_xform = &bithenge_invalid_transform;
939 bithenge_transform_inc_ref(switch_xform);
940 while (state->error == EOK && num >= 1) {
941 num--;
942 int rc = bithenge_if_transform(&switch_xform, exprs[num],
943 xforms[num], switch_xform);
944 if (rc != EOK) {
945 switch_xform = NULL;
946 error_errno(state, rc);
947 }
948 }
949
950 while (num >= 1) {
951 num--;
952 bithenge_expression_dec_ref(exprs[num]);
953 bithenge_transform_dec_ref(xforms[num]);
954 }
955 free(exprs);
956 free(xforms);
957
958 expect(state, '}');
959 return switch_xform;
960}
961
962static bithenge_transform_t *parse_repeat(state_t *state)
963{
964 expect(state, TOKEN_REPEAT);
965 bithenge_expression_t *expr = NULL;
966 if (state->token == '(') {
967 next_token(state);
968 expr = parse_expression(state);
969 expect(state, ')');
970 }
971 expect(state, '{');
972 bithenge_transform_t *xform = parse_transform(state);
973 expect(state, '}');
974
975 if (state->error != EOK) {
976 bithenge_expression_dec_ref(expr);
977 bithenge_transform_dec_ref(xform);
978 return NULL;
979 }
980
981 bithenge_transform_t *repeat_xform;
982 int rc = bithenge_repeat_transform(&repeat_xform, xform, expr);
983 if (rc != EOK) {
984 error_errno(state, rc);
985 return NULL;
986 }
987 return repeat_xform;
988}
989
990static bithenge_transform_t *parse_do_while(state_t *state)
991{
992 expect(state, TOKEN_DO);
993 expect(state, '{');
994 bithenge_transform_t *xform = parse_transform(state);
995 expect(state, '}');
996 expect(state, TOKEN_WHILE);
997 expect(state, '(');
998 bithenge_expression_t *expr = parse_expression(state);
999 expect(state, ')');
1000
1001 if (state->error != EOK) {
1002 bithenge_expression_dec_ref(expr);
1003 bithenge_transform_dec_ref(xform);
1004 return NULL;
1005 }
1006
1007 bithenge_transform_t *do_while_xform;
1008 int rc = bithenge_do_while_transform(&do_while_xform, xform, expr);
1009 if (rc != EOK) {
1010 error_errno(state, rc);
1011 return NULL;
1012 }
1013 return do_while_xform;
1014}
1015
1016static bithenge_transform_t *parse_partial(state_t *state)
1017{
1018 expect(state, TOKEN_PARTIAL);
1019 bithenge_transform_t *offset_xform = NULL;
1020 if (state->token == '(') {
1021 next_token(state);
1022 bithenge_expression_t *offset = parse_expression(state);
1023 expect(state, ')');
1024
1025 bithenge_expression_t *in_expr;
1026 int rc = bithenge_in_node_expression(&in_expr);
1027 if (rc != EOK)
1028 error_errno(state, rc);
1029 if (state->error != EOK) {
1030 bithenge_expression_dec_ref(offset);
1031 return NULL;
1032 }
1033
1034 rc = bithenge_subblob_expression(&offset, in_expr, offset,
1035 NULL, true);
1036 if (rc != EOK) {
1037 error_errno(state, rc);
1038 return NULL;
1039 }
1040
1041 rc = bithenge_expression_transform(&offset_xform, offset);
1042 if (rc != EOK) {
1043 error_errno(state, rc);
1044 return NULL;
1045 }
1046 }
1047 expect(state, '{');
1048 bithenge_transform_t *xform = parse_transform(state);
1049 expect(state, '}');
1050 if (state->error != EOK) {
1051 bithenge_transform_dec_ref(offset_xform);
1052 bithenge_transform_dec_ref(xform);
1053 return NULL;
1054 }
1055
1056 int rc = bithenge_partial_transform(&xform, xform);
1057 if (rc != EOK) {
1058 error_errno(state, rc);
1059 bithenge_transform_dec_ref(offset_xform);
1060 return NULL;
1061 }
1062
1063 if (offset_xform) {
1064 bithenge_transform_t **xforms = malloc(2 * sizeof(*xforms));
1065 if (!xforms) {
1066 error_errno(state, ENOMEM);
1067 bithenge_transform_dec_ref(xform);
1068 bithenge_transform_dec_ref(offset_xform);
1069 return NULL;
1070 }
1071 xforms[0] = xform;
1072 xforms[1] = offset_xform;
1073 rc = bithenge_new_composed_transform(&xform, xforms, 2);
1074 if (rc != EOK) {
1075 error_errno(state, rc);
1076 return NULL;
1077 }
1078 }
1079
1080 return xform;
1081}
1082
1083/* The TOKEN_STRUCT and '{' must already have been skipped. */
1084static bithenge_transform_t *parse_struct(state_t *state)
1085{
1086 size_t num = 0;
1087 bithenge_named_transform_t *subxforms;
1088 /* We keep an extra space for the {NULL, NULL} terminator. */
1089 subxforms = state_malloc(state, sizeof(*subxforms));
1090 while (state->error == EOK && state->token != '}') {
1091 if (state->token == TOKEN_IF) {
1092 subxforms[num].transform = parse_if(state, true);
1093 subxforms[num].name = NULL;
1094 } else if (state->token == TOKEN_SWITCH) {
1095 subxforms[num].transform = parse_switch(state, true);
1096 subxforms[num].name = NULL;
1097 } else {
1098 if (state->token == '.') {
1099 next_token(state);
1100 subxforms[num].name = expect_identifier(state);
1101 } else {
1102 subxforms[num].name = NULL;
1103 }
1104 expect(state, TOKEN_LEFT_ARROW);
1105 subxforms[num].transform = parse_transform(state);
1106 expect(state, ';');
1107 }
1108 num++;
1109 subxforms = state_realloc(state, subxforms,
1110 (num + 1)*sizeof(*subxforms));
1111 }
1112
1113 if (state->error != EOK) {
1114 while (num--) {
1115 free((void *)subxforms[num].name);
1116 bithenge_transform_dec_ref(subxforms[num].transform);
1117 }
1118 free(subxforms);
1119 return NULL;
1120 }
1121
1122 subxforms[num].name = NULL;
1123 subxforms[num].transform = NULL;
1124 bithenge_transform_t *result;
1125 int rc = bithenge_new_struct(&result, subxforms);
1126 if (rc != EOK) {
1127 error_errno(state, rc);
1128 return NULL;
1129 }
1130 return result;
1131}
1132
1133/** Parse a transform without composition.
1134 * @return The parsed transform, or NULL if an error occurred. */
1135static bithenge_transform_t *parse_transform_no_compose(state_t *state)
1136{
1137 if (state->token == '(') {
1138 next_token(state);
1139 state->in_node_used = false;
1140 bithenge_expression_t *expr = parse_expression(state);
1141 expect(state, ')');
1142 if (state->error != EOK) {
1143 bithenge_expression_dec_ref(expr);
1144 return NULL;
1145 }
1146
1147 bithenge_transform_t *xform;
1148 int rc;
1149 if (state->in_node_used)
1150 rc = bithenge_expression_transform(&xform, expr);
1151 else
1152 rc = bithenge_inputless_transform(&xform, expr);
1153 if (rc != EOK) {
1154 error_errno(state, rc);
1155 return NULL;
1156 }
1157 return xform;
1158 } else if (state->token == TOKEN_DO) {
1159 return parse_do_while(state);
1160 } else if (state->token == TOKEN_IDENTIFIER) {
1161 return parse_invocation(state);
1162 } else if (state->token == TOKEN_IF) {
1163 return parse_if(state, false);
1164 } else if (state->token == TOKEN_PARTIAL) {
1165 return parse_partial(state);
1166 } else if (state->token == TOKEN_REPEAT) {
1167 return parse_repeat(state);
1168 } else if (state->token == TOKEN_STRUCT) {
1169 next_token(state);
1170 expect(state, '{');
1171 bithenge_transform_t *xform = parse_struct(state);
1172 expect(state, '}');
1173 return xform;
1174 } else if (state->token == TOKEN_SWITCH) {
1175 return parse_switch(state, false);
1176 } else {
1177 syntax_error(state, "unexpected (transform expected)");
1178 return NULL;
1179 }
1180}
1181
1182/** Parse a transform.
1183 * @return The parsed transform, or NULL if an error occurred. */
1184static bithenge_transform_t *parse_transform(state_t *state)
1185{
1186 bithenge_transform_t *result = parse_transform_no_compose(state);
1187 bithenge_transform_t **xforms = NULL;
1188 size_t num = 1;
1189 while (state->token == TOKEN_LEFT_ARROW) {
1190 expect(state, TOKEN_LEFT_ARROW);
1191 xforms = state_realloc(state, xforms,
1192 (num + 1) * sizeof(*xforms));
1193 if (state->error != EOK)
1194 break;
1195 xforms[num++] = parse_transform_no_compose(state);
1196 }
1197 if (state->error != EOK) {
1198 while (xforms && num > 1)
1199 bithenge_transform_dec_ref(xforms[--num]);
1200 free(xforms);
1201 bithenge_transform_dec_ref(result);
1202 return NULL;
1203 }
1204 if (xforms) {
1205 xforms[0] = result;
1206 int rc = bithenge_new_composed_transform(&result, xforms, num);
1207 if (rc != EOK) {
1208 error_errno(state, rc);
1209 return NULL;
1210 }
1211 }
1212 return result;
1213}
1214
1215/** Parse a definition. */
1216static void parse_definition(state_t *state)
1217{
1218 expect(state, TOKEN_TRANSFORM);
1219 char *name = expect_identifier(state);
1220
1221 if (state->token == '(') {
1222 next_token(state);
1223 while (state->error == EOK && state->token != ')') {
1224 if (state->num_params)
1225 expect(state, ',');
1226 state->parameter_names = state_realloc(state,
1227 state->parameter_names,
1228 (state->num_params + 1)*sizeof(*state->parameter_names));
1229 if (state->error != EOK)
1230 break;
1231 state->parameter_names[state->num_params++] =
1232 expect_identifier(state);
1233 }
1234 expect(state, ')');
1235 }
1236
1237 bithenge_transform_t *barrier = NULL;
1238 if (state->error == EOK) {
1239 int rc = bithenge_new_barrier_transform(&barrier,
1240 state->num_params);
1241 if (rc != EOK) {
1242 barrier = NULL;
1243 error_errno(state, rc);
1244 }
1245 }
1246
1247 add_named_transform(state, barrier, name);
1248
1249 expect(state, '=');
1250 bithenge_transform_t *xform = parse_transform(state);
1251 expect(state, ';');
1252
1253 if (state->error == EOK) {
1254 int rc = bithenge_barrier_transform_set_subtransform(barrier,
1255 xform);
1256 xform = NULL;
1257 if (rc != EOK)
1258 error_errno(state, rc);
1259 }
1260
1261 if (state->error != EOK)
1262 bithenge_transform_dec_ref(xform);
1263
1264 for (int i = 0; i < state->num_params; i++)
1265 free(state->parameter_names[i]);
1266 free(state->parameter_names);
1267 state->parameter_names = NULL;
1268 state->num_params = 0;
1269}
1270
1271/** Initialize the state. */
1272static void state_init(state_t *state, const char *filename)
1273{
1274 state->error = EOK;
1275 state->transform_list = NULL;
1276 state->parameter_names = NULL;
1277 state->num_params = 0;
1278 state->token = TOKEN_ERROR;
1279 state->old_buffer_pos = state->buffer_pos = BUFFER_SIZE - 1;
1280 state->lineno = 1;
1281 state->line_offset = (int)-state->buffer_pos + 1;
1282 state->filename = filename;
1283 state->file = fopen(filename, "r");
1284 if (!state->file) {
1285 error_errno(state, errno);
1286 } else {
1287 next_token(state);
1288 }
1289}
1290
1291/** Destroy the state. */
1292static void state_destroy(state_t *state)
1293{
1294 done_with_token(state);
1295 state->token = TOKEN_ERROR;
1296 if (state->file)
1297 fclose(state->file);
1298 transform_list_t *entry = state->transform_list;
1299 while (entry) {
1300 transform_list_t *next = entry->next;
1301 free(entry->name);
1302 bithenge_transform_dec_ref(entry->transform);
1303 free(entry);
1304 entry = next;
1305 }
1306 for (int i = 0; i < state->num_params; i++)
1307 free(state->parameter_names[i]);
1308 free(state->parameter_names);
1309}
1310
1311/** Parse a script file.
1312 * @param filename The name of the script file.
1313 * @param[out] out Stores the "main" transform.
1314 * @return EOK on success, EINVAL on syntax error, or an error code from
1315 * errno.h. */
1316int bithenge_parse_script(const char *filename, bithenge_transform_t **out)
1317{
1318 state_t state;
1319 state_init(&state, filename);
1320 while (state.error == EOK && state.token != TOKEN_EOF)
1321 parse_definition(&state);
1322 *out = get_named_transform(&state, "main");
1323 int rc = state.error;
1324 state_destroy(&state);
1325 if (rc == EOK && !*out) {
1326 fprintf(stderr, "no \"main\" transform\n");
1327 rc = EINVAL;
1328 }
1329 return rc;
1330}
1331
1332/** @}
1333 */
Note: See TracBrowser for help on using the repository browser.