From 89b47bd53200816ac058eafe0b7d00745183fee4 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Bj=C3=B6rn=20Gustavsson?= Date: Tue, 11 Dec 2012 09:12:47 +0100 Subject: Add a test case for constraint equivalence The constraint simplification pass need to be seriously rethought and rewritten. As a starting point, add a test case to test that equivalent ways to write a constraint are reduced to the same simplified constraint. Fix a few obvious bugs to make the test cases to pass. --- lib/asn1/src/asn1ct_check.erl | 72 +++++++++++++--------- lib/asn1/test/asn1_SUITE.erl | 31 +++++++++- .../asn1_SUITE_data/ConstraintEquivalence.asn1 | 42 +++++++++++++ 3 files changed, 116 insertions(+), 29 deletions(-) create mode 100644 lib/asn1/test/asn1_SUITE_data/ConstraintEquivalence.asn1 (limited to 'lib/asn1') diff --git a/lib/asn1/src/asn1ct_check.erl b/lib/asn1/src/asn1ct_check.erl index fe1b2e14a8..dd77085c39 100644 --- a/lib/asn1/src/asn1ct_check.erl +++ b/lib/asn1/src/asn1ct_check.erl @@ -4340,11 +4340,33 @@ permitted_alphabet_merge([C1|Rest],UorI,Acc) -> %% there will be no extension if the last constraint is without extension. %% The rootset of all constraints are considered in the "outermoust %% intersection". See section 13.1.2 in Dubuisson. -constraint_merge(_S,C=[H])when is_tuple(H) -> +constraint_merge(St, Cs0) -> + Cs = constraint_merge_1(St, Cs0), + normalize_cs(Cs). + +normalize_cs([{'SingleValue',[V]}|Cs]) -> + [{'SingleValue',V}|normalize_cs(Cs)]; +normalize_cs([{'SingleValue',[_|_]=L0}|Cs]) -> + [H|T] = L = lists:usort(L0), + [case is_range(H, T) of + false -> {'SingleValue',L}; + true -> {'ValueRange',{H,lists:last(T)}} + end|normalize_cs(Cs)]; +normalize_cs([{'ValueRange',{Sv,Sv}}|Cs]) -> + [{'SingleValue',Sv}|normalize_cs(Cs)]; +normalize_cs([{'ValueRange',{'MIN','MAX'}}|Cs]) -> + normalize_cs(Cs); +normalize_cs(Other) -> Other. + +is_range(Prev, [H|T]) when Prev =:= H - 1 -> is_range(H, T); +is_range(_, [_|_]) -> false; +is_range(_, []) -> true. + +constraint_merge_1(_S, [H]=C) when is_tuple(H) -> C; -constraint_merge(_S,[]) -> +constraint_merge_1(_S, []) -> []; -constraint_merge(S,C) -> +constraint_merge_1(S, C) -> %% skip all extension but the last extension C1 = filter_extensions(C), %% perform all internal level intersections, intersections first @@ -4367,17 +4389,16 @@ constraint_merge(S,C) -> %% get the least common size constraint SZs = get_constraints(C3,'SizeConstraint'), CombSZ = intersection_of_size(S,SZs), - CminusSVs=ordsets:subtract(ordsets:from_list(C3),ordsets:from_list(SVs)), - % CminusSVsVRs = ordsets:subtract(ordsets:from_list(CminusSVs), -% ordsets:from_list(VRs)), - RestC = ordsets:subtract(ordsets:from_list(CminusSVs), - ordsets:from_list(SZs)), + RestC = ordsets:subtract(ordsets:from_list(C3), + ordsets:from_list(SZs ++ VRs ++ SVs)), %% get the least common combined constraint. That is the union of each - %% deep costraint and merge of single value and value range constraints - NewCs = combine_constraints(S,CombSV,CombVR,CombSZ++RestC), - [X||X <- lists:flatten(NewCs), - X /= intersection, - X /= union]. + %% deep constraint and merge of single value and value range constraints. + %% FIXME: Removing 'intersection' from the flattened list essentially + %% means that intersections are converted to unions! + Cs = combine_constraints(S, CombSV, CombVR, CombSZ++RestC), + [X || X <- lists:flatten(Cs), + X =/= intersection, + X =/= union]. %% constraint_union(S,C) takes a list of constraints as input and %% merge them to a union. Unions are performed when two @@ -4407,16 +4428,16 @@ constraint_union(_S,C) -> constraint_union1(S,[A={'ValueRange',_},union,B={'ValueRange',_}|Rest],Acc) -> AunionB = constraint_union_vr([A,B]), - constraint_union1(S,Rest,Acc ++ AunionB); + constraint_union1(S, AunionB++Rest, Acc); constraint_union1(S,[A={'SingleValue',_},union,B={'SingleValue',_}|Rest],Acc) -> AunionB = constraint_union_sv(S,[A,B]), constraint_union1(S,Rest,Acc ++ AunionB); constraint_union1(S,[A={'SingleValue',_},union,B={'ValueRange',_}|Rest],Acc) -> AunionB = union_sv_vr(S,A,B), - constraint_union1(S,Rest,Acc ++ AunionB); + constraint_union1(S, AunionB++Rest, Acc); constraint_union1(S,[A={'ValueRange',_},union,B={'SingleValue',_}|Rest],Acc) -> AunionB = union_sv_vr(S,B,A), - constraint_union1(S,Rest,Acc ++ AunionB); + constraint_union1(S, AunionB++Rest, Acc); constraint_union1(S,[union|Rest],Acc) -> %skip when unsupported constraints constraint_union1(S,Rest,Acc); constraint_union1(S,[A|Rest],Acc) -> @@ -4449,15 +4470,8 @@ constraint_union_vr(VR) -> ({_,{A1,_B1}},{_,{A2,_B2}}) when is_integer(A1),is_integer(A2),A1 true; ({_,{A,B1}},{_,{A,B2}}) when B1=true; (_,_)->false end, - % sort and remove duplicates - SortedVR = lists:sort(Fun,VR), - RemoveDup = fun([],_) ->[]; - ([H],_) -> [H]; - ([H,H|T],F) -> F([H|T],F); - ([H|T],F) -> [H|F(T,F)] - end, - - constraint_union_vr(RemoveDup(SortedVR,RemoveDup),[]). + SortedVR = lists:usort(Fun,VR), + constraint_union_vr(SortedVR, []). constraint_union_vr([],Acc) -> lists:reverse(Acc); @@ -4467,8 +4481,8 @@ constraint_union_vr([{_,{Lb,Ub2}}|Rest],[{_,{Lb,_Ub1}}|Acc]) -> %Ub2 > Ub1 constraint_union_vr(Rest,[{'ValueRange',{Lb,Ub2}}|Acc]); constraint_union_vr([{_,{_,Ub}}|Rest],A=[{_,{_,Ub}}|_Acc]) -> constraint_union_vr(Rest,A); -constraint_union_vr([{_,{Lb2,Ub2}}|Rest],[{_,{Lb1,Ub1}}|Acc]) when Lb2=Ub1-> +constraint_union_vr([{_,{Lb2,Ub2}}|Rest], [{_,{Lb1,Ub1}}|Acc]) + when Ub1 =< Lb2, Ub1 < Ub2 -> constraint_union_vr(Rest,[{'ValueRange',{Lb1,Ub2}}|Acc]); constraint_union_vr([{_,{_,Ub2}}|Rest],A=[{_,{_,Ub1}}|_Acc]) when Ub2= constraint_union_vr(Rest,A); @@ -4589,9 +4603,11 @@ constraint_intersection(_S,C) -> constraint_intersection1(S,[A,intersection,B|Rest],Acc) -> AisecB = c_intersect(S,A,B), - constraint_intersection1(S,Rest,AisecB++Acc); + constraint_intersection1(S, AisecB++Rest, Acc); constraint_intersection1(S,[A|Rest],Acc) -> constraint_intersection1(S,Rest,[A|Acc]); +constraint_intersection1(_, [], [C]) -> + C; constraint_intersection1(_,[],Acc) -> lists:reverse(Acc). diff --git a/lib/asn1/test/asn1_SUITE.erl b/lib/asn1/test/asn1_SUITE.erl index f8ef1ac19a..3d3ed65a65 100644 --- a/lib/asn1/test/asn1_SUITE.erl +++ b/lib/asn1/test/asn1_SUITE.erl @@ -53,7 +53,8 @@ groups() -> [{compile, parallel([]), [c_syntax, c_string, - c_implicit_before_choice]}, + c_implicit_before_choice, + constraint_equivalence]}, {ber, parallel([]), [ber_choiceinseq, @@ -618,6 +619,34 @@ c_implicit_before_choice(Config, Rule, Opts) -> {error, _R2} = asn1ct:compile(filename:join(DataDir, "CCSNARG3"), [Rule, {outdir, CaseDir}|Opts]). +constraint_equivalence(Config) -> + DataDir = ?config(data_dir, Config), + CaseDir = ?config(case_dir, Config), + Asn1Spec = "ConstraintEquivalence", + Asn1Src = filename:join(DataDir, Asn1Spec), + ok = asn1ct:compile(Asn1Src, [abs,{outdir,CaseDir}]), + AbsFile = filename:join(CaseDir, Asn1Spec++".abs"), + {ok,Terms} = file:consult(AbsFile), + Cs = [begin + 'INTEGER' = element(3, Type), %Assertion. + Constraints = element(4, Type), + Name1 = atom_to_list(Name0), + {Name,_} = lists:splitwith(fun(C) -> C =/= $X end, Name1), + {Name,Constraints} + end || {typedef,_,_,Name0,Type} <- Terms], + R = sofs:relation(Cs, [{name,constraint}]), + F0 = sofs:relation_to_family(R), + F = sofs:to_external(F0), + Diff = [E || {_,L}=E <- F, length(L) > 1], + case Diff of + [] -> + ok; + [_|_] -> + io:put_chars("Not equivalent:\n"), + [io:format("~s: ~p\n", [N,D]) || {N,D} <- Diff], + test_server:fail(length(Diff)) + end. + parse(Config) -> [asn1_test_lib:compile(M, Config, [abs]) || M <- test_modules()]. diff --git a/lib/asn1/test/asn1_SUITE_data/ConstraintEquivalence.asn1 b/lib/asn1/test/asn1_SUITE_data/ConstraintEquivalence.asn1 new file mode 100644 index 0000000000..6a97c1b38e --- /dev/null +++ b/lib/asn1/test/asn1_SUITE_data/ConstraintEquivalence.asn1 @@ -0,0 +1,42 @@ +ConstraintEquivalence DEFINITIONS AUTOMATIC TAGS ::= +BEGIN + SingleValueX42 ::= INTEGER (42) + SingleValueX1 ::= INTEGER ((42) ^ (42)) + SingleValueX2 ::= INTEGER ((42) INTERSECTION (42)) + SingleValueX3 ::= INTEGER ((42) | (42)) + SingleValueX4 ::= INTEGER ((42) UNION (42)) + SingleValueX5 ::= INTEGER ((42) INTERSECTION (MIN..MAX)) + SingleValueX6 ::= INTEGER ((42) INTERSECTION (40..49)) + SingleValueX7 ::= INTEGER (42..42) + + UnconstrainedX0 ::= INTEGER + UnconstrainedX1 ::= INTEGER (MIN..MAX) + UnconstrainedX2 ::= INTEGER (1|(MIN..MAX)) + UnconstrainedX3 ::= INTEGER (1..10|(MIN..MAX)) + UnconstrainedX4 ::= INTEGER ((MIN..MAX)|9|10) + UnconstrainedX5 ::= INTEGER ((MIN..MAX)|10..20) + UnconstrainedX6 ::= INTEGER ((MIN..MAX) UNION (10..20)) + + RangeX00 ::= INTEGER (5..10) + RangeX01 ::= INTEGER (4<..<11) + RangeX02 ::= INTEGER (5..<11) + RangeX03 ::= INTEGER (4<..10) + RangeX04 ::= INTEGER (5|6|7|8|9|10) + RangeX05 ::= INTEGER (10|9|8|7|6|5) + RangeX06 ::= INTEGER (5|6|7..10) + + RangeX10 ::= INTEGER ((5..6) UNION (7..8) UNION (9|10)) + RangeX11 ::= INTEGER ((5|6) UNION (7..8) UNION (9|10)) + RangeX12 ::= INTEGER ((5|6) UNION (7|8) UNION (9|10)) + RangeX13 ::= INTEGER ((5|6) UNION (7) UNION (8..10)) + RangeX14 ::= INTEGER ((5|6) UNION (7) UNION (8..10)) + RangeX15 ::= INTEGER ((5|6) UNION (7) UNION ((8..8)|(9..9)|(10))) + RangeX16 ::= INTEGER ((5|6) UNION (7) UNION (7<..<11)) + + RangeX20 ::= INTEGER (0..20) (5..10) + RangeX21 ::= INTEGER (0..10) (5..20) + RangeX22 ::= INTEGER (0..10) (5..20) (MIN..MAX) + RangeX23 ::= INTEGER ((0..10) INTERSECTION (5..20) ^ (MIN..MAX)) + RangeX24 ::= INTEGER ((5|6|7|8|9|10) INTERSECTION (5..20) ^ (MIN..MAX)) + +END -- cgit v1.2.3