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