content/browser/frame_host/navigation_entry_impl.cc

   1 // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "content/browser/frame_host/navigation_entry_impl.h"
   6
   7 #include <queue>
   8
   9 #include "base/metrics/histogram.h"
  10 #include "base/strings/string_util.h"
  11 #include "base/strings/utf_string_conversions.h"
  12 #include "content/common/navigation_params.h"
  13 #include "content/public/common/content_constants.h"
  14 #include "content/public/common/url_constants.h"
  15 #include "net/base/net_util.h"
  16 #include "ui/gfx/text_elider.h"
  17
  18 // Use this to get a new unique ID for a NavigationEntry during construction.
  19 // The returned ID is guaranteed to be nonzero (which is the "no ID" indicator).
  20 static int GetUniqueIDInConstructor() {
  21   static int unique_id_counter = 0;
  22   return ++unique_id_counter;
  23 }
  24
  25 namespace content {
  26
  27 int NavigationEntryImpl::kInvalidBindings = -1;
  28
  29 NavigationEntryImpl::TreeNode::TreeNode(FrameNavigationEntry* frame_entry)
  30     : frame_entry(frame_entry) {
  31 }
  32
  33 NavigationEntryImpl::TreeNode::~TreeNode() {
  34 }
  35
  36 bool NavigationEntryImpl::TreeNode::MatchesFrame(
  37     FrameTreeNode* frame_tree_node) const {
  38   if (frame_tree_node->frame_tree_node_id() ==
  39       frame_entry->frame_tree_node_id())
  40     return true;
  41
  42   // For now, we set the root FNE's FrameTreeNode ID to -1.
  43   return frame_tree_node->IsMainFrame() &&
  44          frame_entry->frame_tree_node_id() == -1;
  45 }
  46
  47 scoped_ptr<NavigationEntryImpl::TreeNode>
  48 NavigationEntryImpl::TreeNode::CloneAndReplace(
  49     FrameTreeNode* frame_tree_node,
  50     FrameNavigationEntry* frame_navigation_entry) const {
  51   if (frame_tree_node && MatchesFrame(frame_tree_node)) {
  52     // Replace this node in the cloned tree and prune its children.
  53     return make_scoped_ptr(
  54         new NavigationEntryImpl::TreeNode(frame_navigation_entry));
  55   }
  56
  57   // Clone the tree using a copy of the FrameNavigationEntry, without sharing.
  58   // TODO(creis): Share FNEs unless it's for another tab.
  59   scoped_ptr<NavigationEntryImpl::TreeNode> copy(
  60       new NavigationEntryImpl::TreeNode(frame_entry->Clone()));
  61
  62   // Recursively clone the children.
  63   for (auto& child : children) {
  64     copy->children.push_back(
  65         child->CloneAndReplace(frame_tree_node, frame_navigation_entry));
  66   }
  67
  68   return copy.Pass();
  69 }
  70
  71 scoped_ptr<NavigationEntry> NavigationEntry::Create() {
  72   return make_scoped_ptr(new NavigationEntryImpl()).Pass();
  73 }
  74
  75 NavigationEntryImpl* NavigationEntryImpl::FromNavigationEntry(
  76     NavigationEntry* entry) {
  77   return static_cast<NavigationEntryImpl*>(entry);
  78 }
  79
  80 const NavigationEntryImpl* NavigationEntryImpl::FromNavigationEntry(
  81     const NavigationEntry* entry) {
  82   return static_cast<const NavigationEntryImpl*>(entry);
  83 }
  84
  85 scoped_ptr<NavigationEntryImpl> NavigationEntryImpl::FromNavigationEntry(
  86     scoped_ptr<NavigationEntry> entry) {
  87   return make_scoped_ptr(FromNavigationEntry(entry.release()));
  88 }
  89
  90 NavigationEntryImpl::NavigationEntryImpl()
  91     : NavigationEntryImpl(nullptr, -1, GURL(), Referrer(), base::string16(),
  92                           ui::PAGE_TRANSITION_LINK, false) {
  93 }
  94
  95 NavigationEntryImpl::NavigationEntryImpl(SiteInstanceImpl* instance,
  96                                          int page_id,
  97                                          const GURL& url,
  98                                          const Referrer& referrer,
  99                                          const base::string16& title,
 100                                          ui::PageTransition transition_type,
 101                                          bool is_renderer_initiated)
 102     : frame_tree_(new TreeNode(
 103           new FrameNavigationEntry(-1, -1, -1, instance, url, referrer))),
 104       unique_id_(GetUniqueIDInConstructor()),
 105       bindings_(kInvalidBindings),
 106       page_type_(PAGE_TYPE_NORMAL),
 107       update_virtual_url_with_url_(false),
 108       title_(title),
 109       page_id_(page_id),
 110       transition_type_(transition_type),
 111       has_post_data_(false),
 112       post_id_(-1),
 113       restore_type_(RESTORE_NONE),
 114       is_overriding_user_agent_(false),
 115       http_status_code_(0),
 116       is_renderer_initiated_(is_renderer_initiated),
 117       should_replace_entry_(false),
 118       should_clear_history_list_(false),
 119       can_load_local_resources_(false),
 120       frame_tree_node_id_(-1) {
 121 }
 122
 123 NavigationEntryImpl::~NavigationEntryImpl() {
 124 }
 125
 126 int NavigationEntryImpl::GetUniqueID() const {
 127   return unique_id_;
 128 }
 129
 130 PageType NavigationEntryImpl::GetPageType() const {
 131   return page_type_;
 132 }
 133
 134 void NavigationEntryImpl::SetURL(const GURL& url) {
 135   frame_tree_->frame_entry->set_url(url);
 136   cached_display_title_.clear();
 137 }
 138
 139 const GURL& NavigationEntryImpl::GetURL() const {
 140   return frame_tree_->frame_entry->url();
 141 }
 142
 143 void NavigationEntryImpl::SetBaseURLForDataURL(const GURL& url) {
 144   base_url_for_data_url_ = url;
 145 }
 146
 147 const GURL& NavigationEntryImpl::GetBaseURLForDataURL() const {
 148   return base_url_for_data_url_;
 149 }
 150
 151 void NavigationEntryImpl::SetReferrer(const Referrer& referrer) {
 152   frame_tree_->frame_entry->set_referrer(referrer);
 153 }
 154
 155 const Referrer& NavigationEntryImpl::GetReferrer() const {
 156   return frame_tree_->frame_entry->referrer();
 157 }
 158
 159 void NavigationEntryImpl::SetVirtualURL(const GURL& url) {
 160   virtual_url_ = (url == GetURL()) ? GURL() : url;
 161   cached_display_title_.clear();
 162 }
 163
 164 const GURL& NavigationEntryImpl::GetVirtualURL() const {
 165   return virtual_url_.is_empty() ? GetURL() : virtual_url_;
 166 }
 167
 168 void NavigationEntryImpl::SetTitle(const base::string16& title) {
 169   title_ = title;
 170   cached_display_title_.clear();
 171 }
 172
 173 const base::string16& NavigationEntryImpl::GetTitle() const {
 174   return title_;
 175 }
 176
 177 void NavigationEntryImpl::SetPageState(const PageState& state) {
 178   frame_tree_->frame_entry->set_page_state(state);
 179 }
 180
 181 const PageState& NavigationEntryImpl::GetPageState() const {
 182   return frame_tree_->frame_entry->page_state();
 183 }
 184
 185 void NavigationEntryImpl::SetPageID(int page_id) {
 186   page_id_ = page_id;
 187 }
 188
 189 int32 NavigationEntryImpl::GetPageID() const {
 190   return page_id_;
 191 }
 192
 193 void NavigationEntryImpl::set_site_instance(SiteInstanceImpl* site_instance) {
 194   // TODO(creis): Update all callers and remove this method.
 195   frame_tree_->frame_entry->set_site_instance(site_instance);
 196 }
 197
 198 void NavigationEntryImpl::set_source_site_instance(
 199     SiteInstanceImpl* source_site_instance) {
 200   source_site_instance_ = source_site_instance;
 201 }
 202
 203 void NavigationEntryImpl::SetBindings(int bindings) {
 204   // Ensure this is set to a valid value, and that it stays the same once set.
 205   CHECK_NE(bindings, kInvalidBindings);
 206   CHECK(bindings_ == kInvalidBindings || bindings_ == bindings);
 207   bindings_ = bindings;
 208 }
 209
 210 const base::string16& NavigationEntryImpl::GetTitleForDisplay(
 211     const std::string& languages) const {
 212   // Most pages have real titles. Don't even bother caching anything if this is
 213   // the case.
 214   if (!title_.empty())
 215     return title_;
 216
 217   // More complicated cases will use the URLs as the title. This result we will
 218   // cache since it's more complicated to compute.
 219   if (!cached_display_title_.empty())
 220     return cached_display_title_;
 221
 222   // Use the virtual URL first if any, and fall back on using the real URL.
 223   base::string16 title;
 224   if (!virtual_url_.is_empty()) {
 225     title = net::FormatUrl(virtual_url_, languages);
 226   } else if (!GetURL().is_empty()) {
 227     title = net::FormatUrl(GetURL(), languages);
 228   }
 229
 230   // For file:// URLs use the filename as the title, not the full path.
 231   if (GetURL().SchemeIsFile()) {
 232     // It is necessary to ignore the reference and query parameters or else
 233     // looking for slashes might accidentally return one of those values. See
 234     // https://crbug.com/503003.
 235     base::string16::size_type refpos = title.find('#');
 236     base::string16::size_type querypos = title.find('?');
 237     base::string16::size_type lastpos;
 238     if (refpos == base::string16::npos)
 239       lastpos = querypos;
 240     else if (querypos == base::string16::npos)
 241       lastpos = refpos;
 242     else
 243       lastpos = (refpos < querypos) ? refpos : querypos;
 244     base::string16::size_type slashpos = title.rfind('/', lastpos);
 245     if (slashpos != base::string16::npos)
 246       title = title.substr(slashpos + 1);
 247   }
 248
 249   gfx::ElideString(title, kMaxTitleChars, &cached_display_title_);
 250   return cached_display_title_;
 251 }
 252
 253 bool NavigationEntryImpl::IsViewSourceMode() const {
 254   return virtual_url_.SchemeIs(kViewSourceScheme);
 255 }
 256
 257 void NavigationEntryImpl::SetTransitionType(
 258     ui::PageTransition transition_type) {
 259   transition_type_ = transition_type;
 260 }
 261
 262 ui::PageTransition NavigationEntryImpl::GetTransitionType() const {
 263   return transition_type_;
 264 }
 265
 266 const GURL& NavigationEntryImpl::GetUserTypedURL() const {
 267   return user_typed_url_;
 268 }
 269
 270 void NavigationEntryImpl::SetHasPostData(bool has_post_data) {
 271   has_post_data_ = has_post_data;
 272 }
 273
 274 bool NavigationEntryImpl::GetHasPostData() const {
 275   return has_post_data_;
 276 }
 277
 278 void NavigationEntryImpl::SetPostID(int64 post_id) {
 279   post_id_ = post_id;
 280 }
 281
 282 int64 NavigationEntryImpl::GetPostID() const {
 283   return post_id_;
 284 }
 285
 286 void NavigationEntryImpl::SetBrowserInitiatedPostData(
 287     const base::RefCountedMemory* data) {
 288   browser_initiated_post_data_ = data;
 289 }
 290
 291 const base::RefCountedMemory*
 292 NavigationEntryImpl::GetBrowserInitiatedPostData() const {
 293   return browser_initiated_post_data_.get();
 294 }
 295
 296
 297 const FaviconStatus& NavigationEntryImpl::GetFavicon() const {
 298   return favicon_;
 299 }
 300
 301 FaviconStatus& NavigationEntryImpl::GetFavicon() {
 302   return favicon_;
 303 }
 304
 305 const SSLStatus& NavigationEntryImpl::GetSSL() const {
 306   return ssl_;
 307 }
 308
 309 SSLStatus& NavigationEntryImpl::GetSSL() {
 310   return ssl_;
 311 }
 312
 313 void NavigationEntryImpl::SetOriginalRequestURL(const GURL& original_url) {
 314   original_request_url_ = original_url;
 315 }
 316
 317 const GURL& NavigationEntryImpl::GetOriginalRequestURL() const {
 318   return original_request_url_;
 319 }
 320
 321 void NavigationEntryImpl::SetIsOverridingUserAgent(bool override) {
 322   is_overriding_user_agent_ = override;
 323 }
 324
 325 bool NavigationEntryImpl::GetIsOverridingUserAgent() const {
 326   return is_overriding_user_agent_;
 327 }
 328
 329 void NavigationEntryImpl::SetTimestamp(base::Time timestamp) {
 330   timestamp_ = timestamp;
 331 }
 332
 333 base::Time NavigationEntryImpl::GetTimestamp() const {
 334   return timestamp_;
 335 }
 336
 337 void NavigationEntryImpl::SetHttpStatusCode(int http_status_code) {
 338   http_status_code_ = http_status_code;
 339 }
 340
 341 int NavigationEntryImpl::GetHttpStatusCode() const {
 342   return http_status_code_;
 343 }
 344
 345 void NavigationEntryImpl::SetRedirectChain(
 346     const std::vector<GURL>& redirect_chain) {
 347   redirect_chain_ = redirect_chain;
 348 }
 349
 350 const std::vector<GURL>& NavigationEntryImpl::GetRedirectChain() const {
 351   return redirect_chain_;
 352 }
 353
 354 bool NavigationEntryImpl::IsRestored() const {
 355   return restore_type_ != RESTORE_NONE;
 356 }
 357
 358 void NavigationEntryImpl::SetCanLoadLocalResources(bool allow) {
 359   can_load_local_resources_ = allow;
 360 }
 361
 362 bool NavigationEntryImpl::GetCanLoadLocalResources() const {
 363   return can_load_local_resources_;
 364 }
 365
 366 void NavigationEntryImpl::SetExtraData(const std::string& key,
 367                                        const base::string16& data) {
 368   extra_data_[key] = data;
 369 }
 370
 371 bool NavigationEntryImpl::GetExtraData(const std::string& key,
 372                                        base::string16* data) const {
 373   std::map<std::string, base::string16>::const_iterator iter =
 374       extra_data_.find(key);
 375   if (iter == extra_data_.end())
 376     return false;
 377   *data = iter->second;
 378   return true;
 379 }
 380
 381 void NavigationEntryImpl::ClearExtraData(const std::string& key) {
 382   extra_data_.erase(key);
 383 }
 384
 385 scoped_ptr<NavigationEntryImpl> NavigationEntryImpl::Clone() const {
 386   return NavigationEntryImpl::CloneAndReplace(nullptr, nullptr);
 387 }
 388
 389 scoped_ptr<NavigationEntryImpl> NavigationEntryImpl::CloneAndReplace(
 390     FrameTreeNode* frame_tree_node,
 391     FrameNavigationEntry* frame_navigation_entry) const {
 392   scoped_ptr<NavigationEntryImpl> copy =
 393       make_scoped_ptr(new NavigationEntryImpl());
 394
 395   // TODO(creis): Only share the same FrameNavigationEntries if cloning within
 396   // the same tab.
 397   copy->frame_tree_ =
 398       frame_tree_->CloneAndReplace(frame_tree_node, frame_navigation_entry);
 399
 400   // Copy most state over, unless cleared in ResetForCommit.
 401   // Don't copy unique_id_, otherwise it won't be unique.
 402   copy->bindings_ = bindings_;
 403   copy->page_type_ = page_type_;
 404   copy->virtual_url_ = virtual_url_;
 405   copy->update_virtual_url_with_url_ = update_virtual_url_with_url_;
 406   copy->title_ = title_;
 407   copy->favicon_ = favicon_;
 408   copy->page_id_ = page_id_;
 409   copy->ssl_ = ssl_;
 410   copy->transition_type_ = transition_type_;
 411   copy->user_typed_url_ = user_typed_url_;
 412   copy->has_post_data_ = has_post_data_;
 413   copy->post_id_ = post_id_;
 414   copy->restore_type_ = restore_type_;
 415   copy->original_request_url_ = original_request_url_;
 416   copy->is_overriding_user_agent_ = is_overriding_user_agent_;
 417   copy->timestamp_ = timestamp_;
 418   copy->http_status_code_ = http_status_code_;
 419   // ResetForCommit: browser_initiated_post_data_
 420   copy->screenshot_ = screenshot_;
 421   copy->extra_headers_ = extra_headers_;
 422   // ResetForCommit: source_site_instance_
 423   copy->base_url_for_data_url_ = base_url_for_data_url_;
 424   // ResetForCommit: is_renderer_initiated_
 425   copy->cached_display_title_ = cached_display_title_;
 426   // ResetForCommit: transferred_global_request_id_
 427   // ResetForCommit: should_replace_entry_
 428   copy->redirect_chain_ = redirect_chain_;
 429   // ResetForCommit: should_clear_history_list_
 430   // ResetForCommit: frame_tree_node_id_
 431   // ResetForCommit: intent_received_timestamp_
 432   copy->extra_data_ = extra_data_;
 433
 434   return copy.Pass();
 435 }
 436
 437 CommonNavigationParams NavigationEntryImpl::ConstructCommonNavigationParams(
 438     const GURL& dest_url,
 439     const Referrer& dest_referrer,
 440     const FrameNavigationEntry& frame_entry,
 441     FrameMsg_Navigate_Type::Value navigation_type) const {
 442   FrameMsg_UILoadMetricsReportType::Value report_type =
 443       FrameMsg_UILoadMetricsReportType::NO_REPORT;
 444   base::TimeTicks ui_timestamp = base::TimeTicks();
 445 #if defined(OS_ANDROID)
 446   if (!intent_received_timestamp().is_null())
 447     report_type = FrameMsg_UILoadMetricsReportType::REPORT_INTENT;
 448   ui_timestamp = intent_received_timestamp();
 449 #endif
 450
 451   return CommonNavigationParams(
 452       dest_url, dest_referrer, GetTransitionType(), navigation_type,
 453       !IsViewSourceMode(), should_replace_entry(), ui_timestamp, report_type,
 454       GetBaseURLForDataURL(), GetHistoryURLForDataURL());
 455 }
 456
 457 StartNavigationParams NavigationEntryImpl::ConstructStartNavigationParams()
 458     const {
 459   std::vector<unsigned char> browser_initiated_post_data;
 460   if (GetBrowserInitiatedPostData()) {
 461     browser_initiated_post_data.assign(
 462         GetBrowserInitiatedPostData()->front(),
 463         GetBrowserInitiatedPostData()->front() +
 464             GetBrowserInitiatedPostData()->size());
 465   }
 466
 467   return StartNavigationParams(GetHasPostData(), extra_headers(),
 468                                browser_initiated_post_data,
 469                                transferred_global_request_id().child_id,
 470                                transferred_global_request_id().request_id);
 471 }
 472
 473 RequestNavigationParams NavigationEntryImpl::ConstructRequestNavigationParams(
 474     const FrameNavigationEntry& frame_entry,
 475     base::TimeTicks navigation_start,
 476     bool is_same_document_history_load,
 477     bool has_committed_real_load,
 478     bool intended_as_new_entry,
 479     int pending_history_list_offset,
 480     int current_history_list_offset,
 481     int current_history_list_length) const {
 482   // Set the redirect chain to the navigation's redirects, unless returning to a
 483   // completed navigation (whose previous redirects don't apply).
 484   std::vector<GURL> redirects;
 485   if (ui::PageTransitionIsNewNavigation(GetTransitionType())) {
 486     redirects = GetRedirectChain();
 487   }
 488
 489   int pending_offset_to_send = pending_history_list_offset;
 490   int current_offset_to_send = current_history_list_offset;
 491   int current_length_to_send = current_history_list_length;
 492   if (should_clear_history_list()) {
 493     // Set the history list related parameters to the same values a
 494     // NavigationController would return before its first navigation. This will
 495     // fully clear the RenderView's view of the session history.
 496     pending_offset_to_send = -1;
 497     current_offset_to_send = -1;
 498     current_length_to_send = 0;
 499   }
 500   return RequestNavigationParams(
 501       GetIsOverridingUserAgent(), navigation_start, redirects,
 502       GetCanLoadLocalResources(), base::Time::Now(), frame_entry.page_state(),
 503       GetPageID(), GetUniqueID(), is_same_document_history_load,
 504       has_committed_real_load, intended_as_new_entry, pending_offset_to_send,
 505       current_offset_to_send, current_length_to_send,
 506       should_clear_history_list());
 507 }
 508
 509 void NavigationEntryImpl::ResetForCommit() {
 510   // Any state that only matters when a navigation entry is pending should be
 511   // cleared here.
 512   // TODO(creis): This state should be moved to NavigationRequest once
 513   // PlzNavigate is enabled.
 514   SetBrowserInitiatedPostData(nullptr);
 515   set_source_site_instance(nullptr);
 516   set_is_renderer_initiated(false);
 517   set_transferred_global_request_id(GlobalRequestID());
 518   set_should_replace_entry(false);
 519
 520   set_should_clear_history_list(false);
 521   set_frame_tree_node_id(-1);
 522
 523 #if defined(OS_ANDROID)
 524   // Reset the time stamp so that the metrics are not reported if this entry is
 525   // loaded again in the future.
 526   set_intent_received_timestamp(base::TimeTicks());
 527 #endif
 528 }
 529
 530 void NavigationEntryImpl::AddOrUpdateFrameEntry(FrameTreeNode* frame_tree_node,
 531                                                 int64 item_sequence_number,
 532                                                 int64 document_sequence_number,
 533                                                 SiteInstanceImpl* site_instance,
 534                                                 const GURL& url,
 535                                                 const Referrer& referrer,
 536                                                 const PageState& page_state) {
 537   // We should already have a TreeNode for the parent node by the time this node
 538   // commits.  Find it first.
 539   DCHECK(frame_tree_node->parent());
 540   NavigationEntryImpl::TreeNode* parent_node =
 541       FindFrameEntry(frame_tree_node->parent());
 542   if (!parent_node) {
 543     // The renderer should not send a commit for a subframe before its parent.
 544     // TODO(creis): Kill the renderer if we get here.
 545     NOTREACHED() << "Shouldn't see a commit for a subframe before parent.";
 546     return;
 547   }
 548
 549   // Now check whether we have a TreeNode for the node itself.
 550   int frame_tree_node_id = frame_tree_node->frame_tree_node_id();
 551   for (TreeNode* child : parent_node->children) {
 552     if (child->frame_entry->frame_tree_node_id() == frame_tree_node_id) {
 553       // Update the existing FrameNavigationEntry (e.g., for replaceState).
 554       child->frame_entry->UpdateEntry(item_sequence_number,
 555                                       document_sequence_number, site_instance,
 556                                       url, referrer, page_state);
 557       return;
 558     }
 559   }
 560
 561   // No entry exists yet, so create a new one.
 562   // Unordered list, since we expect to look up entries by frame sequence number
 563   // or unique name.
 564   FrameNavigationEntry* frame_entry = new FrameNavigationEntry(
 565       frame_tree_node_id, item_sequence_number, document_sequence_number,
 566       site_instance, url, referrer);
 567   frame_entry->set_page_state(page_state);
 568   parent_node->children.push_back(
 569       new NavigationEntryImpl::TreeNode(frame_entry));
 570 }
 571
 572 FrameNavigationEntry* NavigationEntryImpl::GetFrameEntry(
 573     FrameTreeNode* frame_tree_node) const {
 574   NavigationEntryImpl::TreeNode* tree_node = FindFrameEntry(frame_tree_node);
 575   return tree_node ? tree_node->frame_entry.get() : nullptr;
 576 }
 577
 578 void NavigationEntryImpl::SetScreenshotPNGData(
 579     scoped_refptr<base::RefCountedBytes> png_data) {
 580   screenshot_ = png_data;
 581   if (screenshot_.get())
 582     UMA_HISTOGRAM_MEMORY_KB("Overscroll.ScreenshotSize", screenshot_->size());
 583 }
 584
 585 GURL NavigationEntryImpl::GetHistoryURLForDataURL() const {
 586   return GetBaseURLForDataURL().is_empty() ? GURL() : GetVirtualURL();
 587 }
 588
 589 NavigationEntryImpl::TreeNode* NavigationEntryImpl::FindFrameEntry(
 590     FrameTreeNode* frame_tree_node) const {
 591   NavigationEntryImpl::TreeNode* node = nullptr;
 592   std::queue<NavigationEntryImpl::TreeNode*> work_queue;
 593   work_queue.push(root_node());
 594   while (!work_queue.empty()) {
 595     node = work_queue.front();
 596     work_queue.pop();
 597     if (node->MatchesFrame(frame_tree_node)) {
 598       // Only the root TreeNode should have a FTN ID of -1.
 599       DCHECK_IMPLIES(node->frame_entry->frame_tree_node_id() == -1,
 600                      node == root_node());
 601       return node;
 602     }
 603     // Enqueue any children and keep looking.
 604     for (auto& child : node->children)
 605       work_queue.push(child);
 606   }
 607   return nullptr;
 608 }
 609
 610 }  // namespace content