third_party/WebKit/Source/core/layout/LayoutView.cpp

/*
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
 * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009 Apple Inc.
 *               All rights reserved.
 *
 * This library is free software; you can redistribute it and/or
 * modify it under the terms of the GNU Library General Public
 * License as published by the Free Software Foundation; either
 * version 2 of the License, or (at your option) any later version.
 *
 * This library is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Library General Public License for more details.
 *
 * You should have received a copy of the GNU Library General Public License
 * along with this library; see the file COPYING.LIB.  If not, write to
 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#include "core/layout/LayoutView.h"

#include <inttypes.h>
#include "core/dom/Document.h"
#include "core/dom/Element.h"
#include "core/editing/FrameSelection.h"
#include "core/editing/LayoutSelection.h"
#include "core/frame/FrameView.h"
#include "core/frame/LocalFrame.h"
#include "core/frame/Settings.h"
#include "core/html/HTMLIFrameElement.h"
#include "core/layout/HitTestResult.h"
#include "core/layout/LayoutGeometryMap.h"
#include "core/layout/LayoutPart.h"
#include "core/layout/ViewFragmentationContext.h"
#include "core/layout/api/LayoutAPIShim.h"
#include "core/layout/api/LayoutPartItem.h"
#include "core/layout/api/LayoutViewItem.h"
#include "core/layout/compositing/PaintLayerCompositor.h"
#include "core/page/Page.h"
#include "core/paint/PaintLayer.h"
#include "core/paint/ViewPaintInvalidator.h"
#include "core/paint/ViewPainter.h"
#include "core/svg/SVGDocumentExtensions.h"
#include "platform/Histogram.h"
#include "platform/RuntimeEnabledFeatures.h"
#include "platform/geometry/FloatQuad.h"
#include "platform/geometry/TransformState.h"
#include "platform/graphics/paint/PaintController.h"
#include "platform/instrumentation/tracing/TraceEvent.h"
#include "platform/instrumentation/tracing/TracedValue.h"
#include "platform/wtf/PtrUtil.h"
#include "public/platform/Platform.h"

namespace blink {

namespace {

class HitTestLatencyRecorder {
 public:
  HitTestLatencyRecorder(bool allows_child_frame_content)
      : start_(WTF::MonotonicallyIncreasingTime()),
        allows_child_frame_content_(allows_child_frame_content) {}

  ~HitTestLatencyRecorder() {
    int duration = static_cast<int>(
        (WTF::MonotonicallyIncreasingTime() - start_) * 1000000);

    if (allows_child_frame_content_) {
      DEFINE_STATIC_LOCAL(CustomCountHistogram, recursive_latency_histogram,
                          ("Event.Latency.HitTestRecursive", 0, 10000000, 100));
      recursive_latency_histogram.Count(duration);
    } else {
      DEFINE_STATIC_LOCAL(CustomCountHistogram, latency_histogram,
                          ("Event.Latency.HitTest", 0, 10000000, 100));
      latency_histogram.Count(duration);
    }
  }

 private:
  double start_;
  bool allows_child_frame_content_;
};

}  // namespace

LayoutView::LayoutView(Document* document)
    : LayoutBlockFlow(document),
      frame_view_(document->View()),
      layout_state_(nullptr),
      layout_quote_head_(nullptr),
      layout_counter_count_(0),
      hit_test_count_(0),
      hit_test_cache_hits_(0),
      hit_test_cache_(HitTestCache::Create()) {
  // init LayoutObject attributes
  SetInline(false);

  min_preferred_logical_width_ = LayoutUnit();
  max_preferred_logical_width_ = LayoutUnit();

  SetPreferredLogicalWidthsDirty(kMarkOnlyThis);

  SetPositionState(EPosition::kAbsolute);  // to 0,0 :)
}

LayoutView::~LayoutView() {}

bool LayoutView::HitTest(HitTestResult& result) {
  // We have to recursively update layout/style here because otherwise, when the
  // hit test recurses into a child document, it could trigger a layout on the
  // parent document, which can destroy PaintLayer that are higher up in the
  // call stack, leading to crashes.
  // Note that Document::updateLayout calls its parent's updateLayout.
  // Note that if an iframe has its render pipeline throttled, it will not
  // update layout here, and it will also not propagate the hit test into the
  // iframe's inner document.
  GetFrameView()->UpdateLifecycleToCompositingCleanPlusScrolling();
  HitTestLatencyRecorder hit_test_latency_recorder(
      result.GetHitTestRequest().AllowsChildFrameContent());
  return HitTestNoLifecycleUpdate(result);
}

bool LayoutView::HitTestNoLifecycleUpdate(HitTestResult& result) {
  TRACE_EVENT_BEGIN0("blink,devtools.timeline", "HitTest");
  hit_test_count_++;

  DCHECK(!result.GetHitTestLocation().IsRectBasedTest() ||
         result.GetHitTestRequest().ListBased());

  CommitPendingSelection();

  uint64_t dom_tree_version = GetDocument().DomTreeVersion();
  HitTestResult cache_result = result;
  bool hit_layer = false;
  if (hit_test_cache_->LookupCachedResult(cache_result, dom_tree_version)) {
    hit_test_cache_hits_++;
    hit_layer = true;
    result = cache_result;
  } else {
    hit_layer = Layer()->HitTest(result);

    // FrameView scrollbars are not the same as Layer scrollbars tested by
    // Layer::hitTestOverflowControls, so we need to test FrameView scrollbars
    // separately here. Note that it's important we do this after the hit test
    // above, because that may overwrite the entire HitTestResult when it finds
    // a hit.
    IntPoint frame_point = GetFrameView()->ContentsToFrame(
        result.GetHitTestLocation().RoundedPoint());
    if (Scrollbar* frame_scrollbar =
            GetFrameView()->ScrollbarAtFramePoint(frame_point))
      result.SetScrollbar(frame_scrollbar);

    // If hitTestResult include scrollbar, innerNode should be the parent of the
    // scrollbar.
    if (result.GetScrollbar()) {
      // Clear innerNode if we hit a scrollbar whose ScrollableArea isn't
      // associated with a LayoutBox so we aren't hitting some random element
      // below too.
      result.SetInnerNode(nullptr);
      result.SetURLElement(nullptr);
      ScrollableArea* scrollable_area =
          result.GetScrollbar()->GetScrollableArea();
      if (scrollable_area && scrollable_area->GetLayoutBox() &&
          scrollable_area->GetLayoutBox()->GetNode()) {
        Node* node = scrollable_area->GetLayoutBox()->GetNode();
        result.SetInnerNode(node);
        result.SetURLElement(node->EnclosingLinkEventParentOrSelf());
      }
    }

    if (hit_layer)
      hit_test_cache_->AddCachedResult(result, dom_tree_version);
  }

  TRACE_EVENT_END1(
      "blink,devtools.timeline", "HitTest", "endData",
      InspectorHitTestEvent::EndData(result.GetHitTestRequest(),
                                     result.GetHitTestLocation(), result));
  return hit_layer;
}

void LayoutView::ClearHitTestCache() {
  hit_test_cache_->Clear();
  LayoutPartItem frame_layout_item = GetFrame()->OwnerLayoutItem();
  if (!frame_layout_item.IsNull())
    frame_layout_item.View().ClearHitTestCache();
}

void LayoutView::ComputeLogicalHeight(
    LayoutUnit logical_height,
    LayoutUnit,
    LogicalExtentComputedValues& computed_values) const {
  computed_values.extent_ = LayoutUnit(ViewLogicalHeightForBoxSizing());
}

void LayoutView::UpdateLogicalWidth() {
  SetLogicalWidth(LayoutUnit(ViewLogicalWidthForBoxSizing()));
}

bool LayoutView::IsChildAllowed(LayoutObject* child,
                                const ComputedStyle&) const {
  return child->IsBox();
}

bool LayoutView::CanHaveChildren() const {
  FrameOwner* owner = GetFrame()->Owner();
  if (!owner)
    return true;
  if (!RuntimeEnabledFeatures::displayNoneIFrameCreatesNoLayoutObjectEnabled())
    return true;
  return !owner->IsDisplayNone();
}

void LayoutView::LayoutContent() {
  DCHECK(NeedsLayout());

  LayoutBlockFlow::UpdateLayout();

#if DCHECK_IS_ON()
  CheckLayoutState();
#endif
}

#if DCHECK_IS_ON()
void LayoutView::CheckLayoutState() {
  DCHECK(!layout_state_->Next());
}
#endif

void LayoutView::SetShouldDoFullPaintInvalidationOnResizeIfNeeded(
    bool width_changed,
    bool height_changed) {
  // When background-attachment is 'fixed', we treat the viewport (instead of
  // the 'root' i.e. html or body) as the background positioning area, and we
  // should fully invalidate on viewport resize if the background image is not
  // composited and needs full paint invalidation on background positioning area
  // resize.
  if (Style()->HasFixedBackgroundImage() &&
      (!compositor_ || !compositor_->NeedsFixedRootBackgroundLayer(Layer()))) {
    if ((width_changed && MustInvalidateFillLayersPaintOnWidthChange(
                              Style()->BackgroundLayers())) ||
        (height_changed && MustInvalidateFillLayersPaintOnHeightChange(
                               Style()->BackgroundLayers())))
      SetShouldDoFullPaintInvalidation(kPaintInvalidationBoundsChange);
  }
}

void LayoutView::UpdateLayout() {
  if (!GetDocument().Paginated())
    SetPageLogicalHeight(LayoutUnit());

  // TODO(wangxianzhu): Move this into ViewPaintInvalidator when
  // rootLayerScrolling is permanently enabled.
  IncludeScrollbarsInRect include_scrollbars =
      RuntimeEnabledFeatures::rootLayerScrollingEnabled() ? kIncludeScrollbars
                                                          : kExcludeScrollbars;
  SetShouldDoFullPaintInvalidationOnResizeIfNeeded(
      OffsetWidth() != GetLayoutSize(include_scrollbars).Width(),
      OffsetHeight() != GetLayoutSize(include_scrollbars).Height());

  if (PageLogicalHeight() && ShouldUsePrintingLayout()) {
    min_preferred_logical_width_ = max_preferred_logical_width_ =
        LogicalWidth();
    if (!fragmentation_context_) {
      fragmentation_context_ =
          WTF::WrapUnique(new ViewFragmentationContext(*this));
      pagination_state_changed_ = true;
    }
  } else if (fragmentation_context_) {
    fragmentation_context_.reset();
    pagination_state_changed_ = true;
  }

  SubtreeLayoutScope layout_scope(*this);

  // Use calcWidth/Height to get the new width/height, since this will take the
  // full page zoom factor into account.
  bool relayout_children =
      !ShouldUsePrintingLayout() &&
      (!frame_view_ || LogicalWidth() != ViewLogicalWidthForBoxSizing() ||
       LogicalHeight() != ViewLogicalHeightForBoxSizing());
  if (relayout_children) {
    layout_scope.SetChildNeedsLayout(this);
    for (LayoutObject* child = FirstChild(); child;
         child = child->NextSibling()) {
      if (child->IsSVGRoot())
        continue;

      if ((child->IsBox() && ToLayoutBox(child)->HasRelativeLogicalHeight()) ||
          child->Style()->LogicalHeight().IsPercentOrCalc() ||
          child->Style()->LogicalMinHeight().IsPercentOrCalc() ||
          child->Style()->LogicalMaxHeight().IsPercentOrCalc())
        layout_scope.SetChildNeedsLayout(child);
    }

    if (GetDocument().SvgExtensions())
      GetDocument()
          .AccessSVGExtensions()
          .InvalidateSVGRootsWithRelativeLengthDescendents(&layout_scope);
  }

  DCHECK(!layout_state_);
  if (!NeedsLayout())
    return;

  LayoutState root_layout_state(*this);

  LayoutContent();

#if DCHECK_IS_ON()
  CheckLayoutState();
#endif
  ClearNeedsLayout();
}

LayoutRect LayoutView::VisualOverflowRect() const {
  // In root layer scrolling mode, the LayoutView performs overflow clipping
  // like a regular scrollable div.
  if (RuntimeEnabledFeatures::rootLayerScrollingEnabled())
    return LayoutBlockFlow::VisualOverflowRect();

  // Ditto when not in compositing mode.
  if (!UsesCompositing())
    return LayoutBlockFlow::VisualOverflowRect();

  // In normal compositing mode, LayoutView doesn't actually apply clipping
  // on its descendants. Instead their visual overflow is propagated to
  // compositor()->m_rootContentLayer for accelerated scrolling.
  return LayoutOverflowRect();
}

LayoutRect LayoutView::LocalVisualRect() const {
  // TODO(wangxianzhu): This is only required without rootLayerScrolls (though
  // it is also correct but unnecessary with rootLayerScrolls) because of the
  // special LayoutView overflow model.
  LayoutRect rect = VisualOverflowRect();
  rect.Unite(LayoutRect(rect.Location(), ViewRect().Size()));
  return rect;
}

void LayoutView::MapLocalToAncestor(const LayoutBoxModelObject* ancestor,
                                    TransformState& transform_state,
                                    MapCoordinatesFlags mode) const {
  if (!ancestor && mode & kUseTransforms &&
      ShouldUseTransformFromContainer(0)) {
    TransformationMatrix t;
    GetTransformFromContainer(0, LayoutSize(), t);
    transform_state.ApplyTransform(t);
  }

  if ((mode & kIsFixed) && frame_view_) {
    transform_state.Move(OffsetForFixedPosition());
    // IsFixed flag is only applicable within this LayoutView.
    mode &= ~kIsFixed;
  }

  if (ancestor == this)
    return;

  if (mode & kTraverseDocumentBoundaries) {
    LayoutPartItem parent_doc_layout_item = GetFrame()->OwnerLayoutItem();
    if (!parent_doc_layout_item.IsNull()) {
      if (!(mode & kInputIsInFrameCoordinates)) {
        transform_state.Move(
            LayoutSize(-GetFrame()->View()->GetScrollOffset()));
      } else {
        // The flag applies to immediate LayoutView only.
        mode &= ~kInputIsInFrameCoordinates;
      }

      transform_state.Move(parent_doc_layout_item.ContentBoxOffset());

      parent_doc_layout_item.MapLocalToAncestor(ancestor, transform_state,
                                                mode);
    } else {
      GetFrameView()->ApplyTransformForTopFrameSpace(transform_state);
    }
  }
}

const LayoutObject* LayoutView::PushMappingToContainer(
    const LayoutBoxModelObject* ancestor_to_stop_at,
    LayoutGeometryMap& geometry_map) const {
  LayoutSize offset;
  LayoutObject* container = nullptr;

  if (geometry_map.GetMapCoordinatesFlags() & kTraverseDocumentBoundaries) {
    if (LayoutPart* parent_doc_layout_object = ToLayoutPart(
            LayoutAPIShim::LayoutObjectFrom(GetFrame()->OwnerLayoutItem()))) {
      offset = -LayoutSize(frame_view_->GetScrollOffset());
      offset += parent_doc_layout_object->ContentBoxOffset();
      container = parent_doc_layout_object;
    }
  }

  // If a container was specified, and was not 0 or the LayoutView, then we
  // should have found it by now unless we're traversing to a parent document.
  DCHECK(!ancestor_to_stop_at || ancestor_to_stop_at == this || container);

  if ((!ancestor_to_stop_at || container) &&
      ShouldUseTransformFromContainer(container)) {
    TransformationMatrix t;
    GetTransformFromContainer(container, LayoutSize(), t);
    geometry_map.Push(this, t, kContainsFixedPosition,
                      OffsetForFixedPosition());
  } else {
    geometry_map.Push(this, offset, 0, OffsetForFixedPosition());
  }

  return container;
}

void LayoutView::MapAncestorToLocal(const LayoutBoxModelObject* ancestor,
                                    TransformState& transform_state,
                                    MapCoordinatesFlags mode) const {
  if (this != ancestor && (mode & kTraverseDocumentBoundaries)) {
    if (LayoutPart* parent_doc_layout_object = ToLayoutPart(
            LayoutAPIShim::LayoutObjectFrom(GetFrame()->OwnerLayoutItem()))) {
      // A LayoutView is a containing block for fixed-position elements, so
      // don't carry this state across frames.
      parent_doc_layout_object->MapAncestorToLocal(ancestor, transform_state,
                                                   mode & ~kIsFixed);

      transform_state.Move(parent_doc_layout_object->ContentBoxOffset());
      transform_state.Move(LayoutSize(-GetFrame()->View()->GetScrollOffset()));
    }
  } else {
    DCHECK(this == ancestor || !ancestor);
  }

  if (mode & kIsFixed)
    transform_state.Move(OffsetForFixedPosition());
}

void LayoutView::ComputeSelfHitTestRects(Vector<LayoutRect>& rects,
                                         const LayoutPoint&) const {
  // Record the entire size of the contents of the frame. Note that we don't
  // just use the viewport size (containing block) here because we want to
  // ensure this includes all children (so we can avoid walking them
  // explicitly).
  rects.push_back(LayoutRect(LayoutPoint::Zero(),
                             LayoutSize(GetFrameView()->ContentsSize())));
}

PaintInvalidationReason LayoutView::InvalidatePaintIfNeeded(
    const PaintInvalidationState& paint_invalidation_state) {
  return LayoutBlockFlow::InvalidatePaintIfNeeded(paint_invalidation_state);
}

PaintInvalidationReason LayoutView::InvalidatePaintIfNeeded(
    const PaintInvalidatorContext& context) const {
  return ViewPaintInvalidator(*this, context).InvalidatePaintIfNeeded();
}

void LayoutView::Paint(const PaintInfo& paint_info,
                       const LayoutPoint& paint_offset) const {
  ViewPainter(*this).Paint(paint_info, paint_offset);
}

void LayoutView::PaintBoxDecorationBackground(const PaintInfo& paint_info,
                                              const LayoutPoint&) const {
  ViewPainter(*this).PaintBoxDecorationBackground(paint_info);
}

static void SetShouldDoFullPaintInvalidationForViewAndAllDescendantsInternal(
    LayoutObject* object) {
  object->SetShouldDoFullPaintInvalidation();
  for (LayoutObject* child = object->SlowFirstChild(); child;
       child = child->NextSibling()) {
    SetShouldDoFullPaintInvalidationForViewAndAllDescendantsInternal(child);
  }
}

void LayoutView::SetShouldDoFullPaintInvalidationForViewAndAllDescendants() {
  if (RuntimeEnabledFeatures::slimmingPaintV2Enabled())
    SetShouldDoFullPaintInvalidationIncludingNonCompositingDescendants();
  else
    SetShouldDoFullPaintInvalidationForViewAndAllDescendantsInternal(this);
}

void LayoutView::InvalidatePaintForViewAndCompositedLayers() {
  SetShouldDoFullPaintInvalidationIncludingNonCompositingDescendants();

  // The only way we know how to hit these ASSERTS below this point is via the
  // Chromium OS login screen.
  DisableCompositingQueryAsserts disabler;

  if (Compositor()->InCompositingMode())
    Compositor()->FullyInvalidatePaint();
}

bool LayoutView::MapToVisualRectInAncestorSpace(
    const LayoutBoxModelObject* ancestor,
    LayoutRect& rect,
    MapCoordinatesFlags mode,
    VisualRectFlags visual_rect_flags) const {
  TransformState transform_state(TransformState::kApplyTransformDirection,
                                 FloatQuad(FloatRect(rect)));
  bool retval = MapToVisualRectInAncestorSpaceInternal(
      ancestor, transform_state, mode, visual_rect_flags);
  transform_state.Flatten();
  rect = LayoutRect(transform_state.LastPlanarQuad().BoundingBox());
  return retval;
}

bool LayoutView::MapToVisualRectInAncestorSpaceInternal(
    const LayoutBoxModelObject* ancestor,
    TransformState& transform_state,
    VisualRectFlags visual_rect_flags) const {
  return MapToVisualRectInAncestorSpaceInternal(ancestor, transform_state, 0,
                                                visual_rect_flags);
}

bool LayoutView::MapToVisualRectInAncestorSpaceInternal(
    const LayoutBoxModelObject* ancestor,
    TransformState& transform_state,
    MapCoordinatesFlags mode,
    VisualRectFlags visual_rect_flags) const {
  if (mode & kIsFixed)
    transform_state.Move(OffsetForFixedPosition(true));

  // Apply our transform if we have one (because of full page zooming).
  if (Layer() && Layer()->Transform()) {
    transform_state.ApplyTransform(Layer()->CurrentTransform(),
                                   TransformState::kFlattenTransform);
  }

  transform_state.Flatten();

  if (ancestor == this)
    return true;

  Element* owner = GetDocument().LocalOwner();
  if (!owner) {
    LayoutRect rect(transform_state.LastPlanarQuad().BoundingBox());
    bool retval = GetFrameView()->MapToVisualRectInTopFrameSpace(rect);
    transform_state.SetQuad(FloatQuad(FloatRect(rect)));
    return retval;
  }

  if (LayoutBox* obj = owner->GetLayoutBox()) {
    LayoutRect rect(transform_state.LastPlanarQuad().BoundingBox());
    if (!(mode & kInputIsInFrameCoordinates)) {
      // Intersect the viewport with the visual rect.
      LayoutRect view_rectangle = ViewRect();
      if (visual_rect_flags & kEdgeInclusive) {
        if (!rect.InclusiveIntersect(view_rectangle)) {
          transform_state.SetQuad(FloatQuad(FloatRect(rect)));
          return false;
        }
      } else {
        rect.Intersect(view_rectangle);
      }

      // Adjust for scroll offset of the view.
      rect.MoveBy(-view_rectangle.Location());
    }
    // Frames are painted at rounded-int position. Since we cannot efficiently
    // compute the subpixel offset of painting at this point in a a bottom-up
    // walk, round to the enclosing int rect, which will enclose the actual
    // visible rect.
    rect = LayoutRect(EnclosingIntRect(rect));

    // Adjust for frame border.
    rect.Move(obj->ContentBoxOffset());
    transform_state.SetQuad(FloatQuad(FloatRect(rect)));

    return obj->MapToVisualRectInAncestorSpaceInternal(
        ancestor, transform_state, visual_rect_flags);
  }

  // This can happen, e.g., if the iframe element has display:none.
  transform_state.SetQuad(FloatQuad(FloatRect()));
  return false;
}

LayoutSize LayoutView::OffsetForFixedPosition(
    bool include_pending_scroll) const {
  FloatSize adjustment;
  if (frame_view_) {
    adjustment += frame_view_->GetScrollOffset();

    // FIXME: Paint invalidation should happen after scroll updates, so there
    // should be no pending scroll delta.
    // However, we still have paint invalidation during layout, so we can't
    // DCHECK for now. crbug.com/434950.
    // DCHECK(m_frameView->pendingScrollDelta().isZero());
    // If we have a pending scroll, invalidate the previous scroll position.
    if (include_pending_scroll && !frame_view_->PendingScrollDelta().IsZero())
      adjustment -= frame_view_->PendingScrollDelta();
  }

  if (HasOverflowClip())
    adjustment += FloatSize(ScrolledContentOffset());

  return RoundedLayoutSize(adjustment);
}

void LayoutView::AbsoluteRects(Vector<IntRect>& rects,
                               const LayoutPoint& accumulated_offset) const {
  rects.push_back(
      PixelSnappedIntRect(accumulated_offset, LayoutSize(Layer()->size())));
}

void LayoutView::AbsoluteQuads(Vector<FloatQuad>& quads,
                               MapCoordinatesFlags mode) const {
  quads.push_back(LocalToAbsoluteQuad(
      FloatRect(FloatPoint(), FloatSize(Layer()->size())), mode));
}

static LayoutObject* LayoutObjectAfterPosition(LayoutObject* object,
                                               unsigned offset) {
  if (!object)
    return nullptr;

  LayoutObject* child = object->ChildAt(offset);
  return child ? child : object->NextInPreOrderAfterChildren();
}

static LayoutRect SelectionRectForLayoutObject(const LayoutObject* object) {
  if (!object->IsRooted())
    return LayoutRect();

  if (!object->CanUpdateSelectionOnRootLineBoxes())
    return LayoutRect();

  return object->SelectionRectInViewCoordinates();
}

// TODO(yoichio): Move this to LayoutSelection.
IntRect LayoutSelection::SelectionBounds() {
  // Now create a single bounding box rect that encloses the whole selection.
  LayoutRect sel_rect;

  typedef HashSet<const LayoutBlock*> VisitedContainingBlockSet;
  VisitedContainingBlockSet visited_containing_blocks;

  Commit(*frame_selection_->GetDocument().GetLayoutView());
  LayoutObject* os = selection_start_;
  LayoutObject* stop =
      LayoutObjectAfterPosition(selection_end_, selection_end_pos_);
  while (os && os != stop) {
    if ((os->CanBeSelectionLeaf() || os == selection_start_ ||
         os == selection_end_) &&
        os->GetSelectionState() != SelectionNone) {
      // Blocks are responsible for painting line gaps and margin gaps. They
      // must be examined as well.
      sel_rect.Unite(SelectionRectForLayoutObject(os));
      const LayoutBlock* cb = os->ContainingBlock();
      while (cb && !cb->IsLayoutView()) {
        sel_rect.Unite(SelectionRectForLayoutObject(cb));
        VisitedContainingBlockSet::AddResult add_result =
            visited_containing_blocks.insert(cb);
        if (!add_result.is_new_entry)
          break;
        cb = cb->ContainingBlock();
      }
    }

    os = os->NextInPreOrder();
  }

  return PixelSnappedIntRect(sel_rect);
}

// TODO(yoichio): Move this to LayoutSelection.
void LayoutSelection::InvalidatePaintForSelection() {
  LayoutObject* end =
      LayoutObjectAfterPosition(selection_end_, selection_end_pos_);
  for (LayoutObject* o = selection_start_; o && o != end;
       o = o->NextInPreOrder()) {
    if (!o->CanBeSelectionLeaf() && o != selection_start_ &&
        o != selection_end_)
      continue;
    if (o->GetSelectionState() == SelectionNone)
      continue;

    o->SetShouldInvalidateSelection();
  }
}

// When exploring the LayoutTree looking for the nodes involved in the
// Selection, sometimes it's required to change the traversing direction because
// the "start" position is below the "end" one.
static inline LayoutObject* GetNextOrPrevLayoutObjectBasedOnDirection(
    const LayoutObject* o,
    const LayoutObject* stop,
    bool& continue_exploring,
    bool& exploring_backwards) {
  LayoutObject* next;
  if (exploring_backwards) {
    next = o->PreviousInPreOrder();
    continue_exploring = next && !(next)->IsLayoutView();
  } else {
    next = o->NextInPreOrder();
    continue_exploring = next && next != stop;
    exploring_backwards = !next && (next != stop);
    if (exploring_backwards) {
      next = stop->PreviousInPreOrder();
      continue_exploring = next && !next->IsLayoutView();
    }
  }

  return next;
}

// TODO(yoichio): Move this to LayoutSelection.
void LayoutSelection::SetSelection(
    LayoutObject* start,
    int start_pos,
    LayoutObject* end,
    int end_pos,
    SelectionPaintInvalidationMode block_paint_invalidation_mode) {
  // This code makes no assumptions as to if the layout tree is up to date or
  // not and will not try to update it. Currently clearSelection calls this
  // (intentionally) without updating the layout tree as it doesn't care.
  // Other callers may want to force recalc style before calling this.

  // Make sure both our start and end objects are defined.
  // Check www.msnbc.com and try clicking around to find the case where this
  // happened.
  if ((start && !end) || (end && !start))
    return;

  // Just return if the selection hasn't changed.
  if (selection_start_ == start && selection_start_pos_ == start_pos &&
      selection_end_ == end && selection_end_pos_ == end_pos)
    return;

  // Record the old selected objects. These will be used later when we compare
  // against the new selected objects.
  int old_start_pos = selection_start_pos_;
  int old_end_pos = selection_end_pos_;

  // Objects each have a single selection rect to examine.
  typedef HashMap<LayoutObject*, SelectionState> SelectedObjectMap;
  SelectedObjectMap old_selected_objects;
  // FIXME: |newSelectedObjects| doesn't really need to store the
  // SelectionState, it's just more convenient to have it use the same data
  // structure as |oldSelectedObjects|.
  SelectedObjectMap new_selected_objects;

  // Blocks contain selected objects and fill gaps between them, either on the
  // left, right, or in between lines and blocks.
  // In order to get the visual rect right, we have to examine left, middle, and
  // right rects individually, since otherwise the union of those rects might
  // remain the same even when changes have occurred.
  typedef HashMap<LayoutBlock*, SelectionState> SelectedBlockMap;
  SelectedBlockMap old_selected_blocks;
  // FIXME: |newSelectedBlocks| doesn't really need to store the SelectionState,
  // it's just more convenient to have it use the same data structure as
  // |oldSelectedBlocks|.
  SelectedBlockMap new_selected_blocks;

  LayoutObject* os = selection_start_;
  LayoutObject* stop =
      LayoutObjectAfterPosition(selection_end_, selection_end_pos_);
  bool exploring_backwards = false;
  bool continue_exploring = os && (os != stop);
  while (continue_exploring) {
    if ((os->CanBeSelectionLeaf() || os == selection_start_ ||
         os == selection_end_) &&
        os->GetSelectionState() != SelectionNone) {
      // Blocks are responsible for painting line gaps and margin gaps.  They
      // must be examined as well.
      old_selected_objects.Set(os, os->GetSelectionState());
      if (block_paint_invalidation_mode == kPaintInvalidationNewXOROld) {
        LayoutBlock* cb = os->ContainingBlock();
        while (cb && !cb->IsLayoutView()) {
          SelectedBlockMap::AddResult result =
              old_selected_blocks.insert(cb, cb->GetSelectionState());
          if (!result.is_new_entry)
            break;
          cb = cb->ContainingBlock();
        }
      }
    }

    os = GetNextOrPrevLayoutObjectBasedOnDirection(os, stop, continue_exploring,
                                                   exploring_backwards);
  }

  // Now clear the selection.
  SelectedObjectMap::iterator old_objects_end = old_selected_objects.end();
  for (SelectedObjectMap::iterator i = old_selected_objects.begin();
       i != old_objects_end; ++i)
    i->key->SetSelectionStateIfNeeded(SelectionNone);

  // set selection start and end
  selection_start_ = start;
  selection_start_pos_ = start_pos;
  selection_end_ = end;
  selection_end_pos_ = end_pos;

  // Update the selection status of all objects between m_selectionStart and
  // m_selectionEnd
  if (start && start == end) {
    start->SetSelectionStateIfNeeded(SelectionBoth);
  } else {
    if (start)
      start->SetSelectionStateIfNeeded(SelectionStart);
    if (end)
      end->SetSelectionStateIfNeeded(SelectionEnd);
  }

  LayoutObject* o = start;
  stop = LayoutObjectAfterPosition(end, end_pos);

  while (o && o != stop) {
    if (o != start && o != end && o->CanBeSelectionLeaf())
      o->SetSelectionStateIfNeeded(SelectionInside);
    o = o->NextInPreOrder();
  }

  // Now that the selection state has been updated for the new objects, walk
  // them again and put them in the new objects list.
  o = start;
  exploring_backwards = false;
  continue_exploring = o && (o != stop);
  while (continue_exploring) {
    if ((o->CanBeSelectionLeaf() || o == start || o == end) &&
        o->GetSelectionState() != SelectionNone) {
      new_selected_objects.Set(o, o->GetSelectionState());
      LayoutBlock* cb = o->ContainingBlock();
      while (cb && !cb->IsLayoutView()) {
        SelectedBlockMap::AddResult result =
            new_selected_blocks.insert(cb, cb->GetSelectionState());
        if (!result.is_new_entry)
          break;
        cb = cb->ContainingBlock();
      }
    }

    o = GetNextOrPrevLayoutObjectBasedOnDirection(o, stop, continue_exploring,
                                                  exploring_backwards);
  }

  // TODO(yoichio): DCHECK(frame_selection_->,,,->GetFrameView());
  if (!frame_selection_->GetDocument().GetLayoutView()->GetFrameView())
    return;

  // Have any of the old selected objects changed compared to the new selection?
  for (SelectedObjectMap::iterator i = old_selected_objects.begin();
       i != old_objects_end; ++i) {
    LayoutObject* obj = i->key;
    SelectionState new_selection_state = obj->GetSelectionState();
    SelectionState old_selection_state = i->value;
    if (new_selection_state != old_selection_state ||
        (selection_start_ == obj && old_start_pos != selection_start_pos_) ||
        (selection_end_ == obj && old_end_pos != selection_end_pos_)) {
      obj->SetShouldInvalidateSelection();
      new_selected_objects.erase(obj);
    }
  }

  // Any new objects that remain were not found in the old objects dict, and so
  // they need to be updated.
  SelectedObjectMap::iterator new_objects_end = new_selected_objects.end();
  for (SelectedObjectMap::iterator i = new_selected_objects.begin();
       i != new_objects_end; ++i)
    i->key->SetShouldInvalidateSelection();

  // Have any of the old blocks changed?
  SelectedBlockMap::iterator old_blocks_end = old_selected_blocks.end();
  for (SelectedBlockMap::iterator i = old_selected_blocks.begin();
       i != old_blocks_end; ++i) {
    LayoutBlock* block = i->key;
    SelectionState new_selection_state = block->GetSelectionState();
    SelectionState old_selection_state = i->value;
    if (new_selection_state != old_selection_state) {
      block->SetShouldInvalidateSelection();
      new_selected_blocks.erase(block);
    }
  }

  // Any new blocks that remain were not found in the old blocks dict, and so
  // they need to be updated.
  SelectedBlockMap::iterator new_blocks_end = new_selected_blocks.end();
  for (SelectedBlockMap::iterator i = new_selected_blocks.begin();
       i != new_blocks_end; ++i)
    i->key->SetShouldInvalidateSelection();
}

// TODO(yoichio): Move this to LayoutSelection.
void LayoutSelection::ClearSelection() {
  // For querying Layer::compositingState()
  // This is correct, since destroying layout objects needs to cause eager paint
  // invalidations.
  DisableCompositingQueryAsserts disabler;

  SetSelection(0, -1, 0, -1, kPaintInvalidationNewMinusOld);
}

void LayoutView::ClearSelection() {
  frame_view_->GetFrame().Selection().ClearLayoutSelection();
}

bool LayoutView::HasPendingSelection() const {
  return frame_view_->GetFrame().Selection().IsAppearanceDirty();
}

void LayoutView::CommitPendingSelection() {
  TRACE_EVENT0("blink", "LayoutView::commitPendingSelection");
  frame_view_->GetFrame().Selection().CommitAppearanceIfNeeded(*this);
}

void LayoutView::SelectionStartEnd(int& start_pos, int& end_pos) {
  frame_view_->GetFrame().Selection().LayoutSelectionStartEnd(start_pos,
                                                              end_pos);
}

// TODO(yoichio): Move this to LayoutSelection.
void LayoutSelection::SelectionStartEnd(int& start_pos, int& end_pos) {
  Commit(*frame_selection_->GetDocument().GetLayoutView());
  start_pos = selection_start_pos_;
  end_pos = selection_end_pos_;
}

bool LayoutView::ShouldUsePrintingLayout() const {
  if (!GetDocument().Printing() || !frame_view_)
    return false;
  return frame_view_->GetFrame().ShouldUsePrintingLayout();
}

LayoutRect LayoutView::ViewRect() const {
  if (ShouldUsePrintingLayout())
    return LayoutRect(LayoutPoint(), Size());
  if (frame_view_)
    return LayoutRect(frame_view_->VisibleContentRect());
  return LayoutRect();
}

LayoutRect LayoutView::OverflowClipRect(
    const LayoutPoint& location,
    OverlayScrollbarClipBehavior overlay_scrollbar_clip_behavior) const {
  LayoutRect rect = ViewRect();
  if (rect.IsEmpty())
    return LayoutBox::OverflowClipRect(location,
                                       overlay_scrollbar_clip_behavior);

  rect.SetLocation(location);
  if (HasOverflowClip())
    ExcludeScrollbars(rect, overlay_scrollbar_clip_behavior);

  return rect;
}

IntRect LayoutView::DocumentRect() const {
  LayoutRect overflow_rect(LayoutOverflowRect());
  FlipForWritingMode(overflow_rect);
  // TODO(crbug.com/650768): The pixel snapping looks incorrect.
  return PixelSnappedIntRect(overflow_rect);
}

bool LayoutView::RootBackgroundIsEntirelyFixed() const {
  return Style()->HasEntirelyFixedBackground();
}

IntSize LayoutView::GetLayoutSize(
    IncludeScrollbarsInRect scrollbar_inclusion) const {
  if (ShouldUsePrintingLayout())
    return IntSize(Size().Width().ToInt(), PageLogicalHeight().ToInt());

  if (!frame_view_)
    return IntSize();

  IntSize result = frame_view_->GetLayoutSize(kIncludeScrollbars);
  if (scrollbar_inclusion == kExcludeScrollbars)
    result =
        frame_view_->LayoutViewportScrollableArea()->ExcludeScrollbars(result);
  return result;
}

int LayoutView::ViewLogicalWidth(
    IncludeScrollbarsInRect scrollbar_inclusion) const {
  return Style()->IsHorizontalWritingMode() ? ViewWidth(scrollbar_inclusion)
                                            : ViewHeight(scrollbar_inclusion);
}

int LayoutView::ViewLogicalHeight(
    IncludeScrollbarsInRect scrollbar_inclusion) const {
  return Style()->IsHorizontalWritingMode() ? ViewHeight(scrollbar_inclusion)
                                            : ViewWidth(scrollbar_inclusion);
}

int LayoutView::ViewLogicalWidthForBoxSizing() const {
  return ViewLogicalWidth(RuntimeEnabledFeatures::rootLayerScrollingEnabled()
                              ? kIncludeScrollbars
                              : kExcludeScrollbars);
}

int LayoutView::ViewLogicalHeightForBoxSizing() const {
  return ViewLogicalHeight(RuntimeEnabledFeatures::rootLayerScrollingEnabled()
                               ? kIncludeScrollbars
                               : kExcludeScrollbars);
}

LayoutUnit LayoutView::ViewLogicalHeightForPercentages() const {
  if (ShouldUsePrintingLayout())
    return PageLogicalHeight();
  return LayoutUnit(ViewLogicalHeight());
}

float LayoutView::ZoomFactor() const {
  return frame_view_->GetFrame().PageZoomFactor();
}

void LayoutView::UpdateHitTestResult(HitTestResult& result,
                                     const LayoutPoint& point) {
  if (result.InnerNode())
    return;

  Node* node = GetDocument().documentElement();
  if (node) {
    LayoutPoint adjusted_point = point;
    OffsetForContents(adjusted_point);
    result.SetNodeAndPosition(node, adjusted_point);
  }
}

bool LayoutView::UsesCompositing() const {
  return compositor_ && compositor_->StaleInCompositingMode();
}

PaintLayerCompositor* LayoutView::Compositor() {
  if (!compositor_)
    compositor_ = WTF::WrapUnique(new PaintLayerCompositor(*this));

  return compositor_.get();
}

void LayoutView::SetIsInWindow(bool is_in_window) {
  if (compositor_)
    compositor_->SetIsInWindow(is_in_window);
#if CHECK_DISPLAY_ITEM_CLIENT_ALIVENESS
  // We don't invalidate layers during Document::detachLayoutTree(), so must
  // clear the should-keep-alive DisplayItemClients which may be deleted before
  // the layers being subsequence owners.
  if (!is_in_window && Layer())
    Layer()->EndShouldKeepAliveAllClientsRecursive();
#endif
}

IntervalArena* LayoutView::GetIntervalArena() {
  if (!interval_arena_)
    interval_arena_ = IntervalArena::Create();
  return interval_arena_.Get();
}

bool LayoutView::BackgroundIsKnownToBeOpaqueInRect(const LayoutRect&) const {
  // FIXME: Remove this main frame check. Same concept applies to subframes too.
  if (!GetFrame()->IsMainFrame())
    return false;

  return frame_view_->HasOpaqueBackground();
}

FloatSize LayoutView::ViewportSizeForViewportUnits() const {
  return GetFrameView() ? GetFrameView()->ViewportSizeForViewportUnits()
                        : FloatSize();
}

void LayoutView::WillBeDestroyed() {
  // TODO(wangxianzhu): This is a workaround of crbug.com/570706.
  // Should find and fix the root cause.
  if (PaintLayer* layer = this->Layer())
    layer->SetNeedsRepaint();
  LayoutBlockFlow::WillBeDestroyed();
  compositor_.reset();
}

void LayoutView::UpdateFromStyle() {
  LayoutBlockFlow::UpdateFromStyle();

  // LayoutView of the main frame is responsible for painting base background.
  if (GetDocument().IsInMainFrame())
    SetHasBoxDecorationBackground(true);
}

bool LayoutView::AllowsOverflowClip() const {
  return RuntimeEnabledFeatures::rootLayerScrollingEnabled();
}

ScrollResult LayoutView::Scroll(ScrollGranularity granularity,
                                const FloatSize& delta) {
  // TODO(bokan): We shouldn't need this specialization but we currently do
  // because of the Windows pan scrolling path. That should go through a more
  // normalized ScrollManager-like scrolling path and we should get rid of
  // of this override. All frame scrolling should be handled by
  // ViewportScrollCallback.

  if (!GetFrameView())
    return ScrollResult(false, false, delta.Width(), delta.Height());

  return GetFrameView()->GetScrollableArea()->UserScroll(granularity, delta);
}

LayoutRect LayoutView::DebugRect() const {
  LayoutRect rect;
  LayoutBlock* block = ContainingBlock();
  if (block)
    block->AdjustChildDebugRect(rect);

  rect.SetWidth(LayoutUnit(ViewWidth(kIncludeScrollbars)));
  rect.SetHeight(LayoutUnit(ViewHeight(kIncludeScrollbars)));

  return rect;
}

bool LayoutView::PaintedOutputOfObjectHasNoEffectRegardlessOfSize() const {
  // Frame scroll corner is painted using LayoutView as the display item client.
  if (!RuntimeEnabledFeatures::rootLayerScrollingEnabled() &&
      (GetFrameView()->HorizontalScrollbar() ||
       GetFrameView()->VerticalScrollbar()))
    return false;

  return LayoutBlockFlow::PaintedOutputOfObjectHasNoEffectRegardlessOfSize();
}

}  // namespace blink