Have FindContainerScanResults() find broader media container directories

chrome/browser/media_galleries/media_scan_manager.cc

 // 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/file_util.h"
 #include "base/files/file_enumerator.h"
 #include "base/logging.h"
 #include "base/metrics/histogram.h"
@@ skipping 195 matching lines @@
                             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());
 }
 
 // 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
-// immediate container directories.
+// container directories.
 MediaFolderFinder::MediaFolderFinderResults 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);
   }
-  // Count the number of scan results with the same parent directory.
+  // Find parent directories with majority of media directories,

[vandebo (ex-Chrome), 2014/05/20 20:51:45]

I think this change needs some unit testing.  One layout that I think is
important/likely that this doesn't handle the way we'd like is:

Library/
  Artist1/
    Album1/ [bunch of songs]
  Artist2/
    Album2/ [bunch of songs]
    Album3/ [bunch of songs]
    Album4/ [bunch of songs]
  Artist3/
    Album5/ [bunch of songs]
    Album6/ [bunch of songs]
    Album7/ [bunch of songs]
  Artist4/
    Album8/ [bunch of songs]
    Album9/ [bunch of songs]

[Kevin Bailey, 2014/05/21 14:41:45]

Will do. Here's another one:

A/
  B/
    D/
      E/media
      F/media
    G/
      H/media
      I/media
  C/media

It should include A but exclude B, D and G. D and G are the tricky ones.
However, perhaps I'm being too exclusive. More below.

+  // or container directories. Return |result|.
+  MediaFolderFinder::MediaFolderFinderResults result;
+  // |candidates| keeps track of directories which might have enough
+  // media entries to have us return them.
   typedef std::map<base::FilePath, int /*count*/> ContainerCandidates;
   ContainerCandidates candidates;
-  for (MediaFolderFinder::MediaFolderFinderResults::const_iterator it =
-           found_folders.begin(); it != found_folders.end(); ++it) {
-    base::FilePath parent_directory = it->first.DirName();
+  // |candidates_to_check| are members of |candidates| that have crossed
+  // threshold to be returned, and whose parents should likewise be checked.
+  std::set<base::FilePath> candidates_to_check;
+  MediaFolderFinder::MediaFolderFinderResults::const_iterator folder_it =
+      found_folders.begin();
+  while (folder_it != found_folders.end() && !candidates_to_check.empty()) {
+    base::FilePath candidate;
+    // Go through incoming |found_folders| first, then discovered candidates.
+    if (folder_it != found_folders.end()) {
+      candidate = folder_it->first;
+      ++folder_it;
+    } else {
+      candidate = *candidates_to_check.begin();
+      // Remove in case it gets added back.
+      candidates_to_check.erase(candidates_to_check.begin());
+    }
+    // It *could* have been nuked.
+    ContainerCandidates::iterator it = candidates.find(candidate);
+    if (it == candidates.end())

[vandebo (ex-Chrome), 2014/05/20 20:51:45]

Confused... candidates starts emtpy, so we won't find anything in it, and always
continue, so the code below here is dead.

[Kevin Bailey, 2014/05/21 14:41:45]

arg, leftover cruft. Missed it in the diffs.

+      continue;
+    base::FilePath parent_directory = candidate.DirName();
 
     // Skip sensitive folders and their ancestors.
     bool is_sensitive = false;
     base::FilePath abs_parent_directory =
         base::MakeAbsoluteFilePath(parent_directory);
-    if (abs_parent_directory.empty())
+    if (abs_parent_directory.empty()) {
+      result.erase(result.find(candidate));

[vandebo (ex-Chrome), 2014/05/20 20:51:45]

Why erase it from result?  Just don't add it to begin with.

[Kevin Bailey, 2014/05/21 14:41:45]

In fact, these lines could have simply been removed from this patch, since it's
not adding all the incoming ones any more. But beyond this, to avoid re-scanning
at the end, the strategy was to add/remove as something became un/worthy. Now
that it's caching results, it's trivial to do it at the end again.

+      candidates.erase(it);
       continue;
+    }
     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;
-        continue;
+        break;
       }
     }
-    if (is_sensitive)
+    if (is_sensitive) {
+      result.erase(result.find(candidate));

[vandebo (ex-Chrome), 2014/05/20 20:51:45]

ditto

[Kevin Bailey, 2014/05/21 14:41:45]

ack

+      candidates.erase(it);
       continue;
-
-    ContainerCandidates::iterator existing = candidates.find(parent_directory);
-    if (existing == candidates.end()) {
+    }
+    // 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()) {
       candidates[parent_directory] = 1;
-    } else {
-      existing->second++;
+      continue;
     }
-  }
-
-  // If a parent directory has more than one scan result, consider it.
-  MediaFolderFinder::MediaFolderFinderResults result;
-  for (ContainerCandidates::const_iterator it = candidates.begin();
-       it != candidates.end();
-       ++it) {
-    if (it->second <= 1)
-      continue;
-
-    base::FileEnumerator dir_counter(it->first, false /*recursive*/,
+    parent_it->second++;
+    // If a parent directory has more than one scan result, consider it.
+    base::FileEnumerator dir_counter(parent_it->first, false /*recursive*/,
                                      base::FileEnumerator::DIRECTORIES);
     base::FileEnumerator::FileInfo info;
     int count = 0;
     for (base::FilePath name = dir_counter.Next();

[vandebo (ex-Chrome), 2014/05/20 20:51:45]

This does a directory traversal on every increment above 1, which seems
unnecessary. Maybe cache the value.

[Kevin Bailey, 2014/05/21 14:41:45]

Done.

          !name.empty();
          name = dir_counter.Next()) {
       if (!base::IsLink(name))
         count++;
     }
-    if (it->second * 100 / count >= kContainerDirectoryMinimumPercent)
-      result[it->first] = MediaGalleryScanResult();
+    if (parent_it->second * 100 / count >= kContainerDirectoryMinimumPercent) {
+      // We're keeping this parent. Remove any children.

[vandebo (ex-Chrome), 2014/05/20 20:51:45]

Why remove the children?  They'll get taken care of in the following phase.

[Kevin Bailey, 2014/05/21 14:41:45]

Not positive which phase that you're referring to but I figured that this
function should consolidate a media directory tree up to its root, no matter who
will look at it. Again, perhaps it is being too exclusive. It's trivial to
remove the |has_parent| stuff, if you like.

[vandebo (ex-Chrome), 2014/05/21 15:55:09]

See PartitionChildScanResults()
Yea, lets take that stuff out which will leave this aspect of operation
unchanged.

+      for (ContainerCandidates::iterator child_it = candidates.begin();
+           child_it != candidates.end(); ) {
+        if (child_it != parent_it &&
+            child_it->first.DirName() == parent_it->first) {
+          ContainerCandidates::iterator next(child_it);
+          ++next;
+          result.erase(result.find(child_it->first));
+          candidates.erase(child_it);
+          child_it = next;
+        } else {
+          ++child_it;
+        }
+      }
+      // It's a qualified candidate now.
+      result[parent_it->first] = MediaGalleryScanResult();
+      candidates_to_check.insert(parent_it->first);
+    }
   }
   return result;
 }
 
 int CountScanResultsForExtension(MediaGalleriesPreferences* preferences,
                                  const extensions::Extension* extension,
                                  MediaGalleryScanResult* file_counts) {
   int gallery_count = 0;
 
   MediaGalleryPrefIdSet permitted_galleries =
@@ skipping 220 matching lines @@
                                                            gallery_count,
                                                            file_counts);
       }
     }
     scanning_extensions->clear();
     preferences->SetLastScanCompletionTime(base::Time::Now());
   }
   scoped_extension_registry_observer_.RemoveAll();
   folder_finder_.reset();
 }