source: mainline/uspace/app/bithenge/script.c@ 02dcb20

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

Bithenge: add test files and comment support
  • Property mode set to 100644
File size: 13.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 "os.h"
41#include "script.h"
42#include "transform.h"
43#include "tree.h"
44
45/** Tokens with more characters than this may be read incorrectly. */
46#define MAX_TOKEN_SIZE 256
47#define BUFFER_SIZE 4096
48
49/** Single-character symbols are represented by the character itself. Every
50 * other token uses one of these values: */
51typedef enum {
52 TOKEN_ERROR = -128,
53 TOKEN_EOF,
54 TOKEN_IDENTIFIER,
55 TOKEN_LEFT_ARROW,
56
57 /* Keywords */
58 TOKEN_STRUCT,
59 TOKEN_TRANSFORM,
60} token_type_t;
61
62/** Singly-linked list of named transforms. */
63typedef struct transform_list {
64 char *name;
65 bithenge_transform_t *transform;
66 struct transform_list *next;
67} transform_list_t;
68
69/** State kept by the parser. */
70typedef struct {
71 /** Rather than constantly checking return values, the parser uses this
72 * to indicate whether an error has occurred. */
73 int error;
74 /** The list of named transforms. */
75 transform_list_t *transform_list;
76 /** The name of the script file. */
77 const char *filename;
78 /** The script file being read from. */
79 FILE *file;
80 /** The buffer that holds script code. There is always a '\0' after the
81 * current position to prevent reading too far. */
82 char buffer[BUFFER_SIZE];
83 /** The start position within the buffer of the next unread token. */
84 size_t buffer_pos;
85 /** The start position within the buffer of the current token. */
86 size_t old_buffer_pos;
87 /** The line number of the current token. */
88 int lineno;
89 /** Added to a buffer position to find the column number. */
90 int line_offset;
91 /** The type of the current token. */
92 token_type_t token;
93 union {
94 /** The value of a TOKEN_IDENTIFIER token. Unless changed to
95 * NULL, it will be freed when the next token is read. */
96 char *token_string;
97 };
98} state_t;
99
100/** Free the previous token's data. This must be called before changing
101 * state->token. */
102static void done_with_token(state_t *state)
103{
104 if (state->token == TOKEN_IDENTIFIER)
105 free(state->token_string);
106 state->token = TOKEN_ERROR;
107}
108
109/** Note that an error has occurred. */
110static void error_errno(state_t *state, int error)
111{
112 // Don't overwrite a previous error.
113 if (state->error == EOK) {
114 done_with_token(state);
115 state->token = TOKEN_ERROR;
116 state->error = error;
117 }
118}
119
120/** Note that a syntax error has occurred and print an error message. */
121static void syntax_error(state_t *state, const char *message)
122{
123 // Printing multiple errors is confusing.
124 if (state->error == EOK) {
125 size_t start_char = state->old_buffer_pos + state->line_offset;
126 size_t end_char = state->buffer_pos + state->line_offset;
127 size_t size = end_char - start_char;
128 fprintf(stderr, "%s:%d:", state->filename, state->lineno);
129 if (size <= 1)
130 fprintf(stderr, "%zd: ", start_char);
131 else
132 fprintf(stderr, "%zd-%zd: ", start_char, end_char - 1);
133 fprintf(stderr, "%s: \"%.*s\"\n", message, (int)size,
134 state->buffer + state->old_buffer_pos);
135 error_errno(state, EINVAL);
136 }
137}
138
139/** Ensure the buffer contains enough characters to read a token. */
140static void fill_buffer(state_t *state)
141{
142 if (state->buffer_pos + MAX_TOKEN_SIZE < BUFFER_SIZE)
143 return;
144
145 size_t empty_size = state->buffer_pos;
146 size_t used_size = BUFFER_SIZE - 1 - state->buffer_pos;
147 memmove(state->buffer, state->buffer + state->buffer_pos, used_size);
148 state->line_offset += state->buffer_pos;
149 state->buffer_pos = 0;
150
151 size_t read_size = fread(state->buffer + used_size, 1, empty_size,
152 state->file);
153 if (ferror(state->file))
154 error_errno(state, EIO);
155 state->buffer[used_size + read_size] = '\0';
156}
157
158/** Read the next token. */
159static void next_token(state_t *state)
160{
161 fill_buffer(state);
162 done_with_token(state);
163 state->old_buffer_pos = state->buffer_pos;
164 char ch = state->buffer[state->buffer_pos];
165 if (ch == '\0') {
166 state->token = TOKEN_EOF;
167 } else if (ch == '#') {
168 while (state->buffer[state->buffer_pos] != '\n'
169 && state->buffer[state->buffer_pos] != '\0') {
170 state->buffer_pos++;
171 fill_buffer(state);
172 }
173 next_token(state);
174 return;
175 } else if (isspace(ch)) {
176 // Will eventually reach the '\0' at the end
177 while (isspace(state->buffer[state->buffer_pos])) {
178 if (state->buffer[state->buffer_pos] == '\n') {
179 state->lineno++;
180 state->line_offset = -state->buffer_pos;
181 }
182 state->buffer_pos++;
183 }
184 next_token(state);
185 return;
186 } else if (isalpha(ch)) {
187 while (isalnum(state->buffer[state->buffer_pos])
188 || state->buffer[state->buffer_pos] == '_')
189 state->buffer_pos++;
190 char *value = str_ndup(state->buffer + state->old_buffer_pos,
191 state->buffer_pos - state->old_buffer_pos);
192 if (!value) {
193 error_errno(state, ENOMEM);
194 } else if (!str_cmp(value, "struct")) {
195 state->token = TOKEN_STRUCT;
196 free(value);
197 } else if (!str_cmp(value, "transform")) {
198 state->token = TOKEN_TRANSFORM;
199 free(value);
200 } else {
201 state->token = TOKEN_IDENTIFIER;
202 state->token_string = value;
203 }
204 } else if (ch == '<') {
205 state->token = ch;
206 state->buffer_pos++;
207 if (state->buffer[state->buffer_pos] == '-') {
208 state->buffer_pos++;
209 state->token = TOKEN_LEFT_ARROW;
210 }
211 } else {
212 state->token = ch;
213 state->buffer_pos++;
214 }
215}
216
217/** Allocate memory and handle failure by setting the error in the state. The
218 * caller must check the state for errors before using the return value of this
219 * function. */
220static void *state_malloc(state_t *state, size_t size)
221{
222 if (state->error != EOK)
223 return NULL;
224 void *result = malloc(size);
225 if (result == NULL)
226 error_errno(state, ENOMEM);
227 return result;
228}
229
230/** Reallocate memory and handle failure by setting the error in the state. If
231 * an error occurs, the existing pointer will be returned. */
232static void *state_realloc(state_t *state, void *ptr, size_t size)
233{
234 if (state->error != EOK)
235 return ptr;
236 void *result = realloc(ptr, size);
237 if (result == NULL) {
238 error_errno(state, ENOMEM);
239 return ptr;
240 }
241 return result;
242}
243
244/** Expect and consume a certain token. If the next token is of the wrong type,
245 * an error is caused. */
246static void expect(state_t *state, token_type_t type)
247{
248 if (state->token != type) {
249 syntax_error(state, "unexpected");
250 return;
251 }
252 next_token(state);
253}
254
255/** Expect and consume an identifier token. If the next token is not an
256 * identifier, an error is caused and this function returns null. */
257static char *expect_identifier(state_t *state)
258{
259 if (state->token != TOKEN_IDENTIFIER) {
260 syntax_error(state, "unexpected (identifier expected)");
261 return NULL;
262 }
263 char *val = state->token_string;
264 state->token_string = NULL;
265 next_token(state);
266 return val;
267}
268
269/** Find a transform by name. A reference will be added to the transform.
270 * @return The found transform, or NULL if none was found. */
271static bithenge_transform_t *get_named_transform(state_t *state,
272 const char *name)
273{
274 for (transform_list_t *e = state->transform_list; e; e = e->next) {
275 if (!str_cmp(e->name, name)) {
276 bithenge_transform_inc_ref(e->transform);
277 return e->transform;
278 }
279 }
280 for (int i = 0; bithenge_primitive_transforms[i].name; i++) {
281 if (!str_cmp(bithenge_primitive_transforms[i].name, name)) {
282 bithenge_transform_t *xform =
283 bithenge_primitive_transforms[i].transform;
284 bithenge_transform_inc_ref(xform);
285 return xform;
286 }
287 }
288 return NULL;
289}
290
291/** Add a named transform. This function takes ownership of the name and a
292 * reference to the transform. If an error has occurred, either may be null. */
293static void add_named_transform(state_t *state, bithenge_transform_t *xform, char *name)
294{
295 transform_list_t *entry = state_malloc(state, sizeof(*entry));
296 if (state->error != EOK) {
297 free(name);
298 bithenge_transform_dec_ref(xform);
299 free(entry);
300 return;
301 }
302 entry->name = name;
303 entry->transform = xform;
304 entry->next = state->transform_list;
305 state->transform_list = entry;
306}
307
308static bithenge_transform_t *parse_transform(state_t *state);
309
310static bithenge_transform_t *parse_struct(state_t *state)
311{
312 size_t num = 0;
313 bithenge_named_transform_t *subxforms;
314 /* We keep an extra space for the {NULL, NULL} terminator. */
315 subxforms = state_malloc(state, sizeof(*subxforms));
316 expect(state, TOKEN_STRUCT);
317 expect(state, '{');
318 while (state->error == EOK && state->token != '}') {
319 if (state->token == '.') {
320 expect(state, '.');
321 subxforms[num].name = expect_identifier(state);
322 expect(state, TOKEN_LEFT_ARROW);
323 } else {
324 subxforms[num].name = NULL;
325 expect(state, TOKEN_LEFT_ARROW);
326 }
327 subxforms[num].transform = parse_transform(state);
328 expect(state, ';');
329 num++;
330 subxforms = state_realloc(state, subxforms,
331 (num + 1)*sizeof(*subxforms));
332 }
333 expect(state, '}');
334
335 if (state->error != EOK) {
336 while (num--) {
337 free((void *)subxforms[num].name);
338 bithenge_transform_dec_ref(subxforms[num].transform);
339 }
340 free(subxforms);
341 return NULL;
342 }
343
344 subxforms[num].name = NULL;
345 subxforms[num].transform = NULL;
346 bithenge_transform_t *result;
347 int rc = bithenge_new_struct(&result, subxforms);
348 if (rc != EOK) {
349 error_errno(state, rc);
350 return NULL;
351 }
352 return result;
353}
354
355/** Parse a transform without composition.
356 * @return The parsed transform, or NULL if an error occurred. */
357static bithenge_transform_t *parse_transform_no_compose(state_t *state)
358{
359 if (state->token == TOKEN_IDENTIFIER) {
360 bithenge_transform_t *result = get_named_transform(state,
361 state->token_string);
362 if (!result)
363 syntax_error(state, "transform not found");
364 next_token(state);
365 return result;
366 } else if (state->token == TOKEN_STRUCT) {
367 return parse_struct(state);
368 } else {
369 syntax_error(state, "unexpected (transform expected)");
370 return NULL;
371 }
372}
373
374/** Parse a transform.
375 * @return The parsed transform, or NULL if an error occurred. */
376static bithenge_transform_t *parse_transform(state_t *state)
377{
378 bithenge_transform_t *result = parse_transform_no_compose(state);
379 bithenge_transform_t **xforms = NULL;
380 size_t num = 1;
381 while (state->token == TOKEN_LEFT_ARROW) {
382 expect(state, TOKEN_LEFT_ARROW);
383 xforms = state_realloc(state, xforms,
384 (num + 1) * sizeof(*xforms));
385 if (state->error != EOK)
386 break;
387 xforms[num] = parse_transform_no_compose(state);
388 num++;
389 }
390 if (state->error != EOK) {
391 while (xforms && num--)
392 bithenge_transform_dec_ref(xforms[num]);
393 free(xforms);
394 bithenge_transform_dec_ref(result);
395 return NULL;
396 }
397 if (xforms) {
398 xforms[0] = result;
399 int rc = bithenge_new_composed_transform(&result, xforms, num);
400 if (rc != EOK) {
401 error_errno(state, rc);
402 return NULL;
403 }
404 }
405 return result;
406}
407
408/** Parse a definition. */
409static void parse_definition(state_t *state)
410{
411 expect(state, TOKEN_TRANSFORM);
412 char *name = expect_identifier(state);
413 expect(state, '=');
414 bithenge_transform_t *xform = parse_transform(state);
415 expect(state, ';');
416 add_named_transform(state, xform, name);
417}
418
419/** Initialize the state. */
420static void state_init(state_t *state, const char *filename)
421{
422 state->error = EOK;
423 state->transform_list = NULL;
424 state->token = TOKEN_ERROR;
425 state->old_buffer_pos = state->buffer_pos = BUFFER_SIZE - 1;
426 state->lineno = 1;
427 state->line_offset = (int)-state->buffer_pos + 1;
428 state->filename = filename;
429 state->file = fopen(filename, "r");
430 if (!state->file) {
431 error_errno(state, errno);
432 } else {
433 next_token(state);
434 }
435}
436
437/** Destroy the state. */
438static void state_destroy(state_t *state)
439{
440 done_with_token(state);
441 state->token = TOKEN_ERROR;
442 fclose(state->file);
443 transform_list_t *entry = state->transform_list;
444 while (entry) {
445 transform_list_t *next = entry->next;
446 free(entry->name);
447 bithenge_transform_dec_ref(entry->transform);
448 free(entry);
449 entry = next;
450 }
451}
452
453/** Parse a script file.
454 * @param filename The name of the script file.
455 * @param[out] out Stores the "main" transform.
456 * @return EOK on success, EINVAL on syntax error, or an error code from
457 * errno.h. */
458int bithenge_parse_script(const char *filename, bithenge_transform_t **out)
459{
460 state_t state;
461 state_init(&state, filename);
462 while (state.error == EOK && state.token != TOKEN_EOF)
463 parse_definition(&state);
464 *out = get_named_transform(&state, "main");
465 int rc = state.error;
466 state_destroy(&state);
467 if (rc == EOK && !*out) {
468 fprintf(stderr, "no \"main\" transform\n");
469 rc = EINVAL;
470 }
471 return rc;
472}
473
474/** @}
475 */
Note: See TracBrowser for help on using the repository browser.