Three-way merges of access.Permissions as well as tests.
This method is not hooked up anywhere yet.
Change-Id: I5b6c17b37d7127d1d6eddd37f97a8f8fe579beb1
diff --git a/services/syncbase/vsync/cr_permissions.go b/services/syncbase/vsync/cr_permissions.go
new file mode 100644
index 0000000..105f8f3
--- /dev/null
+++ b/services/syncbase/vsync/cr_permissions.go
@@ -0,0 +1,105 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package vsync
+
+import (
+ "v.io/v23/security"
+ "v.io/v23/security/access"
+ "v.io/x/lib/set"
+)
+
+// resolvePermissions performs fine-grained conflict resolution of Permissions.
+func resolvePermissions(local, remote, ancestor access.Permissions) access.Permissions {
+ result := access.Permissions{}
+ if ancestor == nil {
+ ancestor = access.Permissions{}
+ }
+
+ tagsSet := map[string]bool{}
+ for tag, _ := range local {
+ tagsSet[tag] = true
+ }
+ for tag, _ := range remote {
+ tagsSet[tag] = true
+ }
+ for tag, _ := range tagsSet {
+ in := toBlessingPatterns(resolveSlice(
+ fromBlessingPatterns(local[tag].In),
+ fromBlessingPatterns(remote[tag].In),
+ fromBlessingPatterns(ancestor[tag].In)))
+ notIn := resolveSlice(
+ local[tag].NotIn,
+ remote[tag].NotIn,
+ ancestor[tag].NotIn)
+
+ // TODO(fredq): remove this when it is added to Normalize
+ if len(in) != 0 || len(notIn) != 0 {
+ result[tag] = access.AccessList{In: in, NotIn: notIn}
+ }
+ }
+ return result.Normalize()
+}
+
+// resolveSlice is passed two new versions plus an ancestor and returns the merge of
+// the three by performing the following set calculation:
+// A - (A - L) - (A - R) + (L - A) + (R - A)
+// The resultant set will be the ancestor minus the elements that right and left each removed,
+// plus the elements that the right and left added.
+//
+// Since a side can only express adds and removals (and not, e.g., keep element), it isn't
+// possible for one side to add an element that the other side removed, and vice versa. So if the
+// initial set is {A} and one side adds {B} to it, it is not possible for the other side of
+// the conflict to remove {B} during the conflict, since {B} wasn't yet in the set
+// to be removed.
+func resolveSlice(local, remote, ancestor []string) []string {
+ ls := set.String.FromSlice(local)
+ rs := set.String.FromSlice(remote)
+ as := set.String.FromSlice(ancestor)
+
+ // We may be adding things to ls later, and since it will be nil if local is empty,
+ // let's be sure to allocate a map for it now.
+ if ls == nil {
+ ls = map[string]struct{}{}
+ }
+
+ // ls now has all the local elements in it.
+
+ // Add in the elements from remote that are not in ancestor.
+ for _, el := range remote {
+ if _, exists := as[el]; !exists {
+ ls[el] = struct{}{}
+ }
+ }
+ // Remove the elements that are in ancestor but not in remote.
+ for _, el := range ancestor {
+ if _, exists := rs[el]; !exists {
+ delete(ls, el)
+ }
+ }
+
+ //
+ // Convert the map back to a slice, sort it, and return it.
+ return set.String.ToSlice(ls)
+}
+
+// fromBlessingPatterns takes a slice of BlessingPatterns, which is a type alias of string, and
+// returns a slice of strings, casting each BlessingPattern to a string.
+func fromBlessingPatterns(in []security.BlessingPattern) []string {
+ result := make([]string, len(in))
+ for i, value := range in {
+ result[i] = string(value)
+ }
+ return result
+}
+
+// toBlessingPatterns takes a slice of strings and returns it as a new slice of
+// BlessingPatterns, casting each string to a BlessingPattern.
+func toBlessingPatterns(in []string) []security.BlessingPattern {
+ result := make([]security.BlessingPattern, len(in))
+ for i, value := range in {
+ result[i] = security.BlessingPattern(value)
+ }
+ return result
+}
diff --git a/services/syncbase/vsync/cr_permissions_test.go b/services/syncbase/vsync/cr_permissions_test.go
new file mode 100644
index 0000000..b17b230
--- /dev/null
+++ b/services/syncbase/vsync/cr_permissions_test.go
@@ -0,0 +1,159 @@
+// Copyright 2016 The Vanadium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE file.
+
+package vsync
+
+import (
+ "github.com/stretchr/testify/assert"
+ "reflect"
+ "sort"
+ "testing"
+ "v.io/v23/security"
+ "v.io/v23/security/access"
+)
+
+func TestResolvePermissions(t *testing.T) {
+ ancestor := access.Permissions{}
+ left := access.Permissions{}
+ right := access.Permissions{}
+ expected := access.Permissions{}
+
+ ancestor["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ ancestor["W"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+
+ left["A"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ left["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol"}, NotIn: []string{"bob:bad"}}
+
+ right["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "don"}, NotIn: []string{"bob:bad"}}
+ right["W"] = access.AccessList{In: []security.BlessingPattern{"eric"}, NotIn: []string{"bob:bad"}}
+ right["Z"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+
+ expected["A"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ expected["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol", "don"}, NotIn: []string{"bob:bad"}}
+ expected["W"] = access.AccessList{In: []security.BlessingPattern{"eric"}, NotIn: nil}
+ expected["Z"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+
+ result := resolvePermissions(left, right, ancestor)
+ assertPermsEqual(t, expected, result)
+}
+
+func TestResolvePermissionsRemovals(t *testing.T) {
+ ancestor := access.Permissions{}
+ left := access.Permissions{}
+ right := access.Permissions{}
+ expected := access.Permissions{}
+
+ ancestor["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol", "don"}, NotIn: []string{"bob:bad"}}
+ left["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol"}, NotIn: []string{"bob:bad"}}
+ right["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "don"}, NotIn: []string{"bob:bad"}}
+ expected["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ result := resolvePermissions(left, right, ancestor)
+ assertPermsEqual(t, expected, result)
+
+ ancestor["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ left["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol"}, NotIn: []string{"bob:bad"}}
+ right["R"] = access.AccessList{In: []security.BlessingPattern{"bob"}, NotIn: []string{"bob:bad"}}
+ expected["R"] = access.AccessList{In: []security.BlessingPattern{"bob", "carol"}, NotIn: []string{"bob:bad"}}
+ result = resolvePermissions(left, right, ancestor)
+ assertPermsEqual(t, expected, result)
+}
+
+func TestResolvePermissionsDroppedTags(t *testing.T) {
+ ancestor := access.Permissions{}
+ left := access.Permissions{}
+ right := access.Permissions{}
+ expected := access.Permissions{}
+
+ ancestor["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol", "don"}, NotIn: []string{"bob:bad"}}
+ left["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ right["R"] = access.AccessList{In: []security.BlessingPattern{"carol", "don"}, NotIn: []string{"bob:bad"}}
+ expected["R"] = access.AccessList{In: nil, NotIn: []string{"bob:bad"}}
+ result := resolvePermissions(left, right, ancestor)
+ assertPermsEqual(t, expected, result)
+
+ ancestor["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol", "don"}, NotIn: []string{"bob:bad"}}
+ left["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: nil}
+ right["R"] = access.AccessList{In: []security.BlessingPattern{"carol", "don"}, NotIn: nil}
+ expected = access.Permissions{}
+ result = resolvePermissions(left, right, ancestor)
+ assertPermsEqual(t, expected, result)
+}
+
+func TestResolvePermissionsNoAncestor(t *testing.T) {
+ var ancestor access.Permissions
+ left := access.Permissions{}
+ right := access.Permissions{}
+ expected := access.Permissions{}
+
+ left["A"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ left["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol"}, NotIn: []string{"bob:bad"}}
+ left["W"] = access.AccessList{In: []security.BlessingPattern{"bob"}, NotIn: []string{"bob:bad"}}
+
+ right["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "don"}, NotIn: []string{"bob:bad"}}
+ right["W"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "eric"}, NotIn: []string{"bob:bad"}}
+ right["Z"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+
+ expected["A"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+ expected["R"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "carol", "don"}, NotIn: []string{"bob:bad"}}
+ expected["W"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob", "eric"}, NotIn: []string{"bob:bad"}}
+ expected["Z"] = access.AccessList{In: []security.BlessingPattern{"alice", "bob"}, NotIn: []string{"bob:bad"}}
+
+ result := resolvePermissions(left, right, ancestor)
+ assertPermsEqual(t, expected, result)
+}
+
+func TestResolveSlice(t *testing.T) {
+ ancestor := []string{"a", "b"}
+ left := []string{"b"}
+ right := []string{"a", "b", "e"}
+ expected := []string{"b", "e"}
+ result := resolveSlice(left, right, ancestor)
+ sort.Strings(expected)
+ sort.Strings(result)
+ assert.Equal(t, expected, result)
+
+ ancestor = []string{"a", "b", "c"}
+ left = []string{"a", "b", "d"}
+ right = []string{"b", "c", "e"}
+ expected = []string{"b", "d", "e"}
+ result = resolveSlice(left, right, ancestor)
+ sort.Strings(expected)
+ sort.Strings(result)
+ assert.Equal(t, expected, result)
+
+ // Empty left.
+ ancestor = []string{"a", "b"}
+ left = nil
+ right = []string{"b", "c", "e"}
+ expected = []string{"c", "e"}
+ result = resolveSlice(left, right, ancestor)
+ sort.Strings(expected)
+ sort.Strings(result)
+ assert.Equal(t, expected, result)
+
+ // Empty right.
+ ancestor = []string{"a", "b"}
+ left = []string{"b", "c", "e"}
+ right = nil
+ expected = []string{"c", "e"}
+ result = resolveSlice(left, right, ancestor)
+ sort.Strings(expected)
+ sort.Strings(result)
+ assert.Equal(t, expected, result)
+
+ // Empty ancestor.
+ ancestor = nil
+ left = []string{"b", "c", "e"}
+ right = []string{"a", "b"}
+ expected = []string{"a", "b", "c", "e"}
+ result = resolveSlice(left, right, ancestor)
+ sort.Strings(expected)
+ sort.Strings(result)
+ assert.Equal(t, expected, result)
+}
+
+func assertPermsEqual(t *testing.T, expected, actual access.Permissions) {
+ assert.Equal(t, expected, actual)
+ assert.True(t, reflect.DeepEqual(expected, actual))
+}
diff --git a/services/syncbase/vsync/initiator.go b/services/syncbase/vsync/initiator.go
index 6c076be..c1f3cd0 100644
--- a/services/syncbase/vsync/initiator.go
+++ b/services/syncbase/vsync/initiator.go
@@ -764,7 +764,7 @@
// a Database update to simply update the Database to the latest value.
//
// * There is a conflict and we call into the app or use a well-known policy to
-// resolve the conflict, resulting in three possibilties: (a) conflict was
+// resolve the conflict, resulting in three possibilities: (a) conflict was
// resolved by picking the local version. In this case, Database need not be
// updated, but a link is added to record the choice. (b) conflict was resolved
// by picking the remote version. In this case, Database is updated with the
