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