3 * Common definitions for `runlisp'
5 * (c) 2020 Mark Wooding
8 /*----- Licensing notice --------------------------------------------------*
10 * This file is part of Runlisp, a tool for invoking Common Lisp scripts.
12 * Runlisp is free software: you can redistribute it and/or modify it
13 * under the terms of the GNU General Public License as published by the
14 * Free Software Foundation; either version 3 of the License, or (at your
15 * option) any later version.
17 * Runlisp is distributed in the hope that it will be useful, but WITHOUT
18 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
19 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
22 * You should have received a copy of the GNU General Public License
23 * along with Runlisp. If not, see <https://www.gnu.org/licenses/>.
33 /*----- Header files ------------------------------------------------------*/
40 /*----- Handy macros ------------------------------------------------------*/
42 #define N(v) (sizeof(v)/sizeof((v)[0]))
43 /* The number of elements in the array V. */
45 /* Figure out the compiler version to see whether fancy tricks will work. */
47 # define GCC_VERSION_P(maj, min) \
48 (__GNUC__ > (maj) || (__GNUC__ == (maj) && __GNUC_MINOR__ >= (min)))
50 # define GCC_VERSION_P(maj, min) 0
54 # define CLANG_VERSION_P(maj, min) \
55 (__clang_major__ > (maj) || (__clang_major__ == (maj) && \
56 __clang_minor__ >= (min)))
58 # define CLANG_VERSION_P(maj, min) 0
61 #if GCC_VERSION_P(2, 5) || CLANG_VERSION_P(3, 3)
63 # define NORETURN __attribute__((__noreturn__))
64 /* Mark a function as not returning. */
66 # define PRINTF_LIKE(fix, aix) __attribute__((__format__(printf, fix, aix)))
67 /* Mark a function as accepting a printf(3)-like format string as
68 * argument FIX, with arguments to be substituted starting at AIX.
72 #if GCC_VERSION_P(4, 0) || CLANG_VERSION_P(3, 3)
74 # define EXECL_LIKE(ntrail) __attribute__((__sentinel__(ntrail)))
75 /* Mark a function as expecting a variable number of arguments
76 * terminated by a null pointer, followed by NTRAIL further
82 /* Couldn't detect fancy compiler features. We'll have to make do
89 # define PRINTF_LIKE(fix, aix)
92 # define EXECL_LIKE(ntrail)
95 #define DISCARD(x) do if (x); while (0)
96 /* Discard the result of evaluating expression X, without upsetting
100 #define END ((const char *)0)
101 /* A null pointer to terminate the argument tail to an `EXECL_LIKE'
102 * function. (Note that `NULL' is /not/ adequate for this purpose,
103 * since it might expand simply to `0', which is an integer, not a
104 * pointer, and might well be the wrong size and/or value.)
107 /* Wrap up <ctype.h> macros with explicit conversions to `unsigned char'. */
108 #define CTYPE_HACK(func, ch) (func((unsigned char)(ch)))
109 #define ISSPACE(ch) CTYPE_HACK(isspace, ch)
110 #define ISALNUM(ch) CTYPE_HACK(isalnum, ch)
111 #define TOLOWER(ch) CTYPE_HACK(tolower, ch)
112 #define TOUPPER(ch) CTYPE_HACK(toupper, ch)
114 /* Wrap up comparison functions to take an ordering relation as part of their
115 * syntax. This makes it much harder to screw up.
117 #define MEMCMP(x, op, y, n) (memcmp((x), (y), (n)) op 0)
118 #define STRCMP(x, op, y) (strcmp((x), (y)) op 0)
119 #define STRNCMP(x, op, y, n) (strncmp((x), (y), (n)) op 0)
122 # define SIZE_MAX (-(size_t)1)
124 /* The largest value that can be stored in an object of type
125 * `size_t'. A proper <limits.h> setting would be a preprocessor-
126 * time constant, but we don't actually need that.
129 /*----- Diagnostic utilities ----------------------------------------------*/
131 extern const char *progname
;
132 /* Our program name, for use in error messages. */
134 extern void set_progname(const char */
*prog*/
);
135 /* Set `progname' from the pathname in PROG (typically from
139 extern void vmoan(const char */
*msg*/
, va_list /*ap*/);
140 /* Report an error or warning in Unix style, given a captured
144 extern PRINTF_LIKE(1, 2) void moan(const char */
*msg*/
, ...);
145 /* Issue a warning message. */
147 extern NORETURN
PRINTF_LIKE(1, 2) void lose(const char */
*msg*/
, ...);
148 /* Issue a fatal error message and exit unsuccessfully. */
150 /*----- Memory allocation -------------------------------------------------*/
152 extern void *xmalloc(size_t /*n*/);
153 /* Allocate and return a pointer to N bytes, or report a fatal error.
155 * Release the pointer using `free' as usual. If N is zero, returns
156 * null (but you are not expected to check for this).
159 extern void *xrealloc(void */
*p*/
, size_t /*n*/);
160 /* Resize the block at P (from `malloc' or `xmalloc') to be N bytes
163 * The block might (and probably will) move, so it returns the new
164 * address. If N is zero, then the block is freed (if necessary) and
165 * a null pointer returned; otherwise, if P is null then a fresh
166 * block is allocated. If allocation fails, then a fatal error is
170 extern char *xstrndup(const char */
*p*/
, size_t /*n*/);
171 /* Allocate and return a copy of the N-byte string starting at P.
173 * The new string is null-terminated, though P need not be. If
174 * allocation fails, then a fatal error is reported.
177 extern char *xstrdup(const char */
*p*/
);
178 /* Allocate and return a copy of the null-terminated string starting
181 * If allocation fails, then a fatal error is reported.
184 /*----- Dynamic strings ---------------------------------------------------*/
188 * Note that the string might not be null-terminated.
191 char *p
; /* string base address */
192 size_t len
; /* current string length */
193 size_t sz
; /* allocated size of buffer */
195 #define DSTR_INIT { 0, 0, 0 }
197 extern void dstr_init(struct dstr */
*d*/
);
198 /* Initialize the string D.
200 * Usually you'd use the static initializer `DSTR_INIT'.
203 extern void dstr_reset(struct dstr */
*d*/
);
204 /* Reset string D so it's empty again. */
206 extern void dstr_ensure(struct dstr */
*d*/
, size_t /*n*/);
207 /* Ensure that D has at least N unused bytes available. */
209 extern void dstr_release(struct dstr */
*d*/
);
210 /* Release the memory held by D.
212 * It must be reinitialized (e.g., by `dstr_init') before it can be
216 extern void dstr_putm(struct dstr */
*d*/
, const void */
*p*/
, size_t /*n*/);
217 /* Append the N-byte string at P to D.
219 * P need not be null-terminated. D will not be null-terminated
223 extern void dstr_puts(struct dstr */
*d*/
, const char */
*p*/
);
224 /* Append the null-terminated string P to D.
226 * D /is/ guaranteed to be null-terminated after this.
229 extern void dstr_putc(struct dstr */
*d*/
, int /*ch*/);
230 /* Append the single character CH to D.
232 * D will not be null-terminated afterwards.
235 extern void dstr_putcn(struct dstr */
*d*/
, int /*ch*/, size_t /*n*/);
236 /* Append N copies of the character CH to D.
238 * D will not be null-terminated afterwards.
241 extern void dstr_putz(struct dstr */
*d*/
);
242 /* Null-terminate the string D.
244 * This doesn't change the length of D. If further stuff is appended
245 * then the null terminator will be overwritten.
248 extern void dstr_vputf(struct dstr */
*d*/
,
249 const char */
*p*/
, va_list /*ap*/);
250 /* Append stuff to D, determined by printf(3) format string P and
253 * D will not be null-terminated afterwards.
256 extern PRINTF_LIKE(2, 3)
257 void dstr_putf(struct dstr */
*d*/
, const char */
*p*/
, ...);
258 /* Append stuff to D, determined by printf(3) format string P and
261 * D will not be null-terminated afterwards.
264 extern int dstr_readline(struct dstr */
*d*/
, FILE */
*fp*/
);
265 /* Append the next input line from FP to D.
267 * Return 0 on success, or -1 if reading immediately fails or
268 * encounters end-of-file (call ferror(3) to distinguish). Any
269 * trailing newline is discarded: it is not possible to determine
270 * whether the last line was ended with a newline. D is guaranteed
271 * to be null-terminated afterwards.
274 /*----- Dynamic vectors of strings ----------------------------------------*/
276 /* A dynamic vector of strings.
278 * This machinery only actually tracks character pointers. It assumes that
279 * the caller will manage the underlying storage for the strings.
281 * Note that `v' always points to the first element in the vector. The
282 * underlying storage starts `o' slots before this.
285 char **v
; /* pointer the first element */
286 size_t n
; /* length of the vector */
287 size_t o
; /* number of spare slots at start */
288 size_t sz
; /* allocated size (in slots) */
290 #define ARGV_INIT { 0, 0, 0, 0 }
292 extern void argv_init(struct argv */
*a*/v
);
293 /* Initialize the vector AV.
295 * Usually you'd use the static initializer `ARGV_INIT'.
298 extern void argv_reset(struct argv */
*av*/
);
299 /* Reset the vector AV so that it's empty again. */
301 extern void argv_ensure(struct argv */
*av*/
, size_t /*n*/);
302 /* Ensure that AV has at least N unused slots at the end. */
304 extern void argv_ensure_offset(struct argv */
*av*/
, size_t /*n*/);
305 /* Ensure that AV has at least N unused slots at the /start/. */
307 extern void argv_release(struct argv */
*av*/
);
308 /* Release the memory held by AV.
310 * It must be reinitialized (e.g., by `argv_init') before it can be
314 extern void argv_append(struct argv */
*av*/
, char */
*p*/
);
315 /* Append the pointer P to AV. */
317 extern void argv_appendz(struct argv */
*av*/
);
318 /* Append a null pointer to AV, without extending the vactor length.
320 * The null pointer will be overwritten when the next string is
324 extern void argv_appendn(struct argv */
*av*/
,
325 char *const */
*v*/
, size_t /*n*/);
326 /* Append a N-element vector V of pointers to AV. */
328 extern void argv_appendav(struct argv */
*av*/
, const struct argv */
*bv*/
);
329 /* Append the variable-length vector BV to AV. */
331 extern void argv_appendv(struct argv */
*av*/
, va_list /*ap*/);
332 /* Append the pointers from a variable-length argument list AP to AV.
334 * The list is terminated by a null pointer.
337 extern EXECL_LIKE(0) void argv_appendl(struct argv */
*av*/
, ...);
338 /* Append the argument pointers, terminated by a null pointer, to
342 extern void argv_prepend(struct argv */
*av*/
, char */
*p*/
);
343 /* Prepend the pointer P to AV. */
345 extern void argv_prependn(struct argv */
*av*/
,
346 char *const */
*v*/
, size_t /*n*/);
347 /* Prepend a N-element vector V of pointers to AV. */
349 extern void argv_prependav(struct argv */
*av*/
, const struct argv */
*bv*/
);
350 /* Prepend the variable-length vector BV to AV. */
352 extern void argv_prependv(struct argv */
*av*/
, va_list /*ap*/);
353 /* Prepend the pointers from a variable-length argument list AP to
356 * The list is terminated by a null pointer.
359 extern EXECL_LIKE(0) void argv_prependl(struct argv */
*av*/
, ...);
360 /* Prepend the argument pointers, terminated by a null pointer, to
364 /*----- Treaps ------------------------------------------------------------*/
366 /* A `treap' is a data structure for associating values with keys. This
367 * implementation assumes that keys are simply text strings.
370 struct treap_node
*root
;
372 #define TREAP_INIT { 0 }
374 /* A treap is a combination of a binary search tree and a binary heap. The
375 * nodes are ordered according to the search keys, in the usual way, so that
376 * all the keys in a node's left subtree precede that node's key, and all of
377 * the keys in its right subtree follow the node's key. The trick is that
378 * the tree must /also/ satisfy the heap condition regarding randomly
379 * assigned `weights' attached to each node: so a node's weight must not be
380 * less than their weight of either of its children.
382 * This combination uniquely determines the structure of the tree, except for
383 * nodes whose weights exactly match one (or both) of their children. (The
384 * root must be the heaviest node in the tree. The root's key splits the
385 * remaining nodes into left and right subtrees, whose structure is then
386 * uniquely determined by induction.)
388 * This is an /intrusive/ data structure. A caller is expected to include a
389 * `struct treap_node' as (probably) the initial part of a larger structure.
392 unsigned wt
; /* weight (randomly assigned) */
393 struct treap_node
*left
, *right
; /* left and right subtrees */
394 char *k
; size_t kn
; /* key pointer and length */
396 #define TREAP_NODE_KEY(n) (((const struct treap_node *)(n))->k + 0)
397 #define TREAP_NODE_KEYLEN(n) (((const struct treap_node *)(n))->kn + 0)
399 /* We can't allocate nodes ourselves, because only the caller knows how.
400 * Instead, insertion is split into two operations: `treap_probe' looks to
401 * see whether a matching node is already in the treap, and returns it if so;
402 * otherwise, it flls in this `treap_path' structure, which is passed back to
403 * `treap_insert' to help it add the fresh node into the treap. (See the
404 * commentary in `treap_probe' and `treap_insert' for the details.)
406 #define TREAP_PATHMAX 64
408 struct treap_node
**path
[TREAP_PATHMAX
];
412 /* An external iterator for a treap. (See the commentary for
413 * `treap_start_iter' and `treap_next' for the details.)
416 struct treap_node
*stack
[TREAP_PATHMAX
];
420 extern void treap_init(struct treap */
*t*/
);
421 /* Initialize the treap T.
423 * Usually you'd use the static initializer `TREAP_INIT'.
426 extern void *treap_lookup(const struct treap */
*t*/
,
427 const char */
*k*/
, size_t /*kn*/);
428 /* Look up the KN-byte key K in the treap T.
430 * Return a pointer to the matching node if one was found, or null
434 extern void *treap_probe(struct treap */
*t*/
,
435 const char */
*k*/
, size_t /*kn*/,
436 struct treap_path */
*p*/
);
437 /* Look up the KN-byte K in the treap T, recording a path in P.
439 * This is similar to `treap_lookup', in that it returns the
440 * requested node if it already exists, or null otherwise, but it
441 * also records in P information to be used by `treap_insert' to
442 * insert a new node with the given key it's not there already.
445 extern void treap_insert(struct treap */
*t*/
, const struct treap_path */
*p*/
,
446 struct treap_node */
*n*/
,
447 const char */
*k*/
, size_t /*kn*/);
448 /* Insert a new node N into T, associating it with the KN-byte key K.
450 * Use the path data P, from `treap_probe', to help with insertion.
453 extern void *treap_remove(struct treap */
*t*/
,
454 const char */
*k*/
, size_t /*kn*/);
455 /* Remove the node with the KN-byte K from T.
457 * Return the address of the node we removed, or null if it couldn't
461 extern void treap_start_iter(struct treap */
*t*/
, struct treap_iter */
*i*/
);
462 /* Initialize an iterator I over T's nodes. */
464 extern void *treap_next(struct treap_iter */
*i*/
);
465 /* Return the next node from I, in ascending order by key.
467 * If there are no more nodes, then return null.
470 extern void treap_check(struct treap */
*t*/
);
471 /* Check the treap structure rules for T. */
473 extern void treap_dump(struct treap */
*t*/
);
474 /* Dump the treap T to standard output, for debugging purposes. */
476 /*----- Configuration file parsing ----------------------------------------*/
478 /* A configuration file. */
480 struct treap sections
; /* treap of sections */
481 struct config_section
*head
, **tail
; /* section list, in creation order */
482 struct config_section
*fallback
; /* default parent section */
484 #define CONFIG_INIT { TREAP_INIT, 0, 0 }
486 /* A configuration section. */
487 struct config_section
{
488 struct treap_node _node
; /* treap intrustion */
489 struct config_section
*next
; /* next section in creation order */
490 struct config_section
**parents
; size_t nparents
; /* vector of parents */
491 struct treap vars
; /* treap of variables */
492 struct treap cache
; /* inheritance cache */
494 #define CONFIG_SECTION_NAME(sect) TREAP_NODE_KEY(sect)
495 #define CONFIG_SECTION_NAMELEN(sect) TREAP_NODE_KEYLEN(sect)
497 /* An entry in a section's inheritance cache: see `search_recursive' for
500 struct config_cache_entry
{
501 struct treap_node _node
; /* treap intrusion */
502 unsigned f
; /* flags */
503 #define CF_OPEN 1u /* traps inheritance cycles */
504 struct config_var
*var
; /* pointer to inherited variable */
507 /* A configuration variable. */
509 struct treap_node _node
; /* treap intrusion */
510 char *file
; unsigned line
; /* source location, or null/0 */
511 char *val
; size_t n
; /* value pointer and length */
512 unsigned f
; /* flags */
513 #define CF_LITERAL 1u /* value should not be expanded */
514 #define CF_EXPAND 2u /* traps expansion cycles */
515 #define CF_OVERRIDE 4u /* override settings from files */
517 #define CONFIG_VAR_NAME(var) TREAP_NODE_KEY(var)
518 #define CONFIG_VAR_NAMELEN(var) TREAP_NODE_KEYLEN(var)
520 /* A section iterator.
522 * (Sections are visited in the order in which they were created.)
524 struct config_section_iter
{
525 struct config_section
*sect
; /* next section to return */
528 /* A variable iterator.
530 * (Variables are visited in lexicographical order.)
532 struct config_var_iter
{
537 #define CF_CREAT 1u /* create section or variable */
538 #define CF_INHERIT 2u /* look up variable in parents */
540 extern void config_init(struct config */
*conf*/
);
541 /* Initialize the configuration state CONF.
543 * Usually you'd use the static initializer `CONFIG_INIT'.
546 extern struct config_section
*config_find_section(struct config */
*conf*/
,
548 const char */
*name*/
);
549 /* Find and return the section with null-terminated NAME in CONF.
551 * If no section is found, the behaviour depends on whether
552 * `CF_CREAT' is set in F: if so, an empty section is created and
553 * returned; otherwise, a null pointer is returned.
556 extern struct config_section
*config_find_section_n(struct config */
*conf*/
,
558 const char */
*name*/
,
560 /* Find and return the section with the given SZ-byte NAME in CONF.
562 * This works like `config_find_section', but with an explicit length
563 * for the NAME rather than null-termination.
566 extern void config_set_fallback(struct config */
*conf*/
,
567 struct config_section */
*sect*/
);
568 /* Set the fallback section for CONF to be SECT.
570 * That is, if a section has no explicit parents, then by default it
571 * will have a single parent which is SECT. If SECT is null then
572 * there is no fallback section, and sections which don't have
573 * explicitly specified parents have no parents at all. (This is the
574 * default situation.)
577 extern void config_set_parent(struct config_section */
*sect*/
,
578 struct config_section */
*parent*/
);
579 /* Arrange that SECT has PARENT as its single parent section.
581 * If PARENT is null, then arrange that SECT has no parents at all.
582 * In either case, any `@parents' setting will be ignored.
585 extern void config_start_section_iter(struct config */
*conf*/
,
586 struct config_section_iter */
*i*/
);
587 /* Initialize I to iterate over the sections defined in CONF. */
589 extern struct config_section
*config_next_section
590 (struct config_section_iter */
*i*/
);
591 /* Return the next section from I, in order of creation.
593 * If there are no more sections, then return null.
596 extern struct config_var
*config_find_var(struct config */
*conf*/
,
597 struct config_section */
*sect*/
,
599 const char */
*name*/
);
600 /* Find and return the variable with null-terminated NAME in SECT.
602 * If `CF_INHERIT' is set in F, then the function searches the
603 * section's parents recursively; otherwise, it only checks to see
604 * whether the variable is set directly in SECT.
606 * If no variable is found, the behaviour depends on whether
607 * `CF_CREAT' is set in F: if so, an empty variable is created and
608 * returned; otherwise, a null pointer is returned.
610 * Setting both `CF_INHERIT' and `CF_CREAT' is not useful.
613 extern struct config_var
*config_find_var_n(struct config */
*conf*/
,
614 struct config_section */
*sect*/
,
616 const char */
*name*/
,
618 /* Find and return the variable with the given SZ-byte NAME in SECT.
620 * This works like `config_find_var', but with an explicit length for
621 * the NAME rather than null-termination.
624 extern void config_set_var(struct config */
*conf*/
,
625 struct config_section */
*sect*/
, unsigned /*f*/,
626 const char */
*name*/
, const char */
*value*/
);
627 /* Set variable NAME to VALUE in SECT, with associated flags F.
629 * The names are null-terminated. The flags are variable flags: see
630 * `struct config_var' for details.
632 * If the variable is already set and has the `CF_OVERRIDE' flag,
633 * then this function does nothing unless `CF_OVERRIDE' is /also/ set
637 extern void config_set_var_n(struct config */
*conf*/
,
638 struct config_section */
*sect*/
, unsigned /*f*/,
639 const char */
*name*/
, size_t /*namelen*/,
640 const char */
*value*/
, size_t /*valuelen*/);
641 /* As `config_set_var', except that the variable NAME and VALUE have
642 * explicit lengths (NAMELEN and VALUELEN, respectively) rather than
643 * being null- terminated.
646 extern void config_start_var_iter(struct config */
*conf*/
,
647 struct config_section */
*sect*/
,
648 struct config_var_iter */
*i*/
);
649 /* Initialize I to iterate over the variables directly defined in
653 extern struct config_var
*config_next_var(struct config_var_iter */
*i*/
);
654 /* Return next variable from I, in ascending lexicographical order.
656 * If there are no more variables, then return null.
659 extern int config_read_file(struct config */
*conf*/
, const char */
*file*/
,
661 #define CF_NOENTOK 1u
662 /* Read and parse configuration FILE, applying its settings to CONF.
664 * If all goes well, the function returns 0. If the file is not
665 * found, then the behaviour depends on whether `CF_NOENTOK' is set
666 * in F: if so, then the function simply returns -1. Otherwise, a
667 * fatal error is reported. Note that this /only/ applies if the
668 * file does not exist (specifically, opening it fails with `ENOENT')
669 * -- any other problems are reported as fatal errors regardless of
673 extern void config_read_env(struct config */
*conf*/
,
674 struct config_section */
*sect*/
);
675 /* Populate SECT with environment variables.
677 * Environment variables are always set with `CF_LITERAL'.
680 extern void config_subst_string(struct config */
*config*/
,
681 struct config_section */
*home*/
,
682 const char */
*what*/
,
683 const char */
*p*/
, struct dstr */
*d*/
);
684 /* Expand substitutions in a string.
686 * Expand the null-terminated string P relative to the HOME section,
687 * using configuration CONFIG, and appending the result to dynamic
688 * string D. Blame WHAT in any error messages.
691 extern char *config_subst_string_alloc(struct config */
*config*/
,
692 struct config_section */
*home*/
,
693 const char */
*what*/
,
695 /* Expand substitutions in a string.
697 * Expand the null-terminated string P relative to the HOME section,
698 * using configuration CONFIG, returning the result as a freshly
699 * malloc(3)ed string. Blame WHAT in any error messages.
702 extern void config_subst_var(struct config */
*config*/
,
703 struct config_section */
*home*/
,
704 struct config_var */
*var*/
,
706 /* Expand substitutions in a variable.
708 * Expand the value of the variable VAR relative to the HOME section,
709 * using configuration CONFIG, appending the result to dynamic string
713 extern char *config_subst_var_alloc(struct config */
*config*/
,
714 struct config_section */
*home*/
,
715 struct config_var */
*var*/
);
716 /* Expand substitutions in a variable.
718 * Expand the value of the variable VAR relative to the HOME section,
719 * using configuration CONFIG, returning the result as a freshly
720 * malloc(3)ed string.
723 extern void config_subst_split_var(struct config */
*config*/
,
724 struct config_section */
*home*/
,
725 struct config_var */
*var*/
,
726 struct argv */
*av*/
);
727 /* Expand substitutions in a variable and split into words.
729 * Expand and word-split the value of the variable VAR relative to
730 * the HOME section, using configuration CONFIG, appending the
731 * resulting words into the vector AV.
734 /*----- That's all, folks -------------------------------------------------*/