diff options
Diffstat (limited to 'lib/dialyzer/src/dialyzer_typesig.erl')
-rw-r--r-- | lib/dialyzer/src/dialyzer_typesig.erl | 963 |
1 files changed, 788 insertions, 175 deletions
diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl index d0d27740f3..0df003a035 100644 --- a/lib/dialyzer/src/dialyzer_typesig.erl +++ b/lib/dialyzer/src/dialyzer_typesig.erl @@ -28,7 +28,7 @@ -module(dialyzer_typesig). --export([analyze_scc/5]). +-export([analyze_scc/6]). -export([get_safe_underapprox/2]). -import(erl_types, @@ -78,6 +78,8 @@ -record(constraint_list, {type :: 'conj' | 'disj', list :: [constr()], deps :: [dep()], + masks :: [{dep(),[non_neg_integer()]}] | + {'d',dict()}, id :: {'list', dep()}}). -type constraint_list() :: #constraint_list{}. @@ -91,23 +93,26 @@ -type typesig_scc() :: [{mfa(), {cerl:c_var(), cerl:c_fun()}, dict()}]. -type typesig_funmap() :: [{type_var(), type_var()}]. %% Orddict --record(state, {callgraph :: dialyzer_callgraph:callgraph(), - cs = [] :: [constr()], - cmap = dict:new() :: dict(), - fun_map = [] :: typesig_funmap(), - fun_arities = dict:new() :: dict(), - in_match = false :: boolean(), - in_guard = false :: boolean(), - module :: module(), - name_map = dict:new() :: dict(), - next_label :: label(), - self_recs :: [label()], - plt :: dialyzer_plt:plt(), - prop_types = dict:new() :: dict(), - records = dict:new() :: dict(), - opaques = [] :: [erl_types:erl_type()], - scc = [] :: [type_var()], - mfas = [] :: [dialyzer_callgraph:mfa_or_funlbl()] +-type dict_or_ets() :: {'d', dict()} | {'e', ets:tid()}. + +-record(state, {callgraph :: dialyzer_callgraph:callgraph(), + cs = [] :: [constr()], + cmap = {'d', dict:new()} :: dict_or_ets(), + fun_map = [] :: typesig_funmap(), + fun_arities = dict:new() :: dict(), + in_match = false :: boolean(), + in_guard = false :: boolean(), + module :: module(), + name_map = dict:new() :: dict(), + next_label = 0 :: label(), + self_rec :: erl_types:erl_type(), + plt :: dialyzer_plt:plt(), + prop_types = {'d', dict:new()} :: dict_or_ets(), + records = dict:new() :: dict(), + opaques = [] :: [erl_types:erl_type()], + scc = [] :: [type_var()], + mfas :: [tuple()], + solvers = [] :: [solver()] }). %%----------------------------------------------------------------------------- @@ -119,8 +124,10 @@ %%-define(DEBUG_CONSTRAINTS, true). -ifdef(DEBUG). -define(DEBUG_NAME_MAP, true). +-define(DEBUG_LOOP_DETECTION, true). -endif. %%-define(DEBUG_NAME_MAP, true). +%%-define(DEBUG_LOOP_DETECTION, true). -ifdef(DEBUG). -define(debug(__String, __Args), io:format(__String, __Args)). @@ -139,7 +146,7 @@ %%----------------------------------------------------------------------------- %% Analysis of strongly connected components. %% -%% analyze_scc(SCC, NextLabel, CallGraph, PLT, PropTypes) -> FunTypes +%% analyze_scc(SCC, NextLabel, CallGraph, PLT, PropTypes, Solvers) -> FunTypes %% %% SCC - [{MFA, Def, Records}] %% where Def = {Var, Fun} as in the Core Erlang module definitions. @@ -152,15 +159,17 @@ %% about functions that can be called by this SCC. %% PropTypes - A dictionary. %% FunTypes - A dictionary. +%% Solvers - User specified solvers. %%----------------------------------------------------------------------------- -spec analyze_scc(typesig_scc(), label(), dialyzer_callgraph:callgraph(), - dialyzer_plt:plt(), dict()) -> dict(). + dialyzer_plt:plt(), dict(), [solver()]) -> dict(). -analyze_scc(SCC, NextLabel, CallGraph, Plt, PropTypes) -> +analyze_scc(SCC, NextLabel, CallGraph, Plt, PropTypes, Solvers0) -> + Solvers = solvers(Solvers0), assert_format_of_scc(SCC), - State1 = new_state(SCC, NextLabel, CallGraph, Plt, PropTypes), + State1 = new_state(SCC, NextLabel, CallGraph, Plt, PropTypes, Solvers), DefSet = add_def_list([Var || {_MFA, {Var, _Fun}, _Rec} <- SCC], sets:new()), State2 = traverse_scc(SCC, DefSet, State1), State3 = state__finalize(State2), @@ -174,6 +183,9 @@ assert_format_of_scc([{_MFA, {_Var, _Fun}, _Records}|Left]) -> assert_format_of_scc([]) -> ok. +solvers([]) -> [v2]; +solvers(Solvers) -> Solvers. + %% ============================================================================ %% %% Gets the constraints by traversing the code. @@ -1661,18 +1673,23 @@ get_bif_test_constr(Dst, Arg, Type, State) -> solve([Fun], State) -> ?debug("============ Analyzing Fun: ~w ===========\n", [debug_lookup_name(Fun)]), - solve_fun(Fun, dict:new(), State); + solve_fun(Fun, map_new(), State); solve([_|_] = SCC, State) -> ?debug("============ Analyzing SCC: ~w ===========\n", [[debug_lookup_name(F) || F <- SCC]]), - solve_scc(SCC, dict:new(), State, false). + {Parallel, NewState} = + case parallel_split(SCC) of + false -> {false, State}; + SplitSCC -> {SplitSCC, minimize_state(State)} + end, + solve_scc(SCC, Parallel, map_new(), NewState, false). solve_fun(Fun, FunMap, State) -> Cs = state__get_cs(Fun, State), Deps = get_deps(Cs), Ref = mk_constraint_ref(Fun, Deps), %% Note that functions are always considered to succeed. - {ok, _MapDict, NewMap} = solve_ref_or_list(Ref, FunMap, dict:new(), State), + NewMap = solve(Fun, Ref, FunMap, State), NewType = lookup_type(Fun, NewMap), NewFunMap1 = case state__get_rec_var(Fun, State) of error -> FunMap; @@ -1680,21 +1697,23 @@ solve_fun(Fun, FunMap, State) -> end, enter_type(Fun, NewType, NewFunMap1). -solve_scc(SCC, Map, State, TryingUnit) -> - State1 = state__mark_as_non_self_rec(SCC, State), +solve_scc(SCC, Parallel, Map, State, TryingUnit) -> Vars0 = [{Fun, state__get_rec_var(Fun, State)} || Fun <- SCC], Vars = [Var || {_, {ok, Var}} <- Vars0], Funs = [Fun || {Fun, {ok, _}} <- Vars0], Types = unsafe_lookup_type_list(Funs, Map), RecTypes = [t_limit(Type, ?TYPE_LIMIT) || Type <- Types], CleanMap = lists:foldl(fun(Fun, AccFunMap) -> - dict:erase(t_var_name(Fun), AccFunMap) + erase_type(t_var_name(Fun), AccFunMap) end, Map, SCC), Map1 = enter_type_lists(Vars, RecTypes, CleanMap), ?debug("Checking SCC: ~w\n", [[debug_lookup_name(F) || F <- SCC]]), - SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State1) end, - Map2 = lists:foldl(SolveFun, Map1, SCC), FunSet = ordsets:from_list([t_var_name(F) || F <- SCC]), + Map2 = + case Parallel of + false -> solve_whole_scc(SCC, Map1, State); + SplitSCC -> solve_whole_scc_parallel(SplitSCC, Map1, State) + end, case maps_are_equal(Map2, Map, FunSet) of true -> ?debug("SCC ~w reached fixpoint\n", [SCC]), @@ -1708,20 +1727,134 @@ solve_scc(SCC, Map, State, TryingUnit) -> true -> t_fun(t_fun_args(T), t_unit()) end || T <- NewTypes], Map3 = enter_type_lists(Funs, UnitTypes, Map2), - solve_scc(SCC, Map3, State, true); + solve_scc(SCC, Parallel, Map3, State, true); false -> + case Parallel of + false -> true; + _ -> dispose_state(State) + end, Map2 end; false -> ?debug("SCC ~w did not reach fixpoint\n", [SCC]), - solve_scc(SCC, Map2, State, TryingUnit) + solve_scc(SCC, Parallel, Map2, State, TryingUnit) + end. + +solve_whole_scc(SCC, Map, State) -> + SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end, + lists:foldl(SolveFun, Map, SCC). + +%%------------------------------------------------------------------------------ + +-define(worth_it, 42). + +parallel_split(SCC) -> + Length = length(SCC), + case Length > 2*?worth_it of + false -> false; + true -> + case min(dialyzer_utils:parallelism(), 8) of + 1 -> false; + CPUs -> + FullShare = Length div CPUs + 1, + Unit = max(FullShare, ?worth_it), + split(SCC, Unit, []) + end + end. + +minimize_state(#state{ + cmap = {d, CMap}, + fun_map = FunMap, + fun_arities = FunArities, + self_rec = SelfRec, + prop_types = {d, PropTypes}, + opaques = Opaques, + solvers = Solvers + }) -> + ETSCMap = ets:new(cmap,[{read_concurrency, true}]), + ETSPropTypes = ets:new(prop_types,[{read_concurrency, true}]), + true = ets:insert(ETSCMap, dict:to_list(CMap)), + true = ets:insert(ETSPropTypes, dict:to_list(PropTypes)), + #state + {cmap = {e, ETSCMap}, + fun_map = FunMap, + fun_arities = FunArities, + self_rec = SelfRec, + prop_types = {e, ETSPropTypes}, + opaques = Opaques, + solvers = Solvers + }. + +dispose_state(#state{cmap = {e, ETSCMap}, + prop_types = {e, ETSPropTypes}}) -> + true = ets:delete(ETSCMap), + true = ets:delete(ETSPropTypes). + +solve_whole_scc_parallel(SplitSCC, Map, State) -> + Workers = spawn_workers(SplitSCC, Map, State), + wait_results(Workers, Map, fold_res_fun(State)). + +spawn_workers(SplitSCC, Map, State) -> + Spawner = solve_scc_spawner(self(), Map, State), + lists:foreach(Spawner, SplitSCC), + length(SplitSCC). + +wait_results(0, Map, _FoldResFun) -> + Map; +wait_results(Pending, Map, FoldResFun) -> + Res = receive_scc_result(), + NewMap = lists:foldl(FoldResFun, Map, Res), + wait_results(Pending-1, NewMap, FoldResFun). + +solve_scc_spawner(Parent, Map, State) -> + fun(SCCPart) -> + spawn_link(fun() -> solve_scc_worker(Parent, SCCPart, Map, State) end) + end. + +split([], _Unit, Acc) -> + Acc; +split(List, Unit, Acc) -> + {Taken, Rest} = + try + lists:split(Unit, List) + catch + _:_ -> {List, []} + end, + split(Rest, Unit, [Taken|Acc]). + +solve_scc_worker(Parent, SCCPart, Map, State) -> + SolveFun = fun(X, Y) -> scc_fold_fun(X, Y, State) end, + FinalMap = lists:foldl(SolveFun, Map, SCCPart), + Res = + [{F, t_limit(unsafe_lookup_type(F, FinalMap), ?TYPE_LIMIT)} || + F <- SCCPart], + send_scc_result(Parent, Res). + +fold_res_fun(State) -> + fun({F, Type}, Map) -> + case state__get_rec_var(F, State) of + {ok, R} -> + enter_type(R, Type, enter_type(F, Type, Map)); + error -> + enter_type(F, Type, Map) + end end. +receive_scc_result() -> + receive + {scc_fun, Res} -> Res + end. + +send_scc_result(Parent, Res) -> + Parent ! {scc_fun, Res}. + +%%------------------------------------------------------------------------------ + scc_fold_fun(F, FunMap, State) -> Deps = get_deps(state__get_cs(F, State)), Cs = mk_constraint_ref(F, Deps), %% Note that functions are always considered to succeed. - {ok, _NewMapDict, Map} = solve_ref_or_list(Cs, FunMap, dict:new(), State), + Map = solve(F, Cs, FunMap, State), NewType0 = unsafe_lookup_type(F, Map), NewType = t_limit(NewType0, ?TYPE_LIMIT), NewFunMap = case state__get_rec_var(F, State) of @@ -1734,15 +1867,440 @@ scc_fold_fun(F, FunMap, State) -> format_type(NewType)]), NewFunMap. +solve(Fun, Cs, FunMap, State) -> + Solvers = State#state.solvers, + R = [solver(S, solve_fun(S, Fun, Cs, FunMap, State)) || S <- Solvers], + check_solutions(R, Fun, no_solver, no_map). + +solver(Solver, SolveFun) -> + ?debug("Start solver ~w\n", [Solver]), + try timer:tc(SolveFun) of + {Time, {ok, Map}} -> + ?debug("End solver ~w (~w microsecs)\n", [Solver, Time]), + {Solver, Map, Time}; + {_, _R} -> + ?debug("Solver ~w returned unexpected result:\n ~P\n", + [Solver, _R, 60]), + throw(error) + catch E:R -> + io:format("Solver ~w failed: ~w:~p\n ~p\n", + [Solver, E, R, erlang:get_stacktrace()]), + throw(error) + end. + +solve_fun(v1, _Fun, Cs, FunMap, State) -> + fun() -> + {ok, _MapDict, NewMap} = solve_ref_or_list(Cs, FunMap, dict:new(), State), + {ok, NewMap} + end; +solve_fun(v2, Fun, _Cs, FunMap, State) -> + fun() -> v2_solve_ref(Fun, FunMap, State) end. + +check_solutions([], _Fun, _S, Map) -> + Map; +check_solutions([{S1,Map1,_Time1}|Maps], Fun, S, Map) -> + ?debug("Solver ~w needed ~w microsecs\n", [S1, _Time1]), + case Map =:= no_map orelse sane_maps(Map, Map1, [Fun], S, S1) of + true -> + check_solutions(Maps, Fun, S1, Map1); + false -> + ?debug("Constraint solvers do not agree on ~w\n", [Fun]), + pp_map(atom_to_list(S), Map), + pp_map(atom_to_list(S1), Map1), + io:format("A bug was found. Please report it, and use the option " + "`--solver v1' until the bug has been fixed.\n"), + throw(error) + end. + +sane_maps(Map1, Map2, Keys, _S1, _S2) -> + lists:all(fun(Key) -> + V1 = unsafe_lookup_type(Key, Map1), + V2 = unsafe_lookup_type(Key, Map2), + case t_is_equal(V1, V2) of + true -> true; + false -> + ?debug("Constraint solvers do not agree on ~w\n", [Key]), + ?debug("~w: ~s\n", + [_S1, format_type(unsafe_lookup_type(Key, Map1))]), + ?debug("~w: ~s\n", + [_S2, format_type(unsafe_lookup_type(Key, Map2))]), + false + end + end, Keys). + +%% Solver v2 + +-record(v2_state, {constr_data = dict:new() :: dict(), + state :: #state{}}). + +v2_solve_ref(Fun, Map, State) -> + V2State = #v2_state{state = State}, + {ok, NewMap, _, _} = v2_solve_reference(Fun, Map, V2State), + {ok, NewMap}. + +v2_solve(#constraint{}=C, Map, V2State) -> + State = V2State#v2_state.state, + case solve_one_c(C, Map, State#state.opaques) of + error -> + report_failed_constraint(C, Map), + {error, V2State}; + {ok, {NewMap, U}} -> + {ok, NewMap, V2State, U} + end; +v2_solve(#constraint_list{type = disj}=C, Map, V2State) -> + v2_solve_disjunct(C, Map, V2State); +v2_solve(#constraint_list{type = conj}=C, Map, V2State) -> + v2_solve_conjunct(C, Map, V2State); +v2_solve(#constraint_ref{id = Id}, Map, V2State) -> + v2_solve_reference(Id, Map, V2State). + +v2_solve_reference(Id, Map, V2State0) -> + ?debug("Checking ref to fun: ~w\n", [debug_lookup_name(Id)]), + pp_map("Map", Map), + pp_constr_data("solve_ref", V2State0), + Map1 = restore_local_map(V2State0, Id, Map), + State = V2State0#v2_state.state, + Cs = state__get_cs(Id, State), + Res = + case state__is_self_rec(Id, State) of + true -> v2_solve_self_recursive(Cs, Map1, Id, t_none(), V2State0); + false -> v2_solve(Cs, Map1, V2State0) + end, + {FunType, V2State} = + case Res of + {error, V2State1} -> + ?debug("Error solving for function ~p\n", [debug_lookup_name(Id)]), + Arity = state__fun_arity(Id, State), + FunType0 = + case state__prop_domain(t_var_name(Id), State) of + error -> t_fun(Arity, t_none()); + {ok, Dom} -> t_fun(Dom, t_none()) + end, + {FunType0, V2State1}; + {ok, NewMap, V2State1, U} -> + ?debug("Done solving fun: ~p\n", [debug_lookup_name(Id)]), + FunType0 = lookup_type(Id, NewMap), + V2State2 = save_local_map(V2State1, Id, U, NewMap), + {FunType0, V2State2} + end, + ?debug("ref Id=~w Assigned ~s\n", [Id, format_type(FunType)]), + {NewMap1, U1} = enter_var_type(Id, FunType, Map), + {NewMap2, U2} = + case state__get_rec_var(Id, State) of + {ok, Var} -> enter_var_type(Var, FunType, NewMap1); + error -> {NewMap1, []} + end, + {ok, NewMap2, V2State, lists:umerge(U1, U2)}. + +v2_solve_self_recursive(Cs, Map, Id, RecType0, V2State0) -> + ?debug("Solving self recursive ~w\n", [debug_lookup_name(Id)]), + State = V2State0#v2_state.state, + {ok, RecVar} = state__get_rec_var(Id, State), + ?debug("OldRecType ~s\n", [format_type(RecType0)]), + RecType = t_limit(RecType0, ?TYPE_LIMIT), + {Map1, U0} = enter_var_type(RecVar, RecType, Map), + V2State1 = save_updated_vars1(V2State0, Cs, U0), % Probably not necessary + case v2_solve(Cs, Map1, V2State1) of + {error, _V2State}=Error -> + case t_is_none(RecType0) of + true -> + %% Try again and assume that this is a non-terminating function. + Arity = state__fun_arity(Id, State), + NewRecType = t_fun(lists:duplicate(Arity, t_any()), t_unit()), + v2_solve_self_recursive(Cs, Map, Id, NewRecType, V2State0); + false -> + Error + end; + {ok, NewMap, V2State, U} -> + pp_map("recursive finished", NewMap), + NewRecType = unsafe_lookup_type(Id, NewMap), + case t_is_equal(NewRecType, RecType0) of + true -> + {NewMap2, U1} = enter_var_type(RecVar, NewRecType, NewMap), + {ok, NewMap2, V2State, lists:umerge(U, U1)}; + false -> + v2_solve_self_recursive(Cs, Map, Id, NewRecType, V2State0) + end + end. + +enter_var_type(Var, Type, Map0) -> + {Map, Vs} = enter_type2(Var, Type, Map0), + {Map, [t_var_name(V) || V <- Vs]}. + +v2_solve_disjunct(Disj, Map, V2State0) -> + #constraint_list{type = disj, id = _Id, list = Cs, masks = Masks} = Disj, + ?debug("disjunct Id=~w~n", [_Id]), + pp_map("Map", Map), + pp_constr_data("disjunct", V2State0), + case get_flags(V2State0, Disj) of + {V2State1, failed_list} -> {error, V2State1}; % cannot happen + {V2State1, Flags} when Flags =/= [] -> + {ok, V2State, Eval, UL, MapL0, Uneval, Failed} = + v2_solve_disj(Flags, Cs, 1, Map, V2State1, [], [], [], [], false), + ?debug("disj ending _Id=~w Eval=~w, |Uneval|=~w |UL|=~w~n", + [_Id, Eval, length(Uneval), length(UL)]), + if Eval =:= [], Uneval =:= [] -> + {error, failed_list(Disj, V2State0)}; + true -> + {Is0, UnIds} = lists:unzip(Uneval), + MapL = [restore_local_map(V2State, Id, Map) || + Id <- UnIds] ++ MapL0, + %% If some branch has just failed every variable of the + %% non-failed branches need to be checked, not just the + %% updated ones. + U0 = case Failed of + false -> lists:umerge(UL); + true -> constrained_keys(MapL) + end, + if U0 =:= [] -> {ok, Map, V2State, []}; + true -> + NotFailed = lists:umerge(Is0, Eval), + U1 = [V || V <- U0, + var_occurs_everywhere(V, Masks, NotFailed)], + NewMap = join_maps(U1, MapL, Map), + pp_map("NewMap", NewMap), + U = updated_vars_only(U1, Map, NewMap), + ?debug("disjunct finished _Id=~w\n", [_Id]), + {ok, NewMap, V2State, U} + end + end + end. + +var_occurs_everywhere(V, Masks, NotFailed) -> + ordsets:is_subset(NotFailed, get_mask(V, Masks)). + +v2_solve_disj([I|Is], [C|Cs], I, Map0, V2State0, UL, MapL, Eval, Uneval, + Failed0) -> + Id = C#constraint_list.id, + Map1 = restore_local_map(V2State0, Id, Map0), + case v2_solve(C, Map1, V2State0) of + {error, V2State} -> + ?debug("disj error I=~w~n", [I]), + Failed = Failed0 orelse not is_failed_list(C, V2State0), + v2_solve_disj(Is, Cs, I+1, Map0, V2State, UL, MapL, Eval, Uneval, Failed); + {ok, Map, V2State1, U} -> + ?debug("disj I=~w U=~w~n", [I, U]), + V2State = save_local_map(V2State1, Id, U, Map), + pp_map("DMap", Map), + v2_solve_disj(Is, Cs, I+1, Map0, V2State, [U|UL], [Map|MapL], + [I|Eval], Uneval, Failed0) + end; +v2_solve_disj([], [], _I, _Map, V2State, UL, MapL, Eval, Uneval, Failed) -> + {ok, V2State, lists:reverse(Eval), UL, MapL, lists:reverse(Uneval), Failed}; +v2_solve_disj(Is, [C|Cs], I, Map, V2State, UL, MapL, Eval, Uneval0, Failed) -> + Uneval = [{I,C#constraint_list.id} || + not is_failed_list(C, V2State)] ++ Uneval0, + v2_solve_disj(Is, Cs, I+1, Map, V2State, UL, MapL, Eval, Uneval, Failed). + +save_local_map(#v2_state{constr_data = ConData}=V2State, Id, U, Map) -> + Part0 = [{V,dict:fetch(V, Map)} || V <- U], + Part1 = + case dict:find(Id, ConData) of + error -> []; % cannot happen + {ok, {Part2,[]}} -> Part2 + end, + ?debug("save local map Id=~w:\n", [Id]), + Part = lists:ukeymerge(1, lists:keysort(1, Part0), Part1), + pp_map("New Part", dict:from_list(Part0)), + pp_map("Old Part", dict:from_list(Part1)), + pp_map(" => Part", dict:from_list(Part)), + V2State#v2_state{constr_data = dict:store(Id, {Part,[]}, ConData)}. + +restore_local_map(#v2_state{constr_data = ConData}, Id, Map0) -> + case dict:find(Id, ConData) of + error -> Map0; + {ok, failed} -> Map0; + {ok, {[],_}} -> Map0; + {ok, {Part0,U}} -> + Part = [{K,V} || {K,V} <- Part0, not lists:member(K, U)], + ?debug("restore local map Id=~w U=~w\n", [Id, U]), + pp_map("Part", dict:from_list(Part)), + pp_map("Map0", Map0), + Map = lists:foldl(fun({K,V}, D) -> dict:store(K, V, D)end, Map0, Part), + pp_map("Map", Map), + Map + end. + +v2_solve_conjunct(Conj, Map, V2State0) -> + #constraint_list{type = conj, list = Cs} = Conj, + ?debug("conjunct Id=~w~n", [Conj#constraint_list.id]), + IsFlat = case Cs of [#constraint{}|_] -> true; _ -> false end, + case get_flags(V2State0, Conj) of + {V2State, failed_list} -> {error, V2State}; + {V2State, Flags} -> + v2_solve_conj(Flags, Cs, 1, Map, Conj, IsFlat, V2State, [], [], [], + Map, Flags) + end. + +%% LastMap and LastFlags are used for loop detection. +v2_solve_conj([I|Is], [Cs|Tail], I, Map0, Conj, IsFlat, V2State0, + UL, NewFs0, VarsUp, LastMap, LastFlags) -> + ?debug("conj Id=~w I=~w~n", [Conj#constraint_list.id, I]), + true = IsFlat =:= is_record(Cs, constraint), + pp_constr_data("conj", V2State0), + case v2_solve(Cs, Map0, V2State0) of + {error, V2State1} -> {error, failed_list(Conj, V2State1)}; + {ok, Map, V2State1, []} -> + v2_solve_conj(Is, Tail, I+1, Map, Conj, IsFlat, V2State1, + UL, NewFs0, VarsUp, LastMap, LastFlags); + {ok, Map, V2State1, U} when IsFlat -> % optimization + %% It is ensured by enumerate_constraints() that every + %% #constraint{} has a conjunct as parent, and that such a + %% parent has nothing but #constraint{}:s as children, a fact + %% which is used here to simplify the flag calculation. + Mask = lists:umerge([get_mask(V, Conj#constraint_list.masks) || V <- U]), + {Is1, NewF} = add_mask_to_flags(Is, Mask, I, []), + NewFs = [NewF|NewFs0], + v2_solve_conj(Is1, Tail, I+1, Map, Conj, IsFlat, V2State1, + [U|UL], NewFs, VarsUp, LastMap, LastFlags); + {ok, Map, V2State1, U} -> + #constraint_list{masks = Masks, list = AllCs} = Conj, + M = lists:keydelete(I, 1, vars_per_child(U, Masks)), + {V2State2, NewF0} = save_updated_vars_list(AllCs, M, V2State1), + {NewF, F} = lists:splitwith(fun(J) -> J < I end, NewF0), + Is1 = lists:umerge(Is, F), + NewFs = [NewF|NewFs0], + v2_solve_conj(Is1, Tail, I+1, Map, Conj, IsFlat, V2State2, + [U|UL], NewFs, VarsUp, LastMap, LastFlags) + end; +v2_solve_conj([], _Cs, _I, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, + LastMap, LastFlags) -> + U = lists:umerge(UL), + case lists:umerge(NewFs) of + [] -> + ?debug("conjunct finished Id=~w\n", [Conj#constraint_list.id]), + {ok, Map, V2State, lists:umerge([U|VarsUp])}; + NewFlags when NewFlags =:= LastFlags, Map =:= LastMap -> + %% A loop was detected! The cause is some bug, possibly in erl_types. + %% The evaluation continues, but the results can be wrong. + report_detected_loop(Conj), + {ok, Map, V2State, lists:umerge([U|VarsUp])}; + NewFlags -> + #constraint_list{type = conj, list = Cs} = Conj, + v2_solve_conj(NewFlags, Cs, 1, Map, Conj, IsFlat, V2State, + [], [], [U|VarsUp], Map, NewFlags) + end; +v2_solve_conj(Is, [_|Tail], I, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, + LastMap, LastFlags) -> + v2_solve_conj(Is, Tail, I+1, Map, Conj, IsFlat, V2State, UL, NewFs, VarsUp, + LastMap, LastFlags). + +-ifdef(DEBUG_LOOP_DETECTION). +report_detected_loop(Conj) -> + io:format("A loop was detected in ~w\n", [Conj#constraint_list.id]). +-else. +report_detected_loop(_) -> + ok. +-endif. + +add_mask_to_flags(Flags, [Im|M], I, L) when I > Im -> + add_mask_to_flags(Flags, M, I, [Im|L]); +add_mask_to_flags(Flags, [_|M], _I, L) -> + {lists:umerge(Flags, M), lists:reverse(L)}. + +get_mask(V, {d, Masks}) -> + case dict:find(V, Masks) of + error -> []; + {ok, M} -> M + end; +get_mask(V, Masks) -> + case lists:keyfind(V, 1, Masks) of + false -> []; + {V, M} -> M + end. + +get_flags(#v2_state{constr_data = ConData}=V2State0, C) -> + #constraint_list{id = Id, list = Cs, masks = Masks} = C, + case dict:find(Id, ConData) of + error -> + ?debug("get_flags Id=~w Flags=all ~w\n", [Id, length(Cs)]), + V2State = V2State0#v2_state{constr_data = dict:store(Id, {[],[]}, ConData)}, + {V2State, lists:seq(1, length(Cs))}; + {ok, failed} -> + {V2State0, failed_list}; + {ok, {Part,U}} when U =/= [] -> + ?debug("get_flags Id=~w U=~w\n", [Id, U]), + V2State = V2State0#v2_state{constr_data = dict:store(Id, {Part,[]}, ConData)}, + save_updated_vars_list(Cs, vars_per_child(U, Masks), V2State) + end. + +vars_per_child(U, Masks) -> + family([{I, V} || V <- lists:usort(U), I <- get_mask(V, Masks)]). + +save_updated_vars_list(Cs, IU, V2State) -> + save_updated_vars_list1(Cs, IU, V2State, 1, []). + +save_updated_vars_list1([C|Cs], [{I,U}|IU], V2State0, I, Is) -> + V2State = save_updated_vars(C, U, V2State0), + save_updated_vars_list1(Cs, IU, V2State, I+1, [I|Is]); +save_updated_vars_list1([], [], V2State, _I, Is) -> + {V2State, lists:reverse(Is)}; +save_updated_vars_list1([_|Cs], IU, V2State, I, Is) -> + save_updated_vars_list1(Cs, IU, V2State, I+1, Is). + +save_updated_vars(#constraint{}, _, V2State) -> + V2State; +save_updated_vars(#constraint_list{}=C, U, V2State0) -> + save_updated_vars1(V2State0, C, U); +save_updated_vars(#constraint_ref{id = Id}, U, V2State) -> + Cs = state__get_cs(Id, V2State#v2_state.state), + save_updated_vars(Cs, U, V2State). + +save_updated_vars1(V2State, C, U) -> + #v2_state{constr_data = ConData} = V2State, + #constraint_list{id = Id} = C, + case dict:find(Id, ConData) of + error -> V2State; % error means everything is flagged + {ok, failed} -> V2State; + {ok, {Part,U0}} -> + %% Duplicates are not so common; let masks/2 remove them. + U1 = U ++ U0, + V2State#v2_state{constr_data = dict:store(Id, {Part,U1}, ConData)} + end. + +-ifdef(DEBUG). +pp_constr_data(_Tag, #v2_state{constr_data = D}) -> + io:format("Constr data at ~p\n", [_Tag]), + _ = [begin + case _PartU of + {_Part, _U} -> + io:format("Id: ~w Vars: ~w\n", [_Id, _U]), + [pp_map("Part", dict:from_list(_Part)) || _Part =/= []]; + failed -> + io:format("Id: ~w failed list\n", [_Id]) + end + end || + {_Id, _PartU} <- lists:keysort(1, dict:to_list(D))], + ok. + +-else. +pp_constr_data(_Tag, _V2State) -> + ok. +-endif. + +failed_list(#constraint_list{id = Id}, #v2_state{constr_data = D}=V2State) -> + ?debug("error list ~w~n", [Id]), + V2State#v2_state{constr_data = dict:store(Id, failed, D)}. + +is_failed_list(#constraint_list{id = Id}, #v2_state{constr_data = D}) -> + dict:find(Id, D) =:= {ok, failed}. + +%% Solver v1 + solve_ref_or_list(#constraint_ref{id = Id, deps = Deps}, Map, MapDict, State) -> {OldLocalMap, Check} = case dict:find(Id, MapDict) of - error -> {dict:new(), false}; + error -> {map_new(), false}; {ok, M} -> {M, true} end, ?debug("Checking ref to fun: ~w\n", [debug_lookup_name(Id)]), + %% Note: mk_constraint_ref() has already removed Id from Deps. The + %% reason for doing it there is that it makes it easy for + %% calculate_masks() to make the corresponding adjustment for + %% version v2. CheckDeps = ordsets:del_element(t_var_name(Id), Deps), + true = CheckDeps =:= Deps, case Check andalso maps_are_equal(OldLocalMap, Map, CheckDeps) of true -> ?debug("Equal\n", []), @@ -1771,6 +2329,7 @@ solve_ref_or_list(#constraint_ref{id = Id, deps = Deps}, FunType0 = lookup_type(Id, NewMap), {NewMapDict0, FunType0} end, + ?debug(" Id=~w Assigned ~s\n", [Id, format_type(FunType)]), NewMap1 = enter_type(Id, FunType, Map), NewMap2 = case state__get_rec_var(Id, State) of @@ -1783,17 +2342,21 @@ solve_ref_or_list(#constraint_list{type=Type, list = Cs, deps = Deps, id = Id}, Map, MapDict, State) -> {OldLocalMap, Check} = case dict:find(Id, MapDict) of - error -> {dict:new(), false}; + error -> {map_new(), false}; {ok, M} -> {M, true} end, ?debug("Checking ref to list: ~w\n", [Id]), - case Check andalso maps_are_equal(OldLocalMap, Map, Deps) of + if + OldLocalMap =:= error -> {error, MapDict}; true -> - ?debug("~w equal ~w\n", [Type, Id]), - {ok, MapDict, Map}; - false -> - ?debug("~w not equal: ~w. Solving\n", [Type, Id]), - solve_clist(Cs, Type, Id, Deps, MapDict, Map, State) + case Check andalso maps_are_equal(OldLocalMap, Map, Deps) of + true -> + ?debug("~w equal ~w\n", [Type, Id]), + {ok, MapDict, Map}; + false -> + ?debug("~w not equal: ~w. Solving\n", [Type, Id]), + solve_clist(Cs, Type, Id, Deps, MapDict, Map, State) + end end. solve_self_recursive(Cs, Map, MapDict, Id, RecType0, State) -> @@ -1801,8 +2364,8 @@ solve_self_recursive(Cs, Map, MapDict, Id, RecType0, State) -> {ok, RecVar} = state__get_rec_var(Id, State), ?debug("OldRecType ~s\n", [format_type(RecType0)]), RecType = t_limit(RecType0, ?TYPE_LIMIT), - Map1 = enter_type(RecVar, RecType, dict:erase(t_var_name(Id), Map)), - ?debug("\tMap in: ~p\n",[[{X, format_type(Y)}||{X, Y}<-dict:to_list(Map1)]]), + Map1 = enter_type(RecVar, RecType, erase_type(t_var_name(Id), Map)), + pp_map("Map1", Map1), case solve_ref_or_list(Cs, Map1, MapDict, State) of {error, _} = Error -> case t_is_none(RecType0) of @@ -1815,8 +2378,7 @@ solve_self_recursive(Cs, Map, MapDict, Id, RecType0, State) -> Error end; {ok, NewMapDict, NewMap} -> - ?debug("\tMap: ~p\n", - [[{X, format_type(Y)} || {X, Y} <- dict:to_list(NewMap)]]), + pp_map("NewMap", NewMap), NewRecType = unsafe_lookup_type(Id, NewMap), case t_is_equal(NewRecType, RecType0) of true -> @@ -1828,7 +2390,8 @@ solve_self_recursive(Cs, Map, MapDict, Id, RecType0, State) -> solve_clist(Cs, conj, Id, Deps, MapDict, Map, State) -> case solve_cs(Cs, Map, MapDict, State) of - {error, _} = Error -> Error; + {error, NewMapDict} -> + {error, dict:store(Id, error, NewMapDict)}; {ok, NewMapDict, NewMap} = Ret -> case Cs of [_] -> @@ -1850,7 +2413,7 @@ solve_clist(Cs, disj, Id, _Deps, MapDict, Map, State) -> end, {Maps, NewMapDict} = lists:mapfoldl(Fun, MapDict, Cs), case [X || {ok, X} <- Maps] of - [] -> {error, NewMapDict}; + [] -> {error, dict:store(Id, error, NewMapDict)}; MapList -> NewMap = join_maps(MapList), {ok, dict:store(Id, NewMap, NewMapDict), NewMap} @@ -1869,14 +2432,9 @@ solve_cs([#constraint_list{} = C|Tail], Map, MapDict, State) -> solve_cs([#constraint{} = C|Tail], Map, MapDict, State) -> case solve_one_c(C, Map, State#state.opaques) of error -> - ?debug("+++++++++++\nFailed: ~s :: ~s ~w ~s :: ~s\n+++++++++++\n", - [format_type(C#constraint.lhs), - format_type(lookup_type(C#constraint.lhs, Map)), - C#constraint.op, - format_type(C#constraint.rhs), - format_type(lookup_type(C#constraint.rhs, Map))]), + report_failed_constraint(C, Map), {error, MapDict}; - {ok, NewMap} -> + {ok, {NewMap, _U}} -> solve_cs(Tail, NewMap, MapDict, State) end; solve_cs([], Map, MapDict, _State) -> @@ -1897,7 +2455,11 @@ solve_one_c(#constraint{lhs = Lhs, rhs = Rhs, op = Op}, Map, Opaques) -> eq -> case solve_subtype(Lhs, Inf, Map, Opaques) of error -> error; - {ok, Map1} -> solve_subtype(Rhs, Inf, Map1, Opaques) + {ok, {Map1, U1}} -> + case solve_subtype(Rhs, Inf, Map1, Opaques) of + error -> error; + {ok, {Map2, U2}} -> {ok, {Map2, lists:umerge(U1, U2)}} + end end end end. @@ -1920,18 +2482,34 @@ solve_subtype(Type, Inf, Map, Opaques) -> end. %% end. +report_failed_constraint(_C, _Map) -> + ?debug("+++++++++++\nFailed: ~s :: ~s ~w ~s :: ~s\n+++++++++++\n", + [format_type(_C#constraint.lhs), + format_type(lookup_type(_C#constraint.lhs, _Map)), + _C#constraint.op, + format_type(_C#constraint.rhs), + format_type(lookup_type(_C#constraint.rhs, _Map))]). + %% ============================================================================ %% %% Maps and types. %% %% ============================================================================ +map_new() -> + dict:new(). + +join_maps([Map]) -> + Map; join_maps(Maps) -> - Keys = lists:foldl(fun(TmpMap, AccKeys) -> - [Key || Key <- AccKeys, dict:is_key(Key, TmpMap)] - end, - dict:fetch_keys(hd(Maps)), tl(Maps)), - join_maps(Keys, Maps, dict:new()). + Keys = constrained_keys(Maps), + join_maps(Keys, Maps, map_new()). + +constrained_keys(Maps) -> + lists:foldl(fun(TmpMap, AccKeys) -> + [Key || Key <- AccKeys, dict:is_key(Key, TmpMap)] + end, + dict:fetch_keys(hd(Maps)), tl(Maps)). join_maps([Key|Left], Maps = [Map|MapsLeft], AccMap) -> NewType = join_one_key(Key, MapsLeft, lookup_type(Key, Map)), @@ -1994,13 +2572,13 @@ enter_type(Key, Val, Map) when is_integer(Key) -> ?debug("Entering ~s :: ~s\n", [format_type(t_var(Key)), format_type(Val)]), case t_is_any(Val) of true -> - dict:erase(Key, Map); + erase_type(Key, Map); false -> LimitedVal = t_limit(Val, ?INTERNAL_TYPE_LIMIT), case dict:find(Key, Map) of {ok, LimitedVal} -> Map; - {ok, _} -> dict:store(Key, LimitedVal, Map); - error -> dict:store(Key, LimitedVal, Map) + {ok, _} -> map_store(Key, LimitedVal, Map); + error -> map_store(Key, LimitedVal, Map) end end; enter_type(Key, Val, Map) -> @@ -2008,13 +2586,13 @@ enter_type(Key, Val, Map) -> KeyName = t_var_name(Key), case t_is_any(Val) of true -> - dict:erase(KeyName, Map); + erase_type(KeyName, Map); false -> LimitedVal = t_limit(Val, ?INTERNAL_TYPE_LIMIT), case dict:find(KeyName, Map) of {ok, LimitedVal} -> Map; - {ok, _} -> dict:store(KeyName, LimitedVal, Map); - error -> dict:store(KeyName, LimitedVal, Map) + {ok, _} -> map_store(KeyName, LimitedVal, Map); + error -> map_store(KeyName, LimitedVal, Map) end end. @@ -2024,11 +2602,25 @@ enter_type_lists([Key|KeyTail], [Val|ValTail], Map) -> enter_type_lists([], [], Map) -> Map. -enter_type_list([{Key, Val}|Tail], Map) -> +enter_type_list(KeyVals, Map) -> + enter_type_list(KeyVals, Map, []). + +enter_type_list([{Key, Val}|Tail], Map, U0) -> + {Map1,U1} = enter_type2(Key, Val, Map), + enter_type_list(Tail, Map1, U1++U0); +enter_type_list([], Map, U) -> + {Map, ordsets:from_list(U)}. + +enter_type2(Key, Val, Map) -> Map1 = enter_type(Key, Val, Map), - enter_type_list(Tail, Map1); -enter_type_list([], Map) -> - Map. + {Map1, [Key || not is_same(Key, Map, Map1)]}. + +map_store(Key, Val, Map) -> + ?debug("Storing ~w :: ~s\n", [Key, format_type(Val)]), + dict:store(Key, Val, Map). + +erase_type(Key, Map) -> + dict:erase(Key, Map). lookup_type_list(List, Map) -> [lookup_type(X, Map) || X <- List]. @@ -2079,22 +2671,41 @@ mk_var_no_lit(Var) -> mk_var_no_lit_list(List) -> [mk_var_no_lit(X) || X <- List]. +updated_vars_only(U, OldMap, NewMap) -> + [V || V <- U, not is_same(V, OldMap, NewMap)]. + +is_same(Key, Map1, Map2) -> + t_is_equal(lookup_type(Key, Map1), lookup_type(Key, Map2)). + +pp_map(_S, _Map) -> + ?debug("\t~s: ~p\n", + [_S, [{X, lists:flatten(format_type(Y))} || + {X, Y} <- lists:keysort(1, dict:to_list(_Map))]]). + %% ============================================================================ %% %% The State. %% %% ============================================================================ -new_state(SCC0, NextLabel, CallGraph, Plt, PropTypes) -> +new_state(SCC0, NextLabel, CallGraph, Plt, PropTypes, Solvers) -> List = [{MFA, Var} || {MFA, {Var, _Fun}, _Rec} <- SCC0], NameMap = dict:from_list(List), MFAs = [MFA || {MFA, _Var} <- List], SCC = [mk_var(Fun) || {_MFA, {_Var, Fun}, _Rec} <- SCC0], - SelfRecs = [F || F <- SCC, - dialyzer_callgraph:is_self_rec(t_var_name(F), CallGraph)], + SelfRec = + case SCC of + [OneF] -> + Label = t_var_name(OneF), + case dialyzer_callgraph:is_self_rec(Label, CallGraph) of + true -> OneF; + false -> false + end; + _Many -> false + end, #state{callgraph = CallGraph, name_map = NameMap, next_label = NextLabel, - prop_types = PropTypes, plt = Plt, scc = ordsets:from_list(SCC), - mfas = MFAs, self_recs = ordsets:from_list(SelfRecs)}. + prop_types = {d, PropTypes}, plt = Plt, scc = ordsets:from_list(SCC), + mfas = MFAs, self_rec = SelfRec, solvers = Solvers}. state__set_rec_dict(State, RecDict) -> State#state{records = RecDict}. @@ -2193,14 +2804,21 @@ state__plt(#state{plt = PLT}) -> state__new_constraint_context(State) -> State#state{cs = []}. -state__prop_domain(FunLabel, #state{prop_types = PropTypes}) -> +state__prop_domain(FunLabel, #state{prop_types = {e, ETSPropTypes}}) -> + try ets:lookup_element(ETSPropTypes, FunLabel, 2) of + {_Range_Fun, Dom} -> {ok, Dom}; + FunType -> {ok, t_fun_args(FunType)} + catch + _:_ -> error + end; +state__prop_domain(FunLabel, #state{prop_types = {d, PropTypes}}) -> case dict:find(FunLabel, PropTypes) of error -> error; {ok, {_Range_Fun, Dom}} -> {ok, Dom}; {ok, FunType} -> {ok, t_fun_args(FunType)} end. -state__add_prop_constrs(Tree, #state{prop_types = PropTypes} = State) -> +state__add_prop_constrs(Tree, #state{prop_types = {d, PropTypes}} = State) -> Label = cerl_trees:get_label(Tree), case dict:find(Label, PropTypes) of error -> State; @@ -2263,21 +2881,17 @@ state__mk_vars(N, #state{next_label = NL} = State) -> Vars = [t_var(X) || X <- lists:seq(NL, NewLabel-1)], {State#state{next_label = NewLabel}, Vars}. -state__store_constrs(Id, Cs, #state{cmap = Dict} = State) -> +state__store_constrs(Id, Cs, #state{cmap = {d, Dict}} = State) -> NewDict = dict:store(Id, Cs, Dict), - State#state{cmap = NewDict}. + State#state{cmap = {d, NewDict}}. -state__get_cs(Var, #state{cmap = Dict}) -> +state__get_cs(Var, #state{cmap = {e, ETSDict}}) -> + ets:lookup_element(ETSDict, Var, 2); +state__get_cs(Var, #state{cmap = {d, Dict}}) -> dict:fetch(Var, Dict). -%% The functions here will not be treated as self recursive. -%% These functions will need to be handled as such manually. -state__mark_as_non_self_rec(SCC, #state{self_recs = SelfRecs} = State) -> - %% TODO: Check if the result is always empty and just set it to [] if so. - State#state{self_recs = ordsets:subtract(SelfRecs, ordsets:from_list(SCC))}. - -state__is_self_rec(Fun, #state{self_recs = SelfRecs}) -> - ordsets:is_element(Fun, SelfRecs). +state__is_self_rec(Fun, #state{self_rec = SelfRec}) -> + Fun =:= SelfRec. state__store_funs(Vars0, Funs0, #state{fun_map = Map} = State) -> debug_make_name_map(Vars0, Funs0), @@ -2314,7 +2928,7 @@ mk_constraint(Lhs, Op, Rhs) -> case Deps =:= [] of true -> %% This constraint is constant. Solve it immediately. - case solve_one_c(C, dict:new(), []) of + case solve_one_c(C, map_new(), []) of error -> throw(error); _ -> %% This is always true, keep it anyway for logistic reasons @@ -2337,8 +2951,9 @@ constraint_opnd_is_any(Type) -> t_is_any(Type). -ifdef(DEBUG). --spec mk_fun_var(fun((_) -> erl_types:erl_type()), [erl_types:erl_type()], - integer()) -> #fun_var{}. +-spec mk_fun_var(integer(), + fun((_) -> erl_types:erl_type()), + [erl_types:erl_type()]) -> #fun_var{}. mk_fun_var(Line, Fun, Types) -> Deps = [t_var_name(Var) || Var <- t_collect_vars(t_product(Types))], @@ -2386,7 +3001,9 @@ mk_constraints([], _Op, []) -> []. mk_constraint_ref(Id, Deps) -> - #constraint_ref{id = Id, deps = Deps}. + %% See also solve_ref_or_list(), #constraint_ref{}. + Ds = ordsets:del_element(t_var_name(Id), Deps), + #constraint_ref{id = Id, deps = Ds}. mk_constraint_list(Type, List) -> List1 = ordsets:from_list(lift_lists(Type, List)), @@ -2523,19 +3140,21 @@ enumerate_constraints([#constraint_ref{id = Id} = C|Tail], N, Acc, State) -> enumerate_constraints([#constraint_list{type = conj, list = List} = C|Tail], N, Acc, State) -> %% Separate the flat constraints from the deep ones to make a - %% separate fixpoint interation over the flat ones for speed. - {Flat, Deep} = lists:splitwith(fun(#constraint{}) -> true; + %% separate fixpoint iteration over the flat ones for speed. + {Flat, Deep} = lists:partition(fun(#constraint{}) -> true; (#constraint_list{}) -> false; (#constraint_ref{}) -> false end, List), {NewFlat, N1, State1} = enumerate_constraints(Flat, N, [], State), {NewDeep, N2, State2} = enumerate_constraints(Deep, N1, [], State1), {NewList, N3} = - case shorter_than_two(NewFlat) orelse (NewDeep =:= []) of - true -> {NewFlat ++ NewDeep, N2}; - false -> - {NewCLists, TmpN} = group_constraints_in_components(NewFlat, N2), - {NewCLists ++ NewDeep, TmpN} + if + NewFlat =:= [] -> {NewDeep, N2}; + NewDeep =:= [] -> {NewFlat, N2}; + true -> + TmpCList = mk_conj_constraint_list(NewFlat), + {[TmpCList#constraint_list{id = {list, N2}}| NewDeep], + N2 + 1} end, NewAcc = [C#constraint_list{list = NewList, id = {list, N3}}|Acc], enumerate_constraints(Tail, N3+1, NewAcc, State2); @@ -2549,42 +3168,6 @@ enumerate_constraints([#constraint{} = C|Tail], N, Acc, State) -> enumerate_constraints([], N, Acc, State) -> {lists:reverse(Acc), N, State}. -shorter_than_two([]) -> true; -shorter_than_two([_]) -> true; -shorter_than_two([_|_]) -> false. - -group_constraints_in_components(Cs, N) -> - DepList = [Deps || #constraint{deps = Deps} <- Cs], - case find_dep_components(DepList, []) of - [_] -> {Cs, N}; - [_|_] = Components -> - ConstrComp = [[C || #constraint{deps = D} = C <- Cs, - ordsets:is_subset(D, Comp)] - || Comp <- Components], - lists:mapfoldl(fun(CComp, TmpN) -> - TmpCList = mk_conj_constraint_list(CComp), - {TmpCList#constraint_list{id = {list, TmpN}}, - TmpN + 1} - end, N, ConstrComp) - end. - -find_dep_components([Set|Left], AccComponents) -> - {Component, Ungrouped} = find_dep_components(Left, Set, []), - case Component =:= Set of - true -> find_dep_components(Ungrouped, [Component|AccComponents]); - false -> find_dep_components([Component|Ungrouped], AccComponents) - end; -find_dep_components([], AccComponents) -> - AccComponents. - -find_dep_components([Set|Left], AccSet, Ungrouped) -> - case ordsets:intersection(Set, AccSet) of - [] -> find_dep_components(Left, AccSet, [Set|Ungrouped]); - [_|_] -> find_dep_components(Left, ordsets:union(Set, AccSet), Ungrouped) - end; -find_dep_components([], AccSet, Ungrouped) -> - {AccSet, Ungrouped}. - %% Put the fun ref constraints last in any conjunction since we need %% to separate the environment from the interior of the function. order_fun_constraints(State) -> @@ -2615,7 +3198,9 @@ order_fun_constraints([#constraint_list{list = List, type = Type} = C|Tail], end, lists:mapfoldl(FoldFun, State, List) end, - NewAcc = [update_constraint_list(C, NewList)|Acc], + C1 = update_constraint_list(C, NewList), + Masks = calculate_masks(NewList, 1, []), + NewAcc = [update_masks(C1, Masks)|Acc], order_fun_constraints(Tail, Funs, NewAcc, NewState); order_fun_constraints([#constraint{} = C|Tail], Funs, Acc, State) -> order_fun_constraints(Tail, Funs, [C|Acc], State); @@ -2623,6 +3208,22 @@ order_fun_constraints([], Funs, Acc, State) -> NewState = order_fun_constraints(Funs, State), {lists:reverse(Acc)++Funs, NewState}. +update_masks(C, Masks) -> + C#constraint_list{masks = Masks}. + +-define(VARS_LIMIT, 50). + +calculate_masks([C|Cs], I, L0) -> + calculate_masks(Cs, I+1, [{V, I} || V <- get_deps(C)] ++ L0); +calculate_masks([], _I, L) -> + M = family(L), + case length(M) > ?VARS_LIMIT of + true -> + {d, dict:from_list(M)}; + false -> + M + end. + %% ============================================================================ %% %% Utilities. @@ -2700,6 +3301,9 @@ lookup_record(Records, Tag, Arity) -> error end. +family(L) -> + sofs:to_external(sofs:rel2fam(sofs:relation(L))). + %% ============================================================================ %% %% Pretty printer and debug facilities. @@ -2714,13 +3318,24 @@ lookup_record(Records, Tag, Arity) -> -ifdef(DEBUG). format_type(#fun_var{deps = Deps, origin = Origin}) -> - io_lib:format("Fun@L~p(~s)", - [Origin, lists:flatten([format_type(t_var(X))||X<-Deps])]); + L = [format_type(t_var(X)) || X <- Deps], + io_lib:format("Fun@L~p(~s)", [Origin, join_chars(L, ",")]); format_type(Type) -> case cerl:is_literal(Type) of true -> io_lib:format("~w", [cerl:concrete(Type)]); false -> erl_types:t_to_string(Type) end. + +join_chars([], _Sep) -> + []; +join_chars([H|T], Sep) -> + [H|[[Sep,X] || X <- T]]. + +debug_lookup_name(Var) -> + case dict:find(t_var_name(Var), get(dialyzer_typesig_map)) of + error -> Var; + {ok, Name} -> Name + end. -endif. -ifdef(DEBUG_NAME_MAP). @@ -2739,12 +3354,6 @@ debug_make_name_map([Var|VarLeft], [Fun|FunLeft], Map) -> debug_make_name_map([], [], Map) -> Map. -debug_lookup_name(Var) -> - case dict:find(t_var_name(Var), get(dialyzer_typesig_map)) of - error -> Var; - {ok, Name} -> Name - end. - -else. debug_make_name_map(_Vars, _Funs) -> ok. @@ -2755,51 +3364,55 @@ pp_constrs_scc(SCC, State) -> [pp_constrs(Fun, state__get_cs(Fun, State), State) || Fun <- SCC]. pp_constrs(Fun, Cs, State) -> - io:format("Constraints for fun: ~w\n", [debug_lookup_name(Fun)]), + io:format("Constraints for fun: ~w", [debug_lookup_name(Fun)]), MaxDepth = pp_constraints(Cs, State), io:format("Depth: ~w\n", [MaxDepth]). pp_constraints(Cs, State) -> - Res = pp_constraints([Cs], none, 0, 0, State), + Res = pp_constraints([Cs], 0, 0, State), io:nl(), Res. -pp_constraints([List|Tail], Separator, Level, MaxDepth, - State) when is_list(List) -> - pp_constraints(List++Tail, Separator, Level, MaxDepth, State); -pp_constraints([#constraint_ref{id = Id}|Left], Separator, - Level, MaxDepth, State) -> +pp_constraints([List|Tail], Level, MaxDepth, State) when is_list(List) -> + pp_constraints(List++Tail, Level, MaxDepth, State); +pp_constraints([#constraint_ref{id = Id}|Left], Level, MaxDepth, State) -> Cs = state__get_cs(Id, State), + pp_indent(Level), io:format("%Ref ~w%", [t_var_name(Id)]), - pp_constraints([Cs|Left], Separator, Level, MaxDepth, State); -pp_constraints([#constraint{lhs = Lhs, op = Op, rhs = Rhs}], _Separator, - Level, MaxDepth, _State) -> - io:format("~s ~w ~s", [format_type(Lhs), Op, format_type(Rhs)]), + pp_constraints([Cs|Left], Level, MaxDepth, State); +pp_constraints([#constraint{}=C], Level, MaxDepth, _State) -> + pp_op(C, Level), erlang:max(Level, MaxDepth); -pp_constraints([#constraint{lhs = Lhs, op = Op, rhs = Rhs}|Tail], Separator, - Level, MaxDepth, State) -> - io:format("~s ~w ~s ~s ", [format_type(Lhs), Op, format_type(Rhs),Separator]), - pp_constraints(Tail, Separator, Level, MaxDepth, State); +pp_constraints([#constraint{}=C|Tail], Level, MaxDepth, State) -> + pp_op(C, Level), + pp_constraints(Tail, Level, MaxDepth, State); pp_constraints([#constraint_list{type = Type, list = List, id = Id}], - _Separator, Level, MaxDepth, State) -> - io:format("%List ~w(", [Id]), - NewSeparator = case Type of - conj -> "*"; - disj -> "+" - end, - NewMaxDepth = pp_constraints(List, NewSeparator, Level + 1, MaxDepth, State), + Level, MaxDepth, State) -> + pp_indent(Level), + case Type of + conj -> io:format("Conj ~w (", [Id]); + disj -> io:format("Disj ~w (", [Id]) + end, + NewMaxDepth = pp_constraints(List, Level + 1, MaxDepth, State), io:format(")", []), NewMaxDepth; pp_constraints([#constraint_list{type = Type, list = List, id = Id}|Tail], - Separator, Level, MaxDepth, State) -> - io:format("List ~w(", [Id]), - NewSeparator = case Type of - conj -> "*"; - disj -> "+" - end, - NewMaxDepth = pp_constraints(List, NewSeparator, Level+1, MaxDepth, State), - io:format(") ~s\n~s ", [Separator, Separator]), - pp_constraints(Tail, Separator, Level, NewMaxDepth, State). + Level, MaxDepth, State) -> + pp_indent(Level), + case Type of + conj -> io:format("Conj ~w (", [Id]); + disj -> io:format("Disj ~w (", [Id]) + end, + NewMaxDepth = pp_constraints(List, Level+1, MaxDepth, State), + io:format(")", []), + pp_constraints(Tail, Level, NewMaxDepth, State). + +pp_op(#constraint{lhs = Lhs, op = Op, rhs = Rhs}, Level) -> + pp_indent(Level), + io:format("~s ~w ~s", [format_type(Lhs), Op, format_type(Rhs)]). + +pp_indent(Level) -> + io:format("\n~*s", [Level*2, ""]). -else. pp_constrs_scc(_SCC, _State) -> ok. |