vim-patch:8.1.2342: random number generator in Vim script is slow

Problem:    Random number generator in Vim script is slow.
Solution:   Add rand() and srand(). (Yasuhiro Matsumoto, closes vim/vim#1277)
https://github.com/vim/vim/commit/06b0b4bc27077013e9b4b48fd1d9b33e543ccf99

Add missing method call usage to builtin.txt.
vim_time and test_settime is N/A.
Add a modeline to test_random.vim.
Use typval_T* over listitem_T* vars so we don't need to use TV_LIST_ITEM_TV all
over the place...
Remove NULL list checks (tv_list_len covers this).

4 files changed, 162 insertions, 0 deletions

diff --git a/runtime/doc/builtin.txt b/runtime/doc/builtin.txt
index 4153c1c9d8..35beb97518 100644
--- a/runtime/doc/builtin.txt
+++ b/runtime/doc/builtin.txt
@@ -325,6 +325,7 @@ pumvisible()			Number	whether popup menu is visible
 pyeval({expr})			any	evaluate |Python| expression
 py3eval({expr})			any	evaluate |python3| expression
 pyxeval({expr})			any	evaluate |python_x| expression
+rand([{expr}])			Number	get pseudo-random number
 range({expr} [, {max} [, {stride}]])
 				List	items from {expr} to {max}
 readdir({dir} [, {expr}])	List	file names in {dir} selected by {expr}
@@ -441,6 +442,7 @@ spellsuggest({word} [, {max} [, {capital}]])
 split({expr} [, {pat} [, {keepempty}]])
 				List	make |List| from {pat} separated {expr}
 sqrt({expr})			Float	square root of {expr}
+srand([{expr}])			List	get seed for |rand()|
 stdioopen({dict})		Number	open stdio in a headless instance.
 stdpath({what})			String/List  returns the standard path(s) for {what}
 str2float({expr} [, {quoted}])	Float	convert String to Float
@@ -5530,6 +5532,22 @@ range({expr} [, {max} [, {stride}]])				*range()*
 		Can also be used as a |method|: >
 			GetExpr()->range()
 <
+rand([{expr}])						*rand()*
+		Return a pseudo-random Number generated with an xorshift
+		algorithm using seed {expr}.  {expr} can be initialized by
+		|srand()| and will be updated by rand().
+		If {expr} is omitted, an internal seed value is used and
+		updated.
+
+		Examples: >
+			:echo rand()
+			:let seed = srand()
+			:echo rand(seed)
+			:echo rand(seed)
+<
+		Can also be used as a |method|: >
+			seed->rand()
+<
 							*readdir()*
 readdir({directory} [, {expr}])
 		Return a list with file and directory names in {directory}.
@@ -7178,6 +7196,22 @@ sqrt({expr})						*sqrt()*
 		Can also be used as a |method|: >
 			Compute()->sqrt()
 
+srand([{expr}])						*srand()*
+		Initialize seed used by |rand()|:
+		- If {expr} is not given, seed values are initialized by
+		  time(NULL) a.k.a. epoch time.
+		- If {expr} is given, return seed values which x element is
+		  {expr}.  This is useful for testing or when a predictable
+		  sequence is expected.
+
+		Examples: >
+			:let seed = srand()
+			:let seed = srand(userinput)
+			:echo rand(seed)
+<
+		Can also be used as a |method|: >
+			userinput->srand()
+
 stdioopen({opts})			 *stdioopen()*
 		With |--headless| this opens stdin and stdout as a |channel|.
 		May be called only once. See |channel-stdio|. stderr is not
diff --git a/src/nvim/eval.lua b/src/nvim/eval.lua
index 18967b80f2..ef2b8a0cc0 100644
--- a/src/nvim/eval.lua
+++ b/src/nvim/eval.lua
@@ -273,6 +273,7 @@ return {
     pyeval={args=1, base=1, func="f_py3eval"},
     pyxeval={args=1, base=1, func="f_py3eval"},
     perleval={args=1, base=1},
+    rand={args={0, 1}, base=1},
     range={args={1, 3}, base=1},
     readdir={args={1, 2}, base=1},
     readfile={args={1, 3}, base=1},
@@ -348,6 +349,7 @@ return {
     spellsuggest={args={1, 3}, base=1},
     split={args={1, 3}, base=1},
     sqrt={args=1, base=1, func="float_op_wrapper", data="&sqrt"},
+    srand={args={0, 1}, base=1},
     stdpath={args=1},
     str2float={args=1, base=1},
     str2list={args={1, 2}, base=1},
diff --git a/src/nvim/eval/funcs.c b/src/nvim/eval/funcs.c
index 50030f2994..96d8c93db3 100644
--- a/src/nvim/eval/funcs.c
+++ b/src/nvim/eval/funcs.c
@@ -22,6 +22,7 @@
 #include "nvim/eval/encode.h"
 #include "nvim/eval/executor.h"
 #include "nvim/eval/funcs.h"
+#include "nvim/eval/typval.h"
 #include "nvim/eval/userfunc.h"
 #include "nvim/ex_cmds2.h"
 #include "nvim/ex_docmd.h"
@@ -6978,6 +6979,81 @@ static void f_py3eval(typval_T *argvars, typval_T *rettv, FunPtr fptr)
   script_host_eval("python3", argvars, rettv);
 }
 
+/// "rand()" function
+static void f_rand(typval_T *argvars, typval_T *rettv, FunPtr fptr)
+{
+  uint32_t w;
+#define SHUFFLE_XORSHIFT128 \
+  const uint32_t t = x ^ (x << 11); \
+  x = y; \
+  y = z; \
+  z = w; \
+  w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
+
+  if (argvars[0].v_type == VAR_UNKNOWN) {
+    static bool rand_seed_initialized = false;
+    static uint32_t xyzw[4] = { 123456789, 362436069, 521288629, 88675123 };
+
+    // When argument is not given, return random number initialized
+    // statically.
+    if (!rand_seed_initialized) {
+      xyzw[0] = time(NULL);
+      rand_seed_initialized = true;
+    }
+
+    uint32_t x = xyzw[0];
+    uint32_t y = xyzw[1];
+    uint32_t z = xyzw[2];
+    w = xyzw[3];
+    SHUFFLE_XORSHIFT128;
+    xyzw[0] = x;
+    xyzw[1] = y;
+    xyzw[2] = z;
+    xyzw[3] = w;
+  } else if (argvars[0].v_type == VAR_LIST) {
+    list_T *const l = argvars[0].vval.v_list;
+    if (tv_list_len(l) != 4) {
+      goto theend;
+    }
+
+    typval_T *const tvx = TV_LIST_ITEM_TV(tv_list_find(l, 0L));
+    typval_T *const tvy = TV_LIST_ITEM_TV(tv_list_find(l, 1L));
+    typval_T *const tvz = TV_LIST_ITEM_TV(tv_list_find(l, 2L));
+    typval_T *const tvw = TV_LIST_ITEM_TV(tv_list_find(l, 3L));
+    if (tvx->v_type != VAR_NUMBER) {
+      goto theend;
+    }
+    if (tvy->v_type != VAR_NUMBER) {
+      goto theend;
+    }
+    if (tvz->v_type != VAR_NUMBER) {
+      goto theend;
+    }
+    if (tvw->v_type != VAR_NUMBER) {
+      goto theend;
+    }
+    uint32_t x = tvx->vval.v_number;
+    uint32_t y = tvy->vval.v_number;
+    uint32_t z = tvz->vval.v_number;
+    w = tvw->vval.v_number;
+    SHUFFLE_XORSHIFT128;
+    tvx->vval.v_number = (varnumber_T)x;
+    tvy->vval.v_number = (varnumber_T)y;
+    tvz->vval.v_number = (varnumber_T)z;
+    tvw->vval.v_number = (varnumber_T)w;
+  } else {
+    goto theend;
+  }
+
+#undef SHUFFLE_XORSHIFT128
+  rettv->v_type = VAR_NUMBER;
+  rettv->vval.v_number = (varnumber_T)w;
+  return;
+
+theend:
+  semsg(_(e_invarg2), tv_get_string(&argvars[0]));
+}
+
 /// "perleval()" function
 static void f_perleval(typval_T *argvars, typval_T *rettv, FunPtr fptr)
 {
@@ -10449,6 +10525,25 @@ static void f_stdpath(typval_T *argvars, typval_T *rettv, FunPtr fptr)
   }
 }
 
+/// "srand()" function
+static void f_srand(typval_T *argvars, typval_T *rettv, FunPtr fptr)
+{
+  tv_list_alloc_ret(rettv, 4);
+  if (argvars[0].v_type == VAR_UNKNOWN) {
+    tv_list_append_number(rettv->vval.v_list, (varnumber_T)time(NULL));
+  } else {
+    bool error = false;
+    const uint32_t x = tv_get_number_chk(&argvars[0], &error);
+    if (error) {
+      return;
+    }
+    tv_list_append_number(rettv->vval.v_list, x);
+  }
+  tv_list_append_number(rettv->vval.v_list, 362436069);
+  tv_list_append_number(rettv->vval.v_list, 521288629);
+  tv_list_append_number(rettv->vval.v_list, 88675123);
+}
+
 /*
  * "str2float()" function
  */
diff --git a/src/nvim/testdir/test_random.vim b/src/nvim/testdir/test_random.vim
new file mode 100644
index 0000000000..bde034a96c
--- /dev/null
+++ b/src/nvim/testdir/test_random.vim
@@ -0,0 +1,31 @@
+" Tests for srand() and rand()
+
+func Test_Rand()
+  let r = srand(123456789)
+  call assert_equal([123456789, 362436069, 521288629, 88675123], r)
+  call assert_equal(3701687786, rand(r))
+  call assert_equal(458299110, rand(r))
+  call assert_equal(2500872618, rand(r))
+  call assert_equal(3633119408, rand(r))
+  call assert_equal(516391518, rand(r))
+
+  " Nvim does not support test_settime
+  " call test_settime(12341234)
+  " let s = srand()
+  " call assert_equal(s, srand())
+  " call test_settime(12341235)
+  " call assert_notequal(s, srand())
+
+  call srand()
+  let v = rand()
+  call assert_notequal(v, rand())
+
+  call assert_fails('echo srand([1])', 'E745:')
+  call assert_fails('echo rand([1, 2, 3])', 'E475:')
+  call assert_fails('echo rand([[1], 2, 3, 4])', 'E475:')
+  call assert_fails('echo rand([1, [2], 3, 4])', 'E475:')
+  call assert_fails('echo rand([1, 2, [3], 4])', 'E475:')
+  call assert_fails('echo rand([1, 2, 3, [4]])', 'E475:')
+endfunc
+
+" vim: shiftwidth=2 sts=2 expandtab