chrome/browser/media_galleries/media_scan_manager.cc - platform/external/chromium_org - Git at Google

 // Copyright 2014 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 "chrome/browser/media_galleries/media_scan_manager.h"

 #include "base/files/file_enumerator.h"
 #include "base/files/file_util.h"
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
 #include "base/time/time.h"
 #include "chrome/browser/extensions/extension_service.h"
 #include "chrome/browser/media_galleries/media_galleries_preferences.h"
 #include "chrome/browser/media_galleries/media_galleries_preferences_factory.h"
 #include "chrome/browser/media_galleries/media_scan_manager_observer.h"
 #include "chrome/browser/profiles/profile.h"
 #include "chrome/common/extensions/api/media_galleries.h"
 #include "content/public/browser/browser_thread.h"
 #include "extensions/browser/extension_registry.h"
 #include "extensions/browser/extension_system.h"
 #include "extensions/common/extension.h"

 using extensions::ExtensionRegistry;

 namespace media_galleries = extensions::api::media_galleries;

 namespace {

 typedef std::set<std::string /*extension id*/> ScanningExtensionIdSet;

 // When multiple scan results have the same parent, sometimes it makes sense
 // to combine them into a single scan result at the parent. This constant
 // governs when that happens; kContainerDirectoryMinimumPercent percent of the
 // directories in the parent directory must be scan results.
 const int kContainerDirectoryMinimumPercent = 80;

 // How long after a completed media scan can we provide the cached results.
 const int kScanResultsExpiryTimeInHours = 24;

 struct LocationInfo {
   LocationInfo()
       : pref_id(kInvalidMediaGalleryPrefId),
         type(MediaGalleryPrefInfo::kInvalidType) {}
   LocationInfo(MediaGalleryPrefId pref_id, MediaGalleryPrefInfo::Type type,
                base::FilePath path)
       : pref_id(pref_id), type(type), path(path) {}
   // Highest priority comparison by path, next by type (scan result last),
   // then by pref id (invalid last).
   bool operator<(const LocationInfo& rhs) const {
     if (path.value() == rhs.path.value()) {
       if (type == rhs.type) {
         return pref_id > rhs.pref_id;
       }
       return rhs.type == MediaGalleryPrefInfo::kScanResult;
     }
     return path.value() < rhs.path.value();
   }

   MediaGalleryPrefId pref_id;
   MediaGalleryPrefInfo::Type type;
   base::FilePath path;
   MediaGalleryScanResult file_counts;
 };

 // Finds new scan results that are shadowed (the same location, or a child) by
 // existing locations and moves them from |found_folders| to |child_folders|.
 // Also moves new scan results that are shadowed by other new scan results
 // to |child_folders|.
 void PartitionChildScanResults(
     MediaGalleriesPreferences* preferences,
     MediaFolderFinder::MediaFolderFinderResults* found_folders,
     MediaFolderFinder::MediaFolderFinderResults* child_folders) {
   // Construct a list with everything in it.
   std::vector<LocationInfo> all_locations;
   for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
            found_folders->begin(); it != found_folders->end(); ++it) {
     all_locations.push_back(LocationInfo(kInvalidMediaGalleryPrefId,
                                          MediaGalleryPrefInfo::kScanResult,
                                          it->first));
     all_locations.back().file_counts = it->second;
   }
   const MediaGalleriesPrefInfoMap& known_galleries =
       preferences->known_galleries();
   for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
        it != known_galleries.end();
        ++it) {
     all_locations.push_back(LocationInfo(it->second.pref_id, it->second.type,
                                          it->second.AbsolutePath()));
   }
   // Sorting on path should put all paths that are prefixes of other paths
   // next to each other, with the shortest one first.
   std::sort(all_locations.begin(), all_locations.end());

   size_t previous_parent_index = 0;
   for (size_t i = 1; i < all_locations.size(); i++) {
     const LocationInfo& current = all_locations[i];
     const LocationInfo& previous_parent = all_locations[previous_parent_index];
     bool is_child = previous_parent.path.IsParent(current.path);
     if (current.type == MediaGalleryPrefInfo::kScanResult &&
         current.pref_id == kInvalidMediaGalleryPrefId &&
         (is_child || previous_parent.path == current.path)) {
       // Move new scan results that are shadowed.
       (*child_folders)[current.path] = current.file_counts;
       found_folders->erase(current.path);
     } else if (!is_child) {
       previous_parent_index = i;
     }
   }
 }

 MediaGalleryScanResult SumFilesUnderPath(
     const base::FilePath& path,
     const MediaFolderFinder::MediaFolderFinderResults& candidates) {
   MediaGalleryScanResult results;
   for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
            candidates.begin(); it != candidates.end(); ++it) {
     if (it->first == path || path.IsParent(it->first)) {
       results.audio_count += it->second.audio_count;
       results.image_count += it->second.image_count;
       results.video_count += it->second.video_count;
     }
   }
   return results;
 }

 void AddScanResultsForProfile(
     MediaGalleriesPreferences* preferences,
     const MediaFolderFinder::MediaFolderFinderResults& found_folders) {
   // First, remove any existing scan results where no app has been granted
   // permission - either it is gone, or is already in the new scan results.
   // This burns some pref ids, but not at an appreciable rate.
   MediaGalleryPrefIdSet to_remove;
   const MediaGalleriesPrefInfoMap& known_galleries =
       preferences->known_galleries();
   for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
        it != known_galleries.end();
        ++it) {
     if (it->second.type == MediaGalleryPrefInfo::kScanResult &&
         !preferences->NonAutoGalleryHasPermission(it->first)) {
       to_remove.insert(it->first);
     }
   }
   for (MediaGalleryPrefIdSet::const_iterator it = to_remove.begin();
        it != to_remove.end();
        ++it) {
     preferences->EraseGalleryById(*it);
   }

   MediaFolderFinder::MediaFolderFinderResults child_folders;
   MediaFolderFinder::MediaFolderFinderResults
       unique_found_folders(found_folders);
   PartitionChildScanResults(preferences, &unique_found_folders, &child_folders);

   // Updating prefs while iterating them will invalidate the pointer, so
   // calculate the changes first and then apply them.
   std::map<MediaGalleryPrefId, MediaGalleryScanResult> to_update;
   for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
        it != known_galleries.end();
        ++it) {
     const MediaGalleryPrefInfo& gallery = it->second;
     if (!gallery.IsBlackListedType()) {
       MediaGalleryScanResult file_counts =
           SumFilesUnderPath(gallery.AbsolutePath(), child_folders);
       if (gallery.audio_count != file_counts.audio_count ||
           gallery.image_count != file_counts.image_count ||
           gallery.video_count != file_counts.video_count) {
         to_update[it->first] = file_counts;
       }
     }
   }

   for (std::map<MediaGalleryPrefId,
                 MediaGalleryScanResult>::const_iterator it = to_update.begin();
        it != to_update.end();
        ++it) {
     const MediaGalleryPrefInfo& gallery =
         preferences->known_galleries().find(it->first)->second;
       preferences->AddGallery(gallery.device_id, gallery.path, gallery.type,
                               gallery.volume_label, gallery.vendor_name,
                               gallery.model_name, gallery.total_size_in_bytes,
                               gallery.last_attach_time,
                               it->second.audio_count,
                               it->second.image_count,
                               it->second.video_count);
   }

   // Add new scan results.
   for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
            unique_found_folders.begin();
        it != unique_found_folders.end();
        ++it) {
     MediaGalleryScanResult file_counts =
         SumFilesUnderPath(it->first, child_folders);
     // The top level scan result is not in |child_folders|. Add it in as well.
     file_counts.audio_count += it->second.audio_count;
     file_counts.image_count += it->second.image_count;
     file_counts.video_count += it->second.video_count;

     MediaGalleryPrefInfo gallery;
     bool existing = preferences->LookUpGalleryByPath(it->first, &gallery);
     DCHECK(!existing);
     preferences->AddGallery(gallery.device_id, gallery.path,
                             MediaGalleryPrefInfo::kScanResult,
                             gallery.volume_label, gallery.vendor_name,
                             gallery.model_name, gallery.total_size_in_bytes,
                             gallery.last_attach_time, file_counts.audio_count,
                             file_counts.image_count, file_counts.video_count);
   }
   UMA_HISTOGRAM_COUNTS_10000("MediaGalleries.ScanGalleriesPopulated",
                              unique_found_folders.size() + to_update.size());
 }

 int CountScanResultsForExtension(MediaGalleriesPreferences* preferences,
                                  const extensions::Extension* extension,
                                  MediaGalleryScanResult* file_counts) {
   int gallery_count = 0;

   MediaGalleryPrefIdSet permitted_galleries =
       preferences->GalleriesForExtension(*extension);
   const MediaGalleriesPrefInfoMap& known_galleries =
       preferences->known_galleries();
   for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
        it != known_galleries.end();
        ++it) {
     if (it->second.type == MediaGalleryPrefInfo::kScanResult &&
         !ContainsKey(permitted_galleries, it->first)) {
       gallery_count++;
       file_counts->audio_count += it->second.audio_count;
       file_counts->image_count += it->second.image_count;
       file_counts->video_count += it->second.video_count;
     }
   }
   return gallery_count;
 }

 int CountDirectoryEntries(const base::FilePath& path) {
   base::FileEnumerator dir_counter(
       path, false /*recursive*/, base::FileEnumerator::DIRECTORIES);
   int count = 0;
   base::FileEnumerator::FileInfo info;
   for (base::FilePath name = dir_counter.Next(); !name.empty();
        name = dir_counter.Next()) {
     if (!base::IsLink(name))
       ++count;
   }
   return count;
 }

 struct ContainerCount {
   int seen_count, entries_count;
   bool is_qualified;

   ContainerCount() : seen_count(0), entries_count(-1), is_qualified(false) {}
 };

 typedef std::map<base::FilePath, ContainerCount> ContainerCandidates;

 }  // namespace

 MediaScanManager::MediaScanManager()
     : scoped_extension_registry_observer_(this),
       weak_factory_(this) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
 }

 MediaScanManager::~MediaScanManager() {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
 }

 void MediaScanManager::AddObserver(Profile* profile,
                                    MediaScanManagerObserver* observer) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
   DCHECK(!ContainsKey(observers_, profile));
   observers_[profile].observer = observer;
 }

 void MediaScanManager::RemoveObserver(Profile* profile) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
   bool scan_in_progress = ScanInProgress();
   observers_.erase(profile);
   DCHECK_EQ(scan_in_progress, ScanInProgress());
 }

 void MediaScanManager::CancelScansForProfile(Profile* profile) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
   observers_[profile].scanning_extensions.clear();

   if (!ScanInProgress())
     folder_finder_.reset();
 }

 void MediaScanManager::StartScan(Profile* profile,
                                  const extensions::Extension* extension,
                                  bool user_gesture) {
   DCHECK(extension);
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);

   ScanObserverMap::iterator scans_for_profile = observers_.find(profile);
   // We expect that an MediaScanManagerObserver has already been registered.
   DCHECK(scans_for_profile != observers_.end());
   bool scan_in_progress = ScanInProgress();
   // Ignore requests for extensions that are already scanning.
   ScanningExtensionIdSet* scanning_extensions;
   scanning_extensions = &scans_for_profile->second.scanning_extensions;
   if (scan_in_progress && ContainsKey(*scanning_extensions, extension->id()))
     return;

   // Provide cached result if there is not already a scan in progress,
   // there is no user gesture, and the previous results are unexpired.
   MediaGalleriesPreferences* preferences =
       MediaGalleriesPreferencesFactory::GetForProfile(profile);
   base::TimeDelta time_since_last_scan =
       base::Time::Now() - preferences->GetLastScanCompletionTime();
   if (!scan_in_progress && !user_gesture && time_since_last_scan <
           base::TimeDelta::FromHours(kScanResultsExpiryTimeInHours)) {
     MediaGalleryScanResult file_counts;
     int gallery_count =
         CountScanResultsForExtension(preferences, extension, &file_counts);
     scans_for_profile->second.observer->OnScanStarted(extension->id());
     scans_for_profile->second.observer->OnScanFinished(extension->id(),
                                                        gallery_count,
                                                        file_counts);
     return;
   }

   // On first scan for the |profile|, register to listen for extension unload.
   if (scanning_extensions->empty())
     scoped_extension_registry_observer_.Add(ExtensionRegistry::Get(profile));

   scanning_extensions->insert(extension->id());
   scans_for_profile->second.observer->OnScanStarted(extension->id());

   if (folder_finder_)
     return;

   MediaFolderFinder::MediaFolderFinderResultsCallback callback =
       base::Bind(&MediaScanManager::OnScanCompleted,
                  weak_factory_.GetWeakPtr());
   if (testing_folder_finder_factory_.is_null()) {
     folder_finder_.reset(new MediaFolderFinder(callback));
   } else {
     folder_finder_.reset(testing_folder_finder_factory_.Run(callback));
   }
   scan_start_time_ = base::Time::Now();
   folder_finder_->StartScan();
 }

 void MediaScanManager::CancelScan(Profile* profile,
                                   const extensions::Extension* extension) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);

   // Erases the logical scan if found, early exit otherwise.
   ScanObserverMap::iterator scans_for_profile = observers_.find(profile);
   if (scans_for_profile == observers_.end() ||
       !scans_for_profile->second.scanning_extensions.erase(extension->id())) {
     return;
   }

   scans_for_profile->second.observer->OnScanCancelled(extension->id());

   // No more scanning extensions for |profile|, so stop listening for unloads.
   if (scans_for_profile->second.scanning_extensions.empty())
     scoped_extension_registry_observer_.Remove(ExtensionRegistry::Get(profile));

   if (!ScanInProgress()) {
     folder_finder_.reset();
     DCHECK(!scan_start_time_.is_null());
     UMA_HISTOGRAM_LONG_TIMES("MediaGalleries.ScanCancelTime",
                              base::Time::Now() - scan_start_time_);
     scan_start_time_ = base::Time();
   }
 }

 void MediaScanManager::SetMediaFolderFinderFactory(
     const MediaFolderFinderFactory& factory) {
   testing_folder_finder_factory_ = factory;
 }

 // A single directory may contain many folders with media in them, without
 // containing any media itself. In fact, the primary purpose of that directory
 // may be to contain media directories. This function tries to find those
 // container directories.
 MediaFolderFinder::MediaFolderFinderResults
 MediaScanManager::FindContainerScanResults(
     const MediaFolderFinder::MediaFolderFinderResults& found_folders,
     const std::vector<base::FilePath>& sensitive_locations) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::FILE);
   std::vector<base::FilePath> abs_sensitive_locations;
   for (size_t i = 0; i < sensitive_locations.size(); ++i) {
     base::FilePath path = base::MakeAbsoluteFilePath(sensitive_locations[i]);
     if (!path.empty())
       abs_sensitive_locations.push_back(path);
   }
   // Recursively find parent directories with majority of media directories,
   // or container directories.
   // |candidates| keeps track of directories which might have enough
   // such directories to have us return them.
   typedef std::map<base::FilePath, ContainerCount> ContainerCandidates;
   ContainerCandidates candidates;
   for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
            found_folders.begin();
        it != found_folders.end();
        ++it) {
     base::FilePath child_directory = it->first;
     base::FilePath parent_directory = child_directory.DirName();

     // Parent of root is root.
     while (!parent_directory.empty() && child_directory != parent_directory) {
       // Skip sensitive folders and their ancestors.
       base::FilePath abs_parent_directory =
           base::MakeAbsoluteFilePath(parent_directory);
       if (abs_parent_directory.empty())
         break;
       bool is_sensitive = false;
       for (size_t i = 0; i < abs_sensitive_locations.size(); ++i) {
         if (abs_parent_directory == abs_sensitive_locations[i] ||
             abs_parent_directory.IsParent(abs_sensitive_locations[i])) {
           is_sensitive = true;
           break;
         }
       }
       if (is_sensitive)
         break;

       // Don't bother with ones we already have.
       if (found_folders.find(parent_directory) != found_folders.end())
         continue;

       ContainerCandidates::iterator parent_it =
           candidates.find(parent_directory);
       if (parent_it == candidates.end()) {
         ContainerCount count;
         count.seen_count = 1;
         count.entries_count = CountDirectoryEntries(parent_directory);
         parent_it =
             candidates.insert(std::make_pair(parent_directory, count)).first;
       } else {
         ++candidates[parent_directory].seen_count;
       }
       // If previously sufficient, or not sufficient, bail.
       if (parent_it->second.is_qualified ||
           parent_it->second.seen_count * 100 / parent_it->second.entries_count <
               kContainerDirectoryMinimumPercent) {
         break;
       }
       // Otherwise, mark qualified and check parent.
       parent_it->second.is_qualified = true;
       child_directory = parent_directory;
       parent_directory = child_directory.DirName();
     }
   }
   MediaFolderFinder::MediaFolderFinderResults result;
   // Copy and return worthy results.
   for (ContainerCandidates::const_iterator it = candidates.begin();
        it != candidates.end();
        ++it) {
     if (it->second.is_qualified && it->second.seen_count >= 2)
       result[it->first] = MediaGalleryScanResult();
   }
   return result;
 }

 MediaScanManager::ScanObservers::ScanObservers() : observer(NULL) {}
 MediaScanManager::ScanObservers::~ScanObservers() {}

 void MediaScanManager::OnExtensionUnloaded(
     content::BrowserContext* browser_context,
     const extensions::Extension* extension,
     extensions::UnloadedExtensionInfo::Reason reason) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
   CancelScan(Profile::FromBrowserContext(browser_context), extension);
 }

 bool MediaScanManager::ScanInProgress() const {
   for (ScanObserverMap::const_iterator it = observers_.begin();
        it != observers_.end();
        ++it) {
     if (!it->second.scanning_extensions.empty())
       return true;
   }
   return false;
 }

 void MediaScanManager::OnScanCompleted(
     bool success,
     const MediaFolderFinder::MediaFolderFinderResults& found_folders) {
   DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
   if (!folder_finder_ || !success) {
     folder_finder_.reset();
     return;
   }

   UMA_HISTOGRAM_COUNTS_10000("MediaGalleries.ScanDirectoriesFound",
                              found_folders.size());
   DCHECK(!scan_start_time_.is_null());
   UMA_HISTOGRAM_LONG_TIMES("MediaGalleries.ScanFinishedTime",
                            base::Time::Now() - scan_start_time_);
   scan_start_time_ = base::Time();

   content::BrowserThread::PostTaskAndReplyWithResult(
       content::BrowserThread::FILE, FROM_HERE,
       base::Bind(FindContainerScanResults,
                  found_folders,
                  folder_finder_->graylisted_folders()),
       base::Bind(&MediaScanManager::OnFoundContainerDirectories,
                  weak_factory_.GetWeakPtr(),
                  found_folders));
 }

 void MediaScanManager::OnFoundContainerDirectories(
     const MediaFolderFinder::MediaFolderFinderResults& found_folders,
     const MediaFolderFinder::MediaFolderFinderResults& container_folders) {
   MediaFolderFinder::MediaFolderFinderResults folders;
   folders.insert(found_folders.begin(), found_folders.end());
   folders.insert(container_folders.begin(), container_folders.end());

   for (ScanObserverMap::iterator scans_for_profile = observers_.begin();
        scans_for_profile != observers_.end();
        ++scans_for_profile) {
     if (scans_for_profile->second.scanning_extensions.empty())
       continue;
     Profile* profile = scans_for_profile->first;
     MediaGalleriesPreferences* preferences =
         MediaGalleriesPreferencesFactory::GetForProfile(profile);
     ExtensionService* extension_service =
         extensions::ExtensionSystem::Get(profile)->extension_service();
     if (!extension_service)
       continue;

     AddScanResultsForProfile(preferences, folders);

     ScanningExtensionIdSet* scanning_extensions =
         &scans_for_profile->second.scanning_extensions;
     for (ScanningExtensionIdSet::const_iterator extension_id_it =
              scanning_extensions->begin();
          extension_id_it != scanning_extensions->end();
          ++extension_id_it) {
       const extensions::Extension* extension =
           extension_service->GetExtensionById(*extension_id_it, false);
       if (extension) {
         MediaGalleryScanResult file_counts;
         int gallery_count = CountScanResultsForExtension(preferences, extension,
                                                          &file_counts);
         scans_for_profile->second.observer->OnScanFinished(*extension_id_it,
                                                            gallery_count,
                                                            file_counts);
       }
     }
     scanning_extensions->clear();
     preferences->SetLastScanCompletionTime(base::Time::Now());
   }
   scoped_extension_registry_observer_.RemoveAll();
   folder_finder_.reset();
 }
	// Copyright 2014 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 "chrome/browser/media_galleries/media_scan_manager.h"

	#include "base/files/file_enumerator.h"
	#include "base/files/file_util.h"
	#include "base/logging.h"
	#include "base/metrics/histogram.h"
	#include "base/time/time.h"
	#include "chrome/browser/extensions/extension_service.h"
	#include "chrome/browser/media_galleries/media_galleries_preferences.h"
	#include "chrome/browser/media_galleries/media_galleries_preferences_factory.h"
	#include "chrome/browser/media_galleries/media_scan_manager_observer.h"
	#include "chrome/browser/profiles/profile.h"
	#include "chrome/common/extensions/api/media_galleries.h"
	#include "content/public/browser/browser_thread.h"
	#include "extensions/browser/extension_registry.h"
	#include "extensions/browser/extension_system.h"
	#include "extensions/common/extension.h"

	using extensions::ExtensionRegistry;

	namespace media_galleries = extensions::api::media_galleries;

	namespace {

	typedef std::set<std::string /extension id/> ScanningExtensionIdSet;

	// When multiple scan results have the same parent, sometimes it makes sense
	// to combine them into a single scan result at the parent. This constant
	// governs when that happens; kContainerDirectoryMinimumPercent percent of the
	// directories in the parent directory must be scan results.
	const int kContainerDirectoryMinimumPercent = 80;

	// How long after a completed media scan can we provide the cached results.
	const int kScanResultsExpiryTimeInHours = 24;

	struct LocationInfo {
	LocationInfo()
	: pref_id(kInvalidMediaGalleryPrefId),
	type(MediaGalleryPrefInfo::kInvalidType) {}
	LocationInfo(MediaGalleryPrefId pref_id, MediaGalleryPrefInfo::Type type,
	base::FilePath path)
	: pref_id(pref_id), type(type), path(path) {}
	// Highest priority comparison by path, next by type (scan result last),
	// then by pref id (invalid last).
	bool operator<(const LocationInfo& rhs) const {
	if (path.value() == rhs.path.value()) {
	if (type == rhs.type) {
	return pref_id > rhs.pref_id;
	}
	return rhs.type == MediaGalleryPrefInfo::kScanResult;
	}
	return path.value() < rhs.path.value();
	}

	MediaGalleryPrefId pref_id;
	MediaGalleryPrefInfo::Type type;
	base::FilePath path;
	MediaGalleryScanResult file_counts;
	};

	// Finds new scan results that are shadowed (the same location, or a child) by
	// existing locations and moves them from \|found_folders\| to \|child_folders\|.
	// Also moves new scan results that are shadowed by other new scan results
	// to \|child_folders\|.
	void PartitionChildScanResults(
	MediaGalleriesPreferences* preferences,
	MediaFolderFinder::MediaFolderFinderResults* found_folders,
	MediaFolderFinder::MediaFolderFinderResults* child_folders) {
	// Construct a list with everything in it.
	std::vector<LocationInfo> all_locations;
	for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
	found_folders->begin(); it != found_folders->end(); ++it) {
	all_locations.push_back(LocationInfo(kInvalidMediaGalleryPrefId,
	MediaGalleryPrefInfo::kScanResult,
	it->first));
	all_locations.back().file_counts = it->second;
	}
	const MediaGalleriesPrefInfoMap& known_galleries =
	preferences->known_galleries();
	for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
	it != known_galleries.end();
	++it) {
	all_locations.push_back(LocationInfo(it->second.pref_id, it->second.type,
	it->second.AbsolutePath()));
	}
	// Sorting on path should put all paths that are prefixes of other paths
	// next to each other, with the shortest one first.
	std::sort(all_locations.begin(), all_locations.end());

	size_t previous_parent_index = 0;
	for (size_t i = 1; i < all_locations.size(); i++) {
	const LocationInfo& current = all_locations[i];
	const LocationInfo& previous_parent = all_locations[previous_parent_index];
	bool is_child = previous_parent.path.IsParent(current.path);
	if (current.type == MediaGalleryPrefInfo::kScanResult &&
	current.pref_id == kInvalidMediaGalleryPrefId &&
	(is_child \|\| previous_parent.path == current.path)) {
	// Move new scan results that are shadowed.
	(*child_folders)[current.path] = current.file_counts;
	found_folders->erase(current.path);
	} else if (!is_child) {
	previous_parent_index = i;
	}
	}
	}

	MediaGalleryScanResult SumFilesUnderPath(
	const base::FilePath& path,
	const MediaFolderFinder::MediaFolderFinderResults& candidates) {
	MediaGalleryScanResult results;
	for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
	candidates.begin(); it != candidates.end(); ++it) {
	if (it->first == path \|\| path.IsParent(it->first)) {
	results.audio_count += it->second.audio_count;
	results.image_count += it->second.image_count;
	results.video_count += it->second.video_count;
	}
	}
	return results;
	}

	void AddScanResultsForProfile(
	MediaGalleriesPreferences* preferences,
	const MediaFolderFinder::MediaFolderFinderResults& found_folders) {
	// First, remove any existing scan results where no app has been granted
	// permission - either it is gone, or is already in the new scan results.
	// This burns some pref ids, but not at an appreciable rate.
	MediaGalleryPrefIdSet to_remove;
	const MediaGalleriesPrefInfoMap& known_galleries =
	preferences->known_galleries();
	for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
	it != known_galleries.end();
	++it) {
	if (it->second.type == MediaGalleryPrefInfo::kScanResult &&
	!preferences->NonAutoGalleryHasPermission(it->first)) {
	to_remove.insert(it->first);
	}
	}
	for (MediaGalleryPrefIdSet::const_iterator it = to_remove.begin();
	it != to_remove.end();
	++it) {
	preferences->EraseGalleryById(*it);
	}

	MediaFolderFinder::MediaFolderFinderResults child_folders;
	MediaFolderFinder::MediaFolderFinderResults
	unique_found_folders(found_folders);
	PartitionChildScanResults(preferences, &unique_found_folders, &child_folders);

	// Updating prefs while iterating them will invalidate the pointer, so
	// calculate the changes first and then apply them.
	std::map<MediaGalleryPrefId, MediaGalleryScanResult> to_update;
	for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
	it != known_galleries.end();
	++it) {
	const MediaGalleryPrefInfo& gallery = it->second;
	if (!gallery.IsBlackListedType()) {
	MediaGalleryScanResult file_counts =
	SumFilesUnderPath(gallery.AbsolutePath(), child_folders);
	if (gallery.audio_count != file_counts.audio_count \|\|
	gallery.image_count != file_counts.image_count \|\|
	gallery.video_count != file_counts.video_count) {
	to_update[it->first] = file_counts;
	}
	}
	}

	for (std::map<MediaGalleryPrefId,
	MediaGalleryScanResult>::const_iterator it = to_update.begin();
	it != to_update.end();
	++it) {
	const MediaGalleryPrefInfo& gallery =
	preferences->known_galleries().find(it->first)->second;
	preferences->AddGallery(gallery.device_id, gallery.path, gallery.type,
	gallery.volume_label, gallery.vendor_name,
	gallery.model_name, gallery.total_size_in_bytes,
	gallery.last_attach_time,
	it->second.audio_count,
	it->second.image_count,
	it->second.video_count);
	}

	// Add new scan results.
	for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
	unique_found_folders.begin();
	it != unique_found_folders.end();
	++it) {
	MediaGalleryScanResult file_counts =
	SumFilesUnderPath(it->first, child_folders);
	// The top level scan result is not in \|child_folders\|. Add it in as well.
	file_counts.audio_count += it->second.audio_count;
	file_counts.image_count += it->second.image_count;
	file_counts.video_count += it->second.video_count;

	MediaGalleryPrefInfo gallery;
	bool existing = preferences->LookUpGalleryByPath(it->first, &gallery);
	DCHECK(!existing);
	preferences->AddGallery(gallery.device_id, gallery.path,
	MediaGalleryPrefInfo::kScanResult,
	gallery.volume_label, gallery.vendor_name,
	gallery.model_name, gallery.total_size_in_bytes,
	gallery.last_attach_time, file_counts.audio_count,
	file_counts.image_count, file_counts.video_count);
	}
	UMA_HISTOGRAM_COUNTS_10000("MediaGalleries.ScanGalleriesPopulated",
	unique_found_folders.size() + to_update.size());
	}

	int CountScanResultsForExtension(MediaGalleriesPreferences* preferences,
	const extensions::Extension* extension,
	MediaGalleryScanResult* file_counts) {
	int gallery_count = 0;

	MediaGalleryPrefIdSet permitted_galleries =
	preferences->GalleriesForExtension(*extension);
	const MediaGalleriesPrefInfoMap& known_galleries =
	preferences->known_galleries();
	for (MediaGalleriesPrefInfoMap::const_iterator it = known_galleries.begin();
	it != known_galleries.end();
	++it) {
	if (it->second.type == MediaGalleryPrefInfo::kScanResult &&
	!ContainsKey(permitted_galleries, it->first)) {
	gallery_count++;
	file_counts->audio_count += it->second.audio_count;
	file_counts->image_count += it->second.image_count;
	file_counts->video_count += it->second.video_count;
	}
	}
	return gallery_count;
	}

	int CountDirectoryEntries(const base::FilePath& path) {
	base::FileEnumerator dir_counter(
	path, false /recursive/, base::FileEnumerator::DIRECTORIES);
	int count = 0;
	base::FileEnumerator::FileInfo info;
	for (base::FilePath name = dir_counter.Next(); !name.empty();
	name = dir_counter.Next()) {
	if (!base::IsLink(name))
	++count;
	}
	return count;
	}

	struct ContainerCount {
	int seen_count, entries_count;
	bool is_qualified;

	ContainerCount() : seen_count(0), entries_count(-1), is_qualified(false) {}
	};

	typedef std::map<base::FilePath, ContainerCount> ContainerCandidates;

	} // namespace

	MediaScanManager::MediaScanManager()
	: scoped_extension_registry_observer_(this),
	weak_factory_(this) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	}

	MediaScanManager::~MediaScanManager() {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	}

	void MediaScanManager::AddObserver(Profile* profile,
	MediaScanManagerObserver* observer) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	DCHECK(!ContainsKey(observers_, profile));
	observers_[profile].observer = observer;
	}

	void MediaScanManager::RemoveObserver(Profile* profile) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	bool scan_in_progress = ScanInProgress();
	observers_.erase(profile);
	DCHECK_EQ(scan_in_progress, ScanInProgress());
	}

	void MediaScanManager::CancelScansForProfile(Profile* profile) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	observers_[profile].scanning_extensions.clear();

	if (!ScanInProgress())
	folder_finder_.reset();
	}

	void MediaScanManager::StartScan(Profile* profile,
	const extensions::Extension* extension,
	bool user_gesture) {
	DCHECK(extension);
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);

	ScanObserverMap::iterator scans_for_profile = observers_.find(profile);
	// We expect that an MediaScanManagerObserver has already been registered.
	DCHECK(scans_for_profile != observers_.end());
	bool scan_in_progress = ScanInProgress();
	// Ignore requests for extensions that are already scanning.
	ScanningExtensionIdSet* scanning_extensions;
	scanning_extensions = &scans_for_profile->second.scanning_extensions;
	if (scan_in_progress && ContainsKey(*scanning_extensions, extension->id()))
	return;

	// Provide cached result if there is not already a scan in progress,
	// there is no user gesture, and the previous results are unexpired.
	MediaGalleriesPreferences* preferences =
	MediaGalleriesPreferencesFactory::GetForProfile(profile);
	base::TimeDelta time_since_last_scan =
	base::Time::Now() - preferences->GetLastScanCompletionTime();
	if (!scan_in_progress && !user_gesture && time_since_last_scan <
	base::TimeDelta::FromHours(kScanResultsExpiryTimeInHours)) {
	MediaGalleryScanResult file_counts;
	int gallery_count =
	CountScanResultsForExtension(preferences, extension, &file_counts);
	scans_for_profile->second.observer->OnScanStarted(extension->id());
	scans_for_profile->second.observer->OnScanFinished(extension->id(),
	gallery_count,
	file_counts);
	return;
	}

	// On first scan for the \|profile\|, register to listen for extension unload.
	if (scanning_extensions->empty())
	scoped_extension_registry_observer_.Add(ExtensionRegistry::Get(profile));

	scanning_extensions->insert(extension->id());
	scans_for_profile->second.observer->OnScanStarted(extension->id());

	if (folder_finder_)
	return;

	MediaFolderFinder::MediaFolderFinderResultsCallback callback =
	base::Bind(&MediaScanManager::OnScanCompleted,
	weak_factory_.GetWeakPtr());
	if (testing_folder_finder_factory_.is_null()) {
	folder_finder_.reset(new MediaFolderFinder(callback));
	} else {
	folder_finder_.reset(testing_folder_finder_factory_.Run(callback));
	}
	scan_start_time_ = base::Time::Now();
	folder_finder_->StartScan();
	}

	void MediaScanManager::CancelScan(Profile* profile,
	const extensions::Extension* extension) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);

	// Erases the logical scan if found, early exit otherwise.
	ScanObserverMap::iterator scans_for_profile = observers_.find(profile);
	if (scans_for_profile == observers_.end() \|\|
	!scans_for_profile->second.scanning_extensions.erase(extension->id())) {
	return;
	}

	scans_for_profile->second.observer->OnScanCancelled(extension->id());

	// No more scanning extensions for \|profile\|, so stop listening for unloads.
	if (scans_for_profile->second.scanning_extensions.empty())
	scoped_extension_registry_observer_.Remove(ExtensionRegistry::Get(profile));

	if (!ScanInProgress()) {
	folder_finder_.reset();
	DCHECK(!scan_start_time_.is_null());
	UMA_HISTOGRAM_LONG_TIMES("MediaGalleries.ScanCancelTime",
	base::Time::Now() - scan_start_time_);
	scan_start_time_ = base::Time();
	}
	}

	void MediaScanManager::SetMediaFolderFinderFactory(
	const MediaFolderFinderFactory& factory) {
	testing_folder_finder_factory_ = factory;
	}

	// A single directory may contain many folders with media in them, without
	// containing any media itself. In fact, the primary purpose of that directory
	// may be to contain media directories. This function tries to find those
	// container directories.
	MediaFolderFinder::MediaFolderFinderResults
	MediaScanManager::FindContainerScanResults(
	const MediaFolderFinder::MediaFolderFinderResults& found_folders,
	const std::vector<base::FilePath>& sensitive_locations) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::FILE);
	std::vector<base::FilePath> abs_sensitive_locations;
	for (size_t i = 0; i < sensitive_locations.size(); ++i) {
	base::FilePath path = base::MakeAbsoluteFilePath(sensitive_locations[i]);
	if (!path.empty())
	abs_sensitive_locations.push_back(path);
	}
	// Recursively find parent directories with majority of media directories,
	// or container directories.
	// \|candidates\| keeps track of directories which might have enough
	// such directories to have us return them.
	typedef std::map<base::FilePath, ContainerCount> ContainerCandidates;
	ContainerCandidates candidates;
	for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
	found_folders.begin();
	it != found_folders.end();
	++it) {
	base::FilePath child_directory = it->first;
	base::FilePath parent_directory = child_directory.DirName();

	// Parent of root is root.
	while (!parent_directory.empty() && child_directory != parent_directory) {
	// Skip sensitive folders and their ancestors.
	base::FilePath abs_parent_directory =
	base::MakeAbsoluteFilePath(parent_directory);
	if (abs_parent_directory.empty())
	break;
	bool is_sensitive = false;
	for (size_t i = 0; i < abs_sensitive_locations.size(); ++i) {
	if (abs_parent_directory == abs_sensitive_locations[i] \|\|
	abs_parent_directory.IsParent(abs_sensitive_locations[i])) {
	is_sensitive = true;
	break;
	}
	}
	if (is_sensitive)
	break;

	// Don't bother with ones we already have.
	if (found_folders.find(parent_directory) != found_folders.end())
	continue;

	ContainerCandidates::iterator parent_it =
	candidates.find(parent_directory);
	if (parent_it == candidates.end()) {
	ContainerCount count;
	count.seen_count = 1;
	count.entries_count = CountDirectoryEntries(parent_directory);
	parent_it =
	candidates.insert(std::make_pair(parent_directory, count)).first;
	} else {
	++candidates[parent_directory].seen_count;
	}
	// If previously sufficient, or not sufficient, bail.
	if (parent_it->second.is_qualified \|\|
	parent_it->second.seen_count * 100 / parent_it->second.entries_count <
	kContainerDirectoryMinimumPercent) {
	break;
	}
	// Otherwise, mark qualified and check parent.
	parent_it->second.is_qualified = true;
	child_directory = parent_directory;
	parent_directory = child_directory.DirName();
	}
	}
	MediaFolderFinder::MediaFolderFinderResults result;
	// Copy and return worthy results.
	for (ContainerCandidates::const_iterator it = candidates.begin();
	it != candidates.end();
	++it) {
	if (it->second.is_qualified && it->second.seen_count >= 2)
	result[it->first] = MediaGalleryScanResult();
	}
	return result;
	}

	MediaScanManager::ScanObservers::ScanObservers() : observer(NULL) {}
	MediaScanManager::ScanObservers::~ScanObservers() {}

	void MediaScanManager::OnExtensionUnloaded(
	content::BrowserContext* browser_context,
	const extensions::Extension* extension,
	extensions::UnloadedExtensionInfo::Reason reason) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	CancelScan(Profile::FromBrowserContext(browser_context), extension);
	}

	bool MediaScanManager::ScanInProgress() const {
	for (ScanObserverMap::const_iterator it = observers_.begin();
	it != observers_.end();
	++it) {
	if (!it->second.scanning_extensions.empty())
	return true;
	}
	return false;
	}

	void MediaScanManager::OnScanCompleted(
	bool success,
	const MediaFolderFinder::MediaFolderFinderResults& found_folders) {
	DCHECK_CURRENTLY_ON(content::BrowserThread::UI);
	if (!folder_finder_ \|\| !success) {
	folder_finder_.reset();
	return;
	}

	UMA_HISTOGRAM_COUNTS_10000("MediaGalleries.ScanDirectoriesFound",
	found_folders.size());
	DCHECK(!scan_start_time_.is_null());
	UMA_HISTOGRAM_LONG_TIMES("MediaGalleries.ScanFinishedTime",
	base::Time::Now() - scan_start_time_);
	scan_start_time_ = base::Time();

	content::BrowserThread::PostTaskAndReplyWithResult(
	content::BrowserThread::FILE, FROM_HERE,
	base::Bind(FindContainerScanResults,
	found_folders,
	folder_finder_->graylisted_folders()),
	base::Bind(&MediaScanManager::OnFoundContainerDirectories,
	weak_factory_.GetWeakPtr(),
	found_folders));
	}

	void MediaScanManager::OnFoundContainerDirectories(
	const MediaFolderFinder::MediaFolderFinderResults& found_folders,
	const MediaFolderFinder::MediaFolderFinderResults& container_folders) {
	MediaFolderFinder::MediaFolderFinderResults folders;
	folders.insert(found_folders.begin(), found_folders.end());
	folders.insert(container_folders.begin(), container_folders.end());

	for (ScanObserverMap::iterator scans_for_profile = observers_.begin();
	scans_for_profile != observers_.end();
	++scans_for_profile) {
	if (scans_for_profile->second.scanning_extensions.empty())
	continue;
	Profile* profile = scans_for_profile->first;
	MediaGalleriesPreferences* preferences =
	MediaGalleriesPreferencesFactory::GetForProfile(profile);
	ExtensionService* extension_service =
	extensions::ExtensionSystem::Get(profile)->extension_service();
	if (!extension_service)
	continue;

	AddScanResultsForProfile(preferences, folders);

	ScanningExtensionIdSet* scanning_extensions =
	&scans_for_profile->second.scanning_extensions;
	for (ScanningExtensionIdSet::const_iterator extension_id_it =
	scanning_extensions->begin();
	extension_id_it != scanning_extensions->end();
	++extension_id_it) {
	const extensions::Extension* extension =
	extension_service->GetExtensionById(*extension_id_it, false);
	if (extension) {
	MediaGalleryScanResult file_counts;
	int gallery_count = CountScanResultsForExtension(preferences, extension,
	&file_counts);
	scans_for_profile->second.observer->OnScanFinished(*extension_id_it,
	gallery_count,
	file_counts);
	}
	}
	scanning_extensions->clear();
	preferences->SetLastScanCompletionTime(base::Time::Now());
	}
	scoped_extension_registry_observer_.RemoveAll();
	folder_finder_.reset();
	}