1 /* Scheme format strings.
2 Copyright (C) 2001-2007, 2009, 2014, 2019 Free Software Foundation, Inc.
3 Written by Bruno Haible <haible@clisp.cons.org>, 2001.
4
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.
9
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.
14
15 You should have received a copy of the GNU General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 #ifdef HAVE_CONFIG_H
19 # include <config.h>
20 #endif
21
22 #include <stdbool.h>
23 #include <stdlib.h>
24
25 #include "format.h"
26 #include "c-ctype.h"
27 #include "gcd.h"
28 #include "xalloc.h"
29 #include "xvasprintf.h"
30 #include "format-invalid.h"
31 #include "minmax.h"
32 #include "error.h"
33 #include "error-progname.h"
34 #include "gettext.h"
35
36 #define _(str) gettext (str)
37
38
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)
42
43
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. */
47
48 /* Data structure describing format string derived constraints for an
49 argument list. It is a recursive list structure. Structure sharing
50 is not allowed. */
51
52 enum format_cdr_type
53 {
54 FCT_REQUIRED, /* The format argument list cannot end before this argument. */
55 FCT_OPTIONAL /* The format argument list may end before this argument. */
56 };
57
58 enum format_arg_type
59 {
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. */
70 };
71
72 struct format_arg
73 {
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
78 this argument? */
79 enum format_arg_type type; /* Possible values for this argument. */
80 struct format_arg_list *list; /* For FAT_LIST: List elements. */
81 };
82
83 struct segment
84 {
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. */
90 };
91
92 struct format_arg_list
93 {
94 /* The constraints for the potentially infinite argument list are assumed
95 to become ultimately periodic. (Too complicated argument lists without
96 a-priori period, like
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. */
103
104 struct segment initial; /* Initial arguments segment. */
105 struct segment repeated; /* Endlessly repeated segment. */
106 };
107
108 struct spec
109 {
110 unsigned int directives;
111 struct format_arg_list *list;
112 };
113
114
115 /* Parameter for a directive. */
116 enum param_type
117 {
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 */
123 };
124
125 struct param
126 {
127 enum param_type type;
128 int value; /* for PT_INTEGER: the value, for PT_V: the position */
129 };
130
131
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);
147
148
149 /* ======================= Verify a format_arg_list ======================= */
150
151 /* Verify some invariants. */
152 static void
verify_element(const struct format_arg * e)153 verify_element (const struct format_arg * e)
154 {
155 ASSERT (e->repcount > 0);
156 if (e->type == FAT_LIST)
157 verify_list (e->list);
158 }
159
160 /* Verify some invariants. */
161 /* Memory effects: none. */
162 static void
verify_list(const struct format_arg_list * list)163 verify_list (const struct format_arg_list *list)
164 {
165 unsigned int i;
166 unsigned int total_repcount;
167
168 ASSERT (list->initial.count <= list->initial.allocated);
169 total_repcount = 0;
170 for (i = 0; i < list->initial.count; i++)
171 {
172 verify_element (&list->initial.element[i]);
173 total_repcount += list->initial.element[i].repcount;
174 }
175 ASSERT (total_repcount == list->initial.length);
176
177 ASSERT (list->repeated.count <= list->repeated.allocated);
178 total_repcount = 0;
179 for (i = 0; i < list->repeated.count; i++)
180 {
181 verify_element (&list->repeated.element[i]);
182 total_repcount += list->repeated.element[i].repcount;
183 }
184 ASSERT (total_repcount == list->repeated.length);
185 }
186
187 #define VERIFY_LIST(list) verify_list (list)
188
189
190 /* ======================== Free a format_arg_list ======================== */
191
192 /* Free the data belonging to an argument list element. */
193 static inline void
free_element(struct format_arg * element)194 free_element (struct format_arg *element)
195 {
196 if (element->type == FAT_LIST)
197 free_list (element->list);
198 }
199
200 /* Free an argument list. */
201 /* Memory effects: Frees list. */
202 static void
free_list(struct format_arg_list * list)203 free_list (struct format_arg_list *list)
204 {
205 unsigned int i;
206
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);
211
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);
216 }
217
218
219 /* ======================== Copy a format_arg_list ======================== */
220
221 /* Copy the data belonging to an argument list element. */
222 static inline void
copy_element(struct format_arg * newelement,const struct format_arg * oldelement)223 copy_element (struct format_arg *newelement,
224 const struct format_arg *oldelement)
225 {
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);
231 }
232
233 /* Copy an argument list. */
234 /* Memory effects: Freshly allocated result. */
235 static struct format_arg_list *
copy_list(const struct format_arg_list * list)236 copy_list (const struct format_arg_list *list)
237 {
238 struct format_arg_list *newlist;
239 unsigned int length;
240 unsigned int i;
241
242 VERIFY_LIST (list);
243
244 newlist = XMALLOC (struct format_arg_list);
245
246 newlist->initial.count = newlist->initial.allocated = list->initial.count;
247 length = 0;
248 if (list->initial.count == 0)
249 newlist->initial.element = NULL;
250 else
251 {
252 newlist->initial.element =
253 XNMALLOC (newlist->initial.allocated, struct format_arg);
254 for (i = 0; i < list->initial.count; i++)
255 {
256 copy_element (&newlist->initial.element[i],
257 &list->initial.element[i]);
258 length += list->initial.element[i].repcount;
259 }
260 }
261 ASSERT (length == list->initial.length);
262 newlist->initial.length = length;
263
264 newlist->repeated.count = newlist->repeated.allocated = list->repeated.count;
265 length = 0;
266 if (list->repeated.count == 0)
267 newlist->repeated.element = NULL;
268 else
269 {
270 newlist->repeated.element =
271 XNMALLOC (newlist->repeated.allocated, struct format_arg);
272 for (i = 0; i < list->repeated.count; i++)
273 {
274 copy_element (&newlist->repeated.element[i],
275 &list->repeated.element[i]);
276 length += list->repeated.element[i].repcount;
277 }
278 }
279 ASSERT (length == list->repeated.length);
280 newlist->repeated.length = length;
281
282 VERIFY_LIST (newlist);
283
284 return newlist;
285 }
286
287
288 /* ===================== Compare two format_arg_lists ===================== */
289
290 /* Tests whether two normalized argument constraints are equivalent,
291 ignoring the repcount. */
292 static bool
equal_element(const struct format_arg * e1,const struct format_arg * e2)293 equal_element (const struct format_arg * e1, const struct format_arg * e2)
294 {
295 return (e1->presence == e2->presence
296 && e1->type == e2->type
297 && (e1->type == FAT_LIST ? equal_list (e1->list, e2->list) : true));
298 }
299
300 /* Tests whether two normalized argument list constraints are equivalent. */
301 /* Memory effects: none. */
302 static bool
equal_list(const struct format_arg_list * list1,const struct format_arg_list * list2)303 equal_list (const struct format_arg_list *list1,
304 const struct format_arg_list *list2)
305 {
306 unsigned int n, i;
307
308 VERIFY_LIST (list1);
309 VERIFY_LIST (list2);
310
311 n = list1->initial.count;
312 if (n != list2->initial.count)
313 return false;
314 for (i = 0; i < n; i++)
315 {
316 const struct format_arg * e1 = &list1->initial.element[i];
317 const struct format_arg * e2 = &list2->initial.element[i];
318
319 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
320 return false;
321 }
322
323 n = list1->repeated.count;
324 if (n != list2->repeated.count)
325 return false;
326 for (i = 0; i < n; i++)
327 {
328 const struct format_arg * e1 = &list1->repeated.element[i];
329 const struct format_arg * e2 = &list2->repeated.element[i];
330
331 if (!(e1->repcount == e2->repcount && equal_element (e1, e2)))
332 return false;
333 }
334
335 return true;
336 }
337
338
339 /* ===================== Incremental memory allocation ===================== */
340
341 /* Ensure list->initial.allocated >= newcount. */
342 static inline void
ensure_initial_alloc(struct format_arg_list * list,unsigned int newcount)343 ensure_initial_alloc (struct format_arg_list *list, unsigned int newcount)
344 {
345 if (newcount > list->initial.allocated)
346 {
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));
353 }
354 }
355
356 /* Ensure list->initial.allocated > list->initial.count. */
357 static inline void
grow_initial_alloc(struct format_arg_list * list)358 grow_initial_alloc (struct format_arg_list *list)
359 {
360 if (list->initial.count >= list->initial.allocated)
361 {
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));
368 }
369 }
370
371 /* Ensure list->repeated.allocated >= newcount. */
372 static inline void
ensure_repeated_alloc(struct format_arg_list * list,unsigned int newcount)373 ensure_repeated_alloc (struct format_arg_list *list, unsigned int newcount)
374 {
375 if (newcount > list->repeated.allocated)
376 {
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));
383 }
384 }
385
386 /* Ensure list->repeated.allocated > list->repeated.count. */
387 static inline void
grow_repeated_alloc(struct format_arg_list * list)388 grow_repeated_alloc (struct format_arg_list *list)
389 {
390 if (list->repeated.count >= list->repeated.allocated)
391 {
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));
398 }
399 }
400
401
402 /* ====================== Normalize a format_arg_list ====================== */
403
404 /* Normalize an argument list constraint, assuming all sublists are already
405 normalized. */
406 /* Memory effects: Destructively modifies list. */
407 static void
normalize_outermost_list(struct format_arg_list * list)408 normalize_outermost_list (struct format_arg_list *list)
409 {
410 unsigned int n, i, j;
411
412 /* Step 1: Combine adjacent elements.
413 Copy from i to j, keeping 0 <= j <= i. */
414
415 n = list->initial.count;
416 for (i = j = 0; i < n; i++)
417 if (j > 0
418 && equal_element (&list->initial.element[i],
419 &list->initial.element[j-1]))
420 {
421 list->initial.element[j-1].repcount +=
422 list->initial.element[i].repcount;
423 free_element (&list->initial.element[i]);
424 }
425 else
426 {
427 if (j < i)
428 list->initial.element[j] = list->initial.element[i];
429 j++;
430 }
431 list->initial.count = j;
432
433 n = list->repeated.count;
434 for (i = j = 0; i < n; i++)
435 if (j > 0
436 && equal_element (&list->repeated.element[i],
437 &list->repeated.element[j-1]))
438 {
439 list->repeated.element[j-1].repcount +=
440 list->repeated.element[i].repcount;
441 free_element (&list->repeated.element[i]);
442 }
443 else
444 {
445 if (j < i)
446 list->repeated.element[j] = list->repeated.element[i];
447 j++;
448 }
449 list->repeated.count = j;
450
451 /* Nothing more to be done if the loop segment is empty. */
452 if (list->repeated.count > 0)
453 {
454 unsigned int m, repcount0_extra;
455
456 /* Step 2: Reduce the loop period. */
457 n = list->repeated.count;
458 repcount0_extra = 0;
459 if (n > 1
460 && equal_element (&list->repeated.element[0],
461 &list->repeated.element[n-1]))
462 {
463 repcount0_extra = list->repeated.element[n-1].repcount;
464 n--;
465 }
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++)
469 if ((n % m) == 0)
470 {
471 /* m is a divisor of n. Try to reduce the loop period to n. */
472 bool ok = true;
473
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])))
480 {
481 ok = false;
482 break;
483 }
484 if (ok)
485 {
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;
492 break;
493 }
494 }
495
496 /* Step 3: Roll as much as possible of the initial segment's tail
497 into the loop. */
498 if (list->repeated.count == 1)
499 {
500 if (list->initial.count > 0
501 && equal_element (&list->initial.element[list->initial.count-1],
502 &list->repeated.element[0]))
503 {
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--;
510 }
511 }
512 else
513 {
514 while (list->initial.count > 0
515 && equal_element (&list->initial.element[list->initial.count-1],
516 &list->repeated.element[list->repeated.count-1]))
517 {
518 unsigned int moved_repcount =
519 MIN (list->initial.element[list->initial.count-1].repcount,
520 list->repeated.element[list->repeated.count-1].repcount);
521
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;
526 else
527 {
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;
536 }
537
538 /* Remove the element from the end of list->repeated. */
539 list->repeated.element[list->repeated.count-1].repcount -=
540 moved_repcount;
541 if (list->repeated.element[list->repeated.count-1].repcount == 0)
542 {
543 free_element (&list->repeated.element[list->repeated.count-1]);
544 list->repeated.count--;
545 }
546
547 /* Remove the element from the end of list->initial. */
548 list->initial.element[list->initial.count-1].repcount -=
549 moved_repcount;
550 if (list->initial.element[list->initial.count-1].repcount == 0)
551 {
552 free_element (&list->initial.element[list->initial.count-1]);
553 list->initial.count--;
554 }
555 list->initial.length -= moved_repcount;
556 }
557 }
558 }
559 }
560
561 /* Normalize an argument list constraint. */
562 /* Memory effects: Destructively modifies list. */
563 static void
normalize_list(struct format_arg_list * list)564 normalize_list (struct format_arg_list *list)
565 {
566 unsigned int n, i;
567
568 VERIFY_LIST (list);
569
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);
579
580 /* Then normalize the top level list. */
581 normalize_outermost_list (list);
582
583 VERIFY_LIST (list);
584 }
585
586
587 /* ===================== Unconstrained and empty lists ===================== */
588
589 /* It's easier to allocate these on demand, than to be careful not to
590 accidentally modify statically allocated lists. */
591
592
593 /* Create an unconstrained argument list. */
594 /* Memory effects: Freshly allocated result. */
595 static struct format_arg_list *
make_unconstrained_list()596 make_unconstrained_list ()
597 {
598 struct format_arg_list *list;
599
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;
612
613 VERIFY_LIST (list);
614
615 return list;
616 }
617
618
619 /* Create an empty argument list. */
620 /* Memory effects: Freshly allocated result. */
621 static struct format_arg_list *
make_empty_list()622 make_empty_list ()
623 {
624 struct format_arg_list *list;
625
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;
635
636 VERIFY_LIST (list);
637
638 return list;
639 }
640
641
642 /* Test for an empty list. */
643 /* Memory effects: none. */
644 static bool
is_empty_list(const struct format_arg_list * list)645 is_empty_list (const struct format_arg_list *list)
646 {
647 return (list->initial.count == 0 && list->repeated.count == 0);
648 }
649
650
651 /* ======================== format_arg_list surgery ======================== */
652
653 /* Unfold list->repeated m times, where m >= 1.
654 Assumes list->repeated.count > 0. */
655 /* Memory effects: list is destructively modified. */
656 static void
unfold_loop(struct format_arg_list * list,unsigned int m)657 unfold_loop (struct format_arg_list *list, unsigned int m)
658 {
659 unsigned int i, j, k;
660
661 if (m > 1)
662 {
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;
671 }
672 }
673
674 /* Ensure list->initial.length := m, where m >= list->initial.length.
675 Assumes list->repeated.count > 0. */
676 /* Memory effects: list is destructively modified. */
677 static void
rotate_loop(struct format_arg_list * list,unsigned int m)678 rotate_loop (struct format_arg_list *list, unsigned int m)
679 {
680 if (m == list->initial.length)
681 return;
682
683 if (list->repeated.count == 1)
684 {
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;
688
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;
696 }
697 else
698 {
699 unsigned int n = list->repeated.length;
700
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;
704
705 /* Determine how many entries of list->repeated are needed for
706 length r. */
707 unsigned int s;
708 unsigned int t;
709
710 for (t = r, s = 0;
711 s < list->repeated.count && t >= list->repeated.element[s].repcount;
712 t -= list->repeated.element[s].repcount, s++)
713 ;
714
715 /* s must be < list->repeated.count, otherwise r would have been >= n. */
716 ASSERT (s < list->repeated.count);
717
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]. */
722 {
723 unsigned int i, j, k, newcount;
724
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]);
734 if (t > 0)
735 {
736 copy_element (&list->initial.element[i],
737 &list->repeated.element[j]);
738 list->initial.element[i].repcount = t;
739 i++;
740 }
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
748 = m.
749 */
750 list->initial.length = m;
751 }
752
753 /* And rotate list->repeated. */
754 if (r > 0)
755 {
756 unsigned int i, j, oldcount, newcount;
757 struct format_arg *newelement;
758
759 oldcount = list->repeated.count;
760 newcount = list->repeated.count + (t > 0 ? 1 : 0);
761 newelement = XNMALLOC (newcount, struct format_arg);
762 i = 0;
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];
767 if (t > 0)
768 {
769 copy_element (&newelement[oldcount], &newelement[0]);
770 newelement[0].repcount -= t;
771 newelement[oldcount].repcount = t;
772 }
773 free (list->repeated.element);
774 list->repeated.element = newelement;
775 }
776 }
777 }
778
779
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. */
784 static unsigned int
initial_splitelement(struct format_arg_list * list,unsigned int n)785 initial_splitelement (struct format_arg_list *list, unsigned int n)
786 {
787 unsigned int s;
788 unsigned int t;
789 unsigned int oldrepcount;
790 unsigned int newcount;
791 unsigned int i;
792
793 VERIFY_LIST (list);
794
795 if (n > list->initial.length)
796 {
797 ASSERT (list->repeated.count > 0);
798 rotate_loop (list, n);
799 ASSERT (n <= list->initial.length);
800 }
801
802 /* Determine how many entries of list->initial need to be skipped. */
803 for (t = n, s = 0;
804 s < list->initial.count && t >= list->initial.element[s].repcount;
805 t -= list->initial.element[s].repcount, s++)
806 ;
807
808 if (t == 0)
809 return s;
810
811 ASSERT (s < list->initial.count);
812
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;
823
824 VERIFY_LIST (list);
825
826 return s+1;
827 }
828
829
830 /* Ensure index n in the initial segment is not shared. Return its index. */
831 /* Memory effects: list is destructively modified. */
832 static unsigned int
initial_unshare(struct format_arg_list * list,unsigned int n)833 initial_unshare (struct format_arg_list *list, unsigned int n)
834 {
835 /* This does the same side effects as
836 initial_splitelement (list, n);
837 initial_splitelement (list, n + 1);
838 */
839 unsigned int s;
840 unsigned int t;
841
842 VERIFY_LIST (list);
843
844 if (n >= list->initial.length)
845 {
846 ASSERT (list->repeated.count > 0);
847 rotate_loop (list, n + 1);
848 ASSERT (n < list->initial.length);
849 }
850
851 /* Determine how many entries of list->initial need to be skipped. */
852 for (t = n, s = 0;
853 s < list->initial.count && t >= list->initial.element[s].repcount;
854 t -= list->initial.element[s].repcount, s++)
855 ;
856
857 /* s must be < list->initial.count. */
858 ASSERT (s < list->initial.count);
859
860 if (list->initial.element[s].repcount > 1)
861 {
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)
869 {
870 unsigned int i;
871
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]);
875 if (t == 0)
876 {
877 list->initial.element[s].repcount = 1;
878 list->initial.element[s+1].repcount = oldrepcount - 1;
879 }
880 else
881 {
882 list->initial.element[s].repcount = oldrepcount - 1;
883 list->initial.element[s+1].repcount = 1;
884 }
885 }
886 else
887 {
888 unsigned int i;
889
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;
897 }
898 list->initial.count = newcount;
899 if (t > 0)
900 s++;
901 }
902
903 /* Now the entry for index n has repcount 1. */
904 ASSERT (list->initial.element[s].repcount == 1);
905
906 VERIFY_LIST (list);
907
908 return s;
909 }
910
911
912 /* Add n unconstrained elements at the front of the list. */
913 /* Memory effects: list is destructively modified. */
914 static void
shift_list(struct format_arg_list * list,unsigned int n)915 shift_list (struct format_arg_list *list, unsigned int n)
916 {
917 VERIFY_LIST (list);
918
919 if (n > 0)
920 {
921 unsigned int i;
922
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;
931
932 normalize_outermost_list (list);
933 }
934
935 VERIFY_LIST (list);
936 }
937
938
939 /* ================= Intersection of two format_arg_lists ================= */
940
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. */
945 static bool
make_intersected_element(struct format_arg * re,const struct format_arg * e1,const struct format_arg * e2)946 make_intersected_element (struct format_arg *re,
947 const struct format_arg * e1,
948 const struct format_arg * e2)
949 {
950 /* Intersect the cdr types. */
951 if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED)
952 re->presence = FCT_REQUIRED;
953 else
954 re->presence = FCT_OPTIONAL;
955
956 /* Intersect the arg types. */
957 if (e1->type == FAT_OBJECT)
958 {
959 re->type = e2->type;
960 if (re->type == FAT_LIST)
961 re->list = copy_list (e2->list);
962 }
963 else if (e2->type == FAT_OBJECT)
964 {
965 re->type = e1->type;
966 if (re->type == FAT_LIST)
967 re->list = copy_list (e1->list);
968 }
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))
973 {
974 re->type = e1->type;
975 re->list = make_intersection_with_empty_list (e1->list);
976 if (re->list == NULL)
977 return false;
978 }
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))
983 {
984 re->type = e2->type;
985 re->list = make_intersection_with_empty_list (e2->list);
986 if (re->list == NULL)
987 return false;
988 }
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))
992 {
993 re->type = e2->type;
994 }
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))
998 {
999 re->type = e1->type;
1000 }
1001 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1002 {
1003 re->type = e2->type;
1004 }
1005 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1006 {
1007 re->type = e1->type;
1008 }
1009 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1010 {
1011 re->type = e2->type;
1012 }
1013 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1014 {
1015 re->type = e1->type;
1016 }
1017 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1018 {
1019 re->type = e2->type;
1020 }
1021 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1022 {
1023 re->type = e1->type;
1024 }
1025 else if (e1->type == FAT_COMPLEX
1026 && (e2->type == FAT_REAL || e2->type == FAT_INTEGER))
1027 {
1028 re->type = e2->type;
1029 }
1030 else if (e2->type == FAT_COMPLEX
1031 && (e1->type == FAT_REAL || e1->type == FAT_INTEGER))
1032 {
1033 re->type = e1->type;
1034 }
1035 else if (e1->type == e2->type)
1036 {
1037 re->type = e1->type;
1038 if (re->type == FAT_LIST)
1039 {
1040 re->list = make_intersected_list (copy_list (e1->list),
1041 copy_list (e2->list));
1042 if (re->list == NULL)
1043 return false;
1044 }
1045 }
1046 else
1047 /* Each of FAT_CHARACTER, FAT_INTEGER, FAT_LIST, FAT_FORMATSTRING
1048 matches only itself. Contradiction. */
1049 return false;
1050
1051 return true;
1052 }
1053
1054 /* Append list->repeated to list->initial, and clear list->repeated. */
1055 /* Memory effects: list is destructively modified. */
1056 static void
append_repeated_to_initial(struct format_arg_list * list)1057 append_repeated_to_initial (struct format_arg_list *list)
1058 {
1059 if (list->repeated.count > 0)
1060 {
1061 /* Move list->repeated over to list->initial. */
1062 unsigned int i, j, newcount;
1063
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;
1076 }
1077 }
1078
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,
1084 list is freed. */
1085 static struct format_arg_list *
backtrack_in_initial(struct format_arg_list * list)1086 backtrack_in_initial (struct format_arg_list *list)
1087 {
1088 ASSERT (list->repeated.count == 0);
1089
1090 while (list->initial.count > 0)
1091 {
1092 unsigned int i = list->initial.count - 1;
1093 if (list->initial.element[i].presence == FCT_REQUIRED)
1094 {
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;
1099 }
1100 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1101 {
1102 /* The list must end here. */
1103 list->initial.length--;
1104 if (list->initial.element[i].repcount > 1)
1105 list->initial.element[i].repcount--;
1106 else
1107 {
1108 free_element (&list->initial.element[i]);
1109 list->initial.count = i;
1110 }
1111 VERIFY_LIST (list);
1112 return list;
1113 }
1114 }
1115
1116 free_list (list);
1117 return NULL;
1118 }
1119
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 *
make_intersected_list(struct format_arg_list * list1,struct format_arg_list * list2)1126 make_intersected_list (struct format_arg_list *list1,
1127 struct format_arg_list *list2)
1128 {
1129 struct format_arg_list *result;
1130
1131 VERIFY_LIST (list1);
1132 VERIFY_LIST (list2);
1133
1134 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1135 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1136 {
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 */
1142
1143 unfold_loop (list1, m1);
1144 unfold_loop (list2, m2);
1145 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1146 }
1147
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. */
1153 {
1154 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1155
1156 if (list1->repeated.length > 0)
1157 rotate_loop (list1, m);
1158 if (list2->repeated.length > 0)
1159 rotate_loop (list2, m);
1160 }
1161
1162 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1163 {
1164 ASSERT (list1->initial.length == list2->initial.length);
1165 ASSERT (list1->repeated.length == list2->repeated.length);
1166 }
1167
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;
1178
1179 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1180 {
1181 struct format_arg *e1;
1182 struct format_arg *e2;
1183 unsigned int c1;
1184 unsigned int c2;
1185
1186 e1 = list1->initial.element; c1 = list1->initial.count;
1187 e2 = list2->initial.element; c2 = list2->initial.count;
1188 while (c1 > 0 && c2 > 0)
1189 {
1190 struct format_arg *re;
1191
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);
1196
1197 /* Intersect the argument types. */
1198 if (!make_intersected_element (re, e1, e2))
1199 {
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);
1204 goto done;
1205 }
1206
1207 result->initial.count++;
1208 result->initial.length += re->repcount;
1209
1210 e1->repcount -= re->repcount;
1211 if (e1->repcount == 0)
1212 {
1213 e1++;
1214 c1--;
1215 }
1216 e2->repcount -= re->repcount;
1217 if (e2->repcount == 0)
1218 {
1219 e2++;
1220 c2--;
1221 }
1222 }
1223
1224 if (list1->repeated.count == 0 && list2->repeated.count == 0)
1225 {
1226 /* Intersecting two finite lists. */
1227 if (c1 > 0)
1228 {
1229 /* list1 longer than list2. */
1230 if (e1->presence == FCT_REQUIRED)
1231 /* Contradiction. Backtrack. */
1232 result = backtrack_in_initial (result);
1233 }
1234 else if (c2 > 0)
1235 {
1236 /* list2 longer than list1. */
1237 if (e2->presence == FCT_REQUIRED)
1238 /* Contradiction. Backtrack. */
1239 result = backtrack_in_initial (result);
1240 }
1241 goto done;
1242 }
1243 else if (list1->repeated.count == 0)
1244 {
1245 /* Intersecting a finite and an infinite list. */
1246 ASSERT (c1 == 0);
1247 if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence)
1248 == FCT_REQUIRED)
1249 /* Contradiction. Backtrack. */
1250 result = backtrack_in_initial (result);
1251 goto done;
1252 }
1253 else if (list2->repeated.count == 0)
1254 {
1255 /* Intersecting an infinite and a finite list. */
1256 ASSERT (c2 == 0);
1257 if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence)
1258 == FCT_REQUIRED)
1259 /* Contradiction. Backtrack. */
1260 result = backtrack_in_initial (result);
1261 goto done;
1262 }
1263 /* Intersecting two infinite lists. */
1264 ASSERT (c1 == 0 && c2 == 0);
1265 }
1266
1267 /* Step 5: Elementwise intersection of list1->repeated, list2->repeated. */
1268 {
1269 struct format_arg *e1;
1270 struct format_arg *e2;
1271 unsigned int c1;
1272 unsigned int c2;
1273
1274 e1 = list1->repeated.element; c1 = list1->repeated.count;
1275 e2 = list2->repeated.element; c2 = list2->repeated.count;
1276 while (c1 > 0 && c2 > 0)
1277 {
1278 struct format_arg *re;
1279
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);
1284
1285 /* Intersect the argument types. */
1286 if (!make_intersected_element (re, e1, e2))
1287 {
1288 bool re_is_required = re->presence == FCT_REQUIRED;
1289
1290 append_repeated_to_initial (result);
1291
1292 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1293 if (re_is_required)
1294 /* Contradiction. Backtrack. */
1295 result = backtrack_in_initial (result);
1296
1297 goto done;
1298 }
1299
1300 result->repeated.count++;
1301 result->repeated.length += re->repcount;
1302
1303 e1->repcount -= re->repcount;
1304 if (e1->repcount == 0)
1305 {
1306 e1++;
1307 c1--;
1308 }
1309 e2->repcount -= re->repcount;
1310 if (e2->repcount == 0)
1311 {
1312 e2++;
1313 c2--;
1314 }
1315 }
1316 ASSERT (c1 == 0 && c2 == 0);
1317 }
1318
1319 done:
1320 free_list (list1);
1321 free_list (list2);
1322 if (result != NULL)
1323 {
1324 /* Undo the loop unfolding and unrolling done above. */
1325 normalize_outermost_list (result);
1326 VERIFY_LIST (result);
1327 }
1328 return result;
1329 }
1330
1331
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 *
make_intersection_with_empty_list(struct format_arg_list * list)1336 make_intersection_with_empty_list (struct format_arg_list *list)
1337 {
1338 #if 0 /* equivalent but slower */
1339 return make_intersected_list (copy_list (list), make_empty_list ());
1340 #else
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)
1345 return NULL;
1346 else
1347 return make_empty_list ();
1348 #endif
1349 }
1350
1351
1352 #ifdef unused
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 *
intersection(struct format_arg_list * list1,struct format_arg_list * list2)1358 intersection (struct format_arg_list *list1, struct format_arg_list *list2)
1359 {
1360 if (list1 != NULL)
1361 {
1362 if (list2 != NULL)
1363 return make_intersected_list (list1, list2);
1364 else
1365 {
1366 free_list (list1);
1367 return NULL;
1368 }
1369 }
1370 else
1371 {
1372 if (list2 != NULL)
1373 {
1374 free_list (list2);
1375 return NULL;
1376 }
1377 else
1378 return NULL;
1379 }
1380 }
1381 #endif
1382
1383
1384 /* ===================== Union of two format_arg_lists ===================== */
1385
1386 /* Create the union (i.e. alternative constraints) of two argument
1387 constraints. */
1388 static void
make_union_element(struct format_arg * re,const struct format_arg * e1,const struct format_arg * e2)1389 make_union_element (struct format_arg *re,
1390 const struct format_arg * e1,
1391 const struct format_arg * e2)
1392 {
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;
1398
1399 /* Union of the arg types. */
1400 if (e1->type == e2->type)
1401 {
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));
1406 }
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))
1410 {
1411 re->type = e1->type;
1412 }
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))
1416 {
1417 re->type = e2->type;
1418 }
1419 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1420 {
1421 re->type = e1->type;
1422 }
1423 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1424 {
1425 re->type = e2->type;
1426 }
1427 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1428 {
1429 re->type = e1->type;
1430 }
1431 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1432 {
1433 re->type = e2->type;
1434 }
1435 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1436 {
1437 re->type = e1->type;
1438 }
1439 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1440 {
1441 re->type = e2->type;
1442 }
1443 else if (e1->type == FAT_COMPLEX
1444 && (e2->type == FAT_REAL || e2->type == FAT_INTEGER))
1445 {
1446 re->type = e1->type;
1447 }
1448 else if (e2->type == FAT_COMPLEX
1449 && (e1->type == FAT_REAL || e1->type == FAT_INTEGER))
1450 {
1451 re->type = e2->type;
1452 }
1453 else if (e1->type == FAT_LIST && is_empty_list (e1->list))
1454 {
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;
1463 else
1464 re->type = FAT_OBJECT;
1465 }
1466 else if (e2->type == FAT_LIST && is_empty_list (e2->list))
1467 {
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;
1476 else
1477 re->type = FAT_OBJECT;
1478 }
1479 else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL)
1480 && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL))
1481 {
1482 re->type = FAT_CHARACTER_INTEGER_NULL;
1483 }
1484 else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL)
1485 && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL))
1486 {
1487 re->type = FAT_CHARACTER_INTEGER_NULL;
1488 }
1489 else
1490 {
1491 /* Other union types are too hard to describe precisely. */
1492 re->type = FAT_OBJECT;
1493 }
1494 }
1495
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
1499 allocated. */
1500 static struct format_arg_list *
make_union_list(struct format_arg_list * list1,struct format_arg_list * list2)1501 make_union_list (struct format_arg_list *list1, struct format_arg_list *list2)
1502 {
1503 struct format_arg_list *result;
1504
1505 VERIFY_LIST (list1);
1506 VERIFY_LIST (list2);
1507
1508 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1509 {
1510 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1511 {
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 */
1517
1518 unfold_loop (list1, m1);
1519 unfold_loop (list2, m2);
1520 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1521 }
1522
1523 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1524 {
1525 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1526
1527 rotate_loop (list1, m);
1528 rotate_loop (list2, m);
1529 }
1530
1531 ASSERT (list1->initial.length == list2->initial.length);
1532 ASSERT (list1->repeated.length == list2->repeated.length);
1533 }
1534 else if (list1->repeated.length > 0)
1535 {
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)
1539 {
1540 rotate_loop (list1, list2->initial.length);
1541 if (list1->repeated.element[0].presence == FCT_REQUIRED)
1542 rotate_loop (list1, list1->initial.length + 1);
1543 }
1544 }
1545 else if (list2->repeated.length > 0)
1546 {
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)
1550 {
1551 rotate_loop (list2, list1->initial.length);
1552 if (list2->repeated.element[0].presence == FCT_REQUIRED)
1553 rotate_loop (list2, list2->initial.length + 1);
1554 }
1555 }
1556
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;
1567
1568 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1569 {
1570 struct format_arg *e1;
1571 struct format_arg *e2;
1572 unsigned int c1;
1573 unsigned int c2;
1574
1575 e1 = list1->initial.element; c1 = list1->initial.count;
1576 e2 = list2->initial.element; c2 = list2->initial.count;
1577 while (c1 > 0 && c2 > 0)
1578 {
1579 struct format_arg *re;
1580
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);
1585
1586 /* Union of the argument types. */
1587 make_union_element (re, e1, e2);
1588
1589 result->initial.count++;
1590 result->initial.length += re->repcount;
1591
1592 e1->repcount -= re->repcount;
1593 if (e1->repcount == 0)
1594 {
1595 e1++;
1596 c1--;
1597 }
1598 e2->repcount -= re->repcount;
1599 if (e2->repcount == 0)
1600 {
1601 e2++;
1602 c2--;
1603 }
1604 }
1605
1606 if (c1 > 0)
1607 {
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);
1611
1612 if (e1->presence == FCT_REQUIRED)
1613 {
1614 struct format_arg *re;
1615
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;
1621 re->repcount = 1;
1622 result->initial.count++;
1623 result->initial.length += 1;
1624 e1->repcount -= 1;
1625 if (e1->repcount == 0)
1626 {
1627 e1++;
1628 c1--;
1629 }
1630 }
1631
1632 /* Ensure room in result->initial. */
1633 ensure_initial_alloc (result, result->initial.count + c1);
1634 while (c1 > 0)
1635 {
1636 struct format_arg *re;
1637
1638 re = &result->initial.element[result->initial.count];
1639 copy_element (re, e1);
1640 result->initial.count++;
1641 result->initial.length += re->repcount;
1642 e1++;
1643 c1--;
1644 }
1645 }
1646 else if (c2 > 0)
1647 {
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);
1651
1652 if (e2->presence == FCT_REQUIRED)
1653 {
1654 struct format_arg *re;
1655
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;
1661 re->repcount = 1;
1662 result->initial.count++;
1663 result->initial.length += 1;
1664 e2->repcount -= 1;
1665 if (e2->repcount == 0)
1666 {
1667 e2++;
1668 c2--;
1669 }
1670 }
1671
1672 /* Ensure room in result->initial. */
1673 ensure_initial_alloc (result, result->initial.count + c2);
1674 while (c2 > 0)
1675 {
1676 struct format_arg *re;
1677
1678 re = &result->initial.element[result->initial.count];
1679 copy_element (re, e2);
1680 result->initial.count++;
1681 result->initial.length += re->repcount;
1682 e2++;
1683 c2--;
1684 }
1685 }
1686 ASSERT (c1 == 0 && c2 == 0);
1687 }
1688
1689 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1690 /* Step 5: Elementwise union of list1->repeated, list2->repeated. */
1691 {
1692 struct format_arg *e1;
1693 struct format_arg *e2;
1694 unsigned int c1;
1695 unsigned int c2;
1696
1697 e1 = list1->repeated.element; c1 = list1->repeated.count;
1698 e2 = list2->repeated.element; c2 = list2->repeated.count;
1699 while (c1 > 0 && c2 > 0)
1700 {
1701 struct format_arg *re;
1702
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);
1707
1708 /* Union of the argument types. */
1709 make_union_element (re, e1, e2);
1710
1711 result->repeated.count++;
1712 result->repeated.length += re->repcount;
1713
1714 e1->repcount -= re->repcount;
1715 if (e1->repcount == 0)
1716 {
1717 e1++;
1718 c1--;
1719 }
1720 e2->repcount -= re->repcount;
1721 if (e2->repcount == 0)
1722 {
1723 e2++;
1724 c2--;
1725 }
1726 }
1727 ASSERT (c1 == 0 && c2 == 0);
1728 }
1729 else if (list1->repeated.length > 0)
1730 {
1731 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1732 initial segment. Just copy the repeated segment of list1. */
1733 unsigned int i;
1734
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;
1743 }
1744 else if (list2->repeated.length > 0)
1745 {
1746 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1747 initial segment. Just copy the repeated segment of list2. */
1748 unsigned int i;
1749
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;
1758 }
1759
1760 free_list (list1);
1761 free_list (list2);
1762 /* Undo the loop unfolding and unrolling done above. */
1763 normalize_outermost_list (result);
1764 VERIFY_LIST (result);
1765 return result;
1766 }
1767
1768
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 *
make_union_with_empty_list(struct format_arg_list * list)1772 make_union_with_empty_list (struct format_arg_list *list)
1773 {
1774 #if 0 /* equivalent but slower */
1775 return make_union_list (list, make_empty_list ());
1776 #else
1777 VERIFY_LIST (list);
1778
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)
1783 {
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;
1789
1790 /* We might need to merge list->initial.element[0] and
1791 list->initial.element[1]. */
1792 normalize_outermost_list (list);
1793 }
1794
1795 VERIFY_LIST (list);
1796
1797 return list;
1798 #endif
1799 }
1800
1801
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)
1808 {
1809 if (list1 != NULL)
1810 {
1811 if (list2 != NULL)
1812 return make_union_list (list1, list2);
1813 else
1814 return list1;
1815 }
1816 else
1817 {
1818 if (list2 != NULL)
1819 return list2;
1820 else
1821 return NULL;
1822 }
1823 }
1824
1825
1826 /* =========== Adding specific constraints to a format_arg_list =========== */
1827
1828
1829 /* Test whether arguments 0..n are required arguments in a list. */
1830 static bool
is_required(const struct format_arg_list * list,unsigned int n)1831 is_required (const struct format_arg_list *list, unsigned int n)
1832 {
1833 unsigned int s;
1834 unsigned int t;
1835
1836 /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */
1837 t = n + 1;
1838
1839 /* Walk the list->initial segment. */
1840 for (s = 0;
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)
1844 return false;
1845
1846 if (t == 0)
1847 return true;
1848
1849 if (s < list->initial.count)
1850 {
1851 if (list->initial.element[s].presence != FCT_REQUIRED)
1852 return false;
1853 else
1854 return true;
1855 }
1856
1857 /* Walk the list->repeated segment. */
1858 if (list->repeated.count == 0)
1859 return false;
1860
1861 for (s = 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)
1865 return false;
1866
1867 if (t == 0)
1868 return true;
1869
1870 if (s < list->repeated.count)
1871 {
1872 if (list->repeated.element[s].presence != FCT_REQUIRED)
1873 return false;
1874 else
1875 return true;
1876 }
1877
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. */
1881 return true;
1882 }
1883
1884
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 *
add_required_constraint(struct format_arg_list * list,unsigned int n)1889 add_required_constraint (struct format_arg_list *list, unsigned int n)
1890 {
1891 unsigned int i, rest;
1892
1893 if (list == NULL)
1894 return NULL;
1895
1896 VERIFY_LIST (list);
1897
1898 if (list->repeated.count == 0 && list->initial.length <= n)
1899 {
1900 /* list is already constrained to have at most length n.
1901 Contradiction. */
1902 free_list (list);
1903 return NULL;
1904 }
1905
1906 initial_splitelement (list, n + 1);
1907
1908 for (i = 0, rest = n + 1; rest > 0; )
1909 {
1910 list->initial.element[i].presence = FCT_REQUIRED;
1911 rest -= list->initial.element[i].repcount;
1912 i++;
1913 }
1914
1915 VERIFY_LIST (list);
1916
1917 return list;
1918 }
1919
1920
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
1923 contradiction. */
1924 /* Memory effects: list is freed. The result is freshly allocated. */
1925 static struct format_arg_list *
add_end_constraint(struct format_arg_list * list,unsigned int n)1926 add_end_constraint (struct format_arg_list *list, unsigned int n)
1927 {
1928 unsigned int s, i;
1929 enum format_cdr_type n_presence;
1930
1931 if (list == NULL)
1932 return NULL;
1933
1934 VERIFY_LIST (list);
1935
1936 if (list->repeated.count == 0 && list->initial.length <= n)
1937 /* list is already constrained to have at most length n. */
1938 return list;
1939
1940 s = initial_splitelement (list, n);
1941 n_presence =
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);
1945
1946 for (i = s; i < list->initial.count; i++)
1947 {
1948 list->initial.length -= list->initial.element[i].repcount;
1949 free_element (&list->initial.element[i]);
1950 }
1951 list->initial.count = s;
1952
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;
1961
1962 if (n_presence == FCT_REQUIRED)
1963 return backtrack_in_initial (list);
1964 else
1965 return list;
1966 }
1967
1968
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 *
add_type_constraint(struct format_arg_list * list,unsigned int n,enum format_arg_type type)1974 add_type_constraint (struct format_arg_list *list, unsigned int n,
1975 enum format_arg_type type)
1976 {
1977 unsigned int s;
1978 struct format_arg newconstraint;
1979 struct format_arg tmpelement;
1980
1981 if (list == NULL)
1982 return NULL;
1983
1984 /* Through the previous add_required_constraint, we can assume
1985 list->initial.length >= n+1. */
1986
1987 s = initial_unshare (list, n);
1988
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;
1997
1998 VERIFY_LIST (list);
1999
2000 return list;
2001 }
2002
2003
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 *
add_listtype_constraint(struct format_arg_list * list,unsigned int n,enum format_arg_type type,struct format_arg_list * sublist)2009 add_listtype_constraint (struct format_arg_list *list, unsigned int n,
2010 enum format_arg_type type,
2011 struct format_arg_list *sublist)
2012 {
2013 unsigned int s;
2014 struct format_arg newconstraint;
2015 struct format_arg tmpelement;
2016
2017 if (list == NULL)
2018 return NULL;
2019
2020 /* Through the previous add_required_constraint, we can assume
2021 list->initial.length >= n+1. */
2022
2023 s = initial_unshare (list, n);
2024
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;
2034
2035 VERIFY_LIST (list);
2036
2037 return list;
2038 }
2039
2040
2041 /* ============= Subroutines used by the format string parser ============= */
2042
2043 static void
add_req_type_constraint(struct format_arg_list ** listp,unsigned int position,enum format_arg_type type)2044 add_req_type_constraint (struct format_arg_list **listp,
2045 unsigned int position, enum format_arg_type type)
2046 {
2047 *listp = add_required_constraint (*listp, position);
2048 *listp = add_type_constraint (*listp, position, type);
2049 }
2050
2051
2052 static void
add_req_listtype_constraint(struct format_arg_list ** listp,unsigned int position,enum format_arg_type type,struct format_arg_list * sublist)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)
2056 {
2057 *listp = add_required_constraint (*listp, position);
2058 *listp = add_listtype_constraint (*listp, position, type, sublist);
2059 }
2060
2061
2062 /* Create an endless repeated list whose elements are lists constrained
2063 by sublist. */
2064 /* Memory effects: sublist is freed. The result is freshly allocated. */
2065 static struct format_arg_list *
make_repeated_list_of_lists(struct format_arg_list * sublist)2066 make_repeated_list_of_lists (struct format_arg_list *sublist)
2067 {
2068 if (sublist == NULL)
2069 /* The list cannot have a single element. */
2070 return make_empty_list ();
2071 else
2072 {
2073 struct format_arg_list *listlist;
2074
2075 listlist = XMALLOC (struct format_arg_list);
2076
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;
2089
2090 VERIFY_LIST (listlist);
2091
2092 return listlist;
2093 }
2094 }
2095
2096
2097 /* Create an endless repeated list which represents the union of a finite
2098 number of copies of L, each time shifted by period:
2099 ()
2100 L
2101 L and (*^period L)
2102 L and (*^period L) and (*^{2 period} L)
2103 L and (*^period L) and (*^{2 period} L) and (*^{3 period} L)
2104 ...
2105 */
2106 /* Memory effects: sublist is freed. The result is freshly allocated. */
2107 static struct format_arg_list *
make_repeated_list(struct format_arg_list * sublist,unsigned int period)2108 make_repeated_list (struct format_arg_list *sublist, unsigned int period)
2109 {
2110 struct segment tmp;
2111 struct segment *srcseg;
2112 struct format_arg_list *list;
2113 unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount;
2114 bool ended;
2115
2116 VERIFY_LIST (sublist);
2117
2118 ASSERT (period > 0);
2119
2120 if (sublist->repeated.count == 0)
2121 {
2122 /* L is a finite list. */
2123
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);
2128
2129 srcseg = &sublist->initial;
2130 p = period;
2131 }
2132 else
2133 {
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 */
2138
2139 unfold_loop (sublist, m);
2140 p = m * Lp;
2141
2142 /* Concatenate the initial and the repeated segments into a single
2143 segment. */
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;
2152
2153 srcseg = &tmp;
2154 }
2155
2156 n = srcseg->length;
2157
2158 /* Example: n = 7, p = 2
2159 Let L = (A B C D E F G).
2160
2161 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
2165
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
2169 to right. */
2170
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;
2180
2181 /* Sketch:
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];
2187 */
2188
2189 ended = false;
2190
2191 i = 0, ti = 0, si = 0;
2192 while (i < p)
2193 {
2194 unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
2195
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;
2203
2204 i += k;
2205 ti += k;
2206 if (ti == srcseg->element[si].repcount)
2207 {
2208 ti = 0;
2209 si++;
2210 }
2211 }
2212
2213 ASSERT (list->initial.count > 0);
2214 if (list->initial.element[0].presence == FCT_REQUIRED)
2215 {
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;
2220 }
2221
2222 j = 0, tj = 0, sj = 0;
2223 while (i < n)
2224 {
2225 unsigned int k =
2226 MIN (srcseg->element[si].repcount - ti,
2227 list->initial.element[sj].repcount - tj);
2228
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]))
2234 {
2235 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2236 {
2237 /* Contradiction. Backtrack. */
2238 list = backtrack_in_initial (list);
2239 ASSERT (list != NULL); /* at least the empty list is valid */
2240 return list;
2241 }
2242 else
2243 {
2244 /* The list ends here. */
2245 ended = true;
2246 break;
2247 }
2248 }
2249 list->initial.element[list->initial.count].repcount = k;
2250 list->initial.count++;
2251 list->initial.length += k;
2252
2253 i += k;
2254 ti += k;
2255 if (ti == srcseg->element[si].repcount)
2256 {
2257 ti = 0;
2258 si++;
2259 }
2260
2261 j += k;
2262 tj += k;
2263 if (tj == list->initial.element[sj].repcount)
2264 {
2265 tj = 0;
2266 sj++;
2267 }
2268 }
2269 if (!ended)
2270 ASSERT (list->initial.length == n);
2271
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)
2275 {
2276 si = initial_unshare (list, i);
2277 list->initial.element[si].presence = FCT_OPTIONAL;
2278 }
2279
2280 if (!ended)
2281 {
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)
2286 {
2287 list->repeated.allocated = newcount;
2288 list->repeated.element = XNMALLOC (newcount, struct format_arg);
2289 }
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;
2296 }
2297
2298 VERIFY_LIST (list);
2299
2300 return list;
2301 }
2302
2303
2304 /* ================= Handling of format string directives ================= */
2305
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
2310 };
2311 static const enum format_arg_type IIC [3] = {
2312 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2313 };
2314 static const enum format_arg_type ICCI [4] = {
2315 FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL
2316 };
2317 static const enum format_arg_type IIIC [4] = {
2318 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2319 };
2320 static const enum format_arg_type IICCI [5] = {
2321 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL,
2322 FAT_INTEGER_NULL
2323 };
2324 static const enum format_arg_type IIICC [5] = {
2325 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL,
2326 FAT_CHARACTER_NULL
2327 };
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
2331 };
2332 static const enum format_arg_type THREE [3] = {
2333 FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL,
2334 FAT_CHARACTER_INTEGER_NULL
2335 };
2336
2337
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
2340 invalid. */
2341 static bool
check_params(struct format_arg_list ** listp,unsigned int paramcount,struct param * params,unsigned int t_count,const enum format_arg_type * t_types,unsigned int directives,char ** invalid_reason)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)
2346 {
2347 unsigned int orig_paramcount = paramcount;
2348 unsigned int orig_t_count = t_count;
2349
2350 for (; paramcount > 0 && t_count > 0;
2351 params++, paramcount--, t_types++, t_count--)
2352 {
2353 switch (*t_types)
2354 {
2355 case FAT_CHARACTER_INTEGER_NULL:
2356 break;
2357 case FAT_CHARACTER_NULL:
2358 switch (params->type)
2359 {
2360 case PT_NIL: case PT_CHARACTER: case PT_V:
2361 break;
2362 case PT_INTEGER: case PT_ARGCOUNT:
2363 /* wrong param type */
2364 *invalid_reason =
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");
2366 return false;
2367 }
2368 break;
2369 case FAT_INTEGER_NULL:
2370 switch (params->type)
2371 {
2372 case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V:
2373 break;
2374 case PT_CHARACTER:
2375 /* wrong param type */
2376 *invalid_reason =
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");
2378 return false;
2379 }
2380 break;
2381 default:
2382 abort ();
2383 }
2384 if (params->type == PT_V)
2385 {
2386 int position = params->value;
2387 if (position >= 0)
2388 add_req_type_constraint (listp, position, *t_types);
2389 }
2390 }
2391
2392 for (; paramcount > 0; params++, paramcount--)
2393 switch (params->type)
2394 {
2395 case PT_NIL:
2396 break;
2397 case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT:
2398 /* too many params for directive */
2399 *invalid_reason =
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.",
2402 orig_t_count),
2403 directives, orig_t_count);
2404 return false;
2405 case PT_V:
2406 /* Force argument to be NIL. */
2407 {
2408 int position = params->value;
2409 if (position >= 0)
2410 {
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);
2415 }
2416 }
2417 break;
2418 }
2419
2420 return true;
2421 }
2422
2423
2424 /* ======================= The format string parser ======================= */
2425
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
2434 or an empty union.
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. */
2444 static bool
parse_upto(const char ** formatp,int * positionp,struct format_arg_list ** listp,struct format_arg_list ** escapep,int * separatorp,struct spec * spec,char terminator,bool separator,char * fdi,char ** invalid_reason)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)
2450 {
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;
2456
2457 for (; *format != '\0'; )
2458 if (*format++ == '~')
2459 {
2460 bool colon_p = false;
2461 bool atsign_p = false;
2462 unsigned int paramcount = 0;
2463 struct param *params = NULL;
2464
2465 FDI_SET (format - 1, FMTDIR_START);
2466
2467 /* Count number of directives. */
2468 spec->directives++;
2469
2470 /* Parse parameters. */
2471 for (;;)
2472 {
2473 enum param_type type = PT_NIL;
2474 int value = 0;
2475
2476 if (c_isdigit (*format))
2477 {
2478 type = PT_INTEGER;
2479 do
2480 {
2481 value = 10 * value + (*format - '0');
2482 format++;
2483 }
2484 while (c_isdigit (*format));
2485 }
2486 else if (*format == '+' || *format == '-')
2487 {
2488 bool negative = (*format == '-');
2489 type = PT_INTEGER;
2490 format++;
2491 if (!c_isdigit (*format))
2492 {
2493 if (*format == '\0')
2494 {
2495 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2496 FDI_SET (format - 1, FMTDIR_ERROR);
2497 }
2498 else
2499 {
2500 *invalid_reason =
2501 xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]);
2502 FDI_SET (format, FMTDIR_ERROR);
2503 }
2504 return false;
2505 }
2506 do
2507 {
2508 value = 10 * value + (*format - '0');
2509 format++;
2510 }
2511 while (c_isdigit (*format));
2512 if (negative)
2513 value = -value;
2514 }
2515 else if (*format == '\'')
2516 {
2517 type = PT_CHARACTER;
2518 format++;
2519 if (*format == '\0')
2520 {
2521 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2522 FDI_SET (format - 1, FMTDIR_ERROR);
2523 return false;
2524 }
2525 format++;
2526 }
2527 else if (*format == 'V' || *format == 'v')
2528 {
2529 type = PT_V;
2530 format++;
2531 value = position;
2532 /* Consumes an argument. */
2533 if (position >= 0)
2534 position++;
2535 }
2536 else if (*format == '#')
2537 {
2538 type = PT_ARGCOUNT;
2539 format++;
2540 }
2541
2542 params =
2543 (struct param *)
2544 xrealloc (params, (paramcount + 1) * sizeof (struct param));
2545 params[paramcount].type = type;
2546 params[paramcount].value = value;
2547 paramcount++;
2548
2549 if (*format == ',')
2550 format++;
2551 else
2552 break;
2553 }
2554
2555 /* Parse modifiers. */
2556 for (;;)
2557 {
2558 if (*format == ':')
2559 {
2560 format++;
2561 colon_p = true;
2562 }
2563 else if (*format == '@')
2564 {
2565 format++;
2566 atsign_p = true;
2567 }
2568 else
2569 break;
2570 }
2571
2572 /* Parse directive. */
2573 switch (*format++)
2574 {
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))
2579 {
2580 FDI_SET (format - 1, FMTDIR_ERROR);
2581 return false;
2582 }
2583 if (position >= 0)
2584 add_req_type_constraint (&list, position++, FAT_OBJECT);
2585 break;
2586
2587 case 'C': case 'c': /* FORMAT-CHARACTER */
2588 if (!check_params (&list, paramcount, params, 1, I,
2589 spec->directives, invalid_reason))
2590 {
2591 FDI_SET (format - 1, FMTDIR_ERROR);
2592 return false;
2593 }
2594 if (paramcount == 0
2595 || (paramcount == 1 && params[0].type == PT_NIL))
2596 if (position >= 0)
2597 add_req_type_constraint (&list, position++, FAT_CHARACTER);
2598 break;
2599
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))
2606 {
2607 FDI_SET (format - 1, FMTDIR_ERROR);
2608 return false;
2609 }
2610 if (position >= 0)
2611 add_req_type_constraint (&list, position++, FAT_INTEGER);
2612 break;
2613
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))
2617 {
2618 FDI_SET (format - 1, FMTDIR_ERROR);
2619 return false;
2620 }
2621 if (position >= 0)
2622 add_req_type_constraint (&list, position++, FAT_INTEGER);
2623 break;
2624
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))
2628 {
2629 FDI_SET (format - 1, FMTDIR_ERROR);
2630 return false;
2631 }
2632 if (colon_p)
2633 {
2634 /* Go back by 1 argument. */
2635 if (position > 0)
2636 position--;
2637 }
2638 if (position >= 0)
2639 add_req_type_constraint (&list, position++, FAT_OBJECT);
2640 break;
2641
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))
2645 {
2646 FDI_SET (format - 1, FMTDIR_ERROR);
2647 return false;
2648 }
2649 if (position >= 0)
2650 add_req_type_constraint (&list, position++, FAT_REAL);
2651 break;
2652
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))
2657 {
2658 FDI_SET (format - 1, FMTDIR_ERROR);
2659 return false;
2660 }
2661 if (position >= 0)
2662 add_req_type_constraint (&list, position++, FAT_REAL);
2663 break;
2664
2665 case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */
2666 if (!check_params (&list, paramcount, params, 4, IIIC,
2667 spec->directives, invalid_reason))
2668 {
2669 FDI_SET (format - 1, FMTDIR_ERROR);
2670 return false;
2671 }
2672 if (position >= 0)
2673 add_req_type_constraint (&list, position++, FAT_REAL);
2674 break;
2675
2676 case 'I': case 'i': /* FORMAT-FIXED-FLOAT-COMPLEX */
2677 if (!check_params (&list, paramcount, params, 5, IIICC,
2678 spec->directives, invalid_reason))
2679 {
2680 FDI_SET (format - 1, FMTDIR_ERROR);
2681 return false;
2682 }
2683 if (position >= 0)
2684 add_req_type_constraint (&list, position++, FAT_COMPLEX);
2685 break;
2686
2687 case 'Y': case 'y': /* FORMAT-PRETTY */
2688 if (!check_params (&list, paramcount, params, 0, NULL,
2689 spec->directives, invalid_reason))
2690 {
2691 FDI_SET (format - 1, FMTDIR_ERROR);
2692 return false;
2693 }
2694 if (position >= 0)
2695 add_req_type_constraint (&list, position++, FAT_OBJECT);
2696 break;
2697
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))
2706 {
2707 FDI_SET (format - 1, FMTDIR_ERROR);
2708 return false;
2709 }
2710 break;
2711
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))
2717 {
2718 FDI_SET (format - 1, FMTDIR_ERROR);
2719 return false;
2720 }
2721 break;
2722
2723 case 'T': case 't': /* FORMAT-TABULATE */
2724 if (!check_params (&list, paramcount, params, 3, IIC,
2725 spec->directives, invalid_reason))
2726 {
2727 FDI_SET (format - 1, FMTDIR_ERROR);
2728 return false;
2729 }
2730 break;
2731
2732 case '*': /* 22.3.7.1 FORMAT-GOTO */
2733 if (!check_params (&list, paramcount, params, 1, I,
2734 spec->directives, invalid_reason))
2735 {
2736 FDI_SET (format - 1, FMTDIR_ERROR);
2737 return false;
2738 }
2739 {
2740 int n; /* value of first parameter */
2741 if (paramcount == 0
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;
2746 else
2747 {
2748 /* Unknown argument, leads to an unknown position. */
2749 position = -1;
2750 break;
2751 }
2752 if (n < 0)
2753 {
2754 /* invalid argument */
2755 *invalid_reason =
2756 xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
2757 FDI_SET (format - 1, FMTDIR_ERROR);
2758 return false;
2759 }
2760 if (atsign_p)
2761 {
2762 /* Absolute goto. */
2763 position = n;
2764 }
2765 else if (colon_p)
2766 {
2767 /* Backward goto. */
2768 if (n > 0)
2769 {
2770 if (position >= 0)
2771 {
2772 if (position >= n)
2773 position -= n;
2774 else
2775 position = 0;
2776 }
2777 else
2778 position = -1;
2779 }
2780 }
2781 else
2782 {
2783 /* Forward goto. */
2784 if (position >= 0)
2785 position += n;
2786 }
2787 }
2788 break;
2789
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))
2793 {
2794 FDI_SET (format - 1, FMTDIR_ERROR);
2795 return false;
2796 }
2797 if (position >= 0)
2798 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
2799 if (atsign_p)
2800 position = -1;
2801 else
2802 if (position >= 0)
2803 {
2804 struct format_arg_list *sublist = make_unconstrained_list ();
2805 add_req_listtype_constraint (&list, position++,
2806 FAT_LIST, sublist);
2807 free_list (sublist);
2808 }
2809 break;
2810
2811 case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */
2812 if (!check_params (&list, paramcount, params, 0, NULL,
2813 spec->directives, invalid_reason))
2814 {
2815 FDI_SET (format - 1, FMTDIR_ERROR);
2816 return false;
2817 }
2818 *formatp = format;
2819 *positionp = position;
2820 *listp = list;
2821 *escapep = escape;
2822 {
2823 if (!parse_upto (formatp, positionp, listp, escapep,
2824 NULL, spec, ')', false,
2825 NULL, invalid_reason))
2826 {
2827 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2828 FMTDIR_ERROR);
2829 return false;
2830 }
2831 }
2832 format = *formatp;
2833 position = *positionp;
2834 list = *listp;
2835 escape = *escapep;
2836 break;
2837
2838 case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */
2839 if (terminator != ')')
2840 {
2841 *invalid_reason =
2842 xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
2843 FDI_SET (format - 1, FMTDIR_ERROR);
2844 return false;
2845 }
2846 if (!check_params (&list, paramcount, params, 0, NULL,
2847 spec->directives, invalid_reason))
2848 {
2849 FDI_SET (format - 1, FMTDIR_ERROR);
2850 return false;
2851 }
2852 *formatp = format;
2853 *positionp = position;
2854 *listp = list;
2855 *escapep = escape;
2856 return true;
2857
2858 case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */
2859 if (atsign_p && colon_p)
2860 {
2861 *invalid_reason =
2862 xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
2863 FDI_SET (format - 1, FMTDIR_ERROR);
2864 return false;
2865 }
2866 else if (atsign_p)
2867 {
2868 struct format_arg_list *nil_list;
2869 struct format_arg_list *union_list;
2870
2871 if (!check_params (&list, paramcount, params, 0, NULL,
2872 spec->directives, invalid_reason))
2873 {
2874 FDI_SET (format - 1, FMTDIR_ERROR);
2875 return false;
2876 }
2877
2878 *formatp = format;
2879 *escapep = escape;
2880
2881 /* First alternative: argument is NIL. */
2882 nil_list = (list != NULL ? copy_list (list) : NULL);
2883 if (position >= 0)
2884 {
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);
2889 }
2890
2891 /* Second alternative: use sub-format. */
2892 {
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))
2899 {
2900 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2901 FMTDIR_ERROR);
2902 return false;
2903 }
2904 if (sub_list != NULL)
2905 {
2906 if (position >= 0)
2907 {
2908 if (sub_position == position + 1)
2909 /* new position is branch independent */
2910 position = position + 1;
2911 else
2912 /* new position is branch dependent */
2913 position = -1;
2914 }
2915 }
2916 else
2917 {
2918 if (position >= 0)
2919 position = position + 1;
2920 }
2921 union_list = union (nil_list, sub_list);
2922 }
2923
2924 format = *formatp;
2925 escape = *escapep;
2926
2927 if (list != NULL)
2928 free_list (list);
2929 list = union_list;
2930 }
2931 else if (colon_p)
2932 {
2933 int union_position;
2934 struct format_arg_list *union_list;
2935
2936 if (!check_params (&list, paramcount, params, 0, NULL,
2937 spec->directives, invalid_reason))
2938 {
2939 FDI_SET (format - 1, FMTDIR_ERROR);
2940 return false;
2941 }
2942
2943 if (position >= 0)
2944 add_req_type_constraint (&list, position++, FAT_OBJECT);
2945
2946 *formatp = format;
2947 *escapep = escape;
2948 union_position = -2;
2949 union_list = NULL;
2950
2951 /* First alternative. */
2952 {
2953 int sub_position = position;
2954 struct format_arg_list *sub_list =
2955 (list != NULL ? copy_list (list) : NULL);
2956 int sub_separator = 0;
2957 if (position >= 0)
2958 {
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);
2963 }
2964 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2965 &sub_separator, spec, ']', true,
2966 NULL, invalid_reason))
2967 {
2968 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2969 FMTDIR_ERROR);
2970 return false;
2971 }
2972 if (!sub_separator)
2973 {
2974 *invalid_reason =
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,
2977 FMTDIR_ERROR);
2978 return false;
2979 }
2980 if (sub_list != NULL)
2981 union_position = sub_position;
2982 union_list = union (union_list, sub_list);
2983 }
2984
2985 /* Second alternative. */
2986 {
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))
2993 {
2994 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
2995 FMTDIR_ERROR);
2996 return false;
2997 }
2998 if (sub_list != NULL)
2999 {
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;
3005 }
3006 union_list = union (union_list, sub_list);
3007 }
3008
3009 format = *formatp;
3010 escape = *escapep;
3011
3012 if (union_position != -2)
3013 position = union_position;
3014 if (list != NULL)
3015 free_list (list);
3016 list = union_list;
3017 }
3018 else
3019 {
3020 int arg_position;
3021 int union_position;
3022 struct format_arg_list *union_list;
3023 bool last_alternative;
3024
3025 if (!check_params (&list, paramcount, params, 1, I,
3026 spec->directives, invalid_reason))
3027 {
3028 FDI_SET (format - 1, FMTDIR_ERROR);
3029 return false;
3030 }
3031
3032 /* If there was no first parameter, an argument is consumed. */
3033 arg_position = -1;
3034 if (!(paramcount >= 1 && params[0].type != PT_NIL))
3035 if (position >= 0)
3036 {
3037 arg_position = position;
3038 add_req_type_constraint (&list, position++, FAT_OBJECT);
3039 }
3040
3041 *formatp = format;
3042 *escapep = escape;
3043
3044 union_position = -2;
3045 union_list = NULL;
3046 last_alternative = false;
3047 for (;;)
3048 {
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))
3057 {
3058 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3059 FMTDIR_ERROR);
3060 return false;
3061 }
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,
3066 FAT_INTEGER);
3067 if (sub_list != NULL)
3068 {
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;
3074 }
3075 union_list = union (union_list, sub_list);
3076 if (sub_separator == 2)
3077 last_alternative = true;
3078 if (!sub_separator)
3079 break;
3080 }
3081 if (!last_alternative)
3082 {
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;
3088 if (list != NULL)
3089 union_list = union (union_list, copy_list (list));
3090 }
3091
3092 format = *formatp;
3093 escape = *escapep;
3094
3095 if (union_position != -2)
3096 position = union_position;
3097 if (list != NULL)
3098 free_list (list);
3099 list = union_list;
3100 }
3101 break;
3102
3103 case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */
3104 if (terminator != ']')
3105 {
3106 *invalid_reason =
3107 xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
3108 FDI_SET (format - 1, FMTDIR_ERROR);
3109 return false;
3110 }
3111 if (!check_params (&list, paramcount, params, 0, NULL,
3112 spec->directives, invalid_reason))
3113 {
3114 FDI_SET (format - 1, FMTDIR_ERROR);
3115 return false;
3116 }
3117 *formatp = format;
3118 *positionp = position;
3119 *listp = list;
3120 *escapep = escape;
3121 return true;
3122
3123 case '{': /* 22.3.7.4 FORMAT-ITERATION */
3124 if (!check_params (&list, paramcount, params, 1, I,
3125 spec->directives, invalid_reason))
3126 {
3127 FDI_SET (format - 1, FMTDIR_ERROR);
3128 return false;
3129 }
3130 *formatp = format;
3131 {
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))
3141 {
3142 FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp,
3143 FMTDIR_ERROR);
3144 return false;
3145 }
3146 spec->directives += sub_spec.directives;
3147
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)
3151 if (position >= 0)
3152 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
3153
3154 if (colon_p)
3155 {
3156 /* Each iteration uses a new sublist. */
3157 struct format_arg_list *listlist;
3158
3159 /* ~{ catches ~^. */
3160 sub_list = union (sub_list, sub_escape);
3161
3162 listlist = make_repeated_list_of_lists (sub_list);
3163
3164 sub_list = listlist;
3165 }
3166 else
3167 {
3168 /* Each iteration's arguments are all concatenated in a
3169 single list. */
3170 struct format_arg_list *looplist;
3171
3172 /* FIXME: This is far from correct. Test cases:
3173 abc~{~^~}
3174 abc~{~S~^~S~}
3175 abc~{~D~^~C~}
3176 abc~{~D~^~D~}
3177 abc~{~D~^~S~}
3178 abc~{~D~^~C~}~:*~{~S~^~D~}
3179 */
3180
3181 /* ~{ catches ~^. */
3182 sub_list = union (sub_list, sub_escape);
3183
3184 if (sub_list == NULL)
3185 looplist = make_empty_list ();
3186 else
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);
3193 else
3194 looplist = make_repeated_list (sub_list, sub_position);
3195
3196 sub_list = looplist;
3197 }
3198
3199 if (atsign_p)
3200 {
3201 /* All remaining arguments are used. */
3202 if (list != NULL && position >= 0)
3203 {
3204 shift_list (sub_list, position);
3205 list = make_intersected_list (list, sub_list);
3206 }
3207 position = -1;
3208 }
3209 else
3210 {
3211 /* The argument is a list. */
3212 if (position >= 0)
3213 add_req_listtype_constraint (&list, position++,
3214 FAT_LIST, sub_list);
3215 }
3216 }
3217 format = *formatp;
3218 break;
3219
3220 case '}': /* 22.3.7.5 FORMAT-ITERATION-END */
3221 if (terminator != '}')
3222 {
3223 *invalid_reason =
3224 xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
3225 FDI_SET (format - 1, FMTDIR_ERROR);
3226 return false;
3227 }
3228 if (!check_params (&list, paramcount, params, 0, NULL,
3229 spec->directives, invalid_reason))
3230 {
3231 FDI_SET (format - 1, FMTDIR_ERROR);
3232 return false;
3233 }
3234 *formatp = format;
3235 *positionp = position;
3236 *listp = list;
3237 *escapep = escape;
3238 return true;
3239
3240 case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */
3241 if (!check_params (&list, paramcount, params, 3, THREE,
3242 spec->directives, invalid_reason))
3243 {
3244 FDI_SET (format - 1, FMTDIR_ERROR);
3245 return false;
3246 }
3247 if (position >= 0 && list != NULL && is_required (list, position))
3248 /* This ~^ can never be executed. Ignore it. */
3249 break;
3250 if (list != NULL)
3251 {
3252 struct format_arg_list *this_escape = copy_list (list);
3253 if (position >= 0)
3254 this_escape = add_end_constraint (this_escape, position);
3255 escape = union (escape, this_escape);
3256 }
3257 if (position >= 0)
3258 list = add_required_constraint (list, position);
3259 break;
3260
3261 case ';': /* 22.3.9.1 FORMAT-SEPARATOR */
3262 if (!separator)
3263 {
3264 *invalid_reason =
3265 xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
3266 FDI_SET (format - 1, FMTDIR_ERROR);
3267 return false;
3268 }
3269 if (terminator == '>')
3270 {
3271 if (!check_params (&list, paramcount, params, 1, I,
3272 spec->directives, invalid_reason))
3273 {
3274 FDI_SET (format - 1, FMTDIR_ERROR);
3275 return false;
3276 }
3277 }
3278 else
3279 {
3280 if (!check_params (&list, paramcount, params, 0, NULL,
3281 spec->directives, invalid_reason))
3282 {
3283 FDI_SET (format - 1, FMTDIR_ERROR);
3284 return false;
3285 }
3286 }
3287 *formatp = format;
3288 *positionp = position;
3289 *listp = list;
3290 *escapep = escape;
3291 *separatorp = (colon_p ? 2 : 1);
3292 return true;
3293
3294 default:
3295 --format;
3296 if (*format == '\0')
3297 {
3298 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
3299 FDI_SET (format - 1, FMTDIR_ERROR);
3300 }
3301 else
3302 {
3303 *invalid_reason =
3304 INVALID_CONVERSION_SPECIFIER (spec->directives, *format);
3305 FDI_SET (format, FMTDIR_ERROR);
3306 }
3307 return false;
3308 }
3309
3310 FDI_SET (format - 1, FMTDIR_END);
3311
3312 free (params);
3313 }
3314
3315 *formatp = format;
3316 *positionp = position;
3317 *listp = list;
3318 *escapep = escape;
3319 if (terminator != '\0')
3320 {
3321 *invalid_reason =
3322 xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator);
3323 return false;
3324 }
3325 return true;
3326 }
3327
3328
3329 /* ============== Top level format string handling functions ============== */
3330
3331 static void *
format_parse(const char * format,bool translated,char * fdi,char ** invalid_reason)3332 format_parse (const char *format, bool translated, char *fdi,
3333 char **invalid_reason)
3334 {
3335 struct spec spec;
3336 struct spec *result;
3337 int position = 0;
3338 struct format_arg_list *escape;
3339
3340 spec.directives = 0;
3341 spec.list = make_unconstrained_list ();
3342 escape = NULL;
3343
3344 if (!parse_upto (&format, &position, &spec.list, &escape,
3345 NULL, &spec, '\0', false,
3346 fdi, invalid_reason))
3347 /* Invalid format string. */
3348 return NULL;
3349
3350 /* Catch ~^ here. */
3351 spec.list = union (spec.list, escape);
3352
3353 if (spec.list == NULL)
3354 {
3355 /* Contradictory argument type information. */
3356 *invalid_reason =
3357 xstrdup (_("The string refers to some argument in incompatible ways."));
3358 return NULL;
3359 }
3360
3361 /* Normalize the result. */
3362 normalize_list (spec.list);
3363
3364 result = XMALLOC (struct spec);
3365 *result = spec;
3366 return result;
3367 }
3368
3369 static void
format_free(void * descr)3370 format_free (void *descr)
3371 {
3372 struct spec *spec = (struct spec *) descr;
3373
3374 free_list (spec->list);
3375 }
3376
3377 static int
format_get_number_of_directives(void * descr)3378 format_get_number_of_directives (void *descr)
3379 {
3380 struct spec *spec = (struct spec *) descr;
3381
3382 return spec->directives;
3383 }
3384
3385 static bool
format_check(void * msgid_descr,void * msgstr_descr,bool equality,formatstring_error_logger_t error_logger,const char * pretty_msgid,const char * pretty_msgstr)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)
3389 {
3390 struct spec *spec1 = (struct spec *) msgid_descr;
3391 struct spec *spec2 = (struct spec *) msgstr_descr;
3392 bool err = false;
3393
3394 if (equality)
3395 {
3396 if (!equal_list (spec1->list, spec2->list))
3397 {
3398 if (error_logger)
3399 error_logger (_("format specifications in '%s' and '%s' are not equivalent"),
3400 pretty_msgid, pretty_msgstr);
3401 err = true;
3402 }
3403 }
3404 else
3405 {
3406 struct format_arg_list *intersection =
3407 make_intersected_list (copy_list (spec1->list),
3408 copy_list (spec2->list));
3409
3410 if (!(intersection != NULL
3411 && (normalize_list (intersection),
3412 equal_list (intersection, spec2->list))))
3413 {
3414 if (error_logger)
3415 error_logger (_("format specifications in '%s' are not a subset of those in '%s'"),
3416 pretty_msgstr, pretty_msgid);
3417 err = true;
3418 }
3419 }
3420
3421 return err;
3422 }
3423
3424
3425 struct formatstring_parser formatstring_scheme =
3426 {
3427 format_parse,
3428 format_free,
3429 format_get_number_of_directives,
3430 NULL,
3431 format_check
3432 };
3433
3434
3435 /* ============================= Testing code ============================= */
3436
3437 #undef union
3438
3439 #ifdef TEST
3440
3441 /* Test program: Print the argument list specification returned by
3442 format_parse for strings read from standard input. */
3443
3444 #include <stdio.h>
3445
3446 static void print_list (struct format_arg_list *list);
3447
3448 static void
print_element(struct format_arg * element)3449 print_element (struct format_arg *element)
3450 {
3451 switch (element->presence)
3452 {
3453 case FCT_REQUIRED:
3454 break;
3455 case FCT_OPTIONAL:
3456 printf (". ");
3457 break;
3458 default:
3459 abort ();
3460 }
3461
3462 switch (element->type)
3463 {
3464 case FAT_OBJECT:
3465 printf ("*");
3466 break;
3467 case FAT_CHARACTER_INTEGER_NULL:
3468 printf ("ci()");
3469 break;
3470 case FAT_CHARACTER_NULL:
3471 printf ("c()");
3472 break;
3473 case FAT_CHARACTER:
3474 printf ("c");
3475 break;
3476 case FAT_INTEGER_NULL:
3477 printf ("i()");
3478 break;
3479 case FAT_INTEGER:
3480 printf ("i");
3481 break;
3482 case FAT_REAL:
3483 printf ("r");
3484 break;
3485 case FAT_COMPLEX:
3486 printf ("C");
3487 break;
3488 case FAT_LIST:
3489 print_list (element->list);
3490 break;
3491 case FAT_FORMATSTRING:
3492 printf ("~");
3493 break;
3494 default:
3495 abort ();
3496 }
3497 }
3498
3499 static void
print_list(struct format_arg_list * list)3500 print_list (struct format_arg_list *list)
3501 {
3502 unsigned int i, j;
3503
3504 printf ("(");
3505
3506 for (i = 0; i < list->initial.count; i++)
3507 for (j = 0; j < list->initial.element[i].repcount; j++)
3508 {
3509 if (i > 0 || j > 0)
3510 printf (" ");
3511 print_element (&list->initial.element[i]);
3512 }
3513
3514 if (list->repeated.count > 0)
3515 {
3516 printf (" |");
3517 for (i = 0; i < list->repeated.count; i++)
3518 for (j = 0; j < list->repeated.element[i].repcount; j++)
3519 {
3520 printf (" ");
3521 print_element (&list->repeated.element[i]);
3522 }
3523 }
3524
3525 printf (")");
3526 }
3527
3528 static void
format_print(void * descr)3529 format_print (void *descr)
3530 {
3531 struct spec *spec = (struct spec *) descr;
3532
3533 if (spec == NULL)
3534 {
3535 printf ("INVALID");
3536 return;
3537 }
3538
3539 print_list (spec->list);
3540 }
3541
3542 int
main()3543 main ()
3544 {
3545 for (;;)
3546 {
3547 char *line = NULL;
3548 size_t line_size = 0;
3549 int line_len;
3550 char *invalid_reason;
3551 void *descr;
3552
3553 line_len = getline (&line, &line_size, stdin);
3554 if (line_len < 0)
3555 break;
3556 if (line_len > 0 && line[line_len - 1] == '\n')
3557 line[--line_len] = '\0';
3558
3559 invalid_reason = NULL;
3560 descr = format_parse (line, false, NULL, &invalid_reason);
3561
3562 format_print (descr);
3563 printf ("\n");
3564 if (descr == NULL)
3565 printf ("%s\n", invalid_reason);
3566
3567 free (invalid_reason);
3568 free (line);
3569 }
3570
3571 return 0;
3572 }
3573
3574 /*
3575 * For Emacs M-x compile
3576 * Local Variables:
3577 * compile-command: "/bin/sh ../libtool --tag=CC --mode=link gcc -o a.out -static -O -g -Wall -I.. -I../gnulib-lib -I../../gettext-runtime/intl -DHAVE_CONFIG_H -DTEST format-scheme.c ../gnulib-lib/libgettextlib.la"
3578 * End:
3579 */
3580
3581 #endif /* TEST */
3582