See ChangeLog: Mon Jul 12 14:55:34 CEST 1999 Werner Koch
[libgcrypt.git] / src / sexp.c
1 /* sexp.c  -  Sex^H^H-Expression handling
2  *      Copyright (C) 1999 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
6  * GnuPG is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * GnuPG is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21
22 /****************
23  * TODO:
24  *  - implement reference counting to defere freeing of
25  *    data and make copies of the data on demand.
26  *    --> do we really need this?
27  *
28  */
29
30 #include <config.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <stdarg.h>
35 #include <ctype.h>
36 #include <assert.h>
37
38 #define GCRYPT_NO_MPI_MACROS 1
39 #include "g10lib.h"
40 #include "util.h"
41 #include "memory.h"
42
43
44 /* FIXME: We should really have the m_lib functions to allow
45  *        overriding of the default malloc functions
46  * For now use this kludge: */
47 #define m_lib_alloc        m_alloc
48 #define m_lib_alloc_clear  m_alloc_clear
49 #define m_lib_free         m_free
50
51
52
53
54 #if 0
55 struct sexp_node;
56 typedef struct sexp_node *NODE;
57
58 struct gcry_sexp {
59     int orig_format;  /* format which we used to create this object */
60     NODE sexp;        /* a NULL indicates an empty list */
61 };
62 #else
63 typedef struct gcry_sexp *NODE;
64 #endif
65
66
67 enum node_types { ntLIST, ntDATA, ntMPI };
68
69 struct gcry_sexp {
70     NODE next;
71     NODE up;        /* helper needed for faster traversal */
72     enum node_types type;
73     union {
74         NODE list;
75         GCRY_MPI mpi;
76         struct {
77             size_t len;
78             byte  d[1];
79         } data;
80     } u;
81 };
82
83
84 static void
85 dump_mpi( GCRY_MPI a )
86 {
87     char buffer[1000];
88     size_t n = 1000;
89
90     if( gcry_mpi_print( GCRYMPI_FMT_HEX, buffer, &n, a ) )
91         fputs("[MPI too large to print]", stderr );
92     else
93         fputs( buffer, stderr );
94 }
95
96
97 static void
98 do_dump_list( NODE node, int indent )
99 {
100     for( ; node; node = node->next ) {
101         switch( node->type ) {
102           case ntLIST:
103             if( indent )
104                 putc('\n', stderr);
105             fprintf(stderr, "%*s(", indent, "");
106             do_dump_list( node->u.list, indent+1 );
107             putc(')', stderr);
108             break;
109           case ntDATA:
110             if( !node->u.data.len )
111                 fputs("EMPTY", stderr );
112             else
113                 print_string(stderr, node->u.data.d, node->u.data.len, ')');
114             putc(' ', stderr);
115             break;
116           case ntMPI:
117             dump_mpi( node->u.mpi );
118             putc(' ', stderr);
119             break;
120         }
121         if( !indent )
122             putc('\n', stderr);
123     }
124 }
125
126 static void
127 dump_sexp( NODE node )
128 {
129     do_dump_list( node, 0 );
130 }
131
132
133 /****************
134  * Create a new SEXP element (data)
135  */
136 GCRY_SEXP
137 gcry_sexp_new( const char *buffer, size_t length )
138 {
139     NODE node;
140
141     node = m_alloc_clear( sizeof *node + length );
142     node->type = ntDATA;
143     node->u.data.len = length;
144     memcpy(node->u.data.d, buffer, length );
145     return node;
146 }
147
148 /****************
149  * Release resource of the given SEXP object.
150  */
151 void
152 gcry_sexp_release( GCRY_SEXP sexp )
153 {
154 }
155
156
157
158
159 /****************
160  * Make a pair from items a and b
161  */
162 GCRY_SEXP
163 gcry_sexp_cons( GCRY_SEXP a, GCRY_SEXP b )
164 {
165     NODE head;
166
167     head = m_alloc_clear( sizeof *head );
168     head->type = ntLIST;
169     head->u.list = a;
170     a->up = head;
171     a->next = b;
172     b->up = head;
173     return head;
174 }
175
176 /****************
177  * Make a list from all items, the end of list is indicated by a NULL
178  */
179 GCRY_SEXP
180 gcry_sexp_vlist( GCRY_SEXP a, ... )
181 {
182     NODE head, tail, node;
183     va_list arg_ptr ;
184
185     head = m_alloc_clear( sizeof *node );
186     head->type = ntLIST;
187     head->u.list = a;
188     a->up = head;
189     tail = a;
190
191     va_start( arg_ptr, a ) ;
192     while( (node = va_arg( arg_ptr, NODE )) ) {
193         tail->next = node;
194         node->up = head;
195         tail = node;
196     }
197
198     va_end( arg_ptr );
199     return head;
200 }
201
202
203 /****************
204  * Locate data in a list. Data must be the first item in the list.
205  * Returns: The sublist with that Data (don't modify it!)
206  */
207 GCRY_SEXP
208 gcry_sexp_find_token( GCRY_SEXP list, const char *tok, size_t toklen )
209 {
210     NODE node;
211
212     for( node=list ; node; node = node->next )
213       {
214         switch( node->type ) {
215           case ntLIST: {
216                 NODE n = gcry_sexp_find_token( node->u.list, tok, toklen );
217                 if( n )
218                     return n;
219             }
220             break;
221           case ntDATA:
222             if( node == list
223                 && node->u.data.len == toklen
224                 && !memcmp( node->u.data.d, tok, toklen ) )
225               {
226                 return node;
227               }
228             break;
229           case ntMPI:
230             break;
231         }
232       }
233
234     return NULL;
235 }
236
237
238 /****************
239  * Enumerate all objects in the list.  Ther firts time you call this, pass
240  * the address of a void pointer initialized to NULL.  Then don't touch this
241  * variable anymore but pass it verbatim to the function; you will get
242  * all lists back in turn. End of lists is indicated by a returned NIL in
243  * whic case you should not continue to use this function
244  * (it would wrap around).  If you decide to cancel the operation before
245  * the final NIL you vae to release the context by calling the function
246  * with a the context but a LIST set to NULL.
247  * Note that this function returns only lists and not single objects.
248  */
249 GCRY_SEXP
250 gcry_sexp_enum_lists( GCRY_SEXP list, void **context )
251 {
252     NODE node;
253
254     if( !list ) {
255         /* we are lucky that we can hold all information in the pointer
256          * value ;-) - so there is no need to release any memory */
257         *context = NULL;
258         return NULL;
259     }
260     if( !*context )  /* start enumeration */
261         node = list;
262     else
263         node = *context;
264
265
266     for( ; node; node = node->next ) {
267         if( node->type == ntLIST ) {
268             node = node->u.list;
269             *context = node; /* store our context */
270             return node;
271         }
272     }
273
274     /* release resources and return nil */
275     return gcry_sexp_enum_lists( NULL, context );
276 }
277
278
279 /****************
280  * cdr the mpi from the list or NULL if there is no MPI.
281  * This function tries to convert plain data to an MPI.
282  */
283 MPI
284 gcry_sexp_cdr_mpi( GCRY_SEXP list )
285 {
286
287 }
288
289
290 /****************
291  * Scan the provided buffer and return the S expression in our internal
292  * format.  Returns a newly allocated expression.  If erroff is not NULL and
293  * a parsing error has occured, the offset into buffer will be returned.
294  */
295 int
296 gcry_sexp_sscan( GCRY_SEXP *retsexp, const char *buffer,
297                                      size_t length, size_t *erroff )
298 {
299     static const char tokenchars[] = "abcdefghijklmnopqrstuvwxyz"
300                                      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
301                                      "0123456789-./_:*+=";
302     const char *p;
303     size_t n;
304     NODE head, tail, node;
305     const char *digptr=NULL;
306     const char *quoted=NULL;
307     const char *tokenp=NULL;
308     const char *hexfmt=NULL;
309     const char *base64=NULL;
310     const char *disphint=NULL;
311     int quoted_esc=0;
312     int datalen=0;
313     int first;
314
315     tail = head = NULL;
316     first = 0;
317     for(p=buffer,n=length; n; p++, n-- ) {
318         if( tokenp ) {
319             if( strchr( tokenchars, *p ) )
320                 continue;
321         }
322         if( quoted ) {
323             if( quoted_esc ) {
324                 switch( *p ) {
325                   case 'b': case 't': case 'v': case 'n': case 'f':
326                   case 'r': case '"': case '\'': case '\\':
327                     quoted_esc = 0;
328                     break;
329                   case '0': case '1': case '2': case '3': case '4':
330                   case '5': case '6': case '7':
331                     if( !(n > 2 && p[1] >= '0' && p[1] <= '7'
332                                 && p[2] >= '0' && p[2] <= '7') ) {
333                         *erroff = p - buffer;
334                         return -6;   /* invalid octal value */
335                     }
336                     p += 2; n -= 2;
337                     quoted_esc = 0;
338                     break;
339                   case 'x':
340                     if( !(n > 2 && isxdigit(p[1]) && isxdigit(p[2]) ) ) {
341                         *erroff = p - buffer;
342                         return -6;   /* invalid hex value */
343                     }
344                     p += 2; n -= 2;
345                     quoted_esc = 0;
346                     break;
347                   case '\r':  /* ignore CR[,LF] */
348                     if( n && p[1] == '\n' ) {
349                         p++; n--;
350                     }
351                     quoted_esc = 0;
352                     break;
353                   case '\n':  /* ignore LF[,CR] */
354                     if( n && p[1] == '\r' ) {
355                         p++; n--;
356                     }
357                     quoted_esc = 0;
358                     break;
359                   default:
360                     *erroff = p - buffer;
361                     return -6;   /* invalid quoted string escape */
362                 }
363             }
364             else if( *p == '\\' )
365                 quoted_esc = 1;
366             else if( *p == '\"' ) {
367                 /* fixme: add item */
368                 quoted = NULL;
369             }
370         }
371         else if( hexfmt ) {
372             if( *p == '#' )
373                hexfmt = NULL;
374         }
375         else if( base64 ) {
376             if( *p == '|' )
377                base64 = NULL;
378         }
379         else if( digptr ) {
380             if( isdigit(*p) )
381                 ;
382             else if( *p == ':' ) {
383                 if( !head ) {
384                     *erroff = 0;
385                     return -4;   /* not a list */
386                 }
387                 datalen = atoi( digptr ); /* fixme: check for overflow */
388                 digptr = NULL;
389                 if( datalen > n-1 ) {
390                     *erroff = p - buffer;
391                     return -2; /* buffer too short */
392                 }
393                 /* make a new list entry */
394                 node = m_alloc_clear( sizeof *node + datalen );
395                 if( first ) { /* stuff it into the first node */
396                     first = 0;
397                     node->up = tail;
398                     tail->u.list = node;
399                 }
400                 else {
401                     node->up = tail->up;
402                     tail->next = node;
403                 }
404                 tail = node;
405                 /* and fill in the value (we store the value in the node)*/
406                 node->type = ntDATA;
407                 node->u.data.len = datalen;
408                 memcpy(node->u.data.d, p+1, datalen );
409
410                 n -= datalen;
411                 p += datalen;
412             }
413             else if( *p == '\"' ) {
414                 digptr = NULL; /* we ignore the optional length */
415                 quoted = p;
416                 quoted_esc = 0;
417             }
418             else if( *p == '#' ) {
419                 digptr = NULL; /* we ignore the optional length */
420                 hexfmt = p;
421             }
422             else if( *p == '|' ) {
423                 digptr = NULL; /* we ignore the optional length */
424                 base64 = p;
425             }
426             else {
427                 *erroff = p - buffer;
428                 return -1;
429             }
430         }
431         else if( *p == '(' ) {
432             if( disphint ) {
433                 *erroff = p - buffer;
434                 return -9; /* open display hint */
435             }
436             node = m_alloc_clear( sizeof *node );
437             if( !head )
438                 head = node;
439             else {
440                 node->up = tail->up;
441                 tail->next = node;
442             }
443             node->type = ntLIST;
444             tail = node;
445             first = 1;
446         }
447         else if( *p == ')' ) { /* walk up */
448             if( disphint ) {
449                 *erroff = p - buffer;
450                 return -9; /* open display hint */
451             }
452             if( !head ) {
453                 *erroff = 0;
454                 return -4;   /* not a list */
455             }
456             tail = tail->up;
457             if( !tail ) {
458                 *erroff = p - buffer;
459                 return -3;
460             }
461         }
462         else if( *p == '\"' ) {
463             quoted = p;
464             quoted_esc = 0;
465         }
466         else if( *p == '#' )
467             hexfmt = p;
468         else if( *p == '|' )
469             base64 = p;
470         else if( *p == '[' ) {
471             if( disphint ) {
472                 *erroff = p - buffer;
473                 return -8; /* nested display hints */
474             }
475             disphint = p;
476         }
477         else if( *p == ']' ) {
478             if( !disphint ) {
479                 *erroff = p - buffer;
480                 return -9; /* unmatched display hint close */
481             }
482             disphint = NULL;
483         }
484         else if( isdigit(*p) ) {
485             if( *p == '0' ) { /* a length may not begin with zero */
486                 *erroff = p - buffer;
487                 return -7;
488             }
489             digptr = p;
490         }
491         else if( strchr( tokenchars, *p ) )
492             tokenp = p;
493         else if( isspace(*p) )
494             ;
495         else if( *p == '{' ) {
496             /* fixme: handle rescanning:
497              * we can do this by saving our current state
498              * and start over at p+1 -- Hmmm. At this point here
499              * we are in a well defined state, so we donĀ“ need to save
500              * it.  Great.
501              */
502             *erroff = p - buffer;
503             return -10; /* unexpected reserved punctuation */
504         }
505         else if( strchr( "&\\", *p ) ) { /*reserved punctuation*/
506             *erroff = p - buffer;
507             return -10; /* unexpected reserved punctuation */
508         }
509         else { /* bad or unavailable*/
510             *erroff = p - buffer;
511             return -5;
512         }
513
514     }
515     dump_sexp( head );
516     return 0;
517 }
518
519
520 /****************
521  * Print SEXP to buffer using the MODE.  Returns the length of the
522  * SEXP in buffer or 0 if the buffer is too short (We have at least an
523  * empty list consisting of 2 bytes).  If a buffer of NULL is provided,
524  * the required length is returned.
525  */
526 size_t
527 gcry_sexp_sprint( GCRY_SEXP sexp, int mode, char *buffer, size_t maxlength )
528 {
529     return 0;
530 }
531
532
533
534 /***********************************************************/
535
536 const char *
537 strusage( int level )
538 {
539     return default_strusage(level);
540 }
541
542 int
543 main(int argc, char **argv)
544 {
545     char buffer[5000];
546     size_t erroff;
547     int rc, n;
548     FILE *fp;
549     GCRY_SEXP s_pk, s_dsa, s_p, s_q, s_g, sexp;
550
551   #if 0
552     if( argc > 1 ) {
553         fp = fopen( argv[1], "r" );
554         if( !fp )
555             exit(1);
556         n = fread(buffer, 1, 5000, fp );
557         fprintf(stderr,"read %d bytes\n", n );
558         rc = gcry_sexp_sscan( NULL, buffer, n, &erroff );
559         fprintf(stderr, "read: rc=%d  erroff=%u\n", rc, erroff );
560     }
561   #endif
562
563     s_pk = SEXP_NEW( "public-key", 10 );
564     fputs("pk:\n",stderr);dump_sexp( s_pk );
565     s_dsa = SEXP_NEW( "dsa", 3 );
566     s_p = SEXP_CONS( SEXP_NEW( "p", 1 ), SEXP_NEW( "PPPPPP", 6 ) );
567     fputs("p:\n",stderr);dump_sexp( s_p );
568     s_q = SEXP_CONS( SEXP_NEW( "q", 1 ), SEXP_NEW( "QQQ", 3 ) );
569     s_g = SEXP_CONS( SEXP_NEW( "g", 1 ), SEXP_NEW( "GGGGGG", 6 ) );
570     sexp = SEXP_CONS( s_pk, gcry_sexp_vlist( s_dsa,
571                                              s_p,
572                                              s_q,
573                                              s_g,
574                                              NULL ));
575     fputs("all:\n",stderr);dump_sexp( sexp );
576
577     /* now find something */
578     if( argc > 1 )
579       {
580         GCRY_SEXP s1;
581
582         s1 = gcry_sexp_find_token( sexp, argv[1], strlen(argv[1]) );
583         if( !s1 )
584           {
585             fprintf(stderr, "didn't found `%s'\n", argv[1] );
586           }
587         else
588           {
589             fprintf(stderr, "found `%s':\n", argv[1] );
590             dump_sexp( s1 );
591           }
592       }
593     return 0;
594 }
595