#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 "xerror.h"
#include "format-invalid.h"
#include "minmax.h"
#include "error.h"
#include "error-progname.h"
#include "gettext.h"
#define _(str) gettext (str)
#define ASSERT(expr) if (!(expr)) abort ();
#define VERIFY_LIST(list) verify_list (list)
enum format_cdr_type
{
FCT_REQUIRED,
FCT_OPTIONAL
};
enum format_arg_type
{
FAT_OBJECT,
FAT_CHARACTER_INTEGER_NULL,
FAT_CHARACTER_NULL,
FAT_CHARACTER,
FAT_INTEGER_NULL,
FAT_INTEGER,
FAT_REAL,
FAT_LIST,
FAT_FORMATSTRING,
FAT_FUNCTION
};
struct format_arg
{
unsigned int repcount;
enum format_cdr_type presence;
enum format_arg_type type;
struct format_arg_list *list;
};
struct format_arg_list
{
struct segment
{
unsigned int count;
unsigned int allocated;
struct format_arg *element;
unsigned int length;
}
initial,
repeated;
};
struct spec
{
unsigned int directives;
struct format_arg_list *list;
};
enum param_type
{
PT_NIL,
PT_CHARACTER,
PT_INTEGER,
PT_ARGCOUNT,
PT_V
};
struct param
{
enum param_type type;
int value;
};
#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);
static void
verify_element (const struct format_arg * e)
{
ASSERT (e->repcount > 0);
if (e->type == FAT_LIST)
verify_list (e->list);
}
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)
static inline void
free_element (struct format_arg *element)
{
if (element->type == FAT_LIST)
free_list (element->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);
}
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);
}
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 =
(struct format_arg_list *) xmalloc (sizeof (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 =
(struct format_arg *)
xmalloc (newlist->initial.allocated * sizeof (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 =
(struct format_arg *)
xmalloc (newlist->repeated.allocated * sizeof (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;
}
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));
}
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;
}
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));
}
}
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));
}
}
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));
}
}
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));
}
}
static void
normalize_outermost_list (struct format_arg_list *list)
{
unsigned int n, i, j;
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;
if (list->repeated.count > 0)
{
unsigned int m, repcount0_extra;
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--;
}
for (m = 2; m <= n / 2; n++)
if ((n % m) == 0)
{
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;
}
}
if (list->repeated.count == 1)
{
if (list->initial.count > 0
&& equal_element (&list->initial.element[list->initial.count-1],
&list->repeated.element[0]))
{
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);
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;
}
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--;
}
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;
}
}
}
}
static void
normalize_list (struct format_arg_list *list)
{
unsigned int n, i;
VERIFY_LIST (list);
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);
normalize_outermost_list (list);
VERIFY_LIST (list);
}
static struct format_arg_list *
make_unconstrained_list ()
{
struct format_arg_list *list;
list = (struct format_arg_list *) xmalloc (sizeof (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 =
(struct format_arg *) xmalloc (1 * sizeof (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;
}
static struct format_arg_list *
make_empty_list ()
{
struct format_arg_list *list;
list = (struct format_arg_list *) xmalloc (sizeof (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;
}
static bool
is_empty_list (const struct format_arg_list *list)
{
return (list->initial.count == 0 && list->repeated.count == 0);
}
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;
}
}
static void
rotate_loop (struct format_arg_list *list, unsigned int m)
{
if (m == list->initial.length)
return;
if (list->repeated.count == 1)
{
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;
unsigned int q = (m - list->initial.length) / n;
unsigned int r = (m - list->initial.length) % n;
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++)
;
ASSERT (s < list->repeated.count);
{
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;
list->initial.length = m;
}
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 =
(struct format_arg *)
xmalloc (newcount * sizeof (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;
}
}
}
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);
}
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);
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;
}
static unsigned int
initial_unshare (struct format_arg_list *list, unsigned int n)
{
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);
}
for (t = n, s = 0;
s < list->initial.count && t >= list->initial.element[s].repcount;
t -= list->initial.element[s].repcount, s++)
;
ASSERT (s < list->initial.count);
if (list->initial.element[s].repcount > 1)
{
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++;
}
ASSERT (list->initial.element[s].repcount == 1);
VERIFY_LIST (list);
return s;
}
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);
}
static bool
make_intersected_element (struct format_arg *re,
const struct format_arg * e1,
const struct format_arg * e2)
{
if (e1->presence == FCT_REQUIRED || e2->presence == FCT_REQUIRED)
re->presence = FCT_REQUIRED;
else
re->presence = FCT_OPTIONAL;
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 == 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
return false;
return true;
}
static void
append_repeated_to_initial (struct format_arg_list *list)
{
if (list->repeated.count > 0)
{
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;
}
}
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)
{
list->initial.length -= list->initial.element[i].repcount;
free_element (&list->initial.element[i]);
list->initial.count = i;
}
else
{
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;
}
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)
{
unsigned int n1 = list1->repeated.length;
unsigned int n2 = list2->repeated.length;
unsigned int g = gcd (n1, n2);
unsigned int m1 = n2 / g;
unsigned int m2 = n1 / g;
unfold_loop (list1, m1);
unfold_loop (list2, m2);
}
if (list1->repeated.length > 0 || list2->repeated.length > 0)
{
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);
}
result =
(struct format_arg_list *) xmalloc (sizeof (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;
{
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;
grow_initial_alloc (result);
re = &result->initial.element[result->initial.count];
re->repcount = MIN (e1->repcount, e2->repcount);
if (!make_intersected_element (re, e1, e2))
{
if (re->presence == FCT_REQUIRED)
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)
{
if (c1 > 0)
{
if (e1->presence == FCT_REQUIRED)
result = backtrack_in_initial (result);
}
else if (c2 > 0)
{
if (e2->presence == FCT_REQUIRED)
result = backtrack_in_initial (result);
}
goto done;
}
else if (list1->repeated.count == 0)
{
ASSERT (c1 == 0);
if ((c2 > 0 ? e2->presence : list2->repeated.element[0].presence)
== FCT_REQUIRED)
result = backtrack_in_initial (result);
goto done;
}
else if (list2->repeated.count == 0)
{
ASSERT (c2 == 0);
if ((c1 > 0 ? e1->presence : list1->repeated.element[0].presence)
== FCT_REQUIRED)
result = backtrack_in_initial (result);
goto done;
}
ASSERT (c1 == 0 && c2 == 0);
}
{
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;
grow_repeated_alloc (result);
re = &result->repeated.element[result->repeated.count];
re->repcount = MIN (e1->repcount, e2->repcount);
if (!make_intersected_element (re, e1, e2))
{
append_repeated_to_initial (result);
if (re->presence == FCT_REQUIRED)
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)
{
normalize_outermost_list (result);
VERIFY_LIST (result);
}
return result;
}
static struct format_arg_list *
make_intersection_with_empty_list (struct format_arg_list *list)
{
#if 0
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
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
static void
make_union_element (struct format_arg *re,
const struct format_arg * e1,
const struct format_arg * e2)
{
if (e1->presence == FCT_REQUIRED && e2->presence == FCT_REQUIRED)
re->presence = FCT_REQUIRED;
else
re->presence = FCT_OPTIONAL;
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_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
{
re->type = FAT_OBJECT;
}
}
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)
{
{
unsigned int n1 = list1->repeated.length;
unsigned int n2 = list2->repeated.length;
unsigned int g = gcd (n1, n2);
unsigned int m1 = n2 / g;
unsigned int m2 = n1 / g;
unfold_loop (list1, m1);
unfold_loop (list2, m2);
}
{
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)
{
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)
{
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);
}
}
result =
(struct format_arg_list *) xmalloc (sizeof (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;
{
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;
grow_initial_alloc (result);
re = &result->initial.element[result->initial.count];
re->repcount = MIN (e1->repcount, e2->repcount);
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)
{
ASSERT (list2->repeated.count == 0);
if (e1->presence == FCT_REQUIRED)
{
struct format_arg *re;
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_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)
{
ASSERT (list1->repeated.count == 0);
if (e2->presence == FCT_REQUIRED)
{
struct format_arg *re;
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_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)
{
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;
grow_repeated_alloc (result);
re = &result->repeated.element[result->repeated.count];
re->repcount = MIN (e1->repcount, e2->repcount);
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)
{
unsigned int i;
result->repeated.count = list1->repeated.count;
result->repeated.allocated = result->repeated.count;
result->repeated.element =
(struct format_arg *)
xmalloc (result->repeated.allocated * sizeof (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)
{
unsigned int i;
result->repeated.count = list2->repeated.count;
result->repeated.allocated = result->repeated.count;
result->repeated.element =
(struct format_arg *)
xmalloc (result->repeated.allocated * sizeof (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);
normalize_outermost_list (result);
VERIFY_LIST (result);
return result;
}
static struct format_arg_list *
make_union_with_empty_list (struct format_arg_list *list)
{
#if 0
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;
normalize_outermost_list (list);
}
VERIFY_LIST (list);
return list;
#endif
}
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;
}
}
static bool
is_required (const struct format_arg_list *list, unsigned int n)
{
unsigned int s;
unsigned int t;
t = n + 1;
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;
}
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;
}
return true;
}
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)
{
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;
}
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)
return list;
s = initial_splitelement (list, n);
n_presence =
(s < list->initial.count
? list->initial.element[s].presence
: 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;
}
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;
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;
}
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;
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;
}
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);
}
static struct format_arg_list *
make_repeated_list_of_lists (struct format_arg_list *sublist)
{
if (sublist == NULL)
return make_empty_list ();
else
{
struct format_arg_list *listlist;
listlist =
(struct format_arg_list *) xmalloc (sizeof (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 =
(struct format_arg *) xmalloc (1 * sizeof (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;
}
}
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)
{
if (sublist->initial.length < period)
return make_union_with_empty_list (sublist);
srcseg = &sublist->initial;
p = period;
}
else
{
unsigned int Lp = sublist->repeated.length;
unsigned int m = period / gcd (period, Lp);
unfold_loop (sublist, m);
p = m * Lp;
tmp.count = sublist->initial.count + sublist->repeated.count;
tmp.allocated = tmp.count;
tmp.element =
(struct format_arg *)
xmalloc (tmp.allocated * sizeof (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;
list = (struct format_arg_list *) xmalloc (sizeof (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;
ended = false;
i = 0, ti = 0, si = 0;
while (i < p)
{
unsigned int k = MIN (srcseg->element[si].repcount - ti, p - i);
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);
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)
{
list = backtrack_in_initial (list);
ASSERT (list != NULL);
return list;
}
else
{
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);
for (i = 0; i < list->initial.length; i += period)
{
si = initial_unshare (list, i);
list->initial.element[si].presence = FCT_OPTIONAL;
}
if (!ended)
{
splitindex = initial_splitelement (list, n - p);
newcount = list->initial.count - splitindex;
if (newcount > list->repeated.allocated)
{
list->repeated.allocated = newcount;
list->repeated.element =
(struct format_arg *) xmalloc (newcount * sizeof (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;
}
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 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
};
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:
*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:
*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:
*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:
{
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;
}
static bool
nocheck_params (struct format_arg_list **listp,
unsigned int paramcount, struct param *params,
unsigned int directives, char **invalid_reason)
{
(void) directives;
(void) invalid_reason;
for (; paramcount > 0; params++, paramcount--)
if (params->type == PT_V)
{
int position = params->value;
add_req_type_constraint (listp, position, FAT_CHARACTER_INTEGER_NULL);
}
return true;
}
static bool
parse_upto (const char **formatp,
int *positionp, struct format_arg_list **listp,
struct format_arg_list **escapep, int *separatorp,
struct spec *spec, char terminator, bool separator,
char **invalid_reason)
{
const char *format = *formatp;
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;
spec->directives++;
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))
{
*invalid_reason =
(*format == '\0'
? INVALID_UNTERMINATED_DIRECTIVE ()
: xasprintf (_("In the directive number %u, '%c' is not followed by a digit."), spec->directives, format[-1]));
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 ();
return false;
}
format++;
}
else if (*format == 'V' || *format == 'v')
{
type = PT_V;
format++;
value = position;
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;
}
for (;;)
{
if (*format == ':')
{
format++;
colon_p = true;
}
else if (*format == '@')
{
format++;
atsign_p = true;
}
else
break;
}
switch (*format++)
{
case 'A': case 'a':
case 'S': case 's':
if (!check_params (&list, paramcount, params, 4, IIIC,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_OBJECT);
break;
case 'W': case 'w':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_OBJECT);
break;
case 'D': case 'd':
case 'B': case 'b':
case 'O': case 'o':
case 'X': case 'x':
if (!check_params (&list, paramcount, params, 4, ICCI,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_INTEGER);
break;
case 'R': case 'r':
if (!check_params (&list, paramcount, params, 5, IICCI,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_INTEGER);
break;
case 'P': case 'p':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
if (colon_p)
{
if (position > 0)
position--;
}
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_OBJECT);
break;
case 'C': case 'c':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_CHARACTER);
break;
case 'F': case 'f':
if (!check_params (&list, paramcount, params, 5, IIICC,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_REAL);
break;
case 'E': case 'e':
case 'G': case 'g':
if (!check_params (&list, paramcount, params, 7, IIIICCC,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_REAL);
break;
case '$':
if (!check_params (&list, paramcount, params, 4, IIIC,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_REAL);
break;
case '%':
case '&':
case '|':
case '~':
case 'I': case 'i':
if (!check_params (&list, paramcount, params, 1, I,
spec->directives, invalid_reason))
return false;
break;
case '\n':
case '_':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
break;
case 'T': case 't':
if (!check_params (&list, paramcount, params, 2, II,
spec->directives, invalid_reason))
return false;
break;
case '*':
if (!check_params (&list, paramcount, params, 1, I,
spec->directives, invalid_reason))
return false;
{
int n;
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
{
position = -1;
break;
}
if (n < 0)
{
*invalid_reason =
xasprintf (_("In the directive number %u, the argument %d is negative."), spec->directives, n);
return false;
}
if (atsign_p)
{
position = n;
}
else if (colon_p)
{
if (n > 0)
{
if (position >= 0)
{
if (position >= n)
position -= n;
else
position = 0;
}
else
position = -1;
}
}
else
{
if (position >= 0)
position += n;
}
}
break;
case '?':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
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 '/':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_OBJECT);
while (*format != '\0' && *format != '/')
format++;
if (*format == '\0')
{
*invalid_reason =
xstrdup (_("The string ends in the middle of a ~/.../ directive."));
return false;
}
format++;
break;
case '(':
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
*formatp = format;
*positionp = position;
*listp = list;
*escapep = escape;
{
if (!parse_upto (formatp, positionp, listp, escapep,
NULL, spec, ')', false,
invalid_reason))
return false;
}
format = *formatp;
position = *positionp;
list = *listp;
escape = *escapep;
break;
case ')':
if (terminator != ')')
{
*invalid_reason =
xasprintf (_("Found '~%c' without matching '~%c'."), ')', '(');
return false;
}
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
*formatp = format;
*positionp = position;
*listp = list;
*escapep = escape;
return true;
case '[':
if (atsign_p && colon_p)
{
*invalid_reason =
xasprintf (_("In the directive number %u, both the @ and the : modifiers are given."), spec->directives);
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))
return false;
*formatp = format;
*escapep = escape;
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);
}
{
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,
invalid_reason))
return false;
if (sub_list != NULL)
{
if (position >= 0)
{
if (sub_position == position + 1)
position = position + 1;
else
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))
return false;
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_OBJECT);
*formatp = format;
*escapep = escape;
union_position = -2;
union_list = NULL;
{
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,
invalid_reason))
return false;
if (!sub_separator)
{
*invalid_reason =
xasprintf (_("In the directive number %u, '~:[' is not followed by two clauses, separated by '~;'."), spec->directives);
return false;
}
if (sub_list != NULL)
union_position = sub_position;
union_list = union (union_list, sub_list);
}
{
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,
invalid_reason))
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 union_position;
struct format_arg_list *union_list;
bool last_alternative;
if (!check_params (&list, paramcount, params, 1, I,
spec->directives, invalid_reason))
return false;
if (!(paramcount >= 1 && params[0].type != PT_NIL))
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_OBJECT);
*formatp = format;
*escapep = escape;
union_position = -2;
union_list = NULL;
last_alternative = false;
for (;;)
{
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,
invalid_reason))
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);
if (sub_separator == 2)
last_alternative = true;
if (!sub_separator)
break;
}
if (!last_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 ']':
if (terminator != ']')
{
*invalid_reason =
xasprintf (_("Found '~%c' without matching '~%c'."), ']', '[');
return false;
}
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
*formatp = format;
*positionp = position;
*listp = list;
*escapep = escape;
return true;
case '{':
if (!check_params (&list, paramcount, params, 1, I,
spec->directives, invalid_reason))
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,
invalid_reason))
return false;
spec->directives += sub_spec.directives;
if (*format == '~' && sub_spec.directives == 1)
if (position >= 0)
add_req_type_constraint (&list, position++, FAT_FORMATSTRING);
if (colon_p)
{
struct format_arg_list *listlist;
sub_list = union (sub_list, sub_escape);
listlist = make_repeated_list_of_lists (sub_list);
sub_list = listlist;
}
else
{
struct format_arg_list *looplist;
sub_list = union (sub_list, sub_escape);
if (sub_list == NULL)
looplist = make_empty_list ();
else
if (sub_position < 0 || sub_position == 0)
looplist = make_union_with_empty_list (sub_list);
else
looplist = make_repeated_list (sub_list, sub_position);
sub_list = looplist;
}
if (atsign_p)
{
if (list != NULL && position >= 0)
{
shift_list (sub_list, position);
list = make_intersected_list (list, sub_list);
}
position = -1;
}
else
{
if (position >= 0)
add_req_listtype_constraint (&list, position++,
FAT_LIST, sub_list);
}
}
format = *formatp;
break;
case '}':
if (terminator != '}')
{
*invalid_reason =
xasprintf (_("Found '~%c' without matching '~%c'."), '}', '{');
return false;
}
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
*formatp = format;
*positionp = position;
*listp = list;
*escapep = escape;
return true;
case '<':
if (!check_params (&list, paramcount, params, 4, IIIC,
spec->directives, invalid_reason))
return false;
{
struct format_arg_list *sub_escape = NULL;
*formatp = format;
*positionp = position;
*listp = list;
for (;;)
{
int sub_separator = 0;
if (!parse_upto (formatp, positionp, listp, &sub_escape,
&sub_separator, spec, '>', true,
invalid_reason))
return false;
if (!sub_separator)
break;
}
format = *formatp;
position = *positionp;
list = *listp;
if (sub_escape != NULL)
position = -1;
list = union (list, sub_escape);
}
break;
case '>':
if (terminator != '>')
{
*invalid_reason =
xasprintf (_("Found '~%c' without matching '~%c'."), '>', '<');
return false;
}
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
*formatp = format;
*positionp = position;
*listp = list;
*escapep = escape;
return true;
case '^':
if (!check_params (&list, paramcount, params, 3, THREE,
spec->directives, invalid_reason))
return false;
if (position >= 0 && list != NULL && is_required (list, position))
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 ';':
if (!separator)
{
*invalid_reason =
xasprintf (_("In the directive number %u, '~;' is used in an invalid position."), spec->directives);
return false;
}
if (terminator == '>')
{
if (!check_params (&list, paramcount, params, 1, I,
spec->directives, invalid_reason))
return false;
}
else
{
if (!check_params (&list, paramcount, params, 0, NULL,
spec->directives, invalid_reason))
return false;
}
*formatp = format;
*positionp = position;
*listp = list;
*escapep = escape;
*separatorp = (colon_p ? 2 : 1);
return true;
case '!':
if (!nocheck_params (&list, paramcount, params,
spec->directives, invalid_reason))
return false;
if (position >= 0)
{
add_req_type_constraint (&list, position++, FAT_FUNCTION);
add_req_type_constraint (&list, position++, FAT_OBJECT);
}
break;
default:
--format;
*invalid_reason =
(*format == '\0'
? INVALID_UNTERMINATED_DIRECTIVE ()
: INVALID_CONVERSION_SPECIFIER (spec->directives, *format));
return false;
}
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;
}
static void *
format_parse (const char *format, 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,
invalid_reason))
return NULL;
spec.list = union (spec.list, escape);
if (spec.list == NULL)
{
*invalid_reason =
xstrdup (_("The string refers to some argument in incompatible ways."));
return NULL;
}
normalize_list (spec.list);
result = (struct spec *) xmalloc (sizeof (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 (const lex_pos_ty *pos, void *msgid_descr, void *msgstr_descr,
bool equality, bool noisy, 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 (noisy)
{
error_with_progname = false;
error_at_line (0, 0, pos->file_name, pos->line_number,
_("format specifications in 'msgid' and '%s' are not equivalent"),
pretty_msgstr);
error_with_progname = true;
}
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 (noisy)
{
error_with_progname = false;
error_at_line (0, 0, pos->file_name, pos->line_number,
_("format specifications in '%s' are not a subset of those in 'msgid'"),
pretty_msgstr);
error_with_progname = true;
}
err = true;
}
}
return err;
}
struct formatstring_parser formatstring_lisp =
{
format_parse,
format_free,
format_get_number_of_directives,
format_check
};
#undef union
#ifdef TEST
#include <stdio.h>
#include "getline.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_LIST:
print_list (element->list);
break;
case FAT_FORMATSTRING:
printf ("~");
break;
case FAT_FUNCTION:
printf ("f");
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, &invalid_reason);
format_print (descr);
printf ("\n");
if (descr == NULL)
printf ("%s\n", invalid_reason);
free (invalid_reason);
free (line);
}
return 0;
}
#endif