grid_layout_algorithm.cc | Explore in Territory

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

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/351564777): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#include "third_party/blink/renderer/core/layout/grid/grid_layout_algorithm.h"

#include "third_party/blink/renderer/core/layout/constraint_space_builder.h"
#include "third_party/blink/renderer/core/layout/disable_layout_side_effects_scope.h"
#include "third_party/blink/renderer/core/layout/fragmentation_utils.h"
#include "third_party/blink/renderer/core/layout/length_utils.h"
#include "third_party/blink/renderer/core/layout/logical_box_fragment.h"
#include "third_party/blink/renderer/core/layout/relative_utils.h"
#include "third_party/blink/renderer/core/layout/space_utils.h"

namespace blink {

GridLayoutAlgorithm::GridLayoutAlgorithm(const LayoutAlgorithmParams& params)
    : … { … }

namespace {

void CacheGridItemsProperties(const GridLayoutTrackCollection& track_collection,
                              GridItems* grid_items) { … }

bool HasBlockSizeDependentGridItem(const GridItems& grid_items) { … }

}  // namespace

const LayoutResult* GridLayoutAlgorithm::Layout() { … }

const LayoutResult* GridLayoutAlgorithm::LayoutInternal() { … }

MinMaxSizesResult GridLayoutAlgorithm::ComputeMinMaxSizes(
    const MinMaxSizesFloatInput&) { … }

MinMaxSizes GridLayoutAlgorithm::ComputeSubgridMinMaxSizes(
    const GridSizingSubtree& sizing_subtree) const { … }

LayoutUnit GridLayoutAlgorithm::ComputeSubgridIntrinsicBlockSize(
    const GridSizingSubtree& sizing_subtree) const { … }

namespace {

GridArea SubgriddedAreaInParent(const SubgriddedItemData& opt_subgrid_data) { … }

FragmentGeometry CalculateInitialFragmentGeometryForSubgrid(
    const GridItemData& subgrid_data,
    const ConstraintSpace& space,
    const GridSizingSubtree& sizing_subtree = kNoGridSizingSubtree) { … }

}  // namespace

wtf_size_t GridLayoutAlgorithm::BuildGridSizingSubtree(
    GridSizingTree* sizing_tree,
    HeapVector<Member<LayoutBox>>* opt_oof_children,
    const SubgriddedItemData& opt_subgrid_data,
    const GridLineResolver* opt_parent_line_resolver,
    bool must_invalidate_placement_cache,
    bool must_ignore_children) const { … }

GridSizingTree GridLayoutAlgorithm::BuildGridSizingTree(
    HeapVector<Member<LayoutBox>>* opt_oof_children) const { … }

GridSizingTree GridLayoutAlgorithm::BuildGridSizingTreeIgnoringChildren()
    const { … }

LayoutUnit GridLayoutAlgorithm::Baseline(
    const GridLayoutData& layout_data,
    const GridItemData& grid_item,
    GridTrackSizingDirection track_direction) const { … }

namespace {

struct FirstSetGeometry { … };

FirstSetGeometry ComputeFirstSetGeometry(
    const GridSizingTrackCollection& track_collection,
    const ComputedStyle& container_style,
    LayoutUnit available_size,
    LayoutUnit start_border_scrollbar_padding) { … }

}  // namespace

void GridLayoutAlgorithm::ComputeGridGeometry(
    const GridSizingTree& grid_sizing_tree,
    LayoutUnit* intrinsic_block_size) { … }

LayoutUnit GridLayoutAlgorithm::ComputeIntrinsicBlockSizeIgnoringChildren()
    const { … }

namespace {

const LayoutResult* LayoutGridItemForMeasure(
    const GridItemData& grid_item,
    const ConstraintSpace& constraint_space,
    SizingConstraint sizing_constraint) { … }

LayoutUnit GetExtraMarginForBaseline(const BoxStrut& margins,
                                     const SubgriddedItemData& subgridded_item,
                                     GridTrackSizingDirection track_direction,
                                     WritingMode writing_mode) { … }

LayoutUnit GetLogicalBaseline(const GridItemData& grid_item,
                              const LogicalBoxFragment& baseline_fragment,
                              GridTrackSizingDirection track_direction) { … }

LayoutUnit GetSynthesizedLogicalBaseline(
    const GridItemData& grid_item,
    LayoutUnit block_size,
    GridTrackSizingDirection track_direction) { … }

LayoutUnit ComputeBlockSizeForSubgrid(const GridSizingSubtree& sizing_subtree,
                                      const GridItemData& subgrid_data,
                                      const ConstraintSpace& space) { … }

}  // namespace

LayoutUnit GridLayoutAlgorithm::ContributionSizeForGridItem(
    const GridSizingSubtree& sizing_subtree,
    GridItemContributionType contribution_type,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint,
    GridItemData* grid_item) const { … }

// https://drafts.csswg.org/css-grid-2/#auto-repeat
wtf_size_t GridLayoutAlgorithm::ComputeAutomaticRepetitions(
    const GridSpan& subgrid_span,
    GridTrackSizingDirection track_direction) const { … }

wtf_size_t GridLayoutAlgorithm::ComputeAutomaticRepetitionsForSubgrid(
    wtf_size_t subgrid_span_size,
    GridTrackSizingDirection track_direction) const { … }

void GridLayoutAlgorithm::ComputeGridItemBaselines(
    const scoped_refptr<const GridLayoutTree>& layout_tree,
    const GridSizingSubtree& sizing_subtree,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint) const { … }

std::unique_ptr<GridLayoutTrackCollection>
GridLayoutAlgorithm::CreateSubgridTrackCollection(
    const SubgriddedItemData& subgrid_data,
    GridTrackSizingDirection track_direction) const { … }

void GridLayoutAlgorithm::InitializeTrackCollection(
    const SubgriddedItemData& opt_subgrid_data,
    GridTrackSizingDirection track_direction,
    GridLayoutData* layout_data) const { … }

namespace {

GridTrackSizingDirection RelativeDirectionInSubgrid(
    GridTrackSizingDirection track_direction,
    const GridItemData& subgrid_data) { … }

std::optional<GridTrackSizingDirection> RelativeDirectionFilterInSubgrid(
    const std::optional<GridTrackSizingDirection>& opt_track_direction,
    const GridItemData& subgrid_data) { … }

}  // namespace

void GridLayoutAlgorithm::InitializeTrackSizes(
    const GridSizingSubtree& sizing_subtree,
    const SubgriddedItemData& opt_subgrid_data,
    const std::optional<GridTrackSizingDirection>& opt_track_direction) const { … }

void GridLayoutAlgorithm::InitializeTrackSizes(
    const GridSizingTree& sizing_tree,
    const std::optional<GridTrackSizingDirection>& opt_track_direction) const { … }

namespace {

struct BlockSizeDependentGridItem { … };

Vector<BlockSizeDependentGridItem> BlockSizeDependentGridItems(
    const GridItems& grid_items,
    const GridSizingTrackCollection& track_collection) { … }

bool MayChangeBlockSizeDependentGridItemContributions(
    const Vector<BlockSizeDependentGridItem>& dependent_items,
    const GridSizingTrackCollection& track_collection) { … }

}  // namespace

// https://drafts.csswg.org/css-grid-2/#algo-track-sizing
void GridLayoutAlgorithm::ComputeUsedTrackSizes(
    const GridSizingSubtree& sizing_subtree,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint,
    bool* opt_needs_additional_pass) const { … }

void GridLayoutAlgorithm::CompleteTrackSizingAlgorithm(
    const GridSizingSubtree& sizing_subtree,
    const SubgriddedItemData& opt_subgrid_data,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint,
    bool* opt_needs_additional_pass) const { … }

namespace {

// A subgrid's `MinMaxSizes` cache is stored in its respective `LayoutGrid` and
// gets invalidated via the `IsSubgridMinMaxSizesCacheDirty` flag.
//
// However, a subgrid might need to invalidate the cache if it inherited a
// different track collection in its subgridded axis, which might cause its
// intrinsic sizes to change. This invalidation goes from parent to children,
// which is not accounted for by the invalidation logic in `LayoutObject`.
//
// This method addresses such issue by traversing the tree in postorder checking
// whether the cache at each subgrid level is reusable or not: if the subgrid
// has a valid cache, but its input tracks for the subgridded axis changed,
// then we'll invalidate the cache for that subgrid and its ancestors.
bool ValidateMinMaxSizesCache(const GridNode& grid_node,
                              const GridSizingSubtree& sizing_subtree,
                              GridTrackSizingDirection track_direction) { … }

}  // namespace

void GridLayoutAlgorithm::CompleteTrackSizingAlgorithm(
    const GridSizingTree& sizing_tree,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint,
    bool* opt_needs_additional_pass) const { … }

void GridLayoutAlgorithm::ComputeBaselineAlignment(
    const scoped_refptr<const GridLayoutTree>& layout_tree,
    const GridSizingSubtree& sizing_subtree,
    const SubgriddedItemData& opt_subgrid_data,
    const std::optional<GridTrackSizingDirection>& opt_track_direction,
    SizingConstraint sizing_constraint) const { … }

void GridLayoutAlgorithm::CompleteFinalBaselineAlignment(
    const GridSizingTree& sizing_tree) const { … }

template <typename CallbackFunc>
void GridLayoutAlgorithm::ForEachSubgrid(
    const GridSizingSubtree& sizing_subtree,
    const CallbackFunc& callback_func,
    bool should_compute_min_max_sizes) const { … }

LayoutUnit GridLayoutAlgorithm::ComputeSubgridIntrinsicSize(
    const GridSizingSubtree& sizing_subtree,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint) const { … }

// Helpers for the track sizing algorithm.
namespace {

ClampedFloat;
SetIterator;

const float kFloatEpsilon = …;

SetIterator GetSetIteratorForItem(const GridItemData& grid_item,
                                  GridSizingTrackCollection& track_collection) { … }

LayoutUnit DefiniteGrowthLimit(const GridSet& set) { … }

// Returns the corresponding size to be increased by accommodating a grid item's
// contribution; for intrinsic min track sizing functions, return the base size.
// For intrinsic max track sizing functions, return the growth limit.
LayoutUnit AffectedSizeForContribution(
    const GridSet& set,
    GridItemContributionType contribution_type) { … }

void GrowAffectedSizeByPlannedIncrease(
    GridItemContributionType contribution_type,
    GridSet* set) { … }

void AccomodateSubgridExtraMargins(
    LayoutUnit start_extra_margin,
    LayoutUnit end_extra_margin,
    GridItemIndices set_indices,
    GridSizingTrackCollection* track_collection) { … }

// Returns true if a set should increase its used size according to the steps in
// https://drafts.csswg.org/css-grid-2/#algo-spanning-items; false otherwise.
bool IsContributionAppliedToSet(const GridSet& set,
                                GridItemContributionType contribution_type) { … }

// https://drafts.csswg.org/css-grid-2/#extra-space
// Returns true if a set's used size should be consider to grow beyond its limit
// (see the "Distribute space beyond limits" section); otherwise, false.
// Note that we will deliberately return false in cases where we don't have a
// collection of tracks different than "all affected tracks".
bool ShouldUsedSizeGrowBeyondLimit(const GridSet& set,
                                   GridItemContributionType contribution_type) { … }

bool IsDistributionForGrowthLimits(GridItemContributionType contribution_type) { … }

enum class InfinitelyGrowableBehavior { … };

// We define growth potential = limit - affected size; for base sizes, the limit
// is its growth limit. For growth limits, the limit is infinity if it is marked
// as "infinitely growable", and equal to the growth limit otherwise.
LayoutUnit GrowthPotentialForSet(
    const GridSet& set,
    GridItemContributionType contribution_type,
    InfinitelyGrowableBehavior infinitely_growable_behavior =
        InfinitelyGrowableBehavior::kEnforce) { … }

template <typename T>
bool AreEqual(T a, T b) { … }

template <>
bool AreEqual<float>(float a, float b) { … }

// Follow the definitions from https://drafts.csswg.org/css-grid-2/#extra-space;
// notice that this method replaces the notion of "tracks" with "sets".
template <bool is_equal_distribution>
void DistributeExtraSpaceToSets(LayoutUnit extra_space,
                                float flex_factor_sum,
                                GridItemContributionType contribution_type,
                                GridSetPtrVector* sets_to_grow,
                                GridSetPtrVector* sets_to_grow_beyond_limit) { … }

void DistributeExtraSpaceToSetsEqually(
    LayoutUnit extra_space,
    GridItemContributionType contribution_type,
    GridSetPtrVector* sets_to_grow,
    GridSetPtrVector* sets_to_grow_beyond_limit = nullptr) { … }

void DistributeExtraSpaceToWeightedSets(
    LayoutUnit extra_space,
    float flex_factor_sum,
    GridItemContributionType contribution_type,
    GridSetPtrVector* sets_to_grow) { … }

}  // namespace

void GridLayoutAlgorithm::IncreaseTrackSizesToAccommodateGridItems(
    GridItemDataPtrVector::iterator group_begin,
    GridItemDataPtrVector::iterator group_end,
    const GridSizingSubtree& sizing_subtree,
    bool is_group_spanning_flex_track,
    SizingConstraint sizing_constraint,
    GridItemContributionType contribution_type,
    GridSizingTrackCollection* track_collection) const { … }

// https://drafts.csswg.org/css-grid-2/#algo-content
void GridLayoutAlgorithm::ResolveIntrinsicTrackSizes(
    const GridSizingSubtree& sizing_subtree,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint) const { … }

// https://drafts.csswg.org/css-grid-2/#algo-grow-tracks
void GridLayoutAlgorithm::MaximizeTracks(
    SizingConstraint sizing_constraint,
    GridSizingTrackCollection* track_collection) const { … }

// https://drafts.csswg.org/css-grid-2/#algo-stretch
void GridLayoutAlgorithm::StretchAutoTracks(
    SizingConstraint sizing_constraint,
    GridSizingTrackCollection* track_collection) const { … }

// https://drafts.csswg.org/css-grid-2/#algo-flex-tracks
void GridLayoutAlgorithm::ExpandFlexibleTracks(
    const GridSizingSubtree& sizing_subtree,
    GridTrackSizingDirection track_direction,
    SizingConstraint sizing_constraint) const { … }

LayoutUnit GridLayoutAlgorithm::GutterSize(
    GridTrackSizingDirection track_direction,
    LayoutUnit parent_grid_gutter_size) const { … }

// TODO(ikilpatrick): Determine if other uses of this method need to respect
// |grid_min_available_size_| similar to |StretchAutoTracks|.
LayoutUnit GridLayoutAlgorithm::DetermineFreeSpace(
    SizingConstraint sizing_constraint,
    const GridSizingTrackCollection& track_collection) const { … }

namespace {

// Returns the alignment offset for either the inline or block direction.
LayoutUnit AlignmentOffset(LayoutUnit container_size,
                           LayoutUnit size,
                           LayoutUnit margin_start,
                           LayoutUnit margin_end,
                           LayoutUnit baseline_offset,
                           AxisEdge axis_edge,
                           bool is_overflow_safe) { … }

void AlignmentOffsetForOutOfFlow(AxisEdge inline_axis_edge,
                                 AxisEdge block_axis_edge,
                                 LogicalSize container_size,
                                 LogicalStaticPosition::InlineEdge* inline_edge,
                                 LogicalStaticPosition::BlockEdge* block_edge,
                                 LogicalOffset* offset) { … }

}  // namespace

ConstraintSpace GridLayoutAlgorithm::CreateConstraintSpace(
    LayoutResultCacheSlot cache_slot,
    const GridItemData& grid_item,
    const LogicalSize& containing_grid_area_size,
    const LogicalSize& fixed_available_size,
    GridLayoutSubtree&& opt_layout_subtree,
    bool min_block_size_should_encompass_intrinsic_size,
    std::optional<LayoutUnit> opt_child_block_offset) const { … }

ConstraintSpace GridLayoutAlgorithm::CreateConstraintSpaceForLayout(
    const GridItemData& grid_item,
    const GridLayoutData& layout_data,
    GridLayoutSubtree&& opt_layout_subtree,
    LogicalRect* containing_grid_area,
    LayoutUnit unavailable_block_size,
    bool min_block_size_should_encompass_intrinsic_size,
    std::optional<LayoutUnit> opt_child_block_offset) const { … }

ConstraintSpace GridLayoutAlgorithm::CreateConstraintSpaceForMeasure(
    const SubgriddedItemData& subgridded_item,
    GridTrackSizingDirection track_direction,
    std::optional<LayoutUnit> opt_fixed_inline_size) const { … }

namespace {

// Determining the grid's baseline is prioritized based on grid order (as
// opposed to DOM order). The baseline of the grid is determined by the first
// grid item with baseline alignment in the first row. If no items have
// baseline alignment, fall back to the first item in row-major order.
class BaselineAccumulator { … };

}  // namespace

void GridLayoutAlgorithm::PlaceGridItems(
    const GridSizingTree& sizing_tree,
    Vector<EBreakBetween>* out_row_break_between,
    Vector<GridItemPlacementData>* out_grid_items_placement_data) { … }

// This is only used in GridLayoutAlgorithm::PlaceGridItemsForFragmentation(),
// but placed here to add WTF VectorTraits.
struct ResultAndOffsets { … };

void GridLayoutAlgorithm::PlaceGridItemsForFragmentation(
    const GridSizingTree& sizing_tree,
    const Vector<EBreakBetween>& row_break_between,
    Vector<GridItemPlacementData>* grid_items_placement_data,
    Vector<LayoutUnit>* row_offset_adjustments,
    LayoutUnit* intrinsic_block_size,
    LayoutUnit* offset_in_stitched_container) { … }

void GridLayoutAlgorithm::PlaceOutOfFlowItems(
    const GridLayoutData& layout_data,
    const LayoutUnit block_size,
    HeapVector<Member<LayoutBox>>& oof_children) { … }

void GridLayoutAlgorithm::SetReadingFlowElements(
    const GridSizingTree& sizing_tree) { … }

namespace {

Vector<std::div_t> ComputeTrackSizesInRange(
    const GridLayoutTrackCollection& track_collection,
    const wtf_size_t range_begin_set_index,
    const wtf_size_t range_set_count) { … }

// For out of flow items that are located in the middle of a range, computes
// the extra offset relative to the start of its containing range.
LayoutUnit ComputeTrackOffsetInRange(
    const GridLayoutTrackCollection& track_collection,
    const wtf_size_t range_begin_set_index,
    const wtf_size_t range_set_count,
    const wtf_size_t offset_in_range) { … }

template <bool snap_to_end_of_track>
LayoutUnit TrackOffset(const GridLayoutTrackCollection& track_collection,
                       const wtf_size_t range_index,
                       const wtf_size_t offset_in_range) { … }

LayoutUnit TrackStartOffset(const GridLayoutTrackCollection& track_collection,
                            const wtf_size_t range_index,
                            const wtf_size_t offset_in_range) { … }

LayoutUnit TrackEndOffset(const GridLayoutTrackCollection& track_collection,
                          const wtf_size_t range_index,
                          const wtf_size_t offset_in_range) { … }

void ComputeOutOfFlowOffsetAndSize(
    const GridItemData& out_of_flow_item,
    const GridLayoutTrackCollection& track_collection,
    const BoxStrut& borders,
    const LogicalSize& border_box_size,
    LayoutUnit* start_offset,
    LayoutUnit* size) { … }

}  // namespace

LayoutUnit GridLayoutAlgorithm::ComputeGridItemAvailableSize(
    const GridItemData& grid_item,
    const GridLayoutTrackCollection& track_collection,
    LayoutUnit* start_offset) const { … }

// static
LogicalRect GridLayoutAlgorithm::ComputeOutOfFlowItemContainingRect(
    const GridPlacementData& placement_data,
    const GridLayoutData& layout_data,
    const ComputedStyle& grid_style,
    const BoxStrut& borders,
    const LogicalSize& border_box_size,
    GridItemData* out_of_flow_item) { … }

}  // namespace blink

WTF_ALLOW_CLEAR_UNUSED_SLOTS_WITH_MEM_FUNCTIONS(…)
chromium/third_party/blink/renderer/core/layout/grid/grid_layout_algorithm.cc
