mirror of
https://github.com/LadybirdBrowser/ladybird.git
synced 2026-06-19 08:11:58 +00:00
766bc991ed
Problem: While a document was concurrently loaded, a burst of sync same- document history navigations (e.g. a pushState flood) could spin the UI process at full CPU — and on slow/Sanitizer builds, intermittently time out other tests (since one WebContent process is reused across tests). Cause: The UI process keeps an authoritative session-history mirror, and merges each WebContent snapshot into it. find_merge_anchor compares each local entry against each incoming one. Every URL comparison serializes both URLs. When a snapshot briefly diverges from the mirror, the anchor is no longer near the end. So, the search degraded to a deep quadratic walk — with a string serialization per-comparison. A flood compounded that from both ends: Every pushState added a top-level entry — driving the count each walk must cover into the hundreds — and also triggered a history update. So, the merge ran again for every one of them. Fix: Index the incoming entries by serialized URL once — keyed as URL equality compares (full serialization, fragment included). So, the URL- keyed anchor searches are linear, not quadratic.
1159 lines
50 KiB
C++
1159 lines
50 KiB
C++
/*
|
|
* Copyright (c) 2026-present, the Ladybird developers.
|
|
*
|
|
* SPDX-License-Identifier: BSD-2-Clause
|
|
*/
|
|
|
|
#include <AK/HashMap.h>
|
|
#include <AK/HashTable.h>
|
|
#include <AK/NumericLimits.h>
|
|
#include <AK/QuickSort.h>
|
|
#include <LibWebView/SessionHistory.h>
|
|
|
|
namespace WebView {
|
|
|
|
struct SessionHistoryMergeAnchor {
|
|
size_t local_index { 0 };
|
|
size_t incoming_index { 0 };
|
|
};
|
|
|
|
enum class StepTranslationMode {
|
|
TopLevel,
|
|
Nested,
|
|
};
|
|
|
|
struct DocumentStateIdTranslationState {
|
|
HashMap<u64, u64> translated_document_state_ids;
|
|
u64 next_document_state_id { 1 };
|
|
};
|
|
|
|
struct DocumentStateIdCanonicalizationState {
|
|
HashMap<u64, u64> canonical_document_state_ids;
|
|
u64 next_document_state_id { 1 };
|
|
};
|
|
|
|
static bool steps_are_valid(Vector<i32> const& steps)
|
|
{
|
|
Optional<i32> previous_step;
|
|
for (auto const& step : steps) {
|
|
if (step < 0)
|
|
return false;
|
|
if (previous_step.has_value() && step <= *previous_step)
|
|
return false;
|
|
previous_step = step;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
static bool entries_are_valid(Vector<TraversableSessionHistory::Entry> const& entries)
|
|
{
|
|
Optional<i32> previous_step;
|
|
for (auto const& entry : entries) {
|
|
if (entry.step < 0)
|
|
return false;
|
|
if (previous_step.has_value() && entry.step <= *previous_step)
|
|
return false;
|
|
for (auto const& nested_history : entry.document_state.nested_histories) {
|
|
if (!entries_are_valid(nested_history.entries))
|
|
return false;
|
|
}
|
|
previous_step = entry.step;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
static bool entries_match(Vector<TraversableSessionHistory::Entry> const& a, Vector<TraversableSessionHistory::Entry> const& b)
|
|
{
|
|
if (a.size() != b.size())
|
|
return false;
|
|
|
|
for (size_t i = 0; i < a.size(); ++i) {
|
|
if (Web::HTML::session_history_entry_descriptors_match(a[i], b[i]))
|
|
continue;
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
static bool seed_ack_nested_histories_match(Vector<Web::HTML::SessionHistoryNestedHistoryDescriptor> const&, Vector<Web::HTML::SessionHistoryNestedHistoryDescriptor> const&, Optional<size_t>);
|
|
|
|
static bool current_unknown_entry_seed_ack_matches(TraversableSessionHistory::Entry const& a, TraversableSessionHistory::Entry const& b)
|
|
{
|
|
if (a.step != b.step || a.url != b.url)
|
|
return false;
|
|
if (!a.classic_history_api_state.is_empty() && a.classic_history_api_state != b.classic_history_api_state)
|
|
return false;
|
|
if (!a.navigation_api_state.is_empty() && a.navigation_api_state != b.navigation_api_state)
|
|
return false;
|
|
if (!a.navigation_api_key.is_empty() && a.navigation_api_key != b.navigation_api_key)
|
|
return false;
|
|
if (!a.navigation_api_id.is_empty() && a.navigation_api_id != b.navigation_api_id)
|
|
return false;
|
|
if (a.scroll_restoration_mode != b.scroll_restoration_mode)
|
|
return false;
|
|
if (a.scroll_position_data.viewport_scroll_position.has_value() && a.scroll_position_data != b.scroll_position_data)
|
|
return false;
|
|
return seed_ack_nested_histories_match(a.document_state.nested_histories, b.document_state.nested_histories, {});
|
|
}
|
|
|
|
static bool seed_ack_entries_match(Vector<TraversableSessionHistory::Entry> const& a, Vector<TraversableSessionHistory::Entry> const& b, Optional<size_t> current_unknown_entry_index)
|
|
{
|
|
if (a.size() != b.size())
|
|
return false;
|
|
|
|
for (size_t i = 0; i < a.size(); ++i) {
|
|
if (current_unknown_entry_index.has_value() && i == *current_unknown_entry_index && current_unknown_entry_seed_ack_matches(a[i], b[i]))
|
|
continue;
|
|
if (Web::HTML::session_history_entry_descriptors_match_ignoring_document_state_id(a[i], b[i]))
|
|
continue;
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
static bool seed_ack_nested_histories_match(Vector<Web::HTML::SessionHistoryNestedHistoryDescriptor> const& a, Vector<Web::HTML::SessionHistoryNestedHistoryDescriptor> const& b, Optional<size_t> current_unknown_entry_index)
|
|
{
|
|
if (a.size() != b.size())
|
|
return false;
|
|
|
|
for (size_t i = 0; i < a.size(); ++i) {
|
|
if (a[i].id == b[i].id && seed_ack_entries_match(a[i].entries, b[i].entries, current_unknown_entry_index))
|
|
continue;
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
static bool steps_match(Vector<i32> const& a, Vector<i32> const& b)
|
|
{
|
|
if (a.size() != b.size())
|
|
return false;
|
|
|
|
for (size_t i = 0; i < a.size(); ++i) {
|
|
if (a[i] == b[i])
|
|
continue;
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
static bool entry_steps_match(TraversableSessionHistory::Entry const& a, TraversableSessionHistory::Entry const& b)
|
|
{
|
|
if (a.step != b.step)
|
|
return false;
|
|
if (a.document_state.nested_histories.size() != b.document_state.nested_histories.size())
|
|
return false;
|
|
|
|
for (size_t i = 0; i < a.document_state.nested_histories.size(); ++i) {
|
|
auto const& a_nested_history = a.document_state.nested_histories[i];
|
|
auto const& b_nested_history = b.document_state.nested_histories[i];
|
|
if (a_nested_history.id != b_nested_history.id || a_nested_history.entries.size() != b_nested_history.entries.size())
|
|
return false;
|
|
for (size_t j = 0; j < a_nested_history.entries.size(); ++j) {
|
|
if (!entry_steps_match(a_nested_history.entries[j], b_nested_history.entries[j]))
|
|
return false;
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
static bool entries_have_matching_nonzero_document_state_id(TraversableSessionHistory::Entry const& a, TraversableSessionHistory::Entry const& b)
|
|
{
|
|
return a.document_state.id != 0 && a.document_state.id == b.document_state.id;
|
|
}
|
|
|
|
// https://html.spec.whatwg.org/multipage/browsing-the-web.html#getting-all-used-history-steps
|
|
static Vector<i32> get_all_used_history_steps(Vector<TraversableSessionHistory::Entry> const& traversable_session_history_entries)
|
|
{
|
|
// 1. Assert: this is running within traversable's session history traversal queue.
|
|
|
|
// 2. Let steps be an empty ordered set of non-negative integers.
|
|
OrderedHashTable<i32> steps;
|
|
|
|
// 3. Let entryLists be the ordered set « traversable's session history entries ».
|
|
Vector<Vector<TraversableSessionHistory::Entry> const*> entry_lists { &traversable_session_history_entries };
|
|
|
|
// 4. For each entryList of entryLists:
|
|
while (!entry_lists.is_empty()) {
|
|
auto const* entry_list = entry_lists.take_first();
|
|
|
|
// 1. For each entry of entryList:
|
|
for (auto const& entry : *entry_list) {
|
|
// 1. Append entry's step to steps.
|
|
steps.set(entry.step);
|
|
|
|
// 2. For each nestedHistory of entry's document state's nested histories, append
|
|
// nestedHistory's entries list to entryLists.
|
|
for (auto const& nested_history : entry.document_state.nested_histories)
|
|
entry_lists.append(&nested_history.entries);
|
|
}
|
|
}
|
|
|
|
// 5. Return steps, sorted.
|
|
auto sorted_steps = steps.values();
|
|
quick_sort(sorted_steps);
|
|
return sorted_steps;
|
|
}
|
|
|
|
static bool entries_and_used_steps_are_consistent(Vector<TraversableSessionHistory::Entry> const& entries, Vector<i32> const& used_steps)
|
|
{
|
|
return steps_match(get_all_used_history_steps(entries), used_steps);
|
|
}
|
|
|
|
static bool entries_have_nested_histories(Vector<TraversableSessionHistory::Entry> const& entries)
|
|
{
|
|
for (auto const& entry : entries) {
|
|
if (!entry.document_state.nested_histories.is_empty())
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
static void recompute_used_steps(Vector<TraversableSessionHistory::Entry> const& entries, Vector<i32>& used_steps, Optional<size_t>& current_used_step_index, i32 current_step)
|
|
{
|
|
used_steps = get_all_used_history_steps(entries);
|
|
current_used_step_index = used_steps.find_first_index(current_step);
|
|
}
|
|
|
|
static Optional<size_t> top_level_entry_index_for_step(Vector<TraversableSessionHistory::Entry> const& entries, i32 step)
|
|
{
|
|
Optional<size_t> result;
|
|
for (size_t i = 0; i < entries.size(); ++i) {
|
|
if (entries[i].step > step)
|
|
break;
|
|
result = i;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
static TraversableSessionHistory::Entry const* top_level_entry_for_step(Vector<TraversableSessionHistory::Entry> const& entries, i32 step)
|
|
{
|
|
auto index = top_level_entry_index_for_step(entries, step);
|
|
if (!index.has_value())
|
|
return nullptr;
|
|
return &entries[*index];
|
|
}
|
|
|
|
static TraversableSessionHistory::Entry const* entry_for_step_in_entry_list(Vector<TraversableSessionHistory::Entry> const& entries, i32 step)
|
|
{
|
|
TraversableSessionHistory::Entry const* result = nullptr;
|
|
for (auto const& entry : entries) {
|
|
if (entry.step > step)
|
|
break;
|
|
result = &entry;
|
|
}
|
|
return result;
|
|
}
|
|
|
|
static bool nested_histories_need_restore_after_loading_entry(TraversableSessionHistory::Entry const& entry, i32 step)
|
|
{
|
|
for (auto const& nested_history : entry.document_state.nested_histories) {
|
|
auto target_entry = entry_for_step_in_entry_list(nested_history.entries, step);
|
|
if (!target_entry)
|
|
continue;
|
|
if (target_entry->step != entry.step)
|
|
return true;
|
|
if (nested_histories_need_restore_after_loading_entry(*target_entry, step))
|
|
return true;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
static void update_next_document_state_id(Vector<TraversableSessionHistory::Entry> const& entries, u64& next_document_state_id)
|
|
{
|
|
for (auto const& entry : entries) {
|
|
if (entry.document_state.id >= next_document_state_id)
|
|
next_document_state_id = entry.document_state.id + 1;
|
|
for (auto const& nested_history : entry.document_state.nested_histories)
|
|
update_next_document_state_id(nested_history.entries, next_document_state_id);
|
|
}
|
|
}
|
|
|
|
static u64 translate_incoming_document_state_id(u64 incoming_document_state_id, DocumentStateIdTranslationState& translation_state)
|
|
{
|
|
if (incoming_document_state_id == 0)
|
|
return 0;
|
|
|
|
if (auto translated_document_state_id = translation_state.translated_document_state_ids.get(incoming_document_state_id); translated_document_state_id.has_value())
|
|
return *translated_document_state_id;
|
|
|
|
auto translated_document_state_id = translation_state.next_document_state_id++;
|
|
VERIFY(translated_document_state_id != 0);
|
|
translation_state.translated_document_state_ids.set(incoming_document_state_id, translated_document_state_id);
|
|
return translated_document_state_id;
|
|
}
|
|
|
|
static void canonicalize_document_state_ids(Vector<TraversableSessionHistory::Entry>& entries, DocumentStateIdCanonicalizationState& canonicalization_state)
|
|
{
|
|
for (auto& entry : entries) {
|
|
if (entry.document_state.id != 0) {
|
|
auto canonical_document_state_id = canonicalization_state.canonical_document_state_ids.get(entry.document_state.id);
|
|
if (canonical_document_state_id.has_value()) {
|
|
entry.document_state.id = *canonical_document_state_id;
|
|
} else {
|
|
auto new_document_state_id = canonicalization_state.next_document_state_id++;
|
|
VERIFY(new_document_state_id != 0);
|
|
canonicalization_state.canonical_document_state_ids.set(entry.document_state.id, new_document_state_id);
|
|
entry.document_state.id = new_document_state_id;
|
|
}
|
|
}
|
|
|
|
for (auto& nested_history : entry.document_state.nested_histories)
|
|
canonicalize_document_state_ids(nested_history.entries, canonicalization_state);
|
|
}
|
|
}
|
|
|
|
static void canonicalize_document_state_ids(Vector<TraversableSessionHistory::Entry>& entries)
|
|
{
|
|
DocumentStateIdCanonicalizationState canonicalization_state;
|
|
canonicalize_document_state_ids(entries, canonicalization_state);
|
|
}
|
|
|
|
static Optional<i32> translate_incoming_step(i32 incoming_step, i32 incoming_anchor_step, i32 local_anchor_step, StepTranslationMode mode = StepTranslationMode::TopLevel, Optional<i32> nested_history_step_floor = {})
|
|
{
|
|
// AD-HOC: WebContent snapshots can describe only the history slice known to the current process. When merging
|
|
// such a partial snapshot into the UI-owned traversable session history mirror, translate the incoming
|
|
// step coordinates around the entry that anchors both histories.
|
|
if (mode == StepTranslationMode::Nested && incoming_step < incoming_anchor_step && (!nested_history_step_floor.has_value() || incoming_step < *nested_history_step_floor))
|
|
return local_anchor_step;
|
|
|
|
auto step_delta = static_cast<i64>(incoming_step) - static_cast<i64>(incoming_anchor_step);
|
|
if (step_delta < 0) {
|
|
if (mode != StepTranslationMode::Nested || !nested_history_step_floor.has_value() || incoming_step < *nested_history_step_floor)
|
|
return {};
|
|
if (-step_delta > local_anchor_step)
|
|
return {};
|
|
}
|
|
if (step_delta > NumericLimits<i32>::max() - local_anchor_step)
|
|
return {};
|
|
return local_anchor_step + static_cast<i32>(step_delta);
|
|
}
|
|
|
|
static Optional<Web::HTML::SessionHistoryNestedHistoryDescriptor> translate_incoming_nested_history(Web::HTML::SessionHistoryNestedHistoryDescriptor const&, i32 incoming_anchor_step, i32 local_anchor_step, DocumentStateIdTranslationState&, Optional<i32> nested_history_step_floor);
|
|
|
|
static Optional<Web::HTML::SessionHistoryDocumentStateDescriptor> translate_incoming_document_state_descriptor(Web::HTML::SessionHistoryDocumentStateDescriptor document_state, i32 incoming_anchor_step, i32 local_anchor_step, DocumentStateIdTranslationState& document_state_id_translation_state, Optional<i32> nested_history_step_floor)
|
|
{
|
|
document_state.id = translate_incoming_document_state_id(document_state.id, document_state_id_translation_state);
|
|
|
|
Vector<Web::HTML::SessionHistoryNestedHistoryDescriptor> nested_histories;
|
|
nested_histories.ensure_capacity(document_state.nested_histories.size());
|
|
for (auto const& nested_history : document_state.nested_histories) {
|
|
auto translated_nested_history = translate_incoming_nested_history(nested_history, incoming_anchor_step, local_anchor_step, document_state_id_translation_state, nested_history_step_floor);
|
|
if (!translated_nested_history.has_value())
|
|
return {};
|
|
nested_histories.unchecked_append(translated_nested_history.release_value());
|
|
}
|
|
|
|
document_state.nested_histories = move(nested_histories);
|
|
return document_state;
|
|
}
|
|
|
|
static Optional<TraversableSessionHistory::Entry> translate_incoming_entry(TraversableSessionHistory::Entry const& entry, i32 incoming_anchor_step, i32 local_anchor_step, DocumentStateIdTranslationState& document_state_id_translation_state, StepTranslationMode mode = StepTranslationMode::TopLevel, Optional<i32> nested_history_step_floor = {})
|
|
{
|
|
auto translated_step = translate_incoming_step(entry.step, incoming_anchor_step, local_anchor_step, mode, nested_history_step_floor);
|
|
if (!translated_step.has_value())
|
|
return {};
|
|
auto translated_document_state = translate_incoming_document_state_descriptor(entry.document_state, incoming_anchor_step, local_anchor_step, document_state_id_translation_state, nested_history_step_floor);
|
|
if (!translated_document_state.has_value())
|
|
return {};
|
|
|
|
return TraversableSessionHistory::Entry {
|
|
.step = *translated_step,
|
|
.url = entry.url,
|
|
.document_state = translated_document_state.release_value(),
|
|
.classic_history_api_state = entry.classic_history_api_state,
|
|
.navigation_api_state = entry.navigation_api_state,
|
|
.navigation_api_key = entry.navigation_api_key,
|
|
.navigation_api_id = entry.navigation_api_id,
|
|
.scroll_restoration_mode = entry.scroll_restoration_mode,
|
|
.scroll_position_data = entry.scroll_position_data,
|
|
};
|
|
}
|
|
|
|
static Optional<Web::HTML::SessionHistoryNestedHistoryDescriptor> translate_incoming_nested_history(Web::HTML::SessionHistoryNestedHistoryDescriptor const& nested_history, i32 incoming_anchor_step, i32 local_anchor_step, DocumentStateIdTranslationState& document_state_id_translation_state, Optional<i32> nested_history_step_floor)
|
|
{
|
|
Vector<TraversableSessionHistory::Entry> entries;
|
|
entries.ensure_capacity(nested_history.entries.size());
|
|
Optional<i32> previous_step;
|
|
for (auto const& entry : nested_history.entries) {
|
|
auto translated_entry = translate_incoming_entry(entry, incoming_anchor_step, local_anchor_step, document_state_id_translation_state, StepTranslationMode::Nested, nested_history_step_floor);
|
|
if (!translated_entry.has_value())
|
|
return {};
|
|
if (previous_step.has_value() && translated_entry->step <= *previous_step)
|
|
return {};
|
|
previous_step = translated_entry->step;
|
|
entries.unchecked_append(translated_entry.release_value());
|
|
}
|
|
|
|
return Web::HTML::SessionHistoryNestedHistoryDescriptor {
|
|
.id = nested_history.id,
|
|
.entries = move(entries),
|
|
};
|
|
}
|
|
|
|
static void clear_forward_session_history_entries(Vector<TraversableSessionHistory::Entry>& entries, i32 step)
|
|
{
|
|
// https://html.spec.whatwg.org/multipage/browsing-the-web.html#clear-the-forward-session-history
|
|
|
|
// 1. Assert: this is running within navigable's session history traversal queue.
|
|
|
|
// 2. Let step be the navigable's current session history step.
|
|
|
|
// 3. Let entryLists be the ordered set « navigable's session history entries ».
|
|
Vector<Vector<TraversableSessionHistory::Entry>*> entry_lists { &entries };
|
|
|
|
// 4. For each entryList of entryLists:
|
|
while (!entry_lists.is_empty()) {
|
|
auto* entry_list = entry_lists.take_first();
|
|
|
|
// 1. Remove every session history entry from entryList that has a step greater than step.
|
|
entry_list->remove_all_matching([step](auto const& entry) {
|
|
return entry.step > step;
|
|
});
|
|
|
|
// 2. For each entry of entryList:
|
|
for (auto& entry : *entry_list) {
|
|
// 1. For each nestedHistory of entry's document state's nested histories, append
|
|
// nestedHistory's entries list to entryLists.
|
|
for (auto& nested_history : entry.document_state.nested_histories)
|
|
entry_lists.append(&nested_history.entries);
|
|
}
|
|
}
|
|
}
|
|
|
|
static TraversableSessionHistory::Entry create_ui_process_session_history_entry(
|
|
i32 step,
|
|
URL::URL url,
|
|
Variant<Empty, String, Web::HTML::POSTResource> document_resource)
|
|
{
|
|
return {
|
|
.step = step,
|
|
.url = move(url),
|
|
.document_state = {
|
|
.id = 0,
|
|
.history_policy_container = Web::HTML::DocumentState::Client::Tag,
|
|
.request_referrer = Web::Fetch::Infrastructure::Request::Referrer::Client,
|
|
.request_referrer_policy = Web::ReferrerPolicy::DEFAULT_REFERRER_POLICY,
|
|
.initiator_origin = {},
|
|
.origin = {},
|
|
.about_base_url = {},
|
|
.resource = move(document_resource),
|
|
.reload_pending = false,
|
|
.ever_populated = false,
|
|
.navigable_target_name = {},
|
|
.nested_histories = {},
|
|
},
|
|
.classic_history_api_state = {},
|
|
.navigation_api_state = {},
|
|
.navigation_api_key = {},
|
|
.navigation_api_id = {},
|
|
.scroll_restoration_mode = Web::HTML::ScrollRestorationMode::Auto,
|
|
.scroll_position_data = {},
|
|
};
|
|
}
|
|
|
|
void TraversableSessionHistory::navigate(URL::URL url)
|
|
{
|
|
navigate(move(url), Empty {});
|
|
}
|
|
|
|
void TraversableSessionHistory::navigate(URL::URL url, Variant<Empty, String, Web::HTML::POSTResource> document_resource)
|
|
{
|
|
forget_web_content_state();
|
|
|
|
if (!m_current_used_step_index.has_value()) {
|
|
m_entries.clear();
|
|
m_used_steps.clear();
|
|
m_entries.append(create_ui_process_session_history_entry(0, move(url), move(document_resource)));
|
|
m_used_steps.append(0);
|
|
m_current_used_step_index = 0;
|
|
return;
|
|
}
|
|
|
|
auto current_step = m_used_steps[*m_current_used_step_index];
|
|
VERIFY(current_step < NumericLimits<i32>::max());
|
|
clear_forward_session_history_entries(m_entries, current_step);
|
|
auto step = current_step + 1;
|
|
m_used_steps.remove_all_matching([current_step](auto const& used_step) {
|
|
return used_step > current_step;
|
|
});
|
|
m_entries.append(create_ui_process_session_history_entry(step, move(url), move(document_resource)));
|
|
m_used_steps.append(step);
|
|
m_current_used_step_index = m_used_steps.size() - 1;
|
|
}
|
|
|
|
void TraversableSessionHistory::clear()
|
|
{
|
|
m_entries.clear();
|
|
m_used_steps.clear();
|
|
m_current_used_step_index.clear();
|
|
forget_web_content_state();
|
|
}
|
|
|
|
void TraversableSessionHistory::replace_current_entry_url(URL::URL url)
|
|
{
|
|
forget_web_content_state();
|
|
|
|
if (!m_current_used_step_index.has_value()) {
|
|
navigate(move(url));
|
|
return;
|
|
}
|
|
|
|
auto current_top_level_entry_index = this->current_top_level_entry_index();
|
|
VERIFY(current_top_level_entry_index.has_value());
|
|
m_entries[*current_top_level_entry_index].url = move(url);
|
|
}
|
|
|
|
void TraversableSessionHistory::replace_current_entry(URL::URL url, Variant<Empty, String, Web::HTML::POSTResource> document_resource)
|
|
{
|
|
forget_web_content_state();
|
|
|
|
if (!m_current_used_step_index.has_value()) {
|
|
navigate(move(url), move(document_resource));
|
|
return;
|
|
}
|
|
|
|
auto current_top_level_entry_index = this->current_top_level_entry_index();
|
|
VERIFY(current_top_level_entry_index.has_value());
|
|
|
|
auto current_step = m_used_steps[*m_current_used_step_index];
|
|
m_entries[*current_top_level_entry_index] = create_ui_process_session_history_entry(
|
|
current_step, move(url), move(document_resource));
|
|
recompute_used_steps(m_entries, m_used_steps, m_current_used_step_index, current_step);
|
|
VERIFY(m_current_used_step_index.has_value());
|
|
}
|
|
|
|
void TraversableSessionHistory::mark_current_entry_reload_pending()
|
|
{
|
|
forget_web_content_state();
|
|
|
|
auto current_top_level_entry_index = this->current_top_level_entry_index();
|
|
if (!current_top_level_entry_index.has_value())
|
|
return;
|
|
|
|
// https://html.spec.whatwg.org/multipage/browsing-the-web.html#reload
|
|
// Set navigable's active session history entry's document state's reload
|
|
// pending to true.
|
|
m_entries[*current_top_level_entry_index].document_state.reload_pending = true;
|
|
}
|
|
|
|
void TraversableSessionHistory::clear_current_entry_reload_pending()
|
|
{
|
|
auto current_top_level_entry_index = this->current_top_level_entry_index();
|
|
if (!current_top_level_entry_index.has_value())
|
|
return;
|
|
|
|
m_entries[*current_top_level_entry_index].document_state.reload_pending = false;
|
|
}
|
|
|
|
Optional<size_t> TraversableSessionHistory::current_top_level_entry_index() const
|
|
{
|
|
if (!m_current_used_step_index.has_value())
|
|
return {};
|
|
return top_level_entry_index_for_step(m_entries, m_used_steps[*m_current_used_step_index]);
|
|
}
|
|
|
|
TraversableSessionHistory::UpdateResult TraversableSessionHistory::update_from_web_content(Vector<Entry> entries, Vector<i32> used_steps, size_t current_used_step_index)
|
|
{
|
|
auto invalid_snapshot = [&] {
|
|
forget_web_content_state();
|
|
return UpdateResult::InvalidSnapshot;
|
|
};
|
|
|
|
if (entries.is_empty() || used_steps.is_empty() || current_used_step_index >= used_steps.size() || !entries_are_valid(entries) || !steps_are_valid(used_steps) || !entries_and_used_steps_are_consistent(entries, used_steps))
|
|
return invalid_snapshot();
|
|
|
|
auto incoming_current_top_level_entry_index = top_level_entry_index_for_step(entries, used_steps[current_used_step_index]);
|
|
if (!incoming_current_top_level_entry_index.has_value())
|
|
return invalid_snapshot();
|
|
|
|
if (m_entries.is_empty()) {
|
|
canonicalize_document_state_ids(entries);
|
|
m_entries.clear_with_capacity();
|
|
m_entries.ensure_capacity(entries.size());
|
|
for (auto& entry : entries)
|
|
m_entries.unchecked_append(move(entry));
|
|
m_used_steps = move(used_steps);
|
|
m_current_used_step_index = current_used_step_index;
|
|
m_web_content_known_entries = m_entries;
|
|
m_web_content_known_used_steps = m_used_steps;
|
|
m_web_content_current_step = m_used_steps[*m_current_used_step_index];
|
|
m_web_content_uses_ui_step_coordinates = true;
|
|
return UpdateResult::CompleteSnapshot;
|
|
}
|
|
|
|
VERIFY(m_current_used_step_index.has_value());
|
|
VERIFY(!m_used_steps.is_empty());
|
|
|
|
if (m_entries.size() == entries.size() && m_used_steps.size() == used_steps.size()) {
|
|
if (entries_match(m_entries, entries) && steps_match(m_used_steps, used_steps)) {
|
|
m_current_used_step_index = current_used_step_index;
|
|
m_web_content_known_entries = m_entries;
|
|
m_web_content_known_used_steps = m_used_steps;
|
|
m_web_content_current_step = m_used_steps[*m_current_used_step_index];
|
|
m_web_content_uses_ui_step_coordinates = true;
|
|
return UpdateResult::CompleteSnapshot;
|
|
}
|
|
}
|
|
|
|
auto local_current_top_level_entry_index = current_top_level_entry_index();
|
|
if (!local_current_top_level_entry_index.has_value())
|
|
return invalid_snapshot();
|
|
|
|
if (m_entries.size() == entries.size() + 1
|
|
&& m_used_steps.size() == used_steps.size() + 1
|
|
&& *local_current_top_level_entry_index == m_entries.size() - 1
|
|
&& *m_current_used_step_index == m_used_steps.size() - 1
|
|
&& *local_current_top_level_entry_index > 0
|
|
&& *incoming_current_top_level_entry_index > 0
|
|
&& m_entries[*local_current_top_level_entry_index - 1].step == used_steps[current_used_step_index]
|
|
&& m_entries[*local_current_top_level_entry_index].url == entries[*incoming_current_top_level_entry_index].url) {
|
|
canonicalize_document_state_ids(entries);
|
|
m_entries = move(entries);
|
|
m_used_steps = move(used_steps);
|
|
m_current_used_step_index = current_used_step_index;
|
|
m_web_content_known_entries = m_entries;
|
|
m_web_content_known_used_steps = m_used_steps;
|
|
m_web_content_current_step = m_used_steps[*m_current_used_step_index];
|
|
m_web_content_uses_ui_step_coordinates = true;
|
|
return UpdateResult::CompleteSnapshot;
|
|
}
|
|
|
|
auto find_merge_anchor = [&](auto entry_can_anchor) -> Optional<SessionHistoryMergeAnchor> {
|
|
for (size_t local_index = *local_current_top_level_entry_index + 1; local_index > 0; --local_index) {
|
|
auto candidate_local_index = local_index - 1;
|
|
|
|
for (size_t incoming_index = *incoming_current_top_level_entry_index + 1; incoming_index > 0; --incoming_index) {
|
|
auto candidate_incoming_index = incoming_index - 1;
|
|
if (!entry_can_anchor(m_entries[candidate_local_index], entries[candidate_incoming_index]))
|
|
continue;
|
|
|
|
return SessionHistoryMergeAnchor {
|
|
.local_index = candidate_local_index,
|
|
.incoming_index = candidate_incoming_index,
|
|
};
|
|
}
|
|
}
|
|
return {};
|
|
};
|
|
|
|
auto merge_anchor = Optional<SessionHistoryMergeAnchor> {};
|
|
if (m_web_content_uses_ui_step_coordinates && m_web_content_current_step.has_value()) {
|
|
merge_anchor = find_merge_anchor([&](Entry const& local_entry, Entry const& incoming_entry) {
|
|
if (local_entry.step != incoming_entry.step)
|
|
return false;
|
|
if (local_entry.url == incoming_entry.url)
|
|
return false;
|
|
if (local_entry.step != *m_web_content_current_step)
|
|
return false;
|
|
if (!m_web_content_known_used_steps.contains_slow(local_entry.step))
|
|
return false;
|
|
auto const* web_content_known_entry = WebView::top_level_entry_for_step(m_web_content_known_entries, local_entry.step);
|
|
return web_content_known_entry && web_content_known_entry->step == local_entry.step;
|
|
});
|
|
}
|
|
|
|
// AD-HOC: The URL-keyed anchor searches are the common case. But find_merge_anchor compares every local entry
|
|
// against every incoming entry — and each URL comparison serializes both URLs. A burst of same-document
|
|
// navigations (such as a pushState flood) can push the top-level entry count into the hundreds while this
|
|
// runs once per history update — so, a quadratic scan with per-comparison serialization becomes a
|
|
// UI-process bottleneck. Index the incoming entries by serialized URL once — keyed the same way URL
|
|
// equality compares (full serialization, fragment included) — so each URL-keyed search is linear.
|
|
if (!merge_anchor.has_value()) {
|
|
HashMap<String, Vector<size_t>> incoming_indices_by_url;
|
|
for (size_t incoming_index = *incoming_current_top_level_entry_index + 1; incoming_index > 0; --incoming_index) {
|
|
auto candidate_incoming_index = incoming_index - 1;
|
|
incoming_indices_by_url.ensure(entries[candidate_incoming_index].url.serialize()).append(candidate_incoming_index);
|
|
}
|
|
|
|
// The incoming index lists are built highest-first. So, this reproduces find_merge_anchor's choice among the
|
|
// local/incoming entry pairs whose URLs are equal and who satisfy the predicate: The highest local entry — and
|
|
// for it, the highest matching incoming entry.
|
|
auto find_url_merge_anchor = [&](auto predicate) -> Optional<SessionHistoryMergeAnchor> {
|
|
for (size_t local_index = *local_current_top_level_entry_index + 1; local_index > 0; --local_index) {
|
|
auto candidate_local_index = local_index - 1;
|
|
auto incoming_candidates = incoming_indices_by_url.find(m_entries[candidate_local_index].url.serialize());
|
|
if (incoming_candidates == incoming_indices_by_url.end())
|
|
continue;
|
|
for (auto candidate_incoming_index : incoming_candidates->value) {
|
|
if (!predicate(m_entries[candidate_local_index], entries[candidate_incoming_index]))
|
|
continue;
|
|
return SessionHistoryMergeAnchor {
|
|
.local_index = candidate_local_index,
|
|
.incoming_index = candidate_incoming_index,
|
|
};
|
|
}
|
|
}
|
|
return {};
|
|
};
|
|
|
|
merge_anchor = find_url_merge_anchor([](Entry const& local_entry, Entry const& incoming_entry) {
|
|
return entries_have_matching_nonzero_document_state_id(local_entry, incoming_entry);
|
|
});
|
|
if (!merge_anchor.has_value()) {
|
|
merge_anchor = find_url_merge_anchor([](Entry const&, Entry const&) {
|
|
return true;
|
|
});
|
|
}
|
|
}
|
|
|
|
if (!merge_anchor.has_value())
|
|
return invalid_snapshot();
|
|
|
|
// AD-HOC: The HTML algorithms operate on one traversable session history. Ladybird's UI process can instead
|
|
// receive a valid partial WebContent snapshot after a process swap or fallback load, so merge the suffix
|
|
// WebContent knows about into the durable UI mirror while preserving any still-valid forward history.
|
|
auto local_index = merge_anchor->local_index;
|
|
auto incoming_index = merge_anchor->incoming_index;
|
|
size_t common_suffix_size = 0;
|
|
while (local_index + common_suffix_size < m_entries.size() && incoming_index + common_suffix_size < entries.size()) {
|
|
if (m_entries[local_index + common_suffix_size].url != entries[incoming_index + common_suffix_size].url)
|
|
break;
|
|
++common_suffix_size;
|
|
}
|
|
if (common_suffix_size == 0 && m_web_content_uses_ui_step_coordinates && m_entries[merge_anchor->local_index].step == entries[merge_anchor->incoming_index].step)
|
|
common_suffix_size = 1;
|
|
|
|
auto local_anchor_step = m_entries[merge_anchor->local_index].step;
|
|
auto incoming_anchor_step = entries[merge_anchor->incoming_index].step;
|
|
Optional<i32> nested_history_step_floor;
|
|
if (auto incoming_anchor_document_state_id = entries[merge_anchor->incoming_index].document_state.id; incoming_anchor_document_state_id != 0) {
|
|
for (size_t i = 0; i < merge_anchor->incoming_index; ++i) {
|
|
if (entries[i].document_state.id != incoming_anchor_document_state_id)
|
|
continue;
|
|
nested_history_step_floor = entries[i].step;
|
|
break;
|
|
}
|
|
}
|
|
DocumentStateIdTranslationState document_state_id_translation_state;
|
|
update_next_document_state_id(m_entries, document_state_id_translation_state.next_document_state_id);
|
|
if (entries[merge_anchor->incoming_index].document_state.id != 0 && m_entries[merge_anchor->local_index].document_state.id != 0)
|
|
document_state_id_translation_state.translated_document_state_ids.set(entries[merge_anchor->incoming_index].document_state.id, m_entries[merge_anchor->local_index].document_state.id);
|
|
|
|
auto incoming_has_used_steps_after_anchor = false;
|
|
for (auto const& used_step : used_steps) {
|
|
if (used_step > incoming_anchor_step) {
|
|
incoming_has_used_steps_after_anchor = true;
|
|
break;
|
|
}
|
|
}
|
|
|
|
Vector<Entry> merged_entries;
|
|
auto web_content_uses_ui_step_coordinates = true;
|
|
auto incoming_suffix_size = entries.size() - incoming_index;
|
|
auto preserves_existing_forward_history = common_suffix_size == incoming_suffix_size && !incoming_has_used_steps_after_anchor;
|
|
auto merged_size = preserves_existing_forward_history ? m_entries.size() : merge_anchor->local_index + incoming_suffix_size;
|
|
merged_entries.ensure_capacity(merged_size);
|
|
|
|
for (size_t i = 0; i < merge_anchor->local_index; ++i)
|
|
merged_entries.unchecked_append(m_entries[i]);
|
|
|
|
for (size_t i = merge_anchor->incoming_index; i < entries.size(); ++i) {
|
|
auto translated_entry = translate_incoming_entry(entries[i], incoming_anchor_step, local_anchor_step, document_state_id_translation_state, StepTranslationMode::TopLevel, nested_history_step_floor);
|
|
if (!translated_entry.has_value())
|
|
return invalid_snapshot();
|
|
if (!entry_steps_match(entries[i], *translated_entry))
|
|
web_content_uses_ui_step_coordinates = false;
|
|
merged_entries.unchecked_append(translated_entry.release_value());
|
|
}
|
|
|
|
if (preserves_existing_forward_history) {
|
|
for (size_t i = merge_anchor->local_index + incoming_suffix_size; i < m_entries.size(); ++i)
|
|
merged_entries.unchecked_append(m_entries[i]);
|
|
}
|
|
|
|
Vector<i32> merged_used_steps;
|
|
if (preserves_existing_forward_history) {
|
|
merged_used_steps.ensure_capacity(m_used_steps.size());
|
|
for (auto const& used_step : m_used_steps)
|
|
merged_used_steps.unchecked_append(used_step);
|
|
} else {
|
|
merged_used_steps.ensure_capacity(m_used_steps.size() + used_steps.size());
|
|
for (auto const& used_step : m_used_steps) {
|
|
if (used_step > local_anchor_step)
|
|
break;
|
|
merged_used_steps.append(used_step);
|
|
}
|
|
|
|
for (auto const& incoming_used_step : used_steps) {
|
|
if (incoming_used_step <= incoming_anchor_step)
|
|
continue;
|
|
|
|
auto translated_step = translate_incoming_step(incoming_used_step, incoming_anchor_step, local_anchor_step);
|
|
if (!translated_step.has_value())
|
|
return invalid_snapshot();
|
|
if (*translated_step != incoming_used_step)
|
|
web_content_uses_ui_step_coordinates = false;
|
|
if (!merged_used_steps.is_empty() && *translated_step <= merged_used_steps.last())
|
|
return invalid_snapshot();
|
|
merged_used_steps.append(*translated_step);
|
|
}
|
|
}
|
|
|
|
Vector<i32> translated_web_content_used_steps;
|
|
translated_web_content_used_steps.ensure_capacity(used_steps.size());
|
|
for (auto const& incoming_used_step : used_steps) {
|
|
auto translation_mode = StepTranslationMode::TopLevel;
|
|
if (incoming_used_step < incoming_anchor_step) {
|
|
if (!nested_history_step_floor.has_value() || incoming_used_step < *nested_history_step_floor)
|
|
continue;
|
|
translation_mode = StepTranslationMode::Nested;
|
|
}
|
|
auto translated_step = translate_incoming_step(incoming_used_step, incoming_anchor_step, local_anchor_step, translation_mode, nested_history_step_floor);
|
|
if (!translated_step.has_value())
|
|
return invalid_snapshot();
|
|
if (*translated_step != incoming_used_step)
|
|
web_content_uses_ui_step_coordinates = false;
|
|
if (!translated_web_content_used_steps.is_empty() && *translated_step <= translated_web_content_used_steps.last())
|
|
return invalid_snapshot();
|
|
translated_web_content_used_steps.append(*translated_step);
|
|
}
|
|
|
|
auto current_step_translation_mode = StepTranslationMode::TopLevel;
|
|
if (used_steps[current_used_step_index] < incoming_anchor_step && nested_history_step_floor.has_value() && used_steps[current_used_step_index] >= *nested_history_step_floor)
|
|
current_step_translation_mode = StepTranslationMode::Nested;
|
|
auto translated_current_step = translate_incoming_step(used_steps[current_used_step_index], incoming_anchor_step, local_anchor_step, current_step_translation_mode, nested_history_step_floor);
|
|
if (!translated_current_step.has_value())
|
|
return invalid_snapshot();
|
|
if (*translated_current_step != used_steps[current_used_step_index])
|
|
web_content_uses_ui_step_coordinates = false;
|
|
if (!translated_web_content_used_steps.contains_slow(*translated_current_step))
|
|
return invalid_snapshot();
|
|
auto current_used_step_index_after_merge = merged_used_steps.find_first_index(*translated_current_step);
|
|
if (!current_used_step_index_after_merge.has_value())
|
|
return invalid_snapshot();
|
|
if (!entries_and_used_steps_are_consistent(merged_entries, merged_used_steps))
|
|
return invalid_snapshot();
|
|
canonicalize_document_state_ids(merged_entries);
|
|
|
|
Vector<Entry> translated_web_content_entries;
|
|
auto web_content_known_entries_start_index = merge_anchor->local_index;
|
|
if (nested_history_step_floor.has_value()) {
|
|
auto same_document_entry_index = top_level_entry_index_for_step(merged_entries, *nested_history_step_floor);
|
|
if (same_document_entry_index.has_value())
|
|
web_content_known_entries_start_index = *same_document_entry_index;
|
|
}
|
|
translated_web_content_entries.ensure_capacity(merge_anchor->local_index + incoming_suffix_size - web_content_known_entries_start_index);
|
|
for (size_t i = web_content_known_entries_start_index; i < merge_anchor->local_index + incoming_suffix_size; ++i)
|
|
translated_web_content_entries.unchecked_append(merged_entries[i]);
|
|
|
|
auto entries_in_ui_document_state_id_order = entries;
|
|
canonicalize_document_state_ids(entries_in_ui_document_state_id_order);
|
|
auto web_content_matches_mirror = entries_match(merged_entries, entries_in_ui_document_state_id_order) && steps_match(merged_used_steps, used_steps);
|
|
|
|
m_entries = move(merged_entries);
|
|
m_used_steps = move(merged_used_steps);
|
|
m_current_used_step_index = *current_used_step_index_after_merge;
|
|
VERIFY(*m_current_used_step_index < m_used_steps.size());
|
|
VERIFY(current_top_level_entry_index().has_value());
|
|
|
|
if (web_content_matches_mirror) {
|
|
m_web_content_known_entries = m_entries;
|
|
m_web_content_known_used_steps = m_used_steps;
|
|
m_web_content_uses_ui_step_coordinates = true;
|
|
} else {
|
|
m_web_content_known_entries = move(translated_web_content_entries);
|
|
m_web_content_known_used_steps = move(translated_web_content_used_steps);
|
|
m_web_content_uses_ui_step_coordinates = web_content_uses_ui_step_coordinates;
|
|
}
|
|
m_web_content_current_step = *translated_current_step;
|
|
|
|
return web_content_matches_mirror ? UpdateResult::CompleteSnapshot : UpdateResult::MergedPartialSnapshot;
|
|
}
|
|
|
|
void TraversableSessionHistory::did_seed_web_content_from_ui_process(size_t current_top_level_entry_index)
|
|
{
|
|
VERIFY(current_top_level_entry_index < m_entries.size());
|
|
m_web_content_known_entries = m_entries;
|
|
m_web_content_known_used_steps = m_used_steps;
|
|
m_web_content_current_step = m_entries[current_top_level_entry_index].step;
|
|
m_web_content_uses_ui_step_coordinates = true;
|
|
}
|
|
|
|
bool TraversableSessionHistory::did_seed_web_content_from_ui_process(Vector<Entry> entries, Vector<i32> used_steps, size_t current_used_step_index)
|
|
{
|
|
if (m_entries.is_empty() || entries.is_empty() || used_steps.is_empty() || current_used_step_index >= used_steps.size() || !entries_are_valid(entries) || !steps_are_valid(used_steps) || !entries_and_used_steps_are_consistent(entries, used_steps))
|
|
return false;
|
|
|
|
auto current_top_level_entry_index = this->current_top_level_entry_index();
|
|
if (!current_top_level_entry_index.has_value())
|
|
return false;
|
|
|
|
if (used_steps[current_used_step_index] != m_entries[*current_top_level_entry_index].step)
|
|
return false;
|
|
|
|
auto entries_from_web_content = entries;
|
|
auto expected_entries = m_entries;
|
|
canonicalize_document_state_ids(expected_entries);
|
|
canonicalize_document_state_ids(entries);
|
|
|
|
if (!steps_match(m_used_steps, used_steps))
|
|
return false;
|
|
|
|
if (!entries_match(expected_entries, entries)) {
|
|
Optional<size_t> current_unknown_entry_index;
|
|
if (m_entries[*current_top_level_entry_index].document_state.id == 0)
|
|
current_unknown_entry_index = *current_top_level_entry_index;
|
|
if (!seed_ack_entries_match(m_entries, entries_from_web_content, current_unknown_entry_index))
|
|
return false;
|
|
m_entries = move(entries_from_web_content);
|
|
}
|
|
|
|
m_web_content_known_entries = m_entries;
|
|
m_web_content_known_used_steps = m_used_steps;
|
|
m_web_content_current_step = used_steps[current_used_step_index];
|
|
m_web_content_uses_ui_step_coordinates = true;
|
|
return true;
|
|
}
|
|
|
|
bool TraversableSessionHistory::did_restore_web_content_to_current_step(i32 step)
|
|
{
|
|
if (!m_current_used_step_index.has_value())
|
|
return false;
|
|
if (m_used_steps[*m_current_used_step_index] != step)
|
|
return false;
|
|
if (!m_web_content_uses_ui_step_coordinates)
|
|
return false;
|
|
if (!m_web_content_known_used_steps.contains_slow(step))
|
|
return false;
|
|
|
|
auto const* web_content_current_top_level_entry = WebView::top_level_entry_for_step(m_web_content_known_entries, step);
|
|
auto const* ui_current_top_level_entry = current_entry();
|
|
if (!web_content_current_top_level_entry || !ui_current_top_level_entry)
|
|
return false;
|
|
if (!Web::HTML::session_history_entry_descriptors_match(*web_content_current_top_level_entry, *ui_current_top_level_entry))
|
|
return false;
|
|
|
|
m_web_content_current_step = step;
|
|
return true;
|
|
}
|
|
|
|
bool TraversableSessionHistory::did_apply_web_content_traversal_to_step(i32 step)
|
|
{
|
|
auto target = traversal_target_for_step(step);
|
|
if (!target.has_value())
|
|
return false;
|
|
|
|
if (!web_content_can_traverse_to(*target))
|
|
return false;
|
|
|
|
// https://html.spec.whatwg.org/multipage/browsing-the-web.html#apply-the-history-step
|
|
// Set traversable's current session history step to targetStep.
|
|
m_current_used_step_index = target->target_step_index;
|
|
m_web_content_current_step = step;
|
|
return true;
|
|
}
|
|
|
|
bool TraversableSessionHistory::web_content_history_matches_mirror() const
|
|
{
|
|
if (!m_web_content_current_step.has_value() || !m_current_used_step_index.has_value())
|
|
return false;
|
|
if (!m_web_content_uses_ui_step_coordinates)
|
|
return false;
|
|
if (*m_web_content_current_step != m_used_steps[*m_current_used_step_index])
|
|
return false;
|
|
return entries_match(m_entries, m_web_content_known_entries) && steps_match(m_used_steps, m_web_content_known_used_steps);
|
|
}
|
|
|
|
void TraversableSessionHistory::forget_web_content_state()
|
|
{
|
|
m_web_content_known_entries.clear();
|
|
m_web_content_known_used_steps.clear();
|
|
m_web_content_current_step.clear();
|
|
m_web_content_uses_ui_step_coordinates = false;
|
|
}
|
|
|
|
Vector<TraversableSessionHistory::Entry> TraversableSessionHistory::entries() const
|
|
{
|
|
Vector<Entry> entries;
|
|
entries.ensure_capacity(m_entries.size());
|
|
for (auto const& entry : m_entries)
|
|
entries.unchecked_append(entry);
|
|
return entries;
|
|
}
|
|
|
|
Vector<i32> TraversableSessionHistory::used_steps() const
|
|
{
|
|
return m_used_steps;
|
|
}
|
|
|
|
Vector<TraversableSessionHistory::Entry> TraversableSessionHistory::web_content_known_entries() const
|
|
{
|
|
return m_web_content_known_entries;
|
|
}
|
|
|
|
Vector<i32> TraversableSessionHistory::web_content_known_used_steps() const
|
|
{
|
|
return m_web_content_known_used_steps;
|
|
}
|
|
|
|
Optional<i32> TraversableSessionHistory::web_content_current_step() const
|
|
{
|
|
return m_web_content_current_step;
|
|
}
|
|
|
|
bool TraversableSessionHistory::can_go_back() const
|
|
{
|
|
return m_current_used_step_index.has_value() && *m_current_used_step_index > 0;
|
|
}
|
|
|
|
bool TraversableSessionHistory::can_go_forward() const
|
|
{
|
|
return m_current_used_step_index.has_value() && *m_current_used_step_index + 1 < m_used_steps.size();
|
|
}
|
|
|
|
bool TraversableSessionHistory::has_only_top_level_used_steps() const
|
|
{
|
|
if (entries_have_nested_histories(m_entries))
|
|
return false;
|
|
|
|
if (m_entries.size() != m_used_steps.size())
|
|
return false;
|
|
|
|
for (size_t i = 0; i < m_entries.size(); ++i) {
|
|
if (m_entries[i].step != m_used_steps[i])
|
|
return false;
|
|
}
|
|
return true;
|
|
}
|
|
|
|
bool TraversableSessionHistory::current_step_is_top_level_entry() const
|
|
{
|
|
if (!m_current_used_step_index.has_value())
|
|
return false;
|
|
return entry_for_step(m_used_steps[*m_current_used_step_index]) != nullptr;
|
|
}
|
|
|
|
Optional<i32> TraversableSessionHistory::current_step_to_restore_after_loading_top_level_entry() const
|
|
{
|
|
if (!m_current_used_step_index.has_value())
|
|
return {};
|
|
|
|
auto current_step = m_used_steps[*m_current_used_step_index];
|
|
auto const* current_entry = entry_for_step(current_step);
|
|
if (current_entry) {
|
|
if (nested_histories_need_restore_after_loading_entry(*current_entry, current_step))
|
|
return current_step;
|
|
return {};
|
|
}
|
|
|
|
return current_step;
|
|
}
|
|
|
|
bool TraversableSessionHistory::web_content_can_traverse_to(TraversalTarget const& target) const
|
|
{
|
|
if (!m_current_used_step_index.has_value() || !m_web_content_current_step.has_value())
|
|
return false;
|
|
if (!m_web_content_uses_ui_step_coordinates)
|
|
return false;
|
|
if (*m_web_content_current_step != m_used_steps[*m_current_used_step_index])
|
|
return false;
|
|
if (!m_web_content_known_used_steps.contains_slow(target.target_step))
|
|
return false;
|
|
|
|
auto const* web_content_target_top_level_entry = WebView::top_level_entry_for_step(m_web_content_known_entries, target.target_step);
|
|
if (!web_content_target_top_level_entry || !target.target_top_level_entry)
|
|
return false;
|
|
return Web::HTML::session_history_entry_descriptors_match(*web_content_target_top_level_entry, *target.target_top_level_entry);
|
|
}
|
|
|
|
Optional<TraversableSessionHistory::TraversalTarget> TraversableSessionHistory::traversal_target_for_delta(int delta) const
|
|
{
|
|
auto target_step_index = target_step_index_for_delta(delta);
|
|
if (!target_step_index.has_value())
|
|
return {};
|
|
|
|
auto target_step = step_at(*target_step_index);
|
|
VERIFY(target_step.has_value());
|
|
return traversal_target_for_step(*target_step);
|
|
}
|
|
|
|
Optional<TraversableSessionHistory::TraversalTarget> TraversableSessionHistory::traversal_target_for_step(i32 step) const
|
|
{
|
|
auto target_step_index = m_used_steps.find_first_index(step);
|
|
if (!target_step_index.has_value())
|
|
return {};
|
|
|
|
auto const* target_top_level_entry = top_level_entry_for_step(step);
|
|
VERIFY(target_top_level_entry);
|
|
auto const* current_top_level_entry = current_entry();
|
|
VERIFY(current_top_level_entry);
|
|
|
|
return TraversalTarget {
|
|
.target_step_index = *target_step_index,
|
|
.target_step = step,
|
|
.target_top_level_entry = target_top_level_entry,
|
|
.target_step_is_top_level_entry = entry_for_step(step) != nullptr,
|
|
.changes_top_level_entry = target_top_level_entry != current_top_level_entry,
|
|
};
|
|
}
|
|
|
|
Optional<size_t> TraversableSessionHistory::target_step_index_for_delta(int delta) const
|
|
{
|
|
// https://html.spec.whatwg.org/multipage/browsing-the-web.html#traverse-the-history-by-a-delta
|
|
// Let allSteps be the result of getting all used history steps. Let
|
|
// targetStepIndex be currentStepIndex plus delta. If allSteps[targetStepIndex]
|
|
// does not exist, then abort these steps.
|
|
if (!m_current_used_step_index.has_value() || delta == 0)
|
|
return {};
|
|
|
|
if (delta < 0) {
|
|
auto magnitude = static_cast<size_t>(-static_cast<i64>(delta));
|
|
if (magnitude > *m_current_used_step_index)
|
|
return {};
|
|
return *m_current_used_step_index - magnitude;
|
|
}
|
|
|
|
auto target_index = *m_current_used_step_index + static_cast<size_t>(delta);
|
|
if (target_index >= m_used_steps.size())
|
|
return {};
|
|
return target_index;
|
|
}
|
|
|
|
Optional<i32> TraversableSessionHistory::step_at(size_t index) const
|
|
{
|
|
if (index >= m_used_steps.size())
|
|
return {};
|
|
return m_used_steps[index];
|
|
}
|
|
|
|
TraversableSessionHistory::Entry const* TraversableSessionHistory::current_entry() const
|
|
{
|
|
if (!m_current_used_step_index.has_value())
|
|
return nullptr;
|
|
return top_level_entry_for_step(m_used_steps[*m_current_used_step_index]);
|
|
}
|
|
|
|
TraversableSessionHistory::Entry const* TraversableSessionHistory::entry_at(size_t index) const
|
|
{
|
|
if (index >= m_entries.size())
|
|
return nullptr;
|
|
return &m_entries[index];
|
|
}
|
|
|
|
TraversableSessionHistory::Entry const* TraversableSessionHistory::entry_for_step(i32 step) const
|
|
{
|
|
for (auto const& entry : m_entries) {
|
|
if (entry.step == step)
|
|
return &entry;
|
|
}
|
|
return nullptr;
|
|
}
|
|
|
|
TraversableSessionHistory::Entry const* TraversableSessionHistory::top_level_entry_for_step(i32 step) const
|
|
{
|
|
auto index = top_level_entry_index_for_step(m_entries, step);
|
|
if (!index.has_value())
|
|
return nullptr;
|
|
return &m_entries[*index];
|
|
}
|
|
|
|
void TraversableSessionHistory::traverse_to(size_t index)
|
|
{
|
|
VERIFY(index < m_used_steps.size());
|
|
m_current_used_step_index = index;
|
|
forget_web_content_state();
|
|
}
|
|
|
|
}
|