diff --git a/res/values/integers.xml b/res/values/integers.xml
new file mode 100644
index 0000000..7d26d85
--- /dev/null
+++ b/res/values/integers.xml
@@ -0,0 +1,22 @@
+<?xml version="1.0" encoding="utf-8"?>
+<!--
+/*
+* 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.
+*/
+-->
+
+<resources>
+    <integer name="promise_icon_alpha">127</integer>
+</resources>
\ No newline at end of file
diff --git a/res/values/strings.xml b/res/values/strings.xml
index 9cb6c29..8ba58e5 100644
--- a/res/values/strings.xml
+++ b/res/values/strings.xml
@@ -262,4 +262,15 @@
     <string name="wallpaper_button_text">Wallpapers</string>
     <!-- Text for settings button -->
     <string name="settings_button_text">Settings</string>
+
+    <!-- Label on an icon that references an uninstalled package, that is going to be installed at some point. [CHAR_LIMIT=15] -->
+    <string name="package_state_enqueued">Waiting</string>
+    <!-- Label on an icon that references an uninstalled package, that is currently being downloaded. [CHAR_LIMIT=15] -->
+    <string name="package_state_downloading">Downloading</string>
+    <!-- Label on an icon that references an uninstalled package, that is currently being installed. [CHAR_LIMIT=15] -->
+    <string name="package_state_installing">Installing</string>
+    <!-- Label on an icon that references an uninstalled package, for which we have no information about when it might be installed. [CHAR_LIMIT=15] -->
+    <string name="package_state_unknown">Unknown</string>
+    <!-- Label on an icon that references an uninstalled package, for which restore from market has failed. [CHAR_LIMIT=15] -->
+    <string name="package_state_error">Error</string>
 </resources>
diff --git a/src/com/android/launcher3/BubbleTextView.java b/src/com/android/launcher3/BubbleTextView.java
index ee42904..c180d32 100644
--- a/src/com/android/launcher3/BubbleTextView.java
+++ b/src/com/android/launcher3/BubbleTextView.java
@@ -25,6 +25,7 @@
 import android.graphics.Region.Op;
 import android.graphics.drawable.Drawable;
 import android.util.AttributeSet;
+import android.util.Log;
 import android.util.TypedValue;
 import android.view.MotionEvent;
 import android.widget.TextView;
@@ -43,6 +44,10 @@
     static final float PADDING_H = 8.0f;
     static final float PADDING_V = 3.0f;
 
+    private static final String TAG = "BubbleTextView";
+
+    private static final boolean DEBUG = false;
+
     private int mPrevAlpha = -1;
 
     private HolographicOutlineHelper mOutlineHelper;
@@ -64,6 +69,11 @@
 
     private boolean mStayPressed;
     private CheckLongPressHelper mLongPressHelper;
+    private int mInstallState;
+
+    private int mState;
+
+    private CharSequence mDefaultText = "";
 
     public BubbleTextView(Context context) {
         super(context);
@@ -108,11 +118,14 @@
         LauncherAppState app = LauncherAppState.getInstance();
         DeviceProfile grid = app.getDynamicGrid().getDeviceProfile();
 
-        setCompoundDrawables(null,
-                Utilities.createIconDrawable(b), null, null);
+        Drawable iconDrawable = Utilities.createIconDrawable(b);
+        setCompoundDrawables(null, iconDrawable, null, null);
         setCompoundDrawablePadding(grid.iconDrawablePaddingPx);
         setText(info.title);
         setTag(info);
+        if (info.isPromise()) {
+            setState(ShortcutInfo.PACKAGE_STATE_UNKNOWN); // TODO: persist this state somewhere
+        }
     }
 
     @Override
@@ -392,4 +405,52 @@
 
         mLongPressHelper.cancelLongPress();
     }
+
+    public void setState(int state) {
+        if (mState == ShortcutInfo.PACKAGE_STATE_DEFAULT && mState != state) {
+            mDefaultText = getText();
+        }
+        mState = state;
+        applyState();
+    }
+
+    private void applyState() {
+        int alpha = getResources().getInteger(R.integer.promise_icon_alpha);
+        if (DEBUG) Log.d(TAG, "applying icon state: " + mState);
+
+        switch(mState) {
+            case ShortcutInfo.PACKAGE_STATE_DEFAULT:
+                super.setText(mDefaultText);
+                alpha = 255;
+                break;
+
+            case ShortcutInfo.PACKAGE_STATE_ENQUEUED:
+                setText(R.string.package_state_enqueued);
+                break;
+
+            case ShortcutInfo.PACKAGE_STATE_DOWNLOADING:
+                setText(R.string.package_state_downloading);
+                break;
+
+            case ShortcutInfo.PACKAGE_STATE_INSTALLING:
+                setText(R.string.package_state_installing);
+                break;
+
+            case ShortcutInfo.PACKAGE_STATE_ERROR:
+                setText(R.string.package_state_error);
+                break;
+
+            case ShortcutInfo.PACKAGE_STATE_UNKNOWN:
+            default:
+                setText(R.string.package_state_unknown);
+                break;
+        }
+        if (DEBUG) Log.d(TAG, "setting icon alpha to: " + alpha);
+        Drawable[] drawables = getCompoundDrawables();
+        for (int i = 0; i < drawables.length; i++) {
+            if (drawables[i] != null) {
+                drawables[i].setAlpha(alpha);
+            }
+        }
+    }
 }
diff --git a/src/com/android/launcher3/IconCache.java b/src/com/android/launcher3/IconCache.java
index 827718b..ee9f4d4 100644
--- a/src/com/android/launcher3/IconCache.java
+++ b/src/com/android/launcher3/IconCache.java
@@ -387,20 +387,6 @@
             }
         }
 
-        if (icon != null) {
-            // TODO: handle alpha mask in the view layer
-            Bitmap b = Bitmap.createBitmap(Math.max(icon.getWidth(), 1),
-                    Math.max(icon.getHeight(), 1),
-                    Bitmap.Config.ARGB_8888);
-            Canvas c = new Canvas(b);
-            Paint paint = new Paint();
-            paint.setAlpha(127);
-            c.drawBitmap(icon, 0, 0, paint);
-            c.setBitmap(null);
-            icon.recycle();
-            icon = b;
-        }
-
         return icon;
     }
 
diff --git a/src/com/android/launcher3/Launcher.java b/src/com/android/launcher3/Launcher.java
index 986fa21..bd1ef32 100644
--- a/src/com/android/launcher3/Launcher.java
+++ b/src/com/android/launcher3/Launcher.java
@@ -4223,6 +4223,17 @@
     }
 
     /**
+     * Update the state of a package, typically related to install state.
+     *
+     * Implementation of the method from LauncherModel.Callbacks.
+     */
+    public void updatePackageState(String pkgName, int state) {
+        if (mWorkspace != null) {
+            mWorkspace.updatePackageState(pkgName, state);
+        }
+    }
+
+    /**
      * A package was uninstalled.  We take both the super set of packageNames
      * in addition to specific applications to remove, the reason being that
      * this can be called when a package is updated as well.  In that scenario,
diff --git a/src/com/android/launcher3/LauncherAppState.java b/src/com/android/launcher3/LauncherAppState.java
index 29e18f9..ba10f51 100644
--- a/src/com/android/launcher3/LauncherAppState.java
+++ b/src/com/android/launcher3/LauncherAppState.java
@@ -30,6 +30,8 @@
     private static final String TAG = "LauncherAppState";
     private static final String SHARED_PREFERENCES_KEY = "com.android.launcher3.prefs";
 
+    private static final boolean DEBUG = true; // TODO STOPSHIP: set this to false
+
     private final AppFilter mAppFilter;
     private final BuildInfo mBuildInfo;
     private LauncherModel mModel;
@@ -249,4 +251,9 @@
     public static boolean isDogfoodBuild() {
         return getInstance().mBuildInfo.isDogfoodBuild();
     }
+
+    public void setPackageState(String pkgName, int state) {
+        if (DEBUG) Log.d(TAG, "setPackageState(" + pkgName + ", " +  state  + ")");
+        mModel.setPackageState(pkgName, state);
+    }
 }
diff --git a/src/com/android/launcher3/LauncherModel.java b/src/com/android/launcher3/LauncherModel.java
index 5f8f80c..145d225 100644
--- a/src/com/android/launcher3/LauncherModel.java
+++ b/src/com/android/launcher3/LauncherModel.java
@@ -173,6 +173,7 @@
                                   ArrayList<ItemInfo> addAnimated,
                                   ArrayList<AppInfo> addedApps);
         public void bindAppsUpdated(ArrayList<AppInfo> apps);
+        public void updatePackageState(String pkgName, int state);
         public void bindComponentsRemoved(ArrayList<String> packageNames,
                         ArrayList<AppInfo> appInfos);
         public void bindPackagesUpdated(ArrayList<Object> widgetsAndShortcuts);
@@ -296,6 +297,19 @@
         return null;
     }
 
+    public void setPackageState(final String pkgName, final int state) {
+        // Process the updated package state
+        Runnable r = new Runnable() {
+            public void run() {
+                Callbacks callbacks = mCallbacks != null ? mCallbacks.get() : null;
+                if (callbacks != null) {
+                    callbacks.updatePackageState(pkgName, state);
+                }
+            }
+        };
+        mHandler.post(r);
+    }
+
     public void addAppsToAllApps(final Context ctx, final ArrayList<AppInfo> allAppsApps) {
         final Callbacks callbacks = mCallbacks != null ? mCallbacks.get() : null;
 
@@ -2193,7 +2207,12 @@
                                 line += " | ";
                             }
                             for (int x = 0; x < countX; x++) {
-                                line += ((occupied.get(screenId)[x][y] != null) ? "#" : ".");
+                                ItemInfo[][] screen = occupied.get(screenId);
+                                if (x < screen.length && y < screen[x].length) {
+                                    line += (screen[x][y] != null) ? "#" : ".";
+                                } else {
+                                    line += "!";
+                                }
                             }
                         }
                         Log.d(TAG, "[ " + line + " ]");
diff --git a/src/com/android/launcher3/ShortcutInfo.java b/src/com/android/launcher3/ShortcutInfo.java
index 13e3ef2..ede3175 100644
--- a/src/com/android/launcher3/ShortcutInfo.java
+++ b/src/com/android/launcher3/ShortcutInfo.java
@@ -33,6 +33,24 @@
  */
 public class ShortcutInfo extends ItemInfo {
 
+    /** This package is not installed, and there is no other information available. */
+    public static final int PACKAGE_STATE_UNKNOWN = -2;
+
+    /** This package is not installed, because installation failed. */
+    public static final int PACKAGE_STATE_ERROR = -1;
+
+    /** This package is installed.  This is the typical case */
+    public static final int PACKAGE_STATE_DEFAULT = 0;
+
+    /** This package is not installed, but some external entity has promised to install it. */
+    public static final int PACKAGE_STATE_ENQUEUED = 1;
+
+    /** This package is not installed, but some external entity is downloading it. */
+    public static final int PACKAGE_STATE_DOWNLOADING = 2;
+
+    /** This package is not installed, but some external entity is installing it. */
+    public static final int PACKAGE_STATE_INSTALLING = 3;
+
     /**
      * The intent used to start the application.
      */
@@ -219,5 +237,15 @@
                     + " customIcon=" + info.customIcon);
         }
     }
+
+    public boolean isPromise() {
+        return restoredIntent != null;
+    }
+
+    public boolean isPromiseFor(String pkgName) {
+        return restoredIntent != null
+                && pkgName != null
+                && pkgName.equals(restoredIntent.getComponent().getPackageName());
+    }
 }
 
diff --git a/src/com/android/launcher3/Workspace.java b/src/com/android/launcher3/Workspace.java
index 1d413f5..a22b025 100644
--- a/src/com/android/launcher3/Workspace.java
+++ b/src/com/android/launcher3/Workspace.java
@@ -96,6 +96,9 @@
 
     private static final float ALPHA_CUTOFF_THRESHOLD = 0.01f;
 
+    private static final boolean MAP_NO_RECURSE = false;
+    private static final boolean MAP_RECURSE = true;
+
     // These animators are used to fade the children's outlines
     private ObjectAnimator mChildrenOutlineFadeInAnimation;
     private ObjectAnimator mChildrenOutlineFadeOutAnimation;
@@ -4452,51 +4455,50 @@
         return childrenLayouts;
     }
 
-    public Folder getFolderForTag(Object tag) {
-        ArrayList<ShortcutAndWidgetContainer> childrenLayouts =
-                getAllShortcutAndWidgetContainers();
-        for (ShortcutAndWidgetContainer layout: childrenLayouts) {
-            int count = layout.getChildCount();
-            for (int i = 0; i < count; i++) {
-                View child = layout.getChildAt(i);
-                if (child instanceof Folder) {
-                    Folder f = (Folder) child;
+    public Folder getFolderForTag(final Object tag) {
+        final Folder[] value = new Folder[1];
+        mapOverShortcuts(MAP_NO_RECURSE, new ShortcutOperator() {
+            @Override
+            public boolean evaluate(ItemInfo info, View v, View parent) {
+                if (v instanceof Folder) {
+                    Folder f = (Folder) v;
                     if (f.getInfo() == tag && f.getInfo().opened) {
-                        return f;
+                        value[0] = f;
+                        return true;
                     }
                 }
+                return false;
             }
-        }
-        return null;
+        });
+        return value[0];
     }
 
-    public View getViewForTag(Object tag) {
-        ArrayList<ShortcutAndWidgetContainer> childrenLayouts =
-                getAllShortcutAndWidgetContainers();
-        for (ShortcutAndWidgetContainer layout: childrenLayouts) {
-            int count = layout.getChildCount();
-            for (int i = 0; i < count; i++) {
-                View child = layout.getChildAt(i);
-                if (child.getTag() == tag) {
-                    return child;
+    public View getViewForTag(final Object tag) {
+        final View[] value = new View[1];
+        mapOverShortcuts(MAP_NO_RECURSE, new ShortcutOperator() {
+            @Override
+            public boolean evaluate(ItemInfo info, View v, View parent) {
+                if (v.getTag() == tag) {
+                    value[0] = v;
+                    return true;
                 }
+                return false;
             }
-        }
-        return null;
+        });
+        return value[0];
     }
 
     void clearDropTargets() {
-        ArrayList<ShortcutAndWidgetContainer> childrenLayouts =
-                getAllShortcutAndWidgetContainers();
-        for (ShortcutAndWidgetContainer layout: childrenLayouts) {
-            int childCount = layout.getChildCount();
-            for (int j = 0; j < childCount; j++) {
-                View v = layout.getChildAt(j);
+        mapOverShortcuts(MAP_NO_RECURSE, new ShortcutOperator() {
+            @Override
+            public boolean evaluate(ItemInfo info, View v, View parent) {
                 if (v instanceof DropTarget) {
                     mDragController.removeDropTarget((DropTarget) v);
                 }
+                // not done, process all the shortcuts
+                return false;
             }
-        }
+        });
     }
 
     // Removes ALL items that match a given package name, this is usually called when a package
@@ -4638,6 +4640,55 @@
         }
     }
 
+    interface ShortcutOperator {
+        /**
+         * Process the next shortcut, possibly with side-effect on {@link ShortcutOperator#value}.
+         *
+         * @param info info for the shortcut
+         * @param view view for the shortcut
+         * @param parent containing folder, or null
+         * @return true if done, false to continue the map
+         */
+        public boolean evaluate(ItemInfo info, View view, View parent);
+    }
+
+    /**
+     * Map the operator over the shortcuts, return the first-non-null value.
+     *
+     * @param recurse true: iterate over folder children. false: op get the folders themselves.
+     * @param op the operator to map over the shortcuts
+     */
+    void mapOverShortcuts(boolean recurse, ShortcutOperator op) {
+        ArrayList<ShortcutAndWidgetContainer> containers = getAllShortcutAndWidgetContainers();
+        final int containerCount = containers.size();
+        for (int containerIdx = 0; containerIdx < containerCount; containerIdx++) {
+            ShortcutAndWidgetContainer container = containers.get(containerIdx);
+            // map over all the shortcuts on the workspace
+            final int itemCount = container.getChildCount();
+            for (int itemIdx = 0; itemIdx < itemCount; itemIdx++) {
+                View item = container.getChildAt(itemIdx);
+                ItemInfo info = (ItemInfo) item.getTag();
+                if (recurse && info instanceof FolderInfo && item instanceof FolderIcon) {
+                    FolderIcon folder = (FolderIcon) item;
+                    ArrayList<View> folderChildren = folder.getFolder().getItemsInReadingOrder();
+                    // map over all the children in the folder
+                    final int childCount = folderChildren.size();
+                    for (int childIdx = 0; childIdx < childCount; childIdx++) {
+                        View child = folderChildren.get(childIdx);
+                        info = (ItemInfo) child.getTag();
+                        if (op.evaluate(info, child, folder)) {
+                            return;
+                        }
+                    }
+                } else {
+                    if (op.evaluate(info, item, null)) {
+                        return;
+                    }
+                }
+            }
+        }
+    }
+
     void updateShortcuts(ArrayList<AppInfo> apps) {
         // Create a map of the apps to test against
         final HashMap<ComponentName, AppInfo> appsMap = new HashMap<ComponentName, AppInfo>();
@@ -4645,26 +4696,34 @@
             appsMap.put(ai.componentName, ai);
         }
 
-        ArrayList<ShortcutAndWidgetContainer> childrenLayouts = getAllShortcutAndWidgetContainers();
-        for (ShortcutAndWidgetContainer layout: childrenLayouts) {
-            // Update all the children shortcuts
-            final HashMap<ItemInfo, View> children = new HashMap<ItemInfo, View>();
-            for (int j = 0; j < layout.getChildCount(); j++) {
-                View v = layout.getChildAt(j);
-                ItemInfo info = (ItemInfo) v.getTag();
-                if (info instanceof FolderInfo && v instanceof FolderIcon) {
-                    FolderIcon folder = (FolderIcon) v;
-                    ArrayList<View> folderChildren = folder.getFolder().getItemsInReadingOrder();
-                    for (View fv : folderChildren) {
-                        info = (ItemInfo) fv.getTag();
-                        updateShortcut(appsMap, info, fv);
-                    }
-                    folder.invalidate();
-                } else if (info instanceof ShortcutInfo) {
+        mapOverShortcuts(MAP_RECURSE, new ShortcutOperator() {
+            @Override
+            public boolean evaluate(ItemInfo info, View v, View parent) {
+                if (info instanceof ShortcutInfo) {
                     updateShortcut(appsMap, info, v);
+                    if (parent != null) {
+                        parent.invalidate();
+                    }
                 }
+                // process all the shortcuts
+                return false;
             }
-        }
+        });
+    }
+
+    public void updatePackageState(final String pkgName, final int state) {
+        mapOverShortcuts(MAP_RECURSE, new ShortcutOperator() {
+            @Override
+            public boolean evaluate(ItemInfo info, View v, View parent) {
+                if (info instanceof ShortcutInfo
+                        && ((ShortcutInfo) info).isPromiseFor(pkgName)
+                        && v instanceof BubbleTextView) {
+                    ((BubbleTextView)v).setState(state);
+                }
+                // process all the shortcuts
+                return false;
+            }
+        });
     }
 
     private void moveToScreen(int page, boolean animate) {