1 /* Lisp format strings.
2 Copyright (C) 2001-2004, 2006-2007, 2009 Free Software Foundation, Inc.
3 Written by Bruno Haible <haible@clisp.cons.org>, 2001.
5 This program is free software: you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 3 of the License, or
8 (at your option) any later version.
10 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>. */
29 #include "xvasprintf.h"
30 #include "format-invalid.h"
34 #define _(str) gettext (str)
37 /* Assertion macros. Could be defined to empty for speed. */
38 #define ASSERT(expr) if (!(expr)) abort ();
39 #define VERIFY_LIST(list) verify_list (list)
42 /* Lisp format strings are described in the Common Lisp HyperSpec,
43 chapter 22.3 "Formatted Output". */
45 /* Data structure describing format string derived constraints for an
46 argument list. It is a recursive list structure. Structure sharing
51 FCT_REQUIRED, /* The format argument list cannot end before this argument. */
52 FCT_OPTIONAL /* The format argument list may end before this argument. */
57 FAT_OBJECT, /* Any object, type T. */
58 FAT_CHARACTER_INTEGER_NULL, /* Type (OR CHARACTER INTEGER NULL). */
59 FAT_CHARACTER_NULL, /* Type (OR CHARACTER NULL). */
60 FAT_CHARACTER, /* Type CHARACTER. */
61 FAT_INTEGER_NULL, /* Type (OR INTEGER NULL). */
62 FAT_INTEGER, /* Meant for objects of type INTEGER. */
63 FAT_REAL, /* Meant for objects of type REAL. */
64 FAT_LIST, /* Meant for proper lists. */
65 FAT_FORMATSTRING, /* Format strings. */
66 FAT_FUNCTION /* Function. */
71 unsigned int repcount; /* Number of consecutive arguments this constraint
72 applies to. Normally 1, but unconstrained
73 arguments are often repeated. */
74 enum format_cdr_type presence; /* Can the argument list end right before
76 enum format_arg_type type; /* Possible values for this argument. */
77 struct format_arg_list *list; /* For FAT_LIST: List elements. */
82 unsigned int count; /* Number of format_arg records used. */
83 unsigned int allocated;
84 struct format_arg *element; /* Argument constraints. */
85 unsigned int length; /* Number of arguments represented by this segment.
86 This is the sum of all repcounts in the segment. */
89 struct format_arg_list
91 /* The constraints for the potentially infinite argument list are assumed
92 to become ultimately periodic. (Too complicated argument lists without
94 (format t "~@{~:[-~;~S~]~}" nil t 1 t 3 nil t 4)
95 are described by a constraint that ends in a length 1 period of
96 unconstrained arguments.) Such a periodic sequence can be split into
97 an initial segment and an endlessly repeated loop segment.
98 A finite sequence is represented entirely in the initial segment; the
99 loop segment is empty. */
101 struct segment initial; /* Initial arguments segment. */
102 struct segment repeated; /* Endlessly repeated segment. */
107 unsigned int directives;
108 struct format_arg_list *list;
112 /* Parameter for a directive. */
115 PT_NIL, /* param not present */
116 PT_CHARACTER, /* character */
117 PT_INTEGER, /* integer */
118 PT_ARGCOUNT, /* number of remaining arguments */
119 PT_V /* variable taken from argument list */
124 enum param_type type;
125 int value; /* for PT_INTEGER: the value, for PT_V: the position */
129 /* Forward declaration of local functions. */
130 #define union make_union
131 static void verify_list (const struct format_arg_list *list);
132 static void free_list (struct format_arg_list *list);
133 static struct format_arg_list * copy_list (const struct format_arg_list *list);
134 static bool equal_list (const struct format_arg_list *list1,
135 const struct format_arg_list *list2);
136 static struct format_arg_list * make_intersected_list
137 (struct format_arg_list *list1,
138 struct format_arg_list *list2);
139 static struct format_arg_list * make_intersection_with_empty_list
140 (struct format_arg_list *list);
141 static struct format_arg_list * make_union_list
142 (struct format_arg_list *list1,
143 struct format_arg_list *list2);
146 /* ======================= Verify a format_arg_list ======================= */
148 /* Verify some invariants. */
150 verify_element (const struct format_arg * e)
152 ASSERT (e->repcount > 0);
153 if (e->type == FAT_LIST)
154 verify_list (e->list);
157 /* Verify some invariants. */
158 /* Memory effects: none. */
160 verify_list (const struct format_arg_list *list)
163 unsigned int total_repcount;
165 ASSERT (list->initial.count <= list->initial.allocated);
167 for (i = 0; i < list->initial.count; i++)
169 verify_element (&list->initial.element[i]);
170 total_repcount += list->initial.element[i].repcount;
172 ASSERT (total_repcount == list->initial.length);
174 ASSERT (list->repeated.count <= list->repeated.allocated);
176 for (i = 0; i < list->repeated.count; i++)
178 verify_element (&list->repeated.element[i]);
179 total_repcount += list->repeated.element[i].repcount;
181 ASSERT (total_repcount == list->repeated.length);
184 #define VERIFY_LIST(list) verify_list (list)
187 /* ======================== Free a format_arg_list ======================== */
189 /* Free the data belonging to an argument list element. */
191 free_element (struct format_arg *element)
193 if (element->type == FAT_LIST)
194 free_list (element->list);
197 /* Free an argument list. */
198 /* Memory effects: Frees list. */
200 free_list (struct format_arg_list *list)
204 for (i = 0; i < list->initial.count; i++)
205 free_element (&list->initial.element[i]);
206 if (list->initial.element != NULL)
207 free (list->initial.element);
209 for (i = 0; i < list->repeated.count; i++)
210 free_element (&list->repeated.element[i]);
211 if (list->repeated.element != NULL)
212 free (list->repeated.element);
216 /* ======================== Copy a format_arg_list ======================== */
218 /* Copy the data belonging to an argument list element. */
220 copy_element (struct format_arg *newelement,
221 const struct format_arg *oldelement)
223 newelement->repcount = oldelement->repcount;
224 newelement->presence = oldelement->presence;
225 newelement->type = oldelement->type;
226 if (oldelement->type == FAT_LIST)
227 newelement->list = copy_list (oldelement->list);
230 /* Copy an argument list. */
231 /* Memory effects: Freshly allocated result. */
232 static struct format_arg_list *
233 copy_list (const struct format_arg_list *list)
235 struct format_arg_list *newlist;
241 newlist = XMALLOC (struct format_arg_list);
243 newlist->initial.count = newlist->initial.allocated = list->initial.count;
245 if (list->initial.count == 0)
246 newlist->initial.element = NULL;
249 newlist->initial.element =
250 XNMALLOC (newlist->initial.allocated, struct format_arg);
251 for (i = 0; i < list->initial.count; i++)
253 copy_element (&newlist->initial.element[i],
254 &list->initial.element[i]);
255 length += list->initial.element[i].repcount;
258 ASSERT (length == list->initial.length);
259 newlist->initial.length = length;
261 newlist->repeated.count = newlist->repeated.allocated = list->repeated.count;
263 if (list->repeated.count == 0)
264 newlist->repeated.element = NULL;
267 newlist->repeated.element =
268 XNMALLOC (newlist->repeated.allocated, struct format_arg);
269 for (i = 0; i < list->repeated.count; i++)
271 copy_element (&newlist->repeated.element[i],
272 &list->repeated.element[i]);
273 length += list->repeated.element[i].repcount;
276 ASSERT (length == list->repeated.length);
277 newlist->repeated.length = length;
279 VERIFY_LIST (newlist);
285 /* ===================== Compare two format_arg_lists ===================== */
287 /* Tests whether two normalized argument constraints are equivalent,
288 ignoring the repcount. */
290 equal_element (const struct format_arg * e1, const struct format_arg * e2)
292 return (e1->presence == e2->presence
293 && e1->type == e2->type
294 && (e1->type == FAT_LIST ? equal_list (e1->list, e2->list) : true));
297 /* Tests whether two normalized argument list constraints are equivalent. */
298 /* Memory effects: none. */
300 equal_list (const struct format_arg_list *list1,
301 const struct format_arg_list *list2)
308 n = list1->initial.count;
309 if (n != list2->initial.count)
311 for (i = 0; i < n; i++)
313 const struct format_arg * e1 = &list1->initial.element[i];
314 const struct format_arg * e2 = &list2->initial.element[i];
316 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
320 n = list1->repeated.count;
321 if (n != list2->repeated.count)
323 for (i = 0; i < n; i++)
325 const struct format_arg * e1 = &list1->repeated.element[i];
326 const struct format_arg * e2 = &list2->repeated.element[i];
328 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
336 /* ===================== Incremental memory allocation ===================== */
338 /* Ensure list->initial.allocated >= newcount. */
340 ensure_initial_alloc (struct format_arg_list *list, unsigned int newcount)
342 if (newcount > list->initial.allocated)
344 list->initial.allocated =
345 MAX (2 * list->initial.allocated + 1, newcount);
346 list->initial.element =
347 (struct format_arg *)
348 xrealloc (list->initial.element,
349 list->initial.allocated * sizeof (struct format_arg));
353 /* Ensure list->initial.allocated > list->initial.count. */
355 grow_initial_alloc (struct format_arg_list *list)
357 if (list->initial.count >= list->initial.allocated)
359 list->initial.allocated =
360 MAX (2 * list->initial.allocated + 1, list->initial.count + 1);
361 list->initial.element =
362 (struct format_arg *)
363 xrealloc (list->initial.element,
364 list->initial.allocated * sizeof (struct format_arg));
368 /* Ensure list->repeated.allocated >= newcount. */
370 ensure_repeated_alloc (struct format_arg_list *list, unsigned int newcount)
372 if (newcount > list->repeated.allocated)
374 list->repeated.allocated =
375 MAX (2 * list->repeated.allocated + 1, newcount);
376 list->repeated.element =
377 (struct format_arg *)
378 xrealloc (list->repeated.element,
379 list->repeated.allocated * sizeof (struct format_arg));
383 /* Ensure list->repeated.allocated > list->repeated.count. */
385 grow_repeated_alloc (struct format_arg_list *list)
387 if (list->repeated.count >= list->repeated.allocated)
389 list->repeated.allocated =
390 MAX (2 * list->repeated.allocated + 1, list->repeated.count + 1);
391 list->repeated.element =
392 (struct format_arg *)
393 xrealloc (list->repeated.element,
394 list->repeated.allocated * sizeof (struct format_arg));
399 /* ====================== Normalize a format_arg_list ====================== */
401 /* Normalize an argument list constraint, assuming all sublists are already
403 /* Memory effects: Destructively modifies list. */
405 normalize_outermost_list (struct format_arg_list *list)
407 unsigned int n, i, j;
409 /* Step 1: Combine adjacent elements.
410 Copy from i to j, keeping 0 <= j <= i. */
412 n = list->initial.count;
413 for (i = j = 0; i < n; i++)
415 && equal_element (&list->initial.element[i],
416 &list->initial.element[j-1]))
418 list->initial.element[j-1].repcount +=
419 list->initial.element[i].repcount;
420 free_element (&list->initial.element[i]);
425 list->initial.element[j] = list->initial.element[i];
428 list->initial.count = j;
430 n = list->repeated.count;
431 for (i = j = 0; i < n; i++)
433 && equal_element (&list->repeated.element[i],
434 &list->repeated.element[j-1]))
436 list->repeated.element[j-1].repcount +=
437 list->repeated.element[i].repcount;
438 free_element (&list->repeated.element[i]);
443 list->repeated.element[j] = list->repeated.element[i];
446 list->repeated.count = j;
448 /* Nothing more to be done if the loop segment is empty. */
449 if (list->repeated.count > 0)
451 unsigned int m, repcount0_extra;
453 /* Step 2: Reduce the loop period. */
454 n = list->repeated.count;
457 && equal_element (&list->repeated.element[0],
458 &list->repeated.element[n-1]))
460 repcount0_extra = list->repeated.element[n-1].repcount;
463 /* Proceed as if the loop period were n, with
464 list->repeated.element[0].repcount incremented by repcount0_extra. */
465 for (m = 2; m <= n / 2; n++)
468 /* m is a divisor of n. Try to reduce the loop period to n. */
471 for (i = 0; i < n - m; i++)
472 if (!((list->repeated.element[i].repcount
473 + (i == 0 ? repcount0_extra : 0)
474 == list->repeated.element[i+m].repcount)
475 && equal_element (&list->repeated.element[i],
476 &list->repeated.element[i+m])))
483 for (i = m; i < n; i++)
484 free_element (&list->repeated.element[i]);
485 if (n < list->repeated.count)
486 list->repeated.element[m] = list->repeated.element[n];
487 list->repeated.count = list->repeated.count - n + m;
488 list->repeated.length /= n / m;
493 /* Step 3: Roll as much as possible of the initial segment's tail
495 if (list->repeated.count == 1)
497 if (list->initial.count > 0
498 && equal_element (&list->initial.element[list->initial.count-1],
499 &list->repeated.element[0]))
501 /* Roll the last element of the initial segment into the loop.
502 Its repcount is irrelevant. The second-to-last element is
503 certainly different and doesn't need to be considered. */
504 list->initial.length -=
505 list->initial.element[list->initial.count-1].repcount;
506 list->initial.count--;
511 while (list->initial.count > 0
512 && equal_element (&list->initial.element[list->initial.count-1],
513 &list->repeated.element[list->repeated.count-1]))
515 unsigned int moved_repcount =
516 MIN (list->initial.element[list->initial.count-1].repcount,
517 list->repeated.element[list->repeated.count-1].repcount);
519 /* Add the element at the start of list->repeated. */
520 if (equal_element (&list->repeated.element[0],
521 &list->repeated.element[list->repeated.count-1]))
522 list->repeated.element[0].repcount += moved_repcount;
525 unsigned int newcount = list->repeated.count + 1;
526 ensure_repeated_alloc (list, newcount);
527 for (i = newcount - 1; i > 0; i--)
528 list->repeated.element[i] = list->repeated.element[i-1];
529 list->repeated.count = newcount;
530 copy_element (&list->repeated.element[0],
531 &list->repeated.element[list->repeated.count-1]);
532 list->repeated.element[0].repcount = moved_repcount;
535 /* Remove the element from the end of list->repeated. */
536 list->repeated.element[list->repeated.count-1].repcount -=
538 if (list->repeated.element[list->repeated.count-1].repcount == 0)
540 free_element (&list->repeated.element[list->repeated.count-1]);
541 list->repeated.count--;
544 /* Remove the element from the end of list->initial. */
545 list->initial.element[list->initial.count-1].repcount -=
547 if (list->initial.element[list->initial.count-1].repcount == 0)
549 free_element (&list->initial.element[list->initial.count-1]);
550 list->initial.count--;
552 list->initial.length -= moved_repcount;
558 /* Normalize an argument list constraint. */
559 /* Memory effects: Destructively modifies list. */
561 normalize_list (struct format_arg_list *list)
567 /* First normalize all elements, recursively. */
568 n = list->initial.count;
569 for (i = 0; i < n; i++)
570 if (list->initial.element[i].type == FAT_LIST)
571 normalize_list (list->initial.element[i].list);
572 n = list->repeated.count;
573 for (i = 0; i < n; i++)
574 if (list->repeated.element[i].type == FAT_LIST)
575 normalize_list (list->repeated.element[i].list);
577 /* Then normalize the top level list. */
578 normalize_outermost_list (list);
584 /* ===================== Unconstrained and empty lists ===================== */
586 /* It's easier to allocate these on demand, than to be careful not to
587 accidentally modify statically allocated lists. */
590 /* Create an unconstrained argument list. */
591 /* Memory effects: Freshly allocated result. */
592 static struct format_arg_list *
593 make_unconstrained_list ()
595 struct format_arg_list *list;
597 list = XMALLOC (struct format_arg_list);
598 list->initial.count = 0;
599 list->initial.allocated = 0;
600 list->initial.element = NULL;
601 list->initial.length = 0;
602 list->repeated.count = 1;
603 list->repeated.allocated = 1;
604 list->repeated.element = XNMALLOC (1, struct format_arg);
605 list->repeated.element[0].repcount = 1;
606 list->repeated.element[0].presence = FCT_OPTIONAL;
607 list->repeated.element[0].type = FAT_OBJECT;
608 list->repeated.length = 1;
616 /* Create an empty argument list. */
617 /* Memory effects: Freshly allocated result. */
618 static struct format_arg_list *
621 struct format_arg_list *list;
623 list = XMALLOC (struct format_arg_list);
624 list->initial.count = 0;
625 list->initial.allocated = 0;
626 list->initial.element = NULL;
627 list->initial.length = 0;
628 list->repeated.count = 0;
629 list->repeated.allocated = 0;
630 list->repeated.element = NULL;
631 list->repeated.length = 0;
639 /* Test for an empty list. */
640 /* Memory effects: none. */
642 is_empty_list (const struct format_arg_list *list)
644 return (list->initial.count == 0 && list->repeated.count == 0);
648 /* ======================== format_arg_list surgery ======================== */
650 /* Unfold list->repeated m times, where m >= 1.
651 Assumes list->repeated.count > 0. */
652 /* Memory effects: list is destructively modified. */
654 unfold_loop (struct format_arg_list *list, unsigned int m)
656 unsigned int i, j, k;
660 unsigned int newcount = list->repeated.count * m;
661 ensure_repeated_alloc (list, newcount);
662 i = list->repeated.count;
663 for (k = 1; k < m; k++)
664 for (j = 0; j < list->repeated.count; j++, i++)
665 copy_element (&list->repeated.element[i], &list->repeated.element[j]);
666 list->repeated.count = newcount;
667 list->repeated.length = list->repeated.length * m;
671 /* Ensure list->initial.length := m, where m >= list->initial.length.
672 Assumes list->repeated.count > 0. */
673 /* Memory effects: list is destructively modified. */
675 rotate_loop (struct format_arg_list *list, unsigned int m)
677 if (m == list->initial.length)
680 if (list->repeated.count == 1)
682 /* Instead of multiple copies of list->repeated.element[0], a single
683 copy with higher repcount is appended to list->initial. */
684 unsigned int i, newcount;
686 newcount = list->initial.count + 1;
687 ensure_initial_alloc (list, newcount);
688 i = list->initial.count;
689 copy_element (&list->initial.element[i], &list->repeated.element[0]);
690 list->initial.element[i].repcount = m - list->initial.length;
691 list->initial.count = newcount;
692 list->initial.length = m;
696 unsigned int n = list->repeated.length;
698 /* Write m = list->initial.length + q * n + r with 0 <= r < n. */
699 unsigned int q = (m - list->initial.length) / n;
700 unsigned int r = (m - list->initial.length) % n;
702 /* Determine how many entries of list->repeated are needed for
708 s < list->repeated.count && t >= list->repeated.element[s].repcount;
709 t -= list->repeated.element[s].repcount, s++)
712 /* s must be < list->repeated.count, otherwise r would have been >= n. */
713 ASSERT (s < list->repeated.count);
715 /* So we need to add to list->initial:
716 q full copies of list->repeated,
717 plus the s first elements of list->repeated,
718 plus, if t > 0, a splitoff of list->repeated.element[s]. */
720 unsigned int i, j, k, newcount;
722 i = list->initial.count;
723 newcount = i + q * list->repeated.count + s + (t > 0 ? 1 : 0);
724 ensure_initial_alloc (list, newcount);
725 for (k = 0; k < q; k++)
726 for (j = 0; j < list->repeated.count; j++, i++)
727 copy_element (&list->initial.element[i],
728 &list->repeated.element[j]);
729 for (j = 0; j < s; j++, i++)
730 copy_element (&list->initial.element[i], &list->repeated.element[j]);
733 copy_element (&list->initial.element[i],
734 &list->repeated.element[j]);
735 list->initial.element[i].repcount = t;
738 ASSERT (i == newcount);
739 list->initial.count = newcount;
740 /* The new length of the initial segment is
741 = list->initial.length
742 + q * list->repeated.length
743 + list->repeated[0..s-1].repcount + t
744 = list->initial.length + q * n + r
747 list->initial.length = m;
750 /* And rotate list->repeated. */
753 unsigned int i, j, oldcount, newcount;
754 struct format_arg *newelement;
756 oldcount = list->repeated.count;
757 newcount = list->repeated.count + (t > 0 ? 1 : 0);
758 newelement = XNMALLOC (newcount, struct format_arg);
760 for (j = s; j < oldcount; j++, i++)
761 newelement[i] = list->repeated.element[j];
762 for (j = 0; j < s; j++, i++)
763 newelement[i] = list->repeated.element[j];
766 copy_element (&newelement[oldcount], &newelement[0]);
767 newelement[0].repcount -= t;
768 newelement[oldcount].repcount = t;
770 free (list->repeated.element);
771 list->repeated.element = newelement;
777 /* Ensure index n in the initial segment falls on a split between elements,
778 i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two
779 different adjacent elements. */
780 /* Memory effects: list is destructively modified. */
782 initial_splitelement (struct format_arg_list *list, unsigned int n)
786 unsigned int oldrepcount;
787 unsigned int newcount;
792 if (n > list->initial.length)
794 ASSERT (list->repeated.count > 0);
795 rotate_loop (list, n);
796 ASSERT (n <= list->initial.length);
799 /* Determine how many entries of list->initial need to be skipped. */
801 s < list->initial.count && t >= list->initial.element[s].repcount;
802 t -= list->initial.element[s].repcount, s++)
808 ASSERT (s < list->initial.count);
810 /* Split the entry into two entries. */
811 oldrepcount = list->initial.element[s].repcount;
812 newcount = list->initial.count + 1;
813 ensure_initial_alloc (list, newcount);
814 for (i = list->initial.count - 1; i > s; i--)
815 list->initial.element[i+1] = list->initial.element[i];
816 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
817 list->initial.element[s].repcount = t;
818 list->initial.element[s+1].repcount = oldrepcount - t;
819 list->initial.count = newcount;
827 /* Ensure index n in the initial segment is not shared. Return its index. */
828 /* Memory effects: list is destructively modified. */
830 initial_unshare (struct format_arg_list *list, unsigned int n)
832 /* This does the same side effects as
833 initial_splitelement (list, n);
834 initial_splitelement (list, n + 1);
841 if (n >= list->initial.length)
843 ASSERT (list->repeated.count > 0);
844 rotate_loop (list, n + 1);
845 ASSERT (n < list->initial.length);
848 /* Determine how many entries of list->initial need to be skipped. */
850 s < list->initial.count && t >= list->initial.element[s].repcount;
851 t -= list->initial.element[s].repcount, s++)
854 /* s must be < list->initial.count. */
855 ASSERT (s < list->initial.count);
857 if (list->initial.element[s].repcount > 1)
859 /* Split the entry into at most three entries: for indices < n,
860 for index n, and for indices > n. */
861 unsigned int oldrepcount = list->initial.element[s].repcount;
862 unsigned int newcount =
863 list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2);
864 ensure_initial_alloc (list, newcount);
865 if (t == 0 || t == oldrepcount - 1)
869 for (i = list->initial.count - 1; i > s; i--)
870 list->initial.element[i+1] = list->initial.element[i];
871 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
874 list->initial.element[s].repcount = 1;
875 list->initial.element[s+1].repcount = oldrepcount - 1;
879 list->initial.element[s].repcount = oldrepcount - 1;
880 list->initial.element[s+1].repcount = 1;
887 for (i = list->initial.count - 1; i > s; i--)
888 list->initial.element[i+2] = list->initial.element[i];
889 copy_element (&list->initial.element[s+2], &list->initial.element[s]);
890 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
891 list->initial.element[s].repcount = t;
892 list->initial.element[s+1].repcount = 1;
893 list->initial.element[s+2].repcount = oldrepcount - 1 - t;
895 list->initial.count = newcount;
900 /* Now the entry for index n has repcount 1. */
901 ASSERT (list->initial.element[s].repcount == 1);
909 /* Add n unconstrained elements at the front of the list. */
910 /* Memory effects: list is destructively modified. */
912 shift_list (struct format_arg_list *list, unsigned int n)
920 grow_initial_alloc (list);
921 for (i = list->initial.count; i > 0; i--)
922 list->initial.element[i] = list->initial.element[i-1];
923 list->initial.element[0].repcount = n;
924 list->initial.element[0].presence = FCT_REQUIRED;
925 list->initial.element[0].type = FAT_OBJECT;
926 list->initial.count++;
927 list->initial.length += n;
929 normalize_outermost_list (list);
936 /* ================= Intersection of two format_arg_lists ================= */
938 /* Create the intersection (i.e. combined constraints) of two argument
939 constraints. Return false if the intersection is empty, i.e. if the
940 two constraints give a contradiction. */
941 /* Memory effects: Freshly allocated element's sublist. */
943 make_intersected_element (struct format_arg *re,
944 const struct format_arg * e1,
945 const struct format_arg * e2)
947 /* Intersect the cdr types. */
948 if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED)
949 re->presence = FCT_REQUIRED;
951 re->presence = FCT_OPTIONAL;
953 /* Intersect the arg types. */
954 if (e1->type == FAT_OBJECT)
957 if (re->type == FAT_LIST)
958 re->list = copy_list (e2->list);
960 else if (e2->type == FAT_OBJECT)
963 if (re->type == FAT_LIST)
964 re->list = copy_list (e1->list);
966 else if (e1->type == FAT_LIST
967 && (e2->type == FAT_CHARACTER_INTEGER_NULL
968 || e2->type == FAT_CHARACTER_NULL
969 || e2->type == FAT_INTEGER_NULL))
972 re->list = make_intersection_with_empty_list (e1->list);
973 if (re->list == NULL)
976 else if (e2->type == FAT_LIST
977 && (e1->type == FAT_CHARACTER_INTEGER_NULL
978 || e1->type == FAT_CHARACTER_NULL
979 || e1->type == FAT_INTEGER_NULL))
982 re->list = make_intersection_with_empty_list (e2->list);
983 if (re->list == NULL)
986 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
987 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
988 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
992 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
993 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
994 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
998 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1000 re->type = e2->type;
1002 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1004 re->type = e1->type;
1006 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1008 re->type = e2->type;
1010 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1012 re->type = e1->type;
1014 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1016 re->type = e2->type;
1018 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1020 re->type = e1->type;
1022 else if (e1->type == e2->type)
1024 re->type = e1->type;
1025 if (re->type == FAT_LIST)
1027 re->list = make_intersected_list (copy_list (e1->list),
1028 copy_list (e2->list));
1029 if (re->list == NULL)
1034 /* Each of FAT_CHARACTER, FAT_INTEGER, FAT_LIST, FAT_FORMATSTRING,
1035 FAT_FUNCTION matches only itself. Contradiction. */
1041 /* Append list->repeated to list->initial, and clear list->repeated. */
1042 /* Memory effects: list is destructively modified. */
1044 append_repeated_to_initial (struct format_arg_list *list)
1046 if (list->repeated.count > 0)
1048 /* Move list->repeated over to list->initial. */
1049 unsigned int i, j, newcount;
1051 newcount = list->initial.count + list->repeated.count;
1052 ensure_initial_alloc (list, newcount);
1053 i = list->initial.count;
1054 for (j = 0; j < list->repeated.count; j++, i++)
1055 list->initial.element[i] = list->repeated.element[j];
1056 list->initial.count = newcount;
1057 list->initial.length = list->initial.length + list->repeated.length;
1058 free (list->repeated.element);
1059 list->repeated.element = NULL;
1060 list->repeated.allocated = 0;
1061 list->repeated.count = 0;
1062 list->repeated.length = 0;
1066 /* Handle a contradiction during building of a format_arg_list.
1067 The list consists only of an initial segment. The repeated segment is
1068 empty. This function searches the last FCT_OPTIONAL and cuts off the
1069 list at this point, or - if none is found - returns NULL. */
1070 /* Memory effects: list is destructively modified. If NULL is returned,
1072 static struct format_arg_list *
1073 backtrack_in_initial (struct format_arg_list *list)
1075 ASSERT (list->repeated.count == 0);
1077 while (list->initial.count > 0)
1079 unsigned int i = list->initial.count - 1;
1080 if (list->initial.element[i].presence == FCT_REQUIRED)
1082 /* Throw away this element. */
1083 list->initial.length -= list->initial.element[i].repcount;
1084 free_element (&list->initial.element[i]);
1085 list->initial.count = i;
1087 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1089 /* The list must end here. */
1090 list->initial.length--;
1091 if (list->initial.element[i].repcount > 1)
1092 list->initial.element[i].repcount--;
1095 free_element (&list->initial.element[i]);
1096 list->initial.count = i;
1107 /* Create the intersection (i.e. combined constraints) of two argument list
1108 constraints. Free both argument lists when done. Return NULL if the
1109 intersection is empty, i.e. if the two constraints give a contradiction. */
1110 /* Memory effects: list1 and list2 are freed. The result, if non-NULL, is
1111 freshly allocated. */
1112 static struct format_arg_list *
1113 make_intersected_list (struct format_arg_list *list1,
1114 struct format_arg_list *list2)
1116 struct format_arg_list *result;
1118 VERIFY_LIST (list1);
1119 VERIFY_LIST (list2);
1121 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1122 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1124 unsigned int n1 = list1->repeated.length;
1125 unsigned int n2 = list2->repeated.length;
1126 unsigned int g = gcd (n1, n2);
1127 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1128 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1130 unfold_loop (list1, m1);
1131 unfold_loop (list2, m2);
1132 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1135 if (list1->repeated.length > 0 || list2->repeated.length > 0)
1136 /* Step 2: Ensure the initial segment of the result can be computed
1137 from the initial segments of list1 and list2. If both have a
1138 repeated segment, this means to ensure
1139 list1->initial.length == list2->initial.length. */
1141 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1143 if (list1->repeated.length > 0)
1144 rotate_loop (list1, m);
1145 if (list2->repeated.length > 0)
1146 rotate_loop (list2, m);
1149 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1151 ASSERT (list1->initial.length == list2->initial.length);
1152 ASSERT (list1->repeated.length == list2->repeated.length);
1155 /* Step 3: Allocate the result. */
1156 result = XMALLOC (struct format_arg_list);
1157 result->initial.count = 0;
1158 result->initial.allocated = 0;
1159 result->initial.element = NULL;
1160 result->initial.length = 0;
1161 result->repeated.count = 0;
1162 result->repeated.allocated = 0;
1163 result->repeated.element = NULL;
1164 result->repeated.length = 0;
1166 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1168 struct format_arg *e1;
1169 struct format_arg *e2;
1173 e1 = list1->initial.element; c1 = list1->initial.count;
1174 e2 = list2->initial.element; c2 = list2->initial.count;
1175 while (c1 > 0 && c2 > 0)
1177 struct format_arg *re;
1179 /* Ensure room in result->initial. */
1180 grow_initial_alloc (result);
1181 re = &result->initial.element[result->initial.count];
1182 re->repcount = MIN (e1->repcount, e2->repcount);
1184 /* Intersect the argument types. */
1185 if (!make_intersected_element (re, e1, e2))
1187 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1188 if (re->presence == FCT_REQUIRED)
1189 /* Contradiction. Backtrack. */
1190 result = backtrack_in_initial (result);
1194 result->initial.count++;
1195 result->initial.length += re->repcount;
1197 e1->repcount -= re->repcount;
1198 if (e1->repcount == 0)
1203 e2->repcount -= re->repcount;
1204 if (e2->repcount == 0)
1211 if (list1->repeated.count == 0 && list2->repeated.count == 0)
1213 /* Intersecting two finite lists. */
1216 /* list1 longer than list2. */
1217 if (e1->presence == FCT_REQUIRED)
1218 /* Contradiction. Backtrack. */
1219 result = backtrack_in_initial (result);
1223 /* list2 longer than list1. */
1224 if (e2->presence == FCT_REQUIRED)
1225 /* Contradiction. Backtrack. */
1226 result = backtrack_in_initial (result);
1230 else if (list1->repeated.count == 0)
1232 /* Intersecting a finite and an infinite list. */
1234 if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence)
1236 /* Contradiction. Backtrack. */
1237 result = backtrack_in_initial (result);
1240 else if (list2->repeated.count == 0)
1242 /* Intersecting an infinite and a finite list. */
1244 if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence)
1246 /* Contradiction. Backtrack. */
1247 result = backtrack_in_initial (result);
1250 /* Intersecting two infinite lists. */
1251 ASSERT (c1 == 0 && c2 == 0);
1254 /* Step 5: Elementwise intersection of list1->repeated, list2->repeated. */
1256 struct format_arg *e1;
1257 struct format_arg *e2;
1261 e1 = list1->repeated.element; c1 = list1->repeated.count;
1262 e2 = list2->repeated.element; c2 = list2->repeated.count;
1263 while (c1 > 0 && c2 > 0)
1265 struct format_arg *re;
1267 /* Ensure room in result->repeated. */
1268 grow_repeated_alloc (result);
1269 re = &result->repeated.element[result->repeated.count];
1270 re->repcount = MIN (e1->repcount, e2->repcount);
1272 /* Intersect the argument types. */
1273 if (!make_intersected_element (re, e1, e2))
1275 append_repeated_to_initial (result);
1277 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1278 if (re->presence == FCT_REQUIRED)
1279 /* Contradiction. Backtrack. */
1280 result = backtrack_in_initial (result);
1285 result->repeated.count++;
1286 result->repeated.length += re->repcount;
1288 e1->repcount -= re->repcount;
1289 if (e1->repcount == 0)
1294 e2->repcount -= re->repcount;
1295 if (e2->repcount == 0)
1301 ASSERT (c1 == 0 && c2 == 0);
1309 /* Undo the loop unfolding and unrolling done above. */
1310 normalize_outermost_list (result);
1311 VERIFY_LIST (result);
1317 /* Create the intersection of an argument list and the empty list.
1318 Return NULL if the intersection is empty. */
1319 /* Memory effects: The result, if non-NULL, is freshly allocated. */
1320 static struct format_arg_list *
1321 make_intersection_with_empty_list (struct format_arg_list *list)
1323 #if 0 /* equivalent but slower */
1324 return make_intersected_list (copy_list (list), make_empty_list ());
1326 if (list->initial.count > 0
1327 ? list->initial.element[0].presence == FCT_REQUIRED
1328 : list->repeated.count > 0
1329 && list->repeated.element[0].presence == FCT_REQUIRED)
1332 return make_empty_list ();
1338 /* Create the intersection of two argument list constraints. NULL stands
1339 for an impossible situation, i.e. a contradiction. */
1340 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1341 if non-NULL, is freshly allocated. */
1342 static struct format_arg_list *
1343 intersection (struct format_arg_list *list1, struct format_arg_list *list2)
1348 return make_intersected_list (list1, list2);
1369 /* ===================== Union of two format_arg_lists ===================== */
1371 /* Create the union (i.e. alternative constraints) of two argument
1374 make_union_element (struct format_arg *re,
1375 const struct format_arg * e1,
1376 const struct format_arg * e2)
1378 /* Union of the cdr types. */
1379 if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED)
1380 re->presence = FCT_REQUIRED;
1381 else /* Either one of them is FCT_OPTIONAL. */
1382 re->presence = FCT_OPTIONAL;
1384 /* Union of the arg types. */
1385 if (e1->type == e2->type)
1387 re->type = e1->type;
1388 if (re->type == FAT_LIST)
1389 re->list = make_union_list (copy_list (e1->list),
1390 copy_list (e2->list));
1392 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
1393 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
1394 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
1396 re->type = e1->type;
1398 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
1399 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
1400 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1402 re->type = e2->type;
1404 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1406 re->type = e1->type;
1408 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1410 re->type = e2->type;
1412 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1414 re->type = e1->type;
1416 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1418 re->type = e2->type;
1420 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1422 re->type = e1->type;
1424 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1426 re->type = e2->type;
1428 else if (e1->type == FAT_LIST && is_empty_list (e1->list))
1430 if (e2->type == FAT_CHARACTER_INTEGER_NULL
1431 || e2->type == FAT_CHARACTER_NULL
1432 || e2->type == FAT_INTEGER_NULL)
1433 re->type = e2->type;
1434 else if (e2->type == FAT_CHARACTER)
1435 re->type = FAT_CHARACTER_NULL;
1436 else if (e2->type == FAT_INTEGER)
1437 re->type = FAT_INTEGER_NULL;
1439 re->type = FAT_OBJECT;
1441 else if (e2->type == FAT_LIST && is_empty_list (e2->list))
1443 if (e1->type == FAT_CHARACTER_INTEGER_NULL
1444 || e1->type == FAT_CHARACTER_NULL
1445 || e1->type == FAT_INTEGER_NULL)
1446 re->type = e1->type;
1447 else if (e1->type == FAT_CHARACTER)
1448 re->type = FAT_CHARACTER_NULL;
1449 else if (e1->type == FAT_INTEGER)
1450 re->type = FAT_INTEGER_NULL;
1452 re->type = FAT_OBJECT;
1454 else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL)
1455 && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL))
1457 re->type = FAT_CHARACTER_INTEGER_NULL;
1459 else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL)
1460 && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL))
1462 re->type = FAT_CHARACTER_INTEGER_NULL;
1466 /* Other union types are too hard to describe precisely. */
1467 re->type = FAT_OBJECT;
1471 /* Create the union (i.e. alternative constraints) of two argument list
1472 constraints. Free both argument lists when done. */
1473 /* Memory effects: list1 and list2 are freed. The result is freshly
1475 static struct format_arg_list *
1476 make_union_list (struct format_arg_list *list1, struct format_arg_list *list2)
1478 struct format_arg_list *result;
1480 VERIFY_LIST (list1);
1481 VERIFY_LIST (list2);
1483 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1485 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1487 unsigned int n1 = list1->repeated.length;
1488 unsigned int n2 = list2->repeated.length;
1489 unsigned int g = gcd (n1, n2);
1490 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1491 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1493 unfold_loop (list1, m1);
1494 unfold_loop (list2, m2);
1495 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1498 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1500 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1502 rotate_loop (list1, m);
1503 rotate_loop (list2, m);
1506 ASSERT (list1->initial.length == list2->initial.length);
1507 ASSERT (list1->repeated.length == list2->repeated.length);
1509 else if (list1->repeated.length > 0)
1511 /* Ensure the initial segment of the result can be computed from the
1512 initial segment of list1. */
1513 if (list2->initial.length >= list1->initial.length)
1515 rotate_loop (list1, list2->initial.length);
1516 if (list1->repeated.element[0].presence == FCT_REQUIRED)
1517 rotate_loop (list1, list1->initial.length + 1);
1520 else if (list2->repeated.length > 0)
1522 /* Ensure the initial segment of the result can be computed from the
1523 initial segment of list2. */
1524 if (list1->initial.length >= list2->initial.length)
1526 rotate_loop (list2, list1->initial.length);
1527 if (list2->repeated.element[0].presence == FCT_REQUIRED)
1528 rotate_loop (list2, list2->initial.length + 1);
1532 /* Step 3: Allocate the result. */
1533 result = XMALLOC (struct format_arg_list);
1534 result->initial.count = 0;
1535 result->initial.allocated = 0;
1536 result->initial.element = NULL;
1537 result->initial.length = 0;
1538 result->repeated.count = 0;
1539 result->repeated.allocated = 0;
1540 result->repeated.element = NULL;
1541 result->repeated.length = 0;
1543 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1545 struct format_arg *e1;
1546 struct format_arg *e2;
1550 e1 = list1->initial.element; c1 = list1->initial.count;
1551 e2 = list2->initial.element; c2 = list2->initial.count;
1552 while (c1 > 0 && c2 > 0)
1554 struct format_arg *re;
1556 /* Ensure room in result->initial. */
1557 grow_initial_alloc (result);
1558 re = &result->initial.element[result->initial.count];
1559 re->repcount = MIN (e1->repcount, e2->repcount);
1561 /* Union of the argument types. */
1562 make_union_element (re, e1, e2);
1564 result->initial.count++;
1565 result->initial.length += re->repcount;
1567 e1->repcount -= re->repcount;
1568 if (e1->repcount == 0)
1573 e2->repcount -= re->repcount;
1574 if (e2->repcount == 0)
1583 /* list2 already terminated, but still more elements in list1->initial.
1584 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1585 ASSERT (list2->repeated.count == 0);
1587 if (e1->presence == FCT_REQUIRED)
1589 struct format_arg *re;
1591 /* Ensure room in result->initial. */
1592 grow_initial_alloc (result);
1593 re = &result->initial.element[result->initial.count];
1594 copy_element (re, e1);
1595 re->presence = FCT_OPTIONAL;
1597 result->initial.count++;
1598 result->initial.length += 1;
1600 if (e1->repcount == 0)
1607 /* Ensure room in result->initial. */
1608 ensure_initial_alloc (result, result->initial.count + c1);
1611 struct format_arg *re;
1613 re = &result->initial.element[result->initial.count];
1614 copy_element (re, e1);
1615 result->initial.count++;
1616 result->initial.length += re->repcount;
1623 /* list1 already terminated, but still more elements in list2->initial.
1624 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1625 ASSERT (list1->repeated.count == 0);
1627 if (e2->presence == FCT_REQUIRED)
1629 struct format_arg *re;
1631 /* Ensure room in result->initial. */
1632 grow_initial_alloc (result);
1633 re = &result->initial.element[result->initial.count];
1634 copy_element (re, e2);
1635 re->presence = FCT_OPTIONAL;
1637 result->initial.count++;
1638 result->initial.length += 1;
1640 if (e2->repcount == 0)
1647 /* Ensure room in result->initial. */
1648 ensure_initial_alloc (result, result->initial.count + c2);
1651 struct format_arg *re;
1653 re = &result->initial.element[result->initial.count];
1654 copy_element (re, e2);
1655 result->initial.count++;
1656 result->initial.length += re->repcount;
1661 ASSERT (c1 == 0 && c2 == 0);
1664 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1665 /* Step 5: Elementwise union of list1->repeated, list2->repeated. */
1667 struct format_arg *e1;
1668 struct format_arg *e2;
1672 e1 = list1->repeated.element; c1 = list1->repeated.count;
1673 e2 = list2->repeated.element; c2 = list2->repeated.count;
1674 while (c1 > 0 && c2 > 0)
1676 struct format_arg *re;
1678 /* Ensure room in result->repeated. */
1679 grow_repeated_alloc (result);
1680 re = &result->repeated.element[result->repeated.count];
1681 re->repcount = MIN (e1->repcount, e2->repcount);
1683 /* Union of the argument types. */
1684 make_union_element (re, e1, e2);
1686 result->repeated.count++;
1687 result->repeated.length += re->repcount;
1689 e1->repcount -= re->repcount;
1690 if (e1->repcount == 0)
1695 e2->repcount -= re->repcount;
1696 if (e2->repcount == 0)
1702 ASSERT (c1 == 0 && c2 == 0);
1704 else if (list1->repeated.length > 0)
1706 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1707 initial segment. Just copy the repeated segment of list1. */
1710 result->repeated.count = list1->repeated.count;
1711 result->repeated.allocated = result->repeated.count;
1712 result->repeated.element =
1713 XNMALLOC (result->repeated.allocated, struct format_arg);
1714 for (i = 0; i < list1->repeated.count; i++)
1715 copy_element (&result->repeated.element[i],
1716 &list1->repeated.element[i]);
1717 result->repeated.length = list1->repeated.length;
1719 else if (list2->repeated.length > 0)
1721 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1722 initial segment. Just copy the repeated segment of list2. */
1725 result->repeated.count = list2->repeated.count;
1726 result->repeated.allocated = result->repeated.count;
1727 result->repeated.element =
1728 XNMALLOC (result->repeated.allocated, struct format_arg);
1729 for (i = 0; i < list2->repeated.count; i++)
1730 copy_element (&result->repeated.element[i],
1731 &list2->repeated.element[i]);
1732 result->repeated.length = list2->repeated.length;
1737 /* Undo the loop unfolding and unrolling done above. */
1738 normalize_outermost_list (result);
1739 VERIFY_LIST (result);
1744 /* Create the union of an argument list and the empty list. */
1745 /* Memory effects: list is freed. The result is freshly allocated. */
1746 static struct format_arg_list *
1747 make_union_with_empty_list (struct format_arg_list *list)
1749 #if 0 /* equivalent but slower */
1750 return make_union_list (list, make_empty_list ());
1754 if (list->initial.count > 0
1755 ? list->initial.element[0].presence == FCT_REQUIRED
1756 : list->repeated.count > 0
1757 && list->repeated.element[0].presence == FCT_REQUIRED)
1759 initial_splitelement (list, 1);
1760 ASSERT (list->initial.count > 0);
1761 ASSERT (list->initial.element[0].repcount == 1);
1762 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1763 list->initial.element[0].presence = FCT_OPTIONAL;
1765 /* We might need to merge list->initial.element[0] and
1766 list->initial.element[1]. */
1767 normalize_outermost_list (list);
1777 /* Create the union of two argument list constraints. NULL stands for an
1778 impossible situation, i.e. a contradiction. */
1779 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1780 if non-NULL, is freshly allocated. */
1781 static struct format_arg_list *
1782 union (struct format_arg_list *list1, struct format_arg_list *list2)
1787 return make_union_list (list1, list2);
1801 /* =========== Adding specific constraints to a format_arg_list =========== */
1804 /* Test whether arguments 0..n are required arguments in a list. */
1806 is_required (const struct format_arg_list *list, unsigned int n)
1811 /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */
1814 /* Walk the list->initial segment. */
1816 s < list->initial.count && t >= list->initial.element[s].repcount;
1817 t -= list->initial.element[s].repcount, s++)
1818 if (list->initial.element[s].presence != FCT_REQUIRED)
1824 if (s < list->initial.count)
1826 if (list->initial.element[s].presence != FCT_REQUIRED)
1832 /* Walk the list->repeated segment. */
1833 if (list->repeated.count == 0)
1837 s < list->repeated.count && t >= list->repeated.element[s].repcount;
1838 t -= list->repeated.element[s].repcount, s++)
1839 if (list->repeated.element[s].presence != FCT_REQUIRED)
1845 if (s < list->repeated.count)
1847 if (list->repeated.element[s].presence != FCT_REQUIRED)
1853 /* The list->repeated segment consists only of FCT_REQUIRED. So,
1854 regardless how many more passes through list->repeated would be
1855 needed until t becomes 0, the result is true. */
1860 /* Add a constraint to an argument list, namely that the arguments 0...n are
1861 present. NULL stands for an impossible situation, i.e. a contradiction. */
1862 /* Memory effects: list is freed. The result is freshly allocated. */
1863 static struct format_arg_list *
1864 add_required_constraint (struct format_arg_list *list, unsigned int n)
1866 unsigned int i, rest;
1873 if (list->repeated.count == 0 && list->initial.length <= n)
1875 /* list is already constrained to have at most length n.
1881 initial_splitelement (list, n + 1);
1883 for (i = 0, rest = n + 1; rest > 0; )
1885 list->initial.element[i].presence = FCT_REQUIRED;
1886 rest -= list->initial.element[i].repcount;
1896 /* Add a constraint to an argument list, namely that the argument n is
1897 never present. NULL stands for an impossible situation, i.e. a
1899 /* Memory effects: list is freed. The result is freshly allocated. */
1900 static struct format_arg_list *
1901 add_end_constraint (struct format_arg_list *list, unsigned int n)
1904 enum format_cdr_type n_presence;
1911 if (list->repeated.count == 0 && list->initial.length <= n)
1912 /* list is already constrained to have at most length n. */
1915 s = initial_splitelement (list, n);
1917 (s < list->initial.count
1918 ? /* n < list->initial.length */ list->initial.element[s].presence
1919 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1921 for (i = s; i < list->initial.count; i++)
1923 list->initial.length -= list->initial.element[i].repcount;
1924 free_element (&list->initial.element[i]);
1926 list->initial.count = s;
1928 for (i = 0; i < list->repeated.count; i++)
1929 free_element (&list->repeated.element[i]);
1930 if (list->repeated.element != NULL)
1931 free (list->repeated.element);
1932 list->repeated.element = NULL;
1933 list->repeated.allocated = 0;
1934 list->repeated.count = 0;
1935 list->repeated.length = 0;
1937 if (n_presence == FCT_REQUIRED)
1938 return backtrack_in_initial (list);
1944 /* Add a constraint to an argument list, namely that the argument n is
1945 of a given type. NULL stands for an impossible situation, i.e. a
1946 contradiction. Assumes a preceding add_required_constraint (list, n). */
1947 /* Memory effects: list is freed. The result is freshly allocated. */
1948 static struct format_arg_list *
1949 add_type_constraint (struct format_arg_list *list, unsigned int n,
1950 enum format_arg_type type)
1953 struct format_arg newconstraint;
1954 struct format_arg tmpelement;
1959 /* Through the previous add_required_constraint, we can assume
1960 list->initial.length >= n+1. */
1962 s = initial_unshare (list, n);
1964 newconstraint.presence = FCT_OPTIONAL;
1965 newconstraint.type = type;
1966 if (!make_intersected_element (&tmpelement,
1967 &list->initial.element[s], &newconstraint))
1968 return add_end_constraint (list, n);
1969 free_element (&list->initial.element[s]);
1970 list->initial.element[s].type = tmpelement.type;
1971 list->initial.element[s].list = tmpelement.list;
1979 /* Add a constraint to an argument list, namely that the argument n is
1980 of a given list type. NULL stands for an impossible situation, i.e. a
1981 contradiction. Assumes a preceding add_required_constraint (list, n). */
1982 /* Memory effects: list is freed. The result is freshly allocated. */
1983 static struct format_arg_list *
1984 add_listtype_constraint (struct format_arg_list *list, unsigned int n,
1985 enum format_arg_type type,
1986 struct format_arg_list *sublist)
1989 struct format_arg newconstraint;
1990 struct format_arg tmpelement;
1995 /* Through the previous add_required_constraint, we can assume
1996 list->initial.length >= n+1. */
1998 s = initial_unshare (list, n);
2000 newconstraint.presence = FCT_OPTIONAL;
2001 newconstraint.type = type;
2002 newconstraint.list = sublist;
2003 if (!make_intersected_element (&tmpelement,
2004 &list->initial.element[s], &newconstraint))
2005 return add_end_constraint (list, n);
2006 free_element (&list->initial.element[s]);
2007 list->initial.element[s].type = tmpelement.type;
2008 list->initial.element[s].list = tmpelement.list;
2016 /* ============= Subroutines used by the format string parser ============= */
2019 add_req_type_constraint (struct format_arg_list **listp,
2020 unsigned int position, enum format_arg_type type)
2022 *listp = add_required_constraint (*listp, position);
2023 *listp = add_type_constraint (*listp, position, type);
2028 add_req_listtype_constraint (struct format_arg_list **listp,
2029 unsigned int position, enum format_arg_type type,
2030 struct format_arg_list *sublist)
2032 *listp = add_required_constraint (*listp, position);
2033 *listp = add_listtype_constraint (*listp, position, type, sublist);
2037 /* Create an endless repeated list whose elements are lists constrained
2039 /* Memory effects: sublist is freed. The result is freshly allocated. */
2040 static struct format_arg_list *
2041 make_repeated_list_of_lists (struct format_arg_list *sublist)
2043 if (sublist == NULL)
2044 /* The list cannot have a single element. */
2045 return make_empty_list ();
2048 struct format_arg_list *listlist;
2050 listlist = XMALLOC (struct format_arg_list);
2052 listlist->initial.count = 0;
2053 listlist->initial.allocated = 0;
2054 listlist->initial.element = NULL;
2055 listlist->initial.length = 0;
2056 listlist->repeated.count = 1;
2057 listlist->repeated.allocated = 1;
2058 listlist->repeated.element = XNMALLOC (1, struct format_arg);
2059 listlist->repeated.element[0].repcount = 1;
2060 listlist->repeated.element[0].presence = FCT_OPTIONAL;
2061 listlist->repeated.element[0].type = FAT_LIST;
2062 listlist->repeated.element[0].list = sublist;
2063 listlist->repeated.length = 1;
2065 VERIFY_LIST (listlist);
2072 /* Create an endless repeated list which represents the union of a finite
2073 number of copies of L, each time shifted by period:
2077 L and (*^period L) and (*^{2 period} L)
2078 L and (*^period L) and (*^{2 period} L) and (*^{3 period} L)
2081 /* Memory effects: sublist is freed. The result is freshly allocated. */
2082 static struct format_arg_list *
2083 make_repeated_list (struct format_arg_list *sublist, unsigned int period)
2086 struct segment *srcseg;
2087 struct format_arg_list *list;
2088 unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount;
2091 VERIFY_LIST (sublist);
2093 ASSERT (period > 0);
2095 if (sublist->repeated.count == 0)
2097 /* L is a finite list. */
2099 if (sublist->initial.length < period)
2100 /* L and (*^period L) is a contradition, so we need to consider
2101 only 1 and 0 iterations. */
2102 return make_union_with_empty_list (sublist);
2104 srcseg = &sublist->initial;
2109 /* L is an infinite list. */
2110 /* p := lcm (period, period of L) */
2111 unsigned int Lp = sublist->repeated.length;
2112 unsigned int m = period / gcd (period, Lp); /* = lcm(period,Lp) / Lp */
2114 unfold_loop (sublist, m);
2117 /* Concatenate the initial and the repeated segments into a single
2119 tmp.count = sublist->initial.count + sublist->repeated.count;
2120 tmp.allocated = tmp.count;
2121 tmp.element = XNMALLOC (tmp.allocated, struct format_arg);
2122 for (i = 0; i < sublist->initial.count; i++)
2123 tmp.element[i] = sublist->initial.element[i];
2124 for (j = 0; j < sublist->repeated.count; i++, j++)
2125 tmp.element[i] = sublist->initial.element[j];
2126 tmp.length = sublist->initial.length + sublist->repeated.length;
2133 /* Example: n = 7, p = 2
2134 Let L = (A B C D E F G).
2137 L & L<<p = A B C&A D&B E&C F&D G&E
2138 L & L<<p & L<<2p = A B C&A D&B E&C&A F&D&B G&E&C
2139 ... = A B C&A D&B E&C&A F&D&B G&E&C&A
2141 Thus the result has an initial segment of length n - p and a period
2142 of p, and can be computed by floor(n/p) intersection operations.
2143 Or by a single incremental intersection operation, going from left
2146 list = XMALLOC (struct format_arg_list);
2147 list->initial.count = 0;
2148 list->initial.allocated = 0;
2149 list->initial.element = NULL;
2150 list->initial.length = 0;
2151 list->repeated.count = 0;
2152 list->repeated.allocated = 0;
2153 list->repeated.element = NULL;
2154 list->repeated.length = 0;
2157 for (i = 0; i < p; i++)
2158 list->initial.element[i] = srcseg->element[i];
2159 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2160 for (i = p, j = 0; i < n; i++, j++)
2161 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2166 i = 0, ti = 0, si = 0;
2169 unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
2171 /* Ensure room in list->initial. */
2172 grow_initial_alloc (list);
2173 copy_element (&list->initial.element[list->initial.count],
2174 &srcseg->element[si]);
2175 list->initial.element[list->initial.count].repcount = k;
2176 list->initial.count++;
2177 list->initial.length += k;
2181 if (ti == srcseg->element[si].repcount)
2188 ASSERT (list->initial.count > 0);
2189 if (list->initial.element[0].presence == FCT_REQUIRED)
2191 initial_splitelement (list, 1);
2192 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2193 ASSERT (list->initial.element[0].repcount == 1);
2194 list->initial.element[0].presence = FCT_OPTIONAL;
2197 j = 0, tj = 0, sj = 0;
2201 MIN (srcseg->element[si].repcount - ti,
2202 list->initial.element[sj].repcount - tj);
2204 /* Ensure room in list->initial. */
2205 grow_initial_alloc (list);
2206 if (!make_intersected_element (&list->initial.element[list->initial.count],
2207 &srcseg->element[si],
2208 &list->initial.element[sj]))
2210 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2212 /* Contradiction. Backtrack. */
2213 list = backtrack_in_initial (list);
2214 ASSERT (list != NULL); /* at least the empty list is valid */
2219 /* The list ends here. */
2224 list->initial.element[list->initial.count].repcount = k;
2225 list->initial.count++;
2226 list->initial.length += k;
2230 if (ti == srcseg->element[si].repcount)
2238 if (tj == list->initial.element[sj].repcount)
2245 ASSERT (list->initial.length == n);
2247 /* Add optional exit points at 0, period, 2*period etc.
2248 FIXME: Not sure this is correct in all cases. */
2249 for (i = 0; i < list->initial.length; i += period)
2251 si = initial_unshare (list, i);
2252 list->initial.element[si].presence = FCT_OPTIONAL;
2257 /* Now split off the repeated part. */
2258 splitindex = initial_splitelement (list, n - p);
2259 newcount = list->initial.count - splitindex;
2260 if (newcount > list->repeated.allocated)
2262 list->repeated.allocated = newcount;
2263 list->repeated.element = XNMALLOC (newcount, struct format_arg);
2265 for (i = splitindex, j = 0; i < n; i++, j++)
2266 list->repeated.element[j] = list->initial.element[i];
2267 list->repeated.count = newcount;
2268 list->repeated.length = p;
2269 list->initial.count = splitindex;
2270 list->initial.length = n - p;
2279 /* ================= Handling of format string directives ================= */
2281 /* Possible signatures of format directives. */
2282 static const enum format_arg_type I [1] = { FAT_INTEGER_NULL };
2283 static const enum format_arg_type II [2] = {
2284 FAT_INTEGER_NULL, FAT_INTEGER_NULL
2286 static const enum format_arg_type ICCI [4] = {
2287 FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL
2289 static const enum format_arg_type IIIC [4] = {
2290 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2292 static const enum format_arg_type IICCI [5] = {
2293 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL,
2296 static const enum format_arg_type IIICC [5] = {
2297 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL,
2300 static const enum format_arg_type IIIICCC [7] = {
2301 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL,
2302 FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL
2304 static const enum format_arg_type THREE [3] = {
2305 FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL,
2306 FAT_CHARACTER_INTEGER_NULL
2310 /* Check the parameters. For V params, add the constraint to the argument
2311 list. Return false and fill in *invalid_reason if the format string is
2314 check_params (struct format_arg_list **listp,
2315 unsigned int paramcount, struct param *params,
2316 unsigned int t_count, const enum format_arg_type *t_types,
2317 unsigned int directives, char **invalid_reason)
2319 unsigned int orig_paramcount = paramcount;
2320 unsigned int orig_t_count = t_count;
2322 for (; paramcount > 0 && t_count > 0;
2323 params++, paramcount--, t_types++, t_count--)
2327 case FAT_CHARACTER_INTEGER_NULL:
2329 case FAT_CHARACTER_NULL:
2330 switch (params->type)
2332 case PT_NIL: case PT_CHARACTER: case PT_V:
2334 case PT_INTEGER: case PT_ARGCOUNT:
2335 /* wrong param type */
2337 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");
2341 case FAT_INTEGER_NULL:
2342 switch (params->type)
2344 case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V:
2347 /* wrong param type */
2349 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");
2356 if (params->type == PT_V)
2358 int position = params->value;
2360 add_req_type_constraint (listp, position, *t_types);
2364 for (; paramcount > 0; params++, paramcount--)
2365 switch (params->type)
2369 case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT:
2370 /* too many params for directive */
2372 xasprintf (ngettext ("In the directive number %u, too many parameters are given; expected at most %u parameter.",
2373 "In the directive number %u, too many parameters are given; expected at most %u parameters.",
2375 directives, orig_t_count);
2378 /* Force argument to be NIL. */
2380 int position = params->value;
2383 struct format_arg_list *empty_list = make_empty_list ();
2384 add_req_listtype_constraint (listp, position,
2385 FAT_LIST, empty_list);
2386 free_list (empty_list);
2396 /* Handle the parameters, without a priori type information.
2397 For V params, add the constraint to the argument list.
2398 Return false and fill in *invalid_reason if the format string is
2401 nocheck_params (struct format_arg_list **listp,
2402 unsigned int paramcount, struct param *params,
2403 unsigned int directives, char **invalid_reason)
2406 (void) invalid_reason;
2408 for (; paramcount > 0; params++, paramcount--)
2409 if (params->type == PT_V)
2411 int position = params->value;
2412 add_req_type_constraint (listp, position, FAT_CHARACTER_INTEGER_NULL);
2419 /* ======================= The format string parser ======================= */
2421 /* Parse a piece of format string, until the matching terminating format
2422 directive is encountered.
2423 format is the remainder of the format string.
2424 position is the position in this argument list, if known, or -1 if unknown.
2425 list represents the argument list constraints at the current parse point.
2426 NULL stands for a contradiction.
2427 escape represents the union of the argument list constraints at all the
2428 currently pending FORMAT-UP-AND-OUT points. NULL stands for a contradiction
2430 All four are updated upon valid return.
2431 *separatorp is set to true if the parse terminated due to a ~; separator,
2432 more precisely to 2 if with colon, or to 1 if without colon.
2433 spec is the global struct spec.
2434 terminator is the directive that terminates this parse.
2435 separator specifies if ~; separators are allowed.
2436 fdi is an array to be filled with format directive indicators, or NULL.
2437 If the format string is invalid, false is returned and *invalid_reason is
2438 set to an error message explaining why. */
2440 parse_upto (const char **formatp,
2441 int *positionp, struct format_arg_list **listp,
2442 struct format_arg_list **escapep, int *separatorp,
2443 struct spec *spec, char terminator, bool separator,
2444 char *fdi, char **invalid_reason)
2446 const char *format = *formatp;
2447 const char *const format_start = format;
2448 int position = *positionp;
2449 struct format_arg_list *list = *listp;
2450 struct format_arg_list *escape = *escapep;
2452 for (; *format != '\0'; )
2453 if (*format++ == '~')
2455 bool colon_p = false;
2456 bool atsign_p = false;
2457 unsigned int paramcount = 0;
2458 struct param *params = NULL;
2460 FDI_SET (format - 1, FMTDIR_START);
2462 /* Count number of directives. */
2465 /* Parse parameters. */
2468 enum param_type type = PT_NIL;
2471 if (c_isdigit (*format))
2476 value = 10 * value + (*format - '0');
2479 while (c_isdigit (*format));
2481 else if (*format == '+' || *format == '-')
2483 bool negative = (*format == '-');
2486 if (!c_isdigit (*format))
2488 if (*format == '\0')
2490 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2491 FDI_SET (format - 1, FMTDIR_ERROR);
2496 xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]);
2497 FDI_SET (format, FMTDIR_ERROR);
2503 value = 10 * value + (*format - '0');
2506 while (c_isdigit (*format));
2510 else if (*format == '\'')
2512 type = PT_CHARACTER;
2514 if (*format == '\0')
2516 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2517 FDI_SET (format - 1, FMTDIR_ERROR);
2522 else if (*format == 'V' || *format == 'v')
2527 /* Consumes an argument. */
2531 else if (*format == '#')
2539 xrealloc (params, (paramcount + 1) * sizeof (struct param));
2540 params[paramcount].type = type;
2541 params[paramcount].value = value;
2550 /* Parse modifiers. */
2558 else if (*format == '@')
2567 /* Parse directive. */
2570 case 'A': case 'a': /* 22.3.4.1 FORMAT-ASCII */
2571 case 'S': case 's': /* 22.3.4.2 FORMAT-S-EXPRESSION */
2572 if (!check_params (&list, paramcount, params, 4, IIIC,
2573 spec->directives, invalid_reason))
2575 FDI_SET (format - 1, FMTDIR_ERROR);
2579 add_req_type_constraint (&list, position++, FAT_OBJECT);
2582 case 'W': case 'w': /* 22.3.4.3 FORMAT-WRITE */
2583 if (!check_params (&list, paramcount, params, 0, NULL,
2584 spec->directives, invalid_reason))
2586 FDI_SET (format - 1, FMTDIR_ERROR);
2590 add_req_type_constraint (&list, position++, FAT_OBJECT);
2593 case 'D': case 'd': /* 22.3.2.2 FORMAT-DECIMAL */
2594 case 'B': case 'b': /* 22.3.2.3 FORMAT-BINARY */
2595 case 'O': case 'o': /* 22.3.2.4 FORMAT-OCTAL */
2596 case 'X': case 'x': /* 22.3.2.5 FORMAT-HEXADECIMAL */
2597 if (!check_params (&list, paramcount, params, 4, ICCI,
2598 spec->directives, invalid_reason))
2600 FDI_SET (format - 1, FMTDIR_ERROR);
2604 add_req_type_constraint (&list, position++, FAT_INTEGER);
2607 case 'R': case 'r': /* 22.3.2.1 FORMAT-RADIX */
2608 if (!check_params (&list, paramcount, params, 5, IICCI,
2609 spec->directives, invalid_reason))
2611 FDI_SET (format - 1, FMTDIR_ERROR);
2615 add_req_type_constraint (&list, position++, FAT_INTEGER);
2618 case 'P': case 'p': /* 22.3.8.3 FORMAT-PLURAL */
2619 if (!check_params (&list, paramcount, params, 0, NULL,
2620 spec->directives, invalid_reason))
2622 FDI_SET (format - 1, FMTDIR_ERROR);
2627 /* Go back by 1 argument. */
2632 add_req_type_constraint (&list, position++, FAT_OBJECT);
2635 case 'C': case 'c': /* 22.3.1.1 FORMAT-CHARACTER */
2636 if (!check_params (&list, paramcount, params, 0, NULL,
2637 spec->directives, invalid_reason))
2639 FDI_SET (format - 1, FMTDIR_ERROR);
2643 add_req_type_constraint (&list, position++, FAT_CHARACTER);
2646 case 'F': case 'f': /* 22.3.3.1 FORMAT-FIXED-FLOAT */
2647 if (!check_params (&list, paramcount, params, 5, IIICC,
2648 spec->directives, invalid_reason))
2650 FDI_SET (format - 1, FMTDIR_ERROR);
2654 add_req_type_constraint (&list, position++, FAT_REAL);
2657 case 'E': case 'e': /* 22.3.3.2 FORMAT-EXPONENTIAL-FLOAT */
2658 case 'G': case 'g': /* 22.3.3.3 FORMAT-GENERAL-FLOAT */
2659 if (!check_params (&list, paramcount, params, 7, IIIICCC,
2660 spec->directives, invalid_reason))
2662 FDI_SET (format - 1, FMTDIR_ERROR);
2666 add_req_type_constraint (&list, position++, FAT_REAL);
2669 case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */
2670 if (!check_params (&list, paramcount, params, 4, IIIC,
2671 spec->directives, invalid_reason))
2673 FDI_SET (format - 1, FMTDIR_ERROR);
2677 add_req_type_constraint (&list, position++, FAT_REAL);
2680 case '%': /* 22.3.1.2 FORMAT-TERPRI */
2681 case '&': /* 22.3.1.3 FORMAT-FRESH-LINE */
2682 case '|': /* 22.3.1.4 FORMAT-PAGE */
2683 case '~': /* 22.3.1.5 FORMAT-TILDE */
2684 case 'I': case 'i': /* 22.3.5.3 */
2685 if (!check_params (&list, paramcount, params, 1, I,
2686 spec->directives, invalid_reason))
2688 FDI_SET (format - 1, FMTDIR_ERROR);
2693 case '\n': /* 22.3.9.3 #\Newline */
2694 case '_': /* 22.3.5.1 */
2695 if (!check_params (&list, paramcount, params, 0, NULL,
2696 spec->directives, invalid_reason))
2698 FDI_SET (format - 1, FMTDIR_ERROR);
2703 case 'T': case 't': /* 22.3.6.1 FORMAT-TABULATE */
2704 if (!check_params (&list, paramcount, params, 2, II,
2705 spec->directives, invalid_reason))
2707 FDI_SET (format - 1, FMTDIR_ERROR);
2712 case '*': /* 22.3.7.1 FORMAT-GOTO */
2713 if (!check_params (&list, paramcount, params, 1, I,
2714 spec->directives, invalid_reason))
2716 FDI_SET (format - 1, FMTDIR_ERROR);
2720 int n; /* value of first parameter */
2722 || (paramcount >= 1 && params[0].type == PT_NIL))
2723 n = (atsign_p ? 0 : 1);
2724 else if (paramcount >= 1 && params[0].type == PT_INTEGER)
2725 n = params[0].value;
2728 /* Unknown argument, leads to an unknown position. */
2734 /* invalid argument */
2736 xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
2737 FDI_SET (format - 1, FMTDIR_ERROR);
2742 /* Absolute goto. */
2747 /* Backward goto. */
2770 case '?': /* 22.3.7.6 FORMAT-INDIRECTION */
2771 if (!check_params (&list, paramcount, params, 0, NULL,
2772 spec->directives, invalid_reason))
2774 FDI_SET (format - 1, FMTDIR_ERROR);
2778 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
2784 struct format_arg_list *sublist = make_unconstrained_list ();
2785 add_req_listtype_constraint (&list, position++,
2787 free_list (sublist);
2791 case '/': /* 22.3.5.4 FORMAT-CALL-USER-FUNCTION */
2792 if (!check_params (&list, paramcount, params, 0, NULL,
2793 spec->directives, invalid_reason))
2795 FDI_SET (format - 1, FMTDIR_ERROR);
2799 add_req_type_constraint (&list, position++, FAT_OBJECT);
2800 while (*format != '\0' && *format != '/')
2802 if (*format == '\0')
2805 xstrdup (_("The string ends in the middle of a ~/.../ directive."));
2806 FDI_SET (format - 1, FMTDIR_ERROR);
2812 case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */
2813 if (!check_params (&list, paramcount, params, 0, NULL,
2814 spec->directives, invalid_reason))
2816 FDI_SET (format - 1, FMTDIR_ERROR);
2820 *positionp = position;
2824 if (!parse_upto (formatp, positionp, listp, escapep,
2825 NULL, spec, ')', false,
2826 NULL, invalid_reason))
2828 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2834 position = *positionp;
2839 case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */
2840 if (terminator != ')')
2843 xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
2844 FDI_SET (format - 1, FMTDIR_ERROR);
2847 if (!check_params (&list, paramcount, params, 0, NULL,
2848 spec->directives, invalid_reason))
2850 FDI_SET (format - 1, FMTDIR_ERROR);
2854 *positionp = position;
2859 case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */
2860 if (atsign_p && colon_p)
2863 xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
2864 FDI_SET (format - 1, FMTDIR_ERROR);
2869 struct format_arg_list *nil_list;
2870 struct format_arg_list *union_list;
2872 if (!check_params (&list, paramcount, params, 0, NULL,
2873 spec->directives, invalid_reason))
2875 FDI_SET (format - 1, FMTDIR_ERROR);
2882 /* First alternative: argument is NIL. */
2883 nil_list = (list != NULL ? copy_list (list) : NULL);
2886 struct format_arg_list *empty_list = make_empty_list ();
2887 add_req_listtype_constraint (&nil_list, position,
2888 FAT_LIST, empty_list);
2889 free_list (empty_list);
2892 /* Second alternative: use sub-format. */
2894 int sub_position = position;
2895 struct format_arg_list *sub_list =
2896 (list != NULL ? copy_list (list) : NULL);
2897 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2898 NULL, spec, ']', false,
2899 NULL, invalid_reason))
2901 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2905 if (sub_list != NULL)
2909 if (sub_position == position + 1)
2910 /* new position is branch independent */
2911 position = position + 1;
2913 /* new position is branch dependent */
2920 position = position + 1;
2922 union_list = union (nil_list, sub_list);
2935 struct format_arg_list *union_list;
2937 if (!check_params (&list, paramcount, params, 0, NULL,
2938 spec->directives, invalid_reason))
2940 FDI_SET (format - 1, FMTDIR_ERROR);
2945 add_req_type_constraint (&list, position++, FAT_OBJECT);
2949 union_position = -2;
2952 /* First alternative. */
2954 int sub_position = position;
2955 struct format_arg_list *sub_list =
2956 (list != NULL ? copy_list (list) : NULL);
2957 int sub_separator = 0;
2960 struct format_arg_list *empty_list = make_empty_list ();
2961 add_req_listtype_constraint (&sub_list, position - 1,
2962 FAT_LIST, empty_list);
2963 free_list (empty_list);
2965 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2966 &sub_separator, spec, ']', true,
2967 NULL, invalid_reason))
2969 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2976 xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives);
2977 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2981 if (sub_list != NULL)
2982 union_position = sub_position;
2983 union_list = union (union_list, sub_list);
2986 /* Second alternative. */
2988 int sub_position = position;
2989 struct format_arg_list *sub_list =
2990 (list != NULL ? copy_list (list) : NULL);
2991 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2992 NULL, spec, ']', false,
2993 NULL, invalid_reason))
2995 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2999 if (sub_list != NULL)
3001 if (union_position == -2)
3002 union_position = sub_position;
3003 else if (sub_position < 0
3004 || sub_position != union_position)
3005 union_position = -1;
3007 union_list = union (union_list, sub_list);
3013 if (union_position != -2)
3014 position = union_position;
3023 struct format_arg_list *union_list;
3024 bool last_alternative;
3026 if (!check_params (&list, paramcount, params, 1, I,
3027 spec->directives, invalid_reason))
3029 FDI_SET (format - 1, FMTDIR_ERROR);
3033 /* If there was no first parameter, an argument is consumed. */
3035 if (!(paramcount >= 1 && params[0].type != PT_NIL))
3038 arg_position = position;
3039 add_req_type_constraint (&list, position++, FAT_OBJECT);
3045 union_position = -2;
3047 last_alternative = false;
3050 /* Next alternative. */
3051 int sub_position = position;
3052 struct format_arg_list *sub_list =
3053 (list != NULL ? copy_list (list) : NULL);
3054 int sub_separator = 0;
3055 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
3056 &sub_separator, spec, ']', !last_alternative,
3057 NULL, invalid_reason))
3059 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3063 /* If this alternative is chosen, the argument arg_position
3064 is an integer, namely the index of this alternative. */
3065 if (!last_alternative && arg_position >= 0)
3066 add_req_type_constraint (&sub_list, arg_position,
3068 if (sub_list != NULL)
3070 if (union_position == -2)
3071 union_position = sub_position;
3072 else if (sub_position < 0
3073 || sub_position != union_position)
3074 union_position = -1;
3076 union_list = union (union_list, sub_list);
3077 if (sub_separator == 2)
3078 last_alternative = true;
3082 if (!last_alternative)
3084 /* An implicit default alternative. */
3085 if (union_position == -2)
3086 union_position = position;
3087 else if (position < 0 || position != union_position)
3088 union_position = -1;
3090 union_list = union (union_list, copy_list (list));
3096 if (union_position != -2)
3097 position = union_position;
3104 case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */
3105 if (terminator != ']')
3108 xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
3109 FDI_SET (format - 1, FMTDIR_ERROR);
3112 if (!check_params (&list, paramcount, params, 0, NULL,
3113 spec->directives, invalid_reason))
3115 FDI_SET (format - 1, FMTDIR_ERROR);
3119 *positionp = position;
3124 case '{': /* 22.3.7.4 FORMAT-ITERATION */
3125 if (!check_params (&list, paramcount, params, 1, I,
3126 spec->directives, invalid_reason))
3128 FDI_SET (format - 1, FMTDIR_ERROR);
3133 int sub_position = 0;
3134 struct format_arg_list *sub_list = make_unconstrained_list ();
3135 struct format_arg_list *sub_escape = NULL;
3136 struct spec sub_spec;
3137 sub_spec.directives = 0;
3138 sub_spec.list = sub_list;
3139 if (!parse_upto (formatp, &sub_position, &sub_list, &sub_escape,
3140 NULL, &sub_spec, '}', false,
3141 NULL, invalid_reason))
3143 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3147 spec->directives += sub_spec.directives;
3149 /* If the sub-formatstring is empty, except for the terminating
3150 ~} directive, a formatstring argument is consumed. */
3151 if (*format == '~' && sub_spec.directives == 1)
3153 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
3157 /* Each iteration uses a new sublist. */
3158 struct format_arg_list *listlist;
3160 /* ~{ catches ~^. */
3161 sub_list = union (sub_list, sub_escape);
3163 listlist = make_repeated_list_of_lists (sub_list);
3165 sub_list = listlist;
3169 /* Each iteration's arguments are all concatenated in a
3171 struct format_arg_list *looplist;
3173 /* FIXME: This is far from correct. Test cases:
3179 abc~{~D~^~C~}~:*~{~S~^~D~}
3182 /* ~{ catches ~^. */
3183 sub_list = union (sub_list, sub_escape);
3185 if (sub_list == NULL)
3186 looplist = make_empty_list ();
3188 if (sub_position < 0 || sub_position == 0)
3189 /* Too hard to track the possible argument types
3190 when the iteration is performed 2 times or more.
3191 So be satisfied with the constraints of executing
3192 the iteration 1 or 0 times. */
3193 looplist = make_union_with_empty_list (sub_list);
3195 looplist = make_repeated_list (sub_list, sub_position);
3197 sub_list = looplist;
3202 /* All remaining arguments are used. */
3203 if (list != NULL && position >= 0)
3205 shift_list (sub_list, position);
3206 list = make_intersected_list (list, sub_list);
3212 /* The argument is a list. */
3214 add_req_listtype_constraint (&list, position++,
3215 FAT_LIST, sub_list);
3221 case '}': /* 22.3.7.5 FORMAT-ITERATION-END */
3222 if (terminator != '}')
3225 xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
3226 FDI_SET (format - 1, FMTDIR_ERROR);
3229 if (!check_params (&list, paramcount, params, 0, NULL,
3230 spec->directives, invalid_reason))
3232 FDI_SET (format - 1, FMTDIR_ERROR);
3236 *positionp = position;
3241 case '<': /* 22.3.6.2, 22.3.5.2 FORMAT-JUSTIFICATION */
3242 if (!check_params (&list, paramcount, params, 4, IIIC,
3243 spec->directives, invalid_reason))
3245 FDI_SET (format - 1, FMTDIR_ERROR);
3249 struct format_arg_list *sub_escape = NULL;
3252 *positionp = position;
3257 int sub_separator = 0;
3258 if (!parse_upto (formatp, positionp, listp, &sub_escape,
3259 &sub_separator, spec, '>', true,
3260 NULL, invalid_reason))
3262 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3271 position = *positionp;
3274 /* ~< catches ~^. */
3275 if (sub_escape != NULL)
3277 list = union (list, sub_escape);
3281 case '>': /* 22.3.6.3 FORMAT-JUSTIFICATION-END */
3282 if (terminator != '>')
3285 xasprintf (_("Found '~%c' without matching '~%c'."), '>', '<');
3286 FDI_SET (format - 1, FMTDIR_ERROR);
3289 if (!check_params (&list, paramcount, params, 0, NULL,
3290 spec->directives, invalid_reason))
3292 FDI_SET (format - 1, FMTDIR_ERROR);
3296 *positionp = position;
3301 case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */
3302 if (!check_params (&list, paramcount, params, 3, THREE,
3303 spec->directives, invalid_reason))
3305 FDI_SET (format - 1, FMTDIR_ERROR);
3308 if (position >= 0 && list != NULL && is_required (list, position))
3309 /* This ~^ can never be executed. Ignore it. */
3313 struct format_arg_list *this_escape = copy_list (list);
3315 this_escape = add_end_constraint (this_escape, position);
3316 escape = union (escape, this_escape);
3319 list = add_required_constraint (list, position);
3322 case ';': /* 22.3.9.1 FORMAT-SEPARATOR */
3326 xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
3327 FDI_SET (format - 1, FMTDIR_ERROR);
3330 if (terminator == '>')
3332 if (!check_params (&list, paramcount, params, 1, I,
3333 spec->directives, invalid_reason))
3335 FDI_SET (format - 1, FMTDIR_ERROR);
3341 if (!check_params (&list, paramcount, params, 0, NULL,
3342 spec->directives, invalid_reason))
3344 FDI_SET (format - 1, FMTDIR_ERROR);
3349 *positionp = position;
3352 *separatorp = (colon_p ? 2 : 1);
3355 case '!': /* FORMAT-CALL, a CLISP extension */
3356 if (!nocheck_params (&list, paramcount, params,
3357 spec->directives, invalid_reason))
3359 FDI_SET (format - 1, FMTDIR_ERROR);
3364 add_req_type_constraint (&list, position++, FAT_FUNCTION);
3365 add_req_type_constraint (&list, position++, FAT_OBJECT);
3371 if (*format == '\0')
3373 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
3374 FDI_SET (format - 1, FMTDIR_ERROR);
3379 INVALID_CONVERSION_SPECIFIER (spec->directives, *format);
3380 FDI_SET (format, FMTDIR_ERROR);
3385 FDI_SET (format - 1, FMTDIR_END);
3391 *positionp = position;
3394 if (terminator != '\0')
3397 xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator);
3404 /* ============== Top level format string handling functions ============== */
3407 format_parse (const char *format, bool translated, char *fdi,
3408 char **invalid_reason)
3411 struct spec *result;
3413 struct format_arg_list *escape;
3415 spec.directives = 0;
3416 spec.list = make_unconstrained_list ();
3419 if (!parse_upto (&format, &position, &spec.list, &escape,
3420 NULL, &spec, '\0', false,
3421 fdi, invalid_reason))
3422 /* Invalid format string. */
3425 /* Catch ~^ here. */
3426 spec.list = union (spec.list, escape);
3428 if (spec.list == NULL)
3430 /* Contradictory argument type information. */
3432 xstrdup (_("The string refers to some argument in incompatible ways."));
3436 /* Normalize the result. */
3437 normalize_list (spec.list);
3439 result = XMALLOC (struct spec);
3445 format_free (void *descr)
3447 struct spec *spec = (struct spec *) descr;
3449 free_list (spec->list);
3453 format_get_number_of_directives (void *descr)
3455 struct spec *spec = (struct spec *) descr;
3457 return spec->directives;
3461 format_check (void *msgid_descr, void *msgstr_descr, bool equality,
3462 formatstring_error_logger_t error_logger,
3463 const char *pretty_msgid, const char *pretty_msgstr)
3465 struct spec *spec1 = (struct spec *) msgid_descr;
3466 struct spec *spec2 = (struct spec *) msgstr_descr;
3471 if (!equal_list (spec1->list, spec2->list))
3474 error_logger (_("format specifications in '%s' and '%s' are not equivalent"),
3475 pretty_msgid, pretty_msgstr);
3481 struct format_arg_list *intersection =
3482 make_intersected_list (copy_list (spec1->list),
3483 copy_list (spec2->list));
3485 if (!(intersection != NULL
3486 && (normalize_list (intersection),
3487 equal_list (intersection, spec2->list))))
3490 error_logger (_("format specifications in '%s' are not a subset of those in '%s'"),
3491 pretty_msgstr, pretty_msgid);
3500 struct formatstring_parser formatstring_lisp =
3504 format_get_number_of_directives,
3510 /* ============================= Testing code ============================= */
3516 /* Test program: Print the argument list specification returned by
3517 format_parse for strings read from standard input. */
3521 static void print_list (struct format_arg_list *list);
3524 print_element (struct format_arg *element)
3526 switch (element->presence)
3537 switch (element->type)
3542 case FAT_CHARACTER_INTEGER_NULL:
3545 case FAT_CHARACTER_NULL:
3551 case FAT_INTEGER_NULL:
3561 print_list (element->list);
3563 case FAT_FORMATSTRING:
3575 print_list (struct format_arg_list *list)
3581 for (i = 0; i < list->initial.count; i++)
3582 for (j = 0; j < list->initial.element[i].repcount; j++)
3586 print_element (&list->initial.element[i]);
3589 if (list->repeated.count > 0)
3592 for (i = 0; i < list->repeated.count; i++)
3593 for (j = 0; j < list->repeated.element[i].repcount; j++)
3596 print_element (&list->repeated.element[i]);
3604 format_print (void *descr)
3606 struct spec *spec = (struct spec *) descr;
3614 print_list (spec->list);
3623 size_t line_size = 0;
3625 char *invalid_reason;
3628 line_len = getline (&line, &line_size, stdin);
3631 if (line_len > 0 && line[line_len - 1] == '\n')
3632 line[--line_len] = '\0';
3634 invalid_reason = NULL;
3635 descr = format_parse (line, false, NULL, &invalid_reason);
3637 format_print (descr);
3640 printf ("%s\n", invalid_reason);
3642 free (invalid_reason);
3650 * For Emacs M-x compile
3652 * 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"