## Patch 7.4.341

Expand Messages
• Patch 7.4.341 Problem: sort() doesn t handle numbers well. Solution: Add an argument to specify sorting on numbers. (Christian Brabandt) Files:
Message 1 of 5 , Jun 25, 2014
Patch 7.4.341
Problem: sort() doesn't handle numbers well.
Solution: Add an argument to specify sorting on numbers. (Christian Brabandt)
Files: runtime/doc/eval.txt, src/eval.c, src/testdir/test55.in,
src/testdir/test55.ok

*** ../vim-7.4.340/runtime/doc/eval.txt 2014-06-25 14:39:35.094348583 +0200
--- runtime/doc/eval.txt 2014-06-25 17:05:50.606680574 +0200
***************
*** 5618,5628 ****

If you want a list to remain unmodified make a copy first: >
:let sortedlist = sort(copy(mylist))
- < Uses the string representation of each item to sort on.
- Numbers sort after Strings, |Lists| after Numbers.
- For sorting text in the current buffer use |:sort|.

! When {func} is given and it is one then case is ignored.
When {func} is a |Funcref| or a function name, this function
is called to compare items. The function is invoked with two
items as argument and must return zero if they are equal, 1 or
--- 5628,5647 ----

If you want a list to remain unmodified make a copy first: >
:let sortedlist = sort(copy(mylist))

! < When {func} is omitted, is empty or zero, then sort() uses the
! string representation of each item to sort on. Numbers sort
! after Strings, |Lists| after Numbers. For sorting text in the
! current buffer use |:sort|.
!
! When {func} is given and it is is '1' or 'i' then case is
! ignored.
!
! When {func} is given and it is 'n' then all items will be
! sorted numerical (Implementation detail: This uses the
! strtod() function to parse numbers, Strings, Lists, Dicts and
! Funcrefs will be considered as being 0).
!
When {func} is a |Funcref| or a function name, this function
is called to compare items. The function is invoked with two
items as argument and must return zero if they are equal, 1 or
*** ../vim-7.4.340/src/eval.c 2014-06-17 17:48:21.776628008 +0200
--- src/eval.c 2014-06-25 17:23:05.466719724 +0200
***************
*** 17330,17335 ****
--- 17330,17336 ----
item_compare2 __ARGS((const void *s1, const void *s2));

static int item_compare_ic;
+ static int item_compare_numeric;
static char_u *item_compare_func;
static dict_T *item_compare_selfdict;
static int item_compare_func_err;
***************
*** 17359,17368 ****
p1 = (char_u *)"";
if (p2 == NULL)
p2 = (char_u *)"";
! if (item_compare_ic)
! res = STRICMP(p1, p2);
else
! res = STRCMP(p1, p2);
vim_free(tofree1);
vim_free(tofree2);
return res;
--- 17360,17379 ----
p1 = (char_u *)"";
if (p2 == NULL)
p2 = (char_u *)"";
! if (!item_compare_numeric)
! {
! if (item_compare_ic)
! res = STRICMP(p1, p2);
! else
! res = STRCMP(p1, p2);
! }
else
! {
! double n1, n2;
! n1 = strtod((char *)p1, (char **)&p1);
! n2 = strtod((char *)p2, (char **)&p2);
! res = n1 == n2 ? 0 : n1 > n2 ? 1 : -1;
! }
vim_free(tofree1);
vim_free(tofree2);
return res;
***************
*** 17439,17444 ****
--- 17450,17456 ----
return; /* short list sorts pretty quickly */

item_compare_ic = FALSE;
+ item_compare_numeric = FALSE;
item_compare_func = NULL;
item_compare_selfdict = NULL;
if (argvars[1].v_type != VAR_UNKNOWN)
***************
*** 17457,17462 ****
--- 17469,17487 ----
item_compare_ic = TRUE;
else
item_compare_func = get_tv_string(&argvars[1]);
+ if (item_compare_func != NULL)
+ {
+ if (STRCMP(item_compare_func, "n") == 0)
+ {
+ item_compare_func = NULL;
+ item_compare_numeric = TRUE;
+ }
+ else if (STRCMP(item_compare_func, "i") == 0)
+ {
+ item_compare_func = NULL;
+ item_compare_ic = TRUE;
+ }
+ }
}

if (argvars[2].v_type != VAR_UNKNOWN)
*** ../vim-7.4.340/src/testdir/test55.in 2014-03-25 18:23:27.062087691 +0100
--- src/testdir/test55.in 2014-06-25 17:20:47.006714486 +0200
***************
*** 332,337 ****
--- 332,342 ----
:\$put =string(reverse(sort(l)))
:\$put =string(sort(reverse(sort(l))))
:\$put =string(uniq(sort(l)))
+ :let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0, -0, 0.22, 'foo', 'FOOBAR',{}, []]
+ :\$put =string(sort(copy(l), 'n'))
+ :\$put =string(sort(copy(l), 1))
+ :\$put =string(sort(copy(l), 'i'))
+ :\$put =string(sort(copy(l)))
:"
:" splitting a string to a List
:\$put =string(split(' aa bb '))
*** ../vim-7.4.340/src/testdir/test55.ok 2014-03-25 18:23:27.062087691 +0100
--- src/testdir/test55.ok 2014-06-25 17:23:31.382720704 +0200
***************
*** 101,106 ****
--- 101,110 ----
[[0, 1, 2], [0, 1, 2], 4, 2, 2, 1.5, 'xaaa', 'x8', 'foo6', 'foo', 'foo', 'A11', '-0']
['-0', 'A11', 'foo', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 2, 4, [0, 1, 2], [0, 1, 2]]
['-0', 'A11', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 4, [0, 1, 2]]
+ [-1, 0, 0, 'foo', 'FOOBAR', {}, [], 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]
+ ['foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
+ ['foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
+ ['FOOBAR', 'foo', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
['aa', 'bb']
['aa', 'bb']
['', 'aa', 'bb', '']
*** ../vim-7.4.340/src/version.c 2014-06-25 15:02:29.250400570 +0200
--- src/version.c 2014-06-25 16:46:45.438637250 +0200
***************
*** 736,737 ****
--- 736,739 ----
{ /* Add new patch number below this line */
+ /**/
+ 341,
/**/

--
We do not stumble over mountains, but over molehills.
Confucius

/// Bram Moolenaar -- Bram@... -- http://www.Moolenaar.net \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///

--
--
You received this message from the "vim_dev" maillist.

---
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 vim_dev+unsubscribe@....
• Hi, On my Mac, I ve been unable to install vim due to a failure of test55 coming with Patch 7.4.341. To be more specific, the failure is relevant to lines
Message 2 of 5 , Jun 25, 2014
Hi,

On my Mac, I've been unable to install vim due to a failure of test55 coming with Patch 7.4.341.

To be more specific, the failure is relevant to lines 335--336 of test55.in, and the comparison of test55.failed I got with test55.ok is

\$ diff test55.failed test55.ok
104c104
< [-1, [], {}, 'FOOBAR', 'foo', 0, 0, 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]
---
> [-1, 0, 0, 'foo', 'FOOBAR', {}, [], 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]

But... It looks the Mac just gave one of possible correct results, doesn't it?

Or, is there an undocumented criterion that determines a unique sorting order among such elements that have the same strtod()-oriented precedence?

Regards,
Kazunobu Kuriyama

On Jun 26, 2014, at 0:31, Bram Moolenaar <Bram@...> wrote:

>
> Patch 7.4.341
> Problem: sort() doesn't handle numbers well.
> Solution: Add an argument to specify sorting on numbers. (Christian Brabandt)
> Files: runtime/doc/eval.txt, src/eval.c, src/testdir/test55.in,
> src/testdir/test55.ok
>
>
> *** ../vim-7.4.340/runtime/doc/eval.txt 2014-06-25 14:39:35.094348583 +0200
> --- runtime/doc/eval.txt 2014-06-25 17:05:50.606680574 +0200
> ***************
> *** 5618,5628 ****
>
> If you want a list to remain unmodified make a copy first: >
> :let sortedlist = sort(copy(mylist))
> - < Uses the string representation of each item to sort on.
> - Numbers sort after Strings, |Lists| after Numbers.
> - For sorting text in the current buffer use |:sort|.
>
> ! When {func} is given and it is one then case is ignored.
> When {func} is a |Funcref| or a function name, this function
> is called to compare items. The function is invoked with two
> items as argument and must return zero if they are equal, 1 or
> --- 5628,5647 ----
>
> If you want a list to remain unmodified make a copy first: >
> :let sortedlist = sort(copy(mylist))
>
> ! < When {func} is omitted, is empty or zero, then sort() uses the
> ! string representation of each item to sort on. Numbers sort
> ! after Strings, |Lists| after Numbers. For sorting text in the
> ! current buffer use |:sort|.
> !
> ! When {func} is given and it is is '1' or 'i' then case is
> ! ignored.
> !
> ! When {func} is given and it is 'n' then all items will be
> ! sorted numerical (Implementation detail: This uses the
> ! strtod() function to parse numbers, Strings, Lists, Dicts and
> ! Funcrefs will be considered as being 0).
> !
> When {func} is a |Funcref| or a function name, this function
> is called to compare items. The function is invoked with two
> items as argument and must return zero if they are equal, 1 or
> *** ../vim-7.4.340/src/eval.c 2014-06-17 17:48:21.776628008 +0200
> --- src/eval.c 2014-06-25 17:23:05.466719724 +0200
> ***************
> *** 17330,17335 ****
> --- 17330,17336 ----
> item_compare2 __ARGS((const void *s1, const void *s2));
>
> static int item_compare_ic;
> + static int item_compare_numeric;
> static char_u *item_compare_func;
> static dict_T *item_compare_selfdict;
> static int item_compare_func_err;
> ***************
> *** 17359,17368 ****
> p1 = (char_u *)"";
> if (p2 == NULL)
> p2 = (char_u *)"";
> ! if (item_compare_ic)
> ! res = STRICMP(p1, p2);
> else
> ! res = STRCMP(p1, p2);
> vim_free(tofree1);
> vim_free(tofree2);
> return res;
> --- 17360,17379 ----
> p1 = (char_u *)"";
> if (p2 == NULL)
> p2 = (char_u *)"";
> ! if (!item_compare_numeric)
> ! {
> ! if (item_compare_ic)
> ! res = STRICMP(p1, p2);
> ! else
> ! res = STRCMP(p1, p2);
> ! }
> else
> ! {
> ! double n1, n2;
> ! n1 = strtod((char *)p1, (char **)&p1);
> ! n2 = strtod((char *)p2, (char **)&p2);
> ! res = n1 == n2 ? 0 : n1 > n2 ? 1 : -1;
> ! }
> vim_free(tofree1);
> vim_free(tofree2);
> return res;
> ***************
> *** 17439,17444 ****
> --- 17450,17456 ----
> return; /* short list sorts pretty quickly */
>
> item_compare_ic = FALSE;
> + item_compare_numeric = FALSE;
> item_compare_func = NULL;
> item_compare_selfdict = NULL;
> if (argvars[1].v_type != VAR_UNKNOWN)
> ***************
> *** 17457,17462 ****
> --- 17469,17487 ----
> item_compare_ic = TRUE;
> else
> item_compare_func = get_tv_string(&argvars[1]);
> + if (item_compare_func != NULL)
> + {
> + if (STRCMP(item_compare_func, "n") == 0)
> + {
> + item_compare_func = NULL;
> + item_compare_numeric = TRUE;
> + }
> + else if (STRCMP(item_compare_func, "i") == 0)
> + {
> + item_compare_func = NULL;
> + item_compare_ic = TRUE;
> + }
> + }
> }
>
> if (argvars[2].v_type != VAR_UNKNOWN)
> *** ../vim-7.4.340/src/testdir/test55.in 2014-03-25 18:23:27.062087691 +0100
> --- src/testdir/test55.in 2014-06-25 17:20:47.006714486 +0200
> ***************
> *** 332,337 ****
> --- 332,342 ----
> :\$put =string(reverse(sort(l)))
> :\$put =string(sort(reverse(sort(l))))
> :\$put =string(uniq(sort(l)))
> + :let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0, -0, 0.22, 'foo', 'FOOBAR',{}, []]
> + :\$put =string(sort(copy(l), 'n'))
> + :\$put =string(sort(copy(l), 1))
> + :\$put =string(sort(copy(l), 'i'))
> + :\$put =string(sort(copy(l)))
> :"
> :" splitting a string to a List
> :\$put =string(split(' aa bb '))
> *** ../vim-7.4.340/src/testdir/test55.ok 2014-03-25 18:23:27.062087691 +0100
> --- src/testdir/test55.ok 2014-06-25 17:23:31.382720704 +0200
> ***************
> *** 101,106 ****
> --- 101,110 ----
> [[0, 1, 2], [0, 1, 2], 4, 2, 2, 1.5, 'xaaa', 'x8', 'foo6', 'foo', 'foo', 'A11', '-0']
> ['-0', 'A11', 'foo', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 2, 4, [0, 1, 2], [0, 1, 2]]
> ['-0', 'A11', 'foo', 'foo6', 'x8', 'xaaa', 1.5, 2, 4, [0, 1, 2]]
> + [-1, 0, 0, 'foo', 'FOOBAR', {}, [], 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]
> + ['foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
> + ['foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
> + ['FOOBAR', 'foo', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
> ['aa', 'bb']
> ['aa', 'bb']
> ['', 'aa', 'bb', '']
> *** ../vim-7.4.340/src/version.c 2014-06-25 15:02:29.250400570 +0200
> --- src/version.c 2014-06-25 16:46:45.438637250 +0200
> ***************
> *** 736,737 ****
> --- 736,739 ----
> { /* Add new patch number below this line */
> + /**/
> + 341,
> /**/
>
> --
> We do not stumble over mountains, but over molehills.
> Confucius
>
> /// Bram Moolenaar -- Bram@... -- http://www.Moolenaar.net \\\
> \\\ an exciting new programming language -- http://www.Zimbu.org ///
> \\\ help me help AIDS victims -- http://ICCF-Holland.org ///
>
> --
> --
> You received this message from the "vim_dev" maillist.
>
> ---
> 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 vim_dev+unsubscribe@....
> For more options, visit https://groups.google.com/d/optout.

--
--
You received this message from the "vim_dev" maillist.

---
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 vim_dev+unsubscribe@....
• ... Yes, I ve noticed the same error and just been writing a bug report when I received your post. ... Yes. The qsort(3) is not a stable sort, i.e., it is not
Message 3 of 5 , Jun 25, 2014
On 2014/06/26, at 15:08, Kazunobu Kuriyama <kazunobu.kuriyama@...> wrote:
> On my Mac, I've been unable to install vim due to a failure of test55 coming with Patch 7.4.341.

Yes, I've noticed the same error and just been writing a bug report when

> But... It looks the Mac just gave one of possible correct results, doesn't it?

Yes.

The qsort(3) is not a stable sort, i.e., it is not guaranteed that the
original order is preserved among the "equal" elements.

The Linux version of qsort(3) is apparently stable for test55, but I guess
it may be not stable for other input (e.g., longer list). man qsort(3) says:
"If two members compare as equal, their order in the sorted array is undefined."

On Mac OS X (and freeBSD), man qsort(3) says:
"The algorithms implemented by qsort() ... are not stable; ... The mergesort()
algorithm is stable." But it seems mergesort() is available only on BSDs.

It would be possible to make vim's sort() function stable if we save the original
order in a separate array and use the array as the 2nd key for the comparison.
But I guess such elaboration is not worthwhile here.

Jun

--
--
You received this message from the "vim_dev" maillist.

---
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 vim_dev+unsubscribe@....
• ... No, I was wrong; saving in a separate array won t work; the original order should be saved in the same array, as in the following *experimental* patch.
Message 4 of 5 , Jun 26, 2014
On 2014/06/26, at 15:40, Jun T. <takimoto-j@...> wrote:
> It would be possible to make vim's sort() function stable if we save the original
> order in a separate array and ...

No, I was wrong; saving in a separate array won't work; the original order should
be saved in the same array, as in the following *experimental* patch.
This is just an experiment; I have no intention to say that the sort()
function should be stable.
Is there any simple way to make test55 work?

PS.
I have also attached the diff file.
Which is preferred here, inline patch of attached file?

diff -r e11fcef66289 src/eval.c
--- a/src/eval.c Wed Jun 25 22:55:38 2014 +0200
+++ b/src/eval.c Thu Jun 26 20:12:20 2014 +0900
@@ -17328,6 +17328,7 @@
_RTLENTRYF
#endif
item_compare2 __ARGS((const void *s1, const void *s2));
+static int item_compare_stable __ARGS((const void *s1, const void *s2));

static int item_compare_ic;
static int item_compare_numeric;
@@ -17418,6 +17419,25 @@
return res;
}

+/* struct for stable sort */
+typedef struct sdata_S {
+ listitem_T *li;
+ int i; /* original position in the list */
+} sdata_T;
+
+ static int
+item_compare_stable(s1, s2)
+ const void *s1;
+ const void *s2;
+{
+ int ret;
+ if(item_compare_func)
+ ret = item_compare2(&((sdata_T *)s1)->li, &((sdata_T *)s2)->li);
+ else
+ ret = item_compare(&((sdata_T *)s1)->li, &((sdata_T *)s2)->li);
+ return ret==0 ? ((sdata_T *)s1)->i - ((sdata_T *)s2)->i : ret;
+}
+
/*
* "sort({list})" function
*/
@@ -17429,7 +17449,6 @@
{
list_T *l;
listitem_T *li;
- listitem_T **ptrs;
long len;
long i;

@@ -17496,29 +17515,32 @@
}
}

- /* Make an array with each entry pointing to an item in the List. */
- ptrs = (listitem_T **)alloc((int)(len * sizeof(listitem_T *)));
- if (ptrs == NULL)
- return;
-
i = 0;
if (sort)
{
- /* sort(): ptrs will be the list to sort */
- for (li = l->lv_first; li != NULL; li = li->li_next)
- ptrs[i++] = li;
+ sdata_T *sdata;
+ sdata = (sdata_T *)alloc((int)(len * sizeof(sdata_T)));
+ if (sdata == NULL)
+ return;
+
+ /* save the original position i along with the item pointer */
+ for (li = l->lv_first; li != NULL; li = li->li_next) {
+ sdata[i].li = li;
+ sdata[i].i = i;
+ ++i;
+ }

item_compare_func_err = FALSE;
/* test the compare function */
if (item_compare_func != NULL
- && item_compare2((void *)&ptrs[0], (void *)&ptrs[1])
+ && item_compare2((void *)&sdata[0].li, (void *)&sdata[1].li)
== ITEM_COMPARE_FAIL)
EMSG(_("E702: Sort compare function failed"));
else
{
/* Sort the array with item pointers. */
- qsort((void *)ptrs, (size_t)len, sizeof(listitem_T *),
- item_compare_func == NULL ? item_compare : item_compare2);
+ qsort((void *)sdata, (size_t)len, sizeof(sdata_T),
+ item_compare_stable);

if (!item_compare_func_err)
{
@@ -17526,12 +17548,19 @@
l->lv_first = l->lv_last = l->lv_idx_item = NULL;
l->lv_len = 0;
for (i = 0; i < len; ++i)
- list_append(l, ptrs[i]);
- }
- }
- }
- else
- {
+ list_append(l, sdata[i].li);
+ }
+ }
+ vim_free(sdata);
+ }
+ else
+ {
+ listitem_T **ptrs;
+ /* Make an array with each entry pointing to an item in the List. */
+ ptrs = (listitem_T **)alloc((int)(len * sizeof(listitem_T *)));
+ if (ptrs == NULL)
+ return;
+
int (*item_compare_func_ptr)__ARGS((const void *, const void *));

/* f_uniq(): ptrs will be a stack of items to remove */
@@ -17567,9 +17596,9 @@
l->lv_len--;
}
}
- }
-
- vim_free(ptrs);
+ vim_free(ptrs);
+ }
+
}
}

--
--
You received this message from the "vim_dev" maillist.

---
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 vim_dev+unsubscribe@....
• ... Let s reduce the number of items that evaluate to zero to one item. Then it will work everywhere. -- WOMAN: King of the who? ARTHUR: The Britons. WOMAN:
Message 5 of 5 , Jun 26, 2014
Kazunobu Kuriyama wrote:

> On my Mac, I've been unable to install vim due to a failure of test55
> coming with Patch 7.4.341.
>
> To be more specific, the failure is relevant to lines 335--336 of
> test55.in, and the comparison of test55.failed I got with test55.ok is
>
> \$ diff test55.failed test55.ok
> 104c104
> < [-1, [], {}, 'FOOBAR', 'foo', 0, 0, 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]
> ---
> > [-1, 0, 0, 'foo', 'FOOBAR', {}, [], 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]
>
> But... It looks the Mac just gave one of possible correct results, doesn't it?
>
> Or, is there an undocumented criterion that determines a unique
> sorting order among such elements that have the same strtod()-oriented
> precedence?

Let's reduce the number of items that evaluate to zero to one item.
Then it will work everywhere.

--
WOMAN: King of the who?
ARTHUR: The Britons.
WOMAN: Who are the Britons?
ARTHUR: Well, we all are. we're all Britons and I am your king.
The Quest for the Holy Grail (Monty Python)

/// Bram Moolenaar -- Bram@... -- http://www.Moolenaar.net \\\
\\\ an exciting new programming language -- http://www.Zimbu.org ///
\\\ help me help AIDS victims -- http://ICCF-Holland.org ///

--
--
You received this message from the "vim_dev" maillist.

---
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 vim_dev+unsubscribe@....