Merge branch 'egil/maps/OTP-11616'

* egil/maps/OTP-11616: (112 commits)
  compiler: Add core compile test for maps
  compiler: Fix core parse for Maps
  compiler: Fixup #map_pair{} spec
  erts: Strengthen map_SUITE tests
  erts: Update maps_fold test to respect maps:fold/3
  stdlib: Make maps:fold/3 order-independent
  erts: Fixup enif_make_map_put on windows
  erts: Update preloaded erts_internal.beam
  hipe: Fixup update cerl pretty printer
  erts: Add map construction to driver API
  dialyzer: Add maps tests
  dialyzer: Remove dead code
  dialyzer: Reflect map_pair core changes in dialyzer
  hipe: Update cerl pretty printer
  compiler: Update inliner tests
  compiler: Squash #c_map_pair_*{} to #c_map_pair{}
  compiler: Squash #k_map_pair_*{} to #k_map_pair{}
  preloaded: Fixup export cmp_term in erts_internal
  erts: Change 'size' argument of enif_get_map_size from int* to size_t*
  erts: Fix compile error for halfword emulator
  ...

1 files changed, 463 insertions, 1 deletions

diff --git a/erts/emulator/beam/beam_emu.c b/erts/emulator/beam/beam_emu.c
index 7fecdd5c5f..89d9442526 100644
--- a/erts/emulator/beam/beam_emu.c
+++ b/erts/emulator/beam/beam_emu.c
@@ -31,6 +31,7 @@
 #include "big.h"
 #include "beam_load.h"
 #include "erl_binary.h"
+#include "erl_map.h"
 #include "erl_bits.h"
 #include "dist.h"
 #include "beam_bp.h"
@@ -701,6 +702,19 @@ extern int count_instructions;
         Fail; 								  \
     }
 
+#define IsMap(Src, Fail) if (is_not_map(Src)) { Fail; }
+
+#define HasMapField(Src, Key, Fail) if (has_not_map_field(Src, Key)) { Fail; }
+
+#define GetMapElement(Src, Key, Dst, Fail)	\
+  do {						\
+     Eterm _res = get_map_element(Src, Key);	\
+     if (is_non_value(_res)) {			\
+        Fail;					\
+     }						\
+     Dst = _res;				\
+  } while (0)
+
 #define IsFunction(X, Action)			\
   do {						\
      if ( !(is_any_fun(X)) ) {			\
@@ -944,7 +958,13 @@ static BeamInstr* apply_fun(Process* p, Eterm fun,
 			    Eterm args, Eterm* reg) NOINLINE;
 static Eterm new_fun(Process* p, Eterm* reg,
 		     ErlFunEntry* fe, int num_free) NOINLINE;
-
+static Eterm new_map(Process* p, Eterm* reg, BeamInstr* I) NOINLINE;
+static Eterm update_map_assoc(Process* p, Eterm* reg,
+			      Eterm map, BeamInstr* I) NOINLINE;
+static Eterm update_map_exact(Process* p, Eterm* reg,
+			      Eterm map, BeamInstr* I) NOINLINE;
+static int has_not_map_field(Eterm map, Eterm key);
+static Eterm get_map_element(Eterm map, Eterm key);
 
 /*
  * Functions not directly called by process_main(). OK to inline.
@@ -2323,6 +2343,55 @@ void process_main(void)
      Goto(*I);
  }
 
+ OpCase(new_map_jdII): {
+     Eterm res;
+
+     x(0) = r(0);
+     SWAPOUT;
+     res = new_map(c_p, reg, I);
+     SWAPIN;
+     r(0) = x(0);
+     StoreResult(res, Arg(1));
+     Next(4+Arg(3));
+ }
+
+ OpCase(update_map_assoc_jddII): {
+     Eterm res;
+     Eterm map;
+
+     GetArg1(1, map);
+     x(0) = r(0);
+     SWAPOUT;
+     res = update_map_assoc(c_p, reg, map, I);
+     SWAPIN;
+     if (is_value(res)) {
+	 r(0) = x(0);
+	 StoreResult(res, Arg(2));
+	 Next(5+Arg(4));
+     } else {
+	 goto badarg;
+     }
+ }
+
+ OpCase(update_map_exact_jddII): {
+     Eterm res;
+     Eterm map;
+
+     GetArg1(1, map);
+     x(0) = r(0);
+     SWAPOUT;
+     res = update_map_exact(c_p, reg, map, I);
+     SWAPIN;
+     if (is_value(res)) {
+	 r(0) = x(0);
+	 StoreResult(res, Arg(2));
+	 Next(5+Arg(4));
+     } else {
+	 goto badarg;
+     }
+ }
+
+
     /*
      * All guards with zero arguments have special instructions:
      * 	self/0
@@ -5031,6 +5100,8 @@ translate_gc_bif(void* gcf)
 	return bit_size_1;
     } else if (gcf == erts_gc_byte_size_1) {
 	return byte_size_1;
+    } else if (gcf == erts_gc_map_size_1) {
+	return map_size_1;
     } else if (gcf == erts_gc_abs_1) {
 	return abs_1;
     } else if (gcf == erts_gc_float_1) {
@@ -6227,6 +6298,397 @@ new_fun(Process* p, Eterm* reg, ErlFunEntry* fe, int num_free)
     return make_fun(funp);
 }
 
+static int has_not_map_field(Eterm map, Eterm key)
+{
+    map_t* mp;
+    Eterm* keys;
+    Uint i;
+    Uint n;
+
+    mp   = (map_t *)map_val(map);
+    keys = map_get_keys(mp);
+    n    = map_get_size(mp);
+    if (is_immed(key)) {
+	for (i = 0; i < n; i++) {
+	    if (keys[i] == key) {
+		return 0;
+	    }
+	}
+    } else {
+	for (i = 0; i <  n; i++) {
+	    if (EQ(keys[i], key)) {
+		return 0;
+	    }
+	}
+    }
+    return 1;
+}
+
+static Eterm get_map_element(Eterm map, Eterm key)
+{
+    map_t *mp;
+    Eterm* ks, *vs;
+    Uint i;
+    Uint n;
+
+    mp = (map_t *)map_val(map);
+    ks = map_get_keys(mp);
+    vs = map_get_values(mp);
+    n  = map_get_size(mp);
+    if (is_immed(key)) {
+	for (i = 0; i < n; i++) {
+	    if (ks[i] == key) {
+		return vs[i];
+	    }
+	}
+    } else {
+	for (i = 0; i < n; i++) {
+	    if (EQ(ks[i], key)) {
+		return vs[i];
+	    }
+	}
+    }
+    return THE_NON_VALUE;
+}
+
+#define GET_TERM(term, dest)					\
+do {								\
+    Eterm src = (Eterm)(term);					\
+    switch (src & _TAG_IMMED1_MASK) {				\
+    case (R_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER:	\
+	dest = x(0);						\
+	break;							\
+    case (X_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER:	\
+	dest = x(src >> _TAG_IMMED1_SIZE);			\
+	break;							\
+    case (Y_REG_DEF << _TAG_PRIMARY_SIZE) | TAG_PRIMARY_HEADER:	\
+	dest = y(src >> _TAG_IMMED1_SIZE);			\
+	break;							\
+    default:							\
+	dest = src;						\
+	break;							\
+    }								\
+} while(0)
+
+
+static Eterm
+new_map(Process* p, Eterm* reg, BeamInstr* I)
+{
+    Uint n = Arg(3);
+    Uint i;
+    Uint need = n + 1 /* hdr */ + 1 /*size*/ + 1 /* ptr */ + 1 /* arity */;
+    Eterm keys;
+    Eterm *mhp,*thp;
+    Eterm *E;
+    BeamInstr *ptr;
+    map_t *mp;
+
+    if (HeapWordsLeft(p) < need) {
+	erts_garbage_collect(p, need, reg, Arg(2));
+    }
+
+    thp    = p->htop;
+    mhp    = thp + 1 + n/2;
+    E      = p->stop;
+    ptr    = &Arg(4);
+    keys   = make_tuple(thp);
+    *thp++ = make_arityval(n/2);
+
+    mp = (map_t *)mhp; mhp += MAP_HEADER_SIZE;
+    mp->thing_word = MAP_HEADER;
+    mp->size = n/2;
+    mp->keys = keys;
+
+    for (i = 0; i < n/2; i++) {
+	GET_TERM(*ptr++, *thp++);
+	GET_TERM(*ptr++, *mhp++);
+    }
+    p->htop = mhp;
+    return make_map(mp);
+}
+
+static Eterm
+update_map_assoc(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
+{
+    Uint n;
+    Uint num_old;
+    Uint num_updates;
+    Uint need;
+    map_t *old_mp, *mp;
+    Eterm res;
+    Eterm* hp;
+    Eterm* E;
+    Eterm* old_keys;
+    Eterm* old_vals;
+    BeamInstr* new_p;
+    Eterm new_key;
+    Eterm* kp;
+
+    if (is_not_map(map)) {
+	return THE_NON_VALUE;
+    }
+
+    old_mp = (map_t *) map_val(map);
+    num_old = map_get_size(old_mp);
+
+    /*
+     * If the old map is empty, create a new map.
+     */
+
+    if (num_old == 0) {
+	return new_map(p, reg, I+1);
+    }
+
+    /*
+     * Allocate heap space for the worst case (i.e. all keys in the
+     * update list are new).
+     */
+
+    num_updates = Arg(4) / 2;
+    need = 2*(num_old+num_updates) + 1 + MAP_HEADER_SIZE;
+    if (HeapWordsLeft(p) < need) {
+	Uint live = Arg(3);
+	reg[live] = map;
+	erts_garbage_collect(p, need, reg, live+1);
+	map      = reg[live];
+	old_mp   = (map_t *)map_val(map);
+    }
+
+    /*
+     * Build the skeleton for the map, ready to be filled in.
+     *
+     * +-----------------------------------+
+     * | (Space for aritvyal for keys)     | <-----------+
+     * +-----------------------------------+		 |
+     * | (Space for key 1)		   |		 |    <-- kp
+     * +-----------------------------------+		 |
+     *        .				    		 |
+     *        .				    		 |
+     *        .				    		 |
+     * +-----------------------------------+		 |
+     * | (Space for last key)		   |		 |
+     * +-----------------------------------+		 |
+     * | MAP_HEADER			   |		 |
+     * +-----------------------------------+		 |
+     * | (Space for number of keys/values) |		 |
+     * +-----------------------------------+		 |
+     * | Boxed tuple pointer            >----------------+
+     * +-----------------------------------+
+     * | (Space for value 1)		   |                  <-- hp
+     * +-----------------------------------+
+     */
+
+    E = p->stop;
+    kp = p->htop + 1;		/* Point to first key */
+    hp = kp + num_old + num_updates;
+
+    res = make_map(hp);
+    mp = (map_t *)hp;
+    hp += MAP_HEADER_SIZE;
+    mp->thing_word = MAP_HEADER;
+    mp->keys = make_tuple(kp-1);
+
+    old_vals = map_get_values(old_mp);
+    old_keys = map_get_keys(old_mp);
+
+    new_p = &Arg(5);
+    GET_TERM(*new_p, new_key);
+    n = num_updates;
+
+    /*
+     * Fill in keys and values, until we run out of either updates
+     * or old values and keys.
+     */
+
+    for (;;) {
+	Eterm key;
+	Sint c;
+
+	ASSERT(kp < (Eterm *)mp);
+	key = *old_keys;
+	if ((c = CMP_TERM(key, new_key)) < 0) {
+	    /* Copy old key and value */
+	    *kp++ = key;
+	    *hp++ = *old_vals;
+	    old_keys++, old_vals++, num_old--;
+	} else {		/* Replace or insert new */
+	    GET_TERM(new_p[1], *hp++);
+	    if (c > 0) {	/* If new new key */
+		*kp++ = new_key;
+	    } else {		/* If replacement */
+		*kp++ = key;
+		old_keys++, old_vals++, num_old--;
+	    }
+	    n--;
+	    if (n == 0) {
+		break;
+	    } else {
+		new_p += 2;
+		GET_TERM(*new_p, new_key);
+	    }
+	}
+	if (num_old == 0) {
+	    break;
+	}
+    }
+
+    /*
+     * At this point, we have run out of either old keys and values,
+     * or the update list. In other words, at least of one n and
+     * num_old must be zero.
+     */
+
+    if (n > 0) {
+	/*
+	 * All old keys and values have been copied, but there
+	 * are still new keys and values in the update list that
+	 * must be copied.
+	 */
+	ASSERT(num_old == 0);
+	while (n-- > 0) {
+	    GET_TERM(new_p[0], *kp++);
+	    GET_TERM(new_p[1], *hp++);
+	    new_p += 2;
+	}
+    } else {
+	/*
+	 * All updates are now done. We may still have old
+	 * keys and values that we must copy.
+	 */
+	ASSERT(n == 0);
+	while (num_old-- > 0) {
+	    ASSERT(kp < (Eterm *)mp);
+	    *kp++ = *old_keys++;
+	    *hp++ = *old_vals++;
+	}
+    }
+
+    /*
+     * Calculate how many values that are unused at the end of the
+     * key tuple and fill it out with a bignum header.
+     */
+    if ((n = (Eterm *)mp - kp) > 0) {
+	*kp = make_pos_bignum_header(n-1);
+    }
+
+    /*
+     * Fill in the size of the map in both the key tuple and in the map.
+     */
+
+    n = kp - p->htop - 1;	/* Actual number of keys/values */
+    *p->htop = make_arityval(n);
+    mp->size = n;
+    p->htop = hp;
+    return res;
+}
+
+/*
+ * Update values for keys that already exist in the map.
+ */
+
+static Eterm
+update_map_exact(Process* p, Eterm* reg, Eterm map, BeamInstr* I)
+{
+    Uint n;
+    Uint i;
+    Uint num_old;
+    Uint need;
+    map_t *old_mp, *mp;
+    Eterm res;
+    Eterm* hp;
+    Eterm* E;
+    Eterm* old_keys;
+    Eterm* old_vals;
+    BeamInstr* new_p;
+    Eterm new_key;
+
+    if (is_not_map(map)) {
+	return THE_NON_VALUE;
+    }
+
+    old_mp = (map_t *) map_val(map);
+    num_old = map_get_size(old_mp);
+
+    /*
+     * If the old map is empty, create a new map.
+     */
+
+    if (num_old == 0) {
+	return new_map(p, reg, I+1);
+    }
+
+    /*
+     * Allocate the exact heap space needed.
+     */
+
+    need = num_old + MAP_HEADER_SIZE;
+    if (HeapWordsLeft(p) < need) {
+	Uint live = Arg(3);
+	reg[live] = map;
+	erts_garbage_collect(p, need, reg, live+1);
+	map      = reg[live];
+	old_mp   = (map_t *)map_val(map);
+    }
+
+    /*
+     * Update map, keeping the old key tuple.
+     */
+
+    hp = p->htop;
+    E = p->stop;
+
+    old_vals = map_get_values(old_mp);
+    old_keys = map_get_keys(old_mp);
+
+    res = make_map(hp);
+    mp = (map_t *)hp;
+    hp += MAP_HEADER_SIZE;
+    mp->thing_word = MAP_HEADER;
+    mp->size = num_old;
+    mp->keys = old_mp->keys;
+
+    /* Get array of key/value pairs to be updated */
+    new_p = &Arg(5);
+    GET_TERM(*new_p, new_key);
+
+    /* Update all values */
+    n = Arg(4) / 2;		/* Number of values to be updated */
+    ASSERT(n > 0);
+    for (i = 0; i < num_old; i++) {
+	if (!EQ(*old_keys, new_key)) {
+	    /* Not same keys */
+	    *hp++ = *old_vals;
+	} else {
+	    GET_TERM(new_p[1], *hp);
+	    hp++;
+	    n--;
+	    if (n == 0) {
+		/*
+		 * All updates done. Copy remaining values
+		 * and return the result.
+		 */
+		for (i++, old_vals++; i < num_old; i++) {
+		    *hp++ = *old_vals++;
+		}
+		ASSERT(hp == p->htop + need);
+		p->htop = hp;
+		return res;
+	    } else {
+		new_p += 2;
+		GET_TERM(*new_p, new_key);
+	    }
+	}
+	old_vals++, old_keys++;
+    }
+
+    /*
+     * Updates left. That means that at least one the keys in the
+     * update list did not previously exist.
+     */
+    ASSERT(hp == p->htop + need);
+    return THE_NON_VALUE;
+}
+#undef GET_TERM
 
 int catchlevel(Process *p)
 {