Merge branch 'egil/nox/maps-match_specs/OTP-12270'

* egil/nox/maps-match_specs/OTP-12270:
  erts: Fix return value from erts_maps_get to be const
  Properly support maps in match_specs
  Support maps in ms_transform
  Return pointer to value in erts_maps_get()

7 files changed, 377 insertions, 142 deletions

diff --git a/erts/doc/src/match_spec.xml b/erts/doc/src/match_spec.xml
index 334b47d34c..b4cc8e9f78 100644
--- a/erts/doc/src/match_spec.xml
+++ b/erts/doc/src/match_spec.xml
@@ -76,22 +76,26 @@
        { GuardFunction, ConditionExpression, ... }
       </item>
       <item>BoolFunction ::= <c><![CDATA[is_atom]]></c> |
-      <c><![CDATA[is_float]]></c> | <c><![CDATA[is_integer]]></c> | <c><![CDATA[is_list]]></c> |
-      <c><![CDATA[is_number]]></c> | <c><![CDATA[is_pid]]></c> | <c><![CDATA[is_port]]></c> |
-      <c><![CDATA[is_reference]]></c> | <c><![CDATA[is_tuple]]></c> | <c><![CDATA[is_binary]]></c> |
-      <c><![CDATA[is_function]]></c> | <c><![CDATA[is_record]]></c> | <c><![CDATA[is_seq_trace]]></c> |
-      <c><![CDATA['and']]></c> | <c><![CDATA['or']]></c> | <c><![CDATA['not']]></c> | <c><![CDATA['xor']]></c> | 
-      <c><![CDATA[andalso]]></c> | <c><![CDATA[orelse]]></c></item>
+        <c><![CDATA[is_float]]></c> | <c><![CDATA[is_integer]]></c> |
+        <c><![CDATA[is_list]]></c> | <c><![CDATA[is_number]]></c> |
+        <c><![CDATA[is_pid]]></c> | <c><![CDATA[is_port]]></c> |
+        <c><![CDATA[is_reference]]></c> | <c><![CDATA[is_tuple]]></c> |
+        <c><![CDATA[is_map]]></c> | <c><![CDATA[is_binary]]></c> |
+        <c><![CDATA[is_function]]></c> | <c><![CDATA[is_record]]></c> |
+        <c><![CDATA[is_seq_trace]]></c> | <c><![CDATA['and']]></c> |
+        <c><![CDATA['or']]></c> | <c><![CDATA['not']]></c> |
+        <c><![CDATA['xor']]></c> | <c><![CDATA[andalso]]></c> |
+        <c><![CDATA[orelse]]></c></item>
       <item>ConditionExpression ::= ExprMatchVariable | { GuardFunction } |
        { GuardFunction, ConditionExpression, ... } | TermConstruct
       </item>
       <item>ExprMatchVariable ::= MatchVariable (bound in the MatchHead) | 
       <c><![CDATA['$_']]></c> | <c><![CDATA['$$']]></c></item>
-      <item>TermConstruct = {{}} | {{ ConditionExpression, ... }} | 
-      <c><![CDATA[[]]]></c> | [ConditionExpression, ...] | NonCompositeTerm | Constant
-      </item>
-      <item>NonCompositeTerm ::= term() (not list or tuple)
-      </item>
+      <item>TermConstruct = {{}} | {{ ConditionExpression, ... }} |
+        <c><![CDATA[[]]]></c> | [ConditionExpression, ...] |
+        <c><![CDATA[#{}]]></c> | #{term() => ConditionExpression, ...} |
+        NonCompositeTerm | Constant</item>
+      <item>NonCompositeTerm ::= term() (not list or tuple or map)</item>
       <item>Constant ::= {<c><![CDATA[const]]></c>, term()}
       </item>
       <item>GuardFunction ::= BoolFunction | <c><![CDATA[abs]]></c> |
@@ -134,22 +138,26 @@
        { GuardFunction, ConditionExpression, ... }
       </item>
       <item>BoolFunction ::= <c><![CDATA[is_atom]]></c> |
-      <c><![CDATA[is_float]]></c> | <c><![CDATA[is_integer]]></c> | <c><![CDATA[is_list]]></c> |
-      <c><![CDATA[is_number]]></c> | <c><![CDATA[is_pid]]></c> | <c><![CDATA[is_port]]></c> |
-      <c><![CDATA[is_reference]]></c> | <c><![CDATA[is_tuple]]></c> | <c><![CDATA[is_binary]]></c> |
-      <c><![CDATA[is_function]]></c> | <c><![CDATA[is_record]]></c> | <c><![CDATA[is_seq_trace]]></c> |
-      <c><![CDATA['and']]></c> | <c><![CDATA['or']]></c> | <c><![CDATA['not']]></c> | <c><![CDATA['xor']]></c> |
-      <c><![CDATA[andalso]]></c> | <c><![CDATA[orelse]]></c></item>
+        <c><![CDATA[is_float]]></c> | <c><![CDATA[is_integer]]></c> |
+        <c><![CDATA[is_list]]></c> | <c><![CDATA[is_number]]></c> |
+        <c><![CDATA[is_pid]]></c> | <c><![CDATA[is_port]]></c> |
+        <c><![CDATA[is_reference]]></c> | <c><![CDATA[is_tuple]]></c> |
+        <c><![CDATA[is_map]]></c> | <c><![CDATA[is_binary]]></c> |
+        <c><![CDATA[is_function]]></c> | <c><![CDATA[is_record]]></c> |
+        <c><![CDATA[is_seq_trace]]></c> | <c><![CDATA['and']]></c> |
+        <c><![CDATA['or']]></c> | <c><![CDATA['not']]></c> |
+        <c><![CDATA['xor']]></c> | <c><![CDATA[andalso]]></c> |
+        <c><![CDATA[orelse]]></c></item>
       <item>ConditionExpression ::= ExprMatchVariable | { GuardFunction } |
        { GuardFunction, ConditionExpression, ... } | TermConstruct
       </item>
       <item>ExprMatchVariable ::= MatchVariable (bound in the MatchHead) |
       <c><![CDATA['$_']]></c> | <c><![CDATA['$$']]></c></item>
       <item>TermConstruct = {{}} | {{ ConditionExpression, ... }} |
-      <c><![CDATA[[]]]></c> | [ConditionExpression, ...] | NonCompositeTerm | Constant
-      </item>
-      <item>NonCompositeTerm ::= term() (not list or tuple)
-      </item>
+        <c><![CDATA[[]]]></c> | [ConditionExpression, ...] | #{} |
+        #{term() => ConditionExpression, ...} | NonCompositeTerm |
+        Constant</item>
+      <item>NonCompositeTerm ::= term() (not list or tuple or map)</item>
       <item>Constant ::= {<c><![CDATA[const]]></c>, term()}
       </item>
       <item>GuardFunction ::= BoolFunction | <c><![CDATA[abs]]></c> |
@@ -172,9 +180,10 @@
       <title>Functions allowed in all types of match specifications</title>
       <p>The different functions allowed in <c><![CDATA[match_spec]]></c> work like this:
         </p>
-      <p><em>is_atom, is_float, is_integer, is_list, is_number, is_pid, is_port, is_reference, is_tuple, is_binary, is_function: </em> Like the corresponding guard tests in
-        Erlang, return <c><![CDATA[true]]></c> or <c><![CDATA[false]]></c>.
-        </p>
+      <p><em>is_atom, is_float, is_integer, is_list, is_number, is_pid, is_port,
+        is_reference, is_tuple, is_map, is_binary, is_function:</em> Like the
+        corresponding guard tests in Erlang, return <c><![CDATA[true]]></c> or
+        <c><![CDATA[false]]></c>.</p>
       <p><em>is_record: </em>Takes an additional parameter, which SHALL
         be the result of <c><![CDATA[record_info(size, <record_type>)]]></c>,
         like in <c><![CDATA[{is_record, '$1', rectype, record_info(size, rectype)}]]></c>.
diff --git a/erts/emulator/beam/erl_db_util.c b/erts/emulator/beam/erl_db_util.c
index 3927615e04..b9fd3b208e 100644
--- a/erts/emulator/beam/erl_db_util.c
+++ b/erts/emulator/beam/erl_db_util.c
@@ -198,11 +198,6 @@ set_match_trace(Process *tracee_p, Eterm fail_term, Eterm tracer,
     return ret;
 }
 
-
-/* Type checking... */
-
-#define BOXED_IS_TUPLE(Boxed) is_arity_value(*boxed_val((Boxed)))
-
 /*
 **
 ** Types and enum's (compiled matches)
@@ -218,6 +213,8 @@ typedef enum {
     matchTuple,
     matchPushT,
     matchPushL,
+    matchPushM,
+    matchPushK,
     matchPop,
     matchBind,
     matchCmp,
@@ -227,11 +224,13 @@ typedef enum {
     matchEqRef,
     matchEq,
     matchList,
+    matchMap,
     matchSkip,
     matchPushC,
     matchConsA, /* Car is below Cdr */
     matchConsB, /* Cdr is below Car (unusual) */
     matchMkTuple,
+    matchMkMap,
     matchCall0,
     matchCall1,
     matchCall2,
@@ -856,6 +855,13 @@ static int match_compact(ErlHeapFragment *expr, DMCErrInfo *err_info);
 static Uint my_size_object(Eterm t);
 static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap);
 
+/* Guard subroutines */
+static void
+dmc_rearrange_constants(DMCContext *context, DMC_STACK_TYPE(UWord) *text,
+                        int textpos, Eterm *p, Uint nelems);
+static DMCRet
+dmc_array(DMCContext *context, DMCHeap *heap, DMC_STACK_TYPE(UWord) *text,
+          Eterm *p, Uint nelems, int *constant);
 /* Guard compilation */
 static void do_emit_constant(DMCContext *context, DMC_STACK_TYPE(UWord) *text,
 			     Eterm t);
@@ -869,6 +875,9 @@ static DMCRet dmc_tuple(DMCContext *context,
 		       DMC_STACK_TYPE(UWord) *text,
 		       Eterm t,
 		       int *constant);
+static DMCRet
+dmc_map(DMCContext *context, DMCHeap *heap, DMC_STACK_TYPE(UWord) *text,
+        Eterm t, int *constant);
 static DMCRet dmc_variable(DMCContext *context,
 			   DMCHeap *heap,
 			   DMC_STACK_TYPE(UWord) *text,
@@ -888,12 +897,14 @@ static DMCRet compile_guard_expr(DMCContext *context,
 				    DMCHeap *heap,
 				    DMC_STACK_TYPE(UWord) *text,
 				    Eterm t);
-/* match expression subroutine */
+/* match expression subroutines */
 static DMCRet dmc_one_term(DMCContext *context, 
 			   DMCHeap *heap,
 			   DMC_STACK_TYPE(Eterm) *stack,
 			   DMC_STACK_TYPE(UWord) *text,
 			   Eterm c);
+static Eterm
+dmc_private_copy(DMCContext *context, Eterm c);
 
 
 #ifdef DMC_DEBUG
@@ -1364,7 +1375,51 @@ restart:
 	for (;;) {
 	    switch (t & _TAG_PRIMARY_MASK) {
 	    case TAG_PRIMARY_BOXED:
-		if (!BOXED_IS_TUPLE(t)) {
+                if (is_map(t)) {
+                    num_iters = map_get_size(map_val(t));
+                    if (!structure_checked) {
+                        DMC_PUSH(text, matchMap);
+                        DMC_PUSH(text, num_iters);
+                    }
+                    structure_checked = 0;
+                    for (i = 0; i < num_iters; ++i) {
+                        Eterm key = map_get_keys(map_val(t))[i];
+                        if (db_is_variable(key) >= 0) {
+                            if (context.err_info) {
+                                add_dmc_err(context.err_info,
+                                            "Variable found in map key.",
+                                            -1, 0UL, dmcError);
+                            }
+                            goto error;
+                        } else if (key == am_Underscore) {
+                            if (context.err_info) {
+                                add_dmc_err(context.err_info,
+                                            "Underscore found in map key.",
+                                            -1, 0UL, dmcError);
+                            }
+                            goto error;
+                        }
+                        DMC_PUSH(text, matchPushK);
+                        ++(context.stack_used);
+                        DMC_PUSH(text, dmc_private_copy(&context, key));
+                    }
+                    if (context.stack_used > context.stack_need) {
+                        context.stack_need = context.stack_used;
+                    }
+                    for (i = num_iters; i--; ) {
+                        Eterm value = map_get_values(map_val(t))[i];
+                        DMC_PUSH(text, matchPop);
+                        --(context.stack_used);
+                        res = dmc_one_term(&context, &heap, &stack, &text,
+                                           value);
+                        ASSERT(res != retFail);
+                        if (res == retRestart) {
+                            goto restart;
+                        }
+                    }
+                    break;
+                }
+		if (!is_tuple(t)) {
 		    goto simple_term;
 		}
 		num_iters = arityval(*tuple_val(t));
@@ -1715,10 +1770,8 @@ Eterm db_prog_match(Process *c_p, Binary *bprog,
 		    Uint32 *return_flags)
 {
     MatchProg *prog = Binary2MatchProg(bprog);
-    Eterm *ep;
-    Eterm *tp;
+    const Eterm *ep, *tp, **sp;
     Eterm t;
-    Eterm **sp;
     Eterm *esp;
     MatchVariable* variables;
     BeamInstr *cp;
@@ -1808,7 +1861,7 @@ Eterm db_prog_match(Process *c_p, Binary *bprog,
 restart:
     ep = &term;
     esp = (Eterm*)((char*)mpsp->u.heap + prog->stack_offset);
-    sp = (Eterm **) esp;
+    sp = (const Eterm **)esp;
     ret = am_true;
     do_catch = 0;
     fail_label = -1;
@@ -1887,6 +1940,34 @@ restart:
 	    *sp++ = list_val_rel(*ep,base);
 	    ++ep;
 	    break;
+        case matchMap:
+            if (!is_map_rel(*ep, base)) {
+                FAIL();
+            }
+            n = *pc++;
+            if (map_get_size(map_val_rel(*ep, base)) < n) {
+                FAIL();
+            }
+            ep = map_val_rel(*ep, base);
+            break;
+        case matchPushM:
+            if (!is_map_rel(*ep, base)) {
+                FAIL();
+            }
+            n = *pc++;
+            if (map_get_size(map_val_rel(*ep, base)) < n) {
+                FAIL();
+            }
+            *sp++ = map_val_rel(*ep++, base);
+            break;
+        case matchPushK:
+            t = (Eterm) *pc++;
+            tp = erts_maps_get_rel(t, make_map_rel(ep, base), base);
+            if (!tp) {
+                FAIL();
+            }
+            *sp++ = tp;
+            break;
 	case matchPop:
 	    ep = *(--sp);
 	    break;
@@ -1987,6 +2068,23 @@ restart:
 	    }
 	    *esp++ = t;
 	    break;
+        case matchMkMap:
+            n = *pc++;
+            ehp = HAllocX(build_proc, 1 + MAP_HEADER_SIZE + n, HEAP_XTRA);
+            t = *ehp++ = *--esp;
+            {
+                map_t *m = (map_t *)ehp;
+                m->thing_word = MAP_HEADER;
+                m->size = n;
+                m->keys = t;
+            }
+            t = make_map(ehp);
+            ehp += MAP_HEADER_SIZE;
+            while (n--) {
+                *ehp++ = *--esp;
+            }
+            *esp++ = t;
+            break;
 	case matchCall0:
 	    bif = (Eterm (*)(Process*, ...)) *pc++;
 	    t = (*bif)(build_proc, bif_args);
@@ -3168,7 +3266,7 @@ int db_has_variable(Eterm obj)
 	return(db_has_variable(obj));  /* Non wellformed list or [] */
     }
     case TAG_PRIMARY_BOXED: 
-	if (!BOXED_IS_TUPLE(obj)) {
+	if (!is_tuple(obj)) {
 	    return 0;
 	} else {
 	    Eterm *tuple = tuple_val(obj);
@@ -3243,7 +3341,6 @@ static DMCRet dmc_one_term(DMCContext *context,
 {
     Sint n;
     Eterm *hp;
-    ErlHeapFragment *tmp_mb;
     Uint sz, sz2, sz3;
     Uint i, j;
 
@@ -3334,6 +3431,13 @@ static DMCRet dmc_one_term(DMCContext *context,
 	    DMC_PUSH(*text, n);
 	    DMC_PUSH(*stack, c);
 	    break;
+        case (_TAG_HEADER_MAP >> _TAG_PRIMARY_SIZE):
+            n = map_get_size(map_val(c));
+            DMC_PUSH(*text, matchPushM);
+            ++(context->stack_used);
+            DMC_PUSH(*text, n);
+            DMC_PUSH(*stack, c);
+            break;
 	case (_TAG_HEADER_REF >> _TAG_PRIMARY_SIZE):
 	{
 	    Eterm* ref_val = internal_ref_val(c);
@@ -3415,16 +3519,8 @@ static DMCRet dmc_one_term(DMCContext *context,
 #endif
 	    break;
 	default: /* BINARY, FUN, VECTOR, or EXTERNAL */
-	    /*
-	    ** Make a private copy...
-	    */
-	    n = size_object(c);
-	    tmp_mb = new_message_buffer(n);
-	    hp = tmp_mb->mem;
 	    DMC_PUSH(*text, matchEqBin);
-	    DMC_PUSH(*text, copy_struct(c, n, &hp, &(tmp_mb->off_heap)));
-	    tmp_mb->next = context->save;
-	    context->save = tmp_mb;
+            DMC_PUSH(*text, dmc_private_copy(context, c));
 	    break;
 	}
 	break;
@@ -3437,6 +3533,22 @@ static DMCRet dmc_one_term(DMCContext *context,
 }
 
 /*
+** Make a private copy of a term in a context.
+*/
+
+static Eterm
+dmc_private_copy(DMCContext *context, Eterm c)
+{
+    Uint n = size_object(c);
+    ErlHeapFragment *tmp_mb = new_message_buffer(n);
+    Eterm *hp = tmp_mb->mem;
+    Eterm copy = copy_struct(c, n, &hp, &(tmp_mb->off_heap));
+    tmp_mb->next = context->save;
+    context->save = tmp_mb;
+    return copy;
+}
+
+/*
 ** Match guard compilation
 */
 
@@ -3527,57 +3639,78 @@ static DMCRet dmc_list(DMCContext *context,
     return retOk;
 }
 
-static DMCRet dmc_tuple(DMCContext *context,
-		       DMCHeap *heap,
-		       DMC_STACK_TYPE(UWord) *text,
-		       Eterm t,
-		       int *constant)
+static void
+dmc_rearrange_constants(DMCContext *context, DMC_STACK_TYPE(UWord) *text,
+                        int textpos, Eterm *p, Uint nelems)
 {
     DMC_STACK_TYPE(UWord) instr_save;
+    Uint i;
+
+    DMC_INIT_STACK(instr_save);
+    while (DMC_STACK_NUM(*text) > textpos) {
+        DMC_PUSH(instr_save, DMC_POP(*text));
+    }
+    for (i = nelems; i--;) {
+        do_emit_constant(context, text, p[i]);
+    }
+    while(!DMC_EMPTY(instr_save)) {
+        DMC_PUSH(*text, DMC_POP(instr_save));
+    }
+    DMC_FREE(instr_save);
+}
+
+static DMCRet
+dmc_array(DMCContext *context, DMCHeap *heap, DMC_STACK_TYPE(UWord) *text,
+          Eterm *p, Uint nelems, int *constant)
+{
     int all_constant = 1;
     int textpos = DMC_STACK_NUM(*text);
-    Eterm *p = tuple_val(t);
-    Uint nelems = arityval(*p);
     Uint i;
-    int c;
-    DMCRet ret;
 
     /*
-    ** We remember where we started to layout code, 
+    ** We remember where we started to layout code,
     ** assume all is constant and back up and restart if not so.
-    ** The tuple should be laid out with the last element first,
-    ** so we can memcpy the tuple to the eheap.
+    ** The array should be laid out with the last element first,
+    ** so we can memcpy it to the eheap.
     */
-    for (i = nelems; i > 0; --i) {
-	if ((ret = dmc_expr(context, heap, text, p[i], &c)) != retOk)
-	    return ret;
-	if (!c && all_constant) {
-	    all_constant = 0;
-	    if (i < nelems) {
-		Uint j;
+    for (i = nelems; i--;) {
+        DMCRet ret;
+        int c;
 
-		/*
-		 * Oops, we need to relayout the constants.
-		 * Save the already laid out instructions.
-		 */
-		DMC_INIT_STACK(instr_save);
-		while (DMC_STACK_NUM(*text) > textpos) 
-		    DMC_PUSH(instr_save, DMC_POP(*text));
-		for (j = nelems; j > i; --j)
-		    do_emit_constant(context, text, p[j]);
-		while(!DMC_EMPTY(instr_save))
-		    DMC_PUSH(*text, DMC_POP(instr_save));
-		DMC_FREE(instr_save);
-	    }
-	} else if (c && !all_constant) {
-	    /* push a constant */
-	    do_emit_constant(context, text, p[i]);
-	}
+        ret = dmc_expr(context, heap, text, p[i], &c);
+        if (ret != retOk) {
+            return ret;
+        }
+        if (!c && all_constant) {
+            all_constant = 0;
+            if (i < nelems - 1) {
+                dmc_rearrange_constants(context, text, textpos,
+                                        p + i + 1, nelems - i - 1);
+            }
+        } else if (c && !all_constant) {
+            do_emit_constant(context, text, p[i]);
+        }
+    }
+    *constant = all_constant;
+    return retOk;
+}
+
+static DMCRet
+dmc_tuple(DMCContext *context, DMCHeap *heap, DMC_STACK_TYPE(UWord) *text,
+          Eterm t, int *constant)
+{
+    int all_constant;
+    Eterm *p = tuple_val(t);
+    Uint nelems = arityval(*p);
+    DMCRet ret;
+
+    ret = dmc_array(context, heap, text, p + 1, nelems, &all_constant);
+    if (ret != retOk) {
+        return ret;
     }
-    
     if (all_constant) {
-	*constant = 1;
-	return retOk;
+        *constant = 1;
+        return retOk;
     }
     DMC_PUSH(*text, matchMkTuple);
     DMC_PUSH(*text, nelems);
@@ -3586,6 +3719,36 @@ static DMCRet dmc_tuple(DMCContext *context,
     return retOk;
 }
 
+static DMCRet
+dmc_map(DMCContext *context, DMCHeap *heap, DMC_STACK_TYPE(UWord) *text,
+        Eterm t, int *constant)
+{
+    map_t *m = (map_t *)map_val(t);
+    Eterm *values = map_get_values(m);
+    int nelems = map_get_size(m);
+    int constant_values;
+    DMCRet ret;
+
+    ret = dmc_array(context, heap, text, values, nelems, &constant_values);
+    if (ret != retOk) {
+        return ret;
+    }
+    if (constant_values) {
+        *constant = 1;
+        return retOk;
+    }
+    DMC_PUSH(*text, matchPushC);
+    DMC_PUSH(*text, dmc_private_copy(context, m->keys));
+    if (++context->stack_used > context->stack_need) {
+        context->stack_need = context->stack_used;
+    }
+    DMC_PUSH(*text, matchMkMap);
+    DMC_PUSH(*text, nelems);
+    context->stack_used -= nelems;
+    *constant = 0;
+    return retOk;
+}
+
 static DMCRet dmc_whole_expression(DMCContext *context,
 				   DMCHeap *heap,
 				   DMC_STACK_TYPE(UWord) *text,
@@ -4580,7 +4743,10 @@ static DMCRet dmc_expr(DMCContext *context,
 	    return ret;
 	break;
     case TAG_PRIMARY_BOXED:
-	if (!BOXED_IS_TUPLE(t)) {
+        if (is_map(t)) {
+            return dmc_map(context, heap, text, t, constant);
+        }
+	if (!is_tuple(t)) {
 	    goto simple_term;
 	}
 	p = tuple_val(t);
@@ -4855,7 +5021,7 @@ static Eterm my_copy_struct(Eterm t, Eterm **hp, ErlOffHeap* off_heap)
 	*hp += 2;
 	break;
     case TAG_PRIMARY_BOXED:
-	if (BOXED_IS_TUPLE(t)) {
+	if (is_tuple(t)) {
 	    if (arityval(*tuple_val(t)) == 1 && 
 		is_tuple(a = tuple_val(t)[1])) {
 		Uint i,n;
@@ -5126,6 +5292,12 @@ void db_match_dis(Binary *bp)
 	    ++t;
 	    erts_printf("Tuple\t%beu\n", n);
 	    break;
+        case matchMap:
+            ++t;
+            n = *t;
+            ++t;
+            erts_printf("Map\t%beu\n", n);
+            break;
 	case matchPushT:
 	    ++t;
 	    n = *t;
@@ -5136,6 +5308,18 @@ void db_match_dis(Binary *bp)
 	    ++t;
 	    erts_printf("PushL\n");
 	    break;
+        case matchPushM:
+            ++t;
+            n = *t;
+            ++t;
+            erts_printf("PushM\t%beu\n", n);
+            break;
+        case matchPushK:
+            ++t;
+            p = (Eterm) *t;
+            ++t;
+            erts_printf("PushK\t%p (%T)\n", t, p);
+            break;
 	case matchPop:
 	    ++t;
 	    erts_printf("Pop\n");
@@ -5252,6 +5436,12 @@ void db_match_dis(Binary *bp)
 	    ++t;
 	    erts_printf("MkTuple\t%beu\n", n);
 	    break;
+        case matchMkMap:
+            ++t;
+            n = *t;
+            ++t;
+            erts_printf("MkMapA\t%beu\n", n);
+            break;
 	case matchOr:
 	    ++t;
 	    n = *t;
diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c
index 5e740aacdd..b2a16eb5ed 100644
--- a/erts/emulator/beam/erl_map.c
+++ b/erts/emulator/beam/erl_map.c
@@ -113,36 +113,55 @@ BIF_RETTYPE maps_to_list_1(BIF_ALIST_1) {
  * return value if key *matches* a key in the map
  */
 
-int erts_maps_find(Eterm key, Eterm map, Eterm *value) {
-
-    Eterm *ks,*vs;
+const Eterm *
+#if HALFWORD_HEAP
+erts_maps_get_rel(Eterm key, Eterm map, Eterm *map_base)
+#else
+erts_maps_get(Eterm key, Eterm map)
+#endif
+{
+    Eterm *ks, *vs;
     map_t *mp;
-    Uint n,i;
+    Uint n, i;
 
-    mp  = (map_t*)map_val(map);
+    mp  = (map_t *)map_val_rel(map, map_base);
     n   = map_get_size(mp);
-    ks  = map_get_keys(mp);
+
+    if (n == 0) {
+        return NULL;
+    }
+
+    ks  = (Eterm *)tuple_val_rel(mp->keys, map_base) + 1;
     vs  = map_get_values(mp);
 
-    for( i = 0; i < n; i++) {
-	if (EQ(ks[i], key)) {
-	    *value = vs[i];
-	    return 1;
-	}
+    if (is_immed(key)) {
+        for (i = 0; i < n; i++) {
+            if (ks[i] == key) {
+                return &vs[i];
+            }
+        }
+    }
+
+    for (i = 0; i < n; i++) {
+        if (eq_rel(ks[i], NULL, key, map_base)) {
+            return &vs[i];
+        }
     }
-    return 0;
+    return NULL;
 }
 
 BIF_RETTYPE maps_find_2(BIF_ALIST_2) {
     if (is_map(BIF_ARG_2)) {
-	Eterm *hp, value,res;
+        Eterm *hp, res;
+        const Eterm *value;
 
-	if (erts_maps_find(BIF_ARG_1, BIF_ARG_2, &value)) {
+        value = erts_maps_get(BIF_ARG_1, BIF_ARG_2);
+	if (value) {
 	    hp    = HAlloc(BIF_P, 3);
 	    res   = make_tuple(hp);
 	    *hp++ = make_arityval(2);
 	    *hp++ = am_ok;
-	    *hp++ = value;
+            *hp++ = *value;
 	    BIF_RET(res);
 	}
 
@@ -150,52 +169,22 @@ BIF_RETTYPE maps_find_2(BIF_ALIST_2) {
     }
     BIF_ERROR(BIF_P, BADARG);
 }
+
 /* maps:get/2
  * return value if key *matches* a key in the map
  * exception bad_key if none matches
  */
 
-
-int erts_maps_get(Eterm key, Eterm map, Eterm *value) {
-    Eterm *ks,*vs;
-    map_t *mp;
-    Uint n,i;
-
-    mp  = (map_t*)map_val(map);
-    n   = map_get_size(mp);
-
-    if (n == 0)
-	return 0;
-
-    ks  = map_get_keys(mp);
-    vs  = map_get_values(mp);
-
-    if (is_immed(key)) {
-	for( i = 0; i < n; i++) {
-	    if (ks[i] == key) {
-		*value = vs[i];
-		return 1;
-	    }
-	}
-    }
-
-    for( i = 0; i < n; i++) {
-	if (EQ(ks[i], key)) {
-	    *value = vs[i];
-	    return 1;
-	}
-    }
-    return 0;
-}
-
 BIF_RETTYPE maps_get_2(BIF_ALIST_2) {
     if (is_map(BIF_ARG_2)) {
 	Eterm *hp;
-	Eterm value, error;
+        Eterm error;
+        const Eterm *value;
 	char *s_error;
 
-	if (erts_maps_get(BIF_ARG_1, BIF_ARG_2, &value)) {
-	    BIF_RET(value);
+        value = erts_maps_get(BIF_ARG_1, BIF_ARG_2);
+        if (value) {
+            BIF_RET(*value);
 	}
 
 	s_error = "bad_key";
diff --git a/erts/emulator/beam/erl_map.h b/erts/emulator/beam/erl_map.h
index cfacb2ec28..2e02ca4677 100644
--- a/erts/emulator/beam/erl_map.h
+++ b/erts/emulator/beam/erl_map.h
@@ -64,9 +64,17 @@ typedef struct map_s {
 
 Eterm erts_maps_put(Process *p, Eterm key, Eterm value, Eterm map);
 int   erts_maps_update(Process *p, Eterm key, Eterm value, Eterm map, Eterm *res);
-int   erts_maps_find(Eterm key, Eterm map, Eterm *value);
-int   erts_maps_get(Eterm key, Eterm map, Eterm *value);
 int   erts_maps_remove(Process *p, Eterm key, Eterm map, Eterm *res);
 int   erts_validate_and_sort_map(map_t* map);
+
+#if HALFWORD_HEAP
+const Eterm *
+erts_maps_get_rel(Eterm key, Eterm map, Eterm *map_base);
+#  define erts_maps_get(A, B) erts_maps_get_rel(A, B, NULL)
+#else
+const Eterm *
+erts_maps_get(Eterm key, Eterm map);
+#  define erts_maps_get_rel(A, B, B_BASE) erts_maps_get(A, B)
 #endif
 
+#endif
diff --git a/erts/emulator/beam/erl_nif.c b/erts/emulator/beam/erl_nif.c
index 3708133f40..caa9eba8a7 100644
--- a/erts/emulator/beam/erl_nif.c
+++ b/erts/emulator/beam/erl_nif.c
@@ -1954,10 +1954,16 @@ int enif_get_map_value(ErlNifEnv* env,
 		       Eterm key,
 		       Eterm *value)
 {
+    const Eterm *ret;
     if (is_not_map(map)) {
 	return 0;
     }
-    return erts_maps_get(key, map, value);
+    ret = erts_maps_get(key, map);
+    if (ret) {
+        *value = *ret;
+        return 1;
+    }
+    return 0;
 }
 
 int enif_make_map_update(ErlNifEnv* env,
diff --git a/erts/emulator/test/match_spec_SUITE.erl b/erts/emulator/test/match_spec_SUITE.erl
index fdce157abc..fc4a5028e1 100644
--- a/erts/emulator/test/match_spec_SUITE.erl
+++ b/erts/emulator/test/match_spec_SUITE.erl
@@ -30,6 +30,7 @@
 -export([fpe/1]).
 -export([otp_9422/1]).
 -export([faulty_seq_trace/1, do_faulty_seq_trace/0]).
+-export([maps/1]).
 -export([runner/2, loop_runner/3]).
 -export([f1/1, f2/2, f3/2, fn/1, fn/2, fn/3]).
 -export([do_boxed_and_small/0]).
@@ -62,7 +63,8 @@ all() ->
 	     moving_labels,
 	     faulty_seq_trace,
 	     empty_list,
-	     otp_9422];
+             otp_9422,
+             maps];
 	true -> [not_run]
     end.
 
@@ -899,6 +901,31 @@ fpe(Config) when is_list(Config) ->
 	_ -> ok 
     end.
 
+maps(Config) when is_list(Config) ->
+    {ok,#{},[],[]} = erlang:match_spec_test(#{}, [{'_',[],['$_']}], table),
+    {ok,#{},[],[]} = erlang:match_spec_test(#{}, [{#{},[],['$_']}], table),
+    {ok,false,[],[]} =
+        erlang:match_spec_test(#{}, [{not_a_map,[],['$_']}], table),
+    {ok,bar,[],[]} =
+        erlang:match_spec_test(#{foo => bar},
+                               [{#{foo => '$1'},[],['$1']}],
+                               table),
+    {ok,false,[],[]} =
+        erlang:match_spec_test(#{foo => bar},
+                               [{#{foo => qux},[],[qux]}],
+                               table),
+    {ok,false,[],[]} =
+        erlang:match_spec_test(#{}, [{#{foo => '_'},[],[foo]}], table),
+    {error,_} =
+        erlang:match_spec_test(#{}, [{#{'$1' => '_'},[],[foo]}], table),
+    {ok,bar,[],[]} =
+        erlang:match_spec_test({#{foo => bar}},
+                               [{{#{foo => '$1'}},[],['$1']}],
+                               table),
+    {ok,#{foo := 3},[],[]} =
+        erlang:match_spec_test({}, [{{},[],[#{foo => {'+',1,2}}]}], table),
+    ok.
+
 empty_list(Config) when is_list(Config) ->
     Val=[{'$1',[], [{message,'$1'},{message,{caller}},{return_trace}]}],
      %% Did crash debug VM in faulty assert:
diff --git a/lib/stdlib/src/ms_transform.erl b/lib/stdlib/src/ms_transform.erl
index 27dfcf52e1..e671dcd8cf 100644
--- a/lib/stdlib/src/ms_transform.erl
+++ b/lib/stdlib/src/ms_transform.erl
@@ -1079,6 +1079,12 @@ normalise({cons,_,Head,Tail}) ->
     [normalise(Head)|normalise(Tail)];
 normalise({tuple,_,Args}) ->
     list_to_tuple(normalise_list(Args));
+normalise({map,_,Pairs0}) ->
+    Pairs1 = lists:map(fun ({map_field_exact,_,K,V}) ->
+                               {normalise(K),normalise(V)}
+                       end,
+                       Pairs0),
+    maps:from_list(Pairs1);
 %% Special case for unary +/-.
 normalise({op,_,'+',{char,_,I}}) -> I;
 normalise({op,_,'+',{integer,_,I}}) -> I;