Improve the lists:merge family of functions

The merge functions no longer accept non-list arguments for merging.
Before, non-list arguments were accepted and returned if they were
the first argument and the second (and third, where applicable,
ie in merge3/3 and umerge3/3) arguments were empty lists. For merge/1
and umerge/1, non-list arguments were accepted if they were the only
element in a list of otherwise empty lists.

The merge functions now also return the second (or third, where
applicable) list immediately and unchanged if the other lists
are empty.
Before, this was only done for the first argument, if the second
(and third, where applicable) list was empty. In all other cases,
the merging process would be performed, unnecessarily.

The same applies for the undocumented reverse-merge functions like
rmerge/2,3, rumerge/2,3 etc.

Co-authored-by: Jan Uhlig <juhlig@hnc-agency.org>

1 files changed, 131 insertions, 0 deletions

diff --git a/lib/stdlib/test/property_test/lists_prop.erl b/lib/stdlib/test/property_test/lists_prop.erl
index 4d5809b262..00b518ff83 100644
--- a/lib/stdlib/test/property_test/lists_prop.erl
+++ b/lib/stdlib/test/property_test/lists_prop.erl
@@ -513,6 +513,23 @@ prop_keymerge() ->
         )
     ).
 
+prop_keymerge_invalid() ->
+    ?FORALL(
+        {N, InList, X, Y},
+        ?LET(
+            N,
+            range(1, 5),
+            ?LET(
+                {L, X, Y},
+                {list(gen_tuple(N, N+3)), non_list(), non_list()},
+                {N, L, X, Y}
+            )
+        ),
+        expect_error(fun lists:keymerge/3, [N, InList, Y]) andalso
+        expect_error(fun lists:keymerge/3, [N, X, InList]) andalso
+        expect_error(fun lists:keymerge/3, [N, X, Y])
+    ).
+
 %% keyreplace/4
 prop_keyreplace() ->
     ?FORALL(
@@ -745,6 +762,17 @@ prop_merge_1() ->
         check_merged(fun erlang:'=<'/2, InLists, lists:merge(InLists))
     ).
 
+prop_merge_1_invalid() ->
+    ?FORALL(
+        InLists,
+        ?LET(
+            {L1, X, L2},
+            {list(oneof([non_list(), gen_list()])), non_list(), list(oneof([non_list(), gen_list()]))},
+            L1 ++ [X|L2]
+        ),
+        expect_error(fun lists:merge/1, [InLists])
+    ).
+
 %% merge/2
 prop_merge_2() ->
     ?FORALL(
@@ -757,6 +785,15 @@ prop_merge_2() ->
         check_merged(fun erlang:'=<'/2, [InList1, InList2], lists:merge(InList1, InList2))
     ).
 
+prop_merge_2_invalid() ->
+    ?FORALL(
+        {InList, X, Y},
+        {gen_list(), non_list(), non_list()},
+        expect_error(fun lists:merge/2, [InList, X]) andalso
+        expect_error(fun lists:merge/2, [X, InList]) andalso
+        expect_error(fun lists:merge/2, [X, Y])
+    ).
+
 %% merge/3
 prop_merge_3() ->
     ?FORALL(
@@ -769,6 +806,15 @@ prop_merge_3() ->
         check_merged(SortFn, [InList1, InList2], lists:merge(SortFn, InList1, InList2))
     ).
 
+prop_merge_3_invalid() ->
+    ?FORALL(
+        {SortFn, InList, X, Y},
+        {gen_ordering_fun(), gen_list(), non_list(), non_list()},
+        expect_error(fun lists:merge/3, [SortFn, InList, Y]) andalso
+        expect_error(fun lists:merge/3, [SortFn, X, InList]) andalso
+        expect_error(fun lists:merge/3, [SortFn, X, Y])
+    ).
+
 %% merge3/3
 prop_merge3() ->
     ?FORALL(
@@ -781,6 +827,18 @@ prop_merge3() ->
         check_merged(fun erlang:'=<'/2, [InList1, InList2, InList3], lists:merge3(InList1, InList2, InList3))
     ).
 
+prop_merge3_invalid() ->
+    ?FORALL(
+        {InList, X, Y, Z},
+        {gen_list(), non_list(), non_list(), non_list()},
+        expect_error(fun lists:merge/3, [InList, InList, Z]) andalso
+        expect_error(fun lists:merge/3, [InList, Y, InList]) andalso
+        expect_error(fun lists:merge/3, [InList, Y, Z]) andalso
+        expect_error(fun lists:merge/3, [X, InList, Z]) andalso
+        expect_error(fun lists:merge/3, [X, Y, InList]) andalso
+        expect_error(fun lists:merge/3, [X, Y, Z])
+    ).
+
 %% min/1
 prop_min() ->
     ?FORALL(
@@ -1132,6 +1190,23 @@ prop_ukeymerge() ->
         )
     ).
 
+prop_ukeymerge_invalid() ->
+    ?FORALL(
+        {N, InList, X, Y},
+        ?LET(
+            N,
+            range(1, 5),
+            ?LET(
+                {L, X, Y},
+                {list(gen_tuple(N, N+3)), non_list(), non_list()},
+                {N, L, X, Y}
+            )
+        ),
+        expect_error(fun lists:ukeymerge/3, [N, InList, Y]) andalso
+        expect_error(fun lists:ukeymerge/3, [N, X, InList]) andalso
+        expect_error(fun lists:ukeymerge/3, [N, X, Y])
+    ).
+
 %% ukeysort/2
 prop_ukeysort() ->
     ?FORALL(
@@ -1156,6 +1231,17 @@ prop_umerge_1() ->
         check_umerged(InLists, lists:umerge(InLists))
     ).
 
+prop_umerge_1_invalid() ->
+    ?FORALL(
+        InList,
+        ?LET(
+            {L1, X, L2},
+	    {list(oneof([non_list(), gen_list()])), non_list(), list(oneof([non_list(), gen_list()]))},
+	    L1 ++ [X|L2]
+        ),
+	expect_error(fun lists:umerge/1, [InList])
+    ).
+
 %% umerge/2
 prop_umerge_2() ->
     ?FORALL(
@@ -1168,6 +1254,15 @@ prop_umerge_2() ->
         check_umerged([InList1, InList2], lists:umerge(InList1, InList2))
     ).
 
+prop_umerge_2_invalid() ->
+    ?FORALL(
+        {InList, X, Y},
+	{gen_list(), non_list(), non_list()},
+	expect_error(fun lists:umerge/2, [InList, Y]) andalso
+	expect_error(fun lists:umerge/2, [X, InList]) andalso
+	expect_error(fun lists:umerge/2, [X, Y])
+    ).
+
 %% umerge/3
 prop_umerge_3() ->
     ?FORALL(
@@ -1180,6 +1275,15 @@ prop_umerge_3() ->
         check_umerged(SortFn, [InList1, InList2], lists:umerge(SortFn, InList1, InList2))
     ).
 
+prop_umerge_3_invalid() ->
+    ?FORALL(
+        {SortFn, InList, X, Y},
+	{gen_ordering_fun(), gen_list(), non_list(), non_list()},
+	expect_error(fun lists:umerge/3, [SortFn, InList, Y]) andalso
+	expect_error(fun lists:umerge/3, [SortFn, X, InList]) andalso
+	expect_error(fun lists:umerge/3, [SortFn, X, Y])
+    ).
+
 %% umerge3/3
 prop_umerge3() ->
     ?FORALL(
@@ -1192,6 +1296,19 @@ prop_umerge3() ->
         check_umerged([InList1, InList2, InList3], lists:umerge3(InList1, InList2, InList3))
     ).
 
+prop_umerge3_invalid() ->
+    ?FORALL(
+        {InList, X, Y, Z},
+	{gen_list(), non_list(), non_list(), non_list()},
+	expect_error(fun lists:umerge3/3, [InList, InList, Z]) andalso
+	expect_error(fun lists:umerge3/3, [InList, Y, InList]) andalso
+	expect_error(fun lists:umerge3/3, [InList, Y, Z]) andalso
+	expect_error(fun lists:umerge3/3, [X, InList, InList]) andalso
+	expect_error(fun lists:umerge3/3, [X, InList, Z]) andalso
+	expect_error(fun lists:umerge3/3, [X, Y, InList]) andalso
+	expect_error(fun lists:umerge3/3, [X, Y, Z])
+    ).
+
 %% uniq/1
 prop_uniq_1() ->
     ?FORALL(
@@ -1530,6 +1647,9 @@ prop_zipwith3_5() ->
 %%% Generators %%%
 %%%%%%%%%%%%%%%%%%
 
+non_list() ->
+	?SUCHTHAT(NonList, gen_any(), not is_list(NonList)).
+
 %% Generator for lists of the given type, folding the given function
 %% over values on the top level as they are generated. The first generated
 %% value serves as the initial accumulator.
@@ -1740,6 +1860,17 @@ gen_ordering_fun() ->
 %%%%%%%%%%%%%%%
 
 %% --------------------------------------------------------------------
+expect_error(Fn, Args) when is_function(Fn, length(Args))->
+    try
+        erlang:apply(Fn, Args)
+    of
+        _ -> false
+    catch
+        error:_ -> true;
+        _:_ -> false
+    end.
+
+%% --------------------------------------------------------------------
 check_appended([], []) ->
     true;
 check_appended([[]|Ls], AL) ->