1 /*
2  * Copyright 2024 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package com.android.server.appsearch.external.localstorage;
18 
19 import android.annotation.NonNull;
20 import android.util.ArrayMap;
21 import android.util.ArraySet;
22 
23 import com.google.android.icing.proto.SchemaTypeConfigProto;
24 
25 import java.util.ArrayDeque;
26 import java.util.ArrayList;
27 import java.util.Collections;
28 import java.util.List;
29 import java.util.Map;
30 import java.util.Objects;
31 import java.util.Queue;
32 import java.util.Set;
33 
34 /**
35  * Caches and manages schema information for AppSearch.
36  *
37  * @hide
38  */
39 public class SchemaCache {
40     /**
41      * A map that contains schema types and SchemaTypeConfigProtos for all package-database
42      * prefixes. It maps each package-database prefix to an inner-map. The inner-map maps each
43      * prefixed schema type to its respective SchemaTypeConfigProto.
44      */
45     private final Map<String, Map<String, SchemaTypeConfigProto>> mSchemaMap = new ArrayMap<>();
46 
47     /**
48      * A map that contains schema types and all children schema types for all package-database
49      * prefixes. It maps each package-database prefix to an inner-map. The inner-map maps each
50      * prefixed schema type to its respective list of children prefixed schema types.
51      */
52     private final Map<String, Map<String, List<String>>> mSchemaParentToChildrenMap =
53             new ArrayMap<>();
54 
SchemaCache()55     public SchemaCache() {}
56 
SchemaCache(@onNull Map<String, Map<String, SchemaTypeConfigProto>> schemaMap)57     public SchemaCache(@NonNull Map<String, Map<String, SchemaTypeConfigProto>> schemaMap) {
58         mSchemaMap.putAll(Objects.requireNonNull(schemaMap));
59         rebuildSchemaParentToChildrenMap();
60     }
61 
62     /** Returns the schema map for the given prefix. */
63     @NonNull
getSchemaMapForPrefix(@onNull String prefix)64     public Map<String, SchemaTypeConfigProto> getSchemaMapForPrefix(@NonNull String prefix) {
65         Objects.requireNonNull(prefix);
66 
67         Map<String, SchemaTypeConfigProto> schemaMap = mSchemaMap.get(prefix);
68         if (schemaMap == null) {
69             return Collections.emptyMap();
70         }
71         return schemaMap;
72     }
73 
74     /** Returns a set of all prefixes stored in the cache. */
75     @NonNull
getAllPrefixes()76     public Set<String> getAllPrefixes() {
77         return Collections.unmodifiableSet(mSchemaMap.keySet());
78     }
79 
80     /**
81      * Returns all prefixed schema types stored in the cache.
82      *
83      * <p>This method is inefficient to call repeatedly.
84      */
85     @NonNull
getAllPrefixedSchemaTypes()86     public List<String> getAllPrefixedSchemaTypes() {
87         List<String> cachedPrefixedSchemaTypes = new ArrayList<>();
88         for (Map<String, SchemaTypeConfigProto> value : mSchemaMap.values()) {
89             cachedPrefixedSchemaTypes.addAll(value.keySet());
90         }
91         return cachedPrefixedSchemaTypes;
92     }
93 
94     /**
95      * Returns the schema types for the given set of prefixed schema types with their descendants,
96      * based on the schema parent-to-children map held in the cache.
97      */
98     @NonNull
getSchemaTypesWithDescendants( @onNull String prefix, @NonNull Set<String> prefixedSchemaTypes)99     public Set<String> getSchemaTypesWithDescendants(
100             @NonNull String prefix, @NonNull Set<String> prefixedSchemaTypes) {
101         Objects.requireNonNull(prefix);
102         Objects.requireNonNull(prefixedSchemaTypes);
103         Map<String, List<String>> parentToChildrenMap = mSchemaParentToChildrenMap.get(prefix);
104         if (parentToChildrenMap == null) {
105             parentToChildrenMap = Collections.emptyMap();
106         }
107 
108         // Perform a BFS search on the inheritance graph started by the set of prefixedSchemaTypes.
109         Set<String> visited = new ArraySet<>();
110         Queue<String> prefixedSchemaQueue = new ArrayDeque<>(prefixedSchemaTypes);
111         while (!prefixedSchemaQueue.isEmpty()) {
112             String currentPrefixedSchema = prefixedSchemaQueue.poll();
113             if (visited.contains(currentPrefixedSchema)) {
114                 continue;
115             }
116             visited.add(currentPrefixedSchema);
117             List<String> children = parentToChildrenMap.get(currentPrefixedSchema);
118             if (children == null) {
119                 continue;
120             }
121             prefixedSchemaQueue.addAll(children);
122         }
123 
124         return visited;
125     }
126 
127     /**
128      * Rebuilds the schema parent-to-children map for the given prefix, based on the current schema
129      * map.
130      *
131      * <p>The schema parent-to-children map is required to be updated when {@link #addToSchemaMap}
132      * or {@link #removeFromSchemaMap} has been called. Otherwise, the results from {@link
133      * #getSchemaTypesWithDescendants} would be stale.
134      */
rebuildSchemaParentToChildrenMapForPrefix(@onNull String prefix)135     public void rebuildSchemaParentToChildrenMapForPrefix(@NonNull String prefix) {
136         Objects.requireNonNull(prefix);
137 
138         mSchemaParentToChildrenMap.remove(prefix);
139         Map<String, SchemaTypeConfigProto> prefixedSchemaMap = mSchemaMap.get(prefix);
140         if (prefixedSchemaMap == null) {
141             return;
142         }
143 
144         // Build the parent-to-children map for the current prefix.
145         Map<String, List<String>> parentToChildrenMap = new ArrayMap<>();
146         for (SchemaTypeConfigProto childSchemaConfig : prefixedSchemaMap.values()) {
147             for (int i = 0; i < childSchemaConfig.getParentTypesCount(); i++) {
148                 String parent = childSchemaConfig.getParentTypes(i);
149                 List<String> children = parentToChildrenMap.get(parent);
150                 if (children == null) {
151                     children = new ArrayList<>();
152                     parentToChildrenMap.put(parent, children);
153                 }
154                 children.add(childSchemaConfig.getSchemaType());
155             }
156         }
157 
158         // Record the map for the current prefix.
159         if (!parentToChildrenMap.isEmpty()) {
160             mSchemaParentToChildrenMap.put(prefix, parentToChildrenMap);
161         }
162     }
163 
164     /**
165      * Rebuilds the schema parent-to-children map based on the current schema map.
166      *
167      * <p>The schema parent-to-children map is required to be updated when {@link #addToSchemaMap}
168      * or {@link #removeFromSchemaMap} has been called. Otherwise, the results from {@link
169      * #getSchemaTypesWithDescendants} would be stale.
170      */
rebuildSchemaParentToChildrenMap()171     public void rebuildSchemaParentToChildrenMap() {
172         mSchemaParentToChildrenMap.clear();
173         for (String prefix : mSchemaMap.keySet()) {
174             rebuildSchemaParentToChildrenMapForPrefix(prefix);
175         }
176     }
177 
178     /**
179      * Adds a schema to the schema map.
180      *
181      * <p>Note that this method will invalidate the schema parent-to-children map in the cache, and
182      * either {@link #rebuildSchemaParentToChildrenMap} or {@link
183      * #rebuildSchemaParentToChildrenMapForPrefix} is required to be called to update the cache.
184      */
addToSchemaMap( @onNull String prefix, @NonNull SchemaTypeConfigProto schemaTypeConfigProto)185     public void addToSchemaMap(
186             @NonNull String prefix, @NonNull SchemaTypeConfigProto schemaTypeConfigProto) {
187         Objects.requireNonNull(prefix);
188         Objects.requireNonNull(schemaTypeConfigProto);
189 
190         Map<String, SchemaTypeConfigProto> schemaTypeMap = mSchemaMap.get(prefix);
191         if (schemaTypeMap == null) {
192             schemaTypeMap = new ArrayMap<>();
193             mSchemaMap.put(prefix, schemaTypeMap);
194         }
195         schemaTypeMap.put(schemaTypeConfigProto.getSchemaType(), schemaTypeConfigProto);
196     }
197 
198     /**
199      * Removes a schema from the schema map.
200      *
201      * <p>Note that this method will invalidate the schema parent-to-children map in the cache, and
202      * either {@link #rebuildSchemaParentToChildrenMap} or {@link
203      * #rebuildSchemaParentToChildrenMapForPrefix} is required to be called to update the cache.
204      */
removeFromSchemaMap(@onNull String prefix, @NonNull String schemaType)205     public void removeFromSchemaMap(@NonNull String prefix, @NonNull String schemaType) {
206         Objects.requireNonNull(prefix);
207         Objects.requireNonNull(schemaType);
208 
209         Map<String, SchemaTypeConfigProto> schemaTypeMap = mSchemaMap.get(prefix);
210         if (schemaTypeMap != null) {
211             schemaTypeMap.remove(schemaType);
212         }
213     }
214 
215     /**
216      * Removes the entry of the given prefix from both the schema map and the schema
217      * parent-to-children map, and returns the set of removed prefixed schema type.
218      */
219     @NonNull
removePrefix(@onNull String prefix)220     public Set<String> removePrefix(@NonNull String prefix) {
221         Objects.requireNonNull(prefix);
222 
223         Map<String, SchemaTypeConfigProto> removedSchemas =
224                 Objects.requireNonNull(mSchemaMap.remove(prefix));
225         mSchemaParentToChildrenMap.remove(prefix);
226         return removedSchemas.keySet();
227     }
228 
229     /** Clears all data in the cache. */
clear()230     public void clear() {
231         mSchemaMap.clear();
232         mSchemaParentToChildrenMap.clear();
233     }
234 }
235