source: trunk/libdjvu/miniexp.h @ 17

Last change on this file since 17 was 17, checked in by Eugene Romanenko, 15 years ago

update makefiles, remove absolute paths, update djvulibre to version 3.5.17

File size: 19.1 KB
Line 
1/* -*- C -*-
2// -------------------------------------------------------------------
3// MiniExp - Library for handling lisp expressions
4// Copyright (c) 2005  Leon Bottou
5//
6// This software is subject to, and may be distributed under, the
7// GNU General Public License, Version 2. The license should have
8// accompanied the software or you may obtain a copy of the license
9// from the Free Software Foundation at http://www.fsf.org .
10//
11// This program 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*/
17/* $Id: miniexp.h,v 1.12 2006/02/21 19:27:41 leonb Exp $ */
18
19#ifndef MINIEXP_H
20#define MINIEXP_H
21
22#ifdef __cplusplus
23extern "C" { 
24# ifndef __cplusplus
25}
26# endif
27#endif
28
29#ifndef MINILISPAPI
30# define MINILISPAPI /**/
31#endif
32 
33
34/* -------------------------------------------------- */
35/* LISP EXPRESSIONS                                   */
36/* -------------------------------------------------- */
37
38/* miniexp_t --
39   Opaque pointer type representing a lisp expression. */
40
41typedef struct miniexp_s* miniexp_t;
42
43
44/* There are four basic types of lisp expressions,
45   numbers, symbols, pairs, and objects.
46   The latter category can represent any c++ object
47   that inherits class <miniobj_t> defined later in this file.
48   The only such objects defined in this file are strings. */
49
50
51/* -------- NUMBERS -------- */
52
53/* Minilisp numbers can represent any integer
54   in range [-2^29...2^29-1] */
55
56
57/* miniexp_numberp --
58   Tests if an expression is a number. */
59
60static inline int miniexp_numberp(miniexp_t p) {
61  return (((size_t)(p)&3)==3);
62}
63
64/* miniexp_to_int --
65   Returns the integer corresponding to a lisp expression.
66   Assume that the expression is indeed a number. */
67
68static inline int miniexp_to_int(miniexp_t p) {
69  return (((int)(size_t)(p))>>2);
70}
71
72/* miniexp_number --
73   Constructs the expression corresponding to an integer. */
74
75static inline miniexp_t miniexp_number(int x) {
76  return (miniexp_t) (size_t) ((x<<2)|3);
77}
78   
79
80
81/* -------- SYMBOLS -------- */
82
83/* The textual representation of a minilisp symbol is a
84   sequence of printable characters forming an identifier.
85   Each symbol has a unique representation and remain
86   permanently allocated. To compare two symbols,
87   simply compare the <miniexp_t> pointers. */
88
89
90/* miniexp_symbolp --
91   Tests if an expression is a symbol. */
92
93static inline int miniexp_symbolp(miniexp_t p) {
94  return ((((size_t)p)&3)==2);
95}
96
97/* miniexp_to_name --
98   Returns the symbol name as a string.
99   Returns NULL if the expression is not a symbol. */
100   
101MINILISPAPI const char* miniexp_to_name(miniexp_t p);
102
103/* miniexp_symbol --
104   Returns the unique symbol expression with the specified name. */
105
106MINILISPAPI miniexp_t miniexp_symbol(const char *name);
107
108
109
110/* -------- PAIRS -------- */
111
112/* Pairs (also named "cons") are the basic building blocks for
113   minilisp lists. Each pair contains two expression:
114   - the <car> represents the first element of a list.
115   - the <cdr> usually is a pair representing the rest of the list.
116   The empty list is represented by a null pointer. */
117
118
119/* miniexp_nil --
120   The empty list. */
121
122#define miniexp_nil ((miniexp_t)(size_t)0)
123
124/* miniexp_dummy --
125   An invalid expression used to represent
126   various exceptional conditions. */
127
128#define miniexp_dummy ((miniexp_t)(size_t)2)
129
130/* miniexp_listp --
131   Tests if an expression is either a pair or the empty list. */   
132
133static inline int miniexp_listp(miniexp_t p) {
134  return ((((size_t)p)&3)==0);
135}
136
137/* miniexp_consp --
138   Tests if an expression is a pair. */
139
140static inline int miniexp_consp(miniexp_t p) {
141  return p && miniexp_listp(p);
142}
143
144/* miniexp_length --
145   Returns the length of a list.
146   Returns 0 for non lists, -1 for circular lists. */
147
148MINILISPAPI int miniexp_length(miniexp_t p);
149
150/* miniexp_car --
151   miniexp_cdr --
152   Returns the car or cdr of a pair. */
153
154static inline miniexp_t miniexp_car(miniexp_t p) {
155  if (miniexp_consp(p))
156    return ((miniexp_t*)p)[0];
157  return miniexp_nil;
158}
159
160static inline miniexp_t miniexp_cdr(miniexp_t p) {
161  if (miniexp_consp(p))
162    return ((miniexp_t*)p)[1];
163  return miniexp_nil;
164}
165
166/* miniexp_cXXr --
167   Represent common combinations of car and cdr. */
168
169MINILISPAPI miniexp_t miniexp_caar (miniexp_t p);
170MINILISPAPI miniexp_t miniexp_cadr (miniexp_t p);
171MINILISPAPI miniexp_t miniexp_cdar (miniexp_t p);
172MINILISPAPI miniexp_t miniexp_cddr (miniexp_t p);
173MINILISPAPI miniexp_t miniexp_caddr(miniexp_t p);
174MINILISPAPI miniexp_t miniexp_cdddr(miniexp_t p);
175
176/* miniexp_nth --
177   Returns the n-th element of a list. */
178
179MINILISPAPI miniexp_t miniexp_nth(int n, miniexp_t l);
180
181/* miniexp_cons --
182   Constructs a pair. */
183
184MINILISPAPI miniexp_t miniexp_cons(miniexp_t car, miniexp_t cdr);
185
186/* miniexp_rplaca --
187   miniexp_rplacd --
188   Changes the car or the cdr of a pair. */
189
190MINILISPAPI miniexp_t miniexp_rplaca(miniexp_t pair, miniexp_t newcar);
191MINILISPAPI miniexp_t miniexp_rplacd(miniexp_t pair, miniexp_t newcdr);
192
193/* miniexp_reverse --
194   Reverses a list in place. */
195
196MINILISPAPI miniexp_t miniexp_reverse(miniexp_t p);
197
198
199/* -------- OBJECTS (GENERIC) -------- */
200
201/* Object expressions represent a c++ object
202   that inherits class <miniobj_t> defined later.
203   Each object expression has a symbolic class name
204   and a pointer to the c++ object. */
205
206/* miniexp_objectp --
207   Tests if an expression is an object. */
208
209static inline int miniexp_objectp(miniexp_t p) {
210  return ((((size_t)p)&3)==1);
211}
212
213/* miniexp_classof --
214   Returns the symbolic class of an expression.
215   Returns nil if the expression is not an object. */
216
217MINILISPAPI miniexp_t miniexp_classof(miniexp_t p);
218
219/* miniexp_isa --
220   If <p> is an instance of class named <c> or one of
221   its subclasses, returns the actual class name.
222   Otherwise returns miniexp_nil. */
223
224MINILISPAPI miniexp_t miniexp_isa(miniexp_t p, miniexp_t c);
225
226
227/* -------- OBJECTS (STRINGS) -------- */
228
229/* miniexp_stringp --
230   Tests if an expression is a string. */
231
232MINILISPAPI int miniexp_stringp(miniexp_t p);
233
234/* miniexp_to_str --
235   Returns the c string represented by the expression.
236   Returns NULL if the expression is not a string.
237   The c string remains valid as long as the
238   corresponding lisp object exists. */
239
240MINILISPAPI const char *miniexp_to_str(miniexp_t p);
241
242/* miniexp_string --
243   Constructs a string expression by copying string s. */
244
245MINILISPAPI miniexp_t miniexp_string(const char *s);
246
247/* miniexp_substring --
248   Constructs a string expression by copying
249   at most n character from string s. */
250
251MINILISPAPI miniexp_t miniexp_substring(const char *s, int n);
252
253/* miniexp_concat --
254   Concat all the string expressions in list <l>. */
255
256MINILISPAPI miniexp_t miniexp_concat(miniexp_t l);
257
258
259
260
261
262/* -------------------------------------------------- */
263/* GARBAGE COLLECTION                                 */
264/* -------------------------------------------------- */
265
266
267/* The garbage collector reclaims the memory allocated for
268   lisp expressions no longer in use.  It is automatically
269   invoked by the pair and object allocation functions when
270   the available memory runs low.  It is however possible to
271   temporarily disable it.
272
273   The trick is to determine which lisp expressions are in
274   use at a given moment. This package takes a simplistic
275   approach. All objects of type <minivar_t> are chained and
276   can reference an arbitrary lisp expression.  Garbage
277   collection preserves all lisp expressions referenced by a
278   minivar, as well as all lisp expressions that can be
279   accessed from these.
280     
281   The minivar class is designed such that C++ program can
282   directly use instances of <minivar_t> as normal
283   <miniexp_t> variables.  There is almost no overhead
284   accessing or changing the lisp expression referenced by a
285   minivar. However, the minivar chain must be updated
286   whenever the minivar object is constructed or destructed.
287   
288   Example (in C++ only):
289     miniexp_t copy_in_reverse(miniexp_t p) {
290        minivar_t l = miniexp_nil;
291        while (miniexp_consp(p)) {
292          l = miniexp_cons(miniexp_car(p), l);
293          p = miniexp_cdr(p);
294        }
295        return l;
296     }
297
298   When to use minivar_t instead of miniexp_t?
299
300   * A function that only navigates properly secured
301     s-expressions without modifying them does not need to
302     bother about minivars.
303
304   * Only the following miniexp functions can cause a
305     garbage collection: miniexp_cons(), miniexp_object(),
306     miniexp_string(), miniexp_substring(),
307     miniexp_concat(), miniexp_pprin(), miniexp_pprint(),
308     miniexp_gc(), and miniexp_release_gc_lock().  A
309     function that does not cause calls to these functions
310     does not need to bother about minivars.
311
312   * Other functions should make sure that all useful
313     s-expression are directly or indirectly secured by a
314     minivar_t object. In case of doubt, use minivars
315     everywhere.
316
317   * Function arguments should remain <miniexp_t> in order
318     to allow interoperability with the C language. As a
319     consequence, functions must often copy their arguments
320     into minivars in order to make sure they remain
321     allocated. A small performance improvement can be
322     achieved by deciding that the function should always be
323     called using properly secured arguments. This is more
324     difficult to get right.
325
326   C programs cannot use minivars as easily as C++ programs.
327   Wrappers are provided to allocate minivars and to access
328   their value. This is somehow inconvenient.  It might be
329   more practical to control the garbage collector
330   invocations with <miniexp_acquire_gc_lock()> and
331   <miniexp_release_gc_lock()>...  */
332   
333
334/* minilisp_gc --
335   Invokes the garbage collector now. */
336
337MINILISPAPI void minilisp_gc(void);
338
339/* minilisp_info --
340   Prints garbage collector statistics. */
341
342MINILISPAPI void minilisp_info(void);
343
344/* minilisp_acquire_gc_lock --
345   minilisp_release_gc_lock --
346   Temporarily disables automatic garbage collection.
347   Acquire/release pairs may be nested.
348   Both functions return their argument unmodified.
349   This is practical because <minilisp_release_gc_lock>
350   can invoke the garbage collector. Before doing
351   so it stores its argument in a minivar to
352   preserve it.
353
354   Example (in C):
355     miniexp_t copy_in_reverse(miniexp_t p) {
356        miniexp_t l = 0;
357        minilisp_acquire_gc_lock(0);
358        while (miniexp_consp(p)) {
359          l = miniexp_cons(miniexp_car(p), l);
360          p = miniexp_cdr(p);
361        }
362        return minilisp_release_gc_lock(l);
363     }
364   
365   Disabling garbage collection for a long time
366   increases the memory consumption. */
367
368MINILISPAPI miniexp_t minilisp_acquire_gc_lock(miniexp_t);
369MINILISPAPI miniexp_t minilisp_release_gc_lock(miniexp_t);
370
371/* minivar_t --
372   The minivar type. */
373#ifdef __cplusplus
374class minivar_t;
375#else
376typedef struct minivar_s minivar_t;
377#endif
378
379/* minivar_alloc --
380   minivar_free --
381   Wrappers for creating and destroying minivars in C. */
382
383MINILISPAPI minivar_t *minivar_alloc(void);
384MINILISPAPI void minivar_free(minivar_t *v);
385
386/* minivar_pointer --
387   Wrappers to access the lisp expression referenced
388   by a minivar. This function returns a pointer
389   to the actual miniexp_t variable. */
390
391MINILISPAPI miniexp_t *minivar_pointer(minivar_t *v);
392
393/* minilisp_debug --
394   Setting the debug flag runs the garbage collector
395   very often. This is extremely slow, but can be
396   useful to debug memory allocation problems. */
397
398MINILISPAPI void minilisp_debug(int debugflag);
399
400/* minilisp_finish --
401   Deallocates everything.  This is only useful when using
402   development tools designed to check for memory leaks. 
403   No miniexp function can be used after calliang this. */
404
405MINILISPAPI void minilisp_finish(void);
406
407
408/* -------------------------------------------------- */
409/* INPUT/OUTPUT                                       */
410/* -------------------------------------------------- */
411
412/* Notes about the textual represenation of miniexps.
413
414   - Special characters are:
415     * the parenthesis <(> and <)>,
416     * the double quote <">,
417     * the vertical bar <|>,
418     * any ascii character with a non zero entry
419       in array <minilisp_macrochar_parser>.
420
421   - Symbols are represented by their name.
422     Vertical bars <|> can be used to delimit names that
423     contain blanks, special characters, non printable
424     characters, non ascii characters, or
425     can be confused as a number.
426     
427   - Numbers follow the syntax specified by the C
428     function strtol() with base=0.
429
430   - Strings are delimited by double quotes.
431     All C string escapes are recognized.
432     Non printable ascii characters must be escaped.
433
434   - List are represented by an open parenthesis <(>
435     followed by the space separated list elements,
436     followed by a closing parenthesis <)>.
437     When the cdr of the last pair is non zero,
438     the closed parenthesis is preceded by
439     a space, a dot <.>, a space, and the textual
440     representation of the cdr.
441
442   - When the parser encounters an ascii character corresponding
443     to a non zero function pointer in <minilisp_macrochar_parser>,
444     the function is invoked and must return a possibly empty
445     list of miniexps to be returned by subsequent
446     invocations of the parser. */
447
448
449/* minilisp_puts/getc/ungetc --
450   All minilisp i/o is performed by invoking
451   these functions pointers. */
452
453extern MINILISPAPI int (*minilisp_puts)(const char *s);
454extern MINILISPAPI int (*minilisp_getc)(void);
455extern MINILISPAPI int (*minilisp_ungetc)(int c);
456
457/* minilisp_set_output --
458   minilisp_set_input --
459   Sets the above function to read/write from/to file f.
460   Only defined when <stdio.h> has been included. */
461
462#if defined(stdin)
463MINILISPAPI void minilisp_set_output(FILE *f);
464MINILISPAPI void minilisp_set_input(FILE *f);
465#endif
466
467/* miniexp_read --
468   Reads an expression by repeatedly
469   invoking <minilisp_getc> and <minilisp_ungetc>.
470   Returns <miniexp_dummy> when an error occurs. */
471
472MINILISPAPI miniexp_t miniexp_read(void);
473
474/* miniexp_prin --
475   miniexp_print --
476   Prints a minilisp expression by repeatedly invoking <minilisp_puts>.
477   Only <minilisp_print> outputs a final newline character.
478   These functions are safe to call anytime. */
479
480MINILISPAPI miniexp_t miniexp_prin(miniexp_t p);
481MINILISPAPI miniexp_t miniexp_print(miniexp_t p);
482
483/* miniexp_pprin --
484   miniexp_pprint --
485   Prints a minilisp expression with reasonably pretty line breaks.
486   Argument <width> is the intended number of columns.
487   Only <minilisp_pprint> outputs a final newline character.
488   These functions can cause a garbage collection to occur. */
489
490MINILISPAPI miniexp_t miniexp_pprin(miniexp_t p, int width);
491MINILISPAPI miniexp_t miniexp_pprint(miniexp_t p, int width);
492
493/* miniexp_pname --
494   Returns a string containing the textual representation
495   of a minilisp expression. Set argument <width> to zero
496   to output a single line, or to a positive value to
497   perform pretty line breaks for this intended number of columns.
498   These functions can cause a garbage collection to occur.
499   It works by temporarily redefining <minilisp_puts>. */
500
501MINILISPAPI miniexp_t miniexp_pname(miniexp_t p, int width);
502
503/* minilisp_print_7bits --
504   When this flag is set, all non ascii characters
505   in strings are escaped in octal. */
506
507extern MINILISPAPI int minilisp_print_7bits;
508
509/* minilisp_macrochar_parser --
510   A non zero entry in this array defines a special parsing
511   function that runs when the corresponding character is
512   encountered. */
513
514extern MINILISPAPI miniexp_t (*minilisp_macrochar_parser[128])(void);
515
516
517
518/* -------------------------------------------------- */
519/* STUFF FOR C++ ONLY                                 */
520/* -------------------------------------------------- */
521
522#ifdef __cplusplus
523# ifndef __cplusplus
524{
525# endif
526} // extern "C"
527
528typedef void minilisp_mark_t(miniexp_t *pp);
529
530/* -------- MINIVARS -------- */
531
532/* minivar_t --
533   A class for protected garbage collector variables. */
534
535MINILISPAPI
536class minivar_t
537{
538  miniexp_t data;
539  minivar_t *next;
540  minivar_t **pprev;
541public:
542  minivar_t();
543  minivar_t(miniexp_t p);
544  minivar_t(const minivar_t &v);
545  operator miniexp_t&() { return data; }
546  miniexp_t* operator&() { return &data; }
547  minivar_t& operator=(miniexp_t p) { data = p; return *this; }
548  minivar_t& operator=(const minivar_t &v) { data = v.data; return *this; }
549  ~minivar_t() { if ((*pprev = next)) next->pprev = pprev; }
550#ifdef MINIEXP_IMPLEMENTATION
551  static minivar_t *vars;
552  static void mark(minilisp_mark_t*);
553#endif
554};
555
556
557/* -------- MINIOBJ -------- */
558
559
560/* miniobj_t --
561   The base class for c++ objects
562   represented by object expressions. */
563
564MINILISPAPI
565class miniobj_t {
566 public:
567  virtual ~miniobj_t();
568
569  /* --- stuff defined by MINIOBJ_DECLARE --- */
570  /* classname: a symbol characterizing this class. */
571  static miniexp_t classname;
572  /* classof: class name symbol for this object. */
573  virtual miniexp_t classof() const = 0;
574  /* isa -- tests if this is an instance of <classname>. */
575  virtual bool isa(miniexp_t classname) const;
576 
577  /* --- optional stuff --- */
578  /* mark: iterates over miniexps contained by this object
579     for garbage collecting purposes. */
580  virtual void mark(minilisp_mark_t*);
581
582  /* pname: returns a printable name for this object.
583     The caller must deallocate the result with delete[]. */
584  virtual char *pname() const;
585};
586
587/* MINIOBJ_DECLARE --
588   MINIOBJ_IMPLEMENT --
589   Useful code fragments for implementing
590   the mandatory part of miniobj subclasses. */
591
592#define MINIOBJ_DECLARE(cls, supercls, name) \
593  public: static miniexp_t classname; \
594          virtual miniexp_t classof() const; \
595          virtual bool isa(miniexp_t) const;
596
597#define MINIOBJ_IMPLEMENT(cls, supercls, name)\
598  miniexp_t cls::classname = miniexp_symbol(name);\
599  miniexp_t cls::classof() const {\
600    return cls::classname; }\
601  bool cls::isa(miniexp_t n) const {\
602    return (cls::classname==n) || (supercls::isa(n)); }
603
604
605/* miniexp_to_obj --
606   Returns a pointer to the object represented by an lisp
607   expression. Returns NULL if the expression is not an
608   object expression.
609*/
610
611static inline miniobj_t *miniexp_to_obj(miniexp_t p) {
612  if (miniexp_objectp(p))
613    return ((miniobj_t**)(((size_t)p)&~((size_t)3)))[0];
614  return 0;
615}
616
617/* miniexp_object --
618   Create an object expression for a given object. */
619
620MINILISPAPI miniexp_t miniexp_object(miniobj_t *obj);
621
622
623#endif /* __cplusplus */
624
625
626
627
628
629/* -------------------------------------------------- */
630/* THE END                                            */
631/* -------------------------------------------------- */
632
633#endif /* MINIEXP_H */
Note: See TracBrowser for help on using the repository browser.