source: mainline/uspace/app/bithenge/script.c@ 600f5d1

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

Bithenge: add composition, ascii, and zero_terminated
  • Property mode set to 100644
File size: 13.2 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 (isspace(ch)) {
168 // Will eventually reach the '\0' at the end
169 while (isspace(state->buffer[state->buffer_pos])) {
170 if (state->buffer[state->buffer_pos] == '\n') {
171 state->lineno++;
172 state->line_offset = -state->buffer_pos;
173 }
174 state->buffer_pos++;
175 }
176 next_token(state);
177 return;
178 } else if (isalpha(ch)) {
179 while (isalnum(state->buffer[state->buffer_pos])
180 || state->buffer[state->buffer_pos] == '_')
181 state->buffer_pos++;
182 char *value = str_ndup(state->buffer + state->old_buffer_pos,
183 state->buffer_pos - state->old_buffer_pos);
184 if (!value) {
185 error_errno(state, ENOMEM);
186 } else if (!str_cmp(value, "struct")) {
187 state->token = TOKEN_STRUCT;
188 free(value);
189 } else if (!str_cmp(value, "transform")) {
190 state->token = TOKEN_TRANSFORM;
191 free(value);
192 } else {
193 state->token = TOKEN_IDENTIFIER;
194 state->token_string = value;
195 }
196 } else if (ch == '<') {
197 state->token = ch;
198 state->buffer_pos++;
199 if (state->buffer[state->buffer_pos] == '-') {
200 state->buffer_pos++;
201 state->token = TOKEN_LEFT_ARROW;
202 }
203 } else {
204 state->token = ch;
205 state->buffer_pos++;
206 }
207}
208
209/** Allocate memory and handle failure by setting the error in the state. The
210 * caller must check the state for errors before using the return value of this
211 * function. */
212static void *state_malloc(state_t *state, size_t size)
213{
214 if (state->error != EOK)
215 return NULL;
216 void *result = malloc(size);
217 if (result == NULL)
218 error_errno(state, ENOMEM);
219 return result;
220}
221
222/** Reallocate memory and handle failure by setting the error in the state. If
223 * an error occurs, the existing pointer will be returned. */
224static void *state_realloc(state_t *state, void *ptr, size_t size)
225{
226 if (state->error != EOK)
227 return ptr;
228 void *result = realloc(ptr, size);
229 if (result == NULL) {
230 error_errno(state, ENOMEM);
231 return ptr;
232 }
233 return result;
234}
235
236/** Expect and consume a certain token. If the next token is of the wrong type,
237 * an error is caused. */
238static void expect(state_t *state, token_type_t type)
239{
240 if (state->token != type) {
241 syntax_error(state, "unexpected");
242 return;
243 }
244 next_token(state);
245}
246
247/** Expect and consume an identifier token. If the next token is not an
248 * identifier, an error is caused and this function returns null. */
249static char *expect_identifier(state_t *state)
250{
251 if (state->token != TOKEN_IDENTIFIER) {
252 syntax_error(state, "unexpected (identifier expected)");
253 return NULL;
254 }
255 char *val = state->token_string;
256 state->token_string = NULL;
257 next_token(state);
258 return val;
259}
260
261/** Find a transform by name. A reference will be added to the transform.
262 * @return The found transform, or NULL if none was found. */
263static bithenge_transform_t *get_named_transform(state_t *state,
264 const char *name)
265{
266 for (transform_list_t *e = state->transform_list; e; e = e->next) {
267 if (!str_cmp(e->name, name)) {
268 bithenge_transform_inc_ref(e->transform);
269 return e->transform;
270 }
271 }
272 for (int i = 0; bithenge_primitive_transforms[i].name; i++) {
273 if (!str_cmp(bithenge_primitive_transforms[i].name, name)) {
274 bithenge_transform_t *xform =
275 bithenge_primitive_transforms[i].transform;
276 bithenge_transform_inc_ref(xform);
277 return xform;
278 }
279 }
280 return NULL;
281}
282
283/** Add a named transform. This function takes ownership of the name and a
284 * reference to the transform. If an error has occurred, either may be null. */
285static void add_named_transform(state_t *state, bithenge_transform_t *xform, char *name)
286{
287 transform_list_t *entry = state_malloc(state, sizeof(*entry));
288 if (state->error != EOK) {
289 free(name);
290 bithenge_transform_dec_ref(xform);
291 free(entry);
292 return;
293 }
294 entry->name = name;
295 entry->transform = xform;
296 entry->next = state->transform_list;
297 state->transform_list = entry;
298}
299
300static bithenge_transform_t *parse_transform(state_t *state);
301
302static bithenge_transform_t *parse_struct(state_t *state)
303{
304 size_t num = 0;
305 bithenge_named_transform_t *subxforms;
306 /* We keep an extra space for the {NULL, NULL} terminator. */
307 subxforms = state_malloc(state, sizeof(*subxforms));
308 expect(state, TOKEN_STRUCT);
309 expect(state, '{');
310 while (state->error == EOK && state->token != '}') {
311 if (state->token == '.') {
312 expect(state, '.');
313 subxforms[num].name = expect_identifier(state);
314 expect(state, TOKEN_LEFT_ARROW);
315 } else {
316 subxforms[num].name = NULL;
317 expect(state, TOKEN_LEFT_ARROW);
318 }
319 subxforms[num].transform = parse_transform(state);
320 expect(state, ';');
321 num++;
322 subxforms = state_realloc(state, subxforms,
323 (num + 1)*sizeof(*subxforms));
324 }
325 expect(state, '}');
326
327 if (state->error != EOK) {
328 while (num--) {
329 free((void *)subxforms[num].name);
330 bithenge_transform_dec_ref(subxforms[num].transform);
331 }
332 free(subxforms);
333 return NULL;
334 }
335
336 subxforms[num].name = NULL;
337 subxforms[num].transform = NULL;
338 bithenge_transform_t *result;
339 int rc = bithenge_new_struct(&result, subxforms);
340 if (rc != EOK) {
341 error_errno(state, rc);
342 return NULL;
343 }
344 return result;
345}
346
347/** Parse a transform without composition.
348 * @return The parsed transform, or NULL if an error occurred. */
349static bithenge_transform_t *parse_transform_no_compose(state_t *state)
350{
351 if (state->token == TOKEN_IDENTIFIER) {
352 bithenge_transform_t *result = get_named_transform(state,
353 state->token_string);
354 if (!result)
355 syntax_error(state, "transform not found");
356 next_token(state);
357 return result;
358 } else if (state->token == TOKEN_STRUCT) {
359 return parse_struct(state);
360 } else {
361 syntax_error(state, "unexpected (transform expected)");
362 return NULL;
363 }
364}
365
366/** Parse a transform.
367 * @return The parsed transform, or NULL if an error occurred. */
368static bithenge_transform_t *parse_transform(state_t *state)
369{
370 bithenge_transform_t *result = parse_transform_no_compose(state);
371 bithenge_transform_t **xforms = NULL;
372 size_t num = 1;
373 while (state->token == TOKEN_LEFT_ARROW) {
374 expect(state, TOKEN_LEFT_ARROW);
375 xforms = state_realloc(state, xforms,
376 (num + 1) * sizeof(*xforms));
377 if (state->error != EOK)
378 break;
379 xforms[num] = parse_transform_no_compose(state);
380 num++;
381 }
382 if (state->error != EOK) {
383 while (xforms && num--)
384 bithenge_transform_dec_ref(xforms[num]);
385 free(xforms);
386 bithenge_transform_dec_ref(result);
387 return NULL;
388 }
389 if (xforms) {
390 xforms[0] = result;
391 int rc = bithenge_new_composed_transform(&result, xforms, num);
392 if (rc != EOK) {
393 error_errno(state, rc);
394 return NULL;
395 }
396 }
397 return result;
398}
399
400/** Parse a definition. */
401static void parse_definition(state_t *state)
402{
403 expect(state, TOKEN_TRANSFORM);
404 char *name = expect_identifier(state);
405 expect(state, '=');
406 bithenge_transform_t *xform = parse_transform(state);
407 expect(state, ';');
408 add_named_transform(state, xform, name);
409}
410
411/** Initialize the state. */
412static void state_init(state_t *state, const char *filename)
413{
414 state->error = EOK;
415 state->transform_list = NULL;
416 state->token = TOKEN_ERROR;
417 state->old_buffer_pos = state->buffer_pos = BUFFER_SIZE - 1;
418 state->lineno = 1;
419 state->line_offset = (int)-state->buffer_pos + 1;
420 state->filename = filename;
421 state->file = fopen(filename, "r");
422 if (!state->file) {
423 error_errno(state, errno);
424 } else {
425 next_token(state);
426 }
427}
428
429/** Destroy the state. */
430static void state_destroy(state_t *state)
431{
432 done_with_token(state);
433 state->token = TOKEN_ERROR;
434 fclose(state->file);
435 transform_list_t *entry = state->transform_list;
436 while (entry) {
437 transform_list_t *next = entry->next;
438 free(entry->name);
439 bithenge_transform_dec_ref(entry->transform);
440 free(entry);
441 entry = next;
442 }
443}
444
445/** Parse a script file.
446 * @param filename The name of the script file.
447 * @param[out] out Stores the "main" transform.
448 * @return EOK on success, EINVAL on syntax error, or an error code from
449 * errno.h. */
450int bithenge_parse_script(const char *filename, bithenge_transform_t **out)
451{
452 state_t state;
453 state_init(&state, filename);
454 while (state.error == EOK && state.token != TOKEN_EOF)
455 parse_definition(&state);
456 *out = get_named_transform(&state, "main");
457 int rc = state.error;
458 state_destroy(&state);
459 if (rc == EOK && !*out) {
460 fprintf(stderr, "no \"main\" transform\n");
461 rc = EINVAL;
462 }
463 return rc;
464}
465
466/** @}
467 */
Note: See TracBrowser for help on using the repository browser.