diff options
Diffstat (limited to 'lib/dialyzer/src/dialyzer_dataflow.erl')
| -rw-r--r-- | lib/dialyzer/src/dialyzer_dataflow.erl | 275 |
1 files changed, 216 insertions, 59 deletions
diff --git a/lib/dialyzer/src/dialyzer_dataflow.erl b/lib/dialyzer/src/dialyzer_dataflow.erl index 6e49043551..5ab0c39c04 100644 --- a/lib/dialyzer/src/dialyzer_dataflow.erl +++ b/lib/dialyzer/src/dialyzer_dataflow.erl @@ -2,7 +2,7 @@ %%-------------------------------------------------------------------- %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2015. All Rights Reserved. +%% Copyright Ericsson AB 2006-2016. All Rights Reserved. %% %% Licensed under the Apache License, Version 2.0 (the "License"); %% you may not use this file except in compliance with the License. @@ -43,7 +43,6 @@ -include("dialyzer.hrl"). -%%-import(helper, %% 'helper' could be any module doing sanity checks... -import(erl_types, [t_inf/2, t_inf/3, t_inf_lists/2, t_inf_lists/3, t_inf_lists/3, t_is_equal/2, t_is_subtype/2, t_subtract/2, @@ -72,7 +71,7 @@ t_tuple/0, t_tuple/1, t_tuple_args/1, t_tuple_args/2, t_tuple_subtypes/2, t_unit/0, t_unopaque/2, - t_map/1 + t_map/0, t_map/1, t_is_singleton/2 ]). %%-define(DEBUG, true). @@ -126,8 +125,8 @@ curr_fun :: curr_fun() }). --record(map, {dict = dict:new() :: type_tab(), - subst = dict:new() :: subst_tab(), +-record(map, {map = maps:new() :: type_tab(), + subst = maps:new() :: subst_tab(), modified = [] :: [Key :: term()], modified_stack = [] :: [{[Key :: term()],reference()}], ref = undefined :: reference() | undefined}). @@ -135,10 +134,10 @@ -type env_tab() :: dict:dict(label(), #map{}). -type fun_entry() :: {Args :: [type()], RetType :: type()}. -type fun_tab() :: dict:dict('top' | label(), - {'not_handled', fun_entry()} | fun_entry()). + {'not_handled', fun_entry()} | fun_entry()). -type key() :: label() | cerl:cerl(). --type type_tab() :: dict:dict(key(), type()). --type subst_tab() :: dict:dict(key(), cerl:cerl()). +-type type_tab() :: #{key() => type()}. +-type subst_tab() :: #{key() => cerl:cerl()}. %% Exported Types @@ -342,8 +341,6 @@ traverse(Tree, Map, State) -> handle_tuple(Tree, Map, State); map -> handle_map(Tree, Map, State); - map_pair -> - handle_map_pair(Tree, Map, State); values -> Elements = cerl:values_es(Tree), {State1, Map1, EsType} = traverse_list(Elements, Map, State), @@ -1102,15 +1099,54 @@ handle_try(Tree, Map, State) -> %%---------------------------------------- handle_map(Tree,Map,State) -> - Pairs = cerl:map_es(Tree), - {State1, Map1, TypePairs} = traverse_list(Pairs,Map,State), - {State1, Map1, t_map(TypePairs)}. + Pairs = cerl:map_es(Tree), + Arg = cerl:map_arg(Tree), + {State1, Map1, ArgType} = traverse(Arg, Map, State), + ArgType1 = t_inf(t_map(), ArgType), + case t_is_none_or_unit(ArgType1) of + true -> + {State1, Map1, ArgType1}; + false -> + {State2, Map2, TypePairs, ExactKeys} = + traverse_map_pairs(Pairs, Map1, State1, t_none(), [], []), + InsertPair = fun({KV,assoc,_},Acc) -> erl_types:t_map_put(KV,Acc); + ({KV,exact,KVTree},Acc) -> + case t_is_none(T=erl_types:t_map_update(KV,Acc)) of + true -> throw({none, Acc, KV, KVTree}); + false -> T + end + end, + try lists:foldl(InsertPair, ArgType1, TypePairs) + of ResT -> + BindT = t_map([{K, t_any()} || K <- ExactKeys]), + case bind_pat_vars_reverse([Arg], [BindT], [], Map2, State2) of + {error, _, _, _, _} -> {State2, Map2, ResT}; + {Map3, _} -> {State2, Map3, ResT} + end + catch {none, MapType, {K,_}, KVTree} -> + Msg2 = {map_update, [format_type(MapType, State2), + format_type(K, State2)]}, + {state__add_warning(State2, ?WARN_MAP_CONSTRUCTION, KVTree, Msg2), + Map2, t_none()} + end + end. -handle_map_pair(Tree,Map,State) -> - Key = cerl:map_pair_key(Tree), - Val = cerl:map_pair_val(Tree), +traverse_map_pairs([], Map, State, _ShadowKeys, PairAcc, KeyAcc) -> + {State, Map, lists:reverse(PairAcc), KeyAcc}; +traverse_map_pairs([Pair|Pairs], Map, State, ShadowKeys, PairAcc, KeyAcc) -> + Key = cerl:map_pair_key(Pair), + Val = cerl:map_pair_val(Pair), + Op = cerl:map_pair_op(Pair), {State1, Map1, [K,V]} = traverse_list([Key,Val],Map,State), - {State1, Map1, {K,V}}. + KeyAcc1 = + case cerl:is_literal(Op) andalso cerl:concrete(Op) =:= exact andalso + t_is_singleton(K, State#state.opaques) andalso + t_is_none(t_inf(ShadowKeys, K)) of + true -> [K|KeyAcc]; + false -> KeyAcc + end, + traverse_map_pairs(Pairs, Map1, State1, t_sup(K, ShadowKeys), + [{{K,V},cerl:concrete(Op),Pair}|PairAcc], KeyAcc1). %%---------------------------------------- @@ -1445,7 +1481,9 @@ bind_pat_vars([Pat|PatLeft], [Type|TypeLeft], Acc, Map, State, Rev) -> {NewMap, TypeOut} = case cerl:type(Pat) of alias -> - AliasPat = cerl:alias_pat(Pat), + %% Map patterns are more allowing than the type of their literal. We + %% must unfold AliasPat if it is a literal. + AliasPat = dialyzer_utils:refold_pattern(cerl:alias_pat(Pat)), Var = cerl:alias_var(Pat), Map1 = enter_subst(Var, AliasPat, Map), {Map2, [PatType]} = bind_pat_vars([AliasPat], [Type], [], @@ -1486,14 +1524,59 @@ bind_pat_vars([Pat|PatLeft], [Type|TypeLeft], Acc, Map, State, Rev) -> {Map1, t_cons(HdType, TlType)} end; literal -> - Literal = literal_type(Pat), - case t_is_none(t_inf(Literal, Type, Opaques)) of + Pat0 = dialyzer_utils:refold_pattern(Pat), + case cerl:is_literal(Pat0) of true -> - bind_opaque_pats(Literal, Type, Pat, State); - false -> {Map, Literal} + Literal = literal_type(Pat), + case t_is_none(t_inf(Literal, Type, Opaques)) of + true -> + bind_opaque_pats(Literal, Type, Pat, State); + false -> {Map, Literal} + end; + false -> + %% Retry with the unfolded pattern + {Map1, [PatType]} + = bind_pat_vars([Pat0], [Type], [], Map, State, Rev), + {Map1, PatType} end; map -> - {Map, t_map([])}; + MapT = t_inf(Type, t_map(), Opaques), + case t_is_none(MapT) of + true -> + bind_opaque_pats(t_map(), Type, Pat, State); + false -> + case Rev of + %% TODO: Reverse matching (propagating a matched subset back to a value) + true -> {Map, MapT}; + false -> + FoldFun = + fun(Pair, {MapAcc, ListAcc}) -> + %% Only exact (:=) can appear in patterns + exact = cerl:concrete(cerl:map_pair_op(Pair)), + Key = cerl:map_pair_key(Pair), + KeyType = + case cerl:type(Key) of + var -> + case state__lookup_type_for_letrec(Key, State) of + error -> lookup_type(Key, MapAcc); + {ok, RecType} -> RecType + end; + literal -> + literal_type(Key) + end, + Bind = erl_types:t_map_get(KeyType, MapT), + {MapAcc1, [ValType]} = + bind_pat_vars([cerl:map_pair_val(Pair)], + [Bind], [], MapAcc, State, Rev), + case t_is_singleton(KeyType, Opaques) of + true -> {MapAcc1, [{KeyType, ValType}|ListAcc]}; + false -> {MapAcc1, ListAcc} + end + end, + {Map1, Pairs} = lists:foldl(FoldFun, {Map, []}, cerl:map_es(Pat)), + {Map1, t_inf(MapT, t_map(Pairs))} + end + end; tuple -> Es = cerl:tuple_es(Pat), {TypedRecord, Prototype} = @@ -1682,7 +1765,7 @@ bind_opaque_pats(GenType, Type, Pat, State) -> %% bind_guard(Guard, Map, State) -> - try bind_guard(Guard, Map, dict:new(), pos, State) of + try bind_guard(Guard, Map, maps:new(), pos, State) of {Map1, _Type} -> Map1 catch throw:{fail, Warning} -> {error, Warning}; @@ -1710,20 +1793,63 @@ bind_guard(Guard, Map, Env, Eval, State) -> 'try' -> Arg = cerl:try_arg(Guard), [Var] = cerl:try_vars(Guard), + EVars = cerl:try_evars(Guard), %%?debug("Storing: ~w\n", [Var]), - NewEnv = dict:store(get_label(Var), Arg, Env), - bind_guard(cerl:try_body(Guard), Map, NewEnv, Eval, State); + Map1 = join_maps_begin(Map), + Map2 = mark_as_fresh(EVars, Map1), + %% Visit handler first so we know if it should be ignored + {{HandlerMap, HandlerType}, HandlerE} = + try {bind_guard(cerl:try_handler(Guard), Map2, Env, Eval, State), none} + catch throw:HE -> + {{Map2, t_none()}, HE} + end, + BodyEnv = maps:put(get_label(Var), Arg, Env), + Wanted = case Eval of pos -> t_atom(true); neg -> t_atom(false); + dont_know -> t_any() end, + case t_is_none(t_inf(HandlerType, Wanted)) of + %% Handler won't save us; pretend it does not exist + true -> bind_guard(cerl:try_body(Guard), Map, BodyEnv, Eval, State); + false -> + {{BodyMap, BodyType}, BodyE} = + try {bind_guard(cerl:try_body(Guard), Map1, BodyEnv, + Eval, State), none} + catch throw:BE -> + {{Map1, t_none()}, BE} + end, + Map3 = join_maps_end([BodyMap, HandlerMap], Map1), + case t_is_none(Sup = t_sup(BodyType, HandlerType)) of + true -> + %% Pick a reason. N.B. We assume that the handler is always + %% compiler-generated if the body is; that way, we won't need to + %% check. + Fatality = case {BodyE, HandlerE} of + {{fatal_fail, _}, _} -> fatal_fail; + {_, {fatal_fail, _}} -> fatal_fail; + _ -> fail + end, + throw({Fatality, + case {BodyE, HandlerE} of + {{_, Rsn}, _} when Rsn =/= none -> Rsn; + {_, {_,Rsn}} -> Rsn; + _ -> none + end}); + false -> {Map3, Sup} + end + end; tuple -> Es0 = cerl:tuple_es(Guard), {Map1, Es} = bind_guard_list(Es0, Map, Env, dont_know, State), {Map1, t_tuple(Es)}; map -> - {Map, t_map([])}; + case Eval of + dont_know -> handle_guard_map(Guard, Map, Env, State); + _PosOrNeg -> {Map, t_none()} %% Map exprs do not produce bools + end; 'let' -> Arg = cerl:let_arg(Guard), [Var] = cerl:let_vars(Guard), %%?debug("Storing: ~w\n", [Var]), - NewEnv = dict:store(get_label(Var), Arg, Env), + NewEnv = maps:put(get_label(Var), Arg, Env), bind_guard(cerl:let_body(Guard), Map, NewEnv, Eval, State); values -> Es = cerl:values_es(Guard), @@ -1732,7 +1858,7 @@ bind_guard(Guard, Map, Env, Eval, State) -> {Map, Type}; var -> ?debug("Looking for var(~w)...", [cerl_trees:get_label(Guard)]), - case dict:find(get_label(Guard), Env) of + case maps:find(get_label(Guard), Env) of error -> ?debug("Did not find it\n", []), Type = lookup_type(Guard, Map), @@ -1761,7 +1887,7 @@ handle_guard_call(Guard, Map, Env, Eval, State) -> {erlang, F, 1} when F =:= is_atom; F =:= is_boolean; F =:= is_binary; F =:= is_bitstring; F =:= is_float; F =:= is_function; - F =:= is_integer; F =:= is_list; + F =:= is_integer; F =:= is_list; F =:= is_map; F =:= is_number; F =:= is_pid; F =:= is_port; F =:= is_reference; F =:= is_tuple -> handle_guard_type_test(Guard, F, Map, Env, Eval, State); @@ -1841,6 +1967,7 @@ bind_type_test(Eval, TypeTest, ArgType, State) -> is_function -> t_fun(); is_integer -> t_integer(); is_list -> t_maybe_improper_list(); + is_map -> t_map(); is_number -> t_number(); is_pid -> t_pid(); is_port -> t_port(); @@ -2349,6 +2476,30 @@ bind_guard_list([G|Gs], Map, Env, Eval, State, Acc) -> bind_guard_list([], Map, _Env, _Eval, _State, Acc) -> {Map, lists:reverse(Acc)}. +handle_guard_map(Guard, Map, Env, State) -> + Pairs = cerl:map_es(Guard), + Arg = cerl:map_arg(Guard), + {Map1, ArgType0} = bind_guard(Arg, Map, Env, dont_know, State), + ArgType1 = t_inf(t_map(), ArgType0), + case t_is_none_or_unit(ArgType1) of + true -> {Map1, t_none()}; + false -> + {Map2, TypePairs} = bind_guard_map_pairs(Pairs, Map1, Env, State, []), + {Map2, lists:foldl(fun({KV,assoc},Acc) -> erl_types:t_map_put(KV,Acc); + ({KV,exact},Acc) -> erl_types:t_map_update(KV,Acc) + end, ArgType1, TypePairs)} + end. + +bind_guard_map_pairs([], Map, _Env, _State, PairAcc) -> + {Map, lists:reverse(PairAcc)}; +bind_guard_map_pairs([Pair|Pairs], Map, Env, State, PairAcc) -> + Key = cerl:map_pair_key(Pair), + Val = cerl:map_pair_val(Pair), + Op = cerl:map_pair_op(Pair), + {Map1, [K,V]} = bind_guard_list([Key,Val],Map,Env,dont_know,State), + bind_guard_map_pairs(Pairs, Map1, Env, State, + [{{K,V},cerl:concrete(Op)}|PairAcc]). + -type eval() :: 'pos' | 'neg' | 'dont_know'. -spec signal_guard_fail(eval(), cerl:c_call(), [type()], @@ -2421,7 +2572,9 @@ filter_fail_clauses([Clause|Left]) -> case (cerl:clause_pats(Clause) =:= []) of true -> Body = cerl:clause_body(Clause), - case cerl:is_literal(Body) andalso (cerl:concrete(Body) =:= fail) of + case cerl:is_literal(Body) andalso (cerl:concrete(Body) =:= fail) orelse + cerl:is_c_primop(Body) andalso + (cerl:atom_val(cerl:primop_name(Body)) =:= match_fail) of true -> filter_fail_clauses(Left); false -> [Clause|filter_fail_clauses(Left)] end; @@ -2535,10 +2688,10 @@ join_maps_end(Maps, MapOut) -> #map{ref = Ref, modified_stack = [{M1,R1} | S]} = MapOut, true = lists:all(fun(M) -> M#map.ref =:= Ref end, Maps), % sanity Keys0 = lists:usort(lists:append([M#map.modified || M <- Maps])), - #map{dict = Dict, subst = Subst} = MapOut, + #map{map = Map, subst = Subst} = MapOut, Keys = [Key || Key <- Keys0, - dict:is_key(Key, Dict) orelse dict:is_key(Key, Subst)], + maps:is_key(Key, Map) orelse maps:is_key(Key, Subst)], Out = case Maps of [] -> join_maps(Maps, MapOut); _ -> join_maps(Keys, Maps, MapOut) @@ -2549,8 +2702,8 @@ join_maps_end(Maps, MapOut) -> modified_stack = S}. join_maps(Maps, MapOut) -> - #map{dict = Dict, subst = Subst} = MapOut, - Keys = ordsets:from_list(dict:fetch_keys(Dict) ++ dict:fetch_keys(Subst)), + #map{map = Map, subst = Subst} = MapOut, + Keys = ordsets:from_list(maps:keys(Map) ++ maps:keys(Subst)), join_maps(Keys, Maps, MapOut). join_maps(Keys, Maps, MapOut) -> @@ -2579,11 +2732,11 @@ join_maps_one_key([], _Key, AccType) -> -ifdef(DEBUG). debug_join_check(Maps, MapOut, Out) -> - #map{dict = Dict, subst = Subst} = Out, - #map{dict = Dict2, subst = Subst2} = join_maps(Maps, MapOut), - F = fun(D) -> lists:keysort(1, dict:to_list(D)) end, + #map{map = Map, subst = Subst} = Out, + #map{map = Map2, subst = Subst2} = join_maps(Maps, MapOut), + F = fun(D) -> lists:keysort(1, maps:to_list(D)) end, [throw({bug, join_maps}) || - F(Dict) =/= F(Dict2) orelse F(Subst) =/= F(Subst2)]. + F(Map) =/= F(Map2) orelse F(Subst) =/= F(Subst2)]. -else. debug_join_check(_Maps, _MapOut, _Out) -> ok. -endif. @@ -2614,15 +2767,15 @@ enter_type(Key, Val, MS) -> enter_type_lists(Keys, t_to_tlist(Val), MS) end; false -> - #map{dict = Dict, subst = Subst} = MS, + #map{map = Map, subst = Subst} = MS, KeyLabel = get_label(Key), - case dict:find(KeyLabel, Subst) of + case maps:find(KeyLabel, Subst) of {ok, NewKey} -> ?debug("Binding ~p to ~p\n", [KeyLabel, NewKey]), enter_type(NewKey, Val, MS); error -> ?debug("Entering ~p :: ~s\n", [KeyLabel, t_to_string(Val)]), - case dict:find(KeyLabel, Dict) of + case maps:find(KeyLabel, Map) of {ok, Value} -> case erl_types:t_is_equal(Val, Value) of true -> MS; @@ -2634,13 +2787,14 @@ enter_type(Key, Val, MS) -> end end. -store_map(Key, Val, #map{dict = Dict, ref = undefined} = Map) -> - Map#map{dict = dict:store(Key, Val, Dict)}; -store_map(Key, Val, #map{dict = Dict, modified = Mod} = Map) -> - Map#map{dict = dict:store(Key, Val, Dict), modified = [Key | Mod]}. +store_map(Key, Val, #map{map = Map, ref = undefined} = MapRec) -> + MapRec#map{map = maps:put(Key, Val, Map)}; +store_map(Key, Val, #map{map = Map, modified = Mod} = MapRec) -> + MapRec#map{map = maps:put(Key, Val, Map), modified = [Key | Mod]}. -enter_subst(Key, Val, #map{subst = Subst} = MS) -> +enter_subst(Key, Val0, #map{subst = Subst} = MS) -> KeyLabel = get_label(Key), + Val = dialyzer_utils:refold_pattern(Val0), case cerl:is_literal(Val) of true -> store_map(KeyLabel, literal_type(Val), MS); @@ -2649,7 +2803,7 @@ enter_subst(Key, Val, #map{subst = Subst} = MS) -> false -> MS; true -> ValLabel = get_label(Val), - case dict:find(ValLabel, Subst) of + case maps:find(ValLabel, Subst) of {ok, NewVal} -> enter_subst(Key, NewVal, MS); error -> @@ -2663,22 +2817,22 @@ enter_subst(Key, Val, #map{subst = Subst} = MS) -> end. store_subst(Key, Val, #map{subst = S, ref = undefined} = Map) -> - Map#map{subst = dict:store(Key, Val, S)}; + Map#map{subst = maps:put(Key, Val, S)}; store_subst(Key, Val, #map{subst = S, modified = Mod} = Map) -> - Map#map{subst = dict:store(Key, Val, S), modified = [Key | Mod]}. + Map#map{subst = maps:put(Key, Val, S), modified = [Key | Mod]}. -lookup_type(Key, #map{dict = Dict, subst = Subst}) -> - lookup(Key, Dict, Subst, t_none()). +lookup_type(Key, #map{map = Map, subst = Subst}) -> + lookup(Key, Map, Subst, t_none()). -lookup(Key, Dict, Subst, AnyNone) -> +lookup(Key, Map, Subst, AnyNone) -> case cerl:is_literal(Key) of true -> literal_type(Key); false -> Label = get_label(Key), - case dict:find(Label, Subst) of - {ok, NewKey} -> lookup(NewKey, Dict, Subst, AnyNone); + case maps:find(Label, Subst) of + {ok, NewKey} -> lookup(NewKey, Map, Subst, AnyNone); error -> - case dict:find(Label, Dict) of + case maps:find(Label, Map) of {ok, Val} -> Val; error -> AnyNone end @@ -2703,6 +2857,9 @@ mark_as_fresh([Tree|Left], Map) -> bitstr -> %% The Size field is not fresh. {SubTrees1 -- [cerl:bitstr_size(Tree)], Map}; + map_pair -> + %% The keys are not fresh + {SubTrees1 -- [cerl:map_pair_key(Tree)], Map}; var -> {SubTrees1, enter_type(Tree, t_any(), Map)}; _ -> @@ -2713,12 +2870,12 @@ mark_as_fresh([], Map) -> Map. -ifdef(DEBUG). -debug_pp_map(#map{dict = Dict}=Map) -> - Keys = dict:fetch_keys(Dict), +debug_pp_map(#map{map = Map}=MapRec) -> + Keys = maps:keys(Map), io:format("Map:\n", []), lists:foreach(fun (Key) -> io:format("\t~w :: ~s\n", - [Key, t_to_string(lookup_type(Key, Map))]) + [Key, t_to_string(lookup_type(Key, MapRec))]) end, Keys), ok. -else. |