1 /* <lambda>null2 * Copyright 2025 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package androidx.compose.foundation.lazy.layout 18 19 import androidx.collection.mutableIntIntMapOf 20 import androidx.collection.mutableIntObjectMapOf 21 import androidx.collection.mutableIntSetOf 22 import androidx.compose.foundation.ExperimentalFoundationApi 23 import androidx.compose.foundation.lazy.layout.LazyLayoutPrefetchState.PrefetchHandle 24 import androidx.compose.ui.unit.Density 25 import androidx.compose.ui.util.fastForEach 26 import androidx.compose.ui.util.traceValue 27 import kotlin.math.absoluteValue 28 import kotlin.math.roundToInt 29 import kotlin.math.sign 30 31 /** Implements the logic for [LazyLayoutCacheWindow] prefetching and item preservation. */ 32 @OptIn(ExperimentalFoundationApi::class) 33 internal abstract class CacheWindowLogic( 34 private val cacheWindow: LazyLayoutCacheWindow, 35 ) { 36 37 /** Handles for prefetched items in the current forward window. */ 38 private val prefetchWindowHandles = mutableIntObjectMapOf<List<PrefetchHandle>>() 39 40 private val indicesToRemove = mutableIntSetOf() 41 /** 42 * Cache for items sizes in the current window. Holds sizes for both visible and non-visible 43 * items 44 */ 45 private val windowCache = mutableIntIntMapOf() 46 private var previousPassDelta = 0f 47 private var hasUpdatedVisibleItemsOnce = false 48 49 /** 50 * Indices for the start and end of the cache window. The items between 51 * [prefetchWindowStartLine] and [prefetchWindowEndLine] can be: 52 * 1) Visible. 53 * 2) Cached. 54 * 3) Scheduled for prefetching. 55 * 4) Not scheduled yet. 56 */ 57 internal var prefetchWindowStartLine = Int.MAX_VALUE 58 private set 59 60 internal var prefetchWindowEndLine = Int.MIN_VALUE 61 private set 62 63 /** 64 * Keeps track of the "extra" space used. Extra space starts by being the amount of space 65 * occupied by the first and last visible items outside of the viewport, that is, how much 66 * they're "peeking" out of view. These values will be updated as we fill the cache window. 67 */ 68 private var prefetchWindowStartExtraSpace = 0 69 private var prefetchWindowEndExtraSpace = 0 70 71 /** Signals that we should run the window refilling loop from start. */ 72 private var shouldRefillWindow = false 73 74 /** Keep the latest item count where it can be used more easily. */ 75 private var itemsCount = 0 76 77 fun CacheWindowScope.onScroll(delta: Float) { 78 traceWindowInfo() 79 fillCacheWindowBackward(delta) 80 fillCacheWindowForward(delta) 81 previousPassDelta = delta 82 traceWindowInfo() 83 } 84 85 private fun traceWindowInfo() { 86 traceValue("prefetchWindowStartExtraSpace", prefetchWindowStartExtraSpace.toLong()) 87 traceValue("prefetchWindowEndExtraSpace", prefetchWindowEndExtraSpace.toLong()) 88 traceValue("prefetchWindowStartIndex", prefetchWindowStartLine.toLong()) 89 traceValue("prefetchWindowEndIndex", prefetchWindowEndLine.toLong()) 90 } 91 92 fun CacheWindowScope.onVisibleItemsUpdated() { 93 if (!hasUpdatedVisibleItemsOnce) { 94 val prefetchForwardWindow = 95 with(cacheWindow) { density?.calculateAheadWindow(mainAxisViewportSize) ?: 0 } 96 // we won't fill the window if we don't have a prefetch window 97 if (prefetchForwardWindow != 0) shouldRefillWindow = true 98 hasUpdatedVisibleItemsOnce = true 99 } 100 101 itemsCount = totalItemsCount 102 // If visible items changed, update cached information. Any items that were visible 103 // and became out of bounds will either count for the cache window or be cancelled/removed 104 // by [cancelOutOfBounds]. If any items changed sizes we re-trigger the window filling 105 // update. 106 if (hasVisibleItems) { 107 forEachVisibleItem { index, mainAxisSize -> cacheVisibleItemsInfo(index, mainAxisSize) } 108 if (shouldRefillWindow) { 109 fillCacheWindowForward(0.0f) 110 shouldRefillWindow = false 111 } 112 } else { 113 // if no visible items, it means the dataset is empty and we should reset the window. 114 // Next time visible items update we we re-start the window strategy. 115 resetStrategy() 116 } 117 } 118 119 fun hasValidBounds() = 120 prefetchWindowStartLine != Int.MAX_VALUE && prefetchWindowEndLine != Int.MIN_VALUE 121 122 private fun CacheWindowScope.fillCacheWindowBackward(delta: Float) { 123 if (hasVisibleItems) { 124 val viewport = mainAxisViewportSize 125 126 val keepAroundWindow = 127 with(cacheWindow) { density?.calculateBehindWindow(viewport) ?: 0 } 128 129 // save latest item count 130 itemsCount = totalItemsCount 131 132 onKeepAround( 133 visibleWindowStart = firstVisibleLineIndex, 134 visibleWindowEnd = lastVisibleLineIndex, 135 keepAroundWindow = keepAroundWindow, 136 scrollDelta = delta, 137 itemsCount = totalItemsCount, 138 mainAxisExtraSpaceStart = mainAxisExtraSpaceStart, 139 mainAxisExtraSpaceEnd = mainAxisExtraSpaceEnd, 140 ) 141 } 142 } 143 144 private fun CacheWindowScope.fillCacheWindowForward(delta: Float) { 145 if (hasVisibleItems) { 146 val viewport = mainAxisViewportSize 147 148 val prefetchForwardWindow = 149 with(cacheWindow) { density?.calculateAheadWindow(viewport) ?: 0 } 150 151 onPrefetchForward( 152 visibleWindowStart = firstVisibleLineIndex, 153 visibleWindowEnd = lastVisibleLineIndex, 154 prefetchForwardWindow = prefetchForwardWindow, 155 scrollDelta = delta, 156 mainAxisExtraSpaceStart = mainAxisExtraSpaceStart, 157 mainAxisExtraSpaceEnd = mainAxisExtraSpaceEnd 158 ) 159 } 160 } 161 162 fun resetStrategy() { 163 prefetchWindowStartLine = Int.MAX_VALUE 164 prefetchWindowEndLine = Int.MIN_VALUE 165 prefetchWindowStartExtraSpace = 0 166 prefetchWindowEndExtraSpace = 0 167 168 windowCache.clear() 169 prefetchWindowHandles.removeIf { _, value -> 170 value.fastForEach { it.cancel() } 171 true 172 } 173 } 174 175 /** 176 * Prefetch Forward Logic: Fill in the forward window with prefetched items from the previous 177 * measure pass. If the item is not prefetched yet, schedule a prefetching for it. Once a 178 * prefetch returns, we check if the window is filled and if not we schedule the next 179 * prefetching. 180 */ 181 private fun CacheWindowScope.onPrefetchForward( 182 visibleWindowStart: Int, 183 visibleWindowEnd: Int, 184 prefetchForwardWindow: Int, 185 mainAxisExtraSpaceEnd: Int, 186 mainAxisExtraSpaceStart: Int, 187 scrollDelta: Float 188 ) { 189 val changedScrollDirection = scrollDelta.sign != previousPassDelta.sign 190 191 if (scrollDelta <= 0.0f) { // scrolling forward, starting on last visible 192 if (changedScrollDirection || shouldRefillWindow) { 193 prefetchWindowEndExtraSpace = (prefetchForwardWindow - mainAxisExtraSpaceEnd) 194 prefetchWindowEndLine = visibleWindowEnd 195 } else { 196 prefetchWindowEndExtraSpace += scrollDelta.absoluteValue.roundToInt() 197 } 198 199 while (prefetchWindowEndExtraSpace > 0 && prefetchWindowEndLine < itemsCount) { 200 // If we get the same delta in the next frame, would we cover the extra space needed 201 // to actually need this item? If so, mark it as urgent 202 val isUrgent: Boolean = 203 if (prefetchWindowEndLine + 1 == visibleWindowEnd + 1) { 204 scrollDelta.absoluteValue >= mainAxisExtraSpaceEnd 205 } else { 206 false 207 } 208 209 // no more items available to fill prefetch window if this is null, break 210 val itemSize = 211 getItemSizeOrPrefetch(index = prefetchWindowEndLine + 1, isUrgent = isUrgent) 212 213 if (itemSize == InvalidItemSize) break 214 215 prefetchWindowEndLine++ 216 prefetchWindowEndExtraSpace -= itemSize 217 } 218 } else { // scrolling backwards, starting on first visible 219 220 if (changedScrollDirection || shouldRefillWindow) { 221 prefetchWindowStartExtraSpace = (prefetchForwardWindow - mainAxisExtraSpaceStart) 222 prefetchWindowStartLine = visibleWindowStart 223 } else { 224 prefetchWindowStartExtraSpace += scrollDelta.absoluteValue.roundToInt() 225 } 226 227 while (prefetchWindowStartExtraSpace > 0 && prefetchWindowStartLine > 0) { 228 // If we get the same delta in the next frame, would we cover the extra space needed 229 // to actually need this item? If so, mark it as urgent 230 val isUrgent: Boolean = 231 if (prefetchWindowStartLine - 1 == visibleWindowStart - 1) { 232 scrollDelta.absoluteValue >= mainAxisExtraSpaceStart 233 } else { 234 false 235 } 236 // no more items available to fill prefetch window if this is null, break 237 val itemSize = 238 getItemSizeOrPrefetch(index = prefetchWindowStartLine - 1, isUrgent = isUrgent) 239 if (itemSize == InvalidItemSize) break 240 prefetchWindowStartLine-- 241 prefetchWindowStartExtraSpace -= itemSize 242 } 243 } 244 } 245 246 /** 247 * Keep Around Logic: Keep around items were visible in the previous measure pass. This means 248 * that they will be present in [windowCache] along their size information. We loop through 249 * items starting in the last visible one and update [prefetchWindowStartExtraSpace] or 250 * [prefetchWindowEndExtraSpace] and also [prefetchWindowStartLine] or [prefetchWindowEndLine]. 251 * We never schedule a prefetch call for keep around items. 252 */ 253 private fun onKeepAround( 254 visibleWindowStart: Int, 255 visibleWindowEnd: Int, 256 mainAxisExtraSpaceEnd: Int, 257 mainAxisExtraSpaceStart: Int, 258 keepAroundWindow: Int, 259 scrollDelta: Float, 260 itemsCount: Int 261 ) { 262 263 if (scrollDelta <= 0.0f) { // scrolling forward, keep around from firstVisible 264 prefetchWindowStartExtraSpace = (keepAroundWindow - mainAxisExtraSpaceStart) 265 prefetchWindowStartLine = visibleWindowStart 266 while (prefetchWindowStartExtraSpace > 0 && prefetchWindowStartLine > 0) { 267 val item = 268 if (windowCache.containsKey(prefetchWindowStartLine - 1)) { 269 windowCache[prefetchWindowStartLine - 1] 270 } else { 271 break 272 } 273 274 prefetchWindowStartLine-- 275 prefetchWindowStartExtraSpace -= item 276 } 277 removeOutOfBoundsItems(0, prefetchWindowStartLine - 1) 278 } else { // scrolling backwards, keep around from last visible 279 prefetchWindowEndExtraSpace = (keepAroundWindow - mainAxisExtraSpaceEnd) 280 prefetchWindowEndLine = visibleWindowEnd 281 while (prefetchWindowEndExtraSpace > 0 && prefetchWindowEndLine < itemsCount) { 282 val item = 283 if (windowCache.containsKey(prefetchWindowEndLine + 1)) { 284 windowCache[prefetchWindowEndLine + 1] 285 } else { 286 break 287 } 288 prefetchWindowEndLine++ 289 prefetchWindowEndExtraSpace -= item 290 } 291 removeOutOfBoundsItems(prefetchWindowEndLine + 1, itemsCount - 1) 292 } 293 } 294 295 private fun CacheWindowScope.getItemSizeOrPrefetch(index: Int, isUrgent: Boolean): Int { 296 return if (windowCache.containsKey(index)) { 297 windowCache[index] 298 } else if (prefetchWindowHandles.containsKey(index)) { 299 // item is scheduled but didn't finish yet 300 if (isUrgent) prefetchWindowHandles[index]?.fastForEach { it.markAsUrgent() } 301 InvalidItemSize 302 } else { 303 // item is not scheduled 304 prefetchWindowHandles[index] = 305 schedulePrefetch(index) { prefetchedIndex, size -> 306 onItemPrefetched(prefetchedIndex, size) 307 } 308 if (isUrgent) prefetchWindowHandles[index]?.fastForEach { it.markAsUrgent() } 309 InvalidItemSize 310 } 311 } 312 313 /** Grows the window with measured items and prefetched items. */ 314 private fun cachePrefetchedItem(index: Int, size: Int) { 315 windowCache[index] = size 316 if (index > prefetchWindowEndLine) { 317 prefetchWindowEndLine = index 318 prefetchWindowEndExtraSpace -= size 319 } else if (index < prefetchWindowStartLine) { 320 prefetchWindowStartLine = index 321 prefetchWindowStartExtraSpace -= size 322 } 323 } 324 325 /** 326 * When caching visible items we need to check if the existing item changed sizes. If so, we 327 * will set [shouldRefillWindow] which will trigger a complete window filling and cancel any out 328 * of bounds requests. 329 */ 330 private fun cacheVisibleItemsInfo(index: Int, size: Int) { 331 if (windowCache.containsKey(index) && windowCache[index] != size) { 332 shouldRefillWindow = true 333 } 334 335 windowCache[index] = size 336 // We're caching a visible item, remove its handle since we won't need it anymore. 337 prefetchWindowStartLine = minOf(prefetchWindowStartLine, index) 338 prefetchWindowEndLine = maxOf(prefetchWindowEndLine, index) 339 prefetchWindowHandles.remove(index)?.fastForEach { it.cancel() } 340 } 341 342 /** Takes care of removing caches and canceling handles for items that we won't use anymore. */ 343 private fun removeOutOfBoundsItems(startLine: Int, endLine: Int) { 344 indicesToRemove.clear() 345 prefetchWindowHandles.forEachKey { if (it in startLine..endLine) indicesToRemove.add(it) } 346 347 windowCache.forEachKey { if (it in startLine..endLine) indicesToRemove.add(it) } 348 349 indicesToRemove.forEach { 350 prefetchWindowHandles.remove(it)?.fastForEach { it.cancel() } 351 windowCache.remove(it) 352 } 353 } 354 355 /** 356 * Item prefetching finished, we can cache its information and schedule the next prefetching if 357 * needed. 358 */ 359 private fun CacheWindowScope.onItemPrefetched(index: Int, itemSize: Int) { 360 cachePrefetchedItem(index, itemSize) 361 scheduleNextItemIfNeeded() 362 traceWindowInfo() 363 } 364 365 private fun CacheWindowScope.scheduleNextItemIfNeeded() { 366 var nextPrefetchableIndex: Int = -1 367 // if was scrolling forward 368 if (previousPassDelta.sign <= 0) { 369 if (prefetchWindowEndExtraSpace > 0) nextPrefetchableIndex = prefetchWindowEndLine + 1 370 } else if (previousPassDelta.sign > 0) { 371 if (prefetchWindowStartExtraSpace > 0) 372 nextPrefetchableIndex = prefetchWindowStartLine - 1 373 } 374 375 if (nextPrefetchableIndex in 0..itemsCount) { 376 prefetchWindowHandles[nextPrefetchableIndex] = 377 schedulePrefetch(nextPrefetchableIndex) { index, mainAxisSize -> 378 onItemPrefetched(index, mainAxisSize) 379 } 380 } 381 } 382 } 383 384 @OptIn(ExperimentalFoundationApi::class) 385 /** Bridge between LazyLayout and its implementation. */ 386 internal interface CacheWindowScope { 387 val totalItemsCount: Int 388 val visibleLineCount: Int 389 val hasVisibleItems: Boolean 390 val mainAxisExtraSpaceStart: Int 391 val mainAxisExtraSpaceEnd: Int 392 val firstVisibleLineIndex: Int 393 val lastVisibleLineIndex: Int 394 val mainAxisViewportSize: Int 395 val density: Density? 396 schedulePrefetchnull397 fun schedulePrefetch(lineIndex: Int, onItemPrefetched: (Int, Int) -> Unit): List<PrefetchHandle> 398 399 fun getVisibleItemSize(indexInVisibleLines: Int): Int 400 401 fun getVisibleItemLine(indexInVisibleLines: Int): Int 402 } 403 404 internal inline fun CacheWindowScope.forEachVisibleItem( 405 action: (itemIndex: Int, mainAxisSize: Int) -> Unit 406 ) { 407 repeat(visibleLineCount) { action(getVisibleItemLine(it), getVisibleItemSize(it)) } 408 } 409 410 private const val InvalidItemSize = -1 411