From 5c1dd79d08e8725b408d11b17ceb99e80ec7cddb Mon Sep 17 00:00:00 2001 From: Kostis Sagonas Date: Sun, 7 Nov 2010 18:32:17 +0200 Subject: dialyzer: Speed up analysis of nested list comprehensions Nested list comprehensions are translated into strongly connected funs but dialyzer ignored this. This meant that self-recursive analysis was normally executed for each fun and the whole fixpoint took some time to calculate. This patch adds every fun found in constraint generation to the SCC that is under analysis and then solves the SCC as a whole. Possible issues: - The returned dict contains more entries than usual. This triggered a bug in contract checking that is dealt with is this patch as well (dialyzer_contracts.erl). - As it's not easy to tell apart real fun SCCs from simple funs it performance might be hampered in the simple funs case. While doing these changes, also added and strengthened some specs. In addition, incorporated a modified patch by Ahmed Omar that fixes a bug in dialyzer_analysis_callgraph module that kept the files of only one selected directory in dialyzer's GUI. --- lib/dialyzer/src/dialyzer.erl | 8 ++++- lib/dialyzer/src/dialyzer_analysis_callgraph.erl | 44 +++++++++++++----------- lib/dialyzer/src/dialyzer_cl.erl | 2 +- lib/dialyzer/src/dialyzer_contracts.erl | 29 +++++++++------- lib/dialyzer/src/dialyzer_typesig.erl | 19 ++++++---- 5 files changed, 60 insertions(+), 42 deletions(-) (limited to 'lib') diff --git a/lib/dialyzer/src/dialyzer.erl b/lib/dialyzer/src/dialyzer.erl index d8fd073ca6..895089846a 100644 --- a/lib/dialyzer/src/dialyzer.erl +++ b/lib/dialyzer/src/dialyzer.erl @@ -225,6 +225,8 @@ plt_info(Plt) -> %% Machinery %%----------- +-type doit_ret() :: {'ok', dial_ret()} | {'error', string()}. + doit(F) -> try {ok, F()} @@ -233,13 +235,17 @@ doit(F) -> {error, lists:flatten(Msg)} end. +-spec cl_error(string()) -> no_return(). + cl_error(Msg) -> cl_halt({error, Msg}, #options{}). +-spec gui_halt(doit_ret(), #options{}) -> no_return(). + gui_halt(R, Opts) -> cl_halt(R, Opts#options{report_mode = quiet}). --spec cl_halt({'ok',dial_ret()} | {'error',string()}, #options{}) -> no_return(). +-spec cl_halt(doit_ret(), #options{}) -> no_return(). cl_halt({ok, R = ?RET_NOTHING_SUSPICIOUS}, #options{report_mode = quiet}) -> halt(R); diff --git a/lib/dialyzer/src/dialyzer_analysis_callgraph.erl b/lib/dialyzer/src/dialyzer_analysis_callgraph.erl index 3438cc8c7e..abad1f3a75 100644 --- a/lib/dialyzer/src/dialyzer_analysis_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_analysis_callgraph.erl @@ -21,7 +21,7 @@ %%%------------------------------------------------------------------- %%% File : dialyzer_analysis_callgraph.erl %%% Author : Tobias Lindahl -%%% Description : +%%% Description : %%% %%% Created : 5 Apr 2005 by Tobias Lindahl %%%------------------------------------------------------------------- @@ -32,7 +32,7 @@ -include("dialyzer.hrl"). --record(analysis_state, +-record(analysis_state, { codeserver :: dialyzer_codeserver:codeserver(), analysis_type = succ_typings :: anal_type(), @@ -44,7 +44,7 @@ plt :: dialyzer_plt:plt(), start_from = byte_code :: start_from(), use_contracts = true :: boolean(), - behaviours = {false,[]} :: {boolean(),[atom()]} + behaviours = {false,[]} :: {boolean(),[atom()]} }). -record(server_state, {parent :: pid(), legal_warnings :: [dial_warn_tag()]}). @@ -83,10 +83,10 @@ loop(#server_state{parent = Parent, legal_warnings = LegalWarnings} = State, send_warnings(Parent, SendWarnings) end, loop(State, Analysis, ExtCalls); - {AnalPid, cserver, CServer, Plt} -> + {AnalPid, cserver, CServer, Plt} -> send_codeserver_plt(Parent, CServer, Plt), loop(State, Analysis, ExtCalls); - {AnalPid, done, Plt, DocPlt} -> + {AnalPid, done, Plt, DocPlt} -> case ExtCalls =:= none of true -> send_analysis_done(Parent, Plt, DocPlt); @@ -176,7 +176,7 @@ analysis_start(Parent, Analysis) -> NonExportsList = sets:to_list(NonExports), Plt3 = dialyzer_plt:delete_list(State3#analysis_state.plt, NonExportsList), Plt4 = dialyzer_plt:delete_contract_list(Plt3, NonExportsList), - send_codeserver_plt(Parent, CServer, State3#analysis_state.plt), + send_codeserver_plt(Parent, CServer, State3#analysis_state.plt), send_analysis_done(Parent, Plt4, State3#analysis_state.doc_plt). analyze_callgraph(Callgraph, State) -> @@ -229,24 +229,24 @@ compile_and_store(Files, #analysis_state{codeserver = CServer, {error, Reason} -> {TmpCG, TmpCServer, [{File, Reason}|TmpFailed], TmpNoWarn, TmpMods}; - {ok, NewCG, NoWarn, NewCServer, Mod} -> + {ok, NewCG, NoWarn, NewCServer, Mod} -> {NewCG, NewCServer, TmpFailed, NoWarn++TmpNoWarn, [Mod|TmpMods]} end end; byte_code -> - fun(File, {TmpCG, TmpCServer, TmpFailed, TmpNoWarn, TmpMods}) -> + fun(File, {TmpCG, TmpCServer, TmpFailed, TmpNoWarn, TmpMods}) -> case compile_byte(File, TmpCG, TmpCServer, UseContracts) of {error, Reason} -> {TmpCG, TmpCServer, [{File, Reason}|TmpFailed], TmpNoWarn, TmpMods}; - {ok, NewCG, NoWarn, NewCServer, Mod} -> + {ok, NewCG, NoWarn, NewCServer, Mod} -> {NewCG, NewCServer, TmpFailed, NoWarn++TmpNoWarn, [Mod|TmpMods]} end end end, - {NewCallgraph1, NewCServer, Failed, NoWarn, Modules} = + {NewCallgraph1, NewCServer, Failed, NoWarn, Modules} = lists:foldl(Fun, {Callgraph, CServer, [], [], []}, Files), case Failed =:= [] of true -> @@ -255,7 +255,7 @@ compile_and_store(Files, #analysis_state{codeserver = CServer, lists:foldl(fun({Mod, F}, Dict) -> dict:append(Mod, F, Dict) end, dict:new(), NewFiles), check_for_duplicate_modules(ModDict); - false -> + false -> Msg = io_lib:format("Could not scan the following file(s): ~p", [lists:flatten(Failed)]), exit({error, Msg}) @@ -268,14 +268,14 @@ compile_and_store(Files, #analysis_state{codeserver = CServer, if UnknownBehaviours =:= [] -> ok; true -> send_unknown_behaviours(Parent, UnknownBehaviours) end, - State1 = State#analysis_state{behaviours = {BehChk,KnownBehaviours}}, + State1 = State#analysis_state{behaviours = {BehChk, KnownBehaviours}}, NewCallgraph2 = cleanup_callgraph(State1, NewCServer, NewCallgraph1, Modules), {T3, _} = statistics(runtime), Msg2 = io_lib:format("done in ~.2f secs\n", [(T3-T2)/1000]), - send_log(Parent, Msg2), + send_log(Parent, Msg2), {NewCallgraph2, sets:from_list(NoWarn), NewCServer}. -cleanup_callgraph(#analysis_state{plt = InitPlt, parent = Parent, +cleanup_callgraph(#analysis_state{plt = InitPlt, parent = Parent, codeserver = CodeServer, behaviours = {BehChk, KnownBehaviours} }, @@ -298,9 +298,9 @@ cleanup_callgraph(#analysis_state{plt = InitPlt, parent = Parent, not dialyzer_plt:contains_mfa(InitPlt, To)], {BadCalls1, RealExtCalls} = if ExtCalls1 =:= [] -> {[], []}; - true -> + true -> ModuleSet = sets:from_list(Modules), - lists:partition(fun({_From, {M, _F, _A}}) -> + lists:partition(fun({_From, {M, _F, _A}}) -> sets:is_element(M, ModuleSet) orelse dialyzer_plt:contains_module(InitPlt, M) end, ExtCalls1) @@ -367,14 +367,14 @@ compile_byte(File, Callgraph, CServer, UseContracts) -> case dialyzer_utils:get_record_and_type_info(AbstrCode) of {error, _} = Error -> Error; {ok, RecInfo} -> - CServer1 = + CServer1 = dialyzer_codeserver:store_temp_records(Mod, RecInfo, CServer), case UseContracts of true -> case dialyzer_utils:get_spec_info(Mod, AbstrCode, RecInfo) of {error, _} = Error -> Error; {ok, SpecInfo} -> - CServer2 = + CServer2 = dialyzer_codeserver:store_temp_contracts(Mod, SpecInfo, CServer1), store_core(Mod, Core, NoWarn, Callgraph, CServer2) @@ -455,8 +455,12 @@ expand_files([File|Left], Ext, FileAcc) -> case filelib:is_dir(File) of true -> {ok, List} = file:list_dir(File), - NewFiles = - [filename:join(File, X) || X <- List, filename:extension(X) =:= Ext], + NewFiles = lists:foldl(fun (X, Acc) -> + case filename:extension(X) =:= Ext of + true -> [filename:join(File, X)|Acc]; + false -> Acc + end + end, FileAcc, List), expand_files(Left, Ext, NewFiles); false -> expand_files(Left, Ext, [File|FileAcc]) diff --git a/lib/dialyzer/src/dialyzer_cl.erl b/lib/dialyzer/src/dialyzer_cl.erl index 616e2465dc..0250c47ad0 100644 --- a/lib/dialyzer/src/dialyzer_cl.erl +++ b/lib/dialyzer/src/dialyzer_cl.erl @@ -559,7 +559,7 @@ cl_loop(State, LogCache) -> cl_loop(State, LogCache) end. --spec failed_anal_msg(string(), [_]) -> string(). +-spec failed_anal_msg(string(), [_]) -> nonempty_string(). failed_anal_msg(Reason, LogCache) -> Msg = "Analysis failed with error: " ++ Reason ++ "\n", diff --git a/lib/dialyzer/src/dialyzer_contracts.erl b/lib/dialyzer/src/dialyzer_contracts.erl index bf80c6f470..bcdcf2685d 100644 --- a/lib/dialyzer/src/dialyzer_contracts.erl +++ b/lib/dialyzer/src/dialyzer_contracts.erl @@ -163,20 +163,23 @@ process_contract_remote_types(CodeServer) -> check_contracts(Contracts, Callgraph, FunTypes) -> FoldFun = fun(Label, Type, NewContracts) -> - {ok, {M,F,A} = MFA} = dialyzer_callgraph:lookup_name(Label, Callgraph), - case orddict:find(MFA, Contracts) of - {ok, {_FileLine, Contract}} -> - case check_contract(Contract, Type) of - ok -> - case erl_bif_types:is_known(M, F, A) of - true -> - %% Disregard the contracts since - %% this is a known function. - NewContracts; - false -> - [{MFA, Contract}|NewContracts] + case dialyzer_callgraph:lookup_name(Label, Callgraph) of + {ok, {M,F,A} = MFA} -> + case orddict:find(MFA, Contracts) of + {ok, {_FileLine, Contract}} -> + case check_contract(Contract, Type) of + ok -> + case erl_bif_types:is_known(M, F, A) of + true -> + %% Disregard the contracts since + %% this is a known function. + NewContracts; + false -> + [{MFA, Contract}|NewContracts] + end; + {error, _Error} -> NewContracts end; - {error, _Error} -> NewContracts + error -> NewContracts end; error -> NewContracts end diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl index 3effb1c2e6..f68472d2fc 100644 --- a/lib/dialyzer/src/dialyzer_typesig.erl +++ b/lib/dialyzer/src/dialyzer_typesig.erl @@ -314,6 +314,7 @@ traverse(Tree, DefinedVars, State) -> error -> t_fun(length(Vars), t_none()); {ok, Dom} -> t_fun(Dom, t_none()) end, + TreeVar = mk_var(Tree), State2 = try State1 = case state__add_prop_constrs(Tree, State0) of @@ -321,20 +322,21 @@ traverse(Tree, DefinedVars, State) -> PropState -> PropState end, {BodyState, BodyVar} = traverse(Body, DefinedVars1, State1), - state__store_conj(mk_var(Tree), eq, + state__store_conj(TreeVar, eq, t_fun(mk_var_list(Vars), BodyVar), BodyState) catch throw:error -> - state__store_conj(mk_var(Tree), eq, FunFailType, State0) + state__store_conj(TreeVar, eq, FunFailType, State0) end, Cs = state__cs(State2), - State3 = state__store_constrs(mk_var(Tree), Cs, State2), - Ref = mk_constraint_ref(mk_var(Tree), get_deps(Cs)), + State3 = state__store_constrs(TreeVar, Cs, State2), + Ref = mk_constraint_ref(TreeVar, get_deps(Cs)), OldCs = state__cs(State), State4 = state__new_constraint_context(State3), State5 = state__store_conj_list([OldCs, Ref], State4), State6 = state__store_fun_arity(Tree, State5), - {State6, mk_var(Tree)}; + State7 = state__add_fun_to_scc(TreeVar, State6), + {State7, TreeVar}; 'let' -> Vars = cerl:let_vars(Tree), Arg = cerl:let_arg(Tree), @@ -580,7 +582,7 @@ handle_try(Tree, DefinedVars, State) -> mk_conj_constraint_list([HandlerCs, mk_constraint(TreeVar, eq, HandlerVar)]), Disj = mk_disj_constraint_list([Conj1, Conj2]), - {Disj, mk_var(Tree)}; + {Disj, TreeVar}; {false, true} -> {mk_conj_constraint_list([ArgBodyCs, mk_constraint(TreeVar, eq, BodyVar)]), @@ -2070,7 +2072,7 @@ new_state(SCC0, NextLabel, CallGraph, Plt, PropTypes) -> NameMap = dict:from_list([{MFA, Var} || {MFA, {Var, _Fun}, _Rec} <- SCC0]), SCC = [mk_var(Fun) || {_MFA, {_Var, Fun}, _Rec} <- SCC0], #state{callgraph = CallGraph, name_map = NameMap, next_label = NextLabel, - prop_types = PropTypes, plt = Plt, scc = SCC}. + prop_types = PropTypes, plt = Plt, scc = ordsets:from_list(SCC)}. state__set_rec_dict(State, RecDict) -> State#state{records = RecDict}. @@ -2161,6 +2163,9 @@ get_apply_constr(FunLabels, Dst, ArgTypes, #state{callgraph = CG} = State) -> state__scc(#state{scc = SCC}) -> SCC. +state__add_fun_to_scc(Fun, #state{scc = SCC} = State) -> + State#state{scc = ordsets:add_element(Fun, SCC)}. + state__plt(#state{plt = PLT}) -> PLT. -- cgit v1.2.3