From commits-return-32103-archive-asf-public=cust-asf.ponee.io@couchdb.apache.org Fri Feb 2 20:45:28 2018 Return-Path: X-Original-To: archive-asf-public@eu.ponee.io Delivered-To: archive-asf-public@eu.ponee.io Received: from cust-asf.ponee.io (cust-asf.ponee.io [163.172.22.183]) by mx-eu-01.ponee.io (Postfix) with ESMTP id 86D86180608 for ; Fri, 2 Feb 2018 20:45:28 +0100 (CET) Received: by cust-asf.ponee.io (Postfix) id 769B6160C25; Fri, 2 Feb 2018 19:45:28 +0000 (UTC) Delivered-To: archive-asf-public@cust-asf.ponee.io Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by cust-asf.ponee.io (Postfix) with SMTP id 71272160C49 for ; Fri, 2 Feb 2018 20:45:27 +0100 (CET) Received: (qmail 94391 invoked by uid 500); 2 Feb 2018 19:45:26 -0000 Mailing-List: contact commits-help@couchdb.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@couchdb.apache.org Delivered-To: mailing list commits@couchdb.apache.org Received: (qmail 94381 invoked by uid 99); 2 Feb 2018 19:45:26 -0000 Received: from ec2-52-202-80-70.compute-1.amazonaws.com (HELO gitbox.apache.org) (52.202.80.70) by apache.org (qpsmtpd/0.29) with ESMTP; Fri, 02 Feb 2018 19:45:26 +0000 Received: by gitbox.apache.org (ASF Mail Server at gitbox.apache.org, from userid 33) id 327F5859D0; Fri, 2 Feb 2018 19:45:25 +0000 (UTC) Date: Fri, 02 Feb 2018 19:45:26 +0000 To: "commits@couchdb.apache.org" Subject: [couchdb] 01/01: Key tree property tests MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 8bit From: vatamane@apache.org In-Reply-To: <151760072499.30955.9557417275005751691@gitbox.apache.org> References: <151760072499.30955.9557417275005751691@gitbox.apache.org> X-Git-Host: gitbox.apache.org X-Git-Repo: couchdb X-Git-Refname: refs/heads/property-tests-for-couch-key-tree X-Git-Reftype: branch X-Git-Rev: f215d7ec1aa9e342624eb6e14edbabb4046e9cf5 X-Git-NotificationType: diff X-Git-Multimail-Version: 1.5.dev Auto-Submitted: auto-generated Message-Id: <20180202194525.327F5859D0@gitbox.apache.org> This is an automated email from the ASF dual-hosted git repository. vatamane pushed a commit to branch property-tests-for-couch-key-tree in repository https://gitbox.apache.org/repos/asf/couchdb.git commit f215d7ec1aa9e342624eb6e14edbabb4046e9cf5 Author: Nick Vatamaniuc AuthorDate: Fri Feb 2 12:08:08 2018 -0500 Key tree property tests Key tree module is a candidate to use property tests on as it mostly deals with manipulating a single data structure and functions are referentially transparent, that is, they aren't many side-effects like IO generated. Property tests are currently run as part of the EUnit testing framework. In the future it might be interesting to have a longer or more thourough runs to perhaps catch more edge cases. To run the tests used Triq. It is an Apache licensed property testing tool. It is not as full features as the commerical and the other, GPL-licensed one, but seems to have the basics and should be easy to integrate with CouchDB's code. To run the test: make eunit apps=couch suites=couch_key_tree_prop_tests To play with the code in the interpreter can try this script: ``` set +e make > /dev/null exec erl \ -pa src/couch/ebin \ -pa src/triq/ebin/ \ -pa src/config/ebin \ -eval "application:start(config), code:load_file(couch_key_tree), code:load_file(triq)" ``` --- Makefile | 2 +- Makefile.win | 2 +- rebar.config.script | 5 +- src/couch/test/couch_key_tree_prop_tests.erl | 349 +++++++++++++++++++++++++++ 4 files changed, 354 insertions(+), 4 deletions(-) diff --git a/Makefile b/Makefile index bd3b8ac..4d9d2ea 100644 --- a/Makefile +++ b/Makefile @@ -21,7 +21,7 @@ DESTDIR= # Rebar options apps= -skip_deps=folsom,meck,mochiweb,proper,snappy +skip_deps=folsom,meck,mochiweb,triq,snappy suites= tests= diff --git a/Makefile.win b/Makefile.win index 7ff0ab5..01efc5a 100644 --- a/Makefile.win +++ b/Makefile.win @@ -27,7 +27,7 @@ DESTDIR= # Rebar options apps= -skip_deps=folsom,meck,mochiweb,proper,snappy +skip_deps=folsom,meck,mochiweb,triq,snappy suites= tests= diff --git a/rebar.config.script b/rebar.config.script index 60d2e31..69ec709 100644 --- a/rebar.config.script +++ b/rebar.config.script @@ -64,8 +64,9 @@ DepDescs = [ {ibrowse, "ibrowse", {tag, "CouchDB-4.0.1"}}, {jiffy, "jiffy", {tag, "CouchDB-0.14.11-2"}}, {mochiweb, "mochiweb", {tag, "CouchDB-2.12.0-1"}}, -{meck, "meck", {tag, "0.8.8"}} - +{meck, "meck", {tag, "0.8.8"}}, +{triq, {url, "https://github.com/triqng/triq.git"}, + "1a9b022cc0432c9314f6f06c61dc375e474b5573"} ], diff --git a/src/couch/test/couch_key_tree_prop_tests.erl b/src/couch/test/couch_key_tree_prop_tests.erl new file mode 100644 index 0000000..25ce158 --- /dev/null +++ b/src/couch/test/couch_key_tree_prop_tests.erl @@ -0,0 +1,349 @@ +% 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(couch_key_tree_prop_tests). + +-include_lib("triq/include/triq.hrl"). +-include_lib("eunit/include/eunit.hrl"). + +-define(TEST_TIMEOUT, 300). +-define(SIZE_REDUCTION, 3). % How much to reduce size with tree depth. +-define(MAX_BRANCHES, 4). % Maximum number of branches. +-define(RAND_SIZE, 1 bsl 60). + + +% +% EUnit setup / teardown +% + +couch_key_tree_prop_test_() -> + { + "Couch Key Tree Property Tests", + { + setup, + fun setup/0, fun teardown/1, + { + timeout, ?TEST_TIMEOUT, + ?_test(?assertEqual(true, triq:module(?MODULE))) + } + } + }. + + +% +% Properties +% + + +prop_revtree_merge_with_subset_of_own_nodes() -> + ?FORALL(Revs, g_revs(), + ?FORALL({RevTree, Branch}, {g_revtree(Revs), g_revtree(Revs, 1)}, + ?IMPLIES(length(Branch) > 0, begin + [Tree | _ ] = Branch, + %?debugFmt("RevTree:~p Tree:~p", [RevTree, Tree]), + {Merged, Result} = couch_key_tree:merge(RevTree, Tree), + MergedKeys = lists:usort(keylist(Merged)), + InputKeys = lists:usort(keylist(RevTree) ++ keylist(Tree)), + lists:member(Result, [new_leaf, new_branch, internal_node]) + andalso MergedKeys == InputKeys + end) + ) + ). + + + +% +% Generators +% + +% Generate a full rev tree. Most of the forms are just there to set up default +% parameters, _revtree/3 does all heavy lifting. +% + +%g_revtree() -> +% ?SIZED(Size, g_revtree(Size)). + + +g_revtree(Size) when is_integer(Size) -> + g_revtree(Size, [], ?MAX_BRANCHES); +g_revtree(Revs) when is_list(Revs) -> + ?SIZED(Size, g_revtree(Size, Revs, ?MAX_BRANCHES)). + + +g_revtree(Size, Revs) when is_integer(Size), is_list(Revs) -> + g_revtree(Size, Revs, ?MAX_BRANCHES); +g_revtree(Revs, MaxBranches) when is_list(Revs), is_integer(MaxBranches) -> + ?SIZED(Size, g_revtree(Size, Revs, MaxBranches)). + + +g_revtree(0, _Revs, _MaxBranches) -> + []; +g_revtree(Size, ERevs, MaxBranches) -> + ?LET({Depth, Revs}, {g_stem_depth(Size), g_revs(Size, ERevs)}, + begin + SmallerSize = Size div ?SIZE_REDUCTION, + ?DELAY([{Depth, g_treenode(SmallerSize, Revs, MaxBranches)}]) + end + ). + + +% Generate a tree node and then recursively generate its children. +% +g_treenode(0, Revs, _) -> + {elements(Revs), x, []}; +g_treenode(Size, Revs, MaxBranches) -> + ?DELAY(?LET(N, int(0, MaxBranches), + begin + %?debugFmt("----- g_treenode S:~p N:~p",[Size,N]), + [Rev | ChildRevs] = Revs, + {Rev, x, g_nodes(Size div ?SIZE_REDUCTION, N, ChildRevs, MaxBranches)} + end + )). + + +% Generate a list of child nodes. Depending on how many children there are +% the pre-generarated revision list is split into that many sublists. +% +g_nodes(0, _N, _Revs, _MaxBranches) -> + %?debugFmt("..................... g_nodes Size=0 N:~p", [_N]), + []; +g_nodes(_Size, 0, _Revs, _MaxBranches) -> + %?debugFmt("++++++++++++++++++++++ g_nodes N=0 Size:~p", [_Size]), + []; +g_nodes(Size, ChildCount, Revs, MaxBranches) -> + ?LETSHRINK( + ChildNodes, + begin + ChildRevList = child_revs(ChildCount, Revs, Size, MaxBranches), + %?debugFmt("******* g_nodes ChildRevList Size:~p ChildCount:~p RevList:~p",[Size, ChildCount, length(ChildRevList)]), + [g_treenode(Size, ChildRevs, MaxBranches) || ChildRevs <- ChildRevList] + end, + ordered_nodes(ChildNodes) + ). + + +% Generate each subtree's stem depth +% +g_stem_depth(Size) -> + choose(0, 4 * expected_height(Size, ?SIZE_REDUCTION)). + + +% Uses the shuffle/1 function to shuffle the input list. Unshuffled list is +% used as the shrink value. +% +g_shuffle(L) when is_list(L) -> + triq_dom:domain(g_shuffle, + fun(Self, _Size) -> {Self, shuffle(L)} end, + fun(Self, _Val) -> {Self, L} end + ). + + +% Wrapper to make a list shuffling generator that doesn't shrink +% +g_shuffle_noshrink(L) when is_list(L) -> + triq_dom:noshrink(g_shuffle(L)). + + +% Generate shuffled sublists up to N items long from a list. +% +g_shuffled_sublists(L, N) -> + ?LET(Shuffled, g_shuffle_noshrink(L), lists:sublist(Shuffled, N)). + + +% Generate revision lists. +% +g_revs() -> + ?SIZED(Size, g_revs(Size)). + + +g_revs(Size) when is_integer(Size) -> + g_revs(Size, []). + + +g_revs(Size, Existing) when is_integer(Size), is_list(Existing) -> + Expected = keys_needed(Size, ?SIZE_REDUCTION, ?MAX_BRANCHES), + Revs = revs(Expected, Existing), + case length(Revs) > Expected of + true -> % have extra, try various sublists + g_shuffled_sublists(Revs, Expected); + false -> + triq_dom:return(Revs) + end. + + +% +% Helper functions +% + + +% Shufle a list of items. Tag each item with a random number then sort +% the list and remove the tags. +% +shuffle(L) -> + Tagged = [{triq_rnd:uniform(), X} || X <- L], + [X || {_, X} <- lists:sort(Tagged)]. + + +% Generate list of relateively unique large random numbers +rand_list(N) when N =< 0 -> + []; +rand_list(N) -> + [triq_rnd:uniform(?RAND_SIZE) || _ <- lists:seq(1, N)]. + + +% Generate a list of revisions to be used as key in revision trees. Expected +% must the number of maximum expected nodes in a revision tree. Existing is an +% optional list revisions which must be included in the result. The output list +% is sorted. +revs(0, _Existing) -> + []; +revs(Expected, Existing) when is_integer(Expected), is_list(Existing) -> + Need = Expected - length(Existing), + lists:usort(lists:append(Existing, rand_list(Need))). + + +% Get the list of all the keys in a revision tree. The input can also be a +% an individual tree (tagged with the depth to virtual root) or a node. +% Yes, this is not tail recursive but the idea is to keep it simple. +% +keylist({_D, Node}) when is_tuple(Node) -> + keylist(Node); +keylist({K, _V, Nodes}) -> + [K | keylist(Nodes)]; +keylist(Nodes) -> + lists:append([keylist(Node) || Node <- Nodes]). + + +% Get lists of all the keys at each depth level. Result is an orddict that +% looks like [{depth, [key]}]. The depth used here is the "virtual" depth as +% indicated by the stemmed depth tag that goes with every top level subtree. +% +levels([]) -> + orddict:new(); +levels(RevTree) when is_list(RevTree) -> + lists:foldl(fun(T, Dict) -> levels(T, Dict) end, orddict:new(), RevTree). + + +levels({Depth, Node}, Dict) when is_tuple(Node) -> + levels(Node, Depth, Dict). + + +levels({K, _V, Nodes}, Depth, Dict) -> + Dict1 = case orddict:is_key(Depth, Dict) of + true -> orddict:append(Depth, K, Dict); + false -> orddict:store(Depth, [K], Dict) + end, + levels(Nodes, Depth + 1, Dict1); +levels(Nodes, Depth, Dict) -> + lists:foldl(fun(Node, AccDict) -> + levels(Node, Depth, AccDict) + end, Dict, Nodes). + + +% Get the maximum depth of a revtree. The depth is "virtual" as it takes into +% account the distance to the now stemmed root node as indicated by the top +% level subtrees. +% +depth([]) -> + 0; +depth(RevTree) when is_list(RevTree) -> + lists:max([depth(T) || T <- RevTree]); +depth({Depth, Node}) when is_tuple(Node) -> + depth(Node, Depth - 1). + + +depth({_K, _V, Nodes}, Depth) -> + depth(Nodes, Depth + 1); +depth([], Depth) -> + Depth; +depth(Nodes, Depth) -> + lists:max([depth(Node, Depth) || Node <- Nodes]). + + +% Return an ordered list of revtree nodes. When sorting only immediate keys +% (revisions) are looked at and comparison doesn't descent into the treee. +% +ordered_nodes(Nodes) -> + lists:sort(fun({K1, _, _}, {K2, _, _}) -> K1 =< K2 end, Nodes). + + +% Calculate a maximum number of rev tree nodes needed for a tree of a given +% height and branchiness. Height is derived from Size and LevelReductionFactor, +% that is how big the sample should be and quickly the size parameter would +% shrink on each level. The formula used then is: +% +% N = (B ^ (H + 1) - 1) / (B - 1) +keys_needed(0, _, _) -> + 0; +keys_needed(Size, LevelReductionFactor, 1) -> + expected_height(Size, LevelReductionFactor); +keys_needed(Size, LevelReductionFactor, Branches) -> + Height = expected_height(Size, LevelReductionFactor), + ceil((math:pow(Branches, Height + 1) - 1) / (Branches - 1)). + + +% Calculate expected tree height for a given sample size and branchiness. +% At each step the size is divided by the reduction factor. +expected_height(Size, LevelReductionFactor) -> + ceil(log(LevelReductionFactor, Size)). + + +log(B, X) -> + math:log(X) / math:log(B). + + +% Checks if revisions in a revtree are unique. The observation is if +% the length of the list is the same as the length of the list with +% duplicates removed, then the list has not duplicates. +% +%is_unique(Nodes) -> +% Keys = keylist(Nodes), +% length(Keys) == length(lists:usort(Keys)). + + +% Distribute items in a list into roughly equal chunks of a given size. +% +distribute(_ChunkSize, []) -> + []; +distribute(ChunkSize, L) when ChunkSize >= length(L) -> + [L]; +distribute(ChunkSize, L) -> + {L1, L2} = lists:split(ChunkSize, L), + [L1 | distribute(ChunkSize, L2)]. + + +% Split a single (parent) revision list into chunks (sub-lists), one for each +% child. Also, for safety, double check that at this point in the process the +% list of revisions is sufficiently large. If it isn't something went wrong and +% a specific exception is thrown ({not_enough_revisions, Got, Needed}). +% +child_revs(ChildCount, Revs, Size, MaxBranches) -> + NeedKeys = keys_needed(Size, ?SIZE_REDUCTION, MaxBranches), + case length(Revs) >= NeedKeys of + true -> + ChunkSize = ceil(length(Revs) / ChildCount), + distribute(ChunkSize, Revs); + false -> + throw({not_enough_revisions, length(Revs), NeedKeys}) + end. + + +% Setup / Teardown functions. These are needed to mock the config get calls +% + +setup() -> + meck:new(config), + meck:expect(config, get, fun(_, _, Default) -> Default end). + +teardown(_) -> + meck:unload(config). -- To stop receiving notification emails like this one, please contact vatamane@apache.org.