diff --git a/services/core/java/com/android/server/pm/ShortcutBackupAgent.java b/services/core/java/com/android/server/pm/ShortcutBackupAgent.java
new file mode 100644
index 0000000..a0fbc37
--- /dev/null
+++ b/services/core/java/com/android/server/pm/ShortcutBackupAgent.java
@@ -0,0 +1,37 @@
+/*
+ * Copyright (C) 2016 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.pm;
+
+import android.app.backup.BlobBackupHelper;
+
+public class ShortcutBackupAgent extends BlobBackupHelper {
+    private static final String TAG = "ShortcutBackupAgent";
+    private static final int BLOB_VERSION = 1;
+
+    public ShortcutBackupAgent(int currentBlobVersion, String... keys) {
+        super(currentBlobVersion, keys);
+    }
+
+    @Override
+    protected byte[] getBackupPayload(String key) {
+        throw new RuntimeException("not implemented yet"); // todo
+    }
+
+    @Override
+    protected void applyRestoredPayload(String key, byte[] payload) {
+        throw new RuntimeException("not implemented yet"); // todo
+    }
+}
diff --git a/services/core/java/com/android/server/pm/ShortcutLauncher.java b/services/core/java/com/android/server/pm/ShortcutLauncher.java
index f1920c7..740a8f7 100644
--- a/services/core/java/com/android/server/pm/ShortcutLauncher.java
+++ b/services/core/java/com/android/server/pm/ShortcutLauncher.java
@@ -32,7 +32,7 @@
 /**
  * Launcher information used by {@link ShortcutService}.
  */
-class ShortcutLauncher {
+class ShortcutLauncher implements ShortcutPackageItem {
     private static final String TAG = ShortcutService.TAG;
 
     static final String TAG_ROOT = "launcher-pins";
@@ -44,10 +44,10 @@
     private static final String ATTR_PACKAGE_NAME = "package-name";
 
     @UserIdInt
-    final int mUserId;
+    private final int mUserId;
 
     @NonNull
-    final String mPackageName;
+    private final String mPackageName;
 
     /**
      * Package name -> IDs.
@@ -59,6 +59,16 @@
         mPackageName = packageName;
     }
 
+    @UserIdInt
+    public int getUserId() {
+        return mUserId;
+    }
+
+    @NonNull
+    public String getPackageName() {
+        return mPackageName;
+    }
+
     public void pinShortcuts(@NonNull ShortcutService s, @NonNull String packageName,
             @NonNull List<String> ids) {
         final int idSize = ids.size();
@@ -103,7 +113,7 @@
     /**
      * Persist.
      */
-    public void saveToXml(XmlSerializer out) throws IOException {
+    public void saveToXml(XmlSerializer out, boolean forBackup) throws IOException {
         final int size = mPinnedShortcuts.size();
         if (size == 0) {
             return; // Nothing to write.
@@ -190,7 +200,7 @@
 
             for (int j = 0; j < idSize; j++) {
                 pw.print(prefix);
-                pw.print("    ");
+                pw.print("    Pinned: ");
                 pw.print(ids.valueAt(j));
                 pw.println();
             }
diff --git a/services/core/java/com/android/server/pm/ShortcutPackage.java b/services/core/java/com/android/server/pm/ShortcutPackage.java
index d614251..359ea1c 100644
--- a/services/core/java/com/android/server/pm/ShortcutPackage.java
+++ b/services/core/java/com/android/server/pm/ShortcutPackage.java
@@ -41,7 +41,7 @@
 /**
  * Package information used by {@link ShortcutService}.
  */
-class ShortcutPackage {
+class ShortcutPackage implements ShortcutPackageItem {
     private static final String TAG = ShortcutService.TAG;
 
     static final String TAG_ROOT = "package";
@@ -64,10 +64,10 @@
     private static final String ATTR_BITMAP_PATH = "bitmap-path";
 
     @UserIdInt
-    final int mUserId;
+    private final int mUserId;
 
     @NonNull
-    final String mPackageName;
+    private final String mPackageName;
 
     /**
      * All the shortcuts from the package, keyed on IDs.
@@ -94,6 +94,16 @@
         mPackageName = packageName;
     }
 
+    @UserIdInt
+    public int getUserId() {
+        return mUserId;
+    }
+
+    @NonNull
+    public String getPackageName() {
+        return mPackageName;
+    }
+
     @Nullable
     public ShortcutInfo findShortcutById(String id) {
         return mShortcuts.get(id);
@@ -381,7 +391,8 @@
         pw.println(")");
     }
 
-    public void saveToXml(@NonNull XmlSerializer out) throws IOException, XmlPullParserException {
+    public void saveToXml(@NonNull XmlSerializer out, boolean forBackup)
+            throws IOException, XmlPullParserException {
         final int size = mShortcuts.size();
 
         if (size == 0 && mApiCallCount == 0) {
@@ -396,14 +407,19 @@
         ShortcutService.writeAttr(out, ATTR_LAST_RESET, mLastResetTime);
 
         for (int j = 0; j < size; j++) {
-            saveShortcut(out, mShortcuts.valueAt(j));
+            saveShortcut(out, mShortcuts.valueAt(j), forBackup);
         }
 
         out.endTag(null, TAG_ROOT);
     }
 
-    private static void saveShortcut(XmlSerializer out, ShortcutInfo si)
+    private static void saveShortcut(XmlSerializer out, ShortcutInfo si, boolean forBackup)
             throws IOException, XmlPullParserException {
+        if (forBackup) {
+            if (!si.isPinned()) {
+                return; // Backup only pinned icons.
+            }
+        }
         out.startTag(null, TAG_SHORTCUT);
         ShortcutService.writeAttr(out, ATTR_ID, si.getId());
         // writeAttr(out, "package", si.getPackageName()); // not needed
@@ -414,9 +430,17 @@
         ShortcutService.writeAttr(out, ATTR_WEIGHT, si.getWeight());
         ShortcutService.writeAttr(out, ATTR_TIMESTAMP,
                 si.getLastChangedTimestamp());
-        ShortcutService.writeAttr(out, ATTR_FLAGS, si.getFlags());
-        ShortcutService.writeAttr(out, ATTR_ICON_RES, si.getIconResourceId());
-        ShortcutService.writeAttr(out, ATTR_BITMAP_PATH, si.getBitmapPath());
+        if (forBackup) {
+            // Don't write icon information.  Also drop the dynamic flag.
+            ShortcutService.writeAttr(out, ATTR_FLAGS,
+                    si.getFlags() &
+                            ~(ShortcutInfo.FLAG_HAS_ICON_FILE | ShortcutInfo.FLAG_HAS_ICON_RES
+                            | ShortcutInfo.FLAG_DYNAMIC));
+        } else {
+            ShortcutService.writeAttr(out, ATTR_FLAGS, si.getFlags());
+            ShortcutService.writeAttr(out, ATTR_ICON_RES, si.getIconResourceId());
+            ShortcutService.writeAttr(out, ATTR_BITMAP_PATH, si.getBitmapPath());
+        }
 
         ShortcutService.writeTagExtra(out, TAG_INTENT_EXTRAS,
                 si.getIntentPersistableExtras());
diff --git a/services/core/java/com/android/server/pm/ShortcutPackageInfo.java b/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
new file mode 100644
index 0000000..00ea679
--- /dev/null
+++ b/services/core/java/com/android/server/pm/ShortcutPackageInfo.java
@@ -0,0 +1,292 @@
+/*
+ * Copyright (C) 2016 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.pm;
+
+import android.annotation.NonNull;
+import android.annotation.UserIdInt;
+import android.content.pm.ApplicationInfo;
+import android.content.pm.PackageInfo;
+import android.content.pm.Signature;
+import android.util.Slog;
+
+import com.android.internal.util.Preconditions;
+
+import libcore.io.Base64;
+import libcore.util.HexEncoding;
+
+import org.xmlpull.v1.XmlPullParser;
+import org.xmlpull.v1.XmlPullParserException;
+import org.xmlpull.v1.XmlSerializer;
+
+import java.io.IOException;
+import java.io.PrintWriter;
+import java.security.MessageDigest;
+import java.security.NoSuchAlgorithmException;
+import java.util.ArrayList;
+import java.util.Arrays;
+
+/**
+ * Package information used by {@link android.content.pm.ShortcutManager} for backup / restore.
+ *
+ * TODO: The methods about signature hashes are copied from BackupManagerService, which is not
+ * visible here.  Unify the code.
+ */
+class ShortcutPackageInfo implements ShortcutPackageItem {
+    private static final String TAG = ShortcutService.TAG;
+
+    static final String TAG_ROOT = "package-info";
+    private static final String ATTR_NAME = "name";
+    private static final String ATTR_VERSION = "version";
+    private static final String ATTR_SHADOW = "shadow";
+
+    private static final String TAG_SIGNATURE = "signature";
+    private static final String ATTR_SIGNATURE_HASH = "hash";
+
+    public interface ShortcutPackageInfoHolder {
+        ShortcutPackageInfo getShortcutPackageInfo();
+    }
+
+    private final String mPackageName;
+
+    /**
+     * When true, this package information was restored from the previous device, and the app hasn't
+     * been installed yet.
+     */
+    private boolean mIsShadow;
+    private int mVersionCode;
+    private ArrayList<byte[]> mSigHashes;
+
+    private ShortcutPackageInfo(String packageName, int versionCode, ArrayList<byte[]> sigHashes,
+            boolean isShadow) {
+        mVersionCode = versionCode;
+        mIsShadow = isShadow;
+        mSigHashes = sigHashes;
+        mPackageName = Preconditions.checkNotNull(packageName);
+    }
+
+    @NonNull
+    public String getPackageName() {
+        return mPackageName;
+    }
+
+    public boolean isShadow() {
+        return mIsShadow;
+    }
+
+    public boolean isInstalled() {
+        return !mIsShadow;
+    }
+
+    public void setShadow(boolean shadow) {
+        mIsShadow = shadow;
+    }
+
+    public int getVersionCode() {
+        return mVersionCode;
+    }
+
+    private static byte[] hashSignature(Signature sig) {
+        try {
+            MessageDigest digest = MessageDigest.getInstance("SHA-256");
+            digest.update(sig.toByteArray());
+            return digest.digest();
+        } catch (NoSuchAlgorithmException e) {
+            Slog.w(TAG, "No SHA-256 algorithm found!");
+        }
+        return null;
+    }
+
+    private static ArrayList<byte[]> hashSignatureArray(Signature[] sigs) {
+        if (sigs == null) {
+            return null;
+        }
+
+        ArrayList<byte[]> hashes = new ArrayList<byte[]>(sigs.length);
+        for (Signature s : sigs) {
+            hashes.add(hashSignature(s));
+        }
+        return hashes;
+    }
+
+    private static boolean signaturesMatch(ArrayList<byte[]> storedSigHashes, PackageInfo target) {
+        if (target == null) {
+            return false;
+        }
+
+        // If the target resides on the system partition, we allow it to restore
+        // data from the like-named package in a restore set even if the signatures
+        // do not match.  (Unlike general applications, those flashed to the system
+        // partition will be signed with the device's platform certificate, so on
+        // different phones the same system app will have different signatures.)
+        if ((target.applicationInfo.flags & ApplicationInfo.FLAG_SYSTEM) != 0) {
+            return true;
+        }
+
+        // Allow unsigned apps, but not signed on one device and unsigned on the other
+        // !!! TODO: is this the right policy?
+        Signature[] deviceSigs = target.signatures;
+        if ((storedSigHashes == null || storedSigHashes.size() == 0)
+                && (deviceSigs == null || deviceSigs.length == 0)) {
+            return true;
+        }
+        if (storedSigHashes == null || deviceSigs == null) {
+            return false;
+        }
+
+        // !!! TODO: this demands that every stored signature match one
+        // that is present on device, and does not demand the converse.
+        // Is this this right policy?
+        final int nStored = storedSigHashes.size();
+        final int nDevice = deviceSigs.length;
+
+        // hash each on-device signature
+        ArrayList<byte[]> deviceHashes = new ArrayList<byte[]>(nDevice);
+        for (int i = 0; i < nDevice; i++) {
+            deviceHashes.add(hashSignature(deviceSigs[i]));
+        }
+
+        // now ensure that each stored sig (hash) matches an on-device sig (hash)
+        for (int n = 0; n < nStored; n++) {
+            boolean match = false;
+            final byte[] storedHash = storedSigHashes.get(n);
+            for (int i = 0; i < nDevice; i++) {
+                if (Arrays.equals(storedHash, deviceHashes.get(i))) {
+                    match = true;
+                    break;
+                }
+            }
+            // match is false when no on-device sig matched one of the stored ones
+            if (!match) {
+                return false;
+            }
+        }
+
+        return true;
+    }
+
+    public boolean canRestoreTo(PackageInfo target) {
+        if (target.versionCode < mVersionCode) {
+            Slog.w(TAG, String.format("Package current version %d < backed up version %d",
+                    target.versionCode, mVersionCode));
+            return false;
+        }
+        if (!signaturesMatch(mSigHashes, target)) {
+            Slog.w(TAG, "Package signature mismtach");
+            return false;
+        }
+        return true;
+    }
+
+    public static ShortcutPackageInfo generateForInstalledPackage(
+            ShortcutService s, String packageName, @UserIdInt int userId) {
+        final PackageInfo pi = s.getPackageInfo(packageName, userId, /*signature=*/ true);
+        if (pi.signatures == null || pi.signatures.length == 0) {
+            Slog.e(TAG, "Can't get signatures: package=" + packageName);
+            return null;
+        }
+        final ShortcutPackageInfo ret = new ShortcutPackageInfo(packageName, pi.versionCode,
+                hashSignatureArray(pi.signatures), /* shadow=*/ false);
+
+        return ret;
+    }
+
+    public void refreshAndSave(ShortcutService s, @UserIdInt int userId) {
+        final PackageInfo pi = s.getPackageInfo(mPackageName, userId, /*getSignatures=*/ true);
+        if (pi == null) {
+            Slog.w(TAG, "Package not found: " + mPackageName);
+            return;
+        }
+        mVersionCode = pi.versionCode;
+        mSigHashes = hashSignatureArray(pi.signatures);
+
+        s.scheduleSaveUser(userId);
+    }
+
+    public void saveToXml(XmlSerializer out, boolean forBackup)
+            throws IOException, XmlPullParserException {
+
+        out.startTag(null, TAG_ROOT);
+
+        ShortcutService.writeAttr(out, ATTR_NAME, mPackageName);
+        ShortcutService.writeAttr(out, ATTR_VERSION, mVersionCode);
+        ShortcutService.writeAttr(out, ATTR_SHADOW, mIsShadow);
+
+        for (int i = 0; i < mSigHashes.size(); i++) {
+            out.startTag(null, TAG_SIGNATURE);
+            ShortcutService.writeAttr(out, ATTR_SIGNATURE_HASH, Base64.encode(mSigHashes.get(i)));
+            out.endTag(null, TAG_SIGNATURE);
+        }
+        out.endTag(null, TAG_ROOT);
+    }
+
+    public static ShortcutPackageInfo loadFromXml(XmlPullParser parser)
+            throws IOException, XmlPullParserException {
+
+        final String packageName = ShortcutService.parseStringAttribute(parser, ATTR_NAME);
+        final int versionCode = ShortcutService.parseIntAttribute(parser, ATTR_VERSION);
+        final boolean shadow = ShortcutService.parseBooleanAttribute(parser, ATTR_SHADOW);
+
+        final ArrayList<byte[]> hashes = new ArrayList<>();
+
+
+        final int outerDepth = parser.getDepth();
+        int type;
+        while ((type = parser.next()) != XmlPullParser.END_DOCUMENT
+                && (type != XmlPullParser.END_TAG || parser.getDepth() > outerDepth)) {
+            if (type != XmlPullParser.START_TAG) {
+                continue;
+            }
+            final int depth = parser.getDepth();
+            final String tag = parser.getName();
+            switch (tag) {
+                case TAG_SIGNATURE: {
+                    final String hash = ShortcutService.parseStringAttribute(
+                            parser, ATTR_SIGNATURE_HASH);
+                    hashes.add(Base64.decode(hash.getBytes()));
+                    continue;
+                }
+            }
+            throw ShortcutService.throwForInvalidTag(depth, tag);
+        }
+        return new ShortcutPackageInfo(packageName, versionCode, hashes, shadow);
+    }
+
+    public void dump(ShortcutService s, PrintWriter pw, String prefix) {
+        pw.println();
+
+        pw.print(prefix);
+        pw.print("PackageInfo: ");
+        pw.print(mPackageName);
+        pw.println();
+
+        pw.print(prefix);
+        pw.print("  IsShadow: ");
+        pw.print(mIsShadow);
+        pw.println();
+
+        pw.print(prefix);
+        pw.print("  Version: ");
+        pw.print(mVersionCode);
+        pw.println();
+
+        for (int i = 0; i < mSigHashes.size(); i++) {
+            pw.print(prefix);
+            pw.print("    ");
+            pw.print("SigHash: ");
+            pw.println(HexEncoding.encode(mSigHashes.get(i)));
+        }
+    }
+}
diff --git a/services/core/java/com/android/server/pm/ShortcutPackageItem.java b/services/core/java/com/android/server/pm/ShortcutPackageItem.java
new file mode 100644
index 0000000..526c84d
--- /dev/null
+++ b/services/core/java/com/android/server/pm/ShortcutPackageItem.java
@@ -0,0 +1,31 @@
+/*
+ * Copyright (C) 2016 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.pm;
+
+import android.annotation.NonNull;
+
+import org.xmlpull.v1.XmlPullParserException;
+import org.xmlpull.v1.XmlSerializer;
+
+import java.io.IOException;
+
+public interface ShortcutPackageItem {
+    @NonNull
+    String getPackageName();
+
+    void saveToXml(@NonNull XmlSerializer out, boolean forBackup)
+            throws IOException, XmlPullParserException;
+}
diff --git a/services/core/java/com/android/server/pm/ShortcutService.java b/services/core/java/com/android/server/pm/ShortcutService.java
index 42954f5..0b33ada 100644
--- a/services/core/java/com/android/server/pm/ShortcutService.java
+++ b/services/core/java/com/android/server/pm/ShortcutService.java
@@ -19,13 +19,17 @@
 import android.annotation.Nullable;
 import android.annotation.UserIdInt;
 import android.app.ActivityManager;
+import android.app.AppGlobals;
 import android.content.ComponentName;
 import android.content.ContentProvider;
 import android.content.Context;
 import android.content.Intent;
+import android.content.pm.ApplicationInfo;
+import android.content.pm.IPackageManager;
 import android.content.pm.IShortcutService;
 import android.content.pm.LauncherApps;
 import android.content.pm.LauncherApps.ShortcutQuery;
+import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 import android.content.pm.PackageManager.NameNotFoundException;
 import android.content.pm.PackageManagerInternal;
@@ -55,7 +59,6 @@
 import android.os.UserHandle;
 import android.os.UserManager;
 import android.text.TextUtils;
-import android.text.format.Formatter;
 import android.text.format.Time;
 import android.util.ArrayMap;
 import android.util.ArraySet;
@@ -70,13 +73,13 @@
 import com.android.internal.annotations.VisibleForTesting;
 import com.android.internal.content.PackageMonitor;
 import com.android.internal.os.BackgroundThread;
+import com.android.internal.util.ArrayUtils;
 import com.android.internal.util.FastXmlSerializer;
 import com.android.internal.util.Preconditions;
 import com.android.server.LocalServices;
 import com.android.server.SystemService;
 
 import libcore.io.IoUtils;
-import libcore.util.Objects;
 
 import org.xmlpull.v1.XmlPullParser;
 import org.xmlpull.v1.XmlPullParserException;
@@ -122,6 +125,7 @@
 
     static final boolean DEBUG = false; // STOPSHIP if true
     static final boolean DEBUG_LOAD = false; // STOPSHIP if true
+    static final boolean ENABLE_DEBUG_COMMAND = true; // STOPSHIP if true
 
     @VisibleForTesting
     static final long DEFAULT_RESET_INTERVAL_SEC = 24 * 60 * 60; // 1 day
@@ -249,6 +253,7 @@
 
     private int mSaveDelayMillis;
 
+    private final IPackageManager mIPackageManager;
     private final PackageManagerInternal mPackageManagerInternal;
     private final UserManager mUserManager;
 
@@ -264,6 +269,7 @@
         mContext = Preconditions.checkNotNull(context);
         LocalServices.addService(ShortcutServiceInternal.class, new LocalService());
         mHandler = new Handler(looper);
+        mIPackageManager = AppGlobals.getPackageManager();
         mPackageManagerInternal = LocalServices.getService(PackageManagerInternal.class);
         mUserManager = context.getSystemService(UserManager.class);
 
@@ -319,6 +325,8 @@
         synchronized (mLock) {
             // Preload
             getUserShortcutsLocked(userId);
+
+            cleanupGonePackages(userId);
         }
     }
 
@@ -434,6 +442,10 @@
         return parser.getAttributeValue(null, attribute);
     }
 
+    static boolean parseBooleanAttribute(XmlPullParser parser, String attribute) {
+        return parseLongAttribute(parser, attribute) == 1;
+    }
+
     static int parseIntAttribute(XmlPullParser parser, String attribute) {
         return (int) parseLongAttribute(parser, attribute);
     }
@@ -510,6 +522,12 @@
         writeAttr(out, name, String.valueOf(value));
     }
 
+    static void writeAttr(XmlSerializer out, String name, boolean value) throws IOException {
+        if (value) {
+            writeAttr(out, name, "1");
+        }
+    }
+
     static void writeAttr(XmlSerializer out, String name, ComponentName comp) throws IOException {
         if (comp == null) return;
         writeAttr(out, name, comp.flattenToString());
@@ -616,7 +634,7 @@
             out.setOutput(outs, StandardCharsets.UTF_8.name());
             out.startDocument(null, true);
 
-            getUserShortcutsLocked(userId).saveToXml(out);
+            getUserShortcutsLocked(userId).saveToXml(this, out, /* forBackup= */ false);
 
             out.endDocument();
 
@@ -682,17 +700,17 @@
     }
 
     private void scheduleSaveBaseState() {
-        scheduleSave(UserHandle.USER_NULL); // Special case -- use USER_NULL for base state.
+        scheduleSaveInner(UserHandle.USER_NULL); // Special case -- use USER_NULL for base state.
     }
 
     void scheduleSaveUser(@UserIdInt int userId) {
-        scheduleSave(userId);
+        scheduleSaveInner(userId);
     }
 
     // In order to re-schedule, we need to reuse the same instance, so keep it in final.
     private final Runnable mSaveDirtyInfoRunner = this::saveDirtyInfo;
 
-    private void scheduleSave(@UserIdInt int userId) {
+    private void scheduleSaveInner(@UserIdInt int userId) {
         if (DEBUG) {
             Slog.d(TAG, "Scheduling to save for " + userId);
         }
@@ -1169,6 +1187,8 @@
         final int size = newShortcuts.size();
 
         synchronized (mLock) {
+            getUserShortcutsLocked(userId).ensurePackageInfo(this, packageName, userId);
+
             final ShortcutPackage ps = getPackageShortcutsLocked(packageName, userId);
 
             // Throttling.
@@ -1204,6 +1224,8 @@
         final int size = newShortcuts.size();
 
         synchronized (mLock) {
+            getUserShortcutsLocked(userId).ensurePackageInfo(this, packageName, userId);
+
             final ShortcutPackage ps = getPackageShortcutsLocked(packageName, userId);
 
             // Throttling.
@@ -1241,6 +1263,8 @@
         verifyCaller(packageName, userId);
 
         synchronized (mLock) {
+            getUserShortcutsLocked(userId).ensurePackageInfo(this, packageName, userId);
+
             final ShortcutPackage ps = getPackageShortcutsLocked(packageName, userId);
 
             // Throttling.
@@ -1376,10 +1400,7 @@
     @VisibleForTesting
     boolean hasShortcutHostPermissionInner(@NonNull String callingPackage, int userId) {
         synchronized (mLock) {
-            long start = 0;
-            if (DEBUG) {
-                start = System.currentTimeMillis();
-            }
+            long start = System.currentTimeMillis();
 
             final ShortcutUser user = getUserShortcutsLocked(userId);
 
@@ -1430,8 +1451,8 @@
                     lastPriority = ri.priority;
                 }
             }
+            final long end = System.currentTimeMillis();
             if (DEBUG) {
-                long end = System.currentTimeMillis();
                 Slog.v(TAG, String.format("hasShortcutPermission took %d ms", end - start));
             }
             if (detected != null) {
@@ -1473,6 +1494,9 @@
             mUser.getPackages().valueAt(i).refreshPinnedFlags(this);
         }
 
+        // Remove the package info too.
+        mUser.getPackageInfos().remove(packageName);
+
         scheduleSaveUser(userId);
 
         if (doNotify) {
@@ -1567,6 +1591,9 @@
             Preconditions.checkNotNull(shortcutIds, "shortcutIds");
 
             synchronized (mLock) {
+                getUserShortcutsLocked(userId).ensurePackageInfo(
+                        ShortcutService.this, callingPackage, userId);
+
                 getLauncherShortcuts(callingPackage, userId).pinShortcuts(
                         ShortcutService.this, packageName, shortcutIds);
             }
@@ -1640,7 +1667,16 @@
         }
     }
 
-    private PackageMonitor mPackageMonitor = new PackageMonitor() {
+    /**
+     * Package event callbacks.
+     */
+    @VisibleForTesting
+    final PackageMonitor mPackageMonitor = new PackageMonitor() {
+        @Override
+        public void onPackageAdded(String packageName, int uid) {
+            handlePackageAdded(packageName, getChangingUserId());
+        }
+
         @Override
         public void onPackageUpdateFinished(String packageName, int uid) {
             handlePackageUpdateFinished(packageName, getChangingUserId());
@@ -1650,38 +1686,120 @@
         public void onPackageRemoved(String packageName, int uid) {
             handlePackageRemoved(packageName, getChangingUserId());
         }
-
-        @Override
-        public void onPackageRemovedAllUsers(String packageName, int uid) {
-            handlePackageRemovedAllUsers(packageName, getChangingUserId());
-        }
     };
 
-    void handlePackageUpdateFinished(String packageName, @UserIdInt int userId) {
+    /**
+     * Called when a user is unlocked.  Check all known packages still exist, and otherwise
+     * perform cleanup.
+     */
+    private void cleanupGonePackages(@UserIdInt int userId) {
         if (DEBUG) {
-            Slog.d(TAG, "onPackageUpdateFinished() userId=" + userId);
+            Slog.d(TAG, "cleanupGonePackages() userId=" + userId);
         }
-        // TODO Update the version.
+        ArrayList<String> gonePackages = null;
+
+        final ShortcutUser user = getUserShortcutsLocked(userId);
+        final ArrayMap<String, ShortcutPackageInfo> infos = user.getPackageInfos();
+        for (int i = infos.size() -1; i >= 0; i--) {
+            final ShortcutPackageInfo info = infos.valueAt(i);
+            if (info.isShadow()) {
+                continue;
+            }
+            if (isPackageInstalled(info.getPackageName(), userId)) {
+                continue;
+            }
+            gonePackages = ArrayUtils.add(gonePackages, info.getPackageName());
+        }
+        if (gonePackages != null) {
+            for (int i = gonePackages.size() - 1; i >= 0; i--) {
+                handlePackageGone(gonePackages.get(i), userId);
+            }
+        }
     }
 
-    void handlePackageRemoved(String packageName, @UserIdInt int userId) {
+    private void handlePackageAdded(String packageName, @UserIdInt int userId) {
         if (DEBUG) {
-            Slog.d(TAG, "onPackageRemoved() userId=" + userId);
+            Slog.d(TAG, String.format("handlePackageAdded: %s user=%d", packageName, userId));
+        }
+        synchronized (mLock) {
+            final ArrayMap<String, ShortcutPackageInfo> infos =
+                    getUserShortcutsLocked(userId).getPackageInfos();
+            final ShortcutPackageInfo existing = infos.get(packageName);
+
+            if (existing != null && existing.isShadow()) {
+                Slog.w(TAG, "handlePackageAdded: TODO Restore not implemented");
+            }
+        }
+    }
+
+    private void handlePackageUpdateFinished(String packageName, @UserIdInt int userId) {
+        final PackageInfo pi = getPackageInfo(packageName, userId);
+        if (pi == null) {
+            Slog.w(TAG, "Package not found: " + packageName);
+            return;
+        }
+        synchronized (mLock) {
+            final ShortcutPackageInfo spi =
+                    getUserShortcutsLocked(userId).getPackageInfos().get(packageName);
+            if (spi != null) {
+                spi.refreshAndSave(this, userId);
+            }
+        }
+    }
+
+    private void handlePackageRemoved(String packageName, @UserIdInt int userId) {
+        if (DEBUG) {
+            Slog.d(TAG, String.format("handlePackageRemoved: %s user=%d", packageName, userId));
         }
         synchronized (mLock) {
             cleanUpPackageLocked(packageName, userId);
         }
     }
 
-    void handlePackageRemovedAllUsers(String packageName, @UserIdInt int userId) {
+    private void handlePackageGone(String packageName, @UserIdInt int userId) {
         if (DEBUG) {
-            Slog.d(TAG, "onPackageRemovedAllUsers() userId=" + userId);
+            Slog.d(TAG, String.format("handlePackageGone: %s user=%d", packageName, userId));
         }
         synchronized (mLock) {
             cleanUpPackageLocked(packageName, userId);
         }
+    }
 
-        // TODO Remove from all users, which we can't if the user is locked.
+    // === Backup & restore ===
+
+    PackageInfo getPackageInfo(String packageName, @UserIdInt int userId) {
+        return getPackageInfo(packageName, userId, /*getSignatures=*/ false);
+    }
+
+    PackageInfo getPackageInfo(String packageName, @UserIdInt int userId,
+            boolean getSignatures) {
+        return injectPackageInfo(packageName, userId, getSignatures);
+    }
+
+    @VisibleForTesting
+    PackageInfo injectPackageInfo(String packageName, @UserIdInt int userId,
+            boolean getSignatures) {
+        try {
+            return mIPackageManager.getPackageInfo(packageName,
+                    PackageManager.MATCH_DIRECT_BOOT_AWARE
+                    | PackageManager.MATCH_DIRECT_BOOT_UNAWARE
+                    | (getSignatures ? PackageManager.GET_SIGNATURES : 0)
+                    , userId);
+        } catch (RemoteException e) {
+            // Shouldn't happen.
+            Slog.wtf(TAG, "RemoteException", e);
+            return null;
+        }
+    }
+
+    boolean shouldBackupApp(String packageName, int userId) {
+        final PackageInfo pi = getPackageInfo(packageName, userId);
+        return (pi != null) &&
+                ((pi.applicationInfo.flags & ApplicationInfo.FLAG_ALLOW_BACKUP) != 0);
+    }
+
+    private boolean isPackageInstalled(String packageName, int userId) {
+        return getPackageInfo(packageName, userId) != null;
     }
 
     // === Dump ===
@@ -2039,4 +2157,14 @@
             return pkg.findShortcutById(shortcutId);
         }
     }
+
+    @VisibleForTesting
+    ShortcutPackageInfo getPackageInfoForTest(String packageName, int userId) {
+        synchronized (mLock) {
+            final ShortcutUser user = mUsers.get(userId);
+            if (user == null) return null;
+
+            return user.getPackageInfos().get(packageName);
+        }
+    }
 }
diff --git a/services/core/java/com/android/server/pm/ShortcutUser.java b/services/core/java/com/android/server/pm/ShortcutUser.java
index 4a6b1e4..1a00cda 100644
--- a/services/core/java/com/android/server/pm/ShortcutUser.java
+++ b/services/core/java/com/android/server/pm/ShortcutUser.java
@@ -19,6 +19,7 @@
 import android.annotation.UserIdInt;
 import android.content.ComponentName;
 import android.util.ArrayMap;
+import android.util.Slog;
 
 import libcore.util.Objects;
 
@@ -47,6 +48,8 @@
 
     private final ArrayMap<String, ShortcutLauncher> mLaunchers = new ArrayMap<>();
 
+    private final ArrayMap<String, ShortcutPackageInfo> mPackageInfos = new ArrayMap<>();
+
     private ComponentName mLauncherComponent;
 
     public ShortcutUser(int userId) {
@@ -61,6 +64,10 @@
         return mLaunchers;
     }
 
+    public ArrayMap<String, ShortcutPackageInfo> getPackageInfos() {
+        return mPackageInfos;
+    }
+
     public ShortcutPackage getPackageShortcuts(@NonNull String packageName) {
         ShortcutPackage ret = mPackages.get(packageName);
         if (ret == null) {
@@ -79,25 +86,58 @@
         return ret;
     }
 
-    public void saveToXml(XmlSerializer out) throws IOException, XmlPullParserException {
+    public void ensurePackageInfo(ShortcutService s, String packageName, @UserIdInt int userId) {
+        final ShortcutPackageInfo existing = mPackageInfos.get(packageName);
+
+        if (existing != null) {
+            return;
+        }
+        if (ShortcutService.DEBUG) {
+            Slog.d(TAG, String.format("Fetching package info: %s user=%d", packageName, userId));
+        }
+        final ShortcutPackageInfo newSpi = ShortcutPackageInfo.generateForInstalledPackage(
+                s, packageName, userId);
+        mPackageInfos.put(packageName, newSpi);
+        s.scheduleSaveUser(mUserId);
+    }
+
+    public void saveToXml(ShortcutService s, XmlSerializer out, boolean forBackup)
+            throws IOException, XmlPullParserException {
         out.startTag(null, TAG_ROOT);
 
         ShortcutService.writeTagValue(out, TAG_LAUNCHER,
                 mLauncherComponent);
 
-        final int lsize = mLaunchers.size();
-        for (int i = 0; i < lsize; i++) {
-            mLaunchers.valueAt(i).saveToXml(out);
+        {
+            final int size = mPackageInfos.size();
+            for (int i = 0; i < size; i++) {
+                saveShortcutPackageItem(s, out, mPackageInfos.valueAt(i), forBackup);
+            }
         }
-
-        final int psize = mPackages.size();
-        for (int i = 0; i < psize; i++) {
-            mPackages.valueAt(i).saveToXml(out);
+        {
+            final int size = mLaunchers.size();
+            for (int i = 0; i < size; i++) {
+                saveShortcutPackageItem(s, out, mLaunchers.valueAt(i), forBackup);
+            }
+        }
+        {
+            final int size = mPackages.size();
+            for (int i = 0; i < size; i++) {
+                saveShortcutPackageItem(s, out, mPackages.valueAt(i), forBackup);
+            }
         }
 
         out.endTag(null, TAG_ROOT);
     }
 
+    private void saveShortcutPackageItem(ShortcutService s, XmlSerializer out,
+            ShortcutPackageItem spi, boolean forBackup) throws IOException, XmlPullParserException {
+        if (forBackup && !s.shouldBackupApp(spi.getPackageName(), mUserId)) {
+            return; // Don't save.
+        }
+        spi.saveToXml(out, forBackup);
+    }
+
     public static ShortcutUser loadFromXml(XmlPullParser parser, int userId)
             throws IOException, XmlPullParserException {
         final ShortcutUser ret = new ShortcutUser(userId);
@@ -121,7 +161,7 @@
                     final ShortcutPackage shortcuts = ShortcutPackage.loadFromXml(parser, userId);
 
                     // Don't use addShortcut(), we don't need to save the icon.
-                    ret.getPackages().put(shortcuts.mPackageName, shortcuts);
+                    ret.getPackages().put(shortcuts.getPackageName(), shortcuts);
                     continue;
                 }
 
@@ -129,7 +169,15 @@
                     final ShortcutLauncher shortcuts =
                             ShortcutLauncher.loadFromXml(parser, userId);
 
-                    ret.getLaunchers().put(shortcuts.mPackageName, shortcuts);
+                    ret.getLaunchers().put(shortcuts.getPackageName(), shortcuts);
+                    continue;
+                }
+
+                case ShortcutPackageInfo.TAG_ROOT: {
+                    final ShortcutPackageInfo pi =
+                            ShortcutPackageInfo.loadFromXml(parser);
+
+                    ret.getPackageInfos().put(pi.getPackageName(), pi);
                     continue;
                 }
             }
@@ -175,5 +223,9 @@
         for (int i = 0; i < mPackages.size(); i++) {
             mPackages.valueAt(i).dump(s, pw, prefix + "  ");
         }
+
+        for (int i = 0; i < mPackageInfos.size(); i++) {
+            mPackageInfos.valueAt(i).dump(s, pw, prefix + "  ");
+        }
     }
 }
diff --git a/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest.java b/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest.java
index 28966ca..a30d2b5 100644
--- a/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest.java
+++ b/services/tests/servicestests/src/com/android/server/pm/ShortcutManagerTest.java
@@ -32,19 +32,23 @@
 import android.content.Context;
 import android.content.Intent;
 import android.content.IntentFilter;
+import android.content.pm.ApplicationInfo;
 import android.content.pm.ILauncherApps;
 import android.content.pm.LauncherApps;
 import android.content.pm.LauncherApps.ShortcutQuery;
+import android.content.pm.PackageInfo;
 import android.content.pm.PackageManager;
 import android.content.pm.PackageManagerInternal;
 import android.content.pm.ShortcutInfo;
 import android.content.pm.ShortcutManager;
 import android.content.pm.ShortcutServiceInternal;
+import android.content.pm.Signature;
 import android.content.res.Resources;
 import android.graphics.Bitmap;
 import android.graphics.Bitmap.CompressFormat;
 import android.graphics.BitmapFactory;
 import android.graphics.drawable.Icon;
+import android.net.Uri;
 import android.os.BaseBundle;
 import android.os.Bundle;
 import android.os.FileUtils;
@@ -103,7 +107,6 @@
  * TODO: separate, detailed tests for ShortcutInfo (CTS?) *
  *
  * TODO: Cross-user test (do in CTS?)
- *
  */
 @SmallTest
 public class ShortcutManagerTest extends InstrumentationTestCase {
@@ -217,8 +220,7 @@
 
         @Override
         int injectGetPackageUid(String packageName, int userId) {
-            Integer uid = mInjectedPackageUidMap.get(packageName);
-            return UserHandle.getUid(getCallingUserId(), (uid != null ? uid : 0));
+            return getInjectedPackageInfo(packageName, userId, false).applicationInfo.uid;
         }
 
         @Override
@@ -253,6 +255,12 @@
         }
 
         @Override
+        PackageInfo injectPackageInfo(String packageName, @UserIdInt int userId,
+                boolean getSignatures) {
+            return getInjectedPackageInfo(packageName, userId, getSignatures);
+        }
+
+        @Override
         void postToHandler(Runnable r) {
             final long token = mContext.injectClearCallingIdentity();
             super.postToHandler(r);
@@ -355,7 +363,7 @@
     private int mInjectedCallingUid;
     private String mInjectedClientPackage;
 
-    private Map<String, Integer> mInjectedPackageUidMap;
+    private Map<String, PackageInfo> mInjectedPackages;
 
     private PackageManager mMockPackageManager;
     private PackageManagerInternal mMockPackageManagerInternal;
@@ -407,12 +415,12 @@
 
         mInjectedCurrentTimeLillis = START_TIME;
 
-        mInjectedPackageUidMap = new HashMap<>();
-        mInjectedPackageUidMap.put(CALLING_PACKAGE_1, CALLING_UID_1);
-        mInjectedPackageUidMap.put(CALLING_PACKAGE_2, CALLING_UID_2);
-        mInjectedPackageUidMap.put(CALLING_PACKAGE_3, CALLING_UID_3);
-        mInjectedPackageUidMap.put(LAUNCHER_1, LAUNCHER_UID_1);
-        mInjectedPackageUidMap.put(LAUNCHER_2, LAUNCHER_UID_2);
+        mInjectedPackages = new HashMap<>();;
+        addPackage(CALLING_PACKAGE_1, CALLING_UID_1, 1);
+        addPackage(CALLING_PACKAGE_2, CALLING_UID_2, 2);
+        addPackage(CALLING_PACKAGE_3, CALLING_UID_3, 3);
+        addPackage(LAUNCHER_1, LAUNCHER_UID_1, 4);
+        addPackage(LAUNCHER_2, LAUNCHER_UID_2, 5);
 
         mInjectedFilePathRoot = new File(getTestContext().getCacheDir(), "test-files");
 
@@ -448,12 +456,57 @@
         mService.onBootPhase(SystemService.PHASE_LOCK_SETTINGS_READY);
     }
 
+    private void addPackage(String packageName, int uid, int version) {
+        addPackage(packageName, uid, version, packageName);
+    }
+
+    private Signature[] genSignatures(String... signatures) {
+        final Signature[] sigs = new Signature[signatures.length];
+        for (int i = 0; i < signatures.length; i++){
+            sigs[i] = new Signature(signatures[i].getBytes());
+        }
+        return sigs;
+    }
+
+    private PackageInfo genPackage(String packageName, int uid, int version, String... signatures) {
+        final PackageInfo pi = new PackageInfo();
+        pi.packageName = packageName;
+        pi.applicationInfo = new ApplicationInfo();
+        pi.applicationInfo.uid = uid;
+        pi.versionCode = version;
+        pi.signatures = genSignatures(signatures);
+
+        return pi;
+    }
+
+    private void addPackage(String packageName, int uid, int version, String... signatures) {
+        mInjectedPackages.put(packageName, genPackage(packageName, uid, version, signatures));
+    }
+
+    PackageInfo getInjectedPackageInfo(String packageName, @UserIdInt int userId,
+            boolean getSignatures) {
+        final PackageInfo pi = mInjectedPackages.get(packageName);
+        if (pi == null) return null;
+
+        final PackageInfo ret = new PackageInfo();
+        ret.packageName = pi.packageName;
+        ret.versionCode = pi.versionCode;
+        ret.applicationInfo = new ApplicationInfo(pi.applicationInfo);
+        ret.applicationInfo.uid = UserHandle.getUid(userId, pi.applicationInfo.uid);
+
+        if (getSignatures) {
+            ret.signatures = pi.signatures;
+        }
+
+        return ret;
+    }
+
     /** Replace the current calling package */
     private void setCaller(String packageName, int userId) {
         mInjectedClientPackage = packageName;
-        mInjectedCallingUid = UserHandle.getUid(userId,
-                Preconditions.checkNotNull(mInjectedPackageUidMap.get(packageName),
-                        "Unknown package"));
+        mInjectedCallingUid =
+                Preconditions.checkNotNull(getInjectedPackageInfo(packageName, userId, false),
+                        "Unknown package").applicationInfo.uid;
     }
 
     private void setCaller(String packageName) {
@@ -466,13 +519,13 @@
 
     private void runWithCaller(String packageName, int userId, Runnable r) {
         final String previousPackage = mInjectedClientPackage;
-        final int previousUid = mInjectedCallingUid;
+        final int previousUserId = UserHandle.getUserId(mInjectedCallingUid);
 
         setCaller(packageName, userId);
 
         r.run();
 
-        setCaller(previousPackage, previousUid);
+        setCaller(previousPackage, previousUserId);
     }
 
     private int getCallingUserId() {
@@ -852,6 +905,18 @@
         assertTrue(b == null || b.size() == 0);
     }
 
+    private void assertShortcutPackageInfo(String packageName, int userId, int expectedVersion) {
+        ShortcutPackageInfo spi = mService.getPackageInfoForTest(packageName, userId);
+        assertNotNull(spi);
+        assertEquals(expectedVersion, spi.getVersionCode());
+
+        assertTrue(spi.canRestoreTo(genPackage(packageName, /*uid*/ 0, 9999999, packageName)));
+    }
+
+    private void assertNoShortcutPackageInfo(String packageName, int userId) {
+        assertNull(mService.getPackageInfoForTest(packageName, userId));
+    }
+
     private ShortcutInfo getPackageShortcut(String packageName, String shortcutId, int userId) {
         return mService.getPackageShortcutForTest(packageName, shortcutId, userId);
     }
@@ -886,6 +951,22 @@
         return getLauncherShortcuts(launcher, userId, ShortcutQuery.FLAG_GET_PINNED);
     }
 
+
+    private Intent genPackageDeleteIntent(String pakcageName, int userId) {
+        Intent i = new Intent(Intent.ACTION_PACKAGE_REMOVED);
+        i.setData(Uri.parse("package:" + pakcageName));
+        i.putExtra(Intent.EXTRA_USER_HANDLE, userId);
+        return i;
+    }
+
+    private Intent genPackageUpdateIntent(String pakcageName, int userId) {
+        Intent i = new Intent(Intent.ACTION_PACKAGE_ADDED);
+        i.setData(Uri.parse("package:" + pakcageName));
+        i.putExtra(Intent.EXTRA_USER_HANDLE, userId);
+        i.putExtra(Intent.EXTRA_REPLACING, true);
+        return i;
+    }
+
     /**
      * Wrap a set in an ArraySet just to get a better toString.
      */
@@ -1017,6 +1098,8 @@
     }
 
     public void testSetDynamicShortcuts() {
+        setCaller(CALLING_PACKAGE_1, USER_0);
+
         final Icon icon1 = Icon.createWithResource(getTestContext(), R.drawable.icon1);
         final Icon icon2 = Icon.createWithBitmap(BitmapFactory.decodeResource(
                 getTestContext().getResources(), R.drawable.icon2));
@@ -1045,6 +1128,11 @@
                 "shortcut1", "shortcut2");
         assertEquals(2, mManager.getRemainingCallCount());
 
+        assertShortcutPackageInfo(CALLING_PACKAGE_1, USER_0, 1);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_2, USER_0);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_1, USER_10);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_2, USER_10);
+
         // TODO: Check fields
 
         assertTrue(mManager.setDynamicShortcuts(Arrays.asList(si1)));
@@ -1068,9 +1156,20 @@
         assertEquals(2, mManager.getDynamicShortcuts().size());
 
         // TODO Check max number
+
+        runWithCaller(CALLING_PACKAGE_2, USER_10, () -> {
+            assertTrue(mManager.setDynamicShortcuts(Arrays.asList(makeShortcut("s1"))));
+
+            assertShortcutPackageInfo(CALLING_PACKAGE_1, USER_0, 1);
+            assertNoShortcutPackageInfo(CALLING_PACKAGE_2, USER_0);
+            assertNoShortcutPackageInfo(CALLING_PACKAGE_1, USER_10);
+            assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_10, 2);
+        });
     }
 
     public void testAddDynamicShortcuts() {
+        setCaller(CALLING_PACKAGE_1, USER_0);
+
         final ShortcutInfo si1 = makeShortcut("shortcut1");
         final ShortcutInfo si2 = makeShortcut("shortcut2");
         final ShortcutInfo si3 = makeShortcut("shortcut3");
@@ -1099,6 +1198,11 @@
         // TODO Check max number
 
         // TODO Check fields.
+
+        runWithCaller(CALLING_PACKAGE_2, USER_10, () -> {
+            assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+            assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_10, 2);
+        });
     }
 
     public void testDeleteDynamicShortcut() {
@@ -1691,6 +1795,15 @@
         // TODO Check with other fields too.
 
         // TODO Check bitmap removal too.
+
+        runWithCaller(CALLING_PACKAGE_2, USER_11, () -> {
+            assertNoShortcutPackageInfo(CALLING_PACKAGE_2, USER_11);
+
+            mManager.updateShortcuts(Arrays.asList());
+
+            // Even an empty update call will populate the package info.
+            assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_11, 2);
+        });
     }
 
     // TODO: updateShortcuts()
@@ -1886,9 +1999,16 @@
 
         // Pin some.
         runWithCaller(LAUNCHER_1, USER_0, () -> {
+            assertNoShortcutPackageInfo(LAUNCHER_1, USER_0);
+
             mLauncherApps.pinShortcuts(CALLING_PACKAGE_1,
                     Arrays.asList("s2", "s3"), getCallingUser());
 
+            assertShortcutPackageInfo(LAUNCHER_1, USER_0, 4);
+            assertNoShortcutPackageInfo(LAUNCHER_2, USER_0);
+            assertNoShortcutPackageInfo(LAUNCHER_1, USER_10);
+            assertNoShortcutPackageInfo(LAUNCHER_2, USER_10);
+
             mLauncherApps.pinShortcuts(CALLING_PACKAGE_2,
                     Arrays.asList("s3", "s4", "s5"), getCallingUser());
 
@@ -1949,11 +2069,19 @@
 
         dumpsysOnLogcat();
 
+        assertNoShortcutPackageInfo(LAUNCHER_1, USER_0);
+        assertNoShortcutPackageInfo(LAUNCHER_2, USER_0);
+        assertNoShortcutPackageInfo(LAUNCHER_1, USER_10);
+        assertNoShortcutPackageInfo(LAUNCHER_2, USER_10);
+
         // Pin some.
         runWithCaller(LAUNCHER_1, USER_0, () -> {
             mLauncherApps.pinShortcuts(CALLING_PACKAGE_1,
                     Arrays.asList("s3", "s4"), getCallingUser());
 
+            assertShortcutPackageInfo(LAUNCHER_1, USER_0, 4);
+            assertNoShortcutPackageInfo(LAUNCHER_2, USER_0);
+
             mLauncherApps.pinShortcuts(CALLING_PACKAGE_2,
                     Arrays.asList("s1", "s2", "s4"), getCallingUser());
         });
@@ -2027,10 +2155,16 @@
                                     | ShortcutQuery.FLAG_GET_DYNAMIC), getCallingUser())),
                     "s2");
 
+            assertNoShortcutPackageInfo(LAUNCHER_2, USER_0);
+            assertNoShortcutPackageInfo(LAUNCHER_2, USER_10);
+
             // Now pin some.
             mLauncherApps.pinShortcuts(CALLING_PACKAGE_1,
                     Arrays.asList("s1", "s2"), getCallingUser());
 
+            assertShortcutPackageInfo(LAUNCHER_2, USER_0, 5);
+            assertNoShortcutPackageInfo(LAUNCHER_2, USER_10);
+
             mLauncherApps.pinShortcuts(CALLING_PACKAGE_2,
                     Arrays.asList("s1", "s2"), getCallingUser());
 
@@ -2048,10 +2182,26 @@
                     "s2");
         });
 
+        assertShortcutPackageInfo(CALLING_PACKAGE_1, USER_0, 1);
+        assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_0, 2);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_3, USER_0);
+        assertShortcutPackageInfo(LAUNCHER_1, USER_0, 4);
+        assertShortcutPackageInfo(LAUNCHER_2, USER_0, 5);
+
         // Re-initialize and load from the files.
         mService.saveDirtyInfo();
         initService();
 
+        // Load from file.
+        mService.handleUnlockUser(USER_0);
+
+        // Make sure package info is restored too.
+        assertShortcutPackageInfo(CALLING_PACKAGE_1, USER_0, 1);
+        assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_0, 2);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_3, USER_0);
+        assertShortcutPackageInfo(LAUNCHER_1, USER_0, 4);
+        assertShortcutPackageInfo(LAUNCHER_2, USER_0, 5);
+
         runWithCaller(LAUNCHER_1, USER_0, () -> {
             assertShortcutIds(assertAllPinned(assertAllNotKeyFieldsOnly(
                     mLauncherApps.getShortcuts(buildQuery(/* time =*/ 0, CALLING_PACKAGE_1,
@@ -2489,6 +2639,10 @@
         mService.getShortcutsForTest().get(UserHandle.USER_SYSTEM).setLauncherComponent(
                 mService, new ComponentName("pkg1", "class"));
 
+        assertShortcutPackageInfo(CALLING_PACKAGE_1, USER_0, 1);
+        assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_0, 2);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_3, USER_0);
+
         // Restore.
         mService.saveDirtyInfo();
         initService();
@@ -2499,6 +2653,10 @@
         // this will pre-load the per-user info.
         mService.handleUnlockUser(UserHandle.USER_SYSTEM);
 
+        assertShortcutPackageInfo(CALLING_PACKAGE_1, USER_0, 1);
+        assertShortcutPackageInfo(CALLING_PACKAGE_2, USER_0, 2);
+        assertNoShortcutPackageInfo(CALLING_PACKAGE_3, USER_0);
+
         // Now it's loaded.
         assertEquals(1, mService.getShortcutsForTest().size());
 
@@ -2637,6 +2795,11 @@
         assertShortcutExists(CALLING_PACKAGE_1, "s10_1", USER_10);
         assertShortcutExists(CALLING_PACKAGE_2, "s10_2", USER_10);
 
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+
         mService.saveDirtyInfo();
 
         // Nonexistent package.
@@ -2664,6 +2827,11 @@
         assertShortcutExists(CALLING_PACKAGE_1, "s10_1", USER_10);
         assertShortcutExists(CALLING_PACKAGE_2, "s10_2", USER_10);
 
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+
         mService.saveDirtyInfo();
 
         // Remove a package.
@@ -2690,6 +2858,11 @@
         assertShortcutExists(CALLING_PACKAGE_1, "s10_1", USER_10);
         assertShortcutExists(CALLING_PACKAGE_2, "s10_2", USER_10);
 
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+
         mService.saveDirtyInfo();
 
         // Remove a launcher.
@@ -2738,6 +2911,11 @@
         assertShortcutExists(CALLING_PACKAGE_1, "s10_1", USER_10);
         assertShortcutNotExists(CALLING_PACKAGE_2, "s10_2", USER_10);
 
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+
         mService.saveDirtyInfo();
 
         // Remove the other launcher from user 10 too.
@@ -2792,4 +2970,162 @@
     // TODO Detailed test for hasShortcutPermissionInner().
 
     // TODO Add tests for the command line functions too.
+
+    private void checkCanRestoreTo(boolean expected, ShortcutPackageInfo spi,
+            int version, String... signatures) {
+        assertEquals(expected, spi.canRestoreTo(genPackage(
+                "dummy", /* uid */ 0, version, signatures)));
+    }
+
+    public void testCanRestoreTo() {
+        addPackage(CALLING_PACKAGE_1, CALLING_UID_1, 10, "sig1");
+        addPackage(CALLING_PACKAGE_2, CALLING_UID_1, 10, "sig1", "sig2");
+
+        final ShortcutPackageInfo spi1 = ShortcutPackageInfo.generateForInstalledPackage(
+                mService, CALLING_PACKAGE_1, USER_0);
+        final ShortcutPackageInfo spi2 = ShortcutPackageInfo.generateForInstalledPackage(
+                mService, CALLING_PACKAGE_2, USER_0);
+
+        checkCanRestoreTo(true, spi1, 10, "sig1");
+        checkCanRestoreTo(true, spi1, 10, "x", "sig1");
+        checkCanRestoreTo(true, spi1, 10, "sig1", "y");
+        checkCanRestoreTo(true, spi1, 10, "x", "sig1", "y");
+        checkCanRestoreTo(true, spi1, 11, "sig1");
+
+        checkCanRestoreTo(false, spi1, 10 /* empty */);
+        checkCanRestoreTo(false, spi1, 10, "x");
+        checkCanRestoreTo(false, spi1, 10, "x", "y");
+        checkCanRestoreTo(false, spi1, 10, "x");
+        checkCanRestoreTo(false, spi1, 9, "sig1");
+
+        checkCanRestoreTo(true, spi2, 10, "sig1", "sig2");
+        checkCanRestoreTo(true, spi2, 10, "sig2", "sig1");
+        checkCanRestoreTo(true, spi2, 10, "x", "sig1", "sig2");
+        checkCanRestoreTo(true, spi2, 10, "x", "sig2", "sig1");
+        checkCanRestoreTo(true, spi2, 10, "sig1", "sig2", "y");
+        checkCanRestoreTo(true, spi2, 10, "sig2", "sig1", "y");
+        checkCanRestoreTo(true, spi2, 10, "x", "sig1", "sig2", "y");
+        checkCanRestoreTo(true, spi2, 10, "x", "sig2", "sig1", "y");
+        checkCanRestoreTo(true, spi2, 11, "x", "sig2", "sig1", "y");
+
+        checkCanRestoreTo(false, spi2, 10, "sig1", "sig2x");
+        checkCanRestoreTo(false, spi2, 10, "sig2", "sig1x");
+        checkCanRestoreTo(false, spi2, 10, "x", "sig1x", "sig2");
+        checkCanRestoreTo(false, spi2, 10, "x", "sig2x", "sig1");
+        checkCanRestoreTo(false, spi2, 10, "sig1", "sig2x", "y");
+        checkCanRestoreTo(false, spi2, 10, "sig2", "sig1x", "y");
+        checkCanRestoreTo(false, spi2, 10, "x", "sig1x", "sig2", "y");
+        checkCanRestoreTo(false, spi2, 10, "x", "sig2x", "sig1", "y");
+        checkCanRestoreTo(false, spi2, 11, "x", "sig2x", "sig1", "y");
+    }
+
+    public void testShortcutPackageInfoRefresh() {
+        addPackage(CALLING_PACKAGE_1, CALLING_UID_1, 10, "sig1");
+
+        final ShortcutPackageInfo spi1 = ShortcutPackageInfo.generateForInstalledPackage(
+                mService, CALLING_PACKAGE_1, USER_0);
+
+        checkCanRestoreTo(true, spi1, 10, "sig1");
+
+        addPackage(CALLING_PACKAGE_1, CALLING_UID_1, 11, "sig1", "sig2");
+
+        spi1.refreshAndSave(mService, USER_0);
+
+        mService.handleCleanupUser(USER_0);
+        initService();
+
+        checkCanRestoreTo(false, spi1, 10, "sig1", "sig2");
+        checkCanRestoreTo(false, spi1, 11, "sig", "sig2");
+        checkCanRestoreTo(false, spi1, 11, "sig1", "sig");
+        checkCanRestoreTo(true, spi1, 11, "sig1", "sig2");
+    }
+
+    public void testHandlePackageDelete() {
+        setCaller(CALLING_PACKAGE_1, USER_0);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        setCaller(CALLING_PACKAGE_2, USER_0);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        setCaller(CALLING_PACKAGE_3, USER_0);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        setCaller(CALLING_PACKAGE_1, USER_10);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        setCaller(CALLING_PACKAGE_2, USER_10);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        setCaller(CALLING_PACKAGE_3, USER_10);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_10));
+
+        mService.mPackageMonitor.onReceive(getTestContext(),
+                genPackageDeleteIntent(CALLING_PACKAGE_1, USER_0));
+
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_10));
+
+        mService.mPackageMonitor.onReceive(getTestContext(),
+                genPackageDeleteIntent(CALLING_PACKAGE_2, USER_10));
+
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_10));
+
+        mInjectedPackages.remove(CALLING_PACKAGE_1);
+        mInjectedPackages.remove(CALLING_PACKAGE_3);
+
+        mService.handleUnlockUser(USER_0);
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_10));
+
+        mService.handleUnlockUser(USER_10);
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_0));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_0));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_10));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_2, USER_10));
+        assertNull(mService.getPackageInfoForTest(CALLING_PACKAGE_3, USER_10));
+    }
+
+    public void testHandlePackageUpdate() {
+        setCaller(CALLING_PACKAGE_1, USER_0);
+        assertTrue(mManager.addDynamicShortcut(makeShortcut("s1")));
+
+        assertNotNull(mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0));
+        assertEquals(1, mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0).getVersionCode());
+
+        addPackage(CALLING_PACKAGE_1, CALLING_UID_1, 123);
+
+        mService.mPackageMonitor.onReceive(getTestContext(),
+                genPackageUpdateIntent("abc", USER_0));
+        assertEquals(1, mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0).getVersionCode());
+
+        mService.mPackageMonitor.onReceive(getTestContext(),
+                genPackageUpdateIntent("abc", USER_10));
+        assertEquals(1, mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0).getVersionCode());
+
+        mService.mPackageMonitor.onReceive(getTestContext(),
+                genPackageUpdateIntent(CALLING_PACKAGE_1, USER_0));
+        assertEquals(123, mService.getPackageInfoForTest(CALLING_PACKAGE_1, USER_0)
+                .getVersionCode());
+    }
 }