1// Copyright (c) 2010 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "chrome/browser/sync/engine/get_commit_ids_command.h"
6
7#include <set>
8#include <utility>
9#include <vector>
10
11#include "chrome/browser/sync/engine/syncer_util.h"
12#include "chrome/browser/sync/syncable/syncable.h"
13
14using std::set;
15using std::vector;
16
17namespace browser_sync {
18
19using sessions::OrderedCommitSet;
20using sessions::SyncSession;
21using sessions::StatusController;
22
23GetCommitIdsCommand::GetCommitIdsCommand(int commit_batch_size)
24    : requested_commit_batch_size_(commit_batch_size) {}
25
26GetCommitIdsCommand::~GetCommitIdsCommand() {}
27
28void GetCommitIdsCommand::ExecuteImpl(SyncSession* session) {
29  // Gather the full set of unsynced items and store it in the session. They
30  // are not in the correct order for commit.
31  syncable::Directory::UnsyncedMetaHandles all_unsynced_handles;
32  SyncerUtil::GetUnsyncedEntries(session->write_transaction(),
33                                 &all_unsynced_handles);
34  StatusController* status = session->status_controller();
35  status->set_unsynced_handles(all_unsynced_handles);
36
37  BuildCommitIds(status->unsynced_handles(), session->write_transaction(),
38                 session->routing_info());
39
40  const vector<syncable::Id>& verified_commit_ids =
41      ordered_commit_set_->GetAllCommitIds();
42
43  for (size_t i = 0; i < verified_commit_ids.size(); i++)
44    VLOG(1) << "Debug commit batch result:" << verified_commit_ids[i];
45
46  status->set_commit_set(*ordered_commit_set_.get());
47}
48
49void GetCommitIdsCommand::AddUncommittedParentsAndTheirPredecessors(
50    syncable::BaseTransaction* trans,
51    syncable::Id parent_id,
52    const ModelSafeRoutingInfo& routes) {
53  using namespace syncable;
54  OrderedCommitSet item_dependencies(routes);
55
56  // Climb the tree adding entries leaf -> root.
57  while (!parent_id.ServerKnows()) {
58    Entry parent(trans, GET_BY_ID, parent_id);
59    CHECK(parent.good()) << "Bad user-only parent in item path.";
60    int64 handle = parent.Get(META_HANDLE);
61    if (ordered_commit_set_->HaveCommitItem(handle) ||
62        item_dependencies.HaveCommitItem(handle)) {
63      break;
64    }
65    if (!AddItemThenPredecessors(trans, &parent, IS_UNSYNCED,
66                                 &item_dependencies)) {
67      break;  // Parent was already present in the set.
68    }
69    parent_id = parent.Get(PARENT_ID);
70  }
71
72  // Reverse what we added to get the correct order.
73  ordered_commit_set_->AppendReverse(item_dependencies);
74}
75
76bool GetCommitIdsCommand::AddItem(syncable::Entry* item,
77                                  OrderedCommitSet* result) {
78  int64 item_handle = item->Get(syncable::META_HANDLE);
79  if (result->HaveCommitItem(item_handle) ||
80      ordered_commit_set_->HaveCommitItem(item_handle)) {
81    return false;
82  }
83  result->AddCommitItem(item_handle, item->Get(syncable::ID),
84                        item->GetModelType());
85  return true;
86}
87
88bool GetCommitIdsCommand::AddItemThenPredecessors(
89    syncable::BaseTransaction* trans,
90    syncable::Entry* item,
91    syncable::IndexedBitField inclusion_filter,
92    OrderedCommitSet* result) {
93  if (!AddItem(item, result))
94    return false;
95  if (item->Get(syncable::IS_DEL))
96    return true;  // Deleted items have no predecessors.
97
98  syncable::Id prev_id = item->Get(syncable::PREV_ID);
99  while (!prev_id.IsRoot()) {
100    syncable::Entry prev(trans, syncable::GET_BY_ID, prev_id);
101    CHECK(prev.good()) << "Bad id when walking predecessors.";
102    if (!prev.Get(inclusion_filter))
103      break;
104    if (!AddItem(&prev, result))
105      break;
106    prev_id = prev.Get(syncable::PREV_ID);
107  }
108  return true;
109}
110
111void GetCommitIdsCommand::AddPredecessorsThenItem(
112    syncable::BaseTransaction* trans,
113    syncable::Entry* item,
114    syncable::IndexedBitField inclusion_filter,
115    const ModelSafeRoutingInfo& routes) {
116  OrderedCommitSet item_dependencies(routes);
117  AddItemThenPredecessors(trans, item, inclusion_filter, &item_dependencies);
118
119  // Reverse what we added to get the correct order.
120  ordered_commit_set_->AppendReverse(item_dependencies);
121}
122
123bool GetCommitIdsCommand::IsCommitBatchFull() {
124  return ordered_commit_set_->Size() >= requested_commit_batch_size_;
125}
126
127void GetCommitIdsCommand::AddCreatesAndMoves(
128    const vector<int64>& unsynced_handles,
129    syncable::WriteTransaction* write_transaction,
130    const ModelSafeRoutingInfo& routes) {
131  // Add moves and creates, and prepend their uncommitted parents.
132  for (CommitMetahandleIterator iterator(unsynced_handles, write_transaction,
133                                         ordered_commit_set_.get());
134       !IsCommitBatchFull() && iterator.Valid();
135       iterator.Increment()) {
136    int64 metahandle = iterator.Current();
137
138    syncable::Entry entry(write_transaction,
139                          syncable::GET_BY_HANDLE,
140                          metahandle);
141    if (!entry.Get(syncable::IS_DEL)) {
142      AddUncommittedParentsAndTheirPredecessors(write_transaction,
143          entry.Get(syncable::PARENT_ID), routes);
144      AddPredecessorsThenItem(write_transaction, &entry,
145          syncable::IS_UNSYNCED, routes);
146    }
147  }
148
149  // It's possible that we overcommitted while trying to expand dependent
150  // items.  If so, truncate the set down to the allowed size.
151  ordered_commit_set_->Truncate(requested_commit_batch_size_);
152}
153
154void GetCommitIdsCommand::AddDeletes(const vector<int64>& unsynced_handles,
155    syncable::WriteTransaction* write_transaction) {
156  set<syncable::Id> legal_delete_parents;
157
158  for (CommitMetahandleIterator iterator(unsynced_handles, write_transaction,
159                                         ordered_commit_set_.get());
160       !IsCommitBatchFull() && iterator.Valid();
161       iterator.Increment()) {
162    int64 metahandle = iterator.Current();
163
164    syncable::Entry entry(write_transaction, syncable::GET_BY_HANDLE,
165                          metahandle);
166
167    if (entry.Get(syncable::IS_DEL)) {
168      syncable::Entry parent(write_transaction, syncable::GET_BY_ID,
169                             entry.Get(syncable::PARENT_ID));
170      // If the parent is deleted and unsynced, then any children of that
171      // parent don't need to be added to the delete queue.
172      //
173      // Note: the parent could be synced if there was an update deleting a
174      // folder when we had a deleted all items in it.
175      // We may get more updates, or we may want to delete the entry.
176      if (parent.good() &&
177          parent.Get(syncable::IS_DEL) &&
178          parent.Get(syncable::IS_UNSYNCED)) {
179        // However, if an entry is moved, these rules can apply differently.
180        //
181        // If the entry was moved, then the destination parent was deleted,
182        // then we'll miss it in the roll up. We have to add it in manually.
183        // TODO(chron): Unit test for move / delete cases:
184        // Case 1: Locally moved, then parent deleted
185        // Case 2: Server moved, then locally issue recursive delete.
186        if (entry.Get(syncable::ID).ServerKnows() &&
187            entry.Get(syncable::PARENT_ID) !=
188                entry.Get(syncable::SERVER_PARENT_ID)) {
189          VLOG(1) << "Inserting moved and deleted entry, will be missed by "
190                     "delete roll." << entry.Get(syncable::ID);
191
192          ordered_commit_set_->AddCommitItem(metahandle,
193              entry.Get(syncable::ID),
194              entry.GetModelType());
195        }
196
197        // Skip this entry since it's a child of a parent that will be
198        // deleted. The server will unroll the delete and delete the
199        // child as well.
200        continue;
201      }
202
203      legal_delete_parents.insert(entry.Get(syncable::PARENT_ID));
204    }
205  }
206
207  // We could store all the potential entries with a particular parent during
208  // the above scan, but instead we rescan here. This is less efficient, but
209  // we're dropping memory alloc/dealloc in favor of linear scans of recently
210  // examined entries.
211  //
212  // Scan through the UnsyncedMetaHandles again. If we have a deleted
213  // entry, then check if the parent is in legal_delete_parents.
214  //
215  // Parent being in legal_delete_parents means for the child:
216  //   a recursive delete is not currently happening (no recent deletes in same
217  //     folder)
218  //   parent did expect at least one old deleted child
219  //   parent was not deleted
220
221  for (CommitMetahandleIterator iterator(unsynced_handles, write_transaction,
222                                         ordered_commit_set_.get());
223      !IsCommitBatchFull() && iterator.Valid();
224      iterator.Increment()) {
225    int64 metahandle = iterator.Current();
226    syncable::MutableEntry entry(write_transaction, syncable::GET_BY_HANDLE,
227                                 metahandle);
228    if (entry.Get(syncable::IS_DEL)) {
229      syncable::Id parent_id = entry.Get(syncable::PARENT_ID);
230      if (legal_delete_parents.count(parent_id)) {
231        ordered_commit_set_->AddCommitItem(metahandle, entry.Get(syncable::ID),
232            entry.GetModelType());
233      }
234    }
235  }
236}
237
238void GetCommitIdsCommand::BuildCommitIds(const vector<int64>& unsynced_handles,
239    syncable::WriteTransaction* write_transaction,
240    const ModelSafeRoutingInfo& routes) {
241  ordered_commit_set_.reset(new OrderedCommitSet(routes));
242  // Commits follow these rules:
243  // 1. Moves or creates are preceded by needed folder creates, from
244  //    root to leaf.  For folders whose contents are ordered, moves
245  //    and creates appear in order.
246  // 2. Moves/Creates before deletes.
247  // 3. Deletes, collapsed.
248  // We commit deleted moves under deleted items as moves when collapsing
249  // delete trees.
250
251  // Add moves and creates, and prepend their uncommitted parents.
252  AddCreatesAndMoves(unsynced_handles, write_transaction, routes);
253
254  // Add all deletes.
255  AddDeletes(unsynced_handles, write_transaction);
256}
257
258}  // namespace browser_sync
259