Merge branch 'egil/maps/hamt/OTP-12585'

* egil/maps/hamt/OTP-12585: (113 commits)
  erts: Fix bug in ESTACK and WSTACK
  kernel: Add spec for erts_debug:map_info/1
  mnesia: Update mnesia tests to reflect new ETS hash
  erts: Ensure maps uses _rel functions in halfword
  erts: Do not treat errors as fatal in erl_printf_term
  erts: Update preloaded erts_internal.beam
  erts: Add map decomposition wrappers
  erts: Ensure halfword has correct temp-heap for maps
  hipe: Handle separate hashmap tag correctly
  erts: Fix map bug in dec_term for 32-bit debug VM
  stdlib: Update qlc tests to reflect new ETS hash
  stdlib: Remove obsolete hashmap references in io_lib
  erts: Enhance maps ordering tests
  hipe: Fix maps sort order testcase
  erts: Remove unused variable in crashdump creation
  erts: Fix typo in copy_struct for halfword emulator
  erts: Restrict GCC intrinsics by compiler version
  erts: Fix windows bug in hashmap_info
  erts: Fix typo in make_hash2 for 32-bit arch
  Fix beam_load assert
  ...

Conflicts:
	erts/emulator/beam/bif.tab

1 files changed, 561 insertions, 107 deletions

diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 888ed8e272..c421886431 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -30,7 +30,7 @@
 	t_list_comprehension/1,
 	t_map_sort_literals/1,
 	t_map_equal/1,
-	%t_size/1,
+	t_map_compare/1,
 	t_map_size/1,
 
 	%% Specific Map BIFs
@@ -51,6 +51,10 @@
 	t_erlang_hash/1,
 	t_map_encode_decode/1,
 
+	%% non specific BIF related
+	t_bif_build_and_check/1,
+	t_bif_merge_and_check/1,
+
 	%% maps module not bifs
 	t_maps_fold/1,
 	t_maps_map/1,
@@ -66,6 +70,13 @@
 
 -include_lib("stdlib/include/ms_transform.hrl").
 
+-define(CHECK(Cond,Term),
+	case (catch (Cond)) of
+	    true -> true;
+	    _ -> io:format("###### CHECK FAILED ######~nINPUT:  ~p~n", [Term]),
+		 exit(Term)
+	end).
+
 suite() -> [].
 
 all() -> [
@@ -75,7 +86,7 @@ all() -> [
 	t_update_assoc,t_update_exact,
 	t_guard_bifs, t_guard_sequence, t_guard_update,
 	t_guard_receive,t_guard_fun, t_list_comprehension,
-	t_map_equal,
+	t_map_equal, t_map_compare,
 	t_map_sort_literals,
 
 	%% Specific Map BIFs
@@ -90,6 +101,10 @@ all() -> [
 	t_erlang_hash, t_map_encode_decode,
 	t_map_size,
 
+	%% non specific BIF related
+	t_bif_build_and_check,
+	t_bif_merge_and_check,
+
 	%% maps module
 	t_maps_fold, t_maps_map,
 	t_maps_size, t_maps_without,
@@ -146,17 +161,6 @@ t_build_and_match_literals(Config) when is_list(Config) ->
     ok.
 
 
-%% Tests size(Map).
-%% not implemented, perhaps it shouldn't be either
-
-%t_size(Config) when is_list(Config) ->
-%    0 = size(#{}),
-%    1 = size(#{a=>1}),
-%    1 = size(#{a=>#{a=>1}}),
-%    2 = size(#{a=>1, b=>2}),
-%    3 = size(#{a=>1, b=>2, b=>"3"}),
-%    ok.
-
 t_map_size(Config) when is_list(Config) ->
     0 = map_size(id(#{})),
     1 = map_size(id(#{a=>1})),
@@ -172,12 +176,23 @@ t_map_size(Config) when is_list(Config) ->
     true  = map_is_size(M#{ "a" => 2}, 2),
     false = map_is_size(M#{ "c" => 2}, 2),
 
+    Ks = [build_key(fun(K) -> <<1,K:32,1>> end,I)||I<-lists:seq(1,100)],
+    ok = build_and_check_size(Ks,0,#{}),
+
     %% Error cases.
     {'EXIT',{badarg,_}} = (catch map_size([])),
     {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
     {'EXIT',{badarg,_}} = (catch map_size(1)),
     ok.
 
+build_and_check_size([K|Ks],N,M0) ->
+    N = map_size(M0),
+    M1 = M0#{ K => K },
+    build_and_check_size(Ks,N + 1,M1);
+build_and_check_size([],N,M) ->
+    N = map_size(M),
+    ok.
+
 map_is_size(M,N) when map_size(M) =:= N -> true;
 map_is_size(_,_) -> false.
 
@@ -432,7 +447,7 @@ t_map_sort_literals(Config) when is_list(Config) ->
     true  = #{ c => 1, b => 1, a => 1 } < id(#{ b => 1, c => 1, d => 1}),
     true  = #{ "a" => 1 } < id(#{ <<"a">> => 1}),
     false = #{ <<"a">> => 1 } < id(#{ "a" => 1}),
-    false = #{ 1 => 1 } < id(#{ 1.0 => 1}),
+    true  = #{ 1 => 1 } < id(#{ 1.0 => 1}),
     false = #{ 1.0 => 1 } < id(#{ 1 => 1}),
 
     %% value order
@@ -440,16 +455,47 @@ t_map_sort_literals(Config) when is_list(Config) ->
     false = #{ a => 2 } < id(#{ a => 1}),
     false = #{ a => 2, b => 1 } < id(#{ a => 1, b => 3}),
     true  = #{ a => 1, b => 1 } < id(#{ a => 1, b => 3}),
+    false = #{ a => 1 } < id(#{ a => 1.0}),
+    false = #{ a => 1.0 } < id(#{ a => 1}),
 
     true  = #{ "a" => "hi", b => 134 } == id(#{ b => 134,"a" => "hi"}),
 
+    %% large maps
+
+    M = maps:from_list([{I,I}||I <- lists:seq(1,500)]),
+
+    %% size order
+    true  = M#{ a => 1, b => 2} < id(M#{ a => 1, b => 1, c => 1}),
+    true  = M#{ b => 1, a => 1} < id(M#{ c => 1, a => 1, b => 1}),
+    false = M#{ c => 1, b => 1, a => 1} < id(M#{ c => 1, a => 1}),
+
+    %% key order
+    true  = M#{ a => 1 } < id(M#{ b => 1}),
+    false = M#{ b => 1 } < id(M#{ a => 1}),
+    true  = M#{ a => 1, b => 1, c => 1 } < id(M#{ b => 1, c => 1, d => 1}),
+    true  = M#{ b => 1, c => 1, d => 1 } > id(M#{ a => 1, b => 1, c => 1}),
+    true  = M#{ c => 1, b => 1, a => 1 } < id(M#{ b => 1, c => 1, d => 1}),
+    true  = M#{ "a" => 1 } < id(M#{ <<"a">> => 1}),
+    false = M#{ <<"a">> => 1 } < id(#{ "a" => 1}),
+    true  = M#{ 1 => 1 } < id(maps:remove(1,M#{ 1.0 => 1})),
+    false = M#{ 1.0 => 1 } < id(M#{ 1 => 1}),
+
+    %% value order
+    true  = M#{ a => 1 } < id(M#{ a => 2}),
+    false = M#{ a => 2 } < id(M#{ a => 1}),
+    false = M#{ a => 2, b => 1 } < id(M#{ a => 1, b => 3}),
+    true  = M#{ a => 1, b => 1 } < id(M#{ a => 1, b => 3}),
+    false = M#{ a => 1 } < id(M#{ a => 1.0}),
+    false = M#{ a => 1.0 } < id(M#{ a => 1}),
+
+    true  = M#{ "a" => "hi", b => 134 } == id(M#{ b => 134,"a" => "hi"}),
+
     %% lists:sort
 
     SortVs = [#{"a"=>1},#{a=>2},#{1=>3},#{<<"a">>=>4}],
     [#{1:=ok},#{a:=ok},#{"a":=ok},#{<<"a">>:=ok}] = lists:sort([#{"a"=>ok},#{a=>ok},#{1=>ok},#{<<"a">>=>ok}]),
     [#{1:=3},#{a:=2},#{"a":=1},#{<<"a">>:=4}] = lists:sort(SortVs),
     [#{1:=3},#{a:=2},#{"a":=1},#{<<"a">>:=4}] = lists:sort(lists:reverse(SortVs)),
-
     ok.
 
 t_map_equal(Config) when is_list(Config) ->
@@ -469,27 +515,285 @@ t_map_equal(Config) when is_list(Config) ->
     true = id(#{ a => 1, b => 3, c => <<"wat">> }) =:= id(#{ a => 1, b => 3, c=><<"wat">>}),
     ok.
 
+
+t_map_compare(Config) when is_list(Config) ->
+    Seed = erlang:now(),
+    io:format("seed = ~p\n", [Seed]),
+    random:seed(Seed),
+    repeat(100, fun(_) -> float_int_compare() end, []),
+    repeat(100, fun(_) -> recursive_compare() end, []),
+    ok.
+
+float_int_compare() ->
+    Terms = numeric_keys(3),
+    %%io:format("Keys to use: ~p\n", [Terms]),
+    Pairs = lists:map(fun(K) -> list_to_tuple([{K,V} || V <- Terms]) end, Terms),
+    lists:foreach(fun(Size) ->
+			  MapGen = fun() -> map_gen(list_to_tuple(Pairs), Size) end,
+			  repeat(100, fun do_compare/1, [MapGen, MapGen])
+		  end,
+		  lists:seq(1,length(Terms))),
+    ok.
+
+numeric_keys(N) ->
+    lists:foldl(fun(_,Acc) ->
+			Int = random:uniform(N*4) - N*2,
+			Float = float(Int),
+			[Int, Float, Float * 0.99, Float * 1.01 | Acc]
+		end,
+		[],
+		lists:seq(1,N)).
+
+
+repeat(0, _, _) ->
+    ok;
+repeat(N, Fun, Arg) ->
+    Fun(Arg),
+    repeat(N-1, Fun, Arg).
+
+copy_term(T) ->
+    Papa = self(),
+    P = spawn_link(fun() -> receive Msg -> Papa ! Msg end end),
+    P ! T,
+    receive R -> R end.
+
+do_compare([Gen1, Gen2]) ->
+    M1 = Gen1(),
+    M2 = Gen2(),
+    %%io:format("Maps to compare: ~p AND ~p\n", [M1, M2]),
+    C = (M1 < M2),
+    Erlang = maps_lessthan(M1, M2),
+    C = Erlang,
+    ?CHECK(M1==M1, M1),
+
+    %% Change one key from int to float (or vice versa) and check compare
+    ML1 = maps:to_list(M1),
+    {K1,V1} = lists:nth(random:uniform(length(ML1)), ML1),
+    case K1 of
+	I when is_integer(I) ->
+	    case maps:find(float(I),M1) of
+		error ->
+		    M1f = maps:remove(I, maps:put(float(I), V1, M1)),
+		    ?CHECK(M1f > M1, [M1f, M1]);
+		_ -> ok
+	    end;
+
+	F when is_float(F), round(F) == F ->
+	    case maps:find(round(F),M1) of
+		error ->
+		    M1i = maps:remove(F, maps:put(round(F), V1, M1)),
+		    ?CHECK(M1i < M1, [M1i, M1]);
+		_ -> ok
+	    end;
+
+	_ -> ok   % skip floats with decimals
+    end,
+
+    ?CHECK(M2 == M2, [M2]).
+
+
+maps_lessthan(M1, M2) ->
+  case {maps:size(M1),maps:size(M2)} of
+      {_S,_S} ->
+	  {K1,V1} = lists:unzip(term_sort(maps:to_list(M1))),
+	  {K2,V2} = lists:unzip(term_sort(maps:to_list(M2))),
+
+	  case erts_internal:cmp_term(K1,K2) of
+	      -1 -> true;
+	      0 -> (V1 < V2);
+	      1 -> false
+	  end;
+
+      {S1, S2} ->
+	  S1 < S2
+  end.
+
+term_sort(L) ->
+    lists:sort(fun(A,B) -> erts_internal:cmp_term(A,B) =< 0 end,
+	       L).
+
+
+cmp(T1, T2, Exact) when is_tuple(T1) and is_tuple(T2) ->
+    case {size(T1),size(T2)} of
+	{_S,_S} -> cmp(tuple_to_list(T1), tuple_to_list(T2), Exact);
+	{S1,S2} when S1 < S2 -> -1;
+	{S1,S2} when S1 > S2 -> 1
+    end;
+
+cmp([H1|T1], [H2|T2], Exact) ->
+    case cmp(H1,H2, Exact) of
+	0 -> cmp(T1,T2, Exact);
+	C -> C
+    end;
+
+cmp(M1, M2, Exact) when is_map(M1) andalso is_map(M2) ->
+    cmp_maps(M1,M2,Exact);
+cmp(M1, M2, Exact) ->
+    cmp_others(M1, M2, Exact).
+
+cmp_maps(M1, M2, Exact) ->
+    case {maps:size(M1),maps:size(M2)} of
+	{_S,_S} ->
+	    {K1,V1} = lists:unzip(term_sort(maps:to_list(M1))),
+	    {K2,V2} = lists:unzip(term_sort(maps:to_list(M2))),
+
+	    case cmp(K1, K2, true) of
+		0 -> cmp(V1, V2, Exact);
+		C -> C
+	    end;
+
+	{S1,S2} when S1 < S2 -> -1;
+	{S1,S2} when S1 > S2 -> 1
+    end.
+
+cmp_others(I, F, true) when is_integer(I), is_float(F) ->
+    -1;
+cmp_others(F, I, true) when is_float(F), is_integer(I) ->
+    1;
+cmp_others(T1, T2, _) ->
+    case {T1<T2, T1==T2} of
+	{true,false} -> -1;
+	{false,true} -> 0;
+	{false,false} -> 1
+    end.
+
+map_gen(Pairs, Size) ->
+    {_,L} = lists:foldl(fun(_, {Keys, Acc}) ->
+				KI = random:uniform(size(Keys)),
+				K = element(KI,Keys),
+				KV = element(random:uniform(size(K)), K),
+				{erlang:delete_element(KI,Keys), [KV | Acc]}
+			end,
+			{Pairs, []},
+			lists:seq(1,Size)),
+
+    maps:from_list(L).
+
+
+recursive_compare() ->
+    Leafs = {atom, 17, 16.9, 17.1, [], self(), spawn(fun() -> ok end), make_ref(), make_ref()},
+    {A, B} = term_gen_recursive(Leafs, 0, 0),
+    %%io:format("Recursive term A = ~p\n", [A]),
+    %%io:format("Recursive term B = ~p\n", [B]),
+
+    ?CHECK({true,false} =:=  case do_cmp(A, B, false) of
+				 -1 -> {A<B, A>=B};
+				 0 -> {A==B, A/=B};
+				 1 -> {A>B, A=<B}
+			     end,
+	   {A,B}),
+    A2 = copy_term(A),
+    ?CHECK(A == A2, {A,A2}),
+    ?CHECK(0 =:= cmp(A, A2, false), {A,A2}),
+
+    B2 = copy_term(B),
+    ?CHECK(B == B2, {B,B2}),
+    ?CHECK(0 =:= cmp(B, B2, false), {B,B2}),
+    ok.
+
+do_cmp(A, B, Exact) ->
+    C = cmp(A, B, Exact),
+    C.
+
+%% Generate two terms {A,B} that may only differ
+%% at float vs integer types.
+term_gen_recursive(Leafs, Flags, Depth) ->
+    MaxDepth = 10,
+    Rnd = case {Flags, Depth} of
+	      {_, MaxDepth} -> % Only leafs
+		  random:uniform(size(Leafs)) + 3;
+	      {0, 0} ->        % Only containers
+		  random:uniform(3);
+	      {0,_} ->         % Anything
+		  random:uniform(size(Leafs)+3)
+	  end,
+    case Rnd of
+	1 -> % Make map
+	    Size = random:uniform(size(Leafs)),
+	    lists:foldl(fun(_, {Acc1,Acc2}) ->
+				{K1,K2} = term_gen_recursive(Leafs, Flags,
+							     Depth+1),
+				{V1,V2} = term_gen_recursive(Leafs, Flags, Depth+1),
+				%%ok = check_keys(K1,K2, 0),
+				{maps:put(K1,V1, Acc1), maps:put(K2,V2, Acc2)}
+			end,
+			{maps:new(), maps:new()},
+			lists:seq(1,Size));
+	2 -> % Make cons
+	    {Car1,Car2} = term_gen_recursive(Leafs, Flags, Depth+1),
+	    {Cdr1,Cdr2} = term_gen_recursive(Leafs, Flags, Depth+1),
+	    {[Car1 | Cdr1], [Car2 | Cdr2]};
+	3 -> % Make tuple
+	    Size = random:uniform(size(Leafs)),
+	    L = lists:map(fun(_) -> term_gen_recursive(Leafs, Flags, Depth+1) end,
+			  lists:seq(1,Size)),
+	    {L1, L2} = lists:unzip(L),
+	    {list_to_tuple(L1), list_to_tuple(L2)};
+
+	N -> % Make leaf
+	    case element(N-3, Leafs) of
+		I when is_integer(I) ->
+		    case random:uniform(4) of
+			1 -> {I, float(I)};
+			2 -> {float(I), I};
+			_ -> {I,I}
+		    end;
+		T -> {T,T}
+	    end
+    end.
+
+check_keys(K1, K2, _) when K1 =:= K2 ->
+    case erlang:phash3(K1) =:= erlang:phash3(K2) of
+	true -> ok;
+	false ->
+	    io:format("Same keys with different hash values !!!\nK1 = ~p\nK2 = ~p\n", [K1,K2]),
+	    error
+    end;
+check_keys(K1, K2, 0) ->
+    case {erlang:phash3(K1), erlang:phash3(K2)} of
+	{H,H} -> check_keys(K1, K2, 1);
+	{_,_} -> ok
+    end;
+check_keys(K1, K2, L) when L < 10 ->
+    case {erlang:phash3([L|K1]), erlang:phash3([L|K2])} of
+	{H,H} -> check_keys(K1, K2, L+1);
+	{_,_} -> ok
+    end;
+check_keys(K1, K2, L) ->
+    io:format("Same hash value at level ~p !!!\nK1 = ~p\nK2 = ~p\n", [L,K1,K2]),
+    error.
+
 %% BIFs
 t_bif_map_get(Config) when is_list(Config) ->
-
+    %% small map
     1    = maps:get(a, #{ a=> 1}),
     2    = maps:get(b, #{ a=> 1, b => 2}),
     "hi" = maps:get("hello", #{ a=>1, "hello" => "hi"}),
     "tuple hi" = maps:get({1,1.0}, #{ a=>a, {1,1.0} => "tuple hi"}),
 
-    M    = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }),
-    "v4" = maps:get(<<"k2">>, M#{ <<"k2">> => "v4" }),
+    M0    = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }),
+    "v4" = maps:get(<<"k2">>, M0#{<<"k2">> => "v4"}),
+
+    %% large map
+    M1   = maps:from_list([{I,I}||I<-lists:seq(1,100)] ++
+			  [{a,1},{b,2},{"hello","hi"},{{1,1.0},"tuple hi"},
+			   {k1,"v1"},{<<"k2">>,"v3"}]),
+    1    = maps:get(a, M1),
+    2    = maps:get(b, M1),
+    "hi" = maps:get("hello", M1),
+    "tuple hi" = maps:get({1,1.0}, M1),
+    "v3" = maps:get(<<"k2">>, M1),
 
     %% error case
     {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,[])),
     {'EXIT',{badarg, [{maps,get,_,_}|_]}} = (catch maps:get(a,<<>>)),
     {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get({1,1}, #{{1,1.0} => "tuple"})),
     {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{})),
-    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{ b=>1, c=>2})),
+    {'EXIT',{bad_key,[{maps,get,_,_}|_]}} = (catch maps:get(a,#{b=>1, c=>2})),
     ok.
 
 t_bif_map_find(Config) when is_list(Config) ->
-
+    %% small map
     {ok, 1}     = maps:find(a, #{ a=> 1}),
     {ok, 2}     = maps:find(b, #{ a=> 1, b => 2}),
     {ok, "int"} = maps:find(1, #{ 1   => "int"}),
@@ -498,8 +802,18 @@ t_bif_map_find(Config) when is_list(Config) ->
     {ok, "hi"} = maps:find("hello", #{ a=>1, "hello" => "hi"}),
     {ok, "tuple hi"} = maps:find({1,1.0}, #{ a=>a, {1,1.0} => "tuple hi"}),
 
-    M = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }),
-    {ok, "v4"} = maps:find(<<"k2">>, M#{ <<"k2">> => "v4" }),
+    M0 = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }),
+    {ok, "v4"} = maps:find(<<"k2">>, M0#{ <<"k2">> => "v4" }),
+
+    %% large map
+    M1   = maps:from_list([{I,I}||I<-lists:seq(1,100)] ++
+			  [{a,1},{b,2},{"hello","hi"},{{1,1.0},"tuple hi"},
+			   {k1,"v1"},{<<"k2">>,"v3"}]),
+    {ok, 1}    = maps:find(a, M1),
+    {ok, 2}    = maps:find(b, M1),
+    {ok, "hi"} = maps:find("hello", M1),
+    {ok, "tuple hi"} = maps:find({1,1.0}, M1),
+    {ok, "v3"} = maps:find(<<"k2">>, M1),
 
     %% error case
     error = maps:find(a,#{}),
@@ -508,7 +822,6 @@ t_bif_map_find(Config) when is_list(Config) ->
     error = maps:find(1, #{ 1.0  => "float"}),
     error = maps:find({1.0,1}, #{ a=>a, {1,1.0} => "tuple hi"}), % reverse types in tuple key
 
-
     {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id([]))),
     {'EXIT',{badarg,[{maps,find,_,_}|_]}} = (catch maps:find(a,id(<<>>))),
     ok.
@@ -542,12 +855,12 @@ t_bif_map_is_key(Config) when is_list(Config) ->
 t_bif_map_keys(Config) when is_list(Config) ->
     [] = maps:keys(#{}),
 
-    [1,2,3,4,5] = maps:keys(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e}),
-    [1,2,3,4,5] = maps:keys(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c}),
+    [1,2,3,4,5] = lists:sort(maps:keys(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e})),
+    [1,2,3,4,5] = lists:sort(maps:keys(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c})),
 
     % values in key order: [4,int,"hi",<<"key">>]
     M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
-    [4,int,"hi",<<"key">>] = maps:keys(M1),
+    [4,int,"hi",<<"key">>] = lists:sort(maps:keys(M1)),
 
     %% error case
     {'EXIT',{badarg,[{maps,keys,_,_}|_]}} = (catch maps:keys(1 bsl 65 + 3)),
@@ -596,33 +909,33 @@ t_bif_map_put(Config) when is_list(Config) ->
 
     M1 = #{ "hi" := "hello"} = maps:put("hi", "hello", #{}),
 
-    ["hi"]    = maps:keys(M1),
-    ["hello"] = maps:values(M1),
+    true = is_members(["hi"],maps:keys(M1)),
+    true = is_members(["hello"],maps:values(M1)),
 
     M2 = #{ int := 3 } = maps:put(int, 3, M1),
 
-    [int,"hi"]  = maps:keys(M2),
-    [3,"hello"] = maps:values(M2),
+    true = is_members([int,"hi"],maps:keys(M2)),
+    true = is_members([3,"hello"],maps:values(M2)),
 
     M3 = #{ <<"key">> := <<"value">> } = maps:put(<<"key">>, <<"value">>, M2),
 
-    [int,"hi",<<"key">>]    = maps:keys(M3),
-    [3,"hello",<<"value">>] = maps:values(M3),
+    true = is_members([int,"hi",<<"key">>],maps:keys(M3)),
+    true = is_members([3,"hello",<<"value">>],maps:values(M3)),
 
     M4 = #{ 18446744073709551629 := wat } = maps:put(18446744073709551629, wat, M3),
 
-    [18446744073709551629,int,"hi",<<"key">>] = maps:keys(M4),
-    [wat,3,"hello",<<"value">>]               = maps:values(M4),
+    true = is_members([18446744073709551629,int,"hi",<<"key">>],maps:keys(M4)),
+    true = is_members([wat,3,"hello",<<"value">>],maps:values(M4)),
 
     M0 = #{ 4 := number } = M5 = maps:put(4, number, M4),
 
-    [4,18446744073709551629,int,"hi",<<"key">>] = maps:keys(M5),
-    [number,wat,3,"hello",<<"value">>]          = maps:values(M5),
+    true = is_members([4,18446744073709551629,int,"hi",<<"key">>],maps:keys(M5)),
+    true = is_members([number,wat,3,"hello",<<"value">>],maps:values(M5)),
 
     M6 = #{ <<"key">> := <<"other value">> } = maps:put(<<"key">>, <<"other value">>, M5),
 
-    [4,18446744073709551629,int,"hi",<<"key">>] = maps:keys(M6),
-    [number,wat,3,"hello",<<"other value">>]    = maps:values(M6),
+    true = is_members([4,18446744073709551629,int,"hi",<<"key">>],maps:keys(M6)),
+    true = is_members([number,wat,3,"hello",<<"other value">>],maps:values(M6)),
 
     %% error case
     {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,1 bsl 65 + 3)),
@@ -630,7 +943,15 @@ t_bif_map_put(Config) when is_list(Config) ->
     {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,atom)),
     {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,[])),
     {'EXIT',{badarg,[{maps,put,_,_}|_]}} = (catch maps:put(1,a,<<>>)),
-     ok.
+    ok.
+
+is_members(Ks,Ls) when length(Ks) =/= length(Ls) -> false;
+is_members(Ks,Ls) -> is_members_do(Ks,Ls).
+
+is_members_do([],[]) -> true;
+is_members_do([],_) -> false;
+is_members_do([K|Ks],Ls) ->
+    is_members_do(Ks, lists:delete(K,Ls)).
 
 t_bif_map_remove(Config) when is_list(Config) ->
     0  = erlang:map_size(maps:remove(some_key, #{})),
@@ -639,20 +960,20 @@ t_bif_map_remove(Config) when is_list(Config) ->
 	4 => number, 18446744073709551629 => wat},
 
     M1 = maps:remove("hi", M0),
-    [4,18446744073709551629,int,<<"key">>] = maps:keys(M1),
-    [number,wat,3,<<"value">>]             = maps:values(M1),
+    true = is_members([4,18446744073709551629,int,<<"key">>],maps:keys(M1)),
+    true = is_members([number,wat,3,<<"value">>],maps:values(M1)),
 
     M2 = maps:remove(int, M1),
-    [4,18446744073709551629,<<"key">>] = maps:keys(M2),
-    [number,wat,<<"value">>]           = maps:values(M2),
+    true = is_members([4,18446744073709551629,<<"key">>],maps:keys(M2)),
+    true = is_members([number,wat,<<"value">>],maps:values(M2)),
 
     M3 = maps:remove(<<"key">>, M2),
-    [4,18446744073709551629] = maps:keys(M3),
-    [number,wat]             = maps:values(M3),
+    true = is_members([4,18446744073709551629],maps:keys(M3)),
+    true = is_members([number,wat],maps:values(M3)),
 
     M4 = maps:remove(18446744073709551629, M3),
-    [4]      = maps:keys(M4),
-    [number] = maps:values(M4),
+    true = is_members([4],maps:keys(M4)),
+    true = is_members([number],maps:values(M4)),
 
     M5 = maps:remove(4, M4),
     [] = maps:keys(M5),
@@ -702,15 +1023,15 @@ t_bif_map_update(Config) when is_list(Config) ->
 t_bif_map_values(Config) when is_list(Config) ->
 
     [] = maps:values(#{}),
+    [1] = maps:values(#{a=>1}),
 
-    [a,b,c,d,e] = maps:values(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e}),
-    [a,b,c,d,e] = maps:values(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c}),
+    true = is_members([a,b,c,d,e],maps:values(#{ 1 => a, 2 => b, 3 => c, 4 => d, 5 => e})),
+    true = is_members([a,b,c,d,e],maps:values(#{ 4 => d, 5 => e, 1 => a, 2 => b, 3 => c})),
 
-    % values in key order: [4,int,"hi",<<"key">>]
     M1 = #{ "hi" => "hello", int => 3, <<"key">> => <<"value">>, 4 => number},
     M2 = M1#{ "hi" => "hello2", <<"key">> => <<"value2">> },
-    [number,3,"hello2",<<"value2">>] = maps:values(M2),
-    [number,3,"hello",<<"value">>]   = maps:values(M1),
+    true = is_members([number,3,"hello2",<<"value2">>],maps:values(M2)),
+    true = is_members([number,3,"hello",<<"value">>],maps:values(M1)),
 
     %% error case
     {'EXIT',{badarg,[{maps,values,_,_}|_]}} = (catch maps:values(1 bsl 65 + 3)),
@@ -730,61 +1051,61 @@ t_erlang_hash(Config) when is_list(Config) ->
 t_bif_erlang_phash2() ->
 
     39679005 = erlang:phash2(#{}),
-    78942764 = erlang:phash2(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 }),
-    37338230 = erlang:phash2(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} }),
-    14363616 = erlang:phash2(#{ 1 => a }),
-    51612236 = erlang:phash2(#{ a => 1 }),
+    33667975 = erlang:phash2(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 }), % 78942764
+    95332690 = erlang:phash2(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} }), % 37338230
+    108954384 = erlang:phash2(#{ 1 => a }), % 14363616
+    59617982 = erlang:phash2(#{ a => 1 }), % 51612236
 
-    37468437 = erlang:phash2(#{{} => <<>>}),
-    44049159 = erlang:phash2(#{<<>> => {}}),
+    42770201 = erlang:phash2(#{{} => <<>>}), % 37468437
+    71687700 = erlang:phash2(#{<<>> => {}}), % 44049159
 
     M0 = #{ a => 1, "key" => <<"value">> },
     M1 = maps:remove("key",M0),
     M2 = M1#{ "key" => <<"value">> },
 
-    118679416 = erlang:phash2(M0),
-    51612236  = erlang:phash2(M1),
-    118679416 = erlang:phash2(M2),
+    70249457 = erlang:phash2(M0), % 118679416
+    59617982 = erlang:phash2(M1), % 51612236
+    70249457 = erlang:phash2(M2), % 118679416
     ok.
 
 t_bif_erlang_phash() ->
     Sz = 1 bsl 32,
-    268440612  = erlang:phash(#{},Sz),
-    1196461908 = erlang:phash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz),
-    3944426064 = erlang:phash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz),
-    1394238263 = erlang:phash(#{ 1 => a },Sz),
-    4066388227 = erlang:phash(#{ a => 1 },Sz),
+    1113425985 = erlang:phash(#{},Sz), % 268440612
+    1510068139 = erlang:phash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz), % 1196461908
+    3182345590 = erlang:phash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz), % 3944426064
+    2927531828 = erlang:phash(#{ 1 => a },Sz), % 1394238263
+    1670235874 = erlang:phash(#{ a => 1 },Sz), % 4066388227
 
-    1578050717 = erlang:phash(#{{} => <<>>},Sz),
-    1578050717 = erlang:phash(#{<<>> => {}},Sz), % yep, broken
+    3935089469 = erlang:phash(#{{} => <<>>},Sz), % 1578050717
+    71692856   = erlang:phash(#{<<>> => {}},Sz), % 1578050717
 
     M0 = #{ a => 1, "key" => <<"value">> },
     M1 = maps:remove("key",M0),
     M2 = M1#{ "key" => <<"value">> },
 
-    3590546636 = erlang:phash(M0,Sz),
-    4066388227 = erlang:phash(M1,Sz),
-    3590546636 = erlang:phash(M2,Sz),
+    2620391445 = erlang:phash(M0,Sz), % 3590546636
+    1670235874 = erlang:phash(M1,Sz), % 4066388227
+    2620391445 = erlang:phash(M2,Sz), % 3590546636
     ok.
 
 t_bif_erlang_hash() ->
     Sz = 1 bsl 27 - 1,
-    5158      = erlang:hash(#{},Sz),
-    71555838  = erlang:hash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz),
-    5497225   = erlang:hash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz),
-    126071654 = erlang:hash(#{ 1 => a },Sz),
-    126426236 = erlang:hash(#{ a => 1 },Sz),
+    39684169 = erlang:hash(#{},Sz),  % 5158
+    33673142 = erlang:hash(#{ a => 1, "a" => 2, <<"a">> => 3, {a,b} => 4 },Sz), % 71555838
+    95337869 = erlang:hash(#{ 1 => a, 2 => "a", 3 => <<"a">>, 4 => {a,b} },Sz), % 5497225
+    108959561 = erlang:hash(#{ 1 => a },Sz), % 126071654
+    59623150 = erlang:hash(#{ a => 1 },Sz), % 126426236
 
-    101655720 = erlang:hash(#{{} => <<>>},Sz),
-    101655720 = erlang:hash(#{<<>> => {}},Sz), % yep, broken
+    42775386 = erlang:hash(#{{} => <<>>},Sz), % 101655720
+    71692856 = erlang:hash(#{<<>> => {}},Sz), % 101655720
 
     M0 = #{ a => 1, "key" => <<"value">> },
     M1 = maps:remove("key",M0),
     M2 = M1#{ "key" => <<"value">> },
 
-    38260486  = erlang:hash(M0,Sz),
-    126426236 = erlang:hash(M1,Sz),
-    38260486  = erlang:hash(M2,Sz),
+    70254632 = erlang:hash(M0,Sz), % 38260486
+    59623150 = erlang:hash(M1,Sz), % 126426236
+    70254632 = erlang:hash(M2,Sz), % 38260486
     ok.
 
 
@@ -818,12 +1139,12 @@ t_map_encode_decode(Config) when is_list(Config) ->
 
     %% literally #{ "hi" => "value", a=>33, b=>55 } in the internal order
     #{ a:=33, b:=55, "hi" := "value"} = erlang:binary_to_term(<<131,116,0,0,0,3,
-	107,0,2,104,105, % "hi" :: list()
+	107,0,2,104,105,            % "hi" :: list()
 	107,0,5,118,97,108,117,101, % "value" :: list()
-	100,0,1,97, % a :: atom()
-	97,33, % 33 :: integer()
-	100,0,1,98, % b :: atom()
-	97,55  % 55 :: integer()
+	100,0,1,97,                 % a :: atom()
+	97,33,                      % 33 :: integer()
+	100,0,1,98,                 % b :: atom()
+	97,55                       % 55 :: integer()
 	>>),
 
 
@@ -856,39 +1177,42 @@ t_map_encode_decode(Config) when is_list(Config) ->
 map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, M0) ->
     M1 = maps:put(K,V,M0),
     B0 = erlang:term_to_binary(M1),
-    Ls = lists:sort(fun(A,B) -> erts_internal:cmp_term(A,B) < 0 end, [{K, erlang:term_to_binary(K), erlang:term_to_binary(V)}|EncodedPairs]),
-    %% sort Ks and Vs according to term spec, then match it
-    KVbins = lists:foldr(fun({_,Kbin,Vbin}, Acc) -> [Kbin,Vbin | Acc] end, [], Ls),
-    ok = match_encoded_map(B0, length(Ls), KVbins),
+    Ls = [{erlang:term_to_binary(K), erlang:term_to_binary(V)}|EncodedPairs],
+    ok = match_encoded_map(B0, length(Ls), Ls),
     %% decode and match it
     M1 = erlang:binary_to_term(B0),
     map_encode_decode_and_match(Pairs,Ls,M1);
 map_encode_decode_and_match([],_,_) -> ok.
 
 match_encoded_map(<<131,116,Size:32,Encoded/binary>>,Size,Items) ->
-    match_encoded_map(Encoded,Items);
+    match_encoded_map_stripped_size(Encoded,Items,Items);
 match_encoded_map(_,_,_) -> no_match_size.
 
-match_encoded_map(<<>>,[]) -> ok;
-match_encoded_map(Bin,[<<131,Item/binary>>|Items]) ->
-    Size = erlang:byte_size(Item),
-    <<EncodedTerm:Size/binary, Bin1/binary>> = Bin,
-    EncodedTerm = Item, %% Asssert
-    match_encoded_map(Bin1,Items).
+match_encoded_map_stripped_size(<<>>,_,_) -> ok;
+match_encoded_map_stripped_size(B0,[{<<131,K/binary>>,<<131,V/binary>>}|Items],Ls) ->
+    Ksz = byte_size(K),
+    Vsz = byte_size(V),
+    case B0 of
+	<<K:Ksz/binary,V:Vsz/binary,B1/binary>> ->
+	    match_encoded_map_stripped_size(B1,Ls,Ls);
+	_ ->
+	    match_encoded_map_stripped_size(B0,Items,Ls)
+    end;
+match_encoded_map_stripped_size(_,[],_) -> fail.
 
 
 t_bif_map_to_list(Config) when is_list(Config) ->
     [] = maps:to_list(#{}),
-    [{a,1},{b,2}] = maps:to_list(#{a=>1,b=>2}),
-    [{a,1},{b,2},{c,3}] = maps:to_list(#{c=>3,a=>1,b=>2}),
-    [{a,1},{b,2},{g,3}] = maps:to_list(#{g=>3,a=>1,b=>2}),
-    [{a,1},{b,2},{g,3},{"c",4}] = maps:to_list(#{g=>3,a=>1,b=>2,"c"=>4}),
-    [{3,v2},{hi,v4},{{hi,3},v5},{"hi",v3},{<<"hi">>,v1}] = maps:to_list(#{
-	    <<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5}),
+    [{a,1},{b,2}] = lists:sort(maps:to_list(#{a=>1,b=>2})),
+    [{a,1},{b,2},{c,3}] = lists:sort(maps:to_list(#{c=>3,a=>1,b=>2})),
+    [{a,1},{b,2},{g,3}] = lists:sort(maps:to_list(#{g=>3,a=>1,b=>2})),
+    [{a,1},{b,2},{g,3},{"c",4}] = lists:sort(maps:to_list(#{g=>3,a=>1,b=>2,"c"=>4})),
+    [{3,v2},{hi,v4},{{hi,3},v5},{"hi",v3},{<<"hi">>,v1}] =
+	lists:sort(maps:to_list(#{<<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5})),
 
-    [{3,v7},{hi,v9},{{hi,3},v10},{"hi",v8},{<<"hi">>,v6}] = maps:to_list(#{
-	    <<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5,
-	    <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10}),
+    [{3,v7},{hi,v9},{{hi,3},v10},{"hi",v8},{<<"hi">>,v6}] =
+	lists:sort(maps:to_list(#{<<"hi">>=>v1,3=>v2,"hi"=>v3,hi=>v4,{hi,3}=>v5,
+				  <<"hi">>=>v6,3=>v7,"hi"=>v8,hi=>v9,{hi,3}=>v10})),
 
     %% error cases
     {'EXIT', {badarg,_}} = (catch maps:to_list(id(a))),
@@ -901,7 +1225,7 @@ t_bif_map_from_list(Config) when is_list(Config) ->
     A   = maps:from_list([]),
     0   = erlang:map_size(A),
 
-    #{a:=1,b:=2}  = maps:from_list([{a,1},{b,2}]),
+    #{a:=1,b:=2}      = maps:from_list([{a,1},{b,2}]),
     #{c:=3,a:=1,b:=2} = maps:from_list([{a,1},{b,2},{c,3}]),
     #{g:=3,a:=1,b:=2} = maps:from_list([{a,1},{b,2},{g,3}]),
 
@@ -923,6 +1247,136 @@ t_bif_map_from_list(Config) when is_list(Config) ->
     {'EXIT', {badarg,_}} = (catch maps:from_list(id(42))),
     ok.
 
+t_bif_build_and_check(Config) when is_list(Config) ->
+    ok = check_build_and_remove(750,[
+				      fun(K) -> [K,K] end,
+				      fun(K) -> [float(K),K] end,
+				      fun(K) -> K end,
+				      fun(K) -> {1,K} end,
+				      fun(K) -> {K} end,
+				      fun(K) -> [K|K] end,
+				      fun(K) -> [K,1,2,3,4] end,
+				      fun(K) -> {K,atom} end,
+				      fun(K) -> float(K) end,
+				      fun(K) -> integer_to_list(K) end,
+				      fun(K) -> list_to_atom(integer_to_list(K)) end,
+				      fun(K) -> [K,{K,[K,{K,[K]}]}] end,
+				      fun(K) -> <<K:32>> end
+			      ]),
+
+    ok.
+
+check_build_and_remove(_,[]) -> ok;
+check_build_and_remove(N,[F|Fs]) ->
+    {M,Ks} = build_and_check(N, maps:new(), F, []),
+    ok     = remove_and_check(Ks,M),
+    check_build_and_remove(N,Fs).
+
+build_and_check(0, M0, _, Ks) -> {M0, Ks};
+build_and_check(N, M0, F, Ks) ->
+    K  = build_key(F,N),
+    M1 = maps:put(K,K,M0),
+    ok = check_keys_exist([K|Ks], M1),
+    M2 = maps:update(K,v,M1),
+    v  = maps:get(K,M2),
+    build_and_check(N-1,M1,F,[K|Ks]).
+
+remove_and_check([],_) -> ok;
+remove_and_check([K|Ks], M0) ->
+    K     = maps:get(K,M0),
+    true  = maps:is_key(K,M0),
+    M1    = maps:remove(K,M0),
+    false = maps:is_key(K,M1),
+    true  = maps:is_key(K,M0),
+    ok    = check_keys_exist(Ks,M1),
+    error = maps:find(K,M1),
+    remove_and_check(Ks, M1).
+
+build_key(F,N) when N rem 3 =:= 0 -> F(N);
+build_key(F,N) when N rem 3 =:= 1 -> K = F(N), {K,K};
+build_key(F,N) when N rem 3 =:= 2 -> K = F(N), [K,K].
+
+check_keys_exist([], _) -> ok;
+check_keys_exist([K|Ks],M) ->
+    true = maps:is_key(K,M),
+    check_keys_exist(Ks,M).
+
+t_bif_merge_and_check(Config) when is_list(Config) ->
+    %% simple disjunct ones
+    %% make sure all keys are unique
+    Kss = [[a,b,c,d],
+	   [1,2,3,4],
+	   [],
+	   ["hi"],
+	   [e],
+	   [build_key(fun(K) -> {small,K} end, I) || I <- lists:seq(1,32)],
+	   lists:seq(5, 28),
+	   lists:seq(29, 59),
+	   [build_key(fun(K) -> integer_to_list(K) end, I) || I <- lists:seq(2000,10000)],
+	   [build_key(fun(K) -> <<K:32>> end, I) || I <- lists:seq(1,80)],
+	   [build_key(fun(K) -> {<<K:32>>} end, I) || I <- lists:seq(100,1000)]],
+
+
+    KsMs = build_keys_map_pairs(Kss),
+    Cs   = [{CKs1,CM1,CKs2,CM2} || {CKs1,CM1} <- KsMs, {CKs2,CM2} <- KsMs],
+    ok   = merge_and_check_combo(Cs),
+
+    %% overlapping ones
+
+    KVs1 = [{a,1},{b,2},{c,3}],
+    KVs2 = [{b,3},{c,4},{d,5}],
+    KVs  = [{I,I} || I <- lists:seq(1,32)],
+    KVs3 = KVs1 ++ KVs,
+    KVs4 = KVs2 ++ KVs,
+
+    M1  = maps:from_list(KVs1),
+    M2  = maps:from_list(KVs2),
+    M3  = maps:from_list(KVs3),
+    M4  = maps:from_list(KVs4),
+
+    M12 = maps:merge(M1,M2),
+    ok  = check_key_values(KVs2 ++ [{a,1}], M12),
+    M21 = maps:merge(M2,M1),
+    ok  = check_key_values(KVs1 ++ [{d,5}], M21),
+
+    M34 = maps:merge(M3,M4),
+    ok  = check_key_values(KVs4 ++ [{a,1}], M34),
+    M43 = maps:merge(M4,M3),
+    ok  = check_key_values(KVs3 ++ [{d,5}], M43),
+
+    M14 = maps:merge(M1,M4),
+    ok  = check_key_values(KVs4 ++ [{a,1}], M14),
+    M41 = maps:merge(M4,M1),
+    ok  = check_key_values(KVs1 ++ [{d,5}] ++ KVs, M41),
+
+    ok.
+
+check_key_values([],_) -> ok;
+check_key_values([{K,V}|KVs],M) ->
+    V = maps:get(K,M),
+    check_key_values(KVs,M).
+
+merge_and_check_combo([]) -> ok;
+merge_and_check_combo([{Ks1,M1,Ks2,M2}|Cs]) ->
+    M12 = maps:merge(M1,M2),
+    ok  = check_keys_exist(Ks1 ++ Ks2, M12),
+    M21 = maps:merge(M2,M1),
+    ok  = check_keys_exist(Ks1 ++ Ks2, M21),
+
+    true = M12 =:= M21,
+    M12  = M21,
+
+    merge_and_check_combo(Cs).
+
+build_keys_map_pairs([]) -> [];
+build_keys_map_pairs([Ks|Kss]) ->
+    M  = maps:from_list(keys_to_pairs(Ks)),
+    ok = check_keys_exist(Ks, M),
+    [{Ks,M}|build_keys_map_pairs(Kss)].
+
+keys_to_pairs(Ks) -> [{K,K} || K <- Ks].
+
+
 %% Maps module, not BIFs
 t_maps_fold(_Config) ->
     Vs = lists:seq(1,100),