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