Honor the sort and group keys for notification ranking.

Sort notifications naturally, then move group childen to be next their proxy.
The group proxy is the summary, or if no summary exists, the lowest-ranked
member of the group is chosen as the proxy.

Notifications with a sortKey but no group and placed into a synthetic
group that consists of all notifications from that package and user in
the same priority bucket that also have sortKeys.

Bug: 15190903
Change-Id: I377ed65b9592079446da4a4189f5ab49d28630ec

6 files changed, 296 insertions, 21 deletions

diff --git a/core/java/android/service/notification/StatusBarNotification.java b/core/java/android/service/notification/StatusBarNotification.java
index e7cdc4e..e5a5292 100644
--- a/core/java/android/service/notification/StatusBarNotification.java
+++ b/core/java/android/service/notification/StatusBarNotification.java
@@ -30,6 +30,7 @@ public class StatusBarNotification implements Parcelable {
     private final int id;
     private final String tag;
     private final String key;
+    private final String groupKey;
 
     private final int uid;
     private final String opPkg;
@@ -65,6 +66,7 @@ public class StatusBarNotification implements Parcelable {
         this.notification.setUser(user);
         this.postTime = postTime;
         this.key = key();
+        this.groupKey = groupKey();
     }
 
     public StatusBarNotification(Parcel in) {
@@ -84,12 +86,26 @@ public class StatusBarNotification implements Parcelable {
         this.notification.setUser(this.user);
         this.postTime = in.readLong();
         this.key = key();
+        this.groupKey = groupKey();
     }
 
     private String key() {
         return user.getIdentifier() + "|" + pkg + "|" + id + "|" + tag + "|" + uid;
     }
 
+    private String groupKey() {
+        final String group = getNotification().getGroup();
+        final String sortKey = getNotification().getSortKey();
+        if (group == null && sortKey == null) {
+            // a group of one
+            return key;
+        }
+        return user.getIdentifier() + "|" + pkg + "|" +
+                (group == null
+                        ? "p:" + notification.priority
+                        : "g:" + group);
+    }
+
     public void writeToParcel(Parcel out, int flags) {
         out.writeString(this.pkg);
         out.writeString(this.opPkg);
@@ -240,4 +256,11 @@ public class StatusBarNotification implements Parcelable {
     public String getKey() {
         return key;
     }
+
+    /**
+     * A key that indicates the group with which this message ranks.
+     */
+    public String getGroupKey() {
+        return groupKey;
+    }
 }
diff --git a/services/core/java/com/android/server/notification/GroupedNotificationComparator.java b/services/core/java/com/android/server/notification/GroupedNotificationComparator.java
new file mode 100644
index 0000000..608d55c
--- /dev/null
+++ b/services/core/java/com/android/server/notification/GroupedNotificationComparator.java
@@ -0,0 +1,57 @@
+/*
+ * Copyright (C) 2014 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.server.notification;
+
+import android.text.TextUtils;
+import android.util.Log;
+
+/**
+ * Sorts notifications, accounting for groups and sort keys.
+ */
+public class GroupedNotificationComparator extends NotificationComparator {
+    private static final String TAG = "GroupedNotificationComparator";
+
+    @Override
+    public int compare(NotificationRecord left, NotificationRecord right) {
+        // "recently intrusive" is an ad hoc group that temporarily claims noisy notifications
+        if (left.isRecentlyIntrusive() != right.isRecentlyIntrusive()) {
+            return left.isRecentlyIntrusive() ? -1 : 1;
+        }
+
+        final NotificationRecord leftProxy = left.getRankingProxy();
+        if (leftProxy == null) {
+            throw new RuntimeException("left proxy cannot be null: " + left.getKey());
+        }
+        final NotificationRecord rightProxy = right.getRankingProxy();
+        if (rightProxy == null) {
+            throw new RuntimeException("right proxy cannot be null: " + right.getKey());
+        }
+        final String leftSortKey = left.getNotification().getSortKey();
+        final String rightSortKey = right.getNotification().getSortKey();
+        if (leftProxy != rightProxy) {
+            // between groups, compare proxies
+            return Integer.compare(leftProxy.getAuthoritativeRank(),
+                    rightProxy.getAuthoritativeRank());
+        } else if (TextUtils.isEmpty(leftSortKey) || TextUtils.isEmpty(rightSortKey)) {
+            // missing sort keys, use prior rank
+            return Integer.compare(left.getAuthoritativeRank(),
+                    right.getAuthoritativeRank());
+        } else {
+            // use sort keys within group
+            return leftSortKey.compareTo(rightSortKey);
+        }
+    }
+}
diff --git a/services/core/java/com/android/server/notification/NotificationComparator.java b/services/core/java/com/android/server/notification/NotificationComparator.java
index 0546a55..ec81fd2 100644
--- a/services/core/java/com/android/server/notification/NotificationComparator.java
+++ b/services/core/java/com/android/server/notification/NotificationComparator.java
@@ -18,35 +18,35 @@ package com.android.server.notification;
 import java.util.Comparator;
 
 /**
- * Sorts notificaitons into attention-relelvant order.
+ * Sorts notifications individually into attention-relelvant order.
  */
 public class NotificationComparator
         implements Comparator<NotificationRecord> {
 
     @Override
-    public int compare(NotificationRecord lhs, NotificationRecord rhs) {
-        if (lhs.isRecentlyIntrusive() != rhs.isRecentlyIntrusive()) {
-            return lhs.isRecentlyIntrusive() ? -1 : 1;
-        }
-        final int leftPackagePriority = lhs.getPackagePriority();
-        final int rightPackagePriority = rhs.getPackagePriority();
+    public int compare(NotificationRecord left, NotificationRecord right) {
+        final int leftPackagePriority = left.getPackagePriority();
+        final int rightPackagePriority = right.getPackagePriority();
         if (leftPackagePriority != rightPackagePriority) {
             // by priority, high to low
             return -1 * Integer.compare(leftPackagePriority, rightPackagePriority);
         }
-        final int leftScore = lhs.sbn.getScore();
-        final int rightScore = rhs.sbn.getScore();
+
+        final int leftScore = left.sbn.getScore();
+        final int rightScore = right.sbn.getScore();
         if (leftScore != rightScore) {
             // by priority, high to low
             return -1 * Integer.compare(leftScore, rightScore);
         }
-        final float leftPeple = lhs.getContactAffinity();
-        final float rightPeople = rhs.getContactAffinity();
-        if (leftPeple != rightPeople) {
+
+        final float leftPeople = left.getContactAffinity();
+        final float rightPeople = right.getContactAffinity();
+        if (leftPeople != rightPeople) {
             // by contact proximity, close to far
-            return -1 * Float.compare(leftPeple, rightPeople);
+            return -1 * Float.compare(leftPeople, rightPeople);
         }
+
         // then break ties by time, most recent first
-        return -1 * Long.compare(lhs.getRankingTimeMs(), rhs.getRankingTimeMs());
+        return -1 * Long.compare(left.getRankingTimeMs(), right.getRankingTimeMs());
     }
 }
diff --git a/services/core/java/com/android/server/notification/NotificationRecord.java b/services/core/java/com/android/server/notification/NotificationRecord.java
index 088b813..57f3e2d 100644
--- a/services/core/java/com/android/server/notification/NotificationRecord.java
+++ b/services/core/java/com/android/server/notification/NotificationRecord.java
@@ -21,6 +21,7 @@ import android.content.pm.PackageManager.NameNotFoundException;
 import android.content.res.Resources;
 import android.graphics.Bitmap;
 import android.service.notification.StatusBarNotification;
+import com.android.internal.annotations.VisibleForTesting;
 
 import java.io.PrintWriter;
 import java.lang.reflect.Array;
@@ -60,7 +61,12 @@ public final class NotificationRecord {
     public boolean isUpdate;
     private int mPackagePriority;
 
-    NotificationRecord(StatusBarNotification sbn, int score)
+    // The record that ranking should use for comparisons outside the group.
+    private NotificationRecord mRankingProxy;
+    private int mAuthoritativeRank;
+
+    @VisibleForTesting
+    public NotificationRecord(StatusBarNotification sbn, int score)
     {
         this.sbn = sbn;
         this.score = score;
@@ -73,7 +79,9 @@ public final class NotificationRecord {
         mRecentlyIntrusive = previous.mRecentlyIntrusive;
         mPackagePriority = previous.mPackagePriority;
         mIntercept = previous.mIntercept;
+        mRankingProxy = previous.mRankingProxy;
         mRankingTimeMs = calculateRankingTimeMs(previous.getRankingTimeMs());
+        // Don't copy mGroupKey, recompute it, in case it has changed
     }
 
     public Notification getNotification() { return sbn.getNotification(); }
@@ -89,6 +97,7 @@ public final class NotificationRecord {
                 + " / " + idDebugString(baseContext, sbn.getPackageName(), notification.icon));
         pw.println(prefix + "  pri=" + notification.priority + " score=" + sbn.getScore());
         pw.println(prefix + "  key=" + sbn.getKey());
+        pw.println(prefix + "  groupKey=" + getGroupKey());
         pw.println(prefix + "  contentIntent=" + notification.contentIntent);
         pw.println(prefix + "  deleteIntent=" + notification.deleteIntent);
         pw.println(prefix + "  tickerText=" + notification.tickerText);
@@ -145,6 +154,7 @@ public final class NotificationRecord {
         pw.println(prefix + "  mRecentlyIntrusive=" + mRecentlyIntrusive);
         pw.println(prefix + "  mPackagePriority=" + mPackagePriority);
         pw.println(prefix + "  mIntercept=" + mIntercept);
+        pw.println(prefix + "  mRankingProxy=" + getRankingProxy().getKey());
         pw.println(prefix + "  mRankingTimeMs=" + mRankingTimeMs);
     }
 
@@ -241,4 +251,24 @@ public final class NotificationRecord {
         }
         return sbn.getPostTime();
     }
+
+    public NotificationRecord getRankingProxy() {
+        return mRankingProxy;
+    }
+
+    public void setRankingProxy(NotificationRecord proxy) {
+        mRankingProxy = proxy;
+    }
+
+    public void setAuthoritativeRank(int authoritativeRank) {
+        mAuthoritativeRank = authoritativeRank;
+    }
+
+    public int getAuthoritativeRank() {
+        return mAuthoritativeRank;
+    }
+
+    public String getGroupKey() {
+        return sbn.getGroupKey();
+    }
 }
diff --git a/services/core/java/com/android/server/notification/RankingHelper.java b/services/core/java/com/android/server/notification/RankingHelper.java
index fc03c17..d59e17b 100644
--- a/services/core/java/com/android/server/notification/RankingHelper.java
+++ b/services/core/java/com/android/server/notification/RankingHelper.java
@@ -17,12 +17,12 @@ package com.android.server.notification;
 
 import android.app.Notification;
 import android.content.Context;
+import android.net.Uri;
 import android.os.Handler;
 import android.os.Message;
 import android.os.UserHandle;
 import android.text.TextUtils;
 import android.util.ArrayMap;
-import android.util.Log;
 import android.util.Slog;
 import android.util.SparseIntArray;
 import org.xmlpull.v1.XmlPullParser;
@@ -49,13 +49,13 @@ public class RankingHelper implements RankingConfig {
     private static final String ATT_UID = "uid";
     private static final String ATT_PRIORITY = "priority";
 
-    private static final String VALUE_HIGH = "high";
-
     private final NotificationSignalExtractor[] mSignalExtractors;
-    private final NotificationComparator mRankingComparator = new NotificationComparator();
+    private final NotificationComparator mPreliminaryComparator = new NotificationComparator();
+    private final NotificationComparator mFinalComparator = new GroupedNotificationComparator();
 
     // Package name to uid, to priority. Would be better as Table<String, Int, Int>
     private final ArrayMap<String, SparseIntArray> mPackagePriorities;
+    private final ArrayMap<String, NotificationRecord> mProxyByGroupTmp;
 
     private final Context mContext;
     private final Handler mRankingHandler;
@@ -83,6 +83,7 @@ public class RankingHelper implements RankingConfig {
                 Slog.w(TAG, "Problem accessing extractor " + extractorNames[i] + ".", e);
             }
         }
+        mProxyByGroupTmp = new ArrayMap<String, NotificationRecord>();
     }
 
     public void extractSignals(NotificationRecord r) {
@@ -166,11 +167,39 @@ public class RankingHelper implements RankingConfig {
     }
 
     public void sort(ArrayList<NotificationRecord> notificationList) {
-        Collections.sort(notificationList, mRankingComparator);
+        final int N = notificationList.size();
+        // clear group proxies
+        for (int i = N - 1; i >= 0; i--) {
+            notificationList.get(i).setRankingProxy(null);
+        }
+
+        // rank each record individually
+        Collections.sort(notificationList, mPreliminaryComparator);
+
+        // record inidivdual ranking result and nominate proxies for each group
+        for (int i = N - 1; i >= 0; i--) {
+            final NotificationRecord record = notificationList.get(i);
+            record.setAuthoritativeRank(i);
+            final String groupKey = record.getGroupKey();
+            boolean isGroupSummary = record.getNotification().getGroup() != null
+                    && (record.getNotification().flags & Notification.FLAG_GROUP_SUMMARY) != 0;
+            if (isGroupSummary || mProxyByGroupTmp.get(groupKey) == null) {
+                mProxyByGroupTmp.put(groupKey, record);
+            }
+        }
+        // assign nominated proxies to each notification
+        for (int i = 0; i < N; i++) {
+            final NotificationRecord record = notificationList.get(i);
+            record.setRankingProxy(mProxyByGroupTmp.get(record.getGroupKey()));
+        }
+        // Do a second ranking pass, using group proxies
+        Collections.sort(notificationList, mFinalComparator);
+
+        mProxyByGroupTmp.clear();
     }
 
     public int indexOf(ArrayList<NotificationRecord> notificationList, NotificationRecord target) {
-        return Collections.binarySearch(notificationList, target, mRankingComparator);
+        return Collections.binarySearch(notificationList, target, mFinalComparator);
     }
 
     private static int safeInt(XmlPullParser parser, String att, int defValue) {
diff --git a/services/tests/servicestests/src/com/android/server/notification/RankingHelperTest.java b/services/tests/servicestests/src/com/android/server/notification/RankingHelperTest.java
new file mode 100644
index 0000000..3cc04e8
--- /dev/null
+++ b/services/tests/servicestests/src/com/android/server/notification/RankingHelperTest.java
@@ -0,0 +1,136 @@
+/*
+ * Copyright (C) 2014 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.server.notification;
+
+import android.app.Notification;
+import android.os.UserHandle;
+import android.service.notification.StatusBarNotification;
+import android.test.AndroidTestCase;
+import android.test.suitebuilder.annotation.SmallTest;
+
+import java.util.ArrayList;
+
+public class RankingHelperTest extends AndroidTestCase {
+
+    private Notification mNotiGroupGSortA;
+    private Notification mNotiGroupGSortB;
+    private Notification mNotiNoGroup;
+    private Notification mNotiNoGroup2;
+    private Notification mNotiNoGroupSortA;
+    private NotificationRecord mRecordGroupGSortA;
+    private NotificationRecord mRecordGroupGSortB;
+    private NotificationRecord mRecordNoGroup;
+    private NotificationRecord mRecordNoGroup2;
+    private NotificationRecord mRecordNoGroupSortA;
+    private RankingHelper mHelper;
+
+    @Override
+    public void setUp() {
+        UserHandle user = UserHandle.ALL;
+
+        mHelper = new RankingHelper(getContext(), null, new String[0]);
+
+        mNotiGroupGSortA = new Notification.Builder(getContext())
+                .setContentTitle("A")
+                .setGroup("G")
+                .setSortKey("A")
+                .setWhen(1205)
+                .build();
+        mRecordGroupGSortA = new NotificationRecord(new StatusBarNotification(
+                "package", "package", 1, null, 0, 0, 0, mNotiGroupGSortA, user), 0);
+
+        mNotiGroupGSortB = new Notification.Builder(getContext())
+                .setContentTitle("B")
+                .setGroup("G")
+                .setSortKey("B")
+                .setWhen(1200)
+                .build();
+        mRecordGroupGSortB = new NotificationRecord(new StatusBarNotification(
+                "package", "package", 1, null, 0, 0, 0, mNotiGroupGSortB, user), 0);
+
+        mNotiNoGroup = new Notification.Builder(getContext())
+                .setContentTitle("C")
+                .setWhen(1201)
+                .build();
+        mRecordNoGroup = new NotificationRecord(new StatusBarNotification(
+                "package", "package", 1, null, 0, 0, 0, mNotiNoGroup, user), 0);
+
+        mNotiNoGroup2 = new Notification.Builder(getContext())
+                .setContentTitle("D")
+                .setWhen(1202)
+                .build();
+        mRecordNoGroup2 = new NotificationRecord(new StatusBarNotification(
+                "package", "package", 1, null, 0, 0, 0, mNotiNoGroup2, user), 0);
+
+        mNotiNoGroupSortA = new Notification.Builder(getContext())
+                .setContentTitle("E")
+                .setWhen(1201)
+                .setSortKey("A")
+                .build();
+        mRecordNoGroupSortA = new NotificationRecord(new StatusBarNotification(
+                "package", "package", 1, null, 0, 0, 0, mNotiNoGroupSortA, user), 0);
+    }
+
+    @SmallTest
+    public void testFindAfterRankingWithASplitGroup() throws Exception {
+        ArrayList<NotificationRecord> notificationList = new ArrayList<NotificationRecord>(3);
+        notificationList.add(mRecordGroupGSortA);
+        notificationList.add(mRecordGroupGSortB);
+        notificationList.add(mRecordNoGroup);
+        notificationList.add(mRecordNoGroupSortA);
+        mHelper.sort(notificationList);
+        assertTrue(mHelper.indexOf(notificationList, mRecordGroupGSortA) >= 0);
+        assertTrue(mHelper.indexOf(notificationList, mRecordGroupGSortB) >= 0);
+        assertTrue(mHelper.indexOf(notificationList, mRecordNoGroup) >= 0);
+        assertTrue(mHelper.indexOf(notificationList, mRecordNoGroupSortA) >= 0);
+    }
+
+    @SmallTest
+    public void testSortShouldNotThrowWithPlainNotifications() throws Exception {
+        ArrayList<NotificationRecord> notificationList = new ArrayList<NotificationRecord>(2);
+        notificationList.add(mRecordNoGroup);
+        notificationList.add(mRecordNoGroup2);
+        mHelper.sort(notificationList);
+    }
+
+    @SmallTest
+    public void testSortShouldNotThrowOneSorted() throws Exception {
+        ArrayList<NotificationRecord> notificationList = new ArrayList<NotificationRecord>(2);
+        notificationList.add(mRecordNoGroup);
+        notificationList.add(mRecordNoGroupSortA);
+        mHelper.sort(notificationList);
+    }
+
+    @SmallTest
+    public void testSortShouldNotThrowOneNotification() throws Exception {
+        ArrayList<NotificationRecord> notificationList = new ArrayList<NotificationRecord>(1);
+        notificationList.add(mRecordNoGroup);
+        mHelper.sort(notificationList);
+    }
+
+    @SmallTest
+    public void testSortShouldNotThrowOneSortKey() throws Exception {
+        ArrayList<NotificationRecord> notificationList = new ArrayList<NotificationRecord>(1);
+        notificationList.add(mRecordGroupGSortB);
+        mHelper.sort(notificationList);
+    }
+
+    @SmallTest
+    public void testSortShouldNotThrowOnEmptyList() throws Exception {
+        ArrayList<NotificationRecord> notificationList = new ArrayList<NotificationRecord>();
+        mHelper.sort(notificationList);
+    }
+}