Currently, the way sorting works in eval.c (global variables representing the parameters of the current state) causes undefined behavior in the event that a comparison function calls sort(). I moved the parameters into a struct so it can be changed and reverted if sort() is called while already sorting.
I added a test to test_sort.vim (which causes a segfault before my patch on my machine) for the issue. -Jake -- -- You received this message from the "vim_dev" maillist. Do not top-post! Type your reply below the text you are replying to. For more information, visit http://www.vim.org/maillist.php --- You received this message because you are subscribed to the Google Groups "vim_dev" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. For more options, visit https://groups.google.com/d/optout.
>From 0afb9b2cd641f62eabacbb52036784ddaee2f08d Mon Sep 17 00:00:00 2001 From: Jacob Niehus <[email protected]> Date: Sun, 21 Feb 2016 22:06:15 -0700 Subject: [PATCH] Fix undefined behavior when calling sort() from a compare function --- src/eval.c | 131 +++++++++++++++++++++++++++------------------- src/testdir/test_sort.vim | 14 +++++ 2 files changed, 90 insertions(+), 55 deletions(-) diff --git a/src/eval.c b/src/eval.c index 3fb06d0..d48f4be 100644 --- a/src/eval.c +++ b/src/eval.c @@ -18788,16 +18788,21 @@ typedef struct int idx; } sortItem_T; -static int item_compare_ic; -static int item_compare_numeric; -static int item_compare_numbers; +/* struct storing information about current sort */ +typedef struct +{ + int item_compare_ic; + int item_compare_numeric; + int item_compare_numbers; #ifdef FEAT_FLOAT -static int item_compare_float; -#endif -static char_u *item_compare_func; -static dict_T *item_compare_selfdict; -static int item_compare_func_err; -static int item_compare_keep_zero; + int item_compare_float; +#endif + char_u *item_compare_func; + dict_T *item_compare_selfdict; + int item_compare_func_err; + int item_compare_keep_zero; +} sortinfo_T; +static sortinfo_T *sortinfo; static void do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort); #define ITEM_COMPARE_FAIL 999 @@ -18823,7 +18828,7 @@ item_compare(const void *s1, const void *s2) tv1 = &si1->item->li_tv; tv2 = &si2->item->li_tv; - if (item_compare_numbers) + if (sortinfo->item_compare_numbers) { long v1 = get_tv_number(tv1); long v2 = get_tv_number(tv2); @@ -18832,7 +18837,7 @@ item_compare(const void *s1, const void *s2) } #ifdef FEAT_FLOAT - if (item_compare_float) + if (sortinfo->item_compare_float) { float_T v1 = get_tv_float(tv1); float_T v2 = get_tv_float(tv2); @@ -18846,7 +18851,7 @@ item_compare(const void *s1, const void *s2) * non-string to do what the docs promise. */ if (tv1->v_type == VAR_STRING) { - if (tv2->v_type != VAR_STRING || item_compare_numeric) + if (tv2->v_type != VAR_STRING || sortinfo->item_compare_numeric) p1 = (char_u *)"'"; else p1 = tv1->vval.v_string; @@ -18855,7 +18860,7 @@ item_compare(const void *s1, const void *s2) p1 = tv2string(tv1, &tofree1, numbuf1, 0); if (tv2->v_type == VAR_STRING) { - if (tv1->v_type != VAR_STRING || item_compare_numeric) + if (tv1->v_type != VAR_STRING || sortinfo->item_compare_numeric) p2 = (char_u *)"'"; else p2 = tv2->vval.v_string; @@ -18866,9 +18871,9 @@ item_compare(const void *s1, const void *s2) p1 = (char_u *)""; if (p2 == NULL) p2 = (char_u *)""; - if (!item_compare_numeric) + if (!sortinfo->item_compare_numeric) { - if (item_compare_ic) + if (sortinfo->item_compare_ic) res = STRICMP(p1, p2); else res = STRCMP(p1, p2); @@ -18883,7 +18888,7 @@ item_compare(const void *s1, const void *s2) /* When the result would be zero, compare the item indexes. Makes the * sort stable. */ - if (res == 0 && !item_compare_keep_zero) + if (res == 0 && !sortinfo->item_compare_keep_zero) res = si1->idx > si2->idx ? 1 : -1; vim_free(tofree1); @@ -18904,7 +18909,7 @@ item_compare2(const void *s1, const void *s2) int dummy; /* shortcut after failure in previous call; compare all items equal */ - if (item_compare_func_err) + if (sortinfo->item_compare_func_err) return 0; si1 = (sortItem_T *)s1; @@ -18916,23 +18921,24 @@ item_compare2(const void *s1, const void *s2) copy_tv(&si2->item->li_tv, &argv[1]); rettv.v_type = VAR_UNKNOWN; /* clear_tv() uses this */ - res = call_func(item_compare_func, (int)STRLEN(item_compare_func), + res = call_func(sortinfo->item_compare_func, + (int)STRLEN(sortinfo->item_compare_func), &rettv, 2, argv, 0L, 0L, &dummy, TRUE, - item_compare_selfdict); + sortinfo->item_compare_selfdict); clear_tv(&argv[0]); clear_tv(&argv[1]); if (res == FAIL) res = ITEM_COMPARE_FAIL; else - res = get_tv_number_chk(&rettv, &item_compare_func_err); - if (item_compare_func_err) + res = get_tv_number_chk(&rettv, &sortinfo->item_compare_func_err); + if (sortinfo->item_compare_func_err) res = ITEM_COMPARE_FAIL; /* return value has wrong type */ clear_tv(&rettv); /* When the result would be zero, compare the pointers themselves. Makes * the sort stable. */ - if (res == 0 && !item_compare_keep_zero) + if (res == 0 && !sortinfo->item_compare_keep_zero) res = si1->idx > si2->idx ? 1 : -1; return res; @@ -18947,9 +18953,13 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) list_T *l; listitem_T *li; sortItem_T *ptrs; + sortinfo_T info; long len; long i; + /* Pointer to current info struct used in compare function. */ + sortinfo = &info; + if (argvars[0].v_type != VAR_LIST) EMSG2(_(e_listarg), sort ? "sort()" : "uniq()"); else @@ -18967,19 +18977,19 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) if (len <= 1) return; /* short list sorts pretty quickly */ - item_compare_ic = FALSE; - item_compare_numeric = FALSE; - item_compare_numbers = FALSE; + info.item_compare_ic = FALSE; + info.item_compare_numeric = FALSE; + info.item_compare_numbers = FALSE; #ifdef FEAT_FLOAT - item_compare_float = FALSE; + info.item_compare_float = FALSE; #endif - item_compare_func = NULL; - item_compare_selfdict = NULL; + info.item_compare_func = NULL; + info.item_compare_selfdict = NULL; if (argvars[1].v_type != VAR_UNKNOWN) { /* optional second argument: {func} */ if (argvars[1].v_type == VAR_FUNC) - item_compare_func = argvars[1].vval.v_string; + info.item_compare_func = argvars[1].vval.v_string; else { int error = FALSE; @@ -18988,32 +18998,32 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) if (error) return; /* type error; errmsg already given */ if (i == 1) - item_compare_ic = TRUE; + info.item_compare_ic = TRUE; else - item_compare_func = get_tv_string(&argvars[1]); - if (item_compare_func != NULL) + info.item_compare_func = get_tv_string(&argvars[1]); + if (info.item_compare_func != NULL) { - if (STRCMP(item_compare_func, "n") == 0) + if (STRCMP(info.item_compare_func, "n") == 0) { - item_compare_func = NULL; - item_compare_numeric = TRUE; + info.item_compare_func = NULL; + info.item_compare_numeric = TRUE; } - else if (STRCMP(item_compare_func, "N") == 0) + else if (STRCMP(info.item_compare_func, "N") == 0) { - item_compare_func = NULL; - item_compare_numbers = TRUE; + info.item_compare_func = NULL; + info.item_compare_numbers = TRUE; } #ifdef FEAT_FLOAT - else if (STRCMP(item_compare_func, "f") == 0) + else if (STRCMP(info.item_compare_func, "f") == 0) { - item_compare_func = NULL; - item_compare_float = TRUE; + info.item_compare_func = NULL; + info.item_compare_float = TRUE; } #endif - else if (STRCMP(item_compare_func, "i") == 0) + else if (STRCMP(info.item_compare_func, "i") == 0) { - item_compare_func = NULL; - item_compare_ic = TRUE; + info.item_compare_func = NULL; + info.item_compare_ic = TRUE; } } } @@ -19026,7 +19036,7 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) EMSG(_(e_dictreq)); return; } - item_compare_selfdict = argvars[2].vval.v_dict; + info.item_compare_selfdict = argvars[2].vval.v_dict; } } @@ -19046,10 +19056,10 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) ++i; } - item_compare_func_err = FALSE; - item_compare_keep_zero = FALSE; + info.item_compare_func_err = FALSE; + info.item_compare_keep_zero = FALSE; /* test the compare function */ - if (item_compare_func != NULL + if (info.item_compare_func != NULL && item_compare2((void *)&ptrs[0], (void *)&ptrs[1]) == ITEM_COMPARE_FAIL) EMSG(_("E702: Sort compare function failed")); @@ -19057,9 +19067,10 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) { /* Sort the array with item pointers. */ qsort((void *)ptrs, (size_t)len, sizeof(sortItem_T), - item_compare_func == NULL ? item_compare : item_compare2); + info.item_compare_func == NULL + ? item_compare : item_compare2); - if (!item_compare_func_err) + if (!info.item_compare_func_err) { /* Clear the List and append the items in sorted order. */ l->lv_first = l->lv_last = l->lv_idx_item = NULL; @@ -19074,9 +19085,9 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) int (*item_compare_func_ptr)(const void *, const void *); /* f_uniq(): ptrs will be a stack of items to remove */ - item_compare_func_err = FALSE; - item_compare_keep_zero = TRUE; - item_compare_func_ptr = item_compare_func + info.item_compare_func_err = FALSE; + info.item_compare_keep_zero = TRUE; + item_compare_func_ptr = info.item_compare_func ? item_compare2 : item_compare; for (li = l->lv_first; li != NULL && li->li_next != NULL; @@ -19085,14 +19096,14 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) if (item_compare_func_ptr((void *)&li, (void *)&li->li_next) == 0) ptrs[i++].item = li; - if (item_compare_func_err) + if (info.item_compare_func_err) { EMSG(_("E882: Uniq compare function failed")); break; } } - if (!item_compare_func_err) + if (!info.item_compare_func_err) { while (--i >= 0) { @@ -19119,7 +19130,12 @@ do_sort_uniq(typval_T *argvars, typval_T *rettv, int sort) static void f_sort(typval_T *argvars, typval_T *rettv) { + sortinfo_T *old_sortinfo; /* Pointer to previous info struct in case of + * nested sort() calls. */ + + old_sortinfo = sortinfo; do_sort_uniq(argvars, rettv, TRUE); + sortinfo = old_sortinfo; } /* @@ -19128,7 +19144,12 @@ f_sort(typval_T *argvars, typval_T *rettv) static void f_uniq(typval_T *argvars, typval_T *rettv) { + sortinfo_T *old_sortinfo; /* Pointer to previous info struct in case of + * nested sort() calls. */ + + old_sortinfo = sortinfo; do_sort_uniq(argvars, rettv, FALSE); + sortinfo = old_sortinfo; } /* diff --git a/src/testdir/test_sort.vim b/src/testdir/test_sort.vim index 32ad7f8..68021f6 100644 --- a/src/testdir/test_sort.vim +++ b/src/testdir/test_sort.vim @@ -1,5 +1,14 @@ " Test sort() +:func Compare1(a, b) abort + call sort(range(3), 'Compare2') + return a:a ># a:b +:endfunc + +:func Compare2(a, b) abort + return a:a <# a:b +:endfunc + func Test_sort_strings() " numbers compared as strings call assert_equal([1, 2, 3], sort([3, 2, 1])) @@ -21,3 +30,8 @@ endfunc func Test_sort_float() call assert_equal([0.28, 3, 13.5], sort([13.5, 0.28, 3], 'f')) endfunc + +func Test_sort_nested() + " test ability to call sort() from a compare function + call assert_equal([1, 3, 5], sort([3, 1, 5], 'Compare1')) +endfunc -- 2.4.2
