Merge branch 'egil/fix-maps-from_list-size'

* egil/fix-maps-from_list-size:
  erts: Strengthen Maps merge tests
  erts: Try to test deep Maps collision
  erts: Fix size bug in maps:from_list/1 BIF

2 files changed, 50 insertions, 5 deletions

diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index ab40f47919..a8e8ad346b 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -89,7 +89,7 @@ static Eterm flatmap_from_validated_list(Process *p, Eterm list, Uint size);
 static Eterm hashmap_from_validated_list(Process *p, Eterm list, Uint size);
 static Eterm hashmap_from_unsorted_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int reject_dupkeys);
 static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
-static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, int is_root);
+static Eterm hashmap_from_chunked_array(ErtsHeapFactory*, hxnode_t *hxns, Uint n, Uint size, int is_root);
 static Eterm hashmap_info(Process *p, Eterm node);
 static Eterm hashmap_bld_tuple_uint(Uint **hpp, Uint *szp, Uint n, Uint nums[]);
 static int hxnodecmp(hxnode_t* a, hxnode_t* b);
@@ -661,7 +661,7 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
 	ix++;
     }
 
-    res = hashmap_from_chunked_array(factory, hxns, elems, !lvl);
+    res = hashmap_from_chunked_array(factory, hxns, elems, n, !lvl);
 
     ERTS_FACTORY_HOLE_CHECK(factory);
 
@@ -669,8 +669,8 @@ static Eterm hashmap_from_sorted_unique_array(ErtsHeapFactory* factory,
 }
 
 #define HALLOC_EXTRA 200
-static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
-                                        hxnode_t *hxns, Uint n, int is_root) {
+static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory, hxnode_t *hxns, Uint n,
+                                        Uint size, int is_root) {
     Uint ix, d, dn, dc, slot, elems;
     Uint32 v, vp, vn, hdr;
     Uint bp, sz;
@@ -840,7 +840,7 @@ static Eterm hashmap_from_chunked_array(ErtsHeapFactory *factory,
 
     if (is_root) {
 	*hp++ = (hdr == 0xffff) ? MAP_HEADER_HAMT_HEAD_ARRAY : MAP_HEADER_HAMT_HEAD_BITMAP(hdr);
-	*hp++ = n;
+	*hp++ = size;
     } else {
 	*hp++ = MAP_HEADER_HAMT_NODE_BITMAP(hdr);
     }
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 04c12d3e14..bc649d5808 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -650,6 +650,17 @@ t_map_size(Config) when is_list(Config) ->
     Ks = [build_key(fun(K) -> <<1,K:32,1>> end,I)||I<-lists:seq(1,100)],
     ok = build_and_check_size(Ks,0,#{}),
 
+    %% try deep collisions
+    %% statistically we get another subtree at 50k -> 100k elements
+    %% Try to be nice and don't use too much memory in the testcase,
+
+    N  = 500000,
+    Is = lists:seq(1,N),
+    N  = map_size(maps:from_list([{I,I}||I<-Is])),
+    N  = map_size(maps:from_list([{<<I:32>>,I}||I<-Is])),
+    N  = map_size(maps:from_list([{integer_to_list(I),I}||I<-Is])),
+    N  = map_size(maps:from_list([{float(I),I}||I<-Is])),
+
     %% Error cases.
     {'EXIT',{badarg,_}} = (catch map_size([])),
     {'EXIT',{badarg,_}} = (catch map_size(<<1,2,3>>)),
@@ -1820,6 +1831,40 @@ t_bif_map_merge(Config) when is_list(Config) ->
     #{4 := integer, 18446744073709551629 := wat, float := 3.3, int := 3,
 	{1,2} := "tuple", "hi" := "hello again", <<"key">> := <<"value">>} = maps:merge(M0,M1),
 
+    %% try deep collisions
+    N  = 150000,
+    Is = lists:seq(1,N),
+    M2 = maps:from_list([{I,I}||I<-Is]),
+    150000 = maps:size(M2),
+    M3 = maps:from_list([{<<I:32>>,I}||I<-Is]),
+    150000 = maps:size(M3),
+    M4 = maps:merge(M2,M3),
+    300000 = maps:size(M4),
+    M5 = maps:from_list([{integer_to_list(I),I}||I<-Is]),
+    150000 = maps:size(M5),
+    M6 = maps:merge(M4,M5),
+    450000 = maps:size(M6),
+    M7 = maps:from_list([{float(I),I}||I<-Is]),
+    150000 = maps:size(M7),
+    M8 = maps:merge(M7,M6),
+    600000 = maps:size(M8),
+
+    #{      1 := 1,           "1" := 1,           <<1:32>> := 1      } = M8,
+    #{     10 := 10,         "10" := 10,         <<10:32>> := 10     } = M8,
+    #{    100 := 100,       "100" := 100,       <<100:32>> := 100    } = M8,
+    #{   1000 := 1000,     "1000" := 1000,     <<1000:32>> := 1000   } = M8,
+    #{  10000 := 10000,   "10000" := 10000,   <<10000:32>> := 10000  } = M8,
+    #{ 100000 := 100000, "100000" := 100000, <<100000:32>> := 100000 } = M8,
+
+    %% overlapping
+    M8 = maps:merge(M2,M8),
+    M8 = maps:merge(M3,M8),
+    M8 = maps:merge(M4,M8),
+    M8 = maps:merge(M5,M8),
+    M8 = maps:merge(M6,M8),
+    M8 = maps:merge(M7,M8),
+    M8 = maps:merge(M8,M8),
+
     %% error case
     {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge((1 bsl 65 + 3), <<>>)),
     {'EXIT',{badarg,[{maps,merge,_,_}|_]}} = (catch maps:merge(<<>>, id(#{ a => 1}))),