Skip to content

Commit 077a1e6

Browse files
brammoolbrammool
committed
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 #3676)
1 parent ec98e93 commit 077a1e6

File tree

8 files changed

+198
-1
lines changed

8 files changed

+198
-1
lines changed

‎runtime/doc/eval.txt‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2451,6 +2451,7 @@ finddir({name} [, {path} [, {count}]])
24512451
String find directory {name} in {path}
24522452
findfile({name} [, {path} [, {count}]])
24532453
String find file {name} in {path}
2454+
flatten({list} [, {maxdepth}]) List flatten {list} up to {maxdepth} levels
24542455
float2nr({expr}) Number convert Float {expr} to a Number
24552456
floor({expr}) Float round {expr} down
24562457
fmod({expr1}, {expr2}) Float remainder of {expr1} / {expr2}
@@ -4514,6 +4515,25 @@ findfile({name} [, {path} [, {count}]]) *findfile()*
45144515
Can also be used as a |method|: >
45154516
GetName()->findfile()
45164517

4518+
flatten({list} [, {maxdepth}]) *flatten()*
4519+
Flatten {list} up to {maxdepth} levels. Without {maxdepth}
4520+
the result is a |List| without nesting, as if {maxdepth} is
4521+
a very large number.
4522+
The {list} is changed in place, make a copy first if you do
4523+
not want that.
4524+
*E964*
4525+
{maxdepth} means how deep in nested lists changes are made.
4526+
{list} is not modified when {maxdepth} is 0.
4527+
{maxdepth} must be positive number.
4528+
4529+
If there is an error the number zero is returned.
4530+
4531+
Example: >
4532+
:echo flatten([1, [2, [3, 4]], 5])
4533+
< [1, 2, 3, 4, 5] >
4534+
:echo flatten([1, [2, [3, 4]], 5], 1)
4535+
< [1, 2, [3, 4], 5]
4536+
45174537
float2nr({expr}) *float2nr()*
45184538
Convert {expr} to a Number by omitting the part after the
45194539
decimal point.

‎runtime/doc/usr_41.txt‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -650,6 +650,7 @@ List manipulation: *list-functions*
650650
min() minimum value in a List
651651
count() count number of times a value appears in a List
652652
repeat() repeat a List multiple times
653+
flatten() flatten a List
653654

654655
Dictionary manipulation: *dict-functions*
655656
get() get an entry without an error for a wrong key

‎src/evalfunc.c‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -541,6 +541,7 @@ static funcentry_T global_functions[] =
541541
{"filter", 2, 2, FEARG_1, ret_any, f_filter},
542542
{"finddir", 1, 3, FEARG_1, ret_string, f_finddir},
543543
{"findfile", 1, 3, FEARG_1, ret_string, f_findfile},
544+
{"flatten", 1, 2, FEARG_1, ret_list_any, f_flatten},
544545
{"float2nr", 1, 1, FEARG_1, ret_number, FLOAT_FUNC(f_float2nr)},
545546
{"floor", 1, 1, FEARG_1, ret_float, FLOAT_FUNC(f_floor)},
546547
{"fmod", 2, 2, FEARG_1, ret_float, FLOAT_FUNC(f_fmod)},

‎src/list.c‎

Lines changed: 89 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -730,6 +730,95 @@ list_insert(list_T *l, listitem_T *ni, listitem_T *item)
730730
}
731731
}
732732

733+
/*
734+
* Flatten "list" to depth "maxdepth".
735+
* It does nothing if "maxdepth" is 0.
736+
* Returns FAIL when out of memory.
737+
*/
738+
static int
739+
list_flatten(list_T *list, long maxdepth)
740+
{
741+
listitem_T *item;
742+
int n;
743+
744+
if (maxdepth == 0)
745+
return OK;
746+
CHECK_LIST_MATERIALIZE(list);
747+
748+
n = 0;
749+
item = list->lv_first;
750+
while (item != NULL)
751+
{
752+
fast_breakcheck();
753+
if (got_int)
754+
return FAIL;
755+
756+
if (item->li_tv.v_type == VAR_LIST)
757+
{
758+
listitem_T *next = item->li_next;
759+
760+
vimlist_remove(list, item, item);
761+
if (list_extend(list, item->li_tv.vval.v_list, next) == FAIL)
762+
return FAIL;
763+
764+
if (item->li_prev == NULL)
765+
item = list->lv_first;
766+
else
767+
item = item->li_prev->li_next;
768+
769+
if (++n >= maxdepth)
770+
{
771+
n = 0;
772+
item = next;
773+
}
774+
}
775+
else
776+
{
777+
n = 0;
778+
item = item->li_next;
779+
}
780+
}
781+
782+
return OK;
783+
}
784+
785+
/*
786+
* "flatten(list[, {maxdepth}])" function
787+
*/
788+
void
789+
f_flatten(typval_T *argvars, typval_T *rettv)
790+
{
791+
list_T *l;
792+
long maxdepth;
793+
int error = FALSE;
794+
795+
if (argvars[0].v_type != VAR_LIST)
796+
{
797+
semsg(_(e_listarg), "flatten()");
798+
return;
799+
}
800+
801+
if (argvars[1].v_type == VAR_UNKNOWN)
802+
maxdepth = 999999;
803+
else
804+
{
805+
maxdepth = (long)tv_get_number_chk(&argvars[1], &error);
806+
if (error)
807+
return;
808+
if (maxdepth < 0)
809+
{
810+
emsg(_("E900: maxdepth must be non-negative number"));
811+
return;
812+
}
813+
}
814+
815+
l = argvars[0].vval.v_list;
816+
if (l != NULL && !var_check_lock(l->lv_lock,
817+
(char_u *)N_("flatten() argument"), TRUE)
818+
&& list_flatten(l, maxdepth) == OK)
819+
copy_tv(&argvars[0], rettv);
820+
}
821+
733822
/*
734823
* Extend "l1" with "l2".
735824
* If "bef" is NULL append at the end, otherwise insert before this item.

‎src/proto/list.pro‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -30,14 +30,15 @@ int list_append_string(list_T *l, char_u *str, int len);
3030
int list_append_number(list_T *l, varnumber_T n);
3131
int list_insert_tv(list_T *l, typval_T *tv, listitem_T *item);
3232
void list_insert(list_T *l, listitem_T *ni, listitem_T *item);
33+
void f_flatten(typval_T *argvars, typval_T *rettv);
3334
int list_extend(list_T *l1, list_T *l2, listitem_T *bef);
3435
int list_concat(list_T *l1, list_T *l2, typval_T *tv);
3536
list_T *list_copy(list_T *orig, int deep, int copyID);
3637
void vimlist_remove(list_T *l, listitem_T *item, listitem_T *item2);
3738
char_u *list2string(typval_T *tv, int copyID, int restore_copyID);
3839
int list_join(garray_T *gap, list_T *l, char_u *sep, int echo_style, int restore_copyID, int copyID);
3940
void f_join(typval_T *argvars, typval_T *rettv);
40-
int get_list_tv(char_u **arg, typval_T *rettv, int evaluate, int do_error);
41+
int get_list_tv(char_u **arg, typval_T *rettv, int flags, int do_error);
4142
int write_list(FILE *fd, list_T *list, int binary);
4243
void init_static_list(staticList10_T *sl);
4344
void f_list2str(typval_T *argvars, typval_T *rettv);

‎src/testdir/Make_all.mak‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -135,6 +135,7 @@ NEW_TESTS = \
135135
test_find_complete \
136136
test_findfile \
137137
test_fixeol \
138+
test_flatten \
138139
test_float_func \
139140
test_fnameescape \
140141
test_fnamemodify \
@@ -373,6 +374,7 @@ NEW_TESTS_RES = \
373374
test_find_complete.res \
374375
test_findfile.res \
375376
test_fixeol.res \
377+
test_flatten.res \
376378
test_float_func.res \
377379
test_fnameescape.res \
378380
test_fold.res \

‎src/testdir/test_flatten.vim‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,81 @@
1+
" Test for flatting list.
2+
func Test_flatten()
3+
call assert_fails('call flatten(1)', 'E686:')
4+
call assert_fails('call flatten({})', 'E686:')
5+
call assert_fails('call flatten("string")', 'E686:')
6+
call assert_fails('call flatten([], [])', 'E745:')
7+
call assert_fails('call flatten([], -1)', 'E900: maxdepth')
8+
9+
call assert_equal([], flatten([]))
10+
call assert_equal([], flatten([[]]))
11+
call assert_equal([], flatten([[[]]]))
12+
13+
call assert_equal([1, 2, 3], flatten([1, 2, 3]))
14+
call assert_equal([1, 2, 3], flatten([[1], 2, 3]))
15+
call assert_equal([1, 2, 3], flatten([1, [2], 3]))
16+
call assert_equal([1, 2, 3], flatten([1, 2, [3]]))
17+
call assert_equal([1, 2, 3], flatten([[1], [2], 3]))
18+
call assert_equal([1, 2, 3], flatten([1, [2], [3]]))
19+
call assert_equal([1, 2, 3], flatten([[1], 2, [3]]))
20+
call assert_equal([1, 2, 3], flatten([[1], [2], [3]]))
21+
22+
call assert_equal([1, 2, 3], flatten([[1, 2, 3], []]))
23+
call assert_equal([1, 2, 3], flatten([[], [1, 2, 3]]))
24+
call assert_equal([1, 2, 3], flatten([[1, 2], [], [3]]))
25+
call assert_equal([1, 2, 3], flatten([[], [1, 2, 3], []]))
26+
call assert_equal([1, 2, 3, 4], flatten(range(1, 4)))
27+
28+
" example in the help
29+
call assert_equal([1, 2, 3, 4, 5], flatten([1, [2, [3, 4]], 5]))
30+
call assert_equal([1, 2, [3, 4], 5], flatten([1, [2, [3, 4]], 5], 1))
31+
32+
call assert_equal([0, [1], 2, [3], 4], flatten([[0, [1]], 2, [[3], 4]], 1))
33+
call assert_equal([1, 2, 3], flatten([[[[1]]], [2], [3]], 3))
34+
call assert_equal([[1], [2], [3]], flatten([[[1], [2], [3]]], 1))
35+
call assert_equal([[1]], flatten([[1]], 0))
36+
37+
" Make it flatten if the given maxdepth is larger than actual depth.
38+
call assert_equal([1, 2, 3], flatten([[1, 2, 3]], 1))
39+
call assert_equal([1, 2, 3], flatten([[1, 2, 3]], 2))
40+
41+
let l:list = [[1], [2], [3]]
42+
call assert_equal([1, 2, 3], flatten(l:list))
43+
call assert_equal([1, 2, 3], l:list)
44+
45+
" Tests for checking reference counter works well.
46+
let l:x = {'foo': 'bar'}
47+
call assert_equal([1, 2, l:x, 3], flatten([1, [2, l:x], 3]))
48+
call test_garbagecollect_now()
49+
call assert_equal('bar', l:x.foo)
50+
51+
let l:list = [[1], [2], [3]]
52+
call assert_equal([1, 2, 3], flatten(l:list))
53+
call test_garbagecollect_now()
54+
call assert_equal([1, 2, 3], l:list)
55+
56+
" Tests for checking circular reference list can be flatten.
57+
let l:x = [1]
58+
let l:y = [x]
59+
let l:z = flatten(l:y)
60+
call assert_equal([1], l:z)
61+
call test_garbagecollect_now()
62+
let l:x[0] = 2
63+
call assert_equal([2], l:x)
64+
call assert_equal([1], l:z) " NOTE: primitive types are copied.
65+
call assert_equal([1], l:y)
66+
67+
let l:x = [2]
68+
let l:y = [1, [l:x], 3] " [1, [[2]], 3]
69+
let l:z = flatten(l:y, 1)
70+
call assert_equal([1, [2], 3], l:z)
71+
let l:x[0] = 9
72+
call assert_equal([1, [9], 3], l:z) " Reference to l:x is kept.
73+
call assert_equal([1, [9], 3], l:y)
74+
75+
let l:x = [1]
76+
let l:y = [2]
77+
call add(x, y) " l:x = [1, [2]]
78+
call add(y, x) " l:y = [2, [1, [...]]]
79+
call assert_equal([1, 2, 1, 2], flatten(l:x, 2))
80+
call assert_equal([2, l:x], l:y)
81+
endfunc

‎src/version.c‎

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -754,6 +754,8 @@ static char *(features[]) =
754754

755755
static int included_patches[] =
756756
{ /* Add new patch number below this line */
757+
/**/
758+
935,
757759
/**/
758760
934,
759761
/**/

0 commit comments

Comments
 (0)