source: mainline/uspace/lib/bithenge/src/script.c@ 09ab0a9a

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since 09ab0a9a was 09ab0a9a, checked in by Jiri Svoboda <jiri@…>, 7 years ago

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