1// Copyright 2012 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 "sync/engine/update_applicator.h"
6
7#include <vector>
8
9#include "base/logging.h"
10#include "sync/engine/syncer_util.h"
11#include "sync/syncable/entry.h"
12#include "sync/syncable/mutable_entry.h"
13#include "sync/syncable/syncable_id.h"
14#include "sync/syncable/syncable_write_transaction.h"
15
16using std::vector;
17
18namespace syncer {
19
20using syncable::ID;
21
22UpdateApplicator::UpdateApplicator(Cryptographer* cryptographer,
23                                   const ModelSafeRoutingInfo& routes,
24                                   ModelSafeGroup group_filter)
25    : cryptographer_(cryptographer),
26      group_filter_(group_filter),
27      routing_info_(routes),
28      updates_applied_(0),
29      encryption_conflicts_(0),
30      hierarchy_conflicts_(0) {
31}
32
33UpdateApplicator::~UpdateApplicator() {
34}
35
36// Attempt to apply all updates, using multiple passes if necessary.
37//
38// Some updates must be applied in order.  For example, children must be created
39// after their parent folder is created.  This function runs an O(n^2) algorithm
40// that will keep trying until there is nothing left to apply, or it stops
41// making progress, which would indicate that the hierarchy is invalid.
42//
43// The update applicator also has to deal with simple conflicts, which occur
44// when an item is modified on both the server and the local model.  We remember
45// their IDs so they can be passed to the conflict resolver after all the other
46// applications are complete.
47//
48// Finally, there are encryption conflicts, which can occur when we don't have
49// access to all the Nigori keys.  There's nothing we can do about them here.
50void UpdateApplicator::AttemptApplications(
51    syncable::WriteTransaction* trans,
52    const std::vector<int64>& handles) {
53  std::vector<int64> to_apply = handles;
54
55  DVLOG(1) << "UpdateApplicator running over " << to_apply.size() << " items.";
56  while (!to_apply.empty()) {
57    std::vector<int64> to_reapply;
58
59    for (std::vector<int64>::iterator i = to_apply.begin();
60         i != to_apply.end(); ++i) {
61      syncable::Entry read_entry(trans, syncable::GET_BY_HANDLE, *i);
62      if (SkipUpdate(read_entry)) {
63        continue;
64      }
65
66      syncable::MutableEntry entry(trans, syncable::GET_BY_HANDLE, *i);
67      UpdateAttemptResponse result = AttemptToUpdateEntry(
68          trans, &entry, cryptographer_);
69
70      switch (result) {
71        case SUCCESS:
72          updates_applied_++;
73          break;
74        case CONFLICT_SIMPLE:
75          simple_conflict_ids_.insert(entry.Get(ID));
76          break;
77        case CONFLICT_ENCRYPTION:
78          encryption_conflicts_++;
79          break;
80        case CONFLICT_HIERARCHY:
81          // The decision to classify these as hierarchy conflcits is tentative.
82          // If we make any progress this round, we'll clear the hierarchy
83          // conflict count and attempt to reapply these updates.
84          to_reapply.push_back(*i);
85          break;
86        default:
87          NOTREACHED();
88          break;
89      }
90    }
91
92    if (to_reapply.size() == to_apply.size()) {
93      // We made no progress.  Must be stubborn hierarchy conflicts.
94      hierarchy_conflicts_ = to_apply.size();
95      break;
96    }
97
98    // We made some progress, so prepare for what might be another iteration.
99    // If everything went well, to_reapply will be empty and we'll break out on
100    // the while condition.
101    to_apply.swap(to_reapply);
102    to_reapply.clear();
103  }
104}
105
106bool UpdateApplicator::SkipUpdate(const syncable::Entry& entry) {
107  ModelType type = entry.GetServerModelType();
108  ModelSafeGroup g = GetGroupForModelType(type, routing_info_);
109  // The set of updates passed to the UpdateApplicator should already
110  // be group-filtered.
111  if (g != group_filter_) {
112    NOTREACHED();
113    return true;
114  }
115  if (g == GROUP_PASSIVE &&
116      !routing_info_.count(type) &&
117      type != UNSPECIFIED &&
118      type != TOP_LEVEL_FOLDER) {
119    DVLOG(1) << "Skipping update application, type not permitted.";
120    return true;
121  }
122  return false;
123}
124
125}  // namespace syncer
126