source: mainline/uspace/app/bithenge/script.c@ f85ca3f

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

Bithenge: add expressions that use the current node being created
  • Property mode set to 100644
File size: 17.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 "expression.h"
41#include "os.h"
42#include "script.h"
43#include "transform.h"
44#include "tree.h"
45
46/** Tokens with more characters than this may be read incorrectly. */
47#define MAX_TOKEN_SIZE 256
48#define BUFFER_SIZE 4096
49
50/** Single-character symbols are represented by the character itself. Every
51 * other token uses one of these values: */
52typedef enum {
53 TOKEN_ERROR = -128,
54 TOKEN_EOF,
55 TOKEN_IDENTIFIER,
56 TOKEN_INTEGER,
57 TOKEN_LEFT_ARROW,
58
59 /* Keywords */
60 TOKEN_STRUCT,
61 TOKEN_TRANSFORM,
62} token_type_t;
63
64/** Singly-linked list of named transforms. */
65typedef struct transform_list {
66 char *name;
67 bithenge_transform_t *transform;
68 struct transform_list *next;
69} transform_list_t;
70
71/** State kept by the parser. */
72typedef struct {
73 /** Rather than constantly checking return values, the parser uses this
74 * to indicate whether an error has occurred. */
75 int error;
76
77 /** The list of named transforms. */
78 transform_list_t *transform_list;
79
80 /** The name of the script file. */
81 const char *filename;
82 /** The script file being read from. */
83 FILE *file;
84 /** The buffer that holds script code. There is always a '\0' after the
85 * current position to prevent reading too far. */
86 char buffer[BUFFER_SIZE];
87 /** The start position within the buffer of the next unread token. */
88 size_t buffer_pos;
89 /** The start position within the buffer of the current token. */
90 size_t old_buffer_pos;
91 /** The line number of the current token. */
92 int lineno;
93 /** Added to a buffer position to find the column number. */
94 int line_offset;
95
96 /** The type of the current token. */
97 token_type_t token;
98 union {
99 /** The value of a TOKEN_IDENTIFIER token. Unless changed to
100 * NULL, it will be freed when the next token is read. */
101 char *token_string;
102 /** The value of a TOKEN_INTEGER token. */
103 bithenge_int_t token_int;
104 };
105
106 /** The names of the current transform's parameters. */
107 char **parameter_names;
108 /** The number of parameters. */
109 int num_params;
110} state_t;
111
112/** Free the previous token's data. This must be called before changing
113 * state->token. */
114static void done_with_token(state_t *state)
115{
116 if (state->token == TOKEN_IDENTIFIER)
117 free(state->token_string);
118 state->token = TOKEN_ERROR;
119}
120
121/** Note that an error has occurred if error is not EOK. */
122static void error_errno(state_t *state, int error)
123{
124 // Don't overwrite a previous error.
125 if (state->error == EOK && error != EOK) {
126 done_with_token(state);
127 state->token = TOKEN_ERROR;
128 state->error = error;
129 }
130}
131
132/** Note that a syntax error has occurred and print an error message. */
133static void syntax_error(state_t *state, const char *message)
134{
135 // Printing multiple errors is confusing.
136 if (state->error == EOK) {
137 size_t start_char = state->old_buffer_pos + state->line_offset;
138 size_t end_char = state->buffer_pos + state->line_offset;
139 size_t size = end_char - start_char;
140 fprintf(stderr, "%s:%d:", state->filename, state->lineno);
141 if (size <= 1)
142 fprintf(stderr, "%zd: ", start_char);
143 else
144 fprintf(stderr, "%zd-%zd: ", start_char, end_char - 1);
145 fprintf(stderr, "%s: \"%.*s\"\n", message, (int)size,
146 state->buffer + state->old_buffer_pos);
147 error_errno(state, EINVAL);
148 }
149}
150
151/** Ensure the buffer contains enough characters to read a token. */
152static void fill_buffer(state_t *state)
153{
154 if (state->buffer_pos + MAX_TOKEN_SIZE < BUFFER_SIZE)
155 return;
156
157 size_t empty_size = state->buffer_pos;
158 size_t used_size = BUFFER_SIZE - 1 - state->buffer_pos;
159 memmove(state->buffer, state->buffer + state->buffer_pos, used_size);
160 state->line_offset += state->buffer_pos;
161 state->buffer_pos = 0;
162
163 size_t read_size = fread(state->buffer + used_size, 1, empty_size,
164 state->file);
165 if (ferror(state->file))
166 error_errno(state, EIO);
167 state->buffer[used_size + read_size] = '\0';
168}
169
170/** Read the next token. */
171static void next_token(state_t *state)
172{
173 fill_buffer(state);
174 done_with_token(state);
175 state->old_buffer_pos = state->buffer_pos;
176 char ch = state->buffer[state->buffer_pos];
177 if (ch == '\0') {
178 state->token = TOKEN_EOF;
179 } else if (ch == '#') {
180 while (state->buffer[state->buffer_pos] != '\n'
181 && state->buffer[state->buffer_pos] != '\0') {
182 state->buffer_pos++;
183 fill_buffer(state);
184 }
185 next_token(state);
186 return;
187 } else if (isspace(ch)) {
188 // Will eventually reach the '\0' at the end
189 while (isspace(state->buffer[state->buffer_pos])) {
190 if (state->buffer[state->buffer_pos] == '\n') {
191 state->lineno++;
192 state->line_offset = -state->buffer_pos;
193 }
194 state->buffer_pos++;
195 }
196 next_token(state);
197 return;
198 } else if (isalpha(ch)) {
199 while (isalnum(state->buffer[state->buffer_pos])
200 || state->buffer[state->buffer_pos] == '_')
201 state->buffer_pos++;
202 char *value = str_ndup(state->buffer + state->old_buffer_pos,
203 state->buffer_pos - state->old_buffer_pos);
204 if (!value) {
205 error_errno(state, ENOMEM);
206 } else if (!str_cmp(value, "struct")) {
207 state->token = TOKEN_STRUCT;
208 free(value);
209 } else if (!str_cmp(value, "transform")) {
210 state->token = TOKEN_TRANSFORM;
211 free(value);
212 } else {
213 state->token = TOKEN_IDENTIFIER;
214 state->token_string = value;
215 }
216 } else if (isdigit(ch)) {
217 while (isdigit(state->buffer[state->buffer_pos]))
218 state->buffer_pos++;
219 state->token = TOKEN_INTEGER;
220 int rc = bithenge_parse_int(state->buffer +
221 state->old_buffer_pos, &state->token_int);
222 error_errno(state, rc);
223 } else if (ch == '<') {
224 state->token = ch;
225 state->buffer_pos++;
226 if (state->buffer[state->buffer_pos] == '-') {
227 state->buffer_pos++;
228 state->token = TOKEN_LEFT_ARROW;
229 }
230 } else {
231 state->token = ch;
232 state->buffer_pos++;
233 }
234}
235
236/** Allocate memory and handle failure by setting the error in the state. The
237 * caller must check the state for errors before using the return value of this
238 * function. */
239static void *state_malloc(state_t *state, size_t size)
240{
241 if (state->error != EOK)
242 return NULL;
243 void *result = malloc(size);
244 if (result == NULL)
245 error_errno(state, ENOMEM);
246 return result;
247}
248
249/** Reallocate memory and handle failure by setting the error in the state. If
250 * an error occurs, the existing pointer will be returned. */
251static void *state_realloc(state_t *state, void *ptr, size_t size)
252{
253 if (state->error != EOK)
254 return ptr;
255 void *result = realloc(ptr, size);
256 if (result == NULL) {
257 error_errno(state, ENOMEM);
258 return ptr;
259 }
260 return result;
261}
262
263/** Expect and consume a certain token. If the next token is of the wrong type,
264 * an error is caused. */
265static void expect(state_t *state, token_type_t type)
266{
267 if (state->token != type) {
268 syntax_error(state, "unexpected");
269 return;
270 }
271 next_token(state);
272}
273
274/** Expect and consume an identifier token. If the next token is not an
275 * identifier, an error is caused and this function returns null. */
276static char *expect_identifier(state_t *state)
277{
278 if (state->token != TOKEN_IDENTIFIER) {
279 syntax_error(state, "unexpected (identifier expected)");
280 return NULL;
281 }
282 char *val = state->token_string;
283 state->token_string = NULL;
284 next_token(state);
285 return val;
286}
287
288/** Find a transform by name. A reference will be added to the transform.
289 * @return The found transform, or NULL if none was found. */
290static bithenge_transform_t *get_named_transform(state_t *state,
291 const char *name)
292{
293 for (transform_list_t *e = state->transform_list; e; e = e->next) {
294 if (!str_cmp(e->name, name)) {
295 bithenge_transform_inc_ref(e->transform);
296 return e->transform;
297 }
298 }
299 for (int i = 0; bithenge_primitive_transforms[i].name; i++) {
300 if (!str_cmp(bithenge_primitive_transforms[i].name, name)) {
301 bithenge_transform_t *xform =
302 bithenge_primitive_transforms[i].transform;
303 bithenge_transform_inc_ref(xform);
304 return xform;
305 }
306 }
307 return NULL;
308}
309
310/** Add a named transform. This function takes ownership of the name and a
311 * reference to the transform. If an error has occurred, either may be null. */
312static void add_named_transform(state_t *state, bithenge_transform_t *xform, char *name)
313{
314 transform_list_t *entry = state_malloc(state, sizeof(*entry));
315 if (state->error != EOK) {
316 free(name);
317 bithenge_transform_dec_ref(xform);
318 free(entry);
319 return;
320 }
321 entry->name = name;
322 entry->transform = xform;
323 entry->next = state->transform_list;
324 state->transform_list = entry;
325}
326
327static bithenge_transform_t *parse_transform(state_t *state);
328
329static bithenge_expression_t *parse_expression(state_t *state)
330{
331 if (state->token == TOKEN_INTEGER) {
332 bithenge_int_t val = state->token_int;
333 next_token(state);
334 bithenge_node_t *node;
335 int rc = bithenge_new_integer_node(&node, val);
336 if (rc != EOK) {
337 error_errno(state, rc);
338 return NULL;
339 }
340
341 bithenge_expression_t *expr;
342 rc = bithenge_const_expression(&expr, node);
343 if (rc != EOK) {
344 error_errno(state, rc);
345 return NULL;
346 }
347
348 return expr;
349 } else if (state->token == TOKEN_IDENTIFIER) {
350 int i;
351 for (i = 0; i < state->num_params; i++)
352 if (!str_cmp(state->parameter_names[i],
353 state->token_string))
354 break;
355
356 if (i == state->num_params) {
357 syntax_error(state, "unknown identifier");
358 return NULL;
359 }
360
361 bithenge_expression_t *expr;
362 int rc = bithenge_param_expression(&expr, i);
363 if (rc != EOK) {
364 error_errno(state, rc);
365 return NULL;
366 }
367
368 next_token(state);
369
370 return expr;
371 } else if (state->token == '.') {
372 next_token(state);
373
374 const char *id = expect_identifier(state);
375 bithenge_node_t *key = NULL;
376 bithenge_expression_t *expr = NULL;
377 int rc = bithenge_current_node_expression(&expr);
378 error_errno(state, rc);
379
380 if (state->error == EOK) {
381 rc = bithenge_new_string_node(&key, id, true);
382 id = NULL;
383 error_errno(state, rc);
384 }
385
386 if (state->error == EOK) {
387 rc = bithenge_member_expression(&expr, expr, key);
388 key = NULL;
389 if (rc != EOK)
390 expr = NULL;
391 error_errno(state, rc);
392 }
393
394 if (state->error != EOK) {
395 free((char *)id);
396 bithenge_node_dec_ref(key);
397 bithenge_expression_dec_ref(expr);
398 return NULL;
399 }
400
401 return expr;
402 } else {
403 syntax_error(state, "expression expected");
404 return NULL;
405 }
406}
407
408// state->token must be TOKEN_IDENTIFIER when this is called
409static bithenge_transform_t *parse_invocation(state_t *state)
410{
411 bithenge_transform_t *result = get_named_transform(state,
412 state->token_string);
413 if (!result)
414 syntax_error(state, "transform not found");
415 next_token(state);
416
417 bithenge_expression_t **params = NULL;
418 int num_params = 0;
419 if (state->token == '(') {
420 next_token(state);
421 while (state->error == EOK && state->token != ')') {
422 if (num_params)
423 expect(state, ',');
424 params = state_realloc(state, params,
425 (num_params + 1)*sizeof(*params));
426 if (state->error != EOK)
427 break;
428 params[num_params] = parse_expression(state);
429 num_params++;
430 }
431 expect(state, ')');
432 }
433
434 /* TODO: show correct error position */
435 if (state->error == EOK
436 && bithenge_transform_num_params(result) != num_params)
437 syntax_error(state, "incorrect number of parameters before");
438
439 if (state->error != EOK) {
440 while (num_params--)
441 bithenge_expression_dec_ref(params[num_params]);
442 free(params);
443 bithenge_transform_dec_ref(result);
444 return NULL;
445 }
446
447 if (num_params) {
448 int rc = bithenge_param_wrapper(&result, result, params);
449 if (rc != EOK) {
450 error_errno(state, rc);
451 result = NULL;
452 }
453 }
454
455 return result;
456}
457
458static bithenge_transform_t *parse_struct(state_t *state)
459{
460 size_t num = 0;
461 bithenge_named_transform_t *subxforms;
462 /* We keep an extra space for the {NULL, NULL} terminator. */
463 subxforms = state_malloc(state, sizeof(*subxforms));
464 expect(state, TOKEN_STRUCT);
465 expect(state, '{');
466 while (state->error == EOK && state->token != '}') {
467 if (state->token == '.') {
468 expect(state, '.');
469 subxforms[num].name = expect_identifier(state);
470 expect(state, TOKEN_LEFT_ARROW);
471 } else {
472 subxforms[num].name = NULL;
473 expect(state, TOKEN_LEFT_ARROW);
474 }
475 subxforms[num].transform = parse_transform(state);
476 expect(state, ';');
477 num++;
478 subxforms = state_realloc(state, subxforms,
479 (num + 1)*sizeof(*subxforms));
480 }
481 expect(state, '}');
482
483 if (state->error != EOK) {
484 while (num--) {
485 free((void *)subxforms[num].name);
486 bithenge_transform_dec_ref(subxforms[num].transform);
487 }
488 free(subxforms);
489 return NULL;
490 }
491
492 subxforms[num].name = NULL;
493 subxforms[num].transform = NULL;
494 bithenge_transform_t *result;
495 int rc = bithenge_new_struct(&result, subxforms);
496 if (rc != EOK) {
497 error_errno(state, rc);
498 return NULL;
499 }
500 return result;
501}
502
503/** Parse a transform without composition.
504 * @return The parsed transform, or NULL if an error occurred. */
505static bithenge_transform_t *parse_transform_no_compose(state_t *state)
506{
507 if (state->token == TOKEN_IDENTIFIER) {
508 return parse_invocation(state);
509 } else if (state->token == TOKEN_STRUCT) {
510 return parse_struct(state);
511 } else {
512 syntax_error(state, "unexpected (transform expected)");
513 return NULL;
514 }
515}
516
517/** Parse a transform.
518 * @return The parsed transform, or NULL if an error occurred. */
519static bithenge_transform_t *parse_transform(state_t *state)
520{
521 bithenge_transform_t *result = parse_transform_no_compose(state);
522 bithenge_transform_t **xforms = NULL;
523 size_t num = 1;
524 while (state->token == TOKEN_LEFT_ARROW) {
525 expect(state, TOKEN_LEFT_ARROW);
526 xforms = state_realloc(state, xforms,
527 (num + 1) * sizeof(*xforms));
528 if (state->error != EOK)
529 break;
530 xforms[num] = parse_transform_no_compose(state);
531 num++;
532 }
533 if (state->error != EOK) {
534 while (xforms && num--)
535 bithenge_transform_dec_ref(xforms[num]);
536 free(xforms);
537 bithenge_transform_dec_ref(result);
538 return NULL;
539 }
540 if (xforms) {
541 xforms[0] = result;
542 int rc = bithenge_new_composed_transform(&result, xforms, num);
543 if (rc != EOK) {
544 error_errno(state, rc);
545 return NULL;
546 }
547 }
548 return result;
549}
550
551/** Parse a definition. */
552static void parse_definition(state_t *state)
553{
554 expect(state, TOKEN_TRANSFORM);
555 char *name = expect_identifier(state);
556
557 if (state->token == '(') {
558 next_token(state);
559 while (state->error == EOK && state->token != ')') {
560 if (state->num_params)
561 expect(state, ',');
562 state->parameter_names = state_realloc(state,
563 state->parameter_names,
564 (state->num_params + 1)*sizeof(*state->parameter_names));
565 if (state->error != EOK)
566 break;
567 state->parameter_names[state->num_params++] =
568 expect_identifier(state);
569 }
570 expect(state, ')');
571 }
572
573 expect(state, '=');
574 bithenge_transform_t *xform = parse_transform(state);
575 expect(state, ';');
576
577 if (state->error == EOK && state->num_params) {
578 int rc = bithenge_new_param_transform(&xform, xform,
579 state->num_params);
580 if (rc != EOK) {
581 xform = NULL;
582 error_errno(state, rc);
583 }
584 }
585
586 add_named_transform(state, xform, name);
587
588 for (int i = 0; i < state->num_params; i++)
589 free(state->parameter_names[i]);
590 free(state->parameter_names);
591 state->parameter_names = NULL;
592 state->num_params = 0;
593}
594
595/** Initialize the state. */
596static void state_init(state_t *state, const char *filename)
597{
598 state->error = EOK;
599 state->transform_list = NULL;
600 state->parameter_names = NULL;
601 state->num_params = 0;
602 state->token = TOKEN_ERROR;
603 state->old_buffer_pos = state->buffer_pos = BUFFER_SIZE - 1;
604 state->lineno = 1;
605 state->line_offset = (int)-state->buffer_pos + 1;
606 state->filename = filename;
607 state->file = fopen(filename, "r");
608 if (!state->file) {
609 error_errno(state, errno);
610 } else {
611 next_token(state);
612 }
613}
614
615/** Destroy the state. */
616static void state_destroy(state_t *state)
617{
618 done_with_token(state);
619 state->token = TOKEN_ERROR;
620 if (state->file)
621 fclose(state->file);
622 transform_list_t *entry = state->transform_list;
623 while (entry) {
624 transform_list_t *next = entry->next;
625 free(entry->name);
626 bithenge_transform_dec_ref(entry->transform);
627 free(entry);
628 entry = next;
629 }
630 for (int i = 0; i < state->num_params; i++)
631 free(state->parameter_names[i]);
632 free(state->parameter_names);
633}
634
635/** Parse a script file.
636 * @param filename The name of the script file.
637 * @param[out] out Stores the "main" transform.
638 * @return EOK on success, EINVAL on syntax error, or an error code from
639 * errno.h. */
640int bithenge_parse_script(const char *filename, bithenge_transform_t **out)
641{
642 state_t state;
643 state_init(&state, filename);
644 while (state.error == EOK && state.token != TOKEN_EOF)
645 parse_definition(&state);
646 *out = get_named_transform(&state, "main");
647 int rc = state.error;
648 state_destroy(&state);
649 if (rc == EOK && !*out) {
650 fprintf(stderr, "no \"main\" transform\n");
651 rc = EINVAL;
652 }
653 return rc;
654}
655
656/** @}
657 */
Note: See TracBrowser for help on using the repository browser.