source: trunk/libdjvu/miniexp.h @ 15

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

needed libs update

File size: 18.0 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.6 2005/10/29 16:32:21 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
122const miniexp_t miniexp_nil = (miniexp_t)(size_t)0;
123
124/* miniexp_dummy --
125   An invalid expression used to represent
126   various exceptional conditions. */
127
128const miniexp_t 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/* minilisp_print_7bits --
494   When this flag is set, all non ascii characters
495   in strings are escaped in octal. */
496
497extern MINILISPAPI int minilisp_print_7bits;
498
499/* minilisp_macrochar_parser --
500   A non zero entry in this array defines a special parsing
501   function that runs when the corresponding character is
502   encountered. */
503
504extern MINILISPAPI miniexp_t (*minilisp_macrochar_parser[128])(void);
505
506
507
508/* -------------------------------------------------- */
509/* STUFF FOR C++ ONLY                                 */
510/* -------------------------------------------------- */
511
512#ifdef __cplusplus
513# ifndef __cplusplus
514{
515# endif
516} // extern "C"
517
518typedef void minilisp_mark_t(miniexp_t *pp);
519
520/* -------- MINIVARS -------- */
521
522/* minivar_t --
523   A class for protected garbage collector variables. */
524
525MINILISPAPI
526class minivar_t
527{
528  miniexp_t data;
529  minivar_t *next;
530  minivar_t **pprev;
531public:
532  minivar_t();
533  minivar_t(miniexp_t p);
534  minivar_t(const minivar_t &v);
535  operator miniexp_t&() { return data; }
536  miniexp_t* operator&() { return &data; }
537  minivar_t& operator=(miniexp_t p) { data = p; return *this; }
538  minivar_t& operator=(const minivar_t &v) { data = v.data; return *this; }
539  ~minivar_t() { if ((*pprev = next)) next->pprev = pprev; }
540#ifdef MINIEXP_IMPLEMENTATION
541  static minivar_t *vars;
542  static void mark(minilisp_mark_t*);
543#endif
544};
545
546
547/* -------- MINIOBJ -------- */
548
549
550/* miniobj_t --
551   The base class for c++ objects
552   represented by object expressions. */
553
554MINILISPAPI
555class miniobj_t {
556 public:
557  virtual ~miniobj_t();
558
559  /* --- stuff defined by MINIOBJ_DECLARE --- */
560  /* classname: a symbol characterizing this class. */
561  static miniexp_t classname;
562  /* classof: class name symbol for this object. */
563  virtual miniexp_t classof() const = 0;
564  /* isa -- tests if this is an instance of <classname>. */
565  virtual bool isa(miniexp_t classname) const;
566 
567  /* --- optional stuff --- */
568  /* mark: iterates over miniexps contained by this object
569     for garbage collecting purposes. */
570  virtual void mark(minilisp_mark_t action);
571  /* pname: returns a printable name for this object.
572     The caller must deallocate the result with delete[]. */
573  virtual char *pname() const;
574};
575
576/* MINIOBJ_DECLARE --
577   MINIOBJ_IMPLEMENT --
578   Useful code fragments for implementing
579   the mandatory part of miniobj subclasses. */
580
581#define MINIOBJ_DECLARE(cls, supercls, name) \
582  public: static miniexp_t classname; \
583          virtual miniexp_t classof() const; \
584          virtual bool isa(miniexp_t) const;
585
586#define MINIOBJ_IMPLEMENT(cls, supercls, name)\
587  miniexp_t cls::classname = miniexp_symbol(name);\
588  miniexp_t cls::classof() const {\
589    return cls::classname; }\
590  bool cls::isa(miniexp_t n) const {\
591    return (cls::classname==n) || (supercls::isa(n)); }
592
593
594/* miniexp_to_obj --
595   Returns a pointer to the object represented by an lisp
596   expression. Returns NULL if the expression is not an
597   object expression.
598*/
599
600static inline miniobj_t *miniexp_to_obj(miniexp_t p) {
601  if (miniexp_objectp(p))
602    return ((miniobj_t**)(((size_t)p)&~((size_t)3)))[0];
603  return 0;
604}
605
606/* miniexp_object --
607   Create an object expression for a given object. */
608
609MINILISPAPI miniexp_t miniexp_object(miniobj_t *obj);
610
611
612#endif /* __cplusplus */
613
614
615
616
617
618/* -------------------------------------------------- */
619/* THE END                                            */
620/* -------------------------------------------------- */
621
622#endif /* MINIEXP_H */
Note: See TracBrowser for help on using the repository browser.