chromium/src/third_party/blink/renderer/core/display_lock/display_lock_utilities.cc - manifest_repos/chromium_src - Git at Google

 // Copyright 2019 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.

 #include "third_party/blink/renderer/core/display_lock/display_lock_utilities.h"

 #include "third_party/blink/renderer/core/display_lock/display_lock_context.h"
 #include "third_party/blink/renderer/core/display_lock/display_lock_document_state.h"
 #include "third_party/blink/renderer/core/dom/element.h"
 #include "third_party/blink/renderer/core/dom/flat_tree_traversal.h"
 #include "third_party/blink/renderer/core/dom/node.h"
 #include "third_party/blink/renderer/core/dom/node_computed_style.h"
 #include "third_party/blink/renderer/core/dom/text.h"
 #include "third_party/blink/renderer/core/editing/editing_boundary.h"
 #include "third_party/blink/renderer/core/editing/editing_utilities.h"
 #include "third_party/blink/renderer/core/inspector/inspector_trace_events.h"
 #include "third_party/blink/renderer/core/layout/layout_embedded_content.h"
 #include "third_party/blink/renderer/core/layout/layout_view.h"

 #include <set>

 namespace blink {
 namespace {

 // Returns the frame owner node for the frame that contains the given child, if
 // one exists. Returns nullptr otherwise.
 Node* GetFrameOwnerNode(const Node* child) {
   if (!child || !child->GetDocument().GetFrame() ||
       !child->GetDocument().GetFrame()->OwnerLayoutObject()) {
     return nullptr;
   }
   return child->GetDocument().GetFrame()->OwnerLayoutObject()->GetNode();
 }

 void PopulateAncestorContexts(Node* node,
                               std::set<DisplayLockContext*>* contexts) {
   DCHECK(node);
   for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(*node)) {
     auto* ancestor_element = DynamicTo<Element>(ancestor);
     if (!ancestor_element)
       continue;
     if (auto* context = ancestor_element->GetDisplayLockContext())
       contexts->insert(context);
   }
 }

 template <typename Lambda>
 Element* LockedAncestorPreventingUpdate(const Node& node,
                                         Lambda update_is_prevented) {
   for (auto* ancestor =
            DisplayLockUtilities::NearestLockedExclusiveAncestor(node);
        ancestor;
        ancestor =
            DisplayLockUtilities::NearestLockedExclusiveAncestor(*ancestor)) {
     DCHECK(ancestor->GetDisplayLockContext());
     if (update_is_prevented(ancestor->GetDisplayLockContext()))
       return ancestor;
   }
   return nullptr;
 }

 template <typename Lambda>
 Element* LockedAncestorPreventingUpdate(const LayoutObject& object,
                                         Lambda update_is_prevented) {
   if (auto* ancestor =
           DisplayLockUtilities::NearestLockedExclusiveAncestor(object)) {
     if (update_is_prevented(ancestor->GetDisplayLockContext()))
       return ancestor;
     return LockedAncestorPreventingUpdate(*ancestor, update_is_prevented);
   }
   return nullptr;
 }

 }  // namespace

 bool DisplayLockUtilities::ActivateFindInPageMatchRangeIfNeeded(
     const EphemeralRangeInFlatTree& range) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
     return false;
   DCHECK(!range.IsNull());
   DCHECK(!range.IsCollapsed());
   if (range.GetDocument()
           .GetDisplayLockDocumentState()
           .LockedDisplayLockCount() ==
       range.GetDocument()
           .GetDisplayLockDocumentState()
           .DisplayLockBlockingAllActivationCount())
     return false;
   // Find-in-page matches can't span multiple block-level elements (because the
   // text will be broken by newlines between blocks), so first we find the
   // block-level element which contains the match.
   // This means we only need to traverse up from one node in the range, in this
   // case we are traversing from the start position of the range.
   Element* enclosing_block =
       EnclosingBlock(range.StartPosition(), kCannotCrossEditingBoundary);
   // Note that we don't check the `range.EndPosition()` since we just activate
   // the beginning of the range. In find-in-page cases, the end position is the
   // same since the matches cannot cross block boundaries. However, in
   // scroll-to-text, the range might be different, but we still just activate
   // the beginning of the range. See
   // https://github.com/WICG/display-locking/issues/125 for more details.
   DCHECK(enclosing_block);
   return enclosing_block->ActivateDisplayLockIfNeeded(
       DisplayLockActivationReason::kFindInPage);
 }

 bool DisplayLockUtilities::ActivateSelectionRangeIfNeeded(
     const EphemeralRangeInFlatTree& range) {
   if (range.IsNull() || range.IsCollapsed())
     return false;
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       range.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() ==
           range.GetDocument()
               .GetDisplayLockDocumentState()
               .DisplayLockBlockingAllActivationCount())
     return false;
   UpdateStyleAndLayoutForRangeIfNeeded(range,
                                        DisplayLockActivationReason::kSelection);
   HeapHashSet<Member<Element>> elements_to_activate;
   for (Node& node : range.Nodes()) {
     DCHECK(!node.GetDocument().NeedsLayoutTreeUpdateForNode(node));
     const ComputedStyle* style = node.GetComputedStyle();
     if (!style || style->UserSelect() == EUserSelect::kNone)
       continue;
     if (auto* nearest_locked_ancestor = NearestLockedExclusiveAncestor(node))
       elements_to_activate.insert(nearest_locked_ancestor);
   }
   for (Element* element : elements_to_activate) {
     element->ActivateDisplayLockIfNeeded(
         DisplayLockActivationReason::kSelection);
   }
   return !elements_to_activate.IsEmpty();
 }

 const HeapVector<Member<Element>>
 DisplayLockUtilities::ActivatableLockedInclusiveAncestors(
     const Node& node,
     DisplayLockActivationReason reason) {
   HeapVector<Member<Element>> elements_to_activate;
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       node.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() ==
           node.GetDocument()
               .GetDisplayLockDocumentState()
               .DisplayLockBlockingAllActivationCount())
     return elements_to_activate;

   for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(node)) {
     auto* ancestor_element = DynamicTo<Element>(ancestor);
     if (!ancestor_element)
       continue;
     if (auto* context = ancestor_element->GetDisplayLockContext()) {
       if (!context->IsLocked())
         continue;
       if (!context->IsActivatable(reason)) {
         // If we find a non-activatable locked ancestor, then we shouldn't
         // activate anything.
         elements_to_activate.clear();
         return elements_to_activate;
       }
       elements_to_activate.push_back(ancestor_element);
     }
   }
   return elements_to_activate;
 }

 DisplayLockUtilities::ScopedForcedUpdate::Impl::Impl(const Node* node,
                                                      bool include_self)
     : node_(node) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
     return;

   if (!node_)
     return;

   auto* owner_node = GetFrameOwnerNode(node);
   if (owner_node)
     parent_frame_impl_ = MakeGarbageCollected<Impl>(owner_node, true);

   node->GetDocument().GetDisplayLockDocumentState().BeginNodeForcedScope(
       node, include_self, this);

   if (node->GetDocument()
           .GetDisplayLockDocumentState()
           .LockedDisplayLockCount() == 0)
     return;

   // Get the right ancestor view. Only use inclusive ancestors if the node
   // itself is locked and it prevents self layout, or if |include_self| is true.
   // If self layout is not prevented, we don't need to force the subtree layout,
   // so use exclusive ancestors in that case.
   auto ancestor_view = [node, include_self] {
     if (auto* element = DynamicTo<Element>(node)) {
       auto* context = element->GetDisplayLockContext();
       if (context && include_self)
         return FlatTreeTraversal::InclusiveAncestorsOf(*node);
     }
     return FlatTreeTraversal::AncestorsOf(*node);
   }();

   // TODO(vmpstr): This is somewhat inefficient, since we would pay the cost
   // of traversing the ancestor chain even for nodes that are not in the
   // locked subtree. We need to figure out if there is a supplementary
   // structure that we can use to quickly identify nodes that are in the
   // locked subtree.
   for (Node& ancestor : ancestor_view) {
     auto* ancestor_node = DynamicTo<Element>(ancestor);
     if (!ancestor_node)
       continue;
     if (auto* context = ancestor_node->GetDisplayLockContext()) {
       context->NotifyForcedUpdateScopeStarted();
       forced_context_set_.insert(context);
     }
   }
 }

 void DisplayLockUtilities::ScopedForcedUpdate::Impl::Destroy() {
   if (!node_)
     return;
   if (RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
     node_->GetDocument().GetDisplayLockDocumentState().EndNodeForcedScope(this);
   if (parent_frame_impl_)
     parent_frame_impl_->Destroy();
   for (auto context : forced_context_set_) {
     context->NotifyForcedUpdateScopeEnded();
   }
 }

 void DisplayLockUtilities::ScopedForcedUpdate::Impl::
     AddForcedUpdateScopeForContext(DisplayLockContext* context) {
   auto result = forced_context_set_.insert(context);
   if (result.is_new_entry)
     context->NotifyForcedUpdateScopeStarted();
 }

 const Element* DisplayLockUtilities::NearestLockedInclusiveAncestor(
     const Node& node) {
   auto* element = DynamicTo<Element>(node);
   if (!element)
     return NearestLockedExclusiveAncestor(node);
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       !node.isConnected() ||
       node.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() == 0 ||
       !node.CanParticipateInFlatTree()) {
     return nullptr;
   }
   if (auto* context = element->GetDisplayLockContext()) {
     if (context->IsLocked())
       return element;
   }
   return NearestLockedExclusiveAncestor(node);
 }

 Element* DisplayLockUtilities::NearestLockedInclusiveAncestor(Node& node) {
   return const_cast<Element*>(
       NearestLockedInclusiveAncestor(static_cast<const Node&>(node)));
 }

 Element* DisplayLockUtilities::NearestHiddenMatchableInclusiveAncestor(
     Element& element) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       !element.isConnected() ||
       element.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() == 0 ||
       !element.CanParticipateInFlatTree()) {
     return nullptr;
   }

   if (auto* context = element.GetDisplayLockContext()) {
     if (context->GetState() == EContentVisibility::kHiddenMatchable) {
       return &element;
     }
   }

   // TODO(crbug.com/924550): Once we figure out a more efficient way to
   // determine whether we're inside a locked subtree or not, change this.
   for (Node& ancestor : FlatTreeTraversal::AncestorsOf(element)) {
     auto* ancestor_element = DynamicTo<Element>(ancestor);
     if (!ancestor_element)
       continue;
     if (auto* context = ancestor_element->GetDisplayLockContext()) {
       if (context->GetState() == EContentVisibility::kHiddenMatchable) {
         return ancestor_element;
       }
     }
   }
   return nullptr;
 }

 Element* DisplayLockUtilities::NearestLockedExclusiveAncestor(
     const Node& node) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       !node.isConnected() ||
       node.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() == 0 ||
       !node.CanParticipateInFlatTree()) {
     return nullptr;
   }
   // TODO(crbug.com/924550): Once we figure out a more efficient way to
   // determine whether we're inside a locked subtree or not, change this.
   for (Node& ancestor : FlatTreeTraversal::AncestorsOf(node)) {
     auto* ancestor_element = DynamicTo<Element>(ancestor);
     if (!ancestor_element)
       continue;
     if (auto* context = ancestor_element->GetDisplayLockContext()) {
       if (context->IsLocked())
         return ancestor_element;
     }
   }
   return nullptr;
 }

 Element* DisplayLockUtilities::HighestLockedInclusiveAncestor(
     const Node& node) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       !node.CanParticipateInFlatTree()) {
     return nullptr;
   }
   auto* node_ptr = const_cast<Node*>(&node);
   // If the exclusive result exists, then that's higher than this node, so
   // return it.
   if (auto* result = HighestLockedExclusiveAncestor(node))
     return result;

   // Otherwise, we know the node is not in a locked subtree, so the only
   // other possibility is that the node itself is locked.
   auto* element = DynamicTo<Element>(node_ptr);
   if (element && element->GetDisplayLockContext() &&
       element->GetDisplayLockContext()->IsLocked()) {
     return element;
   }
   return nullptr;
 }

 Element* DisplayLockUtilities::HighestLockedExclusiveAncestor(
     const Node& node) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       !node.CanParticipateInFlatTree()) {
     return nullptr;
   }

   Node* parent = FlatTreeTraversal::Parent(node);
   Element* locked_ancestor = nullptr;
   while (parent) {
     auto* locked_candidate = NearestLockedInclusiveAncestor(*parent);
     auto* last_node = parent;
     if (locked_candidate) {
       locked_ancestor = locked_candidate;
       parent = FlatTreeTraversal::Parent(*parent);
     } else {
       parent = nullptr;
     }

     if (!parent)
       parent = GetFrameOwnerNode(last_node);
   }
   return locked_ancestor;
 }

 Element* DisplayLockUtilities::NearestLockedInclusiveAncestor(
     const LayoutObject& object) {
   auto* node = object.GetNode();
   auto* ancestor = object.Parent();
   while (ancestor && !node) {
     node = ancestor->GetNode();
     ancestor = ancestor->Parent();
   }
   return node ? NearestLockedInclusiveAncestor(*node) : nullptr;
 }

 Element* DisplayLockUtilities::NearestLockedExclusiveAncestor(
     const LayoutObject& object) {
   if (auto* node = object.GetNode())
     return NearestLockedExclusiveAncestor(*node);
   // Since we now navigate to an ancestor, use the inclusive version.
   if (auto* parent = object.Parent())
     return NearestLockedInclusiveAncestor(*parent);
   return nullptr;
 }

 bool DisplayLockUtilities::IsInUnlockedOrActivatableSubtree(
     const Node& node,
     DisplayLockActivationReason activation_reason) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled(
           node.GetExecutionContext()) ||
       node.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() == 0 ||
       !node.CanParticipateInFlatTree()) {
     return true;
   }

   for (auto* element = NearestLockedExclusiveAncestor(node); element;
        element = NearestLockedExclusiveAncestor(*element)) {
     if (!element->GetDisplayLockContext()->IsActivatable(activation_reason)) {
       return false;
     }
   }
   return true;
 }

 bool DisplayLockUtilities::IsInLockedSubtreeCrossingFrames(
     const Node& source_node) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
     return false;
   if (LocalFrameView* frame_view = source_node.GetDocument().View()) {
     if (frame_view->IsDisplayLocked())
       return true;
   }
   const Node* node = &source_node;

   // Since we handled the self-check above, we need to do inclusive checks
   // starting from the parent.
   node = FlatTreeTraversal::Parent(*node);
   // If we don't have a flat-tree parent, get the |source_node|'s owner node
   // instead.
   if (!node)
     node = GetFrameOwnerNode(&source_node);

   while (node) {
     if (NearestLockedInclusiveAncestor(*node))
       return true;
     node = GetFrameOwnerNode(node);
   }
   return false;
 }

 void DisplayLockUtilities::ElementLostFocus(Element* element) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       (element && element->GetDocument()
                           .GetDisplayLockDocumentState()
                           .DisplayLockCount() == 0))
     return;
   for (; element; element = FlatTreeTraversal::ParentElement(*element)) {
     auto* context = element->GetDisplayLockContext();
     if (context)
       context->NotifySubtreeLostFocus();
   }
 }
 void DisplayLockUtilities::ElementGainedFocus(Element* element) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       (element && element->GetDocument()
                           .GetDisplayLockDocumentState()
                           .DisplayLockCount() == 0))
     return;

   for (; element; element = FlatTreeTraversal::ParentElement(*element)) {
     auto* context = element->GetDisplayLockContext();
     if (context)
       context->NotifySubtreeGainedFocus();
   }
 }

 void DisplayLockUtilities::SelectionChanged(
     const EphemeralRangeInFlatTree& old_selection,
     const EphemeralRangeInFlatTree& new_selection) {
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       (!old_selection.IsNull() && old_selection.GetDocument()
                                           .GetDisplayLockDocumentState()
                                           .DisplayLockCount() == 0) ||
       (!new_selection.IsNull() && new_selection.GetDocument()
                                           .GetDisplayLockDocumentState()
                                           .DisplayLockCount() == 0))
     return;

   TRACE_EVENT0("blink", "DisplayLockUtilities::SelectionChanged");
   std::set<Node*> old_nodes;
   for (Node& node : old_selection.Nodes())
     old_nodes.insert(&node);

   std::set<Node*> new_nodes;
   for (Node& node : new_selection.Nodes())
     new_nodes.insert(&node);

   std::set<DisplayLockContext*> lost_selection_contexts;
   std::set<DisplayLockContext*> gained_selection_contexts;

   // Skip common nodes and extract contexts from nodes that lost selection and
   // contexts from nodes that gained selection.
   // This is similar to std::set_symmetric_difference except that we need to
   // know which set the resulting item came from. In this version, we simply do
   // the relevant operation on each of the items instead of storing the
   // difference.
   std::set<Node*>::iterator old_it = old_nodes.begin();
   std::set<Node*>::iterator new_it = new_nodes.begin();
   while (old_it != old_nodes.end() && new_it != new_nodes.end()) {
     // Compare the addresses since that's how the nodes are ordered in the set.
     if (*old_it < *new_it) {
       PopulateAncestorContexts(*old_it++, &lost_selection_contexts);
     } else if (*old_it > *new_it) {
       PopulateAncestorContexts(*new_it++, &gained_selection_contexts);
     } else {
       ++old_it;
       ++new_it;
     }
   }
   while (old_it != old_nodes.end())
     PopulateAncestorContexts(*old_it++, &lost_selection_contexts);
   while (new_it != new_nodes.end())
     PopulateAncestorContexts(*new_it++, &gained_selection_contexts);

   // Now do a similar thing with contexts: skip common ones, and mark the ones
   // that lost selection or gained selection as such.
   std::set<DisplayLockContext*>::iterator lost_it =
       lost_selection_contexts.begin();
   std::set<DisplayLockContext*>::iterator gained_it =
       gained_selection_contexts.begin();
   while (lost_it != lost_selection_contexts.end() &&
          gained_it != gained_selection_contexts.end()) {
     if (*lost_it < *gained_it) {
       (*lost_it++)->NotifySubtreeLostSelection();
     } else if (*lost_it > *gained_it) {
       (*gained_it++)->NotifySubtreeGainedSelection();
     } else {
       ++lost_it;
       ++gained_it;
     }
   }
   while (lost_it != lost_selection_contexts.end())
     (*lost_it++)->NotifySubtreeLostSelection();
   while (gained_it != gained_selection_contexts.end())
     (*gained_it++)->NotifySubtreeGainedSelection();
 }

 void DisplayLockUtilities::SelectionRemovedFromDocument(Document& document) {
   document.GetDisplayLockDocumentState().NotifySelectionRemoved();
 }

 Element* DisplayLockUtilities::LockedAncestorPreventingPrePaint(
     const LayoutObject& object) {
   return LockedAncestorPreventingUpdate(
       object, [](DisplayLockContext* context) {
         return !context->ShouldPrePaintChildren();
       });
 }

 Element* DisplayLockUtilities::LockedAncestorPreventingLayout(
     const LayoutObject& object) {
   return LockedAncestorPreventingUpdate(
       object, [](DisplayLockContext* context) {
         return !context->ShouldLayoutChildren();
       });
 }

 Element* DisplayLockUtilities::LockedAncestorPreventingStyle(const Node& node) {
   return LockedAncestorPreventingUpdate(node, [](DisplayLockContext* context) {
     return !context->ShouldStyleChildren();
   });
 }

 bool DisplayLockUtilities::UpdateStyleAndLayoutForRangeIfNeeded(
     const EphemeralRangeInFlatTree& range,
     DisplayLockActivationReason reason) {
   if (range.IsNull() || range.IsCollapsed())
     return false;
   if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() ||
       range.GetDocument()
               .GetDisplayLockDocumentState()
               .LockedDisplayLockCount() ==
           range.GetDocument()
               .GetDisplayLockDocumentState()
               .DisplayLockBlockingAllActivationCount())
     return false;
   HeapVector<Member<DisplayLockContext>> forced_context_list_;
   for (Node& node : range.Nodes()) {
     for (Element* locked_activatable_ancestor :
          DisplayLockUtilities::ActivatableLockedInclusiveAncestors(node,
                                                                    reason)) {
       DCHECK(locked_activatable_ancestor->GetDisplayLockContext());
       DCHECK(locked_activatable_ancestor->GetDisplayLockContext()->IsLocked());
       auto* context = locked_activatable_ancestor->GetDisplayLockContext();
       // TODO(vmpstr): Clean this up not to call
       // |NotifyForcedUpdateScopeStarted()| directly.
       context->NotifyForcedUpdateScopeStarted();
       forced_context_list_.push_back(context);
     }
   }
   if (!forced_context_list_.IsEmpty()) {
     range.GetDocument().UpdateStyleAndLayout(
         DocumentUpdateReason::kDisplayLock);
   }
   for (auto context : forced_context_list_) {
     context->NotifyForcedUpdateScopeEnded();
   }
   return !forced_context_list_.IsEmpty();
 }

 bool DisplayLockUtilities::PrePaintBlockedInParentFrame(LayoutView* view) {
   auto* owner = view->GetFrameView()->GetFrame().OwnerLayoutObject();
   if (!owner)
     return false;

   auto* element = NearestLockedInclusiveAncestor(*owner);
   while (element) {
     if (!element->GetDisplayLockContext()->ShouldPrePaintChildren())
       return true;
     element = NearestLockedExclusiveAncestor(*element);
   }
   return false;
 }

 bool DisplayLockUtilities::IsAutoWithoutLayout(const LayoutObject& object) {
   auto* context = object.GetDisplayLockContext();
   if (!context)
     return false;
   return !context->IsLocked() && context->IsAuto() &&
          !context->HadLifecycleUpdateSinceLastUnlock();
 }

 }  // namespace blink
	// Copyright 2019 The Chromium Authors. All rights reserved.
	// Use of this source code is governed by a BSD-style license that can be
	// found in the LICENSE file.

	#include "third_party/blink/renderer/core/display_lock/display_lock_utilities.h"

	#include "third_party/blink/renderer/core/display_lock/display_lock_context.h"
	#include "third_party/blink/renderer/core/display_lock/display_lock_document_state.h"
	#include "third_party/blink/renderer/core/dom/element.h"
	#include "third_party/blink/renderer/core/dom/flat_tree_traversal.h"
	#include "third_party/blink/renderer/core/dom/node.h"
	#include "third_party/blink/renderer/core/dom/node_computed_style.h"
	#include "third_party/blink/renderer/core/dom/text.h"
	#include "third_party/blink/renderer/core/editing/editing_boundary.h"
	#include "third_party/blink/renderer/core/editing/editing_utilities.h"
	#include "third_party/blink/renderer/core/inspector/inspector_trace_events.h"
	#include "third_party/blink/renderer/core/layout/layout_embedded_content.h"
	#include "third_party/blink/renderer/core/layout/layout_view.h"

	#include <set>

	namespace blink {
	namespace {

	// Returns the frame owner node for the frame that contains the given child, if
	// one exists. Returns nullptr otherwise.
	Node* GetFrameOwnerNode(const Node* child) {
	if (!child \|\| !child->GetDocument().GetFrame() \|\|
	!child->GetDocument().GetFrame()->OwnerLayoutObject()) {
	return nullptr;
	}
	return child->GetDocument().GetFrame()->OwnerLayoutObject()->GetNode();
	}

	void PopulateAncestorContexts(Node* node,
	std::set<DisplayLockContext> contexts) {
	DCHECK(node);
	for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(*node)) {
	auto* ancestor_element = DynamicTo<Element>(ancestor);
	if (!ancestor_element)
	continue;
	if (auto* context = ancestor_element->GetDisplayLockContext())
	contexts->insert(context);
	}
	}

	template <typename Lambda>
	Element* LockedAncestorPreventingUpdate(const Node& node,
	Lambda update_is_prevented) {
	for (auto* ancestor =
	DisplayLockUtilities::NearestLockedExclusiveAncestor(node);
	ancestor;
	ancestor =
	DisplayLockUtilities::NearestLockedExclusiveAncestor(*ancestor)) {
	DCHECK(ancestor->GetDisplayLockContext());
	if (update_is_prevented(ancestor->GetDisplayLockContext()))
	return ancestor;
	}
	return nullptr;
	}

	template <typename Lambda>
	Element* LockedAncestorPreventingUpdate(const LayoutObject& object,
	Lambda update_is_prevented) {
	if (auto* ancestor =
	DisplayLockUtilities::NearestLockedExclusiveAncestor(object)) {
	if (update_is_prevented(ancestor->GetDisplayLockContext()))
	return ancestor;
	return LockedAncestorPreventingUpdate(*ancestor, update_is_prevented);
	}
	return nullptr;
	}

	} // namespace

	bool DisplayLockUtilities::ActivateFindInPageMatchRangeIfNeeded(
	const EphemeralRangeInFlatTree& range) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
	return false;
	DCHECK(!range.IsNull());
	DCHECK(!range.IsCollapsed());
	if (range.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() ==
	range.GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockBlockingAllActivationCount())
	return false;
	// Find-in-page matches can't span multiple block-level elements (because the
	// text will be broken by newlines between blocks), so first we find the
	// block-level element which contains the match.
	// This means we only need to traverse up from one node in the range, in this
	// case we are traversing from the start position of the range.
	Element* enclosing_block =
	EnclosingBlock(range.StartPosition(), kCannotCrossEditingBoundary);
	// Note that we don't check the `range.EndPosition()` since we just activate
	// the beginning of the range. In find-in-page cases, the end position is the
	// same since the matches cannot cross block boundaries. However, in
	// scroll-to-text, the range might be different, but we still just activate
	// the beginning of the range. See
	// https://github.com/WICG/display-locking/issues/125 for more details.
	DCHECK(enclosing_block);
	return enclosing_block->ActivateDisplayLockIfNeeded(
	DisplayLockActivationReason::kFindInPage);
	}

	bool DisplayLockUtilities::ActivateSelectionRangeIfNeeded(
	const EphemeralRangeInFlatTree& range) {
	if (range.IsNull() \|\| range.IsCollapsed())
	return false;
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	range.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() ==
	range.GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockBlockingAllActivationCount())
	return false;
	UpdateStyleAndLayoutForRangeIfNeeded(range,
	DisplayLockActivationReason::kSelection);
	HeapHashSet<Member<Element>> elements_to_activate;
	for (Node& node : range.Nodes()) {
	DCHECK(!node.GetDocument().NeedsLayoutTreeUpdateForNode(node));
	const ComputedStyle* style = node.GetComputedStyle();
	if (!style \|\| style->UserSelect() == EUserSelect::kNone)
	continue;
	if (auto* nearest_locked_ancestor = NearestLockedExclusiveAncestor(node))
	elements_to_activate.insert(nearest_locked_ancestor);
	}
	for (Element* element : elements_to_activate) {
	element->ActivateDisplayLockIfNeeded(
	DisplayLockActivationReason::kSelection);
	}
	return !elements_to_activate.IsEmpty();
	}

	const HeapVector<Member<Element>>
	DisplayLockUtilities::ActivatableLockedInclusiveAncestors(
	const Node& node,
	DisplayLockActivationReason reason) {
	HeapVector<Member<Element>> elements_to_activate;
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	node.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() ==
	node.GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockBlockingAllActivationCount())
	return elements_to_activate;

	for (Node& ancestor : FlatTreeTraversal::InclusiveAncestorsOf(node)) {
	auto* ancestor_element = DynamicTo<Element>(ancestor);
	if (!ancestor_element)
	continue;
	if (auto* context = ancestor_element->GetDisplayLockContext()) {
	if (!context->IsLocked())
	continue;
	if (!context->IsActivatable(reason)) {
	// If we find a non-activatable locked ancestor, then we shouldn't
	// activate anything.
	elements_to_activate.clear();
	return elements_to_activate;
	}
	elements_to_activate.push_back(ancestor_element);
	}
	}
	return elements_to_activate;
	}

	DisplayLockUtilities::ScopedForcedUpdate::Impl::Impl(const Node* node,
	bool include_self)
	: node_(node) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
	return;

	if (!node_)
	return;

	auto* owner_node = GetFrameOwnerNode(node);
	if (owner_node)
	parent_frame_impl_ = MakeGarbageCollected<Impl>(owner_node, true);

	node->GetDocument().GetDisplayLockDocumentState().BeginNodeForcedScope(
	node, include_self, this);

	if (node->GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() == 0)
	return;

	// Get the right ancestor view. Only use inclusive ancestors if the node
	// itself is locked and it prevents self layout, or if \|include_self\| is true.
	// If self layout is not prevented, we don't need to force the subtree layout,
	// so use exclusive ancestors in that case.
	auto ancestor_view = [node, include_self] {
	if (auto* element = DynamicTo<Element>(node)) {
	auto* context = element->GetDisplayLockContext();
	if (context && include_self)
	return FlatTreeTraversal::InclusiveAncestorsOf(*node);
	}
	return FlatTreeTraversal::AncestorsOf(*node);
	}();

	// TODO(vmpstr): This is somewhat inefficient, since we would pay the cost
	// of traversing the ancestor chain even for nodes that are not in the
	// locked subtree. We need to figure out if there is a supplementary
	// structure that we can use to quickly identify nodes that are in the
	// locked subtree.
	for (Node& ancestor : ancestor_view) {
	auto* ancestor_node = DynamicTo<Element>(ancestor);
	if (!ancestor_node)
	continue;
	if (auto* context = ancestor_node->GetDisplayLockContext()) {
	context->NotifyForcedUpdateScopeStarted();
	forced_context_set_.insert(context);
	}
	}
	}

	void DisplayLockUtilities::ScopedForcedUpdate::Impl::Destroy() {
	if (!node_)
	return;
	if (RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
	node_->GetDocument().GetDisplayLockDocumentState().EndNodeForcedScope(this);
	if (parent_frame_impl_)
	parent_frame_impl_->Destroy();
	for (auto context : forced_context_set_) {
	context->NotifyForcedUpdateScopeEnded();
	}
	}

	void DisplayLockUtilities::ScopedForcedUpdate::Impl::
	AddForcedUpdateScopeForContext(DisplayLockContext* context) {
	auto result = forced_context_set_.insert(context);
	if (result.is_new_entry)
	context->NotifyForcedUpdateScopeStarted();
	}

	const Element* DisplayLockUtilities::NearestLockedInclusiveAncestor(
	const Node& node) {
	auto* element = DynamicTo<Element>(node);
	if (!element)
	return NearestLockedExclusiveAncestor(node);
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	!node.isConnected() \|\|
	node.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() == 0 \|\|
	!node.CanParticipateInFlatTree()) {
	return nullptr;
	}
	if (auto* context = element->GetDisplayLockContext()) {
	if (context->IsLocked())
	return element;
	}
	return NearestLockedExclusiveAncestor(node);
	}

	Element* DisplayLockUtilities::NearestLockedInclusiveAncestor(Node& node) {
	return const_cast<Element*>(
	NearestLockedInclusiveAncestor(static_cast<const Node&>(node)));
	}

	Element* DisplayLockUtilities::NearestHiddenMatchableInclusiveAncestor(
	Element& element) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	!element.isConnected() \|\|
	element.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() == 0 \|\|
	!element.CanParticipateInFlatTree()) {
	return nullptr;
	}

	if (auto* context = element.GetDisplayLockContext()) {
	if (context->GetState() == EContentVisibility::kHiddenMatchable) {
	return &element;
	}
	}

	// TODO(crbug.com/924550): Once we figure out a more efficient way to
	// determine whether we're inside a locked subtree or not, change this.
	for (Node& ancestor : FlatTreeTraversal::AncestorsOf(element)) {
	auto* ancestor_element = DynamicTo<Element>(ancestor);
	if (!ancestor_element)
	continue;
	if (auto* context = ancestor_element->GetDisplayLockContext()) {
	if (context->GetState() == EContentVisibility::kHiddenMatchable) {
	return ancestor_element;
	}
	}
	}
	return nullptr;
	}

	Element* DisplayLockUtilities::NearestLockedExclusiveAncestor(
	const Node& node) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	!node.isConnected() \|\|
	node.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() == 0 \|\|
	!node.CanParticipateInFlatTree()) {
	return nullptr;
	}
	// TODO(crbug.com/924550): Once we figure out a more efficient way to
	// determine whether we're inside a locked subtree or not, change this.
	for (Node& ancestor : FlatTreeTraversal::AncestorsOf(node)) {
	auto* ancestor_element = DynamicTo<Element>(ancestor);
	if (!ancestor_element)
	continue;
	if (auto* context = ancestor_element->GetDisplayLockContext()) {
	if (context->IsLocked())
	return ancestor_element;
	}
	}
	return nullptr;
	}

	Element* DisplayLockUtilities::HighestLockedInclusiveAncestor(
	const Node& node) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	!node.CanParticipateInFlatTree()) {
	return nullptr;
	}
	auto* node_ptr = const_cast<Node*>(&node);
	// If the exclusive result exists, then that's higher than this node, so
	// return it.
	if (auto* result = HighestLockedExclusiveAncestor(node))
	return result;

	// Otherwise, we know the node is not in a locked subtree, so the only
	// other possibility is that the node itself is locked.
	auto* element = DynamicTo<Element>(node_ptr);
	if (element && element->GetDisplayLockContext() &&
	element->GetDisplayLockContext()->IsLocked()) {
	return element;
	}
	return nullptr;
	}

	Element* DisplayLockUtilities::HighestLockedExclusiveAncestor(
	const Node& node) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	!node.CanParticipateInFlatTree()) {
	return nullptr;
	}

	Node* parent = FlatTreeTraversal::Parent(node);
	Element* locked_ancestor = nullptr;
	while (parent) {
	auto* locked_candidate = NearestLockedInclusiveAncestor(*parent);
	auto* last_node = parent;
	if (locked_candidate) {
	locked_ancestor = locked_candidate;
	parent = FlatTreeTraversal::Parent(*parent);
	} else {
	parent = nullptr;
	}

	if (!parent)
	parent = GetFrameOwnerNode(last_node);
	}
	return locked_ancestor;
	}

	Element* DisplayLockUtilities::NearestLockedInclusiveAncestor(
	const LayoutObject& object) {
	auto* node = object.GetNode();
	auto* ancestor = object.Parent();
	while (ancestor && !node) {
	node = ancestor->GetNode();
	ancestor = ancestor->Parent();
	}
	return node ? NearestLockedInclusiveAncestor(*node) : nullptr;
	}

	Element* DisplayLockUtilities::NearestLockedExclusiveAncestor(
	const LayoutObject& object) {
	if (auto* node = object.GetNode())
	return NearestLockedExclusiveAncestor(*node);
	// Since we now navigate to an ancestor, use the inclusive version.
	if (auto* parent = object.Parent())
	return NearestLockedInclusiveAncestor(*parent);
	return nullptr;
	}

	bool DisplayLockUtilities::IsInUnlockedOrActivatableSubtree(
	const Node& node,
	DisplayLockActivationReason activation_reason) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled(
	node.GetExecutionContext()) \|\|
	node.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() == 0 \|\|
	!node.CanParticipateInFlatTree()) {
	return true;
	}

	for (auto* element = NearestLockedExclusiveAncestor(node); element;
	element = NearestLockedExclusiveAncestor(*element)) {
	if (!element->GetDisplayLockContext()->IsActivatable(activation_reason)) {
	return false;
	}
	}
	return true;
	}

	bool DisplayLockUtilities::IsInLockedSubtreeCrossingFrames(
	const Node& source_node) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled())
	return false;
	if (LocalFrameView* frame_view = source_node.GetDocument().View()) {
	if (frame_view->IsDisplayLocked())
	return true;
	}
	const Node* node = &source_node;

	// Since we handled the self-check above, we need to do inclusive checks
	// starting from the parent.
	node = FlatTreeTraversal::Parent(*node);
	// If we don't have a flat-tree parent, get the \|source_node\|'s owner node
	// instead.
	if (!node)
	node = GetFrameOwnerNode(&source_node);

	while (node) {
	if (NearestLockedInclusiveAncestor(*node))
	return true;
	node = GetFrameOwnerNode(node);
	}
	return false;
	}

	void DisplayLockUtilities::ElementLostFocus(Element* element) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	(element && element->GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockCount() == 0))
	return;
	for (; element; element = FlatTreeTraversal::ParentElement(*element)) {
	auto* context = element->GetDisplayLockContext();
	if (context)
	context->NotifySubtreeLostFocus();
	}
	}
	void DisplayLockUtilities::ElementGainedFocus(Element* element) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	(element && element->GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockCount() == 0))
	return;

	for (; element; element = FlatTreeTraversal::ParentElement(*element)) {
	auto* context = element->GetDisplayLockContext();
	if (context)
	context->NotifySubtreeGainedFocus();
	}
	}

	void DisplayLockUtilities::SelectionChanged(
	const EphemeralRangeInFlatTree& old_selection,
	const EphemeralRangeInFlatTree& new_selection) {
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	(!old_selection.IsNull() && old_selection.GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockCount() == 0) \|\|
	(!new_selection.IsNull() && new_selection.GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockCount() == 0))
	return;

	TRACE_EVENT0("blink", "DisplayLockUtilities::SelectionChanged");
	std::set<Node*> old_nodes;
	for (Node& node : old_selection.Nodes())
	old_nodes.insert(&node);

	std::set<Node*> new_nodes;
	for (Node& node : new_selection.Nodes())
	new_nodes.insert(&node);

	std::set<DisplayLockContext*> lost_selection_contexts;
	std::set<DisplayLockContext*> gained_selection_contexts;

	// Skip common nodes and extract contexts from nodes that lost selection and
	// contexts from nodes that gained selection.
	// This is similar to std::set_symmetric_difference except that we need to
	// know which set the resulting item came from. In this version, we simply do
	// the relevant operation on each of the items instead of storing the
	// difference.
	std::set<Node*>::iterator old_it = old_nodes.begin();
	std::set<Node*>::iterator new_it = new_nodes.begin();
	while (old_it != old_nodes.end() && new_it != new_nodes.end()) {
	// Compare the addresses since that's how the nodes are ordered in the set.
	if (old_it < new_it) {
	PopulateAncestorContexts(*old_it++, &lost_selection_contexts);
	} else if (old_it > new_it) {
	PopulateAncestorContexts(*new_it++, &gained_selection_contexts);
	} else {
	++old_it;
	++new_it;
	}
	}
	while (old_it != old_nodes.end())
	PopulateAncestorContexts(*old_it++, &lost_selection_contexts);
	while (new_it != new_nodes.end())
	PopulateAncestorContexts(*new_it++, &gained_selection_contexts);

	// Now do a similar thing with contexts: skip common ones, and mark the ones
	// that lost selection or gained selection as such.
	std::set<DisplayLockContext*>::iterator lost_it =
	lost_selection_contexts.begin();
	std::set<DisplayLockContext*>::iterator gained_it =
	gained_selection_contexts.begin();
	while (lost_it != lost_selection_contexts.end() &&
	gained_it != gained_selection_contexts.end()) {
	if (lost_it < gained_it) {
	(*lost_it++)->NotifySubtreeLostSelection();
	} else if (lost_it > gained_it) {
	(*gained_it++)->NotifySubtreeGainedSelection();
	} else {
	++lost_it;
	++gained_it;
	}
	}
	while (lost_it != lost_selection_contexts.end())
	(*lost_it++)->NotifySubtreeLostSelection();
	while (gained_it != gained_selection_contexts.end())
	(*gained_it++)->NotifySubtreeGainedSelection();
	}

	void DisplayLockUtilities::SelectionRemovedFromDocument(Document& document) {
	document.GetDisplayLockDocumentState().NotifySelectionRemoved();
	}

	Element* DisplayLockUtilities::LockedAncestorPreventingPrePaint(
	const LayoutObject& object) {
	return LockedAncestorPreventingUpdate(
	object, [](DisplayLockContext* context) {
	return !context->ShouldPrePaintChildren();
	});
	}

	Element* DisplayLockUtilities::LockedAncestorPreventingLayout(
	const LayoutObject& object) {
	return LockedAncestorPreventingUpdate(
	object, [](DisplayLockContext* context) {
	return !context->ShouldLayoutChildren();
	});
	}

	Element* DisplayLockUtilities::LockedAncestorPreventingStyle(const Node& node) {
	return LockedAncestorPreventingUpdate(node, [](DisplayLockContext* context) {
	return !context->ShouldStyleChildren();
	});
	}

	bool DisplayLockUtilities::UpdateStyleAndLayoutForRangeIfNeeded(
	const EphemeralRangeInFlatTree& range,
	DisplayLockActivationReason reason) {
	if (range.IsNull() \|\| range.IsCollapsed())
	return false;
	if (!RuntimeEnabledFeatures::CSSContentVisibilityEnabled() \|\|
	range.GetDocument()
	.GetDisplayLockDocumentState()
	.LockedDisplayLockCount() ==
	range.GetDocument()
	.GetDisplayLockDocumentState()
	.DisplayLockBlockingAllActivationCount())
	return false;
	HeapVector<Member<DisplayLockContext>> forced_context_list_;
	for (Node& node : range.Nodes()) {
	for (Element* locked_activatable_ancestor :
	DisplayLockUtilities::ActivatableLockedInclusiveAncestors(node,
	reason)) {
	DCHECK(locked_activatable_ancestor->GetDisplayLockContext());
	DCHECK(locked_activatable_ancestor->GetDisplayLockContext()->IsLocked());
	auto* context = locked_activatable_ancestor->GetDisplayLockContext();
	// TODO(vmpstr): Clean this up not to call
	// \|NotifyForcedUpdateScopeStarted()\| directly.
	context->NotifyForcedUpdateScopeStarted();
	forced_context_list_.push_back(context);
	}
	}
	if (!forced_context_list_.IsEmpty()) {
	range.GetDocument().UpdateStyleAndLayout(
	DocumentUpdateReason::kDisplayLock);
	}
	for (auto context : forced_context_list_) {
	context->NotifyForcedUpdateScopeEnded();
	}
	return !forced_context_list_.IsEmpty();
	}

	bool DisplayLockUtilities::PrePaintBlockedInParentFrame(LayoutView* view) {
	auto* owner = view->GetFrameView()->GetFrame().OwnerLayoutObject();
	if (!owner)
	return false;

	auto* element = NearestLockedInclusiveAncestor(*owner);
	while (element) {
	if (!element->GetDisplayLockContext()->ShouldPrePaintChildren())
	return true;
	element = NearestLockedExclusiveAncestor(*element);
	}
	return false;
	}

	bool DisplayLockUtilities::IsAutoWithoutLayout(const LayoutObject& object) {
	auto* context = object.GetDisplayLockContext();
	if (!context)
	return false;
	return !context->IsLocked() && context->IsAuto() &&
	!context->HadLifecycleUpdateSinceLastUnlock();
	}

	} // namespace blink