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