1 /* Scheme format strings.
2 Copyright (C) 2001-2007, 2009, 2015 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 bool re_is_required = re->presence == FCT_REQUIRED;
1290 append_repeated_to_initial (result);
1292 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1294 /* Contradiction. Backtrack. */
1295 result = backtrack_in_initial (result);
1300 result->repeated.count++;
1301 result->repeated.length += re->repcount;
1303 e1->repcount -= re->repcount;
1304 if (e1->repcount == 0)
1309 e2->repcount -= re->repcount;
1310 if (e2->repcount == 0)
1316 ASSERT (c1 == 0 && c2 == 0);
1324 /* Undo the loop unfolding and unrolling done above. */
1325 normalize_outermost_list (result);
1326 VERIFY_LIST (result);
1332 /* Create the intersection of an argument list and the empty list.
1333 Return NULL if the intersection is empty. */
1334 /* Memory effects: The result, if non-NULL, is freshly allocated. */
1335 static struct format_arg_list *
1336 make_intersection_with_empty_list (struct format_arg_list *list)
1338 #if 0 /* equivalent but slower */
1339 return make_intersected_list (copy_list (list), make_empty_list ());
1341 if (list->initial.count > 0
1342 ? list->initial.element[0].presence == FCT_REQUIRED
1343 : list->repeated.count > 0
1344 && list->repeated.element[0].presence == FCT_REQUIRED)
1347 return make_empty_list ();
1353 /* Create the intersection of two argument list constraints. NULL stands
1354 for an impossible situation, i.e. a contradiction. */
1355 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1356 if non-NULL, is freshly allocated. */
1357 static struct format_arg_list *
1358 intersection (struct format_arg_list *list1, struct format_arg_list *list2)
1363 return make_intersected_list (list1, list2);
1384 /* ===================== Union of two format_arg_lists ===================== */
1386 /* Create the union (i.e. alternative constraints) of two argument
1389 make_union_element (struct format_arg *re,
1390 const struct format_arg * e1,
1391 const struct format_arg * e2)
1393 /* Union of the cdr types. */
1394 if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED)
1395 re->presence = FCT_REQUIRED;
1396 else /* Either one of them is FCT_OPTIONAL. */
1397 re->presence = FCT_OPTIONAL;
1399 /* Union of the arg types. */
1400 if (e1->type == e2->type)
1402 re->type = e1->type;
1403 if (re->type == FAT_LIST)
1404 re->list = make_union_list (copy_list (e1->list),
1405 copy_list (e2->list));
1407 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
1408 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
1409 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
1411 re->type = e1->type;
1413 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
1414 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
1415 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1417 re->type = e2->type;
1419 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1421 re->type = e1->type;
1423 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1425 re->type = e2->type;
1427 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1429 re->type = e1->type;
1431 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1433 re->type = e2->type;
1435 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1437 re->type = e1->type;
1439 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1441 re->type = e2->type;
1443 else if (e1->type == FAT_COMPLEX
1444 && (e2->type == FAT_REAL || e2->type == FAT_INTEGER))
1446 re->type = e1->type;
1448 else if (e2->type == FAT_COMPLEX
1449 && (e1->type == FAT_REAL || e1->type == FAT_INTEGER))
1451 re->type = e2->type;
1453 else if (e1->type == FAT_LIST && is_empty_list (e1->list))
1455 if (e2->type == FAT_CHARACTER_INTEGER_NULL
1456 || e2->type == FAT_CHARACTER_NULL
1457 || e2->type == FAT_INTEGER_NULL)
1458 re->type = e2->type;
1459 else if (e2->type == FAT_CHARACTER)
1460 re->type = FAT_CHARACTER_NULL;
1461 else if (e2->type == FAT_INTEGER)
1462 re->type = FAT_INTEGER_NULL;
1464 re->type = FAT_OBJECT;
1466 else if (e2->type == FAT_LIST && is_empty_list (e2->list))
1468 if (e1->type == FAT_CHARACTER_INTEGER_NULL
1469 || e1->type == FAT_CHARACTER_NULL
1470 || e1->type == FAT_INTEGER_NULL)
1471 re->type = e1->type;
1472 else if (e1->type == FAT_CHARACTER)
1473 re->type = FAT_CHARACTER_NULL;
1474 else if (e1->type == FAT_INTEGER)
1475 re->type = FAT_INTEGER_NULL;
1477 re->type = FAT_OBJECT;
1479 else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL)
1480 && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL))
1482 re->type = FAT_CHARACTER_INTEGER_NULL;
1484 else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL)
1485 && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL))
1487 re->type = FAT_CHARACTER_INTEGER_NULL;
1491 /* Other union types are too hard to describe precisely. */
1492 re->type = FAT_OBJECT;
1496 /* Create the union (i.e. alternative constraints) of two argument list
1497 constraints. Free both argument lists when done. */
1498 /* Memory effects: list1 and list2 are freed. The result is freshly
1500 static struct format_arg_list *
1501 make_union_list (struct format_arg_list *list1, struct format_arg_list *list2)
1503 struct format_arg_list *result;
1505 VERIFY_LIST (list1);
1506 VERIFY_LIST (list2);
1508 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1510 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1512 unsigned int n1 = list1->repeated.length;
1513 unsigned int n2 = list2->repeated.length;
1514 unsigned int g = gcd (n1, n2);
1515 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1516 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1518 unfold_loop (list1, m1);
1519 unfold_loop (list2, m2);
1520 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1523 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1525 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1527 rotate_loop (list1, m);
1528 rotate_loop (list2, m);
1531 ASSERT (list1->initial.length == list2->initial.length);
1532 ASSERT (list1->repeated.length == list2->repeated.length);
1534 else if (list1->repeated.length > 0)
1536 /* Ensure the initial segment of the result can be computed from the
1537 initial segment of list1. */
1538 if (list2->initial.length >= list1->initial.length)
1540 rotate_loop (list1, list2->initial.length);
1541 if (list1->repeated.element[0].presence == FCT_REQUIRED)
1542 rotate_loop (list1, list1->initial.length + 1);
1545 else if (list2->repeated.length > 0)
1547 /* Ensure the initial segment of the result can be computed from the
1548 initial segment of list2. */
1549 if (list1->initial.length >= list2->initial.length)
1551 rotate_loop (list2, list1->initial.length);
1552 if (list2->repeated.element[0].presence == FCT_REQUIRED)
1553 rotate_loop (list2, list2->initial.length + 1);
1557 /* Step 3: Allocate the result. */
1558 result = XMALLOC (struct format_arg_list);
1559 result->initial.count = 0;
1560 result->initial.allocated = 0;
1561 result->initial.element = NULL;
1562 result->initial.length = 0;
1563 result->repeated.count = 0;
1564 result->repeated.allocated = 0;
1565 result->repeated.element = NULL;
1566 result->repeated.length = 0;
1568 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1570 struct format_arg *e1;
1571 struct format_arg *e2;
1575 e1 = list1->initial.element; c1 = list1->initial.count;
1576 e2 = list2->initial.element; c2 = list2->initial.count;
1577 while (c1 > 0 && c2 > 0)
1579 struct format_arg *re;
1581 /* Ensure room in result->initial. */
1582 grow_initial_alloc (result);
1583 re = &result->initial.element[result->initial.count];
1584 re->repcount = MIN (e1->repcount, e2->repcount);
1586 /* Union of the argument types. */
1587 make_union_element (re, e1, e2);
1589 result->initial.count++;
1590 result->initial.length += re->repcount;
1592 e1->repcount -= re->repcount;
1593 if (e1->repcount == 0)
1598 e2->repcount -= re->repcount;
1599 if (e2->repcount == 0)
1608 /* list2 already terminated, but still more elements in list1->initial.
1609 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1610 ASSERT (list2->repeated.count == 0);
1612 if (e1->presence == FCT_REQUIRED)
1614 struct format_arg *re;
1616 /* Ensure room in result->initial. */
1617 grow_initial_alloc (result);
1618 re = &result->initial.element[result->initial.count];
1619 copy_element (re, e1);
1620 re->presence = FCT_OPTIONAL;
1622 result->initial.count++;
1623 result->initial.length += 1;
1625 if (e1->repcount == 0)
1632 /* Ensure room in result->initial. */
1633 ensure_initial_alloc (result, result->initial.count + c1);
1636 struct format_arg *re;
1638 re = &result->initial.element[result->initial.count];
1639 copy_element (re, e1);
1640 result->initial.count++;
1641 result->initial.length += re->repcount;
1648 /* list1 already terminated, but still more elements in list2->initial.
1649 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1650 ASSERT (list1->repeated.count == 0);
1652 if (e2->presence == FCT_REQUIRED)
1654 struct format_arg *re;
1656 /* Ensure room in result->initial. */
1657 grow_initial_alloc (result);
1658 re = &result->initial.element[result->initial.count];
1659 copy_element (re, e2);
1660 re->presence = FCT_OPTIONAL;
1662 result->initial.count++;
1663 result->initial.length += 1;
1665 if (e2->repcount == 0)
1672 /* Ensure room in result->initial. */
1673 ensure_initial_alloc (result, result->initial.count + c2);
1676 struct format_arg *re;
1678 re = &result->initial.element[result->initial.count];
1679 copy_element (re, e2);
1680 result->initial.count++;
1681 result->initial.length += re->repcount;
1686 ASSERT (c1 == 0 && c2 == 0);
1689 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1690 /* Step 5: Elementwise union of list1->repeated, list2->repeated. */
1692 struct format_arg *e1;
1693 struct format_arg *e2;
1697 e1 = list1->repeated.element; c1 = list1->repeated.count;
1698 e2 = list2->repeated.element; c2 = list2->repeated.count;
1699 while (c1 > 0 && c2 > 0)
1701 struct format_arg *re;
1703 /* Ensure room in result->repeated. */
1704 grow_repeated_alloc (result);
1705 re = &result->repeated.element[result->repeated.count];
1706 re->repcount = MIN (e1->repcount, e2->repcount);
1708 /* Union of the argument types. */
1709 make_union_element (re, e1, e2);
1711 result->repeated.count++;
1712 result->repeated.length += re->repcount;
1714 e1->repcount -= re->repcount;
1715 if (e1->repcount == 0)
1720 e2->repcount -= re->repcount;
1721 if (e2->repcount == 0)
1727 ASSERT (c1 == 0 && c2 == 0);
1729 else if (list1->repeated.length > 0)
1731 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1732 initial segment. Just copy the repeated segment of list1. */
1735 result->repeated.count = list1->repeated.count;
1736 result->repeated.allocated = result->repeated.count;
1737 result->repeated.element =
1738 XNMALLOC (result->repeated.allocated, struct format_arg);
1739 for (i = 0; i < list1->repeated.count; i++)
1740 copy_element (&result->repeated.element[i],
1741 &list1->repeated.element[i]);
1742 result->repeated.length = list1->repeated.length;
1744 else if (list2->repeated.length > 0)
1746 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1747 initial segment. Just copy the repeated segment of list2. */
1750 result->repeated.count = list2->repeated.count;
1751 result->repeated.allocated = result->repeated.count;
1752 result->repeated.element =
1753 XNMALLOC (result->repeated.allocated, struct format_arg);
1754 for (i = 0; i < list2->repeated.count; i++)
1755 copy_element (&result->repeated.element[i],
1756 &list2->repeated.element[i]);
1757 result->repeated.length = list2->repeated.length;
1762 /* Undo the loop unfolding and unrolling done above. */
1763 normalize_outermost_list (result);
1764 VERIFY_LIST (result);
1769 /* Create the union of an argument list and the empty list. */
1770 /* Memory effects: list is freed. The result is freshly allocated. */
1771 static struct format_arg_list *
1772 make_union_with_empty_list (struct format_arg_list *list)
1774 #if 0 /* equivalent but slower */
1775 return make_union_list (list, make_empty_list ());
1779 if (list->initial.count > 0
1780 ? list->initial.element[0].presence == FCT_REQUIRED
1781 : list->repeated.count > 0
1782 && list->repeated.element[0].presence == FCT_REQUIRED)
1784 initial_splitelement (list, 1);
1785 ASSERT (list->initial.count > 0);
1786 ASSERT (list->initial.element[0].repcount == 1);
1787 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1788 list->initial.element[0].presence = FCT_OPTIONAL;
1790 /* We might need to merge list->initial.element[0] and
1791 list->initial.element[1]. */
1792 normalize_outermost_list (list);
1802 /* Create the union of two argument list constraints. NULL stands for an
1803 impossible situation, i.e. a contradiction. */
1804 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1805 if non-NULL, is freshly allocated. */
1806 static struct format_arg_list *
1807 union (struct format_arg_list *list1, struct format_arg_list *list2)
1812 return make_union_list (list1, list2);
1826 /* =========== Adding specific constraints to a format_arg_list =========== */
1829 /* Test whether arguments 0..n are required arguments in a list. */
1831 is_required (const struct format_arg_list *list, unsigned int n)
1836 /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */
1839 /* Walk the list->initial segment. */
1841 s < list->initial.count && t >= list->initial.element[s].repcount;
1842 t -= list->initial.element[s].repcount, s++)
1843 if (list->initial.element[s].presence != FCT_REQUIRED)
1849 if (s < list->initial.count)
1851 if (list->initial.element[s].presence != FCT_REQUIRED)
1857 /* Walk the list->repeated segment. */
1858 if (list->repeated.count == 0)
1862 s < list->repeated.count && t >= list->repeated.element[s].repcount;
1863 t -= list->repeated.element[s].repcount, s++)
1864 if (list->repeated.element[s].presence != FCT_REQUIRED)
1870 if (s < list->repeated.count)
1872 if (list->repeated.element[s].presence != FCT_REQUIRED)
1878 /* The list->repeated segment consists only of FCT_REQUIRED. So,
1879 regardless how many more passes through list->repeated would be
1880 needed until t becomes 0, the result is true. */
1885 /* Add a constraint to an argument list, namely that the arguments 0...n are
1886 present. NULL stands for an impossible situation, i.e. a contradiction. */
1887 /* Memory effects: list is freed. The result is freshly allocated. */
1888 static struct format_arg_list *
1889 add_required_constraint (struct format_arg_list *list, unsigned int n)
1891 unsigned int i, rest;
1898 if (list->repeated.count == 0 && list->initial.length <= n)
1900 /* list is already constrained to have at most length n.
1906 initial_splitelement (list, n + 1);
1908 for (i = 0, rest = n + 1; rest > 0; )
1910 list->initial.element[i].presence = FCT_REQUIRED;
1911 rest -= list->initial.element[i].repcount;
1921 /* Add a constraint to an argument list, namely that the argument n is
1922 never present. NULL stands for an impossible situation, i.e. a
1924 /* Memory effects: list is freed. The result is freshly allocated. */
1925 static struct format_arg_list *
1926 add_end_constraint (struct format_arg_list *list, unsigned int n)
1929 enum format_cdr_type n_presence;
1936 if (list->repeated.count == 0 && list->initial.length <= n)
1937 /* list is already constrained to have at most length n. */
1940 s = initial_splitelement (list, n);
1942 (s < list->initial.count
1943 ? /* n < list->initial.length */ list->initial.element[s].presence
1944 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1946 for (i = s; i < list->initial.count; i++)
1948 list->initial.length -= list->initial.element[i].repcount;
1949 free_element (&list->initial.element[i]);
1951 list->initial.count = s;
1953 for (i = 0; i < list->repeated.count; i++)
1954 free_element (&list->repeated.element[i]);
1955 if (list->repeated.element != NULL)
1956 free (list->repeated.element);
1957 list->repeated.element = NULL;
1958 list->repeated.allocated = 0;
1959 list->repeated.count = 0;
1960 list->repeated.length = 0;
1962 if (n_presence == FCT_REQUIRED)
1963 return backtrack_in_initial (list);
1969 /* Add a constraint to an argument list, namely that the argument n is
1970 of a given type. NULL stands for an impossible situation, i.e. a
1971 contradiction. Assumes a preceding add_required_constraint (list, n). */
1972 /* Memory effects: list is freed. The result is freshly allocated. */
1973 static struct format_arg_list *
1974 add_type_constraint (struct format_arg_list *list, unsigned int n,
1975 enum format_arg_type type)
1978 struct format_arg newconstraint;
1979 struct format_arg tmpelement;
1984 /* Through the previous add_required_constraint, we can assume
1985 list->initial.length >= n+1. */
1987 s = initial_unshare (list, n);
1989 newconstraint.presence = FCT_OPTIONAL;
1990 newconstraint.type = type;
1991 if (!make_intersected_element (&tmpelement,
1992 &list->initial.element[s], &newconstraint))
1993 return add_end_constraint (list, n);
1994 free_element (&list->initial.element[s]);
1995 list->initial.element[s].type = tmpelement.type;
1996 list->initial.element[s].list = tmpelement.list;
2004 /* Add a constraint to an argument list, namely that the argument n is
2005 of a given list type. NULL stands for an impossible situation, i.e. a
2006 contradiction. Assumes a preceding add_required_constraint (list, n). */
2007 /* Memory effects: list is freed. The result is freshly allocated. */
2008 static struct format_arg_list *
2009 add_listtype_constraint (struct format_arg_list *list, unsigned int n,
2010 enum format_arg_type type,
2011 struct format_arg_list *sublist)
2014 struct format_arg newconstraint;
2015 struct format_arg tmpelement;
2020 /* Through the previous add_required_constraint, we can assume
2021 list->initial.length >= n+1. */
2023 s = initial_unshare (list, n);
2025 newconstraint.presence = FCT_OPTIONAL;
2026 newconstraint.type = type;
2027 newconstraint.list = sublist;
2028 if (!make_intersected_element (&tmpelement,
2029 &list->initial.element[s], &newconstraint))
2030 return add_end_constraint (list, n);
2031 free_element (&list->initial.element[s]);
2032 list->initial.element[s].type = tmpelement.type;
2033 list->initial.element[s].list = tmpelement.list;
2041 /* ============= Subroutines used by the format string parser ============= */
2044 add_req_type_constraint (struct format_arg_list **listp,
2045 unsigned int position, enum format_arg_type type)
2047 *listp = add_required_constraint (*listp, position);
2048 *listp = add_type_constraint (*listp, position, type);
2053 add_req_listtype_constraint (struct format_arg_list **listp,
2054 unsigned int position, enum format_arg_type type,
2055 struct format_arg_list *sublist)
2057 *listp = add_required_constraint (*listp, position);
2058 *listp = add_listtype_constraint (*listp, position, type, sublist);
2062 /* Create an endless repeated list whose elements are lists constrained
2064 /* Memory effects: sublist is freed. The result is freshly allocated. */
2065 static struct format_arg_list *
2066 make_repeated_list_of_lists (struct format_arg_list *sublist)
2068 if (sublist == NULL)
2069 /* The list cannot have a single element. */
2070 return make_empty_list ();
2073 struct format_arg_list *listlist;
2075 listlist = XMALLOC (struct format_arg_list);
2077 listlist->initial.count = 0;
2078 listlist->initial.allocated = 0;
2079 listlist->initial.element = NULL;
2080 listlist->initial.length = 0;
2081 listlist->repeated.count = 1;
2082 listlist->repeated.allocated = 1;
2083 listlist->repeated.element = XNMALLOC (1, struct format_arg);
2084 listlist->repeated.element[0].repcount = 1;
2085 listlist->repeated.element[0].presence = FCT_OPTIONAL;
2086 listlist->repeated.element[0].type = FAT_LIST;
2087 listlist->repeated.element[0].list = sublist;
2088 listlist->repeated.length = 1;
2090 VERIFY_LIST (listlist);
2097 /* Create an endless repeated list which represents the union of a finite
2098 number of copies of L, each time shifted by period:
2102 L and (*^period L) and (*^{2 period} L)
2103 L and (*^period L) and (*^{2 period} L) and (*^{3 period} L)
2106 /* Memory effects: sublist is freed. The result is freshly allocated. */
2107 static struct format_arg_list *
2108 make_repeated_list (struct format_arg_list *sublist, unsigned int period)
2111 struct segment *srcseg;
2112 struct format_arg_list *list;
2113 unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount;
2116 VERIFY_LIST (sublist);
2118 ASSERT (period > 0);
2120 if (sublist->repeated.count == 0)
2122 /* L is a finite list. */
2124 if (sublist->initial.length < period)
2125 /* L and (*^period L) is a contradition, so we need to consider
2126 only 1 and 0 iterations. */
2127 return make_union_with_empty_list (sublist);
2129 srcseg = &sublist->initial;
2134 /* L is an infinite list. */
2135 /* p := lcm (period, period of L) */
2136 unsigned int Lp = sublist->repeated.length;
2137 unsigned int m = period / gcd (period, Lp); /* = lcm(period,Lp) / Lp */
2139 unfold_loop (sublist, m);
2142 /* Concatenate the initial and the repeated segments into a single
2144 tmp.count = sublist->initial.count + sublist->repeated.count;
2145 tmp.allocated = tmp.count;
2146 tmp.element = XNMALLOC (tmp.allocated, struct format_arg);
2147 for (i = 0; i < sublist->initial.count; i++)
2148 tmp.element[i] = sublist->initial.element[i];
2149 for (j = 0; j < sublist->repeated.count; i++, j++)
2150 tmp.element[i] = sublist->initial.element[j];
2151 tmp.length = sublist->initial.length + sublist->repeated.length;
2158 /* Example: n = 7, p = 2
2159 Let L = (A B C D E F G).
2162 L & L<<p = A B C&A D&B E&C F&D G&E
2163 L & L<<p & L<<2p = A B C&A D&B E&C&A F&D&B G&E&C
2164 ... = A B C&A D&B E&C&A F&D&B G&E&C&A
2166 Thus the result has an initial segment of length n - p and a period
2167 of p, and can be computed by floor(n/p) intersection operations.
2168 Or by a single incremental intersection operation, going from left
2171 list = XMALLOC (struct format_arg_list);
2172 list->initial.count = 0;
2173 list->initial.allocated = 0;
2174 list->initial.element = NULL;
2175 list->initial.length = 0;
2176 list->repeated.count = 0;
2177 list->repeated.allocated = 0;
2178 list->repeated.element = NULL;
2179 list->repeated.length = 0;
2182 for (i = 0; i < p; i++)
2183 list->initial.element[i] = srcseg->element[i];
2184 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2185 for (i = p, j = 0; i < n; i++, j++)
2186 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2191 i = 0, ti = 0, si = 0;
2194 unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
2196 /* Ensure room in list->initial. */
2197 grow_initial_alloc (list);
2198 copy_element (&list->initial.element[list->initial.count],
2199 &srcseg->element[si]);
2200 list->initial.element[list->initial.count].repcount = k;
2201 list->initial.count++;
2202 list->initial.length += k;
2206 if (ti == srcseg->element[si].repcount)
2213 ASSERT (list->initial.count > 0);
2214 if (list->initial.element[0].presence == FCT_REQUIRED)
2216 initial_splitelement (list, 1);
2217 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2218 ASSERT (list->initial.element[0].repcount == 1);
2219 list->initial.element[0].presence = FCT_OPTIONAL;
2222 j = 0, tj = 0, sj = 0;
2226 MIN (srcseg->element[si].repcount - ti,
2227 list->initial.element[sj].repcount - tj);
2229 /* Ensure room in list->initial. */
2230 grow_initial_alloc (list);
2231 if (!make_intersected_element (&list->initial.element[list->initial.count],
2232 &srcseg->element[si],
2233 &list->initial.element[sj]))
2235 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2237 /* Contradiction. Backtrack. */
2238 list = backtrack_in_initial (list);
2239 ASSERT (list != NULL); /* at least the empty list is valid */
2244 /* The list ends here. */
2249 list->initial.element[list->initial.count].repcount = k;
2250 list->initial.count++;
2251 list->initial.length += k;
2255 if (ti == srcseg->element[si].repcount)
2263 if (tj == list->initial.element[sj].repcount)
2270 ASSERT (list->initial.length == n);
2272 /* Add optional exit points at 0, period, 2*period etc.
2273 FIXME: Not sure this is correct in all cases. */
2274 for (i = 0; i < list->initial.length; i += period)
2276 si = initial_unshare (list, i);
2277 list->initial.element[si].presence = FCT_OPTIONAL;
2282 /* Now split off the repeated part. */
2283 splitindex = initial_splitelement (list, n - p);
2284 newcount = list->initial.count - splitindex;
2285 if (newcount > list->repeated.allocated)
2287 list->repeated.allocated = newcount;
2288 list->repeated.element = XNMALLOC (newcount, struct format_arg);
2290 for (i = splitindex, j = 0; i < n; i++, j++)
2291 list->repeated.element[j] = list->initial.element[i];
2292 list->repeated.count = newcount;
2293 list->repeated.length = p;
2294 list->initial.count = splitindex;
2295 list->initial.length = n - p;
2304 /* ================= Handling of format string directives ================= */
2306 /* Possible signatures of format directives. */
2307 static const enum format_arg_type I [1] = { FAT_INTEGER_NULL };
2308 static const enum format_arg_type II [2] = {
2309 FAT_INTEGER_NULL, FAT_INTEGER_NULL
2311 static const enum format_arg_type IIC [3] = {
2312 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2314 static const enum format_arg_type ICCI [4] = {
2315 FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL
2317 static const enum format_arg_type IIIC [4] = {
2318 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2320 static const enum format_arg_type IICCI [5] = {
2321 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL,
2324 static const enum format_arg_type IIICC [5] = {
2325 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL,
2328 static const enum format_arg_type IIIICCC [7] = {
2329 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL,
2330 FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL
2332 static const enum format_arg_type THREE [3] = {
2333 FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL,
2334 FAT_CHARACTER_INTEGER_NULL
2338 /* Check the parameters. For V params, add the constraint to the argument
2339 list. Return false and fill in *invalid_reason if the format string is
2342 check_params (struct format_arg_list **listp,
2343 unsigned int paramcount, struct param *params,
2344 unsigned int t_count, const enum format_arg_type *t_types,
2345 unsigned int directives, char **invalid_reason)
2347 unsigned int orig_paramcount = paramcount;
2348 unsigned int orig_t_count = t_count;
2350 for (; paramcount > 0 && t_count > 0;
2351 params++, paramcount--, t_types++, t_count--)
2355 case FAT_CHARACTER_INTEGER_NULL:
2357 case FAT_CHARACTER_NULL:
2358 switch (params->type)
2360 case PT_NIL: case PT_CHARACTER: case PT_V:
2362 case PT_INTEGER: case PT_ARGCOUNT:
2363 /* wrong param type */
2365 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");
2369 case FAT_INTEGER_NULL:
2370 switch (params->type)
2372 case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V:
2375 /* wrong param type */
2377 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");
2384 if (params->type == PT_V)
2386 int position = params->value;
2388 add_req_type_constraint (listp, position, *t_types);
2392 for (; paramcount > 0; params++, paramcount--)
2393 switch (params->type)
2397 case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT:
2398 /* too many params for directive */
2400 xasprintf (ngettext ("In the directive number %u, too many parameters are given; expected at most %u parameter.",
2401 "In the directive number %u, too many parameters are given; expected at most %u parameters.",
2403 directives, orig_t_count);
2406 /* Force argument to be NIL. */
2408 int position = params->value;
2411 struct format_arg_list *empty_list = make_empty_list ();
2412 add_req_listtype_constraint (listp, position,
2413 FAT_LIST, empty_list);
2414 free_list (empty_list);
2424 /* ======================= The format string parser ======================= */
2426 /* Parse a piece of format string, until the matching terminating format
2427 directive is encountered.
2428 format is the remainder of the format string.
2429 position is the position in this argument list, if known, or -1 if unknown.
2430 list represents the argument list constraints at the current parse point.
2431 NULL stands for a contradiction.
2432 escape represents the union of the argument list constraints at all the
2433 currently pending FORMAT-UP-AND-OUT points. NULL stands for a contradiction
2435 All four are updated upon valid return.
2436 *separatorp is set to true if the parse terminated due to a ~; separator,
2437 more precisely to 2 if with colon, or to 1 if without colon.
2438 spec is the global struct spec.
2439 terminator is the directive that terminates this parse.
2440 separator specifies if ~; separators are allowed.
2441 fdi is an array to be filled with format directive indicators, or NULL.
2442 If the format string is invalid, false is returned and *invalid_reason is
2443 set to an error message explaining why. */
2445 parse_upto (const char **formatp,
2446 int *positionp, struct format_arg_list **listp,
2447 struct format_arg_list **escapep, int *separatorp,
2448 struct spec *spec, char terminator, bool separator,
2449 char *fdi, char **invalid_reason)
2451 const char *format = *formatp;
2452 const char *const format_start = format;
2453 int position = *positionp;
2454 struct format_arg_list *list = *listp;
2455 struct format_arg_list *escape = *escapep;
2457 for (; *format != '\0'; )
2458 if (*format++ == '~')
2460 bool colon_p = false;
2461 bool atsign_p = false;
2462 unsigned int paramcount = 0;
2463 struct param *params = NULL;
2465 FDI_SET (format - 1, FMTDIR_START);
2467 /* Count number of directives. */
2470 /* Parse parameters. */
2473 enum param_type type = PT_NIL;
2476 if (c_isdigit (*format))
2481 value = 10 * value + (*format - '0');
2484 while (c_isdigit (*format));
2486 else if (*format == '+' || *format == '-')
2488 bool negative = (*format == '-');
2491 if (!c_isdigit (*format))
2493 if (*format == '\0')
2495 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2496 FDI_SET (format - 1, FMTDIR_ERROR);
2501 xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]);
2502 FDI_SET (format, FMTDIR_ERROR);
2508 value = 10 * value + (*format - '0');
2511 while (c_isdigit (*format));
2515 else if (*format == '\'')
2517 type = PT_CHARACTER;
2519 if (*format == '\0')
2521 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2522 FDI_SET (format - 1, FMTDIR_ERROR);
2527 else if (*format == 'V' || *format == 'v')
2532 /* Consumes an argument. */
2536 else if (*format == '#')
2544 xrealloc (params, (paramcount + 1) * sizeof (struct param));
2545 params[paramcount].type = type;
2546 params[paramcount].value = value;
2555 /* Parse modifiers. */
2563 else if (*format == '@')
2572 /* Parse directive. */
2575 case 'A': case 'a': /* 22.3.4.1 FORMAT-ASCII */
2576 case 'S': case 's': /* 22.3.4.2 FORMAT-S-EXPRESSION */
2577 if (!check_params (&list, paramcount, params, 4, IIIC,
2578 spec->directives, invalid_reason))
2580 FDI_SET (format - 1, FMTDIR_ERROR);
2584 add_req_type_constraint (&list, position++, FAT_OBJECT);
2587 case 'C': case 'c': /* FORMAT-CHARACTER */
2588 if (!check_params (&list, paramcount, params, 1, I,
2589 spec->directives, invalid_reason))
2591 FDI_SET (format - 1, FMTDIR_ERROR);
2595 || (paramcount == 1 && params[0].type == PT_NIL))
2597 add_req_type_constraint (&list, position++, FAT_CHARACTER);
2600 case 'D': case 'd': /* 22.3.2.2 FORMAT-DECIMAL */
2601 case 'B': case 'b': /* 22.3.2.3 FORMAT-BINARY */
2602 case 'O': case 'o': /* 22.3.2.4 FORMAT-OCTAL */
2603 case 'X': case 'x': /* 22.3.2.5 FORMAT-HEXADECIMAL */
2604 if (!check_params (&list, paramcount, params, 4, ICCI,
2605 spec->directives, invalid_reason))
2607 FDI_SET (format - 1, FMTDIR_ERROR);
2611 add_req_type_constraint (&list, position++, FAT_INTEGER);
2614 case 'R': case 'r': /* 22.3.2.1 FORMAT-RADIX */
2615 if (!check_params (&list, paramcount, params, 5, IICCI,
2616 spec->directives, invalid_reason))
2618 FDI_SET (format - 1, FMTDIR_ERROR);
2622 add_req_type_constraint (&list, position++, FAT_INTEGER);
2625 case 'P': case 'p': /* 22.3.8.3 FORMAT-PLURAL */
2626 if (!check_params (&list, paramcount, params, 0, NULL,
2627 spec->directives, invalid_reason))
2629 FDI_SET (format - 1, FMTDIR_ERROR);
2634 /* Go back by 1 argument. */
2639 add_req_type_constraint (&list, position++, FAT_OBJECT);
2642 case 'F': case 'f': /* 22.3.3.1 FORMAT-FIXED-FLOAT */
2643 if (!check_params (&list, paramcount, params, 5, IIICC,
2644 spec->directives, invalid_reason))
2646 FDI_SET (format - 1, FMTDIR_ERROR);
2650 add_req_type_constraint (&list, position++, FAT_REAL);
2653 case 'E': case 'e': /* 22.3.3.2 FORMAT-EXPONENTIAL-FLOAT */
2654 case 'G': case 'g': /* 22.3.3.3 FORMAT-GENERAL-FLOAT */
2655 if (!check_params (&list, paramcount, params, 7, IIIICCC,
2656 spec->directives, invalid_reason))
2658 FDI_SET (format - 1, FMTDIR_ERROR);
2662 add_req_type_constraint (&list, position++, FAT_REAL);
2665 case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */
2666 if (!check_params (&list, paramcount, params, 4, IIIC,
2667 spec->directives, invalid_reason))
2669 FDI_SET (format - 1, FMTDIR_ERROR);
2673 add_req_type_constraint (&list, position++, FAT_REAL);
2676 case 'I': case 'i': /* FORMAT-FIXED-FLOAT-COMPLEX */
2677 if (!check_params (&list, paramcount, params, 5, IIICC,
2678 spec->directives, invalid_reason))
2680 FDI_SET (format - 1, FMTDIR_ERROR);
2684 add_req_type_constraint (&list, position++, FAT_COMPLEX);
2687 case 'Y': case 'y': /* FORMAT-PRETTY */
2688 if (!check_params (&list, paramcount, params, 0, NULL,
2689 spec->directives, invalid_reason))
2691 FDI_SET (format - 1, FMTDIR_ERROR);
2695 add_req_type_constraint (&list, position++, FAT_OBJECT);
2698 case '%': /* 22.3.1.2 FORMAT-TERPRI */
2699 case '&': /* 22.3.1.3 FORMAT-FRESH-LINE */
2700 case '_': /* FORMAT-SPACE */
2701 case '/': /* FORMAT-TAB */
2702 case '|': /* 22.3.1.4 FORMAT-PAGE */
2703 case '~': /* 22.3.1.5 FORMAT-TILDE */
2704 if (!check_params (&list, paramcount, params, 1, I,
2705 spec->directives, invalid_reason))
2707 FDI_SET (format - 1, FMTDIR_ERROR);
2712 case '!': /* FORMAT-FORCE-OUTPUT */
2713 case '\n': /* 22.3.9.3 #\Newline */
2714 case 'Q': case 'q': /* FORMAT-IMPLEMENTATION */
2715 if (!check_params (&list, paramcount, params, 0, NULL,
2716 spec->directives, invalid_reason))
2718 FDI_SET (format - 1, FMTDIR_ERROR);
2723 case 'T': case 't': /* FORMAT-TABULATE */
2724 if (!check_params (&list, paramcount, params, 3, IIC,
2725 spec->directives, invalid_reason))
2727 FDI_SET (format - 1, FMTDIR_ERROR);
2732 case '*': /* 22.3.7.1 FORMAT-GOTO */
2733 if (!check_params (&list, paramcount, params, 1, I,
2734 spec->directives, invalid_reason))
2736 FDI_SET (format - 1, FMTDIR_ERROR);
2740 int n; /* value of first parameter */
2742 || (paramcount >= 1 && params[0].type == PT_NIL))
2743 n = (atsign_p ? 0 : 1);
2744 else if (paramcount >= 1 && params[0].type == PT_INTEGER)
2745 n = params[0].value;
2748 /* Unknown argument, leads to an unknown position. */
2754 /* invalid argument */
2756 xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
2757 FDI_SET (format - 1, FMTDIR_ERROR);
2762 /* Absolute goto. */
2767 /* Backward goto. */
2790 case '?': case 'K': case 'k': /* 22.3.7.6 FORMAT-INDIRECTION */
2791 if (!check_params (&list, paramcount, params, 0, NULL,
2792 spec->directives, invalid_reason))
2794 FDI_SET (format - 1, FMTDIR_ERROR);
2798 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
2804 struct format_arg_list *sublist = make_unconstrained_list ();
2805 add_req_listtype_constraint (&list, position++,
2807 free_list (sublist);
2811 case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */
2812 if (!check_params (&list, paramcount, params, 0, NULL,
2813 spec->directives, invalid_reason))
2815 FDI_SET (format - 1, FMTDIR_ERROR);
2819 *positionp = position;
2823 if (!parse_upto (formatp, positionp, listp, escapep,
2824 NULL, spec, ')', false,
2825 NULL, invalid_reason))
2827 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2833 position = *positionp;
2838 case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */
2839 if (terminator != ')')
2842 xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
2843 FDI_SET (format - 1, FMTDIR_ERROR);
2846 if (!check_params (&list, paramcount, params, 0, NULL,
2847 spec->directives, invalid_reason))
2849 FDI_SET (format - 1, FMTDIR_ERROR);
2853 *positionp = position;
2858 case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */
2859 if (atsign_p && colon_p)
2862 xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
2863 FDI_SET (format - 1, FMTDIR_ERROR);
2868 struct format_arg_list *nil_list;
2869 struct format_arg_list *union_list;
2871 if (!check_params (&list, paramcount, params, 0, NULL,
2872 spec->directives, invalid_reason))
2874 FDI_SET (format - 1, FMTDIR_ERROR);
2881 /* First alternative: argument is NIL. */
2882 nil_list = (list != NULL ? copy_list (list) : NULL);
2885 struct format_arg_list *empty_list = make_empty_list ();
2886 add_req_listtype_constraint (&nil_list, position,
2887 FAT_LIST, empty_list);
2888 free_list (empty_list);
2891 /* Second alternative: use sub-format. */
2893 int sub_position = position;
2894 struct format_arg_list *sub_list =
2895 (list != NULL ? copy_list (list) : NULL);
2896 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2897 NULL, spec, ']', false,
2898 NULL, invalid_reason))
2900 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2904 if (sub_list != NULL)
2908 if (sub_position == position + 1)
2909 /* new position is branch independent */
2910 position = position + 1;
2912 /* new position is branch dependent */
2919 position = position + 1;
2921 union_list = union (nil_list, sub_list);
2934 struct format_arg_list *union_list;
2936 if (!check_params (&list, paramcount, params, 0, NULL,
2937 spec->directives, invalid_reason))
2939 FDI_SET (format - 1, FMTDIR_ERROR);
2944 add_req_type_constraint (&list, position++, FAT_OBJECT);
2948 union_position = -2;
2951 /* First alternative. */
2953 int sub_position = position;
2954 struct format_arg_list *sub_list =
2955 (list != NULL ? copy_list (list) : NULL);
2956 int sub_separator = 0;
2959 struct format_arg_list *empty_list = make_empty_list ();
2960 add_req_listtype_constraint (&sub_list, position - 1,
2961 FAT_LIST, empty_list);
2962 free_list (empty_list);
2964 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2965 &sub_separator, spec, ']', true,
2966 NULL, invalid_reason))
2968 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2975 xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives);
2976 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2980 if (sub_list != NULL)
2981 union_position = sub_position;
2982 union_list = union (union_list, sub_list);
2985 /* Second alternative. */
2987 int sub_position = position;
2988 struct format_arg_list *sub_list =
2989 (list != NULL ? copy_list (list) : NULL);
2990 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2991 NULL, spec, ']', false,
2992 NULL, invalid_reason))
2994 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2998 if (sub_list != NULL)
3000 if (union_position == -2)
3001 union_position = sub_position;
3002 else if (sub_position < 0
3003 || sub_position != union_position)
3004 union_position = -1;
3006 union_list = union (union_list, sub_list);
3012 if (union_position != -2)
3013 position = union_position;
3022 struct format_arg_list *union_list;
3023 bool last_alternative;
3025 if (!check_params (&list, paramcount, params, 1, I,
3026 spec->directives, invalid_reason))
3028 FDI_SET (format - 1, FMTDIR_ERROR);
3032 /* If there was no first parameter, an argument is consumed. */
3034 if (!(paramcount >= 1 && params[0].type != PT_NIL))
3037 arg_position = position;
3038 add_req_type_constraint (&list, position++, FAT_OBJECT);
3044 union_position = -2;
3046 last_alternative = false;
3049 /* Next alternative. */
3050 int sub_position = position;
3051 struct format_arg_list *sub_list =
3052 (list != NULL ? copy_list (list) : NULL);
3053 int sub_separator = 0;
3054 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
3055 &sub_separator, spec, ']', !last_alternative,
3056 NULL, invalid_reason))
3058 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3062 /* If this alternative is chosen, the argument arg_position
3063 is an integer, namely the index of this alternative. */
3064 if (!last_alternative && arg_position >= 0)
3065 add_req_type_constraint (&sub_list, arg_position,
3067 if (sub_list != NULL)
3069 if (union_position == -2)
3070 union_position = sub_position;
3071 else if (sub_position < 0
3072 || sub_position != union_position)
3073 union_position = -1;
3075 union_list = union (union_list, sub_list);
3076 if (sub_separator == 2)
3077 last_alternative = true;
3081 if (!last_alternative)
3083 /* An implicit default alternative. */
3084 if (union_position == -2)
3085 union_position = position;
3086 else if (position < 0 || position != union_position)
3087 union_position = -1;
3089 union_list = union (union_list, copy_list (list));
3095 if (union_position != -2)
3096 position = union_position;
3103 case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */
3104 if (terminator != ']')
3107 xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
3108 FDI_SET (format - 1, FMTDIR_ERROR);
3111 if (!check_params (&list, paramcount, params, 0, NULL,
3112 spec->directives, invalid_reason))
3114 FDI_SET (format - 1, FMTDIR_ERROR);
3118 *positionp = position;
3123 case '{': /* 22.3.7.4 FORMAT-ITERATION */
3124 if (!check_params (&list, paramcount, params, 1, I,
3125 spec->directives, invalid_reason))
3127 FDI_SET (format - 1, FMTDIR_ERROR);
3132 int sub_position = 0;
3133 struct format_arg_list *sub_list = make_unconstrained_list ();
3134 struct format_arg_list *sub_escape = NULL;
3135 struct spec sub_spec;
3136 sub_spec.directives = 0;
3137 sub_spec.list = sub_list;
3138 if (!parse_upto (formatp, &sub_position, &sub_list, &sub_escape,
3139 NULL, &sub_spec, '}', false,
3140 NULL, invalid_reason))
3142 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3146 spec->directives += sub_spec.directives;
3148 /* If the sub-formatstring is empty, except for the terminating
3149 ~} directive, a formatstring argument is consumed. */
3150 if (*format == '~' && sub_spec.directives == 1)
3152 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
3156 /* Each iteration uses a new sublist. */
3157 struct format_arg_list *listlist;
3159 /* ~{ catches ~^. */
3160 sub_list = union (sub_list, sub_escape);
3162 listlist = make_repeated_list_of_lists (sub_list);
3164 sub_list = listlist;
3168 /* Each iteration's arguments are all concatenated in a
3170 struct format_arg_list *looplist;
3172 /* FIXME: This is far from correct. Test cases:
3178 abc~{~D~^~C~}~:*~{~S~^~D~}
3181 /* ~{ catches ~^. */
3182 sub_list = union (sub_list, sub_escape);
3184 if (sub_list == NULL)
3185 looplist = make_empty_list ();
3187 if (sub_position < 0 || sub_position == 0)
3188 /* Too hard to track the possible argument types
3189 when the iteration is performed 2 times or more.
3190 So be satisfied with the constraints of executing
3191 the iteration 1 or 0 times. */
3192 looplist = make_union_with_empty_list (sub_list);
3194 looplist = make_repeated_list (sub_list, sub_position);
3196 sub_list = looplist;
3201 /* All remaining arguments are used. */
3202 if (list != NULL && position >= 0)
3204 shift_list (sub_list, position);
3205 list = make_intersected_list (list, sub_list);
3211 /* The argument is a list. */
3213 add_req_listtype_constraint (&list, position++,
3214 FAT_LIST, sub_list);
3220 case '}': /* 22.3.7.5 FORMAT-ITERATION-END */
3221 if (terminator != '}')
3224 xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
3225 FDI_SET (format - 1, FMTDIR_ERROR);
3228 if (!check_params (&list, paramcount, params, 0, NULL,
3229 spec->directives, invalid_reason))
3231 FDI_SET (format - 1, FMTDIR_ERROR);
3235 *positionp = position;
3240 case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */
3241 if (!check_params (&list, paramcount, params, 3, THREE,
3242 spec->directives, invalid_reason))
3244 FDI_SET (format - 1, FMTDIR_ERROR);
3247 if (position >= 0 && list != NULL && is_required (list, position))
3248 /* This ~^ can never be executed. Ignore it. */
3252 struct format_arg_list *this_escape = copy_list (list);
3254 this_escape = add_end_constraint (this_escape, position);
3255 escape = union (escape, this_escape);
3258 list = add_required_constraint (list, position);
3261 case ';': /* 22.3.9.1 FORMAT-SEPARATOR */
3265 xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
3266 FDI_SET (format - 1, FMTDIR_ERROR);
3269 if (terminator == '>')
3271 if (!check_params (&list, paramcount, params, 1, I,
3272 spec->directives, invalid_reason))
3274 FDI_SET (format - 1, FMTDIR_ERROR);
3280 if (!check_params (&list, paramcount, params, 0, NULL,
3281 spec->directives, invalid_reason))
3283 FDI_SET (format - 1, FMTDIR_ERROR);
3288 *positionp = position;
3291 *separatorp = (colon_p ? 2 : 1);
3296 if (*format == '\0')
3298 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
3299 FDI_SET (format - 1, FMTDIR_ERROR);
3304 INVALID_CONVERSION_SPECIFIER (spec->directives, *format);
3305 FDI_SET (format, FMTDIR_ERROR);
3310 FDI_SET (format - 1, FMTDIR_END);
3316 *positionp = position;
3319 if (terminator != '\0')
3322 xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator);
3329 /* ============== Top level format string handling functions ============== */
3332 format_parse (const char *format, bool translated, char *fdi,
3333 char **invalid_reason)
3336 struct spec *result;
3338 struct format_arg_list *escape;
3340 spec.directives = 0;
3341 spec.list = make_unconstrained_list ();
3344 if (!parse_upto (&format, &position, &spec.list, &escape,
3345 NULL, &spec, '\0', false,
3346 fdi, invalid_reason))
3347 /* Invalid format string. */
3350 /* Catch ~^ here. */
3351 spec.list = union (spec.list, escape);
3353 if (spec.list == NULL)
3355 /* Contradictory argument type information. */
3357 xstrdup (_("The string refers to some argument in incompatible ways."));
3361 /* Normalize the result. */
3362 normalize_list (spec.list);
3364 result = XMALLOC (struct spec);
3370 format_free (void *descr)
3372 struct spec *spec = (struct spec *) descr;
3374 free_list (spec->list);
3378 format_get_number_of_directives (void *descr)
3380 struct spec *spec = (struct spec *) descr;
3382 return spec->directives;
3386 format_check (void *msgid_descr, void *msgstr_descr, bool equality,
3387 formatstring_error_logger_t error_logger,
3388 const char *pretty_msgid, const char *pretty_msgstr)
3390 struct spec *spec1 = (struct spec *) msgid_descr;
3391 struct spec *spec2 = (struct spec *) msgstr_descr;
3396 if (!equal_list (spec1->list, spec2->list))
3399 error_logger (_("format specifications in '%s' and '%s' are not equivalent"),
3400 pretty_msgid, pretty_msgstr);
3406 struct format_arg_list *intersection =
3407 make_intersected_list (copy_list (spec1->list),
3408 copy_list (spec2->list));
3410 if (!(intersection != NULL
3411 && (normalize_list (intersection),
3412 equal_list (intersection, spec2->list))))
3415 error_logger (_("format specifications in '%s' are not a subset of those in '%s'"),
3416 pretty_msgstr, pretty_msgid);
3425 struct formatstring_parser formatstring_scheme =
3429 format_get_number_of_directives,
3435 /* ============================= Testing code ============================= */
3441 /* Test program: Print the argument list specification returned by
3442 format_parse for strings read from standard input. */
3446 static void print_list (struct format_arg_list *list);
3449 print_element (struct format_arg *element)
3451 switch (element->presence)
3462 switch (element->type)
3467 case FAT_CHARACTER_INTEGER_NULL:
3470 case FAT_CHARACTER_NULL:
3476 case FAT_INTEGER_NULL:
3489 print_list (element->list);
3491 case FAT_FORMATSTRING:
3500 print_list (struct format_arg_list *list)
3506 for (i = 0; i < list->initial.count; i++)
3507 for (j = 0; j < list->initial.element[i].repcount; j++)
3511 print_element (&list->initial.element[i]);
3514 if (list->repeated.count > 0)
3517 for (i = 0; i < list->repeated.count; i++)
3518 for (j = 0; j < list->repeated.element[i].repcount; j++)
3521 print_element (&list->repeated.element[i]);
3529 format_print (void *descr)
3531 struct spec *spec = (struct spec *) descr;
3539 print_list (spec->list);
3548 size_t line_size = 0;
3550 char *invalid_reason;
3553 line_len = getline (&line, &line_size, stdin);
3556 if (line_len > 0 && line[line_len - 1] == '\n')
3557 line[--line_len] = '\0';
3559 invalid_reason = NULL;
3560 descr = format_parse (line, false, NULL, &invalid_reason);
3562 format_print (descr);
3565 printf ("%s\n", invalid_reason);
3567 free (invalid_reason);
3575 * For Emacs M-x compile
3577 * 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"