Line data Source code
1 : // Copyright (C) 2013 The Android Open Source Project
2 : //
3 : // Licensed under the Apache License, Version 2.0 (the "License");
4 : // you may not use this file except in compliance with the License.
5 : // You may obtain a copy of the License at
6 : //
7 : // http://www.apache.org/licenses/LICENSE-2.0
8 : //
9 : // Unless required by applicable law or agreed to in writing, software
10 : // distributed under the License is distributed on an "AS IS" BASIS,
11 : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : // See the License for the specific language governing permissions and
13 : // limitations under the License.
14 :
15 : package com.google.gerrit.server.index.change;
16 :
17 : import static com.google.gerrit.server.query.change.ChangeStatusPredicate.closed;
18 : import static com.google.gerrit.server.query.change.ChangeStatusPredicate.open;
19 :
20 : import com.google.common.collect.Lists;
21 : import com.google.common.collect.Sets;
22 : import com.google.gerrit.common.Nullable;
23 : import com.google.gerrit.entities.Change;
24 : import com.google.gerrit.entities.Change.Status;
25 : import com.google.gerrit.index.IndexConfig;
26 : import com.google.gerrit.index.IndexRewriter;
27 : import com.google.gerrit.index.QueryOptions;
28 : import com.google.gerrit.index.Schema;
29 : import com.google.gerrit.index.SchemaFieldDefs.SchemaField;
30 : import com.google.gerrit.index.query.AndCardinalPredicate;
31 : import com.google.gerrit.index.query.AndPredicate;
32 : import com.google.gerrit.index.query.HasCardinality;
33 : import com.google.gerrit.index.query.IndexPredicate;
34 : import com.google.gerrit.index.query.LimitPredicate;
35 : import com.google.gerrit.index.query.NotPredicate;
36 : import com.google.gerrit.index.query.OrCardinalPredicate;
37 : import com.google.gerrit.index.query.OrPredicate;
38 : import com.google.gerrit.index.query.Predicate;
39 : import com.google.gerrit.index.query.QueryParseException;
40 : import com.google.gerrit.index.query.TooManyTermsInQueryException;
41 : import com.google.gerrit.server.query.change.AndChangeSource;
42 : import com.google.gerrit.server.query.change.ChangeData;
43 : import com.google.gerrit.server.query.change.ChangeDataSource;
44 : import com.google.gerrit.server.query.change.ChangeQueryBuilder;
45 : import com.google.gerrit.server.query.change.ChangeStatusPredicate;
46 : import com.google.gerrit.server.query.change.IsSubmittablePredicate;
47 : import com.google.gerrit.server.query.change.OrSource;
48 : import com.google.inject.Inject;
49 : import com.google.inject.Singleton;
50 : import java.util.BitSet;
51 : import java.util.EnumSet;
52 : import java.util.List;
53 : import java.util.Optional;
54 : import java.util.Set;
55 : import org.eclipse.jgit.util.MutableInteger;
56 :
57 : /** Rewriter that pushes boolean logic into the secondary index. */
58 : @Singleton
59 : public class ChangeIndexRewriter implements IndexRewriter<ChangeData> {
60 : /** Set of all open change statuses. */
61 : public static final Set<Change.Status> OPEN_STATUSES;
62 :
63 : /** Set of all closed change statuses. */
64 : public static final Set<Change.Status> CLOSED_STATUSES;
65 :
66 : static {
67 149 : EnumSet<Change.Status> open = EnumSet.noneOf(Change.Status.class);
68 149 : EnumSet<Change.Status> closed = EnumSet.noneOf(Change.Status.class);
69 149 : for (Change.Status s : Change.Status.values()) {
70 149 : if (s.isOpen()) {
71 149 : open.add(s);
72 : } else {
73 149 : closed.add(s);
74 : }
75 : }
76 149 : OPEN_STATUSES = Sets.immutableEnumSet(open);
77 149 : CLOSED_STATUSES = Sets.immutableEnumSet(closed);
78 149 : }
79 :
80 : /**
81 : * Get the set of statuses that changes matching the given predicate may have.
82 : *
83 : * @param in predicate
84 : * @return the maximal set of statuses that any changes matching the input predicates may have,
85 : * based on examining boolean and {@link ChangeStatusPredicate}s.
86 : */
87 : public static Set<Change.Status> getPossibleStatus(Predicate<ChangeData> in) {
88 5 : EnumSet<Change.Status> s = extractStatus(in);
89 5 : return s != null ? s : EnumSet.allOf(Change.Status.class);
90 : }
91 :
92 : private static @Nullable EnumSet<Change.Status> extractStatus(Predicate<ChangeData> in) {
93 5 : if (in instanceof ChangeStatusPredicate) {
94 4 : Status status = ((ChangeStatusPredicate) in).getStatus();
95 4 : return status != null ? EnumSet.of(status) : null;
96 5 : } else if (in instanceof NotPredicate) {
97 2 : EnumSet<Status> s = extractStatus(in.getChild(0));
98 2 : return s != null ? EnumSet.complementOf(s) : null;
99 5 : } else if (in instanceof OrPredicate) {
100 3 : EnumSet<Change.Status> r = null;
101 3 : int childrenWithStatus = 0;
102 3 : for (int i = 0; i < in.getChildCount(); i++) {
103 3 : EnumSet<Status> c = extractStatus(in.getChild(i));
104 3 : if (c != null) {
105 3 : if (r == null) {
106 3 : r = EnumSet.noneOf(Change.Status.class);
107 : }
108 3 : r.addAll(c);
109 3 : childrenWithStatus++;
110 : }
111 : }
112 3 : if (r != null && childrenWithStatus < in.getChildCount()) {
113 : // At least one child supplied a status but another did not.
114 : // Assume all statuses for the children that did not feed a
115 : // status at this part of the tree. This matches behavior if
116 : // the child was used at the root of a query.
117 0 : return EnumSet.allOf(Change.Status.class);
118 : }
119 3 : return r;
120 5 : } else if (in instanceof AndPredicate) {
121 5 : EnumSet<Change.Status> r = null;
122 5 : for (int i = 0; i < in.getChildCount(); i++) {
123 5 : EnumSet<Change.Status> c = extractStatus(in.getChild(i));
124 5 : if (c != null) {
125 4 : if (r == null) {
126 4 : r = EnumSet.allOf(Change.Status.class);
127 : }
128 4 : r.retainAll(c);
129 : }
130 : }
131 5 : return r;
132 : }
133 5 : return null;
134 : }
135 :
136 : private final ChangeIndexCollection indexes;
137 : private final IndexConfig config;
138 :
139 : @Inject
140 149 : ChangeIndexRewriter(ChangeIndexCollection indexes, IndexConfig config) {
141 149 : this.indexes = indexes;
142 149 : this.config = config;
143 149 : }
144 :
145 : @Override
146 : public Predicate<ChangeData> rewrite(Predicate<ChangeData> in, QueryOptions opts)
147 : throws QueryParseException {
148 111 : Predicate<ChangeData> s = rewriteImpl(in, opts);
149 111 : if (!(s instanceof ChangeDataSource)) {
150 7 : in = Predicate.and(Predicate.or(open(), closed()), in);
151 7 : s = rewriteImpl(in, opts);
152 : }
153 111 : if (!(s instanceof ChangeDataSource)) {
154 0 : throw new QueryParseException("invalid query: " + s);
155 : }
156 111 : return s;
157 : }
158 :
159 : private Predicate<ChangeData> rewriteImpl(Predicate<ChangeData> in, QueryOptions opts)
160 : throws QueryParseException {
161 111 : ChangeIndex index = indexes.getSearchIndex();
162 :
163 111 : MutableInteger leafTerms = new MutableInteger();
164 111 : Predicate<ChangeData> out = rewriteImpl(in, index, opts, leafTerms);
165 111 : if (leafTerms.value > config.maxTerms()) {
166 1 : throw new TooManyTermsInQueryException(leafTerms.value, config.maxTerms());
167 : }
168 111 : if (isSameInstance(in, out) || out instanceof IndexPredicate) {
169 111 : return new IndexedChangeQuery(index, out, opts);
170 10 : } else if (out == null /* cannot rewrite */) {
171 7 : return in;
172 : } else {
173 10 : return out;
174 : }
175 : }
176 :
177 : /**
178 : * Rewrite a single predicate subtree.
179 : *
180 : * @param in predicate to rewrite.
181 : * @param index index whose schema determines which fields are indexed.
182 : * @param opts other query options.
183 : * @param leafTerms number of leaf index query terms encountered so far.
184 : * @return {@code null} if no part of this subtree can be queried in the index directly. {@code
185 : * in} if this subtree and all its children can be queried directly in the index. Otherwise, a
186 : * predicate that is semantically equivalent, with some of its subtrees wrapped to query the
187 : * index directly.
188 : * @throws QueryParseException if the underlying index implementation does not support this
189 : * predicate.
190 : */
191 : @Nullable
192 : private Predicate<ChangeData> rewriteImpl(
193 : Predicate<ChangeData> in, ChangeIndex index, QueryOptions opts, MutableInteger leafTerms)
194 : throws QueryParseException {
195 111 : in = IsSubmittablePredicate.rewrite(in);
196 111 : if (isIndexPredicate(in, index)) {
197 111 : ++leafTerms.value;
198 111 : return in;
199 109 : } else if (in instanceof LimitPredicate) {
200 : // Replace any limits with the limit provided by the caller. The caller
201 : // should have already searched the predicate tree for limit predicates
202 : // and included that in their limit computation.
203 6 : return new LimitPredicate<>(ChangeQueryBuilder.FIELD_LIMIT, opts.limit());
204 109 : } else if (!isRewritePossible(in)) {
205 8 : if (in instanceof IndexPredicate) {
206 1 : throw new QueryParseException("Unsupported index predicate: " + in.toString());
207 : }
208 8 : return null; // magic to indicate "in" cannot be rewritten
209 : }
210 :
211 109 : int n = in.getChildCount();
212 109 : BitSet isIndexed = new BitSet(n);
213 109 : BitSet notIndexed = new BitSet(n);
214 109 : BitSet rewritten = new BitSet(n);
215 109 : BitSet changeSource = new BitSet(n);
216 109 : List<Predicate<ChangeData>> newChildren = Lists.newArrayListWithCapacity(n);
217 109 : for (int i = 0; i < n; i++) {
218 109 : Predicate<ChangeData> c = in.getChild(i);
219 109 : Predicate<ChangeData> nc = rewriteImpl(c, index, opts, leafTerms);
220 109 : if (isSameInstance(nc, c)) {
221 109 : isIndexed.set(i);
222 109 : newChildren.add(c);
223 10 : } else if (nc == null /* cannot rewrite c */) {
224 8 : notIndexed.set(i);
225 8 : newChildren.add(c);
226 : } else {
227 7 : if (nc instanceof ChangeDataSource) {
228 0 : changeSource.set(i);
229 : }
230 7 : rewritten.set(i);
231 7 : newChildren.add(nc);
232 : }
233 : }
234 :
235 109 : if (isIndexed.cardinality() == n) {
236 109 : return in; // All children are indexed, leave as-is for parent.
237 10 : } else if (notIndexed.cardinality() == n) {
238 1 : return null; // Can't rewrite any children, so cannot rewrite in.
239 10 : } else if (rewritten.cardinality() == n) {
240 : // All children were rewritten.
241 0 : if (changeSource.cardinality() == n) {
242 0 : return copy(in, newChildren);
243 : }
244 0 : return in.copy(newChildren);
245 : }
246 10 : return partitionChildren(in, newChildren, isIndexed, index, opts);
247 : }
248 :
249 : private boolean isIndexPredicate(Predicate<ChangeData> in, ChangeIndex index) {
250 111 : if (!(in instanceof IndexPredicate)) {
251 109 : return false;
252 : }
253 111 : IndexPredicate<ChangeData> p = (IndexPredicate<ChangeData>) in;
254 :
255 111 : SchemaField<ChangeData, ?> field = p.getField();
256 111 : Schema<ChangeData> schema = index.getSchema();
257 111 : return schema.hasField(field);
258 : }
259 :
260 : private Predicate<ChangeData> partitionChildren(
261 : Predicate<ChangeData> in,
262 : List<Predicate<ChangeData>> newChildren,
263 : BitSet isIndexed,
264 : ChangeIndex index,
265 : QueryOptions opts)
266 : throws QueryParseException {
267 10 : if (isIndexed.cardinality() == 1) {
268 9 : int i = isIndexed.nextSetBit(0);
269 9 : Predicate<ChangeData> indexed = newChildren.remove(i);
270 9 : newChildren.add(0, new IndexedChangeQuery(index, copy(indexed, indexed.getChildren()), opts));
271 9 : return copy(in, newChildren);
272 : }
273 :
274 : // Group all indexed predicates into a wrapped subtree.
275 6 : List<Predicate<ChangeData>> indexed = Lists.newArrayListWithCapacity(isIndexed.cardinality());
276 :
277 6 : List<Predicate<ChangeData>> all =
278 6 : Lists.newArrayListWithCapacity(newChildren.size() - isIndexed.cardinality() + 1);
279 :
280 6 : for (int i = 0; i < newChildren.size(); i++) {
281 6 : Predicate<ChangeData> c = newChildren.get(i);
282 6 : if (isIndexed.get(i)) {
283 6 : indexed.add(c);
284 : } else {
285 6 : all.add(c);
286 : }
287 : }
288 6 : all.add(0, new IndexedChangeQuery(index, copy(in, indexed), opts));
289 6 : return copy(in, all);
290 : }
291 :
292 : private Predicate<ChangeData> copy(Predicate<ChangeData> in, List<Predicate<ChangeData>> all) {
293 10 : if (in instanceof AndPredicate) {
294 10 : Optional<Predicate<ChangeData>> atLeastOneChangeDataSource =
295 10 : all.stream().filter(p -> (p instanceof ChangeDataSource)).findAny();
296 10 : if (atLeastOneChangeDataSource.isPresent()) {
297 10 : return new AndChangeSource(all, config);
298 : }
299 6 : Optional<Predicate<ChangeData>> atLeastOneCardinalPredicate =
300 6 : all.stream().filter(p -> (p instanceof HasCardinality)).findAny();
301 6 : if (atLeastOneCardinalPredicate.isPresent()) {
302 6 : return new AndCardinalPredicate<>(all);
303 : }
304 9 : } else if (in instanceof OrPredicate) {
305 7 : Optional<Predicate<ChangeData>> nonChangeDataSource =
306 7 : all.stream().filter(p -> !(p instanceof ChangeDataSource)).findAny();
307 7 : if (!nonChangeDataSource.isPresent()) {
308 0 : return new OrSource(all);
309 : }
310 7 : Optional<Predicate<ChangeData>> nonHasCardinality =
311 7 : all.stream().filter(p -> !(p instanceof HasCardinality)).findAny();
312 7 : if (!nonHasCardinality.isPresent()) {
313 7 : return new OrCardinalPredicate<>(all);
314 : }
315 : }
316 7 : return in.copy(all);
317 : }
318 :
319 : private static boolean isRewritePossible(Predicate<ChangeData> p) {
320 109 : return p.getChildCount() > 0
321 : && (p instanceof AndPredicate || p instanceof OrPredicate || p instanceof NotPredicate);
322 : }
323 :
324 : @SuppressWarnings("ReferenceEquality")
325 : private static <T> boolean isSameInstance(T a, T b) {
326 111 : return a == b;
327 : }
328 : }
|
