From d4d65c2138cd1fa07185623e42d3b6c1393f086b Mon Sep 17 00:00:00 2001 From: Hans Bolinder Date: Thu, 5 Apr 2012 14:30:03 +0200 Subject: Bug fixes and improvements of dialyzer_typesig 1. Sometimes the solver forgot that a list had entered the error state. The bug has been fixed by storing the atom 'error' in MapDict. An example where the bug occurred is io_lib_pretty:printable_bin(). The returned spec was weaker than it should have been, but the fix-point loop hid the bug (in this case). 2. lists:partition() has been substituted for lists:splitwith() in enumerate_constraints(). This fix together with 3. solves a problem with long execution times for deeply nested fun:s. An example which is now much faster is lib/compiler/test/lc_SUITE:deeply_nested/1 (included as dialyzer/test/small_SUITE_data/src/deep_lc.erl). 3. The calculation of components in enumerate_constraints() has been simplified and optimized. The important thing here is that _all_ of the simple constraints have been saturated before entering the complex part. 4. The pretty printing of constraints has been improved. --- lib/dialyzer/src/dialyzer_typesig.erl | 173 ++++++++++++++++------------------ 1 file changed, 80 insertions(+), 93 deletions(-) (limited to 'lib/dialyzer/src') diff --git a/lib/dialyzer/src/dialyzer_typesig.erl b/lib/dialyzer/src/dialyzer_typesig.erl index 6ee1795fc5..e997eedf76 100644 --- a/lib/dialyzer/src/dialyzer_typesig.erl +++ b/lib/dialyzer/src/dialyzer_typesig.erl @@ -1908,13 +1908,17 @@ solve_ref_or_list(#constraint_list{type=Type, list = Cs, deps = Deps, id = Id}, {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) -> @@ -1923,7 +1927,7 @@ solve_self_recursive(Cs, Map, MapDict, Id, RecType0, 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)]]), + pp_map("Map1", Map1), case solve_ref_or_list(Cs, Map1, MapDict, State) of {error, _} = Error -> case t_is_none(RecType0) of @@ -1936,8 +1940,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 -> @@ -1949,7 +1952,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 [_] -> @@ -1971,7 +1975,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} @@ -2047,6 +2051,8 @@ solve_subtype(Type, Inf, Map, Opaques) -> %% %% ============================================================================ +join_maps([Map]) -> + Map; join_maps(Maps) -> Keys = lists:foldl(fun(TmpMap, AccKeys) -> [Key || Key <- AccKeys, dict:is_key(Key, TmpMap)] @@ -2200,6 +2206,12 @@ mk_var_no_lit(Var) -> mk_var_no_lit_list(List) -> [mk_var_no_lit(X) || X <- List]. +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. @@ -2655,19 +2667,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); @@ -2681,42 +2695,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) -> @@ -2846,13 +2824,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). @@ -2871,12 +2860,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. @@ -2887,51 +2870,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. -- cgit v1.2.3