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