Add a hasParent() DAG method for Sync of deleted objects.
Let the DAG track the deleted object versions. Sync uses
hasParent() to handle cases of parent-to-child mutations
where either parent or child may be a deleted version:
- parent-to-delete: object deletion
- delete-to-child: conflict resolution revives the object
- parent-to-child: object update
Change-Id: Ibe7c67cba60190e706f2769410ab466f8d43c4d6
diff --git a/runtimes/google/vsync/dag.go b/runtimes/google/vsync/dag.go
index 7f97c99..9e860d9 100644
--- a/runtimes/google/vsync/dag.go
+++ b/runtimes/google/vsync/dag.go
@@ -72,8 +72,9 @@
// and three in-memory (ephemeral) maps (graft, txSet, txGC):
// * nodes: one entry per (object, version) with references to the
// parent node(s) it is derived from, a reference to the
-// log record identifying that change, and a reference to
-// its transaction set (or NoTxID if none)
+// log record identifying that change, a reference to its
+// transaction set (or NoTxID if none), and a boolean to
+// indicate whether this change was a deletion of the object.
// * heads: one entry per object pointing to its most recent version
// in the nodes table
// * trans: one entry per transaction ID containing the set of objects
@@ -137,6 +138,7 @@
Parents []storage.Version // references to parent versions
Logrec string // reference to log record change
TxID TxID // ID of a transaction set
+ Deleted bool // true if the change was a delete
}
type graftInfo struct {
@@ -314,7 +316,7 @@
//
// If the transaction ID is set to NoTxID, this node is not part of a transaction.
// Otherwise, track its membership in the given transaction ID.
-func (d *dag) addNode(oid storage.ID, version storage.Version, remote bool,
+func (d *dag) addNode(oid storage.ID, version storage.Version, remote, deleted bool,
parents []storage.Version, logrec string, tid TxID) error {
if d.store == nil {
return errors.New("invalid DAG")
@@ -413,7 +415,7 @@
}
// Insert the new node in the kvdb.
- node := &dagNode{Level: level, Parents: parents, Logrec: logrec, TxID: tid}
+ node := &dagNode{Level: level, Parents: parents, Logrec: logrec, TxID: tid, Deleted: deleted}
return d.setNode(oid, version, node)
}
@@ -426,6 +428,83 @@
return d.nodes.hasKey(key)
}
+// childOf returns true if the node is a child of the parent version.
+// It means that the parent version is found in the node's Parents array.
+func childOf(node *dagNode, parent storage.Version) bool {
+ if node == nil || parent == storage.NoVersion {
+ return false
+ }
+ for _, pver := range node.Parents {
+ if pver == parent {
+ return true
+ }
+ }
+ return false
+}
+
+// hasParent returns true if the node (oid, version) exists in the DAG DB
+// and has (oid, parent) as a parent node. Either "version" or "parent"
+// could be NoVersion (zero). Thus the 4 cases:
+// 1- "version" and "parent" are _not_ NoVersion: return true if both nodes
+// exist and have a parent/child relationship.
+// 2- Only "parent" is NoVersion: return true if (oid, version) exists and
+// either it has no parents (root of the DAG) or at least one of its
+// parent nodes is a deleted node (i.e. has its "Deleted" flag set true).
+// 3- Only "version" is NoVersion: return true if (oid, parent) exists and
+// at least one of its children is a deleted node.
+// 4- Both "version" and "parent" are NoVersion: return false
+func (d *dag) hasParent(oid storage.ID, version, parent storage.Version) bool {
+ if d.store == nil {
+ return false
+ }
+
+ switch {
+ case version != storage.NoVersion && parent != storage.NoVersion:
+ if !d.hasNode(oid, parent) {
+ return false
+ }
+ node, err := d.getNode(oid, version)
+ if err != nil {
+ return false
+ }
+ return childOf(node, parent)
+
+ case version != storage.NoVersion && parent == storage.NoVersion:
+ node, err := d.getNode(oid, version)
+ if err != nil {
+ return false
+ }
+ if node.Parents == nil {
+ return true
+ }
+ for _, pver := range node.Parents {
+ if pnode, err := d.getNode(oid, pver); err == nil && pnode.Deleted {
+ return true
+ }
+ }
+ return false
+
+ case version == storage.NoVersion && parent != storage.NoVersion:
+ if !d.hasNode(oid, parent) {
+ return false
+ }
+ head, err := d.getHead(oid)
+ if err != nil {
+ return false
+ }
+ found := false
+ d.ancestorIter(oid, []storage.Version{head}, func(oid storage.ID, v storage.Version, node *dagNode) error {
+ if node.Deleted && childOf(node, parent) {
+ found = true
+ return errors.New("found it -- stop the iteration")
+ }
+ return nil
+ })
+ return found
+ }
+ return false
+}
+
// addParent adds to the DAG node (oid, version) linkage to this parent node.
// If the parent linkage is due to a local change (from conflict resolution
// by blessing an existing version), no need to update the grafting structure.
diff --git a/runtimes/google/vsync/dag_test.go b/runtimes/google/vsync/dag_test.go
index a36bc4c..0a50cdf 100644
--- a/runtimes/google/vsync/dag_test.go
+++ b/runtimes/google/vsync/dag_test.go
@@ -99,7 +99,7 @@
t.Error(err)
}
- err = dag.addNode(oid, 4, false, []storage.Version{2, 3}, "foobar", NoTxID)
+ err = dag.addNode(oid, 4, false, false, []storage.Version{2, 3}, "foobar", NoTxID)
if err == nil || err.Error() != "invalid DAG" {
t.Errorf("addNode() did not fail on a closed DAG: %v", err)
}
@@ -199,6 +199,9 @@
if dag.hasNode(oid, 4) {
t.Errorf("hasNode() found an object on a closed DAG")
}
+ if dag.hasParent(oid, 3, 2) {
+ t.Errorf("hasParent() found an parent/child relationship on a closed DAG")
+ }
if pmap := dag.getParentMap(oid); len(pmap) != 0 {
t.Errorf("getParentMap() found data on a closed DAG: %v", pmap)
}
@@ -506,26 +509,26 @@
}
// Make sure an existing node cannot be added again.
- if err = dag.addNode(oid, 1, false, []storage.Version{0, 2}, "foobar", NoTxID); err == nil {
+ if err = dag.addNode(oid, 1, false, false, []storage.Version{0, 2}, "foobar", NoTxID); err == nil {
t.Errorf("addNode() did not fail when given an existing node")
}
// Make sure a new node cannot have more than 2 parents.
- if err = dag.addNode(oid, 3, false, []storage.Version{0, 1, 2}, "foobar", NoTxID); err == nil {
+ if err = dag.addNode(oid, 3, false, false, []storage.Version{0, 1, 2}, "foobar", NoTxID); err == nil {
t.Errorf("addNode() did not fail when given 3 parents")
}
// Make sure a new node cannot have an invalid parent.
- if err = dag.addNode(oid, 3, false, []storage.Version{0, 555}, "foobar", NoTxID); err == nil {
+ if err = dag.addNode(oid, 3, false, false, []storage.Version{0, 555}, "foobar", NoTxID); err == nil {
t.Errorf("addNode() did not fail when using an invalid parent")
}
// Make sure a new root node (no parents) cannot be added once a root exists.
// For the parents array, check both the "nil" and the empty array as input.
- if err = dag.addNode(oid, 6789, false, nil, "foobar", NoTxID); err == nil {
+ if err = dag.addNode(oid, 6789, false, false, nil, "foobar", NoTxID); err == nil {
t.Errorf("Adding a 2nd root node (nil parents) for object %d in DAG file %s did not fail", oid, dagfile)
}
- if err = dag.addNode(oid, 6789, false, []storage.Version{}, "foobar", NoTxID); err == nil {
+ if err = dag.addNode(oid, 6789, false, false, []storage.Version{}, "foobar", NoTxID); err == nil {
t.Errorf("Adding a 2nd root node (empty parents) for object %d in DAG file %s did not fail", oid, dagfile)
}
@@ -1599,10 +1602,10 @@
t.Errorf("Transactions map for Tx ID %v has length %d instead of 0 in DAG file %s", tid_1, n, dagfile)
}
- if err := dag.addNode(oid_a, 3, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
+ if err := dag.addNode(oid_a, 3, false, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_a, tid_1, dagfile, err)
}
- if err := dag.addNode(oid_b, 3, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
+ if err := dag.addNode(oid_b, 3, false, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_1, dagfile, err)
}
@@ -1620,7 +1623,7 @@
t.Errorf("Transactions map for Tx ID %v has length %d instead of 0 in DAG file %s", tid_2, n, dagfile)
}
- if err := dag.addNode(oid_c, 2, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
+ if err := dag.addNode(oid_c, 2, false, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_c, tid_2, dagfile, err)
}
@@ -1651,7 +1654,7 @@
bad_tid++
}
- if err := dag.addNode(oid_c, 3, false, []storage.Version{2}, "logrec-c-03", bad_tid); err == nil {
+ if err := dag.addNode(oid_c, 3, false, false, []storage.Version{2}, "logrec-c-03", bad_tid); err == nil {
t.Errorf("addNode() did not fail on object %d for a bad Tx ID %v in DAG file %s", oid_c, bad_tid, dagfile)
}
if err := dag.addNodeTxEnd(bad_tid); err == nil {
@@ -1783,10 +1786,10 @@
if tid_1 == NoTxID {
t.Fatal("Cannot start 1st DAG addNode() transaction")
}
- if err := dag.addNode(oid_a, 3, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
+ if err := dag.addNode(oid_a, 3, false, false, []storage.Version{2}, "logrec-a-03", tid_1); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_a, tid_1, dagfile, err)
}
- if err := dag.addNode(oid_b, 3, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
+ if err := dag.addNode(oid_b, 3, false, false, []storage.Version{2}, "logrec-b-03", tid_1); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_1, dagfile, err)
}
if err := dag.addNodeTxEnd(tid_1); err != nil {
@@ -1797,20 +1800,20 @@
if tid_2 == NoTxID {
t.Fatal("Cannot start 2nd DAG addNode() transaction")
}
- if err := dag.addNode(oid_b, 4, false, []storage.Version{3}, "logrec-b-04", tid_2); err != nil {
+ if err := dag.addNode(oid_b, 4, false, false, []storage.Version{3}, "logrec-b-04", tid_2); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_2, dagfile, err)
}
- if err := dag.addNode(oid_c, 2, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
+ if err := dag.addNode(oid_c, 2, false, false, []storage.Version{1}, "logrec-c-02", tid_2); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_c, tid_2, dagfile, err)
}
if err := dag.addNodeTxEnd(tid_2); err != nil {
t.Errorf("Cannot addNodeTxEnd() for Tx ID %v in DAG file %s: %v", tid_2, dagfile, err)
}
- if err := dag.addNode(oid_a, 4, false, []storage.Version{3}, "logrec-a-04", NoTxID); err != nil {
+ if err := dag.addNode(oid_a, 4, false, false, []storage.Version{3}, "logrec-a-04", NoTxID); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_a, tid_1, dagfile, err)
}
- if err := dag.addNode(oid_b, 5, false, []storage.Version{4}, "logrec-b-05", NoTxID); err != nil {
+ if err := dag.addNode(oid_b, 5, false, false, []storage.Version{4}, "logrec-b-05", NoTxID); err != nil {
t.Errorf("Cannot addNode() on object %d and Tx ID %v in DAG file %s: %v", oid_b, tid_2, dagfile, err)
}
@@ -1885,7 +1888,7 @@
}
// Add c3 as a new head and prune at that point. This should GC Tx-2.
- if err := dag.addNode(oid_c, 3, false, []storage.Version{2}, "logrec-c-03", NoTxID); err != nil {
+ if err := dag.addNode(oid_c, 3, false, false, []storage.Version{2}, "logrec-c-03", NoTxID); err != nil {
t.Errorf("Cannot addNode() on object %d in DAG file %s: %v", oid_c, dagfile, err)
}
if err = dag.moveHead(oid_c, 3); err != nil {
@@ -1916,3 +1919,65 @@
}
}
}
+
+// TestHasParent tests lookup of DAG parent/child relationship (i.e. hasParent()).
+func TestHasParent(t *testing.T) {
+ dagfile := dagFilename()
+ defer os.Remove(dagfile)
+
+ dag, err := openDAG(dagfile)
+ if err != nil {
+ t.Fatalf("Cannot open new DAG file %s", dagfile)
+ }
+
+ if err = dagReplayCommands(dag, "local-init-03.sync"); err != nil {
+ t.Fatal(err)
+ }
+
+ oid, err := strToObjID("12345")
+ if err != nil {
+ t.Fatal(err)
+ }
+
+ // The object mutations are: v1 -> v2 (deleted) -> v3 with v3 as head node.
+
+ type hasParentTest struct {
+ parent storage.Version
+ child storage.Version
+ result bool
+ }
+ tests := []hasParentTest{
+ {storage.NoVersion, storage.NoVersion, false},
+ {1, 2, true},
+ {2, 3, true},
+ {1, 999, false},
+ {999, 1, false},
+ {1, 3, false},
+ {1, storage.NoVersion, true},
+ {2, storage.NoVersion, false},
+ {3, storage.NoVersion, false},
+ {999, storage.NoVersion, false},
+ {storage.NoVersion, 1, true},
+ {storage.NoVersion, 2, false},
+ {storage.NoVersion, 3, true},
+ {storage.NoVersion, 999, false},
+ }
+
+ for _, test := range tests {
+ result := dag.hasParent(oid, test.child, test.parent)
+ if result != test.result {
+ t.Errorf("hasParent() for parent/child (%d/%d) in DAG file %s: %v instead of %v",
+ test.parent, test.child, dagfile, result, test.result)
+ }
+ }
+
+ // Increase coverage of internal helper function.
+ if childOf(nil, 3) {
+ t.Errorf("childOf() returned true on a nil node")
+ }
+ if childOf(&dagNode{}, storage.NoVersion) {
+ t.Errorf("childOf() returned true on a NoVersion parent")
+ }
+
+ dag.close()
+}
diff --git a/runtimes/google/vsync/ilog.go b/runtimes/google/vsync/ilog.go
index a40606b..f7c46f2 100644
--- a/runtimes/google/vsync/ilog.go
+++ b/runtimes/google/vsync/ilog.go
@@ -410,7 +410,7 @@
}
// Insert the new log record into dag.
- if err = l.s.dag.addNode(rec.ObjID, rec.CurVers, false, rec.Parents, logKey, txID); err != nil {
+ if err = l.s.dag.addNode(rec.ObjID, rec.CurVers, false, val.Delete, rec.Parents, logKey, txID); err != nil {
return err
}
diff --git a/runtimes/google/vsync/initiator.go b/runtimes/google/vsync/initiator.go
index e885359..d6c786e 100644
--- a/runtimes/google/vsync/initiator.go
+++ b/runtimes/google/vsync/initiator.go
@@ -330,7 +330,7 @@
vlog.VI(2).Infof("insertRecInLogAndDag:: Adding log record %v, Tx %v", rec, txID)
switch rec.RecType {
case NodeRec:
- return i.syncd.dag.addNode(rec.ObjID, rec.CurVers, true, rec.Parents, logKey, txID)
+ return i.syncd.dag.addNode(rec.ObjID, rec.CurVers, true, rec.Value.Delete, rec.Parents, logKey, txID)
case LinkRec:
return i.syncd.dag.addParent(rec.ObjID, rec.CurVers, rec.Parents[0], true)
default:
@@ -642,7 +642,7 @@
// TODO(hpucha): addNode operations arising out of conflict resolution
// may need to be part of a transaction when app-driven resolution
// is introduced.
- err = i.syncd.dag.addNode(obj, rec.CurVers, false, rec.Parents, logKey, NoTxID)
+ err = i.syncd.dag.addNode(obj, rec.CurVers, false, rec.Value.Delete, rec.Parents, logKey, NoTxID)
case LinkRec:
err = i.syncd.dag.addParent(obj, rec.CurVers, rec.Parents[0], false)
default:
diff --git a/runtimes/google/vsync/initiator_test.go b/runtimes/google/vsync/initiator_test.go
index 4755fc8..987d4d7 100644
--- a/runtimes/google/vsync/initiator_test.go
+++ b/runtimes/google/vsync/initiator_test.go
@@ -49,7 +49,7 @@
if _, err := s.hdlInitiator.getLogRec(objID, expRec.CurVers); err == nil {
t.Errorf("GetLogRec didn't fail")
}
- if err = s.dag.addNode(objID, expRec.CurVers, false, expRec.Parents, logKey, NoTxID); err != nil {
+ if err = s.dag.addNode(objID, expRec.CurVers, false, false, expRec.Parents, logKey, NoTxID); err != nil {
t.Errorf("AddNode failed with err %v", err)
}
curRec, err := s.hdlInitiator.getLogRec(objID, expRec.CurVers)
@@ -98,7 +98,7 @@
if err != nil {
t.Errorf("PutLogRec failed with err %v", err)
}
- if err = s.dag.addNode(objID, expRec.CurVers, false, expRec.Parents, logKey, NoTxID); err != nil {
+ if err = s.dag.addNode(objID, expRec.CurVers, false, false, expRec.Parents, logKey, NoTxID); err != nil {
t.Errorf("AddNode failed with err %v", err)
}
}
diff --git a/runtimes/google/vsync/replay_test.go b/runtimes/google/vsync/replay_test.go
index 1f43a28..26df5fa 100644
--- a/runtimes/google/vsync/replay_test.go
+++ b/runtimes/google/vsync/replay_test.go
@@ -35,6 +35,7 @@
devID DeviceID
genVec GenVector
continued bool
+ deleted bool
}
func strToObjID(objStr string) (storage.ID, error) {
@@ -91,7 +92,7 @@
switch args[0] {
case "addl", "addr":
- expNargs := 7
+ expNargs := 8
if nargs != expNargs {
return nil, fmt.Errorf("%s:%d: need %d args instead of %d", file, lineno, expNargs, nargs)
}
@@ -114,7 +115,11 @@
if err != nil {
return nil, fmt.Errorf("%s:%d: invalid continued bit: %s", file, lineno, args[6])
}
- cmd := syncCommand{version: version, parents: parents, logrec: args[5], continued: continued}
+ del, err := strconv.ParseBool(args[7])
+ if err != nil {
+ return nil, fmt.Errorf("%s:%d: invalid deleted bit: %s", file, lineno, args[7])
+ }
+ cmd := syncCommand{version: version, parents: parents, logrec: args[5], continued: continued, deleted: del}
if args[0] == "addl" {
cmd.cmd = addLocal
} else {
@@ -197,7 +202,8 @@
for _, cmd := range cmds {
switch cmd.cmd {
case addLocal:
- if err = dag.addNode(cmd.objID, cmd.version, false, cmd.parents, cmd.logrec, NoTxID); err != nil {
+ err = dag.addNode(cmd.objID, cmd.version, false, cmd.deleted, cmd.parents, cmd.logrec, NoTxID)
+ if err != nil {
return fmt.Errorf("cannot add local node %d:%d to DAG: %v", cmd.objID, cmd.version, err)
}
if err := dag.moveHead(cmd.objID, cmd.version); err != nil {
@@ -206,7 +212,8 @@
dag.flush()
case addRemote:
- if err = dag.addNode(cmd.objID, cmd.version, true, cmd.parents, cmd.logrec, NoTxID); err != nil {
+ err = dag.addNode(cmd.objID, cmd.version, true, cmd.deleted, cmd.parents, cmd.logrec, NoTxID)
+ if err != nil {
return fmt.Errorf("cannot add remote node %d:%d to DAG: %v", cmd.objID, cmd.version, err)
}
dag.flush()
diff --git a/runtimes/google/vsync/testdata/local-init-00.sync b/runtimes/google/vsync/testdata/local-init-00.sync
index 047b2de..d1dace2 100644
--- a/runtimes/google/vsync/testdata/local-init-00.sync
+++ b/runtimes/google/vsync/testdata/local-init-00.sync
@@ -1,6 +1,6 @@
# Create an object locally and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addl|12345|0|||logrec-00|false
-addl|12345|1|0||logrec-01|false
-addl|12345|2|1||logrec-02|false
+addl|12345|0|||logrec-00|false|false
+addl|12345|1|0||logrec-01|false|false
+addl|12345|2|1||logrec-02|false|false
diff --git a/runtimes/google/vsync/testdata/local-init-01.sync b/runtimes/google/vsync/testdata/local-init-01.sync
index 93f0b55..525dd09 100644
--- a/runtimes/google/vsync/testdata/local-init-01.sync
+++ b/runtimes/google/vsync/testdata/local-init-01.sync
@@ -1,12 +1,12 @@
# Create an object DAG locally with branches and resolved conflicts.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addl|12345|0|||logrec-00|false
-addl|12345|1|0||logrec-01|false
-addl|12345|2|1||logrec-02|false
-addl|12345|3|1||logrec-03|false
-addl|12345|4|2|3|logrec-04|false
-addl|12345|5|4||logrec-05|false
-addl|12345|6|1||logrec-06|false
-addl|12345|7|5|6|logrec-07|false
-addl|12345|8|7||logrec-08|false
+addl|12345|0|||logrec-00|false|false
+addl|12345|1|0||logrec-01|false|false
+addl|12345|2|1||logrec-02|false|false
+addl|12345|3|1||logrec-03|false|false
+addl|12345|4|2|3|logrec-04|false|false
+addl|12345|5|4||logrec-05|false|false
+addl|12345|6|1||logrec-06|false|false
+addl|12345|7|5|6|logrec-07|false|false
+addl|12345|8|7||logrec-08|false|false
diff --git a/runtimes/google/vsync/testdata/local-init-02.sync b/runtimes/google/vsync/testdata/local-init-02.sync
index 118e3f8..70b1319 100644
--- a/runtimes/google/vsync/testdata/local-init-02.sync
+++ b/runtimes/google/vsync/testdata/local-init-02.sync
@@ -1,10 +1,10 @@
# Create DAGs for 3 objects locally.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addl|12345|1|||logrec-a-01|false
-addl|12345|2|1||logrec-a-02|false
+addl|12345|1|||logrec-a-01|false|false
+addl|12345|2|1||logrec-a-02|false|false
-addl|67890|1|||logrec-b-01|false
-addl|67890|2|1||logrec-b-02|false
+addl|67890|1|||logrec-b-01|false|false
+addl|67890|2|1||logrec-b-02|false|false
-addl|222|1|||logrec-c-01|false
+addl|222|1|||logrec-c-01|false|false
diff --git a/runtimes/google/vsync/testdata/local-init-03.sync b/runtimes/google/vsync/testdata/local-init-03.sync
new file mode 100644
index 0000000..63f4fc6
--- /dev/null
+++ b/runtimes/google/vsync/testdata/local-init-03.sync
@@ -0,0 +1,5 @@
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
+
+addl|12345|1|||logrec-01|false|false
+addl|12345|2|1||logrec-02|false|true
+addl|12345|3|2||logrec-03|false|false
diff --git a/runtimes/google/vsync/testdata/local-resolve-00.sync b/runtimes/google/vsync/testdata/local-resolve-00.sync
index b4f1518..02e1c88 100644
--- a/runtimes/google/vsync/testdata/local-resolve-00.sync
+++ b/runtimes/google/vsync/testdata/local-resolve-00.sync
@@ -1,4 +1,4 @@
# Create an object locally and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addl|12345|6|2|5|logrec-06|false
+addl|12345|6|2|5|logrec-06|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-00.log.sync b/runtimes/google/vsync/testdata/remote-conf-00.log.sync
index 23beca6..994a66f 100644
--- a/runtimes/google/vsync/testdata/remote-conf-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-00.log.sync
@@ -1,8 +1,8 @@
# Update an object remotely three times triggering one conflict after
# it was created locally up to v2 (i.e. assume the remote sync received
# it from the local sync at v1, then updated separately).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|1||VeyronPhone:1:0|false
-addr|12345|4|3||VeyronPhone:1:1|false
-addr|12345|5|4||VeyronPhone:1:2|false
+addr|12345|3|1||VeyronPhone:1:0|false|false
+addr|12345|4|3||VeyronPhone:1:1|false|false
+addr|12345|5|4||VeyronPhone:1:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-00.sync b/runtimes/google/vsync/testdata/remote-conf-00.sync
index ea6ab3f..7e555a6 100644
--- a/runtimes/google/vsync/testdata/remote-conf-00.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-00.sync
@@ -1,8 +1,8 @@
# Update an object remotely three times triggering one conflict after
# it was created locally up to v2 (i.e. assume the remote sync received
# it from the local sync at v1, then updated separately).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|1||logrec-03|false
-addr|12345|4|3||logrec-04|false
-addr|12345|5|4||logrec-05|false
+addr|12345|3|1||logrec-03|false|false
+addr|12345|4|3||logrec-04|false|false
+addr|12345|5|4||logrec-05|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-01.log.sync b/runtimes/google/vsync/testdata/remote-conf-01.log.sync
index 1bcc3c9..4fabf55 100644
--- a/runtimes/google/vsync/testdata/remote-conf-01.log.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-01.log.sync
@@ -3,8 +3,8 @@
# v0, made its own conflicting v3 that it resolved into v4 (against v1)
# then made a v5 change. When the local sync gets back this info it
# sees 2 graft points: v0-v3 and v1-v4.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|0||VeyronLaptop:1:0|false
-addr|12345|4|1|3|VeyronPhone:1:0|false
-addr|12345|5|4||VeyronPhone:1:1|false
+addr|12345|3|0||VeyronLaptop:1:0|false|false
+addr|12345|4|1|3|VeyronPhone:1:0|false|false
+addr|12345|5|4||VeyronPhone:1:1|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-01.sync b/runtimes/google/vsync/testdata/remote-conf-01.sync
index b9aece7..4655a1e 100644
--- a/runtimes/google/vsync/testdata/remote-conf-01.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-01.sync
@@ -3,8 +3,8 @@
# v0, made its own conflicting v3 that it resolved into v4 (against v1)
# then made a v5 change. When the local sync gets back this info it
# sees 2 graft points: v0-v3 and v1-v4.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|0||logrec-03|false
-addr|12345|4|1|3|logrec-04|false
-addr|12345|5|4||logrec-05|false
+addr|12345|3|0||logrec-03|false|false
+addr|12345|4|1|3|logrec-04|false|false
+addr|12345|5|4||logrec-05|false|false
diff --git a/runtimes/google/vsync/testdata/remote-conf-link.log.sync b/runtimes/google/vsync/testdata/remote-conf-link.log.sync
index 627769a..65d0176 100644
--- a/runtimes/google/vsync/testdata/remote-conf-link.log.sync
+++ b/runtimes/google/vsync/testdata/remote-conf-link.log.sync
@@ -1,5 +1,5 @@
# Update an object remotely, detect conflict, and bless the local version.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
linkr|12345|3|1||VeyronPhone:1:1
diff --git a/runtimes/google/vsync/testdata/remote-init-00.log.sync b/runtimes/google/vsync/testdata/remote-init-00.log.sync
index 3a945e9..0030417 100644
--- a/runtimes/google/vsync/testdata/remote-init-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-init-00.log.sync
@@ -1,6 +1,6 @@
# Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|0|||VeyronPhone:1:0|false
-addr|12345|1|0||VeyronPhone:1:1|false
-addr|12345|2|1||VeyronPhone:1:2|false
+addr|12345|0|||VeyronPhone:1:0|false|false
+addr|12345|1|0||VeyronPhone:1:1|false|false
+addr|12345|2|1||VeyronPhone:1:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-init-00.sync b/runtimes/google/vsync/testdata/remote-init-00.sync
index 9ae9adc..7f2189a 100644
--- a/runtimes/google/vsync/testdata/remote-init-00.sync
+++ b/runtimes/google/vsync/testdata/remote-init-00.sync
@@ -1,6 +1,6 @@
# Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|0|||logrec-00|false
-addr|12345|1|0||logrec-01|false
-addr|12345|2|1||logrec-02|false
+addr|12345|0|||logrec-00|false|false
+addr|12345|1|0||logrec-01|false|false
+addr|12345|2|1||logrec-02|false|false
diff --git a/runtimes/google/vsync/testdata/remote-init-01.log.sync b/runtimes/google/vsync/testdata/remote-init-01.log.sync
index 9b02859..a357986 100644
--- a/runtimes/google/vsync/testdata/remote-init-01.log.sync
+++ b/runtimes/google/vsync/testdata/remote-init-01.log.sync
@@ -1,6 +1,6 @@
# Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|0|||VeyronPhone:5:0|false
-addr|12345|1|0||VeyronPhone:5:1|false
-addr|12345|2|1||VeyronPhone:5:2|false
+addr|12345|0|||VeyronPhone:5:0|false|false
+addr|12345|1|0||VeyronPhone:5:1|false|false
+addr|12345|2|1||VeyronPhone:5:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-init-02.log.sync b/runtimes/google/vsync/testdata/remote-init-02.log.sync
index cf71306..c0053ba 100644
--- a/runtimes/google/vsync/testdata/remote-init-02.log.sync
+++ b/runtimes/google/vsync/testdata/remote-init-02.log.sync
@@ -1,17 +1,17 @@
# Create an object remotely and update it twice (linked-list).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|123|0|||VeyronPhone:1:0|false
+addr|123|0|||VeyronPhone:1:0|false|false
-addr|123|1|0||VeyronPhone:1:1|true
-addr|456|0|||VeyronPhone:1:2|true
-addr|789|0|||VeyronPhone:1:3|false
+addr|123|1|0||VeyronPhone:1:1|true|false
+addr|456|0|||VeyronPhone:1:2|true|false
+addr|789|0|||VeyronPhone:1:3|false|false
-addr|789|1|0||VeyronPhone:1:4|false
+addr|789|1|0||VeyronPhone:1:4|false|false
-addr|789|2|0||VeyronTab:1:0|false
+addr|789|2|0||VeyronTab:1:0|false|false
-addr|789|3|1|2|VeyronPhone:2:0|false
+addr|789|3|1|2|VeyronPhone:2:0|false|false
-addr|123|2|1||VeyronPhone:2:1|true
-addr|456|1|0||VeyronPhone:2:2|false
\ No newline at end of file
+addr|123|2|1||VeyronPhone:2:1|true|false
+addr|456|1|0||VeyronPhone:2:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-00.log.sync b/runtimes/google/vsync/testdata/remote-noconf-00.log.sync
index 55afb29..c291155 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-00.log.sync
@@ -1,8 +1,8 @@
# Update an object remotely three times without triggering a conflict
# after it was created locally up to v2 (i.e. assume the remote sync
# received it from the local sync first, then updated it).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|2||VeyronPhone:1:0|false
-addr|12345|4|3||VeyronPhone:1:1|false
-addr|12345|5|4||VeyronPhone:1:2|false
+addr|12345|3|2||VeyronPhone:1:0|false|false
+addr|12345|4|3||VeyronPhone:1:1|false|false
+addr|12345|5|4||VeyronPhone:1:2|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-00.sync b/runtimes/google/vsync/testdata/remote-noconf-00.sync
index fc7b633..9b95c86 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-00.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-00.sync
@@ -1,8 +1,8 @@
# Update an object remotely three times without triggering a conflict
# after it was created locally up to v2 (i.e. assume the remote sync
# received it from the local sync first, then updated it).
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|2||logrec-03|false
-addr|12345|4|3||logrec-04|false
-addr|12345|5|4||logrec-05|false
+addr|12345|3|2||logrec-03|false|false
+addr|12345|4|3||logrec-04|false|false
+addr|12345|5|4||logrec-05|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync
index b3849d5..ab1e2c4 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-00.log.sync
@@ -1,5 +1,5 @@
# Update an object remotely, detect conflict, and bless the remote version.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
linkr|12345|1|3||VeyronPhone:1:1
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync
index 9495dc1..4ee0b53 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-01.log.sync
@@ -1,5 +1,5 @@
# Update an object remotely, detect conflict, and bless the local version.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
linkr|12345|3|2||VeyronPhone:1:1
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync
index 455fb5c..53d9735 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-02.log.sync
@@ -1,6 +1,6 @@
# Update an object remotely, detect conflict, and bless the remote version, and continue updating.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
-addr|12345|3|0||VeyronPhone:1:0|false
+addr|12345|3|0||VeyronPhone:1:0|false|false
linkr|12345|2|3||VeyronPhone:1:1
-addr|12345|4|2||VeyronPhone:2:0|false
+addr|12345|4|2||VeyronPhone:2:0|false|false
diff --git a/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync b/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync
index 9a04969..2ca80bf 100644
--- a/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync
+++ b/runtimes/google/vsync/testdata/remote-noconf-link-repeat.log.sync
@@ -1,5 +1,5 @@
# Resolve the same conflict on two different devices.
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
linkr|12345|2|3||VeyronLaptop:1:0
diff --git a/runtimes/google/vsync/testdata/test-1obj.gc.sync b/runtimes/google/vsync/testdata/test-1obj.gc.sync
index 9cef648..93eca9e 100644
--- a/runtimes/google/vsync/testdata/test-1obj.gc.sync
+++ b/runtimes/google/vsync/testdata/test-1obj.gc.sync
@@ -1,12 +1,12 @@
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
# Local node is A. Remote nodes are B and C.
-addr|12345|0|||C:1:0|false
-addr|12345|1|0||B:1:0|false
-addl|12345|2|0||A:1:0|false
-addl|12345|3|1|2|A:2:0|false
-addr|12345|4|3||C:2:0|false
-addr|12345|5|3||B:2:0|false
-addr|12345|6|4|5|B:3:0|false
+addr|12345|0|||C:1:0|false|false
+addr|12345|1|0||B:1:0|false|false
+addl|12345|2|0||A:1:0|false|false
+addl|12345|3|1|2|A:2:0|false|false
+addr|12345|4|3||C:2:0|false|false
+addr|12345|5|3||B:2:0|false|false
+addr|12345|6|4|5|B:3:0|false|false
# Devtable state
setdev|A|A:2,B:3,C:2
setdev|B|A:2,B:3,C:2
diff --git a/runtimes/google/vsync/testdata/test-3obj.gc.sync b/runtimes/google/vsync/testdata/test-3obj.gc.sync
index fcf6598..d9a3899 100644
--- a/runtimes/google/vsync/testdata/test-3obj.gc.sync
+++ b/runtimes/google/vsync/testdata/test-3obj.gc.sync
@@ -1,42 +1,42 @@
-# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>
+# The format is: <cmd>|<objid>|<version>|<parent1>|<parent2>|<logrec>|<continued>|<deleted>
# Local node is A. Remote nodes are B and C.
-addl|123|1|||A:1:0|false
+addl|123|1|||A:1:0|false|false
-addr|456|1|||B:1:0|false
+addr|456|1|||B:1:0|false|false
-addr|456|2|1||B:2:0|false
-addr|123|2|1||B:2:1|false
+addr|456|2|1||B:2:0|false|false
+addr|123|2|1||B:2:1|false|false
-addl|456|3|2||A:2:0|false
-addl|123|4|2||A:2:1|false
+addl|456|3|2||A:2:0|false|false
+addl|123|4|2||A:2:1|false|false
-addr|789|1|||C:1:0|false
+addr|789|1|||C:1:0|false|false
-addr|789|2|1||C:2:0|false
+addr|789|2|1||C:2:0|false|false
-addr|123|3|1||C:3:0|false
-addr|789|3|2||C:3:1|false
+addr|123|3|1||C:3:0|false|false
+addr|789|3|2||C:3:1|false|false
-addr|123|5|3|2|C:4:0|false
+addr|123|5|3|2|C:4:0|false|false
-addl|123|6|4|5|A:3:0|false
-addl|456|4|3||A:3:1|false
-addl|789|4|3||A:3:2|false
+addl|123|6|4|5|A:3:0|false|false
+addl|456|4|3||A:3:1|false|false
+addl|789|4|3||A:3:2|false|false
-addr|456|5|2||B:3:0|false
+addr|456|5|2||B:3:0|false|false
-addl|456|7|4|5|A:4:0|false
+addl|456|7|4|5|A:4:0|false|false
-addr|456|6|2||C:5:0|false
-addr|123|7|5||C:5:1|false
-addr|123|8|7||C:5:2|false
-addr|789|5|3||C:5:3|false
+addr|456|6|2||C:5:0|false|false
+addr|123|7|5||C:5:1|false|false
+addr|123|8|7||C:5:2|false|false
+addr|789|5|3||C:5:3|false|false
-addl|123|9|6|8|A:5:0|false
-addl|456|8|6|7|A:5:1|false
-addl|789|6|4|5|A:5:2|false
+addl|123|9|6|8|A:5:0|false|false
+addl|456|8|6|7|A:5:1|false|false
+addl|789|6|4|5|A:5:2|false|false
-addl|123|10|9||A:6:0|false
+addl|123|10|9||A:6:0|false|false
# Devtable state
setdev|A|A:6,B:3,C:5
diff --git a/runtimes/google/vsync/util_test.go b/runtimes/google/vsync/util_test.go
index 002ab95..263ee30 100644
--- a/runtimes/google/vsync/util_test.go
+++ b/runtimes/google/vsync/util_test.go
@@ -172,7 +172,7 @@
if err != nil {
return err
}
- if err := s.dag.addNode(rec.ObjID, rec.CurVers, false, rec.Parents, logKey, NoTxID); err != nil {
+ if err := s.dag.addNode(rec.ObjID, rec.CurVers, false, rec.Value.Delete, rec.Parents, logKey, NoTxID); err != nil {
return err
}
if err := s.dag.moveHead(rec.ObjID, rec.CurVers); err != nil {
@@ -205,7 +205,7 @@
ObjID: cmd.objID,
CurVers: cmd.version,
Parents: cmd.parents,
- Value: LogValue{Continued: cmd.continued},
+ Value: LogValue{Continued: cmd.continued, Delete: cmd.deleted},
}
if err := populateLogAndDAG(s, rec); err != nil {
return err
diff --git a/runtimes/google/vsync/watcher.go b/runtimes/google/vsync/watcher.go
index d470ce0..4d887c3 100644
--- a/runtimes/google/vsync/watcher.go
+++ b/runtimes/google/vsync/watcher.go
@@ -163,8 +163,6 @@
w.syncd.lock.Lock()
defer w.syncd.lock.Unlock()
- // TODO(rdaoud): handle object deletion (State == DoesNotExist)
-
vlog.VI(1).Infof("processChanges:: ready to process changes")
var lastResmark []byte
