1 /* MIT (BSD) license - see LICENSE file for details */
3 #include <ccan/tal/str/str.h>
11 static void add_token(struct token **toks, const char *p, size_t len)
13 size_t n = tal_count(*toks);
14 tal_resize(toks, n+1);
19 static size_t to_eol(const char *p)
21 size_t len = strcspn(p, "\n");
23 /* And any \ continuations. */
24 while (p[len] && p[len-1] == '\\')
25 len += strcspn(p+len+1, "\n") + 1;
29 /* Simplified tokenizer: comments and preproc directives removed,
30 identifiers are a token, others are single char tokens. */
31 static struct token *tokenize(const void *ctx, const char *code)
33 unsigned int i, len, tok_start = -1;
34 bool start_of_line = true;
35 struct token *toks = tal_arr(ctx, struct token, 0);
37 for (i = 0; code[i]; i += len) {
38 if (code[i] == '#' && start_of_line) {
39 /* Preprocessor line. */
40 len = to_eol(code + i);
41 } else if (code[i] == '/' && code[i+1] == '/') {
42 /* One line comment. */
43 len = to_eol(code + i);
44 if (tok_start != -1U) {
45 add_token(&toks, code+tok_start, i - tok_start);
48 } else if (code[i] == '/' && code[i+1] == '*') {
49 /* Multi-line comment. */
50 const char *end = strstr(code+i+2, "*/");
51 len = (end + 2) - (code + i);
53 len = strlen(code + i);
54 if (tok_start != -1U) {
55 add_token(&toks, code+tok_start, i - tok_start);
58 } else if (cisalnum(code[i]) || code[i] == '_') {
59 /* Identifier or part thereof */
63 } else if (!cisspace(code[i])) {
64 /* Punctuation: treat as single char token. */
65 if (tok_start != -1U) {
66 add_token(&toks, code+tok_start, i - tok_start);
69 add_token(&toks, code+i, 1);
73 if (tok_start != -1U) {
74 add_token(&toks, code+tok_start, i - tok_start);
81 else if (!cisspace(code[i]))
82 start_of_line = false;
85 /* Add terminating NULL. */
86 tal_resizez(&toks, tal_count(toks) + 1);
92 const struct token *toks;
93 struct cdump_definitions *defs;
97 static const struct token *tok_peek(const struct token **toks)
99 /* Ignore removed tokens (eg. comments) */
100 while (toks[0]->len == 0) {
108 static bool tok_is(const struct token **toks, const char *target)
110 const struct token *t = tok_peek(toks);
111 return (t && t->len == strlen(target)
112 && memcmp(t->p, target, t->len) == 0);
115 static const struct token *tok_take(const struct token **toks)
117 const struct token *t = tok_peek(toks);
124 static const struct token *tok_take_if(const struct token **toks,
127 if (tok_is(toks, target))
128 return tok_take(toks);
132 static const char *tok_take_ident(const tal_t *ctx, const struct token **toks)
134 const struct token *t = tok_peek(toks);
139 if (strspn(t->p, "_0123456789"
140 "abcdefghijklmnopqrstuvwxyz"
141 "ABCDEFGHIJKLMNOPQRSTUVWXYZ") < t->len)
145 return tal_strndup(ctx, t->p, t->len);
148 static char *string_of_toks(const tal_t *ctx,
149 const struct token *first,
150 const struct token *until)
154 /* Careful to skip erased tokens (eg. comments) */
155 str = p = tal_arr(ctx, char, until->p - first->p + 1);
156 while (first != until) {
157 const struct token *next = first + 1;
160 memcpy(p, first->p, first->len);
162 /* Insert space if they weren't adjacent, unless last */
164 if (first->p + first->len != next->p)
175 static char *tok_take_until(const tal_t *ctx,
176 const struct token **toks,
179 const struct token *t, *start;
181 start = tok_peek(toks);
182 while ((t = tok_peek(toks)) != NULL) {
183 /* If this contains a delimiter, copy up to prev token. */
184 if (strcspn(t->p, delims) < t->len)
185 return string_of_toks(ctx, start, t);
189 /* EOF without finding delimiter */
193 static bool type_defined(const struct cdump_type *t)
198 return (t->u.members != NULL);
200 return (t->u.enum_vals != NULL);
202 /* These shouldn't happen; we don't try to define them. */
211 /* May allocate a new type if not already found (steals @name) */
212 static struct cdump_type *get_type(struct cdump_definitions *defs,
213 enum cdump_type_kind kind,
217 struct cdump_type *t;
235 /* Do we already have it? */
237 t = strmap_get(m, name);
242 t = tal(defs, struct cdump_type);
244 t->name = name ? tal_steal(t, name) : NULL;
245 /* These are actually the same, but be thorough */
247 t->u.enum_vals = NULL;
249 strmap_add(m, t->name, t);
254 static void complain(struct parse_state *ps, const char *complaint)
256 unsigned int linenum;
257 const char *p = ps->code;
259 for (linenum = 1; p < ps->toks[0].p; linenum++) {
260 p = strchr(p+1, '\n');
265 tal_append_fmt(&ps->complaints,
266 "Line %u: '%.*s': %s\n",
267 linenum, (int)ps->toks[0].len,
268 ps->toks[0].p, complaint);
271 static void tok_take_unknown_statement(struct parse_state *ps)
273 complain(ps, "Ignoring unknown statement until next semicolon");
274 tal_free(tok_take_until(NULL, &ps->toks, ";"));
275 tok_take_if(&ps->toks, ";");
278 static bool tok_take_expr(struct parse_state *ps, const char *term)
280 while (!tok_is(&ps->toks, term)) {
281 if (tok_take_if(&ps->toks, "(")) {
282 if (!tok_take_expr(ps, ")"))
284 } else if (tok_take_if(&ps->toks, "[")) {
285 if (!tok_take_expr(ps, "]"))
287 } else if (!tok_take(&ps->toks))
290 return tok_take(&ps->toks);
293 static char *tok_take_expr_str(const tal_t *ctx,
294 struct parse_state *ps,
297 const struct token *start = tok_peek(&ps->toks);
299 if (!tok_take_expr(ps, term))
302 return string_of_toks(ctx, start, ps->toks - 1);
306 static bool tok_take_array(struct parse_state *ps, struct cdump_type **type)
308 /* This will be some arbitrary expression! */
309 struct cdump_type *arr = get_type(ps->defs, CDUMP_ARRAY, NULL);
311 arr->u.arr.size = tok_take_expr_str(arr, ps, "]");
312 if (!arr->u.arr.size) {
313 complain(ps, "Could not find closing array size ]");
317 arr->u.arr.type = *type;
323 static struct cdump_type *ptr_of(struct parse_state *ps,
324 const struct cdump_type *ptr_to)
326 struct cdump_type *ptr = get_type(ps->defs, CDUMP_POINTER, NULL);
331 static bool tok_take_type(struct parse_state *ps, struct cdump_type **type)
334 const struct token *types;
335 enum cdump_type_kind kind;
337 /* Ignoring weird typedefs, only these can be combined. */
339 while (tok_take_if(&ps->toks, "int")
340 || tok_take_if(&ps->toks, "long")
341 || tok_take_if(&ps->toks, "short")
342 || tok_take_if(&ps->toks, "double")
343 || tok_take_if(&ps->toks, "float")
344 || tok_take_if(&ps->toks, "char")
345 || tok_take_if(&ps->toks, "signed")
346 || tok_take_if(&ps->toks, "unsigned"));
348 /* Did we get some? */
349 if (ps->toks != types) {
350 name = string_of_toks(NULL, types, tok_peek(&ps->toks));
351 kind = CDUMP_UNKNOWN;
353 /* Try normal types (or simple typedefs, etc). */
354 if (tok_take_if(&ps->toks, "struct")) {
356 } else if (tok_take_if(&ps->toks, "union")) {
358 } else if (tok_take_if(&ps->toks, "enum")) {
361 kind = CDUMP_UNKNOWN;
363 name = tok_take_ident(ps->defs, &ps->toks);
365 complain(ps, "Invalid typename");
370 *type = get_type(ps->defs, kind, name);
375 static bool tok_maybe_take_cdump_note(const tal_t *ctx,
376 struct parse_state *ps, const char **note)
379 if (tok_take_if(&ps->toks, "CDUMP")) {
380 if (!tok_take_if(&ps->toks, "(")) {
381 complain(ps, "Expected ( after CDUMP");
384 *note = tok_take_expr_str(ctx, ps, ")");
386 complain(ps, "Expected ) after CDUMP(");
393 /* struct|union ... */
394 static bool tok_take_conglom(struct parse_state *ps,
395 enum cdump_type_kind conglom_kind)
397 struct cdump_type *e;
401 assert(conglom_kind == CDUMP_STRUCT || conglom_kind == CDUMP_UNION);
403 name = tok_take_ident(ps->defs, &ps->toks);
405 complain(ps, "Invalid struct/union name");
409 e = get_type(ps->defs, conglom_kind, name);
410 if (type_defined(e)) {
411 complain(ps, "Type already defined");
415 if (!tok_maybe_take_cdump_note(e, ps, &e->note))
418 if (!tok_take_if(&ps->toks, "{")) {
419 complain(ps, "Expected { for struct/union");
423 e->u.members = tal_arr(e, struct cdump_member, n = 0);
424 while (!tok_is(&ps->toks, "}")) {
425 struct cdump_type *basetype;
426 const struct token *quals;
427 unsigned int num_quals = 0;
429 /* Anything can have these prepended. */
431 while (tok_take_if(&ps->toks, "const")
432 || tok_take_if(&ps->toks, "volatile"))
435 /* eg. "struct foo" or "varint_t" */
436 if (!tok_take_type(ps, &basetype)) {
437 complain(ps, "Expected typename inside struct/union");
442 struct cdump_member *m;
444 tal_resize(&e->u.members, n+1);
445 m = &e->u.members[n++];
449 = string_of_toks(e, quals,
452 m->qualifiers = NULL;
454 /* May have multiple asterisks. */
455 while (tok_take_if(&ps->toks, "*"))
456 m->type = ptr_of(ps, m->type);
458 m->name = tok_take_ident(e, &ps->toks);
460 complain(ps, "Expected name for member");
464 /* May be an array. */
465 while (tok_take_if(&ps->toks, "[")) {
466 if (!tok_take_array(ps, &m->type))
471 if (!tok_maybe_take_cdump_note(e->u.members,
474 } while (tok_take_if(&ps->toks, ","));
476 if (!tok_take_if(&ps->toks, ";")) {
477 complain(ps, "Expected ; at end of member");
482 if (tok_take_if(&ps->toks, "}") && tok_take_if(&ps->toks, ";"))
484 complain(ps, "Expected }; at end of struct/union");
489 static bool tok_take_enum(struct parse_state *ps)
492 struct cdump_type *e;
495 name = tok_take_ident(ps->defs, &ps->toks);
497 complain(ps, "Expected enum name");
501 e = get_type(ps->defs, CDUMP_ENUM, name);
503 /* Duplicate name? */
504 if (type_defined(e)) {
505 complain(ps, "enum already defined");
510 if (!tok_maybe_take_cdump_note(e, ps, &e->note))
513 if (!tok_take_if(&ps->toks, "{")) {
514 complain(ps, "Expected { after enum name");
518 e->u.enum_vals = tal_arr(e, struct cdump_enum_val, n);
520 struct cdump_enum_val *v;
522 /* GCC extension: comma and end of enum */
523 if (tok_is(&ps->toks, "}"))
526 tal_resize(&e->u.enum_vals, n+1);
527 v = &e->u.enum_vals[n++];
529 v->name = tok_take_ident(e, &ps->toks);
531 complain(ps, "Expected enum value name");
536 if (!tok_maybe_take_cdump_note(e->u.enum_vals, ps, &v->note))
539 if (tok_take_if(&ps->toks, "=")) {
540 v->value = tok_take_until(e, &ps->toks, ",}");
542 complain(ps, "Expected , or } to end value");
547 } while (tok_take_if(&ps->toks, ","));
549 if (tok_take_if(&ps->toks, "}") && tok_take_if(&ps->toks, ";"))
552 complain(ps, "Expected }; at end of enum");
556 static bool gather_undefines(const char *name,
557 struct cdump_type *t,
558 struct cdump_map *undefs)
560 if (!type_defined(t))
561 strmap_add(undefs, name, t);
565 static bool remove_from_map(const char *name,
566 struct cdump_type *t,
567 struct cdump_map *map)
569 strmap_del(map, name, NULL);
573 static void remove_undefined(struct cdump_map *map)
575 struct cdump_map undefs;
577 /* We can't delete inside iterator, so gather all the undefs
578 * then remove them. */
579 strmap_init(&undefs);
581 strmap_iterate(map, gather_undefines, &undefs);
582 strmap_iterate(&undefs, remove_from_map, map);
583 strmap_clear(&undefs);
586 static void destroy_definitions(struct cdump_definitions *defs)
588 strmap_clear(&defs->enums);
589 strmap_clear(&defs->structs);
590 strmap_clear(&defs->unions);
593 /* Simple LL(1) parser, inspired by Tridge's genstruct.pl. */
594 struct cdump_definitions *cdump_extract(const tal_t *ctx, const char *code,
597 struct parse_state ps;
598 const struct token *toks;
600 ps.defs = tal(ctx, struct cdump_definitions);
601 ps.complaints = tal_strdup(ctx, "");
604 strmap_init(&ps.defs->enums);
605 strmap_init(&ps.defs->structs);
606 strmap_init(&ps.defs->unions);
607 tal_add_destructor(ps.defs, destroy_definitions);
609 toks = ps.toks = tokenize(ps.defs, code);
610 while (tok_peek(&ps.toks)) {
611 if (tok_take_if(&ps.toks, "struct")) {
612 if (!tok_take_conglom(&ps, CDUMP_STRUCT))
614 } else if (tok_take_if(&ps.toks, "union")) {
615 if (!tok_take_conglom(&ps, CDUMP_UNION))
617 } else if (tok_take_if(&ps.toks, "enum")) {
618 if (!tok_take_enum(&ps))
621 tok_take_unknown_statement(&ps);
624 /* Now, remove any undefined types! */
625 remove_undefined(&ps.defs->enums);
626 remove_undefined(&ps.defs->structs);
627 remove_undefined(&ps.defs->unions);
631 if (streq(ps.complaints, ""))
632 ps.complaints = tal_free(ps.complaints);
635 *complaints = ps.complaints;
637 tal_free(ps.complaints);
641 ps.defs = tal_free(ps.defs);