vim-patch:8.2.0935: flattening a list with existing code is slow

Problem:    Flattening a list with existing code is slow.
Solution:   Add flatten(). (Mopp, closes vim/vim#3676)
https://github.com/vim/vim/commit/077a1e670ad69ef4cefc22103ca6635bd269e764

2 files changed, 83 insertions, 0 deletions

diff --git a/src/nvim/eval/funcs.c b/src/nvim/eval/funcs.c
index 99014d1a09..95686b97bf 100644
--- a/src/nvim/eval/funcs.c
+++ b/src/nvim/eval/funcs.c
@@ -2160,6 +2160,42 @@ static void f_expandcmd(typval_T *argvars, typval_T *rettv, FunPtr fptr)
   rettv->vval.v_string = cmdstr;
 }
 
+
+/// "flatten(list[, {maxdepth}])" function
+static void f_flatten(typval_T *argvars, typval_T *rettv, FunPtr fptr)
+{
+  list_T *list;
+  long maxdepth;
+  bool error = false;
+
+  if (argvars[0].v_type != VAR_LIST) {
+    EMSG2(_(e_listarg), "flatten()");
+    return;
+  }
+
+  if (argvars[1].v_type == VAR_UNKNOWN) {
+    maxdepth = 999999;
+  } else {
+    maxdepth = (long)tv_get_number_chk(&argvars[1], &error);
+    if (error) {
+      return;
+    }
+    if (maxdepth < 0) {
+      EMSG(_("E900: maxdepth must be non-negative number"));
+      return;
+    }
+  }
+
+  list = argvars[0].vval.v_list;
+  if (list != NULL
+      && !tv_check_lock(tv_list_locked(list),
+                        N_("flatten() argument"),
+                        TV_TRANSLATE)
+      && tv_list_flatten(list, maxdepth) == OK) {
+    tv_copy(&argvars[0], rettv);
+  }
+}
+
 /*
  * "extend(list, list [, idx])" function
  * "extend(dict, dict [, action])" function
diff --git a/src/nvim/eval/typval.c b/src/nvim/eval/typval.c
index 89ca2db59b..576948f052 100644
--- a/src/nvim/eval/typval.c
+++ b/src/nvim/eval/typval.c
@@ -640,6 +640,53 @@ tv_list_copy_error:
   return NULL;
 }
 
+/// Flatten "list" in place to depth "maxdepth".
+/// Does nothing if "maxdepth" is 0.
+///
+/// @param[in] list       List to flatten
+/// @param[in] maxdepth   Maximum depth that will be flattened
+///
+/// @return OK or FAIL
+int tv_list_flatten(list_T *list, long maxdepth)
+  FUNC_ATTR_WARN_UNUSED_RESULT
+{
+  listitem_T *item;
+  int n;
+  if (maxdepth == 0) {
+    return OK;
+  }
+
+  n = 0;
+  item = list->lv_first;
+  while (item != NULL) {
+    fast_breakcheck();
+    if (got_int) {
+      return FAIL;
+    }
+    if (item->li_tv.v_type == VAR_LIST) {
+      listitem_T *next = item->li_next;
+
+      tv_list_drop_items(list, item, item);
+      tv_list_extend(list, item->li_tv.vval.v_list, next);
+
+      if (item->li_prev == NULL) {
+        item = list->lv_first;
+      } else {
+        item = item->li_prev->li_next;
+      }
+
+      if (++n >= maxdepth) {
+        n = 0;
+        item = next;
+      }
+    } else {
+      n = 0;
+      item = item->li_next;
+    }
+  }
+  return OK;
+}
+
 /// Extend first list with the second
 ///
 /// @param[out]  l1  List to extend.