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        scoped_ptr<history::HistoryDBTask>(
303            new DeleteDirectiveTask(weak_ptr_factory_.GetWeakPtr(),
304                                    initial_sync_data,
305                                    DROP_AFTER_PROCESSING)),
306        &internal_tracker_);
307  }
308}
309
310void DeleteDirectiveHandler::Stop() {
311  DCHECK(thread_checker_.CalledOnValidThread());
312  sync_processor_.reset();
313}
314
315bool DeleteDirectiveHandler::CreateDeleteDirectives(
316    const std::set<int64>& global_ids,
317    base::Time begin_time,
318    base::Time end_time) {
319  base::Time now = base::Time::Now();
320  sync_pb::HistoryDeleteDirectiveSpecifics delete_directive;
321
322  // Delete directives require a non-null begin time, so use 1 if it's null.
323  int64 begin_time_usecs =
324      begin_time.is_null() ? 0 : TimeToUnixUsec(begin_time);
325
326  // Determine the actual end time -- it should not be null or in the future.
327  // TODO(dubroy): Use sane time (crbug.com/146090) here when it's available.
328  base::Time end = (end_time.is_null() || end_time > now) ? now : end_time;
329  // -1 because end time in delete directives is inclusive.
330  int64 end_time_usecs = TimeToUnixUsec(end) - 1;
331
332  if (global_ids.empty()) {
333    sync_pb::TimeRangeDirective* time_range_directive =
334        delete_directive.mutable_time_range_directive();
335    time_range_directive->set_start_time_usec(begin_time_usecs);
336    time_range_directive->set_end_time_usec(end_time_usecs);
337  } else {
338    for (std::set<int64>::const_iterator it = global_ids.begin();
339         it != global_ids.end(); ++it) {
340      sync_pb::GlobalIdDirective* global_id_directive =
341          delete_directive.mutable_global_id_directive();
342      global_id_directive->add_global_id(*it);
343      global_id_directive->set_start_time_usec(begin_time_usecs);
344      global_id_directive->set_end_time_usec(end_time_usecs);
345    }
346  }
347  syncer::SyncError error = ProcessLocalDeleteDirective(delete_directive);
348  return !error.IsSet();
349}
350
351syncer::SyncError DeleteDirectiveHandler::ProcessLocalDeleteDirective(
352    const sync_pb::HistoryDeleteDirectiveSpecifics& delete_directive) {
353  DCHECK(thread_checker_.CalledOnValidThread());
354  if (!sync_processor_) {
355    return syncer::SyncError(
356        FROM_HERE,
357        syncer::SyncError::DATATYPE_ERROR,
358        "Cannot send local delete directive to sync",
359        syncer::HISTORY_DELETE_DIRECTIVES);
360  }
361#if !defined(NDEBUG)
362  CheckDeleteDirectiveValid(delete_directive);
363#endif
364
365  // Generate a random sync tag since history delete directives don't
366  // have a 'built-in' ID.  8 bytes should suffice.
367  std::string sync_tag = RandASCIIString(8);
368  sync_pb::EntitySpecifics entity_specifics;
369  entity_specifics.mutable_history_delete_directive()->CopyFrom(
370      delete_directive);
371  syncer::SyncData sync_data =
372      syncer::SyncData::CreateLocalData(
373          sync_tag, sync_tag, entity_specifics);
374  syncer::SyncChange change(
375      FROM_HERE, syncer::SyncChange::ACTION_ADD, sync_data);
376  syncer::SyncChangeList changes(1, change);
377  return sync_processor_->ProcessSyncChanges(FROM_HERE, changes);
378}
379
380syncer::SyncError DeleteDirectiveHandler::ProcessSyncChanges(
381    HistoryService* history_service,
382    const syncer::SyncChangeList& change_list) {
383  DCHECK(thread_checker_.CalledOnValidThread());
384  if (!sync_processor_) {
385    return syncer::SyncError(
386        FROM_HERE,
387        syncer::SyncError::DATATYPE_ERROR,
388        "Sync is disabled.",
389        syncer::HISTORY_DELETE_DIRECTIVES);
390  }
391
392  syncer::SyncDataList delete_directives;
393  for (syncer::SyncChangeList::const_iterator it = change_list.begin();
394       it != change_list.end(); ++it) {
395    switch (it->change_type()) {
396      case syncer::SyncChange::ACTION_ADD:
397        delete_directives.push_back(it->sync_data());
398        break;
399      case syncer::SyncChange::ACTION_DELETE:
400        // TODO(akalin): Keep track of existing delete directives.
401        break;
402      default:
403        NOTREACHED();
404        break;
405    }
406  }
407
408  if (!delete_directives.empty()) {
409    // Don't drop real-time delete directive so that sync engine can detect
410    // redelivered delete directives to avoid processing them again and again
411    // in one chrome session.
412    history_service->ScheduleDBTask(
413        scoped_ptr<history::HistoryDBTask>(
414            new DeleteDirectiveTask(weak_ptr_factory_.GetWeakPtr(),
415                                    delete_directives,
416                                    KEEP_AFTER_PROCESSING)),
417        &internal_tracker_);
418  }
419  return syncer::SyncError();
420}
421
422void DeleteDirectiveHandler::FinishProcessing(
423    PostProcessingAction post_processing_action,
424    const syncer::SyncDataList& delete_directives) {
425  DCHECK(thread_checker_.CalledOnValidThread());
426
427  // If specified, drop processed delete directive in sync model because they
428  // only need to be applied once.
429  if (sync_processor_.get() &&
430      post_processing_action == DROP_AFTER_PROCESSING) {
431    syncer::SyncChangeList change_list;
432    for (size_t i = 0; i < delete_directives.size(); ++i) {
433      change_list.push_back(
434          syncer::SyncChange(FROM_HERE, syncer::SyncChange::ACTION_DELETE,
435                             delete_directives[i]));
436    }
437    sync_processor_->ProcessSyncChanges(FROM_HERE, change_list);
438  }
439}
440
441}  // namespace history
442