docshell/shistory/nsSHistory.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "nsSHistory.h"
   8
   9 #include <algorithm>
  10
  11 #include "nsContentUtils.h"
  12 #include "nsCOMArray.h"
  13 #include "nsComponentManagerUtils.h"
  14 #include "nsDocShell.h"
  15 #include "nsFrameLoaderOwner.h"
  16 #include "nsHashKeys.h"
  17 #include "nsIDocShell.h"
  18 #include "nsIDocumentViewer.h"
  19 #include "nsDocShellLoadState.h"
  20 #include "nsIDocShellTreeItem.h"
  21 #include "nsILayoutHistoryState.h"
  22 #include "nsIObserverService.h"
  23 #include "nsISHEntry.h"
  24 #include "nsISHistoryListener.h"
  25 #include "nsIURI.h"
  26 #include "nsIXULRuntime.h"
  27 #include "nsNetUtil.h"
  28 #include "nsTHashMap.h"
  29 #include "nsSHEntry.h"
  30 #include "SessionHistoryEntry.h"
  31 #include "nsTArray.h"
  32 #include "prsystem.h"
  33
  34 #include "mozilla/Attributes.h"
  35 #include "mozilla/dom/BrowsingContextGroup.h"
  36 #include "mozilla/dom/BrowserParent.h"
  37 #include "mozilla/dom/CanonicalBrowsingContext.h"
  38 #include "mozilla/dom/ContentParent.h"
  39 #include "mozilla/dom/Element.h"
  40 #include "mozilla/dom/RemoteWebProgressRequest.h"
  41 #include "mozilla/dom/WindowGlobalParent.h"
  42 #include "mozilla/LinkedList.h"
  43 #include "mozilla/MathAlgorithms.h"
  44 #include "mozilla/Preferences.h"
  45 #include "mozilla/ProcessPriorityManager.h"
  46 #include "mozilla/Services.h"
  47 #include "mozilla/StaticPrefs_fission.h"
  48 #include "mozilla/StaticPtr.h"
  49 #include "mozilla/dom/CanonicalBrowsingContext.h"
  50 #include "nsIWebNavigation.h"
  51 #include "nsDocShellLoadTypes.h"
  52 #include "base/process.h"
  53
  54 using namespace mozilla;
  55 using namespace mozilla::dom;
  56
  57 #define PREF_SHISTORY_SIZE "browser.sessionhistory.max_entries"
  58 #define PREF_SHISTORY_MAX_TOTAL_VIEWERS \
  59   "browser.sessionhistory.max_total_viewers"
  60 #define CONTENT_VIEWER_TIMEOUT_SECONDS \
  61   "browser.sessionhistory.contentViewerTimeout"
  62 // Observe fission.bfcacheInParent so that BFCache can be enabled/disabled when
  63 // the pref is changed.
  64 #define PREF_FISSION_BFCACHEINPARENT "fission.bfcacheInParent"
  65
  66 // Default this to time out unused content viewers after 30 minutes
  67 #define CONTENT_VIEWER_TIMEOUT_SECONDS_DEFAULT (30 * 60)
  68
  69 static constexpr const char* kObservedPrefs[] = {
  70     PREF_SHISTORY_SIZE, PREF_SHISTORY_MAX_TOTAL_VIEWERS,
  71     PREF_FISSION_BFCACHEINPARENT, nullptr};
  72
  73 static int32_t gHistoryMaxSize = 50;
  74
  75 // List of all SHistory objects, used for content viewer cache eviction.
  76 // When being destroyed, this helper removes everything from the list to avoid
  77 // assertions when we leak.
  78 struct ListHelper {
  79 #ifdef DEBUG
  80   ~ListHelper() { mList.clear(); }
  81 #endif  // DEBUG
  82
  83   LinkedList<nsSHistory> mList;
  84 };
  85
  86 MOZ_RUNINIT static ListHelper gSHistoryList;
  87 // Max viewers allowed total, across all SHistory objects - negative default
  88 // means we will calculate how many viewers to cache based on total memory
  89 int32_t nsSHistory::sHistoryMaxTotalViewers = -1;
  90
  91 // A counter that is used to be able to know the order in which
  92 // entries were touched, so that we can evict older entries first.
  93 static uint32_t gTouchCounter = 0;
  94
  95 extern mozilla::LazyLogModule gSHLog;
  96
  97 LazyLogModule gSHistoryLog("nsSHistory");
  98
  99 #define LOG(format) MOZ_LOG(gSHistoryLog, mozilla::LogLevel::Debug, format)
 100
 101 extern mozilla::LazyLogModule gPageCacheLog;
 102 extern mozilla::LazyLogModule gSHIPBFCacheLog;
 103
 104 // This macro makes it easier to print a log message which includes a URI's
 105 // spec.  Example use:
 106 //
 107 //  nsIURI *uri = [...];
 108 //  LOG_SPEC(("The URI is %s.", _spec), uri);
 109 //
 110 #define LOG_SPEC(format, uri)                        \
 111   PR_BEGIN_MACRO                                     \
 112   if (MOZ_LOG_TEST(gSHistoryLog, LogLevel::Debug)) { \
 113     nsAutoCString _specStr("(null)"_ns);             \
 114     if (uri) {                                       \
 115       _specStr = uri->GetSpecOrDefault();            \
 116     }                                                \
 117     const char* _spec = _specStr.get();              \
 118     LOG(format);                                     \
 119   }                                                  \
 120   PR_END_MACRO
 121
 122 // This macro makes it easy to log a message including an SHEntry's URI.
 123 // For example:
 124 //
 125 //  nsCOMPtr<nsISHEntry> shentry = [...];
 126 //  LOG_SHENTRY_SPEC(("shentry %p has uri %s.", shentry.get(), _spec), shentry);
 127 //
 128 #define LOG_SHENTRY_SPEC(format, shentry)            \
 129   PR_BEGIN_MACRO                                     \
 130   if (MOZ_LOG_TEST(gSHistoryLog, LogLevel::Debug)) { \
 131     nsCOMPtr<nsIURI> uri = shentry->GetURI();        \
 132     LOG_SPEC(format, uri);                           \
 133   }                                                  \
 134   PR_END_MACRO
 135
 136 // Calls a F on all registered session history listeners.
 137 template <typename F>
 138 static void NotifyListeners(nsAutoTObserverArray<nsWeakPtr, 2>& aListeners,
 139                             F&& f) {
 140   for (const nsWeakPtr& weakPtr : aListeners.EndLimitedRange()) {
 141     nsCOMPtr<nsISHistoryListener> listener = do_QueryReferent(weakPtr);
 142     if (listener) {
 143       f(listener);
 144     }
 145   }
 146 }
 147
 148 class MOZ_STACK_CLASS SHistoryChangeNotifier {
 149  public:
 150   explicit SHistoryChangeNotifier(nsSHistory* aHistory) {
 151     // If we're already in an update, the outermost change notifier will
 152     // update browsing context in the destructor.
 153     if (!aHistory->HasOngoingUpdate()) {
 154       aHistory->SetHasOngoingUpdate(true);
 155       mSHistory = aHistory;
 156     }
 157   }
 158
 159   ~SHistoryChangeNotifier() {
 160     if (mSHistory) {
 161       MOZ_ASSERT(mSHistory->HasOngoingUpdate());
 162       mSHistory->SetHasOngoingUpdate(false);
 163
 164       RefPtr<BrowsingContext> rootBC = mSHistory->GetBrowsingContext();
 165       if (mozilla::SessionHistoryInParent() && rootBC) {
 166         rootBC->Canonical()->HistoryCommitIndexAndLength();
 167       }
 168     }
 169   }
 170
 171   RefPtr<nsSHistory> mSHistory;
 172 };
 173
 174 enum HistCmd { HIST_CMD_GOTOINDEX, HIST_CMD_RELOAD };
 175
 176 class nsSHistoryObserver final : public nsIObserver {
 177  public:
 178   NS_DECL_ISUPPORTS
 179   NS_DECL_NSIOBSERVER
 180
 181   nsSHistoryObserver() {}
 182
 183   static void PrefChanged(const char* aPref, void* aSelf);
 184   void PrefChanged(const char* aPref);
 185
 186  protected:
 187   ~nsSHistoryObserver() {}
 188 };
 189
 190 StaticRefPtr<nsSHistoryObserver> gObserver;
 191
 192 NS_IMPL_ISUPPORTS(nsSHistoryObserver, nsIObserver)
 193
 194 // static
 195 void nsSHistoryObserver::PrefChanged(const char* aPref, void* aSelf) {
 196   static_cast<nsSHistoryObserver*>(aSelf)->PrefChanged(aPref);
 197 }
 198
 199 void nsSHistoryObserver::PrefChanged(const char* aPref) {
 200   nsSHistory::UpdatePrefs();
 201   nsSHistory::GloballyEvictDocumentViewers();
 202 }
 203
 204 NS_IMETHODIMP
 205 nsSHistoryObserver::Observe(nsISupports* aSubject, const char* aTopic,
 206                             const char16_t* aData) {
 207   if (!strcmp(aTopic, "cacheservice:empty-cache") ||
 208       !strcmp(aTopic, "memory-pressure")) {
 209     nsSHistory::GloballyEvictAllDocumentViewers();
 210   }
 211
 212   return NS_OK;
 213 }
 214
 215 void nsSHistory::EvictDocumentViewerForEntry(nsISHEntry* aEntry) {
 216   nsCOMPtr<nsIDocumentViewer> viewer = aEntry->GetDocumentViewer();
 217   if (viewer) {
 218     LOG_SHENTRY_SPEC(("Evicting content viewer 0x%p for "
 219                       "owning SHEntry 0x%p at %s.",
 220                       viewer.get(), aEntry, _spec),
 221                      aEntry);
 222
 223     // Drop the presentation state before destroying the viewer, so that
 224     // document teardown is able to correctly persist the state.
 225     NotifyListenersDocumentViewerEvicted(1);
 226     aEntry->SetDocumentViewer(nullptr);
 227     aEntry->SyncPresentationState();
 228     viewer->Destroy();
 229   } else if (nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(aEntry)) {
 230     if (RefPtr<nsFrameLoader> frameLoader = she->GetFrameLoader()) {
 231       nsCOMPtr<nsFrameLoaderOwner> owner =
 232           do_QueryInterface(frameLoader->GetOwnerContent());
 233       RefPtr<nsFrameLoader> currentFrameLoader;
 234       if (owner) {
 235         currentFrameLoader = owner->GetFrameLoader();
 236       }
 237
 238       // Only destroy non-current frameloader when evicting from the bfcache.
 239       if (currentFrameLoader != frameLoader) {
 240         MOZ_LOG(gSHIPBFCacheLog, LogLevel::Debug,
 241                 ("nsSHistory::EvictDocumentViewerForEntry "
 242                  "destroying an nsFrameLoader."));
 243         NotifyListenersDocumentViewerEvicted(1);
 244         she->SetFrameLoader(nullptr);
 245         frameLoader->Destroy();
 246       }
 247     }
 248   }
 249
 250   // When dropping bfcache, we have to remove associated dynamic entries as
 251   // well.
 252   int32_t index = GetIndexOfEntry(aEntry);
 253   if (index != -1) {
 254     RemoveDynEntries(index, aEntry);
 255   }
 256 }
 257
 258 nsSHistory::nsSHistory(BrowsingContext* aRootBC)
 259     : mRootBC(aRootBC->Id()),
 260       mHasOngoingUpdate(false),
 261       mIndex(-1),
 262       mRequestedIndex(-1),
 263       mRootDocShellID(aRootBC->GetHistoryID()) {
 264   static bool sCalledStartup = false;
 265   if (!sCalledStartup) {
 266     Startup();
 267     sCalledStartup = true;
 268   }
 269
 270   // Add this new SHistory object to the list
 271   gSHistoryList.mList.insertBack(this);
 272
 273   // Init mHistoryTracker on setting mRootBC so we can bind its event
 274   // target to the tabGroup.
 275   mHistoryTracker = mozilla::MakeUnique<HistoryTracker>(
 276       this,
 277       mozilla::Preferences::GetUint(CONTENT_VIEWER_TIMEOUT_SECONDS,
 278                                     CONTENT_VIEWER_TIMEOUT_SECONDS_DEFAULT),
 279       GetCurrentSerialEventTarget());
 280 }
 281
 282 nsSHistory::~nsSHistory() {
 283   // Clear mEntries explicitly here so that the destructor of the entries
 284   // can still access nsSHistory in a reasonable way.
 285   mEntries.Clear();
 286 }
 287
 288 NS_IMPL_ADDREF(nsSHistory)
 289 NS_IMPL_RELEASE(nsSHistory)
 290
 291 NS_INTERFACE_MAP_BEGIN(nsSHistory)
 292   NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsISHistory)
 293   NS_INTERFACE_MAP_ENTRY(nsISHistory)
 294   NS_INTERFACE_MAP_ENTRY(nsISupportsWeakReference)
 295 NS_INTERFACE_MAP_END
 296
 297 // static
 298 uint32_t nsSHistory::CalcMaxTotalViewers() {
 299 // This value allows tweaking how fast the allowed amount of content viewers
 300 // grows with increasing amounts of memory. Larger values mean slower growth.
 301 #ifdef ANDROID
 302 #  define MAX_TOTAL_VIEWERS_BIAS 15.9
 303 #else
 304 #  define MAX_TOTAL_VIEWERS_BIAS 14
 305 #endif
 306
 307   // Calculate an estimate of how many DocumentViewers we should cache based
 308   // on RAM.  This assumes that the average DocumentViewer is 4MB (conservative)
 309   // and caps the max at 8 DocumentViewers
 310   //
 311   // TODO: Should we split the cache memory betw. DocumentViewer caching and
 312   // nsCacheService?
 313   //
 314   // RAM    | DocumentViewers | on Android
 315   // -------------------------------------
 316   // 32   Mb       0                0
 317   // 64   Mb       1                0
 318   // 128  Mb       2                0
 319   // 256  Mb       3                1
 320   // 512  Mb       5                2
 321   // 768  Mb       6                2
 322   // 1024 Mb       8                3
 323   // 2048 Mb       8                5
 324   // 3072 Mb       8                7
 325   // 4096 Mb       8                8
 326   uint64_t bytes = PR_GetPhysicalMemorySize();
 327
 328   if (bytes == 0) {
 329     return 0;
 330   }
 331
 332   // Conversion from unsigned int64_t to double doesn't work on all platforms.
 333   // We need to truncate the value at INT64_MAX to make sure we don't
 334   // overflow.
 335   if (bytes > INT64_MAX) {
 336     bytes = INT64_MAX;
 337   }
 338
 339   double kBytesD = (double)(bytes >> 10);
 340
 341   // This is essentially the same calculation as for nsCacheService,
 342   // except that we divide the final memory calculation by 4, since
 343   // we assume each DocumentViewer takes on average 4MB
 344   uint32_t viewers = 0;
 345   double x = std::log(kBytesD) / std::log(2.0) - MAX_TOTAL_VIEWERS_BIAS;
 346   if (x > 0) {
 347     viewers = (uint32_t)(x * x - x + 2.001);  // add .001 for rounding
 348     viewers /= 4;
 349   }
 350
 351   // Cap it off at 8 max
 352   if (viewers > 8) {
 353     viewers = 8;
 354   }
 355   return viewers;
 356 }
 357
 358 // static
 359 void nsSHistory::UpdatePrefs() {
 360   Preferences::GetInt(PREF_SHISTORY_SIZE, &gHistoryMaxSize);
 361   if (mozilla::SessionHistoryInParent() && !mozilla::BFCacheInParent()) {
 362     sHistoryMaxTotalViewers = 0;
 363     return;
 364   }
 365
 366   Preferences::GetInt(PREF_SHISTORY_MAX_TOTAL_VIEWERS,
 367                       &sHistoryMaxTotalViewers);
 368   // If the pref is negative, that means we calculate how many viewers
 369   // we think we should cache, based on total memory
 370   if (sHistoryMaxTotalViewers < 0) {
 371     sHistoryMaxTotalViewers = CalcMaxTotalViewers();
 372   }
 373 }
 374
 375 // static
 376 nsresult nsSHistory::Startup() {
 377   UpdatePrefs();
 378
 379   // The goal of this is to unbreak users who have inadvertently set their
 380   // session history size to less than the default value.
 381   int32_t defaultHistoryMaxSize =
 382       Preferences::GetInt(PREF_SHISTORY_SIZE, 50, PrefValueKind::Default);
 383   if (gHistoryMaxSize < defaultHistoryMaxSize) {
 384     gHistoryMaxSize = defaultHistoryMaxSize;
 385   }
 386
 387   // Allow the user to override the max total number of cached viewers,
 388   // but keep the per SHistory cached viewer limit constant
 389   if (!gObserver) {
 390     gObserver = new nsSHistoryObserver();
 391     Preferences::RegisterCallbacks(nsSHistoryObserver::PrefChanged,
 392                                    kObservedPrefs, gObserver.get());
 393
 394     nsCOMPtr<nsIObserverService> obsSvc =
 395         mozilla::services::GetObserverService();
 396     if (obsSvc) {
 397       // Observe empty-cache notifications so tahat clearing the disk/memory
 398       // cache will also evict all content viewers.
 399       obsSvc->AddObserver(gObserver, "cacheservice:empty-cache", false);
 400
 401       // Same for memory-pressure notifications
 402       obsSvc->AddObserver(gObserver, "memory-pressure", false);
 403     }
 404   }
 405
 406   return NS_OK;
 407 }
 408
 409 // static
 410 void nsSHistory::Shutdown() {
 411   if (gObserver) {
 412     Preferences::UnregisterCallbacks(nsSHistoryObserver::PrefChanged,
 413                                      kObservedPrefs, gObserver.get());
 414
 415     nsCOMPtr<nsIObserverService> obsSvc =
 416         mozilla::services::GetObserverService();
 417     if (obsSvc) {
 418       obsSvc->RemoveObserver(gObserver, "cacheservice:empty-cache");
 419       obsSvc->RemoveObserver(gObserver, "memory-pressure");
 420     }
 421     gObserver = nullptr;
 422   }
 423 }
 424
 425 // static
 426 already_AddRefed<nsISHEntry> nsSHistory::GetRootSHEntry(nsISHEntry* aEntry) {
 427   nsCOMPtr<nsISHEntry> rootEntry = aEntry;
 428   nsCOMPtr<nsISHEntry> result = nullptr;
 429   while (rootEntry) {
 430     result = rootEntry;
 431     rootEntry = result->GetParent();
 432   }
 433
 434   return result.forget();
 435 }
 436
 437 // static
 438 nsresult nsSHistory::WalkHistoryEntries(nsISHEntry* aRootEntry,
 439                                         BrowsingContext* aBC,
 440                                         WalkHistoryEntriesFunc aCallback,
 441                                         void* aData) {
 442   NS_ENSURE_TRUE(aRootEntry, NS_ERROR_FAILURE);
 443
 444   int32_t childCount = aRootEntry->GetChildCount();
 445   for (int32_t i = 0; i < childCount; i++) {
 446     nsCOMPtr<nsISHEntry> childEntry;
 447     aRootEntry->GetChildAt(i, getter_AddRefs(childEntry));
 448     if (!childEntry) {
 449       // childEntry can be null for valid reasons, for example if the
 450       // docshell at index i never loaded anything useful.
 451       // Remember to clone also nulls in the child array (bug 464064).
 452       aCallback(nullptr, nullptr, i, aData);
 453       continue;
 454     }
 455
 456     BrowsingContext* childBC = nullptr;
 457     if (aBC) {
 458       for (BrowsingContext* child : aBC->Children()) {
 459         // If the SH pref is on and we are in the parent process, update
 460         // canonical BC directly
 461         bool foundChild = false;
 462         if (mozilla::SessionHistoryInParent() && XRE_IsParentProcess()) {
 463           if (child->Canonical()->HasHistoryEntry(childEntry)) {
 464             childBC = child;
 465             foundChild = true;
 466           }
 467         }
 468
 469         nsDocShell* docshell = static_cast<nsDocShell*>(child->GetDocShell());
 470         if (docshell && docshell->HasHistoryEntry(childEntry)) {
 471           childBC = docshell->GetBrowsingContext();
 472           foundChild = true;
 473         }
 474
 475         // XXX Simplify this once the old and new session history
 476         // implementations don't run at the same time.
 477         if (foundChild) {
 478           break;
 479         }
 480       }
 481     }
 482
 483     nsresult rv = aCallback(childEntry, childBC, i, aData);
 484     NS_ENSURE_SUCCESS(rv, rv);
 485   }
 486
 487   return NS_OK;
 488 }
 489
 490 // callback data for WalkHistoryEntries
 491 struct MOZ_STACK_CLASS CloneAndReplaceData {
 492   CloneAndReplaceData(uint32_t aCloneID, nsISHEntry* aReplaceEntry,
 493                       bool aCloneChildren, nsISHEntry* aDestTreeParent)
 494       : cloneID(aCloneID),
 495         cloneChildren(aCloneChildren),
 496         replaceEntry(aReplaceEntry),
 497         destTreeParent(aDestTreeParent) {}
 498
 499   uint32_t cloneID;
 500   bool cloneChildren;
 501   nsISHEntry* replaceEntry;
 502   nsISHEntry* destTreeParent;
 503   nsCOMPtr<nsISHEntry> resultEntry;
 504 };
 505
 506 nsresult nsSHistory::CloneAndReplaceChild(nsISHEntry* aEntry,
 507                                           BrowsingContext* aOwnerBC,
 508                                           int32_t aChildIndex, void* aData) {
 509   nsCOMPtr<nsISHEntry> dest;
 510
 511   CloneAndReplaceData* data = static_cast<CloneAndReplaceData*>(aData);
 512   uint32_t cloneID = data->cloneID;
 513   nsISHEntry* replaceEntry = data->replaceEntry;
 514
 515   if (!aEntry) {
 516     if (data->destTreeParent) {
 517       data->destTreeParent->AddChild(nullptr, aChildIndex);
 518     }
 519     return NS_OK;
 520   }
 521
 522   uint32_t srcID = aEntry->GetID();
 523
 524   nsresult rv = NS_OK;
 525   if (srcID == cloneID) {
 526     // Replace the entry
 527     dest = replaceEntry;
 528   } else {
 529     // Clone the SHEntry...
 530     rv = aEntry->Clone(getter_AddRefs(dest));
 531     NS_ENSURE_SUCCESS(rv, rv);
 532   }
 533   dest->SetIsSubFrame(true);
 534
 535   if (srcID != cloneID || data->cloneChildren) {
 536     // Walk the children
 537     CloneAndReplaceData childData(cloneID, replaceEntry, data->cloneChildren,
 538                                   dest);
 539     rv = nsSHistory::WalkHistoryEntries(aEntry, aOwnerBC, CloneAndReplaceChild,
 540                                         &childData);
 541     NS_ENSURE_SUCCESS(rv, rv);
 542   }
 543
 544   if (srcID != cloneID && aOwnerBC) {
 545     nsSHistory::HandleEntriesToSwapInDocShell(aOwnerBC, aEntry, dest);
 546   }
 547
 548   if (data->destTreeParent) {
 549     data->destTreeParent->AddChild(dest, aChildIndex);
 550   }
 551   data->resultEntry = dest;
 552   return rv;
 553 }
 554
 555 // static
 556 nsresult nsSHistory::CloneAndReplace(
 557     nsISHEntry* aSrcEntry, BrowsingContext* aOwnerBC, uint32_t aCloneID,
 558     nsISHEntry* aReplaceEntry, bool aCloneChildren, nsISHEntry** aDestEntry) {
 559   NS_ENSURE_ARG_POINTER(aDestEntry);
 560   NS_ENSURE_TRUE(aReplaceEntry, NS_ERROR_FAILURE);
 561   CloneAndReplaceData data(aCloneID, aReplaceEntry, aCloneChildren, nullptr);
 562   nsresult rv = CloneAndReplaceChild(aSrcEntry, aOwnerBC, 0, &data);
 563   data.resultEntry.swap(*aDestEntry);
 564   return rv;
 565 }
 566
 567 // static
 568 void nsSHistory::WalkContiguousEntries(
 569     nsISHEntry* aEntry, const std::function<void(nsISHEntry*)>& aCallback) {
 570   MOZ_ASSERT(aEntry);
 571
 572   nsCOMPtr<nsISHistory> shistory = aEntry->GetShistory();
 573   if (!shistory) {
 574     // If there is no session history in the entry, it means this is not a root
 575     // entry. So, we can return from here.
 576     return;
 577   }
 578
 579   int32_t index = shistory->GetIndexOfEntry(aEntry);
 580   int32_t count = shistory->GetCount();
 581
 582   nsCOMPtr<nsIURI> targetURI = aEntry->GetURI();
 583
 584   // First, call the callback on the input entry.
 585   aCallback(aEntry);
 586
 587   // Walk backward to find the entries that have the same origin as the
 588   // input entry.
 589   for (int32_t i = index - 1; i >= 0; i--) {
 590     RefPtr<nsISHEntry> entry;
 591     shistory->GetEntryAtIndex(i, getter_AddRefs(entry));
 592     if (entry) {
 593       nsCOMPtr<nsIURI> uri = entry->GetURI();
 594       if (NS_FAILED(nsContentUtils::GetSecurityManager()->CheckSameOriginURI(
 595               targetURI, uri, false, false))) {
 596         break;
 597       }
 598
 599       aCallback(entry);
 600     }
 601   }
 602
 603   // Then, Walk forward.
 604   for (int32_t i = index + 1; i < count; i++) {
 605     RefPtr<nsISHEntry> entry;
 606     shistory->GetEntryAtIndex(i, getter_AddRefs(entry));
 607     if (entry) {
 608       nsCOMPtr<nsIURI> uri = entry->GetURI();
 609       if (NS_FAILED(nsContentUtils::GetSecurityManager()->CheckSameOriginURI(
 610               targetURI, uri, false, false))) {
 611         break;
 612       }
 613
 614       aCallback(entry);
 615     }
 616   }
 617 }
 618
 619 NS_IMETHODIMP
 620 nsSHistory::AddChildSHEntryHelper(nsISHEntry* aCloneRef, nsISHEntry* aNewEntry,
 621                                   BrowsingContext* aRootBC,
 622                                   bool aCloneChildren) {
 623   MOZ_ASSERT(aRootBC->IsTop());
 624
 625   /* You are currently in the rootDocShell.
 626    * You will get here when a subframe has a new url
 627    * to load and you have walked up the tree all the
 628    * way to the top to clone the current SHEntry hierarchy
 629    * and replace the subframe where a new url was loaded with
 630    * a new entry.
 631    */
 632   nsCOMPtr<nsISHEntry> child;
 633   nsCOMPtr<nsISHEntry> currentHE;
 634   int32_t index = mIndex;
 635   if (index < 0) {
 636     return NS_ERROR_FAILURE;
 637   }
 638
 639   GetEntryAtIndex(index, getter_AddRefs(currentHE));
 640   NS_ENSURE_TRUE(currentHE, NS_ERROR_FAILURE);
 641
 642   nsresult rv = NS_OK;
 643   uint32_t cloneID = aCloneRef->GetID();
 644   rv = nsSHistory::CloneAndReplace(currentHE, aRootBC, cloneID, aNewEntry,
 645                                    aCloneChildren, getter_AddRefs(child));
 646
 647   if (NS_SUCCEEDED(rv)) {
 648     rv = AddEntry(child, true);
 649     if (NS_SUCCEEDED(rv)) {
 650       child->SetDocshellID(aRootBC->GetHistoryID());
 651     }
 652   }
 653
 654   return rv;
 655 }
 656
 657 nsresult nsSHistory::SetChildHistoryEntry(nsISHEntry* aEntry,
 658                                           BrowsingContext* aBC,
 659                                           int32_t aEntryIndex, void* aData) {
 660   SwapEntriesData* data = static_cast<SwapEntriesData*>(aData);
 661   if (!aBC || aBC == data->ignoreBC) {
 662     return NS_OK;
 663   }
 664
 665   nsISHEntry* destTreeRoot = data->destTreeRoot;
 666
 667   nsCOMPtr<nsISHEntry> destEntry;
 668
 669   if (data->destTreeParent) {
 670     // aEntry is a clone of some child of destTreeParent, but since the
 671     // trees aren't necessarily in sync, we'll have to locate it.
 672     // Note that we could set aShell's entry to null if we don't find a
 673     // corresponding entry under destTreeParent.
 674
 675     uint32_t targetID = aEntry->GetID();
 676
 677     // First look at the given index, since this is the common case.
 678     nsCOMPtr<nsISHEntry> entry;
 679     data->destTreeParent->GetChildAt(aEntryIndex, getter_AddRefs(entry));
 680     if (entry && entry->GetID() == targetID) {
 681       destEntry.swap(entry);
 682     } else {
 683       int32_t childCount;
 684       data->destTreeParent->GetChildCount(&childCount);
 685       for (int32_t i = 0; i < childCount; ++i) {
 686         data->destTreeParent->GetChildAt(i, getter_AddRefs(entry));
 687         if (!entry) {
 688           continue;
 689         }
 690
 691         if (entry->GetID() == targetID) {
 692           destEntry.swap(entry);
 693           break;
 694         }
 695       }
 696     }
 697   } else {
 698     destEntry = destTreeRoot;
 699   }
 700
 701   nsSHistory::HandleEntriesToSwapInDocShell(aBC, aEntry, destEntry);
 702   // Now handle the children of aEntry.
 703   SwapEntriesData childData = {data->ignoreBC, destTreeRoot, destEntry};
 704   return nsSHistory::WalkHistoryEntries(aEntry, aBC, SetChildHistoryEntry,
 705                                         &childData);
 706 }
 707
 708 // static
 709 void nsSHistory::HandleEntriesToSwapInDocShell(
 710     mozilla::dom::BrowsingContext* aBC, nsISHEntry* aOldEntry,
 711     nsISHEntry* aNewEntry) {
 712   bool shPref = mozilla::SessionHistoryInParent();
 713   if (aBC->IsInProcess() || !shPref) {
 714     nsDocShell* docshell = static_cast<nsDocShell*>(aBC->GetDocShell());
 715     if (docshell) {
 716       docshell->SwapHistoryEntries(aOldEntry, aNewEntry);
 717     }
 718   } else {
 719     // FIXME Bug 1633988: Need to update entries?
 720   }
 721
 722   // XXX Simplify this once the old and new session history implementations
 723   // don't run at the same time.
 724   if (shPref && XRE_IsParentProcess()) {
 725     aBC->Canonical()->SwapHistoryEntries(aOldEntry, aNewEntry);
 726   }
 727 }
 728
 729 void nsSHistory::UpdateRootBrowsingContextState(BrowsingContext* aRootBC) {
 730   if (aRootBC && aRootBC->EverAttached()) {
 731     bool sameDocument = IsEmptyOrHasEntriesForSingleTopLevelPage();
 732     if (sameDocument != aRootBC->GetIsSingleToplevelInHistory()) {
 733       // If the browsing context is discarded then its session history is
 734       // invalid and will go away.
 735       Unused << aRootBC->SetIsSingleToplevelInHistory(sameDocument);
 736     }
 737   }
 738 }
 739
 740 NS_IMETHODIMP
 741 nsSHistory::AddToRootSessionHistory(bool aCloneChildren, nsISHEntry* aOSHE,
 742                                     BrowsingContext* aRootBC,
 743                                     nsISHEntry* aEntry, uint32_t aLoadType,
 744                                     bool aShouldPersist,
 745                                     Maybe<int32_t>* aPreviousEntryIndex,
 746                                     Maybe<int32_t>* aLoadedEntryIndex) {
 747   MOZ_ASSERT(aRootBC->IsTop());
 748
 749   nsresult rv = NS_OK;
 750
 751   // If we need to clone our children onto the new session
 752   // history entry, do so now.
 753   if (aCloneChildren && aOSHE) {
 754     uint32_t cloneID = aOSHE->GetID();
 755     nsCOMPtr<nsISHEntry> newEntry;
 756     nsSHistory::CloneAndReplace(aOSHE, aRootBC, cloneID, aEntry, true,
 757                                 getter_AddRefs(newEntry));
 758     NS_ASSERTION(aEntry == newEntry,
 759                  "The new session history should be in the new entry");
 760   }
 761   // This is the root docshell
 762   bool addToSHistory = !LOAD_TYPE_HAS_FLAGS(
 763       aLoadType, nsIWebNavigation::LOAD_FLAGS_REPLACE_HISTORY);
 764   if (!addToSHistory) {
 765     // Replace current entry in session history; If the requested index is
 766     // valid, it indicates the loading was triggered by a history load, and
 767     // we should replace the entry at requested index instead.
 768     int32_t index = GetIndexForReplace();
 769
 770     // Replace the current entry with the new entry
 771     if (index >= 0) {
 772       rv = ReplaceEntry(index, aEntry);
 773     } else {
 774       // If we're trying to replace an inexistant shistory entry, append.
 775       addToSHistory = true;
 776     }
 777   }
 778   if (addToSHistory) {
 779     // Add to session history
 780     *aPreviousEntryIndex = Some(mIndex);
 781     rv = AddEntry(aEntry, aShouldPersist);
 782     *aLoadedEntryIndex = Some(mIndex);
 783     MOZ_LOG(gPageCacheLog, LogLevel::Verbose,
 784             ("Previous index: %d, Loaded index: %d",
 785              aPreviousEntryIndex->value(), aLoadedEntryIndex->value()));
 786   }
 787   if (NS_SUCCEEDED(rv)) {
 788     aEntry->SetDocshellID(aRootBC->GetHistoryID());
 789   }
 790   return rv;
 791 }
 792
 793 /* Add an entry to the History list at mIndex and
 794  * increment the index to point to the new entry
 795  */
 796 NS_IMETHODIMP
 797 nsSHistory::AddEntry(nsISHEntry* aSHEntry, bool aPersist) {
 798   NS_ENSURE_ARG(aSHEntry);
 799
 800   nsCOMPtr<nsISHistory> shistoryOfEntry = aSHEntry->GetShistory();
 801   if (shistoryOfEntry && shistoryOfEntry != this) {
 802     NS_WARNING(
 803         "The entry has been associated to another nsISHistory instance. "
 804         "Try nsISHEntry.clone() and nsISHEntry.abandonBFCacheEntry() "
 805         "first if you're copying an entry from another nsISHistory.");
 806     return NS_ERROR_FAILURE;
 807   }
 808
 809   aSHEntry->SetShistory(this);
 810
 811   // If we have a root docshell, update the docshell id of the root shentry to
 812   // match the id of that docshell
 813   RefPtr<BrowsingContext> rootBC = GetBrowsingContext();
 814   if (rootBC) {
 815     aSHEntry->SetDocshellID(mRootDocShellID);
 816   }
 817
 818   if (mIndex >= 0) {
 819     MOZ_ASSERT(mIndex < Length(), "Index out of range!");
 820     if (mIndex >= Length()) {
 821       return NS_ERROR_FAILURE;
 822     }
 823
 824     if (mEntries[mIndex] && !mEntries[mIndex]->GetPersist()) {
 825       NotifyListeners(mListeners, [](auto l) { l->OnHistoryReplaceEntry(); });
 826       aSHEntry->SetPersist(aPersist);
 827       mEntries[mIndex] = aSHEntry;
 828       UpdateRootBrowsingContextState();
 829       return NS_OK;
 830     }
 831   }
 832   SHistoryChangeNotifier change(this);
 833
 834   int32_t truncating = Length() - 1 - mIndex;
 835   if (truncating > 0) {
 836     NotifyListeners(mListeners,
 837                     [truncating](auto l) { l->OnHistoryTruncate(truncating); });
 838   }
 839
 840   nsCOMPtr<nsIURI> uri = aSHEntry->GetURI();
 841   NotifyListeners(mListeners,
 842                   [&uri, this](auto l) { l->OnHistoryNewEntry(uri, mIndex); });
 843
 844   // Remove all entries after the current one, add the new one, and set the
 845   // new one as the current one.
 846   MOZ_ASSERT(mIndex >= -1);
 847   aSHEntry->SetPersist(aPersist);
 848   mEntries.TruncateLength(mIndex + 1);
 849   mEntries.AppendElement(aSHEntry);
 850   mIndex++;
 851   if (mIndex > 0) {
 852     UpdateEntryLength(mEntries[mIndex - 1], mEntries[mIndex], false);
 853   }
 854
 855   // Purge History list if it is too long
 856   if (gHistoryMaxSize >= 0 && Length() > gHistoryMaxSize) {
 857     PurgeHistory(Length() - gHistoryMaxSize);
 858   }
 859
 860   UpdateRootBrowsingContextState();
 861
 862   return NS_OK;
 863 }
 864
 865 void nsSHistory::NotifyOnHistoryReplaceEntry() {
 866   NotifyListeners(mListeners, [](auto l) { l->OnHistoryReplaceEntry(); });
 867 }
 868
 869 /* Get size of the history list */
 870 NS_IMETHODIMP
 871 nsSHistory::GetCount(int32_t* aResult) {
 872   MOZ_ASSERT(aResult, "null out param?");
 873   *aResult = Length();
 874   return NS_OK;
 875 }
 876
 877 NS_IMETHODIMP
 878 nsSHistory::GetIndex(int32_t* aResult) {
 879   MOZ_ASSERT(aResult, "null out param?");
 880   *aResult = mIndex;
 881   return NS_OK;
 882 }
 883
 884 NS_IMETHODIMP
 885 nsSHistory::SetIndex(int32_t aIndex) {
 886   if (aIndex < 0 || aIndex >= Length()) {
 887     return NS_ERROR_FAILURE;
 888   }
 889
 890   mIndex = aIndex;
 891   return NS_OK;
 892 }
 893
 894 /* Get the requestedIndex */
 895 NS_IMETHODIMP
 896 nsSHistory::GetRequestedIndex(int32_t* aResult) {
 897   MOZ_ASSERT(aResult, "null out param?");
 898   *aResult = mRequestedIndex;
 899   return NS_OK;
 900 }
 901
 902 NS_IMETHODIMP_(void)
 903 nsSHistory::InternalSetRequestedIndex(int32_t aRequestedIndex) {
 904   MOZ_ASSERT(aRequestedIndex >= -1 && aRequestedIndex < Length());
 905   mRequestedIndex = aRequestedIndex;
 906 }
 907
 908 NS_IMETHODIMP
 909 nsSHistory::GetEntryAtIndex(int32_t aIndex, nsISHEntry** aResult) {
 910   NS_ENSURE_ARG_POINTER(aResult);
 911
 912   if (aIndex < 0 || aIndex >= Length()) {
 913     return NS_ERROR_FAILURE;
 914   }
 915
 916   *aResult = mEntries[aIndex];
 917   NS_ADDREF(*aResult);
 918   return NS_OK;
 919 }
 920
 921 NS_IMETHODIMP_(int32_t)
 922 nsSHistory::GetIndexOfEntry(nsISHEntry* aSHEntry) {
 923   for (int32_t i = 0; i < Length(); i++) {
 924     if (aSHEntry == mEntries[i]) {
 925       return i;
 926     }
 927   }
 928
 929   return -1;
 930 }
 931
 932 static void LogEntry(nsISHEntry* aEntry, int32_t aIndex, int32_t aTotal,
 933                      const nsCString& aPrefix, bool aIsCurrent) {
 934   if (!aEntry) {
 935     MOZ_LOG(gSHLog, LogLevel::Debug,
 936             (" %s+- %i SH Entry null\n", aPrefix.get(), aIndex));
 937     return;
 938   }
 939
 940   nsCOMPtr<nsIURI> uri = aEntry->GetURI();
 941   nsAutoString title, name;
 942   aEntry->GetTitle(title);
 943   aEntry->GetName(name);
 944
 945   SHEntrySharedParentState* shared;
 946   if (mozilla::SessionHistoryInParent()) {
 947     shared = static_cast<SessionHistoryEntry*>(aEntry)->SharedInfo();
 948   } else {
 949     shared = static_cast<nsSHEntry*>(aEntry)->GetState();
 950   }
 951
 952   nsID docShellId;
 953   aEntry->GetDocshellID(docShellId);
 954
 955   int32_t childCount = aEntry->GetChildCount();
 956
 957   MOZ_LOG(gSHLog, LogLevel::Debug,
 958           ("%s%s+- %i SH Entry %p %" PRIu64 " %s\n", aIsCurrent ? ">" : " ",
 959            aPrefix.get(), aIndex, aEntry, shared->GetId(),
 960            nsIDToCString(docShellId).get()));
 961
 962   nsCString prefix(aPrefix);
 963   if (aIndex < aTotal - 1) {
 964     prefix.AppendLiteral("|   ");
 965   } else {
 966     prefix.AppendLiteral("    ");
 967   }
 968
 969   MOZ_LOG(gSHLog, LogLevel::Debug,
 970           (" %s%s  URL = %s\n", prefix.get(), childCount > 0 ? "|" : " ",
 971            uri->GetSpecOrDefault().get()));
 972   MOZ_LOG(gSHLog, LogLevel::Debug,
 973           (" %s%s  Title = %s\n", prefix.get(), childCount > 0 ? "|" : " ",
 974            NS_LossyConvertUTF16toASCII(title).get()));
 975   MOZ_LOG(gSHLog, LogLevel::Debug,
 976           (" %s%s  Name = %s\n", prefix.get(), childCount > 0 ? "|" : " ",
 977            NS_LossyConvertUTF16toASCII(name).get()));
 978   MOZ_LOG(
 979       gSHLog, LogLevel::Debug,
 980       (" %s%s  Is in BFCache = %s\n", prefix.get(), childCount > 0 ? "|" : " ",
 981        aEntry->GetIsInBFCache() ? "true" : "false"));
 982   MOZ_LOG(gSHLog, LogLevel::Debug,
 983           (" %s%s  Has User Interaction = %s\n", prefix.get(),
 984            childCount > 0 ? "|" : " ",
 985            aEntry->GetHasUserInteraction() ? "true" : "false"));
 986
 987   nsCOMPtr<nsISHEntry> prevChild;
 988   for (int32_t i = 0; i < childCount; ++i) {
 989     nsCOMPtr<nsISHEntry> child;
 990     aEntry->GetChildAt(i, getter_AddRefs(child));
 991     LogEntry(child, i, childCount, prefix, false);
 992     child.swap(prevChild);
 993   }
 994 }
 995
 996 void nsSHistory::LogHistory() {
 997   if (!MOZ_LOG_TEST(gSHLog, LogLevel::Debug)) {
 998     return;
 999   }
1000
1001   MOZ_LOG(gSHLog, LogLevel::Debug, ("nsSHistory %p\n", this));
1002   int32_t length = Length();
1003   for (int32_t i = 0; i < length; i++) {
1004     LogEntry(mEntries[i], i, length, EmptyCString(), i == mIndex);
1005   }
1006 }
1007
1008 void nsSHistory::WindowIndices(int32_t aIndex, int32_t* aOutStartIndex,
1009                                int32_t* aOutEndIndex) {
1010   *aOutStartIndex = std::max(0, aIndex - nsSHistory::VIEWER_WINDOW);
1011   *aOutEndIndex = std::min(Length() - 1, aIndex + nsSHistory::VIEWER_WINDOW);
1012 }
1013
1014 static void MarkAsInitialEntry(
1015     SessionHistoryEntry* aEntry,
1016     nsTHashMap<nsIDHashKey, SessionHistoryEntry*>& aHashtable) {
1017   if (!aEntry->BCHistoryLength().Modified()) {
1018     ++(aEntry->BCHistoryLength());
1019   }
1020   aHashtable.InsertOrUpdate(aEntry->DocshellID(), aEntry);
1021   for (const RefPtr<SessionHistoryEntry>& entry : aEntry->Children()) {
1022     if (entry) {
1023       MarkAsInitialEntry(entry, aHashtable);
1024     }
1025   }
1026 }
1027
1028 static void ClearEntries(SessionHistoryEntry* aEntry) {
1029   aEntry->ClearBCHistoryLength();
1030   for (const RefPtr<SessionHistoryEntry>& entry : aEntry->Children()) {
1031     if (entry) {
1032       ClearEntries(entry);
1033     }
1034   }
1035 }
1036
1037 NS_IMETHODIMP
1038 nsSHistory::PurgeHistory(int32_t aNumEntries) {
1039   if (Length() <= 0 || aNumEntries <= 0) {
1040     return NS_ERROR_FAILURE;
1041   }
1042
1043   SHistoryChangeNotifier change(this);
1044
1045   aNumEntries = std::min(aNumEntries, Length());
1046
1047   NotifyListeners(mListeners,
1048                   [aNumEntries](auto l) { l->OnHistoryPurge(aNumEntries); });
1049
1050   // Set all the entries hanging of the first entry that we keep
1051   // (mEntries[aNumEntries]) as being created as the result of a load
1052   // (so contributing one to their BCHistoryLength).
1053   nsTHashMap<nsIDHashKey, SessionHistoryEntry*> docshellIDToEntry;
1054   if (aNumEntries != Length()) {
1055     nsCOMPtr<SessionHistoryEntry> she =
1056         do_QueryInterface(mEntries[aNumEntries]);
1057     if (she) {
1058       MarkAsInitialEntry(she, docshellIDToEntry);
1059     }
1060   }
1061
1062   // Reset the BCHistoryLength of all the entries that we're removing to a new
1063   // counter with value 0 while decreasing their contribution to a shared
1064   // BCHistoryLength. The end result is that they don't contribute to the
1065   // BCHistoryLength of any other entry anymore.
1066   for (int32_t i = 0; i < aNumEntries; ++i) {
1067     nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(mEntries[i]);
1068     if (she) {
1069       ClearEntries(she);
1070     }
1071   }
1072
1073   RefPtr<BrowsingContext> rootBC = GetBrowsingContext();
1074   if (rootBC) {
1075     rootBC->PreOrderWalk([&docshellIDToEntry](BrowsingContext* aBC) {
1076       SessionHistoryEntry* entry = docshellIDToEntry.Get(aBC->GetHistoryID());
1077       Unused << aBC->SetHistoryEntryCount(
1078           entry ? uint32_t(entry->BCHistoryLength()) : 0);
1079     });
1080   }
1081
1082   // Remove the first `aNumEntries` entries.
1083   mEntries.RemoveElementsAt(0, aNumEntries);
1084
1085   // Adjust the indices, but don't let them go below -1.
1086   mIndex -= aNumEntries;
1087   mIndex = std::max(mIndex, -1);
1088   mRequestedIndex -= aNumEntries;
1089   mRequestedIndex = std::max(mRequestedIndex, -1);
1090
1091   if (rootBC && rootBC->GetDocShell()) {
1092     rootBC->GetDocShell()->HistoryPurged(aNumEntries);
1093   }
1094
1095   UpdateRootBrowsingContextState(rootBC);
1096
1097   return NS_OK;
1098 }
1099
1100 NS_IMETHODIMP
1101 nsSHistory::AddSHistoryListener(nsISHistoryListener* aListener) {
1102   NS_ENSURE_ARG_POINTER(aListener);
1103
1104   // Check if the listener supports Weak Reference. This is a must.
1105   // This listener functionality is used by embedders and we want to
1106   // have the right ownership with who ever listens to SHistory
1107   nsWeakPtr listener = do_GetWeakReference(aListener);
1108   if (!listener) {
1109     return NS_ERROR_FAILURE;
1110   }
1111
1112   mListeners.AppendElementUnlessExists(listener);
1113   return NS_OK;
1114 }
1115
1116 void nsSHistory::NotifyListenersDocumentViewerEvicted(uint32_t aNumEvicted) {
1117   NotifyListeners(mListeners, [aNumEvicted](auto l) {
1118     l->OnDocumentViewerEvicted(aNumEvicted);
1119   });
1120 }
1121
1122 NS_IMETHODIMP
1123 nsSHistory::RemoveSHistoryListener(nsISHistoryListener* aListener) {
1124   // Make sure the listener that wants to be removed is the
1125   // one we have in store.
1126   nsWeakPtr listener = do_GetWeakReference(aListener);
1127   mListeners.RemoveElement(listener);
1128   return NS_OK;
1129 }
1130
1131 /* Replace an entry in the History list at a particular index.
1132  * Do not update index or count.
1133  */
1134 NS_IMETHODIMP
1135 nsSHistory::ReplaceEntry(int32_t aIndex, nsISHEntry* aReplaceEntry) {
1136   NS_ENSURE_ARG(aReplaceEntry);
1137
1138   if (aIndex < 0 || aIndex >= Length()) {
1139     return NS_ERROR_FAILURE;
1140   }
1141
1142   nsCOMPtr<nsISHistory> shistoryOfEntry = aReplaceEntry->GetShistory();
1143   if (shistoryOfEntry && shistoryOfEntry != this) {
1144     NS_WARNING(
1145         "The entry has been associated to another nsISHistory instance. "
1146         "Try nsISHEntry.clone() and nsISHEntry.abandonBFCacheEntry() "
1147         "first if you're copying an entry from another nsISHistory.");
1148     return NS_ERROR_FAILURE;
1149   }
1150
1151   aReplaceEntry->SetShistory(this);
1152
1153   NotifyListeners(mListeners, [](auto l) { l->OnHistoryReplaceEntry(); });
1154
1155   aReplaceEntry->SetPersist(true);
1156   mEntries[aIndex] = aReplaceEntry;
1157
1158   UpdateRootBrowsingContextState();
1159
1160   return NS_OK;
1161 }
1162
1163 // Calls OnHistoryReload on all registered session history listeners.
1164 // Listeners may return 'false' to cancel an action so make sure that we
1165 // set the return value to 'false' if one of the listeners wants to cancel.
1166 NS_IMETHODIMP
1167 nsSHistory::NotifyOnHistoryReload(bool* aCanReload) {
1168   *aCanReload = true;
1169
1170   for (const nsWeakPtr& weakPtr : mListeners.EndLimitedRange()) {
1171     nsCOMPtr<nsISHistoryListener> listener = do_QueryReferent(weakPtr);
1172     if (listener) {
1173       bool retval = true;
1174
1175       if (NS_SUCCEEDED(listener->OnHistoryReload(&retval)) && !retval) {
1176         *aCanReload = false;
1177       }
1178     }
1179   }
1180
1181   return NS_OK;
1182 }
1183
1184 NS_IMETHODIMP
1185 nsSHistory::EvictOutOfRangeDocumentViewers(int32_t aIndex) {
1186   MOZ_LOG(gSHIPBFCacheLog, LogLevel::Debug,
1187           ("nsSHistory::EvictOutOfRangeDocumentViewers %i", aIndex));
1188
1189   // Check our per SHistory object limit in the currently navigated SHistory
1190   EvictOutOfRangeWindowDocumentViewers(aIndex);
1191   // Check our total limit across all SHistory objects
1192   GloballyEvictDocumentViewers();
1193   return NS_OK;
1194 }
1195
1196 NS_IMETHODIMP_(void)
1197 nsSHistory::EvictDocumentViewersOrReplaceEntry(nsISHEntry* aNewSHEntry,
1198                                                bool aReplace) {
1199   if (!aReplace) {
1200     int32_t curIndex;
1201     GetIndex(&curIndex);
1202     if (curIndex > -1) {
1203       EvictOutOfRangeDocumentViewers(curIndex);
1204     }
1205   } else {
1206     nsCOMPtr<nsISHEntry> rootSHEntry = nsSHistory::GetRootSHEntry(aNewSHEntry);
1207
1208     int32_t index = GetIndexOfEntry(rootSHEntry);
1209     if (index > -1) {
1210       ReplaceEntry(index, rootSHEntry);
1211     }
1212   }
1213 }
1214
1215 NS_IMETHODIMP
1216 nsSHistory::EvictAllDocumentViewers() {
1217   // XXXbz we don't actually do a good job of evicting things as we should, so
1218   // we might have viewers quite far from mIndex.  So just evict everything.
1219   for (int32_t i = 0; i < Length(); i++) {
1220     EvictDocumentViewerForEntry(mEntries[i]);
1221   }
1222
1223   return NS_OK;
1224 }
1225
1226 MOZ_CAN_RUN_SCRIPT
1227 static void FinishRestore(CanonicalBrowsingContext* aBrowsingContext,
1228                           nsDocShellLoadState* aLoadState,
1229                           SessionHistoryEntry* aEntry,
1230                           nsFrameLoader* aFrameLoader, bool aCanSave) {
1231   MOZ_ASSERT(aEntry);
1232   MOZ_ASSERT(aFrameLoader);
1233
1234   aEntry->SetFrameLoader(nullptr);
1235
1236   nsCOMPtr<nsISHistory> shistory = aEntry->GetShistory();
1237   int32_t indexOfHistoryLoad =
1238       shistory ? shistory->GetIndexOfEntry(aEntry) : -1;
1239
1240   nsCOMPtr<nsFrameLoaderOwner> frameLoaderOwner =
1241       do_QueryInterface(aBrowsingContext->GetEmbedderElement());
1242   if (frameLoaderOwner && aFrameLoader->GetMaybePendingBrowsingContext() &&
1243       indexOfHistoryLoad >= 0) {
1244     RefPtr<BrowsingContextWebProgress> webProgress =
1245         aBrowsingContext->GetWebProgress();
1246     if (webProgress) {
1247       // Synthesize a STATE_START WebProgress state change event from here
1248       // in order to ensure emitting it on the BrowsingContext we navigate
1249       // *from* instead of the BrowsingContext we navigate *to*. This will fire
1250       // before and the next one will be ignored by BrowsingContextWebProgress:
1251       // https://searchfox.org/mozilla-central/rev/77f0b36028b2368e342c982ea47609040b399d89/docshell/base/BrowsingContextWebProgress.cpp#196-203
1252       nsCOMPtr<nsIURI> nextURI = aEntry->GetURI();
1253       nsCOMPtr<nsIURI> nextOriginalURI = aEntry->GetOriginalURI();
1254       nsCOMPtr<nsIRequest> request = MakeAndAddRef<RemoteWebProgressRequest>(
1255           nextURI, nextOriginalURI ? nextOriginalURI : nextURI,
1256           ""_ns /* aMatchedList */);
1257       webProgress->OnStateChange(webProgress, request,
1258                                  nsIWebProgressListener::STATE_START |
1259                                      nsIWebProgressListener::STATE_IS_DOCUMENT |
1260                                      nsIWebProgressListener::STATE_IS_REQUEST |
1261                                      nsIWebProgressListener::STATE_IS_WINDOW |
1262                                      nsIWebProgressListener::STATE_IS_NETWORK,
1263                                  NS_OK);
1264     }
1265
1266     RefPtr<CanonicalBrowsingContext> loadingBC =
1267         aFrameLoader->GetMaybePendingBrowsingContext()->Canonical();
1268     RefPtr<nsFrameLoader> currentFrameLoader =
1269         frameLoaderOwner->GetFrameLoader();
1270     // The current page can be bfcached, store the
1271     // nsFrameLoader in the current SessionHistoryEntry.
1272     RefPtr<SessionHistoryEntry> currentSHEntry =
1273         aBrowsingContext->GetActiveSessionHistoryEntry();
1274     if (currentSHEntry) {
1275       // Update layout history state now, before we change the IsInBFCache flag
1276       // and the active session history entry.
1277       aBrowsingContext->SynchronizeLayoutHistoryState();
1278
1279       if (aCanSave) {
1280         currentSHEntry->SetFrameLoader(currentFrameLoader);
1281         Unused << aBrowsingContext->SetIsInBFCache(true);
1282       }
1283     }
1284
1285     // Ensure browser priority to matches `IsPriorityActive` after restoring.
1286     if (BrowserParent* bp = loadingBC->GetBrowserParent()) {
1287       bp->VisitAll([&](BrowserParent* aBp) {
1288         ProcessPriorityManager::BrowserPriorityChanged(
1289             aBp, aBrowsingContext->IsPriorityActive());
1290       });
1291     }
1292
1293     if (aEntry) {
1294       aEntry->SetWireframe(Nothing());
1295     }
1296
1297     // ReplacedBy will swap the entry back.
1298     aBrowsingContext->SetActiveSessionHistoryEntry(aEntry);
1299     loadingBC->SetActiveSessionHistoryEntry(nullptr);
1300     NavigationIsolationOptions options;
1301     aBrowsingContext->ReplacedBy(loadingBC, options);
1302
1303     // Assuming we still have the session history, update the index.
1304     if (loadingBC->GetSessionHistory()) {
1305       shistory->InternalSetRequestedIndex(indexOfHistoryLoad);
1306       shistory->UpdateIndex();
1307     }
1308     loadingBC->HistoryCommitIndexAndLength();
1309
1310     // ResetSHEntryHasUserInteractionCache(); ?
1311     // browser.navigation.requireUserInteraction is still
1312     // disabled everywhere.
1313
1314     frameLoaderOwner->RestoreFrameLoaderFromBFCache(aFrameLoader);
1315     // EvictOutOfRangeDocumentViewers is called here explicitly to
1316     // possibly evict the now in the bfcache document.
1317     // HistoryCommitIndexAndLength might not have evicted that before the
1318     // FrameLoader swap.
1319     shistory->EvictOutOfRangeDocumentViewers(indexOfHistoryLoad);
1320
1321     // The old page can't be stored in the bfcache,
1322     // destroy the nsFrameLoader.
1323     if (!aCanSave && currentFrameLoader) {
1324       currentFrameLoader->Destroy();
1325     }
1326
1327     Unused << loadingBC->SetIsInBFCache(false);
1328
1329     // We need to call this after we've restored the page from BFCache (see
1330     // SetIsInBFCache(false) above), so that the page is not frozen anymore and
1331     // the right focus events are fired.
1332     frameLoaderOwner->UpdateFocusAndMouseEnterStateAfterFrameLoaderChange();
1333
1334     return;
1335   }
1336
1337   aFrameLoader->Destroy();
1338
1339   // Fall back to do a normal load.
1340   aBrowsingContext->LoadURI(aLoadState, false);
1341 }
1342
1343 /* static */
1344 void nsSHistory::LoadURIOrBFCache(LoadEntryResult& aLoadEntry) {
1345   if (mozilla::BFCacheInParent() && aLoadEntry.mBrowsingContext->IsTop()) {
1346     MOZ_ASSERT(XRE_IsParentProcess());
1347     RefPtr<nsDocShellLoadState> loadState = aLoadEntry.mLoadState;
1348     RefPtr<CanonicalBrowsingContext> canonicalBC =
1349         aLoadEntry.mBrowsingContext->Canonical();
1350     nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(loadState->SHEntry());
1351     nsCOMPtr<SessionHistoryEntry> currentShe =
1352         canonicalBC->GetActiveSessionHistoryEntry();
1353     MOZ_ASSERT(she);
1354     RefPtr<nsFrameLoader> frameLoader = she->GetFrameLoader();
1355     if (frameLoader && canonicalBC->Group()->Toplevels().Length() == 1 &&
1356         (!currentShe || (she->SharedInfo() != currentShe->SharedInfo() &&
1357                          !currentShe->GetFrameLoader()))) {
1358       bool canSave = (!currentShe || currentShe->GetSaveLayoutStateFlag()) &&
1359                      canonicalBC->AllowedInBFCache(Nothing(), nullptr);
1360
1361       MOZ_LOG(gSHIPBFCacheLog, LogLevel::Debug,
1362               ("nsSHistory::LoadURIOrBFCache "
1363                "saving presentation=%i",
1364                canSave));
1365
1366       nsCOMPtr<nsFrameLoaderOwner> frameLoaderOwner =
1367           do_QueryInterface(canonicalBC->GetEmbedderElement());
1368       if (frameLoaderOwner) {
1369         RefPtr<nsFrameLoader> currentFrameLoader =
1370             frameLoaderOwner->GetFrameLoader();
1371         if (currentFrameLoader &&
1372             currentFrameLoader->GetMaybePendingBrowsingContext()) {
1373           if (WindowGlobalParent* wgp =
1374                   currentFrameLoader->GetMaybePendingBrowsingContext()
1375                       ->Canonical()
1376                       ->GetCurrentWindowGlobal()) {
1377             wgp->PermitUnload(
1378                 [canonicalBC, loadState, she, frameLoader, currentFrameLoader,
1379                  canSave](bool aAllow) MOZ_CAN_RUN_SCRIPT_BOUNDARY_LAMBDA {
1380                   if (aAllow && !canonicalBC->IsReplaced()) {
1381                     FinishRestore(canonicalBC, loadState, she, frameLoader,
1382                                   canSave && canonicalBC->AllowedInBFCache(
1383                                                  Nothing(), nullptr));
1384                   } else if (currentFrameLoader
1385                                  ->GetMaybePendingBrowsingContext()) {
1386                     nsISHistory* shistory =
1387                         currentFrameLoader->GetMaybePendingBrowsingContext()
1388                             ->Canonical()
1389                             ->GetSessionHistory();
1390                     if (shistory) {
1391                       shistory->InternalSetRequestedIndex(-1);
1392                     }
1393                   }
1394                 });
1395             return;
1396           }
1397         }
1398       }
1399
1400       FinishRestore(canonicalBC, loadState, she, frameLoader, canSave);
1401       return;
1402     }
1403     if (frameLoader) {
1404       she->SetFrameLoader(nullptr);
1405       frameLoader->Destroy();
1406     }
1407   }
1408
1409   RefPtr<BrowsingContext> bc = aLoadEntry.mBrowsingContext;
1410   RefPtr<nsDocShellLoadState> loadState = aLoadEntry.mLoadState;
1411   bc->LoadURI(loadState, false);
1412 }
1413
1414 /* static */
1415 void nsSHistory::LoadURIs(nsTArray<LoadEntryResult>& aLoadResults) {
1416   for (LoadEntryResult& loadEntry : aLoadResults) {
1417     LoadURIOrBFCache(loadEntry);
1418   }
1419 }
1420
1421 NS_IMETHODIMP
1422 nsSHistory::Reload(uint32_t aReloadFlags) {
1423   nsTArray<LoadEntryResult> loadResults;
1424   nsresult rv = Reload(aReloadFlags, loadResults);
1425   NS_ENSURE_SUCCESS(rv, rv);
1426
1427   if (loadResults.IsEmpty()) {
1428     return NS_OK;
1429   }
1430
1431   LoadURIs(loadResults);
1432   return NS_OK;
1433 }
1434
1435 nsresult nsSHistory::Reload(uint32_t aReloadFlags,
1436                             nsTArray<LoadEntryResult>& aLoadResults) {
1437   MOZ_ASSERT(aLoadResults.IsEmpty());
1438
1439   uint32_t loadType;
1440   if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_PROXY &&
1441       aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_CACHE) {
1442     loadType = LOAD_RELOAD_BYPASS_PROXY_AND_CACHE;
1443   } else if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_PROXY) {
1444     loadType = LOAD_RELOAD_BYPASS_PROXY;
1445   } else if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_CACHE) {
1446     loadType = LOAD_RELOAD_BYPASS_CACHE;
1447   } else if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_CHARSET_CHANGE) {
1448     loadType = LOAD_RELOAD_CHARSET_CHANGE;
1449   } else {
1450     loadType = LOAD_RELOAD_NORMAL;
1451   }
1452
1453   // We are reloading. Send Reload notifications.
1454   // nsDocShellLoadFlagType is not public, where as nsIWebNavigation
1455   // is public. So send the reload notifications with the
1456   // nsIWebNavigation flags.
1457   bool canNavigate = true;
1458   MOZ_ALWAYS_SUCCEEDS(NotifyOnHistoryReload(&canNavigate));
1459   if (!canNavigate) {
1460     return NS_OK;
1461   }
1462
1463   nsresult rv = LoadEntry(
1464       mIndex, loadType, HIST_CMD_RELOAD, aLoadResults, /* aSameEpoch */ false,
1465       /* aLoadCurrentEntry */ true,
1466       aReloadFlags & nsIWebNavigation::LOAD_FLAGS_USER_ACTIVATION);
1467   if (NS_FAILED(rv)) {
1468     aLoadResults.Clear();
1469     return rv;
1470   }
1471
1472   return NS_OK;
1473 }
1474
1475 NS_IMETHODIMP
1476 nsSHistory::ReloadCurrentEntry() {
1477   nsTArray<LoadEntryResult> loadResults;
1478   nsresult rv = ReloadCurrentEntry(loadResults);
1479   NS_ENSURE_SUCCESS(rv, rv);
1480
1481   LoadURIs(loadResults);
1482   return NS_OK;
1483 }
1484
1485 nsresult nsSHistory::ReloadCurrentEntry(
1486     nsTArray<LoadEntryResult>& aLoadResults) {
1487   // Notify listeners
1488   NotifyListeners(mListeners, [](auto l) { l->OnHistoryGotoIndex(); });
1489
1490   return LoadEntry(mIndex, LOAD_HISTORY, HIST_CMD_RELOAD, aLoadResults,
1491                    /* aSameEpoch */ false, /* aLoadCurrentEntry */ true,
1492                    /* aUserActivation */ false);
1493 }
1494
1495 void nsSHistory::EvictOutOfRangeWindowDocumentViewers(int32_t aIndex) {
1496   // XXX rename method to EvictDocumentViewersExceptAroundIndex, or something.
1497
1498   // We need to release all content viewers that are no longer in the range
1499   //
1500   //  aIndex - VIEWER_WINDOW to aIndex + VIEWER_WINDOW
1501   //
1502   // to ensure that this SHistory object isn't responsible for more than
1503   // VIEWER_WINDOW content viewers.  But our job is complicated by the
1504   // fact that two entries which are related by either hash navigations or
1505   // history.pushState will have the same content viewer.
1506   //
1507   // To illustrate the issue, suppose VIEWER_WINDOW = 3 and we have four
1508   // linked entries in our history.  Suppose we then add a new content
1509   // viewer and call into this function.  So the history looks like:
1510   //
1511   //   A A A A B
1512   //     +     *
1513   //
1514   // where the letters are content viewers and + and * denote the beginning and
1515   // end of the range aIndex +/- VIEWER_WINDOW.
1516   //
1517   // Although one copy of the content viewer A exists outside the range, we
1518   // don't want to evict A, because it has other copies in range!
1519   //
1520   // We therefore adjust our eviction strategy to read:
1521   //
1522   //   Evict each content viewer outside the range aIndex -/+
1523   //   VIEWER_WINDOW, unless that content viewer also appears within the
1524   //   range.
1525   //
1526   // (Note that it's entirely legal to have two copies of one content viewer
1527   // separated by a different content viewer -- call pushState twice, go back
1528   // once, and refresh -- so we can't rely on identical viewers only appearing
1529   // adjacent to one another.)
1530
1531   if (aIndex < 0) {
1532     return;
1533   }
1534   NS_ENSURE_TRUE_VOID(aIndex < Length());
1535
1536   // Calculate the range that's safe from eviction.
1537   int32_t startSafeIndex, endSafeIndex;
1538   WindowIndices(aIndex, &startSafeIndex, &endSafeIndex);
1539
1540   LOG(
1541       ("EvictOutOfRangeWindowDocumentViewers(index=%d), "
1542        "Length()=%d. Safe range [%d, %d]",
1543        aIndex, Length(), startSafeIndex, endSafeIndex));
1544
1545   // The content viewers in range aIndex -/+ VIEWER_WINDOW will not be
1546   // evicted.  Collect a set of them so we don't accidentally evict one of them
1547   // if it appears outside this range.
1548   nsCOMArray<nsIDocumentViewer> safeViewers;
1549   nsTArray<RefPtr<nsFrameLoader>> safeFrameLoaders;
1550   for (int32_t i = startSafeIndex; i <= endSafeIndex; i++) {
1551     nsCOMPtr<nsIDocumentViewer> viewer = mEntries[i]->GetDocumentViewer();
1552     if (viewer) {
1553       safeViewers.AppendObject(viewer);
1554     } else if (nsCOMPtr<SessionHistoryEntry> she =
1555                    do_QueryInterface(mEntries[i])) {
1556       nsFrameLoader* frameLoader = she->GetFrameLoader();
1557       if (frameLoader) {
1558         safeFrameLoaders.AppendElement(frameLoader);
1559       }
1560     }
1561   }
1562
1563   // Walk the SHistory list and evict any content viewers that aren't safe.
1564   // (It's important that the condition checks Length(), rather than a cached
1565   // copy of Length(), because the length might change between iterations.)
1566   for (int32_t i = 0; i < Length(); i++) {
1567     nsCOMPtr<nsISHEntry> entry = mEntries[i];
1568     nsCOMPtr<nsIDocumentViewer> viewer = entry->GetDocumentViewer();
1569     if (viewer) {
1570       if (safeViewers.IndexOf(viewer) == -1) {
1571         EvictDocumentViewerForEntry(entry);
1572       }
1573     } else if (nsCOMPtr<SessionHistoryEntry> she =
1574                    do_QueryInterface(mEntries[i])) {
1575       nsFrameLoader* frameLoader = she->GetFrameLoader();
1576       if (frameLoader) {
1577         if (!safeFrameLoaders.Contains(frameLoader)) {
1578           EvictDocumentViewerForEntry(entry);
1579         }
1580       }
1581     }
1582   }
1583 }
1584
1585 namespace {
1586
1587 class EntryAndDistance {
1588  public:
1589   EntryAndDistance(nsSHistory* aSHistory, nsISHEntry* aEntry, uint32_t aDist)
1590       : mSHistory(aSHistory),
1591         mEntry(aEntry),
1592         mViewer(aEntry->GetDocumentViewer()),
1593         mLastTouched(mEntry->GetLastTouched()),
1594         mDistance(aDist) {
1595     nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(aEntry);
1596     if (she) {
1597       mFrameLoader = she->GetFrameLoader();
1598     }
1599     NS_ASSERTION(mViewer || mFrameLoader,
1600                  "Entry should have a content viewer or frame loader.");
1601   }
1602
1603   bool operator<(const EntryAndDistance& aOther) const {
1604     // Compare distances first, and fall back to last-accessed times.
1605     if (aOther.mDistance != this->mDistance) {
1606       return this->mDistance < aOther.mDistance;
1607     }
1608
1609     return this->mLastTouched < aOther.mLastTouched;
1610   }
1611
1612   bool operator==(const EntryAndDistance& aOther) const {
1613     // This is a little silly; we need == so the default comaprator can be
1614     // instantiated, but this function is never actually called when we sort
1615     // the list of EntryAndDistance objects.
1616     return aOther.mDistance == this->mDistance &&
1617            aOther.mLastTouched == this->mLastTouched;
1618   }
1619
1620   RefPtr<nsSHistory> mSHistory;
1621   nsCOMPtr<nsISHEntry> mEntry;
1622   nsCOMPtr<nsIDocumentViewer> mViewer;
1623   RefPtr<nsFrameLoader> mFrameLoader;
1624   uint32_t mLastTouched;
1625   int32_t mDistance;
1626 };
1627
1628 }  // namespace
1629
1630 // static
1631 void nsSHistory::GloballyEvictDocumentViewers() {
1632   // First, collect from each SHistory object the entries which have a cached
1633   // content viewer. Associate with each entry its distance from its SHistory's
1634   // current index.
1635
1636   nsTArray<EntryAndDistance> entries;
1637
1638   for (auto shist : gSHistoryList.mList) {
1639     // Maintain a list of the entries which have viewers and belong to
1640     // this particular shist object.  We'll add this list to the global list,
1641     // |entries|, eventually.
1642     nsTArray<EntryAndDistance> shEntries;
1643
1644     // Content viewers are likely to exist only within shist->mIndex -/+
1645     // VIEWER_WINDOW, so only search within that range.
1646     //
1647     // A content viewer might exist outside that range due to either:
1648     //
1649     //   * history.pushState or hash navigations, in which case a copy of the
1650     //     content viewer should exist within the range, or
1651     //
1652     //   * bugs which cause us not to call nsSHistory::EvictDocumentViewers()
1653     //     often enough.  Once we do call EvictDocumentViewers() for the
1654     //     SHistory object in question, we'll do a full search of its history
1655     //     and evict the out-of-range content viewers, so we don't bother here.
1656     //
1657     int32_t startIndex, endIndex;
1658     shist->WindowIndices(shist->mIndex, &startIndex, &endIndex);
1659     for (int32_t i = startIndex; i <= endIndex; i++) {
1660       nsCOMPtr<nsISHEntry> entry = shist->mEntries[i];
1661       nsCOMPtr<nsIDocumentViewer> viewer = entry->GetDocumentViewer();
1662
1663       bool found = false;
1664       bool hasDocumentViewerOrFrameLoader = false;
1665       if (viewer) {
1666         hasDocumentViewerOrFrameLoader = true;
1667         // Because one content viewer might belong to multiple SHEntries, we
1668         // have to search through shEntries to see if we already know
1669         // about this content viewer.  If we find the viewer, update its
1670         // distance from the SHistory's index and continue.
1671         for (uint32_t j = 0; j < shEntries.Length(); j++) {
1672           EntryAndDistance& container = shEntries[j];
1673           if (container.mViewer == viewer) {
1674             container.mDistance =
1675                 std::min(container.mDistance, DeprecatedAbs(i - shist->mIndex));
1676             found = true;
1677             break;
1678           }
1679         }
1680       } else if (nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(entry)) {
1681         if (RefPtr<nsFrameLoader> frameLoader = she->GetFrameLoader()) {
1682           hasDocumentViewerOrFrameLoader = true;
1683           // Similar search as above but using frameloader.
1684           for (uint32_t j = 0; j < shEntries.Length(); j++) {
1685             EntryAndDistance& container = shEntries[j];
1686             if (container.mFrameLoader == frameLoader) {
1687               container.mDistance = std::min(container.mDistance,
1688                                              DeprecatedAbs(i - shist->mIndex));
1689               found = true;
1690               break;
1691             }
1692           }
1693         }
1694       }
1695
1696       // If we didn't find a EntryAndDistance for this content viewer /
1697       // frameloader, make a new one.
1698       if (hasDocumentViewerOrFrameLoader && !found) {
1699         EntryAndDistance container(shist, entry,
1700                                    DeprecatedAbs(i - shist->mIndex));
1701         shEntries.AppendElement(container);
1702       }
1703     }
1704
1705     // We've found all the entries belonging to shist which have viewers.
1706     // Add those entries to our global list and move on.
1707     entries.AppendElements(shEntries);
1708   }
1709
1710   // We now have collected all cached content viewers.  First check that we
1711   // have enough that we actually need to evict some.
1712   if ((int32_t)entries.Length() <= sHistoryMaxTotalViewers) {
1713     return;
1714   }
1715
1716   // If we need to evict, sort our list of entries and evict the largest
1717   // ones.  (We could of course get better algorithmic complexity here by using
1718   // a heap or something more clever.  But sHistoryMaxTotalViewers isn't large,
1719   // so let's not worry about it.)
1720   entries.Sort();
1721
1722   for (int32_t i = entries.Length() - 1; i >= sHistoryMaxTotalViewers; --i) {
1723     (entries[i].mSHistory)->EvictDocumentViewerForEntry(entries[i].mEntry);
1724   }
1725 }
1726
1727 nsresult nsSHistory::FindEntryForBFCache(SHEntrySharedParentState* aEntry,
1728                                          nsISHEntry** aResult,
1729                                          int32_t* aResultIndex) {
1730   *aResult = nullptr;
1731   *aResultIndex = -1;
1732
1733   int32_t startIndex, endIndex;
1734   WindowIndices(mIndex, &startIndex, &endIndex);
1735
1736   for (int32_t i = startIndex; i <= endIndex; ++i) {
1737     nsCOMPtr<nsISHEntry> shEntry = mEntries[i];
1738
1739     // Does shEntry have the same BFCacheEntry as the argument to this method?
1740     if (shEntry->HasBFCacheEntry(aEntry)) {
1741       shEntry.forget(aResult);
1742       *aResultIndex = i;
1743       return NS_OK;
1744     }
1745   }
1746   return NS_ERROR_FAILURE;
1747 }
1748
1749 NS_IMETHODIMP_(void)
1750 nsSHistory::EvictExpiredDocumentViewerForEntry(
1751     SHEntrySharedParentState* aEntry) {
1752   int32_t index;
1753   nsCOMPtr<nsISHEntry> shEntry;
1754   FindEntryForBFCache(aEntry, getter_AddRefs(shEntry), &index);
1755
1756   if (index == mIndex) {
1757     NS_WARNING("How did the current SHEntry expire?");
1758   }
1759
1760   if (shEntry) {
1761     EvictDocumentViewerForEntry(shEntry);
1762   }
1763 }
1764
1765 NS_IMETHODIMP_(void)
1766 nsSHistory::AddToExpirationTracker(SHEntrySharedParentState* aEntry) {
1767   RefPtr<SHEntrySharedParentState> entry = aEntry;
1768   if (!mHistoryTracker || !entry) {
1769     return;
1770   }
1771
1772   mHistoryTracker->AddObject(entry);
1773   return;
1774 }
1775
1776 NS_IMETHODIMP_(void)
1777 nsSHistory::RemoveFromExpirationTracker(SHEntrySharedParentState* aEntry) {
1778   RefPtr<SHEntrySharedParentState> entry = aEntry;
1779   MOZ_ASSERT(mHistoryTracker && !mHistoryTracker->IsEmpty());
1780   if (!mHistoryTracker || !entry) {
1781     return;
1782   }
1783
1784   mHistoryTracker->RemoveObject(entry);
1785 }
1786
1787 // Evicts all content viewers in all history objects.  This is very
1788 // inefficient, because it requires a linear search through all SHistory
1789 // objects for each viewer to be evicted.  However, this method is called
1790 // infrequently -- only when the disk or memory cache is cleared.
1791
1792 // static
1793 void nsSHistory::GloballyEvictAllDocumentViewers() {
1794   int32_t maxViewers = sHistoryMaxTotalViewers;
1795   sHistoryMaxTotalViewers = 0;
1796   GloballyEvictDocumentViewers();
1797   sHistoryMaxTotalViewers = maxViewers;
1798 }
1799
1800 void GetDynamicChildren(nsISHEntry* aEntry, nsTArray<nsID>& aDocshellIDs) {
1801   int32_t count = aEntry->GetChildCount();
1802   for (int32_t i = 0; i < count; ++i) {
1803     nsCOMPtr<nsISHEntry> child;
1804     aEntry->GetChildAt(i, getter_AddRefs(child));
1805     if (child) {
1806       if (child->IsDynamicallyAdded()) {
1807         child->GetDocshellID(*aDocshellIDs.AppendElement());
1808       } else {
1809         GetDynamicChildren(child, aDocshellIDs);
1810       }
1811     }
1812   }
1813 }
1814
1815 bool RemoveFromSessionHistoryEntry(nsISHEntry* aRoot,
1816                                    nsTArray<nsID>& aDocshellIDs) {
1817   bool didRemove = false;
1818   int32_t childCount = aRoot->GetChildCount();
1819   for (int32_t i = childCount - 1; i >= 0; --i) {
1820     nsCOMPtr<nsISHEntry> child;
1821     aRoot->GetChildAt(i, getter_AddRefs(child));
1822     if (child) {
1823       nsID docshelldID;
1824       child->GetDocshellID(docshelldID);
1825       if (aDocshellIDs.Contains(docshelldID)) {
1826         didRemove = true;
1827         aRoot->RemoveChild(child);
1828       } else if (RemoveFromSessionHistoryEntry(child, aDocshellIDs)) {
1829         didRemove = true;
1830       }
1831     }
1832   }
1833   return didRemove;
1834 }
1835
1836 bool RemoveChildEntries(nsISHistory* aHistory, int32_t aIndex,
1837                         nsTArray<nsID>& aEntryIDs) {
1838   nsCOMPtr<nsISHEntry> root;
1839   aHistory->GetEntryAtIndex(aIndex, getter_AddRefs(root));
1840   return root ? RemoveFromSessionHistoryEntry(root, aEntryIDs) : false;
1841 }
1842
1843 bool IsSameTree(nsISHEntry* aEntry1, nsISHEntry* aEntry2) {
1844   if (!aEntry1 && !aEntry2) {
1845     return true;
1846   }
1847   if ((!aEntry1 && aEntry2) || (aEntry1 && !aEntry2)) {
1848     return false;
1849   }
1850   uint32_t id1 = aEntry1->GetID();
1851   uint32_t id2 = aEntry2->GetID();
1852   if (id1 != id2) {
1853     return false;
1854   }
1855
1856   int32_t count1 = aEntry1->GetChildCount();
1857   int32_t count2 = aEntry2->GetChildCount();
1858   // We allow null entries in the end of the child list.
1859   int32_t count = std::max(count1, count2);
1860   for (int32_t i = 0; i < count; ++i) {
1861     nsCOMPtr<nsISHEntry> child1, child2;
1862     aEntry1->GetChildAt(i, getter_AddRefs(child1));
1863     aEntry2->GetChildAt(i, getter_AddRefs(child2));
1864     if (!IsSameTree(child1, child2)) {
1865       return false;
1866     }
1867   }
1868
1869   return true;
1870 }
1871
1872 bool nsSHistory::RemoveDuplicate(int32_t aIndex, bool aKeepNext) {
1873   NS_ASSERTION(aIndex >= 0, "aIndex must be >= 0!");
1874   NS_ASSERTION(aIndex != 0 || aKeepNext,
1875                "If we're removing index 0 we must be keeping the next");
1876   NS_ASSERTION(aIndex != mIndex, "Shouldn't remove mIndex!");
1877
1878   int32_t compareIndex = aKeepNext ? aIndex + 1 : aIndex - 1;
1879
1880   nsresult rv;
1881   nsCOMPtr<nsISHEntry> root1, root2;
1882   rv = GetEntryAtIndex(aIndex, getter_AddRefs(root1));
1883   if (NS_FAILED(rv)) {
1884     return false;
1885   }
1886   rv = GetEntryAtIndex(compareIndex, getter_AddRefs(root2));
1887   if (NS_FAILED(rv)) {
1888     return false;
1889   }
1890
1891   SHistoryChangeNotifier change(this);
1892
1893   if (IsSameTree(root1, root2)) {
1894     if (aIndex < compareIndex) {
1895       // If we're removing the entry with the lower index we need to move its
1896       // BCHistoryLength to the entry we're keeping. If we're removing the entry
1897       // with the higher index then it shouldn't have a modified
1898       // BCHistoryLength.
1899       UpdateEntryLength(root1, root2, true);
1900     }
1901     nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(root1);
1902     if (she) {
1903       ClearEntries(she);
1904     }
1905     mEntries.RemoveElementAt(aIndex);
1906
1907     // FIXME Bug 1546350: Reimplement history listeners.
1908     // if (mRootBC && mRootBC->GetDocShell()) {
1909     //  static_cast<nsDocShell*>(mRootBC->GetDocShell())
1910     //      ->HistoryEntryRemoved(aIndex);
1911     //}
1912
1913     // Adjust our indices to reflect the removed entry.
1914     if (mIndex > aIndex) {
1915       mIndex = mIndex - 1;
1916     }
1917
1918     // NB: If the entry we are removing is the entry currently
1919     // being navigated to (mRequestedIndex) then we adjust the index
1920     // only if we're not keeping the next entry (because if we are keeping
1921     // the next entry (because the current is a duplicate of the next), then
1922     // that entry slides into the spot that we're currently pointing to.
1923     // We don't do this adjustment for mIndex because mIndex cannot equal
1924     // aIndex.
1925
1926     // NB: We don't need to guard on mRequestedIndex being nonzero here,
1927     // because either they're strictly greater than aIndex which is at least
1928     // zero, or they are equal to aIndex in which case aKeepNext must be true
1929     // if aIndex is zero.
1930     if (mRequestedIndex > aIndex || (mRequestedIndex == aIndex && !aKeepNext)) {
1931       mRequestedIndex = mRequestedIndex - 1;
1932     }
1933
1934     return true;
1935   }
1936   return false;
1937 }
1938
1939 NS_IMETHODIMP_(void)
1940 nsSHistory::RemoveEntries(nsTArray<nsID>& aIDs, int32_t aStartIndex) {
1941   bool didRemove;
1942   RemoveEntries(aIDs, aStartIndex, &didRemove);
1943   if (didRemove) {
1944     RefPtr<BrowsingContext> rootBC = GetBrowsingContext();
1945     if (rootBC && rootBC->GetDocShell()) {
1946       rootBC->GetDocShell()->DispatchLocationChangeEvent();
1947     }
1948   }
1949 }
1950
1951 void nsSHistory::RemoveEntries(nsTArray<nsID>& aIDs, int32_t aStartIndex,
1952                                bool* aDidRemove) {
1953   SHistoryChangeNotifier change(this);
1954
1955   int32_t index = aStartIndex;
1956   while (index >= 0 && RemoveChildEntries(this, --index, aIDs)) {
1957   }
1958   int32_t minIndex = index;
1959   index = aStartIndex;
1960   while (index >= 0 && RemoveChildEntries(this, index++, aIDs)) {
1961   }
1962
1963   // We need to remove duplicate nsSHEntry trees.
1964   *aDidRemove = false;
1965   while (index > minIndex) {
1966     if (index != mIndex && RemoveDuplicate(index, index < mIndex)) {
1967       *aDidRemove = true;
1968     }
1969     --index;
1970   }
1971
1972   UpdateRootBrowsingContextState();
1973 }
1974
1975 void nsSHistory::RemoveFrameEntries(nsISHEntry* aEntry) {
1976   int32_t count = aEntry->GetChildCount();
1977   AutoTArray<nsID, 16> ids;
1978   for (int32_t i = 0; i < count; ++i) {
1979     nsCOMPtr<nsISHEntry> child;
1980     aEntry->GetChildAt(i, getter_AddRefs(child));
1981     if (child) {
1982       child->GetDocshellID(*ids.AppendElement());
1983     }
1984   }
1985   RemoveEntries(ids, mIndex);
1986 }
1987
1988 void nsSHistory::RemoveDynEntries(int32_t aIndex, nsISHEntry* aEntry) {
1989   // Remove dynamic entries which are at the index and belongs to the container.
1990   nsCOMPtr<nsISHEntry> entry(aEntry);
1991   if (!entry) {
1992     GetEntryAtIndex(aIndex, getter_AddRefs(entry));
1993   }
1994
1995   if (entry) {
1996     AutoTArray<nsID, 16> toBeRemovedEntries;
1997     GetDynamicChildren(entry, toBeRemovedEntries);
1998     if (toBeRemovedEntries.Length()) {
1999       RemoveEntries(toBeRemovedEntries, aIndex);
2000     }
2001   }
2002 }
2003
2004 void nsSHistory::RemoveDynEntriesForBFCacheEntry(nsIBFCacheEntry* aBFEntry) {
2005   int32_t index;
2006   nsCOMPtr<nsISHEntry> shEntry;
2007   FindEntryForBFCache(static_cast<nsSHEntryShared*>(aBFEntry),
2008                       getter_AddRefs(shEntry), &index);
2009   if (shEntry) {
2010     RemoveDynEntries(index, shEntry);
2011   }
2012 }
2013
2014 NS_IMETHODIMP
2015 nsSHistory::UpdateIndex() {
2016   SHistoryChangeNotifier change(this);
2017
2018   // Update the actual index with the right value.
2019   if (mIndex != mRequestedIndex && mRequestedIndex != -1) {
2020     mIndex = mRequestedIndex;
2021   }
2022
2023   mRequestedIndex = -1;
2024   return NS_OK;
2025 }
2026
2027 NS_IMETHODIMP
2028 nsSHistory::GotoIndex(int32_t aIndex, bool aUserActivation) {
2029   nsTArray<LoadEntryResult> loadResults;
2030   nsresult rv = GotoIndex(aIndex, loadResults, /*aSameEpoch*/ false,
2031                           aIndex == mIndex, aUserActivation);
2032   NS_ENSURE_SUCCESS(rv, rv);
2033
2034   LoadURIs(loadResults);
2035   return NS_OK;
2036 }
2037
2038 NS_IMETHODIMP_(void)
2039 nsSHistory::EnsureCorrectEntryAtCurrIndex(nsISHEntry* aEntry) {
2040   int index = mRequestedIndex == -1 ? mIndex : mRequestedIndex;
2041   if (index > -1 && (mEntries[index] != aEntry)) {
2042     ReplaceEntry(index, aEntry);
2043   }
2044 }
2045
2046 nsresult nsSHistory::GotoIndex(int32_t aIndex,
2047                                nsTArray<LoadEntryResult>& aLoadResults,
2048                                bool aSameEpoch, bool aLoadCurrentEntry,
2049                                bool aUserActivation) {
2050   return LoadEntry(aIndex, LOAD_HISTORY, HIST_CMD_GOTOINDEX, aLoadResults,
2051                    aSameEpoch, aLoadCurrentEntry, aUserActivation);
2052 }
2053
2054 NS_IMETHODIMP_(bool)
2055 nsSHistory::HasUserInteractionAtIndex(int32_t aIndex) {
2056   nsCOMPtr<nsISHEntry> entry;
2057   GetEntryAtIndex(aIndex, getter_AddRefs(entry));
2058   if (!entry) {
2059     return false;
2060   }
2061   return entry->GetHasUserInteraction();
2062 }
2063
2064 NS_IMETHODIMP
2065 nsSHistory::CanGoBackFromEntryAtIndex(int32_t aIndex, bool* aCanGoBack) {
2066   *aCanGoBack = false;
2067   if (!StaticPrefs::browser_navigation_requireUserInteraction()) {
2068     *aCanGoBack = aIndex > 0;
2069     return NS_OK;
2070   }
2071
2072   for (int32_t i = aIndex - 1; i >= 0; i--) {
2073     if (HasUserInteractionAtIndex(i)) {
2074       *aCanGoBack = true;
2075       break;
2076     }
2077   }
2078
2079   return NS_OK;
2080 }
2081
2082 nsresult nsSHistory::LoadNextPossibleEntry(
2083     int32_t aNewIndex, long aLoadType, uint32_t aHistCmd,
2084     nsTArray<LoadEntryResult>& aLoadResults, bool aLoadCurrentEntry,
2085     bool aUserActivation) {
2086   mRequestedIndex = -1;
2087   if (aNewIndex < mIndex) {
2088     return LoadEntry(aNewIndex - 1, aLoadType, aHistCmd, aLoadResults,
2089                      /*aSameEpoch*/ false, aLoadCurrentEntry, aUserActivation);
2090   }
2091   if (aNewIndex > mIndex) {
2092     return LoadEntry(aNewIndex + 1, aLoadType, aHistCmd, aLoadResults,
2093                      /*aSameEpoch*/ false, aLoadCurrentEntry, aUserActivation);
2094   }
2095   return NS_ERROR_FAILURE;
2096 }
2097
2098 nsresult nsSHistory::LoadEntry(int32_t aIndex, long aLoadType,
2099                                uint32_t aHistCmd,
2100                                nsTArray<LoadEntryResult>& aLoadResults,
2101                                bool aSameEpoch, bool aLoadCurrentEntry,
2102                                bool aUserActivation) {
2103   MOZ_LOG(gSHistoryLog, LogLevel::Debug,
2104           ("LoadEntry(%d, 0x%lx, %u)", aIndex, aLoadType, aHistCmd));
2105   RefPtr<BrowsingContext> rootBC = GetBrowsingContext();
2106   if (!rootBC) {
2107     return NS_ERROR_FAILURE;
2108   }
2109
2110   if (aIndex < 0 || aIndex >= Length()) {
2111     MOZ_LOG(gSHistoryLog, LogLevel::Debug, ("Index out of range"));
2112     // The index is out of range.
2113     // Clear the requested index in case it had bogus value. This way the next
2114     // load succeeds if the offset is reasonable.
2115     mRequestedIndex = -1;
2116
2117     return NS_ERROR_FAILURE;
2118   }
2119
2120   int32_t originalRequestedIndex = mRequestedIndex;
2121   int32_t previousRequest = mRequestedIndex > -1 ? mRequestedIndex : mIndex;
2122   int32_t requestedOffset = aIndex - previousRequest;
2123
2124   // This is a normal local history navigation.
2125
2126   nsCOMPtr<nsISHEntry> prevEntry;
2127   nsCOMPtr<nsISHEntry> nextEntry;
2128   GetEntryAtIndex(mIndex, getter_AddRefs(prevEntry));
2129   GetEntryAtIndex(aIndex, getter_AddRefs(nextEntry));
2130   if (!nextEntry || !prevEntry) {
2131     mRequestedIndex = -1;
2132     return NS_ERROR_FAILURE;
2133   }
2134
2135   if (mozilla::SessionHistoryInParent()) {
2136     if (aHistCmd == HIST_CMD_GOTOINDEX) {
2137       // https://html.spec.whatwg.org/#history-traversal:
2138       // To traverse the history
2139       // "If entry has a different Document object than the current entry, then
2140       // run the following substeps: Remove any tasks queued by the history
2141       // traversal task source..."
2142       //
2143       // aSameEpoch is true only if the navigations would have been
2144       // generated in the same spin of the event loop (i.e. history.go(-2);
2145       // history.go(-1)) and from the same content process.
2146       if (aSameEpoch) {
2147         bool same_doc = false;
2148         prevEntry->SharesDocumentWith(nextEntry, &same_doc);
2149         if (!same_doc) {
2150           MOZ_LOG(
2151               gSHistoryLog, LogLevel::Debug,
2152               ("Aborting GotoIndex %d - same epoch and not same doc", aIndex));
2153           // Ignore this load. Before SessionHistoryInParent, this would
2154           // have been dropped in InternalLoad after we filter out SameDoc
2155           // loads.
2156           return NS_ERROR_FAILURE;
2157         }
2158       }
2159     }
2160   }
2161   // Keep note of requested history index in mRequestedIndex; after all bailouts
2162   mRequestedIndex = aIndex;
2163
2164   // Remember that this entry is getting loaded at this point in the sequence
2165
2166   nextEntry->SetLastTouched(++gTouchCounter);
2167
2168   // Get the uri for the entry we are about to visit
2169   nsCOMPtr<nsIURI> nextURI = nextEntry->GetURI();
2170
2171   MOZ_ASSERT(nextURI, "nextURI can't be null");
2172
2173   // Send appropriate listener notifications.
2174   if (aHistCmd == HIST_CMD_GOTOINDEX) {
2175     // We are going somewhere else. This is not reload either
2176     NotifyListeners(mListeners, [](auto l) { l->OnHistoryGotoIndex(); });
2177   }
2178
2179   if (mRequestedIndex == mIndex) {
2180     // Possibly a reload case
2181     InitiateLoad(nextEntry, rootBC, aLoadType, aLoadResults, aLoadCurrentEntry,
2182                  aUserActivation, requestedOffset);
2183     return NS_OK;
2184   }
2185
2186   // Going back or forward.
2187   bool differenceFound = LoadDifferingEntries(
2188       prevEntry, nextEntry, rootBC, aLoadType, aLoadResults, aLoadCurrentEntry,
2189       aUserActivation, requestedOffset);
2190   if (!differenceFound) {
2191     // LoadNextPossibleEntry will change the offset by one, and in order
2192     // to keep track of the requestedOffset, need to reset mRequestedIndex to
2193     // the value it had initially.
2194     mRequestedIndex = originalRequestedIndex;
2195     // We did not find any differences. Go further in the history.
2196     return LoadNextPossibleEntry(aIndex, aLoadType, aHistCmd, aLoadResults,
2197                                  aLoadCurrentEntry, aUserActivation);
2198   }
2199
2200   return NS_OK;
2201 }
2202
2203 bool nsSHistory::LoadDifferingEntries(nsISHEntry* aPrevEntry,
2204                                       nsISHEntry* aNextEntry,
2205                                       BrowsingContext* aParent, long aLoadType,
2206                                       nsTArray<LoadEntryResult>& aLoadResults,
2207                                       bool aLoadCurrentEntry,
2208                                       bool aUserActivation, int32_t aOffset) {
2209   MOZ_ASSERT(aPrevEntry && aNextEntry && aParent);
2210
2211   uint32_t prevID = aPrevEntry->GetID();
2212   uint32_t nextID = aNextEntry->GetID();
2213
2214   // Check the IDs to verify if the pages are different.
2215   if (prevID != nextID) {
2216     // Set the Subframe flag if not navigating the root docshell.
2217     aNextEntry->SetIsSubFrame(aParent->Id() != mRootBC);
2218     InitiateLoad(aNextEntry, aParent, aLoadType, aLoadResults,
2219                  aLoadCurrentEntry, aUserActivation, aOffset);
2220     return true;
2221   }
2222
2223   // The entries are the same, so compare any child frames
2224   int32_t pcnt = aPrevEntry->GetChildCount();
2225   int32_t ncnt = aNextEntry->GetChildCount();
2226
2227   // Create an array for child browsing contexts.
2228   nsTArray<RefPtr<BrowsingContext>> browsingContexts;
2229   aParent->GetChildren(browsingContexts);
2230
2231   // Search for something to load next.
2232   bool differenceFound = false;
2233   for (int32_t i = 0; i < ncnt; ++i) {
2234     // First get an entry which may cause a new page to be loaded.
2235     nsCOMPtr<nsISHEntry> nChild;
2236     aNextEntry->GetChildAt(i, getter_AddRefs(nChild));
2237     if (!nChild) {
2238       continue;
2239     }
2240     nsID docshellID;
2241     nChild->GetDocshellID(docshellID);
2242
2243     // Then find the associated docshell.
2244     RefPtr<BrowsingContext> bcChild;
2245     for (const RefPtr<BrowsingContext>& bc : browsingContexts) {
2246       if (bc->GetHistoryID() == docshellID) {
2247         bcChild = bc;
2248         break;
2249       }
2250     }
2251     if (!bcChild) {
2252       continue;
2253     }
2254
2255     // Then look at the previous entries to see if there was
2256     // an entry for the docshell.
2257     nsCOMPtr<nsISHEntry> pChild;
2258     for (int32_t k = 0; k < pcnt; ++k) {
2259       nsCOMPtr<nsISHEntry> child;
2260       aPrevEntry->GetChildAt(k, getter_AddRefs(child));
2261       if (child) {
2262         nsID dID;
2263         child->GetDocshellID(dID);
2264         if (dID == docshellID) {
2265           pChild = child;
2266           break;
2267         }
2268       }
2269     }
2270     if (!pChild) {
2271       continue;
2272     }
2273
2274     // Finally recursively call this method.
2275     // This will either load a new page to shell or some subshell or
2276     // do nothing.
2277     if (LoadDifferingEntries(pChild, nChild, bcChild, aLoadType, aLoadResults,
2278                              aLoadCurrentEntry, aUserActivation, aOffset)) {
2279       differenceFound = true;
2280     }
2281   }
2282   return differenceFound;
2283 }
2284
2285 void nsSHistory::InitiateLoad(nsISHEntry* aFrameEntry,
2286                               BrowsingContext* aFrameBC, long aLoadType,
2287                               nsTArray<LoadEntryResult>& aLoadResults,
2288                               bool aLoadCurrentEntry, bool aUserActivation,
2289                               int32_t aOffset) {
2290   MOZ_ASSERT(aFrameBC && aFrameEntry);
2291
2292   LoadEntryResult* loadResult = aLoadResults.AppendElement();
2293   loadResult->mBrowsingContext = aFrameBC;
2294
2295   nsCOMPtr<nsIURI> newURI = aFrameEntry->GetURI();
2296   RefPtr<nsDocShellLoadState> loadState = new nsDocShellLoadState(newURI);
2297
2298   loadState->SetHasValidUserGestureActivation(aUserActivation);
2299
2300   // At the time we initiate a history entry load we already know if https-first
2301   // was able to upgrade the request from http to https. There is no point in
2302   // re-retrying to upgrade.
2303   loadState->SetIsExemptFromHTTPSFirstMode(true);
2304
2305   /* Set the loadType in the SHEntry too to  what was passed on.
2306    * This will be passed on to child subframes later in nsDocShell,
2307    * so that proper loadType is maintained through out a frameset
2308    */
2309   aFrameEntry->SetLoadType(aLoadType);
2310
2311   loadState->SetLoadType(aLoadType);
2312
2313   loadState->SetSHEntry(aFrameEntry);
2314
2315   // If we're loading the current entry we want to treat it as not a
2316   // same-document navigation (see nsDocShell::IsSameDocumentNavigation), so
2317   // record that here in the LoadingSessionHistoryEntry.
2318   bool loadingCurrentEntry;
2319   if (mozilla::SessionHistoryInParent()) {
2320     loadingCurrentEntry = aLoadCurrentEntry;
2321   } else {
2322     loadingCurrentEntry =
2323         aFrameBC->GetDocShell() &&
2324         nsDocShell::Cast(aFrameBC->GetDocShell())->IsOSHE(aFrameEntry);
2325   }
2326   loadState->SetLoadIsFromSessionHistory(aOffset, loadingCurrentEntry);
2327
2328   if (mozilla::SessionHistoryInParent()) {
2329     nsCOMPtr<SessionHistoryEntry> she = do_QueryInterface(aFrameEntry);
2330     aFrameBC->Canonical()->AddLoadingSessionHistoryEntry(
2331         loadState->GetLoadingSessionHistoryInfo()->mLoadId, she);
2332   }
2333
2334   nsCOMPtr<nsIURI> originalURI = aFrameEntry->GetOriginalURI();
2335   loadState->SetOriginalURI(originalURI);
2336
2337   loadState->SetLoadReplace(aFrameEntry->GetLoadReplace());
2338
2339   loadState->SetLoadFlags(nsIWebNavigation::LOAD_FLAGS_NONE);
2340   nsCOMPtr<nsIPrincipal> triggeringPrincipal =
2341       aFrameEntry->GetTriggeringPrincipal();
2342   loadState->SetTriggeringPrincipal(triggeringPrincipal);
2343   loadState->SetFirstParty(false);
2344   nsCOMPtr<nsIContentSecurityPolicy> csp = aFrameEntry->GetCsp();
2345   loadState->SetCsp(csp);
2346
2347   loadResult->mLoadState = std::move(loadState);
2348 }
2349
2350 NS_IMETHODIMP
2351 nsSHistory::CreateEntry(nsISHEntry** aEntry) {
2352   nsCOMPtr<nsISHEntry> entry;
2353   if (XRE_IsParentProcess() && mozilla::SessionHistoryInParent()) {
2354     entry = new SessionHistoryEntry();
2355   } else {
2356     entry = new nsSHEntry();
2357   }
2358   entry.forget(aEntry);
2359   return NS_OK;
2360 }
2361
2362 NS_IMETHODIMP_(bool)
2363 nsSHistory::IsEmptyOrHasEntriesForSingleTopLevelPage() {
2364   if (mEntries.IsEmpty()) {
2365     return true;
2366   }
2367
2368   nsISHEntry* entry = mEntries[0];
2369   size_t length = mEntries.Length();
2370   for (size_t i = 1; i < length; ++i) {
2371     bool sharesDocument = false;
2372     mEntries[i]->SharesDocumentWith(entry, &sharesDocument);
2373     if (!sharesDocument) {
2374       return false;
2375     }
2376   }
2377
2378   return true;
2379 }
2380
2381 static void CollectEntries(
2382     nsTHashMap<nsIDHashKey, SessionHistoryEntry*>& aHashtable,
2383     SessionHistoryEntry* aEntry) {
2384   aHashtable.InsertOrUpdate(aEntry->DocshellID(), aEntry);
2385   for (const RefPtr<SessionHistoryEntry>& entry : aEntry->Children()) {
2386     if (entry) {
2387       CollectEntries(aHashtable, entry);
2388     }
2389   }
2390 }
2391
2392 static void UpdateEntryLength(
2393     nsTHashMap<nsIDHashKey, SessionHistoryEntry*>& aHashtable,
2394     SessionHistoryEntry* aNewEntry, bool aMove) {
2395   SessionHistoryEntry* oldEntry = aHashtable.Get(aNewEntry->DocshellID());
2396   if (oldEntry) {
2397     MOZ_ASSERT(oldEntry->GetID() != aNewEntry->GetID() || !aMove ||
2398                !aNewEntry->BCHistoryLength().Modified());
2399     aNewEntry->SetBCHistoryLength(oldEntry->BCHistoryLength());
2400     if (oldEntry->GetID() != aNewEntry->GetID()) {
2401       MOZ_ASSERT(!aMove);
2402       // If we have a new id then aNewEntry was created for a new load, so
2403       // record that in BCHistoryLength.
2404       ++aNewEntry->BCHistoryLength();
2405     } else if (aMove) {
2406       // We're moving the BCHistoryLength from the old entry to the new entry,
2407       // so we need to let the old entry know that it's not contributing to its
2408       // BCHistoryLength, and the new one that it does if the old one was
2409       // before.
2410       aNewEntry->BCHistoryLength().SetModified(
2411           oldEntry->BCHistoryLength().Modified());
2412       oldEntry->BCHistoryLength().SetModified(false);
2413     }
2414   }
2415
2416   for (const RefPtr<SessionHistoryEntry>& entry : aNewEntry->Children()) {
2417     if (entry) {
2418       UpdateEntryLength(aHashtable, entry, aMove);
2419     }
2420   }
2421 }
2422
2423 void nsSHistory::UpdateEntryLength(nsISHEntry* aOldEntry, nsISHEntry* aNewEntry,
2424                                    bool aMove) {
2425   nsCOMPtr<SessionHistoryEntry> oldSHE = do_QueryInterface(aOldEntry);
2426   nsCOMPtr<SessionHistoryEntry> newSHE = do_QueryInterface(aNewEntry);
2427
2428   if (!oldSHE || !newSHE) {
2429     return;
2430   }
2431
2432   nsTHashMap<nsIDHashKey, SessionHistoryEntry*> docshellIDToEntry;
2433   CollectEntries(docshellIDToEntry, oldSHE);
2434
2435   ::UpdateEntryLength(docshellIDToEntry, newSHE, aMove);
2436 }