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