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