1/* 2 * Copyright 2018 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 */ 16package androidx.recyclerview.widget; 17 18import android.view.View; 19 20import androidx.annotation.Nullable; 21import androidx.core.os.TraceCompat; 22 23import java.util.ArrayList; 24import java.util.Arrays; 25import java.util.Collections; 26import java.util.Comparator; 27import java.util.concurrent.TimeUnit; 28 29final class GapWorker implements Runnable { 30 31 static final ThreadLocal<GapWorker> sGapWorker = new ThreadLocal<>(); 32 33 ArrayList<RecyclerView> mRecyclerViews = new ArrayList<>(); 34 long mPostTimeNs; 35 long mFrameIntervalNs; 36 37 static class Task { 38 public boolean immediate; 39 public int viewVelocity; 40 public int distanceToItem; 41 public RecyclerView view; 42 public int position; 43 44 public void clear() { 45 immediate = false; 46 viewVelocity = 0; 47 distanceToItem = 0; 48 view = null; 49 position = 0; 50 } 51 } 52 53 /** 54 * Temporary storage for prefetch Tasks that execute in {@link #prefetch(long)}. Task objects 55 * are pooled in the ArrayList, and never removed to avoid allocations, but always cleared 56 * in between calls. 57 */ 58 private ArrayList<Task> mTasks = new ArrayList<>(); 59 60 /** 61 * Prefetch information associated with a specific RecyclerView. 62 */ 63 static class LayoutPrefetchRegistryImpl 64 implements RecyclerView.LayoutManager.LayoutPrefetchRegistry { 65 int mPrefetchDx; 66 int mPrefetchDy; 67 int[] mPrefetchArray; 68 69 int mCount; 70 71 void setPrefetchVector(int dx, int dy) { 72 mPrefetchDx = dx; 73 mPrefetchDy = dy; 74 } 75 76 void collectPrefetchPositionsFromView(RecyclerView view, boolean nested) { 77 mCount = 0; 78 if (mPrefetchArray != null) { 79 Arrays.fill(mPrefetchArray, -1); 80 } 81 82 final RecyclerView.LayoutManager layout = view.mLayout; 83 if (view.mAdapter != null 84 && layout != null 85 && layout.isItemPrefetchEnabled()) { 86 if (nested) { 87 // nested prefetch, only if no adapter updates pending. Note: we don't query 88 // view.hasPendingAdapterUpdates(), as first layout may not have occurred 89 if (!view.mAdapterHelper.hasPendingUpdates()) { 90 layout.collectInitialPrefetchPositions(view.mAdapter.getItemCount(), this); 91 } 92 } else { 93 // momentum based prefetch, only if we trust current child/adapter state 94 if (!view.hasPendingAdapterUpdates()) { 95 layout.collectAdjacentPrefetchPositions(mPrefetchDx, mPrefetchDy, 96 view.mState, this); 97 } 98 } 99 100 if (mCount > layout.mPrefetchMaxCountObserved) { 101 layout.mPrefetchMaxCountObserved = mCount; 102 layout.mPrefetchMaxObservedInInitialPrefetch = nested; 103 view.mRecycler.updateViewCacheSize(); 104 } 105 } 106 } 107 108 @Override 109 public void addPosition(int layoutPosition, int pixelDistance) { 110 if (layoutPosition < 0) { 111 throw new IllegalArgumentException("Layout positions must be non-negative"); 112 } 113 114 if (pixelDistance < 0) { 115 throw new IllegalArgumentException("Pixel distance must be non-negative"); 116 } 117 118 // allocate or expand array as needed, doubling when needed 119 final int storagePosition = mCount * 2; 120 if (mPrefetchArray == null) { 121 mPrefetchArray = new int[4]; 122 Arrays.fill(mPrefetchArray, -1); 123 } else if (storagePosition >= mPrefetchArray.length) { 124 final int[] oldArray = mPrefetchArray; 125 mPrefetchArray = new int[storagePosition * 2]; 126 System.arraycopy(oldArray, 0, mPrefetchArray, 0, oldArray.length); 127 } 128 129 // add position 130 mPrefetchArray[storagePosition] = layoutPosition; 131 mPrefetchArray[storagePosition + 1] = pixelDistance; 132 133 mCount++; 134 } 135 136 boolean lastPrefetchIncludedPosition(int position) { 137 if (mPrefetchArray != null) { 138 final int count = mCount * 2; 139 for (int i = 0; i < count; i += 2) { 140 if (mPrefetchArray[i] == position) return true; 141 } 142 } 143 return false; 144 } 145 146 /** 147 * Called when prefetch indices are no longer valid for cache prioritization. 148 */ 149 void clearPrefetchPositions() { 150 if (mPrefetchArray != null) { 151 Arrays.fill(mPrefetchArray, -1); 152 } 153 mCount = 0; 154 } 155 } 156 157 public void add(RecyclerView recyclerView) { 158 if (RecyclerView.DEBUG && mRecyclerViews.contains(recyclerView)) { 159 throw new IllegalStateException("RecyclerView already present in worker list!"); 160 } 161 mRecyclerViews.add(recyclerView); 162 } 163 164 public void remove(RecyclerView recyclerView) { 165 boolean removeSuccess = mRecyclerViews.remove(recyclerView); 166 if (RecyclerView.DEBUG && !removeSuccess) { 167 throw new IllegalStateException("RecyclerView removal failed!"); 168 } 169 } 170 171 /** 172 * Schedule a prefetch immediately after the current traversal. 173 */ 174 void postFromTraversal(RecyclerView recyclerView, int prefetchDx, int prefetchDy) { 175 if (recyclerView.isAttachedToWindow()) { 176 if (RecyclerView.DEBUG && !mRecyclerViews.contains(recyclerView)) { 177 throw new IllegalStateException("attempting to post unregistered view!"); 178 } 179 if (mPostTimeNs == 0) { 180 mPostTimeNs = recyclerView.getNanoTime(); 181 recyclerView.post(this); 182 } 183 } 184 185 recyclerView.mPrefetchRegistry.setPrefetchVector(prefetchDx, prefetchDy); 186 } 187 188 static Comparator<Task> sTaskComparator = new Comparator<Task>() { 189 @Override 190 public int compare(Task lhs, Task rhs) { 191 // first, prioritize non-cleared tasks 192 if ((lhs.view == null) != (rhs.view == null)) { 193 return lhs.view == null ? 1 : -1; 194 } 195 196 // then prioritize immediate 197 if (lhs.immediate != rhs.immediate) { 198 return lhs.immediate ? -1 : 1; 199 } 200 201 // then prioritize _highest_ view velocity 202 int deltaViewVelocity = rhs.viewVelocity - lhs.viewVelocity; 203 if (deltaViewVelocity != 0) return deltaViewVelocity; 204 205 // then prioritize _lowest_ distance to item 206 int deltaDistanceToItem = lhs.distanceToItem - rhs.distanceToItem; 207 if (deltaDistanceToItem != 0) return deltaDistanceToItem; 208 209 return 0; 210 } 211 }; 212 213 private void buildTaskList() { 214 // Update PrefetchRegistry in each view 215 final int viewCount = mRecyclerViews.size(); 216 int totalTaskCount = 0; 217 for (int i = 0; i < viewCount; i++) { 218 RecyclerView view = mRecyclerViews.get(i); 219 if (view.getWindowVisibility() == View.VISIBLE) { 220 view.mPrefetchRegistry.collectPrefetchPositionsFromView(view, false); 221 totalTaskCount += view.mPrefetchRegistry.mCount; 222 } 223 } 224 225 // Populate task list from prefetch data... 226 mTasks.ensureCapacity(totalTaskCount); 227 int totalTaskIndex = 0; 228 for (int i = 0; i < viewCount; i++) { 229 RecyclerView view = mRecyclerViews.get(i); 230 if (view.getWindowVisibility() != View.VISIBLE) { 231 // Invisible view, don't bother prefetching 232 continue; 233 } 234 235 LayoutPrefetchRegistryImpl prefetchRegistry = view.mPrefetchRegistry; 236 final int viewVelocity = Math.abs(prefetchRegistry.mPrefetchDx) 237 + Math.abs(prefetchRegistry.mPrefetchDy); 238 for (int j = 0; j < prefetchRegistry.mCount * 2; j += 2) { 239 final Task task; 240 if (totalTaskIndex >= mTasks.size()) { 241 task = new Task(); 242 mTasks.add(task); 243 } else { 244 task = mTasks.get(totalTaskIndex); 245 } 246 final int distanceToItem = prefetchRegistry.mPrefetchArray[j + 1]; 247 248 task.immediate = distanceToItem <= viewVelocity; 249 task.viewVelocity = viewVelocity; 250 task.distanceToItem = distanceToItem; 251 task.view = view; 252 task.position = prefetchRegistry.mPrefetchArray[j]; 253 254 totalTaskIndex++; 255 } 256 } 257 258 // ... and priority sort 259 Collections.sort(mTasks, sTaskComparator); 260 } 261 262 static boolean isPrefetchPositionAttached(RecyclerView view, int position) { 263 final int childCount = view.mChildHelper.getUnfilteredChildCount(); 264 for (int i = 0; i < childCount; i++) { 265 View attachedView = view.mChildHelper.getUnfilteredChildAt(i); 266 RecyclerView.ViewHolder holder = RecyclerView.getChildViewHolderInt(attachedView); 267 // Note: can use mPosition here because adapter doesn't have pending updates 268 if (holder.mPosition == position && !holder.isInvalid()) { 269 return true; 270 } 271 } 272 return false; 273 } 274 275 private RecyclerView.ViewHolder prefetchPositionWithDeadline(RecyclerView view, 276 int position, long deadlineNs) { 277 if (isPrefetchPositionAttached(view, position)) { 278 // don't attempt to prefetch attached views 279 return null; 280 } 281 282 RecyclerView.Recycler recycler = view.mRecycler; 283 RecyclerView.ViewHolder holder; 284 try { 285 view.onEnterLayoutOrScroll(); 286 holder = recycler.tryGetViewHolderForPositionByDeadline( 287 position, false, deadlineNs); 288 289 if (holder != null) { 290 if (holder.isBound() && !holder.isInvalid()) { 291 // Only give the view a chance to go into the cache if binding succeeded 292 // Note that we must use public method, since item may need cleanup 293 recycler.recycleView(holder.itemView); 294 } else { 295 // Didn't bind, so we can't cache the view, but it will stay in the pool until 296 // next prefetch/traversal. If a View fails to bind, it means we didn't have 297 // enough time prior to the deadline (and won't for other instances of this 298 // type, during this GapWorker prefetch pass). 299 recycler.addViewHolderToRecycledViewPool(holder, false); 300 } 301 } 302 } finally { 303 view.onExitLayoutOrScroll(false); 304 } 305 return holder; 306 } 307 308 private void prefetchInnerRecyclerViewWithDeadline(@Nullable RecyclerView innerView, 309 long deadlineNs) { 310 if (innerView == null) { 311 return; 312 } 313 314 if (innerView.mDataSetHasChangedAfterLayout 315 && innerView.mChildHelper.getUnfilteredChildCount() != 0) { 316 // RecyclerView has new data, but old attached views. Clear everything, so that 317 // we can prefetch without partially stale data. 318 innerView.removeAndRecycleViews(); 319 } 320 321 // do nested prefetch! 322 final LayoutPrefetchRegistryImpl innerPrefetchRegistry = innerView.mPrefetchRegistry; 323 innerPrefetchRegistry.collectPrefetchPositionsFromView(innerView, true); 324 325 if (innerPrefetchRegistry.mCount != 0) { 326 try { 327 TraceCompat.beginSection(RecyclerView.TRACE_NESTED_PREFETCH_TAG); 328 innerView.mState.prepareForNestedPrefetch(innerView.mAdapter); 329 for (int i = 0; i < innerPrefetchRegistry.mCount * 2; i += 2) { 330 // Note that we ignore immediate flag for inner items because 331 // we have lower confidence they're needed next frame. 332 final int innerPosition = innerPrefetchRegistry.mPrefetchArray[i]; 333 prefetchPositionWithDeadline(innerView, innerPosition, deadlineNs); 334 } 335 } finally { 336 TraceCompat.endSection(); 337 } 338 } 339 } 340 341 private void flushTaskWithDeadline(Task task, long deadlineNs) { 342 long taskDeadlineNs = task.immediate ? RecyclerView.FOREVER_NS : deadlineNs; 343 RecyclerView.ViewHolder holder = prefetchPositionWithDeadline(task.view, 344 task.position, taskDeadlineNs); 345 if (holder != null 346 && holder.mNestedRecyclerView != null 347 && holder.isBound() 348 && !holder.isInvalid()) { 349 prefetchInnerRecyclerViewWithDeadline(holder.mNestedRecyclerView.get(), deadlineNs); 350 } 351 } 352 353 private void flushTasksWithDeadline(long deadlineNs) { 354 for (int i = 0; i < mTasks.size(); i++) { 355 final Task task = mTasks.get(i); 356 if (task.view == null) { 357 break; // done with populated tasks 358 } 359 flushTaskWithDeadline(task, deadlineNs); 360 task.clear(); 361 } 362 } 363 364 void prefetch(long deadlineNs) { 365 buildTaskList(); 366 flushTasksWithDeadline(deadlineNs); 367 } 368 369 @Override 370 public void run() { 371 try { 372 TraceCompat.beginSection(RecyclerView.TRACE_PREFETCH_TAG); 373 374 if (mRecyclerViews.isEmpty()) { 375 // abort - no work to do 376 return; 377 } 378 379 // Query most recent vsync so we can predict next one. Note that drawing time not yet 380 // valid in animation/input callbacks, so query it here to be safe. 381 final int size = mRecyclerViews.size(); 382 long latestFrameVsyncMs = 0; 383 for (int i = 0; i < size; i++) { 384 RecyclerView view = mRecyclerViews.get(i); 385 if (view.getWindowVisibility() == View.VISIBLE) { 386 latestFrameVsyncMs = Math.max(view.getDrawingTime(), latestFrameVsyncMs); 387 } 388 } 389 390 if (latestFrameVsyncMs == 0) { 391 // abort - either no views visible, or couldn't get last vsync for estimating next 392 return; 393 } 394 395 long nextFrameNs = TimeUnit.MILLISECONDS.toNanos(latestFrameVsyncMs) + mFrameIntervalNs; 396 397 prefetch(nextFrameNs); 398 399 // TODO: consider rescheduling self, if there's more work to do 400 } finally { 401 mPostTimeNs = 0; 402 TraceCompat.endSection(); 403 } 404 } 405} 406