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