Implement chrome.experimental.downloads.search()

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 <string>
+#include <vector>
+
+#include "base/memory/scoped_ptr.h"
+#include "base/stl_util.h"
+#include "base/string16.h"
+#include "base/string_split.h"
+#include "base/utf_string_conversions.h"
+#include "unicode/regex.h"
+#include "content/browser/download/download_item.h"
+
+namespace download_util {
+
+// The FieldInterfaces allow us to keep the templateyness out of the header.
+
+// Filter fields can be used to filter DownloadItems out of the result set.
+class DownloadQuery::FilterFieldInterface {
+ public:
+  virtual ~FilterFieldInterface() {}
+  virtual bool is_set() const = 0;
+  virtual const std::string& name() const = 0;
+  virtual bool Matches(const DownloadItem& item) const = 0;
+};
+
+// Sort fields are used by DownloadComparator to sort DownloadItems.
+class DownloadQuery::SortFieldInterface {
+ public:
+  virtual ~SortFieldInterface() {}
+  virtual const std::string& name() const = 0;
+  // Return 0 when left's field is equivalent to right's field, -1 when left >
+  // right, or 1 when left < right.

[Randy Smith (Not in Mondays), 2011/10/13 23:23:11]

That seems backward from the usual custom (e.g. qsort).  Why do it that way?

[benjhayden, 2011/10/14 19:31:02]

Ah, I meant to check the convention. Done.

+  virtual int Compare(const DownloadItem& left,
+                      const DownloadItem& right) const = 0;
+};
+
+namespace {
+
+// Functor passed to std::sort to sort DownloadItems.
+class DownloadComparator {
+ public:
+  static const char kInvert = '-';
+
+  // If |order_term| begins with kInvert, return |order_term| after stripping it
+  // off and set |inverted| = true. Otherwise set |inverted| = false and return
+  // |order_term| as-is.
+  static std::string Revert(const std::string& order_term, bool* inverted) {
+    bool default_inverted = false;
+    if (inverted == NULL)
+      inverted = &default_inverted;
+    *inverted = (order_term[0] == kInvert);
+    return *inverted ? order_term.substr(1) : order_term;
+  }
+
+  DownloadComparator(const DownloadQuery::Strings& order_terms,
+                     const DownloadQuery::SortFields& sort_fields)
+    : order_terms_(order_terms),
+      sort_fields_(sort_fields) {
+  }
+
+  bool operator() (const DownloadItem* left, const DownloadItem* right);
+
+ private:
+  const DownloadQuery::Strings& order_terms_;
+  const DownloadQuery::SortFields& sort_fields_;
+
+  // std::sort requires this class to be copyable.
+};
+
+bool DownloadComparator::operator() (const DownloadItem* left,
+                                     const DownloadItem* right) {
+  for (DownloadQuery::Strings::const_iterator order_term = order_terms_.begin();
+       order_term != order_terms_.end(); ++order_term) {
+    bool inverted = false;
+    std::string order_term_value = Revert(*order_term, &inverted);
+    DownloadQuery::SortFields::const_iterator sort_field_iter =
+      sort_fields_.find(order_term_value);

[Randy Smith (Not in Mondays), 2011/10/18 23:58:46]

I wince when I see this.  Performance isn't vital for this functionality (I hope
:-}) but this adds another factor of n in the midst of your n log n operation. 
Is there any way to arrange things such that when we get to doing the
comparison, we're just chugging on down a list of sort key objects, each one of
which we can call Compare() on?

(I only have vague ideas in this direction, but I could imagine template methods
that are templated on the field enum, or static (lazily created) callback
instances that are looked up by field enum and then pushed on the list.)

+    CHECK(sort_field_iter != sort_fields_.end()) << order_term_value;
+    const DownloadQuery::SortFieldInterface* sort_field =
+      sort_field_iter->second;
+    CHECK(sort_field);
+    CHECK_EQ(sort_field->name(), order_term_value);
+    int comparison = sort_field->Compare(*left, *right);
+    if (comparison != 0)
+      return inverted == (comparison < 0);
+  }
+  if (left->id() != right->id())
+    return left->id() < right->id();
+  CHECK_NE(left->db_handle(), right->db_handle());
+  return left->db_handle() < right->db_handle();
+}
+
+static int get_start_time(const DownloadItem& item) {
+  return (item.start_time() - base::Time::UnixEpoch()).InMilliseconds();
+}
+
+static int get_end_time(const DownloadItem& item) {
+  return 0;  // TODO(benjhayden): endTime
+}
+
+static bool get_danger_accepted(const DownloadItem& item) {
+  return (item.safety_state() == DownloadItem::DANGEROUS_BUT_VALIDATED);
+}
+
+static string16 get_filename(const DownloadItem& item) {
+  return item.full_path().LossyDisplayName();
+}
+
+template <typename ValueType>
+class FilterField : public DownloadQuery::FilterFieldInterface {
+ public:
+  explicit FilterField(const char* name)
+    : name_(name),
+      is_set_(false) {
+  }
+  virtual ~FilterField() {}
+
+  virtual const std::string& name() const { return name_; }
+
+  virtual bool Set(const ValueType& value) {
+    value_ = value;
+    is_set_ = true;
+    return true;
+  }
+
+  virtual bool is_set() const { return is_set_; }
+
+ protected:
+  const ValueType& value() const { return value_; }
+
+ private:
+  std::string name_;
+  ValueType value_;
+  bool is_set_;
+};
+
+template <typename ValueType>
+class SortField : public DownloadQuery::SortFieldInterface {
+ public:
+  explicit SortField(const char* name) : name_(name) {}

[Randy Smith (Not in Mondays), 2011/10/18 23:58:46]

What's the purpose for having the name field on these interfaces?  The various
methods need to know which field their getting/comparing by some other method,
and we're switching over to defining fields by enums.  

+  virtual ~SortField() {}
+
+  virtual const std::string& name() const { return name_; }
+
+  virtual ValueType GetField(const DownloadItem& item) const = 0;
+
+  virtual int Compare(const DownloadItem& left,
+                      const DownloadItem& right) const {
+    ValueType left_value = GetField(left), right_value = GetField(right);
+    return (left_value < right_value) ? 1 : (right_value < left_value) ? -1 : 0;
+  }
+
+ private:
+  std::string name_;
+};
+
+class FilterFieldQuery : public FilterField<string16> {
+ public:
+  FilterFieldQuery() : FilterField<string16>("query") {}
+  virtual ~FilterFieldQuery() {}
+  virtual bool Set(const string16& value) {
+    base::SplitString(value, L' ', &terms_);

[Randy Smith (Not in Mondays), 2011/10/18 23:58:46]

This feels like more smarts than I'd expect at this level--what's the use case? 
Is it reasonable to layer this case on top of this class, rather than inside it?

+    // TODO(benjhayden): Split query more intelligently. Quopri?
+    return FilterField<string16>::Set(value);
+  }
+
+  virtual bool Matches(const DownloadItem& item) const {
+    for (std::vector<string16>::const_iterator term = terms_.begin();
+         term != terms_.end(); ++term) {
+      if (!item.MatchesQuery(*term))
+        return false;
+    }
+    return true;
+  }
+
+ private:
+  std::vector<string16> terms_;
+};
+
+template <typename StringType>
+class FilterFieldRegex : public FilterField<StringType> {
+ public:
+  explicit FilterFieldRegex(const char* name) : FilterField<StringType>(name) {}
+  virtual ~FilterFieldRegex() {}
+  virtual bool Set(const StringType& value) {
+    UParseError re_err;
+    UErrorCode re_status = U_ZERO_ERROR;
+    pattern_.reset(icu::RegexPattern::compile(
+        icu::UnicodeString::fromUTF8(ToUTF8(value)),
+        re_err, re_status));
+    return U_SUCCESS(re_status) &&
+           FilterField<StringType>::Set(value);
+  }
+
+ protected:
+  bool RegexMatches(const StringType& text) const {
+    UErrorCode status = U_ZERO_ERROR;
+    scoped_ptr<icu::RegexMatcher> matcher(pattern_->matcher(
+        icu::UnicodeString::fromUTF8(ToUTF8(text)), status));
+    return U_SUCCESS(status) &&
+           matcher->find(0, status);
+  }
+
+  virtual std::string ToUTF8(const StringType& s) const = 0;
+
+ private:
+  scoped_ptr<icu::RegexPattern> pattern_;
+};
+
+class FilterFieldUrlRegex : public FilterFieldRegex<std::string> {
+ public:
+  FilterFieldUrlRegex() : FilterFieldRegex<std::string>("urlRegex") {}
+  virtual ~FilterFieldUrlRegex() {}
+  virtual bool Matches(const DownloadItem& item) const {
+    return RegexMatches(item.original_url().spec());
+  }
+
+ protected:
+  virtual std::string ToUTF8(const std::string& s) const { return s; }
+};
+
+class FilterFieldFilenameRegex : public FilterFieldRegex<string16> {
+ public:
+  FilterFieldFilenameRegex() : FilterFieldRegex<string16>("filenameRegex") {}
+  virtual ~FilterFieldFilenameRegex() {}
+  virtual bool Matches(const DownloadItem& item) const {
+    return RegexMatches(get_filename(item));
+  }
+
+ protected:
+  virtual std::string ToUTF8(const string16& s) const { return UTF16ToUTF8(s); }
+};
+
+}  // anonymous namespace
+
+void DownloadQuery::SetSortField(
+    const char* name, DownloadQuery::SortFieldInterface* field) {
+  DCHECK(sort_fields_.find(name) == sort_fields_.end());
+  sort_fields_[name] = field;
+}
+
+void DownloadQuery::SetFilterField(
+    const char* name, DownloadQuery::FilterFieldInterface* field) {
+  DCHECK(filter_fields_.find(name) == filter_fields_.end());
+  filter_fields_[name] = field;
+}
+
+#define SORT_FIELD(name, type, expr) \

[Randy Smith (Not in Mondays), 2011/10/18 23:58:46]

It took me a couple of read throughs through these macros to follow what was
going on, and one issue was remembering which things were macros arguments as I
read.  Would it make sense to you to call out the macro arguments by (say)
having them have an underscore prepended to them?  (Or something else--I'm not
wedded to the underscore.)

+  SetSortField(#name,  ({\
+    class SortField ## name : public SortField<type> { \
+     public: \
+      SortField ## name() : SortField<type>(#name) {} \
+      virtual type GetField(const DownloadItem& item) const { return expr; } \
+    }; \
+    new SortField ## name(); \
+  })); \
+  FILTER_FIELD(name, type, (expr) == value())
+#define FILTER_FIELD(name, type, expr) \
+  SetFilterField(#name, ({ \
+    class FilterField ## name : public FilterField<type> { \
+     public: \
+      FilterField ## name() : FilterField<type>(#name) {} \
+      virtual bool Matches(const DownloadItem& item) const { return expr; } \
+    }; \
+    new FilterField ## name(); \
+  }))
+
+DownloadQuery::DownloadQuery()
+  : limit_(kuint32max),
+    delete_sort_fields_(&sort_fields_),
+    delete_filter_fields_(&filter_fields_) {
+  // All sort fields are also filter fields, but not all filter fields are sort
+  // fields.
+  // If you define a new sort or filter field, make sure that the type is
+  // enumerated in INSTANTIATE_SET below.
+  SORT_FIELD(startTime, int, get_start_time(item));
+  SORT_FIELD(url, std::string, item.original_url().spec());
+  SORT_FIELD(filename, string16, get_filename(item));
+  SORT_FIELD(danger, DownloadItem::DangerType, item.GetDangerType());
+  SORT_FIELD(dangerAccepted, bool, get_danger_accepted(item));
+  SORT_FIELD(state, DownloadItem::DownloadState, item.state());
+  SORT_FIELD(paused, bool, item.is_paused());
+  SORT_FIELD(mime, std::string, item.mime_type());
+  SORT_FIELD(endTime, int, get_end_time(item));
+  SORT_FIELD(bytesReceived, int, item.received_bytes());
+  SORT_FIELD(totalBytes, int, item.total_bytes());
+  SORT_FIELD(fileSize, int, 0);  // TODO
+  SORT_FIELD(error, int, 0);  // TODO
+
+  FILTER_FIELD(startedBefore, int, get_start_time(item) < value());
+  FILTER_FIELD(startedAfter, int, get_start_time(item) > value());
+  FILTER_FIELD(endedBefore, int, get_end_time(item) < value());
+  FILTER_FIELD(endedAfter, int, get_end_time(item) > value());
+  FILTER_FIELD(totalBytesGreater, int, item.total_bytes() > value());
+  FILTER_FIELD(totalBytesLess, int, item.total_bytes() < value());
+  FILTER_FIELD(fileSizeGreater, int, false);  // TODO
+  FILTER_FIELD(fileSizeLess, int, false);  // TODO
+  FILTER_FIELD(filter, base::Callback<bool(const DownloadItem& item)>,
+               value().Run(item));
+
+  filter_fields_["query"] = new FilterFieldQuery();
+  filter_fields_["filenameRegex"] = new FilterFieldFilenameRegex();
+  filter_fields_["urlRegex"] = new FilterFieldUrlRegex();
+}
+
+#undef FILTER_FIELD
+#undef SORT_FIELD
+
+DownloadQuery::~DownloadQuery() {
+}
+
+template <typename ValueType>
+bool DownloadQuery::Set(const char* name, const ValueType& value) {
+  FilterFields::iterator iter = filter_fields_.find(name);
+  return (iter != filter_fields_.end()) &&
+         (iter->second != NULL) &&
+         (iter->second->name() == name) &&
+         static_cast<FilterField<ValueType>*>(iter->second)->Set(value);
+}
+
+#define INSTANTIATE_SET(type) \
+  template bool DownloadQuery::Set(const char* name, const type& value)
+INSTANTIATE_SET(int);
+INSTANTIATE_SET(bool);
+INSTANTIATE_SET(std::string);
+INSTANTIATE_SET(string16);
+INSTANTIATE_SET(base::Callback<bool(const DownloadItem& item)>);
+INSTANTIATE_SET(DownloadItem::DownloadState);
+INSTANTIATE_SET(DownloadItem::DangerType);
+#undef INSTANTIATE_SET
+
+bool DownloadQuery::Matches(const DownloadItem& item) const {
+  for (FilterFields::const_iterator filter_field = filter_fields_.begin();
+        filter_field != filter_fields_.end(); ++filter_field) {
+    if (filter_field->second->is_set() && !filter_field->second->Matches(item))
+      return false;
+  }
+  return true;
+}
+
+bool DownloadQuery::OrderBy(const std::string& order_by) {
+  order_by_fields_.clear();
+  base::SplitString(order_by, ' ', &order_by_fields_);
+  for (Strings::const_iterator field = order_by_fields_.begin();
+       field != order_by_fields_.end(); ++field) {
+    if (sort_fields_.find(DownloadComparator::Revert(*field, NULL)) ==
+        sort_fields_.end()) {
+      order_by_fields_.clear();
+      return false;
+    }
+  }
+  return true;
+}
+
+void DownloadQuery::Search(const DownloadQuery::DownloadItems& all_items,
+                           DownloadQuery::DownloadItems* results) const {
+  results->clear();
+  for (DownloadItems::const_iterator item = all_items.begin();
+       item != all_items.end(); ++item) {
+    if (Matches(**item))
+      results->push_back(*item);
+  }
+  if (!order_by_fields_.empty())
+    std::sort(results->begin(), results->end(),
+              DownloadComparator(order_by_fields_, sort_fields_));

[Randy Smith (Not in Mondays), 2011/10/18 23:58:46]

partial sort, so we don't take quite as big a hit where the results of the
matches will be large, but we're limiting?

+  if (results->size() > limit_)
+    results->resize(limit_);
+}
+
+}  // namespace download_util
+