Add globally-unique HistoryItem identifiers (and have WebKit2 adopt them).
[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 static const unsigned DefaultCapacity = 100;
40
41 WebBackForwardList::WebBackForwardList(WebPageProxy& page)
42     : m_page(&page)
43     , m_hasCurrentIndex(false)
44     , m_currentIndex(0)
45     , m_capacity(DefaultCapacity)
46 {
47 }
48
49 WebBackForwardList::~WebBackForwardList()
50 {
51     // A WebBackForwardList should never be destroyed unless it's associated page has been closed or is invalid.
52     ASSERT((!m_page && !m_hasCurrentIndex) || !m_page->isValid());
53 }
54
55 WebBackForwardListItem* WebBackForwardList::itemForID(const BackForwardItemIdentifier& identifier)
56 {
57     if (!m_page)
58         return nullptr;
59
60     auto* item = WebBackForwardListItem::itemForID(identifier);
61     if (!item)
62         return nullptr;
63
64     ASSERT(item->pageID() == m_page->pageID());
65     return item;
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 = nullptr;
80     m_entries.clear();
81     m_hasCurrentIndex = false;
82 }
83
84 void WebBackForwardList::addItem(Ref<WebBackForwardListItem>&& newItem)
85 {
86     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
87
88     if (!m_capacity || !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     auto* newItemPtr = newItem.ptr();
143     if (!shouldKeepCurrentItem) {
144         // m_current should never be pointing past the end of the entries Vector.
145         // If it is, something has gone wrong and we should not try to swap in the new item.
146         ASSERT(m_currentIndex < m_entries.size());
147
148         removedItems.append(m_entries[m_currentIndex].copyRef());
149         m_entries[m_currentIndex] = WTFMove(newItem);
150     } else {
151         // m_current should never be pointing more than 1 past the end of the entries Vector.
152         // If it is, something has gone wrong and we should not try to insert the new item.
153         ASSERT(m_currentIndex <= m_entries.size());
154
155         if (m_currentIndex <= m_entries.size())
156             m_entries.insert(m_currentIndex, WTFMove(newItem));
157     }
158
159     m_page->didChangeBackForwardList(newItemPtr, WTFMove(removedItems));
160 }
161
162 void WebBackForwardList::goToItem(WebBackForwardListItem& item)
163 {
164     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
165
166     if (!m_entries.size() || !m_page || !m_hasCurrentIndex)
167         return;
168
169     size_t targetIndex = notFound;
170     for (size_t i = 0; i < m_entries.size(); ++i) {
171         if (m_entries[i].ptr() == &item) {
172             targetIndex = i;
173             break;
174         }
175     }
176
177     // If the target item wasn't even in the list, there's nothing else to do.
178     if (targetIndex == notFound)
179         return;
180
181     if (targetIndex < m_currentIndex) {
182         unsigned delta = m_entries.size() - targetIndex - 1;
183         String deltaValue = delta > 10 ? ASCIILiteral("over10") : String::number(delta);
184         m_page->logDiagnosticMessage(WebCore::DiagnosticLoggingKeys::backNavigationDeltaKey(), deltaValue, ShouldSample::No);
185     }
186
187     // If we're going to an item different from the current item, ask the client if the current
188     // item should remain in the list.
189     auto& currentItem = m_entries[m_currentIndex];
190     bool shouldKeepCurrentItem = true;
191     if (currentItem.ptr() != &item) {
192         m_page->recordAutomaticNavigationSnapshot();
193         shouldKeepCurrentItem = m_page->shouldKeepCurrentBackForwardListItemInList(m_entries[m_currentIndex]);
194     }
195
196     // If the client said to remove the current item, remove it and then update the target index.
197     Vector<Ref<WebBackForwardListItem>> removedItems;
198     if (!shouldKeepCurrentItem) {
199         removedItems.append(currentItem.copyRef());
200         m_entries.remove(m_currentIndex);
201         targetIndex = notFound;
202         for (size_t i = 0; i < m_entries.size(); ++i) {
203             if (m_entries[i].ptr() == &item) {
204                 targetIndex = i;
205                 break;
206             }
207         }
208         ASSERT(targetIndex != notFound);
209     }
210
211     m_currentIndex = targetIndex;
212     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
213 }
214
215 WebBackForwardListItem* WebBackForwardList::currentItem() const
216 {
217     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
218
219     return m_page && m_hasCurrentIndex ? m_entries[m_currentIndex].ptr() : nullptr;
220 }
221
222 WebBackForwardListItem* WebBackForwardList::backItem() const
223 {
224     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
225
226     return m_page && m_hasCurrentIndex && m_currentIndex ? m_entries[m_currentIndex - 1].ptr() : nullptr;
227 }
228
229 WebBackForwardListItem* WebBackForwardList::forwardItem() const
230 {
231     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
232
233     return m_page && m_hasCurrentIndex && m_entries.size() && m_currentIndex < m_entries.size() - 1 ? m_entries[m_currentIndex + 1].ptr() : nullptr;
234 }
235
236 WebBackForwardListItem* WebBackForwardList::itemAtIndex(int index) const
237 {
238     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
239
240     if (!m_hasCurrentIndex || !m_page)
241         return nullptr;
242     
243     // Do range checks without doing math on index to avoid overflow.
244     if (index < -backListCount())
245         return nullptr;
246     
247     if (index > forwardListCount())
248         return nullptr;
249         
250     return m_entries[index + m_currentIndex].ptr();
251 }
252
253 int WebBackForwardList::backListCount() const
254 {
255     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
256
257     return m_page && m_hasCurrentIndex ? m_currentIndex : 0;
258 }
259
260 int WebBackForwardList::forwardListCount() const
261 {
262     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
263
264     return m_page && m_hasCurrentIndex ? m_entries.size() - (m_currentIndex + 1) : 0;
265 }
266
267 Ref<API::Array> WebBackForwardList::backList() const
268 {
269     return backListAsAPIArrayWithLimit(backListCount());
270 }
271
272 Ref<API::Array> WebBackForwardList::forwardList() const
273 {
274     return forwardListAsAPIArrayWithLimit(forwardListCount());
275 }
276
277 Ref<API::Array> WebBackForwardList::backListAsAPIArrayWithLimit(unsigned limit) const
278 {
279     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
280
281     if (!m_page || !m_hasCurrentIndex)
282         return API::Array::create();
283
284     unsigned backListSize = static_cast<unsigned>(backListCount());
285     unsigned size = std::min(backListSize, limit);
286     if (!size)
287         return API::Array::create();
288
289     Vector<RefPtr<API::Object>> vector;
290     vector.reserveInitialCapacity(size);
291
292     ASSERT(backListSize >= size);
293     for (unsigned i = backListSize - size; i < backListSize; ++i)
294         vector.uncheckedAppend(m_entries[i].ptr());
295
296     return API::Array::create(WTFMove(vector));
297 }
298
299 Ref<API::Array> WebBackForwardList::forwardListAsAPIArrayWithLimit(unsigned limit) const
300 {
301     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
302
303     if (!m_page || !m_hasCurrentIndex)
304         return API::Array::create();
305
306     unsigned size = std::min(static_cast<unsigned>(forwardListCount()), limit);
307     if (!size)
308         return API::Array::create();
309
310     Vector<RefPtr<API::Object>> vector;
311     vector.reserveInitialCapacity(size);
312
313     unsigned last = m_currentIndex + size;
314     ASSERT(last < m_entries.size());
315     for (unsigned i = m_currentIndex + 1; i <= last; ++i)
316         vector.uncheckedAppend(m_entries[i].ptr());
317
318     return API::Array::create(WTFMove(vector));
319 }
320
321 void WebBackForwardList::removeAllItems()
322 {
323     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
324
325     Vector<Ref<WebBackForwardListItem>> removedItems;
326
327     for (auto& entry : m_entries) {
328         didRemoveItem(entry);
329         removedItems.append(WTFMove(entry));
330     }
331
332     m_entries.clear();
333     m_hasCurrentIndex = false;
334     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
335 }
336
337 void WebBackForwardList::clear()
338 {
339     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
340
341     size_t size = m_entries.size();
342     if (!m_page || size <= 1)
343         return;
344
345     RefPtr<WebBackForwardListItem> currentItem = this->currentItem();
346     Vector<Ref<WebBackForwardListItem>> removedItems;
347
348     if (!currentItem) {
349         // We should only ever have no current item if we also have no current item index.
350         ASSERT(!m_hasCurrentIndex);
351
352         // But just in case it does happen in practice we should get back into a consistent state now.
353         for (size_t i = 0; i < size; ++i) {
354             didRemoveItem(m_entries[i]);
355             removedItems.append(WTFMove(m_entries[i]));
356         }
357
358         m_entries.clear();
359         m_hasCurrentIndex = false;
360         m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
361
362         return;
363     }
364
365     for (size_t i = 0; i < size; ++i) {
366         if (m_entries[i].ptr() != currentItem)
367             didRemoveItem(m_entries[i]);
368     }
369
370     removedItems.reserveCapacity(size - 1);
371     for (size_t i = 0; i < size; ++i) {
372         if (i != m_currentIndex && m_hasCurrentIndex)
373             removedItems.append(WTFMove(m_entries[i]));
374     }
375
376     m_currentIndex = 0;
377
378     m_entries.clear();
379     if (currentItem)
380         m_entries.append(currentItem.releaseNonNull());
381     else
382         m_hasCurrentIndex = false;
383     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
384 }
385
386 BackForwardListState WebBackForwardList::backForwardListState(WTF::Function<bool (WebBackForwardListItem&)>&& filter) const
387 {
388     ASSERT(!m_hasCurrentIndex || m_currentIndex < m_entries.size());
389
390     BackForwardListState backForwardListState;
391     if (m_hasCurrentIndex)
392         backForwardListState.currentIndex = m_currentIndex;
393
394     for (size_t i = 0; i < m_entries.size(); ++i) {
395         auto& entry = m_entries[i];
396
397         if (filter && !filter(entry)) {
398             auto& currentIndex = backForwardListState.currentIndex;
399             if (currentIndex && i <= currentIndex.value() && currentIndex.value())
400                 --currentIndex.value();
401
402             continue;
403         }
404
405         backForwardListState.items.append(entry->itemState());
406     }
407
408     if (backForwardListState.items.isEmpty())
409         backForwardListState.currentIndex = std::nullopt;
410     else if (backForwardListState.items.size() <= backForwardListState.currentIndex.value())
411         backForwardListState.currentIndex = backForwardListState.items.size() - 1;
412
413     return backForwardListState;
414 }
415
416 void WebBackForwardList::restoreFromState(BackForwardListState backForwardListState)
417 {
418     Vector<Ref<WebBackForwardListItem>> items;
419     items.reserveInitialCapacity(backForwardListState.items.size());
420
421     for (auto& backForwardListItemState : backForwardListState.items) {
422         backForwardListItemState.identifier = { Process::identifier(), generateObjectIdentifier<BackForwardItemIdentifier::ItemIdentifierType>() };
423         items.uncheckedAppend(WebBackForwardListItem::create(WTFMove(backForwardListItemState), m_page->pageID()));
424     }
425     m_hasCurrentIndex = !!backForwardListState.currentIndex;
426     m_currentIndex = backForwardListState.currentIndex.value_or(0);
427     m_entries = WTFMove(items);
428 }
429
430 Vector<BackForwardListItemState> WebBackForwardList::itemStates() const
431 {
432     Vector<BackForwardListItemState> itemStates;
433     itemStates.reserveInitialCapacity(m_entries.size());
434
435     for (const auto& entry : m_entries)
436         itemStates.uncheckedAppend(entry->itemState());
437
438     return itemStates;
439 }
440
441 void WebBackForwardList::didRemoveItem(WebBackForwardListItem& backForwardListItem)
442 {
443     m_page->backForwardRemovedItem(backForwardListItem.itemID());
444
445 #if PLATFORM(COCOA)
446     backForwardListItem.setSnapshot(nullptr);
447 #endif
448 }
449
450 } // namespace WebKit