Move most visited item state info from InstantController to InstantService.

chrome/common/instant_restricted_id_cache.h

 // 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.
 
 #ifndef CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
 #define CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_
 
 #include <set>
 #include <utility>
 #include <vector>
@@ skipping 51 matching lines @@
   // returns a copy of the item.
   bool GetItemWithRestrictedID(InstantRestrictedID restricted_id,
                                T* item) const;
 
  private:
   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AutoIDGeneration);
   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, CrazyIDGeneration);
   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, ManualIDGeneration);
   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, MixIDGeneration);
   FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest, AddEmptySet);
+  FRIEND_TEST_ALL_PREFIXES(InstantRestrictedIDCacheTest,
+                           AddItemsWithRestrictedID);
 
   typedef base::MRUCache<InstantRestrictedID, T> CacheImpl;
 
   mutable CacheImpl cache_;
   typename CacheImpl::reverse_iterator last_add_start_;
   InstantRestrictedID last_restricted_id_;
 
   DISALLOW_COPY_AND_ASSIGN(InstantRestrictedIDCache);
 };
 
@@ skipping 37 matching lines @@
   }
 
   std::set<InstantRestrictedID> ids_added;
   for (size_t i = 0; i < items.size(); ++i) {
     const ItemIDPair& item_id = items[i];
 
     DCHECK(ids_added.find(item_id.first) == ids_added.end());
     ids_added.insert(item_id.first);
 
     cache_.Put(item_id.first, item_id.second);
-    if (i == 0)
-      last_add_start_ = --cache_.rend();
     last_restricted_id_ = std::max(item_id.first, last_restricted_id_);
   }
+
+  // cache_.Put() can invalidate the iterator |last_add_start_| is pointing to.

[Jered, 2013/05/24 15:58:21]

So were you seeing last_add_start_ reset for i == 0, and then become invalidated
inside the loop above?

From reading mru_cache, I think that should only happen if items contains
duplicate restricted ids or is larger than the cache capacity. Both seem like
deeper problems. Backing up by items.size() would not be correct in those cases
because we did not add that many items.

[Jered, 2013/05/24 19:23:02]

Ok, got it. This is sort of nasty and subtle. :-)

To avoid actually having a dummy before begin(), reverse_iterator defines
rbegin() to be end() and rend() maps to begin(). operator* accesses i-1. So
--rend() actually points at the last element of the _previously_ added MV items,
it's just that operator* makes it look like the first added item from this
batch. Yuck.

So, in your unit test, when erase() removes item 12, i.e. the last item of the
previously added batch, that invalidates last_add_start_.

I'm not sure why we're not seeing a bazillion renderer crashes because of this.

Anyway, I am fine with this fix. I would be _even happier_ with never ever using
reverse_iterators at all, because this behavior is really confusing and
dangerous.

[kmadhusu, 2013/05/24 20:12:23]

Yes. I completely agree. Reverse_iterator is very confusing. I will  clean up
this file in a separate CL.

+  // Therefore, update |last_add_start_| after adding all the items to the
+  // |cache_|.
+  last_add_start_ = cache_.rend();
+  for (size_t i = 0; i < items.size(); ++i)
+    --last_add_start_;
 }
 
 template <typename T>
 void InstantRestrictedIDCache<T>::GetCurrentItems(ItemIDVector* items) const {
   items->clear();
 
   for (typename CacheImpl::reverse_iterator it = last_add_start_;
        it != cache_.rend(); ++it) {
     items->push_back(std::make_pair(it->first, it->second));
   }
 }
 
 template <typename T>
 bool InstantRestrictedIDCache<T>::GetItemWithRestrictedID(
     InstantRestrictedID restricted_id,
     T* item) const {
   DCHECK(item);
 
   typename CacheImpl::const_iterator cache_it = cache_.Peek(restricted_id);
   if (cache_it == cache_.end())
     return false;
   *item = cache_it->second;
   return true;
 }
 
 #endif  // CHROME_COMMON_INSTANT_RESTRICTED_ID_CACHE_H_