source: mainline/uspace/lib/bithenge/src/script.c@ 6ff23ff

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

Fix block comment formatting (ccheck).
  • 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
453
454/***************** Expressions *****************/
455
456/** @cond internal */
457typedef enum {
458 PRECEDENCE_NONE,
459 PRECEDENCE_AND,
460 PRECEDENCE_EQUALS,
461 PRECEDENCE_COMPARE,
462 PRECEDENCE_ADD,
463 PRECEDENCE_MULTIPLY,
464} precedence_t;
465/** @endcond */
466
467static bithenge_binary_op_t token_as_binary_operator(token_type_t token)
468{
469 switch ((int)token) {
470 case '+':
471 return BITHENGE_EXPRESSION_ADD;
472 case '-':
473 return BITHENGE_EXPRESSION_SUBTRACT;
474 case '*':
475 return BITHENGE_EXPRESSION_MULTIPLY;
476 case TOKEN_INTEGER_DIVIDE:
477 return BITHENGE_EXPRESSION_INTEGER_DIVIDE;
478 case '%':
479 return BITHENGE_EXPRESSION_MODULO;
480 case '<':
481 return BITHENGE_EXPRESSION_LESS_THAN;
482 case TOKEN_LESS_THAN_OR_EQUAL:
483 return BITHENGE_EXPRESSION_LESS_THAN_OR_EQUAL;
484 case '>':
485 return BITHENGE_EXPRESSION_GREATER_THAN;
486 case TOKEN_GREATER_THAN_OR_EQUAL:
487 return BITHENGE_EXPRESSION_GREATER_THAN_OR_EQUAL;
488 case TOKEN_EQUALS:
489 return BITHENGE_EXPRESSION_EQUALS;
490 case TOKEN_NOT_EQUAL:
491 return BITHENGE_EXPRESSION_NOT_EQUALS;
492 case TOKEN_AND:
493 return BITHENGE_EXPRESSION_AND;
494 case TOKEN_OR:
495 return BITHENGE_EXPRESSION_OR;
496 case TOKEN_CONCAT:
497 return BITHENGE_EXPRESSION_CONCAT;
498 default:
499 return BITHENGE_EXPRESSION_INVALID_BINARY_OP;
500 }
501}
502
503static precedence_t binary_operator_precedence(bithenge_binary_op_t op)
504{
505 switch (op) {
506 case BITHENGE_EXPRESSION_ADD: /* fallthrough */
507 case BITHENGE_EXPRESSION_SUBTRACT: /* fallthrough */
508 case BITHENGE_EXPRESSION_CONCAT:
509 return PRECEDENCE_ADD;
510 case BITHENGE_EXPRESSION_MULTIPLY: /* fallthrough */
511 case BITHENGE_EXPRESSION_INTEGER_DIVIDE: /* fallthrough */
512 case BITHENGE_EXPRESSION_MODULO:
513 return PRECEDENCE_MULTIPLY;
514 case BITHENGE_EXPRESSION_LESS_THAN: /* fallthrough */
515 case BITHENGE_EXPRESSION_LESS_THAN_OR_EQUAL: /* fallthrough */
516 case BITHENGE_EXPRESSION_GREATER_THAN: /* fallthrough */
517 case BITHENGE_EXPRESSION_GREATER_THAN_OR_EQUAL:
518 return PRECEDENCE_COMPARE;
519 case BITHENGE_EXPRESSION_EQUALS: /* fallthrough */
520 case BITHENGE_EXPRESSION_NOT_EQUALS:
521 return PRECEDENCE_EQUALS;
522 case BITHENGE_EXPRESSION_AND: /* fallthrough */
523 case BITHENGE_EXPRESSION_OR:
524 return PRECEDENCE_AND;
525 default:
526 assert(false);
527 return PRECEDENCE_NONE;
528 }
529}
530
531static bithenge_expression_t *parse_term(state_t *state)
532{
533 errno_t rc;
534 if (state->token == TOKEN_TRUE || state->token == TOKEN_FALSE) {
535 bool val = state->token == TOKEN_TRUE;
536 next_token(state);
537 bithenge_node_t *node;
538 rc = bithenge_new_boolean_node(&node, val);
539 if (rc != EOK) {
540 error_errno(state, rc);
541 return NULL;
542 }
543
544 bithenge_expression_t *expr;
545 rc = bithenge_const_expression(&expr, node);
546 if (rc != EOK) {
547 error_errno(state, rc);
548 return NULL;
549 }
550
551 return expr;
552 } else if (state->token == TOKEN_IN) {
553 next_token(state);
554 state->in_node_used = true;
555 bithenge_expression_t *expr;
556 rc = bithenge_in_node_expression(&expr);
557 if (rc != EOK) {
558 error_errno(state, rc);
559 return NULL;
560 }
561 return expr;
562 } else if (state->token == TOKEN_INTEGER) {
563 bithenge_int_t val = state->token_int;
564 next_token(state);
565 bithenge_node_t *node;
566 rc = bithenge_new_integer_node(&node, val);
567 if (rc != EOK) {
568 error_errno(state, rc);
569 return NULL;
570 }
571
572 bithenge_expression_t *expr;
573 rc = bithenge_const_expression(&expr, node);
574 if (rc != EOK) {
575 error_errno(state, rc);
576 return NULL;
577 }
578
579 return expr;
580 } else if (state->token == TOKEN_IDENTIFIER) {
581 int i;
582 for (i = 0; i < state->num_params; i++)
583 if (!str_cmp(state->parameter_names[i],
584 state->token_string))
585 break;
586
587 if (i == state->num_params) {
588 syntax_error(state, "unknown identifier");
589 return NULL;
590 }
591
592 next_token(state);
593
594 bithenge_expression_t *expr;
595 rc = bithenge_param_expression(&expr, i);
596 if (rc != EOK) {
597 error_errno(state, rc);
598 return NULL;
599 }
600 return expr;
601 } else if (state->token == '.') {
602 next_token(state);
603
604 const char *id = expect_identifier(state);
605 bithenge_node_t *key = NULL;
606 bithenge_expression_t *expr = NULL;
607
608 if (state->error == EOK) {
609 rc = bithenge_new_string_node(&key, id, true);
610 id = NULL;
611 error_errno(state, rc);
612 }
613
614 if (state->error == EOK) {
615 rc = bithenge_scope_member_expression(&expr, key);
616 key = NULL;
617 if (rc != EOK)
618 expr = NULL;
619 error_errno(state, rc);
620 }
621
622 if (state->error != EOK) {
623 free((char *)id);
624 bithenge_node_dec_ref(key);
625 bithenge_expression_dec_ref(expr);
626 return NULL;
627 }
628
629 return expr;
630 } else if (state->token == '(') {
631 next_token(state);
632 bithenge_expression_t *expr = parse_expression(state);
633 expect(state, ')');
634 return expr;
635 } else {
636 syntax_error(state, "expression expected");
637 return NULL;
638 }
639}
640
641static bithenge_expression_t *parse_postfix_expression(state_t *state)
642{
643 errno_t rc;
644 bithenge_expression_t *expr = parse_term(state);
645 while (state->error == EOK) {
646 if (state->token == '.') {
647 next_token(state);
648
649 const char *id = expect_identifier(state);
650
651 if (state->error != EOK) {
652 free((char *)id);
653 bithenge_expression_dec_ref(expr);
654 return NULL;
655 }
656
657 bithenge_node_t *key = NULL;
658 rc = bithenge_new_string_node(&key, id, true);
659 if (rc != EOK) {
660 error_errno(state, rc);
661 bithenge_expression_dec_ref(expr);
662 return NULL;
663 }
664
665 bithenge_expression_t *key_expr;
666 rc = bithenge_const_expression(&key_expr, key);
667 if (rc != EOK) {
668 error_errno(state, rc);
669 bithenge_expression_dec_ref(expr);
670 return NULL;
671 }
672
673 rc = bithenge_binary_expression(&expr,
674 BITHENGE_EXPRESSION_MEMBER, expr, key_expr);
675 if (rc != EOK) {
676 error_errno(state, rc);
677 return NULL;
678 }
679 } else if (state->token == '[') {
680 next_token(state);
681 bithenge_expression_t *start = parse_expression(state);
682 bool absolute_limit = false;
683 if (state->token == ',' || state->token == ':') {
684 absolute_limit = state->token == ':';
685 next_token(state);
686 bithenge_expression_t *limit = NULL;
687 if (!(state->token == ']' && absolute_limit))
688 limit = parse_expression(state);
689 expect(state, ']');
690
691 if (state->error != EOK) {
692 bithenge_expression_dec_ref(expr);
693 bithenge_expression_dec_ref(start);
694 bithenge_expression_dec_ref(limit);
695 return NULL;
696 }
697 rc = bithenge_subblob_expression(&expr, expr, start,
698 limit, absolute_limit);
699 if (rc != EOK) {
700 error_errno(state, rc);
701 return NULL;
702 }
703 } else if (state->token == ']') {
704 next_token(state);
705
706 if (state->error != EOK) {
707 bithenge_expression_dec_ref(expr);
708 bithenge_expression_dec_ref(start);
709 return NULL;
710 }
711 rc = bithenge_binary_expression(&expr,
712 BITHENGE_EXPRESSION_MEMBER, expr, start);
713 if (rc != EOK) {
714 error_errno(state, rc);
715 return NULL;
716 }
717 } else {
718 syntax_error(state, "expected ',', ':', or ']'");
719 bithenge_expression_dec_ref(expr);
720 bithenge_expression_dec_ref(start);
721 return NULL;
722 }
723 } else {
724 break;
725 }
726 }
727 return expr;
728}
729
730static bithenge_expression_t *parse_expression_precedence(state_t *state,
731 precedence_t prev_precedence)
732{
733 bithenge_expression_t *expr = parse_postfix_expression(state);
734 while (state->error == EOK) {
735 bithenge_binary_op_t op =
736 token_as_binary_operator(state->token);
737 if (op == BITHENGE_EXPRESSION_INVALID_BINARY_OP)
738 break;
739 precedence_t precedence = binary_operator_precedence(op);
740 if (precedence <= prev_precedence)
741 break;
742 next_token(state);
743
744 bithenge_expression_t *expr2 =
745 parse_expression_precedence(state, precedence);
746 if (state->error != EOK) {
747 bithenge_expression_dec_ref(expr2);
748 break;
749 }
750 errno_t rc = bithenge_binary_expression(&expr, op, expr, expr2);
751 if (rc != EOK) {
752 expr = NULL;
753 error_errno(state, rc);
754 }
755 }
756 if (state->error != EOK) {
757 bithenge_expression_dec_ref(expr);
758 expr = NULL;
759 }
760 return expr;
761}
762
763static bithenge_expression_t *parse_expression(state_t *state)
764{
765 return parse_expression_precedence(state, PRECEDENCE_NONE);
766}
767
768
769
770/* state->token must be TOKEN_IDENTIFIER when this is called. */
771static bithenge_transform_t *parse_invocation(state_t *state)
772{
773 bithenge_transform_t *result = get_named_transform(state,
774 state->token_string);
775 if (!result)
776 syntax_error(state, "transform not found");
777 next_token(state);
778
779 bithenge_expression_t **params = NULL;
780 int num_params = 0;
781 if (state->token == '(') {
782 next_token(state);
783 while (state->error == EOK && state->token != ')') {
784 if (num_params)
785 expect(state, ',');
786 params = state_realloc(state, params,
787 (num_params + 1) * sizeof(*params));
788 if (state->error != EOK)
789 break;
790 params[num_params] = parse_expression(state);
791 num_params++;
792 }
793 expect(state, ')');
794 }
795
796 /* TODO: show correct error position */
797 if (state->error == EOK &&
798 bithenge_transform_num_params(result) != num_params)
799 syntax_error(state, "incorrect number of parameters before");
800
801 if (state->error != EOK) {
802 while (num_params--)
803 bithenge_expression_dec_ref(params[num_params]);
804 free(params);
805 bithenge_transform_dec_ref(result);
806 return NULL;
807 }
808
809 if (num_params) {
810 errno_t rc = bithenge_param_wrapper(&result, result, params);
811 if (rc != EOK) {
812 error_errno(state, rc);
813 result = NULL;
814 }
815 }
816
817 return result;
818}
819
820/** Create a transform that just produces an empty node.
821 * @param state The parser state.
822 * @return The new transform, or NULL on error.
823 */
824static bithenge_transform_t *make_empty_transform(state_t *state)
825{
826 bithenge_node_t *node;
827 errno_t rc = bithenge_new_empty_internal_node(&node);
828 if (rc != EOK) {
829 error_errno(state, rc);
830 return NULL;
831 }
832
833 bithenge_expression_t *expr;
834 rc = bithenge_const_expression(&expr, node);
835 if (rc != EOK) {
836 error_errno(state, rc);
837 return NULL;
838 }
839
840 bithenge_transform_t *xform;
841 rc = bithenge_inputless_transform(&xform, expr);
842 if (rc != EOK) {
843 error_errno(state, rc);
844 return NULL;
845 }
846
847 return xform;
848}
849
850static bithenge_transform_t *parse_if(state_t *state, bool in_struct)
851{
852 expect(state, TOKEN_IF);
853 expect(state, '(');
854 bithenge_expression_t *expr = parse_expression(state);
855 expect(state, ')');
856 expect(state, '{');
857 bithenge_transform_t *true_xform =
858 in_struct ? parse_struct(state) : parse_transform(state);
859 expect(state, '}');
860
861 bithenge_transform_t *false_xform = NULL;
862 if (state->token == TOKEN_ELSE) {
863 next_token(state);
864 expect(state, '{');
865 false_xform =
866 in_struct ? parse_struct(state) : parse_transform(state);
867 expect(state, '}');
868 } else {
869 if (in_struct)
870 false_xform = make_empty_transform(state);
871 else
872 syntax_error(state, "else expected");
873 }
874
875 if (state->error != EOK) {
876 bithenge_expression_dec_ref(expr);
877 bithenge_transform_dec_ref(true_xform);
878 bithenge_transform_dec_ref(false_xform);
879 return NULL;
880 }
881
882 bithenge_transform_t *if_xform;
883 errno_t rc = bithenge_if_transform(&if_xform, expr, true_xform,
884 false_xform);
885 if (rc != EOK) {
886 error_errno(state, rc);
887 return NULL;
888 }
889 return if_xform;
890}
891
892static bithenge_transform_t *parse_switch(state_t *state, bool in_struct)
893{
894 expect(state, TOKEN_SWITCH);
895 expect(state, '(');
896 bithenge_expression_t *ref_expr = parse_expression(state);
897 expect(state, ')');
898 expect(state, '{');
899 int num = 0;
900 bithenge_expression_t **exprs = NULL;
901 bithenge_transform_t **xforms = NULL;
902 while (state->error == EOK && state->token != '}') {
903 bithenge_expression_t *expr;
904 if (state->token == TOKEN_ELSE) {
905 next_token(state);
906 bithenge_node_t *node;
907 errno_t rc = bithenge_new_boolean_node(&node, true);
908 if (rc != EOK) {
909 error_errno(state, rc);
910 break;
911 }
912 rc = bithenge_const_expression(&expr, node);
913 if (rc != EOK) {
914 error_errno(state, rc);
915 break;
916 }
917 } else {
918 expr = parse_expression(state);
919 if (state->error == EOK) {
920 bithenge_expression_inc_ref(ref_expr);
921 errno_t rc = bithenge_binary_expression(&expr,
922 BITHENGE_EXPRESSION_EQUALS, ref_expr,
923 expr);
924 if (rc != EOK) {
925 error_errno(state, rc);
926 break;
927 }
928 }
929 }
930
931 expect(state, ':');
932 bithenge_transform_t *xform;
933 if (in_struct) {
934 expect(state, '{');
935 xform = parse_struct(state);
936 expect(state, '}');
937 } else
938 xform = parse_transform(state);
939 expect(state, ';');
940
941 exprs = state_realloc(state, exprs,
942 sizeof(*exprs) * (num + 1));
943 xforms = state_realloc(state, xforms,
944 sizeof(*xforms) * (num + 1));
945 if (state->error != EOK) {
946 bithenge_expression_dec_ref(expr);
947 bithenge_transform_dec_ref(xform);
948 break;
949 }
950
951 exprs[num] = expr;
952 xforms[num] = xform;
953 num++;
954 }
955 bithenge_expression_dec_ref(ref_expr);
956
957 bithenge_transform_t *switch_xform = &bithenge_invalid_transform;
958 bithenge_transform_inc_ref(switch_xform);
959 while (state->error == EOK && num >= 1) {
960 num--;
961 errno_t rc = bithenge_if_transform(&switch_xform, exprs[num],
962 xforms[num], switch_xform);
963 if (rc != EOK) {
964 switch_xform = NULL;
965 error_errno(state, rc);
966 }
967 }
968
969 while (num >= 1) {
970 num--;
971 bithenge_expression_dec_ref(exprs[num]);
972 bithenge_transform_dec_ref(xforms[num]);
973 }
974 free(exprs);
975 free(xforms);
976
977 expect(state, '}');
978 return switch_xform;
979}
980
981static bithenge_transform_t *parse_repeat(state_t *state)
982{
983 expect(state, TOKEN_REPEAT);
984 bithenge_expression_t *expr = NULL;
985 if (state->token == '(') {
986 next_token(state);
987 expr = parse_expression(state);
988 expect(state, ')');
989 }
990 expect(state, '{');
991 bithenge_transform_t *xform = parse_transform(state);
992 expect(state, '}');
993
994 if (state->error != EOK) {
995 bithenge_expression_dec_ref(expr);
996 bithenge_transform_dec_ref(xform);
997 return NULL;
998 }
999
1000 bithenge_transform_t *repeat_xform;
1001 errno_t rc = bithenge_repeat_transform(&repeat_xform, xform, expr);
1002 if (rc != EOK) {
1003 error_errno(state, rc);
1004 return NULL;
1005 }
1006 return repeat_xform;
1007}
1008
1009static bithenge_transform_t *parse_do_while(state_t *state)
1010{
1011 expect(state, TOKEN_DO);
1012 expect(state, '{');
1013 bithenge_transform_t *xform = parse_transform(state);
1014 expect(state, '}');
1015 expect(state, TOKEN_WHILE);
1016 expect(state, '(');
1017 bithenge_expression_t *expr = parse_expression(state);
1018 expect(state, ')');
1019
1020 if (state->error != EOK) {
1021 bithenge_expression_dec_ref(expr);
1022 bithenge_transform_dec_ref(xform);
1023 return NULL;
1024 }
1025
1026 bithenge_transform_t *do_while_xform;
1027 errno_t rc = bithenge_do_while_transform(&do_while_xform, xform, expr);
1028 if (rc != EOK) {
1029 error_errno(state, rc);
1030 return NULL;
1031 }
1032 return do_while_xform;
1033}
1034
1035static bithenge_transform_t *parse_partial(state_t *state)
1036{
1037 expect(state, TOKEN_PARTIAL);
1038 bithenge_transform_t *offset_xform = NULL;
1039 if (state->token == '(') {
1040 next_token(state);
1041 bithenge_expression_t *offset = parse_expression(state);
1042 expect(state, ')');
1043
1044 bithenge_expression_t *in_expr;
1045 errno_t rc = bithenge_in_node_expression(&in_expr);
1046 if (rc != EOK)
1047 error_errno(state, rc);
1048 if (state->error != EOK) {
1049 bithenge_expression_dec_ref(offset);
1050 return NULL;
1051 }
1052
1053 rc = bithenge_subblob_expression(&offset, in_expr, offset,
1054 NULL, true);
1055 if (rc != EOK) {
1056 error_errno(state, rc);
1057 return NULL;
1058 }
1059
1060 rc = bithenge_expression_transform(&offset_xform, offset);
1061 if (rc != EOK) {
1062 error_errno(state, rc);
1063 return NULL;
1064 }
1065 }
1066 expect(state, '{');
1067 bithenge_transform_t *xform = parse_transform(state);
1068 expect(state, '}');
1069 if (state->error != EOK) {
1070 bithenge_transform_dec_ref(offset_xform);
1071 bithenge_transform_dec_ref(xform);
1072 return NULL;
1073 }
1074
1075 errno_t rc = bithenge_partial_transform(&xform, xform);
1076 if (rc != EOK) {
1077 error_errno(state, rc);
1078 bithenge_transform_dec_ref(offset_xform);
1079 return NULL;
1080 }
1081
1082 if (offset_xform) {
1083 bithenge_transform_t **xforms = malloc(2 * sizeof(*xforms));
1084 if (!xforms) {
1085 error_errno(state, ENOMEM);
1086 bithenge_transform_dec_ref(xform);
1087 bithenge_transform_dec_ref(offset_xform);
1088 return NULL;
1089 }
1090 xforms[0] = xform;
1091 xforms[1] = offset_xform;
1092 rc = bithenge_new_composed_transform(&xform, xforms, 2);
1093 if (rc != EOK) {
1094 error_errno(state, rc);
1095 return NULL;
1096 }
1097 }
1098
1099 return xform;
1100}
1101
1102/* The TOKEN_STRUCT and '{' must already have been skipped. */
1103static bithenge_transform_t *parse_struct(state_t *state)
1104{
1105 size_t num = 0;
1106 bithenge_named_transform_t *subxforms;
1107 /* We keep an extra space for the {NULL, NULL} terminator. */
1108 subxforms = state_malloc(state, sizeof(*subxforms));
1109 while (state->error == EOK && state->token != '}') {
1110 if (state->token == TOKEN_IF) {
1111 subxforms[num].transform = parse_if(state, true);
1112 subxforms[num].name = NULL;
1113 } else if (state->token == TOKEN_SWITCH) {
1114 subxforms[num].transform = parse_switch(state, true);
1115 subxforms[num].name = NULL;
1116 } else {
1117 if (state->token == '.') {
1118 next_token(state);
1119 subxforms[num].name = expect_identifier(state);
1120 } else {
1121 subxforms[num].name = NULL;
1122 }
1123 expect(state, TOKEN_LEFT_ARROW);
1124 subxforms[num].transform = parse_transform(state);
1125 expect(state, ';');
1126 }
1127 num++;
1128 subxforms = state_realloc(state, subxforms,
1129 (num + 1) * sizeof(*subxforms));
1130 }
1131
1132 if (state->error != EOK) {
1133 while (num--) {
1134 free((void *)subxforms[num].name);
1135 bithenge_transform_dec_ref(subxforms[num].transform);
1136 }
1137 free(subxforms);
1138 return NULL;
1139 }
1140
1141 subxforms[num].name = NULL;
1142 subxforms[num].transform = NULL;
1143 bithenge_transform_t *result;
1144 errno_t rc = bithenge_new_struct(&result, subxforms);
1145 if (rc != EOK) {
1146 error_errno(state, rc);
1147 return NULL;
1148 }
1149 return result;
1150}
1151
1152/** Parse a transform without composition.
1153 * @return The parsed transform, or NULL if an error occurred.
1154 */
1155static bithenge_transform_t *parse_transform_no_compose(state_t *state)
1156{
1157 if (state->token == '(') {
1158 next_token(state);
1159 state->in_node_used = false;
1160 bithenge_expression_t *expr = parse_expression(state);
1161 expect(state, ')');
1162 if (state->error != EOK) {
1163 bithenge_expression_dec_ref(expr);
1164 return NULL;
1165 }
1166
1167 bithenge_transform_t *xform;
1168 errno_t rc;
1169 if (state->in_node_used)
1170 rc = bithenge_expression_transform(&xform, expr);
1171 else
1172 rc = bithenge_inputless_transform(&xform, expr);
1173 if (rc != EOK) {
1174 error_errno(state, rc);
1175 return NULL;
1176 }
1177 return xform;
1178 } else if (state->token == TOKEN_DO) {
1179 return parse_do_while(state);
1180 } else if (state->token == TOKEN_IDENTIFIER) {
1181 return parse_invocation(state);
1182 } else if (state->token == TOKEN_IF) {
1183 return parse_if(state, false);
1184 } else if (state->token == TOKEN_PARTIAL) {
1185 return parse_partial(state);
1186 } else if (state->token == TOKEN_REPEAT) {
1187 return parse_repeat(state);
1188 } else if (state->token == TOKEN_STRUCT) {
1189 next_token(state);
1190 expect(state, '{');
1191 bithenge_transform_t *xform = parse_struct(state);
1192 expect(state, '}');
1193 return xform;
1194 } else if (state->token == TOKEN_SWITCH) {
1195 return parse_switch(state, false);
1196 } else {
1197 syntax_error(state, "unexpected (transform expected)");
1198 return NULL;
1199 }
1200}
1201
1202/** Parse a transform.
1203 * @return The parsed transform, or NULL if an error occurred.
1204 */
1205static bithenge_transform_t *parse_transform(state_t *state)
1206{
1207 bithenge_transform_t *result = parse_transform_no_compose(state);
1208 bithenge_transform_t **xforms = NULL;
1209 size_t num = 1;
1210 while (state->token == TOKEN_LEFT_ARROW) {
1211 expect(state, TOKEN_LEFT_ARROW);
1212 xforms = state_realloc(state, xforms,
1213 (num + 1) * sizeof(*xforms));
1214 if (state->error != EOK)
1215 break;
1216 xforms[num++] = parse_transform_no_compose(state);
1217 }
1218 if (state->error != EOK) {
1219 while (xforms && num > 1)
1220 bithenge_transform_dec_ref(xforms[--num]);
1221 free(xforms);
1222 bithenge_transform_dec_ref(result);
1223 return NULL;
1224 }
1225 if (xforms) {
1226 xforms[0] = result;
1227 errno_t rc = bithenge_new_composed_transform(&result, xforms, num);
1228 if (rc != EOK) {
1229 error_errno(state, rc);
1230 return NULL;
1231 }
1232 }
1233 return result;
1234}
1235
1236/** Parse a definition. */
1237static void parse_definition(state_t *state)
1238{
1239 expect(state, TOKEN_TRANSFORM);
1240 char *name = expect_identifier(state);
1241
1242 if (state->token == '(') {
1243 next_token(state);
1244 while (state->error == EOK && state->token != ')') {
1245 if (state->num_params)
1246 expect(state, ',');
1247 state->parameter_names = state_realloc(state,
1248 state->parameter_names,
1249 (state->num_params + 1) * sizeof(*state->parameter_names));
1250 if (state->error != EOK)
1251 break;
1252 state->parameter_names[state->num_params++] =
1253 expect_identifier(state);
1254 }
1255 expect(state, ')');
1256 }
1257
1258 bithenge_transform_t *barrier = NULL;
1259 if (state->error == EOK) {
1260 errno_t rc = bithenge_new_barrier_transform(&barrier,
1261 state->num_params);
1262 if (rc != EOK) {
1263 barrier = NULL;
1264 error_errno(state, rc);
1265 }
1266 }
1267
1268 add_named_transform(state, barrier, name);
1269
1270 expect(state, '=');
1271 bithenge_transform_t *xform = parse_transform(state);
1272 expect(state, ';');
1273
1274 if (state->error == EOK) {
1275 errno_t rc = bithenge_barrier_transform_set_subtransform(barrier,
1276 xform);
1277 xform = NULL;
1278 if (rc != EOK)
1279 error_errno(state, rc);
1280 }
1281
1282 if (state->error != EOK)
1283 bithenge_transform_dec_ref(xform);
1284
1285 for (int i = 0; i < state->num_params; i++)
1286 free(state->parameter_names[i]);
1287 free(state->parameter_names);
1288 state->parameter_names = NULL;
1289 state->num_params = 0;
1290}
1291
1292/** Initialize the state. */
1293static void state_init(state_t *state, const char *filename)
1294{
1295 state->error = EOK;
1296 state->transform_list = NULL;
1297 state->parameter_names = NULL;
1298 state->num_params = 0;
1299 state->token = TOKEN_ERROR;
1300 state->old_buffer_pos = state->buffer_pos = BUFFER_SIZE - 1;
1301 state->lineno = 1;
1302 state->line_offset = (int)-state->buffer_pos + 1;
1303 state->filename = filename;
1304 state->file = fopen(filename, "r");
1305 if (!state->file) {
1306 error_errno(state, errno);
1307 } else {
1308 next_token(state);
1309 }
1310}
1311
1312/** Destroy the state. */
1313static void state_destroy(state_t *state)
1314{
1315 done_with_token(state);
1316 state->token = TOKEN_ERROR;
1317 if (state->file)
1318 fclose(state->file);
1319 transform_list_t *entry = state->transform_list;
1320 while (entry) {
1321 transform_list_t *next = entry->next;
1322 free(entry->name);
1323 bithenge_transform_dec_ref(entry->transform);
1324 free(entry);
1325 entry = next;
1326 }
1327 for (int i = 0; i < state->num_params; i++)
1328 free(state->parameter_names[i]);
1329 free(state->parameter_names);
1330}
1331
1332/** Parse a script file.
1333 * @param filename The name of the script file.
1334 * @param[out] out Stores the "main" transform.
1335 * @return EOK on success, EINVAL on syntax error, or an error code from
1336 * errno.h.
1337 */
1338errno_t bithenge_parse_script(const char *filename, bithenge_transform_t **out)
1339{
1340 state_t state;
1341 state_init(&state, filename);
1342 while (state.error == EOK && state.token != TOKEN_EOF)
1343 parse_definition(&state);
1344 *out = get_named_transform(&state, "main");
1345 errno_t rc = state.error;
1346 state_destroy(&state);
1347 if (rc == EOK && !*out) {
1348 fprintf(stderr, "no \"main\" transform\n");
1349 rc = EINVAL;
1350 }
1351 return rc;
1352}
1353
1354/** @}
1355 */
Note: See TracBrowser for help on using the repository browser.