| /* Scheme format strings. |
| Copyright (C) 2001-2007, 2009, 2014, 2019 Free Software Foundation, Inc. |
| Written by Bruno Haible <haible@clisp.cons.org>, 2001. |
| |
| This program is free software: you can redistribute it and/or modify |
| it under the terms of the GNU General Public License as published by |
| the Free Software Foundation; either version 3 of the License, or |
| (at your option) any later version. |
| |
| This program is distributed in the hope that it will be useful, |
| but WITHOUT ANY WARRANTY; without even the implied warranty of |
| MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with this program. If not, see <https://www.gnu.org/licenses/>. */ |
| |
| #ifdef HAVE_CONFIG_H |
| # include <config.h> |
| #endif |
| |
| #include <stdbool.h> |
| #include <stdlib.h> |
| |
| #include "format.h" |
| #include "c-ctype.h" |
| #include "gcd.h" |
| #include "xalloc.h" |
| #include "xvasprintf.h" |
| #include "format-invalid.h" |
| #include "minmax.h" |
| #include "error.h" |
| #include "error-progname.h" |
| #include "gettext.h" |
| |
| #define _(str) gettext (str) |
| |
| |
| /* Assertion macros. Could be defined to empty for speed. */ |
| #define ASSERT(expr) if (!(expr)) abort (); |
| #define VERIFY_LIST(list) verify_list (list) |
| |
| |
| /* Scheme format strings are described in the GNU guile documentation, |
| section "Formatted Output". They are implemented in |
| guile-1.6.4/ice-9/format.scm. */ |
| |
| /* Data structure describing format string derived constraints for an |
| argument list. It is a recursive list structure. Structure sharing |
| is not allowed. */ |
| |
| enum format_cdr_type |
| { |
| FCT_REQUIRED, /* The format argument list cannot end before this argument. */ |
| FCT_OPTIONAL /* The format argument list may end before this argument. */ |
| }; |
| |
| enum format_arg_type |
| { |
| FAT_OBJECT, /* Any object, type T. */ |
| FAT_CHARACTER_INTEGER_NULL, /* Type (OR CHARACTER INTEGER NULL). */ |
| FAT_CHARACTER_NULL, /* Type (OR CHARACTER NULL). */ |
| FAT_CHARACTER, /* Type CHARACTER. */ |
| FAT_INTEGER_NULL, /* Type (OR INTEGER NULL). */ |
| FAT_INTEGER, /* Meant for objects of type INTEGER. */ |
| FAT_REAL, /* Meant for objects of type REAL. */ |
| FAT_COMPLEX, /* Meant for objects of type COMPLEX. */ |
| FAT_LIST, /* Meant for proper lists. */ |
| FAT_FORMATSTRING /* Format strings. */ |
| }; |
| |
| struct format_arg |
| { |
| unsigned int repcount; /* Number of consecutive arguments this constraint |
| applies to. Normally 1, but unconstrained |
| arguments are often repeated. */ |
| enum format_cdr_type presence; /* Can the argument list end right before |
| this argument? */ |
| enum format_arg_type type; /* Possible values for this argument. */ |
| struct format_arg_list *list; /* For FAT_LIST: List elements. */ |
| }; |
| |
| struct segment |
| { |
| unsigned int count; /* Number of format_arg records used. */ |
| unsigned int allocated; |
| struct format_arg *element; /* Argument constraints. */ |
| unsigned int length; /* Number of arguments represented by this segment. |
| This is the sum of all repcounts in the segment. */ |
| }; |
| |
| struct format_arg_list |
| { |
| /* The constraints for the potentially infinite argument list are assumed |
| to become ultimately periodic. (Too complicated argument lists without |
| a-priori period, like |
| (format t "~@{~:[-~;~S~]~}" nil t 1 t 3 nil t 4) |
| are described by a constraint that ends in a length 1 period of |
| unconstrained arguments.) Such a periodic sequence can be split into |
| an initial segment and an endlessly repeated loop segment. |
| A finite sequence is represented entirely in the initial segment; the |
| loop segment is empty. */ |
| |
| struct segment initial; /* Initial arguments segment. */ |
| struct segment repeated; /* Endlessly repeated segment. */ |
| }; |
| |
| struct spec |
| { |
| unsigned int directives; |
| struct format_arg_list *list; |
| }; |
| |
| |
| /* Parameter for a directive. */ |
| enum param_type |
| { |
| PT_NIL, /* param not present */ |
| PT_CHARACTER, /* character */ |
| PT_INTEGER, /* integer */ |
| PT_ARGCOUNT, /* number of remaining arguments */ |
| PT_V /* variable taken from argument list */ |
| }; |
| |
| struct param |
| { |
| enum param_type type; |
| int value; /* for PT_INTEGER: the value, for PT_V: the position */ |
| }; |
| |
| |
| /* Forward declaration of local functions. */ |
| #define union make_union |
| static void verify_list (const struct format_arg_list *list); |
| static void free_list (struct format_arg_list *list); |
| static struct format_arg_list * copy_list (const struct format_arg_list *list); |
| static bool equal_list (const struct format_arg_list *list1, |
| const struct format_arg_list *list2); |
| static struct format_arg_list * make_intersected_list |
| (struct format_arg_list *list1, |
| struct format_arg_list *list2); |
| static struct format_arg_list * make_intersection_with_empty_list |
| (struct format_arg_list *list); |
| static struct format_arg_list * make_union_list |
| (struct format_arg_list *list1, |
| struct format_arg_list *list2); |
| |
| |
| /* ======================= Verify a format_arg_list ======================= */ |
| |
| /* Verify some invariants. */ |
| static void |
| verify_element (const struct format_arg * e) |
| { |
| ASSERT (e->repcount > 0); |
| if (e->type == FAT_LIST) |
| verify_list (e->list); |
| } |
| |
| /* Verify some invariants. */ |
| /* Memory effects: none. */ |
| static void |
| verify_list (const struct format_arg_list *list) |
| { |
| unsigned int i; |
| unsigned int total_repcount; |
| |
| ASSERT (list->initial.count <= list->initial.allocated); |
| total_repcount = 0; |
| for (i = 0; i < list->initial.count; i++) |
| { |
| verify_element (&list->initial.element[i]); |
| total_repcount += list->initial.element[i].repcount; |
| } |
| ASSERT (total_repcount == list->initial.length); |
| |
| ASSERT (list->repeated.count <= list->repeated.allocated); |
| total_repcount = 0; |
| for (i = 0; i < list->repeated.count; i++) |
| { |
| verify_element (&list->repeated.element[i]); |
| total_repcount += list->repeated.element[i].repcount; |
| } |
| ASSERT (total_repcount == list->repeated.length); |
| } |
| |
| #define VERIFY_LIST(list) verify_list (list) |
| |
| |
| /* ======================== Free a format_arg_list ======================== */ |
| |
| /* Free the data belonging to an argument list element. */ |
| static inline void |
| free_element (struct format_arg *element) |
| { |
| if (element->type == FAT_LIST) |
| free_list (element->list); |
| } |
| |
| /* Free an argument list. */ |
| /* Memory effects: Frees list. */ |
| static void |
| free_list (struct format_arg_list *list) |
| { |
| unsigned int i; |
| |
| for (i = 0; i < list->initial.count; i++) |
| free_element (&list->initial.element[i]); |
| if (list->initial.element != NULL) |
| free (list->initial.element); |
| |
| for (i = 0; i < list->repeated.count; i++) |
| free_element (&list->repeated.element[i]); |
| if (list->repeated.element != NULL) |
| free (list->repeated.element); |
| } |
| |
| |
| /* ======================== Copy a format_arg_list ======================== */ |
| |
| /* Copy the data belonging to an argument list element. */ |
| static inline void |
| copy_element (struct format_arg *newelement, |
| const struct format_arg *oldelement) |
| { |
| newelement->repcount = oldelement->repcount; |
| newelement->presence = oldelement->presence; |
| newelement->type = oldelement->type; |
| if (oldelement->type == FAT_LIST) |
| newelement->list = copy_list (oldelement->list); |
| } |
| |
| /* Copy an argument list. */ |
| /* Memory effects: Freshly allocated result. */ |
| static struct format_arg_list * |
| copy_list (const struct format_arg_list *list) |
| { |
| struct format_arg_list *newlist; |
| unsigned int length; |
| unsigned int i; |
| |
| VERIFY_LIST (list); |
| |
| newlist = XMALLOC (struct format_arg_list); |
| |
| newlist->initial.count = newlist->initial.allocated = list->initial.count; |
| length = 0; |
| if (list->initial.count == 0) |
| newlist->initial.element = NULL; |
| else |
| { |
| newlist->initial.element = |
| XNMALLOC (newlist->initial.allocated, struct format_arg); |
| for (i = 0; i < list->initial.count; i++) |
| { |
| copy_element (&newlist->initial.element[i], |
| &list->initial.element[i]); |
| length += list->initial.element[i].repcount; |
| } |
| } |
| ASSERT (length == list->initial.length); |
| newlist->initial.length = length; |
| |
| newlist->repeated.count = newlist->repeated.allocated = list->repeated.count; |
| length = 0; |
| if (list->repeated.count == 0) |
| newlist->repeated.element = NULL; |
| else |
| { |
| newlist->repeated.element = |
| XNMALLOC (newlist->repeated.allocated, struct format_arg); |
| for (i = 0; i < list->repeated.count; i++) |
| { |
| copy_element (&newlist->repeated.element[i], |
| &list->repeated.element[i]); |
| length += list->repeated.element[i].repcount; |
| } |
| } |
| ASSERT (length == list->repeated.length); |
| newlist->repeated.length = length; |
| |
| VERIFY_LIST (newlist); |
| |
| return newlist; |
| } |
| |
| |
| /* ===================== Compare two format_arg_lists ===================== */ |
| |
| /* Tests whether two normalized argument constraints are equivalent, |
| ignoring the repcount. */ |
| static bool |
| equal_element (const struct format_arg * e1, const struct format_arg * e2) |
| { |
| return (e1->presence == e2->presence |
| && e1->type == e2->type |
| && (e1->type == FAT_LIST ? equal_list (e1->list, e2->list) : true)); |
| } |
| |
| /* Tests whether two normalized argument list constraints are equivalent. */ |
| /* Memory effects: none. */ |
| static bool |
| equal_list (const struct format_arg_list *list1, |
| const struct format_arg_list *list2) |
| { |
| unsigned int n, i; |
| |
| VERIFY_LIST (list1); |
| VERIFY_LIST (list2); |
| |
| n = list1->initial.count; |
| if (n != list2->initial.count) |
| return false; |
| for (i = 0; i < n; i++) |
| { |
| const struct format_arg * e1 = &list1->initial.element[i]; |
| const struct format_arg * e2 = &list2->initial.element[i]; |
| |
| if (!(e1->repcount == e2->repcount && equal_element (e1, e2))) |
| return false; |
| } |
| |
| n = list1->repeated.count; |
| if (n != list2->repeated.count) |
| return false; |
| for (i = 0; i < n; i++) |
| { |
| const struct format_arg * e1 = &list1->repeated.element[i]; |
| const struct format_arg * e2 = &list2->repeated.element[i]; |
| |
| if (!(e1->repcount == e2->repcount && equal_element (e1, e2))) |
| return false; |
| } |
| |
| return true; |
| } |
| |
| |
| /* ===================== Incremental memory allocation ===================== */ |
| |
| /* Ensure list->initial.allocated >= newcount. */ |
| static inline void |
| ensure_initial_alloc (struct format_arg_list *list, unsigned int newcount) |
| { |
| if (newcount > list->initial.allocated) |
| { |
| list->initial.allocated = |
| MAX (2 * list->initial.allocated + 1, newcount); |
| list->initial.element = |
| (struct format_arg *) |
| xrealloc (list->initial.element, |
| list->initial.allocated * sizeof (struct format_arg)); |
| } |
| } |
| |
| /* Ensure list->initial.allocated > list->initial.count. */ |
| static inline void |
| grow_initial_alloc (struct format_arg_list *list) |
| { |
| if (list->initial.count >= list->initial.allocated) |
| { |
| list->initial.allocated = |
| MAX (2 * list->initial.allocated + 1, list->initial.count + 1); |
| list->initial.element = |
| (struct format_arg *) |
| xrealloc (list->initial.element, |
| list->initial.allocated * sizeof (struct format_arg)); |
| } |
| } |
| |
| /* Ensure list->repeated.allocated >= newcount. */ |
| static inline void |
| ensure_repeated_alloc (struct format_arg_list *list, unsigned int newcount) |
| { |
| if (newcount > list->repeated.allocated) |
| { |
| list->repeated.allocated = |
| MAX (2 * list->repeated.allocated + 1, newcount); |
| list->repeated.element = |
| (struct format_arg *) |
| xrealloc (list->repeated.element, |
| list->repeated.allocated * sizeof (struct format_arg)); |
| } |
| } |
| |
| /* Ensure list->repeated.allocated > list->repeated.count. */ |
| static inline void |
| grow_repeated_alloc (struct format_arg_list *list) |
| { |
| if (list->repeated.count >= list->repeated.allocated) |
| { |
| list->repeated.allocated = |
| MAX (2 * list->repeated.allocated + 1, list->repeated.count + 1); |
| list->repeated.element = |
| (struct format_arg *) |
| xrealloc (list->repeated.element, |
| list->repeated.allocated * sizeof (struct format_arg)); |
| } |
| } |
| |
| |
| /* ====================== Normalize a format_arg_list ====================== */ |
| |
| /* Normalize an argument list constraint, assuming all sublists are already |
| normalized. */ |
| /* Memory effects: Destructively modifies list. */ |
| static void |
| normalize_outermost_list (struct format_arg_list *list) |
| { |
| unsigned int n, i, j; |
| |
| /* Step 1: Combine adjacent elements. |
| Copy from i to j, keeping 0 <= j <= i. */ |
| |
| n = list->initial.count; |
| for (i = j = 0; i < n; i++) |
| if (j > 0 |
| && equal_element (&list->initial.element[i], |
| &list->initial.element[j-1])) |
| { |
| list->initial.element[j-1].repcount += |
| list->initial.element[i].repcount; |
| free_element (&list->initial.element[i]); |
| } |
| else |
| { |
| if (j < i) |
| list->initial.element[j] = list->initial.element[i]; |
| j++; |
| } |
| list->initial.count = j; |
| |
| n = list->repeated.count; |
| for (i = j = 0; i < n; i++) |
| if (j > 0 |
| && equal_element (&list->repeated.element[i], |
| &list->repeated.element[j-1])) |
| { |
| list->repeated.element[j-1].repcount += |
| list->repeated.element[i].repcount; |
| free_element (&list->repeated.element[i]); |
| } |
| else |
| { |
| if (j < i) |
| list->repeated.element[j] = list->repeated.element[i]; |
| j++; |
| } |
| list->repeated.count = j; |
| |
| /* Nothing more to be done if the loop segment is empty. */ |
| if (list->repeated.count > 0) |
| { |
| unsigned int m, repcount0_extra; |
| |
| /* Step 2: Reduce the loop period. */ |
| n = list->repeated.count; |
| repcount0_extra = 0; |
| if (n > 1 |
| && equal_element (&list->repeated.element[0], |
| &list->repeated.element[n-1])) |
| { |
| repcount0_extra = list->repeated.element[n-1].repcount; |
| n--; |
| } |
| /* Proceed as if the loop period were n, with |
| list->repeated.element[0].repcount incremented by repcount0_extra. */ |
| for (m = 2; m <= n / 2; n++) |
| if ((n % m) == 0) |
| { |
| /* m is a divisor of n. Try to reduce the loop period to n. */ |
| bool ok = true; |
| |
| for (i = 0; i < n - m; i++) |
| if (!((list->repeated.element[i].repcount |
| + (i == 0 ? repcount0_extra : 0) |
| == list->repeated.element[i+m].repcount) |
| && equal_element (&list->repeated.element[i], |
| &list->repeated.element[i+m]))) |
| { |
| ok = false; |
| break; |
| } |
| if (ok) |
| { |
| for (i = m; i < n; i++) |
| free_element (&list->repeated.element[i]); |
| if (n < list->repeated.count) |
| list->repeated.element[m] = list->repeated.element[n]; |
| list->repeated.count = list->repeated.count - n + m; |
| list->repeated.length /= n / m; |
| break; |
| } |
| } |
| |
| /* Step 3: Roll as much as possible of the initial segment's tail |
| into the loop. */ |
| if (list->repeated.count == 1) |
| { |
| if (list->initial.count > 0 |
| && equal_element (&list->initial.element[list->initial.count-1], |
| &list->repeated.element[0])) |
| { |
| /* Roll the last element of the initial segment into the loop. |
| Its repcount is irrelevant. The second-to-last element is |
| certainly different and doesn't need to be considered. */ |
| list->initial.length -= |
| list->initial.element[list->initial.count-1].repcount; |
| list->initial.count--; |
| } |
| } |
| else |
| { |
| while (list->initial.count > 0 |
| && equal_element (&list->initial.element[list->initial.count-1], |
| &list->repeated.element[list->repeated.count-1])) |
| { |
| unsigned int moved_repcount = |
| MIN (list->initial.element[list->initial.count-1].repcount, |
| list->repeated.element[list->repeated.count-1].repcount); |
| |
| /* Add the element at the start of list->repeated. */ |
| if (equal_element (&list->repeated.element[0], |
| &list->repeated.element[list->repeated.count-1])) |
| list->repeated.element[0].repcount += moved_repcount; |
| else |
| { |
| unsigned int newcount = list->repeated.count + 1; |
| ensure_repeated_alloc (list, newcount); |
| for (i = newcount - 1; i > 0; i--) |
| list->repeated.element[i] = list->repeated.element[i-1]; |
| list->repeated.count = newcount; |
| copy_element (&list->repeated.element[0], |
| &list->repeated.element[list->repeated.count-1]); |
| list->repeated.element[0].repcount = moved_repcount; |
| } |
| |
| /* Remove the element from the end of list->repeated. */ |
| list->repeated.element[list->repeated.count-1].repcount -= |
| moved_repcount; |
| if (list->repeated.element[list->repeated.count-1].repcount == 0) |
| { |
| free_element (&list->repeated.element[list->repeated.count-1]); |
| list->repeated.count--; |
| } |
| |
| /* Remove the element from the end of list->initial. */ |
| list->initial.element[list->initial.count-1].repcount -= |
| moved_repcount; |
| if (list->initial.element[list->initial.count-1].repcount == 0) |
| { |
| free_element (&list->initial.element[list->initial.count-1]); |
| list->initial.count--; |
| } |
| list->initial.length -= moved_repcount; |
| } |
| } |
| } |
| } |
| |
| /* Normalize an argument list constraint. */ |
| /* Memory effects: Destructively modifies list. */ |
| static void |
| normalize_list (struct format_arg_list *list) |
| { |
| unsigned int n, i; |
| |
| VERIFY_LIST (list); |
| |
| /* First normalize all elements, recursively. */ |
| n = list->initial.count; |
| for (i = 0; i < n; i++) |
| if (list->initial.element[i].type == FAT_LIST) |
| normalize_list (list->initial.element[i].list); |
| n = list->repeated.count; |
| for (i = 0; i < n; i++) |
| if (list->repeated.element[i].type == FAT_LIST) |
| normalize_list (list->repeated.element[i].list); |
| |
| /* Then normalize the top level list. */ |
| normalize_outermost_list (list); |
| |
| VERIFY_LIST (list); |
| } |
| |
| |
| /* ===================== Unconstrained and empty lists ===================== */ |
| |
| /* It's easier to allocate these on demand, than to be careful not to |
| accidentally modify statically allocated lists. */ |
| |
| |
| /* Create an unconstrained argument list. */ |
| /* Memory effects: Freshly allocated result. */ |
| static struct format_arg_list * |
| make_unconstrained_list () |
| { |
| struct format_arg_list *list; |
| |
| list = XMALLOC (struct format_arg_list); |
| list->initial.count = 0; |
| list->initial.allocated = 0; |
| list->initial.element = NULL; |
| list->initial.length = 0; |
| list->repeated.count = 1; |
| list->repeated.allocated = 1; |
| list->repeated.element = XNMALLOC (1, struct format_arg); |
| list->repeated.element[0].repcount = 1; |
| list->repeated.element[0].presence = FCT_OPTIONAL; |
| list->repeated.element[0].type = FAT_OBJECT; |
| list->repeated.length = 1; |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| } |
| |
| |
| /* Create an empty argument list. */ |
| /* Memory effects: Freshly allocated result. */ |
| static struct format_arg_list * |
| make_empty_list () |
| { |
| struct format_arg_list *list; |
| |
| list = XMALLOC (struct format_arg_list); |
| list->initial.count = 0; |
| list->initial.allocated = 0; |
| list->initial.element = NULL; |
| list->initial.length = 0; |
| list->repeated.count = 0; |
| list->repeated.allocated = 0; |
| list->repeated.element = NULL; |
| list->repeated.length = 0; |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| } |
| |
| |
| /* Test for an empty list. */ |
| /* Memory effects: none. */ |
| static bool |
| is_empty_list (const struct format_arg_list *list) |
| { |
| return (list->initial.count == 0 && list->repeated.count == 0); |
| } |
| |
| |
| /* ======================== format_arg_list surgery ======================== */ |
| |
| /* Unfold list->repeated m times, where m >= 1. |
| Assumes list->repeated.count > 0. */ |
| /* Memory effects: list is destructively modified. */ |
| static void |
| unfold_loop (struct format_arg_list *list, unsigned int m) |
| { |
| unsigned int i, j, k; |
| |
| if (m > 1) |
| { |
| unsigned int newcount = list->repeated.count * m; |
| ensure_repeated_alloc (list, newcount); |
| i = list->repeated.count; |
| for (k = 1; k < m; k++) |
| for (j = 0; j < list->repeated.count; j++, i++) |
| copy_element (&list->repeated.element[i], &list->repeated.element[j]); |
| list->repeated.count = newcount; |
| list->repeated.length = list->repeated.length * m; |
| } |
| } |
| |
| /* Ensure list->initial.length := m, where m >= list->initial.length. |
| Assumes list->repeated.count > 0. */ |
| /* Memory effects: list is destructively modified. */ |
| static void |
| rotate_loop (struct format_arg_list *list, unsigned int m) |
| { |
| if (m == list->initial.length) |
| return; |
| |
| if (list->repeated.count == 1) |
| { |
| /* Instead of multiple copies of list->repeated.element[0], a single |
| copy with higher repcount is appended to list->initial. */ |
| unsigned int i, newcount; |
| |
| newcount = list->initial.count + 1; |
| ensure_initial_alloc (list, newcount); |
| i = list->initial.count; |
| copy_element (&list->initial.element[i], &list->repeated.element[0]); |
| list->initial.element[i].repcount = m - list->initial.length; |
| list->initial.count = newcount; |
| list->initial.length = m; |
| } |
| else |
| { |
| unsigned int n = list->repeated.length; |
| |
| /* Write m = list->initial.length + q * n + r with 0 <= r < n. */ |
| unsigned int q = (m - list->initial.length) / n; |
| unsigned int r = (m - list->initial.length) % n; |
| |
| /* Determine how many entries of list->repeated are needed for |
| length r. */ |
| unsigned int s; |
| unsigned int t; |
| |
| for (t = r, s = 0; |
| s < list->repeated.count && t >= list->repeated.element[s].repcount; |
| t -= list->repeated.element[s].repcount, s++) |
| ; |
| |
| /* s must be < list->repeated.count, otherwise r would have been >= n. */ |
| ASSERT (s < list->repeated.count); |
| |
| /* So we need to add to list->initial: |
| q full copies of list->repeated, |
| plus the s first elements of list->repeated, |
| plus, if t > 0, a splitoff of list->repeated.element[s]. */ |
| { |
| unsigned int i, j, k, newcount; |
| |
| i = list->initial.count; |
| newcount = i + q * list->repeated.count + s + (t > 0 ? 1 : 0); |
| ensure_initial_alloc (list, newcount); |
| for (k = 0; k < q; k++) |
| for (j = 0; j < list->repeated.count; j++, i++) |
| copy_element (&list->initial.element[i], |
| &list->repeated.element[j]); |
| for (j = 0; j < s; j++, i++) |
| copy_element (&list->initial.element[i], &list->repeated.element[j]); |
| if (t > 0) |
| { |
| copy_element (&list->initial.element[i], |
| &list->repeated.element[j]); |
| list->initial.element[i].repcount = t; |
| i++; |
| } |
| ASSERT (i == newcount); |
| list->initial.count = newcount; |
| /* The new length of the initial segment is |
| = list->initial.length |
| + q * list->repeated.length |
| + list->repeated[0..s-1].repcount + t |
| = list->initial.length + q * n + r |
| = m. |
| */ |
| list->initial.length = m; |
| } |
| |
| /* And rotate list->repeated. */ |
| if (r > 0) |
| { |
| unsigned int i, j, oldcount, newcount; |
| struct format_arg *newelement; |
| |
| oldcount = list->repeated.count; |
| newcount = list->repeated.count + (t > 0 ? 1 : 0); |
| newelement = XNMALLOC (newcount, struct format_arg); |
| i = 0; |
| for (j = s; j < oldcount; j++, i++) |
| newelement[i] = list->repeated.element[j]; |
| for (j = 0; j < s; j++, i++) |
| newelement[i] = list->repeated.element[j]; |
| if (t > 0) |
| { |
| copy_element (&newelement[oldcount], &newelement[0]); |
| newelement[0].repcount -= t; |
| newelement[oldcount].repcount = t; |
| } |
| free (list->repeated.element); |
| list->repeated.element = newelement; |
| } |
| } |
| } |
| |
| |
| /* Ensure index n in the initial segment falls on a split between elements, |
| i.e. if 0 < n < list->initial.length, then n-1 and n are covered by two |
| different adjacent elements. */ |
| /* Memory effects: list is destructively modified. */ |
| static unsigned int |
| initial_splitelement (struct format_arg_list *list, unsigned int n) |
| { |
| unsigned int s; |
| unsigned int t; |
| unsigned int oldrepcount; |
| unsigned int newcount; |
| unsigned int i; |
| |
| VERIFY_LIST (list); |
| |
| if (n > list->initial.length) |
| { |
| ASSERT (list->repeated.count > 0); |
| rotate_loop (list, n); |
| ASSERT (n <= list->initial.length); |
| } |
| |
| /* Determine how many entries of list->initial need to be skipped. */ |
| for (t = n, s = 0; |
| s < list->initial.count && t >= list->initial.element[s].repcount; |
| t -= list->initial.element[s].repcount, s++) |
| ; |
| |
| if (t == 0) |
| return s; |
| |
| ASSERT (s < list->initial.count); |
| |
| /* Split the entry into two entries. */ |
| oldrepcount = list->initial.element[s].repcount; |
| newcount = list->initial.count + 1; |
| ensure_initial_alloc (list, newcount); |
| for (i = list->initial.count - 1; i > s; i--) |
| list->initial.element[i+1] = list->initial.element[i]; |
| copy_element (&list->initial.element[s+1], &list->initial.element[s]); |
| list->initial.element[s].repcount = t; |
| list->initial.element[s+1].repcount = oldrepcount - t; |
| list->initial.count = newcount; |
| |
| VERIFY_LIST (list); |
| |
| return s+1; |
| } |
| |
| |
| /* Ensure index n in the initial segment is not shared. Return its index. */ |
| /* Memory effects: list is destructively modified. */ |
| static unsigned int |
| initial_unshare (struct format_arg_list *list, unsigned int n) |
| { |
| /* This does the same side effects as |
| initial_splitelement (list, n); |
| initial_splitelement (list, n + 1); |
| */ |
| unsigned int s; |
| unsigned int t; |
| |
| VERIFY_LIST (list); |
| |
| if (n >= list->initial.length) |
| { |
| ASSERT (list->repeated.count > 0); |
| rotate_loop (list, n + 1); |
| ASSERT (n < list->initial.length); |
| } |
| |
| /* Determine how many entries of list->initial need to be skipped. */ |
| for (t = n, s = 0; |
| s < list->initial.count && t >= list->initial.element[s].repcount; |
| t -= list->initial.element[s].repcount, s++) |
| ; |
| |
| /* s must be < list->initial.count. */ |
| ASSERT (s < list->initial.count); |
| |
| if (list->initial.element[s].repcount > 1) |
| { |
| /* Split the entry into at most three entries: for indices < n, |
| for index n, and for indices > n. */ |
| unsigned int oldrepcount = list->initial.element[s].repcount; |
| unsigned int newcount = |
| list->initial.count + (t == 0 || t == oldrepcount - 1 ? 1 : 2); |
| ensure_initial_alloc (list, newcount); |
| if (t == 0 || t == oldrepcount - 1) |
| { |
| unsigned int i; |
| |
| for (i = list->initial.count - 1; i > s; i--) |
| list->initial.element[i+1] = list->initial.element[i]; |
| copy_element (&list->initial.element[s+1], &list->initial.element[s]); |
| if (t == 0) |
| { |
| list->initial.element[s].repcount = 1; |
| list->initial.element[s+1].repcount = oldrepcount - 1; |
| } |
| else |
| { |
| list->initial.element[s].repcount = oldrepcount - 1; |
| list->initial.element[s+1].repcount = 1; |
| } |
| } |
| else |
| { |
| unsigned int i; |
| |
| for (i = list->initial.count - 1; i > s; i--) |
| list->initial.element[i+2] = list->initial.element[i]; |
| copy_element (&list->initial.element[s+2], &list->initial.element[s]); |
| copy_element (&list->initial.element[s+1], &list->initial.element[s]); |
| list->initial.element[s].repcount = t; |
| list->initial.element[s+1].repcount = 1; |
| list->initial.element[s+2].repcount = oldrepcount - 1 - t; |
| } |
| list->initial.count = newcount; |
| if (t > 0) |
| s++; |
| } |
| |
| /* Now the entry for index n has repcount 1. */ |
| ASSERT (list->initial.element[s].repcount == 1); |
| |
| VERIFY_LIST (list); |
| |
| return s; |
| } |
| |
| |
| /* Add n unconstrained elements at the front of the list. */ |
| /* Memory effects: list is destructively modified. */ |
| static void |
| shift_list (struct format_arg_list *list, unsigned int n) |
| { |
| VERIFY_LIST (list); |
| |
| if (n > 0) |
| { |
| unsigned int i; |
| |
| grow_initial_alloc (list); |
| for (i = list->initial.count; i > 0; i--) |
| list->initial.element[i] = list->initial.element[i-1]; |
| list->initial.element[0].repcount = n; |
| list->initial.element[0].presence = FCT_REQUIRED; |
| list->initial.element[0].type = FAT_OBJECT; |
| list->initial.count++; |
| list->initial.length += n; |
| |
| normalize_outermost_list (list); |
| } |
| |
| VERIFY_LIST (list); |
| } |
| |
| |
| /* ================= Intersection of two format_arg_lists ================= */ |
| |
| /* Create the intersection (i.e. combined constraints) of two argument |
| constraints. Return false if the intersection is empty, i.e. if the |
| two constraints give a contradiction. */ |
| /* Memory effects: Freshly allocated element's sublist. */ |
| static bool |
| make_intersected_element (struct format_arg *re, |
| const struct format_arg * e1, |
| const struct format_arg * e2) |
| { |
| /* Intersect the cdr types. */ |
| if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED) |
| re->presence = FCT_REQUIRED; |
| else |
| re->presence = FCT_OPTIONAL; |
| |
| /* Intersect the arg types. */ |
| if (e1->type == FAT_OBJECT) |
| { |
| re->type = e2->type; |
| if (re->type == FAT_LIST) |
| re->list = copy_list (e2->list); |
| } |
| else if (e2->type == FAT_OBJECT) |
| { |
| re->type = e1->type; |
| if (re->type == FAT_LIST) |
| re->list = copy_list (e1->list); |
| } |
| else if (e1->type == FAT_LIST |
| && (e2->type == FAT_CHARACTER_INTEGER_NULL |
| || e2->type == FAT_CHARACTER_NULL |
| || e2->type == FAT_INTEGER_NULL)) |
| { |
| re->type = e1->type; |
| re->list = make_intersection_with_empty_list (e1->list); |
| if (re->list == NULL) |
| return false; |
| } |
| else if (e2->type == FAT_LIST |
| && (e1->type == FAT_CHARACTER_INTEGER_NULL |
| || e1->type == FAT_CHARACTER_NULL |
| || e1->type == FAT_INTEGER_NULL)) |
| { |
| re->type = e2->type; |
| re->list = make_intersection_with_empty_list (e2->list); |
| if (re->list == NULL) |
| return false; |
| } |
| else if (e1->type == FAT_CHARACTER_INTEGER_NULL |
| && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER |
| || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER)) |
| { |
| re->type = e2->type; |
| } |
| else if (e2->type == FAT_CHARACTER_INTEGER_NULL |
| && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER |
| || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER)) |
| { |
| re->type = e1->type; |
| } |
| else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER) |
| { |
| re->type = e2->type; |
| } |
| else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER) |
| { |
| re->type = e1->type; |
| } |
| else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER) |
| { |
| re->type = e2->type; |
| } |
| else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER) |
| { |
| re->type = e1->type; |
| } |
| else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER) |
| { |
| re->type = e2->type; |
| } |
| else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER) |
| { |
| re->type = e1->type; |
| } |
| else if (e1->type == FAT_COMPLEX |
| && (e2->type == FAT_REAL || e2->type == FAT_INTEGER)) |
| { |
| re->type = e2->type; |
| } |
| else if (e2->type == FAT_COMPLEX |
| && (e1->type == FAT_REAL || e1->type == FAT_INTEGER)) |
| { |
| re->type = e1->type; |
| } |
| else if (e1->type == e2->type) |
| { |
| re->type = e1->type; |
| if (re->type == FAT_LIST) |
| { |
| re->list = make_intersected_list (copy_list (e1->list), |
| copy_list (e2->list)); |
| if (re->list == NULL) |
| return false; |
| } |
| } |
| else |
| /* Each of FAT_CHARACTER, FAT_INTEGER, FAT_LIST, FAT_FORMATSTRING |
| matches only itself. Contradiction. */ |
| return false; |
| |
| return true; |
| } |
| |
| /* Append list->repeated to list->initial, and clear list->repeated. */ |
| /* Memory effects: list is destructively modified. */ |
| static void |
| append_repeated_to_initial (struct format_arg_list *list) |
| { |
| if (list->repeated.count > 0) |
| { |
| /* Move list->repeated over to list->initial. */ |
| unsigned int i, j, newcount; |
| |
| newcount = list->initial.count + list->repeated.count; |
| ensure_initial_alloc (list, newcount); |
| i = list->initial.count; |
| for (j = 0; j < list->repeated.count; j++, i++) |
| list->initial.element[i] = list->repeated.element[j]; |
| list->initial.count = newcount; |
| list->initial.length = list->initial.length + list->repeated.length; |
| free (list->repeated.element); |
| list->repeated.element = NULL; |
| list->repeated.allocated = 0; |
| list->repeated.count = 0; |
| list->repeated.length = 0; |
| } |
| } |
| |
| /* Handle a contradiction during building of a format_arg_list. |
| The list consists only of an initial segment. The repeated segment is |
| empty. This function searches the last FCT_OPTIONAL and cuts off the |
| list at this point, or - if none is found - returns NULL. */ |
| /* Memory effects: list is destructively modified. If NULL is returned, |
| list is freed. */ |
| static struct format_arg_list * |
| backtrack_in_initial (struct format_arg_list *list) |
| { |
| ASSERT (list->repeated.count == 0); |
| |
| while (list->initial.count > 0) |
| { |
| unsigned int i = list->initial.count - 1; |
| if (list->initial.element[i].presence == FCT_REQUIRED) |
| { |
| /* Throw away this element. */ |
| list->initial.length -= list->initial.element[i].repcount; |
| free_element (&list->initial.element[i]); |
| list->initial.count = i; |
| } |
| else /* list->initial.element[i].presence == FCT_OPTIONAL */ |
| { |
| /* The list must end here. */ |
| list->initial.length--; |
| if (list->initial.element[i].repcount > 1) |
| list->initial.element[i].repcount--; |
| else |
| { |
| free_element (&list->initial.element[i]); |
| list->initial.count = i; |
| } |
| VERIFY_LIST (list); |
| return list; |
| } |
| } |
| |
| free_list (list); |
| return NULL; |
| } |
| |
| /* Create the intersection (i.e. combined constraints) of two argument list |
| constraints. Free both argument lists when done. Return NULL if the |
| intersection is empty, i.e. if the two constraints give a contradiction. */ |
| /* Memory effects: list1 and list2 are freed. The result, if non-NULL, is |
| freshly allocated. */ |
| static struct format_arg_list * |
| make_intersected_list (struct format_arg_list *list1, |
| struct format_arg_list *list2) |
| { |
| struct format_arg_list *result; |
| |
| VERIFY_LIST (list1); |
| VERIFY_LIST (list2); |
| |
| if (list1->repeated.length > 0 && list2->repeated.length > 0) |
| /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */ |
| { |
| unsigned int n1 = list1->repeated.length; |
| unsigned int n2 = list2->repeated.length; |
| unsigned int g = gcd (n1, n2); |
| unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */ |
| unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */ |
| |
| unfold_loop (list1, m1); |
| unfold_loop (list2, m2); |
| /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */ |
| } |
| |
| if (list1->repeated.length > 0 || list2->repeated.length > 0) |
| /* Step 2: Ensure the initial segment of the result can be computed |
| from the initial segments of list1 and list2. If both have a |
| repeated segment, this means to ensure |
| list1->initial.length == list2->initial.length. */ |
| { |
| unsigned int m = MAX (list1->initial.length, list2->initial.length); |
| |
| if (list1->repeated.length > 0) |
| rotate_loop (list1, m); |
| if (list2->repeated.length > 0) |
| rotate_loop (list2, m); |
| } |
| |
| if (list1->repeated.length > 0 && list2->repeated.length > 0) |
| { |
| ASSERT (list1->initial.length == list2->initial.length); |
| ASSERT (list1->repeated.length == list2->repeated.length); |
| } |
| |
| /* Step 3: Allocate the result. */ |
| result = XMALLOC (struct format_arg_list); |
| result->initial.count = 0; |
| result->initial.allocated = 0; |
| result->initial.element = NULL; |
| result->initial.length = 0; |
| result->repeated.count = 0; |
| result->repeated.allocated = 0; |
| result->repeated.element = NULL; |
| result->repeated.length = 0; |
| |
| /* Step 4: Elementwise intersection of list1->initial, list2->initial. */ |
| { |
| struct format_arg *e1; |
| struct format_arg *e2; |
| unsigned int c1; |
| unsigned int c2; |
| |
| e1 = list1->initial.element; c1 = list1->initial.count; |
| e2 = list2->initial.element; c2 = list2->initial.count; |
| while (c1 > 0 && c2 > 0) |
| { |
| struct format_arg *re; |
| |
| /* Ensure room in result->initial. */ |
| grow_initial_alloc (result); |
| re = &result->initial.element[result->initial.count]; |
| re->repcount = MIN (e1->repcount, e2->repcount); |
| |
| /* Intersect the argument types. */ |
| if (!make_intersected_element (re, e1, e2)) |
| { |
| /* If re->presence == FCT_OPTIONAL, the result list ends here. */ |
| if (re->presence == FCT_REQUIRED) |
| /* Contradiction. Backtrack. */ |
| result = backtrack_in_initial (result); |
| goto done; |
| } |
| |
| result->initial.count++; |
| result->initial.length += re->repcount; |
| |
| e1->repcount -= re->repcount; |
| if (e1->repcount == 0) |
| { |
| e1++; |
| c1--; |
| } |
| e2->repcount -= re->repcount; |
| if (e2->repcount == 0) |
| { |
| e2++; |
| c2--; |
| } |
| } |
| |
| if (list1->repeated.count == 0 && list2->repeated.count == 0) |
| { |
| /* Intersecting two finite lists. */ |
| if (c1 > 0) |
| { |
| /* list1 longer than list2. */ |
| if (e1->presence == FCT_REQUIRED) |
| /* Contradiction. Backtrack. */ |
| result = backtrack_in_initial (result); |
| } |
| else if (c2 > 0) |
| { |
| /* list2 longer than list1. */ |
| if (e2->presence == FCT_REQUIRED) |
| /* Contradiction. Backtrack. */ |
| result = backtrack_in_initial (result); |
| } |
| goto done; |
| } |
| else if (list1->repeated.count == 0) |
| { |
| /* Intersecting a finite and an infinite list. */ |
| ASSERT (c1 == 0); |
| if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence) |
| == FCT_REQUIRED) |
| /* Contradiction. Backtrack. */ |
| result = backtrack_in_initial (result); |
| goto done; |
| } |
| else if (list2->repeated.count == 0) |
| { |
| /* Intersecting an infinite and a finite list. */ |
| ASSERT (c2 == 0); |
| if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence) |
| == FCT_REQUIRED) |
| /* Contradiction. Backtrack. */ |
| result = backtrack_in_initial (result); |
| goto done; |
| } |
| /* Intersecting two infinite lists. */ |
| ASSERT (c1 == 0 && c2 == 0); |
| } |
| |
| /* Step 5: Elementwise intersection of list1->repeated, list2->repeated. */ |
| { |
| struct format_arg *e1; |
| struct format_arg *e2; |
| unsigned int c1; |
| unsigned int c2; |
| |
| e1 = list1->repeated.element; c1 = list1->repeated.count; |
| e2 = list2->repeated.element; c2 = list2->repeated.count; |
| while (c1 > 0 && c2 > 0) |
| { |
| struct format_arg *re; |
| |
| /* Ensure room in result->repeated. */ |
| grow_repeated_alloc (result); |
| re = &result->repeated.element[result->repeated.count]; |
| re->repcount = MIN (e1->repcount, e2->repcount); |
| |
| /* Intersect the argument types. */ |
| if (!make_intersected_element (re, e1, e2)) |
| { |
| bool re_is_required = re->presence == FCT_REQUIRED; |
| |
| append_repeated_to_initial (result); |
| |
| /* If re->presence == FCT_OPTIONAL, the result list ends here. */ |
| if (re_is_required) |
| /* Contradiction. Backtrack. */ |
| result = backtrack_in_initial (result); |
| |
| goto done; |
| } |
| |
| result->repeated.count++; |
| result->repeated.length += re->repcount; |
| |
| e1->repcount -= re->repcount; |
| if (e1->repcount == 0) |
| { |
| e1++; |
| c1--; |
| } |
| e2->repcount -= re->repcount; |
| if (e2->repcount == 0) |
| { |
| e2++; |
| c2--; |
| } |
| } |
| ASSERT (c1 == 0 && c2 == 0); |
| } |
| |
| done: |
| free_list (list1); |
| free_list (list2); |
| if (result != NULL) |
| { |
| /* Undo the loop unfolding and unrolling done above. */ |
| normalize_outermost_list (result); |
| VERIFY_LIST (result); |
| } |
| return result; |
| } |
| |
| |
| /* Create the intersection of an argument list and the empty list. |
| Return NULL if the intersection is empty. */ |
| /* Memory effects: The result, if non-NULL, is freshly allocated. */ |
| static struct format_arg_list * |
| make_intersection_with_empty_list (struct format_arg_list *list) |
| { |
| #if 0 /* equivalent but slower */ |
| return make_intersected_list (copy_list (list), make_empty_list ()); |
| #else |
| if (list->initial.count > 0 |
| ? list->initial.element[0].presence == FCT_REQUIRED |
| : list->repeated.count > 0 |
| && list->repeated.element[0].presence == FCT_REQUIRED) |
| return NULL; |
| else |
| return make_empty_list (); |
| #endif |
| } |
| |
| |
| #ifdef unused |
| /* Create the intersection of two argument list constraints. NULL stands |
| for an impossible situation, i.e. a contradiction. */ |
| /* Memory effects: list1 and list2 are freed if non-NULL. The result, |
| if non-NULL, is freshly allocated. */ |
| static struct format_arg_list * |
| intersection (struct format_arg_list *list1, struct format_arg_list *list2) |
| { |
| if (list1 != NULL) |
| { |
| if (list2 != NULL) |
| return make_intersected_list (list1, list2); |
| else |
| { |
| free_list (list1); |
| return NULL; |
| } |
| } |
| else |
| { |
| if (list2 != NULL) |
| { |
| free_list (list2); |
| return NULL; |
| } |
| else |
| return NULL; |
| } |
| } |
| #endif |
| |
| |
| /* ===================== Union of two format_arg_lists ===================== */ |
| |
| /* Create the union (i.e. alternative constraints) of two argument |
| constraints. */ |
| static void |
| make_union_element (struct format_arg *re, |
| const struct format_arg * e1, |
| const struct format_arg * e2) |
| { |
| /* Union of the cdr types. */ |
| if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED) |
| re->presence = FCT_REQUIRED; |
| else /* Either one of them is FCT_OPTIONAL. */ |
| re->presence = FCT_OPTIONAL; |
| |
| /* Union of the arg types. */ |
| if (e1->type == e2->type) |
| { |
| re->type = e1->type; |
| if (re->type == FAT_LIST) |
| re->list = make_union_list (copy_list (e1->list), |
| copy_list (e2->list)); |
| } |
| else if (e1->type == FAT_CHARACTER_INTEGER_NULL |
| && (e2->type == FAT_CHARACTER_NULL || e2->type == FAT_CHARACTER |
| || e2->type == FAT_INTEGER_NULL || e2->type == FAT_INTEGER)) |
| { |
| re->type = e1->type; |
| } |
| else if (e2->type == FAT_CHARACTER_INTEGER_NULL |
| && (e1->type == FAT_CHARACTER_NULL || e1->type == FAT_CHARACTER |
| || e1->type == FAT_INTEGER_NULL || e1->type == FAT_INTEGER)) |
| { |
| re->type = e2->type; |
| } |
| else if (e1->type == FAT_CHARACTER_NULL && e2->type == FAT_CHARACTER) |
| { |
| re->type = e1->type; |
| } |
| else if (e2->type == FAT_CHARACTER_NULL && e1->type == FAT_CHARACTER) |
| { |
| re->type = e2->type; |
| } |
| else if (e1->type == FAT_INTEGER_NULL && e2->type == FAT_INTEGER) |
| { |
| re->type = e1->type; |
| } |
| else if (e2->type == FAT_INTEGER_NULL && e1->type == FAT_INTEGER) |
| { |
| re->type = e2->type; |
| } |
| else if (e1->type == FAT_REAL && e2->type == FAT_INTEGER) |
| { |
| re->type = e1->type; |
| } |
| else if (e2->type == FAT_REAL && e1->type == FAT_INTEGER) |
| { |
| re->type = e2->type; |
| } |
| else if (e1->type == FAT_COMPLEX |
| && (e2->type == FAT_REAL || e2->type == FAT_INTEGER)) |
| { |
| re->type = e1->type; |
| } |
| else if (e2->type == FAT_COMPLEX |
| && (e1->type == FAT_REAL || e1->type == FAT_INTEGER)) |
| { |
| re->type = e2->type; |
| } |
| else if (e1->type == FAT_LIST && is_empty_list (e1->list)) |
| { |
| if (e2->type == FAT_CHARACTER_INTEGER_NULL |
| || e2->type == FAT_CHARACTER_NULL |
| || e2->type == FAT_INTEGER_NULL) |
| re->type = e2->type; |
| else if (e2->type == FAT_CHARACTER) |
| re->type = FAT_CHARACTER_NULL; |
| else if (e2->type == FAT_INTEGER) |
| re->type = FAT_INTEGER_NULL; |
| else |
| re->type = FAT_OBJECT; |
| } |
| else if (e2->type == FAT_LIST && is_empty_list (e2->list)) |
| { |
| if (e1->type == FAT_CHARACTER_INTEGER_NULL |
| || e1->type == FAT_CHARACTER_NULL |
| || e1->type == FAT_INTEGER_NULL) |
| re->type = e1->type; |
| else if (e1->type == FAT_CHARACTER) |
| re->type = FAT_CHARACTER_NULL; |
| else if (e1->type == FAT_INTEGER) |
| re->type = FAT_INTEGER_NULL; |
| else |
| re->type = FAT_OBJECT; |
| } |
| else if ((e1->type == FAT_CHARACTER || e1->type == FAT_CHARACTER_NULL) |
| && (e2->type == FAT_INTEGER || e2->type == FAT_INTEGER_NULL)) |
| { |
| re->type = FAT_CHARACTER_INTEGER_NULL; |
| } |
| else if ((e2->type == FAT_CHARACTER || e2->type == FAT_CHARACTER_NULL) |
| && (e1->type == FAT_INTEGER || e1->type == FAT_INTEGER_NULL)) |
| { |
| re->type = FAT_CHARACTER_INTEGER_NULL; |
| } |
| else |
| { |
| /* Other union types are too hard to describe precisely. */ |
| re->type = FAT_OBJECT; |
| } |
| } |
| |
| /* Create the union (i.e. alternative constraints) of two argument list |
| constraints. Free both argument lists when done. */ |
| /* Memory effects: list1 and list2 are freed. The result is freshly |
| allocated. */ |
| static struct format_arg_list * |
| make_union_list (struct format_arg_list *list1, struct format_arg_list *list2) |
| { |
| struct format_arg_list *result; |
| |
| VERIFY_LIST (list1); |
| VERIFY_LIST (list2); |
| |
| if (list1->repeated.length > 0 && list2->repeated.length > 0) |
| { |
| /* Step 1: Ensure list1->repeated.length == list2->repeated.length. */ |
| { |
| unsigned int n1 = list1->repeated.length; |
| unsigned int n2 = list2->repeated.length; |
| unsigned int g = gcd (n1, n2); |
| unsigned int m1 = n2 / g; /* = lcm(n1,n2) / n1 */ |
| unsigned int m2 = n1 / g; /* = lcm(n1,n2) / n2 */ |
| |
| unfold_loop (list1, m1); |
| unfold_loop (list2, m2); |
| /* Now list1->repeated.length = list2->repeated.length = lcm(n1,n2). */ |
| } |
| |
| /* Step 2: Ensure that list1->initial.length == list2->initial.length. */ |
| { |
| unsigned int m = MAX (list1->initial.length, list2->initial.length); |
| |
| rotate_loop (list1, m); |
| rotate_loop (list2, m); |
| } |
| |
| ASSERT (list1->initial.length == list2->initial.length); |
| ASSERT (list1->repeated.length == list2->repeated.length); |
| } |
| else if (list1->repeated.length > 0) |
| { |
| /* Ensure the initial segment of the result can be computed from the |
| initial segment of list1. */ |
| if (list2->initial.length >= list1->initial.length) |
| { |
| rotate_loop (list1, list2->initial.length); |
| if (list1->repeated.element[0].presence == FCT_REQUIRED) |
| rotate_loop (list1, list1->initial.length + 1); |
| } |
| } |
| else if (list2->repeated.length > 0) |
| { |
| /* Ensure the initial segment of the result can be computed from the |
| initial segment of list2. */ |
| if (list1->initial.length >= list2->initial.length) |
| { |
| rotate_loop (list2, list1->initial.length); |
| if (list2->repeated.element[0].presence == FCT_REQUIRED) |
| rotate_loop (list2, list2->initial.length + 1); |
| } |
| } |
| |
| /* Step 3: Allocate the result. */ |
| result = XMALLOC (struct format_arg_list); |
| result->initial.count = 0; |
| result->initial.allocated = 0; |
| result->initial.element = NULL; |
| result->initial.length = 0; |
| result->repeated.count = 0; |
| result->repeated.allocated = 0; |
| result->repeated.element = NULL; |
| result->repeated.length = 0; |
| |
| /* Step 4: Elementwise union of list1->initial, list2->initial. */ |
| { |
| struct format_arg *e1; |
| struct format_arg *e2; |
| unsigned int c1; |
| unsigned int c2; |
| |
| e1 = list1->initial.element; c1 = list1->initial.count; |
| e2 = list2->initial.element; c2 = list2->initial.count; |
| while (c1 > 0 && c2 > 0) |
| { |
| struct format_arg *re; |
| |
| /* Ensure room in result->initial. */ |
| grow_initial_alloc (result); |
| re = &result->initial.element[result->initial.count]; |
| re->repcount = MIN (e1->repcount, e2->repcount); |
| |
| /* Union of the argument types. */ |
| make_union_element (re, e1, e2); |
| |
| result->initial.count++; |
| result->initial.length += re->repcount; |
| |
| e1->repcount -= re->repcount; |
| if (e1->repcount == 0) |
| { |
| e1++; |
| c1--; |
| } |
| e2->repcount -= re->repcount; |
| if (e2->repcount == 0) |
| { |
| e2++; |
| c2--; |
| } |
| } |
| |
| if (c1 > 0) |
| { |
| /* list2 already terminated, but still more elements in list1->initial. |
| Copy them all, but turn the first presence to FCT_OPTIONAL. */ |
| ASSERT (list2->repeated.count == 0); |
| |
| if (e1->presence == FCT_REQUIRED) |
| { |
| struct format_arg *re; |
| |
| /* Ensure room in result->initial. */ |
| grow_initial_alloc (result); |
| re = &result->initial.element[result->initial.count]; |
| copy_element (re, e1); |
| re->presence = FCT_OPTIONAL; |
| re->repcount = 1; |
| result->initial.count++; |
| result->initial.length += 1; |
| e1->repcount -= 1; |
| if (e1->repcount == 0) |
| { |
| e1++; |
| c1--; |
| } |
| } |
| |
| /* Ensure room in result->initial. */ |
| ensure_initial_alloc (result, result->initial.count + c1); |
| while (c1 > 0) |
| { |
| struct format_arg *re; |
| |
| re = &result->initial.element[result->initial.count]; |
| copy_element (re, e1); |
| result->initial.count++; |
| result->initial.length += re->repcount; |
| e1++; |
| c1--; |
| } |
| } |
| else if (c2 > 0) |
| { |
| /* list1 already terminated, but still more elements in list2->initial. |
| Copy them all, but turn the first presence to FCT_OPTIONAL. */ |
| ASSERT (list1->repeated.count == 0); |
| |
| if (e2->presence == FCT_REQUIRED) |
| { |
| struct format_arg *re; |
| |
| /* Ensure room in result->initial. */ |
| grow_initial_alloc (result); |
| re = &result->initial.element[result->initial.count]; |
| copy_element (re, e2); |
| re->presence = FCT_OPTIONAL; |
| re->repcount = 1; |
| result->initial.count++; |
| result->initial.length += 1; |
| e2->repcount -= 1; |
| if (e2->repcount == 0) |
| { |
| e2++; |
| c2--; |
| } |
| } |
| |
| /* Ensure room in result->initial. */ |
| ensure_initial_alloc (result, result->initial.count + c2); |
| while (c2 > 0) |
| { |
| struct format_arg *re; |
| |
| re = &result->initial.element[result->initial.count]; |
| copy_element (re, e2); |
| result->initial.count++; |
| result->initial.length += re->repcount; |
| e2++; |
| c2--; |
| } |
| } |
| ASSERT (c1 == 0 && c2 == 0); |
| } |
| |
| if (list1->repeated.length > 0 && list2->repeated.length > 0) |
| /* Step 5: Elementwise union of list1->repeated, list2->repeated. */ |
| { |
| struct format_arg *e1; |
| struct format_arg *e2; |
| unsigned int c1; |
| unsigned int c2; |
| |
| e1 = list1->repeated.element; c1 = list1->repeated.count; |
| e2 = list2->repeated.element; c2 = list2->repeated.count; |
| while (c1 > 0 && c2 > 0) |
| { |
| struct format_arg *re; |
| |
| /* Ensure room in result->repeated. */ |
| grow_repeated_alloc (result); |
| re = &result->repeated.element[result->repeated.count]; |
| re->repcount = MIN (e1->repcount, e2->repcount); |
| |
| /* Union of the argument types. */ |
| make_union_element (re, e1, e2); |
| |
| result->repeated.count++; |
| result->repeated.length += re->repcount; |
| |
| e1->repcount -= re->repcount; |
| if (e1->repcount == 0) |
| { |
| e1++; |
| c1--; |
| } |
| e2->repcount -= re->repcount; |
| if (e2->repcount == 0) |
| { |
| e2++; |
| c2--; |
| } |
| } |
| ASSERT (c1 == 0 && c2 == 0); |
| } |
| else if (list1->repeated.length > 0) |
| { |
| /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the |
| initial segment. Just copy the repeated segment of list1. */ |
| unsigned int i; |
| |
| result->repeated.count = list1->repeated.count; |
| result->repeated.allocated = result->repeated.count; |
| result->repeated.element = |
| XNMALLOC (result->repeated.allocated, struct format_arg); |
| for (i = 0; i < list1->repeated.count; i++) |
| copy_element (&result->repeated.element[i], |
| &list1->repeated.element[i]); |
| result->repeated.length = list1->repeated.length; |
| } |
| else if (list2->repeated.length > 0) |
| { |
| /* Turning FCT_REQUIRED into FCT_OPTIONAL was already handled in the |
| initial segment. Just copy the repeated segment of list2. */ |
| unsigned int i; |
| |
| result->repeated.count = list2->repeated.count; |
| result->repeated.allocated = result->repeated.count; |
| result->repeated.element = |
| XNMALLOC (result->repeated.allocated, struct format_arg); |
| for (i = 0; i < list2->repeated.count; i++) |
| copy_element (&result->repeated.element[i], |
| &list2->repeated.element[i]); |
| result->repeated.length = list2->repeated.length; |
| } |
| |
| free_list (list1); |
| free_list (list2); |
| /* Undo the loop unfolding and unrolling done above. */ |
| normalize_outermost_list (result); |
| VERIFY_LIST (result); |
| return result; |
| } |
| |
| |
| /* Create the union of an argument list and the empty list. */ |
| /* Memory effects: list is freed. The result is freshly allocated. */ |
| static struct format_arg_list * |
| make_union_with_empty_list (struct format_arg_list *list) |
| { |
| #if 0 /* equivalent but slower */ |
| return make_union_list (list, make_empty_list ()); |
| #else |
| VERIFY_LIST (list); |
| |
| if (list->initial.count > 0 |
| ? list->initial.element[0].presence == FCT_REQUIRED |
| : list->repeated.count > 0 |
| && list->repeated.element[0].presence == FCT_REQUIRED) |
| { |
| initial_splitelement (list, 1); |
| ASSERT (list->initial.count > 0); |
| ASSERT (list->initial.element[0].repcount == 1); |
| ASSERT (list->initial.element[0].presence == FCT_REQUIRED); |
| list->initial.element[0].presence = FCT_OPTIONAL; |
| |
| /* We might need to merge list->initial.element[0] and |
| list->initial.element[1]. */ |
| normalize_outermost_list (list); |
| } |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| #endif |
| } |
| |
| |
| /* Create the union of two argument list constraints. NULL stands for an |
| impossible situation, i.e. a contradiction. */ |
| /* Memory effects: list1 and list2 are freed if non-NULL. The result, |
| if non-NULL, is freshly allocated. */ |
| static struct format_arg_list * |
| union (struct format_arg_list *list1, struct format_arg_list *list2) |
| { |
| if (list1 != NULL) |
| { |
| if (list2 != NULL) |
| return make_union_list (list1, list2); |
| else |
| return list1; |
| } |
| else |
| { |
| if (list2 != NULL) |
| return list2; |
| else |
| return NULL; |
| } |
| } |
| |
| |
| /* =========== Adding specific constraints to a format_arg_list =========== */ |
| |
| |
| /* Test whether arguments 0..n are required arguments in a list. */ |
| static bool |
| is_required (const struct format_arg_list *list, unsigned int n) |
| { |
| unsigned int s; |
| unsigned int t; |
| |
| /* We'll check whether the first n+1 presence flags are FCT_REQUIRED. */ |
| t = n + 1; |
| |
| /* Walk the list->initial segment. */ |
| for (s = 0; |
| s < list->initial.count && t >= list->initial.element[s].repcount; |
| t -= list->initial.element[s].repcount, s++) |
| if (list->initial.element[s].presence != FCT_REQUIRED) |
| return false; |
| |
| if (t == 0) |
| return true; |
| |
| if (s < list->initial.count) |
| { |
| if (list->initial.element[s].presence != FCT_REQUIRED) |
| return false; |
| else |
| return true; |
| } |
| |
| /* Walk the list->repeated segment. */ |
| if (list->repeated.count == 0) |
| return false; |
| |
| for (s = 0; |
| s < list->repeated.count && t >= list->repeated.element[s].repcount; |
| t -= list->repeated.element[s].repcount, s++) |
| if (list->repeated.element[s].presence != FCT_REQUIRED) |
| return false; |
| |
| if (t == 0) |
| return true; |
| |
| if (s < list->repeated.count) |
| { |
| if (list->repeated.element[s].presence != FCT_REQUIRED) |
| return false; |
| else |
| return true; |
| } |
| |
| /* The list->repeated segment consists only of FCT_REQUIRED. So, |
| regardless how many more passes through list->repeated would be |
| needed until t becomes 0, the result is true. */ |
| return true; |
| } |
| |
| |
| /* Add a constraint to an argument list, namely that the arguments 0...n are |
| present. NULL stands for an impossible situation, i.e. a contradiction. */ |
| /* Memory effects: list is freed. The result is freshly allocated. */ |
| static struct format_arg_list * |
| add_required_constraint (struct format_arg_list *list, unsigned int n) |
| { |
| unsigned int i, rest; |
| |
| if (list == NULL) |
| return NULL; |
| |
| VERIFY_LIST (list); |
| |
| if (list->repeated.count == 0 && list->initial.length <= n) |
| { |
| /* list is already constrained to have at most length n. |
| Contradiction. */ |
| free_list (list); |
| return NULL; |
| } |
| |
| initial_splitelement (list, n + 1); |
| |
| for (i = 0, rest = n + 1; rest > 0; ) |
| { |
| list->initial.element[i].presence = FCT_REQUIRED; |
| rest -= list->initial.element[i].repcount; |
| i++; |
| } |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| } |
| |
| |
| /* Add a constraint to an argument list, namely that the argument n is |
| never present. NULL stands for an impossible situation, i.e. a |
| contradiction. */ |
| /* Memory effects: list is freed. The result is freshly allocated. */ |
| static struct format_arg_list * |
| add_end_constraint (struct format_arg_list *list, unsigned int n) |
| { |
| unsigned int s, i; |
| enum format_cdr_type n_presence; |
| |
| if (list == NULL) |
| return NULL; |
| |
| VERIFY_LIST (list); |
| |
| if (list->repeated.count == 0 && list->initial.length <= n) |
| /* list is already constrained to have at most length n. */ |
| return list; |
| |
| s = initial_splitelement (list, n); |
| n_presence = |
| (s < list->initial.count |
| ? /* n < list->initial.length */ list->initial.element[s].presence |
| : /* n >= list->initial.length */ list->repeated.element[0].presence); |
| |
| for (i = s; i < list->initial.count; i++) |
| { |
| list->initial.length -= list->initial.element[i].repcount; |
| free_element (&list->initial.element[i]); |
| } |
| list->initial.count = s; |
| |
| for (i = 0; i < list->repeated.count; i++) |
| free_element (&list->repeated.element[i]); |
| if (list->repeated.element != NULL) |
| free (list->repeated.element); |
| list->repeated.element = NULL; |
| list->repeated.allocated = 0; |
| list->repeated.count = 0; |
| list->repeated.length = 0; |
| |
| if (n_presence == FCT_REQUIRED) |
| return backtrack_in_initial (list); |
| else |
| return list; |
| } |
| |
| |
| /* Add a constraint to an argument list, namely that the argument n is |
| of a given type. NULL stands for an impossible situation, i.e. a |
| contradiction. Assumes a preceding add_required_constraint (list, n). */ |
| /* Memory effects: list is freed. The result is freshly allocated. */ |
| static struct format_arg_list * |
| add_type_constraint (struct format_arg_list *list, unsigned int n, |
| enum format_arg_type type) |
| { |
| unsigned int s; |
| struct format_arg newconstraint; |
| struct format_arg tmpelement; |
| |
| if (list == NULL) |
| return NULL; |
| |
| /* Through the previous add_required_constraint, we can assume |
| list->initial.length >= n+1. */ |
| |
| s = initial_unshare (list, n); |
| |
| newconstraint.presence = FCT_OPTIONAL; |
| newconstraint.type = type; |
| if (!make_intersected_element (&tmpelement, |
| &list->initial.element[s], &newconstraint)) |
| return add_end_constraint (list, n); |
| free_element (&list->initial.element[s]); |
| list->initial.element[s].type = tmpelement.type; |
| list->initial.element[s].list = tmpelement.list; |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| } |
| |
| |
| /* Add a constraint to an argument list, namely that the argument n is |
| of a given list type. NULL stands for an impossible situation, i.e. a |
| contradiction. Assumes a preceding add_required_constraint (list, n). */ |
| /* Memory effects: list is freed. The result is freshly allocated. */ |
| 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) |
| { |
| unsigned int s; |
| struct format_arg newconstraint; |
| struct format_arg tmpelement; |
| |
| if (list == NULL) |
| return NULL; |
| |
| /* Through the previous add_required_constraint, we can assume |
| list->initial.length >= n+1. */ |
| |
| s = initial_unshare (list, n); |
| |
| newconstraint.presence = FCT_OPTIONAL; |
| newconstraint.type = type; |
| newconstraint.list = sublist; |
| if (!make_intersected_element (&tmpelement, |
| &list->initial.element[s], &newconstraint)) |
| return add_end_constraint (list, n); |
| free_element (&list->initial.element[s]); |
| list->initial.element[s].type = tmpelement.type; |
| list->initial.element[s].list = tmpelement.list; |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| } |
| |
| |
| /* ============= Subroutines used by the format string parser ============= */ |
| |
| static void |
| add_req_type_constraint (struct format_arg_list **listp, |
| unsigned int position, enum format_arg_type type) |
| { |
| *listp = add_required_constraint (*listp, position); |
| *listp = add_type_constraint (*listp, position, type); |
| } |
| |
| |
| static void |
| add_req_listtype_constraint (struct format_arg_list **listp, |
| unsigned int position, enum format_arg_type type, |
| struct format_arg_list *sublist) |
| { |
| *listp = add_required_constraint (*listp, position); |
| *listp = add_listtype_constraint (*listp, position, type, sublist); |
| } |
| |
| |
| /* Create an endless repeated list whose elements are lists constrained |
| by sublist. */ |
| /* Memory effects: sublist is freed. The result is freshly allocated. */ |
| static struct format_arg_list * |
| make_repeated_list_of_lists (struct format_arg_list *sublist) |
| { |
| if (sublist == NULL) |
| /* The list cannot have a single element. */ |
| return make_empty_list (); |
| else |
| { |
| struct format_arg_list *listlist; |
| |
| listlist = XMALLOC (struct format_arg_list); |
| |
| listlist->initial.count = 0; |
| listlist->initial.allocated = 0; |
| listlist->initial.element = NULL; |
| listlist->initial.length = 0; |
| listlist->repeated.count = 1; |
| listlist->repeated.allocated = 1; |
| listlist->repeated.element = XNMALLOC (1, struct format_arg); |
| listlist->repeated.element[0].repcount = 1; |
| listlist->repeated.element[0].presence = FCT_OPTIONAL; |
| listlist->repeated.element[0].type = FAT_LIST; |
| listlist->repeated.element[0].list = sublist; |
| listlist->repeated.length = 1; |
| |
| VERIFY_LIST (listlist); |
| |
| return listlist; |
| } |
| } |
| |
| |
| /* Create an endless repeated list which represents the union of a finite |
| number of copies of L, each time shifted by period: |
| () |
| L |
| L and (*^period L) |
| L and (*^period L) and (*^{2 period} L) |
| L and (*^period L) and (*^{2 period} L) and (*^{3 period} L) |
| ... |
| */ |
| /* Memory effects: sublist is freed. The result is freshly allocated. */ |
| static struct format_arg_list * |
| make_repeated_list (struct format_arg_list *sublist, unsigned int period) |
| { |
| struct segment tmp; |
| struct segment *srcseg; |
| struct format_arg_list *list; |
| unsigned int p, n, i, si, ti, j, sj, tj, splitindex, newcount; |
| bool ended; |
| |
| VERIFY_LIST (sublist); |
| |
| ASSERT (period > 0); |
| |
| if (sublist->repeated.count == 0) |
| { |
| /* L is a finite list. */ |
| |
| if (sublist->initial.length < period) |
| /* L and (*^period L) is a contradition, so we need to consider |
| only 1 and 0 iterations. */ |
| return make_union_with_empty_list (sublist); |
| |
| srcseg = &sublist->initial; |
| p = period; |
| } |
| else |
| { |
| /* L is an infinite list. */ |
| /* p := lcm (period, period of L) */ |
| unsigned int Lp = sublist->repeated.length; |
| unsigned int m = period / gcd (period, Lp); /* = lcm(period,Lp) / Lp */ |
| |
| unfold_loop (sublist, m); |
| p = m * Lp; |
| |
| /* Concatenate the initial and the repeated segments into a single |
| segment. */ |
| tmp.count = sublist->initial.count + sublist->repeated.count; |
| tmp.allocated = tmp.count; |
| tmp.element = XNMALLOC (tmp.allocated, struct format_arg); |
| for (i = 0; i < sublist->initial.count; i++) |
| tmp.element[i] = sublist->initial.element[i]; |
| for (j = 0; j < sublist->repeated.count; i++, j++) |
| tmp.element[i] = sublist->initial.element[j]; |
| tmp.length = sublist->initial.length + sublist->repeated.length; |
| |
| srcseg = &tmp; |
| } |
| |
| n = srcseg->length; |
| |
| /* Example: n = 7, p = 2 |
| Let L = (A B C D E F G). |
| |
| L = A B C D E F G |
| L & L<<p = A B C&A D&B E&C F&D G&E |
| L & L<<p & L<<2p = A B C&A D&B E&C&A F&D&B G&E&C |
| ... = A B C&A D&B E&C&A F&D&B G&E&C&A |
| |
| Thus the result has an initial segment of length n - p and a period |
| of p, and can be computed by floor(n/p) intersection operations. |
| Or by a single incremental intersection operation, going from left |
| to right. */ |
| |
| list = XMALLOC (struct format_arg_list); |
| list->initial.count = 0; |
| list->initial.allocated = 0; |
| list->initial.element = NULL; |
| list->initial.length = 0; |
| list->repeated.count = 0; |
| list->repeated.allocated = 0; |
| list->repeated.element = NULL; |
| list->repeated.length = 0; |
| |
| /* Sketch: |
| for (i = 0; i < p; i++) |
| list->initial.element[i] = srcseg->element[i]; |
| list->initial.element[0].presence = FCT_OPTIONAL; // union with empty list |
| for (i = p, j = 0; i < n; i++, j++) |
| list->initial.element[i] = srcseg->element[i] & list->initial.element[j]; |
| */ |
| |
| ended = false; |
| |
| i = 0, ti = 0, si = 0; |
| while (i < p) |
| { |
| unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i); |
| |
| /* Ensure room in list->initial. */ |
| grow_initial_alloc (list); |
| copy_element (&list->initial.element[list->initial.count], |
| &srcseg->element[si]); |
| list->initial.element[list->initial.count].repcount = k; |
| list->initial.count++; |
| list->initial.length += k; |
| |
| i += k; |
| ti += k; |
| if (ti == srcseg->element[si].repcount) |
| { |
| ti = 0; |
| si++; |
| } |
| } |
| |
| ASSERT (list->initial.count > 0); |
| if (list->initial.element[0].presence == FCT_REQUIRED) |
| { |
| initial_splitelement (list, 1); |
| ASSERT (list->initial.element[0].presence == FCT_REQUIRED); |
| ASSERT (list->initial.element[0].repcount == 1); |
| list->initial.element[0].presence = FCT_OPTIONAL; |
| } |
| |
| j = 0, tj = 0, sj = 0; |
| while (i < n) |
| { |
| unsigned int k = |
| MIN (srcseg->element[si].repcount - ti, |
| list->initial.element[sj].repcount - tj); |
| |
| /* Ensure room in list->initial. */ |
| grow_initial_alloc (list); |
| if (!make_intersected_element (&list->initial.element[list->initial.count], |
| &srcseg->element[si], |
| &list->initial.element[sj])) |
| { |
| if (list->initial.element[list->initial.count].presence == FCT_REQUIRED) |
| { |
| /* Contradiction. Backtrack. */ |
| list = backtrack_in_initial (list); |
| ASSERT (list != NULL); /* at least the empty list is valid */ |
| return list; |
| } |
| else |
| { |
| /* The list ends here. */ |
| ended = true; |
| break; |
| } |
| } |
| list->initial.element[list->initial.count].repcount = k; |
| list->initial.count++; |
| list->initial.length += k; |
| |
| i += k; |
| ti += k; |
| if (ti == srcseg->element[si].repcount) |
| { |
| ti = 0; |
| si++; |
| } |
| |
| j += k; |
| tj += k; |
| if (tj == list->initial.element[sj].repcount) |
| { |
| tj = 0; |
| sj++; |
| } |
| } |
| if (!ended) |
| ASSERT (list->initial.length == n); |
| |
| /* Add optional exit points at 0, period, 2*period etc. |
| FIXME: Not sure this is correct in all cases. */ |
| for (i = 0; i < list->initial.length; i += period) |
| { |
| si = initial_unshare (list, i); |
| list->initial.element[si].presence = FCT_OPTIONAL; |
| } |
| |
| if (!ended) |
| { |
| /* Now split off the repeated part. */ |
| splitindex = initial_splitelement (list, n - p); |
| newcount = list->initial.count - splitindex; |
| if (newcount > list->repeated.allocated) |
| { |
| list->repeated.allocated = newcount; |
| list->repeated.element = XNMALLOC (newcount, struct format_arg); |
| } |
| for (i = splitindex, j = 0; i < n; i++, j++) |
| list->repeated.element[j] = list->initial.element[i]; |
| list->repeated.count = newcount; |
| list->repeated.length = p; |
| list->initial.count = splitindex; |
| list->initial.length = n - p; |
| } |
| |
| VERIFY_LIST (list); |
| |
| return list; |
| } |
| |
| |
| /* ================= Handling of format string directives ================= */ |
| |
| /* Possible signatures of format directives. */ |
| static const enum format_arg_type I [1] = { FAT_INTEGER_NULL }; |
| static const enum format_arg_type II [2] = { |
| FAT_INTEGER_NULL, FAT_INTEGER_NULL |
| }; |
| static const enum format_arg_type IIC [3] = { |
| FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL |
| }; |
| static const enum format_arg_type ICCI [4] = { |
| FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_INTEGER_NULL |
| }; |
| static const enum format_arg_type IIIC [4] = { |
| FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL |
| }; |
| static const enum format_arg_type IICCI [5] = { |
| FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, |
| FAT_INTEGER_NULL |
| }; |
| static const enum format_arg_type IIICC [5] = { |
| FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_CHARACTER_NULL, |
| FAT_CHARACTER_NULL |
| }; |
| static const enum format_arg_type IIIICCC [7] = { |
| FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, FAT_INTEGER_NULL, |
| FAT_CHARACTER_NULL, FAT_CHARACTER_NULL, FAT_CHARACTER_NULL |
| }; |
| static const enum format_arg_type THREE [3] = { |
| FAT_CHARACTER_INTEGER_NULL, FAT_CHARACTER_INTEGER_NULL, |
| FAT_CHARACTER_INTEGER_NULL |
| }; |
| |
| |
| /* Check the parameters. For V params, add the constraint to the argument |
| list. Return false and fill in *invalid_reason if the format string is |
| invalid. */ |
| 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) |
| { |
| unsigned int orig_paramcount = paramcount; |
| unsigned int orig_t_count = t_count; |
| |
| for (; paramcount > 0 && t_count > 0; |
| params++, paramcount--, t_types++, t_count--) |
| { |
| switch (*t_types) |
| { |
| case FAT_CHARACTER_INTEGER_NULL: |
| break; |
| case FAT_CHARACTER_NULL: |
| switch (params->type) |
| { |
| case PT_NIL: case PT_CHARACTER: case PT_V: |
| break; |
| case PT_INTEGER: case PT_ARGCOUNT: |
| /* wrong param type */ |
| *invalid_reason = |
| 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"); |
| return false; |
| } |
| break; |
| case FAT_INTEGER_NULL: |
| switch (params->type) |
| { |
| case PT_NIL: case PT_INTEGER: case PT_ARGCOUNT: case PT_V: |
| break; |
| case PT_CHARACTER: |
| /* wrong param type */ |
| *invalid_reason = |
| 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"); |
| return false; |
| } |
| break; |
| default: |
| abort (); |
| } |
| if (params->type == PT_V) |
| { |
| int position = params->value; |
| if (position >= 0) |
| add_req_type_constraint (listp, position, *t_types); |
| } |
| } |
| |
| for (; paramcount > 0; params++, paramcount--) |
| switch (params->type) |
| { |
| case PT_NIL: |
| break; |
| case PT_CHARACTER: case PT_INTEGER: case PT_ARGCOUNT: |
| /* too many params for directive */ |
| *invalid_reason = |
| xasprintf (ngettext ("In the directive number %u, too many parameters are given; expected at most %u parameter.", |
| "In the directive number %u, too many parameters are given; expected at most %u parameters.", |
| orig_t_count), |
| directives, orig_t_count); |
| return false; |
| case PT_V: |
| /* Force argument to be NIL. */ |
| { |
| int position = params->value; |
| if (position >= 0) |
| { |
| struct format_arg_list *empty_list = make_empty_list (); |
| add_req_listtype_constraint (listp, position, |
| FAT_LIST, empty_list); |
| free_list (empty_list); |
| } |
| } |
| break; |
| } |
| |
| return true; |
| } |
| |
| |
| /* ======================= The format string parser ======================= */ |
| |
| /* Parse a piece of format string, until the matching terminating format |
| directive is encountered. |
| format is the remainder of the format string. |
| position is the position in this argument list, if known, or -1 if unknown. |
| list represents the argument list constraints at the current parse point. |
| NULL stands for a contradiction. |
| escape represents the union of the argument list constraints at all the |
| currently pending FORMAT-UP-AND-OUT points. NULL stands for a contradiction |
| or an empty union. |
| All four are updated upon valid return. |
| *separatorp is set to true if the parse terminated due to a ~; separator, |
| more precisely to 2 if with colon, or to 1 if without colon. |
| spec is the global struct spec. |
| terminator is the directive that terminates this parse. |
| separator specifies if ~; separators are allowed. |
| fdi is an array to be filled with format directive indicators, or NULL. |
| If the format string is invalid, false is returned and *invalid_reason is |
| set to an error message explaining why. */ |
| 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) |
| { |
| const char *format = *formatp; |
| const char *const format_start = format; |
| int position = *positionp; |
| struct format_arg_list *list = *listp; |
| struct format_arg_list *escape = *escapep; |
| |
| for (; *format != '\0'; ) |
| if (*format++ == '~') |
| { |
| bool colon_p = false; |
| bool atsign_p = false; |
| unsigned int paramcount = 0; |
| struct param *params = NULL; |
| |
| FDI_SET (format - 1, FMTDIR_START); |
| |
| /* Count number of directives. */ |
| spec->directives++; |
| |
| /* Parse parameters. */ |
| for (;;) |
| { |
| enum param_type type = PT_NIL; |
| int value = 0; |
| |
| if (c_isdigit (*format)) |
| { |
| type = PT_INTEGER; |
| do |
| { |
| value = 10 * value + (*format - '0'); |
| format++; |
| } |
| while (c_isdigit (*format)); |
| } |
| else if (*format == '+' || *format == '-') |
| { |
| bool negative = (*format == '-'); |
| type = PT_INTEGER; |
| format++; |
| if (!c_isdigit (*format)) |
| { |
| if (*format == '\0') |
| { |
| *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE (); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| } |
| else |
| { |
| *invalid_reason = |
| xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]); |
| FDI_SET (format, FMTDIR_ERROR); |
| } |
| return false; |
| } |
| do |
| { |
| value = 10 * value + (*format - '0'); |
| format++; |
| } |
| while (c_isdigit (*format)); |
| if (negative) |
| value = -value; |
| } |
| else if (*format == '\'') |
| { |
| type = PT_CHARACTER; |
| format++; |
| if (*format == '\0') |
| { |
| *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE (); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| format++; |
| } |
| else if (*format == 'V' || *format == 'v') |
| { |
| type = PT_V; |
| format++; |
| value = position; |
| /* Consumes an argument. */ |
| if (position >= 0) |
| position++; |
| } |
| else if (*format == '#') |
| { |
| type = PT_ARGCOUNT; |
| format++; |
| } |
| |
| params = |
| (struct param *) |
| xrealloc (params, (paramcount + 1) * sizeof (struct param)); |
| params[paramcount].type = type; |
| params[paramcount].value = value; |
| paramcount++; |
| |
| if (*format == ',') |
| format++; |
| else |
| break; |
| } |
| |
| /* Parse modifiers. */ |
| for (;;) |
| { |
| if (*format == ':') |
| { |
| format++; |
| colon_p = true; |
| } |
| else if (*format == '@') |
| { |
| format++; |
| atsign_p = true; |
| } |
| else |
| break; |
| } |
| |
| /* Parse directive. */ |
| switch (*format++) |
| { |
| case 'A': case 'a': /* 22.3.4.1 FORMAT-ASCII */ |
| case 'S': case 's': /* 22.3.4.2 FORMAT-S-EXPRESSION */ |
| if (!check_params (&list, paramcount, params, 4, IIIC, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_OBJECT); |
| break; |
| |
| case 'C': case 'c': /* FORMAT-CHARACTER */ |
| if (!check_params (&list, paramcount, params, 1, I, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (paramcount == 0 |
| || (paramcount == 1 && params[0].type == PT_NIL)) |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_CHARACTER); |
| break; |
| |
| case 'D': case 'd': /* 22.3.2.2 FORMAT-DECIMAL */ |
| case 'B': case 'b': /* 22.3.2.3 FORMAT-BINARY */ |
| case 'O': case 'o': /* 22.3.2.4 FORMAT-OCTAL */ |
| case 'X': case 'x': /* 22.3.2.5 FORMAT-HEXADECIMAL */ |
| if (!check_params (&list, paramcount, params, 4, ICCI, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_INTEGER); |
| break; |
| |
| case 'R': case 'r': /* 22.3.2.1 FORMAT-RADIX */ |
| if (!check_params (&list, paramcount, params, 5, IICCI, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_INTEGER); |
| break; |
| |
| case 'P': case 'p': /* 22.3.8.3 FORMAT-PLURAL */ |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (colon_p) |
| { |
| /* Go back by 1 argument. */ |
| if (position > 0) |
| position--; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_OBJECT); |
| break; |
| |
| case 'F': case 'f': /* 22.3.3.1 FORMAT-FIXED-FLOAT */ |
| if (!check_params (&list, paramcount, params, 5, IIICC, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_REAL); |
| break; |
| |
| case 'E': case 'e': /* 22.3.3.2 FORMAT-EXPONENTIAL-FLOAT */ |
| case 'G': case 'g': /* 22.3.3.3 FORMAT-GENERAL-FLOAT */ |
| if (!check_params (&list, paramcount, params, 7, IIIICCC, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_REAL); |
| break; |
| |
| case '$': /* 22.3.3.4 FORMAT-DOLLARS-FLOAT */ |
| if (!check_params (&list, paramcount, params, 4, IIIC, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_REAL); |
| break; |
| |
| case 'I': case 'i': /* FORMAT-FIXED-FLOAT-COMPLEX */ |
| if (!check_params (&list, paramcount, params, 5, IIICC, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_COMPLEX); |
| break; |
| |
| case 'Y': case 'y': /* FORMAT-PRETTY */ |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_OBJECT); |
| break; |
| |
| case '%': /* 22.3.1.2 FORMAT-TERPRI */ |
| case '&': /* 22.3.1.3 FORMAT-FRESH-LINE */ |
| case '_': /* FORMAT-SPACE */ |
| case '/': /* FORMAT-TAB */ |
| case '|': /* 22.3.1.4 FORMAT-PAGE */ |
| case '~': /* 22.3.1.5 FORMAT-TILDE */ |
| if (!check_params (&list, paramcount, params, 1, I, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| break; |
| |
| case '!': /* FORMAT-FORCE-OUTPUT */ |
| case '\n': /* 22.3.9.3 #\Newline */ |
| case 'Q': case 'q': /* FORMAT-IMPLEMENTATION */ |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| break; |
| |
| case 'T': case 't': /* FORMAT-TABULATE */ |
| if (!check_params (&list, paramcount, params, 3, IIC, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| break; |
| |
| case '*': /* 22.3.7.1 FORMAT-GOTO */ |
| if (!check_params (&list, paramcount, params, 1, I, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| { |
| int n; /* value of first parameter */ |
| if (paramcount == 0 |
| || (paramcount >= 1 && params[0].type == PT_NIL)) |
| n = (atsign_p ? 0 : 1); |
| else if (paramcount >= 1 && params[0].type == PT_INTEGER) |
| n = params[0].value; |
| else |
| { |
| /* Unknown argument, leads to an unknown position. */ |
| position = -1; |
| break; |
| } |
| if (n < 0) |
| { |
| /* invalid argument */ |
| *invalid_reason = |
| xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (atsign_p) |
| { |
| /* Absolute goto. */ |
| position = n; |
| } |
| else if (colon_p) |
| { |
| /* Backward goto. */ |
| if (n > 0) |
| { |
| if (position >= 0) |
| { |
| if (position >= n) |
| position -= n; |
| else |
| position = 0; |
| } |
| else |
| position = -1; |
| } |
| } |
| else |
| { |
| /* Forward goto. */ |
| if (position >= 0) |
| position += n; |
| } |
| } |
| break; |
| |
| case '?': case 'K': case 'k': /* 22.3.7.6 FORMAT-INDIRECTION */ |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_FORMATSTRING); |
| if (atsign_p) |
| position = -1; |
| else |
| if (position >= 0) |
| { |
| struct format_arg_list *sublist = make_unconstrained_list (); |
| add_req_listtype_constraint (&list, position++, |
| FAT_LIST, sublist); |
| free_list (sublist); |
| } |
| break; |
| |
| case '(': /* 22.3.8.1 FORMAT-CASE-CONVERSION */ |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| *formatp = format; |
| *positionp = position; |
| *listp = list; |
| *escapep = escape; |
| { |
| if (!parse_upto (formatp, positionp, listp, escapep, |
| NULL, spec, ')', false, |
| NULL, invalid_reason)) |
| { |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| } |
| format = *formatp; |
| position = *positionp; |
| list = *listp; |
| escape = *escapep; |
| break; |
| |
| case ')': /* 22.3.8.2 FORMAT-CASE-CONVERSION-END */ |
| if (terminator != ')') |
| { |
| *invalid_reason = |
| xasprintf (_("Found '~%c' without matching '~%c'."), ')', '('); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| *formatp = format; |
| *positionp = position; |
| *listp = list; |
| *escapep = escape; |
| return true; |
| |
| case '[': /* 22.3.7.2 FORMAT-CONDITIONAL */ |
| if (atsign_p && colon_p) |
| { |
| *invalid_reason = |
| xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| else if (atsign_p) |
| { |
| struct format_arg_list *nil_list; |
| struct format_arg_list *union_list; |
| |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| |
| *formatp = format; |
| *escapep = escape; |
| |
| /* First alternative: argument is NIL. */ |
| nil_list = (list != NULL ? copy_list (list) : NULL); |
| if (position >= 0) |
| { |
| struct format_arg_list *empty_list = make_empty_list (); |
| add_req_listtype_constraint (&nil_list, position, |
| FAT_LIST, empty_list); |
| free_list (empty_list); |
| } |
| |
| /* Second alternative: use sub-format. */ |
| { |
| int sub_position = position; |
| struct format_arg_list *sub_list = |
| (list != NULL ? copy_list (list) : NULL); |
| if (!parse_upto (formatp, &sub_position, &sub_list, escapep, |
| NULL, spec, ']', false, |
| NULL, invalid_reason)) |
| { |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| if (sub_list != NULL) |
| { |
| if (position >= 0) |
| { |
| if (sub_position == position + 1) |
| /* new position is branch independent */ |
| position = position + 1; |
| else |
| /* new position is branch dependent */ |
| position = -1; |
| } |
| } |
| else |
| { |
| if (position >= 0) |
| position = position + 1; |
| } |
| union_list = union (nil_list, sub_list); |
| } |
| |
| format = *formatp; |
| escape = *escapep; |
| |
| if (list != NULL) |
| free_list (list); |
| list = union_list; |
| } |
| else if (colon_p) |
| { |
| int union_position; |
| struct format_arg_list *union_list; |
| |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_OBJECT); |
| |
| *formatp = format; |
| *escapep = escape; |
| union_position = -2; |
| union_list = NULL; |
| |
| /* First alternative. */ |
| { |
| int sub_position = position; |
| struct format_arg_list *sub_list = |
| (list != NULL ? copy_list (list) : NULL); |
| int sub_separator = 0; |
| if (position >= 0) |
| { |
| struct format_arg_list *empty_list = make_empty_list (); |
| add_req_listtype_constraint (&sub_list, position - 1, |
| FAT_LIST, empty_list); |
| free_list (empty_list); |
| } |
| if (!parse_upto (formatp, &sub_position, &sub_list, escapep, |
| &sub_separator, spec, ']', true, |
| NULL, invalid_reason)) |
| { |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| if (!sub_separator) |
| { |
| *invalid_reason = |
| xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives); |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| if (sub_list != NULL) |
| union_position = sub_position; |
| union_list = union (union_list, sub_list); |
| } |
| |
| /* Second alternative. */ |
| { |
| int sub_position = position; |
| struct format_arg_list *sub_list = |
| (list != NULL ? copy_list (list) : NULL); |
| if (!parse_upto (formatp, &sub_position, &sub_list, escapep, |
| NULL, spec, ']', false, |
| NULL, invalid_reason)) |
| { |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| if (sub_list != NULL) |
| { |
| if (union_position == -2) |
| union_position = sub_position; |
| else if (sub_position < 0 |
| || sub_position != union_position) |
| union_position = -1; |
| } |
| union_list = union (union_list, sub_list); |
| } |
| |
| format = *formatp; |
| escape = *escapep; |
| |
| if (union_position != -2) |
| position = union_position; |
| if (list != NULL) |
| free_list (list); |
| list = union_list; |
| } |
| else |
| { |
| int arg_position; |
| int union_position; |
| struct format_arg_list *union_list; |
| bool last_alternative; |
| |
| if (!check_params (&list, paramcount, params, 1, I, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| |
| /* If there was no first parameter, an argument is consumed. */ |
| arg_position = -1; |
| if (!(paramcount >= 1 && params[0].type != PT_NIL)) |
| if (position >= 0) |
| { |
| arg_position = position; |
| add_req_type_constraint (&list, position++, FAT_OBJECT); |
| } |
| |
| *formatp = format; |
| *escapep = escape; |
| |
| union_position = -2; |
| union_list = NULL; |
| last_alternative = false; |
| for (;;) |
| { |
| /* Next alternative. */ |
| int sub_position = position; |
| struct format_arg_list *sub_list = |
| (list != NULL ? copy_list (list) : NULL); |
| int sub_separator = 0; |
| if (!parse_upto (formatp, &sub_position, &sub_list, escapep, |
| &sub_separator, spec, ']', !last_alternative, |
| NULL, invalid_reason)) |
| { |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| /* If this alternative is chosen, the argument arg_position |
| is an integer, namely the index of this alternative. */ |
| if (!last_alternative && arg_position >= 0) |
| add_req_type_constraint (&sub_list, arg_position, |
| FAT_INTEGER); |
| if (sub_list != NULL) |
| { |
| if (union_position == -2) |
| union_position = sub_position; |
| else if (sub_position < 0 |
| || sub_position != union_position) |
| union_position = -1; |
| } |
| union_list = union (union_list, sub_list); |
| if (sub_separator == 2) |
| last_alternative = true; |
| if (!sub_separator) |
| break; |
| } |
| if (!last_alternative) |
| { |
| /* An implicit default alternative. */ |
| if (union_position == -2) |
| union_position = position; |
| else if (position < 0 || position != union_position) |
| union_position = -1; |
| if (list != NULL) |
| union_list = union (union_list, copy_list (list)); |
| } |
| |
| format = *formatp; |
| escape = *escapep; |
| |
| if (union_position != -2) |
| position = union_position; |
| if (list != NULL) |
| free_list (list); |
| list = union_list; |
| } |
| break; |
| |
| case ']': /* 22.3.7.3 FORMAT-CONDITIONAL-END */ |
| if (terminator != ']') |
| { |
| *invalid_reason = |
| xasprintf (_("Found '~%c' without matching '~%c'."), ']', '['); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| *formatp = format; |
| *positionp = position; |
| *listp = list; |
| *escapep = escape; |
| return true; |
| |
| case '{': /* 22.3.7.4 FORMAT-ITERATION */ |
| if (!check_params (&list, paramcount, params, 1, I, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| *formatp = format; |
| { |
| int sub_position = 0; |
| struct format_arg_list *sub_list = make_unconstrained_list (); |
| struct format_arg_list *sub_escape = NULL; |
| struct spec sub_spec; |
| sub_spec.directives = 0; |
| sub_spec.list = sub_list; |
| if (!parse_upto (formatp, &sub_position, &sub_list, &sub_escape, |
| NULL, &sub_spec, '}', false, |
| NULL, invalid_reason)) |
| { |
| FDI_SET (**formatp == '\0' ? *formatp - 1 : *formatp, |
| FMTDIR_ERROR); |
| return false; |
| } |
| spec->directives += sub_spec.directives; |
| |
| /* If the sub-formatstring is empty, except for the terminating |
| ~} directive, a formatstring argument is consumed. */ |
| if (*format == '~' && sub_spec.directives == 1) |
| if (position >= 0) |
| add_req_type_constraint (&list, position++, FAT_FORMATSTRING); |
| |
| if (colon_p) |
| { |
| /* Each iteration uses a new sublist. */ |
| struct format_arg_list *listlist; |
| |
| /* ~{ catches ~^. */ |
| sub_list = union (sub_list, sub_escape); |
| |
| listlist = make_repeated_list_of_lists (sub_list); |
| |
| sub_list = listlist; |
| } |
| else |
| { |
| /* Each iteration's arguments are all concatenated in a |
| single list. */ |
| struct format_arg_list *looplist; |
| |
| /* FIXME: This is far from correct. Test cases: |
| abc~{~^~} |
| abc~{~S~^~S~} |
| abc~{~D~^~C~} |
| abc~{~D~^~D~} |
| abc~{~D~^~S~} |
| abc~{~D~^~C~}~:*~{~S~^~D~} |
| */ |
| |
| /* ~{ catches ~^. */ |
| sub_list = union (sub_list, sub_escape); |
| |
| if (sub_list == NULL) |
| looplist = make_empty_list (); |
| else |
| if (sub_position < 0 || sub_position == 0) |
| /* Too hard to track the possible argument types |
| when the iteration is performed 2 times or more. |
| So be satisfied with the constraints of executing |
| the iteration 1 or 0 times. */ |
| looplist = make_union_with_empty_list (sub_list); |
| else |
| looplist = make_repeated_list (sub_list, sub_position); |
| |
| sub_list = looplist; |
| } |
| |
| if (atsign_p) |
| { |
| /* All remaining arguments are used. */ |
| if (list != NULL && position >= 0) |
| { |
| shift_list (sub_list, position); |
| list = make_intersected_list (list, sub_list); |
| } |
| position = -1; |
| } |
| else |
| { |
| /* The argument is a list. */ |
| if (position >= 0) |
| add_req_listtype_constraint (&list, position++, |
| FAT_LIST, sub_list); |
| } |
| } |
| format = *formatp; |
| break; |
| |
| case '}': /* 22.3.7.5 FORMAT-ITERATION-END */ |
| if (terminator != '}') |
| { |
| *invalid_reason = |
| xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{'); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| *formatp = format; |
| *positionp = position; |
| *listp = list; |
| *escapep = escape; |
| return true; |
| |
| case '^': /* 22.3.9.2 FORMAT-UP-AND-OUT */ |
| if (!check_params (&list, paramcount, params, 3, THREE, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (position >= 0 && list != NULL && is_required (list, position)) |
| /* This ~^ can never be executed. Ignore it. */ |
| break; |
| if (list != NULL) |
| { |
| struct format_arg_list *this_escape = copy_list (list); |
| if (position >= 0) |
| this_escape = add_end_constraint (this_escape, position); |
| escape = union (escape, this_escape); |
| } |
| if (position >= 0) |
| list = add_required_constraint (list, position); |
| break; |
| |
| case ';': /* 22.3.9.1 FORMAT-SEPARATOR */ |
| if (!separator) |
| { |
| *invalid_reason = |
| xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| if (terminator == '>') |
| { |
| if (!check_params (&list, paramcount, params, 1, I, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| } |
| else |
| { |
| if (!check_params (&list, paramcount, params, 0, NULL, |
| spec->directives, invalid_reason)) |
| { |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| return false; |
| } |
| } |
| *formatp = format; |
| *positionp = position; |
| *listp = list; |
| *escapep = escape; |
| *separatorp = (colon_p ? 2 : 1); |
| return true; |
| |
| default: |
| --format; |
| if (*format == '\0') |
| { |
| *invalid_reason = INVALID_UNTERMINATED_DIRECTIVE (); |
| FDI_SET (format - 1, FMTDIR_ERROR); |
| } |
| else |
| { |
| *invalid_reason = |
| INVALID_CONVERSION_SPECIFIER (spec->directives, *format); |
| FDI_SET (format, FMTDIR_ERROR); |
| } |
| return false; |
| } |
| |
| FDI_SET (format - 1, FMTDIR_END); |
| |
| free (params); |
| } |
| |
| *formatp = format; |
| *positionp = position; |
| *listp = list; |
| *escapep = escape; |
| if (terminator != '\0') |
| { |
| *invalid_reason = |
| xasprintf (_("Found '~%c' without matching '~%c'."), terminator - 1, terminator); |
| return false; |
| } |
| return true; |
| } |
| |
| |
| /* ============== Top level format string handling functions ============== */ |
| |
| static void * |
| format_parse (const char *format, bool translated, char *fdi, |
| char **invalid_reason) |
| { |
| struct spec spec; |
| struct spec *result; |
| int position = 0; |
| struct format_arg_list *escape; |
| |
| spec.directives = 0; |
| spec.list = make_unconstrained_list (); |
| escape = NULL; |
| |
| if (!parse_upto (&format, &position, &spec.list, &escape, |
| NULL, &spec, '\0', false, |
| fdi, invalid_reason)) |
| /* Invalid format string. */ |
| return NULL; |
| |
| /* Catch ~^ here. */ |
| spec.list = union (spec.list, escape); |
| |
| if (spec.list == NULL) |
| { |
| /* Contradictory argument type information. */ |
| *invalid_reason = |
| xstrdup (_("The string refers to some argument in incompatible ways.")); |
| return NULL; |
| } |
| |
| /* Normalize the result. */ |
| normalize_list (spec.list); |
| |
| result = XMALLOC (struct spec); |
| *result = spec; |
| return result; |
| } |
| |
| static void |
| format_free (void *descr) |
| { |
| struct spec *spec = (struct spec *) descr; |
| |
| free_list (spec->list); |
| } |
| |
| static int |
| format_get_number_of_directives (void *descr) |
| { |
| struct spec *spec = (struct spec *) descr; |
| |
| return spec->directives; |
| } |
| |
| 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) |
| { |
| struct spec *spec1 = (struct spec *) msgid_descr; |
| struct spec *spec2 = (struct spec *) msgstr_descr; |
| bool err = false; |
| |
| if (equality) |
| { |
| if (!equal_list (spec1->list, spec2->list)) |
| { |
| if (error_logger) |
| error_logger (_("format specifications in '%s' and '%s' are not equivalent"), |
| pretty_msgid, pretty_msgstr); |
| err = true; |
| } |
| } |
| else |
| { |
| struct format_arg_list *intersection = |
| make_intersected_list (copy_list (spec1->list), |
| copy_list (spec2->list)); |
| |
| if (!(intersection != NULL |
| && (normalize_list (intersection), |
| equal_list (intersection, spec2->list)))) |
| { |
| if (error_logger) |
| error_logger (_("format specifications in '%s' are not a subset of those in '%s'"), |
| pretty_msgstr, pretty_msgid); |
| err = true; |
| } |
| } |
| |
| return err; |
| } |
| |
| |
| struct formatstring_parser formatstring_scheme = |
| { |
| format_parse, |
| format_free, |
| format_get_number_of_directives, |
| NULL, |
| format_check |
| }; |
| |
| |
| /* ============================= Testing code ============================= */ |
| |
| #undef union |
| |
| #ifdef TEST |
| |
| /* Test program: Print the argument list specification returned by |
| format_parse for strings read from standard input. */ |
| |
| #include <stdio.h> |
| |
| static void print_list (struct format_arg_list *list); |
| |
| static void |
| print_element (struct format_arg *element) |
| { |
| switch (element->presence) |
| { |
| case FCT_REQUIRED: |
| break; |
| case FCT_OPTIONAL: |
| printf (". "); |
| break; |
| default: |
| abort (); |
| } |
| |
| switch (element->type) |
| { |
| case FAT_OBJECT: |
| printf ("*"); |
| break; |
| case FAT_CHARACTER_INTEGER_NULL: |
| printf ("ci()"); |
| break; |
| case FAT_CHARACTER_NULL: |
| printf ("c()"); |
| break; |
| case FAT_CHARACTER: |
| printf ("c"); |
| break; |
| case FAT_INTEGER_NULL: |
| printf ("i()"); |
| break; |
| case FAT_INTEGER: |
| printf ("i"); |
| break; |
| case FAT_REAL: |
| printf ("r"); |
| break; |
| case FAT_COMPLEX: |
| printf ("C"); |
| break; |
| case FAT_LIST: |
| print_list (element->list); |
| break; |
| case FAT_FORMATSTRING: |
| printf ("~"); |
| break; |
| default: |
| abort (); |
| } |
| } |
| |
| static void |
| print_list (struct format_arg_list *list) |
| { |
| unsigned int i, j; |
| |
| printf ("("); |
| |
| for (i = 0; i < list->initial.count; i++) |
| for (j = 0; j < list->initial.element[i].repcount; j++) |
| { |
| if (i > 0 || j > 0) |
| printf (" "); |
| print_element (&list->initial.element[i]); |
| } |
| |
| if (list->repeated.count > 0) |
| { |
| printf (" |"); |
| for (i = 0; i < list->repeated.count; i++) |
| for (j = 0; j < list->repeated.element[i].repcount; j++) |
| { |
| printf (" "); |
| print_element (&list->repeated.element[i]); |
| } |
| } |
| |
| printf (")"); |
| } |
| |
| static void |
| format_print (void *descr) |
| { |
| struct spec *spec = (struct spec *) descr; |
| |
| if (spec == NULL) |
| { |
| printf ("INVALID"); |
| return; |
| } |
| |
| print_list (spec->list); |
| } |
| |
| int |
| main () |
| { |
| for (;;) |
| { |
| char *line = NULL; |
| size_t line_size = 0; |
| int line_len; |
| char *invalid_reason; |
| void *descr; |
| |
| line_len = getline (&line, &line_size, stdin); |
| if (line_len < 0) |
| break; |
| if (line_len > 0 && line[line_len - 1] == '\n') |
| line[--line_len] = '\0'; |
| |
| invalid_reason = NULL; |
| descr = format_parse (line, false, NULL, &invalid_reason); |
| |
| format_print (descr); |
| printf ("\n"); |
| if (descr == NULL) |
| printf ("%s\n", invalid_reason); |
| |
| free (invalid_reason); |
| free (line); |
| } |
| |
| return 0; |
| } |
| |
| /* |
| * For Emacs M-x compile |
| * Local Variables: |
| * compile-command: "/bin/sh ../libtool --tag=CC --mode=link gcc -o a.out -static -O -g -Wall -I.. -I../gnulib-lib -I../../gettext-runtime/intl -DHAVE_CONFIG_H -DTEST format-scheme.c ../gnulib-lib/libgettextlib.la" |
| * End: |
| */ |
| |
| #endif /* TEST */ |