dialyzer_dep.erl

来自「OTP是开放电信平台的简称」· ERL 代码 · 共 553 行 · 第 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_dep.erl
%%% Author  : Tobias Lindahl <[e-mail]>
%%%
%%% Description: A pretty limited but efficient escape/dependency
%%%              analysis of Core Erlang.
%%%
%%% Created : 28 Oct 2005 by Tobias Lindahl <[e-mail]>
%%%-------------------------------------------------------------------
-module(dialyzer_dep).

-define(NO_UNUSED, true).

-export([analyze/1]).
-ifndef(NO_UNUSED).
-export([test/1]).
-endif.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%% analyze(CoreTree) -> {Deps, Esc, Calls}.
%%                
%% Deps =  a dict mapping labels of functions to a ordset of functions it calls.
%%
%% Esc =   a set (ordsets) of the labels of escaping functions. A function
%%         is considered to escape if the control escapes a function,
%%         i.e., this analysis is not module-local but rather
%%         function-local.
%%
%% Calls = a dict mapping apply:s to a ordset of function labels to which
%%         the operation can refer to. If 'external' is part of the
%%         set the operation can be externally defined.
%%

analyze(Tree) ->
  %%io:format("Handling ~w\n", [cerl:atom_val(cerl:module_name(Tree))]),
  {_, State} = traverse(Tree, map__new(), state__new(Tree), top),
  Esc = state__esc(State), 
  %% Add dependency from 'external' to all escaping function
  State1 = state__add_deps(external, output(Esc), State),
  Deps = state__deps(State1),
  Calls = state__calls(State1),
  {map__finalize(Deps), set__to_ordsets(Esc), map__finalize(Calls)}.

traverse(Tree, Out, State, CurrentFun) ->
  %%io:format("Type: ~w\n", [cerl:type(Tree)]),
  case cerl:type(Tree) of
    apply ->
      Op = cerl:apply_op(Tree),
      Args = cerl:apply_args(Tree),
      %% Op is always a variable and should not be marked as escaping
      %% based on its use.
      case var =:= cerl:type(Op) of
	false -> erlang:fault({apply_op_not_a_variable, cerl:type(Op)});
	true -> ok
      end,
      OpFuns = case map__lookup(cerl_trees:get_label(Op), Out) of
		 none -> output(none);
		 {value, OF} -> OF
	       end,
      {ArgFuns, State2} = traverse_list(Args, Out, State, CurrentFun),
      State3 = state__add_esc(merge_outs(ArgFuns), State2),
      State4 = state__add_deps(CurrentFun, OpFuns, State3),
      State5 = state__store_callsite(cerl_trees:get_label(Tree), OpFuns,State4),
      {output(set__singleton(external)), State5};
    binary ->
      {output(none), State};
    'case' ->
      Arg = cerl:case_arg(Tree),
      {Funs, NewState} = traverse(Arg, Out, State, CurrentFun),
      Clauses = cerl:case_clauses(Tree),
      traverse_clauses(Clauses, Funs, Out, NewState, CurrentFun);
    call ->
      Args = cerl:call_args(Tree),
      {ArgFuns, State1} = traverse_list(Args, Out, State, CurrentFun),
      remote_call(Tree, merge_outs(ArgFuns), State1);
    'catch' ->
      traverse(cerl:catch_body(Tree), Out, State, CurrentFun);
    cons ->
      {HdFuns, State1} = traverse(cerl:cons_hd(Tree), Out, State, CurrentFun),
      {TlFuns, State2} = traverse(cerl:cons_tl(Tree), Out, State1, CurrentFun),
      {merge_outs([HdFuns, TlFuns]), State2};
    'fun' ->
      %%io:format("Entering fun: ~w\n", [cerl_trees:get_label(Tree)]),
      Body = cerl:fun_body(Tree),
      Label = cerl_trees:get_label(Tree),
      if CurrentFun =:= top -> 
	  State1 = state__add_deps(top, output(set__singleton(Label)), State);
	 true -> 
	  O1 = output(set__singleton(CurrentFun)),
	  O2 = output(set__singleton(Label)),
	  TmpState = state__add_deps(Label, O1, State),
	  State1 = state__add_deps(CurrentFun, O2,TmpState)
      end,
      {BodyFuns, State2} = traverse(Body, Out, State1, 
				    cerl_trees:get_label(Tree)),
      {output(set__singleton(Label)), state__add_esc(BodyFuns, State2)};
    'let' ->
      Vars = cerl:let_vars(Tree),
      Arg = cerl:let_arg(Tree),
      Body = cerl:let_body(Tree),
      {ArgFuns, State1} = traverse(Arg, Out, State, CurrentFun),
      Out1 = bind_list(Vars, ArgFuns, Out),
      traverse(Body, Out1, State1, CurrentFun);
    letrec ->
      Defs = cerl:letrec_defs(Tree),
      Body = cerl:letrec_body(Tree),
      Out1 = bind_defs(Defs, Out),
      State1 = traverse_defs(Defs, Out1, State, CurrentFun),
      traverse(Body, Out1, State1, CurrentFun);
    literal ->
      {output(none), State};
    module ->
      Defs = cerl:module_defs(Tree),
      Out1 = bind_defs(Defs, Out),
      State1 = traverse_defs(Defs, Out1, State, CurrentFun),
      {output(none), State1};
    primop ->
      Args = cerl:primop_args(Tree),
      {ArgFuns, State1} = traverse_list(Args, Out, State, CurrentFun),
      primop(Tree, merge_outs(ArgFuns), State1);
    'receive' ->
      Clauses = cerl:receive_clauses(Tree),
      TimeOut = cerl:receive_timeout(Tree),
      Action = cerl:receive_action(Tree),
      {ClauseFuns, State1} = 
	traverse_clauses(Clauses, output(none), Out, State, CurrentFun),
      {_, State2} = traverse(TimeOut, Out, State1, CurrentFun),
      {ActionFuns, State3} = traverse(Action, Out, State2, CurrentFun),
      {merge_outs([ClauseFuns, ActionFuns]), State3};
    seq ->
      {_, State1} = traverse(cerl:seq_arg(Tree), Out, State, CurrentFun),
      traverse(cerl:seq_body(Tree), Out, State1, CurrentFun);
    'try' ->
      Arg = cerl:try_arg(Tree),
      Body = cerl:try_body(Tree),
      Vars = cerl:try_vars(Tree),
      EVars = cerl:try_evars(Tree),
      Handler = cerl:try_handler(Tree),
      {ArgFuns, State1} = traverse(Arg, Out, State, CurrentFun),
      Out1 = bind_list(Vars, ArgFuns, Out),
      {BodyFuns, State2} = traverse(Body, Out1, State1, CurrentFun),
      Out2 = bind_single(EVars, output(set__singleton(external)), Out),
      {HandlerFuns, State3} = traverse(Handler, Out2, State2, CurrentFun),
      {merge_outs([BodyFuns, HandlerFuns]), State3};
    tuple ->
      Args = cerl:tuple_es(Tree),
      {List, State1} = traverse_list(Args, Out, State, CurrentFun),
      {merge_outs(List), State1};
    values ->      
      traverse_list(cerl:values_es(Tree), Out, State, CurrentFun);
    var ->
      case map__lookup(cerl_trees:get_label(Tree), Out) of
	none -> {output(none), State};
	{value, Val} -> 
	  case is_only_external(Val) of
	    true ->
	      %% Do nothing
	      {Val, State};
	    false ->
	      %% If this is used in a function this means a dependency.
	      {Val, state__add_deps(CurrentFun, Val, State)}
	  end
      end
  end.

traverse_list(Trees, Out, State, CurrentFun) ->
  traverse_list(Trees, Out, State, CurrentFun, []).

traverse_list([Tree|Left], Out, State, CurrentFun, Acc) ->
  {X, State1} = traverse(Tree, Out, State, CurrentFun),
  traverse_list(Left, Out, State1, CurrentFun, [X|Acc]);
traverse_list([], _Out, State, _CurrentFun, Acc) ->
  {output(lists:reverse(Acc)), State}.

traverse_defs([{_, Fun}|Left], Out, State, CurrentFun) ->
  {_, State1} = traverse(Fun, Out, State, CurrentFun),
  traverse_defs(Left, Out, State1, CurrentFun);
traverse_defs([], _Out, State, _CurrentFun) ->
  State.

traverse_clauses(Clauses, ArgFuns, Out, State, CurrentFun) ->
  case filter_match_fail(Clauses) of
    [] ->
      %% Can happen for example with receives used as timouts.
      {output(none), State};
    Clauses1 ->
      traverse_clauses(Clauses1, ArgFuns, Out, State, CurrentFun, [])
  end.

traverse_clauses([Clause|Left], ArgFuns, Out, State, CurrentFun, Acc) ->
  Pats = cerl:clause_pats(Clause),
  Guard = cerl:clause_guard(Clause),
  Body = cerl:clause_body(Clause),
  Out1 = bind_pats_list(Pats, ArgFuns, Out),
  {_, State2} = traverse(Guard, Out1, State, CurrentFun),
  {BodyFuns, State3} = traverse(Body, Out1, State2, CurrentFun),
  traverse_clauses(Left, ArgFuns, Out, State3, CurrentFun, [BodyFuns|Acc]);
traverse_clauses([], _ArgFuns, _Out, State, _CurrentFun, Acc) ->
  {merge_outs(Acc), State}.

filter_match_fail([Clause]) ->
  Body = cerl:clause_body(Clause),
  case cerl:type(Body) of
    primop ->
      case cerl:atom_val(cerl:primop_name(Body)) of
	match_fail -> [];
	raise -> [];
	_ -> [Clause]
      end;
    _ -> [Clause]
  end;
filter_match_fail([H|T]) ->
  [H|filter_match_fail(T)];
filter_match_fail([]) ->
  %% This can actually happen, for example in 
  %%      receive after 1 -> ok end
  [].

remote_call(Tree, ArgFuns, State) ->  
  M = cerl:call_module(Tree),
  F = cerl:call_name(Tree),
  A = length(cerl:call_args(Tree)),
  case cerl:is_c_atom(M) andalso cerl:is_c_atom(F) of
    false ->
      %% Unknown function. 
      {output(set__singleton(external)), state__add_esc(ArgFuns, State)};
    true ->
      M1 = cerl:atom_val(M),
      F1 = cerl:atom_val(F),
      Literal = cerl_closurean:is_literal_op(M1, F1, A),
      case erl_bifs:is_pure(M1, F1, A) of
	true ->
	  case Literal of
	    true -> 
	      {output(none), State};
	    false -> 
	      {output(set__singleton(external)), state__add_esc(ArgFuns, State)}
	  end;
	false ->	  
	  State1 = case cerl_closurean:is_escape_op(M1, F1, A) of
		     true -> state__add_esc(ArgFuns, State);
		     false -> State
		   end,
	  case Literal of
	    true -> {output(none), State1};
	    false -> {add_external(ArgFuns), State1}
	  end
      end
  end.

primop(Tree, ArgFuns, State) ->
  F = cerl:atom_val(cerl:primop_name(Tree)),
  A = length(cerl:primop_args(Tree)),
  State1 = case cerl_closurean:is_escape_op(F, A) of
	     true -> state__add_esc(ArgFuns, State);
	     false -> State
	   end,
  case cerl_closurean:is_literal_op(F, A) of
    true -> {output(none), State1};
    false -> {ArgFuns, State1}