9982d816370bfbaeb101a87b9e4a9980db6f7665
[WebKit-https.git] / Source / WebKit / UIProcess / WebBackForwardList.cpp
1 /*
2  * Copyright (C) 2010 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 INC. AND ITS CONTRIBUTORS ``AS IS''
14  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23  * THE POSSIBILITY OF SUCH DAMAGE.
24  */
25
26 #include "config.h"
27 #include "WebBackForwardList.h"
28
29 #include "APIArray.h"
30 #include "SessionState.h"
31 #include "WebPageProxy.h"
32 #include <WebCore/DiagnosticLoggingClient.h>
33 #include <WebCore/DiagnosticLoggingKeys.h>
34
35 namespace WebKit {
36
37 using namespace WebCore;
38
39 // FIXME: Make this static once WebBackForwardListCF.cpp is no longer using it.
40 uint64_t generateWebBackForwardItemID();
41
42 uint64_t generateWebBackForwardItemID()
43 {
44     // These IDs exist in the UIProcess for items created by the UIProcess.
45     // The IDs generated here need to never collide with the IDs created in WebBackForwardListProxy in the WebProcess.
46     // We accomplish this by starting from 2, and only ever using even ids.
47     static uint64_t uniqueHistoryItemID = 0;
48     uniqueHistoryItemID += 2;
49     return uniqueHistoryItemID;
50 }
51
52 static const unsigned DefaultCapacity = 100;
53
54 WebBackForwardList::WebBackForwardList(WebPageProxy& page)
55     : m_page(&page)
56     , m_hasCurrentIndex(false)
57     , m_currentIndex(0)
58     , m_capacity(DefaultCapacity)
59 {
60 }
61
62 WebBackForwardList::~WebBackForwardList()
63 {
64     // A WebBackForwardList should never be destroyed unless it's associated page has been closed or is invalid.
65     ASSERT((!m_page && !m_hasCurrentIndex) || !m_page->isValid());
66 }
67
68 void WebBackForwardList::pageClosed()
69 {
70     // We should have always started out with an m_page and we should never close the page twice.
71     ASSERT(m_page);
72
73     if (m_page) {
74         size_t size = m_entries.size();
75         for (size_t i = 0; i < size; ++i)
76             didRemoveItem(m_entries[i]);
77     }
78
79     m_page = 0;
80     m_entries.clear();
81     m_hasCurrentIndex = false;
82 }
83
84 void WebBackForwardList::addItem(WebBackForwardListItem* newItem)
85 {
86     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
87
88     if (!m_capacity || !newItem || !m_page)
89         return;
90
91     Vector<Ref<WebBackForwardListItem>> removedItems;
92     
93     if (m_hasCurrentIndex) {
94         m_page->recordAutomaticNavigationSnapshot();
95
96         // Toss everything in the forward list.
97         unsigned targetSize = m_currentIndex + 1;
98         removedItems.reserveCapacity(m_entries.size() - targetSize);
99         while (m_entries.size() > targetSize) {
100             didRemoveItem(m_entries.last());
101             removedItems.append(WTFMove(m_entries.last()));
102             m_entries.removeLast();
103         }
104
105         // Toss the first item if the list is getting too big, as long as we're not using it
106         // (or even if we are, if we only want 1 entry).
107         if (m_entries.size() == m_capacity && (m_currentIndex || m_capacity == 1)) {
108             didRemoveItem(m_entries[0]);
109             removedItems.append(WTFMove(m_entries[0]));
110             m_entries.remove(0);
111
112             if (m_entries.isEmpty())
113                 m_hasCurrentIndex = false;
114             else
115                 m_currentIndex--;
116         }
117     } else {
118         // If we have no current item index we should also not have any entries.
119         ASSERT(m_entries.isEmpty());
120
121         // But just in case it does happen in practice we'll get back in to a consistent state now before adding the new item.
122         size_t size = m_entries.size();
123         for (size_t i = 0; i < size; ++i) {
124             didRemoveItem(m_entries[i]);
125             removedItems.append(WTFMove(m_entries[i]));
126         }
127         m_entries.clear();
128     }
129
130     bool shouldKeepCurrentItem = true;
131
132     if (!m_hasCurrentIndex) {
133         ASSERT(m_entries.isEmpty());
134         m_currentIndex = 0;
135         m_hasCurrentIndex = true;
136     } else {
137         shouldKeepCurrentItem = m_page->shouldKeepCurrentBackForwardListItemInList(m_entries[m_currentIndex]);
138         if (shouldKeepCurrentItem)
139             m_currentIndex++;
140     }
141
142     if (!shouldKeepCurrentItem) {
143         // m_current should never be pointing past the end of the entries Vector.
144         // If it is, something has gone wrong and we should not try to swap in the new item.
145         ASSERT(m_currentIndex < m_entries.size());
146
147         removedItems.append(m_entries[m_currentIndex].copyRef());
148         m_entries[m_currentIndex] = *newItem;
149     } else {
150         // m_current should never be pointing more than 1 past the end of the entries Vector.
151         // If it is, something has gone wrong and we should not try to insert the new item.
152         ASSERT(m_currentIndex <= m_entries.size());
153
154         if (m_currentIndex <= m_entries.size())
155             m_entries.insert(m_currentIndex, *newItem);
156     }
157
158     m_page->didChangeBackForwardList(newItem, WTFMove(removedItems));
159 }
160
161 void WebBackForwardList::goToItem(WebBackForwardListItem& item)
162 {
163     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
164
165     if (!m_entries.size() || !m_page || !m_hasCurrentIndex)
166         return;
167
168     size_t targetIndex = notFound;
169     for (size_t i = 0; i < m_entries.size(); ++i) {
170         if (m_entries[i].ptr() == &item) {
171             targetIndex = i;
172             break;
173         }
174     }
175
176     // If the target item wasn't even in the list, there's nothing else to do.
177     if (targetIndex == notFound)
178         return;
179
180     if (targetIndex < m_currentIndex) {
181         unsigned delta = m_entries.size() - targetIndex - 1;
182         String deltaValue = delta > 10 ? ASCIILiteral("over10") : String::number(delta);
183         m_page->logDiagnosticMessage(WebCore::DiagnosticLoggingKeys::backNavigationDeltaKey(), deltaValue, ShouldSample::No);
184     }
185
186     // If we're going to an item different from the current item, ask the client if the current
187     // item should remain in the list.
188     auto& currentItem = m_entries[m_currentIndex];
189     bool shouldKeepCurrentItem = true;
190     if (currentItem.ptr() != &item) {
191         m_page->recordAutomaticNavigationSnapshot();
192         shouldKeepCurrentItem = m_page->shouldKeepCurrentBackForwardListItemInList(m_entries[m_currentIndex]);
193     }
194
195     // If the client said to remove the current item, remove it and then update the target index.
196     Vector<Ref<WebBackForwardListItem>> removedItems;
197     if (!shouldKeepCurrentItem) {
198         removedItems.append(currentItem.copyRef());
199         m_entries.remove(m_currentIndex);
200         targetIndex = notFound;
201         for (size_t i = 0; i < m_entries.size(); ++i) {
202             if (m_entries[i].ptr() == &item) {
203                 targetIndex = i;
204                 break;
205             }
206         }
207         ASSERT(targetIndex != notFound);
208     }
209
210     m_currentIndex = targetIndex;
211     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
212 }
213
214 WebBackForwardListItem* WebBackForwardList::currentItem() const
215 {
216     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
217
218     return m_page && m_hasCurrentIndex ? m_entries[m_currentIndex].ptr() : nullptr;
219 }
220
221 WebBackForwardListItem* WebBackForwardList::backItem() const
222 {
223     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
224
225     return m_page && m_hasCurrentIndex && m_currentIndex ? m_entries[m_currentIndex - 1].ptr() : nullptr;
226 }
227
228 WebBackForwardListItem* WebBackForwardList::forwardItem() const
229 {
230     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
231
232     return m_page && m_hasCurrentIndex && m_entries.size() && m_currentIndex < m_entries.size() - 1 ? m_entries[m_currentIndex + 1].ptr() : nullptr;
233 }
234
235 WebBackForwardListItem* WebBackForwardList::itemAtIndex(int index) const
236 {
237     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
238
239     if (!m_hasCurrentIndex || !m_page)
240         return nullptr;
241     
242     // Do range checks without doing math on index to avoid overflow.
243     if (index < -backListCount())
244         return nullptr;
245     
246     if (index > forwardListCount())
247         return nullptr;
248         
249     return m_entries[index + m_currentIndex].ptr();
250 }
251
252 int WebBackForwardList::backListCount() const
253 {
254     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
255
256     return m_page && m_hasCurrentIndex ? m_currentIndex : 0;
257 }
258
259 int WebBackForwardList::forwardListCount() const
260 {
261     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
262
263     return m_page && m_hasCurrentIndex ? m_entries.size() - (m_currentIndex + 1) : 0;
264 }
265
266 Ref<API::Array> WebBackForwardList::backList() const
267 {
268     return backListAsAPIArrayWithLimit(backListCount());
269 }
270
271 Ref<API::Array> WebBackForwardList::forwardList() const
272 {
273     return forwardListAsAPIArrayWithLimit(forwardListCount());
274 }
275
276 Ref<API::Array> WebBackForwardList::backListAsAPIArrayWithLimit(unsigned limit) const
277 {
278     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
279
280     if (!m_page || !m_hasCurrentIndex)
281         return API::Array::create();
282
283     unsigned backListSize = static_cast<unsigned>(backListCount());
284     unsigned size = std::min(backListSize, limit);
285     if (!size)
286         return API::Array::create();
287
288     Vector<RefPtr<API::Object>> vector;
289     vector.reserveInitialCapacity(size);
290
291     ASSERT(backListSize >= size);
292     for (unsigned i = backListSize - size; i < backListSize; ++i)
293         vector.uncheckedAppend(m_entries[i].ptr());
294
295     return API::Array::create(WTFMove(vector));
296 }
297
298 Ref<API::Array> WebBackForwardList::forwardListAsAPIArrayWithLimit(unsigned limit) const
299 {
300     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
301
302     if (!m_page || !m_hasCurrentIndex)
303         return API::Array::create();
304
305     unsigned size = std::min(static_cast<unsigned>(forwardListCount()), limit);
306     if (!size)
307         return API::Array::create();
308
309     Vector<RefPtr<API::Object>> vector;
310     vector.reserveInitialCapacity(size);
311
312     unsigned last = m_currentIndex + size;
313     ASSERT(last < m_entries.size());
314     for (unsigned i = m_currentIndex + 1; i <= last; ++i)
315         vector.uncheckedAppend(m_entries[i].ptr());
316
317     return API::Array::create(WTFMove(vector));
318 }
319
320 void WebBackForwardList::removeAllItems()
321 {
322     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
323
324     Vector<Ref<WebBackForwardListItem>> removedItems;
325
326     for (auto& entry : m_entries) {
327         didRemoveItem(entry);
328         removedItems.append(WTFMove(entry));
329     }
330
331     m_entries.clear();
332     m_hasCurrentIndex = false;
333     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
334 }
335
336 void WebBackForwardList::clear()
337 {
338     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
339
340     size_t size = m_entries.size();
341     if (!m_page || size <= 1)
342         return;
343
344     RefPtr<WebBackForwardListItem> currentItem = this->currentItem();
345     Vector<Ref<WebBackForwardListItem>> removedItems;
346
347     if (!currentItem) {
348         // We should only ever have no current item if we also have no current item index.
349         ASSERT(!m_hasCurrentIndex);
350
351         // But just in case it does happen in practice we should get back into a consistent state now.
352         for (size_t i = 0; i < size; ++i) {
353             didRemoveItem(m_entries[i]);
354             removedItems.append(WTFMove(m_entries[i]));
355         }
356
357         m_entries.clear();
358         m_hasCurrentIndex = false;
359         m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
360
361         return;
362     }
363
364     for (size_t i = 0; i < size; ++i) {
365         if (m_entries[i].ptr() != currentItem)
366             didRemoveItem(m_entries[i]);
367     }
368
369     removedItems.reserveCapacity(size - 1);
370     for (size_t i = 0; i < size; ++i) {
371         if (i != m_currentIndex && m_hasCurrentIndex)
372             removedItems.append(WTFMove(m_entries[i]));
373     }
374
375     m_currentIndex = 0;
376
377     m_entries.clear();
378     if (currentItem)
379         m_entries.append(currentItem.releaseNonNull());
380     else
381         m_hasCurrentIndex = false;
382     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
383 }
384
385 BackForwardListState WebBackForwardList::backForwardListState(WTF::Function<bool (WebBackForwardListItem&)>&& filter) const
386 {
387     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
388
389     BackForwardListState backForwardListState;
390     if (m_hasCurrentIndex)
391         backForwardListState.currentIndex = m_currentIndex;
392
393     for (size_t i = 0; i < m_entries.size(); ++i) {
394         auto& entry = m_entries[i];
395
396         if (filter && !filter(entry)) {
397             auto& currentIndex = backForwardListState.currentIndex;
398             if (currentIndex && i <= currentIndex.value() && currentIndex.value())
399                 --currentIndex.value();
400
401             continue;
402         }
403
404         backForwardListState.items.append(entry->itemState());
405     }
406
407     if (backForwardListState.items.isEmpty())
408         backForwardListState.currentIndex = std::nullopt;
409     else if (backForwardListState.items.size() <= backForwardListState.currentIndex.value())
410         backForwardListState.currentIndex = backForwardListState.items.size() - 1;
411
412     return backForwardListState;
413 }
414
415 void WebBackForwardList::restoreFromState(BackForwardListState backForwardListState)
416 {
417     Vector<Ref<WebBackForwardListItem>> items;
418     items.reserveInitialCapacity(backForwardListState.items.size());
419
420     for (auto& backForwardListItemState : backForwardListState.items) {
421         backForwardListItemState.identifier = generateWebBackForwardItemID();
422         items.uncheckedAppend(WebBackForwardListItem::create(WTFMove(backForwardListItemState), m_page->pageID()));
423     }
424     m_hasCurrentIndex = !!backForwardListState.currentIndex;
425     m_currentIndex = backForwardListState.currentIndex.value_or(0);
426     m_entries = WTFMove(items);
427 }
428
429 Vector<BackForwardListItemState> WebBackForwardList::itemStates() const
430 {
431     Vector<BackForwardListItemState> itemStates;
432     itemStates.reserveInitialCapacity(m_entries.size());
433
434     for (const auto& entry : m_entries)
435         itemStates.uncheckedAppend(entry->itemState());
436
437     return itemStates;
438 }
439
440 void WebBackForwardList::didRemoveItem(WebBackForwardListItem& backForwardListItem)
441 {
442     m_page->backForwardRemovedItem(backForwardListItem.itemID());
443
444 #if PLATFORM(COCOA)
445     backForwardListItem.setSnapshot(nullptr);
446 #endif
447 }
448
449 } // namespace WebKit