chrome/browser/chromeos/drive/search_metadata.cc

   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/chromeos/drive/search_metadata.h"
   6
   7 #include <algorithm>
   8 #include <queue>
   9
  10 #include "base/bind.h"
  11 #include "base/i18n/string_search.h"
  12 #include "base/metrics/histogram.h"
  13 #include "base/strings/utf_string_conversions.h"
  14 #include "base/time/time.h"
  15 #include "chrome/browser/chromeos/drive/file_system_core_util.h"
  16 #include "components/drive/drive_api_util.h"
  17 #include "net/base/escape.h"
  18
  19 namespace drive {
  20 namespace internal {
  21
  22 namespace {
  23
  24 struct ResultCandidate {
  25   ResultCandidate(const std::string& local_id,
  26                   const ResourceEntry& entry,
  27                   const std::string& highlighted_base_name)
  28       : local_id(local_id),
  29         entry(entry),
  30         highlighted_base_name(highlighted_base_name) {
  31   }
  32
  33   std::string local_id;
  34   ResourceEntry entry;
  35   std::string highlighted_base_name;
  36 };
  37
  38 // Used to sort the result candidates per the last accessed/modified time. The
  39 // recently accessed/modified files come first.
  40 bool CompareByTimestamp(const ResourceEntry& a, const ResourceEntry& b) {
  41   const PlatformFileInfoProto& a_file_info = a.file_info();
  42   const PlatformFileInfoProto& b_file_info = b.file_info();
  43
  44   if (a_file_info.last_accessed() != b_file_info.last_accessed())
  45     return a_file_info.last_accessed() > b_file_info.last_accessed();
  46
  47   // When the entries have the same last access time (which happens quite often
  48   // because Drive server doesn't set the field until an entry is viewed via
  49   // drive.google.com), we use last modified time as the tie breaker.
  50   return a_file_info.last_modified() > b_file_info.last_modified();
  51 }
  52
  53 struct ResultCandidateComparator {
  54   bool operator()(const ResultCandidate* a, const ResultCandidate* b) const {
  55     return CompareByTimestamp(a->entry, b->entry);
  56   }
  57 };
  58
  59 // A wrapper of std::priority_queue which deals with pointers of values.
  60 template<typename T, typename Compare>
  61 class ScopedPriorityQueue {
  62  public:
  63   ScopedPriorityQueue() {}
  64
  65   ~ScopedPriorityQueue() {
  66     while (!empty())
  67       pop();
  68   }
  69
  70   bool empty() const { return queue_.empty(); }
  71
  72   size_t size() const { return queue_.size(); }
  73
  74   const T* top() const { return queue_.top(); }
  75
  76   void push(T* x) { queue_.push(x); }
  77
  78   void pop() {
  79     // Keep top alive for the pop() call so that debug checks can access
  80     // underlying data (e.g. validating heap property of the priority queue
  81     // will call the comparator).
  82     T* saved_top = queue_.top();
  83     queue_.pop();
  84     delete saved_top;
  85   }
  86
  87  private:
  88   std::priority_queue<T*, std::vector<T*>, Compare> queue_;
  89
  90   DISALLOW_COPY_AND_ASSIGN(ScopedPriorityQueue);
  91 };
  92
  93 // Classifies the given entry as hidden if it's not under specific directories.
  94 class HiddenEntryClassifier {
  95  public:
  96   HiddenEntryClassifier(ResourceMetadata* metadata,
  97                         const std::string& mydrive_local_id)
  98       : metadata_(metadata) {
  99     // Only things under My Drive and drive/other are not hidden.
 100     is_hiding_child_[mydrive_local_id] = false;
 101     is_hiding_child_[util::kDriveOtherDirLocalId] = false;
 102
 103     // Everything else is hidden, including the directories mentioned above
 104     // themselves.
 105     is_hiding_child_[""] = true;
 106   }
 107
 108   // |result| is set to true if |entry| is hidden.
 109   FileError IsHidden(const ResourceEntry& entry, bool* result) {
 110     // Look up for parents recursively.
 111     std::vector<std::string> undetermined_ids;
 112     undetermined_ids.push_back(entry.parent_local_id());
 113
 114     std::map<std::string, bool>::iterator it =
 115         is_hiding_child_.find(undetermined_ids.back());
 116     for (; it == is_hiding_child_.end();
 117          it = is_hiding_child_.find(undetermined_ids.back())) {
 118       ResourceEntry parent;
 119       FileError error =
 120           metadata_->GetResourceEntryById(undetermined_ids.back(), &parent);
 121       if (error != FILE_ERROR_OK)
 122         return error;
 123       undetermined_ids.push_back(parent.parent_local_id());
 124     }
 125
 126     // Cache the result.
 127     undetermined_ids.pop_back();  // The last one is already in the map.
 128     for (size_t i = 0; i < undetermined_ids.size(); ++i)
 129       is_hiding_child_[undetermined_ids[i]] = it->second;
 130
 131     *result = it->second;
 132     return FILE_ERROR_OK;
 133   }
 134
 135  private:
 136   ResourceMetadata* metadata_;
 137
 138   // local ID to is_hidden map.
 139   std::map<std::string, bool> is_hiding_child_;
 140 };
 141
 142 // Used to implement SearchMetadata.
 143 // Adds entry to the result when appropriate.
 144 // In particular, if |query| is non-null, only adds files with the name matching
 145 // the query.
 146 FileError MaybeAddEntryToResult(
 147     ResourceMetadata* resource_metadata,
 148     ResourceMetadata::Iterator* it,
 149     base::i18n::FixedPatternStringSearchIgnoringCaseAndAccents* query,
 150     const SearchMetadataPredicate& predicate,
 151     size_t at_most_num_matches,
 152     HiddenEntryClassifier* hidden_entry_classifier,
 153     ScopedPriorityQueue<ResultCandidate, ResultCandidateComparator>*
 154         result_candidates) {
 155   DCHECK_GE(at_most_num_matches, result_candidates->size());
 156
 157   const ResourceEntry& entry = it->GetValue();
 158
 159   // If the candidate set is already full, and this |entry| is old, do nothing.
 160   // We perform this check first in order to avoid the costly find-and-highlight
 161   // or FilePath lookup as much as possible.
 162   if (result_candidates->size() == at_most_num_matches &&
 163       !CompareByTimestamp(entry, result_candidates->top()->entry))
 164     return FILE_ERROR_OK;
 165
 166   // Add |entry| to the result if the entry is eligible for the given
 167   // |options| and matches the query. The base name of the entry must
 168   // contain |query| to match the query.
 169   std::string highlighted;
 170   if (!predicate.Run(entry) ||
 171       (query && !FindAndHighlight(entry.base_name(), query, &highlighted)))
 172     return FILE_ERROR_OK;
 173
 174   // Hidden entry should not be returned.
 175   bool hidden = false;
 176   FileError error = hidden_entry_classifier->IsHidden(entry, &hidden);
 177   if (error != FILE_ERROR_OK || hidden)
 178     return error;
 179
 180   // Make space for |entry| when appropriate.
 181   if (result_candidates->size() == at_most_num_matches)
 182     result_candidates->pop();
 183   result_candidates->push(new ResultCandidate(it->GetID(), entry, highlighted));
 184   return FILE_ERROR_OK;
 185 }
 186
 187 // Implements SearchMetadata().
 188 FileError SearchMetadataOnBlockingPool(ResourceMetadata* resource_metadata,
 189                                        const std::string& query_text,
 190                                        const SearchMetadataPredicate& predicate,
 191                                        int at_most_num_matches,
 192                                        MetadataSearchResultVector* results) {
 193   ScopedPriorityQueue<ResultCandidate,
 194                       ResultCandidateComparator> result_candidates;
 195
 196   // Prepare data structure for searching.
 197   base::i18n::FixedPatternStringSearchIgnoringCaseAndAccents query(
 198       base::UTF8ToUTF16(query_text));
 199
 200   // Prepare an object to filter out hidden entries.
 201   ResourceEntry mydrive;
 202   FileError error = resource_metadata->GetResourceEntryByPath(
 203       util::GetDriveMyDriveRootPath(), &mydrive);
 204   if (error != FILE_ERROR_OK)
 205     return error;
 206   HiddenEntryClassifier hidden_entry_classifier(resource_metadata,
 207                                                 mydrive.local_id());
 208
 209   // Iterate over entries.
 210   scoped_ptr<ResourceMetadata::Iterator> it = resource_metadata->GetIterator();
 211   for (; !it->IsAtEnd(); it->Advance()) {
 212     FileError error = MaybeAddEntryToResult(
 213         resource_metadata, it.get(), query_text.empty() ? NULL : &query,
 214         predicate, at_most_num_matches, &hidden_entry_classifier,
 215         &result_candidates);
 216     if (error != FILE_ERROR_OK)
 217       return error;
 218   }
 219
 220   // Prepare the result.
 221   for (; !result_candidates.empty(); result_candidates.pop()) {
 222     const ResultCandidate& candidate = *result_candidates.top();
 223     // The path field of entries in result_candidates are empty at this point,
 224     // because we don't want to run the expensive metadata DB look up except for
 225     // the final results. Hence, here we fill the part.
 226     base::FilePath path;
 227     error = resource_metadata->GetFilePath(candidate.local_id, &path);
 228     if (error != FILE_ERROR_OK)
 229       return error;
 230     bool is_directory = candidate.entry.file_info().is_directory();
 231     results->push_back(MetadataSearchResult(
 232         path, is_directory, candidate.highlighted_base_name,
 233         candidate.entry.file_specific_info().md5()));
 234   }
 235
 236   // Reverse the order here because |result_candidates| puts the most
 237   // uninteresting candidate at the top.
 238   std::reverse(results->begin(), results->end());
 239
 240   return FILE_ERROR_OK;
 241 }
 242
 243 // Runs the SearchMetadataCallback and updates the histogram.
 244 void RunSearchMetadataCallback(const SearchMetadataCallback& callback,
 245                                const base::TimeTicks& start_time,
 246                                scoped_ptr<MetadataSearchResultVector> results,
 247                                FileError error) {
 248   if (error != FILE_ERROR_OK)
 249     results.reset();
 250   callback.Run(error, results.Pass());
 251
 252   UMA_HISTOGRAM_TIMES("Drive.SearchMetadataTime",
 253                       base::TimeTicks::Now() - start_time);
 254 }
 255
 256 }  // namespace
 257
 258 void SearchMetadata(
 259     scoped_refptr<base::SequencedTaskRunner> blocking_task_runner,
 260     ResourceMetadata* resource_metadata,
 261     const std::string& query,
 262     const SearchMetadataPredicate& predicate,
 263     size_t at_most_num_matches,
 264     const SearchMetadataCallback& callback) {
 265   DCHECK(!callback.is_null());
 266
 267   const base::TimeTicks start_time = base::TimeTicks::Now();
 268
 269   scoped_ptr<MetadataSearchResultVector> results(
 270       new MetadataSearchResultVector);
 271   MetadataSearchResultVector* results_ptr = results.get();
 272   base::PostTaskAndReplyWithResult(
 273       blocking_task_runner.get(), FROM_HERE,
 274       base::Bind(&SearchMetadataOnBlockingPool, resource_metadata, query,
 275                  predicate, at_most_num_matches, results_ptr),
 276       base::Bind(&RunSearchMetadataCallback, callback, start_time,
 277                  base::Passed(&results)));
 278 }
 279
 280 bool MatchesType(int options, const ResourceEntry& entry) {
 281   if ((options & SEARCH_METADATA_EXCLUDE_HOSTED_DOCUMENTS) &&
 282       entry.file_specific_info().is_hosted_document())
 283     return false;
 284
 285   if ((options & SEARCH_METADATA_EXCLUDE_DIRECTORIES) &&
 286       entry.file_info().is_directory())
 287     return false;
 288
 289   if (options & SEARCH_METADATA_SHARED_WITH_ME)
 290     return entry.shared_with_me();
 291
 292   if (options & SEARCH_METADATA_OFFLINE) {
 293     if (entry.file_specific_info().is_hosted_document()) {
 294       // Not all hosted documents are cached by Drive offline app.
 295       // https://support.google.com/drive/answer/2375012
 296       std::string mime_type = entry.file_specific_info().content_mime_type();
 297       return mime_type == drive::util::kGoogleDocumentMimeType ||
 298              mime_type == drive::util::kGoogleSpreadsheetMimeType ||
 299              mime_type == drive::util::kGooglePresentationMimeType ||
 300              mime_type == drive::util::kGoogleDrawingMimeType;
 301     } else {
 302       return entry.file_specific_info().cache_state().is_present();
 303     }
 304   }
 305
 306   return true;
 307 }
 308
 309 bool FindAndHighlight(
 310     const std::string& text,
 311     base::i18n::FixedPatternStringSearchIgnoringCaseAndAccents* query,
 312     std::string* highlighted_text) {
 313   DCHECK(query);
 314   DCHECK(highlighted_text);
 315   highlighted_text->clear();
 316
 317   base::string16 text16 = base::UTF8ToUTF16(text);
 318   size_t match_start = 0;
 319   size_t match_length = 0;
 320   if (!query->Search(text16, &match_start, &match_length))
 321     return false;
 322
 323   base::string16 pre = text16.substr(0, match_start);
 324   base::string16 match = text16.substr(match_start, match_length);
 325   base::string16 post = text16.substr(match_start + match_length);
 326   highlighted_text->append(net::EscapeForHTML(base::UTF16ToUTF8(pre)));
 327   highlighted_text->append("<b>");
 328   highlighted_text->append(net::EscapeForHTML(base::UTF16ToUTF8(match)));
 329   highlighted_text->append("</b>");
 330   highlighted_text->append(net::EscapeForHTML(base::UTF16ToUTF8(post)));
 331   return true;
 332 }
 333
 334 }  // namespace internal
 335 }  // namespace drive