From c52f42bbaf16c02143ad2a840c5a4f9101235943 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Thu, 19 Jul 2018 19:33:14 +0200 Subject: Optimise functions in the maps module Using direct pattern matching on the map is more effient than pattern matching on the result of maps:find/2, because it avoids allocating the intermediate tuple. --- lib/stdlib/src/maps.erl | 40 +++++++++++++++++----------------------- 1 file changed, 17 insertions(+), 23 deletions(-) diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl index 60463feec2..12302ce839 100644 --- a/lib/stdlib/src/maps.erl +++ b/lib/stdlib/src/maps.erl @@ -164,11 +164,9 @@ values(_) -> erlang:nif_error(undef). Fun :: fun((Value1 :: term()) -> Value2 :: term()). update_with(Key,Fun,Map) when is_function(Fun,1), is_map(Map) -> - try maps:get(Key,Map) of - Val -> maps:update(Key,Fun(Val),Map) - catch - error:{badkey,_} -> - erlang:error({badkey,Key},[Key,Fun,Map]) + case Map of + #{Key := Value} -> Map#{Key := Fun(Value)}; + #{} -> erlang:error({badkey,Key},[Key,Fun,Map]) end; update_with(Key,Fun,Map) -> erlang:error(error_type(Map),[Key,Fun,Map]). @@ -182,9 +180,9 @@ update_with(Key,Fun,Map) -> Init :: term(). update_with(Key,Fun,Init,Map) when is_function(Fun,1), is_map(Map) -> - case maps:find(Key,Map) of - {ok,Val} -> maps:update(Key,Fun(Val),Map); - error -> maps:put(Key,Init,Map) + case Map of + #{Key := Value} -> Map#{Key := Fun(Value)}; + #{} -> Map#{Key => Init} end; update_with(Key,Fun,Init,Map) -> erlang:error(error_type(Map),[Key,Fun,Init,Map]). @@ -197,11 +195,9 @@ update_with(Key,Fun,Init,Map) -> Default :: term(). get(Key,Map,Default) when is_map(Map) -> - case maps:find(Key, Map) of - {ok, Value} -> - Value; - error -> - Default + case Map of + #{Key := Value} -> Value; + #{} -> Default end; get(Key,Map,Default) -> erlang:error({badmap,Map},[Key,Map,Default]). @@ -318,7 +314,7 @@ next(Iter) -> K :: term(). without(Ks,M) when is_list(Ks), is_map(M) -> - lists:foldl(fun(K, M1) -> maps:remove(K, M1) end, M, Ks); + lists:foldl(fun maps:remove/2, M, Ks); without(Ks,M) -> erlang:error(error_type(M),[Ks,M]). @@ -329,18 +325,16 @@ without(Ks,M) -> K :: term(). with(Ks,Map1) when is_list(Ks), is_map(Map1) -> - Fun = fun(K, List) -> - case maps:find(K, Map1) of - {ok, V} -> - [{K, V} | List]; - error -> - List - end - end, - maps:from_list(lists:foldl(Fun, [], Ks)); + maps:from_list(with_1(Ks, Map1)); with(Ks,M) -> erlang:error(error_type(M),[Ks,M]). +with_1([K|Ks], Map) -> + case Map of + #{K := V} -> [{K,V}|with_1(Ks, Map)]; + #{} -> with_1(Ks, Map) + end; +with_1([], _Map) -> []. error_type(M) when is_map(M) -> badarg; error_type(V) -> {badmap, V}. -- cgit v1.2.3 From 7cae8734155671908264dc5ad057879125125ffe Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Micha=C5=82=20Muska=C5=82a?= Date: Thu, 19 Jul 2018 19:37:07 +0200 Subject: Refine types of functions in maps module This only touches functions that are not further manually enhanced in erl_bif_types. The hope is that this will allow dialyzer to discover more issues in code using maps. --- .../test/small_SUITE_data/results/maps_sum | 2 +- lib/stdlib/doc/src/maps.xml | 34 ++++--- lib/stdlib/src/maps.erl | 101 ++++++++------------- 3 files changed, 59 insertions(+), 78 deletions(-) diff --git a/lib/dialyzer/test/small_SUITE_data/results/maps_sum b/lib/dialyzer/test/small_SUITE_data/results/maps_sum index b29ac77d88..daa099e490 100644 --- a/lib/dialyzer/test/small_SUITE_data/results/maps_sum +++ b/lib/dialyzer/test/small_SUITE_data/results/maps_sum @@ -1,4 +1,4 @@ -maps_sum.erl:15: Invalid type specification for function maps_sum:wrong1/1. The success typing is (maps:iterator() | map()) -> any() +maps_sum.erl:15: Invalid type specification for function maps_sum:wrong1/1. The success typing is (maps:iterator(_,_) | map()) -> any() maps_sum.erl:26: Function wrong2/1 has no local return maps_sum.erl:27: The call lists:foldl(fun((_,_,_) -> any()),0,Data::any()) will never return since it differs in the 1st argument from the success typing arguments: (fun((_,_) -> any()),any(),[any()]) diff --git a/lib/stdlib/doc/src/maps.xml b/lib/stdlib/doc/src/maps.xml index a225dea3b5..4c5199ca2b 100644 --- a/lib/stdlib/doc/src/maps.xml +++ b/lib/stdlib/doc/src/maps.xml @@ -35,9 +35,10 @@ - + -

An iterator representing the key value associations in a map.

+

An iterator representing the associations in a map with keys of type + Key and values of type Value.

Created using maps:iterator/1.

Consumed by maps:next/1, maps:filter/2, @@ -45,6 +46,10 @@ maps:map/2.

 + + + + @@ -90,13 +95,13 @@ -

Calls F(K, V, AccIn) for every K to value - V association in MapOrIter in - any order. Function fun F/3 must return a new - accumulator, which is passed to the next successive call. - This function returns the final value of the accumulator. The initial - accumulator value Init is returned if the map is - empty.

+

Calls F(Key, Value, AccIn) for every Key + to value Value association in + MapOrIter in any order. Function fun F/3 + must return a new accumulator, which is passed to the next successive + call. This function returns the final value of the accumulator. + The initial accumulator value Init is returned + if the map is empty.

The call fails with a {badmap,Map} exception if MapOrIter is not a map or valid iterator, or with badarg if Fun is not a @@ -234,11 +239,12 @@ none

Produces a new map Map by calling function - fun F(K, V1) for every K to value - V1 association in MapOrIter in - any order. Function fun F/2 must return value - V2 to be associated with key K - for the new map Map.

+ fun F(Key, Value1) for every Key to value + Value1 association in + MapOrIter in any order. Function fun Fun/2 + must return value Value2 to be associated with + key Key for the new map + Map.

The call fails with a {badmap,Map} exception if MapOrIter is not a map or valid iterator, or with badarg if Fun is not a diff --git a/lib/stdlib/src/maps.erl b/lib/stdlib/src/maps.erl index 12302ce839..da0f92e412 100644 --- a/lib/stdlib/src/maps.erl +++ b/lib/stdlib/src/maps.erl @@ -32,10 +32,12 @@ new/0, put/3, remove/2, take/2, to_list/1, update/3, values/1]). --opaque iterator() :: {term(), term(), iterator()} - | none | nonempty_improper_list(integer(),map()). +-opaque iterator(Key, Value) :: {Key, Value, iterator(Key, Value)} | none + | nonempty_improper_list(integer(), #{Key => Value}). --export_type([iterator/0]). +-type iterator() :: iterator(term(), term()). + +-export_type([iterator/2, iterator/0]). -dialyzer({no_improper_lists, iterator/1}). @@ -50,9 +52,7 @@ get(_,_) -> erlang:nif_error(undef). -spec find(Key,Map) -> {ok, Value} | error when - Key :: term(), - Map :: map(), - Value :: term(). + Map :: #{Key => Value, _ => _}. find(_,_) -> erlang:nif_error(undef). @@ -75,9 +75,8 @@ is_key(_,_) -> erlang:nif_error(undef). -spec keys(Map) -> Keys when - Map :: map(), - Keys :: [Key], - Key :: term(). + Map :: #{Key => _}, + Keys :: [Key]. keys(_) -> erlang:nif_error(undef). @@ -116,17 +115,13 @@ put(_,_,_) -> erlang:nif_error(undef). remove(_,_) -> erlang:nif_error(undef). -spec take(Key,Map1) -> {Value,Map2} | error when - Key :: term(), - Map1 :: map(), - Value :: term(), - Map2 :: map(). + Map1 :: #{Key => Value, _ => _}, + Map2 :: #{_ => _}. take(_,_) -> erlang:nif_error(undef). -spec to_list(Map) -> [{Key,Value}] when - Map :: map(), - Key :: term(), - Value :: term(). + Map :: #{Key => Value}. to_list(Map) when is_map(Map) -> to_list_internal(erts_internal:map_next(0, Map, [])); @@ -140,28 +135,24 @@ to_list_internal(Acc) -> %% Shadowed by erl_bif_types: maps:update/3 -spec update(Key,Value,Map1) -> Map2 when - Key :: term(), - Value :: term(), - Map1 :: map(), - Map2 :: map(). + Map1 :: #{Key := _, _ => _}, + Map2 :: #{Key := Value, _ => _}. update(_,_,_) -> erlang:nif_error(undef). -spec values(Map) -> Values when - Map :: map(), - Values :: [Value], - Value :: term(). + Map :: #{_ => Value}, + Values :: [Value]. values(_) -> erlang:nif_error(undef). %% End of BIFs -spec update_with(Key,Fun,Map1) -> Map2 when - Key :: term(), - Map1 :: map(), - Map2 :: map(), - Fun :: fun((Value1 :: term()) -> Value2 :: term()). + Map1 :: #{Key := Value1, _ => _}, + Map2 :: #{Key := Value2, _ => _}, + Fun :: fun((Value1) -> Value2). update_with(Key,Fun,Map) when is_function(Fun,1), is_map(Map) -> case Map of @@ -173,11 +164,9 @@ update_with(Key,Fun,Map) -> -spec update_with(Key,Fun,Init,Map1) -> Map2 when - Key :: term(), - Map1 :: Map1, - Map2 :: Map2, - Fun :: fun((Value1 :: term()) -> Value2 :: term()), - Init :: term(). + Map1 :: #{Key => Value1, _ => _}, + Map2 :: #{Key := Value2 | Init, _ => _}, + Fun :: fun((Value1) -> Value2). update_with(Key,Fun,Init,Map) when is_function(Fun,1), is_map(Map) -> case Map of @@ -189,10 +178,7 @@ update_with(Key,Fun,Init,Map) -> -spec get(Key, Map, Default) -> Value | Default when - Key :: term(), - Map :: map(), - Value :: term(), - Default :: term(). + Map :: #{Key => Value, _ => _}. get(Key,Map,Default) when is_map(Map) -> case Map of @@ -203,12 +189,10 @@ get(Key,Map,Default) -> erlang:error({badmap,Map},[Key,Map,Default]). --spec filter(Pred,MapOrIter) -> Map when +-spec filter(Pred, MapOrIter) -> Map when Pred :: fun((Key, Value) -> boolean()), - Key :: term(), - Value :: term(), - MapOrIter :: map() | iterator(), - Map :: map(). + MapOrIter :: #{Key => Value} | iterator(Key, Value), + Map :: #{Key => Value}. filter(Pred,Map) when is_function(Pred,2), is_map(Map) -> maps:from_list(filter_1(Pred, iterator(Map))); @@ -231,14 +215,11 @@ filter_1(Pred, Iter) -> end. -spec fold(Fun,Init,MapOrIter) -> Acc when - Fun :: fun((K, V, AccIn) -> AccOut), + Fun :: fun((Key, Value, AccIn) -> AccOut), Init :: term(), - Acc :: term(), - AccIn :: term(), - AccOut :: term(), - MapOrIter :: map() | iterator(), - K :: term(), - V :: term(). + Acc :: AccOut, + AccIn :: Init | AccOut, + MapOrIter :: #{Key => Value} | iterator(Key, Value). fold(Fun,Init,Map) when is_function(Fun,3), is_map(Map) -> fold_1(Fun,Init,iterator(Map)); @@ -256,12 +237,9 @@ fold_1(Fun, Acc, Iter) -> end. -spec map(Fun,MapOrIter) -> Map when - Fun :: fun((K, V1) -> V2), - MapOrIter :: map() | iterator(), - Map :: map(), - K :: term(), - V1 :: term(), - V2 :: term(). + Fun :: fun((Key, Value1) -> Value2), + MapOrIter :: #{Key => Value1} | iterator(Key, Value1), + Map :: #{Key => Value2}. map(Fun,Map) when is_function(Fun, 2), is_map(Map) -> maps:from_list(map_1(Fun, iterator(Map))); @@ -287,17 +265,15 @@ size(Val) -> erlang:error({badmap,Val},[Val]). -spec iterator(Map) -> Iterator when - Map :: map(), - Iterator :: iterator(). + Map :: #{Key => Value}, + Iterator :: iterator(Key, Value). iterator(M) when is_map(M) -> [0 | M]; iterator(M) -> erlang:error({badmap, M}, [M]). -spec next(Iterator) -> {Key, Value, NextIterator} | 'none' when - Iterator :: iterator(), - Key :: term(), - Value :: term(), - NextIterator :: iterator(). + Iterator :: iterator(Key, Value), + NextIterator :: iterator(Key, Value). next({K, V, I}) -> {K, V, I}; next([Path | Map]) when is_integer(Path), is_map(Map) -> @@ -320,9 +296,8 @@ without(Ks,M) -> -spec with(Ks, Map1) -> Map2 when Ks :: [K], - Map1 :: map(), - Map2 :: map(), - K :: term(). + Map1 :: #{K => V, _ => _}, + Map2 :: #{K => V}. with(Ks,Map1) when is_list(Ks), is_map(Map1) -> maps:from_list(with_1(Ks, Map1)); -- cgit v1.2.3