patch 8.1.2342: random number generator in Vim script is slowv8.1.2342

Problem:    Random number generator in Vim script is slow.
Solution:   Add rand() and srand(). (Yasuhiro Matsumoto, closes #1277)

5 files changed, 163 insertions, 0 deletions

diff --git a/runtime/doc/eval.txt b/runtime/doc/eval.txt
index a6f56eb916..5936437af1 100644
--- a/runtime/doc/eval.txt
+++ b/runtime/doc/eval.txt
@@ -2648,6 +2648,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}
@@ -2761,6 +2762,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()|
 state([{what}])			String	current state of Vim
 str2float({expr})		Float	convert String to Float
 str2list({expr} [, {utf8}])	List	convert each character of {expr} to
@@ -7637,6 +7639,20 @@ 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)
+<
 							*readdir()*
 readdir({directory} [, {expr}])
 		Return a list with file and directory names in {directory}.
@@ -9130,6 +9146,19 @@ sqrt({expr})						*sqrt()*
 		{only available when compiled with the |+float| feature}
 
 
+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)
+
 state([{what}])						*state()*
 		Return a string which contains characters indicating the
 		current state.  Mostly useful in callbacks that want to do
diff --git a/src/evalfunc.c b/src/evalfunc.c
index 075ef1bf1b..a3e5b3e380 100644
--- a/src/evalfunc.c
+++ b/src/evalfunc.c
@@ -169,6 +169,7 @@ static void f_pyeval(typval_T *argvars, typval_T *rettv);
 #if defined(FEAT_PYTHON) || defined(FEAT_PYTHON3)
 static void f_pyxeval(typval_T *argvars, typval_T *rettv);
 #endif
+static void f_rand(typval_T *argvars, typval_T *rettv);
 static void f_range(typval_T *argvars, typval_T *rettv);
 static void f_reg_executing(typval_T *argvars, typval_T *rettv);
 static void f_reg_recording(typval_T *argvars, typval_T *rettv);
@@ -225,6 +226,7 @@ static void f_spellsuggest(typval_T *argvars, typval_T *rettv);
 static void f_split(typval_T *argvars, typval_T *rettv);
 #ifdef FEAT_FLOAT
 static void f_sqrt(typval_T *argvars, typval_T *rettv);
+static void f_srand(typval_T *argvars, typval_T *rettv);
 static void f_str2float(typval_T *argvars, typval_T *rettv);
 #endif
 static void f_str2list(typval_T *argvars, typval_T *rettv);
@@ -634,6 +636,7 @@ static funcentry_T global_functions[] =
 #if defined(FEAT_PYTHON) || defined(FEAT_PYTHON3)
     {"pyxeval",		1, 1, FEARG_1,	  f_pyxeval},
 #endif
+    {"rand",		0, 1, FEARG_1,	  f_rand},
     {"range",		1, 3, FEARG_1,	  f_range},
     {"readdir",		1, 2, FEARG_1,	  f_readdir},
     {"readfile",	1, 3, FEARG_1,	  f_readfile},
@@ -725,6 +728,7 @@ static funcentry_T global_functions[] =
     {"split",		1, 3, FEARG_1,	  f_split},
 #ifdef FEAT_FLOAT
     {"sqrt",		1, 1, FEARG_1,	  f_sqrt},
+    {"srand",		0, 1, FEARG_1,	  f_srand},
 #endif
     {"state",		0, 1, FEARG_1,	  f_state},
 #ifdef FEAT_FLOAT
@@ -5129,6 +5133,79 @@ f_pyxeval(typval_T *argvars, typval_T *rettv)
 #endif
 
 /*
+ * "rand()" function
+ */
+    static void
+f_rand(typval_T *argvars, typval_T *rettv)
+{
+    list_T	*l = NULL;
+    UINT32_T	x, y, z, w, t;
+    static int	rand_seed_initialized = FALSE;
+    static UINT32_T xyzw[4] = {123456789, 362436069, 521288629, 88675123};
+
+#define SHUFFLE_XORSHIFT128 \
+	t = x ^ (x << 11); \
+	x = y; y = z; z = w; \
+	w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
+
+    if (argvars[0].v_type == VAR_UNKNOWN)
+    {
+	// When argument is not given, return random number initialized
+	// statically.
+	if (!rand_seed_initialized)
+	{
+	    xyzw[0] = (varnumber_T)time(NULL);
+	    rand_seed_initialized = TRUE;
+	}
+
+	x = xyzw[0];
+	y = xyzw[1];
+	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)
+    {
+	listitem_T	*lx, *ly, *lz, *lw;
+
+	l = argvars[0].vval.v_list;
+	if (list_len(l) != 4)
+	    goto theend;
+
+	lx = list_find(l, 0L);
+	ly = list_find(l, 1L);
+	lz = list_find(l, 2L);
+	lw = list_find(l, 3L);
+	if (lx->li_tv.v_type != VAR_NUMBER) goto theend;
+	if (ly->li_tv.v_type != VAR_NUMBER) goto theend;
+	if (lz->li_tv.v_type != VAR_NUMBER) goto theend;
+	if (lw->li_tv.v_type != VAR_NUMBER) goto theend;
+	x = (UINT32_T)lx->li_tv.vval.v_number;
+	y = (UINT32_T)ly->li_tv.vval.v_number;
+	z = (UINT32_T)lz->li_tv.vval.v_number;
+	w = (UINT32_T)lw->li_tv.vval.v_number;
+	SHUFFLE_XORSHIFT128;
+	lx->li_tv.vval.v_number = (varnumber_T)x;
+	ly->li_tv.vval.v_number = (varnumber_T)y;
+	lz->li_tv.vval.v_number = (varnumber_T)z;
+	lw->li_tv.vval.v_number = (varnumber_T)w;
+    }
+    else
+	goto theend;
+
+    rettv->v_type = VAR_NUMBER;
+    rettv->vval.v_number = (varnumber_T)w;
+    return;
+
+theend:
+    semsg(_(e_invarg2), tv_get_string(&argvars[0]));
+}
+
+/*
  * "range()" function
  */
     static void
@@ -7013,6 +7090,31 @@ f_sqrt(typval_T *argvars, typval_T *rettv)
 }
 
 /*
+ * "srand()" function
+ */
+    static void
+f_srand(typval_T *argvars, typval_T *rettv)
+{
+    if (rettv_list_alloc(rettv) == FAIL)
+	return;
+    if (argvars[0].v_type == VAR_UNKNOWN)
+	list_append_number(rettv->vval.v_list, (varnumber_T)vim_time());
+    else
+    {
+	int	    error = FALSE;
+	UINT32_T    x = (UINT32_T)tv_get_number_chk(&argvars[0], &error);
+
+	if (error)
+	    return;
+
+	list_append_number(rettv->vval.v_list, x);
+    }
+    list_append_number(rettv->vval.v_list, 362436069);
+    list_append_number(rettv->vval.v_list, 521288629);
+    list_append_number(rettv->vval.v_list, 88675123);
+}
+
+/*
  * "str2float()" function
  */
     static void
diff --git a/src/testdir/Make_all.mak b/src/testdir/Make_all.mak
index ac254202a8..f6d6c17176 100644
--- a/src/testdir/Make_all.mak
+++ b/src/testdir/Make_all.mak
@@ -211,6 +211,7 @@ NEW_TESTS = \
 	test_pyx3 \
 	test_quickfix \
 	test_quotestar \
+	test_random \
 	test_recover \
 	test_regex_char_classes \
 	test_regexp_latin \
@@ -403,6 +404,7 @@ NEW_TESTS_RES = \
 	test_pyx3.res \
 	test_quickfix.res \
 	test_quotestar.res \
+	test_random.res \
 	test_regex_char_classes.res \
 	test_registers.res \
 	test_restricted.res \
diff --git a/src/testdir/test_random.vim b/src/testdir/test_random.vim
new file mode 100644
index 0000000000..381475a43f
--- /dev/null
+++ b/src/testdir/test_random.vim
@@ -0,0 +1,28 @@
+" 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))
+
+  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
diff --git a/src/version.c b/src/version.c
index bbc71be6e8..f88d0e9adc 100644
--- a/src/version.c
+++ b/src/version.c
@@ -738,6 +738,8 @@ static char *(features[]) =
 static int included_patches[] =
 {   /* Add new patch number below this line */
 /**/
+    2342,
+/**/
     2341,
 /**/
     2340,