1 /* 2 * Copyright (C) 2019 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 com.android.systemui.statusbar.notification.collection; 18 19 import static com.android.internal.util.Preconditions.checkArgument; 20 import static com.android.internal.util.Preconditions.checkState; 21 import static com.android.systemui.statusbar.notification.collection.GroupEntry.ROOT_ENTRY; 22 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_BUILD_STARTED; 23 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_FINALIZE_FILTERING; 24 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_FINALIZING; 25 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_GROUPING; 26 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_GROUP_STABILIZING; 27 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_IDLE; 28 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_PRE_GROUP_FILTERING; 29 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_RESETTING; 30 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_SORTING; 31 import static com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState.STATE_TRANSFORMING; 32 33 import static java.util.Objects.requireNonNull; 34 35 import android.annotation.MainThread; 36 import android.annotation.Nullable; 37 import android.os.Trace; 38 import android.service.notification.StatusBarNotification; 39 import android.util.ArrayMap; 40 import android.util.ArraySet; 41 import android.util.Log; 42 43 import androidx.annotation.NonNull; 44 import androidx.annotation.VisibleForTesting; 45 46 import com.android.systemui.Dumpable; 47 import com.android.systemui.dagger.SysUISingleton; 48 import com.android.systemui.dump.DumpManager; 49 import com.android.systemui.statusbar.NotificationInteractionTracker; 50 import com.android.systemui.statusbar.notification.NotifPipelineFlags; 51 import com.android.systemui.statusbar.notification.collection.listbuilder.NotifSection; 52 import com.android.systemui.statusbar.notification.collection.listbuilder.OnBeforeFinalizeFilterListener; 53 import com.android.systemui.statusbar.notification.collection.listbuilder.OnBeforeRenderListListener; 54 import com.android.systemui.statusbar.notification.collection.listbuilder.OnBeforeSortListener; 55 import com.android.systemui.statusbar.notification.collection.listbuilder.OnBeforeTransformGroupsListener; 56 import com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState; 57 import com.android.systemui.statusbar.notification.collection.listbuilder.SemiStableSort; 58 import com.android.systemui.statusbar.notification.collection.listbuilder.SemiStableSort.StableOrder; 59 import com.android.systemui.statusbar.notification.collection.listbuilder.ShadeListBuilderHelper; 60 import com.android.systemui.statusbar.notification.collection.listbuilder.ShadeListBuilderLogger; 61 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.DefaultNotifStabilityManager; 62 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.Invalidator; 63 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.NotifComparator; 64 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.NotifFilter; 65 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.NotifPromoter; 66 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.NotifSectioner; 67 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.NotifStabilityManager; 68 import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.Pluggable; 69 import com.android.systemui.statusbar.notification.collection.notifcollection.CollectionReadyForBuildListener; 70 import com.android.systemui.statusbar.notification.stack.NotificationPriorityBucketKt; 71 import com.android.systemui.util.Assert; 72 import com.android.systemui.util.NamedListenerSet; 73 import com.android.systemui.util.time.SystemClock; 74 75 import java.io.PrintWriter; 76 import java.util.ArrayList; 77 import java.util.Collection; 78 import java.util.Collections; 79 import java.util.Comparator; 80 import java.util.Iterator; 81 import java.util.List; 82 import java.util.Map; 83 import java.util.Objects; 84 import java.util.Set; 85 86 import javax.inject.Inject; 87 88 /** 89 * The second half of {@link NotifPipeline}. Sits downstream of the NotifCollection and transforms 90 * its "notification set" into the "shade list", the filtered, grouped, and sorted list of 91 * notifications that are currently present in the notification shade. 92 */ 93 @MainThread 94 @SysUISingleton 95 public class ShadeListBuilder implements Dumpable, PipelineDumpable { 96 private final SystemClock mSystemClock; 97 private final ShadeListBuilderLogger mLogger; 98 private final NotificationInteractionTracker mInteractionTracker; 99 private final DumpManager mDumpManager; 100 // used exclusivly by ShadeListBuilder#notifySectionEntriesUpdated 101 // TODO replace temp with collection pool for readability 102 private final ArrayList<ListEntry> mTempSectionMembers = new ArrayList<>(); 103 private NotifPipelineFlags mFlags; 104 private final boolean mAlwaysLogList; 105 106 private List<ListEntry> mNotifList = new ArrayList<>(); 107 private List<ListEntry> mNewNotifList = new ArrayList<>(); 108 109 private final SemiStableSort mSemiStableSort = new SemiStableSort(); 110 private final StableOrder<ListEntry> mStableOrder = this::getStableOrderRank; 111 private final PipelineState mPipelineState = new PipelineState(); 112 private final Map<String, GroupEntry> mGroups = new ArrayMap<>(); 113 private Collection<NotificationEntry> mAllEntries = Collections.emptyList(); 114 @Nullable 115 private Collection<NotificationEntry> mPendingEntries = null; 116 private int mIterationCount = 0; 117 118 private final List<NotifFilter> mNotifPreGroupFilters = new ArrayList<>(); 119 private final List<NotifPromoter> mNotifPromoters = new ArrayList<>(); 120 private final List<NotifFilter> mNotifFinalizeFilters = new ArrayList<>(); 121 private final List<NotifComparator> mNotifComparators = new ArrayList<>(); 122 private final List<NotifSection> mNotifSections = new ArrayList<>(); 123 private NotifStabilityManager mNotifStabilityManager; 124 125 private final NamedListenerSet<OnBeforeTransformGroupsListener> 126 mOnBeforeTransformGroupsListeners = new NamedListenerSet<>(); 127 private final NamedListenerSet<OnBeforeSortListener> 128 mOnBeforeSortListeners = new NamedListenerSet<>(); 129 private final NamedListenerSet<OnBeforeFinalizeFilterListener> 130 mOnBeforeFinalizeFilterListeners = new NamedListenerSet<>(); 131 private final NamedListenerSet<OnBeforeRenderListListener> 132 mOnBeforeRenderListListeners = new NamedListenerSet<>(); 133 @Nullable private OnRenderListListener mOnRenderListListener; 134 135 private List<ListEntry> mReadOnlyNotifList = Collections.unmodifiableList(mNotifList); 136 private List<ListEntry> mReadOnlyNewNotifList = Collections.unmodifiableList(mNewNotifList); 137 private final NotifPipelineChoreographer mChoreographer; 138 139 private int mConsecutiveReentrantRebuilds = 0; 140 @VisibleForTesting public static final int MAX_CONSECUTIVE_REENTRANT_REBUILDS = 3; 141 142 @Inject ShadeListBuilder( DumpManager dumpManager, NotifPipelineChoreographer pipelineChoreographer, NotifPipelineFlags flags, NotificationInteractionTracker interactionTracker, ShadeListBuilderLogger logger, SystemClock systemClock )143 public ShadeListBuilder( 144 DumpManager dumpManager, 145 NotifPipelineChoreographer pipelineChoreographer, 146 NotifPipelineFlags flags, 147 NotificationInteractionTracker interactionTracker, 148 ShadeListBuilderLogger logger, 149 SystemClock systemClock 150 ) { 151 mSystemClock = systemClock; 152 mLogger = logger; 153 mFlags = flags; 154 mAlwaysLogList = flags.isDevLoggingEnabled(); 155 mInteractionTracker = interactionTracker; 156 mChoreographer = pipelineChoreographer; 157 mDumpManager = dumpManager; 158 setSectioners(Collections.emptyList()); 159 } 160 161 /** 162 * Attach the list builder to the NotifCollection. After this is called, it will start building 163 * the notif list in response to changes to the colletion. 164 */ attach(NotifCollection collection)165 public void attach(NotifCollection collection) { 166 Assert.isMainThread(); 167 mDumpManager.registerDumpable(TAG, this); 168 collection.addCollectionListener(mInteractionTracker); 169 collection.setBuildListener(mReadyForBuildListener); 170 mChoreographer.addOnEvalListener(this::buildList); 171 } 172 173 /** 174 * Registers the listener that's responsible for rendering the notif list to the screen. Called 175 * At the very end of pipeline execution, after all other listeners and pluggables have fired. 176 */ setOnRenderListListener(OnRenderListListener onRenderListListener)177 public void setOnRenderListListener(OnRenderListListener onRenderListListener) { 178 Assert.isMainThread(); 179 180 mPipelineState.requireState(STATE_IDLE); 181 mOnRenderListListener = onRenderListListener; 182 } 183 addOnBeforeTransformGroupsListener(OnBeforeTransformGroupsListener listener)184 void addOnBeforeTransformGroupsListener(OnBeforeTransformGroupsListener listener) { 185 Assert.isMainThread(); 186 187 mPipelineState.requireState(STATE_IDLE); 188 mOnBeforeTransformGroupsListeners.addIfAbsent(listener); 189 } 190 addOnBeforeSortListener(OnBeforeSortListener listener)191 void addOnBeforeSortListener(OnBeforeSortListener listener) { 192 Assert.isMainThread(); 193 194 mPipelineState.requireState(STATE_IDLE); 195 mOnBeforeSortListeners.addIfAbsent(listener); 196 } 197 addOnBeforeFinalizeFilterListener(OnBeforeFinalizeFilterListener listener)198 void addOnBeforeFinalizeFilterListener(OnBeforeFinalizeFilterListener listener) { 199 Assert.isMainThread(); 200 201 mPipelineState.requireState(STATE_IDLE); 202 mOnBeforeFinalizeFilterListeners.addIfAbsent(listener); 203 } 204 addOnBeforeRenderListListener(OnBeforeRenderListListener listener)205 void addOnBeforeRenderListListener(OnBeforeRenderListListener listener) { 206 Assert.isMainThread(); 207 208 mPipelineState.requireState(STATE_IDLE); 209 mOnBeforeRenderListListeners.addIfAbsent(listener); 210 } 211 addPreRenderInvalidator(Invalidator invalidator)212 void addPreRenderInvalidator(Invalidator invalidator) { 213 Assert.isMainThread(); 214 215 mPipelineState.requireState(STATE_IDLE); 216 invalidator.setInvalidationListener(this::onPreRenderInvalidated); 217 } 218 addPreGroupFilter(NotifFilter filter)219 void addPreGroupFilter(NotifFilter filter) { 220 Assert.isMainThread(); 221 mPipelineState.requireState(STATE_IDLE); 222 223 mNotifPreGroupFilters.add(filter); 224 filter.setInvalidationListener(this::onPreGroupFilterInvalidated); 225 } 226 addFinalizeFilter(NotifFilter filter)227 void addFinalizeFilter(NotifFilter filter) { 228 Assert.isMainThread(); 229 mPipelineState.requireState(STATE_IDLE); 230 231 mNotifFinalizeFilters.add(filter); 232 filter.setInvalidationListener(this::onFinalizeFilterInvalidated); 233 } 234 addPromoter(NotifPromoter promoter)235 void addPromoter(NotifPromoter promoter) { 236 Assert.isMainThread(); 237 mPipelineState.requireState(STATE_IDLE); 238 239 mNotifPromoters.add(promoter); 240 promoter.setInvalidationListener(this::onPromoterInvalidated); 241 } 242 setSectioners(List<NotifSectioner> sectioners)243 void setSectioners(List<NotifSectioner> sectioners) { 244 Assert.isMainThread(); 245 mPipelineState.requireState(STATE_IDLE); 246 247 mNotifSections.clear(); 248 for (NotifSectioner sectioner : sectioners) { 249 final NotifSection section = new NotifSection(sectioner, mNotifSections.size()); 250 final NotifComparator sectionComparator = section.getComparator(); 251 mNotifSections.add(section); 252 sectioner.setInvalidationListener(this::onNotifSectionInvalidated); 253 if (sectionComparator != null) { 254 sectionComparator.setInvalidationListener(this::onNotifComparatorInvalidated); 255 } 256 } 257 258 mNotifSections.add(new NotifSection(DEFAULT_SECTIONER, mNotifSections.size())); 259 260 // validate sections 261 final ArraySet<Integer> seenBuckets = new ArraySet<>(); 262 int lastBucket = mNotifSections.size() > 0 263 ? mNotifSections.get(0).getBucket() 264 : 0; 265 for (NotifSection section : mNotifSections) { 266 if (lastBucket != section.getBucket() && seenBuckets.contains(section.getBucket())) { 267 throw new IllegalStateException("setSectioners with non contiguous sections " 268 + section.getLabel() + " has an already seen bucket"); 269 } 270 lastBucket = section.getBucket(); 271 seenBuckets.add(lastBucket); 272 } 273 } 274 setNotifStabilityManager(@onNull NotifStabilityManager notifStabilityManager)275 void setNotifStabilityManager(@NonNull NotifStabilityManager notifStabilityManager) { 276 Assert.isMainThread(); 277 mPipelineState.requireState(STATE_IDLE); 278 279 if (mNotifStabilityManager != null) { 280 throw new IllegalStateException( 281 "Attempting to set the NotifStabilityManager more than once. There should " 282 + "only be one visual stability manager. Manager is being set by " 283 + mNotifStabilityManager.getName() + " and " 284 + notifStabilityManager.getName()); 285 } 286 287 mNotifStabilityManager = notifStabilityManager; 288 mNotifStabilityManager.setInvalidationListener(this::onReorderingAllowedInvalidated); 289 } 290 291 @NonNull getStabilityManager()292 private NotifStabilityManager getStabilityManager() { 293 if (mNotifStabilityManager == null) { 294 return DefaultNotifStabilityManager.INSTANCE; 295 } 296 return mNotifStabilityManager; 297 } 298 setComparators(List<NotifComparator> comparators)299 void setComparators(List<NotifComparator> comparators) { 300 Assert.isMainThread(); 301 mPipelineState.requireState(STATE_IDLE); 302 303 mNotifComparators.clear(); 304 for (NotifComparator comparator : comparators) { 305 mNotifComparators.add(comparator); 306 comparator.setInvalidationListener(this::onNotifComparatorInvalidated); 307 } 308 } 309 getShadeList()310 List<ListEntry> getShadeList() { 311 Assert.isMainThread(); 312 // NOTE: Accessing this method when the pipeline is running is generally going to provide 313 // incorrect results, and indicates a poorly behaved component of the pipeline. 314 mPipelineState.requireState(STATE_IDLE); 315 return mReadOnlyNotifList; 316 } 317 318 private final CollectionReadyForBuildListener mReadyForBuildListener = 319 new CollectionReadyForBuildListener() { 320 @Override 321 public void onBuildList(Collection<NotificationEntry> entries, String reason) { 322 Assert.isMainThread(); 323 mPendingEntries = new ArrayList<>(entries); 324 mLogger.logOnBuildList(reason); 325 rebuildListIfBefore(STATE_BUILD_STARTED); 326 } 327 }; 328 onPreRenderInvalidated(Invalidator invalidator, @Nullable String reason)329 private void onPreRenderInvalidated(Invalidator invalidator, @Nullable String reason) { 330 Assert.isMainThread(); 331 332 mLogger.logPreRenderInvalidated(invalidator, mPipelineState.getState(), reason); 333 334 rebuildListIfBefore(STATE_FINALIZING); 335 } 336 onPreGroupFilterInvalidated(NotifFilter filter, @Nullable String reason)337 private void onPreGroupFilterInvalidated(NotifFilter filter, @Nullable String reason) { 338 Assert.isMainThread(); 339 340 mLogger.logPreGroupFilterInvalidated(filter, mPipelineState.getState(), reason); 341 342 rebuildListIfBefore(STATE_PRE_GROUP_FILTERING); 343 } 344 onReorderingAllowedInvalidated(NotifStabilityManager stabilityManager, @Nullable String reason)345 private void onReorderingAllowedInvalidated(NotifStabilityManager stabilityManager, 346 @Nullable String reason) { 347 Assert.isMainThread(); 348 349 mLogger.logReorderingAllowedInvalidated( 350 stabilityManager, 351 mPipelineState.getState(), 352 reason); 353 354 rebuildListIfBefore(STATE_GROUPING); 355 } 356 onPromoterInvalidated(NotifPromoter promoter, @Nullable String reason)357 private void onPromoterInvalidated(NotifPromoter promoter, @Nullable String reason) { 358 Assert.isMainThread(); 359 360 mLogger.logPromoterInvalidated(promoter, mPipelineState.getState(), reason); 361 362 rebuildListIfBefore(STATE_TRANSFORMING); 363 } 364 onNotifSectionInvalidated(NotifSectioner section, @Nullable String reason)365 private void onNotifSectionInvalidated(NotifSectioner section, @Nullable String reason) { 366 Assert.isMainThread(); 367 368 mLogger.logNotifSectionInvalidated(section, mPipelineState.getState(), reason); 369 370 rebuildListIfBefore(STATE_SORTING); 371 } 372 onFinalizeFilterInvalidated(NotifFilter filter, @Nullable String reason)373 private void onFinalizeFilterInvalidated(NotifFilter filter, @Nullable String reason) { 374 Assert.isMainThread(); 375 376 mLogger.logFinalizeFilterInvalidated(filter, mPipelineState.getState(), reason); 377 378 rebuildListIfBefore(STATE_FINALIZE_FILTERING); 379 } 380 onNotifComparatorInvalidated(NotifComparator comparator, @Nullable String reason)381 private void onNotifComparatorInvalidated(NotifComparator comparator, @Nullable String reason) { 382 Assert.isMainThread(); 383 384 mLogger.logNotifComparatorInvalidated(comparator, mPipelineState.getState(), reason); 385 386 rebuildListIfBefore(STATE_SORTING); 387 } 388 389 /** 390 * The core algorithm of the pipeline. See the top comment in {@link NotifPipeline} for 391 * details on our contracts with other code. 392 * 393 * Once the build starts we are very careful to protect against reentrant code. Anything that 394 * tries to invalidate itself after the pipeline has passed it by will return in an exception. 395 * In general, we should be extremely sensitive to client code doing things in the wrong order; 396 * if we detect that behavior, we should crash instantly. 397 */ buildList()398 private void buildList() { 399 Trace.beginSection("ShadeListBuilder.buildList"); 400 mPipelineState.requireIsBefore(STATE_BUILD_STARTED); 401 402 if (mPendingEntries != null) { 403 mAllEntries = mPendingEntries; 404 mPendingEntries = null; 405 } 406 407 if (!mNotifStabilityManager.isPipelineRunAllowed()) { 408 mLogger.logPipelineRunSuppressed(); 409 Trace.endSection(); 410 return; 411 } 412 413 mPipelineState.setState(STATE_BUILD_STARTED); 414 415 // Step 1: Reset notification states 416 mPipelineState.incrementTo(STATE_RESETTING); 417 resetNotifs(); 418 onBeginRun(); 419 420 // Step 2: Filter out any notifications that shouldn't be shown right now 421 mPipelineState.incrementTo(STATE_PRE_GROUP_FILTERING); 422 filterNotifs(mAllEntries, mNotifList, mNotifPreGroupFilters); 423 424 // Step 3: Group notifications with the same group key and set summaries 425 mPipelineState.incrementTo(STATE_GROUPING); 426 groupNotifs(mNotifList, mNewNotifList); 427 applyNewNotifList(); 428 pruneIncompleteGroups(mNotifList); 429 430 // Step 4: Group transforming 431 // Move some notifs out of their groups and up to top-level (mostly used for heads-upping) 432 dispatchOnBeforeTransformGroups(mReadOnlyNotifList); 433 mPipelineState.incrementTo(STATE_TRANSFORMING); 434 promoteNotifs(mNotifList); 435 pruneIncompleteGroups(mNotifList); 436 437 // Step 4.5: Reassign/revert any groups to maintain visual stability 438 mPipelineState.incrementTo(STATE_GROUP_STABILIZING); 439 stabilizeGroupingNotifs(mNotifList); 440 441 // Step 5: Section & Sort 442 // Assign each top-level entry a section, and copy to all of its children 443 dispatchOnBeforeSort(mReadOnlyNotifList); 444 mPipelineState.incrementTo(STATE_SORTING); 445 assignSections(); 446 notifySectionEntriesUpdated(); 447 // Sort the list by section and then within section by our list of custom comparators 448 sortListAndGroups(); 449 450 // Step 6: Filter out entries after pre-group filtering, grouping, promoting, and sorting 451 // Now filters can see grouping, sectioning, and order information to determine whether 452 // to filter or not. 453 dispatchOnBeforeFinalizeFilter(mReadOnlyNotifList); 454 mPipelineState.incrementTo(STATE_FINALIZE_FILTERING); 455 filterNotifs(mNotifList, mNewNotifList, mNotifFinalizeFilters); 456 applyNewNotifList(); 457 pruneIncompleteGroups(mNotifList); 458 459 // Step 7: Lock in our group structure and log anything that's changed since the last run 460 mPipelineState.incrementTo(STATE_FINALIZING); 461 logChanges(); 462 freeEmptyGroups(); 463 cleanupPluggables(); 464 465 // Step 8: Dispatch the new list, first to any listeners and then to the view layer 466 dispatchOnBeforeRenderList(mReadOnlyNotifList); 467 Trace.beginSection("ShadeListBuilder.onRenderList"); 468 if (mOnRenderListListener != null) { 469 mOnRenderListListener.onRenderList(mReadOnlyNotifList); 470 } 471 Trace.endSection(); 472 473 Trace.beginSection("ShadeListBuilder.logEndBuildList"); 474 // Step 9: We're done! 475 mLogger.logEndBuildList( 476 mIterationCount, 477 mReadOnlyNotifList.size(), 478 countChildren(mReadOnlyNotifList), 479 /* enforcedVisualStability */ !mNotifStabilityManager.isEveryChangeAllowed()); 480 if (mAlwaysLogList || mIterationCount % 10 == 0) { 481 Trace.beginSection("ShadeListBuilder.logFinalList"); 482 mLogger.logFinalList(mNotifList); 483 Trace.endSection(); 484 } 485 Trace.endSection(); 486 mPipelineState.setState(STATE_IDLE); 487 mIterationCount++; 488 Trace.endSection(); 489 } 490 notifySectionEntriesUpdated()491 private void notifySectionEntriesUpdated() { 492 Trace.beginSection("ShadeListBuilder.notifySectionEntriesUpdated"); 493 mTempSectionMembers.clear(); 494 for (NotifSection section : mNotifSections) { 495 for (ListEntry entry : mNotifList) { 496 if (section == entry.getSection()) { 497 mTempSectionMembers.add(entry); 498 } 499 } 500 Trace.beginSection(section.getLabel()); 501 section.getSectioner().onEntriesUpdated(mTempSectionMembers); 502 Trace.endSection(); 503 mTempSectionMembers.clear(); 504 } 505 Trace.endSection(); 506 } 507 508 /** 509 * Points mNotifList to the list stored in mNewNotifList. 510 * Reuses the (emptied) mNotifList as mNewNotifList. 511 * 512 * Accordingly, updates the ReadOnlyNotifList pointers. 513 */ applyNewNotifList()514 private void applyNewNotifList() { 515 mNotifList.clear(); 516 List<ListEntry> emptyList = mNotifList; 517 mNotifList = mNewNotifList; 518 mNewNotifList = emptyList; 519 520 List<ListEntry> readOnlyNotifList = mReadOnlyNotifList; 521 mReadOnlyNotifList = mReadOnlyNewNotifList; 522 mReadOnlyNewNotifList = readOnlyNotifList; 523 } 524 resetNotifs()525 private void resetNotifs() { 526 for (GroupEntry group : mGroups.values()) { 527 group.beginNewAttachState(); 528 group.clearChildren(); 529 group.setSummary(null); 530 } 531 532 for (NotificationEntry entry : mAllEntries) { 533 entry.beginNewAttachState(); 534 } 535 536 mNotifList.clear(); 537 } 538 filterNotifs( Collection<? extends ListEntry> entries, List<ListEntry> out, List<NotifFilter> filters)539 private void filterNotifs( 540 Collection<? extends ListEntry> entries, 541 List<ListEntry> out, 542 List<NotifFilter> filters) { 543 Trace.beginSection("ShadeListBuilder.filterNotifs"); 544 final long now = mSystemClock.uptimeMillis(); 545 for (ListEntry entry : entries) { 546 if (entry instanceof GroupEntry) { 547 final GroupEntry groupEntry = (GroupEntry) entry; 548 549 // apply filter on its summary 550 final NotificationEntry summary = groupEntry.getRepresentativeEntry(); 551 if (applyFilters(summary, now, filters)) { 552 groupEntry.setSummary(null); 553 annulAddition(summary); 554 } 555 556 // apply filter on its children 557 final List<NotificationEntry> children = groupEntry.getRawChildren(); 558 for (int j = children.size() - 1; j >= 0; j--) { 559 final NotificationEntry child = children.get(j); 560 if (applyFilters(child, now, filters)) { 561 children.remove(child); 562 annulAddition(child); 563 } 564 } 565 566 out.add(groupEntry); 567 } else { 568 if (applyFilters((NotificationEntry) entry, now, filters)) { 569 annulAddition(entry); 570 } else { 571 out.add(entry); 572 } 573 } 574 } 575 Trace.endSection(); 576 } 577 groupNotifs(List<ListEntry> entries, List<ListEntry> out)578 private void groupNotifs(List<ListEntry> entries, List<ListEntry> out) { 579 Trace.beginSection("ShadeListBuilder.groupNotifs"); 580 for (ListEntry listEntry : entries) { 581 // since grouping hasn't happened yet, all notifs are NotificationEntries 582 NotificationEntry entry = (NotificationEntry) listEntry; 583 if (entry.getSbn().isGroup()) { 584 final String topLevelKey = entry.getSbn().getGroupKey(); 585 586 GroupEntry group = mGroups.get(topLevelKey); 587 if (group == null) { 588 group = new GroupEntry(topLevelKey, mSystemClock.uptimeMillis()); 589 mGroups.put(topLevelKey, group); 590 } 591 if (group.getParent() == null) { 592 group.setParent(ROOT_ENTRY); 593 out.add(group); 594 } 595 596 entry.setParent(group); 597 598 if (entry.getSbn().getNotification().isGroupSummary()) { 599 final NotificationEntry existingSummary = group.getSummary(); 600 601 if (existingSummary == null) { 602 group.setSummary(entry); 603 } else { 604 mLogger.logDuplicateSummary(mIterationCount, group, existingSummary, entry); 605 606 // Use whichever one was posted most recently 607 if (entry.getSbn().getPostTime() 608 > existingSummary.getSbn().getPostTime()) { 609 group.setSummary(entry); 610 annulAddition(existingSummary, out); 611 } else { 612 annulAddition(entry, out); 613 } 614 } 615 } else { 616 group.addChild(entry); 617 } 618 619 } else { 620 621 final String topLevelKey = entry.getKey(); 622 if (mGroups.containsKey(topLevelKey)) { 623 mLogger.logDuplicateTopLevelKey(mIterationCount, topLevelKey); 624 } else { 625 entry.setParent(ROOT_ENTRY); 626 out.add(entry); 627 } 628 } 629 } 630 Trace.endSection(); 631 } 632 stabilizeGroupingNotifs(List<ListEntry> topLevelList)633 private void stabilizeGroupingNotifs(List<ListEntry> topLevelList) { 634 if (getStabilityManager().isEveryChangeAllowed()) { 635 return; 636 } 637 Trace.beginSection("ShadeListBuilder.stabilizeGroupingNotifs"); 638 639 for (int i = 0; i < topLevelList.size(); i++) { 640 final ListEntry tle = topLevelList.get(i); 641 if (tle instanceof GroupEntry) { 642 // maybe put children back into their old group (including moving back to top-level) 643 GroupEntry groupEntry = (GroupEntry) tle; 644 List<NotificationEntry> children = groupEntry.getRawChildren(); 645 for (int j = 0; j < groupEntry.getChildren().size(); j++) { 646 if (maybeSuppressGroupChange(children.get(j), topLevelList)) { 647 // child was put back into its previous group, so we remove it from this 648 // group 649 children.remove(j); 650 j--; 651 } 652 } 653 } else { 654 // maybe put top-level-entries back into their previous groups 655 if (maybeSuppressGroupChange(tle.getRepresentativeEntry(), topLevelList)) { 656 // entry was put back into its previous group, so we remove it from the list of 657 // top-level-entries 658 topLevelList.remove(i); 659 i--; 660 } 661 } 662 } 663 Trace.endSection(); 664 } 665 666 /** 667 * Returns true if the group change was suppressed, else false 668 */ maybeSuppressGroupChange(NotificationEntry entry, List<ListEntry> out)669 private boolean maybeSuppressGroupChange(NotificationEntry entry, List<ListEntry> out) { 670 final GroupEntry prevParent = entry.getPreviousAttachState().getParent(); 671 if (prevParent == null) { 672 // New entries are always allowed. 673 return false; 674 } 675 final GroupEntry assignedParent = entry.getParent(); 676 if (prevParent == assignedParent) { 677 // Nothing to change. 678 return false; 679 } 680 if (prevParent != ROOT_ENTRY && prevParent.getParent() == null) { 681 // Previous parent was a group, which has been removed (hence, its parent is null). 682 // Always allow this group change, otherwise the child will remain attached to the 683 // removed group and be removed from the shade until visual stability ends. 684 return false; 685 } 686 // TODO: Rather than perform "half" of the move here and require the caller remove the child 687 // from the assignedParent, ideally we would have an atomic "move" operation. 688 if (!getStabilityManager().isGroupChangeAllowed(entry.getRepresentativeEntry())) { 689 entry.getAttachState().getSuppressedChanges().setParent(assignedParent); 690 entry.setParent(prevParent); 691 if (prevParent == ROOT_ENTRY) { 692 out.add(entry); 693 } else { 694 prevParent.addChild(entry); 695 if (!mGroups.containsKey(prevParent.getKey())) { 696 mGroups.put(prevParent.getKey(), prevParent); 697 } 698 } 699 return true; 700 } 701 return false; 702 } 703 promoteNotifs(List<ListEntry> list)704 private void promoteNotifs(List<ListEntry> list) { 705 Trace.beginSection("ShadeListBuilder.promoteNotifs"); 706 for (int i = 0; i < list.size(); i++) { 707 final ListEntry tle = list.get(i); 708 709 if (tle instanceof GroupEntry) { 710 final GroupEntry group = (GroupEntry) tle; 711 712 group.getRawChildren().removeIf(child -> { 713 final boolean shouldPromote = applyTopLevelPromoters(child); 714 715 if (shouldPromote) { 716 child.setParent(ROOT_ENTRY); 717 list.add(child); 718 } 719 720 return shouldPromote; 721 }); 722 } 723 } 724 Trace.endSection(); 725 } 726 pruneIncompleteGroups(List<ListEntry> shadeList)727 private void pruneIncompleteGroups(List<ListEntry> shadeList) { 728 Trace.beginSection("ShadeListBuilder.pruneIncompleteGroups"); 729 // Any group which lost a child on this run to stability is exempt from being pruned or 730 // having its summary promoted, regardless of how many children it has 731 Set<String> groupsWithChildrenLostToStability = 732 getGroupsWithChildrenLostToStability(shadeList); 733 // Groups with children lost to stability are exempt from summary promotion. 734 ArraySet<String> groupsExemptFromSummaryPromotion = 735 new ArraySet<>(groupsWithChildrenLostToStability); 736 // Any group which lost a child to filtering or promotion is exempt from having its summary 737 // promoted when it has no attached children. 738 addGroupsWithChildrenLostToFiltering(groupsExemptFromSummaryPromotion); 739 addGroupsWithChildrenLostToPromotion(shadeList, groupsExemptFromSummaryPromotion); 740 741 // Iterate backwards, so that we can remove elements without affecting indices of 742 // yet-to-be-accessed entries. 743 for (int i = shadeList.size() - 1; i >= 0; i--) { 744 final ListEntry tle = shadeList.get(i); 745 746 if (tle instanceof GroupEntry) { 747 final GroupEntry group = (GroupEntry) tle; 748 final List<NotificationEntry> children = group.getRawChildren(); 749 final boolean hasSummary = group.getSummary() != null; 750 751 if (hasSummary && children.size() == 0) { 752 if (groupsExemptFromSummaryPromotion.contains(group.getKey())) { 753 // This group lost a child on this run to promotion or stability, so it is 754 // exempt from having its summary promoted to the top level, so prune it. 755 // It has no children, so it will just vanish. 756 pruneGroupAtIndexAndPromoteAnyChildren(shadeList, group, i); 757 } else { 758 // For any other summary with no children, promote the summary. 759 pruneGroupAtIndexAndPromoteSummary(shadeList, group, i); 760 } 761 } else if (!hasSummary) { 762 // If the group doesn't provide a summary, ignore it and add 763 // any children it may have directly to top-level. 764 pruneGroupAtIndexAndPromoteAnyChildren(shadeList, group, i); 765 } else if (children.size() < MIN_CHILDREN_FOR_GROUP) { 766 // This group has a summary and insufficient, but nonzero children. 767 checkState(hasSummary, "group must have summary at this point"); 768 checkState(!children.isEmpty(), "empty group should have been promoted"); 769 770 if (groupsWithChildrenLostToStability.contains(group.getKey())) { 771 // This group lost a child on this run to stability, so it is exempt from 772 // the "min children" requirement; keep it around in case more children are 773 // added before changes are allowed again. 774 group.getAttachState().getSuppressedChanges().setWasPruneSuppressed(true); 775 continue; 776 } 777 if (group.wasAttachedInPreviousPass() 778 && !getStabilityManager().isGroupPruneAllowed(group)) { 779 checkState(!children.isEmpty(), "empty group should have been pruned"); 780 // This group was previously attached and group changes aren't 781 // allowed; keep it around until group changes are allowed again. 782 group.getAttachState().getSuppressedChanges().setWasPruneSuppressed(true); 783 continue; 784 } 785 786 // The group is too small, ignore it and add 787 // its children (if any) directly to top-level. 788 pruneGroupAtIndexAndPromoteAnyChildren(shadeList, group, i); 789 } 790 } 791 } 792 Trace.endSection(); 793 } 794 pruneGroupAtIndexAndPromoteSummary(List<ListEntry> shadeList, GroupEntry group, int index)795 private void pruneGroupAtIndexAndPromoteSummary(List<ListEntry> shadeList, 796 GroupEntry group, int index) { 797 // Validate that the group has no children 798 checkArgument(group.getChildren().isEmpty(), "group should have no children"); 799 800 NotificationEntry summary = group.getSummary(); 801 summary.setParent(ROOT_ENTRY); 802 // The list may be sorted; replace the group with the summary, in its place 803 ListEntry oldEntry = shadeList.set(index, summary); 804 805 // Validate that the replaced entry was the group entry 806 checkState(oldEntry == group); 807 808 group.setSummary(null); 809 annulAddition(group, shadeList); 810 summary.getAttachState().setGroupPruneReason( 811 "SUMMARY with no children @ " + mPipelineState.getStateName()); 812 } 813 pruneGroupAtIndexAndPromoteAnyChildren(List<ListEntry> shadeList, GroupEntry group, int index)814 private void pruneGroupAtIndexAndPromoteAnyChildren(List<ListEntry> shadeList, 815 GroupEntry group, int index) { 816 // REMOVE the GroupEntry at this index 817 ListEntry oldEntry = shadeList.remove(index); 818 819 // Validate that the replaced entry was the group entry 820 checkState(oldEntry == group); 821 822 List<NotificationEntry> children = group.getRawChildren(); 823 boolean hasSummary = group.getSummary() != null; 824 825 // Remove the group summary, if present, and leave detached. 826 if (hasSummary) { 827 final NotificationEntry summary = group.getSummary(); 828 group.setSummary(null); 829 annulAddition(summary, shadeList); 830 summary.getAttachState().setGroupPruneReason( 831 "SUMMARY with too few children @ " + mPipelineState.getStateName()); 832 } 833 834 // Promote any children 835 if (!children.isEmpty()) { 836 // create the reason we will report on the child for why its group was pruned. 837 String childReason = hasSummary 838 ? ("CHILD with " + (children.size() - 1) + " siblings @ " 839 + mPipelineState.getStateName()) 840 : ("CHILD with no summary @ " + mPipelineState.getStateName()); 841 842 // Remove children from the group and add them to the shadeList. 843 for (int j = 0; j < children.size(); j++) { 844 final NotificationEntry child = children.get(j); 845 child.setParent(ROOT_ENTRY); 846 child.getAttachState().setGroupPruneReason(requireNonNull(childReason)); 847 } 848 // The list may be sorted, so add the children in order where the group was. 849 shadeList.addAll(index, children); 850 children.clear(); 851 } 852 853 annulAddition(group, shadeList); 854 } 855 856 /** 857 * Collect the keys of any groups which have already lost a child to stability this run. 858 * 859 * If stability is being enforced, then {@link #stabilizeGroupingNotifs(List)} might have 860 * detached some children from their groups and left them at the top level because the child was 861 * previously attached at the top level. Doing so would set the 862 * {@link SuppressedAttachState#getParent() suppressed parent} for the current attach state. 863 * 864 * If we've already removed a child from this group, we don't want to remove any more children 865 * from the group (even if that would leave only a single notification in the group) because 866 * that could cascade over multiple runs and allow a large group of notifications all show up as 867 * top level (ungrouped) notifications. 868 */ 869 @NonNull getGroupsWithChildrenLostToStability(List<ListEntry> shadeList)870 private Set<String> getGroupsWithChildrenLostToStability(List<ListEntry> shadeList) { 871 if (getStabilityManager().isEveryChangeAllowed()) { 872 return Collections.emptySet(); 873 } 874 ArraySet<String> groupsWithChildrenLostToStability = new ArraySet<>(); 875 for (int i = 0; i < shadeList.size(); i++) { 876 final ListEntry tle = shadeList.get(i); 877 final GroupEntry suppressedParent = 878 tle.getAttachState().getSuppressedChanges().getParent(); 879 if (suppressedParent != null) { 880 // This top-level-entry was supposed to be attached to this group, 881 // so mark the group as having lost a child to stability. 882 groupsWithChildrenLostToStability.add(suppressedParent.getKey()); 883 } 884 } 885 return groupsWithChildrenLostToStability; 886 } 887 888 /** 889 * Collect the keys of any groups which have already lost a child to a {@link NotifPromoter} 890 * this run. 891 * 892 * These groups will be exempt from appearing without any children. 893 */ addGroupsWithChildrenLostToPromotion(List<ListEntry> shadeList, Set<String> out)894 private void addGroupsWithChildrenLostToPromotion(List<ListEntry> shadeList, Set<String> out) { 895 for (int i = 0; i < shadeList.size(); i++) { 896 final ListEntry tle = shadeList.get(i); 897 if (tle.getAttachState().getPromoter() != null) { 898 // This top-level-entry was part of a group, but was promoted out of it. 899 final String groupKey = tle.getRepresentativeEntry().getSbn().getGroupKey(); 900 out.add(groupKey); 901 } 902 } 903 } 904 905 /** 906 * Collect the keys of any groups which have already lost a child to a {@link NotifFilter} 907 * this run. 908 * 909 * These groups will be exempt from appearing without any children. 910 */ addGroupsWithChildrenLostToFiltering(Set<String> out)911 private void addGroupsWithChildrenLostToFiltering(Set<String> out) { 912 for (ListEntry tle : mAllEntries) { 913 StatusBarNotification sbn = tle.getRepresentativeEntry().getSbn(); 914 if (sbn.isGroup() 915 && !sbn.getNotification().isGroupSummary() 916 && tle.getAttachState().getExcludingFilter() != null) { 917 out.add(sbn.getGroupKey()); 918 } 919 } 920 } 921 922 /** 923 * If a ListEntry was added to the shade list and then later removed (e.g. because it was a 924 * group that was broken up), this method will erase any bookkeeping traces of that addition 925 * and/or check that they were already erased. 926 * 927 * Before calling this method, the entry must already have been removed from its parent. If 928 * it's a group, its summary must be null and its children must be empty. 929 */ annulAddition(ListEntry entry, List<ListEntry> shadeList)930 private void annulAddition(ListEntry entry, List<ListEntry> shadeList) { 931 932 // This function does very little, but if any of its assumptions are violated (and it has a 933 // lot of them), it will put the system into an inconsistent state. So we check all of them 934 // here. 935 936 if (entry.getParent() == null) { 937 throw new IllegalStateException( 938 "Cannot nullify addition of " + entry.getKey() + ": no parent."); 939 } 940 941 if (entry.getParent() == ROOT_ENTRY) { 942 if (shadeList.contains(entry)) { 943 throw new IllegalStateException("Cannot nullify addition of " + entry.getKey() 944 + ": it's still in the shade list."); 945 } 946 } 947 948 if (entry instanceof GroupEntry) { 949 GroupEntry ge = (GroupEntry) entry; 950 if (ge.getSummary() != null) { 951 throw new IllegalStateException( 952 "Cannot nullify group " + ge.getKey() + ": summary is not null"); 953 } 954 if (!ge.getChildren().isEmpty()) { 955 throw new IllegalStateException( 956 "Cannot nullify group " + ge.getKey() + ": still has children"); 957 } 958 } else if (entry instanceof NotificationEntry) { 959 if (entry == entry.getParent().getSummary() 960 || entry.getParent().getChildren().contains(entry)) { 961 throw new IllegalStateException("Cannot nullify addition of child " 962 + entry.getKey() + ": it's still attached to its parent."); 963 } 964 } 965 966 annulAddition(entry); 967 968 } 969 970 /** 971 * Erases bookkeeping traces stored on an entry when it is removed from the notif list. 972 * This can happen if the entry is removed from a group that was broken up or if the entry was 973 * filtered out during any of the filtering steps. 974 */ annulAddition(ListEntry entry)975 private void annulAddition(ListEntry entry) { 976 entry.getAttachState().detach(); 977 } 978 assignSections()979 private void assignSections() { 980 Trace.beginSection("ShadeListBuilder.assignSections"); 981 // Assign sections to top-level elements and their children 982 for (ListEntry entry : mNotifList) { 983 NotifSection section = applySections(entry); 984 if (entry instanceof GroupEntry) { 985 GroupEntry parent = (GroupEntry) entry; 986 for (NotificationEntry child : parent.getChildren()) { 987 setEntrySection(child, section); 988 } 989 } 990 } 991 Trace.endSection(); 992 } 993 sortListAndGroups()994 private void sortListAndGroups() { 995 Trace.beginSection("ShadeListBuilder.sortListAndGroups"); 996 sortWithSemiStableSort(); 997 Trace.endSection(); 998 } 999 sortWithSemiStableSort()1000 private void sortWithSemiStableSort() { 1001 // Sort each group's children 1002 boolean allSorted = true; 1003 for (ListEntry entry : mNotifList) { 1004 if (entry instanceof GroupEntry) { 1005 GroupEntry parent = (GroupEntry) entry; 1006 allSorted &= sortGroupChildren(parent.getRawChildren()); 1007 } 1008 } 1009 // Sort each section within the top level list 1010 mNotifList.sort(mTopLevelComparator); 1011 if (!getStabilityManager().isEveryChangeAllowed()) { 1012 for (List<ListEntry> subList : getSectionSubLists(mNotifList)) { 1013 allSorted &= mSemiStableSort.stabilizeTo(subList, mStableOrder, mNewNotifList); 1014 } 1015 applyNewNotifList(); 1016 } 1017 assignIndexes(mNotifList); 1018 if (!allSorted) { 1019 // Report suppressed order changes 1020 getStabilityManager().onEntryReorderSuppressed(); 1021 } 1022 } 1023 getSectionSubLists(List<ListEntry> entries)1024 private Iterable<List<ListEntry>> getSectionSubLists(List<ListEntry> entries) { 1025 return ShadeListBuilderHelper.INSTANCE.getSectionSubLists(entries); 1026 } 1027 sortGroupChildren(List<NotificationEntry> entries)1028 private boolean sortGroupChildren(List<NotificationEntry> entries) { 1029 if (getStabilityManager().isEveryChangeAllowed()) { 1030 entries.sort(mGroupChildrenComparator); 1031 return true; 1032 } else { 1033 return mSemiStableSort.sort(entries, mStableOrder, mGroupChildrenComparator); 1034 } 1035 } 1036 1037 /** Determine whether the items in the list are sorted according to the comparator */ 1038 @VisibleForTesting isSorted(List<T> items, Comparator<? super T> comparator)1039 public static <T> boolean isSorted(List<T> items, Comparator<? super T> comparator) { 1040 if (items.size() <= 1) { 1041 return true; 1042 } 1043 Iterator<T> iterator = items.iterator(); 1044 T previous = iterator.next(); 1045 T current; 1046 while (iterator.hasNext()) { 1047 current = iterator.next(); 1048 if (comparator.compare(previous, current) > 0) { 1049 return false; 1050 } 1051 previous = current; 1052 } 1053 return true; 1054 } 1055 1056 /** 1057 * Assign the index of each notification relative to the total order 1058 */ assignIndexes(List<ListEntry> notifList)1059 private void assignIndexes(List<ListEntry> notifList) { 1060 if (notifList.size() == 0) return; 1061 NotifSection currentSection = requireNonNull(notifList.get(0).getSection()); 1062 int sectionMemberIndex = 0; 1063 for (int i = 0; i < notifList.size(); i++) { 1064 final ListEntry entry = notifList.get(i); 1065 NotifSection section = requireNonNull(entry.getSection()); 1066 if (section.getIndex() != currentSection.getIndex()) { 1067 sectionMemberIndex = 0; 1068 currentSection = section; 1069 } 1070 entry.getAttachState().setStableIndex(sectionMemberIndex++); 1071 if (entry instanceof GroupEntry) { 1072 final GroupEntry parent = (GroupEntry) entry; 1073 final NotificationEntry summary = parent.getSummary(); 1074 if (summary != null) { 1075 summary.getAttachState().setStableIndex(sectionMemberIndex++); 1076 } 1077 for (NotificationEntry child : parent.getChildren()) { 1078 child.getAttachState().setStableIndex(sectionMemberIndex++); 1079 } 1080 } 1081 } 1082 } 1083 freeEmptyGroups()1084 private void freeEmptyGroups() { 1085 Trace.beginSection("ShadeListBuilder.freeEmptyGroups"); 1086 mGroups.values().removeIf(ge -> ge.getSummary() == null && ge.getChildren().isEmpty()); 1087 Trace.endSection(); 1088 } 1089 logChanges()1090 private void logChanges() { 1091 Trace.beginSection("ShadeListBuilder.logChanges"); 1092 for (NotificationEntry entry : mAllEntries) { 1093 logAttachStateChanges(entry); 1094 } 1095 for (GroupEntry group : mGroups.values()) { 1096 logAttachStateChanges(group); 1097 } 1098 Trace.endSection(); 1099 } 1100 logAttachStateChanges(ListEntry entry)1101 private void logAttachStateChanges(ListEntry entry) { 1102 1103 final ListAttachState curr = entry.getAttachState(); 1104 final ListAttachState prev = entry.getPreviousAttachState(); 1105 1106 if (!Objects.equals(curr, prev)) { 1107 mLogger.logEntryAttachStateChanged( 1108 mIterationCount, 1109 entry, 1110 prev.getParent(), 1111 curr.getParent()); 1112 1113 if (curr.getParent() != prev.getParent()) { 1114 mLogger.logParentChanged(mIterationCount, prev.getParent(), curr.getParent()); 1115 } 1116 1117 GroupEntry currSuppressedParent = curr.getSuppressedChanges().getParent(); 1118 GroupEntry prevSuppressedParent = prev.getSuppressedChanges().getParent(); 1119 if (currSuppressedParent != null && (prevSuppressedParent == null 1120 || !prevSuppressedParent.getKey().equals(currSuppressedParent.getKey()))) { 1121 mLogger.logParentChangeSuppressedStarted( 1122 mIterationCount, 1123 currSuppressedParent, 1124 curr.getParent()); 1125 } 1126 if (prevSuppressedParent != null && currSuppressedParent == null) { 1127 mLogger.logParentChangeSuppressedStopped( 1128 mIterationCount, 1129 prevSuppressedParent, 1130 prev.getParent()); 1131 } 1132 1133 if (curr.getSuppressedChanges().getSection() != null) { 1134 mLogger.logSectionChangeSuppressed( 1135 mIterationCount, 1136 curr.getSuppressedChanges().getSection(), 1137 curr.getSection()); 1138 } 1139 1140 if (curr.getSuppressedChanges().getWasPruneSuppressed()) { 1141 mLogger.logGroupPruningSuppressed( 1142 mIterationCount, 1143 curr.getParent()); 1144 } 1145 1146 if (!Objects.equals(curr.getGroupPruneReason(), prev.getGroupPruneReason())) { 1147 mLogger.logPrunedReasonChanged( 1148 mIterationCount, 1149 prev.getGroupPruneReason(), 1150 curr.getGroupPruneReason()); 1151 } 1152 1153 if (curr.getExcludingFilter() != prev.getExcludingFilter()) { 1154 mLogger.logFilterChanged( 1155 mIterationCount, 1156 prev.getExcludingFilter(), 1157 curr.getExcludingFilter()); 1158 } 1159 1160 // When something gets detached, its promoter and section are always set to null, so 1161 // don't bother logging those changes. 1162 final boolean wasDetached = curr.getParent() == null && prev.getParent() != null; 1163 1164 if (!wasDetached && curr.getPromoter() != prev.getPromoter()) { 1165 mLogger.logPromoterChanged( 1166 mIterationCount, 1167 prev.getPromoter(), 1168 curr.getPromoter()); 1169 } 1170 1171 if (!wasDetached && curr.getSection() != prev.getSection()) { 1172 mLogger.logSectionChanged( 1173 mIterationCount, 1174 prev.getSection(), 1175 curr.getSection()); 1176 } 1177 } 1178 } 1179 onBeginRun()1180 private void onBeginRun() { 1181 getStabilityManager().onBeginRun(); 1182 } 1183 cleanupPluggables()1184 private void cleanupPluggables() { 1185 Trace.beginSection("ShadeListBuilder.cleanupPluggables"); 1186 callOnCleanup(mNotifPreGroupFilters); 1187 callOnCleanup(mNotifPromoters); 1188 callOnCleanup(mNotifFinalizeFilters); 1189 callOnCleanup(mNotifComparators); 1190 1191 for (int i = 0; i < mNotifSections.size(); i++) { 1192 final NotifSection notifSection = mNotifSections.get(i); 1193 notifSection.getSectioner().onCleanup(); 1194 final NotifComparator comparator = notifSection.getComparator(); 1195 if (comparator != null) { 1196 comparator.onCleanup(); 1197 } 1198 } 1199 1200 callOnCleanup(List.of(getStabilityManager())); 1201 Trace.endSection(); 1202 } 1203 callOnCleanup(List<? extends Pluggable<?>> pluggables)1204 private void callOnCleanup(List<? extends Pluggable<?>> pluggables) { 1205 for (int i = 0; i < pluggables.size(); i++) { 1206 pluggables.get(i).onCleanup(); 1207 } 1208 } 1209 1210 @Nullable getSectionComparator( @onNull ListEntry o1, @NonNull ListEntry o2)1211 private NotifComparator getSectionComparator( 1212 @NonNull ListEntry o1, @NonNull ListEntry o2) { 1213 final NotifSection section = o1.getSection(); 1214 if (section != o2.getSection()) { 1215 throw new RuntimeException("Entry ordering should only be done within sections"); 1216 } 1217 if (section != null) { 1218 return section.getComparator(); 1219 } 1220 return null; 1221 } 1222 1223 private final Comparator<ListEntry> mTopLevelComparator = (o1, o2) -> { 1224 int cmp = Integer.compare( 1225 o1.getSectionIndex(), 1226 o2.getSectionIndex()); 1227 if (cmp != 0) return cmp; 1228 1229 NotifComparator sectionComparator = getSectionComparator(o1, o2); 1230 if (sectionComparator != null) { 1231 cmp = sectionComparator.compare(o1, o2); 1232 if (cmp != 0) return cmp; 1233 } 1234 1235 for (int i = 0; i < mNotifComparators.size(); i++) { 1236 cmp = mNotifComparators.get(i).compare(o1, o2); 1237 if (cmp != 0) return cmp; 1238 } 1239 1240 cmp = Integer.compare( 1241 o1.getRepresentativeEntry().getRanking().getRank(), 1242 o2.getRepresentativeEntry().getRanking().getRank()); 1243 if (cmp != 0) return cmp; 1244 1245 cmp = -1 * Long.compare( 1246 o1.getRepresentativeEntry().getSbn().getNotification().getWhen(), 1247 o2.getRepresentativeEntry().getSbn().getNotification().getWhen()); 1248 1249 return cmp; 1250 }; 1251 1252 1253 private final Comparator<NotificationEntry> mGroupChildrenComparator = (o1, o2) -> { 1254 int cmp = Integer.compare( 1255 o1.getRepresentativeEntry().getRanking().getRank(), 1256 o2.getRepresentativeEntry().getRanking().getRank()); 1257 if (cmp != 0) return cmp; 1258 1259 cmp = -1 * Long.compare( 1260 o1.getRepresentativeEntry().getSbn().getNotification().getWhen(), 1261 o2.getRepresentativeEntry().getSbn().getNotification().getWhen()); 1262 return cmp; 1263 }; 1264 1265 @Nullable getStableOrderRank(ListEntry entry)1266 private Integer getStableOrderRank(ListEntry entry) { 1267 if (getStabilityManager().isEntryReorderingAllowed(entry)) { 1268 // let the stability manager constrain or allow reordering 1269 return null; 1270 } 1271 if (entry.getAttachState().getSectionIndex() 1272 != entry.getPreviousAttachState().getSectionIndex()) { 1273 // stable index is only valid within the same section; otherwise we allow reordering 1274 return null; 1275 } 1276 final int stableIndex = entry.getPreviousAttachState().getStableIndex(); 1277 return stableIndex == -1 ? null : stableIndex; 1278 } 1279 applyFilters(NotificationEntry entry, long now, List<NotifFilter> filters)1280 private boolean applyFilters(NotificationEntry entry, long now, List<NotifFilter> filters) { 1281 final NotifFilter filter = findRejectingFilter(entry, now, filters); 1282 entry.getAttachState().setExcludingFilter(filter); 1283 if (filter != null) { 1284 // notification is removed from the list, so we reset its initialization time 1285 entry.resetInitializationTime(); 1286 } 1287 return filter != null; 1288 } 1289 findRejectingFilter(NotificationEntry entry, long now, List<NotifFilter> filters)1290 @Nullable private static NotifFilter findRejectingFilter(NotificationEntry entry, long now, 1291 List<NotifFilter> filters) { 1292 final int size = filters.size(); 1293 1294 for (int i = 0; i < size; i++) { 1295 NotifFilter filter = filters.get(i); 1296 if (filter.shouldFilterOut(entry, now)) { 1297 return filter; 1298 } 1299 } 1300 return null; 1301 } 1302 applyTopLevelPromoters(NotificationEntry entry)1303 private boolean applyTopLevelPromoters(NotificationEntry entry) { 1304 NotifPromoter promoter = findPromoter(entry); 1305 entry.getAttachState().setPromoter(promoter); 1306 return promoter != null; 1307 } 1308 findPromoter(NotificationEntry entry)1309 @Nullable private NotifPromoter findPromoter(NotificationEntry entry) { 1310 for (int i = 0; i < mNotifPromoters.size(); i++) { 1311 NotifPromoter promoter = mNotifPromoters.get(i); 1312 if (promoter.shouldPromoteToTopLevel(entry)) { 1313 return promoter; 1314 } 1315 } 1316 return null; 1317 } 1318 applySections(ListEntry entry)1319 private NotifSection applySections(ListEntry entry) { 1320 final NotifSection newSection = findSection(entry); 1321 final ListAttachState prevAttachState = entry.getPreviousAttachState(); 1322 1323 NotifSection finalSection = newSection; 1324 1325 // have we seen this entry before and are we changing its section? 1326 if (entry.wasAttachedInPreviousPass() && newSection != prevAttachState.getSection()) { 1327 1328 // are section changes allowed? 1329 if (!getStabilityManager().isSectionChangeAllowed(entry.getRepresentativeEntry())) { 1330 // record the section that we wanted to change to 1331 entry.getAttachState().getSuppressedChanges().setSection(newSection); 1332 1333 // keep the previous section 1334 finalSection = prevAttachState.getSection(); 1335 } 1336 } 1337 1338 setEntrySection(entry, finalSection); 1339 return finalSection; 1340 } 1341 setEntrySection(ListEntry entry, NotifSection finalSection)1342 private void setEntrySection(ListEntry entry, NotifSection finalSection) { 1343 entry.getAttachState().setSection(finalSection); 1344 NotificationEntry representativeEntry = entry.getRepresentativeEntry(); 1345 if (representativeEntry != null) { 1346 representativeEntry.getAttachState().setSection(finalSection); 1347 if (finalSection != null) { 1348 representativeEntry.setBucket(finalSection.getBucket()); 1349 } 1350 } 1351 } 1352 1353 @NonNull findSection(ListEntry entry)1354 private NotifSection findSection(ListEntry entry) { 1355 for (int i = 0; i < mNotifSections.size(); i++) { 1356 NotifSection section = mNotifSections.get(i); 1357 if (section.getSectioner().isInSection(entry)) { 1358 return section; 1359 } 1360 } 1361 throw new RuntimeException("Missing default sectioner!"); 1362 } 1363 rebuildListIfBefore(@ipelineState.StateName int rebuildState)1364 private void rebuildListIfBefore(@PipelineState.StateName int rebuildState) { 1365 final @PipelineState.StateName int currentState = mPipelineState.getState(); 1366 1367 // If the pipeline is idle, requesting an invalidation is always okay, and starts a new run. 1368 if (currentState == STATE_IDLE) { 1369 scheduleRebuild(/* reentrant = */ false, rebuildState); 1370 return; 1371 } 1372 1373 // If the pipeline is running, it is okay to request an invalidation of a *later* stage. 1374 // Since the current pipeline run hasn't run it yet, no new pipeline run is needed. 1375 if (rebuildState > currentState) { 1376 return; 1377 } 1378 1379 // If the pipeline is running, it is bad to request an invalidation of *earlier* stages or 1380 // the *current* stage; this will run the pipeline more often than needed, and may even 1381 // cause an infinite loop of pipeline runs. 1382 // 1383 // Unfortunately, there are some unfixed bugs that cause reentrant pipeline runs, so we keep 1384 // a counter and allow a few reentrant runs in a row between any two non-reentrant runs. 1385 // 1386 // It is technically possible for a *pair* of invalidations, one reentrant and one not, to 1387 // trigger *each other*, alternating responsibility for pipeline runs in an infinite loop 1388 // but constantly resetting the reentrant run counter. Hopefully that doesn't happen. 1389 scheduleRebuild(/* reentrant = */ true, rebuildState); 1390 } 1391 scheduleRebuild(boolean reentrant)1392 private void scheduleRebuild(boolean reentrant) { 1393 scheduleRebuild(reentrant, STATE_IDLE); 1394 } 1395 scheduleRebuild(boolean reentrant, @PipelineState.StateName int rebuildState)1396 private void scheduleRebuild(boolean reentrant, @PipelineState.StateName int rebuildState) { 1397 if (!reentrant) { 1398 mConsecutiveReentrantRebuilds = 0; 1399 mChoreographer.schedule(); 1400 return; 1401 } 1402 1403 final @PipelineState.StateName int currentState = mPipelineState.getState(); 1404 1405 final String rebuildStateName = PipelineState.getStateName(rebuildState); 1406 final String currentStateName = PipelineState.getStateName(currentState); 1407 final IllegalStateException exception = new IllegalStateException( 1408 "Reentrant notification pipeline rebuild of state " + rebuildStateName 1409 + " while pipeline in state " + currentStateName + "."); 1410 1411 mConsecutiveReentrantRebuilds++; 1412 1413 if (mConsecutiveReentrantRebuilds > MAX_CONSECUTIVE_REENTRANT_REBUILDS) { 1414 Log.e(TAG, "Crashing after more than " + MAX_CONSECUTIVE_REENTRANT_REBUILDS 1415 + " consecutive reentrant notification pipeline rebuilds.", exception); 1416 throw exception; 1417 } 1418 1419 Log.wtf(TAG, "Allowing " + mConsecutiveReentrantRebuilds 1420 + " consecutive reentrant notification pipeline rebuild(s).", exception); 1421 mChoreographer.schedule(); 1422 } 1423 countChildren(List<ListEntry> entries)1424 private static int countChildren(List<ListEntry> entries) { 1425 int count = 0; 1426 for (int i = 0; i < entries.size(); i++) { 1427 final ListEntry entry = entries.get(i); 1428 if (entry instanceof GroupEntry) { 1429 count += ((GroupEntry) entry).getChildren().size(); 1430 } 1431 } 1432 return count; 1433 } 1434 dispatchOnBeforeTransformGroups(List<ListEntry> entries)1435 private void dispatchOnBeforeTransformGroups(List<ListEntry> entries) { 1436 Trace.beginSection("ShadeListBuilder.dispatchOnBeforeTransformGroups"); 1437 mOnBeforeTransformGroupsListeners.forEachTraced(listener -> { 1438 listener.onBeforeTransformGroups(entries); 1439 }); 1440 Trace.endSection(); 1441 } 1442 dispatchOnBeforeSort(List<ListEntry> entries)1443 private void dispatchOnBeforeSort(List<ListEntry> entries) { 1444 Trace.beginSection("ShadeListBuilder.dispatchOnBeforeSort"); 1445 mOnBeforeSortListeners.forEachTraced(listener -> { 1446 listener.onBeforeSort(entries); 1447 }); 1448 Trace.endSection(); 1449 } 1450 dispatchOnBeforeFinalizeFilter(List<ListEntry> entries)1451 private void dispatchOnBeforeFinalizeFilter(List<ListEntry> entries) { 1452 Trace.beginSection("ShadeListBuilder.dispatchOnBeforeFinalizeFilter"); 1453 mOnBeforeFinalizeFilterListeners.forEachTraced(listener -> { 1454 listener.onBeforeFinalizeFilter(entries); 1455 }); 1456 Trace.endSection(); 1457 } 1458 dispatchOnBeforeRenderList(List<ListEntry> entries)1459 private void dispatchOnBeforeRenderList(List<ListEntry> entries) { 1460 Trace.beginSection("ShadeListBuilder.dispatchOnBeforeRenderList"); 1461 mOnBeforeRenderListListeners.forEachTraced(listener -> { 1462 listener.onBeforeRenderList(entries); 1463 }); 1464 Trace.endSection(); 1465 } 1466 1467 @Override dump(PrintWriter pw, @NonNull String[] args)1468 public void dump(PrintWriter pw, @NonNull String[] args) { 1469 pw.println("\t" + TAG + " shade notifications:"); 1470 if (getShadeList().size() == 0) { 1471 pw.println("\t\t None"); 1472 } 1473 1474 pw.println(ListDumper.dumpTree( 1475 getShadeList(), 1476 mInteractionTracker, 1477 true, 1478 "\t\t")); 1479 } 1480 1481 @Override dumpPipeline(@onNull PipelineDumper d)1482 public void dumpPipeline(@NonNull PipelineDumper d) { 1483 d.dump("choreographer", mChoreographer); 1484 d.dump("notifPreGroupFilters", mNotifPreGroupFilters); 1485 d.dump("onBeforeTransformGroupsListeners", mOnBeforeTransformGroupsListeners); 1486 d.dump("notifPromoters", mNotifPromoters); 1487 d.dump("onBeforeSortListeners", mOnBeforeSortListeners); 1488 d.dump("notifSections", mNotifSections); 1489 d.dump("notifComparators", mNotifComparators); 1490 d.dump("onBeforeFinalizeFilterListeners", mOnBeforeFinalizeFilterListeners); 1491 d.dump("notifFinalizeFilters", mNotifFinalizeFilters); 1492 d.dump("onBeforeRenderListListeners", mOnBeforeRenderListListeners); 1493 d.dump("onRenderListListener", mOnRenderListListener); 1494 } 1495 1496 /** See {@link #setOnRenderListListener(OnRenderListListener)} */ 1497 public interface OnRenderListListener { 1498 /** 1499 * Called with the final filtered, grouped, and sorted list. 1500 * 1501 * @param entries A read-only view into the current notif list. Note that this list is 1502 * backed by the live list and will change in response to new pipeline runs. 1503 */ onRenderList(@onNull List<ListEntry> entries)1504 void onRenderList(@NonNull List<ListEntry> entries); 1505 } 1506 1507 private static final NotifSectioner DEFAULT_SECTIONER = new NotifSectioner("UnknownSection", 1508 NotificationPriorityBucketKt.BUCKET_UNKNOWN) { 1509 @Override 1510 public boolean isInSection(ListEntry entry) { 1511 return true; 1512 } 1513 }; 1514 1515 private static final int MIN_CHILDREN_FOR_GROUP = 2; 1516 1517 private static final String TAG = "ShadeListBuilder"; 1518 } 1519