New link rel=prerender api, using WebKit::WebPrerenderingPlatform

chrome/browser/prerender/prerender_link_manager.cc

+// Copyright (c) 2012 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/prerender/prerender_link_manager.h"
+
+#include <limits>
+#include <queue>
+#include <utility>
+
+#include "chrome/browser/prerender/prerender_contents.h"
+#include "chrome/browser/prerender/prerender_manager.h"
+#include "chrome/browser/prerender/prerender_manager_factory.h"
+#include "chrome/browser/profiles/profile.h"
+#include "content/public/common/referrer.h"
+#include "googleurl/src/gurl.h"
+#include "googleurl/src/url_canon.h"
+#include "ui/gfx/size.h"
+
+namespace {
+
+template<typename MapForwards, typename MapBackwards>
+bool MapsAreInverseOfEachOther(const MapForwards& map_forwards,
+                               const MapBackwards& map_backwards) {
+  if (map_forwards.size() != map_backwards.size())
+    return false;
+  for (typename MapForwards::const_iterator i = map_forwards.begin(),
+                                            e = map_forwards.end();
+       i != e; ++i) {

[dominich, 2012/04/26 22:50:58]

why do you need to declare e in the first part? ie, why not the more typical:

for (typename MapForwards::const_iterator i = map_forwards.begin(); 
     i != map_forwards.end(); ++i) {
  ...
}

[gavinp, 2012/04/27 20:31:32]

Pure superstition.  The standard guarantees that the standard container end()
etc... will run in constant time, but not how much constant time.  Running it
once and taking a copy is a hedge against a bad implementation of end.  We have
a good standard library on all platforms, so I am removing this for end.

However, in the situations where I loop on upper_bound(), I'm leaving it in
place: upper_bound() has a complexity guarantee of only log(size()) on the
standard associative containers, so without the copy I'm doing an
O(n*log(size()) loop, which is probably worth the copy to avoid.

+    // Best to use std::count here both times, as
+    // AssociativeContainer::count returns size_t, vs. std::count
+    // returning iterator_traits<InputIterator>::difference_type
+    typedef typename std::iterator_traits<
+        typename MapForwards::iterator>::difference_type diff_type;
+    diff_type forwards_count =
+        std::count(map_forwards.begin(), map_forwards.end(),
+                   typename MapForwards::value_type(i->first, i->second));
+    diff_type backwards_count =
+        std::count(map_backwards.begin(), map_backwards.end(),
+                   typename MapBackwards::value_type(i->second, i->first));
+    if (forwards_count != backwards_count) {

[dominich, 2012/04/26 22:50:58]

nit: {} not necessary here

[gavinp, 2012/04/27 20:31:32]

Done.

+      return false;
+    }
+  }
+  return true;
+}
+
+}
+
+namespace prerender {
+
+PrerenderLinkManager::PrerenderLinkManager(

[dominich, 2012/04/26 22:50:58]

nit: unnecessary to wrap this line

[gavinp, 2012/04/27 20:31:32]

Done.

+    PrerenderManager* manager)
+    : manager_(manager) {
+}
+
+PrerenderLinkManager::~PrerenderLinkManager() {
+}
+
+bool PrerenderLinkManager::OnAddPrerender(int child_id,
+                                          int prerender_id,
+                                          const GURL& orig_url,
+                                          const content::Referrer& referrer,
+                                          const gfx::Size& ALLOW_UNUSED size,
+                                          int render_view_route_id) {
+  DVLOG(2) << "OnAddPrerender, child_id = " << child_id
+           << ", prerender_id = " << prerender_id
+           << ", url = " << orig_url.spec();
+  DVLOG(3) << "... render_view_route_id = " << render_view_route_id
+           << ", referrer url = " << referrer.url.spec();
+  DCHECK(MapsAreInverseOfEachOther(ids_to_url_map_, urls_to_id_map_));
+  // TODO(gavinp): Add tests to insure fragments work, then remove this fragment
+  // clearing code.
+  url_canon::Replacements<char> replacements;
+  replacements.ClearRef();
+  const GURL url = orig_url.ReplaceComponents(replacements);
+
+  // TODO(gavinp,dominich): After the Prerender API can send events back to

[dominich, 2012/04/26 22:50:58]

From this code, I don't see why the urls_to_id_map_ is needed. It looks like
it's just inserting and erasing from it without using the contents. What am I
missing?

[gavinp, 2012/04/27 20:31:32]

Two links prerender the same page from the same origin; for instance, from a
page, and from an iframe contained in the page.  One of them cancels the
prerender.  This map is currently used in OnCancelPrerender() to figure out what
happens to the underlying prerender, when.  There are browser tests that depend
on this.

There was a discussion in the last bug about if I should just be keeping the map
from urls, with counts:
http://codereview.chromium.org/9875026/diff/2001/chrome/browser/prerender/pre...


My claim remains that this work will end up being needed when events go both
ways, and I didn't want to write this twice.

[dominich, 2012/04/27 21:52:01]

So they'd have the same child_id but different prerender_ids, no?
Perhaps it would be better to propagate the prerender_id (or
child_and_prerender_id) to PrerenderManager instead of using the URL as the key
there.

[gavinp, 2012/04/27 23:31:45]

Yes.  However, notice that OnCancelPrerender has different behaviour depending
on if the url is in urls_to_id_map_?  It's 37 lines down from here.  When you
remove the first link, the prerender stays alive.  When you remove the second,
we kill it.
That sounds to me like making this entire class part of the PrerenderManager,
that's a viable strategy, but I find the PrerenderManager too confusing already;
why not separate out the semantics of links from it?

I'd like to see a PrerenderManager that is concerned with managing prerenders
through their lifetime, and notifying observers as needed.  If a launcher has
different semantics, they should implement those in a separate class which is a
user and/or observer of a simpler PrerenderManager.  I know I haven't done that
yet, PrerenderManager::AddLinkFromRel... is still there, but my hope is to just
add links to the prerendermanager based on their proper unique ID, and deal with
them through that.

What distinguishes prerenders is, I believe, the pair<GURL, int
web_storage_namespace>, although that bears some more thought.  So eventually
some object like that will be in the url side of these maps; and this
prerender_link_manager will be 

+  // their client links, revisit having both maps and all the trouble that
+  // causes.
+  const bool did_successfully_add = manager_->AddPrerenderFromLinkRelPrerender(
+      child_id, render_view_route_id, url, referrer);
+  const ChildAndPrerenderIdPair child_and_prerender_id(child_id, prerender_id);
+  DCHECK(ids_to_url_map_.find(child_and_prerender_id) == ids_to_url_map_.end());
+  ids_to_url_map_.insert(std::make_pair(child_and_prerender_id, url));

[dominich, 2012/04/26 22:50:58]

Why insert these if |did_successfully_add| is false? OnCancel and OnAbandon
already search the map and handles them not being there.

[gavinp, 2012/04/27 20:31:32]

Done.  What I liked about the original approach was that a debug build had a
nice NOTREACHED() when the API double-canceled, but this is a release, let's
drop it.

+  urls_to_id_map_.insert(std::make_pair(url, child_and_prerender_id));
+  DCHECK(MapsAreInverseOfEachOther(ids_to_url_map_, urls_to_id_map_));
+  return did_successfully_add;
+}
+
+void PrerenderLinkManager::OnCancelPrerender(int prerender_id,
+                                             int child_id) {
+  DVLOG(2) << "OnCancelPrerender, child_id = " << child_id
+           << ", prerender_id = " << prerender_id;
+  const ChildAndPrerenderIdPair child_and_prerender_id(child_id, prerender_id);
+  IdPairToUrlMap::iterator id_url_iter =
+      ids_to_url_map_.find(child_and_prerender_id);
+  if (id_url_iter == ids_to_url_map_.end()) {
+    NOTREACHED() << "Canceling a prerender that doesn't exist.";
+    return;
+  }
+  const GURL url = id_url_iter->second;
+  RemovePrerender(id_url_iter);
+
+  if (urls_to_id_map_.find(url) != urls_to_id_map_.end())
+    return;
+
+  // TODO(gavinp): Track down the correct prerender and stop it, rather than
+  // this nuclear option, which assumes that only one prerender at a time
+  // runs.
+  if (PrerenderContents* contents = manager_->GetEntry(url))
+    contents->Destroy(FINAL_STATUS_CANCELLED);
+}
+
+void PrerenderLinkManager::OnAbandonPrerender(int prerender_id, int child_id) {
+  DVLOG(2) << "OnAbandonPrerender, child_id = " << child_id
+           << ", prerender_id = " << prerender_id;
+  // TODO(gavinp,cbentzel): Implement reasonable behaviour for
+  // navigation away from launcher.
+  const ChildAndPrerenderIdPair child_and_prerender_id(child_id, prerender_id);
+  IdPairToUrlMap::iterator id_url_iter =
+      ids_to_url_map_.find(child_and_prerender_id);
+  if (id_url_iter == ids_to_url_map_.end()) {
+    // FIXME(gavinp): Currently, canceled prerenders also get abandoned later.
+    // When the WebKit fix to stop this lands, add a NOTREACHED() here.
+    return;
+  }
+  RemovePrerender(id_url_iter);
+}
+
+void PrerenderLinkManager::OnChannelClosing(int child_id) {
+  DVLOG(2) << "OnChannelClosing, child id = " << child_id;
+  const ChildAndPrerenderIdPair child_and_minimum_prerender_id(
+      child_id, std::numeric_limits<int>::min());
+  const ChildAndPrerenderIdPair child_and_maximum_prerender_id(
+      child_id, std::numeric_limits<int>::max());
+  std::queue<int> prerender_ids_to_abandon;
+  for (IdPairToUrlMap::iterator
+           i = ids_to_url_map_.lower_bound(child_and_minimum_prerender_id),
+           e = ids_to_url_map_.upper_bound(child_and_maximum_prerender_id);
+       i != e; ++i) {
+    prerender_ids_to_abandon.push(i->first.second);
+  }
+  while (!prerender_ids_to_abandon.empty()) {
+    DVLOG(4) << "---> abandon prerender_id = "
+             << prerender_ids_to_abandon.front();
+    OnAbandonPrerender(prerender_ids_to_abandon.front(), child_id);
+    prerender_ids_to_abandon.pop();
+  }
+}
+
+void PrerenderLinkManager::RemovePrerender(
+    const IdPairToUrlMap::iterator& id_url_iter) {
+  DCHECK(MapsAreInverseOfEachOther(ids_to_url_map_, urls_to_id_map_));
+  const GURL url = id_url_iter->second;
+  const ChildAndPrerenderIdPair child_and_prerender_id = id_url_iter->first;
+  ids_to_url_map_.erase(id_url_iter);
+
+  for (UrlToIdPairMap::iterator i = urls_to_id_map_.lower_bound(url),
+                                e = urls_to_id_map_.upper_bound(url);

[gavinp, 2012/04/27 20:31:32]

I'm leaving this one here, multimap::upper_bound() is not cheap (see discussion
above).

+       i != e; ++i) {
+    if (i->second == child_and_prerender_id) {
+      urls_to_id_map_.erase(i);
+      DCHECK(MapsAreInverseOfEachOther(ids_to_url_map_, urls_to_id_map_));
+      return;
+    }
+  }
+  NOTREACHED();
+}
+
+bool PrerenderLinkManager::IsEmpty() const {
+  return ids_to_url_map_.empty();
+}
+
+}  // namespace prerender
+