1%%
2%% %CopyrightBegin%
3%%
4%% Copyright Ericsson AB 2019. All Rights Reserved.
5%%
6%% Licensed under the Apache License, Version 2.0 (the "License");
7%% you may not use this file except in compliance with the License.
8%% You may obtain a copy of the License at
9%%
10%%     http://www.apache.org/licenses/LICENSE-2.0
11%%
12%% Unless required by applicable law or agreed to in writing, software
13%% distributed under the License is distributed on an "AS IS" BASIS,
14%% WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15%% See the License for the specific language governing permissions and
16%% limitations under the License.
17%%
18%% %CopyrightEnd%
19%%
20
21-module(beam_call_types).
22
23-include("beam_types.hrl").
24
25-import(lists, [duplicate/2,foldl/3]).
26
27-export([will_succeed/3, types/3]).
28
29%%
30%% Returns whether a call will succeed or not.
31%%
32%% Note that it only answers 'yes' for functions in the 'erlang' module as
33%% calls to other modules may fail due to not being loaded, even if we consider
34%% the module to be known.
35%%
36
37-spec will_succeed(Mod, Func, ArgTypes) -> Result when
38      Mod :: atom(),
39      Func :: atom(),
40      ArgTypes :: [normal_type()],
41      Result :: yes | no | maybe.
42
43will_succeed(erlang, '++', [LHS, _RHS]) ->
44    succeeds_if_type(LHS, proper_list());
45will_succeed(erlang, '--', [LHS, RHS]) ->
46    case {succeeds_if_type(LHS, proper_list()),
47          succeeds_if_type(RHS, proper_list())} of
48        {yes, yes} -> yes;
49        {no, _} -> no;
50        {_, no} -> no;
51        {_, _} -> maybe
52    end;
53will_succeed(erlang, BoolOp, [LHS, RHS]) when BoolOp =:= 'and';
54                                              BoolOp =:= 'or' ->
55    case {succeeds_if_type(LHS, beam_types:make_boolean()),
56          succeeds_if_type(RHS, beam_types:make_boolean())} of
57        {yes, yes} -> yes;
58        {no, _} -> no;
59        {_, no} -> no;
60        {_, _} -> maybe
61    end;
62will_succeed(erlang, bit_size, [Arg]) ->
63    succeeds_if_type(Arg, #t_bitstring{});
64will_succeed(erlang, byte_size, [Arg]) ->
65    succeeds_if_type(Arg, #t_bitstring{});
66will_succeed(erlang, hd, [Arg]) ->
67    succeeds_if_type(Arg, #t_cons{});
68will_succeed(erlang, is_function, [_,#t_integer{elements={Min,_}}])
69  when Min >= 0 ->
70    yes;
71will_succeed(erlang, is_map_key, [_Key, Map]) ->
72    succeeds_if_type(Map, #t_map{});
73will_succeed(erlang, length, [Arg]) ->
74    succeeds_if_type(Arg, proper_list());
75will_succeed(erlang, map_size, [Arg]) ->
76    succeeds_if_type(Arg, #t_map{});
77will_succeed(erlang, 'not', [Arg]) ->
78    succeeds_if_type(Arg, beam_types:make_boolean());
79will_succeed(erlang, setelement, [#t_integer{elements={Min,Max}},
80                                  #t_tuple{exact=Exact,size=Size}, _]) ->
81    case Min >= 1 andalso Max =< Size of
82        true -> yes;
83        false when Exact -> no;
84        false -> maybe
85    end;
86will_succeed(erlang, size, [Arg]) ->
87    ArgType = beam_types:join(#t_tuple{}, #t_bitstring{}),
88    succeeds_if_type(Arg, ArgType);
89will_succeed(erlang, tuple_size, [Arg]) ->
90    succeeds_if_type(Arg, #t_tuple{});
91will_succeed(erlang, tl, [Arg]) ->
92    succeeds_if_type(Arg, #t_cons{});
93will_succeed(Mod, Func, Args) ->
94    Arity = length(Args),
95    case erl_bifs:is_safe(Mod, Func, Arity) of
96        true ->
97            yes;
98        false ->
99            case erl_bifs:is_exit_bif(Mod, Func, Arity) of
100                true ->
101                    no;
102                false ->
103                    %% While we can't infer success for functions outside the
104                    %% 'erlang' module (see above comment), it's safe to infer
105                    %% failure when we know they return none or if the
106                    %% arguments must have certain types.
107                    case types(Mod, Func, Args) of
108                        {none, _, _} -> no;
109                        {_, ArgTypes, _} -> fails_on_conflict(Args, ArgTypes)
110                    end
111            end
112    end.
113
114fails_on_conflict([ArgType | Args], [Required | Types]) ->
115    case beam_types:meet(ArgType, Required) of
116        none -> no;
117        _ -> fails_on_conflict(Args, Types)
118    end;
119fails_on_conflict([], []) ->
120    maybe.
121
122succeeds_if_type(ArgType, Required) ->
123    case beam_types:meet(ArgType, Required) of
124        ArgType -> yes;
125        none -> no;
126        _ -> maybe
127    end.
128
129%%
130%% Returns the inferred return and argument types for known functions, and
131%% whether it's safe to subtract argument types on failure.
132%%
133%% Note that the return type will be 'none' if we can statically determine that
134%% the function will fail at runtime.
135%%
136
137-spec types(Mod, Func, ArgTypes) -> {RetType, ArgTypes, CanSubtract} when
138      Mod :: atom(),
139      Func :: atom(),
140      ArgTypes :: [normal_type()],
141      RetType :: type(),
142      CanSubtract :: boolean().
143
144%% Functions that only fail due to bad argument *types*, meaning it's safe to
145%% subtract argument types on failure.
146%%
147%% Note that these are all from the erlang module; suitable functions in other
148%% modules could fail due to the module not being loaded.
149types(erlang, 'map_size', [_]) ->
150    sub_safe(#t_integer{}, [#t_map{}]);
151types(erlang, 'tuple_size', [_]) ->
152    sub_safe(#t_integer{}, [#t_tuple{}]);
153types(erlang, 'bit_size', [_]) ->
154    sub_safe(#t_integer{}, [#t_bitstring{}]);
155types(erlang, 'byte_size', [_]) ->
156    sub_safe(#t_integer{}, [#t_bitstring{}]);
157types(erlang, hd, [Src]) ->
158    RetType = erlang_hd_type(Src),
159    sub_safe(RetType, [#t_cons{}]);
160types(erlang, tl, [Src]) ->
161    RetType = erlang_tl_type(Src),
162    sub_safe(RetType, [#t_cons{}]);
163types(erlang, 'not', [_]) ->
164    Bool = beam_types:make_boolean(),
165    sub_safe(Bool, [Bool]);
166types(erlang, 'length', [_]) ->
167    sub_safe(#t_integer{}, [proper_list()]);
168
169%% Boolean ops
170types(erlang, 'and', [_,_]) ->
171    Bool = beam_types:make_boolean(),
172    sub_unsafe(Bool, [Bool, Bool]);
173types(erlang, 'or', [_,_]) ->
174    Bool = beam_types:make_boolean(),
175    sub_unsafe(Bool, [Bool, Bool]);
176types(erlang, 'xor', [_,_]) ->
177    Bool = beam_types:make_boolean(),
178    sub_unsafe(Bool, [Bool, Bool]);
179
180%% Bitwise ops
181types(erlang, 'band', [_,_]=Args) ->
182    sub_unsafe(erlang_band_type(Args), [#t_integer{}, #t_integer{}]);
183types(erlang, 'bor', [_,_]) ->
184    sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]);
185types(erlang, 'bxor', [_,_]) ->
186    sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]);
187types(erlang, 'bsl', [_,_]) ->
188    sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]);
189types(erlang, 'bsr', [_,_]) ->
190    sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]);
191types(erlang, 'bnot', [_]) ->
192    sub_unsafe(#t_integer{}, [#t_integer{}]);
193
194%% Fixed-type arithmetic
195types(erlang, 'float', [_]) ->
196    sub_unsafe(#t_float{}, [number]);
197types(erlang, 'round', [_]) ->
198    sub_unsafe(#t_integer{}, [number]);
199types(erlang, 'floor', [_]) ->
200    sub_unsafe(#t_integer{}, [number]);
201types(erlang, 'ceil', [_]) ->
202    sub_unsafe(#t_integer{}, [number]);
203types(erlang, 'trunc', [_]) ->
204    sub_unsafe(#t_integer{}, [number]);
205types(erlang, '/', [_,_]) ->
206    sub_unsafe(#t_float{}, [number, number]);
207types(erlang, 'div', [_,_]) ->
208    sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]);
209types(erlang, 'rem', [_,_]) ->
210    sub_unsafe(#t_integer{}, [#t_integer{}, #t_integer{}]);
211
212%% Mixed-type arithmetic; '+'/2 and friends are handled in the catch-all
213%% clause for the 'erlang' module.
214types(erlang, 'abs', [_]=Args) ->
215    mixed_arith_types(Args);
216
217%% List operations
218types(erlang, '++', [LHS, RHS]) ->
219    %% `[] ++ RHS` yields RHS, even if RHS is not a list.
220    ListType = copy_list(LHS, same_length, proper),
221    RetType = beam_types:join(ListType, RHS),
222    sub_unsafe(RetType, [proper_list(), any]);
223types(erlang, '--', [LHS, _]) ->
224    RetType = copy_list(LHS, new_length, proper),
225    sub_unsafe(RetType, [proper_list(), proper_list()]);
226
227types(erlang, 'iolist_to_binary', [_]) ->
228    %% Arg is an iodata(), despite its name.
229    ArgType = beam_types:join(#t_list{}, #t_bitstring{size_unit=8}),
230    sub_unsafe(#t_bitstring{size_unit=8}, [ArgType]);
231types(erlang, 'list_to_binary', [_]) ->
232    %% Arg is an iolist(), despite its name.
233    sub_unsafe(#t_bitstring{size_unit=8}, [#t_list{}]);
234types(erlang, 'list_to_bitstring', [_]) ->
235    %% As list_to_binary but with bitstrings rather than binaries.
236    sub_unsafe(#t_bitstring{}, [proper_list()]);
237
238%% Misc ops.
239types(erlang, 'binary_part', [_, _]) ->
240    PosLen = make_two_tuple(#t_integer{}, #t_integer{}),
241    Binary = #t_bitstring{size_unit=8},
242    sub_unsafe(Binary, [Binary, PosLen]);
243types(erlang, 'binary_part', [_, _, _]) ->
244    Binary = #t_bitstring{size_unit=8},
245    sub_unsafe(Binary, [Binary, #t_integer{}, #t_integer{}]);
246types(erlang, 'is_map_key', [Key, Map]) ->
247    RetType = case erlang_map_get_type(Key, Map) of
248                  none -> beam_types:make_atom(false);
249                  _ -> beam_types:make_boolean()
250              end,
251    sub_unsafe(RetType, [any, #t_map{}]);
252types(erlang, 'map_get', [Key, Map]) ->
253    RetType = erlang_map_get_type(Key, Map),
254    sub_unsafe(RetType, [any, #t_map{}]);
255types(erlang, 'node', [_]) ->
256    sub_unsafe(#t_atom{}, [any]);
257types(erlang, 'node', []) ->
258    sub_unsafe(#t_atom{}, []);
259types(erlang, 'size', [_]) ->
260    ArgType = beam_types:join(#t_tuple{}, #t_bitstring{}),
261    sub_unsafe(#t_integer{}, [ArgType]);
262
263%% Tuple element ops
264types(erlang, element, [PosType, TupleType]) ->
265    Index = case PosType of
266                #t_integer{elements={Same,Same}} when is_integer(Same) ->
267                    Same;
268                _ ->
269                    0
270            end,
271
272    RetType = case TupleType of
273                  #t_tuple{size=Sz,elements=Es} when Index =< Sz,
274                                                     Index >= 1 ->
275                      beam_types:get_tuple_element(Index, Es);
276                  _ ->
277                      any
278              end,
279
280    sub_unsafe(RetType, [#t_integer{}, #t_tuple{size=Index}]);
281types(erlang, setelement, [PosType, TupleType, ArgType]) ->
282    RetType = case {PosType,TupleType} of
283                  {#t_integer{elements={Index,Index}},
284                   #t_tuple{elements=Es0,size=Size}=T} when Index >= 1 ->
285                      %% This is an exact index, update the type of said
286                      %% element or return 'none' if it's known to be out of
287                      %% bounds.
288                      Es = beam_types:set_tuple_element(Index, ArgType, Es0),
289                      case T#t_tuple.exact of
290                          false ->
291                              T#t_tuple{size=max(Index, Size),elements=Es};
292                          true when Index =< Size ->
293                              T#t_tuple{elements=Es};
294                          true ->
295                              none
296                      end;
297                  {#t_integer{elements={Min,Max}},
298                   #t_tuple{elements=Es0,size=Size}=T} when Min >= 1 ->
299                      %% We know this will land between Min and Max, so kill
300                      %% the types for those indexes.
301                      Es = discard_tuple_element_info(Min, Max, Es0),
302                      case T#t_tuple.exact of
303                          false ->
304                              T#t_tuple{elements=Es,size=max(Min, Size)};
305                          true when Min =< Size ->
306                              T#t_tuple{elements=Es,size=Size};
307                          true ->
308                              none
309                      end;
310                  {_,#t_tuple{}=T} ->
311                      %% Position unknown, so we have to discard all element
312                      %% information.
313                      T#t_tuple{elements=#{}};
314                  {#t_integer{elements={Min,_Max}},_} ->
315                      #t_tuple{size=Min};
316                  {_,_} ->
317                      #t_tuple{}
318              end,
319    sub_unsafe(RetType, [#t_integer{}, #t_tuple{}, any]);
320
321types(erlang, make_fun, [_,_,Arity0]) ->
322    Type = case Arity0 of
323               #t_integer{elements={Arity,Arity}} when Arity >= 0 ->
324                   #t_fun{arity=Arity};
325               _ ->
326                   #t_fun{}
327           end,
328    sub_unsafe(Type, [#t_atom{}, #t_atom{}, #t_integer{}]);
329
330types(erlang, Name, Args) ->
331    Arity = length(Args),
332
333    case erl_bifs:is_exit_bif(erlang, Name, Arity) of
334        true ->
335            {none, Args, false};
336        false ->
337            case erl_internal:arith_op(Name, Arity) of
338                true ->
339                    mixed_arith_types(Args);
340                false ->
341                    IsTest =
342                        erl_internal:new_type_test(Name, Arity) orelse
343                        erl_internal:comp_op(Name, Arity),
344
345                    RetType = case IsTest of
346                                  true -> beam_types:make_boolean();
347                                  false -> any
348                              end,
349
350                    sub_unsafe(RetType, duplicate(Arity, any))
351            end
352    end;
353
354%%
355%% Math BIFs
356%%
357
358types(math, cos, [_]) ->
359    sub_unsafe(#t_float{}, [number]);
360types(math, cosh, [_]) ->
361    sub_unsafe(#t_float{}, [number]);
362types(math, sin, [_]) ->
363    sub_unsafe(#t_float{}, [number]);
364types(math, sinh, [_]) ->
365    sub_unsafe(#t_float{}, [number]);
366types(math, tan, [_]) ->
367    sub_unsafe(#t_float{}, [number]);
368types(math, tanh, [_]) ->
369    sub_unsafe(#t_float{}, [number]);
370types(math, acos, [_]) ->
371    sub_unsafe(#t_float{}, [number]);
372types(math, acosh, [_]) ->
373    sub_unsafe(#t_float{}, [number]);
374types(math, asin, [_]) ->
375    sub_unsafe(#t_float{}, [number]);
376types(math, asinh, [_]) ->
377    sub_unsafe(#t_float{}, [number]);
378types(math, atan, [_]) ->
379    sub_unsafe(#t_float{}, [number]);
380types(math, atanh, [_]) ->
381    sub_unsafe(#t_float{}, [number]);
382types(math, erf, [_]) ->
383    sub_unsafe(#t_float{}, [number]);
384types(math, erfc, [_]) ->
385    sub_unsafe(#t_float{}, [number]);
386types(math, exp, [_]) ->
387    sub_unsafe(#t_float{}, [number]);
388types(math, log, [_]) ->
389    sub_unsafe(#t_float{}, [number]);
390types(math, log2, [_]) ->
391    sub_unsafe(#t_float{}, [number]);
392types(math, log10, [_]) ->
393    sub_unsafe(#t_float{}, [number]);
394types(math, sqrt, [_]) ->
395    sub_unsafe(#t_float{}, [number]);
396types(math, atan2, [_,_]) ->
397    sub_unsafe(#t_float{}, [number, number]);
398types(math, pow, [_,_]) ->
399    sub_unsafe(#t_float{}, [number, number]);
400types(math, ceil, [_]) ->
401    sub_unsafe(#t_float{}, [number]);
402types(math, floor, [_]) ->
403    sub_unsafe(#t_float{}, [number]);
404types(math, fmod, [_,_]) ->
405    sub_unsafe(#t_float{}, [number, number]);
406types(math, pi, []) ->
407    sub_unsafe(#t_float{}, []);
408
409%%
410%% List functions
411%%
412%% These tend to have tricky edge cases around nil and proper lists, be very
413%% careful and try not to narrow the types needlessly. Keep in mind that they
414%% need to be safe regardless of how the function is implemented, so it's best
415%% not to say that a list is proper unless every element must be visited to
416%% succeed.
417%%
418
419%% Operator aliases.
420types(lists, append, [_,_]=Args) ->
421    types(erlang, '++', Args);
422types(lists, append, [_]) ->
423    %% This is implemented through folding the list over erlang:'++'/2, so it
424    %% can hypothetically return anything, but we can infer that its argument
425    %% is a proper list on success.
426    sub_unsafe(any, [proper_list()]);
427types(lists, subtract, [_,_]=Args) ->
428    types(erlang, '--', Args);
429
430%% Functions returning booleans.
431types(lists, all, [_,_]) ->
432    %% This can succeed on improper lists if the fun returns 'false' for an
433    %% element before reaching the end.
434    sub_unsafe(beam_types:make_boolean(), [#t_fun{arity=1}, #t_list{}]);
435types(lists, any, [_,_]) ->
436    %% Doesn't imply that the argument is a proper list; see lists:all/2
437    sub_unsafe(beam_types:make_boolean(), [#t_fun{arity=1}, #t_list{}]);
438types(lists, keymember, [_,_,_]) ->
439    %% Doesn't imply that the argument is a proper list; see lists:all/2
440    sub_unsafe(beam_types:make_boolean(), [any, #t_integer{}, #t_list{}]);
441types(lists, member, [_,_]) ->
442    %% Doesn't imply that the argument is a proper list; see lists:all/2
443    sub_unsafe(beam_types:make_boolean(), [any, #t_list{}]);
444types(lists, prefix, [_,_]) ->
445    %% This function doesn't need to reach the end of either list to return
446    %% false, so we can succeed even when both are improper lists.
447    sub_unsafe(beam_types:make_boolean(), [#t_list{}, #t_list{}]);
448types(lists, suffix, [_,_]) ->
449    %% A different implementation could return true when the first list is nil,
450    %% so we can't tell if either is proper.
451    sub_unsafe(beam_types:make_boolean(), [#t_list{}, #t_list{}]);
452
453%% Simple folds
454types(lists, foldl, [Fun, Init, List]) ->
455    RetType = lists_fold_type(Fun, Init, List),
456    sub_unsafe(RetType, [#t_fun{arity=2}, any, proper_list()]);
457types(lists, foldr, [Fun, Init, List]) ->
458    RetType = lists_fold_type(Fun, Init, List),
459    sub_unsafe(RetType, [#t_fun{arity=2}, any, proper_list()]);
460
461%% Functions returning plain lists.
462types(lists, droplast, [List]) ->
463    RetType = copy_list(List, new_length, proper),
464    sub_unsafe(RetType, [proper_list()]);
465types(lists, dropwhile, [_Fun, List]) ->
466    %% If the element is found before the end of the list, we could return an
467    %% improper list.
468    RetType = copy_list(List, new_length, maybe_improper),
469    sub_unsafe(RetType, [#t_fun{arity=1}, #t_list{}]);
470types(lists, duplicate, [_Count, Element]) ->
471    sub_unsafe(proper_list(Element), [#t_integer{}, any]);
472types(lists, filter, [_Fun, List]) ->
473    RetType = copy_list(List, new_length, proper),
474    sub_unsafe(RetType, [#t_fun{arity=1}, proper_list()]);
475types(lists, flatten, [_]) ->
476    sub_unsafe(proper_list(), [proper_list()]);
477types(lists, map, [Fun, List]) ->
478    RetType = lists_map_type(Fun, List),
479    sub_unsafe(RetType, [#t_fun{arity=1}, proper_list()]);
480types(lists, reverse, [List]) ->
481    RetType = copy_list(List, same_length, proper),
482    sub_unsafe(RetType, [proper_list()]);
483types(lists, sort, [List]) ->
484    RetType = copy_list(List, same_length, proper),
485    sub_unsafe(RetType, [proper_list()]);
486types(lists, takewhile, [_Fun, List]) ->
487    %% Doesn't imply that the argument is a proper list; see lists:all/2
488    RetType = copy_list(List, new_length, proper),
489    sub_unsafe(RetType, [#t_fun{arity=1}, #t_list{}]);
490types(lists, usort, [List]) ->
491    %% The result is not quite the same length, but a non-empty list will stay
492    %% non-empty.
493    RetType = copy_list(List, same_length, proper),
494    sub_unsafe(RetType, [proper_list()]);
495types(lists, zip, [_,_]=Lists) ->
496    {RetType, ArgType} = lists_zip_types(Lists),
497    sub_unsafe(RetType, [ArgType, ArgType]);
498types(lists, zipwith, [Fun | [_,_]=Lists]) ->
499    {RetType, ArgType} = lists_zipwith_types(Fun, Lists),
500    sub_unsafe(RetType, [#t_fun{arity=2}, ArgType, ArgType]);
501
502%% Functions with complex return values.
503types(lists, keyfind, [KeyType,PosType,_]) ->
504    %% Doesn't imply that the argument is a proper list; see lists:all/2
505    TupleType = case PosType of
506                    #t_integer{elements={Index,Index}} when is_integer(Index),
507                                                            Index >= 1 ->
508                        Es = beam_types:set_tuple_element(Index, KeyType, #{}),
509                        #t_tuple{size=Index,elements=Es};
510                    _ ->
511                        #t_tuple{}
512                end,
513    RetType = beam_types:join(TupleType, beam_types:make_atom(false)),
514    sub_unsafe(RetType, [any, #t_integer{}, #t_list{}]);
515types(lists, MapFold, [Fun, Init, List])
516  when MapFold =:= mapfoldl; MapFold =:= mapfoldr ->
517    RetType = lists_mapfold_type(Fun, Init, List),
518    sub_unsafe(RetType, [#t_fun{arity=2}, any, proper_list()]);
519types(lists, partition, [_Fun, List]) ->
520    ListType = copy_list(List, new_length, proper),
521    RetType = make_two_tuple(ListType, ListType),
522    sub_unsafe(RetType, [#t_fun{arity=1}, proper_list()]);
523types(lists, search, [_,_]) ->
524    %% Doesn't imply that the argument is a proper list; see lists:all/2
525    TupleType = make_two_tuple(beam_types:make_atom(value), any),
526    RetType = beam_types:join(TupleType, beam_types:make_atom(false)),
527    sub_unsafe(RetType, [#t_fun{arity=1}, #t_list{}]);
528types(lists, splitwith, [_Fun, List]) ->
529    %% Only the elements in the left list are guaranteed to be visited, so both
530    %% the argument and the right list may be improper.
531    Left = copy_list(List, new_length, proper),
532    Right = copy_list(List, new_length, maybe_improper),
533    sub_unsafe(make_two_tuple(Left, Right), [#t_fun{arity=1}, #t_list{}]);
534types(lists, unzip, [List]) ->
535    RetType = lists_unzip_type(2, List),
536    sub_unsafe(RetType, [proper_list()]);
537
538%%
539%% Map functions
540%%
541
542types(maps, filter, [_Fun, Map]) ->
543    %% Conservatively assume that key/value types are unchanged.
544    RetType = case Map of
545                  #t_map{}=T -> T;
546                  _ -> #t_map{}
547              end,
548    sub_unsafe(RetType, [#t_fun{arity=2}, #t_map{}]);
549types(maps, find, [Key, Map]) ->
550    TupleType = case erlang_map_get_type(Key, Map) of
551                    none ->
552                        none;
553                    ValueType ->
554                        make_two_tuple(beam_types:make_atom(ok), ValueType)
555                end,
556    %% error | {ok, Value}
557    RetType = beam_types:join(beam_types:make_atom(error), TupleType),
558    sub_unsafe(RetType, [any, #t_map{}]);
559types(maps, fold, [Fun, Init, _Map]) ->
560    RetType = case Fun of
561                  #t_fun{type=Type} ->
562                      %% The map is potentially empty, so we have to assume it
563                      %% can return the initial value.
564                      beam_types:join(Type, Init);
565                  _ ->
566                      any
567              end,
568    sub_unsafe(RetType, [#t_fun{arity=3}, any, #t_map{}]);
569types(maps, from_list, [Pairs]) ->
570    PairType = erlang_hd_type(Pairs),
571    RetType = case beam_types:normalize(PairType) of
572                  #t_tuple{elements=Es} ->
573                      SKey = beam_types:get_tuple_element(1, Es),
574                      SValue = beam_types:get_tuple_element(2, Es),
575                      #t_map{super_key=SKey,super_value=SValue};
576                  _ ->
577                      #t_map{}
578              end,
579    sub_unsafe(RetType, [proper_list()]);
580types(maps, get, [_Key, _Map]=Args) ->
581    types(erlang, map_get, Args);
582types(maps, get, [Key, Map, Default]) ->
583    RetType = case erlang_map_get_type(Key, Map) of
584                  none -> Default;
585                  ValueType -> beam_types:join(ValueType, Default)
586              end,
587    sub_unsafe(RetType, [any, #t_map{}, any]);
588types(maps, is_key, [_Key, _Map]=Args) ->
589    types(erlang, is_map_key, Args);
590types(maps, keys, [Map]) ->
591    RetType = case Map of
592                  #t_map{super_key=none} -> nil;
593                  #t_map{super_key=SKey} -> proper_list(SKey);
594                  _ -> proper_list()
595              end,
596    sub_unsafe(RetType, [#t_map{}]);
597types(maps, map, [Fun, Map]) ->
598    RetType = case {Fun, Map} of
599                  {#t_fun{type=FunRet}, #t_map{super_value=SValue0}} ->
600                      SValue = beam_types:join(FunRet, SValue0),
601                      Map#t_map{super_value=SValue};
602                  _ ->
603                      #t_map{}
604              end,
605    sub_unsafe(RetType, [#t_fun{arity=2}, #t_map{}]);
606types(maps, merge, [A, B]) ->
607    RetType = case {A, B} of
608                  {#t_map{super_key=SKeyA,super_value=SValueA},
609                   #t_map{super_key=SKeyB,super_value=SValueB}} ->
610                      SKey = beam_types:join(SKeyA, SKeyB),
611                      SValue = beam_types:join(SValueA, SValueB),
612                      #t_map{super_key=SKey,super_value=SValue};
613                  _ ->
614                      #t_map{}
615              end,
616    sub_unsafe(RetType, [#t_map{}, #t_map{}]);
617types(maps, new, []) ->
618    RetType = #t_map{super_key=none,super_value=none},
619    sub_unsafe(RetType, []);
620types(maps, put, [Key, Value, Map]) ->
621    RetType = case Map of
622                  #t_map{super_key=SKey0,super_value=SValue0} ->
623                      SKey = beam_types:join(Key, SKey0),
624                      SValue = beam_types:join(Value, SValue0),
625                      #t_map{super_key=SKey,super_value=SValue};
626                  _ ->
627                      #t_map{}
628              end,
629    sub_unsafe(RetType, [any, any, #t_map{}]);
630types(maps, remove, [Key, Map]) ->
631    RetType = maps_remove_type(Key, Map),
632    sub_unsafe(RetType, [any, #t_map{}]);
633types(maps, take, [Key, Map]) ->
634    TupleType = case erlang_map_get_type(Key, Map) of
635                    none ->
636                        none;
637                    ValueType ->
638                        MapType = beam_types:meet(Map, #t_map{}),
639                        make_two_tuple(ValueType, MapType)
640                end,
641    %% error | {Value, Map}
642    RetType = beam_types:join(beam_types:make_atom(error), TupleType),
643    sub_unsafe(RetType, [any, #t_map{}]);
644types(maps, to_list, [Map]) ->
645    RetType = case Map of
646                  #t_map{super_key=SKey,super_value=SValue} ->
647                      proper_list(make_two_tuple(SKey, SValue));
648                  _ ->
649                      proper_list()
650              end,
651    sub_unsafe(RetType, [#t_map{}]);
652types(maps, update_with, [_Key, Fun, Map]) ->
653    RetType = case {Fun, Map} of
654                  {#t_fun{type=FunRet}, #t_map{super_value=SValue0}} ->
655                      SValue = beam_types:join(FunRet, SValue0),
656                      Map#t_map{super_value=SValue};
657                  _ ->
658                      #t_map{}
659              end,
660    sub_unsafe(RetType, [any, #t_fun{arity=1}, #t_map{}]);
661types(maps, values, [Map]) ->
662    RetType = case Map of
663                  #t_map{super_value=none} -> nil;
664                  #t_map{super_value=SValue} -> proper_list(SValue);
665                  _ -> proper_list()
666              end,
667    sub_unsafe(RetType, [#t_map{}]);
668types(maps, with, [Keys, Map]) ->
669    RetType = case Map of
670                  #t_map{super_key=SKey0} ->
671                      %% Since we know that the Map will only contain the pairs
672                      %% pointed out by Keys, we can restrict the types to
673                      %% those in the list.
674                      SKey = beam_types:meet(erlang_hd_type(Keys), SKey0),
675                      Map#t_map{super_key=SKey};
676                  _ ->
677                      #t_map{}
678              end,
679    sub_unsafe(RetType, [proper_list(), #t_map{}]);
680types(maps, without, [Keys, Map]) ->
681    RetType = maps_remove_type(erlang_hd_type(Keys), Map),
682    sub_unsafe(RetType, [proper_list(), #t_map{}]);
683
684%% Catch-all clause for unknown functions.
685
686types(_, _, Args) ->
687    sub_unsafe(any, [any || _ <- Args]).
688
689%%
690%% Function-specific helpers.
691%%
692
693mixed_arith_types([FirstType | _]=Args0) ->
694    RetType = foldl(fun(#t_integer{}, #t_integer{}) -> #t_integer{};
695                       (#t_integer{}, number) -> number;
696                       (#t_integer{}, #t_float{}) -> #t_float{};
697                       (#t_float{}, #t_integer{}) -> #t_float{};
698                       (#t_float{}, number) -> #t_float{};
699                       (#t_float{}, #t_float{}) -> #t_float{};
700                       (number, #t_integer{}) -> number;
701                       (number, #t_float{}) -> #t_float{};
702                       (number, number) -> number;
703                       (any, _) -> number;
704                       (_, _) -> none
705                    end, FirstType, Args0),
706    sub_unsafe(RetType, [number || _ <- Args0]).
707
708erlang_hd_type(Src) ->
709    case beam_types:meet(Src, #t_cons{}) of
710        #t_cons{type=Type} -> Type;
711        _ -> any
712    end.
713
714erlang_tl_type(Src) ->
715    case beam_types:meet(Src, #t_cons{}) of
716        #t_cons{terminator=Term}=Cons -> beam_types:join(Cons, Term);
717        _ -> any
718    end.
719
720erlang_band_type([#t_integer{elements={Int,Int}}, RHS]) when is_integer(Int) ->
721    erlang_band_type_1(RHS, Int);
722erlang_band_type([LHS, #t_integer{elements={Int,Int}}]) when is_integer(Int) ->
723    erlang_band_type_1(LHS, Int);
724erlang_band_type(_) ->
725    #t_integer{}.
726
727erlang_band_type_1(LHS, Int) ->
728    case LHS of
729        #t_integer{elements={Min0,Max0}} when Max0 - Min0 < 1 bsl 256 ->
730            {Intersection, Union} = range_masks(Min0, Max0),
731
732            Min = Intersection band Int,
733            Max = min(Max0, Union band Int),
734
735            #t_integer{elements={Min,Max}};
736        #t_integer{} when Int >= 0 ->
737            %% The range is either unknown or too wide, conservatively assume
738            %% that the new range is 0 .. Int.
739            %%
740            %% NOTE: We must not produce a singleton type unless we are sure
741            %% that the operation can't fail. Therefore, we only do this
742            %% inference if LHS is known to be an integer.
743            beam_types:meet(LHS, #t_integer{elements={0,Int}});
744        _ ->
745            %% We can't infer boundaries when LHS is not an integer or
746            %% the range is unknown and the other operand is a
747            %% negative number, as the latter sign-extends to infinity
748            %% and we can't express an inverted range at the moment
749            %% (cf. X band -8; either less than -7 or greater than 7).
750            beam_types:meet(LHS, #t_integer{})
751    end.
752
753erlang_map_get_type(Key, Map) ->
754    case Map of
755        #t_map{super_key=SKey,super_value=SValue} ->
756            case beam_types:meet(SKey, Key) of
757                none -> none;
758                _ -> SValue
759            end;
760        _ ->
761            any
762    end.
763
764lists_fold_type(_Fun, Init, nil) ->
765    Init;
766lists_fold_type(#t_fun{type=Type}, _Init, #t_cons{}) ->
767    %% The list is non-empty so it's safe to ignore Init.
768    Type;
769lists_fold_type(#t_fun{type=Type}, Init, #t_list{}) ->
770    %% The list is possibly empty so we have to assume it can return the
771    %% initial value, whose type can differ significantly from the fun's
772    %% return value.
773    beam_types:join(Type, Init);
774lists_fold_type(_Fun, _Init, _List) ->
775    any.
776
777lists_map_type(#t_fun{type=Type}, Types) ->
778    lists_map_type_1(Types, Type);
779lists_map_type(_Fun, Types) ->
780    lists_map_type_1(Types, any).
781
782lists_map_type_1(nil, _ElementType) ->
783    nil;
784lists_map_type_1(#t_cons{}, none) ->
785    %% The list is non-empty and the fun never returns.
786    none;
787lists_map_type_1(#t_cons{}, ElementType) ->
788    proper_cons(ElementType);
789lists_map_type_1(_, none) ->
790    %% The fun never returns, so the only way we could return normally is
791    %% if the list is empty.
792    nil;
793lists_map_type_1(_, ElementType) ->
794    proper_list(ElementType).
795
796lists_mapfold_type(#t_fun{type=#t_tuple{size=2,elements=Es}}, Init, List) ->
797    ElementType = beam_types:get_tuple_element(1, Es),
798    AccType = beam_types:get_tuple_element(2, Es),
799    lists_mapfold_type_1(List, ElementType, Init, AccType);
800lists_mapfold_type(#t_fun{type=none}, _Init, #t_cons{}) ->
801    %% The list is non-empty and the fun never returns.
802    none;
803lists_mapfold_type(#t_fun{type=none}, Init, _List) ->
804    %% The fun never returns, so the only way we could return normally is
805    %% if the list is empty, in which case we'll return [] and the initial
806    %% value.
807    make_two_tuple(nil, Init);
808lists_mapfold_type(_Fun, Init, List) ->
809    lists_mapfold_type_1(List, any, Init, any).
810
811lists_mapfold_type_1(nil, _ElementType, Init, _AccType) ->
812    make_two_tuple(nil, Init);
813lists_mapfold_type_1(#t_cons{}, ElementType, _Init, AccType) ->
814    %% The list has at least one element, so it's safe to ignore Init.
815    make_two_tuple(proper_cons(ElementType), AccType);
816lists_mapfold_type_1(_, ElementType, Init, AccType0) ->
817    %% We can only rely on AccType when we know the list is non-empty, so we
818    %% have to join it with the initial value in case the list is empty.
819    AccType = beam_types:join(AccType0, Init),
820    make_two_tuple(proper_list(ElementType), AccType).
821
822lists_unzip_type(Size, List) ->
823    Es = lut_make_elements(lut_list_types(Size, List), 1, #{}),
824    #t_tuple{size=Size,exact=true,elements=Es}.
825
826lut_make_elements([Type | Types], Index, Es0) ->
827    Es = beam_types:set_tuple_element(Index, Type, Es0),
828    lut_make_elements(Types, Index + 1, Es);
829lut_make_elements([], _Index, Es) ->
830    Es.
831
832lut_list_types(Size, #t_cons{type=#t_tuple{size=Size,elements=Es}}) ->
833    Types = lut_element_types(1, Size, Es),
834    [proper_cons(T) || T <- Types];
835lut_list_types(Size, #t_list{type=#t_tuple{size=Size,elements=Es}}) ->
836    Types = lut_element_types(1, Size, Es),
837    [proper_list(T) || T <- Types];
838lut_list_types(Size, nil) ->
839    lists:duplicate(Size, nil);
840lut_list_types(Size, _) ->
841    lists:duplicate(Size, proper_list()).
842
843lut_element_types(Index, Max, #{}) when Index > Max ->
844    [];
845lut_element_types(Index, Max, Es) ->
846    ElementType = beam_types:get_tuple_element(Index, Es),
847    [ElementType | lut_element_types(Index + 1, Max, Es)].
848
849%% lists:zip/2 and friends only succeed when all arguments have the same
850%% length, so if one of them is #t_cons{}, we can infer that all of them are
851%% #t_cons{} on success.
852
853lists_zip_types(Types) ->
854    lists_zip_types_1(Types, false, #{}, 1).
855
856lists_zip_types_1([nil | _], _AnyCons, _Es, _N) ->
857    %% Early exit; we know the result is [] on success.
858    {nil, nil};
859lists_zip_types_1([#t_cons{type=Type,terminator=nil} | Lists],
860                  _AnyCons, Es0, N) ->
861    Es = beam_types:set_tuple_element(N, Type, Es0),
862    lists_zip_types_1(Lists, true, Es, N + 1);
863lists_zip_types_1([#t_list{type=Type,terminator=nil} | Lists],
864                  AnyCons, Es0, N) ->
865    Es = beam_types:set_tuple_element(N, Type, Es0),
866    lists_zip_types_1(Lists, AnyCons, Es, N + 1);
867lists_zip_types_1([_ | Lists], AnyCons, Es, N) ->
868    lists_zip_types_1(Lists, AnyCons, Es, N + 1);
869lists_zip_types_1([], true, Es, N) ->
870    %% At least one element was cons, so we know it's non-empty on success.
871    ElementType = #t_tuple{exact=true,size=(N - 1),elements=Es},
872    RetType = proper_cons(ElementType),
873    ArgType = proper_cons(),
874    {RetType, ArgType};
875lists_zip_types_1([], false, Es, N) ->
876    ElementType = #t_tuple{exact=true,size=(N - 1),elements=Es},
877    RetType = proper_list(ElementType),
878    ArgType = proper_list(),
879    {RetType, ArgType}.
880
881lists_zipwith_types(#t_fun{type=Type}, Types) ->
882    lists_zipwith_type_1(Types, Type);
883lists_zipwith_types(_Fun, Types) ->
884    lists_zipwith_type_1(Types, any).
885
886lists_zipwith_type_1([nil | _], _ElementType) ->
887    %% Early exit; we know the result is [] on success.
888    {nil, nil};
889lists_zipwith_type_1([#t_cons{} | _Lists], none) ->
890    %% Early exit; the list is non-empty and we know the fun never
891    %% returns.
892    {none, any};
893lists_zipwith_type_1([#t_cons{} | _Lists], ElementType) ->
894    %% Early exit; we know the result is cons on success.
895    RetType = proper_cons(ElementType),
896    ArgType = proper_cons(),
897    {RetType, ArgType};
898lists_zipwith_type_1([_ | Lists], ElementType) ->
899    lists_zipwith_type_1(Lists, ElementType);
900lists_zipwith_type_1([], none) ->
901    %% Since we know the fun won't return, the only way we could return
902    %% normally is if all lists are empty.
903    {nil, nil};
904lists_zipwith_type_1([], ElementType) ->
905    RetType = proper_list(ElementType),
906    ArgType = proper_list(),
907    {RetType, ArgType}.
908
909maps_remove_type(Key, #t_map{super_key=SKey0}=Map) ->
910    case beam_types:is_singleton_type(Key) of
911        true ->
912            SKey = beam_types:subtract(SKey0, Key),
913            Map#t_map{super_key=SKey};
914        false ->
915            Map
916    end;
917maps_remove_type(_Key, _Map) ->
918    #t_map{}.
919
920%%%
921%%% Generic helpers
922%%%
923
924sub_unsafe(RetType, ArgTypes) ->
925    {RetType, ArgTypes, false}.
926
927sub_safe(RetType, ArgTypes) ->
928    {RetType, ArgTypes, true}.
929
930discard_tuple_element_info(Min, Max, Es) ->
931    foldl(fun(El, Acc) when Min =< El, El =< Max ->
932                  maps:remove(El, Acc);
933             (_El, Acc) -> Acc
934          end, Es, maps:keys(Es)).
935
936%% Returns two bitmasks describing all possible values between From and To.
937%%
938%% The first contains the bits that are common to all values, and the second
939%% contains the bits that are set by any value in the range.
940range_masks(From, To) when From =< To ->
941    range_masks_1(From, To, 0, -1, 0).
942
943range_masks_1(From, To, BitPos, Intersection, Union) when From < To ->
944    range_masks_1(From + (1 bsl BitPos), To, BitPos + 1,
945                  Intersection band From, Union bor From);
946range_masks_1(_From, To, _BitPos, Intersection0, Union0) ->
947    Intersection = To band Intersection0,
948    Union = To bor Union0,
949    {Intersection, Union}.
950
951proper_cons() ->
952    #t_cons{terminator=nil}.
953
954proper_cons(ElementType) ->
955    #t_cons{type=ElementType,terminator=nil}.
956
957proper_list() ->
958    #t_list{terminator=nil}.
959
960proper_list(ElementType) ->
961    #t_list{type=ElementType,terminator=nil}.
962
963%% Constructs a new list type based on another, optionally keeping the same
964%% length and/or making it proper.
965-spec copy_list(List, Length, Proper) -> type() when
966      List :: type(),
967      Length :: same_length | new_length,
968      Proper :: proper | maybe_improper.
969copy_list(#t_cons{terminator=Term}=T, Length, maybe_improper) ->
970    copy_list_1(T, Length, Term);
971copy_list(#t_list{terminator=Term}=T, Length, maybe_improper) ->
972    copy_list_1(T, Length, Term);
973copy_list(T, Length, proper) ->
974    copy_list_1(T, Length, nil);
975copy_list(T, Length, _Proper) ->
976    copy_list_1(T, Length, any).
977
978copy_list_1(#t_cons{}=T, same_length, Terminator) ->
979    T#t_cons{terminator=Terminator};
980copy_list_1(#t_cons{type=Type}, new_length, Terminator) ->
981    #t_list{type=Type,terminator=Terminator};
982copy_list_1(#t_list{}=T, _Length, Terminator) ->
983    T#t_list{terminator=Terminator};
984copy_list_1(nil, _Length, _Terminator) ->
985    nil;
986copy_list_1(_, _Length, Terminator) ->
987    #t_list{terminator=Terminator}.
988
989make_two_tuple(Type1, Type2) ->
990    Es0 = beam_types:set_tuple_element(1, Type1, #{}),
991    Es = beam_types:set_tuple_element(2, Type2, Es0),
992    #t_tuple{size=2,exact=true,elements=Es}.
993