1 /* Scheme format strings.
2 Copyright (C) 2001-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"
33 #include "error-progname.h"
36 #define _(str) gettext (str)
39 /* Assertion macros. Could be defined to empty for speed. */
40 #define ASSERT(expr) if (!(expr)) abort ();
41 #define VERIFY_LIST(list) verify_list (list)
44 /* Scheme format strings are described in the GNU guile documentation,
45 section "Formatted Output". They are implemented in
46 guile-1.6.4/ice-9/format.scm. */
48 /* Data structure describing format string derived constraints for an
49 argument list. It is a recursive list structure. Structure sharing
54 FCT_REQUIRED, /* The format argument list cannot end before this argument. */
55 FCT_OPTIONAL /* The format argument list may end before this argument. */
60 FAT_OBJECT, /* Any object, type T. */
61 FAT_CHARACTER_INTEGER_NULL, /* Type (OR CHARACTER INTEGER NULL). */
62 FAT_CHARACTER_NULL, /* Type (OR CHARACTER NULL). */
63 FAT_CHARACTER, /* Type CHARACTER. */
64 FAT_INTEGER_NULL, /* Type (OR INTEGER NULL). */
65 FAT_INTEGER, /* Meant for objects of type INTEGER. */
66 FAT_REAL, /* Meant for objects of type REAL. */
67 FAT_COMPLEX, /* Meant for objects of type COMPLEX. */
68 FAT_LIST, /* Meant for proper lists. */
69 FAT_FORMATSTRING /* Format strings. */
74 unsigned int repcount; /* Number of consecutive arguments this constraint
75 applies to. Normally 1, but unconstrained
76 arguments are often repeated. */
77 enum format_cdr_type presence; /* Can the argument list end right before
79 enum format_arg_type type; /* Possible values for this argument. */
80 struct format_arg_list *list; /* For FAT_LIST: List elements. */
85 unsigned int count; /* Number of format_arg records used. */
86 unsigned int allocated;
87 struct format_arg *element; /* Argument constraints. */
88 unsigned int length; /* Number of arguments represented by this segment.
89 This is the sum of all repcounts in the segment. */
92 struct format_arg_list
94 /* The constraints for the potentially infinite argument list are assumed
95 to become ultimately periodic. (Too complicated argument lists without
97 (format t "~@{~:[-~;~S~]~}" nil t 1 t 3 nil t 4)
98 are described by a constraint that ends in a length 1 period of
99 unconstrained arguments.) Such a periodic sequence can be split into
100 an initial segment and an endlessly repeated loop segment.
101 A finite sequence is represented entirely in the initial segment; the
102 loop segment is empty. */
104 struct segment initial; /* Initial arguments segment. */
105 struct segment repeated; /* Endlessly repeated segment. */
110 unsigned int directives;
111 struct format_arg_list *list;
115 /* Parameter for a directive. */
118 PT_NIL, /* param not present */
119 PT_CHARACTER, /* character */
120 PT_INTEGER, /* integer */
121 PT_ARGCOUNT, /* number of remaining arguments */
122 PT_V /* variable taken from argument list */
127 enum param_type type;
128 int value; /* for PT_INTEGER: the value, for PT_V: the position */
132 /* Forward declaration of local functions. */
133 #define union make_union
134 static void verify_list (const struct format_arg_list *list);
135 static void free_list (struct format_arg_list *list);
136 static struct format_arg_list * copy_list (const struct format_arg_list *list);
137 static bool equal_list (const struct format_arg_list *list1,
138 const struct format_arg_list *list2);
139 static struct format_arg_list * make_intersected_list
140 (struct format_arg_list *list1,
141 struct format_arg_list *list2);
142 static struct format_arg_list * make_intersection_with_empty_list
143 (struct format_arg_list *list);
144 static struct format_arg_list * make_union_list
145 (struct format_arg_list *list1,
146 struct format_arg_list *list2);
149 /* ======================= Verify a format_arg_list ======================= */
151 /* Verify some invariants. */
153 verify_element (const struct format_arg * e)
155 ASSERT (e->repcount > 0);
156 if (e->type == FAT_LIST)
157 verify_list (e->list);
160 /* Verify some invariants. */
161 /* Memory effects: none. */
163 verify_list (const struct format_arg_list *list)
166 unsigned int total_repcount;
168 ASSERT (list->initial.count <= list->initial.allocated);
170 for (i = 0; i < list->initial.count; i++)
172 verify_element (&list->initial.element[i]);
173 total_repcount += list->initial.element[i].repcount;
175 ASSERT (total_repcount == list->initial.length);
177 ASSERT (list->repeated.count <= list->repeated.allocated);
179 for (i = 0; i < list->repeated.count; i++)
181 verify_element (&list->repeated.element[i]);
182 total_repcount += list->repeated.element[i].repcount;
184 ASSERT (total_repcount == list->repeated.length);
187 #define VERIFY_LIST(list) verify_list (list)
190 /* ======================== Free a format_arg_list ======================== */
192 /* Free the data belonging to an argument list element. */
194 free_element (struct format_arg *element)
196 if (element->type == FAT_LIST)
197 free_list (element->list);
200 /* Free an argument list. */
201 /* Memory effects: Frees list. */
203 free_list (struct format_arg_list *list)
207 for (i = 0; i < list->initial.count; i++)
208 free_element (&list->initial.element[i]);
209 if (list->initial.element != NULL)
210 free (list->initial.element);
212 for (i = 0; i < list->repeated.count; i++)
213 free_element (&list->repeated.element[i]);
214 if (list->repeated.element != NULL)
215 free (list->repeated.element);
219 /* ======================== Copy a format_arg_list ======================== */
221 /* Copy the data belonging to an argument list element. */
223 copy_element (struct format_arg *newelement,
224 const struct format_arg *oldelement)
226 newelement->repcount = oldelement->repcount;
227 newelement->presence = oldelement->presence;
228 newelement->type = oldelement->type;
229 if (oldelement->type == FAT_LIST)
230 newelement->list = copy_list (oldelement->list);
233 /* Copy an argument list. */
234 /* Memory effects: Freshly allocated result. */
235 static struct format_arg_list *
236 copy_list (const struct format_arg_list *list)
238 struct format_arg_list *newlist;
244 newlist = XMALLOC (struct format_arg_list);
246 newlist->initial.count = newlist->initial.allocated = list->initial.count;
248 if (list->initial.count == 0)
249 newlist->initial.element = NULL;
252 newlist->initial.element =
253 XNMALLOC (newlist->initial.allocated, struct format_arg);
254 for (i = 0; i < list->initial.count; i++)
256 copy_element (&newlist->initial.element[i],
257 &list->initial.element[i]);
258 length += list->initial.element[i].repcount;
261 ASSERT (length == list->initial.length);
262 newlist->initial.length = length;
264 newlist->repeated.count = newlist->repeated.allocated = list->repeated.count;
266 if (list->repeated.count == 0)
267 newlist->repeated.element = NULL;
270 newlist->repeated.element =
271 XNMALLOC (newlist->repeated.allocated, struct format_arg);
272 for (i = 0; i < list->repeated.count; i++)
274 copy_element (&newlist->repeated.element[i],
275 &list->repeated.element[i]);
276 length += list->repeated.element[i].repcount;
279 ASSERT (length == list->repeated.length);
280 newlist->repeated.length = length;
282 VERIFY_LIST (newlist);
288 /* ===================== Compare two format_arg_lists ===================== */
290 /* Tests whether two normalized argument constraints are equivalent,
291 ignoring the repcount. */
293 equal_element (const struct format_arg * e1, const struct format_arg * e2)
295 return (e1->presence == e2->presence
296 && e1->type == e2->type
297 && (e1->type == FAT_LIST ? equal_list (e1->list, e2->list) : true));
300 /* Tests whether two normalized argument list constraints are equivalent. */
301 /* Memory effects: none. */
303 equal_list (const struct format_arg_list *list1,
304 const struct format_arg_list *list2)
311 n = list1->initial.count;
312 if (n != list2->initial.count)
314 for (i = 0; i < n; i++)
316 const struct format_arg * e1 = &list1->initial.element[i];
317 const struct format_arg * e2 = &list2->initial.element[i];
319 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
323 n = list1->repeated.count;
324 if (n != list2->repeated.count)
326 for (i = 0; i < n; i++)
328 const struct format_arg * e1 = &list1->repeated.element[i];
329 const struct format_arg * e2 = &list2->repeated.element[i];
331 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
339 /* ===================== Incremental memory allocation ===================== */
341 /* Ensure list->initial.allocated >= newcount. */
343 ensure_initial_alloc (struct format_arg_list *list, unsigned int newcount)
345 if (newcount > list->initial.allocated)
347 list->initial.allocated =
348 MAX (2 * list->initial.allocated + 1, newcount);
349 list->initial.element =
350 (struct format_arg *)
351 xrealloc (list->initial.element,
352 list->initial.allocated * sizeof (struct format_arg));
356 /* Ensure list->initial.allocated > list->initial.count. */
358 grow_initial_alloc (struct format_arg_list *list)
360 if (list->initial.count >= list->initial.allocated)
362 list->initial.allocated =
363 MAX (2 * list->initial.allocated + 1, list->initial.count + 1);
364 list->initial.element =
365 (struct format_arg *)
366 xrealloc (list->initial.element,
367 list->initial.allocated * sizeof (struct format_arg));
371 /* Ensure list->repeated.allocated >= newcount. */
373 ensure_repeated_alloc (struct format_arg_list *list, unsigned int newcount)
375 if (newcount > list->repeated.allocated)
377 list->repeated.allocated =
378 MAX (2 * list->repeated.allocated + 1, newcount);
379 list->repeated.element =
380 (struct format_arg *)
381 xrealloc (list->repeated.element,
382 list->repeated.allocated * sizeof (struct format_arg));
386 /* Ensure list->repeated.allocated > list->repeated.count. */
388 grow_repeated_alloc (struct format_arg_list *list)
390 if (list->repeated.count >= list->repeated.allocated)
392 list->repeated.allocated =
393 MAX (2 * list->repeated.allocated + 1, list->repeated.count + 1);
394 list->repeated.element =
395 (struct format_arg *)
396 xrealloc (list->repeated.element,
397 list->repeated.allocated * sizeof (struct format_arg));
402 /* ====================== Normalize a format_arg_list ====================== */
404 /* Normalize an argument list constraint, assuming all sublists are already
406 /* Memory effects: Destructively modifies list. */
408 normalize_outermost_list (struct format_arg_list *list)
410 unsigned int n, i, j;
412 /* Step 1: Combine adjacent elements.
413 Copy from i to j, keeping 0 <= j <= i. */
415 n = list->initial.count;
416 for (i = j = 0; i < n; i++)
418 && equal_element (&list->initial.element[i],
419 &list->initial.element[j-1]))
421 list->initial.element[j-1].repcount +=
422 list->initial.element[i].repcount;
423 free_element (&list->initial.element[i]);
428 list->initial.element[j] = list->initial.element[i];
431 list->initial.count = j;
433 n = list->repeated.count;
434 for (i = j = 0; i < n; i++)
436 && equal_element (&list->repeated.element[i],
437 &list->repeated.element[j-1]))
439 list->repeated.element[j-1].repcount +=
440 list->repeated.element[i].repcount;
441 free_element (&list->repeated.element[i]);
446 list->repeated.element[j] = list->repeated.element[i];
449 list->repeated.count = j;
451 /* Nothing more to be done if the loop segment is empty. */
452 if (list->repeated.count > 0)
454 unsigned int m, repcount0_extra;
456 /* Step 2: Reduce the loop period. */
457 n = list->repeated.count;
460 && equal_element (&list->repeated.element[0],
461 &list->repeated.element[n-1]))
463 repcount0_extra = list->repeated.element[n-1].repcount;
466 /* Proceed as if the loop period were n, with
467 list->repeated.element[0].repcount incremented by repcount0_extra. */
468 for (m = 2; m <= n / 2; n++)
471 /* m is a divisor of n. Try to reduce the loop period to n. */
474 for (i = 0; i < n - m; i++)
475 if (!((list->repeated.element[i].repcount
476 + (i == 0 ? repcount0_extra : 0)
477 == list->repeated.element[i+m].repcount)
478 && equal_element (&list->repeated.element[i],
479 &list->repeated.element[i+m])))
486 for (i = m; i < n; i++)
487 free_element (&list->repeated.element[i]);
488 if (n < list->repeated.count)
489 list->repeated.element[m] = list->repeated.element[n];
490 list->repeated.count = list->repeated.count - n + m;
491 list->repeated.length /= n / m;
496 /* Step 3: Roll as much as possible of the initial segment's tail
498 if (list->repeated.count == 1)
500 if (list->initial.count > 0
501 && equal_element (&list->initial.element[list->initial.count-1],
502 &list->repeated.element[0]))
504 /* Roll the last element of the initial segment into the loop.
505 Its repcount is irrelevant. The second-to-last element is
506 certainly different and doesn't need to be considered. */
507 list->initial.length -=
508 list->initial.element[list->initial.count-1].repcount;
509 list->initial.count--;
514 while (list->initial.count > 0
515 && equal_element (&list->initial.element[list->initial.count-1],
516 &list->repeated.element[list->repeated.count-1]))
518 unsigned int moved_repcount =
519 MIN (list->initial.element[list->initial.count-1].repcount,
520 list->repeated.element[list->repeated.count-1].repcount);
522 /* Add the element at the start of list->repeated. */
523 if (equal_element (&list->repeated.element[0],
524 &list->repeated.element[list->repeated.count-1]))
525 list->repeated.element[0].repcount += moved_repcount;
528 unsigned int newcount = list->repeated.count + 1;
529 ensure_repeated_alloc (list, newcount);
530 for (i = newcount - 1; i > 0; i--)
531 list->repeated.element[i] = list->repeated.element[i-1];
532 list->repeated.count = newcount;
533 copy_element (&list->repeated.element[0],
534 &list->repeated.element[list->repeated.count-1]);
535 list->repeated.element[0].repcount = moved_repcount;
538 /* Remove the element from the end of list->repeated. */
539 list->repeated.element[list->repeated.count-1].repcount -=
541 if (list->repeated.element[list->repeated.count-1].repcount == 0)
543 free_element (&list->repeated.element[list->repeated.count-1]);
544 list->repeated.count--;
547 /* Remove the element from the end of list->initial. */
548 list->initial.element[list->initial.count-1].repcount -=
550 if (list->initial.element[list->initial.count-1].repcount == 0)
552 free_element (&list->initial.element[list->initial.count-1]);
553 list->initial.count--;
555 list->initial.length -= moved_repcount;
561 /* Normalize an argument list constraint. */
562 /* Memory effects: Destructively modifies list. */
564 normalize_list (struct format_arg_list *list)
570 /* First normalize all elements, recursively. */
571 n = list->initial.count;
572 for (i = 0; i < n; i++)
573 if (list->initial.element[i].type == FAT_LIST)
574 normalize_list (list->initial.element[i].list);
575 n = list->repeated.count;
576 for (i = 0; i < n; i++)
577 if (list->repeated.element[i].type == FAT_LIST)
578 normalize_list (list->repeated.element[i].list);
580 /* Then normalize the top level list. */
581 normalize_outermost_list (list);
587 /* ===================== Unconstrained and empty lists ===================== */
589 /* It's easier to allocate these on demand, than to be careful not to
590 accidentally modify statically allocated lists. */
593 /* Create an unconstrained argument list. */
594 /* Memory effects: Freshly allocated result. */
595 static struct format_arg_list *
596 make_unconstrained_list ()
598 struct format_arg_list *list;
600 list = XMALLOC (struct format_arg_list);
601 list->initial.count = 0;
602 list->initial.allocated = 0;
603 list->initial.element = NULL;
604 list->initial.length = 0;
605 list->repeated.count = 1;
606 list->repeated.allocated = 1;
607 list->repeated.element = XNMALLOC (1, struct format_arg);
608 list->repeated.element[0].repcount = 1;
609 list->repeated.element[0].presence = FCT_OPTIONAL;
610 list->repeated.element[0].type = FAT_OBJECT;
611 list->repeated.length = 1;
619 /* Create an empty argument list. */
620 /* Memory effects: Freshly allocated result. */
621 static struct format_arg_list *
624 struct format_arg_list *list;
626 list = XMALLOC (struct format_arg_list);
627 list->initial.count = 0;
628 list->initial.allocated = 0;
629 list->initial.element = NULL;
630 list->initial.length = 0;
631 list->repeated.count = 0;
632 list->repeated.allocated = 0;
633 list->repeated.element = NULL;
634 list->repeated.length = 0;
642 /* Test for an empty list. */
643 /* Memory effects: none. */
645 is_empty_list (const struct format_arg_list *list)
647 return (list->initial.count == 0 && list->repeated.count == 0);
651 /* ======================== format_arg_list surgery ======================== */
653 /* Unfold list->repeated m times, where m >= 1.
654 Assumes list->repeated.count > 0. */
655 /* Memory effects: list is destructively modified. */
657 unfold_loop (struct format_arg_list *list, unsigned int m)
659 unsigned int i, j, k;
663 unsigned int newcount = list->repeated.count * m;
664 ensure_repeated_alloc (list, newcount);
665 i = list->repeated.count;
666 for (k = 1; k < m; k++)
667 for (j = 0; j < list->repeated.count; j++, i++)
668 copy_element (&list->repeated.element[i], &list->repeated.element[j]);
669 list->repeated.count = newcount;
670 list->repeated.length = list->repeated.length * m;
674 /* Ensure list->initial.length := m, where m >= list->initial.length.
675 Assumes list->repeated.count > 0. */
676 /* Memory effects: list is destructively modified. */
678 rotate_loop (struct format_arg_list *list, unsigned int m)
680 if (m == list->initial.length)
683 if (list->repeated.count == 1)
685 /* Instead of multiple copies of list->repeated.element[0], a single
686 copy with higher repcount is appended to list->initial. */
687 unsigned int i, newcount;
689 newcount = list->initial.count + 1;
690 ensure_initial_alloc (list, newcount);
691 i = list->initial.count;
692 copy_element (&list->initial.element[i], &list->repeated.element[0]);
693 list->initial.element[i].repcount = m - list->initial.length;
694 list->initial.count = newcount;
695 list->initial.length = m;
699 unsigned int n = list->repeated.length;
701 /* Write m = list->initial.length + q * n + r with 0 <= r < n. */
702 unsigned int q = (m - list->initial.length) / n;
703 unsigned int r = (m - list->initial.length) % n;
705 /* Determine how many entries of list->repeated are needed for
711 s < list->repeated.count && t >= list->repeated.element[s].repcount;
712 t -= list->repeated.element[s].repcount, s++)
715 /* s must be < list->repeated.count, otherwise r would have been >= n. */
716 ASSERT (s < list->repeated.count);
718 /* So we need to add to list->initial:
719 q full copies of list->repeated,
720 plus the s first elements of list->repeated,
721 plus, if t > 0, a splitoff of list->repeated.element[s]. */
723 unsigned int i, j, k, newcount;
725 i = list->initial.count;
726 newcount = i + q * list->repeated.count + s + (t > 0 ? 1 : 0);
727 ensure_initial_alloc (list, newcount);
728 for (k = 0; k < q; k++)
729 for (j = 0; j < list->repeated.count; j++, i++)
730 copy_element (&list->initial.element[i],
731 &list->repeated.element[j]);
732 for (j = 0; j < s; j++, i++)
733 copy_element (&list->initial.element[i], &list->repeated.element[j]);
736 copy_element (&list->initial.element[i],
737 &list->repeated.element[j]);
738 list->initial.element[i].repcount = t;
741 ASSERT (i == newcount);
742 list->initial.count = newcount;
743 /* The new length of the initial segment is
744 = list->initial.length
745 + q * list->repeated.length
746 + list->repeated[0..s-1].repcount + t
747 = list->initial.length + q * n + r
750 list->initial.length = m;
753 /* And rotate list->repeated. */
756 unsigned int i, j, oldcount, newcount;
757 struct format_arg *newelement;
759 oldcount = list->repeated.count;
760 newcount = list->repeated.count + (t > 0 ? 1 : 0);
761 newelement = XNMALLOC (newcount, struct format_arg);
763 for (j = s; j < oldcount; j++, i++)
764 newelement[i] = list->repeated.element[j];
765 for (j = 0; j < s; j++, i++)
766 newelement[i] = list->repeated.element[j];
769 copy_element (&newelement[oldcount], &newelement[0]);
770 newelement[0].repcount -= t;
771 newelement[oldcount].repcount = t;
773 free (list->repeated.element);
774 list->repeated.element = newelement;
780 /* Ensure index n in the initial segment falls on a split between elements,
781 i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two
782 different adjacent elements. */
783 /* Memory effects: list is destructively modified. */
785 initial_splitelement (struct format_arg_list *list, unsigned int n)
789 unsigned int oldrepcount;
790 unsigned int newcount;
795 if (n > list->initial.length)
797 ASSERT (list->repeated.count > 0);
798 rotate_loop (list, n);
799 ASSERT (n <= list->initial.length);
802 /* Determine how many entries of list->initial need to be skipped. */
804 s < list->initial.count && t >= list->initial.element[s].repcount;
805 t -= list->initial.element[s].repcount, s++)
811 ASSERT (s < list->initial.count);
813 /* Split the entry into two entries. */
814 oldrepcount = list->initial.element[s].repcount;
815 newcount = list->initial.count + 1;
816 ensure_initial_alloc (list, newcount);
817 for (i = list->initial.count - 1; i > s; i--)
818 list->initial.element[i+1] = list->initial.element[i];
819 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
820 list->initial.element[s].repcount = t;
821 list->initial.element[s+1].repcount = oldrepcount - t;
822 list->initial.count = newcount;
830 /* Ensure index n in the initial segment is not shared. Return its index. */
831 /* Memory effects: list is destructively modified. */
833 initial_unshare (struct format_arg_list *list, unsigned int n)
835 /* This does the same side effects as
836 initial_splitelement (list, n);
837 initial_splitelement (list, n + 1);
844 if (n >= list->initial.length)
846 ASSERT (list->repeated.count > 0);
847 rotate_loop (list, n + 1);
848 ASSERT (n < list->initial.length);
851 /* Determine how many entries of list->initial need to be skipped. */
853 s < list->initial.count && t >= list->initial.element[s].repcount;
854 t -= list->initial.element[s].repcount, s++)
857 /* s must be < list->initial.count. */
858 ASSERT (s < list->initial.count);
860 if (list->initial.element[s].repcount > 1)
862 /* Split the entry into at most three entries: for indices < n,
863 for index n, and for indices > n. */
864 unsigned int oldrepcount = list->initial.element[s].repcount;
865 unsigned int newcount =
866 list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2);
867 ensure_initial_alloc (list, newcount);
868 if (t == 0 || t == oldrepcount - 1)
872 for (i = list->initial.count - 1; i > s; i--)
873 list->initial.element[i+1] = list->initial.element[i];
874 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
877 list->initial.element[s].repcount = 1;
878 list->initial.element[s+1].repcount = oldrepcount - 1;
882 list->initial.element[s].repcount = oldrepcount - 1;
883 list->initial.element[s+1].repcount = 1;
890 for (i = list->initial.count - 1; i > s; i--)
891 list->initial.element[i+2] = list->initial.element[i];
892 copy_element (&list->initial.element[s+2], &list->initial.element[s]);
893 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
894 list->initial.element[s].repcount = t;
895 list->initial.element[s+1].repcount = 1;
896 list->initial.element[s+2].repcount = oldrepcount - 1 - t;
898 list->initial.count = newcount;
903 /* Now the entry for index n has repcount 1. */
904 ASSERT (list->initial.element[s].repcount == 1);
912 /* Add n unconstrained elements at the front of the list. */
913 /* Memory effects: list is destructively modified. */
915 shift_list (struct format_arg_list *list, unsigned int n)
923 grow_initial_alloc (list);
924 for (i = list->initial.count; i > 0; i--)
925 list->initial.element[i] = list->initial.element[i-1];
926 list->initial.element[0].repcount = n;
927 list->initial.element[0].presence = FCT_REQUIRED;
928 list->initial.element[0].type = FAT_OBJECT;
929 list->initial.count++;
930 list->initial.length += n;
932 normalize_outermost_list (list);
939 /* ================= Intersection of two format_arg_lists ================= */
941 /* Create the intersection (i.e. combined constraints) of two argument
942 constraints. Return false if the intersection is empty, i.e. if the
943 two constraints give a contradiction. */
944 /* Memory effects: Freshly allocated element's sublist. */
946 make_intersected_element (struct format_arg *re,
947 const struct format_arg * e1,
948 const struct format_arg * e2)
950 /* Intersect the cdr types. */
951 if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED)
952 re->presence = FCT_REQUIRED;
954 re->presence = FCT_OPTIONAL;
956 /* Intersect the arg types. */
957 if (e1->type == FAT_OBJECT)
960 if (re->type == FAT_LIST)
961 re->list = copy_list (e2->list);
963 else if (e2->type == FAT_OBJECT)
966 if (re->type == FAT_LIST)
967 re->list = copy_list (e1->list);
969 else if (e1->type == FAT_LIST
970 && (e2->type == FAT_CHARACTER_INTEGER_NULL
971 || e2->type == FAT_CHARACTER_NULL
972 || e2->type == FAT_INTEGER_NULL))
975 re->list = make_intersection_with_empty_list (e1->list);
976 if (re->list == NULL)
979 else if (e2->type == FAT_LIST
980 && (e1->type == FAT_CHARACTER_INTEGER_NULL
981 || e1->type == FAT_CHARACTER_NULL
982 || e1->type == FAT_INTEGER_NULL))
985 re->list = make_intersection_with_empty_list (e2->list);
986 if (re->list == NULL)
989 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
990 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
991 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
995 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
996 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
997 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1001 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1003 re->type = e2->type;
1005 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1007 re->type = e1->type;
1009 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1011 re->type = e2->type;
1013 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1015 re->type = e1->type;
1017 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1019 re->type = e2->type;
1021 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1023 re->type = e1->type;
1025 else if (e1->type == FAT_COMPLEX
1026 && (e2->type == FAT_REAL || e2->type == FAT_INTEGER))
1028 re->type = e2->type;
1030 else if (e2->type == FAT_COMPLEX
1031 && (e1->type == FAT_REAL || e1->type == FAT_INTEGER))
1033 re->type = e1->type;
1035 else if (e1->type == e2->type)
1037 re->type = e1->type;
1038 if (re->type == FAT_LIST)
1040 re->list = make_intersected_list (copy_list (e1->list),
1041 copy_list (e2->list));
1042 if (re->list == NULL)
1047 /* Each of FAT_CHARACTER, FAT_INTEGER, FAT_LIST, FAT_FORMATSTRING
1048 matches only itself. Contradiction. */
1054 /* Append list->repeated to list->initial, and clear list->repeated. */
1055 /* Memory effects: list is destructively modified. */
1057 append_repeated_to_initial (struct format_arg_list *list)
1059 if (list->repeated.count > 0)
1061 /* Move list->repeated over to list->initial. */
1062 unsigned int i, j, newcount;
1064 newcount = list->initial.count + list->repeated.count;
1065 ensure_initial_alloc (list, newcount);
1066 i = list->initial.count;
1067 for (j = 0; j < list->repeated.count; j++, i++)
1068 list->initial.element[i] = list->repeated.element[j];
1069 list->initial.count = newcount;
1070 list->initial.length = list->initial.length + list->repeated.length;
1071 free (list->repeated.element);
1072 list->repeated.element = NULL;
1073 list->repeated.allocated = 0;
1074 list->repeated.count = 0;
1075 list->repeated.length = 0;
1079 /* Handle a contradiction during building of a format_arg_list.
1080 The list consists only of an initial segment. The repeated segment is
1081 empty. This function searches the last FCT_OPTIONAL and cuts off the
1082 list at this point, or - if none is found - returns NULL. */
1083 /* Memory effects: list is destructively modified. If NULL is returned,
1085 static struct format_arg_list *
1086 backtrack_in_initial (struct format_arg_list *list)
1088 ASSERT (list->repeated.count == 0);
1090 while (list->initial.count > 0)
1092 unsigned int i = list->initial.count - 1;
1093 if (list->initial.element[i].presence == FCT_REQUIRED)
1095 /* Throw away this element. */
1096 list->initial.length -= list->initial.element[i].repcount;
1097 free_element (&list->initial.element[i]);
1098 list->initial.count = i;
1100 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1102 /* The list must end here. */
1103 list->initial.length--;
1104 if (list->initial.element[i].repcount > 1)
1105 list->initial.element[i].repcount--;
1108 free_element (&list->initial.element[i]);
1109 list->initial.count = i;
1120 /* Create the intersection (i.e. combined constraints) of two argument list
1121 constraints. Free both argument lists when done. Return NULL if the
1122 intersection is empty, i.e. if the two constraints give a contradiction. */
1123 /* Memory effects: list1 and list2 are freed. The result, if non-NULL, is
1124 freshly allocated. */
1125 static struct format_arg_list *
1126 make_intersected_list (struct format_arg_list *list1,
1127 struct format_arg_list *list2)
1129 struct format_arg_list *result;
1131 VERIFY_LIST (list1);
1132 VERIFY_LIST (list2);
1134 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1135 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1137 unsigned int n1 = list1->repeated.length;
1138 unsigned int n2 = list2->repeated.length;
1139 unsigned int g = gcd (n1, n2);
1140 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1141 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1143 unfold_loop (list1, m1);
1144 unfold_loop (list2, m2);
1145 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1148 if (list1->repeated.length > 0 || list2->repeated.length > 0)
1149 /* Step 2: Ensure the initial segment of the result can be computed
1150 from the initial segments of list1 and list2. If both have a
1151 repeated segment, this means to ensure
1152 list1->initial.length == list2->initial.length. */
1154 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1156 if (list1->repeated.length > 0)
1157 rotate_loop (list1, m);
1158 if (list2->repeated.length > 0)
1159 rotate_loop (list2, m);
1162 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1164 ASSERT (list1->initial.length == list2->initial.length);
1165 ASSERT (list1->repeated.length == list2->repeated.length);
1168 /* Step 3: Allocate the result. */
1169 result = XMALLOC (struct format_arg_list);
1170 result->initial.count = 0;
1171 result->initial.allocated = 0;
1172 result->initial.element = NULL;
1173 result->initial.length = 0;
1174 result->repeated.count = 0;
1175 result->repeated.allocated = 0;
1176 result->repeated.element = NULL;
1177 result->repeated.length = 0;
1179 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1181 struct format_arg *e1;
1182 struct format_arg *e2;
1186 e1 = list1->initial.element; c1 = list1->initial.count;
1187 e2 = list2->initial.element; c2 = list2->initial.count;
1188 while (c1 > 0 && c2 > 0)
1190 struct format_arg *re;
1192 /* Ensure room in result->initial. */
1193 grow_initial_alloc (result);
1194 re = &result->initial.element[result->initial.count];
1195 re->repcount = MIN (e1->repcount, e2->repcount);
1197 /* Intersect the argument types. */
1198 if (!make_intersected_element (re, e1, e2))
1200 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1201 if (re->presence == FCT_REQUIRED)
1202 /* Contradiction. Backtrack. */
1203 result = backtrack_in_initial (result);
1207 result->initial.count++;
1208 result->initial.length += re->repcount;
1210 e1->repcount -= re->repcount;
1211 if (e1->repcount == 0)
1216 e2->repcount -= re->repcount;
1217 if (e2->repcount == 0)
1224 if (list1->repeated.count == 0 && list2->repeated.count == 0)
1226 /* Intersecting two finite lists. */
1229 /* list1 longer than list2. */
1230 if (e1->presence == FCT_REQUIRED)
1231 /* Contradiction. Backtrack. */
1232 result = backtrack_in_initial (result);
1236 /* list2 longer than list1. */
1237 if (e2->presence == FCT_REQUIRED)
1238 /* Contradiction. Backtrack. */
1239 result = backtrack_in_initial (result);
1243 else if (list1->repeated.count == 0)
1245 /* Intersecting a finite and an infinite list. */
1247 if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence)
1249 /* Contradiction. Backtrack. */
1250 result = backtrack_in_initial (result);
1253 else if (list2->repeated.count == 0)
1255 /* Intersecting an infinite and a finite list. */
1257 if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence)
1259 /* Contradiction. Backtrack. */
1260 result = backtrack_in_initial (result);
1263 /* Intersecting two infinite lists. */
1264 ASSERT (c1 == 0 && c2 == 0);
1267 /* Step 5: Elementwise intersection of list1->repeated, list2->repeated. */
1269 struct format_arg *e1;
1270 struct format_arg *e2;
1274 e1 = list1->repeated.element; c1 = list1->repeated.count;
1275 e2 = list2->repeated.element; c2 = list2->repeated.count;
1276 while (c1 > 0 && c2 > 0)
1278 struct format_arg *re;
1280 /* Ensure room in result->repeated. */
1281 grow_repeated_alloc (result);
1282 re = &result->repeated.element[result->repeated.count];
1283 re->repcount = MIN (e1->repcount, e2->repcount);
1285 /* Intersect the argument types. */
1286 if (!make_intersected_element (re, e1, e2))
1288 append_repeated_to_initial (result);
1290 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1291 if (re->presence == FCT_REQUIRED)
1292 /* Contradiction. Backtrack. */
1293 result = backtrack_in_initial (result);
1298 result->repeated.count++;
1299 result->repeated.length += re->repcount;
1301 e1->repcount -= re->repcount;
1302 if (e1->repcount == 0)
1307 e2->repcount -= re->repcount;
1308 if (e2->repcount == 0)
1314 ASSERT (c1 == 0 && c2 == 0);
1322 /* Undo the loop unfolding and unrolling done above. */
1323 normalize_outermost_list (result);
1324 VERIFY_LIST (result);
1330 /* Create the intersection of an argument list and the empty list.
1331 Return NULL if the intersection is empty. */
1332 /* Memory effects: The result, if non-NULL, is freshly allocated. */
1333 static struct format_arg_list *
1334 make_intersection_with_empty_list (struct format_arg_list *list)
1336 #if 0 /* equivalent but slower */
1337 return make_intersected_list (copy_list (list), make_empty_list ());
1339 if (list->initial.count > 0
1340 ? list->initial.element[0].presence == FCT_REQUIRED
1341 : list->repeated.count > 0
1342 && list->repeated.element[0].presence == FCT_REQUIRED)
1345 return make_empty_list ();
1351 /* Create the intersection of two argument list constraints. NULL stands
1352 for an impossible situation, i.e. a contradiction. */
1353 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1354 if non-NULL, is freshly allocated. */
1355 static struct format_arg_list *
1356 intersection (struct format_arg_list *list1, struct format_arg_list *list2)
1361 return make_intersected_list (list1, list2);
1382 /* ===================== Union of two format_arg_lists ===================== */
1384 /* Create the union (i.e. alternative constraints) of two argument
1387 make_union_element (struct format_arg *re,
1388 const struct format_arg * e1,
1389 const struct format_arg * e2)
1391 /* Union of the cdr types. */
1392 if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED)
1393 re->presence = FCT_REQUIRED;
1394 else /* Either one of them is FCT_OPTIONAL. */
1395 re->presence = FCT_OPTIONAL;
1397 /* Union of the arg types. */
1398 if (e1->type == e2->type)
1400 re->type = e1->type;
1401 if (re->type == FAT_LIST)
1402 re->list = make_union_list (copy_list (e1->list),
1403 copy_list (e2->list));
1405 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
1406 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
1407 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
1409 re->type = e1->type;
1411 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
1412 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
1413 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1415 re->type = e2->type;
1417 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1419 re->type = e1->type;
1421 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1423 re->type = e2->type;
1425 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1427 re->type = e1->type;
1429 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1431 re->type = e2->type;
1433 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1435 re->type = e1->type;
1437 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1439 re->type = e2->type;
1441 else if (e1->type == FAT_COMPLEX
1442 && (e2->type == FAT_REAL || e2->type == FAT_INTEGER))
1444 re->type = e1->type;
1446 else if (e2->type == FAT_COMPLEX
1447 && (e1->type == FAT_REAL || e1->type == FAT_INTEGER))
1449 re->type = e2->type;
1451 else if (e1->type == FAT_LIST && is_empty_list (e1->list))
1453 if (e2->type == FAT_CHARACTER_INTEGER_NULL
1454 || e2->type == FAT_CHARACTER_NULL
1455 || e2->type == FAT_INTEGER_NULL)
1456 re->type = e2->type;
1457 else if (e2->type == FAT_CHARACTER)
1458 re->type = FAT_CHARACTER_NULL;
1459 else if (e2->type == FAT_INTEGER)
1460 re->type = FAT_INTEGER_NULL;
1462 re->type = FAT_OBJECT;
1464 else if (e2->type == FAT_LIST && is_empty_list (e2->list))
1466 if (e1->type == FAT_CHARACTER_INTEGER_NULL
1467 || e1->type == FAT_CHARACTER_NULL
1468 || e1->type == FAT_INTEGER_NULL)
1469 re->type = e1->type;
1470 else if (e1->type == FAT_CHARACTER)
1471 re->type = FAT_CHARACTER_NULL;
1472 else if (e1->type == FAT_INTEGER)
1473 re->type = FAT_INTEGER_NULL;
1475 re->type = FAT_OBJECT;
1477 else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL)
1478 && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL))
1480 re->type = FAT_CHARACTER_INTEGER_NULL;
1482 else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL)
1483 && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL))
1485 re->type = FAT_CHARACTER_INTEGER_NULL;
1489 /* Other union types are too hard to describe precisely. */
1490 re->type = FAT_OBJECT;
1494 /* Create the union (i.e. alternative constraints) of two argument list
1495 constraints. Free both argument lists when done. */
1496 /* Memory effects: list1 and list2 are freed. The result is freshly
1498 static struct format_arg_list *
1499 make_union_list (struct format_arg_list *list1, struct format_arg_list *list2)
1501 struct format_arg_list *result;
1503 VERIFY_LIST (list1);
1504 VERIFY_LIST (list2);
1506 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1508 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1510 unsigned int n1 = list1->repeated.length;
1511 unsigned int n2 = list2->repeated.length;
1512 unsigned int g = gcd (n1, n2);
1513 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1514 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1516 unfold_loop (list1, m1);
1517 unfold_loop (list2, m2);
1518 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1521 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1523 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1525 rotate_loop (list1, m);
1526 rotate_loop (list2, m);
1529 ASSERT (list1->initial.length == list2->initial.length);
1530 ASSERT (list1->repeated.length == list2->repeated.length);
1532 else if (list1->repeated.length > 0)
1534 /* Ensure the initial segment of the result can be computed from the
1535 initial segment of list1. */
1536 if (list2->initial.length >= list1->initial.length)
1538 rotate_loop (list1, list2->initial.length);
1539 if (list1->repeated.element[0].presence == FCT_REQUIRED)
1540 rotate_loop (list1, list1->initial.length + 1);
1543 else if (list2->repeated.length > 0)
1545 /* Ensure the initial segment of the result can be computed from the
1546 initial segment of list2. */
1547 if (list1->initial.length >= list2->initial.length)
1549 rotate_loop (list2, list1->initial.length);
1550 if (list2->repeated.element[0].presence == FCT_REQUIRED)
1551 rotate_loop (list2, list2->initial.length + 1);
1555 /* Step 3: Allocate the result. */
1556 result = XMALLOC (struct format_arg_list);
1557 result->initial.count = 0;
1558 result->initial.allocated = 0;
1559 result->initial.element = NULL;
1560 result->initial.length = 0;
1561 result->repeated.count = 0;
1562 result->repeated.allocated = 0;
1563 result->repeated.element = NULL;
1564 result->repeated.length = 0;
1566 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1568 struct format_arg *e1;
1569 struct format_arg *e2;
1573 e1 = list1->initial.element; c1 = list1->initial.count;
1574 e2 = list2->initial.element; c2 = list2->initial.count;
1575 while (c1 > 0 && c2 > 0)
1577 struct format_arg *re;
1579 /* Ensure room in result->initial. */
1580 grow_initial_alloc (result);
1581 re = &result->initial.element[result->initial.count];
1582 re->repcount = MIN (e1->repcount, e2->repcount);
1584 /* Union of the argument types. */
1585 make_union_element (re, e1, e2);
1587 result->initial.count++;
1588 result->initial.length += re->repcount;
1590 e1->repcount -= re->repcount;
1591 if (e1->repcount == 0)
1596 e2->repcount -= re->repcount;
1597 if (e2->repcount == 0)
1606 /* list2 already terminated, but still more elements in list1->initial.
1607 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1608 ASSERT (list2->repeated.count == 0);
1610 if (e1->presence == FCT_REQUIRED)
1612 struct format_arg *re;
1614 /* Ensure room in result->initial. */
1615 grow_initial_alloc (result);
1616 re = &result->initial.element[result->initial.count];
1617 copy_element (re, e1);
1618 re->presence = FCT_OPTIONAL;
1620 result->initial.count++;
1621 result->initial.length += 1;
1623 if (e1->repcount == 0)
1630 /* Ensure room in result->initial. */
1631 ensure_initial_alloc (result, result->initial.count + c1);
1634 struct format_arg *re;
1636 re = &result->initial.element[result->initial.count];
1637 copy_element (re, e1);
1638 result->initial.count++;
1639 result->initial.length += re->repcount;
1646 /* list1 already terminated, but still more elements in list2->initial.
1647 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1648 ASSERT (list1->repeated.count == 0);
1650 if (e2->presence == FCT_REQUIRED)
1652 struct format_arg *re;
1654 /* Ensure room in result->initial. */
1655 grow_initial_alloc (result);
1656 re = &result->initial.element[result->initial.count];
1657 copy_element (re, e2);
1658 re->presence = FCT_OPTIONAL;
1660 result->initial.count++;
1661 result->initial.length += 1;
1663 if (e2->repcount == 0)
1670 /* Ensure room in result->initial. */
1671 ensure_initial_alloc (result, result->initial.count + c2);
1674 struct format_arg *re;
1676 re = &result->initial.element[result->initial.count];
1677 copy_element (re, e2);
1678 result->initial.count++;
1679 result->initial.length += re->repcount;
1684 ASSERT (c1 == 0 && c2 == 0);
1687 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1688 /* Step 5: Elementwise union of list1->repeated, list2->repeated. */
1690 struct format_arg *e1;
1691 struct format_arg *e2;
1695 e1 = list1->repeated.element; c1 = list1->repeated.count;
1696 e2 = list2->repeated.element; c2 = list2->repeated.count;
1697 while (c1 > 0 && c2 > 0)
1699 struct format_arg *re;
1701 /* Ensure room in result->repeated. */
1702 grow_repeated_alloc (result);
1703 re = &result->repeated.element[result->repeated.count];
1704 re->repcount = MIN (e1->repcount, e2->repcount);
1706 /* Union of the argument types. */
1707 make_union_element (re, e1, e2);
1709 result->repeated.count++;
1710 result->repeated.length += re->repcount;
1712 e1->repcount -= re->repcount;
1713 if (e1->repcount == 0)
1718 e2->repcount -= re->repcount;
1719 if (e2->repcount == 0)
1725 ASSERT (c1 == 0 && c2 == 0);
1727 else if (list1->repeated.length > 0)
1729 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1730 initial segment. Just copy the repeated segment of list1. */
1733 result->repeated.count = list1->repeated.count;
1734 result->repeated.allocated = result->repeated.count;
1735 result->repeated.element =
1736 XNMALLOC (result->repeated.allocated, struct format_arg);
1737 for (i = 0; i < list1->repeated.count; i++)
1738 copy_element (&result->repeated.element[i],
1739 &list1->repeated.element[i]);
1740 result->repeated.length = list1->repeated.length;
1742 else if (list2->repeated.length > 0)
1744 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1745 initial segment. Just copy the repeated segment of list2. */
1748 result->repeated.count = list2->repeated.count;
1749 result->repeated.allocated = result->repeated.count;
1750 result->repeated.element =
1751 XNMALLOC (result->repeated.allocated, struct format_arg);
1752 for (i = 0; i < list2->repeated.count; i++)
1753 copy_element (&result->repeated.element[i],
1754 &list2->repeated.element[i]);
1755 result->repeated.length = list2->repeated.length;
1760 /* Undo the loop unfolding and unrolling done above. */
1761 normalize_outermost_list (result);
1762 VERIFY_LIST (result);
1767 /* Create the union of an argument list and the empty list. */
1768 /* Memory effects: list is freed. The result is freshly allocated. */
1769 static struct format_arg_list *
1770 make_union_with_empty_list (struct format_arg_list *list)
1772 #if 0 /* equivalent but slower */
1773 return make_union_list (list, make_empty_list ());
1777 if (list->initial.count > 0
1778 ? list->initial.element[0].presence == FCT_REQUIRED
1779 : list->repeated.count > 0
1780 && list->repeated.element[0].presence == FCT_REQUIRED)
1782 initial_splitelement (list, 1);
1783 ASSERT (list->initial.count > 0);
1784 ASSERT (list->initial.element[0].repcount == 1);
1785 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1786 list->initial.element[0].presence = FCT_OPTIONAL;
1788 /* We might need to merge list->initial.element[0] and
1789 list->initial.element[1]. */
1790 normalize_outermost_list (list);
1800 /* Create the union of two argument list constraints. NULL stands for an
1801 impossible situation, i.e. a contradiction. */
1802 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1803 if non-NULL, is freshly allocated. */
1804 static struct format_arg_list *
1805 union (struct format_arg_list *list1, struct format_arg_list *list2)
1810 return make_union_list (list1, list2);
1824 /* =========== Adding specific constraints to a format_arg_list =========== */
1827 /* Test whether arguments 0..n are required arguments in a list. */
1829 is_required (const struct format_arg_list *list, unsigned int n)
1834 /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */
1837 /* Walk the list->initial segment. */
1839 s < list->initial.count && t >= list->initial.element[s].repcount;
1840 t -= list->initial.element[s].repcount, s++)
1841 if (list->initial.element[s].presence != FCT_REQUIRED)
1847 if (s < list->initial.count)
1849 if (list->initial.element[s].presence != FCT_REQUIRED)
1855 /* Walk the list->repeated segment. */
1856 if (list->repeated.count == 0)
1860 s < list->repeated.count && t >= list->repeated.element[s].repcount;
1861 t -= list->repeated.element[s].repcount, s++)
1862 if (list->repeated.element[s].presence != FCT_REQUIRED)
1868 if (s < list->repeated.count)
1870 if (list->repeated.element[s].presence != FCT_REQUIRED)
1876 /* The list->repeated segment consists only of FCT_REQUIRED. So,
1877 regardless how many more passes through list->repeated would be
1878 needed until t becomes 0, the result is true. */
1883 /* Add a constraint to an argument list, namely that the arguments 0...n are
1884 present. NULL stands for an impossible situation, i.e. a contradiction. */
1885 /* Memory effects: list is freed. The result is freshly allocated. */
1886 static struct format_arg_list *
1887 add_required_constraint (struct format_arg_list *list, unsigned int n)
1889 unsigned int i, rest;
1896 if (list->repeated.count == 0 && list->initial.length <= n)
1898 /* list is already constrained to have at most length n.
1904 initial_splitelement (list, n + 1);
1906 for (i = 0, rest = n + 1; rest > 0; )
1908 list->initial.element[i].presence = FCT_REQUIRED;
1909 rest -= list->initial.element[i].repcount;
1919 /* Add a constraint to an argument list, namely that the argument n is
1920 never present. NULL stands for an impossible situation, i.e. a
1922 /* Memory effects: list is freed. The result is freshly allocated. */
1923 static struct format_arg_list *
1924 add_end_constraint (struct format_arg_list *list, unsigned int n)
1927 enum format_cdr_type n_presence;
1934 if (list->repeated.count == 0 && list->initial.length <= n)
1935 /* list is already constrained to have at most length n. */
1938 s = initial_splitelement (list, n);
1940 (s < list->initial.count
1941 ? /* n < list->initial.length */ list->initial.element[s].presence
1942 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1944 for (i = s; i < list->initial.count; i++)
1946 list->initial.length -= list->initial.element[i].repcount;
1947 free_element (&list->initial.element[i]);
1949 list->initial.count = s;
1951 for (i = 0; i < list->repeated.count; i++)
1952 free_element (&list->repeated.element[i]);
1953 if (list->repeated.element != NULL)
1954 free (list->repeated.element);
1955 list->repeated.element = NULL;
1956 list->repeated.allocated = 0;
1957 list->repeated.count = 0;
1958 list->repeated.length = 0;
1960 if (n_presence == FCT_REQUIRED)
1961 return backtrack_in_initial (list);
1967 /* Add a constraint to an argument list, namely that the argument n is
1968 of a given type. NULL stands for an impossible situation, i.e. a
1969 contradiction. Assumes a preceding add_required_constraint (list, n). */
1970 /* Memory effects: list is freed. The result is freshly allocated. */
1971 static struct format_arg_list *
1972 add_type_constraint (struct format_arg_list *list, unsigned int n,
1973 enum format_arg_type type)
1976 struct format_arg newconstraint;
1977 struct format_arg tmpelement;
1982 /* Through the previous add_required_constraint, we can assume
1983 list->initial.length >= n+1. */
1985 s = initial_unshare (list, n);
1987 newconstraint.presence = FCT_OPTIONAL;
1988 newconstraint.type = type;
1989 if (!make_intersected_element (&tmpelement,
1990 &list->initial.element[s], &newconstraint))
1991 return add_end_constraint (list, n);
1992 free_element (&list->initial.element[s]);
1993 list->initial.element[s].type = tmpelement.type;
1994 list->initial.element[s].list = tmpelement.list;
2002 /* Add a constraint to an argument list, namely that the argument n is
2003 of a given list type. NULL stands for an impossible situation, i.e. a
2004 contradiction. Assumes a preceding add_required_constraint (list, n). */
2005 /* Memory effects: list is freed. The result is freshly allocated. */
2006 static struct format_arg_list *
2007 add_listtype_constraint (struct format_arg_list *list, unsigned int n,
2008 enum format_arg_type type,
2009 struct format_arg_list *sublist)
2012 struct format_arg newconstraint;
2013 struct format_arg tmpelement;
2018 /* Through the previous add_required_constraint, we can assume
2019 list->initial.length >= n+1. */
2021 s = initial_unshare (list, n);
2023 newconstraint.presence = FCT_OPTIONAL;
2024 newconstraint.type = type;
2025 newconstraint.list = sublist;
2026 if (!make_intersected_element (&tmpelement,
2027 &list->initial.element[s], &newconstraint))
2028 return add_end_constraint (list, n);
2029 free_element (&list->initial.element[s]);
2030 list->initial.element[s].type = tmpelement.type;
2031 list->initial.element[s].list = tmpelement.list;
2039 /* ============= Subroutines used by the format string parser ============= */
2042 add_req_type_constraint (struct format_arg_list **listp,
2043 unsigned int position, enum format_arg_type type)
2045 *listp = add_required_constraint (*listp, position);
2046 *listp = add_type_constraint (*listp, position, type);
2051 add_req_listtype_constraint (struct format_arg_list **listp,
2052 unsigned int position, enum format_arg_type type,
2053 struct format_arg_list *sublist)
2055 *listp = add_required_constraint (*listp, position);
2056 *listp = add_listtype_constraint (*listp, position, type, sublist);
2060 /* Create an endless repeated list whose elements are lists constrained
2062 /* Memory effects: sublist is freed. The result is freshly allocated. */
2063 static struct format_arg_list *
2064 make_repeated_list_of_lists (struct format_arg_list *sublist)
2066 if (sublist == NULL)
2067 /* The list cannot have a single element. */
2068 return make_empty_list ();
2071 struct format_arg_list *listlist;
2073 listlist = XMALLOC (struct format_arg_list);
2075 listlist->initial.count = 0;
2076 listlist->initial.allocated = 0;
2077 listlist->initial.element = NULL;
2078 listlist->initial.length = 0;
2079 listlist->repeated.count = 1;
2080 listlist->repeated.allocated = 1;
2081 listlist->repeated.element = XNMALLOC (1, struct format_arg);
2082 listlist->repeated.element[0].repcount = 1;
2083 listlist->repeated.element[0].presence = FCT_OPTIONAL;
2084 listlist->repeated.element[0].type = FAT_LIST;
2085 listlist->repeated.element[0].list = sublist;
2086 listlist->repeated.length = 1;
2088 VERIFY_LIST (listlist);
2095 /* Create an endless repeated list which represents the union of a finite
2096 number of copies of L, each time shifted by period:
2100 L and (*^period L) and (*^{2 period} L)
2101 L and (*^period L) and (*^{2 period} L) and (*^{3 period} L)
2104 /* Memory effects: sublist is freed. The result is freshly allocated. */
2105 static struct format_arg_list *
2106 make_repeated_list (struct format_arg_list *sublist, unsigned int period)
2109 struct segment *srcseg;
2110 struct format_arg_list *list;
2111 unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount;
2114 VERIFY_LIST (sublist);
2116 ASSERT (period > 0);
2118 if (sublist->repeated.count == 0)
2120 /* L is a finite list. */
2122 if (sublist->initial.length < period)
2123 /* L and (*^period L) is a contradition, so we need to consider
2124 only 1 and 0 iterations. */
2125 return make_union_with_empty_list (sublist);
2127 srcseg = &sublist->initial;
2132 /* L is an infinite list. */
2133 /* p := lcm (period, period of L) */
2134 unsigned int Lp = sublist->repeated.length;
2135 unsigned int m = period / gcd (period, Lp); /* = lcm(period,Lp) / Lp */
2137 unfold_loop (sublist, m);
2140 /* Concatenate the initial and the repeated segments into a single
2142 tmp.count = sublist->initial.count + sublist->repeated.count;
2143 tmp.allocated = tmp.count;
2144 tmp.element = XNMALLOC (tmp.allocated, struct format_arg);
2145 for (i = 0; i < sublist->initial.count; i++)
2146 tmp.element[i] = sublist->initial.element[i];
2147 for (j = 0; j < sublist->repeated.count; i++, j++)
2148 tmp.element[i] = sublist->initial.element[j];
2149 tmp.length = sublist->initial.length + sublist->repeated.length;
2156 /* Example: n = 7, p = 2
2157 Let L = (A B C D E F G).
2160 L & L<<p = A B C&A D&B E&C F&D G&E
2161 L & L<<p & L<<2p = A B C&A D&B E&C&A F&D&B G&E&C
2162 ... = A B C&A D&B E&C&A F&D&B G&E&C&A
2164 Thus the result has an initial segment of length n - p and a period
2165 of p, and can be computed by floor(n/p) intersection operations.
2166 Or by a single incremental intersection operation, going from left
2169 list = XMALLOC (struct format_arg_list);
2170 list->initial.count = 0;
2171 list->initial.allocated = 0;
2172 list->initial.element = NULL;
2173 list->initial.length = 0;
2174 list->repeated.count = 0;
2175 list->repeated.allocated = 0;
2176 list->repeated.element = NULL;
2177 list->repeated.length = 0;
2180 for (i = 0; i < p; i++)
2181 list->initial.element[i] = srcseg->element[i];
2182 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2183 for (i = p, j = 0; i < n; i++, j++)
2184 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2189 i = 0, ti = 0, si = 0;
2192 unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
2194 /* Ensure room in list->initial. */
2195 grow_initial_alloc (list);
2196 copy_element (&list->initial.element[list->initial.count],
2197 &srcseg->element[si]);
2198 list->initial.element[list->initial.count].repcount = k;
2199 list->initial.count++;
2200 list->initial.length += k;
2204 if (ti == srcseg->element[si].repcount)
2211 ASSERT (list->initial.count > 0);
2212 if (list->initial.element[0].presence == FCT_REQUIRED)
2214 initial_splitelement (list, 1);
2215 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2216 ASSERT (list->initial.element[0].repcount == 1);
2217 list->initial.element[0].presence = FCT_OPTIONAL;
2220 j = 0, tj = 0, sj = 0;
2224 MIN (srcseg->element[si].repcount - ti,
2225 list->initial.element[sj].repcount - tj);
2227 /* Ensure room in list->initial. */
2228 grow_initial_alloc (list);
2229 if (!make_intersected_element (&list->initial.element[list->initial.count],
2230 &srcseg->element[si],
2231 &list->initial.element[sj]))
2233 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2235 /* Contradiction. Backtrack. */
2236 list = backtrack_in_initial (list);
2237 ASSERT (list != NULL); /* at least the empty list is valid */
2242 /* The list ends here. */
2247 list->initial.element[list->initial.count].repcount = k;
2248 list->initial.count++;
2249 list->initial.length += k;
2253 if (ti == srcseg->element[si].repcount)
2261 if (tj == list->initial.element[sj].repcount)
2268 ASSERT (list->initial.length == n);
2270 /* Add optional exit points at 0, period, 2*period etc.
2271 FIXME: Not sure this is correct in all cases. */
2272 for (i = 0; i < list->initial.length; i += period)
2274 si = initial_unshare (list, i);
2275 list->initial.element[si].presence = FCT_OPTIONAL;
2280 /* Now split off the repeated part. */
2281 splitindex = initial_splitelement (list, n - p);
2282 newcount = list->initial.count - splitindex;
2283 if (newcount > list->repeated.allocated)
2285 list->repeated.allocated = newcount;
2286 list->repeated.element = XNMALLOC (newcount, struct format_arg);
2288 for (i = splitindex, j = 0; i < n; i++, j++)
2289 list->repeated.element[j] = list->initial.element[i];
2290 list->repeated.count = newcount;
2291 list->repeated.length = p;
2292 list->initial.count = splitindex;
2293 list->initial.length = n - p;
2302 /* ================= Handling of format string directives ================= */
2304 /* Possible signatures of format directives. */
2305 static const enum format_arg_type I [1] = { FAT_INTEGER_NULL };
2306 static const enum format_arg_type II [2] = {
2307 FAT_INTEGER_NULL, FAT_INTEGER_NULL
2309 static const enum format_arg_type IIC [3] = {
2310 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2312 static const enum format_arg_type ICCI [4] = {
2313 FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL
2315 static const enum format_arg_type IIIC [4] = {
2316 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2318 static const enum format_arg_type IICCI [5] = {
2319 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL,
2322 static const enum format_arg_type IIICC [5] = {
2323 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL,
2326 static const enum format_arg_type IIIICCC [7] = {
2327 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL,
2328 FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL
2330 static const enum format_arg_type THREE [3] = {
2331 FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL,
2332 FAT_CHARACTER_INTEGER_NULL
2336 /* Check the parameters. For V params, add the constraint to the argument
2337 list. Return false and fill in *invalid_reason if the format string is
2340 check_params (struct format_arg_list **listp,
2341 unsigned int paramcount, struct param *params,
2342 unsigned int t_count, const enum format_arg_type *t_types,
2343 unsigned int directives, char **invalid_reason)
2345 unsigned int orig_paramcount = paramcount;
2346 unsigned int orig_t_count = t_count;
2348 for (; paramcount > 0 && t_count > 0;
2349 params++, paramcount--, t_types++, t_count--)
2353 case FAT_CHARACTER_INTEGER_NULL:
2355 case FAT_CHARACTER_NULL:
2356 switch (params->type)
2358 case PT_NIL: case PT_CHARACTER: case PT_V:
2360 case PT_INTEGER: case PT_ARGCOUNT:
2361 /* wrong param type */
2363 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");
2367 case FAT_INTEGER_NULL:
2368 switch (params->type)
2370 case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V:
2373 /* wrong param type */
2375 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");
2382 if (params->type == PT_V)
2384 int position = params->value;
2386 add_req_type_constraint (listp, position, *t_types);
2390 for (; paramcount > 0; params++, paramcount--)
2391 switch (params->type)
2395 case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT:
2396 /* too many params for directive */
2398 xasprintf (ngettext ("In the directive number %u, too many parameters are given; expected at most %u parameter.",
2399 "In the directive number %u, too many parameters are given; expected at most %u parameters.",
2401 directives, orig_t_count);
2404 /* Force argument to be NIL. */
2406 int position = params->value;
2409 struct format_arg_list *empty_list = make_empty_list ();
2410 add_req_listtype_constraint (listp, position,
2411 FAT_LIST, empty_list);
2412 free_list (empty_list);
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 'C': case 'c': /* FORMAT-CHARACTER */
2586 if (!check_params (&list, paramcount, params, 1, I,
2587 spec->directives, invalid_reason))
2589 FDI_SET (format - 1, FMTDIR_ERROR);
2593 || (paramcount == 1 && params[0].type == PT_NIL))
2595 add_req_type_constraint (&list, position++, FAT_CHARACTER);
2598 case 'D': case 'd': /* 22.3.2.2 FORMAT-DECIMAL */
2599 case 'B': case 'b': /* 22.3.2.3 FORMAT-BINARY */
2600 case 'O': case 'o': /* 22.3.2.4 FORMAT-OCTAL */
2601 case 'X': case 'x': /* 22.3.2.5 FORMAT-HEXADECIMAL */
2602 if (!check_params (&list, paramcount, params, 4, ICCI,
2603 spec->directives, invalid_reason))
2605 FDI_SET (format - 1, FMTDIR_ERROR);
2609 add_req_type_constraint (&list, position++, FAT_INTEGER);
2612 case 'R': case 'r': /* 22.3.2.1 FORMAT-RADIX */
2613 if (!check_params (&list, paramcount, params, 5, IICCI,
2614 spec->directives, invalid_reason))
2616 FDI_SET (format - 1, FMTDIR_ERROR);
2620 add_req_type_constraint (&list, position++, FAT_INTEGER);
2623 case 'P': case 'p': /* 22.3.8.3 FORMAT-PLURAL */
2624 if (!check_params (&list, paramcount, params, 0, NULL,
2625 spec->directives, invalid_reason))
2627 FDI_SET (format - 1, FMTDIR_ERROR);
2632 /* Go back by 1 argument. */
2637 add_req_type_constraint (&list, position++, FAT_OBJECT);
2640 case 'F': case 'f': /* 22.3.3.1 FORMAT-FIXED-FLOAT */
2641 if (!check_params (&list, paramcount, params, 5, IIICC,
2642 spec->directives, invalid_reason))
2644 FDI_SET (format - 1, FMTDIR_ERROR);
2648 add_req_type_constraint (&list, position++, FAT_REAL);
2651 case 'E': case 'e': /* 22.3.3.2 FORMAT-EXPONENTIAL-FLOAT */
2652 case 'G': case 'g': /* 22.3.3.3 FORMAT-GENERAL-FLOAT */
2653 if (!check_params (&list, paramcount, params, 7, IIIICCC,
2654 spec->directives, invalid_reason))
2656 FDI_SET (format - 1, FMTDIR_ERROR);
2660 add_req_type_constraint (&list, position++, FAT_REAL);
2663 case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */
2664 if (!check_params (&list, paramcount, params, 4, IIIC,
2665 spec->directives, invalid_reason))
2667 FDI_SET (format - 1, FMTDIR_ERROR);
2671 add_req_type_constraint (&list, position++, FAT_REAL);
2674 case 'I': case 'i': /* FORMAT-FIXED-FLOAT-COMPLEX */
2675 if (!check_params (&list, paramcount, params, 5, IIICC,
2676 spec->directives, invalid_reason))
2678 FDI_SET (format - 1, FMTDIR_ERROR);
2682 add_req_type_constraint (&list, position++, FAT_COMPLEX);
2685 case 'Y': case 'y': /* FORMAT-PRETTY */
2686 if (!check_params (&list, paramcount, params, 0, NULL,
2687 spec->directives, invalid_reason))
2689 FDI_SET (format - 1, FMTDIR_ERROR);
2693 add_req_type_constraint (&list, position++, FAT_OBJECT);
2696 case '%': /* 22.3.1.2 FORMAT-TERPRI */
2697 case '&': /* 22.3.1.3 FORMAT-FRESH-LINE */
2698 case '_': /* FORMAT-SPACE */
2699 case '/': /* FORMAT-TAB */
2700 case '|': /* 22.3.1.4 FORMAT-PAGE */
2701 case '~': /* 22.3.1.5 FORMAT-TILDE */
2702 if (!check_params (&list, paramcount, params, 1, I,
2703 spec->directives, invalid_reason))
2705 FDI_SET (format - 1, FMTDIR_ERROR);
2710 case '!': /* FORMAT-FORCE-OUTPUT */
2711 case '\n': /* 22.3.9.3 #\Newline */
2712 case 'Q': case 'q': /* FORMAT-IMPLEMENTATION */
2713 if (!check_params (&list, paramcount, params, 0, NULL,
2714 spec->directives, invalid_reason))
2716 FDI_SET (format - 1, FMTDIR_ERROR);
2721 case 'T': case 't': /* FORMAT-TABULATE */
2722 if (!check_params (&list, paramcount, params, 3, IIC,
2723 spec->directives, invalid_reason))
2725 FDI_SET (format - 1, FMTDIR_ERROR);
2730 case '*': /* 22.3.7.1 FORMAT-GOTO */
2731 if (!check_params (&list, paramcount, params, 1, I,
2732 spec->directives, invalid_reason))
2734 FDI_SET (format - 1, FMTDIR_ERROR);
2738 int n; /* value of first parameter */
2740 || (paramcount >= 1 && params[0].type == PT_NIL))
2741 n = (atsign_p ? 0 : 1);
2742 else if (paramcount >= 1 && params[0].type == PT_INTEGER)
2743 n = params[0].value;
2746 /* Unknown argument, leads to an unknown position. */
2752 /* invalid argument */
2754 xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
2755 FDI_SET (format - 1, FMTDIR_ERROR);
2760 /* Absolute goto. */
2765 /* Backward goto. */
2788 case '?': case 'K': case 'k': /* 22.3.7.6 FORMAT-INDIRECTION */
2789 if (!check_params (&list, paramcount, params, 0, NULL,
2790 spec->directives, invalid_reason))
2792 FDI_SET (format - 1, FMTDIR_ERROR);
2796 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
2802 struct format_arg_list *sublist = make_unconstrained_list ();
2803 add_req_listtype_constraint (&list, position++,
2805 free_list (sublist);
2809 case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */
2810 if (!check_params (&list, paramcount, params, 0, NULL,
2811 spec->directives, invalid_reason))
2813 FDI_SET (format - 1, FMTDIR_ERROR);
2817 *positionp = position;
2821 if (!parse_upto (formatp, positionp, listp, escapep,
2822 NULL, spec, ')', false,
2823 NULL, invalid_reason))
2825 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2831 position = *positionp;
2836 case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */
2837 if (terminator != ')')
2840 xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
2841 FDI_SET (format - 1, FMTDIR_ERROR);
2844 if (!check_params (&list, paramcount, params, 0, NULL,
2845 spec->directives, invalid_reason))
2847 FDI_SET (format - 1, FMTDIR_ERROR);
2851 *positionp = position;
2856 case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */
2857 if (atsign_p && colon_p)
2860 xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
2861 FDI_SET (format - 1, FMTDIR_ERROR);
2866 struct format_arg_list *nil_list;
2867 struct format_arg_list *union_list;
2869 if (!check_params (&list, paramcount, params, 0, NULL,
2870 spec->directives, invalid_reason))
2872 FDI_SET (format - 1, FMTDIR_ERROR);
2879 /* First alternative: argument is NIL. */
2880 nil_list = (list != NULL ? copy_list (list) : NULL);
2883 struct format_arg_list *empty_list = make_empty_list ();
2884 add_req_listtype_constraint (&nil_list, position,
2885 FAT_LIST, empty_list);
2886 free_list (empty_list);
2889 /* Second alternative: use sub-format. */
2891 int sub_position = position;
2892 struct format_arg_list *sub_list =
2893 (list != NULL ? copy_list (list) : NULL);
2894 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2895 NULL, spec, ']', false,
2896 NULL, invalid_reason))
2898 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2902 if (sub_list != NULL)
2906 if (sub_position == position + 1)
2907 /* new position is branch independent */
2908 position = position + 1;
2910 /* new position is branch dependent */
2917 position = position + 1;
2919 union_list = union (nil_list, sub_list);
2932 struct format_arg_list *union_list;
2934 if (!check_params (&list, paramcount, params, 0, NULL,
2935 spec->directives, invalid_reason))
2937 FDI_SET (format - 1, FMTDIR_ERROR);
2942 add_req_type_constraint (&list, position++, FAT_OBJECT);
2946 union_position = -2;
2949 /* First alternative. */
2951 int sub_position = position;
2952 struct format_arg_list *sub_list =
2953 (list != NULL ? copy_list (list) : NULL);
2954 int sub_separator = 0;
2957 struct format_arg_list *empty_list = make_empty_list ();
2958 add_req_listtype_constraint (&sub_list, position - 1,
2959 FAT_LIST, empty_list);
2960 free_list (empty_list);
2962 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2963 &sub_separator, spec, ']', true,
2964 NULL, invalid_reason))
2966 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2973 xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives);
2974 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2978 if (sub_list != NULL)
2979 union_position = sub_position;
2980 union_list = union (union_list, sub_list);
2983 /* Second alternative. */
2985 int sub_position = position;
2986 struct format_arg_list *sub_list =
2987 (list != NULL ? copy_list (list) : NULL);
2988 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2989 NULL, spec, ']', false,
2990 NULL, invalid_reason))
2992 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2996 if (sub_list != NULL)
2998 if (union_position == -2)
2999 union_position = sub_position;
3000 else if (sub_position < 0
3001 || sub_position != union_position)
3002 union_position = -1;
3004 union_list = union (union_list, sub_list);
3010 if (union_position != -2)
3011 position = union_position;
3020 struct format_arg_list *union_list;
3021 bool last_alternative;
3023 if (!check_params (&list, paramcount, params, 1, I,
3024 spec->directives, invalid_reason))
3026 FDI_SET (format - 1, FMTDIR_ERROR);
3030 /* If there was no first parameter, an argument is consumed. */
3032 if (!(paramcount >= 1 && params[0].type != PT_NIL))
3035 arg_position = position;
3036 add_req_type_constraint (&list, position++, FAT_OBJECT);
3042 union_position = -2;
3044 last_alternative = false;
3047 /* Next alternative. */
3048 int sub_position = position;
3049 struct format_arg_list *sub_list =
3050 (list != NULL ? copy_list (list) : NULL);
3051 int sub_separator = 0;
3052 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
3053 &sub_separator, spec, ']', !last_alternative,
3054 NULL, invalid_reason))
3056 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3060 /* If this alternative is chosen, the argument arg_position
3061 is an integer, namely the index of this alternative. */
3062 if (!last_alternative && arg_position >= 0)
3063 add_req_type_constraint (&sub_list, arg_position,
3065 if (sub_list != NULL)
3067 if (union_position == -2)
3068 union_position = sub_position;
3069 else if (sub_position < 0
3070 || sub_position != union_position)
3071 union_position = -1;
3073 union_list = union (union_list, sub_list);
3074 if (sub_separator == 2)
3075 last_alternative = true;
3079 if (!last_alternative)
3081 /* An implicit default alternative. */
3082 if (union_position == -2)
3083 union_position = position;
3084 else if (position < 0 || position != union_position)
3085 union_position = -1;
3087 union_list = union (union_list, copy_list (list));
3093 if (union_position != -2)
3094 position = union_position;
3101 case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */
3102 if (terminator != ']')
3105 xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
3106 FDI_SET (format - 1, FMTDIR_ERROR);
3109 if (!check_params (&list, paramcount, params, 0, NULL,
3110 spec->directives, invalid_reason))
3112 FDI_SET (format - 1, FMTDIR_ERROR);
3116 *positionp = position;
3121 case '{': /* 22.3.7.4 FORMAT-ITERATION */
3122 if (!check_params (&list, paramcount, params, 1, I,
3123 spec->directives, invalid_reason))
3125 FDI_SET (format - 1, FMTDIR_ERROR);
3130 int sub_position = 0;
3131 struct format_arg_list *sub_list = make_unconstrained_list ();
3132 struct format_arg_list *sub_escape = NULL;
3133 struct spec sub_spec;
3134 sub_spec.directives = 0;
3135 sub_spec.list = sub_list;
3136 if (!parse_upto (formatp, &sub_position, &sub_list, &sub_escape,
3137 NULL, &sub_spec, '}', false,
3138 NULL, invalid_reason))
3140 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3144 spec->directives += sub_spec.directives;
3146 /* If the sub-formatstring is empty, except for the terminating
3147 ~} directive, a formatstring argument is consumed. */
3148 if (*format == '~' && sub_spec.directives == 1)
3150 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
3154 /* Each iteration uses a new sublist. */
3155 struct format_arg_list *listlist;
3157 /* ~{ catches ~^. */
3158 sub_list = union (sub_list, sub_escape);
3160 listlist = make_repeated_list_of_lists (sub_list);
3162 sub_list = listlist;
3166 /* Each iteration's arguments are all concatenated in a
3168 struct format_arg_list *looplist;
3170 /* FIXME: This is far from correct. Test cases:
3176 abc~{~D~^~C~}~:*~{~S~^~D~}
3179 /* ~{ catches ~^. */
3180 sub_list = union (sub_list, sub_escape);
3182 if (sub_list == NULL)
3183 looplist = make_empty_list ();
3185 if (sub_position < 0 || sub_position == 0)
3186 /* Too hard to track the possible argument types
3187 when the iteration is performed 2 times or more.
3188 So be satisfied with the constraints of executing
3189 the iteration 1 or 0 times. */
3190 looplist = make_union_with_empty_list (sub_list);
3192 looplist = make_repeated_list (sub_list, sub_position);
3194 sub_list = looplist;
3199 /* All remaining arguments are used. */
3200 if (list != NULL && position >= 0)
3202 shift_list (sub_list, position);
3203 list = make_intersected_list (list, sub_list);
3209 /* The argument is a list. */
3211 add_req_listtype_constraint (&list, position++,
3212 FAT_LIST, sub_list);
3218 case '}': /* 22.3.7.5 FORMAT-ITERATION-END */
3219 if (terminator != '}')
3222 xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
3223 FDI_SET (format - 1, FMTDIR_ERROR);
3226 if (!check_params (&list, paramcount, params, 0, NULL,
3227 spec->directives, invalid_reason))
3229 FDI_SET (format - 1, FMTDIR_ERROR);
3233 *positionp = position;
3238 case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */
3239 if (!check_params (&list, paramcount, params, 3, THREE,
3240 spec->directives, invalid_reason))
3242 FDI_SET (format - 1, FMTDIR_ERROR);
3245 if (position >= 0 && list != NULL && is_required (list, position))
3246 /* This ~^ can never be executed. Ignore it. */
3250 struct format_arg_list *this_escape = copy_list (list);
3252 this_escape = add_end_constraint (this_escape, position);
3253 escape = union (escape, this_escape);
3256 list = add_required_constraint (list, position);
3259 case ';': /* 22.3.9.1 FORMAT-SEPARATOR */
3263 xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
3264 FDI_SET (format - 1, FMTDIR_ERROR);
3267 if (terminator == '>')
3269 if (!check_params (&list, paramcount, params, 1, I,
3270 spec->directives, invalid_reason))
3272 FDI_SET (format - 1, FMTDIR_ERROR);
3278 if (!check_params (&list, paramcount, params, 0, NULL,
3279 spec->directives, invalid_reason))
3281 FDI_SET (format - 1, FMTDIR_ERROR);
3286 *positionp = position;
3289 *separatorp = (colon_p ? 2 : 1);
3294 if (*format == '\0')
3296 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
3297 FDI_SET (format - 1, FMTDIR_ERROR);
3302 INVALID_CONVERSION_SPECIFIER (spec->directives, *format);
3303 FDI_SET (format, FMTDIR_ERROR);
3308 FDI_SET (format - 1, FMTDIR_END);
3314 *positionp = position;
3317 if (terminator != '\0')
3320 xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator);
3327 /* ============== Top level format string handling functions ============== */
3330 format_parse (const char *format, bool translated, char *fdi,
3331 char **invalid_reason)
3334 struct spec *result;
3336 struct format_arg_list *escape;
3338 spec.directives = 0;
3339 spec.list = make_unconstrained_list ();
3342 if (!parse_upto (&format, &position, &spec.list, &escape,
3343 NULL, &spec, '\0', false,
3344 fdi, invalid_reason))
3345 /* Invalid format string. */
3348 /* Catch ~^ here. */
3349 spec.list = union (spec.list, escape);
3351 if (spec.list == NULL)
3353 /* Contradictory argument type information. */
3355 xstrdup (_("The string refers to some argument in incompatible ways."));
3359 /* Normalize the result. */
3360 normalize_list (spec.list);
3362 result = XMALLOC (struct spec);
3368 format_free (void *descr)
3370 struct spec *spec = (struct spec *) descr;
3372 free_list (spec->list);
3376 format_get_number_of_directives (void *descr)
3378 struct spec *spec = (struct spec *) descr;
3380 return spec->directives;
3384 format_check (void *msgid_descr, void *msgstr_descr, bool equality,
3385 formatstring_error_logger_t error_logger,
3386 const char *pretty_msgid, const char *pretty_msgstr)
3388 struct spec *spec1 = (struct spec *) msgid_descr;
3389 struct spec *spec2 = (struct spec *) msgstr_descr;
3394 if (!equal_list (spec1->list, spec2->list))
3397 error_logger (_("format specifications in '%s' and '%s' are not equivalent"),
3398 pretty_msgid, pretty_msgstr);
3404 struct format_arg_list *intersection =
3405 make_intersected_list (copy_list (spec1->list),
3406 copy_list (spec2->list));
3408 if (!(intersection != NULL
3409 && (normalize_list (intersection),
3410 equal_list (intersection, spec2->list))))
3413 error_logger (_("format specifications in '%s' are not a subset of those in '%s'"),
3414 pretty_msgstr, pretty_msgid);
3423 struct formatstring_parser formatstring_scheme =
3427 format_get_number_of_directives,
3433 /* ============================= Testing code ============================= */
3439 /* Test program: Print the argument list specification returned by
3440 format_parse for strings read from standard input. */
3444 static void print_list (struct format_arg_list *list);
3447 print_element (struct format_arg *element)
3449 switch (element->presence)
3460 switch (element->type)
3465 case FAT_CHARACTER_INTEGER_NULL:
3468 case FAT_CHARACTER_NULL:
3474 case FAT_INTEGER_NULL:
3487 print_list (element->list);
3489 case FAT_FORMATSTRING:
3498 print_list (struct format_arg_list *list)
3504 for (i = 0; i < list->initial.count; i++)
3505 for (j = 0; j < list->initial.element[i].repcount; j++)
3509 print_element (&list->initial.element[i]);
3512 if (list->repeated.count > 0)
3515 for (i = 0; i < list->repeated.count; i++)
3516 for (j = 0; j < list->repeated.element[i].repcount; j++)
3519 print_element (&list->repeated.element[i]);
3527 format_print (void *descr)
3529 struct spec *spec = (struct spec *) descr;
3537 print_list (spec->list);
3546 size_t line_size = 0;
3548 char *invalid_reason;
3551 line_len = getline (&line, &line_size, stdin);
3554 if (line_len > 0 && line[line_len - 1] == '\n')
3555 line[--line_len] = '\0';
3557 invalid_reason = NULL;
3558 descr = format_parse (line, false, NULL, &invalid_reason);
3560 format_print (descr);
3563 printf ("%s\n", invalid_reason);
3565 free (invalid_reason);
3573 * For Emacs M-x compile
3575 * 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-scheme.c ../gnulib-lib/libgettextlib.la"