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%% Common term types for passes operating on beam SSA and assembly. Helper 22%% functions for wrangling these can be found in beam_types.erl 23%% 24%% The type lattice is as follows: 25%% 26%% any Any Erlang term (top element). 27%% 28%% - #t_atom{} Atom, or a set thereof. 29%% - #t_bs_matchable{} Binary-matchable types. 30%% - #t_bitstring{} Bitstring. 31%% - #t_bs_context{} Match context. 32%% - #t_fun{} Fun. 33%% - #t_map{} Map. 34%% - number Any number. 35%% -- #t_float{} Floating point number. 36%% -- #t_integer{} Integer. 37%% - #t_list{} Any list. 38%% -- #t_cons{} Cons (nonempty list). 39%% -- nil The empty list. 40%% - #t_tuple{} Tuple. 41%% 42%% none No type (bottom element). 43%% 44%% We also use #t_union{} to represent conflicting types produced by certain 45%% expressions, e.g. the "#t_atom{} or #t_tuple{}" of lists:keyfind/3, which is 46%% very useful for preserving type information when we would otherwise have 47%% reduced it to 'any'. Since few operations can make direct use of this extra 48%% type information, types should generally be normalized to one of the above 49%% before use. 50%% 51%% When adding a new type it's important that the lattice stays consistent [1]. 52%% In brief, the following properties must hold: 53%% 54%% * All types must be unambiguous; any given value must narrow down to a 55%% single type, and multiple supertypes are not allowed. 56%% 57%% * `meet` is used when we know more about a value (e.g. type tests), so it 58%% must not return a more general type than either of its arguments. In other 59%% words, we're only allowed to *add* knowledge in a `meet`. 60%% 61%% * `join` is used when we know less about a value (e.g. phi node), so it 62%% must not return a more specific type than either of its arguments. In 63%% other words we're only allowed to *remove* knowledge in a `join`. 64%% 65%% * Both `join` and `meet` must be commutative, associative, and idempotent. 66%% 67%% Maintaining the above may seem trivial but subtle errors can creep in when 68%% adding fields or restrictions to a type. ?TUPLE_ELEMENT_LIMIT is a great 69%% example of this. 70%% 71%% The property test suite ensures that the above holds, so don't forget to 72%% add your new types there. You should also consider increasing ?REPETITIONS 73%% during development to ensure it hits all nooks and crannies. 74%% 75%% [1] https://en.wikipedia.org/wiki/Lattice_(order)#General_lattice 76 77-define(ATOM_SET_SIZE, 5). 78 79-record(t_atom, {elements=any :: 'any' | ordsets:ordset(atom())}). 80-record(t_bitstring, {size_unit=1 :: pos_integer()}). 81-record(t_bs_context, {tail_unit=1 :: pos_integer(), 82 slots=0 :: non_neg_integer(), 83 valid=0 :: non_neg_integer()}). 84-record(t_bs_matchable, {tail_unit=1}). 85-record(t_float, {elements=any :: 'any' | {float(),float()}}). 86-record(t_fun, {arity=any :: arity() | 'any', 87 type=any :: type() }). 88-record(t_integer, {elements=any :: 'any' | {integer(),integer()}}). 89 90%% `super_key` and `super_value` are the join of all key and value types. 91%% 92%% Note that we don't track specific elements as we have no obvious way to 93%% limit them. See ?TUPLE_ELEMENT_LIMIT for details. 94-record(t_map, {super_key=any :: type(), 95 super_value=any :: type()}). 96 97%% `type` is the join of all list elements, and `terminator` is the tail of the 98%% last cons cell ('nil' for proper lists). 99%% 100%% Note that `type` may not be updated unless the entire list is known, and 101%% that the terminator being known is not a guarantee that the rest of the list 102%% is. 103-record(t_cons, {type=any :: type(), terminator=any :: type()}). 104-record(t_list, {type=any :: type(), terminator=any :: type()}). 105 106-record(t_tuple, {size=0 :: integer(), 107 exact=false :: boolean(), 108 elements=#{} :: tuple_elements()}). 109 110%% Known element types, where the key is a 1-based integer index. Unknown 111%% elements are assumed to be 'any', and indexes above ?TUPLE_ELEMENT_LIMIT are 112%% ignored for performance reasons. 113%% 114%% Cutting off all indexes above a certain limit may seem strange, but is 115%% required to ensure that a meet of two types always returns a type that's at 116%% least as specific as either type. Consider the following types: 117%% 118%% A = #t_tuple{elements=#{ ... elements 1 .. 6 ... }} 119%% B = #t_tuple{elements=#{ ... elements 7 .. 13 ... }} 120%% 121%% If we'd collapse types once a tuple has more than 12 elements, meet(A, B) 122%% would suddenly be less specific than either A or B. Ignoring all elements 123%% above a certain index avoids this problem, at the small price of losing type 124%% information in huge tuples. 125 126-define(TUPLE_ELEMENT_LIMIT, 12). 127-type tuple_elements() :: #{ Key :: pos_integer() => type() }. 128 129-type normal_type() :: any | none | 130 number | #t_float{} | #t_integer{} | 131 #t_atom{} | 132 #t_bitstring{} | #t_bs_context{} | #t_bs_matchable{} | 133 #t_fun{} | 134 #t_list{} | #t_cons{} | nil | 135 #t_map{} | 136 #t_tuple{}. 137 138-type record_key() :: {Arity :: integer(), Tag :: normal_type() }. 139-type record_set() :: ordsets:ordset({record_key(), #t_tuple{}}). 140-type tuple_set() :: #t_tuple{} | record_set(). 141 142-record(t_union, {atom=none :: none | #t_atom{}, 143 list=none :: none | #t_list{} | #t_cons{} | nil, 144 number=none :: none | number | #t_float{} | #t_integer{}, 145 tuple_set=none :: none | tuple_set(), 146 other=none :: normal_type()}). 147 148-type type() :: #t_union{} | normal_type(). 149 150-ifdef(BEAM_TYPES_INTERNAL). 151%% Internal constants used by beam_types.erl and its whitebox tests 152-define(TUPLE_SET_LIMIT, 12). 153-define(MAX_TYPE_DEPTH, 4). 154-endif. 155