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