1 /* Lisp format strings.
2 Copyright (C) 2001-2004, 2006-2007, 2009, 2015 Free Software
4 Written by Bruno Haible <haible@clisp.cons.org>, 2001.
6 This program 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 3 of the License, or
9 (at your option) any later version.
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.
16 You should have received a copy of the GNU General Public License
17 along with this program. If not, see <http://www.gnu.org/licenses/>. */
30 #include "xvasprintf.h"
31 #include "format-invalid.h"
35 #define _(str) gettext (str)
38 /* Assertion macros. Could be defined to empty for speed. */
39 #define ASSERT(expr) if (!(expr)) abort ();
40 #define VERIFY_LIST(list) verify_list (list)
43 /* Lisp format strings are described in the Common Lisp HyperSpec,
44 chapter 22.3 "Formatted Output". */
46 /* Data structure describing format string derived constraints for an
47 argument list. It is a recursive list structure. Structure sharing
52 FCT_REQUIRED, /* The format argument list cannot end before this argument. */
53 FCT_OPTIONAL /* The format argument list may end before this argument. */
58 FAT_OBJECT, /* Any object, type T. */
59 FAT_CHARACTER_INTEGER_NULL, /* Type (OR CHARACTER INTEGER NULL). */
60 FAT_CHARACTER_NULL, /* Type (OR CHARACTER NULL). */
61 FAT_CHARACTER, /* Type CHARACTER. */
62 FAT_INTEGER_NULL, /* Type (OR INTEGER NULL). */
63 FAT_INTEGER, /* Meant for objects of type INTEGER. */
64 FAT_REAL, /* Meant for objects of type REAL. */
65 FAT_LIST, /* Meant for proper lists. */
66 FAT_FORMATSTRING, /* Format strings. */
67 FAT_FUNCTION /* Function. */
72 unsigned int repcount; /* Number of consecutive arguments this constraint
73 applies to. Normally 1, but unconstrained
74 arguments are often repeated. */
75 enum format_cdr_type presence; /* Can the argument list end right before
77 enum format_arg_type type; /* Possible values for this argument. */
78 struct format_arg_list *list; /* For FAT_LIST: List elements. */
83 unsigned int count; /* Number of format_arg records used. */
84 unsigned int allocated;
85 struct format_arg *element; /* Argument constraints. */
86 unsigned int length; /* Number of arguments represented by this segment.
87 This is the sum of all repcounts in the segment. */
90 struct format_arg_list
92 /* The constraints for the potentially infinite argument list are assumed
93 to become ultimately periodic. (Too complicated argument lists without
95 (format t "~@{~:[-~;~S~]~}" nil t 1 t 3 nil t 4)
96 are described by a constraint that ends in a length 1 period of
97 unconstrained arguments.) Such a periodic sequence can be split into
98 an initial segment and an endlessly repeated loop segment.
99 A finite sequence is represented entirely in the initial segment; the
100 loop segment is empty. */
102 struct segment initial; /* Initial arguments segment. */
103 struct segment repeated; /* Endlessly repeated segment. */
108 unsigned int directives;
109 struct format_arg_list *list;
113 /* Parameter for a directive. */
116 PT_NIL, /* param not present */
117 PT_CHARACTER, /* character */
118 PT_INTEGER, /* integer */
119 PT_ARGCOUNT, /* number of remaining arguments */
120 PT_V /* variable taken from argument list */
125 enum param_type type;
126 int value; /* for PT_INTEGER: the value, for PT_V: the position */
130 /* Forward declaration of local functions. */
131 #define union make_union
132 static void verify_list (const struct format_arg_list *list);
133 static void free_list (struct format_arg_list *list);
134 static struct format_arg_list * copy_list (const struct format_arg_list *list);
135 static bool equal_list (const struct format_arg_list *list1,
136 const struct format_arg_list *list2);
137 static struct format_arg_list * make_intersected_list
138 (struct format_arg_list *list1,
139 struct format_arg_list *list2);
140 static struct format_arg_list * make_intersection_with_empty_list
141 (struct format_arg_list *list);
142 static struct format_arg_list * make_union_list
143 (struct format_arg_list *list1,
144 struct format_arg_list *list2);
147 /* ======================= Verify a format_arg_list ======================= */
149 /* Verify some invariants. */
151 verify_element (const struct format_arg * e)
153 ASSERT (e->repcount > 0);
154 if (e->type == FAT_LIST)
155 verify_list (e->list);
158 /* Verify some invariants. */
159 /* Memory effects: none. */
161 verify_list (const struct format_arg_list *list)
164 unsigned int total_repcount;
166 ASSERT (list->initial.count <= list->initial.allocated);
168 for (i = 0; i < list->initial.count; i++)
170 verify_element (&list->initial.element[i]);
171 total_repcount += list->initial.element[i].repcount;
173 ASSERT (total_repcount == list->initial.length);
175 ASSERT (list->repeated.count <= list->repeated.allocated);
177 for (i = 0; i < list->repeated.count; i++)
179 verify_element (&list->repeated.element[i]);
180 total_repcount += list->repeated.element[i].repcount;
182 ASSERT (total_repcount == list->repeated.length);
185 #define VERIFY_LIST(list) verify_list (list)
188 /* ======================== Free a format_arg_list ======================== */
190 /* Free the data belonging to an argument list element. */
192 free_element (struct format_arg *element)
194 if (element->type == FAT_LIST)
195 free_list (element->list);
198 /* Free an argument list. */
199 /* Memory effects: Frees list. */
201 free_list (struct format_arg_list *list)
205 for (i = 0; i < list->initial.count; i++)
206 free_element (&list->initial.element[i]);
207 if (list->initial.element != NULL)
208 free (list->initial.element);
210 for (i = 0; i < list->repeated.count; i++)
211 free_element (&list->repeated.element[i]);
212 if (list->repeated.element != NULL)
213 free (list->repeated.element);
217 /* ======================== Copy a format_arg_list ======================== */
219 /* Copy the data belonging to an argument list element. */
221 copy_element (struct format_arg *newelement,
222 const struct format_arg *oldelement)
224 newelement->repcount = oldelement->repcount;
225 newelement->presence = oldelement->presence;
226 newelement->type = oldelement->type;
227 if (oldelement->type == FAT_LIST)
228 newelement->list = copy_list (oldelement->list);
231 /* Copy an argument list. */
232 /* Memory effects: Freshly allocated result. */
233 static struct format_arg_list *
234 copy_list (const struct format_arg_list *list)
236 struct format_arg_list *newlist;
242 newlist = XMALLOC (struct format_arg_list);
244 newlist->initial.count = newlist->initial.allocated = list->initial.count;
246 if (list->initial.count == 0)
247 newlist->initial.element = NULL;
250 newlist->initial.element =
251 XNMALLOC (newlist->initial.allocated, struct format_arg);
252 for (i = 0; i < list->initial.count; i++)
254 copy_element (&newlist->initial.element[i],
255 &list->initial.element[i]);
256 length += list->initial.element[i].repcount;
259 ASSERT (length == list->initial.length);
260 newlist->initial.length = length;
262 newlist->repeated.count = newlist->repeated.allocated = list->repeated.count;
264 if (list->repeated.count == 0)
265 newlist->repeated.element = NULL;
268 newlist->repeated.element =
269 XNMALLOC (newlist->repeated.allocated, struct format_arg);
270 for (i = 0; i < list->repeated.count; i++)
272 copy_element (&newlist->repeated.element[i],
273 &list->repeated.element[i]);
274 length += list->repeated.element[i].repcount;
277 ASSERT (length == list->repeated.length);
278 newlist->repeated.length = length;
280 VERIFY_LIST (newlist);
286 /* ===================== Compare two format_arg_lists ===================== */
288 /* Tests whether two normalized argument constraints are equivalent,
289 ignoring the repcount. */
291 equal_element (const struct format_arg * e1, const struct format_arg * e2)
293 return (e1->presence == e2->presence
294 && e1->type == e2->type
295 && (e1->type == FAT_LIST ? equal_list (e1->list, e2->list) : true));
298 /* Tests whether two normalized argument list constraints are equivalent. */
299 /* Memory effects: none. */
301 equal_list (const struct format_arg_list *list1,
302 const struct format_arg_list *list2)
309 n = list1->initial.count;
310 if (n != list2->initial.count)
312 for (i = 0; i < n; i++)
314 const struct format_arg * e1 = &list1->initial.element[i];
315 const struct format_arg * e2 = &list2->initial.element[i];
317 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
321 n = list1->repeated.count;
322 if (n != list2->repeated.count)
324 for (i = 0; i < n; i++)
326 const struct format_arg * e1 = &list1->repeated.element[i];
327 const struct format_arg * e2 = &list2->repeated.element[i];
329 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
337 /* ===================== Incremental memory allocation ===================== */
339 /* Ensure list->initial.allocated >= newcount. */
341 ensure_initial_alloc (struct format_arg_list *list, unsigned int newcount)
343 if (newcount > list->initial.allocated)
345 list->initial.allocated =
346 MAX (2 * list->initial.allocated + 1, newcount);
347 list->initial.element =
348 (struct format_arg *)
349 xrealloc (list->initial.element,
350 list->initial.allocated * sizeof (struct format_arg));
354 /* Ensure list->initial.allocated > list->initial.count. */
356 grow_initial_alloc (struct format_arg_list *list)
358 if (list->initial.count >= list->initial.allocated)
360 list->initial.allocated =
361 MAX (2 * list->initial.allocated + 1, list->initial.count + 1);
362 list->initial.element =
363 (struct format_arg *)
364 xrealloc (list->initial.element,
365 list->initial.allocated * sizeof (struct format_arg));
369 /* Ensure list->repeated.allocated >= newcount. */
371 ensure_repeated_alloc (struct format_arg_list *list, unsigned int newcount)
373 if (newcount > list->repeated.allocated)
375 list->repeated.allocated =
376 MAX (2 * list->repeated.allocated + 1, newcount);
377 list->repeated.element =
378 (struct format_arg *)
379 xrealloc (list->repeated.element,
380 list->repeated.allocated * sizeof (struct format_arg));
384 /* Ensure list->repeated.allocated > list->repeated.count. */
386 grow_repeated_alloc (struct format_arg_list *list)
388 if (list->repeated.count >= list->repeated.allocated)
390 list->repeated.allocated =
391 MAX (2 * list->repeated.allocated + 1, list->repeated.count + 1);
392 list->repeated.element =
393 (struct format_arg *)
394 xrealloc (list->repeated.element,
395 list->repeated.allocated * sizeof (struct format_arg));
400 /* ====================== Normalize a format_arg_list ====================== */
402 /* Normalize an argument list constraint, assuming all sublists are already
404 /* Memory effects: Destructively modifies list. */
406 normalize_outermost_list (struct format_arg_list *list)
408 unsigned int n, i, j;
410 /* Step 1: Combine adjacent elements.
411 Copy from i to j, keeping 0 <= j <= i. */
413 n = list->initial.count;
414 for (i = j = 0; i < n; i++)
416 && equal_element (&list->initial.element[i],
417 &list->initial.element[j-1]))
419 list->initial.element[j-1].repcount +=
420 list->initial.element[i].repcount;
421 free_element (&list->initial.element[i]);
426 list->initial.element[j] = list->initial.element[i];
429 list->initial.count = j;
431 n = list->repeated.count;
432 for (i = j = 0; i < n; i++)
434 && equal_element (&list->repeated.element[i],
435 &list->repeated.element[j-1]))
437 list->repeated.element[j-1].repcount +=
438 list->repeated.element[i].repcount;
439 free_element (&list->repeated.element[i]);
444 list->repeated.element[j] = list->repeated.element[i];
447 list->repeated.count = j;
449 /* Nothing more to be done if the loop segment is empty. */
450 if (list->repeated.count > 0)
452 unsigned int m, repcount0_extra;
454 /* Step 2: Reduce the loop period. */
455 n = list->repeated.count;
458 && equal_element (&list->repeated.element[0],
459 &list->repeated.element[n-1]))
461 repcount0_extra = list->repeated.element[n-1].repcount;
464 /* Proceed as if the loop period were n, with
465 list->repeated.element[0].repcount incremented by repcount0_extra. */
466 for (m = 2; m <= n / 2; n++)
469 /* m is a divisor of n. Try to reduce the loop period to n. */
472 for (i = 0; i < n - m; i++)
473 if (!((list->repeated.element[i].repcount
474 + (i == 0 ? repcount0_extra : 0)
475 == list->repeated.element[i+m].repcount)
476 && equal_element (&list->repeated.element[i],
477 &list->repeated.element[i+m])))
484 for (i = m; i < n; i++)
485 free_element (&list->repeated.element[i]);
486 if (n < list->repeated.count)
487 list->repeated.element[m] = list->repeated.element[n];
488 list->repeated.count = list->repeated.count - n + m;
489 list->repeated.length /= n / m;
494 /* Step 3: Roll as much as possible of the initial segment's tail
496 if (list->repeated.count == 1)
498 if (list->initial.count > 0
499 && equal_element (&list->initial.element[list->initial.count-1],
500 &list->repeated.element[0]))
502 /* Roll the last element of the initial segment into the loop.
503 Its repcount is irrelevant. The second-to-last element is
504 certainly different and doesn't need to be considered. */
505 list->initial.length -=
506 list->initial.element[list->initial.count-1].repcount;
507 list->initial.count--;
512 while (list->initial.count > 0
513 && equal_element (&list->initial.element[list->initial.count-1],
514 &list->repeated.element[list->repeated.count-1]))
516 unsigned int moved_repcount =
517 MIN (list->initial.element[list->initial.count-1].repcount,
518 list->repeated.element[list->repeated.count-1].repcount);
520 /* Add the element at the start of list->repeated. */
521 if (equal_element (&list->repeated.element[0],
522 &list->repeated.element[list->repeated.count-1]))
523 list->repeated.element[0].repcount += moved_repcount;
526 unsigned int newcount = list->repeated.count + 1;
527 ensure_repeated_alloc (list, newcount);
528 for (i = newcount - 1; i > 0; i--)
529 list->repeated.element[i] = list->repeated.element[i-1];
530 list->repeated.count = newcount;
531 copy_element (&list->repeated.element[0],
532 &list->repeated.element[list->repeated.count-1]);
533 list->repeated.element[0].repcount = moved_repcount;
536 /* Remove the element from the end of list->repeated. */
537 list->repeated.element[list->repeated.count-1].repcount -=
539 if (list->repeated.element[list->repeated.count-1].repcount == 0)
541 free_element (&list->repeated.element[list->repeated.count-1]);
542 list->repeated.count--;
545 /* Remove the element from the end of list->initial. */
546 list->initial.element[list->initial.count-1].repcount -=
548 if (list->initial.element[list->initial.count-1].repcount == 0)
550 free_element (&list->initial.element[list->initial.count-1]);
551 list->initial.count--;
553 list->initial.length -= moved_repcount;
559 /* Normalize an argument list constraint. */
560 /* Memory effects: Destructively modifies list. */
562 normalize_list (struct format_arg_list *list)
568 /* First normalize all elements, recursively. */
569 n = list->initial.count;
570 for (i = 0; i < n; i++)
571 if (list->initial.element[i].type == FAT_LIST)
572 normalize_list (list->initial.element[i].list);
573 n = list->repeated.count;
574 for (i = 0; i < n; i++)
575 if (list->repeated.element[i].type == FAT_LIST)
576 normalize_list (list->repeated.element[i].list);
578 /* Then normalize the top level list. */
579 normalize_outermost_list (list);
585 /* ===================== Unconstrained and empty lists ===================== */
587 /* It's easier to allocate these on demand, than to be careful not to
588 accidentally modify statically allocated lists. */
591 /* Create an unconstrained argument list. */
592 /* Memory effects: Freshly allocated result. */
593 static struct format_arg_list *
594 make_unconstrained_list ()
596 struct format_arg_list *list;
598 list = XMALLOC (struct format_arg_list);
599 list->initial.count = 0;
600 list->initial.allocated = 0;
601 list->initial.element = NULL;
602 list->initial.length = 0;
603 list->repeated.count = 1;
604 list->repeated.allocated = 1;
605 list->repeated.element = XNMALLOC (1, struct format_arg);
606 list->repeated.element[0].repcount = 1;
607 list->repeated.element[0].presence = FCT_OPTIONAL;
608 list->repeated.element[0].type = FAT_OBJECT;
609 list->repeated.length = 1;
617 /* Create an empty argument list. */
618 /* Memory effects: Freshly allocated result. */
619 static struct format_arg_list *
622 struct format_arg_list *list;
624 list = XMALLOC (struct format_arg_list);
625 list->initial.count = 0;
626 list->initial.allocated = 0;
627 list->initial.element = NULL;
628 list->initial.length = 0;
629 list->repeated.count = 0;
630 list->repeated.allocated = 0;
631 list->repeated.element = NULL;
632 list->repeated.length = 0;
640 /* Test for an empty list. */
641 /* Memory effects: none. */
643 is_empty_list (const struct format_arg_list *list)
645 return (list->initial.count == 0 && list->repeated.count == 0);
649 /* ======================== format_arg_list surgery ======================== */
651 /* Unfold list->repeated m times, where m >= 1.
652 Assumes list->repeated.count > 0. */
653 /* Memory effects: list is destructively modified. */
655 unfold_loop (struct format_arg_list *list, unsigned int m)
657 unsigned int i, j, k;
661 unsigned int newcount = list->repeated.count * m;
662 ensure_repeated_alloc (list, newcount);
663 i = list->repeated.count;
664 for (k = 1; k < m; k++)
665 for (j = 0; j < list->repeated.count; j++, i++)
666 copy_element (&list->repeated.element[i], &list->repeated.element[j]);
667 list->repeated.count = newcount;
668 list->repeated.length = list->repeated.length * m;
672 /* Ensure list->initial.length := m, where m >= list->initial.length.
673 Assumes list->repeated.count > 0. */
674 /* Memory effects: list is destructively modified. */
676 rotate_loop (struct format_arg_list *list, unsigned int m)
678 if (m == list->initial.length)
681 if (list->repeated.count == 1)
683 /* Instead of multiple copies of list->repeated.element[0], a single
684 copy with higher repcount is appended to list->initial. */
685 unsigned int i, newcount;
687 newcount = list->initial.count + 1;
688 ensure_initial_alloc (list, newcount);
689 i = list->initial.count;
690 copy_element (&list->initial.element[i], &list->repeated.element[0]);
691 list->initial.element[i].repcount = m - list->initial.length;
692 list->initial.count = newcount;
693 list->initial.length = m;
697 unsigned int n = list->repeated.length;
699 /* Write m = list->initial.length + q * n + r with 0 <= r < n. */
700 unsigned int q = (m - list->initial.length) / n;
701 unsigned int r = (m - list->initial.length) % n;
703 /* Determine how many entries of list->repeated are needed for
709 s < list->repeated.count && t >= list->repeated.element[s].repcount;
710 t -= list->repeated.element[s].repcount, s++)
713 /* s must be < list->repeated.count, otherwise r would have been >= n. */
714 ASSERT (s < list->repeated.count);
716 /* So we need to add to list->initial:
717 q full copies of list->repeated,
718 plus the s first elements of list->repeated,
719 plus, if t > 0, a splitoff of list->repeated.element[s]. */
721 unsigned int i, j, k, newcount;
723 i = list->initial.count;
724 newcount = i + q * list->repeated.count + s + (t > 0 ? 1 : 0);
725 ensure_initial_alloc (list, newcount);
726 for (k = 0; k < q; k++)
727 for (j = 0; j < list->repeated.count; j++, i++)
728 copy_element (&list->initial.element[i],
729 &list->repeated.element[j]);
730 for (j = 0; j < s; j++, i++)
731 copy_element (&list->initial.element[i], &list->repeated.element[j]);
734 copy_element (&list->initial.element[i],
735 &list->repeated.element[j]);
736 list->initial.element[i].repcount = t;
739 ASSERT (i == newcount);
740 list->initial.count = newcount;
741 /* The new length of the initial segment is
742 = list->initial.length
743 + q * list->repeated.length
744 + list->repeated[0..s-1].repcount + t
745 = list->initial.length + q * n + r
748 list->initial.length = m;
751 /* And rotate list->repeated. */
754 unsigned int i, j, oldcount, newcount;
755 struct format_arg *newelement;
757 oldcount = list->repeated.count;
758 newcount = list->repeated.count + (t > 0 ? 1 : 0);
759 newelement = XNMALLOC (newcount, struct format_arg);
761 for (j = s; j < oldcount; j++, i++)
762 newelement[i] = list->repeated.element[j];
763 for (j = 0; j < s; j++, i++)
764 newelement[i] = list->repeated.element[j];
767 copy_element (&newelement[oldcount], &newelement[0]);
768 newelement[0].repcount -= t;
769 newelement[oldcount].repcount = t;
771 free (list->repeated.element);
772 list->repeated.element = newelement;
778 /* Ensure index n in the initial segment falls on a split between elements,
779 i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two
780 different adjacent elements. */
781 /* Memory effects: list is destructively modified. */
783 initial_splitelement (struct format_arg_list *list, unsigned int n)
787 unsigned int oldrepcount;
788 unsigned int newcount;
793 if (n > list->initial.length)
795 ASSERT (list->repeated.count > 0);
796 rotate_loop (list, n);
797 ASSERT (n <= list->initial.length);
800 /* Determine how many entries of list->initial need to be skipped. */
802 s < list->initial.count && t >= list->initial.element[s].repcount;
803 t -= list->initial.element[s].repcount, s++)
809 ASSERT (s < list->initial.count);
811 /* Split the entry into two entries. */
812 oldrepcount = list->initial.element[s].repcount;
813 newcount = list->initial.count + 1;
814 ensure_initial_alloc (list, newcount);
815 for (i = list->initial.count - 1; i > s; i--)
816 list->initial.element[i+1] = list->initial.element[i];
817 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
818 list->initial.element[s].repcount = t;
819 list->initial.element[s+1].repcount = oldrepcount - t;
820 list->initial.count = newcount;
828 /* Ensure index n in the initial segment is not shared. Return its index. */
829 /* Memory effects: list is destructively modified. */
831 initial_unshare (struct format_arg_list *list, unsigned int n)
833 /* This does the same side effects as
834 initial_splitelement (list, n);
835 initial_splitelement (list, n + 1);
842 if (n >= list->initial.length)
844 ASSERT (list->repeated.count > 0);
845 rotate_loop (list, n + 1);
846 ASSERT (n < list->initial.length);
849 /* Determine how many entries of list->initial need to be skipped. */
851 s < list->initial.count && t >= list->initial.element[s].repcount;
852 t -= list->initial.element[s].repcount, s++)
855 /* s must be < list->initial.count. */
856 ASSERT (s < list->initial.count);
858 if (list->initial.element[s].repcount > 1)
860 /* Split the entry into at most three entries: for indices < n,
861 for index n, and for indices > n. */
862 unsigned int oldrepcount = list->initial.element[s].repcount;
863 unsigned int newcount =
864 list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2);
865 ensure_initial_alloc (list, newcount);
866 if (t == 0 || t == oldrepcount - 1)
870 for (i = list->initial.count - 1; i > s; i--)
871 list->initial.element[i+1] = list->initial.element[i];
872 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
875 list->initial.element[s].repcount = 1;
876 list->initial.element[s+1].repcount = oldrepcount - 1;
880 list->initial.element[s].repcount = oldrepcount - 1;
881 list->initial.element[s+1].repcount = 1;
888 for (i = list->initial.count - 1; i > s; i--)
889 list->initial.element[i+2] = list->initial.element[i];
890 copy_element (&list->initial.element[s+2], &list->initial.element[s]);
891 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
892 list->initial.element[s].repcount = t;
893 list->initial.element[s+1].repcount = 1;
894 list->initial.element[s+2].repcount = oldrepcount - 1 - t;
896 list->initial.count = newcount;
901 /* Now the entry for index n has repcount 1. */
902 ASSERT (list->initial.element[s].repcount == 1);
910 /* Add n unconstrained elements at the front of the list. */
911 /* Memory effects: list is destructively modified. */
913 shift_list (struct format_arg_list *list, unsigned int n)
921 grow_initial_alloc (list);
922 for (i = list->initial.count; i > 0; i--)
923 list->initial.element[i] = list->initial.element[i-1];
924 list->initial.element[0].repcount = n;
925 list->initial.element[0].presence = FCT_REQUIRED;
926 list->initial.element[0].type = FAT_OBJECT;
927 list->initial.count++;
928 list->initial.length += n;
930 normalize_outermost_list (list);
937 /* ================= Intersection of two format_arg_lists ================= */
939 /* Create the intersection (i.e. combined constraints) of two argument
940 constraints. Return false if the intersection is empty, i.e. if the
941 two constraints give a contradiction. */
942 /* Memory effects: Freshly allocated element's sublist. */
944 make_intersected_element (struct format_arg *re,
945 const struct format_arg * e1,
946 const struct format_arg * e2)
948 /* Intersect the cdr types. */
949 if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED)
950 re->presence = FCT_REQUIRED;
952 re->presence = FCT_OPTIONAL;
954 /* Intersect the arg types. */
955 if (e1->type == FAT_OBJECT)
958 if (re->type == FAT_LIST)
959 re->list = copy_list (e2->list);
961 else if (e2->type == FAT_OBJECT)
964 if (re->type == FAT_LIST)
965 re->list = copy_list (e1->list);
967 else if (e1->type == FAT_LIST
968 && (e2->type == FAT_CHARACTER_INTEGER_NULL
969 || e2->type == FAT_CHARACTER_NULL
970 || e2->type == FAT_INTEGER_NULL))
973 re->list = make_intersection_with_empty_list (e1->list);
974 if (re->list == NULL)
977 else if (e2->type == FAT_LIST
978 && (e1->type == FAT_CHARACTER_INTEGER_NULL
979 || e1->type == FAT_CHARACTER_NULL
980 || e1->type == FAT_INTEGER_NULL))
983 re->list = make_intersection_with_empty_list (e2->list);
984 if (re->list == NULL)
987 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
988 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
989 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
993 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
994 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
995 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
999 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1001 re->type = e2->type;
1003 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1005 re->type = e1->type;
1007 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1009 re->type = e2->type;
1011 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1013 re->type = e1->type;
1015 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1017 re->type = e2->type;
1019 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1021 re->type = e1->type;
1023 else if (e1->type == e2->type)
1025 re->type = e1->type;
1026 if (re->type == FAT_LIST)
1028 re->list = make_intersected_list (copy_list (e1->list),
1029 copy_list (e2->list));
1030 if (re->list == NULL)
1035 /* Each of FAT_CHARACTER, FAT_INTEGER, FAT_LIST, FAT_FORMATSTRING,
1036 FAT_FUNCTION matches only itself. Contradiction. */
1042 /* Append list->repeated to list->initial, and clear list->repeated. */
1043 /* Memory effects: list is destructively modified. */
1045 append_repeated_to_initial (struct format_arg_list *list)
1047 if (list->repeated.count > 0)
1049 /* Move list->repeated over to list->initial. */
1050 unsigned int i, j, newcount;
1052 newcount = list->initial.count + list->repeated.count;
1053 ensure_initial_alloc (list, newcount);
1054 i = list->initial.count;
1055 for (j = 0; j < list->repeated.count; j++, i++)
1056 list->initial.element[i] = list->repeated.element[j];
1057 list->initial.count = newcount;
1058 list->initial.length = list->initial.length + list->repeated.length;
1059 free (list->repeated.element);
1060 list->repeated.element = NULL;
1061 list->repeated.allocated = 0;
1062 list->repeated.count = 0;
1063 list->repeated.length = 0;
1067 /* Handle a contradiction during building of a format_arg_list.
1068 The list consists only of an initial segment. The repeated segment is
1069 empty. This function searches the last FCT_OPTIONAL and cuts off the
1070 list at this point, or - if none is found - returns NULL. */
1071 /* Memory effects: list is destructively modified. If NULL is returned,
1073 static struct format_arg_list *
1074 backtrack_in_initial (struct format_arg_list *list)
1076 ASSERT (list->repeated.count == 0);
1078 while (list->initial.count > 0)
1080 unsigned int i = list->initial.count - 1;
1081 if (list->initial.element[i].presence == FCT_REQUIRED)
1083 /* Throw away this element. */
1084 list->initial.length -= list->initial.element[i].repcount;
1085 free_element (&list->initial.element[i]);
1086 list->initial.count = i;
1088 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1090 /* The list must end here. */
1091 list->initial.length--;
1092 if (list->initial.element[i].repcount > 1)
1093 list->initial.element[i].repcount--;
1096 free_element (&list->initial.element[i]);
1097 list->initial.count = i;
1108 /* Create the intersection (i.e. combined constraints) of two argument list
1109 constraints. Free both argument lists when done. Return NULL if the
1110 intersection is empty, i.e. if the two constraints give a contradiction. */
1111 /* Memory effects: list1 and list2 are freed. The result, if non-NULL, is
1112 freshly allocated. */
1113 static struct format_arg_list *
1114 make_intersected_list (struct format_arg_list *list1,
1115 struct format_arg_list *list2)
1117 struct format_arg_list *result;
1119 VERIFY_LIST (list1);
1120 VERIFY_LIST (list2);
1122 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1123 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1125 unsigned int n1 = list1->repeated.length;
1126 unsigned int n2 = list2->repeated.length;
1127 unsigned int g = gcd (n1, n2);
1128 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1129 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1131 unfold_loop (list1, m1);
1132 unfold_loop (list2, m2);
1133 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1136 if (list1->repeated.length > 0 || list2->repeated.length > 0)
1137 /* Step 2: Ensure the initial segment of the result can be computed
1138 from the initial segments of list1 and list2. If both have a
1139 repeated segment, this means to ensure
1140 list1->initial.length == list2->initial.length. */
1142 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1144 if (list1->repeated.length > 0)
1145 rotate_loop (list1, m);
1146 if (list2->repeated.length > 0)
1147 rotate_loop (list2, m);
1150 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1152 ASSERT (list1->initial.length == list2->initial.length);
1153 ASSERT (list1->repeated.length == list2->repeated.length);
1156 /* Step 3: Allocate the result. */
1157 result = XMALLOC (struct format_arg_list);
1158 result->initial.count = 0;
1159 result->initial.allocated = 0;
1160 result->initial.element = NULL;
1161 result->initial.length = 0;
1162 result->repeated.count = 0;
1163 result->repeated.allocated = 0;
1164 result->repeated.element = NULL;
1165 result->repeated.length = 0;
1167 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1169 struct format_arg *e1;
1170 struct format_arg *e2;
1174 e1 = list1->initial.element; c1 = list1->initial.count;
1175 e2 = list2->initial.element; c2 = list2->initial.count;
1176 while (c1 > 0 && c2 > 0)
1178 struct format_arg *re;
1180 /* Ensure room in result->initial. */
1181 grow_initial_alloc (result);
1182 re = &result->initial.element[result->initial.count];
1183 re->repcount = MIN (e1->repcount, e2->repcount);
1185 /* Intersect the argument types. */
1186 if (!make_intersected_element (re, e1, e2))
1188 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1189 if (re->presence == FCT_REQUIRED)
1190 /* Contradiction. Backtrack. */
1191 result = backtrack_in_initial (result);
1195 result->initial.count++;
1196 result->initial.length += re->repcount;
1198 e1->repcount -= re->repcount;
1199 if (e1->repcount == 0)
1204 e2->repcount -= re->repcount;
1205 if (e2->repcount == 0)
1212 if (list1->repeated.count == 0 && list2->repeated.count == 0)
1214 /* Intersecting two finite lists. */
1217 /* list1 longer than list2. */
1218 if (e1->presence == FCT_REQUIRED)
1219 /* Contradiction. Backtrack. */
1220 result = backtrack_in_initial (result);
1224 /* list2 longer than list1. */
1225 if (e2->presence == FCT_REQUIRED)
1226 /* Contradiction. Backtrack. */
1227 result = backtrack_in_initial (result);
1231 else if (list1->repeated.count == 0)
1233 /* Intersecting a finite and an infinite list. */
1235 if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence)
1237 /* Contradiction. Backtrack. */
1238 result = backtrack_in_initial (result);
1241 else if (list2->repeated.count == 0)
1243 /* Intersecting an infinite and a finite list. */
1245 if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence)
1247 /* Contradiction. Backtrack. */
1248 result = backtrack_in_initial (result);
1251 /* Intersecting two infinite lists. */
1252 ASSERT (c1 == 0 && c2 == 0);
1255 /* Step 5: Elementwise intersection of list1->repeated, list2->repeated. */
1257 struct format_arg *e1;
1258 struct format_arg *e2;
1262 e1 = list1->repeated.element; c1 = list1->repeated.count;
1263 e2 = list2->repeated.element; c2 = list2->repeated.count;
1264 while (c1 > 0 && c2 > 0)
1266 struct format_arg *re;
1268 /* Ensure room in result->repeated. */
1269 grow_repeated_alloc (result);
1270 re = &result->repeated.element[result->repeated.count];
1271 re->repcount = MIN (e1->repcount, e2->repcount);
1273 /* Intersect the argument types. */
1274 if (!make_intersected_element (re, e1, e2))
1276 bool re_is_required = re->presence == FCT_REQUIRED;
1278 append_repeated_to_initial (result);
1280 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1282 /* Contradiction. Backtrack. */
1283 result = backtrack_in_initial (result);
1288 result->repeated.count++;
1289 result->repeated.length += re->repcount;
1291 e1->repcount -= re->repcount;
1292 if (e1->repcount == 0)
1297 e2->repcount -= re->repcount;
1298 if (e2->repcount == 0)
1304 ASSERT (c1 == 0 && c2 == 0);
1312 /* Undo the loop unfolding and unrolling done above. */
1313 normalize_outermost_list (result);
1314 VERIFY_LIST (result);
1320 /* Create the intersection of an argument list and the empty list.
1321 Return NULL if the intersection is empty. */
1322 /* Memory effects: The result, if non-NULL, is freshly allocated. */
1323 static struct format_arg_list *
1324 make_intersection_with_empty_list (struct format_arg_list *list)
1326 #if 0 /* equivalent but slower */
1327 return make_intersected_list (copy_list (list), make_empty_list ());
1329 if (list->initial.count > 0
1330 ? list->initial.element[0].presence == FCT_REQUIRED
1331 : list->repeated.count > 0
1332 && list->repeated.element[0].presence == FCT_REQUIRED)
1335 return make_empty_list ();
1341 /* Create the intersection of two argument list constraints. NULL stands
1342 for an impossible situation, i.e. a contradiction. */
1343 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1344 if non-NULL, is freshly allocated. */
1345 static struct format_arg_list *
1346 intersection (struct format_arg_list *list1, struct format_arg_list *list2)
1351 return make_intersected_list (list1, list2);
1372 /* ===================== Union of two format_arg_lists ===================== */
1374 /* Create the union (i.e. alternative constraints) of two argument
1377 make_union_element (struct format_arg *re,
1378 const struct format_arg * e1,
1379 const struct format_arg * e2)
1381 /* Union of the cdr types. */
1382 if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED)
1383 re->presence = FCT_REQUIRED;
1384 else /* Either one of them is FCT_OPTIONAL. */
1385 re->presence = FCT_OPTIONAL;
1387 /* Union of the arg types. */
1388 if (e1->type == e2->type)
1390 re->type = e1->type;
1391 if (re->type == FAT_LIST)
1392 re->list = make_union_list (copy_list (e1->list),
1393 copy_list (e2->list));
1395 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
1396 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
1397 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
1399 re->type = e1->type;
1401 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
1402 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
1403 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1405 re->type = e2->type;
1407 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1409 re->type = e1->type;
1411 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1413 re->type = e2->type;
1415 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1417 re->type = e1->type;
1419 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1421 re->type = e2->type;
1423 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1425 re->type = e1->type;
1427 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1429 re->type = e2->type;
1431 else if (e1->type == FAT_LIST && is_empty_list (e1->list))
1433 if (e2->type == FAT_CHARACTER_INTEGER_NULL
1434 || e2->type == FAT_CHARACTER_NULL
1435 || e2->type == FAT_INTEGER_NULL)
1436 re->type = e2->type;
1437 else if (e2->type == FAT_CHARACTER)
1438 re->type = FAT_CHARACTER_NULL;
1439 else if (e2->type == FAT_INTEGER)
1440 re->type = FAT_INTEGER_NULL;
1442 re->type = FAT_OBJECT;
1444 else if (e2->type == FAT_LIST && is_empty_list (e2->list))
1446 if (e1->type == FAT_CHARACTER_INTEGER_NULL
1447 || e1->type == FAT_CHARACTER_NULL
1448 || e1->type == FAT_INTEGER_NULL)
1449 re->type = e1->type;
1450 else if (e1->type == FAT_CHARACTER)
1451 re->type = FAT_CHARACTER_NULL;
1452 else if (e1->type == FAT_INTEGER)
1453 re->type = FAT_INTEGER_NULL;
1455 re->type = FAT_OBJECT;
1457 else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL)
1458 && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL))
1460 re->type = FAT_CHARACTER_INTEGER_NULL;
1462 else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL)
1463 && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL))
1465 re->type = FAT_CHARACTER_INTEGER_NULL;
1469 /* Other union types are too hard to describe precisely. */
1470 re->type = FAT_OBJECT;
1474 /* Create the union (i.e. alternative constraints) of two argument list
1475 constraints. Free both argument lists when done. */
1476 /* Memory effects: list1 and list2 are freed. The result is freshly
1478 static struct format_arg_list *
1479 make_union_list (struct format_arg_list *list1, struct format_arg_list *list2)
1481 struct format_arg_list *result;
1483 VERIFY_LIST (list1);
1484 VERIFY_LIST (list2);
1486 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1488 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1490 unsigned int n1 = list1->repeated.length;
1491 unsigned int n2 = list2->repeated.length;
1492 unsigned int g = gcd (n1, n2);
1493 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1494 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1496 unfold_loop (list1, m1);
1497 unfold_loop (list2, m2);
1498 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1501 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1503 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1505 rotate_loop (list1, m);
1506 rotate_loop (list2, m);
1509 ASSERT (list1->initial.length == list2->initial.length);
1510 ASSERT (list1->repeated.length == list2->repeated.length);
1512 else if (list1->repeated.length > 0)
1514 /* Ensure the initial segment of the result can be computed from the
1515 initial segment of list1. */
1516 if (list2->initial.length >= list1->initial.length)
1518 rotate_loop (list1, list2->initial.length);
1519 if (list1->repeated.element[0].presence == FCT_REQUIRED)
1520 rotate_loop (list1, list1->initial.length + 1);
1523 else if (list2->repeated.length > 0)
1525 /* Ensure the initial segment of the result can be computed from the
1526 initial segment of list2. */
1527 if (list1->initial.length >= list2->initial.length)
1529 rotate_loop (list2, list1->initial.length);
1530 if (list2->repeated.element[0].presence == FCT_REQUIRED)
1531 rotate_loop (list2, list2->initial.length + 1);
1535 /* Step 3: Allocate the result. */
1536 result = XMALLOC (struct format_arg_list);
1537 result->initial.count = 0;
1538 result->initial.allocated = 0;
1539 result->initial.element = NULL;
1540 result->initial.length = 0;
1541 result->repeated.count = 0;
1542 result->repeated.allocated = 0;
1543 result->repeated.element = NULL;
1544 result->repeated.length = 0;
1546 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1548 struct format_arg *e1;
1549 struct format_arg *e2;
1553 e1 = list1->initial.element; c1 = list1->initial.count;
1554 e2 = list2->initial.element; c2 = list2->initial.count;
1555 while (c1 > 0 && c2 > 0)
1557 struct format_arg *re;
1559 /* Ensure room in result->initial. */
1560 grow_initial_alloc (result);
1561 re = &result->initial.element[result->initial.count];
1562 re->repcount = MIN (e1->repcount, e2->repcount);
1564 /* Union of the argument types. */
1565 make_union_element (re, e1, e2);
1567 result->initial.count++;
1568 result->initial.length += re->repcount;
1570 e1->repcount -= re->repcount;
1571 if (e1->repcount == 0)
1576 e2->repcount -= re->repcount;
1577 if (e2->repcount == 0)
1586 /* list2 already terminated, but still more elements in list1->initial.
1587 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1588 ASSERT (list2->repeated.count == 0);
1590 if (e1->presence == FCT_REQUIRED)
1592 struct format_arg *re;
1594 /* Ensure room in result->initial. */
1595 grow_initial_alloc (result);
1596 re = &result->initial.element[result->initial.count];
1597 copy_element (re, e1);
1598 re->presence = FCT_OPTIONAL;
1600 result->initial.count++;
1601 result->initial.length += 1;
1603 if (e1->repcount == 0)
1610 /* Ensure room in result->initial. */
1611 ensure_initial_alloc (result, result->initial.count + c1);
1614 struct format_arg *re;
1616 re = &result->initial.element[result->initial.count];
1617 copy_element (re, e1);
1618 result->initial.count++;
1619 result->initial.length += re->repcount;
1626 /* list1 already terminated, but still more elements in list2->initial.
1627 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1628 ASSERT (list1->repeated.count == 0);
1630 if (e2->presence == FCT_REQUIRED)
1632 struct format_arg *re;
1634 /* Ensure room in result->initial. */
1635 grow_initial_alloc (result);
1636 re = &result->initial.element[result->initial.count];
1637 copy_element (re, e2);
1638 re->presence = FCT_OPTIONAL;
1640 result->initial.count++;
1641 result->initial.length += 1;
1643 if (e2->repcount == 0)
1650 /* Ensure room in result->initial. */
1651 ensure_initial_alloc (result, result->initial.count + c2);
1654 struct format_arg *re;
1656 re = &result->initial.element[result->initial.count];
1657 copy_element (re, e2);
1658 result->initial.count++;
1659 result->initial.length += re->repcount;
1664 ASSERT (c1 == 0 && c2 == 0);
1667 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1668 /* Step 5: Elementwise union of list1->repeated, list2->repeated. */
1670 struct format_arg *e1;
1671 struct format_arg *e2;
1675 e1 = list1->repeated.element; c1 = list1->repeated.count;
1676 e2 = list2->repeated.element; c2 = list2->repeated.count;
1677 while (c1 > 0 && c2 > 0)
1679 struct format_arg *re;
1681 /* Ensure room in result->repeated. */
1682 grow_repeated_alloc (result);
1683 re = &result->repeated.element[result->repeated.count];
1684 re->repcount = MIN (e1->repcount, e2->repcount);
1686 /* Union of the argument types. */
1687 make_union_element (re, e1, e2);
1689 result->repeated.count++;
1690 result->repeated.length += re->repcount;
1692 e1->repcount -= re->repcount;
1693 if (e1->repcount == 0)
1698 e2->repcount -= re->repcount;
1699 if (e2->repcount == 0)
1705 ASSERT (c1 == 0 && c2 == 0);
1707 else if (list1->repeated.length > 0)
1709 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1710 initial segment. Just copy the repeated segment of list1. */
1713 result->repeated.count = list1->repeated.count;
1714 result->repeated.allocated = result->repeated.count;
1715 result->repeated.element =
1716 XNMALLOC (result->repeated.allocated, struct format_arg);
1717 for (i = 0; i < list1->repeated.count; i++)
1718 copy_element (&result->repeated.element[i],
1719 &list1->repeated.element[i]);
1720 result->repeated.length = list1->repeated.length;
1722 else if (list2->repeated.length > 0)
1724 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1725 initial segment. Just copy the repeated segment of list2. */
1728 result->repeated.count = list2->repeated.count;
1729 result->repeated.allocated = result->repeated.count;
1730 result->repeated.element =
1731 XNMALLOC (result->repeated.allocated, struct format_arg);
1732 for (i = 0; i < list2->repeated.count; i++)
1733 copy_element (&result->repeated.element[i],
1734 &list2->repeated.element[i]);
1735 result->repeated.length = list2->repeated.length;
1740 /* Undo the loop unfolding and unrolling done above. */
1741 normalize_outermost_list (result);
1742 VERIFY_LIST (result);
1747 /* Create the union of an argument list and the empty list. */
1748 /* Memory effects: list is freed. The result is freshly allocated. */
1749 static struct format_arg_list *
1750 make_union_with_empty_list (struct format_arg_list *list)
1752 #if 0 /* equivalent but slower */
1753 return make_union_list (list, make_empty_list ());
1757 if (list->initial.count > 0
1758 ? list->initial.element[0].presence == FCT_REQUIRED
1759 : list->repeated.count > 0
1760 && list->repeated.element[0].presence == FCT_REQUIRED)
1762 initial_splitelement (list, 1);
1763 ASSERT (list->initial.count > 0);
1764 ASSERT (list->initial.element[0].repcount == 1);
1765 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1766 list->initial.element[0].presence = FCT_OPTIONAL;
1768 /* We might need to merge list->initial.element[0] and
1769 list->initial.element[1]. */
1770 normalize_outermost_list (list);
1780 /* Create the union of two argument list constraints. NULL stands for an
1781 impossible situation, i.e. a contradiction. */
1782 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1783 if non-NULL, is freshly allocated. */
1784 static struct format_arg_list *
1785 union (struct format_arg_list *list1, struct format_arg_list *list2)
1790 return make_union_list (list1, list2);
1804 /* =========== Adding specific constraints to a format_arg_list =========== */
1807 /* Test whether arguments 0..n are required arguments in a list. */
1809 is_required (const struct format_arg_list *list, unsigned int n)
1814 /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */
1817 /* Walk the list->initial segment. */
1819 s < list->initial.count && t >= list->initial.element[s].repcount;
1820 t -= list->initial.element[s].repcount, s++)
1821 if (list->initial.element[s].presence != FCT_REQUIRED)
1827 if (s < list->initial.count)
1829 if (list->initial.element[s].presence != FCT_REQUIRED)
1835 /* Walk the list->repeated segment. */
1836 if (list->repeated.count == 0)
1840 s < list->repeated.count && t >= list->repeated.element[s].repcount;
1841 t -= list->repeated.element[s].repcount, s++)
1842 if (list->repeated.element[s].presence != FCT_REQUIRED)
1848 if (s < list->repeated.count)
1850 if (list->repeated.element[s].presence != FCT_REQUIRED)
1856 /* The list->repeated segment consists only of FCT_REQUIRED. So,
1857 regardless how many more passes through list->repeated would be
1858 needed until t becomes 0, the result is true. */
1863 /* Add a constraint to an argument list, namely that the arguments 0...n are
1864 present. NULL stands for an impossible situation, i.e. a contradiction. */
1865 /* Memory effects: list is freed. The result is freshly allocated. */
1866 static struct format_arg_list *
1867 add_required_constraint (struct format_arg_list *list, unsigned int n)
1869 unsigned int i, rest;
1876 if (list->repeated.count == 0 && list->initial.length <= n)
1878 /* list is already constrained to have at most length n.
1884 initial_splitelement (list, n + 1);
1886 for (i = 0, rest = n + 1; rest > 0; )
1888 list->initial.element[i].presence = FCT_REQUIRED;
1889 rest -= list->initial.element[i].repcount;
1899 /* Add a constraint to an argument list, namely that the argument n is
1900 never present. NULL stands for an impossible situation, i.e. a
1902 /* Memory effects: list is freed. The result is freshly allocated. */
1903 static struct format_arg_list *
1904 add_end_constraint (struct format_arg_list *list, unsigned int n)
1907 enum format_cdr_type n_presence;
1914 if (list->repeated.count == 0 && list->initial.length <= n)
1915 /* list is already constrained to have at most length n. */
1918 s = initial_splitelement (list, n);
1920 (s < list->initial.count
1921 ? /* n < list->initial.length */ list->initial.element[s].presence
1922 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1924 for (i = s; i < list->initial.count; i++)
1926 list->initial.length -= list->initial.element[i].repcount;
1927 free_element (&list->initial.element[i]);
1929 list->initial.count = s;
1931 for (i = 0; i < list->repeated.count; i++)
1932 free_element (&list->repeated.element[i]);
1933 if (list->repeated.element != NULL)
1934 free (list->repeated.element);
1935 list->repeated.element = NULL;
1936 list->repeated.allocated = 0;
1937 list->repeated.count = 0;
1938 list->repeated.length = 0;
1940 if (n_presence == FCT_REQUIRED)
1941 return backtrack_in_initial (list);
1947 /* Add a constraint to an argument list, namely that the argument n is
1948 of a given type. NULL stands for an impossible situation, i.e. a
1949 contradiction. Assumes a preceding add_required_constraint (list, n). */
1950 /* Memory effects: list is freed. The result is freshly allocated. */
1951 static struct format_arg_list *
1952 add_type_constraint (struct format_arg_list *list, unsigned int n,
1953 enum format_arg_type type)
1956 struct format_arg newconstraint;
1957 struct format_arg tmpelement;
1962 /* Through the previous add_required_constraint, we can assume
1963 list->initial.length >= n+1. */
1965 s = initial_unshare (list, n);
1967 newconstraint.presence = FCT_OPTIONAL;
1968 newconstraint.type = type;
1969 if (!make_intersected_element (&tmpelement,
1970 &list->initial.element[s], &newconstraint))
1971 return add_end_constraint (list, n);
1972 free_element (&list->initial.element[s]);
1973 list->initial.element[s].type = tmpelement.type;
1974 list->initial.element[s].list = tmpelement.list;
1982 /* Add a constraint to an argument list, namely that the argument n is
1983 of a given list type. NULL stands for an impossible situation, i.e. a
1984 contradiction. Assumes a preceding add_required_constraint (list, n). */
1985 /* Memory effects: list is freed. The result is freshly allocated. */
1986 static struct format_arg_list *
1987 add_listtype_constraint (struct format_arg_list *list, unsigned int n,
1988 enum format_arg_type type,
1989 struct format_arg_list *sublist)
1992 struct format_arg newconstraint;
1993 struct format_arg tmpelement;
1998 /* Through the previous add_required_constraint, we can assume
1999 list->initial.length >= n+1. */
2001 s = initial_unshare (list, n);
2003 newconstraint.presence = FCT_OPTIONAL;
2004 newconstraint.type = type;
2005 newconstraint.list = sublist;
2006 if (!make_intersected_element (&tmpelement,
2007 &list->initial.element[s], &newconstraint))
2008 return add_end_constraint (list, n);
2009 free_element (&list->initial.element[s]);
2010 list->initial.element[s].type = tmpelement.type;
2011 list->initial.element[s].list = tmpelement.list;
2019 /* ============= Subroutines used by the format string parser ============= */
2022 add_req_type_constraint (struct format_arg_list **listp,
2023 unsigned int position, enum format_arg_type type)
2025 *listp = add_required_constraint (*listp, position);
2026 *listp = add_type_constraint (*listp, position, type);
2031 add_req_listtype_constraint (struct format_arg_list **listp,
2032 unsigned int position, enum format_arg_type type,
2033 struct format_arg_list *sublist)
2035 *listp = add_required_constraint (*listp, position);
2036 *listp = add_listtype_constraint (*listp, position, type, sublist);
2040 /* Create an endless repeated list whose elements are lists constrained
2042 /* Memory effects: sublist is freed. The result is freshly allocated. */
2043 static struct format_arg_list *
2044 make_repeated_list_of_lists (struct format_arg_list *sublist)
2046 if (sublist == NULL)
2047 /* The list cannot have a single element. */
2048 return make_empty_list ();
2051 struct format_arg_list *listlist;
2053 listlist = XMALLOC (struct format_arg_list);
2055 listlist->initial.count = 0;
2056 listlist->initial.allocated = 0;
2057 listlist->initial.element = NULL;
2058 listlist->initial.length = 0;
2059 listlist->repeated.count = 1;
2060 listlist->repeated.allocated = 1;
2061 listlist->repeated.element = XNMALLOC (1, struct format_arg);
2062 listlist->repeated.element[0].repcount = 1;
2063 listlist->repeated.element[0].presence = FCT_OPTIONAL;
2064 listlist->repeated.element[0].type = FAT_LIST;
2065 listlist->repeated.element[0].list = sublist;
2066 listlist->repeated.length = 1;
2068 VERIFY_LIST (listlist);
2075 /* Create an endless repeated list which represents the union of a finite
2076 number of copies of L, each time shifted by period:
2080 L and (*^period L) and (*^{2 period} L)
2081 L and (*^period L) and (*^{2 period} L) and (*^{3 period} L)
2084 /* Memory effects: sublist is freed. The result is freshly allocated. */
2085 static struct format_arg_list *
2086 make_repeated_list (struct format_arg_list *sublist, unsigned int period)
2089 struct segment *srcseg;
2090 struct format_arg_list *list;
2091 unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount;
2094 VERIFY_LIST (sublist);
2096 ASSERT (period > 0);
2098 if (sublist->repeated.count == 0)
2100 /* L is a finite list. */
2102 if (sublist->initial.length < period)
2103 /* L and (*^period L) is a contradition, so we need to consider
2104 only 1 and 0 iterations. */
2105 return make_union_with_empty_list (sublist);
2107 srcseg = &sublist->initial;
2112 /* L is an infinite list. */
2113 /* p := lcm (period, period of L) */
2114 unsigned int Lp = sublist->repeated.length;
2115 unsigned int m = period / gcd (period, Lp); /* = lcm(period,Lp) / Lp */
2117 unfold_loop (sublist, m);
2120 /* Concatenate the initial and the repeated segments into a single
2122 tmp.count = sublist->initial.count + sublist->repeated.count;
2123 tmp.allocated = tmp.count;
2124 tmp.element = XNMALLOC (tmp.allocated, struct format_arg);
2125 for (i = 0; i < sublist->initial.count; i++)
2126 tmp.element[i] = sublist->initial.element[i];
2127 for (j = 0; j < sublist->repeated.count; i++, j++)
2128 tmp.element[i] = sublist->initial.element[j];
2129 tmp.length = sublist->initial.length + sublist->repeated.length;
2136 /* Example: n = 7, p = 2
2137 Let L = (A B C D E F G).
2140 L & L<<p = A B C&A D&B E&C F&D G&E
2141 L & L<<p & L<<2p = A B C&A D&B E&C&A F&D&B G&E&C
2142 ... = A B C&A D&B E&C&A F&D&B G&E&C&A
2144 Thus the result has an initial segment of length n - p and a period
2145 of p, and can be computed by floor(n/p) intersection operations.
2146 Or by a single incremental intersection operation, going from left
2149 list = XMALLOC (struct format_arg_list);
2150 list->initial.count = 0;
2151 list->initial.allocated = 0;
2152 list->initial.element = NULL;
2153 list->initial.length = 0;
2154 list->repeated.count = 0;
2155 list->repeated.allocated = 0;
2156 list->repeated.element = NULL;
2157 list->repeated.length = 0;
2160 for (i = 0; i < p; i++)
2161 list->initial.element[i] = srcseg->element[i];
2162 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2163 for (i = p, j = 0; i < n; i++, j++)
2164 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2169 i = 0, ti = 0, si = 0;
2172 unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
2174 /* Ensure room in list->initial. */
2175 grow_initial_alloc (list);
2176 copy_element (&list->initial.element[list->initial.count],
2177 &srcseg->element[si]);
2178 list->initial.element[list->initial.count].repcount = k;
2179 list->initial.count++;
2180 list->initial.length += k;
2184 if (ti == srcseg->element[si].repcount)
2191 ASSERT (list->initial.count > 0);
2192 if (list->initial.element[0].presence == FCT_REQUIRED)
2194 initial_splitelement (list, 1);
2195 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2196 ASSERT (list->initial.element[0].repcount == 1);
2197 list->initial.element[0].presence = FCT_OPTIONAL;
2200 j = 0, tj = 0, sj = 0;
2204 MIN (srcseg->element[si].repcount - ti,
2205 list->initial.element[sj].repcount - tj);
2207 /* Ensure room in list->initial. */
2208 grow_initial_alloc (list);
2209 if (!make_intersected_element (&list->initial.element[list->initial.count],
2210 &srcseg->element[si],
2211 &list->initial.element[sj]))
2213 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2215 /* Contradiction. Backtrack. */
2216 list = backtrack_in_initial (list);
2217 ASSERT (list != NULL); /* at least the empty list is valid */
2222 /* The list ends here. */
2227 list->initial.element[list->initial.count].repcount = k;
2228 list->initial.count++;
2229 list->initial.length += k;
2233 if (ti == srcseg->element[si].repcount)
2241 if (tj == list->initial.element[sj].repcount)
2248 ASSERT (list->initial.length == n);
2250 /* Add optional exit points at 0, period, 2*period etc.
2251 FIXME: Not sure this is correct in all cases. */
2252 for (i = 0; i < list->initial.length; i += period)
2254 si = initial_unshare (list, i);
2255 list->initial.element[si].presence = FCT_OPTIONAL;
2260 /* Now split off the repeated part. */
2261 splitindex = initial_splitelement (list, n - p);
2262 newcount = list->initial.count - splitindex;
2263 if (newcount > list->repeated.allocated)
2265 list->repeated.allocated = newcount;
2266 list->repeated.element = XNMALLOC (newcount, struct format_arg);
2268 for (i = splitindex, j = 0; i < n; i++, j++)
2269 list->repeated.element[j] = list->initial.element[i];
2270 list->repeated.count = newcount;
2271 list->repeated.length = p;
2272 list->initial.count = splitindex;
2273 list->initial.length = n - p;
2282 /* ================= Handling of format string directives ================= */
2284 /* Possible signatures of format directives. */
2285 static const enum format_arg_type I [1] = { FAT_INTEGER_NULL };
2286 static const enum format_arg_type II [2] = {
2287 FAT_INTEGER_NULL, FAT_INTEGER_NULL
2289 static const enum format_arg_type ICCI [4] = {
2290 FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL
2292 static const enum format_arg_type IIIC [4] = {
2293 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2295 static const enum format_arg_type IICCI [5] = {
2296 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL,
2299 static const enum format_arg_type IIICC [5] = {
2300 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL,
2303 static const enum format_arg_type IIIICCC [7] = {
2304 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL,
2305 FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL
2307 static const enum format_arg_type THREE [3] = {
2308 FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL,
2309 FAT_CHARACTER_INTEGER_NULL
2313 /* Check the parameters. For V params, add the constraint to the argument
2314 list. Return false and fill in *invalid_reason if the format string is
2317 check_params (struct format_arg_list **listp,
2318 unsigned int paramcount, struct param *params,
2319 unsigned int t_count, const enum format_arg_type *t_types,
2320 unsigned int directives, char **invalid_reason)
2322 unsigned int orig_paramcount = paramcount;
2323 unsigned int orig_t_count = t_count;
2325 for (; paramcount > 0 && t_count > 0;
2326 params++, paramcount--, t_types++, t_count--)
2330 case FAT_CHARACTER_INTEGER_NULL:
2332 case FAT_CHARACTER_NULL:
2333 switch (params->type)
2335 case PT_NIL: case PT_CHARACTER: case PT_V:
2337 case PT_INTEGER: case PT_ARGCOUNT:
2338 /* wrong param type */
2340 xasprintf (_("In the directive number %u, parameter %u is of type '%s' but a parameter of type '%s' is expected."), directives, orig_paramcount - paramcount + 1, "integer", "character");
2344 case FAT_INTEGER_NULL:
2345 switch (params->type)
2347 case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V:
2350 /* wrong param type */
2352 xasprintf (_("In the directive number %u, parameter %u is of type '%s' but a parameter of type '%s' is expected."), directives, orig_paramcount - paramcount + 1, "character", "integer");
2359 if (params->type == PT_V)
2361 int position = params->value;
2363 add_req_type_constraint (listp, position, *t_types);
2367 for (; paramcount > 0; params++, paramcount--)
2368 switch (params->type)
2372 case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT:
2373 /* too many params for directive */
2375 xasprintf (ngettext ("In the directive number %u, too many parameters are given; expected at most %u parameter.",
2376 "In the directive number %u, too many parameters are given; expected at most %u parameters.",
2378 directives, orig_t_count);
2381 /* Force argument to be NIL. */
2383 int position = params->value;
2386 struct format_arg_list *empty_list = make_empty_list ();
2387 add_req_listtype_constraint (listp, position,
2388 FAT_LIST, empty_list);
2389 free_list (empty_list);
2399 /* Handle the parameters, without a priori type information.
2400 For V params, add the constraint to the argument list.
2401 Return false and fill in *invalid_reason if the format string is
2404 nocheck_params (struct format_arg_list **listp,
2405 unsigned int paramcount, struct param *params,
2406 unsigned int directives, char **invalid_reason)
2409 (void) invalid_reason;
2411 for (; paramcount > 0; params++, paramcount--)
2412 if (params->type == PT_V)
2414 int position = params->value;
2415 add_req_type_constraint (listp, position, FAT_CHARACTER_INTEGER_NULL);
2422 /* ======================= The format string parser ======================= */
2424 /* Parse a piece of format string, until the matching terminating format
2425 directive is encountered.
2426 format is the remainder of the format string.
2427 position is the position in this argument list, if known, or -1 if unknown.
2428 list represents the argument list constraints at the current parse point.
2429 NULL stands for a contradiction.
2430 escape represents the union of the argument list constraints at all the
2431 currently pending FORMAT-UP-AND-OUT points. NULL stands for a contradiction
2433 All four are updated upon valid return.
2434 *separatorp is set to true if the parse terminated due to a ~; separator,
2435 more precisely to 2 if with colon, or to 1 if without colon.
2436 spec is the global struct spec.
2437 terminator is the directive that terminates this parse.
2438 separator specifies if ~; separators are allowed.
2439 fdi is an array to be filled with format directive indicators, or NULL.
2440 If the format string is invalid, false is returned and *invalid_reason is
2441 set to an error message explaining why. */
2443 parse_upto (const char **formatp,
2444 int *positionp, struct format_arg_list **listp,
2445 struct format_arg_list **escapep, int *separatorp,
2446 struct spec *spec, char terminator, bool separator,
2447 char *fdi, char **invalid_reason)
2449 const char *format = *formatp;
2450 const char *const format_start = format;
2451 int position = *positionp;
2452 struct format_arg_list *list = *listp;
2453 struct format_arg_list *escape = *escapep;
2455 for (; *format != '\0'; )
2456 if (*format++ == '~')
2458 bool colon_p = false;
2459 bool atsign_p = false;
2460 unsigned int paramcount = 0;
2461 struct param *params = NULL;
2463 FDI_SET (format - 1, FMTDIR_START);
2465 /* Count number of directives. */
2468 /* Parse parameters. */
2471 enum param_type type = PT_NIL;
2474 if (c_isdigit (*format))
2479 value = 10 * value + (*format - '0');
2482 while (c_isdigit (*format));
2484 else if (*format == '+' || *format == '-')
2486 bool negative = (*format == '-');
2489 if (!c_isdigit (*format))
2491 if (*format == '\0')
2493 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2494 FDI_SET (format - 1, FMTDIR_ERROR);
2499 xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]);
2500 FDI_SET (format, FMTDIR_ERROR);
2506 value = 10 * value + (*format - '0');
2509 while (c_isdigit (*format));
2513 else if (*format == '\'')
2515 type = PT_CHARACTER;
2517 if (*format == '\0')
2519 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2520 FDI_SET (format - 1, FMTDIR_ERROR);
2525 else if (*format == 'V' || *format == 'v')
2530 /* Consumes an argument. */
2534 else if (*format == '#')
2542 xrealloc (params, (paramcount + 1) * sizeof (struct param));
2543 params[paramcount].type = type;
2544 params[paramcount].value = value;
2553 /* Parse modifiers. */
2561 else if (*format == '@')
2570 /* Parse directive. */
2573 case 'A': case 'a': /* 22.3.4.1 FORMAT-ASCII */
2574 case 'S': case 's': /* 22.3.4.2 FORMAT-S-EXPRESSION */
2575 if (!check_params (&list, paramcount, params, 4, IIIC,
2576 spec->directives, invalid_reason))
2578 FDI_SET (format - 1, FMTDIR_ERROR);
2582 add_req_type_constraint (&list, position++, FAT_OBJECT);
2585 case 'W': case 'w': /* 22.3.4.3 FORMAT-WRITE */
2586 if (!check_params (&list, paramcount, params, 0, NULL,
2587 spec->directives, invalid_reason))
2589 FDI_SET (format - 1, FMTDIR_ERROR);
2593 add_req_type_constraint (&list, position++, FAT_OBJECT);
2596 case 'D': case 'd': /* 22.3.2.2 FORMAT-DECIMAL */
2597 case 'B': case 'b': /* 22.3.2.3 FORMAT-BINARY */
2598 case 'O': case 'o': /* 22.3.2.4 FORMAT-OCTAL */
2599 case 'X': case 'x': /* 22.3.2.5 FORMAT-HEXADECIMAL */
2600 if (!check_params (&list, paramcount, params, 4, ICCI,
2601 spec->directives, invalid_reason))
2603 FDI_SET (format - 1, FMTDIR_ERROR);
2607 add_req_type_constraint (&list, position++, FAT_INTEGER);
2610 case 'R': case 'r': /* 22.3.2.1 FORMAT-RADIX */
2611 if (!check_params (&list, paramcount, params, 5, IICCI,
2612 spec->directives, invalid_reason))
2614 FDI_SET (format - 1, FMTDIR_ERROR);
2618 add_req_type_constraint (&list, position++, FAT_INTEGER);
2621 case 'P': case 'p': /* 22.3.8.3 FORMAT-PLURAL */
2622 if (!check_params (&list, paramcount, params, 0, NULL,
2623 spec->directives, invalid_reason))
2625 FDI_SET (format - 1, FMTDIR_ERROR);
2630 /* Go back by 1 argument. */
2635 add_req_type_constraint (&list, position++, FAT_OBJECT);
2638 case 'C': case 'c': /* 22.3.1.1 FORMAT-CHARACTER */
2639 if (!check_params (&list, paramcount, params, 0, NULL,
2640 spec->directives, invalid_reason))
2642 FDI_SET (format - 1, FMTDIR_ERROR);
2646 add_req_type_constraint (&list, position++, FAT_CHARACTER);
2649 case 'F': case 'f': /* 22.3.3.1 FORMAT-FIXED-FLOAT */
2650 if (!check_params (&list, paramcount, params, 5, IIICC,
2651 spec->directives, invalid_reason))
2653 FDI_SET (format - 1, FMTDIR_ERROR);
2657 add_req_type_constraint (&list, position++, FAT_REAL);
2660 case 'E': case 'e': /* 22.3.3.2 FORMAT-EXPONENTIAL-FLOAT */
2661 case 'G': case 'g': /* 22.3.3.3 FORMAT-GENERAL-FLOAT */
2662 if (!check_params (&list, paramcount, params, 7, IIIICCC,
2663 spec->directives, invalid_reason))
2665 FDI_SET (format - 1, FMTDIR_ERROR);
2669 add_req_type_constraint (&list, position++, FAT_REAL);
2672 case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */
2673 if (!check_params (&list, paramcount, params, 4, IIIC,
2674 spec->directives, invalid_reason))
2676 FDI_SET (format - 1, FMTDIR_ERROR);
2680 add_req_type_constraint (&list, position++, FAT_REAL);
2683 case '%': /* 22.3.1.2 FORMAT-TERPRI */
2684 case '&': /* 22.3.1.3 FORMAT-FRESH-LINE */
2685 case '|': /* 22.3.1.4 FORMAT-PAGE */
2686 case '~': /* 22.3.1.5 FORMAT-TILDE */
2687 case 'I': case 'i': /* 22.3.5.3 */
2688 if (!check_params (&list, paramcount, params, 1, I,
2689 spec->directives, invalid_reason))
2691 FDI_SET (format - 1, FMTDIR_ERROR);
2696 case '\n': /* 22.3.9.3 #\Newline */
2697 case '_': /* 22.3.5.1 */
2698 if (!check_params (&list, paramcount, params, 0, NULL,
2699 spec->directives, invalid_reason))
2701 FDI_SET (format - 1, FMTDIR_ERROR);
2706 case 'T': case 't': /* 22.3.6.1 FORMAT-TABULATE */
2707 if (!check_params (&list, paramcount, params, 2, II,
2708 spec->directives, invalid_reason))
2710 FDI_SET (format - 1, FMTDIR_ERROR);
2715 case '*': /* 22.3.7.1 FORMAT-GOTO */
2716 if (!check_params (&list, paramcount, params, 1, I,
2717 spec->directives, invalid_reason))
2719 FDI_SET (format - 1, FMTDIR_ERROR);
2723 int n; /* value of first parameter */
2725 || (paramcount >= 1 && params[0].type == PT_NIL))
2726 n = (atsign_p ? 0 : 1);
2727 else if (paramcount >= 1 && params[0].type == PT_INTEGER)
2728 n = params[0].value;
2731 /* Unknown argument, leads to an unknown position. */
2737 /* invalid argument */
2739 xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
2740 FDI_SET (format - 1, FMTDIR_ERROR);
2745 /* Absolute goto. */
2750 /* Backward goto. */
2773 case '?': /* 22.3.7.6 FORMAT-INDIRECTION */
2774 if (!check_params (&list, paramcount, params, 0, NULL,
2775 spec->directives, invalid_reason))
2777 FDI_SET (format - 1, FMTDIR_ERROR);
2781 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
2787 struct format_arg_list *sublist = make_unconstrained_list ();
2788 add_req_listtype_constraint (&list, position++,
2790 free_list (sublist);
2794 case '/': /* 22.3.5.4 FORMAT-CALL-USER-FUNCTION */
2795 if (!check_params (&list, paramcount, params, 0, NULL,
2796 spec->directives, invalid_reason))
2798 FDI_SET (format - 1, FMTDIR_ERROR);
2802 add_req_type_constraint (&list, position++, FAT_OBJECT);
2803 while (*format != '\0' && *format != '/')
2805 if (*format == '\0')
2808 xstrdup (_("The string ends in the middle of a ~/.../ directive."));
2809 FDI_SET (format - 1, FMTDIR_ERROR);
2815 case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */
2816 if (!check_params (&list, paramcount, params, 0, NULL,
2817 spec->directives, invalid_reason))
2819 FDI_SET (format - 1, FMTDIR_ERROR);
2823 *positionp = position;
2827 if (!parse_upto (formatp, positionp, listp, escapep,
2828 NULL, spec, ')', false,
2829 NULL, invalid_reason))
2831 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2837 position = *positionp;
2842 case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */
2843 if (terminator != ')')
2846 xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
2847 FDI_SET (format - 1, FMTDIR_ERROR);
2850 if (!check_params (&list, paramcount, params, 0, NULL,
2851 spec->directives, invalid_reason))
2853 FDI_SET (format - 1, FMTDIR_ERROR);
2857 *positionp = position;
2862 case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */
2863 if (atsign_p && colon_p)
2866 xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
2867 FDI_SET (format - 1, FMTDIR_ERROR);
2872 struct format_arg_list *nil_list;
2873 struct format_arg_list *union_list;
2875 if (!check_params (&list, paramcount, params, 0, NULL,
2876 spec->directives, invalid_reason))
2878 FDI_SET (format - 1, FMTDIR_ERROR);
2885 /* First alternative: argument is NIL. */
2886 nil_list = (list != NULL ? copy_list (list) : NULL);
2889 struct format_arg_list *empty_list = make_empty_list ();
2890 add_req_listtype_constraint (&nil_list, position,
2891 FAT_LIST, empty_list);
2892 free_list (empty_list);
2895 /* Second alternative: use sub-format. */
2897 int sub_position = position;
2898 struct format_arg_list *sub_list =
2899 (list != NULL ? copy_list (list) : NULL);
2900 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2901 NULL, spec, ']', false,
2902 NULL, invalid_reason))
2904 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2908 if (sub_list != NULL)
2912 if (sub_position == position + 1)
2913 /* new position is branch independent */
2914 position = position + 1;
2916 /* new position is branch dependent */
2923 position = position + 1;
2925 union_list = union (nil_list, sub_list);
2938 struct format_arg_list *union_list;
2940 if (!check_params (&list, paramcount, params, 0, NULL,
2941 spec->directives, invalid_reason))
2943 FDI_SET (format - 1, FMTDIR_ERROR);
2948 add_req_type_constraint (&list, position++, FAT_OBJECT);
2952 union_position = -2;
2955 /* First alternative. */
2957 int sub_position = position;
2958 struct format_arg_list *sub_list =
2959 (list != NULL ? copy_list (list) : NULL);
2960 int sub_separator = 0;
2963 struct format_arg_list *empty_list = make_empty_list ();
2964 add_req_listtype_constraint (&sub_list, position - 1,
2965 FAT_LIST, empty_list);
2966 free_list (empty_list);
2968 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2969 &sub_separator, spec, ']', true,
2970 NULL, invalid_reason))
2972 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2979 xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives);
2980 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2984 if (sub_list != NULL)
2985 union_position = sub_position;
2986 union_list = union (union_list, sub_list);
2989 /* Second alternative. */
2991 int sub_position = position;
2992 struct format_arg_list *sub_list =
2993 (list != NULL ? copy_list (list) : NULL);
2994 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2995 NULL, spec, ']', false,
2996 NULL, invalid_reason))
2998 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3002 if (sub_list != NULL)
3004 if (union_position == -2)
3005 union_position = sub_position;
3006 else if (sub_position < 0
3007 || sub_position != union_position)
3008 union_position = -1;
3010 union_list = union (union_list, sub_list);
3016 if (union_position != -2)
3017 position = union_position;
3026 struct format_arg_list *union_list;
3027 bool last_alternative;
3029 if (!check_params (&list, paramcount, params, 1, I,
3030 spec->directives, invalid_reason))
3032 FDI_SET (format - 1, FMTDIR_ERROR);
3036 /* If there was no first parameter, an argument is consumed. */
3038 if (!(paramcount >= 1 && params[0].type != PT_NIL))
3041 arg_position = position;
3042 add_req_type_constraint (&list, position++, FAT_OBJECT);
3048 union_position = -2;
3050 last_alternative = false;
3053 /* Next alternative. */
3054 int sub_position = position;
3055 struct format_arg_list *sub_list =
3056 (list != NULL ? copy_list (list) : NULL);
3057 int sub_separator = 0;
3058 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
3059 &sub_separator, spec, ']', !last_alternative,
3060 NULL, invalid_reason))
3062 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3066 /* If this alternative is chosen, the argument arg_position
3067 is an integer, namely the index of this alternative. */
3068 if (!last_alternative && arg_position >= 0)
3069 add_req_type_constraint (&sub_list, arg_position,
3071 if (sub_list != NULL)
3073 if (union_position == -2)
3074 union_position = sub_position;
3075 else if (sub_position < 0
3076 || sub_position != union_position)
3077 union_position = -1;
3079 union_list = union (union_list, sub_list);
3080 if (sub_separator == 2)
3081 last_alternative = true;
3085 if (!last_alternative)
3087 /* An implicit default alternative. */
3088 if (union_position == -2)
3089 union_position = position;
3090 else if (position < 0 || position != union_position)
3091 union_position = -1;
3093 union_list = union (union_list, copy_list (list));
3099 if (union_position != -2)
3100 position = union_position;
3107 case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */
3108 if (terminator != ']')
3111 xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
3112 FDI_SET (format - 1, FMTDIR_ERROR);
3115 if (!check_params (&list, paramcount, params, 0, NULL,
3116 spec->directives, invalid_reason))
3118 FDI_SET (format - 1, FMTDIR_ERROR);
3122 *positionp = position;
3127 case '{': /* 22.3.7.4 FORMAT-ITERATION */
3128 if (!check_params (&list, paramcount, params, 1, I,
3129 spec->directives, invalid_reason))
3131 FDI_SET (format - 1, FMTDIR_ERROR);
3136 int sub_position = 0;
3137 struct format_arg_list *sub_list = make_unconstrained_list ();
3138 struct format_arg_list *sub_escape = NULL;
3139 struct spec sub_spec;
3140 sub_spec.directives = 0;
3141 sub_spec.list = sub_list;
3142 if (!parse_upto (formatp, &sub_position, &sub_list, &sub_escape,
3143 NULL, &sub_spec, '}', false,
3144 NULL, invalid_reason))
3146 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3150 spec->directives += sub_spec.directives;
3152 /* If the sub-formatstring is empty, except for the terminating
3153 ~} directive, a formatstring argument is consumed. */
3154 if (*format == '~' && sub_spec.directives == 1)
3156 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
3160 /* Each iteration uses a new sublist. */
3161 struct format_arg_list *listlist;
3163 /* ~{ catches ~^. */
3164 sub_list = union (sub_list, sub_escape);
3166 listlist = make_repeated_list_of_lists (sub_list);
3168 sub_list = listlist;
3172 /* Each iteration's arguments are all concatenated in a
3174 struct format_arg_list *looplist;
3176 /* FIXME: This is far from correct. Test cases:
3182 abc~{~D~^~C~}~:*~{~S~^~D~}
3185 /* ~{ catches ~^. */
3186 sub_list = union (sub_list, sub_escape);
3188 if (sub_list == NULL)
3189 looplist = make_empty_list ();
3191 if (sub_position < 0 || sub_position == 0)
3192 /* Too hard to track the possible argument types
3193 when the iteration is performed 2 times or more.
3194 So be satisfied with the constraints of executing
3195 the iteration 1 or 0 times. */
3196 looplist = make_union_with_empty_list (sub_list);
3198 looplist = make_repeated_list (sub_list, sub_position);
3200 sub_list = looplist;
3205 /* All remaining arguments are used. */
3206 if (list != NULL && position >= 0)
3208 shift_list (sub_list, position);
3209 list = make_intersected_list (list, sub_list);
3215 /* The argument is a list. */
3217 add_req_listtype_constraint (&list, position++,
3218 FAT_LIST, sub_list);
3224 case '}': /* 22.3.7.5 FORMAT-ITERATION-END */
3225 if (terminator != '}')
3228 xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
3229 FDI_SET (format - 1, FMTDIR_ERROR);
3232 if (!check_params (&list, paramcount, params, 0, NULL,
3233 spec->directives, invalid_reason))
3235 FDI_SET (format - 1, FMTDIR_ERROR);
3239 *positionp = position;
3244 case '<': /* 22.3.6.2, 22.3.5.2 FORMAT-JUSTIFICATION */
3245 if (!check_params (&list, paramcount, params, 4, IIIC,
3246 spec->directives, invalid_reason))
3248 FDI_SET (format - 1, FMTDIR_ERROR);
3252 struct format_arg_list *sub_escape = NULL;
3255 *positionp = position;
3260 int sub_separator = 0;
3261 if (!parse_upto (formatp, positionp, listp, &sub_escape,
3262 &sub_separator, spec, '>', true,
3263 NULL, invalid_reason))
3265 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3274 position = *positionp;
3277 /* ~< catches ~^. */
3278 if (sub_escape != NULL)
3280 list = union (list, sub_escape);
3284 case '>': /* 22.3.6.3 FORMAT-JUSTIFICATION-END */
3285 if (terminator != '>')
3288 xasprintf (_("Found '~%c' without matching '~%c'."), '>', '<');
3289 FDI_SET (format - 1, FMTDIR_ERROR);
3292 if (!check_params (&list, paramcount, params, 0, NULL,
3293 spec->directives, invalid_reason))
3295 FDI_SET (format - 1, FMTDIR_ERROR);
3299 *positionp = position;
3304 case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */
3305 if (!check_params (&list, paramcount, params, 3, THREE,
3306 spec->directives, invalid_reason))
3308 FDI_SET (format - 1, FMTDIR_ERROR);
3311 if (position >= 0 && list != NULL && is_required (list, position))
3312 /* This ~^ can never be executed. Ignore it. */
3316 struct format_arg_list *this_escape = copy_list (list);
3318 this_escape = add_end_constraint (this_escape, position);
3319 escape = union (escape, this_escape);
3322 list = add_required_constraint (list, position);
3325 case ';': /* 22.3.9.1 FORMAT-SEPARATOR */
3329 xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
3330 FDI_SET (format - 1, FMTDIR_ERROR);
3333 if (terminator == '>')
3335 if (!check_params (&list, paramcount, params, 1, I,
3336 spec->directives, invalid_reason))
3338 FDI_SET (format - 1, FMTDIR_ERROR);
3344 if (!check_params (&list, paramcount, params, 0, NULL,
3345 spec->directives, invalid_reason))
3347 FDI_SET (format - 1, FMTDIR_ERROR);
3352 *positionp = position;
3355 *separatorp = (colon_p ? 2 : 1);
3358 case '!': /* FORMAT-CALL, a CLISP extension */
3359 if (!nocheck_params (&list, paramcount, params,
3360 spec->directives, invalid_reason))
3362 FDI_SET (format - 1, FMTDIR_ERROR);
3367 add_req_type_constraint (&list, position++, FAT_FUNCTION);
3368 add_req_type_constraint (&list, position++, FAT_OBJECT);
3374 if (*format == '\0')
3376 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
3377 FDI_SET (format - 1, FMTDIR_ERROR);
3382 INVALID_CONVERSION_SPECIFIER (spec->directives, *format);
3383 FDI_SET (format, FMTDIR_ERROR);
3388 FDI_SET (format - 1, FMTDIR_END);
3394 *positionp = position;
3397 if (terminator != '\0')
3400 xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator);
3407 /* ============== Top level format string handling functions ============== */
3410 format_parse (const char *format, bool translated, char *fdi,
3411 char **invalid_reason)
3414 struct spec *result;
3416 struct format_arg_list *escape;
3418 spec.directives = 0;
3419 spec.list = make_unconstrained_list ();
3422 if (!parse_upto (&format, &position, &spec.list, &escape,
3423 NULL, &spec, '\0', false,
3424 fdi, invalid_reason))
3425 /* Invalid format string. */
3428 /* Catch ~^ here. */
3429 spec.list = union (spec.list, escape);
3431 if (spec.list == NULL)
3433 /* Contradictory argument type information. */
3435 xstrdup (_("The string refers to some argument in incompatible ways."));
3439 /* Normalize the result. */
3440 normalize_list (spec.list);
3442 result = XMALLOC (struct spec);
3448 format_free (void *descr)
3450 struct spec *spec = (struct spec *) descr;
3452 free_list (spec->list);
3456 format_get_number_of_directives (void *descr)
3458 struct spec *spec = (struct spec *) descr;
3460 return spec->directives;
3464 format_check (void *msgid_descr, void *msgstr_descr, bool equality,
3465 formatstring_error_logger_t error_logger,
3466 const char *pretty_msgid, const char *pretty_msgstr)
3468 struct spec *spec1 = (struct spec *) msgid_descr;
3469 struct spec *spec2 = (struct spec *) msgstr_descr;
3474 if (!equal_list (spec1->list, spec2->list))
3477 error_logger (_("format specifications in '%s' and '%s' are not equivalent"),
3478 pretty_msgid, pretty_msgstr);
3484 struct format_arg_list *intersection =
3485 make_intersected_list (copy_list (spec1->list),
3486 copy_list (spec2->list));
3488 if (!(intersection != NULL
3489 && (normalize_list (intersection),
3490 equal_list (intersection, spec2->list))))
3493 error_logger (_("format specifications in '%s' are not a subset of those in '%s'"),
3494 pretty_msgstr, pretty_msgid);
3503 struct formatstring_parser formatstring_lisp =
3507 format_get_number_of_directives,
3513 /* ============================= Testing code ============================= */
3519 /* Test program: Print the argument list specification returned by
3520 format_parse for strings read from standard input. */
3524 static void print_list (struct format_arg_list *list);
3527 print_element (struct format_arg *element)
3529 switch (element->presence)
3540 switch (element->type)
3545 case FAT_CHARACTER_INTEGER_NULL:
3548 case FAT_CHARACTER_NULL:
3554 case FAT_INTEGER_NULL:
3564 print_list (element->list);
3566 case FAT_FORMATSTRING:
3578 print_list (struct format_arg_list *list)
3584 for (i = 0; i < list->initial.count; i++)
3585 for (j = 0; j < list->initial.element[i].repcount; j++)
3589 print_element (&list->initial.element[i]);
3592 if (list->repeated.count > 0)
3595 for (i = 0; i < list->repeated.count; i++)
3596 for (j = 0; j < list->repeated.element[i].repcount; j++)
3599 print_element (&list->repeated.element[i]);
3607 format_print (void *descr)
3609 struct spec *spec = (struct spec *) descr;
3617 print_list (spec->list);
3626 size_t line_size = 0;
3628 char *invalid_reason;
3631 line_len = getline (&line, &line_size, stdin);
3634 if (line_len > 0 && line[line_len - 1] == '\n')
3635 line[--line_len] = '\0';
3637 invalid_reason = NULL;
3638 descr = format_parse (line, false, NULL, &invalid_reason);
3640 format_print (descr);
3643 printf ("%s\n", invalid_reason);
3645 free (invalid_reason);
3653 * For Emacs M-x compile
3655 * compile-command: "/bin/sh ../libtool --tag=CC --mode=link gcc -o a.out -static -O -g -Wall -I.. -I../gnulib-lib -I../intl -DHAVE_CONFIG_H -DTEST format-lisp.c ../gnulib-lib/libgettextlib.la"