Source/WebCore/history/HistoryItem.cpp

   1 /*
   2  * Copyright (C) 2005, 2006, 2008, 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "HistoryItem.h"
  28
  29 #include "CachedPage.h"
  30 #include "Document.h"
  31 #include "IconDatabase.h"
  32 #include "PageCache.h"
  33 #include "ResourceRequest.h"
  34 #include "SerializedScriptValue.h"
  35 #include "SharedBuffer.h"
  36 #include <stdio.h>
  37 #include <wtf/CurrentTime.h>
  38 #include <wtf/DateMath.h>
  39 #include <wtf/Decoder.h>
  40 #include <wtf/Encoder.h>
  41 #include <wtf/text/CString.h>
  42
  43 namespace WebCore {
  44
  45 const uint32_t backForwardTreeEncodingVersion = 2;
  46
  47 static long long generateSequenceNumber()
  48 {
  49     // Initialize to the current time to reduce the likelihood of generating
  50     // identifiers that overlap with those from past/future browser sessions.
  51     static long long next = static_cast<long long>(currentTime() * 1000000.0);
  52     return ++next;
  53 }
  54
  55 static void defaultNotifyHistoryItemChanged(HistoryItem*)
  56 {
  57 }
  58
  59 void (*notifyHistoryItemChanged)(HistoryItem*) = defaultNotifyHistoryItemChanged;
  60
  61 HistoryItem::HistoryItem()
  62     : m_lastVisitedTime(0)
  63     , m_lastVisitWasHTTPNonGet(false)
  64     , m_pageScaleFactor(0)
  65     , m_lastVisitWasFailure(false)
  66     , m_isTargetItem(false)
  67     , m_visitCount(0)
  68     , m_itemSequenceNumber(generateSequenceNumber())
  69     , m_documentSequenceNumber(generateSequenceNumber())
  70     , m_next(0)
  71     , m_prev(0)
  72 {
  73 }
  74
  75 HistoryItem::HistoryItem(const String& urlString, const String& title, double time)
  76     : m_urlString(urlString)
  77     , m_originalURLString(urlString)
  78     , m_title(title)
  79     , m_lastVisitedTime(time)
  80     , m_lastVisitWasHTTPNonGet(false)
  81     , m_pageScaleFactor(0)
  82     , m_lastVisitWasFailure(false)
  83     , m_isTargetItem(false)
  84     , m_visitCount(0)
  85     , m_itemSequenceNumber(generateSequenceNumber())
  86     , m_documentSequenceNumber(generateSequenceNumber())
  87     , m_next(0)
  88     , m_prev(0)
  89 {
  90     iconDatabase().retainIconForPageURL(m_urlString);
  91 }
  92
  93 HistoryItem::HistoryItem(const String& urlString, const String& title, const String& alternateTitle, double time)
  94     : m_urlString(urlString)
  95     , m_originalURLString(urlString)
  96     , m_title(title)
  97     , m_displayTitle(alternateTitle)
  98     , m_lastVisitedTime(time)
  99     , m_lastVisitWasHTTPNonGet(false)
 100     , m_pageScaleFactor(0)
 101     , m_lastVisitWasFailure(false)
 102     , m_isTargetItem(false)
 103     , m_visitCount(0)
 104     , m_itemSequenceNumber(generateSequenceNumber())
 105     , m_documentSequenceNumber(generateSequenceNumber())
 106     , m_next(0)
 107     , m_prev(0)
 108 {
 109     iconDatabase().retainIconForPageURL(m_urlString);
 110 }
 111
 112 HistoryItem::HistoryItem(const URL& url, const String& target, const String& parent, const String& title)
 113     : m_urlString(url.string())
 114     , m_originalURLString(url.string())
 115     , m_target(target)
 116     , m_parent(parent)
 117     , m_title(title)
 118     , m_lastVisitedTime(0)
 119     , m_lastVisitWasHTTPNonGet(false)
 120     , m_pageScaleFactor(0)
 121     , m_lastVisitWasFailure(false)
 122     , m_isTargetItem(false)
 123     , m_visitCount(0)
 124     , m_itemSequenceNumber(generateSequenceNumber())
 125     , m_documentSequenceNumber(generateSequenceNumber())
 126     , m_next(0)
 127     , m_prev(0)
 128 {
 129     iconDatabase().retainIconForPageURL(m_urlString);
 130 }
 131
 132 HistoryItem::~HistoryItem()
 133 {
 134     ASSERT(!m_cachedPage);
 135     iconDatabase().releaseIconForPageURL(m_urlString);
 136 }
 137
 138 inline HistoryItem::HistoryItem(const HistoryItem& item)
 139     : RefCounted<HistoryItem>()
 140     , m_urlString(item.m_urlString)
 141     , m_originalURLString(item.m_originalURLString)
 142     , m_referrer(item.m_referrer)
 143     , m_target(item.m_target)
 144     , m_parent(item.m_parent)
 145     , m_title(item.m_title)
 146     , m_displayTitle(item.m_displayTitle)
 147     , m_lastVisitedTime(item.m_lastVisitedTime)
 148     , m_lastVisitWasHTTPNonGet(item.m_lastVisitWasHTTPNonGet)
 149     , m_scrollPoint(item.m_scrollPoint)
 150     , m_pageScaleFactor(item.m_pageScaleFactor)
 151     , m_lastVisitWasFailure(item.m_lastVisitWasFailure)
 152     , m_isTargetItem(item.m_isTargetItem)
 153     , m_visitCount(item.m_visitCount)
 154     , m_dailyVisitCounts(item.m_dailyVisitCounts)
 155     , m_weeklyVisitCounts(item.m_weeklyVisitCounts)
 156     , m_itemSequenceNumber(item.m_itemSequenceNumber)
 157     , m_documentSequenceNumber(item.m_documentSequenceNumber)
 158     , m_formContentType(item.m_formContentType)
 159 {
 160     if (item.m_formData)
 161         m_formData = item.m_formData->copy();
 162
 163     unsigned size = item.m_children.size();
 164     m_children.reserveInitialCapacity(size);
 165     for (unsigned i = 0; i < size; ++i)
 166         m_children.uncheckedAppend(item.m_children[i]->copy());
 167
 168     if (item.m_redirectURLs)
 169         m_redirectURLs = adoptPtr(new Vector<String>(*item.m_redirectURLs));
 170 }
 171
 172 PassRefPtr<HistoryItem> HistoryItem::copy() const
 173 {
 174     return adoptRef(new HistoryItem(*this));
 175 }
 176
 177 void HistoryItem::reset()
 178 {
 179     iconDatabase().releaseIconForPageURL(m_urlString);
 180
 181     m_urlString = String();
 182     m_originalURLString = String();
 183     m_referrer = String();
 184     m_target = String();
 185     m_parent = String();
 186     m_title = String();
 187     m_displayTitle = String();
 188
 189     m_lastVisitedTime = 0;
 190     m_lastVisitWasHTTPNonGet = false;
 191
 192     m_lastVisitWasFailure = false;
 193     m_isTargetItem = false;
 194     m_visitCount = 0;
 195     m_dailyVisitCounts.clear();
 196     m_weeklyVisitCounts.clear();
 197
 198     m_redirectURLs.clear();
 199
 200     m_itemSequenceNumber = generateSequenceNumber();
 201
 202     m_stateObject = 0;
 203     m_documentSequenceNumber = generateSequenceNumber();
 204
 205     m_formData = 0;
 206     m_formContentType = String();
 207
 208     clearChildren();
 209 }
 210
 211 const String& HistoryItem::urlString() const
 212 {
 213     return m_urlString;
 214 }
 215
 216 // The first URL we loaded to get to where this history item points.  Includes both client
 217 // and server redirects.
 218 const String& HistoryItem::originalURLString() const
 219 {
 220     return m_originalURLString;
 221 }
 222
 223 const String& HistoryItem::title() const
 224 {
 225     return m_title;
 226 }
 227
 228 const String& HistoryItem::alternateTitle() const
 229 {
 230     return m_displayTitle;
 231 }
 232
 233 bool HistoryItem::hasCachedPageExpired() const
 234 {
 235     return m_cachedPage ? m_cachedPage->hasExpired() : false;
 236 }
 237
 238 double HistoryItem::lastVisitedTime() const
 239 {
 240     return m_lastVisitedTime;
 241 }
 242
 243 URL HistoryItem::url() const
 244 {
 245     return URL(ParsedURLString, m_urlString);
 246 }
 247
 248 URL HistoryItem::originalURL() const
 249 {
 250     return URL(ParsedURLString, m_originalURLString);
 251 }
 252
 253 const String& HistoryItem::referrer() const
 254 {
 255     return m_referrer;
 256 }
 257
 258 const String& HistoryItem::target() const
 259 {
 260     return m_target;
 261 }
 262
 263 const String& HistoryItem::parent() const
 264 {
 265     return m_parent;
 266 }
 267
 268 void HistoryItem::setAlternateTitle(const String& alternateTitle)
 269 {
 270     m_displayTitle = alternateTitle;
 271     notifyHistoryItemChanged(this);
 272 }
 273
 274 void HistoryItem::setURLString(const String& urlString)
 275 {
 276     if (m_urlString != urlString) {
 277         iconDatabase().releaseIconForPageURL(m_urlString);
 278         m_urlString = urlString;
 279         iconDatabase().retainIconForPageURL(m_urlString);
 280     }
 281
 282     notifyHistoryItemChanged(this);
 283 }
 284
 285 void HistoryItem::setURL(const URL& url)
 286 {
 287     pageCache()->remove(this);
 288     setURLString(url.string());
 289     clearDocumentState();
 290 }
 291
 292 void HistoryItem::setOriginalURLString(const String& urlString)
 293 {
 294     m_originalURLString = urlString;
 295     notifyHistoryItemChanged(this);
 296 }
 297
 298 void HistoryItem::setReferrer(const String& referrer)
 299 {
 300     m_referrer = referrer;
 301     notifyHistoryItemChanged(this);
 302 }
 303
 304 void HistoryItem::setTitle(const String& title)
 305 {
 306     m_title = title;
 307     notifyHistoryItemChanged(this);
 308 }
 309
 310 void HistoryItem::setTarget(const String& target)
 311 {
 312     m_target = target;
 313     notifyHistoryItemChanged(this);
 314 }
 315
 316 void HistoryItem::setParent(const String& parent)
 317 {
 318     m_parent = parent;
 319 }
 320
 321 static inline int timeToDay(double time)
 322 {
 323     return static_cast<int>(ceil(time / secondsPerDay));
 324 }
 325
 326 void HistoryItem::padDailyCountsForNewVisit(double time)
 327 {
 328     if (m_dailyVisitCounts.isEmpty())
 329         m_dailyVisitCounts.insert(0, m_visitCount);
 330
 331     int daysElapsed = timeToDay(time) - timeToDay(m_lastVisitedTime);
 332
 333     if (daysElapsed < 0)
 334       daysElapsed = 0;
 335
 336     Vector<int> padding;
 337     padding.fill(0, daysElapsed);
 338     m_dailyVisitCounts.insert(0, padding);
 339 }
 340
 341 static const size_t daysPerWeek = 7;
 342 static const size_t maxDailyCounts = 2 * daysPerWeek - 1;
 343 static const size_t maxWeeklyCounts = 5;
 344
 345 void HistoryItem::collapseDailyVisitsToWeekly()
 346 {
 347     while (m_dailyVisitCounts.size() > maxDailyCounts) {
 348         int oldestWeekTotal = 0;
 349         for (size_t i = 0; i < daysPerWeek; i++)
 350             oldestWeekTotal += m_dailyVisitCounts[m_dailyVisitCounts.size() - daysPerWeek + i];
 351         m_dailyVisitCounts.shrink(m_dailyVisitCounts.size() - daysPerWeek);
 352         m_weeklyVisitCounts.insert(0, oldestWeekTotal);
 353     }
 354
 355     if (m_weeklyVisitCounts.size() > maxWeeklyCounts)
 356         m_weeklyVisitCounts.shrink(maxWeeklyCounts);
 357 }
 358
 359 void HistoryItem::recordVisitAtTime(double time, VisitCountBehavior visitCountBehavior)
 360 {
 361     padDailyCountsForNewVisit(time);
 362
 363     m_lastVisitedTime = time;
 364
 365     if (visitCountBehavior == IncreaseVisitCount) {
 366         ++m_visitCount;
 367         ++m_dailyVisitCounts[0];
 368     }
 369
 370     collapseDailyVisitsToWeekly();
 371 }
 372
 373 void HistoryItem::setLastVisitedTime(double time)
 374 {
 375     if (m_lastVisitedTime != time)
 376         recordVisitAtTime(time);
 377 }
 378
 379 void HistoryItem::visited(const String& title, double time, VisitCountBehavior visitCountBehavior)
 380 {
 381     m_title = title;
 382     recordVisitAtTime(time, visitCountBehavior);
 383 }
 384
 385 int HistoryItem::visitCount() const
 386 {
 387     return m_visitCount;
 388 }
 389
 390 void HistoryItem::recordInitialVisit()
 391 {
 392     ASSERT(!m_visitCount);
 393     recordVisitAtTime(m_lastVisitedTime);
 394 }
 395
 396 void HistoryItem::setVisitCount(int count)
 397 {
 398     m_visitCount = count;
 399 }
 400
 401 void HistoryItem::adoptVisitCounts(Vector<int>& dailyCounts, Vector<int>& weeklyCounts)
 402 {
 403     m_dailyVisitCounts.clear();
 404     m_dailyVisitCounts.swap(dailyCounts);
 405     m_weeklyVisitCounts.clear();
 406     m_weeklyVisitCounts.swap(weeklyCounts);
 407 }
 408
 409 const IntPoint& HistoryItem::scrollPoint() const
 410 {
 411     return m_scrollPoint;
 412 }
 413
 414 void HistoryItem::setScrollPoint(const IntPoint& point)
 415 {
 416     m_scrollPoint = point;
 417 }
 418
 419 void HistoryItem::clearScrollPoint()
 420 {
 421     m_scrollPoint.setX(0);
 422     m_scrollPoint.setY(0);
 423 }
 424
 425 float HistoryItem::pageScaleFactor() const
 426 {
 427     return m_pageScaleFactor;
 428 }
 429
 430 void HistoryItem::setPageScaleFactor(float scaleFactor)
 431 {
 432     m_pageScaleFactor = scaleFactor;
 433 }
 434
 435 void HistoryItem::setDocumentState(const Vector<String>& state)
 436 {
 437     m_documentState = state;
 438 }
 439
 440 const Vector<String>& HistoryItem::documentState() const
 441 {
 442     return m_documentState;
 443 }
 444
 445 void HistoryItem::clearDocumentState()
 446 {
 447     m_documentState.clear();
 448 }
 449
 450 bool HistoryItem::isTargetItem() const
 451 {
 452     return m_isTargetItem;
 453 }
 454
 455 void HistoryItem::setIsTargetItem(bool flag)
 456 {
 457     m_isTargetItem = flag;
 458 }
 459
 460 void HistoryItem::setStateObject(PassRefPtr<SerializedScriptValue> object)
 461 {
 462     m_stateObject = object;
 463 }
 464
 465 void HistoryItem::addChildItem(PassRefPtr<HistoryItem> child)
 466 {
 467     ASSERT(!childItemWithTarget(child->target()));
 468     m_children.append(child);
 469 }
 470
 471 void HistoryItem::setChildItem(PassRefPtr<HistoryItem> child)
 472 {
 473     ASSERT(!child->isTargetItem());
 474     unsigned size = m_children.size();
 475     for (unsigned i = 0; i < size; ++i)  {
 476         if (m_children[i]->target() == child->target()) {
 477             child->setIsTargetItem(m_children[i]->isTargetItem());
 478             m_children[i] = child;
 479             return;
 480         }
 481     }
 482     m_children.append(child);
 483 }
 484
 485 HistoryItem* HistoryItem::childItemWithTarget(const String& target) const
 486 {
 487     unsigned size = m_children.size();
 488     for (unsigned i = 0; i < size; ++i) {
 489         if (m_children[i]->target() == target)
 490             return m_children[i].get();
 491     }
 492     return 0;
 493 }
 494
 495 HistoryItem* HistoryItem::childItemWithDocumentSequenceNumber(long long number) const
 496 {
 497     unsigned size = m_children.size();
 498     for (unsigned i = 0; i < size; ++i) {
 499         if (m_children[i]->documentSequenceNumber() == number)
 500             return m_children[i].get();
 501     }
 502     return 0;
 503 }
 504
 505 // <rdar://problem/4895849> HistoryItem::findTargetItem() should be replaced with a non-recursive method.
 506 HistoryItem* HistoryItem::findTargetItem()
 507 {
 508     if (m_isTargetItem)
 509         return this;
 510     unsigned size = m_children.size();
 511     for (unsigned i = 0; i < size; ++i) {
 512         if (HistoryItem* match = m_children[i]->targetItem())
 513             return match;
 514     }
 515     return 0;
 516 }
 517
 518 HistoryItem* HistoryItem::targetItem()
 519 {
 520     HistoryItem* foundItem = findTargetItem();
 521     return foundItem ? foundItem : this;
 522 }
 523
 524 const HistoryItemVector& HistoryItem::children() const
 525 {
 526     return m_children;
 527 }
 528
 529 bool HistoryItem::hasChildren() const
 530 {
 531     return !m_children.isEmpty();
 532 }
 533
 534 void HistoryItem::clearChildren()
 535 {
 536     m_children.clear();
 537 }
 538
 539 bool HistoryItem::isAncestorOf(const HistoryItem* item) const
 540 {
 541     for (size_t i = 0; i < m_children.size(); ++i) {
 542         HistoryItem* child = m_children[i].get();
 543         if (child == item)
 544             return true;
 545         if (child->isAncestorOf(item))
 546             return true;
 547     }
 548     return false;
 549 }
 550
 551 // We do same-document navigation if going to a different item and if either of the following is true:
 552 // - The other item corresponds to the same document (for history entries created via pushState or fragment changes).
 553 // - The other item corresponds to the same set of documents, including frames (for history entries created via regular navigation)
 554 bool HistoryItem::shouldDoSameDocumentNavigationTo(HistoryItem* otherItem) const
 555 {
 556     if (this == otherItem)
 557         return false;
 558
 559     if (stateObject() || otherItem->stateObject())
 560         return documentSequenceNumber() == otherItem->documentSequenceNumber();
 561
 562     if ((url().hasFragmentIdentifier() || otherItem->url().hasFragmentIdentifier()) && equalIgnoringFragmentIdentifier(url(), otherItem->url()))
 563         return documentSequenceNumber() == otherItem->documentSequenceNumber();
 564
 565     return hasSameDocumentTree(otherItem);
 566 }
 567
 568 // Does a recursive check that this item and its descendants have the same
 569 // document sequence numbers as the other item.
 570 bool HistoryItem::hasSameDocumentTree(HistoryItem* otherItem) const
 571 {
 572     if (documentSequenceNumber() != otherItem->documentSequenceNumber())
 573         return false;
 574
 575     if (children().size() != otherItem->children().size())
 576         return false;
 577
 578     for (size_t i = 0; i < children().size(); i++) {
 579         HistoryItem* child = children()[i].get();
 580         HistoryItem* otherChild = otherItem->childItemWithDocumentSequenceNumber(child->documentSequenceNumber());
 581         if (!otherChild || !child->hasSameDocumentTree(otherChild))
 582             return false;
 583     }
 584
 585     return true;
 586 }
 587
 588 // Does a non-recursive check that this item and its immediate children have the
 589 // same frames as the other item.
 590 bool HistoryItem::hasSameFrames(HistoryItem* otherItem) const
 591 {
 592     if (target() != otherItem->target())
 593         return false;
 594
 595     if (children().size() != otherItem->children().size())
 596         return false;
 597
 598     for (size_t i = 0; i < children().size(); i++) {
 599         if (!otherItem->childItemWithTarget(children()[i]->target()))
 600             return false;
 601     }
 602
 603     return true;
 604 }
 605
 606 String HistoryItem::formContentType() const
 607 {
 608     return m_formContentType;
 609 }
 610
 611 void HistoryItem::setFormInfoFromRequest(const ResourceRequest& request)
 612 {
 613     m_referrer = request.httpReferrer();
 614
 615     if (equalIgnoringCase(request.httpMethod(), "POST")) {
 616         // FIXME: Eventually we have to make this smart enough to handle the case where
 617         // we have a stream for the body to handle the "data interspersed with files" feature.
 618         m_formData = request.httpBody();
 619         m_formContentType = request.httpContentType();
 620     } else {
 621         m_formData = 0;
 622         m_formContentType = String();
 623     }
 624 }
 625
 626 void HistoryItem::setFormData(PassRefPtr<FormData> formData)
 627 {
 628     m_formData = formData;
 629 }
 630
 631 void HistoryItem::setFormContentType(const String& formContentType)
 632 {
 633     m_formContentType = formContentType;
 634 }
 635
 636 FormData* HistoryItem::formData()
 637 {
 638     return m_formData.get();
 639 }
 640
 641 bool HistoryItem::isCurrentDocument(Document* doc) const
 642 {
 643     // FIXME: We should find a better way to check if this is the current document.
 644     return equalIgnoringFragmentIdentifier(url(), doc->url());
 645 }
 646
 647 void HistoryItem::mergeAutoCompleteHints(HistoryItem* otherItem)
 648 {
 649     // FIXME: this is broken - we should be merging the daily counts
 650     // somehow.  but this is to support API that's not really used in
 651     // practice so leave it broken for now.
 652     ASSERT(otherItem);
 653     if (otherItem != this)
 654         m_visitCount += otherItem->m_visitCount;
 655 }
 656
 657 void HistoryItem::addRedirectURL(const String& url)
 658 {
 659     if (!m_redirectURLs)
 660         m_redirectURLs = adoptPtr(new Vector<String>);
 661
 662     // Our API allows us to store all the URLs in the redirect chain, but for
 663     // now we only have a use for the final URL.
 664     (*m_redirectURLs).resize(1);
 665     (*m_redirectURLs)[0] = url;
 666 }
 667
 668 Vector<String>* HistoryItem::redirectURLs() const
 669 {
 670     return m_redirectURLs.get();
 671 }
 672
 673 void HistoryItem::setRedirectURLs(PassOwnPtr<Vector<String> > redirectURLs)
 674 {
 675     m_redirectURLs = redirectURLs;
 676 }
 677
 678 void HistoryItem::encodeBackForwardTree(Encoder& encoder) const
 679 {
 680     encoder.encodeUInt32(backForwardTreeEncodingVersion);
 681
 682     encodeBackForwardTreeNode(encoder);
 683 }
 684
 685 void HistoryItem::encodeBackForwardTreeNode(Encoder& encoder) const
 686 {
 687     size_t size = m_children.size();
 688     encoder.encodeUInt64(size);
 689     for (size_t i = 0; i < size; ++i) {
 690         const HistoryItem& child = *m_children[i];
 691
 692         encoder.encodeString(child.m_originalURLString);
 693
 694         encoder.encodeString(child.m_urlString);
 695
 696         child.encodeBackForwardTreeNode(encoder);
 697     }
 698
 699     encoder.encodeInt64(m_documentSequenceNumber);
 700
 701     size = m_documentState.size();
 702     encoder.encodeUInt64(size);
 703     for (size_t i = 0; i < size; ++i)
 704         encoder.encodeString(m_documentState[i]);
 705
 706     encoder.encodeString(m_formContentType);
 707
 708     encoder.encodeBool(m_formData);
 709     if (m_formData)
 710         m_formData->encode(encoder);
 711
 712     encoder.encodeInt64(m_itemSequenceNumber);
 713
 714     encoder.encodeString(m_referrer);
 715
 716     encoder.encodeInt32(m_scrollPoint.x());
 717     encoder.encodeInt32(m_scrollPoint.y());
 718
 719     encoder.encodeFloat(m_pageScaleFactor);
 720
 721     encoder.encodeBool(m_stateObject);
 722     if (m_stateObject)
 723         encoder.encodeBytes(m_stateObject->data().data(), m_stateObject->data().size());
 724
 725     encoder.encodeString(m_target);
 726 }
 727
 728 struct DecodeRecursionStackElement {
 729     RefPtr<HistoryItem> node;
 730     size_t i;
 731     uint64_t size;
 732
 733     DecodeRecursionStackElement(PassRefPtr<HistoryItem> node, size_t i, uint64_t size)
 734         : node(node)
 735         , i(i)
 736         , size(size)
 737     {
 738     }
 739 };
 740
 741 PassRefPtr<HistoryItem> HistoryItem::decodeBackForwardTree(const String& topURLString, const String& topTitle, const String& topOriginalURLString, Decoder& decoder)
 742 {
 743     // Since the data stream is not trusted, the decode has to be non-recursive.
 744     // We don't want bad data to cause a stack overflow.
 745
 746     uint32_t version;
 747     if (!decoder.decodeUInt32(version))
 748         return 0;
 749     if (version != backForwardTreeEncodingVersion)
 750         return 0;
 751
 752     String urlString = topURLString;
 753     String title = topTitle;
 754     String originalURLString = topOriginalURLString;
 755
 756     Vector<DecodeRecursionStackElement, 16> recursionStack;
 757
 758 recurse:
 759     RefPtr<HistoryItem> node = create(urlString, title, 0);
 760
 761     node->setOriginalURLString(originalURLString);
 762
 763     title = String();
 764
 765     uint64_t size;
 766     if (!decoder.decodeUInt64(size))
 767         return 0;
 768     size_t i;
 769     RefPtr<HistoryItem> child;
 770     for (i = 0; i < size; ++i) {
 771         if (!decoder.decodeString(originalURLString))
 772             return 0;
 773
 774         if (!decoder.decodeString(urlString))
 775             return 0;
 776
 777         recursionStack.append(DecodeRecursionStackElement(node.release(), i, size));
 778         goto recurse;
 779
 780 resume:
 781         node->m_children.append(child.release());
 782     }
 783
 784     if (!decoder.decodeInt64(node->m_documentSequenceNumber))
 785         return 0;
 786
 787     if (!decoder.decodeUInt64(size))
 788         return 0;
 789     for (i = 0; i < size; ++i) {
 790         String state;
 791         if (!decoder.decodeString(state))
 792             return 0;
 793         node->m_documentState.append(state);
 794     }
 795
 796     if (!decoder.decodeString(node->m_formContentType))
 797         return 0;
 798
 799     bool hasFormData;
 800     if (!decoder.decodeBool(hasFormData))
 801         return 0;
 802     if (hasFormData) {
 803         node->m_formData = FormData::decode(decoder);
 804         if (!node->m_formData)
 805             return 0;
 806     }
 807
 808     if (!decoder.decodeInt64(node->m_itemSequenceNumber))
 809         return 0;
 810
 811     if (!decoder.decodeString(node->m_referrer))
 812         return 0;
 813
 814     int32_t x;
 815     if (!decoder.decodeInt32(x))
 816         return 0;
 817     int32_t y;
 818     if (!decoder.decodeInt32(y))
 819         return 0;
 820     node->m_scrollPoint = IntPoint(x, y);
 821
 822     if (!decoder.decodeFloat(node->m_pageScaleFactor))
 823         return 0;
 824
 825     bool hasStateObject;
 826     if (!decoder.decodeBool(hasStateObject))
 827         return 0;
 828     if (hasStateObject) {
 829         Vector<uint8_t> bytes;
 830         if (!decoder.decodeBytes(bytes))
 831             return 0;
 832         node->m_stateObject = SerializedScriptValue::adopt(bytes);
 833     }
 834
 835     if (!decoder.decodeString(node->m_target))
 836         return 0;
 837
 838     // Simulate recursion with our own stack.
 839     if (!recursionStack.isEmpty()) {
 840         DecodeRecursionStackElement& element = recursionStack.last();
 841         child = node.release();
 842         node = element.node.release();
 843         i = element.i;
 844         size = element.size;
 845         recursionStack.removeLast();
 846         goto resume;
 847     }
 848
 849     return node.release();
 850 }
 851
 852 #ifndef NDEBUG
 853
 854 int HistoryItem::showTree() const
 855 {
 856     return showTreeWithIndent(0);
 857 }
 858
 859 int HistoryItem::showTreeWithIndent(unsigned indentLevel) const
 860 {
 861     Vector<char> prefix;
 862     for (unsigned i = 0; i < indentLevel; ++i)
 863         prefix.append("  ", 2);
 864     prefix.append("\0", 1);
 865
 866     fprintf(stderr, "%s+-%s (%p)\n", prefix.data(), m_urlString.utf8().data(), this);
 867
 868     int totalSubItems = 0;
 869     for (unsigned i = 0; i < m_children.size(); ++i)
 870         totalSubItems += m_children[i]->showTreeWithIndent(indentLevel + 1);
 871     return totalSubItems + 1;
 872 }
 873
 874 #endif
 875
 876 } // namespace WebCore
 877
 878 #ifndef NDEBUG
 879
 880 int showTree(const WebCore::HistoryItem* item)
 881 {
 882     return item->showTree();
 883 }
 884
 885 #endif