vim-patch:7.4.351

Problem:    sort() is not stable.
Solution:   When the items are identical, compare the pointers.

https://code.google.com/p/vim/source/detail?r=v7-4-351

4 files changed, 26 insertions, 9 deletions

diff --git a/src/nvim/eval.c b/src/nvim/eval.c
index 8d06660b1b..d8fd6f95c5 100644
--- a/src/nvim/eval.c
+++ b/src/nvim/eval.c
@@ -13366,6 +13366,7 @@ static bool item_compare_numeric;
 static char_u   *item_compare_func;
 static dict_T   *item_compare_selfdict;
 static int item_compare_func_err;
+static bool  item_compare_keep_zero;
 #define ITEM_COMPARE_FAIL 999
 
 /*
@@ -13397,6 +13398,13 @@ static int item_compare(const void *s1, const void *s2)
     n2 = strtod((char *)p2, (char **)&p2);
     res = n1 == n2 ? 0 : n1 > n2 ? 1 : -1;
   }
+
+  // When the result would be zero, compare the pointers themselves.  Makes
+  // the sort stable.
+  if (res == 0 && !item_compare_keep_zero) {
+    res = s1 > s2 ? 1 : -1;
+  }
+  
   free(tofree1);
   free(tofree2);
   return res;
@@ -13413,8 +13421,8 @@ static int item_compare2(const void *s1, const void *s2)
   if (item_compare_func_err)
     return 0;
 
-  /* copy the values.  This is needed to be able to set v_lock to VAR_FIXED
-   * in the copy without changing the original list items. */
+  // Copy the values.  This is needed to be able to set v_lock to VAR_FIXED
+  // in the copy without changing the original list items.
   copy_tv(&(*(listitem_T **)s1)->li_tv, &argv[0]);
   copy_tv(&(*(listitem_T **)s2)->li_tv, &argv[1]);
 
@@ -13432,6 +13440,13 @@ static int item_compare2(const void *s1, const void *s2)
   if (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) {
+    res = s1 > s2 ? 1 : -1;
+  }
+
   return res;
 }
 
@@ -13513,6 +13528,7 @@ static void do_sort_uniq(typval_T *argvars, typval_T *rettv, bool sort)
       }
 
       item_compare_func_err = FALSE;
+      item_compare_keep_zero = false;
       // Test the compare function.
       if (item_compare_func != NULL
           && item_compare2(&ptrs[0], &ptrs[1]) == ITEM_COMPARE_FAIL) {
@@ -13539,6 +13555,7 @@ static void do_sort_uniq(typval_T *argvars, typval_T *rettv, bool sort)
 
       // 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 ? item_compare2 : item_compare;
 
       for (li = l->lv_first; li != NULL && li->li_next != NULL; li = li->li_next) {
diff --git a/src/nvim/testdir/test55.in b/src/nvim/testdir/test55.in
index ace97bf30e..8e073f30f2 100644
--- a/src/nvim/testdir/test55.in
+++ b/src/nvim/testdir/test55.in
@@ -332,9 +332,9 @@ let l = [0, 1, 2, 3]
 :$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.22, 'foo']
+:let l=[7, 9, 'one', 18, 12, 22, 'two', 10.0e-16, -1, 'three', 0xff, 0.22, 'four']
 :$put =string(sort(copy(l), 'n'))
-:let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0, -0, 0.22, 'foo', 'FOOBAR',{}, []]
+:let l=[7, 9, 18, 12, 22, 10.0e-16, -1, 0xff, 0, -0, 0.22, 'bar', 'BAR', 'Bar', 'Foo', 'FOO', 'foo', 'FOOBAR', {}, []]
 :$put =string(sort(copy(l), 1))
 :$put =string(sort(copy(l), 'i'))
 :$put =string(sort(copy(l)))
diff --git a/src/nvim/testdir/test55.ok b/src/nvim/testdir/test55.ok
index 3969995a1e..dfd8060db7 100644
--- a/src/nvim/testdir/test55.ok
+++ b/src/nvim/testdir/test55.ok
@@ -101,10 +101,10 @@ caught a:000[3]
 [[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, 'foo', 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, [], {}]
+[-1, 'one', 'two', 'three', 'four', 1.0e-15, 0.22, 7, 9, 12, 18, 22, 255]
+['bar', 'BAR', 'Bar', 'Foo', 'FOO', 'foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
+['bar', 'BAR', 'Bar', 'Foo', 'FOO', 'foo', 'FOOBAR', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
+['BAR', 'Bar', 'FOO', 'FOOBAR', 'Foo', 'bar', 'foo', -1, 0, 0, 0.22, 1.0e-15, 12, 18, 22, 255, 7, 9, [], {}]
 ['aa', 'bb']
 ['aa', 'bb']
 ['', 'aa', 'bb', '']
diff --git a/src/nvim/version.c b/src/nvim/version.c
index f99767cf19..e062970193 100644
--- a/src/nvim/version.c
+++ b/src/nvim/version.c
@@ -244,7 +244,7 @@ static int included_patches[] = {
   //354 NA
   353,
   352,
-  //351,
+  351,
   //350,
   349,
   348,