diff options
Diffstat (limited to 'lib/hipe/cerl')
-rw-r--r-- | lib/hipe/cerl/Makefile | 4 | ||||
-rw-r--r-- | lib/hipe/cerl/cerl_messagean.erl | 1095 | ||||
-rw-r--r-- | lib/hipe/cerl/erl_bif_types.erl | 45 | ||||
-rw-r--r-- | lib/hipe/cerl/erl_types.erl | 333 |
4 files changed, 109 insertions, 1368 deletions
diff --git a/lib/hipe/cerl/Makefile b/lib/hipe/cerl/Makefile index 9f50d6bf91..f653dce36f 100644 --- a/lib/hipe/cerl/Makefile +++ b/lib/hipe/cerl/Makefile @@ -1,7 +1,7 @@ # # %CopyrightBegin% # -# Copyright Ericsson AB 2003-2016. All Rights Reserved. +# Copyright Ericsson AB 2003-2018. 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. @@ -44,7 +44,7 @@ RELSYSDIR = $(RELEASE_PATH)/lib/hipe-$(VSN) # Target Specs # ---------------------------------------------------- MODULES = cerl_cconv cerl_closurean cerl_hipeify cerl_lib \ - cerl_messagean cerl_pmatch cerl_prettypr cerl_to_icode \ + cerl_pmatch cerl_prettypr cerl_to_icode \ cerl_typean erl_bif_types erl_types HRL_FILES= cerl_hipe_primops.hrl diff --git a/lib/hipe/cerl/cerl_messagean.erl b/lib/hipe/cerl/cerl_messagean.erl deleted file mode 100644 index c79e045bd0..0000000000 --- a/lib/hipe/cerl/cerl_messagean.erl +++ /dev/null @@ -1,1095 +0,0 @@ -%% 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. -%% -%% @copyright 2002 Richard Carlsson -%% @author Richard Carlsson <[email protected]> -%% @doc Message analysis of Core Erlang programs. - -%% TODO: might need a "top" (`any') element for any-length value lists. - --module(cerl_messagean). - --export([annotate/1]). - --import(cerl, [alias_pat/1, alias_var/1, ann_c_var/2, ann_c_fun/3, - apply_args/1, apply_op/1, atom_val/1, bitstr_size/1, - bitstr_val/1, binary_segments/1, c_letrec/2, - ann_c_tuple/2, c_nil/0, call_args/1, call_module/1, - call_name/1, case_arg/1, case_clauses/1, catch_body/1, - clause_body/1, clause_guard/1, clause_pats/1, cons_hd/1, - cons_tl/1, fun_body/1, fun_vars/1, get_ann/1, int_val/1, - is_c_atom/1, is_c_int/1, let_arg/1, let_body/1, - let_vars/1, letrec_body/1, letrec_defs/1, module_defs/1, - module_defs/1, module_exports/1, pat_vars/1, - primop_args/1, primop_name/1, receive_action/1, - receive_clauses/1, receive_timeout/1, seq_arg/1, - seq_body/1, set_ann/2, try_arg/1, try_body/1, try_vars/1, - try_evars/1, try_handler/1, tuple_es/1, type/1, - values_es/1]). - --import(cerl_trees, [get_label/1]). - --define(DEF_LIMIT, 4). - -%% -export([test/1, test1/1, ttest/1]). - -%% ttest(F) -> -%% {T, _} = cerl_trees:label(user_default:read(F)), -%% {Time0, _} = erlang:statistics(runtime), -%% analyze(T), -%% {Time1, _} = erlang:statistics(runtime), -%% Time1 - Time0. - -%% test(F) -> -%% {T, _} = cerl_trees:label(user_default:read(F)), -%% {Time0, _} = erlang:statistics(runtime), -%% {Esc, _Vars} = analyze(T), -%% {Time1, _} = erlang:statistics(runtime), -%% io:fwrite("messages: ~p.\n", [Esc]), -%% Set = sets:from_list(Esc), -%% H = fun (Node, Ctxt, Cont) -> -%% Doc = case get_ann(Node) of -%% [{label, L} | _] -> -%% B = sets:is_element(L, Set), -%% bf(Node, Ctxt, Cont, B); -%% _ -> -%% bf(Node, Ctxt, Cont, false) -%% end, -%% case type(Node) of -%% cons -> color(Doc); -%% tuple -> color(Doc); -%% _ -> Doc -%% end -%% end, -%% {ok, FD} = file:open("out.html",[write]), -%% Txt = cerl_prettypr:format(T, [{hook, H},{user,false}]), -%% io:put_chars(FD, "<pre>\n"), -%% io:put_chars(FD, html(Txt)), -%% io:put_chars(FD, "</pre>\n"), -%% file:close(FD), -%% {ok, Time1 - Time0}. - -%% test1(F) -> -%% {T, _} = cerl_trees:label(user_default:read(F)), -%% {Time0, _} = erlang:statistics(runtime), -%% {T1, Esc, Vars} = annotate(T), -%% {Time1, _} = erlang:statistics(runtime), -%% io:fwrite("messages: ~p.\n", [Esc]), -%% %%% io:fwrite("vars: ~p.\n", [[X || X <- dict:to_list(Vars)]]), -%% T2 = hhl_transform:transform(T1, Vars), -%% Set = sets:from_list(Esc), -%% H = fun (Node, Ctxt, Cont) -> -%% case get_ann(Node) of -%% [{label, L} | _] -> -%% B = sets:is_element(L, Set), -%% bf(Node, Ctxt, Cont, B); -%% _ -> -%% bf(Node, Ctxt, Cont, false) -%% end -%% end, -%% {ok, FD} = file:open("out.html",[write]), -%% Txt = cerl_prettypr:format(T2, [{hook, H},{user,false}]), -%% io:put_chars(FD, "<pre>\n"), -%% io:put_chars(FD, html(Txt)), -%% io:put_chars(FD, "</pre>\n"), -%% file:close(FD), -%% {ok, Time1 - Time0}. - -%% html(Cs) -> -%% html(Cs, []). - -%% html([$#, $< | Cs], As) -> -%% html_1(Cs, [$< | As]); -%% html([$< | Cs], As) -> -%% html(Cs, ";tl&" ++ As); -%% html([$> | Cs], As) -> -%% html(Cs, ";tg&" ++ As); -%% html([$& | Cs], As) -> -%% html(Cs, ";pma&" ++ As); -%% html([C | Cs], As) -> -%% html(Cs, [C | As]); -%% html([], As) -> -%% lists:reverse(As). - -%% html_1([$> | Cs], As) -> -%% html(Cs, [$> | As]); -%% html_1([C | Cs], As) -> -%% html_1(Cs, [C | As]). - -%% bf(Node, Ctxt, Cont, B) -> -%% B0 = cerl_prettypr:get_ctxt_user(Ctxt), -%% if B /= B0 -> -%% Ctxt1 = cerl_prettypr:set_ctxt_user(Ctxt, B), -%% Doc = Cont(Node, Ctxt1), -%% case B of -%% true -> -%% Start = "<b>", -%% End = "</b>"; -%% false -> -%% Start = "</b>", -%% End = "<b>" -%% end, -%% markup(Doc, Start, End); -%% true -> -%% Cont(Node, Ctxt) -%% end. - -%% color(Doc) -> -%% % Doc. -%% markup(Doc, "<font color=blue>", "</font>"). - -%% markup(Doc, Start, End) -> -%% prettypr:beside( -%% prettypr:null_text([$# | Start]), -%% prettypr:beside(Doc, -%% prettypr:null_text([$# | End]))). - - -%% ===================================================================== -%% annotate(Tree) -> {Tree1, Escapes, Vars} -%% -%% Tree = cerl:cerl() -%% -%% Analyzes `Tree' (see `analyze') and appends a term 'escapes', to -%% the annotation list of each constructor expression node and of -%% `Tree', corresponding to the escape information derived by the -%% analysis. Any previous such annotations are removed from `Tree'. -%% `Tree1' is the modified tree; for details on `OutList', -%% `Outputs' , `Dependencies', `Escapes' and `Parents', see -%% `analyze'. -%% -%% Note: `Tree' must be annotated with labels in order to use this -%% function; see `analyze' for details. - --type label() :: integer() | 'external' | 'top'. --type ordset(X) :: [X]. % XXX: TAKE ME OUT - --spec annotate(cerl:cerl()) -> {cerl:cerl(), ordset(label()), dict:dict()}. - -annotate(Tree) -> - {Esc0, Vars} = analyze(Tree), - Esc = sets:from_list(Esc0), - F = fun (T) -> - case type(T) of - literal -> T; -%%% var -> -%%% L = get_label(T), -%%% T1 = ann_escape(T, L, Esc), -%%% X = dict:fetch(L, Vars), -%%% set_ann(T1, append_ann({s,X}, get_ann(T1))); - _ -> - L = get_label(T), - ann_escape(T, L, Esc) - end - end, - {cerl_trees:map(F, Tree), Esc0, Vars}. - -ann_escape(T, L, Esc) -> - case sets:is_element(L, Esc) of - true -> - set_ann(T, append_ann(escapes, get_ann(T))); - false -> - T - end. - -append_ann(Tag, [X | Xs]) -> - if tuple_size(X) >= 1, element(1, X) =:= Tag -> - append_ann(Tag, Xs); - true -> - [X | append_ann(Tag, Xs)] - end; -append_ann(Tag, []) -> - [Tag]. - - -%% ===================================================================== -%% analyze(Tree) -> Escapes -%% -%% Tree = cerl:cerl() -%% Escapes = ordset(Label) -%% Label = integer() | external | top -%% -%% Analyzes a module or an expression represented by `Tree'. -%% -%% `Escapes' is the set of labels of constructor expressions in -%% `Tree' such that the created values may be accessed from outside -%% `Tree'. -%% -%% Note: `Tree' must be annotated with labels (as done by the -%% function `cerl_trees:label/1') in order to use this function. -%% The label annotation `{label, L}' (where L should be an integer) -%% must be the first element of the annotation list of each node in -%% the tree. Instances of variables bound in `Tree' which denote -%% the same variable must have the same label; apart from this, -%% labels should be unique. Constant literals do not need to be -%% labeled. - --record(state, {vars, out, dep, work, funs, k}). - -%% Note: We assume that all remote calls and primops return a single -%% value. - -%% The analysis determines which objects (identified by the -%% corresponding "cons-point" labels in the code) are likely to be -%% passed in a message. (If so, we say that they "escape".) It is always -%% safe to assume either case, because the send operation will assure -%% that things are copied if necessary. This analysis tries to -%% anticipate that copying will be done. -%% -%% Rules: -%% 1) An object passed as message argument (or part of such an -%% argument) to a known send-operation, will probably be a message. -%% 2) A received value is always a message (safe). -%% 3) The external function can return any object (unsafe). -%% 4) A function called from the external function can receive any -%% object (unsafe) as argument. -%% 5) Unknown functions/operations can return any object (unsafe). - -%% We wrap the given syntax tree T in a fun-expression labeled `top', -%% which is initially in the set of escaped labels. `top' will be -%% visited at least once. -%% -%% We create a separate function labeled `external', defined as: -%% "'external'/1 = fun () -> Any", which will represent any and all -%% functions outside T, and which returns the 'unsafe' value. - -analyze(Tree) -> - analyze(Tree, ?DEF_LIMIT). - -analyze(Tree, Limit) -> - {_, _, Esc, Dep, _Par} = cerl_closurean:analyze(Tree), -%%% io:fwrite("dependencies: ~w.\n", [dict:to_list(Dep)]), - analyze(Tree, Limit, Dep, Esc). - -analyze(Tree, Limit, Dep0, Esc0) -> - %% Note that we use different name spaces for variable labels and - %% function/call site labels, so we can reuse some names here. We - %% assume that the labeling of Tree only uses integers, not atoms. - Any = ann_c_var([{label, any}], 'Any'), - External = ann_c_var([{label, external}], {external, 1}), - ExtFun = ann_c_fun([{label, external}], [], Any), -%%% io:fwrite("external fun:\n~s.\n", -%%% [cerl_prettypr:format(ExtFun, [noann, {paper, 80}])]), - Top = ann_c_var([{label, top}], {top, 0}), - TopFun = ann_c_fun([{label, top}], [], Tree), - - %% The "start fun" just makes the initialisation easier. It is not - %% itself in the call graph. - StartFun = ann_c_fun([{label, start}], [], - c_letrec([{External, ExtFun}, {Top, TopFun}], - c_nil())), -%%% io:fwrite("start fun:\n~s.\n", -%%% [cerl_prettypr:format(StartFun, [{paper, 80}])]), - - %% Initialise the Any and Escape variables. Gather a database of all - %% fun-expressions in Tree and initialise their outputs and parameter - %% variables. All escaping functions can receive any values as - %% inputs. Bind all module- and letrec-defined variables to their - %% corresponding labels. - Esc = sets:from_list(Esc0), - Unsafe = unsafe(), - Empty = empty(), - Funs0 = dict:new(), - Vars0 = dict:store(escape, empty(), - dict:store(any, Unsafe, dict:new())), - Out0 = dict:new(), - F = fun (T, S = {Fs, Vs, Os}) -> - case type(T) of - 'fun' -> - L = get_label(T), - As = fun_vars(T), - X = case sets:is_element(L, Esc) of - true -> Unsafe; - false -> Empty - end, - {dict:store(L, T, Fs), - bind_vars_single(As, X, Vs), - dict:store(L, none, Os)}; - letrec -> - {Fs, bind_defs(letrec_defs(T), Vs), Os}; - module -> - {Fs, bind_defs(module_defs(T), Vs), Os}; - _ -> - S - end - end, - {Funs, Vars, Out} = cerl_trees:fold(F, {Funs0, Vars0, Out0}, StartFun), - - %% Add the dependency for the loop in 'external': - Dep = add_dep(loop, external, Dep0), - - %% Enter the fixpoint iteration at the StartFun. - St = loop(StartFun, start, #state{vars = Vars, - out = Out, - dep = Dep, - work = init_work(), - funs = Funs, - k = Limit}), - Ms = labels(dict:fetch(escape, St#state.vars)), - {Ms, St#state.vars}. - -loop(T, L, St0) -> -%%% io:fwrite("analyzing: ~w.\n",[L]), -%%% io:fwrite("work: ~w.\n", [St0#state.work]), - Xs0 = dict:fetch(L, St0#state.out), - {Xs1, St1} = visit(fun_body(T), L, St0), - Xs = limit(Xs1, St1#state.k), - {W, M} = case equal(Xs0, Xs) of - true -> - {St1#state.work, St1#state.out}; - false -> -%%% io:fwrite("out (~w) changed: ~w <- ~w.\n", -%%% [L, Xs, Xs0]), - M1 = dict:store(L, Xs, St1#state.out), - case dict:find(L, St1#state.dep) of - {ok, S} -> - {add_work(set__to_list(S), St1#state.work), - M1}; - error -> - {St1#state.work, M1} - end - end, - St2 = St1#state{out = M}, - case take_work(W) of - {ok, L1, W1} -> - T1 = dict:fetch(L1, St2#state.funs), - loop(T1, L1, St2#state{work = W1}); - none -> - St2 - end. - -visit(T, L, St) -> -%%% io:fwrite("visiting: ~w.\n",[type(T)]), - case type(T) of - literal -> - %% This is (or should be) a constant, even if it's compound, - %% so it's bugger all whether it is sent or not. - case cerl:concrete(T) of - [] -> {[empty()], St}; - X when is_atom(X) -> {[empty()], St}; - X when is_integer(X) -> {[empty()], St}; - X when is_float(X) -> {[empty()], St}; - _ -> - exit({not_literal, T}) - end; - var -> - %% If a variable is not already in the store here, it must - %% be free in the program. - L1 = get_label(T), - Vars = St#state.vars, - case dict:find(L1, Vars) of - {ok, X} -> - {[X], St}; - error -> -%%% io:fwrite("free var: ~w.\n",[L1]), - X = unsafe(), - St1 = St#state{vars = dict:store(L1, X, Vars)}, - {[X], St1} - end; - 'fun' -> - %% Must revisit the fun also, because its environment might - %% have changed. (We don't keep track of such dependencies.) - L1 = get_label(T), - St1 = St#state{work = add_work([L1], St#state.work)}, - %% Currently, lambda expressions can only be locally - %% allocated, and therefore we have to force copying by - %% treating them as "unsafe" for now. - {[unsafe()], St1}; - %% {[singleton(L1)], St1}; - values -> - visit_list(values_es(T), L, St); - cons -> - {[X1, X2], St1} = visit_list([cons_hd(T), cons_tl(T)], L, St), - L1 = get_label(T), - X = make_cons(L1, X1, X2), - %% Also store the values of the elements. - Hd = get_hd(X), - Tl = get_tl(X), - St2 = St1#state{vars = dict:store(L1, [Hd, Tl], St1#state.vars)}, - {[X], St2}; - tuple -> - {Xs, St1} = visit_list(tuple_es(T), L, St), - L1 = get_label(T), - %% Also store the values of the elements. - St2 = St1#state{vars = dict:store(L1, Xs, St1#state.vars)}, - {[struct(L1, Xs)], St2}; - 'let' -> - {Xs, St1} = visit(let_arg(T), L, St), - Vars = bind_vars(let_vars(T), Xs, St1#state.vars), - visit(let_body(T), L, St1#state{vars = Vars}); - seq -> - {_, St1} = visit(seq_arg(T), L, St), - visit(seq_body(T), L, St1); - apply -> - {_F, St1} = visit(apply_op(T), L, St), - {As, St2} = visit_list(apply_args(T), L, St1), - L1 = get_label(T), - Ls = get_deps(L1, St#state.dep), - Out = St2#state.out, - Xs1 = join_list([dict:fetch(X, Out) || X <- Ls]), - {Xs1, call_site(Ls, As, St2)}; - call -> - M = call_module(T), - F = call_name(T), - As = call_args(T), - {_, St1} = visit(M, L, St), - {_, St2} = visit(F, L, St1), - {Xs, St3} = visit_list(As, L, St2), - L1 = get_label(T), - remote_call(M, F, Xs, As, L1, St3); - primop -> - As = primop_args(T), - {Xs, St1} = visit_list(As, L, St), - F = atom_val(primop_name(T)), - primop_call(F, length(Xs), Xs, As, St1); - 'case' -> - {Xs, St1} = visit(case_arg(T), L, St), - visit_clauses(Xs, case_clauses(T), L, St1); - 'receive' -> - %% The received value is of course a message, so it - %% is 'empty()', not 'unsafe()'. - X = empty(), - {Xs1, St1} = visit_clauses([X], receive_clauses(T), L, St), - {_, St2} = visit(receive_timeout(T), L, St1), - {Xs2, St3} = visit(receive_action(T), L, St2), - {join(Xs1, Xs2), St3}; - 'try' -> - {Xs1, St1} = visit(try_arg(T), L, St), - X = unsafe(), - Vars = bind_vars(try_vars(T), Xs1, St1#state.vars), - {Xs2, St2} = visit(try_body(T), L, St1#state{vars = Vars}), - EVars = bind_vars(try_evars(T), [X, X, X], St2#state.vars), - {Xs3, St3} = visit(try_handler(T), L, St2#state{vars = EVars}), - {join(Xs2, Xs3), St3}; - 'catch' -> - %% If we catch an exception, we can get unsafe data. - {Xs, St1} = visit(catch_body(T), L, St), - {join([unsafe()], Xs), St1}; - binary -> - %% Binaries are heap objects, but we don't have special - %% shared-heap allocation operators for them at the moment. - %% They must therefore be treated as unsafe. - {_, St1} = visit_list(binary_segments(T), L, St), - {[unsafe()], St1}; - bitstr -> - %% The other fields are constant literals. - {_, St1} = visit(bitstr_val(T), L, St), - {_, St2} = visit(bitstr_size(T), L, St1), - {none, St2}; - letrec -> - %% All the bound funs should be revisited, because the - %% environment might have changed. - Ls = [get_label(F) || {_, F} <- letrec_defs(T)], - St1 = St#state{work = add_work(Ls, St#state.work)}, - visit(letrec_body(T), L, St1); - module -> - %% We regard a module as a tuple of function variables in - %% the body of a `letrec'. - visit(c_letrec(module_defs(T), - ann_c_tuple([{label, get_label(T)}], - module_exports(T))), - L, St) - end. - -visit_clause(T, Xs, L, St) -> - Vars = bind_pats(clause_pats(T), Xs, St#state.vars), - {_, St1} = visit(clause_guard(T), L, St#state{vars = Vars}), - visit(clause_body(T), L, St1). - -%% We assume correct value-list typing. - -visit_list([T | Ts], L, St) -> - {Xs, St1} = visit(T, L, St), - {Xs1, St2} = visit_list(Ts, L, St1), - X = case Xs of - [X1] -> X1; - _ -> empty() - end, - {[X | Xs1], St2}; -visit_list([], _L, St) -> - {[], St}. - -visit_clauses(Xs, [T | Ts], L, St) -> - {Xs1, St1} = visit_clause(T, Xs, L, St), - {Xs2, St2} = visit_clauses(Xs, Ts, L, St1), - {join(Xs1, Xs2), St2}; -visit_clauses(_, [], _L, St) -> - {none, St}. - -bind_defs([{V, F} | Ds], Vars) -> - bind_defs(Ds, dict:store(get_label(V), singleton(get_label(F)), Vars)); -bind_defs([], Vars) -> - Vars. - -bind_pats(Ps, none, Vars) -> - bind_pats_single(Ps, empty(), Vars); -bind_pats(Ps, Xs, Vars) -> - if length(Xs) =:= length(Ps) -> - bind_pats_list(Ps, Xs, Vars); - true -> - bind_pats_single(Ps, empty(), Vars) - end. - -%% The lists might not be of the same length. - -bind_pats_list([P | Ps], [X | Xs], Vars) -> - bind_pats_list(Ps, Xs, bind_pat_vars(P, X, Vars)); -bind_pats_list(Ps, [], Vars) -> - bind_pats_single(Ps, empty(), Vars); -bind_pats_list([], _, Vars) -> - Vars. - -bind_pats_single([P | Ps], X, Vars) -> - bind_pats_single(Ps, X, bind_pat_vars(P, X, Vars)); -bind_pats_single([], _X, Vars) -> - Vars. - -bind_pat_vars(P, X, Vars) -> - case type(P) of - var -> - dict:store(get_label(P), X, Vars); - literal -> - Vars; - cons -> - bind_pats_list([cons_hd(P), cons_tl(P)], - [get_hd(X), get_tl(X)], Vars); - tuple -> - case elements(X) of - none -> - bind_vars_single(pat_vars(P), X, Vars); - Xs -> - bind_pats_list(tuple_es(P), Xs, Vars) - end; - binary -> - %% See the handling of binary-expressions. - bind_pats_single(binary_segments(P), unsafe(), Vars); - bitstr -> - %% See the handling of binary-expressions. - bind_pats_single([bitstr_val(P), bitstr_size(P)], - unsafe(), Vars); - alias -> - P1 = alias_pat(P), - Vars1 = bind_pat_vars(P1, X, Vars), - dict:store(get_label(alias_var(P)), X, Vars1) - end. - -%%% %% This is the "exact" version of list representation, which simply -%%% %% mimics the actual cons, head and tail operations. -%%% make_cons(L, X1, X2) -> -%%% struct(L1, [X1, X2]). -%%% get_hd(X) -> -%%% case elements(X) of -%%% none -> X; -%%% [X1 | _] -> X1; -%%% _ -> empty() -%%% end. -%%% get_tl(X) -> -%%% case elements(X) of -%%% none -> X; -%%% [_, X2 | _] -> X2; -%%% _ -> empty() -%%% end. - -%% This version does not unnecessarily confuse spine labels with element -%% labels, and is safe. However, it loses precision if cons cells are -%% used for other things than proper lists. - -make_cons(L, X1, X2) -> - %% join subtypes and cons locations - join_single(struct(L, [X1]), X2). - -get_hd(X) -> - case elements(X) of - none -> X; - [X1 | _] -> X1; % First element represents list subtype. - _ -> empty() - end. - -get_tl(X) -> X. % Tail of X has same type as X. - -bind_vars(Vs, none, Vars) -> - bind_vars_single(Vs, empty(), Vars); -bind_vars(Vs, Xs, Vars) -> - if length(Vs) =:= length(Xs) -> - bind_vars_list(Vs, Xs, Vars); - true -> - bind_vars_single(Vs, empty(), Vars) - end. - -bind_vars_list([V | Vs], [X | Xs], Vars) -> - bind_vars_list(Vs, Xs, dict:store(get_label(V), X, Vars)); -bind_vars_list([], [], Vars) -> - Vars. - -bind_vars_single([V | Vs], X, Vars) -> - bind_vars_single(Vs, X, dict:store(get_label(V), X, Vars)); -bind_vars_single([], _X, Vars) -> - Vars. - -%% This handles a call site, updating parameter variables with respect -%% to the actual parameters. The 'external' function is handled -%% specially, since it can get an arbitrary number of arguments. For our -%% purposes here, calls to the external function can be ignored. - -call_site(Ls, Xs, St) -> -%%% io:fwrite("call site: ~w -> ~w (~w).\n", [L, Ls, Xs]), - {W, V} = call_site(Ls, Xs, St#state.work, St#state.vars, - St#state.funs, St#state.k), - St#state{work = W, vars = V}. - -call_site([external | Ls], Xs, W, V, Fs, Limit) -> - call_site(Ls, Xs, W, V, Fs, Limit); -call_site([L | Ls], Xs, W, V, Fs, Limit) -> - Vs = fun_vars(dict:fetch(L, Fs)), - case bind_args(Vs, Xs, V, Limit) of - {V1, true} -> - call_site(Ls, Xs, add_work([L], W), V1, Fs, Limit); - {V1, false} -> - call_site(Ls, Xs, W, V1, Fs, Limit) - end; -call_site([], _, W, V, _, _) -> - {W, V}. - -add_dep(Source, Target, Deps) -> - case dict:find(Source, Deps) of - {ok, X} -> - case set__is_member(Target, X) of - true -> - Deps; - false -> -%%% io:fwrite("new dep: ~w <- ~w.\n", [Target, Source]), - dict:store(Source, set__add(Target, X), Deps) - end; - error -> -%%% io:fwrite("new dep: ~w <- ~w.\n", [Target, Source]), - dict:store(Source, set__singleton(Target), Deps) - end. - -%% If the arity does not match the call, nothing is done here. - -bind_args(Vs, Xs, Vars, Limit) -> - if length(Vs) =:= length(Xs) -> - bind_args(Vs, Xs, Vars, Limit, false); - true -> - {Vars, false} - end. - -bind_args([V | Vs], [X | Xs], Vars, Limit, Ch) -> - L = get_label(V), - {Vars1, Ch1} = bind_arg(L, X, Vars, Limit, Ch), - bind_args(Vs, Xs, Vars1, Limit, Ch1); -bind_args([], [], Vars, _Limit, Ch) -> - {Vars, Ch}. - -%% bind_arg(L, X, Vars, Limit) -> -%% bind_arg(L, X, Vars, Limit, false). - -bind_arg(L, X, Vars, Limit, Ch) -> - X0 = dict:fetch(L, Vars), - X1 = limit_single(join_single(X, X0), Limit), - case equal_single(X0, X1) of - true -> - {Vars, Ch}; - false -> -%%% io:fwrite("arg (~w) changed: ~w <- ~w + ~w.\n", -%%% [L, X1, X0, X]), - {dict:store(L, X1, Vars), true} - end. - -%% This handles escapes from things like primops and remote calls. - -escape(Xs, Ns, St) -> - escape(Xs, Ns, 1, St). - -escape([_ | Xs], Ns=[N1 | _], N, St) when is_integer(N1), N1 > N -> - escape(Xs, Ns, N + 1, St); -escape([X | Xs], [N | Ns], N, St) -> - Vars = St#state.vars, - X0 = dict:fetch(escape, Vars), - X1 = join_single(X, X0), - case equal_single(X0, X1) of - true -> - escape(Xs, Ns, N + 1, St); - false -> -%%% io:fwrite("escape changed: ~w <- ~w + ~w.\n", [X1, X0, X]), - Vars1 = dict:store(escape, X1, Vars), - escape(Xs, Ns, N + 1, St#state{vars = Vars1}) - end; -escape(Xs, [_ | Ns], N, St) -> - escape(Xs, Ns, N + 1, St); -escape(_, _, _, St) -> - St. - -%% Handle primop calls: (At present, we assume that all unknown calls -%% yield exactly one value. This might have to be changed.) - -primop_call(F, A, Xs, _As, St0) -> - %% St1 = case is_escape_op(F, A) of - %% [] -> St0; - %% Ns -> escape(Xs, Ns, St0) - %% end, - St1 = St0, - case is_imm_op(F, A) of - true -> - {[empty()], St1}; - false -> - call_unknown(Xs, St1) - end. - -%% Handle remote-calls: (At present, we assume that all unknown calls -%% yield exactly one value. This might have to be changed.) - -remote_call(M, F, Xs, As, L, St) -> - case is_c_atom(M) andalso is_c_atom(F) of - true -> - remote_call_1(atom_val(M), atom_val(F), length(Xs), - Xs, As, L, St); - false -> - %% Unknown function - call_unknown(Xs, St) - end. - -%% When calling an unknown function, we assume that the result does -%% *not* contain any of the constructors in its arguments (but it could -%% return locally allocated data that we don't know about). Note that -%% even a "pure" function can still cons up new data. - -call_unknown(_Xs, St) -> - {[unsafe()], St}. - -%% We need to handle some important standard functions in order to get -%% decent precision. -%% TODO: foldl, map, mapfoldl - -remote_call_1(erlang, hd, 1, [X], _As, _L, St) -> - {[get_hd(X)], St}; -remote_call_1(erlang, tl, 1, [X], _As, _L, St) -> - {[get_tl(X)], St}; -remote_call_1(erlang, element, 2, [_,X], [N|_], _L, St) -> - case elements(X) of - none -> {[X], St}; - Xs -> - case is_c_int(N) of - true -> - N1 = int_val(N), - if is_integer(N1), 1 =< N1, N1 =< length(Xs) -> - {[nth(N1, Xs)], St}; - true -> - {none, St} - end; - false -> - %% Even if we don't know which element is selected, - %% we know that the top level is never part of the - %% returned value. - {[join_single_list(Xs)], St} - end - end; -remote_call_1(erlang, setelement, 3, [_,X, Y], [N|_], L, St) -> - %% The constructor gets the label of the call operation. - case elements(X) of - none -> {[join_single(singleton(L), join_single(X, Y))], St}; - Xs -> - case is_c_int(N) of - true -> - N1 = int_val(N), - if is_integer(N1), 1 =< N1, N1 =< length(Xs) -> - Xs1 = set_nth(N1, Y, Xs), - {[struct(L, Xs1)], St}; - true -> - {none, St} - end; - false -> - %% Even if we don't know which element is selected, - %% we know that the top level is never part of the - %% returned value (a new tuple is always created). - Xs1 = [join_single(Y, X1) || X1 <- Xs], - {[struct(L, Xs1)], St} - end - end; -remote_call_1(erlang, '++', 2, [X1,X2], _As, _L, St) -> - %% Note: this is unsafe for non-proper lists! (See make_cons/3). - %% No safe version is implemented. - {[join_single(X1, X2)], St}; -remote_call_1(erlang, '--', 2, [X1,_X2], _As, _L, St) -> - {[X1], St}; -remote_call_1(lists, append, 2, Xs, As, L, St) -> - remote_call_1(erlang, '++', 2, Xs, As, L, St); -remote_call_1(lists, subtract, 2, Xs, As, L, St) -> - remote_call_1(erlang, '--', 2, Xs, As, L, St); -remote_call_1(M, F, A, Xs, _As, _L, St0) -> - St1 = case is_escape_op(M, F, A) of - [] -> St0; - Ns -> escape(Xs, Ns, St0) - end, - case is_imm_op(M, F, A) of - true -> - {[empty()], St1}; - false -> - call_unknown(Xs, St1) - end. - -%% 1-based n:th-element list selector and update function. - -nth(1, [X | _Xs]) -> X; -nth(N, [_X | Xs]) when N > 1 -> nth(N - 1, Xs). - -set_nth(1, Y, [_X | Xs]) -> [Y | Xs]; -set_nth(N, Y, [X | Xs]) when N > 1 -> [X | set_nth(N - 1, Y, Xs)]. - -%% Domain: none | [V], where V = {S, none} | {S, [V]}, S = set(integer()). - -join(none, Xs2) -> Xs2; -join(Xs1, none) -> Xs1; -join(Xs1, Xs2) -> - if length(Xs1) =:= length(Xs2) -> - join_1(Xs1, Xs2); - true -> - none - end. - -join_1([X1 | Xs1], [X2 | Xs2]) -> - [join_single(X1, X2) | join_1(Xs1, Xs2)]; -join_1([], []) -> - []. - -join_list([Xs | Xss]) -> - join(Xs, join_list(Xss)); -join_list([]) -> - none. - -empty() -> {set__new(), []}. - -singleton(X) -> {set__singleton(X), []}. - -struct(X, Xs) -> {set__singleton(X), Xs}. - -elements({_, Xs}) -> Xs. - -unsafe() -> {set__singleton(unsafe), none}. - -equal(none, none) -> true; -equal(none, _) -> false; -equal(_, none) -> false; -equal(X1, X2) -> equal_1(X1, X2). - -equal_1([X1 | Xs1], [X2 | Xs2]) -> - equal_single(X1, X2) andalso equal_1(Xs1, Xs2); -equal_1([], []) -> true; -equal_1(_, _) -> false. - -equal_single({S1, none}, {S2, none}) -> - set__equal(S1, S2); -equal_single({_, none}, _) -> - false; -equal_single(_, {_, none}) -> - false; -equal_single({S1, Vs1}, {S2, Vs2}) -> - set__equal(S1, S2) andalso equal_single_lists(Vs1, Vs2). - -equal_single_lists([X1 | Xs1], [X2 | Xs2]) -> - equal_single(X1, X2) andalso equal_single_lists(Xs1, Xs2); -equal_single_lists([], []) -> - true; -equal_single_lists(_, _) -> - false. - -join_single({S, none}, V) -> - {set__union(S, labels(V)), none}; -join_single(V, {S, none}) -> - {set__union(S, labels(V)), none}; -join_single({S1, Vs1}, {S2, Vs2}) -> - {set__union(S1, S2), join_single_lists(Vs1, Vs2)}. - -join_single_list([V | Vs]) -> - join_single(V, join_single_list(Vs)); -join_single_list([]) -> - empty(). - -%% If one list has more elements that the other, and N is the length of -%% the longer list, then the result has N elements. - -join_single_lists([V1], [V2]) -> - [join_single(V1, V2)]; -join_single_lists([V1 | Vs1], [V2 | Vs2]) -> - [join_single(V1, V2) | join_single_lists(Vs1, Vs2)]; -join_single_lists([], Vs) -> Vs; -join_single_lists(Vs, []) -> Vs. - -collapse(V) -> - {labels(V), none}. - -%% collapse_list([]) -> -%% empty(); -%% collapse_list(Vs) -> -%% {labels_list(Vs), none}. - -labels({S, none}) -> S; -labels({S, []}) -> S; -labels({S, Vs}) -> set__union(S, labels_list(Vs)). - -labels_list([V]) -> - labels(V); -labels_list([V | Vs]) -> - set__union(labels(V), labels_list(Vs)). - -limit(none, _K) -> none; -limit(X, K) -> limit_list(X, K). - -limit_list([X | Xs], K) -> - [limit_single(X, K) | limit_list(Xs, K)]; -limit_list([], _) -> - []. - -limit_single({_, none} = V, _K) -> - V; -limit_single({_, []} = V, _K) -> - V; -limit_single({S, Vs}, K) when K > 0 -> - {S, limit_list(Vs, K - 1)}; -limit_single(V, _K) -> - collapse(V). - -%% Set abstraction for label sets in the domain. - -%% set__is_empty([]) -> true; -%% set__is_empty(_) -> false. - -set__new() -> []. - -set__singleton(X) -> [X]. - -set__to_list(S) -> S. - -%% set__from_list(S) -> ordsets:from_list(S). - -set__union(X, Y) -> ordsets:union(X, Y). - -set__add(X, S) -> ordsets:add_element(X, S). - -set__is_member(X, S) -> ordsets:is_element(X, S). - -%% set__subtract(X, Y) -> ordsets:subtract(X, Y). - -set__equal(X, Y) -> X =:= Y. - -%% A simple but efficient functional queue. - -queue__new() -> {[], []}. - -queue__put(X, {In, Out}) -> {[X | In], Out}. - -queue__get({In, [X | Out]}) -> {ok, X, {In, Out}}; -queue__get({[], _}) -> empty; -queue__get({In, _}) -> - [X | In1] = lists:reverse(In), - {ok, X, {[], In1}}. - -%% The work list - a queue without repeated elements. - -init_work() -> - {queue__new(), sets:new()}. - -add_work(Ls, {Q, Set}) -> - add_work(Ls, Q, Set). - -%% Note that the elements are enqueued in order. - -add_work([L | Ls], Q, Set) -> - case sets:is_element(L, Set) of - true -> - add_work(Ls, Q, Set); - false -> - add_work(Ls, queue__put(L, Q), sets:add_element(L, Set)) - end; -add_work([], Q, Set) -> - {Q, Set}. - -take_work({Queue0, Set0}) -> - case queue__get(Queue0) of - {ok, L, Queue1} -> - Set1 = sets:del_element(L, Set0), - {ok, L, {Queue1, Set1}}; - empty -> - none - end. - -get_deps(L, Dep) -> - case dict:find(L, Dep) of - {ok, Ls} -> Ls; - error -> [] - end. - -%% Escape operators may let their arguments escape. For this analysis, -%% only send-operations are considered as causing escapement, and only -%% in specific arguments. - -%% is_escape_op(_F, _A) -> []. - --spec is_escape_op(atom(), atom(), arity()) -> [arity()]. - -is_escape_op(erlang, '!', 2) -> [2]; -is_escape_op(erlang, send, 2) -> [2]; -is_escape_op(erlang, spawn, 1) -> [1]; -is_escape_op(erlang, spawn, 3) -> [3]; -is_escape_op(erlang, spawn, 4) -> [4]; -is_escape_op(erlang, spawn_link, 3) -> [3]; -is_escape_op(erlang, spawn_link, 4) -> [4]; -is_escape_op(_M, _F, _A) -> []. - -%% "Immediate" operators will never return heap allocated data. This is -%% of course true for operators that never return, like 'exit/1'. (Note -%% that floats are always heap allocated objects, and that most integer -%% arithmetic can return a bignum on the heap.) - --spec is_imm_op(atom(), arity()) -> boolean(). - -is_imm_op(match_fail, 1) -> true; -is_imm_op(_, _) -> false. - --spec is_imm_op(atom(), atom(), arity()) -> boolean(). - -is_imm_op(erlang, self, 0) -> true; -is_imm_op(erlang, '=:=', 2) -> true; -is_imm_op(erlang, '==', 2) -> true; -is_imm_op(erlang, '=/=', 2) -> true; -is_imm_op(erlang, '/=', 2) -> true; -is_imm_op(erlang, '<', 2) -> true; -is_imm_op(erlang, '=<', 2) -> true; -is_imm_op(erlang, '>', 2) -> true; -is_imm_op(erlang, '>=', 2) -> true; -is_imm_op(erlang, 'and', 2) -> true; -is_imm_op(erlang, 'or', 2) -> true; -is_imm_op(erlang, 'xor', 2) -> true; -is_imm_op(erlang, 'not', 1) -> true; -is_imm_op(erlang, is_alive, 0) -> true; -is_imm_op(erlang, is_atom, 1) -> true; -is_imm_op(erlang, is_binary, 1) -> true; -is_imm_op(erlang, is_builtin, 3) -> true; -is_imm_op(erlang, is_float, 1) -> true; -is_imm_op(erlang, is_function, 1) -> true; -is_imm_op(erlang, is_integer, 1) -> true; -is_imm_op(erlang, is_list, 1) -> true; -is_imm_op(erlang, is_number, 1) -> true; -is_imm_op(erlang, is_pid, 1) -> true; -is_imm_op(erlang, is_port, 1) -> true; -is_imm_op(erlang, is_process_alive, 1) -> true; -is_imm_op(erlang, is_reference, 1) -> true; -is_imm_op(erlang, is_tuple, 1) -> true; -is_imm_op(erlang, length, 1) -> true; % never a bignum -is_imm_op(erlang, list_to_atom, 1) -> true; -is_imm_op(erlang, node, 0) -> true; -is_imm_op(erlang, node, 1) -> true; -is_imm_op(erlang, throw, 1) -> true; -is_imm_op(erlang, exit, 1) -> true; -is_imm_op(erlang, error, 1) -> true; -is_imm_op(erlang, error, 2) -> true; -is_imm_op(_M, _F, _A) -> false. diff --git a/lib/hipe/cerl/erl_bif_types.erl b/lib/hipe/cerl/erl_bif_types.erl index 518f67ee1b..8ae1cd4ab7 100644 --- a/lib/hipe/cerl/erl_bif_types.erl +++ b/lib/hipe/cerl/erl_bif_types.erl @@ -585,6 +585,13 @@ type(erlang, float, 1, Xs, Opaques) -> %% Guard bif, needs to be here. type(erlang, floor, 1, Xs, Opaques) -> strict(erlang, floor, 1, Xs, fun (_) -> t_integer() end, Opaques); +%% Primop, needs to be somewhere. +type(erlang, build_stacktrace, 0, _, _Opaques) -> + t_list(t_tuple([t_module(), + t_atom(), + t_sup([t_arity(),t_list()]), + t_list(t_sup([t_tuple([t_atom('file'),t_string()]), + t_tuple([t_atom('line'),t_pos_integer()])]))])); %% Guard bif, needs to be here. type(erlang, hd, 1, Xs, Opaques) -> strict(erlang, hd, 1, Xs, fun ([X]) -> t_cons_hd(X) end, Opaques); @@ -658,6 +665,8 @@ type(erlang, is_map, 1, Xs, Opaques) -> check_guard(X, fun (Y) -> t_is_map(Y, Opaques) end, t_map(), Opaques) end, strict(erlang, is_map, 1, Xs, Fun, Opaques); +type(erlang, is_map_key, 2, Xs, Opaques) -> + type(maps, is_key, 2, Xs, Opaques); type(erlang, is_number, 1, Xs, Opaques) -> Fun = fun (X) -> check_guard(X, fun (Y) -> t_is_number(Y, Opaques) end, @@ -763,6 +772,9 @@ type(erlang, length, 1, Xs, Opaques) -> %% Guard bif, needs to be here. type(erlang, map_size, 1, Xs, Opaques) -> type(maps, size, 1, Xs, Opaques); +%% Guard bif, needs to be here. +type(erlang, map_get, 2, Xs, Opaques) -> + type(maps, get, 2, Xs, Opaques); type(erlang, make_fun, 3, Xs, Opaques) -> strict(erlang, make_fun, 3, Xs, fun ([_, _, Arity]) -> @@ -1701,24 +1713,6 @@ type(maps, size, 1, Xs, Opaques) -> t_from_range(LowerBound, UpperBound) end end, Opaques); -type(maps, to_list, 1, Xs, Opaques) -> - strict(maps, to_list, 1, Xs, - fun ([Map]) -> - DefK = t_map_def_key(Map, Opaques), - DefV = t_map_def_val(Map, Opaques), - Pairs = t_map_entries(Map, Opaques), - EType = lists:foldl( - fun({K,_,V},EType0) -> - case t_is_none(V) of - true -> t_subtract(EType0, t_tuple([K,t_any()])); - false -> t_sup(EType0, t_tuple([K,V])) - end - end, t_tuple([DefK, DefV]), Pairs), - case t_is_none(EType) of - true -> t_nil(); - false -> t_list(EType) - end - end, Opaques); type(maps, update, 3, Xs, Opaques) -> strict(maps, update, 3, Xs, fun ([Key, Value, Map]) -> @@ -2231,10 +2225,7 @@ type_order() -> t_map(), t_list(), t_bitstr()]. key_comparisons_fail(X0, KeyPos, TupleList, Opaques) -> - X = case t_is_number(t_inf(X0, t_number(), Opaques), Opaques) of - false -> X0; - true -> t_number() - end, + X = erl_types:t_widen_to_number(X0), lists:all(fun(Tuple) -> Key = type(erlang, element, 2, [KeyPos, Tuple]), t_is_none(t_inf(Key, X, Opaques)) @@ -2354,6 +2345,9 @@ arg_types(erlang, float, 1) -> %% Guard bif, needs to be here. arg_types(erlang, floor, 1) -> [t_number()]; +%% Primop, needs to be somewhere. +arg_types(erlang, build_stacktrace, 0) -> + []; %% Guard bif, needs to be here. arg_types(erlang, hd, 1) -> [t_cons()]; @@ -2379,6 +2373,8 @@ arg_types(erlang, is_list, 1) -> [t_any()]; arg_types(erlang, is_map, 1) -> [t_any()]; +arg_types(erlang, is_map_key, 2) -> + [t_any(), t_map()]; arg_types(erlang, is_number, 1) -> [t_any()]; arg_types(erlang, is_pid, 1) -> @@ -2399,6 +2395,9 @@ arg_types(erlang, length, 1) -> %% Guard bif, needs to be here. arg_types(erlang, map_size, 1) -> [t_map()]; +%% Guard bif, needs to be here. +arg_types(erlang, map_get, 2) -> + [t_any(), t_map()]; arg_types(erlang, make_fun, 3) -> [t_atom(), t_atom(), t_arity()]; arg_types(erlang, make_tuple, 2) -> @@ -2651,8 +2650,6 @@ arg_types(maps, put, 3) -> [t_any(), t_any(), t_map()]; arg_types(maps, size, 1) -> [t_map()]; -arg_types(maps, to_list, 1) -> - [t_map()]; arg_types(maps, update, 3) -> [t_any(), t_any(), t_map()]; arg_types(M, F, A) when is_atom(M), is_atom(F), diff --git a/lib/hipe/cerl/erl_types.erl b/lib/hipe/cerl/erl_types.erl index 2b290b2f23..d61cd8664c 100644 --- a/lib/hipe/cerl/erl_types.erl +++ b/lib/hipe/cerl/erl_types.erl @@ -66,7 +66,6 @@ t_find_opaque_mismatch/3, t_find_unknown_opaque/3, t_fixnum/0, - t_map/2, t_non_neg_fixnum/0, t_pos_fixnum/0, t_float/0, @@ -108,13 +107,14 @@ t_is_bitstr/1, t_is_bitstr/2, t_is_bitwidth/1, t_is_boolean/1, t_is_boolean/2, - %% t_is_byte/1, - %% t_is_char/1, + t_is_byte/1, + t_is_char/1, t_is_cons/1, t_is_cons/2, t_is_equal/2, t_is_fixnum/1, t_is_float/1, t_is_float/2, t_is_fun/1, t_is_fun/2, + t_is_identifier/1, t_is_instance/2, t_is_integer/1, t_is_integer/2, t_is_list/1, @@ -204,6 +204,7 @@ t_unopaque/1, t_unopaque/2, t_var/1, t_var_name/1, + t_widen_to_number/1, %% t_assign_variables_to_subtype/2, type_is_defined/4, record_field_diffs_to_string/2, @@ -216,18 +217,7 @@ cache__new/0 ]). -%%-define(DO_ERL_TYPES_TEST, true). --compile({no_auto_import,[min/2,max/2]}). - --ifdef(DO_ERL_TYPES_TEST). --export([test/0]). --else. --define(NO_UNUSED, true). --endif. - --ifndef(NO_UNUSED). --export([t_is_identifier/1]). --endif. +-compile({no_auto_import,[min/2,max/2,map_get/2]}). -export_type([erl_type/0, opaques/0, type_table/0, var_table/0, cache/0]). @@ -1190,12 +1180,10 @@ is_fun(_) -> false. t_identifier() -> ?identifier(?any). --ifdef(DO_ERL_TYPES_TEST). --spec t_is_identifier(erl_type()) -> erl_type(). +-spec t_is_identifier(erl_type()) -> boolean(). t_is_identifier(?identifier(_)) -> true; t_is_identifier(_) -> false. --endif. %%------------------------------------ @@ -1366,7 +1354,6 @@ is_integer1(_) -> false. t_byte() -> ?byte. --ifdef(DO_ERL_TYPES_TEST). -spec t_is_byte(erl_type()) -> boolean(). t_is_byte(?int_range(neg_inf, _)) -> false; @@ -1376,7 +1363,6 @@ t_is_byte(?int_range(From, To)) t_is_byte(?int_set(Set)) -> (set_min(Set) >= 0) andalso (set_max(Set) =< ?MAX_BYTE); t_is_byte(_) -> false. --endif. %%------------------------------------ @@ -1608,6 +1594,50 @@ lift_list_to_pos_empty(?nil) -> ?nil; lift_list_to_pos_empty(?list(Content, Termination, _)) -> ?list(Content, Termination, ?unknown_qual). +-spec t_widen_to_number(erl_type()) -> erl_type(). + +%% Widens integers and floats to t_number(). +%% Used by erl_bif_types:key_comparison_fail(). + +t_widen_to_number(?any) -> ?any; +t_widen_to_number(?none) -> ?none; +t_widen_to_number(?unit) -> ?unit; +t_widen_to_number(?atom(_Set) = T) -> T; +t_widen_to_number(?bitstr(_Unit, _Base) = T) -> T; +t_widen_to_number(?float) -> t_number(); +t_widen_to_number(?function(Domain, Range)) -> + ?function(t_widen_to_number(Domain), t_widen_to_number(Range)); +t_widen_to_number(?identifier(_Types) = T) -> T; +t_widen_to_number(?int_range(_From, _To)) -> t_number(); +t_widen_to_number(?int_set(_Set)) -> t_number(); +t_widen_to_number(?integer(_Types)) -> t_number(); +t_widen_to_number(?list(Type, Tail, Size)) -> + ?list(t_widen_to_number(Type), t_widen_to_number(Tail), Size); +t_widen_to_number(?map(Pairs, DefK, DefV)) -> + L = [{t_widen_to_number(K), MNess, t_widen_to_number(V)} || + {K, MNess, V} <- Pairs], + t_map(L, t_widen_to_number(DefK), t_widen_to_number(DefV)); +t_widen_to_number(?matchstate(_P, _Slots) = T) -> T; +t_widen_to_number(?nil) -> ?nil; +t_widen_to_number(?number(_Set, _Tag)) -> t_number(); +t_widen_to_number(?opaque(Set)) -> + L = [Opaque#opaque{struct = t_widen_to_number(S)} || + #opaque{struct = S} = Opaque <- set_to_list(Set)], + ?opaque(ordsets:from_list(L)); +t_widen_to_number(?product(Types)) -> + ?product(list_widen_to_number(Types)); +t_widen_to_number(?tuple(?any, _, _) = T) -> T; +t_widen_to_number(?tuple(Types, Arity, Tag)) -> + ?tuple(list_widen_to_number(Types), Arity, Tag); +t_widen_to_number(?tuple_set(_) = Tuples) -> + t_sup([t_widen_to_number(T) || T <- t_tuple_subtypes(Tuples)]); +t_widen_to_number(?union(List)) -> + ?union(list_widen_to_number(List)); +t_widen_to_number(?var(_Id)= T) -> T. + +list_widen_to_number(List) -> + [t_widen_to_number(E) || E <- List]. + %%----------------------------------------------------------------------------- %% Maps %% @@ -3118,9 +3148,18 @@ is_compat_arg(?list(Contents1, Termination1, Size1), is_compat_arg(?product(Types1), ?product(Types2)) -> is_compat_list(Types1, Types2); is_compat_arg(?map(Pairs1, DefK1, DefV1), ?map(Pairs2, DefK2, DefV2)) -> - (is_compat_list(Pairs1, Pairs2) andalso - is_compat_arg(DefK1, DefK2) andalso - is_compat_arg(DefV1, DefV2)); + {Ks1, _, Vs1} = lists:unzip3(Pairs1), + {Ks2, _, Vs2} = lists:unzip3(Pairs2), + Key1 = t_sup([DefK1 | Ks1]), + Key2 = t_sup([DefK2 | Ks2]), + case is_compat_arg(Key1, Key2) of + true -> + Value1 = t_sup([DefV1 | Vs1]), + Value2 = t_sup([DefV2 | Vs2]), + is_compat_arg(Value1, Value2); + false -> + false + end; is_compat_arg(?tuple(?any, ?any, ?any), ?tuple(_, _, _)) -> false; is_compat_arg(?tuple(_, _, _), ?tuple(?any, ?any, ?any)) -> false; is_compat_arg(?tuple(Elements1, Arity, _), @@ -4170,39 +4209,6 @@ t_abstract_records(?opaque(_)=Type, RecDict) -> t_abstract_records(T, _RecDict) -> T. -%% Map over types. Depth first. Used by the contract checker. ?list is -%% not fully implemented so take care when changing the type in Termination. - --spec t_map(fun((erl_type()) -> erl_type()), erl_type()) -> erl_type(). - -t_map(Fun, ?list(Contents, Termination, Size)) -> - Fun(?list(t_map(Fun, Contents), t_map(Fun, Termination), Size)); -t_map(Fun, ?function(Domain, Range)) -> - Fun(?function(t_map(Fun, Domain), t_map(Fun, Range))); -t_map(Fun, ?product(Types)) -> - Fun(?product([t_map(Fun, T) || T <- Types])); -t_map(Fun, ?union(Types)) -> - Fun(t_sup([t_map(Fun, T) || T <- Types])); -t_map(Fun, ?tuple(?any, ?any, ?any) = T) -> - Fun(T); -t_map(Fun, ?tuple(Elements, _Arity, _Tag)) -> - Fun(t_tuple([t_map(Fun, E) || E <- Elements])); -t_map(Fun, ?tuple_set(_) = Tuples) -> - Fun(t_sup([t_map(Fun, T) || T <- t_tuple_subtypes(Tuples)])); -t_map(Fun, ?opaque(Set)) -> - L = [Opaque#opaque{struct = NewS} || - #opaque{struct = S} = Opaque <- set_to_list(Set), - not t_is_none(NewS = t_map(Fun, S))], - Fun(case L of - [] -> ?none; - _ -> ?opaque(ordsets:from_list(L)) - end); -t_map(Fun, ?map(Pairs,DefK,DefV)) -> - %% TODO: - Fun(t_map(Pairs, Fun(DefK), Fun(DefV))); -t_map(Fun, T) -> - Fun(T). - %%============================================================================= %% %% Prettyprinter @@ -4257,13 +4263,13 @@ t_to_string(?identifier(Set), _RecDict) -> case Set of ?any -> "identifier()"; _ -> - string:join([flat_format("~w()", [T]) || T <- set_to_list(Set)], " | ") + flat_join([flat_format("~w()", [T]) || T <- set_to_list(Set)], " | ") end; t_to_string(?opaque(Set), RecDict) -> - string:join([opaque_type(Mod, Name, Args, S, RecDict) || - #opaque{mod = Mod, name = Name, struct = S, args = Args} - <- set_to_list(Set)], - " | "); + flat_join([opaque_type(Mod, Name, Args, S, RecDict) || + #opaque{mod = Mod, name = Name, struct = S, args = Args} + <- set_to_list(Set)], + " | "); t_to_string(?matchstate(Pres, Slots), RecDict) -> flat_format("ms(~ts,~ts)", [t_to_string(Pres, RecDict), t_to_string(Slots,RecDict)]); @@ -4354,9 +4360,9 @@ t_to_string(?map(Pairs0,DefK,DefV), RecDict) -> end end, StrMand = [{Tos(K),Tos(V)}||{K,?mand,V}<-Pairs], StrOpt = [{Tos(K),Tos(V)}||{K,?opt,V}<-Pairs], - "#{" ++ string:join([K ++ ":=" ++ V||{K,V}<-StrMand] - ++ [K ++ "=>" ++ V||{K,V}<-StrOpt] - ++ ExtraEl, ", ") ++ "}"; + "#{" ++ flat_join([K ++ ":=" ++ V||{K,V}<-StrMand] + ++ [K ++ "=>" ++ V||{K,V}<-StrOpt] + ++ ExtraEl, ", ") ++ "}"; t_to_string(?tuple(?any, ?any, ?any), _RecDict) -> "tuple()"; t_to_string(?tuple(Elements, _Arity, ?any), RecDict) -> "{" ++ comma_sequence(Elements, RecDict) ++ "}"; @@ -4379,7 +4385,7 @@ t_to_string(?var(Id), _RecDict) when is_integer(Id) -> record_to_string(Tag, [_|Fields], FieldNames, RecDict) -> FieldStrings = record_fields_to_string(Fields, FieldNames, RecDict, []), - "#" ++ atom_to_string(Tag) ++ "{" ++ string:join(FieldStrings, ",") ++ "}". + "#" ++ atom_to_string(Tag) ++ "{" ++ flat_join(FieldStrings, ",") ++ "}". record_fields_to_string([F|Fs], [{FName, _Abstr, DefType}|FDefs], RecDict, Acc) -> @@ -4405,7 +4411,7 @@ record_field_diffs_to_string(?tuple([_|Fs], Arity, Tag), RecDict) -> {ok, FieldNames} = lookup_record(TagAtom, Arity-1, RecDict), %% io:format("RecCElems = ~p\nRecTypes = ~p\n", [Fs, FieldNames]), FieldDiffs = field_diffs(Fs, FieldNames, RecDict, []), - string:join(FieldDiffs, " and "). + flat_join(FieldDiffs, " and "). field_diffs([F|Fs], [{FName, _Abstr, DefType}|FDefs], RecDict, Acc) -> %% Don't care about opacity for now. @@ -4425,11 +4431,11 @@ comma_sequence(Types, RecDict) -> true -> "_"; false -> t_to_string(T, RecDict) end || T <- Types], - string:join(List, ","). + flat_join(List, ","). union_sequence(Types, RecDict) -> List = [t_to_string(T, RecDict) || T <- Types], - string:join(List, " | "). + flat_join(List, " | "). -ifdef(DEBUG). opaque_type(Mod, Name, _Args, S, RecDict) -> @@ -5269,7 +5275,7 @@ t_form_to_string({ann_type, _L, [Var, Type]}) -> t_form_to_string({paren_type, _L, [Type]}) -> flat_format("(~ts)", [t_form_to_string(Type)]); t_form_to_string({remote_type, _L, [{atom, _, Mod}, {atom, _, Name}, Args]}) -> - ArgString = "(" ++ string:join(t_form_to_string_list(Args), ",") ++ ")", + ArgString = "(" ++ flat_join(t_form_to_string_list(Args), ",") ++ ")", flat_format("~w:~tw", [Mod, Name]) ++ ArgString; t_form_to_string({type, _L, arity, []}) -> "arity()"; t_form_to_string({type, _L, binary, []}) -> "binary()"; @@ -5292,7 +5298,7 @@ t_form_to_string({type, _L, 'fun', []}) -> "fun()"; t_form_to_string({type, _L, 'fun', [{type, _, any}, Range]}) -> "fun(...) -> " ++ t_form_to_string(Range); t_form_to_string({type, _L, 'fun', [{type, _, product, Domain}, Range]}) -> - "fun((" ++ string:join(t_form_to_string_list(Domain), ",") ++ ") -> " + "fun((" ++ flat_join(t_form_to_string_list(Domain), ",") ++ ") -> " ++ t_form_to_string(Range) ++ ")"; t_form_to_string({type, _L, iodata, []}) -> "iodata()"; t_form_to_string({type, _L, iolist, []}) -> "iolist()"; @@ -5300,7 +5306,7 @@ t_form_to_string({type, _L, list, [Type]}) -> "[" ++ t_form_to_string(Type) ++ "]"; t_form_to_string({type, _L, map, any}) -> "map()"; t_form_to_string({type, _L, map, Args}) -> - "#{" ++ string:join(t_form_to_string_list(Args), ",") ++ "}"; + "#{" ++ flat_join(t_form_to_string_list(Args), ",") ++ "}"; t_form_to_string({type, _L, map_field_assoc, [Key, Val]}) -> t_form_to_string(Key) ++ "=>" ++ t_form_to_string(Val); t_form_to_string({type, _L, map_field_exact, [Key, Val]}) -> @@ -5312,7 +5318,7 @@ t_form_to_string({type, _L, nonempty_list, [Type]}) -> "[" ++ t_form_to_string(Type) ++ ",...]"; t_form_to_string({type, _L, nonempty_string, []}) -> "nonempty_string()"; t_form_to_string({type, _L, product, Elements}) -> - "<" ++ string:join(t_form_to_string_list(Elements), ",") ++ ">"; + "<" ++ flat_join(t_form_to_string_list(Elements), ",") ++ ">"; t_form_to_string({type, _L, range, [From, To]} = Type) -> case {erl_eval:partial_eval(From), erl_eval:partial_eval(To)} of {{integer, _, FromVal}, {integer, _, ToVal}} -> @@ -5322,7 +5328,7 @@ t_form_to_string({type, _L, range, [From, To]} = Type) -> t_form_to_string({type, _L, record, [{atom, _, Name}]}) -> flat_format("#~tw{}", [Name]); t_form_to_string({type, _L, record, [{atom, _, Name}|Fields]}) -> - FieldString = string:join(t_form_to_string_list(Fields), ","), + FieldString = flat_join(t_form_to_string_list(Fields), ","), flat_format("#~tw{~ts}", [Name, FieldString]); t_form_to_string({type, _L, field_type, [{atom, _, Name}, Type]}) -> flat_format("~tw::~ts", [Name, t_form_to_string(Type)]); @@ -5330,9 +5336,9 @@ t_form_to_string({type, _L, term, []}) -> "term()"; t_form_to_string({type, _L, timeout, []}) -> "timeout()"; t_form_to_string({type, _L, tuple, any}) -> "tuple()"; t_form_to_string({type, _L, tuple, Args}) -> - "{" ++ string:join(t_form_to_string_list(Args), ",") ++ "}"; + "{" ++ flat_join(t_form_to_string_list(Args), ",") ++ "}"; t_form_to_string({type, _L, union, Args}) -> - string:join(t_form_to_string_list(Args), " | "); + flat_join(t_form_to_string_list(Args), " | "); t_form_to_string({type, _L, Name, []} = T) -> try M = mod, @@ -5350,7 +5356,7 @@ t_form_to_string({type, _L, Name, []} = T) -> end; t_form_to_string({user_type, _L, Name, List}) -> flat_format("~tw(~ts)", - [Name, string:join(t_form_to_string_list(List), ",")]); + [Name, flat_join(t_form_to_string_list(List), ",")]); t_form_to_string({type, L, Name, List}) -> %% Compatibility: modules compiled before Erlang/OTP 18.0. t_form_to_string({user_type, L, Name, List}). @@ -5611,7 +5617,7 @@ set_to_string(Set) -> true -> io_lib:write_string(atom_to_list(X), $'); % stupid emacs ' false -> flat_format("~tw", [X]) end || X <- set_to_list(Set)], - string:join(L, " | "). + flat_join(L, " | "). set_min([H|_]) -> H. @@ -5621,6 +5627,9 @@ set_max(Set) -> flat_format(F, S) -> lists:flatten(io_lib:format(F, S)). +flat_join(List, Sep) -> + lists:flatten(lists:join(Sep, List)). + %%============================================================================= %% %% Utilities for the binary type @@ -5690,173 +5699,3 @@ family(L) -> var_table__new() -> maps:new(). - -%%============================================================================= -%% Consistency-testing function(s) below -%%============================================================================= - --ifdef(DO_ERL_TYPES_TEST). - -test() -> - Atom1 = t_atom(), - Atom2 = t_atom(foo), - Atom3 = t_atom(bar), - true = t_is_atom(Atom2), - - True = t_atom(true), - False = t_atom(false), - Bool = t_boolean(), - true = t_is_boolean(True), - true = t_is_boolean(Bool), - false = t_is_boolean(Atom1), - - Binary = t_binary(), - true = t_is_binary(Binary), - - Bitstr = t_bitstr(), - true = t_is_bitstr(Bitstr), - - Bitstr1 = t_bitstr(7, 3), - true = t_is_bitstr(Bitstr1), - false = t_is_binary(Bitstr1), - - Bitstr2 = t_bitstr(16, 8), - true = t_is_bitstr(Bitstr2), - true = t_is_binary(Bitstr2), - - ?bitstr(8, 16) = t_subtract(t_bitstr(4, 12), t_bitstr(8, 12)), - ?bitstr(8, 16) = t_subtract(t_bitstr(4, 12), t_bitstr(8, 12)), - - Int1 = t_integer(), - Int2 = t_integer(1), - Int3 = t_integer(16#ffffffff), - true = t_is_integer(Int2), - true = t_is_byte(Int2), - false = t_is_byte(Int3), - false = t_is_byte(t_from_range(-1, 1)), - true = t_is_byte(t_from_range(1, ?MAX_BYTE)), - - Tuple1 = t_tuple(), - Tuple2 = t_tuple(3), - Tuple3 = t_tuple([Atom1, Int1]), - Tuple4 = t_tuple([Tuple1, Tuple2]), - Tuple5 = t_tuple([Tuple3, Tuple4]), - Tuple6 = t_limit(Tuple5, 2), - Tuple7 = t_limit(Tuple5, 3), - true = t_is_tuple(Tuple1), - - Port = t_port(), - Pid = t_pid(), - Ref = t_reference(), - Identifier = t_identifier(), - false = t_is_reference(Port), - true = t_is_identifier(Port), - - Function1 = t_fun(), - Function2 = t_fun(Pid), - Function3 = t_fun([], Pid), - Function4 = t_fun([Port, Pid], Pid), - Function5 = t_fun([Pid, Atom1], Int2), - true = t_is_fun(Function3), - - List1 = t_list(), - List2 = t_list(t_boolean()), - List3 = t_cons(t_boolean(), List2), - List4 = t_cons(t_boolean(), t_atom()), - List5 = t_cons(t_boolean(), t_nil()), - List6 = t_cons_tl(List5), - List7 = t_sup(List4, List5), - List8 = t_inf(List7, t_list()), - List9 = t_cons(), - List10 = t_cons_tl(List9), - true = t_is_boolean(t_cons_hd(List5)), - true = t_is_list(List5), - false = t_is_list(List4), - - Product1 = t_product([Atom1, Atom2]), - Product2 = t_product([Atom3, Atom1]), - Product3 = t_product([Atom3, Atom2]), - - Union1 = t_sup(Atom2, Atom3), - Union2 = t_sup(Tuple2, Tuple3), - Union3 = t_sup(Int2, Atom3), - Union4 = t_sup(Port, Pid), - Union5 = t_sup(Union4, Int1), - Union6 = t_sup(Function1, Function2), - Union7 = t_sup(Function4, Function5), - Union8 = t_sup(True, False), - true = t_is_boolean(Union8), - Union9 = t_sup(Int2, t_integer(2)), - true = t_is_byte(Union9), - Union10 = t_sup(t_tuple([t_atom(true), ?any]), - t_tuple([t_atom(false), ?any])), - - ?any = t_sup(Product3, Function5), - - Atom3 = t_inf(Union3, Atom1), - Union2 = t_inf(Union2, Tuple1), - Int2 = t_inf(Int1, Union3), - Union4 = t_inf(Union4, Identifier), - Port = t_inf(Union5, Port), - Function4 = t_inf(Union7, Function4), - ?none = t_inf(Product2, Atom1), - Product3 = t_inf(Product1, Product2), - Function5 = t_inf(Union7, Function5), - true = t_is_byte(t_inf(Union9, t_number())), - true = t_is_char(t_inf(Union9, t_number())), - - io:format("3? ~p ~n", [?int_set([3])]), - - RecDict = dict:store({foo, 2}, [bar, baz], dict:new()), - Record1 = t_from_term({foo, [1,2], {1,2,3}}), - - Types = [ - Atom1, - Atom2, - Atom3, - Binary, - Int1, - Int2, - Tuple1, - Tuple2, - Tuple3, - Tuple4, - Tuple5, - Tuple6, - Tuple7, - Ref, - Port, - Pid, - Identifier, - List1, - List2, - List3, - List4, - List5, - List6, - List7, - List8, - List9, - List10, - Function1, - Function2, - Function3, - Function4, - Function5, - Product1, - Product2, - Record1, - Union1, - Union2, - Union3, - Union4, - Union5, - Union6, - Union7, - Union8, - Union10, - t_inf(Union10, t_tuple([t_atom(true), t_integer()])) - ], - io:format("~p\n", [[t_to_string(X, RecDict) || X <- Types]]). - --endif. |