DownloadQuery filters and sorts DownloadItems

DownloadQuery will be used first by the DownloadsSearchFunction in download_extension_api.h/cc to implement the chrome.experimental.downloads.search() function outlined in http://goo.gl/6hO1n

BUG=12133
TEST=content_unittests DownloadQueryTest

Review URL: http://codereview.chromium.org/8601012

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@114460 0039d316-1c4b-4281-b951-d872f2087c98

5 files changed, 921 insertions, 0 deletions

diff --git a/content/browser/download/download_query.cc b/content/browser/download/download_query.cc
new file mode 100644
index 0000000..730da6a
--- /dev/null
+++ b/content/browser/download/download_query.cc
@@ -0,0 +1,373 @@
+// 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 <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 "base/values.h"
+#include "content/browser/download/download_item.h"
+#include "googleurl/src/gurl.h"
+#include "unicode/regex.h"
+
+namespace {
+
+// Templatized base::Value::GetAs*().
+template <typename T> bool GetAs(const base::Value& in, T* out);
+template<> bool GetAs(const base::Value& in, bool* out) {
+  return in.GetAsBoolean(out);
+}
+template<> bool GetAs(const base::Value& in, int* out) {
+  return in.GetAsInteger(out);
+}
+template<> bool GetAs(const base::Value& in, std::string* out) {
+  return in.GetAsString(out);
+}
+template<> bool GetAs(const base::Value& in, string16* out) {
+  return in.GetAsString(out);
+}
+
+// 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;
+}
+
+// Helper for building a Callback to FieldMatches<>().
+template <typename ValueType> DownloadQuery::FilterCallback BuildFilter(
+    const base::Value& value, ComparisonType cmptype,
+    ValueType (*accessor)(const DownloadItem&)) {
+  ValueType cpp_value;
+  if (!GetAs(value, &cpp_value)) return DownloadQuery::FilterCallback();
+  return base::Bind(&FieldMatches<ValueType>, cpp_value, cmptype,
+                    InnerCallback<ValueType>(base::Bind(accessor)));
+}
+
+// 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() == TRUE;  // Ugh, VS complains bool != UBool.
+}
+
+// Helper for building a Callback to FindRegex().
+DownloadQuery::FilterCallback BuildRegexFilter(
+    const base::Value& regex_value,
+    std::string (*accessor)(const DownloadItem&)) {
+  std::string regex_str;
+  if (!GetAs(regex_value, &regex_str)) return DownloadQuery::FilterCallback();
+  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 DownloadQuery::FilterCallback();
+  return base::Bind(&FindRegex, base::Owned(pattern.release()),
+                    InnerCallback<std::string>(base::Bind(accessor)));
+}
+
+// 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;
+  if (left_value < right_value) return LT;
+  DCHECK_EQ(left_value, right_value);
+  return EQ;
+}
+
+}  // anonymous namespace
+
+DownloadQuery::DownloadQuery()
+  : limit_(kuint32max) {
+}
+
+DownloadQuery::~DownloadQuery() {
+}
+
+// AddFilter() pushes a new FilterCallback to filters_. Most FilterCallbacks are
+// Callbacks to FieldMatches<>(). Search() iterates over given DownloadItems,
+// discarding items for which any filter returns false. A DownloadQuery may have
+// zero or more FilterCallbacks.
+
+bool DownloadQuery::AddFilter(const DownloadQuery::FilterCallback& value) {
+  if (value.is_null()) return false;
+  filters_.push_back(value);
+  return true;
+}
+
+void DownloadQuery::AddFilter(DownloadItem::DownloadState state) {
+  AddFilter(base::Bind(&FieldMatches<DownloadItem::DownloadState>, state, EQ,
+      InnerCallback<DownloadItem::DownloadState>(base::Bind(&GetState))));
+}
+
+void DownloadQuery::AddFilter(DownloadStateInfo::DangerType danger) {
+  AddFilter(base::Bind(&FieldMatches<DownloadStateInfo::DangerType>, danger, EQ,
+      InnerCallback<DownloadStateInfo::DangerType>(base::Bind(
+          &GetDangerType))));
+}
+
+bool DownloadQuery::AddFilter(DownloadQuery::FilterType type,
+                              const base::Value& value) {
+  switch (type) {
+    case FILTER_BYTES_RECEIVED:
+      return AddFilter(BuildFilter<int>(value, EQ, &GetReceivedBytes));
+    case FILTER_DANGER_ACCEPTED:
+      return AddFilter(BuildFilter<bool>(value, EQ, &GetDangerAccepted));
+    case FILTER_FILENAME:
+      return AddFilter(BuildFilter<string16>(value, EQ, &GetFilename));
+    case FILTER_FILENAME_REGEX:
+      return AddFilter(BuildRegexFilter(value, &GetFilenameUTF8));
+    case FILTER_MIME:
+      return AddFilter(BuildFilter<std::string>(value, EQ, &GetMimeType));
+    case FILTER_PAUSED:
+      return AddFilter(BuildFilter<bool>(value, EQ, &IsPaused));
+    case FILTER_QUERY: {
+      string16 query;
+      return GetAs(value, &query) &&
+             AddFilter(base::Bind(&MatchesQuery, query));
+    }
+    case FILTER_STARTED_AFTER:
+      return AddFilter(BuildFilter<int>(value, GT, &GetStartTime));
+    case FILTER_STARTED_BEFORE:
+      return AddFilter(BuildFilter<int>(value, LT, &GetStartTime));
+    case FILTER_START_TIME:
+      return AddFilter(BuildFilter<int>(value, EQ, &GetStartTime));
+    case FILTER_TOTAL_BYTES:
+      return AddFilter(BuildFilter<int>(value, EQ, &GetTotalBytes));
+    case FILTER_TOTAL_BYTES_GREATER:
+      return AddFilter(BuildFilter<int>(value, GT, &GetTotalBytes));
+    case FILTER_TOTAL_BYTES_LESS:
+      return AddFilter(BuildFilter<int>(value, LT, &GetTotalBytes));
+    case FILTER_URL:
+      return AddFilter(BuildFilter<std::string>(value, EQ, &GetUrl));
+    case FILTER_URL_REGEX:
+      return AddFilter(BuildRegexFilter(value, &GetUrl));
+  }
+  return false;
+}
+
+bool DownloadQuery::Matches(const DownloadItem& item) const {
+  for (FilterCallbackVector::const_iterator filter = filters_.begin();
+        filter != filters_.end(); ++filter) {
+    if (!filter->Run(item))
+      return false;
+  }
+  return true;
+}
+
+// AddSorter() creates a Sorter and pushes it onto sorters_. A Sorter is a
+// direction and a Callback to Compare<>(). After filtering, Search() makes a
+// DownloadComparator functor from the sorters_ and passes the
+// DownloadComparator to std::partial_sort. std::partial_sort calls the
+// DownloadComparator with different pairs of DownloadItems.  DownloadComparator
+// iterates over the sorters until a callback returns ComparisonType LT or GT.
+// DownloadComparator returns true or false depending on that ComparisonType and
+// the sorter's direction in order to indicate to std::partial_sort whether the
+// left item is after or before the right item. If all sorters return EQ, then
+// DownloadComparator compares GetId. A DownloadQuery may have zero or more
+// Sorters, but there is one DownloadComparator per call to Search().
+
+struct DownloadQuery::Sorter {
+  typedef base::Callback<ComparisonType(
+      const DownloadItem&, const DownloadItem&)> SortType;
+
+  template<typename ValueType>
+  static Sorter Build(DownloadQuery::SortDirection adirection,
+                         ValueType (*accessor)(const DownloadItem&)) {
+    return Sorter(adirection, base::Bind(&Compare<ValueType>,
+        InnerCallback<ValueType>(base::Bind(accessor))));
+  }
+
+  Sorter(DownloadQuery::SortDirection adirection,
+            const SortType& asorter)
+    : direction(adirection),
+      sorter(asorter) {
+  }
+  ~Sorter() {}
+
+  DownloadQuery::SortDirection direction;
+  SortType sorter;
+};
+
+class DownloadQuery::DownloadComparator {
+ public:
+  DownloadComparator(const DownloadQuery::SorterVector& terms)
+    : terms_(terms) {
+  }
+
+  // Returns true if |left| sorts before |right|.
+  bool operator() (const DownloadItem* left, const DownloadItem* right);
+
+ private:
+  const DownloadQuery::SorterVector& terms_;
+
+  // std::sort requires this class to be copyable.
+};
+
+bool DownloadQuery::DownloadComparator::operator() (
+    const DownloadItem* left, const DownloadItem* right) {
+  for (DownloadQuery::SorterVector::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
+    }
+  }
+  CHECK_NE(left->GetId(), right->GetId());
+  return left->GetId() < right->GetId();
+}
+
+void DownloadQuery::AddSorter(DownloadQuery::SortType type,
+                              DownloadQuery::SortDirection direction) {
+  switch (type) {
+    case SORT_START_TIME:
+      sorters_.push_back(Sorter::Build<int>(direction, &GetStartTime));
+      break;
+    case SORT_URL:
+      sorters_.push_back(Sorter::Build<std::string>(direction, &GetUrl));
+      break;
+    case SORT_FILENAME:
+      sorters_.push_back(Sorter::Build<string16>(direction, &GetFilename));
+      break;
+    case SORT_DANGER:
+      sorters_.push_back(Sorter::Build<DownloadStateInfo::DangerType>(
+          direction, &GetDangerType));
+      break;
+    case SORT_DANGER_ACCEPTED:
+      sorters_.push_back(Sorter::Build<bool>(direction, &GetDangerAccepted));
+      break;
+    case SORT_STATE:
+      sorters_.push_back(Sorter::Build<DownloadItem::DownloadState>(
+          direction, &GetState));
+      break;
+    case SORT_PAUSED:
+      sorters_.push_back(Sorter::Build<bool>(direction, &IsPaused));
+      break;
+    case SORT_MIME:
+      sorters_.push_back(Sorter::Build<std::string>(direction, &GetMimeType));
+      break;
+    case SORT_BYTES_RECEIVED:
+      sorters_.push_back(Sorter::Build<int>(direction, &GetReceivedBytes));
+      break;
+    case SORT_TOTAL_BYTES:
+      sorters_.push_back(Sorter::Build<int>(direction, &GetTotalBytes));
+      break;
+  }
+}
+
+void DownloadQuery::FinishSearch(DownloadQuery::DownloadVector* results) const {
+  if (!sorters_.empty())
+    std::partial_sort(results->begin(),
+                      results->begin() + std::min(limit_, results->size()),
+                      results->end(),
+                      DownloadComparator(sorters_));
+  if (results->size() > limit_)
+    results->resize(limit_);
+}
diff --git a/content/browser/download/download_query.h b/content/browser/download/download_query.h
new file mode 100644
index 0000000..ee6fab6
--- /dev/null
+++ b/content/browser/download/download_query.h
@@ -0,0 +1,148 @@
+// 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.
+
+#ifndef CONTENT_BROWSER_DOWNLOAD_DOWNLOAD_QUERY_H_
+#define CONTENT_BROWSER_DOWNLOAD_DOWNLOAD_QUERY_H_
+#pragma once
+
+#include <map>
+#include <string>
+#include <vector>
+
+#include "base/callback_forward.h"
+#include "content/browser/download/download_item.h"
+
+namespace base {
+class Value;
+}
+
+// Filter and sort a vector of DownloadItem*s.
+//
+// The following example copies from |all_items| to |results| those
+// DownloadItem*s whose start time is 0 and whose id is odd, sorts primarily by
+// bytes received ascending and secondarily by url descending, and limits the
+// results to 20 items. Any number of filters or sorters is allowed. If all
+// sorters compare two DownloadItems equivalently, then they are sorted by their
+// id ascending.
+//
+// DownloadQuery query;
+// scoped_ptr<base::Value> start_time(base::Balue::CreateIntegerValue(0));
+// CHECK(query.AddFilter(FILTER_START_TIME, *start_time.get()));
+// bool FilterOutOddDownloads(const DownloadItem& item) {
+//   return 0 == (item.GetId() % 2);
+// }
+// CHECK(query.AddFilter(base::Bind(&FilterOutOddDownloads)));
+// query.AddSorter(SORT_BYTES_RECEIVED, ASCENDING);
+// query.AddSorter(SORT_URL, DESCENDING);
+// query.Limit(20);
+// DownloadVector all_items, results;
+// query.Search(all_items.begin(), all_items.end(), &results);
+class CONTENT_EXPORT DownloadQuery {
+ public:
+  typedef std::vector<DownloadItem*> DownloadVector;
+
+  // FilterCallback is a Callback that takes a DownloadItem and returns true if
+  // the item matches the filter and false otherwise.
+  // query.AddFilter(base::Bind(&YourFilterFunction));
+  typedef base::Callback<bool(const DownloadItem&)> FilterCallback;
+
+  // All times are the number of milliseconds since the Unix epoch.
+  enum FilterType {
+    FILTER_BYTES_RECEIVED,       // int
+    FILTER_DANGER_ACCEPTED,      // bool
+    FILTER_FILENAME,             // string
+    FILTER_FILENAME_REGEX,       // string
+    FILTER_MIME,                 // string
+    FILTER_PAUSED,               // bool
+    FILTER_QUERY,                // string
+    FILTER_STARTED_AFTER,        // int
+    FILTER_STARTED_BEFORE,       // int
+    FILTER_START_TIME,           // int
+    FILTER_TOTAL_BYTES,          // int
+    FILTER_TOTAL_BYTES_GREATER,  // int
+    FILTER_TOTAL_BYTES_LESS,     // int
+    FILTER_URL,                  // string
+    FILTER_URL_REGEX,            // string
+  };
+
+  enum SortType {
+    SORT_BYTES_RECEIVED,
+    SORT_DANGER,
+    SORT_DANGER_ACCEPTED,
+    SORT_FILENAME,
+    SORT_MIME,
+    SORT_PAUSED,
+    SORT_START_TIME,
+    SORT_STATE,
+    SORT_TOTAL_BYTES,
+    SORT_URL,
+  };
+
+  enum SortDirection {
+    ASCENDING,
+    DESCENDING,
+  };
+
+  DownloadQuery();
+  ~DownloadQuery();
+
+  // Adds a new filter of type |type| with value |value| and returns true if
+  // |type| is valid and |value| is the correct Value-type and well-formed.
+  // Returns false if |type| is invalid or |value| is the incorrect Value-type
+  // or malformed.  Search() will filter out all DownloadItem*s that do not
+  // match all filters.  Multiple instances of the same FilterType are allowed,
+  // so you can pass two regexes to AddFilter(URL_REGEX,...) in order to
+  // Search() for items whose url matches both regexes. You can also pass two
+  // different DownloadStates to AddFilter(), which will cause Search() to
+  // filter out all items.
+  bool AddFilter(const FilterCallback& filter);
+  bool AddFilter(FilterType type, const base::Value& value);
+  void AddFilter(DownloadStateInfo::DangerType danger);
+  void AddFilter(DownloadItem::DownloadState state);
+
+  // Adds a new sorter of type |type| with direction |direction|.  After
+  // filtering DownloadItem*s, Search() will sort the results primarily by the
+  // sorter from the first call to Sort(), secondarily by the sorter from the
+  // second call to Sort(), and so on. For example, if the InputIterator passed
+  // to Search() yields four DownloadItems {id:0, error:0, start_time:0}, {id:1,
+  // error:0, start_time:1}, {id:2, error:1, start_time:0}, {id:3, error:1,
+  // start_time:1}, and Sort is called twice, once with (SORT_ERROR, ASCENDING)
+  // then with (SORT_START_TIME, DESCENDING), then Search() will return items
+  // ordered 1,0,3,2.
+  void AddSorter(SortType type, SortDirection direction);
+
+  // Limit the size of search results to |limit|.
+  void Limit(size_t limit) { limit_ = limit; }
+
+  // Filters DownloadItem*s from |iter| to |last| into |results|, sorts
+  // |results|, and limits the size of |results|. |results| must be non-NULL.
+  template <typename InputIterator>
+  void Search(InputIterator iter, const InputIterator last,
+              DownloadVector* results) const {
+    results->clear();
+    for (; iter != last; ++iter) {
+      if (Matches(**iter)) results->push_back(*iter);
+    }
+    FinishSearch(results);
+  }
+
+ private:
+  struct Sorter;
+  class DownloadComparator;
+  typedef std::vector<FilterCallback> FilterCallbackVector;
+  typedef std::vector<Sorter> SorterVector;
+
+  bool FilterRegex(const std::string& regex_str,
+      const base::Callback<std::string(const DownloadItem&)>& accessor);
+  bool Matches(const DownloadItem& item) const;
+  void FinishSearch(DownloadVector* results) const;
+
+  FilterCallbackVector filters_;
+  SorterVector sorters_;
+  size_t limit_;
+
+  DISALLOW_COPY_AND_ASSIGN(DownloadQuery);
+};
+
+#endif  // CONTENT_BROWSER_DOWNLOAD_DOWNLOAD_QUERY_H_
diff --git a/content/browser/download/download_query_unittest.cc b/content/browser/download/download_query_unittest.cc
new file mode 100644
index 0000000..0197182
--- /dev/null
+++ b/content/browser/download/download_query_unittest.cc
@@ -0,0 +1,397 @@
+// 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 <string>
+
+#include "base/bind.h"
+#include "base/file_path.h"
+#include "base/logging.h"
+#include "base/memory/scoped_ptr.h"
+#include "base/stl_util.h"
+#include "base/string16.h"
+#include "base/time.h"
+#include "base/values.h"
+#include "content/browser/download/download_query.h"
+#include "content/browser/download/mock_download_item.h"
+#include "testing/gmock/include/gmock/gmock.h"
+#include "testing/gtest/include/gtest/gtest.h"
+
+using ::testing::Return;
+using ::testing::ReturnRef;
+using ::testing::_;
+using base::Time;
+using base::Value;
+typedef DownloadQuery::DownloadVector DownloadVector;
+
+namespace {
+
+bool IdNotEqual(int not_id, const DownloadItem& item) {
+  return item.GetId() != not_id;
+}
+
+bool AlwaysReturn(bool result, const DownloadItem& item) {
+  return result;
+}
+
+}  // anonymous namespace
+
+class DownloadQueryTest : public testing::Test {
+ public:
+  DownloadQueryTest() {}
+
+  virtual ~DownloadQueryTest() {}
+
+  virtual void TearDown() {
+    STLDeleteElements(&mocks_);
+  }
+
+  void CreateMocks(int count) {
+    for (int i = 0; i < count; ++i) {
+      mocks_.push_back(new MockDownloadItem());
+    }
+  }
+
+  MockDownloadItem& mock(int index) { return *mocks_[index]; }
+
+  DownloadQuery* query() { return &query_; }
+
+  template<typename ValueType> void AddFilter(
+      DownloadQuery::FilterType name, ValueType value);
+
+  void Search() {
+    query_.Search(mocks_.begin(), mocks_.end(), &results_);
+  }
+
+  DownloadVector* results() { return &results_; }
+
+ private:
+  std::vector<MockDownloadItem*> mocks_;
+  DownloadQuery query_;
+  DownloadVector results_;
+
+  DISALLOW_COPY_AND_ASSIGN(DownloadQueryTest);
+};
+
+template<> void DownloadQueryTest::AddFilter(
+    DownloadQuery::FilterType name, bool cpp_value) {
+  scoped_ptr<base::Value> value(Value::CreateBooleanValue(cpp_value));
+  CHECK(query_.AddFilter(name, *value.get()));
+}
+
+template<> void DownloadQueryTest::AddFilter(
+    DownloadQuery::FilterType name, int cpp_value) {
+  scoped_ptr<base::Value> value(Value::CreateIntegerValue(cpp_value));
+  CHECK(query_.AddFilter(name, *value.get()));
+}
+
+template<> void DownloadQueryTest::AddFilter(
+    DownloadQuery::FilterType name, const char* cpp_value) {
+  scoped_ptr<base::Value> value(Value::CreateStringValue(cpp_value));
+  CHECK(query_.AddFilter(name, *value.get()));
+}
+
+template<> void DownloadQueryTest::AddFilter(
+    DownloadQuery::FilterType name, const char16* cpp_value) {
+  scoped_ptr<base::Value> value(Value::CreateStringValue(string16(cpp_value)));
+  CHECK(query_.AddFilter(name, *value.get()));
+}
+
+TEST_F(DownloadQueryTest, DownloadQueryEmptyNoItems) {
+  Search();
+  EXPECT_EQ(0U, results()->size());
+}
+
+TEST_F(DownloadQueryTest, DownloadQueryEmptySomeItems) {
+  CreateMocks(3);
+  Search();
+  EXPECT_EQ(3U, results()->size());
+}
+
+TEST_F(DownloadQueryTest, DownloadQueryInvalidFilters) {
+  scoped_ptr<base::Value> value(Value::CreateIntegerValue(0));
+  EXPECT_FALSE(query()->AddFilter(
+      static_cast<DownloadQuery::FilterType>(kint32max),
+      *value.get()));
+}
+
+TEST_F(DownloadQueryTest, DownloadQueryLimit) {
+  CreateMocks(2);
+  query()->Limit(1);
+  Search();
+  EXPECT_EQ(1U, results()->size());
+}
+
+// Syntactic sugar for an expression version of the switch-case statement.
+// Cf. Lisp's |case| form.
+#define SWITCH2(_index, _col1, _ret1, _default) \
+  ((_index == (_col1)) ? _ret1 : _default)
+#define SWITCH3(_index, _col1, _ret1, _col2, _ret2, _default) \
+  SWITCH2(_index, _col1, _ret1, SWITCH2(_index, _col2, _ret2, _default))
+#define SWITCH4(_index, _col1, _ret1, _col2, _ret2, _col3, _ret3, _default) \
+  SWITCH3(_index, _col1, _ret1, _col2, _ret2, \
+      SWITCH2(_index, _col3, _ret3, _default))
+
+TEST_F(DownloadQueryTest, DownloadQueryAllFilters) {
+  // Set up mocks such that only mock(0) matches all filters, and every other
+  // mock fails a different filter (or two for GREATER/LESS filters).
+  static const size_t kNumItems = 19;
+  CreateMocks(kNumItems);
+  FilePath refail_filename(FILE_PATH_LITERAL("z"));
+  FilePath fail_filename(FILE_PATH_LITERAL("fail"));
+  FilePath match_filename(FILE_PATH_LITERAL("match"));
+  GURL refail_url("http://z.com/");
+  GURL fail_url("http://example.com/fail");
+  GURL match_url("http://example.com/match");
+  // Picture a 2D matrix. The rows are MockDownloadItems and the columns are
+  // filter types. Every cell contains a value that matches all filters, except
+  // for the diagonal. Every item matches all the filters except one filter,
+  // which it fails, except one item, which matches all the filters without
+  // exception. Each mocked method is used to test (corresponds to) one or more
+  // filter types (columns). For example, GetTotalBytes() is used to test
+  // FILTER_TOTAL_BYTES_GREATER, FILTER_TOTAL_BYTES_LESS, and
+  // FILTER_TOTAL_BYTES, so it uses 3 columns: it returns 1 for row (item) 11,
+  // it returns 4 for row 12, 3 for 13, and it returns 2 for all other rows
+  // (items).
+  for (size_t i = 0; i < kNumItems; ++i) {
+    EXPECT_CALL(mock(i), GetId()).WillRepeatedly(Return(i));
+    EXPECT_CALL(mock(i), GetReceivedBytes()).WillRepeatedly(Return(SWITCH2(i,
+        1, 2,
+           1)));
+    EXPECT_CALL(mock(i), GetSafetyState()).WillRepeatedly(Return(SWITCH2(i,
+        2, DownloadItem::DANGEROUS,
+           DownloadItem::DANGEROUS_BUT_VALIDATED)));
+    EXPECT_CALL(mock(i), GetFullPath()).WillRepeatedly(ReturnRef(SWITCH3(i,
+        3, refail_filename,
+        4, fail_filename,
+           match_filename)));
+    EXPECT_CALL(mock(i), GetMimeType()).WillRepeatedly(Return(SWITCH2(i,
+        5, "image",
+           "text")));
+    EXPECT_CALL(mock(i), IsPaused()).WillRepeatedly(Return(SWITCH2(i,
+        6, false,
+           true)));
+    EXPECT_CALL(mock(i), MatchesQuery(_)).WillRepeatedly(Return(SWITCH2(i,
+        7, false,
+           true)));
+    EXPECT_CALL(mock(i), GetStartTime()).WillRepeatedly(Return(SWITCH4(i,
+        8,  base::Time::FromTimeT(1),
+        9,  base::Time::FromTimeT(4),
+        10, base::Time::FromTimeT(3),
+            base::Time::FromTimeT(2))));
+    EXPECT_CALL(mock(i), GetTotalBytes()).WillRepeatedly(Return(SWITCH4(i,
+        11, 1,
+        12, 4,
+        13, 3,
+            2)));
+    EXPECT_CALL(mock(i), GetOriginalUrl()).WillRepeatedly(ReturnRef(SWITCH3(i,
+        14, refail_url,
+        15, fail_url,
+            match_url)));
+    EXPECT_CALL(mock(i), GetState()).WillRepeatedly(Return(SWITCH2(i,
+        17, DownloadItem::CANCELLED,
+            DownloadItem::IN_PROGRESS)));
+    EXPECT_CALL(mock(i), GetDangerType()).WillRepeatedly(Return(SWITCH2(i,
+        18, DownloadStateInfo::DANGEROUS_FILE,
+            DownloadStateInfo::NOT_DANGEROUS)));
+  }
+  for (size_t i = 0; i < kNumItems; ++i) {
+    switch (i) {
+      case 0: break;
+      case 1: AddFilter(DownloadQuery::FILTER_BYTES_RECEIVED, 1); break;
+      case 2: AddFilter(DownloadQuery::FILTER_DANGER_ACCEPTED, true);
+              break;
+      case 3: AddFilter(DownloadQuery::FILTER_FILENAME_REGEX, "a"); break;
+      case 4: AddFilter(DownloadQuery::FILTER_FILENAME,
+                        match_filename.value().c_str()); break;
+      case 5: AddFilter(DownloadQuery::FILTER_MIME, "text"); break;
+      case 6: AddFilter(DownloadQuery::FILTER_PAUSED, true); break;
+      case 7: AddFilter(DownloadQuery::FILTER_QUERY, ""); break;
+      case 8: AddFilter(DownloadQuery::FILTER_STARTED_AFTER, 1000); break;
+      case 9: AddFilter(DownloadQuery::FILTER_STARTED_BEFORE, 4000);
+              break;
+      case 10: AddFilter(DownloadQuery::FILTER_START_TIME, 2000); break;
+      case 11: AddFilter(DownloadQuery::FILTER_TOTAL_BYTES_GREATER, 1);
+               break;
+      case 12: AddFilter(DownloadQuery::FILTER_TOTAL_BYTES_LESS, 4);
+               break;
+      case 13: AddFilter(DownloadQuery::FILTER_TOTAL_BYTES, 2); break;
+      case 14: AddFilter(DownloadQuery::FILTER_URL_REGEX, "example");
+               break;
+      case 15: AddFilter(DownloadQuery::FILTER_URL,
+                         match_url.spec().c_str()); break;
+      case 16: CHECK(query()->AddFilter(base::Bind(&IdNotEqual, 16))); break;
+      case 17: query()->AddFilter(DownloadItem::IN_PROGRESS); break;
+      case 18: query()->AddFilter(DownloadStateInfo::NOT_DANGEROUS); break;
+      default: NOTREACHED(); break;
+    }
+    Search();
+    ASSERT_EQ(kNumItems - i, results()->size())
+      << "Failing filter: " << i;
+    if (i > 0) {
+      ASSERT_EQ(0, results()->at(0)->GetId())
+        << "Failing filter: " << i;
+      for (size_t j = 1; j < kNumItems - i; ++j) {
+        ASSERT_EQ(static_cast<int32>(j + i), results()->at(j)->GetId())
+          << "Failing filter: " << i;
+      }
+    }
+  }
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortBytesReceived) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetReceivedBytes()).WillRepeatedly(Return(0));
+  EXPECT_CALL(mock(1), GetReceivedBytes()).WillRepeatedly(Return(1));
+  query()->AddSorter(
+      DownloadQuery::SORT_BYTES_RECEIVED, DownloadQuery::DESCENDING);
+  Search();
+  EXPECT_EQ(1, results()->at(0)->GetReceivedBytes());
+  EXPECT_EQ(0, results()->at(1)->GetReceivedBytes());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortDanger) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetDangerType()).WillRepeatedly(Return(
+        DownloadStateInfo::DANGEROUS_FILE));
+  EXPECT_CALL(mock(1), GetDangerType()).WillRepeatedly(Return(
+        DownloadStateInfo::NOT_DANGEROUS));
+  query()->AddSorter(
+      DownloadQuery::SORT_DANGER, DownloadQuery::ASCENDING);
+  Search();
+  EXPECT_EQ(DownloadStateInfo::NOT_DANGEROUS,
+            results()->at(0)->GetDangerType());
+  EXPECT_EQ(DownloadStateInfo::DANGEROUS_FILE,
+            results()->at(1)->GetDangerType());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortDangerAccepted) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetSafetyState()).WillRepeatedly(Return(
+        DownloadItem::DANGEROUS));
+  EXPECT_CALL(mock(1), GetSafetyState()).WillRepeatedly(Return(
+        DownloadItem::DANGEROUS_BUT_VALIDATED));
+  query()->AddSorter(
+      DownloadQuery::SORT_DANGER_ACCEPTED, DownloadQuery::DESCENDING);
+  Search();
+  EXPECT_EQ(DownloadItem::DANGEROUS_BUT_VALIDATED,
+            results()->at(0)->GetSafetyState());
+  EXPECT_EQ(DownloadItem::DANGEROUS, results()->at(1)->GetSafetyState());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortFilename) {
+  CreateMocks(2);
+  FilePath a_filename(FILE_PATH_LITERAL("a"));
+  FilePath b_filename(FILE_PATH_LITERAL("b"));
+  EXPECT_CALL(mock(0), GetFullPath()).WillRepeatedly(ReturnRef(b_filename));
+  EXPECT_CALL(mock(1), GetFullPath()).WillRepeatedly(ReturnRef(a_filename));
+  query()->AddSorter(
+      DownloadQuery::SORT_FILENAME, DownloadQuery::ASCENDING);
+  Search();
+  EXPECT_EQ(a_filename, results()->at(0)->GetFullPath());
+  EXPECT_EQ(b_filename, results()->at(1)->GetFullPath());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortMime) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetMimeType()).WillRepeatedly(Return("a"));
+  EXPECT_CALL(mock(1), GetMimeType()).WillRepeatedly(Return("b"));
+  query()->AddSorter(
+      DownloadQuery::SORT_MIME, DownloadQuery::DESCENDING);
+  Search();
+  EXPECT_EQ("b", results()->at(0)->GetMimeType());
+  EXPECT_EQ("a", results()->at(1)->GetMimeType());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortPaused) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), IsPaused()).WillRepeatedly(Return(true));
+  EXPECT_CALL(mock(1), IsPaused()).WillRepeatedly(Return(false));
+  query()->AddSorter(
+      DownloadQuery::SORT_PAUSED, DownloadQuery::ASCENDING);
+  Search();
+  EXPECT_EQ(false, results()->at(0)->IsPaused());
+  EXPECT_EQ(true, results()->at(1)->IsPaused());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortStartTime) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetStartTime()).WillRepeatedly(Return(
+        base::Time::FromTimeT(0)));
+  EXPECT_CALL(mock(1), GetStartTime()).WillRepeatedly(Return(
+        base::Time::FromTimeT(1)));
+  query()->AddSorter(
+      DownloadQuery::SORT_START_TIME, DownloadQuery::DESCENDING);
+  Search();
+  EXPECT_EQ(base::Time::FromTimeT(1), results()->at(0)->GetStartTime());
+  EXPECT_EQ(base::Time::FromTimeT(0), results()->at(1)->GetStartTime());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortState) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetState()).WillRepeatedly(Return(
+        DownloadItem::IN_PROGRESS));
+  EXPECT_CALL(mock(1), GetState()).WillRepeatedly(Return(
+        DownloadItem::COMPLETE));
+  query()->AddSorter(
+      DownloadQuery::SORT_STATE, DownloadQuery::ASCENDING);
+  Search();
+  EXPECT_EQ(DownloadItem::IN_PROGRESS, results()->at(0)->GetState());
+  EXPECT_EQ(DownloadItem::COMPLETE, results()->at(1)->GetState());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortTotalBytes) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetTotalBytes()).WillRepeatedly(Return(0));
+  EXPECT_CALL(mock(1), GetTotalBytes()).WillRepeatedly(Return(1));
+  query()->AddSorter(
+      DownloadQuery::SORT_TOTAL_BYTES, DownloadQuery::DESCENDING);
+  Search();
+  EXPECT_EQ(1, results()->at(0)->GetTotalBytes());
+  EXPECT_EQ(0, results()->at(1)->GetTotalBytes());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortUrl) {
+  CreateMocks(2);
+  GURL a_url("http://example.com/a");
+  GURL b_url("http://example.com/b");
+  EXPECT_CALL(mock(0), GetOriginalUrl()).WillRepeatedly(ReturnRef(b_url));
+  EXPECT_CALL(mock(1), GetOriginalUrl()).WillRepeatedly(ReturnRef(a_url));
+  query()->AddSorter(
+      DownloadQuery::SORT_URL, DownloadQuery::ASCENDING);
+  Search();
+  EXPECT_EQ(a_url, results()->at(0)->GetOriginalUrl());
+  EXPECT_EQ(b_url, results()->at(1)->GetOriginalUrl());
+}
+
+TEST_F(DownloadQueryTest, DownloadQuerySortId) {
+  CreateMocks(2);
+  EXPECT_CALL(mock(0), GetReceivedBytes()).WillRepeatedly(Return(0));
+  EXPECT_CALL(mock(1), GetReceivedBytes()).WillRepeatedly(Return(0));
+  EXPECT_CALL(mock(0), GetId()).WillRepeatedly(Return(1));
+  EXPECT_CALL(mock(1), GetId()).WillRepeatedly(Return(0));
+  query()->AddSorter(
+      DownloadQuery::SORT_BYTES_RECEIVED, DownloadQuery::DESCENDING);
+  Search();
+  EXPECT_EQ(0, results()->at(0)->GetId());
+  EXPECT_EQ(1, results()->at(1)->GetId());
+}
+
+TEST_F(DownloadQueryTest, DownloadQueryFilterPerformance) {
+  static const int kNumItems = 10000;
+  static const int kNumFilters = 1000;
+  CreateMocks(kNumItems);
+  for (size_t i = 0; i < (kNumFilters - 1); ++i) {
+    query()->AddFilter(base::Bind(&AlwaysReturn, true));
+  }
+  query()->AddFilter(base::Bind(&AlwaysReturn, false));
+  base::Time start = base::Time::Now();
+  Search();
+  base::Time end = base::Time::Now();
+  double nanos = (end - start).InMillisecondsF() * 1000.0 * 1000.0;
+  double nanos_per_item = nanos / static_cast<double>(kNumItems);
+  double nanos_per_item_per_filter = nanos_per_item
+    / static_cast<double>(kNumFilters);
+  std::cout << "Search took " << nanos_per_item_per_filter
+            << " nanoseconds per item per filter.\n";
+}
diff --git a/content/content_browser.gypi b/content/content_browser.gypi
index f0f0578..49526ea 100644
--- a/content/content_browser.gypi
+++ b/content/content_browser.gypi
@@ -166,6 +166,8 @@
     'browser/download/download_manager_impl.h',
     'browser/download/download_persistent_store_info.cc',
     'browser/download/download_persistent_store_info.h',
+    'browser/download/download_query.cc',
+    'browser/download/download_query.h',
     'browser/download/download_request_handle.cc',
     'browser/download/download_request_handle.h',
     'browser/download/download_resource_handler.cc',
diff --git a/content/content_tests.gypi b/content/content_tests.gypi
index bf27619..673a089 100644
--- a/content/content_tests.gypi
+++ b/content/content_tests.gypi
@@ -188,6 +188,7 @@
         'browser/download/download_buffer_unittest.cc',
         'browser/download/download_file_unittest.cc',
         'browser/download/download_id_unittest.cc',
+        'browser/download/download_query_unittest.cc',
         'browser/download/download_status_updater_unittest.cc',
         'browser/download/save_package_unittest.cc',
         'browser/gamepad/gamepad_provider_unittest.cc',