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 {
+
+enum ComparisonType {LT, EQ, GT};
+
+static bool MatchesQuery(const string16& value, const DownloadItem& item) {

[Randy Smith (Not in Mondays), 2011/11/30 19:26:17]

nit, suggestion: Comment before this set of functions indicate what the general
usage for them is (e.g. "helper functions for accessing non-simple attributes of
DownloadItem"?)

[benjhayden, 2011/11/30 22:13:49]

Done.

+  return item.MatchesQuery(value);
+}
+
+static int GetStartTime(const DownloadItem& item) {
+  return (item.GetStartTime() - base::Time::UnixEpoch()).InMilliseconds();
+}
+
+static int GetEndTime(const DownloadItem& item) {
+  return 0;  // TODO
+}
+
+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.

[Randy Smith (Not in Mondays), 2011/11/30 19:26:17]

nit: If there's an issue number, it should be in the comment.

[benjhayden, 2011/11/30 22:13:49]

There isn't a bug, it's just one CL: http://codereview.chromium.org/8738001/

+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.
+  bool is_null() const { return inner_.is_null(); }
+  ValueType Run(const DownloadItem& item) const { return inner_.Run(item); }
+
+ private:
+  CallbackType inner_;
+};
+
+// Returns true if |item| matches the filter specified by |value|, |signum|, and

[Randy Smith (Not in Mondays), 2011/11/30 19:26:17]

nit: I think this would be more easily comprehensible if ComparisonType was
defined right before this function; any reason not to?

I also find |signum| non-pneumonic.  Maybe |comptype| or |comparison_type|?

[benjhayden, 2011/11/30 22:13:49]

Done.
"cmptype" ok?

ComparisonType was originally called Signum because it replaced the 0/1/-1 in
Compare<>(). I missed this parameter when I renamed Signum.

+// |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 signum,
+    const InnerCallback<ValueType>& accessor,
+    const DownloadItem& item) {
+  switch (signum) {
+    case LT: return accessor.Run(item) < value;
+    case EQ: return accessor.Run(item) == value;
+    case GT: return accessor.Run(item) > value;
+  }
+  return false;
+}
+
+static bool ValidateRegex(const std::string& regex_str) {
+  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));
+  return U_SUCCESS(re_status);
+}
+
+// Returns true if |accessor.Run(item)| matches the regex pattern in
+// |regex_str|.
+static bool FindRegex(
+    const std::string& regex_str,
+    const InnerCallback<std::string>& accessor,
+    const DownloadItem& item) {
+  CHECK(!accessor.is_null());
+  icu::UnicodeString pattern(regex_str.c_str());
+  icu::UnicodeString input(accessor.Run(item).c_str());
+  UErrorCode status = U_ZERO_ERROR;
+  icu::RegexMatcher match(pattern, input, 0, status);

[Randy Smith (Not in Mondays), 2011/11/30 19:26:17]

This looks like we're going to recompile the pattern on every DownloadItem.  Is
there a way to compile the pattern only once?  This isn't top priority, just a
useful pre-optimization if we can do it.

[benjhayden, 2011/11/30 22:13:49]

Done.

+  return match.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) {
+  CHECK(!accessor.is_null());
+  ValueType left_value = accessor.Run(left);
+  ValueType right_value = accessor.Run(right);
+  if (left_value > right_value) return GT;
+  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, GT,
+                        InnerCallback<int>(base::Bind(&GetStartTime))));
+      return true;
+    case FILTER_FIELD_STARTED_AFTER:
+      Filter(base::Bind(&FieldMatches<int>, value, LT,
+                        InnerCallback<int>(base::Bind(&GetStartTime))));
+      return true;
+    case FILTER_FIELD_END_TIME:
+      Filter(base::Bind(&FieldMatches<int>, value, EQ,
+                        InnerCallback<int>(base::Bind(&GetEndTime))));
+      return true;
+    case FILTER_FIELD_ENDED_BEFORE:
+      Filter(base::Bind(&FieldMatches<int>, value, GT,
+                        InnerCallback<int>(base::Bind(&GetEndTime))));
+      return true;
+    case FILTER_FIELD_ENDED_AFTER:
+      Filter(base::Bind(&FieldMatches<int>, value, LT,
+                        InnerCallback<int>(base::Bind(&GetEndTime))));
+      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:
+      Filter(base::Bind(&FieldMatches<int>, value, LT,
+                        InnerCallback<int>(base::Bind(&GetTotalBytes))));
+      return true;
+    case FILTER_FIELD_TOTAL_BYTES_LESS:
+      Filter(base::Bind(&FieldMatches<int>, value, GT,
+                        InnerCallback<int>(base::Bind(&GetTotalBytes))));
+      return true;
+    case FILTER_FIELD_FILE_SIZE: return false;  // TODO
+    case FILTER_FIELD_FILE_SIZE_GREATER: return false;  // TODO
+    case FILTER_FIELD_FILE_SIZE_LESS: return false;  // TODO
+    case FILTER_FIELD_ERROR: return false;  // TODO
+  }
+  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::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:
+      if (!ValidateRegex(value)) return false;
+      Filter(base::Bind(&FindRegex, value,
+                        InnerCallback<std::string>(base::Bind(&GetUrl))));
+      return true;
+  }
+  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:
+      if (!ValidateRegex(UTF16ToUTF8(value))) return false;
+      Filter(base::Bind(&FindRegex, UTF16ToUTF8(value),
+          InnerCallback<std::string>(base::Bind(&GetFilenameUTF8))));
+      return true;
+  }
+  return false;
+}
+
+bool DownloadQuery::Matches(const DownloadItem& item) const {
+  for (FilterFieldVector::const_iterator filter = filter_fields_.begin();
+        filter != filter_fields_.end(); ++filter) {
+    CHECK(!filter->is_null());
+    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) {
+    CHECK(!(*term).sorter.is_null());
+    switch ((*term).sorter.Run(*left, *right)) {
+      case LT: return ((*term).direction == DownloadQuery::ASCENDING);
+      case GT: return ((*term).direction == DownloadQuery::DESCENDING);
+      case EQ: continue;
+    }
+  }
+  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_END_TIME:
+      sort_fields_.push_back(SortField(direction, base::Bind(
+          &Compare<int>, InnerCallback<int>(base::Bind(&GetEndTime)))));
+      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;
+    case SORT_FIELD_FILE_SIZE: break; // TODO
+    case SORT_FIELD_ERROR: break; // TODO

[Randy Smith (Not in Mondays), 2011/11/30 19:26:17]

Why are these no-ops?  I think of it as friendlier to return an error for
something that we haven't implemented than to pretend that it works.

[benjhayden, 2011/11/30 22:13:49]

Sort() doesn't return anything, so I'll make it NOTIMPLEMENTED().

+    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;
+