source: mainline/uspace/lib/bithenge/src/script.c@ 3bacee1

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

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