| /* |
| * Copyright (C) 2015 Google Inc. All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or without |
| * modification, are permitted provided that the following conditions are |
| * met: |
| * |
| * * Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * * Redistributions in binary form must reproduce the above |
| * copyright notice, this list of conditions and the following disclaimer |
| * in the documentation and/or other materials provided with the |
| * distribution. |
| * * Neither the name of Google Inc. nor the names of its |
| * contributors may be used to endorse or promote products derived from |
| * this software without specific prior written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
| * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
| * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
| * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
| * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
| * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
| * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
| * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
| * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
| * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| #include "third_party/blink/renderer/core/html/html_slot_element.h" |
| |
| #include "third_party/blink/renderer/bindings/core/v8/v8_assigned_nodes_options.h" |
| #include "third_party/blink/renderer/core/css/style_change_reason.h" |
| #include "third_party/blink/renderer/core/css/style_engine.h" |
| #include "third_party/blink/renderer/core/dom/events/event.h" |
| #include "third_party/blink/renderer/core/dom/flat_tree_node_data.h" |
| #include "third_party/blink/renderer/core/dom/mutation_observer.h" |
| #include "third_party/blink/renderer/core/dom/node_computed_style.h" |
| #include "third_party/blink/renderer/core/dom/node_traversal.h" |
| #include "third_party/blink/renderer/core/dom/shadow_root.h" |
| #include "third_party/blink/renderer/core/dom/slot_assignment.h" |
| #include "third_party/blink/renderer/core/dom/text.h" |
| #include "third_party/blink/renderer/core/dom/whitespace_attacher.h" |
| #include "third_party/blink/renderer/core/frame/web_feature.h" |
| #include "third_party/blink/renderer/core/html_names.h" |
| #include "third_party/blink/renderer/core/probe/core_probes.h" |
| #include "third_party/blink/renderer/core/style/computed_style.h" |
| #include "third_party/blink/renderer/platform/bindings/microtask.h" |
| #include "third_party/blink/renderer/platform/instrumentation/use_counter.h" |
| |
| namespace blink { |
| |
| namespace { |
| constexpr size_t kLCSTableSizeLimit = 16; |
| } |
| |
| HTMLSlotElement* HTMLSlotElement::CreateUserAgentDefaultSlot( |
| Document& document) { |
| HTMLSlotElement* slot = MakeGarbageCollected<HTMLSlotElement>(document); |
| slot->setAttribute(html_names::kNameAttr, UserAgentDefaultSlotName()); |
| return slot; |
| } |
| |
| HTMLSlotElement* HTMLSlotElement::CreateUserAgentCustomAssignSlot( |
| Document& document) { |
| HTMLSlotElement* slot = MakeGarbageCollected<HTMLSlotElement>(document); |
| slot->setAttribute(html_names::kNameAttr, UserAgentCustomAssignSlotName()); |
| return slot; |
| } |
| |
| HTMLSlotElement::HTMLSlotElement(Document& document) |
| : HTMLElement(html_names::kSlotTag, document) { |
| UseCounter::Count(document, WebFeature::kHTMLSlotElement); |
| } |
| |
| // static |
| AtomicString HTMLSlotElement::NormalizeSlotName(const AtomicString& name) { |
| return (name.IsNull() || name.IsEmpty()) ? g_empty_atom : name; |
| } |
| |
| // static |
| const AtomicString& HTMLSlotElement::UserAgentDefaultSlotName() { |
| DEFINE_STATIC_LOCAL(const AtomicString, user_agent_default_slot_name, |
| ("user-agent-default-slot")); |
| return user_agent_default_slot_name; |
| } |
| |
| // static |
| const AtomicString& HTMLSlotElement::UserAgentCustomAssignSlotName() { |
| DEFINE_STATIC_LOCAL(const AtomicString, user_agent_custom_assign_slot_name, |
| ("user-agent-custom-assign-slot")); |
| return user_agent_custom_assign_slot_name; |
| } |
| |
| const HeapVector<Member<Node>>& HTMLSlotElement::AssignedNodes() const { |
| if (!SupportsAssignment()) { |
| DCHECK(assigned_nodes_.IsEmpty()); |
| return assigned_nodes_; |
| } |
| ContainingShadowRoot()->GetSlotAssignment().RecalcAssignment(); |
| return assigned_nodes_; |
| } |
| |
| namespace { |
| |
| HeapVector<Member<Node>> CollectFlattenedAssignedNodes( |
| const HTMLSlotElement& slot) { |
| DCHECK(slot.SupportsAssignment()); |
| |
| const HeapVector<Member<Node>>& assigned_nodes = slot.AssignedNodes(); |
| HeapVector<Member<Node>> nodes; |
| if (assigned_nodes.IsEmpty()) { |
| // Fallback contents. |
| for (auto& child : NodeTraversal::ChildrenOf(slot)) { |
| if (!child.IsSlotable()) |
| continue; |
| if (auto* child_slot = ToHTMLSlotElementIfSupportsAssignmentOrNull(child)) |
| nodes.AppendVector(CollectFlattenedAssignedNodes(*child_slot)); |
| else |
| nodes.push_back(child); |
| } |
| } else { |
| for (auto& node : assigned_nodes) { |
| DCHECK(node->IsSlotable()); |
| if (auto* assigned_node_slot = |
| ToHTMLSlotElementIfSupportsAssignmentOrNull(*node)) |
| nodes.AppendVector(CollectFlattenedAssignedNodes(*assigned_node_slot)); |
| else |
| nodes.push_back(node); |
| } |
| } |
| return nodes; |
| } |
| |
| } // namespace |
| |
| const HeapVector<Member<Node>> HTMLSlotElement::FlattenedAssignedNodes() { |
| if (!SupportsAssignment()) { |
| DCHECK(assigned_nodes_.IsEmpty()); |
| return assigned_nodes_; |
| } |
| return CollectFlattenedAssignedNodes(*this); |
| } |
| |
| const HeapVector<Member<Node>> HTMLSlotElement::AssignedNodesForBinding( |
| const AssignedNodesOptions* options) { |
| if (options->hasFlatten() && options->flatten()) |
| return FlattenedAssignedNodes(); |
| return AssignedNodes(); |
| } |
| |
| const HeapVector<Member<Element>> HTMLSlotElement::AssignedElements() { |
| HeapVector<Member<Element>> elements; |
| for (auto& node : AssignedNodes()) { |
| if (auto* element = DynamicTo<Element>(node.Get())) |
| elements.push_back(*element); |
| } |
| return elements; |
| } |
| |
| const HeapVector<Member<Element>> HTMLSlotElement::AssignedElementsForBinding( |
| const AssignedNodesOptions* options) { |
| HeapVector<Member<Element>> elements; |
| for (auto& node : AssignedNodesForBinding(options)) { |
| if (auto* element = DynamicTo<Element>(node.Get())) |
| elements.push_back(*element); |
| } |
| return elements; |
| } |
| |
| bool HTMLSlotElement::CheckNodesValidity(HeapVector<Member<Node>> nodes, |
| ExceptionState& exception_state) { |
| auto* host = OwnerShadowHost(); |
| for (auto& node : nodes) { |
| if (node->parentNode() != host) { |
| exception_state.ThrowDOMException( |
| DOMExceptionCode::kNotAllowedError, |
| "Node: '" + node->nodeName() + |
| "' is invalid for manual slot assignment."); |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| void HTMLSlotElement::assign(HeapVector<Member<Node>> nodes, |
| ExceptionState& exception_state) { |
| if (!SupportsAssignment() || !ContainingShadowRoot()->IsManualSlotting()) { |
| exception_state.ThrowDOMException( |
| DOMExceptionCode::kNotAllowedError, |
| "This shadow root does not support manual slot assignment."); |
| return; |
| } |
| |
| if (!CheckNodesValidity(nodes, exception_state)) |
| return; |
| |
| UseCounter::Count(GetDocument(), WebFeature::kSlotAssignNode); |
| ContainingShadowRoot()->GetSlotAssignment().ClearCandidateNodes( |
| assigned_nodes_candidates_); |
| HeapLinkedHashSet<Member<Node>> candidates; |
| bool updated = false; |
| for (auto& node : nodes) { |
| // Before assignment, see if this node belongs to another slot. |
| updated |= ContainingShadowRoot() |
| ->GetSlotAssignment() |
| .UpdateCandidateNodeAssignedSlot(*node, *this); |
| candidates.AppendOrMoveToLast(node); |
| } |
| |
| bool candidates_changed = |
| (updated || (candidates.size() != assigned_nodes_candidates_.size())); |
| if (!candidates_changed) { |
| for (auto it1 = candidates.begin(), |
| it2 = assigned_nodes_candidates_.begin(); |
| it1 != candidates.end(); ++it1, ++it2) { |
| if (!(*it1 == *it2)) { |
| candidates_changed = true; |
| break; |
| } |
| } |
| } |
| |
| if (candidates_changed) { |
| assigned_nodes_candidates_.Swap(candidates); |
| SetShadowRootNeedsAssignmentRecalc(); |
| DidSlotChange(SlotChangeType::kSignalSlotChangeEvent); |
| } |
| } |
| |
| void HTMLSlotElement::AppendAssignedNode(Node& host_child) { |
| DCHECK(host_child.IsSlotable()); |
| assigned_nodes_.push_back(&host_child); |
| } |
| |
| void HTMLSlotElement::UpdateManuallyAssignedNodesOrdering() { |
| if (assigned_nodes_.IsEmpty() || assigned_nodes_candidates_.IsEmpty()) |
| return; |
| |
| // TODO: (1067153) Add perf benchmark test for large assigned list. |
| HeapHashSet<Member<Node>> prev_nodes; |
| for (auto& node : assigned_nodes_) { |
| prev_nodes.insert(node); |
| } |
| assigned_nodes_.clear(); |
| for (auto& node : assigned_nodes_candidates_) { |
| if (prev_nodes.Contains(node)) |
| assigned_nodes_.push_back(node); |
| } |
| } |
| |
| void HTMLSlotElement::RemoveAssignedNodeCandidate(Node& node) { |
| auto it = assigned_nodes_candidates_.find(&node); |
| if (it != assigned_nodes_candidates_.end()) { |
| assigned_nodes_candidates_.erase(it); |
| DidSlotChange(SlotChangeType::kSignalSlotChangeEvent); |
| } |
| } |
| |
| void HTMLSlotElement::ClearAssignedNodesCandidates() { |
| assigned_nodes_candidates_.clear(); |
| } |
| |
| void HTMLSlotElement::ClearAssignedNodes() { |
| assigned_nodes_.clear(); |
| } |
| |
| void HTMLSlotElement::ClearAssignedNodesAndFlatTreeChildren() { |
| ClearAssignedNodes(); |
| flat_tree_children_.clear(); |
| } |
| |
| void HTMLSlotElement::UpdateFlatTreeNodeDataForAssignedNodes() { |
| Node* previous = nullptr; |
| for (auto& current : assigned_nodes_) { |
| bool flat_tree_parent_changed = false; |
| if (!current->NeedsStyleRecalc() && !current->GetComputedStyle()) { |
| if (auto* node_data = current->GetFlatTreeNodeData()) |
| flat_tree_parent_changed = !node_data->AssignedSlot(); |
| } |
| FlatTreeNodeData& flat_tree_node_data = current->EnsureFlatTreeNodeData(); |
| flat_tree_node_data.SetAssignedSlot(this); |
| flat_tree_node_data.SetPreviousInAssignedNodes(previous); |
| if (previous) { |
| DCHECK(previous->GetFlatTreeNodeData()); |
| previous->GetFlatTreeNodeData()->SetNextInAssignedNodes(current); |
| } |
| previous = current; |
| if (flat_tree_parent_changed) |
| current->FlatTreeParentChanged(); |
| } |
| if (previous) { |
| DCHECK(previous->GetFlatTreeNodeData()); |
| previous->GetFlatTreeNodeData()->SetNextInAssignedNodes(nullptr); |
| } |
| } |
| |
| void HTMLSlotElement::RecalcFlatTreeChildren() { |
| DCHECK(SupportsAssignment()); |
| |
| HeapVector<Member<Node>> old_flat_tree_children; |
| old_flat_tree_children.swap(flat_tree_children_); |
| |
| if (assigned_nodes_.IsEmpty()) { |
| // Use children as fallback |
| for (auto& child : NodeTraversal::ChildrenOf(*this)) { |
| if (child.IsSlotable()) |
| flat_tree_children_.push_back(child); |
| } |
| } else { |
| flat_tree_children_ = assigned_nodes_; |
| for (auto& node : old_flat_tree_children) { |
| // Detach fallback nodes. Host children which are no longer slotted are |
| // detached in SlotAssignment::RecalcAssignment(). |
| if (node->parentNode() == this) |
| node->RemovedFromFlatTree(); |
| } |
| } |
| |
| NotifySlottedNodesOfFlatTreeChange(old_flat_tree_children, |
| flat_tree_children_); |
| } |
| |
| void HTMLSlotElement::DispatchSlotChangeEvent() { |
| DCHECK(!IsInUserAgentShadowRoot()); |
| Event* event = Event::CreateBubble(event_type_names::kSlotchange); |
| event->SetTarget(this); |
| DispatchScopedEvent(*event); |
| } |
| |
| AtomicString HTMLSlotElement::GetName() const { |
| return NormalizeSlotName(FastGetAttribute(html_names::kNameAttr)); |
| } |
| |
| void HTMLSlotElement::AttachLayoutTree(AttachContext& context) { |
| HTMLElement::AttachLayoutTree(context); |
| |
| if (SupportsAssignment()) { |
| LayoutObject* layout_object = GetLayoutObject(); |
| AttachContext children_context(context); |
| const ComputedStyle* style = GetComputedStyle(); |
| AdjustForceLegacyLayout(style, &children_context.force_legacy_layout); |
| if (layout_object || !style || style->IsEnsuredInDisplayNone()) { |
| children_context.previous_in_flow = nullptr; |
| children_context.parent = layout_object; |
| children_context.next_sibling = nullptr; |
| children_context.next_sibling_valid = true; |
| } |
| |
| for (auto& node : AssignedNodes()) |
| node->AttachLayoutTree(children_context); |
| if (children_context.previous_in_flow) |
| context.previous_in_flow = children_context.previous_in_flow; |
| } |
| } |
| |
| void HTMLSlotElement::DetachLayoutTree(bool performing_reattach) { |
| if (SupportsAssignment()) { |
| auto* host = OwnerShadowHost(); |
| const HeapVector<Member<Node>>& flat_tree_children = assigned_nodes_; |
| for (auto& node : flat_tree_children) { |
| // Don't detach the assigned node if the node is no longer a child of the |
| // host. |
| // |
| // 1. It's no long a direct flat-tree child of this slot. |
| // 2. It was already detached when removed from the host. |
| // 3. It might already have been inserted in a different part of the DOM, |
| // or a new document tree and been attached. |
| // 4. It might have been marked style-dirty in its new location and |
| // calling DetachLayoutTree here would have incorrectly cleared those |
| // dirty bits. |
| if (host == node->parentNode()) |
| node->DetachLayoutTree(performing_reattach); |
| } |
| } |
| HTMLElement::DetachLayoutTree(performing_reattach); |
| } |
| |
| void HTMLSlotElement::RebuildDistributedChildrenLayoutTrees( |
| WhitespaceAttacher& whitespace_attacher) { |
| DCHECK(SupportsAssignment()); |
| |
| // This loop traverses the nodes from right to left for the same reason as the |
| // one described in ContainerNode::RebuildChildrenLayoutTrees(). |
| for (auto it = flat_tree_children_.rbegin(); it != flat_tree_children_.rend(); |
| ++it) { |
| RebuildLayoutTreeForChild(*it, whitespace_attacher); |
| } |
| } |
| |
| void HTMLSlotElement::AttributeChanged( |
| const AttributeModificationParams& params) { |
| if (params.name == html_names::kNameAttr) { |
| if (ShadowRoot* root = ContainingShadowRoot()) { |
| if (params.old_value != params.new_value) { |
| root->GetSlotAssignment().DidRenameSlot( |
| NormalizeSlotName(params.old_value), *this); |
| } |
| } |
| } |
| HTMLElement::AttributeChanged(params); |
| } |
| |
| Node::InsertionNotificationRequest HTMLSlotElement::InsertedInto( |
| ContainerNode& insertion_point) { |
| HTMLElement::InsertedInto(insertion_point); |
| if (SupportsAssignment()) { |
| ShadowRoot* root = ContainingShadowRoot(); |
| DCHECK(root); |
| if (root == insertion_point.ContainingShadowRoot()) { |
| // This slot is inserted into the same tree of |insertion_point| |
| root->DidAddSlot(*this); |
| } else if (insertion_point.isConnected() && |
| root->NeedsSlotAssignmentRecalc()) { |
| // Even when a slot and its containing shadow root is removed together |
| // and inserted together again, the slot's cached assigned nodes can be |
| // stale if the NeedsSlotAssignmentRecalc flag is set, and it may cause |
| // infinite recursion in DetachLayoutTree() when one of the stale node |
| // is a shadow-including ancestor of this slot by making a circular |
| // reference. Clear the cache here to avoid the situation. |
| // See http://crbug.com/849599 for details. |
| ClearAssignedNodesAndFlatTreeChildren(); |
| } |
| } |
| return kInsertionDone; |
| } |
| |
| void HTMLSlotElement::RemovedFrom(ContainerNode& insertion_point) { |
| // `removedFrom` is called after the node is removed from the tree. |
| // That means: |
| // 1. If this slot is still in a tree scope, it means the slot has been in a |
| // shadow tree. An inclusive shadow-including ancestor of the shadow host |
| // was originally removed from its parent. See slot s2 below. |
| // 2. Or (this slot is not in a tree scope), this slot's inclusive |
| // ancestor was orginally removed from its parent (== insertion point). |
| // This slot and the originally removed node was in the same tree before |
| // removal. See slot s1 below. |
| |
| // For example, given the following trees, (srN: = shadow root, sN: = slot) |
| // a |
| // |- b --sr1 |
| // |- c |--d |
| // |- e-----sr2 |
| // |- s1 |--f |
| // |--s2 |
| |
| // If we call 'e.remove()', then: |
| // - For slot s1, s1.removedFrom(d) is called. |
| // - For slot s2, s2.removedFrom(d) is called. |
| |
| // ContainingShadowRoot() is okay to use here because 1) It doesn't use |
| // kIsInShadowTreeFlag flag, and 2) TreeScope has been already updated for the |
| // slot. |
| if (ShadowRoot* shadow_root = ContainingShadowRoot()) { |
| // In this case, the shadow host (or its shadow-inclusive ancestor) was |
| // removed originally. In the above example, (this slot == s2) and |
| // (shadow_root == sr2). The shadow tree (sr2)'s structure didn't change at |
| // all. |
| if (shadow_root->NeedsSlotAssignmentRecalc()) { |
| // Clear |assigned_nodes_| here, so that the referenced node can get |
| // garbage collected if they no longer needed. See also InsertedInto()'s |
| // comment for cases that stale |assigned_nodes| can be problematic. |
| ClearAssignedNodesAndFlatTreeChildren(); |
| } else { |
| // We don't need to clear |assigned_nodes_| here. That's an important |
| // optimization. |
| } |
| } else if (insertion_point.IsInShadowTree()) { |
| // This slot was in a shadow tree and got disconnected from the shadow tree. |
| // In the above example, (this slot == s1), (insertion point == d) |
| // and (insertion_point->ContainingShadowRoot == sr1). |
| insertion_point.ContainingShadowRoot()->GetSlotAssignment().DidRemoveSlot( |
| *this); |
| ClearAssignedNodesAndFlatTreeChildren(); |
| } else { |
| DCHECK(assigned_nodes_.IsEmpty()); |
| } |
| |
| HTMLElement::RemovedFrom(insertion_point); |
| } |
| |
| void HTMLSlotElement::RecalcStyleForSlotChildren( |
| const StyleRecalcChange change, |
| const StyleRecalcContext& style_recalc_context) { |
| for (auto& node : flat_tree_children_) { |
| if (!change.TraverseChild(*node)) |
| continue; |
| if (auto* element = DynamicTo<Element>(node.Get())) |
| element->RecalcStyle(change, style_recalc_context); |
| else if (auto* text_node = DynamicTo<Text>(node.Get())) |
| text_node->RecalcTextStyle(change); |
| } |
| } |
| |
| void HTMLSlotElement::NotifySlottedNodesOfFlatTreeChangeByDynamicProgramming( |
| const HeapVector<Member<Node>>& old_slotted, |
| const HeapVector<Member<Node>>& new_slotted) { |
| // Use dynamic programming to minimize the number of nodes being reattached. |
| using LCSTable = |
| Vector<LCSArray<wtf_size_t, kLCSTableSizeLimit>, kLCSTableSizeLimit>; |
| using Backtrack = std::pair<wtf_size_t, wtf_size_t>; |
| using BacktrackTable = |
| Vector<LCSArray<Backtrack, kLCSTableSizeLimit>, kLCSTableSizeLimit>; |
| |
| DEFINE_STATIC_LOCAL(LCSTable*, lcs_table, (new LCSTable(kLCSTableSizeLimit))); |
| DEFINE_STATIC_LOCAL(BacktrackTable*, backtrack_table, |
| (new BacktrackTable(kLCSTableSizeLimit))); |
| |
| FillLongestCommonSubsequenceDynamicProgrammingTable( |
| old_slotted, new_slotted, *lcs_table, *backtrack_table); |
| |
| wtf_size_t r = old_slotted.size(); |
| wtf_size_t c = new_slotted.size(); |
| while (r > 0 && c > 0) { |
| Backtrack backtrack = (*backtrack_table)[r][c]; |
| if (backtrack == std::make_pair(r - 1, c - 1)) { |
| DCHECK_EQ(old_slotted[r - 1], new_slotted[c - 1]); |
| } else if (backtrack == std::make_pair(r, c - 1)) { |
| new_slotted[c - 1]->FlatTreeParentChanged(); |
| } |
| std::tie(r, c) = backtrack; |
| } |
| if (c > 0) { |
| for (wtf_size_t i = 0; i < c; ++i) |
| new_slotted[i]->FlatTreeParentChanged(); |
| } |
| } |
| |
| void HTMLSlotElement::NotifySlottedNodesOfFlatTreeChange( |
| const HeapVector<Member<Node>>& old_slotted, |
| const HeapVector<Member<Node>>& new_slotted) { |
| if (old_slotted == new_slotted) |
| return; |
| probe::DidPerformSlotDistribution(this); |
| |
| // It is very important to minimize the number of reattaching nodes in |
| // |new_assigned_nodes| here. The following *works*, in terms of the |
| // correctness of the rendering, |
| // |
| // for (auto& node: new_slotted) { |
| // node->FlatTreeParentChanged(); |
| // } |
| // |
| // However, reattaching all ndoes is not good in terms of performance. |
| // Reattach is very expensive operation. |
| // |
| // A possible approach is: Find the Longest Commons Subsequence (LCS) between |
| // |old_slotted| and |new_slotted|, and reattach nodes in |new_slotted| which |
| // LCS does not include. |
| // |
| // Note that a relative order between nodes which are not reattached should be |
| // preserved in old and new. For example, |
| // |
| // - old: [1, 4, 2, 3] |
| // - new: [3, 1, 2] |
| // |
| // This case, we must reattach 3 here, as the best possible solution. If we |
| // don't reattach 3, 3's LayoutObject will have an invalid next sibling |
| // pointer. We don't have any chance to update their sibling pointers (3's |
| // next and 1's previous). Sibling pointers between 1 and 2 are correctly |
| // updated when we reattach 4, which is done in another code path. |
| if (old_slotted.size() + 1 > kLCSTableSizeLimit || |
| new_slotted.size() + 1 > kLCSTableSizeLimit) { |
| // Since DP takes O(N^2), we don't use DP if the size is larger than the |
| // pre-defined limit. |
| NotifySlottedNodesOfFlatTreeChangeNaive(old_slotted, new_slotted); |
| } else { |
| NotifySlottedNodesOfFlatTreeChangeByDynamicProgramming(old_slotted, |
| new_slotted); |
| } |
| } |
| |
| void HTMLSlotElement::DidSlotChangeAfterRemovedFromShadowTree() { |
| DCHECK(!ContainingShadowRoot()); |
| EnqueueSlotChangeEvent(); |
| CheckSlotChange(SlotChangeType::kSuppressSlotChangeEvent); |
| } |
| |
| void HTMLSlotElement::DidSlotChangeAfterRenaming() { |
| DCHECK(SupportsAssignment()); |
| EnqueueSlotChangeEvent(); |
| SetShadowRootNeedsAssignmentRecalc(); |
| CheckSlotChange(SlotChangeType::kSuppressSlotChangeEvent); |
| } |
| |
| void HTMLSlotElement::NotifySlottedNodesOfFlatTreeChangeNaive( |
| const HeapVector<Member<Node>>& old_assigned_nodes, |
| const HeapVector<Member<Node>>& new_assigned_nodes) { |
| // Use O(N) naive greedy algorithm to find a *suboptimal* longest common |
| // subsequence (LCS), and reattach nodes which are not in suboptimal LCS. We |
| // run a greedy algorithm twice in both directions (scan forward and scan |
| // backward), and use the better result. Though this greedy algorithm is not |
| // perfect, it works well in some common cases, such as: |
| |
| // Inserting a node: |
| // old assigned nodes: [a, b ...., z] |
| // new assigned nodes: [a, b ...., z, A] |
| // => The algorithm reattaches only node |A|. |
| |
| // Removing a node: |
| // - old assigned nodes: [a, b, ..., m, n, o, ..., z] |
| // - new assigned nodes: [a, b, ..., m, o, ... , z] |
| // => The algorithm does not reattach any node. |
| |
| // Moving a node: |
| // - old assigned nodes: [a, b, ..., z] |
| // - new assigned nodes: [b, ..., z, a] |
| // => The algorithm reattaches only node |a|. |
| |
| // Swapping the first node and the last node |
| // - old assigned nodes: [a, b, ..., y, z] |
| // - new assigned nodes: [z, b, ..., y, a] |
| // => Ideally, we should reattach only |a| and |z|, however, the algorithm |
| // does not work well here, reattaching [a, b, ...., y] (or [b, ... y, z]). |
| // We could reconsider to support this case if a compelling case arises. |
| |
| // TODO(hayato): Consider to write an unit test for the algorithm. We |
| // probably want to make the algorithm templatized so we can test it |
| // easily. Like, Vec<T> greedy_suboptimal_lcs(Vec<T> old, Vec<T> new) |
| |
| HeapHashMap<Member<Node>, wtf_size_t> old_index_map; |
| for (wtf_size_t i = 0; i < old_assigned_nodes.size(); ++i) { |
| old_index_map.insert(old_assigned_nodes[i], i); |
| } |
| |
| // Scan forward |
| HeapVector<Member<Node>> forward_result; |
| |
| wtf_size_t i = 0; |
| wtf_size_t j = 0; |
| |
| while (i < old_assigned_nodes.size() && j < new_assigned_nodes.size()) { |
| auto& new_node = new_assigned_nodes[j]; |
| if (old_assigned_nodes[i] == new_node) { |
| ++i; |
| ++j; |
| continue; |
| } |
| if (old_index_map.Contains(new_node)) { |
| wtf_size_t old_index = old_index_map.at(new_node); |
| if (old_index > i) { |
| i = old_index_map.at(new_node) + 1; |
| ++j; |
| continue; |
| } |
| } |
| forward_result.push_back(new_node); |
| ++j; |
| } |
| |
| for (; j < new_assigned_nodes.size(); ++j) { |
| forward_result.push_back(new_assigned_nodes[j]); |
| } |
| |
| // Scan backward |
| HeapVector<Member<Node>> backward_result; |
| |
| i = old_assigned_nodes.size(); |
| j = new_assigned_nodes.size(); |
| |
| while (i > 0 && j > 0) { |
| auto& new_node = new_assigned_nodes[j - 1]; |
| if (old_assigned_nodes[i - 1] == new_node) { |
| --i; |
| --j; |
| continue; |
| } |
| if (old_index_map.Contains(new_node)) { |
| wtf_size_t old_index = old_index_map.at(new_node); |
| if (old_index < i - 1) { |
| i = old_index; |
| --j; |
| continue; |
| } |
| } |
| backward_result.push_back(new_node); |
| --j; |
| } |
| |
| for (; j > 0; --j) { |
| backward_result.push_back(new_assigned_nodes[j - 1]); |
| } |
| |
| // Reattach nodes |
| if (forward_result.size() <= backward_result.size()) { |
| for (auto& node : forward_result) { |
| node->FlatTreeParentChanged(); |
| } |
| } else { |
| for (auto& node : backward_result) { |
| node->FlatTreeParentChanged(); |
| } |
| } |
| } |
| |
| void HTMLSlotElement::SetShadowRootNeedsAssignmentRecalc() { |
| ContainingShadowRoot()->GetSlotAssignment().SetNeedsAssignmentRecalc(); |
| } |
| |
| void HTMLSlotElement::DidSlotChange(SlotChangeType slot_change_type) { |
| DCHECK(SupportsAssignment()); |
| if (slot_change_type == SlotChangeType::kSignalSlotChangeEvent) |
| EnqueueSlotChangeEvent(); |
| SetShadowRootNeedsAssignmentRecalc(); |
| // Check slotchange recursively since this slotchange may cause another |
| // slotchange. |
| CheckSlotChange(SlotChangeType::kSuppressSlotChangeEvent); |
| } |
| |
| void HTMLSlotElement::CheckFallbackAfterInsertedIntoShadowTree() { |
| DCHECK(SupportsAssignment()); |
| if (HasSlotableChild()) { |
| // We use kSuppress here because a slotchange event shouldn't be |
| // dispatched if a slot being inserted doesn't get any assigned |
| // node, but has a slotable child, according to DOM Standard. |
| DidSlotChange(SlotChangeType::kSuppressSlotChangeEvent); |
| } |
| } |
| |
| void HTMLSlotElement::CheckFallbackAfterRemovedFromShadowTree() { |
| if (HasSlotableChild()) { |
| // Since a slot was removed from a shadow tree, |
| // we don't need to set dirty flag for a disconnected tree. |
| // However, we need to call CheckSlotChange because we might need to set a |
| // dirty flag for a shadow tree which a parent of the slot may host. |
| CheckSlotChange(SlotChangeType::kSuppressSlotChangeEvent); |
| } |
| } |
| |
| bool HTMLSlotElement::HasSlotableChild() const { |
| for (auto& child : NodeTraversal::ChildrenOf(*this)) { |
| if (child.IsSlotable()) |
| return true; |
| } |
| return false; |
| } |
| |
| void HTMLSlotElement::EnqueueSlotChangeEvent() { |
| // TODO(kochi): This suppresses slotchange event on user-agent shadows, |
| // but could be improved further by not running change detection logic |
| // in SlotAssignment::Did{Add,Remove}SlotInternal etc., although naive |
| // skipping turned out breaking fallback content handling. |
| if (IsInUserAgentShadowRoot()) |
| return; |
| if (slotchange_event_enqueued_) |
| return; |
| MutationObserver::EnqueueSlotChange(*this); |
| slotchange_event_enqueued_ = true; |
| } |
| |
| bool HTMLSlotElement::HasAssignedNodesSlow() const { |
| ShadowRoot* root = ContainingShadowRoot(); |
| DCHECK(root) << "This should only be called on slots inside a shadow tree"; |
| SlotAssignment& assignment = root->GetSlotAssignment(); |
| if (assignment.FindSlotByName(GetName()) != this) |
| return false; |
| return assignment.FindHostChildBySlotName(GetName()); |
| } |
| |
| void HTMLSlotElement::ChildrenChanged(const ChildrenChange& change) { |
| HTMLElement::ChildrenChanged(change); |
| if (SupportsAssignment()) |
| SetShadowRootNeedsAssignmentRecalc(); |
| } |
| |
| void HTMLSlotElement::Trace(Visitor* visitor) const { |
| visitor->Trace(assigned_nodes_); |
| visitor->Trace(flat_tree_children_); |
| visitor->Trace(assigned_nodes_candidates_); |
| HTMLElement::Trace(visitor); |
| } |
| |
| } // namespace blink |