1 files changed, 160 insertions, 20 deletions

diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl
index 65f1251099..40d2f72b4c 100644
--- a/lib/compiler/src/v3_kernel.erl
+++ b/lib/compiler/src/v3_kernel.erl
@@ -81,7 +81,7 @@
 -export([module/2,format_error/1]).
 
 -import(lists, [map/2,foldl/3,foldr/3,mapfoldl/3,splitwith/2,member/2,
-		keymember/3,keyfind/3,partition/2]).
+		keymember/3,keyfind/3,partition/2,droplast/1,last/1]).
 -import(ordsets, [add_element/2,del_element/2,union/2,union/1,subtract/2]).
 -import(cerl, [c_tuple/1]).
 
@@ -272,6 +272,18 @@ expr(#c_cons{anno=A,hd=Ch,tl=Ct}, Sub, St0) ->
 expr(#c_tuple{anno=A,es=Ces}, Sub, St0) ->
     {Kes,Ep,St1} = atomic_list(Ces, Sub, St0),
     {#k_tuple{anno=A,es=Kes},Ep,St1};
+expr(#c_map{anno=A,arg=Var,es=Ces}, Sub, St0) ->
+    try expr_map(A,Var,Ces,Sub,St0) of
+	{_,_,_}=Res -> Res
+    catch
+	throw:bad_map ->
+	    St1 = add_warning(get_line(A), bad_map, A, St0),
+	    Erl = #c_literal{val=erlang},
+	    Name = #c_literal{val=error},
+	    Args = [#c_literal{val=badarg}],
+	    Error = #c_call{anno=A,module=Erl,name=Name,args=Args},
+	    expr(Error, Sub, St1)
+    end;
 expr(#c_binary{anno=A,segments=Cv}, Sub, St0) ->
     try atomic_bin(Cv, Sub, St0) of
 	{Kv,Ep,St1} ->
@@ -347,7 +359,7 @@ expr(#c_case{arg=Ca,clauses=Ccs}, Sub, St0) ->
     {Kvs,Pv,St2} = match_vars(Ka, St1),		%Must have variables here!
     {Km,St3} = kmatch(Kvs, Ccs, Sub, St2),
     Match = flatten_seq(build_match(Kvs, Km)),
-    {last(Match),Pa ++ Pv ++ first(Match),St3};
+    {last(Match),Pa ++ Pv ++ droplast(Match),St3};
 expr(#c_receive{anno=A,clauses=Ccs0,timeout=Ce,action=Ca}, Sub, St0) ->
     {Ke,Pe,St1} = atomic(Ce, Sub, St0),		%Force this to be atomic!
     {Rvar,St2} = new_var(St1),
@@ -493,6 +505,85 @@ translate_match_fail_1(Anno, As, Sub, #kern{ff=FF}) ->
 translate_fc(Args) ->
     [#c_literal{val=function_clause},make_list(Args)].
 
+expr_map(A,Var0,Ces,Sub,St0) ->
+    %% An extra pass of validation of Map src because of inlining
+    {Var,Mps,St1} = expr(Var0, Sub, St0),
+    case is_valid_map_src(Var) of
+	true ->
+	    {Km,Eps,St2} = map_split_pairs(A, Var, Ces, Sub, St1),
+	    {Km,Eps++Mps,St2};
+	false -> throw(bad_map)
+    end.
+
+is_valid_map_src(#k_map{}) -> true;
+is_valid_map_src(#k_literal{val=M}) when is_map(M) -> true;
+is_valid_map_src(#k_var{}) -> true;
+is_valid_map_src(_) -> false.
+
+map_split_pairs(A, Var, Ces, Sub, St0) ->
+    %% two steps
+    %% 1. force variables
+    %% 2. remove multiples
+    Pairs0 = [{Op,K,V} || #c_map_pair{op=#c_literal{val=Op},key=K,val=V} <- Ces],
+    {Pairs,Esp,St1} = foldr(fun
+	    ({Op,K0,V0}, {Ops,Espi,Sti0}) when Op =:= assoc; Op =:= exact ->
+		{K,[],Sti1} = expr(K0, Sub, Sti0),
+		{V,Ep,Sti2} = atomic(V0, Sub, Sti1),
+		{[{Op,K,V}|Ops],Ep ++ Espi,Sti2}
+	end, {[],[],St0}, Pairs0),
+
+    case map_group_pairs(Pairs) of
+	{Assoc,[]} ->
+	    Kes = [#k_map_pair{key=K,val=V}||{_,{assoc,K,V}} <- Assoc],
+	    {#k_map{anno=A,op=assoc,var=Var,es=Kes},Esp,St1};
+	{[],Exact} ->
+	    Kes = [#k_map_pair{key=K,val=V}||{_,{exact,K,V}} <- Exact],
+	    {#k_map{anno=A,op=exact,var=Var,es=Kes},Esp,St1};
+	{Assoc,Exact} ->
+	    Kes1 = [#k_map_pair{key=K,val=V}||{_,{assoc,K,V}} <- Assoc],
+	    {Mvar,Em,St2} = force_atomic(#k_map{anno=A,op=assoc,var=Var,es=Kes1},St1),
+	    Kes2 = [#k_map_pair{key=K,val=V}||{_,{exact,K,V}} <- Exact],
+	    {#k_map{anno=A,op=exact,var=Mvar,es=Kes2},Esp ++ Em,St2}
+
+    end.
+
+%% Group map by Assoc operations and Exact operations
+
+map_group_pairs(Es) ->
+    Groups = dict:to_list(map_group_pairs(Es,dict:new())),
+    partition(fun({_,{Op,_,_}}) -> Op =:= assoc end, Groups).
+
+map_group_pairs([{assoc,K,V}|Es0],Used0) ->
+    Used1 = case map_key_is_used(K,Used0) of
+	{ok, {assoc,_,_}} -> map_key_set_used(K,{assoc,K,V},Used0);
+	{ok, {exact,_,_}} -> map_key_set_used(K,{exact,K,V},Used0);
+	_                 -> map_key_set_used(K,{assoc,K,V},Used0)
+    end,
+    map_group_pairs(Es0,Used1);
+map_group_pairs([{exact,K,V}|Es0],Used0) ->
+    Used1 = case map_key_is_used(K,Used0) of
+	{ok, {assoc,_,_}} -> map_key_set_used(K,{assoc,K,V},Used0);
+	{ok, {exact,_,_}} -> map_key_set_used(K,{exact,K,V},Used0);
+	_                 -> map_key_set_used(K,{exact,K,V},Used0)
+    end,
+    map_group_pairs(Es0,Used1);
+map_group_pairs([],Used) ->
+    Used.
+
+map_key_set_used(K,How,Used) ->
+    dict:store(map_key_clean(K),How,Used).
+
+map_key_is_used(K,Used) ->
+    dict:find(map_key_clean(K),Used).
+
+%% Be explicit instead of using set_kanno(K,[])
+map_key_clean(#k_literal{val=V}) -> {k_literal,V};
+map_key_clean(#k_int{val=V})     -> {k_int,V};
+map_key_clean(#k_float{val=V})   -> {k_float,V};
+map_key_clean(#k_atom{val=V})    -> {k_atom,V};
+map_key_clean(#k_nil{})          -> k_nil.
+
+
 %% call_type(Module, Function, Arity) -> call | bif | apply | error.
 %%  Classify the call.
 call_type(#c_literal{val=M}, #c_literal{val=F}, Ar) when is_atom(M), is_atom(F) ->
@@ -648,6 +739,9 @@ pattern(#c_cons{anno=A,hd=Ch,tl=Ct}, Isub, Osub0, St0) ->
 pattern(#c_tuple{anno=A,es=Ces}, Isub, Osub0, St0) ->
     {Kes,Osub1,St1} = pattern_list(Ces, Isub, Osub0, St0),
     {#k_tuple{anno=A,es=Kes},Osub1,St1};
+pattern(#c_map{anno=A,es=Ces}, Isub, Osub0, St0) ->
+    {Kes,Osub1,St1} = pattern_map_pairs(Ces, Isub, Osub0, St0),
+    {#k_map{anno=A,op=exact,es=Kes},Osub1,St1};
 pattern(#c_binary{anno=A,segments=Cv}, Isub, Osub0, St0) ->
     {Kv,Osub1,St1} = pattern_bin(Cv, Isub, Osub0, St0),
     {#k_binary{anno=A,segs=Kv},Osub1,St1};
@@ -662,6 +756,25 @@ flatten_alias(#c_alias{var=V,pat=P}) ->
     {[V|Vs],Pat};
 flatten_alias(Pat) -> {[],Pat}.
 
+pattern_map_pairs(Ces0, Isub, Osub0, St0) ->
+    %% It is assumed that all core keys are literals
+    %% It is later assumed that these keys are term sorted
+    %% so we need to sort them here
+    Ces1 = lists:sort(fun
+	    (#c_map_pair{key=CkA},#c_map_pair{key=CkB}) ->
+		A = core_lib:literal_value(CkA),
+		B = core_lib:literal_value(CkB),
+		erts_internal:cmp_term(A,B) < 0
+	end, Ces0),
+    %% pattern the pair keys and values as normal
+    {Kes,{Osub1,St1}} = lists:mapfoldl(fun
+	    (#c_map_pair{anno=A,key=Ck,val=Cv},{Osubi0,Sti0}) ->
+		{Kk,Osubi1,Sti1} = pattern(Ck, Isub, Osubi0, Sti0),
+		{Kv,Osubi2,Sti2} = pattern(Cv, Isub, Osubi1, Sti1),
+		{#k_map_pair{anno=A,key=Kk,val=Kv},{Osubi2,Sti2}}
+	end, {Osub0, St0}, Ces1),
+    {Kes,Osub1,St1}.
+
 pattern_bin(Es, Isub, Osub0, St0) ->
     {Kbin,{_,Osub},St} = pattern_bin_1(Es, Isub, Osub0, St0),
     {Kbin,Osub,St}.
@@ -826,15 +939,6 @@ foldr2(Fun, Acc0, [E1|L1], [E2|L2]) ->
     foldr2(Fun, Acc1, L1, L2);
 foldr2(_, Acc, [], []) -> Acc.
 
-%% first([A]) -> [A].
-%% last([A]) -> A.
-
-last([L]) -> L;
-last([_|T]) -> last(T).
-
-first([_]) -> [];
-first([H|T]) -> [H|first(T)].
-
 %% This code implements the algorithm for an optimizing compiler for
 %% pattern matching given "The Implementation of Functional
 %% Programming Languages" by Simon Peyton Jones. The code is much
@@ -1015,7 +1119,8 @@ match_con_1([U|_Us] = L, Cs, Def, St0) ->
     %% Extract clauses for different constructors (types).
     %%ok = io:format("match_con ~p~n", [Cs]),
     Ttcs = select_types([k_binary], Cs) ++ select_bin_con(Cs) ++
-	select_types([k_cons,k_tuple,k_atom,k_float,k_int,k_nil,k_literal], Cs),
+	select_types([k_cons,k_tuple,k_map,k_atom,k_float,k_int,
+		      k_nil,k_literal], Cs),
     %%ok = io:format("ttcs = ~p~n", [Ttcs]),
     {Scs,St1} =
 	mapfoldl(fun ({T,Tcs}, St) ->
@@ -1251,10 +1356,9 @@ group_value(k_cons, Cs) -> [Cs];		%These are single valued
 group_value(k_nil, Cs) -> [Cs];
 group_value(k_binary, Cs) -> [Cs];
 group_value(k_bin_end, Cs) -> [Cs];
-group_value(k_bin_seg, Cs) ->
-    group_bin_seg(Cs);
-group_value(k_bin_int, Cs) ->
-    [Cs];
+group_value(k_bin_seg, Cs) -> group_bin_seg(Cs);
+group_value(k_bin_int, Cs) -> [Cs];
+group_value(k_map, Cs) -> group_map(Cs);
 group_value(_, Cs) ->
     %% group_value(Cs).
     Cd = foldl(fun (C, Gcs0) -> dict:append(clause_val(C), C, Gcs0) end,
@@ -1267,6 +1371,12 @@ group_bin_seg([C1|Cs]) ->
     [[C1|More]|group_bin_seg(Rest)];
 group_bin_seg([]) -> [].
 
+group_map([C1|Cs]) ->
+    V1 = clause_val(C1),
+    {More,Rest} = splitwith(fun (C) -> clause_val(C) =:= V1 end, Cs),
+    [[C1|More]|group_map(Rest)];
+group_map([]) -> [].
+
 %% Profiling shows that this quadratic implementation account for a big amount
 %% of the execution time if there are many values.
 % group_value([C|Cs]) ->
@@ -1315,6 +1425,13 @@ get_match(#k_bin_int{}=BinInt, St0) ->
 get_match(#k_tuple{es=Es}, St0) ->
     {Mes,St1} = new_vars(length(Es), St0),
     {#k_tuple{es=Mes},Mes,St1};
+get_match(#k_map{op=exact,es=Es0}, St0) ->
+    {Mes,St1} = new_vars(length(Es0), St0),
+    {Es,_} = mapfoldl(fun
+	    (#k_map_pair{}=Pair, [V|Vs]) ->
+		{Pair#k_map_pair{val=V},Vs}
+	end, Mes, Es0),
+    {#k_map{op=exact,es=Es},Mes,St1};
 get_match(M, St) ->
     {M,[],St}.
 
@@ -1331,7 +1448,11 @@ new_clauses(Cs0, U, St) ->
 				     [S,N|As];
 				 #k_bin_int{next=N} ->
 				     [N|As];
-				 _Other -> As
+				 #k_map{op=exact,es=Es} ->
+				     Vals = [V || #k_map_pair{val=V} <- Es],
+				     Vals ++ As;
+				 _Other ->
+				     As
 			     end,
 		      Vs = arg_alias(Arg),
 		      Osub1 = foldl(fun (#k_var{name=V}, Acc) ->
@@ -1406,6 +1527,7 @@ arg_con(Arg) ->
 	#k_nil{} -> k_nil;
 	#k_cons{} -> k_cons; 
 	#k_tuple{} -> k_tuple;
+	#k_map{} -> k_map;
 	#k_binary{} -> k_binary;
 	#k_bin_end{} -> k_bin_end;
 	#k_bin_seg{} -> k_bin_seg;
@@ -1426,7 +1548,15 @@ arg_val(Arg, C) ->
 		    {#k_var{name=get_vsub(V, Isub)},U,T,Fs};
 		_ ->
 		    {set_kanno(S, []),U,T,Fs}
-	    end
+	    end;
+	#k_map{op=exact,es=Es} ->
+	    Keys = [begin
+			#k_map_pair{key=#k_literal{val=Key}} = Pair,
+			Key
+		    end || Pair <- Es],
+	    %% multiple keys may have the same name
+	    %% do not use ordsets
+	    lists:sort(fun(A,B) -> erts_internal:cmp_term(A,B) < 0 end, Keys)
     end.
 
 %% ubody_used_vars(Expr, State) -> [UsedVar]
@@ -1795,6 +1925,10 @@ lit_vars(#k_atom{}) -> [];
 lit_vars(#k_nil{}) -> [];
 lit_vars(#k_cons{hd=H,tl=T}) ->
     union(lit_vars(H), lit_vars(T));
+lit_vars(#k_map{var=Var,es=Es}) ->
+    lit_list_vars([Var|Es]);
+lit_vars(#k_map_pair{key=K,val=V}) ->
+    union(lit_vars(K), lit_vars(V));
 lit_vars(#k_binary{segs=V}) -> lit_vars(V);
 lit_vars(#k_bin_end{}) -> [];
 lit_vars(#k_bin_seg{size=Size,seg=S,next=N}) ->
@@ -1830,7 +1964,11 @@ pat_vars(#k_bin_int{size=Size}) ->
     {U,[]};
 pat_vars(#k_bin_end{}) -> {[],[]};
 pat_vars(#k_tuple{es=Es}) ->
-    pat_list_vars(Es).
+    pat_list_vars(Es);
+pat_vars(#k_map{es=Es}) ->
+    pat_list_vars(Es);
+pat_vars(#k_map_pair{val=V}) ->
+    pat_vars(V).
 
 pat_list_vars(Ps) ->
     foldl(fun (P, {Used0,New0}) ->
@@ -1871,7 +2009,9 @@ format_error(nomatch_shadow) ->
 format_error(bad_call) ->
     "invalid module and/or function name; this call will always fail";
 format_error(bad_segment_size) ->
-    "binary construction will fail because of a type mismatch".
+    "binary construction will fail because of a type mismatch";
+format_error(bad_map) ->
+    "map construction will fail because of a type mismatch".
 
 add_warning(none, Term, Anno, #kern{ws=Ws}=St) ->
     File = get_file(Anno),