docshell/shistory/src/nsSHistory.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is the Mozilla browser.
  17  *
  18  * The Initial Developer of the Original Code is
  19  * Netscape Communications, Inc.
  20  * Portions created by the Initial Developer are Copyright (C) 1999
  21  * the Initial Developer. All Rights Reserved.
  22  *
  23  * Contributor(s):
  24  *   Radha Kulkarni <radha@netscape.com>
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 // Local Includes
  41 #include "nsSHistory.h"
  42
  43 // Helper Classes
  44 #include "nsXPIDLString.h"
  45 #include "nsReadableUtils.h"
  46
  47 // Interfaces Needed
  48 #include "nsILayoutHistoryState.h"
  49 #include "nsIDocShell.h"
  50 #include "nsIDocShellLoadInfo.h"
  51 #include "nsISHContainer.h"
  52 #include "nsIDocShellTreeItem.h"
  53 #include "nsIDocShellTreeNode.h"
  54 #include "nsIDocShellLoadInfo.h"
  55 #include "nsIServiceManager.h"
  56 #include "nsIPrefService.h"
  57 #include "nsIURI.h"
  58 #include "nsIContentViewer.h"
  59 #include "nsICacheService.h"
  60 #include "nsIObserverService.h"
  61 #include "prclist.h"
  62 #include "mozilla/Services.h"
  63 #include "nsTArray.h"
  64 #include "nsCOMArray.h"
  65 #include "nsDocShell.h"
  66
  67 // For calculating max history entries and max cachable contentviewers
  68 #include "nspr.h"
  69 #include <math.h>  // for log()
  70
  71 #define PREF_SHISTORY_SIZE "browser.sessionhistory.max_entries"
  72 #define PREF_SHISTORY_MAX_TOTAL_VIEWERS "browser.sessionhistory.max_total_viewers"
  73 #define PREF_SHISTORY_OPTIMIZE_EVICTION "browser.sessionhistory.optimize_eviction"
  74
  75 static PRInt32  gHistoryMaxSize = 50;
  76 // Max viewers allowed per SHistory objects
  77 static const PRInt32  gHistoryMaxViewers = 3;
  78 // List of all SHistory objects, used for content viewer cache eviction
  79 static PRCList gSHistoryList;
  80 // Max viewers allowed total, across all SHistory objects - negative default
  81 // means we will calculate how many viewers to cache based on total memory
  82 PRInt32 nsSHistory::sHistoryMaxTotalViewers = -1;
  83
  84 // Whether we should optimize the search for which entry to evict,
  85 // by evicting older entries first. See entryLastTouched in
  86 // nsSHistory::EvictGlobalContentViewer().
  87 // NB: After 4.0, we should remove this option and the corresponding
  88 //     pref - optimization should always be used
  89 static PRBool gOptimizeEviction = PR_FALSE;
  90 // A counter that is used to be able to know the order in which
  91 // entries were touched, so that we can evict older entries first.
  92 static PRUint32 gTouchCounter = 0;
  93
  94 enum HistCmd{
  95   HIST_CMD_BACK,
  96   HIST_CMD_FORWARD,
  97   HIST_CMD_GOTOINDEX,
  98   HIST_CMD_RELOAD
  99 } ;
 100
 101 //*****************************************************************************
 102 //***      nsSHistoryObserver
 103 //*****************************************************************************
 104
 105 class nsSHistoryObserver : public nsIObserver
 106 {
 107
 108 public:
 109   NS_DECL_ISUPPORTS
 110   NS_DECL_NSIOBSERVER
 111
 112   nsSHistoryObserver() {}
 113
 114 protected:
 115   ~nsSHistoryObserver() {}
 116 };
 117
 118 NS_IMPL_ISUPPORTS1(nsSHistoryObserver, nsIObserver)
 119
 120 NS_IMETHODIMP
 121 nsSHistoryObserver::Observe(nsISupports *aSubject, const char *aTopic,
 122                             const PRUnichar *aData)
 123 {
 124   if (!strcmp(aTopic, NS_PREFBRANCH_PREFCHANGE_TOPIC_ID)) {
 125     nsCOMPtr<nsIPrefBranch> prefs = do_QueryInterface(aSubject);
 126     if (prefs) {
 127       nsSHistory::UpdatePrefs(prefs);
 128       nsSHistory::EvictGlobalContentViewer();
 129     }
 130   } else if (!strcmp(aTopic, NS_CACHESERVICE_EMPTYCACHE_TOPIC_ID) ||
 131              !strcmp(aTopic, "memory-pressure")) {
 132     nsSHistory::EvictAllContentViewersGlobally();
 133   }
 134
 135   return NS_OK;
 136 }
 137
 138 //*****************************************************************************
 139 //***    nsSHistory: Object Management
 140 //*****************************************************************************
 141
 142 nsSHistory::nsSHistory() : mListRoot(nsnull), mIndex(-1), mLength(0), mRequestedIndex(-1)
 143 {
 144   // Add this new SHistory object to the list
 145   PR_APPEND_LINK(this, &gSHistoryList);
 146 }
 147
 148
 149 nsSHistory::~nsSHistory()
 150 {
 151   // Remove this SHistory object from the list
 152   PR_REMOVE_LINK(this);
 153 }
 154
 155 //*****************************************************************************
 156 //    nsSHistory: nsISupports
 157 //*****************************************************************************
 158
 159 NS_IMPL_ADDREF(nsSHistory)
 160 NS_IMPL_RELEASE(nsSHistory)
 161
 162 NS_INTERFACE_MAP_BEGIN(nsSHistory)
 163    NS_INTERFACE_MAP_ENTRY_AMBIGUOUS(nsISupports, nsISHistory)
 164    NS_INTERFACE_MAP_ENTRY(nsISHistory)
 165    NS_INTERFACE_MAP_ENTRY(nsIWebNavigation)
 166    NS_INTERFACE_MAP_ENTRY(nsISHistoryInternal)
 167    NS_INTERFACE_MAP_ENTRY(nsISHistory_2_0_BRANCH)
 168 NS_INTERFACE_MAP_END
 169
 170 //*****************************************************************************
 171 //    nsSHistory: nsISHistory
 172 //*****************************************************************************
 173
 174 // static
 175 PRUint32
 176 nsSHistory::CalcMaxTotalViewers()
 177 {
 178   // Calculate an estimate of how many ContentViewers we should cache based
 179   // on RAM.  This assumes that the average ContentViewer is 4MB (conservative)
 180   // and caps the max at 8 ContentViewers
 181   //
 182   // TODO: Should we split the cache memory betw. ContentViewer caching and
 183   // nsCacheService?
 184   //
 185   // RAM      ContentViewers
 186   // -----------------------
 187   // 32   Mb       0
 188   // 64   Mb       1
 189   // 128  Mb       2
 190   // 256  Mb       3
 191   // 512  Mb       5
 192   // 1024 Mb       8
 193   // 2048 Mb       8
 194   // 4096 Mb       8
 195   PRUint64 bytes = PR_GetPhysicalMemorySize();
 196
 197   if (LL_IS_ZERO(bytes))
 198     return 0;
 199
 200   // Conversion from unsigned int64 to double doesn't work on all platforms.
 201   // We need to truncate the value at LL_MAXINT to make sure we don't
 202   // overflow.
 203   if (LL_CMP(bytes, >, LL_MAXINT))
 204     bytes = LL_MAXINT;
 205
 206   PRUint64 kbytes;
 207   LL_SHR(kbytes, bytes, 10);
 208
 209   double kBytesD;
 210   LL_L2D(kBytesD, (PRInt64) kbytes);
 211
 212   // This is essentially the same calculation as for nsCacheService,
 213   // except that we divide the final memory calculation by 4, since
 214   // we assume each ContentViewer takes on average 4MB
 215   PRUint32 viewers = 0;
 216   double x = log(kBytesD)/log(2.0) - 14;
 217   if (x > 0) {
 218     viewers    = (PRUint32)(x * x - x + 2.001); // add .001 for rounding
 219     viewers   /= 4;
 220   }
 221
 222   // Cap it off at 8 max
 223   if (viewers > 8) {
 224     viewers = 8;
 225   }
 226   return viewers;
 227 }
 228
 229 // static
 230 void
 231 nsSHistory::UpdatePrefs(nsIPrefBranch *aPrefBranch)
 232 {
 233   aPrefBranch->GetIntPref(PREF_SHISTORY_SIZE, &gHistoryMaxSize);
 234   aPrefBranch->GetIntPref(PREF_SHISTORY_MAX_TOTAL_VIEWERS,
 235                           &sHistoryMaxTotalViewers);
 236   aPrefBranch->GetBoolPref(PREF_SHISTORY_OPTIMIZE_EVICTION,
 237                           &gOptimizeEviction);
 238   // If the pref is negative, that means we calculate how many viewers
 239   // we think we should cache, based on total memory
 240   if (sHistoryMaxTotalViewers < 0) {
 241     sHistoryMaxTotalViewers = CalcMaxTotalViewers();
 242   }
 243 }
 244
 245 // static
 246 nsresult
 247 nsSHistory::Startup()
 248 {
 249   nsCOMPtr<nsIPrefService> prefs = do_GetService(NS_PREFSERVICE_CONTRACTID);
 250   if (prefs) {
 251     nsCOMPtr<nsIPrefBranch> sesHBranch;
 252     prefs->GetBranch(nsnull, getter_AddRefs(sesHBranch));
 253     if (sesHBranch) {
 254       UpdatePrefs(sesHBranch);
 255     }
 256
 257     // The goal of this is to unbreak users who have inadvertently set their
 258     // session history size to less than the default value.
 259     PRInt32  defaultHistoryMaxSize = 50;
 260     nsCOMPtr<nsIPrefBranch> defaultBranch;
 261     prefs->GetDefaultBranch(nsnull, getter_AddRefs(defaultBranch));
 262     if (defaultBranch) {
 263       defaultBranch->GetIntPref(PREF_SHISTORY_SIZE, &defaultHistoryMaxSize);
 264     }
 265
 266     if (gHistoryMaxSize < defaultHistoryMaxSize) {
 267       gHistoryMaxSize = defaultHistoryMaxSize;
 268     }
 269
 270     // Allow the user to override the max total number of cached viewers,
 271     // but keep the per SHistory cached viewer limit constant
 272     nsCOMPtr<nsIPrefBranch2> branch = do_QueryInterface(sesHBranch);
 273     if (branch) {
 274       nsSHistoryObserver* obs = new nsSHistoryObserver();
 275       if (!obs) {
 276         return NS_ERROR_OUT_OF_MEMORY;
 277       }
 278       branch->AddObserver(PREF_SHISTORY_SIZE, obs, PR_FALSE);
 279       branch->AddObserver(PREF_SHISTORY_MAX_TOTAL_VIEWERS,
 280                           obs, PR_FALSE);
 281       branch->AddObserver(PREF_SHISTORY_OPTIMIZE_EVICTION,
 282                           obs, PR_FALSE);
 283
 284       nsCOMPtr<nsIObserverService> obsSvc =
 285         mozilla::services::GetObserverService();
 286       if (obsSvc) {
 287         // Observe empty-cache notifications so tahat clearing the disk/memory
 288         // cache will also evict all content viewers.
 289         obsSvc->AddObserver(obs,
 290                             NS_CACHESERVICE_EMPTYCACHE_TOPIC_ID, PR_FALSE);
 291
 292         // Same for memory-pressure notifications
 293         obsSvc->AddObserver(obs, "memory-pressure", PR_FALSE);
 294       }
 295     }
 296   }
 297
 298   // Initialize the global list of all SHistory objects
 299   PR_INIT_CLIST(&gSHistoryList);
 300   return NS_OK;
 301 }
 302
 303 /* Add an entry to the History list at mIndex and
 304  * increment the index to point to the new entry
 305  */
 306 NS_IMETHODIMP
 307 nsSHistory::AddEntry(nsISHEntry * aSHEntry, PRBool aPersist)
 308 {
 309   NS_ENSURE_ARG(aSHEntry);
 310
 311   nsCOMPtr<nsISHTransaction> currentTxn;
 312
 313   if(mListRoot)
 314     GetTransactionAtIndex(mIndex, getter_AddRefs(currentTxn));
 315
 316   PRBool currentPersist = PR_TRUE;
 317   if(currentTxn)
 318     currentTxn->GetPersist(&currentPersist);
 319
 320   if(!currentPersist)
 321   {
 322     NS_ENSURE_SUCCESS(currentTxn->SetSHEntry(aSHEntry),NS_ERROR_FAILURE);
 323     currentTxn->SetPersist(aPersist);
 324     return NS_OK;
 325   }
 326
 327   nsCOMPtr<nsISHTransaction> txn(do_CreateInstance(NS_SHTRANSACTION_CONTRACTID));
 328   NS_ENSURE_TRUE(txn, NS_ERROR_FAILURE);
 329
 330   // Notify any listener about the new addition
 331   if (mListener) {
 332     nsCOMPtr<nsISHistoryListener> listener(do_QueryReferent(mListener));
 333     if (listener) {
 334       nsCOMPtr<nsIURI> uri;
 335       nsCOMPtr<nsIHistoryEntry> hEntry(do_QueryInterface(aSHEntry));
 336       if (hEntry) {
 337         PRInt32 currentIndex = mIndex;
 338         hEntry->GetURI(getter_AddRefs(uri));
 339         listener->OnHistoryNewEntry(uri);
 340
 341         // If a listener has changed mIndex, we need to get currentTxn again,
 342         // otherwise we'll be left at an inconsistent state (see bug 320742)
 343         if (currentIndex != mIndex)
 344           GetTransactionAtIndex(mIndex, getter_AddRefs(currentTxn));
 345       }
 346     }
 347   }
 348
 349   // Set the ShEntry and parent for the transaction. setting the
 350   // parent will properly set the parent child relationship
 351   txn->SetPersist(aPersist);
 352   NS_ENSURE_SUCCESS(txn->Create(aSHEntry, currentTxn), NS_ERROR_FAILURE);
 353
 354   // A little tricky math here...  Basically when adding an object regardless of
 355   // what the length was before, it should always be set back to the current and
 356   // lop off the forward.
 357   mLength = (++mIndex + 1);
 358
 359   // If this is the very first transaction, initialize the list
 360   if(!mListRoot)
 361     mListRoot = txn;
 362
 363   // Purge History list if it is too long
 364   if ((gHistoryMaxSize >= 0) && (mLength > gHistoryMaxSize))
 365     PurgeHistory(mLength-gHistoryMaxSize);
 366
 367   RemoveDynEntries(mIndex - 1, mIndex);
 368   return NS_OK;
 369 }
 370
 371 /* Get size of the history list */
 372 NS_IMETHODIMP
 373 nsSHistory::GetCount(PRInt32 * aResult)
 374 {
 375   NS_ENSURE_ARG_POINTER(aResult);
 376   *aResult = mLength;
 377   return NS_OK;
 378 }
 379
 380 /* Get index of the history list */
 381 NS_IMETHODIMP
 382 nsSHistory::GetIndex(PRInt32 * aResult)
 383 {
 384   NS_PRECONDITION(aResult, "null out param?");
 385   *aResult = mIndex;
 386   return NS_OK;
 387 }
 388
 389 /* Get the requestedIndex */
 390 NS_IMETHODIMP
 391 nsSHistory::GetRequestedIndex(PRInt32 * aResult)
 392 {
 393   NS_PRECONDITION(aResult, "null out param?");
 394   *aResult = mRequestedIndex;
 395   return NS_OK;
 396 }
 397
 398 NS_IMETHODIMP
 399 nsSHistory::GetEntryAtIndex(PRInt32 aIndex, PRBool aModifyIndex, nsISHEntry** aResult)
 400 {
 401   nsresult rv;
 402   nsCOMPtr<nsISHTransaction> txn;
 403
 404   /* GetTransactionAtIndex ensures aResult is valid and validates aIndex */
 405   rv = GetTransactionAtIndex(aIndex, getter_AddRefs(txn));
 406   if (NS_SUCCEEDED(rv) && txn) {
 407     //Get the Entry from the transaction
 408     rv = txn->GetSHEntry(aResult);
 409     if (NS_SUCCEEDED(rv) && (*aResult)) {
 410       // Set mIndex to the requested index, if asked to do so..
 411       if (aModifyIndex) {
 412         mIndex = aIndex;
 413       }
 414     } //entry
 415   }  //Transaction
 416   return rv;
 417 }
 418
 419
 420 /* Get the entry at a given index */
 421 NS_IMETHODIMP
 422 nsSHistory::GetEntryAtIndex(PRInt32 aIndex, PRBool aModifyIndex, nsIHistoryEntry** aResult)
 423 {
 424   nsresult rv;
 425   nsCOMPtr<nsISHEntry> shEntry;
 426   rv = GetEntryAtIndex(aIndex, aModifyIndex, getter_AddRefs(shEntry));
 427   if (NS_SUCCEEDED(rv) && shEntry)
 428     rv = CallQueryInterface(shEntry, aResult);
 429
 430   return rv;
 431 }
 432
 433 /* Get the transaction at a given index */
 434 NS_IMETHODIMP
 435 nsSHistory::GetTransactionAtIndex(PRInt32 aIndex, nsISHTransaction ** aResult)
 436 {
 437   nsresult rv;
 438   NS_ENSURE_ARG_POINTER(aResult);
 439
 440   if ((mLength <= 0) || (aIndex < 0) || (aIndex >= mLength))
 441     return NS_ERROR_FAILURE;
 442
 443   if (!mListRoot)
 444     return NS_ERROR_FAILURE;
 445
 446   if (aIndex == 0)
 447   {
 448     *aResult = mListRoot;
 449     NS_ADDREF(*aResult);
 450     return NS_OK;
 451   }
 452   PRInt32   cnt=0;
 453   nsCOMPtr<nsISHTransaction>  tempPtr;
 454
 455   rv = GetRootTransaction(getter_AddRefs(tempPtr));
 456   if (NS_FAILED(rv) || !tempPtr)
 457     return NS_ERROR_FAILURE;
 458
 459   while(1) {
 460     nsCOMPtr<nsISHTransaction> ptr;
 461     rv = tempPtr->GetNext(getter_AddRefs(ptr));
 462     if (NS_SUCCEEDED(rv) && ptr) {
 463       cnt++;
 464       if (cnt == aIndex) {
 465         *aResult = ptr;
 466         NS_ADDREF(*aResult);
 467         break;
 468       }
 469       else {
 470         tempPtr = ptr;
 471         continue;
 472       }
 473     }  //NS_SUCCEEDED
 474     else
 475       return NS_ERROR_FAILURE;
 476   }  // while
 477
 478   return NS_OK;
 479 }
 480
 481 #ifdef DEBUG
 482 nsresult
 483 nsSHistory::PrintHistory()
 484 {
 485
 486   nsCOMPtr<nsISHTransaction>   txn;
 487   PRInt32 index = 0;
 488   nsresult rv;
 489
 490   if (!mListRoot)
 491     return NS_ERROR_FAILURE;
 492
 493   txn = mListRoot;
 494
 495   while (1) {
 496     if (!txn)
 497       break;
 498     nsCOMPtr<nsISHEntry>  entry;
 499     rv = txn->GetSHEntry(getter_AddRefs(entry));
 500     if (NS_FAILED(rv) && !entry)
 501       return NS_ERROR_FAILURE;
 502
 503     nsCOMPtr<nsILayoutHistoryState> layoutHistoryState;
 504     nsCOMPtr<nsIURI>  uri;
 505     nsXPIDLString title;
 506
 507     entry->GetLayoutHistoryState(getter_AddRefs(layoutHistoryState));
 508     nsCOMPtr<nsIHistoryEntry> hEntry(do_QueryInterface(entry));
 509     if (hEntry) {
 510       hEntry->GetURI(getter_AddRefs(uri));
 511       hEntry->GetTitle(getter_Copies(title));
 512     }
 513
 514 #if 0
 515     nsCAutoString url;
 516     if (uri)
 517      uri->GetSpec(url);
 518
 519     printf("**** SH Transaction #%d, Entry = %x\n", index, entry.get());
 520     printf("\t\t URL = %s\n", url.get());
 521
 522     printf("\t\t Title = %s\n", NS_LossyConvertUTF16toASCII(title).get());
 523     printf("\t\t layout History Data = %x\n", layoutHistoryState.get());
 524 #endif
 525
 526     nsCOMPtr<nsISHTransaction> next;
 527     rv = txn->GetNext(getter_AddRefs(next));
 528     if (NS_SUCCEEDED(rv) && next) {
 529       txn = next;
 530       index++;
 531       continue;
 532     }
 533     else
 534       break;
 535   }
 536
 537   return NS_OK;
 538 }
 539 #endif
 540
 541
 542 NS_IMETHODIMP
 543 nsSHistory::GetRootTransaction(nsISHTransaction ** aResult)
 544 {
 545   NS_ENSURE_ARG_POINTER(aResult);
 546   *aResult=mListRoot;
 547   NS_IF_ADDREF(*aResult);
 548   return NS_OK;
 549 }
 550
 551 /* Get the max size of the history list */
 552 NS_IMETHODIMP
 553 nsSHistory::GetMaxLength(PRInt32 * aResult)
 554 {
 555   NS_ENSURE_ARG_POINTER(aResult);
 556   *aResult = gHistoryMaxSize;
 557   return NS_OK;
 558 }
 559
 560 /* Set the max size of the history list */
 561 NS_IMETHODIMP
 562 nsSHistory::SetMaxLength(PRInt32 aMaxSize)
 563 {
 564   if (aMaxSize < 0)
 565     return NS_ERROR_ILLEGAL_VALUE;
 566
 567   gHistoryMaxSize = aMaxSize;
 568   if (mLength > aMaxSize)
 569     PurgeHistory(mLength-aMaxSize);
 570   return NS_OK;
 571 }
 572
 573 NS_IMETHODIMP
 574 nsSHistory::PurgeHistory(PRInt32 aEntries)
 575 {
 576   if (mLength <= 0 || aEntries <= 0)
 577     return NS_ERROR_FAILURE;
 578
 579   aEntries = NS_MIN(aEntries, mLength);
 580
 581   PRBool purgeHistory = PR_TRUE;
 582   // Notify the listener about the history purge
 583   if (mListener) {
 584     nsCOMPtr<nsISHistoryListener> listener(do_QueryReferent(mListener));
 585     if (listener) {
 586       listener->OnHistoryPurge(aEntries, &purgeHistory);
 587     }
 588   }
 589
 590   if (!purgeHistory) {
 591     // Listener asked us not to purge
 592     return NS_SUCCESS_LOSS_OF_INSIGNIFICANT_DATA;
 593   }
 594
 595   PRInt32 cnt = 0;
 596   while (cnt < aEntries) {
 597     nsCOMPtr<nsISHTransaction> nextTxn;
 598     if (mListRoot) {
 599       mListRoot->GetNext(getter_AddRefs(nextTxn));
 600       mListRoot->SetNext(nsnull);
 601     }
 602     mListRoot = nextTxn;
 603     if (mListRoot) {
 604       mListRoot->SetPrev(nsnull);
 605     }
 606     cnt++;
 607   }
 608   mLength -= cnt;
 609   mIndex -= cnt;
 610
 611   // Now if we were not at the end of the history, mIndex could have
 612   // become far too negative.  If so, just set it to -1.
 613   if (mIndex < -1) {
 614     mIndex = -1;
 615   }
 616
 617   if (mRootDocShell)
 618     mRootDocShell->HistoryPurged(cnt);
 619
 620   return NS_OK;
 621 }
 622
 623
 624 NS_IMETHODIMP
 625 nsSHistory::AddSHistoryListener(nsISHistoryListener * aListener)
 626 {
 627   NS_ENSURE_ARG_POINTER(aListener);
 628
 629   // Check if the listener supports Weak Reference. This is a must.
 630   // This listener functionality is used by embedders and we want to
 631   // have the right ownership with who ever listens to SHistory
 632   nsWeakPtr listener = do_GetWeakReference(aListener);
 633   if (!listener) return NS_ERROR_FAILURE;
 634   mListener = listener;
 635   return NS_OK;
 636 }
 637
 638
 639 NS_IMETHODIMP
 640 nsSHistory::RemoveSHistoryListener(nsISHistoryListener * aListener)
 641 {
 642   // Make sure the listener that wants to be removed is the
 643   // one we have in store.
 644   nsWeakPtr listener = do_GetWeakReference(aListener);
 645   if (listener == mListener) {
 646     mListener = nsnull;
 647     return NS_OK;
 648   }
 649   return NS_ERROR_FAILURE;
 650 }
 651
 652
 653 /* Replace an entry in the History list at a particular index.
 654  * Do not update index or count.
 655  */
 656 NS_IMETHODIMP
 657 nsSHistory::ReplaceEntry(PRInt32 aIndex, nsISHEntry * aReplaceEntry)
 658 {
 659   NS_ENSURE_ARG(aReplaceEntry);
 660   nsresult rv;
 661   nsCOMPtr<nsISHTransaction> currentTxn;
 662
 663   if (!mListRoot) // Session History is not initialised.
 664     return NS_ERROR_FAILURE;
 665
 666   rv = GetTransactionAtIndex(aIndex, getter_AddRefs(currentTxn));
 667
 668   if(currentTxn)
 669   {
 670     // Set the replacement entry in the transaction
 671     rv = currentTxn->SetSHEntry(aReplaceEntry);
 672     rv = currentTxn->SetPersist(PR_TRUE);
 673   }
 674   return rv;
 675 }
 676
 677 /* Get a handle to the Session history listener */
 678 NS_IMETHODIMP
 679 nsSHistory::GetListener(nsISHistoryListener ** aListener)
 680 {
 681   NS_ENSURE_ARG_POINTER(aListener);
 682   if (mListener)
 683     CallQueryReferent(mListener.get(),  aListener);
 684   // Don't addref aListener. It is a weak pointer.
 685   return NS_OK;
 686 }
 687
 688 NS_IMETHODIMP
 689 nsSHistory::EvictContentViewers(PRInt32 aPreviousIndex, PRInt32 aIndex)
 690 {
 691   // Check our per SHistory object limit in the currently navigated SHistory
 692   EvictWindowContentViewers(aPreviousIndex, aIndex);
 693   // Check our total limit across all SHistory objects
 694   EvictGlobalContentViewer();
 695   return NS_OK;
 696 }
 697
 698 NS_IMETHODIMP
 699 nsSHistory::EvictAllContentViewers()
 700 {
 701   // XXXbz we don't actually do a good job of evicting things as we should, so
 702   // we might have viewers quite far from mIndex.  So just evict everything.
 703   EvictContentViewersInRange(0, mLength);
 704   return NS_OK;
 705 }
 706
 707
 708
 709 //*****************************************************************************
 710 //    nsSHistory: nsIWebNavigation
 711 //*****************************************************************************
 712
 713 NS_IMETHODIMP
 714 nsSHistory::GetCanGoBack(PRBool * aCanGoBack)
 715 {
 716   NS_ENSURE_ARG_POINTER(aCanGoBack);
 717   *aCanGoBack = PR_FALSE;
 718
 719   PRInt32 index = -1;
 720   NS_ENSURE_SUCCESS(GetIndex(&index), NS_ERROR_FAILURE);
 721   if(index > 0)
 722      *aCanGoBack = PR_TRUE;
 723
 724   return NS_OK;
 725 }
 726
 727 NS_IMETHODIMP
 728 nsSHistory::GetCanGoForward(PRBool * aCanGoForward)
 729 {
 730   NS_ENSURE_ARG_POINTER(aCanGoForward);
 731   *aCanGoForward = PR_FALSE;
 732
 733   PRInt32 index = -1;
 734   PRInt32 count = -1;
 735
 736   NS_ENSURE_SUCCESS(GetIndex(&index), NS_ERROR_FAILURE);
 737   NS_ENSURE_SUCCESS(GetCount(&count), NS_ERROR_FAILURE);
 738
 739   if((index >= 0) && (index < (count - 1)))
 740     *aCanGoForward = PR_TRUE;
 741
 742   return NS_OK;
 743 }
 744
 745 NS_IMETHODIMP
 746 nsSHistory::GoBack()
 747 {
 748   PRBool canGoBack = PR_FALSE;
 749
 750   GetCanGoBack(&canGoBack);
 751   if (!canGoBack)  // Can't go back
 752     return NS_ERROR_UNEXPECTED;
 753   return LoadEntry(mIndex-1, nsIDocShellLoadInfo::loadHistory, HIST_CMD_BACK);
 754 }
 755
 756
 757 NS_IMETHODIMP
 758 nsSHistory::GoForward()
 759 {
 760   PRBool canGoForward = PR_FALSE;
 761
 762   GetCanGoForward(&canGoForward);
 763   if (!canGoForward)  // Can't go forward
 764     return NS_ERROR_UNEXPECTED;
 765   return LoadEntry(mIndex+1, nsIDocShellLoadInfo::loadHistory, HIST_CMD_FORWARD);
 766 }
 767
 768 NS_IMETHODIMP
 769 nsSHistory::Reload(PRUint32 aReloadFlags)
 770 {
 771   nsresult rv;
 772   nsDocShellInfoLoadType loadType;
 773   if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_PROXY &&
 774       aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_CACHE)
 775   {
 776     loadType = nsIDocShellLoadInfo::loadReloadBypassProxyAndCache;
 777   }
 778   else if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_PROXY)
 779   {
 780     loadType = nsIDocShellLoadInfo::loadReloadBypassProxy;
 781   }
 782   else if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_BYPASS_CACHE)
 783   {
 784     loadType = nsIDocShellLoadInfo::loadReloadBypassCache;
 785   }
 786   else if (aReloadFlags & nsIWebNavigation::LOAD_FLAGS_CHARSET_CHANGE)
 787   {
 788     loadType = nsIDocShellLoadInfo::loadReloadCharsetChange;
 789   }
 790   else
 791   {
 792     loadType = nsIDocShellLoadInfo::loadReloadNormal;
 793   }
 794
 795   // Notify listeners
 796   PRBool canNavigate = PR_TRUE;
 797   if (mListener) {
 798     nsCOMPtr<nsISHistoryListener> listener(do_QueryReferent(mListener));
 799     // We are reloading. Send Reload notifications.
 800     // nsDocShellLoadFlagType is not public, where as nsIWebNavigation
 801     // is public. So send the reload notifications with the
 802     // nsIWebNavigation flags.
 803     if (listener) {
 804       nsCOMPtr<nsIURI> currentURI;
 805       rv = GetCurrentURI(getter_AddRefs(currentURI));
 806       listener->OnHistoryReload(currentURI, aReloadFlags, &canNavigate);
 807     }
 808   }
 809   if (!canNavigate)
 810     return NS_OK;
 811
 812   return LoadEntry(mIndex, loadType, HIST_CMD_RELOAD);
 813 }
 814
 815 NS_IMETHODIMP
 816 nsSHistory::ReloadCurrentEntry()
 817 {
 818   // Notify listeners
 819   PRBool canNavigate = PR_TRUE;
 820   if (mListener) {
 821     nsCOMPtr<nsISHistoryListener> listener(do_QueryReferent(mListener));
 822     if (listener) {
 823       nsCOMPtr<nsIURI> currentURI;
 824       GetCurrentURI(getter_AddRefs(currentURI));
 825       listener->OnHistoryGotoIndex(mIndex, currentURI, &canNavigate);
 826     }
 827   }
 828   if (!canNavigate)
 829     return NS_OK;
 830
 831   return LoadEntry(mIndex, nsIDocShellLoadInfo::loadHistory, HIST_CMD_RELOAD);
 832 }
 833
 834 void
 835 nsSHistory::EvictWindowContentViewers(PRInt32 aFromIndex, PRInt32 aToIndex)
 836 {
 837   // To enforce the per SHistory object limit on cached content viewers, we
 838   // need to release all of the content viewers that are no longer in the
 839   // "window" that now ends/begins at aToIndex.  Existing content viewers
 840   // should be in the window from
 841   // aFromIndex - gHistoryMaxViewers to aFromIndex + gHistoryMaxViewers
 842   //
 843   // We make the assumption that entries outside this range have no viewers so
 844   // that we don't have to walk the whole entire session history checking for
 845   // content viewers.
 846
 847   // This can happen on the first load of a page in a particular window
 848   if (aFromIndex < 0 || aToIndex < 0) {
 849     return;
 850   }
 851   NS_ASSERTION(aFromIndex < mLength, "aFromIndex is out of range");
 852   NS_ASSERTION(aToIndex < mLength, "aToIndex is out of range");
 853   if (aFromIndex >= mLength || aToIndex >= mLength) {
 854     return;
 855   }
 856
 857   // These indices give the range of SHEntries whose content viewers will be
 858   // evicted
 859   PRInt32 startIndex, endIndex;
 860   if (aToIndex > aFromIndex) { // going forward
 861     endIndex = aToIndex - gHistoryMaxViewers;
 862     if (endIndex <= 0) {
 863       return;
 864     }
 865     startIndex = NS_MAX(0, aFromIndex - gHistoryMaxViewers);
 866   } else { // going backward
 867     startIndex = aToIndex + gHistoryMaxViewers + 1;
 868     if (startIndex >= mLength) {
 869       return;
 870     }
 871     endIndex = NS_MIN(mLength, aFromIndex + gHistoryMaxViewers + 1);
 872   }
 873
 874 #ifdef DEBUG
 875   nsCOMPtr<nsISHTransaction> trans;
 876   GetTransactionAtIndex(0, getter_AddRefs(trans));
 877
 878   // Walk the full session history and check that entries outside the window
 879   // around aFromIndex have no content viewers
 880   for (PRInt32 i = 0; i < mLength; ++i) {
 881     if (i < aFromIndex - gHistoryMaxViewers ||
 882         i > aFromIndex + gHistoryMaxViewers) {
 883       nsCOMPtr<nsISHEntry> entry;
 884       trans->GetSHEntry(getter_AddRefs(entry));
 885       nsCOMPtr<nsIContentViewer> viewer;
 886       nsCOMPtr<nsISHEntry> ownerEntry;
 887       entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
 888                                  getter_AddRefs(viewer));
 889       NS_WARN_IF_FALSE(!viewer,
 890                        "ContentViewer exists outside gHistoryMaxViewer range");
 891     }
 892
 893     nsISHTransaction *temp = trans;
 894     temp->GetNext(getter_AddRefs(trans));
 895   }
 896 #endif
 897
 898   EvictContentViewersInRange(startIndex, endIndex);
 899 }
 900
 901 void
 902 nsSHistory::EvictContentViewersInRange(PRInt32 aStart, PRInt32 aEnd)
 903 {
 904   nsCOMPtr<nsISHTransaction> trans;
 905   GetTransactionAtIndex(aStart, getter_AddRefs(trans));
 906   if (!trans)
 907     return;
 908
 909   for (PRInt32 i = aStart; i < aEnd; ++i) {
 910     nsCOMPtr<nsISHEntry> entry;
 911     trans->GetSHEntry(getter_AddRefs(entry));
 912     nsCOMPtr<nsIContentViewer> viewer;
 913     nsCOMPtr<nsISHEntry> ownerEntry;
 914     entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
 915                                getter_AddRefs(viewer));
 916     if (viewer) {
 917       NS_ASSERTION(ownerEntry,
 918                    "ContentViewer exists but its SHEntry is null");
 919 #ifdef DEBUG_PAGE_CACHE
 920       nsCOMPtr<nsIURI> uri;
 921       ownerEntry->GetURI(getter_AddRefs(uri));
 922       nsCAutoString spec;
 923       if (uri)
 924         uri->GetSpec(spec);
 925
 926       printf("per SHistory limit: evicting content viewer: %s\n", spec.get());
 927 #endif
 928
 929       // Drop the presentation state before destroying the viewer, so that
 930       // document teardown is able to correctly persist the state.
 931       ownerEntry->SetContentViewer(nsnull);
 932       ownerEntry->SyncPresentationState();
 933       viewer->Destroy();
 934     }
 935
 936     nsISHTransaction *temp = trans;
 937     temp->GetNext(getter_AddRefs(trans));
 938   }
 939 }
 940
 941 // static
 942 void
 943 nsSHistory::EvictGlobalContentViewer()
 944 {
 945   // true until the total number of content viewers is <= total max
 946   // The usual case is that we only need to evict one content viewer.
 947   // However, if somebody resets the pref value, we might occasionally
 948   // need to evict more than one.
 949   PRBool shouldTryEviction = PR_TRUE;
 950   while (shouldTryEviction) {
 951     // Walk through our list of SHistory objects, looking for content
 952     // viewers in the possible active window of all of the SHEntry objects.
 953     // Keep track of the SHEntry object that has a ContentViewer and is
 954     // farthest from the current focus in any SHistory object.  The
 955     // ContentViewer associated with that SHEntry will be evicted
 956     PRInt32 distanceFromFocus = 0;
 957     PRUint32 candidateLastTouched = 0;
 958     nsCOMPtr<nsISHEntry> evictFromSHE;
 959     nsCOMPtr<nsIContentViewer> evictViewer;
 960     PRInt32 totalContentViewers = 0;
 961     nsSHistory* shist = static_cast<nsSHistory*>
 962                                    (PR_LIST_HEAD(&gSHistoryList));
 963     while (shist != &gSHistoryList) {
 964       // Calculate the window of SHEntries that could possibly have a content
 965       // viewer.  There could be up to gHistoryMaxViewers content viewers,
 966       // but we don't know whether they are before or after the mIndex position
 967       // in the SHEntry list.  Just check both sides, to be safe.
 968       PRInt32 startIndex = NS_MAX(0, shist->mIndex - gHistoryMaxViewers);
 969       PRInt32 endIndex = NS_MIN(shist->mLength - 1,
 970                                 shist->mIndex + gHistoryMaxViewers);
 971       nsCOMPtr<nsISHTransaction> trans;
 972       shist->GetTransactionAtIndex(startIndex, getter_AddRefs(trans));
 973
 974       if (!trans) {
 975         shist = static_cast<nsSHistory*>(PR_NEXT_LINK(shist));
 976         continue;
 977       }
 978
 979       for (PRInt32 i = startIndex; i <= endIndex; ++i) {
 980         nsCOMPtr<nsISHEntry> entry;
 981         trans->GetSHEntry(getter_AddRefs(entry));
 982         nsCOMPtr<nsIContentViewer> viewer;
 983         nsCOMPtr<nsISHEntry> ownerEntry;
 984         entry->GetAnyContentViewer(getter_AddRefs(ownerEntry),
 985                                    getter_AddRefs(viewer));
 986
 987         PRUint32 entryLastTouched = 0;
 988         if (gOptimizeEviction) {
 989           nsCOMPtr<nsISHEntryInternal> entryInternal = do_QueryInterface(entry);
 990           if (entryInternal) {
 991             // Find when this entry was last activated
 992             entryInternal->GetLastTouched(&entryLastTouched);
 993           }
 994         }
 995
 996 #ifdef DEBUG_PAGE_CACHE
 997         nsCOMPtr<nsIURI> uri;
 998         if (ownerEntry) {
 999           ownerEntry->GetURI(getter_AddRefs(uri));
1000         } else {
1001           entry->GetURI(getter_AddRefs(uri));
1002         }
1003         nsCAutoString spec;
1004         if (uri) {
1005           uri->GetSpec(spec);
1006           printf("Considering for eviction: %s\n", spec.get());
1007         }
1008 #endif
1009
1010         // This SHEntry has a ContentViewer, so check how far away it is from
1011         // the currently used SHEntry within this SHistory object
1012         if (viewer) {
1013           PRInt32 distance = PR_ABS(shist->mIndex - i);
1014
1015 #ifdef DEBUG_PAGE_CACHE
1016           printf("Has a cached content viewer: %s\n", spec.get());
1017           printf("mIndex: %d i: %d\n", shist->mIndex, i);
1018 #endif
1019           totalContentViewers++;
1020
1021           // If this entry is further away from focus than any previously found
1022           // or at the same distance but it is longer time since it was activated
1023           // then take this entry as the new candiate for eviction
1024           if (distance > distanceFromFocus || (distance == distanceFromFocus && candidateLastTouched > entryLastTouched)) {
1025
1026 #ifdef DEBUG_PAGE_CACHE
1027             printf("Choosing as new eviction candidate: %s\n", spec.get());
1028 #endif
1029             candidateLastTouched = entryLastTouched;
1030             distanceFromFocus = distance;
1031             evictFromSHE = ownerEntry;
1032             evictViewer = viewer;
1033           }
1034         }
1035         nsISHTransaction* temp = trans;
1036         temp->GetNext(getter_AddRefs(trans));
1037       }
1038       shist = static_cast<nsSHistory*>(PR_NEXT_LINK(shist));
1039     }
1040
1041 #ifdef DEBUG_PAGE_CACHE
1042     printf("Distance from focus: %d\n", distanceFromFocus);
1043     printf("Total max viewers: %d\n", sHistoryMaxTotalViewers);
1044     printf("Total number of viewers: %d\n", totalContentViewers);
1045 #endif
1046
1047     if (totalContentViewers > sHistoryMaxTotalViewers && evictViewer) {
1048 #ifdef DEBUG_PAGE_CACHE
1049       nsCOMPtr<nsIURI> uri;
1050       evictFromSHE->GetURI(getter_AddRefs(uri));
1051       nsCAutoString spec;
1052       if (uri) {
1053         uri->GetSpec(spec);
1054         printf("Evicting content viewer: %s\n", spec.get());
1055       }
1056 #endif
1057
1058       // Drop the presentation state before destroying the viewer, so that
1059       // document teardown is able to correctly persist the state.
1060       evictFromSHE->SetContentViewer(nsnull);
1061       evictFromSHE->SyncPresentationState();
1062       evictViewer->Destroy();
1063
1064       // If we only needed to evict one content viewer, then we are done.
1065       // Otherwise, continue evicting until we reach the max total limit.
1066       if (totalContentViewers - sHistoryMaxTotalViewers == 1) {
1067         shouldTryEviction = PR_FALSE;
1068       }
1069     } else {
1070       // couldn't find a content viewer to evict, so we are done
1071       shouldTryEviction = PR_FALSE;
1072     }
1073   }  // while shouldTryEviction
1074 }
1075
1076 NS_IMETHODIMP
1077 nsSHistory::EvictExpiredContentViewerForEntry(nsISHEntry *aEntry)
1078 {
1079   PRInt32 startIndex = NS_MAX(0, mIndex - gHistoryMaxViewers);
1080   PRInt32 endIndex = NS_MIN(mLength - 1,
1081                             mIndex + gHistoryMaxViewers);
1082   nsCOMPtr<nsISHTransaction> trans;
1083   GetTransactionAtIndex(startIndex, getter_AddRefs(trans));
1084
1085   PRInt32 i;
1086   for (i = startIndex; i <= endIndex; ++i) {
1087     nsCOMPtr<nsISHEntry> entry;
1088     trans->GetSHEntry(getter_AddRefs(entry));
1089     if (entry == aEntry)
1090       break;
1091
1092     nsISHTransaction *temp = trans;
1093     temp->GetNext(getter_AddRefs(trans));
1094   }
1095   if (i > endIndex)
1096     return NS_OK;
1097
1098   NS_ASSERTION(i != mIndex, "How did the current session entry expire?");
1099   if (i == mIndex)
1100     return NS_OK;
1101
1102   // We evict content viewers for the expired entry and any other entries that
1103   // we would have to go through the expired entry to get to (i.e. the entries
1104   // that have the expired entry between them and the current entry). Those
1105   // other entries should have timed out already, actually, but this is just
1106   // to be on the safe side.
1107   if (i < mIndex) {
1108     EvictContentViewersInRange(startIndex, i + 1);
1109   } else {
1110     EvictContentViewersInRange(i, endIndex + 1);
1111   }
1112
1113   return NS_OK;
1114 }
1115
1116 // Evicts all content viewers in all history objects.  This is very
1117 // inefficient, because it requires a linear search through all SHistory
1118 // objects for each viewer to be evicted.  However, this method is called
1119 // infrequently -- only when the disk or memory cache is cleared.
1120
1121 //static
1122 void
1123 nsSHistory::EvictAllContentViewersGlobally()
1124 {
1125   PRInt32 maxViewers = sHistoryMaxTotalViewers;
1126   sHistoryMaxTotalViewers = 0;
1127   EvictGlobalContentViewer();
1128   sHistoryMaxTotalViewers = maxViewers;
1129 }
1130
1131 void GetDynamicChildren(nsISHContainer* aContainer,
1132                         nsTArray<PRUint64>& aDocshellIDs,
1133                         PRBool aOnlyTopLevelDynamic)
1134 {
1135   PRInt32 count = 0;
1136   aContainer->GetChildCount(&count);
1137   for (PRInt32 i = 0; i < count; ++i) {
1138     nsCOMPtr<nsISHEntry> child;
1139     aContainer->GetChildAt(i, getter_AddRefs(child));
1140     if (child) {
1141       PRBool dynAdded = PR_FALSE;
1142       child->IsDynamicallyAdded(&dynAdded);
1143       if (dynAdded) {
1144         PRUint64 docshellID = 0;
1145         child->GetDocshellID(&docshellID);
1146         aDocshellIDs.AppendElement(docshellID);
1147       }
1148       if (!dynAdded || !aOnlyTopLevelDynamic) {
1149         nsCOMPtr<nsISHContainer> childAsContainer = do_QueryInterface(child);
1150         if (childAsContainer) {
1151           GetDynamicChildren(childAsContainer, aDocshellIDs,
1152                              aOnlyTopLevelDynamic);
1153         }
1154       }
1155     }
1156   }
1157 }
1158
1159 PRBool
1160 RemoveFromSessionHistoryContainer(nsISHContainer* aContainer,
1161                                   nsTArray<PRUint64>& aDocshellIDs)
1162 {
1163   nsCOMPtr<nsISHEntry> root = do_QueryInterface(aContainer);
1164   NS_ENSURE_TRUE(root, PR_FALSE);
1165
1166   PRBool didRemove = PR_FALSE;
1167   PRInt32 childCount = 0;
1168   aContainer->GetChildCount(&childCount);
1169   for (PRInt32 i = childCount - 1; i >= 0; --i) {
1170     nsCOMPtr<nsISHEntry> child;
1171     aContainer->GetChildAt(i, getter_AddRefs(child));
1172     if (child) {
1173       PRUint64 docshelldID = 0;
1174       child->GetDocshellID(&docshelldID);
1175       if (aDocshellIDs.Contains(docshelldID)) {
1176         didRemove = PR_TRUE;
1177         aContainer->RemoveChild(child);
1178       } else {
1179         nsCOMPtr<nsISHContainer> container = do_QueryInterface(child);
1180         if (container) {
1181           PRBool childRemoved =
1182             RemoveFromSessionHistoryContainer(container, aDocshellIDs);
1183           if (childRemoved) {
1184             didRemove = PR_TRUE;
1185           }
1186         }
1187       }
1188     }
1189   }
1190   return didRemove;
1191 }
1192
1193 PRBool RemoveChildEntries(nsISHistory* aHistory, PRInt32 aIndex,
1194                           nsTArray<PRUint64>& aEntryIDs)
1195 {
1196   nsCOMPtr<nsIHistoryEntry> rootHE;
1197   aHistory->GetEntryAtIndex(aIndex, PR_FALSE, getter_AddRefs(rootHE));
1198   nsCOMPtr<nsISHContainer> root = do_QueryInterface(rootHE);
1199   return root ? RemoveFromSessionHistoryContainer(root, aEntryIDs) : PR_FALSE;
1200 }
1201
1202 PRBool IsSameTree(nsISHEntry* aEntry1, nsISHEntry* aEntry2)
1203 {
1204   if (!aEntry1 && !aEntry2) {
1205     return PR_TRUE;
1206   }
1207   if ((!aEntry1 && aEntry2) || (aEntry1 && !aEntry2)) {
1208     return PR_FALSE;
1209   }
1210   PRUint32 id1, id2;
1211   aEntry1->GetID(&id1);
1212   aEntry2->GetID(&id2);
1213   if (id1 != id2) {
1214     return PR_FALSE;
1215   }
1216
1217   nsCOMPtr<nsISHContainer> container1 = do_QueryInterface(aEntry1);
1218   nsCOMPtr<nsISHContainer> container2 = do_QueryInterface(aEntry2);
1219   PRInt32 count1, count2;
1220   container1->GetChildCount(&count1);
1221   container2->GetChildCount(&count2);
1222   // We allow null entries in the end of the child list.
1223   PRInt32 count = PR_MAX(count1, count2);
1224   for (PRInt32 i = 0; i < count; ++i) {
1225     nsCOMPtr<nsISHEntry> child1, child2;
1226     container1->GetChildAt(i, getter_AddRefs(child1));
1227     container2->GetChildAt(i, getter_AddRefs(child2));
1228     if (!IsSameTree(child1, child2)) {
1229       return PR_FALSE;
1230     }
1231   }
1232
1233   return PR_TRUE;
1234 }
1235
1236 PRBool
1237 nsSHistory::RemoveDuplicate(PRInt32 aIndex, PRBool aKeepNext)
1238 {
1239   NS_ASSERTION(aIndex >= 0, "aIndex must be >= 0!");
1240   NS_ASSERTION(aIndex != mIndex, "Shouldn't remove mIndex!");
1241   PRInt32 compareIndex = aKeepNext ? aIndex + 1 : aIndex - 1;
1242   nsCOMPtr<nsIHistoryEntry> rootHE1, rootHE2;
1243   GetEntryAtIndex(aIndex, PR_FALSE, getter_AddRefs(rootHE1));
1244   GetEntryAtIndex(compareIndex, PR_FALSE, getter_AddRefs(rootHE2));
1245   nsCOMPtr<nsISHEntry> root1 = do_QueryInterface(rootHE1);
1246   nsCOMPtr<nsISHEntry> root2 = do_QueryInterface(rootHE2);
1247   if (IsSameTree(root1, root2)) {
1248     nsCOMPtr<nsISHTransaction> txToRemove, txToKeep, txNext, txPrev;
1249     GetTransactionAtIndex(aIndex, getter_AddRefs(txToRemove));
1250     GetTransactionAtIndex(compareIndex, getter_AddRefs(txToKeep));
1251     NS_ENSURE_TRUE(txToRemove, PR_FALSE);
1252     NS_ENSURE_TRUE(txToKeep, PR_FALSE);
1253     txToRemove->GetNext(getter_AddRefs(txNext));
1254     txToRemove->GetPrev(getter_AddRefs(txPrev));
1255     txToRemove->SetNext(nsnull);
1256     txToRemove->SetPrev(nsnull);
1257     if (aKeepNext) {
1258       if (txPrev) {
1259         txPrev->SetNext(txToKeep);
1260       } else {
1261         txToKeep->SetPrev(nsnull);
1262       }
1263     } else {
1264       txToKeep->SetNext(txNext);
1265     }
1266
1267     if (aIndex == 0 && aKeepNext) {
1268       NS_ASSERTION(txToRemove == mListRoot,
1269                    "Transaction at index 0 should be mListRoot!");
1270       // We're removing the very first session history transaction!
1271       mListRoot = txToKeep;
1272     }
1273     if (mRootDocShell) {
1274       static_cast<nsDocShell*>(mRootDocShell)->HistoryTransactionRemoved(aIndex);
1275     }
1276     if (mIndex > aIndex) {
1277       mIndex = mIndex - 1;
1278     }
1279     --mLength;
1280     return PR_TRUE;
1281   }
1282   return PR_FALSE;
1283 }
1284
1285 NS_IMETHODIMP_(void)
1286 nsSHistory::RemoveEntries(nsTArray<PRUint64>& aIDs, PRInt32 aStartIndex)
1287 {
1288   PRInt32 index = aStartIndex;
1289   while(index >= 0 && RemoveChildEntries(this, --index, aIDs));
1290   PRInt32 minIndex = index;
1291   index = aStartIndex;
1292   while(index >= 0 && RemoveChildEntries(this, index++, aIDs));
1293
1294   // We need to remove duplicate nsSHEntry trees.
1295   PRBool didRemove = PR_FALSE;
1296   while (index > minIndex) {
1297     if (index != mIndex) {
1298       didRemove = RemoveDuplicate(index, index < mIndex) || didRemove;
1299     }
1300     --index;
1301   }
1302   if (didRemove && mRootDocShell) {
1303     nsRefPtr<nsIRunnable> ev =
1304       NS_NewRunnableMethod(static_cast<nsDocShell*>(mRootDocShell),
1305                            &nsDocShell::FireDummyOnLocationChange);
1306     NS_DispatchToCurrentThread(ev);
1307   }
1308 }
1309
1310 void
1311 nsSHistory::RemoveDynEntries(PRInt32 aOldIndex, PRInt32 aNewIndex)
1312 {
1313   // Search for the entries which are in the current index,
1314   // but not in the new one.
1315   nsCOMPtr<nsISHEntry> originalSH;
1316   GetEntryAtIndex(aOldIndex, PR_FALSE, getter_AddRefs(originalSH));
1317   nsCOMPtr<nsISHContainer> originalContainer = do_QueryInterface(originalSH);
1318   nsAutoTArray<PRUint64, 16> toBeRemovedEntries;
1319   if (originalContainer) {
1320     nsTArray<PRUint64> originalDynDocShellIDs;
1321     GetDynamicChildren(originalContainer, originalDynDocShellIDs, PR_TRUE);
1322     if (originalDynDocShellIDs.Length()) {
1323       nsCOMPtr<nsISHEntry> currentSH;
1324       GetEntryAtIndex(aNewIndex, PR_FALSE, getter_AddRefs(currentSH));
1325       nsCOMPtr<nsISHContainer> newContainer = do_QueryInterface(currentSH);
1326       if (newContainer) {
1327         nsTArray<PRUint64> newDynDocShellIDs;
1328         GetDynamicChildren(newContainer, newDynDocShellIDs, PR_FALSE);
1329         for (PRUint32 i = 0; i < originalDynDocShellIDs.Length(); ++i) {
1330           if (!newDynDocShellIDs.Contains(originalDynDocShellIDs[i])) {
1331             toBeRemovedEntries.AppendElement(originalDynDocShellIDs[i]);
1332           }
1333         }
1334       }
1335     }
1336   }
1337   if (toBeRemovedEntries.Length()) {
1338     RemoveEntries(toBeRemovedEntries, aOldIndex);
1339   }
1340 }
1341
1342 NS_IMETHODIMP
1343 nsSHistory::UpdateIndex()
1344 {
1345   // Update the actual index with the right value.
1346   if (mIndex != mRequestedIndex && mRequestedIndex != -1) {
1347     RemoveDynEntries(mIndex, mRequestedIndex);
1348     mIndex = mRequestedIndex;
1349   }
1350
1351   mRequestedIndex = -1;
1352   return NS_OK;
1353 }
1354
1355 NS_IMETHODIMP
1356 nsSHistory::Stop(PRUint32 aStopFlags)
1357 {
1358   //Not implemented
1359   return NS_OK;
1360 }
1361
1362
1363 NS_IMETHODIMP
1364 nsSHistory::GetDocument(nsIDOMDocument** aDocument)
1365 {
1366   // Not implemented
1367   return NS_OK;
1368 }
1369
1370
1371 NS_IMETHODIMP
1372 nsSHistory::GetCurrentURI(nsIURI** aResultURI)
1373 {
1374   NS_ENSURE_ARG_POINTER(aResultURI);
1375   nsresult rv;
1376
1377   nsCOMPtr<nsIHistoryEntry> currentEntry;
1378   rv = GetEntryAtIndex(mIndex, PR_FALSE, getter_AddRefs(currentEntry));
1379   if (NS_FAILED(rv) && !currentEntry) return rv;
1380   rv = currentEntry->GetURI(aResultURI);
1381   return rv;
1382 }
1383
1384
1385 NS_IMETHODIMP
1386 nsSHistory::GetReferringURI(nsIURI** aURI)
1387 {
1388   *aURI = nsnull;
1389   // Not implemented
1390   return NS_OK;
1391 }
1392
1393
1394 NS_IMETHODIMP
1395 nsSHistory::SetSessionHistory(nsISHistory* aSessionHistory)
1396 {
1397   // Not implemented
1398   return NS_OK;
1399 }
1400
1401
1402 NS_IMETHODIMP
1403 nsSHistory::GetSessionHistory(nsISHistory** aSessionHistory)
1404 {
1405   // Not implemented
1406   return NS_OK;
1407 }
1408
1409
1410 NS_IMETHODIMP
1411 nsSHistory::LoadURI(const PRUnichar* aURI,
1412                     PRUint32 aLoadFlags,
1413                     nsIURI* aReferringURI,
1414                     nsIInputStream* aPostStream,
1415                     nsIInputStream* aExtraHeaderStream)
1416 {
1417   return NS_OK;
1418 }
1419
1420 NS_IMETHODIMP
1421 nsSHistory::GotoIndex(PRInt32 aIndex)
1422 {
1423   return LoadEntry(aIndex, nsIDocShellLoadInfo::loadHistory, HIST_CMD_GOTOINDEX);
1424 }
1425
1426 nsresult
1427 nsSHistory::LoadNextPossibleEntry(PRInt32 aNewIndex, long aLoadType, PRUint32 aHistCmd)
1428 {
1429   mRequestedIndex = -1;
1430   if (aNewIndex < mIndex) {
1431     return LoadEntry(aNewIndex - 1, aLoadType, aHistCmd);
1432   }
1433   if (aNewIndex > mIndex) {
1434     return LoadEntry(aNewIndex + 1, aLoadType, aHistCmd);
1435   }
1436   return NS_ERROR_FAILURE;
1437 }
1438
1439 NS_IMETHODIMP
1440 nsSHistory::LoadEntry(PRInt32 aIndex, long aLoadType, PRUint32 aHistCmd)
1441 {
1442   nsCOMPtr<nsIDocShell> docShell;
1443   // Keep note of requested history index in mRequestedIndex.
1444   mRequestedIndex = aIndex;
1445
1446   nsCOMPtr<nsISHEntry> prevEntry;
1447   GetEntryAtIndex(mIndex, PR_FALSE, getter_AddRefs(prevEntry));
1448
1449   nsCOMPtr<nsISHEntry> nextEntry;
1450   GetEntryAtIndex(mRequestedIndex, PR_FALSE, getter_AddRefs(nextEntry));
1451   nsCOMPtr<nsIHistoryEntry> nHEntry(do_QueryInterface(nextEntry));
1452   if (!nextEntry || !prevEntry || !nHEntry) {
1453     mRequestedIndex = -1;
1454     return NS_ERROR_FAILURE;
1455   }
1456
1457   // Remember that this entry is getting loaded at this point in the sequence
1458   nsCOMPtr<nsISHEntryInternal> entryInternal = do_QueryInterface(nextEntry);
1459
1460   if (entryInternal) {
1461     entryInternal->SetLastTouched(++gTouchCounter);
1462   }
1463
1464   // Send appropriate listener notifications
1465   PRBool canNavigate = PR_TRUE;
1466   // Get the uri for the entry we are about to visit
1467   nsCOMPtr<nsIURI> nextURI;
1468   nHEntry->GetURI(getter_AddRefs(nextURI));
1469
1470   if(mListener) {
1471     nsCOMPtr<nsISHistoryListener> listener(do_QueryReferent(mListener));
1472     if (listener) {
1473       if (aHistCmd == HIST_CMD_BACK) {
1474         // We are going back one entry. Send GoBack notifications
1475         listener->OnHistoryGoBack(nextURI, &canNavigate);
1476       }
1477       else if (aHistCmd == HIST_CMD_FORWARD) {
1478         // We are going forward. Send GoForward notification
1479         listener->OnHistoryGoForward(nextURI, &canNavigate);
1480       }
1481       else if (aHistCmd == HIST_CMD_GOTOINDEX) {
1482         // We are going somewhere else. This is not reload either
1483         listener->OnHistoryGotoIndex(aIndex, nextURI, &canNavigate);
1484       }
1485     }
1486   }
1487
1488   if (!canNavigate) {
1489     // If the listener asked us not to proceed with
1490     // the operation, simply return.
1491     return NS_OK;  // XXX Maybe I can return some other error code?
1492   }
1493
1494   nsCOMPtr<nsIURI> nexturi;
1495   PRInt32 pCount=0, nCount=0;
1496   nsCOMPtr<nsISHContainer> prevAsContainer(do_QueryInterface(prevEntry));
1497   nsCOMPtr<nsISHContainer> nextAsContainer(do_QueryInterface(nextEntry));
1498   if (prevAsContainer && nextAsContainer) {
1499     prevAsContainer->GetChildCount(&pCount);
1500     nextAsContainer->GetChildCount(&nCount);
1501   }
1502
1503   nsCOMPtr<nsIDocShellLoadInfo> loadInfo;
1504   if (mRequestedIndex == mIndex) {
1505     // Possibly a reload case
1506     docShell = mRootDocShell;
1507   }
1508   else {
1509     // Going back or forward.
1510     if ((pCount > 0) && (nCount > 0)) {
1511       /* THis is a subframe navigation. Go find
1512        * the docshell in which load should happen
1513        */
1514       PRBool frameFound = PR_FALSE;
1515       nsresult rv = CompareFrames(prevEntry, nextEntry, mRootDocShell, aLoadType, &frameFound);
1516       if (!frameFound) {
1517         // We did not successfully find the subframe in which
1518         // the new url was to be loaded. Go further in the history.
1519         return LoadNextPossibleEntry(aIndex, aLoadType, aHistCmd);
1520       }
1521       return rv;
1522     }   // (pCount >0)
1523     else {
1524       // Loading top level page.
1525       PRUint32 prevID = 0;
1526       PRUint32 nextID = 0;
1527       prevEntry->GetID(&prevID);
1528       nextEntry->GetID(&nextID);
1529       if (prevID == nextID) {
1530         // Try harder to find something new to load.
1531         // This may happen for example if some page removed iframes dynamically.
1532         return LoadNextPossibleEntry(aIndex, aLoadType, aHistCmd);
1533       }
1534       docShell = mRootDocShell;
1535     }
1536   }
1537
1538   if (!docShell) {
1539     // we did not successfully go to the proper index.
1540     // return error.
1541     mRequestedIndex = -1;
1542     return NS_ERROR_FAILURE;
1543   }
1544
1545   // Start the load on the appropriate docshell
1546   return InitiateLoad(nextEntry, docShell, aLoadType);
1547 }
1548
1549 nsresult
1550 nsSHistory::CompareFrames(nsISHEntry * aPrevEntry, nsISHEntry * aNextEntry, nsIDocShell * aParent, long aLoadType, PRBool * aIsFrameFound)
1551 {
1552   if (!aPrevEntry || !aNextEntry || !aParent)
1553     return NS_ERROR_FAILURE;
1554
1555   // We should be comparing only entries which were created for the
1556   // same docshell. This is here to just prevent anything strange happening.
1557   // This check could be possibly an assertion.
1558   PRUint64 prevdID, nextdID;
1559   aPrevEntry->GetDocshellID(&prevdID);
1560   aNextEntry->GetDocshellID(&nextdID);
1561   NS_ENSURE_STATE(prevdID == nextdID);
1562
1563   nsresult result = NS_OK;
1564   PRUint32 prevID, nextID;
1565
1566   aPrevEntry->GetID(&prevID);
1567   aNextEntry->GetID(&nextID);
1568
1569   // Check the IDs to verify if the pages are different.
1570   if (prevID != nextID) {
1571     if (aIsFrameFound)
1572       *aIsFrameFound = PR_TRUE;
1573     // Set the Subframe flag of the entry to indicate that
1574     // it is subframe navigation
1575     aNextEntry->SetIsSubFrame(PR_TRUE);
1576     InitiateLoad(aNextEntry, aParent, aLoadType);
1577     return NS_OK;
1578   }
1579
1580   /* The root entries are the same, so compare any child frames */
1581   PRInt32 pcnt=0, ncnt=0, dsCount=0;
1582   nsCOMPtr<nsISHContainer>  prevContainer(do_QueryInterface(aPrevEntry));
1583   nsCOMPtr<nsISHContainer>  nextContainer(do_QueryInterface(aNextEntry));
1584   nsCOMPtr<nsIDocShellTreeNode> dsTreeNode(do_QueryInterface(aParent));
1585
1586   if (!dsTreeNode)
1587     return NS_ERROR_FAILURE;
1588   if (!prevContainer || !nextContainer)
1589     return NS_ERROR_FAILURE;
1590
1591   prevContainer->GetChildCount(&pcnt);
1592   nextContainer->GetChildCount(&ncnt);
1593   dsTreeNode->GetChildCount(&dsCount);
1594
1595   // Create an array for child docshells.
1596   nsCOMArray<nsIDocShell> docshells;
1597   for (PRInt32 i = 0; i < dsCount; ++i) {
1598     nsCOMPtr<nsIDocShellTreeItem> treeItem;
1599     dsTreeNode->GetChildAt(i, getter_AddRefs(treeItem));
1600     nsCOMPtr<nsIDocShell> shell = do_QueryInterface(treeItem);
1601     if (shell) {
1602       docshells.AppendObject(shell);
1603     }
1604   }
1605
1606   // Search for something to load next.
1607   for (PRInt32 i = 0; i < ncnt; ++i) {
1608     // First get an entry which may cause a new page to be loaded.
1609     nsCOMPtr<nsISHEntry> nChild;
1610     nextContainer->GetChildAt(i, getter_AddRefs(nChild));
1611     if (!nChild) {
1612       continue;
1613     }
1614     PRUint64 docshellID = 0;
1615     nChild->GetDocshellID(&docshellID);
1616
1617     // Then find the associated docshell.
1618     nsIDocShell* dsChild = nsnull;
1619     PRInt32 count = docshells.Count();
1620     for (PRInt32 j = 0; j < count; ++j) {
1621       PRUint64 shellID = 0;
1622       nsIDocShell* shell = docshells[j];
1623       shell->GetHistoryID(&shellID);
1624       if (shellID == docshellID) {
1625         dsChild = shell;
1626         break;
1627       }
1628     }
1629     if (!dsChild) {
1630       continue;
1631     }
1632
1633     // Then look at the previous entries to see if there was
1634     // an entry for the docshell.
1635     nsCOMPtr<nsISHEntry> pChild;
1636     for (PRInt32 k = 0; k < pcnt; ++k) {
1637       nsCOMPtr<nsISHEntry> child;
1638       prevContainer->GetChildAt(k, getter_AddRefs(child));
1639       if (child) {
1640         PRUint64 dID = 0;
1641         child->GetDocshellID(&dID);
1642         if (dID == docshellID) {
1643           pChild = child;
1644           break;
1645         }
1646       }
1647     }
1648
1649     // Finally recursively call this method.
1650     // This will either load a new page to shell or some subshell or
1651     // do nothing.
1652     CompareFrames(pChild, nChild, dsChild, aLoadType, aIsFrameFound);
1653   }
1654   return result;
1655 }
1656
1657
1658 nsresult
1659 nsSHistory::InitiateLoad(nsISHEntry * aFrameEntry, nsIDocShell * aFrameDS, long aLoadType)
1660 {
1661   NS_ENSURE_STATE(aFrameDS && aFrameEntry);
1662
1663   nsCOMPtr<nsIDocShellLoadInfo> loadInfo;
1664
1665   /* Set the loadType in the SHEntry too to  what was passed on.
1666    * This will be passed on to child subframes later in nsDocShell,
1667    * so that proper loadType is maintained through out a frameset
1668    */
1669   aFrameEntry->SetLoadType(aLoadType);
1670   aFrameDS->CreateLoadInfo (getter_AddRefs(loadInfo));
1671
1672   loadInfo->SetLoadType(aLoadType);
1673   loadInfo->SetSHEntry(aFrameEntry);
1674
1675   nsCOMPtr<nsIURI> nextURI;
1676   nsCOMPtr<nsIHistoryEntry> hEntry(do_QueryInterface(aFrameEntry));
1677   hEntry->GetURI(getter_AddRefs(nextURI));
1678   // Time   to initiate a document load
1679   return aFrameDS->LoadURI(nextURI, loadInfo, nsIWebNavigation::LOAD_FLAGS_NONE, PR_FALSE);
1680
1681 }
1682
1683
1684
1685 NS_IMETHODIMP
1686 nsSHistory::SetRootDocShell(nsIDocShell * aDocShell)
1687 {
1688   mRootDocShell = aDocShell;
1689   return NS_OK;
1690 }
1691
1692 NS_IMETHODIMP
1693 nsSHistory::GetRootDocShell(nsIDocShell ** aDocShell)
1694 {
1695   NS_ENSURE_ARG_POINTER(aDocShell);
1696
1697   *aDocShell = mRootDocShell;
1698   //Not refcounted. May this method should not be available for public
1699   // NS_IF_ADDREF(*aDocShell);
1700   return NS_OK;
1701 }
1702
1703
1704 NS_IMETHODIMP
1705 nsSHistory::GetSHistoryEnumerator(nsISimpleEnumerator** aEnumerator)
1706 {
1707   nsresult status = NS_OK;
1708
1709   NS_ENSURE_ARG_POINTER(aEnumerator);
1710   nsSHEnumerator * iterator = new nsSHEnumerator(this);
1711   if (iterator && NS_FAILED(status = CallQueryInterface(iterator, aEnumerator)))
1712     delete iterator;
1713   return status;
1714 }
1715
1716
1717 //*****************************************************************************
1718 //***    nsSHEnumerator: Object Management
1719 //*****************************************************************************
1720
1721 nsSHEnumerator::nsSHEnumerator(nsSHistory * aSHistory):mIndex(-1)
1722 {
1723   mSHistory = aSHistory;
1724 }
1725
1726 nsSHEnumerator::~nsSHEnumerator()
1727 {
1728   mSHistory = nsnull;
1729 }
1730
1731 NS_IMPL_ISUPPORTS1(nsSHEnumerator, nsISimpleEnumerator)
1732
1733 NS_IMETHODIMP
1734 nsSHEnumerator::HasMoreElements(PRBool * aReturn)
1735 {
1736   PRInt32 cnt;
1737   *aReturn = PR_FALSE;
1738   mSHistory->GetCount(&cnt);
1739   if (mIndex >= -1 && mIndex < (cnt-1) ) {
1740     *aReturn = PR_TRUE;
1741   }
1742   return NS_OK;
1743 }
1744
1745
1746 NS_IMETHODIMP
1747 nsSHEnumerator::GetNext(nsISupports **aItem)
1748 {
1749   NS_ENSURE_ARG_POINTER(aItem);
1750   PRInt32 cnt= 0;
1751
1752   nsresult  result = NS_ERROR_FAILURE;
1753   mSHistory->GetCount(&cnt);
1754   if (mIndex < (cnt-1)) {
1755     mIndex++;
1756     nsCOMPtr<nsIHistoryEntry> hEntry;
1757     result = mSHistory->GetEntryAtIndex(mIndex, PR_FALSE, getter_AddRefs(hEntry));
1758     if (hEntry)
1759       result = CallQueryInterface(hEntry, aItem);
1760   }
1761   return result;
1762 }