diff options
Diffstat (limited to 'lib/dialyzer')
27 files changed, 2833 insertions, 1302 deletions
diff --git a/lib/dialyzer/doc/src/Makefile b/lib/dialyzer/doc/src/Makefile index 45b0ffa5ff..a827281cc5 100644 --- a/lib/dialyzer/doc/src/Makefile +++ b/lib/dialyzer/doc/src/Makefile @@ -100,13 +100,13 @@ clean clean_docs: include $(ERL_TOP)/make/otp_release_targets.mk release_docs_spec: docs - $(INSTALL_DIR) $(RELSYSDIR)/doc/pdf - $(INSTALL_DATA) $(TOP_PDF_FILE) $(RELSYSDIR)/doc/pdf - $(INSTALL_DIR) $(RELSYSDIR)/doc/html + $(INSTALL_DIR) "$(RELSYSDIR)/doc/pdf" + $(INSTALL_DATA) $(TOP_PDF_FILE) "$(RELSYSDIR)/doc/pdf" + $(INSTALL_DIR) "$(RELSYSDIR)/doc/html" $(INSTALL_DATA) $(HTMLDIR)/* \ - $(RELSYSDIR)/doc/html - $(INSTALL_DATA) $(INFO_FILE) $(RELSYSDIR) - $(INSTALL_DIR) $(RELEASE_PATH)/man/man3 - $(INSTALL_DATA) $(MAN3DIR)/* $(RELEASE_PATH)/man/man3 + "$(RELSYSDIR)/doc/html" + $(INSTALL_DATA) $(INFO_FILE) "$(RELSYSDIR)" + $(INSTALL_DIR) "$(RELEASE_PATH)/man/man3" + $(INSTALL_DATA) $(MAN3DIR)/* "$(RELEASE_PATH)/man/man3" release_spec: diff --git a/lib/dialyzer/src/Makefile b/lib/dialyzer/src/Makefile index 04f3b844c4..63cc1c98f1 100644 --- a/lib/dialyzer/src/Makefile +++ b/lib/dialyzer/src/Makefile @@ -63,7 +63,10 @@ MODULES = \ dialyzer_plt \ dialyzer_races \ dialyzer_succ_typings \ + dialyzer_timing \ dialyzer_typesig \ + dialyzer_coordinator \ + dialyzer_worker \ dialyzer_utils HRL_FILES= dialyzer.hrl dialyzer_gui_wx.hrl @@ -152,10 +155,10 @@ $(EBIN)/dialyzer_utils.beam: dialyzer.hrl include $(ERL_TOP)/make/otp_release_targets.mk release_spec: opt - $(INSTALL_DIR) $(RELSYSDIR)/src + $(INSTALL_DIR) "$(RELSYSDIR)/src" $(INSTALL_DATA) $(ERL_FILES) $(HRL_FILES) $(EXTRA_FILES) \ - $(RELSYSDIR)/src - $(INSTALL_DIR) $(RELSYSDIR)/ebin - $(INSTALL_DATA) $(INSTALL_FILES) $(RELSYSDIR)/ebin + "$(RELSYSDIR)/src" + $(INSTALL_DIR) "$(RELSYSDIR)/ebin" + $(INSTALL_DATA) $(INSTALL_FILES) "$(RELSYSDIR)/ebin" release_docs_spec: diff --git a/lib/dialyzer/src/dialyzer.hrl b/lib/dialyzer/src/dialyzer.hrl index 5e089d1773..105a174e31 100644 --- a/lib/dialyzer/src/dialyzer.hrl +++ b/lib/dialyzer/src/dialyzer.hrl @@ -2,7 +2,7 @@ %%% %%% %CopyrightBegin% %%% -%%% Copyright Ericsson AB 2006-2011. All Rights Reserved. +%%% Copyright Ericsson AB 2006-2012. All Rights Reserved. %%% %%% The contents of this file are subject to the Erlang Public License, %%% Version 1.1, (the "License"); you may not use this file except in @@ -110,6 +110,8 @@ -type label() :: non_neg_integer(). -type rep_mode() :: 'quiet' | 'normal' | 'verbose'. -type start_from() :: 'byte_code' | 'src_code'. +-type mfa_or_funlbl() :: label() | mfa(). +-type solver() :: 'v1' | 'v2'. %%-------------------------------------------------------------------- %% Record declarations used by various files @@ -126,11 +128,15 @@ use_contracts = true :: boolean(), race_detection = false :: boolean(), behaviours_chk = false :: boolean(), - callgraph_file = "" :: file:filename()}). + timing = false :: boolean() | 'debug', + timing_server :: dialyzer_timing:timing_server(), + callgraph_file = "" :: file:filename(), + solvers :: [solver()]}). -record(options, {files = [] :: [file:filename()], files_rec = [] :: [file:filename()], analysis_type = succ_typings :: anal_type1(), + timing = false :: boolean() | 'debug', defines = [] :: [dial_define()], from = byte_code :: start_from(), get_warnings = maybe :: boolean() | 'maybe', @@ -145,10 +151,20 @@ output_format = formatted :: format(), filename_opt = basename :: fopt(), callgraph_file = "" :: file:filename(), - check_plt = true :: boolean()}). + check_plt = true :: boolean(), + solvers = [] :: [solver()]}). -record(contract, {contracts = [] :: [contract_pair()], args = [] :: [erl_types:erl_type()], forms = [] :: [{_, _}]}). %%-------------------------------------------------------------------- + +-define(timing(Server, Msg, Var, Expr), + begin + dialyzer_timing:start_stamp(Server, Msg), + Var = Expr, + dialyzer_timing:end_stamp(Server), + Var + end). +-define(timing(Server, Msg, Expr),?timing(Server, Msg, _T, Expr)). diff --git a/lib/dialyzer/src/dialyzer_analysis_callgraph.erl b/lib/dialyzer/src/dialyzer_analysis_callgraph.erl index 2c4622155a..496d317f8a 100644 --- a/lib/dialyzer/src/dialyzer_analysis_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_analysis_callgraph.erl @@ -30,6 +30,15 @@ -export([start/3]). +-export([compile_init_result/0, + add_to_result/4, + start_compilation/2, + continue_compilation/2]). + +-export_type([compile_init_data/0, + one_file_result/0, + compile_result/0]). + -include("dialyzer.hrl"). -record(analysis_state, @@ -43,7 +52,9 @@ parent :: pid(), plt :: dialyzer_plt:plt(), start_from = byte_code :: start_from(), - use_contracts = true :: boolean() + use_contracts = true :: boolean(), + timing_server :: dialyzer_timing:timing_server(), + solvers :: [solver()] }). -record(server_state, {parent :: pid(), legal_warnings :: [dial_warn_tag()]}). @@ -55,12 +66,15 @@ -spec start(pid(), [dial_warn_tag()], #analysis{}) -> 'ok'. start(Parent, LegalWarnings, Analysis) -> + TimingServer = dialyzer_timing:init(Analysis#analysis.timing), RacesOn = ordsets:is_element(?WARN_RACE_CONDITION, LegalWarnings), - Analysis0 = Analysis#analysis{race_detection = RacesOn}, + Analysis0 = + Analysis#analysis{race_detection = RacesOn, timing_server = TimingServer}, Analysis1 = expand_files(Analysis0), Analysis2 = run_analysis(Analysis1), State = #server_state{parent = Parent, legal_warnings = LegalWarnings}, - loop(State, Analysis2, none). + loop(State, Analysis2, none), + dialyzer_timing:stop(TimingServer). run_analysis(Analysis) -> Self = self(), @@ -122,7 +136,9 @@ analysis_start(Parent, Analysis) -> plt = Plt, parent = Parent, start_from = Analysis#analysis.start_from, - use_contracts = Analysis#analysis.use_contracts + use_contracts = Analysis#analysis.use_contracts, + timing_server = Analysis#analysis.timing_server, + solvers = Analysis#analysis.solvers }, Files = ordsets:from_list(Analysis#analysis.files), {Callgraph, NoWarn, TmpCServer0} = compile_and_store(Files, State), @@ -146,7 +162,8 @@ analysis_start(Parent, Analysis) -> dialyzer_codeserver:insert_temp_exported_types(MergedExpTypes, TmpCServer1), TmpCServer3 = dialyzer_utils:process_record_remote_types(TmpCServer2), - dialyzer_contracts:process_contract_remote_types(TmpCServer3) + ?timing(State#analysis_state.timing_server, "remote", + dialyzer_contracts:process_contract_remote_types(TmpCServer3)) catch throw:{error, _ErrorMsg} = Error -> exit(Error) end, @@ -174,72 +191,67 @@ analysis_start(Parent, Analysis) -> send_codeserver_plt(Parent, CServer, State3#analysis_state.plt), send_analysis_done(Parent, Plt2, State3#analysis_state.doc_plt). -analyze_callgraph(Callgraph, State) -> - Codeserver = State#analysis_state.codeserver, - Parent = State#analysis_state.parent, - DocPlt = State#analysis_state.doc_plt, +analyze_callgraph(Callgraph, #analysis_state{codeserver = Codeserver, + doc_plt = DocPlt, + timing_server = TimingServer, + parent = Parent, + solvers = Solvers} = State) -> Plt = dialyzer_plt:insert_callbacks(State#analysis_state.plt, Codeserver), - Callgraph1 = dialyzer_callgraph:finalize(Callgraph), {NewPlt, NewDocPlt} = case State#analysis_state.analysis_type of plt_build -> - {dialyzer_succ_typings:analyze_callgraph(Callgraph1, Plt, - Codeserver, Parent), - DocPlt}; + NewPlt0 = + dialyzer_succ_typings:analyze_callgraph(Callgraph, Plt, Codeserver, + TimingServer, Solvers, Parent), + {NewPlt0, DocPlt}; succ_typings -> NoWarn = State#analysis_state.no_warn_unused, {Warnings, NewPlt0, NewDocPlt0} = - dialyzer_succ_typings:get_warnings(Callgraph1, Plt, DocPlt, - Codeserver, NoWarn, Parent), + dialyzer_succ_typings:get_warnings(Callgraph, Plt, DocPlt, Codeserver, + NoWarn, TimingServer, Solvers, Parent), send_warnings(State#analysis_state.parent, Warnings), {NewPlt0, NewDocPlt0} end, - dialyzer_callgraph:delete(Callgraph1), + dialyzer_callgraph:delete(Callgraph), State#analysis_state{plt = NewPlt, doc_plt = NewDocPlt}. %%-------------------------------------------------------------------- %% Build the callgraph and fill the codeserver. %%-------------------------------------------------------------------- +-record(compile_init,{ + callgraph :: dialyzer_callgraph:callgraph(), + codeserver :: dialyzer_codeserver:codeserver(), + defines = [] :: [dial_define()], + include_dirs = [] :: [file:filename()], + start_from = byte_code :: start_from(), + use_contracts = true :: boolean() + }). + +make_compile_init(#analysis_state{codeserver = Codeserver, + defines = Defs, + include_dirs = Dirs, + use_contracts = UseContracts, + start_from = StartFrom}, Callgraph) -> + #compile_init{callgraph = Callgraph, + codeserver = Codeserver, + defines = [{d, Macro, Val} || {Macro, Val} <- Defs], + include_dirs = [{i, D} || D <- Dirs], + use_contracts = UseContracts, + start_from = StartFrom}. + compile_and_store(Files, #analysis_state{codeserver = CServer, - defines = Defs, - include_dirs = Dirs, - parent = Parent, - use_contracts = UseContracts, - start_from = StartFrom - } = State) -> + timing_server = Timing, + parent = Parent} = State) -> send_log(Parent, "Reading files and computing callgraph... "), {T1, _} = statistics(runtime), - Includes = [{i, D} || D <- Dirs], - Defines = [{d, Macro, Val} || {Macro, Val} <- Defs], Callgraph = dialyzer_callgraph:new(), - Fun = case StartFrom of - src_code -> - fun(File, {TmpCG, TmpCServer, TmpFailed, TmpNoWarn, TmpMods}) -> - case compile_src(File, Includes, Defines, TmpCG, - TmpCServer, UseContracts) of - {error, Reason} -> - {TmpCG, TmpCServer, [{File, Reason}|TmpFailed], TmpNoWarn, - TmpMods}; - {ok, NewCG, NoWarn, NewCServer, Mod} -> - {NewCG, NewCServer, TmpFailed, NoWarn++TmpNoWarn, - [Mod|TmpMods]} - end - end; - byte_code -> - 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} -> - {NewCG, NewCServer, TmpFailed, NoWarn++TmpNoWarn, - [Mod|TmpMods]} - end - end - end, - {NewCallgraph1, NewCServer, Failed, NoWarn, Modules} = - lists:foldl(Fun, {Callgraph, CServer, [], [], []}, Files), + CompileInit = make_compile_init(State, Callgraph), + {{Failed, NoWarn, Modules}, NextLabel} = + ?timing(Timing, "compile", _C1, + dialyzer_coordinator:parallel_job(compile, Files, + CompileInit, Timing)), + CServer2 = dialyzer_codeserver:set_next_core_label(NextLabel, CServer), case Failed =:= [] of true -> NewFiles = lists:zip(lists:reverse(Modules), Files), @@ -255,11 +267,56 @@ compile_and_store(Files, #analysis_state{codeserver = CServer, {T2, _} = statistics(runtime), Msg1 = io_lib:format("done in ~.2f secs\nRemoving edges... ", [(T2-T1)/1000]), send_log(Parent, Msg1), - NewCallgraph2 = cleanup_callgraph(State, NewCServer, NewCallgraph1, Modules), + Callgraph = + ?timing(Timing, "clean", _C2, + cleanup_callgraph(State, CServer2, Callgraph, Modules)), {T3, _} = statistics(runtime), Msg2 = io_lib:format("done in ~.2f secs\n", [(T3-T2)/1000]), send_log(Parent, Msg2), - {NewCallgraph2, sets:from_list(NoWarn), NewCServer}. + {Callgraph, sets:from_list(NoWarn), CServer2}. + +-type compile_init_data() :: #compile_init{}. +-type error_reason() :: string(). +-type compile_result() :: {[{file:filename(), error_reason()}], [mfa()], + [module()]}. %%opaque +-type one_file_result() :: {error, error_reason()} | + {ok, [dialyzer_callgraph:callgraph_edge()], + [mfa_or_funlbl()], [mfa()], module()}. %%opaque +-type compile_mid_data() :: {module(), cerl:cerl(), [mfa()], + dialyzer_callgraph:callgraph(), + dialyzer_codeserver:codeserver()}. + +-spec compile_init_result() -> compile_result(). + +compile_init_result() -> {[], [], []}. + +-spec add_to_result(file:filename(), one_file_result(), compile_result(), + compile_init_data()) -> compile_result(). + +add_to_result(File, NewData, {Failed, NoWarn, Mods}, InitData) -> + case NewData of + {error, Reason} -> + {[{File, Reason}|Failed], NoWarn, Mods}; + {ok, V, E, NewNoWarn, Mod} -> + Callgraph = InitData#compile_init.callgraph, + dialyzer_callgraph:add_edges(E, V, Callgraph), + {Failed, NewNoWarn ++ NoWarn, [Mod|Mods]} + end. + +-spec start_compilation(file:filename(), compile_init_data()) -> + {error, error_reason()} |{ok, integer(), compile_mid_data()}. + +start_compilation(File, + #compile_init{callgraph = Callgraph, codeserver = Codeserver, + defines = Defines, include_dirs = IncludeD, + use_contracts = UseContracts, + start_from = StartFrom}) -> + case StartFrom of + src_code -> + compile_src(File, IncludeD, Defines, Callgraph, Codeserver, UseContracts); + byte_code -> + compile_byte(File, Callgraph, Codeserver, UseContracts) + end. cleanup_callgraph(#analysis_state{plt = InitPlt, parent = Parent, codeserver = CodeServer @@ -348,14 +405,18 @@ compile_common(File, AbstrCode, CompOpts, Callgraph, CServer, UseContracts) -> store_core(Mod, Core, NoWarn, Callgraph, CServer) -> Exp = get_exports_from_core(Core), - OldExpTypes = dialyzer_codeserver:get_temp_exported_types(CServer), - NewExpTypes = get_exported_types_from_core(Core), - MergedExpTypes = sets:union(NewExpTypes, OldExpTypes), - CServer1 = dialyzer_codeserver:insert_exports(Exp, CServer), - CServer2 = dialyzer_codeserver:insert_temp_exported_types(MergedExpTypes, - CServer1), - {LabeledCore, CServer3} = label_core(Core, CServer2), - store_code_and_build_callgraph(Mod, LabeledCore, Callgraph, CServer3, NoWarn). + ExpTypes = get_exported_types_from_core(Core), + CServer = dialyzer_codeserver:insert_exports(Exp, CServer), + CServer = dialyzer_codeserver:insert_temp_exported_types(ExpTypes, CServer), + CoreTree = cerl:from_records(Core), + {ok, cerl_trees:size(CoreTree), {Mod, CoreTree, NoWarn, Callgraph, CServer}}. + +-spec continue_compilation(integer(), compile_mid_data()) -> one_file_result(). + +continue_compilation(NextLabel, {Mod, CoreTree, NoWarn, Callgraph, CServer}) -> + {LabeledTree, _NewNextLabel} = cerl_trees:label(CoreTree, NextLabel), + LabeledCore = cerl:to_records(LabeledTree), + store_code_and_build_callgraph(Mod, LabeledCore, Callgraph, NoWarn, CServer). abs_get_nowarn(Abs, M) -> Opts = lists:flatten([C || {attribute, _, compile, C} <- Abs]), @@ -388,18 +449,11 @@ get_exports_from_core(Core) -> M = cerl:atom_val(cerl:module_name(Tree)), [{M, F, A} || {F, A} <- Exports2]. -label_core(Core, CServer) -> - NextLabel = dialyzer_codeserver:get_next_core_label(CServer), - CoreTree = cerl:from_records(Core), - {LabeledTree, NewNextLabel} = cerl_trees:label(CoreTree, NextLabel), - {cerl:to_records(LabeledTree), - dialyzer_codeserver:set_next_core_label(NewNextLabel, CServer)}. - -store_code_and_build_callgraph(Mod, Core, Callgraph, CServer, NoWarn) -> +store_code_and_build_callgraph(Mod, Core, Callgraph, NoWarn, CServer) -> CoreTree = cerl:from_records(Core), - NewCallgraph = dialyzer_callgraph:scan_core_tree(CoreTree, Callgraph), - CServer2 = dialyzer_codeserver:insert(Mod, CoreTree, CServer), - {ok, NewCallgraph, NoWarn, CServer2, Mod}. + {Vertices, Edges} = dialyzer_callgraph:scan_core_tree(CoreTree, Callgraph), + CServer = dialyzer_codeserver:insert(Mod, CoreTree, CServer), + {ok, Vertices, Edges, NoWarn, Mod}. %%-------------------------------------------------------------------- %% Utilities diff --git a/lib/dialyzer/src/dialyzer_behaviours.erl b/lib/dialyzer/src/dialyzer_behaviours.erl index 127e906135..b84071b95c 100644 --- a/lib/dialyzer/src/dialyzer_behaviours.erl +++ b/lib/dialyzer/src/dialyzer_behaviours.erl @@ -30,7 +30,7 @@ -module(dialyzer_behaviours). --export([check_callbacks/4, get_behaviour_apis/1, +-export([check_callbacks/5, get_behaviour_apis/1, translate_behaviour_api_call/5, translatable_behaviours/1, translate_callgraph/3]). @@ -47,15 +47,16 @@ -record(state, {plt :: dialyzer_plt:plt(), codeserver :: dialyzer_codeserver:codeserver(), filename :: file:filename(), - behlines :: [{behaviour(), non_neg_integer()}]}). + behlines :: [{behaviour(), non_neg_integer()}], + records :: dict()}). %%-------------------------------------------------------------------- --spec check_callbacks(module(), [{cerl:cerl(), cerl:cerl()}], +-spec check_callbacks(module(), [{cerl:cerl(), cerl:cerl()}], dict(), dialyzer_plt:plt(), dialyzer_codeserver:codeserver()) -> [dial_warning()]. -check_callbacks(Module, Attrs, Plt, Codeserver) -> +check_callbacks(Module, Attrs, Records, Plt, Codeserver) -> {Behaviours, BehLines} = get_behaviours(Attrs), case Behaviours of [] -> []; @@ -64,7 +65,7 @@ check_callbacks(Module, Attrs, Plt, Codeserver) -> {_Var,Code} = dialyzer_codeserver:lookup_mfa_code(MFA, Codeserver), File = get_file(cerl:get_ann(Code)), State = #state{plt = Plt, filename = File, behlines = BehLines, - codeserver = Codeserver}, + codeserver = Codeserver, records = Records}, Warnings = get_warnings(Module, Behaviours, State), [add_tag_file_line(Module, W, State) || W <- Warnings] end. @@ -92,24 +93,21 @@ get_warnings(Module, [Behaviour|Rest], State, Acc) -> check_behaviour(Module, Behaviour, #state{plt = Plt} = State, Acc) -> case dialyzer_plt:lookup_callbacks(Plt, Behaviour) of - [] -> [{callback_info_missing, [Behaviour]}|Acc]; - Callbacks -> check_all_callbacks(Module, Behaviour, Callbacks, State, Acc) + none -> [{callback_info_missing, [Behaviour]}|Acc]; + {value, Callbacks} -> + check_all_callbacks(Module, Behaviour, Callbacks, State, Acc) end. check_all_callbacks(_Module, _Behaviour, [], _State, Acc) -> Acc; check_all_callbacks(Module, Behaviour, [Cb|Rest], - #state{plt = Plt, codeserver = Codeserver} = State, Acc) -> + #state{plt = Plt, codeserver = Codeserver, + records = Records} = State, Acc) -> {{Behaviour, Function, Arity}, {{_BehFile, _BehLine}, Callback}} = Cb, CbMFA = {Module, Function, Arity}, CbReturnType = dialyzer_contracts:get_contract_return(Callback), CbArgTypes = dialyzer_contracts:get_contract_args(Callback), - Records = - case dict:find(Module, dialyzer_codeserver:get_records(Codeserver)) of - {ok, V} -> V; - error -> dict:new() - end, Acc0 = Acc, Acc1 = case dialyzer_plt:lookup(Plt, CbMFA) of @@ -282,8 +280,8 @@ translate_callgraph([{Behaviour,_}|Behaviours], Module, Callgraph) -> DirectCalls = [{From, {Module, Fun, Arity}} || {From, To} <- UsedCalls,{API, {Fun, Arity, _Ord}} <- Calls, To =:= API], - NewCallgraph = dialyzer_callgraph:add_edges(DirectCalls, Callgraph), - translate_callgraph(Behaviours, Module, NewCallgraph); + dialyzer_callgraph:add_edges(DirectCalls, Callgraph), + translate_callgraph(Behaviours, Module, Callgraph); translate_callgraph([], _Module, Callgraph) -> Callgraph. diff --git a/lib/dialyzer/src/dialyzer_callgraph.erl b/lib/dialyzer/src/dialyzer_callgraph.erl index effd619bde..64e0ee88af 100644 --- a/lib/dialyzer/src/dialyzer_callgraph.erl +++ b/lib/dialyzer/src/dialyzer_callgraph.erl @@ -28,6 +28,7 @@ -module(dialyzer_callgraph). -export([add_edges/2, + add_edges/3, all_nodes/1, delete/1, finalize/1, @@ -43,12 +44,15 @@ %% module_postorder/1, module_postorder_from_funs/2, new/0, + get_depends_on/2, + get_required_by/2, in_neighbours/2, renew_race_info/4, + renew_race_code/2, + renew_race_public_tables/2, reset_from_funs/2, scan_core_tree/2, strip_module_deps/2, - take_scc/1, remove_external/1, to_dot/2, to_ps/3]). @@ -57,15 +61,14 @@ get_race_code/1, get_race_detection/1, race_code_new/1, put_digraph/2, put_race_code/2, put_race_detection/2, put_named_tables/2, put_public_tables/2, put_behaviour_api_calls/2, - get_behaviour_api_calls/1]). + get_behaviour_api_calls/1, dispose_race_server/1, duplicate/1]). --export_type([callgraph/0, mfa_or_funlbl/0]). +-export_type([callgraph/0, mfa_or_funlbl/0, callgraph_edge/0]). -include("dialyzer.hrl"). %%---------------------------------------------------------------------- --type mfa_or_funlbl() :: label() | mfa(). -type scc() :: [mfa_or_funlbl()]. -type mfa_calls() :: [{mfa_or_funlbl(), mfa_or_funlbl()}]. @@ -78,9 +81,6 @@ %% digraph - A digraph representing the callgraph. %% Nodes are represented as MFAs or labels. %% esc - A set of all escaping functions as reported by dialyzer_dep. -%% postorder - A list of strongly connected components of the callgraph -%% sorted in a topological bottom-up order. -%% This is produced by calling finalize/1. %% name_map - A mapping from label to MFA. %% rev_name_map - A reverse mapping of the name_map. %% rec_var_map - A dict mapping from letrec bound labels to function names. @@ -91,29 +91,42 @@ %%----------------------------------------------------------------------------- -record(callgraph, {digraph = digraph:new() :: digraph(), - esc = sets:new() :: set(), - name_map = dict:new() :: dict(), - rev_name_map = dict:new() :: dict(), - postorder = [] :: [scc()], - rec_var_map = dict:new() :: dict(), - self_rec = sets:new() :: set(), - calls = dict:new() :: dict(), - race_code = dict:new() :: dict(), - public_tables = [] :: [label()], - named_tables = [] :: [string()], + active_digraph :: active_digraph(), + esc :: ets:tid(), + name_map :: ets:tid(), + rev_name_map :: ets:tid(), + rec_var_map :: ets:tid(), + self_rec :: ets:tid(), + calls :: ets:tid(), race_detection = false :: boolean(), - beh_api_calls = [] :: [{mfa(), mfa()}]}). + race_data_server = new_race_data_server() :: pid()}). + +-record(race_data_state, {race_code = dict:new() :: dict(), + public_tables = [] :: [label()], + named_tables = [] :: [string()], + beh_api_calls = [] :: [{mfa(), mfa()}]}). %% Exported Types -type callgraph() :: #callgraph{}. +-type active_digraph() :: {'d', digraph()} | {'e', ets:tid(), ets:tid()}. + %%---------------------------------------------------------------------- -spec new() -> callgraph(). new() -> - #callgraph{}. + [ETSEsc, ETSNameMap, ETSRevNameMap, ETSRecVarMap, ETSSelfRec, ETSCalls] = + [ets:new(N,[public, {read_concurrency, true}]) || + N <- [callgraph_esc, callgraph_name_map, callgraph_rev_name_map, + callgraph_rec_var_map, callgraph_self_rec, callgraph_calls]], + #callgraph{esc = ETSEsc, + name_map = ETSNameMap, + rev_name_map = ETSRevNameMap, + rec_var_map = ETSRecVarMap, + self_rec = ETSSelfRec, + calls = ETSCalls}. -spec delete(callgraph()) -> 'true'. @@ -129,32 +142,32 @@ all_nodes(#callgraph{digraph = DG}) -> lookup_rec_var(Label, #callgraph{rec_var_map = RecVarMap}) when is_integer(Label) -> - dict:find(Label, RecVarMap). + ets_lookup_dict(Label, RecVarMap). -spec lookup_call_site(label(), callgraph()) -> 'error' | {'ok', [_]}. % XXX: refine lookup_call_site(Label, #callgraph{calls = Calls}) when is_integer(Label) -> - dict:find(Label, Calls). + ets_lookup_dict(Label, Calls). -spec lookup_name(label(), callgraph()) -> 'error' | {'ok', mfa()}. lookup_name(Label, #callgraph{name_map = NameMap}) when is_integer(Label) -> - dict:find(Label, NameMap). + ets_lookup_dict(Label, NameMap). -spec lookup_label(mfa_or_funlbl(), callgraph()) -> 'error' | {'ok', integer()}. lookup_label({_,_,_} = MFA, #callgraph{rev_name_map = RevNameMap}) -> - dict:find(MFA, RevNameMap); + ets_lookup_dict(MFA, RevNameMap); lookup_label(Label, #callgraph{}) when is_integer(Label) -> {ok, Label}. -spec in_neighbours(mfa_or_funlbl(), callgraph()) -> 'none' | [mfa_or_funlbl(),...]. -in_neighbours(Label, #callgraph{digraph = Digraph, name_map = NameMap}) +in_neighbours(Label, #callgraph{digraph = Digraph} = CG) when is_integer(Label) -> - Name = case dict:find(Label, NameMap) of + Name = case lookup_name(Label, CG) of {ok, Val} -> Val; error -> Label end, @@ -165,34 +178,27 @@ in_neighbours({_, _, _} = MFA, #callgraph{digraph = Digraph}) -> -spec is_self_rec(mfa_or_funlbl(), callgraph()) -> boolean(). is_self_rec(MfaOrLabel, #callgraph{self_rec = SelfRecs}) -> - sets:is_element(MfaOrLabel, SelfRecs). + ets_lookup_set(MfaOrLabel, SelfRecs). -spec is_escaping(label(), callgraph()) -> boolean(). is_escaping(Label, #callgraph{esc = Esc}) when is_integer(Label) -> - sets:is_element(Label, Esc). + ets_lookup_set(Label, Esc). -type callgraph_edge() :: {mfa_or_funlbl(),mfa_or_funlbl()}. --spec add_edges([callgraph_edge()], callgraph()) -> callgraph(). +-spec add_edges([callgraph_edge()], callgraph()) -> ok. -add_edges([], CG) -> - CG; -add_edges(Edges, #callgraph{digraph = Digraph} = CG) -> - CG#callgraph{digraph = digraph_add_edges(Edges, Digraph)}. +add_edges([], _CG) -> + ok; +add_edges(Edges, #callgraph{digraph = Digraph}) -> + digraph_add_edges(Edges, Digraph). --spec add_edges([callgraph_edge()], [mfa_or_funlbl()], callgraph()) -> callgraph(). +-spec add_edges([callgraph_edge()], [mfa_or_funlbl()], callgraph()) -> ok. add_edges(Edges, MFAs, #callgraph{digraph = DG} = CG) -> - DG = digraph_confirm_vertices(MFAs, DG), + digraph_confirm_vertices(MFAs, DG), add_edges(Edges, CG). --spec take_scc(callgraph()) -> 'none' | {'ok', scc(), callgraph()}. - -take_scc(#callgraph{postorder = [SCC|SCCs]} = CG) -> - {ok, SCC, CG#callgraph{postorder = SCCs}}; -take_scc(#callgraph{postorder = []}) -> - none. - -spec remove_external(callgraph()) -> {callgraph(), [tuple()]}. remove_external(#callgraph{digraph = DG} = CG) -> @@ -221,13 +227,25 @@ find_non_local_calls([{Label1, Label2}|Left], Set) when is_integer(Label1), find_non_local_calls([], Set) -> sets:to_list(Set). --spec renew_race_info(callgraph(), dict(), [label()], [string()]) -> - callgraph(). +-spec get_depends_on(scc() | module(), callgraph()) -> [scc()]. + +get_depends_on(SCC, #callgraph{active_digraph = {'e', Out, _In}}) -> + case ets_lookup_dict(SCC, Out) of + {ok, Value} -> Value; + error -> [] + end; +get_depends_on(SCC, #callgraph{active_digraph = {'d', DG}}) -> + digraph:out_neighbours(DG, SCC). + +-spec get_required_by(scc() | module(), callgraph()) -> [scc()]. -renew_race_info(CG, RaceCode, PublicTables, NamedTables) -> - CG#callgraph{race_code = RaceCode, - public_tables = PublicTables, - named_tables = NamedTables}. +get_required_by(SCC, #callgraph{active_digraph = {'e', _Out, In}}) -> + case ets_lookup_dict(SCC, In) of + {ok, Value} -> Value; + error -> [] + end; +get_required_by(SCC, #callgraph{active_digraph = {'d', DG}}) -> + digraph:in_neighbours(DG, SCC). %%---------------------------------------------------------------------- %% Handling of modules & SCCs @@ -238,32 +256,37 @@ renew_race_info(CG, RaceCode, PublicTables, NamedTables) -> modules(#callgraph{digraph = DG}) -> ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]). --spec module_postorder(callgraph()) -> [[module()]]. +-spec module_postorder(callgraph()) -> {[module()], {'d', digraph()}}. module_postorder(#callgraph{digraph = DG}) -> - {MDG, _Nodes} = get_module_digraph_and_nodes(DG), - MDG1 = digraph_utils:condensation(MDG), - PostOrder = digraph_utils:postorder(MDG1), - PostOrder1 = sort_sccs_internally(PostOrder, MDG), - digraph:delete(MDG1), - digraph_delete(MDG), - PostOrder1. + Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)), + Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), + MDG = digraph:new([acyclic]), + digraph_confirm_vertices(sets:to_list(Nodes), MDG), + Foreach = fun({M1,M2}) -> digraph:add_edge(MDG, M1, M2) end, + lists:foreach(Foreach, sets:to_list(Edges)), + {digraph_utils:topsort(MDG), {'d', MDG}}. + +edge_fold({{M1,_,_},{M2,_,_}}, Set) -> + case M1 =/= M2 of + true -> sets:add_element({M1,M2},Set); + false -> Set + end; +edge_fold(_, Set) -> Set. -get_module_digraph_and_nodes(DG) -> - Edges = digraph_edges(DG), - Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), - MDG = digraph:new(), - MDG = digraph_confirm_vertices(Nodes, MDG), - MDG = create_module_digraph(Edges, MDG), - {MDG, Nodes}. %% The module deps of a module are modules that depend on the module -spec module_deps(callgraph()) -> dict(). module_deps(#callgraph{digraph = DG}) -> - {MDG, Nodes} = get_module_digraph_and_nodes(DG), + Edges = lists:foldl(fun edge_fold/2, sets:new(), digraph_edges(DG)), + Nodes = sets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]), + MDG = digraph:new(), + digraph_confirm_vertices(sets:to_list(Nodes), MDG), + Foreach = fun({M1,M2}) -> digraph:add_edge(MDG, M1, M2) end, + lists:foreach(Foreach, sets:to_list(Edges)), Deps = [{N, ordsets:from_list(digraph:in_neighbours(MDG, N))} - || N <- Nodes], + || N <- sets:to_list(Nodes)], digraph_delete(MDG), dict:from_list(Deps). @@ -276,52 +299,42 @@ strip_module_deps(ModDeps, StripSet) -> FilterFun2 = fun(_Key, ValSet) -> ValSet =/= [] end, dict:filter(FilterFun2, ModDeps1). -sort_sccs_internally(PO, MDG) -> - sort_sccs_internally(PO, MDG, []). - -sort_sccs_internally([SCC|SCCs], MDG, Acc) -> - case SCC of - [_, _, _ | _] -> % length(SCC) >= 3 - TmpDG = digraph_utils:subgraph(MDG, SCC), - NewSCC = digraph_utils:postorder(TmpDG), - digraph_delete(TmpDG), - sort_sccs_internally(SCCs, MDG, [NewSCC|Acc]); - _ -> - sort_sccs_internally(SCCs, MDG, [SCC|Acc]) - end; -sort_sccs_internally([], _MDG, Acc) -> - lists:reverse(Acc). - -create_module_digraph([{{M, _, _}, {M, _, _}}|Left], MDG) -> - create_module_digraph(Left, MDG); -create_module_digraph([{{M1, _, _}, {M2, _, _}}|Left], MDG) -> - create_module_digraph(Left, digraph_add_edge(M1, M2, MDG)); -create_module_digraph([{_, _}|Left], MDG) -> - create_module_digraph(Left, MDG); -create_module_digraph([], MDG) -> - MDG. - --spec finalize(callgraph()) -> callgraph(). +-spec finalize(callgraph()) -> {[scc()], callgraph()}. finalize(#callgraph{digraph = DG} = CG) -> - CG#callgraph{postorder = digraph_finalize(DG)}. + {ActiveDG, Postorder} = condensation(DG), + {Postorder, CG#callgraph{active_digraph = ActiveDG}}. --spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> callgraph(). +-spec reset_from_funs([mfa_or_funlbl()], callgraph()) -> {[scc()], callgraph()}. -reset_from_funs(Funs, #callgraph{digraph = DG} = CG) -> +reset_from_funs(Funs, #callgraph{digraph = DG, active_digraph = ADG} = CG) -> + active_digraph_delete(ADG), SubGraph = digraph_reaching_subgraph(Funs, DG), - Postorder = digraph_finalize(SubGraph), + {NewActiveDG, Postorder} = condensation(SubGraph), digraph_delete(SubGraph), - CG#callgraph{postorder = Postorder}. + {Postorder, CG#callgraph{active_digraph = NewActiveDG}}. --spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> [[module()]]. +-spec module_postorder_from_funs([mfa_or_funlbl()], callgraph()) -> + {[module()], callgraph()}. -module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> +module_postorder_from_funs(Funs, #callgraph{digraph = DG, + active_digraph = ADG} = CG) -> + active_digraph_delete(ADG), SubGraph = digraph_reaching_subgraph(Funs, DG), - PO = module_postorder(CG#callgraph{digraph = SubGraph}), + {PO, Active} = module_postorder(CG#callgraph{digraph = SubGraph}), digraph_delete(SubGraph), - PO. - + {PO, CG#callgraph{active_digraph = Active}}. + +ets_lookup_dict(Key, Table) -> + try ets:lookup_element(Table, Key, 2) of + Val -> {ok, Val} + catch + _:_ -> error + end. + +ets_lookup_set(Key, Table) -> + ets:lookup(Table, Key) =/= []. + %%---------------------------------------------------------------------- %% Core code %%---------------------------------------------------------------------- @@ -330,36 +343,37 @@ module_postorder_from_funs(Funs, #callgraph{digraph = DG} = CG) -> %% The set of labels in the tree must be disjoint from the set of %% labels already occuring in the callgraph. --spec scan_core_tree(cerl:c_module(), callgraph()) -> callgraph(). +-spec scan_core_tree(cerl:c_module(), callgraph()) -> + {[mfa_or_funlbl()], [callgraph_edge()]}. -scan_core_tree(Tree, #callgraph{calls = OldCalls, - esc = OldEsc, - name_map = OldNameMap, - rec_var_map = OldRecVarMap, - rev_name_map = OldRevNameMap, - self_rec = OldSelfRec} = CG) -> +scan_core_tree(Tree, #callgraph{calls = ETSCalls, + esc = ETSEsc, + name_map = ETSNameMap, + rec_var_map = ETSRecVarMap, + rev_name_map = ETSRevNameMap, + self_rec = ETSSelfRec}) -> %% Build name map and recursion variable maps. - {NewNameMap, NewRevNameMap, NewRecVarMap} = - build_maps(Tree, OldRecVarMap, OldNameMap, OldRevNameMap), - + build_maps(Tree, ETSRecVarMap, ETSNameMap, ETSRevNameMap), + %% First find the module-local dependencies. {Deps0, EscapingFuns, Calls} = dialyzer_dep:analyze(Tree), - NewCalls = dict:merge(fun(_Key, Val, Val) -> Val end, OldCalls, Calls), - NewEsc = sets:union(sets:from_list(EscapingFuns), OldEsc), + true = ets:insert(ETSCalls, dict:to_list(Calls)), + true = ets:insert(ETSEsc, [{E} || E <- EscapingFuns]), + LabelEdges = get_edges_from_deps(Deps0), %% Find the self recursive functions. Named functions get both the %% key and their name for convenience. SelfRecs0 = lists:foldl(fun({Key, Key}, Acc) -> - case dict:find(Key, NewNameMap) of + case ets_lookup_dict(Key, ETSNameMap) of error -> [Key|Acc]; {ok, Name} -> [Key, Name|Acc] end; (_, Acc) -> Acc end, [], LabelEdges), - SelfRecs = sets:union(sets:from_list(SelfRecs0), OldSelfRec), + true = ets:insert(ETSSelfRec, [{S} || S <- SelfRecs0]), - NamedEdges1 = name_edges(LabelEdges, NewNameMap), + NamedEdges1 = name_edges(LabelEdges, ETSNameMap), %% We need to scan for inter-module calls since these are not tracked %% by dialyzer_dep. Note that the caller is always recorded as the @@ -378,27 +392,25 @@ scan_core_tree(Tree, #callgraph{calls = OldCalls, NewNamedEdges1 = [E || {From, To} = E <- NamedEdges1, From =/= top, To =/= top], NamedEdges3 = NewNamedEdges1 ++ NewNamedEdges2, - CG1 = add_edges(NamedEdges3, Names3, CG), - CG1#callgraph{calls = NewCalls, - esc = NewEsc, - name_map = NewNameMap, - rec_var_map = NewRecVarMap, - rev_name_map = NewRevNameMap, - self_rec = SelfRecs}. - -build_maps(Tree, RecVarMap, NameMap, RevNameMap) -> + {Names3, NamedEdges3}. + +build_maps(Tree, ETSRecVarMap, ETSNameMap, ETSRevNameMap) -> %% We only care about the named (top level) functions. The anonymous %% functions will be analysed together with their parents. Defs = cerl:module_defs(Tree), Mod = cerl:atom_val(cerl:module_name(Tree)), - lists:foldl(fun({Var, Function}, {AccNameMap, AccRevNameMap, AccRecVarMap}) -> - FunName = cerl:fname_id(Var), - Arity = cerl:fname_arity(Var), - MFA = {Mod, FunName, Arity}, - {dict:store(get_label(Function), MFA, AccNameMap), - dict:store(MFA, get_label(Function), AccRevNameMap), - dict:store(get_label(Var), MFA, AccRecVarMap)} - end, {NameMap, RevNameMap, RecVarMap}, Defs). + Fun = + fun({Var, Function}) -> + FunName = cerl:fname_id(Var), + Arity = cerl:fname_arity(Var), + MFA = {Mod, FunName, Arity}, + FunLabel = get_label(Function), + VarLabel = get_label(Var), + true = ets:insert(ETSNameMap, {FunLabel, MFA}), + true = ets:insert(ETSRevNameMap, {MFA, FunLabel}), + true = ets:insert(ETSRecVarMap, {VarLabel, MFA}) + end, + lists:foreach(Fun, Defs). get_edges_from_deps(Deps) -> %% Convert the dependencies as produced by dialyzer_dep to a list of @@ -411,22 +423,22 @@ get_edges_from_deps(Deps) -> end, [], Deps), lists:flatten(Edges). -name_edges(Edges, NameMap) -> +name_edges(Edges, ETSNameMap) -> %% If a label is present in the name map it is renamed. Otherwise %% keep the label as the identity. MapFun = fun(X) -> - case dict:find(X, NameMap) of + case ets_lookup_dict(X, ETSNameMap) of error -> X; {ok, MFA} -> MFA end end, - name_edges(Edges, MapFun, NameMap, []). + name_edges(Edges, MapFun, []). -name_edges([{From, To}|Left], MapFun, NameMap, Acc) -> +name_edges([{From, To}|Left], MapFun, Acc) -> NewFrom = MapFun(From), NewTo = MapFun(To), - name_edges(Left, MapFun, NameMap, [{NewFrom, NewTo}|Acc]); -name_edges([], _MapFun, _NameMap, Acc) -> + name_edges(Left, MapFun, [{NewFrom, NewTo}|Acc]); +name_edges([], _MapFun, Acc) -> Acc. scan_core_funs(Tree) -> @@ -478,9 +490,10 @@ get_label(T) -> %%---------------------------------------------------------------------- digraph_add_edges([{From, To}|Left], DG) -> - digraph_add_edges(Left, digraph_add_edge(From, To, DG)); -digraph_add_edges([], DG) -> - DG. + digraph_add_edge(From, To, DG), + digraph_add_edges(Left, DG); +digraph_add_edges([], _DG) -> + ok. digraph_add_edge(From, To, DG) -> case digraph:vertex(DG, From) of @@ -492,13 +505,13 @@ digraph_add_edge(From, To, DG) -> {To, _} -> ok end, digraph:add_edge(DG, {From, To}, From, To, []), - DG. + ok. digraph_confirm_vertices([MFA|Left], DG) -> digraph:add_vertex(DG, MFA, confirmed), digraph_confirm_vertices(Left, DG); -digraph_confirm_vertices([], DG) -> - DG. +digraph_confirm_vertices([], _DG) -> + ok. digraph_remove_external(DG) -> Vertices = digraph:vertices(DG), @@ -522,6 +535,12 @@ remove_unconfirmed([], DG, Unconfirmed) -> digraph_delete(DG) -> digraph:delete(DG). +active_digraph_delete({'d', DG}) -> + digraph:delete(DG); +active_digraph_delete({'e', Out, In}) -> + ets:delete(Out), + ets:delete(In). + digraph_edges(DG) -> digraph:edges(DG). @@ -534,75 +553,6 @@ digraph_in_neighbours(V, DG) -> List -> List end. -%% Pick all the independent nodes (leaves) from one module. Then try -%% to stay within the module until no more independent nodes can be -%% chosen. Then pick a new module and so on. -%% -%% Note that an SCC that ranges over more than one module is -%% considered to belong to all modules to make sure that we do not -%% lose any nodes. - -digraph_postorder(Digraph) -> - %% Remove all self-edges for SCCs. - Edges = [digraph:edge(Digraph, E) || E <- digraph:edges(Digraph)], - SelfEdges = [E || {E, V, V, _} <- Edges], - true = digraph:del_edges(Digraph, SelfEdges), - %% Determine the first module outside of the loop. - Leaves = digraph_leaves(Digraph), - case Leaves =:= [] of - true -> []; - false -> - {Module, Taken} = take_sccs_from_fresh_module(Leaves), - true = digraph:del_vertices(Digraph, Taken), - digraph_postorder(Digraph, Module, [Taken]) - end. - -digraph_postorder(Digraph, LastModule, Acc) -> - Leaves = digraph_leaves(Digraph), - case Leaves =:= [] of - true -> lists:append(lists:reverse(Acc)); - false -> - case [SCC || SCC <- Leaves, scc_belongs_to_module(SCC, LastModule)] of - [] -> - {NewModule, NewTaken} = take_sccs_from_fresh_module(Leaves), - true = digraph:del_vertices(Digraph, NewTaken), - digraph_postorder(Digraph, NewModule, [NewTaken|Acc]); - NewTaken -> - true = digraph:del_vertices(Digraph, NewTaken), - digraph_postorder(Digraph, LastModule, [NewTaken|Acc]) - end - end. - -digraph_leaves(Digraph) -> - [V || V <- digraph:vertices(Digraph), digraph:out_degree(Digraph, V) =:= 0]. - -take_sccs_from_fresh_module(Leaves) -> - NewModule = find_module(hd(Leaves)), - {NewModule, - [SCC || SCC <- Leaves, scc_belongs_to_module(SCC, NewModule)]}. - --spec scc_belongs_to_module(scc(), module()) -> boolean(). - -scc_belongs_to_module([Label|Left], Module) when is_integer(Label) -> - scc_belongs_to_module(Left, Module); -scc_belongs_to_module([{M, _, _}|Left], Module) -> - if M =:= Module -> true; - true -> scc_belongs_to_module(Left, Module) - end; -scc_belongs_to_module([], _Module) -> - false. - --spec find_module(scc()) -> module(). - -find_module([{M, _, _}|_]) -> M; -find_module([Label|Left]) when is_integer(Label) -> find_module(Left). - -digraph_finalize(DG) -> - DG1 = digraph_utils:condensation(DG), - Postorder = digraph_postorder(DG1), - digraph:delete(DG1), - Postorder. - digraph_reaching_subgraph(Funs, DG) -> Vertices = digraph_utils:reaching(Funs, DG), digraph_utils:subgraph(DG, Vertices). @@ -611,20 +561,71 @@ digraph_reaching_subgraph(Funs, DG) -> %% Races %%---------------------------------------------------------------------- +-spec renew_race_info(callgraph(), dict(), [label()], [string()]) -> + callgraph(). + +renew_race_info(#callgraph{race_data_server = RaceDataServer} = CG, + RaceCode, PublicTables, NamedTables) -> + ok = race_data_server_cast( + {renew_race_info, {RaceCode, PublicTables, NamedTables}}, + RaceDataServer), + CG. + +renew_race_info({RaceCode, PublicTables, NamedTables}, + #race_data_state{} = State) -> + State#race_data_state{race_code = RaceCode, + public_tables = PublicTables, + named_tables = NamedTables}. + +-spec renew_race_code(dialyzer_races:races(), callgraph()) -> callgraph(). + +renew_race_code(Races, #callgraph{race_data_server = RaceDataServer} = CG) -> + Fun = dialyzer_races:get_curr_fun(Races), + FunArgs = dialyzer_races:get_curr_fun_args(Races), + Code = lists:reverse(dialyzer_races:get_race_list(Races)), + ok = race_data_server_cast( + {renew_race_code, {Fun, FunArgs, Code}}, + RaceDataServer), + CG. + +renew_race_code_handler({Fun, FunArgs, Code}, + #race_data_state{race_code = RaceCode} = State) -> + State#race_data_state{race_code = dict:store(Fun, [FunArgs, Code], RaceCode)}. + +-spec renew_race_public_tables(label(), callgraph()) -> callgraph(). + +renew_race_public_tables(VarLabel, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = + race_data_server_cast({renew_race_public_tables, VarLabel}, RaceDataServer), + CG. + +renew_race_public_tables_handler(VarLabel, + #race_data_state{public_tables = PT} + = State) -> + State#race_data_state{public_tables = ordsets:add_element(VarLabel, PT)}. + -spec cleanup(callgraph()) -> callgraph(). -cleanup(#callgraph{digraph = Digraph, - name_map = NameMap, - rev_name_map = RevNameMap, - public_tables = PublicTables, - named_tables = NamedTables, - race_code = RaceCode}) -> +cleanup(#callgraph{digraph = Digraph, + name_map = NameMap, + rev_name_map = RevNameMap, + race_data_server = RaceDataServer}) -> #callgraph{digraph = Digraph, - name_map = NameMap, - rev_name_map = RevNameMap, - public_tables = PublicTables, - named_tables = NamedTables, - race_code = RaceCode}. + name_map = NameMap, + rev_name_map = RevNameMap, + race_data_server = race_data_server_call(dup, RaceDataServer)}. + +-spec duplicate(callgraph()) -> callgraph(). + +duplicate(#callgraph{race_data_server = RaceDataServer} = Callgraph) -> + Callgraph#callgraph{ + race_data_server = race_data_server_call(dup, RaceDataServer)}. + +-spec dispose_race_server(callgraph()) -> ok. + +dispose_race_server(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_cast(stop, RaceDataServer). -spec get_digraph(callgraph()) -> digraph(). @@ -633,28 +634,34 @@ get_digraph(#callgraph{digraph = Digraph}) -> -spec get_named_tables(callgraph()) -> [string()]. -get_named_tables(#callgraph{named_tables = NamedTables}) -> - NamedTables. +get_named_tables(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_named_tables, RaceDataServer). -spec get_public_tables(callgraph()) -> [label()]. -get_public_tables(#callgraph{public_tables = PT}) -> - PT. +get_public_tables(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_public_tables, RaceDataServer). -spec get_race_code(callgraph()) -> dict(). -get_race_code(#callgraph{race_code = RaceCode}) -> - RaceCode. +get_race_code(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_race_code, RaceDataServer). -spec get_race_detection(callgraph()) -> boolean(). get_race_detection(#callgraph{race_detection = RD}) -> RD. +-spec get_behaviour_api_calls(callgraph()) -> [{mfa(), mfa()}]. + +get_behaviour_api_calls(#callgraph{race_data_server = RaceDataServer}) -> + race_data_server_call(get_behaviour_api_calls, RaceDataServer). + -spec race_code_new(callgraph()) -> callgraph(). -race_code_new(Callgraph) -> - Callgraph#callgraph{race_code = dict:new()}. +race_code_new(#callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast(race_code_new, RaceDataServer), + CG. -spec put_digraph(digraph(), callgraph()) -> callgraph(). @@ -663,8 +670,9 @@ put_digraph(Digraph, Callgraph) -> -spec put_race_code(dict(), callgraph()) -> callgraph(). -put_race_code(RaceCode, Callgraph) -> - Callgraph#callgraph{race_code = RaceCode}. +put_race_code(RaceCode, #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_race_code, RaceCode}, RaceDataServer), + CG. -spec put_race_detection(boolean(), callgraph()) -> callgraph(). @@ -673,13 +681,79 @@ put_race_detection(RaceDetection, Callgraph) -> -spec put_named_tables([string()], callgraph()) -> callgraph(). -put_named_tables(NamedTables, Callgraph) -> - Callgraph#callgraph{named_tables = NamedTables}. +put_named_tables(NamedTables, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_named_tables, NamedTables}, RaceDataServer), + CG. -spec put_public_tables([label()], callgraph()) -> callgraph(). -put_public_tables(PublicTables, Callgraph) -> - Callgraph#callgraph{public_tables = PublicTables}. +put_public_tables(PublicTables, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_public_tables, PublicTables}, RaceDataServer), + CG. + +-spec put_behaviour_api_calls([{mfa(), mfa()}], callgraph()) -> callgraph(). + +put_behaviour_api_calls(Calls, + #callgraph{race_data_server = RaceDataServer} = CG) -> + ok = race_data_server_cast({put_behaviour_api_calls, Calls}, RaceDataServer), + CG. + + +new_race_data_server() -> + spawn_link(fun() -> race_data_server_loop(#race_data_state{}) end). + +race_data_server_loop(State) -> + receive + {call, From, Ref, Query} -> + Reply = race_data_server_handle_call(Query, State), + From ! {Ref, Reply}, + race_data_server_loop(State); + {cast, stop} -> + ok; + {cast, Message} -> + NewState = race_data_server_handle_cast(Message, State), + race_data_server_loop(NewState) + end. + +race_data_server_call(Query, Server) -> + Ref = make_ref(), + Server ! {call, self(), Ref, Query}, + receive + {Ref, Reply} -> Reply + end. + +race_data_server_cast(Message, Server) -> + Server ! {cast, Message}, + ok. + +race_data_server_handle_cast(race_code_new, State) -> + State#race_data_state{race_code = dict:new()}; +race_data_server_handle_cast({Tag, Data}, State) -> + case Tag of + renew_race_info -> renew_race_info(Data, State); + renew_race_code -> renew_race_code_handler(Data, State); + renew_race_public_tables -> renew_race_public_tables_handler(Data, State); + put_race_code -> State#race_data_state{race_code = Data}; + put_public_tables -> State#race_data_state{public_tables = Data}; + put_named_tables -> State#race_data_state{named_tables = Data}; + put_behaviour_api_calls -> State#race_data_state{beh_api_calls = Data} + end. + +race_data_server_handle_call(Query, + #race_data_state{race_code = RaceCode, + public_tables = PublicTables, + named_tables = NamedTables, + beh_api_calls = BehApiCalls} + = State) -> + case Query of + dup -> spawn_link(fun() -> race_data_server_loop(State) end); + get_race_code -> RaceCode; + get_public_tables -> PublicTables; + get_named_tables -> NamedTables; + get_behaviour_api_calls -> BehApiCalls + end. %%============================================================================= %% Utilities for 'dot' @@ -695,7 +769,7 @@ to_dot(#callgraph{digraph = DG, esc = Esc} = CG, File) -> end end, Escaping = [{Fun(L), {color, red}} - || L <- sets:to_list(Esc), L =/= external], + || L <- [E || {E} <- ets:tab2list(Esc)], L =/= external], Vertices = digraph_edges(DG), hipe_dot:translate_list(Vertices, File, "CG", Escaping). @@ -708,14 +782,41 @@ to_ps(#callgraph{} = CG, File, Args) -> _ = os:cmd(Command), ok. -%------------------------------------------------------------------------------- - --spec put_behaviour_api_calls([{mfa(), mfa()}], callgraph()) -> callgraph(). - -put_behaviour_api_calls(Calls, Callgraph) -> - Callgraph#callgraph{beh_api_calls = Calls}. - --spec get_behaviour_api_calls(callgraph()) -> [{mfa(), mfa()}]. - -get_behaviour_api_calls(Callgraph) -> - Callgraph#callgraph.beh_api_calls. +condensation(G) -> + SCs = digraph_utils:strong_components(G), + V2I = ets:new(condensation_v2i, []), + I2C = ets:new(condensation_i2c, []), + I2I = ets:new(condensation_i2i, [bag]), + CFun = + fun(SC, N) -> + lists:foreach(fun(V) -> true = ets:insert(V2I, {V,N}) end, SC), + true = ets:insert(I2C, {N, SC}), + N + 1 + end, + lists:foldl(CFun, 1, SCs), + Fun1 = + fun({V1, V2}) -> + I1 = ets:lookup_element(V2I, V1, 2), + I2 = ets:lookup_element(V2I, V2, 2), + case I1 =:= I2 of + true -> true; + false -> ets:insert(I2I, {I1, I2}) + end + end, + lists:foreach(Fun1, digraph:edges(G)), + Fun3 = + fun({I1, I2}, {Out, In}) -> + SC1 = ets:lookup_element(I2C, I1, 2), + SC2 = ets:lookup_element(I2C, I2, 2), + {dict:append(SC1, SC2, Out), dict:append(SC2, SC1, In)} + end, + {OutDict, InDict} = ets:foldl(Fun3, {dict:new(), dict:new()}, I2I), + [OutETS, InETS] = + [ets:new(Name,[{read_concurrency, true}]) || + Name <- [callgraph_deps_out, callgraph_deps_in]], + ets:insert(OutETS, dict:to_list(OutDict)), + ets:insert(InETS, dict:to_list(InDict)), + ets:delete(V2I), + ets:delete(I2C), + ets:delete(I2I), + {{'e', OutETS, InETS}, SCs}. diff --git a/lib/dialyzer/src/dialyzer_cl.erl b/lib/dialyzer/src/dialyzer_cl.erl index 04a0db890f..6732d96b98 100644 --- a/lib/dialyzer/src/dialyzer_cl.erl +++ b/lib/dialyzer/src/dialyzer_cl.erl @@ -2,7 +2,7 @@ %%------------------------------------------------------------------- %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2011. All Rights Reserved. +%% Copyright Ericsson AB 2006-2012. All Rights Reserved. %% %% The contents of this file are subject to the Erlang Public License, %% Version 1.1, (the "License"); you may not use this file except in @@ -188,6 +188,7 @@ plt_common(#options{init_plts = [InitPlt]} = Opts, RemoveFiles, AddFiles) -> ok -> case Opts#options.output_plt of none -> ok; + InitPlt -> ok; OutPlt -> {ok, Binary} = file:read_file(InitPlt), ok = file:write_file(OutPlt, Binary) @@ -393,10 +394,12 @@ do_analysis(Files, Options, Plt, PltInfo) -> defines = Options#options.defines, include_dirs = Options#options.include_dirs, files = Files, - start_from = Options#options.from, + start_from = Options#options.from, + timing = Options#options.timing, plt = Plt, use_contracts = Options#options.use_contracts, - callgraph_file = Options#options.callgraph_file}, + callgraph_file = Options#options.callgraph_file, + solvers = Options#options.solvers}, State3 = start_analysis(State2, InitAnalysis), {T1, _} = statistics(wall_clock), Return = cl_loop(State3), diff --git a/lib/dialyzer/src/dialyzer_cl_parse.erl b/lib/dialyzer/src/dialyzer_cl_parse.erl index ff8fc39a5e..2ea3d3af5a 100644 --- a/lib/dialyzer/src/dialyzer_cl_parse.erl +++ b/lib/dialyzer/src/dialyzer_cl_parse.erl @@ -2,7 +2,7 @@ %%----------------------------------------------------------------------- %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2011. All Rights Reserved. +%% Copyright Ericsson AB 2006-2012. All Rights Reserved. %% %% The contents of this file are subject to the Erlang Public License, %% Version 1.1, (the "License"); you may not use this file except in @@ -164,6 +164,13 @@ cl(["--src"|T]) -> cl(["--no_spec"|T]) -> put(dialyzer_options_use_contracts, false), cl(T); +cl(["--statistics"|T]) -> + put(dialyzer_timing, true), + cl(T); +cl(["--resources"|T]) -> + put(dialyzer_options_report_mode, quiet), + put(dialyzer_timing, debug), + cl(T); cl(["-v"|_]) -> io:format("Dialyzer version "++?VSN++"\n"), erlang:halt(?RET_NOTHING_SUSPICIOUS); @@ -191,6 +198,9 @@ cl(["--gui"|T]) -> cl(["--wx"|T]) -> put(dialyzer_options_mode, {gui, wx}), cl(T); +cl(["--solver",Solver|T]) -> % not documented + append_var(dialyzer_solvers, [list_to_atom(Solver)]), + cl(T); cl([H|_] = L) -> case filelib:is_file(H) orelse filelib:is_dir(H) of true -> @@ -250,6 +260,8 @@ init() -> put(dialyzer_output_format, formatted), put(dialyzer_filename_opt, basename), put(dialyzer_options_check_plt, DefaultOpts#options.check_plt), + put(dialyzer_timing, DefaultOpts#options.timing), + put(dialyzer_solvers, DefaultOpts#options.solvers), ok. append_defines([Def, Val]) -> @@ -290,6 +302,7 @@ cl_options() -> {filename_opt, get(dialyzer_filename_opt)}, {analysis_type, get(dialyzer_options_analysis_type)}, {get_warnings, get(dialyzer_options_get_warnings)}, + {timing, get(dialyzer_timing)}, {callgraph_file, get(dialyzer_callgraph_file)} |common_options()]. @@ -302,7 +315,8 @@ common_options() -> {report_mode, get(dialyzer_options_report_mode)}, {use_spec, get(dialyzer_options_use_contracts)}, {warnings, get(dialyzer_warnings)}, - {check_plt, get(dialyzer_options_check_plt)}]. + {check_plt, get(dialyzer_options_check_plt)}, + {solvers, get(dialyzer_solvers)}]. %%----------------------------------------------------------------------- @@ -351,7 +365,7 @@ help_message() -> [--apps applications] [-o outfile] [--build_plt] [--add_to_plt] [--remove_from_plt] [--check_plt] [--no_check_plt] [--plt_info] [--get_warnings] - [--no_native] [--fullpath] + [--no_native] [--fullpath] [--statistics] Options: files_or_dirs (for backwards compatibility also as: -c files_or_dirs) Use Dialyzer from the command line to detect defects in the @@ -418,6 +432,9 @@ Options: Make Dialyzer a bit more quiet. --verbose Make Dialyzer a bit more verbose. + --statistics + Prints information about the progress of execution (analysis phases, + time spent in each and size of the relative input). --build_plt The analysis starts from an empty plt and creates a new one from the files specified with -c and -r. Only works for beam files. diff --git a/lib/dialyzer/src/dialyzer_codeserver.erl b/lib/dialyzer/src/dialyzer_codeserver.erl index f1e87affbd..9989118671 100644 --- a/lib/dialyzer/src/dialyzer_codeserver.erl +++ b/lib/dialyzer/src/dialyzer_codeserver.erl @@ -52,9 +52,7 @@ new/0, set_next_core_label/2, set_temp_records/2, - store_records/3, store_temp_records/3, - store_contracts/3, store_temp_contracts/4]). -export_type([codeserver/0]). @@ -63,85 +61,159 @@ %%-------------------------------------------------------------------- --record(codeserver, {table_pid :: pid(), - exported_types = sets:new() :: set(), % set(mfa()) - temp_exported_types = sets:new() :: set(), % set(mfa()) - exports = sets:new() :: set(), % set(mfa()) - next_core_label = 0 :: label(), - records = dict:new() :: dict(), - temp_records = dict:new() :: dict(), - contracts = dict:new() :: dict(), - callbacks = dict:new() :: dict(), - temp_contracts = dict:new() :: dict(), - temp_callbacks = dict:new() :: dict() +-type dict_ets() :: ets:tid(). +-type set_ets() :: ets:tid(). + +-record(codeserver, {next_core_label = 0 :: label(), + code :: dict_ets(), + exported_types :: set_ets(), % set(mfa()) + records :: dict_ets(), + contracts :: dict_ets(), + callbacks :: dict_ets(), + exports :: 'clean' | set_ets(), % set(mfa()) + temp_exported_types :: 'clean' | set_ets(), % set(mfa()) + temp_records :: 'clean' | dict_ets(), + temp_contracts :: 'clean' | dict_ets(), + temp_callbacks :: 'clean' | dict_ets() }). -opaque codeserver() :: #codeserver{}. %%-------------------------------------------------------------------- +ets_dict_find(Key, Table) -> + try ets:lookup_element(Table, Key, 2) of + Val -> {ok, Val} + catch + _:_ -> error + end. + +ets_dict_store(Key, Element, Table) -> + true = ets:insert(Table, {Key, Element}), + Table. + +ets_dict_store_dict(Dict, Table) -> + true = ets:insert(Table, dict:to_list(Dict)). + +ets_dict_to_dict(Table) -> + Fold = fun({Key,Value}, Dict) -> dict:store(Key, Value, Dict) end, + ets:foldl(Fold, dict:new(), Table). + +ets_set_is_element(Key, Table) -> + case ets:lookup(Table, Key) of + [] -> false; + _ -> true + end. + +ets_set_insert_set(Set, Table) -> + ets_set_insert_list(sets:to_list(Set), Table). + +ets_set_insert_list(List, Table) -> + true = ets:insert(Table, [{E} || E <- List]). + +ets_set_to_set(Table) -> + Fold = fun({E}, Set) -> sets:add_element(E, Set) end, + ets:foldl(Fold, sets:new(), Table). + +ets_read_concurrent_table(Name) -> + ets:new(Name,[{read_concurrency, true}]). + +%%-------------------------------------------------------------------- + -spec new() -> codeserver(). new() -> - #codeserver{table_pid = table__new()}. + CodeOptions = [compressed, public, {read_concurrency, true}], + Code = ets:new(dialyzer_codeserver_code, CodeOptions), + TempOptions = [public, {write_concurrency, true}], + [Exports, TempExportedTypes, TempRecords, TempContracts, TempCallbacks] = + [ets:new(Name, TempOptions) || + Name <- + [dialyzer_codeserver_exports, dialyzer_codeserver_temp_exported_types, + dialyzer_codeserver_temp_records, dialyzer_codeserver_temp_contracts, + dialyzer_codeserver_temp_callbacks]], + #codeserver{code = Code, + exports = Exports, + temp_exported_types = TempExportedTypes, + temp_records = TempRecords, + temp_contracts = TempContracts, + temp_callbacks = TempCallbacks}. -spec delete(codeserver()) -> 'ok'. -delete(#codeserver{table_pid = TablePid}) -> - table__delete(TablePid). +delete(#codeserver{code = Code, exported_types = ExportedTypes, + records = Records, contracts = Contracts, + callbacks = Callbacks}) -> + lists:foreach(fun ets:delete/1, + [Code, ExportedTypes, Records, Contracts, Callbacks]). -spec insert(atom(), cerl:c_module(), codeserver()) -> codeserver(). insert(Mod, ModCode, CS) -> - NewTablePid = table__insert(CS#codeserver.table_pid, Mod, ModCode), - CS#codeserver{table_pid = NewTablePid}. + Name = cerl:module_name(ModCode), + Exports = cerl:module_exports(ModCode), + Attrs = cerl:module_attrs(ModCode), + Defs = cerl:module_defs(ModCode), + As = cerl:get_ann(ModCode), + Funs = + [{{Mod, cerl:fname_id(Var), cerl:fname_arity(Var)}, + Val} || Val = {Var, _Fun} <- Defs], + Keys = [Key || {Key, _Value} <- Funs], + ModEntry = {Mod, {Name, Exports, Attrs, Keys, As}}, + true = ets:insert(CS#codeserver.code, [ModEntry|Funs]), + CS. + +-spec get_temp_exported_types(codeserver()) -> set(). + +get_temp_exported_types(#codeserver{temp_exported_types = TempExpTypes}) -> + ets_set_to_set(TempExpTypes). -spec insert_temp_exported_types(set(), codeserver()) -> codeserver(). insert_temp_exported_types(Set, CS) -> - CS#codeserver{temp_exported_types = Set}. + TempExportedTypes = CS#codeserver.temp_exported_types, + true = ets_set_insert_set(Set, TempExportedTypes), + CS. -spec insert_exports([mfa()], codeserver()) -> codeserver(). insert_exports(List, #codeserver{exports = Exports} = CS) -> - Set = sets:from_list(List), - NewExports = sets:union(Exports, Set), - CS#codeserver{exports = NewExports}. + true = ets_set_insert_list(List, Exports), + CS. -spec is_exported(mfa(), codeserver()) -> boolean(). is_exported(MFA, #codeserver{exports = Exports}) -> - sets:is_element(MFA, Exports). + ets_set_is_element(MFA, Exports). -spec get_exported_types(codeserver()) -> set(). % set(mfa()) get_exported_types(#codeserver{exported_types = ExpTypes}) -> - ExpTypes. - --spec get_temp_exported_types(codeserver()) -> set(). - -get_temp_exported_types(#codeserver{temp_exported_types = TempExpTypes}) -> - TempExpTypes. + ets_set_to_set(ExpTypes). -spec get_exports(codeserver()) -> set(). % set(mfa()) get_exports(#codeserver{exports = Exports}) -> - Exports. + ets_set_to_set(Exports). -spec finalize_exported_types(set(), codeserver()) -> codeserver(). finalize_exported_types(Set, CS) -> - CS#codeserver{exported_types = Set, temp_exported_types = sets:new()}. + ExportedTypes = ets_read_concurrent_table(dialyzer_codeserver_exported_types), + true = ets_set_insert_set(Set, ExportedTypes), + TempExpTypes = CS#codeserver.temp_exported_types, + true = ets:delete(TempExpTypes), + CS#codeserver{exported_types = ExportedTypes, temp_exported_types = clean}. -spec lookup_mod_code(atom(), codeserver()) -> cerl:c_module(). lookup_mod_code(Mod, CS) when is_atom(Mod) -> - table__lookup(CS#codeserver.table_pid, Mod). + table__lookup(CS#codeserver.code, Mod). -spec lookup_mfa_code(mfa(), codeserver()) -> {cerl:c_var(), cerl:c_fun()}. lookup_mfa_code({_M, _F, _A} = MFA, CS) -> - table__lookup(CS#codeserver.table_pid, MFA). + table__lookup(CS#codeserver.code, MFA). -spec get_next_core_label(codeserver()) -> label(). @@ -153,20 +225,10 @@ get_next_core_label(#codeserver{next_core_label = NCL}) -> set_next_core_label(NCL, CS) -> CS#codeserver{next_core_label = NCL}. --spec store_records(atom(), dict(), codeserver()) -> codeserver(). - -store_records(Mod, Dict, #codeserver{records = RecDict} = CS) - when is_atom(Mod) -> - case dict:size(Dict) =:= 0 of - true -> CS; - false -> CS#codeserver{records = dict:store(Mod, Dict, RecDict)} - end. - -spec lookup_mod_records(atom(), codeserver()) -> dict(). -lookup_mod_records(Mod, #codeserver{records = RecDict}) - when is_atom(Mod) -> - case dict:find(Mod, RecDict) of +lookup_mod_records(Mod, #codeserver{records = RecDict}) when is_atom(Mod) -> + case ets_dict_find(Mod, RecDict) of error -> dict:new(); {ok, Dict} -> Dict end. @@ -174,7 +236,7 @@ lookup_mod_records(Mod, #codeserver{records = RecDict}) -spec get_records(codeserver()) -> dict(). get_records(#codeserver{records = RecDict}) -> - RecDict. + ets_dict_to_dict(RecDict). -spec store_temp_records(atom(), dict(), codeserver()) -> codeserver(). @@ -182,59 +244,58 @@ store_temp_records(Mod, Dict, #codeserver{temp_records = TempRecDict} = CS) when is_atom(Mod) -> case dict:size(Dict) =:= 0 of true -> CS; - false -> CS#codeserver{temp_records = dict:store(Mod, Dict, TempRecDict)} + false -> CS#codeserver{temp_records = ets_dict_store(Mod, Dict, TempRecDict)} end. -spec get_temp_records(codeserver()) -> dict(). get_temp_records(#codeserver{temp_records = TempRecDict}) -> - TempRecDict. + ets_dict_to_dict(TempRecDict). -spec set_temp_records(dict(), codeserver()) -> codeserver(). set_temp_records(Dict, CS) -> - CS#codeserver{temp_records = Dict}. + true = ets:delete(CS#codeserver.temp_records), + TempRecords = ets:new(dialyzer_codeserver_temp_records,[]), + true = ets_dict_store_dict(Dict, TempRecords), + CS#codeserver{temp_records = TempRecords}. -spec finalize_records(dict(), codeserver()) -> codeserver(). finalize_records(Dict, CS) -> - CS#codeserver{records = Dict, temp_records = dict:new()}. - --spec store_contracts(atom(), dict(), codeserver()) -> codeserver(). - -store_contracts(Mod, Dict, #codeserver{contracts = C} = CS) when is_atom(Mod) -> - case dict:size(Dict) =:= 0 of - true -> CS; - false -> CS#codeserver{contracts = dict:store(Mod, Dict, C)} - end. + true = ets:delete(CS#codeserver.temp_records), + Records = ets_read_concurrent_table(dialyzer_codeserver_records), + true = ets_dict_store_dict(Dict, Records), + CS#codeserver{records = Records, temp_records = clean}. -spec lookup_mod_contracts(atom(), codeserver()) -> dict(). lookup_mod_contracts(Mod, #codeserver{contracts = ContDict}) when is_atom(Mod) -> - case dict:find(Mod, ContDict) of + case ets_dict_find(Mod, ContDict) of error -> dict:new(); - {ok, Dict} -> Dict + {ok, Keys} -> + dict:from_list([get_contract_pair(Key, ContDict)|| Key <- Keys]) end. +get_contract_pair(Key, ContDict) -> + {Key, ets:lookup_element(ContDict, Key, 2)}. + -spec lookup_mfa_contract(mfa(), codeserver()) -> 'error' | {'ok', dialyzer_contracts:file_contract()}. -lookup_mfa_contract({M,_F,_A} = MFA, #codeserver{contracts = ContDict}) -> - case dict:find(M, ContDict) of - error -> error; - {ok, Dict} -> dict:find(MFA, Dict) - end. +lookup_mfa_contract(MFA, #codeserver{contracts = ContDict}) -> + ets_dict_find(MFA, ContDict). -spec get_contracts(codeserver()) -> dict(). get_contracts(#codeserver{contracts = ContDict}) -> - ContDict. + ets_dict_to_dict(ContDict). --spec get_callbacks(codeserver()) -> dict(). +-spec get_callbacks(codeserver()) -> list(). get_callbacks(#codeserver{callbacks = CallbDict}) -> - CallbDict. + ets:tab2list(CallbDict). -spec store_temp_contracts(atom(), dict(), dict(), codeserver()) -> codeserver(). @@ -246,91 +307,44 @@ store_temp_contracts(Mod, SpecDict, CallbackDict, CS1 = case dict:size(SpecDict) =:= 0 of true -> CS; - false -> CS#codeserver{temp_contracts = dict:store(Mod, SpecDict, Cn)} + false -> + CS#codeserver{temp_contracts = ets_dict_store(Mod, SpecDict, Cn)} end, case dict:size(CallbackDict) =:= 0 of true -> CS1; - false -> CS1#codeserver{temp_callbacks = dict:store(Mod, CallbackDict, Cb)} + false -> + CS1#codeserver{temp_callbacks = ets_dict_store(Mod, CallbackDict, Cb)} end. -spec get_temp_contracts(codeserver()) -> {dict(), dict()}. get_temp_contracts(#codeserver{temp_contracts = TempContDict, temp_callbacks = TempCallDict}) -> - {TempContDict, TempCallDict}. + {ets_dict_to_dict(TempContDict), ets_dict_to_dict(TempCallDict)}. -spec finalize_contracts(dict(), dict(), codeserver()) -> codeserver(). -finalize_contracts(CnDict, CbDict, CS) -> - CS#codeserver{contracts = CnDict, - callbacks = CbDict, - temp_contracts = dict:new(), - temp_callbacks = dict:new() - }. - -table__new() -> - spawn_link(fun() -> table__loop(none, dict:new()) end). - -table__delete(TablePid) -> - TablePid ! stop, - ok. - -table__lookup(TablePid, Key) -> - TablePid ! {self(), lookup, Key}, - receive - {TablePid, Key, Ans} -> Ans - end. - -table__insert(TablePid, Key, Val) -> - TablePid ! {insert, [{Key, term_to_binary(Val, [compressed])}]}, - TablePid. - -table__loop(Cached, Map) -> - receive - stop -> ok; - {Pid, lookup, {M, F, A} = MFA} -> - {NewCached, Ans} = - case Cached of - {M, Tree} -> - Val = find_fun(F, A, Tree), - {Cached, Val}; - _ -> - Tree = fetch_and_expand(M, Map), - Val = find_fun(F, A, Tree), - {{M, Tree}, Val} - end, - Pid ! {self(), MFA, Ans}, - table__loop(NewCached, Map); - {Pid, lookup, Mod} when is_atom(Mod) -> - Ans = case Cached of - {Mod, Tree} -> Tree; - _ -> fetch_and_expand(Mod, Map) - end, - Pid ! {self(), Mod, Ans}, - table__loop({Mod, Ans}, Map); - {insert, List} -> - NewMap = lists:foldl(fun({Key, Val}, AccMap) -> - dict:store(Key, Val, AccMap) - end, Map, List), - table__loop(Cached, NewMap) - end. - -fetch_and_expand(Mod, Map) -> - try - Bin = dict:fetch(Mod, Map), - binary_to_term(Bin) - catch - _:_ -> - S = atom_to_list(Mod), - Msg = "found no module named '" ++ S ++ "' in the analyzed files", - exit({error, Msg}) - end. - -find_fun(F, A, Tree) -> - Pred = - fun({Var, _Fun}) -> - (cerl:fname_id(Var) =/= F) orelse - (cerl:fname_arity(Var) =/= A) - end, - [Val|_] = lists:dropwhile(Pred, cerl:module_defs(Tree)), - Val. +finalize_contracts(SpecDict, CallbackDict, CS) -> + Contracts = ets_read_concurrent_table(dialyzer_codeserver_contracts), + Callbacks = ets_read_concurrent_table(dialyzer_codeserver_callbacks), + Contracts = dict:fold(fun decompose_spec_dict/3, Contracts, SpecDict), + Callbacks = dict:fold(fun decompose_cb_dict/3, Callbacks, CallbackDict), + CS#codeserver{contracts = Contracts, callbacks = Callbacks, + temp_contracts = clean, temp_callbacks = clean}. + +decompose_spec_dict(Mod, Dict, Table) -> + Keys = dict:fetch_keys(Dict), + true = ets:insert(Table, dict:to_list(Dict)), + true = ets:insert(Table, {Mod, Keys}), + Table. + +decompose_cb_dict(_Mod, Dict, Table) -> + true = ets:insert(Table, dict:to_list(Dict)), + Table. + +table__lookup(TablePid, M) when is_atom(M) -> + {Name, Exports, Attrs, Keys, As} = ets:lookup_element(TablePid, M, 2), + Defs = [table__lookup(TablePid, Key) || Key <- Keys], + cerl:ann_c_module(As, Name, Exports, Attrs, Defs); +table__lookup(TablePid, MFA) -> + ets:lookup_element(TablePid, MFA, 2). diff --git a/lib/dialyzer/src/dialyzer_contracts.erl b/lib/dialyzer/src/dialyzer_contracts.erl index 2b78b736ab..76f23d00b9 100644 --- a/lib/dialyzer/src/dialyzer_contracts.erl +++ b/lib/dialyzer/src/dialyzer_contracts.erl @@ -344,7 +344,7 @@ insert_constraints([{subtype, Type1, Type2}|Left], Dict) -> false -> %% A lot of things should change to add supertypes throw({error, io_lib:format("First argument of is_subtype constraint " - "must be a type variable\n", [])}) + "must be a type variable: ~p\n", [Type1])}) end; insert_constraints([], Dict) -> Dict. @@ -385,9 +385,8 @@ contract_from_form([{type, _L1, bounded_fun, RecDict, FileLine, TypeAcc, FormAcc) -> TypeFun = fun(ExpTypes, AllRecords) -> - Constr1 = [constraint_from_form(C, RecDict, ExpTypes, AllRecords) - || C <- Constr], - VarDict = insert_constraints(Constr1, dict:new()), + {Constr1, VarDict} = + process_constraints(Constr, RecDict, ExpTypes, AllRecords), Type = erl_types:t_from_form(Form, RecDict, VarDict), NewType = erl_types:t_solve_remote(Type, ExpTypes, AllRecords), {NewType, Constr1} @@ -398,18 +397,66 @@ contract_from_form([{type, _L1, bounded_fun, contract_from_form([], _RecDict, _FileLine, TypeAcc, FormAcc) -> {lists:reverse(TypeAcc), lists:reverse(FormAcc)}. -constraint_from_form({type, _, constraint, [{atom, _, is_subtype}, - [Type1, Type2]]}, RecDict, - ExpTypes, AllRecords) -> - T1 = erl_types:t_from_form(Type1, RecDict), - T2 = erl_types:t_from_form(Type2, RecDict), - T3 = erl_types:t_solve_remote(T1, ExpTypes, AllRecords), - T4 = erl_types:t_solve_remote(T2, ExpTypes, AllRecords), - {subtype, T3, T4}; -constraint_from_form({type, _, constraint, [{atom,_,Name}, List]}, _RecDict, - _ExpTypes, _AllRecords) -> - N = length(List), - throw({error, io_lib:format("Unsupported type guard ~w/~w\n", [Name, N])}). +process_constraints(Constrs, RecDict, ExpTypes, AllRecords) -> + Init = initialize_constraints(Constrs, RecDict, ExpTypes, AllRecords), + constraints_fixpoint(Init, RecDict, ExpTypes, AllRecords). + +initialize_constraints(Constrs, RecDict, ExpTypes, AllRecords) -> + initialize_constraints(Constrs, RecDict, ExpTypes, AllRecords, []). + +initialize_constraints([], _RecDict, _ExpTypes, _AllRecords, Acc) -> + Acc; +initialize_constraints([Constr|Rest], RecDict, ExpTypes, AllRecords, Acc) -> + case Constr of + {type, _, constraint, [{atom, _, is_subtype}, [Type1, Type2]]} -> + T1 = final_form(Type1, RecDict, ExpTypes, AllRecords, dict:new()), + Entry = {T1, Type2}, + initialize_constraints(Rest, RecDict, ExpTypes, AllRecords, [Entry|Acc]); + {type, _, constraint, [{atom,_,Name}, List]} -> + N = length(List), + throw({error, + io_lib:format("Unsupported type guard ~w/~w\n", [Name, N])}) + end. + +constraints_fixpoint(Constrs, RecDict, ExpTypes, AllRecords) -> + VarDict = + constraints_to_dict(Constrs, RecDict, ExpTypes, AllRecords, dict:new()), + constraints_fixpoint(VarDict, Constrs, RecDict, ExpTypes, AllRecords). + +constraints_fixpoint(OldVarDict, Constrs, RecDict, ExpTypes, AllRecords) -> + NewVarDict = + constraints_to_dict(Constrs, RecDict, ExpTypes, AllRecords, OldVarDict), + case NewVarDict of + OldVarDict -> + DictFold = + fun(Key, Value, Acc) -> + [{subtype, erl_types:t_var(Key), Value}|Acc] + end, + FinalConstrs = dict:fold(DictFold, [], NewVarDict), + {FinalConstrs, NewVarDict}; + _Other -> + constraints_fixpoint(NewVarDict, Constrs, RecDict, ExpTypes, AllRecords) + end. + +-define(TYPE_LIMIT, 4). + +final_form(Form, RecDict, ExpTypes, AllRecords, VarDict) -> + T1 = erl_types:t_from_form(Form, RecDict, VarDict), + T2 = erl_types:t_solve_remote(T1, ExpTypes, AllRecords), + erl_types:t_limit(T2, ?TYPE_LIMIT). + +constraints_to_dict(Constrs, RecDict, ExpTypes, AllRecords, VarDict) -> + Subtypes = + constraints_to_subs(Constrs, RecDict, ExpTypes, AllRecords, VarDict, []), + insert_constraints(Subtypes, dict:new()). + +constraints_to_subs([], _RecDict, _ExpTypes, _AllRecords, _VarDict, Acc) -> + Acc; +constraints_to_subs([C|Rest], RecDict, ExpTypes, AllRecords, VarDict, Acc) -> + {T1, Form2} = C, + T2 = final_form(Form2, RecDict, ExpTypes, AllRecords, VarDict), + NewAcc = [{subtype, T1, T2}|Acc], + constraints_to_subs(Rest, RecDict, ExpTypes, AllRecords, VarDict, NewAcc). %% Gets the most general domain of a list of domains of all %% the overloaded contracts diff --git a/lib/dialyzer/src/dialyzer_coordinator.erl b/lib/dialyzer/src/dialyzer_coordinator.erl new file mode 100644 index 0000000000..5719132215 --- /dev/null +++ b/lib/dialyzer/src/dialyzer_coordinator.erl @@ -0,0 +1,250 @@ +%% -*- erlang-indent-level: 2 -*- +%%----------------------------------------------------------------------- +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2006-2011. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +%%%------------------------------------------------------------------- +%%% File : dialyzer_coordinator.erl +%%% Authors : Stavros Aronis <[email protected]> +%%%------------------------------------------------------------------- + +-module(dialyzer_coordinator). + +%%% Export for dialyzer main process +-export([parallel_job/4]). + +%%% Exports for all possible workers +-export([wait_activation/0, job_done/3]). + +%%% Exports for the typesig and dataflow analysis workers +-export([sccs_to_pids/2, request_activation/1]). + +%%% Exports for the compilation workers +-export([get_next_label/2]). + +-export_type([coordinator/0, mode/0, init_data/0, result/0]). + +%%-------------------------------------------------------------------- + +-type collector() :: pid(). +-type regulator() :: pid(). +-type scc_to_pid() :: ets:tid() | 'unused'. + +-type coordinator() :: {collector(), regulator(), scc_to_pid()}. %%opaque +-type timing() :: dialyzer_timing:timing_server(). + +-type scc() :: [mfa_or_funlbl()]. +-type mode() :: 'typesig' | 'dataflow' | 'compile' | 'warnings'. + +-type compile_jobs() :: [file:filename()]. +-type typesig_jobs() :: [scc()]. +-type dataflow_jobs() :: [module()]. +-type warnings_jobs() :: [module()]. + +-type compile_init_data() :: dialyzer_analysis_callgraph:compile_init_data(). +-type typesig_init_data() :: dialyzer_succ_typings:typesig_init_data(). +-type dataflow_init_data() :: dialyzer_succ_typings:dataflow_init_data(). +-type warnings_init_data() :: dialyzer_succ_typings:warnings_init_data(). + +-type compile_result() :: dialyzer_analysis_callgraph:compile_result(). +-type typesig_result() :: [mfa_or_funlbl()]. +-type dataflow_result() :: [mfa_or_funlbl()]. +-type warnings_result() :: [dial_warning()]. + +-type init_data() :: compile_init_data() | typesig_init_data() | + dataflow_init_data() | warnings_init_data(). + +-type result() :: compile_result() | typesig_result() | + dataflow_result() | warnings_result(). + +-type job() :: scc() | module() | file:filename(). +-type job_result() :: dialyzer_analysis_callgraph:one_file_result() | + typesig_result() | dataflow_result() | warnings_result(). + +-record(state, {mode :: mode(), + active = 0 :: integer(), + result :: result(), + next_label = 0 :: integer(), + init_data :: init_data(), + regulator :: regulator(), + scc_to_pid :: scc_to_pid() + }). + +-include("dialyzer.hrl"). + +%%-------------------------------------------------------------------- + +-spec parallel_job('compile', compile_jobs(), compile_init_data(), timing()) -> + {compile_result(), integer()}; + ('typesig', typesig_jobs(), typesig_init_data(), timing()) -> + typesig_result(); + ('dataflow', dataflow_jobs(), dataflow_init_data(), + timing()) -> dataflow_result(); + ('warnings', warnings_jobs(), warnings_init_data(), + timing()) -> warnings_result(). + +parallel_job(Mode, Jobs, InitData, Timing) -> + State = spawn_jobs(Mode, Jobs, InitData, Timing), + collect_result(State). + +spawn_jobs(Mode, Jobs, InitData, Timing) -> + Collector = self(), + Regulator = spawn_regulator(), + TypesigOrDataflow = (Mode =:= 'typesig') orelse (Mode =:= 'dataflow'), + SCCtoPID = + case TypesigOrDataflow of + true -> ets:new(scc_to_pid, [{read_concurrency, true}]); + false -> unused + end, + Coordinator = {Collector, Regulator, SCCtoPID}, + Fold = + fun(Job, Count) -> + Pid = dialyzer_worker:launch(Mode, Job, InitData, Coordinator), + case TypesigOrDataflow of + true -> true = ets:insert(SCCtoPID, {Job, Pid}); + false -> request_activation(Regulator, Pid) + end, + Count + 1 + end, + JobCount = lists:foldl(Fold, 0, Jobs), + Unit = + case Mode of + 'typesig' -> "SCCs"; + _ -> "modules" + end, + dialyzer_timing:send_size_info(Timing, JobCount, Unit), + InitResult = + case Mode of + 'compile' -> dialyzer_analysis_callgraph:compile_init_result(); + _ -> [] + end, + #state{mode = Mode, active = JobCount, result = InitResult, next_label = 0, + init_data = InitData, regulator = Regulator, scc_to_pid = SCCtoPID}. + +collect_result(#state{mode = Mode, active = Active, result = Result, + next_label = NextLabel, init_data = InitData, + regulator = Regulator, scc_to_pid = SCCtoPID} = State) -> + receive + {next_label_request, Estimation, Pid} -> + Pid ! {next_label_reply, NextLabel}, + collect_result(State#state{next_label = NextLabel + Estimation}); + {done, Job, Data} -> + NewResult = update_result(Mode, InitData, Job, Data, Result), + case Active of + 1 -> + kill_regulator(Regulator), + case Mode of + 'compile' -> + {NewResult, NextLabel}; + X when X =:= 'typesig'; X =:= 'dataflow' -> + ets:delete(SCCtoPID), + NewResult; + 'warnings' -> + NewResult + end; + N -> + collect_result(State#state{result = NewResult, active = N - 1}) + end + end. + +update_result(Mode, InitData, Job, Data, Result) -> + case Mode of + 'compile' -> + dialyzer_analysis_callgraph:add_to_result(Job, Data, Result, + InitData); + X when X =:= 'typesig'; X =:= 'dataflow' -> + dialyzer_succ_typings:lookup_names(Data, InitData) ++ Result; + 'warnings' -> + Data ++ Result + end. + +-spec sccs_to_pids([scc() | module()], coordinator()) -> + {[dialyzer_worker:worker()], [scc() | module()]}. + +sccs_to_pids(SCCs, {_Collector, _Regulator, SCCtoPID}) -> + Fold = + fun(SCC, {Pids, Unknown}) -> + try ets:lookup_element(SCCtoPID, SCC, 2) of + Result -> {[Result|Pids], Unknown} + catch + _:_ -> {Pids, [SCC|Unknown]} + end + end, + lists:foldl(Fold, {[], []}, SCCs). + +-spec job_done(job(), job_result(), coordinator()) -> ok. + +job_done(Job, Result, {Collector, Regulator, _SCCtoPID}) -> + Regulator ! done, + Collector ! {done, Job, Result}, + ok. + +-spec get_next_label(integer(), coordinator()) -> integer(). + +get_next_label(EstimatedSize, {Collector, _Regulator, _SCCtoPID}) -> + Collector ! {next_label_request, EstimatedSize, self()}, + receive + {next_label_reply, NextLabel} -> NextLabel + end. + +-spec wait_activation() -> ok. + +wait_activation() -> + receive activate -> ok end. + +activate_pid(Pid) -> + Pid ! activate. + +-spec request_activation(coordinator()) -> ok. + +request_activation({_Collector, Regulator, _SCCtoPID}) -> + Regulator ! {req, self()}, + wait_activation(). + +request_activation(Regulator, Pid) -> + Regulator ! {req, Pid}. + +spawn_regulator() -> + InitTickets = dialyzer_utils:parallelism(), + spawn_link(fun() -> regulator_loop(InitTickets, queue:new()) end). + +regulator_loop(Tickets, Queue) -> + receive + {req, Pid} -> + case Tickets of + 0 -> + regulator_loop(0, queue:in(Pid, Queue)); + N -> + activate_pid(Pid), + regulator_loop(N-1, Queue) + end; + done -> + {Waiting, NewQueue} = queue:out(Queue), + NewTickets = + case Waiting of + empty -> Tickets + 1; + {value, Pid} -> + activate_pid(Pid), + Tickets + end, + regulator_loop(NewTickets, NewQueue); + stop -> ok + end. + +kill_regulator(Regulator) -> + Regulator ! stop. diff --git a/lib/dialyzer/src/dialyzer_dataflow.erl b/lib/dialyzer/src/dialyzer_dataflow.erl index bd375b04fa..7131633da1 100644 --- a/lib/dialyzer/src/dialyzer_dataflow.erl +++ b/lib/dialyzer/src/dialyzer_dataflow.erl @@ -32,13 +32,11 @@ %% Data structure interfaces. -export([state__add_warning/2, state__cleanup/1, + state__duplicate/1, dispose_state/1, state__get_callgraph/1, state__get_races/1, state__get_records/1, state__put_callgraph/2, state__put_races/2, state__records_only/1]). -%% Debug and test interfaces. --export([get_top_level_signatures/2, pp/1]). - -export_type([state/0]). -include("dialyzer.hrl"). @@ -67,7 +65,7 @@ %%-define(DEBUG, true). %%-define(DEBUG_PP, true). -%%-define(DOT, true). +%%-define(DEBUG_TIME, true). -ifdef(DEBUG). -import(erl_types, [t_to_string/1]). @@ -111,7 +109,7 @@ -spec get_warnings(cerl:c_module(), dialyzer_plt:plt(), dialyzer_callgraph:callgraph(), dict(), set()) -> - {[dial_warning()], dict(), dict(), [label()], [string()]}. + {[dial_warning()], dict()}. get_warnings(Tree, Plt, Callgraph, Records, NoWarnUnused) -> State1 = analyze_module(Tree, Plt, Callgraph, Records, true), @@ -119,145 +117,14 @@ get_warnings(Tree, Plt, Callgraph, Records, NoWarnUnused) -> State3 = state__renew_warnings(state__get_warnings(State2, NoWarnUnused), State2), State4 = state__get_race_warnings(State3), - Callgraph1 = State2#state.callgraph, - {State4#state.warnings, state__all_fun_types(State4), - dialyzer_callgraph:get_race_code(Callgraph1), - dialyzer_callgraph:get_public_tables(Callgraph1), - dialyzer_callgraph:get_named_tables(Callgraph1)}. + {State4#state.warnings, state__all_fun_types(State4)}. -spec get_fun_types(cerl:c_module(), dialyzer_plt:plt(), - dialyzer_callgraph:callgraph(), dict()) -> - {dict(), dict(), [label()], [string()]}. + dialyzer_callgraph:callgraph(), dict()) -> dict(). get_fun_types(Tree, Plt, Callgraph, Records) -> State = analyze_module(Tree, Plt, Callgraph, Records, false), - Callgraph1 = State#state.callgraph, - {state__all_fun_types(State), - dialyzer_callgraph:get_race_code(Callgraph1), - dialyzer_callgraph:get_public_tables(Callgraph1), - dialyzer_callgraph:get_named_tables(Callgraph1)}. - -%%-------------------------------------------------------------------- - --spec pp(file:filename()) -> 'ok'. - -pp(File) -> - {ok, Code} = dialyzer_utils:get_core_from_src(File, [no_copt]), - Plt = get_def_plt(), - AnnTree = annotate_module(Code, Plt), - io:put_chars(cerl_prettypr:format(AnnTree, [{hook, cerl_typean:pp_hook()}])), - io:nl(). - -%%-------------------------------------------------------------------- -%% This is used in the testsuite. - --spec get_top_level_signatures(cerl:c_module(), dict()) -> - [{{atom(), arity()}, erl_types:erl_type()}]. - -get_top_level_signatures(Code, Records) -> - {Tree, _} = cerl_trees:label(cerl:from_records(Code)), - Callgraph0 = dialyzer_callgraph:new(), - Callgraph1 = dialyzer_callgraph:scan_core_tree(Tree, Callgraph0), - {Callgraph2, _} = dialyzer_callgraph:remove_external(Callgraph1), - Callgraph = dialyzer_callgraph:finalize(Callgraph2), - to_dot(Callgraph), - Plt = get_def_plt(), - FunTypes = get_fun_types(Tree, Plt, Callgraph, Records), - FunTypes1 = lists:foldl(fun({V, F}, Acc) -> - Label = get_label(F), - case dict:find(Label, Acc) of - error -> - Arity = cerl:fname_arity(V), - Type = t_fun(lists:duplicate(Arity, - t_none()), - t_none()), - dict:store(Label, Type, Acc); - {ok, _} -> Acc - end - end, FunTypes, cerl:module_defs(Tree)), - dialyzer_callgraph:delete(Callgraph), - Sigs = [{{cerl:fname_id(V), cerl:fname_arity(V)}, - dict:fetch(get_label(F), FunTypes1)} - || {V, F} <- cerl:module_defs(Tree)], - ordsets:from_list(Sigs). - -get_def_plt() -> - try - dialyzer_plt:from_file(dialyzer_plt:get_default_plt()) - catch - throw:{dialyzer_error, _} -> dialyzer_plt:new() - end. - -%%% =========================================================================== -%%% -%%% Annotate all top level funs. -%%% -%%% =========================================================================== - -annotate_module(Code, Plt) -> - {Tree, _} = cerl_trees:label(cerl:from_records(Code)), - Callgraph0 = dialyzer_callgraph:new(), - Callgraph1 = dialyzer_callgraph:scan_core_tree(Tree, Callgraph0), - {Callgraph2, _} = dialyzer_callgraph:remove_external(Callgraph1), - Callgraph = dialyzer_callgraph:finalize(Callgraph2), - State = analyze_module(Tree, Plt, Callgraph), - Res = annotate(Tree, State), - dialyzer_callgraph:delete(Callgraph), - Res. - -annotate(Tree, State) -> - case cerl:subtrees(Tree) of - [] -> set_type(Tree, State); - List -> - NewSubTrees = [[annotate(Subtree, State) || Subtree <- Group] - || Group <- List], - NewTree = cerl:update_tree(Tree, NewSubTrees), - set_type(NewTree, State) - end. - -set_type(Tree, State) -> - case cerl:type(Tree) of - 'fun' -> - Type = state__fun_type(Tree, State), - case t_is_any(Type) of - true -> - cerl:set_ann(Tree, delete_ann(typesig, cerl:get_ann(Tree))); - false -> - cerl:set_ann(Tree, append_ann(typesig, Type, cerl:get_ann(Tree))) - end; - apply -> - case state__find_apply_return(Tree, State) of - unknown -> Tree; - ReturnType -> - case t_is_any(ReturnType) of - true -> - cerl:set_ann(Tree, delete_ann(type, cerl:get_ann(Tree))); - false -> - cerl:set_ann(Tree, append_ann(type, ReturnType, - cerl:get_ann(Tree))) - end - end; - _ -> - Tree - end. - -append_ann(Tag, Val, [X | Xs]) -> - if tuple_size(X) >= 1, element(1, X) =:= Tag -> - append_ann(Tag, Val, Xs); - true -> - [X | append_ann(Tag, Val, Xs)] - end; -append_ann(Tag, Val, []) -> - [{Tag, Val}]. - -delete_ann(Tag, [X | Xs]) -> - if tuple_size(X) >= 1, element(1, X) =:= Tag -> - delete_ann(Tag, Xs); - true -> - [X | delete_ann(Tag, Xs)] - end; -delete_ann(_, []) -> - []. + state__all_fun_types(State). %%% =========================================================================== %%% @@ -265,56 +132,46 @@ delete_ann(_, []) -> %%% %%% =========================================================================== -analyze_module(Tree, Plt, Callgraph) -> - analyze_module(Tree, Plt, Callgraph, dict:new(), false). - analyze_module(Tree, Plt, Callgraph, Records, GetWarnings) -> debug_pp(Tree, false), Module = cerl:atom_val(cerl:module_name(Tree)), RaceDetection = dialyzer_callgraph:get_race_detection(Callgraph), - RaceCode = dialyzer_callgraph:get_race_code(Callgraph), BehaviourTranslations = case RaceDetection of true -> dialyzer_behaviours:translatable_behaviours(Tree); false -> [] end, TopFun = cerl:ann_c_fun([{label, top}], [], Tree), - State = state__new(dialyzer_callgraph:race_code_new(Callgraph), - TopFun, Plt, Module, Records, BehaviourTranslations), + State = + state__new(Callgraph, TopFun, Plt, Module, Records, BehaviourTranslations), State1 = state__race_analysis(not GetWarnings, State), State2 = analyze_loop(State1), case GetWarnings of true -> State3 = state__set_warning_mode(State2), State4 = analyze_loop(State3), - State5 = state__restore_race_code(RaceCode, State4), %% EXPERIMENTAL: Turn all behaviour API calls into calls to the %% respective callback module's functions. case BehaviourTranslations of - [] -> dialyzer_races:race(State5); + [] -> dialyzer_races:race(State4); Behaviours -> - Callgraph2 = State5#state.callgraph, - Digraph = dialyzer_callgraph:get_digraph(Callgraph2), + Digraph = dialyzer_callgraph:get_digraph(State4#state.callgraph), TranslatedCallgraph = dialyzer_behaviours:translate_callgraph(Behaviours, Module, - Callgraph2), + Callgraph), St = - dialyzer_races:race(State5#state{callgraph = TranslatedCallgraph}), - Callgraph3 = dialyzer_callgraph:put_digraph(Digraph, - St#state.callgraph), - St#state{callgraph = Callgraph3} + dialyzer_races:race(State4#state{callgraph = TranslatedCallgraph}), + FinalCallgraph = dialyzer_callgraph:put_digraph(Digraph, + St#state.callgraph), + St#state{callgraph = FinalCallgraph} end; false -> - Callgraph1 = State2#state.callgraph, - RaceCode1 = dialyzer_callgraph:get_race_code(Callgraph1), - state__restore_race_code( - dict:merge(fun (_K, V1, _V2) -> V1 end, - RaceCode, RaceCode1), State2) + State2 end. -analyze_loop(#state{callgraph = Callgraph, races = Races} = State) -> +analyze_loop(State) -> case state__get_work(State) of none -> State; {Fun, NewState1} -> @@ -340,10 +197,9 @@ analyze_loop(#state{callgraph = Callgraph, races = Races} = State) -> Map1 = enter_type_lists(Vars, ArgTypes, Map), Body = cerl:fun_body(Fun), FunLabel = get_label(Fun), - RaceDetection = dialyzer_callgraph:get_race_detection(Callgraph), - RaceAnalysis = dialyzer_races:get_race_analysis(Races), + IsRaceAnalysisEnabled = is_race_analysis_enabled(State), NewState3 = - case RaceDetection andalso RaceAnalysis of + case IsRaceAnalysisEnabled of true -> NewState2 = state__renew_curr_fun( state__lookup_name(FunLabel, NewState1), FunLabel, @@ -357,17 +213,8 @@ analyze_loop(#state{callgraph = Callgraph, races = Races} = State) -> [state__lookup_name(get_label(Fun), State), t_to_string(t_fun(ArgTypes, BodyType))]), NewState5 = - case RaceDetection andalso RaceAnalysis of - true -> - Races1 = NewState4#state.races, - Code = lists:reverse(dialyzer_races:get_race_list(Races1)), - Callgraph1 = - renew_code(dialyzer_races:get_curr_fun(Races1), - dialyzer_races:get_curr_fun_args(Races1), - Code, - state__warning_mode(NewState4), - NewState4#state.callgraph), - NewState4#state{callgraph = Callgraph1}; + case IsRaceAnalysisEnabled of + true -> renew_race_code(NewState4); false -> NewState4 end, NewState6 = @@ -582,9 +429,7 @@ handle_apply_or_call([{local, external}|Left], Args, ArgTypes, Map, Tree, State, ArgTypes, t_any()); handle_apply_or_call([{TypeOfApply, {Fun, Sig, Contr, LocalRet}}|Left], Args, ArgTypes, Map, Tree, - #state{callgraph = Callgraph, races = Races, - opaques = Opaques} = State, - AccArgTypes, AccRet) -> + #state{opaques = Opaques} = State, AccArgTypes, AccRet) -> Any = t_any(), AnyArgs = [Any || _ <- Args], GenSig = {AnyArgs, fun(_) -> t_any() end}, @@ -680,8 +525,7 @@ handle_apply_or_call([{TypeOfApply, {Fun, Sig, Contr, LocalRet}}|Left], ?debug("ContrRet: ~s\n", [erl_types:t_to_string(CRange(TmpArgTypes))]), ?debug("SigRet: ~s\n", [erl_types:t_to_string(SigRange)]), State1 = - case dialyzer_callgraph:get_race_detection(Callgraph) andalso - dialyzer_races:get_race_analysis(Races) of + case is_race_analysis_enabled(State) of true -> Ann = cerl:get_ann(Tree), File = get_file(Ann), @@ -1047,20 +891,17 @@ handle_call(Tree, Map, State) -> %%---------------------------------------- -handle_case(Tree, Map, #state{callgraph = Callgraph} = State) -> +handle_case(Tree, Map, State) -> Arg = cerl:case_arg(Tree), Clauses = filter_match_fail(cerl:case_clauses(Tree)), {State1, Map1, ArgType} = SMA = traverse(Arg, Map, State), case t_is_none_or_unit(ArgType) of true -> SMA; false -> - Races = State1#state.races, State2 = - case dialyzer_callgraph:get_race_detection(Callgraph) andalso - dialyzer_races:get_race_analysis(Races) of + case is_race_analysis_enabled(State) of true -> - RaceList = dialyzer_races:get_race_list(Races), - RaceListSize = dialyzer_races:get_race_list_size(Races), + {RaceList, RaceListSize} = get_race_list_and_size(State1), state__renew_race_list([beg_case|RaceList], RaceListSize + 1, State1); false -> State1 @@ -1094,9 +935,8 @@ handle_cons(Tree, Map, State) -> %%---------------------------------------- -handle_let(Tree, Map, #state{callgraph = Callgraph, races = Races} = State) -> - RaceAnalysis = dialyzer_races:get_race_analysis(Races), - RaceDetection = dialyzer_callgraph:get_race_detection(Callgraph), +handle_let(Tree, Map, State) -> + IsRaceAnalysisEnabled = is_race_analysis_enabled(State), Arg = cerl:let_arg(Tree), Vars = cerl:let_vars(Tree), {Map0, State0} = @@ -1104,10 +944,9 @@ handle_let(Tree, Map, #state{callgraph = Callgraph, races = Races} = State) -> true -> [Var] = Vars, {enter_subst(Var, Arg, Map), - case RaceDetection andalso RaceAnalysis of + case IsRaceAnalysisEnabled of true -> - RaceList = dialyzer_races:get_race_list(Races), - RaceListSize = dialyzer_races:get_race_list_size(Races), + {RaceList, RaceListSize} = get_race_list_and_size(State), state__renew_race_list( [dialyzer_races:let_tag_new(Var, Arg)|RaceList], RaceListSize + 1, State); @@ -1117,9 +956,8 @@ handle_let(Tree, Map, #state{callgraph = Callgraph, races = Races} = State) -> end, Body = cerl:let_body(Tree), {State1, Map1, ArgTypes} = SMA = traverse(Arg, Map0, State0), - Callgraph1 = State1#state.callgraph, - Callgraph2 = - case RaceDetection andalso RaceAnalysis andalso cerl:is_c_call(Arg) of + State2 = + case IsRaceAnalysisEnabled andalso cerl:is_c_call(Arg) of true -> Mod = cerl:call_module(Arg), Name = cerl:call_name(Arg), @@ -1127,16 +965,11 @@ handle_let(Tree, Map, #state{callgraph = Callgraph, races = Races} = State) -> cerl:concrete(Mod) =:= ets andalso cerl:is_literal(Name) andalso cerl:concrete(Name) =:= new of - true -> - NewTable = dialyzer_races:get_new_table(State1#state.races), - renew_public_tables(Vars, NewTable, - state__warning_mode(State1), - Callgraph1); - false -> Callgraph1 + true -> renew_race_public_tables(Vars, State1); + false -> State1 end; - false -> Callgraph1 + false -> State1 end, - State2 = State1#state{callgraph = Callgraph2}, case t_is_none_or_unit(ArgTypes) of true -> SMA; false -> @@ -1167,16 +1000,13 @@ handle_module(Tree, Map, State) -> %%---------------------------------------- -handle_receive(Tree, Map, - #state{callgraph = Callgraph, races = Races} = State) -> +handle_receive(Tree, Map, State) -> Clauses = filter_match_fail(cerl:receive_clauses(Tree)), Timeout = cerl:receive_timeout(Tree), State1 = - case dialyzer_callgraph:get_race_detection(Callgraph) andalso - dialyzer_races:get_race_analysis(Races) of + case is_race_analysis_enabled(State) of true -> - RaceList = dialyzer_races:get_race_list(Races), - RaceListSize = dialyzer_races:get_race_list_size(Races), + {RaceList, RaceListSize} = get_race_list_and_size(State), state__renew_race_list([beg_case|RaceList], RaceListSize + 1, State); false -> State @@ -1299,16 +1129,13 @@ handle_tuple(Tree, Map, State) -> %%---------------------------------------- %% Clauses %% -handle_clauses([C|Left], Arg, ArgType, OrigArgType, - #state{callgraph = Callgraph, races = Races} = State, - CaseTypes, MapIn, Acc, ClauseAcc) -> - RaceDetection = dialyzer_callgraph:get_race_detection(Callgraph), - RaceAnalysis = dialyzer_races:get_race_analysis(Races), +handle_clauses([C|Left], Arg, ArgType, OrigArgType, State, CaseTypes, MapIn, + Acc, ClauseAcc) -> + IsRaceAnalysisEnabled = is_race_analysis_enabled(State), State1 = - case RaceDetection andalso RaceAnalysis of + case IsRaceAnalysisEnabled of true -> - RaceList = dialyzer_races:get_race_list(Races), - RaceListSize = dialyzer_races:get_race_list_size(Races), + {RaceList, RaceListSize} = get_race_list_and_size(State), state__renew_race_list( [dialyzer_races:beg_clause_new(Arg, cerl:clause_pats(C), cerl:clause_guard(C))| @@ -1319,11 +1146,9 @@ handle_clauses([C|Left], Arg, ArgType, OrigArgType, {State2, ClauseMap, BodyType, NewArgType} = do_clause(C, Arg, ArgType, OrigArgType, MapIn, State1), {NewClauseAcc, State3} = - case RaceDetection andalso RaceAnalysis of + case IsRaceAnalysisEnabled of true -> - Races1 = State2#state.races, - RaceList1 = dialyzer_races:get_race_list(Races1), - RaceListSize1 = dialyzer_races:get_race_list_size(Races1), + {RaceList1, RaceListSize1} = get_race_list_and_size(State2), EndClause = dialyzer_races:end_clause_new(Arg, cerl:clause_pats(C), cerl:clause_guard(C)), {[EndClause|ClauseAcc], @@ -1338,30 +1163,25 @@ handle_clauses([C|Left], Arg, ArgType, OrigArgType, end, handle_clauses(Left, Arg, NewArgType, OrigArgType, State3, NewCaseTypes, MapIn, NewAcc, NewClauseAcc); -handle_clauses([], _Arg, _ArgType, _OrigArgType, - #state{callgraph = Callgraph, races = Races} = State, - CaseTypes, _MapIn, Acc, ClauseAcc) -> +handle_clauses([], _Arg, _ArgType, _OrigArgType, State, CaseTypes, _MapIn, Acc, + ClauseAcc) -> State1 = - case dialyzer_callgraph:get_race_detection(Callgraph) andalso - dialyzer_races:get_race_analysis(Races) of + case is_race_analysis_enabled(State) of true -> + {RaceList, RaceListSize} = get_race_list_and_size(State), state__renew_race_list( - [dialyzer_races:end_case_new(ClauseAcc)| - dialyzer_races:get_race_list(Races)], - dialyzer_races:get_race_list_size(Races) + 1, State); + [dialyzer_races:end_case_new(ClauseAcc)|RaceList], + RaceListSize + 1, State); false -> State end, {lists:reverse(Acc), State1, t_sup(CaseTypes)}. -do_clause(C, Arg, ArgType0, OrigArgType, Map, - #state{callgraph = Callgraph, races = Races} = State) -> +do_clause(C, Arg, ArgType0, OrigArgType, Map, State) -> Pats = cerl:clause_pats(C), Guard = cerl:clause_guard(C), Body = cerl:clause_body(C), - RaceDetection = dialyzer_callgraph:get_race_detection(Callgraph), - RaceAnalysis = dialyzer_races:get_race_analysis(Races), State1 = - case RaceDetection andalso RaceAnalysis of + case is_race_analysis_enabled(State) of true -> state__renew_fun_args(Pats, State); false -> State @@ -2648,14 +2468,18 @@ join_maps(Maps, MapOut) -> Keys = ordsets:from_list(dict:fetch_keys(Dict) ++ dict:fetch_keys(Subst)), join_maps(Keys, Maps, MapOut). -join_maps([Key|Left], Maps, MapOut) -> +join_maps(Keys, Maps, MapOut) -> + KTs = join_maps_collect(Keys, Maps, MapOut), + lists:foldl(fun({K, T}, M) -> enter_type(K, T, M) end, MapOut, KTs). + +join_maps_collect([Key|Left], Maps, MapOut) -> Type = join_maps_one_key(Maps, Key, t_none()), case t_is_equal(lookup_type(Key, MapOut), Type) of - true -> join_maps(Left, Maps, MapOut); - false -> join_maps(Left, Maps, enter_type(Key, Type, MapOut)) + true -> join_maps_collect(Left, Maps, MapOut); + false -> [{Key, Type} | join_maps_collect(Left, Maps, MapOut)] end; -join_maps([], _Maps, MapOut) -> - MapOut. +join_maps_collect([], _Maps, _MapOut) -> + []. join_maps_one_key([Map|Left], Key, AccType) -> case t_is_any(AccType) of @@ -2914,10 +2738,6 @@ state__set_warning_mode(#state{tree_map = TreeMap, fun_tab = FunTab, fun_tab = FunTab, warning_mode = true, races = dialyzer_races:put_race_analysis(true, Races)}. -state__restore_race_code(RaceCode, #state{callgraph = Callgraph} = State) -> - State#state{callgraph = dialyzer_callgraph:put_race_code(RaceCode, - Callgraph)}. - state__race_analysis(Analysis, #state{races = Races} = State) -> State#state{races = dialyzer_races:put_race_analysis(Analysis, Races)}. @@ -3260,21 +3080,6 @@ state__fun_info(Fun, #state{callgraph = CG, fun_tab = FunTab, plt = PLT}) -> ?debug("LocalRet: ~s\n", [t_to_string(LocalRet)]), {Fun, Sig, Contract, LocalRet}. -state__find_apply_return(Tree, #state{callgraph = Callgraph} = State) -> - Apply = get_label(Tree), - case dialyzer_callgraph:lookup_call_site(Apply, Callgraph) of - error -> - unknown; - {ok, List} -> - case lists:member(external, List) of - true -> t_any(); - false -> - FunTypes = [state__fun_type(F, State) || F <- List], - Returns = [t_fun_range(F) || F <- FunTypes], - t_sup(Returns) - end - end. - forward_args(Fun, ArgTypes, #state{work = Work, fun_tab = FunTab} = State) -> {OldArgTypes, OldOut, Fixpoint} = case dict:find(Fun, FunTab) of @@ -3305,6 +3110,16 @@ state__cleanup(#state{callgraph = Callgraph, races = dialyzer_races:cleanup(Races), records = Records}. +-spec state__duplicate(state()) -> state(). + +state__duplicate(#state{callgraph = Callgraph} = State) -> + State#state{callgraph = dialyzer_callgraph:duplicate(Callgraph)}. + +-spec dispose_state(state()) -> ok. + +dispose_state(#state{callgraph = Callgraph}) -> + dialyzer_callgraph:dispose_race_server(Callgraph). + -spec state__get_callgraph(state()) -> dialyzer_callgraph:callgraph(). state__get_callgraph(#state{callgraph = Callgraph}) -> @@ -3342,26 +3157,36 @@ state__records_only(#state{records = Records}) -> %%% %%% =========================================================================== -renew_code(Fun, FunArgs, Code, WarningMode, Callgraph) -> +is_race_analysis_enabled(#state{races = Races, callgraph = Callgraph}) -> + RaceDetection = dialyzer_callgraph:get_race_detection(Callgraph), + RaceAnalysis = dialyzer_races:get_race_analysis(Races), + RaceDetection andalso RaceAnalysis. + +get_race_list_and_size(#state{races = Races}) -> + dialyzer_races:get_race_list_and_size(Races). + +renew_race_code(#state{races = Races, callgraph = Callgraph, + warning_mode = WarningMode} = State) -> case WarningMode of - true -> Callgraph; + true -> State; false -> - RaceCode = dialyzer_callgraph:get_race_code(Callgraph), - dialyzer_callgraph:put_race_code( - dict:store(Fun, [FunArgs, Code], RaceCode), Callgraph) + NewCallgraph = dialyzer_callgraph:renew_race_code(Races, Callgraph), + State#state{callgraph = NewCallgraph} end. -renew_public_tables([Var], Table, WarningMode, Callgraph) -> +renew_race_public_tables([Var], #state{races = Races, callgraph = Callgraph, + warning_mode = WarningMode} = State) -> case WarningMode of - true -> Callgraph; + true -> State; false -> + Table = dialyzer_races:get_new_table(Races), case Table of - no_t -> Callgraph; - _Other -> - VarLabel = get_label(Var), - PTables = dialyzer_callgraph:get_public_tables(Callgraph), - dialyzer_callgraph:put_public_tables( - lists:usort([VarLabel|PTables]), Callgraph) + no_t -> State; + _Other -> + VarLabel = get_label(Var), + NewCallgraph = + dialyzer_callgraph:renew_race_public_tables(VarLabel, Callgraph), + State#state{callgraph = NewCallgraph} end end. @@ -3688,17 +3513,3 @@ strip_annotations(Tree) -> debug_pp(_Tree, _UseHook) -> ok. -endif. - -%%---------------------------------------------------------------------------- - --spec to_dot(dialyzer_callgraph:callgraph()) -> 'ok'. - --ifdef(DOT). -to_dot(CG) -> - dialyzer_callgraph:to_dot(CG). --else. -to_dot(_CG) -> - ok. --endif. - -%%---------------------------------------------------------------------------- diff --git a/lib/dialyzer/src/dialyzer_options.erl b/lib/dialyzer/src/dialyzer_options.erl index 866650a0b2..06672e595f 100644 --- a/lib/dialyzer/src/dialyzer_options.erl +++ b/lib/dialyzer/src/dialyzer_options.erl @@ -2,7 +2,7 @@ %%----------------------------------------------------------------------- %% %CopyrightBegin% %% -%% Copyright Ericsson AB 2006-2011. All Rights Reserved. +%% Copyright Ericsson AB 2006-2012. All Rights Reserved. %% %% The contents of this file are subject to the Erlang Public License, %% Version 1.1, (the "License"); you may not use this file except in @@ -194,6 +194,11 @@ build_options([{OptionName, Value} = Term|Rest], Options) -> callgraph_file -> assert_filename(Value), build_options(Rest, Options#options{callgraph_file = Value}); + timing -> + build_options(Rest, Options#options{timing = Value}); + solvers -> + assert_solvers(Value), + build_options(Rest, Options#options{solvers = Value}); _ -> bad_option("Unknown dialyzer command line option", Term) end; @@ -255,6 +260,15 @@ is_plt_mode(plt_remove) -> true; is_plt_mode(plt_check) -> true; is_plt_mode(succ_typings) -> false. +assert_solvers([]) -> + ok; +assert_solvers([v1|Terms]) -> + assert_solvers(Terms); +assert_solvers([v2|Terms]) -> + assert_solvers(Terms); +assert_solvers([Term|_]) -> + bad_option("Illegal value for solver", Term). + -spec build_warnings([atom()], [dial_warning()]) -> [dial_warning()]. build_warnings([Opt|Opts], Warnings) -> diff --git a/lib/dialyzer/src/dialyzer_plt.erl b/lib/dialyzer/src/dialyzer_plt.erl index 06eaadad9c..5f64099210 100644 --- a/lib/dialyzer/src/dialyzer_plt.erl +++ b/lib/dialyzer/src/dialyzer_plt.erl @@ -55,7 +55,10 @@ plt_and_info_from_file/1, get_specs/1, get_specs/4, - to_file/4]). + to_file/4, + get_mini_plt/1, + restore_full_plt/2 + ]). %% Debug utilities -export([pp_non_returning/0, pp_mod/1]). @@ -82,7 +85,13 @@ contracts = table_new() :: dict(), callbacks = table_new() :: dict(), exported_types = sets:new() :: set()}). --opaque plt() :: #plt{}. + +-record(mini_plt, {info :: ets:tid(), + contracts :: ets:tid(), + callbacks :: ets:tid() + }). + +-opaque plt() :: #plt{} | #mini_plt{}. -include("dialyzer.hrl"). @@ -132,51 +141,48 @@ delete_list(#plt{info = Info, types = Types, -spec insert_contract_list(plt(), dialyzer_contracts:plt_contracts()) -> plt(). -insert_contract_list(#plt{contracts = Contracts} = PLT, List) -> - PLT#plt{contracts = table_insert_list(Contracts, List)}. +insert_contract_list(#mini_plt{contracts = Contracts} = PLT, List) -> + true = ets:insert(Contracts, List), + PLT. -spec insert_callbacks(plt(), dialyzer_codeserver:codeserver()) -> plt(). insert_callbacks(#plt{callbacks = Callbacks} = Plt, Codeserver) -> - FunPreferNew = fun(_Key, _Val1, Val2) -> Val2 end, - FunDictMerger = - fun(_Key, Value, AccIn) -> dict:merge(FunPreferNew, Value, AccIn) end, - MergedCallbacks = dict:fold(FunDictMerger, dict:new(), - dialyzer_codeserver:get_callbacks(Codeserver)), - List = dict:to_list(MergedCallbacks), + List = dialyzer_codeserver:get_callbacks(Codeserver), Plt#plt{callbacks = table_insert_list(Callbacks, List)}. -spec lookup_contract(plt(), mfa_patt()) -> 'none' | {'value', #contract{}}. -lookup_contract(#plt{contracts = Contracts}, +lookup_contract(#mini_plt{contracts = ETSContracts}, {M, F, _} = MFA) when is_atom(M), is_atom(F) -> - table_lookup(Contracts, MFA). + ets_table_lookup(ETSContracts, MFA). -spec lookup_callbacks(plt(), module()) -> - [{mfa(), {{Filename::string(), Line::pos_integer()}, #contract{}}}]. + 'none' | {'value', [{mfa(), {{Filename::string(), + Line::pos_integer()}, + #contract{}}}]}. -lookup_callbacks(#plt{callbacks = Callbacks}, Mod) when is_atom(Mod) -> - FunModFilter = - fun({M, _F, _A}, _Val) -> M =:= Mod; - ( _Key, _Val) -> false - end, - ModCallbacks = dict:filter(FunModFilter, Callbacks), - dict:to_list(ModCallbacks). +lookup_callbacks(#mini_plt{callbacks = ETSCallbacks}, Mod) when is_atom(Mod) -> + ets_table_lookup(ETSCallbacks, Mod). -type ret_args_types() :: {erl_types:erl_type(), [erl_types:erl_type()]}. -spec insert_list(plt(), [{mfa() | integer(), ret_args_types()}]) -> plt(). -insert_list(#plt{info = Info} = PLT, List) -> - PLT#plt{info = table_insert_list(Info, List)}. +insert_list(#mini_plt{info = Info} = PLT, List) -> + true = ets:insert(Info, List), + PLT. -spec lookup(plt(), integer() | mfa_patt()) -> 'none' | {'value', ret_args_types()}. -lookup(#plt{info = Info}, {M, F, _} = MFA) when is_atom(M), is_atom(F) -> - table_lookup(Info, MFA); -lookup(#plt{info = Info}, Label) when is_integer(Label) -> - table_lookup(Info, Label). +lookup(Plt, {M, F, _} = MFA) when is_atom(M), is_atom(F) -> + lookup_1(Plt, MFA); +lookup(Plt, Label) when is_integer(Label) -> + lookup_1(Plt, Label). + +lookup_1(#mini_plt{info = Info}, MFAorLabel) -> + ets_table_lookup(Info, MFAorLabel). -spec insert_types(plt(), dict()) -> plt(). @@ -503,6 +509,34 @@ init_md5_list_1([], DiffList, Acc) -> init_md5_list_1(Md5List, [], Acc) -> {ok, lists:reverse(Acc, Md5List)}. +-spec get_mini_plt(plt()) -> plt(). + +get_mini_plt(#plt{info = Info, contracts = Contracts, callbacks = Callbacks}) -> + [ETSInfo, ETSContracts, ETSCallbacks] = + [ets:new(Name, [public]) || Name <- [plt_info, plt_contracts, plt_callbacks]], + CallbackList = dict:to_list(Callbacks), + CallbacksByModule = + [{M, [Cb || {{M1,_,_},_} = Cb <- CallbackList, M1 =:= M]} || + M <- lists:usort([M || {{M,_,_},_} <- CallbackList])], + [true, true] = + [ets:insert(ETS, dict:to_list(Data)) || + {ETS, Data} <- [{ETSInfo, Info}, {ETSContracts, Contracts}]], + true = ets:insert(ETSCallbacks, CallbacksByModule), + #mini_plt{info = ETSInfo, contracts = ETSContracts, callbacks = ETSCallbacks}; +get_mini_plt(undefined) -> + undefined. + +-spec restore_full_plt(plt(), plt()) -> plt(). + +restore_full_plt(#mini_plt{info = ETSInfo, contracts = ETSContracts}, Plt) -> + Info = dict:from_list(ets:tab2list(ETSInfo)), + Contracts = dict:from_list(ets:tab2list(ETSContracts)), + ets:delete(ETSContracts), + ets:delete(ETSInfo), + Plt#plt{info = Info, contracts = Contracts}; +restore_full_plt(undefined, undefined) -> + undefined. + %%--------------------------------------------------------------------------- %% Edoc @@ -595,6 +629,13 @@ table_lookup(Plt, Obj) -> {ok, Val} -> {value, Val} end. +ets_table_lookup(Plt, Obj) -> + try ets:lookup_element(Plt, Obj, 2) of + Val -> {value, Val} + catch + _:_ -> none + end. + table_lookup_module(Plt, Mod) -> List = dict:fold(fun(Key, Val, Acc) -> case Key of diff --git a/lib/dialyzer/src/dialyzer_races.erl b/lib/dialyzer/src/dialyzer_races.erl index cc635b0eef..cdb9f25999 100644 --- a/lib/dialyzer/src/dialyzer_races.erl +++ b/lib/dialyzer/src/dialyzer_races.erl @@ -36,6 +36,7 @@ -export([beg_clause_new/3, cleanup/1, end_case_new/1, end_clause_new/3, get_curr_fun/1, get_curr_fun_args/1, get_new_table/1, get_race_analysis/1, get_race_list/1, get_race_list_size/1, + get_race_list_and_size/1, let_tag_new/2, new/0, put_curr_fun/3, put_fun_args/2, put_race_analysis/2, put_race_list/3]). @@ -346,6 +347,7 @@ fixup_race_list(RaceWarnTag, WarnVarArgs, State) -> DepList2 = fixup_race_list_helper(NewParents, Calls, CurrFun, WarnVarArgs, RaceWarnTag, NewState), + dialyzer_dataflow:dispose_state(CleanState), lists:usort(cleanup_dep_calls(DepList1 ++ DepList2)). fixup_race_list_helper(Parents, Calls, CurrFun, WarnVarArgs, RaceWarnTag, @@ -380,13 +382,15 @@ fixup_race_forward_pullout(CurrFun, CurrFunLabel, Calls, Code, RaceList, InitFun, WarnVarArgs, RaceWarnTag, RaceVarMap, FunDefVars, FunCallVars, FunArgTypes, NestingLevel, State) -> + TState = dialyzer_dataflow:state__duplicate(State), {DepList, NewCurrFun, NewCurrFunLabel, NewCalls, NewCode, NewRaceList, NewRaceVarMap, NewFunDefVars, NewFunCallVars, NewFunArgTypes, NewNestingLevel} = fixup_race_forward(CurrFun, CurrFunLabel, Calls, Code, RaceList, InitFun, WarnVarArgs, RaceWarnTag, RaceVarMap, FunDefVars, FunCallVars, FunArgTypes, NestingLevel, - cleanup_race_code(State)), + cleanup_race_code(TState)), + dialyzer_dataflow:dispose_state(TState), case NewCode of [] -> DepList; [#fun_call{caller = NewCurrFun, callee = Call, arg_types = FunTypes, @@ -2434,6 +2438,12 @@ get_race_list(#races{race_list = RaceList}) -> get_race_list_size(#races{race_list_size = RaceListSize}) -> RaceListSize. +-spec get_race_list_and_size(races()) -> {code(), non_neg_integer()}. + +get_race_list_and_size(#races{race_list = RaceList, + race_list_size = RaceListSize}) -> + {RaceList, RaceListSize}. + -spec let_tag_new(var_to_map1(), var_to_map1()) -> #let_tag{}. let_tag_new(Var, Arg) -> diff --git a/lib/dialyzer/src/dialyzer_succ_typings.erl b/lib/dialyzer/src/dialyzer_succ_typings.erl index 5982603b7b..84379642bf 100644 --- a/lib/dialyzer/src/dialyzer_succ_typings.erl +++ b/lib/dialyzer/src/dialyzer_succ_typings.erl @@ -28,15 +28,22 @@ -module(dialyzer_succ_typings). -export([analyze_callgraph/3, - analyze_callgraph/4, - get_warnings/6]). + analyze_callgraph/6, + get_warnings/8 + ]). -%% These are only intended as debug functions. --export([doit/1, - get_top_level_signatures/3]). +-export([ + find_succ_types_for_scc/2, + refine_one_module/2, + find_required_by/2, + find_depends_on/2, + collect_warnings/2, + lookup_names/2 + ]). + +-export_type([typesig_init_data/0, dataflow_init_data/0, warnings_init_data/0]). %%-define(DEBUG, true). -%%-define(DEBUG_PP, true). -ifdef(DEBUG). -define(debug(X__, Y__), io:format(X__, Y__)). @@ -54,11 +61,21 @@ %% State record -- local to this module -type parent() :: 'none' | pid(). +-type typesig_init_data() :: term(). +-type dataflow_init_data() :: term(). +-type warnings_init_data() :: term(). + +-type fixpoint_init_data() :: typesig_init_data() | dataflow_init_data(). + +-type scc() :: [mfa_or_funlbl()] | [module()]. + -record(st, {callgraph :: dialyzer_callgraph:callgraph(), codeserver :: dialyzer_codeserver:codeserver(), no_warn_unused :: set(), parent = none :: parent(), + timing_server :: dialyzer_timing:timing_server(), + solvers :: [solver()], plt :: dialyzer_plt:plt()}). %%-------------------------------------------------------------------- @@ -68,60 +85,90 @@ dialyzer_plt:plt(). analyze_callgraph(Callgraph, Plt, Codeserver) -> - analyze_callgraph(Callgraph, Plt, Codeserver, none). + analyze_callgraph(Callgraph, Plt, Codeserver, none, [], none). -spec analyze_callgraph(dialyzer_callgraph:callgraph(), dialyzer_plt:plt(), - dialyzer_codeserver:codeserver(), parent()) -> + dialyzer_codeserver:codeserver(), + dialyzer_timing:timing_server(), + [solver()], parent()) -> dialyzer_plt:plt(). -analyze_callgraph(Callgraph, Plt, Codeserver, Parent) -> - State = #st{callgraph = Callgraph, plt = Plt, - codeserver = Codeserver, parent = Parent}, - NewState = get_refined_success_typings(State), - NewState#st.plt. +analyze_callgraph(Callgraph, Plt, Codeserver, TimingServer, Solvers, Parent) -> + NewState = + init_state_and_get_success_typings(Callgraph, Plt, Codeserver, + TimingServer, Solvers, Parent), + dialyzer_plt:restore_full_plt(NewState#st.plt, Plt). %%-------------------------------------------------------------------- -get_refined_success_typings(State) -> - case find_succ_typings(State) of +init_state_and_get_success_typings(Callgraph, Plt, Codeserver, + TimingServer, Solvers, Parent) -> + {SCCs, Callgraph1} = + ?timing(TimingServer, "order", dialyzer_callgraph:finalize(Callgraph)), + State = #st{callgraph = Callgraph1, plt = dialyzer_plt:get_mini_plt(Plt), + codeserver = Codeserver, parent = Parent, + timing_server = TimingServer, solvers = Solvers}, + get_refined_success_typings(SCCs, State). + +get_refined_success_typings(SCCs, #st{callgraph = Callgraph, + timing_server = TimingServer} = State) -> + case find_succ_typings(SCCs, State) of {fixpoint, State1} -> State1; {not_fixpoint, NotFixpoint1, State1} -> - Callgraph = State1#st.callgraph, - NotFixpoint2 = [lookup_name(F, Callgraph) || F <- NotFixpoint1], - ModulePostorder = - dialyzer_callgraph:module_postorder_from_funs(NotFixpoint2, Callgraph), - case refine_succ_typings(ModulePostorder, State1) of + {ModulePostorder, ModCallgraph} = + ?timing( + TimingServer, "order", _C1, + dialyzer_callgraph:module_postorder_from_funs(NotFixpoint1, + Callgraph)), + ModState = State1#st{callgraph = ModCallgraph}, + case refine_succ_typings(ModulePostorder, ModState) of {fixpoint, State2} -> State2; - {not_fixpoint, NotFixpoint3, State2} -> - Callgraph1 = State2#st.callgraph, + {not_fixpoint, NotFixpoint2, State2} -> %% Need to reset the callgraph. - NotFixpoint4 = [lookup_name(F, Callgraph1) || F <- NotFixpoint3], - Callgraph2 = dialyzer_callgraph:reset_from_funs(NotFixpoint4, - Callgraph1), - get_refined_success_typings(State2#st{callgraph = Callgraph2}) + {NewSCCs, Callgraph2} = + ?timing(TimingServer, "order", _C2, + dialyzer_callgraph:reset_from_funs(NotFixpoint2, + ModCallgraph)), + NewState = State2#st{callgraph = Callgraph2}, + get_refined_success_typings(NewSCCs, NewState) end end. -type doc_plt() :: 'undefined' | dialyzer_plt:plt(). -spec get_warnings(dialyzer_callgraph:callgraph(), dialyzer_plt:plt(), doc_plt(), dialyzer_codeserver:codeserver(), set(), - pid()) -> + dialyzer_timing:timing_server(), [solver()], pid()) -> {[dial_warning()], dialyzer_plt:plt(), doc_plt()}. -get_warnings(Callgraph, Plt, DocPlt, Codeserver, NoWarnUnused, Parent) -> - InitState = #st{callgraph = Callgraph, codeserver = Codeserver, - no_warn_unused = NoWarnUnused, parent = Parent, plt = Plt}, - NewState = get_refined_success_typings(InitState), +get_warnings(Callgraph, Plt, DocPlt, Codeserver, + NoWarnUnused, TimingServer, Solvers, Parent) -> + InitState = + init_state_and_get_success_typings(Callgraph, Plt, Codeserver, + TimingServer, Solvers, Parent), + NewState = InitState#st{no_warn_unused = NoWarnUnused}, Mods = dialyzer_callgraph:modules(NewState#st.callgraph), - CWarns = dialyzer_contracts:get_invalid_contract_warnings(Mods, Codeserver, - NewState#st.plt), - get_warnings_from_modules(Mods, NewState, DocPlt, CWarns). - -get_warnings_from_modules([M|Ms], State, DocPlt, Acc) when is_atom(M) -> - send_log(State#st.parent, io_lib:format("Getting warnings for ~w\n", [M])), + MiniPlt = NewState#st.plt, + CWarns = + dialyzer_contracts:get_invalid_contract_warnings(Mods, Codeserver, MiniPlt), + MiniDocPlt = dialyzer_plt:get_mini_plt(DocPlt), + ModWarns = + ?timing(TimingServer, "warning", + get_warnings_from_modules(Mods, NewState, MiniDocPlt)), + {postprocess_warnings(CWarns ++ ModWarns, Codeserver), + dialyzer_plt:restore_full_plt(MiniPlt, Plt), + dialyzer_plt:restore_full_plt(MiniDocPlt, DocPlt)}. + +get_warnings_from_modules(Mods, State, DocPlt) -> #st{callgraph = Callgraph, codeserver = Codeserver, - no_warn_unused = NoWarnUnused, plt = Plt} = State, + no_warn_unused = NoWarnUnused, plt = Plt, + timing_server = TimingServer} = State, + Init = {Codeserver, Callgraph, NoWarnUnused, Plt, DocPlt}, + dialyzer_coordinator:parallel_job(warnings, Mods, Init, TimingServer). + +-spec collect_warnings(module(), warnings_init_data()) -> [dial_warning()]. + +collect_warnings(M, {Codeserver, Callgraph, NoWarnUnused, Plt, DocPlt}) -> ModCode = dialyzer_codeserver:lookup_mod_code(M, Codeserver), Records = dialyzer_codeserver:lookup_mod_records(M, Codeserver), Contracts = dialyzer_codeserver:lookup_mod_contracts(M, Codeserver), @@ -129,28 +176,27 @@ get_warnings_from_modules([M|Ms], State, DocPlt, Acc) when is_atom(M) -> %% Check if there are contracts for functions that do not exist Warnings1 = dialyzer_contracts:contracts_without_fun(Contracts, AllFuns, Callgraph), - {RawWarnings2, FunTypes, RaceCode, PublicTables, NamedTables} = - dialyzer_dataflow:get_warnings(ModCode, Plt, Callgraph, Records, NoWarnUnused), - {NewAcc, Warnings2} = postprocess_dataflow_warns(RawWarnings2, State, Acc), + {Warnings2, FunTypes} = + dialyzer_dataflow:get_warnings(ModCode, Plt, Callgraph, + Records, NoWarnUnused), Attrs = cerl:module_attrs(ModCode), - Warnings3 = dialyzer_behaviours:check_callbacks(M, Attrs, Plt, Codeserver), - NewDocPlt = insert_into_doc_plt(FunTypes, Callgraph, DocPlt), - NewCallgraph = - dialyzer_callgraph:renew_race_info(Callgraph, RaceCode, PublicTables, - NamedTables), - State1 = st__renew_state_calls(NewCallgraph, State), - get_warnings_from_modules(Ms, State1, NewDocPlt, - [Warnings1, Warnings2, Warnings3|NewAcc]); -get_warnings_from_modules([], #st{plt = Plt}, DocPlt, Acc) -> - {lists:flatten(Acc), Plt, DocPlt}. - -postprocess_dataflow_warns(RawWarnings, State, WarnAcc) -> - postprocess_dataflow_warns(RawWarnings, State, WarnAcc, []). - -postprocess_dataflow_warns([], _State, WAcc, Acc) -> - {WAcc, lists:reverse(Acc)}; + Warnings3 = + dialyzer_behaviours:check_callbacks(M, Attrs, Records, Plt, Codeserver), + DocPlt = insert_into_doc_plt(FunTypes, Callgraph, DocPlt), + lists:flatten([Warnings1, Warnings2, Warnings3]). + +postprocess_warnings(RawWarnings, Codeserver) -> + Pred = + fun({?WARN_CONTRACT_RANGE, _, _}) -> true; + (_) -> false + end, + {CRWarns, NonCRWarns} = lists:partition(Pred, RawWarnings), + postprocess_dataflow_warns(CRWarns, Codeserver, NonCRWarns, []). + +postprocess_dataflow_warns([], _Callgraph, WAcc, Acc) -> + lists:reverse(Acc, WAcc); postprocess_dataflow_warns([{?WARN_CONTRACT_RANGE, {CallF, CallL}, Msg}|Rest], - #st{codeserver = Codeserver} = State, WAcc, Acc) -> + Codeserver, WAcc, Acc) -> {contract_range, [Contract, M, F, A, ArgStrings, CRet]} = Msg, case dialyzer_codeserver:lookup_mfa_contract({M,F,A}, Codeserver) of {ok, {{ContrF, _ContrL} = FileLine, _C}} -> @@ -163,87 +209,66 @@ postprocess_dataflow_warns([{?WARN_CONTRACT_RANGE, {CallF, CallL}, Msg}|Rest], (_) -> true end, FilterWAcc = lists:filter(Filter, WAcc), - postprocess_dataflow_warns(Rest, State, FilterWAcc, [W|Acc]); + postprocess_dataflow_warns(Rest, Codeserver, FilterWAcc, [W|Acc]); false -> - postprocess_dataflow_warns(Rest, State, WAcc, Acc) + postprocess_dataflow_warns(Rest, Codeserver, WAcc, Acc) end; error -> %% The contract is not in a module that is currently under analysis. %% We display the warning in the file/line of the call. NewMsg = {contract_range, [Contract, M, F, ArgStrings, CallL, CRet]}, W = {?WARN_CONTRACT_RANGE, {CallF, CallL}, NewMsg}, - postprocess_dataflow_warns(Rest, State, WAcc, [W|Acc]) - end; -postprocess_dataflow_warns([W|Rest], State, Wacc, Acc) -> - postprocess_dataflow_warns(Rest, State, Wacc, [W|Acc]). + postprocess_dataflow_warns(Rest, Codeserver, WAcc, [W|Acc]) + end. -refine_succ_typings(ModulePostorder, State) -> - ?debug("Module postorder: ~p\n", [ModulePostorder]), - refine_succ_typings(ModulePostorder, State, []). - -refine_succ_typings([SCC|SCCs], State, Fixpoint) -> - Msg = io_lib:format("Dataflow of one SCC: ~w\n", [SCC]), - send_log(State#st.parent, Msg), - ?debug("~s\n", [Msg]), - {NewState, FixpointFromScc} = - case SCC of - [M] -> refine_one_module(M, State); - [_|_] -> refine_one_scc(SCC, State) - end, - NewFixpoint = ordsets:union(Fixpoint, FixpointFromScc), - refine_succ_typings(SCCs, NewState, NewFixpoint); -refine_succ_typings([], State, Fixpoint) -> - case Fixpoint =:= [] of +refine_succ_typings(Modules, #st{codeserver = Codeserver, + callgraph = Callgraph, + plt = Plt, + timing_server = Timing, + solvers = Solvers} = State) -> + ?debug("Module postorder: ~p\n", [Modules]), + Init = {Codeserver, Callgraph, Plt, Solvers}, + NotFixpoint = + ?timing(Timing, "refine", + dialyzer_coordinator:parallel_job(dataflow, Modules, Init, Timing)), + ?debug("==================== Dataflow done ====================\n\n", []), + case NotFixpoint =:= [] of true -> {fixpoint, State}; - false -> {not_fixpoint, Fixpoint, State} + false -> {not_fixpoint, NotFixpoint, State} end. --spec refine_one_module(module(), #st{}) -> {#st{}, [label()]}. % ordset +-spec find_depends_on(scc() | module(), fixpoint_init_data()) -> [scc()]. -refine_one_module(M, State) -> - #st{callgraph = Callgraph, codeserver = CodeServer, plt = PLT} = State, +find_depends_on(SCC, {_Codeserver, Callgraph, _Plt, _Solvers}) -> + dialyzer_callgraph:get_depends_on(SCC, Callgraph). + +-spec find_required_by(scc() | module(), fixpoint_init_data()) -> [scc()]. + +find_required_by(SCC, {_Codeserver, Callgraph, _Plt, _Solvers}) -> + dialyzer_callgraph:get_required_by(SCC, Callgraph). + +-spec lookup_names([label()], fixpoint_init_data()) -> [mfa_or_funlbl()]. + +lookup_names(Labels, {_Codeserver, Callgraph, _Plt, _Solvers}) -> + [lookup_name(F, Callgraph) || F <- Labels]. + +-spec refine_one_module(module(), dataflow_init_data()) -> [label()]. % ordset + +refine_one_module(M, {CodeServer, Callgraph, Plt, _Solvers}) -> ModCode = dialyzer_codeserver:lookup_mod_code(M, CodeServer), AllFuns = collect_fun_info([ModCode]), - FunTypes = get_fun_types_from_plt(AllFuns, Callgraph, PLT), Records = dialyzer_codeserver:lookup_mod_records(M, CodeServer), - {NewFunTypes, RaceCode, PublicTables, NamedTables} = - dialyzer_dataflow:get_fun_types(ModCode, PLT, Callgraph, Records), - NewCallgraph = - dialyzer_callgraph:renew_race_info(Callgraph, RaceCode, PublicTables, - NamedTables), + FunTypes = get_fun_types_from_plt(AllFuns, Callgraph, Plt), + NewFunTypes = + dialyzer_dataflow:get_fun_types(ModCode, Plt, Callgraph, Records), case reached_fixpoint(FunTypes, NewFunTypes) of - true -> - State1 = st__renew_state_calls(NewCallgraph, State), - {State1, ordsets:new()}; + true -> []; {false, NotFixpoint} -> ?debug("Not fixpoint\n", []), - NewState = insert_into_plt(dict:from_list(NotFixpoint), State), - NewState1 = st__renew_state_calls(NewCallgraph, NewState), - {NewState1, ordsets:from_list([FunLbl || {FunLbl,_Type} <- NotFixpoint])} + Plt = insert_into_plt(dict:from_list(NotFixpoint), Callgraph, Plt), + [FunLbl || {FunLbl,_Type} <- NotFixpoint] end. -st__renew_state_calls(Callgraph, State) -> - State#st{callgraph = Callgraph}. - -refine_one_scc(SCC, State) -> - refine_one_scc(SCC, State, []). - -refine_one_scc(SCC, State, AccFixpoint) -> - {NewState, FixpointFromScc} = refine_mods_in_scc(SCC, State, []), - case FixpointFromScc =:= [] of - true -> {NewState, AccFixpoint}; - false -> - NewAccFixpoint = ordsets:union(AccFixpoint, FixpointFromScc), - refine_one_scc(SCC, NewState, NewAccFixpoint) - end. - -refine_mods_in_scc([Mod|Mods], State, Fixpoint) -> - {NewState, FixpointFromModule} = refine_one_module(Mod, State), - NewFixpoint = ordsets:union(FixpointFromModule, Fixpoint), - refine_mods_in_scc(Mods, NewState, NewFixpoint); -refine_mods_in_scc([], State, Fixpoint) -> - {State, Fixpoint}. - reached_fixpoint(OldTypes, NewTypes) -> reached_fixpoint(OldTypes, NewTypes, false). @@ -299,31 +324,22 @@ compare_types_1([], [], _Strict, NotFixpoint) -> false -> {false, NotFixpoint} end. -find_succ_typings(State) -> - find_succ_typings(State, []). - -find_succ_typings(#st{callgraph = Callgraph, parent = Parent} = State, - NotFixpoint) -> - case dialyzer_callgraph:take_scc(Callgraph) of - {ok, SCC, NewCallgraph} -> - Msg = io_lib:format("Typesig analysis for SCC: ~w\n", [format_scc(SCC)]), - ?debug("~s", [Msg]), - send_log(Parent, Msg), - {NewState, NewNotFixpoint1} = - analyze_scc(SCC, State#st{callgraph = NewCallgraph}), - NewNotFixpoint2 = ordsets:union(NewNotFixpoint1, NotFixpoint), - find_succ_typings(NewState, NewNotFixpoint2); - none -> - ?debug("==================== Typesig done ====================\n\n", []), - case NotFixpoint =:= [] of - true -> {fixpoint, State}; - false -> {not_fixpoint, NotFixpoint, State} - end +find_succ_typings(SCCs, #st{codeserver = Codeserver, callgraph = Callgraph, + plt = Plt, timing_server = Timing, + solvers = Solvers} = State) -> + Init = {Codeserver, Callgraph, Plt, Solvers}, + NotFixpoint = + ?timing(Timing, "typesig", + dialyzer_coordinator:parallel_job(typesig, SCCs, Init, Timing)), + ?debug("==================== Typesig done ====================\n\n", []), + case NotFixpoint =:= [] of + true -> {fixpoint, State}; + false -> {not_fixpoint, NotFixpoint, State} end. -analyze_scc(SCC, #st{codeserver = Codeserver, - callgraph = Callgraph, - plt = Plt} = State) -> +-spec find_succ_types_for_scc(scc(), typesig_init_data()) -> [mfa_or_funlbl()]. + +find_succ_types_for_scc(SCC, {Codeserver, Callgraph, Plt, Solvers}) -> SCC_Info = [{MFA, dialyzer_codeserver:lookup_mfa_code(MFA, Codeserver), dialyzer_codeserver:lookup_mod_records(M, Codeserver)} @@ -332,26 +348,18 @@ analyze_scc(SCC, #st{codeserver = Codeserver, || {_, _, _} = MFA <- SCC], Contracts2 = [{MFA, Contract} || {MFA, {ok, Contract}} <- Contracts1], Contracts3 = orddict:from_list(Contracts2), - NextLabel = dialyzer_codeserver:get_next_core_label(Codeserver), - {SuccTypes, PltContracts, NotFixpoint} = - find_succ_types_for_scc(SCC_Info, Contracts3, NextLabel, Callgraph, Plt), - State1 = insert_into_plt(SuccTypes, State), - ContrPlt = dialyzer_plt:insert_contract_list(State1#st.plt, PltContracts), - {State1#st{plt = ContrPlt}, NotFixpoint}. - -find_succ_types_for_scc(SCC_Info, Contracts, NextLabel, Callgraph, Plt) -> - %% Assume that the PLT contains the current propagated types + Label = dialyzer_codeserver:get_next_core_label(Codeserver), AllFuns = collect_fun_info([Fun || {_MFA, {_Var, Fun}, _Rec} <- SCC_Info]), PropTypes = get_fun_types_from_plt(AllFuns, Callgraph, Plt), - FunTypes = dialyzer_typesig:analyze_scc(SCC_Info, NextLabel, - Callgraph, Plt, PropTypes), + %% Assume that the PLT contains the current propagated types + FunTypes = dialyzer_typesig:analyze_scc(SCC_Info, Label, Callgraph, + Plt, PropTypes, Solvers), AllFunSet = sets:from_list([X || {X, _} <- AllFuns]), - FilteredFunTypes = dict:filter(fun(X, _) -> - sets:is_element(X, AllFunSet) - end, FunTypes), + FilteredFunTypes = + dict:filter(fun(X, _) -> sets:is_element(X, AllFunSet) end, FunTypes), %% Check contracts - PltContracts = dialyzer_contracts:check_contracts(Contracts, Callgraph, - FilteredFunTypes), + PltContracts = + dialyzer_contracts:check_contracts(Contracts3, Callgraph, FilteredFunTypes), ContractFixpoint = lists:all(fun({MFA, _C}) -> %% Check the non-deleted PLT @@ -360,14 +368,14 @@ find_succ_types_for_scc(SCC_Info, Contracts, NextLabel, Callgraph, Plt) -> {value, _} -> true end end, PltContracts), + Plt = insert_into_plt(FilteredFunTypes, Callgraph, Plt), + Plt = dialyzer_plt:insert_contract_list(Plt, PltContracts), case (ContractFixpoint andalso reached_fixpoint_strict(PropTypes, FilteredFunTypes)) of - true -> - {FilteredFunTypes, PltContracts, []}; + true -> []; false -> ?debug("Not fixpoint for: ~w\n", [AllFuns]), - {FilteredFunTypes, PltContracts, - ordsets:from_list([Fun || {Fun, _Arity} <- AllFuns])} + [Fun || {Fun, _Arity} <- AllFuns] end. get_fun_types_from_plt(FunList, Callgraph, Plt) -> @@ -407,10 +415,10 @@ insert_into_doc_plt(FunTypes, Callgraph, DocPlt) -> SuccTypes = format_succ_types(FunTypes, Callgraph), dialyzer_plt:insert_list(DocPlt, SuccTypes). -insert_into_plt(SuccTypes0, #st{callgraph = Callgraph, plt = Plt} = State) -> +insert_into_plt(SuccTypes0, Callgraph, Plt) -> SuccTypes = format_succ_types(SuccTypes0, Callgraph), debug_pp_succ_typings(SuccTypes), - State#st{plt = dialyzer_plt:insert_list(Plt, SuccTypes)}. + dialyzer_plt:insert_list(Plt, SuccTypes). format_succ_types(SuccTypes, Callgraph) -> format_succ_types(dict:to_list(SuccTypes), Callgraph, []). @@ -445,131 +453,3 @@ lookup_name(F, CG) -> error -> F; {ok, Name} -> Name end. - -send_log(none, _Msg) -> - ok; -send_log(Parent, Msg) -> - Parent ! {self(), log, lists:flatten(Msg)}, - ok. - -format_scc(SCC) -> - [MFA || {_M, _F, _A} = MFA <- SCC]. - -%% ============================================================================ -%% -%% Debug interface. -%% -%% ============================================================================ - --spec doit(atom() | file:filename()) -> 'ok'. - -doit(Module) -> - {ok, AbstrCode} = dialyzer_utils:get_abstract_code_from_src(Module), - {ok, Code} = dialyzer_utils:get_core_from_abstract_code(AbstrCode), - {ok, Records} = dialyzer_utils:get_record_and_type_info(AbstrCode), - %% contract typing info in dictionary format - {ok, Contracts, _Callbacks} = - dialyzer_utils:get_spec_info(cerl:concrete(cerl:module_name(Code)), - AbstrCode, Records), - Sigs0 = get_top_level_signatures(Code, Records, Contracts), - M = if is_atom(Module) -> - list_to_atom(filename:basename(atom_to_list(Module))); - is_list(Module) -> - list_to_atom(filename:basename(Module)) - end, - Sigs1 = [{{M, F, A}, Type} || {{F, A}, Type} <- Sigs0], - Sigs = ordsets:from_list(Sigs1), - io:format("==================== Final result ====================\n\n", []), - pp_signatures(Sigs, Records), - ok. - --spec get_top_level_signatures(cerl:c_module(), dict(), dict()) -> - [{{atom(), arity()}, erl_types:erl_type()}]. - -get_top_level_signatures(Code, Records, Contracts) -> - Tree = cerl:from_records(Code), - {LabeledTree, NextLabel} = cerl_trees:label(Tree), - Plt = get_def_plt(), - ModuleName = cerl:atom_val(cerl:module_name(LabeledTree)), - Plt1 = dialyzer_plt:delete_module(Plt, ModuleName), - Plt2 = analyze_module(LabeledTree, NextLabel, Plt1, Records, Contracts), - M = cerl:concrete(cerl:module_name(Tree)), - Functions = [{M, cerl:fname_id(V), cerl:fname_arity(V)} - || {V, _F} <- cerl:module_defs(LabeledTree)], - %% First contracts check - AllContracts = dict:fetch_keys(Contracts), - ErrorContracts = AllContracts -- Functions, - lists:foreach(fun(C) -> - io:format("Contract for non-existing function: ~w\n",[C]) - end, ErrorContracts), - Types = [{MFA, dialyzer_plt:lookup(Plt2, MFA)} || MFA <- Functions], - Sigs = [{{F, A}, erl_types:t_fun(ArgT, RetT)} - || {{_M, F, A}, {value, {RetT, ArgT}}} <- Types], - ordsets:from_list(Sigs). - -get_def_plt() -> - try - dialyzer_plt:from_file(dialyzer_plt:get_default_plt()) - catch - error:no_such_file -> dialyzer_plt:new(); - throw:{dialyzer_error, _} -> dialyzer_plt:new() - end. - -pp_signatures([{{_, module_info, 0}, _}|Left], Records) -> - pp_signatures(Left, Records); -pp_signatures([{{_, module_info, 1}, _}|Left], Records) -> - pp_signatures(Left, Records); -pp_signatures([{{M, F, _A}, Type}|Left], Records) -> - TypeString = - case cerl:is_literal(Type) of -%% Commented out so that dialyzer does not complain -%% false -> -%% "fun(" ++ String = erl_types:t_to_string(Type, Records), -%% string:substr(String, 1, length(String)-1); - true -> - io_lib:format("~w", [cerl:concrete(Type)]) - end, - io:format("~w:~w~s\n", [M, F, TypeString]), - pp_signatures(Left, Records); -pp_signatures([], _Records) -> - ok. - --ifdef(DEBUG_PP). -debug_pp(Tree, _Map) -> - Tree1 = strip_annotations(Tree), - io:put_chars(cerl_prettypr:format(Tree1)), - io:nl(). - -strip_annotations(Tree) -> - cerl_trees:map(fun(T) -> - case cerl:is_literal(T) orelse cerl:is_c_values(T) of - true -> cerl:set_ann(T, []); - false -> - Label = cerl_trees:get_label(T), - cerl:set_ann(T, [{'label', Label}]) - end - end, Tree). --else. -debug_pp(_Tree, _Map) -> - ok. --endif. % DEBUG_PP - -%% -%% Analysis of a single module -%% -analyze_module(LabeledTree, NextLbl, Plt, Records, Contracts) -> - debug_pp(LabeledTree, dict:new()), - CallGraph1 = dialyzer_callgraph:new(), - CallGraph2 = dialyzer_callgraph:scan_core_tree(LabeledTree, CallGraph1), - {CallGraph3, _Ext} = dialyzer_callgraph:remove_external(CallGraph2), - CallGraph4 = dialyzer_callgraph:finalize(CallGraph3), - CodeServer1 = dialyzer_codeserver:new(), - Mod = cerl:concrete(cerl:module_name(LabeledTree)), - CodeServer2 = dialyzer_codeserver:insert(Mod, LabeledTree, CodeServer1), - CodeServer3 = dialyzer_codeserver:set_next_core_label(NextLbl, CodeServer2), - CodeServer4 = dialyzer_codeserver:store_records(Mod, Records, CodeServer3), - CodeServer5 = dialyzer_codeserver:store_contracts(Mod, Contracts, CodeServer4), - Res = analyze_callgraph(CallGraph4, Plt, CodeServer5), - dialyzer_callgraph:delete(CallGraph4), - dialyzer_codeserver:delete(CodeServer5), - Res. diff --git a/lib/dialyzer/src/dialyzer_timing.erl b/lib/dialyzer/src/dialyzer_timing.erl new file mode 100644 index 0000000000..b1a4bdc07c --- /dev/null +++ b/lib/dialyzer/src/dialyzer_timing.erl @@ -0,0 +1,133 @@ +%% -*- erlang-indent-level: 2 -*- +%%------------------------------------------------------------------- +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2006-2012. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +%%%------------------------------------------------------------------- +%%% File : dialyzer_timing.erl +%%% Authors : Stavros Aronis <[email protected]> +%%% Description : Timing reports for Dialyzer +%%%------------------------------------------------------------------- + +-module(dialyzer_timing). + +-export([init/1, start_stamp/2, send_size_info/3, end_stamp/1, stop/1]). + +-export_type([timing_server/0]). + +-type timing_server() :: pid() | 'none'. + +-spec init(boolean() | 'debug') -> timing_server(). + +init(Active) -> + case Active of + true -> + io:format("\n"), + spawn_link(fun() -> loop(now(), 0, "") end); + debug -> + io:format("\n"), + spawn_link(fun() -> debug_loop("") end); + false -> none + end. + +loop(LastNow, Size, Unit) -> + receive + {stamp, Msg, Now} -> + io:format(" ~-10s (+~4.2fs):", [Msg, diff(Now, LastNow)]), + loop(Now, 0, ""); + {stamp, Now} -> + SizeStr = + case Size of + 0 -> ""; + _ -> + Data = io_lib:format("~p ~s",[Size, Unit]), + io_lib:format(" (~12s)",[Data]) + end, + io:format("~7.2fs~s\n", [diff(Now, LastNow), SizeStr]), + loop(Now, 0, ""); + {size, NewSize, NewUnit} -> + loop(LastNow, NewSize, NewUnit); + {Pid, stop, Now} -> + io:format(" ~-9s (+~5.2fs)\n", ["",diff(Now, LastNow)]), + Pid ! ok; + {Pid, stop} -> + Pid ! ok + end. + +debug_loop(Phase) -> + receive + Message -> + {Runtime,_} = statistics(wall_clock), + Procs = erlang:system_info(process_count), + ProcMem = erlang:memory(total), + Status = io_lib:format("~12w ~6w ~20w", [Runtime, Procs, ProcMem]), + case Message of + {stamp, Msg, _Now} -> + io:format("~s ~s_start\n", [Status, Msg]), + debug_loop(Msg); + {stamp, _Now} -> + io:format("~s ~s_stop\n", [Status, Phase]), + debug_loop(""); + {Pid, stop, _Now} -> + Pid ! ok; + {Pid, stop} -> + Pid ! ok; + _ -> + debug_loop(Phase) + end + after + 50 -> + {Runtime,_} = statistics(wall_clock), + Procs = erlang:system_info(process_count), + ProcMem = erlang:memory(total), + Status = io_lib:format("~12w ~6w ~20w", [Runtime, Procs, ProcMem]), + io:format("~s\n", [Status]), + debug_loop(Phase) + end. + + +-spec start_stamp(timing_server(), string()) -> ok. + +start_stamp(none, _) -> ok; +start_stamp(Pid, Msg) -> + Pid ! {stamp, Msg, now()}, + ok. + +-spec end_stamp(timing_server()) -> ok. + +end_stamp(none) -> ok; +end_stamp(Pid) -> + Pid ! {stamp, now()}, + ok. + +-spec send_size_info(timing_server(), integer(), string()) -> ok. + +send_size_info(none, _, _) -> ok; +send_size_info(Pid, Size, Unit) -> + Pid ! {size, Size, Unit}, + ok. + +-spec stop(timing_server()) -> ok. + +stop(none) -> ok; +stop(Pid) -> + Pid ! {self(), stop, now()}, + receive ok -> ok end. + +diff(T2, T1) -> + timer:now_diff(T2,T1) / 1000000. 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. diff --git a/lib/dialyzer/src/dialyzer_utils.erl b/lib/dialyzer/src/dialyzer_utils.erl index 2a248fb028..149e777e1f 100644 --- a/lib/dialyzer/src/dialyzer_utils.erl +++ b/lib/dialyzer/src/dialyzer_utils.erl @@ -43,7 +43,8 @@ pp_hook/0, process_record_remote_types/1, sets_filter/2, - src_compiler_opts/0 + src_compiler_opts/0, + parallelism/0 ]). -include("dialyzer.hrl"). @@ -536,3 +537,12 @@ pp_unit(Unit, Ctxt, Cont) -> pp_atom(Atom) -> String = atom_to_list(cerl:atom_val(Atom)), prettypr:text(String). + +%%------------------------------------------------------------------------------ + +-spec parallelism() -> integer(). + +parallelism() -> + CPUs = erlang:system_info(logical_processors_available), + Schedulers = erlang:system_info(schedulers), + min(CPUs, Schedulers). diff --git a/lib/dialyzer/src/dialyzer_worker.erl b/lib/dialyzer/src/dialyzer_worker.erl new file mode 100644 index 0000000000..50b2e31ed8 --- /dev/null +++ b/lib/dialyzer/src/dialyzer_worker.erl @@ -0,0 +1,189 @@ +%% -*- erlang-indent-level: 2 -*- +%%----------------------------------------------------------------------- +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2006-2010. All Rights Reserved. +%% +%% The contents of this file are subject to the Erlang Public License, +%% Version 1.1, (the "License"); you may not use this file except in +%% compliance with the License. You should have received a copy of the +%% Erlang Public License along with this software. If not, it can be +%% retrieved online at http://www.erlang.org/. +%% +%% Software distributed under the License is distributed on an "AS IS" +%% basis, WITHOUT WARRANTY OF ANY KIND, either express or implied. See +%% the License for the specific language governing rights and limitations +%% under the License. +%% +%% %CopyrightEnd% +%% + +-module(dialyzer_worker). + +-export([launch/4, sequential/4]). + +-export_type([worker/0]). + +-type worker() :: pid(). %%opaque + +-type mode() :: dialyzer_coordinator:mode(). +-type coordinator() :: dialyzer_coordinator:coordinator(). +-type init_data() :: dialyzer_coordinator:init_data(). +-type result() :: dialyzer_coordinator:result(). + +-record(state, { + mode :: mode(), + job :: mfa_or_funlbl() | file:filename(), + coordinator :: coordinator(), + init_data :: init_data(), + depends_on = [] :: list() + }). + +-include("dialyzer.hrl"). + +%% -define(DEBUG, true). + +-ifdef(DEBUG). +-define(debug(X__, Y__), io:format(X__, Y__)). +-else. +-define(debug(X__, Y__), ok). +-endif. + +%%-------------------------------------------------------------------- + +-spec launch(mode(), [mfa_or_funlbl()], init_data(), coordinator()) -> worker(). + +launch(Mode, Job, InitData, Coordinator) -> + State = #state{mode = Mode, + job = Job, + init_data = InitData, + coordinator = Coordinator}, + InitState = + case Mode of + X when X =:= 'typesig'; X =:= 'dataflow' -> initializing; + X when X =:= 'compile'; X =:= 'warnings' -> running + end, + spawn_link(fun() -> loop(InitState, State) end). + +%%-------------------------------------------------------------------- + +loop(updating, State) -> + ?debug("Update: ~p\n",[State#state.job]), + NextStatus = + case waits_more_success_typings(State) of + true -> waiting; + false -> running + end, + loop(NextStatus, State); +loop(initializing, #state{job = SCC, init_data = InitData} = State) -> + DependsOn = dialyzer_succ_typings:find_depends_on(SCC, InitData), + ?debug("Deps ~p: ~p\n",[State#state.job, DependsOn]), + loop(updating, State#state{depends_on = DependsOn}); +loop(waiting, State) -> + ?debug("Wait: ~p\n",[State#state.job]), + NewState = wait_for_success_typings(State), + loop(updating, NewState); +loop(running, #state{mode = 'compile'} = State) -> + dialyzer_coordinator:wait_activation(), + ?debug("Compile: ~s\n",[State#state.job]), + Result = + case start_compilation(State) of + {ok, EstimatedSize, Data} -> + Label = ask_coordinator_for_label(EstimatedSize, State), + continue_compilation(Label, Data); + {error, _Reason} = Error -> + Error + end, + report_to_coordinator(Result, State); +loop(running, #state{mode = 'warnings'} = State) -> + dialyzer_coordinator:wait_activation(), + ?debug("Warning: ~s\n",[State#state.job]), + Result = collect_warnings(State), + report_to_coordinator(Result, State); +loop(running, #state{mode = Mode} = State) when + Mode =:= 'typesig'; Mode =:= 'dataflow' -> + request_activation(State), + ?debug("Run: ~p\n",[State#state.job]), + NotFixpoint = do_work(State), + ok = broadcast_done(State), + report_to_coordinator(NotFixpoint, State). + +waits_more_success_typings(#state{depends_on = Depends}) -> + Depends =/= []. + +broadcast_done(#state{job = SCC, init_data = InitData, + coordinator = Coordinator}) -> + RequiredBy = dialyzer_succ_typings:find_required_by(SCC, InitData), + {Callers, Unknown} = + dialyzer_coordinator:sccs_to_pids(RequiredBy, Coordinator), + send_done(Callers, SCC), + continue_broadcast_done(Unknown, SCC, Coordinator). + +send_done(Callers, SCC) -> + ?debug("Sending ~p: ~p\n",[SCC, Callers]), + SendSTFun = fun(PID) -> PID ! {done, SCC} end, + lists:foreach(SendSTFun, Callers). + +continue_broadcast_done([], _SCC, _Coordinator) -> ok; +continue_broadcast_done(Rest, SCC, Coordinator) -> + %% This time limit should be greater than the time required + %% by the coordinator to spawn all processes. + timer:sleep(500), + {Callers, Unknown} = dialyzer_coordinator:sccs_to_pids(Rest, Coordinator), + send_done(Callers, SCC), + continue_broadcast_done(Unknown, SCC, Coordinator). + +wait_for_success_typings(#state{depends_on = DependsOn} = State) -> + receive + {done, SCC} -> + ?debug("GOT ~p: ~p\n",[State#state.job, SCC]), + State#state{depends_on = DependsOn -- [SCC]} + after + 5000 -> + ?debug("Still Waiting ~p: ~p\n",[State#state.job, DependsOn]), + State + end. + +request_activation(#state{coordinator = Coordinator}) -> + dialyzer_coordinator:request_activation(Coordinator). + +do_work(#state{mode = Mode, job = Job, init_data = InitData}) -> + case Mode of + typesig -> dialyzer_succ_typings:find_succ_types_for_scc(Job, InitData); + dataflow -> dialyzer_succ_typings:refine_one_module(Job, InitData) + end. + +report_to_coordinator(Result, #state{job = Job, coordinator = Coordinator}) -> + ?debug("Done: ~p\n",[Job]), + dialyzer_coordinator:job_done(Job, Result, Coordinator). + +start_compilation(#state{job = Job, init_data = InitData}) -> + dialyzer_analysis_callgraph:start_compilation(Job, InitData). + +ask_coordinator_for_label(EstimatedSize, #state{coordinator = Coordinator}) -> + dialyzer_coordinator:get_next_label(EstimatedSize, Coordinator). + +continue_compilation(Label, Data) -> + dialyzer_analysis_callgraph:continue_compilation(Label, Data). + +collect_warnings(#state{job = Job, init_data = InitData}) -> + dialyzer_succ_typings:collect_warnings(Job, InitData). + +%%------------------------------------------------------------------------------ + +-type extra() :: label() | 'unused'. + +-spec sequential(mode(), [mfa_or_funlbl()], init_data(), extra()) -> result(). + +sequential('compile', Job, InitData, Extra) -> + case dialyzer_analysis_callgraph:start_compilation(Job, InitData) of + {ok, EstimatedSize, Data} -> + {EstimatedSize, continue_compilation(Extra, Data)}; + {error, _Reason} = Error -> {0, Error} + end; +sequential('typesig', Job, InitData, _Extra) -> + dialyzer_succ_typings:find_succ_types_for_scc(Job, InitData); +sequential('dataflow', Job, InitData, _Extra) -> + dialyzer_succ_typings:refine_one_module(Job, InitData); +sequential('warnings', Job, InitData, _Extra) -> + dialyzer_succ_typings:collect_warnings(Job, InitData). diff --git a/lib/dialyzer/test/Makefile b/lib/dialyzer/test/Makefile index 6a1abce943..9f8a3f1194 100644 --- a/lib/dialyzer/test/Makefile +++ b/lib/dialyzer/test/Makefile @@ -25,10 +25,10 @@ RELSYSDIR = $(RELEASE_PATH)/dialyzer_test include $(ERL_TOP)/make/otp_release_targets.mk release_tests_spec: - $(INSTALL_DIR) $(RELSYSDIR) - chmod -R u+w $(RELSYSDIR) - $(INSTALL_DATA) $(AUXILIARY_FILES) $(RELSYSDIR) - @tar cf - *_SUITE_data | (cd $(RELSYSDIR); tar xf -) - cd $(RELSYSDIR);\ + $(INSTALL_DIR) "$(RELSYSDIR)" + chmod -R u+w "$(RELSYSDIR)" + $(INSTALL_DATA) $(AUXILIARY_FILES) "$(RELSYSDIR)" + @tar cf - *_SUITE_data | (cd "$(RELSYSDIR)"; tar xf -) + cd "$(RELSYSDIR)";\ erlc dialyzer_common.erl file_utils.erl;\ erl -noshell -run dialyzer_common create_all_suites -s erlang halt diff --git a/lib/dialyzer/test/opaque_SUITE_data/results/queue b/lib/dialyzer/test/opaque_SUITE_data/results/queue index 59ce33f098..c3f04ea64d 100644 --- a/lib/dialyzer/test/opaque_SUITE_data/results/queue +++ b/lib/dialyzer/test/opaque_SUITE_data/results/queue @@ -5,6 +5,7 @@ queue_use.erl:27: The attempt to match a term of type queue() against the patter queue_use.erl:33: Attempt to test for equality between a term of type {[42,...],[]} and a term of opaque type queue() queue_use.erl:36: The attempt to match a term of type queue() against the pattern {F, _R} breaks the opaqueness of the term queue_use.erl:40: The call queue:out({[42,...],[]}) does not have an opaque term of type queue() as 1st argument +queue_use.erl:48: The call queue_use:add_unique(42,#db{p::[],q::queue()}) contains an opaque term as 2nd argument when terms of different types are expected in these positions queue_use.erl:51: The call queue_use:is_in_queue(E::42,DB::#db{p::[],q::queue()}) contains an opaque term as 2nd argument when terms of different types are expected in these positions queue_use.erl:56: The attempt to match a term of type #db{p::[],q::queue()} against the pattern {'db', _, {L1, L2}} breaks the opaqueness of queue() queue_use.erl:62: The call queue_use:tuple_queue({42,'gazonk'}) does not have a term of type {_,queue()} (with opaque subterms) as 1st argument diff --git a/lib/dialyzer/test/small_SUITE_data/results/contracts_with_subtypes b/lib/dialyzer/test/small_SUITE_data/results/contracts_with_subtypes new file mode 100644 index 0000000000..8dc0361b0d --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/results/contracts_with_subtypes @@ -0,0 +1,31 @@ + +contracts_with_subtypes.erl:106: The call contracts_with_subtypes:rec_arg({'a','b'}) breaks the contract (Arg) -> 'ok' when is_subtype(Arg,{'a',A} | {'b',B}), is_subtype(A,'a' | {'b',B}), is_subtype(B,'b' | {'a',A}) +contracts_with_subtypes.erl:107: The call contracts_with_subtypes:rec_arg({'b','a'}) breaks the contract (Arg) -> 'ok' when is_subtype(Arg,{'a',A} | {'b',B}), is_subtype(A,'a' | {'b',B}), is_subtype(B,'b' | {'a',A}) +contracts_with_subtypes.erl:108: The call contracts_with_subtypes:rec_arg({'a',{'b','a'}}) breaks the contract (Arg) -> 'ok' when is_subtype(Arg,{'a',A} | {'b',B}), is_subtype(A,'a' | {'b',B}), is_subtype(B,'b' | {'a',A}) +contracts_with_subtypes.erl:109: The call contracts_with_subtypes:rec_arg({'b',{'a','b'}}) breaks the contract (Arg) -> 'ok' when is_subtype(Arg,{'a',A} | {'b',B}), is_subtype(A,'a' | {'b',B}), is_subtype(B,'b' | {'a',A}) +contracts_with_subtypes.erl:110: The call contracts_with_subtypes:rec_arg({'a',{'b',{'a','b'}}}) breaks the contract (Arg) -> 'ok' when is_subtype(Arg,{'a',A} | {'b',B}), is_subtype(A,'a' | {'b',B}), is_subtype(B,'b' | {'a',A}) +contracts_with_subtypes.erl:111: The call contracts_with_subtypes:rec_arg({'b',{'a',{'b','a'}}}) breaks the contract (Arg) -> 'ok' when is_subtype(Arg,{'a',A} | {'b',B}), is_subtype(A,'a' | {'b',B}), is_subtype(B,'b' | {'a',A}) +contracts_with_subtypes.erl:142: The pattern 1 can never match the type binary() | string() +contracts_with_subtypes.erl:145: The pattern 'alpha' can never match the type {'ok',X} | {'ok',X,binary() | string()} +contracts_with_subtypes.erl:147: The pattern 42 can never match the type {'ok',_} | {'ok',_,binary() | string()} +contracts_with_subtypes.erl:163: The pattern 'alpha' can never match the type {'ok',X} +contracts_with_subtypes.erl:165: The pattern 42 can never match the type {'ok',X} +contracts_with_subtypes.erl:183: The pattern 'alpha' can never match the type {'ok',X} +contracts_with_subtypes.erl:185: The pattern 42 can never match the type {'ok',X} +contracts_with_subtypes.erl:202: The pattern 1 can never match the type binary() | string() +contracts_with_subtypes.erl:205: The pattern {'ok', _} can never match the type {'ok',X,binary() | string()} +contracts_with_subtypes.erl:206: The pattern 'alpha' can never match the type {'ok',X,binary() | string()} +contracts_with_subtypes.erl:207: The pattern {'ok', 42} can never match the type {'ok',X,binary() | string()} +contracts_with_subtypes.erl:208: The pattern 42 can never match the type {'ok',X,binary() | string()} +contracts_with_subtypes.erl:234: Function flat_ets_new_t/0 has no local return +contracts_with_subtypes.erl:235: The call contracts_with_subtypes:flat_ets_new(12,[]) breaks the contract (Name,Options) -> atom() when is_subtype(Name,atom()), is_subtype(Options,[Option]), is_subtype(Option,'set' | 'ordered_set' | 'bag' | 'duplicate_bag' | 'public' | 'protected' | 'private' | 'named_table' | {'keypos',integer()} | {'heir',pid(),term()} | {'heir','none'} | {'write_concurrency',boolean()} | {'read_concurrency',boolean()} | 'compressed') +contracts_with_subtypes.erl:23: Invalid type specification for function contracts_with_subtypes:extract2/0. The success typing is () -> 'something' +contracts_with_subtypes.erl:261: Function factored_ets_new_t/0 has no local return +contracts_with_subtypes.erl:262: The call contracts_with_subtypes:factored_ets_new(12,[]) breaks the contract (Name,Options) -> atom() when is_subtype(Name,atom()), is_subtype(Options,[Option]), is_subtype(Option,Type | Access | 'named_table' | {'keypos',Pos} | {'heir',Pid::pid(),HeirData} | {'heir','none'} | Tweaks), is_subtype(Type,type()), is_subtype(Access,access()), is_subtype(Tweaks,{'write_concurrency',boolean()} | {'read_concurrency',boolean()} | 'compressed'), is_subtype(Pos,pos_integer()), is_subtype(HeirData,term()) +contracts_with_subtypes.erl:77: The call contracts_with_subtypes:foo1(5) breaks the contract (Arg1) -> Res when is_subtype(Arg1,atom()), is_subtype(Res,atom()) +contracts_with_subtypes.erl:78: The call contracts_with_subtypes:foo2(5) breaks the contract (Arg1) -> Res when is_subtype(Arg1,Arg2), is_subtype(Arg2,atom()), is_subtype(Res,atom()) +contracts_with_subtypes.erl:79: The call contracts_with_subtypes:foo3(5) breaks the contract (Arg1) -> Res when is_subtype(Arg2,atom()), is_subtype(Arg1,Arg2), is_subtype(Res,atom()) +contracts_with_subtypes.erl:7: Invalid type specification for function contracts_with_subtypes:extract/0. The success typing is () -> 'something' +contracts_with_subtypes.erl:80: The call contracts_with_subtypes:foo4(5) breaks the contract (Type) -> Type when is_subtype(Type,atom()) +contracts_with_subtypes.erl:81: The call contracts_with_subtypes:foo5(5) breaks the contract (Type::atom()) -> Type::atom() +contracts_with_subtypes.erl:82: The call contracts_with_subtypes:foo6(5) breaks the contract (Type) -> Type when is_subtype(Type,atom()) diff --git a/lib/dialyzer/test/small_SUITE_data/src/collapse_lists/a.erl b/lib/dialyzer/test/small_SUITE_data/src/collapse_lists/a.erl new file mode 100644 index 0000000000..7efe870b0d --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/src/collapse_lists/a.erl @@ -0,0 +1,9 @@ +-module(a). +-export([g/1]). + +-export_type([a/0, t/0]). +-type a() :: integer(). +-type t() :: a() | maybe_improper_list(t(), t()). + +-spec g(t()) -> t(). +g(X) -> X. diff --git a/lib/dialyzer/test/small_SUITE_data/src/collapse_lists/b.erl b/lib/dialyzer/test/small_SUITE_data/src/collapse_lists/b.erl new file mode 100644 index 0000000000..b08bc5e66c --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/src/collapse_lists/b.erl @@ -0,0 +1,5 @@ +-module(b). +-export([f/1]). + +-spec f(a:t()) -> a:t(). +f(X) -> a:g(X). diff --git a/lib/dialyzer/test/small_SUITE_data/src/contracts_with_subtypes.erl b/lib/dialyzer/test/small_SUITE_data/src/contracts_with_subtypes.erl new file mode 100644 index 0000000000..d72138d509 --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/src/contracts_with_subtypes.erl @@ -0,0 +1,267 @@ +-module(contracts_with_subtypes). + +-compile(export_all). + +%=============================================================================== + +-spec extract() -> 'ok'. + +extract() -> + case dz_extract() of + {ok, Val} -> Val; + error -> exit(boom) + end. + +-spec dz_extract() -> RetValue when + FileList :: something, + RetValue :: {ok, FileList} | error. + +dz_extract() -> get(foo). + +%------------------------------------------------------------------------------- + +-spec extract2() -> 'ok'. + +extract2() -> + case dz_extract2() of + {ok, Val} -> Val; + error -> exit(boom) + end. + +-spec dz_extract2() -> RetValue when + RetValue :: {ok, FileList} | error, + FileList :: something. + +dz_extract2() -> get(foo). + +%=============================================================================== + +-spec foo1(Arg1) -> Res when + Arg1 :: atom(), + Res :: atom(). + +foo1(X) -> X. + +-spec foo2(Arg1) -> Res when + Arg1 :: Arg2, + Arg2 :: atom(), + Res :: atom(). + +foo2(X) -> X. + +-spec foo3(Arg1) -> Res when + Arg2 :: atom(), + Arg1 :: Arg2, + Res :: atom(). + +foo3(X) -> X. + +-spec foo4(Type) -> Type when is_subtype(Type, atom()). + +foo4(X) -> X. + +-spec foo5(Type :: atom()) -> Type :: atom(). + +foo5(X) -> X. + +-spec foo6(Type) -> Type when Type :: atom(). + +foo6(X) -> X. + +-spec foo7(Type) -> Type. + +foo7(X) -> X. + +%------------------------------------------------------------------------------- + +bar(1) -> foo1(5); +bar(2) -> foo2(5); +bar(3) -> foo3(5); +bar(4) -> foo4(5); +bar(5) -> foo5(5); +bar(6) -> foo6(5); +bar(7) -> foo7(5). + +wrong_foo6() -> + b = foo6(a). + +%=============================================================================== + +-spec rec_arg(Arg) -> ok when + Arg :: {a, A} | {b, B}, + A :: a | {b, B}, + B :: b | {a, A}. + +rec_arg(X) -> get(X). + +c(aa) -> rec_arg({a, a}); +c(bb) -> rec_arg({b, b}); +c(abb) -> rec_arg({a, {b, b}}); +c(baa) -> rec_arg({b, {a, a}}); +c(abaa) -> rec_arg({a, {b, {a, a}}}); +c(babb) -> rec_arg({b, {a, {b, b}}}); +c(ababb) -> rec_arg({a, {b, {a, {b, b}}}}); +c(babaa) -> rec_arg({b, {a, {b, {a, a}}}}). + +w(ab) -> rec_arg({a, b}); +w(ba) -> rec_arg({b, a}); +w(aba) -> rec_arg({a, {b, a}}); +w(bab) -> rec_arg({b, {a, b}}); +w(abab) -> rec_arg({a, {b, {a, b}}}); +w(baba) -> rec_arg({b, {a, {b, a}}}); +w(ababa) -> rec_arg({a, {b, {a, {b, a}}}}); +w(babab) -> rec_arg({b, {a, {b, {a, b}}}}). + +%=============================================================================== + +-type dublo(X) :: {X, X}. + +-type weird(X,Y) :: {X, Y, X, X}. + +-spec forfun(dublo(Var)) -> ok when Var :: atom(). + +forfun(_) -> ok. + +-spec forfun2(weird(Var, Var)) -> ok when Var :: atom(). + +forfun2(_) -> ok. + +%=============================================================================== + +-spec shallow(X) -> {ok, X} | {ok, X, file:filename()} | err1 | err2. + +shallow(X) -> get(X). + +st(X) when is_atom(X) -> + case shallow(X) of + err1 -> ok; + err2 -> ok; + {ok, X} -> ok; + {ok, X, Res} -> + case Res of + 1 -> bad; + _Other -> ok + end; + alpha -> bad; + {ok, 42} -> bad; + 42 -> bad + end. + +%------------------------------------------------------------------------------- + +-spec deep(X) -> Ret when + Ret :: {ok, X} | Err, + Err :: err1 | err2. + +deep(X) -> get(X). + +dt(X) when is_atom(X) -> + case deep(X) of + err1 -> ok; + err2 -> ok; + {ok, X} -> ok; + alpha -> bad; + {ok, 42} -> bad; + 42 -> bad + end. + +%------------------------------------------------------------------------------- + +-type local_errors() :: err1 | err2. + +-spec deep2(X) -> Ret when + Ret :: {ok, X} | Err, + Err :: local_errors(). + +deep2(X) -> get(X). + +dt2(X) when is_atom(X) -> + case deep2(X) of + err1 -> ok; + err2 -> ok; + {ok, X} -> ok; + alpha -> bad; + {ok, 42} -> bad; + 42 -> bad + end. + +%------------------------------------------------------------------------------- + +-spec deep3(X) -> Ret when + Ret :: {ok, X, file:filename()} | Err, + Err :: local_errors(). + +deep3(X) -> get(X). + +dt3(X) when is_atom(X) -> + case deep3(X) of + err1 -> ok; + err2 -> ok; + {ok, X, Res} -> + case Res of + 1 -> bad; + _Other -> ok + end; + {ok, X} -> bad; + alpha -> bad; + {ok, 42} -> bad; + 42 -> bad + end. + +%=============================================================================== + +-spec flat_ets_new(Name, Options) -> atom() when + Name :: atom(), + Options :: [Option], + Option :: set + | ordered_set + | bag + | duplicate_bag + | public + | protected + | private + | named_table + | {keypos, integer()} + | {heir, pid(), term()} + | {heir, none} + | {write_concurrency, boolean()} + | {read_concurrency, boolean()} + | compressed. + +flat_ets_new(Name, Options) -> + get({Name, Options}). + +flat_ets_new_t() -> + flat_ets_new(12,[]), + flat_ets_new({a,b},[]), + flat_ets_new(name,[foo]), + flat_ets_new(name,{bag}), + flat_ets_new(name,bag), + ok. + +-type access() :: public | protected | private. +-type type() :: set | ordered_set | bag | duplicate_bag. + +-spec factored_ets_new(Name, Options) -> atom() when + Name :: atom(), + Options :: [Option], + Option :: Type | Access | named_table | {keypos,Pos} + | {heir, Pid :: pid(), HeirData} | {heir, none} | Tweaks, + Type :: type(), + Access :: access(), + Tweaks :: {write_concurrency, boolean()} + | {read_concurrency, boolean()} + | compressed, + Pos :: pos_integer(), + HeirData :: term(). + +factored_ets_new(Name, Options) -> + get({Name, Options}). + +factored_ets_new_t() -> + factored_ets_new(12,[]), + factored_ets_new({a,b},[]), + factored_ets_new(name,[foo]), + factored_ets_new(name,{bag}), + factored_ets_new(name,bag), + ok. diff --git a/lib/dialyzer/test/small_SUITE_data/src/deep_lc.erl b/lib/dialyzer/test/small_SUITE_data/src/deep_lc.erl new file mode 100644 index 0000000000..d9ca0817d9 --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/src/deep_lc.erl @@ -0,0 +1,14 @@ +-module(deep_lc). + +-export([t/0]). + +%% This is compile/test/lc_SUITE:deeply_nested/1 +%% +%% Used to be _very_ slow. Unknown how slow, but more than 15 hours. + +t() -> + [[X1,X2,X3,X4,X5,X6,X7(),X8,X9,X10,X11,X12,X13,X14,X15,X16,X17,X18(),X19,X20] || + X1 <- [99],X2 <- [98],X3 <- [97],X4 <- [96],X5 <- [42],X6 <- [17], + X7 <- [fun() -> X5*X5 end],X8 <- [12],X9 <- [11],X10 <- [10], + X11 <- [9],X12 <- [8],X13 <- [7],X14 <- [6],X15 <- [5], + X16 <- [4],X17 <- [3],X18 <- [fun() -> X16+X17 end],X19 <- [2],X20 <- [1]]. |