dialyzer_dataflow.erl

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

enter_subst(Key, Val, MS = {Map, Subst}) ->
  KeyLabel = get_label(Key),
  case cerl:is_literal(Val) of
    true -> 
      NewMap = dict:store(KeyLabel, literal_type(Val), Map),
      {NewMap, Subst};
    false ->
      case cerl:is_c_var(Val) of
	false -> MS;
	true ->
	  ValLabel = get_label(Val),
	  case dict:find(ValLabel, Subst) of
	    {ok, NewVal} ->
	      enter_subst(Key, NewVal, MS);
	    error ->
	      if KeyLabel =:= ValLabel -> MS;
		 true ->
		  ?debug("Subst: storing ~p = ~p\n", [KeyLabel, ValLabel]),
		  NewSubst = dict:store(KeyLabel, ValLabel, Subst),
		  {Map, NewSubst}
	      end
	  end
      end
  end.

lookup_type(Key, {Map, Subst}) -> 
  lookup(Key, Map, Subst, t_none()).

lookup(Key, Map, Subst, AnyNone) ->
  case cerl:is_literal(Key) of
    true -> literal_type(Key);
    false -> 
      Label = get_label(Key),
      case dict:find(Label, Subst) of
	{ok, NewKey} -> lookup(NewKey, Map, Subst, AnyNone);
	error ->
	  case dict:find(Label, Map) of
	    {ok, Val} -> Val;
	    error -> AnyNone
	  end
      end
  end.

lookup_fun_name(Fun, Callgraph) ->
  case dialyzer_callgraph:lookup_name(Fun, Callgraph) of
    {ok, MFA} -> MFA;
    error -> Fun
  end.

lookup_fun_sig(Fun, Callgraph, Plt, Args) ->
  MFAorLabel = lookup_fun_name(Fun, Callgraph),
  dialyzer_plt:lookup(Plt, MFAorLabel, Args).

literal_type(Lit) ->
  t_from_term(cerl:concrete(Lit)).

mark_as_fresh(Trees, Map) ->
  Fun = fun(T, AccMap) ->
	    case cerl:is_literal(T) of
	      true -> enter_type(T, literal_type(T), AccMap);
	      false -> enter_type(T, t_any(), AccMap)
	    end
	end,
  mark_as_fresh(Trees, Fun, Map).

mark_as_fresh([Tree|Left], Fun, Map) ->
  Map1 = cerl_trees:fold(Fun, Map, Tree),
  mark_as_fresh(Left, Map1);
mark_as_fresh([], _Fun, Map) ->
  Map.  

-ifdef(DEBUG).
debug_pp_map(Map = {Map0, _Subst}) ->
  Keys = dict:fetch_keys(Map0),
  io:format("Map:\n", []),
  [io:format("\t~w :: ~s\n", [Key, t_to_string(lookup_type(Key, Map))])
   || Key <- Keys],
  ok.
-else.
debug_pp_map(_Map) -> ok.
-endif.

%%% ============================================================================
%%%
%%%  Utilities
%%%
%%% ============================================================================

add_def_vars([H|T], DefVars) ->
  add_def_vars(T, ordsets:add_element(get_label(H), DefVars));
add_def_vars([], DefVars) ->
  DefVars.

is_def_var(Var, DefVars) ->
  ordsets:is_element(get_label(Var), DefVars).

get_label(L) when is_integer(L) ->
  L;
get_label(T) ->
  cerl_trees:get_label(T).

any_none([X|Xs]) ->
  case t_is_none(X) of
    true ->
      true;
    false ->
      any_none(Xs)
  end;
any_none([]) -> false.

any_unit([X|Xs]) ->
  case t_is_unit(X) of
    true ->
      true;
    false ->
      any_unit(Xs)
  end;
any_unit([]) -> false.



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
  [].


%%% ============================================================================
%%%
%%%  The State.
%%%
%%% ============================================================================

-record(state, {callgraph, envs, forward_mode, fun_tab, plt, 
		records, tree_map, warning_mode, warnings, work}).

state__new(Callgraph, Tree, Plt, Records, ForwardMode) -> 
  TreeMap = build_tree_map(Tree),
  Funs = dict:fetch_keys(TreeMap),
  FunTab = init_fun_tab(Funs, dict:new(), TreeMap, Callgraph, Plt, ForwardMode),
  
  Work = init_work([get_label(Tree)]),
  Env = dict:store(top, {map__new(), []}, dict:new()),
  #state{callgraph=Callgraph, envs=Env, fun_tab=FunTab, 
	 forward_mode=ForwardMode,
	 plt=Plt, records=Records, warning_mode=false, warnings=[],
	 work=Work, tree_map=TreeMap}.

state__mark_fun_as_handled(State = #state{fun_tab=FunTab}, Fun0) ->
  Fun = get_label(Fun0),
  case dict:find(Fun, FunTab) of
    {ok, {not_handled, Entry}} -> 
      State#state{fun_tab=dict:store(Fun, Entry, FunTab)};
    {ok, {_, _}} ->
      State
  end.

state__warning_mode(#state{warning_mode=WM}) ->
  WM.

state__set_warning_mode(State = #state{tree_map=TreeMap, fun_tab=FunTab}) ->
  ?debug("Starting warning pass\n", []),
  Funs = dict:fetch_keys(TreeMap),
  State#state{work=init_work([top|Funs--[top]]), fun_tab=FunTab,
	      warning_mode=true}.

state__add_warning(State, Tag, Tree, Msg) ->
  state__add_warning(State, Tag, Tree, Msg, false).

state__add_warning(S = #state{warning_mode=false}, _Tag, _Tree, _Msg, _Force) ->
  S;
state__add_warning(State = #state{warnings=Warnings, warning_mode=true}, 
		   Tag, Tree, Msg, Force) ->
  Ann = cerl:get_ann(Tree),
  case Force of
    true ->
      Warn = {Tag, {{get_file(Ann), abs(get_line(Ann))}, Msg}},
      State#state{warnings=[Warn|Warnings]};
    false ->
      case is_compiler_generated(Ann) of
	    true -> State;
	false ->
	  Warn = {Tag, {{get_file(Ann), get_line(Ann)}, Msg}},
	  State#state{warnings=[Warn|Warnings]}
      end
  end.

state__get_warnings(State = #state{tree_map=TreeMap, 
				   fun_tab=FunTab,
				   callgraph=Callgraph},
		    NoWarnUnused) ->
  FoldFun = 
    fun({top, _}, AccState) -> AccState;
       ({FunLbl, Fun}, AccState) ->
	{NotCalled, Ret} =
	  case dict:fetch(get_label(Fun), FunTab) of
	    {not_handled, {_Args0, Ret0}} -> {true, Ret0};
	    {Args0, Ret0} -> {any_none(Args0), Ret0}
	  end,
	case NotCalled of
	  true ->
	    {Warn, NameString} =
	      case lookup_fun_name(FunLbl, Callgraph) of
		FunLbl -> {true, "Function "};
		{_M, F, A} = MFA-> 
		  {not sets:is_element(MFA, NoWarnUnused),    
		   io_lib:format("Function ~w/~w ", [F, A])}
	      end,
	    Msg = NameString ++ "will never be called\n",
	    if Warn -> state__add_warning(AccState, ?WARN_NOT_CALLED, Fun, Msg);
	       true -> AccState
	    end;
	  false ->
	    NameString =
	      case lookup_fun_name(FunLbl, Callgraph) of
		FunLbl -> "Function ";
		{_M, F, A} -> io_lib:format("Function ~w/~w ", [F, A])
	      end,
	    case t_is_none_or_unit(Ret) of
	      true ->
		case classify_returns(Fun) of
		  only_explicit ->
		    Msg = NameString ++ 
		      "only terminates with explicit exception\n",
		    state__add_warning(AccState, ?WARN_RETURN_ONLY_EXIT, 
				       Fun, Msg);
		  only_normal ->
		    Msg = NameString ++ "has no local return\n",
		    state__add_warning(AccState, ?WARN_RETURN_NO_RETURN, 
				       Fun, Msg);
		  both ->
		    Msg = NameString ++ "has no local return\n",
		    state__add_warning(AccState, ?WARN_RETURN_NO_RETURN, 
				       Fun, Msg)
		end;
	      false ->
		AccState
	    end
	end
    end,
  #state{warnings=Warn} = lists:foldl(FoldFun, State, dict:to_list(TreeMap)),
  Warn.

state__is_escaping(Fun, #state{callgraph=Callgraph}) ->
  dialyzer_callgraph:is_escaping(Fun, Callgraph).

state__lookup_type_for_rec_var(Var, S = #state{callgraph=Callgraph}) ->
  Label = get_label(Var),
  case dialyzer_callgraph:lookup_rec_var(Label, Callgraph) of
    error -> error;
    {ok, MFA} ->
      case dialyzer_callgraph:lookup_label(MFA, Callgraph) of
	error -> error;
	{ok, FunLabel} ->
	  {ok, state__fun_type(FunLabel, S)}
      end
  end.

state__lookup_record(Tag, Arity, #state{records=Records}) ->
  case erl_types:lookup_record(Tag, Arity, Records) of
    {ok, Fields} -> 
      {ok, t_tuple([t_from_term(Tag)|
		    [FieldType || {_FieldName, FieldType} <- Fields]])};
    error -> 
      error
  end.

state__get_args(Tree, #state{fun_tab=FunTab}) ->
  Fun = get_label(Tree),
  case dict:find(Fun, FunTab) of
    {ok, {not_handled, {ArgTypes, _}}} -> ArgTypes;
    {ok, {ArgTypes, _}} -> ArgTypes
  end.

build_tree_map(Tree) ->
  Fun =
    fun(T, Dict) ->
	case cerl:is_c_fun(T) of
	  true ->
	    dict:store(get_label(T), T, Dict);
	  false ->
	    Dict
	end
    end,
  cerl_trees:fold(Fun, dict:new(), Tree).

init_fun_tab([top|Left], Dict, TreeMap, Callgraph, Plt, ForwardMode) ->
  NewDict = dict:store(top, {not_handled, {[], t_none()}}, Dict),
  init_fun_tab(Left, NewDict, TreeMap, Callgraph, Plt, ForwardMode);
init_fun_tab([Fun|Left], Dict, TreeMap, Callgraph, Plt, ForwardMode) ->
  Arity = cerl:fun_arity(dict:fetch(Fun, TreeMap)),
  FunEntry =
    case dialyzer_callgraph:is_escaping(Fun, Callgraph) of
      true -> 
	case lookup_fun_sig(Fun, Callgraph, Plt, none) of
	  none -> {duplicate(Arity, t_any()), t_unit()};
	  {value, {RetType, ArgTypes0}} ->
	    ArgTypes = 
	      case ForwardMode of
		unconstrained -> duplicate(Arity, t_any());
		constrained -> ArgTypes0
	      end,
	    case t_is_none(RetType) of
	      true -> {ArgTypes, t_none()};
	      false -> {ArgTypes, t_unit()}
	    end
	end;
      false -> {duplicate(Arity, t_none()), t_unit()}
    end,
  NewDict = dict:store(Fun, {not_handled, FunEntry}, Dict),
  init_fun_tab(Left, NewDict, TreeMap, Callgraph, Plt, ForwardMode);
init_fun_tab([], Dict, _TreeMap, _Callgraph, _Plt, _ForwardMode) ->
  Dict.

state__update_fun_env(Tree, MapAndDef, State = #state{envs=Envs}) ->
  NewEnvs = dict:store(get_label(Tree), MapAndDef, Envs),
  State#state{envs=NewEnvs}.

state__fun_env(Tree, #state{envs=Envs}) ->
  Fun = get_label(Tree),
  case dict:find(Fun, Envs) of
    error -> none;
    {ok, MapAndDef} -> MapAndDef
  end.

state__clean_not_called(State = #state{fun_tab=FunTab}) ->
  NewFunTab =
    dict:map(fun(top, Entry) -> Entry;
		(_Fun, {not_handled, {Args, _}}) -> {Args, t_none()};
		(_Fun, Entry) -> Entry
	     end, FunTab),
  State#state{fun_tab=NewFunTab}.

state__all_fun_types(#state{fun_tab=FunTab}) ->
  Tab1 = dict:erase(top, FunTab),
  dict:map(fun(_Fun, {Args, Ret}) -> t_fun(Args, Ret)end, Tab1).

state__fun_type(Fun, #state{fun_tab=FunTab}) ->
  Label = 
    if is_integer(Fun) -> Fun;
       true -> get_label(Fun)
    end,
  case dict:find(Label, FunTab) of
    {ok, {not_handled, {A, R}}} ->
      t_fun(A, R);
    {ok, {A, R}} ->
      t_fun(A, R)
  end.

state__update_fun_entry(Tree, ArgTypes, Out0, 
			State = #state{fun_tab=FunTab, callgraph=CG, plt=Plt})->
  Fun = get_label(Tree),
  Out1 = 
    if Fun =:= top -> Out0;
       true -> 
	case lookup_fun_sig(Fun, CG, Plt, ArgTypes) of
	  {value, {SigRet, _}} -> t_inf(SigRet, Out0);
	  none -> Out0
	end
    end,
  Out = t_limit(Out1, ?TYPE_LIMIT),
  case dict:find(Fun, FunTab) of
    {ok, {ArgTypes, OldOut}} ->
      case t_is_equal(OldOut, Out) of
	true -> 
	  ?debug("Fixpoint for ~w: ~s\n", 
		 [debug_lookup_name(Fun), 
		  t_to_string(t_fun(ArgTypes, Out))]),
	  State;
	false ->
	  NewEntry = {ArgTypes, Out},
	  ?debug("New Entry for ~w: ~s\n", 
		 [debug_lookup_name(Fun), 
		     t_to_string(t_fun(ArgTypes, Out))]),
	  NewFunTab = dict:store(Fun, NewEntry, FunTab),
	  State1 = State#state{fun_tab=NewFunTab},
	  state__add_work_from_fun(Tree, State1)
      end;
    {ok, {NewArgTypes, _OldOut}} ->
      %% Can only happen in self-recursive functions. Only update the out type.
      NewEntry = {NewArgTypes, Out},
      ?debug("New Entry for ~w: ~s\n", 
	     [debug_lookup_name(Fun), 
	      t_to_string(t_fun(NewArgTypes, Out))]),
      NewFunTab = dict:store(Fun, NewEntry, FunTab),
      State1 = State#state{fun_tab=NewFunTab},
      state__add_work_from_fun(Tree, State1)
  end.

state__add_work_from_fun(_Tree, State = #state{warning_mode=true}) ->
  State;
state__add_work_from_fun(Tree, State = #state{callgraph=Callgraph, 
					      tree_map=TreeMap}) ->
  case get_label(Tree) of
    top -> State;
    Label when is_integer(Label) ->
      case dialyzer_callgraph:in_neighbours(Label, Callgraph) of
	none -> State;
	MFAList ->
	  LabelList = [dialyzer_callgraph:lookup_label(MFA, Callgraph)
		       || MFA <- MFAList],
	  %% Must filter the result for results in this module.	  
	  FilteredList = lists:filter(fun({ok, L})->dict:is_key(