diff options
Diffstat (limited to 'lib')
43 files changed, 3746 insertions, 612 deletions
diff --git a/lib/compiler/src/beam_ssa_pre_codegen.erl b/lib/compiler/src/beam_ssa_pre_codegen.erl index bad43a9c4e..bf99e8fc26 100644 --- a/lib/compiler/src/beam_ssa_pre_codegen.erl +++ b/lib/compiler/src/beam_ssa_pre_codegen.erl @@ -342,21 +342,22 @@ make_save_point_dict_1([], Ctx, I, Acc) -> [{Ctx,I}|Acc]. bs_restores([{L,#b_blk{is=Is,last=Last}}|Bs], CtxChain, D0, Rs0) -> - FPos = case D0 of - #{L:=Pos0} -> Pos0; - #{} -> #{} - end, - {SPos,Rs} = bs_restores_is(Is, CtxChain, FPos, Rs0), - D = bs_update_successors(Last, SPos, FPos, D0), + InPos = maps:get(L, D0, #{}), + {SuccPos, FailPos, Rs} = bs_restores_is(Is, CtxChain, InPos, InPos, Rs0), + + D = bs_update_successors(Last, SuccPos, FailPos, D0), bs_restores(Bs, CtxChain, D, Rs); bs_restores([], _, _, Rs) -> Rs. bs_update_successors(#b_br{succ=Succ,fail=Fail}, SPos, FPos, D) -> join_positions([{Succ,SPos},{Fail,FPos}], D); -bs_update_successors(#b_switch{fail=Fail,list=List}, SPos, _FPos, D) -> +bs_update_successors(#b_switch{fail=Fail,list=List}, SPos, FPos, D) -> + SPos = FPos, %Assertion. Update = [{L,SPos} || {_,L} <- List] ++ [{Fail,SPos}], join_positions(Update, D); -bs_update_successors(#b_ret{}, _, _, D) -> D. +bs_update_successors(#b_ret{}, SPos, FPos, D) -> + SPos = FPos, %Assertion. + D. join_positions([{L,MapPos0}|T], D) -> case D of @@ -382,75 +383,91 @@ join_positions_1(MapPos0, MapPos1) -> end, MapPos1), maps:merge(MapPos0, MapPos2). +%% +%% Updates the restore and position maps according to the given instructions. +%% +%% Note that positions may be updated even when a match fails; if a match +%% requires a restore, the position at the fail block will be the position +%% we've *restored to* and not the one we entered the current block with. +%% + bs_restores_is([#b_set{op=bs_start_match,dst=Start}|Is], - CtxChain, PosMap0, Rs) -> - PosMap = PosMap0#{Start=>Start}, - bs_restores_is(Is, CtxChain, PosMap, Rs); + CtxChain, SPos0, FPos, Rs) -> + %% We only allow one match per block. + SPos0 = FPos, %Assertion. + SPos = SPos0#{Start=>Start}, + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); bs_restores_is([#b_set{op=bs_match,dst=NewPos,args=Args}=I|Is], - CtxChain, PosMap0, Rs0) -> + CtxChain, SPos0, FPos0, Rs0) -> + SPos0 = FPos0, %Assertion. Start = bs_subst_ctx(NewPos, CtxChain), [_,FromPos|_] = Args, - case PosMap0 of + case SPos0 of #{Start:=FromPos} -> %% Same position, no restore needed. - PosMap = case bs_match_type(I) of + SPos = case bs_match_type(I) of plain -> %% Update position to new position. - PosMap0#{Start:=NewPos}; + SPos0#{Start:=NewPos}; _ -> %% Position will not change (test_unit %% instruction or no instruction at %% all). - PosMap0#{Start:=FromPos} + SPos0#{Start:=FromPos} end, - bs_restores_is(Is, CtxChain, PosMap, Rs0); + bs_restores_is(Is, CtxChain, SPos, FPos0, Rs0); #{Start:=_} -> %% Different positions, might need a restore instruction. case bs_match_type(I) of none -> - %% The tail test will be optimized away. - %% No need to do a restore. - PosMap = PosMap0#{Start:=FromPos}, - bs_restores_is(Is, CtxChain, PosMap, Rs0); + %% This is a tail test that will be optimized away. + %% There's no need to do a restore, and all + %% positions are unchanged. + bs_restores_is(Is, CtxChain, SPos0, FPos0, Rs0); test_unit -> %% This match instruction will be replaced by %% a test_unit instruction. We will need a %% restore. The new position will be the position %% restored to (NOT NewPos). - PosMap = PosMap0#{Start:=FromPos}, + SPos = SPos0#{Start:=FromPos}, + FPos = FPos0#{Start:=FromPos}, Rs = Rs0#{NewPos=>{Start,FromPos}}, - bs_restores_is(Is, CtxChain, PosMap, Rs); + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); plain -> %% Match or skip. Position will be changed. - PosMap = PosMap0#{Start:=NewPos}, + SPos = SPos0#{Start:=NewPos}, + FPos = FPos0#{Start:=FromPos}, Rs = Rs0#{NewPos=>{Start,FromPos}}, - bs_restores_is(Is, CtxChain, PosMap, Rs) + bs_restores_is(Is, CtxChain, SPos, FPos, Rs) end end; bs_restores_is([#b_set{op=bs_extract,args=[FromPos|_]}|Is], - CtxChain, PosMap, Rs) -> + CtxChain, SPos, FPos, Rs) -> Start = bs_subst_ctx(FromPos, CtxChain), - #{Start:=FromPos} = PosMap, %Assertion. - bs_restores_is(Is, CtxChain, PosMap, Rs); + #{Start:=FromPos} = SPos, %Assertion. + #{Start:=FromPos} = FPos, %Assertion. + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); bs_restores_is([#b_set{op=call,dst=Dst,args=Args}|Is], - CtxChain, PosMap0, Rs0) -> - {Rs,PosMap1} = bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0), - PosMap = bs_invalidate_pos(Args, PosMap1, CtxChain), - bs_restores_is(Is, CtxChain, PosMap, Rs); -bs_restores_is([#b_set{op=landingpad}|Is], CtxChain, PosMap0, Rs) -> + CtxChain, SPos0, FPos0, Rs0) -> + {Rs, SPos1, FPos1} = bs_restore_args(Args, SPos0, FPos0, CtxChain, Dst, Rs0), + {SPos, FPos} = bs_invalidate_pos(Args, SPos1, FPos1, CtxChain), + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); +bs_restores_is([#b_set{op=landingpad}|Is], CtxChain, SPos0, FPos0, Rs) -> %% We can land here from any point, so all positions are invalid. - PosMap = maps:map(fun(_Start,_Pos) -> unknown end, PosMap0), - bs_restores_is(Is, CtxChain, PosMap, Rs); + Invalidate = fun(_Start,_Pos) -> unknown end, + SPos = maps:map(Invalidate, SPos0), + FPos = maps:map(Invalidate, FPos0), + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); bs_restores_is([#b_set{op=Op,dst=Dst,args=Args}|Is], - CtxChain, PosMap0, Rs0) + CtxChain, SPos0, FPos0, Rs0) when Op =:= bs_test_tail; Op =:= bs_get_tail -> - {Rs,PosMap} = bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0), - bs_restores_is(Is, CtxChain, PosMap, Rs); -bs_restores_is([_|Is], CtxChain, PosMap, Rs) -> - bs_restores_is(Is, CtxChain, PosMap, Rs); -bs_restores_is([], _CtxChain, PosMap, Rs) -> - {PosMap,Rs}. + {Rs, SPos, FPos} = bs_restore_args(Args, SPos0, FPos0, CtxChain, Dst, Rs0), + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); +bs_restores_is([_|Is], CtxChain, SPos, FPos, Rs) -> + bs_restores_is(Is, CtxChain, SPos, FPos, Rs); +bs_restores_is([], _CtxChain, SPos, FPos, Rs) -> + {SPos, FPos, Rs}. bs_match_type(#b_set{args=[#b_literal{val=skip},_Ctx, #b_literal{val=binary},_Flags, @@ -464,40 +481,42 @@ bs_match_type(_) -> %% Call instructions leave the match position in an undefined state, %% requiring us to invalidate each affected argument. -bs_invalidate_pos([#b_var{}=Arg|Args], PosMap0, CtxChain) -> +bs_invalidate_pos([#b_var{}=Arg|Args], SPos0, FPos0, CtxChain) -> Start = bs_subst_ctx(Arg, CtxChain), - case PosMap0 of + case SPos0 of #{Start:=_} -> - PosMap = PosMap0#{Start:=unknown}, - bs_invalidate_pos(Args, PosMap, CtxChain); + SPos = SPos0#{Start:=unknown}, + FPos = FPos0#{Start:=unknown}, + bs_invalidate_pos(Args, SPos, FPos, CtxChain); #{} -> %% Not a match context. - bs_invalidate_pos(Args, PosMap0, CtxChain) + bs_invalidate_pos(Args, SPos0, FPos0, CtxChain) end; -bs_invalidate_pos([_|Args], PosMap, CtxChain) -> - bs_invalidate_pos(Args, PosMap, CtxChain); -bs_invalidate_pos([], PosMap, _CtxChain) -> - PosMap. +bs_invalidate_pos([_|Args], SPos, FPos, CtxChain) -> + bs_invalidate_pos(Args, SPos, FPos, CtxChain); +bs_invalidate_pos([], SPos, FPos, _CtxChain) -> + {SPos, FPos}. -bs_restore_args([#b_var{}=Arg|Args], PosMap0, CtxChain, Dst, Rs0) -> +bs_restore_args([#b_var{}=Arg|Args], SPos0, FPos0, CtxChain, Dst, Rs0) -> Start = bs_subst_ctx(Arg, CtxChain), - case PosMap0 of + case SPos0 of #{Start:=Arg} -> %% Same position, no restore needed. - bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0); + bs_restore_args(Args, SPos0, FPos0, CtxChain, Dst, Rs0); #{Start:=_} -> %% Different positions, need a restore instruction. - PosMap = PosMap0#{Start:=Arg}, + SPos = SPos0#{Start:=Arg}, + FPos = FPos0#{Start:=Arg}, Rs = Rs0#{Dst=>{Start,Arg}}, - bs_restore_args(Args, PosMap, CtxChain, Dst, Rs); + bs_restore_args(Args, SPos, FPos, CtxChain, Dst, Rs); #{} -> %% Not a match context. - bs_restore_args(Args, PosMap0, CtxChain, Dst, Rs0) + bs_restore_args(Args, SPos0, FPos0, CtxChain, Dst, Rs0) end; -bs_restore_args([_|Args], PosMap, CtxChain, Dst, Rs) -> - bs_restore_args(Args, PosMap, CtxChain, Dst, Rs); -bs_restore_args([], PosMap, _CtxChain, _Dst, Rs) -> - {Rs,PosMap}. +bs_restore_args([_|Args], SPos, FPos, CtxChain, Dst, Rs) -> + bs_restore_args(Args, SPos, FPos, CtxChain, Dst, Rs); +bs_restore_args([], SPos, FPos, _CtxChain, _Dst, Rs) -> + {Rs,SPos,FPos}. %% Insert all bs_save and bs_restore instructions. diff --git a/lib/compiler/src/beam_validator.erl b/lib/compiler/src/beam_validator.erl index efd2be94cb..09a5a6c104 100644 --- a/lib/compiler/src/beam_validator.erl +++ b/lib/compiler/src/beam_validator.erl @@ -1604,8 +1604,13 @@ infer_types_1(#value{op={bif,'=:='},args=[LHS,RHS]}) -> end; infer_types_1(#value{op={bif,element},args=[{integer,Index}=Key,Tuple]}) -> fun(Val, S) -> - Type = get_term_type(Val, S), - update_type(fun meet/2,{tuple,[Index],#{ Key => Type }}, Tuple, S) + case is_value_alive(Tuple, S) of + true -> + Type = {tuple,[Index], #{ Key => get_term_type(Val, S) }}, + update_type(fun meet/2, Type, Tuple, S); + false -> + S + end end; infer_types_1(#value{op={bif,is_atom},args=[Src]}) -> infer_type_test_bif({atom,[]}, Src); @@ -1629,7 +1634,10 @@ infer_types_1(#value{op={bif,is_tuple},args=[Src]}) -> infer_type_test_bif({tuple,[0],#{}}, Src); infer_types_1(#value{op={bif,tuple_size}, args=[Tuple]}) -> fun({integer,Arity}, S) -> - update_type(fun meet/2, {tuple,Arity,#{}}, Tuple, S); + case is_value_alive(Tuple, S) of + true -> update_type(fun meet/2, {tuple,Arity,#{}}, Tuple, S); + false -> S + end; (_, S) -> S end; infer_types_1(_) -> @@ -1637,7 +1645,10 @@ infer_types_1(_) -> infer_type_test_bif(Type, Src) -> fun({atom,true}, S) -> - update_type(fun meet/2, Type, Src, S); + case is_value_alive(Src, S) of + true -> update_type(fun meet/2, Type, Src, S); + false -> S + end; (_, S) -> S end. @@ -2274,6 +2285,9 @@ get_raw_type(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) -> get_raw_type(Src, #vst{}) -> get_literal_type(Src). +is_value_alive(#value_ref{}=Ref, #vst{current=#st{vs=Vs}}) -> + is_map_key(Ref, Vs). + get_literal_type(nil=T) -> T; get_literal_type({atom,A}=T) when is_atom(A) -> T; get_literal_type({float,F}=T) when is_float(F) -> T; diff --git a/lib/compiler/test/beam_validator_SUITE.erl b/lib/compiler/test/beam_validator_SUITE.erl index de5a3c2873..6b1438abdd 100644 --- a/lib/compiler/test/beam_validator_SUITE.erl +++ b/lib/compiler/test/beam_validator_SUITE.erl @@ -35,7 +35,7 @@ map_field_lists/1,cover_bin_opt/1, val_dsetel/1,bad_tuples/1,bad_try_catch_nesting/1, receive_stacked/1,aliased_types/1,type_conflict/1, - infer_on_eq/1]). + infer_on_eq/1,infer_dead_value/1]). -include_lib("common_test/include/ct.hrl"). @@ -65,7 +65,7 @@ groups() -> map_field_lists,cover_bin_opt,val_dsetel, bad_tuples,bad_try_catch_nesting, receive_stacked,aliased_types,type_conflict, - infer_on_eq]}]. + infer_on_eq,infer_dead_value]}]. init_per_suite(Config) -> test_lib:recompile(?MODULE), @@ -679,6 +679,27 @@ infer_on_eq_4(T) -> true = erlang:tuple_size(T) =:= 1, {ok, erlang:element(1, T)}. +%% ERIERL-348; types were inferred for dead values, causing validation to fail. + +infer_dead_value(Config) when is_list(Config) -> + a = idv_1({a, b, c, d, e, f, g}, {0, 0, 0, 0, 0, 0, 0}), + b = idv_1({a, b, c, d, 0, 0, 0}, {a, b, c, d, 0, 0, 0}), + c = idv_1({0, 0, 0, 0, 0, f, g}, {0, 0, 0, 0, 0, f, g}), + error = idv_1(gurka, gaffel), + ok. + +idv_1({_A, _B, _C, _D, _E, _F, _G}, + {0, 0, 0, 0, 0, 0, 0}) -> + a; +idv_1({A, B, C, D,_E, _F, _G}=_Tuple1, + {A, B, C, D, 0, 0, 0}=_Tuple2) -> + b; +idv_1({_A, _B, _C, _D, _E, F, G}, + {0, 0, 0, 0, 0, F, G}) -> + c; +idv_1(_A, _B) -> + error. + %%%------------------------------------------------------------------------- transform_remove(Remove, Module) -> diff --git a/lib/compiler/test/bs_match_SUITE.erl b/lib/compiler/test/bs_match_SUITE.erl index 41e4918b1e..d97f49c56e 100644 --- a/lib/compiler/test/bs_match_SUITE.erl +++ b/lib/compiler/test/bs_match_SUITE.erl @@ -1891,15 +1891,37 @@ expression_before_match_1(R) -> %% Make sure that context positions are updated on calls. restore_on_call(Config) when is_list(Config) -> - ok = restore_on_call_1(<<0, 1, 2>>). + ok = restore_on_call_plain(<<0, 1, 2>>), + <<"x">> = restore_on_call_match(<<0, "x">>), + ok. -restore_on_call_1(<<0, Rest/binary>>) -> - <<2>> = restore_on_call_2(Rest), - <<2>> = restore_on_call_2(Rest), %% {badmatch, <<>>} on missing restore. +restore_on_call_plain(<<0, Rest/binary>>) -> + <<2>> = restore_on_call_plain_1(Rest), + %% {badmatch, <<>>} on missing restore. + <<2>> = restore_on_call_plain_1(Rest), ok. -restore_on_call_2(<<1, Rest/binary>>) -> Rest; -restore_on_call_2(Other) -> Other. +restore_on_call_plain_1(<<1, Rest/binary>>) -> Rest; +restore_on_call_plain_1(Other) -> Other. + +%% Calls a function that moves the match context passed to it, and then matches +%% on its result to confuse the reposition algorithm's success/fail logic. +restore_on_call_match(<<0, Bin/binary>>) -> + case skip_until_zero(Bin) of + {skipped, Rest} -> + Rest; + not_found -> + %% The match context did not get repositioned before the + %% bs_get_tail instruction here. + Bin + end. + +skip_until_zero(<<0,Rest/binary>>) -> + {skipped, Rest}; +skip_until_zero(<<_C,Rest/binary>>) -> + skip_until_zero(Rest); +skip_until_zero(_) -> + not_found. %% 'catch' must invalidate positions. restore_after_catch(Config) when is_list(Config) -> @@ -1983,5 +2005,4 @@ do_matching_meets_apply(_Bin, {Handler, State}) -> %% Another case of the above. Handler:abs(State). - id(I) -> I. diff --git a/lib/dialyzer/src/dialyzer.erl b/lib/dialyzer/src/dialyzer.erl index 185c8c9ae6..a168b3c8c5 100644 --- a/lib/dialyzer/src/dialyzer.erl +++ b/lib/dialyzer/src/dialyzer.erl @@ -320,9 +320,12 @@ message_to_string({call_to_missing, [M, F, A]}) -> message_to_string({exact_eq, [Type1, Op, Type2]}) -> io_lib:format("The test ~ts ~s ~ts can never evaluate to 'true'\n", [Type1, Op, Type2]); -message_to_string({fun_app_args, [Args, Type]}) -> +message_to_string({fun_app_args, [ArgNs, Args, Type]}) -> + PositionString = form_position_string(ArgNs), io_lib:format("Fun application with arguments ~ts will fail" - " since the function has type ~ts\n", [Args, Type]); + " since the function has type ~ts," + " which differs in the ~s argument\n", + [Args, Type, PositionString]); message_to_string({fun_app_no_fun, [Op, Type, Arity]}) -> io_lib:format("Fun application will fail since ~ts :: ~ts" " is not a function of arity ~w\n", [Op, Type, Arity]); diff --git a/lib/dialyzer/src/dialyzer_dataflow.erl b/lib/dialyzer/src/dialyzer_dataflow.erl index 45b4abb253..f7aa167f5c 100644 --- a/lib/dialyzer/src/dialyzer_dataflow.erl +++ b/lib/dialyzer/src/dialyzer_dataflow.erl @@ -405,8 +405,13 @@ handle_apply(Tree, Map, State) -> t_fun_args(OpType1, 'universe')), case any_none(NewArgs) of true -> + EnumNewArgs = lists:zip(lists:seq(1, length(NewArgs)), + NewArgs), + ArgNs = [Arg || + {Arg, Type} <- EnumNewArgs, t_is_none(Type)], Msg = {fun_app_args, - [format_args(Args, ArgTypes, State), + [ArgNs, + format_args(Args, ArgTypes, State), format_type(OpType, State)]}, State3 = state__add_warning(State2, ?WARN_FAILING_CALL, Tree, Msg), diff --git a/lib/dialyzer/test/small_SUITE_data/results/fun_app_args b/lib/dialyzer/test/small_SUITE_data/results/fun_app_args new file mode 100644 index 0000000000..ac153a6fb2 --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/results/fun_app_args @@ -0,0 +1,3 @@ + +fun_app_args.erl:12: Fun application with arguments ('b',[]) will fail since the function has type 'c' | fun(('a',[]) -> any()), which differs in the 1st argument +fun_app_args.erl:12: The created fun has no local return diff --git a/lib/dialyzer/test/small_SUITE_data/src/fun_app_args.erl b/lib/dialyzer/test/small_SUITE_data/src/fun_app_args.erl new file mode 100644 index 0000000000..b4409bc550 --- /dev/null +++ b/lib/dialyzer/test/small_SUITE_data/src/fun_app_args.erl @@ -0,0 +1,12 @@ +-module(fun_app_args). + +-export([t/1]). + +-type ft() :: fun((a, []) -> any()). + +-record(r, { + h = c :: c | ft() +}). + +t(#r{h = H}) -> + fun(_) -> (H)(b, []) end. diff --git a/lib/eldap/src/eldap.erl b/lib/eldap/src/eldap.erl index 6497922852..9b7e254dfe 100644 --- a/lib/eldap/src/eldap.erl +++ b/lib/eldap/src/eldap.erl @@ -957,20 +957,20 @@ do_modify_dn_0(Data, Entry, NewRDN, DelOldRDN, NewSup, Controls) -> do_unbind(Data) -> Req = "", log2(Data, "unbind request = ~p (has no reply)~n", [Req]), - case Data#eldap.using_tls of - true -> - send_request(Data#eldap.fd, Data, Data#eldap.id, {unbindRequest, Req}), - ssl:close(Data#eldap.fd); - false -> - OldTrapExit = process_flag(trap_exit, true), - catch send_request(Data#eldap.fd, Data, Data#eldap.id, {unbindRequest, Req}), - catch gen_tcp:close(Data#eldap.fd), - receive - {'EXIT', _From, _Reason} -> ok - after 0 -> ok - end, - process_flag(trap_exit, OldTrapExit) - end, + _ = case Data#eldap.using_tls of + true -> + send_request(Data#eldap.fd, Data, Data#eldap.id, {unbindRequest, Req}), + ssl:close(Data#eldap.fd); + false -> + OldTrapExit = process_flag(trap_exit, true), + catch send_request(Data#eldap.fd, Data, Data#eldap.id, {unbindRequest, Req}), + catch gen_tcp:close(Data#eldap.fd), + receive + {'EXIT', _From, _Reason} -> ok + after 0 -> ok + end, + process_flag(trap_exit, OldTrapExit) + end, {no_reply, Data#eldap{binddn = (#eldap{})#eldap.binddn, passwd = (#eldap{})#eldap.passwd, fd = (#eldap{})#eldap.fd, @@ -1130,7 +1130,7 @@ ldap_closed_p(Data, Emsg) when Data#eldap.using_tls == true -> %% Check if the SSL socket seems to be alive or not case catch ssl:sockname(Data#eldap.fd) of {error, _} -> - ssl:close(Data#eldap.fd), + _ = ssl:close(Data#eldap.fd), {error, ldap_closed}; {ok, _} -> {error, Emsg}; diff --git a/lib/erl_interface/include/ei.h b/lib/erl_interface/include/ei.h index 591367dc95..a860df3f77 100644 --- a/lib/erl_interface/include/ei.h +++ b/lib/erl_interface/include/ei.h @@ -287,7 +287,7 @@ typedef struct { struct { char* func; int func_allocated; - } export; + } exprt; } u; } erlang_fun; diff --git a/lib/erl_interface/src/decode/decode_fun.c b/lib/erl_interface/src/decode/decode_fun.c index 32a950433e..3a7a2b01c1 100644 --- a/lib/erl_interface/src/decode/decode_fun.c +++ b/lib/erl_interface/src/decode/decode_fun.c @@ -153,8 +153,8 @@ int ei_decode_fun(const char *buf, int *index, erlang_fun *p) /* try use module buffer for function name */ used = strlen(p->module) + 1; p_func = p->module + used; - p->u.export.func = p_func; - p->u.export.func_allocated = 0; + p->u.exprt.func = p_func; + p->u.exprt.func_allocated = 0; } else { used = 0; @@ -165,8 +165,8 @@ int ei_decode_fun(const char *buf, int *index, erlang_fun *p) if (!used) return -1; p_func = malloc(MAXATOMLEN_UTF8); - p->u.export.func = p_func; - p->u.export.func_allocated = 1; + p->u.exprt.func = p_func; + p->u.exprt.func_allocated = 1; used = 0; } if (ei_decode_long(s, &ix, p_arity) < 0) @@ -186,8 +186,8 @@ void free_fun(erlang_fun* f) ei_free(f->u.closure.free_vars); break; case EI_FUN_EXPORT: - if (f->u.export.func_allocated) - ei_free(f->u.export.func); + if (f->u.exprt.func_allocated) + ei_free(f->u.exprt.func); break; } } diff --git a/lib/erl_interface/src/encode/encode_fun.c b/lib/erl_interface/src/encode/encode_fun.c index 38ba7c5b30..e29424f9f4 100644 --- a/lib/erl_interface/src/encode/encode_fun.c +++ b/lib/erl_interface/src/encode/encode_fun.c @@ -87,7 +87,7 @@ int ei_encode_fun(char *buf, int *index, const erlang_fun *p) ix++; if (ei_encode_atom_as(buf, &ix, p->module, ERLANG_UTF8, ERLANG_UTF8) < 0) return -1; - if (ei_encode_atom_as(buf, &ix, p->u.export.func, ERLANG_UTF8, ERLANG_UTF8) < 0) + if (ei_encode_atom_as(buf, &ix, p->u.exprt.func, ERLANG_UTF8, ERLANG_UTF8) < 0) return -1; if (ei_encode_long(buf, &ix, p->arity) < 0) return -1; diff --git a/lib/kernel/doc/src/gen_tcp.xml b/lib/kernel/doc/src/gen_tcp.xml index fc16473393..f8b41d24e2 100644 --- a/lib/kernel/doc/src/gen_tcp.xml +++ b/lib/kernel/doc/src/gen_tcp.xml @@ -259,6 +259,12 @@ do_recv(Sock, Bs) -> <p>The optional <c><anno>Timeout</anno></c> parameter specifies a time-out in milliseconds. Defaults to <c>infinity</c>.</p> <note> + <p>Keep in mind that if the underlying OS <c>connect()</c> call returns + a timeout, <c>gen_tcp:connect</c> will also return a timeout + (i.e. <c>{error, etimedout}</c>), even if a larger <c>Timeout</c> was + specified.</p> + </note> + <note> <p>The default values for options specified to <c>connect</c> can be affected by the Kernel configuration parameter <c>inet_default_connect_options</c>. For details, see diff --git a/lib/kernel/doc/src/inet.xml b/lib/kernel/doc/src/inet.xml index 709ba8e8fd..d4678ca5db 100644 --- a/lib/kernel/doc/src/inet.xml +++ b/lib/kernel/doc/src/inet.xml @@ -294,6 +294,9 @@ fe80::204:acff:fe17:bf38 <datatype> <name name="socket_protocol"/> </datatype> + <datatype> + <name name="stat_option"/> + </datatype> </datatypes> <funcs> diff --git a/lib/kernel/src/erl_distribution.erl b/lib/kernel/src/erl_distribution.erl index 0bec78e938..cdb2d2f1f6 100644 --- a/lib/kernel/src/erl_distribution.erl +++ b/lib/kernel/src/erl_distribution.erl @@ -21,6 +21,8 @@ -behaviour(supervisor). +-include_lib("kernel/include/logger.hrl"). + -export([start_link/0,start_link/2,init/1,start/1,stop/0]). -define(DBG,erlang:display([?MODULE,?LINE])). @@ -83,6 +85,10 @@ do_start_link([{Arg,Flag}|T]) -> case init:get_argument(Arg) of {ok,[[Name]]} -> start_link([list_to_atom(Name),Flag|ticktime()], true); + {ok,[[Name]|_Rest]} -> + ?LOG_WARNING("Multiple -~p given to erl, using the first, ~p", + [Arg, Name]), + start_link([list_to_atom(Name),Flag|ticktime()], true); _ -> do_start_link(T) end; diff --git a/lib/kernel/test/erl_distribution_SUITE.erl b/lib/kernel/test/erl_distribution_SUITE.erl index 8dd4ef1987..c3a022df0a 100644 --- a/lib/kernel/test/erl_distribution_SUITE.erl +++ b/lib/kernel/test/erl_distribution_SUITE.erl @@ -205,6 +205,9 @@ nodenames(Config) when is_list(Config) -> legal("a-1@b"), legal("a_1@b"), + %% Test that giving two -sname works as it should + test_node("a_1@b", false, long_or_short() ++ "a_0@b"), + illegal("cdé@a"), illegal("te欢st@a"). @@ -258,8 +261,11 @@ illegal(Name) -> test_node(Name) -> test_node(Name, false). test_node(Name, Illigal) -> + test_node(Name, Illigal, ""). +test_node(Name, Illigal, ExtraArgs) -> ProgName = ct:get_progname(), - Command = ProgName ++ " -noinput " ++ long_or_short() ++ Name ++ + Command = ProgName ++ " -noinput " ++ ExtraArgs ++ + long_or_short() ++ Name ++ " -eval \"net_adm:ping('" ++ atom_to_list(node()) ++ "')\"" ++ case Illigal of true -> diff --git a/lib/public_key/doc/src/public_key.xml b/lib/public_key/doc/src/public_key.xml index 8db5620686..12bb0b21b0 100644 --- a/lib/public_key/doc/src/public_key.xml +++ b/lib/public_key/doc/src/public_key.xml @@ -286,7 +286,9 @@ entries as ASN.1 DER encoded entities.</fsummary> <desc> <p>Decodes PEM binary data and returns entries as ASN.1 DER encoded entities.</p> - <p>Example <c>{ok, PemBin} = file:read_file("cert.pem").</c></p> + <p>Example <c>{ok, PemBin} = file:read_file("cert.pem"). + PemEntries = public_key:pem_decode(PemBin). + </c></p> </desc> </func> diff --git a/lib/public_key/src/pubkey_cert.erl b/lib/public_key/src/pubkey_cert.erl index 61a1239d26..12c61e158f 100644 --- a/lib/public_key/src/pubkey_cert.erl +++ b/lib/public_key/src/pubkey_cert.erl @@ -1187,6 +1187,8 @@ sign_algorithm(#'ECPrivateKey'{parameters = Parms}, Opts) -> parameters = Parms}. rsa_digest_oid(sha1) -> ?'sha1WithRSAEncryption'; +rsa_digest_oid(sha) -> + ?'sha1WithRSAEncryption'; rsa_digest_oid(sha512) -> ?'sha512WithRSAEncryption'; rsa_digest_oid(sha384) -> @@ -1198,6 +1200,8 @@ rsa_digest_oid(md5) -> ecdsa_digest_oid(sha1) -> ?'ecdsa-with-SHA1'; +ecdsa_digest_oid(sha) -> + ?'ecdsa-with-SHA1'; ecdsa_digest_oid(sha512) -> ?'ecdsa-with-SHA512'; ecdsa_digest_oid(sha384) -> diff --git a/lib/public_key/src/public_key.erl b/lib/public_key/src/public_key.erl index 431c77141c..47266c514c 100644 --- a/lib/public_key/src/public_key.erl +++ b/lib/public_key/src/public_key.erl @@ -112,6 +112,7 @@ -type ssh_file() :: openssh_public_key | rfc4716_public_key | known_hosts | auth_keys. -type digest_type() :: none % None is for backwards compatibility + | sha1 % Backwards compatibility | crypto:rsa_digest_type() | crypto:dss_digest_type() | crypto:ecdsa_digest_type(). diff --git a/lib/ssh/doc/src/notes.xml b/lib/ssh/doc/src/notes.xml index bad5815f40..78990c48f2 100644 --- a/lib/ssh/doc/src/notes.xml +++ b/lib/ssh/doc/src/notes.xml @@ -30,6 +30,28 @@ <file>notes.xml</file> </header> +<section><title>Ssh 4.7.6</title> + + <section><title>Improvements and New Features</title> + <list> + <item> + <p> + When an SSH server receives the very first message on a + new TCP connection, and that message is not the expected + one, the 64 first bytes of the received message are now + dumped in the INFO REPORT that reports the Protocol + Error.</p> + <p> + This facilitates the debugging of who sends the bad + message or of detecting a possible port scanning.</p> + <p> + Own Id: OTP-15772</p> + </item> + </list> + </section> + +</section> + <section><title>Ssh 4.7.5</title> <section><title>Fixed Bugs and Malfunctions</title> diff --git a/lib/ssh/src/ssh_connection_handler.erl b/lib/ssh/src/ssh_connection_handler.erl index 7c87591cf2..8f32966a12 100644 --- a/lib/ssh/src/ssh_connection_handler.erl +++ b/lib/ssh/src/ssh_connection_handler.erl @@ -594,7 +594,7 @@ handle_event(_, socket_control, {hello,_}=StateName, D) -> {stop, {shutdown,{unexpected_getopts_return, Other}}} end; -handle_event(_, {info_line,_Line}, {hello,Role}=StateName, D) -> +handle_event(_, {info_line,Line}, {hello,Role}=StateName, D) -> case Role of client -> %% The server may send info lines to the client before the version_exchange @@ -605,9 +605,9 @@ handle_event(_, {info_line,_Line}, {hello,Role}=StateName, D) -> %% But the client may NOT send them to the server. Openssh answers with cleartext, %% and so do we send_bytes("Protocol mismatch.", D), - ?call_disconnectfun_and_log_cond("Protocol mismatch.", - "Protocol mismatch in version exchange. Client sent info lines.", - StateName, D), + Msg = io_lib:format("Protocol mismatch in version exchange. Client sent info lines.~n~s", + [ssh_dbg:hex_dump(Line, 64)]), + ?call_disconnectfun_and_log_cond("Protocol mismatch.", Msg, StateName, D), {stop, {shutdown,"Protocol mismatch in version exchange. Client sent info lines."}} end; diff --git a/lib/ssh/src/ssh_dbg.erl b/lib/ssh/src/ssh_dbg.erl index 4fe15b24d3..43ac4c0ccf 100644 --- a/lib/ssh/src/ssh_dbg.erl +++ b/lib/ssh/src/ssh_dbg.erl @@ -60,6 +60,7 @@ cbuf_stop_clear/0, cbuf_in/1, cbuf_list/0, + hex_dump/1, hex_dump/2, fmt_cbuf_items/0, fmt_cbuf_item/1 ]). @@ -439,3 +440,75 @@ fmt_value(#circ_buf_entry{module = M, io_lib:format("~p:~p ~p/~p ~p~n~s",[M,L,F,A,Pid,fmt_value(V)]); fmt_value(Value) -> io_lib:format("~p",[Value]). + +%%%================================================================ + +-record(h, {max_bytes = 65536, + bytes_per_line = 16, + address_len = 4 + }). + + +hex_dump(Data) -> hex_dump1(Data, hd_opts([])). + +hex_dump(X, Max) when is_integer(Max) -> + hex_dump(X, [{max_bytes,Max}]); +hex_dump(X, OptList) when is_list(OptList) -> + hex_dump1(X, hd_opts(OptList)). + +hex_dump1(B, Opts) when is_binary(B) -> hex_dump1(binary_to_list(B), Opts); +hex_dump1(L, Opts) when is_list(L), length(L) > Opts#h.max_bytes -> + io_lib:format("~s---- skip ~w bytes----~n", [hex_dump1(lists:sublist(L,Opts#h.max_bytes), Opts), + length(L) - Opts#h.max_bytes + ]); +hex_dump1(L, Opts0) when is_list(L) -> + Opts = Opts0#h{address_len = num_hex_digits(Opts0#h.max_bytes)}, + Result = hex_dump(L, [{0,[],[]}], Opts), + [io_lib:format("~*.s | ~*s | ~s~n" + "~*.c-+-~*c-+-~*c~n", + [Opts#h.address_len, lists:sublist("Address",Opts#h.address_len), + -3*Opts#h.bytes_per_line, lists:sublist("Hexdump",3*Opts#h.bytes_per_line), + "ASCII", + Opts#h.address_len, $-, + 3*Opts#h.bytes_per_line, $-, + Opts#h.bytes_per_line, $- + ]) | + [io_lib:format("~*.16.0b | ~s~*c | ~s~n",[Opts#h.address_len, N*Opts#h.bytes_per_line, + lists:reverse(Hexs), + 3*(Opts#h.bytes_per_line-length(Hexs)), $ , + lists:reverse(Chars)]) + || {N,Hexs,Chars} <- lists:reverse(Result) + ] + ]. + + +hd_opts(L) -> lists:foldl(fun hd_opt/2, #h{}, L). + +hd_opt({max_bytes,M}, O) -> O#h{max_bytes=M}; +hd_opt({bytes_per_line,M}, O) -> O#h{bytes_per_line=M}. + + +num_hex_digits(N) when N<16 -> 1; +num_hex_digits(N) -> trunc(math:ceil(math:log2(N)/4)). + + +hex_dump([L|Cs], Result0, Opts) when is_list(L) -> + Result = hex_dump(L,Result0, Opts), + hex_dump(Cs, Result, Opts); + +hex_dump(Cs, [{N0,_,Chars}|_]=Lines, Opts) when length(Chars) == Opts#h.bytes_per_line -> + hex_dump(Cs, [{N0+1,[],[]}|Lines], Opts); + +hex_dump([C|Cs], [{N,Hexs,Chars}|Lines], Opts) -> + Asc = if + 16#20 =< C,C =< 16#7E -> C; + true -> $. + end, + Hex = io_lib:format("~2.16.0b ", [C]), + hex_dump(Cs, [{N, [Hex|Hexs], [Asc|Chars]} | Lines], Opts); + +hex_dump([], Result, _) -> + Result. + + + diff --git a/lib/ssh/vsn.mk b/lib/ssh/vsn.mk index 2947f82556..837da27ab0 100644 --- a/lib/ssh/vsn.mk +++ b/lib/ssh/vsn.mk @@ -1,4 +1,4 @@ #-*-makefile-*- ; force emacs to enter makefile-mode -SSH_VSN = 4.7.5 +SSH_VSN = 4.7.6 APP_VSN = "ssh-$(SSH_VSN)" diff --git a/lib/ssl/doc/src/ssl.xml b/lib/ssl/doc/src/ssl.xml index 74a0a0a03e..d626748af6 100644 --- a/lib/ssl/doc/src/ssl.xml +++ b/lib/ssl/doc/src/ssl.xml @@ -128,7 +128,7 @@ <name name="hostname"/> </datatype> - <datatype> + <datatype> <name name="ip_address"/> </datatype> @@ -136,14 +136,14 @@ <name name="protocol_version"/> </datatype> - <datatype> + <datatype> <name name="tls_version"/> </datatype> - + <datatype> <name name="dtls_version"/> </datatype> - + <datatype> <name name="tls_legacy_version"/> </datatype> @@ -151,9 +151,8 @@ <datatype> <name name="dtls_legacy_version"/> </datatype> - - - <datatype> + + <datatype> <name name="prf_random"/> </datatype> @@ -218,10 +217,6 @@ </datatype> <datatype> - <name name="eccs"/> - </datatype> - - <datatype> <name name="named_curve"/> </datatype> @@ -253,6 +248,10 @@ <name name="tls_alert"/> </datatype> + <datatype> + <name name="reason"/> + </datatype> + <datatype_title>TLS/DTLS OPTION DESCRIPTIONS - COMMON for SERVER and CLIENT</datatype_title> <datatype> @@ -343,13 +342,6 @@ </datatype> <datatype> - <name name="eccs"/> - <desc><p> Allows to specify the order of preference for named curves - and to restrict their usage when using a cipher suite supporting them.</p> - </desc> - </datatype> - - <datatype> <name name="signature_schemes"/> <desc> <p> @@ -1109,13 +1101,8 @@ fun(srp, Username :: string(), UserState :: term()) -> <funcs> <func> - <name since="OTP 20.3">append_cipher_suites(Deferred, Suites) -> ciphers() </name> + <name name="append_cipher_suites" arity="2" since="OTP 20.3"/> <fsummary></fsummary> - <type> - <v>Deferred = <seealso marker="#type-ciphers">ciphers()</seealso> | - <seealso marker="#type-cipher_filters">cipher_filters()</seealso></v> - <v>Suites = <seealso marker="#type-ciphers">ciphers()</seealso></v> - </type> <desc><p>Make <c>Deferred</c> suites become the least preferred suites, that is put them at the end of the cipher suite list <c>Suites</c> after removing them from <c>Suites</c> if @@ -1126,25 +1113,18 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP R14B">cipher_suites() -></name> - <name since="OTP R14B">cipher_suites(Type) -> [old_cipher_suite()]</name> + <name name="cipher_suites" arity="0" since="OTP R14B"/> + <name name="cipher_suites" arity="1" since="OTP R14B"/> <fsummary>Returns a list of supported cipher suites.</fsummary> - <type> - <v>Type = erlang | openssl | all</v> - </type> <desc> <p>Deprecated in OTP 21, use <seealso marker="#cipher_suites-2">cipher_suites/2</seealso> instead.</p> </desc> </func> <func> - <name since="OTP 20.3">cipher_suites(Supported, Version) -> ciphers()</name> + <name name="cipher_suites" arity="2" since="OTP 20.3"/> <fsummary>Returns a list of all default or all supported cipher suites.</fsummary> - <type> - <v> Supported = default | all | anonymous </v> - <v> Version = <seealso marker="#type-protocol_version">protocol_version() </seealso></v> - </type> <desc><p>Returns all default or all supported (except anonymous), or all anonymous cipher suites for a TLS version</p> @@ -1152,16 +1132,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 19.2">eccs() -></name> - <name since="OTP 19.2">eccs(Version) -> NamedCurves</name> + <name name="eccs" arity="0" since="OTP 19.2"/> + <name name="eccs" arity="1" since="OTP 19.2"/> <fsummary>Returns a list of supported ECCs.</fsummary> - - <type> - <v> Version = <seealso marker="#type-protocol_version">protocol_version() </seealso></v> - <v> NamedCurves = <seealso marker="#type-named_curve">[named_curve()] </seealso></v> - - </type> - <desc><p>Returns a list of supported ECCs. <c>eccs()</c> is equivalent to calling <c>eccs(Protocol)</c> with all supported protocols and then deduplicating the output.</p> @@ -1169,9 +1142,8 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 17.5">clear_pem_cache() -> ok </name> + <name name="clear_pem_cache" arity="0" since="OTP 17.5"/> <fsummary> Clears the pem cache</fsummary> - <desc><p>PEM files, used by ssl API-functions, are cached. The cache is regularly checked to see if any cache entries should be invalidated, however this function provides a way to @@ -1181,19 +1153,10 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP R14B">connect(Socket, Options) -> </name> - <name since="">connect(Socket, Options, Timeout) -> {ok, SslSocket} | {ok, SslSocket, Ext} - | {error, Reason}</name> + <name name="connect" arity="2" since="OTP R14B"/> + <name name="connect" arity="3" clause_i="1" since=""/> <fsummary>Upgrades a <c>gen_tcp</c>, or equivalent, connected socket to an TLS socket.</fsummary> - <type> - <v>Socket = <seealso marker="#type-socket"> socket() </seealso></v> - <v>Options = <seealso marker="#type-tls_client_option"> [tls_client_option()] </seealso></v> - <v>Timeout = timeout()</v> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Ext = <seealso marker="#type-protocol_extensions">protocol_extensions()</seealso></v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc><p>Upgrades a <c>gen_tcp</c>, or equivalent, connected socket to an TLS socket, that is, performs the client-side TLS handshake.</p> @@ -1225,18 +1188,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">connect(Host, Port, Options) -></name> - <name since="">connect(Host, Port, Options, Timeout) -> - {ok, SslSocket}| {ok, SslSocket, Ext} | {error, Reason}</name> + <name since="" name="connect" arity="3" clause_i="2"/> + <name since="" name="connect" arity="4"/> <fsummary>Opens an TLS/DTLS connection to <c>Host</c>, <c>Port</c>.</fsummary> - <type> - <v>Host =<seealso marker="#type-host"> host() </seealso> </v> - <v>Port = <seealso marker="kernel:inet#type-port_number">inet:port_number()</seealso></v> - <v>Options = <seealso marker="#type-tls_client_option"> [tls_client_option()]</seealso></v> - <v>Timeout = timeout()</v> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc><p>Opens an TLS/DTLS connection to <c>Host</c>, <c>Port</c>.</p> <p> When the option <c>verify</c> is set to <c>verify_peer</c> the check @@ -1273,24 +1227,15 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">close(SslSocket) -> ok | {error, Reason}</name> + <name since="" name="close" arity="1" /> <fsummary>Closes an TLS/DTLS connection.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Reason = term()</v> - </type> <desc><p>Closes an TLS/DTLS connection.</p> </desc> </func> <func> - <name since="OTP 18.1">close(SslSocket, How) -> ok | {ok, port()} | {error, Reason}</name> + <name since="OTP 18.1" name="close" arity="2"/> <fsummary>Closes an TLS connection.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>How = timeout() | {NewController::pid(), timeout()} </v> - <v>Reason = term()</v> - </type> <desc><p>Closes or downgrades an TLS connection. In the latter case the transport connection will be handed over to the <c>NewController</c> process after receiving the TLS close alert from the peer. The returned transport socket will have @@ -1299,15 +1244,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">controlling_process(SslSocket, NewOwner) -> - ok | {error, Reason}</name> + <name since="" name="controlling_process" arity="2" /> <fsummary>Assigns a new controlling process to the TLS/DTLS socket.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>NewOwner = pid()</v> - <v>Reason = term()</v> - </type> <desc><p>Assigns a new controlling process to the SSL socket. A controlling process is the owner of an SSL socket, and receives all messages from the socket.</p> @@ -1315,17 +1254,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 18.0">connection_information(SslSocket) -> - {ok, Result} | {error, Reason} </name> + <name since="OTP 18.0" name="connection_information" arity="1"/> <fsummary>Returns all the connection information. </fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Item = protocol | selected_cipher_suite | sni_hostname | ecc | session_id | atom()</v> - <d>Meaningful atoms, not specified above, are the ssl option names.</d> - <v>Result = [{Item::atom(), Value::term()}]</v> - <v>Reason = term()</v> - </type> <desc><p>Returns the most relevant information about the connection, ssl options that are undefined will be filtered out. Note that values that affect the security of the connection will only be returned if explicitly requested by connection_information/2.</p> @@ -1336,34 +1267,23 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 18.0">connection_information(SslSocket, Items) -> - {ok, Result} | {error, Reason} </name> + <name since="OTP 18.0" name="connection_information" arity="2"/> <fsummary>Returns the requested connection information. </fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Items = [Item]</v> - <v>Item = protocol | cipher_suite | sni_hostname | ecc | session_id | client_random - | server_random | master_secret | atom()</v> - <d>Note that client_random, server_random and master_secret are values - that affect the security of connection. Meaningful atoms, not specified above, are the ssl option names.</d> - <v>Result = [{Item::atom(), Value::term()}]</v> - <v>Reason = term()</v> - </type> <desc><p>Returns the requested information items about the connection, if they are defined.</p> + <p>Note that client_random, server_random and master_secret are values + that affect the security of connection. Meaningful atoms, not specified + above, are the ssl option names.</p> + <note><p>If only undefined options are requested the resulting list can be empty.</p></note> </desc> </func> <func> - <name since="OTP 20.3">filter_cipher_suites(Suites, Filters) -> ciphers()</name> + <name since="OTP 20.3" name="filter_cipher_suites" arity="2" /> <fsummary></fsummary> - <type> - <v> Suites = <seealso marker="#type-ciphers"> ciphers() </seealso></v> - <v> Filters = <seealso marker="#type-cipher_filters"> cipher_filters() </seealso></v> - </type> <desc><p>Removes cipher suites if any of the filter functions returns false for any part of the cipher suite. This function also calls default filter functions to make sure the cipher @@ -1373,24 +1293,16 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">format_error(Reason) -> string()</name> + <name since="" name="format_error" arity="1" /> <fsummary>Returns an error string.</fsummary> - <type> - <v>Reason = term()</v> - </type> <desc> <p>Presents the error returned by an SSL function as a printable string.</p> </desc> </func> <func> - <name since="">getopts(SslSocket, OptionNames) -> - {ok, [socketoption()]} | {error, Reason}</name> + <name since="" name="getopts" arity="2" /> <fsummary>Gets the values of the specified options.</fsummary> - <type> - <v>Socket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>OptionNames = [atom()]</v> - </type> <desc> <p>Gets the values of the specified socket options. </p> @@ -1398,16 +1310,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 19.0">getstat(SslSocket) -> - {ok, OptionValues} | {error, inet:posix()}</name> - <name since="OTP 19.0">getstat(SslSocket, OptionNames) -> - {ok, OptionValues} | {error, inet:posix()}</name> + <name since="OTP 19.0" name="getstat" arity="1" /> + <name since="OTP 19.0" name="getstat" arity="2" /> <fsummary>Get one or more statistic options for a socket</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>OptionNames = [atom()]</v> - <v>OptionValues = [{inet:stat_option(), integer()}]</v> - </type> <desc> <p>Gets one or more statistic options for the underlying TCP socket.</p> <p>See inet:getstat/2 for statistic options description.</p> @@ -1415,14 +1320,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 21.0">handshake(HsSocket) -> </name> - <name since="OTP 21.0">handshake(HsSocket, Timeout) -> {ok, SslSocket} | {error, Reason}</name> + <name since="OTP 21.0" name="handshake" arity="1" /> + <name since="OTP 21.0" name="handshake" arity="2" clause_i="1" /> <fsummary>Performs server-side SSL/TLS handshake.</fsummary> - <type> - <v>HsSocket = SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Timeout = timeout()</v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc> <p>Performs the SSL/TLS/DTLS server-side handshake.</p> <p>Returns a new TLS/DTLS socket if the handshake is successful.</p> @@ -1435,17 +1335,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 21.0">handshake(Socket, Options) -> </name> - <name since="OTP 21.0">handshake(Socket, Options, Timeout) -> {ok, SslSocket} | {ok, SslSocket, Ext} | {error, Reason}</name> + <name since="OTP 21.0" name="handshake" arity="2" clause_i="2" /> + <name since="OTP 21.0" name="handshake" arity="3" /> <fsummary>Performs server-side SSL/TLS/DTLS handshake.</fsummary> - <type> - <v>Socket = socket() | <seealso marker="#type-sslsocket"> socket() </seealso> </v> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso> </v> - <v>Ext = <seealso marker="#type-protocol_extensions">protocol_extensions()</seealso></v> - <v>Options = <seealso marker="#type-tls_server_option"> [server_option()] </seealso> </v> - <v>Timeout = timeout()</v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc> <p>If <c>Socket</c> is a ordinary <c>socket()</c>: upgrades a <c>gen_tcp</c>, or equivalent, socket to an SSL socket, that is, performs @@ -1481,52 +1373,33 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 21.0">handshake_cancel(SslSocket) -> ok </name> + <name since="OTP 21.0" name="handshake_cancel" arity="1" /> <fsummary>Cancel handshake with a fatal alert</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - </type> <desc> <p>Cancel the handshake with a fatal <c>USER_CANCELED</c> alert.</p> </desc> </func> <func> - <name since="OTP 21.0">handshake_continue(HsSocket, Options) -> {ok, SslSocket} | {error, Reason}</name> - <name since="OTP 21.0">handshake_continue(HsSocket, Options, Timeout) -> {ok, SslSocket} | {error, Reason}</name> + <name since="OTP 21.0" name="handshake_continue" arity="2" /> + <name since="OTP 21.0" name="handshake_continue" arity="3" /> <fsummary>Continue the SSL/TLS handshake.</fsummary> - <type> - <v>HsSocket = SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Options = <seealso marker="#type-tls_option"> tls_option() </seealso> </v> - <v>Timeout = timeout()</v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc> <p>Continue the SSL/TLS handshake possiby with new, additional or changed options.</p> </desc> </func> <func> - <name since="">listen(Port, Options) -> - {ok, ListenSocket} | {error, Reason}</name> + <name since="" name="listen" arity="2" /> <fsummary>Creates an SSL listen socket.</fsummary> - <type> - <v>Port = <seealso marker="kernel:inet#type-port_number">inet:port_number()</seealso></v> - <v>Options = <seealso marker="#type-tls_server_option"> [server_option()] </seealso></v> - <v>ListenSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - </type> <desc> <p>Creates an SSL listen socket.</p> </desc> </func> <func> - <name since="OTP 18.0">negotiated_protocol(SslSocket) -> {ok, Protocol} | {error, protocol_not_negotiated}</name> + <name since="OTP 18.0" name="negotiated_protocol" arity="1" /> <fsummary>Returns the protocol negotiated through ALPN or NPN extensions.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Protocol = binary()</v> - </type> <desc> <p> Returns the protocol negotiated through ALPN or NPN extensions. @@ -1535,12 +1408,8 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">peercert(SslSocket) -> {ok, Cert} | {error, Reason}</name> + <name since="" name="peercert" arity="1" /> <fsummary>Returns the peer certificate.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Cert = binary()</v> - </type> <desc> <p>The peer certificate is returned as a DER-encoded binary. The certificate can be decoded with @@ -1550,27 +1419,16 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">peername(SslSocket) -> {ok, {Address, Port}} | - {error, Reason}</name> + <name since="" name="peername" arity="1" /> <fsummary>Returns the peer address and port.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Address = ipaddress()</v> - <v>Port = <seealso marker="kernel:inet#type-port_number">inet:port_number()</seealso></v> - </type> <desc> <p>Returns the address and port number of the peer.</p> </desc> </func> <func> - <name since="OTP 20.3">prepend_cipher_suites(Preferred, Suites) -> ciphers()</name> + <name since="OTP 20.3" name="prepend_cipher_suites" arity="2" /> <fsummary></fsummary> - <type> - <v>Preferred = <seealso marker="#type-ciphers">ciphers()</seealso> | - <seealso marker="#type-cipher_filters">cipher_filters()</seealso></v> - <v>Suites = <seealso marker="#type-ciphers">ciphers()</seealso></v> - </type> <desc><p>Make <c>Preferred</c> suites become the most preferred suites that is put them at the head of the cipher suite list <c>Suites</c> after removing them from <c>Suites</c> if @@ -1581,15 +1439,8 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP R15B01">prf(Socket, Secret, Label, Seed, WantedLength) -> {ok, binary()} | {error, reason()}</name> + <name since="OTP R15B01" name="prf" arity="5" /> <fsummary>Uses a session Pseudo-Random Function to generate key material.</fsummary> - <type> - <v>Socket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Secret = binary() | master_secret</v> - <v>Label = binary()</v> - <v>Seed = [binary() | <seealso marker="#type-prf_random"> prf_random()</seealso>]</v> - <v>WantedLength = non_neg_integer()</v> - </type> <desc> <p>Uses the Pseudo-Random Function (PRF) of a TLS session to generate extra key material. It either takes user-generated values for @@ -1601,16 +1452,14 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">recv(SslSocket, Length) -> </name> - <name since="">recv(SslSocket, Length, Timeout) -> {ok, Data} | {error, - Reason}</name> + <name since="" name="recv" arity="2" /> + <name since="" name="recv" arity="3" /> <fsummary>Receives data on a socket.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Length = integer()</v> - <v>Timeout = timeout()</v> - <v>Data = [char()] | binary()</v> - </type> + <type_desc variable="HttpPacket">See the description of + <c>HttpPacket</c> in + <seealso marker="erts:erlang#decode_packet/3"><c>erlang:decode_packet/3</c></seealso> + in ERTS. + </type_desc> <desc> <p>Receives a packet from a socket in passive mode. A closed socket is indicated by return value @@ -1628,11 +1477,8 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP R14B">renegotiate(SslSocket) -> ok | {error, Reason}</name> + <name since="OTP R14B" name="renegotiate" arity="1" /> <fsummary>Initiates a new handshake.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - </type> <desc><p>Initiates a new handshake. A notable return value is <c>{error, renegotiation_rejected}</c> indicating that the peer refused to go through with the renegotiation, but the connection @@ -1641,40 +1487,27 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">send(SslSocket, Data) -> ok | {error, Reason}</name> + <name since="" name="send" arity="2" /> <fsummary>Writes data to a socket.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Data = iodata()</v> - </type> <desc> - <p>Writes <c>Data</c> to <c>Socket</c>.</p> + <p>Writes <c>Data</c> to <c>SslSocket</c>.</p> <p>A notable return value is <c>{error, closed}</c> indicating that the socket is closed.</p> </desc> </func> <func> - <name since="">setopts(SslSocket, Options) -> ok | {error, Reason}</name> + <name since="" name="setopts" arity="2" /> <fsummary>Sets socket options.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Options = <seealso marker="#type-socket_option"> [socket_option()] </seealso></v> - </type> <desc> <p>Sets options according to <c>Options</c> for socket - <c>Socket</c>.</p> + <c>SslSocket</c>.</p> </desc> </func> <func> - <name since="OTP R14B">shutdown(SslSocket, How) -> ok | {error, Reason}</name> + <name since="OTP R14B" name="shutdown" arity="2" /> <fsummary>Immediately closes a socket.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>How = read | write | read_write</v> - <v>Reason = reason()</v> - </type> <desc> <p>Immediately closes a socket in one or two directions.</p> <p><c>How == write</c> means closing the socket for writing, @@ -1686,14 +1519,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">ssl_accept(SslSocket) -> </name> - <name since="">ssl_accept(SslSocket, Timeout) -> ok | {error, Reason}</name> + <name since="" name="ssl_accept" arity="1" /> + <name since="" name="ssl_accept" arity="2" /> <fsummary>Performs server-side SSL/TLS handshake.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Timeout = timeout()</v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc> <p>Deprecated in OTP 21, use <seealso marker="#handshake-1">handshake/[1,2]</seealso> instead.</p> <note><p>handshake/[1,2] always returns a new socket.</p></note> @@ -1701,15 +1529,8 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">ssl_accept(Socket, Options) -> </name> - <name since="OTP R14B">ssl_accept(Socket, Options, Timeout) -> {ok, Socket} | ok | {error, Reason}</name> + <name since="OTP R14B" name="ssl_accept" arity="3" /> <fsummary>Performs server-side SSL/TLS/DTLS handshake.</fsummary> - <type> - <v>Socket = socket() | <seealso marker="#type-sslsocket"> sslsocket() </seealso> </v> - <v>Options = <seealso marker="#type-tls_server_option"> [server_option()] </seealso> </v> - <v>Timeout = timeout()</v> - <v>Reason = closed | timeout | <seealso marker="#type-error_alert"> error_alert() </seealso></v> - </type> <desc> <p>Deprecated in OTP 21, use <seealso marker="#handshake-3">handshake/[2,3]</seealso> instead.</p> <note><p>handshake/[2,3] always returns a new socket.</p></note> @@ -1717,27 +1538,18 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="">sockname(SslSocket) -> {ok, {Address, Port}} | - {error, Reason}</name> + <name since="" name="sockname" arity="1" /> <fsummary>Returns the local address and port.</fsummary> - <type> - <v>SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Address = <seealso marker="#type-ip_address">ip_address()</seealso></v> - <v>Port = <seealso marker="kernel:inet#type-port_number">inet:port_number()</seealso></v> - </type> <desc> <p>Returns the local address and port number of socket - <c>Socket</c>.</p> + <c>SslSocket</c>.</p> </desc> </func> <func> - <name since="OTP R14B">start() -> </name> + <name since="OTP R14B" name="start" arity="0" /> <name since="OTP R14B">start(Type) -> ok | {error, Reason}</name> <fsummary>Starts the SSL application.</fsummary> - <type> - <v>Type = permanent | transient | temporary</v> - </type> <desc> <p>Starts the SSL application. Default type is <c>temporary</c>.</p> @@ -1745,7 +1557,7 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP R14B">stop() -> ok </name> + <name since="OTP R14B" name="stop" arity="0" /> <fsummary>Stops the SSL application.</fsummary> <desc> <p>Stops the SSL application.</p> @@ -1753,28 +1565,18 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP 21.0">suite_to_str(CipherSuite) -> String</name> + <name since="OTP 21.0" name="suite_to_str" arity="1" clause_i="1" /> <fsummary>Returns the string representation of a cipher suite.</fsummary> - <type> - <v>CipherSuite = <seealso marker="#type-erl_cipher_suite"> erl_cipher_suite() </seealso></v> - <v>String = string()</v> - </type> <desc> <p>Returns the string representation of a cipher suite.</p> </desc> </func> <func> - <name since="">transport_accept(ListenSocket) -></name> - <name since="">transport_accept(ListenSocket, Timeout) -> - {ok, SslSocket} | {error, Reason}</name> + <name since="" name="transport_accept" arity="1" /> + <name since="" name="transport_accept" arity="2" /> <fsummary>Accepts an incoming connection and prepares for <c>ssl_accept</c>.</fsummary> - <type> - <v>ListenSocket = SslSocket = <seealso marker="#type-sslsocket"> sslsocket() </seealso></v> - <v>Timeout = timeout()</v> - <v>Reason = reason()</v> - </type> <desc> <p>Accepts an incoming connection request on a listen socket. <c>ListenSocket</c> must be a socket returned from @@ -1800,13 +1602,9 @@ fun(srp, Username :: string(), UserState :: term()) -> </func> <func> - <name since="OTP R14B">versions() -> [versions_info()]</name> + <name since="OTP R14B" name="versions" arity="0" /> <fsummary>Returns version information relevant for the SSL application.</fsummary> - <type> - <v>versions_info() = {app_vsn, string()} | {supported | available, [ssl_tls_protocol()]} | - {supported_dtls | available_dtls, [dtls_protocol()]} </v> - </type> <desc> <p>Returns version information relevant for the SSL application.</p> diff --git a/lib/ssl/doc/src/standards_compliance.xml b/lib/ssl/doc/src/standards_compliance.xml index c20bab4e50..ca98385f85 100644 --- a/lib/ssl/doc/src/standards_compliance.xml +++ b/lib/ssl/doc/src/standards_compliance.xml @@ -126,8 +126,34 @@ <section> <title>TLS 1.3</title> - <p> This section describes the current state of standards compliance for TLS 1.3.</p> - <p>(C = Compliant, NC = Non-Compliant, P = Partially-Compliant, NA = Not Applicable)</p> + <p>OTP-22 introduces basic support for TLS 1.3 on the server side. Basic functionality + covers a simple TLS 1.3 handshake with support of the mandatory extensions + (supported_groups, signature_algorithms, key_share, supported_versions and + signature_algorithms_cert). The server supports a selective set of cryptographic algorithms:</p> + <list type="bulleted"> + <item>Key Exchange: ECDHE</item> + <item>Groups: all standard groups supported for the Diffie-Hellman key exchange</item> + <item>Ciphers: TLS_AES_128_GCM_SHA256, TLS_AES_256_GCM_SHA384, + TLS_CHACHA20_POLY1305_SHA256 and TLS_AES_128_CCM_SHA256</item> + <item>Signature Algorithms: RSA and RSA PSS</item> + <item>Certificates: currently only certificates with RSA keys are supported</item> + </list> + <p>Other notable features:</p> + <list type="bulleted"> + <item>The server supports the HelloRetryRequest mechanism</item> + <item>PSK and session resumption not supported</item> + <item>Early data and 0-RTT not supported</item> + <item>Key and Initialization Vector Update not supported</item> + </list> + <p>For more detailed information see the + <seealso marker="#soc_table">Standards Compliance</seealso> below.</p> + <warning><p>Note that the client side is not yet functional. It is planned to be released + later in OTP-22.</p></warning> + + <p> The following table describes the current state of standards compliance for TLS 1.3.</p> + <p>(<em>C</em> = Compliant, <em>NC</em> = Non-Compliant, <em>PC</em> = Partially-Compliant, + <em>NA</em> = Not Applicable)</p> + <marker id="soc_table"/> <table> <row> <cell align="left" valign="middle"><em>Section</em></cell> @@ -155,7 +181,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle">RSASSA-PSS signature schemes</cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle">22</cell> </row> <row> @@ -178,7 +204,7 @@ </url> </cell> <cell align="left" valign="middle"></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -240,7 +266,7 @@ </url> </cell> <cell align="left" valign="middle"></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -783,7 +809,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>Server</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1265,7 +1291,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>Server</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1379,7 +1405,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>Server</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1456,7 +1482,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>Server</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1527,7 +1553,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>Server</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em></em></cell> </row> <row> @@ -1762,7 +1788,7 @@ </url> </cell> <cell align="left" valign="middle"><em></em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1924,7 +1950,7 @@ </url> </cell> <cell align="left" valign="middle"><em></em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1942,14 +1968,14 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle">SHOULD implement the TLS_CHACHA20_POLY1305_SHA256</cell> - <cell align="left" valign="middle"><em>NC</em></cell> - <cell align="left" valign="middle"></cell> + <cell align="left" valign="middle"><em>C</em></cell> + <cell align="left" valign="middle">22</cell> </row> <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>Digital signatures</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -1997,7 +2023,7 @@ </url> </cell> <cell align="left" valign="middle"><em></em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -2108,7 +2134,7 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle"><em>TLS 1.3 ServerHello</em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -2160,7 +2186,7 @@ </url> </cell> <cell align="left" valign="middle"><em></em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> <row> @@ -2178,14 +2204,14 @@ <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle">TLS_CHACHA20_POLY1305_SHA256</cell> - <cell align="left" valign="middle"><em>NC</em></cell> - <cell align="left" valign="middle"></cell> + <cell align="left" valign="middle"><em>C</em></cell> + <cell align="left" valign="middle">22</cell> </row> <row> <cell align="left" valign="middle"></cell> <cell align="left" valign="middle">TLS_AES_128_CCM_SHA256</cell> - <cell align="left" valign="middle"><em>NC</em></cell> - <cell align="left" valign="middle"></cell> + <cell align="left" valign="middle"><em>C</em></cell> + <cell align="left" valign="middle">22</cell> </row> <row> <cell align="left" valign="middle"></cell> @@ -2223,7 +2249,7 @@ </url> </cell> <cell align="left" valign="middle"><em></em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> @@ -2289,7 +2315,7 @@ </url> </cell> <cell align="left" valign="middle"><em></em></cell> - <cell align="left" valign="middle"><em>P</em></cell> + <cell align="left" valign="middle"><em>PC</em></cell> <cell align="left" valign="middle"><em>22</em></cell> </row> diff --git a/lib/ssl/src/ssl.erl b/lib/ssl/src/ssl.erl index 74511dce4b..e3bb4df1ac 100644 --- a/lib/ssl/src/ssl.erl +++ b/lib/ssl/src/ssl.erl @@ -86,27 +86,28 @@ srp_param_type/0]). %% ------------------------------------------------------------------------------------------------------- --type socket() :: gen_tcp:socket(). --type socket_option() :: gen_tcp:connect_option() | gen_tcp:listen_option() | gen_udp:option(). --type sslsocket() :: any(). --type tls_option() :: tls_client_option() | tls_server_option(). --type tls_client_option() :: client_option() | common_option() | socket_option() | transport_option(). --type tls_server_option() :: server_option() | common_option() | socket_option() | transport_option(). + +-type socket() :: gen_tcp:socket(). % exported +-type socket_option() :: gen_tcp:connect_option() | gen_tcp:listen_option() | gen_udp:option(). % exported +-type sslsocket() :: any(). % exported +-type tls_option() :: tls_client_option() | tls_server_option(). % exported +-type tls_client_option() :: client_option() | common_option() | socket_option() | transport_option(). % exported +-type tls_server_option() :: server_option() | common_option() | socket_option() | transport_option(). % exported -type active_msgs() :: {ssl, sslsocket(), Data::binary() | list()} | {ssl_closed, sslsocket()} | - {ssl_error, sslsocket(), Reason::term()} | {ssl_passive, sslsocket()}. + {ssl_error, sslsocket(), Reason::any()} | {ssl_passive, sslsocket()}. % exported -type transport_option() :: {cb_info, {CallbackModule::atom(), DataTag::atom(), ClosedTag::atom(), ErrTag::atom()}} | {cb_info, {CallbackModule::atom(), DataTag::atom(), ClosedTag::atom(), ErrTag::atom(), PassiveTag::atom()}}. --type host() :: hostname() | ip_address(). +-type host() :: hostname() | ip_address(). % exported -type hostname() :: string(). -type ip_address() :: inet:ip_address(). --type session_id() :: binary(). --type protocol_version() :: tls_version() | dtls_version(). +-type session_id() :: binary(). % exported +-type protocol_version() :: tls_version() | dtls_version(). % exported -type tls_version() :: 'tlsv1.2' | 'tlsv1.3' | tls_legacy_version(). -type dtls_version() :: 'dtlsv1.2' | dtls_legacy_version(). -type tls_legacy_version() :: tlsv1 | 'tlsv1.1' | sslv3. --type dtls_legacy_version() :: 'dtlsv1'. +-type dtls_legacy_version() :: 'dtlsv1'. -type verify_type() :: verify_none | verify_peer. -type cipher() :: aes_128_cbc | aes_256_cbc | @@ -117,14 +118,14 @@ aes_128_ccm_8 | aes_256_ccm_8 | chacha20_poly1305 | - legacy_cipher(). + legacy_cipher(). % exported -type legacy_cipher() :: rc4_128 | des_cbc | '3des_ede_cbc'. -type hash() :: sha | sha2() | - legacy_hash(). + legacy_hash(). % exported -type sha2() :: sha224 | sha256 | @@ -133,7 +134,7 @@ -type legacy_hash() :: md5. --type sign_algo() :: rsa | dsa | ecdsa. +-type sign_algo() :: rsa | dsa | ecdsa. % exported -type sign_scheme() :: rsa_pkcs1_sha256 | rsa_pkcs1_sha384 @@ -155,7 +156,7 @@ srp_rsa| srp_dss | psk | dhe_psk | rsa_psk | dh_anon | ecdh_anon | srp_anon | - any. %% TLS 1.3 + any. %% TLS 1.3 , exported -type erl_cipher_suite() :: #{key_exchange := kex_algo(), cipher := cipher(), mac := hash() | aead, @@ -195,15 +196,18 @@ secp160r1 | secp160r2. +-type group() :: secp256r1 | secp384r1 | secp521r1 | ffdhe2048 | + ffdhe3072 | ffdhe4096 | ffdhe6144 | ffdhe8192. + -type srp_param_type() :: srp_1024 | srp_1536 | srp_2048 | srp_3072 | srp_4096 | srp_6144 | - srp_8192. + srp_8192. % exported --type error_alert() :: {tls_alert, {tls_alert(), Description::string()}}. +-type error_alert() :: {tls_alert, {tls_alert(), Description::string()}}. % exported -type tls_alert() :: close_notify | unexpected_message | @@ -234,6 +238,7 @@ bad_certificate_hash_value | unknown_psk_identity | no_application_protocol. + %% ------------------------------------------------------------------------------------------------------- -type common_option() :: {protocol, protocol()} | {handshake, handshake_completion()} | @@ -243,7 +248,7 @@ {keyfile, key_pem()} | {password, key_password()} | {ciphers, cipher_suites()} | - {eccs, eccs()} | + {eccs, [named_curve()]} | {signature_algs_cert, signature_schemes()} | {secure_renegotiate, secure_renegotiation()} | {depth, allowed_cert_chain_length()} | @@ -270,29 +275,28 @@ #{algorithm := rsa | dss | ecdsa, engine := crypto:engine_ref(), key_id := crypto:key_id(), - password => crypto:password()}. + password => crypto:password()}. % exported -type key_pem() :: file:filename(). -type key_password() :: string(). -type cipher_suites() :: ciphers(). -type ciphers() :: [erl_cipher_suite()] | - string(). % (according to old API) + string(). % (according to old API) exported -type cipher_filters() :: list({key_exchange | cipher | mac | prf, - algo_filter()}). + algo_filter()}). % exported -type algo_filter() :: fun((kex_algo()|cipher()|hash()|aead|default_prf) -> true | false). --type eccs() :: [named_curve()]. -type secure_renegotiation() :: boolean(). -type allowed_cert_chain_length() :: integer(). --type custom_verify() :: {Verifyfun :: fun(), InitialUserState :: term()}. +-type custom_verify() :: {Verifyfun :: fun(), InitialUserState :: any()}. -type crl_check() :: boolean() | peer | best_effort. --type crl_cache_opts() :: [term()]. +-type crl_cache_opts() :: [any()]. -type handshake_size() :: integer(). -type hibernate_after() :: timeout(). -type root_fun() :: fun(). -type protocol_versions() :: [protocol_version()]. -type signature_algs() :: [{hash(), sign_algo()}]. -type signature_schemes() :: [sign_scheme()]. --type custom_user_lookup() :: {Lookupfun :: fun(), UserState :: term()}. +-type custom_user_lookup() :: {Lookupfun :: fun(), UserState :: any()}. -type padding_check() :: boolean(). -type beast_mitigation() :: one_n_minus_one | zero_n | disabled. -type srp_identity() :: {Username :: string(), Password :: string()}. @@ -375,7 +379,7 @@ -type honor_ecc_order() :: boolean(). -type client_renegotiation() :: boolean(). %% ------------------------------------------------------------------------------------------------------- --type prf_random() :: client_random | server_random. +-type prf_random() :: client_random | server_random. % exported -type protocol_extensions() :: #{renegotiation_info => binary(), signature_algs => signature_algs(), alpn => app_level_protocol(), @@ -383,7 +387,7 @@ next_protocol => app_level_protocol(), ec_point_formats => [0..2], elliptic_curves => [public_key:oid()], - sni => hostname()}. + sni => hostname()}. % exported %% ------------------------------------------------------------------------------------------------------- %%%-------------------------------------------------------------------- @@ -419,14 +423,31 @@ stop() -> %% %% Description: Connect to an ssl server. %%-------------------------------------------------------------------- --spec connect(host() | port(), [tls_client_option()]) -> {ok, #sslsocket{}} | - {error, reason()}. + +-spec connect(TCPSocket, TLSOptions) -> + {ok, sslsocket()} | + {error, reason()} | + {option_not_a_key_value_tuple, any()} when + TCPSocket :: socket(), + TLSOptions :: [tls_client_option()]. + connect(Socket, SslOptions) when is_port(Socket) -> connect(Socket, SslOptions, infinity). --spec connect(host() | port(), [tls_client_option()] | inet:port_number(), - timeout() | list()) -> - {ok, #sslsocket{}} | {error, reason()}. +-spec connect(TCPSocket, TLSOptions, Timeout) -> + {ok, sslsocket()} | {error, reason()} when + TCPSocket :: socket(), + TLSOptions :: [tls_client_option()], + Timeout :: timeout(); + (Host, Port, TLSOptions) -> + {ok, sslsocket()} | + {ok, sslsocket(),Ext :: protocol_extensions()} | + {error, reason()} | + {option_not_a_key_value_tuple, any()} when + Host :: host(), + Port :: inet:port_number(), + TLSOptions :: [tls_client_option()]. + connect(Socket, SslOptions0, Timeout) when is_port(Socket), (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity) -> CbInfo = handle_option(cb_info, SslOptions0, default_cb_info(tls)), @@ -443,8 +464,16 @@ connect(Socket, SslOptions0, Timeout) when is_port(Socket), connect(Host, Port, Options) -> connect(Host, Port, Options, infinity). --spec connect(host() | port(), inet:port_number(), list(), timeout()) -> - {ok, #sslsocket{}} | {error, reason()}. + +-spec connect(Host, Port, TLSOptions, Timeout) -> + {ok, sslsocket()} | + {ok, sslsocket(),Ext :: protocol_extensions()} | + {error, reason()} | + {option_not_a_key_value_tuple, any()} when + Host :: host(), + Port :: inet:port_number(), + TLSOptions :: [tls_client_option()], + Timeout :: timeout(). connect(Host, Port, Options, Timeout) when (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity) -> try @@ -461,7 +490,10 @@ connect(Host, Port, Options, Timeout) when (is_integer(Timeout) andalso Timeout end. %%-------------------------------------------------------------------- --spec listen(inet:port_number(), [tls_server_option()]) ->{ok, #sslsocket{}} | {error, reason()}. +-spec listen(Port, Options) -> {ok, ListenSocket} | {error, reason()} when + Port::inet:port_number(), + Options::[tls_server_option()], + ListenSocket :: sslsocket(). %% %% Description: Creates an ssl listen socket. @@ -480,13 +512,20 @@ listen(Port, Options0) -> %% %% Description: Performs transport accept on an ssl listen socket %%-------------------------------------------------------------------- --spec transport_accept(#sslsocket{}) -> {ok, #sslsocket{}} | - {error, reason()}. +-spec transport_accept(ListenSocket) -> {ok, SslSocket} | + {error, reason()} when + ListenSocket :: sslsocket(), + SslSocket :: sslsocket(). + transport_accept(ListenSocket) -> transport_accept(ListenSocket, infinity). --spec transport_accept(#sslsocket{}, timeout()) -> {ok, #sslsocket{}} | - {error, reason()}. +-spec transport_accept(ListenSocket, Timeout) -> {ok, SslSocket} | + {error, reason()} when + ListenSocket :: sslsocket(), + Timeout :: timeout(), + SslSocket :: sslsocket(). + transport_accept(#sslsocket{pid = {ListenSocket, #config{connection_cb = ConnectionCb} = Config}}, Timeout) when (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity) -> @@ -502,12 +541,22 @@ transport_accept(#sslsocket{pid = {ListenSocket, %% Description: Performs accept on an ssl listen socket. e.i. performs %% ssl handshake. %%-------------------------------------------------------------------- --spec ssl_accept(#sslsocket{}) -> ok | {error, timeout | closed | {options, any()}| error_alert()}. +-spec ssl_accept(SslSocket) -> + ok | + {error, Reason} when + SslSocket :: sslsocket(), + Reason :: closed | timeout | error_alert(). + ssl_accept(ListenSocket) -> ssl_accept(ListenSocket, [], infinity). --spec ssl_accept(#sslsocket{} | port(), timeout()| [tls_server_option()]) -> - ok | {ok, #sslsocket{}} | {error, timeout | closed | {options, any()}| error_alert()}. +-spec ssl_accept(Socket, TimeoutOrOptions) -> + ok | + {ok, sslsocket()} | {error, Reason} when + Socket :: sslsocket() | socket(), + TimeoutOrOptions :: timeout() | [tls_server_option()], + Reason :: timeout | closed | {options, any()} | error_alert(). + ssl_accept(Socket, Timeout) when (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity) -> ssl_accept(Socket, [], Timeout); ssl_accept(ListenSocket, SslOptions) when is_port(ListenSocket) -> @@ -515,8 +564,13 @@ ssl_accept(ListenSocket, SslOptions) when is_port(ListenSocket) -> ssl_accept(Socket, Timeout) -> ssl_accept(Socket, [], Timeout). --spec ssl_accept(#sslsocket{} | port(), [tls_server_option()], timeout()) -> - ok | {ok, #sslsocket{}} | {error, timeout | closed | {options, any()}| error_alert()}. +-spec ssl_accept(Socket, Options, Timeout) -> + ok | {ok, sslsocket()} | {error, Reason} when + Socket :: sslsocket() | socket(), + Options :: [tls_server_option()], + Timeout :: timeout(), + Reason :: timeout | closed | {options, any()} | error_alert(). + ssl_accept(Socket, SslOptions, Timeout) when is_port(Socket) -> handshake(Socket, SslOptions, Timeout); ssl_accept(Socket, SslOptions, Timeout) -> @@ -533,13 +587,28 @@ ssl_accept(Socket, SslOptions, Timeout) -> %%-------------------------------------------------------------------- %% Performs the SSL/TLS/DTLS server-side handshake. --spec handshake(#sslsocket{}) -> {ok, #sslsocket{}} | {error, timeout | closed | {options, any()} | error_alert()}. +-spec handshake(HsSocket) -> {ok, SslSocket} | {ok, SslSocket, Ext} | {error, Reason} when + HsSocket :: sslsocket(), + SslSocket :: sslsocket(), + Ext :: protocol_extensions(), + Reason :: closed | timeout | error_alert(). handshake(ListenSocket) -> handshake(ListenSocket, infinity). --spec handshake(#sslsocket{} | port(), timeout()| [tls_server_option()]) -> - {ok, #sslsocket{}} | {error, timeout | closed | {options, any()} | error_alert()}. +-spec handshake(HsSocket, Timeout) -> {ok, SslSocket} | {ok, SslSocket, Ext} | {error, Reason} when + HsSocket :: sslsocket(), + Timeout :: timeout(), + SslSocket :: sslsocket(), + Ext :: protocol_extensions(), + Reason :: closed | timeout | error_alert(); + (Socket, Options) -> {ok, SslSocket} | {ok, SslSocket, Ext} | {error, Reason} when + Socket :: socket() | sslsocket(), + SslSocket :: sslsocket(), + Options :: [server_option()], + Ext :: protocol_extensions(), + Reason :: closed | timeout | error_alert(). + handshake(#sslsocket{} = Socket, Timeout) when (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity) -> ssl_connection:handshake(Socket, Timeout); @@ -553,8 +622,17 @@ handshake(#sslsocket{} = Socket, Timeout) when (is_integer(Timeout) andalso Tim handshake(ListenSocket, SslOptions) when is_port(ListenSocket) -> handshake(ListenSocket, SslOptions, infinity). --spec handshake(#sslsocket{} | port(), [tls_server_option()], timeout()) -> - {ok, #sslsocket{}} | {error, timeout | closed | {options, any()} | error_alert()}. +-spec handshake(Socket, Options, Timeout) -> + {ok, SslSocket} | + {ok, SslSocket, Ext} | + {error, Reason} when + Socket :: socket() | sslsocket(), + SslSocket :: sslsocket(), + Options :: [server_option()], + Timeout :: timeout(), + Ext :: protocol_extensions(), + Reason :: closed | timeout | {options, any()} | error_alert(). + handshake(#sslsocket{} = Socket, [], Timeout) when (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity)-> handshake(Socket, Timeout); @@ -597,8 +675,12 @@ handshake(Socket, SslOptions, Timeout) when is_port(Socket), %%-------------------------------------------------------------------- --spec handshake_continue(#sslsocket{}, [tls_client_option() | tls_server_option()]) -> - {ok, #sslsocket{}} | {error, reason()}. +-spec handshake_continue(HsSocket, Options) -> + {ok, SslSocket} | {error, Reason} when + HsSocket :: sslsocket(), + Options :: [tls_client_option() | tls_server_option()], + SslSocket :: sslsocket(), + Reason :: closed | timeout | error_alert(). %% %% %% Description: Continues the handshke possible with newly supplied options. @@ -606,8 +688,13 @@ handshake(Socket, SslOptions, Timeout) when is_port(Socket), handshake_continue(Socket, SSLOptions) -> handshake_continue(Socket, SSLOptions, infinity). %%-------------------------------------------------------------------- --spec handshake_continue(#sslsocket{}, [tls_client_option() | tls_server_option()], timeout()) -> - {ok, #sslsocket{}} | {error, reason()}. +-spec handshake_continue(HsSocket, Options, Timeout) -> + {ok, SslSocket} | {error, Reason} when + HsSocket :: sslsocket(), + Options :: [tls_client_option() | tls_server_option()], + Timeout :: timeout(), + SslSocket :: sslsocket(), + Reason :: closed | timeout | error_alert(). %% %% %% Description: Continues the handshke possible with newly supplied options. @@ -615,7 +702,7 @@ handshake_continue(Socket, SSLOptions) -> handshake_continue(Socket, SSLOptions, Timeout) -> ssl_connection:handshake_continue(Socket, SSLOptions, Timeout). %%-------------------------------------------------------------------- --spec handshake_cancel(#sslsocket{}) -> term(). +-spec handshake_cancel(#sslsocket{}) -> any(). %% %% Description: Cancels the handshakes sending a close alert. %%-------------------------------------------------------------------- @@ -623,7 +710,9 @@ handshake_cancel(Socket) -> ssl_connection:handshake_cancel(Socket). %%-------------------------------------------------------------------- --spec close(#sslsocket{}) -> term(). +-spec close(SslSocket) -> ok | {error, Reason} when + SslSocket :: sslsocket(), + Reason :: any(). %% %% Description: Close an ssl connection %%-------------------------------------------------------------------- @@ -635,7 +724,10 @@ close(#sslsocket{pid = {ListenSocket, #config{transport_info={Transport,_,_,_,_} Transport:close(ListenSocket). %%-------------------------------------------------------------------- --spec close(#sslsocket{}, timeout() | {pid(), integer()}) -> term(). +-spec close(SslSocket, How) -> ok | {ok, port()} | {error,Reason} when + SslSocket :: sslsocket(), + How :: timeout() | {NewController::pid(), timeout()}, + Reason :: any(). %% %% Description: Close an ssl connection %%-------------------------------------------------------------------- @@ -651,7 +743,9 @@ close(#sslsocket{pid = {ListenSocket, #config{transport_info={Transport,_,_,_,_} Transport:close(ListenSocket). %%-------------------------------------------------------------------- --spec send(#sslsocket{}, iodata()) -> ok | {error, reason()}. +-spec send(SslSocket, Data) -> ok | {error, reason()} when + SslSocket :: sslsocket(), + Data :: iodata(). %% %% Description: Sends data over the ssl connection %%-------------------------------------------------------------------- @@ -671,11 +765,22 @@ send(#sslsocket{pid = {ListenSocket, #config{transport_info = Info}}}, Data) -> %% %% Description: Receives data when active = false %%-------------------------------------------------------------------- --spec recv(#sslsocket{}, integer()) -> {ok, binary()| list()} | {error, reason()}. +-spec recv(SslSocket, Length) -> {ok, Data} | {error, reason()} when + SslSocket :: sslsocket(), + Length :: integer(), + Data :: binary() | list() | HttpPacket, + HttpPacket :: any(). + recv(Socket, Length) -> recv(Socket, Length, infinity). --spec recv(#sslsocket{}, integer(), timeout()) -> {ok, binary()| list()} | {error, reason()}. +-spec recv(SslSocket, Length, Timeout) -> {ok, Data} | {error, reason()} when + SslSocket :: sslsocket(), + Length :: integer(), + Data :: binary() | list() | HttpPacket, + Timeout :: timeout(), + HttpPacket :: any(). + recv(#sslsocket{pid = [Pid|_]}, Length, Timeout) when is_pid(Pid), (is_integer(Timeout) andalso Timeout >= 0) or (Timeout == infinity)-> ssl_connection:recv(Pid, Length, Timeout); @@ -687,7 +792,10 @@ recv(#sslsocket{pid = {Listen, Transport:recv(Listen, 0). %% {error,enotconn} %%-------------------------------------------------------------------- --spec controlling_process(#sslsocket{}, pid()) -> ok | {error, reason()}. +-spec controlling_process(SslSocket, NewOwner) -> ok | {error, Reason} when + SslSocket :: sslsocket(), + NewOwner :: pid(), + Reason :: any(). %% %% Description: Changes process that receives the messages when active = true %% or once. @@ -706,7 +814,11 @@ controlling_process(#sslsocket{pid = {Listen, %%-------------------------------------------------------------------- --spec connection_information(#sslsocket{}) -> {ok, list()} | {error, reason()}. +-spec connection_information(SslSocket) -> {ok, Result} | {error, reason()} when + SslSocket :: sslsocket(), + Result :: [{OptionName, OptionValue}], + OptionName :: atom(), + OptionValue :: any(). %% %% Description: Return SSL information for the connection %%-------------------------------------------------------------------- @@ -723,7 +835,12 @@ connection_information(#sslsocket{pid = {dtls,_}}) -> {error,enotconn}. %%-------------------------------------------------------------------- --spec connection_information(#sslsocket{}, [atom()]) -> {ok, list()} | {error, reason()}. +-spec connection_information(SslSocket, Items) -> {ok, Result} | {error, reason()} when + SslSocket :: sslsocket(), + Items :: [OptionName], + Result :: [{OptionName, OptionValue}], + OptionName :: atom(), + OptionValue :: any(). %% %% Description: Return SSL information for the connection %%-------------------------------------------------------------------- @@ -737,7 +854,11 @@ connection_information(#sslsocket{pid = [Pid|_]}, Items) when is_pid(Pid) -> end. %%-------------------------------------------------------------------- --spec peername(#sslsocket{}) -> {ok, {inet:ip_address(), inet:port_number()}} | {error, reason()}. +-spec peername(SslSocket) -> {ok, {Address, Port}} | + {error, reason()} when + SslSocket :: sslsocket(), + Address :: inet:ip_address(), + Port :: inet:port_number(). %% %% Description: same as inet:peername/1. %%-------------------------------------------------------------------- @@ -753,7 +874,9 @@ peername(#sslsocket{pid = {dtls,_}}) -> {error,enotconn}. %%-------------------------------------------------------------------- --spec peercert(#sslsocket{}) ->{ok, DerCert::binary()} | {error, reason()}. +-spec peercert(SslSocket) -> {ok, Cert} | {error, reason()} when + SslSocket :: sslsocket(), + Cert :: binary(). %% %% Description: Returns the peercert. %%-------------------------------------------------------------------- @@ -770,7 +893,10 @@ peercert(#sslsocket{pid = {Listen, _}}) when is_port(Listen) -> {error, enotconn}. %%-------------------------------------------------------------------- --spec negotiated_protocol(#sslsocket{}) -> {ok, binary()} | {error, reason()}. +-spec negotiated_protocol(SslSocket) -> {ok, Protocol} | {error, Reason} when + SslSocket :: sslsocket(), + Protocol :: binary(), + Reason :: protocol_not_negotiated. %% %% Description: Returns the protocol that has been negotiated. If no %% protocol has been negotiated will return {error, protocol_not_negotiated} @@ -784,8 +910,9 @@ negotiated_protocol(#sslsocket{pid = [Pid|_]}) when is_pid(Pid) -> cipher_suites() -> cipher_suites(erlang). %%-------------------------------------------------------------------- --spec cipher_suites(erlang | openssl | all) -> - [old_cipher_suite() | string()]. +-spec cipher_suites(Type) -> [old_cipher_suite() | string()] when + Type :: erlang | openssl | all. + %% Description: Returns all supported cipher suites. %%-------------------------------------------------------------------- cipher_suites(erlang) -> @@ -799,9 +926,10 @@ cipher_suites(all) -> [ssl_cipher_format:suite_legacy(Suite) || Suite <- available_suites(all)]. %%-------------------------------------------------------------------- --spec cipher_suites(default | all | anonymous, ssl_record:ssl_version() | - tls_record:tls_atom_version() | dtls_record:dtls_atom_version()) -> - [erl_cipher_suite()]. +-spec cipher_suites(Supported, Version) -> ciphers() when + Supported :: default | all | anonymous, + Version :: protocol_version(). + %% Description: Returns all default and all supported cipher suites for a %% TLS/DTLS version %%-------------------------------------------------------------------- @@ -817,9 +945,10 @@ cipher_suites(Base, Version) -> [ssl_cipher_format:suite_bin_to_map(Suite) || Suite <- supported_suites(Base, Version)]. %%-------------------------------------------------------------------- --spec filter_cipher_suites([erl_cipher_suite()] | [ssl_cipher_format:cipher_suite()] , - [{key_exchange | cipher | mac | prf, fun()}] | []) -> - [erl_cipher_suite()] | [ssl_cipher_format:cipher_suite()]. +-spec filter_cipher_suites(Suites, Filters) -> Ciphers when + Suites :: ciphers(), + Filters :: cipher_filters(), + Ciphers :: ciphers(). %% Description: Removes cipher suites if any of the filter functions returns false %% for any part of the cipher suite. This function also calls default filter functions @@ -837,10 +966,10 @@ filter_cipher_suites(Suites, Filters0) -> prf_filters => add_filter(proplists:get_value(prf, Filters0), PrfF)}, ssl_cipher:filter_suites(Suites, Filters). %%-------------------------------------------------------------------- --spec prepend_cipher_suites([erl_cipher_suite()] | - [{key_exchange | cipher | mac | prf, fun()}], - [erl_cipher_suite()]) -> - [erl_cipher_suite()]. +-spec prepend_cipher_suites(Preferred, Suites) -> ciphers() when + Preferred :: ciphers() | cipher_filters(), + Suites :: ciphers(). + %% Description: Make <Preferred> suites become the most prefered %% suites that is put them at the head of the cipher suite list %% and remove them from <Suites> if present. <Preferred> may be a @@ -855,10 +984,10 @@ prepend_cipher_suites(Filters, Suites) -> Preferred = filter_cipher_suites(Suites, Filters), Preferred ++ (Suites -- Preferred). %%-------------------------------------------------------------------- --spec append_cipher_suites(Deferred :: [erl_cipher_suite()] | - [{key_exchange | cipher | mac | prf, fun()}], - [erl_cipher_suite()]) -> - [erl_cipher_suite()]. +-spec append_cipher_suites(Deferred, Suites) -> ciphers() when + Deferred :: ciphers() | cipher_filters(), + Suites :: ciphers(). + %% Description: Make <Deferred> suites suites become the %% least prefered suites that is put them at the end of the cipher suite list %% and removed them from <Suites> if present. @@ -872,7 +1001,9 @@ append_cipher_suites(Filters, Suites) -> (Suites -- Deferred) ++ Deferred. %%-------------------------------------------------------------------- --spec eccs() -> tls_v1:curves(). +-spec eccs() -> NamedCurves when + NamedCurves :: [named_curve()]. + %% Description: returns all supported curves across all versions %%-------------------------------------------------------------------- eccs() -> @@ -880,27 +1011,24 @@ eccs() -> eccs_filter_supported(Curves). %%-------------------------------------------------------------------- --spec eccs(tls_record:tls_atom_version() | - ssl_record:ssl_version() | dtls_record:dtls_atom_version()) -> - tls_v1:curves(). +-spec eccs(Version) -> NamedCurves when + Version :: protocol_version(), + NamedCurves :: [named_curve()]. + %% Description: returns the curves supported for a given version of %% ssl/tls. %%-------------------------------------------------------------------- -eccs({3,0}) -> +eccs(sslv3) -> []; -eccs({3,_}) -> - Curves = tls_v1:ecc_curves(all), - eccs_filter_supported(Curves); -eccs({254,_} = Version) -> - eccs(dtls_v1:corresponding_tls_version(Version)); +eccs('dtlsv1') -> + eccs('tlsv1.1'); +eccs('dtlsv1.2') -> + eccs('tlsv1.2'); eccs(Version) when Version == 'tlsv1.2'; Version == 'tlsv1.1'; - Version == tlsv1; - Version == sslv3 -> - eccs(tls_record:protocol_version(Version)); -eccs(Version) when Version == 'dtlsv1.2'; - Version == 'dtlsv1'-> - eccs(dtls_v1:corresponding_tls_version(dtls_record:protocol_version(Version))). + Version == tlsv1 -> + Curves = tls_v1:ecc_curves(all), + eccs_filter_supported(Curves). eccs_filter_supported(Curves) -> CryptoCurves = crypto:ec_curves(), @@ -908,22 +1036,24 @@ eccs_filter_supported(Curves) -> Curves). %%-------------------------------------------------------------------- --spec groups() -> tls_v1:supported_groups(). +-spec groups() -> [group()]. %% Description: returns all supported groups (TLS 1.3 and later) %%-------------------------------------------------------------------- groups() -> tls_v1:groups(4). %%-------------------------------------------------------------------- --spec groups(default) -> tls_v1:supported_groups(). +-spec groups(default) -> [group()]. %% Description: returns the default groups (TLS 1.3 and later) %%-------------------------------------------------------------------- groups(default) -> tls_v1:default_groups(4). %%-------------------------------------------------------------------- --spec getopts(#sslsocket{}, [gen_tcp:option_name()]) -> - {ok, [gen_tcp:option()]} | {error, reason()}. +-spec getopts(SslSocket, OptionNames) -> + {ok, [gen_tcp:option()]} | {error, reason()} when + SslSocket :: sslsocket(), + OptionNames :: [gen_tcp:option_name()]. %% %% Description: Gets options %%-------------------------------------------------------------------- @@ -954,7 +1084,9 @@ getopts(#sslsocket{}, OptionTags) -> {error, {options, {socket_options, OptionTags}}}. %%-------------------------------------------------------------------- --spec setopts(#sslsocket{}, [gen_tcp:option()]) -> ok | {error, reason()}. +-spec setopts(SslSocket, Options) -> ok | {error, reason()} when + SslSocket :: sslsocket(), + Options :: [gen_tcp:option()]. %% %% Description: Sets options %%-------------------------------------------------------------------- @@ -1010,9 +1142,9 @@ setopts(#sslsocket{}, Options) -> {error, {options,{not_a_proplist, Options}}}. %%--------------------------------------------------------------- --spec getstat(Socket) -> - {ok, OptionValues} | {error, inet:posix()} when - Socket :: #sslsocket{}, +-spec getstat(SslSocket) -> + {ok, OptionValues} | {error, inet:posix()} when + SslSocket :: sslsocket(), OptionValues :: [{inet:stat_option(), integer()}]. %% %% Description: Get all statistic options for a socket. @@ -1021,9 +1153,9 @@ getstat(Socket) -> getstat(Socket, inet:stats()). %%--------------------------------------------------------------- --spec getstat(Socket, Options) -> - {ok, OptionValues} | {error, inet:posix()} when - Socket :: #sslsocket{}, +-spec getstat(SslSocket, Options) -> + {ok, OptionValues} | {error, inet:posix()} when + SslSocket :: sslsocket(), Options :: [inet:stat_option()], OptionValues :: [{inet:stat_option(), integer()}]. %% @@ -1036,7 +1168,9 @@ getstat(#sslsocket{pid = [Pid|_], fd = {Transport, Socket, _, _}}, Options) when tls_socket:getstat(Transport, Socket, Options). %%--------------------------------------------------------------- --spec shutdown(#sslsocket{}, read | write | read_write) -> ok | {error, reason()}. +-spec shutdown(SslSocket, How) -> ok | {error, reason()} when + SslSocket :: sslsocket(), + How :: read | write | read_write. %% %% Description: Same as gen_tcp:shutdown/2 %%-------------------------------------------------------------------- @@ -1050,7 +1184,11 @@ shutdown(#sslsocket{pid = [Pid|_]}, How) when is_pid(Pid) -> ssl_connection:shutdown(Pid, How). %%-------------------------------------------------------------------- --spec sockname(#sslsocket{}) -> {ok, {inet:ip_address(), inet:port_number()}} | {error, reason()}. +-spec sockname(SslSocket) -> + {ok, {Address, Port}} | {error, reason()} when + SslSocket :: sslsocket(), + Address :: inet:ip_address(), + Port :: inet:port_number(). %% %% Description: Same as inet:sockname/1 %%-------------------------------------------------------------------- @@ -1064,10 +1202,10 @@ sockname(#sslsocket{pid = [Pid| _], fd = {Transport, Socket,_,_}}) when is_pid(P tls_socket:sockname(Transport, Socket). %%--------------------------------------------------------------- --spec versions() -> [{ssl_app, string()} | {supported, [tls_record:tls_atom_version()]} | - {supported_dtls, [dtls_record:dtls_atom_version()]} | - {available, [tls_record:tls_atom_version()]} | - {available_dtls, [dtls_record:dtls_atom_version()]}]. +-spec versions() -> [VersionInfo] when + VersionInfo :: {ssl_app, string()} | + {supported | available, [tls_version()]} | + {supported_dtls | available_dtls, [dtls_version()]}. %% %% Description: Returns a list of relevant versions. %%-------------------------------------------------------------------- @@ -1085,7 +1223,8 @@ versions() -> %%--------------------------------------------------------------- --spec renegotiate(#sslsocket{}) -> ok | {error, reason()}. +-spec renegotiate(SslSocket) -> ok | {error, reason()} when + SslSocket :: sslsocket(). %% %% Description: Initiates a renegotiation. %%-------------------------------------------------------------------- @@ -1105,9 +1244,13 @@ renegotiate(#sslsocket{pid = {Listen,_}}) when is_port(Listen) -> {error, enotconn}. %%-------------------------------------------------------------------- --spec prf(#sslsocket{}, binary() | 'master_secret', binary(), - [binary() | prf_random()], non_neg_integer()) -> - {ok, binary()} | {error, reason()}. +-spec prf(SslSocket, Secret, Label, Seed, WantedLength) -> + {ok, binary()} | {error, reason()} when + SslSocket :: sslsocket(), + Secret :: binary() | 'master_secret', + Label::binary(), + Seed :: [binary() | prf_random()], + WantedLength :: non_neg_integer(). %% %% Description: use a ssl sessions TLS PRF to generate key material %%-------------------------------------------------------------------- @@ -1128,7 +1271,8 @@ clear_pem_cache() -> ssl_pem_cache:clear(). %%--------------------------------------------------------------- --spec format_error({error, term()}) -> list(). +-spec format_error({error, Reason}) -> string() when + Reason :: any(). %% %% Description: Creates error string. %%-------------------------------------------------------------------- @@ -1167,7 +1311,14 @@ tls_version({254, _} = Version) -> dtls_v1:corresponding_tls_version(Version). %%-------------------------------------------------------------------- --spec suite_to_str(erl_cipher_suite()) -> string(). +-spec suite_to_str(CipherSuite) -> string() when + CipherSuite :: erl_cipher_suite(); + (CipherSuite) -> string() when + %% For internal use! + CipherSuite :: #{key_exchange := null, + cipher := null, + mac := null, + prf := null}. %% %% Description: Return the string representation of a cipher suite. %%-------------------------------------------------------------------- diff --git a/lib/ssl/src/ssl_cipher.hrl b/lib/ssl/src/ssl_cipher.hrl index 9c5e2f80a9..0fa5f66c49 100644 --- a/lib/ssl/src/ssl_cipher.hrl +++ b/lib/ssl/src/ssl_cipher.hrl @@ -690,9 +690,9 @@ -define(TLS_CHACHA20_POLY1305_SHA256, <<?BYTE(16#13),?BYTE(16#03)>>). %% %% TLS_AES_128_CCM_SHA256 = {0x13,0x04} -%% -define(TLS_AES_128_CCM_SHA256, <<?BYTE(16#13), ?BYTE(16#04)>>). +-define(TLS_AES_128_CCM_SHA256, <<?BYTE(16#13), ?BYTE(16#04)>>). %% %% TLS_AES_128_CCM_8_SHA256 = {0x13,0x05} -%% -define(TLS_AES_128_CCM_8_SHA256, <<?BYTE(16#13),?BYTE(16#05)>>). +-define(TLS_AES_128_CCM_8_SHA256, <<?BYTE(16#13),?BYTE(16#05)>>). -endif. % -ifdef(ssl_cipher). diff --git a/lib/ssl/src/ssl_cipher_format.erl b/lib/ssl/src/ssl_cipher_format.erl index 887eb6c653..577156a4b5 100644 --- a/lib/ssl/src/ssl_cipher_format.erl +++ b/lib/ssl/src/ssl_cipher_format.erl @@ -955,12 +955,12 @@ suite_bin_to_map(?TLS_CHACHA20_POLY1305_SHA256) -> #{key_exchange => any, cipher => chacha20_poly1305, mac => aead, - prf => sha256}. -%% suite_bin_to_map(?TLS_AES_128_CCM_SHA256) -> -%% #{key_exchange => any, -%% cipher => aes_128_ccm, -%% mac => aead -%% prf => sha256}; + prf => sha256}; +suite_bin_to_map(?TLS_AES_128_CCM_SHA256) -> + #{key_exchange => any, + cipher => aes_128_ccm, + mac => aead, + prf => sha256}. %% suite_bin_to_map(?TLS_AES_128_CCM_8_SHA256) -> %% #{key_exchange => any, %% cipher => aes_128_ccm_8, @@ -1690,12 +1690,12 @@ suite_map_to_bin(#{key_exchange := any, cipher := chacha20_poly1305, mac := aead, prf := sha256}) -> - ?TLS_CHACHA20_POLY1305_SHA256. -%% suite_map_to_bin(#{key_exchange := any, -%% cipher := aes_128_ccm, -%% mac := aead, -%% prf := sha256}) -> -%% ?TLS_AES_128_CCM_SHA256; + ?TLS_CHACHA20_POLY1305_SHA256; +suite_map_to_bin(#{key_exchange := any, + cipher := aes_128_ccm, + mac := aead, + prf := sha256}) -> + ?TLS_AES_128_CCM_SHA256. %% suite_map_to_bin(#{key_exchange := any, %% cipher := aes_128_ccm_8, %% mac := aead, diff --git a/lib/ssl/src/ssl_connection.erl b/lib/ssl/src/ssl_connection.erl index 6e325b504c..a5f754d2e3 100644 --- a/lib/ssl/src/ssl_connection.erl +++ b/lib/ssl/src/ssl_connection.erl @@ -115,7 +115,7 @@ handshake(Connection, Port, Socket, Opts, User, CbInfo, Timeout) -> %%-------------------------------------------------------------------- -spec handshake(#sslsocket{}, timeout()) -> {ok, #sslsocket{}} | - {ok, #sslsocket{}, map()}| {error, reason()}. + {ok, #sslsocket{}, map()}| {error, reason()}. %% %% Description: Starts ssl handshake. %%-------------------------------------------------------------------- @@ -130,8 +130,8 @@ handshake(#sslsocket{pid = [Pid|_]} = Socket, Timeout) -> end. %%-------------------------------------------------------------------- --spec handshake(#sslsocket{}, {#ssl_options{},#socket_options{}}, - timeout()) -> {ok, #sslsocket{}} | {error, reason()}. +-spec handshake(#sslsocket{}, {#ssl_options{},#socket_options{}}, timeout()) -> + {ok, #sslsocket{}} | {ok, #sslsocket{}, map()} | {error, reason()}. %% %% Description: Starts ssl handshake with some new options %%-------------------------------------------------------------------- diff --git a/lib/ssl/src/ssl_handshake.erl b/lib/ssl/src/ssl_handshake.erl index dc037bb1ea..7b34991f4f 100644 --- a/lib/ssl/src/ssl_handshake.erl +++ b/lib/ssl/src/ssl_handshake.erl @@ -98,7 +98,7 @@ hello_request() -> #hello_request{}. %%-------------------------------------------------------------------- --spec server_hello(#session{}, ssl_record:ssl_version(), ssl_record:connection_states(), +-spec server_hello(binary(), ssl_record:ssl_version(), ssl_record:connection_states(), Extension::map()) -> #server_hello{}. %% %% Description: Creates a server hello message. diff --git a/lib/ssl/src/ssl_internal.hrl b/lib/ssl/src/ssl_internal.hrl index 4ee0230d88..06c3ccae45 100644 --- a/lib/ssl/src/ssl_internal.hrl +++ b/lib/ssl/src/ssl_internal.hrl @@ -28,12 +28,12 @@ -define(VSN, "8.2.6"). -define(SECRET_PRINTOUT, "***"). --type reason() :: term(). --type reply() :: term(). --type msg() :: term(). --type from() :: term(). +-type reason() :: any(). +-type reply() :: any(). +-type msg() :: any(). +-type from() :: any(). -type certdb_ref() :: reference(). --type db_handle() :: term(). +-type db_handle() :: any(). -type der_cert() :: binary(). -type issuer() :: tuple(). -type serialnumber() :: integer(). @@ -109,26 +109,26 @@ -define('24H_in_sec', 86400). -record(ssl_options, { - protocol :: tls | dtls, - versions :: [ssl_record:ssl_version()], %% ssl_record:atom_version() in API - verify :: verify_none | verify_peer, + protocol :: tls | dtls | 'undefined', + versions :: [ssl_record:ssl_version()] | 'undefined', %% ssl_record:atom_version() in API + verify :: verify_none | verify_peer | 'undefined', verify_fun, %%:: fun(CertVerifyErrors::term()) -> boolean(), - partial_chain :: fun(), - fail_if_no_peer_cert :: boolean(), - verify_client_once :: boolean(), + partial_chain :: fun() | 'undefined', + fail_if_no_peer_cert :: boolean() | 'undefined', + verify_client_once :: boolean() | 'undefined', %% fun(Extensions, State, Verify, AccError) -> {Extensions, State, AccError} validate_extensions_fun, - depth :: integer(), - certfile :: binary(), + depth :: integer() | 'undefined', + certfile :: binary() | 'undefined', cert :: public_key:der_encoded() | secret_printout() | 'undefined', - keyfile :: binary(), - key :: {'RSAPrivateKey' | 'DSAPrivateKey' | 'ECPrivateKey' | 'PrivateKeyInfo', + keyfile :: binary() | 'undefined', + key :: {'RSAPrivateKey' | 'DSAPrivateKey' | 'ECPrivateKey' | 'PrivateKeyInfo' | 'undefined', public_key:der_encoded()} | map() %%map() -> ssl:key() how to handle dialyzer? | secret_printout() | 'undefined', password :: string() | secret_printout() | 'undefined', cacerts :: [public_key:der_encoded()] | secret_printout() | 'undefined', - cacertfile :: binary(), - dh :: public_key:der_encoded() | secret_printout(), + cacertfile :: binary() | 'undefined', + dh :: public_key:der_encoded() | secret_printout() | 'undefined', dhfile :: binary() | secret_printout() | 'undefined', user_lookup_fun, % server option, fun to lookup the user psk_identity :: binary() | secret_printout() | 'undefined', @@ -140,23 +140,23 @@ reuse_session :: fun() | binary() | undefined, %% Server side is a fun() %% If false sessions will never be reused, if true they %% will be reused if possible. - reuse_sessions :: boolean() | save, %% Only client side can use value save + reuse_sessions :: boolean() | save | 'undefined', %% Only client side can use value save renegotiate_at, secure_renegotiate, client_renegotiation, %% undefined if not hibernating, or number of ms of %% inactivity after which ssl_connection will go into %% hibernation - hibernate_after :: timeout(), + hibernate_after :: timeout() | 'undefined', %% This option should only be set to true by inet_tls_dist erl_dist = false :: boolean(), - alpn_advertised_protocols = undefined :: [binary()] | undefined , + alpn_advertised_protocols = undefined :: [binary()] | undefined, alpn_preferred_protocols = undefined :: [binary()] | undefined, next_protocols_advertised = undefined :: [binary()] | undefined, next_protocol_selector = undefined, %% fun([binary()]) -> binary()) log_level = notice :: atom(), server_name_indication = undefined, - sni_hosts :: [{inet:hostname(), [tuple()]}], + sni_hosts :: [{inet:hostname(), [tuple()]}] | 'undefined', sni_fun :: function() | undefined, %% Should the server prefer its own cipher order over the one provided by %% the client? @@ -166,14 +166,14 @@ %%mitigation entirely? beast_mitigation = one_n_minus_one :: one_n_minus_one | zero_n | disabled, fallback = false :: boolean(), - crl_check :: boolean() | peer | best_effort, + crl_check :: boolean() | peer | best_effort | 'undefined', crl_cache, signature_algs, signature_algs_cert, eccs, supported_groups, %% RFC 8422, RFC 8446 - honor_ecc_order :: boolean(), - max_handshake_size :: integer(), + honor_ecc_order :: boolean() | 'undefined', + max_handshake_size :: integer() | 'undefined', handshake, customize_hostname_check %% , @@ -199,9 +199,9 @@ }). -type state_name() :: hello | abbreviated | certify | cipher | connection. --type gen_fsm_state_return() :: {next_state, state_name(), term()} | - {next_state, state_name(), term(), timeout()} | - {stop, term(), term()}. +-type gen_fsm_state_return() :: {next_state, state_name(), any()} | + {next_state, state_name(), any(), timeout()} | + {stop, any(), any()}. -type ssl_options() :: #ssl_options{}. -endif. % -ifdef(ssl_internal). diff --git a/lib/ssl/src/tls_handshake.erl b/lib/ssl/src/tls_handshake.erl index 74ab0d5923..2480e05097 100644 --- a/lib/ssl/src/tls_handshake.erl +++ b/lib/ssl/src/tls_handshake.erl @@ -251,7 +251,7 @@ encode_handshake(Package, Version) -> %%-------------------------------------------------------------------- -spec get_tls_handshake(tls_record:tls_version(), binary(), binary() | iolist(), #ssl_options{}) -> - {[tls_handshake()], binary()}. + {[{tls_handshake(), binary()}], binary()}. %% %% Description: Given buffered and new data from ssl_record, collects %% and returns it as a list of handshake messages, also returns leftover diff --git a/lib/ssl/src/tls_v1.erl b/lib/ssl/src/tls_v1.erl index f103f3218b..27cd5765e5 100644 --- a/lib/ssl/src/tls_v1.erl +++ b/lib/ssl/src/tls_v1.erl @@ -501,18 +501,18 @@ suites(3) -> suites(4) -> [?TLS_AES_256_GCM_SHA384, ?TLS_AES_128_GCM_SHA256, - ?TLS_CHACHA20_POLY1305_SHA256 + ?TLS_CHACHA20_POLY1305_SHA256, + ?TLS_AES_128_CCM_SHA256 %% Not supported - %% ?TLS_AES_128_CCM_SHA256, %% ?TLS_AES_128_CCM_8_SHA256 ] ++ suites(3); suites('TLS_v1.3') -> [?TLS_AES_256_GCM_SHA384, ?TLS_AES_128_GCM_SHA256, - ?TLS_CHACHA20_POLY1305_SHA256 + ?TLS_CHACHA20_POLY1305_SHA256, + ?TLS_AES_128_CCM_SHA256 %% Not supported - %% ?TLS_AES_128_CCM_SHA256, %% ?TLS_AES_128_CCM_8_SHA256 ]. diff --git a/lib/ssl/test/ssl_ECC_SUITE.erl b/lib/ssl/test/ssl_ECC_SUITE.erl index ca8d0ec70c..c64358960c 100644 --- a/lib/ssl/test/ssl_ECC_SUITE.erl +++ b/lib/ssl/test/ssl_ECC_SUITE.erl @@ -212,7 +212,7 @@ client_ecdsa_server_ecdsa_with_raw_key(Config) when is_list(Config) -> ecc_default_order(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_ecdsa, @@ -227,7 +227,7 @@ ecc_default_order(Config) -> ecc_default_order_custom_curves(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_ecdsa, @@ -242,7 +242,7 @@ ecc_default_order_custom_curves(Config) -> ecc_client_order(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_ecdsa, @@ -257,7 +257,7 @@ ecc_client_order(Config) -> ecc_client_order_custom_curves(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_ecdsa, @@ -282,7 +282,7 @@ ecc_unknown_curve(Config) -> client_ecdh_rsa_server_ecdhe_ecdsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdh_rsa, ecdhe_ecdsa, Config), @@ -296,7 +296,7 @@ client_ecdh_rsa_server_ecdhe_ecdsa_server_custom(Config) -> client_ecdh_rsa_server_ecdhe_rsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdh_rsa, ecdhe_rsa, Config), @@ -311,7 +311,7 @@ client_ecdh_rsa_server_ecdhe_rsa_server_custom(Config) -> client_ecdhe_rsa_server_ecdhe_ecdsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_rsa, ecdhe_ecdsa, Config), @@ -325,7 +325,7 @@ client_ecdhe_rsa_server_ecdhe_ecdsa_server_custom(Config) -> client_ecdhe_rsa_server_ecdhe_rsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_rsa, ecdhe_rsa, Config), @@ -339,7 +339,7 @@ client_ecdhe_rsa_server_ecdhe_rsa_server_custom(Config) -> end. client_ecdhe_rsa_server_ecdh_rsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), Ext = x509_test:extensions([{key_usage, [keyEncipherment]}]), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, [[], [], [{extensions, Ext}]]}, {client_chain, Default}], @@ -357,7 +357,7 @@ client_ecdhe_rsa_server_ecdh_rsa_server_custom(Config) -> client_ecdhe_ecdsa_server_ecdhe_ecdsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_ecdsa, Config), @@ -371,7 +371,7 @@ client_ecdhe_ecdsa_server_ecdhe_ecdsa_server_custom(Config) -> client_ecdhe_ecdsa_server_ecdhe_rsa_server_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_rsa, Config), @@ -385,7 +385,7 @@ client_ecdhe_ecdsa_server_ecdhe_rsa_server_custom(Config) -> client_ecdhe_ecdsa_server_ecdhe_ecdsa_client_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_ecdsa, ecdhe_ecdsa, Config), @@ -399,7 +399,7 @@ client_ecdhe_ecdsa_server_ecdhe_ecdsa_client_custom(Config) -> client_ecdhe_rsa_server_ecdhe_ecdsa_client_custom(Config) -> Default = ssl_test_lib:default_cert_chain_conf(), - DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(0))), + DefaultCurve = pubkey_cert_records:namedCurves(hd(tls_v1:ecc_curves(1))), {COpts0, SOpts0} = ssl_test_lib:make_ec_cert_chains([{server_chain, Default}, {client_chain, Default}], ecdhe_rsa, ecdhe_ecdsa, Config), diff --git a/lib/ssl/test/ssl_basic_SUITE.erl b/lib/ssl/test/ssl_basic_SUITE.erl index 7b98209b31..20d9f28512 100644 --- a/lib/ssl/test/ssl_basic_SUITE.erl +++ b/lib/ssl/test/ssl_basic_SUITE.erl @@ -549,11 +549,10 @@ alerts(Config) when is_list(Config) -> Alerts = [?ALERT_REC(?WARNING, ?CLOSE_NOTIFY) | [?ALERT_REC(?FATAL, Desc) || Desc <- Descriptions]], lists:foreach(fun(Alert) -> - case ssl_alert:alert_txt(Alert) of - Txt when is_list(Txt) -> - ok; - Other -> - ct:fail({unexpected, Other}) + try ssl_alert:alert_txt(Alert) + catch + C:E:T -> + ct:fail({unexpected, {C, E, T}}) end end, Alerts). %%-------------------------------------------------------------------- @@ -1833,14 +1832,12 @@ eccs() -> eccs(Config) when is_list(Config) -> [_|_] = All = ssl:eccs(), - [] = SSL3 = ssl:eccs({3,0}), - [_|_] = Tls = ssl:eccs({3,1}), - [_|_] = Tls1 = ssl:eccs({3,2}), - [_|_] = Tls2 = ssl:eccs({3,3}), [] = SSL3 = ssl:eccs(sslv3), [_|_] = Tls = ssl:eccs(tlsv1), [_|_] = Tls1 = ssl:eccs('tlsv1.1'), [_|_] = Tls2 = ssl:eccs('tlsv1.2'), + [_|_] = Tls1 = ssl:eccs('dtlsv1'), + [_|_] = Tls2 = ssl:eccs('dtlsv1.2'), %% ordering is currently unverified by the test true = lists:sort(All) =:= lists:usort(SSL3 ++ Tls ++ Tls1 ++ Tls2), ok. @@ -3655,7 +3652,7 @@ listen_socket(Config) -> {error, enotconn} = ssl:peername(ListenSocket), {error, enotconn} = ssl:peercert(ListenSocket), {error, enotconn} = ssl:renegotiate(ListenSocket), - {error, enotconn} = ssl:prf(ListenSocket, 'master_secret', <<"Label">>, client_random, 256), + {error, enotconn} = ssl:prf(ListenSocket, 'master_secret', <<"Label">>, [client_random], 256), {error, enotconn} = ssl:shutdown(ListenSocket, read_write), ok = ssl:close(ListenSocket). diff --git a/lib/ssl/test/ssl_certificate_verify_SUITE.erl b/lib/ssl/test/ssl_certificate_verify_SUITE.erl index 4f340af4f5..55dee9a48f 100644 --- a/lib/ssl/test/ssl_certificate_verify_SUITE.erl +++ b/lib/ssl/test/ssl_certificate_verify_SUITE.erl @@ -448,7 +448,7 @@ server_require_peer_cert_partial_chain_fun_fail(Config) when is_list(Config) -> [{_,_,_}, {_, IntermidiateCA, _} | _] = public_key:pem_decode(ServerCAs), PartialChain = fun(_CertChain) -> - ture = false %% crash on purpose + true = false %% crash on purpose end, Server = ssl_test_lib:start_server_error([{node, ServerNode}, {port, 0}, diff --git a/lib/ssl/test/ssl_test_lib.erl b/lib/ssl/test/ssl_test_lib.erl index 798bdf0416..65b8998cc3 100644 --- a/lib/ssl/test/ssl_test_lib.erl +++ b/lib/ssl/test/ssl_test_lib.erl @@ -1873,6 +1873,14 @@ check_sane_openssl_version(Version) -> case {Version, os:cmd("openssl version")} of {'sslv3', "OpenSSL 1.0.2" ++ _} -> false; + {'dtlsv1', "OpenSSL 0" ++ _} -> + false; + {'dtlsv1.2', "OpenSSL 0" ++ _} -> + false; + {'dtlsv1.2', "OpenSSL 1.0.2" ++ _} -> + false; + {'dtlsv1', "OpenSSL 1.0.0" ++ _} -> + false; {'dtlsv1', _} -> not is_fips(openssl); {'dtlsv1.2', _} -> @@ -1885,18 +1893,10 @@ check_sane_openssl_version(Version) -> false; {'tlsv1.1', "OpenSSL 1.0.0" ++ _} -> false; - {'dtlsv1.2', "OpenSSL 1.0.2" ++ _} -> - false; - {'dtlsv1', "OpenSSL 1.0.0" ++ _} -> - false; {'tlsv1.2', "OpenSSL 0" ++ _} -> false; {'tlsv1.1', "OpenSSL 0" ++ _} -> false; - {'dtlsv1', "OpenSSL 0" ++ _} -> - false; - {'dtlsv1.2', "OpenSSL 0" ++ _} -> - false; {_, _} -> true end; diff --git a/lib/stdlib/doc/src/queue.xml b/lib/stdlib/doc/src/queue.xml index 83a8afea81..89cce6d85b 100644 --- a/lib/stdlib/doc/src/queue.xml +++ b/lib/stdlib/doc/src/queue.xml @@ -168,7 +168,7 @@ <fsummary>Test if a queue is empty.</fsummary> <desc> <p>Tests if <c><anno>Q</anno></c> is empty and returns <c>true</c> if - so, otherwise otherwise.</p> + so, otherwise <c>false</c>.</p> </desc> </func> diff --git a/lib/tools/test/Makefile b/lib/tools/test/Makefile index 2b7b17afb3..7a0a941ccc 100644 --- a/lib/tools/test/Makefile +++ b/lib/tools/test/Makefile @@ -32,6 +32,7 @@ MODULES = \ make_SUITE \ tools_SUITE \ xref_SUITE \ + prof_bench_SUITE \ ignore_cores ERL_FILES= $(MODULES:%=%.erl) @@ -41,7 +42,7 @@ INSTALL_PROGS= $(TARGET_FILES) EMAKEFILE=Emakefile -SPEC_FILES= tools.spec +SPEC_FILES= tools.spec tools_bench.spec COVER_FILE = tools.cover # ---------------------------------------------------- diff --git a/lib/tools/test/emacs_SUITE.erl b/lib/tools/test/emacs_SUITE.erl index 8756a4e9b3..73270e6ed6 100644 --- a/lib/tools/test/emacs_SUITE.erl +++ b/lib/tools/test/emacs_SUITE.erl @@ -119,7 +119,7 @@ compile_and_load(_Config) -> false -> " " end, emacs([Pedantic, - " -f batch-byte-compile ",filename:join(Dir, File)]), + " -f batch-byte-compile ", dquote(filename:join(Dir, File))]), true end, lists:foreach(Compile, Files), @@ -144,6 +144,10 @@ tests_compiled(_Config) -> ok end. + +dquote(Str) -> + "\"" ++ Str ++ "\"". + %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% indent(Config) -> @@ -207,14 +211,14 @@ emacs_version_ok(AcceptVer) -> emacs(EmacsCmds) when is_list(EmacsCmds) -> Cmd = ["emacs ", "--batch --quick ", - "--directory ", emacs_dir(), " ", + "--directory ", dquote(emacs_dir()), " ", "--eval \"(require 'erlang-start)\" " | EmacsCmds], Res0 = os:cmd(Cmd ++ " ; echo $?"), Rows = string:lexemes(Res0, ["\r\n", $\n]), Res = lists:last(Rows), Output = string:join(lists:droplast(Rows), "\n"), - io:format("Cmd ~s:~n => ~s ~ts~n", [Cmd, Res, Output]), + io:format("Cmd ~ts:~n => ~s ~ts~n", [Cmd, Res, Output]), "0" = Res, Output. diff --git a/lib/tools/test/prof_bench_SUITE.erl b/lib/tools/test/prof_bench_SUITE.erl new file mode 100644 index 0000000000..50d0ba9cd9 --- /dev/null +++ b/lib/tools/test/prof_bench_SUITE.erl @@ -0,0 +1,126 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2017. 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. +%% 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. +%% +%% %CopyrightEnd% +%% +-module(prof_bench_SUITE). + +-include_lib("common_test/include/ct_event.hrl"). + +%% Test server framework exports +-export([all/0, suite/0, init_per_suite/1, end_per_suite/1]). + +-export([overhead/1]). + +%%%--------------------------------------------------------------------- +%%% Test suites +%%%--------------------------------------------------------------------- + + +suite() -> + [{timetrap,{minutes,10}}]. + +all() -> + [overhead]. + +init_per_suite(Config) -> + case {test_server:is_native(fprof_SUITE) or + (lists:any(fun(M) -> test_server:is_native(M) end, modules())) or + (whereis(cover_server) =/= undefined), + erlang:system_info(wordsize)} + of + {true, _} -> {skip, "Native or cover code"}; + {_, 4} -> {skip, "Can't run on 32-bit as files will be large"}; + {false, 8} -> Config + end. + +end_per_suite(Config) -> + LogFile = filename:join(proplists:get_value(priv_dir, Config), "fprof.trace"), + file:delete(LogFile), + ok. + +%%%--------------------------------------------------------------------- + +%% ct:run_test([{suite, prof_bench_SUITE}]). +overhead(Config) -> + LogFile = filename:join(proplists:get_value(priv_dir, Config), "fprof.trace"), + SofsCopy = filename:join(proplists:get_value(data_dir, Config), "sofs_copy.erl"), + TC = fun() -> compile:file(SofsCopy, [binary]) end, + _Warmup = timer:tc(TC), + + {NormTime,{ok, sofs_copy, _}} = timer:tc(TC), + {FProfTime,{ok,sofs_copy,_}} = fprof:apply(timer, tc, [TC], [{file, LogFile}]), + ct:pal("FProf: ~p Norm: ~p Ratio: ~p",[FProfTime, NormTime, NormTime / FProfTime * 100]), + {ok,{EProfTime,{ok,sofs_copy,_}}} = eprof:profile([], timer, tc, [TC]), + ct:pal("EProf: ~p Norm: ~p Ratio: ~p",[EProfTime, NormTime, NormTime / EProfTime * 100]), + {CProfTime,{ok,sofs_copy,_}} = cprof_apply(timer, tc, [TC]), + ct:pal("CProf: ~p Norm: ~p Ratio: ~p",[CProfTime, NormTime, NormTime / CProfTime * 100]), + {CoverTime,{ok,sofs_copy,_}} = cover_apply(timer, tc, [TC]), + ct:pal("Cover: ~p Norm: ~p Ratio: ~p",[CoverTime, NormTime, NormTime / CoverTime * 100]), + + ct_event:notify(#event{name = benchmark_data, + data = [{name, fprof_overhead}, + {value, NormTime / FProfTime * 100}]}), + ct_event:notify(#event{name = benchmark_data, + data = [{name, eprof_overhead}, + {value, NormTime / EProfTime * 100}]}), + ct_event:notify(#event{name = benchmark_data, + data = [{name, cprof_overhead}, + {value, NormTime / CProfTime * 100}]}), + ct_event:notify(#event{name = benchmark_data, + data = [{name, cover_overhead}, + {value, NormTime / CoverTime * 100}]}). + +%% overhead(Config) -> +%% LogFile = filename:join(proplists:get_value(priv_dir, Config), "fprof.trace"), +%% SofsCopy = filename:join(proplists:get_value(data_dir, Config), "sofs_copy.erl"), +%% TC = fun() -> compile:file(SofsCopy, [binary]) end, +%% _Warmup = timer:tc(TC), + +%% [{ok,{EProfTime,{ok,sofs_copy,_}}} = eprof:profile([], timer, tc, [TC]) +%% || _ <- lists:seq(1,10)], +%% %% [fprof:apply(timer, tc, [TC], [{file, LogFile}]) || _ <- lists:seq(1,10)], +%% {FProfTime,{ok,sofs_copy,_}} = fprof:apply(timer, tc, [TC], [{file, LogFile}]), +%% {NormTime,{ok, sofs_copy, _}} = timer:tc(TC), + + %% ct:pal("FProf: ~p Norm: ~p Ratio: ~p",[FProfTime, NormTime, FProfTime / NormTime]). + +cprof_apply(M, F, A) -> + cprof:start(), + Res = apply(M, F, A), + cprof:stop(), + Res. + +cover_apply(M, F, A) -> + cover:start(), + catch cover:local_only(), + Modules = modules(), + [code:unstick_mod(Mod) || Mod <- Modules], + cover:compile_beam(Modules), + [code:stick_mod(Mod) || Mod <- Modules], + Res = apply(M, F, A), + cover:stop(), + Res. + +modules() -> + application:load(compiler), + {ok, CompilerModules} = application:get_key(compiler, modules), + %% Only cover compile a subset of the stdlib modules + StdlibModules = [erl_parse, erl_expand_records, erl_lint, gb_trees, gb_sets, sofs, + beam_lib, dict, epp, erl_anno, erl_bits, + orddict, ordsets, sets, string, unicode, unicode_util], + CompilerModules ++ StdlibModules. diff --git a/lib/tools/test/prof_bench_SUITE_data/sofs_copy.erl b/lib/tools/test/prof_bench_SUITE_data/sofs_copy.erl new file mode 100644 index 0000000000..2a9b19177e --- /dev/null +++ b/lib/tools/test/prof_bench_SUITE_data/sofs_copy.erl @@ -0,0 +1,2809 @@ +%% +%% %CopyrightBegin% +%% +%% Copyright Ericsson AB 2001-2017. 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. +%% 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. +%% +%% %CopyrightEnd% +%% +-module(sofs_copy). + +-export([from_term/1, from_term/2, from_external/2, empty_set/0, + is_type/1, set/1, set/2, from_sets/1, relation/1, relation/2, + a_function/1, a_function/2, family/1, family/2, + to_external/1, type/1, to_sets/1, no_elements/1, + specification/2, union/2, intersection/2, difference/2, + symdiff/2, symmetric_partition/2, product/1, product/2, + constant_function/2, is_equal/2, is_subset/2, is_sofs_set/1, + is_set/1, is_empty_set/1, is_disjoint/2]). + +-export([union/1, intersection/1, canonical_relation/1]). + +-export([relation_to_family/1, domain/1, range/1, field/1, + relative_product/1, relative_product/2, relative_product1/2, + converse/1, image/2, inverse_image/2, strict_relation/1, + weak_relation/1, extension/3, is_a_function/1]). + +-export([composite/2, inverse/1]). + +-export([restriction/2, restriction/3, drestriction/2, drestriction/3, + substitution/2, projection/2, partition/1, partition/2, + partition/3, multiple_relative_product/2, join/4]). + +-export([family_to_relation/1, family_specification/2, + union_of_family/1, intersection_of_family/1, + family_union/1, family_intersection/1, + family_domain/1, family_range/1, family_field/1, + family_union/2, family_intersection/2, family_difference/2, + partition_family/2, family_projection/2]). + +-export([family_to_digraph/1, family_to_digraph/2, + digraph_to_family/1, digraph_to_family/2]). + +%% Shorter names of some functions. +-export([fam2rel/1, rel2fam/1]). + +-import(lists, + [any/2, append/1, flatten/1, foreach/2, + keysort/2, last/1, map/2, mapfoldl/3, member/2, merge/2, + reverse/1, reverse/2, sort/1, umerge/1, umerge/2, usort/1]). + +-compile({inline, [{family_to_relation,1}, {relation_to_family,1}]}). + +-compile({inline, [{rel,2},{a_func,2},{fam,2},{term2set,2}]}). + +-compile({inline, [{external_fun,1},{element_type,1}]}). + +-compile({inline, + [{unify_types,2}, {match_types,2}, + {test_rel,3}, {symdiff,3}, + {subst,3}]}). + +-compile({inline, [{fam_binop,3}]}). + +%% Nope, no is_member, del_member or add_member. +%% +%% See also "Naive Set Theory" by Paul R. Halmos. +%% +%% By convention, erlang:error/1 is called from exported functions. + +-define(TAG, 'Set'). +-define(ORDTAG, 'OrdSet'). + +-record(?TAG, {data = [] :: list(), type = type :: term()}). +-record(?ORDTAG, {orddata = {} :: tuple() | atom(), + ordtype = type :: term()}). + +-define(LIST(S), (S)#?TAG.data). +-define(TYPE(S), (S)#?TAG.type). +-define(SET(L, T), #?TAG{data = L, type = T}). +-define(IS_SET(S), is_record(S, ?TAG)). +-define(IS_UNTYPED_SET(S), ?TYPE(S) =:= ?ANYTYPE). + +%% Ordered sets and atoms: +-define(ORDDATA(S), (S)#?ORDTAG.orddata). +-define(ORDTYPE(S), (S)#?ORDTAG.ordtype). +-define(ORDSET(L, T), #?ORDTAG{orddata = L, ordtype = T}). +-define(IS_ORDSET(S), is_record(S, ?ORDTAG)). +-define(ATOM_TYPE, atom). +-define(IS_ATOM_TYPE(T), is_atom(T)). % true for ?ANYTYPE... + +%% When IS_SET is true: +-define(ANYTYPE, '_'). +-define(BINREL(X, Y), {X, Y}). +-define(IS_RELATION(R), is_tuple(R)). +-define(REL_ARITY(R), tuple_size(R)). +-define(REL_TYPE(I, R), element(I, R)). +-define(SET_OF(X), [X]). +-define(IS_SET_OF(X), is_list(X)). +-define(FAMILY(X, Y), ?BINREL(X, ?SET_OF(Y))). + +-export_type([anyset/0, binary_relation/0, external_set/0, a_function/0, + family/0, relation/0, set_of_sets/0, set_fun/0, spec_fun/0, + type/0]). +-export_type([ordset/0, a_set/0]). + +-type(anyset() :: ordset() | a_set()). +-type(binary_relation() :: relation()). +-type(external_set() :: term()). +-type(a_function() :: relation()). +-type(family() :: a_function()). +-opaque(ordset() :: #?ORDTAG{}). +-type(relation() :: a_set()). +-opaque(a_set() :: #?TAG{}). +-type(set_of_sets() :: a_set()). +-type(set_fun() :: pos_integer() + | {external, fun((external_set()) -> external_set())} + | fun((anyset()) -> anyset())). +-type(spec_fun() :: {external, fun((external_set()) -> boolean())} + | fun((anyset()) -> boolean())). +-type(type() :: term()). + +-type(tuple_of(_T) :: tuple()). + +%% +%% Exported functions +%% + +%%% +%%% Create sets +%%% + +-spec(from_term(Term) -> AnySet when + AnySet :: anyset(), + Term :: term()). +from_term(T) -> + Type = case T of + _ when is_list(T) -> [?ANYTYPE]; + _ -> ?ANYTYPE + end, + try setify(T, Type) + catch _:_ -> erlang:error(badarg) + end. + +-spec(from_term(Term, Type) -> AnySet when + AnySet :: anyset(), + Term :: term(), + Type :: type()). +from_term(L, T) -> + case is_type(T) of + true -> + try setify(L, T) + catch _:_ -> erlang:error(badarg) + end; + false -> + erlang:error(badarg) + end. + +-spec(from_external(ExternalSet, Type) -> AnySet when + ExternalSet :: external_set(), + AnySet :: anyset(), + Type :: type()). +from_external(L, ?SET_OF(Type)) -> + ?SET(L, Type); +from_external(T, Type) -> + ?ORDSET(T, Type). + +-spec(empty_set() -> Set when + Set :: a_set()). +empty_set() -> + ?SET([], ?ANYTYPE). + +-spec(is_type(Term) -> Bool when + Bool :: boolean(), + Term :: term()). +is_type(Atom) when ?IS_ATOM_TYPE(Atom), Atom =/= ?ANYTYPE -> + true; +is_type(?SET_OF(T)) -> + is_element_type(T); +is_type(T) when tuple_size(T) > 0 -> + is_types(tuple_size(T), T); +is_type(_T) -> + false. + +-spec(set(Terms) -> Set when + Set :: a_set(), + Terms :: [term()]). +set(L) -> + try usort(L) of + SL -> ?SET(SL, ?ATOM_TYPE) + catch _:_ -> erlang:error(badarg) + end. + +-spec(set(Terms, Type) -> Set when + Set :: a_set(), + Terms :: [term()], + Type :: type()). +set(L, ?SET_OF(Type)) when ?IS_ATOM_TYPE(Type), Type =/= ?ANYTYPE -> + try usort(L) of + SL -> ?SET(SL, Type) + catch _:_ -> erlang:error(badarg) + end; +set(L, ?SET_OF(_) = T) -> + try setify(L, T) + catch _:_ -> erlang:error(badarg) + end; +set(_, _) -> + erlang:error(badarg). + +-spec(from_sets(ListOfSets) -> Set when + Set :: a_set(), + ListOfSets :: [anyset()]; + (TupleOfSets) -> Ordset when + Ordset :: ordset(), + TupleOfSets :: tuple_of(anyset())). +from_sets(Ss) when is_list(Ss) -> + case set_of_sets(Ss, [], ?ANYTYPE) of + {error, Error} -> + erlang:error(Error); + Set -> + Set + end; +from_sets(Tuple) when is_tuple(Tuple) -> + case ordset_of_sets(tuple_to_list(Tuple), [], []) of + error -> + erlang:error(badarg); + Set -> + Set + end; +from_sets(_) -> + erlang:error(badarg). + +-spec(relation(Tuples) -> Relation when + Relation :: relation(), + Tuples :: [tuple()]). +relation([]) -> + ?SET([], ?BINREL(?ATOM_TYPE, ?ATOM_TYPE)); +relation(Ts = [T | _]) when is_tuple(T) -> + try rel(Ts, tuple_size(T)) + catch _:_ -> erlang:error(badarg) + end; +relation(_) -> + erlang:error(badarg). + +-spec(relation(Tuples, Type) -> Relation when + N :: integer(), + Type :: N | type(), + Relation :: relation(), + Tuples :: [tuple()]). +relation(Ts, TS) -> + try rel(Ts, TS) + catch _:_ -> erlang:error(badarg) + end. + +-spec(a_function(Tuples) -> Function when + Function :: a_function(), + Tuples :: [tuple()]). +a_function(Ts) -> + try func(Ts, ?BINREL(?ATOM_TYPE, ?ATOM_TYPE)) of + Bad when is_atom(Bad) -> + erlang:error(Bad); + Set -> + Set + catch _:_ -> erlang:error(badarg) + end. + +-spec(a_function(Tuples, Type) -> Function when + Function :: a_function(), + Tuples :: [tuple()], + Type :: type()). +a_function(Ts, T) -> + try a_func(Ts, T) of + Bad when is_atom(Bad) -> + erlang:error(Bad); + Set -> + Set + catch _:_ -> erlang:error(badarg) + end. + +-spec(family(Tuples) -> Family when + Family :: family(), + Tuples :: [tuple()]). +family(Ts) -> + try fam2(Ts, ?FAMILY(?ATOM_TYPE, ?ATOM_TYPE)) of + Bad when is_atom(Bad) -> + erlang:error(Bad); + Set -> + Set + catch _:_ -> erlang:error(badarg) + end. + +-spec(family(Tuples, Type) -> Family when + Family :: family(), + Tuples :: [tuple()], + Type :: type()). +family(Ts, T) -> + try fam(Ts, T) of + Bad when is_atom(Bad) -> + erlang:error(Bad); + Set -> + Set + catch _:_ -> erlang:error(badarg) + end. + +%%% +%%% Functions on sets. +%%% + +-spec(to_external(AnySet) -> ExternalSet when + ExternalSet :: external_set(), + AnySet :: anyset()). +to_external(S) when ?IS_SET(S) -> + ?LIST(S); +to_external(S) when ?IS_ORDSET(S) -> + ?ORDDATA(S). + +-spec(type(AnySet) -> Type when + AnySet :: anyset(), + Type :: type()). +type(S) when ?IS_SET(S) -> + ?SET_OF(?TYPE(S)); +type(S) when ?IS_ORDSET(S) -> + ?ORDTYPE(S). + +-spec(to_sets(ASet) -> Sets when + ASet :: a_set() | ordset(), + Sets :: tuple_of(AnySet) | [AnySet], + AnySet :: anyset()). +to_sets(S) when ?IS_SET(S) -> + case ?TYPE(S) of + ?SET_OF(Type) -> list_of_sets(?LIST(S), Type, []); + Type -> list_of_ordsets(?LIST(S), Type, []) + end; +to_sets(S) when ?IS_ORDSET(S), is_tuple(?ORDTYPE(S)) -> + tuple_of_sets(tuple_to_list(?ORDDATA(S)), tuple_to_list(?ORDTYPE(S)), []); +to_sets(S) when ?IS_ORDSET(S) -> + erlang:error(badarg). + +-spec(no_elements(ASet) -> NoElements when + ASet :: a_set() | ordset(), + NoElements :: non_neg_integer()). +no_elements(S) when ?IS_SET(S) -> + length(?LIST(S)); +no_elements(S) when ?IS_ORDSET(S), is_tuple(?ORDTYPE(S)) -> + tuple_size(?ORDDATA(S)); +no_elements(S) when ?IS_ORDSET(S) -> + erlang:error(badarg). + +-spec(specification(Fun, Set1) -> Set2 when + Fun :: spec_fun(), + Set1 :: a_set(), + Set2 :: a_set()). +specification(Fun, S) when ?IS_SET(S) -> + Type = ?TYPE(S), + R = case external_fun(Fun) of + false -> + spec(?LIST(S), Fun, element_type(Type), []); + XFun -> + specification(?LIST(S), XFun, []) + end, + case R of + SL when is_list(SL) -> + ?SET(SL, Type); + Bad -> + erlang:error(Bad) + end. + +-spec(union(Set1, Set2) -> Set3 when + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set()). +union(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case unify_types(?TYPE(S1), ?TYPE(S2)) of + [] -> erlang:error(type_mismatch); + Type -> ?SET(umerge(?LIST(S1), ?LIST(S2)), Type) + end. + +-spec(intersection(Set1, Set2) -> Set3 when + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set()). +intersection(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case unify_types(?TYPE(S1), ?TYPE(S2)) of + [] -> erlang:error(type_mismatch); + Type -> ?SET(intersection(?LIST(S1), ?LIST(S2), []), Type) + end. + +-spec(difference(Set1, Set2) -> Set3 when + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set()). +difference(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case unify_types(?TYPE(S1), ?TYPE(S2)) of + [] -> erlang:error(type_mismatch); + Type -> ?SET(difference(?LIST(S1), ?LIST(S2), []), Type) + end. + +-spec(symdiff(Set1, Set2) -> Set3 when + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set()). +symdiff(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case unify_types(?TYPE(S1), ?TYPE(S2)) of + [] -> erlang:error(type_mismatch); + Type -> ?SET(symdiff(?LIST(S1), ?LIST(S2), []), Type) + end. + +-spec(symmetric_partition(Set1, Set2) -> {Set3, Set4, Set5} when + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set(), + Set4 :: a_set(), + Set5 :: a_set()). +symmetric_partition(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case unify_types(?TYPE(S1), ?TYPE(S2)) of + [] -> erlang:error(type_mismatch); + Type -> sympart(?LIST(S1), ?LIST(S2), [], [], [], Type) + end. + +-spec(product(Set1, Set2) -> BinRel when + BinRel :: binary_relation(), + Set1 :: a_set(), + Set2 :: a_set()). +product(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + if + ?TYPE(S1) =:= ?ANYTYPE -> S1; + ?TYPE(S2) =:= ?ANYTYPE -> S2; + true -> + F = fun(E) -> {0, E} end, + T = ?BINREL(?TYPE(S1), ?TYPE(S2)), + ?SET(relprod(map(F, ?LIST(S1)), map(F, ?LIST(S2))), T) + end. + +-spec(product(TupleOfSets) -> Relation when + Relation :: relation(), + TupleOfSets :: tuple_of(a_set())). +product({S1, S2}) -> + product(S1, S2); +product(T) when is_tuple(T) -> + Ss = tuple_to_list(T), + try sets_to_list(Ss) of + [] -> + erlang:error(badarg); + L -> + Type = types(Ss, []), + case member([], L) of + true -> + empty_set(); + false -> + ?SET(reverse(prod(L, [], [])), Type) + end + catch _:_ -> erlang:error(badarg) + end. + +-spec(constant_function(Set, AnySet) -> Function when + AnySet :: anyset(), + Function :: a_function(), + Set :: a_set()). +constant_function(S, E) when ?IS_SET(S) -> + case {?TYPE(S), is_sofs_set(E)} of + {?ANYTYPE, true} -> S; + {Type, true} -> + NType = ?BINREL(Type, type(E)), + ?SET(constant_function(?LIST(S), to_external(E), []), NType); + _ -> erlang:error(badarg) + end; +constant_function(S, _) when ?IS_ORDSET(S) -> + erlang:error(badarg). + +-spec(is_equal(AnySet1, AnySet2) -> Bool when + AnySet1 :: anyset(), + AnySet2 :: anyset(), + Bool :: boolean()). +is_equal(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case match_types(?TYPE(S1), ?TYPE(S2)) of + true -> ?LIST(S1) == ?LIST(S2); + false -> erlang:error(type_mismatch) + end; +is_equal(S1, S2) when ?IS_ORDSET(S1), ?IS_ORDSET(S2) -> + case match_types(?ORDTYPE(S1), ?ORDTYPE(S2)) of + true -> ?ORDDATA(S1) == ?ORDDATA(S2); + false -> erlang:error(type_mismatch) + end; +is_equal(S1, S2) when ?IS_SET(S1), ?IS_ORDSET(S2) -> + erlang:error(type_mismatch); +is_equal(S1, S2) when ?IS_ORDSET(S1), ?IS_SET(S2) -> + erlang:error(type_mismatch). + +-spec(is_subset(Set1, Set2) -> Bool when + Bool :: boolean(), + Set1 :: a_set(), + Set2 :: a_set()). +is_subset(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case match_types(?TYPE(S1), ?TYPE(S2)) of + true -> subset(?LIST(S1), ?LIST(S2)); + false -> erlang:error(type_mismatch) + end. + +-spec(is_sofs_set(Term) -> Bool when + Bool :: boolean(), + Term :: term()). +is_sofs_set(S) when ?IS_SET(S) -> + true; +is_sofs_set(S) when ?IS_ORDSET(S) -> + true; +is_sofs_set(_S) -> + false. + +-spec(is_set(AnySet) -> Bool when + AnySet :: anyset(), + Bool :: boolean()). +is_set(S) when ?IS_SET(S) -> + true; +is_set(S) when ?IS_ORDSET(S) -> + false. + +-spec(is_empty_set(AnySet) -> Bool when + AnySet :: anyset(), + Bool :: boolean()). +is_empty_set(S) when ?IS_SET(S) -> + ?LIST(S) =:= []; +is_empty_set(S) when ?IS_ORDSET(S) -> + false. + +-spec(is_disjoint(Set1, Set2) -> Bool when + Bool :: boolean(), + Set1 :: a_set(), + Set2 :: a_set()). +is_disjoint(S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + case match_types(?TYPE(S1), ?TYPE(S2)) of + true -> + case ?LIST(S1) of + [] -> true; + [A | As] -> disjoint(?LIST(S2), A, As) + end; + false -> erlang:error(type_mismatch) + end. + +%%% +%%% Functions on set-of-sets. +%%% + +-spec(union(SetOfSets) -> Set when + Set :: a_set(), + SetOfSets :: set_of_sets()). +union(Sets) when ?IS_SET(Sets) -> + case ?TYPE(Sets) of + ?SET_OF(Type) -> ?SET(lunion(?LIST(Sets)), Type); + ?ANYTYPE -> Sets; + _ -> erlang:error(badarg) + end. + +-spec(intersection(SetOfSets) -> Set when + Set :: a_set(), + SetOfSets :: set_of_sets()). +intersection(Sets) when ?IS_SET(Sets) -> + case ?LIST(Sets) of + [] -> erlang:error(badarg); + [L | Ls] -> + case ?TYPE(Sets) of + ?SET_OF(Type) -> + ?SET(lintersection(Ls, L), Type); + _ -> erlang:error(badarg) + end + end. + +-spec(canonical_relation(SetOfSets) -> BinRel when + BinRel :: binary_relation(), + SetOfSets :: set_of_sets()). +canonical_relation(Sets) when ?IS_SET(Sets) -> + ST = ?TYPE(Sets), + case ST of + ?SET_OF(?ANYTYPE) -> empty_set(); + ?SET_OF(Type) -> + ?SET(can_rel(?LIST(Sets), []), ?BINREL(Type, ST)); + ?ANYTYPE -> Sets; + _ -> erlang:error(badarg) + end. + +%%% +%%% Functions on binary relations only. +%%% + +-spec(rel2fam(BinRel) -> Family when + Family :: family(), + BinRel :: binary_relation()). +rel2fam(R) -> + relation_to_family(R). + +-spec(relation_to_family(BinRel) -> Family when + Family :: family(), + BinRel :: binary_relation()). +%% Inlined. +relation_to_family(R) when ?IS_SET(R) -> + case ?TYPE(R) of + ?BINREL(DT, RT) -> + ?SET(rel2family(?LIST(R)), ?FAMILY(DT, RT)); + ?ANYTYPE -> R; + _Else -> erlang:error(badarg) + end. + +-spec(domain(BinRel) -> Set when + BinRel :: binary_relation(), + Set :: a_set()). +domain(R) when ?IS_SET(R) -> + case ?TYPE(R) of + ?BINREL(DT, _) -> ?SET(dom(?LIST(R)), DT); + ?ANYTYPE -> R; + _Else -> erlang:error(badarg) + end. + +-spec(range(BinRel) -> Set when + BinRel :: binary_relation(), + Set :: a_set()). +range(R) when ?IS_SET(R) -> + case ?TYPE(R) of + ?BINREL(_, RT) -> ?SET(ran(?LIST(R), []), RT); + ?ANYTYPE -> R; + _ -> erlang:error(badarg) + end. + +-spec(field(BinRel) -> Set when + BinRel :: binary_relation(), + Set :: a_set()). +%% In "Introduction to LOGIC", Suppes defines the field of a binary +%% relation to be the union of the domain and the range (or +%% counterdomain). +field(R) -> + union(domain(R), range(R)). + +-spec(relative_product(ListOfBinRels) -> BinRel2 when + ListOfBinRels :: [BinRel, ...], + BinRel :: binary_relation(), + BinRel2 :: binary_relation()). +%% The following clause is kept for backward compatibility. +%% The list is due to Dialyzer's specs. +relative_product(RT) when is_tuple(RT) -> + relative_product(tuple_to_list(RT)); +relative_product(RL) when is_list(RL) -> + case relprod_n(RL, foo, false, false) of + {error, Reason} -> + erlang:error(Reason); + Reply -> + Reply + end. + +-spec(relative_product(ListOfBinRels, BinRel1) -> BinRel2 when + ListOfBinRels :: [BinRel, ...], + BinRel :: binary_relation(), + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation(); + (BinRel1, BinRel2) -> BinRel3 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation(), + BinRel3 :: binary_relation()). +relative_product(R1, R2) when ?IS_SET(R1), ?IS_SET(R2) -> + relative_product1(converse(R1), R2); +%% The following clause is kept for backward compatibility. +%% The list is due to Dialyzer's specs. +relative_product(RT, R) when is_tuple(RT), ?IS_SET(R) -> + relative_product(tuple_to_list(RT), R); +relative_product(RL, R) when is_list(RL), ?IS_SET(R) -> + EmptyR = case ?TYPE(R) of + ?BINREL(_, _) -> ?LIST(R) =:= []; + ?ANYTYPE -> true; + _ -> erlang:error(badarg) + end, + case relprod_n(RL, R, EmptyR, true) of + {error, Reason} -> + erlang:error(Reason); + Reply -> + Reply + end. + +-spec(relative_product1(BinRel1, BinRel2) -> BinRel3 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation(), + BinRel3 :: binary_relation()). +relative_product1(R1, R2) when ?IS_SET(R1), ?IS_SET(R2) -> + {DTR1, RTR1} = case ?TYPE(R1) of + ?BINREL(_, _) = R1T -> R1T; + ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE}; + _ -> erlang:error(badarg) + end, + {DTR2, RTR2} = case ?TYPE(R2) of + ?BINREL(_, _) = R2T -> R2T; + ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE}; + _ -> erlang:error(badarg) + end, + case match_types(DTR1, DTR2) of + true when DTR1 =:= ?ANYTYPE -> R1; + true when DTR2 =:= ?ANYTYPE -> R2; + true -> ?SET(relprod(?LIST(R1), ?LIST(R2)), ?BINREL(RTR1, RTR2)); + false -> erlang:error(type_mismatch) + end. + +-spec(converse(BinRel1) -> BinRel2 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation()). +converse(R) when ?IS_SET(R) -> + case ?TYPE(R) of + ?BINREL(DT, RT) -> ?SET(converse(?LIST(R), []), ?BINREL(RT, DT)); + ?ANYTYPE -> R; + _ -> erlang:error(badarg) + end. + +-spec(image(BinRel, Set1) -> Set2 when + BinRel :: binary_relation(), + Set1 :: a_set(), + Set2 :: a_set()). +image(R, S) when ?IS_SET(R), ?IS_SET(S) -> + case ?TYPE(R) of + ?BINREL(DT, RT) -> + case match_types(DT, ?TYPE(S)) of + true -> + ?SET(usort(restrict(?LIST(S), ?LIST(R))), RT); + false -> + erlang:error(type_mismatch) + end; + ?ANYTYPE -> R; + _ -> erlang:error(badarg) + end. + +-spec(inverse_image(BinRel, Set1) -> Set2 when + BinRel :: binary_relation(), + Set1 :: a_set(), + Set2 :: a_set()). +inverse_image(R, S) when ?IS_SET(R), ?IS_SET(S) -> + case ?TYPE(R) of + ?BINREL(DT, RT) -> + case match_types(RT, ?TYPE(S)) of + true -> + NL = restrict(?LIST(S), converse(?LIST(R), [])), + ?SET(usort(NL), DT); + false -> + erlang:error(type_mismatch) + end; + ?ANYTYPE -> R; + _ -> erlang:error(badarg) + end. + +-spec(strict_relation(BinRel1) -> BinRel2 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation()). +strict_relation(R) when ?IS_SET(R) -> + case ?TYPE(R) of + Type = ?BINREL(_, _) -> + ?SET(strict(?LIST(R), []), Type); + ?ANYTYPE -> R; + _ -> erlang:error(badarg) + end. + +-spec(weak_relation(BinRel1) -> BinRel2 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation()). +weak_relation(R) when ?IS_SET(R) -> + case ?TYPE(R) of + ?BINREL(DT, RT) -> + case unify_types(DT, RT) of + [] -> + erlang:error(badarg); + Type -> + ?SET(weak(?LIST(R)), ?BINREL(Type, Type)) + end; + ?ANYTYPE -> R; + _ -> erlang:error(badarg) + end. + +-spec(extension(BinRel1, Set, AnySet) -> BinRel2 when + AnySet :: anyset(), + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation(), + Set :: a_set()). +extension(R, S, E) when ?IS_SET(R), ?IS_SET(S) -> + case {?TYPE(R), ?TYPE(S), is_sofs_set(E)} of + {T=?BINREL(DT, RT), ST, true} -> + case match_types(DT, ST) and match_types(RT, type(E)) of + false -> + erlang:error(type_mismatch); + true -> + RL = ?LIST(R), + case extc([], ?LIST(S), to_external(E), RL) of + [] -> + R; + L -> + ?SET(merge(RL, reverse(L)), T) + end + end; + {?ANYTYPE, ?ANYTYPE, true} -> + R; + {?ANYTYPE, ST, true} -> + case type(E) of + ?SET_OF(?ANYTYPE) -> + R; + ET -> + ?SET([], ?BINREL(ST, ET)) + end; + {_, _, true} -> + erlang:error(badarg) + end. + +-spec(is_a_function(BinRel) -> Bool when + Bool :: boolean(), + BinRel :: binary_relation()). +is_a_function(R) when ?IS_SET(R) -> + case ?TYPE(R) of + ?BINREL(_, _) -> + case ?LIST(R) of + [] -> true; + [{V,_} | Es] -> is_a_func(Es, V) + end; + ?ANYTYPE -> true; + _ -> erlang:error(badarg) + end. + +-spec(restriction(BinRel1, Set) -> BinRel2 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation(), + Set :: a_set()). +restriction(Relation, Set) -> + restriction(1, Relation, Set). + +-spec(drestriction(BinRel1, Set) -> BinRel2 when + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation(), + Set :: a_set()). +drestriction(Relation, Set) -> + drestriction(1, Relation, Set). + +%%% +%%% Functions on functions only. +%%% + +-spec(composite(Function1, Function2) -> Function3 when + Function1 :: a_function(), + Function2 :: a_function(), + Function3 :: a_function()). +composite(Fn1, Fn2) when ?IS_SET(Fn1), ?IS_SET(Fn2) -> + ?BINREL(DTF1, RTF1) = case ?TYPE(Fn1)of + ?BINREL(_, _) = F1T -> F1T; + ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE}; + _ -> erlang:error(badarg) + end, + ?BINREL(DTF2, RTF2) = case ?TYPE(Fn2) of + ?BINREL(_, _) = F2T -> F2T; + ?ANYTYPE -> {?ANYTYPE, ?ANYTYPE}; + _ -> erlang:error(badarg) + end, + case match_types(RTF1, DTF2) of + true when DTF1 =:= ?ANYTYPE -> Fn1; + true when DTF2 =:= ?ANYTYPE -> Fn2; + true -> + case comp(?LIST(Fn1), ?LIST(Fn2)) of + SL when is_list(SL) -> + ?SET(sort(SL), ?BINREL(DTF1, RTF2)); + Bad -> + erlang:error(Bad) + end; + false -> erlang:error(type_mismatch) + end. + +-spec(inverse(Function1) -> Function2 when + Function1 :: a_function(), + Function2 :: a_function()). +inverse(Fn) when ?IS_SET(Fn) -> + case ?TYPE(Fn) of + ?BINREL(DT, RT) -> + case inverse1(?LIST(Fn)) of + SL when is_list(SL) -> + ?SET(SL, ?BINREL(RT, DT)); + Bad -> + erlang:error(Bad) + end; + ?ANYTYPE -> Fn; + _ -> erlang:error(badarg) + end. + +%%% +%%% Functions on relations (binary or other). +%%% + +-spec(restriction(SetFun, Set1, Set2) -> Set3 when + SetFun :: set_fun(), + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set()). +%% Equivalent to range(restriction(inverse(substitution(Fun, S1)), S2)). +restriction(I, R, S) when is_integer(I), ?IS_SET(R), ?IS_SET(S) -> + RT = ?TYPE(R), + ST = ?TYPE(S), + case check_for_sort(RT, I) of + empty -> + R; + error -> + erlang:error(badarg); + Sort -> + RL = ?LIST(R), + case {match_types(?REL_TYPE(I, RT), ST), ?LIST(S)} of + {true, _SL} when RL =:= [] -> + R; + {true, []} -> + ?SET([], RT); + {true, [E | Es]} when Sort =:= false -> % I =:= 1 + ?SET(reverse(restrict_n(I, RL, E, Es, [])), RT); + {true, [E | Es]} -> + ?SET(sort(restrict_n(I, keysort(I, RL), E, Es, [])), RT); + {false, _SL} -> + erlang:error(type_mismatch) + end + end; +restriction(SetFun, S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + Type1 = ?TYPE(S1), + Type2 = ?TYPE(S2), + SL1 = ?LIST(S1), + case external_fun(SetFun) of + false when Type2 =:= ?ANYTYPE -> + S2; + false -> + case subst(SL1, SetFun, element_type(Type1)) of + {NSL, NewType} -> % NewType can be ?ANYTYPE + case match_types(NewType, Type2) of + true -> + NL = sort(restrict(?LIST(S2), converse(NSL, []))), + ?SET(NL, Type1); + false -> + erlang:error(type_mismatch) + end; + Bad -> + erlang:error(Bad) + end; + _ when Type1 =:= ?ANYTYPE -> + S1; + _XFun when ?IS_SET_OF(Type1) -> + erlang:error(badarg); + XFun -> + FunT = XFun(Type1), + try check_fun(Type1, XFun, FunT) of + Sort -> + case match_types(FunT, Type2) of + true -> + R1 = inverse_substitution(SL1, XFun, Sort), + ?SET(sort(Sort, restrict(?LIST(S2), R1)), Type1); + false -> + erlang:error(type_mismatch) + end + catch _:_ -> erlang:error(badarg) + end + end. + +-spec(drestriction(SetFun, Set1, Set2) -> Set3 when + SetFun :: set_fun(), + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set()). +drestriction(I, R, S) when is_integer(I), ?IS_SET(R), ?IS_SET(S) -> + RT = ?TYPE(R), + ST = ?TYPE(S), + case check_for_sort(RT, I) of + empty -> + R; + error -> + erlang:error(badarg); + Sort -> + RL = ?LIST(R), + case {match_types(?REL_TYPE(I, RT), ST), ?LIST(S)} of + {true, []} -> + R; + {true, _SL} when RL =:= [] -> + R; + {true, [E | Es]} when Sort =:= false -> % I =:= 1 + ?SET(diff_restrict_n(I, RL, E, Es, []), RT); + {true, [E | Es]} -> + ?SET(diff_restrict_n(I, keysort(I, RL), E, Es, []), RT); + {false, _SL} -> + erlang:error(type_mismatch) + end + end; +drestriction(SetFun, S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + Type1 = ?TYPE(S1), + Type2 = ?TYPE(S2), + SL1 = ?LIST(S1), + case external_fun(SetFun) of + false when Type2 =:= ?ANYTYPE -> + S1; + false -> + case subst(SL1, SetFun, element_type(Type1)) of + {NSL, NewType} -> % NewType can be ?ANYTYPE + case match_types(NewType, Type2) of + true -> + SL2 = ?LIST(S2), + NL = sort(diff_restrict(SL2, converse(NSL, []))), + ?SET(NL, Type1); + false -> + erlang:error(type_mismatch) + end; + Bad -> + erlang:error(Bad) + end; + _ when Type1 =:= ?ANYTYPE -> + S1; + _XFun when ?IS_SET_OF(Type1) -> + erlang:error(badarg); + XFun -> + FunT = XFun(Type1), + try check_fun(Type1, XFun, FunT) of + Sort -> + case match_types(FunT, Type2) of + true -> + R1 = inverse_substitution(SL1, XFun, Sort), + SL2 = ?LIST(S2), + ?SET(sort(Sort, diff_restrict(SL2, R1)), Type1); + false -> + erlang:error(type_mismatch) + end + catch _:_ -> erlang:error(badarg) + end + end. + +-spec(projection(SetFun, Set1) -> Set2 when + SetFun :: set_fun(), + Set1 :: a_set(), + Set2 :: a_set()). +projection(I, Set) when is_integer(I), ?IS_SET(Set) -> + Type = ?TYPE(Set), + case check_for_sort(Type, I) of + empty -> + Set; + error -> + erlang:error(badarg); + _ when I =:= 1 -> + ?SET(projection1(?LIST(Set)), ?REL_TYPE(I, Type)); + _ -> + ?SET(projection_n(?LIST(Set), I, []), ?REL_TYPE(I, Type)) + end; +projection(Fun, Set) -> + range(substitution(Fun, Set)). + +-spec(substitution(SetFun, Set1) -> Set2 when + SetFun :: set_fun(), + Set1 :: a_set(), + Set2 :: a_set()). +substitution(I, Set) when is_integer(I), ?IS_SET(Set) -> + Type = ?TYPE(Set), + case check_for_sort(Type, I) of + empty -> + Set; + error -> + erlang:error(badarg); + _Sort -> + NType = ?REL_TYPE(I, Type), + NSL = substitute_element(?LIST(Set), I, []), + ?SET(NSL, ?BINREL(Type, NType)) + end; +substitution(SetFun, Set) when ?IS_SET(Set) -> + Type = ?TYPE(Set), + L = ?LIST(Set), + case external_fun(SetFun) of + false when L =/= [] -> + case subst(L, SetFun, element_type(Type)) of + {SL, NewType} -> + ?SET(reverse(SL), ?BINREL(Type, NewType)); + Bad -> + erlang:error(Bad) + end; + false -> + empty_set(); + _ when Type =:= ?ANYTYPE -> + empty_set(); + _XFun when ?IS_SET_OF(Type) -> + erlang:error(badarg); + XFun -> + FunT = XFun(Type), + try check_fun(Type, XFun, FunT) of + _Sort -> + SL = substitute(L, XFun, []), + ?SET(SL, ?BINREL(Type, FunT)) + catch _:_ -> erlang:error(badarg) + end + end. + +-spec(partition(SetOfSets) -> Partition when + SetOfSets :: set_of_sets(), + Partition :: a_set()). +partition(Sets) -> + F1 = relation_to_family(canonical_relation(Sets)), + F2 = relation_to_family(converse(F1)), + range(F2). + +-spec(partition(SetFun, Set) -> Partition when + SetFun :: set_fun(), + Partition :: a_set(), + Set :: a_set()). +partition(I, Set) when is_integer(I), ?IS_SET(Set) -> + Type = ?TYPE(Set), + case check_for_sort(Type, I) of + empty -> + Set; + error -> + erlang:error(badarg); + false -> % I =:= 1 + ?SET(partition_n(I, ?LIST(Set)), ?SET_OF(Type)); + true -> + ?SET(partition_n(I, keysort(I, ?LIST(Set))), ?SET_OF(Type)) + end; +partition(Fun, Set) -> + range(partition_family(Fun, Set)). + +-spec(partition(SetFun, Set1, Set2) -> {Set3, Set4} when + SetFun :: set_fun(), + Set1 :: a_set(), + Set2 :: a_set(), + Set3 :: a_set(), + Set4 :: a_set()). +partition(I, R, S) when is_integer(I), ?IS_SET(R), ?IS_SET(S) -> + RT = ?TYPE(R), + ST = ?TYPE(S), + case check_for_sort(RT, I) of + empty -> + {R, R}; + error -> + erlang:error(badarg); + Sort -> + RL = ?LIST(R), + case {match_types(?REL_TYPE(I, RT), ST), ?LIST(S)} of + {true, _SL} when RL =:= [] -> + {R, R}; + {true, []} -> + {?SET([], RT), R}; + {true, [E | Es]} when Sort =:= false -> % I =:= 1 + [L1 | L2] = partition3_n(I, RL, E, Es, [], []), + {?SET(L1, RT), ?SET(L2, RT)}; + {true, [E | Es]} -> + [L1 | L2] = partition3_n(I, keysort(I,RL), E, Es, [], []), + {?SET(L1, RT), ?SET(L2, RT)}; + {false, _SL} -> + erlang:error(type_mismatch) + end + end; +partition(SetFun, S1, S2) when ?IS_SET(S1), ?IS_SET(S2) -> + Type1 = ?TYPE(S1), + Type2 = ?TYPE(S2), + SL1 = ?LIST(S1), + case external_fun(SetFun) of + false when Type2 =:= ?ANYTYPE -> + {S2, S1}; + false -> + case subst(SL1, SetFun, element_type(Type1)) of + {NSL, NewType} -> % NewType can be ?ANYTYPE + case match_types(NewType, Type2) of + true -> + R1 = converse(NSL, []), + [L1 | L2] = partition3(?LIST(S2), R1), + {?SET(sort(L1), Type1), ?SET(sort(L2), Type1)}; + false -> + erlang:error(type_mismatch) + end; + Bad -> + erlang:error(Bad) + end; + _ when Type1 =:= ?ANYTYPE -> + {S1, S1}; + _XFun when ?IS_SET_OF(Type1) -> + erlang:error(badarg); + XFun -> + FunT = XFun(Type1), + try check_fun(Type1, XFun, FunT) of + Sort -> + case match_types(FunT, Type2) of + true -> + R1 = inverse_substitution(SL1, XFun, Sort), + [L1 | L2] = partition3(?LIST(S2), R1), + {?SET(sort(L1), Type1), ?SET(sort(L2), Type1)}; + false -> + erlang:error(type_mismatch) + end + catch _:_ -> erlang:error(badarg) + end + end. + +-spec(multiple_relative_product(TupleOfBinRels, BinRel1) -> BinRel2 when + TupleOfBinRels :: tuple_of(BinRel), + BinRel :: binary_relation(), + BinRel1 :: binary_relation(), + BinRel2 :: binary_relation()). +multiple_relative_product(T, R) when is_tuple(T), ?IS_SET(R) -> + case test_rel(R, tuple_size(T), eq) of + true when ?TYPE(R) =:= ?ANYTYPE -> + empty_set(); + true -> + MProd = mul_relprod(tuple_to_list(T), 1, R), + relative_product(MProd); + false -> + erlang:error(badarg) + end. + +-spec(join(Relation1, I, Relation2, J) -> Relation3 when + Relation1 :: relation(), + Relation2 :: relation(), + Relation3 :: relation(), + I :: pos_integer(), + J :: pos_integer()). +join(R1, I1, R2, I2) + when ?IS_SET(R1), ?IS_SET(R2), is_integer(I1), is_integer(I2) -> + case test_rel(R1, I1, lte) and test_rel(R2, I2, lte) of + false -> erlang:error(badarg); + true when ?TYPE(R1) =:= ?ANYTYPE -> R1; + true when ?TYPE(R2) =:= ?ANYTYPE -> R2; + true -> + L1 = ?LIST(raise_element(R1, I1)), + L2 = ?LIST(raise_element(R2, I2)), + T = relprod1(L1, L2), + F = case (I1 =:= 1) and (I2 =:= 1) of + true -> + fun({X,Y}) -> join_element(X, Y) end; + false -> + fun({X,Y}) -> + list_to_tuple(join_element(X, Y, I2)) + end + end, + ?SET(replace(T, F, []), F({?TYPE(R1), ?TYPE(R2)})) + end. + +%% Inlined. +test_rel(R, I, C) -> + case ?TYPE(R) of + Rel when ?IS_RELATION(Rel), C =:= eq, I =:= ?REL_ARITY(Rel) -> true; + Rel when ?IS_RELATION(Rel), C =:= lte, I>=1, I =< ?REL_ARITY(Rel) -> + true; + ?ANYTYPE -> true; + _ -> false + end. + +%%% +%%% Family functions +%%% + +-spec(fam2rel(Family) -> BinRel when + Family :: family(), + BinRel :: binary_relation()). +fam2rel(F) -> + family_to_relation(F). + +-spec(family_to_relation(Family) -> BinRel when + Family :: family(), + BinRel :: binary_relation()). +%% Inlined. +family_to_relation(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(DT, RT) -> + ?SET(family2rel(?LIST(F), []), ?BINREL(DT, RT)); + ?ANYTYPE -> F; + _ -> erlang:error(badarg) + end. + +-spec(family_specification(Fun, Family1) -> Family2 when + Fun :: spec_fun(), + Family1 :: family(), + Family2 :: family()). +family_specification(Fun, F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(_DT, Type) = FType -> + R = case external_fun(Fun) of + false -> + fam_spec(?LIST(F), Fun, Type, []); + XFun -> + fam_specification(?LIST(F), XFun, []) + end, + case R of + SL when is_list(SL) -> + ?SET(SL, FType); + Bad -> + erlang:error(Bad) + end; + ?ANYTYPE -> F; + _ -> erlang:error(badarg) + end. + +-spec(union_of_family(Family) -> Set when + Family :: family(), + Set :: a_set()). +union_of_family(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(_DT, Type) -> + ?SET(un_of_fam(?LIST(F), []), Type); + ?ANYTYPE -> F; + _ -> erlang:error(badarg) + end. + +-spec(intersection_of_family(Family) -> Set when + Family :: family(), + Set :: a_set()). +intersection_of_family(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(_DT, Type) -> + case int_of_fam(?LIST(F)) of + FU when is_list(FU) -> + ?SET(FU, Type); + Bad -> + erlang:error(Bad) + end; + _ -> erlang:error(badarg) + end. + +-spec(family_union(Family1) -> Family2 when + Family1 :: family(), + Family2 :: family()). +family_union(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(DT, ?SET_OF(Type)) -> + ?SET(fam_un(?LIST(F), []), ?FAMILY(DT, Type)); + ?ANYTYPE -> F; + _ -> erlang:error(badarg) + end. + +-spec(family_intersection(Family1) -> Family2 when + Family1 :: family(), + Family2 :: family()). +family_intersection(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(DT, ?SET_OF(Type)) -> + case fam_int(?LIST(F), []) of + FU when is_list(FU) -> + ?SET(FU, ?FAMILY(DT, Type)); + Bad -> + erlang:error(Bad) + end; + ?ANYTYPE -> F; + _ -> erlang:error(badarg) + end. + +-spec(family_domain(Family1) -> Family2 when + Family1 :: family(), + Family2 :: family()). +family_domain(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(FDT, ?BINREL(DT, _)) -> + ?SET(fam_dom(?LIST(F), []), ?FAMILY(FDT, DT)); + ?ANYTYPE -> F; + ?FAMILY(_, ?ANYTYPE) -> F; + _ -> erlang:error(badarg) + end. + +-spec(family_range(Family1) -> Family2 when + Family1 :: family(), + Family2 :: family()). +family_range(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(DT, ?BINREL(_, RT)) -> + ?SET(fam_ran(?LIST(F), []), ?FAMILY(DT, RT)); + ?ANYTYPE -> F; + ?FAMILY(_, ?ANYTYPE) -> F; + _ -> erlang:error(badarg) + end. + +-spec(family_field(Family1) -> Family2 when + Family1 :: family(), + Family2 :: family()). +family_field(F) -> + family_union(family_domain(F), family_range(F)). + +-spec(family_union(Family1, Family2) -> Family3 when + Family1 :: family(), + Family2 :: family(), + Family3 :: family()). +family_union(F1, F2) -> + fam_binop(F1, F2, fun fam_union/3). + +-spec(family_intersection(Family1, Family2) -> Family3 when + Family1 :: family(), + Family2 :: family(), + Family3 :: family()). +family_intersection(F1, F2) -> + fam_binop(F1, F2, fun fam_intersect/3). + +-spec(family_difference(Family1, Family2) -> Family3 when + Family1 :: family(), + Family2 :: family(), + Family3 :: family()). +family_difference(F1, F2) -> + fam_binop(F1, F2, fun fam_difference/3). + +%% Inlined. +fam_binop(F1, F2, FF) when ?IS_SET(F1), ?IS_SET(F2) -> + case unify_types(?TYPE(F1), ?TYPE(F2)) of + [] -> + erlang:error(type_mismatch); + ?ANYTYPE -> + F1; + Type = ?FAMILY(_, _) -> + ?SET(FF(?LIST(F1), ?LIST(F2), []), Type); + _ -> erlang:error(badarg) + end. + +-spec(partition_family(SetFun, Set) -> Family when + Family :: family(), + SetFun :: set_fun(), + Set :: a_set()). +partition_family(I, Set) when is_integer(I), ?IS_SET(Set) -> + Type = ?TYPE(Set), + case check_for_sort(Type, I) of + empty -> + Set; + error -> + erlang:error(badarg); + false -> % when I =:= 1 + ?SET(fam_partition_n(I, ?LIST(Set)), + ?BINREL(?REL_TYPE(I, Type), ?SET_OF(Type))); + true -> + ?SET(fam_partition_n(I, keysort(I, ?LIST(Set))), + ?BINREL(?REL_TYPE(I, Type), ?SET_OF(Type))) + end; +partition_family(SetFun, Set) when ?IS_SET(Set) -> + Type = ?TYPE(Set), + SL = ?LIST(Set), + case external_fun(SetFun) of + false when SL =/= [] -> + case subst(SL, SetFun, element_type(Type)) of + {NSL, NewType} -> + P = fam_partition(converse(NSL, []), true), + ?SET(reverse(P), ?BINREL(NewType, ?SET_OF(Type))); + Bad -> + erlang:error(Bad) + end; + false -> + empty_set(); + _ when Type =:= ?ANYTYPE -> + empty_set(); + _XFun when ?IS_SET_OF(Type) -> + erlang:error(badarg); + XFun -> + DType = XFun(Type), + try check_fun(Type, XFun, DType) of + Sort -> + Ts = inverse_substitution(?LIST(Set), XFun, Sort), + P = fam_partition(Ts, Sort), + ?SET(reverse(P), ?BINREL(DType, ?SET_OF(Type))) + catch _:_ -> erlang:error(badarg) + end + end. + +-spec(family_projection(SetFun, Family1) -> Family2 when + SetFun :: set_fun(), + Family1 :: family(), + Family2 :: family()). +family_projection(SetFun, F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(_, _) when [] =:= ?LIST(F) -> + empty_set(); + ?FAMILY(DT, Type) -> + case external_fun(SetFun) of + false -> + case fam_proj(?LIST(F), SetFun, Type, ?ANYTYPE, []) of + {SL, NewType} -> + ?SET(SL, ?BINREL(DT, NewType)); + Bad -> + erlang:error(Bad) + end; + _ -> + erlang:error(badarg) + end; + ?ANYTYPE -> F; + _ -> erlang:error(badarg) + end. + +%%% +%%% Digraph functions +%%% + +-spec(family_to_digraph(Family) -> Graph when + Graph :: digraph:graph(), + Family :: family()). +family_to_digraph(F) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(_, _) -> fam2digraph(F, digraph:new()); + ?ANYTYPE -> digraph:new(); + _Else -> erlang:error(badarg) + end. + +-spec(family_to_digraph(Family, GraphType) -> Graph when + Graph :: digraph:graph(), + Family :: family(), + GraphType :: [digraph:d_type()]). +family_to_digraph(F, Type) when ?IS_SET(F) -> + case ?TYPE(F) of + ?FAMILY(_, _) -> ok; + ?ANYTYPE -> ok; + _Else -> erlang:error(badarg) + end, + try digraph:new(Type) of + G -> case catch fam2digraph(F, G) of + {error, Reason} -> + true = digraph:delete(G), + erlang:error(Reason); + _ -> + G + end + catch + error:badarg -> erlang:error(badarg) + end. + +-spec(digraph_to_family(Graph) -> Family when + Graph :: digraph:graph(), + Family :: family()). +digraph_to_family(G) -> + try digraph_family(G) of + L -> ?SET(L, ?FAMILY(?ATOM_TYPE, ?ATOM_TYPE)) + catch _:_ -> erlang:error(badarg) + end. + +-spec(digraph_to_family(Graph, Type) -> Family when + Graph :: digraph:graph(), + Family :: family(), + Type :: type()). +digraph_to_family(G, T) -> + case {is_type(T), T} of + {true, ?SET_OF(?FAMILY(_,_) = Type)} -> + try digraph_family(G) of + L -> ?SET(L, Type) + catch _:_ -> erlang:error(badarg) + end; + _ -> + erlang:error(badarg) + end. + +%% +%% Local functions +%% + +%% Type = OrderedSetType +%% | SetType +%% | atom() except '_' +%% OrderedSetType = {Type, ..., Type} +%% SetType = [ElementType] % list of exactly one element +%% ElementType = '_' % any type (implies empty set) +%% | Type + +is_types(0, _T) -> + true; +is_types(I, T) -> + case is_type(?REL_TYPE(I, T)) of + true -> is_types(I-1, T); + false -> false + end. + +is_element_type(?ANYTYPE) -> + true; +is_element_type(T) -> + is_type(T). + +set_of_sets([S | Ss], L, T0) when ?IS_SET(S) -> + case unify_types([?TYPE(S)], T0) of + [] -> {error, type_mismatch}; + Type -> set_of_sets(Ss, [?LIST(S) | L], Type) + end; +set_of_sets([S | Ss], L, T0) when ?IS_ORDSET(S) -> + case unify_types(?ORDTYPE(S), T0) of + [] -> {error, type_mismatch}; + Type -> set_of_sets(Ss, [?ORDDATA(S) | L], Type) + end; +set_of_sets([], L, T) -> + ?SET(usort(L), T); +set_of_sets(_, _L, _T) -> + {error, badarg}. + +ordset_of_sets([S | Ss], L, T) when ?IS_SET(S) -> + ordset_of_sets(Ss, [?LIST(S) | L], [[?TYPE(S)] | T]); +ordset_of_sets([S | Ss], L, T) when ?IS_ORDSET(S) -> + ordset_of_sets(Ss, [?ORDDATA(S) | L], [?ORDTYPE(S) | T]); +ordset_of_sets([], L, T) -> + ?ORDSET(list_to_tuple(reverse(L)), list_to_tuple(reverse(T))); +ordset_of_sets(_, _L, _T) -> + error. + +%% Inlined. +rel(Ts, [Type]) -> + case is_type(Type) and atoms_only(Type, 1) of + true -> + rel(Ts, tuple_size(Type), Type); + false -> + rel_type(Ts, [], Type) + end; +rel(Ts, Sz) -> + rel(Ts, Sz, erlang:make_tuple(Sz, ?ATOM_TYPE)). + +atoms_only(Type, I) when ?IS_ATOM_TYPE(?REL_TYPE(I, Type)) -> + atoms_only(Type, I+1); +atoms_only(Type, I) when I > tuple_size(Type), ?IS_RELATION(Type) -> + true; +atoms_only(_Type, _I) -> + false. + +rel(Ts, Sz, Type) when Sz >= 1 -> + SL = usort(Ts), + rel(SL, SL, Sz, Type). + +rel([T | Ts], L, Sz, Type) when tuple_size(T) =:= Sz -> + rel(Ts, L, Sz, Type); +rel([], L, _Sz, Type) -> + ?SET(L, Type). + +rel_type([E | Ts], L, Type) -> + {NType, NE} = make_element(E, Type, Type), + rel_type(Ts, [NE | L], NType); +rel_type([], [], ?ANYTYPE) -> + empty_set(); +rel_type([], SL, Type) when ?IS_RELATION(Type) -> + ?SET(usort(SL), Type). + +%% Inlined. +a_func(Ts, T) -> + case {T, is_type(T)} of + {[?BINREL(DT, RT) = Type], true} when ?IS_ATOM_TYPE(DT), + ?IS_ATOM_TYPE(RT) -> + func(Ts, Type); + {[Type], true} -> + func_type(Ts, [], Type, fun(?BINREL(_,_)) -> true end) + end. + +func(L0, Type) -> + L = usort(L0), + func(L, L, L, Type). + +func([{X,_} | Ts], X0, L, Type) when X /= X0 -> + func(Ts, X, L, Type); +func([{X,_} | _Ts], X0, _L, _Type) when X == X0 -> + bad_function; +func([], _X0, L, Type) -> + ?SET(L, Type). + +%% Inlined. +fam(Ts, T) -> + case {T, is_type(T)} of + {[?FAMILY(DT, RT) = Type], true} when ?IS_ATOM_TYPE(DT), + ?IS_ATOM_TYPE(RT) -> + fam2(Ts, Type); + {[Type], true} -> + func_type(Ts, [], Type, fun(?FAMILY(_,_)) -> true end) + end. + +fam2([], Type) -> + ?SET([], Type); +fam2(Ts, Type) -> + fam2(sort(Ts), Ts, [], Type). + +fam2([{I,L} | T], I0, SL, Type) when I /= I0 -> + fam2(T, I, [{I,usort(L)} | SL], Type); +fam2([{I,L} | T], I0, SL, Type) when I == I0 -> + case {usort(L), SL} of + {NL, [{_I,NL1} | _]} when NL == NL1 -> + fam2(T, I0, SL, Type); + _ -> + bad_function + end; +fam2([], _I0, SL, Type) -> + ?SET(reverse(SL), Type). + +func_type([E | T], SL, Type, F) -> + {NType, NE} = make_element(E, Type, Type), + func_type(T, [NE | SL], NType, F); +func_type([], [], ?ANYTYPE, _F) -> + empty_set(); +func_type([], SL, Type, F) -> + true = F(Type), + NL = usort(SL), + check_function(NL, ?SET(NL, Type)). + +setify(L, ?SET_OF(Atom)) when ?IS_ATOM_TYPE(Atom), Atom =/= ?ANYTYPE -> + ?SET(usort(L), Atom); +setify(L, ?SET_OF(Type0)) -> + try is_no_lists(Type0) of + N when is_integer(N) -> + rel(L, N, Type0); + Sizes -> + make_oset(L, Sizes, L, Type0) + catch + _:_ -> + {?SET_OF(Type), Set} = create(L, Type0, Type0, []), + ?SET(Set, Type) + end; +setify(E, Type0) -> + {Type, OrdSet} = make_element(E, Type0, Type0), + ?ORDSET(OrdSet, Type). + +is_no_lists(T) when is_tuple(T) -> + Sz = tuple_size(T), + is_no_lists(T, Sz, Sz, []). + +is_no_lists(_T, 0, Sz, []) -> + Sz; +is_no_lists(_T, 0, Sz, L) -> + {Sz, L}; +is_no_lists(T, I, Sz, L) when ?IS_ATOM_TYPE(?REL_TYPE(I, T)) -> + is_no_lists(T, I-1, Sz, L); +is_no_lists(T, I, Sz, L) -> + is_no_lists(T, I-1, Sz, [{I,is_no_lists(?REL_TYPE(I, T))} | L]). + +create([E | Es], T, T0, L) -> + {NT, S} = make_element(E, T, T0), + create(Es, NT, T0, [S | L]); +create([], T, _T0, L) -> + {?SET_OF(T), usort(L)}. + +make_element(C, ?ANYTYPE, _T0) -> + make_element(C); +make_element(C, Atom, ?ANYTYPE) when ?IS_ATOM_TYPE(Atom), + not is_list(C), not is_tuple(C) -> + {Atom, C}; +make_element(C, Atom, Atom) when ?IS_ATOM_TYPE(Atom) -> + {Atom, C}; +make_element(T, TT, ?ANYTYPE) when tuple_size(T) =:= tuple_size(TT) -> + make_tuple(tuple_to_list(T), tuple_to_list(TT), [], [], ?ANYTYPE); +make_element(T, TT, T0) when tuple_size(T) =:= tuple_size(TT) -> + make_tuple(tuple_to_list(T), tuple_to_list(TT), [], [], tuple_to_list(T0)); +make_element(L, [LT], ?ANYTYPE) when is_list(L) -> + create(L, LT, ?ANYTYPE, []); +make_element(L, [LT], [T0]) when is_list(L) -> + create(L, LT, T0, []). + +make_tuple([E | Es], [T | Ts], NT, L, T0) when T0 =:= ?ANYTYPE -> + {ET, ES} = make_element(E, T, T0), + make_tuple(Es, Ts, [ET | NT], [ES | L], T0); +make_tuple([E | Es], [T | Ts], NT, L, [T0 | T0s]) -> + {ET, ES} = make_element(E, T, T0), + make_tuple(Es, Ts, [ET | NT], [ES | L], T0s); +make_tuple([], [], NT, L, _T0s) when NT =/= [] -> + {list_to_tuple(reverse(NT)), list_to_tuple(reverse(L))}. + +%% Derive type. +make_element(C) when not is_list(C), not is_tuple(C) -> + {?ATOM_TYPE, C}; +make_element(T) when is_tuple(T) -> + make_tuple(tuple_to_list(T), [], []); +make_element(L) when is_list(L) -> + create(L, ?ANYTYPE, ?ANYTYPE, []). + +make_tuple([E | Es], T, L) -> + {ET, ES} = make_element(E), + make_tuple(Es, [ET | T], [ES | L]); +make_tuple([], T, L) when T =/= [] -> + {list_to_tuple(reverse(T)), list_to_tuple(reverse(L))}. + +make_oset([T | Ts], Szs, L, Type) -> + true = test_oset(Szs, T, T), + make_oset(Ts, Szs, L, Type); +make_oset([], _Szs, L, Type) -> + ?SET(usort(L), Type). + +%% Optimization. Avoid re-building (nested) tuples. +test_oset({Sz,Args}, T, T0) when tuple_size(T) =:= Sz -> + test_oset_args(Args, T, T0); +test_oset(Sz, T, _T0) when tuple_size(T) =:= Sz -> + true. + +test_oset_args([{Arg,Szs} | Ss], T, T0) -> + true = test_oset(Szs, ?REL_TYPE(Arg, T), T0), + test_oset_args(Ss, T, T0); +test_oset_args([], _T, _T0) -> + true. + +list_of_sets([S | Ss], Type, L) -> + list_of_sets(Ss, Type, [?SET(S, Type) | L]); +list_of_sets([], _Type, L) -> + reverse(L). + +list_of_ordsets([S | Ss], Type, L) -> + list_of_ordsets(Ss, Type, [?ORDSET(S, Type) | L]); +list_of_ordsets([], _Type, L) -> + reverse(L). + +tuple_of_sets([S | Ss], [?SET_OF(Type) | Types], L) -> + tuple_of_sets(Ss, Types, [?SET(S, Type) | L]); +tuple_of_sets([S | Ss], [Type | Types], L) -> + tuple_of_sets(Ss, Types, [?ORDSET(S, Type) | L]); +tuple_of_sets([], [], L) -> + list_to_tuple(reverse(L)). + +spec([E | Es], Fun, Type, L) -> + case Fun(term2set(E, Type)) of + true -> + spec(Es, Fun, Type, [E | L]); + false -> + spec(Es, Fun, Type, L); + _ -> + badarg + end; +spec([], _Fun, _Type, L) -> + reverse(L). + +specification([E | Es], Fun, L) -> + case Fun(E) of + true -> + specification(Es, Fun, [E | L]); + false -> + specification(Es, Fun, L); + _ -> + badarg + end; +specification([], _Fun, L) -> + reverse(L). + +%% Elements from the first list are kept. +intersection([H1 | T1], [H2 | T2], L) when H1 < H2 -> + intersection1(T1, T2, L, H2); +intersection([H1 | T1], [H2 | T2], L) when H1 == H2 -> + intersection(T1, T2, [H1 | L]); +intersection([H1 | T1], [_H2 | T2], L) -> + intersection2(T1, T2, L, H1); +intersection(_, _, L) -> + reverse(L). + +intersection1([H1 | T1], T2, L, H2) when H1 < H2 -> + intersection1(T1, T2, L, H2); +intersection1([H1 | T1], T2, L, H2) when H1 == H2 -> + intersection(T1, T2, [H1 | L]); +intersection1([H1 | T1], T2, L, _H2) -> + intersection2(T1, T2, L, H1); +intersection1(_, _, L, _) -> + reverse(L). + +intersection2(T1, [H2 | T2], L, H1) when H1 > H2 -> + intersection2(T1, T2, L, H1); +intersection2(T1, [H2 | T2], L, H1) when H1 == H2 -> + intersection(T1, T2, [H1 | L]); +intersection2(T1, [H2 | T2], L, _H1) -> + intersection1(T1, T2, L, H2); +intersection2(_, _, L, _) -> + reverse(L). + +difference([H1 | T1], [H2 | T2], L) when H1 < H2 -> + diff(T1, T2, [H1 | L], H2); +difference([H1 | T1], [H2 | T2], L) when H1 == H2 -> + difference(T1, T2, L); +difference([H1 | T1], [_H2 | T2], L) -> + diff2(T1, T2, L, H1); +difference(L1, _, L) -> + reverse(L, L1). + +diff([H1 | T1], T2, L, H2) when H1 < H2 -> + diff(T1, T2, [H1 | L], H2); +diff([H1 | T1], T2, L, H2) when H1 == H2 -> + difference(T1, T2, L); +diff([H1 | T1], T2, L, _H2) -> + diff2(T1, T2, L, H1); +diff(_, _, L, _) -> + reverse(L). + +diff2(T1, [H2 | T2], L, H1) when H1 > H2 -> + diff2(T1, T2, L, H1); +diff2(T1, [H2 | T2], L, H1) when H1 == H2 -> + difference(T1, T2, L); +diff2(T1, [H2 | T2], L, H1) -> + diff(T1, T2, [H1 | L], H2); +diff2(T1, _, L, H1) -> + reverse(L, [H1 | T1]). + +symdiff([H1 | T1], T2, L) -> + symdiff2(T1, T2, L, H1); +symdiff(_, T2, L) -> + reverse(L, T2). + +symdiff1([H1 | T1], T2, L, H2) when H1 < H2 -> + symdiff1(T1, T2, [H1 | L], H2); +symdiff1([H1 | T1], T2, L, H2) when H1 == H2 -> + symdiff(T1, T2, L); +symdiff1([H1 | T1], T2, L, H2) -> + symdiff2(T1, T2, [H2 | L], H1); +symdiff1(_, T2, L, H2) -> + reverse(L, [H2 | T2]). + +symdiff2(T1, [H2 | T2], L, H1) when H1 > H2 -> + symdiff2(T1, T2, [H2 | L], H1); +symdiff2(T1, [H2 | T2], L, H1) when H1 == H2 -> + symdiff(T1, T2, L); +symdiff2(T1, [H2 | T2], L, H1) -> + symdiff1(T1, T2, [H1 | L], H2); +symdiff2(T1, _, L, H1) -> + reverse(L, [H1 | T1]). + +sympart([H1 | T1], [H2 | T2], L1, L12, L2, T) when H1 < H2 -> + sympart1(T1, T2, [H1 | L1], L12, L2, T, H2); +sympart([H1 | T1], [H2 | T2], L1, L12, L2, T) when H1 == H2 -> + sympart(T1, T2, L1, [H1 | L12], L2, T); +sympart([H1 | T1], [H2 | T2], L1, L12, L2, T) -> + sympart2(T1, T2, L1, L12, [H2 | L2], T, H1); +sympart(S1, [], L1, L12, L2, T) -> + {?SET(reverse(L1, S1), T), + ?SET(reverse(L12), T), + ?SET(reverse(L2), T)}; +sympart(_, S2, L1, L12, L2, T) -> + {?SET(reverse(L1), T), + ?SET(reverse(L12), T), + ?SET(reverse(L2, S2), T)}. + +sympart1([H1 | T1], T2, L1, L12, L2, T, H2) when H1 < H2 -> + sympart1(T1, T2, [H1 | L1], L12, L2, T, H2); +sympart1([H1 | T1], T2, L1, L12, L2, T, H2) when H1 == H2 -> + sympart(T1, T2, L1, [H1 | L12], L2, T); +sympart1([H1 | T1], T2, L1, L12, L2, T, H2) -> + sympart2(T1, T2, L1, L12, [H2 | L2], T, H1); +sympart1(_, T2, L1, L12, L2, T, H2) -> + {?SET(reverse(L1), T), + ?SET(reverse(L12), T), + ?SET(reverse(L2, [H2 | T2]), T)}. + +sympart2(T1, [H2 | T2], L1, L12, L2, T, H1) when H1 > H2 -> + sympart2(T1, T2, L1, L12, [H2 | L2], T, H1); +sympart2(T1, [H2 | T2], L1, L12, L2, T, H1) when H1 == H2 -> + sympart(T1, T2, L1, [H1 | L12], L2, T); +sympart2(T1, [H2 | T2], L1, L12, L2, T, H1) -> + sympart1(T1, T2, [H1 | L1], L12, L2, T, H2); +sympart2(T1, _, L1, L12, L2, T, H1) -> + {?SET(reverse(L1, [H1 | T1]), T), + ?SET(reverse(L12), T), + ?SET(reverse(L2), T)}. + +prod([[E | Es] | Xs], T, L) -> + prod(Es, Xs, T, prod(Xs, [E | T], L)); +prod([], T, L) -> + [list_to_tuple(reverse(T)) | L]. + +prod([E | Es], Xs, T, L) -> + prod(Es, Xs, T, prod(Xs, [E | T], L)); +prod([], _Xs, _E, L) -> + L. + +constant_function([E | Es], X, L) -> + constant_function(Es, X, [{E,X} | L]); +constant_function([], _X, L) -> + reverse(L). + +subset([H1 | T1], [H2 | T2]) when H1 > H2 -> + subset(T1, T2, H1); +subset([H1 | T1], [H2 | T2]) when H1 == H2 -> + subset(T1, T2); +subset(L1, _) -> + L1 =:= []. + +subset(T1, [H2 | T2], H1) when H1 > H2 -> + subset(T1, T2, H1); +subset(T1, [H2 | T2], H1) when H1 == H2 -> + subset(T1, T2); +subset(_, _, _) -> + false. + +disjoint([B | Bs], A, As) when A < B -> + disjoint(As, B, Bs); +disjoint([B | _Bs], A, _As) when A == B -> + false; +disjoint([_B | Bs], A, As) -> + disjoint(Bs, A, As); +disjoint(_Bs, _A, _As) -> + true. + +%% Append sets that come in order, then "merge". +lunion([[_] = S]) -> % optimization + S; +lunion([[] | Ls]) -> + lunion(Ls); +lunion([S | Ss]) -> + umerge(lunion(Ss, last(S), [S], [])); +lunion([]) -> + []. + +lunion([[E] = S | Ss], Last, SL, Ls) when E > Last -> % optimization + lunion(Ss, E, [S | SL], Ls); +lunion([S | Ss], Last, SL, Ls) when hd(S) > Last -> + lunion(Ss, last(S), [S | SL], Ls); +lunion([S | Ss], _Last, SL, Ls) -> + lunion(Ss, last(S), [S], [append(reverse(SL)) | Ls]); +lunion([], _Last, SL, Ls) -> + [append(reverse(SL)) | Ls]. + +%% The empty list is always the first list, if present. +lintersection(_, []) -> + []; +lintersection([S | Ss], S0) -> + lintersection(Ss, intersection(S, S0, [])); +lintersection([], S) -> + S. + +can_rel([S | Ss], L) -> + can_rel(Ss, L, S, S); +can_rel([], L) -> + sort(L). + +can_rel(Ss, L, [E | Es], S) -> + can_rel(Ss, [{E, S} | L], Es, S); +can_rel(Ss, L, _, _S) -> + can_rel(Ss, L). + +rel2family([{X,Y} | S]) -> + rel2fam(S, X, [Y], []); +rel2family([]) -> + []. + +rel2fam([{X,Y} | S], X0, YL, L) when X0 == X -> + rel2fam(S, X0, [Y | YL], L); +rel2fam([{X,Y} | S], X0, [A,B | YL], L) -> % optimization + rel2fam(S, X, [Y], [{X0,reverse(YL,[B,A])} | L]); +rel2fam([{X,Y} | S], X0, YL, L) -> + rel2fam(S, X, [Y], [{X0,YL} | L]); +rel2fam([], X, YL, L) -> + reverse([{X,reverse(YL)} | L]). + +dom([{X,_} | Es]) -> + dom([], X, Es); +dom([] = L) -> + L. + +dom(L, X, [{X1,_} | Es]) when X == X1 -> + dom(L, X, Es); +dom(L, X, [{Y,_} | Es]) -> + dom([X | L], Y, Es); +dom(L, X, []) -> + reverse(L, [X]). + +ran([{_,Y} | Es], L) -> + ran(Es, [Y | L]); +ran([], L) -> + usort(L). + +relprod(A, B) -> + usort(relprod1(A, B)). + +relprod1([{Ay,Ax} | A], B) -> + relprod1(B, Ay, Ax, A, []); +relprod1(_A, _B) -> + []. + +relprod1([{Bx,_By} | B], Ay, Ax, A, L) when Ay > Bx -> + relprod1(B, Ay, Ax, A, L); +relprod1([{Bx,By} | B], Ay, Ax, A, L) when Ay == Bx -> + relprod(B, Bx, By, A, [{Ax,By} | L], Ax, B, Ay); +relprod1([{Bx,By} | B], _Ay, _Ax, A, L) -> + relprod2(B, Bx, By, A, L); +relprod1(_B, _Ay, _Ax, _A, L) -> + L. + +relprod2(B, Bx, By, [{Ay, _Ax} | A], L) when Ay < Bx -> + relprod2(B, Bx, By, A, L); +relprod2(B, Bx, By, [{Ay, Ax} | A], L) when Ay == Bx -> + relprod(B, Bx, By, A, [{Ax,By} | L], Ax, B, Ay); +relprod2(B, _Bx, _By, [{Ay, Ax} | A], L) -> + relprod1(B, Ay, Ax, A, L); +relprod2(_, _, _, _, L) -> + L. + +relprod(B0, Bx0, By0, A0, L, Ax, [{Bx,By} | B], Ay) when Ay == Bx -> + relprod(B0, Bx0, By0, A0, [{Ax,By} | L], Ax, B, Ay); +relprod(B0, Bx0, By0, A0, L, _Ax, _B, _Ay) -> + relprod2(B0, Bx0, By0, A0, L). + +relprod_n([], _R, _EmptyG, _IsR) -> + {error, badarg}; +relprod_n(RL, R, EmptyR, IsR) -> + case domain_type(RL, ?ANYTYPE) of + Error = {error, _Reason} -> + Error; + DType -> + Empty = any(fun is_empty_set/1, RL) or EmptyR, + RType = range_type(RL, []), + Type = ?BINREL(DType, RType), + Prod = + case Empty of + true when DType =:= ?ANYTYPE; RType =:= ?ANYTYPE -> + empty_set(); + true -> + ?SET([], Type); + false -> + TL = ?LIST((relprod_n(RL))), + Sz = length(RL), + Fun = fun({X,A}) -> {X, flat(Sz, A, [])} end, + ?SET(map(Fun, TL), Type) + end, + case IsR of + true -> relative_product(Prod, R); + false -> Prod + end + end. + +relprod_n([R | Rs]) -> + relprod_n(Rs, R). + +relprod_n([], R) -> + R; +relprod_n([R | Rs], R0) -> + T = raise_element(R0, 1), + R1 = relative_product1(T, R), + NR = projection({external, fun({{X,A},AS}) -> {X,{A,AS}} end}, R1), + relprod_n(Rs, NR). + +flat(1, A, L) -> + list_to_tuple([A | L]); +flat(N, {T,A}, L) -> + flat(N-1, T, [A | L]). + +domain_type([T | Ts], T0) when ?IS_SET(T) -> + case ?TYPE(T) of + ?BINREL(DT, _RT) -> + case unify_types(DT, T0) of + [] -> {error, type_mismatch}; + T1 -> domain_type(Ts, T1) + end; + ?ANYTYPE -> + domain_type(Ts, T0); + _ -> {error, badarg} + end; +domain_type([], T0) -> + T0. + +range_type([T | Ts], L) -> + case ?TYPE(T) of + ?BINREL(_DT, RT) -> + range_type(Ts, [RT | L]); + ?ANYTYPE -> + ?ANYTYPE + end; +range_type([], L) -> + list_to_tuple(reverse(L)). + +converse([{A,B} | X], L) -> + converse(X, [{B,A} | L]); +converse([], L) -> + sort(L). + +strict([{E1,E2} | Es], L) when E1 == E2 -> + strict(Es, L); +strict([E | Es], L) -> + strict(Es, [E | L]); +strict([], L) -> + reverse(L). + +weak(Es) -> + %% Not very efficient... + weak(Es, ran(Es, []), []). + +weak(Es=[{X,_} | _], [Y | Ys], L) when X > Y -> + weak(Es, Ys, [{Y,Y} | L]); +weak(Es=[{X,_} | _], [Y | Ys], L) when X == Y -> + weak(Es, Ys, L); +weak([E={X,Y} | Es], Ys, L) when X > Y -> + weak1(Es, Ys, [E | L], X); +weak([E={X,Y} | Es], Ys, L) when X == Y -> + weak2(Es, Ys, [E | L], X); +weak([E={X,_Y} | Es], Ys, L) -> % when X < _Y + weak2(Es, Ys, [E, {X,X} | L], X); +weak([], [Y | Ys], L) -> + weak([], Ys, [{Y,Y} | L]); +weak([], [], L) -> + reverse(L). + +weak1([E={X,Y} | Es], Ys, L, X0) when X > Y, X == X0 -> + weak1(Es, Ys, [E | L], X); +weak1([E={X,Y} | Es], Ys, L, X0) when X == Y, X == X0 -> + weak2(Es, Ys, [E | L], X); +weak1([E={X,_Y} | Es], Ys, L, X0) when X == X0 -> % when X < Y + weak2(Es, Ys, [E, {X,X} | L], X); +weak1(Es, Ys, L, X) -> + weak(Es, Ys, [{X,X} | L]). + +weak2([E={X,_Y} | Es], Ys, L, X0) when X == X0 -> % when X < _Y + weak2(Es, Ys, [E | L], X); +weak2(Es, Ys, L, _X) -> + weak(Es, Ys, L). + +extc(L, [D | Ds], C, Ts) -> + extc(L, Ds, C, Ts, D); +extc(L, [], _C, _Ts) -> + L. + +extc(L, Ds, C, [{X,_Y} | Ts], D) when X < D -> + extc(L, Ds, C, Ts, D); +extc(L, Ds, C, [{X,_Y} | Ts], D) when X == D -> + extc(L, Ds, C, Ts); +extc(L, Ds, C, [{X,_Y} | Ts], D) -> + extc2([{D,C} | L], Ds, C, Ts, X); +extc(L, Ds, C, [], D) -> + extc_tail([{D,C} | L], Ds, C). + +extc2(L, [D | Ds], C, Ts, X) when X > D -> + extc2([{D,C} | L], Ds, C, Ts, X); +extc2(L, [D | Ds], C, Ts, X) when X == D -> + extc(L, Ds, C, Ts); +extc2(L, [D | Ds], C, Ts, _X) -> + extc(L, Ds, C, Ts, D); +extc2(L, [], _C, _Ts, _X) -> + L. + +extc_tail(L, [D | Ds], C) -> + extc_tail([{D,C} | L], Ds, C); +extc_tail(L, [], _C) -> + L. + +is_a_func([{E,_} | Es], E0) when E /= E0 -> + is_a_func(Es, E); +is_a_func(L, _E) -> + L =:= []. + +restrict_n(I, [T | Ts], Key, Keys, L) -> + case element(I, T) of + K when K < Key -> + restrict_n(I, Ts, Key, Keys, L); + K when K == Key -> + restrict_n(I, Ts, Key, Keys, [T | L]); + K -> + restrict_n(I, K, Ts, Keys, L, T) + end; +restrict_n(_I, _Ts, _Key, _Keys, L) -> + L. + +restrict_n(I, K, Ts, [Key | Keys], L, E) when K > Key -> + restrict_n(I, K, Ts, Keys, L, E); +restrict_n(I, K, Ts, [Key | Keys], L, E) when K == Key -> + restrict_n(I, Ts, Key, Keys, [E | L]); +restrict_n(I, _K, Ts, [Key | Keys], L, _E) -> + restrict_n(I, Ts, Key, Keys, L); +restrict_n(_I, _K, _Ts, _Keys, L, _E) -> + L. + +restrict([Key | Keys], Tuples) -> + restrict(Tuples, Key, Keys, []); +restrict(_Keys, _Tuples) -> + []. + +restrict([{K,_E} | Ts], Key, Keys, L) when K < Key -> + restrict(Ts, Key, Keys, L); +restrict([{K,E} | Ts], Key, Keys, L) when K == Key -> + restrict(Ts, Key, Keys, [E | L]); +restrict([{K,E} | Ts], _Key, Keys, L) -> + restrict(Ts, K, Keys, L, E); +restrict(_Ts, _Key, _Keys, L) -> + L. + +restrict(Ts, K, [Key | Keys], L, E) when K > Key -> + restrict(Ts, K, Keys, L, E); +restrict(Ts, K, [Key | Keys], L, E) when K == Key -> + restrict(Ts, Key, Keys, [E | L]); +restrict(Ts, _K, [Key | Keys], L, _E) -> + restrict(Ts, Key, Keys, L); +restrict(_Ts, _K, _Keys, L, _E) -> + L. + +diff_restrict_n(I, [T | Ts], Key, Keys, L) -> + case element(I, T) of + K when K < Key -> + diff_restrict_n(I, Ts, Key, Keys, [T | L]); + K when K == Key -> + diff_restrict_n(I, Ts, Key, Keys, L); + K -> + diff_restrict_n(I, K, Ts, Keys, L, T) + end; +diff_restrict_n(I, _Ts, _Key, _Keys, L) when I =:= 1 -> + reverse(L); +diff_restrict_n(_I, _Ts, _Key, _Keys, L) -> + sort(L). + +diff_restrict_n(I, K, Ts, [Key | Keys], L, T) when K > Key -> + diff_restrict_n(I, K, Ts, Keys, L, T); +diff_restrict_n(I, K, Ts, [Key | Keys], L, _T) when K == Key -> + diff_restrict_n(I, Ts, Key, Keys, L); +diff_restrict_n(I, _K, Ts, [Key | Keys], L, T) -> + diff_restrict_n(I, Ts, Key, Keys, [T | L]); +diff_restrict_n(I, _K, Ts, _Keys, L, T) when I =:= 1 -> + reverse(L, [T | Ts]); +diff_restrict_n(_I, _K, Ts, _Keys, L, T) -> + sort([T | Ts ++ L]). + +diff_restrict([Key | Keys], Tuples) -> + diff_restrict(Tuples, Key, Keys, []); +diff_restrict(_Keys, Tuples) -> + diff_restrict_tail(Tuples, []). + +diff_restrict([{K,E} | Ts], Key, Keys, L) when K < Key -> + diff_restrict(Ts, Key, Keys, [E | L]); +diff_restrict([{K,_E} | Ts], Key, Keys, L) when K == Key -> + diff_restrict(Ts, Key, Keys, L); +diff_restrict([{K,E} | Ts], _Key, Keys, L) -> + diff_restrict(Ts, K, Keys, L, E); +diff_restrict(_Ts, _Key, _Keys, L) -> + L. + +diff_restrict(Ts, K, [Key | Keys], L, E) when K > Key -> + diff_restrict(Ts, K, Keys, L, E); +diff_restrict(Ts, K, [Key | Keys], L, _E) when K == Key -> + diff_restrict(Ts, Key, Keys, L); +diff_restrict(Ts, _K, [Key | Keys], L, E) -> + diff_restrict(Ts, Key, Keys, [E | L]); +diff_restrict(Ts, _K, _Keys, L, E) -> + diff_restrict_tail(Ts, [E | L]). + +diff_restrict_tail([{_K,E} | Ts], L) -> + diff_restrict_tail(Ts, [E | L]); +diff_restrict_tail(_Ts, L) -> + L. + +comp([], B) -> + check_function(B, []); +comp(_A, []) -> + bad_function; +comp(A0, [{Bx,By} | B]) -> + A = converse(A0, []), + check_function(A0, comp1(A, B, [], Bx, By)). + +comp1([{Ay,Ax} | A], B, L, Bx, By) when Ay == Bx -> + comp1(A, B, [{Ax,By} | L], Bx, By); +comp1([{Ay,Ax} | A], B, L, Bx, _By) when Ay > Bx -> + comp2(A, B, L, Bx, Ay, Ax); +comp1([{Ay,_Ax} | _A], _B, _L, Bx, _By) when Ay < Bx -> + bad_function; +comp1([], B, L, Bx, _By) -> + check_function(Bx, B, L). + +comp2(A, [{Bx,_By} | B], L, Bx0, Ay, Ax) when Ay > Bx, Bx /= Bx0 -> + comp2(A, B, L, Bx, Ay, Ax); +comp2(A, [{Bx,By} | B], L, _Bx0, Ay, Ax) when Ay == Bx -> + comp1(A, B, [{Ax,By} | L], Bx, By); +comp2(_A, _B, _L, _Bx0, _Ay, _Ax) -> + bad_function. + +inverse1([{A,B} | X]) -> + inverse(X, A, [{B,A}]); +inverse1([]) -> + []. + +inverse([{A,B} | X], A0, L) when A0 /= A -> + inverse(X, A, [{B,A} | L]); +inverse([{A,_B} | _X], A0, _L) when A0 == A -> + bad_function; +inverse([], _A0, L) -> + SL = [{V,_} | Es] = sort(L), + case is_a_func(Es, V) of + true -> SL; + false -> bad_function + end. + +%% Inlined. +external_fun({external, Function}) when is_atom(Function) -> + false; +external_fun({external, Fun}) -> + Fun; +external_fun(_) -> + false. + +%% Inlined. +element_type(?SET_OF(Type)) -> Type; +element_type(Type) -> Type. + +subst(Ts, Fun, Type) -> + subst(Ts, Fun, Type, ?ANYTYPE, []). + +subst([T | Ts], Fun, Type, NType, L) -> + case setfun(T, Fun, Type, NType) of + {SD, ST} -> subst(Ts, Fun, Type, ST, [{T, SD} | L]); + Bad -> Bad + end; +subst([], _Fun, _Type, NType, L) -> + {L, NType}. + +projection1([E | Es]) -> + projection1([], element(1, E), Es); +projection1([] = L) -> + L. + +projection1(L, X, [E | Es]) -> + case element(1, E) of + X1 when X == X1 -> projection1(L, X, Es); + X1 -> projection1([X | L], X1, Es) + end; +projection1(L, X, []) -> + reverse(L, [X]). + +projection_n([E | Es], I, L) -> + projection_n(Es, I, [element(I, E) | L]); +projection_n([], _I, L) -> + usort(L). + +substitute_element([T | Ts], I, L) -> + substitute_element(Ts, I, [{T, element(I, T)} | L]); +substitute_element(_, _I, L) -> + reverse(L). + +substitute([T | Ts], Fun, L) -> + substitute(Ts, Fun, [{T, Fun(T)} | L]); +substitute(_, _Fun, L) -> + reverse(L). + +partition_n(I, [E | Ts]) -> + partition_n(I, Ts, element(I, E), [E], []); +partition_n(_I, []) -> + []. + +partition_n(I, [E | Ts], K, Es, P) -> + case {element(I, E), Es} of + {K1, _} when K == K1 -> + partition_n(I, Ts, K, [E | Es], P); + {K1, [_]} -> % optimization + partition_n(I, Ts, K1, [E], [Es | P]); + {K1, _} -> + partition_n(I, Ts, K1, [E], [reverse(Es) | P]) + end; +partition_n(I, [], _K, Es, P) when I > 1 -> + sort([reverse(Es) | P]); +partition_n(_I, [], _K, [_] = Es, P) -> % optimization + reverse(P, [Es]); +partition_n(_I, [], _K, Es, P) -> + reverse(P, [reverse(Es)]). + +partition3_n(I, [T | Ts], Key, Keys, L1, L2) -> + case element(I, T) of + K when K < Key -> + partition3_n(I, Ts, Key, Keys, L1, [T | L2]); + K when K == Key -> + partition3_n(I, Ts, Key, Keys, [T | L1], L2); + K -> + partition3_n(I, K, Ts, Keys, L1, L2, T) + end; +partition3_n(I, _Ts, _Key, _Keys, L1, L2) when I =:= 1 -> + [reverse(L1) | reverse(L2)]; +partition3_n(_I, _Ts, _Key, _Keys, L1, L2) -> + [sort(L1) | sort(L2)]. + +partition3_n(I, K, Ts, [Key | Keys], L1, L2, T) when K > Key -> + partition3_n(I, K, Ts, Keys, L1, L2, T); +partition3_n(I, K, Ts, [Key | Keys], L1, L2, T) when K == Key -> + partition3_n(I, Ts, Key, Keys, [T | L1], L2); +partition3_n(I, _K, Ts, [Key | Keys], L1, L2, T) -> + partition3_n(I, Ts, Key, Keys, L1, [T | L2]); +partition3_n(I, _K, Ts, _Keys, L1, L2, T) when I =:= 1 -> + [reverse(L1) | reverse(L2, [T | Ts])]; +partition3_n(_I, _K, Ts, _Keys, L1, L2, T) -> + [sort(L1) | sort([T | Ts ++ L2])]. + +partition3([Key | Keys], Tuples) -> + partition3(Tuples, Key, Keys, [], []); +partition3(_Keys, Tuples) -> + partition3_tail(Tuples, [], []). + +partition3([{K,E} | Ts], Key, Keys, L1, L2) when K < Key -> + partition3(Ts, Key, Keys, L1, [E | L2]); +partition3([{K,E} | Ts], Key, Keys, L1, L2) when K == Key -> + partition3(Ts, Key, Keys, [E | L1], L2); +partition3([{K,E} | Ts], _Key, Keys, L1, L2) -> + partition3(Ts, K, Keys, L1, L2, E); +partition3(_Ts, _Key, _Keys, L1, L2) -> + [L1 | L2]. + +partition3(Ts, K, [Key | Keys], L1, L2, E) when K > Key -> + partition3(Ts, K, Keys, L1, L2, E); +partition3(Ts, K, [Key | Keys], L1, L2, E) when K == Key -> + partition3(Ts, Key, Keys, [E | L1], L2); +partition3(Ts, _K, [Key | Keys], L1, L2, E) -> + partition3(Ts, Key, Keys, L1, [E | L2]); +partition3(Ts, _K, _Keys, L1, L2, E) -> + partition3_tail(Ts, L1, [E | L2]). + +partition3_tail([{_K,E} | Ts], L1, L2) -> + partition3_tail(Ts, L1, [E | L2]); +partition3_tail(_Ts, L1, L2) -> + [L1 | L2]. + +replace([E | Es], F, L) -> + replace(Es, F, [F(E) | L]); +replace(_, _F, L) -> + sort(L). + +mul_relprod([T | Ts], I, R) when ?IS_SET(T) -> + P = raise_element(R, I), + F = relative_product1(P, T), + [F | mul_relprod(Ts, I+1, R)]; +mul_relprod([], _I, _R) -> + []. + +raise_element(R, I) -> + L = sort(I =/= 1, rearr(?LIST(R), I, [])), + Type = ?TYPE(R), + ?SET(L, ?BINREL(?REL_TYPE(I, Type), Type)). + +rearr([E | Es], I, L) -> + rearr(Es, I, [{element(I, E), E} | L]); +rearr([], _I, L) -> + L. + +join_element(E1, E2) -> + [_ | L2] = tuple_to_list(E2), + list_to_tuple(tuple_to_list(E1) ++ L2). + +join_element(E1, E2, I2) -> + tuple_to_list(E1) ++ join_element2(tuple_to_list(E2), 1, I2). + +join_element2([B | Bs], C, I2) when C =/= I2 -> + [B | join_element2(Bs, C+1, I2)]; +join_element2([_ | Bs], _C, _I2) -> + Bs. + +family2rel([{X,S} | F], L) -> + fam2rel(F, L, X, S); +family2rel([], L) -> + reverse(L). + +fam2rel(F, L, X, [Y | Ys]) -> + fam2rel(F, [{X,Y} | L], X, Ys); +fam2rel(F, L, _X, _) -> + family2rel(F, L). + +fam_spec([{_,S}=E | F], Fun, Type, L) -> + case Fun(?SET(S, Type)) of + true -> + fam_spec(F, Fun, Type, [E | L]); + false -> + fam_spec(F, Fun, Type, L); + _ -> + badarg + end; +fam_spec([], _Fun, _Type, L) -> + reverse(L). + +fam_specification([{_,S}=E | F], Fun, L) -> + case Fun(S) of + true -> + fam_specification(F, Fun, [E | L]); + false -> + fam_specification(F, Fun, L); + _ -> + badarg + end; +fam_specification([], _Fun, L) -> + reverse(L). + +un_of_fam([{_X,S} | F], L) -> + un_of_fam(F, [S | L]); +un_of_fam([], L) -> + lunion(sort(L)). + +int_of_fam([{_,S} | F]) -> + int_of_fam(F, [S]); +int_of_fam([]) -> + badarg. + +int_of_fam([{_,S} | F], L) -> + int_of_fam(F, [S | L]); +int_of_fam([], [L | Ls]) -> + lintersection(Ls, L). + +fam_un([{X,S} | F], L) -> + fam_un(F, [{X, lunion(S)} | L]); +fam_un([], L) -> + reverse(L). + +fam_int([{X, [S | Ss]} | F], L) -> + fam_int(F, [{X, lintersection(Ss, S)} | L]); +fam_int([{_X,[]} | _F], _L) -> + badarg; +fam_int([], L) -> + reverse(L). + +fam_dom([{X,S} | F], L) -> + fam_dom(F, [{X, dom(S)} | L]); +fam_dom([], L) -> + reverse(L). + +fam_ran([{X,S} | F], L) -> + fam_ran(F, [{X, ran(S, [])} | L]); +fam_ran([], L) -> + reverse(L). + +fam_union(F1 = [{A,_AS} | _AL], [B1={B,_BS} | BL], L) when A > B -> + fam_union(F1, BL, [B1 | L]); +fam_union([{A,AS} | AL], [{B,BS} | BL], L) when A == B -> + fam_union(AL, BL, [{A, umerge(AS, BS)} | L]); +fam_union([A1 | AL], F2, L) -> + fam_union(AL, F2, [A1 | L]); +fam_union(_, F2, L) -> + reverse(L, F2). + +fam_intersect(F1 = [{A,_AS} | _AL], [{B,_BS} | BL], L) when A > B -> + fam_intersect(F1, BL, L); +fam_intersect([{A,AS} | AL], [{B,BS} | BL], L) when A == B -> + fam_intersect(AL, BL, [{A, intersection(AS, BS, [])} | L]); +fam_intersect([_A1 | AL], F2, L) -> + fam_intersect(AL, F2, L); +fam_intersect(_, _, L) -> + reverse(L). + +fam_difference(F1 = [{A,_AS} | _AL], [{B,_BS} | BL], L) when A > B -> + fam_difference(F1, BL, L); +fam_difference([{A,AS} | AL], [{B,BS} | BL], L) when A == B -> + fam_difference(AL, BL, [{A, difference(AS, BS, [])} | L]); +fam_difference([A1 | AL], F2, L) -> + fam_difference(AL, F2, [A1 | L]); +fam_difference(F1, _, L) -> + reverse(L, F1). + +check_function([{X,_} | XL], R) -> + check_function(X, XL, R); +check_function([], R) -> + R. + +check_function(X0, [{X,_} | XL], R) when X0 /= X -> + check_function(X, XL, R); +check_function(X0, [{X,_} | _XL], _R) when X0 == X -> + bad_function; +check_function(_X0, [], R) -> + R. + +fam_partition_n(I, [E | Ts]) -> + fam_partition_n(I, Ts, element(I, E), [E], []); +fam_partition_n(_I, []) -> + []. + +fam_partition_n(I, [E | Ts], K, Es, P) -> + case {element(I, E), Es} of + {K1, _} when K == K1 -> + fam_partition_n(I, Ts, K, [E | Es], P); + {K1, [_]} -> % optimization + fam_partition_n(I, Ts, K1, [E], [{K,Es} | P]); + {K1, _} -> + fam_partition_n(I, Ts, K1, [E], [{K,reverse(Es)} | P]) + end; +fam_partition_n(_I, [], K, [_] = Es, P) -> % optimization + reverse(P, [{K,Es}]); +fam_partition_n(_I, [], K, Es, P) -> + reverse(P, [{K,reverse(Es)}]). + +fam_partition([{K,Vs} | Ts], Sort) -> + fam_partition(Ts, K, [Vs], [], Sort); +fam_partition([], _Sort) -> + []. + +fam_partition([{K1,V} | Ts], K, Vs, P, S) when K1 == K -> + fam_partition(Ts, K, [V | Vs], P, S); +fam_partition([{K1,V} | Ts], K, [_] = Vs, P, S) -> % optimization + fam_partition(Ts, K1, [V], [{K, Vs} | P], S); +fam_partition([{K1,V} | Ts], K, Vs, P, S) -> + fam_partition(Ts, K1, [V], [{K, sort(S, Vs)} | P], S); +fam_partition([], K, [_] = Vs, P, _S) -> % optimization + [{K, Vs} | P]; +fam_partition([], K, Vs, P, S) -> + [{K, sort(S, Vs)} | P]. + +fam_proj([{X,S} | F], Fun, Type, NType, L) -> + case setfun(S, Fun, Type, NType) of + {SD, ST} -> fam_proj(F, Fun, Type, ST, [{X, SD} | L]); + Bad -> Bad + end; +fam_proj([], _Fun, _Type, NType, L) -> + {reverse(L), NType}. + +setfun(T, Fun, Type, NType) -> + case Fun(term2set(T, Type)) of + NS when ?IS_SET(NS) -> + case unify_types(NType, ?SET_OF(?TYPE(NS))) of + [] -> type_mismatch; + NT -> {?LIST(NS), NT} + end; + NS when ?IS_ORDSET(NS) -> + case unify_types(NType, NT = ?ORDTYPE(NS)) of + [] -> type_mismatch; + NT -> {?ORDDATA(NS), NT} + end; + _ -> + badarg + end. + +%% Inlined. +term2set(L, Type) when is_list(L) -> + ?SET(L, Type); +term2set(T, Type) -> + ?ORDSET(T, Type). + +fam2digraph(F, G) -> + Fun = fun({From, ToL}) -> + digraph:add_vertex(G, From), + Fun2 = fun(To) -> + digraph:add_vertex(G, To), + case digraph:add_edge(G, From, To) of + {error, {bad_edge, _}} -> + throw({error, cyclic}); + _ -> + true + end + end, + foreach(Fun2, ToL) + end, + foreach(Fun, to_external(F)), + G. + +digraph_family(G) -> + Vs = sort(digraph:vertices(G)), + digraph_fam(Vs, Vs, G, []). + +digraph_fam([V | Vs], V0, G, L) when V /= V0 -> + Ns = sort(digraph:out_neighbours(G, V)), + digraph_fam(Vs, V, G, [{V,Ns} | L]); +digraph_fam([], _V0, _G, L) -> + reverse(L). + +%% -> boolean() +check_fun(T, F, FunT) -> + true = is_type(FunT), + {NT, _MaxI} = number_tuples(T, 1), + L = flatten(tuple2list(F(NT))), + has_hole(L, 1). + +number_tuples(T, N) when is_tuple(T) -> + {L, NN} = mapfoldl(fun number_tuples/2, N, tuple_to_list(T)), + {list_to_tuple(L), NN}; +number_tuples(_, N) -> + {N, N+1}. + +tuple2list(T) when is_tuple(T) -> + map(fun tuple2list/1, tuple_to_list(T)); +tuple2list(C) -> + [C]. + +has_hole([I | Is], I0) when I =< I0 -> has_hole(Is, erlang:max(I+1, I0)); +has_hole(Is, _I) -> Is =/= []. + +%% Optimization. Same as check_fun/3, but for integers. +check_for_sort(T, _I) when T =:= ?ANYTYPE -> + empty; +check_for_sort(T, I) when ?IS_RELATION(T), I =< ?REL_ARITY(T), I >= 1 -> + I > 1; +check_for_sort(_T, _I) -> + error. + +inverse_substitution(L, Fun, Sort) -> + %% One easily sees that the inverse of the tuples created by + %% applying Fun need to be sorted iff the tuples created by Fun + %% need to be sorted. + sort(Sort, fun_rearr(L, Fun, [])). + +fun_rearr([E | Es], Fun, L) -> + fun_rearr(Es, Fun, [{Fun(E), E} | L]); +fun_rearr([], _Fun, L) -> + L. + +sets_to_list(Ss) -> + map(fun(S) when ?IS_SET(S) -> ?LIST(S) end, Ss). + +types([], L) -> + list_to_tuple(reverse(L)); +types([S | _Ss], _L) when ?TYPE(S) =:= ?ANYTYPE -> + ?ANYTYPE; +types([S | Ss], L) -> + types(Ss, [?TYPE(S) | L]). + +%% Inlined. +unify_types(T, T) -> T; +unify_types(Type1, Type2) -> + catch unify_types1(Type1, Type2). + +unify_types1(Atom, Atom) when ?IS_ATOM_TYPE(Atom) -> + Atom; +unify_types1(?ANYTYPE, Type) -> + Type; +unify_types1(Type, ?ANYTYPE) -> + Type; +unify_types1(?SET_OF(Type1), ?SET_OF(Type2)) -> + [unify_types1(Type1, Type2)]; +unify_types1(T1, T2) when tuple_size(T1) =:= tuple_size(T2) -> + unify_typesl(tuple_size(T1), T1, T2, []); +unify_types1(_T1, _T2) -> + throw([]). + +unify_typesl(0, _T1, _T2, L) -> + list_to_tuple(L); +unify_typesl(N, T1, T2, L) -> + T = unify_types1(?REL_TYPE(N, T1), ?REL_TYPE(N, T2)), + unify_typesl(N-1, T1, T2, [T | L]). + +%% inlined. +match_types(T, T) -> true; +match_types(Type1, Type2) -> match_types1(Type1, Type2). + +match_types1(Atom, Atom) when ?IS_ATOM_TYPE(Atom) -> + true; +match_types1(?ANYTYPE, _) -> + true; +match_types1(_, ?ANYTYPE) -> + true; +match_types1(?SET_OF(Type1), ?SET_OF(Type2)) -> + match_types1(Type1, Type2); +match_types1(T1, T2) when tuple_size(T1) =:= tuple_size(T2) -> + match_typesl(tuple_size(T1), T1, T2); +match_types1(_T1, _T2) -> + false. + +match_typesl(0, _T1, _T2) -> + true; +match_typesl(N, T1, T2) -> + case match_types1(?REL_TYPE(N, T1), ?REL_TYPE(N, T2)) of + true -> match_typesl(N-1, T1, T2); + false -> false + end. + +sort(true, L) -> + sort(L); +sort(false, L) -> + reverse(L). diff --git a/lib/tools/test/tools_bench.spec b/lib/tools/test/tools_bench.spec new file mode 100644 index 0000000000..ef08fd68a8 --- /dev/null +++ b/lib/tools/test/tools_bench.spec @@ -0,0 +1 @@ +{suites,"../tools_test",[prof_bench_SUITE]}. |