chrome/browser/devtools/devtools_file_system_indexer.cc

   1 // Copyright 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/devtools/devtools_file_system_indexer.h"
   6
   7 #include <iterator>
   8
   9 #include "base/bind.h"
  10 #include "base/callback.h"
  11 #include "base/file_util.h"
  12 #include "base/files/file_enumerator.h"
  13 #include "base/files/file_util_proxy.h"
  14 #include "base/lazy_instance.h"
  15 #include "base/logging.h"
  16 #include "base/platform_file.h"
  17 #include "base/strings/utf_string_conversions.h"
  18 #include "content/public/browser/browser_thread.h"
  19
  20 using base::Bind;
  21 using base::Callback;
  22 using base::FileEnumerator;
  23 using base::FilePath;
  24 using base::Time;
  25 using base::TimeDelta;
  26 using base::TimeTicks;
  27 using base::PassPlatformFile;
  28 using base::PlatformFile;
  29 using content::BrowserThread;
  30 using std::map;
  31 using std::set;
  32 using std::string;
  33 using std::vector;
  34
  35 namespace {
  36
  37 typedef int32 Trigram;
  38 typedef char TrigramChar;
  39 typedef uint16 FileId;
  40
  41 const int kMinTimeoutBetweenWorkedNitification = 200;
  42 // Trigram characters include all ASCII printable characters (32-126) except for
  43 // the capital letters, because the index is case insensitive.
  44 const size_t kTrigramCharacterCount = 126 - 'Z' - 1 + 'A' - ' ' + 1;
  45 const size_t kTrigramCount =
  46     kTrigramCharacterCount * kTrigramCharacterCount * kTrigramCharacterCount;
  47 const int kMaxReadLength = 10 * 1024;
  48 const TrigramChar kUndefinedTrigramChar = -1;
  49 const Trigram kUndefinedTrigram = -1;
  50
  51 base::LazyInstance<vector<bool> >::Leaky g_is_binary_char =
  52     LAZY_INSTANCE_INITIALIZER;
  53
  54 base::LazyInstance<vector<TrigramChar> >::Leaky g_trigram_chars =
  55     LAZY_INSTANCE_INITIALIZER;
  56
  57 class Index {
  58  public:
  59   Index();
  60   Time LastModifiedTimeForFile(const FilePath& file_path);
  61   void SetTrigramsForFile(const FilePath& file_path,
  62                           const vector<Trigram>& index,
  63                           const Time& time);
  64   vector<FilePath> Search(string query);
  65   void PrintStats();
  66   void NormalizeVectors();
  67
  68  private:
  69   ~Index();
  70
  71   FileId GetFileId(const FilePath& file_path);
  72
  73   typedef map<FilePath, FileId> FileIdsMap;
  74   FileIdsMap file_ids_;
  75   FileId last_file_id_;
  76   // The index in this vector is the trigram id.
  77   vector<vector<FileId> > index_;
  78   typedef map<FilePath, Time> IndexedFilesMap;
  79   IndexedFilesMap index_times_;
  80   vector<bool> is_normalized_;
  81
  82   DISALLOW_COPY_AND_ASSIGN(Index);
  83 };
  84
  85 base::LazyInstance<Index>::Leaky g_trigram_index = LAZY_INSTANCE_INITIALIZER;
  86
  87 void InitIsBinaryCharMap() {
  88   for (size_t i = 0; i < 256; ++i) {
  89     unsigned char ch = i;
  90     bool is_binary_char = ch < 9 || (ch >= 14 && ch < 32) || ch == 127;
  91     g_is_binary_char.Get().push_back(is_binary_char);
  92   }
  93 }
  94
  95 bool IsBinaryChar(char c) {
  96   unsigned char uc = static_cast<unsigned char>(c);
  97   return g_is_binary_char.Get()[uc];
  98 }
  99
 100 void InitTrigramCharsMap() {
 101   for (size_t i = 0; i < 256; ++i) {
 102     if (i > 127) {
 103       g_trigram_chars.Get().push_back(kUndefinedTrigramChar);
 104       continue;
 105     }
 106     char ch = i;
 107     if (ch == '\t')
 108       ch = ' ';
 109     if (ch >= 'A' && ch <= 'Z')
 110       ch = ch - 'A' + 'a';
 111     if ((IsBinaryChar(ch)) || (ch < ' ')) {
 112       g_trigram_chars.Get().push_back(kUndefinedTrigramChar);
 113       continue;
 114     }
 115
 116     if (ch >= 'Z')
 117       ch = ch - 'Z' - 1 + 'A';
 118     ch -= ' ';
 119     char signed_trigram_char_count = static_cast<char>(kTrigramCharacterCount);
 120     CHECK(ch >= 0 && ch < signed_trigram_char_count);
 121     g_trigram_chars.Get().push_back(ch);
 122   }
 123 }
 124
 125 TrigramChar TrigramCharForChar(char c) {
 126   unsigned char uc = static_cast<unsigned char>(c);
 127   return g_trigram_chars.Get()[uc];
 128 }
 129
 130 Trigram TrigramAtIndex(const vector<TrigramChar>& trigram_chars, size_t index) {
 131   static int kTrigramCharacterCountSquared =
 132       kTrigramCharacterCount * kTrigramCharacterCount;
 133   if (trigram_chars[index] == kUndefinedTrigramChar ||
 134       trigram_chars[index + 1] == kUndefinedTrigramChar ||
 135       trigram_chars[index + 2] == kUndefinedTrigramChar)
 136     return kUndefinedTrigram;
 137   Trigram trigram = kTrigramCharacterCountSquared * trigram_chars[index] +
 138                     kTrigramCharacterCount * trigram_chars[index + 1] +
 139                     trigram_chars[index + 2];
 140   return trigram;
 141 }
 142
 143 Index::Index() : last_file_id_(0) {
 144   index_.resize(kTrigramCount);
 145   is_normalized_.resize(kTrigramCount);
 146   std::fill(is_normalized_.begin(), is_normalized_.end(), true);
 147 }
 148
 149 Index::~Index() {}
 150
 151 Time Index::LastModifiedTimeForFile(const FilePath& file_path) {
 152   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 153   Time last_modified_time;
 154   if (index_times_.find(file_path) != index_times_.end())
 155     last_modified_time = index_times_[file_path];
 156   return last_modified_time;
 157 }
 158
 159 void Index::SetTrigramsForFile(const FilePath& file_path,
 160                                const vector<Trigram>& index,
 161                                const Time& time) {
 162   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 163   FileId file_id = GetFileId(file_path);
 164   vector<Trigram>::const_iterator it = index.begin();
 165   for (; it != index.end(); ++it) {
 166     Trigram trigram = *it;
 167     index_[trigram].push_back(file_id);
 168     is_normalized_[trigram] = false;
 169   }
 170   index_times_[file_path] = time;
 171 }
 172
 173 vector<FilePath> Index::Search(string query) {
 174   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 175   const char* data = query.c_str();
 176   vector<TrigramChar> trigram_chars;
 177   trigram_chars.reserve(query.size());
 178   for (size_t i = 0; i < query.size(); ++i)
 179       trigram_chars.push_back(TrigramCharForChar(data[i]));
 180   vector<Trigram> trigrams;
 181   for (size_t i = 0; i + 2 < query.size(); ++i) {
 182     Trigram trigram = TrigramAtIndex(trigram_chars, i);
 183     if (trigram != kUndefinedTrigram)
 184       trigrams.push_back(trigram);
 185   }
 186   set<FileId> file_ids;
 187   bool first = true;
 188   vector<Trigram>::const_iterator it = trigrams.begin();
 189   for (; it != trigrams.end(); ++it) {
 190     Trigram trigram = *it;
 191     if (first) {
 192       std::copy(index_[trigram].begin(),
 193                 index_[trigram].end(),
 194                 std::inserter(file_ids, file_ids.begin()));
 195       first = false;
 196       continue;
 197     }
 198     set<FileId> intersection;
 199     std::set_intersection(file_ids.begin(),
 200                           file_ids.end(),
 201                           index_[trigram].begin(),
 202                           index_[trigram].end(),
 203                           std::inserter(intersection, intersection.begin()));
 204     file_ids.swap(intersection);
 205   }
 206   vector<FilePath> result;
 207   FileIdsMap::const_iterator ids_it = file_ids_.begin();
 208   for (; ids_it != file_ids_.end(); ++ids_it) {
 209     if (trigrams.size() == 0 ||
 210         file_ids.find(ids_it->second) != file_ids.end()) {
 211       result.push_back(ids_it->first);
 212     }
 213   }
 214   return result;
 215 }
 216
 217 FileId Index::GetFileId(const FilePath& file_path) {
 218   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 219   string file_path_str = file_path.AsUTF8Unsafe();
 220   if (file_ids_.find(file_path) != file_ids_.end())
 221     return file_ids_[file_path];
 222   file_ids_[file_path] = ++last_file_id_;
 223   return last_file_id_;
 224 }
 225
 226 void Index::NormalizeVectors() {
 227   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 228   for (size_t i = 0; i < kTrigramCount; ++i) {
 229     if (!is_normalized_[i]) {
 230       std::sort(index_[i].begin(), index_[i].end());
 231       if (index_[i].capacity() > index_[i].size())
 232         vector<FileId>(index_[i]).swap(index_[i]);
 233       is_normalized_[i] = true;
 234     }
 235   }
 236 }
 237
 238 void Index::PrintStats() {
 239   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 240   LOG(ERROR) << "Index stats:";
 241   size_t size = 0;
 242   size_t maxSize = 0;
 243   size_t capacity = 0;
 244   for (size_t i = 0; i < kTrigramCount; ++i) {
 245     if (index_[i].size() > maxSize)
 246       maxSize = index_[i].size();
 247     size += index_[i].size();
 248     capacity += index_[i].capacity();
 249   }
 250   LOG(ERROR) << "  - total trigram count: " << size;
 251   LOG(ERROR) << "  - max file count per trigram: " << maxSize;
 252   LOG(ERROR) << "  - total vectors capacity " << capacity;
 253   size_t total_index_size =
 254       capacity * sizeof(FileId) + sizeof(vector<FileId>) * kTrigramCount;
 255   LOG(ERROR) << "  - estimated total index size " << total_index_size;
 256 }
 257
 258 typedef Callback<void(bool, const vector<bool>&)> IndexerCallback;
 259
 260 }  // namespace
 261
 262 DevToolsFileSystemIndexer::FileSystemIndexingJob::FileSystemIndexingJob(
 263     const FilePath& file_system_path,
 264     const TotalWorkCallback& total_work_callback,
 265     const WorkedCallback& worked_callback,
 266     const DoneCallback& done_callback)
 267     : file_system_path_(file_system_path),
 268       total_work_callback_(total_work_callback),
 269       worked_callback_(worked_callback),
 270       done_callback_(done_callback),
 271       current_file_(BrowserThread::GetMessageLoopProxyForThread(
 272                         BrowserThread::FILE).get()),
 273       files_indexed_(0),
 274       stopped_(false) {
 275   current_trigrams_set_.resize(kTrigramCount);
 276   current_trigrams_.reserve(kTrigramCount);
 277 }
 278
 279 DevToolsFileSystemIndexer::FileSystemIndexingJob::~FileSystemIndexingJob() {}
 280
 281 void DevToolsFileSystemIndexer::FileSystemIndexingJob::Start() {
 282   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 283   BrowserThread::PostTask(
 284       BrowserThread::FILE,
 285       FROM_HERE,
 286       Bind(&FileSystemIndexingJob::CollectFilesToIndex, this));
 287 }
 288
 289 void DevToolsFileSystemIndexer::FileSystemIndexingJob::Stop() {
 290   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 291   BrowserThread::PostTask(BrowserThread::FILE,
 292                           FROM_HERE,
 293                           Bind(&FileSystemIndexingJob::StopOnFileThread, this));
 294 }
 295
 296 void DevToolsFileSystemIndexer::FileSystemIndexingJob::StopOnFileThread() {
 297   stopped_ = true;
 298 }
 299
 300 void DevToolsFileSystemIndexer::FileSystemIndexingJob::CollectFilesToIndex() {
 301   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 302   if (stopped_)
 303     return;
 304   if (!file_enumerator_) {
 305     file_enumerator_.reset(
 306         new FileEnumerator(file_system_path_, true, FileEnumerator::FILES));
 307   }
 308   FilePath file_path = file_enumerator_->Next();
 309   if (file_path.empty()) {
 310     BrowserThread::PostTask(
 311         BrowserThread::UI,
 312         FROM_HERE,
 313         Bind(total_work_callback_, file_path_times_.size()));
 314     indexing_it_ = file_path_times_.begin();
 315     IndexFiles();
 316     return;
 317   }
 318   Time saved_last_modified_time =
 319       g_trigram_index.Get().LastModifiedTimeForFile(file_path);
 320   FileEnumerator::FileInfo file_info = file_enumerator_->GetInfo();
 321   Time current_last_modified_time = file_info.GetLastModifiedTime();
 322   if (current_last_modified_time > saved_last_modified_time) {
 323     file_path_times_[file_path] = current_last_modified_time;
 324   }
 325   BrowserThread::PostTask(
 326       BrowserThread::FILE,
 327       FROM_HERE,
 328       Bind(&FileSystemIndexingJob::CollectFilesToIndex, this));
 329 }
 330
 331 void DevToolsFileSystemIndexer::FileSystemIndexingJob::IndexFiles() {
 332   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 333   if (stopped_)
 334     return;
 335   if (indexing_it_ == file_path_times_.end()) {
 336     g_trigram_index.Get().NormalizeVectors();
 337     BrowserThread::PostTask(BrowserThread::UI, FROM_HERE, done_callback_);
 338     return;
 339   }
 340   FilePath file_path = indexing_it_->first;
 341   current_file_.CreateOrOpen(
 342         file_path,
 343         base::File::FLAG_OPEN | base::File::FLAG_READ,
 344         Bind(&FileSystemIndexingJob::StartFileIndexing, this));
 345 }
 346
 347 void DevToolsFileSystemIndexer::FileSystemIndexingJob::StartFileIndexing(
 348     base::File::Error error) {
 349   if (!current_file_.IsValid()) {
 350     FinishFileIndexing(false);
 351     return;
 352   }
 353   current_file_offset_ = 0;
 354   current_trigrams_.clear();
 355   std::fill(current_trigrams_set_.begin(), current_trigrams_set_.end(), false);
 356   ReadFromFile();
 357 }
 358
 359 void DevToolsFileSystemIndexer::FileSystemIndexingJob::ReadFromFile() {
 360   if (stopped_) {
 361     CloseFile();
 362     return;
 363   }
 364   current_file_.Read(current_file_offset_, kMaxReadLength,
 365                      Bind(&FileSystemIndexingJob::OnRead, this));
 366 }
 367
 368 void DevToolsFileSystemIndexer::FileSystemIndexingJob::OnRead(
 369     base::File::Error error,
 370     const char* data,
 371     int bytes_read) {
 372   if (error != base::File::FILE_OK) {
 373     FinishFileIndexing(false);
 374     return;
 375   }
 376
 377   if (!bytes_read || bytes_read < 3) {
 378     FinishFileIndexing(true);
 379     return;
 380   }
 381
 382   size_t size = static_cast<size_t>(bytes_read);
 383   vector<TrigramChar> trigram_chars;
 384   trigram_chars.reserve(size);
 385   for (size_t i = 0; i < size; ++i) {
 386     if (IsBinaryChar(data[i])) {
 387       current_trigrams_.clear();
 388       FinishFileIndexing(true);
 389       return;
 390     }
 391     trigram_chars.push_back(TrigramCharForChar(data[i]));
 392   }
 393
 394   for (size_t i = 0; i + 2 < size; ++i) {
 395     Trigram trigram = TrigramAtIndex(trigram_chars, i);
 396     if ((trigram != kUndefinedTrigram) && !current_trigrams_set_[trigram]) {
 397       current_trigrams_set_[trigram] = true;
 398       current_trigrams_.push_back(trigram);
 399     }
 400   }
 401   current_file_offset_ += bytes_read - 2;
 402   ReadFromFile();
 403 }
 404
 405 void DevToolsFileSystemIndexer::FileSystemIndexingJob::FinishFileIndexing(
 406     bool success) {
 407   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 408   CloseFile();
 409   if (success) {
 410     FilePath file_path = indexing_it_->first;
 411     g_trigram_index.Get().SetTrigramsForFile(
 412         file_path, current_trigrams_, file_path_times_[file_path]);
 413   }
 414   ReportWorked();
 415   ++indexing_it_;
 416   IndexFiles();
 417 }
 418
 419 void DevToolsFileSystemIndexer::FileSystemIndexingJob::CloseFile() {
 420   if (current_file_.IsValid())
 421     current_file_.Close(Bind(&FileSystemIndexingJob::CloseCallback, this));
 422 }
 423
 424 void DevToolsFileSystemIndexer::FileSystemIndexingJob::CloseCallback(
 425     base::File::Error error) {}
 426
 427 void DevToolsFileSystemIndexer::FileSystemIndexingJob::ReportWorked() {
 428   TimeTicks current_time = TimeTicks::Now();
 429   bool should_send_worked_nitification = true;
 430   if (!last_worked_notification_time_.is_null()) {
 431     TimeDelta delta = current_time - last_worked_notification_time_;
 432     if (delta.InMilliseconds() < kMinTimeoutBetweenWorkedNitification)
 433       should_send_worked_nitification = false;
 434   }
 435   ++files_indexed_;
 436   if (should_send_worked_nitification) {
 437     last_worked_notification_time_ = current_time;
 438     BrowserThread::PostTask(
 439         BrowserThread::UI, FROM_HERE, Bind(worked_callback_, files_indexed_));
 440     files_indexed_ = 0;
 441   }
 442 }
 443
 444 DevToolsFileSystemIndexer::DevToolsFileSystemIndexer() {
 445   static bool maps_initialized = false;
 446   if (!maps_initialized) {
 447     InitIsBinaryCharMap();
 448     InitTrigramCharsMap();
 449     maps_initialized = true;
 450   }
 451 }
 452
 453 DevToolsFileSystemIndexer::~DevToolsFileSystemIndexer() {}
 454
 455 scoped_refptr<DevToolsFileSystemIndexer::FileSystemIndexingJob>
 456 DevToolsFileSystemIndexer::IndexPath(
 457     const string& file_system_path,
 458     const TotalWorkCallback& total_work_callback,
 459     const WorkedCallback& worked_callback,
 460     const DoneCallback& done_callback) {
 461   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 462   scoped_refptr<FileSystemIndexingJob> indexing_job =
 463       new FileSystemIndexingJob(FilePath::FromUTF8Unsafe(file_system_path),
 464                                 total_work_callback,
 465                                 worked_callback,
 466                                 done_callback);
 467   indexing_job->Start();
 468   return indexing_job;
 469 }
 470
 471 void DevToolsFileSystemIndexer::SearchInPath(const string& file_system_path,
 472                                              const string& query,
 473                                              const SearchCallback& callback) {
 474   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::UI));
 475   BrowserThread::PostTask(
 476       BrowserThread::FILE,
 477       FROM_HERE,
 478       Bind(&DevToolsFileSystemIndexer::SearchInPathOnFileThread,
 479            this,
 480            file_system_path,
 481            query,
 482            callback));
 483 }
 484
 485 void DevToolsFileSystemIndexer::SearchInPathOnFileThread(
 486     const string& file_system_path,
 487     const string& query,
 488     const SearchCallback& callback) {
 489   DCHECK(BrowserThread::CurrentlyOn(BrowserThread::FILE));
 490   vector<FilePath> file_paths = g_trigram_index.Get().Search(query);
 491   vector<string> result;
 492   FilePath path = FilePath::FromUTF8Unsafe(file_system_path);
 493   vector<FilePath>::const_iterator it = file_paths.begin();
 494   for (; it != file_paths.end(); ++it) {
 495     if (path.IsParent(*it))
 496       result.push_back(it->AsUTF8Unsafe());
 497   }
 498   BrowserThread::PostTask(BrowserThread::UI, FROM_HERE, Bind(callback, result));
 499 }