/*
* 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;
}
}