/*
 * Copyright (C) 2015 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.Nullable;
import android.annotation.UserIdInt;
import android.content.Intent;
import android.content.pm.InstantAppInfo;
import android.content.pm.PackageManager;
import android.content.pm.PackageParser;
import android.graphics.Bitmap;
import android.graphics.BitmapFactory;
import android.graphics.Canvas;
import android.graphics.drawable.BitmapDrawable;
import android.graphics.drawable.Drawable;
import android.os.Binder;
import android.os.Environment;
import android.os.Handler;
import android.os.Looper;
import android.os.Message;
import android.os.UserHandle;
import android.os.storage.StorageManager;
import android.provider.Settings;
import android.util.ArrayMap;
import android.util.AtomicFile;
import android.util.ByteStringUtils;
import android.util.PackageUtils;
import android.util.Slog;
import android.util.SparseArray;
import android.util.SparseBooleanArray;
import android.util.Xml;
import com.android.internal.annotations.GuardedBy;
import com.android.internal.os.BackgroundThread;
import com.android.internal.os.SomeArgs;
import com.android.internal.util.ArrayUtils;
import com.android.internal.util.XmlUtils;
import libcore.io.IoUtils;
import org.xmlpull.v1.XmlPullParser;
import org.xmlpull.v1.XmlPullParserException;
import org.xmlpull.v1.XmlSerializer;

import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.security.SecureRandom;
import java.util.ArrayList;
import java.util.List;
import java.util.Locale;
import java.util.Set;
import java.util.function.Predicate;

/**
 * This class is a part of the package manager service that is responsible
 * for managing data associated with instant apps such as cached uninstalled
 * instant apps and instant apps' cookies. In addition it is responsible for
 * pruning installed instant apps and meta-data for uninstalled instant apps
 * when free space is needed.
 */
class InstantAppRegistry {
    private static final boolean DEBUG = false;

    private static final String LOG_TAG = "InstantAppRegistry";

    static final long DEFAULT_INSTALLED_INSTANT_APP_MIN_CACHE_PERIOD =
            DEBUG ? 30 * 1000L /* thirty seconds */ : 7 * 24 * 60 * 60 * 1000L; /* one week */

    private static final long DEFAULT_INSTALLED_INSTANT_APP_MAX_CACHE_PERIOD =
            DEBUG ? 60 * 1000L /* one min */ : 6 * 30 * 24 * 60 * 60 * 1000L; /* six months */

    static final long DEFAULT_UNINSTALLED_INSTANT_APP_MIN_CACHE_PERIOD =
            DEBUG ? 30 * 1000L /* thirty seconds */ : 7 * 24 * 60 * 60 * 1000L; /* one week */

    private static final long DEFAULT_UNINSTALLED_INSTANT_APP_MAX_CACHE_PERIOD =
            DEBUG ? 60 * 1000L /* one min */ : 6 * 30 * 24 * 60 * 60 * 1000L; /* six months */

    private static final String INSTANT_APPS_FOLDER = "instant";
    private static final String INSTANT_APP_ICON_FILE = "icon.png";
    private static final String INSTANT_APP_COOKIE_FILE_PREFIX = "cookie_";
    private static final String INSTANT_APP_COOKIE_FILE_SIFFIX = ".dat";
    private static final String INSTANT_APP_METADATA_FILE = "metadata.xml";
    private static final String INSTANT_APP_ANDROID_ID_FILE = "android_id";

    private static final String TAG_PACKAGE = "package";
    private static final String TAG_PERMISSIONS = "permissions";
    private static final String TAG_PERMISSION = "permission";

    private static final String ATTR_LABEL = "label";
    private static final String ATTR_NAME = "name";
    private static final String ATTR_GRANTED = "granted";

    private final PackageManagerService mService;
    private final CookiePersistence mCookiePersistence;

    /** State for uninstalled instant apps */
    @GuardedBy("mService.mPackages")
    private SparseArray<List<UninstalledInstantAppState>> mUninstalledInstantApps;

    /**
     * Automatic grants for access to instant app metadata.
     * The key is the target application UID.
     * The value is a set of instant app UIDs.
     * UserID -> TargetAppId -> InstantAppId
     */
    @GuardedBy("mService.mPackages")
    private SparseArray<SparseArray<SparseBooleanArray>> mInstantGrants;

    /** The set of all installed instant apps. UserID -> AppID */
    @GuardedBy("mService.mPackages")
    private SparseArray<SparseBooleanArray> mInstalledInstantAppUids;

    public InstantAppRegistry(PackageManagerService service) {
        mService = service;
        mCookiePersistence = new CookiePersistence(BackgroundThread.getHandler().getLooper());
    }

    public byte[] getInstantAppCookieLPw(@NonNull String packageName,
            @UserIdInt int userId) {
        // Only installed packages can get their own cookie
        PackageParser.Package pkg = mService.mPackages.get(packageName);
        if (pkg == null) {
            return null;
        }

        byte[] pendingCookie = mCookiePersistence.getPendingPersistCookieLPr(pkg, userId);
        if (pendingCookie != null) {
            return pendingCookie;
        }
        File cookieFile = peekInstantCookieFile(packageName, userId);
        if (cookieFile != null && cookieFile.exists()) {
            try {
                return IoUtils.readFileAsByteArray(cookieFile.toString());
            } catch (IOException e) {
                Slog.w(LOG_TAG, "Error reading cookie file: " + cookieFile);
            }
        }
        return null;
    }

    public boolean setInstantAppCookieLPw(@NonNull String packageName,
            @Nullable byte[] cookie, @UserIdInt int userId) {
        if (cookie != null && cookie.length > 0) {
            final int maxCookieSize = mService.mContext.getPackageManager()
                    .getInstantAppCookieMaxBytes();
            if (cookie.length > maxCookieSize) {
                Slog.e(LOG_TAG, "Instant app cookie for package " + packageName + " size "
                        + cookie.length + " bytes while max size is " + maxCookieSize);
                return false;
            }
        }

        // Only an installed package can set its own cookie
        PackageParser.Package pkg = mService.mPackages.get(packageName);
        if (pkg == null) {
            return false;
        }

        mCookiePersistence.schedulePersistLPw(userId, pkg, cookie);
        return true;
    }

    private void persistInstantApplicationCookie(@Nullable byte[] cookie,
            @NonNull String packageName, @NonNull File cookieFile, @UserIdInt int userId) {
        synchronized (mService.mPackages) {
            File appDir = getInstantApplicationDir(packageName, userId);
            if (!appDir.exists() && !appDir.mkdirs()) {
                Slog.e(LOG_TAG, "Cannot create instant app cookie directory");
                return;
            }

            if (cookieFile.exists() && !cookieFile.delete()) {
                Slog.e(LOG_TAG, "Cannot delete instant app cookie file");
            }

            // No cookie or an empty one means delete - done
            if (cookie == null || cookie.length <= 0) {
                return;
            }
        }
        try (FileOutputStream fos = new FileOutputStream(cookieFile)) {
            fos.write(cookie, 0, cookie.length);
        } catch (IOException e) {
            Slog.e(LOG_TAG, "Error writing instant app cookie file: " + cookieFile, e);
        }
    }

    public Bitmap getInstantAppIconLPw(@NonNull String packageName,
                                       @UserIdInt int userId) {
        File iconFile = new File(getInstantApplicationDir(packageName, userId),
                INSTANT_APP_ICON_FILE);
        if (iconFile.exists()) {
            return BitmapFactory.decodeFile(iconFile.toString());
        }
        return null;
    }

    public String getInstantAppAndroidIdLPw(@NonNull String packageName,
                                            @UserIdInt int userId) {
        File idFile = new File(getInstantApplicationDir(packageName, userId),
                INSTANT_APP_ANDROID_ID_FILE);
        if (idFile.exists()) {
            try {
                return IoUtils.readFileAsString(idFile.getAbsolutePath());
            } catch (IOException e) {
                Slog.e(LOG_TAG, "Failed to read instant app android id file: " + idFile, e);
            }
        }
        return generateInstantAppAndroidIdLPw(packageName, userId);
    }

    private String generateInstantAppAndroidIdLPw(@NonNull String packageName,
                                                @UserIdInt int userId) {
        byte[] randomBytes = new byte[8];
        new SecureRandom().nextBytes(randomBytes);
        String id = ByteStringUtils.toHexString(randomBytes).toLowerCase(Locale.US);
        File appDir = getInstantApplicationDir(packageName, userId);
        if (!appDir.exists() && !appDir.mkdirs()) {
            Slog.e(LOG_TAG, "Cannot create instant app cookie directory");
            return id;
        }
        File idFile = new File(getInstantApplicationDir(packageName, userId),
                INSTANT_APP_ANDROID_ID_FILE);
        try (FileOutputStream fos = new FileOutputStream(idFile)) {
            fos.write(id.getBytes());
        } catch (IOException e) {
            Slog.e(LOG_TAG, "Error writing instant app android id file: " + idFile, e);
        }
        return id;

    }

    public @Nullable List<InstantAppInfo> getInstantAppsLPr(@UserIdInt int userId) {
        List<InstantAppInfo> installedApps = getInstalledInstantApplicationsLPr(userId);
        List<InstantAppInfo> uninstalledApps = getUninstalledInstantApplicationsLPr(userId);
        if (installedApps != null) {
            if (uninstalledApps != null) {
                installedApps.addAll(uninstalledApps);
            }
            return installedApps;
        }
        return uninstalledApps;
    }

    public void onPackageInstalledLPw(@NonNull PackageParser.Package pkg, @NonNull int[] userIds) {
        PackageSetting ps = (PackageSetting) pkg.mExtras;
        if (ps == null) {
            return;
        }

        for (int userId : userIds) {
            // Ignore not installed apps
            if (mService.mPackages.get(pkg.packageName) == null || !ps.getInstalled(userId)) {
                continue;
            }

            // Propagate permissions before removing any state
            propagateInstantAppPermissionsIfNeeded(pkg.packageName, userId);

            // Track instant apps
            if (ps.getInstantApp(userId)) {
                addInstantAppLPw(userId, ps.appId);
            }

            // Remove the in-memory state
            removeUninstalledInstantAppStateLPw((UninstalledInstantAppState state) ->
                            state.mInstantAppInfo.getPackageName().equals(pkg.packageName),
                    userId);

            // Remove the on-disk state except the cookie
            File instantAppDir = getInstantApplicationDir(pkg.packageName, userId);
            new File(instantAppDir, INSTANT_APP_METADATA_FILE).delete();
            new File(instantAppDir, INSTANT_APP_ICON_FILE).delete();

            // If app signature changed - wipe the cookie
            File currentCookieFile = peekInstantCookieFile(pkg.packageName, userId);
            if (currentCookieFile == null) {
                continue;
            }
            File expectedCookeFile = computeInstantCookieFile(pkg, userId);
            if (!currentCookieFile.equals(expectedCookeFile)) {
                Slog.i(LOG_TAG, "Signature for package " + pkg.packageName
                        + " changed - dropping cookie");
                // Make sure a pending write for the old signed app is cancelled
                mCookiePersistence.cancelPendingPersistLPw(pkg, userId);
                currentCookieFile.delete();
            }
        }
    }

    public void onPackageUninstalledLPw(@NonNull PackageParser.Package pkg,
            @NonNull int[] userIds) {
        PackageSetting ps = (PackageSetting) pkg.mExtras;
        if (ps == null) {
            return;
        }

        for (int userId : userIds) {
            if (mService.mPackages.get(pkg.packageName) != null && ps.getInstalled(userId)) {
                continue;
            }

            if (ps.getInstantApp(userId)) {
                // Add a record for an uninstalled instant app
                addUninstalledInstantAppLPw(pkg, userId);
                removeInstantAppLPw(userId, ps.appId);
            } else {
                // Deleting an app prunes all instant state such as cookie
                deleteDir(getInstantApplicationDir(pkg.packageName, userId));
                mCookiePersistence.cancelPendingPersistLPw(pkg, userId);
                removeAppLPw(userId, ps.appId);
            }
        }
    }

    public void onUserRemovedLPw(int userId) {
        if (mUninstalledInstantApps != null) {
            mUninstalledInstantApps.remove(userId);
            if (mUninstalledInstantApps.size() <= 0) {
                mUninstalledInstantApps = null;
            }
        }
        if (mInstalledInstantAppUids != null) {
            mInstalledInstantAppUids.remove(userId);
            if (mInstalledInstantAppUids.size() <= 0) {
                mInstalledInstantAppUids = null;
            }
        }
        if (mInstantGrants != null) {
            mInstantGrants.remove(userId);
            if (mInstantGrants.size() <= 0) {
                mInstantGrants = null;
            }
        }
        deleteDir(getInstantApplicationsDir(userId));
    }

    public boolean isInstantAccessGranted(@UserIdInt int userId, int targetAppId,
            int instantAppId) {
        if (mInstantGrants == null) {
            return false;
        }
        final SparseArray<SparseBooleanArray> targetAppList = mInstantGrants.get(userId);
        if (targetAppList == null) {
            return false;
        }
        final SparseBooleanArray instantGrantList = targetAppList.get(targetAppId);
        if (instantGrantList == null) {
            return false;
        }
        return instantGrantList.get(instantAppId);
    }

    public void grantInstantAccessLPw(@UserIdInt int userId, @Nullable Intent intent,
            int targetAppId, int instantAppId) {
        if (mInstalledInstantAppUids == null) {
            return;     // no instant apps installed; no need to grant
        }
        SparseBooleanArray instantAppList = mInstalledInstantAppUids.get(userId);
        if (instantAppList == null || !instantAppList.get(instantAppId)) {
            return;     // instant app id isn't installed; no need to grant
        }
        if (instantAppList.get(targetAppId)) {
            return;     // target app id is an instant app; no need to grant
        }
        if (intent != null && Intent.ACTION_VIEW.equals(intent.getAction())) {
            final Set<String> categories = intent.getCategories();
            if (categories != null && categories.contains(Intent.CATEGORY_BROWSABLE)) {
                return;  // launched via VIEW/BROWSABLE intent; no need to grant
            }
        }
        if (mInstantGrants == null) {
            mInstantGrants = new SparseArray<>();
        }
        SparseArray<SparseBooleanArray> targetAppList = mInstantGrants.get(userId);
        if (targetAppList == null) {
            targetAppList = new SparseArray<>();
            mInstantGrants.put(userId, targetAppList);
        }
        SparseBooleanArray instantGrantList = targetAppList.get(targetAppId);
        if (instantGrantList == null) {
            instantGrantList = new SparseBooleanArray();
            targetAppList.put(targetAppId, instantGrantList);
        }
        instantGrantList.put(instantAppId, true /*granted*/);
    }

    public void addInstantAppLPw(@UserIdInt int userId, int instantAppId) {
        if (mInstalledInstantAppUids == null) {
            mInstalledInstantAppUids = new SparseArray<>();
        }
        SparseBooleanArray instantAppList = mInstalledInstantAppUids.get(userId);
        if (instantAppList == null) {
            instantAppList = new SparseBooleanArray();
            mInstalledInstantAppUids.put(userId, instantAppList);
        }
        instantAppList.put(instantAppId, true /*installed*/);
    }

    private void removeInstantAppLPw(@UserIdInt int userId, int instantAppId) {
        // remove from the installed list
        if (mInstalledInstantAppUids == null) {
            return; // no instant apps on the system
        }
        final SparseBooleanArray instantAppList = mInstalledInstantAppUids.get(userId);
        if (instantAppList == null) {
            return;
        }

        instantAppList.delete(instantAppId);

        // remove any grants
        if (mInstantGrants == null) {
            return; // no grants on the system
        }
        final SparseArray<SparseBooleanArray> targetAppList = mInstantGrants.get(userId);
        if (targetAppList == null) {
            return; // no grants for this user
        }
        for (int i = targetAppList.size() - 1; i >= 0; --i) {
            targetAppList.valueAt(i).delete(instantAppId);
        }
    }

    private void removeAppLPw(@UserIdInt int userId, int targetAppId) {
        // remove from the installed list
        if (mInstantGrants == null) {
            return; // no grants on the system
        }
        final SparseArray<SparseBooleanArray> targetAppList = mInstantGrants.get(userId);
        if (targetAppList == null) {
            return; // no grants for this user
        }
        targetAppList.delete(targetAppId);
    }

    private void addUninstalledInstantAppLPw(@NonNull PackageParser.Package pkg,
            @UserIdInt int userId) {
        InstantAppInfo uninstalledApp = createInstantAppInfoForPackage(
                pkg, userId, false);
        if (uninstalledApp == null) {
            return;
        }
        if (mUninstalledInstantApps == null) {
            mUninstalledInstantApps = new SparseArray<>();
        }
        List<UninstalledInstantAppState> uninstalledAppStates =
                mUninstalledInstantApps.get(userId);
        if (uninstalledAppStates == null) {
            uninstalledAppStates = new ArrayList<>();
            mUninstalledInstantApps.put(userId, uninstalledAppStates);
        }
        UninstalledInstantAppState uninstalledAppState = new UninstalledInstantAppState(
                uninstalledApp, System.currentTimeMillis());
        uninstalledAppStates.add(uninstalledAppState);

        writeUninstalledInstantAppMetadata(uninstalledApp, userId);
        writeInstantApplicationIconLPw(pkg, userId);
    }

    private void writeInstantApplicationIconLPw(@NonNull PackageParser.Package pkg,
            @UserIdInt int userId) {
        File appDir = getInstantApplicationDir(pkg.packageName, userId);
        if (!appDir.exists()) {
            return;
        }

        Drawable icon = pkg.applicationInfo.loadIcon(mService.mContext.getPackageManager());

        final Bitmap bitmap;
        if (icon instanceof BitmapDrawable) {
            bitmap = ((BitmapDrawable) icon).getBitmap();
        } else  {
            bitmap = Bitmap.createBitmap(icon.getIntrinsicWidth(),
                    icon.getIntrinsicHeight(), Bitmap.Config.ARGB_8888);
            Canvas canvas = new Canvas(bitmap);
            icon.setBounds(0, 0, icon.getIntrinsicWidth(), icon.getIntrinsicHeight());
            icon.draw(canvas);
        }

        File iconFile = new File(getInstantApplicationDir(pkg.packageName, userId),
                INSTANT_APP_ICON_FILE);

        try (FileOutputStream out = new FileOutputStream(iconFile)) {
            bitmap.compress(Bitmap.CompressFormat.PNG, 100, out);
        } catch (Exception e) {
            Slog.e(LOG_TAG, "Error writing instant app icon", e);
        }
    }

    public void deleteInstantApplicationMetadataLPw(@NonNull String packageName,
            @UserIdInt int userId) {
        removeUninstalledInstantAppStateLPw((UninstalledInstantAppState state) ->
                state.mInstantAppInfo.getPackageName().equals(packageName),
                userId);

        File instantAppDir = getInstantApplicationDir(packageName, userId);
        new File(instantAppDir, INSTANT_APP_METADATA_FILE).delete();
        new File(instantAppDir, INSTANT_APP_ICON_FILE).delete();
        new File(instantAppDir, INSTANT_APP_ANDROID_ID_FILE).delete();
        File cookie = peekInstantCookieFile(packageName, userId);
        if (cookie != null) {
            cookie.delete();
        }
    }

    private void removeUninstalledInstantAppStateLPw(
            @NonNull Predicate<UninstalledInstantAppState> criteria, @UserIdInt int userId) {
        if (mUninstalledInstantApps == null) {
            return;
        }
        List<UninstalledInstantAppState> uninstalledAppStates =
                mUninstalledInstantApps.get(userId);
        if (uninstalledAppStates == null) {
            return;
        }
        final int appCount = uninstalledAppStates.size();
        for (int i = appCount - 1; i >= 0; --i) {
            UninstalledInstantAppState uninstalledAppState = uninstalledAppStates.get(i);
            if (!criteria.test(uninstalledAppState)) {
                continue;
            }
            uninstalledAppStates.remove(i);
            if (uninstalledAppStates.isEmpty()) {
                mUninstalledInstantApps.remove(userId);
                if (mUninstalledInstantApps.size() <= 0) {
                    mUninstalledInstantApps = null;
                }
                return;
            }
        }
    }

    void pruneInstantApps() {
        final long maxInstalledCacheDuration = Settings.Global.getLong(
                mService.mContext.getContentResolver(),
                Settings.Global.INSTALLED_INSTANT_APP_MAX_CACHE_PERIOD,
                DEFAULT_INSTALLED_INSTANT_APP_MAX_CACHE_PERIOD);

        final long maxUninstalledCacheDuration = Settings.Global.getLong(
                mService.mContext.getContentResolver(),
                Settings.Global.UNINSTALLED_INSTANT_APP_MAX_CACHE_PERIOD,
                DEFAULT_UNINSTALLED_INSTANT_APP_MAX_CACHE_PERIOD);

        try {
            pruneInstantApps(Long.MAX_VALUE,
                    maxInstalledCacheDuration, maxUninstalledCacheDuration);
        } catch (IOException e) {
            Slog.e(LOG_TAG, "Error pruning installed and uninstalled instant apps", e);
        }
    }

    boolean pruneInstalledInstantApps(long neededSpace, long maxInstalledCacheDuration) {
        try {
            return pruneInstantApps(neededSpace, maxInstalledCacheDuration, Long.MAX_VALUE);
        } catch (IOException e) {
            Slog.e(LOG_TAG, "Error pruning installed instant apps", e);
            return false;
        }
    }

    boolean pruneUninstalledInstantApps(long neededSpace, long maxUninstalledCacheDuration) {
        try {
            return pruneInstantApps(neededSpace, Long.MAX_VALUE, maxUninstalledCacheDuration);
        } catch (IOException e) {
            Slog.e(LOG_TAG, "Error pruning uninstalled instant apps", e);
            return false;
        }
    }

    /**
     * Prunes instant apps until there is enough <code>neededSpace</code>. Both
     * installed and uninstalled instant apps are pruned that are older than
     * <code>maxInstalledCacheDuration</code> and <code>maxUninstalledCacheDuration</code>
     * respectively. All times are in milliseconds.
     *
     * @param neededSpace The space to ensure is free.
     * @param maxInstalledCacheDuration The max duration for caching installed apps in millis.
     * @param maxUninstalledCacheDuration The max duration for caching uninstalled apps in millis.
     * @return Whether enough space was freed.
     *
     * @throws IOException
     */
    private boolean pruneInstantApps(long neededSpace, long maxInstalledCacheDuration,
            long maxUninstalledCacheDuration) throws IOException {
        final StorageManager storage = mService.mContext.getSystemService(StorageManager.class);
        final File file = storage.findPathForUuid(StorageManager.UUID_PRIVATE_INTERNAL);

        if (file.getUsableSpace() >= neededSpace) {
            return true;
        }

        List<String> packagesToDelete = null;

        final int[] allUsers;
        final long now = System.currentTimeMillis();

        // Prune first installed instant apps
        synchronized (mService.mPackages) {
            allUsers = PackageManagerService.sUserManager.getUserIds();

            final int packageCount = mService.mPackages.size();
            for (int i = 0; i < packageCount; i++) {
                final PackageParser.Package pkg = mService.mPackages.valueAt(i);
                if (now - pkg.getLatestPackageUseTimeInMills() < maxInstalledCacheDuration) {
                    continue;
                }
                if (!(pkg.mExtras instanceof PackageSetting)) {
                    continue;
                }
                final PackageSetting  ps = (PackageSetting) pkg.mExtras;
                boolean installedOnlyAsInstantApp = false;
                for (int userId : allUsers) {
                    if (ps.getInstalled(userId)) {
                        if (ps.getInstantApp(userId)) {
                            installedOnlyAsInstantApp = true;
                        } else {
                            installedOnlyAsInstantApp = false;
                            break;
                        }
                    }
                }
                if (installedOnlyAsInstantApp) {
                    if (packagesToDelete == null) {
                        packagesToDelete = new ArrayList<>();
                    }
                    packagesToDelete.add(pkg.packageName);
                }
            }

            if (packagesToDelete != null) {
                packagesToDelete.sort((String lhs, String rhs) -> {
                    final PackageParser.Package lhsPkg = mService.mPackages.get(lhs);
                    final PackageParser.Package rhsPkg = mService.mPackages.get(rhs);
                    if (lhsPkg == null && rhsPkg == null) {
                        return 0;
                    } else if (lhsPkg == null) {
                        return -1;
                    } else if (rhsPkg == null) {
                        return 1;
                    } else {
                        if (lhsPkg.getLatestPackageUseTimeInMills() >
                                rhsPkg.getLatestPackageUseTimeInMills()) {
                            return 1;
                        } else if (lhsPkg.getLatestPackageUseTimeInMills() <
                                rhsPkg.getLatestPackageUseTimeInMills()) {
                            return -1;
                        } else {
                            if (lhsPkg.mExtras instanceof PackageSetting
                                    && rhsPkg.mExtras instanceof PackageSetting) {
                                final PackageSetting lhsPs = (PackageSetting) lhsPkg.mExtras;
                                final PackageSetting rhsPs = (PackageSetting) rhsPkg.mExtras;
                                if (lhsPs.firstInstallTime > rhsPs.firstInstallTime) {
                                    return 1;
                                } else {
                                    return -1;
                                }
                            } else {
                                return 0;
                            }
                        }
                    }
                });
            }
        }

        if (packagesToDelete != null) {
            final int packageCount = packagesToDelete.size();
            for (int i = 0; i < packageCount; i++) {
                final String packageToDelete = packagesToDelete.get(i);
                if (mService.deletePackageX(packageToDelete, PackageManager.VERSION_CODE_HIGHEST,
                        UserHandle.USER_SYSTEM, PackageManager.DELETE_ALL_USERS)
                                == PackageManager.DELETE_SUCCEEDED) {
                    if (file.getUsableSpace() >= neededSpace) {
                        return true;
                    }
                }
            }
        }

        // Prune uninstalled instant apps
        synchronized (mService.mPackages) {
            // TODO: Track last used time for uninstalled instant apps for better pruning
            for (int userId : UserManagerService.getInstance().getUserIds()) {
                // Prune in-memory state
                removeUninstalledInstantAppStateLPw((UninstalledInstantAppState state) -> {
                    final long elapsedCachingMillis = System.currentTimeMillis() - state.mTimestamp;
                    return (elapsedCachingMillis > maxUninstalledCacheDuration);
                }, userId);

                // Prune on-disk state
                File instantAppsDir = getInstantApplicationsDir(userId);
                if (!instantAppsDir.exists()) {
                    continue;
                }
                File[] files = instantAppsDir.listFiles();
                if (files == null) {
                    continue;
                }
                for (File instantDir : files) {
                    if (!instantDir.isDirectory()) {
                        continue;
                    }

                    File metadataFile = new File(instantDir, INSTANT_APP_METADATA_FILE);
                    if (!metadataFile.exists()) {
                        continue;
                    }

                    final long elapsedCachingMillis = System.currentTimeMillis()
                            - metadataFile.lastModified();
                    if (elapsedCachingMillis > maxUninstalledCacheDuration) {
                        deleteDir(instantDir);
                        if (file.getUsableSpace() >= neededSpace) {
                            return true;
                        }
                    }
                }
            }
        }

        return false;
    }

    private @Nullable List<InstantAppInfo> getInstalledInstantApplicationsLPr(
            @UserIdInt int userId) {
        List<InstantAppInfo> result = null;

        final int packageCount = mService.mPackages.size();
        for (int i = 0; i < packageCount; i++) {
            final PackageParser.Package pkg = mService.mPackages.valueAt(i);
            final PackageSetting ps = (PackageSetting) pkg.mExtras;
            if (ps == null || !ps.getInstantApp(userId)) {
                continue;
            }
            final InstantAppInfo info = createInstantAppInfoForPackage(
                    pkg, userId, true);
            if (info == null) {
                continue;
            }
            if (result == null) {
                result = new ArrayList<>();
            }
            result.add(info);
        }

        return result;
    }

    private @NonNull
    InstantAppInfo createInstantAppInfoForPackage(
            @NonNull PackageParser.Package pkg, @UserIdInt int userId,
            boolean addApplicationInfo) {
        PackageSetting ps = (PackageSetting) pkg.mExtras;
        if (ps == null) {
            return null;
        }
        if (!ps.getInstalled(userId)) {
            return null;
        }

        String[] requestedPermissions = new String[pkg.requestedPermissions.size()];
        pkg.requestedPermissions.toArray(requestedPermissions);

        Set<String> permissions = ps.getPermissionsState().getPermissions(userId);
        String[] grantedPermissions = new String[permissions.size()];
        permissions.toArray(grantedPermissions);

        if (addApplicationInfo) {
            return new InstantAppInfo(pkg.applicationInfo,
                    requestedPermissions, grantedPermissions);
        } else {
            return new InstantAppInfo(pkg.applicationInfo.packageName,
                    pkg.applicationInfo.loadLabel(mService.mContext.getPackageManager()),
                    requestedPermissions, grantedPermissions);
        }
    }

    private @Nullable List<InstantAppInfo> getUninstalledInstantApplicationsLPr(
            @UserIdInt int userId) {
        List<UninstalledInstantAppState> uninstalledAppStates =
                getUninstalledInstantAppStatesLPr(userId);
        if (uninstalledAppStates == null || uninstalledAppStates.isEmpty()) {
            return null;
        }

        List<InstantAppInfo> uninstalledApps = null;
        final int stateCount = uninstalledAppStates.size();
        for (int i = 0; i < stateCount; i++) {
            UninstalledInstantAppState uninstalledAppState = uninstalledAppStates.get(i);
            if (uninstalledApps == null) {
                uninstalledApps = new ArrayList<>();
            }
            uninstalledApps.add(uninstalledAppState.mInstantAppInfo);
        }
        return uninstalledApps;
    }

    private void propagateInstantAppPermissionsIfNeeded(@NonNull String packageName,
            @UserIdInt int userId) {
        InstantAppInfo appInfo = peekOrParseUninstalledInstantAppInfo(
                packageName, userId);
        if (appInfo == null) {
            return;
        }
        if (ArrayUtils.isEmpty(appInfo.getGrantedPermissions())) {
            return;
        }
        final long identity = Binder.clearCallingIdentity();
        try {
            for (String grantedPermission : appInfo.getGrantedPermissions()) {
                BasePermission bp = mService.mSettings.mPermissions.get(grantedPermission);
                if (bp != null && (bp.isRuntime() || bp.isDevelopment()) && bp.isInstant()) {
                    mService.grantRuntimePermission(packageName, grantedPermission, userId);
                }
            }
        } finally {
            Binder.restoreCallingIdentity(identity);
        }
    }

    private @NonNull
    InstantAppInfo peekOrParseUninstalledInstantAppInfo(
            @NonNull String packageName, @UserIdInt int userId) {
        if (mUninstalledInstantApps != null) {
            List<UninstalledInstantAppState> uninstalledAppStates =
                    mUninstalledInstantApps.get(userId);
            if (uninstalledAppStates != null) {
                final int appCount = uninstalledAppStates.size();
                for (int i = 0; i < appCount; i++) {
                    UninstalledInstantAppState uninstalledAppState = uninstalledAppStates.get(i);
                    if (uninstalledAppState.mInstantAppInfo
                            .getPackageName().equals(packageName)) {
                        return uninstalledAppState.mInstantAppInfo;
                    }
                }
            }
        }

        File metadataFile = new File(getInstantApplicationDir(packageName, userId),
                INSTANT_APP_METADATA_FILE);
        UninstalledInstantAppState uninstalledAppState = parseMetadataFile(metadataFile);
        if (uninstalledAppState == null) {
            return null;
        }

        return uninstalledAppState.mInstantAppInfo;
    }

    private @Nullable List<UninstalledInstantAppState> getUninstalledInstantAppStatesLPr(
            @UserIdInt int userId) {
        List<UninstalledInstantAppState> uninstalledAppStates = null;
        if (mUninstalledInstantApps != null) {
            uninstalledAppStates = mUninstalledInstantApps.get(userId);
            if (uninstalledAppStates != null) {
                return uninstalledAppStates;
            }
        }

        File instantAppsDir = getInstantApplicationsDir(userId);
        if (instantAppsDir.exists()) {
            File[] files = instantAppsDir.listFiles();
            if (files != null) {
                for (File instantDir : files) {
                    if (!instantDir.isDirectory()) {
                        continue;
                    }
                    File metadataFile = new File(instantDir,
                            INSTANT_APP_METADATA_FILE);
                    UninstalledInstantAppState uninstalledAppState =
                            parseMetadataFile(metadataFile);
                    if (uninstalledAppState == null) {
                        continue;
                    }
                    if (uninstalledAppStates == null) {
                        uninstalledAppStates = new ArrayList<>();
                    }
                    uninstalledAppStates.add(uninstalledAppState);
                }
            }
        }

        if (uninstalledAppStates != null) {
            if (mUninstalledInstantApps == null) {
                mUninstalledInstantApps = new SparseArray<>();
            }
            mUninstalledInstantApps.put(userId, uninstalledAppStates);
        }

        return uninstalledAppStates;
    }

    private static @Nullable UninstalledInstantAppState parseMetadataFile(
            @NonNull File metadataFile) {
        if (!metadataFile.exists()) {
            return null;
        }
        FileInputStream in;
        try {
            in = new AtomicFile(metadataFile).openRead();
        } catch (FileNotFoundException fnfe) {
            Slog.i(LOG_TAG, "No instant metadata file");
            return null;
        }

        final File instantDir = metadataFile.getParentFile();
        final long timestamp = metadataFile.lastModified();
        final String packageName = instantDir.getName();

        try {
            XmlPullParser parser = Xml.newPullParser();
            parser.setInput(in, StandardCharsets.UTF_8.name());
            return new UninstalledInstantAppState(
                    parseMetadata(parser, packageName), timestamp);
        } catch (XmlPullParserException | IOException e) {
            throw new IllegalStateException("Failed parsing instant"
                    + " metadata file: " + metadataFile, e);
        } finally {
            IoUtils.closeQuietly(in);
        }
    }

    private static @NonNull File computeInstantCookieFile(@NonNull PackageParser.Package pkg,
            @UserIdInt int userId) {
        File appDir = getInstantApplicationDir(pkg.packageName, userId);
        String cookieFile = INSTANT_APP_COOKIE_FILE_PREFIX + PackageUtils.computeSha256Digest(
                pkg.mSignatures[0].toByteArray()) + INSTANT_APP_COOKIE_FILE_SIFFIX;
        return new File(appDir, cookieFile);
    }

    private static @Nullable File peekInstantCookieFile(@NonNull String packageName,
            @UserIdInt int userId) {
        File appDir = getInstantApplicationDir(packageName, userId);
        if (!appDir.exists()) {
            return null;
        }
        File[] files = appDir.listFiles();
        if (files == null) {
            return null;
        }
        for (File file : files) {
            if (!file.isDirectory()
                    && file.getName().startsWith(INSTANT_APP_COOKIE_FILE_PREFIX)
                    && file.getName().endsWith(INSTANT_APP_COOKIE_FILE_SIFFIX)) {
                return file;
            }
        }
        return null;
    }

    private static @Nullable
    InstantAppInfo parseMetadata(@NonNull XmlPullParser parser,
                                 @NonNull String packageName)
            throws IOException, XmlPullParserException {
        final int outerDepth = parser.getDepth();
        while (XmlUtils.nextElementWithin(parser, outerDepth)) {
            if (TAG_PACKAGE.equals(parser.getName())) {
                return parsePackage(parser, packageName);
            }
        }
        return null;
    }

    private static InstantAppInfo parsePackage(@NonNull XmlPullParser parser,
                                               @NonNull String packageName)
            throws IOException, XmlPullParserException {
        String label = parser.getAttributeValue(null, ATTR_LABEL);

        List<String> outRequestedPermissions = new ArrayList<>();
        List<String> outGrantedPermissions = new ArrayList<>();

        final int outerDepth = parser.getDepth();
        while (XmlUtils.nextElementWithin(parser, outerDepth)) {
            if (TAG_PERMISSIONS.equals(parser.getName())) {
                parsePermissions(parser, outRequestedPermissions, outGrantedPermissions);
            }
        }

        String[] requestedPermissions = new String[outRequestedPermissions.size()];
        outRequestedPermissions.toArray(requestedPermissions);

        String[] grantedPermissions = new String[outGrantedPermissions.size()];
        outGrantedPermissions.toArray(grantedPermissions);

        return new InstantAppInfo(packageName, label,
                requestedPermissions, grantedPermissions);
    }

    private static void parsePermissions(@NonNull XmlPullParser parser,
            @NonNull List<String> outRequestedPermissions,
            @NonNull List<String> outGrantedPermissions)
            throws IOException, XmlPullParserException {
        final int outerDepth = parser.getDepth();
        while (XmlUtils.nextElementWithin(parser,outerDepth)) {
            if (TAG_PERMISSION.equals(parser.getName())) {
                String permission = XmlUtils.readStringAttribute(parser, ATTR_NAME);
                outRequestedPermissions.add(permission);
                if (XmlUtils.readBooleanAttribute(parser, ATTR_GRANTED)) {
                    outGrantedPermissions.add(permission);
                }
            }
        }
    }

    private void writeUninstalledInstantAppMetadata(
            @NonNull InstantAppInfo instantApp, @UserIdInt int userId) {
        File appDir = getInstantApplicationDir(instantApp.getPackageName(), userId);
        if (!appDir.exists() && !appDir.mkdirs()) {
            return;
        }

        File metadataFile = new File(appDir, INSTANT_APP_METADATA_FILE);

        AtomicFile destination = new AtomicFile(metadataFile);
        FileOutputStream out = null;
        try {
            out = destination.startWrite();

            XmlSerializer serializer = Xml.newSerializer();
            serializer.setOutput(out, StandardCharsets.UTF_8.name());
            serializer.setFeature("http://xmlpull.org/v1/doc/features.html#indent-output", true);

            serializer.startDocument(null, true);

            serializer.startTag(null, TAG_PACKAGE);
            serializer.attribute(null, ATTR_LABEL, instantApp.loadLabel(
                    mService.mContext.getPackageManager()).toString());

            serializer.startTag(null, TAG_PERMISSIONS);
            for (String permission : instantApp.getRequestedPermissions()) {
                serializer.startTag(null, TAG_PERMISSION);
                serializer.attribute(null, ATTR_NAME, permission);
                if (ArrayUtils.contains(instantApp.getGrantedPermissions(), permission)) {
                    serializer.attribute(null, ATTR_GRANTED, String.valueOf(true));
                }
                serializer.endTag(null, TAG_PERMISSION);
            }
            serializer.endTag(null, TAG_PERMISSIONS);

            serializer.endTag(null, TAG_PACKAGE);

            serializer.endDocument();
            destination.finishWrite(out);
        } catch (Throwable t) {
            Slog.wtf(LOG_TAG, "Failed to write instant state, restoring backup", t);
            destination.failWrite(out);
        } finally {
            IoUtils.closeQuietly(out);
        }
    }

    private static @NonNull File getInstantApplicationsDir(int userId) {
        return new File(Environment.getUserSystemDirectory(userId),
                INSTANT_APPS_FOLDER);
    }

    private static @NonNull File getInstantApplicationDir(String packageName, int userId) {
        return new File (getInstantApplicationsDir(userId), packageName);
    }

    private static void deleteDir(@NonNull File dir) {
        File[] files = dir.listFiles();
        if (files != null) {
            for (File file : files) {
                deleteDir(file);
            }
        }
        dir.delete();
    }

    private static final class UninstalledInstantAppState {
        final InstantAppInfo mInstantAppInfo;
        final long mTimestamp;

        public UninstalledInstantAppState(InstantAppInfo instantApp,
                long timestamp) {
            mInstantAppInfo = instantApp;
            mTimestamp = timestamp;
        }
    }

    private final class CookiePersistence extends Handler {
        private static final long PERSIST_COOKIE_DELAY_MILLIS = 1000L; /* one second */

        // In case you wonder why we stash the cookies aside, we use
        // the user id for the message id and the package for the payload.
        // Handler allows removing messages by id and tag where the
        // tag is compared using ==. So to allow cancelling the
        // pending persistence for an app under a given user we use
        // the fact that package are cached by the system so the ==
        // comparison would match and we end up with a way to cancel
        // persisting the cookie for a user and package.
        private final SparseArray<ArrayMap<PackageParser.Package, SomeArgs>> mPendingPersistCookies
                = new SparseArray<>();

        public CookiePersistence(Looper looper) {
            super(looper);
        }

        public void schedulePersistLPw(@UserIdInt int userId, @NonNull PackageParser.Package pkg,
                @NonNull byte[] cookie) {
            File cookieFile = computeInstantCookieFile(pkg, userId);
            cancelPendingPersistLPw(pkg, userId);
            addPendingPersistCookieLPw(userId, pkg, cookie, cookieFile);
            sendMessageDelayed(obtainMessage(userId, pkg),
                    PERSIST_COOKIE_DELAY_MILLIS);
        }

        public @Nullable byte[] getPendingPersistCookieLPr(@NonNull PackageParser.Package pkg,
                @UserIdInt int userId) {
            ArrayMap<PackageParser.Package, SomeArgs> pendingWorkForUser =
                    mPendingPersistCookies.get(userId);
            if (pendingWorkForUser != null) {
                SomeArgs state = pendingWorkForUser.get(pkg);
                if (state != null) {
                    return (byte[]) state.arg1;
                }
            }
            return null;
        }

        public void cancelPendingPersistLPw(@NonNull PackageParser.Package pkg,
                @UserIdInt int userId) {
            removeMessages(userId, pkg);
            SomeArgs state = removePendingPersistCookieLPr(pkg, userId);
            if (state != null) {
                state.recycle();
            }
        }

        private void addPendingPersistCookieLPw(@UserIdInt int userId,
                @NonNull PackageParser.Package pkg, @NonNull byte[] cookie,
                @NonNull File cookieFile) {
            ArrayMap<PackageParser.Package, SomeArgs> pendingWorkForUser =
                    mPendingPersistCookies.get(userId);
            if (pendingWorkForUser == null) {
                pendingWorkForUser = new ArrayMap<>();
                mPendingPersistCookies.put(userId, pendingWorkForUser);
            }
            SomeArgs args = SomeArgs.obtain();
            args.arg1 = cookie;
            args.arg2 = cookieFile;
            pendingWorkForUser.put(pkg, args);
        }

        private SomeArgs removePendingPersistCookieLPr(@NonNull PackageParser.Package pkg,
                @UserIdInt int userId) {
            ArrayMap<PackageParser.Package, SomeArgs> pendingWorkForUser =
                    mPendingPersistCookies.get(userId);
            SomeArgs state = null;
            if (pendingWorkForUser != null) {
                state = pendingWorkForUser.remove(pkg);
                if (pendingWorkForUser.isEmpty()) {
                    mPendingPersistCookies.remove(userId);
                }
            }
            return state;
        }

        @Override
        public void handleMessage(Message message) {
            int userId = message.what;
            PackageParser.Package pkg = (PackageParser.Package) message.obj;
            SomeArgs state = removePendingPersistCookieLPr(pkg, userId);
            if (state == null) {
                return;
            }
            byte[] cookie = (byte[]) state.arg1;
            File cookieFile = (File) state.arg2;
            state.recycle();
            persistInstantApplicationCookie(cookie, pkg.packageName, cookieFile, userId);
        }
    }
}