Root/eeshow/kicad/sexpr.c

1/*
2 * kicad/sexpr.c - S-expression parser
3 *
4 * Written 2016 by Werner Almesberger
5 * Copyright 2016 by Werner Almesberger
6 *
7 * This program is free software; you can redistribute it and/or modify
8 * it under the terms of the GNU General Public License as published by
9 * the Free Software Foundation; either version 2 of the License, or
10 * (at your option) any later version.
11 */
12
13#include <stdbool.h>
14#include <stdlib.h>
15#include <stdio.h>
16#include <string.h>
17
18#include "misc/util.h"
19#include "misc/diag.h"
20#include "kicad/sexpr.h"
21
22
23struct stack {
24    struct expr **next;
25    struct stack *prev;
26};
27
28struct sexpr_ctx {
29    enum sexpr_state {
30        idle,
31        token,
32        string,
33        escape,
34        failed
35    } state;
36    struct expr *e; /* expression */
37    const char *p; /* beginning of string */
38    struct stack *sp;
39    struct stack stack;
40};
41
42
43/* ----- Parser ------------------------------------------------------------ */
44
45
46static void new_expr(struct sexpr_ctx *ctx)
47{
48    struct stack *st = alloc_type(struct stack);
49    struct expr *e = alloc_type(struct expr);
50
51    e->s = NULL;
52    e->e = NULL;
53    e->next = NULL;
54
55    *ctx->sp->next = e;
56    ctx->sp->next = &e->next;
57
58    st->prev = ctx->sp;
59    st->next = &e->e;
60    ctx->sp = st;
61}
62
63
64static void add_string(struct sexpr_ctx *ctx, const char *end)
65{
66    struct expr *e;
67    unsigned old;
68    unsigned new = end - ctx->p;
69
70    e = *ctx->sp->next;
71    if (e) {
72        old = strlen(e->s);
73    } else {
74        e = alloc_type(struct expr);
75        e->s = NULL;
76        e->e = NULL;
77        e->next = NULL;
78
79        *ctx->sp->next = e;
80        old = 0;
81    }
82
83    if (!new)
84        return;
85
86    e->s = realloc_size(e->s, old + new + 1);
87    memcpy(e->s + old, ctx->p, new);
88    e->s[old + new] = 0;
89}
90
91
92static void end_string(struct sexpr_ctx *ctx, const char *end)
93{
94    struct expr *e;
95    char *s, *t;
96
97    add_string(ctx, end);
98    e = *ctx->sp->next;
99    ctx->sp->next = &e->next;
100
101    for (s = t = e->s; *s; s++) {
102        if (*s == '\\')
103            switch (*++s) {
104            case 'n':
105                *t++ = '\n';
106                continue;
107            case 't':
108                *t++ = '\t';
109                continue;
110            case 0:
111                abort();
112            default:
113                break;
114            }
115        *t++ = *s;
116    }
117    *t = 0;
118}
119
120
121bool sexpr_parse(struct sexpr_ctx *ctx, const char *s)
122{
123    ctx->p = s;
124    while (*s) {
125        switch (ctx->state) {
126        case idle:
127            switch (*s) {
128            case ' ':
129            case '\t':
130            case '\r':
131            case '\n':
132                break;
133            case '(':
134                new_expr(ctx);
135                break;
136            case ')':
137                if (!ctx->sp->prev) {
138                    ctx->state = failed;
139                    error("too many )");
140                    break;
141                }
142                ctx->sp = ctx->sp->prev;
143                break;
144            case '"':
145                ctx->state = string;
146                ctx->p = s + 1;
147                break;
148            default:
149                ctx->p = s;
150                ctx->state = token;
151                break;
152            }
153            break;
154        case token:
155            switch (*s) {
156            case ' ':
157            case '\t':
158            case '\r':
159            case '\n':
160                ctx->state = idle;
161                end_string(ctx, s);
162                break;
163            case '(':
164            case ')':
165            case '"':
166                ctx->state = idle;
167                end_string(ctx, s);
168                continue;
169            default:
170                break;
171            }
172            break;
173        case string:
174            switch (*s) {
175            case '\r':
176            case '\n':
177                ctx->state = failed;
178                error("newline in string");
179                break;
180            case '"':
181                ctx->state = idle;
182                end_string(ctx, s);
183                break;
184            case '\\':
185                ctx->state = escape;
186                break;
187            default:
188                break;
189            }
190            break;
191        case escape:
192            switch (*s) {
193            case '\r':
194            case '\n':
195                ctx->state = failed;
196                error("newline in string");
197                break;
198            default:
199                ctx->state = string;
200                break;
201            }
202            break;
203        case failed:
204            return 0;
205        default:
206            abort();
207        }
208        s++;
209    }
210
211    switch (ctx->state) {
212    case token:
213    case string:
214    case escape:
215        add_string(ctx, s);
216        break;
217    default:
218        break;
219    }
220
221    return 1;
222}
223
224
225/* ----- Dumping ----------------------------------------------------------- */
226
227
228static void do_dump_expr(const struct expr *e, unsigned depth)
229{
230    bool need_nl = 0;
231
232    if (depth)
233        printf("%*s(", (depth - 1) * 2, "");
234    while (e) {
235        if (e->s) {
236            if (need_nl) {
237                printf("\n%*s", depth * 2, "");
238                need_nl = 0;
239            }
240            printf("\"%s\" ", e->s); /* @@@ escaping */
241        }
242        if (e->e) {
243            putchar('\n');
244            do_dump_expr(e->e, depth + 1);
245            need_nl = 1;
246        }
247        e = e->next;
248    }
249    if (depth)
250        putchar(')');
251}
252
253
254void dump_expr(const struct expr *e)
255{
256    do_dump_expr(e, 0);
257    putchar('\n');
258}
259
260
261/* ----- Cleanup ----------------------------------------------------------- */
262
263
264static void free_stack(struct sexpr_ctx *ctx)
265{
266    struct stack *prev;
267
268    while (ctx->sp != &ctx->stack) {
269        prev = ctx->sp->prev;
270        free(ctx->sp);
271        ctx->sp = prev;
272    }
273}
274
275
276void free_expr(struct expr *e)
277{
278    struct expr *next;
279
280    while (e) {
281        next = e->next;
282        if (e->s)
283            free(e->s);
284        else if (e->e)
285            free_expr(e->e);
286        free(e);
287        e = next;
288    }
289}
290
291
292/* ----- Parser creation --------------------------------------------------- */
293
294
295struct sexpr_ctx *sexpr_new(void)
296{
297    struct sexpr_ctx *ctx;
298
299    ctx = alloc_type(struct sexpr_ctx);
300    ctx->state = idle;
301    ctx->e = NULL;
302    ctx->p = NULL;
303    ctx->sp = &ctx->stack;
304    ctx->stack.next = &ctx->e;
305    ctx->stack.prev = NULL;
306    return ctx;
307}
308
309
310/* ----- Termination ------------------------------------------------------- */
311
312
313void sexpr_abort(struct sexpr_ctx *ctx)
314{
315    free_stack(ctx);
316    free_expr(ctx->e);
317    free(ctx);
318}
319
320
321bool sexpr_finish(struct sexpr_ctx *ctx, struct expr **res)
322{
323    if (ctx->sp != &ctx->stack) {
324        error("not enough )");
325        ctx->state = failed;
326    }
327    if (ctx->state != idle && ctx->state != failed)
328        error("invalid end state %d", ctx->state);
329    if (ctx->state != idle) {
330        sexpr_abort(ctx);
331        return 0;
332    }
333    if (res)
334        *res = ctx->e;
335    else
336        free_expr(ctx->e);
337    free(ctx);
338    return 1;
339}
340

Archive Download this file

Branches:
master



interactive