sexp.c 11.9 KB
Newer Older
Niels Möller's avatar
Niels Möller committed
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* sexp.c
 *
 * An implementation of Ron Rivest's S-expressions, used in spki.
 *
 * $Id$ */

/* lsh, an implementation of the ssh protocol
 *
 * Copyright (C) 1998 Niels Mller
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include "sexp.h"

28
29
#include "format.h"
#include "werror.h"
Niels Möller's avatar
Niels Möller committed
30
31
#include "xalloc.h"

32
33
34
#include <assert.h>
#include <stdarg.h>

Niels Möller's avatar
Niels Möller committed
35
#define CLASS_DEFINE
36
#include "sexp.h.x"
Niels Möller's avatar
Niels Möller committed
37
38
#undef CLASS_DEFINE

39
/* Defines int char_classes[0x100] */
Niels Möller's avatar
Niels Möller committed
40
#define CHAR_CLASSES_TABLE sexp_char_classes
41
#include "sexp_table.h"
Niels Möller's avatar
Niels Möller committed
42
#undef CHAR_CLASSES_TABLE
43

44
45
46
47
48
49
50
51
52
53
54
#include "sexp.c.x"

/* CLASS:
   (class
     (name sexp_string)
     (super sexp)
     (vars
       (display string)
       (contents string)))
*/

55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
/* For advanced format */
static struct lsh_string *do_format_simple_string(struct lsh_string *s,
						  int style)
{
  int quote_friendly = ( (~CHAR_control & ~CHAR_international)
			 | CHAR_escapable);
  
  switch(style)
    {
    case SEXP_TRANSPORT:
      fatal("Internal error!\n");
    case SEXP_CANONICAL:
      return ssh_format("%dS", s);
    case SEXP_INTERNATIONAL:
      quote_friendly |= CHAR_international;
      /* Fall through */
    case SEXP_ADVANCED:
      {
	int c;
	unsigned i;

	if (!s->length)
	  return ssh_format("\"\"");

	/* Compute the set of all character classes represented in the string */
	for (c = 0, i = 0; i < s->length; i++)
Niels Möller's avatar
Niels Möller committed
81
	  c |= sexp_char_classes[s->data[i]];
82

Niels Möller's avatar
Niels Möller committed
83
	if (! ( (sexp_char_classes[s->data[0]] & CHAR_digit)
84
85
86
87
88
89
90
91
92
93
94
95
96
		|| (c & ~(CHAR_alpha | CHAR_digit | CHAR_punctuation))))
	  /* Output token, without any quoting at all */
	  return lsh_string_dup(s);

	if (! (c & ~quote_friendly))
	  {
	    /* Count the number of characters needing escape */
	    unsigned length = s->length;
	    unsigned i;
	    struct lsh_string *res;
	    UINT8 *dst;
	    
	    for (i = 0; i<s->length; i++)
Niels Möller's avatar
Niels Möller committed
97
	      if (sexp_char_classes[s->data[i]] & CHAR_escapable)
98
99
100
101
		length++;

	    res = ssh_format("\"%lr\"", length, &dst);
	    for (i=0; i<s->length; i++)
Niels Möller's avatar
Niels Möller committed
102
	      if (sexp_char_classes[s->data[i]] & CHAR_escapable)
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
		{
		  *dst++ = '\\';
		  switch(s->data[i])
		    {
		    case '\b':
		      *dst++ = 'b';
		      break;
		    case '\t':
		      *dst++ = 't';
		      break;
		    case '\v':
		      *dst++ = 'v';
		      break;
		    case '\n':
		      *dst++ = 'n';
		      break;
		    case '\f':
		      *dst++ = 'f';
		      break;
		    case '\r':
		      *dst++ = 'r';
		      break;
		    case '\"':
		      *dst++ = '\"';
		      break;
		    case '\\':
		      *dst++ = '\\';
		      break;
		    default:
		      fatal("Internal error!\n");
		    }
		}
	      else
		*dst++ = s->data[i];

	    assert(dst == (res->data + 1 + length));

	    return res;
	  }
	/* Base 64 string */
	return encode_base64(s, "||", 0);
      }
    default:
      fatal("do_format_sexp_string: Unknown output style.\n");
    }
}
  
150
static struct lsh_string *do_format_sexp_string(struct sexp *s, int style)
Niels Möller's avatar
Niels Möller committed
151
152
153
154
155
{
  CAST(sexp_string, self, s);

  switch(style)
    {
156
157
    case SEXP_TRANSPORT:
      fatal("Internal error!\n");
Niels Möller's avatar
Niels Möller committed
158
    case SEXP_ADVANCED:
159
    case SEXP_INTERNATIONAL:
Niels Möller's avatar
Niels Möller committed
160
161
    case SEXP_CANONICAL:
      if (self->display)
162
163
164
	return ssh_format("[%lfS]%lfS",
			  do_format_simple_string(self->display, style),
			  do_format_simple_string(self->contents, style));
Niels Möller's avatar
Niels Möller committed
165
      else
166
167
	return ssh_format("%lfS",
			  do_format_simple_string(self->contents, style));
Niels Möller's avatar
Niels Möller committed
168
169
170
171
172
    default:
      fatal("do_format_sexp_string: Unknown output style.\n");
    }
}

173
/* Consumes its args (display may be NULL) */
Niels Möller's avatar
Niels Möller committed
174
struct sexp *make_sexp_string(struct lsh_string *d, struct lsh_string *c)
175
176
177
178
{
  NEW(sexp_string, s);

  s->super.format = do_format_sexp_string;
179
  s->super.iter = NULL;
180
181
182
183
184
185
186
  
  s->display = d;
  s->contents = c;
  
  return &s->super;
}

187

188
static struct lsh_string *
189
do_format_sexp_nil(struct sexp *ignored UNUSED, int style UNUSED)
190
191
192
193
{
  return ssh_format("()");
}

194
195
196
/* Forward declaration */
static struct sexp_iterator *make_iter_cons(struct sexp *s);

197
struct sexp_cons sexp_nil =
198
199
{ { STATIC_HEADER, make_iter_cons, do_format_sexp_nil },
  &sexp_nil.super, &sexp_nil };
200
201
202

#define SEXP_NIL (&sexp_nil.super)

203
204
205
/* CLASS:
   (class
     (name sexp_iter_cons)
206
     (super sexp_iterator)
207
208
209
210
     (vars
       (p object sexp_cons)))
*/

211
static struct sexp *do_cons_get(struct sexp_iterator *c)
212
{
213
214
215
216
  CAST(sexp_iter_cons, i, c);
  return (i->p != &sexp_nil) ? NULL : i->p->car;
}

217
static void do_cons_set(struct sexp_iterator *c, struct sexp *e)
218
219
220
221
222
223
224
{
  CAST(sexp_iter_cons, i, c);
  assert (i->p != &sexp_nil);

  i->p->car = e;
}

225
static void do_cons_next(struct sexp_iterator *c)
226
227
228
229
230
{
  CAST(sexp_iter_cons, i, c);
  i->p = i->p->cdr;
}

231
static struct sexp_iterator *make_iter_cons(struct sexp *s)
232
233
234
235
236
237
{
  CAST(sexp_cons, c, s);
  NEW(sexp_iter_cons, iter);

  iter->super.get = do_cons_get;
  iter->super.set = do_cons_set;
238
239
  iter->super.next = do_cons_next;
  iter->p = c;
240
241
  
  return &iter->super;
242
243
}

244
245
static struct lsh_string *do_format_sexp_tail(struct sexp_cons *c, int style)
{
246
247
248
  int use_space = 0;
  
  if (c == &sexp_nil)
249
250
251
252
253
254
255
    return ssh_format(")");

  switch(style)
    {
    case SEXP_TRANSPORT:
      fatal("Internal error!\n");
    case SEXP_ADVANCED:
256
257
258
    case SEXP_INTERNATIONAL:
      use_space = 1;
      /* Fall through */
259
    case SEXP_CANONICAL:
260
      return ssh_format(use_space ? " %ls%ls" : "%ls%ls",
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
			sexp_format(c->car, style),
			do_format_sexp_tail(c->cdr, style));
    default:
      fatal("do_format_sexp_tail: Unknown output style.\n");
    }
}

static struct lsh_string *do_format_sexp_cons(struct sexp *s, int style)
{
  CAST(sexp_cons, self, s);

  switch(style)
    {
    case SEXP_TRANSPORT:
      fatal("Internal error!\n");
    case SEXP_ADVANCED:
277
    case SEXP_INTERNATIONAL:
278
279
280
281
282
283
284
285
286
287
288
289
    case SEXP_CANONICAL:
      return ssh_format("(%ls", do_format_sexp_tail(self, style));
    default:
      fatal("do_format_sexp_tail: Unknown output style.\n");
    }
}

struct sexp *sexp_c(struct sexp *car, struct sexp_cons *cdr)
{
  NEW(sexp_cons, c);

  c->super.format = do_format_sexp_cons;
290
  c->super.iter = make_iter_cons;
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
  
  c->car = car;
  c->cdr = cdr;

  return &c->super;
}

/* CLASS:
   (class
     (name sexp_vector)
     (super sexp)
     (vars
       ; FIXME: With better var-array support, this
       ; could use an embedded var-array instead.
       (elements object object_list)))
*/

308
309
310
/* CLASS:
   (class
     (name sexp_iter_vector)
311
     (super sexp_iterator)
312
     (vars
313
       (l object object_list)
314
315
316
       (i . unsigned)))
*/

317
static struct sexp *do_vector_get(struct sexp_iterator *c)
318
319
320
321
322
323
324
325
326
327
{
  CAST(sexp_iter_vector, i, c);
  if (i->i < LIST_LENGTH(i->l))
    {
      CAST(sexp, res, LIST(i->l)[i->i]);
      return res;
    }
  return NULL;
}

328
static void do_vector_set(struct sexp_iterator *c, struct sexp *e)
329
330
331
332
333
334
335
{
  CAST(sexp_iter_vector, i, c);
  assert(i->i < LIST_LENGTH(i->l));

  LIST(i->l)[i->i] = &e->super;
}

336
static void do_vector_next(struct sexp_iterator *c)
337
338
339
340
341
342
{
  CAST(sexp_iter_vector, i, c);
  if (i->i < LIST_LENGTH(i->l))
    i->i++;
}

343
static struct sexp_iterator *make_iter_vector(struct sexp *s)
344
345
346
347
348
349
{
  CAST(sexp_vector, v, s);
  NEW(sexp_iter_vector, iter);

  iter->super.get = do_vector_get;
  iter->super.set = do_vector_set;  
350
  iter->super.next = do_vector_next;
351

352
  iter->l = v->elements;
353
  iter->i = 0;
354
355

  return &iter->super;
356
357
}

358
359
360
361
362
363
static struct lsh_string *do_format_sexp_vector(struct sexp *e, int style)
{
  CAST(sexp_vector, v, e);

  unsigned i;
  UINT32 size;
364
  int use_space = 0;
365
366
367
368
369
370
371
372
373
  
  struct lsh_string **elements = alloca(LIST_LENGTH(v->elements)
					* sizeof(struct lsh_string *) );
  
  switch(style)
    {
    case SEXP_TRANSPORT:
      fatal("Internal error!\n");
    case SEXP_ADVANCED:
374
375
376
    case SEXP_INTERNATIONAL:
      use_space = 1;
      /* Fall through */
377
378
379
380
381
382
    case SEXP_CANONICAL:
      {
	struct lsh_string *res;
	UINT8 *dst;
	
	assert(LIST_LENGTH(v->elements));
383
	for (i = 0, size = 2; i<LIST_LENGTH(v->elements); i++)
384
385
386
387
388
389
	  {
	    CAST_SUBTYPE(sexp, o, LIST(v->elements)[i]);
	    
	    elements[i] = sexp_format(o, style);
	    size += elements[i]->length;
	  }
390
391
392

	if (use_space)
	  size += LIST_LENGTH(v->elements) - 1;
393
	
394
	res = lsh_string_alloc(size);
395
396
397
398
399
	dst = res->data;
	
	*dst++ = '(';
	for (i = 0; i<LIST_LENGTH(v->elements); i++)
	  {
400
401
402
	    if (i && use_space)
	      *dst++ = ' ';
	    
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
	    memcpy(dst, elements[i]->data, elements[i]->length);
	    dst += elements[i]->length;
	    
	    lsh_string_free(elements[i]);
	  }
	*dst++ = ')';
	
	assert(dst == (res->data + res->length));
	
	return res;
      }
    default:
      fatal("do_format_sexp_vector: Unknown output style.\n");
    }
}

Niels Möller's avatar
Niels Möller committed
419
420
421
422
423
424
425
426
427
428
429
430
struct sexp *sexp_v(struct object_list *l)
{
  NEW(sexp_vector, v);

  v->super.format = do_format_sexp_vector;
  v->super.iter = make_iter_vector;
  
  v->elements = l;

  return &v->super;
}

431
432
433
434
435
436
437
438
439
440
struct sexp *sexp_l(unsigned n, ...)
{
  va_list args;

  va_start(args, n);

  if (!n)
    {
      assert(va_arg(args, int) == -1);
      va_end(args);
441
      return SEXP_NIL;
442
443
444
    }
  else
    {
Niels Möller's avatar
Niels Möller committed
445
      struct sexp *v = sexp_v(make_object_listv(n, args));
446
      
447
448
      va_end(args);

Niels Möller's avatar
Niels Möller committed
449
      return v;
450
451
452
    }
}

453
struct sexp *sexp_a(const int a)
454
455
456
457
{
  return make_sexp_string(NULL, ssh_format("%la", a));
}

458
struct sexp *sexp_z(const char *s)
459
460
461
462
463
{
  return make_sexp_string(NULL, ssh_format("%lz", s));
}

/* mpz->atom */
464
struct sexp *sexp_n(const mpz_t n)
465
466
467
468
{
  return make_sexp_string(NULL, ssh_format("%ln", n));
}

469
struct sexp *sexp_sn(const mpz_t n)
470
{
471
  (void) n;
472
473
474
475
476
477
478
479
  fatal("sexp_sn: Signed numbers are not supported.\n");
}
    
struct lsh_string *sexp_format(struct sexp *e, int style)
{
  switch(style)
    {
    case SEXP_TRANSPORT:
480
      return encode_base64(sexp_format(e, SEXP_CANONICAL), "{}", 1);
481
    case SEXP_CANONICAL:
482
483
484
485
    case SEXP_ADVANCED:
    case SEXP_INTERNATIONAL:
      /* NOTE: Check for NULL here? I don't think so. */
      return SEXP_FORMAT(e, style);
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
    default:
      fatal("sexp_format: Unknown output style.\n");
    }
}

static void encode_base64_group(UINT32 n, UINT8 *dest)
{
  static const UINT8 digits[64] =
    "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdef"
    "ghijklmnopqrstuvwxyz0123456789+/";
  unsigned i;

  for (i = 0; i<4; i++)
    {
      dest[3 - i] = digits[n & 0x3f];
      n >>= 6;
    }
}

505
struct lsh_string *encode_base64(struct lsh_string *s,
506
				 const char *delimiters,
507
				 int free)				 
508
509
510
{
  UINT32 full_groups = (s->length) / 3;
  unsigned last = (s->length) % 3;
511
  unsigned length =  (full_groups + !!last) * 4;
512
  UINT8 *src = s->data;
513
514
515
516
517
518
519
  UINT8 *dst;
    
  struct lsh_string *res
    = (delimiters
       ? ssh_format("%c%lr%c", delimiters[0], length, &dst, delimiters[1])
       : ssh_format("%lr", length, &dst));
  
520
521
522
  if (full_groups)
    {
      unsigned i;
Niels Möller's avatar
Niels Möller committed
523
      
524
      /* Loop over all but the last group. */
525
      for (i=0; i<full_groups; dst += 4, i++)
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
	{
	  encode_base64_group( ( (*src++) << 16)
			       | ( (*src++) << 8)
			       | (*src++), dst);
	}
    }
  switch(last)
    {
    case 0:
      /* Finished */
      break;
    case 1:
      encode_base64_group( (*src++) << 16, dst);
      dst += 2;
      *dst++ = '=';
      *dst++ = '=';
      break;
    case 2:
      encode_base64_group( ( (*src++) << 16)
			   | ( (*src++) << 8), dst);
      dst += 3;
      *dst++ = '=';
      break;
    default:
      fatal("encode_base64: Internal error!\n");
    }

553
  assert( (dst + !!delimiters) == (res->data + res->length));
554
555
556
557
558
559

  if (free)
    lsh_string_free(s);
  
  return res;
}
560

561
int sexp_nullp(const struct sexp *e)
562
563
564
565
{
  return (e == SEXP_NIL);
}

566
int sexp_atomp(const struct sexp *e)
567
568
569
570
571
572
{
  return !e->iter;
}