diff --git a/src/com/android/launcher3/Launcher.java b/src/com/android/launcher3/Launcher.java
index 0841f4f..8814eb8 100644
--- a/src/com/android/launcher3/Launcher.java
+++ b/src/com/android/launcher3/Launcher.java
@@ -3768,16 +3768,12 @@
      * Implementation of the method from LauncherModel.Callbacks.
      *
      * @param updated list of shortcuts which have changed.
-     * @param removed list of shortcuts which were deleted in the background. This can happen when
-     *                an app gets removed from the system or some of its components are no longer
-     *                available.
      */
     @Override
-    public void bindShortcutsChanged(final ArrayList<ShortcutInfo> updated,
-            final ArrayList<ShortcutInfo> removed, final UserHandle user) {
+    public void bindShortcutsChanged(final ArrayList<ShortcutInfo> updated, final UserHandle user) {
         Runnable r = new Runnable() {
             public void run() {
-                bindShortcutsChanged(updated, removed, user);
+                bindShortcutsChanged(updated, user);
             }
         };
         if (waitUntilResume(r)) {
@@ -3787,31 +3783,6 @@
         if (!updated.isEmpty()) {
             mWorkspace.updateShortcuts(updated);
         }
-
-        if (!removed.isEmpty()) {
-            HashSet<ComponentName> removedComponents = new HashSet<>();
-            HashSet<ShortcutKey> removedDeepShortcuts = new HashSet<>();
-
-            for (ShortcutInfo si : removed) {
-                if (si.itemType == Favorites.ITEM_TYPE_DEEP_SHORTCUT) {
-                    removedDeepShortcuts.add(ShortcutKey.fromItemInfo(si));
-                } else {
-                    removedComponents.add(si.getTargetComponent());
-                }
-            }
-
-            if (!removedComponents.isEmpty()) {
-                ItemInfoMatcher matcher = ItemInfoMatcher.ofComponents(removedComponents, user);
-                mWorkspace.removeItemsByMatcher(matcher);
-                mDragController.onAppsRemoved(matcher);
-            }
-
-            if (!removedDeepShortcuts.isEmpty()) {
-                ItemInfoMatcher matcher = ItemInfoMatcher.ofShortcutKeys(removedDeepShortcuts);
-                mWorkspace.removeItemsByMatcher(matcher);
-                mDragController.onAppsRemoved(matcher);
-            }
-        }
     }
 
     /**
@@ -3841,28 +3812,17 @@
      * package-removal should clear all items by package name.
      */
     @Override
-    public void bindWorkspaceComponentsRemoved(
-            final HashSet<String> packageNames, final HashSet<ComponentName> components,
-            final UserHandle user) {
+    public void bindWorkspaceComponentsRemoved(final ItemInfoMatcher matcher) {
         Runnable r = new Runnable() {
             public void run() {
-                bindWorkspaceComponentsRemoved(packageNames, components, user);
+                bindWorkspaceComponentsRemoved(matcher);
             }
         };
         if (waitUntilResume(r)) {
             return;
         }
-        if (!packageNames.isEmpty()) {
-            ItemInfoMatcher matcher = ItemInfoMatcher.ofPackages(packageNames, user);
-            mWorkspace.removeItemsByMatcher(matcher);
-            mDragController.onAppsRemoved(matcher);
-
-        }
-        if (!components.isEmpty()) {
-            ItemInfoMatcher matcher = ItemInfoMatcher.ofComponents(components, user);
-            mWorkspace.removeItemsByMatcher(matcher);
-            mDragController.onAppsRemoved(matcher);
-        }
+        mWorkspace.removeItemsByMatcher(matcher);
+        mDragController.onAppsRemoved(matcher);
     }
 
     @Override
diff --git a/src/com/android/launcher3/LauncherModel.java b/src/com/android/launcher3/LauncherModel.java
index 22d62ec..a906b00 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -56,6 +56,7 @@
 import com.android.launcher3.shortcuts.DeepShortcutManager;
 import com.android.launcher3.shortcuts.ShortcutInfoCompat;
 import com.android.launcher3.util.ComponentKey;
+import com.android.launcher3.util.ItemInfoMatcher;
 import com.android.launcher3.util.MultiHashMap;
 import com.android.launcher3.util.PackageUserKey;
 import com.android.launcher3.util.Preconditions;
@@ -148,13 +149,10 @@
                                   ArrayList<ItemInfo> addNotAnimated,
                                   ArrayList<ItemInfo> addAnimated);
         public void bindPromiseAppProgressUpdated(PromiseAppInfo app);
-        public void bindShortcutsChanged(ArrayList<ShortcutInfo> updated,
-                ArrayList<ShortcutInfo> removed, UserHandle user);
+        public void bindShortcutsChanged(ArrayList<ShortcutInfo> updated, UserHandle user);
         public void bindWidgetsRestored(ArrayList<LauncherAppWidgetInfo> widgets);
         public void bindRestoreItemsChange(HashSet<ItemInfo> updates);
-        public void bindWorkspaceComponentsRemoved(
-                HashSet<String> packageNames, HashSet<ComponentName> components,
-                UserHandle user);
+        public void bindWorkspaceComponentsRemoved(ItemInfoMatcher matcher);
         public void bindAppInfosRemoved(ArrayList<AppInfo> appInfos);
         public void bindAllWidgets(MultiHashMap<PackageItemInfo, WidgetItem> widgets);
         public void onPageBoundSynchronously(int page);
diff --git a/src/com/android/launcher3/model/BaseModelUpdateTask.java b/src/com/android/launcher3/model/BaseModelUpdateTask.java
index 9b4510f..d5b5aa7 100644
--- a/src/com/android/launcher3/model/BaseModelUpdateTask.java
+++ b/src/com/android/launcher3/model/BaseModelUpdateTask.java
@@ -26,6 +26,7 @@
 import com.android.launcher3.LauncherModel.Callbacks;
 import com.android.launcher3.ShortcutInfo;
 import com.android.launcher3.util.ComponentKey;
+import com.android.launcher3.util.ItemInfoMatcher;
 import com.android.launcher3.util.MultiHashMap;
 
 import java.util.ArrayList;
@@ -94,19 +95,12 @@
 
 
     public void bindUpdatedShortcuts(
-            ArrayList<ShortcutInfo> updatedShortcuts, UserHandle user) {
-        bindUpdatedShortcuts(updatedShortcuts, new ArrayList<ShortcutInfo>(), user);
-    }
-
-    public void bindUpdatedShortcuts(
-            final ArrayList<ShortcutInfo> updatedShortcuts,
-            final ArrayList<ShortcutInfo> removedShortcuts,
-            final UserHandle user) {
-        if (!updatedShortcuts.isEmpty() || !removedShortcuts.isEmpty()) {
+            final ArrayList<ShortcutInfo> updatedShortcuts, final UserHandle user) {
+        if (!updatedShortcuts.isEmpty()) {
             scheduleCallbackTask(new CallbackTask() {
                 @Override
                 public void execute(Callbacks callbacks) {
-                    callbacks.bindShortcutsChanged(updatedShortcuts, removedShortcuts, user);
+                    callbacks.bindShortcutsChanged(updatedShortcuts, user);
                 }
             });
         }
@@ -132,4 +126,16 @@
             }
         });
     }
+
+    public void deleteAndBindComponentsRemoved(final ItemInfoMatcher matcher) {
+        getModelWriter().deleteItemsFromDatabase(matcher);
+
+        // Call the components-removed callback
+        scheduleCallbackTask(new CallbackTask() {
+            @Override
+            public void execute(Callbacks callbacks) {
+                callbacks.bindWorkspaceComponentsRemoved(matcher);
+            }
+        });
+    }
 }
diff --git a/src/com/android/launcher3/model/PackageUpdatedTask.java b/src/com/android/launcher3/model/PackageUpdatedTask.java
index c6e878c..6c78d5b 100644
--- a/src/com/android/launcher3/model/PackageUpdatedTask.java
+++ b/src/com/android/launcher3/model/PackageUpdatedTask.java
@@ -43,6 +43,7 @@
 import com.android.launcher3.graphics.LauncherIcons;
 import com.android.launcher3.util.FlagOp;
 import com.android.launcher3.util.ItemInfoMatcher;
+import com.android.launcher3.util.LongArrayMap;
 import com.android.launcher3.util.PackageManagerHelper;
 import com.android.launcher3.util.PackageUserKey;
 import java.util.ArrayList;
@@ -172,7 +173,7 @@
         // Update shortcut infos
         if (mOp == OP_ADD || flagOp != FlagOp.NO_OP) {
             final ArrayList<ShortcutInfo> updatedShortcuts = new ArrayList<>();
-            final ArrayList<ShortcutInfo> removedShortcuts = new ArrayList<>();
+            final LongArrayMap<Boolean> removedShortcuts = new LongArrayMap<>();
             final ArrayList<LauncherAppWidgetInfo> widgets = new ArrayList<>();
 
             synchronized (dataModel) {
@@ -213,7 +214,7 @@
                                         }
 
                                         if ((intent == null) || (appInfo == null)) {
-                                            removedShortcuts.add(si);
+                                            removedShortcuts.put(si.id, true);
                                             continue;
                                         }
                                         si.intent = intent;
@@ -267,9 +268,9 @@
                 }
             }
 
-            bindUpdatedShortcuts(updatedShortcuts, removedShortcuts, mUser);
+            bindUpdatedShortcuts(updatedShortcuts, mUser);
             if (!removedShortcuts.isEmpty()) {
-                getModelWriter().deleteItemsFromDatabase(removedShortcuts);
+                deleteAndBindComponentsRemoved(ItemInfoMatcher.ofItemIds(removedShortcuts, false));
             }
 
             if (!widgets.isEmpty()) {
@@ -306,22 +307,12 @@
         }
 
         if (!removedPackages.isEmpty() || !removedComponents.isEmpty()) {
-            getModelWriter().deleteItemsFromDatabase(
-                    ItemInfoMatcher.ofPackages(removedPackages, mUser));
-            getModelWriter().deleteItemsFromDatabase(
-                    ItemInfoMatcher.ofComponents(removedComponents, mUser));
+            ItemInfoMatcher removeMatch = ItemInfoMatcher.ofPackages(removedPackages, mUser)
+                    .or(ItemInfoMatcher.ofComponents(removedComponents, mUser));
+            deleteAndBindComponentsRemoved(removeMatch);
 
             // Remove any queued items from the install queue
             InstallShortcutReceiver.removeFromInstallQueue(context, removedPackages, mUser);
-
-            // Call the components-removed callback
-            scheduleCallbackTask(new CallbackTask() {
-                @Override
-                public void execute(Callbacks callbacks) {
-                    callbacks.bindWorkspaceComponentsRemoved(
-                            removedPackages, removedComponents, mUser);
-                }
-            });
         }
 
         if (!removedApps.isEmpty()) {
diff --git a/src/com/android/launcher3/model/ShortcutsChangedTask.java b/src/com/android/launcher3/model/ShortcutsChangedTask.java
index 17cc238..c1f33a6 100644
--- a/src/com/android/launcher3/model/ShortcutsChangedTask.java
+++ b/src/com/android/launcher3/model/ShortcutsChangedTask.java
@@ -26,9 +26,12 @@
 import com.android.launcher3.graphics.LauncherIcons;
 import com.android.launcher3.shortcuts.DeepShortcutManager;
 import com.android.launcher3.shortcuts.ShortcutInfoCompat;
+import com.android.launcher3.shortcuts.ShortcutKey;
+import com.android.launcher3.util.ItemInfoMatcher;
 import com.android.launcher3.util.MultiHashMap;
 
 import java.util.ArrayList;
+import java.util.HashSet;
 import java.util.List;
 
 /**
@@ -56,33 +59,35 @@
         deepShortcutManager.onShortcutsChanged(mShortcuts);
 
         // Find ShortcutInfo's that have changed on the workspace.
-        final ArrayList<ShortcutInfo> removedShortcutInfos = new ArrayList<>();
-        MultiHashMap<String, ShortcutInfo> idsToWorkspaceShortcutInfos = new MultiHashMap<>();
+        HashSet<ShortcutKey> removedKeys = new HashSet<>();
+        MultiHashMap<ShortcutKey, ShortcutInfo> keyToShortcutInfo = new MultiHashMap<>();
+        HashSet<String> allIds = new HashSet<>();
+
         for (ItemInfo itemInfo : dataModel.itemsIdMap) {
             if (itemInfo.itemType == LauncherSettings.Favorites.ITEM_TYPE_DEEP_SHORTCUT) {
                 ShortcutInfo si = (ShortcutInfo) itemInfo;
-                if (si.getIntent().getPackage().equals(mPackageName)
-                        && si.user.equals(mUser)) {
-                    idsToWorkspaceShortcutInfos.addToList(si.getDeepShortcutId(), si);
+                if (si.getIntent().getPackage().equals(mPackageName) && si.user.equals(mUser)) {
+                    keyToShortcutInfo.addToList(ShortcutKey.fromItemInfo(si), si);
+                    allIds.add(si.getDeepShortcutId());
                 }
             }
         }
 
         final ArrayList<ShortcutInfo> updatedShortcutInfos = new ArrayList<>();
-        if (!idsToWorkspaceShortcutInfos.isEmpty()) {
+        if (!keyToShortcutInfo.isEmpty()) {
             // Update the workspace to reflect the changes to updated shortcuts residing on it.
             List<ShortcutInfoCompat> shortcuts = deepShortcutManager.queryForFullDetails(
-                    mPackageName, new ArrayList<>(idsToWorkspaceShortcutInfos.keySet()), mUser);
+                    mPackageName, new ArrayList<>(allIds), mUser);
             for (ShortcutInfoCompat fullDetails : shortcuts) {
-                List<ShortcutInfo> shortcutInfos = idsToWorkspaceShortcutInfos
-                        .remove(fullDetails.getId());
+                ShortcutKey key = ShortcutKey.fromInfo(fullDetails);
+                List<ShortcutInfo> shortcutInfos = keyToShortcutInfo.remove(key);
                 if (!fullDetails.isPinned()) {
                     // The shortcut was previously pinned but is no longer, so remove it from
                     // the workspace and our pinned shortcut counts.
                     // Note that we put this check here, after querying for full details,
                     // because there's a possible race condition between pinning and
                     // receiving this callback.
-                    removedShortcutInfos.addAll(shortcutInfos);
+                    removedKeys.add(key);
                     continue;
                 }
                 for (final ShortcutInfo shortcutInfo : shortcutInfos) {
@@ -94,16 +99,14 @@
             }
         }
 
-        // If there are still entries in idsToWorkspaceShortcutInfos, that means that
+        // If there are still entries in keyToShortcutInfo, that means that
         // the corresponding shortcuts weren't passed in onShortcutsChanged(). This
         // means they were cleared, so we remove and unpin them now.
-        for (String id : idsToWorkspaceShortcutInfos.keySet()) {
-            removedShortcutInfos.addAll(idsToWorkspaceShortcutInfos.get(id));
-        }
+        removedKeys.addAll(keyToShortcutInfo.keySet());
 
-        bindUpdatedShortcuts(updatedShortcutInfos, removedShortcutInfos, mUser);
-        if (!removedShortcutInfos.isEmpty()) {
-            getModelWriter().deleteItemsFromDatabase(removedShortcutInfos);
+        bindUpdatedShortcuts(updatedShortcutInfos, mUser);
+        if (!keyToShortcutInfo.isEmpty()) {
+            deleteAndBindComponentsRemoved(ItemInfoMatcher.ofShortcutKeys(removedKeys));
         }
 
         if (mUpdateIdMap) {
diff --git a/src/com/android/launcher3/model/UserLockStateChangedTask.java b/src/com/android/launcher3/model/UserLockStateChangedTask.java
index 802771f..8170f9a 100644
--- a/src/com/android/launcher3/model/UserLockStateChangedTask.java
+++ b/src/com/android/launcher3/model/UserLockStateChangedTask.java
@@ -29,9 +29,11 @@
 import com.android.launcher3.shortcuts.ShortcutInfoCompat;
 import com.android.launcher3.shortcuts.ShortcutKey;
 import com.android.launcher3.util.ComponentKey;
+import com.android.launcher3.util.ItemInfoMatcher;
 
 import java.util.ArrayList;
 import java.util.HashMap;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 
@@ -70,17 +72,19 @@
 
         // Update the workspace to reflect the changes to updated shortcuts residing on it.
         ArrayList<ShortcutInfo> updatedShortcutInfos = new ArrayList<>();
-        ArrayList<ShortcutInfo> deletedShortcutInfos = new ArrayList<>();
+        HashSet<ShortcutKey> removedKeys = new HashSet<>();
+
         for (ItemInfo itemInfo : dataModel.itemsIdMap) {
             if (itemInfo.itemType == LauncherSettings.Favorites.ITEM_TYPE_DEEP_SHORTCUT
                     && mUser.equals(itemInfo.user)) {
                 ShortcutInfo si = (ShortcutInfo) itemInfo;
                 if (isUserUnlocked) {
-                    ShortcutInfoCompat shortcut = pinnedShortcuts.get(ShortcutKey.fromItemInfo(si));
+                    ShortcutKey key = ShortcutKey.fromItemInfo(si);
+                    ShortcutInfoCompat shortcut = pinnedShortcuts.get(key);
                     // We couldn't verify the shortcut during loader. If its no longer available
                     // (probably due to clear data), delete the workspace item as well
                     if (shortcut == null) {
-                        deletedShortcutInfos.add(si);
+                        removedKeys.add(key);
                         continue;
                     }
                     si.isDisabled &= ~ShortcutInfo.FLAG_DISABLED_LOCKED_USER;
@@ -93,9 +97,9 @@
                 updatedShortcutInfos.add(si);
             }
         }
-        bindUpdatedShortcuts(updatedShortcutInfos, deletedShortcutInfos, mUser);
-        if (!deletedShortcutInfos.isEmpty()) {
-            getModelWriter().deleteItemsFromDatabase(deletedShortcutInfos);
+        bindUpdatedShortcuts(updatedShortcutInfos, mUser);
+        if (!removedKeys.isEmpty()) {
+            deleteAndBindComponentsRemoved(ItemInfoMatcher.ofShortcutKeys(removedKeys));
         }
 
         // Remove shortcut id map for that user
diff --git a/src/com/android/launcher3/util/ItemInfoMatcher.java b/src/com/android/launcher3/util/ItemInfoMatcher.java
index 42de284..18787b6 100644
--- a/src/com/android/launcher3/util/ItemInfoMatcher.java
+++ b/src/com/android/launcher3/util/ItemInfoMatcher.java
@@ -18,6 +18,7 @@
 
 import android.content.ComponentName;
 import android.os.UserHandle;
+import android.util.SparseLongArray;
 
 import com.android.launcher3.FolderInfo;
 import com.android.launcher3.ItemInfo;
@@ -66,6 +67,32 @@
         return filtered;
     }
 
+    /**
+     * Returns a new matcher with returns true if either this or {@param matcher} returns true.
+     */
+    public ItemInfoMatcher or(final ItemInfoMatcher matcher) {
+       final ItemInfoMatcher that = this;
+        return new ItemInfoMatcher() {
+            @Override
+            public boolean matches(ItemInfo info, ComponentName cn) {
+                return that.matches(info, cn) || matcher.matches(info, cn);
+            }
+        };
+    }
+
+    /**
+     * Returns a new matcher with returns true if both this and {@param matcher} returns true.
+     */
+    public ItemInfoMatcher and(final ItemInfoMatcher matcher) {
+        final ItemInfoMatcher that = this;
+        return new ItemInfoMatcher() {
+            @Override
+            public boolean matches(ItemInfo info, ComponentName cn) {
+                return that.matches(info, cn) && matcher.matches(info, cn);
+            }
+        };
+    }
+
     public static ItemInfoMatcher ofUser(final UserHandle user) {
         return new ItemInfoMatcher() {
             @Override
@@ -104,4 +131,14 @@
             }
         };
     }
+
+    public static ItemInfoMatcher ofItemIds(
+            final LongArrayMap<Boolean> ids, final Boolean matchDefault) {
+        return new ItemInfoMatcher() {
+            @Override
+            public boolean matches(ItemInfo info, ComponentName cn) {
+                return ids.get(info.id, matchDefault);
+            }
+        };
+    }
 }