diff options
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/stdlib/doc/src/lists.xml | 6 | ||||
| -rw-r--r-- | lib/stdlib/test/lists_SUITE.erl | 42 |
2 files changed, 42 insertions, 6 deletions
diff --git a/lib/stdlib/doc/src/lists.xml b/lib/stdlib/doc/src/lists.xml index 89ba5238b5..4a4c170bba 100644 --- a/lib/stdlib/doc/src/lists.xml +++ b/lib/stdlib/doc/src/lists.xml @@ -708,12 +708,6 @@ splitwith(Pred, List) -> > <input>lists:subtract("123212", "212").</input> "312".</pre> <p><c>lists:subtract(A, B)</c> is equivalent to <c>A -- B</c>.</p> - <warning><p>The complexity of <c>lists:subtract(A, B)</c> is proportional - to <c>length(A)*length(B)</c>, meaning that it will be very slow if - both <c>A</c> and <c>B</c> are long lists. - (Using ordered lists and - <seealso marker="ordsets#subtract/2">ordsets:subtract/2</seealso> - is a much better choice if both lists are long.)</p></warning> </desc> </func> <func> diff --git a/lib/stdlib/test/lists_SUITE.erl b/lib/stdlib/test/lists_SUITE.erl index a0f7fd2744..21b2dd1777 100644 --- a/lib/stdlib/test/lists_SUITE.erl +++ b/lib/stdlib/test/lists_SUITE.erl @@ -2692,6 +2692,13 @@ subtract(Config) when is_list(Config) -> ?line {'EXIT',_} = (catch sub([a|b], [])), ?line {'EXIT',_} = (catch sub([a|b], [a])), + %% Trapping, both crashing and otherwise. + [sub_trapping(N) || N <- lists:seq(0, 18)], + + %% The current implementation chooses which algorithm to use based on + %% certain thresholds, and we need proper coverage for all corner cases. + [sub_thresholds(N) || N <- lists:seq(0, 32)], + ok. sub_non_matching(A, B) -> @@ -2701,6 +2708,41 @@ sub(A, B) -> Res = A -- B, Res = lists:subtract(A, B). +sub_trapping(N) -> + List = lists:duplicate(N + (1 bsl N), gurka), + ImproperList = List ++ crash, + + {'EXIT',_} = (catch sub_trapping_1(ImproperList, [])), + {'EXIT',_} = (catch sub_trapping_1(List, ImproperList)), + + List = List -- lists:duplicate(N + (1 bsl N), gaffel), + ok = sub_trapping_1(List, []). + +sub_trapping_1([], _) -> ok; +sub_trapping_1(L, R) -> sub_trapping_1(L -- R, [gurka | R]). + +sub_thresholds(N) -> + %% This needs to be long enough to cause trapping. + OtherLen = 1 bsl 18, + Other = lists:seq(0, OtherLen - 1), + + Disjoint = lists:seq(-N, -1), + Subset = lists:seq(1, N), + + %% LHS is disjoint from RHS, so all elements must be retained. + Disjoint = Disjoint -- Other, + + %% LHS is covered by RHS, so all elements must be removed. + [] = Subset -- Other, + + %% RHS is disjoint from LHS, so all elements must be retained. + Other = Other -- Disjoint, + + %% RHS is covered by LHS, so N elements must be removed. + N = OtherLen - length(Other -- Subset), + + ok. + %% Test lists:droplast/1 droplast(Config) when is_list(Config) -> ?line [] = lists:droplast([x]), |