source: mainline/uspace/lib/bithenge/script.c@ 1c79996

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

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