[couchdb] branch shard-split updated: Property tests for mem3_util:get_ring() function

[va...@apache.org]

This is an automated email from the ASF dual-hosted git repository.

vatamane pushed a commit to branch shard-split
in repository https://gitbox.apache.org/repos/asf/couchdb.git


The following commit(s) were added to refs/heads/shard-split by this push:
     new 696ed75  Property tests for mem3_util:get_ring() function
696ed75 is described below

commit 696ed754ddb5fe0f765f9a4ba05fd921fdd07265
Author: Nick Vatamaniuc <va...@apache.org>
AuthorDate: Thu Feb 14 12:05:32 2019 -0500

    Property tests for mem3_util:get_ring() function
---
 src/mem3/src/mem3_util.erl             |  8 +++-
 src/mem3/test/mem3_ring_prop_tests.erl | 84 ++++++++++++++++++++++++++++++++++
 2 files changed, 91 insertions(+), 1 deletion(-)

diff --git a/src/mem3/src/mem3_util.erl b/src/mem3/src/mem3_util.erl
index 8575e66..af30fb0 100644
--- a/src/mem3/src/mem3_util.erl
+++ b/src/mem3/src/mem3_util.erl
@@ -24,6 +24,7 @@
     range_overlap/2,
     get_ring/1,
     get_ring/2,
+    get_ring/3,
     get_ring/4,
     non_overlapping_shards/1,
     non_overlapping_shards/3
@@ -411,10 +412,15 @@ non_overlapping_shards(Shards, Start, End) ->
 get_ring(Ranges) ->
     get_ring(Ranges, fun sort_ranges_fun/2, 0, ?RING_END).
 
+
 get_ring(Ranges, SortFun) when is_function(SortFun, 2) ->
     get_ring(Ranges, SortFun, 0, ?RING_END).
 
 
+get_ring(Ranges, Start, End) when is_integer(Start), is_integer(End),
+        Start >= 0, End >= 0, Start =< End ->
+    get_ring(Ranges, fun sort_ranges_fun/2, Start, End).
+
 % Build a ring out of a list of possibly overlapping ranges. If a ring cannot
 % be built then [] is returned. Start and End supply a custom range such that
 % only intervals in that range will be considered. SortFun is a custom sorting
@@ -423,7 +429,7 @@ get_ring(Ranges, SortFun) when is_function(SortFun, 2) ->
 % shortest ranges first (and thus have more total shards) or longer or any
 % other scheme.
 %
-get_ring([], _SortFun, _Begin, _End) ->
+get_ring([], _SortFun, _Start, _End) ->
     [];
 get_ring(Ranges, SortFun, Start, End) when is_function(SortFun, 2),
         is_integer(Start), is_integer(End),
diff --git a/src/mem3/test/mem3_ring_prop_tests.erl b/src/mem3/test/mem3_ring_prop_tests.erl
new file mode 100644
index 0000000..0fe6efb
--- /dev/null
+++ b/src/mem3/test/mem3_ring_prop_tests.erl
@@ -0,0 +1,84 @@
+% 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.
+
+-module(mem3_ring_prop_tests).
+
+
+-include_lib("triq/include/triq.hrl").
+-triq(eunit).
+
+-compile(export_all).
+
+
+% Properties
+
+prop_get_ring_with_connected_intervals() ->
+    ?FORALL({Start, End}, oneof(ranges()),
+        ?FORALL(Intervals, g_connected_intervals(Start, End),
+            mem3_util:get_ring(Intervals, Start, End) =/= []
+        )
+    ).
+
+
+prop_get_ring_with_disconnected_intervals() ->
+    ?FORALL({Start, End}, oneof(ranges()),
+        ?FORALL(Intervals, g_disconnected_intervals(Start, End),
+            mem3_util:get_ring(Intervals, Start, End) =:= []
+        )
+    ).
+
+
+% Generators
+
+ranges() ->
+    [{0,1}, {1, 10}, {0, 2 bsl 31 - 1}, {2 bsl 31 - 10, 2 bsl 31 - 1}].
+
+
+g_connected_intervals(Begin, End) ->
+    ?SIZED(Size, g_connected_intervals(Begin, End, 10 * Size)).
+
+
+g_connected_intervals(Begin, End, Split) when Begin =< End ->
+    ?LET(N, choose(0, Split),
+    begin
+        if
+            N == 0 ->
+                [{Begin, End}];
+            N > 0 ->
+                Ns = lists:seq(1, N - 1),
+                Bs = lists:usort([rand_range(Begin, End) || _ <- Ns]),
+                Es = [B - 1 || B <- Bs],
+                lists:zip([Begin] ++ Bs, Es ++ [End])
+        end
+    end).
+
+
+g_non_trivial_connected_intervals(Begin, End, Split) ->
+    ?SUCHTHAT(Connected, g_connected_intervals(Begin, End, Split),
+        length(Connected) > 1).
+
+
+g_disconnected_intervals(Begin, End) ->
+    ?SIZED(Size, g_disconnected_intervals(Begin, End, Size)).
+
+
+g_disconnected_intervals(Begin, End, Split) when Begin =< End ->
+    ?LET(Connected, g_non_trivial_connected_intervals(Begin, End, Split),
+    begin
+        I = triq_rnd:uniform(length(Connected)) - 1,
+        {Before, [_ | After]} = lists:split(I, Connected),
+        Before ++ After
+    end).
+
+
+rand_range(B, E) ->
+    B + triq_rnd:uniform(E - B).