blob: 468348dc1cf2b71148cf3aa20a6407089d6db00f [file] [log] [blame]
// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
import 'dart:math' as math;
import 'package:flutter/foundation.dart';
import 'package:flutter/rendering.dart';
import 'base_grid_layout.dart';
/// A sliver that places multiple box children in a two dimensional arrangement.
///
/// [RenderDynamicSliverGrid] places its children in arbitrary positions determined by
/// the [DynamicSliverGridLayout] provided by the [gridDelegate].
///
/// {@macro dynamicLayouts.garbageCollection}
class RenderDynamicSliverGrid extends RenderSliverGrid {
/// Creates a sliver that contains multiple box children whose size and
/// position are managed by a delegate.
///
/// The [childManager] and [gridDelegate] arguments must not be null.
RenderDynamicSliverGrid({
required super.childManager,
required super.gridDelegate,
});
@override
void performLayout() {
final SliverConstraints constraints = this.constraints;
childManager.didStartLayout();
childManager.setDidUnderflow(false);
final double scrollOffset =
constraints.scrollOffset + constraints.cacheOrigin;
assert(scrollOffset >= 0.0);
final double remainingExtent = constraints.remainingCacheExtent;
assert(remainingExtent >= 0.0);
final double targetEndScrollOffset = scrollOffset + remainingExtent;
final DynamicSliverGridLayout layout =
gridDelegate.getLayout(constraints) as DynamicSliverGridLayout;
int leadingGarbage = 0;
int trailingGarbage = 0;
bool reachedEnd = false;
// This algorithm in principle is straight-forward: find the first child
// that overlaps the given scrollOffset, creating more children at the top
// of the grid if necessary, then walk through the grid updating and laying
// out each child and adding more at the end if necessary until we have
// enough children to cover the entire viewport.
//
// It is complicated by one minor issue, which is that any time you update
// or create a child, it's possible that some of the children that
// haven't yet been laid out will be removed, leaving the list in an
// inconsistent state, and requiring that missing nodes be recreated.
//
// To keep this mess tractable, this algorithm starts from what is currently
// the first child, if any, and then walks up and/or down from there, so
// that the nodes that might get removed are always at the edges of what has
// already been laid out.
// Make sure we have at least one child to start from.
if (firstChild == null && !addInitialChild()) {
// There are no children.
geometry = SliverGeometry.zero;
childManager.didFinishLayout();
return;
}
// We have at least one child.
assert(firstChild != null);
// These variables track the range of children that we have laid out. Within
// this range, the children have consecutive indices. Outside this range,
// it's possible for a child to get removed without notice.
RenderBox? leadingChildWithLayout, trailingChildWithLayout;
RenderBox? earliestUsefulChild = firstChild;
// A firstChild with null layout offset is likely a result of children
// reordering.
//
// We rely on firstChild to have accurate layout offset. In the case of null
// layout offset, we have to find the first child that has valid layout
// offset.
if (childScrollOffset(firstChild!) == null) {
int leadingChildrenWithoutLayoutOffset = 0;
while (earliestUsefulChild != null &&
childScrollOffset(earliestUsefulChild) == null) {
earliestUsefulChild = childAfter(earliestUsefulChild);
leadingChildrenWithoutLayoutOffset += 1;
}
// We should be able to destroy children with null layout offset safely,
// because they are likely outside of viewport
collectGarbage(leadingChildrenWithoutLayoutOffset, 0);
// If we cannot find a valid layout offset, start from the initial child.
if (firstChild == null && !addInitialChild()) {
// There are no children.
geometry = SliverGeometry.zero;
childManager.didFinishLayout();
return;
}
}
// Find the last child that is at or before the scrollOffset.
earliestUsefulChild = firstChild;
assert(earliestUsefulChild != null);
for (int index = indexOf(earliestUsefulChild!) - 1;
childScrollOffset(earliestUsefulChild!)! > scrollOffset;
--index) {
final double earliestScrollOffset =
childScrollOffset(earliestUsefulChild)!;
// We have to add children before the earliestUsefulChild.
SliverGridGeometry gridGeometry = layout.getGeometryForChildIndex(index);
earliestUsefulChild = insertAndLayoutLeadingChild(
gridGeometry.getBoxConstraints(constraints),
parentUsesSize: true,
);
// There are no more preceding children.
if (earliestUsefulChild == null) {
final SliverGridParentData childParentData =
firstChild!.parentData! as SliverGridParentData;
childParentData.layoutOffset = gridGeometry.scrollOffset;
childParentData.crossAxisOffset = gridGeometry.crossAxisOffset;
if (scrollOffset == 0.0) {
// insertAndLayoutLeadingChild only lays out the children before
// firstChild. In this case, nothing has been laid out. We have
// to lay out firstChild manually.
gridGeometry = layout.getGeometryForChildIndex(0);
firstChild!.layout(gridGeometry.getBoxConstraints(constraints),
parentUsesSize: true);
earliestUsefulChild = firstChild;
leadingChildWithLayout = earliestUsefulChild;
trailingChildWithLayout ??= earliestUsefulChild;
break;
} else {
// We ran out of children before reaching the scroll offset.
// We must inform our parent that this sliver cannot fulfill
// its contract and that we need a scroll offset correction.
geometry = SliverGeometry(
scrollOffsetCorrection: -scrollOffset,
);
return;
}
}
final double firstChildScrollOffset =
earliestScrollOffset - paintExtentOf(firstChild!);
// firstChildScrollOffset may contain double precision error
if (firstChildScrollOffset < -precisionErrorTolerance) {
// Let's assume there is no child before the first child. We will
// correct it on the next layout if it is not.
geometry = SliverGeometry(
scrollOffsetCorrection: -firstChildScrollOffset,
);
final SliverGridParentData childParentData =
firstChild!.parentData! as SliverGridParentData;
childParentData.layoutOffset = gridGeometry.scrollOffset;
childParentData.crossAxisOffset = gridGeometry.crossAxisOffset;
return;
}
final SliverGridParentData childParentData =
earliestUsefulChild.parentData! as SliverGridParentData;
gridGeometry = layout.updateGeometryForChildIndex(
indexOf(earliestUsefulChild), earliestUsefulChild.size);
childParentData.layoutOffset = gridGeometry.scrollOffset;
childParentData.crossAxisOffset = gridGeometry.crossAxisOffset;
assert(earliestUsefulChild == firstChild);
leadingChildWithLayout = earliestUsefulChild;
trailingChildWithLayout ??= earliestUsefulChild;
}
assert(childScrollOffset(firstChild!)! > -precisionErrorTolerance);
// If the scroll offset is at zero, we should make sure we are
// actually at the beginning of the list.
if (scrollOffset < precisionErrorTolerance) {
// We iterate from the firstChild in case the leading child has a 0 paint
// extent.
int indexOfFirstChild = indexOf(firstChild!);
while (indexOfFirstChild > 0) {
final double earliestScrollOffset = childScrollOffset(firstChild!)!;
// We correct one child at a time. If there are more children before
// the earliestUsefulChild, we will correct it once the scroll offset
// reaches zero again.
SliverGridGeometry gridGeometry =
layout.getGeometryForChildIndex(indexOfFirstChild - 1);
earliestUsefulChild = insertAndLayoutLeadingChild(
gridGeometry.getBoxConstraints(constraints),
parentUsesSize: true,
);
assert(earliestUsefulChild != null);
final double firstChildScrollOffset =
earliestScrollOffset - paintExtentOf(firstChild!);
final SliverGridParentData childParentData =
firstChild!.parentData! as SliverGridParentData;
gridGeometry = layout.updateGeometryForChildIndex(
indexOfFirstChild - 1, firstChild!.size);
childParentData.layoutOffset = gridGeometry.scrollOffset;
childParentData.crossAxisOffset = gridGeometry.crossAxisOffset;
// We only need to correct if the leading child actually has a
// paint extent.
if (firstChildScrollOffset < -precisionErrorTolerance) {
geometry = SliverGeometry(
scrollOffsetCorrection: -firstChildScrollOffset,
);
return;
}
indexOfFirstChild = indexOf(firstChild!);
}
}
// At this point, earliestUsefulChild is the first child, and is a child
// whose scrollOffset is at or before the scrollOffset, and
// leadingChildWithLayout and trailingChildWithLayout are either null or
// cover a range of render boxes that we have laid out with the first being
// the same as earliestUsefulChild and the last being either at or after the
// scroll offset.
assert(earliestUsefulChild == firstChild);
assert(childScrollOffset(earliestUsefulChild!)! <= scrollOffset);
// Make sure we've laid out at least one child.
if (leadingChildWithLayout == null) {
final int index = indexOf(earliestUsefulChild!);
SliverGridGeometry gridGeometry = layout.getGeometryForChildIndex(index);
earliestUsefulChild.layout(
gridGeometry.getBoxConstraints(constraints),
parentUsesSize: true,
);
leadingChildWithLayout = earliestUsefulChild;
trailingChildWithLayout = earliestUsefulChild;
gridGeometry =
layout.updateGeometryForChildIndex(index, earliestUsefulChild.size);
final SliverGridParentData childParentData =
earliestUsefulChild.parentData! as SliverGridParentData;
childParentData.layoutOffset = gridGeometry.scrollOffset;
childParentData.crossAxisOffset = gridGeometry.crossAxisOffset;
}
// Here, earliestUsefulChild is still the first child, it's got a
// scrollOffset that is at or before our actual scrollOffset, and it has
// been laid out, and is in fact our leadingChildWithLayout. It's possible
// that some children beyond that one have also been laid out.
bool inLayoutRange = true;
RenderBox? child = earliestUsefulChild;
int index = indexOf(child!);
double endScrollOffset = childScrollOffset(child)! + paintExtentOf(child);
bool advance() {
// returns true if we advanced, false if we have no more children
// This function is used in two different places below, to avoid code duplication.
late SliverGridGeometry gridGeometry;
assert(child != null);
if (child == trailingChildWithLayout) {
inLayoutRange = false;
}
child = childAfter(child!);
if (child == null) {
inLayoutRange = false;
}
index += 1;
if (!inLayoutRange) {
if (child == null || indexOf(child!) != index) {
// We are missing a child. Insert it (and lay it out) if possible.
gridGeometry = layout
.getGeometryForChildIndex(indexOf(trailingChildWithLayout!) + 1);
child = insertAndLayoutChild(
gridGeometry.getBoxConstraints(constraints),
after: trailingChildWithLayout,
parentUsesSize: true,
);
if (child == null) {
// We have run out of children.
return false;
}
} else {
// Lay out the child.
assert(indexOf(child!) == index);
gridGeometry = layout.getGeometryForChildIndex(index);
child!.layout(
gridGeometry.getBoxConstraints(constraints),
parentUsesSize: true,
);
}
trailingChildWithLayout = child;
}
assert(child != null);
final SliverGridParentData childParentData =
child!.parentData! as SliverGridParentData;
gridGeometry = layout.updateGeometryForChildIndex(index, child!.size);
childParentData.layoutOffset = gridGeometry.scrollOffset;
childParentData.crossAxisOffset = gridGeometry.crossAxisOffset;
assert(childParentData.index == index);
// The current child may not extend past a previously laid out child.
endScrollOffset = math.max(
endScrollOffset,
childScrollOffset(child!)! + paintExtentOf(child!),
);
return true;
}
// Find the first child that ends after the scroll offset.
while (endScrollOffset < scrollOffset) {
leadingGarbage += 1;
if (!advance()) {
assert(leadingGarbage == childCount);
assert(child == null);
// we want to make sure we keep the last child around so we know the end
// scroll offset
collectGarbage(leadingGarbage - 1, 0);
assert(firstChild == lastChild);
final double extent =
childScrollOffset(lastChild!)! + paintExtentOf(lastChild!);
geometry = SliverGeometry(
scrollExtent: extent,
maxPaintExtent: extent,
);
return;
}
}
// Now find the first child that ends after our end.
while (endScrollOffset < targetEndScrollOffset ||
!layout.reachedTargetScrollOffset(targetEndScrollOffset)) {
if (!advance()) {
reachedEnd = true;
break;
}
}
// Finally count up all the remaining children and label them as garbage.
if (child != null) {
child = childAfter(child!);
while (child != null) {
trailingGarbage += 1;
child = childAfter(child!);
}
}
// At this point everything should be good to go, we just have to clean up
// the garbage and report the geometry.
// We only collect trailing garbage because
//
// 1 - dynamic tile placement is dependent on the preceding tile,
// potentially, the SliverGridLayout could cache the placement of each
// tile to refer back to, but that would mean tiles could not change in
// size or be added/removed without having to recompute the whole layout.
//
// 2 - Currently, Flutter only supports collecting garbage in sequential
// order. Dynamic layout patterns can break this assumption. In order to
// truly collect garbage efficiently, support for non-sequential garbage
// collection is necessary.
// TODO(all): https://github.com/flutter/flutter/issues/112234
collectGarbage(0, trailingGarbage);
assert(debugAssertChildListIsNonEmptyAndContiguous());
final double estimatedMaxScrollOffset;
if (reachedEnd) {
estimatedMaxScrollOffset = endScrollOffset;
} else {
estimatedMaxScrollOffset = childManager.estimateMaxScrollOffset(
constraints,
firstIndex: indexOf(firstChild!),
lastIndex: indexOf(lastChild!),
leadingScrollOffset: childScrollOffset(firstChild!),
trailingScrollOffset: endScrollOffset,
);
assert(estimatedMaxScrollOffset >=
endScrollOffset - childScrollOffset(firstChild!)!);
}
final double paintExtent = calculatePaintOffset(
constraints,
from: childScrollOffset(firstChild!)!,
to: endScrollOffset,
);
final double cacheExtent = calculateCacheOffset(
constraints,
from: childScrollOffset(firstChild!)!,
to: endScrollOffset,
);
final double targetEndScrollOffsetForPaint =
constraints.scrollOffset + constraints.remainingPaintExtent;
geometry = SliverGeometry(
scrollExtent: estimatedMaxScrollOffset,
paintExtent: paintExtent,
cacheExtent: cacheExtent,
maxPaintExtent: estimatedMaxScrollOffset,
// Conservative to avoid flickering away the clip during scroll.
hasVisualOverflow: endScrollOffset > targetEndScrollOffsetForPaint ||
constraints.scrollOffset > 0.0,
);
// We may have started the layout while scrolled to the end, which would not
// expose a new child.
if (estimatedMaxScrollOffset == endScrollOffset) {
childManager.setDidUnderflow(true);
}
childManager.didFinishLayout();
}
}