1 : /*
2 : * Copyright (c) 2013 The Native Client Authors. All rights reserved.
3 : * Use of this source code is governed by a BSD-style license that can be
4 : * found in the LICENSE file.
5 : */
6 :
7 : #include <ctype.h>
8 : #include <stdio.h>
9 : #include <stdlib.h>
10 : #include <string.h>
11 :
12 : #include "native_client/tests/lock_manager/nacl_test_util_sexp.h"
13 :
14 : #include "native_client/src/shared/platform/nacl_check.h"
15 :
16 : /*
17 : * A basic lisp parser. The execution part is separate (see
18 : * nacl_file_lock-test.c) since the execution model wires in special
19 : * forms that are non-standard (event matchers).
20 : */
21 :
22 : static int g_NaClSexpVerbosity = 0;
23 :
24 0 : void NaClSexpSetVerbosity(int v) {
25 0 : g_NaClSexpVerbosity = v;
26 0 : }
27 :
28 : void NaClSexpIncVerbosity(void) {
29 0 : ++g_NaClSexpVerbosity;
30 0 : }
31 :
32 1976 : static void NaClSexpIoUngetc(struct NaClSexpIo *p, int ch) {
33 1976 : if (p->num_unget == 2) {
34 0 : fprintf(stderr, "NaClSexpIoUngetc: internal error: too many ugetc\n");
35 0 : abort();
36 : }
37 1976 : p->ungetbuf[p->num_unget++] = ch;
38 1976 : }
39 :
40 6002 : static int NaClSexpIoReadCharSkipComments(struct NaClSexpIo *p) {
41 6002 : int ch;
42 :
43 6002 : if (p->num_unget > 0) {
44 1976 : return p->ungetbuf[--p->num_unget];
45 : }
46 4026 : ch = getc(p->iob);
47 8044 : if (EOF == ch || ';' != ch) {
48 4020 : return ch;
49 : }
50 450 : while ((EOF != (ch = getc(p->iob))) && '\n' != ch) {
51 216 : continue; /* skip */
52 : }
53 6 : return ch;
54 6002 : }
55 :
56 8 : void NaClSexpIoCtor(struct NaClSexpIo *self, FILE *iob,
57 8 : void (*err_func)(struct NaClSexpIo *self, char const *r)) {
58 8 : self->line_num = 1;
59 8 : self->iob = iob;
60 8 : self->num_unget = 0;
61 8 : self->on_error = err_func;
62 8 : }
63 :
64 0 : void NaClSexpIoSetIob(struct NaClSexpIo *self, FILE *iob) {
65 0 : self->iob = iob;
66 0 : }
67 :
68 1976 : static int NaClSexpIoReadCharSkipSpaces(struct NaClSexpIo *p) {
69 1976 : int ch;
70 8808 : while (EOF != (ch = NaClSexpIoReadCharSkipComments(p)) && isspace(ch)) {
71 1444 : if ('\n' == ch) {
72 216 : ++p->line_num;
73 216 : }
74 1444 : }
75 1976 : return ch;
76 : }
77 :
78 292 : static char *ReadToken(struct NaClSexpIo *p) {
79 292 : size_t space = 10;
80 292 : char *str = malloc(space);
81 292 : size_t used = 0;
82 292 : int ch;
83 :
84 876 : CHECK(NULL != str);
85 2258 : while (EOF != (ch = NaClSexpIoReadCharSkipComments(p)) &&
86 3656 : !isspace(ch) && ')' != ch) {
87 1674 : if (used == space) {
88 8 : char *new_str = realloc(str, 2 * space);
89 8 : if (NULL == new_str) {
90 0 : (*p->on_error)(p, "out of memory reading string token");
91 0 : }
92 8 : space *= 2;
93 8 : str = new_str;
94 8 : }
95 1674 : str[used++] = ch;
96 1674 : }
97 292 : if (EOF != ch) {
98 292 : NaClSexpIoUngetc(p, ch);
99 292 : }
100 292 : if (used == space) {
101 0 : char *new_str = realloc(str, space+1);
102 0 : if (NULL == new_str) {
103 0 : (*p->on_error)(p,
104 : "out-of-memory reading string token (null termination)");
105 0 : }
106 0 : str = new_str;
107 0 : ++space;
108 0 : }
109 292 : str[used++] = '\0';
110 292 : return str;
111 : }
112 :
113 308 : static int ReadInteger(struct NaClSexpIo *p) {
114 308 : int base = -1; /* unknown */
115 308 : int ch;
116 308 : int val = 0;
117 308 : int negative = 0;
118 :
119 924 : while (EOF != (ch = NaClSexpIoReadCharSkipComments(p))) {
120 924 : if (-1 == base && '-' == ch) {
121 0 : negative = 1;
122 0 : base = 0;
123 924 : } else if (base <= 0 && '0' == ch) {
124 156 : base = 8;
125 768 : } else if (base <= 0 && isdigit(ch)) {
126 152 : base = 10;
127 152 : val = ch - '0';
128 616 : } else if (8 == base && 'x' == ch) {
129 0 : base = 16;
130 308 : } else if (16 == base && isxdigit(ch)) {
131 0 : val *= 16;
132 0 : if (isalpha(ch) && isupper(ch)) {
133 0 : ch = tolower(ch);
134 0 : }
135 0 : if (isalpha(ch)) {
136 0 : val += ch - 'a' + 10;
137 0 : } else {
138 0 : val += ch - '0';
139 : }
140 460 : } else if (10 == base && isdigit(ch)) {
141 0 : val *= 10;
142 0 : val += ch - '0';
143 464 : } else if (8 == base && isdigit(ch) && ch < '8') {
144 0 : val *= 8;
145 0 : val += ch - '0';
146 0 : } else {
147 308 : NaClSexpIoUngetc(p, ch);
148 308 : break;
149 : }
150 308 : }
151 924 : return negative ? -val : val;
152 : }
153 :
154 : void NaClSexpPrintConsIntern(FILE *iob, struct NaClSexpCons *c);
155 :
156 0 : void NaClSexpPrintCons(FILE *iob, struct NaClSexpCons *c) {
157 0 : putc('(', iob);
158 0 : NaClSexpPrintConsIntern(iob, c);
159 0 : }
160 :
161 120 : void NaClSexpPrintNode(FILE *iob, struct NaClSexpNode *n) {
162 120 : if (NULL == n) {
163 52 : fprintf(iob, "nil");
164 52 : return;
165 : }
166 188 : switch (n->type) {
167 : case kNaClSexpCons:
168 0 : putc('(', iob);
169 0 : if (g_NaClSexpVerbosity) {
170 0 : fprintf(iob, "[cons]");
171 0 : }
172 0 : NaClSexpPrintConsIntern(iob, n->u.cval);
173 0 : break;
174 : case kNaClSexpInteger:
175 68 : if (g_NaClSexpVerbosity) {
176 0 : fprintf(iob, "[int]");
177 0 : }
178 68 : fprintf(iob, "%"NACL_PRId64, n->u.ival);
179 68 : break;
180 : case kNaClSexpToken:
181 0 : if (g_NaClSexpVerbosity) {
182 0 : fprintf(iob, "[token]");
183 0 : }
184 0 : fprintf(iob, "%s", n->u.tval);
185 0 : break;
186 : }
187 120 : }
188 :
189 0 : void NaClSexpPrintConsIntern(FILE *iob, struct NaClSexpCons *c) {
190 0 : if (NULL == c) {
191 0 : putc(')', iob);
192 0 : return;
193 : }
194 0 : NaClSexpPrintNode(iob, c->car);
195 0 : if (NULL == c->cdr) {
196 0 : putc(')', iob);
197 0 : } else {
198 0 : putc(' ', iob);
199 0 : NaClSexpPrintConsIntern(iob, c->cdr);
200 : }
201 0 : }
202 :
203 1072 : struct NaClSexpCons *NaClSexpReadList(struct NaClSexpIo *p) {
204 1072 : struct NaClSexpCons *c;
205 1072 : int ch = NaClSexpIoReadCharSkipSpaces(p);
206 1072 : if (EOF == ch) {
207 0 : (*p->on_error)(p, "Premature end of list");
208 0 : }
209 1072 : if (')' == ch) {
210 296 : return NULL;
211 : }
212 776 : c = malloc(sizeof *c);
213 2328 : CHECK(NULL != c);
214 776 : NaClSexpIoUngetc(p, ch);
215 776 : c->car = NaClSexpReadSexp(p);
216 776 : c->cdr = NaClSexpReadList(p);
217 776 : return c;
218 1072 : }
219 :
220 904 : struct NaClSexpNode *NaClSexpReadSexp(struct NaClSexpIo *p) {
221 904 : int ch = NaClSexpIoReadCharSkipSpaces(p);
222 904 : struct NaClSexpNode *n;
223 904 : int is_int;
224 :
225 904 : if (EOF == ch) {
226 8 : return NULL;
227 : }
228 896 : n = malloc(sizeof *n);
229 2688 : CHECK(NULL != n);
230 896 : if ('(' == ch) {
231 296 : n->type = kNaClSexpCons;
232 296 : n->u.cval = NaClSexpReadList(p);
233 296 : return n;
234 : }
235 600 : is_int = isdigit(ch);
236 600 : if ('-' == ch) {
237 0 : int next_ch = NaClSexpIoReadCharSkipComments(p);
238 0 : if (isdigit(next_ch)) {
239 0 : is_int = 1;
240 0 : } else {
241 : /* is token! */
242 : }
243 0 : NaClSexpIoUngetc(p, next_ch);
244 0 : }
245 600 : if (is_int) {
246 308 : NaClSexpIoUngetc(p, ch);
247 308 : n->type = kNaClSexpInteger;
248 308 : n->u.ival = ReadInteger(p);
249 308 : return n;
250 : }
251 292 : NaClSexpIoUngetc(p, ch);
252 292 : n->type = kNaClSexpToken;
253 292 : n->u.tval = ReadToken(p);
254 292 : if (strlen(n->u.tval) == 0) {
255 0 : printf("bad parse\n");
256 0 : free(n);
257 0 : return NULL;
258 : }
259 292 : return n;
260 904 : }
261 :
262 108 : static char *NaClSexpDupToken(char const *t) {
263 108 : char *nt = strdup(t);
264 108 : return nt;
265 : }
266 :
267 634 : struct NaClSexpNode *NaClSexpDupNode(struct NaClSexpNode *n) {
268 634 : struct NaClSexpNode *nn;
269 634 : if (NULL == n) {
270 0 : return NULL;
271 : }
272 634 : nn = malloc(sizeof *nn);
273 1902 : CHECK(NULL != nn);
274 1268 : nn->type = n->type;
275 1268 : switch (nn->type) {
276 : case kNaClSexpCons:
277 112 : nn->u.cval = NaClSexpDupCons(n->u.cval);
278 112 : break;
279 : case kNaClSexpInteger:
280 414 : nn->u.ival = n->u.ival;
281 414 : break;
282 : case kNaClSexpToken:
283 108 : nn->u.tval = NaClSexpDupToken(n->u.tval);
284 108 : break;
285 : }
286 634 : return nn;
287 634 : }
288 :
289 444 : struct NaClSexpCons *NaClSexpDupCons(struct NaClSexpCons *c) {
290 444 : struct NaClSexpCons *nc;
291 :
292 444 : if (NULL == c) {
293 112 : return NULL;
294 : }
295 332 : nc = malloc(sizeof *nc);
296 996 : CHECK(NULL != nc);
297 332 : nc->car = NaClSexpDupNode(c->car);
298 332 : nc->cdr = NaClSexpDupCons(c->cdr);
299 332 : return nc;
300 444 : }
301 :
302 216 : struct NaClSexpCons *NaClSexpConsCons(struct NaClSexpNode *n,
303 216 : struct NaClSexpCons *c) {
304 216 : struct NaClSexpCons *cell;
305 :
306 216 : cell = malloc(sizeof *cell);
307 648 : CHECK(NULL != cell);
308 216 : cell->car = n;
309 216 : cell->cdr = c;
310 216 : return cell;
311 : }
312 :
313 0 : static struct NaClSexpCons *NaClSexpAppendIntern(struct NaClSexpCons *f,
314 0 : struct NaClSexpCons *rest) {
315 0 : if (f == NULL) {
316 0 : return rest;
317 : }
318 0 : rest = NaClSexpAppendIntern(f->cdr, rest);
319 :
320 0 : return NaClSexpConsCons(NaClSexpDupNode(f->car), rest);
321 0 : }
322 :
323 0 : struct NaClSexpCons *NaClSexpAppend(struct NaClSexpCons *first,
324 0 : struct NaClSexpCons *second) {
325 0 : struct NaClSexpCons *n = NaClSexpDupCons(second);
326 :
327 0 : return NaClSexpAppendIntern(first, n);
328 : }
329 :
330 : void NaClSexpFreeNode(struct NaClSexpNode *n);
331 :
332 1540 : void NaClSexpFreeCons(struct NaClSexpCons *c) {
333 1540 : if (NULL == c) {
334 440 : return;
335 : }
336 1100 : NaClSexpFreeNode(c->car);
337 1100 : NaClSexpFreeCons(c->cdr);
338 2640 : }
339 :
340 1794 : void NaClSexpFreeNode(struct NaClSexpNode *n) {
341 1794 : if (NULL == n) {
342 96 : return;
343 : }
344 3492 : switch (n->type) {
345 : case kNaClSexpCons:
346 440 : NaClSexpFreeCons(n->u.cval);
347 440 : break;
348 : case kNaClSexpInteger:
349 930 : break;
350 : case kNaClSexpToken:
351 328 : free(n->u.tval);
352 328 : break;
353 : }
354 1794 : }
355 :
356 790 : int NaClSexpConsp(struct NaClSexpNode *n) {
357 1580 : return NULL != n && kNaClSexpCons == n->type;
358 790 : }
359 :
360 530 : int NaClSexpIntp(struct NaClSexpNode *n) {
361 1060 : return NULL != n && kNaClSexpInteger == n->type;
362 530 : }
363 :
364 297 : int NaClSexpTokenp(struct NaClSexpNode *n) {
365 594 : return NULL != n && kNaClSexpToken == n->type;
366 297 : }
367 :
368 549 : struct NaClSexpCons *NaClSexpNodeToCons(struct NaClSexpNode *n) {
369 549 : return n->u.cval;
370 : }
371 :
372 526 : int64_t NaClSexpNodeToInt(struct NaClSexpNode const *n) {
373 526 : return n->u.ival;
374 : }
375 :
376 297 : char const *NaClSexpNodeToToken(struct NaClSexpNode const *n) {
377 297 : return n->u.tval;
378 : }
379 :
380 108 : struct NaClSexpNode *NaClSexpNodeWrapCons(struct NaClSexpCons *c) {
381 108 : struct NaClSexpNode *n = malloc(sizeof *n);
382 :
383 324 : CHECK(NULL != n);
384 108 : n->type = kNaClSexpCons;
385 108 : n->u.cval = c;
386 108 : return n;
387 : }
388 :
389 292 : struct NaClSexpNode *NaClSexpNodeWrapInt(int64_t num) {
390 292 : struct NaClSexpNode *n = malloc(sizeof *n);
391 :
392 876 : CHECK(NULL != n);
393 292 : n->type = kNaClSexpInteger;
394 292 : n->u.ival = num;
395 292 : return n;
396 : }
397 :
398 0 : struct NaClSexpNode *NaClSexpNodeWrapToken(char *t) {
399 0 : struct NaClSexpNode *n = malloc(sizeof *n);
400 :
401 0 : CHECK(NULL != n);
402 0 : n->type = kNaClSexpToken;
403 0 : n->u.tval = t;
404 0 : return n;
405 : }
406 :
407 0 : struct NaClSexpCons *NaClSexpConsWrapNode(struct NaClSexpNode *n) {
408 0 : struct NaClSexpCons *c = malloc(sizeof *c);
409 :
410 0 : CHECK(NULL != c);
411 0 : c->car = n;
412 0 : c->cdr = NULL;
413 0 : return c;
414 : }
415 :
416 407 : size_t NaClSexpListLength(struct NaClSexpCons const *c) {
417 407 : size_t len;
418 :
419 2786 : for (len = 0; c != NULL; c = c->cdr)
420 986 : ++len;
421 407 : return len;
422 : }
|
