dialyzer_dataflow.erl

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

%% -*- erlang-indent-level: 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_dataflow.erl
%%% Author  : Tobias Lindahl <[e-mail]>
%%% Description : 
%%%
%%% Created : 19 Apr 2005 by Tobias Lindahl <[e-mail]>
%%%-------------------------------------------------------------------
-module(dialyzer_dataflow).

-include("dialyzer.hrl").

-import(erl_types, 
	[t_any/0, t_atom/0, t_atom/1, t_binary/0, t_bool/0, t_cons/0, t_cons/2,
	 t_cons_hd/1, t_cons_tl/1, t_components/1, t_float/0,
	 t_from_range/2, t_fun/0, t_fun/2, t_fun_args/1, t_fun_range/1,
	 t_inf/2, t_inf_lists/2, t_integer/0, t_is_integer/1, t_is_nil/1,
	 t_is_atom/1, t_is_atom/2, t_is_bool/1, t_is_unit/1,
	 t_atom_vals/1, t_is_equal/2, t_is_none/1, t_is_none_or_unit/1,
	 t_is_any/1, t_is_subtype/2, t_limit/2, t_list/0,
	 t_non_neg_integer/0, t_number/0, t_number_vals/1, t_pid/0, t_port/0,
	 t_pos_improper_list/0,
	 t_product/1, t_ref/0, t_to_string/2, t_to_string/1,
	 t_tuple/0, t_tuple/1, t_tuple_args/1,
	 t_tuple_subtypes/1, t_sup/1, t_sup/2, t_subtract/2,
	 t_from_term/1, t_none/0, t_unit/0]).


-export([annotate_module/2,
	 doit/1,
	 doit/2,
	 get_fun_types/4,
	 get_top_level_signatures/2,
	 get_warnings/5,
	 pp/1]).

%-define(DEBUG, true).
%-define(DEBUG_NAME_MAP, true).
%-define(DEBUG_PP, true).
%-define(DEBUG_TIME, true).
%-define(DOT, true).

-ifdef(DEBUG).
-define(debug(S_, L_), io:format(S_, L_)).
-else.
-define(debug(S_, L_), ok).
-endif.

%-define(debug1(S_, L_), io:format(S_, L_)).
%-define(debug1(S_, L_), ok).

-define(TYPE_LIMIT, 3).


pp(File) ->
  Code = dialyzer_utils:get_core_from_src(File, [no_copt]),
  Plt = get_def_plt(),
  AnnTree = annotate_module(Code, Plt),
  dialyzer_plt:delete(Plt),
  io:put_chars(cerl_prettypr:format(AnnTree, [{hook, cerl_typean:pp_hook()}])),
  io:nl().

get_warnings(Tree, Plt, Callgraph, Records, NoWarnUnused) ->
  State = analyze_module(Tree, Plt, Callgraph, Records, true),
  {state__get_warnings(State, NoWarnUnused), state__all_fun_types(State)}.

get_fun_types(Tree, Plt, Callgraph, Records) ->
  debug_build_namemap(Tree),
  State = analyze_module(Tree, Plt, Callgraph, Records, false),
  state__all_fun_types(State).

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(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_typesig_plt, 
			   filename:join([code:lib_dir(dialyzer),
					  "plt","dialyzer_init_plt"]))
  catch
    throw:{dialyzer_error, _} -> ets:new(dialyzer_typesig_plt, [])
  end.

doit(Module) ->
  doit(Module, [no_copt]).

doit(Module, Opts) ->
  AbstrCode = dialyzer_utils:get_abstract_code_from_src(Module, Opts),
  Code = dialyzer_utils:get_core_from_abstract_code(AbstrCode, Opts),
  {ok, Records} = dialyzer_utils:get_record_info(AbstrCode),
  Sigs = get_top_level_signatures(Code, Records),
  [io:format("~w/~w :: ~s\n", [F, A, t_to_string(T, Records)])
   || {{F, A}, T} <- Sigs].

%%% ============================================================================
%%%
%%%  Annotate all top level funs.
%%%
%%% ============================================================================

annotate_module(Code, Plt) ->
  {Tree, _} = cerl_trees:label(cerl:from_records(Code)),
  debug_build_namemap(Tree),
  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 is_tuple(X), 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 is_tuple(X), size(X) >= 1, element(1, X) =:= Tag -> 
      delete_ann(Tag, Xs);
     true ->
      [X | delete_ann(Tag, Xs)]
  end;
delete_ann(_, []) ->
  [].

%%% ============================================================================
%%%
%%%  The analysis.
%%%
%%% ============================================================================

analyze_module(Tree, Plt, Callgraph) ->
  analyze_module(Tree, Plt, Callgraph, dict:new(), false).

analyze_module(Tree, Plt, Callgraph, Records, GetWarnings) ->
  debug_pp(Tree, false),
  TopFun =  cerl:ann_c_fun([{label, top}], [], Tree),
  case GetWarnings of
    true ->
      State = state__new(Callgraph, TopFun, Plt, Records, unconstrained),
      State1 = analyze_loop(State),
      State2 = state__set_warning_mode(State1),
      analyze_loop(State2);
    false ->
      State = state__new(Callgraph, TopFun, Plt, Records, constrained),
      analyze_loop(State)
  end.

analyze_loop(State) ->
  case state__get_work(State) of
    none -> state__clean_not_called(State);
    {Fun, NewState} ->
      ArgTypes = state__get_args(Fun, NewState),
      case any_none(ArgTypes) of
	true -> 
	  ?debug("Not handling1 ~w: ~s\n", [debug_lookup_name(get_label(Fun)), 
					   t_to_string(t_product(ArgTypes))]),
	  analyze_loop(NewState);
	false -> 
	  case state__fun_env(Fun, NewState) of
	    none -> 
	      ?debug("Not handling2 ~w: ~s\n", 
		     [debug_lookup_name(get_label(Fun)), 
		      t_to_string(t_product(ArgTypes))]),
	      analyze_loop(NewState);
	    {Map, DefVars} ->
	      ?debug("Handling fun ~p: ~s\n", 
		     [debug_lookup_name(get_label(Fun)), 
		      t_to_string(state__fun_type(Fun, NewState))]),
	      NewState1 = state__mark_fun_as_handled(NewState, Fun),
	      Vars = cerl:fun_vars(Fun),
	      Map1 = enter_type_lists(Vars, ArgTypes, Map),
	      Body = cerl:fun_body(Fun),
	      DefVars1 = add_def_vars(Vars, DefVars),
	      {NewState2, _Map2, BodyType} = 
		traverse(Body, Map1, DefVars1, NewState1),
	      ?debug("Done analyzing: ~w:~s\n", 
		     [debug_lookup_name(get_label(Fun)),
		      t_to_string(t_fun(ArgTypes, BodyType))]),
	      NewState3 =
		state__update_fun_entry(Fun, ArgTypes, BodyType, NewState2),
	      ?debug("done adding stuff for ~w\n", 
		     [debug_lookup_name(get_label(Fun))]),
	      analyze_loop(NewState3)
	  end
      end
  end.

traverse(Tree, Map, DefVars, State) ->
  ?debug("Handling ~p\n", [cerl:type(Tree)]),
  %%debug_pp_map(Map),
  case cerl:type(Tree) of
    apply ->
      Args = cerl:apply_args(Tree),
      Op = cerl:apply_op(Tree),
      {State1, Map1, ArgTypes} = traverse_list(Args, Map, DefVars, State),
      case state__handle_apply(Tree, ArgTypes, State1) of
	unknown ->
	  {State2, Map2, OpType} = traverse(Op, Map1, DefVars, State1),
	  %% This is an externally defined closure
	  OpType1 = t_inf(OpType, t_fun(length(Args), t_any())),
	  case t_is_none(OpType1) of
	    true ->
	      {State2, Map2, t_none()};
	    false ->
	      OpRange = t_fun_range(OpType1),
	      {State2, enter_type(Op, OpType1, Map2), OpRange}
	  end;
	{failed, {MFA, Sig}} ->
	  State2 = 
	    case any_none(lists:flatten([t_fun_range(Sig), t_fun_args(Sig)])) of
	      true -> State1;
	      false ->
		Msg =
		  case MFA of
		    {M, F, A} ->
		      io_lib:format("The call ~w:~w~s "
				    "will fail since the signature is "
				    "~w:~w/~w :: ~s\n",
				    [M, F, format_args(Args, ArgTypes, State),
				     M, F, A, t_to_string(Sig)]);
		    Label when is_integer(Label) ->
		      io_lib:format("Fun application of function with "
				    "signature ~s will fail since the "
				    "arguments are ~s\n",
				    [Sig, format_args(Args, ArgTypes, State)])
		  end,
		state__add_warning(State1, ?WARN_FAILING_CALL, Tree, Msg)
	    end,
	  {State2, Map1, t_none()};
	{NewArgTypes, Return} ->
	  State2 =
	    case state__warning_mode(State1) of
	      true -> State1;
	      false ->
		case state__forward_mode(State1) of
		  unconstrained -> state__forward_args(Tree, ArgTypes, State1);
		  constrained -> state__forward_args(Tree, NewArgTypes, State1)
		end
	    end,
	  Map2 = enter_type_lists(Args, NewArgTypes, Map1),
	  {State2, Map2, Return}
      end;
    binary ->
      Segs = cerl:binary_segments(Tree),
      {State1, Map1, SegTypes} = traverse_list(Segs, Map, DefVars, State),
      case any_none(SegTypes) of
	true -> {State1, Map1, t_none()};
	false -> {State1, Map1, t_binary()}
      end;
    bitstr ->
      %% NOTE! This should only be used for matchings!
      Size = cerl:bitstr_size(Tree),
      Val = cerl:bitstr_val(Tree),
      {State1, Map1, SizeType0} = traverse(Size, Map, DefVars, State),
      {State2, Map2, ValType} = traverse(Val, Map1, DefVars, State1),
      {ValType0, SizeType} =
	case cerl:concrete(cerl:bitstr_type(Tree)) of
	  float -> 
	    Inf = t_inf(SizeType0, t_non_neg_integer()),
	    case t_is_none(Inf) of
	      true -> {t_none(), t_none()};
	      false -> {t_number(), Inf}
	    end;
	  binary -> 
	    Inf = t_inf(SizeType0, t_non_neg_integer()),
	    case t_is_none(Inf) of
	      true -> 
		case (cerl:is_c_atom(Size) 
		      andalso (cerl:concrete(Size) =:= all)) of
		  true -> {t_binary(), SizeType0};
		  false -> {t_none(), t_none()}
		end;
	      false -> {t_binary(), Inf}
	    end;
	  integer ->
	    Inf = t_inf(SizeType0, t_non_neg_integer()),
	    case t_is_none(Inf) of
	      true -> {t_none(), t_none()};
	      false -> {t_integer(), Inf}
	    end
	end,
      Type = t_inf(ValType0, ValType),
      Map3 = enter_type(Val, Type, Map2),
      Map4 = enter_type(Size, SizeType, Map3),
      {State2, Map4, Type};
    call ->
      M = cerl:call_module(Tree),
      F = cerl:call_name(Tree),
      Args = cerl:call_args(Tree),
      MFAList = [M, F|Args],
      {State1, Map1, [MType0, FType0|As]} = 
	traverse_list(MFAList, Map, DefVars, State),
      MType = t_inf(t_atom(), MType0),
      FType = t_inf(t_atom(), FType0),
      case any_none([MType, FType|As]) of
	true ->
	  {State1, Map1, t_none()};
	false ->
	  %% XXX: Consider doing this for all combinations of MF
	  case {t_atom_vals(MType), t_atom_vals(FType)} of
	    {[MAtom], [FAtom]} ->
	      {State2, Return, NewArgs} =
		case do_call(MAtom, FAtom, As, State) of
		  {failed, Sig} ->
		    A = length(As),
		    Msg =
		      io_lib:format("The call ~w:~w~s "
				    "will fail since the signature is "
				    "~w:~w/~w :: ~s\n",
				    [MAtom, FAtom, format_args(Args, As, State),
				     MAtom, FAtom, A, t_to_string(Sig)]),
		    {state__add_warning(State1, ?WARN_FAILING_CALL, Tree, Msg),
		     t_none(), duplicate(A, t_none())};
		  {Ret, NewArgs0} -> {State1, Ret, NewArgs0}
		end,
	      Map2 = enter_type_lists(cerl:call_args(Tree), NewArgs, Map1),
	      {State2, Map2, Return};
	    {_MAtoms, _FAtoms} ->
	      {State1, Map1, t_any()}
	  end
      end;
    'case' ->
      Arg = cerl:case_arg(Tree),
      Clauses = filter_match_fail(cerl:case_clauses(Tree)),
      {State1, Map1, ArgType} = traverse(Arg, Map, DefVars, State),
      ArgComps = wrap_if_single(t_components(ArgType)),
      case any_none(ArgComps) of
	true -> {State1, Map1, t_none()};
	false ->
	  case any_unit(ArgComps) of
	    true -> {State1, Map1, t_unit()};
	    false ->
	      {MapList, State2, Type} = 
		handle_clauses(Clauses, Arg, ArgType, ArgType, State1, 
			       [], Map1, DefVars, []),
	      Map2 = join_maps(MapList, Map1),
	      debug_pp_map(Map2),
	      {State2, Map2, Type}