Return-Path: X-Original-To: apmail-couchdb-commits-archive@www.apache.org Delivered-To: apmail-couchdb-commits-archive@www.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id B35EA11D1D for ; Thu, 28 Aug 2014 12:37:23 +0000 (UTC) Received: (qmail 79789 invoked by uid 500); 28 Aug 2014 12:37:23 -0000 Delivered-To: apmail-couchdb-commits-archive@couchdb.apache.org Received: (qmail 79726 invoked by uid 500); 28 Aug 2014 12:37:23 -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 79714 invoked by uid 99); 28 Aug 2014 12:37:23 -0000 Received: from tyr.zones.apache.org (HELO tyr.zones.apache.org) (140.211.11.114) by apache.org (qpsmtpd/0.29) with ESMTP; Thu, 28 Aug 2014 12:37:23 +0000 Received: by tyr.zones.apache.org (Postfix, from userid 65534) id 1AC80A02EAC; Thu, 28 Aug 2014 12:37:23 +0000 (UTC) Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: rnewson@apache.org To: commits@couchdb.apache.org Date: Thu, 28 Aug 2014 12:37:24 -0000 Message-Id: In-Reply-To: <4cd3c9085adc4e6aa1bc12b6e6af4b37@git.apache.org> References: <4cd3c9085adc4e6aa1bc12b6e6af4b37@git.apache.org> X-Mailer: ASF-Git Admin Mailer Subject: [02/23] couchdb commit: updated refs/heads/master to aa9f32d Be more specific on the merge result We have three results that can happen when merging a path into a revision tree: * We can extend a branch which replaces a leaf * We can create a new branch which results in a new leaf * We can land on an existing internal node The first result (new_leaf) means that there is no conflict in the update operation. The second (new_branch) means we branched a revision path which means the operation introduces a conflict. The third (internal_node) means that the merge was the result of an edit that has already been applied to this document. For the third case we have a subtle special case in that if we have deleted the document and want to recreate it into the same initial state we need to give the new state a different revision. The current code follows the edit path and extends the first deleted leaf it finds. BugzID: 25150 Conflicts: apps/couch/src/couch_key_tree.erl Project: http://git-wip-us.apache.org/repos/asf/couchdb/repo Commit: http://git-wip-us.apache.org/repos/asf/couchdb/commit/5b1f7cea Tree: http://git-wip-us.apache.org/repos/asf/couchdb/tree/5b1f7cea Diff: http://git-wip-us.apache.org/repos/asf/couchdb/diff/5b1f7cea Branch: refs/heads/master Commit: 5b1f7cea04b08fea12364acae72a9898d45212d6 Parents: 699ad9c Author: Paul J. Davis Authored: Fri Nov 15 12:13:17 2013 -0600 Committer: Robert Newson Committed: Wed Aug 6 19:29:59 2014 +0100 ---------------------------------------------------------------------- test/etap/060-kt-merging.t | 53 ++++++++++++++++++++--------------------- 1 file changed, 26 insertions(+), 27 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/couchdb/blob/5b1f7cea/test/etap/060-kt-merging.t ---------------------------------------------------------------------- diff --git a/test/etap/060-kt-merging.t b/test/etap/060-kt-merging.t index efbdbf6..e0b1a9c 100755 --- a/test/etap/060-kt-merging.t +++ b/test/etap/060-kt-merging.t @@ -29,12 +29,12 @@ test() -> One = {1, {"1","foo",[]}}, etap:is( - {[One], no_conflicts}, + {[One], new_leaf}, couch_key_tree:merge([], One, 10), "The empty tree is the identity for merge." ), etap:is( - {[One], no_conflicts}, + {[One], internal_node}, couch_key_tree:merge([One], One, 10), "Merging is reflexive." ), @@ -43,7 +43,7 @@ test() -> {1, {"2","foo",[]}}], etap:is( - {TwoSibs, no_conflicts}, + {TwoSibs, internal_node}, couch_key_tree:merge(TwoSibs, One, 10), "Merging a prefix of a tree with the tree yields the tree." ), @@ -54,7 +54,7 @@ test() -> {1, {"3","foo",[]}}], etap:is( - {ThreeSibs, conflicts}, + {ThreeSibs, new_branch}, couch_key_tree:merge(TwoSibs, Three, 10), "Merging a third unrelated branch leads to a conflict." ), @@ -63,30 +63,17 @@ test() -> TwoChild = {1, {"1","foo", [{"1a", "bar", [{"1aa", "bar", []}]}]}}, etap:is( - {[TwoChild], no_conflicts}, + {[TwoChild], internal_node}, couch_key_tree:merge([TwoChild], TwoChild, 10), "Merging two children is still reflexive." ), TwoChildSibs = {1, {"1","foo", [{"1a", "bar", []}, {"1b", "bar", []}]}}, - etap:is( - {[TwoChildSibs], no_conflicts}, - couch_key_tree:merge([TwoChildSibs], TwoChildSibs, 10), - "Merging a tree to itself is itself."), - - TwoChildPlusSibs = - {1, {"1","foo", [{"1a", "bar", [{"1aa", "bar", []}]}, - {"1b", "bar", []}]}}, - - etap:is( - {[TwoChildPlusSibs], no_conflicts}, - couch_key_tree:merge([TwoChild], TwoChildSibs, 10), - "Merging tree of uneven length at node 2."), Stemmed1b = {2, {"1a", "bar", []}}, etap:is( - {[TwoChildSibs], no_conflicts}, + {[TwoChildSibs], internal_node}, couch_key_tree:merge([TwoChildSibs], Stemmed1b, 10), "Merging a tree with a stem." ), @@ -95,7 +82,7 @@ test() -> {"1b", "bar", [{"1bb", "boo", []}]}]}}, Stemmed1bb = {3, {"1bb", "boo", []}}, etap:is( - {[TwoChildSibs2], no_conflicts}, + {[TwoChildSibs2], internal_node}, couch_key_tree:merge([TwoChildSibs2], Stemmed1bb, 10), "Merging a stem at a deeper level." ), @@ -104,27 +91,27 @@ test() -> {2,{"1b", "bar", [{"1bb", "boo", []}]}}], etap:is( - {StemmedTwoChildSibs2, no_conflicts}, + {StemmedTwoChildSibs2, internal_node}, couch_key_tree:merge(StemmedTwoChildSibs2, Stemmed1bb, 10), "Merging a stem at a deeper level against paths at deeper levels." ), Stemmed1aa = {3, {"1aa", "bar", []}}, etap:is( - {[TwoChild], no_conflicts}, + {[TwoChild], internal_node}, couch_key_tree:merge([TwoChild], Stemmed1aa, 10), "Merging a single tree with a deeper stem." ), Stemmed1a = {2, {"1a", "bar", [{"1aa", "bar", []}]}}, etap:is( - {[TwoChild], no_conflicts}, + {[TwoChild], internal_node}, couch_key_tree:merge([TwoChild], Stemmed1a, 10), "Merging a larger stem." ), etap:is( - {[Stemmed1a], no_conflicts}, + {[Stemmed1a], internal_node}, couch_key_tree:merge([Stemmed1a], Stemmed1aa, 10), "More merging." ), @@ -132,13 +119,13 @@ test() -> OneChild = {1, {"1","foo",[{"1a", "bar", []}]}}, Expect1 = [OneChild, Stemmed1aa], etap:is( - {Expect1, conflicts}, + {Expect1, new_branch}, couch_key_tree:merge([OneChild], Stemmed1aa, 10), "Merging should create conflicts." ), etap:is( - {[TwoChild], no_conflicts}, + {[TwoChild], new_leaf}, couch_key_tree:merge(Expect1, TwoChild, 10), "Merge should have no conflicts." ), @@ -168,9 +155,21 @@ test() -> ]}}, etap:is( - {[FooBar], no_conflicts}, + {[FooBar], new_leaf}, couch_key_tree:merge([Foo],Bar,10), "Merging trees with conflicts ought to behave." ), + etap:is( + {[TwoChild], internal_node}, + couch_key_tree:merge([TwoChild],One,10), + "Merging tree with already-existing path." + ), + + etap:is( + {[TwoChildSibs], internal_node}, + couch_key_tree:merge([TwoChildSibs],One,10), + "Merging tree with already-existing path with siblings." + ), + ok.