diff options
Diffstat (limited to 'lib/compiler/src/beam_call_types.erl')
| -rw-r--r-- | lib/compiler/src/beam_call_types.erl | 551 |
1 files changed, 551 insertions, 0 deletions
diff --git a/lib/compiler/src/beam_call_types.erl b/lib/compiler/src/beam_call_types.erl new file mode 100644 index 0000000000..904d82a62d --- /dev/null +++ b/lib/compiler/src/beam_call_types.erl @@ -0,0 +1,551 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2019. All Rights Reserved. +%% +%% Licensed under the Apache License, Version 2.0 (the "License"); +%% you may not use this file except in compliance with the License. +%% You may obtain a copy of the License at +%% +%% http://www.apache.org/licenses/LICENSE-2.0 +%% +%% Unless required by applicable law or agreed to in writing, software +%% distributed under the License is distributed on an "AS IS" BASIS, +%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +%% See the License for the specific language governing permissions and +%% limitations under the License. +%% +%% %CopyrightEnd% +%% + +-module(beam_call_types). + +-include("beam_types.hrl"). + +-import(lists, [duplicate/2,foldl/3]). + +-export([will_succeed/3, types/3]). + +%% +%% Returns whether a call will succeed or not. +%% +%% Note that it only answers 'yes' for functions in the 'erlang' module as +%% calls to other modules may fail due to not being loaded, even if we consider +%% the module to be known. +%% + +-spec will_succeed(Mod, Func, ArgTypes) -> Result when + Mod :: atom(), + Func :: atom(), + ArgTypes :: [normal_type()], + Result :: yes | no | maybe. + +will_succeed(erlang, BoolOp, [LHS, RHS]) when BoolOp =:= 'and'; + BoolOp =:= 'or' -> + case {succeeds_if_type(LHS, beam_types:make_boolean()), + succeeds_if_type(RHS, beam_types:make_boolean())} of + {yes, yes} -> yes; + {no, _} -> no; + {_, no} -> no; + {_, _} -> maybe + end; +will_succeed(erlang, bit_size, [Arg]) -> + succeeds_if_type(Arg, #t_bitstring{}); +will_succeed(erlang, byte_size, [Arg]) -> + succeeds_if_type(Arg, #t_bitstring{}); +will_succeed(erlang, map_size, [Arg]) -> + succeeds_if_type(Arg, #t_map{}); +will_succeed(erlang, 'not', [Arg]) -> + succeeds_if_type(Arg, beam_types:make_boolean()); +will_succeed(erlang, setelement, [#t_integer{elements={Min,Max}}, + #t_tuple{exact=Exact,size=Size}, _]) -> + case Min >= 1 andalso Max =< Size of + true -> yes; + false when Exact -> no; + false -> maybe + end; +will_succeed(erlang, size, [Arg]) -> + succeeds_if_type(Arg, #t_bitstring{}); +will_succeed(erlang, tuple_size, [Arg]) -> + succeeds_if_type(Arg, #t_tuple{}); +will_succeed(Mod, Func, Args) -> + Arity = length(Args), + case erl_bifs:is_safe(Mod, Func, Arity) of + true -> + yes; + false -> + case erl_bifs:is_exit_bif(Mod, Func, Arity) of + true -> no; + false -> maybe + end + end. + +succeeds_if_type(ArgType, Required) -> + case beam_types:meet(ArgType, Required) of + ArgType -> yes; + none -> no; + _ -> maybe + end. + +%% +%% Returns the inferred return and argument types for known functions, and +%% whether it's safe to subtract argument types on failure. +%% +%% Note that the return type will be 'none' if we can statically determine that +%% the function will fail at runtime. +%% + +-spec types(Mod, Func, ArgTypes) -> {RetType, ArgTypes, CanSubtract} when + Mod :: atom(), + Func :: atom(), + ArgTypes :: [normal_type()], + RetType :: type(), + CanSubtract :: boolean(). + +%% Functions that only fail due to bad argument *types*, meaning it's safe to +%% subtract argument types on failure. +%% +%% Note that these are all from the erlang module; suitable functions in other +%% modules could fail due to the module not being loaded. +types(erlang, 'map_size', [_]) -> + sub_safe(#t_integer{}, [#t_map{}]); +types(erlang, 'tuple_size', [_]) -> + sub_safe(#t_integer{}, [#t_tuple{}]); +types(erlang, 'bit_size', [_]) -> + sub_safe(#t_integer{}, [#t_bitstring{}]); +types(erlang, 'byte_size', [_]) -> + sub_safe(#t_integer{}, [#t_bitstring{}]); +types(erlang, 'hd', [_]) -> + sub_safe(any, [cons]); +types(erlang, 'tl', [_]) -> + sub_safe(any, [cons]); +types(erlang, 'length', [_]) -> + sub_safe(#t_integer{}, [list]); +types(erlang, 'not', [_]) -> + Bool = beam_types:make_boolean(), + sub_safe(Bool, [Bool]); + +%% Boolean ops +types(erlang, 'and', [_,_]) -> + Bool = beam_types:make_boolean(), + sub_unsafe(Bool, [Bool, Bool]); +types(erlang, 'or', [_,_]) -> + Bool = beam_types:make_boolean(), + sub_unsafe(Bool, [Bool, Bool]); +types(erlang, 'xor', [_,_]) -> + Bool = beam_types:make_boolean(), + sub_unsafe(Bool, [Bool, Bool]); + +%% Bitwise ops +types(erlang, 'band', [_,_]=Args) -> + sub_unsafe(band_return_type(Args), [#t_integer{}, #t_integer{}]); +types(erlang, 'bor', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bxor', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bsl', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bsr', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'bnot', [_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}]); + +%% Fixed-type arithmetic +types(erlang, 'float', [_]) -> + sub_unsafe(float, [number]); +types(erlang, 'round', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, 'floor', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, 'ceil', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, 'trunc', [_]) -> + sub_unsafe(#t_integer{}, [number]); +types(erlang, '/', [_,_]) -> + sub_unsafe(float, [number, number]); +types(erlang, 'div', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); +types(erlang, 'rem', [_,_]) -> + sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]); + +%% Mixed-type arithmetic; '+'/2 and friends are handled in the catch-all +%% clause for the 'erlang' module. +types(erlang, 'abs', [_]=Args) -> + mixed_arith_types(Args); + +%% List operations +types(erlang, '++', [LHS,RHS]) -> + %% `[] ++ RHS` yields RHS, even if RHS is not a list. + RetType = case {LHS, RHS} of + {cons, _} -> cons; + {_, cons} -> cons; + _ -> beam_types:join(list, RHS) + end, + sub_unsafe(RetType, [list, any]); +types(erlang, '--', [_,_]) -> + sub_unsafe(list, [list, list]); + +%% Misc ops. +types(erlang, 'binary_part', [_, _]) -> + PosLen = make_two_tuple(#t_integer{}, #t_integer{}), + Binary = #t_bitstring{unit=8}, + sub_unsafe(Binary, [Binary, PosLen]); +types(erlang, 'binary_part', [_, _, _]) -> + Binary = #t_bitstring{unit=8}, + sub_unsafe(Binary, [Binary, #t_integer{}, #t_integer{}]); +types(erlang, 'is_map_key', [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [any,#t_map{}]); +types(erlang, 'map_get', [_,_]) -> + sub_unsafe(any, [any,#t_map{}]); +types(erlang, 'node', [_]) -> + sub_unsafe(#t_atom{}, [any]); +types(erlang, 'node', []) -> + sub_unsafe(#t_atom{}, []); +types(erlang, 'size', [_]) -> + sub_unsafe(#t_integer{}, [any]); +types(erlang, 'size', [_]) -> + sub_unsafe(#t_integer{}, [any]); + +%% Tuple element ops +types(erlang, element, [PosType, TupleType]) -> + Index = case PosType of + #t_integer{elements={Same,Same}} when is_integer(Same) -> + Same; + _ -> + 0 + end, + + RetType = case TupleType of + #t_tuple{size=Sz,elements=Es} when Index =< Sz, + Index >= 1 -> + beam_types:get_element_type(Index, Es); + _ -> + any + end, + + sub_unsafe(RetType, [#t_integer{}, #t_tuple{size=Index}]); +types(erlang, setelement, [PosType, TupleType, ArgType]) -> + RetType = case {PosType,TupleType} of + {#t_integer{elements={Index,Index}}, + #t_tuple{elements=Es0,size=Size}=T} when Index >= 1 -> + %% This is an exact index, update the type of said + %% element or return 'none' if it's known to be out of + %% bounds. + Es = beam_types:set_element_type(Index, ArgType, Es0), + case T#t_tuple.exact of + false -> + T#t_tuple{size=max(Index, Size),elements=Es}; + true when Index =< Size -> + T#t_tuple{elements=Es}; + true -> + none + end; + {#t_integer{elements={Min,Max}}, + #t_tuple{elements=Es0,size=Size}=T} when Min >= 1 -> + %% We know this will land between Min and Max, so kill + %% the types for those indexes. + Es = discard_tuple_element_info(Min, Max, Es0), + case T#t_tuple.exact of + false -> + T#t_tuple{elements=Es,size=max(Min, Size)}; + true when Min =< Size -> + T#t_tuple{elements=Es,size=Size}; + true -> + none + end; + {_,#t_tuple{}=T} -> + %% Position unknown, so we have to discard all element + %% information. + T#t_tuple{elements=#{}}; + {#t_integer{elements={Min,_Max}},_} -> + #t_tuple{size=Min}; + {_,_} -> + #t_tuple{} + end, + sub_unsafe(RetType, [#t_integer{}, #t_tuple{}, any]); + +types(erlang, make_fun, [_,_,Arity0]) -> + Type = case Arity0 of + #t_integer{elements={Arity,Arity}} when Arity >= 0 -> + #t_fun{arity=Arity}; + _ -> + #t_fun{} + end, + sub_unsafe(Type, [#t_atom{}, #t_atom{}, #t_integer{}]); + +types(erlang, Name, Args) -> + Arity = length(Args), + + case erl_bifs:is_exit_bif(erlang, Name, Arity) of + true -> + {none, Args, false}; + false -> + case erl_internal:arith_op(Name, Arity) of + true -> + mixed_arith_types(Args); + false -> + IsTest = + erl_internal:new_type_test(Name, Arity) orelse + erl_internal:comp_op(Name, Arity), + + RetType = case IsTest of + true -> beam_types:make_boolean(); + false -> any + end, + + sub_unsafe(RetType, duplicate(Arity, any)) + end + end; + +%% +%% Math BIFs +%% + +types(math, cos, [_]) -> + sub_unsafe(float, [number]); +types(math, cosh, [_]) -> + sub_unsafe(float, [number]); +types(math, sin, [_]) -> + sub_unsafe(float, [number]); +types(math, sinh, [_]) -> + sub_unsafe(float, [number]); +types(math, tan, [_]) -> + sub_unsafe(float, [number]); +types(math, tanh, [_]) -> + sub_unsafe(float, [number]); +types(math, acos, [_]) -> + sub_unsafe(float, [number]); +types(math, acosh, [_]) -> + sub_unsafe(float, [number]); +types(math, asin, [_]) -> + sub_unsafe(float, [number]); +types(math, asinh, [_]) -> + sub_unsafe(float, [number]); +types(math, atan, [_]) -> + sub_unsafe(float, [number]); +types(math, atanh, [_]) -> + sub_unsafe(float, [number]); +types(math, erf, [_]) -> + sub_unsafe(float, [number]); +types(math, erfc, [_]) -> + sub_unsafe(float, [number]); +types(math, exp, [_]) -> + sub_unsafe(float, [number]); +types(math, log, [_]) -> + sub_unsafe(float, [number]); +types(math, log2, [_]) -> + sub_unsafe(float, [number]); +types(math, log10, [_]) -> + sub_unsafe(float, [number]); +types(math, sqrt, [_]) -> + sub_unsafe(float, [number]); +types(math, atan2, [_,_]) -> + sub_unsafe(float, [number, number]); +types(math, pow, [_,_]) -> + sub_unsafe(float, [number, number]); +types(math, ceil, [_]) -> + sub_unsafe(float, [number]); +types(math, floor, [_]) -> + sub_unsafe(float, [number]); +types(math, fmod, [_,_]) -> + sub_unsafe(float, [number, number]); +types(math, pi, []) -> + sub_unsafe(float, []); + +%% +%% List functions +%% + +%% Operator aliases. +types(lists, append, [_,_]=Args) -> + types(erlang, '++', Args); +types(lists, append, [_]) -> + %% This is implemented through folding the list over erlang:'++'/2, so it + %% can hypothetically return anything, but we can infer that its argument + %% is a list on success. + sub_unsafe(any, [list]); +types(lists, subtract, [_,_]) -> + sub_unsafe(list, [list, list]); + +%% Functions returning booleans. +types(lists, all, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [#t_fun{arity=1}, list]); +types(lists, any, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [#t_fun{arity=1}, list]); +types(lists, keymember, [_,_,_]) -> + sub_unsafe(beam_types:make_boolean(), [any, #t_integer{}, list]); +types(lists, member, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [any, list]); +types(lists, prefix, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [list, list]); +types(lists, suffix, [_,_]) -> + sub_unsafe(beam_types:make_boolean(), [list, list]); + +%% Functions returning plain lists. +types(lists, dropwhile, [_,_]) -> + sub_unsafe(list, [#t_fun{arity=1}, list]); +types(lists, duplicate, [_,_]) -> + sub_unsafe(list, [#t_integer{}, any]); +types(lists, filter, [_,_]) -> + sub_unsafe(list, [#t_fun{arity=1}, list]); +types(lists, flatten, [_]) -> + sub_unsafe(list, [list]); +types(lists, map, [_Fun, List]) -> + sub_unsafe(same_length_type(List), [#t_fun{arity=1}, list]); +types(lists, reverse, [List]) -> + sub_unsafe(same_length_type(List), [list]); +types(lists, sort, [List]) -> + sub_unsafe(same_length_type(List), [list]); +types(lists, takewhile, [_,_]) -> + sub_unsafe(list, [#t_fun{arity=1}, list]); +types(lists, usort, [List]) -> + sub_unsafe(same_length_type(List), [list]); +types(lists, zip, [A,B]) -> + ZipType = lists_zip_type([A,B]), + sub_unsafe(ZipType, [ZipType, ZipType]); +types(lists, zip3, [A,B,C]) -> + ZipType = lists_zip_type([A,B,C]), + sub_unsafe(ZipType, [ZipType, ZipType, ZipType]); +types(lists, zipwith, [_,A,B]) -> + ZipType = lists_zip_type([A,B]), + sub_unsafe(ZipType, [#t_fun{arity=2}, ZipType, ZipType]); +types(lists, zipwith3, [_,A,B,C]) -> + ZipType = lists_zip_type([A,B,C]), + sub_unsafe(ZipType, [#t_fun{arity=3}, ZipType, ZipType, ZipType]); + +%% Functions with complex return values. +types(lists, keyfind, [KeyType,PosType,_]) -> + TupleType = case PosType of + #t_integer{elements={Index,Index}} when is_integer(Index), + Index >= 1 -> + Es = beam_types:set_element_type(Index, KeyType, #{}), + #t_tuple{size=Index,elements=Es}; + _ -> + #t_tuple{} + end, + RetType = beam_types:join(TupleType, beam_types:make_atom(false)), + sub_unsafe(RetType, [any, #t_integer{}, list]); +types(lists, MapFold, [_Fun, _Init, List]) + when MapFold =:= mapfoldl; MapFold =:= mapfoldr -> + RetType = make_two_tuple(same_length_type(List), any), + sub_unsafe(RetType, [#t_fun{arity=2}, any, list]); +types(lists, partition, [_,_]) -> + sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); +types(lists, search, [_,_]) -> + TupleType = make_two_tuple(beam_types:make_atom(value), any), + RetType = beam_types:join(TupleType, beam_types:make_atom(false)), + sub_unsafe(RetType, [#t_fun{arity=1}, list]); +types(lists, splitwith, [_,_]) -> + sub_unsafe(make_two_tuple(list, list), [#t_fun{arity=1}, list]); +types(lists, unzip, [List]) -> + ListType = same_length_type(List), + RetType = make_two_tuple(ListType, ListType), + sub_unsafe(RetType, [list]); + +%% Catch-all clause for unknown functions. + +types(_, _, Args) -> + sub_unsafe(any, [any || _ <- Args]). + +%% +%% Helpers +%% + +sub_unsafe(none, ArgTypes) -> + %% This is known to fail at runtime, but the type optimization pass + %% doesn't yet support cutting a block short at any point, so we + %% pretend it's raining instead. + %% + %% Actual exit BIFs get special treatment in the catch-all clause + %% for the 'erlang' module. + sub_unsafe(any, ArgTypes); +sub_unsafe(RetType, ArgTypes) -> + {RetType, ArgTypes, false}. + +sub_safe(RetType, ArgTypes) -> + {RetType, ArgTypes, true}. + +mixed_arith_types([FirstType | _]=Args0) -> + RetType = foldl(fun(#t_integer{}, #t_integer{}) -> #t_integer{}; + (#t_integer{}, number) -> number; + (#t_integer{}, float) -> float; + (float, #t_integer{}) -> float; + (float, number) -> float; + (float, float) -> float; + (number, #t_integer{}) -> number; + (number, float) -> float; + (number, number) -> number; + (any, _) -> number; + (_, _) -> none + end, FirstType, Args0), + sub_unsafe(RetType, [number || _ <- Args0]). + +band_return_type([#t_integer{elements={Int,Int}}, RHS]) when is_integer(Int) -> + band_return_type_1(RHS, Int); +band_return_type([LHS, #t_integer{elements={Int,Int}}]) when is_integer(Int) -> + band_return_type_1(LHS, Int); +band_return_type(_) -> + #t_integer{}. + +band_return_type_1(LHS, Int) -> + case LHS of + #t_integer{elements={Min0,Max0}} when Max0 - Min0 < 1 bsl 256 -> + {Intersection, Union} = range_masks(Min0, Max0), + + Min = Intersection band Int, + Max = min(Max0, Union band Int), + + #t_integer{elements={Min,Max}}; + _ when Int >= 0 -> + %% The range is either unknown or too wide, conservatively assume + %% that the new range is 0 .. Int. + #t_integer{elements={0,Int}}; + _ when Int < 0 -> + %% We can't infer boundaries when the range is unknown and the + %% other operand is a negative number, as the latter sign-extends + %% to infinity and we can't express an inverted range at the + %% moment (cf. X band -8; either less than -7 or greater than 7). + #t_integer{} + end. + +%% Returns two bitmasks describing all possible values between From and To. +%% +%% The first contains the bits that are common to all values, and the second +%% contains the bits that are set by any value in the range. +range_masks(From, To) when From =< To -> + range_masks_1(From, To, 0, -1, 0). + +range_masks_1(From, To, BitPos, Intersection, Union) when From < To -> + range_masks_1(From + (1 bsl BitPos), To, BitPos + 1, + Intersection band From, Union bor From); +range_masks_1(_From, To, _BitPos, Intersection0, Union0) -> + Intersection = To band Intersection0, + Union = To bor Union0, + {Intersection, Union}. + +discard_tuple_element_info(Min, Max, Es) -> + foldl(fun(El, Acc) when Min =< El, El =< Max -> + maps:remove(El, Acc); + (_El, Acc) -> Acc + end, Es, maps:keys(Es)). + +%% For a lists function that return a list of the same length as the input +%% list, return the type of the list. +same_length_type(cons) -> cons; +same_length_type(nil) -> nil; +same_length_type(_) -> list. + +%% lists:zip/2 and friends only succeed when all arguments have the same +%% length, so if one of them is cons, we can infer that all of them are cons +%% on success. +lists_zip_type(Types) -> + foldl(fun(cons, _) -> cons; + (_, cons) -> cons; + (nil, _) -> nil; + (_, T) -> T + end, list, Types). + +make_two_tuple(Type1, Type2) -> + Es0 = beam_types:set_element_type(1, Type1, #{}), + Es = beam_types:set_element_type(2, Type2, Es0), + #t_tuple{size=2,exact=true,elements=Es}. |