erts: Change external format for maps

to be: 116,Arity, K1,V1,K2,V2,...,Kn,Vn

instead of: 116,Arity, K1,K2,...,Kn, V1,V2,....,Vn

We think this will be better for future internal map structures
like HAMT. Would be bad if we need to iterate twice over HAMT
in term_to_binary, one for keys and one for values.

8 files changed, 56 insertions, 75 deletions

diff --git a/erts/doc/src/erl_ext_dist.xml b/erts/doc/src/erl_ext_dist.xml
index 9a53f3f829..fa083db4c7 100644
--- a/erts/doc/src/erl_ext_dist.xml
+++ b/erts/doc/src/erl_ext_dist.xml
@@ -581,23 +581,20 @@
 	    <cell align="center">1</cell>
 	    <cell align="center">4</cell>
 	    <cell align="center">N</cell>
-	    <cell align="center">M</cell>
 	  </row>
 	  <row>
 	    <cell align="center">116</cell>
 	    <cell align="center">Arity</cell>
-	    <cell align="center">Keys</cell>
-	    <cell align="center">Values</cell>
+	    <cell align="center">Pairs</cell>
 	  </row>
 	<tcaption></tcaption></table>
 	<p>
 	  <c>MAP_EXT</c> encodes a map. The <c>Arity</c> field is an unsigned
 	  4 byte integer in big endian format that determines the number of
-	  key-value pairs in the map. All key terms follow in the <c>Keys</c>
-	  section and then all value terms in the <c>Values</c> section. Keys
-	  and values are paired according to order; first key with first value
-	  and so on. Duplicate keys are <em>not allowed</em> within the same
-	  map.
+	  key-value pairs in the map. Key and value pairs (<c>Ki => Vi</c>)
+	  are encoded in the <c>Pairs</c> section in the following order:
+	  <c>K1, V1, K2, V2,..., Kn, Vn</c>.
+	  Duplicate keys are <em>not allowed</em> within the same map.
 	</p>
 	<p><em>Since: </em>OTP 17.0</p>
     </section>
diff --git a/erts/emulator/beam/external.c b/erts/emulator/beam/external.c
index 9671cde228..656de7c49a 100644
--- a/erts/emulator/beam/external.c
+++ b/erts/emulator/beam/external.c
@@ -2562,29 +2562,25 @@ enc_term_int(TTBEncodeContext* ctx, ErtsAtomCacheMap *acmp, Eterm obj, byte* ep,
 	    {
 		map_t *mp = (map_t*)map_val(obj);
 		Uint size = map_get_size(mp);
-		Eterm *mptr;
 
 		*ep++ = MAP_EXT;
 		put_int32(size, ep); ep += 4;
 
-		/* Push values first */
 		if (size > 0) {
-		    mptr = map_get_values(mp);
+		    Eterm *kptr = map_get_keys(mp);
+		    Eterm *vptr = map_get_values(mp);
+
 		    for (i = size-1; i >= 1; i--) {
 			WSTACK_PUSH(s, ENC_TERM);
-			WSTACK_PUSH(s, (UWord) mptr[i]);
+			WSTACK_PUSH(s, (UWord) vptr[i]);
+			WSTACK_PUSH(s, ENC_TERM);
+			WSTACK_PUSH(s, (UWord) kptr[i]);
 		    }
 
 		    WSTACK_PUSH(s, ENC_TERM);
-		    WSTACK_PUSH(s, (UWord) mptr[0]);
-
-		    mptr = map_get_keys(mp);
-		    for (i = size-1; i >= 1; i--) {
-			WSTACK_PUSH(s, ENC_TERM);
-			WSTACK_PUSH(s, (UWord) mptr[i]);
-		    }
+		    WSTACK_PUSH(s, (UWord) vptr[0]);
 
-		    obj = mptr[0];
+		    obj = kptr[0];
 		    goto L_jump_start;
 		}
 	    }
@@ -3518,16 +3514,16 @@ dec_term_atom_common:
 
 		keys  = make_tuple(hp);
 		*hp++ = make_arityval(size);
-		kptr  = hp;
 		hp   += size;
+		kptr = hp - 1;
 
 		mp    = (map_t*)hp;
 		hp   += MAP_HEADER_SIZE;
-		vptr  = hp;
 		hp   += size;
+		vptr = hp - 1;
 
-		/* kptr, first word for keys
-		 * vptr, first word for values
+		/* kptr, last word for keys
+		 * vptr, last word for values
 		 */
 
 		/*
@@ -3542,27 +3538,12 @@ dec_term_atom_common:
 		mp->keys       = keys;
 		*objp          = make_map(mp);
 
-		/* We assume the map is wellformed, meaning:
-		 * - ascending key order
-		 * - unique keys
-		 */
-
-		objp  = vptr + size - 1;
-		n     = size;
-
-		while (n-- > 0) {
-		    *objp = (Eterm) COMPRESS_POINTER(next);
-		    next  = objp;
-		    objp--;
-		}
-
-		objp  = kptr + size - 1;
-		n     = size;
-
-		while (n-- > 0) {
-		    *objp = (Eterm) COMPRESS_POINTER(next);
-		    next  = objp;
-		    objp--;
+		for (n = size; n; n--) {
+		    *vptr = (Eterm) COMPRESS_POINTER(next);
+		    *kptr = (Eterm) COMPRESS_POINTER(vptr);
+		    next  = kptr;
+		    vptr--;
+		    kptr--;
 		}
 	    }
 	    break;
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 753d6f7727..888ed8e272 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -813,16 +813,16 @@ t_map_encode_decode(Config) when is_list(Config) ->
 
     %% literally #{ b=>2, a=>1 } in the internal order
     #{ a:=1, b:=2 } =
-	erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,100,0,1,97,97,2,97,1>>),
+	erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,97,2,100,0,1,97,97,1>>),
 
 
     %% 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()
-	100,0,1,97, % a :: atom()
-	100,0,1,98, % b :: atom()
 	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()
 	>>),
 
@@ -834,11 +834,17 @@ t_map_encode_decode(Config) when is_list(Config) ->
     %% uniqueness violation
     %% literally #{ a=>1, "hi"=>"value", a=>2 }
     {'EXIT',{badarg,[{_,_,_,_}|_]}} = (catch
-	erlang:binary_to_term(<<131,116,0,0,0,3,100,0,1,97,107,0,2,104,105,100,0,1,97,97,1,107,0,5,118,97,108,117,101,97,2>>)),
+	erlang:binary_to_term(<<131,116,0,0,0,3,
+			       100,0,1,97,
+			       97,1,
+			       107,0,2,104,105,
+			       107,0,5,118,97,108,117,101,
+			       100,0,1,97,
+			       97,2>>)),
 
     %% bad size (too large)
     {'EXIT',{badarg,[{_,_,_,_}|_]}} = (catch
-	erlang:binary_to_term(<<131,116,0,0,0,12,100,0,1,97,100,0,1,98,97,1,97,1>>)),
+	erlang:binary_to_term(<<131,116,0,0,0,12,100,0,1,97,97,1,100,0,1,98,97,1>>)),
 
     %% bad size (too small) .. should fail just truncate it .. weird.
     %% possibly change external format so truncated will be #{a:=1}
@@ -852,7 +858,8 @@ map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, 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
-    ok = match_encoded_map(B0, length(Ls), [Kbin||{_,Kbin,_}<-Ls] ++ [Vbin||{_,_,Vbin}<-Ls]),
+    KVbins = lists:foldr(fun({_,Kbin,Vbin}, Acc) -> [Kbin,Vbin | Acc] end, [], Ls),
+    ok = match_encoded_map(B0, length(Ls), KVbins),
     %% decode and match it
     M1 = erlang:binary_to_term(B0),
     map_encode_decode_and_match(Pairs,Ls,M1);
diff --git a/lib/debugger/test/map_SUITE.erl b/lib/debugger/test/map_SUITE.erl
index e9f4ea1fad..741ad2dc41 100644
--- a/lib/debugger/test/map_SUITE.erl
+++ b/lib/debugger/test/map_SUITE.erl
@@ -790,16 +790,16 @@ t_map_encode_decode(Config) when is_list(Config) ->
 
     %% literally #{ b=>2, a=>1 } in the internal order
     #{ a:=1, b:=2 } =
-	erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,100,0,1,97,97,2,97,1>>),
+	erlang:binary_to_term(<<131,116,0,0,0,2,100,0,1,98,97,2,100,0,1,97,97,1>>),
 
 
     %% 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()
-	100,0,1,97, % a :: atom()
-	100,0,1,98, % b :: atom()
 	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()
 	>>),
 
@@ -829,7 +829,8 @@ map_encode_decode_and_match([{K,V}|Pairs], EncodedPairs, 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
-    ok = match_encoded_map(B0, length(Ls), [Kbin||{_,Kbin,_}<-Ls] ++ [Vbin||{_,_,Vbin}<-Ls]),
+    KVbins = lists:foldr(fun({_,Kbin,Vbin}, Acc) -> [Kbin,Vbin | Acc] end, [], Ls),
+    ok = match_encoded_map(B0, length(Ls), KVbins),
     %% decode and match it
     M1 = erlang:binary_to_term(B0),
     map_encode_decode_and_match(Pairs,Ls,M1);
diff --git a/lib/erl_interface/doc/src/ei.xml b/lib/erl_interface/doc/src/ei.xml
index 1756ee8a7d..90495eebd6 100644
--- a/lib/erl_interface/doc/src/ei.xml
+++ b/lib/erl_interface/doc/src/ei.xml
@@ -422,19 +422,18 @@ ei_x_encode_empty_list(&amp;x);
       <fsummary>Encode a map</fsummary>
       <desc>
         <p>This function encodes a map header, with a specified arity. The next
-	   <c>arity</c> terms encoded will be the keys of the map, and the next
-	   <c>arity</c> terms after that will be the corresponding values in
-	   same order.</p>
+	   <c>arity*2</c> terms encoded will be the keys and values of the map
+	   encoded in the following order: <c>K1, V1, K2, V2, ..., Kn, Vn</c>.
+	</p>
         <p>E.g. to encode the map <c>#{a => "Apple", b => "Banana"}</c>:</p>
         <pre>
 ei_x_encode_map_header(&amp;x, 2);
 ei_x_encode_atom(&amp;x, "a");
-ei_x_encode_atom(&amp;x, "b");
 ei_x_encode_string(&amp;x, "Apple");
+ei_x_encode_atom(&amp;x, "b");
 ei_x_encode_string(&amp;x, "Banana");
         </pre>
-	<p>A correctly encoded map can not have duplicate keys, but no check
-	for duplicate keys is done by this function.</p>
+	<p>A correctly encoded map can not have duplicate keys.</p>
       </desc>
     </func>
     <func>
@@ -664,10 +663,9 @@ ei_x_encode_string(&amp;x, "Banana");
       <desc>
         <p>This function decodes a map header from the binary
           format. The number of key-value pairs is returned in
-          <c>arity</c>. Keys and values follows, first all keys and then all values,
-	  which makes a total of <c>arity*2</c> terms.
-	  Keys and values are paired according to their order, the first key
-	  with the first value and so on. If <c>arity</c> is zero, it's an empty map.
+          <c>*arity</c>. Keys and values follow in the following order:
+	  <c>K1, V1, K2, V2, ..., Kn, Vn</c>. This makes a total of
+	  <c>arity*2</c> terms. If <c>arity</c> is zero, it's an empty map.
 	  A correctly encoded map does not have duplicate keys.</p>
       </desc>
     </func>
diff --git a/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c b/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c
index 790d498a1d..fcf546105b 100644
--- a/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c
+++ b/lib/erl_interface/test/ei_decode_encode_SUITE_data/ei_decode_encode_test.c
@@ -527,8 +527,9 @@ TESTCASE(test_ei_decode_encode)
 
     { /* #{atom => atom, atom => pid, port => ref }*/
 	struct Type* map[] = { &map_type,
-	    &my_atom_type, &my_atom_type, &port_type,
-	    &my_atom_type, &pid_type, &ref_type
+	    &my_atom_type, &my_atom_type,
+	    &my_atom_type, &pid_type,
+	    &port_type, &ref_type
 	};
 	decode_encode(map, 7);
     }
diff --git a/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java b/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java
index 7c1cf84e98..03c18e55a2 100644
--- a/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java
+++ b/lib/jinterface/java_src/com/ericsson/otp/erlang/OtpErlangMap.java
@@ -125,8 +125,6 @@ public class OtpErlangMap extends OtpErlangObject implements Serializable,
 
 	    for (int i = 0; i < arity; i++) {
 		keys[i] = buf.read_any();
-	    }
-	    for (int i = 0; i < arity; i++) {
 		values[i] = buf.read_any();
 	    }
 	} else {
@@ -227,8 +225,6 @@ public class OtpErlangMap extends OtpErlangObject implements Serializable,
 
 	for (int i = 0; i < arity; i++) {
 	    buf.write_any(keys[i]);
-	}
-	for (int i = 0; i < arity; i++) {
 	    buf.write_any(values[i]);
 	}
     }
diff --git a/lib/jinterface/test/jinterface_SUITE_data/Maps.java b/lib/jinterface/test/jinterface_SUITE_data/Maps.java
index 136a665f23..653defc621 100644
--- a/lib/jinterface/test/jinterface_SUITE_data/Maps.java
+++ b/lib/jinterface/test/jinterface_SUITE_data/Maps.java
@@ -42,16 +42,16 @@ class Maps {
 	runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 1, 100, 0, 1, 97, 100,
 		0, 1, 98 }, "#{a => b}", 2);
 	// make sure keys are sorted here, jinterface doesn't reorder them
-	runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 100, 0, 1, 97,
-		106, 97, 1 }, "#{2 => [],a => 1}", 3);
+	runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 106,
+			     100, 0, 1, 97, 97, 1 }, "#{2 => [],a => 1}", 3);
 	runTest(new byte[] { (byte) 131, 116, 0, 0, 0, 1, 104, 1, 97, 3, 108,
 		0, 0, 0, 1, 100, 0, 1, 114, 106 }, "#{{3} => [r]}", 4);
 
 	try {
 	    // #{2 => [],a => 1}
 	    final OtpErlangMap map = new OtpErlangMap(new OtpInputStream(
-		    new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 100, 0, 1,
-			    97, 106, 97, 1 }));
+		  new byte[] { (byte) 131, 116, 0, 0, 0, 2, 97, 2, 106,
+			       100, 0, 1, 97, 97, 1 }));
 
 	    if (map.arity() != 2) {
 		fail(5);