DownloadQuery filters and sorts DownloadItems.

content/browser/download/download_query.cc

+// Copyright (c) 2011 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 "content/browser/download/download_query.h"
+
+#include <algorithm>
+#include <set>
+#include <string>
+#include <vector>
+
+#include "base/bind.h"
+#include "base/callback.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/stl_util.h"
+#include "base/string16.h"
+#include "base/string_split.h"
+#include "base/time.h"
+#include "base/utf_string_conversions.h"
+#include "content/browser/download/download_item.h"
+#include "googleurl/src/gurl.h"
+#include "unicode/regex.h"
+
+namespace {
+
+// The next several functions are helpers for making Callbacks that access
+// DownloadItem fields.
+
+static bool MatchesQuery(const string16& value, const DownloadItem& item) {
+  return item.MatchesQuery(value);
+}
+
+static int GetStartTime(const DownloadItem& item) {
+  return (item.GetStartTime() - base::Time::UnixEpoch()).InMilliseconds();
+}
+
+static bool GetDangerAccepted(const DownloadItem& item) {
+  return (item.GetSafetyState() == DownloadItem::DANGEROUS_BUT_VALIDATED);
+}
+
+static string16 GetFilename(const DownloadItem& item) {
+  // This filename will be compared with strings that could be passed in by the
+  // user, who only sees LossyDisplayNames.
+  return item.GetFullPath().LossyDisplayName();
+}
+
+static std::string GetFilenameUTF8(const DownloadItem& item) {
+  return UTF16ToUTF8(GetFilename(item));
+}
+
+static std::string GetUrl(const DownloadItem& item) {
+  return item.GetOriginalUrl().spec();
+}
+
+static DownloadItem::DownloadState GetState(const DownloadItem& item) {
+  return item.GetState();
+}
+
+static DownloadStateInfo::DangerType GetDangerType(const DownloadItem& item) {
+  return item.GetDangerType();
+}
+
+static int GetReceivedBytes(const DownloadItem& item) {
+  return item.GetReceivedBytes();
+}
+
+static int GetTotalBytes(const DownloadItem& item) {
+  return item.GetTotalBytes();
+}
+
+static std::string GetMimeType(const DownloadItem& item) {
+  return item.GetMimeType();
+}
+
+static bool IsPaused(const DownloadItem& item) {
+  return item.IsPaused();
+}
+
+// Wrap Callback to work around a bug in base::Bind/Callback where the inner
+// callback is nullified when the outer callback is Run.
+template<typename ValueType>
+class InnerCallback {
+ public:
+  typedef base::Callback<ValueType(const DownloadItem&)> CallbackType;
+
+  explicit InnerCallback(const CallbackType& inner) : inner_(inner) {}
+  ~InnerCallback() {}
+
+  // Mimic Callback's interface to facilitate removing InnerCallback when the
+  // bug is fixed.
+  ValueType Run(const DownloadItem& item) const { return inner_.Run(item); }
+
+ private:
+  CallbackType inner_;
+};
+
+enum ComparisonType {LT, EQ, GT};
+
+// Returns true if |item| matches the filter specified by |value|, |cmptype|,
+// and |accessor|. |accessor| is conceptually a function that takes a
+// DownloadItem and returns one of its fields, which is then compared to
+// |value|.
+template<typename ValueType>
+static bool FieldMatches(
+    const ValueType& value,
+    ComparisonType cmptype,
+    const InnerCallback<ValueType>& accessor,
+    const DownloadItem& item) {
+  switch (cmptype) {
+    case LT: return accessor.Run(item) < value;
+    case EQ: return accessor.Run(item) == value;
+    case GT: return accessor.Run(item) > value;
+  }
+  NOTREACHED();
+  return false;
+}
+
+// Returns true if |accessor.Run(item)| matches |pattern|.
+static bool FindRegex(
+    icu::RegexPattern* pattern,
+    const InnerCallback<std::string>& accessor,
+    const DownloadItem& item) {
+  icu::UnicodeString input(accessor.Run(item).c_str());
+  UErrorCode status = U_ZERO_ERROR;
+  scoped_ptr<icu::RegexMatcher> matcher(pattern->matcher(input, status));
+  return matcher->find();
+}
+
+// Returns a ComparisonType to indicate whether a field in |left| is less than,
+// greater than or equal to the same field in |right|.
+template<typename ValueType>
+static ComparisonType Compare(
+    const InnerCallback<ValueType>& accessor,
+    const DownloadItem& left, const DownloadItem& right) {
+  ValueType left_value = accessor.Run(left);
+  ValueType right_value = accessor.Run(right);
+  if (left_value > right_value) return GT;

[cbentzel, 2011/12/05 21:56:26]

Do you need to return GT/LT/EQ? Could you just return bool and do the LT
operator like sort functors? 

[benjhayden, 2011/12/09 19:29:15]

Yes to the first, no to the second. :-)
Compare() is called per sort field by the DownloadComparator (which is the sort
functor) in the context of possibly several other sort fields. There are two
bits of information that Compare() returns to the Comparator: whether this
(accessor) sort field of these two items is different, and if they're different,
whether the left is less than or greater than the right. If the two items are
equivalent, then the Comparator continues comparing other sort fields; if
they're different, then it returns true or false (depending on the sort field's
direction) regardless of subsequent sort fields.
I could make Compare() return a different enum {KEEP_GOING, RETURN_TRUE,
RETURN_FALSE}, but it reduces to ComparisonType.

+  if (left_value < right_value) return LT;
+  DCHECK_EQ(left_value, right_value);
+  return EQ;
+}
+
+}  // anonymous namespace
+
+DownloadQuery::DownloadQuery()
+  : limit_(kuint32max) {
+}
+
+DownloadQuery::~DownloadQuery() {
+}
+
+// Filter() pushes a new FilterType to filter_fields_. Most FilterTypes are
+// Callbacks to FieldMatches<>(). Search() iterates over given DownloadItems,
+// discarding items for which any filter returns false. A DownloadQuery may have
+// zero or more FilterTypes.
+
+void DownloadQuery::Filter(const DownloadQuery::FilterType& value) {
+  filter_fields_.push_back(value);
+}
+
+void DownloadQuery::Filter(DownloadItem::DownloadState state) {
+  filter_fields_.push_back(base::Bind(
+        &FieldMatches<DownloadItem::DownloadState>,
+        state,
+        EQ,
+        InnerCallback<DownloadItem::DownloadState>(base::Bind(&GetState))));
+}
+
+void DownloadQuery::Filter(DownloadStateInfo::DangerType danger) {
+  filter_fields_.push_back(base::Bind(
+        &FieldMatches<DownloadStateInfo::DangerType>,
+        danger,
+        EQ,
+        InnerCallback<DownloadStateInfo::DangerType>(base::Bind(
+            &GetDangerType))));
+}
+
+bool DownloadQuery::Filter(DownloadQuery::FilterFieldName name, int value) {
+  switch (static_cast<int>(name)) {
+    case FILTER_FIELD_START_TIME:
+      Filter(base::Bind(&FieldMatches<int>, value, EQ,
+                        InnerCallback<int>(base::Bind(&GetStartTime))));
+      return true;
+    case FILTER_FIELD_STARTED_BEFORE:
+      Filter(base::Bind(&FieldMatches<int>, value, LT,
+                        InnerCallback<int>(base::Bind(&GetStartTime))));
+      return true;
+    case FILTER_FIELD_STARTED_AFTER:
+      Filter(base::Bind(&FieldMatches<int>, value, GT,
+                        InnerCallback<int>(base::Bind(&GetStartTime))));
+      return true;
+    case FILTER_FIELD_BYTES_RECEIVED:
+      Filter(base::Bind(&FieldMatches<int>, value, EQ,
+                        InnerCallback<int>(base::Bind(&GetReceivedBytes))));
+      return true;
+    case FILTER_FIELD_TOTAL_BYTES:
+      Filter(base::Bind(&FieldMatches<int>, value, EQ,
+                        InnerCallback<int>(base::Bind(&GetTotalBytes))));
+      return true;
+    case FILTER_FIELD_TOTAL_BYTES_GREATER:

[cbentzel, 2011/12/05 21:56:26]

Should bytes filter fields be size_t or check >= 0?

[benjhayden, 2011/12/09 19:29:15]

If we're allowing users to specify conflicting filters, I'd rather also allow
them to specify singular filters that filter out nothing or everything instead
of risking forgetting to prevent the check at the caller and documenting the
explosiveness.

+      Filter(base::Bind(&FieldMatches<int>, value, GT,
+                        InnerCallback<int>(base::Bind(&GetTotalBytes))));
+      return true;
+    case FILTER_FIELD_TOTAL_BYTES_LESS:
+      Filter(base::Bind(&FieldMatches<int>, value, LT,
+                        InnerCallback<int>(base::Bind(&GetTotalBytes))));
+      return true;
+  }
+  return false;
+}
+
+bool DownloadQuery::Filter(DownloadQuery::FilterFieldName name, bool value) {
+  switch (static_cast<int>(name)) {
+    case FILTER_FIELD_DANGER_ACCEPTED:
+      Filter(base::Bind(&FieldMatches<bool>, value, EQ,
+                        InnerCallback<bool>(base::Bind(&GetDangerAccepted))));
+      return true;
+    case FILTER_FIELD_PAUSED:
+      Filter(base::Bind(&FieldMatches<bool>, value, EQ,
+                        InnerCallback<bool>(base::Bind(&IsPaused))));
+      return true;
+  }
+  return false;
+}
+
+bool DownloadQuery::FilterRegex(
+    const std::string& regex_str,
+    const InnerCallback<std::string>::CallbackType& accessor) {
+  UParseError re_err;
+  UErrorCode re_status = U_ZERO_ERROR;
+  scoped_ptr<icu::RegexPattern> pattern(icu::RegexPattern::compile(
+      icu::UnicodeString::fromUTF8(regex_str), re_err, re_status));
+  if (!U_SUCCESS(re_status)) return false;
+  Filter(base::Bind(&FindRegex, base::Owned(pattern.release()),
+                    InnerCallback<std::string>(accessor)));
+  return true;
+}
+
+bool DownloadQuery::Filter(
+    DownloadQuery::FilterFieldName name, const std::string& value) {
+  switch (static_cast<int>(name)) {
+    case FILTER_FIELD_MIME:
+      Filter(base::Bind(&FieldMatches<std::string>, value, EQ,
+                        InnerCallback<std::string>(base::Bind(&GetMimeType))));
+      return true;
+    case FILTER_FIELD_URL:
+      Filter(base::Bind(&FieldMatches<std::string>, value, EQ,
+                        InnerCallback<std::string>(base::Bind(&GetUrl))));
+      return true;
+    case FILTER_FIELD_URL_REGEX:
+      return FilterRegex(value, base::Bind(&GetUrl));
+  }
+  return false;
+}
+
+bool DownloadQuery::Filter(
+    DownloadQuery::FilterFieldName name, const string16& value) {
+  switch (static_cast<int>(name)) {
+    case FILTER_FIELD_QUERY:
+      Filter(base::Bind(&MatchesQuery, value));
+      return true;
+    case FILTER_FIELD_FILENAME:
+      Filter(base::Bind(&FieldMatches<string16>, value, EQ,
+                        InnerCallback<string16>(base::Bind(&GetFilename))));
+      return true;
+    case FILTER_FIELD_FILENAME_REGEX:
+      return FilterRegex(UTF16ToUTF8(value), base::Bind(&GetFilenameUTF8));
+  }
+  return false;
+}
+
+bool DownloadQuery::Matches(const DownloadItem& item) const {
+  for (FilterFieldVector::const_iterator filter = filter_fields_.begin();
+        filter != filter_fields_.end(); ++filter) {
+    if (!filter->Run(item))
+      return false;
+  }
+  return true;
+}
+
+// Sort() creates a SortField and pushes it onto sort_fields_. A SortField is a
+// direction and a Callback to Compare<>(). After filtering, Search() makes a
+// DownloadComparator functor from the sort_fields_ and passes the
+// DownloadComparator to std::partial_sort. std::partial_sort calls the
+// DownloadComparator with different pairs of DownloadItems.  DownloadComparator
+// iterates over the sort fields until a callback returns ComparisonType LT or
+// GT.  DownloadComparator returns true or false depending on that
+// ComparisonType and the sort field's direction in order to indicate to
+// std::partial_sort whether the left item is after or before the right item. If
+// all sort fields return EQ, then DownloadComparator compares GetId or
+// GetDbHandle. A DownloadQuery may have zero or more SortFields, but there is
+// one DownloadComparator per call to Search().
+
+struct DownloadQuery::SortField {
+  typedef base::Callback<ComparisonType(
+      const DownloadItem&, const DownloadItem&)> SortType;
+
+  SortField(DownloadQuery::SortFieldDirection adirection,
+            const SortType& asorter)
+    : direction(adirection),
+      sorter(asorter) {
+  }
+  ~SortField() {}
+
+  DownloadQuery::SortFieldDirection direction;
+  SortType sorter;
+};
+
+class DownloadQuery::DownloadComparator {
+ public:
+  DownloadComparator(const DownloadQuery::SortFieldVector& terms)
+    : terms_(terms) {
+  }
+
+  // Returns true if |left| sorts before |right|.
+  bool operator() (const DownloadItem* left, const DownloadItem* right);
+
+ private:
+  const DownloadQuery::SortFieldVector& terms_;
+
+  // std::sort requires this class to be copyable.
+};
+
+bool DownloadQuery::DownloadComparator::operator() (
+    const DownloadItem* left, const DownloadItem* right) {
+  for (DownloadQuery::SortFieldVector::const_iterator term = terms_.begin();
+       term != terms_.end(); ++term) {
+    switch (term->sorter.Run(*left, *right)) {
+      case LT: return term->direction == DownloadQuery::ASCENDING;
+      case GT: return term->direction == DownloadQuery::DESCENDING;
+      case EQ: break;  // break the switch but not the loop
+    }
+  }
+  if (left->GetId() != right->GetId())
+    return left->GetId() < right->GetId();
+  CHECK_NE(left->GetDbHandle(), right->GetDbHandle());
+  return left->GetDbHandle() < right->GetDbHandle();
+}
+
+void DownloadQuery::Sort(DownloadQuery::SortFieldName name,
+                         DownloadQuery::SortFieldDirection direction) {
+  switch (name) {
+    case SORT_FIELD_START_TIME:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<int>, InnerCallback<int>(base::Bind(&GetStartTime)))));
+      break;
+    case SORT_FIELD_URL:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<std::string>,
+          InnerCallback<std::string>(base::Bind(&GetUrl)))));
+      break;
+    case SORT_FIELD_FILENAME:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<string16>,
+          InnerCallback<string16>(base::Bind(&GetFilename)))));
+      break;
+    case SORT_FIELD_DANGER:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<DownloadStateInfo::DangerType>,
+          InnerCallback<DownloadStateInfo::DangerType>(base::Bind(
+              &GetDangerType)))));
+      break;
+    case SORT_FIELD_DANGER_ACCEPTED:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<bool>,
+          InnerCallback<bool>(base::Bind(&GetDangerAccepted)))));
+      break;
+    case SORT_FIELD_STATE:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<DownloadItem::DownloadState>,
+          InnerCallback<DownloadItem::DownloadState>(base::Bind(&GetState)))));
+      break;
+    case SORT_FIELD_PAUSED:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<bool>, InnerCallback<bool>(base::Bind(&IsPaused)))));
+      break;
+    case SORT_FIELD_MIME:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<std::string>,
+          InnerCallback<std::string>(base::Bind(&GetMimeType)))));
+      break;
+    case SORT_FIELD_BYTES_RECEIVED:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<int>, InnerCallback<int>(base::Bind(&GetReceivedBytes)))));
+      break;
+    case SORT_FIELD_TOTAL_BYTES:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<int>, InnerCallback<int>(base::Bind(&GetTotalBytes)))));
+      break;
+    default: NOTREACHED();
+  }
+}
+
+template <typename InputIterator>
+void DownloadQuery::Search(InputIterator iter, const InputIterator last,
+                           DownloadQuery::DownloadVector* results) const {
+  results->clear();
+  for (; iter != last; ++iter) {
+    if (Matches(**iter))
+      results->push_back(*iter);
+  }
+  if (!sort_fields_.empty())
+    std::partial_sort(results->begin(),
+                      results->begin() + std::min(limit_, results->size()),
+                      results->end(),
+                      DownloadComparator(sort_fields_));
+  if (results->size() > limit_)
+    results->resize(limit_);
+}
+
+template void DownloadQuery::Search(
+    std::set<DownloadItem*>::const_iterator iter,
+    const std::set<DownloadItem*>::const_iterator last,
+    DownloadQuery::DownloadVector* results) const;
+template void DownloadQuery::Search(
+    std::vector<DownloadItem*>::const_iterator iter,
+    const std::vector<DownloadItem*>::const_iterator last,
+    DownloadQuery::DownloadVector* results) const;
+template void DownloadQuery::Search(
+    std::vector<DownloadItem*>::iterator iter,
+    const std::vector<DownloadItem*>::iterator last,
+    DownloadQuery::DownloadVector* results) const;
+