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