1 /* Lisp format strings.
2 Copyright (C) 2001-2004, 2006 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 2, or (at your option)
8 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, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
18
19 #ifdef HAVE_CONFIG_H
20 # include <config.h>
21 #endif
22
23 #include <stdbool.h>
24 #include <stdlib.h>
25
26 #include "format.h"
27 #include "c-ctype.h"
28 #include "gcd.h"
29 #include "xalloc.h"
30 #include "xvasprintf.h"
31 #include "format-invalid.h"
32 #include "minmax.h"
33 #include "gettext.h"
34
35 #define _(str) gettext (str)
36
37
38 /* Assertion macros. Could be defined to empty for speed. */
39 #define ASSERT(expr) if (!(expr)) abort ();
40 #define VERIFY_LIST(list) verify_list (list)
41
42
43 /* Lisp format strings are described in the Common Lisp HyperSpec,
44 chapter 22.3 "Formatted Output". */
45
46 /* Data structure describing format string derived constraints for an
47 argument list. It is a recursive list structure. Structure sharing
48 is not allowed. */
49
50 enum format_cdr_type
51 {
52 FCT_REQUIRED, /* The format argument list cannot end before this argument. */
53 FCT_OPTIONAL /* The format argument list may end before this argument. */
54 };
55
56 enum format_arg_type
57 {
58 FAT_OBJECT, /* Any object, type T. */
59 FAT_CHARACTER_INTEGER_NULL, /* Type (OR CHARACTER INTEGER NULL). */
60 FAT_CHARACTER_NULL, /* Type (OR CHARACTER NULL). */
61 FAT_CHARACTER, /* Type CHARACTER. */
62 FAT_INTEGER_NULL, /* Type (OR INTEGER NULL). */
63 FAT_INTEGER, /* Meant for objects of type INTEGER. */
64 FAT_REAL, /* Meant for objects of type REAL. */
65 FAT_LIST, /* Meant for proper lists. */
66 FAT_FORMATSTRING, /* Format strings. */
67 FAT_FUNCTION /* Function. */
68 };
69
70 struct format_arg
71 {
72 unsigned int repcount; /* Number of consecutive arguments this constraint
73 applies to. Normally 1, but unconstrained
74 arguments are often repeated. */
75 enum format_cdr_type presence; /* Can the argument list end right before
76 this argument? */
77 enum format_arg_type type; /* Possible values for this argument. */
78 struct format_arg_list *list; /* For FAT_LIST: List elements. */
79 };
80
81 struct format_arg_list
82 {
83 /* The constraints for the potentially infinite argument list are assumed
84 to become ultimately periodic. (Too complicated argument lists without
85 a-priori period, like
86 (format t "~@{~:[-~;~S~]~}" nil t 1 t 3 nil t 4)
87 are described by a constraint that ends in a length 1 period of
88 unconstrained arguments.) Such a periodic sequence can be split into
89 an initial segment and an endlessly repeated loop segment.
90 A finite sequence is represented entirely in the initial segment; the
91 loop segment is empty. */
92
93 struct segment
94 {
95 unsigned int count; /* Number of format_arg records used. */
96 unsigned int allocated;
97 struct format_arg *element; /* Argument constraints. */
98 unsigned int length; /* Number of arguments represented by this segment.
99 This is the sum of all repcounts in the segment. */
100 }
101 initial, /* Initial arguments segment. */
102 repeated; /* Endlessly repeated segment. */
103 };
104
105 struct spec
106 {
107 unsigned int directives;
108 struct format_arg_list *list;
109 };
110
111
112 /* Parameter for a directive. */
113 enum param_type
114 {
115 PT_NIL, /* param not present */
116 PT_CHARACTER, /* character */
117 PT_INTEGER, /* integer */
118 PT_ARGCOUNT, /* number of remaining arguments */
119 PT_V /* variable taken from argument list */
120 };
121
122 struct param
123 {
124 enum param_type type;
125 int value; /* for PT_INTEGER: the value, for PT_V: the position */
126 };
127
128
129 /* Forward declaration of local functions. */
130 #define union make_union
131 static void verify_list (const struct format_arg_list *list);
132 static void free_list (struct format_arg_list *list);
133 static struct format_arg_list * copy_list (const struct format_arg_list *list);
134 static bool equal_list (const struct format_arg_list *list1,
135 const struct format_arg_list *list2);
136 static struct format_arg_list * make_intersected_list
137 (struct format_arg_list *list1,
138 struct format_arg_list *list2);
139 static struct format_arg_list * make_intersection_with_empty_list
140 (struct format_arg_list *list);
141 static struct format_arg_list * make_union_list
142 (struct format_arg_list *list1,
143 struct format_arg_list *list2);
144
145
146 /* ======================= Verify a format_arg_list ======================= */
147
148 /* Verify some invariants. */
149 static void
verify_element(const struct format_arg * e)150 verify_element (const struct format_arg * e)
151 {
152 ASSERT (e->repcount > 0);
153 if (e->type == FAT_LIST)
154 verify_list (e->list);
155 }
156
157 /* Verify some invariants. */
158 /* Memory effects: none. */
159 static void
verify_list(const struct format_arg_list * list)160 verify_list (const struct format_arg_list *list)
161 {
162 unsigned int i;
163 unsigned int total_repcount;
164
165 ASSERT (list->initial.count <= list->initial.allocated);
166 total_repcount = 0;
167 for (i = 0; i < list->initial.count; i++)
168 {
169 verify_element (&list->initial.element[i]);
170 total_repcount += list->initial.element[i].repcount;
171 }
172 ASSERT (total_repcount == list->initial.length);
173
174 ASSERT (list->repeated.count <= list->repeated.allocated);
175 total_repcount = 0;
176 for (i = 0; i < list->repeated.count; i++)
177 {
178 verify_element (&list->repeated.element[i]);
179 total_repcount += list->repeated.element[i].repcount;
180 }
181 ASSERT (total_repcount == list->repeated.length);
182 }
183
184 #define VERIFY_LIST(list) verify_list (list)
185
186
187 /* ======================== Free a format_arg_list ======================== */
188
189 /* Free the data belonging to an argument list element. */
190 static inline void
free_element(struct format_arg * element)191 free_element (struct format_arg *element)
192 {
193 if (element->type == FAT_LIST)
194 free_list (element->list);
195 }
196
197 /* Free an argument list. */
198 /* Memory effects: Frees list. */
199 static void
free_list(struct format_arg_list * list)200 free_list (struct format_arg_list *list)
201 {
202 unsigned int i;
203
204 for (i = 0; i < list->initial.count; i++)
205 free_element (&list->initial.element[i]);
206 if (list->initial.element != NULL)
207 free (list->initial.element);
208
209 for (i = 0; i < list->repeated.count; i++)
210 free_element (&list->repeated.element[i]);
211 if (list->repeated.element != NULL)
212 free (list->repeated.element);
213 }
214
215
216 /* ======================== Copy a format_arg_list ======================== */
217
218 /* Copy the data belonging to an argument list element. */
219 static inline void
copy_element(struct format_arg * newelement,const struct format_arg * oldelement)220 copy_element (struct format_arg *newelement,
221 const struct format_arg *oldelement)
222 {
223 newelement->repcount = oldelement->repcount;
224 newelement->presence = oldelement->presence;
225 newelement->type = oldelement->type;
226 if (oldelement->type == FAT_LIST)
227 newelement->list = copy_list (oldelement->list);
228 }
229
230 /* Copy an argument list. */
231 /* Memory effects: Freshly allocated result. */
232 static struct format_arg_list *
copy_list(const struct format_arg_list * list)233 copy_list (const struct format_arg_list *list)
234 {
235 struct format_arg_list *newlist;
236 unsigned int length;
237 unsigned int i;
238
239 VERIFY_LIST (list);
240
241 newlist =
242 (struct format_arg_list *) xmalloc (sizeof (struct format_arg_list));
243
244 newlist->initial.count = newlist->initial.allocated = list->initial.count;
245 length = 0;
246 if (list->initial.count == 0)
247 newlist->initial.element = NULL;
248 else
249 {
250 newlist->initial.element =
251 (struct format_arg *)
252 xmalloc (newlist->initial.allocated * sizeof (struct format_arg));
253 for (i = 0; i < list->initial.count; i++)
254 {
255 copy_element (&newlist->initial.element[i],
256 &list->initial.element[i]);
257 length += list->initial.element[i].repcount;
258 }
259 }
260 ASSERT (length == list->initial.length);
261 newlist->initial.length = length;
262
263 newlist->repeated.count = newlist->repeated.allocated = list->repeated.count;
264 length = 0;
265 if (list->repeated.count == 0)
266 newlist->repeated.element = NULL;
267 else
268 {
269 newlist->repeated.element =
270 (struct format_arg *)
271 xmalloc (newlist->repeated.allocated * sizeof (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 = (struct format_arg_list *) xmalloc (sizeof (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 =
608 (struct format_arg *) xmalloc (1 * sizeof (struct format_arg));
609 list->repeated.element[0].repcount = 1;
610 list->repeated.element[0].presence = FCT_OPTIONAL;
611 list->repeated.element[0].type = FAT_OBJECT;
612 list->repeated.length = 1;
613
614 VERIFY_LIST (list);
615
616 return list;
617 }
618
619
620 /* Create an empty argument list. */
621 /* Memory effects: Freshly allocated result. */
622 static struct format_arg_list *
make_empty_list()623 make_empty_list ()
624 {
625 struct format_arg_list *list;
626
627 list = (struct format_arg_list *) xmalloc (sizeof (struct format_arg_list));
628 list->initial.count = 0;
629 list->initial.allocated = 0;
630 list->initial.element = NULL;
631 list->initial.length = 0;
632 list->repeated.count = 0;
633 list->repeated.allocated = 0;
634 list->repeated.element = NULL;
635 list->repeated.length = 0;
636
637 VERIFY_LIST (list);
638
639 return list;
640 }
641
642
643 /* Test for an empty list. */
644 /* Memory effects: none. */
645 static bool
is_empty_list(const struct format_arg_list * list)646 is_empty_list (const struct format_arg_list *list)
647 {
648 return (list->initial.count == 0 && list->repeated.count == 0);
649 }
650
651
652 /* ======================== format_arg_list surgery ======================== */
653
654 /* Unfold list->repeated m times, where m >= 1.
655 Assumes list->repeated.count > 0. */
656 /* Memory effects: list is destructively modified. */
657 static void
unfold_loop(struct format_arg_list * list,unsigned int m)658 unfold_loop (struct format_arg_list *list, unsigned int m)
659 {
660 unsigned int i, j, k;
661
662 if (m > 1)
663 {
664 unsigned int newcount = list->repeated.count * m;
665 ensure_repeated_alloc (list, newcount);
666 i = list->repeated.count;
667 for (k = 1; k < m; k++)
668 for (j = 0; j < list->repeated.count; j++, i++)
669 copy_element (&list->repeated.element[i], &list->repeated.element[j]);
670 list->repeated.count = newcount;
671 list->repeated.length = list->repeated.length * m;
672 }
673 }
674
675 /* Ensure list->initial.length := m, where m >= list->initial.length.
676 Assumes list->repeated.count > 0. */
677 /* Memory effects: list is destructively modified. */
678 static void
rotate_loop(struct format_arg_list * list,unsigned int m)679 rotate_loop (struct format_arg_list *list, unsigned int m)
680 {
681 if (m == list->initial.length)
682 return;
683
684 if (list->repeated.count == 1)
685 {
686 /* Instead of multiple copies of list->repeated.element[0], a single
687 copy with higher repcount is appended to list->initial. */
688 unsigned int i, newcount;
689
690 newcount = list->initial.count + 1;
691 ensure_initial_alloc (list, newcount);
692 i = list->initial.count;
693 copy_element (&list->initial.element[i], &list->repeated.element[0]);
694 list->initial.element[i].repcount = m - list->initial.length;
695 list->initial.count = newcount;
696 list->initial.length = m;
697 }
698 else
699 {
700 unsigned int n = list->repeated.length;
701
702 /* Write m = list->initial.length + q * n + r with 0 <= r < n. */
703 unsigned int q = (m - list->initial.length) / n;
704 unsigned int r = (m - list->initial.length) % n;
705
706 /* Determine how many entries of list->repeated are needed for
707 length r. */
708 unsigned int s;
709 unsigned int t;
710
711 for (t = r, s = 0;
712 s < list->repeated.count && t >= list->repeated.element[s].repcount;
713 t -= list->repeated.element[s].repcount, s++)
714 ;
715
716 /* s must be < list->repeated.count, otherwise r would have been >= n. */
717 ASSERT (s < list->repeated.count);
718
719 /* So we need to add to list->initial:
720 q full copies of list->repeated,
721 plus the s first elements of list->repeated,
722 plus, if t > 0, a splitoff of list->repeated.element[s]. */
723 {
724 unsigned int i, j, k, newcount;
725
726 i = list->initial.count;
727 newcount = i + q * list->repeated.count + s + (t > 0 ? 1 : 0);
728 ensure_initial_alloc (list, newcount);
729 for (k = 0; k < q; k++)
730 for (j = 0; j < list->repeated.count; j++, i++)
731 copy_element (&list->initial.element[i],
732 &list->repeated.element[j]);
733 for (j = 0; j < s; j++, i++)
734 copy_element (&list->initial.element[i], &list->repeated.element[j]);
735 if (t > 0)
736 {
737 copy_element (&list->initial.element[i],
738 &list->repeated.element[j]);
739 list->initial.element[i].repcount = t;
740 i++;
741 }
742 ASSERT (i == newcount);
743 list->initial.count = newcount;
744 /* The new length of the initial segment is
745 = list->initial.length
746 + q * list->repeated.length
747 + list->repeated[0..s-1].repcount + t
748 = list->initial.length + q * n + r
749 = m.
750 */
751 list->initial.length = m;
752 }
753
754 /* And rotate list->repeated. */
755 if (r > 0)
756 {
757 unsigned int i, j, oldcount, newcount;
758 struct format_arg *newelement;
759
760 oldcount = list->repeated.count;
761 newcount = list->repeated.count + (t > 0 ? 1 : 0);
762 newelement =
763 (struct format_arg *)
764 xmalloc (newcount * sizeof (struct format_arg));
765 i = 0;
766 for (j = s; j < oldcount; j++, i++)
767 newelement[i] = list->repeated.element[j];
768 for (j = 0; j < s; j++, i++)
769 newelement[i] = list->repeated.element[j];
770 if (t > 0)
771 {
772 copy_element (&newelement[oldcount], &newelement[0]);
773 newelement[0].repcount -= t;
774 newelement[oldcount].repcount = t;
775 }
776 free (list->repeated.element);
777 list->repeated.element = newelement;
778 }
779 }
780 }
781
782
783 /* Ensure index n in the initial segment falls on a split between elements,
784 i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two
785 different adjacent elements. */
786 /* Memory effects: list is destructively modified. */
787 static unsigned int
initial_splitelement(struct format_arg_list * list,unsigned int n)788 initial_splitelement (struct format_arg_list *list, unsigned int n)
789 {
790 unsigned int s;
791 unsigned int t;
792 unsigned int oldrepcount;
793 unsigned int newcount;
794 unsigned int i;
795
796 VERIFY_LIST (list);
797
798 if (n > list->initial.length)
799 {
800 ASSERT (list->repeated.count > 0);
801 rotate_loop (list, n);
802 ASSERT (n <= list->initial.length);
803 }
804
805 /* Determine how many entries of list->initial need to be skipped. */
806 for (t = n, s = 0;
807 s < list->initial.count && t >= list->initial.element[s].repcount;
808 t -= list->initial.element[s].repcount, s++)
809 ;
810
811 if (t == 0)
812 return s;
813
814 ASSERT (s < list->initial.count);
815
816 /* Split the entry into two entries. */
817 oldrepcount = list->initial.element[s].repcount;
818 newcount = list->initial.count + 1;
819 ensure_initial_alloc (list, newcount);
820 for (i = list->initial.count - 1; i > s; i--)
821 list->initial.element[i+1] = list->initial.element[i];
822 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
823 list->initial.element[s].repcount = t;
824 list->initial.element[s+1].repcount = oldrepcount - t;
825 list->initial.count = newcount;
826
827 VERIFY_LIST (list);
828
829 return s+1;
830 }
831
832
833 /* Ensure index n in the initial segment is not shared. Return its index. */
834 /* Memory effects: list is destructively modified. */
835 static unsigned int
initial_unshare(struct format_arg_list * list,unsigned int n)836 initial_unshare (struct format_arg_list *list, unsigned int n)
837 {
838 /* This does the same side effects as
839 initial_splitelement (list, n);
840 initial_splitelement (list, n + 1);
841 */
842 unsigned int s;
843 unsigned int t;
844
845 VERIFY_LIST (list);
846
847 if (n >= list->initial.length)
848 {
849 ASSERT (list->repeated.count > 0);
850 rotate_loop (list, n + 1);
851 ASSERT (n < list->initial.length);
852 }
853
854 /* Determine how many entries of list->initial need to be skipped. */
855 for (t = n, s = 0;
856 s < list->initial.count && t >= list->initial.element[s].repcount;
857 t -= list->initial.element[s].repcount, s++)
858 ;
859
860 /* s must be < list->initial.count. */
861 ASSERT (s < list->initial.count);
862
863 if (list->initial.element[s].repcount > 1)
864 {
865 /* Split the entry into at most three entries: for indices < n,
866 for index n, and for indices > n. */
867 unsigned int oldrepcount = list->initial.element[s].repcount;
868 unsigned int newcount =
869 list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2);
870 ensure_initial_alloc (list, newcount);
871 if (t == 0 || t == oldrepcount - 1)
872 {
873 unsigned int i;
874
875 for (i = list->initial.count - 1; i > s; i--)
876 list->initial.element[i+1] = list->initial.element[i];
877 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
878 if (t == 0)
879 {
880 list->initial.element[s].repcount = 1;
881 list->initial.element[s+1].repcount = oldrepcount - 1;
882 }
883 else
884 {
885 list->initial.element[s].repcount = oldrepcount - 1;
886 list->initial.element[s+1].repcount = 1;
887 }
888 }
889 else
890 {
891 unsigned int i;
892
893 for (i = list->initial.count - 1; i > s; i--)
894 list->initial.element[i+2] = list->initial.element[i];
895 copy_element (&list->initial.element[s+2], &list->initial.element[s]);
896 copy_element (&list->initial.element[s+1], &list->initial.element[s]);
897 list->initial.element[s].repcount = t;
898 list->initial.element[s+1].repcount = 1;
899 list->initial.element[s+2].repcount = oldrepcount - 1 - t;
900 }
901 list->initial.count = newcount;
902 if (t > 0)
903 s++;
904 }
905
906 /* Now the entry for index n has repcount 1. */
907 ASSERT (list->initial.element[s].repcount == 1);
908
909 VERIFY_LIST (list);
910
911 return s;
912 }
913
914
915 /* Add n unconstrained elements at the front of the list. */
916 /* Memory effects: list is destructively modified. */
917 static void
shift_list(struct format_arg_list * list,unsigned int n)918 shift_list (struct format_arg_list *list, unsigned int n)
919 {
920 VERIFY_LIST (list);
921
922 if (n > 0)
923 {
924 unsigned int i;
925
926 grow_initial_alloc (list);
927 for (i = list->initial.count; i > 0; i--)
928 list->initial.element[i] = list->initial.element[i-1];
929 list->initial.element[0].repcount = n;
930 list->initial.element[0].presence = FCT_REQUIRED;
931 list->initial.element[0].type = FAT_OBJECT;
932 list->initial.count++;
933 list->initial.length += n;
934
935 normalize_outermost_list (list);
936 }
937
938 VERIFY_LIST (list);
939 }
940
941
942 /* ================= Intersection of two format_arg_lists ================= */
943
944 /* Create the intersection (i.e. combined constraints) of two argument
945 constraints. Return false if the intersection is empty, i.e. if the
946 two constraints give a contradiction. */
947 /* Memory effects: Freshly allocated element's sublist. */
948 static bool
make_intersected_element(struct format_arg * re,const struct format_arg * e1,const struct format_arg * e2)949 make_intersected_element (struct format_arg *re,
950 const struct format_arg * e1,
951 const struct format_arg * e2)
952 {
953 /* Intersect the cdr types. */
954 if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED)
955 re->presence = FCT_REQUIRED;
956 else
957 re->presence = FCT_OPTIONAL;
958
959 /* Intersect the arg types. */
960 if (e1->type == FAT_OBJECT)
961 {
962 re->type = e2->type;
963 if (re->type == FAT_LIST)
964 re->list = copy_list (e2->list);
965 }
966 else if (e2->type == FAT_OBJECT)
967 {
968 re->type = e1->type;
969 if (re->type == FAT_LIST)
970 re->list = copy_list (e1->list);
971 }
972 else if (e1->type == FAT_LIST
973 && (e2->type == FAT_CHARACTER_INTEGER_NULL
974 || e2->type == FAT_CHARACTER_NULL
975 || e2->type == FAT_INTEGER_NULL))
976 {
977 re->type = e1->type;
978 re->list = make_intersection_with_empty_list (e1->list);
979 if (re->list == NULL)
980 return false;
981 }
982 else if (e2->type == FAT_LIST
983 && (e1->type == FAT_CHARACTER_INTEGER_NULL
984 || e1->type == FAT_CHARACTER_NULL
985 || e1->type == FAT_INTEGER_NULL))
986 {
987 re->type = e2->type;
988 re->list = make_intersection_with_empty_list (e2->list);
989 if (re->list == NULL)
990 return false;
991 }
992 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
993 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
994 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
995 {
996 re->type = e2->type;
997 }
998 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
999 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
1000 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1001 {
1002 re->type = e1->type;
1003 }
1004 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1005 {
1006 re->type = e2->type;
1007 }
1008 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1009 {
1010 re->type = e1->type;
1011 }
1012 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1013 {
1014 re->type = e2->type;
1015 }
1016 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1017 {
1018 re->type = e1->type;
1019 }
1020 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1021 {
1022 re->type = e2->type;
1023 }
1024 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1025 {
1026 re->type = e1->type;
1027 }
1028 else if (e1->type == e2->type)
1029 {
1030 re->type = e1->type;
1031 if (re->type == FAT_LIST)
1032 {
1033 re->list = make_intersected_list (copy_list (e1->list),
1034 copy_list (e2->list));
1035 if (re->list == NULL)
1036 return false;
1037 }
1038 }
1039 else
1040 /* Each of FAT_CHARACTER, FAT_INTEGER, FAT_LIST, FAT_FORMATSTRING,
1041 FAT_FUNCTION matches only itself. Contradiction. */
1042 return false;
1043
1044 return true;
1045 }
1046
1047 /* Append list->repeated to list->initial, and clear list->repeated. */
1048 /* Memory effects: list is destructively modified. */
1049 static void
append_repeated_to_initial(struct format_arg_list * list)1050 append_repeated_to_initial (struct format_arg_list *list)
1051 {
1052 if (list->repeated.count > 0)
1053 {
1054 /* Move list->repeated over to list->initial. */
1055 unsigned int i, j, newcount;
1056
1057 newcount = list->initial.count + list->repeated.count;
1058 ensure_initial_alloc (list, newcount);
1059 i = list->initial.count;
1060 for (j = 0; j < list->repeated.count; j++, i++)
1061 list->initial.element[i] = list->repeated.element[j];
1062 list->initial.count = newcount;
1063 list->initial.length = list->initial.length + list->repeated.length;
1064 free (list->repeated.element);
1065 list->repeated.element = NULL;
1066 list->repeated.allocated = 0;
1067 list->repeated.count = 0;
1068 list->repeated.length = 0;
1069 }
1070 }
1071
1072 /* Handle a contradiction during building of a format_arg_list.
1073 The list consists only of an initial segment. The repeated segment is
1074 empty. This function searches the last FCT_OPTIONAL and cuts off the
1075 list at this point, or - if none is found - returns NULL. */
1076 /* Memory effects: list is destructively modified. If NULL is returned,
1077 list is freed. */
1078 static struct format_arg_list *
backtrack_in_initial(struct format_arg_list * list)1079 backtrack_in_initial (struct format_arg_list *list)
1080 {
1081 ASSERT (list->repeated.count == 0);
1082
1083 while (list->initial.count > 0)
1084 {
1085 unsigned int i = list->initial.count - 1;
1086 if (list->initial.element[i].presence == FCT_REQUIRED)
1087 {
1088 /* Throw away this element. */
1089 list->initial.length -= list->initial.element[i].repcount;
1090 free_element (&list->initial.element[i]);
1091 list->initial.count = i;
1092 }
1093 else /* list->initial.element[i].presence == FCT_OPTIONAL */
1094 {
1095 /* The list must end here. */
1096 list->initial.length--;
1097 if (list->initial.element[i].repcount > 1)
1098 list->initial.element[i].repcount--;
1099 else
1100 {
1101 free_element (&list->initial.element[i]);
1102 list->initial.count = i;
1103 }
1104 VERIFY_LIST (list);
1105 return list;
1106 }
1107 }
1108
1109 free_list (list);
1110 return NULL;
1111 }
1112
1113 /* Create the intersection (i.e. combined constraints) of two argument list
1114 constraints. Free both argument lists when done. Return NULL if the
1115 intersection is empty, i.e. if the two constraints give a contradiction. */
1116 /* Memory effects: list1 and list2 are freed. The result, if non-NULL, is
1117 freshly allocated. */
1118 static struct format_arg_list *
make_intersected_list(struct format_arg_list * list1,struct format_arg_list * list2)1119 make_intersected_list (struct format_arg_list *list1,
1120 struct format_arg_list *list2)
1121 {
1122 struct format_arg_list *result;
1123
1124 VERIFY_LIST (list1);
1125 VERIFY_LIST (list2);
1126
1127 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1128 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1129 {
1130 unsigned int n1 = list1->repeated.length;
1131 unsigned int n2 = list2->repeated.length;
1132 unsigned int g = gcd (n1, n2);
1133 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1134 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1135
1136 unfold_loop (list1, m1);
1137 unfold_loop (list2, m2);
1138 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1139 }
1140
1141 if (list1->repeated.length > 0 || list2->repeated.length > 0)
1142 /* Step 2: Ensure the initial segment of the result can be computed
1143 from the initial segments of list1 and list2. If both have a
1144 repeated segment, this means to ensure
1145 list1->initial.length == list2->initial.length. */
1146 {
1147 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1148
1149 if (list1->repeated.length > 0)
1150 rotate_loop (list1, m);
1151 if (list2->repeated.length > 0)
1152 rotate_loop (list2, m);
1153 }
1154
1155 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1156 {
1157 ASSERT (list1->initial.length == list2->initial.length);
1158 ASSERT (list1->repeated.length == list2->repeated.length);
1159 }
1160
1161 /* Step 3: Allocate the result. */
1162 result =
1163 (struct format_arg_list *) xmalloc (sizeof (struct format_arg_list));
1164 result->initial.count = 0;
1165 result->initial.allocated = 0;
1166 result->initial.element = NULL;
1167 result->initial.length = 0;
1168 result->repeated.count = 0;
1169 result->repeated.allocated = 0;
1170 result->repeated.element = NULL;
1171 result->repeated.length = 0;
1172
1173 /* Step 4: Elementwise intersection of list1->initial, list2->initial. */
1174 {
1175 struct format_arg *e1;
1176 struct format_arg *e2;
1177 unsigned int c1;
1178 unsigned int c2;
1179
1180 e1 = list1->initial.element; c1 = list1->initial.count;
1181 e2 = list2->initial.element; c2 = list2->initial.count;
1182 while (c1 > 0 && c2 > 0)
1183 {
1184 struct format_arg *re;
1185
1186 /* Ensure room in result->initial. */
1187 grow_initial_alloc (result);
1188 re = &result->initial.element[result->initial.count];
1189 re->repcount = MIN (e1->repcount, e2->repcount);
1190
1191 /* Intersect the argument types. */
1192 if (!make_intersected_element (re, e1, e2))
1193 {
1194 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1195 if (re->presence == FCT_REQUIRED)
1196 /* Contradiction. Backtrack. */
1197 result = backtrack_in_initial (result);
1198 goto done;
1199 }
1200
1201 result->initial.count++;
1202 result->initial.length += re->repcount;
1203
1204 e1->repcount -= re->repcount;
1205 if (e1->repcount == 0)
1206 {
1207 e1++;
1208 c1--;
1209 }
1210 e2->repcount -= re->repcount;
1211 if (e2->repcount == 0)
1212 {
1213 e2++;
1214 c2--;
1215 }
1216 }
1217
1218 if (list1->repeated.count == 0 && list2->repeated.count == 0)
1219 {
1220 /* Intersecting two finite lists. */
1221 if (c1 > 0)
1222 {
1223 /* list1 longer than list2. */
1224 if (e1->presence == FCT_REQUIRED)
1225 /* Contradiction. Backtrack. */
1226 result = backtrack_in_initial (result);
1227 }
1228 else if (c2 > 0)
1229 {
1230 /* list2 longer than list1. */
1231 if (e2->presence == FCT_REQUIRED)
1232 /* Contradiction. Backtrack. */
1233 result = backtrack_in_initial (result);
1234 }
1235 goto done;
1236 }
1237 else if (list1->repeated.count == 0)
1238 {
1239 /* Intersecting a finite and an infinite list. */
1240 ASSERT (c1 == 0);
1241 if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence)
1242 == FCT_REQUIRED)
1243 /* Contradiction. Backtrack. */
1244 result = backtrack_in_initial (result);
1245 goto done;
1246 }
1247 else if (list2->repeated.count == 0)
1248 {
1249 /* Intersecting an infinite and a finite list. */
1250 ASSERT (c2 == 0);
1251 if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence)
1252 == FCT_REQUIRED)
1253 /* Contradiction. Backtrack. */
1254 result = backtrack_in_initial (result);
1255 goto done;
1256 }
1257 /* Intersecting two infinite lists. */
1258 ASSERT (c1 == 0 && c2 == 0);
1259 }
1260
1261 /* Step 5: Elementwise intersection of list1->repeated, list2->repeated. */
1262 {
1263 struct format_arg *e1;
1264 struct format_arg *e2;
1265 unsigned int c1;
1266 unsigned int c2;
1267
1268 e1 = list1->repeated.element; c1 = list1->repeated.count;
1269 e2 = list2->repeated.element; c2 = list2->repeated.count;
1270 while (c1 > 0 && c2 > 0)
1271 {
1272 struct format_arg *re;
1273
1274 /* Ensure room in result->repeated. */
1275 grow_repeated_alloc (result);
1276 re = &result->repeated.element[result->repeated.count];
1277 re->repcount = MIN (e1->repcount, e2->repcount);
1278
1279 /* Intersect the argument types. */
1280 if (!make_intersected_element (re, e1, e2))
1281 {
1282 append_repeated_to_initial (result);
1283
1284 /* If re->presence == FCT_OPTIONAL, the result list ends here. */
1285 if (re->presence == FCT_REQUIRED)
1286 /* Contradiction. Backtrack. */
1287 result = backtrack_in_initial (result);
1288
1289 goto done;
1290 }
1291
1292 result->repeated.count++;
1293 result->repeated.length += re->repcount;
1294
1295 e1->repcount -= re->repcount;
1296 if (e1->repcount == 0)
1297 {
1298 e1++;
1299 c1--;
1300 }
1301 e2->repcount -= re->repcount;
1302 if (e2->repcount == 0)
1303 {
1304 e2++;
1305 c2--;
1306 }
1307 }
1308 ASSERT (c1 == 0 && c2 == 0);
1309 }
1310
1311 done:
1312 free_list (list1);
1313 free_list (list2);
1314 if (result != NULL)
1315 {
1316 /* Undo the loop unfolding and unrolling done above. */
1317 normalize_outermost_list (result);
1318 VERIFY_LIST (result);
1319 }
1320 return result;
1321 }
1322
1323
1324 /* Create the intersection of an argument list and the empty list.
1325 Return NULL if the intersection is empty. */
1326 /* Memory effects: The result, if non-NULL, is freshly allocated. */
1327 static struct format_arg_list *
make_intersection_with_empty_list(struct format_arg_list * list)1328 make_intersection_with_empty_list (struct format_arg_list *list)
1329 {
1330 #if 0 /* equivalent but slower */
1331 return make_intersected_list (copy_list (list), make_empty_list ());
1332 #else
1333 if (list->initial.count > 0
1334 ? list->initial.element[0].presence == FCT_REQUIRED
1335 : list->repeated.count > 0
1336 && list->repeated.element[0].presence == FCT_REQUIRED)
1337 return NULL;
1338 else
1339 return make_empty_list ();
1340 #endif
1341 }
1342
1343
1344 #ifdef unused
1345 /* Create the intersection of two argument list constraints. NULL stands
1346 for an impossible situation, i.e. a contradiction. */
1347 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1348 if non-NULL, is freshly allocated. */
1349 static struct format_arg_list *
intersection(struct format_arg_list * list1,struct format_arg_list * list2)1350 intersection (struct format_arg_list *list1, struct format_arg_list *list2)
1351 {
1352 if (list1 != NULL)
1353 {
1354 if (list2 != NULL)
1355 return make_intersected_list (list1, list2);
1356 else
1357 {
1358 free_list (list1);
1359 return NULL;
1360 }
1361 }
1362 else
1363 {
1364 if (list2 != NULL)
1365 {
1366 free_list (list2);
1367 return NULL;
1368 }
1369 else
1370 return NULL;
1371 }
1372 }
1373 #endif
1374
1375
1376 /* ===================== Union of two format_arg_lists ===================== */
1377
1378 /* Create the union (i.e. alternative constraints) of two argument
1379 constraints. */
1380 static void
make_union_element(struct format_arg * re,const struct format_arg * e1,const struct format_arg * e2)1381 make_union_element (struct format_arg *re,
1382 const struct format_arg * e1,
1383 const struct format_arg * e2)
1384 {
1385 /* Union of the cdr types. */
1386 if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED)
1387 re->presence = FCT_REQUIRED;
1388 else /* Either one of them is FCT_OPTIONAL. */
1389 re->presence = FCT_OPTIONAL;
1390
1391 /* Union of the arg types. */
1392 if (e1->type == e2->type)
1393 {
1394 re->type = e1->type;
1395 if (re->type == FAT_LIST)
1396 re->list = make_union_list (copy_list (e1->list),
1397 copy_list (e2->list));
1398 }
1399 else if (e1->type == FAT_CHARACTER_INTEGER_NULL
1400 && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER
1401 || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER))
1402 {
1403 re->type = e1->type;
1404 }
1405 else if (e2->type == FAT_CHARACTER_INTEGER_NULL
1406 && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER
1407 || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER))
1408 {
1409 re->type = e2->type;
1410 }
1411 else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER)
1412 {
1413 re->type = e1->type;
1414 }
1415 else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER)
1416 {
1417 re->type = e2->type;
1418 }
1419 else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER)
1420 {
1421 re->type = e1->type;
1422 }
1423 else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER)
1424 {
1425 re->type = e2->type;
1426 }
1427 else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER)
1428 {
1429 re->type = e1->type;
1430 }
1431 else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER)
1432 {
1433 re->type = e2->type;
1434 }
1435 else if (e1->type == FAT_LIST && is_empty_list (e1->list))
1436 {
1437 if (e2->type == FAT_CHARACTER_INTEGER_NULL
1438 || e2->type == FAT_CHARACTER_NULL
1439 || e2->type == FAT_INTEGER_NULL)
1440 re->type = e2->type;
1441 else if (e2->type == FAT_CHARACTER)
1442 re->type = FAT_CHARACTER_NULL;
1443 else if (e2->type == FAT_INTEGER)
1444 re->type = FAT_INTEGER_NULL;
1445 else
1446 re->type = FAT_OBJECT;
1447 }
1448 else if (e2->type == FAT_LIST && is_empty_list (e2->list))
1449 {
1450 if (e1->type == FAT_CHARACTER_INTEGER_NULL
1451 || e1->type == FAT_CHARACTER_NULL
1452 || e1->type == FAT_INTEGER_NULL)
1453 re->type = e1->type;
1454 else if (e1->type == FAT_CHARACTER)
1455 re->type = FAT_CHARACTER_NULL;
1456 else if (e1->type == FAT_INTEGER)
1457 re->type = FAT_INTEGER_NULL;
1458 else
1459 re->type = FAT_OBJECT;
1460 }
1461 else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL)
1462 && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL))
1463 {
1464 re->type = FAT_CHARACTER_INTEGER_NULL;
1465 }
1466 else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL)
1467 && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL))
1468 {
1469 re->type = FAT_CHARACTER_INTEGER_NULL;
1470 }
1471 else
1472 {
1473 /* Other union types are too hard to describe precisely. */
1474 re->type = FAT_OBJECT;
1475 }
1476 }
1477
1478 /* Create the union (i.e. alternative constraints) of two argument list
1479 constraints. Free both argument lists when done. */
1480 /* Memory effects: list1 and list2 are freed. The result is freshly
1481 allocated. */
1482 static struct format_arg_list *
make_union_list(struct format_arg_list * list1,struct format_arg_list * list2)1483 make_union_list (struct format_arg_list *list1, struct format_arg_list *list2)
1484 {
1485 struct format_arg_list *result;
1486
1487 VERIFY_LIST (list1);
1488 VERIFY_LIST (list2);
1489
1490 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1491 {
1492 /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */
1493 {
1494 unsigned int n1 = list1->repeated.length;
1495 unsigned int n2 = list2->repeated.length;
1496 unsigned int g = gcd (n1, n2);
1497 unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */
1498 unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */
1499
1500 unfold_loop (list1, m1);
1501 unfold_loop (list2, m2);
1502 /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */
1503 }
1504
1505 /* Step 2: Ensure that list1->initial.length == list2->initial.length. */
1506 {
1507 unsigned int m = MAX (list1->initial.length, list2->initial.length);
1508
1509 rotate_loop (list1, m);
1510 rotate_loop (list2, m);
1511 }
1512
1513 ASSERT (list1->initial.length == list2->initial.length);
1514 ASSERT (list1->repeated.length == list2->repeated.length);
1515 }
1516 else if (list1->repeated.length > 0)
1517 {
1518 /* Ensure the initial segment of the result can be computed from the
1519 initial segment of list1. */
1520 if (list2->initial.length >= list1->initial.length)
1521 {
1522 rotate_loop (list1, list2->initial.length);
1523 if (list1->repeated.element[0].presence == FCT_REQUIRED)
1524 rotate_loop (list1, list1->initial.length + 1);
1525 }
1526 }
1527 else if (list2->repeated.length > 0)
1528 {
1529 /* Ensure the initial segment of the result can be computed from the
1530 initial segment of list2. */
1531 if (list1->initial.length >= list2->initial.length)
1532 {
1533 rotate_loop (list2, list1->initial.length);
1534 if (list2->repeated.element[0].presence == FCT_REQUIRED)
1535 rotate_loop (list2, list2->initial.length + 1);
1536 }
1537 }
1538
1539 /* Step 3: Allocate the result. */
1540 result =
1541 (struct format_arg_list *) xmalloc (sizeof (struct format_arg_list));
1542 result->initial.count = 0;
1543 result->initial.allocated = 0;
1544 result->initial.element = NULL;
1545 result->initial.length = 0;
1546 result->repeated.count = 0;
1547 result->repeated.allocated = 0;
1548 result->repeated.element = NULL;
1549 result->repeated.length = 0;
1550
1551 /* Step 4: Elementwise union of list1->initial, list2->initial. */
1552 {
1553 struct format_arg *e1;
1554 struct format_arg *e2;
1555 unsigned int c1;
1556 unsigned int c2;
1557
1558 e1 = list1->initial.element; c1 = list1->initial.count;
1559 e2 = list2->initial.element; c2 = list2->initial.count;
1560 while (c1 > 0 && c2 > 0)
1561 {
1562 struct format_arg *re;
1563
1564 /* Ensure room in result->initial. */
1565 grow_initial_alloc (result);
1566 re = &result->initial.element[result->initial.count];
1567 re->repcount = MIN (e1->repcount, e2->repcount);
1568
1569 /* Union of the argument types. */
1570 make_union_element (re, e1, e2);
1571
1572 result->initial.count++;
1573 result->initial.length += re->repcount;
1574
1575 e1->repcount -= re->repcount;
1576 if (e1->repcount == 0)
1577 {
1578 e1++;
1579 c1--;
1580 }
1581 e2->repcount -= re->repcount;
1582 if (e2->repcount == 0)
1583 {
1584 e2++;
1585 c2--;
1586 }
1587 }
1588
1589 if (c1 > 0)
1590 {
1591 /* list2 already terminated, but still more elements in list1->initial.
1592 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1593 ASSERT (list2->repeated.count == 0);
1594
1595 if (e1->presence == FCT_REQUIRED)
1596 {
1597 struct format_arg *re;
1598
1599 /* Ensure room in result->initial. */
1600 grow_initial_alloc (result);
1601 re = &result->initial.element[result->initial.count];
1602 copy_element (re, e1);
1603 re->presence = FCT_OPTIONAL;
1604 re->repcount = 1;
1605 result->initial.count++;
1606 result->initial.length += 1;
1607 e1->repcount -= 1;
1608 if (e1->repcount == 0)
1609 {
1610 e1++;
1611 c1--;
1612 }
1613 }
1614
1615 /* Ensure room in result->initial. */
1616 ensure_initial_alloc (result, result->initial.count + c1);
1617 while (c1 > 0)
1618 {
1619 struct format_arg *re;
1620
1621 re = &result->initial.element[result->initial.count];
1622 copy_element (re, e1);
1623 result->initial.count++;
1624 result->initial.length += re->repcount;
1625 e1++;
1626 c1--;
1627 }
1628 }
1629 else if (c2 > 0)
1630 {
1631 /* list1 already terminated, but still more elements in list2->initial.
1632 Copy them all, but turn the first presence to FCT_OPTIONAL. */
1633 ASSERT (list1->repeated.count == 0);
1634
1635 if (e2->presence == FCT_REQUIRED)
1636 {
1637 struct format_arg *re;
1638
1639 /* Ensure room in result->initial. */
1640 grow_initial_alloc (result);
1641 re = &result->initial.element[result->initial.count];
1642 copy_element (re, e2);
1643 re->presence = FCT_OPTIONAL;
1644 re->repcount = 1;
1645 result->initial.count++;
1646 result->initial.length += 1;
1647 e2->repcount -= 1;
1648 if (e2->repcount == 0)
1649 {
1650 e2++;
1651 c2--;
1652 }
1653 }
1654
1655 /* Ensure room in result->initial. */
1656 ensure_initial_alloc (result, result->initial.count + c2);
1657 while (c2 > 0)
1658 {
1659 struct format_arg *re;
1660
1661 re = &result->initial.element[result->initial.count];
1662 copy_element (re, e2);
1663 result->initial.count++;
1664 result->initial.length += re->repcount;
1665 e2++;
1666 c2--;
1667 }
1668 }
1669 ASSERT (c1 == 0 && c2 == 0);
1670 }
1671
1672 if (list1->repeated.length > 0 && list2->repeated.length > 0)
1673 /* Step 5: Elementwise union of list1->repeated, list2->repeated. */
1674 {
1675 struct format_arg *e1;
1676 struct format_arg *e2;
1677 unsigned int c1;
1678 unsigned int c2;
1679
1680 e1 = list1->repeated.element; c1 = list1->repeated.count;
1681 e2 = list2->repeated.element; c2 = list2->repeated.count;
1682 while (c1 > 0 && c2 > 0)
1683 {
1684 struct format_arg *re;
1685
1686 /* Ensure room in result->repeated. */
1687 grow_repeated_alloc (result);
1688 re = &result->repeated.element[result->repeated.count];
1689 re->repcount = MIN (e1->repcount, e2->repcount);
1690
1691 /* Union of the argument types. */
1692 make_union_element (re, e1, e2);
1693
1694 result->repeated.count++;
1695 result->repeated.length += re->repcount;
1696
1697 e1->repcount -= re->repcount;
1698 if (e1->repcount == 0)
1699 {
1700 e1++;
1701 c1--;
1702 }
1703 e2->repcount -= re->repcount;
1704 if (e2->repcount == 0)
1705 {
1706 e2++;
1707 c2--;
1708 }
1709 }
1710 ASSERT (c1 == 0 && c2 == 0);
1711 }
1712 else if (list1->repeated.length > 0)
1713 {
1714 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1715 initial segment. Just copy the repeated segment of list1. */
1716 unsigned int i;
1717
1718 result->repeated.count = list1->repeated.count;
1719 result->repeated.allocated = result->repeated.count;
1720 result->repeated.element =
1721 (struct format_arg *)
1722 xmalloc (result->repeated.allocated * sizeof (struct format_arg));
1723 for (i = 0; i < list1->repeated.count; i++)
1724 copy_element (&result->repeated.element[i],
1725 &list1->repeated.element[i]);
1726 result->repeated.length = list1->repeated.length;
1727 }
1728 else if (list2->repeated.length > 0)
1729 {
1730 /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the
1731 initial segment. Just copy the repeated segment of list2. */
1732 unsigned int i;
1733
1734 result->repeated.count = list2->repeated.count;
1735 result->repeated.allocated = result->repeated.count;
1736 result->repeated.element =
1737 (struct format_arg *)
1738 xmalloc (result->repeated.allocated * sizeof (struct format_arg));
1739 for (i = 0; i < list2->repeated.count; i++)
1740 copy_element (&result->repeated.element[i],
1741 &list2->repeated.element[i]);
1742 result->repeated.length = list2->repeated.length;
1743 }
1744
1745 free_list (list1);
1746 free_list (list2);
1747 /* Undo the loop unfolding and unrolling done above. */
1748 normalize_outermost_list (result);
1749 VERIFY_LIST (result);
1750 return result;
1751 }
1752
1753
1754 /* Create the union of an argument list and the empty list. */
1755 /* Memory effects: list is freed. The result is freshly allocated. */
1756 static struct format_arg_list *
make_union_with_empty_list(struct format_arg_list * list)1757 make_union_with_empty_list (struct format_arg_list *list)
1758 {
1759 #if 0 /* equivalent but slower */
1760 return make_union_list (list, make_empty_list ());
1761 #else
1762 VERIFY_LIST (list);
1763
1764 if (list->initial.count > 0
1765 ? list->initial.element[0].presence == FCT_REQUIRED
1766 : list->repeated.count > 0
1767 && list->repeated.element[0].presence == FCT_REQUIRED)
1768 {
1769 initial_splitelement (list, 1);
1770 ASSERT (list->initial.count > 0);
1771 ASSERT (list->initial.element[0].repcount == 1);
1772 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
1773 list->initial.element[0].presence = FCT_OPTIONAL;
1774
1775 /* We might need to merge list->initial.element[0] and
1776 list->initial.element[1]. */
1777 normalize_outermost_list (list);
1778 }
1779
1780 VERIFY_LIST (list);
1781
1782 return list;
1783 #endif
1784 }
1785
1786
1787 /* Create the union of two argument list constraints. NULL stands for an
1788 impossible situation, i.e. a contradiction. */
1789 /* Memory effects: list1 and list2 are freed if non-NULL. The result,
1790 if non-NULL, is freshly allocated. */
1791 static struct format_arg_list *
1792 union (struct format_arg_list *list1, struct format_arg_list *list2)
1793 {
1794 if (list1 != NULL)
1795 {
1796 if (list2 != NULL)
1797 return make_union_list (list1, list2);
1798 else
1799 return list1;
1800 }
1801 else
1802 {
1803 if (list2 != NULL)
1804 return list2;
1805 else
1806 return NULL;
1807 }
1808 }
1809
1810
1811 /* =========== Adding specific constraints to a format_arg_list =========== */
1812
1813
1814 /* Test whether arguments 0..n are required arguments in a list. */
1815 static bool
is_required(const struct format_arg_list * list,unsigned int n)1816 is_required (const struct format_arg_list *list, unsigned int n)
1817 {
1818 unsigned int s;
1819 unsigned int t;
1820
1821 /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */
1822 t = n + 1;
1823
1824 /* Walk the list->initial segment. */
1825 for (s = 0;
1826 s < list->initial.count && t >= list->initial.element[s].repcount;
1827 t -= list->initial.element[s].repcount, s++)
1828 if (list->initial.element[s].presence != FCT_REQUIRED)
1829 return false;
1830
1831 if (t == 0)
1832 return true;
1833
1834 if (s < list->initial.count)
1835 {
1836 if (list->initial.element[s].presence != FCT_REQUIRED)
1837 return false;
1838 else
1839 return true;
1840 }
1841
1842 /* Walk the list->repeated segment. */
1843 if (list->repeated.count == 0)
1844 return false;
1845
1846 for (s = 0;
1847 s < list->repeated.count && t >= list->repeated.element[s].repcount;
1848 t -= list->repeated.element[s].repcount, s++)
1849 if (list->repeated.element[s].presence != FCT_REQUIRED)
1850 return false;
1851
1852 if (t == 0)
1853 return true;
1854
1855 if (s < list->repeated.count)
1856 {
1857 if (list->repeated.element[s].presence != FCT_REQUIRED)
1858 return false;
1859 else
1860 return true;
1861 }
1862
1863 /* The list->repeated segment consists only of FCT_REQUIRED. So,
1864 regardless how many more passes through list->repeated would be
1865 needed until t becomes 0, the result is true. */
1866 return true;
1867 }
1868
1869
1870 /* Add a constraint to an argument list, namely that the arguments 0...n are
1871 present. NULL stands for an impossible situation, i.e. a contradiction. */
1872 /* Memory effects: list is freed. The result is freshly allocated. */
1873 static struct format_arg_list *
add_required_constraint(struct format_arg_list * list,unsigned int n)1874 add_required_constraint (struct format_arg_list *list, unsigned int n)
1875 {
1876 unsigned int i, rest;
1877
1878 if (list == NULL)
1879 return NULL;
1880
1881 VERIFY_LIST (list);
1882
1883 if (list->repeated.count == 0 && list->initial.length <= n)
1884 {
1885 /* list is already constrained to have at most length n.
1886 Contradiction. */
1887 free_list (list);
1888 return NULL;
1889 }
1890
1891 initial_splitelement (list, n + 1);
1892
1893 for (i = 0, rest = n + 1; rest > 0; )
1894 {
1895 list->initial.element[i].presence = FCT_REQUIRED;
1896 rest -= list->initial.element[i].repcount;
1897 i++;
1898 }
1899
1900 VERIFY_LIST (list);
1901
1902 return list;
1903 }
1904
1905
1906 /* Add a constraint to an argument list, namely that the argument n is
1907 never present. NULL stands for an impossible situation, i.e. a
1908 contradiction. */
1909 /* Memory effects: list is freed. The result is freshly allocated. */
1910 static struct format_arg_list *
add_end_constraint(struct format_arg_list * list,unsigned int n)1911 add_end_constraint (struct format_arg_list *list, unsigned int n)
1912 {
1913 unsigned int s, i;
1914 enum format_cdr_type n_presence;
1915
1916 if (list == NULL)
1917 return NULL;
1918
1919 VERIFY_LIST (list);
1920
1921 if (list->repeated.count == 0 && list->initial.length <= n)
1922 /* list is already constrained to have at most length n. */
1923 return list;
1924
1925 s = initial_splitelement (list, n);
1926 n_presence =
1927 (s < list->initial.count
1928 ? /* n < list->initial.length */ list->initial.element[s].presence
1929 : /* n >= list->initial.length */ list->repeated.element[0].presence);
1930
1931 for (i = s; i < list->initial.count; i++)
1932 {
1933 list->initial.length -= list->initial.element[i].repcount;
1934 free_element (&list->initial.element[i]);
1935 }
1936 list->initial.count = s;
1937
1938 for (i = 0; i < list->repeated.count; i++)
1939 free_element (&list->repeated.element[i]);
1940 if (list->repeated.element != NULL)
1941 free (list->repeated.element);
1942 list->repeated.element = NULL;
1943 list->repeated.allocated = 0;
1944 list->repeated.count = 0;
1945 list->repeated.length = 0;
1946
1947 if (n_presence == FCT_REQUIRED)
1948 return backtrack_in_initial (list);
1949 else
1950 return list;
1951 }
1952
1953
1954 /* Add a constraint to an argument list, namely that the argument n is
1955 of a given type. NULL stands for an impossible situation, i.e. a
1956 contradiction. Assumes a preceding add_required_constraint (list, n). */
1957 /* Memory effects: list is freed. The result is freshly allocated. */
1958 static struct format_arg_list *
add_type_constraint(struct format_arg_list * list,unsigned int n,enum format_arg_type type)1959 add_type_constraint (struct format_arg_list *list, unsigned int n,
1960 enum format_arg_type type)
1961 {
1962 unsigned int s;
1963 struct format_arg newconstraint;
1964 struct format_arg tmpelement;
1965
1966 if (list == NULL)
1967 return NULL;
1968
1969 /* Through the previous add_required_constraint, we can assume
1970 list->initial.length >= n+1. */
1971
1972 s = initial_unshare (list, n);
1973
1974 newconstraint.presence = FCT_OPTIONAL;
1975 newconstraint.type = type;
1976 if (!make_intersected_element (&tmpelement,
1977 &list->initial.element[s], &newconstraint))
1978 return add_end_constraint (list, n);
1979 free_element (&list->initial.element[s]);
1980 list->initial.element[s].type = tmpelement.type;
1981 list->initial.element[s].list = tmpelement.list;
1982
1983 VERIFY_LIST (list);
1984
1985 return list;
1986 }
1987
1988
1989 /* Add a constraint to an argument list, namely that the argument n is
1990 of a given list type. NULL stands for an impossible situation, i.e. a
1991 contradiction. Assumes a preceding add_required_constraint (list, n). */
1992 /* Memory effects: list is freed. The result is freshly allocated. */
1993 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)1994 add_listtype_constraint (struct format_arg_list *list, unsigned int n,
1995 enum format_arg_type type,
1996 struct format_arg_list *sublist)
1997 {
1998 unsigned int s;
1999 struct format_arg newconstraint;
2000 struct format_arg tmpelement;
2001
2002 if (list == NULL)
2003 return NULL;
2004
2005 /* Through the previous add_required_constraint, we can assume
2006 list->initial.length >= n+1. */
2007
2008 s = initial_unshare (list, n);
2009
2010 newconstraint.presence = FCT_OPTIONAL;
2011 newconstraint.type = type;
2012 newconstraint.list = sublist;
2013 if (!make_intersected_element (&tmpelement,
2014 &list->initial.element[s], &newconstraint))
2015 return add_end_constraint (list, n);
2016 free_element (&list->initial.element[s]);
2017 list->initial.element[s].type = tmpelement.type;
2018 list->initial.element[s].list = tmpelement.list;
2019
2020 VERIFY_LIST (list);
2021
2022 return list;
2023 }
2024
2025
2026 /* ============= Subroutines used by the format string parser ============= */
2027
2028 static void
add_req_type_constraint(struct format_arg_list ** listp,unsigned int position,enum format_arg_type type)2029 add_req_type_constraint (struct format_arg_list **listp,
2030 unsigned int position, enum format_arg_type type)
2031 {
2032 *listp = add_required_constraint (*listp, position);
2033 *listp = add_type_constraint (*listp, position, type);
2034 }
2035
2036
2037 static void
add_req_listtype_constraint(struct format_arg_list ** listp,unsigned int position,enum format_arg_type type,struct format_arg_list * sublist)2038 add_req_listtype_constraint (struct format_arg_list **listp,
2039 unsigned int position, enum format_arg_type type,
2040 struct format_arg_list *sublist)
2041 {
2042 *listp = add_required_constraint (*listp, position);
2043 *listp = add_listtype_constraint (*listp, position, type, sublist);
2044 }
2045
2046
2047 /* Create an endless repeated list whose elements are lists constrained
2048 by sublist. */
2049 /* Memory effects: sublist is freed. The result is freshly allocated. */
2050 static struct format_arg_list *
make_repeated_list_of_lists(struct format_arg_list * sublist)2051 make_repeated_list_of_lists (struct format_arg_list *sublist)
2052 {
2053 if (sublist == NULL)
2054 /* The list cannot have a single element. */
2055 return make_empty_list ();
2056 else
2057 {
2058 struct format_arg_list *listlist;
2059
2060 listlist =
2061 (struct format_arg_list *) xmalloc (sizeof (struct format_arg_list));
2062
2063 listlist->initial.count = 0;
2064 listlist->initial.allocated = 0;
2065 listlist->initial.element = NULL;
2066 listlist->initial.length = 0;
2067 listlist->repeated.count = 1;
2068 listlist->repeated.allocated = 1;
2069 listlist->repeated.element =
2070 (struct format_arg *) xmalloc (1 * sizeof (struct format_arg));
2071 listlist->repeated.element[0].repcount = 1;
2072 listlist->repeated.element[0].presence = FCT_OPTIONAL;
2073 listlist->repeated.element[0].type = FAT_LIST;
2074 listlist->repeated.element[0].list = sublist;
2075 listlist->repeated.length = 1;
2076
2077 VERIFY_LIST (listlist);
2078
2079 return listlist;
2080 }
2081 }
2082
2083
2084 /* Create an endless repeated list which represents the union of a finite
2085 number of copies of L, each time shifted by period:
2086 ()
2087 L
2088 L and (*^period L)
2089 L and (*^period L) and (*^{2 period} L)
2090 L and (*^period L) and (*^{2 period} L) and (*^{3 period} L)
2091 ...
2092 */
2093 /* Memory effects: sublist is freed. The result is freshly allocated. */
2094 static struct format_arg_list *
make_repeated_list(struct format_arg_list * sublist,unsigned int period)2095 make_repeated_list (struct format_arg_list *sublist, unsigned int period)
2096 {
2097 struct segment tmp;
2098 struct segment *srcseg;
2099 struct format_arg_list *list;
2100 unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount;
2101 bool ended;
2102
2103 VERIFY_LIST (sublist);
2104
2105 ASSERT (period > 0);
2106
2107 if (sublist->repeated.count == 0)
2108 {
2109 /* L is a finite list. */
2110
2111 if (sublist->initial.length < period)
2112 /* L and (*^period L) is a contradition, so we need to consider
2113 only 1 and 0 iterations. */
2114 return make_union_with_empty_list (sublist);
2115
2116 srcseg = &sublist->initial;
2117 p = period;
2118 }
2119 else
2120 {
2121 /* L is an infinite list. */
2122 /* p := lcm (period, period of L) */
2123 unsigned int Lp = sublist->repeated.length;
2124 unsigned int m = period / gcd (period, Lp); /* = lcm(period,Lp) / Lp */
2125
2126 unfold_loop (sublist, m);
2127 p = m * Lp;
2128
2129 /* Concatenate the initial and the repeated segments into a single
2130 segment. */
2131 tmp.count = sublist->initial.count + sublist->repeated.count;
2132 tmp.allocated = tmp.count;
2133 tmp.element =
2134 (struct format_arg *)
2135 xmalloc (tmp.allocated * sizeof (struct format_arg));
2136 for (i = 0; i < sublist->initial.count; i++)
2137 tmp.element[i] = sublist->initial.element[i];
2138 for (j = 0; j < sublist->repeated.count; i++, j++)
2139 tmp.element[i] = sublist->initial.element[j];
2140 tmp.length = sublist->initial.length + sublist->repeated.length;
2141
2142 srcseg = &tmp;
2143 }
2144
2145 n = srcseg->length;
2146
2147 /* Example: n = 7, p = 2
2148 Let L = (A B C D E F G).
2149
2150 L = A B C D E F G
2151 L & L<<p = A B C&A D&B E&C F&D G&E
2152 L & L<<p & L<<2p = A B C&A D&B E&C&A F&D&B G&E&C
2153 ... = A B C&A D&B E&C&A F&D&B G&E&C&A
2154
2155 Thus the result has an initial segment of length n - p and a period
2156 of p, and can be computed by floor(n/p) intersection operations.
2157 Or by a single incremental intersection operation, going from left
2158 to right. */
2159
2160 list = (struct format_arg_list *) xmalloc (sizeof (struct format_arg_list));
2161 list->initial.count = 0;
2162 list->initial.allocated = 0;
2163 list->initial.element = NULL;
2164 list->initial.length = 0;
2165 list->repeated.count = 0;
2166 list->repeated.allocated = 0;
2167 list->repeated.element = NULL;
2168 list->repeated.length = 0;
2169
2170 /* Sketch:
2171 for (i = 0; i < p; i++)
2172 list->initial.element[i] = srcseg->element[i];
2173 list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list
2174 for (i = p, j = 0; i < n; i++, j++)
2175 list->initial.element[i] = srcseg->element[i] & list->initial.element[j];
2176 */
2177
2178 ended = false;
2179
2180 i = 0, ti = 0, si = 0;
2181 while (i < p)
2182 {
2183 unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
2184
2185 /* Ensure room in list->initial. */
2186 grow_initial_alloc (list);
2187 copy_element (&list->initial.element[list->initial.count],
2188 &srcseg->element[si]);
2189 list->initial.element[list->initial.count].repcount = k;
2190 list->initial.count++;
2191 list->initial.length += k;
2192
2193 i += k;
2194 ti += k;
2195 if (ti == srcseg->element[si].repcount)
2196 {
2197 ti = 0;
2198 si++;
2199 }
2200 }
2201
2202 ASSERT (list->initial.count > 0);
2203 if (list->initial.element[0].presence == FCT_REQUIRED)
2204 {
2205 initial_splitelement (list, 1);
2206 ASSERT (list->initial.element[0].presence == FCT_REQUIRED);
2207 ASSERT (list->initial.element[0].repcount == 1);
2208 list->initial.element[0].presence = FCT_OPTIONAL;
2209 }
2210
2211 j = 0, tj = 0, sj = 0;
2212 while (i < n)
2213 {
2214 unsigned int k =
2215 MIN (srcseg->element[si].repcount - ti,
2216 list->initial.element[sj].repcount - tj);
2217
2218 /* Ensure room in list->initial. */
2219 grow_initial_alloc (list);
2220 if (!make_intersected_element (&list->initial.element[list->initial.count],
2221 &srcseg->element[si],
2222 &list->initial.element[sj]))
2223 {
2224 if (list->initial.element[list->initial.count].presence == FCT_REQUIRED)
2225 {
2226 /* Contradiction. Backtrack. */
2227 list = backtrack_in_initial (list);
2228 ASSERT (list != NULL); /* at least the empty list is valid */
2229 return list;
2230 }
2231 else
2232 {
2233 /* The list ends here. */
2234 ended = true;
2235 break;
2236 }
2237 }
2238 list->initial.element[list->initial.count].repcount = k;
2239 list->initial.count++;
2240 list->initial.length += k;
2241
2242 i += k;
2243 ti += k;
2244 if (ti == srcseg->element[si].repcount)
2245 {
2246 ti = 0;
2247 si++;
2248 }
2249
2250 j += k;
2251 tj += k;
2252 if (tj == list->initial.element[sj].repcount)
2253 {
2254 tj = 0;
2255 sj++;
2256 }
2257 }
2258 if (!ended)
2259 ASSERT (list->initial.length == n);
2260
2261 /* Add optional exit points at 0, period, 2*period etc.
2262 FIXME: Not sure this is correct in all cases. */
2263 for (i = 0; i < list->initial.length; i += period)
2264 {
2265 si = initial_unshare (list, i);
2266 list->initial.element[si].presence = FCT_OPTIONAL;
2267 }
2268
2269 if (!ended)
2270 {
2271 /* Now split off the repeated part. */
2272 splitindex = initial_splitelement (list, n - p);
2273 newcount = list->initial.count - splitindex;
2274 if (newcount > list->repeated.allocated)
2275 {
2276 list->repeated.allocated = newcount;
2277 list->repeated.element =
2278 (struct format_arg *) xmalloc (newcount * sizeof (struct format_arg));
2279 }
2280 for (i = splitindex, j = 0; i < n; i++, j++)
2281 list->repeated.element[j] = list->initial.element[i];
2282 list->repeated.count = newcount;
2283 list->repeated.length = p;
2284 list->initial.count = splitindex;
2285 list->initial.length = n - p;
2286 }
2287
2288 VERIFY_LIST (list);
2289
2290 return list;
2291 }
2292
2293
2294 /* ================= Handling of format string directives ================= */
2295
2296 /* Possible signatures of format directives. */
2297 static const enum format_arg_type I [1] = { FAT_INTEGER_NULL };
2298 static const enum format_arg_type II [2] = {
2299 FAT_INTEGER_NULL, FAT_INTEGER_NULL
2300 };
2301 static const enum format_arg_type ICCI [4] = {
2302 FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL
2303 };
2304 static const enum format_arg_type IIIC [4] = {
2305 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL
2306 };
2307 static const enum format_arg_type IICCI [5] = {
2308 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL,
2309 FAT_INTEGER_NULL
2310 };
2311 static const enum format_arg_type IIICC [5] = {
2312 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL,
2313 FAT_CHARACTER_NULL
2314 };
2315 static const enum format_arg_type IIIICCC [7] = {
2316 FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL,
2317 FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL
2318 };
2319 static const enum format_arg_type THREE [3] = {
2320 FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL,
2321 FAT_CHARACTER_INTEGER_NULL
2322 };
2323
2324
2325 /* Check the parameters. For V params, add the constraint to the argument
2326 list. Return false and fill in *invalid_reason if the format string is
2327 invalid. */
2328 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)2329 check_params (struct format_arg_list **listp,
2330 unsigned int paramcount, struct param *params,
2331 unsigned int t_count, const enum format_arg_type *t_types,
2332 unsigned int directives, char **invalid_reason)
2333 {
2334 unsigned int orig_paramcount = paramcount;
2335 unsigned int orig_t_count = t_count;
2336
2337 for (; paramcount > 0 && t_count > 0;
2338 params++, paramcount--, t_types++, t_count--)
2339 {
2340 switch (*t_types)
2341 {
2342 case FAT_CHARACTER_INTEGER_NULL:
2343 break;
2344 case FAT_CHARACTER_NULL:
2345 switch (params->type)
2346 {
2347 case PT_NIL: case PT_CHARACTER: case PT_V:
2348 break;
2349 case PT_INTEGER: case PT_ARGCOUNT:
2350 /* wrong param type */
2351 *invalid_reason =
2352 xasprintf (_("In the directive number %u, parameter %u is of type '%s' but a parameter of type '%s' is expected."), directives, orig_paramcount - paramcount + 1, "integer", "character");
2353 return false;
2354 }
2355 break;
2356 case FAT_INTEGER_NULL:
2357 switch (params->type)
2358 {
2359 case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V:
2360 break;
2361 case PT_CHARACTER:
2362 /* wrong param type */
2363 *invalid_reason =
2364 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");
2365 return false;
2366 }
2367 break;
2368 default:
2369 abort ();
2370 }
2371 if (params->type == PT_V)
2372 {
2373 int position = params->value;
2374 if (position >= 0)
2375 add_req_type_constraint (listp, position, *t_types);
2376 }
2377 }
2378
2379 for (; paramcount > 0; params++, paramcount--)
2380 switch (params->type)
2381 {
2382 case PT_NIL:
2383 break;
2384 case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT:
2385 /* too many params for directive */
2386 *invalid_reason =
2387 xasprintf (ngettext ("In the directive number %u, too many parameters are given; expected at most %u parameter.",
2388 "In the directive number %u, too many parameters are given; expected at most %u parameters.",
2389 orig_t_count),
2390 directives, orig_t_count);
2391 return false;
2392 case PT_V:
2393 /* Force argument to be NIL. */
2394 {
2395 int position = params->value;
2396 if (position >= 0)
2397 {
2398 struct format_arg_list *empty_list = make_empty_list ();
2399 add_req_listtype_constraint (listp, position,
2400 FAT_LIST, empty_list);
2401 free_list (empty_list);
2402 }
2403 }
2404 break;
2405 }
2406
2407 return true;
2408 }
2409
2410
2411 /* Handle the parameters, without a priori type information.
2412 For V params, add the constraint to the argument list.
2413 Return false and fill in *invalid_reason if the format string is
2414 invalid. */
2415 static bool
nocheck_params(struct format_arg_list ** listp,unsigned int paramcount,struct param * params,unsigned int directives,char ** invalid_reason)2416 nocheck_params (struct format_arg_list **listp,
2417 unsigned int paramcount, struct param *params,
2418 unsigned int directives, char **invalid_reason)
2419 {
2420 (void) directives;
2421 (void) invalid_reason;
2422
2423 for (; paramcount > 0; params++, paramcount--)
2424 if (params->type == PT_V)
2425 {
2426 int position = params->value;
2427 add_req_type_constraint (listp, position, FAT_CHARACTER_INTEGER_NULL);
2428 }
2429
2430 return true;
2431 }
2432
2433
2434 /* ======================= The format string parser ======================= */
2435
2436 /* Parse a piece of format string, until the matching terminating format
2437 directive is encountered.
2438 format is the remainder of the format string.
2439 position is the position in this argument list, if known, or -1 if unknown.
2440 list represents the argument list constraints at the current parse point.
2441 NULL stands for a contradiction.
2442 escape represents the union of the argument list constraints at all the
2443 currently pending FORMAT-UP-AND-OUT points. NULL stands for a contradiction
2444 or an empty union.
2445 All four are updated upon valid return.
2446 *separatorp is set to true if the parse terminated due to a ~; separator,
2447 more precisely to 2 if with colon, or to 1 if without colon.
2448 spec is the global struct spec.
2449 terminator is the directive that terminates this parse.
2450 separator specifies if ~; separators are allowed.
2451 If the format string is invalid, false is returned and *invalid_reason is
2452 set to an error message explaining why. */
2453 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 ** invalid_reason)2454 parse_upto (const char **formatp,
2455 int *positionp, struct format_arg_list **listp,
2456 struct format_arg_list **escapep, int *separatorp,
2457 struct spec *spec, char terminator, bool separator,
2458 char **invalid_reason)
2459 {
2460 const char *format = *formatp;
2461 int position = *positionp;
2462 struct format_arg_list *list = *listp;
2463 struct format_arg_list *escape = *escapep;
2464
2465 for (; *format != '\0'; )
2466 if (*format++ == '~')
2467 {
2468 bool colon_p = false;
2469 bool atsign_p = false;
2470 unsigned int paramcount = 0;
2471 struct param *params = NULL;
2472
2473 /* Count number of directives. */
2474 spec->directives++;
2475
2476 /* Parse parameters. */
2477 for (;;)
2478 {
2479 enum param_type type = PT_NIL;
2480 int value = 0;
2481
2482 if (c_isdigit (*format))
2483 {
2484 type = PT_INTEGER;
2485 do
2486 {
2487 value = 10 * value + (*format - '0');
2488 format++;
2489 }
2490 while (c_isdigit (*format));
2491 }
2492 else if (*format == '+' || *format == '-')
2493 {
2494 bool negative = (*format == '-');
2495 type = PT_INTEGER;
2496 format++;
2497 if (!c_isdigit (*format))
2498 {
2499 *invalid_reason =
2500 (*format == '\0'
2501 ? INVALID_UNTERMINATED_DIRECTIVE ()
2502 : xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]));
2503 return false;
2504 }
2505 do
2506 {
2507 value = 10 * value + (*format - '0');
2508 format++;
2509 }
2510 while (c_isdigit (*format));
2511 if (negative)
2512 value = -value;
2513 }
2514 else if (*format == '\'')
2515 {
2516 type = PT_CHARACTER;
2517 format++;
2518 if (*format == '\0')
2519 {
2520 *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE ();
2521 return false;
2522 }
2523 format++;
2524 }
2525 else if (*format == 'V' || *format == 'v')
2526 {
2527 type = PT_V;
2528 format++;
2529 value = position;
2530 /* Consumes an argument. */
2531 if (position >= 0)
2532 position++;
2533 }
2534 else if (*format == '#')
2535 {
2536 type = PT_ARGCOUNT;
2537 format++;
2538 }
2539
2540 params =
2541 (struct param *)
2542 xrealloc (params, (paramcount + 1) * sizeof (struct param));
2543 params[paramcount].type = type;
2544 params[paramcount].value = value;
2545 paramcount++;
2546
2547 if (*format == ',')
2548 format++;
2549 else
2550 break;
2551 }
2552
2553 /* Parse modifiers. */
2554 for (;;)
2555 {
2556 if (*format == ':')
2557 {
2558 format++;
2559 colon_p = true;
2560 }
2561 else if (*format == '@')
2562 {
2563 format++;
2564 atsign_p = true;
2565 }
2566 else
2567 break;
2568 }
2569
2570 /* Parse directive. */
2571 switch (*format++)
2572 {
2573 case 'A': case 'a': /* 22.3.4.1 FORMAT-ASCII */
2574 case 'S': case 's': /* 22.3.4.2 FORMAT-S-EXPRESSION */
2575 if (!check_params (&list, paramcount, params, 4, IIIC,
2576 spec->directives, invalid_reason))
2577 return false;
2578 if (position >= 0)
2579 add_req_type_constraint (&list, position++, FAT_OBJECT);
2580 break;
2581
2582 case 'W': case 'w': /* 22.3.4.3 FORMAT-WRITE */
2583 if (!check_params (&list, paramcount, params, 0, NULL,
2584 spec->directives, invalid_reason))
2585 return false;
2586 if (position >= 0)
2587 add_req_type_constraint (&list, position++, FAT_OBJECT);
2588 break;
2589
2590 case 'D': case 'd': /* 22.3.2.2 FORMAT-DECIMAL */
2591 case 'B': case 'b': /* 22.3.2.3 FORMAT-BINARY */
2592 case 'O': case 'o': /* 22.3.2.4 FORMAT-OCTAL */
2593 case 'X': case 'x': /* 22.3.2.5 FORMAT-HEXADECIMAL */
2594 if (!check_params (&list, paramcount, params, 4, ICCI,
2595 spec->directives, invalid_reason))
2596 return false;
2597 if (position >= 0)
2598 add_req_type_constraint (&list, position++, FAT_INTEGER);
2599 break;
2600
2601 case 'R': case 'r': /* 22.3.2.1 FORMAT-RADIX */
2602 if (!check_params (&list, paramcount, params, 5, IICCI,
2603 spec->directives, invalid_reason))
2604 return false;
2605 if (position >= 0)
2606 add_req_type_constraint (&list, position++, FAT_INTEGER);
2607 break;
2608
2609 case 'P': case 'p': /* 22.3.8.3 FORMAT-PLURAL */
2610 if (!check_params (&list, paramcount, params, 0, NULL,
2611 spec->directives, invalid_reason))
2612 return false;
2613 if (colon_p)
2614 {
2615 /* Go back by 1 argument. */
2616 if (position > 0)
2617 position--;
2618 }
2619 if (position >= 0)
2620 add_req_type_constraint (&list, position++, FAT_OBJECT);
2621 break;
2622
2623 case 'C': case 'c': /* 22.3.1.1 FORMAT-CHARACTER */
2624 if (!check_params (&list, paramcount, params, 0, NULL,
2625 spec->directives, invalid_reason))
2626 return false;
2627 if (position >= 0)
2628 add_req_type_constraint (&list, position++, FAT_CHARACTER);
2629 break;
2630
2631 case 'F': case 'f': /* 22.3.3.1 FORMAT-FIXED-FLOAT */
2632 if (!check_params (&list, paramcount, params, 5, IIICC,
2633 spec->directives, invalid_reason))
2634 return false;
2635 if (position >= 0)
2636 add_req_type_constraint (&list, position++, FAT_REAL);
2637 break;
2638
2639 case 'E': case 'e': /* 22.3.3.2 FORMAT-EXPONENTIAL-FLOAT */
2640 case 'G': case 'g': /* 22.3.3.3 FORMAT-GENERAL-FLOAT */
2641 if (!check_params (&list, paramcount, params, 7, IIIICCC,
2642 spec->directives, invalid_reason))
2643 return false;
2644 if (position >= 0)
2645 add_req_type_constraint (&list, position++, FAT_REAL);
2646 break;
2647
2648 case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */
2649 if (!check_params (&list, paramcount, params, 4, IIIC,
2650 spec->directives, invalid_reason))
2651 return false;
2652 if (position >= 0)
2653 add_req_type_constraint (&list, position++, FAT_REAL);
2654 break;
2655
2656 case '%': /* 22.3.1.2 FORMAT-TERPRI */
2657 case '&': /* 22.3.1.3 FORMAT-FRESH-LINE */
2658 case '|': /* 22.3.1.4 FORMAT-PAGE */
2659 case '~': /* 22.3.1.5 FORMAT-TILDE */
2660 case 'I': case 'i': /* 22.3.5.3 */
2661 if (!check_params (&list, paramcount, params, 1, I,
2662 spec->directives, invalid_reason))
2663 return false;
2664 break;
2665
2666 case '\n': /* 22.3.9.3 #\Newline */
2667 case '_': /* 22.3.5.1 */
2668 if (!check_params (&list, paramcount, params, 0, NULL,
2669 spec->directives, invalid_reason))
2670 return false;
2671 break;
2672
2673 case 'T': case 't': /* 22.3.6.1 FORMAT-TABULATE */
2674 if (!check_params (&list, paramcount, params, 2, II,
2675 spec->directives, invalid_reason))
2676 return false;
2677 break;
2678
2679 case '*': /* 22.3.7.1 FORMAT-GOTO */
2680 if (!check_params (&list, paramcount, params, 1, I,
2681 spec->directives, invalid_reason))
2682 return false;
2683 {
2684 int n; /* value of first parameter */
2685 if (paramcount == 0
2686 || (paramcount >= 1 && params[0].type == PT_NIL))
2687 n = (atsign_p ? 0 : 1);
2688 else if (paramcount >= 1 && params[0].type == PT_INTEGER)
2689 n = params[0].value;
2690 else
2691 {
2692 /* Unknown argument, leads to an unknown position. */
2693 position = -1;
2694 break;
2695 }
2696 if (n < 0)
2697 {
2698 /* invalid argument */
2699 *invalid_reason =
2700 xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
2701 return false;
2702 }
2703 if (atsign_p)
2704 {
2705 /* Absolute goto. */
2706 position = n;
2707 }
2708 else if (colon_p)
2709 {
2710 /* Backward goto. */
2711 if (n > 0)
2712 {
2713 if (position >= 0)
2714 {
2715 if (position >= n)
2716 position -= n;
2717 else
2718 position = 0;
2719 }
2720 else
2721 position = -1;
2722 }
2723 }
2724 else
2725 {
2726 /* Forward goto. */
2727 if (position >= 0)
2728 position += n;
2729 }
2730 }
2731 break;
2732
2733 case '?': /* 22.3.7.6 FORMAT-INDIRECTION */
2734 if (!check_params (&list, paramcount, params, 0, NULL,
2735 spec->directives, invalid_reason))
2736 return false;
2737 if (position >= 0)
2738 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
2739 if (atsign_p)
2740 position = -1;
2741 else
2742 if (position >= 0)
2743 {
2744 struct format_arg_list *sublist = make_unconstrained_list ();
2745 add_req_listtype_constraint (&list, position++,
2746 FAT_LIST, sublist);
2747 free_list (sublist);
2748 }
2749 break;
2750
2751 case '/': /* 22.3.5.4 FORMAT-CALL-USER-FUNCTION */
2752 if (!check_params (&list, paramcount, params, 0, NULL,
2753 spec->directives, invalid_reason))
2754 return false;
2755 if (position >= 0)
2756 add_req_type_constraint (&list, position++, FAT_OBJECT);
2757 while (*format != '\0' && *format != '/')
2758 format++;
2759 if (*format == '\0')
2760 {
2761 *invalid_reason =
2762 xstrdup (_("The string ends in the middle of a ~/.../ directive."));
2763 return false;
2764 }
2765 format++;
2766 break;
2767
2768 case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */
2769 if (!check_params (&list, paramcount, params, 0, NULL,
2770 spec->directives, invalid_reason))
2771 return false;
2772 *formatp = format;
2773 *positionp = position;
2774 *listp = list;
2775 *escapep = escape;
2776 {
2777 if (!parse_upto (formatp, positionp, listp, escapep,
2778 NULL, spec, ')', false,
2779 invalid_reason))
2780 return false;
2781 }
2782 format = *formatp;
2783 position = *positionp;
2784 list = *listp;
2785 escape = *escapep;
2786 break;
2787
2788 case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */
2789 if (terminator != ')')
2790 {
2791 *invalid_reason =
2792 xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
2793 return false;
2794 }
2795 if (!check_params (&list, paramcount, params, 0, NULL,
2796 spec->directives, invalid_reason))
2797 return false;
2798 *formatp = format;
2799 *positionp = position;
2800 *listp = list;
2801 *escapep = escape;
2802 return true;
2803
2804 case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */
2805 if (atsign_p && colon_p)
2806 {
2807 *invalid_reason =
2808 xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
2809 return false;
2810 }
2811 else if (atsign_p)
2812 {
2813 struct format_arg_list *nil_list;
2814 struct format_arg_list *union_list;
2815
2816 if (!check_params (&list, paramcount, params, 0, NULL,
2817 spec->directives, invalid_reason))
2818 return false;
2819
2820 *formatp = format;
2821 *escapep = escape;
2822
2823 /* First alternative: argument is NIL. */
2824 nil_list = (list != NULL ? copy_list (list) : NULL);
2825 if (position >= 0)
2826 {
2827 struct format_arg_list *empty_list = make_empty_list ();
2828 add_req_listtype_constraint (&nil_list, position,
2829 FAT_LIST, empty_list);
2830 free_list (empty_list);
2831 }
2832
2833 /* Second alternative: use sub-format. */
2834 {
2835 int sub_position = position;
2836 struct format_arg_list *sub_list =
2837 (list != NULL ? copy_list (list) : NULL);
2838 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2839 NULL, spec, ']', false,
2840 invalid_reason))
2841 return false;
2842 if (sub_list != NULL)
2843 {
2844 if (position >= 0)
2845 {
2846 if (sub_position == position + 1)
2847 /* new position is branch independent */
2848 position = position + 1;
2849 else
2850 /* new position is branch dependent */
2851 position = -1;
2852 }
2853 }
2854 else
2855 {
2856 if (position >= 0)
2857 position = position + 1;
2858 }
2859 union_list = union (nil_list, sub_list);
2860 }
2861
2862 format = *formatp;
2863 escape = *escapep;
2864
2865 if (list != NULL)
2866 free_list (list);
2867 list = union_list;
2868 }
2869 else if (colon_p)
2870 {
2871 int union_position;
2872 struct format_arg_list *union_list;
2873
2874 if (!check_params (&list, paramcount, params, 0, NULL,
2875 spec->directives, invalid_reason))
2876 return false;
2877
2878 if (position >= 0)
2879 add_req_type_constraint (&list, position++, FAT_OBJECT);
2880
2881 *formatp = format;
2882 *escapep = escape;
2883 union_position = -2;
2884 union_list = NULL;
2885
2886 /* First alternative. */
2887 {
2888 int sub_position = position;
2889 struct format_arg_list *sub_list =
2890 (list != NULL ? copy_list (list) : NULL);
2891 int sub_separator = 0;
2892 if (position >= 0)
2893 {
2894 struct format_arg_list *empty_list = make_empty_list ();
2895 add_req_listtype_constraint (&sub_list, position - 1,
2896 FAT_LIST, empty_list);
2897 free_list (empty_list);
2898 }
2899 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2900 &sub_separator, spec, ']', true,
2901 invalid_reason))
2902 return false;
2903 if (!sub_separator)
2904 {
2905 *invalid_reason =
2906 xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives);
2907 return false;
2908 }
2909 if (sub_list != NULL)
2910 union_position = sub_position;
2911 union_list = union (union_list, sub_list);
2912 }
2913
2914 /* Second alternative. */
2915 {
2916 int sub_position = position;
2917 struct format_arg_list *sub_list =
2918 (list != NULL ? copy_list (list) : NULL);
2919 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2920 NULL, spec, ']', false,
2921 invalid_reason))
2922 return false;
2923 if (sub_list != NULL)
2924 {
2925 if (union_position == -2)
2926 union_position = sub_position;
2927 else if (sub_position < 0
2928 || sub_position != union_position)
2929 union_position = -1;
2930 }
2931 union_list = union (union_list, sub_list);
2932 }
2933
2934 format = *formatp;
2935 escape = *escapep;
2936
2937 if (union_position != -2)
2938 position = union_position;
2939 if (list != NULL)
2940 free_list (list);
2941 list = union_list;
2942 }
2943 else
2944 {
2945 int arg_position;
2946 int union_position;
2947 struct format_arg_list *union_list;
2948 bool last_alternative;
2949
2950 if (!check_params (&list, paramcount, params, 1, I,
2951 spec->directives, invalid_reason))
2952 return false;
2953
2954 /* If there was no first parameter, an argument is consumed. */
2955 arg_position = -1;
2956 if (!(paramcount >= 1 && params[0].type != PT_NIL))
2957 if (position >= 0)
2958 {
2959 arg_position = position;
2960 add_req_type_constraint (&list, position++, FAT_OBJECT);
2961 }
2962
2963 *formatp = format;
2964 *escapep = escape;
2965
2966 union_position = -2;
2967 union_list = NULL;
2968 last_alternative = false;
2969 for (;;)
2970 {
2971 /* Next alternative. */
2972 int sub_position = position;
2973 struct format_arg_list *sub_list =
2974 (list != NULL ? copy_list (list) : NULL);
2975 int sub_separator = 0;
2976 if (!parse_upto (formatp, &sub_position, &sub_list, escapep,
2977 &sub_separator, spec, ']', !last_alternative,
2978 invalid_reason))
2979 return false;
2980 /* If this alternative is chosen, the argument arg_position
2981 is an integer, namely the index of this alternative. */
2982 if (!last_alternative && arg_position >= 0)
2983 add_req_type_constraint (&sub_list, arg_position,
2984 FAT_INTEGER);
2985 if (sub_list != NULL)
2986 {
2987 if (union_position == -2)
2988 union_position = sub_position;
2989 else if (sub_position < 0
2990 || sub_position != union_position)
2991 union_position = -1;
2992 }
2993 union_list = union (union_list, sub_list);
2994 if (sub_separator == 2)
2995 last_alternative = true;
2996 if (!sub_separator)
2997 break;
2998 }
2999 if (!last_alternative)
3000 {
3001 /* An implicit default alternative. */
3002 if (union_position == -2)
3003 union_position = position;
3004 else if (position < 0 || position != union_position)
3005 union_position = -1;
3006 if (list != NULL)
3007 union_list = union (union_list, copy_list (list));
3008 }
3009
3010 format = *formatp;
3011 escape = *escapep;
3012
3013 if (union_position != -2)
3014 position = union_position;
3015 if (list != NULL)
3016 free_list (list);
3017 list = union_list;
3018 }
3019 break;
3020
3021 case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */
3022 if (terminator != ']')
3023 {
3024 *invalid_reason =
3025 xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
3026 return false;
3027 }
3028 if (!check_params (&list, paramcount, params, 0, NULL,
3029 spec->directives, invalid_reason))
3030 return false;
3031 *formatp = format;
3032 *positionp = position;
3033 *listp = list;
3034 *escapep = escape;
3035 return true;
3036
3037 case '{': /* 22.3.7.4 FORMAT-ITERATION */
3038 if (!check_params (&list, paramcount, params, 1, I,
3039 spec->directives, invalid_reason))
3040 return false;
3041 *formatp = format;
3042 {
3043 int sub_position = 0;
3044 struct format_arg_list *sub_list = make_unconstrained_list ();
3045 struct format_arg_list *sub_escape = NULL;
3046 struct spec sub_spec;
3047 sub_spec.directives = 0;
3048 sub_spec.list = sub_list;
3049 if (!parse_upto (formatp, &sub_position, &sub_list, &sub_escape,
3050 NULL, &sub_spec, '}', false,
3051 invalid_reason))
3052 return false;
3053 spec->directives += sub_spec.directives;
3054
3055 /* If the sub-formatstring is empty, except for the terminating
3056 ~} directive, a formatstring argument is consumed. */
3057 if (*format == '~' && sub_spec.directives == 1)
3058 if (position >= 0)
3059 add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
3060
3061 if (colon_p)
3062 {
3063 /* Each iteration uses a new sublist. */
3064 struct format_arg_list *listlist;
3065
3066 /* ~{ catches ~^. */
3067 sub_list = union (sub_list, sub_escape);
3068
3069 listlist = make_repeated_list_of_lists (sub_list);
3070
3071 sub_list = listlist;
3072 }
3073 else
3074 {
3075 /* Each iteration's arguments are all concatenated in a
3076 single list. */
3077 struct format_arg_list *looplist;
3078
3079 /* FIXME: This is far from correct. Test cases:
3080 abc~{~^~}
3081 abc~{~S~^~S~}
3082 abc~{~D~^~C~}
3083 abc~{~D~^~D~}
3084 abc~{~D~^~S~}
3085 abc~{~D~^~C~}~:*~{~S~^~D~}
3086 */
3087
3088 /* ~{ catches ~^. */
3089 sub_list = union (sub_list, sub_escape);
3090
3091 if (sub_list == NULL)
3092 looplist = make_empty_list ();
3093 else
3094 if (sub_position < 0 || sub_position == 0)
3095 /* Too hard to track the possible argument types
3096 when the iteration is performed 2 times or more.
3097 So be satisfied with the constraints of executing
3098 the iteration 1 or 0 times. */
3099 looplist = make_union_with_empty_list (sub_list);
3100 else
3101 looplist = make_repeated_list (sub_list, sub_position);
3102
3103 sub_list = looplist;
3104 }
3105
3106 if (atsign_p)
3107 {
3108 /* All remaining arguments are used. */
3109 if (list != NULL && position >= 0)
3110 {
3111 shift_list (sub_list, position);
3112 list = make_intersected_list (list, sub_list);
3113 }
3114 position = -1;
3115 }
3116 else
3117 {
3118 /* The argument is a list. */
3119 if (position >= 0)
3120 add_req_listtype_constraint (&list, position++,
3121 FAT_LIST, sub_list);
3122 }
3123 }
3124 format = *formatp;
3125 break;
3126
3127 case '}': /* 22.3.7.5 FORMAT-ITERATION-END */
3128 if (terminator != '}')
3129 {
3130 *invalid_reason =
3131 xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
3132 return false;
3133 }
3134 if (!check_params (&list, paramcount, params, 0, NULL,
3135 spec->directives, invalid_reason))
3136 return false;
3137 *formatp = format;
3138 *positionp = position;
3139 *listp = list;
3140 *escapep = escape;
3141 return true;
3142
3143 case '<': /* 22.3.6.2, 22.3.5.2 FORMAT-JUSTIFICATION */
3144 if (!check_params (&list, paramcount, params, 4, IIIC,
3145 spec->directives, invalid_reason))
3146 return false;
3147 {
3148 struct format_arg_list *sub_escape = NULL;
3149
3150 *formatp = format;
3151 *positionp = position;
3152 *listp = list;
3153
3154 for (;;)
3155 {
3156 int sub_separator = 0;
3157 if (!parse_upto (formatp, positionp, listp, &sub_escape,
3158 &sub_separator, spec, '>', true,
3159 invalid_reason))
3160 return false;
3161 if (!sub_separator)
3162 break;
3163 }
3164
3165 format = *formatp;
3166 position = *positionp;
3167 list = *listp;
3168
3169 /* ~< catches ~^. */
3170 if (sub_escape != NULL)
3171 position = -1;
3172 list = union (list, sub_escape);
3173 }
3174 break;
3175
3176 case '>': /* 22.3.6.3 FORMAT-JUSTIFICATION-END */
3177 if (terminator != '>')
3178 {
3179 *invalid_reason =
3180 xasprintf (_("Found '~%c' without matching '~%c'."), '>', '<');
3181 return false;
3182 }
3183 if (!check_params (&list, paramcount, params, 0, NULL,
3184 spec->directives, invalid_reason))
3185 return false;
3186 *formatp = format;
3187 *positionp = position;
3188 *listp = list;
3189 *escapep = escape;
3190 return true;
3191
3192 case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */
3193 if (!check_params (&list, paramcount, params, 3, THREE,
3194 spec->directives, invalid_reason))
3195 return false;
3196 if (position >= 0 && list != NULL && is_required (list, position))
3197 /* This ~^ can never be executed. Ignore it. */
3198 break;
3199 if (list != NULL)
3200 {
3201 struct format_arg_list *this_escape = copy_list (list);
3202 if (position >= 0)
3203 this_escape = add_end_constraint (this_escape, position);
3204 escape = union (escape, this_escape);
3205 }
3206 if (position >= 0)
3207 list = add_required_constraint (list, position);
3208 break;
3209
3210 case ';': /* 22.3.9.1 FORMAT-SEPARATOR */
3211 if (!separator)
3212 {
3213 *invalid_reason =
3214 xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
3215 return false;
3216 }
3217 if (terminator == '>')
3218 {
3219 if (!check_params (&list, paramcount, params, 1, I,
3220 spec->directives, invalid_reason))
3221 return false;
3222 }
3223 else
3224 {
3225 if (!check_params (&list, paramcount, params, 0, NULL,
3226 spec->directives, invalid_reason))
3227 return false;
3228 }
3229 *formatp = format;
3230 *positionp = position;
3231 *listp = list;
3232 *escapep = escape;
3233 *separatorp = (colon_p ? 2 : 1);
3234 return true;
3235
3236 case '!': /* FORMAT-CALL, a CLISP extension */
3237 if (!nocheck_params (&list, paramcount, params,
3238 spec->directives, invalid_reason))
3239 return false;
3240 if (position >= 0)
3241 {
3242 add_req_type_constraint (&list, position++, FAT_FUNCTION);
3243 add_req_type_constraint (&list, position++, FAT_OBJECT);
3244 }
3245 break;
3246
3247 default:
3248 --format;
3249 *invalid_reason =
3250 (*format == '\0'
3251 ? INVALID_UNTERMINATED_DIRECTIVE ()
3252 : INVALID_CONVERSION_SPECIFIER (spec->directives, *format));
3253 return false;
3254 }
3255
3256 free (params);
3257 }
3258
3259 *formatp = format;
3260 *positionp = position;
3261 *listp = list;
3262 *escapep = escape;
3263 if (terminator != '\0')
3264 {
3265 *invalid_reason =
3266 xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator);
3267 return false;
3268 }
3269 return true;
3270 }
3271
3272
3273 /* ============== Top level format string handling functions ============== */
3274
3275 static void *
format_parse(const char * format,bool translated,char ** invalid_reason)3276 format_parse (const char *format, bool translated, char **invalid_reason)
3277 {
3278 struct spec spec;
3279 struct spec *result;
3280 int position = 0;
3281 struct format_arg_list *escape;
3282
3283 spec.directives = 0;
3284 spec.list = make_unconstrained_list ();
3285 escape = NULL;
3286
3287 if (!parse_upto (&format, &position, &spec.list, &escape,
3288 NULL, &spec, '\0', false,
3289 invalid_reason))
3290 /* Invalid format string. */
3291 return NULL;
3292
3293 /* Catch ~^ here. */
3294 spec.list = union (spec.list, escape);
3295
3296 if (spec.list == NULL)
3297 {
3298 /* Contradictory argument type information. */
3299 *invalid_reason =
3300 xstrdup (_("The string refers to some argument in incompatible ways."));
3301 return NULL;
3302 }
3303
3304 /* Normalize the result. */
3305 normalize_list (spec.list);
3306
3307 result = (struct spec *) xmalloc (sizeof (struct spec));
3308 *result = spec;
3309 return result;
3310 }
3311
3312 static void
format_free(void * descr)3313 format_free (void *descr)
3314 {
3315 struct spec *spec = (struct spec *) descr;
3316
3317 free_list (spec->list);
3318 }
3319
3320 static int
format_get_number_of_directives(void * descr)3321 format_get_number_of_directives (void *descr)
3322 {
3323 struct spec *spec = (struct spec *) descr;
3324
3325 return spec->directives;
3326 }
3327
3328 static bool
format_check(void * msgid_descr,void * msgstr_descr,bool equality,formatstring_error_logger_t error_logger,const char * pretty_msgstr)3329 format_check (void *msgid_descr, void *msgstr_descr, bool equality,
3330 formatstring_error_logger_t error_logger,
3331 const char *pretty_msgstr)
3332 {
3333 struct spec *spec1 = (struct spec *) msgid_descr;
3334 struct spec *spec2 = (struct spec *) msgstr_descr;
3335 bool err = false;
3336
3337 if (equality)
3338 {
3339 if (!equal_list (spec1->list, spec2->list))
3340 {
3341 if (error_logger)
3342 error_logger (_("format specifications in 'msgid' and '%s' are not equivalent"),
3343 pretty_msgstr);
3344 err = true;
3345 }
3346 }
3347 else
3348 {
3349 struct format_arg_list *intersection =
3350 make_intersected_list (copy_list (spec1->list),
3351 copy_list (spec2->list));
3352
3353 if (!(intersection != NULL
3354 && (normalize_list (intersection),
3355 equal_list (intersection, spec2->list))))
3356 {
3357 if (error_logger)
3358 error_logger (_("format specifications in '%s' are not a subset of those in 'msgid'"),
3359 pretty_msgstr);
3360 err = true;
3361 }
3362 }
3363
3364 return err;
3365 }
3366
3367
3368 struct formatstring_parser formatstring_lisp =
3369 {
3370 format_parse,
3371 format_free,
3372 format_get_number_of_directives,
3373 NULL,
3374 format_check
3375 };
3376
3377
3378 /* ============================= Testing code ============================= */
3379
3380 #undef union
3381
3382 #ifdef TEST
3383
3384 /* Test program: Print the argument list specification returned by
3385 format_parse for strings read from standard input. */
3386
3387 #include <stdio.h>
3388 #include "getline.h"
3389
3390 static void print_list (struct format_arg_list *list);
3391
3392 static void
print_element(struct format_arg * element)3393 print_element (struct format_arg *element)
3394 {
3395 switch (element->presence)
3396 {
3397 case FCT_REQUIRED:
3398 break;
3399 case FCT_OPTIONAL:
3400 printf (". ");
3401 break;
3402 default:
3403 abort ();
3404 }
3405
3406 switch (element->type)
3407 {
3408 case FAT_OBJECT:
3409 printf ("*");
3410 break;
3411 case FAT_CHARACTER_INTEGER_NULL:
3412 printf ("ci()");
3413 break;
3414 case FAT_CHARACTER_NULL:
3415 printf ("c()");
3416 break;
3417 case FAT_CHARACTER:
3418 printf ("c");
3419 break;
3420 case FAT_INTEGER_NULL:
3421 printf ("i()");
3422 break;
3423 case FAT_INTEGER:
3424 printf ("i");
3425 break;
3426 case FAT_REAL:
3427 printf ("r");
3428 break;
3429 case FAT_LIST:
3430 print_list (element->list);
3431 break;
3432 case FAT_FORMATSTRING:
3433 printf ("~");
3434 break;
3435 case FAT_FUNCTION:
3436 printf ("f");
3437 break;
3438 default:
3439 abort ();
3440 }
3441 }
3442
3443 static void
print_list(struct format_arg_list * list)3444 print_list (struct format_arg_list *list)
3445 {
3446 unsigned int i, j;
3447
3448 printf ("(");
3449
3450 for (i = 0; i < list->initial.count; i++)
3451 for (j = 0; j < list->initial.element[i].repcount; j++)
3452 {
3453 if (i > 0 || j > 0)
3454 printf (" ");
3455 print_element (&list->initial.element[i]);
3456 }
3457
3458 if (list->repeated.count > 0)
3459 {
3460 printf (" |");
3461 for (i = 0; i < list->repeated.count; i++)
3462 for (j = 0; j < list->repeated.element[i].repcount; j++)
3463 {
3464 printf (" ");
3465 print_element (&list->repeated.element[i]);
3466 }
3467 }
3468
3469 printf (")");
3470 }
3471
3472 static void
format_print(void * descr)3473 format_print (void *descr)
3474 {
3475 struct spec *spec = (struct spec *) descr;
3476
3477 if (spec == NULL)
3478 {
3479 printf ("INVALID");
3480 return;
3481 }
3482
3483 print_list (spec->list);
3484 }
3485
3486 int
main()3487 main ()
3488 {
3489 for (;;)
3490 {
3491 char *line = NULL;
3492 size_t line_size = 0;
3493 int line_len;
3494 char *invalid_reason;
3495 void *descr;
3496
3497 line_len = getline (&line, &line_size, stdin);
3498 if (line_len < 0)
3499 break;
3500 if (line_len > 0 && line[line_len - 1] == '\n')
3501 line[--line_len] = '\0';
3502
3503 invalid_reason = NULL;
3504 descr = format_parse (line, false, &invalid_reason);
3505
3506 format_print (descr);
3507 printf ("\n");
3508 if (descr == NULL)
3509 printf ("%s\n", invalid_reason);
3510
3511 free (invalid_reason);
3512 free (line);
3513 }
3514
3515 return 0;
3516 }
3517
3518 /*
3519 * For Emacs M-x compile
3520 * Local Variables:
3521 * compile-command: "/bin/sh ../libtool --mode=link gcc -o a.out -static -O -g -Wall -I.. -I../lib -I../intl -DHAVE_CONFIG_H -DTEST format-lisp.c ../lib/libgettextlib.la"
3522 * End:
3523 */
3524
3525 #endif /* TEST */
3526