aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2015-03-23 13:10:20 +0100
committerBjörn Gustavsson <[email protected]>2015-04-13 12:37:54 +0200
commit529af720ae7b663aa6a1a086b31ba9e3605ff21e (patch)
treeb395c9b16b2e07c00c3d98b163997ddc12db7a18
parentc92cf260bb888c004fb02651670d19989dbc2b74 (diff)
downloadotp-529af720ae7b663aa6a1a086b31ba9e3605ff21e.tar.gz
otp-529af720ae7b663aa6a1a086b31ba9e3605ff21e.tar.bz2
otp-529af720ae7b663aa6a1a086b31ba9e3605ff21e.zip
Sort maps keys in the loader
The map instructions require that the keys in the instructions are sorted (for flatmaps). But that is an implementation detail that should not exposed outside of the BEAM virtual machine. Therefore, make the sorting of the keys the responsibility of the loader and not the compiler. Also note that the sort order for maps with numeric keys or keys with numeric components has changed in OTP 18. That means that code compiled for OTP 17 that operated on maps with map keys might not work in OTP 18 without the sorting in the loader (although it is unlikely to be an issue in practice).
-rw-r--r--erts/emulator/beam/beam_load.c80
-rw-r--r--erts/emulator/beam/ops.tab24
-rw-r--r--erts/emulator/test/map_SUITE.erl3
3 files changed, 100 insertions, 7 deletions
diff --git a/erts/emulator/beam/beam_load.c b/erts/emulator/beam/beam_load.c
index 18e1e312ad..1a6c6c16ad 100644
--- a/erts/emulator/beam/beam_load.c
+++ b/erts/emulator/beam/beam_load.c
@@ -4082,6 +4082,86 @@ is_empty_map(LoaderState* stp, GenOpArg Lit)
}
/*
+ * Pseudo predicate map_key_sort that will sort the Rest operand for
+ * map instructions as a side effect.
+ */
+
+typedef struct SortGenOpArg {
+ Eterm term; /* Term to use for comparing */
+ GenOpArg arg; /* Original data */
+} SortGenOpArg;
+
+static int
+genopargtermcompare(SortGenOpArg* a, SortGenOpArg* b)
+{
+ return CMP_TERM(a->term, b->term);
+}
+
+static int
+map_key_sort(LoaderState* stp, GenOpArg Size, GenOpArg* Rest)
+{
+ SortGenOpArg* t;
+ unsigned size = Size.val;
+ unsigned i;
+
+ if (size == 2) {
+ return 1; /* Already sorted. */
+ }
+
+
+ t = (SortGenOpArg *) erts_alloc(ERTS_ALC_T_TMP, size*sizeof(SortGenOpArg));
+
+ /*
+ * Copy original data and sort keys to a temporary array.
+ */
+ for (i = 0; i < size; i += 2) {
+ t[i].arg = Rest[i];
+ switch (Rest[i].type) {
+ case TAG_a:
+ t[i].term = Rest[i].val;
+ ASSERT(is_atom(t[i].term));
+ break;
+ case TAG_i:
+ t[i].term = make_small(Rest[i].val);
+ break;
+ case TAG_n:
+ t[i].term = NIL;
+ break;
+ case TAG_q:
+ t[i].term = stp->literals[Rest[i].val].term;
+ break;
+ default:
+ /*
+ * Not a literal key. Not allowed. Only a single
+ * variable key is allowed in each map instruction.
+ */
+ erts_free(ERTS_ALC_T_TMP, (void *) t);
+ return 0;
+ }
+#ifdef DEBUG
+ t[i+1].term = THE_NON_VALUE;
+#endif
+ t[i+1].arg = Rest[i+1];
+ }
+
+ /*
+ * Sort the temporary array.
+ */
+ qsort((void *) t, size / 2, 2 * sizeof(SortGenOpArg),
+ (int (*)(const void *, const void *)) genopargtermcompare);
+
+ /*
+ * Copy back the sorted, original data.
+ */
+ for (i = 0; i < size; i++) {
+ Rest[i] = t[i].arg;
+ }
+
+ erts_free(ERTS_ALC_T_TMP, (void *) t);
+ return 1;
+}
+
+/*
* Replace a get_map_elements with one key to an instruction with one
* element
*/
diff --git a/erts/emulator/beam/ops.tab b/erts/emulator/beam/ops.tab
index abaa47217a..92d9ccb5eb 100644
--- a/erts/emulator/beam/ops.tab
+++ b/erts/emulator/beam/ops.tab
@@ -1473,16 +1473,24 @@ apply_last I P
# Map instructions in R17.
#
-put_map_assoc j Map Dst Live Size Rest=* | is_empty_map(Map) => \
+sorted_put_map_assoc/5
+put_map_assoc F Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \
+ sorted_put_map_assoc F Map Dst Live Size Rest
+
+sorted_put_map_exact/5
+put_map_exact F Map Dst Live Size Rest=* | map_key_sort(Size, Rest) => \
+ sorted_put_map_exact F Map Dst Live Size Rest
+
+sorted_put_map_assoc j Map Dst Live Size Rest=* | is_empty_map(Map) => \
new_map Dst Live Size Rest
-put_map_assoc F Src=s Dst Live Size Rest=* => \
+sorted_put_map_assoc F Src=s Dst Live Size Rest=* => \
update_map_assoc F Src Dst Live Size Rest
-put_map_assoc F Src Dst Live Size Rest=* => \
+sorted_put_map_assoc F Src Dst Live Size Rest=* => \
move Src x | update_map_assoc F x Dst Live Size Rest
-put_map_exact F Src=s Dst Live Size Rest=* => \
+sorted_put_map_exact F Src=s Dst Live Size Rest=* => \
update_map_exact F Src Dst Live Size Rest
-put_map_exact F Src Dst Live Size Rest=* => \
+sorted_put_map_exact F Src Dst Live Size Rest=* => \
move Src x | update_map_exact F x Dst Live Size Rest
new_map d I I
@@ -1506,8 +1514,10 @@ has_map_fields Fail Src Size Rest=* => \
get_map_element/4
-get_map_elements Fail Src=rxy Size=u==2 Rest=* => gen_get_map_element(Fail,Src,Size,Rest)
-get_map_elements Fail Src Size Rest=* => i_get_map_elements Fail Src Size Rest
+get_map_elements Fail Src=rxy Size=u==2 Rest=* => \
+ gen_get_map_element(Fail, Src, Size, Rest)
+get_map_elements Fail Src Size Rest=* | map_key_sort(Size, Rest) => \
+ i_get_map_elements Fail Src Size Rest
i_get_map_elements f s I
diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl
index 7b68e91dc5..008fa0e11b 100644
--- a/erts/emulator/test/map_SUITE.erl
+++ b/erts/emulator/test/map_SUITE.erl
@@ -164,6 +164,9 @@ t_build_and_match_literals(Config) when is_list(Config) ->
#{1:=a,2:=b,3:="c","4":="d",<<"5">>:=<<"e">>,{"6",7}:="f",8:=g} =
id(#{1=>a,2=>b,3=>"c","4"=>"d",<<"5">>=><<"e">>,{"6",7}=>"f",8=>g}),
+ #{[]:=a,42.0:=b,x:={x,y},[a,b]:=list} =
+ id(#{[]=>a,42.0=>b,x=>{x,y},[a,b]=>list}),
+
#{<<"hi all">> := 1} = id(#{<<"hi",32,"all">> => 1}),
#{a:=X,a:=X=3,b:=4} = id(#{a=>3,b=>4}), % weird but ok =)