diff options
9 files changed, 773 insertions, 29 deletions
diff --git a/packages/SystemUI/src/com/android/systemui/flags/Flags.java b/packages/SystemUI/src/com/android/systemui/flags/Flags.java index e17ae28c9e95..d05097b053a4 100644 --- a/packages/SystemUI/src/com/android/systemui/flags/Flags.java +++ b/packages/SystemUI/src/com/android/systemui/flags/Flags.java @@ -75,7 +75,9 @@ public class Flags { public static final UnreleasedFlag STABILITY_INDEX_FIX = new UnreleasedFlag(114, true); - // next id: 115 + public static final UnreleasedFlag SEMI_STABLE_SORT = new UnreleasedFlag(115, true); + + // next id: 116 /***************************************/ // 200 - keyguard/lockscreen diff --git a/packages/SystemUI/src/com/android/systemui/statusbar/notification/NotifPipelineFlags.kt b/packages/SystemUI/src/com/android/systemui/statusbar/notification/NotifPipelineFlags.kt index 2f0a1aa9b0d5..e3e8a99f6db3 100644 --- a/packages/SystemUI/src/com/android/systemui/statusbar/notification/NotifPipelineFlags.kt +++ b/packages/SystemUI/src/com/android/systemui/statusbar/notification/NotifPipelineFlags.kt @@ -57,4 +57,8 @@ class NotifPipelineFlags @Inject constructor( val isStabilityIndexFixEnabled: Boolean by lazy { featureFlags.isEnabled(Flags.STABILITY_INDEX_FIX) } + + val isSemiStableSortEnabled: Boolean by lazy { + featureFlags.isEnabled(Flags.SEMI_STABLE_SORT) + } } diff --git a/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ListAttachState.kt b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ListAttachState.kt index f8449ae8807b..84ab0d1190f0 100644 --- a/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ListAttachState.kt +++ b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ListAttachState.kt @@ -68,6 +68,9 @@ data class ListAttachState private constructor( */ var stableIndex: Int = -1 + /** Access the index of the [section] or -1 if the entry does not have one */ + val sectionIndex: Int get() = section?.index ?: -1 + /** Copies the state of another instance. */ fun clone(other: ListAttachState) { parent = other.parent @@ -95,11 +98,13 @@ data class ListAttachState private constructor( * This can happen if the entry is removed from a group that was broken up or if the entry was * filtered out during any of the filtering steps. */ - fun detach() { + fun detach(includingStableIndex: Boolean) { parent = null section = null promoter = null - // stableIndex = -1 // TODO(b/241229236): Clear this once we fix the stability fragility + if (includingStableIndex) { + stableIndex = -1 + } } companion object { diff --git a/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilder.java b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilder.java index 225236f95179..3ae2545e4e10 100644 --- a/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilder.java +++ b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilder.java @@ -54,6 +54,9 @@ import com.android.systemui.statusbar.notification.collection.listbuilder.OnBefo import com.android.systemui.statusbar.notification.collection.listbuilder.OnBeforeSortListener; import com.android.systemui.statusbar.notification.collection.listbuilder.OnBeforeTransformGroupsListener; import com.android.systemui.statusbar.notification.collection.listbuilder.PipelineState; +import com.android.systemui.statusbar.notification.collection.listbuilder.SemiStableSort; +import com.android.systemui.statusbar.notification.collection.listbuilder.SemiStableSort.StableOrder; +import com.android.systemui.statusbar.notification.collection.listbuilder.ShadeListBuilderHelper; import com.android.systemui.statusbar.notification.collection.listbuilder.ShadeListBuilderLogger; import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.DefaultNotifStabilityManager; import com.android.systemui.statusbar.notification.collection.listbuilder.pluggable.Invalidator; @@ -96,12 +99,14 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { // used exclusivly by ShadeListBuilder#notifySectionEntriesUpdated // TODO replace temp with collection pool for readability private final ArrayList<ListEntry> mTempSectionMembers = new ArrayList<>(); - private final NotifPipelineFlags mFlags; + private NotifPipelineFlags mFlags; private final boolean mAlwaysLogList; private List<ListEntry> mNotifList = new ArrayList<>(); private List<ListEntry> mNewNotifList = new ArrayList<>(); + private final SemiStableSort mSemiStableSort = new SemiStableSort(); + private final StableOrder<ListEntry> mStableOrder = this::getStableOrderRank; private final PipelineState mPipelineState = new PipelineState(); private final Map<String, GroupEntry> mGroups = new ArrayMap<>(); private Collection<NotificationEntry> mAllEntries = Collections.emptyList(); @@ -529,7 +534,7 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { List<NotifFilter> filters) { Trace.beginSection("ShadeListBuilder.filterNotifs"); final long now = mSystemClock.uptimeMillis(); - for (ListEntry entry : entries) { + for (ListEntry entry : entries) { if (entry instanceof GroupEntry) { final GroupEntry groupEntry = (GroupEntry) entry; @@ -960,7 +965,8 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { * filtered out during any of the filtering steps. */ private void annulAddition(ListEntry entry) { - entry.getAttachState().detach(); + // NOTE(b/241229236): Don't clear stableIndex until we fix stability fragility + entry.getAttachState().detach(/* includingStableIndex= */ mFlags.isSemiStableSortEnabled()); } private void assignSections() { @@ -980,7 +986,16 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { private void sortListAndGroups() { Trace.beginSection("ShadeListBuilder.sortListAndGroups"); - // Assign sections to top-level elements and sort their children + if (mFlags.isSemiStableSortEnabled()) { + sortWithSemiStableSort(); + } else { + sortWithLegacyStability(); + } + Trace.endSection(); + } + + private void sortWithLegacyStability() { + // Sort all groups and the top level list for (ListEntry entry : mNotifList) { if (entry instanceof GroupEntry) { GroupEntry parent = (GroupEntry) entry; @@ -993,16 +1008,15 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { // Check for suppressed order changes if (!getStabilityManager().isEveryChangeAllowed()) { mForceReorderable = true; - boolean isSorted = isShadeSorted(); + boolean isSorted = isShadeSortedLegacy(); mForceReorderable = false; if (!isSorted) { getStabilityManager().onEntryReorderSuppressed(); } } - Trace.endSection(); } - private boolean isShadeSorted() { + private boolean isShadeSortedLegacy() { if (!isSorted(mNotifList, mTopLevelComparator)) { return false; } @@ -1016,6 +1030,43 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { return true; } + private void sortWithSemiStableSort() { + // Sort each group's children + boolean allSorted = true; + for (ListEntry entry : mNotifList) { + if (entry instanceof GroupEntry) { + GroupEntry parent = (GroupEntry) entry; + allSorted &= sortGroupChildren(parent.getRawChildren()); + } + } + // Sort each section within the top level list + mNotifList.sort(mTopLevelComparator); + if (!getStabilityManager().isEveryChangeAllowed()) { + for (List<ListEntry> subList : getSectionSubLists(mNotifList)) { + allSorted &= mSemiStableSort.stabilizeTo(subList, mStableOrder, mNewNotifList); + } + applyNewNotifList(); + } + assignIndexes(mNotifList); + if (!allSorted) { + // Report suppressed order changes + getStabilityManager().onEntryReorderSuppressed(); + } + } + + private Iterable<List<ListEntry>> getSectionSubLists(List<ListEntry> entries) { + return ShadeListBuilderHelper.INSTANCE.getSectionSubLists(entries); + } + + private boolean sortGroupChildren(List<NotificationEntry> entries) { + if (getStabilityManager().isEveryChangeAllowed()) { + entries.sort(mGroupChildrenComparator); + return true; + } else { + return mSemiStableSort.sort(entries, mStableOrder, mGroupChildrenComparator); + } + } + /** Determine whether the items in the list are sorted according to the comparator */ @VisibleForTesting public static <T> boolean isSorted(List<T> items, Comparator<? super T> comparator) { @@ -1212,7 +1263,7 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { o2.getSectionIndex()); if (cmp != 0) return cmp; - cmp = Integer.compare( + cmp = mFlags.isSemiStableSortEnabled() ? 0 : Integer.compare( getStableOrderIndex(o1), getStableOrderIndex(o2)); if (cmp != 0) return cmp; @@ -1241,7 +1292,7 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { private final Comparator<NotificationEntry> mGroupChildrenComparator = (o1, o2) -> { - int cmp = Integer.compare( + int cmp = mFlags.isSemiStableSortEnabled() ? 0 : Integer.compare( getStableOrderIndex(o1), getStableOrderIndex(o2)); if (cmp != 0) return cmp; @@ -1272,9 +1323,25 @@ public class ShadeListBuilder implements Dumpable, PipelineDumpable { // let the stability manager constrain or allow reordering return -1; } + // NOTE(b/241229236): Can't use cleared section index until we fix stability fragility return entry.getPreviousAttachState().getStableIndex(); } + @Nullable + private Integer getStableOrderRank(ListEntry entry) { + if (getStabilityManager().isEntryReorderingAllowed(entry)) { + // let the stability manager constrain or allow reordering + return null; + } + if (entry.getAttachState().getSectionIndex() + != entry.getPreviousAttachState().getSectionIndex()) { + // stable index is only valid within the same section; otherwise we allow reordering + return null; + } + final int stableIndex = entry.getPreviousAttachState().getStableIndex(); + return stableIndex == -1 ? null : stableIndex; + } + private boolean applyFilters(NotificationEntry entry, long now, List<NotifFilter> filters) { final NotifFilter filter = findRejectingFilter(entry, now, filters); entry.getAttachState().setExcludingFilter(filter); diff --git a/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/listbuilder/SemiStableSort.kt b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/listbuilder/SemiStableSort.kt new file mode 100644 index 000000000000..9ec8e07e73b3 --- /dev/null +++ b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/listbuilder/SemiStableSort.kt @@ -0,0 +1,200 @@ +/* + * Copyright (C) 2022 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.systemui.statusbar.notification.collection.listbuilder + +import androidx.annotation.VisibleForTesting +import kotlin.math.sign + +class SemiStableSort { + val preallocatedWorkspace by lazy { ArrayList<Any>() } + val preallocatedAdditions by lazy { ArrayList<Any>() } + val preallocatedMapToIndex by lazy { HashMap<Any, Int>() } + val preallocatedMapToIndexComparator: Comparator<Any> by lazy { + Comparator.comparingInt { item -> preallocatedMapToIndex[item] ?: -1 } + } + + /** + * Sort the given [items] such that items which have a [stableOrder] will all be in that order, + * items without a [stableOrder] will be sorted according to the comparator, and the two sets of + * items will be combined to have the fewest elements out of order according to the [comparator] + * . The result will be placed into the original [items] list. + */ + fun <T : Any> sort( + items: MutableList<T>, + stableOrder: StableOrder<in T>, + comparator: Comparator<in T>, + ): Boolean = + withWorkspace<T, Boolean> { workspace -> + val ordered = + sortTo( + items, + stableOrder, + comparator, + workspace, + ) + items.clear() + items.addAll(workspace) + return ordered + } + + /** + * Sort the given [items] such that items which have a [stableOrder] will all be in that order, + * items without a [stableOrder] will be sorted according to the comparator, and the two sets of + * items will be combined to have the fewest elements out of order according to the [comparator] + * . The result will be put into [output]. + */ + fun <T : Any> sortTo( + items: Iterable<T>, + stableOrder: StableOrder<in T>, + comparator: Comparator<in T>, + output: MutableList<T>, + ): Boolean { + if (DEBUG) println("\n> START from ${items.map { it to stableOrder.getRank(it) }}") + // If array already has elements, use subList to ensure we only append + val result = output.takeIf { it.isEmpty() } ?: output.subList(output.size, output.size) + items.filterTo(result) { stableOrder.getRank(it) != null } + result.sortBy { stableOrder.getRank(it)!! } + val isOrdered = result.isSorted(comparator) + withAdditions<T> { additions -> + items.filterTo(additions) { stableOrder.getRank(it) == null } + additions.sortWith(comparator) + insertPreSortedElementsWithFewestMisOrderings(result, additions, comparator) + } + return isOrdered + } + + /** + * Rearrange the [sortedItems] to enforce that items are in the [stableOrder], and store the + * result in [output]. Items with a [stableOrder] will be in that order, items without a + * [stableOrder] will remain in same relative order as the input, and the two sets of items will + * be combined to have the fewest elements moved from their locations in the original. + */ + fun <T : Any> stabilizeTo( + sortedItems: Iterable<T>, + stableOrder: StableOrder<in T>, + output: MutableList<T>, + ): Boolean { + // Append to the output array if present + val result = output.takeIf { it.isEmpty() } ?: output.subList(output.size, output.size) + sortedItems.filterTo(result) { stableOrder.getRank(it) != null } + val stableRankComparator = compareBy<T> { stableOrder.getRank(it)!! } + val isOrdered = result.isSorted(stableRankComparator) + if (!isOrdered) { + result.sortWith(stableRankComparator) + } + if (result.isEmpty()) { + sortedItems.filterTo(result) { stableOrder.getRank(it) == null } + return isOrdered + } + withAdditions<T> { additions -> + sortedItems.filterTo(additions) { stableOrder.getRank(it) == null } + if (additions.isNotEmpty()) { + withIndexOfComparator(sortedItems) { comparator -> + insertPreSortedElementsWithFewestMisOrderings(result, additions, comparator) + } + } + } + return isOrdered + } + + private inline fun <T : Any, R> withWorkspace(block: (ArrayList<T>) -> R): R { + preallocatedWorkspace.clear() + val result = block(preallocatedWorkspace as ArrayList<T>) + preallocatedWorkspace.clear() + return result + } + + private inline fun <T : Any> withAdditions(block: (ArrayList<T>) -> Unit) { + preallocatedAdditions.clear() + block(preallocatedAdditions as ArrayList<T>) + preallocatedAdditions.clear() + } + + private inline fun <T : Any> withIndexOfComparator( + sortedItems: Iterable<T>, + block: (Comparator<in T>) -> Unit + ) { + preallocatedMapToIndex.clear() + sortedItems.forEachIndexed { i, item -> preallocatedMapToIndex[item] = i } + block(preallocatedMapToIndexComparator as Comparator<in T>) + preallocatedMapToIndex.clear() + } + + companion object { + + /** + * This is the core of the algorithm. + * + * Insert [preSortedAdditions] (the elements to be inserted) into [existing] without + * changing the relative order of any elements already in [existing], even though those + * elements may be mis-ordered relative to the [comparator], such that the total number of + * elements which are ordered incorrectly according to the [comparator] is fewest. + */ + private fun <T> insertPreSortedElementsWithFewestMisOrderings( + existing: MutableList<T>, + preSortedAdditions: Iterable<T>, + comparator: Comparator<in T>, + ) { + if (DEBUG) println(" To $existing insert $preSortedAdditions with fewest misordering") + var iStart = 0 + preSortedAdditions.forEach { toAdd -> + if (DEBUG) println(" need to add $toAdd to $existing, starting at $iStart") + var cmpSum = 0 + var cmpSumMax = 0 + var iCmpSumMax = iStart + if (DEBUG) print(" ") + for (i in iCmpSumMax until existing.size) { + val cmp = comparator.compare(toAdd, existing[i]).sign + cmpSum += cmp + if (cmpSum > cmpSumMax) { + cmpSumMax = cmpSum + iCmpSumMax = i + 1 + } + if (DEBUG) print("sum[$i]=$cmpSum, ") + } + if (DEBUG) println("inserting $toAdd at $iCmpSumMax") + existing.add(iCmpSumMax, toAdd) + iStart = iCmpSumMax + 1 + } + } + + /** Determines if a list is correctly sorted according to the given comparator */ + @VisibleForTesting + fun <T> List<T>.isSorted(comparator: Comparator<T>): Boolean { + if (this.size <= 1) { + return true + } + val iterator = this.iterator() + var previous = iterator.next() + var current: T? + while (iterator.hasNext()) { + current = iterator.next() + if (comparator.compare(previous, current) > 0) { + return false + } + previous = current + } + return true + } + } + + fun interface StableOrder<T> { + fun getRank(item: T): Int? + } +} + +val DEBUG = false diff --git a/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/listbuilder/ShadeListBuilderHelper.kt b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/listbuilder/ShadeListBuilderHelper.kt new file mode 100644 index 000000000000..d8f75f61c05a --- /dev/null +++ b/packages/SystemUI/src/com/android/systemui/statusbar/notification/collection/listbuilder/ShadeListBuilderHelper.kt @@ -0,0 +1,53 @@ +/* + * Copyright (C) 2022 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package com.android.systemui.statusbar.notification.collection.listbuilder + +import com.android.systemui.statusbar.notification.collection.ListEntry + +object ShadeListBuilderHelper { + fun getSectionSubLists(entries: List<ListEntry>): Iterable<List<ListEntry>> = + getContiguousSubLists(entries, minLength = 1) { it.sectionIndex } + + inline fun <T : Any, K : Any> getContiguousSubLists( + itemList: List<T>, + minLength: Int = 1, + key: (T) -> K, + ): Iterable<List<T>> { + val subLists = mutableListOf<List<T>>() + val numEntries = itemList.size + var currentSectionStartIndex = 0 + var currentSectionKey: K? = null + for (i in 0 until numEntries) { + val sectionKey = key(itemList[i]) + if (currentSectionKey == null) { + currentSectionKey = sectionKey + } else if (currentSectionKey != sectionKey) { + val length = i - currentSectionStartIndex + if (length >= minLength) { + subLists.add(itemList.subList(currentSectionStartIndex, i)) + } + currentSectionStartIndex = i + currentSectionKey = sectionKey + } + } + val length = numEntries - currentSectionStartIndex + if (length >= minLength) { + subLists.add(itemList.subList(currentSectionStartIndex, numEntries)) + } + return subLists + } +} diff --git a/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilderTest.java b/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilderTest.java index 896ce2b3994b..09f8a10f88c7 100644 --- a/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilderTest.java +++ b/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/ShadeListBuilderTest.java @@ -34,6 +34,7 @@ import static org.mockito.Mockito.atLeast; import static org.mockito.Mockito.atLeastOnce; import static org.mockito.Mockito.clearInvocations; import static org.mockito.Mockito.inOrder; +import static org.mockito.Mockito.mock; import static org.mockito.Mockito.never; import static org.mockito.Mockito.spy; import static org.mockito.Mockito.times; @@ -136,6 +137,7 @@ public class ShadeListBuilderTest extends SysuiTestCase { public void setUp() { MockitoAnnotations.initMocks(this); allowTestableLooperAsMainThread(); + when(mNotifPipelineFlags.isStabilityIndexFixEnabled()).thenReturn(true); mListBuilder = new ShadeListBuilder( mDumpManager, @@ -1996,22 +1998,89 @@ public class ShadeListBuilderTest extends SysuiTestCase { } @Test + public void testActiveOrdering_withLegacyStability() { + when(mNotifPipelineFlags.isSemiStableSortEnabled()).thenReturn(false); + assertOrder("ABCDEFG", "ABCDEFG", "ABCDEFG", true); // no change + assertOrder("ABCDEFG", "ACDEFXBG", "ACDEFXBG", true); // X + assertOrder("ABCDEFG", "ACDEFBG", "ACDEFBG", true); // no change + assertOrder("ABCDEFG", "ACDEFBXZG", "ACDEFBXZG", true); // Z and X + assertOrder("ABCDEFG", "AXCDEZFBG", "AXCDEZFBG", true); // Z and X + gap + } + + @Test + public void testStableOrdering_withLegacyStability() { + when(mNotifPipelineFlags.isSemiStableSortEnabled()).thenReturn(false); + mStabilityManager.setAllowEntryReordering(false); + assertOrder("ABCDEFG", "ABCDEFG", "ABCDEFG", true); // no change + assertOrder("ABCDEFG", "ACDEFXBG", "XABCDEFG", false); // X + assertOrder("ABCDEFG", "ACDEFBG", "ABCDEFG", false); // no change + assertOrder("ABCDEFG", "ACDEFBXZG", "XZABCDEFG", false); // Z and X + assertOrder("ABCDEFG", "AXCDEZFBG", "XZABCDEFG", false); // Z and X + gap + } + + @Test public void testStableOrdering() { + when(mNotifPipelineFlags.isSemiStableSortEnabled()).thenReturn(true); mStabilityManager.setAllowEntryReordering(false); - assertOrder("ABCDEFG", "ACDEFXBG", "XABCDEFG"); // X - assertOrder("ABCDEFG", "ACDEFBG", "ABCDEFG"); // no change - assertOrder("ABCDEFG", "ACDEFBXZG", "XZABCDEFG"); // Z and X - assertOrder("ABCDEFG", "AXCDEZFBG", "XZABCDEFG"); // Z and X + gap - verify(mStabilityManager, times(4)).onEntryReorderSuppressed(); + // No input or output + assertOrder("", "", "", true); + // Remove everything + assertOrder("ABCDEFG", "", "", true); + // Literally no changes + assertOrder("ABCDEFG", "ABCDEFG", "ABCDEFG", true); + + // No stable order + assertOrder("", "ABCDEFG", "ABCDEFG", true); + + // F moved after A, and... + assertOrder("ABCDEFG", "AFBCDEG", "ABCDEFG", false); // No other changes + assertOrder("ABCDEFG", "AXFBCDEG", "AXBCDEFG", false); // Insert X before F + assertOrder("ABCDEFG", "AFXBCDEG", "AXBCDEFG", false); // Insert X after F + assertOrder("ABCDEFG", "AFBCDEXG", "ABCDEFXG", false); // Insert X where F was + + // B moved after F, and... + assertOrder("ABCDEFG", "ACDEFBG", "ABCDEFG", false); // No other changes + assertOrder("ABCDEFG", "ACDEFXBG", "ABCDEFXG", false); // Insert X before B + assertOrder("ABCDEFG", "ACDEFBXG", "ABCDEFXG", false); // Insert X after B + assertOrder("ABCDEFG", "AXCDEFBG", "AXBCDEFG", false); // Insert X where B was + + // Swap F and B, and... + assertOrder("ABCDEFG", "AFCDEBG", "ABCDEFG", false); // No other changes + assertOrder("ABCDEFG", "AXFCDEBG", "AXBCDEFG", false); // Insert X before F + assertOrder("ABCDEFG", "AFXCDEBG", "AXBCDEFG", false); // Insert X after F + assertOrder("ABCDEFG", "AFCXDEBG", "AXBCDEFG", false); // Insert X between CD (or: ABCXDEFG) + assertOrder("ABCDEFG", "AFCDXEBG", "ABCDXEFG", false); // Insert X between DE (or: ABCDEFXG) + assertOrder("ABCDEFG", "AFCDEXBG", "ABCDEFXG", false); // Insert X before B + assertOrder("ABCDEFG", "AFCDEBXG", "ABCDEFXG", false); // Insert X after B + + // Remove a bunch of entries at once + assertOrder("ABCDEFGHIJKL", "ACEGHI", "ACEGHI", true); + + // Remove a bunch of entries and scramble + assertOrder("ABCDEFGHIJKL", "GCEHAI", "ACEGHI", false); + + // Add a bunch of entries at once + assertOrder("ABCDEFG", "AVBWCXDYZEFG", "AVBWCXDYZEFG", true); + + // Add a bunch of entries and reverse originals + // NOTE: Some of these don't have obviously correct answers + assertOrder("ABCDEFG", "GFEBCDAVWXYZ", "ABCDEFGVWXYZ", false); // appended + assertOrder("ABCDEFG", "VWXYZGFEBCDA", "VWXYZABCDEFG", false); // prepended + assertOrder("ABCDEFG", "GFEBVWXYZCDA", "ABCDEFGVWXYZ", false); // closer to back: append + assertOrder("ABCDEFG", "GFEVWXYZBCDA", "VWXYZABCDEFG", false); // closer to front: prepend + assertOrder("ABCDEFG", "GFEVWBXYZCDA", "VWABCDEFGXYZ", false); // split new entries + + // Swap 2 pairs ("*BC*NO*"->"*NO*CB*"), remove EG, add UVWXYZ throughout + assertOrder("ABCDEFGHIJKLMNOP", "AUNOVDFHWXIJKLMYCBZP", "AUVBCDFHWXIJKLMNOYZP", false); } @Test public void testActiveOrdering() { - assertOrder("ABCDEFG", "ACDEFXBG", "ACDEFXBG"); // X - assertOrder("ABCDEFG", "ACDEFBG", "ACDEFBG"); // no change - assertOrder("ABCDEFG", "ACDEFBXZG", "ACDEFBXZG"); // Z and X - assertOrder("ABCDEFG", "AXCDEZFBG", "AXCDEZFBG"); // Z and X + gap - verify(mStabilityManager, never()).onEntryReorderSuppressed(); + when(mNotifPipelineFlags.isSemiStableSortEnabled()).thenReturn(true); + assertOrder("ABCDEFG", "ACDEFXBG", "ACDEFXBG", true); // X + assertOrder("ABCDEFG", "ACDEFBG", "ACDEFBG", true); // no change + assertOrder("ABCDEFG", "ACDEFBXZG", "ACDEFBXZG", true); // Z and X + assertOrder("ABCDEFG", "AXCDEZFBG", "AXCDEZFBG", true); // Z and X + gap } @Test @@ -2063,6 +2132,52 @@ public class ShadeListBuilderTest extends SysuiTestCase { } @Test + public void stableOrderingDisregardedWithSectionChange() { + when(mNotifPipelineFlags.isSemiStableSortEnabled()).thenReturn(true); + // GIVEN the first sectioner's packages can be changed from run-to-run + List<String> mutableSectionerPackages = new ArrayList<>(); + mutableSectionerPackages.add(PACKAGE_1); + mListBuilder.setSectioners(asList( + new PackageSectioner(mutableSectionerPackages, null), + new PackageSectioner(List.of(PACKAGE_1, PACKAGE_2, PACKAGE_3), null))); + mStabilityManager.setAllowEntryReordering(false); + + // WHEN the list is originally built with reordering disabled (and section changes allowed) + addNotif(0, PACKAGE_1).setRank(4); + addNotif(1, PACKAGE_1).setRank(5); + addNotif(2, PACKAGE_2).setRank(1); + addNotif(3, PACKAGE_2).setRank(2); + addNotif(4, PACKAGE_3).setRank(3); + dispatchBuild(); + + // VERIFY the order and that entry reordering has not been suppressed + verifyBuiltList( + notif(0), + notif(1), + notif(2), + notif(3), + notif(4) + ); + verify(mStabilityManager, never()).onEntryReorderSuppressed(); + + // WHEN the first section now claims PACKAGE_3 notifications + mutableSectionerPackages.add(PACKAGE_3); + dispatchBuild(); + + // VERIFY the re-sectioned notification is inserted at #1 of the first section, which + // is the correct position based on its rank, rather than #3 in the new section simply + // because it was #3 in its previous section. + verifyBuiltList( + notif(4), + notif(0), + notif(1), + notif(2), + notif(3) + ); + verify(mStabilityManager, never()).onEntryReorderSuppressed(); + } + + @Test public void testStableChildOrdering() { // WHEN the list is originally built with reordering disabled mStabilityManager.setAllowEntryReordering(false); @@ -2335,26 +2450,35 @@ public class ShadeListBuilderTest extends SysuiTestCase { return addGroupChildWithTag(index, packageId, groupId, null); } - private void assertOrder(String visible, String active, String expected) { + private void assertOrder(String visible, String active, String expected, + boolean isOrderedCorrectly) { StringBuilder differenceSb = new StringBuilder(); + NotifSection section = new NotifSection(mock(NotifSectioner.class), 0); for (char c : active.toCharArray()) { if (visible.indexOf(c) < 0) differenceSb.append(c); } String difference = differenceSb.toString(); + int globalIndex = 0; for (int i = 0; i < visible.length(); i++) { - addNotif(i, String.valueOf(visible.charAt(i))) - .setRank(active.indexOf(visible.charAt(i))) + final char c = visible.charAt(i); + // Skip notifications which aren't active anymore + if (!active.contains(String.valueOf(c))) continue; + addNotif(globalIndex++, String.valueOf(c)) + .setRank(active.indexOf(c)) + .setSection(section) .setStableIndex(i); - } - for (int i = 0; i < difference.length(); i++) { - addNotif(i + visible.length(), String.valueOf(difference.charAt(i))) - .setRank(active.indexOf(difference.charAt(i))) + for (char c : difference.toCharArray()) { + addNotif(globalIndex++, String.valueOf(c)) + .setRank(active.indexOf(c)) + .setSection(section) .setStableIndex(-1); } + clearInvocations(mStabilityManager); + dispatchBuild(); StringBuilder resultSb = new StringBuilder(); for (int i = 0; i < expected.length(); i++) { @@ -2364,6 +2488,9 @@ public class ShadeListBuilderTest extends SysuiTestCase { assertEquals("visible [" + visible + "] active [" + active + "]", expected, resultSb.toString()); mEntrySet.clear(); + + verify(mStabilityManager, isOrderedCorrectly ? never() : times(1)) + .onEntryReorderSuppressed(); } private int nextId(String packageName) { diff --git a/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/listbuilder/SemiStableSortTest.kt b/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/listbuilder/SemiStableSortTest.kt new file mode 100644 index 000000000000..1cdd023dd01c --- /dev/null +++ b/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/listbuilder/SemiStableSortTest.kt @@ -0,0 +1,210 @@ +/* + * Copyright (C) 2022 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.android.systemui.statusbar.notification.collection.listbuilder + +import android.testing.AndroidTestingRunner +import android.testing.TestableLooper.RunWithLooper +import android.util.Log +import androidx.test.filters.SmallTest +import com.android.systemui.SysuiTestCase +import org.junit.Assert.assertFalse +import org.junit.Assert.assertTrue +import org.junit.Before +import org.junit.Test +import org.junit.runner.RunWith + +@SmallTest +@RunWith(AndroidTestingRunner::class) +@RunWithLooper +class SemiStableSortTest : SysuiTestCase() { + + var shuffleInput: Boolean = false + var testStabilizeTo: Boolean = false + var sorter: SemiStableSort? = null + + @Before + fun setUp() { + shuffleInput = false + sorter = null + } + + private fun stringStabilizeTo( + stableOrder: String, + activeOrder: String, + ): Pair<String, Boolean> { + val actives = activeOrder.toMutableList() + val result = mutableListOf<Char>() + return (sorter ?: SemiStableSort()) + .stabilizeTo( + actives, + { ch -> stableOrder.indexOf(ch).takeIf { it >= 0 } }, + result, + ) + .let { ordered -> result.joinToString("") to ordered } + } + + private fun stringSort( + stableOrder: String, + activeOrder: String, + ): Pair<String, Boolean> { + val actives = activeOrder.toMutableList() + if (shuffleInput) { + actives.shuffle() + } + return (sorter ?: SemiStableSort()) + .sort( + actives, + { ch -> stableOrder.indexOf(ch).takeIf { it >= 0 } }, + compareBy { activeOrder.indexOf(it) }, + ) + .let { ordered -> actives.joinToString("") to ordered } + } + + private fun testCase( + stableOrder: String, + activeOrder: String, + expected: String, + expectOrdered: Boolean, + ) { + val (mergeResult, ordered) = + if (testStabilizeTo) stringStabilizeTo(stableOrder, activeOrder) + else stringSort(stableOrder, activeOrder) + val resultPass = expected == mergeResult + val orderedPass = ordered == expectOrdered + val pass = resultPass && orderedPass + val resultSuffix = + if (resultPass) "result=$expected" else "expected=$expected got=$mergeResult" + val orderedSuffix = + if (orderedPass) "ordered=$ordered" else "expected ordered to be $expectOrdered" + val readableResult = "stable=$stableOrder active=$activeOrder $resultSuffix $orderedSuffix" + Log.d("SemiStableSortTest", "${if (pass) "PASS" else "FAIL"}: $readableResult") + if (!pass) { + throw AssertionError("Test case failed: $readableResult") + } + } + + private fun runAllTestCases() { + // No input or output + testCase("", "", "", true) + // Remove everything + testCase("ABCDEFG", "", "", true) + // Literally no changes + testCase("ABCDEFG", "ABCDEFG", "ABCDEFG", true) + + // No stable order + testCase("", "ABCDEFG", "ABCDEFG", true) + + // F moved after A, and... + testCase("ABCDEFG", "AFBCDEG", "ABCDEFG", false) // No other changes + testCase("ABCDEFG", "AXFBCDEG", "AXBCDEFG", false) // Insert X before F + testCase("ABCDEFG", "AFXBCDEG", "AXBCDEFG", false) // Insert X after F + testCase("ABCDEFG", "AFBCDEXG", "ABCDEFXG", false) // Insert X where F was + + // B moved after F, and... + testCase("ABCDEFG", "ACDEFBG", "ABCDEFG", false) // No other changes + testCase("ABCDEFG", "ACDEFXBG", "ABCDEFXG", false) // Insert X before B + testCase("ABCDEFG", "ACDEFBXG", "ABCDEFXG", false) // Insert X after B + testCase("ABCDEFG", "AXCDEFBG", "AXBCDEFG", false) // Insert X where B was + + // Swap F and B, and... + testCase("ABCDEFG", "AFCDEBG", "ABCDEFG", false) // No other changes + testCase("ABCDEFG", "AXFCDEBG", "AXBCDEFG", false) // Insert X before F + testCase("ABCDEFG", "AFXCDEBG", "AXBCDEFG", false) // Insert X after F + testCase("ABCDEFG", "AFCXDEBG", "AXBCDEFG", false) // Insert X between CD (Alt: ABCXDEFG) + testCase("ABCDEFG", "AFCDXEBG", "ABCDXEFG", false) // Insert X between DE (Alt: ABCDEFXG) + testCase("ABCDEFG", "AFCDEXBG", "ABCDEFXG", false) // Insert X before B + testCase("ABCDEFG", "AFCDEBXG", "ABCDEFXG", false) // Insert X after B + + // Remove a bunch of entries at once + testCase("ABCDEFGHIJKL", "ACEGHI", "ACEGHI", true) + + // Remove a bunch of entries and scramble + testCase("ABCDEFGHIJKL", "GCEHAI", "ACEGHI", false) + + // Add a bunch of entries at once + testCase("ABCDEFG", "AVBWCXDYZEFG", "AVBWCXDYZEFG", true) + + // Add a bunch of entries and reverse originals + // NOTE: Some of these don't have obviously correct answers + testCase("ABCDEFG", "GFEBCDAVWXYZ", "ABCDEFGVWXYZ", false) // appended + testCase("ABCDEFG", "VWXYZGFEBCDA", "VWXYZABCDEFG", false) // prepended + testCase("ABCDEFG", "GFEBVWXYZCDA", "ABCDEFGVWXYZ", false) // closer to back: append + testCase("ABCDEFG", "GFEVWXYZBCDA", "VWXYZABCDEFG", false) // closer to front: prepend + testCase("ABCDEFG", "GFEVWBXYZCDA", "VWABCDEFGXYZ", false) // split new entries + + // Swap 2 pairs ("*BC*NO*"->"*NO*CB*"), remove EG, add UVWXYZ throughout + testCase("ABCDEFGHIJKLMNOP", "AUNOVDFHWXIJKLMYCBZP", "AUVBCDFHWXIJKLMNOYZP", false) + } + + @Test + fun testSort() { + testStabilizeTo = false + shuffleInput = false + sorter = null + runAllTestCases() + } + + @Test + fun testSortWithSingleInstance() { + testStabilizeTo = false + shuffleInput = false + sorter = SemiStableSort() + runAllTestCases() + } + + @Test + fun testSortWithShuffledInput() { + testStabilizeTo = false + shuffleInput = true + sorter = null + runAllTestCases() + } + + @Test + fun testStabilizeTo() { + testStabilizeTo = true + sorter = null + runAllTestCases() + } + + @Test + fun testStabilizeToWithSingleInstance() { + testStabilizeTo = true + sorter = SemiStableSort() + runAllTestCases() + } + + @Test + fun testIsSorted() { + val intCmp = Comparator<Int> { x, y -> Integer.compare(x, y) } + SemiStableSort.apply { + assertTrue(emptyList<Int>().isSorted(intCmp)) + assertTrue(listOf(1).isSorted(intCmp)) + assertTrue(listOf(1, 2).isSorted(intCmp)) + assertTrue(listOf(1, 2, 3).isSorted(intCmp)) + assertTrue(listOf(1, 2, 3, 4).isSorted(intCmp)) + assertTrue(listOf(1, 2, 3, 4, 5).isSorted(intCmp)) + assertTrue(listOf(1, 1, 1, 1, 1).isSorted(intCmp)) + assertTrue(listOf(1, 1, 2, 2, 3, 3).isSorted(intCmp)) + assertFalse(listOf(2, 1).isSorted(intCmp)) + assertFalse(listOf(2, 1, 2).isSorted(intCmp)) + assertFalse(listOf(1, 2, 1).isSorted(intCmp)) + assertFalse(listOf(1, 2, 3, 2, 5).isSorted(intCmp)) + assertFalse(listOf(5, 2, 3, 4, 5).isSorted(intCmp)) + assertFalse(listOf(1, 2, 3, 4, 1).isSorted(intCmp)) + } + } +} diff --git a/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/listbuilder/ShadeListBuilderHelperTest.kt b/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/listbuilder/ShadeListBuilderHelperTest.kt new file mode 100644 index 000000000000..20369546d68a --- /dev/null +++ b/packages/SystemUI/tests/src/com/android/systemui/statusbar/notification/collection/listbuilder/ShadeListBuilderHelperTest.kt @@ -0,0 +1,76 @@ +/* + * Copyright (C) 2022 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package com.android.systemui.statusbar.notification.collection.listbuilder + +import android.testing.AndroidTestingRunner +import android.testing.TestableLooper.RunWithLooper +import androidx.test.filters.SmallTest +import com.android.systemui.SysuiTestCase +import com.android.systemui.statusbar.notification.collection.listbuilder.ShadeListBuilderHelper.getContiguousSubLists +import com.google.common.truth.Truth.assertThat +import org.junit.Test +import org.junit.runner.RunWith + +@SmallTest +@RunWith(AndroidTestingRunner::class) +@RunWithLooper +class ShadeListBuilderHelperTest : SysuiTestCase() { + + @Test + fun testGetContiguousSubLists() { + assertThat(getContiguousSubLists("AAAAAA".toList()) { it }) + .containsExactly( + listOf('A', 'A', 'A', 'A', 'A', 'A'), + ) + .inOrder() + assertThat(getContiguousSubLists("AAABBB".toList()) { it }) + .containsExactly( + listOf('A', 'A', 'A'), + listOf('B', 'B', 'B'), + ) + .inOrder() + assertThat(getContiguousSubLists("AAABAA".toList()) { it }) + .containsExactly( + listOf('A', 'A', 'A'), + listOf('B'), + listOf('A', 'A'), + ) + .inOrder() + assertThat(getContiguousSubLists("AAABAA".toList(), minLength = 2) { it }) + .containsExactly( + listOf('A', 'A', 'A'), + listOf('A', 'A'), + ) + .inOrder() + assertThat(getContiguousSubLists("AAABBBBCCDEEE".toList()) { it }) + .containsExactly( + listOf('A', 'A', 'A'), + listOf('B', 'B', 'B', 'B'), + listOf('C', 'C'), + listOf('D'), + listOf('E', 'E', 'E'), + ) + .inOrder() + assertThat(getContiguousSubLists("AAABBBBCCDEEE".toList(), minLength = 2) { it }) + .containsExactly( + listOf('A', 'A', 'A'), + listOf('B', 'B', 'B', 'B'), + listOf('C', 'C'), + listOf('E', 'E', 'E'), + ) + .inOrder() + } +} |