1// Copyright (c) 2013 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/history/delete_directive_handler.h"
6
7#include "base/json/json_writer.h"
8#include "base/rand_util.h"
9#include "base/time/time.h"
10#include "base/values.h"
11#include "chrome/browser/history/history_backend.h"
12#include "chrome/browser/history/history_db_task.h"
13#include "chrome/browser/history/history_service.h"
14#include "sync/api/sync_change.h"
15#include "sync/protocol/history_delete_directive_specifics.pb.h"
16#include "sync/protocol/proto_value_conversions.h"
17#include "sync/protocol/sync.pb.h"
18
19namespace {
20
21std::string RandASCIIString(size_t length) {
22  std::string result;
23  const int kMin = static_cast<int>(' ');
24  const int kMax = static_cast<int>('~');
25  for (size_t i = 0; i < length; ++i)
26    result.push_back(static_cast<char>(base::RandInt(kMin, kMax)));
27  return result;
28}
29
30std::string DeleteDirectiveToString(
31    const sync_pb::HistoryDeleteDirectiveSpecifics& delete_directive) {
32  scoped_ptr<base::DictionaryValue> value(
33      syncer::HistoryDeleteDirectiveSpecificsToValue(delete_directive));
34  std::string str;
35  base::JSONWriter::Write(value.get(), &str);
36  return str;
37}
38
39// Compare time range directives first by start time, then by end time.
40bool TimeRangeLessThan(const syncer::SyncData& data1,
41                       const syncer::SyncData& data2) {
42  const sync_pb::TimeRangeDirective& range1 =
43      data1.GetSpecifics().history_delete_directive().time_range_directive();
44  const sync_pb::TimeRangeDirective& range2 =
45      data2.GetSpecifics().history_delete_directive().time_range_directive();
46  if (range1.start_time_usec() < range2.start_time_usec())
47    return true;
48  if (range1.start_time_usec() > range2.start_time_usec())
49    return false;
50  return range1.end_time_usec() < range2.end_time_usec();
51}
52
53// Converts a Unix timestamp in microseconds to a base::Time value.
54base::Time UnixUsecToTime(int64 usec) {
55  return base::Time::UnixEpoch() + base::TimeDelta::FromMicroseconds(usec);
56}
57
58// Converts a base::Time value to a Unix timestamp in microseconds.
59int64 TimeToUnixUsec(base::Time time) {
60  DCHECK(!time.is_null());
61  return (time - base::Time::UnixEpoch()).InMicroseconds();
62}
63
64// Converts global IDs in |global_id_directive| to times.
65void GetTimesFromGlobalIds(
66    const sync_pb::GlobalIdDirective& global_id_directive,
67    std::set<base::Time> *times) {
68  for (int i = 0; i < global_id_directive.global_id_size(); ++i) {
69    times->insert(
70        base::Time::FromInternalValue(global_id_directive.global_id(i)));
71  }
72}
73
74#if !defined(NDEBUG)
75// Checks that the given delete directive is properly formed.
76void CheckDeleteDirectiveValid(
77    const sync_pb::HistoryDeleteDirectiveSpecifics& delete_directive) {
78  if (delete_directive.has_global_id_directive()) {
79    const sync_pb::GlobalIdDirective& global_id_directive =
80        delete_directive.global_id_directive();
81
82    DCHECK(!delete_directive.has_time_range_directive());
83    DCHECK_NE(global_id_directive.global_id_size(), 0);
84    if (global_id_directive.has_start_time_usec())
85      DCHECK_GE(global_id_directive.start_time_usec(), 0);
86    if (global_id_directive.has_end_time_usec()) {
87      DCHECK_GT(global_id_directive.end_time_usec(), 0);
88
89      if (global_id_directive.has_start_time_usec()) {
90        DCHECK_LE(global_id_directive.start_time_usec(),
91                  global_id_directive.end_time_usec());
92      }
93    }
94
95  } else if (delete_directive.has_time_range_directive()) {
96    const sync_pb::TimeRangeDirective& time_range_directive =
97        delete_directive.time_range_directive();
98
99    DCHECK(!delete_directive.has_global_id_directive());
100    DCHECK(time_range_directive.has_start_time_usec());
101    DCHECK(time_range_directive.has_end_time_usec());
102    DCHECK_GE(time_range_directive.start_time_usec(), 0);
103    DCHECK_GT(time_range_directive.end_time_usec(), 0);
104    DCHECK_GT(time_range_directive.end_time_usec(),
105              time_range_directive.start_time_usec());
106  } else {
107    NOTREACHED() << "Delete directive has no time range or global ID directive";
108  }
109}
110#endif  // !defined(NDEBUG)
111
112}  // anonymous namespace
113
114namespace history {
115
116class DeleteDirectiveHandler::DeleteDirectiveTask : public HistoryDBTask {
117 public:
118  DeleteDirectiveTask(
119      base::WeakPtr<DeleteDirectiveHandler> delete_directive_handler,
120      const syncer::SyncDataList& delete_directive,
121      DeleteDirectiveHandler::PostProcessingAction post_processing_action)
122     : delete_directive_handler_(delete_directive_handler),
123       delete_directives_(delete_directive),
124       post_processing_action_(post_processing_action) {}
125
126  // Implements HistoryDBTask.
127  virtual bool RunOnDBThread(history::HistoryBackend* backend,
128                             history::HistoryDatabase* db) OVERRIDE;
129  virtual void DoneRunOnMainThread() OVERRIDE;
130
131 private:
132  virtual ~DeleteDirectiveTask() {}
133
134  // Process a list of global Id directives. Delete all visits to a URL in
135  // time ranges of directives if the timestamp of one visit matches with one
136  // global id.
137  void ProcessGlobalIdDeleteDirectives(
138      history::HistoryBackend* history_backend,
139      const syncer::SyncDataList& global_id_directives);
140
141  // Process a list of time range directives, all history entries within the
142  // time ranges are deleted. |time_range_directives| should be sorted by
143  // |start_time_usec| and |end_time_usec| already.
144  void ProcessTimeRangeDeleteDirectives(
145      history::HistoryBackend* history_backend,
146      const syncer::SyncDataList& time_range_directives);
147
148  base::WeakPtr<DeleteDirectiveHandler> delete_directive_handler_;
149  syncer::SyncDataList delete_directives_;
150  DeleteDirectiveHandler::PostProcessingAction post_processing_action_;
151};
152
153bool DeleteDirectiveHandler::DeleteDirectiveTask::RunOnDBThread(
154    history::HistoryBackend* backend,
155    history::HistoryDatabase* db) {
156  syncer::SyncDataList global_id_directives;
157  syncer::SyncDataList time_range_directives;
158  for (syncer::SyncDataList::const_iterator it = delete_directives_.begin();
159       it != delete_directives_.end(); ++it) {
160    DCHECK_EQ(it->GetDataType(), syncer::HISTORY_DELETE_DIRECTIVES);
161    const sync_pb::HistoryDeleteDirectiveSpecifics& delete_directive =
162        it->GetSpecifics().history_delete_directive();
163    if (delete_directive.has_global_id_directive()) {
164      global_id_directives.push_back(*it);
165    } else {
166      time_range_directives.push_back(*it);
167    }
168  }
169
170  ProcessGlobalIdDeleteDirectives(backend, global_id_directives);
171  std::sort(time_range_directives.begin(), time_range_directives.end(),
172            TimeRangeLessThan);
173  ProcessTimeRangeDeleteDirectives(backend, time_range_directives);
174  return true;
175}
176
177void DeleteDirectiveHandler::DeleteDirectiveTask::DoneRunOnMainThread() {
178  if (delete_directive_handler_.get()) {
179    delete_directive_handler_->FinishProcessing(post_processing_action_,
180                                                delete_directives_);
181  }
182}
183
184void
185DeleteDirectiveHandler::DeleteDirectiveTask::ProcessGlobalIdDeleteDirectives(
186    history::HistoryBackend* history_backend,
187    const syncer::SyncDataList& global_id_directives) {
188  if (global_id_directives.empty())
189    return;
190
191  // Group times represented by global IDs by time ranges of delete directives.
192  // It's more efficient for backend to process all directives with same time
193  // range at once.
194  typedef std::map<std::pair<base::Time, base::Time>, std::set<base::Time> >
195      GlobalIdTimesGroup;
196  GlobalIdTimesGroup id_times_group;
197  for (size_t i = 0; i < global_id_directives.size(); ++i) {
198    DVLOG(1) << "Processing delete directive: "
199             << DeleteDirectiveToString(
200                    global_id_directives[i].GetSpecifics()
201                        .history_delete_directive());
202
203    const sync_pb::GlobalIdDirective& id_directive =
204        global_id_directives[i].GetSpecifics().history_delete_directive()
205            .global_id_directive();
206    if (id_directive.global_id_size() == 0 ||
207        !id_directive.has_start_time_usec() ||
208        !id_directive.has_end_time_usec()) {
209      DLOG(ERROR) << "Invalid global id directive.";
210      continue;
211    }
212    GetTimesFromGlobalIds(
213        id_directive,
214        &id_times_group[
215            std::make_pair(UnixUsecToTime(id_directive.start_time_usec()),
216                           UnixUsecToTime(id_directive.end_time_usec()))]);
217  }
218
219  if (id_times_group.empty())
220    return;
221
222  // Call backend to expire history of directives in each group.
223  for (GlobalIdTimesGroup::const_iterator group_it = id_times_group.begin();
224      group_it != id_times_group.end(); ++group_it) {
225    // Add 1us to cover history entries visited at the end time because time
226    // range in directive is inclusive.
227    history_backend->ExpireHistoryForTimes(
228        group_it->second,
229        group_it->first.first,
230        group_it->first.second + base::TimeDelta::FromMicroseconds(1));
231  }
232}
233
234void
235DeleteDirectiveHandler::DeleteDirectiveTask::ProcessTimeRangeDeleteDirectives(
236    history::HistoryBackend* history_backend,
237    const syncer::SyncDataList& time_range_directives) {
238  if (time_range_directives.empty())
239    return;
240
241  // Iterate through time range directives. Expire history in combined
242  // time range for multiple directives whose time ranges overlap.
243  base::Time current_start_time;
244  base::Time current_end_time;
245  for (size_t i = 0; i < time_range_directives.size(); ++i) {
246    const sync_pb::HistoryDeleteDirectiveSpecifics& delete_directive =
247        time_range_directives[i].GetSpecifics().history_delete_directive();
248    DVLOG(1) << "Processing time range directive: "
249             << DeleteDirectiveToString(delete_directive);
250
251    const sync_pb::TimeRangeDirective& time_range_directive =
252        delete_directive.time_range_directive();
253    if (!time_range_directive.has_start_time_usec() ||
254        !time_range_directive.has_end_time_usec() ||
255        time_range_directive.start_time_usec() >=
256            time_range_directive.end_time_usec()) {
257      DLOG(ERROR) << "Invalid time range directive.";
258      continue;
259    }
260
261    base::Time directive_start_time =
262        UnixUsecToTime(time_range_directive.start_time_usec());
263    base::Time directive_end_time =
264        UnixUsecToTime(time_range_directive.end_time_usec());
265    if (directive_start_time > current_end_time) {
266      if (!current_start_time.is_null()) {
267        // Add 1us to cover history entries visited at the end time because
268        // time range in directive is inclusive.
269        history_backend->ExpireHistoryBetween(
270            std::set<GURL>(), current_start_time,
271            current_end_time + base::TimeDelta::FromMicroseconds(1));
272      }
273      current_start_time = directive_start_time;
274    }
275    if (directive_end_time > current_end_time)
276      current_end_time = directive_end_time;
277  }
278
279  if (!current_start_time.is_null()) {
280    history_backend->ExpireHistoryBetween(
281        std::set<GURL>(), current_start_time,
282        current_end_time + base::TimeDelta::FromMicroseconds(1));
283  }
284}
285
286DeleteDirectiveHandler::DeleteDirectiveHandler()
287    : weak_ptr_factory_(this) {}
288
289DeleteDirectiveHandler::~DeleteDirectiveHandler() {
290  weak_ptr_factory_.InvalidateWeakPtrs();
291}
292
293void DeleteDirectiveHandler::Start(
294    HistoryService* history_service,
295    const syncer::SyncDataList& initial_sync_data,
296    scoped_ptr<syncer::SyncChangeProcessor> sync_processor) {
297  DCHECK(thread_checker_.CalledOnValidThread());
298  sync_processor_ = sync_processor.Pass();
299  if (!initial_sync_data.empty()) {
300    // Drop processed delete directives during startup.
301    history_service->ScheduleDBTask(
302        new DeleteDirectiveTask(weak_ptr_factory_.GetWeakPtr(),
303                                initial_sync_data,
304                                DROP_AFTER_PROCESSING),
305        &internal_consumer_);
306  }
307}
308
309void DeleteDirectiveHandler::Stop() {
310  DCHECK(thread_checker_.CalledOnValidThread());
311  sync_processor_.reset();
312}
313
314bool DeleteDirectiveHandler::CreateDeleteDirectives(
315    const std::set<int64>& global_ids,
316    base::Time begin_time,
317    base::Time end_time) {
318  base::Time now = base::Time::Now();
319  sync_pb::HistoryDeleteDirectiveSpecifics delete_directive;
320
321  // Delete directives require a non-null begin time, so use 1 if it's null.
322  int64 begin_time_usecs =
323      begin_time.is_null() ? 0 : TimeToUnixUsec(begin_time);
324
325  // Determine the actual end time -- it should not be null or in the future.
326  // TODO(dubroy): Use sane time (crbug.com/146090) here when it's available.
327  base::Time end = (end_time.is_null() || end_time > now) ? now : end_time;
328  // -1 because end time in delete directives is inclusive.
329  int64 end_time_usecs = TimeToUnixUsec(end) - 1;
330
331  if (global_ids.empty()) {
332    sync_pb::TimeRangeDirective* time_range_directive =
333        delete_directive.mutable_time_range_directive();
334    time_range_directive->set_start_time_usec(begin_time_usecs);
335    time_range_directive->set_end_time_usec(end_time_usecs);
336  } else {
337    for (std::set<int64>::const_iterator it = global_ids.begin();
338         it != global_ids.end(); ++it) {
339      sync_pb::GlobalIdDirective* global_id_directive =
340          delete_directive.mutable_global_id_directive();
341      global_id_directive->add_global_id(*it);
342      global_id_directive->set_start_time_usec(begin_time_usecs);
343      global_id_directive->set_end_time_usec(end_time_usecs);
344    }
345  }
346  syncer::SyncError error = ProcessLocalDeleteDirective(delete_directive);
347  return !error.IsSet();
348}
349
350syncer::SyncError DeleteDirectiveHandler::ProcessLocalDeleteDirective(
351    const sync_pb::HistoryDeleteDirectiveSpecifics& delete_directive) {
352  DCHECK(thread_checker_.CalledOnValidThread());
353  if (!sync_processor_) {
354    return syncer::SyncError(
355        FROM_HERE,
356        syncer::SyncError::DATATYPE_ERROR,
357        "Cannot send local delete directive to sync",
358        syncer::HISTORY_DELETE_DIRECTIVES);
359  }
360#if !defined(NDEBUG)
361  CheckDeleteDirectiveValid(delete_directive);
362#endif
363
364  // Generate a random sync tag since history delete directives don't
365  // have a 'built-in' ID.  8 bytes should suffice.
366  std::string sync_tag = RandASCIIString(8);
367  sync_pb::EntitySpecifics entity_specifics;
368  entity_specifics.mutable_history_delete_directive()->CopyFrom(
369      delete_directive);
370  syncer::SyncData sync_data =
371      syncer::SyncData::CreateLocalData(
372          sync_tag, sync_tag, entity_specifics);
373  syncer::SyncChange change(
374      FROM_HERE, syncer::SyncChange::ACTION_ADD, sync_data);
375  syncer::SyncChangeList changes(1, change);
376  return sync_processor_->ProcessSyncChanges(FROM_HERE, changes);
377}
378
379syncer::SyncError DeleteDirectiveHandler::ProcessSyncChanges(
380    HistoryService* history_service,
381    const syncer::SyncChangeList& change_list) {
382  DCHECK(thread_checker_.CalledOnValidThread());
383  if (!sync_processor_) {
384    return syncer::SyncError(
385        FROM_HERE,
386        syncer::SyncError::DATATYPE_ERROR,
387        "Sync is disabled.",
388        syncer::HISTORY_DELETE_DIRECTIVES);
389  }
390
391  syncer::SyncDataList delete_directives;
392  for (syncer::SyncChangeList::const_iterator it = change_list.begin();
393       it != change_list.end(); ++it) {
394    switch (it->change_type()) {
395      case syncer::SyncChange::ACTION_ADD:
396        delete_directives.push_back(it->sync_data());
397        break;
398      case syncer::SyncChange::ACTION_DELETE:
399        // TODO(akalin): Keep track of existing delete directives.
400        break;
401      default:
402        NOTREACHED();
403        break;
404    }
405  }
406
407  if (!delete_directives.empty()) {
408    // Don't drop real-time delete directive so that sync engine can detect
409    // redelivered delete directives to avoid processing them again and again
410    // in one chrome session.
411    history_service->ScheduleDBTask(
412        new DeleteDirectiveTask(weak_ptr_factory_.GetWeakPtr(),
413                                delete_directives, KEEP_AFTER_PROCESSING),
414        &internal_consumer_);
415  }
416  return syncer::SyncError();
417}
418
419void DeleteDirectiveHandler::FinishProcessing(
420    PostProcessingAction post_processing_action,
421    const syncer::SyncDataList& delete_directives) {
422  DCHECK(thread_checker_.CalledOnValidThread());
423
424  // If specified, drop processed delete directive in sync model because they
425  // only need to be applied once.
426  if (sync_processor_.get() &&
427      post_processing_action == DROP_AFTER_PROCESSING) {
428    syncer::SyncChangeList change_list;
429    for (size_t i = 0; i < delete_directives.size(); ++i) {
430      change_list.push_back(
431          syncer::SyncChange(FROM_HERE, syncer::SyncChange::ACTION_DELETE,
432                             delete_directives[i]));
433    }
434    sync_processor_->ProcessSyncChanges(FROM_HERE, change_list);
435  }
436}
437
438}  // namespace history
439