From 5b7bf677f832311008c33a10729a9e8a6197a087 Mon Sep 17 00:00:00 2001 From: Fred Hebert Date: Sun, 6 Dec 2015 11:37:10 -0500 Subject: Add test cases for tuple deduplication (the tests fail) --- test/rebar_utils_SUITE.erl | 71 ++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 69 insertions(+), 2 deletions(-) diff --git a/test/rebar_utils_SUITE.erl b/test/rebar_utils_SUITE.erl index 24e8afe..42a9551 100644 --- a/test/rebar_utils_SUITE.erl +++ b/test/rebar_utils_SUITE.erl @@ -30,7 +30,8 @@ invalid_otp_version/1, nonblacklisted_otp_version/1, blacklisted_otp_version/1, - sh_does_not_miss_messages/1]). + sh_does_not_miss_messages/1, + tup_merge/1]). -include_lib("common_test/include/ct.hrl"). -include_lib("eunit/include/eunit.hrl"). @@ -44,7 +45,8 @@ end_per_testcase(_, _Config) -> all() -> [{group, args_to_tasks}, - sh_does_not_miss_messages]. + sh_does_not_miss_messages, + tup_merge]. groups() -> [{args_to_tasks, [], [empty_arglist, @@ -198,3 +200,68 @@ sh_does_not_miss_messages(_Config) -> false end, AnyMessageRemained = false. + +tup_merge(_Config) -> + ?assertEqual( + [a,{a,a},{a,a,a},{a,b},{a,b,b},b,{b,a},{b,a,a},{b,b},{b,b,b},z,{z,a},{z,a,a},{z,b},{z,b,b}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([a,{a,a},{a,a,a},b,{b,a},{b,a,a},z,{z,a},{z,a,a}]), + rebar_utils:tup_sort([a,{a,b},{a,b,b},b,{b,b},{b,b,b},z,{z,b},{z,b,b}]) + ) + ), + ?assertEqual( + [a,{a,b},{a,b,b},{a,a},{a,a,a},b,{b,b},{b,b,b},{b,a},{b,a,a},z,{z,b},{z,b,b},{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([a,{a,b},{a,b,b},b,{b,b},{b,b,b},z,{z,b},{z,b,b}]), + rebar_utils:tup_sort([a,{a,a},{a,a,a},b,{b,a},{b,a,a},z,{z,a},{z,a,a}]) + ) + ), + ?assertEqual( + [a,{a,b},{a,b,b},{a,a},{a,a,a},b,{b,b},{b,b,b},{b,a},{b,a,a},z,{z,b},{z,b,b},{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([a,b,z,{a,b},{b,b},{z,b},{a,b,b},{b,b,b},{z,b,b}]), + rebar_utils:tup_sort([a,{a,a},{a,a,a},b,{b,a},{b,a,a},z,{z,a},{z,a,a}]) + ) + ), + ?assertEqual( + [{a,b},a,{a,b,b},{a,a},{a,a,a},{b,b},b,{b,b,b},{b,a},{b,a,a},{z,b},z,{z,b,b},{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([{a,b},{b,b},{z,b},a,b,z,{a,b,b},{b,b,b},{z,b,b}]), + rebar_utils:tup_sort([a,{a,a},{a,a,a},b,{b,a},{b,a,a},z,{z,a},{z,a,a}]) + ) + ), + ?assertEqual( + [a,{a,b},{a,b,b},{a,a},{a,a,a},b,{b,b},{b,b,b},{b,a},{b,a,a},z,{z,b},{z,b,b},{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([a,{a,b},{a,b,b},b,{b,b},{b,b,b},z,{z,b},{z,b,b}]), + rebar_utils:tup_sort([{a,a},a,{a,a,a},{b,a},b,{b,a,a},{z,a},z,{z,a,a}]) + ) + ), + ?assertEqual( + [{a,b},a,{a,b,b},{a,a},{a,a,a},{b,b},b,{b,b,b},{b,a},{b,a,a},{z,b},z,{z,b,b},{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([{a,b},{b,b},{z,b},a,b,z,{a,b,b},{b,b,b},{z,b,b}]), + rebar_utils:tup_sort([{a,a},a,{a,a,a},{b,a},b,{b,a,a},{z,a},z,{z,a,a}]) + ) + ), + ?assertEqual( + [{a,b},{a,b,b},a,{a,a},{a,a,a},{b,b},{b,b,b},b,{b,a},{b,a,a},{z,b},{z,b,b},z,{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([{a,b},{a,b,b},{b,b},{b,b,b},{z,b},{z,b,b},a,b,z]), + rebar_utils:tup_sort([{a,a},{a,a,a},a,{b,a},{b,a,a},b,{z,a},{z,a,a},z]) + ) + ), + ?assertEqual( + [{a,b},{a,b,b},a,{a,a},{a,a,a},{b,b},{b,b,b},b,{b,a},{b,a,a},{z,b},{z,b,b},z,{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([{a,b},{a,b,b},{b,b},{b,b,b},{z,b},{z,b,b},a,b,z]), + rebar_utils:tup_sort([{a,a},{a,b},{a,a,a},{a,b,b},a,{b,a},{b,a,a},b,{z,a},{z,a,a},z]) + ) + ), + ?assertEqual( + [{a,b,b},{a,b},a,{a,a},{a,a,a},{b,b},{b,b,b},b,{b,a,a},{b,a},{z,b},{z,b,b},z,{z,a},{z,a,a}], + rebar_utils:tup_umerge( + rebar_utils:tup_sort([{a,b,b},{b,b},{a,b},{b,b,b},{z,b},{z,b,b},a,b,z]), + rebar_utils:tup_sort([{a,a},{a,a,a},a,{b,a,a},b,{z,a},{z,a,a},{b,a},z]) + ) + ). -- cgit v1.1 From f0876ae8c751b4083eadb81a14d000dcd59eeeb7 Mon Sep 17 00:00:00 2001 From: Fred Hebert Date: Sun, 6 Dec 2015 11:38:15 -0500 Subject: Fix tuple umerging - proper segregation of comparison between tuple terms and non-tuple terms. Guards weren't specific enough and that meant the wrong clauses of guards would be triggered - proper deduplication of entries in the list. An additional N passes are required (we co-opt the reverse step to be more efficient) because while the original lists:umerge easily removes dupes, this is requiring more logic here since `[a,{a,b},{a,b,c},a,{a,b,c}]` is a possible interleaving and we'd want `[a,{a,b},{a,b,c}]` -- comparison of direct neighbours isn't enough. --- src/rebar_utils.erl | 25 ++++++++++++++++++------- 1 file changed, 18 insertions(+), 7 deletions(-) diff --git a/src/rebar_utils.erl b/src/rebar_utils.erl index ea60e42..9fe22ea 100644 --- a/src/rebar_utils.erl +++ b/src/rebar_utils.erl @@ -285,7 +285,18 @@ tup_umerge(NewList, OldList) -> tup_umerge_([], Olds) -> Olds; tup_umerge_([New|News], Olds) -> - lists:reverse(umerge(News, Olds, [], New)). + tup_umerge_dedup_(umerge(News, Olds, [], New), []). + +%% removes 100% identical duplicate elements so that +%% `[a,{a,b},a,{a,c},a]' returns `[a,{a,b},{a,c}]'. +%% Operates on a reverted list that gets reversed as part of this pass +tup_umerge_dedup_([], Acc) -> + Acc; +tup_umerge_dedup_([H|T], Acc) -> + case lists:member(H,T) of + true -> tup_umerge_dedup_(T, Acc); + false -> tup_umerge_dedup_(T, [H|Acc]) + end. tup_find(_Elem, []) -> false; @@ -304,9 +315,9 @@ tup_find(Elem, [_Elem | Elems]) -> %% This is equivalent to umerge2_2 in the stdlib, except we use the expanded %% value/key only to compare umerge(News, [Old|Olds], Merged, Cmp) when element(1, Cmp) == element(1, Old); - element(1, Cmp) == Old; - Cmp == element(1, Old); - Cmp =< Old -> + element(1, Cmp) == Old andalso not is_tuple(Old); + Cmp == element(1, Old) andalso not is_tuple(Cmp); + Cmp =< Old andalso not is_tuple(Cmp) andalso not is_tuple(Old) -> umerge(News, Olds, [Cmp | Merged], Cmp, Old); umerge(News, [Old|Olds], Merged, Cmp) -> umerge(News, Olds, [Old | Merged], Cmp); @@ -320,9 +331,9 @@ umerge(News, [], Merged, Cmp) -> umerge([New|News], Olds, Merged, CmpMerged, Cmp) when CmpMerged == Cmp -> umerge(News, Olds, Merged, New); umerge([New|News], Olds, Merged, _CmpMerged, Cmp) when element(1,New) == element(1, Cmp); - element(1,New) == Cmp; - New == element(1, Cmp); - New =< Cmp -> + element(1,New) == Cmp andalso not is_tuple(Cmp); + New == element(1, Cmp) andalso not is_tuple(New); + New =< Cmp andalso not is_tuple(New) andalso not is_tuple(Cmp) -> umerge(News, Olds, [New | Merged], New, Cmp); umerge([New|News], Olds, Merged, _CmpMerged, Cmp) -> % > umerge(News, Olds, [Cmp | Merged], New); -- cgit v1.1