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