From ad9d525a9aac5e36280d1274e1b8efd6f4e58632 Mon Sep 17 00:00:00 2001 From: "nick@chromium.org" Date: Sat, 23 Jul 2011 02:05:28 +0000 Subject: sync: have the client compute position_in_parent values. This is a protocol change to allow the server to operate on top of an eventually consistent store. Rather than having the server do a lookup of the sibling position to generate an absolute position, the client will now be responsible for doing that same operation. As implemented here, math of interpolation is the same as what the server has historically done. The client will continue sending the insert_after_item_id, for interoperation with server implementations that depend on the old behavior. Implement the new behavior in the testserver. TEST=sync_integration_tests,included unittests Review URL: http://codereview.chromium.org/7481003 git-svn-id: svn://svn.chromium.org/chrome/trunk/src@93762 0039d316-1c4b-4281-b951-d872f2087c98 --- net/tools/testserver/chromiumsync.py | 80 +++++++------------------------ net/tools/testserver/chromiumsync_test.py | 75 ++++------------------------- 2 files changed, 27 insertions(+), 128 deletions(-) (limited to 'net/tools') diff --git a/net/tools/testserver/chromiumsync.py b/net/tools/testserver/chromiumsync.py index fc1be20..3c0255f 100755 --- a/net/tools/testserver/chromiumsync.py +++ b/net/tools/testserver/chromiumsync.py @@ -500,66 +500,26 @@ class SyncDataModel(object): migration_version_string, separator, inner_id = remainder.partition('^') return (int(datatype_string), int(migration_version_string), inner_id) - def _WritePosition(self, entry, parent_id, prev_id=None): - """Convert from a relative position into an absolute, numeric position. + def _WritePosition(self, entry, parent_id): + """Ensure the entry has an absolute, numeric position and parent_id. - Clients specify positions using the predecessor-based references; the - server stores and reports item positions using sparse integer values. - This method converts from the former to the latter. + Historically, clients would specify positions using the predecessor-based + references in the insert_after_item_id field; starting July 2011, this + was changed and Chrome now sends up the absolute position. The server + must store a position_in_parent value and must not maintain + insert_after_item_id. Args: - entry: The entry for which to compute a position. Its ID field are + entry: The entry for which to write a position. Its ID field are assumed to be server IDs. This entry will have its parent_id_string and position_in_parent fields updated; its insert_after_item_id field will be cleared. parent_id: The ID of the entry intended as the new parent. - prev_id: The ID of the entry intended as the new predecessor. If this - is None, or an ID of an object which is not a child of the new parent, - the entry will be positioned at the end (right) of the ordering. If - the empty ID (''), this will be positioned at the front (left) of the - ordering. Otherwise, the entry will be given a position_in_parent - value placing it just after (to the right of) the new predecessor. """ - preferred_gap = 2 ** 20 - - def ExtendRange(current_limit_entry, sign_multiplier): - """Compute values at the beginning or end.""" - if current_limit_entry.id_string == entry.id_string: - step = 0 - else: - step = sign_multiplier * preferred_gap - return current_limit_entry.position_in_parent + step - - siblings = [x for x in self._entries.values() - if x.parent_id_string == parent_id and not x.deleted] - siblings = sorted(siblings, key=operator.attrgetter('position_in_parent')) - if prev_id == entry.id_string: - prev_id = '' - if not siblings: - # First item in this container; start in the middle. - entry.position_in_parent = 0 - elif not prev_id: - # A special value in the protocol. Insert at first position. - entry.position_in_parent = ExtendRange(siblings[0], -1) - else: - # Handle mid-insertion; consider items along with their successors. - for item, successor in zip(siblings, siblings[1:]): - if item.id_string != prev_id: - continue - elif successor.id_string == entry.id_string: - # We're already in place; don't change anything. - entry.position_in_parent = successor.position_in_parent - else: - # Interpolate new position between the previous item and its - # existing successor. - entry.position_in_parent = (item.position_in_parent * 7 + - successor.position_in_parent) / 8 - break - else: - # Insert at end. Includes the case where prev_id is None. - entry.position_in_parent = ExtendRange(siblings[-1], +1) entry.parent_id_string = parent_id + if not entry.HasField('position_in_parent'): + entry.position_in_parent = 1337 # A debuggable, distinctive default. entry.ClearField('insert_after_item_id') def _ItemExists(self, id_string): @@ -847,19 +807,13 @@ class SyncDataModel(object): entry = MakeTombstone(entry.id_string) else: # Comments in sync.proto detail how the representation of positional - # ordering works: the 'insert_after_item_id' field specifies a - # predecessor during Commit operations, but the 'position_in_parent' - # field provides an absolute ordering in GetUpdates contexts. Here - # we convert from the former to the latter. Specifically, we'll - # generate a numeric position placing the item just after the object - # identified by 'insert_after_item_id', and then clear the - # 'insert_after_item_id' field so that it's not sent back to the client - # during later GetUpdates requests. - if entry.HasField('insert_after_item_id'): - self._WritePosition(entry, entry.parent_id_string, - entry.insert_after_item_id) - else: - self._WritePosition(entry, entry.parent_id_string) + # ordering works: either the 'insert_after_item_id' field or the + # 'position_in_parent' field may determine the sibling order during + # Commit operations. The 'position_in_parent' field provides an absolute + # ordering in GetUpdates contexts. Here we assume the client will + # always send a valid position_in_parent (this is the newer style), and + # we ignore insert_after_item_id (an older style). + self._WritePosition(entry, entry.parent_id_string) # Preserve the originator info, which the client is not required to send # when updating. diff --git a/net/tools/testserver/chromiumsync_test.py b/net/tools/testserver/chromiumsync_test.py index f27045d..af8aa36 100755 --- a/net/tools/testserver/chromiumsync_test.py +++ b/net/tools/testserver/chromiumsync_test.py @@ -65,59 +65,6 @@ class SyncDataModelTest(unittest.TestCase): self.assertTrue(self.model._ItemExists(proto.id_string)) self.assertEqual(2, self.model._entries[proto.id_string].version) - def testWritePosition(self): - def MakeProto(id_string, parent, position): - proto = sync_pb2.SyncEntity() - proto.id_string = id_string - proto.position_in_parent = position - proto.parent_id_string = parent - self.AddToModel(proto) - - MakeProto('a', 'X', 1000) - MakeProto('b', 'X', 1800) - MakeProto('c', 'X', 2600) - MakeProto('a1', 'Z', 1007) - MakeProto('a2', 'Z', 1807) - MakeProto('a3', 'Z', 2607) - MakeProto('s', 'Y', 10000) - - def AssertPositionResult(my_id, parent_id, prev_id, expected_position): - entry = sync_pb2.SyncEntity() - entry.id_string = my_id - self.model._WritePosition(entry, parent_id, prev_id) - self.assertEqual(expected_position, entry.position_in_parent) - self.assertEqual(parent_id, entry.parent_id_string) - self.assertFalse(entry.HasField('insert_after_item_id')) - - AssertPositionResult('new', 'new_parent', '', 0) - AssertPositionResult('new', 'Y', '', 10000 - (2 ** 20)) - AssertPositionResult('new', 'Y', 's', 10000 + (2 ** 20)) - AssertPositionResult('s', 'Y', '', 10000) - AssertPositionResult('s', 'Y', 's', 10000) - AssertPositionResult('a1', 'Z', '', 1007) - - AssertPositionResult('new', 'X', '', 1000 - (2 ** 20)) - AssertPositionResult('new', 'X', 'a', 1100) - AssertPositionResult('new', 'X', 'b', 1900) - AssertPositionResult('new', 'X', 'c', 2600 + (2 ** 20)) - - AssertPositionResult('a1', 'X', '', 1000 - (2 ** 20)) - AssertPositionResult('a1', 'X', 'a', 1100) - AssertPositionResult('a1', 'X', 'b', 1900) - AssertPositionResult('a1', 'X', 'c', 2600 + (2 ** 20)) - - AssertPositionResult('a', 'X', '', 1000) - AssertPositionResult('a', 'X', 'b', 1900) - AssertPositionResult('a', 'X', 'c', 2600 + (2 ** 20)) - - AssertPositionResult('b', 'X', '', 1000 - (2 ** 20)) - AssertPositionResult('b', 'X', 'a', 1800) - AssertPositionResult('b', 'X', 'c', 2600 + (2 ** 20)) - - AssertPositionResult('c', 'X', '', 1000 - (2 ** 20)) - AssertPositionResult('c', 'X', 'a', 1100) - AssertPositionResult('c', 'X', 'b', 2600) - def testCreatePermanentItems(self): self.model._CreatePermanentItems(chromiumsync.ALL_TYPES) self.assertEqual(len(chromiumsync.ALL_TYPES) + 2, @@ -237,7 +184,7 @@ class SyncDataModelTest(unittest.TestCase): self.GetChangesFromTimestamp([sync_type], 0)) def DoCommit(original=None, id_string='', name=None, parent=None, - prev=None): + position=0): proto = sync_pb2.SyncEntity() if original is not None: proto.version = original.version @@ -252,10 +199,8 @@ class SyncDataModelTest(unittest.TestCase): proto.name = name if parent: proto.parent_id_string = parent.id_string - if prev: - proto.insert_after_item_id = prev.id_string - else: - proto.insert_after_item_id = '' + proto.insert_after_item_id = 'please discard' + proto.position_in_parent = position proto.folder = True proto.deleted = False result = self.model.CommitEntry(proto, my_cache_guid, commit_session) @@ -264,14 +209,14 @@ class SyncDataModelTest(unittest.TestCase): # Commit a new item. proto1, result1 = DoCommit(name='namae', id_string='Foo', - parent=original_changes[-1]) + parent=original_changes[-1], position=100) # Commit an item whose parent is another item (referenced via the # pre-commit ID). proto2, result2 = DoCommit(name='Secondo', id_string='Bar', - parent=proto1) + parent=proto1, position=-100) # Commit a sibling of the second item. proto3, result3 = DoCommit(name='Third!', id_string='Baz', - parent=proto1, prev=proto2) + parent=proto1, position=-50) self.assertEqual(3, len(commit_session)) for p, r in [(proto1, result1), (proto2, result2), (proto3, result3)]: @@ -296,7 +241,7 @@ class SyncDataModelTest(unittest.TestCase): self.assertTrue(c is not self.model._entries[c.id_string], "GetChanges didn't make a defensive copy.") self.assertTrue(result2.position_in_parent < result3.position_in_parent) - self.assertEqual(0, result2.position_in_parent) + self.assertEqual(-100, result2.position_in_parent) # Now update the items so that the second item is the parent of the # first; with the first sandwiched between two new items (4 and 5). @@ -308,11 +253,11 @@ class SyncDataModelTest(unittest.TestCase): proto2b, result2b = DoCommit(original=result2, parent=original_changes[-1]) proto4, result4 = DoCommit(id_string='ID4', name='Four', - parent=result2, prev=None) + parent=result2, position=-200) proto1b, result1b = DoCommit(original=result1, - parent=result2, prev=proto4) + parent=result2, position=-150) proto5, result5 = DoCommit(id_string='ID5', name='Five', parent=result2, - prev=result1) + position=150) self.assertEqual(2, len(commit_session), 'Only new items in second ' 'batch should be in the session') -- cgit v1.1