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