path: root/lib/compiler/src/beam_call_types.erl

%%
%% %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}.