Multi-Process Find-in-Page.

content/browser/find_request_manager.cc

 // Copyright 2016 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 "content/browser/find_request_manager.h"
 
 #include "content/browser/frame_host/render_frame_host_impl.h"
 #include "content/browser/web_contents/web_contents_impl.h"
 #include "content/common/frame_messages.h"
 #include "content/common/input_messages.h"
 
 namespace content {
 
+namespace {
+
+// Returns the key for the frame associated with |rfh|.
+FindRequestManager::FrameKey GetFrameKey(RenderFrameHost* rfh) {
+  return std::make_pair(rfh->GetProcess()->GetID(), rfh->GetRoutingID());
+}
+
+// Returns the RenderFrameHostImpl associated with |frame_key|.
+RenderFrameHostImpl* GetRenderFrameHost(
+    const FindRequestManager::FrameKey& frame_key) {
+  return RenderFrameHostImpl::FromID(frame_key.first, frame_key.second);
+}
+
+// Returns the deepest last child frame under |node|/|rfh| in the frame tree.
+FrameTreeNode* GetDeepestLastChild(FrameTreeNode* node) {
+  while (node->child_count())
+    node = node->child_at(node->child_count() - 1);
+  return node;
+}
+RenderFrameHost* GetDeepestLastChild(RenderFrameHost* rfh) {
+  FrameTreeNode* node =
+      static_cast<RenderFrameHostImpl*>(rfh)->frame_tree_node();
+  return GetDeepestLastChild(node)->current_frame_host();
+}
+
+// Returns the FrameTreeNode directly after |node| in the frame tree in search
+// order, or nullptr if one does not exist. If |wrap| is set, then wrapping
+// between the first and last frames is permitted. Note that this traversal
+// follows the same ordering as in blink::FrameTree::traverseNextWithWrap().
+FrameTreeNode* TraverseNext(FrameTreeNode* node, bool wrap) {
+  if (node->child_count())
+    return node->child_at(0);
+
+  FrameTreeNode* sibling = node->NextSibling();
+  while (!sibling) {
+    if (!node->parent())
+      return wrap ? node : nullptr;
+    node = node->parent();
+    sibling = node->NextSibling();
+  }
+  return sibling;
+}
+
+// Returns the FrameTreeNode directly before |node| in the frame tree in search
+// order, or nullptr if one does not exist. If |wrap| is set, then wrapping
+// between the first and last frames is permitted. Note that this traversal
+// follows the same ordering as in blink::FrameTree::traversePreviousWithWrap().
+FrameTreeNode* TraversePrevious(FrameTreeNode* node, bool wrap) {
+  if (FrameTreeNode* previous_sibling = node->PreviousSibling())
+    return GetDeepestLastChild(previous_sibling);
+  if (node->parent())
+    return node->parent();
+  return wrap ? GetDeepestLastChild(node) : nullptr;
+}
+
+// The same as either TraverseNext() or TraversePrevious() depending on
+// |forward|.
+FrameTreeNode* TraverseNode(FrameTreeNode* node, bool forward, bool wrap) {
+  return forward ? TraverseNext(node, wrap) : TraversePrevious(node, wrap);
+}

[ncarter (slow), 2016/05/23 21:59:16]

Could you move these to FrameTree or FrameTreeNode, and add unittests for them
in frame_tree_unittest.cc? You could even just extend FrameTreeTest.Shape with
some new asserts.

The wrapping logic probably can stay here.

FWIW, I understand that the FrameTree::Nodes() ordering is different from this.
If I read the wikipedia page right, I think FrameTree::Nodes() does treeorder
traversal, and find-in-page needs preorder traversal. I don't think there's any
reason why FrameTree::Nodes() couldn't be preorder as well -- the only property
we really need for FrameTree::NodeS() is for parents to be visited before
children. So, long term I would not mind unifying the two (e.g., implementing
the NodeIterator in terms of these tree traversal functions), but doing so
doesn't block this CL.

[paulmeyer, 2016/05/30 15:08:22]

As discussed offline, I can look into moving these and changing the ordering of
Nodes() in a future patch.

+
+}  // namespace
+
+#if defined(OS_ANDROID)
+FindRequestManager::FindMatchRectsState::FindMatchRectsState() = default;
+FindRequestManager::FindMatchRectsState::~FindMatchRectsState() {}
+#endif
+
 // static
 const int FindRequestManager::kInvalidId = -1;
 
 FindRequestManager::FindRequestManager(WebContentsImpl* web_contents)
-    : contents_(web_contents),
+    : WebContentsObserver(web_contents),
+      contents_(web_contents),
       current_session_id_(kInvalidId),
+      pending_active_match_ordinal_(kInvalidId),
       number_of_matches_(0),
+      relative_active_match_ordinal_(
+          std::make_pair(std::make_pair(kInvalidId, kInvalidId), 0)),
       active_match_ordinal_(0) {}
 
 FindRequestManager::~FindRequestManager() {}
 
 void FindRequestManager::Find(int request_id,
                               const base::string16& search_text,
                               const blink::WebFindOptions& options) {
   // Every find request must have a unique ID, and these IDs must strictly
   // increase so that newer requests always have greater IDs than older
   // requests.
   DCHECK_GT(request_id, current_request_.id);
   DCHECK_GT(request_id, current_session_id_);
 
-  FindRequest request(request_id, search_text, options);
-
-  if (options.findNext) {
-    // This is a find next operation.
-
-    // This implies that there is an ongoing find session with the same search
-    // text.
-    DCHECK_GE(current_session_id_, 0);
-    DCHECK_EQ(request.search_text, current_request_.search_text);
-
-    current_request_ = request;
-  } else {
-    // This is an initial find operation.
-    Reset(request);
+  // If this is a new find session, clear any queued requests from last session.
+  if (!options.findNext) {
+    find_request_queue_ = std::queue<FindRequest>();
   }
 
-  SendFindIPC(request, contents_->GetMainFrame());
+  find_request_queue_.emplace(request_id, search_text, options);
+  if (find_request_queue_.size() == 1)
+    FindInternal(find_request_queue_.front());
 }
 
 void FindRequestManager::StopFinding(StopFindAction action) {
-  SendStopFindingIPC(action, contents_->GetMainFrame());
+  contents_->ForEachFrame(base::Bind(

[ncarter (slow), 2016/05/23 21:59:16]

We should skip !IsRenderFrameLive() frames.

SendToAllFrames does this automatically. Or, you can consider using a loop here
(over FrameTree::Nodes()) instead of ForEach() and a helper function.

[paulmeyer, 2016/05/30 15:08:22]

I'll just use SendToAllFrames in this case.

+      &FindRequestManager::SendStopFindingIPC, base::Unretained(this), action));
   current_session_id_ = kInvalidId;
+#if defined(OS_ANDROID)
+  // It is important that these pending replies are cleared whenever a find
+  // session ends, so that subsequent replies for the old session are ignored.
+  match_rects_.pending_replies.clear();
+#endif
 }
 
 void FindRequestManager::OnFindReply(RenderFrameHost* rfh,
                                      int request_id,
                                      int number_of_matches,
                                      const gfx::Rect& selection_rect,
                                      int active_match_ordinal,
                                      bool final_update) {
   // Ignore stale replies from abandoned find sessions.
   if (current_session_id_ == kInvalidId || request_id < current_session_id_)
     return;
+  DCHECK(CheckFrame(rfh));
+
+  FrameKey frame_key = GetFrameKey(rfh);
 
   // Update the stored results.
-  number_of_matches_ = number_of_matches;
-  selection_rect_ = selection_rect;
-  active_match_ordinal_ = active_match_ordinal;
+  if (number_of_matches != -1) {

[ncarter (slow), 2016/05/23 21:59:16]

This use of sentinel values makes me wonder if we ought to break this IPC
message in half.

[paulmeyer, 2016/05/30 15:08:22]

As discussed offline, splitting this IPC may not make things simpler, but this
can be revisited in the future.

+    DCHECK_GE(number_of_matches, 0);
+    // Increment the global number of matches by the number of additional
+    // matches found for this frame.
+    auto matches_per_frame_it = matches_per_frame_.find(frame_key);
+    number_of_matches_ += number_of_matches - matches_per_frame_it->second;
+    matches_per_frame_it->second = number_of_matches;
+  }
+  if (!selection_rect.IsEmpty())
+    selection_rect_ = selection_rect;
+  if (active_match_ordinal > 0) {

[ncarter (slow), 2016/05/23 21:59:16]

Could we rename either active_match_ordinal or active_match_ordinal_? Since the
operation isn't a straight copy anymore, it's hard to follow what's going on
here.

[paulmeyer, 2016/05/30 15:08:22]

I'd actually really rather keep them the way they are, since they're named as
exactly what they are, and that's how these things are referred to in other
places. Also, |active_match_ordinal_| is only referred to once in this whole
function, so I think it should be okay.

I can see how this part of the function was a bit busy though...

I've added some comments and spacing to hopefully make it more clear where each
result is potentially updated. It's also a bit cleaner already after following
your comments about |relative_active_match_ordinal_| and |old_rfh|.

+    if (GetFrameKey(rfh) == relative_active_match_ordinal_.first) {
+      active_match_ordinal_ +=
+          active_match_ordinal - relative_active_match_ordinal_.second;

[ncarter (slow), 2016/05/23 21:59:16]

is the value of "(active_match_ordinal - relative_active_match_ordinal_.second)"
always either 1 or -1?

[paulmeyer, 2016/05/30 15:08:22]

No, it could be any arbitrary int. In a large frame, the user can click
somewhere else in the same frame and then "find next" to get the next active
match to be far away from the previous.

+      relative_active_match_ordinal_.second = active_match_ordinal;
+    } else {
+      if (relative_active_match_ordinal_.first.first != kInvalidId) {
+        RenderFrameHost* old_rfh =
+            GetRenderFrameHost(relative_active_match_ordinal_.first);
+        if (old_rfh && old_rfh != rfh) {

[ncarter (slow), 2016/05/23 21:59:16]

the != case here is impossible. We already checked for this on line 152.

Likewise, the !old_rfh case ought to be impossible, since we cleanup
relative_active_match_ordinal_.first on RenderFrameDeleted.

[paulmeyer, 2016/05/30 15:08:22]

Okay, you're right. I can just take out these conditions.

+          old_rfh->Send(new FrameMsg_ClearActiveFindMatch(
+              old_rfh->GetRoutingID()));
+        }
+      }
+      relative_active_match_ordinal_ =
+          std::make_pair(GetFrameKey(rfh), active_match_ordinal);
+      UpdateActiveMatchOrdinal();
+    }
+    if (pending_active_match_ordinal_ == request_id)
+      pending_active_match_ordinal_ = kInvalidId;
+    AdvanceQueue(request_id);
+  }

[ncarter (slow), 2016/05/23 21:59:16]

Looking at this function, I wondered: what if we try to advance the selection
into a subframe that previously reported matches, but for which no matches were
found?

[paulmeyer, 2016/05/30 15:08:22]

That case involves dynamically changing content (since previously existing
matches were removed somehow), which find-in-page does not currently handle. My
multi-process implementation also doesn't explicitly provide this functionality,
though it will never crash or do any worse than the current implementation (the
worst that can happen is that the number of matches or active match ordinal
might show incorrectly until the next find session).

That being said, I just tried this and this particular case actually happens to
be handled correctly by my implementation. It breaks the find session in stable
Chrome, so that's an improvement. :)

What happens in my code is the frame will be entered that previously had
matches, but no new active match will be returned (because there are none). This
will be caught in FinalUpdate(), which will then look for an active match in the
next frame it expects should have one. If that one also no longer has any, this
will continue until the next active match is found or no frames are left with
matches. The number of matches also gets updated by this, so everything works
out.

[ncarter (slow), 2016/05/23 21:59:16]

Possibly related to the previous comment: In a debug Windows build, I can repro
a renderer crash fairly in consistently with the following document (I didn't
gather a stack trace since my MSVC license decided to expire today). Keep
searching for variations of 'result' and hit enter/escape/Ctrl+S occasionally:

<!DOCTYPE html>
<html>
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0,
maximum-scale=1.0, user-scalable=no" />
</head>
<body>
RESULT result
<script>
/*
window.setInterval(function() {
	var ifr = document.createElement('iframe');
	ifr.srcdoc = "<script>window.setInterval(function() {
document.body.appendChild(document.createTextNode('result'));}, 7000)</sc" +
"ript>";
	document.body.appendChild(ifr);
}, 7000);
*/
window.setInterval(function() {
	var ifr = document.createElement('iframe');
	ifr.srcdoc = "<body>result result<script>window.setTimeout(function() {
document.write('cleared');}, 3000)</sc" + "ript>";
	document.body.appendChild(ifr);
}, 2000);

</script>
</body>
</html>

[paulmeyer, 2016/05/30 15:08:22]

I was able to repro this. It's this DCHECK in DocumentMarkerController.cpp:
https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...

Looks like there's an attempt to clear markers when there are already no
markers. This probably happened because there WERE matches in a frame that
showed "result result", but then it was changed to "cleared" so there were no
markers left. After talking to dcheng@ and roulan@, it looks like this is a
reasonable case, and the DCHECK should be changed to an early out.

I was able to get this to repro (not with your test page, but with a more direct
test) on ToT as well, so it is a separate bug from this CL. I will file a bug
and fix in a separate CL.

Bug filed: https://bugs.chromium.org/p/chromium/issues/detail?id=615160

-  NotifyFindReply(request_id, final_update);
+  if (!final_update) {
+    NotifyFindReply(request_id, false /* final_update */);
+    return;
+  }
+
+  // This is the final update for this frame for the current find operation.
+
+  pending_replies_.erase(frame_key);
+  if (request_id == current_session_id_ && !pending_replies_.empty()) {
+    NotifyFindReply(request_id, false /* final_update */);
+    return;
+  }
+  DCHECK(request_id == current_session_id_ ||
+         current_request_.options.findNext);
+
+  // This is the final update for the current find operation.
+  FinalUpdate(request_id, rfh);
+}
+
+void FindRequestManager::RemoveFrame(RenderFrameHost* rfh) {
+  RemoveFrame(GetFrameKey(rfh));
+}
+
+void FindRequestManager::RemoveFrame(const FrameKey& frame_key) {
+  if (current_session_id_ == kInvalidId || !CheckFrame(frame_key))
+    return;
+
+  if (pending_replies_.count(frame_key)) {
+    // A reply should not be expected from the removed frame.
+    pending_replies_.erase(frame_key);
+    if (pending_replies_.empty())
+      FinalUpdate(current_session_id_, GetRenderFrameHost(frame_key));
+  }
+
+#if defined(OS_ANDROID)
+  // A reply should not be expected from the removed frame.
+  RemoveNearestFindResultPendingReply(frame_key);
+  RemoveFindMatchRectsPendingReply(frame_key);
+
+  // Match rects in the removed frame are no longer relevant.
+  match_rects_.rects.erase(frame_key);
+#endif
+
+  // If matches are counted for the frame that is being removed, decrement the
+  // match total before erasing that entry.
+  auto it = matches_per_frame_.find(frame_key);
+  if (it != matches_per_frame_.end()) {
+    number_of_matches_ -= it->second;
+    matches_per_frame_.erase(it);
+  }
+
+  // Update the active match ordinal, since it may have changed.
+  if (relative_active_match_ordinal_.first == frame_key) {
+    relative_active_match_ordinal_ =
+        std::make_pair(std::make_pair(kInvalidId, kInvalidId), 0);
+  }
+  UpdateActiveMatchOrdinal();
+
+  NotifyFindReply(current_session_id_,
+                  pending_replies_.empty() /* final_update */);
 }
 
 #if defined(OS_ANDROID)
+FindRequestManager::ActivateNearestFindResultState::
+ActivateNearestFindResultState() = default;
+FindRequestManager::ActivateNearestFindResultState::
+ActivateNearestFindResultState(float x, float y)
+    : current_request_id(GetNextID()),
+      x(x),
+      y(y) {}
+FindRequestManager::ActivateNearestFindResultState::
+~ActivateNearestFindResultState() {};
+
 void FindRequestManager::ActivateNearestFindResult(float x,
                                                    float y) {
   if (current_session_id_ == kInvalidId)
     return;
 
-  auto rfh = contents_->GetMainFrame();
-  rfh->Send(new InputMsg_ActivateNearestFindResult(
-      rfh->GetRoutingID(), current_session_id_, x, y));
+  activate_ = ActivateNearestFindResultState(x, y);
+
+  contents_->ForEachFrame(base::Bind(

[ncarter (slow), 2016/05/23 21:59:16]

We should skip !IsRenderFrameLive() frames.

SendToAllFrames does this automatically. Or, you can consider using a loop here
(over FrameTree::Nodes()) instead of ForEach() and a helper function.

[paulmeyer, 2016/05/30 15:08:22]

I've removed SendGetNearestFindResultIPC() and just do what it did in a loop
through FrameTree::Nodes().

+      &FindRequestManager::SendGetNearestFindResultIPC,
+      base::Unretained(this)));
+}
+
+void FindRequestManager::GetNearestFindResultReply(RenderFrameHost* rfh,
+                                                   int request_id,
+                                                   float distance) {
+  FrameKey frame_key = GetFrameKey(rfh);
+
+  if (request_id != activate_.current_request_id ||
+      !activate_.pending_replies.count(frame_key)) {
+    return;
+  }
+
+  // Check if this frame has a nearer find result than the current nearest.
+  if (distance < activate_.nearest_distance) {
+    activate_.nearest_frame = frame_key;
+    activate_.nearest_distance = distance;
+  }
+
+  RemoveNearestFindResultPendingReply(frame_key);
 }
 
 void FindRequestManager::RequestFindMatchRects(int current_version) {
+  match_rects_.pending_replies.clear();
   match_rects_.request_version = current_version;
-  SendFindMatchRectsIPC(contents_->GetMainFrame());
+  contents_->ForEachFrame(base::Bind(

[ncarter (slow), 2016/05/23 21:59:16]

We should skip !IsRenderFrameLive() frames.

SendToAllFrames does this automatically. Or, you can consider using a loop here
(over FrameTree::Nodes()) instead of ForEach() and a helper function.

[paulmeyer, 2016/05/30 15:08:22]

I've removed SendFindMatchRectsIPC(). I'll just do what it did in a loop through
FrameTree::Nodes().

+      &FindRequestManager::SendFindMatchRectsIPC, base::Unretained(this)));
 }
 
 void FindRequestManager::OnFindMatchRectsReply(
     RenderFrameHost* rfh,
     int version,
     const std::vector<gfx::RectF>& rects,
     const gfx::RectF& active_rect) {
-  contents_->NotifyFindMatchRectsReply(version, rects, active_rect);
+  FrameKey frame_key = GetFrameKey(rfh);
+  auto it = match_rects_.rects.find(frame_key);
+  if (it == match_rects_.rects.end() || it->second.first != version) {
+    // New version of rects has been received, so update the data.
+    match_rects_.rects[frame_key] = std::make_pair(version, rects);
+    ++match_rects_.known_version;
+  }
+  if (!active_rect.IsEmpty())
+    match_rects_.active_rect = active_rect;
+  RemoveFindMatchRectsPendingReply(frame_key);
 }
 #endif
 
+void FindRequestManager::RenderFrameDeleted(RenderFrameHost* rfh) {
+  RemoveFrame(rfh);
+}
+
+void FindRequestManager::FrameDeleted(RenderFrameHost* rfh) {

[ncarter (slow), 2016/05/23 21:59:16]

Usually if you care about FrameDeleted (which is what happens when an FTN goes
away), you care about RenderFrameHostChanged too (which is what happens when an
FTN navigates to a different process, changing the value of current_frame_host()
for the node).

Here I think you probably need overrides for all three:
 - RenderFrameDeleted to handle the case that a subframe crashes.
 - FrameDeleted to handle a case that the parent document deletes its iframe
element
 - RenderFrameHostChanged to handle cross-process navigation (just RemoveFrame
on (old_frame)).

[paulmeyer, 2016/05/30 15:08:23]

I wasn't aware of that case; thanks for catching that! Done.

+  RemoveFrame(rfh);
+}

[ncarter (slow), 2016/05/23 21:59:16]

Based on my manual testing of this patch, it seems like we are taking a slight
regression vs TOT, in the following two behaviors:

 - When a new iframe is added during the course of the session, we won't descend
into it.

 - If an iframe exists at the beginning of the session, but initially has no
matches, and then later its document is updated to have matches, we will never
visit those matches. Even if you delete and re-type the last character of the
search text, it seems like there's a case where we skip over a frame with
matches in it.

Can these be reasonably fixed? The following html snippet demonstrates the above
problems.

<script>
window.setInterval(function() {
document.body.appendChild(document.createTextNode('result'));}, 5000);

window.setInterval(function() {
	var ifr = document.createElement('iframe');
	ifr.srcdoc = "<script>window.setInterval(function() {
document.body.appendChild(document.createTextNode('result'));}, 7000)</sc" +
"ript>";
	document.body.appendChild(ifr);
}, 7000);

</script>

[paulmeyer, 2016/05/30 15:08:22]

For the first case:

As a kind of dynamic content change, this is something that is not handled in
all cases on ToT or in my implementation. When adding a frame mid-session,
neither ToT nor my implementation will search it. What I think you're seeing is
if after adding the new frame you then "find next" past the end of a previous
frame, the frame then gets searched. This only happens because of a very recent
addition to find-in-page that triggers a new search of the whole page if a new
active match is discovered that isn't already in the list of scoped matches.
This only happens when a "find next" runs into it on the way to another match
(because the whole page is not searched during a "find next" operation).

I didn't plan for this functionality initially since it wasn't around when I
started, but I have included it now. The only reason you're not seeing it
working with my CL in this case is because on ToT, the whole page including text
in iframes is treated as one search space. In my implementation, each frame is
essentially its own search space, so text in new frames just isn't hit during
"find next" operations, and so that new functionality doesn't come into effect.

Since this kind of case is not officially supported by find-in-page now, and
because the "best effort" partial solution is very new, I would be okay with
leaving this case out in this CL (I feel it's just a bit too much to add in to
this already large patch). I would really like to add support for this in a
future CL though, including searching new frames right when they're added, which
ToT does not do.


For the second case:

I was able to repro this bug on ToT as well, so it is not something new in my
CL. It is definitely a bug though.

I wouldn't expect matches to be found when they are added, since that was never
supported, but I agree that it is a bug for new text not to get searched when
starting new find sessions (such as when deleting the last letter in the find
bar). I've noticed that the only way I can get these matches to be searched is
to close the find bar (which triggers StopFinding()) and then search again.

I'm not sure what's causing this bug yet, but it is somewhere in Blink (not in
my code). I will try to make a more concise test page and file a bug for this.

[paulmeyer, 2016/05/31 14:32:38]

More info about second case: This actually isn't a bug. This behavior is
documented:
https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...

"// Determines whether the scoping effort is required for a particular frame.
// It is not necessary if the frame is invisible, for example, or if this
// is a repeat search that already returned nothing last time the same prefix
// was searched.
bool shouldScopeMatches(const WTF::String& searchText);"

So basically, if the frame was already searched and had no matches, if you try
to search it again for a string with the same prefix, it won't bother trying to
search because it assumes nothing will be there (dynamic content not supported).

+
 void FindRequestManager::Reset(const FindRequest& initial_request) {
   current_session_id_ = initial_request.id;
   current_request_ = initial_request;
+  pending_replies_.clear();
+  pending_active_match_ordinal_ = initial_request.id;
+  matches_per_frame_.clear();
   number_of_matches_ = 0;
+  relative_active_match_ordinal_ =
+      std::make_pair(std::make_pair(kInvalidId, kInvalidId), 0);
   active_match_ordinal_ = 0;
   selection_rect_ = gfx::Rect();
 #if defined(OS_ANDROID)
-  match_rects_ = FindMatchRectsState();
+  activate_ = ActivateNearestFindResultState();
+  match_rects_.pending_replies.clear();
 #endif
 }
 
+void FindRequestManager::FindInternal(const FindRequest& request) {
+  DCHECK_GT(request.id, current_request_.id);
+  DCHECK_GT(request.id, current_session_id_);
+
+  if (request.options.findNext) {
+    // This is a find next operation.
+
+    // This implies that there is an ongoing find session with the same search
+    // text.
+    DCHECK_GE(current_session_id_, 0);
+    DCHECK_EQ(request.search_text, current_request_.search_text);
+
+    // The find next request will be directed at the focused frame if there is
+    // one, or the first frame with matches otherwise.
+    RenderFrameHost* target_rfh = contents_->GetFocusedFrame();
+    if (!target_rfh || !CheckFrame(target_rfh))
+      target_rfh = GetInitialFrame(request.options.forward);
+
+    SendFindIPC(request, target_rfh);
+    current_request_ = request;
+    pending_active_match_ordinal_ = request.id;
+    return;
+  }
+
+  // This is an initial find operation.
+  Reset(request);
+  contents_->ForEachFrame(base::Bind(&FindRequestManager::AddFrame,

[ncarter (slow), 2016/05/23 21:59:16]

We should skip !IsRenderFrameLive() frames.

You can consider using a loop here (over FrameTree::Nodes()) instead of
ForEach() and a helper function.

[paulmeyer, 2016/05/30 15:08:23]

I'll use a loop over FrameTree::Nodes() here too.

+                                     base::Unretained(this)));
+}
+
+void FindRequestManager::AdvanceQueue(int request_id) {
+  if (find_request_queue_.empty() ||
+      request_id != find_request_queue_.front().id) {
+    return;
+  }
+
+  find_request_queue_.pop();
+  if (!find_request_queue_.empty())
+    FindInternal(find_request_queue_.front());
+}
+
 void FindRequestManager::SendFindIPC(const FindRequest& request,
                                      RenderFrameHost* rfh) {
+  pending_replies_.insert(GetFrameKey(rfh));
   rfh->Send(new FrameMsg_Find(rfh->GetRoutingID(), request.id,
                               request.search_text, request.options));
 }
 
 void FindRequestManager::SendStopFindingIPC(StopFindAction action,
                                             RenderFrameHost* rfh) const {
   rfh->Send(new FrameMsg_StopFinding(rfh->GetRoutingID(), action));
 }
 
 void FindRequestManager::NotifyFindReply(int request_id,
                                          bool final_update) const {
   if (request_id == kInvalidId) {
     NOTREACHED();
     return;
   }
 
   contents_->NotifyFindReply(request_id, number_of_matches_, selection_rect_,
                              active_match_ordinal_, final_update);
 }
 
+RenderFrameHost* FindRequestManager::GetInitialFrame(bool forward) const {
+  RenderFrameHost* rfh = contents_->GetMainFrame();
+
+  if (!forward)
+    rfh = GetDeepestLastChild(rfh);
+
+  return rfh;
+}
+
+RenderFrameHost* FindRequestManager::Traverse(RenderFrameHost* rfh,
+                                              bool forward,
+                                              bool matches_only,
+                                              bool wrap) const {
+  FrameTreeNode* node =
+      static_cast<RenderFrameHostImpl*>(rfh)->frame_tree_node();
+
+  while ((node = TraverseNode(node, forward, wrap)) != nullptr) {
+    if (!CheckFrame(node->current_frame_host()))
+      continue;
+    FrameKey frame_key = GetFrameKey(node->current_frame_host());
+    if (!matches_only || matches_per_frame_.find(frame_key)->second ||
+        pending_replies_.count(frame_key)) {
+      // Note that if there is still a pending reply expected for this frame,
+      // then it may have unaccounted matches and will not be skipped via
+      // |matches_only|.
+      return node->current_frame_host();
+    }
+    if (wrap && node->current_frame_host() == rfh)
+      return nullptr;
+  }
+
+  return nullptr;
+}
+
+void FindRequestManager::AddFrame(RenderFrameHost* rfh) {
+  FrameKey frame_key = GetFrameKey(rfh);
+  // A frame that is already being searched should not be added again.
+  DCHECK(!CheckFrame(frame_key));
+
+  matches_per_frame_[frame_key] = 0;
+
+  FindRequest request = current_request_;
+  request.id = current_session_id_;
+  request.options.findNext = false;
+  SendFindIPC(request, rfh);
+}
+
+bool FindRequestManager::CheckFrame(RenderFrameHost* rfh) const {
+  return rfh ? CheckFrame(GetFrameKey(rfh)) : false;
+}
+
+bool FindRequestManager::CheckFrame(const FrameKey& frame_key) const {
+  return matches_per_frame_.count(frame_key) == 1;
+}
+
+void FindRequestManager::UpdateActiveMatchOrdinal() {
+  if (relative_active_match_ordinal_.first.first == kInvalidId ||
+      relative_active_match_ordinal_.first.second == kInvalidId ||
+      relative_active_match_ordinal_.second == 0) {
+    active_match_ordinal_ = 0;
+    return;
+  }
+
+  RenderFrameHost* rfh =
+      GetRenderFrameHost(relative_active_match_ordinal_.first);
+  if (!rfh) {
+    RemoveFrame(relative_active_match_ordinal_.first);
+    active_match_ordinal_ = 0;
+    return;
+  }
+
+  // Traverse the frame tree backwards (in search order) and count all of the
+  // matches in frames before the frame with the active match, in order to
+  // determine the overall active match ordinal.
+  active_match_ordinal_ = 0;
+  while ((rfh = Traverse(rfh,
+                         false /* forward */,
+                         true /* matches_only */,
+                         false /* wrap */)) != nullptr) {
+    active_match_ordinal_ += matches_per_frame_[GetFrameKey(rfh)];
+  }
+  active_match_ordinal_ += relative_active_match_ordinal_.second;
+}
+
+void FindRequestManager::FinalUpdate(int request_id, RenderFrameHost* rfh) {
+  if (!number_of_matches_ || pending_active_match_ordinal_ != request_id) {
+    NotifyFindReply(request_id, true /* final_update */);
+    AdvanceQueue(request_id);
+    return;
+  }
+
+  // There are matches, but no active match was returned, so another find next
+  // request must be sent.
+
+  DCHECK_EQ(request_id, current_request_.id);
+  RenderFrameHost* target_rfh;
+  if (current_request_.options.findNext) {
+    // If this was a find next operation, then the active match will be in the
+    // next frame with matches after this one.
+    target_rfh = Traverse(static_cast<RenderFrameHostImpl*>(rfh),
+                          current_request_.options.forward,
+                          true /* matches_only */,
+                          true /* wrap */);
+  } else if ((target_rfh = contents_->GetFocusedFrame()) != nullptr) {
+    // Otherwise, if there is a focused frame, then the active match will be in
+    // the next frame with matches after that one.
+    target_rfh = Traverse(target_rfh,
+                          current_request_.options.forward,
+                          true /* matches_only */,
+                          true /* wrap */);
+  } else {
+    // Otherwise, the first frame with matches will have the active match.
+    target_rfh = GetInitialFrame(current_request_.options.forward);
+    if (!CheckFrame(target_rfh) ||
+        !matches_per_frame_[GetFrameKey(target_rfh)]) {
+      target_rfh = Traverse(target_rfh,
+                            current_request_.options.forward,
+                            true /* matches_only */,
+                            false /* wrap */);
+    }
+  }
+  DCHECK(target_rfh);
+
+  // Forward the find reply without |final_update| set because the active match
+  // has not yet been found.
+  NotifyFindReply(request_id, false /* final_update */);
+
+  current_request_.options.findNext = true;
+  SendFindIPC(current_request_, target_rfh);
+}
+
 #if defined(OS_ANDROID)
+void FindRequestManager::SendGetNearestFindResultIPC(RenderFrameHost* rfh) {
+  FrameKey frame_key = GetFrameKey(rfh);
+  if (!CheckFrame(frame_key))
+    return;
+
+  activate_.pending_replies.insert(GetFrameKey(rfh));
+  rfh->Send(new FrameMsg_GetNearestFindResult(
+      rfh->GetRoutingID(), activate_.current_request_id,
+      activate_.x, activate_.y));
+}
+
+void FindRequestManager::RemoveNearestFindResultPendingReply(
+    FrameKey frame_key) {
+  auto it = activate_.pending_replies.find(frame_key);
+  if (it != activate_.pending_replies.end()) {
+    activate_.pending_replies.erase(it);
+    if (activate_.pending_replies.empty() &&
+        CheckFrame(activate_.nearest_frame)) {
+      RenderFrameHostImpl* rfh = GetRenderFrameHost(activate_.nearest_frame);
+      rfh->Send(new FrameMsg_ActivateNearestFindResult(
+          rfh->GetRoutingID(), current_session_id_, activate_.x, activate_.y));
+    }
+  }
+}
+
 void FindRequestManager::SendFindMatchRectsIPC(RenderFrameHost* rfh) {
-  rfh->Send(new FrameMsg_FindMatchRects(rfh->GetRoutingID(),
-                                        match_rects_.request_version));
+  FrameKey frame_key = GetFrameKey(rfh);
+  if (!CheckFrame(frame_key))
+    return;
+
+  match_rects_.pending_replies.insert(frame_key);
+  auto it = match_rects_.rects.find(frame_key);
+  int version =
+      (it != match_rects_.rects.end()) ? it->second.first : kInvalidId;
+  rfh->Send(new FrameMsg_FindMatchRects(rfh->GetRoutingID(), version));
+}
+
+void FindRequestManager::RemoveFindMatchRectsPendingReply(FrameKey frame_key) {
+  auto it = match_rects_.pending_replies.find(frame_key);
+  if (it == match_rects_.pending_replies.end())
+    return;
+
+  match_rects_.pending_replies.erase(it);
+  if (match_rects_.pending_replies.empty()) {
+    // All replies are in.
+    std::vector<gfx::RectF> rects;
+    if (match_rects_.request_version != match_rects_.known_version) {
+      // Request version is stale, so aggregate and report the newer find
+      // match rects.
+      for (auto& entry : match_rects_.rects) {
+        std::vector<gfx::RectF>& frame_rects = entry.second.second;
+        rects.insert(rects.end(), frame_rects.begin(), frame_rects.end());
+      }
+    }
+    contents_->NotifyFindMatchRectsReply(
+        match_rects_.known_version, rects, match_rects_.active_rect);
+  }
 }
 #endif
 
 }  // namespace content