Multi-Process Find-in-Page.

content/browser/find_request_manager.h

 // 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.
 
 #ifndef CONTENT_BROWSER_FIND_REQUEST_MANAGER_H_
 #define CONTENT_BROWSER_FIND_REQUEST_MANAGER_H_
 
+#include <map>
+#include <queue>
 #include <set>
+#include <utility>
 #include <vector>
 
+#include "content/common/content_export.h"
+#include "content/public/browser/web_contents_observer.h"
 #include "content/public/common/stop_find_action.h"
 #include "third_party/WebKit/public/web/WebFindOptions.h"
 #include "ui/gfx/geometry/rect.h"
 #include "ui/gfx/geometry/rect_f.h"
 
 namespace content {

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

I patched this in. It works great and it handled everything I threw at it,
including using devtools to delete random nodes from
file:///C:/src/cr/src/content/test/data/cross_site_iframe_factory.html?a(a(a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a),a(a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a),a(a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a),a(a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a(a(a,a,a,a),a(a,a,a,a),a(a,a,a,a),a(a,a,a,a)),a))

Nice work.

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

Thanks!

 
 class RenderFrameHost;
 class WebContentsImpl;
 
 // FindRequestManager manages all of the find-in-page requests/replies
 // initiated/received through a WebContents. It coordinates searching across
 // multiple (potentially out-of-process) frames, handles the aggregation of find
 // results from each frame, and facilitates active match traversal. It is
 // instantiated once per WebContents, and is owned by that WebContents.
-//
-// TODO(paulmeyer): FindRequestManager is currently incomplete and does not do
-// all of these things yet, but will soon.
-class FindRequestManager {
+class CONTENT_EXPORT FindRequestManager : public WebContentsObserver {
  public:
+  // Frames can be uniquely identified by a (process ID, frame ID) pair.
+  using FrameKey = std::pair<int, int>;

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

Some places have started to use content/browser/loader/global_routing_id.h for
this.

Did you consider simply using RenderFrameHostImpl* ptrs as keys instead? It
seems like you are cleaning up your FrameKeys at RenderFrameDeleted time anyway,
so you don't need to worry about use-after-free.

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

I'm usually wary of holding onto pointers, but since I'm using a
WebContentsObserver to ensure the pointers are good anyways, I agree that I
might as well use them. :)

I've removed the use of FrameKey and switched them all to RenderFrameHost*
pointers.

+
   explicit FindRequestManager(WebContentsImpl* web_contents);
-  ~FindRequestManager();
+  ~FindRequestManager() override;
 
   // Initiates a find operation for |search_text| with the options specified in
   // |options|. |request_id| uniquely identifies the find request.
   void Find(int request_id,
             const base::string16& search_text,
             const blink::WebFindOptions& options);
 
   // Stops the active find session and clears the general highlighting of the
   // matches. |action| determines whether the last active match (if any) will be
   // activated, cleared, or remain highlighted.
   void StopFinding(StopFindAction action);
 
   // Called when a reply is received from a frame with the results from a
   // find request.
   void OnFindReply(RenderFrameHost* rfh,
                    int request_id,
                    int number_of_matches,
                    const gfx::Rect& selection_rect,
                    int active_match_ordinal,
                    bool final_update);
 
+  // Removes a frame from the set of frames being searched. This should be
+  // called whenever a frame is discovered to no longer exist.
+  void RemoveFrame(RenderFrameHost* rfh);
+  void RemoveFrame(const FrameKey& frame_key);
+
 #if defined(OS_ANDROID)
   // Selects and zooms to the find result nearest to the point (x,y) defined in
   // find-in-page coordinates.
   void ActivateNearestFindResult(float x, float y);
 
+  // Called when a reply is received from a frame in response to the
+  // GetNearestFindResult IPC.
+  void GetNearestFindResultReply(RenderFrameHost* rfh,
+                                 int nearest_find_result_request_id,
+                                 float distance);
+
   // Requests the rects of the current find matches from the renderer process.
   void RequestFindMatchRects(int current_version);
 
-  // Called when a reply is received in response to a request for find match
-  // rects.
+  // Called when a reply is received from a frame in response to a request for
+  // find match rects.
   void OnFindMatchRectsReply(RenderFrameHost* rfh,
                              int version,
                              const std::vector<gfx::RectF>& rects,
                              const gfx::RectF& active_rect);
 #endif
 
  private:
   // An invalid ID. This value is invalid for any render process ID, render
   // frame ID, or find request ID.
   static const int kInvalidId;
 
   // The request data for a single find request.
   struct FindRequest {
     // The find request ID that uniquely identifies this find request.
     int id = kInvalidId;
 
     // The text that is being searched for in this find request.
     base::string16 search_text;
 
     // The set of find options in effect for this find request.
     blink::WebFindOptions options;
 
     FindRequest() = default;
     FindRequest(int id,
                 const base::string16& search_text,
                 const blink::WebFindOptions& options)
         : id(id), search_text(search_text), options(options) {}
   };
 
-  // Send a find IPC containing the find request |request| to the RenderFrame
+  // WebContentsObserver implementation.
+  void RenderFrameDeleted(RenderFrameHost* rfh) override;
+  void FrameDeleted(RenderFrameHost* rfh) override;
+
+  // Resets all of the per-session state for a new find-in-page session.
+  void Reset(const FindRequest& initial_request);
+
+  // Called internally as find requests come up in the queue.
+  void FindInternal(const FindRequest& request);
+
+  // Called when an informative response (a response with enough information to
+  // be able to route subsequent find requests) comes in for the find request
+  // with ID |request_id|. Advances the queue if appropriate.
+  void AdvanceQueue(int request_id);
+
+  // Sends a find IPC containing the find request |request| to the RenderFrame
   // associated with |rfh|.
   void SendFindIPC(const FindRequest& request, RenderFrameHost* rfh);
 
-  // Send a stop finding IPC to the RenderFrame associated with |rfh|.
+  // Sends a stop finding IPC to the RenderFrame associated with |rfh|.
   void SendStopFindingIPC(StopFindAction action, RenderFrameHost* rfh) const;
 
-  // Reset all of the per-session state for a new find-in-page session.
-  void Reset(const FindRequest& initial_request);
-
-  // Send the find results (as they currently are) to the WebContents.
+  // Sends the find results (as they currently are) to the WebContents.
   void NotifyFindReply(int request_id, bool final_update) const;
 
+  // Returns the initial frame in search order. This will be either the first
+  // frame, if searching forward, or the last frame, if searching backward.
+  RenderFrameHost* GetInitialFrame(bool forward) const;
+
+  // Traverses the frame tree to find and return the next RenderFrameHost after
+  // |rfh| in search order. |forward| indicates whether the frame tree should be
+  // traversed forward (if true) or backward (if false). If |matches_only| is
+  // set, then the frame tree will be traversed until the first frame is found
+  // for which matches have been found. If |wrap| is set, then the traversal can
+  // wrap around past the last frame to the first one (or vice-versa, if
+  // |forward| == false). If no frame can be found under these conditions,
+  // nullptr is returned.
+  RenderFrameHost* Traverse(RenderFrameHost* rfh,
+                            bool forward,
+                            bool matches_only,
+                            bool wrap) const;
+
+  // Adds a frame to the set of frames that are being searched. The new frame
+  // will automatically be searched when added, using the same options (stored
+  // in |current_request_.options|).
+  void AddFrame(RenderFrameHost* rfh);
+
+  // Returns whether the frame associated with |rfh| is in the set of frames
+  // being searched in the current find session.
+  bool CheckFrame(RenderFrameHost* rfh) const;
+  bool CheckFrame(const FrameKey& frame_key) const;
+
+  // Computes and updates |active_match_ordinal_| based on
+  // |relative_active_match_ordinal_|.
+  void UpdateActiveMatchOrdinal();
+
+  // Called when all pending find replies have been received.
+  void FinalUpdate(int request_id, RenderFrameHost* rfh);
+
 #if defined(OS_ANDROID)
-  // Request the latest find match rects from a frame.
+  // Requests the distance to the nearest find result in the frame associated
+  // with |rfh| from the point (x,y) defined in find-in-page coordinates.
+  void SendGetNearestFindResultIPC(RenderFrameHost* rfh);
+
+  // Called when a nearest find result reply is no longer pending for a frame.
+  void RemoveNearestFindResultPendingReply(FrameKey frame_key);
+
+  // Requests the latest find match rects from a frame.
   void SendFindMatchRectsIPC(RenderFrameHost* rfh);
 
+  // Called when a find match rects reply is no longer pending for a frame.
+  void RemoveFindMatchRectsPendingReply(FrameKey frame_key);
+
+  // State related to ActivateNearestFindResult requests.
+  struct ActivateNearestFindResultState {
+    // An ID to uniquely identify the current nearest find result request and
+    // its replies.
+    int current_request_id = kInvalidId;
+
+    // The x value of the requested point, in find-in-page coordinates.
+    float x = 0.0f;
+
+    // The y value of the requested point, in find-in-page coordinates.
+    float y = 0.0f;
+
+    // The distance to the nearest result found so far.
+    float nearest_distance = FLT_MAX;
+
+    // The frame containing the nearest result found so far.
+    FrameKey nearest_frame = std::make_pair(kInvalidId, kInvalidId);
+
+    // Nearest find result replies are still pending for these frames.
+    std::set<FrameKey> pending_replies;
+
+    ActivateNearestFindResultState();
+    ActivateNearestFindResultState(float x, float y);
+    ~ActivateNearestFindResultState();
+
+    static int GetNextID() {
+      static int next_id = 0;
+      return next_id++;
+    }
+  } activate_;
+
   // State related to FindMatchRects requests.
   struct FindMatchRectsState {
-    // The latest find match rects version known by the requester.
+    // The latest find match rects version known by the requester. This will be
+    // compared to |known_version_| after polling frames for updates to their
+    // match rects, in order to determine if the requester already has the
+    // latest version of rects or not.
     int request_version = kInvalidId;
+
+    // The current overall find match rects version known by FindRequestManager.
+    int known_version = 0;
+
+    // A map from each frame to its find match rects and the version number for
+    // those rects.
+    using RectData = std::pair<int, std::vector<gfx::RectF>>;

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

Sometimes we need a pair as a key for a data structure (so that comparison is
defined, a la FrameKey), but I don't see a good reason to ever use it like this.
Structs with named members produce much more readable, and greppable, code.

Please define a struct for this.

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

Done.

+    std::map<FrameKey, RectData> rects;
+
+    // The active find match rect.
+    gfx::RectF active_rect;
+
+    // Find match rects replies are still pending for these frames.
+    std::set<FrameKey> pending_replies;
+
+    FindMatchRectsState();
+    ~FindMatchRectsState();
   } match_rects_;
 #endif
 
   // The WebContents that owns this FindRequestManager.
   WebContentsImpl* const contents_;
 
   // The request ID of the initial find request in the current find-in-page
   // session, which uniquely identifies this session. Request IDs are included
   // in all find-related IPCs, which allows reply IPCs containing results from
   // previous sessions (with |request_id| < |current_session_id_|) to be easily
   // identified and ignored.
   int current_session_id_;
 
   // The current find request.
   FindRequest current_request_;
 
-  // The total number of matches found in the current find-in-page session.
+  // The set of frames that are still expected to reply to a pending find
+  // request. Frames are removed from |pending_replies_| when their reply with
+  // |final_update| set to true is received.
+  std::set<FrameKey> pending_replies_;

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

Consider making this a std::unordered_set.

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

Done.

+
+  // Indicates whether an update to the active match ordinal is expected. The
+  // value is the ID of the request for which the ordinal is pending, or
+  // kInvalidId otherwise.

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

This member is somewhat confusing to me. It is a request ID, but the name
suggests that its value would be either a match ordinal or a bool.

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

It was originally a bool, representing whether the FindRequestManager was still
waiting for the active match ordinal to be updated. Later on, it became
necessary to specifically keep track of which request still needed a reply with
an active match. This was before |current_request_.id| existed. I believe now
|pending_active_match_ordinal_| will always either be the same as it or
kInvalidId, so I can make it a bool again now.

+  int pending_active_match_ordinal_;

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

Under what circumstances can pending_active_match_ordinal_ ever be a different
value from current_request_.id?

If current_request_.id can advance past pending_active_match_ordinal_, why is it
important that we preserve the older pending_active_match_ordinal_ request id?

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

It won't be different anymore. I'll change this back to a bool.

+
+  // The number of matches found in each frame, stored by a (process ID, frame
+  // ID) pair that uniquely identifies each frame. There will necessarily be
+  // entries in this map for every frame that is being (or has been) searched in
+  // the current find session, and no other frames.
+  std::map<FrameKey, int> matches_per_frame_;

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

I see four different data structures keyed by FrameKey.

Would it be worth merging these into a single std::map<FrameKey, FrameState>,
where FrameState is a struct or class like:

  bool is_pending_reply_;
  bool is_pending_match_rects_reply_;
  int match_count_;
  RectData match_rects_data_;

?  My preference is for whatever is most readable.

If you do merge them, your usage pattern for all these data structures looks
like a better fit for unordered_map, since you never iterate over the
collection.

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

I think I like these better separately, because some of the pending replies sets
and other maps are associated with the separate android-specific operations (and
currently in structs related to those), and also because I think the way the
pending replies are used is cleaner to have them separate (like clearing, or
checking if they are empty).

I will change the maps into unordered_maps.

+
+  // The total number of matches found in the current find-in-page session. This
+  // should always be equal to the sum of all the entries in
+  // |matches_per_frame_|.
   int number_of_matches_;
 
+  // The active match ordinal relative to the matches found in its own frame.
+  std::pair<FrameKey, int> relative_active_match_ordinal_;

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

For the same reasons as the other pair, this would be better as two members.

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

Done.

+
   // The overall active match ordinal for the current find-in-page session.
   int active_match_ordinal_;
 
   // The rectangle around the active match, in screen coordinates.
   gfx::Rect selection_rect_;
+
+  // Find requests are queued here when previous requests need to be handled
+  // before these ones can be properly routed.
+  std::queue<FindRequest> find_request_queue_;
 };
 
 }  // namespace content
 
 #endif  // CONTENT_BROWSER_FIND_REQUEST_MANAGER_H_