[iOS] Replace "node assistance" terminology in WebKit with "focused element"
[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 "Logging.h"
31 #include "SessionState.h"
32 #include "WebPageProxy.h"
33 #include <WebCore/DiagnosticLoggingClient.h>
34 #include <WebCore/DiagnosticLoggingKeys.h>
35 #include <wtf/DebugUtilities.h>
36 #include <wtf/text/StringBuilder.h>
37
38 namespace WebKit {
39 using namespace WebCore;
40
41 static const unsigned DefaultCapacity = 100;
42
43 WebBackForwardList::WebBackForwardList(WebPageProxy& page)
44     : m_page(&page)
45 {
46     LOG(BackForward, "(Back/Forward) Created WebBackForwardList %p", this);
47 }
48
49 WebBackForwardList::~WebBackForwardList()
50 {
51     LOG(BackForward, "(Back/Forward) Destroying WebBackForwardList %p", this);
52
53     // A WebBackForwardList should never be destroyed unless it's associated page has been closed or is invalid.
54     ASSERT((!m_page && !m_currentIndex) || !m_page->isValid());
55 }
56
57 WebBackForwardListItem* WebBackForwardList::itemForID(const BackForwardItemIdentifier& identifier)
58 {
59     if (!m_page)
60         return nullptr;
61
62     auto* item = WebBackForwardListItem::itemForID(identifier);
63     if (!item)
64         return nullptr;
65
66     ASSERT(item->pageID() == m_page->pageID());
67     return item;
68 }
69
70 void WebBackForwardList::pageClosed()
71 {
72     LOG(BackForward, "(Back/Forward) WebBackForwardList %p had its page closed with current size %zu", this, m_entries.size());
73
74     // We should have always started out with an m_page and we should never close the page twice.
75     ASSERT(m_page);
76
77     if (m_page) {
78         size_t size = m_entries.size();
79         for (size_t i = 0; i < size; ++i)
80             didRemoveItem(m_entries[i]);
81     }
82
83     m_page = nullptr;
84     m_entries.clear();
85     m_currentIndex = WTF::nullopt;
86 }
87
88 void WebBackForwardList::addItem(Ref<WebBackForwardListItem>&& newItem)
89 {
90     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
91
92     if (!m_page)
93         return;
94
95     Vector<Ref<WebBackForwardListItem>> removedItems;
96     
97     if (m_currentIndex) {
98         m_page->recordAutomaticNavigationSnapshot();
99
100         // Toss everything in the forward list.
101         unsigned targetSize = *m_currentIndex + 1;
102         removedItems.reserveCapacity(m_entries.size() - targetSize);
103         while (m_entries.size() > targetSize) {
104             didRemoveItem(m_entries.last());
105             removedItems.append(WTFMove(m_entries.last()));
106             m_entries.removeLast();
107         }
108
109         // Toss the first item if the list is getting too big, as long as we're not using it
110         // (or even if we are, if we only want 1 entry).
111         if (m_entries.size() >= DefaultCapacity && (*m_currentIndex)) {
112             didRemoveItem(m_entries[0]);
113             removedItems.append(WTFMove(m_entries[0]));
114             m_entries.remove(0);
115
116             if (m_entries.isEmpty())
117                 m_currentIndex = WTF::nullopt;
118             else
119                 --*m_currentIndex;
120         }
121     } else {
122         // If we have no current item index we should also not have any entries.
123         ASSERT(m_entries.isEmpty());
124
125         // But just in case it does happen in practice we'll get back in to a consistent state now before adding the new item.
126         size_t size = m_entries.size();
127         for (size_t i = 0; i < size; ++i) {
128             didRemoveItem(m_entries[i]);
129             removedItems.append(WTFMove(m_entries[i]));
130         }
131         m_entries.clear();
132     }
133
134     bool shouldKeepCurrentItem = true;
135
136     if (!m_currentIndex) {
137         ASSERT(m_entries.isEmpty());
138         m_currentIndex = 0;
139     } else {
140         shouldKeepCurrentItem = m_page->shouldKeepCurrentBackForwardListItemInList(m_entries[*m_currentIndex]);
141         if (shouldKeepCurrentItem)
142             ++*m_currentIndex;
143     }
144
145     auto* newItemPtr = newItem.ptr();
146     if (!shouldKeepCurrentItem) {
147         // m_current should never be pointing past the end of the entries Vector.
148         // If it is, something has gone wrong and we should not try to swap in the new item.
149         ASSERT(*m_currentIndex < m_entries.size());
150
151         removedItems.append(m_entries[*m_currentIndex].copyRef());
152         m_entries[*m_currentIndex] = WTFMove(newItem);
153     } else {
154         // m_current should never be pointing more than 1 past the end of the entries Vector.
155         // If it is, something has gone wrong and we should not try to insert the new item.
156         ASSERT(*m_currentIndex <= m_entries.size());
157
158         if (*m_currentIndex <= m_entries.size())
159             m_entries.insert(*m_currentIndex, WTFMove(newItem));
160     }
161
162     LOG(BackForward, "(Back/Forward) WebBackForwardList %p added an item. Current size %zu, current index %zu, threw away %zu items", this, m_entries.size(), *m_currentIndex, removedItems.size());
163     m_page->didChangeBackForwardList(newItemPtr, WTFMove(removedItems));
164 }
165
166 void WebBackForwardList::goToItem(WebBackForwardListItem& item)
167 {
168     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
169
170     if (!m_entries.size() || !m_page || !m_currentIndex)
171         return;
172
173     size_t targetIndex = notFound;
174     for (size_t i = 0; i < m_entries.size(); ++i) {
175         if (m_entries[i].ptr() == &item) {
176             targetIndex = i;
177             break;
178         }
179     }
180
181     // If the target item wasn't even in the list, there's nothing else to do.
182     if (targetIndex == notFound) {
183         LOG(BackForward, "(Back/Forward) WebBackForwardList %p could not go to item %s (%s) because it was not found", this, item.itemID().logString(), item.url().utf8().data());
184         return;
185     }
186
187     if (targetIndex < *m_currentIndex) {
188         unsigned delta = m_entries.size() - targetIndex - 1;
189         String deltaValue = delta > 10 ? "over10"_s : String::number(delta);
190         m_page->logDiagnosticMessage(WebCore::DiagnosticLoggingKeys::backNavigationDeltaKey(), deltaValue, ShouldSample::No);
191     }
192
193     // If we're going to an item different from the current item, ask the client if the current
194     // item should remain in the list.
195     auto& currentItem = m_entries[*m_currentIndex];
196     bool shouldKeepCurrentItem = true;
197     if (currentItem.ptr() != &item) {
198         m_page->recordAutomaticNavigationSnapshot();
199         shouldKeepCurrentItem = m_page->shouldKeepCurrentBackForwardListItemInList(m_entries[*m_currentIndex]);
200     }
201
202     // If the client said to remove the current item, remove it and then update the target index.
203     Vector<Ref<WebBackForwardListItem>> removedItems;
204     if (!shouldKeepCurrentItem) {
205         removedItems.append(currentItem.copyRef());
206         m_entries.remove(*m_currentIndex);
207         targetIndex = notFound;
208         for (size_t i = 0; i < m_entries.size(); ++i) {
209             if (m_entries[i].ptr() == &item) {
210                 targetIndex = i;
211                 break;
212             }
213         }
214         ASSERT(targetIndex != notFound);
215     }
216
217     m_currentIndex = targetIndex;
218
219     LOG(BackForward, "(Back/Forward) WebBackForwardList %p going to item %s, is now at index %zu", this, item.itemID().logString(), targetIndex);
220     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
221 }
222
223 WebBackForwardListItem* WebBackForwardList::currentItem() const
224 {
225     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
226
227     return m_page && m_currentIndex ? m_entries[*m_currentIndex].ptr() : nullptr;
228 }
229
230 WebBackForwardListItem* WebBackForwardList::backItem() const
231 {
232     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
233
234     return m_page && m_currentIndex && *m_currentIndex ? m_entries[*m_currentIndex - 1].ptr() : nullptr;
235 }
236
237 WebBackForwardListItem* WebBackForwardList::forwardItem() const
238 {
239     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
240
241     return m_page && m_currentIndex && m_entries.size() && *m_currentIndex < m_entries.size() - 1 ? m_entries[*m_currentIndex + 1].ptr() : nullptr;
242 }
243
244 WebBackForwardListItem* WebBackForwardList::itemAtIndex(int index) const
245 {
246     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
247
248     if (!m_currentIndex || !m_page)
249         return nullptr;
250     
251     // Do range checks without doing math on index to avoid overflow.
252     if (index < 0 && static_cast<unsigned>(-index) > backListCount())
253         return nullptr;
254     
255     if (index > 0 && static_cast<unsigned>(index) > forwardListCount())
256         return nullptr;
257
258     return m_entries[index + *m_currentIndex].ptr();
259 }
260
261 unsigned WebBackForwardList::backListCount() const
262 {
263     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
264
265     return m_page && m_currentIndex ? *m_currentIndex : 0;
266 }
267
268 unsigned WebBackForwardList::forwardListCount() const
269 {
270     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
271
272     return m_page && m_currentIndex ? m_entries.size() - (*m_currentIndex + 1) : 0;
273 }
274
275 Ref<API::Array> WebBackForwardList::backList() const
276 {
277     return backListAsAPIArrayWithLimit(backListCount());
278 }
279
280 Ref<API::Array> WebBackForwardList::forwardList() const
281 {
282     return forwardListAsAPIArrayWithLimit(forwardListCount());
283 }
284
285 Ref<API::Array> WebBackForwardList::backListAsAPIArrayWithLimit(unsigned limit) const
286 {
287     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
288
289     if (!m_page || !m_currentIndex)
290         return API::Array::create();
291
292     unsigned backListSize = static_cast<unsigned>(backListCount());
293     unsigned size = std::min(backListSize, limit);
294     if (!size)
295         return API::Array::create();
296
297     Vector<RefPtr<API::Object>> vector;
298     vector.reserveInitialCapacity(size);
299
300     ASSERT(backListSize >= size);
301     for (unsigned i = backListSize - size; i < backListSize; ++i)
302         vector.uncheckedAppend(m_entries[i].ptr());
303
304     return API::Array::create(WTFMove(vector));
305 }
306
307 Ref<API::Array> WebBackForwardList::forwardListAsAPIArrayWithLimit(unsigned limit) const
308 {
309     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
310
311     if (!m_page || !m_currentIndex)
312         return API::Array::create();
313
314     unsigned size = std::min(static_cast<unsigned>(forwardListCount()), limit);
315     if (!size)
316         return API::Array::create();
317
318     Vector<RefPtr<API::Object>> vector;
319     vector.reserveInitialCapacity(size);
320
321     size_t last = *m_currentIndex + size;
322     ASSERT(last < m_entries.size());
323     for (size_t i = *m_currentIndex + 1; i <= last; ++i)
324         vector.uncheckedAppend(m_entries[i].ptr());
325
326     return API::Array::create(WTFMove(vector));
327 }
328
329 void WebBackForwardList::removeAllItems()
330 {
331     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
332
333     LOG(BackForward, "(Back/Forward) WebBackForwardList %p removeAllItems (has %zu of them)", this, m_entries.size());
334
335     Vector<Ref<WebBackForwardListItem>> removedItems;
336
337     for (auto& entry : m_entries) {
338         didRemoveItem(entry);
339         removedItems.append(WTFMove(entry));
340     }
341
342     m_entries.clear();
343     m_currentIndex = WTF::nullopt;
344     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
345 }
346
347 void WebBackForwardList::clear()
348 {
349     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
350
351     LOG(BackForward, "(Back/Forward) WebBackForwardList %p clear (has %zu of them)", this, m_entries.size());
352
353     size_t size = m_entries.size();
354     if (!m_page || size <= 1)
355         return;
356
357     RefPtr<WebBackForwardListItem> currentItem = this->currentItem();
358     Vector<Ref<WebBackForwardListItem>> removedItems;
359
360     if (!currentItem) {
361         // We should only ever have no current item if we also have no current item index.
362         ASSERT(!m_currentIndex);
363
364         // But just in case it does happen in practice we should get back into a consistent state now.
365         for (size_t i = 0; i < size; ++i) {
366             didRemoveItem(m_entries[i]);
367             removedItems.append(WTFMove(m_entries[i]));
368         }
369
370         m_entries.clear();
371         m_currentIndex = WTF::nullopt;
372         m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
373
374         return;
375     }
376
377     for (size_t i = 0; i < size; ++i) {
378         if (m_entries[i].ptr() != currentItem)
379             didRemoveItem(m_entries[i]);
380     }
381
382     removedItems.reserveCapacity(size - 1);
383     for (size_t i = 0; i < size; ++i) {
384         if (m_currentIndex && i != *m_currentIndex)
385             removedItems.append(WTFMove(m_entries[i]));
386     }
387
388     m_currentIndex = 0;
389
390     m_entries.clear();
391     if (currentItem)
392         m_entries.append(currentItem.releaseNonNull());
393     else
394         m_currentIndex = WTF::nullopt;
395     m_page->didChangeBackForwardList(nullptr, WTFMove(removedItems));
396 }
397
398 BackForwardListState WebBackForwardList::backForwardListState(WTF::Function<bool (WebBackForwardListItem&)>&& filter) const
399 {
400     ASSERT(!m_currentIndex || *m_currentIndex < m_entries.size());
401
402     BackForwardListState backForwardListState;
403     if (m_currentIndex)
404         backForwardListState.currentIndex = *m_currentIndex;
405
406     for (size_t i = 0; i < m_entries.size(); ++i) {
407         auto& entry = m_entries[i];
408
409         if (filter && !filter(entry)) {
410             auto& currentIndex = backForwardListState.currentIndex;
411             if (currentIndex && i <= currentIndex.value() && currentIndex.value())
412                 --currentIndex.value();
413
414             continue;
415         }
416
417         backForwardListState.items.append(entry->itemState());
418     }
419
420     if (backForwardListState.items.isEmpty())
421         backForwardListState.currentIndex = WTF::nullopt;
422     else if (backForwardListState.items.size() <= backForwardListState.currentIndex.value())
423         backForwardListState.currentIndex = backForwardListState.items.size() - 1;
424
425     return backForwardListState;
426 }
427
428 void WebBackForwardList::restoreFromState(BackForwardListState backForwardListState)
429 {
430     if (!m_page)
431         return;
432
433     Vector<Ref<WebBackForwardListItem>> items;
434     items.reserveInitialCapacity(backForwardListState.items.size());
435
436     for (auto& backForwardListItemState : backForwardListState.items) {
437         backForwardListItemState.identifier = { Process::identifier(), generateObjectIdentifier<BackForwardItemIdentifier::ItemIdentifierType>() };
438         items.uncheckedAppend(WebBackForwardListItem::create(WTFMove(backForwardListItemState), m_page->pageID()));
439     }
440     m_currentIndex = backForwardListState.currentIndex ? Optional<size_t>(*backForwardListState.currentIndex) : WTF::nullopt;
441     m_entries = WTFMove(items);
442
443     LOG(BackForward, "(Back/Forward) WebBackForwardList %p restored from state (has %zu entries)", this, m_entries.size());
444 }
445
446 Vector<BackForwardListItemState> WebBackForwardList::filteredItemStates(Function<bool(WebBackForwardListItem&)>&& functor) const
447 {
448     Vector<BackForwardListItemState> itemStates;
449     itemStates.reserveInitialCapacity(m_entries.size());
450
451     for (const auto& entry : m_entries) {
452         if (functor(entry))
453             itemStates.uncheckedAppend(entry->itemState());
454     }
455
456     return itemStates;
457 }
458
459 Vector<BackForwardListItemState> WebBackForwardList::itemStates() const
460 {
461     return filteredItemStates([](WebBackForwardListItem&) {
462         return true;
463     });
464 }
465
466 void WebBackForwardList::didRemoveItem(WebBackForwardListItem& backForwardListItem)
467 {
468     m_page->backForwardRemovedItem(backForwardListItem.itemID());
469
470     backForwardListItem.setSuspendedPage(nullptr);
471 #if PLATFORM(COCOA)
472     backForwardListItem.setSnapshot(nullptr);
473 #endif
474 }
475
476
477 #if !LOG_DISABLED
478 const char* WebBackForwardList::loggingString()
479 {
480     StringBuilder builder;
481     builder.append(String::format("WebBackForwardList %p - %zu entries, has current index %s (%zu)", this, m_entries.size(), m_currentIndex ? "YES" : "NO", m_currentIndex ? *m_currentIndex : 0));
482
483     for (size_t i = 0; i < m_entries.size(); ++i) {
484         builder.append("\n");
485         if (m_currentIndex && *m_currentIndex == i)
486             builder.append(" * ");
487         else
488             builder.append(" - ");
489
490         builder.append(m_entries[i]->loggingString());
491     }
492
493     return debugString("\n", builder.toString());
494 }
495 #endif // !LOG_DISABLED
496
497 } // namespace WebKit