/*
 * 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 android.content.pm.split;

import android.annotation.IntRange;
import android.annotation.NonNull;
import android.content.pm.PackageParser;
import android.util.IntArray;
import android.util.SparseArray;

import libcore.util.EmptyArray;

import java.util.Arrays;
import java.util.BitSet;

/**
 * A helper class that implements the dependency tree traversal for splits. Callbacks
 * are implemented by subclasses to notify whether a split has already been constructed
 * and is cached, and to actually create the split requested.
 *
 * This helper is meant to be subclassed so as to reduce the number of allocations
 * needed to make use of it.
 *
 * All inputs and outputs are assumed to be indices into an array of splits.
 *
 * @hide
 */
public abstract class SplitDependencyLoader<E extends Exception> {
    private final @NonNull SparseArray<int[]> mDependencies;

    /**
     * Construct a new SplitDependencyLoader. Meant to be called from the
     * subclass constructor.
     * @param dependencies The dependency tree of splits.
     */
    protected SplitDependencyLoader(@NonNull SparseArray<int[]> dependencies) {
        mDependencies = dependencies;
    }

    /**
     * Traverses the dependency tree and constructs any splits that are not already
     * cached. This routine short-circuits and skips the creation of splits closer to the
     * root if they are cached, as reported by the subclass implementation of
     * {@link #isSplitCached(int)}. The construction of splits is delegated to the subclass
     * implementation of {@link #constructSplit(int, int[], int)}.
     * @param splitIdx The index of the split to load. 0 represents the base Application.
     */
    protected void loadDependenciesForSplit(@IntRange(from = 0) int splitIdx) throws E {
        // Quick check before any allocations are done.
        if (isSplitCached(splitIdx)) {
            return;
        }

        // Special case the base, since it has no dependencies.
        if (splitIdx == 0) {
            final int[] configSplitIndices = collectConfigSplitIndices(0);
            constructSplit(0, configSplitIndices, -1);
            return;
        }

        // Build up the dependency hierarchy.
        final IntArray linearDependencies = new IntArray();
        linearDependencies.add(splitIdx);

        // Collect all the dependencies that need to be constructed.
        // They will be listed from leaf to root.
        while (true) {
            // Only follow the first index into the array. The others are config splits and
            // get loaded with the split.
            final int[] deps = mDependencies.get(splitIdx);
            if (deps != null && deps.length > 0) {
                splitIdx = deps[0];
            } else {
                splitIdx = -1;
            }

            if (splitIdx < 0 || isSplitCached(splitIdx)) {
                break;
            }

            linearDependencies.add(splitIdx);
        }

        // Visit each index, from right to left (root to leaf).
        int parentIdx = splitIdx;
        for (int i = linearDependencies.size() - 1; i >= 0; i--) {
            final int idx = linearDependencies.get(i);
            final int[] configSplitIndices = collectConfigSplitIndices(idx);
            constructSplit(idx, configSplitIndices, parentIdx);
            parentIdx = idx;
        }
    }

    private @NonNull int[] collectConfigSplitIndices(int splitIdx) {
        // The config splits appear after the first element.
        final int[] deps = mDependencies.get(splitIdx);
        if (deps == null || deps.length <= 1) {
            return EmptyArray.INT;
        }
        return Arrays.copyOfRange(deps, 1, deps.length);
    }

    /**
     * Subclass to report whether the split at `splitIdx` is cached and need not be constructed.
     * It is assumed that if `splitIdx` is cached, any parent of `splitIdx` is also cached.
     * @param splitIdx The index of the split to check for in the cache.
     * @return true if the split is cached and does not need to be constructed.
     */
    protected abstract boolean isSplitCached(@IntRange(from = 0) int splitIdx);

    /**
     * Subclass to construct a split at index `splitIdx` with parent split `parentSplitIdx`.
     * The result is expected to be cached by the subclass in its own structures.
     * @param splitIdx The index of the split to construct. 0 represents the base Application.
     * @param configSplitIndices The array of configuration splits to load along with this split.
     *                           May be empty (length == 0) but never null.
     * @param parentSplitIdx The index of the parent split. -1 if there is no parent.
     * @throws E Subclass defined exception representing failure to construct a split.
     */
    protected abstract void constructSplit(@IntRange(from = 0) int splitIdx,
            @NonNull @IntRange(from = 1) int[] configSplitIndices,
            @IntRange(from = -1) int parentSplitIdx) throws E;

    public static class IllegalDependencyException extends Exception {
        private IllegalDependencyException(String message) {
            super(message);
        }
    }

    private static int[] append(int[] src, int elem) {
        if (src == null) {
            return new int[] { elem };
        }
        int[] dst = Arrays.copyOf(src, src.length + 1);
        dst[src.length] = elem;
        return dst;
    }

    public static @NonNull SparseArray<int[]> createDependenciesFromPackage(
            PackageParser.PackageLite pkg) throws IllegalDependencyException {
        // The data structure that holds the dependencies. In PackageParser, splits are stored
        // in their own array, separate from the base. We treat all paths as equals, so
        // we need to insert the base as index 0, and shift all other splits.
        final SparseArray<int[]> splitDependencies = new SparseArray<>();

        // The base depends on nothing.
        splitDependencies.put(0, new int[] {-1});

        // First write out the <uses-split> dependencies. These must appear first in the
        // array of ints, as is convention in this class.
        for (int splitIdx = 0; splitIdx < pkg.splitNames.length; splitIdx++) {
            if (!pkg.isFeatureSplits[splitIdx]) {
                // Non-feature splits don't have dependencies.
                continue;
            }

            // Implicit dependency on the base.
            final int targetIdx;
            final String splitDependency = pkg.usesSplitNames[splitIdx];
            if (splitDependency != null) {
                final int depIdx = Arrays.binarySearch(pkg.splitNames, splitDependency);
                if (depIdx < 0) {
                    throw new IllegalDependencyException("Split '" + pkg.splitNames[splitIdx]
                            + "' requires split '" + splitDependency + "', which is missing.");
                }
                targetIdx = depIdx + 1;
            } else {
                // Implicitly depend on the base.
                targetIdx = 0;
            }
            splitDependencies.put(splitIdx + 1, new int[] {targetIdx});
        }

        // Write out the configForSplit reverse-dependencies. These appear after the <uses-split>
        // dependencies and are considered leaves.
        //
        // At this point, all splits in splitDependencies have the first element in their array set.
        for (int splitIdx = 0; splitIdx < pkg.splitNames.length; splitIdx++) {
            if (pkg.isFeatureSplits[splitIdx]) {
                // Feature splits are not configForSplits.
                continue;
            }

            // Implicit feature for the base.
            final int targetSplitIdx;
            final String configForSplit = pkg.configForSplit[splitIdx];
            if (configForSplit != null) {
                final int depIdx = Arrays.binarySearch(pkg.splitNames, configForSplit);
                if (depIdx < 0) {
                    throw new IllegalDependencyException("Split '" + pkg.splitNames[splitIdx]
                            + "' targets split '" + configForSplit + "', which is missing.");
                }

                if (!pkg.isFeatureSplits[depIdx]) {
                    throw new IllegalDependencyException("Split '" + pkg.splitNames[splitIdx]
                            + "' declares itself as configuration split for a non-feature split '"
                            + pkg.splitNames[depIdx] + "'");
                }
                targetSplitIdx = depIdx + 1;
            } else {
                targetSplitIdx = 0;
            }
            splitDependencies.put(targetSplitIdx,
                    append(splitDependencies.get(targetSplitIdx), splitIdx + 1));
        }

        // Verify that there are no cycles.
        final BitSet bitset = new BitSet();
        for (int i = 0, size = splitDependencies.size(); i < size; i++) {
            int splitIdx = splitDependencies.keyAt(i);

            bitset.clear();
            while (splitIdx != -1) {
                // Check if this split has been visited yet.
                if (bitset.get(splitIdx)) {
                    throw new IllegalDependencyException("Cycle detected in split dependencies.");
                }

                // Mark the split so that if we visit it again, we no there is a cycle.
                bitset.set(splitIdx);

                // Follow the first dependency only, the others are leaves by definition.
                final int[] deps = splitDependencies.get(splitIdx);
                splitIdx = deps != null ? deps[0] : -1;
            }
        }
        return splitDependencies;
    }
}