From 1414073af81016d54fc9157f2005301b7fcf4fe6 Mon Sep 17 00:00:00 2001
From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= <bjorn@erlang.org>
Date: Tue, 24 Mar 2015 09:29:17 +0100
Subject: beam_validator: No longer require strict literal term order

The BEAM loader will now sort keys for maps during loading, so
beam_validator should not require the keys to be ordered any order.

However, we must still ensure that literals keys are unique (which
was implicitly guaranteed by the strict ordering requirement).
---
 lib/compiler/src/beam_validator.erl                | 26 +++++++++-------------
 lib/compiler/test/beam_validator_SUITE.erl         |  4 ++--
 .../beam_validator_SUITE_data/map_field_lists.S    |  2 +-
 3 files changed, 14 insertions(+), 18 deletions(-)

diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl
index 4d4536b79c..c55919dc73 100644
--- a/lib/compiler/src/beam_validator.erl
+++ b/lib/compiler/src/beam_validator.erl
@@ -667,7 +667,7 @@ valfun_4({test,test_arity,{f,Lbl},[Tuple,Sz]}, Vst) when is_integer(Sz) ->
     set_type_reg({tuple,Sz}, Tuple, branch_state(Lbl, Vst));
 valfun_4({test,has_map_fields,{f,Lbl},Src,{list,List}}, Vst) ->
     assert_type(map, Src, Vst),
-    assert_strict_literal_termorder(List),
+    assert_unique_map_keys(List),
     branch_state(Lbl, Vst);
 valfun_4({test,is_map,{f,Lbl},[Src]}, Vst0) ->
     Vst = branch_state(Lbl, Vst0),
@@ -774,7 +774,7 @@ verify_get_map(Fail, Src, List, Vst0) ->
     assert_type(map, Src, Vst0),
     Vst1 = branch_state(Fail, Vst0),
     Keys = extract_map_keys(List),
-    assert_strict_literal_termorder(Keys),
+    assert_unique_map_keys(Keys),
     verify_get_map_pair(List,Vst0,Vst1).
 
 extract_map_keys([Key,_Val|T]) ->
@@ -794,6 +794,8 @@ verify_put_map(Fail, Src, Dst, Live, List, Vst0) ->
     Vst1 = heap_alloc(0, Vst0),
     Vst2 = branch_state(Fail, Vst1),
     Vst = prune_x_regs(Live, Vst2),
+    Keys = extract_map_keys(List),
+    assert_unique_map_keys(Keys),
     set_type_reg(map, Dst, Vst).
 
 %%
@@ -1007,29 +1009,23 @@ assert_freg_set(Fr, _) -> error({bad_source,Fr}).
 
 %% A single item list may be either a list or a register.
 %%
-%% A list with more than item must contain literals in
-%% ascending term order.
+%% A list with more than item must contain unique literals.
 %%
 %% An empty list is not allowed.
 
-assert_strict_literal_termorder([]) ->
+assert_unique_map_keys([]) ->
     %% There is no reason to use the get_map_elements and
     %% has_map_fields instructions with empty lists.
     error(empty_field_list);
-assert_strict_literal_termorder([_]) ->
+assert_unique_map_keys([_]) ->
     ok;
-assert_strict_literal_termorder([_,_|_]=Ls) ->
+assert_unique_map_keys([_,_|_]=Ls) ->
     Vs = [get_literal(L) || L <- Ls],
-    case check_strict_value_termorder(Vs) of
-	true ->  ok;
-	false -> error(not_strict_order)
+    case length(Vs) =:= sets:size(sets:from_list(Vs)) of
+	true -> ok;
+	false -> error(keys_not_unique)
     end.
 
-check_strict_value_termorder([V1|[V2|_]=Vs]) ->
-    erts_internal:cmp_term(V1, V2) < 0 andalso
-	check_strict_value_termorder(Vs);
-check_strict_value_termorder([_]) -> true.
-
 %%%
 %%% New binary matching instructions.
 %%%
diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl
index 1b1c7db0e8..551cf7661b 100644
--- a/lib/compiler/test/beam_validator_SUITE.erl
+++ b/lib/compiler/test/beam_validator_SUITE.erl
@@ -420,9 +420,9 @@ map_field_lists(Config) ->
     Errors = do_val(map_field_lists, Config),
     [{{map_field_lists,x,1},
       {{test,has_map_fields,{f,1},{x,0},
-	{list,[{atom,z},{atom,a}]}},
+	{list,[{atom,a},{atom,a}]}},
        5,
-       not_strict_order}},
+       keys_not_unique}},
      {{map_field_lists,y,1},
       {{test,has_map_fields,{f,3},{x,0},{list,[]}},
        5,
diff --git a/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S b/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S
index 9af68c82d4..5e7ccc1e5d 100644
--- a/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S
+++ b/lib/compiler/test/beam_validator_SUITE_data/map_field_lists.S
@@ -13,7 +13,7 @@
     {func_info,{atom,map_field_lists},{atom,x},1}.
   {label,2}.
     {test,is_map,{f,1},[{x,0}]}.
-    {test,has_map_fields,{f,1},{x,0},{list,[{atom,z},{atom,a}]}}.
+    {test,has_map_fields,{f,1},{x,0},{list,[{atom,a},{atom,a}]}}.
     {move,{atom,ok},{x,0}}.
     return.
 
-- 
cgit v1.2.3