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