From 62c1dd9d9994367da43212f1b33c9e2dacb27e4b Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 16 Jan 2015 07:02:54 +0100 Subject: core_lib: Teach is_var_used/2 to handle keys in map patterns is_var_used/2 did not notice that variable keys in map patterns were used, which could cause sys_core_fold to do unsafe optimizations. --- lib/compiler/src/core_lib.erl | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/core_lib.erl b/lib/compiler/src/core_lib.erl index 0d95971f91..730e3a5317 100644 --- a/lib/compiler/src/core_lib.erl +++ b/lib/compiler/src/core_lib.erl @@ -236,10 +236,15 @@ vu_pat_seg_list(V, Ss, St) -> end end, St, Ss). -vu_map_pairs(V, [#c_map_pair{val=Pat}|T], St0) -> - case vu_pattern(V, Pat, St0) of - {true,_}=St -> St; - St -> vu_map_pairs(V, T, St) +vu_map_pairs(V, [#c_map_pair{key=Key,val=Pat}|T], St0) -> + case vu_expr(V, Key) of + true -> + {true,false}; + false -> + case vu_pattern(V, Pat, St0) of + {true,_}=St -> St; + St -> vu_map_pairs(V, T, St) + end end; vu_map_pairs(_, [], St) -> St. -- cgit v1.2.3 From a1243173ed98d1006914337b94f28c9594bd8b02 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Thu, 15 Jan 2015 17:17:11 +0100 Subject: Fix handling of binary map keys in comprehensions The translation of list comprehension with a map pattern with a big literal binary as key such as: lc(L) -> [V || #{<<2:301>> := V} <- L]. would generate Core Erlang code where an unbound variable were referenced: 'lc'/1 = fun (L) -> letrec 'lc$^0'/1 = fun (_cor4) -> case _cor4 of <[~{~<_cor1,V>}~|_cor3]> when 'true' -> let <_cor5> = apply 'lc$^0'/1(_cor3) in [V|_cor5] <[_cor2|_cor3]> when 'true' -> apply 'lc$^0'/1(_cor3) <[]> when 'true' -> [] end in let <_cor1> = #{#<2>(301,1,'integer',['unsigned'|['big']])}# in apply 'lc$^0'/1(L) In the map pattern in the 'case' in the 'letrec', the key is the variable '_cor1' which should be bound in the enclosing environment. It is not. There is binding of '_cor1', but in the wrong place (at the end of the function). Because of the way v3_kernel translates letrecs, the code *happens* to work. The code will break if Core Erlang optimizations were strengthened to more aggressively eliminate variable bindings that are not used, or if the translation from Core Erlang to Kernel Erlang were changed. Correct the translation so that '_cor1' is bound in the environment enclosing the 'letrec': 'lc'/1 = fun (L) -> let <_cor1> = #{#<2>(301,1,'integer',['unsigned'|['big']])}# in letrec 'lc$^0'/1 = fun (_cor4) -> case _cor4 of <[~{~<_cor1,V>}~|_cor3]> when 'true' -> let <_cor5> = apply 'lc$^0'/1(_cor3) in [V|_cor5] <[_cor2|_cor3]> when 'true' -> apply 'lc$^0'/1(_cor3) <[]> when 'true' -> [] end in apply 'lc$^0'/1(L) Unfortunately I was not able to come up with a test case that demonstrates the bug. --- lib/compiler/src/v3_core.erl | 18 +++++++++++------- 1 file changed, 11 insertions(+), 7 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl index 612660c2d6..b861de3bbb 100644 --- a/lib/compiler/src/v3_core.erl +++ b/lib/compiler/src/v3_core.erl @@ -105,7 +105,8 @@ -record(iset, {anno=#a{},var,arg}). -record(itry, {anno=#a{},args,vars,body,evars,handler}). -record(ifilter, {anno=#a{},arg}). --record(igen, {anno=#a{},acc_pat,acc_guard,skip_pat,tail,tail_pat,arg}). +-record(igen, {anno=#a{},ceps=[],acc_pat,acc_guard, + skip_pat,tail,tail_pat,arg}). -type iapply() :: #iapply{}. -type ibinary() :: #ibinary{}. @@ -1011,7 +1012,8 @@ fun_tq({_,_,Name}=Id, Cs0, L, St0, NameInfo) -> %% lc_tq(Line, Exp, [Qualifier], Mc, State) -> {LetRec,[PreExp],State}. %% This TQ from Simon PJ pp 127-138. -lc_tq(Line, E, [#igen{anno=GAnno,acc_pat=AccPat,acc_guard=AccGuard, +lc_tq(Line, E, [#igen{anno=GAnno,ceps=Ceps, + acc_pat=AccPat,acc_guard=AccGuard, skip_pat=SkipPat,tail=Tail,tail_pat=TailPat, arg={Pre,Arg}}|Qs], Mc, St0) -> {Name,St1} = new_fun_name("lc", St0), @@ -1046,7 +1048,7 @@ lc_tq(Line, E, [#igen{anno=GAnno,acc_pat=AccPat,acc_guard=AccGuard, Fun = #ifun{anno=LAnno,id=[],vars=[Var],clauses=Cs,fc=Fc}, {#iletrec{anno=LAnno#a{anno=[list_comprehension|LA]},defs=[{{Name,1},Fun}], body=Pre ++ [#iapply{anno=LAnno,op=F,args=[Arg]}]}, - [],St4}; + Ceps,St4}; lc_tq(Line, E, [#ifilter{}=Filter|Qs], Mc, St) -> filter_tq(Line, E, Filter, Mc, St, Qs, fun lc_tq/5); lc_tq(Line, E0, [], Mc0, St0) -> @@ -1071,7 +1073,8 @@ bc_tq(Line, Exp, Qs0, _, St0) -> args=[Sz]}}] ++ BcPre, {E,Pre,St}. -bc_tq1(Line, E, [#igen{anno=GAnno,acc_pat=AccPat,acc_guard=AccGuard, +bc_tq1(Line, E, [#igen{anno=GAnno,ceps=Ceps, + acc_pat=AccPat,acc_guard=AccGuard, skip_pat=SkipPat,tail=Tail,tail_pat=TailPat, arg={Pre,Arg}}|Qs], Mc, St0) -> {Name,St1} = new_fun_name("lbc", St0), @@ -1109,7 +1112,7 @@ bc_tq1(Line, E, [#igen{anno=GAnno,acc_pat=AccPat,acc_guard=AccGuard, Fun = #ifun{anno=LAnno,id=[],vars=Vars,clauses=Cs,fc=Fc}, {#iletrec{anno=LAnno#a{anno=[list_comprehension|LA]},defs=[{{Name,2},Fun}], body=Pre ++ [#iapply{anno=LAnno,op=F,args=[Arg,Mc]}]}, - [],St4}; + Ceps,St4}; bc_tq1(Line, E, [#ifilter{}=Filter|Qs], Mc, St) -> filter_tq(Line, E, Filter, Mc, St, Qs, fun bc_tq1/5); bc_tq1(_, {bin,Bl,Elements}, [], AccVar, St0) -> @@ -1245,8 +1248,9 @@ generator(Line, {generate,Lg,P0,E}, Gs, St0) -> ann_c_cons(LA, Skip, Tail)} end, {Ce,Pre,St4} = safe(E, St3), - Gen = #igen{anno=#a{anno=GA},acc_pat=AccPat,acc_guard=Cg,skip_pat=SkipPat, - tail=Tail,tail_pat=#c_literal{anno=LA,val=[]},arg={Ceps++Pre,Ce}}, + Gen = #igen{anno=#a{anno=GA},ceps=Ceps, + acc_pat=AccPat,acc_guard=Cg,skip_pat=SkipPat, + tail=Tail,tail_pat=#c_literal{anno=LA,val=[]},arg={Pre,Ce}}, {Gen,St4}; generator(Line, {b_generate,Lg,P,E}, Gs, St0) -> LA = lineno_anno(Line, St0), -- cgit v1.2.3 From 1ef53ead19d5bd07caad4daa71b8fecf2fbcd2a6 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Fri, 16 Jan 2015 15:06:53 +0100 Subject: sys_core_fold: Strengthen optimization of letrecs in effect context We used to evaluate the body of a 'letrec' in value context, even if the 'letrec' was being evaluated in effect context. In most cases, the context does not matter because the body is usually just an 'apply' which will never be optimized away. However, in the case of incorrect code described in the previous commit, it does matter. We can find such bad code by evaluating the body in effect context. For example, if we have the following incorrect code: letrec f/1 = fun(A) -> ... ... in let Var = <<2:301>> in apply(Arg) If the letrec is evaluated in effect context, the code will be reduced to: letrec f/1 = fun(A) -> ... ... in seq Var = <<2:301>> do apply(Arg) Now Var will be unbound and a later compiler pass will crash to ensure that the bad Core Erlang code is noticed. Also add a test case to ensure that the compiler crashes if the bug fixed in the previous commit re-surfaces. --- lib/compiler/src/sys_core_fold.erl | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl index 09716d0866..e079fc072a 100644 --- a/lib/compiler/src/sys_core_fold.erl +++ b/lib/compiler/src/sys_core_fold.erl @@ -313,7 +313,7 @@ expr(#c_letrec{defs=Fs0,body=B0}=Letrec, Ctxt, Sub) -> Fs1 = map(fun ({Name,Fb}) -> {Name,expr(Fb, {letrec,Ctxt}, Sub)} end, Fs0), - B1 = body(B0, value, Sub), + B1 = body(B0, Ctxt, Sub), Letrec#c_letrec{defs=Fs1,body=B1}; expr(#c_case{}=Case0, Ctxt, Sub) -> %% Ideally, the compiler should only emit warnings when there is -- cgit v1.2.3 From 3ebfb44a83fcfd506fe4e4925412a973a86474ed Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 21 Jan 2015 12:21:18 +0100 Subject: cerl_clauses: Fix indentation --- lib/compiler/src/cerl_clauses.erl | 46 +++++++++++++++++++-------------------- 1 file changed, 23 insertions(+), 23 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/cerl_clauses.erl b/lib/compiler/src/cerl_clauses.erl index 87bd47c08b..ef74c5b76f 100644 --- a/lib/compiler/src/cerl_clauses.erl +++ b/lib/compiler/src/cerl_clauses.erl @@ -354,29 +354,29 @@ match(P, E, Bs) -> {false, Bs} end end; - map -> - %% The most we can do is to say "definitely no match" if a - %% map pattern is matched against non-map data. - case E of - any -> - {false, Bs}; - _ -> - case type(E) of - literal -> - case is_map(concrete(E)) of - false -> - none; - true -> - {false, Bs} - end; - cons -> - none; - tuple -> - none; - _ -> - {false, Bs} - end - end; + map -> + %% The most we can do is to say "definitely no match" if a + %% map pattern is matched against non-map data. + case E of + any -> + {false, Bs}; + _ -> + case type(E) of + literal -> + case is_map(concrete(E)) of + false -> + none; + true -> + {false, Bs} + end; + cons -> + none; + tuple -> + none; + _ -> + {false, Bs} + end + end; _ -> match_1(P, E, Bs) end. -- cgit v1.2.3 From 142da57a6790e879f0e593f97cf5a65459693c34 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 20 Jan 2015 11:05:28 +0100 Subject: cerl: Make sure that we preserve the invariants for maps Maps have certain invariants that must be preserved: (1) A map as a pattern must be represented as #c_map{} record, never as a literal. The reason is that the pattern '#{}' will match any map, not just the empty map. The literal '#{}' will only match the empty map. (2) In a map pattern, the key must be a literal, a variable, or data (list or tuple). Keys that are binaries or maps *must* be represented as literals. (3) Maps in expressions should be represented as literals if possible. Nothing is broken if this invariant is broken, but the generated code will be less efficient. To preserve invariant (1), cerl:update_c_map/3 must never collapse a map to a literal. To preserve invariant (3), cerl:update_c_map/3 must collapse a map to a literal if possible. To preserve both invariants, we need a way for cerl:update_c_map/3 to know whether the map is used as a pattern or as an expression. The simplest way is to have an 'is_pat' boolean in the #c_map{} record which is set when a #c_map{} record is initially created. We also need to update core_parse.yrl to establish the invariants in the same way as v3_core, to ensure that compiling from a .core file will work even if all optimizations on Core Erlang are disabled. --- lib/compiler/src/cerl.erl | 26 +++++++++++++---- lib/compiler/src/core_parse.hrl | 3 +- lib/compiler/src/core_parse.yrl | 64 +++++++++++++++++++++++++++++++++++------ lib/compiler/src/v3_core.erl | 2 +- 4 files changed, 78 insertions(+), 17 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/cerl.erl b/lib/compiler/src/cerl.erl index 7a2c3d70de..96c8e02542 100644 --- a/lib/compiler/src/cerl.erl +++ b/lib/compiler/src/cerl.erl @@ -123,11 +123,13 @@ bitstr_flags/1, %% keep map exports here for now + c_map_pattern/1, map_es/1, map_arg/1, update_c_map/3, c_map/1, is_c_map_empty/1, ann_c_map/2, ann_c_map/3, + ann_c_map_pattern/2, map_pair_op/1,map_pair_key/1,map_pair_val/1, update_c_map_pair/4, c_map_pair/2, @@ -1590,7 +1592,17 @@ map_arg(#c_map{arg=M}) -> -spec c_map([c_map_pair()]) -> c_map(). c_map(Pairs) -> - #c_map{es=Pairs}. + ann_c_map([], Pairs). + +-spec c_map_pattern([c_map_pair()]) -> c_map(). + +c_map_pattern(Pairs) -> + #c_map{es=Pairs, is_pat=true}. + +-spec ann_c_map_pattern([term()], [c_map_pair()]) -> c_map(). + +ann_c_map_pattern(As, Pairs) -> + #c_map{anno=As, es=Pairs, is_pat=true}. -spec is_c_map_empty(c_map() | c_literal()) -> boolean(). @@ -1598,9 +1610,9 @@ is_c_map_empty(#c_map{ es=[] }) -> true; is_c_map_empty(#c_literal{val=M}) when is_map(M),map_size(M) =:= 0 -> true; is_c_map_empty(_) -> false. --spec ann_c_map([term()], [cerl()]) -> c_map() | c_literal(). +-spec ann_c_map([term()], [c_map_pair()]) -> c_map() | c_literal(). -ann_c_map(As,Es) -> +ann_c_map(As, Es) -> ann_c_map(As, #c_literal{val=#{}}, Es). -spec ann_c_map([term()], c_map() | c_literal(), [c_map_pair()]) -> c_map() | c_literal(). @@ -1648,10 +1660,12 @@ fold_map_pairs(As,[#c_map_pair{op=#c_literal{val=exact},key=Ck,val=Cv}=E|Es],M) fold_map_pairs(As,Es,M) -> #c_map{arg=#c_literal{val=M,anno=As}, es=Es, anno=As }. -%-spec update_c_map(c_map() | c_literal(), [c_map_pair()]) -> c_map() | c_literal(). +-spec update_c_map(c_map(), cerl(), [cerl()]) -> c_map() | c_literal(). -update_c_map(Old,M,Es) -> - #c_map{arg=M, es = Es, anno = get_ann(Old)}. +update_c_map(#c_map{is_pat=true}=Old, M, Es) -> + Old#c_map{arg=M, es=Es}; +update_c_map(#c_map{is_pat=false}=Old, M, Es) -> + ann_c_map(get_ann(Old), M, Es). map_pair_key(#c_map_pair{key=K}) -> K. map_pair_val(#c_map_pair{val=V}) -> V. diff --git a/lib/compiler/src/core_parse.hrl b/lib/compiler/src/core_parse.hrl index 4a00535360..7fd4a82e4e 100644 --- a/lib/compiler/src/core_parse.hrl +++ b/lib/compiler/src/core_parse.hrl @@ -72,7 +72,8 @@ -record(c_map, {anno=[], arg=#c_literal{val=#{}} :: cerl:c_var() | cerl:c_literal(), - es :: [cerl:c_map_pair()]}). + es :: [cerl:c_map_pair()], + is_pat=false :: boolean()}). -record(c_map_pair, {anno=[], op :: #c_literal{val::'assoc'} | #c_literal{val::'exact'}, diff --git a/lib/compiler/src/core_parse.yrl b/lib/compiler/src/core_parse.yrl index a66ad4235f..716c03bc94 100644 --- a/lib/compiler/src/core_parse.yrl +++ b/lib/compiler/src/core_parse.yrl @@ -182,14 +182,14 @@ atomic_pattern -> atomic_literal : '$1'. tuple_pattern -> '{' '}' : c_tuple([]). tuple_pattern -> '{' anno_patterns '}' : c_tuple('$2'). -map_pattern -> '~' '{' '}' '~' : #c_map{es=[]}. +map_pattern -> '~' '{' '}' '~' : c_map_pattern([]). map_pattern -> '~' '{' map_pair_patterns '}' '~' : - #c_map{es=lists:sort('$3')}. + c_map_pattern(lists:sort('$3')). map_pair_patterns -> map_pair_pattern : ['$1']. map_pair_patterns -> map_pair_pattern ',' map_pair_patterns : ['$1' | '$3']. -map_pair_pattern -> '~' '<' anno_pattern ',' anno_pattern '>' : +map_pair_pattern -> '~' '<' anno_expression ',' anno_pattern '>' : #c_map_pair{op=#c_literal{val=exact},key='$3',val='$5'}. cons_pattern -> '[' anno_pattern tail_pattern : @@ -284,10 +284,10 @@ tail_literal -> ',' literal tail_literal : #c_cons{hd='$2',tl='$3'}. tuple -> '{' '}' : c_tuple([]). tuple -> '{' anno_expressions '}' : c_tuple('$2'). -map_expr -> '~' '{' '}' '~' : #c_map{es=[]}. -map_expr -> '~' '{' map_pairs '}' '~' : #c_map{es='$3'}. -map_expr -> '~' '{' map_pairs '|' variable '}' '~' : #c_map{arg='$5',es='$3'}. -map_expr -> '~' '{' map_pairs '|' map_expr '}' '~' : #c_map{arg='$5',es='$3'}. +map_expr -> '~' '{' '}' '~' : c_map([]). +map_expr -> '~' '{' map_pairs '}' '~' : c_map('$3'). +map_expr -> '~' '{' map_pairs '|' variable '}' '~' : ann_c_map([], '$5', '$3'). +map_expr -> '~' '{' map_pairs '|' map_expr '}' '~' : ann_c_map([], '$5', '$3'). map_pairs -> map_pair : ['$1']. map_pairs -> map_pair ',' map_pairs : ['$1' | '$3']. @@ -307,7 +307,7 @@ tail -> '|' anno_expression ']' : '$2'. tail -> ',' anno_expression tail : c_cons('$2', '$3'). binary -> '#' '{' '}' '#' : #c_literal{val = <<>>}. -binary -> '#' '{' segments '}' '#' : #c_binary{segments='$3'}. +binary -> '#' '{' segments '}' '#' : make_binary('$3'). segments -> segment ',' segments : ['$1' | '$3']. segments -> segment : ['$1']. @@ -410,9 +410,55 @@ Erlang code. -include("core_parse.hrl"). --import(cerl, [c_cons/2,c_tuple/1]). +-import(cerl, [ann_c_map/3,c_cons/2,c_map/1,c_map_pattern/1,c_tuple/1]). tok_val(T) -> element(3, T). tok_line(T) -> element(2, T). +%% make_binary([#c_bitstr{}]) -> #c_binary{} | #c_literal{} +%% Create either #c_binary{} or #c_literal{} from the binary segments. +%% In certain contexts, such as keys for maps, only literals and +%% variables are allowed, so we must not create a #c_binary{} +%% record in those situation. +%% +%% To keep this function simple, we use a crude heuristic. We will +%% assume that Core Erlang has been produced by core_pp. If the +%% segments *could* have been output from a literal binary by +%% core_pp, we will create a #c_literal{}. Otherwise we will create a +%% #c_binary{} record. + +make_binary(Segs) -> + try make_lit_bin(<<>>, Segs) of + Bs when is_bitstring(Bs) -> + #c_literal{val=Bs} + catch + throw:impossible -> + #c_binary{segments=Segs} + end. + +make_lit_bin(Acc, [#c_bitstr{val=I0,size=Sz0,unit=U0,type=Type0,flags=F0}|T]) -> + I = get_lit_val(I0), + Sz = get_lit_val(Sz0), + U = get_lit_val(U0), + Type = get_lit_val(Type0), + F = get_lit_val(F0), + if + is_integer(I), U =:= 1, Type =:= integer, F =:= [unsigned,big] -> + ok; + true -> + throw(impossible) + end, + if + Sz =< 8, T =:= [] -> + <>; + Sz =:= 8 -> + make_lit_bin(<>, T); + true -> + throw(impossible) + end; +make_lit_bin(Acc, []) -> Acc. + +get_lit_val(#c_literal{val=Val}) -> Val; +get_lit_val(_) -> throw(impossible). + %% vim: syntax=erlang diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl index b861de3bbb..1d5eb85a1c 100644 --- a/lib/compiler/src/v3_core.erl +++ b/lib/compiler/src/v3_core.erl @@ -1638,7 +1638,7 @@ pattern({tuple,L,Ps}, St) -> {annotate_tuple(record_anno(L, St), Ps1, St),Eps,St1}; pattern({map,L,Pairs}, St0) -> {Ps,Eps,St1} = pattern_map_pairs(Pairs, St0), - {#c_map{anno=lineno_anno(L, St1), es=Ps},Eps,St1}; + {#c_map{anno=lineno_anno(L, St1),es=Ps,is_pat=true},Eps,St1}; pattern({bin,L,Ps}, St) -> %% We don't create a #ibinary record here, since there is %% no need to hold any used/new annotations in a pattern. -- cgit v1.2.3 From 1fcdcd50e9dc09c78259434ae7ba189e6a47ced4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 27 Jan 2015 07:49:12 +0100 Subject: core_parse: Always fold literal conses v3_core is careful to always create literals whenever possible. Correct core_parse so it, too, always creates literals out of literal conses. With that correction, we can remove the workaround in sys_core_fold (introduced in 26a5dea3cb5e101) that handles non-literal flags in a binary. --- lib/compiler/src/core_parse.yrl | 8 ++++---- lib/compiler/src/sys_core_fold.erl | 8 -------- 2 files changed, 4 insertions(+), 12 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/core_parse.yrl b/lib/compiler/src/core_parse.yrl index 716c03bc94..849f801a11 100644 --- a/lib/compiler/src/core_parse.yrl +++ b/lib/compiler/src/core_parse.yrl @@ -193,12 +193,12 @@ map_pair_pattern -> '~' '<' anno_expression ',' anno_pattern '>' : #c_map_pair{op=#c_literal{val=exact},key='$3',val='$5'}. cons_pattern -> '[' anno_pattern tail_pattern : - #c_cons{hd='$2',tl='$3'}. + c_cons('$2', '$3'). tail_pattern -> ']' : #c_literal{val=[]}. tail_pattern -> '|' anno_pattern ']' : '$2'. tail_pattern -> ',' anno_pattern tail_pattern : - #c_cons{hd='$2',tl='$3'}. + c_cons('$2', '$3'). binary_pattern -> '#' '{' '}' '#' : #c_binary{segments=[]}. binary_pattern -> '#' '{' segment_patterns '}' '#' : #c_binary{segments='$3'}. @@ -206,7 +206,7 @@ binary_pattern -> '#' '{' segment_patterns '}' '#' : #c_binary{segments='$3'}. segment_patterns -> segment_pattern ',' segment_patterns : ['$1' | '$3']. segment_patterns -> segment_pattern : ['$1']. -segment_pattern -> '#' '<' anno_pattern '>' '(' anno_patterns ')': +segment_pattern -> '#' '<' anno_pattern '>' '(' anno_expressions ')': case '$6' of [S,U,T,Fs] -> #c_bitstr{val='$3',size=S,unit=U,type=T,flags=Fs}; @@ -279,7 +279,7 @@ cons_literal -> '[' literal tail_literal : c_cons('$2', '$3'). tail_literal -> ']' : #c_literal{val=[]}. tail_literal -> '|' literal ']' : '$2'. -tail_literal -> ',' literal tail_literal : #c_cons{hd='$2',tl='$3'}. +tail_literal -> ',' literal tail_literal : c_cons('$2', '$3'). tuple -> '{' '}' : c_tuple([]). tuple -> '{' anno_expressions '}' : c_tuple('$2'). diff --git a/lib/compiler/src/sys_core_fold.erl b/lib/compiler/src/sys_core_fold.erl index e079fc072a..08b1c0d7b7 100644 --- a/lib/compiler/src/sys_core_fold.erl +++ b/lib/compiler/src/sys_core_fold.erl @@ -607,14 +607,6 @@ eval_binary_1([#c_bitstr{val=#c_literal{val=Val},size=#c_literal{val=Sz}, error:_ -> throw(impossible) end; -eval_binary_1([#c_bitstr{val=#c_literal{},size=#c_literal{}, - unit=#c_literal{},type=#c_literal{}, - flags=#c_cons{}=Flags}=Bitstr|Ss], Acc0) -> - case cerl:fold_literal(Flags) of - #c_literal{} = Flags1 -> - eval_binary_1([Bitstr#c_bitstr{flags=Flags1}|Ss], Acc0); - _ -> throw(impossible) - end; eval_binary_1([], Acc) -> Acc; eval_binary_1(_, _) -> throw(impossible). -- cgit v1.2.3 From 440c54f6a6b78015e8c8e0c7d16ad3cbb3d22147 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 27 Jan 2015 13:42:31 +0100 Subject: core_pp: Correct printing of map literals A map key in a pattern would be incorrectly pretty-printed. As an example, the pattern in: x() -> #{ #{ a => 3 } := 42 } = X. would be pretty-printed as: <~{~<~{~<'a',3>}~,42>}~ instead of: <~{~<~{::<'a',3>}~,42>}~ When this problem has been corrected, the workaround for it in cerl:ann_c_map/3 can be removed. The workaround was not harmless, as it would cause the following map update to incorrectly succeed: (#{})#{a:=1} --- lib/compiler/src/cerl.erl | 12 ------------ lib/compiler/src/core_pp.erl | 10 ++++++++-- 2 files changed, 8 insertions(+), 14 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/cerl.erl b/lib/compiler/src/cerl.erl index 96c8e02542..705c87539e 100644 --- a/lib/compiler/src/cerl.erl +++ b/lib/compiler/src/cerl.erl @@ -1617,18 +1617,6 @@ ann_c_map(As, Es) -> -spec ann_c_map([term()], c_map() | c_literal(), [c_map_pair()]) -> c_map() | c_literal(). -ann_c_map(As,#c_literal{val=Mval}=M,Es) when is_map(Mval), map_size(Mval) =:= 0 -> - Pairs = [[Ck,Cv]||#c_map_pair{key=Ck,val=Cv}<-Es], - IsLit = lists:foldl(fun(Pair,Res) -> - Res andalso is_lit_list(Pair) - end, true, Pairs), - Fun = fun(Pair) -> [K,V] = lit_list_vals(Pair), {K,V} end, - case IsLit of - false -> - #c_map{arg=M, es=Es, anno=As }; - true -> - #c_literal{anno=As, val=maps:from_list(lists:map(Fun, Pairs))} - end; ann_c_map(As,#c_literal{val=M},Es) when is_map(M) -> fold_map_pairs(As,Es,M); ann_c_map(As,M,Es) -> diff --git a/lib/compiler/src/core_pp.erl b/lib/compiler/src/core_pp.erl index 03801a9b6d..01922c3fdf 100644 --- a/lib/compiler/src/core_pp.erl +++ b/lib/compiler/src/core_pp.erl @@ -184,12 +184,12 @@ format_1(#c_map{arg=Var,es=Es}, Ctxt) -> ]; format_1(#c_map_pair{op=#c_literal{val=assoc},key=K,val=V}, Ctxt) -> ["::<", - format_hseq([K,V], ",", add_indent(Ctxt, 1), fun format/2), + format_map_pair(K, V, Ctxt), ">" ]; format_1(#c_map_pair{op=#c_literal{val=exact},key=K,val=V}, Ctxt) -> ["~<", - format_hseq([K,V], ",", add_indent(Ctxt, 1), fun format/2), + format_map_pair(K, V, Ctxt), ">" ]; format_1(#c_cons{hd=H,tl=T}, Ctxt) -> @@ -448,6 +448,12 @@ format_list_tail(#c_cons{anno=[],hd=H,tl=T}, Ctxt) -> format_list_tail(Tail, Ctxt) -> ["|",format(Tail, add_indent(Ctxt, 1)),"]"]. +format_map_pair(K, V, Ctxt0) -> + Ctxt1 = add_indent(Ctxt0, 1), + Txt = format(K, set_class(Ctxt1, expr)), + Ctxt2 = add_indent(Ctxt0, width(Txt, Ctxt1)), + [Txt,",",format(V, Ctxt2)]. + indent(Ctxt) -> indent(Ctxt#ctxt.indent, Ctxt). indent(N, _) when N =< 0 -> ""; -- cgit v1.2.3 From 25603134a658a64d5b024fe1668d9db6f331b2e2 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 27 Jan 2015 09:16:07 +0100 Subject: Move grouping of map constructions from v3_core to v3_kernel When translating a function with map construction: f(A) -> B = b, C = c, #{A=>1,B=>2,C=>3}. v3_core would break apart the map construction into three parts because of the way the map instructions in BEAM work -- variable keys need to be in their own instruction. In the example, constant propagation will turn two of the keys to literal keys. But the initial breaking apart will not be undone, so there will still be three map constructions: 'f'/1 = fun (_cor0) -> let <_cor3> = ~{::<_cor0,1>}~ in let <_cor4> = ~{::<'b',2>|_cor3}~ in ~{::<'c',3>|_cor4}~ It would be possible to complicate the sys_core_fold pass to regroup map operations so that we would get: 'f'/1 = fun (_cor0) -> let <_cor3> = ~{::<_cor0,1>}~ in ~{::<'b',2>,::<'c',3>|_cor3}~ A simpler way that allows to simplify the translation is to skip the grouping in v3_core and translate the function to: 'f'/1 = fun (_cor0) -> ~{::<_cor0,1>,::<'b',2>,::<'c',3>}~ We will then let v3_kernel do the grouping while translating from Core Erlang to Kernel Erlang. --- lib/compiler/src/v3_core.erl | 75 +++++++++-------------------- lib/compiler/src/v3_kernel.erl | 106 +++++++++++++++++++++++------------------ 2 files changed, 82 insertions(+), 99 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/v3_core.erl b/lib/compiler/src/v3_core.erl index 1d5eb85a1c..a9b54005d1 100644 --- a/lib/compiler/src/v3_core.erl +++ b/lib/compiler/src/v3_core.erl @@ -536,7 +536,7 @@ expr({tuple,L,Es0}, St0) -> A = record_anno(L, St1), {annotate_tuple(A, Es1, St1),Eps,St1}; expr({map,L,Es0}, St0) -> - map_build_pair_chain(#c_literal{val=#{}},Es0,lineno_anno(L,St0),St0); + map_build_pairs(#c_literal{val=#{}}, Es0, lineno_anno(L, St0), St0); expr({map,L,M0,Es0}, St0) -> try expr_map(M0,Es0,lineno_anno(L, St0),St0) of {_,_,_}=Res -> Res @@ -779,66 +779,35 @@ expr_map(M0,Es0,A,St0) -> Fc = fail_clause([Fpat], A, #c_literal{val=badarg}), {#icase{anno=#a{anno=A},args=[M1],clauses=Cs,fc=Fc},Mps,St3}; {_,_} -> - {M2,Eps,St2} = map_build_pair_chain(M1,Es0,A,St1), + {M2,Eps,St2} = map_build_pairs(M1, Es0, A, St1), {M2,Mps++Eps,St2} end; false -> throw({bad_map,bad_map}) end. -%% Group continuous literal blocks and single variables, i.e. -%% M0#{ a := 1, b := V1, K1 := V2, K2 := 42} -%% becomes equivalent to -%% M1 = M0#{ a := 1, b := V1 }, -%% M2 = M1#{ K1 := V1 }, -%% M3 = M2#{ K2 := 42 } - -map_build_pair_chain(M,Es,A,St) -> - %% hack, remove iset if only literal - case map_build_pair_chain(M,Es,A,St,[]) of - {_,[#iset{arg=#c_literal{}=Val}],St1} -> {Val,[],St1}; - Normal -> Normal +map_build_pairs(Map0, Es0, Ann, St0) -> + {Es,Pre,St1} = map_build_pairs_1(Es0, St0), + case ann_c_map(Ann, Map0, Es) of + #c_literal{}=Map -> + {Map,[],St1}; + #c_map{}=Map -> + {Var,St2} = new_var(St1), + {Var,Pre++[#iset{var=Var,arg=Map}],St2} end. -map_build_pair_chain(M0,[],_,St,Mps) -> - {M0,Mps,St}; -map_build_pair_chain(M0,Es0,A,St0,Mps) -> - % group continuous literal blocks - % Anno = #a{anno=[compiler_generated]}, - % order is important, we need to reverse the literals - case map_pair_block(Es0,[],[],St0) of - {{CesL,EspL},{[],[]},Es1,St1} -> - {MVar,St2} = new_var(St1), - Pre = [#iset{var=MVar, arg=ann_c_map(A,M0,reverse(CesL))}], - map_build_pair_chain(MVar,Es1,A,St2,Mps++EspL++Pre); - {{[],[]},{CesV,EspV},Es1,St1} -> - {MVar,St2} = new_var(St1), - Pre = [#iset{var=MVar, arg=#c_map{arg=M0,es=CesV, anno=A}}], - map_build_pair_chain(MVar,Es1,A,St2,Mps ++ EspV++Pre); - {{CesL,EspL},{CesV,EspV},Es1,St1} -> - {MVarL,St2} = new_var(St1), - {MVarV,St3} = new_var(St2), - Pre = [#iset{var=MVarL, arg=ann_c_map(A,M0,reverse(CesL))}, - #iset{var=MVarV, arg=#c_map{arg=MVarL,es=CesV,anno=A}}], - map_build_pair_chain(MVarV,Es1,A,St3,Mps++EspL++EspV++Pre) - end. - -map_pair_block([{Op,L,K0,V0}|Es],Ces,Esp,St0) -> - {K,Ep0,St1} = safe(K0, St0), - {V,Ep1,St2} = safe(V0, St1), - A = lineno_anno(L, St2), - Pair0 = map_op_to_c_map_pair(Op), - Pair1 = Pair0#c_map_pair{anno=A,key=K,val=V}, - case cerl:is_literal(K) of - true -> - map_pair_block(Es,[Pair1|Ces],Ep0 ++ Ep1 ++ Esp,St2); - false -> - {{Ces,Esp},{[Pair1],Ep0++Ep1},Es,St2} - end; -map_pair_block([],Ces,Esp,St) -> - {{Ces,Esp},{[],[]},[],St}. +map_build_pairs_1([{Op0,L,K0,V0}|Es], St0) -> + {K,Pre0,St1} = safe(K0, St0), + {V,Pre1,St2} = safe(V0, St1), + {Pairs,Pre2,St3} = map_build_pairs_1(Es, St2), + As = lineno_anno(L, St3), + Op = map_op(Op0), + Pair = cerl:ann_c_map_pair(As, Op, K, V), + {[Pair|Pairs],Pre0++Pre1++Pre2,St3}; +map_build_pairs_1([], St) -> + {[],[],St}. -map_op_to_c_map_pair(map_field_assoc) -> #c_map_pair{op=#c_literal{val=assoc}}; -map_op_to_c_map_pair(map_field_exact) -> #c_map_pair{op=#c_literal{val=exact}}. +map_op(map_field_assoc) -> #c_literal{val=assoc}; +map_op(map_field_exact) -> #c_literal{val=exact}. is_valid_map_src(#c_literal{val = M}) when is_map(M) -> true; is_valid_map_src(#c_var{}) -> true; diff --git a/lib/compiler/src/v3_kernel.erl b/lib/compiler/src/v3_kernel.erl index 6504351c02..72e7a39333 100644 --- a/lib/compiler/src/v3_kernel.erl +++ b/lib/compiler/src/v3_kernel.erl @@ -521,62 +521,76 @@ is_valid_map_src(#k_var{}) -> true; is_valid_map_src(_) -> false. map_split_pairs(A, Var, Ces, Sub, St0) -> - %% two steps - %% 1. force variables - %% 2. remove multiples - Pairs0 = [{Op,K,V} || #c_map_pair{op=#c_literal{val=Op},key=K,val=V} <- Ces], + %% 1. Force variables. + %% 2. Group adjacent pairs with literal keys. + %% 3. Within each such group, remove multiple assignments to the same key. + %% 4. Partition each group according to operator ('=>' and ':='). + Pairs0 = [{Op,K,V} || + #c_map_pair{op=#c_literal{val=Op},key=K,val=V} <- Ces], {Pairs,Esp,St1} = foldr(fun ({Op,K0,V0}, {Ops,Espi,Sti0}) when Op =:= assoc; Op =:= exact -> {K,Eps1,Sti1} = atomic(K0, Sub, Sti0), {V,Eps2,Sti2} = atomic(V0, Sub, Sti1), {[{Op,K,V}|Ops],Eps1 ++ Eps2 ++ Espi,Sti2} end, {[],[],St0}, Pairs0), - - case map_group_pairs(Pairs) of - {Assoc,[]} -> - Kes = [#k_map_pair{key=K,val=V}||{_,{assoc,K,V}} <- Assoc], - {#k_map{anno=A,op=assoc,var=Var,es=Kes},Esp,St1}; - {[],Exact} -> - Kes = [#k_map_pair{key=K,val=V}||{_,{exact,K,V}} <- Exact], - {#k_map{anno=A,op=exact,var=Var,es=Kes},Esp,St1}; - {Assoc,Exact} -> - Kes1 = [#k_map_pair{key=K,val=V}||{_,{assoc,K,V}} <- Assoc], - {Mvar,Em,St2} = force_atomic(#k_map{anno=A,op=assoc,var=Var,es=Kes1},St1), - Kes2 = [#k_map_pair{key=K,val=V}||{_,{exact,K,V}} <- Exact], - {#k_map{anno=A,op=exact,var=Mvar,es=Kes2},Esp ++ Em,St2} - + map_split_pairs_1(A, Var, Pairs, Esp, St1). + +map_split_pairs_1(A, Map0, [{Op,Key,Val}|Pairs1]=Pairs0, Esp0, St0) -> + {Map1,Em,St1} = force_atomic(Map0, St0), + case Key of + #k_var{} -> + %% Don't combine variable keys with other keys. + Kes = [#k_map_pair{key=Key,val=Val}], + Map = #k_map{anno=A,op=Op,var=Map1,es=Kes}, + map_split_pairs_1(A, Map, Pairs1, Esp0 ++ Em, St1); + _ -> + %% Literal key. Split off all literal keys. + {L,Pairs} = splitwith(fun({_,#k_var{},_}) -> false; + ({_,_,_}) -> true + end, Pairs0), + {Map,Esp,St2} = map_group_pairs(A, Map1, L, Esp0 ++ Em, St1), + map_split_pairs_1(A, Map, Pairs, Esp, St2) + end; +map_split_pairs_1(_, Map, [], Esp, St0) -> + {Map,Esp,St0}. + +map_group_pairs(A, Var, Pairs0, Esp, St0) -> + Pairs = map_remove_dup_keys(Pairs0), + Assoc = [#k_map_pair{key=K,val=V} || {_,{assoc,K,V}} <- Pairs], + Exact = [#k_map_pair{key=K,val=V} || {_,{exact,K,V}} <- Pairs], + case {Assoc,Exact} of + {[_|_],[]} -> + {#k_map{anno=A,op=assoc,var=Var,es=Assoc},Esp,St0}; + {[],[_|_]} -> + {#k_map{anno=A,op=exact,var=Var,es=Exact},Esp,St0}; + {[_|_],[_|_]} -> + Map = #k_map{anno=A,op=assoc,var=Var,es=Assoc}, + {Mvar,Em,St1} = force_atomic(Map, St0), + {#k_map{anno=A,op=exact,var=Mvar,es=Exact},Esp ++ Em,St1} end. -%% Group map by Assoc operations and Exact operations - -map_group_pairs(Es) -> - Groups = dict:to_list(map_group_pairs(Es,dict:new())), - partition(fun({_,{Op,_,_}}) -> Op =:= assoc end, Groups). - -map_group_pairs([{assoc,K,V}|Es0],Used0) -> - Used1 = case map_key_is_used(K,Used0) of - {ok, {assoc,_,_}} -> map_key_set_used(K,{assoc,K,V},Used0); - {ok, {exact,_,_}} -> map_key_set_used(K,{exact,K,V},Used0); - _ -> map_key_set_used(K,{assoc,K,V},Used0) - end, - map_group_pairs(Es0,Used1); -map_group_pairs([{exact,K,V}|Es0],Used0) -> - Used1 = case map_key_is_used(K,Used0) of - {ok, {assoc,_,_}} -> map_key_set_used(K,{assoc,K,V},Used0); - {ok, {exact,_,_}} -> map_key_set_used(K,{exact,K,V},Used0); - _ -> map_key_set_used(K,{exact,K,V},Used0) - end, - map_group_pairs(Es0,Used1); -map_group_pairs([],Used) -> - Used. +map_remove_dup_keys(Es) -> + dict:to_list(map_remove_dup_keys(Es, dict:new())). -map_key_set_used(K,How,Used) -> - dict:store(map_key_clean(K),How,Used). - -map_key_is_used(K,Used) -> - dict:find(map_key_clean(K),Used). +map_remove_dup_keys([{assoc,K0,V}|Es0],Used0) -> + K = map_key_clean(K0), + Op = case dict:find(K, Used0) of + {ok,{exact,_,_}} -> exact; + _ -> assoc + end, + Used1 = dict:store(K, {Op,K0,V}, Used0), + map_remove_dup_keys(Es0, Used1); +map_remove_dup_keys([{exact,K0,V}|Es0],Used0) -> + K = map_key_clean(K0), + Op = case dict:find(K, Used0) of + {ok,{assoc,_,_}} -> assoc; + _ -> exact + end, + Used1 = dict:store(K, {Op,K0,V}, Used0), + map_remove_dup_keys(Es0, Used1); +map_remove_dup_keys([], Used) -> Used. -%% Be explicit instead of using set_kanno(K,[]) +%% Be explicit instead of using set_kanno(K, []). map_key_clean(#k_var{name=V}) -> {var,V}; map_key_clean(#k_literal{val=V}) -> {lit,V}; map_key_clean(#k_int{val=V}) -> {lit,V}; -- cgit v1.2.3 From 70478d290046844b504c8fe0643e499009b735b4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Wed, 28 Jan 2015 15:26:52 +0100 Subject: cerl: Remove a clause in fold_map_pairs/3 that will never be reached --- lib/compiler/src/cerl.erl | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'lib/compiler/src') diff --git a/lib/compiler/src/cerl.erl b/lib/compiler/src/cerl.erl index 705c87539e..1a2957ee31 100644 --- a/lib/compiler/src/cerl.erl +++ b/lib/compiler/src/cerl.erl @@ -1644,9 +1644,7 @@ fold_map_pairs(As,[#c_map_pair{op=#c_literal{val=exact},key=Ck,val=Cv}=E|Es],M) end; false -> #c_map{arg=#c_literal{val=M,anno=As}, es=[E|Es], anno=As } - end; -fold_map_pairs(As,Es,M) -> - #c_map{arg=#c_literal{val=M,anno=As}, es=Es, anno=As }. + end. -spec update_c_map(c_map(), cerl(), [cerl()]) -> c_map() | c_literal(). -- cgit v1.2.3