Make app list search result mixer more resilient to reordering.

chrome/browser/ui/app_list/search/mixer.cc

 // Copyright 2013 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/ui/app_list/search/mixer.h"
 
 #include <algorithm>
 #include <set>
 #include <string>
 #include <vector>
@@ skipping 48 matching lines @@
     if (id_set.find(id) != id_set.end())
       continue;
 
     id_set.insert(id);
     final.push_back(*it);
   }
 
   results->swap(final);
 }
 
-// Publishes the given |results| to |ui_results|. Reuse existing ones to avoid
-// flickering.
-void Publish(const SortedResults& results,
+// Publishes the given |new_results| to |ui_results|. Reuse existing ones to

[Matt Giuca, 2014/07/04 08:21:21]

I'm a little skeptical of the name |new_results|, because it could be
misconstrued to mean "add |new_results| to the existing set of results, and
don't remove existing ones", whereas I think you mean to replace all results in
|ui_results| with the new ones.

I'm fine with keeping the name, but please give a more detailed description
here:
"Publishes the given |new_results| to |ui_results|, deleting any existing
results that are not in |new_results|. ..."

Also s/Reuse/Reuses/.

[calamity, 2014/07/08 09:47:20]

Done. Also changed the second sentence to better describe the problem.

+// avoid flickering.
+void Publish(const SortedResults& new_results,

[Matt Giuca, 2014/07/04 08:21:21]

I think there should be unit tests for this function alone. It is sufficiently
complicated (it probably was before, but now it certainly is).

[calamity, 2014/07/08 09:47:21]

Done.

              AppListModel::SearchResults* ui_results) {

[Matt Giuca, 2014/07/04 08:21:22]

It might be nice to give a high-level overview of the algorithm at the top:

// 1. Transform both the |new_results| and |ui_results| lists into unordered
maps from result ID to item.
// 2. Update the existing items with the items from |new_results|, deleting any
items that are not in |new_results|.
// 3. Convert the updated item map back into an ordered results list, using the
order of the items in |new_results|.

[calamity, 2014/07/08 09:47:20]

Done. Changed for new algorithm.

-  for (size_t i = 0; i < results.size(); ++i) {
-    ChromeSearchResult* result = results[i].result;
+  typedef std::map<std::string, ChromeSearchResult*> IdToResultMap;
 
-    ChromeSearchResult* ui_result = i < ui_results->item_count() ?
-        static_cast<ChromeSearchResult*>(ui_results->GetItemAt(i)) : NULL;
-    if (ui_result && ui_result->id() == result->id()) {
-      ui_result->set_title(result->title());
-      ui_result->set_title_tags(result->title_tags());
-      ui_result->set_details(result->details());
-      ui_result->set_details_tags(result->details_tags());
-      ui_results->NotifyItemsChanged(i, 1);
+  IdToResultMap new_results_map;
+  for (size_t i = 0; i < new_results.size(); ++i)

[Matt Giuca, 2014/07/04 08:21:21]

Use an iterator.

[calamity, 2014/07/08 09:47:21]

Done.

+    new_results_map[new_results[i].result->id()] = new_results[i].result;
+
+  // A map of the items in |ui_results| that takes ownership of the items.
+  IdToResultMap ui_results_map;
+  for (size_t i = 0; i < ui_results->item_count(); ++i) {
+    ChromeSearchResult* ui_result =
+        static_cast<ChromeSearchResult*>(ui_results->GetItemAt(i));
+    ui_results_map[ui_result->id()] = ui_result;
+  }
+  // We have to erase all results at once so that observers are notified with
+  // meaningful indexes.

[Matt Giuca, 2014/07/04 08:21:22]

Does this mean observers will see a "remove" of a result and an "add" of the
same result, if one is present in both the old and new lists?

[calamity, 2014/07/08 09:47:21]

Yes. The alternative is to use a Move(), but the old code did a DeleteAt() then
AddAt() so I think this is okay (there's actually a PostTask that batches these
events in search_result_list_view.cc). 

Although, there should really be an AddAll() in list model so that I can just
send 1 notification. I can add this in a follow-up CL.

+  ui_results->RemoveAll();
+
+  // For each ui result, update its properties if it is in the new results,
+  // otherwise delete it.
+  std::vector<std::string> ids_to_delete;
+  for (IdToResultMap::const_iterator ui_result_it = ui_results_map.begin();
+       ui_result_it != ui_results_map.end();
+       ++ui_result_it) {
+    ChromeSearchResult* ui_result = ui_result_it->second;
+    IdToResultMap::const_iterator result_it =
+        new_results_map.find(ui_result->id());
+    if (result_it != new_results_map.end()) {
+      ChromeSearchResult* new_result = result_it->second;

[Matt Giuca, 2014/07/04 08:21:22]

Can I suggest (the original code could have used this too) a separate function:
UpdateResult(const SortData& new_result, AppListModel::SearchResult* ui_result)
that updates a single result as appropriate.

[calamity, 2014/07/08 09:47:21]

Done.

+      ui_result->set_title(new_result->title());
+      ui_result->set_title_tags(new_result->title_tags());
+      ui_result->set_details(new_result->details());
+      ui_result->set_details_tags(new_result->details_tags());
+      new_results_map.erase(result_it);

[Matt Giuca, 2014/07/04 08:21:21]

Is there a reason you need to erase results from new_results_map? You never
refer to them again, so may as well just let them be deleted when
new_results_map goes out of scope.

     } else {
-      if (ui_result)
-        ui_results->DeleteAt(i);
-      ui_results->AddAt(i, result->Duplicate().release());
+      ids_to_delete.push_back(ui_result->id());
     }
   }
 
-  while (ui_results->item_count() > results.size())
-    ui_results->DeleteAt(ui_results->item_count() - 1);
+  for (size_t i = 0; i < ids_to_delete.size(); ++i) {
+    delete ui_results_map[ids_to_delete[i]];
+    ui_results_map.erase(ids_to_delete[i]);
+  }
+
+  // Insert results in the order of |new_results|.

[Matt Giuca, 2014/07/04 08:21:21]

Before this comment, say:
// Now, ui_results_map contains all of the updated results that were common to
both |ui_results| and |new_results|, but none of the newly added results.

(When I first read this, I was confused and thought you had forgotten about the
newly added results, until I saw that you were getting them directly from
|new_results| in the loop below.)

[calamity, 2014/07/08 09:47:21]

Done.

+  for (size_t i = 0; i < new_results.size(); ++i) {
+    ChromeSearchResult* new_result = new_results[i].result;
+    IdToResultMap::const_iterator ui_result_it =
+        ui_results_map.find(new_result->id());
+    // |ui_results| takes ownership here.
+    ui_results->Add(ui_result_it != ui_results_map.end()
+                        ? ui_result_it->second
+                        : new_result->Duplicate().release());

[Matt Giuca, 2014/07/04 08:21:21]

Should you be calling NotifyItemsChanged here? The original code does it.

[calamity, 2014/07/08 09:47:21]

Not necessary as the add and remove are used to notify the observers of a
change. Changed SearchResultListView to reflect this.

+  }
 }
 
 }  // namespace
 
 // Used to group relevant providers together fox mixing their results.
 class Mixer::Group {
  public:
   Group(size_t max_results, double boost)
       : max_results_(max_results),
         boost_(boost) {
@@ skipping 125 matching lines @@
 
 void Mixer::FetchResults(const KnownResults& known_results) {
   for (Groups::iterator group_it = groups_.begin();
        group_it != groups_.end();
        ++group_it) {
     (*group_it)->FetchResults(known_results);
   }
 }
 
 }  // namespace app_list