1// Copyright 2014 The Flutter Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5/// @docImport 'sliver_fixed_extent_list.dart';
6/// @docImport 'sliver_grid.dart';
7library;
8
9import 'package:flutter/foundation.dart';
10
11import 'box.dart';
12import 'sliver.dart';
13import 'sliver_multi_box_adaptor.dart';
14
15/// A sliver that places multiple box children in a linear array along the main
16/// axis.
17///
18/// Each child is forced to have the [SliverConstraints.crossAxisExtent] in the
19/// cross axis but determines its own main axis extent.
20///
21/// [RenderSliverList] determines its scroll offset by "dead reckoning" because
22/// children outside the visible part of the sliver are not materialized, which
23/// means [RenderSliverList] cannot learn their main axis extent. Instead, newly
24/// materialized children are placed adjacent to existing children. If this dead
25/// reckoning results in a logical inconsistency (e.g., attempting to place the
26/// zeroth child at a scroll offset other than zero), the [RenderSliverList]
27/// generates a [SliverGeometry.scrollOffsetCorrection] to restore consistency.
28///
29/// If the children have a fixed extent in the main axis, consider using
30/// [RenderSliverFixedExtentList] rather than [RenderSliverList] because
31/// [RenderSliverFixedExtentList] does not need to perform layout on its
32/// children to obtain their extent in the main axis and is therefore more
33/// efficient.
34///
35/// See also:
36///
37/// * [RenderSliverFixedExtentList], which is more efficient for children with
38/// the same extent in the main axis.
39/// * [RenderSliverGrid], which places its children in arbitrary positions.
40class RenderSliverList extends RenderSliverMultiBoxAdaptor {
41 /// Creates a sliver that places multiple box children in a linear array along
42 /// the main axis.
43 RenderSliverList({
44 required super.childManager,
45 });
46
47 @override
48 void performLayout() {
49 final SliverConstraints constraints = this.constraints;
50 childManager.didStartLayout();
51 childManager.setDidUnderflow(false);
52
53 final double scrollOffset = constraints.scrollOffset + constraints.cacheOrigin;
54 assert(scrollOffset >= 0.0);
55 final double remainingExtent = constraints.remainingCacheExtent;
56 assert(remainingExtent >= 0.0);
57 final double targetEndScrollOffset = scrollOffset + remainingExtent;
58 final BoxConstraints childConstraints = constraints.asBoxConstraints();
59 int leadingGarbage = 0;
60 int trailingGarbage = 0;
61 bool reachedEnd = false;
62
63 // This algorithm in principle is straight-forward: find the first child
64 // that overlaps the given scrollOffset, creating more children at the top
65 // of the list if necessary, then walk down the list updating and laying out
66 // each child and adding more at the end if necessary until we have enough
67 // children to cover the entire viewport.
68 //
69 // It is complicated by one minor issue, which is that any time you update
70 // or create a child, it's possible that the some of the children that
71 // haven't yet been laid out will be removed, leaving the list in an
72 // inconsistent state, and requiring that missing nodes be recreated.
73 //
74 // To keep this mess tractable, this algorithm starts from what is currently
75 // the first child, if any, and then walks up and/or down from there, so
76 // that the nodes that might get removed are always at the edges of what has
77 // already been laid out.
78
79 // Make sure we have at least one child to start from.
80 if (firstChild == null) {
81 if (!addInitialChild()) {
82 // There are no children.
83 geometry = SliverGeometry.zero;
84 childManager.didFinishLayout();
85 return;
86 }
87 }
88
89 // We have at least one child.
90
91 // These variables track the range of children that we have laid out. Within
92 // this range, the children have consecutive indices. Outside this range,
93 // it's possible for a child to get removed without notice.
94 RenderBox? leadingChildWithLayout, trailingChildWithLayout;
95
96 RenderBox? earliestUsefulChild = firstChild;
97
98 // A firstChild with null layout offset is likely a result of children
99 // reordering.
100 //
101 // We rely on firstChild to have accurate layout offset. In the case of null
102 // layout offset, we have to find the first child that has valid layout
103 // offset.
104 if (childScrollOffset(firstChild!) == null) {
105 int leadingChildrenWithoutLayoutOffset = 0;
106 while (earliestUsefulChild != null && childScrollOffset(earliestUsefulChild) == null) {
107 earliestUsefulChild = childAfter(earliestUsefulChild);
108 leadingChildrenWithoutLayoutOffset += 1;
109 }
110 // We should be able to destroy children with null layout offset safely,
111 // because they are likely outside of viewport
112 collectGarbage(leadingChildrenWithoutLayoutOffset, 0);
113 // If can not find a valid layout offset, start from the initial child.
114 if (firstChild == null) {
115 if (!addInitialChild()) {
116 // There are no children.
117 geometry = SliverGeometry.zero;
118 childManager.didFinishLayout();
119 return;
120 }
121 }
122 }
123
124 // Find the last child that is at or before the scrollOffset.
125 earliestUsefulChild = firstChild;
126 for (double earliestScrollOffset = childScrollOffset(earliestUsefulChild!)!;
127 earliestScrollOffset > scrollOffset;
128 earliestScrollOffset = childScrollOffset(earliestUsefulChild)!) {
129 // We have to add children before the earliestUsefulChild.
130 earliestUsefulChild = insertAndLayoutLeadingChild(childConstraints, parentUsesSize: true);
131 if (earliestUsefulChild == null) {
132 final SliverMultiBoxAdaptorParentData childParentData = firstChild!.parentData! as SliverMultiBoxAdaptorParentData;
133 childParentData.layoutOffset = 0.0;
134
135 if (scrollOffset == 0.0) {
136 // insertAndLayoutLeadingChild only lays out the children before
137 // firstChild. In this case, nothing has been laid out. We have
138 // to lay out firstChild manually.
139 firstChild!.layout(childConstraints, parentUsesSize: true);
140 earliestUsefulChild = firstChild;
141 leadingChildWithLayout = earliestUsefulChild;
142 trailingChildWithLayout ??= earliestUsefulChild;
143 break;
144 } else {
145 // We ran out of children before reaching the scroll offset.
146 // We must inform our parent that this sliver cannot fulfill
147 // its contract and that we need a scroll offset correction.
148 geometry = SliverGeometry(
149 scrollOffsetCorrection: -scrollOffset,
150 );
151 return;
152 }
153 }
154
155 final double firstChildScrollOffset = earliestScrollOffset - paintExtentOf(firstChild!);
156 // firstChildScrollOffset may contain double precision error
157 if (firstChildScrollOffset < -precisionErrorTolerance) {
158 // Let's assume there is no child before the first child. We will
159 // correct it on the next layout if it is not.
160 geometry = SliverGeometry(
161 scrollOffsetCorrection: -firstChildScrollOffset,
162 );
163 final SliverMultiBoxAdaptorParentData childParentData = firstChild!.parentData! as SliverMultiBoxAdaptorParentData;
164 childParentData.layoutOffset = 0.0;
165 return;
166 }
167
168 final SliverMultiBoxAdaptorParentData childParentData = earliestUsefulChild.parentData! as SliverMultiBoxAdaptorParentData;
169 childParentData.layoutOffset = firstChildScrollOffset;
170 assert(earliestUsefulChild == firstChild);
171 leadingChildWithLayout = earliestUsefulChild;
172 trailingChildWithLayout ??= earliestUsefulChild;
173 }
174
175 assert(childScrollOffset(firstChild!)! > -precisionErrorTolerance);
176
177 // If the scroll offset is at zero, we should make sure we are
178 // actually at the beginning of the list.
179 if (scrollOffset < precisionErrorTolerance) {
180 // We iterate from the firstChild in case the leading child has a 0 paint
181 // extent.
182 while (indexOf(firstChild!) > 0) {
183 final double earliestScrollOffset = childScrollOffset(firstChild!)!;
184 // We correct one child at a time. If there are more children before
185 // the earliestUsefulChild, we will correct it once the scroll offset
186 // reaches zero again.
187 earliestUsefulChild = insertAndLayoutLeadingChild(childConstraints, parentUsesSize: true);
188 assert(earliestUsefulChild != null);
189 final double firstChildScrollOffset = earliestScrollOffset - paintExtentOf(firstChild!);
190 final SliverMultiBoxAdaptorParentData childParentData = firstChild!.parentData! as SliverMultiBoxAdaptorParentData;
191 childParentData.layoutOffset = 0.0;
192 // We only need to correct if the leading child actually has a
193 // paint extent.
194 if (firstChildScrollOffset < -precisionErrorTolerance) {
195 geometry = SliverGeometry(
196 scrollOffsetCorrection: -firstChildScrollOffset,
197 );
198 return;
199 }
200 }
201 }
202
203 // At this point, earliestUsefulChild is the first child, and is a child
204 // whose scrollOffset is at or before the scrollOffset, and
205 // leadingChildWithLayout and trailingChildWithLayout are either null or
206 // cover a range of render boxes that we have laid out with the first being
207 // the same as earliestUsefulChild and the last being either at or after the
208 // scroll offset.
209
210 assert(earliestUsefulChild == firstChild);
211 assert(childScrollOffset(earliestUsefulChild!)! <= scrollOffset);
212
213 // Make sure we've laid out at least one child.
214 if (leadingChildWithLayout == null) {
215 earliestUsefulChild!.layout(childConstraints, parentUsesSize: true);
216 leadingChildWithLayout = earliestUsefulChild;
217 trailingChildWithLayout = earliestUsefulChild;
218 }
219
220 // Here, earliestUsefulChild is still the first child, it's got a
221 // scrollOffset that is at or before our actual scrollOffset, and it has
222 // been laid out, and is in fact our leadingChildWithLayout. It's possible
223 // that some children beyond that one have also been laid out.
224
225 bool inLayoutRange = true;
226 RenderBox? child = earliestUsefulChild;
227 int index = indexOf(child!);
228 double endScrollOffset = childScrollOffset(child)! + paintExtentOf(child);
229 bool advance() { // returns true if we advanced, false if we have no more children
230 // This function is used in two different places below, to avoid code duplication.
231 assert(child != null);
232 if (child == trailingChildWithLayout) {
233 inLayoutRange = false;
234 }
235 child = childAfter(child!);
236 if (child == null) {
237 inLayoutRange = false;
238 }
239 index += 1;
240 if (!inLayoutRange) {
241 if (child == null || indexOf(child!) != index) {
242 // We are missing a child. Insert it (and lay it out) if possible.
243 child = insertAndLayoutChild(childConstraints,
244 after: trailingChildWithLayout,
245 parentUsesSize: true,
246 );
247 if (child == null) {
248 // We have run out of children.
249 return false;
250 }
251 } else {
252 // Lay out the child.
253 child!.layout(childConstraints, parentUsesSize: true);
254 }
255 trailingChildWithLayout = child;
256 }
257 assert(child != null);
258 final SliverMultiBoxAdaptorParentData childParentData = child!.parentData! as SliverMultiBoxAdaptorParentData;
259 childParentData.layoutOffset = endScrollOffset;
260 assert(childParentData.index == index);
261 endScrollOffset = childScrollOffset(child!)! + paintExtentOf(child!);
262 return true;
263 }
264
265 // Find the first child that ends after the scroll offset.
266 while (endScrollOffset < scrollOffset) {
267 leadingGarbage += 1;
268 if (!advance()) {
269 assert(leadingGarbage == childCount);
270 assert(child == null);
271 // we want to make sure we keep the last child around so we know the end scroll offset
272 collectGarbage(leadingGarbage - 1, 0);
273 assert(firstChild == lastChild);
274 final double extent = childScrollOffset(lastChild!)! + paintExtentOf(lastChild!);
275 geometry = SliverGeometry(
276 scrollExtent: extent,
277 maxPaintExtent: extent,
278 );
279 return;
280 }
281 }
282
283 // Now find the first child that ends after our end.
284 while (endScrollOffset < targetEndScrollOffset) {
285 if (!advance()) {
286 reachedEnd = true;
287 break;
288 }
289 }
290
291 // Finally count up all the remaining children and label them as garbage.
292 if (child != null) {
293 child = childAfter(child!);
294 while (child != null) {
295 trailingGarbage += 1;
296 child = childAfter(child!);
297 }
298 }
299
300 // At this point everything should be good to go, we just have to clean up
301 // the garbage and report the geometry.
302
303 collectGarbage(leadingGarbage, trailingGarbage);
304
305 assert(debugAssertChildListIsNonEmptyAndContiguous());
306 final double estimatedMaxScrollOffset;
307 if (reachedEnd) {
308 estimatedMaxScrollOffset = endScrollOffset;
309 } else {
310 estimatedMaxScrollOffset = childManager.estimateMaxScrollOffset(
311 constraints,
312 firstIndex: indexOf(firstChild!),
313 lastIndex: indexOf(lastChild!),
314 leadingScrollOffset: childScrollOffset(firstChild!),
315 trailingScrollOffset: endScrollOffset,
316 );
317 assert(estimatedMaxScrollOffset >= endScrollOffset - childScrollOffset(firstChild!)!);
318 }
319 final double paintExtent = calculatePaintOffset(
320 constraints,
321 from: childScrollOffset(firstChild!)!,
322 to: endScrollOffset,
323 );
324 final double cacheExtent = calculateCacheOffset(
325 constraints,
326 from: childScrollOffset(firstChild!)!,
327 to: endScrollOffset,
328 );
329 final double targetEndScrollOffsetForPaint = constraints.scrollOffset + constraints.remainingPaintExtent;
330 geometry = SliverGeometry(
331 scrollExtent: estimatedMaxScrollOffset,
332 paintExtent: paintExtent,
333 cacheExtent: cacheExtent,
334 maxPaintExtent: estimatedMaxScrollOffset,
335 // Conservative to avoid flickering away the clip during scroll.
336 hasVisualOverflow: endScrollOffset > targetEndScrollOffsetForPaint || constraints.scrollOffset > 0.0,
337 );
338
339 // We may have started the layout while scrolled to the end, which would not
340 // expose a new child.
341 if (estimatedMaxScrollOffset == endScrollOffset) {
342 childManager.setDidUnderflow(true);
343 }
344 childManager.didFinishLayout();
345 }
346}
347