diff options
author | rlarocque@chromium.org <rlarocque@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2013-04-02 04:08:20 +0000 |
---|---|---|
committer | rlarocque@chromium.org <rlarocque@chromium.org@0039d316-1c4b-4281-b951-d872f2087c98> | 2013-04-02 04:08:20 +0000 |
commit | 457eaeb40454ac430d095da7f99f79b010167a6d (patch) | |
tree | a48fd1aba11f3bf826b6e354f1700e138f02b6f6 | |
parent | aa5d4d980164c325f35667d40d38090cb869d100 (diff) | |
download | chromium_src-457eaeb40454ac430d095da7f99f79b010167a6d.zip chromium_src-457eaeb40454ac430d095da7f99f79b010167a6d.tar.gz chromium_src-457eaeb40454ac430d095da7f99f79b010167a6d.tar.bz2 |
sync: Bookmark unique position end-to-end support
This change rewrites the bookmark positioning system to use absolute,
arbitrary-precision, unique positions from end-to-end.
First, it introduces the concept of a UNIQUE_BOOKMARK_TAG. This has a
similar format to the UNIQUE_CLIENT_TAG, though bookmarks have never
supported unique tags previously. For new items, it is initialized
based on the bookmark's originator client item ID (ie. the "c-" style
ID) and the originator's cache_guid. These values should be globally
unique.
Many previously created items that exist in the database do not have
this information available. Non-committed items will still have this
information, and will have their tags set correctly. Previously
committed items will have server style IDs and no hint as to what the
originator_cache_guid is. In that common case, we will initialize the
tag with a "fake" one based solely on the server ID. This has the
advantage of being something that all existing clients will agree on,
even it if new clients and updated items/the server will disagree with
them.
To bring everyone back into sync, whenever they receive an update
clients will access the included originator_cache_guid and
originator_client_item_id fields and reset the UNIQUE_BOOKMARK_TAG field
according to the values they find there. Over time, clients should
converge towards the same tag values.
Next, this change adds the UNIQUE_POSITION and SERVER_UNIQUE_POSITION
fields to each entry. See the UniquePosition class documentation for
more information on their behaviour. New items should have their local
position updated when they are first inserted into the list, which
should happen shortly after they are initialized. Existing items will
have these fields populated from the SERVER_ORDINAL_IN_PARENT field and
the genrated UNIQUE_BOOKMARK_TAG. Unfortunately, all outstanding local
changes will be lost during the migration.
With the addition of UNIQUE_POSITION fields comes the removal of the
PREV_ID and NEXT_ID fields. This required significant refactoring of
the Directory so it could continue to support the PutPredecessor(),
GetPredecessorId(), GetSuccessorId() and GetFirstChildId() functions. A
new class, ParentChildIndex, has been introduced to contain some of the
complexity introduced by the new system. See that class' documentation
for more information.
Communication with the server has also been affected by this change.
The client will now set the unique_position field on every update. It
will also set the legacy server_position_in_parent field with a value
derrived from a truncation of its local UNIQUE_POSITION. This replaces
the existing server position in parent calculation through
interpolation.
The receipt of updates has been changed as well. If the client receives
an update with a unique_position, it will apply it. If the update was
written by an older client, it will contain only the
server_position_in_parent. In that case, the client will use that
position and the unique tag derrived from the update to construct a
unique position that approximates the server_position_in_parent value.
This will work well if the clients have not exceeded the available
precision in an int64. Otherwise, some spurious re-positioning may
occur.
Finally, all these changes required some updates to the tests. Some
arbitrary position assertions had to be updated, since the arbitrary
ordering has changed. Some test helpers have been updated to no longer
automatically place bookmarks at the end of the list; that logic has
been moved to the tests themselves.
BUG=145412, 126505, 147715, 101852, 107744, 112203, 123429, 177521, 20011
Review URL: https://chromiumcodereview.appspot.com/11885024
git-svn-id: svn://svn.chromium.org/chrome/trunk/src@191767 0039d316-1c4b-4281-b951-d872f2087c98
62 files changed, 1865 insertions, 1379 deletions
diff --git a/chrome/browser/sync/glue/bookmark_change_processor.cc b/chrome/browser/sync/glue/bookmark_change_processor.cc index 4a660bb..0f22b2b 100644 --- a/chrome/browser/sync/glue/bookmark_change_processor.cc +++ b/chrome/browser/sync/glue/bookmark_change_processor.cc @@ -179,10 +179,7 @@ void BookmarkChangeProcessor::RemoveAllChildNodes( const int64 sync_node_id = dfs_sync_id_stack.top(); syncer::WriteNode node(trans); node.InitByIdLookup(sync_node_id); - int64 child_id = node.GetFirstChildId(); - if (child_id != syncer::kInvalidId) { - dfs_sync_id_stack.push(child_id); - } else { + if (!node.GetIsFolder() || node.GetFirstChildId() == syncer::kInvalidId) { // All children of the node has been processed, delete the node and // pop it off the stack. dfs_sync_id_stack.pop(); @@ -194,6 +191,11 @@ void BookmarkChangeProcessor::RemoveAllChildNodes( // the stack should be empty. DCHECK(dfs_sync_id_stack.empty()); } + } else { + int64 child_id = node.GetFirstChildId(); + if (child_id != syncer::kInvalidId) { + dfs_sync_id_stack.push(child_id); + } } } } diff --git a/chrome/browser/sync/profile_sync_service_bookmark_unittest.cc b/chrome/browser/sync/profile_sync_service_bookmark_unittest.cc index 38dbaa7..bc62c97 100644 --- a/chrome/browser/sync/profile_sync_service_bookmark_unittest.cc +++ b/chrome/browser/sync/profile_sync_service_bookmark_unittest.cc @@ -126,7 +126,8 @@ class FakeServerChange { // Delete the sync node. syncer::WriteNode node(trans_); EXPECT_EQ(BaseNode::INIT_OK, node.InitByIdLookup(id)); - EXPECT_FALSE(node.GetFirstChildId()); + if (node.GetIsFolder()) + EXPECT_FALSE(node.GetFirstChildId()); node.GetMutableEntryForTest()->Put(syncer::syncable::SERVER_IS_DEL, true); node.Tombstone(); @@ -567,8 +568,9 @@ class ProfileSyncServiceBookmarkTest : public testing::Test { syncer::ReadNode gnode(trans); ASSERT_EQ(BaseNode::INIT_OK, gnode.InitByIdLookup(id)); - stack.push(gnode.GetFirstChildId()); stack.push(gnode.GetSuccessorId()); + if (gnode.GetIsFolder()) + stack.push(gnode.GetFirstChildId()); } } @@ -1809,13 +1811,6 @@ TEST_F(ProfileSyncServiceBookmarkTestWithData, UpdateTransactionVersion) { GetTransactionVersions(model_->root_node(), &new_versions); EXPECT_EQ(initial_versions[model_->root_node()->id()] + 1, new_versions[model_->root_node()->id()]); - // HACK(haitaol): siblings of removed node are actually updated in sync model - // because of NEXT_ID/PREV_ID. After switching to ordinal, - // siblings will not get updated and the hack below can be - // removed. - model_->SetNodeMetaInfo(bookmark_bar->GetChild(0), - kBookmarkTransactionVersionKey, "41"); - initial_versions[bookmark_bar->GetChild(0)->id()] = 41; ExpectTransactionVersionMatch(model_->bookmark_bar_node(), initial_versions); ExpectTransactionVersionMatch(model_->other_node(), initial_versions); ExpectTransactionVersionMatch(model_->mobile_node(), initial_versions); @@ -1829,7 +1824,7 @@ TEST_F(ProfileSyncServiceBookmarkTestWithData, UpdateTransactionVersion) { GetTransactionVersions(model_->root_node(), &new_versions); EXPECT_EQ(initial_versions[model_->root_node()->id()] + 2, new_versions[model_->root_node()->id()]); - EXPECT_EQ(initial_versions[changed_bookmark->id()] + 1, + EXPECT_LT(initial_versions[changed_bookmark->id()], new_versions[changed_bookmark->id()]); initial_versions.erase(changed_bookmark->id()); ExpectTransactionVersionMatch(model_->bookmark_bar_node(), initial_versions); diff --git a/chrome/browser/sync/profile_sync_service_password_unittest.cc b/chrome/browser/sync/profile_sync_service_password_unittest.cc index cc26c7a..bf839be 100644 --- a/chrome/browser/sync/profile_sync_service_password_unittest.cc +++ b/chrome/browser/sync/profile_sync_service_password_unittest.cc @@ -253,6 +253,27 @@ class ProfileSyncServicePasswordTest : public AbstractProfileSyncServiceTest { } } + // Helper to sort the results of GetPasswordEntriesFromSyncDB. The sorting + // doesn't need to be particularly intelligent, it just needs to be consistent + // enough that we can base our tests expectations on the ordering it provides. + static bool PasswordFormComparator(const PasswordForm& pf1, + const PasswordForm& pf2) { + if (pf1.submit_element < pf2.submit_element) + return true; + if (pf1.username_element < pf2.username_element) + return true; + if (pf1.username_value < pf2.username_value) + return true; + if (pf1.username_value < pf2.username_value) + return true; + if (pf1.password_element < pf2.password_element) + return true; + if (pf1.password_value < pf2.password_value) + return true; + + return false; + } + void GetPasswordEntriesFromSyncDB(std::vector<PasswordForm>* entries) { syncer::ReadTransaction trans(FROM_HERE, sync_service_->GetUserShare()); syncer::ReadNode password_root(&trans); @@ -275,6 +296,8 @@ class ProfileSyncServicePasswordTest : public AbstractProfileSyncServiceTest { child_id = child_node.GetSuccessorId(); } + + std::sort(entries->begin(), entries->end(), PasswordFormComparator); } bool ComparePasswords(const PasswordForm& lhs, const PasswordForm& rhs) { diff --git a/sync/engine/build_commit_command.cc b/sync/engine/build_commit_command.cc index 531eaf6..96772ad 100644 --- a/sync/engine/build_commit_command.cc +++ b/sync/engine/build_commit_command.cc @@ -11,6 +11,7 @@ #include "base/string_util.h" #include "sync/engine/syncer_proto_util.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/protocol/bookmark_specifics.pb.h" #include "sync/protocol/sync.pb.h" #include "sync/sessions/ordered_commit_set.h" @@ -22,11 +23,6 @@ #include "sync/syncable/syncable_proto_util.h" #include "sync/util/time.h" -// TODO(vishwath): Remove this include after node positions have -// shifted to completely using Ordinals. -// See http://crbug.com/145412 . -#include "sync/internal_api/public/base/node_ordinal.h" - using std::set; using std::string; using std::vector; @@ -36,26 +32,11 @@ namespace syncer { using sessions::SyncSession; using syncable::Entry; using syncable::IS_DEL; -using syncable::SERVER_ORDINAL_IN_PARENT; using syncable::IS_UNAPPLIED_UPDATE; using syncable::IS_UNSYNCED; using syncable::Id; using syncable::SPECIFICS; - -// static -int64 BuildCommitCommand::GetFirstPosition() { - return std::numeric_limits<int64>::min(); -} - -// static -int64 BuildCommitCommand::GetLastPosition() { - return std::numeric_limits<int64>::max(); -} - -// static -int64 BuildCommitCommand::GetGap() { - return 1LL << 20; -} +using syncable::UNIQUE_POSITION; BuildCommitCommand::BuildCommitCommand( syncable::BaseTransaction* trans, @@ -216,30 +197,16 @@ SyncerError BuildCommitCommand::ExecuteImpl(SyncSession* session) { sync_entry->set_deleted(true); } else { if (meta_entry.Get(SPECIFICS).has_bookmark()) { - // Common data in both new and old protocol. + // Both insert_after_item_id and position_in_parent fields are set only + // for legacy reasons. See comments in sync.proto for more information. const Id& prev_id = meta_entry.GetPredecessorId(); string prev_id_string = prev_id.IsRoot() ? string() : prev_id.GetServerId(); sync_entry->set_insert_after_item_id(prev_id_string); - - // Compute a numeric position based on what we know locally. - std::pair<int64, int64> position_block( - GetFirstPosition(), GetLastPosition()); - std::map<Id, std::pair<int64, int64> >::iterator prev_pos = - position_map.find(prev_id); - if (prev_pos != position_map.end()) { - position_block = prev_pos->second; - position_map.erase(prev_pos); - } else { - position_block = std::make_pair( - FindAnchorPosition(syncable::PREV_ID, meta_entry), - FindAnchorPosition(syncable::NEXT_ID, meta_entry)); - } - position_block.first = BuildCommitCommand::InterpolatePosition( - position_block.first, position_block.second); - - position_map[id] = position_block; - sync_entry->set_position_in_parent(position_block.first); + sync_entry->set_position_in_parent( + meta_entry.Get(UNIQUE_POSITION).ToInt64()); + meta_entry.Get(UNIQUE_POSITION).ToProto( + sync_entry->mutable_unique_position()); } SetEntrySpecifics(&meta_entry, sync_entry); } @@ -248,43 +215,4 @@ SyncerError BuildCommitCommand::ExecuteImpl(SyncSession* session) { return SYNCER_OK; } -int64 BuildCommitCommand::FindAnchorPosition(syncable::IdField direction, - const syncable::Entry& entry) { - Id next_id = entry.Get(direction); - while (!next_id.IsRoot()) { - Entry next_entry(entry.trans(), - syncable::GET_BY_ID, - next_id); - if (!next_entry.Get(IS_UNSYNCED) && !next_entry.Get(IS_UNAPPLIED_UPDATE)) { - return NodeOrdinalToInt64(next_entry.Get(SERVER_ORDINAL_IN_PARENT)); - } - next_id = next_entry.Get(direction); - } - return - direction == syncable::PREV_ID ? - GetFirstPosition() : GetLastPosition(); -} - -// static -int64 BuildCommitCommand::InterpolatePosition(const int64 lo, - const int64 hi) { - DCHECK_LE(lo, hi); - - // The first item to be added under a parent gets a position of zero. - if (lo == GetFirstPosition() && hi == GetLastPosition()) - return 0; - - // For small gaps, we do linear interpolation. For larger gaps, - // we use an additive offset of |GetGap()|. We are careful to avoid - // signed integer overflow. - uint64 delta = static_cast<uint64>(hi) - static_cast<uint64>(lo); - if (delta <= static_cast<uint64>(GetGap()*2)) - return lo + (static_cast<int64>(delta) + 7) / 8; // Interpolate. - else if (lo == GetFirstPosition()) - return hi - GetGap(); // Extend range just before successor. - else - return lo + GetGap(); // Use or extend range just after predecessor. -} - - } // namespace syncer diff --git a/sync/engine/build_commit_command.h b/sync/engine/build_commit_command.h index a1b101d..a55a0b4 100644 --- a/sync/engine/build_commit_command.h +++ b/sync/engine/build_commit_command.h @@ -51,11 +51,6 @@ class SYNC_EXPORT_PRIVATE BuildCommitCommand : public SyncerCommand { private: FRIEND_TEST_ALL_PREFIXES(BuildCommitCommandTest, InterpolatePosition); - // Functions returning constants controlling range of values. - static int64 GetFirstPosition(); - static int64 GetLastPosition(); - static int64 GetGap(); - void AddExtensionsActivityToMessage(sessions::SyncSession* session, sync_pb::CommitMessage* message); @@ -63,17 +58,6 @@ class SYNC_EXPORT_PRIVATE BuildCommitCommand : public SyncerCommand { void AddClientConfigParamsToMessage(sessions::SyncSession* session, sync_pb::CommitMessage* message); - // Helper for computing position. Find the numeric position value - // of the closest already-synced entry. |direction| must be one of - // NEXT_ID or PREV_ID; this parameter controls the search direction. - // For an open range (no predecessor or successor), the return - // value will be kFirstPosition or kLastPosition. - int64 FindAnchorPosition(syncable::IdField direction, - const syncable::Entry& entry); - // Given two values of the type returned by FindAnchorPosition, - // compute a third value in between the two ranges. - static int64 InterpolatePosition(int64 lo, int64 hi); - DISALLOW_COPY_AND_ASSIGN(BuildCommitCommand); // A pointer to a valid transaction not owned by this class. diff --git a/sync/engine/build_commit_command_unittest.cc b/sync/engine/build_commit_command_unittest.cc deleted file mode 100644 index 1ad8667..0000000 --- a/sync/engine/build_commit_command_unittest.cc +++ /dev/null @@ -1,105 +0,0 @@ -// Copyright (c) 2012 The Chromium Authors. All rights reserved. -// Use of this source code is governed by a BSD-style license that can be -// found in the LICENSE file. - -#include "sync/engine/build_commit_command.h" -#include "sync/test/engine/syncer_command_test.h" - -namespace syncer { - -// A test fixture for tests exercising ClearDataCommandTest. -class BuildCommitCommandTest : public SyncerCommandTest { }; - -TEST_F(BuildCommitCommandTest, InterpolatePosition) { - EXPECT_LT(BuildCommitCommand::GetFirstPosition(), - BuildCommitCommand::GetLastPosition()); - - // Dense ranges. - EXPECT_EQ(10, BuildCommitCommand::InterpolatePosition(10, 10)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 11)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 12)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 13)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 14)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 15)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 16)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 17)); - EXPECT_EQ(11, BuildCommitCommand::InterpolatePosition(10, 18)); - EXPECT_EQ(12, BuildCommitCommand::InterpolatePosition(10, 19)); - EXPECT_EQ(12, BuildCommitCommand::InterpolatePosition(10, 20)); - - // Sparse ranges. - EXPECT_EQ(0x32535ffe3dc97LL + BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - 0x32535ffe3dc97LL, 0x61abcd323122cLL)); - EXPECT_EQ(~0x61abcd323122cLL + BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - ~0x61abcd323122cLL, ~0x32535ffe3dc97LL)); - - // Lower limits - EXPECT_EQ(BuildCommitCommand::GetFirstPosition() + 0x20, - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition(), - BuildCommitCommand::GetFirstPosition() + 0x100)); - EXPECT_EQ(BuildCommitCommand::GetFirstPosition() + 2, - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition() + 1, - BuildCommitCommand::GetFirstPosition() + 2)); - EXPECT_EQ(BuildCommitCommand::GetFirstPosition() + - BuildCommitCommand::GetGap()/8 + 1, - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition() + 1, - BuildCommitCommand::GetFirstPosition() + 1 + - BuildCommitCommand::GetGap())); - - // Extremal cases. - EXPECT_EQ(0, - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition(), - BuildCommitCommand::GetLastPosition())); - EXPECT_EQ(BuildCommitCommand::GetFirstPosition() + 1 + - BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition() + 1, - BuildCommitCommand::GetLastPosition())); - EXPECT_EQ(BuildCommitCommand::GetFirstPosition() + 1 + - BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition() + 1, - BuildCommitCommand::GetLastPosition() - 1)); - EXPECT_EQ(BuildCommitCommand::GetLastPosition() - 1 - - BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition(), - BuildCommitCommand::GetLastPosition() - 1)); - - // Edge cases around zero. - EXPECT_EQ(BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - 0, BuildCommitCommand::GetLastPosition())); - EXPECT_EQ(BuildCommitCommand::GetGap() + 1, - BuildCommitCommand::InterpolatePosition( - 1, BuildCommitCommand::GetLastPosition())); - EXPECT_EQ(BuildCommitCommand::GetGap() - 1, - BuildCommitCommand::InterpolatePosition( - -1, BuildCommitCommand::GetLastPosition())); - EXPECT_EQ(-BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition(), 0)); - EXPECT_EQ(-BuildCommitCommand::GetGap() + 1, - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition(), 1)); - EXPECT_EQ(-BuildCommitCommand::GetGap() - 1, - BuildCommitCommand::InterpolatePosition( - BuildCommitCommand::GetFirstPosition(), -1)); - EXPECT_EQ(BuildCommitCommand::GetGap() / 8, - BuildCommitCommand::InterpolatePosition( - 0, BuildCommitCommand::GetGap())); - EXPECT_EQ(BuildCommitCommand::GetGap() / 4, - BuildCommitCommand::InterpolatePosition( - 0, BuildCommitCommand::GetGap()*2)); - EXPECT_EQ(BuildCommitCommand::GetGap(), - BuildCommitCommand::InterpolatePosition( - 0, BuildCommitCommand::GetGap()*2 + 1)); -} - -} // namespace syncer diff --git a/sync/engine/conflict_resolver.cc b/sync/engine/conflict_resolver.cc index 5b485a1..074eb37 100644 --- a/sync/engine/conflict_resolver.cc +++ b/sync/engine/conflict_resolver.cc @@ -95,55 +95,18 @@ void ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans, entry.Get(syncable::SERVER_PARENT_ID); bool entry_deleted = entry.Get(syncable::IS_DEL); - // This positional check is meant to be necessary but not sufficient. As a - // result, it may be false even when the position hasn't changed, possibly - // resulting in unnecessary commits, but if it's true the position has - // definitely not changed. The check works by verifying that the prev id - // as calculated from the server position (which will ignore any - // unsynced/unapplied predecessors and be root for non-bookmark datatypes) - // matches the client prev id. Because we traverse chains of conflicting - // items in predecessor -> successor order, we don't need to also verify the - // successor matches (If it's in conflict, we'll verify it next. If it's - // not, then it should be taken into account already in the - // ComputePrevIdFromServerPosition calculation). This works even when there - // are chains of conflicting items. + // The position check might fail spuriously if one of the positions was + // based on a legacy random suffix, rather than a deterministic one based on + // originator_cache_guid and originator_item_id. If an item is being + // modified regularly, it shouldn't take long for the suffix and position to + // be updated, so such false failures shouldn't be a problem for long. // - // Example: Original sequence was abcde. Server changes to aCDbe, while - // client changes to aDCbe (C and D are in conflict). Locally, D's prev id - // is a, while C's prev id is D. On the other hand, the server prev id will - // ignore unsynced/unapplied items, so D's server prev id will also be a, - // just like C's. Because we traverse in client predecessor->successor - // order, we evaluate D first. Since prev id and server id match, we - // consider the position to have remained the same for D, and will unset - // it's UNSYNCED/UNAPPLIED bits. When we evaluate C though, we'll see that - // the prev id is D locally while the server's prev id is a. C will - // therefore count as a positional conflict (and the local data will be - // overwritten by the server data typically). The final result will be - // aCDbe (the same as the server's view). Even though both C and D were - // modified, only one counted as being in actual conflict and was resolved - // with local/server wins. - // - // In general, when there are chains of positional conflicts, only the first - // item in chain (based on the clients point of view) will have both its - // server prev id and local prev id match. For all the rest the server prev - // id will be the predecessor of the first item in the chain, and therefore - // not match the local prev id. - // - // Similarly, chains of conflicts where the server and client info are the - // same are supported due to the predecessor->successor ordering. In this - // case, from the first item onward, we unset the UNSYNCED/UNAPPLIED bits as - // we decide that nothing changed. The subsequent item's server prev id will - // accurately match the local prev id because the predecessor is no longer - // UNSYNCED/UNAPPLIED. - // TODO(zea): simplify all this once we can directly compare server position - // to client position. - syncable::Id server_prev_id = entry.ComputePrevIdFromServerPosition( - entry.Get(syncable::SERVER_PARENT_ID)); - bool needs_reinsertion = !parent_matches || - server_prev_id != entry.GetPredecessorId(); - DVLOG_IF(1, needs_reinsertion) << "Insertion needed, server prev id " - << " is " << server_prev_id << ", local prev id is " - << entry.GetPredecessorId(); + // Lucky for us, it's OK to be wrong here. The position_matches check is + // allowed to return false negatives, as long as it returns no false + // positives. + bool position_matches = parent_matches && + entry.Get(syncable::SERVER_UNIQUE_POSITION).Equals( + entry.Get(syncable::UNIQUE_POSITION)); const sync_pb::EntitySpecifics& specifics = entry.Get(syncable::SPECIFICS); const sync_pb::EntitySpecifics& server_specifics = @@ -189,7 +152,7 @@ void ConflictResolver::ProcessSimpleConflict(WriteTransaction* trans, } if (!entry_deleted && name_matches && parent_matches && specifics_match && - !needs_reinsertion) { + position_matches) { DVLOG(1) << "Resolving simple conflict, everything matches, ignoring " << "changes for: " << entry; conflict_util::IgnoreConflict(&entry); @@ -288,6 +251,11 @@ void ConflictResolver::ResolveConflicts( Entry entry(trans, syncable::GET_BY_ID, prev_id); // Any entry in conflict must be valid. CHECK(entry.good()); + + // We can't traverse over a delete item. + if (entry.Get(syncable::IS_DEL)) + break; + Id new_prev_id = entry.GetPredecessorId(); if (new_prev_id == prev_id) break; diff --git a/sync/engine/process_commit_response_command.cc b/sync/engine/process_commit_response_command.cc index 96a82bd..4a921cf 100644 --- a/sync/engine/process_commit_response_command.cc +++ b/sync/engine/process_commit_response_command.cc @@ -13,6 +13,7 @@ #include "base/location.h" #include "sync/engine/syncer_proto_util.h" #include "sync/engine/syncer_util.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/sessions/sync_session.h" #include "sync/syncable/entry.h" #include "sync/syncable/mutable_entry.h" @@ -22,11 +23,6 @@ #include "sync/syncable/syncable_write_transaction.h" #include "sync/util/time.h" -// TODO(vishwath): Remove this include after node positions have -// shifted to completely using Ordinals. -// See http://crbug.com/145412 . -#include "sync/internal_api/public/base/node_ordinal.h" - using std::set; using std::string; using std::vector; @@ -50,7 +46,6 @@ using syncable::IS_UNSYNCED; using syncable::PARENT_ID; using syncable::SERVER_IS_DEL; using syncable::SERVER_PARENT_ID; -using syncable::SERVER_ORDINAL_IN_PARENT; using syncable::SERVER_VERSION; using syncable::SYNCER; using syncable::SYNCING; @@ -342,8 +337,11 @@ void ProcessCommitResponseCommand::UpdateServerFieldsAfterCommit( ProtoTimeToTime(committed_entry.mtime())); local_entry->Put(syncable::SERVER_CTIME, ProtoTimeToTime(committed_entry.ctime())); - local_entry->Put(syncable::SERVER_ORDINAL_IN_PARENT, - Int64ToNodeOrdinal(entry_response.position_in_parent())); + if (committed_entry.has_unique_position()) { + local_entry->Put(syncable::SERVER_UNIQUE_POSITION, + UniquePosition::FromProto( + committed_entry.unique_position())); + } // TODO(nick): The server doesn't set entry_response.server_parent_id in // practice; to update SERVER_PARENT_ID appropriately here we'd need to @@ -386,23 +384,6 @@ void ProcessCommitResponseCommand::OverrideClientFieldsAfterCommit( << " to new name: " << server_name; local_entry->Put(syncable::NON_UNIQUE_NAME, server_name); } - - // The server has the final say on positioning, so apply the absolute - // position that it returns. - if (entry_response.has_position_in_parent()) { - // The SERVER_ field should already have been written. - DCHECK_EQ(entry_response.position_in_parent(), - NodeOrdinalToInt64(local_entry->Get(SERVER_ORDINAL_IN_PARENT))); - - // We just committed successfully, so we assume that the position - // value we got applies to the PARENT_ID we submitted. - syncable::Id new_prev = local_entry->ComputePrevIdFromServerPosition( - local_entry->Get(PARENT_ID)); - if (!local_entry->PutPredecessor(new_prev)) { - // TODO(lipalani) : Propagate the error to caller. crbug.com/100444. - NOTREACHED(); - } - } } void ProcessCommitResponseCommand::ProcessSuccessfulCommitResponse( diff --git a/sync/engine/process_commit_response_command_unittest.cc b/sync/engine/process_commit_response_command_unittest.cc index 5c96424..0d25c01 100644 --- a/sync/engine/process_commit_response_command_unittest.cc +++ b/sync/engine/process_commit_response_command_unittest.cc @@ -32,11 +32,13 @@ namespace syncer { using sessions::SyncSession; using syncable::BASE_VERSION; using syncable::Entry; +using syncable::ID; using syncable::IS_DIR; using syncable::IS_UNSYNCED; using syncable::Id; using syncable::MutableEntry; using syncable::NON_UNIQUE_NAME; +using syncable::UNIQUE_POSITION; using syncable::UNITTEST; using syncable::WriteTransaction; @@ -132,7 +134,6 @@ class ProcessCommitResponseCommandTest : public SyncerCommandTest { else entry_response->set_id_string(id_factory_.NewServerId().GetServerId()); entry_response->set_version(next_new_revision_++); - entry_response->set_position_in_parent(next_server_position_++); // If the ID of our parent item committed earlier in the batch was // rewritten, rewrite it in the entry response. This matches @@ -218,7 +219,6 @@ TEST_F(ProcessCommitResponseCommandTest, MultipleCommitIdProjections) { Entry b2(&trans, syncable::GET_BY_HANDLE, bookmark2_handle); CheckEntry(&b1, "bookmark 1", BOOKMARKS, new_fid); CheckEntry(&b2, "bookmark 2", BOOKMARKS, new_fid); - ASSERT_TRUE(b2.GetSuccessorId().IsRoot()); // Look at the prefs and autofill items. Entry p1(&trans, syncable::GET_BY_HANDLE, pref1_handle); @@ -230,7 +230,6 @@ TEST_F(ProcessCommitResponseCommandTest, MultipleCommitIdProjections) { Entry a2(&trans, syncable::GET_BY_HANDLE, autofill2_handle); CheckEntry(&a1, "Autofill 1", AUTOFILL, id_factory_.root()); CheckEntry(&a2, "Autofill 2", AUTOFILL, id_factory_.root()); - ASSERT_TRUE(a2.GetSuccessorId().IsRoot()); } // In this test, we test processing a commit response for a commit batch that @@ -256,25 +255,31 @@ TEST_F(ProcessCommitResponseCommandTest, NewFolderCommitKeepsChildOrder) { // Verify that the item is reachable. { - Id child_id; syncable::ReadTransaction trans(FROM_HERE, directory()); syncable::Entry root(&trans, syncable::GET_BY_ID, id_factory_.root()); ASSERT_TRUE(root.good()); - ASSERT_TRUE(directory()->GetFirstChildId( - &trans, id_factory_.root(), &child_id)); + Id child_id = root.GetFirstChildId(); ASSERT_EQ(folder_id, child_id); } // The first 25 children of the parent folder will be part of the commit - // batch. + // batch. They will be placed left to right in order of creation. int batch_size = 25; int i = 0; + Id prev_id = TestIdFactory::root(); for (; i < batch_size; ++i) { // Alternate between new and old child items, just for kicks. Id id = (i % 4 < 2) ? id_factory_.NewLocalId() : id_factory_.NewServerId(); - CreateUnprocessedCommitResult( + int64 handle = CreateUnprocessedCommitResult( id, folder_id, base::StringPrintf("Item %d", i), false, BOOKMARKS, &commit_set, &request, &response); + { + syncable::WriteTransaction trans(FROM_HERE, UNITTEST, directory()); + syncable::MutableEntry e(&trans, syncable::GET_BY_HANDLE, handle); + ASSERT_TRUE(e.good()); + e.PutPredecessor(prev_id); + } + prev_id = id; } // The second 25 children will be unsynced items but NOT part of the commit // batch. When the ID of the parent folder changes during the commit, @@ -283,9 +288,17 @@ TEST_F(ProcessCommitResponseCommandTest, NewFolderCommitKeepsChildOrder) { for (; i < 2*batch_size; ++i) { // Alternate between new and old child items, just for kicks. Id id = (i % 4 < 2) ? id_factory_.NewLocalId() : id_factory_.NewServerId(); + int64 handle = -1; test_entry_factory_->CreateUnsyncedItem( id, folder_id, base::StringPrintf("Item %d", i), - false, BOOKMARKS, NULL); + false, BOOKMARKS, &handle); + { + syncable::WriteTransaction trans(FROM_HERE, UNITTEST, directory()); + syncable::MutableEntry e(&trans, syncable::GET_BY_HANDLE, handle); + ASSERT_TRUE(e.good()); + e.PutPredecessor(prev_id); + } + prev_id = id; } // Process the commit response for the parent folder and the first @@ -299,9 +312,9 @@ TEST_F(ProcessCommitResponseCommandTest, NewFolderCommitKeepsChildOrder) { syncable::ReadTransaction trans(FROM_HERE, directory()); // Lookup the parent folder by finding a child of the root. We can't use // folder_id here, because it changed during the commit. - Id new_fid; - ASSERT_TRUE(directory()->GetFirstChildId( - &trans, id_factory_.root(), &new_fid)); + syncable::Entry root(&trans, syncable::GET_BY_ID, id_factory_.root()); + ASSERT_TRUE(root.good()); + Id new_fid = root.GetFirstChildId(); ASSERT_FALSE(new_fid.IsRoot()); EXPECT_TRUE(new_fid.ServerKnows()); EXPECT_FALSE(folder_id.ServerKnows()); @@ -313,8 +326,8 @@ TEST_F(ProcessCommitResponseCommandTest, NewFolderCommitKeepsChildOrder) { ASSERT_LT(0, parent.Get(BASE_VERSION)) << "Parent should have a valid (positive) server base revision"; - Id cid; - ASSERT_TRUE(directory()->GetFirstChildId(&trans, new_fid, &cid)); + Id cid = parent.GetFirstChildId(); + int child_count = 0; // Now loop over all the children of the parent folder, verifying // that they are in their original order by checking to see that their diff --git a/sync/engine/process_updates_command.cc b/sync/engine/process_updates_command.cc index 0789958..12498f6 100644 --- a/sync/engine/process_updates_command.cc +++ b/sync/engine/process_updates_command.cc @@ -19,11 +19,6 @@ #include "sync/syncable/syncable_write_transaction.h" #include "sync/util/cryptographer.h" -// TODO(vishwath): Remove this include after node positions have -// shifted to completely using Ordinals. -// See http://crbug.com/145412 . -#include "sync/internal_api/public/base/node_ordinal.h" - using std::vector; namespace syncer { @@ -313,12 +308,25 @@ ServerUpdateProcessingResult ProcessUpdatesCommand::ProcessUpdate( // (on which any current or future local changes are based) before we // overwrite SERVER_SPECIFICS. // MTIME, CTIME, and NON_UNIQUE_NAME are not enforced. + + bool position_matches = false; + if (target_entry.ShouldMaintainPosition() && !update.deleted()) { + std::string update_tag = GetUniqueBookmarkTagFromUpdate(update); + if (UniquePosition::IsValidSuffix(update_tag)) { + position_matches = GetUpdatePosition(update, update_tag).Equals( + target_entry.Get(syncable::SERVER_UNIQUE_POSITION)); + } else { + NOTREACHED(); + } + } else { + // If this item doesn't care about positions, then set this flag to true. + position_matches = true; + } + if (!update.deleted() && !target_entry.Get(syncable::SERVER_IS_DEL) && (SyncableIdFromProto(update.parent_id_string()) == target_entry.Get(syncable::SERVER_PARENT_ID)) && - (update.position_in_parent() == - NodeOrdinalToInt64( - target_entry.Get(syncable::SERVER_ORDINAL_IN_PARENT))) && + position_matches && update.has_specifics() && update.specifics().has_encrypted() && !cryptographer->CanDecrypt(update.specifics().encrypted())) { sync_pb::EntitySpecifics prev_specifics = diff --git a/sync/engine/process_updates_command_unittest.cc b/sync/engine/process_updates_command_unittest.cc index f4cc583..885fbe1 100644 --- a/sync/engine/process_updates_command_unittest.cc +++ b/sync/engine/process_updates_command_unittest.cc @@ -4,16 +4,22 @@ #include "base/basictypes.h" #include "sync/engine/process_updates_command.h" +#include "sync/engine/syncer_proto_util.h" #include "sync/internal_api/public/base/model_type.h" +#include "sync/internal_api/public/test/test_entry_factory.h" #include "sync/sessions/sync_session.h" #include "sync/syncable/mutable_entry.h" #include "sync/syncable/syncable_id.h" +#include "sync/syncable/syncable_proto_util.h" +#include "sync/syncable/syncable_read_transaction.h" +#include "sync/syncable/syncable_write_transaction.h" #include "sync/test/engine/fake_model_worker.h" #include "sync/test/engine/syncer_command_test.h" #include "testing/gtest/include/gtest/gtest.h" namespace syncer { +using sync_pb::SyncEntity; using syncable::Id; using syncable::MutableEntry; using syncable::UNITTEST; @@ -35,6 +41,7 @@ class ProcessUpdatesCommandTest : public SyncerCommandTest { (*mutable_routing_info())[BOOKMARKS] = GROUP_UI; (*mutable_routing_info())[AUTOFILL] = GROUP_DB; SyncerCommandTest::SetUp(); + test_entry_factory_.reset(new TestEntryFactory(directory())); } void CreateLocalItem(const std::string& item_id, @@ -54,18 +61,21 @@ class ProcessUpdatesCommandTest : public SyncerCommandTest { entry.Put(syncable::SERVER_SPECIFICS, default_specifics); } - void AddUpdate(sync_pb::GetUpdatesResponse* updates, + SyncEntity* AddUpdate(sync_pb::GetUpdatesResponse* updates, const std::string& id, const std::string& parent, const ModelType& type) { sync_pb::SyncEntity* e = updates->add_entries(); - e->set_id_string("b1"); + e->set_id_string(id); e->set_parent_id_string(parent); - e->set_non_unique_name("b1"); - e->set_name("b1"); + e->set_non_unique_name(id); + e->set_name(id); + e->set_version(1000); AddDefaultFieldValue(type, e->mutable_specifics()); + return e; } ProcessUpdatesCommand command_; + scoped_ptr<TestEntryFactory> test_entry_factory_; private: DISALLOW_COPY_AND_ASSIGN(ProcessUpdatesCommandTest); @@ -74,8 +84,6 @@ class ProcessUpdatesCommandTest : public SyncerCommandTest { TEST_F(ProcessUpdatesCommandTest, GroupsToChange) { std::string root = syncable::GetNullId().GetServerId(); - CreateLocalItem("b1", root, BOOKMARKS); - CreateLocalItem("b2", root, BOOKMARKS); CreateLocalItem("p1", root, PREFERENCES); CreateLocalItem("a1", root, AUTOFILL); @@ -84,8 +92,6 @@ TEST_F(ProcessUpdatesCommandTest, GroupsToChange) { sync_pb::GetUpdatesResponse* updates = session()->mutable_status_controller()-> mutable_updates_response()->mutable_get_updates(); - AddUpdate(updates, "b1", root, BOOKMARKS); - AddUpdate(updates, "b2", root, BOOKMARKS); AddUpdate(updates, "p1", root, PREFERENCES); AddUpdate(updates, "a1", root, AUTOFILL); @@ -94,6 +100,93 @@ TEST_F(ProcessUpdatesCommandTest, GroupsToChange) { command_.ExecuteImpl(session()); } +static const char kCacheGuid[] = "IrcjZ2jyzHDV9Io4+zKcXQ=="; + +// Test that the bookmark tag is set on newly downloaded items. +TEST_F(ProcessUpdatesCommandTest, NewBookmarkTag) { + std::string root = syncable::GetNullId().GetServerId(); + sync_pb::GetUpdatesResponse* updates = + session()->mutable_status_controller()-> + mutable_updates_response()->mutable_get_updates(); + Id server_id = Id::CreateFromServerId("b1"); + SyncEntity* e = + AddUpdate(updates, SyncableIdToProto(server_id), root, BOOKMARKS); + + e->set_originator_cache_guid( + std::string(kCacheGuid, arraysize(kCacheGuid)-1)); + Id client_id = Id::CreateFromClientString("-2"); + e->set_originator_client_item_id(client_id.GetServerId()); + e->set_position_in_parent(0); + + command_.ExecuteImpl(session()); + + syncable::ReadTransaction trans(FROM_HERE, directory()); + syncable::Entry entry(&trans, syncable::GET_BY_ID, server_id); + ASSERT_TRUE(entry.good()); + EXPECT_TRUE( + UniquePosition::IsValidSuffix(entry.Get(syncable::UNIQUE_BOOKMARK_TAG))); + EXPECT_TRUE(entry.Get(syncable::SERVER_UNIQUE_POSITION).IsValid()); + + // If this assertion fails, that might indicate that the algorithm used to + // generate bookmark tags has been modified. This could have implications for + // bookmark ordering. Please make sure you know what you're doing if you + // intend to make such a change. + EXPECT_EQ("6wHRAb3kbnXV5GHrejp4/c1y5tw=", + entry.Get(syncable::UNIQUE_BOOKMARK_TAG)); +} + +TEST_F(ProcessUpdatesCommandTest, ReceiveServerCreatedBookmarkFolders) { + Id server_id = Id::CreateFromServerId("xyz"); + std::string root = syncable::GetNullId().GetServerId(); + sync_pb::GetUpdatesResponse* updates = + session()->mutable_status_controller()-> + mutable_updates_response()->mutable_get_updates(); + + // Create an update that mimics the bookmark root. + SyncEntity* e = + AddUpdate(updates, SyncableIdToProto(server_id), root, BOOKMARKS); + e->set_server_defined_unique_tag("google_chrome_bookmarks"); + e->set_folder(true); + + EXPECT_FALSE(SyncerProtoUtil::ShouldMaintainPosition(*e)); + + command_.ExecuteImpl(session()); + + syncable::ReadTransaction trans(FROM_HERE, directory()); + syncable::Entry entry(&trans, syncable::GET_BY_ID, server_id); + ASSERT_TRUE(entry.good()); + + EXPECT_FALSE(entry.ShouldMaintainPosition()); + EXPECT_FALSE(entry.Get(syncable::UNIQUE_POSITION).IsValid()); + EXPECT_FALSE(entry.Get(syncable::SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_TRUE(entry.Get(syncable::UNIQUE_BOOKMARK_TAG).empty()); +} + +TEST_F(ProcessUpdatesCommandTest, ReceiveNonBookmarkItem) { + Id server_id = Id::CreateFromServerId("xyz"); + std::string root = syncable::GetNullId().GetServerId(); + sync_pb::GetUpdatesResponse* updates = + session()->mutable_status_controller()-> + mutable_updates_response()->mutable_get_updates(); + + SyncEntity* e = + AddUpdate(updates, SyncableIdToProto(server_id), root, AUTOFILL); + e->set_server_defined_unique_tag("9PGRuKdX5sHyGMB17CvYTXuC43I="); + + EXPECT_FALSE(SyncerProtoUtil::ShouldMaintainPosition(*e)); + + command_.ExecuteImpl(session()); + + syncable::ReadTransaction trans(FROM_HERE, directory()); + syncable::Entry entry(&trans, syncable::GET_BY_ID, server_id); + ASSERT_TRUE(entry.good()); + + EXPECT_FALSE(entry.ShouldMaintainPosition()); + EXPECT_FALSE(entry.Get(syncable::UNIQUE_POSITION).IsValid()); + EXPECT_FALSE(entry.Get(syncable::SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_TRUE(entry.Get(syncable::UNIQUE_BOOKMARK_TAG).empty()); +} + } // namespace } // namespace syncer diff --git a/sync/engine/syncer.cc b/sync/engine/syncer.cc index 90d193a..ad0d534 100644 --- a/sync/engine/syncer.cc +++ b/sync/engine/syncer.cc @@ -22,14 +22,10 @@ #include "sync/engine/store_timestamps_command.h" #include "sync/engine/syncer_types.h" #include "sync/engine/throttled_data_type_tracker.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/syncable/mutable_entry.h" #include "sync/syncable/syncable-inl.h" -// TODO(vishwath): Remove this include after node positions have -// shifted to completely using Ordinals. -// See http://crbug.com/145412 . -#include "sync/internal_api/public/base/node_ordinal.h" - using base::Time; using base::TimeDelta; using sync_pb::ClientCommand; @@ -45,8 +41,8 @@ using syncable::SERVER_IS_DIR; using syncable::SERVER_MTIME; using syncable::SERVER_NON_UNIQUE_NAME; using syncable::SERVER_PARENT_ID; -using syncable::SERVER_ORDINAL_IN_PARENT; using syncable::SERVER_SPECIFICS; +using syncable::SERVER_UNIQUE_POSITION; using syncable::SERVER_VERSION; #define ENUM_CASE(x) case x: return #x @@ -198,20 +194,7 @@ void CopyServerFields(syncable::Entry* src, syncable::MutableEntry* dest) { dest->Put(SERVER_IS_DEL, src->Get(SERVER_IS_DEL)); dest->Put(IS_UNAPPLIED_UPDATE, src->Get(IS_UNAPPLIED_UPDATE)); dest->Put(SERVER_SPECIFICS, src->Get(SERVER_SPECIFICS)); - dest->Put(SERVER_ORDINAL_IN_PARENT, src->Get(SERVER_ORDINAL_IN_PARENT)); -} - -void ClearServerData(syncable::MutableEntry* entry) { - entry->Put(SERVER_NON_UNIQUE_NAME, ""); - entry->Put(SERVER_PARENT_ID, syncable::GetNullId()); - entry->Put(SERVER_MTIME, Time()); - entry->Put(SERVER_CTIME, Time()); - entry->Put(SERVER_VERSION, 0); - entry->Put(SERVER_IS_DIR, false); - entry->Put(SERVER_IS_DEL, false); - entry->Put(IS_UNAPPLIED_UPDATE, false); - entry->Put(SERVER_SPECIFICS, sync_pb::EntitySpecifics::default_instance()); - entry->Put(SERVER_ORDINAL_IN_PARENT, Int64ToNodeOrdinal(0)); + dest->Put(SERVER_UNIQUE_POSITION, src->Get(SERVER_UNIQUE_POSITION)); } } // namespace syncer diff --git a/sync/engine/syncer.h b/sync/engine/syncer.h index ac7892e..8656e7c 100644 --- a/sync/engine/syncer.h +++ b/sync/engine/syncer.h @@ -95,7 +95,6 @@ class SYNC_EXPORT_PRIVATE Syncer { // Utility function declarations. void CopyServerFields(syncable::Entry* src, syncable::MutableEntry* dest); -void ClearServerData(syncable::MutableEntry* entry); const char* SyncerStepToString(const SyncerStep); } // namespace syncer diff --git a/sync/engine/syncer_proto_util.cc b/sync/engine/syncer_proto_util.cc index 9138417..3b72c17 100644 --- a/sync/engine/syncer_proto_util.cc +++ b/sync/engine/syncer_proto_util.cc @@ -519,6 +519,16 @@ bool SyncerProtoUtil::Compare(const syncable::Entry& local_entry, } // static +bool SyncerProtoUtil::ShouldMaintainPosition( + const sync_pb::SyncEntity& sync_entity) { + // Maintain positions for bookmarks that are not server-defined top-level + // folders. + return GetModelType(sync_entity) == BOOKMARKS + && !(sync_entity.folder() && + !sync_entity.server_defined_unique_tag().empty()); +} + +// static void SyncerProtoUtil::CopyProtoBytesIntoBlob(const std::string& proto_bytes, syncable::Blob* blob) { syncable::Blob proto_blob(proto_bytes.begin(), proto_bytes.end()); diff --git a/sync/engine/syncer_proto_util.h b/sync/engine/syncer_proto_util.h index 1f271d8..fedd211 100644 --- a/sync/engine/syncer_proto_util.h +++ b/sync/engine/syncer_proto_util.h @@ -69,6 +69,8 @@ class SYNC_EXPORT_PRIVATE SyncerProtoUtil { static bool Compare(const syncable::Entry& local_entry, const sync_pb::SyncEntity& server_entry); + static bool ShouldMaintainPosition(const sync_pb::SyncEntity& sync_entity); + // Utility methods for converting between syncable::Blobs and protobuf byte // fields. static void CopyProtoBytesIntoBlob(const std::string& proto_bytes, diff --git a/sync/engine/syncer_unittest.cc b/sync/engine/syncer_unittest.cc index 44b452f..5ee9e47 100644 --- a/sync/engine/syncer_unittest.cc +++ b/sync/engine/syncer_unittest.cc @@ -33,7 +33,6 @@ #include "sync/engine/traffic_recorder.h" #include "sync/internal_api/public/base/model_type.h" #include "sync/internal_api/public/engine/model_safe_worker.h" -#include "sync/internal_api/public/base/node_ordinal.h" #include "sync/protocol/bookmark_specifics.pb.h" #include "sync/protocol/nigori_specifics.pb.h" #include "sync/protocol/preference_specifics.pb.h" @@ -59,10 +58,12 @@ using base::TimeDelta; +using std::count; using std::map; using std::multimap; using std::set; using std::string; +using std::vector; namespace syncer { @@ -96,7 +97,6 @@ using syncable::PARENT_ID; using syncable::BASE_SERVER_SPECIFICS; using syncable::SERVER_IS_DEL; using syncable::SERVER_PARENT_ID; -using syncable::SERVER_ORDINAL_IN_PARENT; using syncable::SERVER_SPECIFICS; using syncable::SERVER_VERSION; using syncable::UNIQUE_CLIENT_TAG; @@ -860,6 +860,12 @@ TEST_F(SyncerTest, EncryptionAwareConflicts) { EXPECT_TRUE(GetCryptographer(&wtrans)->has_pending_keys()); } + // We need to remember the exact position of our local items, so we can + // make updates that do not modify those positions. + UniquePosition pos1; + UniquePosition pos2; + UniquePosition pos3; + mock_server_->AddUpdateSpecifics(1, 0, "A", 10, 10, true, 0, bookmark, foreign_cache_guid(), "-1"); mock_server_->AddUpdateSpecifics(2, 1, "B", 10, 10, false, 2, bookmark, @@ -875,6 +881,15 @@ TEST_F(SyncerTest, EncryptionAwareConflicts) { VERIFY_ENTRY(2, false, false, false, 1, 10, 10, ids_, &rtrans); VERIFY_ENTRY(3, false, false, false, 1, 10, 10, ids_, &rtrans); VERIFY_ENTRY(4, false, false, false, 0, 10, 10, ids_, &rtrans); + + Entry entry1(&rtrans, syncable::GET_BY_ID, ids_.FromNumber(1)); + ASSERT_TRUE(entry1.Get(syncable::UNIQUE_POSITION).Equals( + entry1.Get(syncable::SERVER_UNIQUE_POSITION))); + pos1 = entry1.Get(syncable::UNIQUE_POSITION); + Entry entry2(&rtrans, syncable::GET_BY_ID, ids_.FromNumber(2)); + pos2 = entry2.Get(syncable::UNIQUE_POSITION); + Entry entry3(&rtrans, syncable::GET_BY_ID, ids_.FromNumber(3)); + pos3 = entry3.Get(syncable::UNIQUE_POSITION); } // Server side encryption will not be applied due to undecryptable data. @@ -1418,13 +1433,29 @@ TEST_F(SyncerTest, TestCommitListOrderingWithNewItems) { SyncShareNudge(); ASSERT_EQ(6u, mock_server_->committed_ids().size()); - // If this test starts failing, be aware other sort orders could be valid. - EXPECT_TRUE(parent1_id == mock_server_->committed_ids()[0]); - EXPECT_TRUE(parent2_id == mock_server_->committed_ids()[1]); - EXPECT_TRUE(ids_.FromNumber(102) == mock_server_->committed_ids()[2]); - EXPECT_TRUE(ids_.FromNumber(-103) == mock_server_->committed_ids()[3]); - EXPECT_TRUE(ids_.FromNumber(-104) == mock_server_->committed_ids()[4]); - EXPECT_TRUE(ids_.FromNumber(105) == mock_server_->committed_ids()[5]); + + // This strange iteration and std::count() usage is to allow the order to + // vary. All we really care about is that parent1_id and parent2_id are the + // first two IDs, and that the children make up the next four. Other than + // that, ordering doesn't matter. + + vector<syncable::Id>::const_iterator i = + mock_server_->committed_ids().begin(); + vector<syncable::Id>::const_iterator parents_begin = i; + i++; + i++; + vector<syncable::Id>::const_iterator parents_end = i; + vector<syncable::Id>::const_iterator children_begin = i; + vector<syncable::Id>::const_iterator children_end = + mock_server_->committed_ids().end(); + + EXPECT_EQ(1, count(parents_begin, parents_end, parent1_id)); + EXPECT_EQ(1, count(parents_begin, parents_end, parent2_id)); + + EXPECT_EQ(1, count(children_begin, children_end, ids_.FromNumber(-103))); + EXPECT_EQ(1, count(children_begin, children_end, ids_.FromNumber(102))); + EXPECT_EQ(1, count(children_begin, children_end, ids_.FromNumber(105))); + EXPECT_EQ(1, count(children_begin, children_end, ids_.FromNumber(-104))); } TEST_F(SyncerTest, TestCommitListOrderingCounterexample) { @@ -1456,10 +1487,15 @@ TEST_F(SyncerTest, TestCommitListOrderingCounterexample) { SyncShareNudge(); ASSERT_EQ(3u, mock_server_->committed_ids().size()); - // If this test starts failing, be aware other sort orders could be valid. EXPECT_TRUE(parent_id_ == mock_server_->committed_ids()[0]); - EXPECT_TRUE(child_id_ == mock_server_->committed_ids()[1]); - EXPECT_TRUE(child2_id == mock_server_->committed_ids()[2]); + // There are two possible valid orderings. + if (child2_id == mock_server_->committed_ids()[1]) { + EXPECT_TRUE(child2_id == mock_server_->committed_ids()[1]); + EXPECT_TRUE(child_id_ == mock_server_->committed_ids()[2]); + } else { + EXPECT_TRUE(child_id_ == mock_server_->committed_ids()[1]); + EXPECT_TRUE(child2_id == mock_server_->committed_ids()[2]); + } } TEST_F(SyncerTest, TestCommitListOrderingAndNewParent) { @@ -2340,7 +2376,6 @@ TEST_F(SyncerTest, CommitsUpdateDoesntAlterEntry) { SyncShareNudge(); syncable::Id id; int64 version; - NodeOrdinal server_ordinal_in_parent; { syncable::ReadTransaction trans(FROM_HERE, directory()); Entry entry(&trans, syncable::GET_BY_HANDLE, entry_metahandle); @@ -2348,7 +2383,6 @@ TEST_F(SyncerTest, CommitsUpdateDoesntAlterEntry) { id = entry.Get(ID); EXPECT_TRUE(id.ServerKnows()); version = entry.Get(BASE_VERSION); - server_ordinal_in_parent = entry.Get(SERVER_ORDINAL_IN_PARENT); } sync_pb::SyncEntity* update = mock_server_->AddUpdateFromLastCommit(); update->set_originator_cache_guid(local_cache_guid()); @@ -2357,9 +2391,6 @@ TEST_F(SyncerTest, CommitsUpdateDoesntAlterEntry) { EXPECT_EQ(id.GetServerId(), update->id_string()); EXPECT_EQ(root_id_.GetServerId(), update->parent_id_string()); EXPECT_EQ(version, update->version()); - EXPECT_EQ( - NodeOrdinalToInt64(server_ordinal_in_parent), - update->position_in_parent()); SyncShareNudge(); { syncable::ReadTransaction trans(FROM_HERE, directory()); @@ -4702,225 +4733,6 @@ TEST_F(SyncerUndeletionTest, OtherClientUndeletesImmediately) { EXPECT_EQ("Thadeusz", Get(metahandle_, NON_UNIQUE_NAME)); } -// A group of tests exercising the syncer's handling of sibling ordering, as -// represented in the sync protocol. -class SyncerPositionUpdateTest : public SyncerTest { - public: - SyncerPositionUpdateTest() : next_update_id_(1), next_revision_(1) {} - - protected: - void ExpectLocalItemsInServerOrder() { - if (position_map_.empty()) - return; - - syncable::ReadTransaction trans(FROM_HERE, directory()); - - Id prev_id; - DCHECK(prev_id.IsRoot()); - PosMap::iterator next = position_map_.begin(); - for (PosMap::iterator i = next++; i != position_map_.end(); ++i) { - Id id = i->second; - Entry entry_with_id(&trans, GET_BY_ID, id); - EXPECT_TRUE(entry_with_id.good()); - EXPECT_EQ(prev_id, entry_with_id.GetPredecessorId()); - EXPECT_EQ( - i->first, - NodeOrdinalToInt64(entry_with_id.Get(SERVER_ORDINAL_IN_PARENT))); - if (next == position_map_.end()) { - EXPECT_EQ(Id(), entry_with_id.GetSuccessorId()); - } else { - EXPECT_EQ(next->second, entry_with_id.GetSuccessorId()); - next++; - } - prev_id = id; - } - } - - void AddRootItemWithPosition(int64 position) { - string id = string("ServerId") + base::Int64ToString(next_update_id_++); - string name = "my name is my id -- " + id; - int revision = next_revision_++; - mock_server_->AddUpdateDirectory(id, kRootId, name, revision, revision, - foreign_cache_guid(), - ids_.NewLocalId().GetServerId()); - mock_server_->SetLastUpdatePosition(position); - position_map_.insert( - PosMap::value_type(position, Id::CreateFromServerId(id))); - } - private: - typedef multimap<int64, Id> PosMap; - PosMap position_map_; - int next_update_id_; - int next_revision_; - DISALLOW_COPY_AND_ASSIGN(SyncerPositionUpdateTest); -}; - -TEST_F(SyncerPositionUpdateTest, InOrderPositive) { - // Add a bunch of items in increasing order, starting with just positive - // position values. - AddRootItemWithPosition(100); - AddRootItemWithPosition(199); - AddRootItemWithPosition(200); - AddRootItemWithPosition(201); - AddRootItemWithPosition(400); - - SyncShareNudge(); - ExpectLocalItemsInServerOrder(); -} - -TEST_F(SyncerPositionUpdateTest, InOrderNegative) { - // Test negative position values, but in increasing order. - AddRootItemWithPosition(-400); - AddRootItemWithPosition(-201); - AddRootItemWithPosition(-200); - AddRootItemWithPosition(-150); - AddRootItemWithPosition(100); - - SyncShareNudge(); - ExpectLocalItemsInServerOrder(); -} - -TEST_F(SyncerPositionUpdateTest, ReverseOrder) { - // Test when items are sent in the reverse order. - AddRootItemWithPosition(400); - AddRootItemWithPosition(201); - AddRootItemWithPosition(200); - AddRootItemWithPosition(100); - AddRootItemWithPosition(-150); - AddRootItemWithPosition(-201); - AddRootItemWithPosition(-200); - AddRootItemWithPosition(-400); - - SyncShareNudge(); - ExpectLocalItemsInServerOrder(); -} - -TEST_F(SyncerPositionUpdateTest, RandomOrderInBatches) { - // Mix it all up, interleaving position values, and try multiple batches of - // updates. - AddRootItemWithPosition(400); - AddRootItemWithPosition(201); - AddRootItemWithPosition(-400); - AddRootItemWithPosition(100); - - SyncShareNudge(); - ExpectLocalItemsInServerOrder(); - - AddRootItemWithPosition(-150); - AddRootItemWithPosition(-200); - AddRootItemWithPosition(200); - AddRootItemWithPosition(-201); - - SyncShareNudge(); - ExpectLocalItemsInServerOrder(); - - AddRootItemWithPosition(-144); - - SyncShareNudge(); - ExpectLocalItemsInServerOrder(); -} - -class SyncerPositionTiebreakingTest : public SyncerTest { - public: - SyncerPositionTiebreakingTest() - : low_id_(Id::CreateFromServerId("A")), - mid_id_(Id::CreateFromServerId("M")), - high_id_(Id::CreateFromServerId("Z")), - next_revision_(1) { - DCHECK(low_id_ < mid_id_); - DCHECK(mid_id_ < high_id_); - DCHECK(low_id_ < high_id_); - } - - // Adds the item by its Id, using a constant value for the position - // so that the syncer has to resolve the order some other way. - void Add(const Id& id) { - int revision = next_revision_++; - mock_server_->AddUpdateDirectory(id.GetServerId(), kRootId, - id.GetServerId(), revision, revision, - foreign_cache_guid(), ids_.NewLocalId().GetServerId()); - // The update position doesn't vary. - mock_server_->SetLastUpdatePosition(90210); - } - - void ExpectLocalOrderIsByServerId() { - syncable::ReadTransaction trans(FROM_HERE, directory()); - Id null_id; - Entry low(&trans, GET_BY_ID, low_id_); - Entry mid(&trans, GET_BY_ID, mid_id_); - Entry high(&trans, GET_BY_ID, high_id_); - EXPECT_TRUE(low.good()); - EXPECT_TRUE(mid.good()); - EXPECT_TRUE(high.good()); - EXPECT_TRUE(low.GetPredecessorId() == null_id); - EXPECT_TRUE(mid.GetPredecessorId() == low_id_); - EXPECT_TRUE(high.GetPredecessorId() == mid_id_); - EXPECT_TRUE(high.GetSuccessorId() == null_id); - EXPECT_TRUE(mid.GetSuccessorId() == high_id_); - EXPECT_TRUE(low.GetSuccessorId() == mid_id_); - } - - protected: - // When there's a tiebreak on the numeric position, it's supposed to be - // broken by string comparison of the ids. These ids are in increasing - // order. - const Id low_id_; - const Id mid_id_; - const Id high_id_; - - private: - int next_revision_; - DISALLOW_COPY_AND_ASSIGN(SyncerPositionTiebreakingTest); -}; - -TEST_F(SyncerPositionTiebreakingTest, LowMidHigh) { - Add(low_id_); - Add(mid_id_); - Add(high_id_); - SyncShareNudge(); - ExpectLocalOrderIsByServerId(); -} - -TEST_F(SyncerPositionTiebreakingTest, LowHighMid) { - Add(low_id_); - Add(high_id_); - Add(mid_id_); - SyncShareNudge(); - ExpectLocalOrderIsByServerId(); -} - -TEST_F(SyncerPositionTiebreakingTest, HighMidLow) { - Add(high_id_); - Add(mid_id_); - Add(low_id_); - SyncShareNudge(); - ExpectLocalOrderIsByServerId(); -} - -TEST_F(SyncerPositionTiebreakingTest, HighLowMid) { - Add(high_id_); - Add(low_id_); - Add(mid_id_); - SyncShareNudge(); - ExpectLocalOrderIsByServerId(); -} - -TEST_F(SyncerPositionTiebreakingTest, MidHighLow) { - Add(mid_id_); - Add(high_id_); - Add(low_id_); - SyncShareNudge(); - ExpectLocalOrderIsByServerId(); -} - -TEST_F(SyncerPositionTiebreakingTest, MidLowHigh) { - Add(mid_id_); - Add(low_id_); - Add(high_id_); - SyncShareNudge(); - ExpectLocalOrderIsByServerId(); -} - enum { TEST_PARAM_BOOKMARK_ENABLE_BIT, TEST_PARAM_AUTOFILL_ENABLE_BIT, diff --git a/sync/engine/syncer_util.cc b/sync/engine/syncer_util.cc index 3548ba1..c571b10 100644 --- a/sync/engine/syncer_util.cc +++ b/sync/engine/syncer_util.cc @@ -9,12 +9,15 @@ #include <string> #include <vector> +#include "base/base64.h" #include "base/location.h" #include "base/metrics/histogram.h" +#include "base/string_number_conversions.h" #include "sync/engine/conflict_resolver.h" #include "sync/engine/syncer_proto_util.h" #include "sync/engine/syncer_types.h" #include "sync/internal_api/public/base/model_type.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/protocol/bookmark_specifics.pb.h" #include "sync/protocol/password_specifics.pb.h" #include "sync/protocol/sync.pb.h" @@ -29,13 +32,9 @@ #include "sync/util/cryptographer.h" #include "sync/util/time.h" -// TODO(vishwath): Remove this include after node positions have -// shifted to completely uing Ordinals. -// See http://crbug.com/145412 . -#include "sync/internal_api/public/base/node_ordinal.h" - namespace syncer { +using syncable::BASE_SERVER_SPECIFICS; using syncable::BASE_VERSION; using syncable::CHANGES_VERSION; using syncable::CREATE_NEW_UPDATE_ITEM; @@ -54,7 +53,6 @@ using syncable::META_HANDLE; using syncable::MTIME; using syncable::MutableEntry; using syncable::NON_UNIQUE_NAME; -using syncable::BASE_SERVER_SPECIFICS; using syncable::PARENT_ID; using syncable::SERVER_CTIME; using syncable::SERVER_IS_DEL; @@ -62,13 +60,15 @@ using syncable::SERVER_IS_DIR; using syncable::SERVER_MTIME; using syncable::SERVER_NON_UNIQUE_NAME; using syncable::SERVER_PARENT_ID; -using syncable::SERVER_ORDINAL_IN_PARENT; using syncable::SERVER_SPECIFICS; +using syncable::SERVER_UNIQUE_POSITION; using syncable::SERVER_VERSION; -using syncable::UNIQUE_CLIENT_TAG; -using syncable::UNIQUE_SERVER_TAG; using syncable::SPECIFICS; using syncable::SYNCER; +using syncable::UNIQUE_BOOKMARK_TAG; +using syncable::UNIQUE_CLIENT_TAG; +using syncable::UNIQUE_POSITION; +using syncable::UNIQUE_SERVER_TAG; using syncable::WriteTransaction; syncable::Id FindLocalIdToUpdate( @@ -273,7 +273,32 @@ UpdateAttemptResponse AttemptToUpdateEntry( return SUCCESS; } +std::string GetUniqueBookmarkTagFromUpdate(const sync_pb::SyncEntity& update) { + if (!update.has_originator_cache_guid() || + !update.has_originator_client_item_id()) { + return std::string(); + } + + return syncable::GenerateSyncableBookmarkHash( + update.originator_cache_guid(), update.originator_client_item_id()); +} + +UniquePosition GetUpdatePosition(const sync_pb::SyncEntity& update, + const std::string& suffix) { + DCHECK(UniquePosition::IsValidSuffix(suffix)); + if (!(SyncerProtoUtil::ShouldMaintainPosition(update))) { + return UniquePosition::CreateInvalid(); + } else if (update.has_unique_position()) { + return UniquePosition::FromProto(update.unique_position()); + } else if (update.has_position_in_parent()) { + return UniquePosition::FromInt64(update.position_in_parent(), suffix); + } else { + return UniquePosition::CreateInvalid(); + } +} + namespace { + // Helper to synthesize a new-style sync_pb::EntitySpecifics for use locally, // when the server speaks only the old sync_pb::SyncEntity_BookmarkData-based // protocol. @@ -294,9 +319,34 @@ void UpdateBookmarkSpecifics(const std::string& singleton_tag, local_entry->Put(SERVER_SPECIFICS, pb); } +void UpdateBookmarkPositioning(const sync_pb::SyncEntity& update, + MutableEntry* local_entry) { + // Update our unique bookmark tag. In many cases this will be identical to + // the tag we already have. However, clients that have recently upgraded to + // versions that support unique positions will have incorrect tags. See the + // v86 migration logic in directory_backing_store.cc for more information. + // + // Both the old and new values are unique to this element. Applying this + // update will not risk the creation of conflicting unique tags. + std::string bookmark_tag = GetUniqueBookmarkTagFromUpdate(update); + if (UniquePosition::IsValidSuffix(bookmark_tag)) { + local_entry->PutUniqueBookmarkTag(bookmark_tag); + } + + // Update our position. + UniquePosition update_pos = + GetUpdatePosition(update, local_entry->Get(UNIQUE_BOOKMARK_TAG)); + if (update_pos.IsValid()) { + local_entry->Put(syncable::SERVER_UNIQUE_POSITION, update_pos); + } else { + // TODO(sync): This and other cases of unexpected input should be handled + // better. + NOTREACHED(); + } +} + } // namespace -// Pass in name and checksum because of UTF8 conversion. void UpdateServerFieldsFromUpdate( MutableEntry* target, const sync_pb::SyncEntity& update, @@ -355,9 +405,9 @@ void UpdateServerFieldsFromUpdate( bookmark.bookmark_favicon(), target); } - if (update.has_position_in_parent()) - target->Put(SERVER_ORDINAL_IN_PARENT, - Int64ToNodeOrdinal(update.position_in_parent())); + if (SyncerProtoUtil::ShouldMaintainPosition(update)) { + UpdateBookmarkPositioning(update, target); + } target->Put(SERVER_IS_DEL, update.deleted()); // We only mark the entry as unapplied if its version is greater than the @@ -378,21 +428,6 @@ void CreateNewEntry(syncable::WriteTransaction *trans, } } -void SplitServerInformationIntoNewEntry( - syncable::WriteTransaction* trans, - syncable::MutableEntry* entry) { - syncable::Id id = entry->Get(ID); - ChangeEntryIDAndUpdateChildren(trans, entry, trans->directory()->NextId()); - entry->Put(BASE_VERSION, 0); - - MutableEntry new_entry(trans, CREATE_NEW_UPDATE_ITEM, id); - CopyServerFields(entry, &new_entry); - ClearServerData(entry); - - DVLOG(1) << "Splitting server information, local entry: " << *entry - << " server entry: " << new_entry; -} - // This function is called on an entry when we can update the user-facing data // from the server data. void UpdateLocalDataFromServerData( @@ -415,11 +450,8 @@ void UpdateLocalDataFromServerData( } else { entry->Put(NON_UNIQUE_NAME, entry->Get(SERVER_NON_UNIQUE_NAME)); entry->Put(PARENT_ID, entry->Get(SERVER_PARENT_ID)); + entry->Put(UNIQUE_POSITION, entry->Get(SERVER_UNIQUE_POSITION)); CHECK(entry->Put(IS_DEL, false)); - Id new_predecessor = - entry->ComputePrevIdFromServerPosition(entry->Get(SERVER_PARENT_ID)); - CHECK(entry->PutPredecessor(new_predecessor)) - << " Illegal predecessor after converting from server position."; } entry->Put(CTIME, entry->Get(SERVER_CTIME)); @@ -448,47 +480,6 @@ VerifyCommitResult ValidateCommitEntry(syncable::Entry* entry) { return VERIFY_OK; } -bool AddItemThenPredecessors( - syncable::BaseTransaction* trans, - syncable::Entry* item, - syncable::IndexedBitField inclusion_filter, - syncable::MetahandleSet* inserted_items, - std::vector<syncable::Id>* commit_ids) { - - if (!inserted_items->insert(item->Get(META_HANDLE)).second) - return false; - commit_ids->push_back(item->Get(ID)); - if (item->Get(IS_DEL)) - return true; // Deleted items have no predecessors. - - Id prev_id = item->GetPredecessorId(); - while (!prev_id.IsRoot()) { - Entry prev(trans, GET_BY_ID, prev_id); - CHECK(prev.good()) << "Bad id when walking predecessors."; - if (!prev.Get(inclusion_filter)) - break; - if (!inserted_items->insert(prev.Get(META_HANDLE)).second) - break; - commit_ids->push_back(prev_id); - prev_id = prev.GetPredecessorId(); - } - return true; -} - -void AddPredecessorsThenItem( - syncable::BaseTransaction* trans, - syncable::Entry* item, - syncable::IndexedBitField inclusion_filter, - syncable::MetahandleSet* inserted_items, - std::vector<syncable::Id>* commit_ids) { - size_t initial_size = commit_ids->size(); - if (!AddItemThenPredecessors(trans, item, inclusion_filter, inserted_items, - commit_ids)) - return; - // Reverse what we added to get the correct order. - std::reverse(commit_ids->begin() + initial_size, commit_ids->end()); -} - void MarkDeletedChildrenSynced( syncable::Directory* dir, std::set<syncable::Id>* deleted_folders) { diff --git a/sync/engine/syncer_util.h b/sync/engine/syncer_util.h index 108622c..ea947ab 100644 --- a/sync/engine/syncer_util.h +++ b/sync/engine/syncer_util.h @@ -48,6 +48,21 @@ UpdateAttemptResponse AttemptToUpdateEntry( syncable::MutableEntry* const entry, Cryptographer* cryptographer); +// Returns the most accurate position information available in this update. It +// prefers to use the unique_position() field, but will fall back to using the +// int64-based position_in_parent if necessary. +// +// The suffix parameter is the unique bookmark tag for the item being updated. +// +// Will return an invalid position if no valid position can be constructed, or +// if this type does not support positioning. +UniquePosition GetUpdatePosition(const sync_pb::SyncEntity& update, + const std::string& suffix); + +// Fetch the cache_guid and item_id-based unique bookmark tag from an update. +// Will return an empty string if someting unexpected happens. +std::string GetUniqueBookmarkTagFromUpdate(const sync_pb::SyncEntity& update); + // Pass in name to avoid redundant UTF8 conversion. void UpdateServerFieldsFromUpdate( syncable::MutableEntry* local_entry, @@ -58,10 +73,6 @@ void UpdateServerFieldsFromUpdate( void CreateNewEntry(syncable::WriteTransaction *trans, const syncable::Id& id); -void SplitServerInformationIntoNewEntry( - syncable::WriteTransaction* trans, - syncable::MutableEntry* entry); - // This function is called on an entry when we can update the user-facing data // from the server data. void UpdateLocalDataFromServerData(syncable::WriteTransaction* trans, @@ -88,32 +99,6 @@ VerifyResult VerifyUndelete(syncable::WriteTransaction* trans, const sync_pb::SyncEntity& update, syncable::MutableEntry* target); -// Append |item|, followed by a chain of its predecessors selected by -// |inclusion_filter|, to the |commit_ids| vector and tag them as included by -// storing in the set |inserted_items|. |inclusion_filter| (typically one of -// IS_UNAPPLIED_UPDATE or IS_UNSYNCED) selects which type of predecessors to -// include. Returns true if |item| was added, and false if it was already in -// the list. -// -// Use AddPredecessorsThenItem instead of this method if you want the -// item to be the last, rather than first, item appended. -bool AddItemThenPredecessors( - syncable::BaseTransaction* trans, - syncable::Entry* item, - syncable::IndexedBitField inclusion_filter, - syncable::MetahandleSet* inserted_items, - std::vector<syncable::Id>* commit_ids); - -// Exactly like AddItemThenPredecessors, except items are appended in the -// reverse (and generally more useful) order: a chain of predecessors from -// far to near, and finally the item. -void AddPredecessorsThenItem( - syncable::BaseTransaction* trans, - syncable::Entry* item, - syncable::IndexedBitField inclusion_filter, - syncable::MetahandleSet* inserted_items, - std::vector<syncable::Id>* commit_ids); - void MarkDeletedChildrenSynced( syncable::Directory* dir, std::set<syncable::Id>* deleted_folders); diff --git a/sync/internal_api/base_node.cc b/sync/internal_api/base_node.cc index 4ae318b..b45787f 100644 --- a/sync/internal_api/base_node.cc +++ b/sync/internal_api/base_node.cc @@ -209,20 +209,13 @@ int64 BaseNode::GetSuccessorId() const { } int64 BaseNode::GetFirstChildId() const { - syncable::Directory* dir = GetTransaction()->GetDirectory(); - syncable::BaseTransaction* trans = GetTransaction()->GetWrappedTrans(); - syncable::Id id_string; - // TODO(akalin): Propagate up the error further (see - // http://crbug.com/100907). - CHECK(dir->GetFirstChildId(trans, - GetEntry()->Get(syncable::ID), &id_string)); + syncable::Id id_string = GetEntry()->GetFirstChildId(); if (id_string.IsRoot()) return kInvalidId; return IdToMetahandle(GetTransaction()->GetWrappedTrans(), id_string); } int BaseNode::GetTotalNodeCount() const { - syncable::Directory* dir = GetTransaction()->GetDirectory(); syncable::BaseTransaction* trans = GetTransaction()->GetWrappedTrans(); int count = 1; // Start with one to include the node itself. @@ -238,13 +231,14 @@ int BaseNode::GetTotalNodeCount() const { syncable::Entry entry(trans, syncable::GET_BY_HANDLE, handle); if (!entry.good()) continue; - syncable::Id id = entry.Get(syncable::ID); - syncable::Id child_id; - if (dir->GetFirstChildId(trans, id, &child_id) && !child_id.IsRoot()) - stack.push(IdToMetahandle(trans, child_id)); syncable::Id successor_id = entry.GetSuccessorId(); if (!successor_id.IsRoot()) stack.push(IdToMetahandle(trans, successor_id)); + if (!entry.Get(syncable::IS_DIR)) + continue; + syncable::Id child_id = entry.GetFirstChildId(); + if (!child_id.IsRoot()) + stack.push(IdToMetahandle(trans, child_id)); } return count; } @@ -261,21 +255,23 @@ DictionaryValue* BaseNode::GetSummaryAsValue() const { DictionaryValue* BaseNode::GetDetailsAsValue() const { DictionaryValue* node_info = GetSummaryAsValue(); node_info->SetString( - "modificationTime", - GetTimeDebugString(GetModificationTime())); + "modificationTime", GetTimeDebugString(GetModificationTime())); node_info->SetString("parentId", base::Int64ToString(GetParentId())); // Specifics are already in the Entry value, so no need to duplicate // it here. - node_info->SetString("externalId", - base::Int64ToString(GetExternalId())); - node_info->SetString("predecessorId", - base::Int64ToString(GetPredecessorId())); - node_info->SetString("successorId", - base::Int64ToString(GetSuccessorId())); - node_info->SetString("firstChildId", - base::Int64ToString(GetFirstChildId())); - node_info->Set("entry", - GetEntry()->ToValue(GetTransaction()->GetCryptographer())); + node_info->SetString("externalId", base::Int64ToString(GetExternalId())); + if (GetEntry()->ShouldMaintainPosition() && + !GetEntry()->Get(syncable::IS_DEL)) { + node_info->SetString("successorId", base::Int64ToString(GetSuccessorId())); + node_info->SetString( + "predecessorId", base::Int64ToString(GetPredecessorId())); + } + if (GetEntry()->Get(syncable::IS_DIR)) { + node_info->SetString( + "firstChildId", base::Int64ToString(GetFirstChildId())); + } + node_info->Set( + "entry", GetEntry()->ToValue(GetTransaction()->GetCryptographer())); return node_info; } diff --git a/sync/internal_api/change_reorder_buffer.cc b/sync/internal_api/change_reorder_buffer.cc index 5358fa2..0ddb6b3 100644 --- a/sync/internal_api/change_reorder_buffer.cc +++ b/sync/internal_api/change_reorder_buffer.cc @@ -154,8 +154,9 @@ bool ChangeReorderBuffer::GetAllChangesInTreeOrder( CHECK_EQ(BaseNode::INIT_OK, node.InitByIdLookup(i->first)); // We only care about parents of entry's with position-sensitive models. - if (ShouldMaintainPosition(node.GetEntry()->GetModelType())) { + if (node.GetEntry()->ShouldMaintainPosition()) { parents_of_position_changes.insert(node.GetParentId()); + traversal.ExpandToInclude(trans, node.GetParentId()); } } } @@ -200,12 +201,7 @@ bool ChangeReorderBuffer::GetAllChangesInTreeOrder( // There were ordering changes on the children of this parent, so // enumerate all the children in the sibling order. syncable::Entry parent(trans, syncable::GET_BY_HANDLE, next); - syncable::Id id; - if (!trans->directory()->GetFirstChildId( - trans, parent.Get(syncable::ID), &id)) { - *changes = ImmutableChangeRecordList(); - return false; - } + syncable::Id id = parent.GetFirstChildId(); while (!id.IsRoot()) { syncable::Entry child(trans, syncable::GET_BY_ID, id); CHECK(child.good()); diff --git a/sync/internal_api/public/base/model_type.h b/sync/internal_api/public/base/model_type.h index 92df116..7a95d8c 100644 --- a/sync/internal_api/public/base/model_type.h +++ b/sync/internal_api/public/base/model_type.h @@ -158,10 +158,6 @@ SYNC_EXPORT_PRIVATE ModelType GetModelType( SYNC_EXPORT ModelType GetModelTypeFromSpecifics( const sync_pb::EntitySpecifics& specifics); -// If this returns false, we shouldn't bother maintaining a position -// value (sibling ordering) for this item. -bool ShouldMaintainPosition(ModelType model_type); - // Protocol types are those types that have actual protocol buffer // representations. This distinguishes them from Proxy types, which have no // protocol representation and are never sent to the server. diff --git a/sync/internal_api/public/base/unique_position.cc b/sync/internal_api/public/base/unique_position.cc index 839fc82..a47d42b 100644 --- a/sync/internal_api/public/base/unique_position.cc +++ b/sync/internal_api/public/base/unique_position.cc @@ -117,6 +117,13 @@ void UniquePosition::ToProto(sync_pb::UniquePosition* proto) const { proto->set_value(bytes_); } +void UniquePosition::SerializeToString(std::string* blob) const { + DCHECK(blob); + sync_pb::UniquePosition proto; + ToProto(&proto); + proto.SerializeToString(blob); +} + int64 UniquePosition::ToInt64() const { uint64 y = 0; const std::string& s = bytes_; @@ -140,6 +147,9 @@ bool UniquePosition::IsValid() const { } std::string UniquePosition::ToDebugString() const { + if (bytes_.empty()) + return std::string("INVALID[]"); + std::string debug_string = base::HexEncode(bytes_.data(), bytes_.length()); if (!IsValid()) { debug_string = "INVALID[" + debug_string + "]"; diff --git a/sync/internal_api/public/base/unique_position.h b/sync/internal_api/public/base/unique_position.h index 3fbd5af..f1ff950 100644 --- a/sync/internal_api/public/base/unique_position.h +++ b/sync/internal_api/public/base/unique_position.h @@ -78,6 +78,9 @@ class SYNC_EXPORT_PRIVATE UniquePosition { // Serializes the position's internal state to a protobuf. void ToProto(sync_pb::UniquePosition* proto) const; + // Serializes the protobuf representation of this object as a string. + void SerializeToString(std::string* blob) const; + // Returns a human-readable representation of this item's internal state. std::string ToDebugString() const; diff --git a/sync/internal_api/public/base/unique_position_unittest.cc b/sync/internal_api/public/base/unique_position_unittest.cc index 0f979c8..659ca60 100644 --- a/sync/internal_api/public/base/unique_position_unittest.cc +++ b/sync/internal_api/public/base/unique_position_unittest.cc @@ -69,7 +69,9 @@ const UniquePosition kSmallPositionPlusOne = FromBytes( const std::string kMinSuffix = std::string(UniquePosition::kSuffixLength - 1, '\x00') + '\x01'; const std::string kMaxSuffix(UniquePosition::kSuffixLength, '\xFF'); -const std::string kNormalSuffix(UniquePosition::kSuffixLength, '\xAB'); +const std::string kNormalSuffix( + "\x68\x44\x6C\x6B\x32\x58\x78\x34\x69\x70\x46\x34\x79\x49" + "\x44\x4F\x66\x4C\x58\x41\x31\x34\x68\x59\x56\x43\x6F\x3D"); ::testing::AssertionResult LessThan(const char* m_expr, const char* n_expr, diff --git a/sync/internal_api/sync_manager_impl.cc b/sync/internal_api/sync_manager_impl.cc index 017fdf5..363fa81 100644 --- a/sync/internal_api/sync_manager_impl.cc +++ b/sync/internal_api/sync_manager_impl.cc @@ -56,6 +56,7 @@ namespace syncer { using sessions::SyncSessionContext; using syncable::ImmutableWriteTransactionInfo; using syncable::SPECIFICS; +using syncable::UNIQUE_POSITION; namespace { @@ -225,12 +226,9 @@ bool SyncManagerImpl::VisiblePositionsDiffer( const syncable::EntryKernelMutation& mutation) const { const syncable::EntryKernel& a = mutation.original; const syncable::EntryKernel& b = mutation.mutated; - // If the datatype isn't one where the browser model cares about position, - // don't bother notifying that data model of position-only changes. - if (!ShouldMaintainPosition(GetModelTypeFromSpecifics(b.ref(SPECIFICS)))) { + if (!b.ShouldMaintainPosition()) return false; - } - if (a.ref(syncable::NEXT_ID) != b.ref(syncable::NEXT_ID)) + if (!a.ref(UNIQUE_POSITION).Equals(b.ref(UNIQUE_POSITION))) return true; if (a.ref(syncable::PARENT_ID) != b.ref(syncable::PARENT_ID)) return true; diff --git a/sync/internal_api/sync_manager_impl.h b/sync/internal_api/sync_manager_impl.h index c0373cf..acc0175 100644 --- a/sync/internal_api/sync_manager_impl.h +++ b/sync/internal_api/sync_manager_impl.h @@ -220,11 +220,10 @@ class SYNC_EXPORT_PRIVATE SyncManagerImpl : typedef std::map<std::string, JsMessageHandler> JsMessageHandlerMap; // Determine if the parents or predecessors differ between the old and new - // versions of an entry stored in |a| and |b|. Note that a node's index may - // change without its NEXT_ID changing if the node at NEXT_ID also moved (but - // the relative order is unchanged). To handle such cases, we rely on the - // caller to treat a position update on any sibling as updating the positions - // of all siblings. + // versions of an entry. Note that a node's index may change without its + // UNIQUE_POSITION changing if its sibling nodes were changed. To handle such + // cases, we rely on the caller to treat a position update on any sibling as + // updating the positions of all siblings. bool VisiblePositionsDiffer( const syncable::EntryKernelMutation& mutation) const; diff --git a/sync/internal_api/sync_manager_impl_unittest.cc b/sync/internal_api/sync_manager_impl_unittest.cc index 5e4d0ae..9a6ddee 100644 --- a/sync/internal_api/sync_manager_impl_unittest.cc +++ b/sync/internal_api/sync_manager_impl_unittest.cc @@ -532,6 +532,8 @@ namespace { void CheckNodeValue(const BaseNode& node, const base::DictionaryValue& value, bool is_detailed) { + size_t expected_field_count = 4; + ExpectInt64Value(node.GetId(), value, "id"); { bool is_folder = false; @@ -539,28 +541,22 @@ void CheckNodeValue(const BaseNode& node, const base::DictionaryValue& value, EXPECT_EQ(node.GetIsFolder(), is_folder); } ExpectDictStringValue(node.GetTitle(), value, "title"); - { - ModelType expected_model_type = node.GetModelType(); - std::string type_str; - EXPECT_TRUE(value.GetString("type", &type_str)); - if (expected_model_type >= FIRST_REAL_MODEL_TYPE) { - ModelType model_type = ModelTypeFromString(type_str); - EXPECT_EQ(expected_model_type, model_type); - } else if (expected_model_type == TOP_LEVEL_FOLDER) { - EXPECT_EQ("Top-level folder", type_str); - } else if (expected_model_type == UNSPECIFIED) { - EXPECT_EQ("Unspecified", type_str); - } else { - ADD_FAILURE(); - } + + ModelType expected_model_type = node.GetModelType(); + std::string type_str; + EXPECT_TRUE(value.GetString("type", &type_str)); + if (expected_model_type >= FIRST_REAL_MODEL_TYPE) { + ModelType model_type = ModelTypeFromString(type_str); + EXPECT_EQ(expected_model_type, model_type); + } else if (expected_model_type == TOP_LEVEL_FOLDER) { + EXPECT_EQ("Top-level folder", type_str); + } else if (expected_model_type == UNSPECIFIED) { + EXPECT_EQ("Unspecified", type_str); + } else { + ADD_FAILURE(); } + if (is_detailed) { - ExpectInt64Value(node.GetParentId(), value, "parentId"); - ExpectTimeValue(node.GetModificationTime(), value, "modificationTime"); - ExpectInt64Value(node.GetExternalId(), value, "externalId"); - ExpectInt64Value(node.GetPredecessorId(), value, "predecessorId"); - ExpectInt64Value(node.GetSuccessorId(), value, "successorId"); - ExpectInt64Value(node.GetFirstChildId(), value, "firstChildId"); { scoped_ptr<base::DictionaryValue> expected_entry( node.GetEntry()->ToValue(NULL)); @@ -568,10 +564,27 @@ void CheckNodeValue(const BaseNode& node, const base::DictionaryValue& value, EXPECT_TRUE(value.Get("entry", &entry)); EXPECT_TRUE(base::Value::Equals(entry, expected_entry.get())); } - EXPECT_EQ(11u, value.size()); - } else { - EXPECT_EQ(4u, value.size()); + + ExpectInt64Value(node.GetParentId(), value, "parentId"); + ExpectTimeValue(node.GetModificationTime(), value, "modificationTime"); + ExpectInt64Value(node.GetExternalId(), value, "externalId"); + expected_field_count += 4; + + if (value.HasKey("predecessorId")) { + ExpectInt64Value(node.GetPredecessorId(), value, "predecessorId"); + expected_field_count++; + } + if (value.HasKey("successorId")) { + ExpectInt64Value(node.GetSuccessorId(), value, "successorId"); + expected_field_count++; + } + if (value.HasKey("firstChildId")) { + ExpectInt64Value(node.GetFirstChildId(), value, "firstChildId"); + expected_field_count++; + } } + + EXPECT_EQ(expected_field_count, value.size()); } } // namespace diff --git a/sync/internal_api/test/test_entry_factory.cc b/sync/internal_api/test/test_entry_factory.cc index e53c458..f9d7d49 100644 --- a/sync/internal_api/test/test_entry_factory.cc +++ b/sync/internal_api/test/test_entry_factory.cc @@ -99,13 +99,6 @@ void TestEntryFactory::CreateUnsyncedItem( WriteTransaction trans(FROM_HERE, UNITTEST, directory_); - Id predecessor_id; - if (model_type == BOOKMARKS) { - bool lookup_result = directory_->GetLastChildIdForTest( - &trans, parent_id, &predecessor_id); - DCHECK(lookup_result); - } - MutableEntry entry(&trans, syncable::CREATE, model_type, parent_id, name); DCHECK(entry.good()); entry.Put(syncable::ID, item_id); @@ -119,12 +112,6 @@ void TestEntryFactory::CreateUnsyncedItem( AddDefaultFieldValue(model_type, &default_specifics); entry.Put(syncable::SPECIFICS, default_specifics); - // Bookmarks get inserted at the end of the list. - if (model_type == BOOKMARKS) { - bool put_result = entry.PutPredecessor(predecessor_id); - DCHECK(put_result); - } - if (item_id.ServerKnows()) { entry.Put(syncable::SERVER_SPECIFICS, default_specifics); entry.Put(syncable::SERVER_IS_DIR, false); @@ -177,12 +164,6 @@ int64 TestEntryFactory::CreateSyncedItem( entry.Put(syncable::IS_DEL, false); entry.Put(syncable::PARENT_ID, parent_id); - // TODO(sync): Place bookmarks at the end of the list? - if (!entry.PutPredecessor(TestIdFactory::root())) { - NOTREACHED(); - return syncable::kInvalidMetaHandle; - } - entry.Put(syncable::SERVER_VERSION, GetNextRevision()); entry.Put(syncable::IS_UNAPPLIED_UPDATE, false); entry.Put(syncable::SERVER_NON_UNIQUE_NAME, name); diff --git a/sync/protocol/proto_value_conversions.cc b/sync/protocol/proto_value_conversions.cc index d102b7c..fbf90eb 100644 --- a/sync/protocol/proto_value_conversions.cc +++ b/sync/protocol/proto_value_conversions.cc @@ -11,6 +11,7 @@ #include "base/logging.h" #include "base/string_number_conversions.h" #include "base/values.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/protocol/app_notification_specifics.pb.h" #include "sync/protocol/app_setting_specifics.pb.h" #include "sync/protocol/app_specifics.pb.h" @@ -35,6 +36,7 @@ #include "sync/protocol/synced_notification_specifics.pb.h" #include "sync/protocol/theme_specifics.pb.h" #include "sync/protocol/typed_url_specifics.pb.h" +#include "sync/protocol/unique_position.pb.h" namespace syncer { @@ -542,6 +544,12 @@ base::DictionaryValue* EntitySpecificsToValue( namespace { +StringValue* UniquePositionToStringValue( + const sync_pb::UniquePosition& proto) { + UniquePosition pos = UniquePosition::FromProto(proto); + return new StringValue(pos.ToDebugString()); +} + base::DictionaryValue* SyncEntityToValue(const sync_pb::SyncEntity& proto, bool include_specifics) { base::DictionaryValue* value = new base::DictionaryValue(); @@ -556,6 +564,7 @@ base::DictionaryValue* SyncEntityToValue(const sync_pb::SyncEntity& proto, SET_INT64(sync_timestamp); SET_STR(server_defined_unique_tag); SET_INT64(position_in_parent); + SET(unique_position, UniquePositionToStringValue); SET_STR(insert_after_item_id); SET_BOOL(deleted); SET_STR(originator_cache_guid); diff --git a/sync/sync_core.gypi b/sync/sync_core.gypi index 716f2af..d9eb244 100644 --- a/sync/sync_core.gypi +++ b/sync/sync_core.gypi @@ -137,7 +137,12 @@ 'syncable/nigori_util.h', 'syncable/on_disk_directory_backing_store.cc', 'syncable/on_disk_directory_backing_store.h', + 'syncable/parent_child_index.cc', + 'syncable/parent_child_index.h', + 'syncable/scoped_index_updater.h', 'syncable/scoped_kernel_lock.h', + 'syncable/scoped_parent_child_index_updater.cc', + 'syncable/scoped_parent_child_index_updater.h', 'syncable/syncable-inl.h', 'syncable/syncable_base_transaction.cc', 'syncable/syncable_base_transaction.h', diff --git a/sync/sync_tests.gypi b/sync/sync_tests.gypi index 059c930..30e06db 100644 --- a/sync/sync_tests.gypi +++ b/sync/sync_tests.gypi @@ -243,7 +243,6 @@ 'engine/apply_control_data_updates_unittest.cc', 'engine/apply_updates_and_resolve_conflicts_command_unittest.cc', 'engine/backoff_delay_provider_unittest.cc', - 'engine/build_commit_command_unittest.cc', 'engine/download_updates_command_unittest.cc', 'engine/model_changing_syncer_command_unittest.cc', 'engine/process_commit_response_command_unittest.cc', @@ -267,6 +266,7 @@ 'syncable/directory_backing_store_unittest.cc', 'syncable/model_type_unittest.cc', 'syncable/nigori_util_unittest.cc', + 'syncable/parent_child_index_unittest.cc', 'syncable/syncable_enum_conversions_unittest.cc', 'syncable/syncable_id_unittest.cc', 'syncable/syncable_unittest.cc', diff --git a/sync/syncable/directory.cc b/sync/syncable/directory.cc index a9e0f65..a844e66 100644 --- a/sync/syncable/directory.cc +++ b/sync/syncable/directory.cc @@ -4,17 +4,18 @@ #include "sync/syncable/directory.h" +#include "base/base64.h" #include "base/debug/trace_event.h" -#include "base/perftimer.h" #include "base/stl_util.h" #include "base/string_number_conversions.h" -#include "sync/internal_api/public/base/node_ordinal.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/internal_api/public/util/unrecoverable_error_handler.h" #include "sync/syncable/entry.h" #include "sync/syncable/entry_kernel.h" #include "sync/syncable/in_memory_directory_backing_store.h" #include "sync/syncable/on_disk_directory_backing_store.h" #include "sync/syncable/scoped_index_updater.h" +#include "sync/syncable/scoped_parent_child_index_updater.h" #include "sync/syncable/syncable-inl.h" #include "sync/syncable/syncable_base_transaction.h" #include "sync/syncable/syncable_changes_version.h" @@ -36,7 +37,6 @@ void InitializeIndexEntry(EntryKernel* entry, index->insert(entry); } } - } // static @@ -44,29 +44,6 @@ bool ClientTagIndexer::ShouldInclude(const EntryKernel* a) { return !a->ref(UNIQUE_CLIENT_TAG).empty(); } -bool ParentIdAndHandleIndexer::Comparator::operator() ( - const syncable::EntryKernel* a, - const syncable::EntryKernel* b) const { - int cmp = a->ref(PARENT_ID).compare(b->ref(PARENT_ID)); - if (cmp != 0) - return cmp < 0; - - const NodeOrdinal& a_position = a->ref(SERVER_ORDINAL_IN_PARENT); - const NodeOrdinal& b_position = b->ref(SERVER_ORDINAL_IN_PARENT); - if (!a_position.Equals(b_position)) - return a_position.LessThan(b_position); - - cmp = a->ref(ID).compare(b->ref(ID)); - return cmp < 0; -} - -// static -bool ParentIdAndHandleIndexer::ShouldInclude(const EntryKernel* a) { - // This index excludes deleted items and the root item. The root - // item is excluded so that it doesn't show up as a child of itself. - return !a->ref(IS_DEL) && !a->ref(ID).IsRoot(); -} - // static const base::FilePath::CharType Directory::kSyncDatabaseFilename[] = FILE_PATH_LITERAL("SyncData.sqlite3"); @@ -116,7 +93,7 @@ Directory::Kernel::Kernel( name(name), metahandles_index(new Directory::MetahandlesIndex), ids_index(new Directory::IdsIndex), - parent_id_child_index(new Directory::ParentIdChildIndex), + parent_child_index(new ParentChildIndex), client_tag_index(new Directory::ClientTagIndex), unsynced_metahandles(new MetahandleSet), dirty_metahandles(new MetahandleSet), @@ -135,7 +112,7 @@ Directory::Kernel::~Kernel() { delete unsynced_metahandles; delete dirty_metahandles; delete metahandles_to_purge; - delete parent_id_child_index; + delete parent_child_index; delete client_tag_index; delete ids_index; STLDeleteElements(metahandles_index); @@ -181,8 +158,8 @@ void Directory::InitializeIndices() { MetahandlesIndex::iterator it = kernel_->metahandles_index->begin(); for (; it != kernel_->metahandles_index->end(); ++it) { EntryKernel* entry = *it; - InitializeIndexEntry<ParentIdAndHandleIndexer>(entry, - kernel_->parent_id_child_index); + if (ParentChildIndex::ShouldInclude(entry)) + kernel_->parent_child_index->Insert(entry); InitializeIndexEntry<IdIndexer>(entry, kernel_->ids_index); InitializeIndexEntry<ClientTagIndexer>(entry, kernel_->client_tag_index); const int64 metahandle = entry->ref(META_HANDLE); @@ -367,8 +344,8 @@ bool Directory::InsertEntry(WriteTransaction* trans, trans)) return false; - if (!entry->ref(IS_DEL)) { - if (!SyncAssert(kernel_->parent_id_child_index->insert(entry).second, + if (ParentChildIndex::ShouldInclude(entry)) { + if (!SyncAssert(kernel_->parent_child_index->Insert(entry), FROM_HERE, error, trans)) { @@ -399,8 +376,8 @@ bool Directory::ReindexId(WriteTransaction* trans, { // Update the indices that depend on the ID field. ScopedIndexUpdater<IdIndexer> updater_a(lock, entry, kernel_->ids_index); - ScopedIndexUpdater<ParentIdAndHandleIndexer> updater_b(lock, entry, - kernel_->parent_id_child_index); + ScopedParentChildIndexUpdater updater_b(lock, entry, + kernel_->parent_child_index); entry->put(ID, new_id); } return true; @@ -413,8 +390,8 @@ bool Directory::ReindexParentId(WriteTransaction* trans, { // Update the indices that depend on the PARENT_ID field. - ScopedIndexUpdater<ParentIdAndHandleIndexer> index_updater(lock, entry, - kernel_->parent_id_child_index); + ScopedParentChildIndexUpdater index_updater(lock, entry, + kernel_->parent_child_index); entry->put(PARENT_ID, new_parent_id); } return true; @@ -550,7 +527,7 @@ bool Directory::VacuumAfterSaveChanges(const SaveChangesSnapshot& snapshot) { // Might not be in it num_erased = kernel_->client_tag_index->erase(entry); DCHECK_EQ(entry->ref(UNIQUE_CLIENT_TAG).empty(), !num_erased); - if (!SyncAssert(!kernel_->parent_id_child_index->count(entry), + if (!SyncAssert(!kernel_->parent_child_index->Contains(entry), FROM_HERE, "Deleted entry still present", (&trans))) @@ -589,8 +566,6 @@ bool Directory::PurgeEntriesWithTypeIn(ModelTypeSet types, // Note the dance around incrementing |it|, since we sometimes erase(). if ((IsRealDataType(local_type) && types.Has(local_type)) || (IsRealDataType(server_type) && types.Has(server_type))) { - if (!UnlinkEntryFromOrder(*it, &trans, &lock, DATA_TYPE_PURGE)) - return false; int64 handle = (*it)->ref(META_HANDLE); kernel_->metahandles_to_purge->insert(handle); @@ -606,8 +581,8 @@ bool Directory::PurgeEntriesWithTypeIn(ModelTypeSet types, num_erased = kernel_->unapplied_update_metahandles[server_type].erase(handle); DCHECK_EQ(entry->ref(IS_UNAPPLIED_UPDATE), num_erased > 0); - num_erased = kernel_->parent_id_child_index->erase(entry); - DCHECK_EQ(entry->ref(IS_DEL), !num_erased); + if (kernel_->parent_child_index->Contains(entry)) + kernel_->parent_child_index->Remove(entry); kernel_->metahandles_index->erase(it++); if ((types_to_journal.Has(local_type) || @@ -730,14 +705,6 @@ bool Directory::InitialSyncEndedForType( return entry.good() && entry.Get(syncable::BASE_VERSION) != CHANGES_VERSION; } -template <class T> void Directory::TestAndSet( - T* kernel_data, const T* data_to_set) { - if (*kernel_data != *data_to_set) { - *kernel_data = *data_to_set; - kernel_->info_status = KERNEL_SHARE_INFO_DIRTY; - } -} - string Directory::store_birthday() const { ScopedKernelLock lock(this); return kernel_->persisted_info.store_birthday; @@ -1030,76 +997,6 @@ void Directory::SetInvariantCheckLevel(InvariantCheckLevel check_level) { invariant_check_level_ = check_level; } -bool Directory::UnlinkEntryFromOrder(EntryKernel* entry, - WriteTransaction* trans, - ScopedKernelLock* lock, - UnlinkReason unlink_reason) { - if (!SyncAssert(!trans || this == trans->directory(), - FROM_HERE, - "Transaction not pointing to the right directory", - trans)) - return false; - Id old_previous = entry->ref(PREV_ID); - Id old_next = entry->ref(NEXT_ID); - - entry->put(NEXT_ID, entry->ref(ID)); - entry->put(PREV_ID, entry->ref(ID)); - entry->mark_dirty(kernel_->dirty_metahandles); - - if (!old_previous.IsRoot()) { - if (old_previous == old_next) { - // Note previous == next doesn't imply previous == next == Get(ID). We - // could have prev==next=="c-XX" and Get(ID)=="sX..." if an item was added - // and deleted before receiving the server ID in the commit response. - if (!SyncAssert( - (old_next == entry->ref(ID)) || !old_next.ServerKnows(), - FROM_HERE, - "Encounteered inconsistent entry while deleting", - trans)) { - return false; - } - return true; // Done if we were already self-looped (hence unlinked). - } - EntryKernel* previous_entry = GetEntryById(old_previous, lock); - ModelType type = GetModelTypeFromSpecifics(entry->ref(SPECIFICS)); - // TODO(tim): Multiple asserts here for bug 101039 investigation. - if (type == AUTOFILL) { - if (!SyncAssert(previous_entry != NULL, - FROM_HERE, - "Could not find previous autofill entry", - trans)) { - return false; - } - } else { - if (!SyncAssert(previous_entry != NULL, - FROM_HERE, - "Could not find previous entry", - trans)) { - return false; - } - } - if (unlink_reason == NODE_MANIPULATION) - trans->SaveOriginal(previous_entry); - previous_entry->put(NEXT_ID, old_next); - previous_entry->mark_dirty(kernel_->dirty_metahandles); - } - - if (!old_next.IsRoot()) { - EntryKernel* next_entry = GetEntryById(old_next, lock); - if (!SyncAssert(next_entry != NULL, - FROM_HERE, - "Could not find next entry", - trans)) { - return false; - } - if (unlink_reason == NODE_MANIPULATION) - trans->SaveOriginal(next_entry); - next_entry->put(PREV_ID, old_previous); - next_entry->mark_dirty(kernel_->dirty_metahandles); - } - return true; -} - int64 Directory::NextMetahandle() { ScopedKernelLock lock(this); int64 metahandle = (kernel_->next_metahandle)++; @@ -1121,171 +1018,161 @@ Id Directory::NextId() { bool Directory::HasChildren(BaseTransaction* trans, const Id& id) { ScopedKernelLock lock(this); - return (GetPossibleFirstChild(lock, id) != NULL); + return kernel_->parent_child_index->GetChildren(id) != NULL; } -bool Directory::GetFirstChildId(BaseTransaction* trans, - const Id& parent_id, - Id* first_child_id) { +Id Directory::GetFirstChildId(BaseTransaction* trans, + const EntryKernel* parent) { + DCHECK(parent); + DCHECK(parent->ref(IS_DIR)); + ScopedKernelLock lock(this); - EntryKernel* entry = GetPossibleFirstChild(lock, parent_id); - if (!entry) { - *first_child_id = Id(); - return true; - } + const OrderedChildSet* children = + kernel_->parent_child_index->GetChildren(parent->ref(ID)); - // Walk to the front of the list; the server position ordering - // is commonly identical to the linked-list ordering, but pending - // unsynced or unapplied items may diverge. - while (!entry->ref(PREV_ID).IsRoot()) { - entry = GetEntryById(entry->ref(PREV_ID), &lock); - if (!entry) { - *first_child_id = Id(); - return false; - } - } - *first_child_id = entry->ref(ID); - return true; + // We're expected to return root if there are no children. + if (!children) + return Id(); + + return (*children->begin())->ref(ID); } -bool Directory::GetLastChildIdForTest( - BaseTransaction* trans, const Id& parent_id, Id* last_child_id) { +syncable::Id Directory::GetPredecessorId(EntryKernel* e) { ScopedKernelLock lock(this); - EntryKernel* entry = GetPossibleFirstChild(lock, parent_id); - if (!entry) { - *last_child_id = Id(); - return true; - } - // Walk to the back of the list; the server position ordering - // is commonly identical to the linked-list ordering, but pending - // unsynced or unapplied items may diverge. - while (!entry->ref(NEXT_ID).IsRoot()) { - entry = GetEntryById(entry->ref(NEXT_ID), &lock); - if (!entry) { - *last_child_id = Id(); - return false; - } + DCHECK(ParentChildIndex::ShouldInclude(e)); + const OrderedChildSet* children = + kernel_->parent_child_index->GetChildren(e->ref(PARENT_ID)); + DCHECK(children && !children->empty()); + OrderedChildSet::const_iterator i = children->find(e); + DCHECK(i != children->end()); + + if (i == children->begin()) { + return Id(); + } else { + i--; + return (*i)->ref(ID); } - - *last_child_id = entry->ref(ID); - return true; } -Id Directory::ComputePrevIdFromServerPosition( - const EntryKernel* entry, - const syncable::Id& parent_id) { +syncable::Id Directory::GetSuccessorId(EntryKernel* e) { ScopedKernelLock lock(this); - // Find the natural insertion point in the parent_id_child_index, and - // work back from there, filtering out ineligible candidates. - ParentIdChildIndex::iterator sibling = LocateInParentChildIndex( - lock, - parent_id, - NodeOrdinalToInt64(entry->ref(SERVER_ORDINAL_IN_PARENT)), - entry->ref(ID)); - ParentIdChildIndex::iterator first_sibling = - GetParentChildIndexLowerBound(lock, parent_id); - - while (sibling != first_sibling) { - --sibling; - EntryKernel* candidate = *sibling; - - // The item itself should never be in the range under consideration. - DCHECK_NE(candidate->ref(META_HANDLE), entry->ref(META_HANDLE)); - - // Ignore unapplied updates -- they might not even be server-siblings. - if (candidate->ref(IS_UNAPPLIED_UPDATE)) - continue; + DCHECK(ParentChildIndex::ShouldInclude(e)); + const OrderedChildSet* children = + kernel_->parent_child_index->GetChildren(e->ref(PARENT_ID)); + DCHECK(children && !children->empty()); + OrderedChildSet::const_iterator i = children->find(e); + DCHECK(i != children->end()); + + i++; + if (i == children->end()) { + return Id(); + } else { + return (*i)->ref(ID); + } +} - // We can't trust the SERVER_ fields of unsynced items, but they are - // potentially legitimate local predecessors. In the case where - // |update_item| and an unsynced item wind up in the same insertion - // position, we need to choose how to order them. The following check puts - // the unapplied update first; removing it would put the unsynced item(s) - // first. - if (candidate->ref(IS_UNSYNCED)) - continue; +// TODO(rlarocque): Remove all support for placing ShouldMaintainPosition() +// items as siblings of items that do not maintain postions. It is required +// only for tests. See crbug.com/178282. +void Directory::PutPredecessor(EntryKernel* e, EntryKernel* predecessor) { + DCHECK(!e->ref(IS_DEL)); + if (!e->ShouldMaintainPosition()) { + DCHECK(!e->ref(UNIQUE_POSITION).IsValid()); + return; + } + std::string suffix = e->ref(UNIQUE_BOOKMARK_TAG); + DCHECK(!suffix.empty()); - // Skip over self-looped items, which are not valid predecessors. This - // shouldn't happen in practice, but is worth defending against. - if (candidate->ref(PREV_ID) == candidate->ref(NEXT_ID) && - !candidate->ref(PREV_ID).IsRoot()) { - NOTREACHED(); - continue; + // Remove our item from the ParentChildIndex and remember to re-add it later. + ScopedKernelLock lock(this); + ScopedParentChildIndexUpdater updater(lock, e, kernel_->parent_child_index); + + // Note: The ScopedParentChildIndexUpdater will update this set for us as we + // leave this function. + const OrderedChildSet* siblings = + kernel_->parent_child_index->GetChildren(e->ref(PARENT_ID)); + + if (!siblings) { + // This parent currently has no other children. + DCHECK(predecessor->ref(ID).IsRoot()); + UniquePosition pos = UniquePosition::InitialPosition(suffix); + e->put(UNIQUE_POSITION, pos); + return; + } + + if (predecessor->ref(ID).IsRoot()) { + // We have at least one sibling, and we're inserting to the left of them. + UniquePosition successor_pos = (*siblings->begin())->ref(UNIQUE_POSITION); + + UniquePosition pos; + if (!successor_pos.IsValid()) { + // If all our successors are of non-positionable types, just create an + // initial position. We arbitrarily choose to sort invalid positions to + // the right of the valid positions. + // + // We really shouldn't need to support this. See TODO above. + pos = UniquePosition::InitialPosition(suffix); + } else { + DCHECK(!siblings->empty()); + pos = UniquePosition::Before(successor_pos, suffix); } - return candidate->ref(ID); + + e->put(UNIQUE_POSITION, pos); + return; } - // This item will be the first in the sibling order. - return Id(); -} -Directory::ParentIdChildIndex::iterator Directory::LocateInParentChildIndex( - const ScopedKernelLock& lock, - const Id& parent_id, - int64 position_in_parent, - const Id& item_id_for_tiebreaking) { - kernel_->needle.put(PARENT_ID, parent_id); - kernel_->needle.put(SERVER_ORDINAL_IN_PARENT, - Int64ToNodeOrdinal(position_in_parent)); - kernel_->needle.put(ID, item_id_for_tiebreaking); - return kernel_->parent_id_child_index->lower_bound(&kernel_->needle); -} + // We can't support placing an item after an invalid position. Fortunately, + // the tests don't exercise this particular case. We should not support + // siblings with invalid positions at all. See TODO above. + DCHECK(predecessor->ref(UNIQUE_POSITION).IsValid()); + + OrderedChildSet::const_iterator neighbour = siblings->find(predecessor); + DCHECK(neighbour != siblings->end()); + + ++neighbour; + if (neighbour == siblings->end()) { + // Inserting at the end of the list. + UniquePosition pos = UniquePosition::After( + predecessor->ref(UNIQUE_POSITION), + suffix); + e->put(UNIQUE_POSITION, pos); + return; + } -Directory::ParentIdChildIndex::iterator -Directory::GetParentChildIndexLowerBound(const ScopedKernelLock& lock, - const Id& parent_id) { - // Peg the parent ID, and use the least values for the remaining - // index variables. - return LocateInParentChildIndex(lock, parent_id, - std::numeric_limits<int64>::min(), - Id::GetLeastIdForLexicographicComparison()); -} + EntryKernel* successor = *neighbour; + + // Another mixed valid and invalid position case. This one could be supported + // in theory, but we're trying to deprecate support for siblings with and + // without valid positions. See TODO above. + DCHECK(successor->ref(UNIQUE_POSITION).IsValid()); -Directory::ParentIdChildIndex::iterator -Directory::GetParentChildIndexUpperBound(const ScopedKernelLock& lock, - const Id& parent_id) { - // The upper bound of |parent_id|'s range is the lower - // bound of |++parent_id|'s range. - return GetParentChildIndexLowerBound(lock, - parent_id.GetLexicographicSuccessor()); + // Finally, the normal case: inserting between two elements. + UniquePosition pos = UniquePosition::Between( + predecessor->ref(UNIQUE_POSITION), + successor->ref(UNIQUE_POSITION), + suffix); + e->put(UNIQUE_POSITION, pos); + return; } +// TODO(rlarocque): Avoid this indirection. Just return the set. void Directory::AppendChildHandles(const ScopedKernelLock& lock, const Id& parent_id, Directory::ChildHandles* result) { - typedef ParentIdChildIndex::iterator iterator; - CHECK(result); - for (iterator i = GetParentChildIndexLowerBound(lock, parent_id), - end = GetParentChildIndexUpperBound(lock, parent_id); - i != end; ++i) { + const OrderedChildSet* children = + kernel_->parent_child_index->GetChildren(parent_id); + if (!children) + return; + + for (OrderedChildSet::const_iterator i = children->begin(); + i != children->end(); ++i) { DCHECK_EQ(parent_id, (*i)->ref(PARENT_ID)); result->push_back((*i)->ref(META_HANDLE)); } } -EntryKernel* Directory::GetPossibleFirstChild( - const ScopedKernelLock& lock, const Id& parent_id) { - // We can use the server positional ordering as a hint because it's generally - // in sync with the local (linked-list) positional ordering, and we have an - // index on it. - ParentIdChildIndex::iterator candidate = - GetParentChildIndexLowerBound(lock, parent_id); - ParentIdChildIndex::iterator end_range = - GetParentChildIndexUpperBound(lock, parent_id); - for (; candidate != end_range; ++candidate) { - EntryKernel* entry = *candidate; - // Filter out self-looped items, which are temporarily not in the child - // ordering. - if (entry->ref(PREV_ID).IsRoot() || - entry->ref(PREV_ID) != entry->ref(NEXT_ID)) { - return entry; - } - } - // There were no children in the linked list. - return NULL; -} - ScopedKernelLock::ScopedKernelLock(const Directory* dir) : scoped_lock_(dir->kernel_->mutex), dir_(const_cast<Directory*>(dir)) { } diff --git a/sync/syncable/directory.h b/sync/syncable/directory.h index 51ceaf8..61c5522 100644 --- a/sync/syncable/directory.h +++ b/sync/syncable/directory.h @@ -17,6 +17,7 @@ #include "sync/syncable/dir_open_result.h" #include "sync/syncable/entry_kernel.h" #include "sync/syncable/metahandle_set.h" +#include "sync/syncable/parent_child_index.h" #include "sync/syncable/scoped_kernel_lock.h" #include "sync/syncable/syncable_delete_journal.h" @@ -86,21 +87,6 @@ struct ClientTagIndexer { static bool ShouldInclude(const EntryKernel* a); }; -// This index contains EntryKernels ordered by parent ID and metahandle. -// It allows efficient lookup of the children of a given parent. -struct ParentIdAndHandleIndexer { - // This index is of the parent ID and metahandle. We use a custom - // comparator. - class Comparator { - public: - bool operator() (const syncable::EntryKernel* a, - const syncable::EntryKernel* b) const; - }; - - // This index does not include deleted items. - static bool ShouldInclude(const EntryKernel* a); -}; - // Given an Indexer providing the semantics of an index, defines the // set type used to actually contain the index. template <typename Indexer> @@ -108,13 +94,6 @@ struct Index { typedef std::set<EntryKernel*, typename Indexer::Comparator> Set; }; -// Reason for unlinking. -enum UnlinkReason { - NODE_MANIPULATION, // To be used by any operation manipulating the linked - // list. - DATA_TYPE_PURGE // To be used when purging a dataype. -}; - enum InvariantCheckLevel { OFF = 0, // No checking. VERIFY_CHANGES = 1, // Checks only mutated entries. Does not check hierarchy. @@ -126,9 +105,7 @@ class SYNC_EXPORT Directory { friend class Entry; friend class MutableEntry; friend class ReadTransaction; - friend class ReadTransactionWithoutDB; friend class ScopedKernelLock; - friend class ScopedKernelUnlock; friend class WriteTransaction; friend class SyncableDirectoryTest; friend class syncer::TestUserShare; @@ -233,9 +210,8 @@ class SYNC_EXPORT Directory { void Close(); int64 NextMetahandle(); - // Always returns a negative id. Positive client ids are generated - // by the server only. - Id NextId(); + // Returns a negative integer unique to this client. + syncable::Id NextId(); bool good() const { return NULL != kernel_; } @@ -320,13 +296,6 @@ class SYNC_EXPORT Directory { const Id& new_parent_id); void ClearDirtyMetahandles(); - // These don't do semantic checking. - // The semantic checking is implemented higher up. - bool UnlinkEntryFromOrder(EntryKernel* entry, - WriteTransaction* trans, - ScopedKernelLock* lock, - UnlinkReason unlink_reason); - DirOpenResult OpenImpl( const std::string& name, DirectoryChangeDelegate* delegate, @@ -337,8 +306,6 @@ class SYNC_EXPORT Directory { // before calling. EntryKernel* GetEntryById(const Id& id, ScopedKernelLock* const lock); - template <class T> void TestAndSet(T* kernel_data, const T* data_to_set); - public: typedef std::vector<int64> ChildHandles; @@ -361,23 +328,27 @@ class SYNC_EXPORT Directory { // and fill in |*first_child_id| with its id. Fills in a root Id if // parent has no children. Returns true if the first child was // successfully found, or false if an error was encountered. - bool GetFirstChildId(BaseTransaction* trans, const Id& parent_id, - Id* first_child_id) WARN_UNUSED_RESULT; + Id GetFirstChildId(BaseTransaction* trans, const EntryKernel* parent); - // Find the last child in the positional ordering under a parent, - // and fill in |*first_child_id| with its id. Fills in a root Id if - // parent has no children. Returns true if the first child was - // successfully found, or false if an error was encountered. - bool GetLastChildIdForTest(BaseTransaction* trans, const Id& parent_id, - Id* last_child_id) WARN_UNUSED_RESULT; + // These functions allow one to fetch the next or previous item under + // the same folder. Returns the "root" ID if there is no predecessor + // or successor. + // + // TODO(rlarocque): These functions are used mainly for tree traversal. We + // should replace these with an iterator API. See crbug.com/178275. + syncable::Id GetPredecessorId(EntryKernel*); + syncable::Id GetSuccessorId(EntryKernel*); - // Compute a local predecessor position for |update_item|. The position - // is determined by the SERVER_POSITION_IN_PARENT value of |update_item|, - // as well as the SERVER_POSITION_IN_PARENT values of any up-to-date - // children of |parent_id|. - Id ComputePrevIdFromServerPosition( - const EntryKernel* update_item, - const syncable::Id& parent_id); + // Places |e| as a successor to |predecessor|. If |predecessor| is NULL, + // |e| will be placed as the left-most item in its folder. + // + // Both |e| and |predecessor| must be valid entries under the same parent. + // + // TODO(rlarocque): This function includes limited support for placing items + // with valid positions (ie. Bookmarks) as siblings of items that have no set + // ordering (ie. Autofill items). This support is required only for tests, + // and should be removed. See crbug.com/178282. + void PutPredecessor(EntryKernel* e, EntryKernel* predecessor); // SaveChanges works by taking a consistent snapshot of the current Directory // state and indices (by deep copy) under a ReadTransaction, passing this @@ -486,12 +457,9 @@ class SYNC_EXPORT Directory { Directory& operator = (const Directory&); public: + // These contain all items, including IS_DEL items. typedef Index<MetahandleIndexer>::Set MetahandlesIndex; typedef Index<IdIndexer>::Set IdsIndex; - // All entries in memory must be in both the MetahandlesIndex and - // the IdsIndex, but only non-deleted entries will be the - // ParentIdChildIndex. - typedef Index<ParentIdAndHandleIndexer>::Set ParentIdChildIndex; // Contains both deleted and existing entries with tags. // We can't store only existing tags because the client would create @@ -538,7 +506,11 @@ class SYNC_EXPORT Directory { MetahandlesIndex* metahandles_index; // Entries indexed by id IdsIndex* ids_index; - ParentIdChildIndex* parent_id_child_index; + + // Contains non-deleted items, indexed according to parent and position + // within parent. Protected by the ScopedKernelLock. + ParentChildIndex* parent_child_index; + ClientTagIndex* client_tag_index; // So we don't have to create an EntryKernel every time we want to // look something up in an index. Needle in haystack metaphor. @@ -583,36 +555,11 @@ class SYNC_EXPORT Directory { const WeakHandle<TransactionObserver> transaction_observer; }; - // Helper method used to do searches on |parent_id_child_index|. - ParentIdChildIndex::iterator LocateInParentChildIndex( - const ScopedKernelLock& lock, - const Id& parent_id, - int64 position_in_parent, - const Id& item_id_for_tiebreaking); - - // Return an iterator to the beginning of the range of the children of - // |parent_id| in the kernel's parent_id_child_index. - ParentIdChildIndex::iterator GetParentChildIndexLowerBound( - const ScopedKernelLock& lock, - const Id& parent_id); - - // Return an iterator to just past the end of the range of the - // children of |parent_id| in the kernel's parent_id_child_index. - ParentIdChildIndex::iterator GetParentChildIndexUpperBound( - const ScopedKernelLock& lock, - const Id& parent_id); - // Append the handles of the children of |parent_id| to |result|. void AppendChildHandles( const ScopedKernelLock& lock, const Id& parent_id, Directory::ChildHandles* result); - // Return a pointer to what is probably (but not certainly) the - // first child of |parent_id|, or NULL if |parent_id| definitely has - // no children. - EntryKernel* GetPossibleFirstChild( - const ScopedKernelLock& lock, const Id& parent_id); - Kernel* kernel_; scoped_ptr<DirectoryBackingStore> store_; diff --git a/sync/syncable/directory_backing_store.cc b/sync/syncable/directory_backing_store.cc index 0683957..f0b87be 100644 --- a/sync/syncable/directory_backing_store.cc +++ b/sync/syncable/directory_backing_store.cc @@ -10,13 +10,8 @@ #include "base/base64.h" #include "base/debug/trace_event.h" -#include "base/file_util.h" -#include "base/hash_tables.h" #include "base/logging.h" -#include "base/metrics/histogram.h" #include "base/rand_util.h" -#include "base/stl_util.h" -#include "base/string_number_conversions.h" #include "base/stringprintf.h" #include "base/time.h" #include "sql/connection.h" @@ -27,6 +22,7 @@ #include "sync/protocol/sync.pb.h" #include "sync/syncable/syncable-inl.h" #include "sync/syncable/syncable_columns.h" +#include "sync/syncable/syncable_util.h" #include "sync/util/time.h" using std::string; @@ -39,7 +35,7 @@ namespace syncable { static const string::size_type kUpdateStatementBufferSize = 2048; // Increment this version whenever updating DB tables. -const int32 kCurrentDBVersion = 85; +const int32 kCurrentDBVersion = 86; // Iterate over the fields of |entry| and bind each to |statement| for // updating. Returns the number of args bound. @@ -64,13 +60,14 @@ void BindFields(const EntryKernel& entry, for ( ; i < STRING_FIELDS_END; ++i) { statement->BindString(index++, entry.ref(static_cast<StringField>(i))); } - std::string temp; for ( ; i < PROTO_FIELDS_END; ++i) { + std::string temp; entry.ref(static_cast<ProtoField>(i)).SerializeToString(&temp); statement->BindBlob(index++, temp.data(), temp.length()); } - for( ; i < ORDINAL_FIELDS_END; ++i) { - temp = entry.ref(static_cast<OrdinalField>(i)).ToInternalValue(); + for ( ; i < UNIQUE_POSITION_FIELDS_END; ++i) { + std::string temp; + entry.ref(static_cast<UniquePositionField>(i)).SerializeToString(&temp); statement->BindBlob(index++, temp.data(), temp.length()); } } @@ -104,19 +101,18 @@ scoped_ptr<EntryKernel> UnpackEntry(sql::Statement* statement) { kernel->mutable_ref(static_cast<ProtoField>(i)).ParseFromArray( statement->ColumnBlob(i), statement->ColumnByteLength(i)); } - for( ; i < ORDINAL_FIELDS_END; ++i) { + for ( ; i < UNIQUE_POSITION_FIELDS_END; ++i) { std::string temp; statement->ColumnBlobAsString(i, &temp); - NodeOrdinal unpacked_ord(temp); - // Its safe to assume that an invalid ordinal is a sign that - // some external corruption has occurred. Return NULL to force - // a re-download of the sync data. - if(!unpacked_ord.IsValid()) { - DVLOG(1) << "Unpacked invalid ordinal. Signaling that the DB is corrupt"; + sync_pb::UniquePosition proto; + if (!proto.ParseFromString(temp)) { + DVLOG(1) << "Unpacked invalid position. Assuming the DB is corrupt"; return scoped_ptr<EntryKernel>(NULL); } - kernel->mutable_ref(static_cast<OrdinalField>(i)) = unpacked_ord; + + kernel->mutable_ref(static_cast<UniquePositionField>(i)) = + UniquePosition::FromProto(proto); } return kernel.Pass(); } @@ -400,6 +396,13 @@ bool DirectoryBackingStore::InitializeTables() { version_on_disk = 85; } + // Version 86 migration converts bookmarks to the unique positioning system. + // It also introduces a new field to store a unique ID for each bookmark. + if (version_on_disk == 85) { + if (MigrateVersion85To86()) + version_on_disk = 86; + } + // If one of the migrations requested it, drop columns that aren't current. // It's only safe to do this after migrating all the way to the current // version. @@ -961,7 +964,8 @@ bool DirectoryBackingStore::MigrateVersion76To77() { #if defined(OS_WIN) // On Windows, we used to store timestamps in FILETIME format (100s of // ns since Jan 1, 1601). Magic numbers taken from -// http://stackoverflow.com/questions/5398557/java-library-for-dealing-with-win32-filetime +// http://stackoverflow.com/questions/5398557/ +// java-library-for-dealing-with-win32-filetime // . #define TO_UNIX_TIME_MS(x) #x " = " #x " / 10000 - 11644473600000" #else @@ -1085,7 +1089,7 @@ bool DirectoryBackingStore::MigrateVersion83To84() { } bool DirectoryBackingStore::MigrateVersion84To85() { - // Version 84 removes the initial_sync_ended flag. + // Version 85 removes the initial_sync_ended flag. if (!db_->Execute("ALTER TABLE models RENAME TO temp_models")) return false; if (!CreateModelsTable()) @@ -1101,6 +1105,131 @@ bool DirectoryBackingStore::MigrateVersion84To85() { return true; } +bool DirectoryBackingStore::MigrateVersion85To86() { + // Version 86 removes both server ordinals and local NEXT_ID, PREV_ID and + // SERVER_{POSITION,ORDINAL}_IN_PARENT and replaces them with UNIQUE_POSITION + // and SERVER_UNIQUE_POSITION. + if (!db_->Execute("ALTER TABLE metas ADD COLUMN " + "server_unique_position BLOB")) { + return false; + } + if (!db_->Execute("ALTER TABLE metas ADD COLUMN " + "unique_position BLOB")) { + return false; + } + if (!db_->Execute("ALTER TABLE metas ADD COLUMN " + "unique_bookmark_tag VARCHAR")) { + return false; + } + + // Fetch the cache_guid from the DB, because we don't otherwise have access to + // it from here. + sql::Statement get_cache_guid(db_->GetUniqueStatement( + "SELECT cache_guid FROM share_info")); + if (!get_cache_guid.Step()) { + return false; + } + std::string cache_guid = get_cache_guid.ColumnString(0); + DCHECK(!get_cache_guid.Step()); + DCHECK(get_cache_guid.Succeeded()); + + sql::Statement get(db_->GetUniqueStatement( + "SELECT " + " metahandle, " + " id, " + " specifics, " + " is_dir, " + " unique_server_tag, " + " server_ordinal_in_parent " + "FROM metas")); + + // Note that we set both the local and server position based on the server + // position. We wll lose any unsynced local position changes. Unfortunately, + // there's nothing we can do to avoid that. The NEXT_ID / PREV_ID values + // can't be translated into a UNIQUE_POSTION in a reliable way. + sql::Statement put(db_->GetCachedStatement( + SQL_FROM_HERE, + "UPDATE metas SET" + " server_unique_position = ?," + " unique_position = ?," + " unique_bookmark_tag = ?" + "WHERE metahandle = ?")); + + while (get.Step()) { + int64 metahandle = get.ColumnInt64(0); + + std::string id_string; + get.ColumnBlobAsString(1, &id_string); + + sync_pb::EntitySpecifics specifics; + specifics.ParseFromArray( + get.ColumnBlob(2), get.ColumnByteLength(2)); + + bool is_dir = get.ColumnBool(3); + + std::string server_unique_tag = get.ColumnString(4); + + std::string ordinal_string; + get.ColumnBlobAsString(5, &ordinal_string); + NodeOrdinal ordinal(ordinal_string); + + + std::string unique_bookmark_tag; + + // We only maintain positions for bookmarks that are not server-defined + // top-level folders. + UniquePosition position; + if (GetModelTypeFromSpecifics(specifics) == BOOKMARKS + && !(is_dir && !server_unique_tag.empty())) { + if (id_string.at(0) == 'c') { + // We found an uncommitted item. This is rare, but fortunate. This + // means we can set the bookmark tag according to the originator client + // item ID and originator cache guid, because (unlike the other case) we + // know that this client is the originator. + unique_bookmark_tag = syncable::GenerateSyncableBookmarkHash( + cache_guid, + id_string.substr(1)); + } else { + // If we've already committed the item, then we don't know who the + // originator was. We do not have access to the originator client item + // ID and originator cache guid at this point. + // + // We will base our hash entirely on the server ID instead. This is + // incorrect, but at least all clients that undergo this migration step + // will be incorrect in the same way. + // + // To get everyone back into a synced state, we will update the bookmark + // tag according to the originator_cache_guid and originator_item_id + // when we see updates for this item. That should ensure that commonly + // modified items will end up with the proper tag values eventually. + unique_bookmark_tag = syncable::GenerateSyncableBookmarkHash( + std::string(), // cache_guid left intentionally blank. + id_string.substr(1)); + } + + int64 int_position = NodeOrdinalToInt64(ordinal); + position = UniquePosition::FromInt64(int_position, unique_bookmark_tag); + } else { + // Leave bookmark_tag and position at their default (invalid) values. + } + + std::string position_blob; + position.SerializeToString(&position_blob); + put.BindBlob(0, position_blob.data(), position_blob.length()); + put.BindBlob(1, position_blob.data(), position_blob.length()); + put.BindBlob(2, unique_bookmark_tag.data(), unique_bookmark_tag.length()); + put.BindInt64(3, metahandle); + + if (!put.Run()) + return false; + put.Reset(true); + } + + SetVersion(86); + needs_column_refresh_ = true; + return true; +} + bool DirectoryBackingStore::CreateTables() { DVLOG(1) << "First run, creating tables"; // Create two little tables share_version and share_info @@ -1165,13 +1294,10 @@ bool DirectoryBackingStore::CreateTables() { const int64 now = TimeToProtoTime(base::Time::Now()); sql::Statement s(db_->GetUniqueStatement( "INSERT INTO metas " - "( id, metahandle, is_dir, ctime, mtime, server_ordinal_in_parent) " - "VALUES ( \"r\", 1, 1, ?, ?, ?)")); + "( id, metahandle, is_dir, ctime, mtime ) " + "VALUES ( \"r\", 1, 1, ?, ? )")); s.BindInt64(0, now); s.BindInt64(1, now); - const std::string ord = - NodeOrdinal::CreateInitialOrdinal().ToInternalValue(); - s.BindBlob(2, ord.data(), ord.length()); if (!s.Run()) return false; @@ -1273,8 +1399,8 @@ bool DirectoryBackingStore::CreateShareInfoTableVersion71( } // This function checks to see if the given list of Metahandles has any nodes -// whose PREV_ID, PARENT_ID or NEXT_ID values refer to ID values that do not -// actually exist. Returns true on success. +// whose PARENT_ID values refer to ID values that do not actually exist. +// Returns true on success. bool DirectoryBackingStore::VerifyReferenceIntegrity( const syncable::MetahandlesIndex &index) { TRACE_EVENT0("sync", "SyncDatabaseIntegrityCheck"); @@ -1295,10 +1421,10 @@ bool DirectoryBackingStore::VerifyReferenceIntegrity( for (MetahandlesIndex::const_iterator it = index.begin(); it != index.end(); ++it) { EntryKernel* entry = *it; - bool prev_exists = (ids_set.find(entry->ref(PREV_ID).value()) != end); bool parent_exists = (ids_set.find(entry->ref(PARENT_ID).value()) != end); - bool next_exists = (ids_set.find(entry->ref(NEXT_ID).value()) != end); - is_ok = is_ok && prev_exists && parent_exists && next_exists; + if (!parent_exists) { + return false; + } } return is_ok; } diff --git a/sync/syncable/directory_backing_store.h b/sync/syncable/directory_backing_store.h index 3ee8844..1b0b721 100644 --- a/sync/syncable/directory_backing_store.h +++ b/sync/syncable/directory_backing_store.h @@ -172,6 +172,7 @@ class SYNC_EXPORT_PRIVATE DirectoryBackingStore : public base::NonThreadSafe { bool MigrateVersion82To83(); bool MigrateVersion83To84(); bool MigrateVersion84To85(); + bool MigrateVersion85To86(); scoped_ptr<sql::Connection> db_; sql::Statement save_meta_statment_; diff --git a/sync/syncable/directory_backing_store_unittest.cc b/sync/syncable/directory_backing_store_unittest.cc index a9da2ca0..6b5f5af 100644 --- a/sync/syncable/directory_backing_store_unittest.cc +++ b/sync/syncable/directory_backing_store_unittest.cc @@ -72,15 +72,16 @@ class MigrationTest : public testing::TestWithParam<int> { void SetUpVersion83Database(sql::Connection* connection); void SetUpVersion84Database(sql::Connection* connection); void SetUpVersion85Database(sql::Connection* connection); + void SetUpVersion86Database(sql::Connection* connection); void SetUpCurrentDatabaseAndCheckVersion(sql::Connection* connection) { - SetUpVersion85Database(connection); // Prepopulates data. + SetUpVersion86Database(connection); // Prepopulates data. scoped_ptr<TestDirectoryBackingStore> dbs( new TestDirectoryBackingStore(GetUsername(), connection)); + ASSERT_EQ(kCurrentDBVersion, dbs->GetVersion()); ASSERT_TRUE(LoadAndIgnoreReturnedData(dbs.get())); ASSERT_FALSE(dbs->needs_column_refresh_); - ASSERT_EQ(kCurrentDBVersion, dbs->GetVersion()); } private: @@ -2426,6 +2427,96 @@ void MigrationTest::SetUpVersion85Database(sql::Connection* connection) { ASSERT_TRUE(connection->CommitTransaction()); } +void MigrationTest::SetUpVersion86Database(sql::Connection* connection) { + ASSERT_TRUE(connection->is_open()); + ASSERT_TRUE(connection->BeginTransaction()); + ASSERT_TRUE(connection->Execute( + "CREATE TABLE share_version (id VARCHAR(128) primary key, data INT);" + "INSERT INTO 'share_version' VALUES('nick@chromium.org',86);" + "CREATE TABLE models (model_id BLOB primary key, progress_marker BLOB," + " transaction_version BIGINT default 0);" + "INSERT INTO 'models' VALUES(X'C2881000',X'0888810218B605',1);" + "CREATE TABLE 'metas'(metahandle bigint primary key ON CONFLICT FAIL,b" + "ase_version bigint default -1,server_version bigint default 0,local_e" + "xternal_id bigint default 0,transaction_version bigint default 0,mtim" + "e bigint default 0,server_mtime bigint default 0,ctime bigint default" + " 0,server_ctime bigint default 0,id varchar(255) default 'r',parent_i" + "d varchar(255) default 'r',server_parent_id varchar(255) default 'r'," + "is_unsynced bit default 0,is_unapplied_update bit default 0,is_del bi" + "t default 0,is_dir bit default 0,server_is_dir bit default 0,server_i" + "s_del bit default 0,non_unique_name varchar,server_non_unique_name va" + "rchar(255),unique_server_tag varchar,unique_client_tag varchar,specif" + "ics blob,server_specifics blob,base_server_specifics blob,server_uniq" + "ue_position blob,unique_position blob,unique_bookmark_tag blob);" + "INSERT INTO 'metas' VALUES(1,-1,0,0,0," + META_PROTO_TIMES_VALS(1) + ",'r','r','r',0,0,0,1,0,0,NULL,NULL,NULL,NULL," + "X'',X'',NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(6,694,694,6,0," + META_PROTO_TIMES_VALS(6) ",'s_ID_6','s_ID_9','s_ID_9',0,0,0,1,1,0,'T" + "he Internet','The Internet',NULL,NULL,X'C2881000',X'C2881000',NULL,X'" + "',X'',X'');" + "INSERT INTO 'metas' VALUES(7,663,663,0,0," + META_PROTO_TIMES_VALS(7) ",'s_ID_7','r','r',0,0,0,1,1,0,'Google Chro" + "me','Google Chrome','google_chrome',NULL,NULL,NULL,NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(8,664,664,0,0," + META_PROTO_TIMES_VALS(8) ",'s_ID_8','s_ID_7','s_ID_7',0,0,0,1,1,0,'B" + "ookmarks','Bookmarks','google_chrome_bookmarks',NULL,X'C2881000',X'C2" + "881000',NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(9,665,665,1,0," + META_PROTO_TIMES_VALS(9) ",'s_ID_9','s_ID_8','s_ID_8',0,0,0,1,1,0,'B" + "ookmark Bar','Bookmark Bar','bookmark_bar',NULL,X'C2881000',X'C288100" + "0',NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(10,666,666,2,0," + META_PROTO_TIMES_VALS(10) ",'s_ID_10','s_ID_8','s_ID_8',0,0,0,1,1,0," + "'Other Bookmarks','Other Bookmarks','other_bookmarks',NULL,X'C2881000" + "',X'C2881000',NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(11,683,683,8,0," + META_PROTO_TIMES_VALS(11) ",'s_ID_11','s_ID_6','s_ID_6',0,0,0,0,0,0," + "'Home (The Chromium Projects)','Home (The Chromium Projects)',NULL,NU" + "LL,X'C28810220A18687474703A2F2F6465762E6368726F6D69756D2E6F72672F1206" + "414741545741',X'C28810290A1D687474703A2F2F6465762E6368726F6D69756D2E6" + "F72672F6F7468657212084146414756415346',NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(12,685,685,9,0," + META_PROTO_TIMES_VALS(12) ",'s_ID_12','s_ID_6','s_ID_6',0,0,0,1,1,0," + "'Extra Bookmarks','Extra Bookmarks',NULL,NULL,X'C2881000',X'C2881000'" + ",NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(13,687,687,10,0," + META_PROTO_TIMES_VALS(13) ",'s_ID_13','s_ID_6','s_ID_6',0,0,0,0,0,0" + ",'ICANN | Internet Corporation for Assigned Names and Numbers','ICANN" + " | Internet Corporation for Assigned Names and Numbers',NULL,NULL,X'C" + "28810240A15687474703A2F2F7777772E6963616E6E2E636F6D2F120B504E47415846" + "3041414646',X'C28810200A15687474703A2F2F7777772E6963616E6E2E636F6D2F1" + "20744414146415346',NULL,X'',X'',X'');" + "INSERT INTO 'metas' VALUES(14,692,692,11,0," + META_PROTO_TIMES_VALS(14) ",'s_ID_14','s_ID_6','s_ID_6',0,0,0,0,0,0" + ",'The WebKit Open Source Project','The WebKit Open Source Project',NU" + "LL,NULL,X'C288101A0A12687474703A2F2F7765626B69742E6F72672F1204504E475" + "8',X'C288101C0A13687474703A2F2F7765626B69742E6F72672F781205504E473259" + "',NULL,X'',X'',X'');" + "CREATE TABLE deleted_metas (metahandle bigint primary key ON CONFLICT" + " FAIL,base_version bigint default -1,server_version bigint default 0," + "local_external_id bigint default 0,transaction_version bigint default" + " 0,mtime bigint default 0,server_mtime bigint default 0,ctime bigint " + "default 0,server_ctime bigint default 0,id varchar(255) default 'r',p" + "arent_id varchar(255) default 'r',server_parent_id varchar(255) defau" + "lt 'r',is_unsynced bit default 0,is_unapplied_update bit default 0,is" + "_del bit default 0,is_dir bit default 0,server_is_dir bit default 0,s" + "erver_is_del bit default 0,non_unique_name varchar,server_non_unique_" + "name varchar(255),unique_server_tag varchar,unique_client_tag varchar" + ",specifics blob,server_specifics blob,base_server_specifics blob,serv" + "er_unique_position blob,unique_position blob,unique_bookmark_tag blob" + ");" + "CREATE TABLE 'share_info' (id TEXT primary key, name TEXT, store_birt" + "hday TEXT, db_create_version TEXT, db_create_time INT, next_id INT de" + "fault -2, cache_guid TEXT, notification_state BLOB, bag_of_chips BLOB" + ");" + "INSERT INTO 'share_info' VALUES('nick@chromium.org','nick@chromium.or" + "g','c27e9f59-08ca-46f8-b0cc-f16a2ed778bb','Unknown',1263522064,-13107" + "8,'9010788312004066376x-6609234393368420856x',NULL,NULL);")); + ASSERT_TRUE(connection->CommitTransaction()); +} + TEST_F(DirectoryBackingStoreTest, MigrateVersion67To68) { sql::Connection connection; ASSERT_TRUE(connection.OpenInMemory()); @@ -2812,34 +2903,6 @@ TEST_F(DirectoryBackingStoreTest, MigrateVersion80To81) { ASSERT_EQ(expected_ordinal, actual_ordinal); } -TEST_F(DirectoryBackingStoreTest, DetectInvalidOrdinal) { - sql::Connection connection; - ASSERT_TRUE(connection.OpenInMemory()); - SetUpVersion81Database(&connection); - - scoped_ptr<TestDirectoryBackingStore> dbs( - new TestDirectoryBackingStore(GetUsername(), &connection)); - ASSERT_EQ(81, dbs->GetVersion()); - - // Insert row with bad ordinal. - const int64 now = TimeToProtoTime(base::Time::Now()); - sql::Statement s(connection.GetUniqueStatement( - "INSERT INTO metas " - "( id, metahandle, is_dir, ctime, mtime, server_ordinal_in_parent) " - "VALUES( \"c-invalid\", 9999, 1, ?, ?, \" \")")); - s.BindInt64(0, now); - s.BindInt64(1, now); - ASSERT_TRUE(s.Run()); - - // Trying to unpack this entry should signal that the DB is corrupted. - MetahandlesIndex entry_bucket; - JournalIndex delete_journals;; - STLElementDeleter<MetahandlesIndex> deleter(&entry_bucket); - Directory::KernelLoadInfo kernel_load_info; - ASSERT_EQ(FAILED_DATABASE_CORRUPT, - dbs->Load(&entry_bucket, &delete_journals, &kernel_load_info)); -} - TEST_F(DirectoryBackingStoreTest, MigrateVersion81To82) { sql::Connection connection; ASSERT_TRUE(connection.OpenInMemory()); @@ -2897,6 +2960,130 @@ TEST_F(DirectoryBackingStoreTest, MigrateVersion84To85) { ASSERT_FALSE(connection.DoesColumnExist("models", "initial_sync_ended")); } +TEST_F(DirectoryBackingStoreTest, MigrateVersion85To86) { + sql::Connection connection; + ASSERT_TRUE(connection.OpenInMemory()); + SetUpVersion85Database(&connection); + EXPECT_TRUE(connection.DoesColumnExist("metas", "next_id")); + EXPECT_TRUE(connection.DoesColumnExist("metas", "prev_id")); + EXPECT_TRUE(connection.DoesColumnExist("metas", "server_ordinal_in_parent")); + EXPECT_FALSE(connection.DoesColumnExist("metas", "unique_position")); + EXPECT_FALSE(connection.DoesColumnExist("metas", "server_unique_position")); + EXPECT_FALSE(connection.DoesColumnExist("metas", "unique_bookmark_tag")); + + scoped_ptr<TestDirectoryBackingStore> dbs( + new TestDirectoryBackingStore(GetUsername(), &connection)); + ASSERT_TRUE(dbs->MigrateVersion85To86()); + EXPECT_EQ(86, dbs->GetVersion()); + EXPECT_TRUE(connection.DoesColumnExist("metas", "unique_position")); + EXPECT_TRUE(connection.DoesColumnExist("metas", "server_unique_position")); + EXPECT_TRUE(connection.DoesColumnExist("metas", "unique_bookmark_tag")); + ASSERT_TRUE(dbs->needs_column_refresh_); + ASSERT_TRUE(dbs->RefreshColumns()); + EXPECT_FALSE(connection.DoesColumnExist("metas", "next_id")); + EXPECT_FALSE(connection.DoesColumnExist("metas", "prev_id")); + EXPECT_FALSE(connection.DoesColumnExist("metas", "server_ordinal_in_parent")); + + { + MetahandlesIndex metas; + STLElementDeleter<MetahandlesIndex> deleter(&metas); + dbs->LoadEntries(&metas); + + EntryKernel needle; + + // Grab a bookmark and examine it. + needle.put(META_HANDLE, 5); + MetahandlesIndex::iterator i = metas.find(&needle); + ASSERT_FALSE(i == metas.end()); + EntryKernel* bm = *i; + ASSERT_EQ(bm->ref(ID).value(), "s_ID_5"); + + EXPECT_TRUE(bm->ref(UNIQUE_POSITION).IsValid()); + EXPECT_TRUE(bm->ref(SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_EQ(UniquePosition::kSuffixLength, + bm->ref(UNIQUE_BOOKMARK_TAG).length()); + + // Grab a non-bookmark and examine it. + needle.put(META_HANDLE, 1); + MetahandlesIndex::iterator j = metas.find(&needle); + ASSERT_FALSE(j == metas.end()); + EntryKernel* root = *j; + ASSERT_EQ(root->ref(ID).value(), "r"); + + EXPECT_FALSE(root->ref(UNIQUE_POSITION).IsValid()); + EXPECT_FALSE(root->ref(SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_TRUE(root->ref(UNIQUE_BOOKMARK_TAG).empty()); + + // Make sure we didn't mistake the bookmark root node for a real bookmark. + needle.put(META_HANDLE, 8); + MetahandlesIndex::iterator k = metas.find(&needle); + ASSERT_FALSE(k == metas.end()); + EntryKernel* bm_root = *k; + ASSERT_EQ(bm_root->ref(ID).value(), "s_ID_8"); + ASSERT_EQ(bm_root->ref(UNIQUE_SERVER_TAG), "google_chrome_bookmarks"); + + EXPECT_FALSE(bm_root->ref(UNIQUE_POSITION).IsValid()); + EXPECT_FALSE(bm_root->ref(SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_TRUE(bm_root->ref(UNIQUE_BOOKMARK_TAG).empty()); + + // Make sure we didn't assign positions to server-created folders, either. + needle.put(META_HANDLE, 10); + MetahandlesIndex::iterator l = metas.find(&needle); + ASSERT_FALSE(l == metas.end()); + EntryKernel* perm_folder = *l; + ASSERT_EQ(perm_folder->ref(ID).value(), "s_ID_10"); + ASSERT_EQ(perm_folder->ref(UNIQUE_SERVER_TAG), "other_bookmarks"); + + EXPECT_FALSE(perm_folder->ref(UNIQUE_POSITION).IsValid()); + EXPECT_FALSE(perm_folder->ref(SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_TRUE(perm_folder->ref(UNIQUE_BOOKMARK_TAG).empty()); + + // Make sure that the syncable::Directory and the migration code agree on + // which items should or should not have unique position values. This test + // may become obsolete if the directory's definition of that function + // changes, but, until then, this is a useful test. + for (MetahandlesIndex::iterator it = metas.begin(); + it != metas.end(); it++) { + SCOPED_TRACE((*it)->ref(ID)); + if ((*it)->ShouldMaintainPosition()) { + EXPECT_TRUE((*it)->ref(UNIQUE_POSITION).IsValid()); + EXPECT_TRUE((*it)->ref(SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_FALSE((*it)->ref(UNIQUE_BOOKMARK_TAG).empty()); + } else { + EXPECT_FALSE((*it)->ref(UNIQUE_POSITION).IsValid()); + EXPECT_FALSE((*it)->ref(SERVER_UNIQUE_POSITION).IsValid()); + EXPECT_TRUE((*it)->ref(UNIQUE_BOOKMARK_TAG).empty()); + } + } + } +} + +TEST_F(DirectoryBackingStoreTest, DetectInvalidPosition) { + sql::Connection connection; + ASSERT_TRUE(connection.OpenInMemory()); + SetUpVersion86Database(&connection); + + scoped_ptr<TestDirectoryBackingStore> dbs( + new TestDirectoryBackingStore(GetUsername(), &connection)); + ASSERT_EQ(86, dbs->GetVersion()); + + // Insert row with bad position. + sql::Statement s(connection.GetUniqueStatement( + "INSERT INTO metas " + "( id, metahandle, is_dir, ctime, mtime," + " unique_position, server_unique_position) " + "VALUES('c-invalid', 9999, 1, 0, 0, 'BAD_POS', 'BAD_POS')")); + ASSERT_TRUE(s.Run()); + + // Trying to unpack this entry should signal that the DB is corrupted. + MetahandlesIndex entry_bucket; + JournalIndex delete_journals;; + STLElementDeleter<MetahandlesIndex> deleter(&entry_bucket); + Directory::KernelLoadInfo kernel_load_info; + ASSERT_EQ(FAILED_DATABASE_CORRUPT, + dbs->Load(&entry_bucket, &delete_journals, &kernel_load_info)); +} + TEST_P(MigrationTest, ToCurrentVersion) { sql::Connection connection; ASSERT_TRUE(connection.OpenInMemory()); @@ -2955,6 +3142,12 @@ TEST_P(MigrationTest, ToCurrentVersion) { case 84: SetUpVersion84Database(&connection); break; + case 85: + SetUpVersion85Database(&connection); + break; + case 86: + SetUpVersion86Database(&connection); + break; default: // If you see this error, it may mean that you've increased the // database version number but you haven't finished adding unit tests @@ -3169,7 +3362,7 @@ TEST_P(MigrationTest, ToCurrentVersion) { } INSTANTIATE_TEST_CASE_P(DirectoryBackingStore, MigrationTest, - testing::Range(67, kCurrentDBVersion)); + testing::Range(67, kCurrentDBVersion + 1)); TEST_F(DirectoryBackingStoreTest, ModelTypeIds) { ModelTypeSet protocol_types = ProtocolTypes(); diff --git a/sync/syncable/entry.cc b/sync/syncable/entry.cc index c6cc4f0..2d98c6f 100644 --- a/sync/syncable/entry.cc +++ b/sync/syncable/entry.cc @@ -7,6 +7,7 @@ #include <iomanip> #include "base/json/string_escape.h" +#include "base/string_util.h" #include "sync/syncable/blob.h" #include "sync/syncable/directory.h" #include "sync/syncable/syncable_base_transaction.h" @@ -41,10 +42,6 @@ Directory* Entry::dir() const { return basetrans_->directory(); } -Id Entry::ComputePrevIdFromServerPosition(const Id& parent_id) const { - return dir()->ComputePrevIdFromServerPosition(kernel_, parent_id); -} - DictionaryValue* Entry::ToValue(Cryptographer* cryptographer) const { DictionaryValue* entry_info = new DictionaryValue(); entry_info->SetBoolean("good", good()); @@ -96,11 +93,19 @@ ModelType Entry::GetModelType() const { } Id Entry::GetPredecessorId() const { - return kernel_->ref(PREV_ID); + return dir()->GetPredecessorId(kernel_); } Id Entry::GetSuccessorId() const { - return kernel_->ref(NEXT_ID); + return dir()->GetSuccessorId(kernel_); +} + +Id Entry::GetFirstChildId() const { + return dir()->GetFirstChildId(basetrans_, kernel_); +} + +bool Entry::ShouldMaintainPosition() const { + return kernel_->ShouldMaintainPosition(); } std::ostream& operator<<(std::ostream& s, const Blob& blob) { @@ -142,9 +147,9 @@ std::ostream& operator<<(std::ostream& os, const Entry& entry) { &escaped_str); os << g_metas_columns[i].name << ": " << escaped_str << ", "; } - for ( ; i < ORDINAL_FIELDS_END; ++i) { + for ( ; i < UNIQUE_POSITION_FIELDS_END; ++i) { os << g_metas_columns[i].name << ": " - << kernel->ref(static_cast<OrdinalField>(i)).ToDebugString() + << kernel->ref(static_cast<UniquePositionField>(i)).ToDebugString() << ", "; } os << "TempFlags: "; diff --git a/sync/syncable/entry.h b/sync/syncable/entry.h index e1c8717..f9d3f90 100644 --- a/sync/syncable/entry.h +++ b/sync/syncable/entry.h @@ -93,7 +93,7 @@ class SYNC_EXPORT Entry { DCHECK(kernel_); return kernel_->ref(field); } - inline const NodeOrdinal& Get(OrdinalField field) const { + inline const UniquePosition& Get(UniquePositionField field) const { DCHECK(kernel_); return kernel_->ref(field); } @@ -107,6 +107,7 @@ class SYNC_EXPORT Entry { Id GetPredecessorId() const; Id GetSuccessorId() const; + Id GetFirstChildId() const; inline bool ExistsOnClientBecauseNameIsNonEmpty() const { DCHECK(kernel_); @@ -118,18 +119,16 @@ class SYNC_EXPORT Entry { return kernel_->ref(ID).IsRoot(); } + // Returns true if this is an entry that is expected to maintain a certain + // sort ordering relative to its siblings under the same parent. + bool ShouldMaintainPosition() const; + Directory* dir() const; const EntryKernel GetKernelCopy() const { return *kernel_; } - // Compute a local predecessor position for |update_item|, based on its - // absolute server position. The returned ID will be a valid predecessor - // under SERVER_PARENT_ID that is consistent with the - // SERVER_POSITION_IN_PARENT ordering. - Id ComputePrevIdFromServerPosition(const Id& parent_id) const; - // Dumps all entry info into a DictionaryValue and returns it. // Transfers ownership of the DictionaryValue to the caller. base::DictionaryValue* ToValue(Cryptographer* cryptographer) const; diff --git a/sync/syncable/entry_kernel.cc b/sync/syncable/entry_kernel.cc index 5b21612..01f2cae 100644 --- a/sync/syncable/entry_kernel.cc +++ b/sync/syncable/entry_kernel.cc @@ -21,6 +21,20 @@ EntryKernel::EntryKernel() : dirty_(false) { EntryKernel::~EntryKernel() {} +ModelType EntryKernel::GetModelType() const { + ModelType specifics_type = GetModelTypeFromSpecifics(ref(SPECIFICS)); + if (specifics_type != UNSPECIFIED) + return specifics_type; + if (ref(ID).IsRoot()) + return TOP_LEVEL_FOLDER; + // Loose check for server-created top-level folders that aren't + // bound to a particular model type. + if (!ref(UNIQUE_SERVER_TAG).empty() && ref(SERVER_IS_DIR)) + return TOP_LEVEL_FOLDER; + + return UNSPECIFIED; +} + ModelType EntryKernel::GetServerModelType() const { ModelType specifics_type = GetModelTypeFromSpecifics(ref(SERVER_SPECIFICS)); if (specifics_type != UNSPECIFIED) @@ -35,6 +49,13 @@ ModelType EntryKernel::GetServerModelType() const { return UNSPECIFIED; } +bool EntryKernel::ShouldMaintainPosition() const { + // We maintain positions for all bookmarks, except those that are + // server-created top-level folders. + return (GetModelTypeFromSpecifics(ref(SPECIFICS)) == syncer::BOOKMARKS) + && !(!ref(UNIQUE_SERVER_TAG).empty() && ref(IS_DIR)); +} + namespace { // Utility function to loop through a set of enum values and add the @@ -96,10 +117,6 @@ base::StringValue* IdToValue(const Id& id) { return id.ToValue(); } -base::StringValue* OrdinalToValue(const NodeOrdinal& ord) { - return new base::StringValue(ord.ToDebugString()); -} - base::FundamentalValue* BooleanToValue(bool bool_val) { return new base::FundamentalValue(bool_val); } @@ -108,6 +125,10 @@ base::StringValue* StringToValue(const std::string& str) { return new base::StringValue(str); } +StringValue* UniquePositionToValue(const UniquePosition& pos) { + return Value::CreateStringValue(pos.ToDebugString()); +} + } // namespace base::DictionaryValue* EntryKernel::ToValue( @@ -160,10 +181,10 @@ base::DictionaryValue* EntryKernel::ToValue( SetEncryptableProtoValues(*this, cryptographer, kernel_info, PROTO_FIELDS_BEGIN, PROTO_FIELDS_END - 1); - // Ordinal fields + // UniquePosition fields SetFieldValues(*this, kernel_info, - &GetOrdinalFieldString, &OrdinalToValue, - ORDINAL_FIELDS_BEGIN, ORDINAL_FIELDS_END - 1); + &GetUniquePositionFieldString, &UniquePositionToValue, + UNIQUE_POSITION_FIELDS_BEGIN, UNIQUE_POSITION_FIELDS_END - 1); // Bit temps. SetFieldValues(*this, kernel_info, diff --git a/sync/syncable/entry_kernel.h b/sync/syncable/entry_kernel.h index e9cf828..16a6e97 100644 --- a/sync/syncable/entry_kernel.h +++ b/sync/syncable/entry_kernel.h @@ -11,7 +11,7 @@ #include "base/values.h" #include "sync/base/sync_export.h" #include "sync/internal_api/public/base/model_type.h" -#include "sync/internal_api/public/base/node_ordinal.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/internal_api/public/util/immutable.h" #include "sync/protocol/sync.pb.h" #include "sync/syncable/metahandle_set.h" @@ -83,9 +83,6 @@ enum IdField { ID = ID_FIELDS_BEGIN, PARENT_ID, SERVER_PARENT_ID, - - PREV_ID, - NEXT_ID, ID_FIELDS_END }; @@ -127,6 +124,7 @@ enum StringField { // identifies a singleton instance. UNIQUE_SERVER_TAG, // Tagged by the server UNIQUE_CLIENT_TAG, // Tagged by the client + UNIQUE_BOOKMARK_TAG, // Client tags for bookmark items STRING_FIELDS_END, }; @@ -146,21 +144,21 @@ enum ProtoField { enum { PROTO_FIELDS_COUNT = PROTO_FIELDS_END - PROTO_FIELDS_BEGIN, - ORDINAL_FIELDS_BEGIN = PROTO_FIELDS_END + UNIQUE_POSITION_FIELDS_BEGIN = PROTO_FIELDS_END }; -enum OrdinalField { - // An Ordinal that identifies the relative ordering of this object - // among its siblings. - SERVER_ORDINAL_IN_PARENT = ORDINAL_FIELDS_BEGIN, - ORDINAL_FIELDS_END +enum UniquePositionField { + SERVER_UNIQUE_POSITION = UNIQUE_POSITION_FIELDS_BEGIN, + UNIQUE_POSITION, + UNIQUE_POSITION_FIELDS_END }; enum { - ORDINAL_FIELDS_COUNT = ORDINAL_FIELDS_END - ORDINAL_FIELDS_BEGIN, - FIELD_COUNT = ORDINAL_FIELDS_END - BEGIN_FIELDS, + UNIQUE_POSITION_FIELDS_COUNT = + UNIQUE_POSITION_FIELDS_END - UNIQUE_POSITION_FIELDS_BEGIN, + FIELD_COUNT = UNIQUE_POSITION_FIELDS_END - BEGIN_FIELDS, // Past this point we have temporaries, stored in memory only. - BEGIN_TEMPS = ORDINAL_FIELDS_END, + BEGIN_TEMPS = UNIQUE_POSITION_FIELDS_END, BIT_TEMPS_BEGIN = BEGIN_TEMPS, }; @@ -184,7 +182,7 @@ struct SYNC_EXPORT_PRIVATE EntryKernel { int64 int64_fields[INT64_FIELDS_COUNT]; base::Time time_fields[TIME_FIELDS_COUNT]; Id id_fields[ID_FIELDS_COUNT]; - NodeOrdinal ordinal_fields[ORDINAL_FIELDS_COUNT]; + UniquePosition unique_position_fields[UNIQUE_POSITION_FIELDS_COUNT]; std::bitset<BIT_FIELDS_COUNT> bit_fields; std::bitset<BIT_TEMPS_COUNT> bit_temps; @@ -252,8 +250,8 @@ struct SYNC_EXPORT_PRIVATE EntryKernel { inline void put(ProtoField field, const sync_pb::EntitySpecifics& value) { specifics_fields[field - PROTO_FIELDS_BEGIN].CopyFrom(value); } - inline void put(OrdinalField field, const NodeOrdinal& value) { - ordinal_fields[field - ORDINAL_FIELDS_BEGIN] = value; + inline void put(UniquePositionField field, const UniquePosition& value) { + unique_position_fields[field - UNIQUE_POSITION_FIELDS_BEGIN] = value; } inline void put(BitTemp field, bool value) { bit_temps[field - BIT_TEMPS_BEGIN] = value; @@ -290,8 +288,8 @@ struct SYNC_EXPORT_PRIVATE EntryKernel { inline const sync_pb::EntitySpecifics& ref(ProtoField field) const { return specifics_fields[field - PROTO_FIELDS_BEGIN]; } - inline const NodeOrdinal& ref(OrdinalField field) const { - return ordinal_fields[field - ORDINAL_FIELDS_BEGIN]; + inline const UniquePosition& ref(UniquePositionField field) const { + return unique_position_fields[field - UNIQUE_POSITION_FIELDS_BEGIN]; } inline bool ref(BitTemp field) const { return bit_temps[field - BIT_TEMPS_BEGIN]; @@ -307,11 +305,13 @@ struct SYNC_EXPORT_PRIVATE EntryKernel { inline Id& mutable_ref(IdField field) { return id_fields[field - ID_FIELDS_BEGIN]; } - inline NodeOrdinal& mutable_ref(OrdinalField field) { - return ordinal_fields[field - ORDINAL_FIELDS_BEGIN]; + inline UniquePosition& mutable_ref(UniquePositionField field) { + return unique_position_fields[field - UNIQUE_POSITION_FIELDS_BEGIN]; } + ModelType GetModelType() const; ModelType GetServerModelType() const; + bool ShouldMaintainPosition() const; // Dumps all kernel info into a DictionaryValue and returns it. // Transfers ownership of the DictionaryValue to the caller. diff --git a/sync/syncable/in_memory_directory_backing_store.cc b/sync/syncable/in_memory_directory_backing_store.cc index 9451354..f130fb5 100644 --- a/sync/syncable/in_memory_directory_backing_store.cc +++ b/sync/syncable/in_memory_directory_backing_store.cc @@ -8,7 +8,9 @@ namespace syncer { namespace syncable { InMemoryDirectoryBackingStore::InMemoryDirectoryBackingStore( - const std::string& dir_name) : DirectoryBackingStore(dir_name) { + const std::string& dir_name) + : DirectoryBackingStore(dir_name), + consistent_cache_guid_requested_(false) { } DirOpenResult InMemoryDirectoryBackingStore::Load( @@ -23,6 +25,13 @@ DirOpenResult InMemoryDirectoryBackingStore::Load( if (!InitializeTables()) return FAILED_OPEN_DATABASE; + if (consistent_cache_guid_requested_) { + if (!db_->Execute("UPDATE share_info " + "SET cache_guid = 'IrcjZ2jyzHDV9Io4+zKcXQ=='")) { + return FAILED_OPEN_DATABASE; + } + } + if (!DropDeletedEntries()) return FAILED_DATABASE_CORRUPT; if (!LoadEntries(entry_bucket)) diff --git a/sync/syncable/in_memory_directory_backing_store.h b/sync/syncable/in_memory_directory_backing_store.h index 846d96a..3afa051 100644 --- a/sync/syncable/in_memory_directory_backing_store.h +++ b/sync/syncable/in_memory_directory_backing_store.h @@ -29,7 +29,13 @@ class SYNC_EXPORT_PRIVATE InMemoryDirectoryBackingStore JournalIndex* delete_journals, Directory::KernelLoadInfo* kernel_load_info) OVERRIDE; + void request_consistent_cache_guid() { + consistent_cache_guid_requested_ = true; + } + private: + bool consistent_cache_guid_requested_; + DISALLOW_COPY_AND_ASSIGN(InMemoryDirectoryBackingStore); }; diff --git a/sync/syncable/model_type.cc b/sync/syncable/model_type.cc index 31120a7..2657ebc 100644 --- a/sync/syncable/model_type.cc +++ b/sync/syncable/model_type.cc @@ -306,10 +306,6 @@ ModelType GetModelTypeFromSpecifics(const sync_pb::EntitySpecifics& specifics) { return UNSPECIFIED; } -bool ShouldMaintainPosition(ModelType model_type) { - return model_type == BOOKMARKS; -} - ModelTypeSet ProtocolTypes() { ModelTypeSet set = ModelTypeSet::All(); set.RemoveAll(ProxyTypes()); diff --git a/sync/syncable/mutable_entry.cc b/sync/syncable/mutable_entry.cc index 70b2a26..7c91135 100644 --- a/sync/syncable/mutable_entry.cc +++ b/sync/syncable/mutable_entry.cc @@ -5,10 +5,11 @@ #include "sync/syncable/mutable_entry.h" #include "base/memory/scoped_ptr.h" -#include "sync/internal_api/public/base/node_ordinal.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/syncable/directory.h" #include "sync/syncable/scoped_index_updater.h" #include "sync/syncable/scoped_kernel_lock.h" +#include "sync/syncable/scoped_parent_child_index_updater.h" #include "sync/syncable/syncable-inl.h" #include "sync/syncable/syncable_changes_version.h" #include "sync/syncable/syncable_util.h" @@ -36,7 +37,6 @@ void MutableEntry::Init(WriteTransaction* trans, kernel->put(MTIME, now); // We match the database defaults here kernel->put(BASE_VERSION, CHANGES_VERSION); - kernel->put(SERVER_ORDINAL_IN_PARENT, NodeOrdinal::CreateInitialOrdinal()); // Normally the SPECIFICS setting code is wrapped in logic to deal with // unknown fields and encryption. Since all we want to do here is ensure that @@ -63,8 +63,19 @@ MutableEntry::MutableEntry(WriteTransaction* trans, : Entry(trans), write_transaction_(trans) { Init(trans, model_type, parent_id, name); - bool insert_result = trans->directory()->InsertEntry(trans, kernel_); - DCHECK(insert_result); + // We need to have a valid position ready before we can index the item. + if (model_type == BOOKMARKS) { + // Base the tag off of our cache-guid and local "c-" style ID. + std::string unique_tag = syncable::GenerateSyncableBookmarkHash( + trans->directory()->cache_guid(), Get(ID).GetServerId()); + kernel_->put(UNIQUE_BOOKMARK_TAG, unique_tag); + kernel_->put(UNIQUE_POSITION, UniquePosition::InitialPosition(unique_tag)); + } else { + DCHECK(!ShouldMaintainPosition()); + } + + bool result = trans->directory()->InsertEntry(trans, kernel_); + DCHECK(result); } MutableEntry::MutableEntry(WriteTransaction* trans, CreateNewUpdateItem, @@ -80,7 +91,6 @@ MutableEntry::MutableEntry(WriteTransaction* trans, CreateNewUpdateItem, kernel->put(ID, id); kernel->put(META_HANDLE, trans->directory_->NextMetahandle()); kernel->mark_dirty(trans->directory_->kernel_->dirty_metahandles); - kernel->put(SERVER_ORDINAL_IN_PARENT, NodeOrdinal::CreateInitialOrdinal()); kernel->put(IS_DEL, true); // We match the database defaults here kernel->put(BASE_VERSION, CHANGES_VERSION); @@ -118,10 +128,6 @@ bool MutableEntry::PutIsDel(bool is_del) { return true; } if (is_del) { - if (!UnlinkFromOrder()) { - return false; - } - // If the server never knew about this item and it's deleted then we don't // need to keep it around. Unsetting IS_UNSYNCED will: // - Ensure that the item is never committed to the server. @@ -139,20 +145,13 @@ bool MutableEntry::PutIsDel(bool is_del) { ScopedKernelLock lock(dir()); // Some indices don't include deleted items and must be updated // upon a value change. - ScopedIndexUpdater<ParentIdAndHandleIndexer> updater(lock, kernel_, - dir()->kernel_->parent_id_child_index); + ScopedParentChildIndexUpdater updater(lock, kernel_, + dir()->kernel_->parent_child_index); kernel_->put(IS_DEL, is_del); kernel_->mark_dirty(dir()->kernel_->dirty_metahandles); } - if (!is_del) - // Restores position to the 0th index. - if (!PutPredecessor(Id())) { - // TODO(lipalani) : Propagate the error to caller. crbug.com/100444. - NOTREACHED(); - } - return true; } @@ -185,11 +184,12 @@ bool MutableEntry::Put(IdField field, const Id& value) { if (!dir()->ReindexId(write_transaction(), kernel_, value)) return false; } else if (PARENT_ID == field) { - PutParentIdPropertyOnly(value); // Makes sibling order inconsistent. - // Fixes up the sibling order inconsistency. - if (!PutPredecessor(Id())) { - // TODO(lipalani) : Propagate the error to caller. crbug.com/100444. - NOTREACHED(); + PutParentIdPropertyOnly(value); + if (!Get(IS_DEL)) { + if (!PutPredecessor(Id())) { + // TODO(lipalani) : Propagate the error to caller. crbug.com/100444. + NOTREACHED(); + } } } else { kernel_->put(field, value); @@ -199,15 +199,16 @@ bool MutableEntry::Put(IdField field, const Id& value) { return true; } -bool MutableEntry::Put(OrdinalField field, const NodeOrdinal& value) { +bool MutableEntry::Put(UniquePositionField field, const UniquePosition& value) { DCHECK(kernel_); - DCHECK(value.IsValid()); write_transaction_->SaveOriginal(kernel_); if(!kernel_->ref(field).Equals(value)) { + // We should never overwrite a valid position with an invalid one. + DCHECK(value.IsValid()); ScopedKernelLock lock(dir()); - if (SERVER_ORDINAL_IN_PARENT == field) { - ScopedIndexUpdater<ParentIdAndHandleIndexer> updater( - lock, kernel_, dir()->kernel_->parent_id_child_index); + if (UNIQUE_POSITION == field) { + ScopedParentChildIndexUpdater updater( + lock, kernel_, dir()->kernel_->parent_child_index); kernel_->put(field, value); } else { kernel_->put(field, value); @@ -375,67 +376,34 @@ bool MutableEntry::Put(IndexedBitField field, bool value) { return true; } -bool MutableEntry::UnlinkFromOrder() { - ScopedKernelLock lock(dir()); - return dir()->UnlinkEntryFromOrder(kernel_, - write_transaction(), - &lock, - NODE_MANIPULATION); +void MutableEntry::PutUniqueBookmarkTag(const std::string& tag) { + // This unique tag will eventually be used as the unique suffix when adjusting + // this bookmark's position. Let's make sure it's a valid suffix. + if (!UniquePosition::IsValidSuffix(tag)) { + NOTREACHED(); + return; + } + + if (!kernel_->ref(UNIQUE_BOOKMARK_TAG).empty() + && tag != kernel_->ref(UNIQUE_BOOKMARK_TAG)) { + // There is only one scenario where our tag is expected to change. That + // scenario occurs when our current tag is a non-correct tag assigned during + // the UniquePosition migration. + std::string migration_generated_tag = + GenerateSyncableBookmarkHash(std::string(), + kernel_->ref(ID).GetServerId()); + DCHECK_EQ(migration_generated_tag, kernel_->ref(UNIQUE_BOOKMARK_TAG)); + } + + kernel_->put(UNIQUE_BOOKMARK_TAG, tag); + kernel_->mark_dirty(dir()->kernel_->dirty_metahandles); } bool MutableEntry::PutPredecessor(const Id& predecessor_id) { - if (!UnlinkFromOrder()) + MutableEntry predecessor(write_transaction_, GET_BY_ID, predecessor_id); + if (!predecessor.good()) return false; - - if (Get(IS_DEL)) { - DCHECK(predecessor_id.IsNull()); - return true; - } - - // TODO(ncarter): It should be possible to not maintain position for - // non-bookmark items. However, we'd need to robustly handle all possible - // permutations of setting IS_DEL and the SPECIFICS to identify the - // object type; or else, we'd need to add a ModelType to the - // MutableEntry's Create ctor. - // if (!ShouldMaintainPosition()) { - // return false; - // } - - // This is classic insert-into-doubly-linked-list from CS 101 and your last - // job interview. An "IsRoot" Id signifies the head or tail. - Id successor_id; - if (!predecessor_id.IsRoot()) { - MutableEntry predecessor(write_transaction(), GET_BY_ID, predecessor_id); - if (!predecessor.good()) { - LOG(ERROR) << "Predecessor is not good : " - << predecessor_id.GetServerId(); - return false; - } - if (predecessor.Get(PARENT_ID) != Get(PARENT_ID)) - return false; - successor_id = predecessor.GetSuccessorId(); - predecessor.Put(NEXT_ID, Get(ID)); - } else { - syncable::Directory* dir = trans()->directory(); - if (!dir->GetFirstChildId(trans(), Get(PARENT_ID), &successor_id)) { - return false; - } - } - if (!successor_id.IsRoot()) { - MutableEntry successor(write_transaction(), GET_BY_ID, successor_id); - if (!successor.good()) { - LOG(ERROR) << "Successor is not good: " - << successor_id.GetServerId(); - return false; - } - if (successor.Get(PARENT_ID) != Get(PARENT_ID)) - return false; - successor.Put(PREV_ID, Get(ID)); - } - DCHECK(predecessor_id != Get(ID)); - DCHECK(successor_id != Get(ID)); - Put(PREV_ID, predecessor_id); - Put(NEXT_ID, successor_id); + dir()->PutPredecessor(kernel_, predecessor.kernel_); return true; } diff --git a/sync/syncable/mutable_entry.h b/sync/syncable/mutable_entry.h index 51cd794..134e4a9 100644 --- a/sync/syncable/mutable_entry.h +++ b/sync/syncable/mutable_entry.h @@ -7,7 +7,6 @@ #include "sync/base/sync_export.h" #include "sync/internal_api/public/base/model_type.h" -#include "sync/internal_api/public/base/node_ordinal.h" #include "sync/syncable/entry.h" #include "sync/syncable/metahandle_set.h" @@ -52,7 +51,7 @@ class SYNC_EXPORT_PRIVATE MutableEntry : public Entry { bool Put(Int64Field field, const int64& value); bool Put(TimeField field, const base::Time& value); bool Put(IdField field, const Id& value); - bool Put(OrdinalField field, const NodeOrdinal& value); + bool Put(UniquePositionField field, const UniquePosition& value); // Do a simple property-only update if the PARENT_ID field. Use with caution. // @@ -75,6 +74,8 @@ class SYNC_EXPORT_PRIVATE MutableEntry : public Entry { } bool Put(IndexedBitField field, bool value); + void PutUniqueBookmarkTag(const std::string& tag); + // Sets the position of this item, and updates the entry kernels of the // adjacent siblings so that list invariants are maintained. Returns false // and fails if |predecessor_id| does not identify a sibling. Pass the root diff --git a/sync/syncable/nigori_util.cc b/sync/syncable/nigori_util.cc index 4888f66..1b00dbd 100644 --- a/sync/syncable/nigori_util.cc +++ b/sync/syncable/nigori_util.cc @@ -108,12 +108,7 @@ bool VerifyDataTypeEncryptionForTest( } std::queue<Id> to_visit; - Id id_string; - if (!trans->directory()->GetFirstChildId( - trans, type_root.Get(ID), &id_string)) { - NOTREACHED(); - return false; - } + Id id_string = type_root.GetFirstChildId(); to_visit.push(id_string); while (!to_visit.empty()) { id_string = to_visit.front(); @@ -127,12 +122,7 @@ bool VerifyDataTypeEncryptionForTest( return false; } if (child.Get(IS_DIR)) { - Id child_id_string; - if (!trans->directory()->GetFirstChildId( - trans, child.Get(ID), &child_id_string)) { - NOTREACHED(); - return false; - } + Id child_id_string = child.GetFirstChildId(); // Traverse the children. to_visit.push(child_id_string); } diff --git a/sync/syncable/parent_child_index.cc b/sync/syncable/parent_child_index.cc new file mode 100644 index 0000000..71fb92e --- /dev/null +++ b/sync/syncable/parent_child_index.cc @@ -0,0 +1,115 @@ +// Copyright (c) 2012 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "sync/syncable/parent_child_index.h" + +#include "base/stl_util.h" + +#include "sync/syncable/entry_kernel.h" +#include "sync/syncable/syncable_id.h" + +namespace syncer { +namespace syncable { + +bool ChildComparator::operator()( + const syncable::EntryKernel* a, + const syncable::EntryKernel* b) const { + const UniquePosition& a_pos = a->ref(UNIQUE_POSITION); + const UniquePosition& b_pos = b->ref(UNIQUE_POSITION); + + if (a_pos.IsValid() && b_pos.IsValid()) { + // Position is important to this type. + return a_pos.LessThan(b_pos); + } else if (a_pos.IsValid() && !b_pos.IsValid()) { + // TODO(rlarocque): Remove this case. + // An item with valid position as sibling of one with invalid position. + // We should not support this, but the tests rely on it. For now, just + // move all invalid position items to the right. + return true; + } else if (!a_pos.IsValid() && b_pos.IsValid()) { + // TODO(rlarocque): Remove this case. + // Mirror of the above case. + return false; + } else { + // Position doesn't matter. + DCHECK(!a->ref(UNIQUE_POSITION).IsValid()); + DCHECK(!b->ref(UNIQUE_POSITION).IsValid()); + return a->ref(ID) < b->ref(ID); + } +} + +ParentChildIndex::ParentChildIndex() { +} + +ParentChildIndex::~ParentChildIndex() { + STLDeleteContainerPairSecondPointers( + parent_children_map_.begin(), parent_children_map_.end()); +} + +bool ParentChildIndex::ShouldInclude(const EntryKernel* entry) { + // This index excludes deleted items and the root item. The root + // item is excluded so that it doesn't show up as a child of itself. + return !entry->ref(IS_DEL) && !entry->ref(ID).IsRoot(); +} + +bool ParentChildIndex::Insert(EntryKernel* entry) { + DCHECK(ShouldInclude(entry)); + + const syncable::Id& parent_id = entry->ref(PARENT_ID); + OrderedChildSet* children = NULL; + ParentChildrenMap::iterator i = parent_children_map_.find(parent_id); + if (i != parent_children_map_.end()) { + children = i->second; + } else { + children = new OrderedChildSet(); + parent_children_map_.insert(std::make_pair(parent_id, children)); + } + + return children->insert(entry).second; +} + +// Like the other containers used to help support the syncable::Directory, this +// one does not own any EntryKernels. This function removes references to the +// given EntryKernel but does not delete it. +void ParentChildIndex::Remove(EntryKernel* e) { + ParentChildrenMap::iterator parent = + parent_children_map_.find(e->ref(PARENT_ID)); + DCHECK(parent != parent_children_map_.end()); + + OrderedChildSet* children = parent->second; + OrderedChildSet::iterator j = children->find(e); + DCHECK(j != children->end()); + + children->erase(j); + if (children->empty()) { + delete children; + parent_children_map_.erase(parent); + } +} + +bool ParentChildIndex::Contains(EntryKernel *e) const { + const syncable::Id& parent_id = e->ref(PARENT_ID); + ParentChildrenMap::const_iterator parent = + parent_children_map_.find(parent_id); + if (parent == parent_children_map_.end()) { + return false; + } + const OrderedChildSet* children = parent->second; + DCHECK(children && !children->empty()); + return children->count(e) > 0; +} + +const OrderedChildSet* ParentChildIndex::GetChildren(const syncable::Id& id) { + ParentChildrenMap::iterator parent = parent_children_map_.find(id); + if (parent == parent_children_map_.end()) { + return NULL; + } + + // A successful lookup implies at least some children exist. + DCHECK(!parent->second->empty()); + return parent->second; +} + +} // namespace syncable +} // namespace syncer diff --git a/sync/syncable/parent_child_index.h b/sync/syncable/parent_child_index.h new file mode 100644 index 0000000..fd0f2e8 --- /dev/null +++ b/sync/syncable/parent_child_index.h @@ -0,0 +1,66 @@ +// Copyright (c) 2012 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef SYNC_SYNCABLE_PARENT_CHILD_INDEX +#define SYNC_SYNCABLE_PARENT_CHILD_INDEX + +#include <map> +#include <set> + +#include "base/basictypes.h" +#include "sync/base/sync_export.h" + +namespace syncer { +namespace syncable { + +struct EntryKernel; +class Id; +class ParentChildIndex; + +// A node ordering function. +struct SYNC_EXPORT_PRIVATE ChildComparator { + bool operator() (const EntryKernel* a, const EntryKernel* b) const; +}; + +// An ordered set of nodes. +typedef std::set<EntryKernel*, ChildComparator> OrderedChildSet; + +// Container that tracks parent-child relationships. +// Provides fast lookup of all items under a given parent. +class SYNC_EXPORT_PRIVATE ParentChildIndex { + public: + ParentChildIndex(); + ~ParentChildIndex(); + + // Returns whether or not this entry belongs in the index. + // True for all non-deleted, non-root entries. + static bool ShouldInclude(const EntryKernel* e); + + // Inserts a given child into the index. + bool Insert(EntryKernel* e); + + // Removes a given child from the index. + void Remove(EntryKernel* e); + + // Returns true if this item is in the index as a child. + bool Contains(EntryKernel* e) const; + + // Returns all children of the entry with the given Id. Returns NULL if the + // node has no children or the Id does not identify a valid directory node. + const OrderedChildSet* GetChildren(const Id& id); + + private: + typedef std::map<syncable::Id, OrderedChildSet*> ParentChildrenMap; + + // A map of parent IDs to children. + // Parents with no children are not included in this map. + ParentChildrenMap parent_children_map_; + + DISALLOW_COPY_AND_ASSIGN(ParentChildIndex); +}; + +} // namespace syncable +} // namespace syncer + +#endif // SYNC_SYNCABLE_PARENT_CHILD_INDEX diff --git a/sync/syncable/parent_child_index_unittest.cc b/sync/syncable/parent_child_index_unittest.cc new file mode 100644 index 0000000..a2058c5 --- /dev/null +++ b/sync/syncable/parent_child_index_unittest.cc @@ -0,0 +1,344 @@ +// Copyright (c) 2013 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "sync/syncable/parent_child_index.h" + +#include <list> + +#include "base/stl_util.h" +#include "base/strings/string_number_conversions.h" +#include "sync/syncable/entry_kernel.h" +#include "sync/syncable/syncable_util.h" +#include "testing/gtest/include/gtest/gtest.h" + +namespace syncer { +namespace syncable { + +namespace { + +static const std::string kCacheGuid = "8HhNIHlEOCGQbIAALr9QEg=="; + +class ParentChildIndexTest : public testing::Test { + public: + void TearDown() { + // To make memory management easier, we take ownership of all EntryKernels + // returned by our factory methods and delete them here. + STLDeleteElements(&owned_entry_kernels_); + } + + // Unfortunately, we can't use the regular Entry factory methods, because the + // ParentChildIndex deals in EntryKernels. + + static syncable::Id GetBookmarkRootId() { + return syncable::Id::CreateFromServerId("bookmark_folder"); + } + + static syncable::Id GetBookmarkId(int n) { + return syncable::Id::CreateFromServerId("b" + base::IntToString(n)); + } + + static syncable::Id GetClientUniqueId(int n) { + return syncable::Id::CreateFromServerId("c" + base::IntToString(n)); + } + + EntryKernel* MakeRoot() { + // Mimics the root node. + EntryKernel* root = new EntryKernel(); + root->put(META_HANDLE, 1); + root->put(BASE_VERSION, -1); + root->put(SERVER_VERSION, 0); + root->put(IS_DIR, true); + root->put(ID, syncable::Id()); + root->put(PARENT_ID, syncable::Id()); + root->put(SERVER_PARENT_ID, syncable::Id()); + + owned_entry_kernels_.push_back(root); + return root; + } + + EntryKernel* MakeBookmarkRoot() { + // Mimics a server-created bookmark folder. + EntryKernel* folder = new EntryKernel; + folder->put(META_HANDLE, 1); + folder->put(BASE_VERSION, 9); + folder->put(SERVER_VERSION, 9); + folder->put(IS_DIR, true); + folder->put(ID, GetBookmarkRootId()); + folder->put(SERVER_PARENT_ID, syncable::Id()); + folder->put(PARENT_ID, syncable::Id()); + folder->put(UNIQUE_SERVER_TAG, "google_chrome_bookmarks"); + + owned_entry_kernels_.push_back(folder); + return folder; + } + + EntryKernel* MakeBookmark(int n, int pos, bool is_dir) { + // Mimics a regular bookmark or folder. + EntryKernel* bm = new EntryKernel(); + bm->put(META_HANDLE, n); + bm->put(BASE_VERSION, 10); + bm->put(SERVER_VERSION, 10); + bm->put(IS_DIR, is_dir); + bm->put(ID, GetBookmarkId(n)); + bm->put(PARENT_ID, GetBookmarkRootId()); + bm->put(SERVER_PARENT_ID, GetBookmarkRootId()); + + bm->put(UNIQUE_BOOKMARK_TAG, + syncable::GenerateSyncableBookmarkHash(kCacheGuid, + bm->ref(ID).GetServerId())); + + UniquePosition unique_pos = + UniquePosition::FromInt64(pos, bm->ref(UNIQUE_BOOKMARK_TAG)); + bm->put(UNIQUE_POSITION, unique_pos); + bm->put(SERVER_UNIQUE_POSITION, unique_pos); + + owned_entry_kernels_.push_back(bm); + return bm; + } + + EntryKernel* MakeUniqueClientItem(int n) { + EntryKernel* item = new EntryKernel(); + item->put(META_HANDLE, n); + item->put(BASE_VERSION, 10); + item->put(SERVER_VERSION, 10); + item->put(IS_DIR, false); + item->put(ID, GetClientUniqueId(n)); + item->put(PARENT_ID, syncable::Id()); + item->put(SERVER_PARENT_ID, syncable::Id()); + item->put(UNIQUE_CLIENT_TAG, base::IntToString(n)); + + owned_entry_kernels_.push_back(item); + return item; + } + + ParentChildIndex index_; + + private: + std::list<EntryKernel*> owned_entry_kernels_; +}; + +TEST_F(ParentChildIndexTest, TestRootNode) { + EntryKernel* root = MakeRoot(); + EXPECT_FALSE(ParentChildIndex::ShouldInclude(root)); +} + +TEST_F(ParentChildIndexTest, TestBookmarkRootFolder) { + EntryKernel* bm_folder = MakeBookmarkRoot(); + EXPECT_TRUE(ParentChildIndex::ShouldInclude(bm_folder)); +} + +// Tests iteration over a set of siblings. +TEST_F(ParentChildIndexTest, ChildInsertionAndIteration) { + EntryKernel* bm_folder = MakeBookmarkRoot(); + index_.Insert(bm_folder); + + // Make some folder and non-folder entries. + EntryKernel* b1 = MakeBookmark(1, 1, false); + EntryKernel* b2 = MakeBookmark(2, 2, false); + EntryKernel* b3 = MakeBookmark(3, 3, true); + EntryKernel* b4 = MakeBookmark(4, 4, false); + + // Insert them out-of-order to test different cases. + index_.Insert(b3); // Only child. + index_.Insert(b4); // Right-most child. + index_.Insert(b1); // Left-most child. + index_.Insert(b2); // Between existing items. + + // Double-check they've been added. + EXPECT_TRUE(index_.Contains(b1)); + EXPECT_TRUE(index_.Contains(b2)); + EXPECT_TRUE(index_.Contains(b3)); + EXPECT_TRUE(index_.Contains(b4)); + + // Check the ordering. + const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId()); + ASSERT_TRUE(children); + ASSERT_EQ(children->size(), 4UL); + OrderedChildSet::const_iterator it = children->begin(); + EXPECT_EQ(*it, b1); + it++; + EXPECT_EQ(*it, b2); + it++; + EXPECT_EQ(*it, b3); + it++; + EXPECT_EQ(*it, b4); + it++; + EXPECT_TRUE(it == children->end()); +} + +// Tests iteration when hierarchy is involved. +TEST_F(ParentChildIndexTest, ChildInsertionAndIterationWithHierarchy) { + EntryKernel* bm_folder = MakeBookmarkRoot(); + index_.Insert(bm_folder); + + // Just below the root, we have folders f1 and f2. + EntryKernel* f1 = MakeBookmark(1, 1, false); + EntryKernel* f2 = MakeBookmark(2, 2, false); + EntryKernel* f3 = MakeBookmark(3, 3, false); + + // Under folder f1, we have two bookmarks. + EntryKernel* f1_b1 = MakeBookmark(101, 1, false); + f1_b1->put(PARENT_ID, GetBookmarkId(1)); + EntryKernel* f1_b2 = MakeBookmark(102, 2, false); + f1_b2->put(PARENT_ID, GetBookmarkId(1)); + + // Under folder f2, there is one bookmark. + EntryKernel* f2_b1 = MakeBookmark(201, 1, false); + f2_b1->put(PARENT_ID, GetBookmarkId(2)); + + // Under folder f3, there is nothing. + + // Insert in a strange order, because we can. + index_.Insert(f1_b2); + index_.Insert(f2); + index_.Insert(f2_b1); + index_.Insert(f1); + index_.Insert(f1_b1); + index_.Insert(f3); + + OrderedChildSet::const_iterator it; + + // Iterate over children of the bookmark root. + const OrderedChildSet* top_children = index_.GetChildren(GetBookmarkRootId()); + ASSERT_TRUE(top_children); + ASSERT_EQ(top_children->size(), 3UL); + it = top_children->begin(); + EXPECT_EQ(*it, f1); + it++; + EXPECT_EQ(*it, f2); + it++; + EXPECT_EQ(*it, f3); + it++; + EXPECT_TRUE(it == top_children->end()); + + // Iterate over children of the first folder. + const OrderedChildSet* f1_children = index_.GetChildren(GetBookmarkId(1)); + ASSERT_TRUE(f1_children); + ASSERT_EQ(f1_children->size(), 2UL); + it = f1_children->begin(); + EXPECT_EQ(*it, f1_b1); + it++; + EXPECT_EQ(*it, f1_b2); + it++; + EXPECT_TRUE(it == f1_children->end()); + + // Iterate over children of the second folder. + const OrderedChildSet* f2_children = index_.GetChildren(GetBookmarkId(2)); + ASSERT_TRUE(f2_children); + ASSERT_EQ(f2_children->size(), 1UL); + it = f2_children->begin(); + EXPECT_EQ(*it, f2_b1); + it++; + EXPECT_TRUE(it == f2_children->end()); + + // Check for children of the third folder. + const OrderedChildSet* f3_children = index_.GetChildren(GetBookmarkId(3)); + EXPECT_FALSE(f3_children); +} + +// Tests removing items. +TEST_F(ParentChildIndexTest, RemoveWithHierarchy) { + EntryKernel* bm_folder = MakeBookmarkRoot(); + index_.Insert(bm_folder); + + // Just below the root, we have folders f1 and f2. + EntryKernel* f1 = MakeBookmark(1, 1, false); + EntryKernel* f2 = MakeBookmark(2, 2, false); + EntryKernel* f3 = MakeBookmark(3, 3, false); + + // Under folder f1, we have two bookmarks. + EntryKernel* f1_b1 = MakeBookmark(101, 1, false); + f1_b1->put(PARENT_ID, GetBookmarkId(1)); + EntryKernel* f1_b2 = MakeBookmark(102, 2, false); + f1_b2->put(PARENT_ID, GetBookmarkId(1)); + + // Under folder f2, there is one bookmark. + EntryKernel* f2_b1 = MakeBookmark(201, 1, false); + f2_b1->put(PARENT_ID, GetBookmarkId(2)); + + // Under folder f3, there is nothing. + + // Insert in any order. + index_.Insert(f2_b1); + index_.Insert(f3); + index_.Insert(f1_b2); + index_.Insert(f1); + index_.Insert(f2); + index_.Insert(f1_b1); + + // Check that all are in the index. + EXPECT_TRUE(index_.Contains(f1)); + EXPECT_TRUE(index_.Contains(f2)); + EXPECT_TRUE(index_.Contains(f3)); + EXPECT_TRUE(index_.Contains(f1_b1)); + EXPECT_TRUE(index_.Contains(f1_b2)); + EXPECT_TRUE(index_.Contains(f2_b1)); + + // Remove them all in any order. + index_.Remove(f3); + EXPECT_FALSE(index_.Contains(f3)); + index_.Remove(f1_b2); + EXPECT_FALSE(index_.Contains(f1_b2)); + index_.Remove(f2_b1); + EXPECT_FALSE(index_.Contains(f2_b1)); + index_.Remove(f1); + EXPECT_FALSE(index_.Contains(f1)); + index_.Remove(f2); + EXPECT_FALSE(index_.Contains(f2)); + index_.Remove(f1_b1); + EXPECT_FALSE(index_.Contains(f1_b1)); +} + +// Test that involves two non-ordered items. +TEST_F(ParentChildIndexTest, UnorderedChildren) { + // Make two unique client tag items under the root node. + EntryKernel* u1 = MakeUniqueClientItem(1); + EntryKernel* u2 = MakeUniqueClientItem(2); + + EXPECT_FALSE(u1->ShouldMaintainPosition()); + EXPECT_FALSE(u2->ShouldMaintainPosition()); + + index_.Insert(u1); + index_.Insert(u2); + + const OrderedChildSet* children = index_.GetChildren(syncable::Id()); + EXPECT_EQ(children->count(u1), 1UL); + EXPECT_EQ(children->count(u2), 1UL); + EXPECT_EQ(children->size(), 2UL); +} + +// Test ordered and non-ordered entries under the same parent. +// TODO(rlarocque): We should not need to support this. +TEST_F(ParentChildIndexTest, OrderedAndUnorderedChildren) { + EntryKernel* bm_folder = MakeBookmarkRoot(); + index_.Insert(bm_folder); + + EntryKernel* b1 = MakeBookmark(1, 1, false); + EntryKernel* b2 = MakeBookmark(2, 2, false); + EntryKernel* u1 = MakeUniqueClientItem(1); + u1->put(PARENT_ID, GetBookmarkRootId()); + + index_.Insert(b1); + index_.Insert(u1); + index_.Insert(b2); + + const OrderedChildSet* children = index_.GetChildren(GetBookmarkRootId()); + ASSERT_TRUE(children); + EXPECT_EQ(children->size(), 3UL); + + // Ensure that the non-positionable item is moved to the far right. + OrderedChildSet::const_iterator it = children->begin(); + EXPECT_EQ(*it, b1); + it++; + EXPECT_EQ(*it, b2); + it++; + EXPECT_EQ(*it, u1); + it++; + EXPECT_TRUE(it == children->end()); +} + +} // namespace +} // namespace syncable +} // namespace syncer + diff --git a/sync/syncable/scoped_parent_child_index_updater.cc b/sync/syncable/scoped_parent_child_index_updater.cc new file mode 100644 index 0000000..0dc3e95 --- /dev/null +++ b/sync/syncable/scoped_parent_child_index_updater.cc @@ -0,0 +1,28 @@ +// Copyright (c) 2012 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#include "sync/syncable/scoped_parent_child_index_updater.h" + +#include "sync/syncable/parent_child_index.h" + +namespace syncer { +namespace syncable { + +ScopedParentChildIndexUpdater::ScopedParentChildIndexUpdater( + ScopedKernelLock& proof_of_lock, + EntryKernel* entry, + ParentChildIndex* index) : entry_(entry), index_(index) { + if (ParentChildIndex::ShouldInclude(entry_)) { + index_->Remove(entry_); + } +} + +ScopedParentChildIndexUpdater::~ScopedParentChildIndexUpdater() { + if (ParentChildIndex::ShouldInclude(entry_)) { + index_->Insert(entry_); + } +} + +} // namespace syncer +} // namespace syncable diff --git a/sync/syncable/scoped_parent_child_index_updater.h b/sync/syncable/scoped_parent_child_index_updater.h new file mode 100644 index 0000000..89385feb --- /dev/null +++ b/sync/syncable/scoped_parent_child_index_updater.h @@ -0,0 +1,37 @@ +// Copyright (c) 2012 The Chromium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +#ifndef SYNC_SYNCABLE_PARENT_CHILD_INDEX_UPDATER_H_ +#define SYNC_SYNCABLE_PARENT_CHILD_INDEX_UPDATER_H_ + +#include "base/basictypes.h" +#include "sync/base/sync_export.h" + +namespace syncer { +namespace syncable { + +class ParentChildIndex; +class ScopedKernelLock; +struct EntryKernel; + +// Temporarily removes an item from the ParentChildIndex and re-adds it this +// object goes out of scope. +class ScopedParentChildIndexUpdater { + public: + ScopedParentChildIndexUpdater(ScopedKernelLock& proof_of_lock, + EntryKernel* entry, + ParentChildIndex* index); + ~ScopedParentChildIndexUpdater(); + + private: + EntryKernel* entry_; + ParentChildIndex* index_; + + DISALLOW_COPY_AND_ASSIGN(ScopedParentChildIndexUpdater); +}; + +} // namespace syncer +} // namespace syncable + +#endif // SYNC_SYNCABLE_PARENT_CHILD_INDEX_UPDATER_H_ diff --git a/sync/syncable/syncable_columns.h b/sync/syncable/syncable_columns.h index 6eda058..9d45c74 100644 --- a/sync/syncable/syncable_columns.h +++ b/sync/syncable/syncable_columns.h @@ -37,8 +37,6 @@ static const ColumnSpec g_metas_columns[] = { {"id", "varchar(255) default \"r\""}, {"parent_id", "varchar(255) default \"r\""}, {"server_parent_id", "varchar(255) default \"r\""}, - {"prev_id", "varchar(255) default \"r\""}, - {"next_id", "varchar(255) default \"r\""}, ////////////////////////////////////// // bits {"is_unsynced", "bit default 0"}, @@ -53,14 +51,16 @@ static const ColumnSpec g_metas_columns[] = { {"server_non_unique_name", "varchar(255)"}, {"unique_server_tag", "varchar"}, {"unique_client_tag", "varchar"}, + {"unique_bookmark_tag", "varchar"}, ////////////////////////////////////// // Blobs (serialized protos). {"specifics", "blob"}, {"server_specifics", "blob"}, {"base_server_specifics", "blob"}, ////////////////////////////////////// - // Blobs (ordinals). - {"server_ordinal_in_parent", "blob"}, + // Blobs (positions). + {"server_unique_position", "blob"}, + {"unique_position", "blob"}, }; // At least enforce that there are equal number of column names and fields. diff --git a/sync/syncable/syncable_enum_conversions.cc b/sync/syncable/syncable_enum_conversions.cc index b4425a6..8f27912 100644 --- a/sync/syncable/syncable_enum_conversions.cc +++ b/sync/syncable/syncable_enum_conversions.cc @@ -72,14 +72,12 @@ const char* GetTimeFieldString(TimeField time_field) { } const char* GetIdFieldString(IdField id_field) { - ASSERT_ENUM_BOUNDS(ID, NEXT_ID, + ASSERT_ENUM_BOUNDS(ID, SERVER_PARENT_ID, ID_FIELDS_BEGIN, ID_FIELDS_END - 1); switch (id_field) { ENUM_CASE(ID); ENUM_CASE(PARENT_ID); ENUM_CASE(SERVER_PARENT_ID); - ENUM_CASE(PREV_ID); - ENUM_CASE(NEXT_ID); case ID_FIELDS_END: break; } NOTREACHED(); @@ -122,13 +120,14 @@ const char* GetBitFieldString(BitField bit_field) { } const char* GetStringFieldString(StringField string_field) { - ASSERT_ENUM_BOUNDS(NON_UNIQUE_NAME, UNIQUE_CLIENT_TAG, + ASSERT_ENUM_BOUNDS(NON_UNIQUE_NAME, UNIQUE_BOOKMARK_TAG, STRING_FIELDS_BEGIN, STRING_FIELDS_END - 1); switch (string_field) { ENUM_CASE(NON_UNIQUE_NAME); ENUM_CASE(SERVER_NON_UNIQUE_NAME); ENUM_CASE(UNIQUE_SERVER_TAG); ENUM_CASE(UNIQUE_CLIENT_TAG); + ENUM_CASE(UNIQUE_BOOKMARK_TAG); case STRING_FIELDS_END: break; } NOTREACHED(); @@ -148,12 +147,14 @@ const char* GetProtoFieldString(ProtoField proto_field) { return ""; } -const char* GetOrdinalFieldString(OrdinalField ordinal_field) { - ASSERT_ENUM_BOUNDS(SERVER_ORDINAL_IN_PARENT, SERVER_ORDINAL_IN_PARENT, - ORDINAL_FIELDS_BEGIN, ORDINAL_FIELDS_END - 1); - switch(ordinal_field) { - ENUM_CASE(SERVER_ORDINAL_IN_PARENT); - case ORDINAL_FIELDS_END: break; +const char* GetUniquePositionFieldString(UniquePositionField position_field) { + ASSERT_ENUM_BOUNDS(SERVER_UNIQUE_POSITION, UNIQUE_POSITION, + UNIQUE_POSITION_FIELDS_BEGIN, + UNIQUE_POSITION_FIELDS_END - 1); + switch(position_field) { + ENUM_CASE(SERVER_UNIQUE_POSITION); + ENUM_CASE(UNIQUE_POSITION); + case UNIQUE_POSITION_FIELDS_END: break; } NOTREACHED(); return ""; diff --git a/sync/syncable/syncable_enum_conversions.h b/sync/syncable/syncable_enum_conversions.h index 3727420..12f6428 100644 --- a/sync/syncable/syncable_enum_conversions.h +++ b/sync/syncable/syncable_enum_conversions.h @@ -41,8 +41,8 @@ SYNC_EXPORT_PRIVATE const char* GetStringFieldString(StringField string_field); SYNC_EXPORT_PRIVATE const char* GetProtoFieldString(ProtoField proto_field); -SYNC_EXPORT_PRIVATE const char* GetOrdinalFieldString( - OrdinalField ordinal_field); +SYNC_EXPORT_PRIVATE const char* GetUniquePositionFieldString( + UniquePositionField position_field); SYNC_EXPORT_PRIVATE const char* GetBitTempString(BitTemp bit_temp); diff --git a/sync/syncable/syncable_enum_conversions_unittest.cc b/sync/syncable/syncable_enum_conversions_unittest.cc index eac4a37..f74d130 100644 --- a/sync/syncable/syncable_enum_conversions_unittest.cc +++ b/sync/syncable/syncable_enum_conversions_unittest.cc @@ -77,9 +77,10 @@ TEST_F(SyncableEnumConversionsTest, GetProtoFieldString) { GetProtoFieldString, PROTO_FIELDS_BEGIN, PROTO_FIELDS_END - 1); } -TEST_F(SyncableEnumConversionsTest, GetOrdinalFieldString) { +TEST_F(SyncableEnumConversionsTest, GetUniquePositionFieldString) { TestEnumStringFunction( - GetOrdinalFieldString, ORDINAL_FIELDS_BEGIN, ORDINAL_FIELDS_END - 1); + GetUniquePositionFieldString, + UNIQUE_POSITION_FIELDS_BEGIN, UNIQUE_POSITION_FIELDS_END - 1); } TEST_F(SyncableEnumConversionsTest, GetBitTempString) { diff --git a/sync/syncable/syncable_unittest.cc b/sync/syncable/syncable_unittest.cc index b4772b9..f99ad23 100644 --- a/sync/syncable/syncable_unittest.cc +++ b/sync/syncable/syncable_unittest.cc @@ -19,7 +19,6 @@ #include "base/test/values_test_util.h" #include "base/threading/platform_thread.h" #include "base/values.h" -#include "sync/internal_api/public/base/node_ordinal.h" #include "sync/protocol/bookmark_specifics.pb.h" #include "sync/syncable/directory_backing_store.h" #include "sync/syncable/directory_change_delegate.h" @@ -230,10 +229,10 @@ TEST_F(SyncableGeneralTest, ChildrenOps) { Entry e(&rtrans, GET_BY_ID, id); ASSERT_FALSE(e.good()); // Hasn't been written yet. + Entry root(&rtrans, GET_BY_ID, rtrans.root_id()); + ASSERT_TRUE(root.good()); EXPECT_FALSE(dir.HasChildren(&rtrans, rtrans.root_id())); - Id child_id; - EXPECT_TRUE(dir.GetFirstChildId(&rtrans, rtrans.root_id(), &child_id)); - EXPECT_TRUE(child_id.IsRoot()); + EXPECT_TRUE(root.GetFirstChildId().IsRoot()); } { @@ -254,10 +253,10 @@ TEST_F(SyncableGeneralTest, ChildrenOps) { Entry child(&rtrans, GET_BY_HANDLE, written_metahandle); ASSERT_TRUE(child.good()); + Entry root(&rtrans, GET_BY_ID, rtrans.root_id()); + ASSERT_TRUE(root.good()); EXPECT_TRUE(dir.HasChildren(&rtrans, rtrans.root_id())); - Id child_id; - EXPECT_TRUE(dir.GetFirstChildId(&rtrans, rtrans.root_id(), &child_id)); - EXPECT_EQ(e.Get(ID), child_id); + EXPECT_EQ(e.Get(ID), root.GetFirstChildId()); } { @@ -273,10 +272,10 @@ TEST_F(SyncableGeneralTest, ChildrenOps) { Entry e(&rtrans, GET_BY_ID, id); ASSERT_TRUE(e.good()); + Entry root(&rtrans, GET_BY_ID, rtrans.root_id()); + ASSERT_TRUE(root.good()); EXPECT_FALSE(dir.HasChildren(&rtrans, rtrans.root_id())); - Id child_id; - EXPECT_TRUE(dir.GetFirstChildId(&rtrans, rtrans.root_id(), &child_id)); - EXPECT_TRUE(child_id.IsRoot()); + EXPECT_TRUE(root.GetFirstChildId().IsRoot()); } dir.SaveChanges(); @@ -417,6 +416,32 @@ TEST_F(SyncableGeneralTest, ToValue) { dir.SaveChanges(); } +// Test that the bookmark tag generation algorithm remains unchanged. +TEST_F(SyncableGeneralTest, BookmarkTagTest) { + InMemoryDirectoryBackingStore* store = new InMemoryDirectoryBackingStore("x"); + + // The two inputs that form the bookmark tag are the directory's cache_guid + // and its next_id value. We don't need to take any action to ensure + // consistent next_id values, but we do need to explicitly request that our + // InMemoryDirectoryBackingStore always return the same cache_guid. + store->request_consistent_cache_guid(); + + Directory dir(store, &handler_, NULL, NULL, NULL); + ASSERT_EQ(OPENED, dir.Open("x", &delegate_, NullTransactionObserver())); + + { + WriteTransaction wtrans(FROM_HERE, UNITTEST, &dir); + MutableEntry bm(&wtrans, CREATE, BOOKMARKS, wtrans.root_id(), "bm"); + bm.Put(IS_UNSYNCED, true); + + // If this assertion fails, that might indicate that the algorithm used to + // generate bookmark tags has been modified. This could have implications + // for bookmark ordering. Please make sure you know what you're doing if + // you intend to make such a change. + ASSERT_EQ("6wHRAb3kbnXV5GHrejp4/c1y5tw=", bm.Get(UNIQUE_BOOKMARK_TAG)); + } +} + // A test fixture for syncable::Directory. Uses an in-memory database to keep // the unit tests fast. class SyncableDirectoryTest : public testing::Test { @@ -1496,12 +1521,19 @@ TEST_F(SyncableDirectoryTest, OldClientLeftUnsyncedDeletedLocalItem) { } } -TEST_F(SyncableDirectoryTest, OrdinalWithNullSurvivesSaveAndReload) { +TEST_F(SyncableDirectoryTest, PositionWithNullSurvivesSaveAndReload) { TestIdFactory id_factory; Id null_child_id; const char null_cstr[] = "\0null\0test"; std::string null_str(null_cstr, arraysize(null_cstr) - 1); - NodeOrdinal null_ord = NodeOrdinal(null_str); + // Pad up to the minimum length with 0x7f characters, then add a string that + // contains a few NULLs to the end. This is slightly wrong, since the suffix + // part of a UniquePosition shouldn't contain NULLs, but it's good enough for + // this test. + std::string suffix = + std::string(UniquePosition::kSuffixLength - null_str.length(), '\x7f') + + null_str; + UniquePosition null_pos = UniquePosition::FromInt64(10, suffix); { WriteTransaction trans(FROM_HERE, UNITTEST, dir_.get()); @@ -1512,7 +1544,8 @@ TEST_F(SyncableDirectoryTest, OrdinalWithNullSurvivesSaveAndReload) { MutableEntry child(&trans, CREATE, BOOKMARKS, parent.Get(ID), "child"); child.Put(IS_UNSYNCED, true); - child.Put(SERVER_ORDINAL_IN_PARENT, null_ord); + child.Put(UNIQUE_POSITION, null_pos); + child.Put(SERVER_UNIQUE_POSITION, null_pos); null_child_id = child.Get(ID); } @@ -1524,9 +1557,10 @@ TEST_F(SyncableDirectoryTest, OrdinalWithNullSurvivesSaveAndReload) { Entry null_ordinal_child(&trans, GET_BY_ID, null_child_id); EXPECT_TRUE( - null_ord.Equals(null_ordinal_child.Get(SERVER_ORDINAL_IN_PARENT))); + null_pos.Equals(null_ordinal_child.Get(UNIQUE_POSITION))); + EXPECT_TRUE( + null_pos.Equals(null_ordinal_child.Get(SERVER_UNIQUE_POSITION))); } - } // An OnDirectoryBackingStore that can be set to always fail SaveChanges. @@ -1879,13 +1913,13 @@ TEST_F(OnDiskSyncableDirectoryTest, update_post_save.ref((ProtoField)i).SerializeAsString()) << "Blob field #" << i << " changed during save/load"; } - for ( ; i < ORDINAL_FIELDS_END; ++i) { - EXPECT_EQ(create_pre_save.ref((OrdinalField)i).ToInternalValue(), - create_post_save.ref((OrdinalField)i).ToInternalValue()) - << "Blob field #" << i << " changed during save/load"; - EXPECT_EQ(update_pre_save.ref((OrdinalField)i).ToInternalValue(), - update_post_save.ref((OrdinalField)i).ToInternalValue()) - << "Blob field #" << i << " changed during save/load"; + for ( ; i < UNIQUE_POSITION_FIELDS_END; ++i) { + EXPECT_TRUE(create_pre_save.ref((UniquePositionField)i).Equals( + create_post_save.ref((UniquePositionField)i))) + << "Position field #" << i << " changed during save/load"; + EXPECT_TRUE(update_pre_save.ref((UniquePositionField)i).Equals( + update_post_save.ref((UniquePositionField)i))) + << "Position field #" << i << " changed during save/load"; } } diff --git a/sync/syncable/syncable_util.cc b/sync/syncable/syncable_util.cc index 857fc85..6d7f126 100644 --- a/sync/syncable/syncable_util.cc +++ b/sync/syncable/syncable_util.cc @@ -66,27 +66,13 @@ void ChangeEntryIDAndUpdateChildren( while (i != children.end()) { MutableEntry child_entry(trans, GET_BY_HANDLE, *i++); CHECK(child_entry.good()); - // Use the unchecked setter here to avoid touching the child's NEXT_ID - // and PREV_ID fields (which Put(PARENT_ID) would normally do to - // maintain linked-list invariants). In this case, NEXT_ID and PREV_ID - // among the children will be valid after the loop, since we update all - // the children at once. + // Use the unchecked setter here to avoid touching the child's + // UNIQUE_POSITION field. In this case, UNIQUE_POSITION among the + // children will be valid after the loop, since we update all the children + // at once. child_entry.PutParentIdPropertyOnly(new_id); } } - // Update Id references on the previous and next nodes in the sibling - // order. Do this by reinserting into the linked list; the first - // step in PutPredecessor is to Unlink from the existing order, which - // will overwrite the stale Id value from the adjacent nodes. - if (entry->GetPredecessorId() == entry->GetSuccessorId() && - entry->GetPredecessorId() == old_id) { - // We just need a shallow update to |entry|'s fields since it is already - // self looped. - entry->Put(NEXT_ID, new_id); - entry->Put(PREV_ID, new_id); - } else { - entry->PutPredecessor(entry->GetPredecessorId()); - } } // Function to handle runtime failures on syncable code. Rather than crashing, @@ -119,5 +105,12 @@ std::string GenerateSyncableHash( return encode_output; } +std::string GenerateSyncableBookmarkHash( + const std::string originator_cache_guid, + const std::string originator_client_item_id) { + return syncable::GenerateSyncableHash( + BOOKMARKS, originator_cache_guid + originator_client_item_id); +} + } // namespace syncable } // namespace syncer diff --git a/sync/syncable/syncable_util.h b/sync/syncable/syncable_util.h index 4ea8a6f..465324d 100644 --- a/sync/syncable/syncable_util.h +++ b/sync/syncable/syncable_util.h @@ -44,6 +44,13 @@ SYNC_EXPORT_PRIVATE int GetUnsyncedEntries(BaseTransaction* trans, SYNC_EXPORT_PRIVATE std::string GenerateSyncableHash( ModelType model_type, const std::string& client_tag); +// A helper for generating the bookmark type's tag. This is required in more +// than one place, so we define the algorithm here to make sure the +// implementation is consistent. +SYNC_EXPORT_PRIVATE std::string GenerateSyncableBookmarkHash( + const std::string originator_cache_guid, + const std::string originator_client_item_id); + } // namespace syncable } // namespace syncer diff --git a/sync/test/engine/mock_connection_manager.cc b/sync/test/engine/mock_connection_manager.cc index 3fd4a32..e5fd452 100644 --- a/sync/test/engine/mock_connection_manager.cc +++ b/sync/test/engine/mock_connection_manager.cc @@ -32,6 +32,7 @@ namespace syncer { using syncable::WriteTransaction; static char kValidAuthToken[] = "AuthToken"; +static char kCacheGuid[] = "kqyg7097kro6GSUod+GSg=="; MockConnectionManager::MockConnectionManager(syncable::Directory* directory) : ServerConnectionManager("unused", 0, false), @@ -343,6 +344,19 @@ sync_pb::SyncEntity* MockConnectionManager::AddUpdateMeta( ent->set_mtime(sync_ts); ent->set_ctime(1); ent->set_position_in_parent(GeneratePositionInParent()); + + // This isn't perfect, but it works well enough. This is an update, which + // means the ID is a server ID, which means it never changes. By making + // kCacheGuid also never change, we guarantee that the same item always has + // the same originator_cache_guid and originator_client_item_id. + // + // Unfortunately, neither this class nor the tests that use it explicitly + // track sync entitites, so supporting proper cache guids and client item IDs + // would require major refactoring. The ID used here ought to be the "c-" + // style ID that was sent up on the commit. + ent->set_originator_cache_guid(kCacheGuid); + ent->set_originator_client_item_id(id); + return ent; } @@ -395,9 +409,20 @@ sync_pb::SyncEntity* MockConnectionManager::AddUpdateFromLastCommit() { last_commit_response().entryresponse(0).version()); ent->set_id_string( last_commit_response().entryresponse(0).id_string()); + + // This is the same hack as in AddUpdateMeta. See the comment in that + // function for more information. + ent->set_originator_cache_guid(kCacheGuid); + ent->set_originator_client_item_id( + last_commit_response().entryresponse(0).id_string()); + + if (last_sent_commit().entries(0).has_unique_position()) { + ent->mutable_unique_position()->CopyFrom( + last_sent_commit().entries(0).unique_position()); + } + // Tests don't currently care about the following: - // originator_cache_guid, originator_client_item_id, parent_id_string, - // name, non_unique_name. + // parent_id_string, name, non_unique_name. } return GetMutableLastUpdate(); } diff --git a/sync/test/engine/mock_connection_manager.h b/sync/test/engine/mock_connection_manager.h index 53b950bd..f4f9882 100644 --- a/sync/test/engine/mock_connection_manager.h +++ b/sync/test/engine/mock_connection_manager.h @@ -18,6 +18,7 @@ #include "sync/engine/net/server_connection_manager.h" #include "sync/internal_api/public/base/model_type.h" #include "sync/internal_api/public/base/model_type_invalidation_map.h" +#include "sync/internal_api/public/base/unique_position.h" #include "sync/protocol/sync.pb.h" namespace syncer { diff --git a/sync/test/test_directory_backing_store.h b/sync/test/test_directory_backing_store.h index cbbe16e..54fe49e 100644 --- a/sync/test/test_directory_backing_store.h +++ b/sync/test/test_directory_backing_store.h @@ -48,7 +48,8 @@ class TestDirectoryBackingStore : public DirectoryBackingStore { FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, MigrateVersion82To83); FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, MigrateVersion83To84); FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, MigrateVersion84To85); - FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, DetectInvalidOrdinal); + FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, MigrateVersion85To86); + FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, DetectInvalidPosition); FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, ModelTypeIds); FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, Corruption); FRIEND_TEST_ALL_PREFIXES(DirectoryBackingStoreTest, DeleteEntries); diff --git a/sync/tools/testserver/chromiumsync.py b/sync/tools/testserver/chromiumsync.py index 06dfa40..eecea5c 100644 --- a/sync/tools/testserver/chromiumsync.py +++ b/sync/tools/testserver/chromiumsync.py @@ -630,12 +630,14 @@ class SyncDataModel(object): 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. + Starting in Jan 2013, the client will also send up a unique_position field + which should be saved and returned on subsequent GetUpdates. Args: 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. + assumed to be server IDs. This entry will have its parent_id_string, + position_in_parent and unique_position fields updated; its + insert_after_item_id field will be cleared. parent_id: The ID of the entry intended as the new parent. """ @@ -950,12 +952,14 @@ class SyncDataModel(object): entry = MakeTombstone(entry.id_string) else: # Comments in sync.proto detail how the representation of positional - # 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). + # ordering works. + # + # We've almost fully deprecated the 'insert_after_item_id' field. + # The 'position_in_parent' field is also deprecated, but as of Jan 2013 + # is still in common use. The 'unique_position' field is the latest + # and greatest in positioning technology. + # + # This server supports 'position_in_parent' and 'unique_position'. self._WritePosition(entry, entry.parent_id_string) # Preserve the originator info, which the client is not required to send |