diff options
Diffstat (limited to 'lib/hipe/cerl/erl_types.erl')
-rw-r--r-- | lib/hipe/cerl/erl_types.erl | 201 |
1 files changed, 135 insertions, 66 deletions
diff --git a/lib/hipe/cerl/erl_types.erl b/lib/hipe/cerl/erl_types.erl index 32390045e3..4b2bec5fa8 100644 --- a/lib/hipe/cerl/erl_types.erl +++ b/lib/hipe/cerl/erl_types.erl @@ -72,7 +72,7 @@ t_contains_opaque/1, t_contains_opaque/2, t_decorate_with_opaque/3, t_elements/1, - t_find_opaque_mismatch/2, + t_find_opaque_mismatch/3, t_find_unknown_opaque/3, t_fixnum/0, t_map/2, @@ -126,6 +126,8 @@ t_is_instance/2, t_is_integer/1, t_is_integer/2, t_is_list/1, + t_is_map/1, + t_is_map/2, t_is_matchstate/1, t_is_nil/1, t_is_nil/2, t_is_non_neg_integer/1, @@ -148,6 +150,8 @@ t_list/1, t_list_elements/1, t_list_elements/2, t_list_termination/1, + t_map/0, + t_map/1, t_matchstate/0, t_matchstate/2, t_matchstate_present/1, @@ -205,14 +209,11 @@ type_is_defined/4, record_field_diffs_to_string/2, subst_all_vars_to_any/1, + subst_all_remote/2, lift_list_to_pos_empty/1, is_opaque_type/2, is_erl_type/1, - atom_to_string/1, - - t_is_map/2, - t_map/1, - t_map/0 + atom_to_string/1 ]). %%-define(DO_ERL_TYPES_TEST, true). @@ -261,6 +262,8 @@ -define(TAG_IMMED1_SIZE, 4). -define(BITS, (erlang:system_info(wordsize) * 8) - ?TAG_IMMED1_SIZE). +-define(MAX_TUPLE_SIZE, (1 bsl 10)). + %%----------------------------------------------------------------------------- %% Type tags and qualifiers %% @@ -498,9 +501,9 @@ t_contains_opaque(?int_range(_From, _To), _Opaques) -> false; t_contains_opaque(?int_set(_Set), _Opaques) -> false; t_contains_opaque(?list(Type, Tail, _), Opaques) -> t_contains_opaque(Type, Opaques) orelse t_contains_opaque(Tail, Opaques); -t_contains_opaque(?map(Pairs), Opaques) -> - list_contains_opaque([V||{_,V}<-Pairs], Opaques) orelse - list_contains_opaque([K||{K,_}<-Pairs], Opaques); +t_contains_opaque(?map(_) = Map, Opaques) -> + list_contains_opaque(map_values(Map), Opaques) orelse + list_contains_opaque(map_keys(Map), Opaques); t_contains_opaque(?matchstate(_P, _Slots), _Opaques) -> false; t_contains_opaque(?nil, _Opaques) -> false; t_contains_opaque(?number(_Set, _Tag), _Opaques) -> false; @@ -529,39 +532,51 @@ list_contains_opaque(List, Opaques) -> %% The first argument of the function is the pattern and its second %% argument the type we are matching against the pattern. --spec t_find_opaque_mismatch(erl_type(), erl_type()) -> 'error' | {'ok', erl_type(), erl_type()}. +-spec t_find_opaque_mismatch(erl_type(), erl_type(), [erl_type()]) -> + 'error' | {'ok', erl_type(), erl_type()}. -t_find_opaque_mismatch(T1, T2) -> - t_find_opaque_mismatch(T1, T2, T2). +t_find_opaque_mismatch(T1, T2, Opaques) -> + t_find_opaque_mismatch(T1, T2, T2, Opaques). -t_find_opaque_mismatch(?any, _Type, _TopType) -> error; -t_find_opaque_mismatch(?none, _Type, _TopType) -> error; -t_find_opaque_mismatch(?list(T1, Tl1, _), ?list(T2, Tl2, _), TopType) -> - t_find_opaque_mismatch_ordlists([T1, Tl1], [T2, Tl2], TopType); -t_find_opaque_mismatch(_T1, ?opaque(_) = T2, TopType) -> {ok, TopType, T2}; -t_find_opaque_mismatch(?opaque(_) = T1, _T2, TopType) -> +t_find_opaque_mismatch(?any, _Type, _TopType, _Opaques) -> error; +t_find_opaque_mismatch(?none, _Type, _TopType, _Opaques) -> error; +t_find_opaque_mismatch(?list(T1, Tl1, _), ?list(T2, Tl2, _), TopType, Opaques) -> + t_find_opaque_mismatch_ordlists([T1, Tl1], [T2, Tl2], TopType, Opaques); +t_find_opaque_mismatch(T1, ?opaque(_) = T2, TopType, Opaques) -> + case is_opaque_type(T2, Opaques) of + false -> {ok, TopType, T2}; + true -> + t_find_opaque_mismatch(T1, t_opaque_structure(T2), TopType, Opaques) + end; +t_find_opaque_mismatch(?opaque(_) = T1, T2, TopType, Opaques) -> %% The generated message is somewhat misleading: - {ok, TopType, T1}; -t_find_opaque_mismatch(?product(T1), ?product(T2), TopType) -> - t_find_opaque_mismatch_ordlists(T1, T2, TopType); -t_find_opaque_mismatch(?tuple(T1, Arity, _), ?tuple(T2, Arity, _), TopType) -> - t_find_opaque_mismatch_ordlists(T1, T2, TopType); -t_find_opaque_mismatch(?tuple(_, _, _) = T1, ?tuple_set(_) = T2, TopType) -> + case is_opaque_type(T1, Opaques) of + false -> {ok, TopType, T1}; + true -> + t_find_opaque_mismatch(t_opaque_structure(T1), T2, TopType, Opaques) + end; +t_find_opaque_mismatch(?product(T1), ?product(T2), TopType, Opaques) -> + t_find_opaque_mismatch_ordlists(T1, T2, TopType, Opaques); +t_find_opaque_mismatch(?tuple(T1, Arity, _), ?tuple(T2, Arity, _), + TopType, Opaques) -> + t_find_opaque_mismatch_ordlists(T1, T2, TopType, Opaques); +t_find_opaque_mismatch(?tuple(_, _, _) = T1, ?tuple_set(_) = T2, + TopType, Opaques) -> Tuples1 = t_tuple_subtypes(T1), Tuples2 = t_tuple_subtypes(T2), - t_find_opaque_mismatch_lists(Tuples1, Tuples2, TopType); -t_find_opaque_mismatch(T1, ?union(U2), TopType) -> - t_find_opaque_mismatch_lists([T1], U2, TopType); -t_find_opaque_mismatch(_T1, _T2, _TopType) -> error. + t_find_opaque_mismatch_lists(Tuples1, Tuples2, TopType, Opaques); +t_find_opaque_mismatch(T1, ?union(U2), TopType, Opaques) -> + t_find_opaque_mismatch_lists([T1], U2, TopType, Opaques); +t_find_opaque_mismatch(_T1, _T2, _TopType, _Opaques) -> error. -t_find_opaque_mismatch_ordlists(L1, L2, TopType) -> +t_find_opaque_mismatch_ordlists(L1, L2, TopType, Opaques) -> List = lists:zipwith(fun(T1, T2) -> - t_find_opaque_mismatch(T1, T2, TopType) + t_find_opaque_mismatch(T1, T2, TopType, Opaques) end, L1, L2), t_find_opaque_mismatch_list(List). -t_find_opaque_mismatch_lists(L1, L2, _TopType) -> - List = [t_find_opaque_mismatch(T1, T2, T2) || T1 <- L1, T2 <- L2], +t_find_opaque_mismatch_lists(L1, L2, _TopType, Opaques) -> + List = [t_find_opaque_mismatch(T1, T2, T2, Opaques) || T1 <- L1, T2 <- L2], t_find_opaque_mismatch_list(List). t_find_opaque_mismatch_list([]) -> error; @@ -614,7 +629,7 @@ t_decorate_with_opaque(T1, T2, Opaques) -> end end. -decorate(?none=Type, _, _Opaques) -> Type; +decorate(Type, ?none, _Opaques) -> Type; decorate(?function(Domain, Range), ?function(D, R), Opaques) -> ?function(decorate(Domain, D, Opaques), decorate(Range, R, Opaques)); decorate(?list(Types, Tail, Size), ?list(Ts, Tl, _Sz), Opaques) -> @@ -680,6 +695,7 @@ union_decorate(U1, U2, Opaques) -> List = [A,B,F,I,L,N,T,M,Map], DecList = [Dec || E <- List, + not t_is_none(E), not t_is_none(Dec = decorate(E, Opaque, Opaques))], t_sup([Union|DecList]). @@ -1421,7 +1437,6 @@ t_number_vals(Type) -> t_number_vals(Type, Opaques) -> do_opaque(Type, Opaques, fun number_vals/1). -number_vals(?int_set(?any)) -> unknown; number_vals(?int_set(Set)) -> set_to_list(Set); number_vals(?number(_, _)) -> unknown; number_vals(?opaque(_)) -> unknown; @@ -1728,11 +1743,16 @@ lift_list_to_pos_empty(?list(Content, Termination, _)) -> t_map() -> ?map([]). --spec t_map([{erl_type(),erl_type()}]) -> erl_type(). +-spec t_map([{erl_type(), erl_type()}]) -> erl_type(). t_map(_) -> ?map([]). +-spec t_is_map(erl_type()) -> boolean(). + +t_is_map(Type) -> + t_is_map(Type, 'universe'). + -spec t_is_map(erl_type(), opaques()) -> boolean(). t_is_map(Type, Opaques) -> @@ -1741,7 +1761,6 @@ t_is_map(Type, Opaques) -> is_map1(?map(_)) -> true; is_map1(_) -> false. - %%----------------------------------------------------------------------------- %% Tuples %% @@ -1753,6 +1772,8 @@ t_tuple() -> -spec t_tuple(non_neg_integer() | [erl_type()]) -> erl_type(). +t_tuple(N) when is_integer(N), N > ?MAX_TUPLE_SIZE -> + t_tuple(); t_tuple(N) when is_integer(N) -> ?tuple(lists:duplicate(N, ?any), N, ?any); t_tuple(List) -> @@ -2089,6 +2110,8 @@ t_has_var(?tuple(Elements, _, _)) -> t_has_var_list(Elements); t_has_var(?tuple_set(_) = T) -> t_has_var_list(t_tuple_subtypes(T)); +t_has_var(?map(_)= Map) -> + t_has_var_list(map_keys(Map)) orelse t_has_var_list(map_values(Map)); t_has_var(?opaque(Set)) -> %% Assume variables in 'args' are also present i 'struct' t_has_var_list([O#opaque.struct || O <- set_to_list(Set)]); @@ -2116,21 +2139,28 @@ t_collect_vars(?function(Domain, Range), Acc) -> t_collect_vars(?list(Contents, Termination, _), Acc) -> ordsets:union(t_collect_vars(Contents, Acc), t_collect_vars(Termination, [])); t_collect_vars(?product(Types), Acc) -> - lists:foldl(fun(T, TmpAcc) -> t_collect_vars(T, TmpAcc) end, Acc, Types); + t_collect_vars_list(Types, Acc); t_collect_vars(?tuple(?any, ?any, ?any), Acc) -> Acc; t_collect_vars(?tuple(Types, _, _), Acc) -> - lists:foldl(fun(T, TmpAcc) -> t_collect_vars(T, TmpAcc) end, Acc, Types); + t_collect_vars_list(Types, Acc); t_collect_vars(?tuple_set(_) = TS, Acc) -> - lists:foldl(fun(T, TmpAcc) -> t_collect_vars(T, TmpAcc) end, Acc, - t_tuple_subtypes(TS)); + t_collect_vars_list(t_tuple_subtypes(TS), Acc); +t_collect_vars(?map(_) = Map, Acc0) -> + Acc = t_collect_vars_list(map_keys(Map), Acc0), + t_collect_vars_list(map_values(Map), Acc); t_collect_vars(?opaque(Set), Acc) -> %% Assume variables in 'args' are also present i 'struct' - lists:foldl(fun(T, TmpAcc) -> t_collect_vars(T, TmpAcc) end, Acc, - [O#opaque.struct || O <- set_to_list(Set)]); + t_collect_vars_list([O#opaque.struct || O <- set_to_list(Set)], Acc); +t_collect_vars(?union(List), Acc) -> + t_collect_vars_list(List, Acc); t_collect_vars(_, Acc) -> Acc. +t_collect_vars_list([T|Ts], Acc0) -> + Acc = t_collect_vars(T, Acc0), + t_collect_vars_list(Ts, Acc); +t_collect_vars_list([], Acc) -> Acc. %%============================================================================= %% @@ -2153,6 +2183,7 @@ t_from_term(T) when is_function(T) -> {arity, Arity} = erlang:fun_info(T, arity), t_fun(Arity, t_any()); t_from_term(T) when is_integer(T) -> t_integer(T); +t_from_term(T) when is_map(T) -> t_map(); t_from_term(T) when is_pid(T) -> t_pid(); t_from_term(T) when is_port(T) -> t_port(); t_from_term(T) when is_reference(T) -> t_reference(); @@ -2555,7 +2586,7 @@ force_union(T = ?function(_, _)) -> ?function_union(T); force_union(T = ?identifier(_)) -> ?identifier_union(T); force_union(T = ?list(_, _, _)) -> ?list_union(T); force_union(T = ?nil) -> ?list_union(T); -force_union(T = ?number(_,_)) -> ?number_union(T); +force_union(T = ?number(_, _)) -> ?number_union(T); force_union(T = ?opaque(_)) -> ?opaque_union(T); force_union(T = ?remote(_)) -> ?remote_union(T); force_union(T = ?map(_)) -> ?map_union(T); @@ -2970,16 +3001,19 @@ inf_union(U1, U2, Opaques) -> List = [A,B,F,I,L,N,T,M,Map], inf_union_collect(List, Opaque, InfFun, [], []) end, - O1 = OpaqueFun(U1, U2, fun(E, Opaque) -> t_inf(Opaque, E, Opaques) end), - O2 = OpaqueFun(U2, U1, fun(E, Opaque) -> t_inf(E, Opaque, Opaques) end), - Union = inf_union(U1, U2, 0, [], Opaques), - t_sup([O1, O2, Union]). + {O1, ThrowList1} = + OpaqueFun(U1, U2, fun(E, Opaque) -> t_inf(Opaque, E, Opaques) end), + {O2, ThrowList2} + = OpaqueFun(U2, U1, fun(E, Opaque) -> t_inf(E, Opaque, Opaques) end), + {Union, ThrowList3} = inf_union(U1, U2, 0, [], [], Opaques), + ThrowList = lists:merge3(ThrowList1, ThrowList2, ThrowList3), + case t_sup([O1, O2, Union]) of + ?none when ThrowList =/= [] -> throw(hd(ThrowList)); + Sup -> Sup + end. inf_union_collect([], _Opaque, _InfFun, InfList, ThrowList) -> - case t_sup(InfList) of - ?none when ThrowList =/= [] -> throw(hd(lists:flatten(ThrowList))); - Sup -> Sup - end; + {t_sup(InfList), lists:usort(ThrowList)}; inf_union_collect([?none|L], Opaque, InfFun, InfList, ThrowList) -> inf_union_collect(L, Opaque, InfFun, [?none|InfList], ThrowList); inf_union_collect([E|L], Opaque, InfFun, InfList, ThrowList) -> @@ -2990,19 +3024,21 @@ inf_union_collect([E|L], Opaque, InfFun, InfList, ThrowList) -> inf_union_collect(L, Opaque, InfFun, InfList, [N|ThrowList]) end. -inf_union([?none|Left1], [?none|Left2], N, Acc, Opaques) -> - inf_union(Left1, Left2, N, [?none|Acc], Opaques); -inf_union([T1|Left1], [T2|Left2], N, Acc, Opaques) -> - case t_inf(T1, T2, Opaques) of - ?none -> inf_union(Left1, Left2, N, [?none|Acc], Opaques); - T -> inf_union(Left1, Left2, N+1, [T|Acc], Opaques) +inf_union([?none|Left1], [?none|Left2], N, Acc, ThrowList, Opaques) -> + inf_union(Left1, Left2, N, [?none|Acc], ThrowList, Opaques); +inf_union([T1|Left1], [T2|Left2], N, Acc, ThrowList, Opaques) -> + try t_inf(T1, T2, Opaques) of + ?none -> inf_union(Left1, Left2, N, [?none|Acc], ThrowList, Opaques); + T -> inf_union(Left1, Left2, N+1, [T|Acc], ThrowList, Opaques) + catch throw:N when is_integer(N) -> + inf_union(Left1, Left2, N, [?none|Acc], [N|ThrowList], Opaques) end; -inf_union([], [], N, Acc, _Opaques) -> - if N =:= 0 -> ?none; +inf_union([], [], N, Acc, ThrowList, _Opaques) -> + if N =:= 0 -> {?none, ThrowList}; N =:= 1 -> [Type] = [T || T <- Acc, T =/= ?none], - Type; - N >= 2 -> ?union(lists:reverse(Acc)) + {Type, ThrowList}; + N >= 2 -> {?union(lists:reverse(Acc)), ThrowList} end. inf_bitstr(U1, B1, U2, B2) -> @@ -3076,6 +3112,9 @@ t_subst_dict(?tuple(Elements, _Arity, _Tag), Dict) -> t_tuple([t_subst_dict(E, Dict) || E <- Elements]); t_subst_dict(?tuple_set(_) = TS, Dict) -> t_sup([t_subst_dict(T, Dict) || T <- t_tuple_subtypes(TS)]); +t_subst_dict(?map(Pairs), Dict) -> + ?map([{t_subst_dict(K, Dict), t_subst_dict(V, Dict)} || + {K, V} <- Pairs]); t_subst_dict(?opaque(Es), Dict) -> List = [Opaque#opaque{args = [t_subst_dict(Arg, Dict) || Arg <- Args], struct = t_subst_dict(S, Dict)} || @@ -3125,6 +3164,9 @@ t_subst_aux(?tuple(Elements, _Arity, _Tag), VarMap) -> t_tuple([t_subst_aux(E, VarMap) || E <- Elements]); t_subst_aux(?tuple_set(_) = TS, VarMap) -> t_sup([t_subst_aux(T, VarMap) || T <- t_tuple_subtypes(TS)]); +t_subst_aux(?map(Pairs), VarMap) -> + ?map([{t_subst_aux(K, VarMap), t_subst_aux(V, VarMap)} || + {K, V} <- Pairs]); t_subst_aux(?opaque(Es), VarMap) -> List = [Opaque#opaque{args = [t_subst_aux(Arg, VarMap) || Arg <- Args], struct = t_subst_aux(S, VarMap)} || @@ -3135,6 +3177,18 @@ t_subst_aux(?union(List), VarMap) -> t_subst_aux(T, _VarMap) -> T. +-spec subst_all_remote(erl_type(), erl_type()) -> erl_type(). + +subst_all_remote(Type0, Substitute) -> + Map = + fun(Type) -> + case erl_types:t_is_remote(Type) of + true -> Substitute; + false -> Type + end + end, + erl_types:t_map(Map, Type0). + %%----------------------------------------------------------------------------- %% Unification %% @@ -3560,6 +3614,8 @@ t_subtract(?product(Elements1) = T1, ?product(Elements2)) -> _ -> T1 end end; +t_subtract(?map(_) = T, _) -> % XXX: very crude; will probably need refinement + T; t_subtract(?product(P1), _) -> ?product(P1); t_subtract(T, ?product(_)) -> @@ -3700,7 +3756,7 @@ t_unopaque(T) -> t_unopaque(?opaque(_) = T, Opaques) -> case Opaques =:= 'universe' orelse is_opaque_type(T, Opaques) of true -> t_unopaque(t_opaque_structure(T), Opaques); - false -> T % XXX: needs revision for parametric opaque data types + false -> T end; t_unopaque(?list(ElemT, Termination, Sz), Opaques) -> ?list(t_unopaque(ElemT, Opaques), t_unopaque(Termination, Opaques), Sz); @@ -3720,11 +3776,12 @@ t_unopaque(?union([A,B,F,I,L,N,T,M,O,R,Map]), Opaques) -> UL = t_unopaque(L, Opaques), UT = t_unopaque(T, Opaques), UF = t_unopaque(F, Opaques), + UMap = t_unopaque(Map, Opaques), {OF,UO} = case t_unopaque(O, Opaques) of ?opaque(_) = O1 -> {O1, []}; Type -> {?none, [Type]} end, - t_sup([?union([A,B,UF,I,UL,N,UT,M,OF,R,Map])|UO]); + t_sup([?union([A,B,UF,I,UL,N,UT,M,OF,R,UMap])|UO]); t_unopaque(T, _) -> T. @@ -4231,8 +4288,8 @@ t_from_form({type, _L, list, []}, _TypeNames, _RecDict, _VarDict) -> t_from_form({type, _L, list, [Type]}, TypeNames, RecDict, VarDict) -> {T, R} = t_from_form(Type, TypeNames, RecDict, VarDict), {t_list(T), R}; -t_from_form({type, _L, map, _}, _TypeNames, _RecDict, _VarDict) -> - {t_map([]), []}; +t_from_form({type, _L, map, _}, TypeNames, RecDict, VarDict) -> + builtin_type(map, t_map([]), TypeNames, RecDict, VarDict); t_from_form({type, _L, mfa, []}, _TypeNames, _RecDict, _VarDict) -> {t_mfa(), []}; t_from_form({type, _L, module, []}, _TypeNames, _RecDict, _VarDict) -> @@ -4445,7 +4502,9 @@ get_mod_record([{FieldName, DeclType}|Left1], [{FieldName, ModType}|Left2], Acc) -> ModTypeNoVars = subst_all_vars_to_any(ModType), case - t_is_remote(ModTypeNoVars) orelse t_is_subtype(ModTypeNoVars, DeclType) + contains_remote(ModTypeNoVars) + orelse contains_remote(DeclType) + orelse t_is_subtype(ModTypeNoVars, DeclType) of false -> {error, FieldName}; true -> get_mod_record(Left1, Left2, [{FieldName, ModType}|Acc]) @@ -4459,6 +4518,10 @@ get_mod_record(DeclFields, [], Acc) -> get_mod_record(_, [{FieldName2, _ModType}|_], _Acc) -> {error, FieldName2}. +contains_remote(Type) -> + TypeNoRemote = subst_all_remote(Type, t_none()), + not t_is_equal(Type, TypeNoRemote). + fields_from_form([], _TypeNames, _RecDict, _VarDict) -> {[], []}; fields_from_form([{Name, Type}|Tail], TypeNames, RecDict, @@ -4695,6 +4758,12 @@ is_same_type_name2(gb_trees, gb_tree, [], gb_trees, tree, [_, _]) -> true; is_same_type_name2(gb_trees, tree, [_, _], gb_trees, gb_tree, []) -> true; is_same_type_name2(_, _, _, _, _, _) -> false. +map_keys(?map(Pairs)) -> + [K || {K, _} <- Pairs]. + +map_values(?map(Pairs)) -> + [V || {_, V} <- Pairs]. + %% ----------------------------------- %% Set %% |