dialyzer_callgraph.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 564 行 · 第 1/2 页

%% ``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 via the world wide web 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.
%% 
%% Copyright 2006, Tobias Lindahl and Kostis Sagonas
%% 
%%     $Id$
%%

%%%-------------------------------------------------------------------
%%% File    : dialyzer_callgraph.erl
%%% Author  : Tobias Lindahl <[e-mail]>
%%% Description : 
%%%
%%% Created : 30 Mar 2005 by Tobias Lindahl <[e-mail]>
%%%-------------------------------------------------------------------
-module(dialyzer_callgraph).

-export([all_nodes/1,
	 delete/1,
	 finalize/1,
	 is_escaping/2,
	 is_self_rec/2,	 
	 non_local_calls/1,
	 lookup_rec_var/2,	 
	 lookup_call_site/2,
	 lookup_label/2,
	 lookup_name/2,
	 modules/1,
	 module_postorder/1,
	 module_postorder_from_funs/2,
	 in_neighbours/2,
	 reset_from_funs/2,
	 scan_core_tree/2,
	 scan_icode/2,
	 split_into_components/1,
	 new/0, 
	 take_scc/1, 
	 remove_external/1]).

%-define(NO_UNUSED, true).
-ifndef(NO_UNUSED).
-export([to_dot/1]).
-endif.

%%----------------------------------------------------------------------
%%
%% A callgraph is a directed graph where the nodes are functions and a
%% call between two functions is an edge from the caller to the
%% callee. 
%%
%% calls       -  A mapping from call site (and apply site) labels 
%%                to the possible functions that can be called.
%% 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. 
%%                Only for top level functions (from module defs).
%% self_rec    -  a set containing all self recursive functions.
%%                Note that this contains MFAs for named functions and labels
%%                whenever applicable.
%%

-record(dialyzer_callgraph, {digraph, esc, name_map, rev_name_map, postorder,
			     rec_var_map, self_rec, calls}).

new() ->
  #dialyzer_callgraph{calls=dict:new(),
		      digraph=digraph_new(),
		      esc=sets:new(),
		      name_map=dict:new(),
		      postorder=[],
		      rec_var_map=dict:new(),
		      rev_name_map=dict:new(),
		      self_rec=sets:new()}.

delete(#dialyzer_callgraph{digraph=Digraph}) ->
  digraph_delete(Digraph).

split_into_components(CG = #dialyzer_callgraph{digraph=Digraph}) ->
  %% Splits the callgraph into connected components that can be
  %% analyzed in parallell. Note that we keep all other information in
  %% the callgraph the same in all parts even if it means a lot of
  %% redundant information.
  DigraphList = digraph_components(Digraph),
  [CG#dialyzer_callgraph{digraph=DG} || DG <- DigraphList].

all_nodes(#dialyzer_callgraph{digraph=DG}) ->
  digraph_vertices(DG).

lookup_rec_var(Label, #dialyzer_callgraph{rec_var_map=RecVarMap}) 
  when is_integer(Label) ->
  dict:find(Label, RecVarMap).

lookup_call_site(Label,#dialyzer_callgraph{calls=Calls})when is_integer(Label)->
  dict:find(Label, Calls).

lookup_name(Label,#dialyzer_callgraph{name_map=NameMap})when is_integer(Label)->
  dict:find(Label, NameMap).

lookup_label(MFA = {_,_,_}, #dialyzer_callgraph{rev_name_map=RevNameMap}) ->
  dict:find(MFA, RevNameMap);
lookup_label(Label, #dialyzer_callgraph{}) when is_integer(Label) ->
  {ok, Label}.

in_neighbours(Label, CG=#dialyzer_callgraph{}) when is_integer(Label) ->
  Name = case dict:find(Label, CG#dialyzer_callgraph.name_map) of
	   {ok, Val} -> Val;
	   error -> Label
	 end,
  digraph_in_neighbours(Name, CG#dialyzer_callgraph.digraph);
in_neighbours(MFA={_,_,_}, CG=#dialyzer_callgraph{}) ->
  digraph_in_neighbours(MFA, CG#dialyzer_callgraph.digraph).

is_self_rec(MfaOrLabel, #dialyzer_callgraph{self_rec=SelfRecs}) ->
  sets:is_element(MfaOrLabel, SelfRecs).

is_escaping(Label, #dialyzer_callgraph{esc=Esc}) when is_integer(Label) ->
  sets:is_element(Label, Esc).  

add_edges([], CG) ->
  CG;
add_edges(Edges, CG = #dialyzer_callgraph{digraph=Callgraph}) ->
  CG#dialyzer_callgraph{digraph=digraph_add_edges(Edges, Callgraph)}.

add_edges(Edges, MFAs, CG = #dialyzer_callgraph{digraph=DG}) ->
  DG1 = digraph_confirm_vertices(MFAs, DG),
  add_edges(Edges, CG#dialyzer_callgraph{digraph=DG1}).

take_scc(CG = #dialyzer_callgraph{postorder=[SCC|Left]}) ->
  {ok, SCC, CG#dialyzer_callgraph{postorder=Left}};
take_scc(#dialyzer_callgraph{postorder=[]}) ->
  none.

remove_external(CG = #dialyzer_callgraph{digraph=DG}) ->
  {NewDG, External} = digraph_remove_external(DG),
  {CG#dialyzer_callgraph{digraph=NewDG}, External}.

non_local_calls(#dialyzer_callgraph{digraph=DG}) ->
  Edges = digraph_edges(DG),		
  find_non_local_calls(Edges, sets:new()).

find_non_local_calls([{{M, _, _}, {M, _, _}}|Left], Set) ->
  find_non_local_calls(Left, Set);
find_non_local_calls([Edge={{M1, _, _},{M2, _, _}}|Left], Set) when M1 =/= M2 ->
  find_non_local_calls(Left, sets:add_element(Edge, Set));
find_non_local_calls([{{_,_,_}, Label}|Left], Set) when is_integer(Label) ->
  find_non_local_calls(Left, Set);  
find_non_local_calls([{Label, {_,_,_}}|Left], Set) when is_integer(Label) ->
  find_non_local_calls(Left, Set);
find_non_local_calls([{Label1, Label2}|Left], Set) when is_integer(Label1),
							is_integer(Label2) ->
  find_non_local_calls(Left, Set);
find_non_local_calls([], Set) ->
  sets:to_list(Set).

modules(#dialyzer_callgraph{digraph=DG}) ->
  ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]).

module_postorder(#dialyzer_callgraph{digraph=DG}) ->
  Edges = digraph_edges(DG),
  Nodes = ordsets:from_list([M || {M,_F,_A} <- digraph_vertices(DG)]),
  MDG = digraph_new(),
  MDG1 = digraph_confirm_vertices(Nodes, MDG),
  MDG2 = create_module_digraph(Edges, MDG1),
  MDG3 = digraph_utils:condensation(MDG2),
  PostOrder = digraph_utils:postorder(MDG3),
  PostOrder1 = sort_sccs_internally(PostOrder, MDG2),
  digraph:delete(MDG2),
  digraph_delete(MDG3),
  PostOrder1.

sort_sccs_internally(PO, MDG) ->
  sort_sccs_internally(PO, MDG, []).

sort_sccs_internally([SCC|Left], MDG, Acc) ->
  case length(SCC) >= 3 of
    false -> sort_sccs_internally(Left, MDG, [SCC|Acc]);
    true ->
      TmpDG = digraph_utils:subgraph(MDG, SCC),
      NewSCC = digraph_utils:postorder(TmpDG),
      digraph_delete(TmpDG),
      sort_sccs_internally(Left, MDG, [NewSCC|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.

finalize(CG = #dialyzer_callgraph{digraph=DG}) ->
  CG#dialyzer_callgraph{postorder=digraph_finalize(DG)}.

reset_from_funs(Funs, CG = #dialyzer_callgraph{digraph=DG}) ->
  SubGraph = digraph_reaching_subgraph(Funs, DG),
  Postorder = digraph_finalize(SubGraph),
  digraph_delete(SubGraph),
  CG#dialyzer_callgraph{postorder=Postorder}.

module_postorder_from_funs(Funs, CG = #dialyzer_callgraph{digraph=DG}) ->
  SubGraph = digraph_reaching_subgraph(Funs, DG),
  PO = module_postorder(CG#dialyzer_callgraph{digraph=SubGraph}),
  digraph_delete(SubGraph),
  PO.
  
%%____________________________________________________________
%%
%% Core code
%%

%% The core tree must be labeled as by cerl_trees:label/1 (or /2).
%% The set of labels in the tree must be disjoint from the set of
%% labels already occuring in the callgraph.

scan_core_tree(Tree, CG=#dialyzer_callgraph{calls=OldCalls,
					    esc=OldEsc,
					    name_map=OldNameMap,
					    rec_var_map=OldRecVarMap, 
					    rev_name_map=OldRevNameMap,
					    self_rec=OldSelfRec}) ->
  %% Build name map and recursion variable maps.
  {NewNameMap, NewRevNameMap, NewRecVarMap} = 
    build_maps(Tree, OldRecVarMap, OldNameMap, OldRevNameMap),
  
  %% 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),
  LabelEdges = get_edges_from_deps(Deps0),
  
  %% Find the self recursive functions. Named functions gets both the
  %% key and its name for convenience.
  SelfRecs0 = lists:foldl(fun({Key, Key}, Acc) -> 
			      case dict:find(Key, NewNameMap) of
				error      -> [Key|Acc];
				{ok, Name} -> [Key, Name|Acc]
			      end;
			     (_, Acc) -> Acc
			  end, [], LabelEdges),
  SelfRecs = sets:union(sets:from_list(SelfRecs0), OldSelfRec),
  
  NamedEdges1 = name_edges(LabelEdges, NewNameMap),
  
  %% We need to scan for intermodular calls since this is not tracked
  %% by dialyzer_dep. Note that the caller is always recorded as the
  %% top level function. This is ok since the included functions are
  %% stored as scc with the parent.
  NamedEdges2 = scan_core_funs(Tree),

  %% Confirm all nodes in the tree.
  Names1 = lists:flatten([[X, Y] || {X, Y} <- NamedEdges1]),
  Names2 = ordsets:from_list(Names1),
  Names3 = ordsets:del_element(top, Names2),
  CG1 = add_edges(NamedEdges2++NamedEdges1, Names3, CG),
  
  CG1#dialyzer_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) ->
  %% We only care about the named (top level) functions. The anonymous