aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorBjörn Gustavsson <[email protected]>2012-12-11 09:12:47 +0100
committerBjörn Gustavsson <[email protected]>2012-12-18 14:46:14 +0100
commit89b47bd53200816ac058eafe0b7d00745183fee4 (patch)
treea96fe6c84ba203620e8247fc7c80ec3b8b6c04fc
parentb82d7370ddef1a91e960486716c8dea3d31c2e3b (diff)
downloadotp-89b47bd53200816ac058eafe0b7d00745183fee4.tar.gz
otp-89b47bd53200816ac058eafe0b7d00745183fee4.tar.bz2
otp-89b47bd53200816ac058eafe0b7d00745183fee4.zip
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.
-rw-r--r--lib/asn1/src/asn1ct_check.erl72
-rw-r--r--lib/asn1/test/asn1_SUITE.erl31
-rw-r--r--lib/asn1/test/asn1_SUITE_data/ConstraintEquivalence.asn142
3 files changed, 116 insertions, 29 deletions
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<A2 -> true;
({_,{A,B1}},{_,{A,B2}}) when B1=<B2->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,
- Ub2>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=<Ub1->
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