From 5d0874a8f9fd617308d9024783db1e4e24268184 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Fri, 27 Apr 2018 12:40:07 +0200 Subject: Introduce is_map_key/2 guard BIF This complements the `map_get/2` guard BIF introduced in #1784. Rationale. `map_get/2` allows accessing map fields in guards, but it might be problematic in more complex guard expressions, for example: foo(X) when map_get(a, X) =:= 1 or is_list(X) -> ... The `is_list/1` part of the guard could never succeed since the `map_get/2` guard would fail the whole guard expression. In this situation, this could be solved by using `;` instead of `or` to separate the guards, but it is not possible in every case. To solve this situation, this PR proposes a `is_map_key/2` guard that allows to check if a map has key inside a guard before trying to access that key. When combined with `is_map/1` this allows to construct a purely boolean guard expression testing a value of a key in a map. Implementation. Given the use case motivating the introduction of this function, the PR contains compiler optimisations that produce optimial code for the following guard expression: foo(X) when is_map(X) and is_map_key(a, X) and map_get(a, X) =:= 1 -> ok; foo(_) -> error. Given all three tests share the failure label, the `is_map_key/2` and `is_map/2` tests are optimised away. As with `map_get/2` the `is_map_key/2` BIF is allowed in match specs. --- erts/doc/src/erlang.xml | 20 +++++++++++++++ erts/doc/src/match_spec.xml | 23 +++++++++--------- erts/emulator/beam/bif.tab | 1 + erts/emulator/beam/erl_db_util.c | 6 +++++ erts/emulator/beam/erl_map.c | 7 +++++- erts/emulator/test/map_SUITE.erl | 43 ++++++++++++++++++++++++++++++++- erts/emulator/test/match_spec_SUITE.erl | 7 ++++++ erts/preloaded/src/erlang.erl | 9 ++++++- lib/compiler/src/beam_dead.erl | 20 +++++++++++++++ lib/compiler/src/beam_peep.erl | 6 +++++ lib/compiler/src/beam_type.erl | 3 +++ lib/compiler/src/erl_bifs.erl | 1 + lib/compiler/src/v3_codegen.erl | 6 +++++ lib/compiler/test/map_SUITE.erl | 18 ++++++++++++++ lib/hipe/cerl/erl_bif_types.erl | 6 ++++- lib/stdlib/src/erl_internal.erl | 2 ++ lib/stdlib/src/ms_transform.erl | 1 + lib/tools/emacs/erlang.el | 1 + 18 files changed, 165 insertions(+), 15 deletions(-) diff --git a/erts/doc/src/erlang.xml b/erts/doc/src/erlang.xml index f561413fab..3154fdaf8c 100644 --- a/erts/doc/src/erlang.xml +++ b/erts/doc/src/erlang.xml @@ -2431,6 +2431,26 @@ os_prompt% + + + + +

Returns true if map Map contains + Key and returns false if it does not + contain the Key.

+

The call fails with a {badmap,Map} exception if + Map is not a map.

+

Example:

+ +> Map = #{"42" => value}. +#{"42" => value} +> is_map_key("42",Map). +true +> is_map_key(value,Map). +false + + + Check whether a term is a number. diff --git a/erts/doc/src/match_spec.xml b/erts/doc/src/match_spec.xml index 888366b239..46a3daebe8 100644 --- a/erts/doc/src/match_spec.xml +++ b/erts/doc/src/match_spec.xml @@ -86,12 +86,12 @@ | | | | | | - | | - | | - | | - | | - | | - + | | + | | + | | + | | + | | + | ConditionExpression ::= ExprMatchVariable | { GuardFunction } | { GuardFunction, ConditionExpression, ... } | TermConstruct @@ -168,11 +168,12 @@ | | | | | | - | | - | | - | | - | | - | + | | + | | + | | + | | + | | + ConditionExpression ::= ExprMatchVariable | { GuardFunction } | { GuardFunction, ConditionExpression, ... } | TermConstruct diff --git a/erts/emulator/beam/bif.tab b/erts/emulator/beam/bif.tab index 276bef2bbb..33738dc20b 100644 --- a/erts/emulator/beam/bif.tab +++ b/erts/emulator/beam/bif.tab @@ -696,3 +696,4 @@ bif ets:whereis/1 bif erts_internal:gather_alloc_histograms/1 bif erts_internal:gather_carrier_info/1 ubif erlang:map_get/2 +ubif erlang:is_map_key/2 diff --git a/erts/emulator/beam/erl_db_util.c b/erts/emulator/beam/erl_db_util.c index 6354abfd1f..ef22cda1f0 100644 --- a/erts/emulator/beam/erl_db_util.c +++ b/erts/emulator/beam/erl_db_util.c @@ -643,6 +643,12 @@ static DMCGuardBif guard_tab[] = 2, DBIF_ALL }, + { + am_is_map_key, + &is_map_key_2, + 2, + DBIF_ALL + }, { am_bit_size, &bit_size_1, diff --git a/erts/emulator/beam/erl_map.c b/erts/emulator/beam/erl_map.c index f577b017c3..3d565b1bb8 100644 --- a/erts/emulator/beam/erl_map.c +++ b/erts/emulator/beam/erl_map.c @@ -43,6 +43,7 @@ * * DONE: * - erlang:is_map/1 + * - erlang:is_map_key/2 * - erlang:map_size/1 * - erlang:map_get/2 * @@ -919,7 +920,7 @@ static int hxnodecmp(hxnode_t *a, hxnode_t *b) { return -1; } -/* maps:is_key/2 */ +/* maps:is_key/2 and erlang:is_map_key/2 */ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { if (is_map(BIF_ARG_2)) { @@ -929,6 +930,10 @@ BIF_RETTYPE maps_is_key_2(BIF_ALIST_2) { BIF_ERROR(BIF_P, BADMAP); } +BIF_RETTYPE is_map_key_2(BIF_ALIST_2) { + BIF_RET(maps_is_key_2(BIF_CALL_ARGS)); +} + /* maps:keys/1 */ BIF_RETTYPE maps_keys_1(BIF_ALIST_1) { diff --git a/erts/emulator/test/map_SUITE.erl b/erts/emulator/test/map_SUITE.erl index 43807b4388..f93c637650 100644 --- a/erts/emulator/test/map_SUITE.erl +++ b/erts/emulator/test/map_SUITE.erl @@ -38,6 +38,7 @@ t_map_size/1, t_map_get/1, t_is_map/1, + t_is_map_key/1, %% Specific Map BIFs t_bif_map_get/1, @@ -718,7 +719,47 @@ t_map_get(Config) when is_list(Config) -> true = if map_get(a, M2) =:= 1 -> true; true -> false end, false = if map_get(x, M2) =:= 1 -> true; true -> false end, do_badmap(fun - (T) when map_get(T, x) =:= 1 -> ok; + (T) when map_get(x, T) =:= 1 -> ok; + (T) -> false = is_map(T) + end), + ok. + +t_is_map_key(Config) when is_list(Config) -> + %% small map + true = is_map_key(a, id(#{a=>1})), + true = is_map_key(b, id(#{a=>1, b=>2})), + true = is_map_key("hello", id(#{a=>1, "hello"=>"hi"})), + true = is_map_key({1,1.0}, id(#{a=>a, {1,1.0}=>"tuple hi"})), + + M0 = id(#{ k1=>"v1", <<"k2">> => <<"v3">> }), + true = is_map_key(<<"k2">>, M0#{<<"k2">> => "v4"}), + + %% large map + M1 = maps:from_list([{I,I}||I<-lists:seq(1,100)] ++ + [{a,1},{b,2},{"hello","hi"},{{1,1.0},"tuple hi"}, + {k1,"v1"},{<<"k2">>,"v3"}]), + true = is_map_key(a, M1), + true = is_map_key(b, M1), + true = is_map_key("hello", M1), + true = is_map_key({1,1.0}, M1), + true = is_map_key(<<"k2">>, M1), + + %% error cases + do_badmap(fun(T) -> + {'EXIT',{{badmap,T},[{erlang,is_map_key,_,_}|_]}} = + (catch is_map_key(a, T)) + end), + + false = is_map_key({1,1}, id(#{{1,1.0}=>"tuple"})), + false = is_map_key(a, id(#{})), + false = is_map_key(a, id(#{b=>1, c=>2})), + + %% in guards + M2 = id(#{a=>1}), + true = if is_map_key(a, M2) -> true; true -> false end, + false = if is_map_key(x, M2) -> true; true -> false end, + do_badmap(fun + (T) when is_map_key(T, x) =:= 1 -> ok; (T) -> false = is_map(T) end), ok. diff --git a/erts/emulator/test/match_spec_SUITE.erl b/erts/emulator/test/match_spec_SUITE.erl index c1bc01f01e..4415d8d1b9 100644 --- a/erts/emulator/test/match_spec_SUITE.erl +++ b/erts/emulator/test/match_spec_SUITE.erl @@ -898,6 +898,13 @@ maps(Config) when is_list(Config) -> {ok,false,[],[]} = erlang:match_spec_test(not_a_map, [{'$1',[{map_get,b,'$1'}],['$_']}], table), {ok,true,[],[]} = erlang:match_spec_test(#{a => true}, [{'$1',[{map_get,a,'$1'}],[true]}], table), + {ok,true,[],[]} = erlang:match_spec_test(#{a => 1}, [{'$1',[],[{is_map_key,a,'$1'}]}], table), + {ok,false,[],[]} = erlang:match_spec_test(#{a => 1}, [{'$1',[],[{is_map_key,b,'$1'}]}], table), + {ok,'EXIT',[],[]} = erlang:match_spec_test(not_a_map, [{'$1',[],[{is_map_key,a,'$1'}]}], table), + {ok,false,[],[]} = erlang:match_spec_test(#{a => 1}, [{'$1',[{is_map_key,b,'$1'}],['$_']}], table), + {ok,false,[],[]} = erlang:match_spec_test(not_a_map, [{'$1',[{is_map_key,b,'$1'}],['$_']}], table), + {ok,true,[],[]} = erlang:match_spec_test(#{a => true}, [{'$1',[{is_map_key,a,'$1'}],[true]}], table), + %% large maps Ls0 = [{I,<>}||I <- lists:seq(1,415)], diff --git a/erts/preloaded/src/erlang.erl b/erts/preloaded/src/erlang.erl index 53e90a4f2d..5fcad25c6d 100644 --- a/erts/preloaded/src/erlang.erl +++ b/erts/preloaded/src/erlang.erl @@ -135,7 +135,7 @@ -export([insert_element/3]). -export([integer_to_binary/1, integer_to_list/1]). -export([iolist_size/1, iolist_to_binary/1, iolist_to_iovec/1]). --export([is_alive/0, is_builtin/3, is_process_alive/1, length/1, link/1]). +-export([is_alive/0, is_builtin/3, is_map_key/2, is_process_alive/1, length/1, link/1]). -export([list_to_atom/1, list_to_binary/1]). -export([list_to_bitstring/1, list_to_existing_atom/1, list_to_float/1]). -export([list_to_integer/1, list_to_integer/2]). @@ -1121,6 +1121,13 @@ is_alive() -> is_builtin(_Module, _Function, _Arity) -> erlang:nif_error(undefined). +%% Shadowed by erl_bif_types: erlang:is_map_key/2 +-spec is_map_key(Key, Map) -> boolean() when + Key :: term(), + Map :: map(). +is_map_key(_,_) -> + erlang:nif_error(undef). + %% is_process_alive/1 -spec is_process_alive(Pid) -> boolean() when Pid :: pid(). diff --git a/lib/compiler/src/beam_dead.erl b/lib/compiler/src/beam_dead.erl index dbbaae05eb..762c7bdf9e 100644 --- a/lib/compiler/src/beam_dead.erl +++ b/lib/compiler/src/beam_dead.erl @@ -392,6 +392,26 @@ backward([{bif,'or',{f,To0},[Dst,{atom,false}],Dst}=I|Is], D, _ -> backward(Is, D, [I|Acc]) end; +backward([{bif,map_get,{f,FF},[Key,Map],_}=I0, + {test,has_map_fields,{f,FT}=F,[Map|Keys0]}=I1|Is], D, Acc) when FF =/= 0 -> + case shortcut_label(FF, D) of + FT -> + case lists:delete(Key, Keys0) of + [] -> + backward([I0|Is], D, Acc); + Keys -> + Test = {test,has_map_fields,F,[Map|Keys]}, + backward([Test|Is], D, [I0|Acc]) + end; + _ -> + backward([I1|Is], D, [I0|Acc]) + end; +backward([{bif,map_get,{f,FF},[_,Map],_}=I0, + {test,is_map,{f,FT},[Map]}=I1|Is], D, Acc) when FF =/= 0 -> + case shortcut_label(FF, D) of + FT -> backward([I0|Is], D, Acc); + _ -> backward([I1|Is], D, [I0|Acc]) + end; backward([I|Is], D, Acc) -> backward(Is, D, [I|Acc]); backward([], _D, Acc) -> Acc. diff --git a/lib/compiler/src/beam_peep.erl b/lib/compiler/src/beam_peep.erl index eb3192fe8f..920fb00397 100644 --- a/lib/compiler/src/beam_peep.erl +++ b/lib/compiler/src/beam_peep.erl @@ -77,6 +77,12 @@ peep([{bif,tuple_size,_,[_]=Ops,Dst}=I|Is], SeenTests0, Acc) -> %% Kill all remembered tests that depend on the destination register. SeenTests = kill_seen(Dst, SeenTests1), peep(Is, SeenTests, [I|Acc]); +peep([{bif,map_get,_,[Key,Map],Dst}=I|Is], SeenTests0, Acc) -> + %% Pretend that we have seen {test,has_map_fields,_,[Map,Key]} + SeenTests1 = gb_sets:add({has_map_fields,[Map,Key]}, SeenTests0), + %% Kill all remembered tests that depend on the destination register. + SeenTests = kill_seen(Dst, SeenTests1), + peep(Is, SeenTests, [I|Acc]); peep([{bif,_,_,_,Dst}=I|Is], SeenTests0, Acc) -> %% Kill all remembered tests that depend on the destination register. SeenTests = kill_seen(Dst, SeenTests0), diff --git a/lib/compiler/src/beam_type.erl b/lib/compiler/src/beam_type.erl index 28f36db399..12da8c9446 100644 --- a/lib/compiler/src/beam_type.erl +++ b/lib/compiler/src/beam_type.erl @@ -462,6 +462,9 @@ update({set,[D],[Index,Reg],{bif,element,_}}, Ts0) -> end, Ts = tdb_meet(Reg, {tuple,min_size,MinSize,[]}, Ts0), tdb_store(D, any, Ts); +update({set,[D],[_Key,Map],{bif,map_get,_}}, Ts0) -> + Ts = tdb_meet(Map, map, Ts0), + tdb_store(D, any, Ts); update({set,[D],Args,{bif,N,_}}, Ts) -> Ar = length(Args), BoolOp = erl_internal:new_type_test(N, Ar) orelse diff --git a/lib/compiler/src/erl_bifs.erl b/lib/compiler/src/erl_bifs.erl index 70b36f029e..a7452aebc8 100644 --- a/lib/compiler/src/erl_bifs.erl +++ b/lib/compiler/src/erl_bifs.erl @@ -94,6 +94,7 @@ is_pure(erlang, is_function, 1) -> true; is_pure(erlang, is_integer, 1) -> true; is_pure(erlang, is_list, 1) -> true; is_pure(erlang, is_map, 1) -> true; +is_pure(erlang, is_map_key, 2) -> true; is_pure(erlang, is_number, 1) -> true; is_pure(erlang, is_pid, 1) -> true; is_pure(erlang, is_port, 1) -> true; diff --git a/lib/compiler/src/v3_codegen.erl b/lib/compiler/src/v3_codegen.erl index 8e73b613a0..9652a8476d 100644 --- a/lib/compiler/src/v3_codegen.erl +++ b/lib/compiler/src/v3_codegen.erl @@ -589,6 +589,7 @@ is_gc_bif(element, 2) -> false; is_gc_bif(get, 1) -> false; is_gc_bif(tuple_size, 1) -> false; is_gc_bif(map_get, 2) -> false; +is_gc_bif(is_map_key, 2) -> false; is_gc_bif(Bif, Arity) -> not (erl_internal:bool_op(Bif, Arity) orelse erl_internal:new_type_test(Bif, Arity) orelse @@ -1620,6 +1621,11 @@ test_cg(is_boolean, [#k_atom{val=Val}], Fail, I, Vdb, Bef, St) -> false -> [{jump,{f,Fail}}] end, {Is,Aft,St}; +test_cg(is_map_key, As, Fail, I, Vdb, Bef, St) -> + [Key,Map] = cg_reg_args(As, Bef), + Aft = clear_dead(Bef, I, Vdb), + F = {f,Fail}, + {[{test,is_map,F,[Map]},{test,has_map_fields,F,Map,{list,[Key]}}],Aft,St}; test_cg(Test, As, Fail, I, Vdb, Bef, St) -> Args = cg_reg_args(As, Bef), Aft = clear_dead(Bef, I, Vdb), diff --git a/lib/compiler/test/map_SUITE.erl b/lib/compiler/test/map_SUITE.erl index e98c295da6..6badc7a8b8 100644 --- a/lib/compiler/test/map_SUITE.erl +++ b/lib/compiler/test/map_SUITE.erl @@ -1203,12 +1203,18 @@ t_guard_bifs(Config) when is_list(Config) -> true = map_guard_empty_2(), true = map_guard_head(#{a=>1}), false = map_guard_head([]), + true = map_get_head(#{a=>1}), + false = map_get_head([]), + true = map_is_key_head(#{a=>1}), + false = map_is_key_head(#{}), true = map_guard_body(#{a=>1}), false = map_guard_body({}), true = map_guard_pattern(#{a=>1, <<"hi">> => "hi" }), false = map_guard_pattern("list"), true = map_guard_tautology(), true = map_guard_ill_map_size(), + true = map_field_check_sequence(#{a=>1}), + false = map_field_check_sequence(#{}), ok. map_guard_empty() when is_map(#{}); false -> true. @@ -1218,6 +1224,12 @@ map_guard_empty_2() when true; #{} andalso false -> true. map_guard_head(M) when is_map(M) -> true; map_guard_head(_) -> false. +map_get_head(M) when map_get(a, M) =:= 1 -> true; +map_get_head(_) -> false. + +map_is_key_head(M) when is_map_key(a, M) -> true; +map_is_key_head(M) -> false. + map_guard_body(M) -> is_map(M). map_guard_pattern(#{}) -> true; @@ -1227,6 +1239,12 @@ map_guard_tautology() when #{} =:= #{}; true -> true. map_guard_ill_map_size() when true; map_size(0) -> true. +map_field_check_sequence(M) + when is_map(M) andalso is_map_key(a, M) andalso (map_get(a, M) == 1) -> + true; +map_field_check_sequence(_) -> + false. + t_guard_sequence(Config) when is_list(Config) -> {1, "a"} = map_guard_sequence_1(#{seq=>1,val=>id("a")}), {2, "b"} = map_guard_sequence_1(#{seq=>2,val=>id("b")}), diff --git a/lib/hipe/cerl/erl_bif_types.erl b/lib/hipe/cerl/erl_bif_types.erl index fe6ab0659c..48ce641ab9 100644 --- a/lib/hipe/cerl/erl_bif_types.erl +++ b/lib/hipe/cerl/erl_bif_types.erl @@ -665,6 +665,8 @@ type(erlang, is_map, 1, Xs, Opaques) -> check_guard(X, fun (Y) -> t_is_map(Y, Opaques) end, t_map(), Opaques) end, strict(erlang, is_map, 1, Xs, Fun, Opaques); +type(erlang, is_map_key, 2, Xs, Opaques) -> + type(maps, is_key, 2, Xs, Opaques); type(erlang, is_number, 1, Xs, Opaques) -> Fun = fun (X) -> check_guard(X, fun (Y) -> t_is_number(Y, Opaques) end, @@ -2374,6 +2376,8 @@ arg_types(erlang, is_list, 1) -> [t_any()]; arg_types(erlang, is_map, 1) -> [t_any()]; +arg_types(erlang, is_map_key, 2) -> + [t_any(), t_map()]; arg_types(erlang, is_number, 1) -> [t_any()]; arg_types(erlang, is_pid, 1) -> @@ -2396,7 +2400,7 @@ arg_types(erlang, map_size, 1) -> [t_map()]; %% Guard bif, needs to be here. arg_types(erlang, map_get, 2) -> - [t_map(), t_any()]; + [t_any(), t_map()]; arg_types(erlang, make_fun, 3) -> [t_atom(), t_atom(), t_arity()]; arg_types(erlang, make_tuple, 2) -> diff --git a/lib/stdlib/src/erl_internal.erl b/lib/stdlib/src/erl_internal.erl index 6d3d5baa23..dd509191ef 100644 --- a/lib/stdlib/src/erl_internal.erl +++ b/lib/stdlib/src/erl_internal.erl @@ -109,6 +109,7 @@ new_type_test(is_function, 2) -> true; new_type_test(is_integer, 1) -> true; new_type_test(is_list, 1) -> true; new_type_test(is_map, 1) -> true; +new_type_test(is_map_key, 2) -> true; new_type_test(is_number, 1) -> true; new_type_test(is_pid, 1) -> true; new_type_test(is_port, 1) -> true; @@ -315,6 +316,7 @@ bif(is_function, 2) -> true; bif(is_integer, 1) -> true; bif(is_list, 1) -> true; bif(is_map, 1) -> true; +bif(is_map_key, 2) -> true; bif(is_number, 1) -> true; bif(is_pid, 1) -> true; bif(is_port, 1) -> true; diff --git a/lib/stdlib/src/ms_transform.erl b/lib/stdlib/src/ms_transform.erl index ec8cfd56c2..428c23524b 100644 --- a/lib/stdlib/src/ms_transform.erl +++ b/lib/stdlib/src/ms_transform.erl @@ -929,6 +929,7 @@ bool_test(is_port,1) -> true; bool_test(is_reference,1) -> true; bool_test(is_tuple,1) -> true; bool_test(is_map,1) -> true; +bool_test(is_map_key, 2) -> true; bool_test(is_binary,1) -> true; bool_test(is_function,1) -> true; bool_test(is_record,2) -> true; diff --git a/lib/tools/emacs/erlang.el b/lib/tools/emacs/erlang.el index fd51aca861..e08db0ea79 100644 --- a/lib/tools/emacs/erlang.el +++ b/lib/tools/emacs/erlang.el @@ -804,6 +804,7 @@ resulting regexp is surrounded by \\_< and \\_>." "is_integer" "is_list" "is_map" + "is_map_key" "is_number" "is_pid" "is_port" -- cgit v1.2.3