1 /* vi:set ts=8 sts=4 sw=4 noet: 2 * 3 * VIM - Vi IMproved by Bram Moolenaar 4 * 5 * Do ":help uganda" in Vim to read copying and usage conditions. 6 * Do ":help credits" in Vim to see a list of people who contributed. 7 * See README.txt for an overview of the Vim source code. 8 */ 9 10 /* 11 * list.c: List support and container (List, Dict, Blob) functions. 12 */ 13 14 #include "vim.h" 15 16 #if defined(FEAT_EVAL) || defined(PROTO) 17 18 static char *e_listblobarg = N_("E899: Argument of %s must be a List or Blob"); 19 20 // List heads for garbage collection. 21 static list_T *first_list = NULL; // list of all lists 22 23 #define FOR_ALL_WATCHERS(l, lw) \ 24 for ((lw) = (l)->lv_watch; (lw) != NULL; (lw) = (lw)->lw_next) 25 26 static void list_free_item(list_T *l, listitem_T *item); 27 28 /* 29 * Add a watcher to a list. 30 */ 31 void 32 list_add_watch(list_T *l, listwatch_T *lw) 33 { 34 lw->lw_next = l->lv_watch; 35 l->lv_watch = lw; 36 } 37 38 /* 39 * Remove a watcher from a list. 40 * No warning when it isn't found... 41 */ 42 void 43 list_rem_watch(list_T *l, listwatch_T *lwrem) 44 { 45 listwatch_T *lw, **lwp; 46 47 lwp = &l->lv_watch; 48 FOR_ALL_WATCHERS(l, lw) 49 { 50 if (lw == lwrem) 51 { 52 *lwp = lw->lw_next; 53 break; 54 } 55 lwp = &lw->lw_next; 56 } 57 } 58 59 /* 60 * Just before removing an item from a list: advance watchers to the next 61 * item. 62 */ 63 static void 64 list_fix_watch(list_T *l, listitem_T *item) 65 { 66 listwatch_T *lw; 67 68 FOR_ALL_WATCHERS(l, lw) 69 if (lw->lw_item == item) 70 lw->lw_item = item->li_next; 71 } 72 73 static void 74 list_init(list_T *l) 75 { 76 // Prepend the list to the list of lists for garbage collection. 77 if (first_list != NULL) 78 first_list->lv_used_prev = l; 79 l->lv_used_prev = NULL; 80 l->lv_used_next = first_list; 81 first_list = l; 82 } 83 84 /* 85 * Allocate an empty header for a list. 86 * Caller should take care of the reference count. 87 */ 88 list_T * 89 list_alloc(void) 90 { 91 list_T *l; 92 93 l = ALLOC_CLEAR_ONE(list_T); 94 if (l != NULL) 95 list_init(l); 96 return l; 97 } 98 99 /* 100 * list_alloc() with an ID for alloc_fail(). 101 */ 102 list_T * 103 list_alloc_id(alloc_id_T id UNUSED) 104 { 105 #ifdef FEAT_EVAL 106 if (alloc_fail_id == id && alloc_does_fail(sizeof(list_T))) 107 return NULL; 108 #endif 109 return (list_alloc()); 110 } 111 112 /* 113 * Allocate space for a list, plus "count" items. 114 * Next list_set_item() must be called for each item. 115 */ 116 list_T * 117 list_alloc_with_items(int count) 118 { 119 list_T *l; 120 121 l = (list_T *)alloc_clear(sizeof(list_T) + count * sizeof(listitem_T)); 122 if (l != NULL) 123 { 124 list_init(l); 125 126 if (count > 0) 127 { 128 listitem_T *li = (listitem_T *)(l + 1); 129 int i; 130 131 l->lv_len = count; 132 l->lv_with_items = count; 133 l->lv_first = li; 134 l->lv_u.mat.lv_last = li + count - 1; 135 for (i = 0; i < count; ++i) 136 { 137 if (i == 0) 138 li->li_prev = NULL; 139 else 140 li->li_prev = li - 1; 141 if (i == count - 1) 142 li->li_next = NULL; 143 else 144 li->li_next = li + 1; 145 ++li; 146 } 147 } 148 } 149 return l; 150 } 151 152 /* 153 * Set item "idx" for a list previously allocated with list_alloc_with_items(). 154 * The contents of "tv" is moved into the list item. 155 * Each item must be set exactly once. 156 */ 157 void 158 list_set_item(list_T *l, int idx, typval_T *tv) 159 { 160 listitem_T *li = (listitem_T *)(l + 1) + idx; 161 162 li->li_tv = *tv; 163 } 164 165 /* 166 * Allocate an empty list for a return value, with reference count set. 167 * Returns OK or FAIL. 168 */ 169 int 170 rettv_list_alloc(typval_T *rettv) 171 { 172 list_T *l = list_alloc(); 173 174 if (l == NULL) 175 return FAIL; 176 177 rettv->v_lock = 0; 178 rettv_list_set(rettv, l); 179 return OK; 180 } 181 182 /* 183 * Same as rettv_list_alloc() but uses an allocation id for testing. 184 */ 185 int 186 rettv_list_alloc_id(typval_T *rettv, alloc_id_T id UNUSED) 187 { 188 #ifdef FEAT_EVAL 189 if (alloc_fail_id == id && alloc_does_fail(sizeof(list_T))) 190 return FAIL; 191 #endif 192 return rettv_list_alloc(rettv); 193 } 194 195 196 /* 197 * Set a list as the return value. Increments the reference count. 198 */ 199 void 200 rettv_list_set(typval_T *rettv, list_T *l) 201 { 202 rettv->v_type = VAR_LIST; 203 rettv->vval.v_list = l; 204 if (l != NULL) 205 ++l->lv_refcount; 206 } 207 208 /* 209 * Unreference a list: decrement the reference count and free it when it 210 * becomes zero. 211 */ 212 void 213 list_unref(list_T *l) 214 { 215 if (l != NULL && --l->lv_refcount <= 0) 216 list_free(l); 217 } 218 219 /* 220 * Free a list, including all non-container items it points to. 221 * Ignores the reference count. 222 */ 223 static void 224 list_free_contents(list_T *l) 225 { 226 listitem_T *item; 227 228 if (l->lv_first != &range_list_item) 229 for (item = l->lv_first; item != NULL; item = l->lv_first) 230 { 231 // Remove the item before deleting it. 232 l->lv_first = item->li_next; 233 clear_tv(&item->li_tv); 234 list_free_item(l, item); 235 } 236 } 237 238 /* 239 * Go through the list of lists and free items without the copyID. 240 * But don't free a list that has a watcher (used in a for loop), these 241 * are not referenced anywhere. 242 */ 243 int 244 list_free_nonref(int copyID) 245 { 246 list_T *ll; 247 int did_free = FALSE; 248 249 for (ll = first_list; ll != NULL; ll = ll->lv_used_next) 250 if ((ll->lv_copyID & COPYID_MASK) != (copyID & COPYID_MASK) 251 && ll->lv_watch == NULL) 252 { 253 // Free the List and ordinary items it contains, but don't recurse 254 // into Lists and Dictionaries, they will be in the list of dicts 255 // or list of lists. 256 list_free_contents(ll); 257 did_free = TRUE; 258 } 259 return did_free; 260 } 261 262 static void 263 list_free_list(list_T *l) 264 { 265 // Remove the list from the list of lists for garbage collection. 266 if (l->lv_used_prev == NULL) 267 first_list = l->lv_used_next; 268 else 269 l->lv_used_prev->lv_used_next = l->lv_used_next; 270 if (l->lv_used_next != NULL) 271 l->lv_used_next->lv_used_prev = l->lv_used_prev; 272 273 vim_free(l); 274 } 275 276 void 277 list_free_items(int copyID) 278 { 279 list_T *ll, *ll_next; 280 281 for (ll = first_list; ll != NULL; ll = ll_next) 282 { 283 ll_next = ll->lv_used_next; 284 if ((ll->lv_copyID & COPYID_MASK) != (copyID & COPYID_MASK) 285 && ll->lv_watch == NULL) 286 { 287 // Free the List and ordinary items it contains, but don't recurse 288 // into Lists and Dictionaries, they will be in the list of dicts 289 // or list of lists. 290 list_free_list(ll); 291 } 292 } 293 } 294 295 void 296 list_free(list_T *l) 297 { 298 if (!in_free_unref_items) 299 { 300 list_free_contents(l); 301 list_free_list(l); 302 } 303 } 304 305 /* 306 * Allocate a list item. 307 * It is not initialized, don't forget to set v_lock. 308 */ 309 listitem_T * 310 listitem_alloc(void) 311 { 312 return ALLOC_ONE(listitem_T); 313 } 314 315 /* 316 * Free a list item, unless it was allocated together with the list itself. 317 * Does not clear the value. Does not notify watchers. 318 */ 319 static void 320 list_free_item(list_T *l, listitem_T *item) 321 { 322 if (l->lv_with_items == 0 || item < (listitem_T *)l 323 || item >= (listitem_T *)(l + 1) + l->lv_with_items) 324 vim_free(item); 325 } 326 327 /* 328 * Free a list item, unless it was allocated together with the list itself. 329 * Also clears the value. Does not notify watchers. 330 */ 331 void 332 listitem_free(list_T *l, listitem_T *item) 333 { 334 clear_tv(&item->li_tv); 335 list_free_item(l, item); 336 } 337 338 /* 339 * Remove a list item from a List and free it. Also clears the value. 340 */ 341 void 342 listitem_remove(list_T *l, listitem_T *item) 343 { 344 vimlist_remove(l, item, item); 345 listitem_free(l, item); 346 } 347 348 /* 349 * Get the number of items in a list. 350 */ 351 long 352 list_len(list_T *l) 353 { 354 if (l == NULL) 355 return 0L; 356 return l->lv_len; 357 } 358 359 /* 360 * Return TRUE when two lists have exactly the same values. 361 */ 362 int 363 list_equal( 364 list_T *l1, 365 list_T *l2, 366 int ic, // ignore case for strings 367 int recursive) // TRUE when used recursively 368 { 369 listitem_T *item1, *item2; 370 371 if (l1 == l2) 372 return TRUE; 373 if (list_len(l1) != list_len(l2)) 374 return FALSE; 375 if (list_len(l1) == 0) 376 // empty and NULL list are considered equal 377 return TRUE; 378 if (l1 == NULL || l2 == NULL) 379 return FALSE; 380 381 CHECK_LIST_MATERIALIZE(l1); 382 CHECK_LIST_MATERIALIZE(l2); 383 384 for (item1 = l1->lv_first, item2 = l2->lv_first; 385 item1 != NULL && item2 != NULL; 386 item1 = item1->li_next, item2 = item2->li_next) 387 if (!tv_equal(&item1->li_tv, &item2->li_tv, ic, recursive)) 388 return FALSE; 389 return item1 == NULL && item2 == NULL; 390 } 391 392 /* 393 * Locate item with index "n" in list "l" and return it. 394 * A negative index is counted from the end; -1 is the last item. 395 * Returns NULL when "n" is out of range. 396 */ 397 listitem_T * 398 list_find(list_T *l, long n) 399 { 400 listitem_T *item; 401 long idx; 402 403 if (l == NULL) 404 return NULL; 405 406 // Negative index is relative to the end. 407 if (n < 0) 408 n = l->lv_len + n; 409 410 // Check for index out of range. 411 if (n < 0 || n >= l->lv_len) 412 return NULL; 413 414 CHECK_LIST_MATERIALIZE(l); 415 416 // When there is a cached index may start search from there. 417 if (l->lv_u.mat.lv_idx_item != NULL) 418 { 419 if (n < l->lv_u.mat.lv_idx / 2) 420 { 421 // closest to the start of the list 422 item = l->lv_first; 423 idx = 0; 424 } 425 else if (n > (l->lv_u.mat.lv_idx + l->lv_len) / 2) 426 { 427 // closest to the end of the list 428 item = l->lv_u.mat.lv_last; 429 idx = l->lv_len - 1; 430 } 431 else 432 { 433 // closest to the cached index 434 item = l->lv_u.mat.lv_idx_item; 435 idx = l->lv_u.mat.lv_idx; 436 } 437 } 438 else 439 { 440 if (n < l->lv_len / 2) 441 { 442 // closest to the start of the list 443 item = l->lv_first; 444 idx = 0; 445 } 446 else 447 { 448 // closest to the end of the list 449 item = l->lv_u.mat.lv_last; 450 idx = l->lv_len - 1; 451 } 452 } 453 454 while (n > idx) 455 { 456 // search forward 457 item = item->li_next; 458 ++idx; 459 } 460 while (n < idx) 461 { 462 // search backward 463 item = item->li_prev; 464 --idx; 465 } 466 467 // cache the used index 468 l->lv_u.mat.lv_idx = idx; 469 l->lv_u.mat.lv_idx_item = item; 470 471 return item; 472 } 473 474 /* 475 * Get list item "l[idx]" as a number. 476 */ 477 long 478 list_find_nr( 479 list_T *l, 480 long idx, 481 int *errorp) // set to TRUE when something wrong 482 { 483 listitem_T *li; 484 485 if (l != NULL && l->lv_first == &range_list_item) 486 { 487 long n = idx; 488 489 // not materialized range() list: compute the value. 490 // Negative index is relative to the end. 491 if (n < 0) 492 n = l->lv_len + n; 493 494 // Check for index out of range. 495 if (n < 0 || n >= l->lv_len) 496 { 497 if (errorp != NULL) 498 *errorp = TRUE; 499 return -1L; 500 } 501 502 return l->lv_u.nonmat.lv_start + n * l->lv_u.nonmat.lv_stride; 503 } 504 505 li = list_find(l, idx); 506 if (li == NULL) 507 { 508 if (errorp != NULL) 509 *errorp = TRUE; 510 return -1L; 511 } 512 return (long)tv_get_number_chk(&li->li_tv, errorp); 513 } 514 515 /* 516 * Get list item "l[idx - 1]" as a string. Returns NULL for failure. 517 */ 518 char_u * 519 list_find_str(list_T *l, long idx) 520 { 521 listitem_T *li; 522 523 li = list_find(l, idx - 1); 524 if (li == NULL) 525 { 526 semsg(_(e_listidx), idx); 527 return NULL; 528 } 529 return tv_get_string(&li->li_tv); 530 } 531 532 /* 533 * Locate "item" list "l" and return its index. 534 * Returns -1 when "item" is not in the list. 535 */ 536 long 537 list_idx_of_item(list_T *l, listitem_T *item) 538 { 539 long idx = 0; 540 listitem_T *li; 541 542 if (l == NULL) 543 return -1; 544 CHECK_LIST_MATERIALIZE(l); 545 idx = 0; 546 for (li = l->lv_first; li != NULL && li != item; li = li->li_next) 547 ++idx; 548 if (li == NULL) 549 return -1; 550 return idx; 551 } 552 553 /* 554 * Append item "item" to the end of list "l". 555 */ 556 void 557 list_append(list_T *l, listitem_T *item) 558 { 559 CHECK_LIST_MATERIALIZE(l); 560 if (l->lv_u.mat.lv_last == NULL) 561 { 562 // empty list 563 l->lv_first = item; 564 l->lv_u.mat.lv_last = item; 565 item->li_prev = NULL; 566 } 567 else 568 { 569 l->lv_u.mat.lv_last->li_next = item; 570 item->li_prev = l->lv_u.mat.lv_last; 571 l->lv_u.mat.lv_last = item; 572 } 573 ++l->lv_len; 574 item->li_next = NULL; 575 } 576 577 /* 578 * Append typval_T "tv" to the end of list "l". "tv" is copied. 579 * Return FAIL when out of memory. 580 */ 581 int 582 list_append_tv(list_T *l, typval_T *tv) 583 { 584 listitem_T *li = listitem_alloc(); 585 586 if (li == NULL) 587 return FAIL; 588 copy_tv(tv, &li->li_tv); 589 list_append(l, li); 590 return OK; 591 } 592 593 /* 594 * As list_append_tv() but move the value instead of copying it. 595 * Return FAIL when out of memory. 596 */ 597 int 598 list_append_tv_move(list_T *l, typval_T *tv) 599 { 600 listitem_T *li = listitem_alloc(); 601 602 if (li == NULL) 603 return FAIL; 604 li->li_tv = *tv; 605 list_append(l, li); 606 return OK; 607 } 608 609 /* 610 * Add a dictionary to a list. Used by getqflist(). 611 * Return FAIL when out of memory. 612 */ 613 int 614 list_append_dict(list_T *list, dict_T *dict) 615 { 616 listitem_T *li = listitem_alloc(); 617 618 if (li == NULL) 619 return FAIL; 620 li->li_tv.v_type = VAR_DICT; 621 li->li_tv.v_lock = 0; 622 li->li_tv.vval.v_dict = dict; 623 list_append(list, li); 624 ++dict->dv_refcount; 625 return OK; 626 } 627 628 /* 629 * Append list2 to list1. 630 * Return FAIL when out of memory. 631 */ 632 int 633 list_append_list(list_T *list1, list_T *list2) 634 { 635 listitem_T *li = listitem_alloc(); 636 637 if (li == NULL) 638 return FAIL; 639 li->li_tv.v_type = VAR_LIST; 640 li->li_tv.v_lock = 0; 641 li->li_tv.vval.v_list = list2; 642 list_append(list1, li); 643 ++list2->lv_refcount; 644 return OK; 645 } 646 647 /* 648 * Make a copy of "str" and append it as an item to list "l". 649 * When "len" >= 0 use "str[len]". 650 * Returns FAIL when out of memory. 651 */ 652 int 653 list_append_string(list_T *l, char_u *str, int len) 654 { 655 listitem_T *li = listitem_alloc(); 656 657 if (li == NULL) 658 return FAIL; 659 list_append(l, li); 660 li->li_tv.v_type = VAR_STRING; 661 li->li_tv.v_lock = 0; 662 if (str == NULL) 663 li->li_tv.vval.v_string = NULL; 664 else if ((li->li_tv.vval.v_string = (len >= 0 ? vim_strnsave(str, len) 665 : vim_strsave(str))) == NULL) 666 return FAIL; 667 return OK; 668 } 669 670 /* 671 * Append "n" to list "l". 672 * Returns FAIL when out of memory. 673 */ 674 int 675 list_append_number(list_T *l, varnumber_T n) 676 { 677 listitem_T *li; 678 679 li = listitem_alloc(); 680 if (li == NULL) 681 return FAIL; 682 li->li_tv.v_type = VAR_NUMBER; 683 li->li_tv.v_lock = 0; 684 li->li_tv.vval.v_number = n; 685 list_append(l, li); 686 return OK; 687 } 688 689 /* 690 * Insert typval_T "tv" in list "l" before "item". 691 * If "item" is NULL append at the end. 692 * Return FAIL when out of memory. 693 */ 694 int 695 list_insert_tv(list_T *l, typval_T *tv, listitem_T *item) 696 { 697 listitem_T *ni = listitem_alloc(); 698 699 if (ni == NULL) 700 return FAIL; 701 copy_tv(tv, &ni->li_tv); 702 list_insert(l, ni, item); 703 return OK; 704 } 705 706 void 707 list_insert(list_T *l, listitem_T *ni, listitem_T *item) 708 { 709 CHECK_LIST_MATERIALIZE(l); 710 if (item == NULL) 711 // Append new item at end of list. 712 list_append(l, ni); 713 else 714 { 715 // Insert new item before existing item. 716 ni->li_prev = item->li_prev; 717 ni->li_next = item; 718 if (item->li_prev == NULL) 719 { 720 l->lv_first = ni; 721 ++l->lv_u.mat.lv_idx; 722 } 723 else 724 { 725 item->li_prev->li_next = ni; 726 l->lv_u.mat.lv_idx_item = NULL; 727 } 728 item->li_prev = ni; 729 ++l->lv_len; 730 } 731 } 732 733 /* 734 * Extend "l1" with "l2". 735 * If "bef" is NULL append at the end, otherwise insert before this item. 736 * Returns FAIL when out of memory. 737 */ 738 int 739 list_extend(list_T *l1, list_T *l2, listitem_T *bef) 740 { 741 listitem_T *item; 742 int todo = l2->lv_len; 743 744 CHECK_LIST_MATERIALIZE(l1); 745 CHECK_LIST_MATERIALIZE(l2); 746 747 // We also quit the loop when we have inserted the original item count of 748 // the list, avoid a hang when we extend a list with itself. 749 for (item = l2->lv_first; item != NULL && --todo >= 0; item = item->li_next) 750 if (list_insert_tv(l1, &item->li_tv, bef) == FAIL) 751 return FAIL; 752 return OK; 753 } 754 755 /* 756 * Concatenate lists "l1" and "l2" into a new list, stored in "tv". 757 * Return FAIL when out of memory. 758 */ 759 int 760 list_concat(list_T *l1, list_T *l2, typval_T *tv) 761 { 762 list_T *l; 763 764 if (l1 == NULL || l2 == NULL) 765 return FAIL; 766 767 // make a copy of the first list. 768 l = list_copy(l1, FALSE, 0); 769 if (l == NULL) 770 return FAIL; 771 tv->v_type = VAR_LIST; 772 tv->vval.v_list = l; 773 774 // append all items from the second list 775 return list_extend(l, l2, NULL); 776 } 777 778 /* 779 * Make a copy of list "orig". Shallow if "deep" is FALSE. 780 * The refcount of the new list is set to 1. 781 * See item_copy() for "copyID". 782 * Returns NULL when out of memory. 783 */ 784 list_T * 785 list_copy(list_T *orig, int deep, int copyID) 786 { 787 list_T *copy; 788 listitem_T *item; 789 listitem_T *ni; 790 791 if (orig == NULL) 792 return NULL; 793 794 copy = list_alloc(); 795 if (copy != NULL) 796 { 797 if (copyID != 0) 798 { 799 // Do this before adding the items, because one of the items may 800 // refer back to this list. 801 orig->lv_copyID = copyID; 802 orig->lv_copylist = copy; 803 } 804 CHECK_LIST_MATERIALIZE(orig); 805 for (item = orig->lv_first; item != NULL && !got_int; 806 item = item->li_next) 807 { 808 ni = listitem_alloc(); 809 if (ni == NULL) 810 break; 811 if (deep) 812 { 813 if (item_copy(&item->li_tv, &ni->li_tv, deep, copyID) == FAIL) 814 { 815 vim_free(ni); 816 break; 817 } 818 } 819 else 820 copy_tv(&item->li_tv, &ni->li_tv); 821 list_append(copy, ni); 822 } 823 ++copy->lv_refcount; 824 if (item != NULL) 825 { 826 list_unref(copy); 827 copy = NULL; 828 } 829 } 830 831 return copy; 832 } 833 834 /* 835 * Remove items "item" to "item2" from list "l". 836 * Does not free the listitem or the value! 837 * This used to be called list_remove, but that conflicts with a Sun header 838 * file. 839 */ 840 void 841 vimlist_remove(list_T *l, listitem_T *item, listitem_T *item2) 842 { 843 listitem_T *ip; 844 845 CHECK_LIST_MATERIALIZE(l); 846 847 // notify watchers 848 for (ip = item; ip != NULL; ip = ip->li_next) 849 { 850 --l->lv_len; 851 list_fix_watch(l, ip); 852 if (ip == item2) 853 break; 854 } 855 856 if (item2->li_next == NULL) 857 l->lv_u.mat.lv_last = item->li_prev; 858 else 859 item2->li_next->li_prev = item->li_prev; 860 if (item->li_prev == NULL) 861 l->lv_first = item2->li_next; 862 else 863 item->li_prev->li_next = item2->li_next; 864 l->lv_u.mat.lv_idx_item = NULL; 865 } 866 867 /* 868 * Return an allocated string with the string representation of a list. 869 * May return NULL. 870 */ 871 char_u * 872 list2string(typval_T *tv, int copyID, int restore_copyID) 873 { 874 garray_T ga; 875 876 if (tv->vval.v_list == NULL) 877 return NULL; 878 ga_init2(&ga, (int)sizeof(char), 80); 879 ga_append(&ga, '['); 880 CHECK_LIST_MATERIALIZE(tv->vval.v_list); 881 if (list_join(&ga, tv->vval.v_list, (char_u *)", ", 882 FALSE, restore_copyID, copyID) == FAIL) 883 { 884 vim_free(ga.ga_data); 885 return NULL; 886 } 887 ga_append(&ga, ']'); 888 ga_append(&ga, NUL); 889 return (char_u *)ga.ga_data; 890 } 891 892 typedef struct join_S { 893 char_u *s; 894 char_u *tofree; 895 } join_T; 896 897 static int 898 list_join_inner( 899 garray_T *gap, // to store the result in 900 list_T *l, 901 char_u *sep, 902 int echo_style, 903 int restore_copyID, 904 int copyID, 905 garray_T *join_gap) // to keep each list item string 906 { 907 int i; 908 join_T *p; 909 int len; 910 int sumlen = 0; 911 int first = TRUE; 912 char_u *tofree; 913 char_u numbuf[NUMBUFLEN]; 914 listitem_T *item; 915 char_u *s; 916 917 // Stringify each item in the list. 918 CHECK_LIST_MATERIALIZE(l); 919 for (item = l->lv_first; item != NULL && !got_int; item = item->li_next) 920 { 921 s = echo_string_core(&item->li_tv, &tofree, numbuf, copyID, 922 echo_style, restore_copyID, !echo_style); 923 if (s == NULL) 924 return FAIL; 925 926 len = (int)STRLEN(s); 927 sumlen += len; 928 929 (void)ga_grow(join_gap, 1); 930 p = ((join_T *)join_gap->ga_data) + (join_gap->ga_len++); 931 if (tofree != NULL || s != numbuf) 932 { 933 p->s = s; 934 p->tofree = tofree; 935 } 936 else 937 { 938 p->s = vim_strnsave(s, len); 939 p->tofree = p->s; 940 } 941 942 line_breakcheck(); 943 if (did_echo_string_emsg) // recursion error, bail out 944 break; 945 } 946 947 // Allocate result buffer with its total size, avoid re-allocation and 948 // multiple copy operations. Add 2 for a tailing ']' and NUL. 949 if (join_gap->ga_len >= 2) 950 sumlen += (int)STRLEN(sep) * (join_gap->ga_len - 1); 951 if (ga_grow(gap, sumlen + 2) == FAIL) 952 return FAIL; 953 954 for (i = 0; i < join_gap->ga_len && !got_int; ++i) 955 { 956 if (first) 957 first = FALSE; 958 else 959 ga_concat(gap, sep); 960 p = ((join_T *)join_gap->ga_data) + i; 961 962 if (p->s != NULL) 963 ga_concat(gap, p->s); 964 line_breakcheck(); 965 } 966 967 return OK; 968 } 969 970 /* 971 * Join list "l" into a string in "*gap", using separator "sep". 972 * When "echo_style" is TRUE use String as echoed, otherwise as inside a List. 973 * Return FAIL or OK. 974 */ 975 int 976 list_join( 977 garray_T *gap, 978 list_T *l, 979 char_u *sep, 980 int echo_style, 981 int restore_copyID, 982 int copyID) 983 { 984 garray_T join_ga; 985 int retval; 986 join_T *p; 987 int i; 988 989 if (l->lv_len < 1) 990 return OK; // nothing to do 991 ga_init2(&join_ga, (int)sizeof(join_T), l->lv_len); 992 retval = list_join_inner(gap, l, sep, echo_style, restore_copyID, 993 copyID, &join_ga); 994 995 // Dispose each item in join_ga. 996 if (join_ga.ga_data != NULL) 997 { 998 p = (join_T *)join_ga.ga_data; 999 for (i = 0; i < join_ga.ga_len; ++i) 1000 { 1001 vim_free(p->tofree); 1002 ++p; 1003 } 1004 ga_clear(&join_ga); 1005 } 1006 1007 return retval; 1008 } 1009 1010 /* 1011 * "join()" function 1012 */ 1013 void 1014 f_join(typval_T *argvars, typval_T *rettv) 1015 { 1016 garray_T ga; 1017 char_u *sep; 1018 1019 if (argvars[0].v_type != VAR_LIST) 1020 { 1021 emsg(_(e_listreq)); 1022 return; 1023 } 1024 if (argvars[0].vval.v_list == NULL) 1025 return; 1026 if (argvars[1].v_type == VAR_UNKNOWN) 1027 sep = (char_u *)" "; 1028 else 1029 sep = tv_get_string_chk(&argvars[1]); 1030 1031 rettv->v_type = VAR_STRING; 1032 1033 if (sep != NULL) 1034 { 1035 ga_init2(&ga, (int)sizeof(char), 80); 1036 list_join(&ga, argvars[0].vval.v_list, sep, TRUE, FALSE, 0); 1037 ga_append(&ga, NUL); 1038 rettv->vval.v_string = (char_u *)ga.ga_data; 1039 } 1040 else 1041 rettv->vval.v_string = NULL; 1042 } 1043 1044 /* 1045 * Allocate a variable for a List and fill it from "*arg". 1046 * Return OK or FAIL. 1047 */ 1048 int 1049 get_list_tv(char_u **arg, typval_T *rettv, int flags, int do_error) 1050 { 1051 int evaluate = flags & EVAL_EVALUATE; 1052 list_T *l = NULL; 1053 typval_T tv; 1054 listitem_T *item; 1055 1056 if (evaluate) 1057 { 1058 l = list_alloc(); 1059 if (l == NULL) 1060 return FAIL; 1061 } 1062 1063 *arg = skipwhite(*arg + 1); 1064 while (**arg != ']' && **arg != NUL) 1065 { 1066 if (eval1(arg, &tv, flags) == FAIL) // recursive! 1067 goto failret; 1068 if (evaluate) 1069 { 1070 item = listitem_alloc(); 1071 if (item != NULL) 1072 { 1073 item->li_tv = tv; 1074 item->li_tv.v_lock = 0; 1075 list_append(l, item); 1076 } 1077 else 1078 clear_tv(&tv); 1079 } 1080 1081 if (**arg == ']') 1082 break; 1083 if (**arg != ',') 1084 { 1085 if (do_error) 1086 semsg(_("E696: Missing comma in List: %s"), *arg); 1087 goto failret; 1088 } 1089 *arg = skipwhite(*arg + 1); 1090 } 1091 1092 if (**arg != ']') 1093 { 1094 if (do_error) 1095 semsg(_(e_list_end), *arg); 1096 failret: 1097 if (evaluate) 1098 list_free(l); 1099 return FAIL; 1100 } 1101 1102 *arg = skipwhite(*arg + 1); 1103 if (evaluate) 1104 rettv_list_set(rettv, l); 1105 1106 return OK; 1107 } 1108 1109 /* 1110 * Write "list" of strings to file "fd". 1111 */ 1112 int 1113 write_list(FILE *fd, list_T *list, int binary) 1114 { 1115 listitem_T *li; 1116 int c; 1117 int ret = OK; 1118 char_u *s; 1119 1120 CHECK_LIST_MATERIALIZE(list); 1121 FOR_ALL_LIST_ITEMS(list, li) 1122 { 1123 for (s = tv_get_string(&li->li_tv); *s != NUL; ++s) 1124 { 1125 if (*s == '\n') 1126 c = putc(NUL, fd); 1127 else 1128 c = putc(*s, fd); 1129 if (c == EOF) 1130 { 1131 ret = FAIL; 1132 break; 1133 } 1134 } 1135 if (!binary || li->li_next != NULL) 1136 if (putc('\n', fd) == EOF) 1137 { 1138 ret = FAIL; 1139 break; 1140 } 1141 if (ret == FAIL) 1142 { 1143 emsg(_(e_write)); 1144 break; 1145 } 1146 } 1147 return ret; 1148 } 1149 1150 /* 1151 * Initialize a static list with 10 items. 1152 */ 1153 void 1154 init_static_list(staticList10_T *sl) 1155 { 1156 list_T *l = &sl->sl_list; 1157 int i; 1158 1159 memset(sl, 0, sizeof(staticList10_T)); 1160 l->lv_first = &sl->sl_items[0]; 1161 l->lv_u.mat.lv_last = &sl->sl_items[9]; 1162 l->lv_refcount = DO_NOT_FREE_CNT; 1163 l->lv_lock = VAR_FIXED; 1164 sl->sl_list.lv_len = 10; 1165 1166 for (i = 0; i < 10; ++i) 1167 { 1168 listitem_T *li = &sl->sl_items[i]; 1169 1170 if (i == 0) 1171 li->li_prev = NULL; 1172 else 1173 li->li_prev = li - 1; 1174 if (i == 9) 1175 li->li_next = NULL; 1176 else 1177 li->li_next = li + 1; 1178 } 1179 } 1180 1181 /* 1182 * "list2str()" function 1183 */ 1184 void 1185 f_list2str(typval_T *argvars, typval_T *rettv) 1186 { 1187 list_T *l; 1188 listitem_T *li; 1189 garray_T ga; 1190 int utf8 = FALSE; 1191 1192 rettv->v_type = VAR_STRING; 1193 rettv->vval.v_string = NULL; 1194 if (argvars[0].v_type != VAR_LIST) 1195 { 1196 emsg(_(e_invarg)); 1197 return; 1198 } 1199 1200 l = argvars[0].vval.v_list; 1201 if (l == NULL) 1202 return; // empty list results in empty string 1203 1204 if (argvars[1].v_type != VAR_UNKNOWN) 1205 utf8 = (int)tv_get_number_chk(&argvars[1], NULL); 1206 1207 CHECK_LIST_MATERIALIZE(l); 1208 ga_init2(&ga, 1, 80); 1209 if (has_mbyte || utf8) 1210 { 1211 char_u buf[MB_MAXBYTES + 1]; 1212 int (*char2bytes)(int, char_u *); 1213 1214 if (utf8 || enc_utf8) 1215 char2bytes = utf_char2bytes; 1216 else 1217 char2bytes = mb_char2bytes; 1218 1219 FOR_ALL_LIST_ITEMS(l, li) 1220 { 1221 buf[(*char2bytes)(tv_get_number(&li->li_tv), buf)] = NUL; 1222 ga_concat(&ga, buf); 1223 } 1224 ga_append(&ga, NUL); 1225 } 1226 else if (ga_grow(&ga, list_len(l) + 1) == OK) 1227 { 1228 FOR_ALL_LIST_ITEMS(l, li) 1229 ga_append(&ga, tv_get_number(&li->li_tv)); 1230 ga_append(&ga, NUL); 1231 } 1232 1233 rettv->v_type = VAR_STRING; 1234 rettv->vval.v_string = ga.ga_data; 1235 } 1236 1237 static void 1238 list_remove(typval_T *argvars, typval_T *rettv, char_u *arg_errmsg) 1239 { 1240 list_T *l; 1241 listitem_T *item, *item2; 1242 listitem_T *li; 1243 int error = FALSE; 1244 int idx; 1245 1246 if ((l = argvars[0].vval.v_list) == NULL 1247 || var_check_lock(l->lv_lock, arg_errmsg, TRUE)) 1248 return; 1249 1250 idx = (long)tv_get_number_chk(&argvars[1], &error); 1251 if (error) 1252 ; // type error: do nothing, errmsg already given 1253 else if ((item = list_find(l, idx)) == NULL) 1254 semsg(_(e_listidx), idx); 1255 else 1256 { 1257 if (argvars[2].v_type == VAR_UNKNOWN) 1258 { 1259 // Remove one item, return its value. 1260 vimlist_remove(l, item, item); 1261 *rettv = item->li_tv; 1262 list_free_item(l, item); 1263 } 1264 else 1265 { 1266 // Remove range of items, return list with values. 1267 int end = (long)tv_get_number_chk(&argvars[2], &error); 1268 1269 if (error) 1270 ; // type error: do nothing 1271 else if ((item2 = list_find(l, end)) == NULL) 1272 semsg(_(e_listidx), end); 1273 else 1274 { 1275 int cnt = 0; 1276 1277 for (li = item; li != NULL; li = li->li_next) 1278 { 1279 ++cnt; 1280 if (li == item2) 1281 break; 1282 } 1283 if (li == NULL) // didn't find "item2" after "item" 1284 emsg(_(e_invrange)); 1285 else 1286 { 1287 vimlist_remove(l, item, item2); 1288 if (rettv_list_alloc(rettv) == OK) 1289 { 1290 l = rettv->vval.v_list; 1291 l->lv_first = item; 1292 l->lv_u.mat.lv_last = item2; 1293 item->li_prev = NULL; 1294 item2->li_next = NULL; 1295 l->lv_len = cnt; 1296 } 1297 } 1298 } 1299 } 1300 } 1301 } 1302 1303 static int item_compare(const void *s1, const void *s2); 1304 static int item_compare2(const void *s1, const void *s2); 1305 1306 // struct used in the array that's given to qsort() 1307 typedef struct 1308 { 1309 listitem_T *item; 1310 int idx; 1311 } sortItem_T; 1312 1313 // struct storing information about current sort 1314 typedef struct 1315 { 1316 int item_compare_ic; 1317 int item_compare_numeric; 1318 int item_compare_numbers; 1319 #ifdef FEAT_FLOAT 1320 int item_compare_float; 1321 #endif 1322 char_u *item_compare_func; 1323 partial_T *item_compare_partial; 1324 dict_T *item_compare_selfdict; 1325 int item_compare_func_err; 1326 int item_compare_keep_zero; 1327 } sortinfo_T; 1328 static sortinfo_T *sortinfo = NULL; 1329 #define ITEM_COMPARE_FAIL 999 1330 1331 /* 1332 * Compare functions for f_sort() and f_uniq() below. 1333 */ 1334 static int 1335 item_compare(const void *s1, const void *s2) 1336 { 1337 sortItem_T *si1, *si2; 1338 typval_T *tv1, *tv2; 1339 char_u *p1, *p2; 1340 char_u *tofree1 = NULL, *tofree2 = NULL; 1341 int res; 1342 char_u numbuf1[NUMBUFLEN]; 1343 char_u numbuf2[NUMBUFLEN]; 1344 1345 si1 = (sortItem_T *)s1; 1346 si2 = (sortItem_T *)s2; 1347 tv1 = &si1->item->li_tv; 1348 tv2 = &si2->item->li_tv; 1349 1350 if (sortinfo->item_compare_numbers) 1351 { 1352 varnumber_T v1 = tv_get_number(tv1); 1353 varnumber_T v2 = tv_get_number(tv2); 1354 1355 return v1 == v2 ? 0 : v1 > v2 ? 1 : -1; 1356 } 1357 1358 #ifdef FEAT_FLOAT 1359 if (sortinfo->item_compare_float) 1360 { 1361 float_T v1 = tv_get_float(tv1); 1362 float_T v2 = tv_get_float(tv2); 1363 1364 return v1 == v2 ? 0 : v1 > v2 ? 1 : -1; 1365 } 1366 #endif 1367 1368 // tv2string() puts quotes around a string and allocates memory. Don't do 1369 // that for string variables. Use a single quote when comparing with a 1370 // non-string to do what the docs promise. 1371 if (tv1->v_type == VAR_STRING) 1372 { 1373 if (tv2->v_type != VAR_STRING || sortinfo->item_compare_numeric) 1374 p1 = (char_u *)"'"; 1375 else 1376 p1 = tv1->vval.v_string; 1377 } 1378 else 1379 p1 = tv2string(tv1, &tofree1, numbuf1, 0); 1380 if (tv2->v_type == VAR_STRING) 1381 { 1382 if (tv1->v_type != VAR_STRING || sortinfo->item_compare_numeric) 1383 p2 = (char_u *)"'"; 1384 else 1385 p2 = tv2->vval.v_string; 1386 } 1387 else 1388 p2 = tv2string(tv2, &tofree2, numbuf2, 0); 1389 if (p1 == NULL) 1390 p1 = (char_u *)""; 1391 if (p2 == NULL) 1392 p2 = (char_u *)""; 1393 if (!sortinfo->item_compare_numeric) 1394 { 1395 if (sortinfo->item_compare_ic) 1396 res = STRICMP(p1, p2); 1397 else 1398 res = STRCMP(p1, p2); 1399 } 1400 else 1401 { 1402 double n1, n2; 1403 n1 = strtod((char *)p1, (char **)&p1); 1404 n2 = strtod((char *)p2, (char **)&p2); 1405 res = n1 == n2 ? 0 : n1 > n2 ? 1 : -1; 1406 } 1407 1408 // When the result would be zero, compare the item indexes. Makes the 1409 // sort stable. 1410 if (res == 0 && !sortinfo->item_compare_keep_zero) 1411 res = si1->idx > si2->idx ? 1 : -1; 1412 1413 vim_free(tofree1); 1414 vim_free(tofree2); 1415 return res; 1416 } 1417 1418 static int 1419 item_compare2(const void *s1, const void *s2) 1420 { 1421 sortItem_T *si1, *si2; 1422 int res; 1423 typval_T rettv; 1424 typval_T argv[3]; 1425 char_u *func_name; 1426 partial_T *partial = sortinfo->item_compare_partial; 1427 funcexe_T funcexe; 1428 1429 // shortcut after failure in previous call; compare all items equal 1430 if (sortinfo->item_compare_func_err) 1431 return 0; 1432 1433 si1 = (sortItem_T *)s1; 1434 si2 = (sortItem_T *)s2; 1435 1436 if (partial == NULL) 1437 func_name = sortinfo->item_compare_func; 1438 else 1439 func_name = partial_name(partial); 1440 1441 // Copy the values. This is needed to be able to set v_lock to VAR_FIXED 1442 // in the copy without changing the original list items. 1443 copy_tv(&si1->item->li_tv, &argv[0]); 1444 copy_tv(&si2->item->li_tv, &argv[1]); 1445 1446 rettv.v_type = VAR_UNKNOWN; // clear_tv() uses this 1447 CLEAR_FIELD(funcexe); 1448 funcexe.evaluate = TRUE; 1449 funcexe.partial = partial; 1450 funcexe.selfdict = sortinfo->item_compare_selfdict; 1451 res = call_func(func_name, -1, &rettv, 2, argv, &funcexe); 1452 clear_tv(&argv[0]); 1453 clear_tv(&argv[1]); 1454 1455 if (res == FAIL) 1456 res = ITEM_COMPARE_FAIL; 1457 else 1458 res = (int)tv_get_number_chk(&rettv, &sortinfo->item_compare_func_err); 1459 if (sortinfo->item_compare_func_err) 1460 res = ITEM_COMPARE_FAIL; // return value has wrong type 1461 clear_tv(&rettv); 1462 1463 // When the result would be zero, compare the pointers themselves. Makes 1464 // the sort stable. 1465 if (res == 0 && !sortinfo->item_compare_keep_zero) 1466 res = si1->idx > si2->idx ? 1 : -1; 1467 1468 return res; 1469 } 1470 1471 /* 1472 * "sort()" or "uniq()" function 1473 */ 1474 static void 1475 do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) 1476 { 1477 list_T *l; 1478 listitem_T *li; 1479 sortItem_T *ptrs; 1480 sortinfo_T *old_sortinfo; 1481 sortinfo_T info; 1482 long len; 1483 long i; 1484 1485 // Pointer to current info struct used in compare function. Save and 1486 // restore the current one for nested calls. 1487 old_sortinfo = sortinfo; 1488 sortinfo = &info; 1489 1490 if (argvars[0].v_type != VAR_LIST) 1491 semsg(_(e_listarg), sort ? "sort()" : "uniq()"); 1492 else 1493 { 1494 l = argvars[0].vval.v_list; 1495 if (l == NULL || var_check_lock(l->lv_lock, 1496 (char_u *)(sort ? N_("sort() argument") : N_("uniq() argument")), 1497 TRUE)) 1498 goto theend; 1499 rettv_list_set(rettv, l); 1500 CHECK_LIST_MATERIALIZE(l); 1501 1502 len = list_len(l); 1503 if (len <= 1) 1504 goto theend; // short list sorts pretty quickly 1505 1506 info.item_compare_ic = FALSE; 1507 info.item_compare_numeric = FALSE; 1508 info.item_compare_numbers = FALSE; 1509 #ifdef FEAT_FLOAT 1510 info.item_compare_float = FALSE; 1511 #endif 1512 info.item_compare_func = NULL; 1513 info.item_compare_partial = NULL; 1514 info.item_compare_selfdict = NULL; 1515 if (argvars[1].v_type != VAR_UNKNOWN) 1516 { 1517 // optional second argument: {func} 1518 if (argvars[1].v_type == VAR_FUNC) 1519 info.item_compare_func = argvars[1].vval.v_string; 1520 else if (argvars[1].v_type == VAR_PARTIAL) 1521 info.item_compare_partial = argvars[1].vval.v_partial; 1522 else 1523 { 1524 int error = FALSE; 1525 1526 i = (long)tv_get_number_chk(&argvars[1], &error); 1527 if (error) 1528 goto theend; // type error; errmsg already given 1529 if (i == 1) 1530 info.item_compare_ic = TRUE; 1531 else if (argvars[1].v_type != VAR_NUMBER) 1532 info.item_compare_func = tv_get_string(&argvars[1]); 1533 else if (i != 0) 1534 { 1535 emsg(_(e_invarg)); 1536 goto theend; 1537 } 1538 if (info.item_compare_func != NULL) 1539 { 1540 if (*info.item_compare_func == NUL) 1541 { 1542 // empty string means default sort 1543 info.item_compare_func = NULL; 1544 } 1545 else if (STRCMP(info.item_compare_func, "n") == 0) 1546 { 1547 info.item_compare_func = NULL; 1548 info.item_compare_numeric = TRUE; 1549 } 1550 else if (STRCMP(info.item_compare_func, "N") == 0) 1551 { 1552 info.item_compare_func = NULL; 1553 info.item_compare_numbers = TRUE; 1554 } 1555 #ifdef FEAT_FLOAT 1556 else if (STRCMP(info.item_compare_func, "f") == 0) 1557 { 1558 info.item_compare_func = NULL; 1559 info.item_compare_float = TRUE; 1560 } 1561 #endif 1562 else if (STRCMP(info.item_compare_func, "i") == 0) 1563 { 1564 info.item_compare_func = NULL; 1565 info.item_compare_ic = TRUE; 1566 } 1567 } 1568 } 1569 1570 if (argvars[2].v_type != VAR_UNKNOWN) 1571 { 1572 // optional third argument: {dict} 1573 if (argvars[2].v_type != VAR_DICT) 1574 { 1575 emsg(_(e_dictreq)); 1576 goto theend; 1577 } 1578 info.item_compare_selfdict = argvars[2].vval.v_dict; 1579 } 1580 } 1581 1582 // Make an array with each entry pointing to an item in the List. 1583 ptrs = ALLOC_MULT(sortItem_T, len); 1584 if (ptrs == NULL) 1585 goto theend; 1586 1587 i = 0; 1588 if (sort) 1589 { 1590 // sort(): ptrs will be the list to sort 1591 FOR_ALL_LIST_ITEMS(l, li) 1592 { 1593 ptrs[i].item = li; 1594 ptrs[i].idx = i; 1595 ++i; 1596 } 1597 1598 info.item_compare_func_err = FALSE; 1599 info.item_compare_keep_zero = FALSE; 1600 // test the compare function 1601 if ((info.item_compare_func != NULL 1602 || info.item_compare_partial != NULL) 1603 && item_compare2((void *)&ptrs[0], (void *)&ptrs[1]) 1604 == ITEM_COMPARE_FAIL) 1605 emsg(_("E702: Sort compare function failed")); 1606 else 1607 { 1608 // Sort the array with item pointers. 1609 qsort((void *)ptrs, (size_t)len, sizeof(sortItem_T), 1610 info.item_compare_func == NULL 1611 && info.item_compare_partial == NULL 1612 ? item_compare : item_compare2); 1613 1614 if (!info.item_compare_func_err) 1615 { 1616 // Clear the List and append the items in sorted order. 1617 l->lv_first = l->lv_u.mat.lv_last 1618 = l->lv_u.mat.lv_idx_item = NULL; 1619 l->lv_len = 0; 1620 for (i = 0; i < len; ++i) 1621 list_append(l, ptrs[i].item); 1622 } 1623 } 1624 } 1625 else 1626 { 1627 int (*item_compare_func_ptr)(const void *, const void *); 1628 1629 // f_uniq(): ptrs will be a stack of items to remove 1630 info.item_compare_func_err = FALSE; 1631 info.item_compare_keep_zero = TRUE; 1632 item_compare_func_ptr = info.item_compare_func != NULL 1633 || info.item_compare_partial != NULL 1634 ? item_compare2 : item_compare; 1635 1636 for (li = l->lv_first; li != NULL && li->li_next != NULL; 1637 li = li->li_next) 1638 { 1639 if (item_compare_func_ptr((void *)&li, (void *)&li->li_next) 1640 == 0) 1641 ptrs[i++].item = li; 1642 if (info.item_compare_func_err) 1643 { 1644 emsg(_("E882: Uniq compare function failed")); 1645 break; 1646 } 1647 } 1648 1649 if (!info.item_compare_func_err) 1650 { 1651 while (--i >= 0) 1652 { 1653 li = ptrs[i].item->li_next; 1654 ptrs[i].item->li_next = li->li_next; 1655 if (li->li_next != NULL) 1656 li->li_next->li_prev = ptrs[i].item; 1657 else 1658 l->lv_u.mat.lv_last = ptrs[i].item; 1659 list_fix_watch(l, li); 1660 listitem_free(l, li); 1661 l->lv_len--; 1662 } 1663 } 1664 } 1665 1666 vim_free(ptrs); 1667 } 1668 theend: 1669 sortinfo = old_sortinfo; 1670 } 1671 1672 /* 1673 * "sort({list})" function 1674 */ 1675 void 1676 f_sort(typval_T *argvars, typval_T *rettv) 1677 { 1678 do_sort_uniq(argvars, rettv, TRUE); 1679 } 1680 1681 /* 1682 * "uniq({list})" function 1683 */ 1684 void 1685 f_uniq(typval_T *argvars, typval_T *rettv) 1686 { 1687 do_sort_uniq(argvars, rettv, FALSE); 1688 } 1689 1690 /* 1691 * Handle one item for map() and filter(). 1692 */ 1693 static int 1694 filter_map_one(typval_T *tv, typval_T *expr, int map, int *remp) 1695 { 1696 typval_T rettv; 1697 typval_T argv[3]; 1698 int retval = FAIL; 1699 1700 copy_tv(tv, get_vim_var_tv(VV_VAL)); 1701 argv[0] = *get_vim_var_tv(VV_KEY); 1702 argv[1] = *get_vim_var_tv(VV_VAL); 1703 if (eval_expr_typval(expr, argv, 2, &rettv) == FAIL) 1704 goto theend; 1705 if (map) 1706 { 1707 // map(): replace the list item value 1708 clear_tv(tv); 1709 rettv.v_lock = 0; 1710 *tv = rettv; 1711 } 1712 else 1713 { 1714 int error = FALSE; 1715 1716 // filter(): when expr is zero remove the item 1717 *remp = (tv_get_number_chk(&rettv, &error) == 0); 1718 clear_tv(&rettv); 1719 // On type error, nothing has been removed; return FAIL to stop the 1720 // loop. The error message was given by tv_get_number_chk(). 1721 if (error) 1722 goto theend; 1723 } 1724 retval = OK; 1725 theend: 1726 clear_tv(get_vim_var_tv(VV_VAL)); 1727 return retval; 1728 } 1729 1730 /* 1731 * Implementation of map() and filter(). 1732 */ 1733 static void 1734 filter_map(typval_T *argvars, typval_T *rettv, int map) 1735 { 1736 typval_T *expr; 1737 listitem_T *li, *nli; 1738 list_T *l = NULL; 1739 dictitem_T *di; 1740 hashtab_T *ht; 1741 hashitem_T *hi; 1742 dict_T *d = NULL; 1743 blob_T *b = NULL; 1744 int rem; 1745 int todo; 1746 char_u *ermsg = (char_u *)(map ? "map()" : "filter()"); 1747 char_u *arg_errmsg = (char_u *)(map ? N_("map() argument") 1748 : N_("filter() argument")); 1749 int save_did_emsg; 1750 int idx = 0; 1751 1752 if (argvars[0].v_type == VAR_BLOB) 1753 { 1754 if ((b = argvars[0].vval.v_blob) == NULL) 1755 return; 1756 } 1757 else if (argvars[0].v_type == VAR_LIST) 1758 { 1759 if ((l = argvars[0].vval.v_list) == NULL 1760 || (!map && var_check_lock(l->lv_lock, arg_errmsg, TRUE))) 1761 return; 1762 } 1763 else if (argvars[0].v_type == VAR_DICT) 1764 { 1765 if ((d = argvars[0].vval.v_dict) == NULL 1766 || (!map && var_check_lock(d->dv_lock, arg_errmsg, TRUE))) 1767 return; 1768 } 1769 else 1770 { 1771 semsg(_(e_listdictarg), ermsg); 1772 return; 1773 } 1774 1775 expr = &argvars[1]; 1776 // On type errors, the preceding call has already displayed an error 1777 // message. Avoid a misleading error message for an empty string that 1778 // was not passed as argument. 1779 if (expr->v_type != VAR_UNKNOWN) 1780 { 1781 typval_T save_val; 1782 typval_T save_key; 1783 1784 prepare_vimvar(VV_VAL, &save_val); 1785 prepare_vimvar(VV_KEY, &save_key); 1786 1787 // We reset "did_emsg" to be able to detect whether an error 1788 // occurred during evaluation of the expression. 1789 save_did_emsg = did_emsg; 1790 did_emsg = FALSE; 1791 1792 if (argvars[0].v_type == VAR_DICT) 1793 { 1794 int prev_lock = d->dv_lock; 1795 1796 if (map && d->dv_lock == 0) 1797 d->dv_lock = VAR_LOCKED; 1798 ht = &d->dv_hashtab; 1799 hash_lock(ht); 1800 todo = (int)ht->ht_used; 1801 for (hi = ht->ht_array; todo > 0; ++hi) 1802 { 1803 if (!HASHITEM_EMPTY(hi)) 1804 { 1805 int r; 1806 1807 --todo; 1808 di = HI2DI(hi); 1809 if (map && (var_check_lock(di->di_tv.v_lock, 1810 arg_errmsg, TRUE) 1811 || var_check_ro(di->di_flags, 1812 arg_errmsg, TRUE))) 1813 break; 1814 set_vim_var_string(VV_KEY, di->di_key, -1); 1815 r = filter_map_one(&di->di_tv, expr, map, &rem); 1816 clear_tv(get_vim_var_tv(VV_KEY)); 1817 if (r == FAIL || did_emsg) 1818 break; 1819 if (!map && rem) 1820 { 1821 if (var_check_fixed(di->di_flags, arg_errmsg, TRUE) 1822 || var_check_ro(di->di_flags, arg_errmsg, TRUE)) 1823 break; 1824 dictitem_remove(d, di); 1825 } 1826 } 1827 } 1828 hash_unlock(ht); 1829 d->dv_lock = prev_lock; 1830 } 1831 else if (argvars[0].v_type == VAR_BLOB) 1832 { 1833 int i; 1834 typval_T tv; 1835 varnumber_T val; 1836 1837 // set_vim_var_nr() doesn't set the type 1838 set_vim_var_type(VV_KEY, VAR_NUMBER); 1839 1840 for (i = 0; i < b->bv_ga.ga_len; i++) 1841 { 1842 tv.v_type = VAR_NUMBER; 1843 val = blob_get(b, i); 1844 tv.vval.v_number = val; 1845 set_vim_var_nr(VV_KEY, idx); 1846 if (filter_map_one(&tv, expr, map, &rem) == FAIL || did_emsg) 1847 break; 1848 if (tv.v_type != VAR_NUMBER) 1849 { 1850 emsg(_(e_invalblob)); 1851 break; 1852 } 1853 if (map) 1854 { 1855 if (tv.vval.v_number != val) 1856 blob_set(b, i, tv.vval.v_number); 1857 } 1858 else if (rem) 1859 { 1860 char_u *p = (char_u *)argvars[0].vval.v_blob->bv_ga.ga_data; 1861 1862 mch_memmove(p + i, p + i + 1, 1863 (size_t)b->bv_ga.ga_len - i - 1); 1864 --b->bv_ga.ga_len; 1865 --i; 1866 } 1867 ++idx; 1868 } 1869 } 1870 else // argvars[0].v_type == VAR_LIST 1871 { 1872 int prev_lock = l->lv_lock; 1873 1874 // set_vim_var_nr() doesn't set the type 1875 set_vim_var_type(VV_KEY, VAR_NUMBER); 1876 1877 CHECK_LIST_MATERIALIZE(l); 1878 if (map && l->lv_lock == 0) 1879 l->lv_lock = VAR_LOCKED; 1880 for (li = l->lv_first; li != NULL; li = nli) 1881 { 1882 if (map && var_check_lock(li->li_tv.v_lock, arg_errmsg, TRUE)) 1883 break; 1884 nli = li->li_next; 1885 set_vim_var_nr(VV_KEY, idx); 1886 if (filter_map_one(&li->li_tv, expr, map, &rem) == FAIL 1887 || did_emsg) 1888 break; 1889 if (!map && rem) 1890 listitem_remove(l, li); 1891 ++idx; 1892 } 1893 l->lv_lock = prev_lock; 1894 } 1895 1896 restore_vimvar(VV_KEY, &save_key); 1897 restore_vimvar(VV_VAL, &save_val); 1898 1899 did_emsg |= save_did_emsg; 1900 } 1901 1902 copy_tv(&argvars[0], rettv); 1903 } 1904 1905 /* 1906 * "filter()" function 1907 */ 1908 void 1909 f_filter(typval_T *argvars, typval_T *rettv) 1910 { 1911 filter_map(argvars, rettv, FALSE); 1912 } 1913 1914 /* 1915 * "map()" function 1916 */ 1917 void 1918 f_map(typval_T *argvars, typval_T *rettv) 1919 { 1920 filter_map(argvars, rettv, TRUE); 1921 } 1922 1923 /* 1924 * "add(list, item)" function 1925 */ 1926 void 1927 f_add(typval_T *argvars, typval_T *rettv) 1928 { 1929 list_T *l; 1930 blob_T *b; 1931 1932 rettv->vval.v_number = 1; // Default: Failed 1933 if (argvars[0].v_type == VAR_LIST) 1934 { 1935 if ((l = argvars[0].vval.v_list) != NULL 1936 && !var_check_lock(l->lv_lock, 1937 (char_u *)N_("add() argument"), TRUE) 1938 && list_append_tv(l, &argvars[1]) == OK) 1939 copy_tv(&argvars[0], rettv); 1940 } 1941 else if (argvars[0].v_type == VAR_BLOB) 1942 { 1943 if ((b = argvars[0].vval.v_blob) != NULL 1944 && !var_check_lock(b->bv_lock, 1945 (char_u *)N_("add() argument"), TRUE)) 1946 { 1947 int error = FALSE; 1948 varnumber_T n = tv_get_number_chk(&argvars[1], &error); 1949 1950 if (!error) 1951 { 1952 ga_append(&b->bv_ga, (int)n); 1953 copy_tv(&argvars[0], rettv); 1954 } 1955 } 1956 } 1957 else 1958 emsg(_(e_listblobreq)); 1959 } 1960 1961 /* 1962 * "count()" function 1963 */ 1964 void 1965 f_count(typval_T *argvars, typval_T *rettv) 1966 { 1967 long n = 0; 1968 int ic = FALSE; 1969 int error = FALSE; 1970 1971 if (argvars[2].v_type != VAR_UNKNOWN) 1972 ic = (int)tv_get_number_chk(&argvars[2], &error); 1973 1974 if (argvars[0].v_type == VAR_STRING) 1975 { 1976 char_u *expr = tv_get_string_chk(&argvars[1]); 1977 char_u *p = argvars[0].vval.v_string; 1978 char_u *next; 1979 1980 if (!error && expr != NULL && *expr != NUL && p != NULL) 1981 { 1982 if (ic) 1983 { 1984 size_t len = STRLEN(expr); 1985 1986 while (*p != NUL) 1987 { 1988 if (MB_STRNICMP(p, expr, len) == 0) 1989 { 1990 ++n; 1991 p += len; 1992 } 1993 else 1994 MB_PTR_ADV(p); 1995 } 1996 } 1997 else 1998 while ((next = (char_u *)strstr((char *)p, (char *)expr)) 1999 != NULL) 2000 { 2001 ++n; 2002 p = next + STRLEN(expr); 2003 } 2004 } 2005 2006 } 2007 else if (argvars[0].v_type == VAR_LIST) 2008 { 2009 listitem_T *li; 2010 list_T *l; 2011 long idx; 2012 2013 if ((l = argvars[0].vval.v_list) != NULL) 2014 { 2015 CHECK_LIST_MATERIALIZE(l); 2016 li = l->lv_first; 2017 if (argvars[2].v_type != VAR_UNKNOWN) 2018 { 2019 if (argvars[3].v_type != VAR_UNKNOWN) 2020 { 2021 idx = (long)tv_get_number_chk(&argvars[3], &error); 2022 if (!error) 2023 { 2024 li = list_find(l, idx); 2025 if (li == NULL) 2026 semsg(_(e_listidx), idx); 2027 } 2028 } 2029 if (error) 2030 li = NULL; 2031 } 2032 2033 for ( ; li != NULL; li = li->li_next) 2034 if (tv_equal(&li->li_tv, &argvars[1], ic, FALSE)) 2035 ++n; 2036 } 2037 } 2038 else if (argvars[0].v_type == VAR_DICT) 2039 { 2040 int todo; 2041 dict_T *d; 2042 hashitem_T *hi; 2043 2044 if ((d = argvars[0].vval.v_dict) != NULL) 2045 { 2046 if (argvars[2].v_type != VAR_UNKNOWN) 2047 { 2048 if (argvars[3].v_type != VAR_UNKNOWN) 2049 emsg(_(e_invarg)); 2050 } 2051 2052 todo = error ? 0 : (int)d->dv_hashtab.ht_used; 2053 for (hi = d->dv_hashtab.ht_array; todo > 0; ++hi) 2054 { 2055 if (!HASHITEM_EMPTY(hi)) 2056 { 2057 --todo; 2058 if (tv_equal(&HI2DI(hi)->di_tv, &argvars[1], ic, FALSE)) 2059 ++n; 2060 } 2061 } 2062 } 2063 } 2064 else 2065 semsg(_(e_listdictarg), "count()"); 2066 rettv->vval.v_number = n; 2067 } 2068 2069 /* 2070 * "extend(list, list [, idx])" function 2071 * "extend(dict, dict [, action])" function 2072 */ 2073 void 2074 f_extend(typval_T *argvars, typval_T *rettv) 2075 { 2076 char_u *arg_errmsg = (char_u *)N_("extend() argument"); 2077 2078 if (argvars[0].v_type == VAR_LIST && argvars[1].v_type == VAR_LIST) 2079 { 2080 list_T *l1, *l2; 2081 listitem_T *item; 2082 long before; 2083 int error = FALSE; 2084 2085 l1 = argvars[0].vval.v_list; 2086 l2 = argvars[1].vval.v_list; 2087 if (l1 != NULL && !var_check_lock(l1->lv_lock, arg_errmsg, TRUE) 2088 && l2 != NULL) 2089 { 2090 if (argvars[2].v_type != VAR_UNKNOWN) 2091 { 2092 before = (long)tv_get_number_chk(&argvars[2], &error); 2093 if (error) 2094 return; // type error; errmsg already given 2095 2096 if (before == l1->lv_len) 2097 item = NULL; 2098 else 2099 { 2100 item = list_find(l1, before); 2101 if (item == NULL) 2102 { 2103 semsg(_(e_listidx), before); 2104 return; 2105 } 2106 } 2107 } 2108 else 2109 item = NULL; 2110 list_extend(l1, l2, item); 2111 2112 copy_tv(&argvars[0], rettv); 2113 } 2114 } 2115 else if (argvars[0].v_type == VAR_DICT && argvars[1].v_type == VAR_DICT) 2116 { 2117 dict_T *d1, *d2; 2118 char_u *action; 2119 int i; 2120 2121 d1 = argvars[0].vval.v_dict; 2122 d2 = argvars[1].vval.v_dict; 2123 if (d1 != NULL && !var_check_lock(d1->dv_lock, arg_errmsg, TRUE) 2124 && d2 != NULL) 2125 { 2126 // Check the third argument. 2127 if (argvars[2].v_type != VAR_UNKNOWN) 2128 { 2129 static char *(av[]) = {"keep", "force", "error"}; 2130 2131 action = tv_get_string_chk(&argvars[2]); 2132 if (action == NULL) 2133 return; // type error; errmsg already given 2134 for (i = 0; i < 3; ++i) 2135 if (STRCMP(action, av[i]) == 0) 2136 break; 2137 if (i == 3) 2138 { 2139 semsg(_(e_invarg2), action); 2140 return; 2141 } 2142 } 2143 else 2144 action = (char_u *)"force"; 2145 2146 dict_extend(d1, d2, action); 2147 2148 copy_tv(&argvars[0], rettv); 2149 } 2150 } 2151 else 2152 semsg(_(e_listdictarg), "extend()"); 2153 } 2154 2155 /* 2156 * "insert()" function 2157 */ 2158 void 2159 f_insert(typval_T *argvars, typval_T *rettv) 2160 { 2161 long before = 0; 2162 listitem_T *item; 2163 list_T *l; 2164 int error = FALSE; 2165 2166 if (argvars[0].v_type == VAR_BLOB) 2167 { 2168 int val, len; 2169 char_u *p; 2170 2171 if (argvars[0].vval.v_blob == NULL) 2172 return; 2173 2174 len = blob_len(argvars[0].vval.v_blob); 2175 if (argvars[2].v_type != VAR_UNKNOWN) 2176 { 2177 before = (long)tv_get_number_chk(&argvars[2], &error); 2178 if (error) 2179 return; // type error; errmsg already given 2180 if (before < 0 || before > len) 2181 { 2182 semsg(_(e_invarg2), tv_get_string(&argvars[2])); 2183 return; 2184 } 2185 } 2186 val = tv_get_number_chk(&argvars[1], &error); 2187 if (error) 2188 return; 2189 if (val < 0 || val > 255) 2190 { 2191 semsg(_(e_invarg2), tv_get_string(&argvars[1])); 2192 return; 2193 } 2194 2195 if (ga_grow(&argvars[0].vval.v_blob->bv_ga, 1) == FAIL) 2196 return; 2197 p = (char_u *)argvars[0].vval.v_blob->bv_ga.ga_data; 2198 mch_memmove(p + before + 1, p + before, (size_t)len - before); 2199 *(p + before) = val; 2200 ++argvars[0].vval.v_blob->bv_ga.ga_len; 2201 2202 copy_tv(&argvars[0], rettv); 2203 } 2204 else if (argvars[0].v_type != VAR_LIST) 2205 semsg(_(e_listblobarg), "insert()"); 2206 else if ((l = argvars[0].vval.v_list) != NULL 2207 && !var_check_lock(l->lv_lock, 2208 (char_u *)N_("insert() argument"), TRUE)) 2209 { 2210 if (argvars[2].v_type != VAR_UNKNOWN) 2211 before = (long)tv_get_number_chk(&argvars[2], &error); 2212 if (error) 2213 return; // type error; errmsg already given 2214 2215 if (before == l->lv_len) 2216 item = NULL; 2217 else 2218 { 2219 item = list_find(l, before); 2220 if (item == NULL) 2221 { 2222 semsg(_(e_listidx), before); 2223 l = NULL; 2224 } 2225 } 2226 if (l != NULL) 2227 { 2228 list_insert_tv(l, &argvars[1], item); 2229 copy_tv(&argvars[0], rettv); 2230 } 2231 } 2232 } 2233 2234 /* 2235 * "remove()" function 2236 */ 2237 void 2238 f_remove(typval_T *argvars, typval_T *rettv) 2239 { 2240 char_u *arg_errmsg = (char_u *)N_("remove() argument"); 2241 2242 if (argvars[0].v_type == VAR_DICT) 2243 dict_remove(argvars, rettv, arg_errmsg); 2244 else if (argvars[0].v_type == VAR_BLOB) 2245 blob_remove(argvars, rettv); 2246 else if (argvars[0].v_type == VAR_LIST) 2247 list_remove(argvars, rettv, arg_errmsg); 2248 else 2249 semsg(_(e_listdictblobarg), "remove()"); 2250 } 2251 2252 /* 2253 * "reverse({list})" function 2254 */ 2255 void 2256 f_reverse(typval_T *argvars, typval_T *rettv) 2257 { 2258 list_T *l; 2259 listitem_T *li, *ni; 2260 2261 if (argvars[0].v_type == VAR_BLOB) 2262 { 2263 blob_T *b = argvars[0].vval.v_blob; 2264 int i, len = blob_len(b); 2265 2266 for (i = 0; i < len / 2; i++) 2267 { 2268 int tmp = blob_get(b, i); 2269 2270 blob_set(b, i, blob_get(b, len - i - 1)); 2271 blob_set(b, len - i - 1, tmp); 2272 } 2273 rettv_blob_set(rettv, b); 2274 return; 2275 } 2276 2277 if (argvars[0].v_type != VAR_LIST) 2278 semsg(_(e_listblobarg), "reverse()"); 2279 else if ((l = argvars[0].vval.v_list) != NULL 2280 && !var_check_lock(l->lv_lock, 2281 (char_u *)N_("reverse() argument"), TRUE)) 2282 { 2283 if (l->lv_first == &range_list_item) 2284 { 2285 varnumber_T new_start = l->lv_u.nonmat.lv_start 2286 + (l->lv_len - 1) * l->lv_u.nonmat.lv_stride; 2287 l->lv_u.nonmat.lv_end = new_start 2288 - (l->lv_u.nonmat.lv_end - l->lv_u.nonmat.lv_start); 2289 l->lv_u.nonmat.lv_start = new_start; 2290 l->lv_u.nonmat.lv_stride = -l->lv_u.nonmat.lv_stride; 2291 rettv_list_set(rettv, l); 2292 return; 2293 } 2294 li = l->lv_u.mat.lv_last; 2295 l->lv_first = l->lv_u.mat.lv_last = NULL; 2296 l->lv_len = 0; 2297 while (li != NULL) 2298 { 2299 ni = li->li_prev; 2300 list_append(l, li); 2301 li = ni; 2302 } 2303 rettv_list_set(rettv, l); 2304 l->lv_u.mat.lv_idx = l->lv_len - l->lv_u.mat.lv_idx - 1; 2305 } 2306 } 2307 2308 #endif // defined(FEAT_EVAL) 2309