See ChangeLog: Mon Jul 26 09:34:46 CEST 1999 Werner Koch
[libgcrypt.git] / src / sexp.c
1 /* sexp.c  -  S-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( !a )
91         fputs("[no MPI]", stderr );
92     else if( gcry_mpi_print( GCRYMPI_FMT_HEX, buffer, &n, a ) )
93         fputs("[MPI too large to print]", stderr );
94     else
95         fputs( buffer, stderr );
96 }
97
98
99 static void
100 do_dump_list( NODE node, int indent )
101 {
102     for( ; node; node = node->next ) {
103         switch( node->type ) {
104           case ntLIST:
105             if( indent )
106                 putc('\n', stderr);
107             fprintf(stderr, "%*s(", indent, "");
108             do_dump_list( node->u.list, indent+1 );
109             putc(')', stderr);
110             break;
111           case ntDATA:
112             if( !node->u.data.len )
113                 fputs("EMPTY", stderr );
114             else
115                 print_string(stderr, node->u.data.d, node->u.data.len, ')');
116             putc(' ', stderr);
117             break;
118           case ntMPI:
119             dump_mpi( node->u.mpi );
120             putc(' ', stderr);
121             break;
122         }
123         if( !indent )
124             putc('\n', stderr);
125     }
126 }
127
128 static void
129 dump_sexp( NODE node )
130 {
131     do_dump_list( node, 0 );
132 }
133
134
135 /****************
136  * Create a new SEXP element (data)
137  */
138 GCRY_SEXP
139 gcry_sexp_new_data( const char *buffer, size_t length )
140 {
141     NODE list, node;
142
143     node = m_alloc_clear( sizeof *node + length );
144     node->type = ntDATA;
145     node->u.data.len = length;
146     memcpy(node->u.data.d, buffer, length );
147     list = m_alloc_clear( sizeof *list );
148     list->type = ntLIST;
149     list->u.list = node;
150     return list;
151 }
152
153 /****************
154  * Release resource of the given SEXP object.
155  */
156 void
157 gcry_sexp_release( GCRY_SEXP sexp )
158 {
159 }
160
161
162
163
164 /****************
165  * Make a pair from lists a and b, don't use a or b alter on.
166  * Special behaviour:  If one is a single element list we put the
167  * element straingt into the new pair.
168  */
169 GCRY_SEXP
170 gcry_sexp_cons( GCRY_SEXP a, GCRY_SEXP b )
171 {
172     NODE head;
173
174     if( a->type != ntLIST ) {
175         fputs("sexp_cons: arg 1 is not a list\n", stderr );
176         return NULL;
177     }
178     if( b->type != ntLIST ) {
179         fputs("sexp_cons: arg 2 is not a list\n", stderr );
180         return NULL;
181     }
182
183
184     head = m_alloc_clear( sizeof *head );
185     head->type = ntLIST;
186     if( !a->u.list->next ) { /* a has only one item */
187         NODE tmp = a;
188         a = a->u.list;
189         /* fixme: release tmp here */
190     }
191     if( !b->u.list->next ) { /* b has only one item */
192         NODE tmp = b;
193         b = b->u.list;
194         /* fixme: release tmp here */
195     }
196
197     head->u.list = a;
198     a->up = head;
199     a->next = b;
200     b->up = head;
201
202     return head;
203 }
204
205 /****************
206  * Make a list from all items, the end of list is indicated by a NULL
207  * donĀ“ use the passed lists lateron, they are void.
208  */
209 GCRY_SEXP
210 gcry_sexp_vlist( GCRY_SEXP a, ... )
211 {
212     NODE head, tail, node;
213     va_list arg_ptr ;
214
215     if( a->type != ntLIST ) {
216         fputs("sexp_vlist: arg 1 is not a list\n", stderr );
217         return NULL;
218     }
219     head = m_alloc_clear( sizeof *node );
220     head->type = ntLIST;
221     if( !a->u.list->next ) { /* a has only one item */
222         NODE tmp = a;
223         a = a->u.list;
224         /* fixme: release tmp here */
225     }
226     head->u.list = a;
227     a->up = head;
228     tail = a;
229
230     va_start( arg_ptr, a ) ;
231     while( (node = va_arg( arg_ptr, NODE )) ) {
232         if( node->type != ntLIST ) {
233             fputs("sexp_vlist: an arg is not a list\n", stderr );
234             return NULL;  /* fixme: we should release alread allocated nodes */
235         }
236         if( !node->u.list->next ) { /* node has only one item */
237             NODE tmp = node;
238             node = node->u.list;
239             /* fixme: release tmp here */
240         }
241         tail->next = node;
242         node->up = head;
243         tail = node;
244     }
245
246     va_end( arg_ptr );
247     return head;
248 }
249
250
251
252 /****************
253  * Locate data in a list. Data must be the first item in the list.
254  * Returns: The sublist with that Data (don't modify it!)
255  */
256 GCRY_SEXP
257 gcry_sexp_find_token( GCRY_SEXP list, const char *tok, size_t toklen )
258 {
259     NODE node;
260
261     if( !toklen )
262         toklen = strlen(tok);
263
264     for( node=list ; node; node = node->next )
265       {
266         switch( node->type ) {
267           case ntLIST: {
268                 NODE n = gcry_sexp_find_token( node->u.list, tok, toklen );
269                 if( n )
270                     return n;
271             }
272             break;
273           case ntDATA:
274             if( node == list
275                 && node->u.data.len == toklen
276                 && !memcmp( node->u.data.d, tok, toklen ) )
277               {
278                 return node;
279               }
280             break;
281           case ntMPI:
282             break;
283         }
284       }
285
286     return NULL;
287 }
288
289
290 /****************
291  * Enumerate all objects in the list.  Ther first time you call this, pass
292  * the address of a void pointer initialized to NULL.  Then don't touch this
293  * variable anymore but pass it verbatim to the function; you will get
294  * all lists back in turn. End of lists is indicated by a returned NIL in
295  * whic case you should not continue to use this function
296  * (it would wrap around).  If you decide to cancel the operation before
297  * the final NIL you vae to release the context by calling the function
298  * with a the context but a LIST set to NULL.
299  * Note that this function returns only lists and not single objects.
300  */
301 GCRY_SEXP
302 gcry_sexp_enum( GCRY_SEXP list, void **context, int mode )
303 {
304     NODE node;
305
306     if( mode )
307         return NULL; /* mode is reserved and must be 0 */
308     if( !list ) {
309         /* we are lucky that we can hold all information in the pointer
310          * value ;-) - so there is no need to release any memory */
311         *context = NULL;
312         return NULL;
313     }
314     if( !*context )  /* start enumeration */
315         node = list;
316     else {
317         node = *context;
318         node = node->next;
319     }
320
321     for( ; node; node = node->next ) {
322         *context = node; /* store our context */
323         if( node->type == ntLIST )
324             return node->u.list;
325         return node;
326     }
327
328     /* release resources and return nil */
329     return gcry_sexp_enum( NULL, context, mode );
330 }
331
332
333
334 /****************
335  * Get the CAR
336  */
337 GCRY_SEXP
338 gcry_sexp_car( GCRY_SEXP list )
339 {
340     return list;
341 }
342
343 /****************
344  * Get data from the car
345  */
346 const char *
347 gcry_sexp_car_data( GCRY_SEXP list, size_t *datalen )
348 {
349     if( list && list->type == ntDATA ) {
350         *datalen = list->u.data.len;
351         return list->u.data.d;
352     }
353
354     return NULL;
355 }
356
357 /****************
358  * Get the CDR
359  */
360 GCRY_SEXP
361 gcry_sexp_cdr( GCRY_SEXP list )
362 {
363     if( list && (list = list->next) )
364         return list;
365     return NULL;
366 }
367
368 /****************
369  * Get data from the cdr assuming this is a pair
370  */
371 const char *
372 gcry_sexp_cdr_data( GCRY_SEXP list, size_t *datalen )
373 {
374     if( list && (list = list->next) && list->type == ntDATA ) {
375         *datalen = list->u.data.len;
376         return list->u.data.d;
377     }
378
379     return NULL;
380 }
381
382
383 /****************
384  * cdr the mpi from the list or NULL if there is no MPI.
385  * This function tries to convert plain data to an MPI.
386  * Actually this funtion returns only the second item of the list
387  * and ignores any further arguments.
388  */
389 MPI
390 gcry_sexp_cdr_mpi( GCRY_SEXP list, int mpifmt )
391 {
392     NODE node = list;
393
394     if( !node || !(node = node->next) || node == ntLIST )
395         return NULL;
396     if( node->type == ntDATA ) {
397         MPI a;
398         size_t n = node->u.data.len;
399         if( gcry_mpi_scan( &a, mpifmt, node->u.data.d, &n ) )
400             return NULL;
401         return a;
402     }
403     else if( node->type == ntMPI )
404         return gcry_mpi_copy( node->u.mpi );
405     else
406         return NULL;
407 }
408
409
410 /****************
411  * Check wether the car is equal to data
412  */
413 #if 0 /* not tested */
414 int
415 gcry_sexp_eqp_car( GCRY_SEXP list, const char *data, size_t datalen )
416 {
417     if( list && list->type == ntDATA
418         && list->u.data.len == datalen
419         && !memcmp( list->u.data.d, list, listlen ) )
420         return 1;
421
422     return 0;
423 }
424 #endif
425
426 /****************
427  * Scan the provided buffer and return the S expression in our internal
428  * format.  Returns a newly allocated expression.  If erroff is not NULL and
429  * a parsing error has occured, the offset into buffer will be returned.
430  */
431 int
432 gcry_sexp_sscan( GCRY_SEXP *retsexp, const char *buffer,
433                                      size_t length, size_t *erroff )
434 {
435     static const char tokenchars[] = "abcdefghijklmnopqrstuvwxyz"
436                                      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
437                                      "0123456789-./_:*+=";
438     const char *p;
439     size_t n;
440     NODE head, tail, node;
441     const char *digptr=NULL;
442     const char *quoted=NULL;
443     const char *tokenp=NULL;
444     const char *hexfmt=NULL;
445     const char *base64=NULL;
446     const char *disphint=NULL;
447     int quoted_esc=0;
448     int datalen=0;
449     int first;
450
451     tail = head = NULL;
452     first = 0;
453     for(p=buffer,n=length; n; p++, n-- ) {
454         if( tokenp ) {
455             if( strchr( tokenchars, *p ) )
456                 continue;
457         }
458         if( quoted ) {
459             if( quoted_esc ) {
460                 switch( *p ) {
461                   case 'b': case 't': case 'v': case 'n': case 'f':
462                   case 'r': case '"': case '\'': case '\\':
463                     quoted_esc = 0;
464                     break;
465                   case '0': case '1': case '2': case '3': case '4':
466                   case '5': case '6': case '7':
467                     if( !(n > 2 && p[1] >= '0' && p[1] <= '7'
468                                 && p[2] >= '0' && p[2] <= '7') ) {
469                         *erroff = p - buffer;
470                         return -6;   /* invalid octal value */
471                     }
472                     p += 2; n -= 2;
473                     quoted_esc = 0;
474                     break;
475                   case 'x':
476                     if( !(n > 2 && isxdigit(p[1]) && isxdigit(p[2]) ) ) {
477                         *erroff = p - buffer;
478                         return -6;   /* invalid hex value */
479                     }
480                     p += 2; n -= 2;
481                     quoted_esc = 0;
482                     break;
483                   case '\r':  /* ignore CR[,LF] */
484                     if( n && p[1] == '\n' ) {
485                         p++; n--;
486                     }
487                     quoted_esc = 0;
488                     break;
489                   case '\n':  /* ignore LF[,CR] */
490                     if( n && p[1] == '\r' ) {
491                         p++; n--;
492                     }
493                     quoted_esc = 0;
494                     break;
495                   default:
496                     *erroff = p - buffer;
497                     return -6;   /* invalid quoted string escape */
498                 }
499             }
500             else if( *p == '\\' )
501                 quoted_esc = 1;
502             else if( *p == '\"' ) {
503                 /* fixme: add item */
504                 quoted = NULL;
505             }
506         }
507         else if( hexfmt ) {
508             if( *p == '#' )
509                hexfmt = NULL;
510         }
511         else if( base64 ) {
512             if( *p == '|' )
513                base64 = NULL;
514         }
515         else if( digptr ) {
516             if( isdigit(*p) )
517                 ;
518             else if( *p == ':' ) {
519                 if( !head ) {
520                     *erroff = 0;
521                     return -4;   /* not a list */
522                 }
523                 datalen = atoi( digptr ); /* fixme: check for overflow */
524                 digptr = NULL;
525                 if( datalen > n-1 ) {
526                     *erroff = p - buffer;
527                     return -2; /* buffer too short */
528                 }
529                 /* make a new list entry */
530                 node = m_alloc_clear( sizeof *node + datalen );
531                 if( first ) { /* stuff it into the first node */
532                     first = 0;
533                     node->up = tail;
534                     tail->u.list = node;
535                 }
536                 else {
537                     node->up = tail->up;
538                     tail->next = node;
539                 }
540                 tail = node;
541                 /* and fill in the value (we store the value in the node)*/
542                 node->type = ntDATA;
543                 node->u.data.len = datalen;
544                 memcpy(node->u.data.d, p+1, datalen );
545
546                 n -= datalen;
547                 p += datalen;
548             }
549             else if( *p == '\"' ) {
550                 digptr = NULL; /* we ignore the optional length */
551                 quoted = p;
552                 quoted_esc = 0;
553             }
554             else if( *p == '#' ) {
555                 digptr = NULL; /* we ignore the optional length */
556                 hexfmt = p;
557             }
558             else if( *p == '|' ) {
559                 digptr = NULL; /* we ignore the optional length */
560                 base64 = p;
561             }
562             else {
563                 *erroff = p - buffer;
564                 return -1;
565             }
566         }
567         else if( *p == '(' ) {
568             if( disphint ) {
569                 *erroff = p - buffer;
570                 return -9; /* open display hint */
571             }
572             node = m_alloc_clear( sizeof *node );
573             if( !head )
574                 head = node;
575             else {
576                 node->up = tail->up;
577                 tail->next = node;
578             }
579             node->type = ntLIST;
580             tail = node;
581             first = 1;
582         }
583         else if( *p == ')' ) { /* walk up */
584             if( disphint ) {
585                 *erroff = p - buffer;
586                 return -9; /* open display hint */
587             }
588             if( !head ) {
589                 *erroff = 0;
590                 return -4;   /* not a list */
591             }
592             tail = tail->up;
593             if( !tail ) {
594                 *erroff = p - buffer;
595                 return -3;
596             }
597         }
598         else if( *p == '\"' ) {
599             quoted = p;
600             quoted_esc = 0;
601         }
602         else if( *p == '#' )
603             hexfmt = p;
604         else if( *p == '|' )
605             base64 = p;
606         else if( *p == '[' ) {
607             if( disphint ) {
608                 *erroff = p - buffer;
609                 return -8; /* nested display hints */
610             }
611             disphint = p;
612         }
613         else if( *p == ']' ) {
614             if( !disphint ) {
615                 *erroff = p - buffer;
616                 return -9; /* unmatched display hint close */
617             }
618             disphint = NULL;
619         }
620         else if( isdigit(*p) ) {
621             if( *p == '0' ) { /* a length may not begin with zero */
622                 *erroff = p - buffer;
623                 return -7;
624             }
625             digptr = p;
626         }
627         else if( strchr( tokenchars, *p ) )
628             tokenp = p;
629         else if( isspace(*p) )
630             ;
631         else if( *p == '{' ) {
632             /* fixme: handle rescanning:
633              * we can do this by saving our current state
634              * and start over at p+1 -- Hmmm. At this point here
635              * we are in a well defined state, so we donĀ“ need to save
636              * it.  Great.
637              */
638             *erroff = p - buffer;
639             return -10; /* unexpected reserved punctuation */
640         }
641         else if( strchr( "&\\", *p ) ) { /*reserved punctuation*/
642             *erroff = p - buffer;
643             return -10; /* unexpected reserved punctuation */
644         }
645         else { /* bad or unavailable*/
646             *erroff = p - buffer;
647             return -5;
648         }
649
650     }
651     *retsexp = head;
652     return 0;
653 }
654
655
656 /****************
657  * Print SEXP to buffer using the MODE.  Returns the length of the
658  * SEXP in buffer or 0 if the buffer is too short (We have at least an
659  * empty list consisting of 2 bytes).  If a buffer of NULL is provided,
660  * the required length is returned.
661  */
662 size_t
663 gcry_sexp_sprint( GCRY_SEXP sexp, int mode, char *buffer, size_t maxlength )
664 {
665     return 0;
666 }
667
668
669
670 /***********************************************************/
671
672 const char *
673 strusage( int level )
674 {
675     return default_strusage(level);
676 }
677
678 int
679 main(int argc, char **argv)
680 {
681     char buffer[5000];
682     size_t erroff;
683     int rc, n;
684     FILE *fp;
685     GCRY_SEXP s_pk, s_dsa, s_p, s_q, s_g, sexp;
686
687   #if 0
688     fp = stdin;
689     n = fread(buffer, 1, 5000, fp );
690     rc = gcry_sexp_sscan( &sexp, buffer, n, &erroff );
691     if( rc ) {
692         fprintf(stderr, "parse error %d at offset %u\n", rc, erroff );
693         exit(1);
694     }
695   #else
696     s_pk = SEXP_NEW( "public-key", 10 );
697     fputs("pk:\n",stderr);dump_sexp( s_pk );
698     s_dsa = SEXP_NEW( "dsa", 3 );
699     s_p = SEXP_CONS( SEXP_NEW( "p", 1 ), SEXP_NEW( "PPPPPP", 6 ) );
700     fputs("p:\n",stderr);dump_sexp( s_p );
701     s_q = SEXP_CONS( SEXP_NEW( "q", 1 ), SEXP_NEW( "QQQ", 3 ) );
702     s_g = SEXP_CONS( SEXP_NEW( "g", 1 ), SEXP_NEW( "GGGGGG", 6 ) );
703     sexp = SEXP_CONS( s_pk, gcry_sexp_vlist( s_dsa,
704                                              s_p,
705                                              s_q,
706                                              s_g,
707                                              NULL ));
708     fputs("Here is what we have:\n",stderr);
709     dump_sexp( sexp );
710   #endif
711
712     /* now find something */
713     if( argc > 1 )
714       {
715         GCRY_SEXP s1;
716
717         s1 = gcry_sexp_find_token( sexp, argv[1], strlen(argv[1]) );
718         if( !s1 )
719           {
720             fprintf(stderr, "didn't found `%s'\n", argv[1] );
721           }
722         else
723           {
724             fprintf(stderr, "found `%s':\n", argv[1] );
725             dump_sexp( s1 );
726           }
727
728
729         if( argc > 2 ) /* get the MPI out of the list */
730         #if 1
731           {
732             GCRY_SEXP s2;
733             const char *p;
734             size_t n;
735
736             p = gcry_sexp_car_data( s1, &n );
737             if( !p ) {
738                 fputs("no CAR\n", stderr );
739                 exit(1);
740             }
741             fprintf(stderr, "CAR=`%.*s'\n", (int)n, p );
742
743             p = gcry_sexp_cdr_data( s1, &n );
744             if( !p ) {
745                 s2 = gcry_sexp_cdr( s1 );
746                 if( !s2 ) {
747                     fputs("no CDR at all\n", stderr );
748                     exit(1);
749                 }
750                 p = gcry_sexp_car_data( s2, &n );
751             }
752             if( !p ) {
753                 fputs("no CDR data\n", stderr );
754                 exit(1);
755             }
756             fprintf(stderr, "CDR=`%.*s'\n", (int)n, p );
757
758
759
760           }
761         #elif 0
762           {
763             GCRY_SEXP s2;
764             MPI a;
765
766             s2 = gcry_sexp_find_token( s1, argv[2], strlen(argv[2]) );
767             if( !s1 )
768             {
769                fprintf(stderr, "didn't found `%s'\n", argv[2] );
770                exit(1);
771             }
772
773             a = gcry_sexp_cdr_mpi( s2, GCRYMPI_FMT_USG );
774             if( a ) {
775                 fprintf(stderr, "MPI: ");
776                 dump_mpi( a );
777                 fprintf(stderr, "\n");
778             }
779             else
780                 fprintf(stderr, "cannot cdr a mpi\n" );
781           }
782          #else
783           {    /* print all MPIs */
784             void *ctx = NULL;
785             GCRY_SEXP s2;
786             MPI a;
787
788             while( (s2 = gcry_sexp_enum( s1, &ctx, 0 )) )
789               {
790                 const char *car_d;
791                 size_t car_n;
792
793                 car_d = gcry_sexp_car_data( s2, &car_n );
794                 if( car_d ) {
795                    fprintf(stderr, "CAR: %.*s=", (int)car_n, car_d );
796                    a = gcry_sexp_cdr_mpi( s2, GCRYMPI_FMT_USG );
797                    dump_mpi( a );
798                    fprintf(stderr, "\n");
799
800                 }
801                 else
802                     fprintf(stderr, "no CAR\n");
803               }
804           }
805          #endif
806       }
807     return 0;
808 }
809