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