Line data Source code
1 : // Copyright (C) 2017 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.extensions.conditions;
16 :
17 : import com.google.common.collect.Iterables;
18 : import java.util.Collections;
19 :
20 : /** Delayed evaluation of a boolean condition. */
21 : public abstract class BooleanCondition {
22 64 : public static final BooleanCondition TRUE = new Value(true);
23 64 : public static final BooleanCondition FALSE = new Value(false);
24 :
25 : public static BooleanCondition valueOf(boolean a) {
26 64 : return a ? TRUE : FALSE;
27 : }
28 :
29 : public static BooleanCondition and(BooleanCondition a, BooleanCondition b) {
30 62 : return a == FALSE || b == FALSE ? FALSE : new And(a, b);
31 : }
32 :
33 : public static BooleanCondition and(boolean a, BooleanCondition b) {
34 58 : return and(valueOf(a), b);
35 : }
36 :
37 : public static BooleanCondition or(BooleanCondition a, BooleanCondition b) {
38 60 : return a == TRUE || b == TRUE ? TRUE : new Or(a, b);
39 : }
40 :
41 : public static BooleanCondition or(boolean a, BooleanCondition b) {
42 60 : return or(valueOf(a), b);
43 : }
44 :
45 : public static BooleanCondition not(BooleanCondition bc) {
46 1 : return bc == TRUE ? FALSE : bc == FALSE ? TRUE : new Not(bc);
47 : }
48 :
49 64 : BooleanCondition() {}
50 :
51 : /** Evaluates the condition and return its value. */
52 : public abstract boolean value();
53 :
54 : /**
55 : * Recursively collect all children of type {@code type}.
56 : *
57 : * @param type implementation type of the conditions to collect and return.
58 : * @return non-null, unmodifiable iteration of children of type {@code type}.
59 : */
60 : public abstract <T> Iterable<T> children(Class<T> type);
61 :
62 : /**
63 : * Reduce evaluation tree by cutting off branches that evaluate trivially and replacing them with
64 : * a leave note corresponding to the value the branch evaluated to.
65 : *
66 : * <p>
67 : *
68 : * <pre>{@code
69 : * Example 1 (T=True, F=False, C=non-trivial check):
70 : * OR
71 : * / \ => T
72 : * C T
73 : * Example 2 (cuts off a not-trivial check):
74 : * AND
75 : * / \ => F
76 : * C F
77 : * Example 3:
78 : * AND
79 : * / \ => F
80 : * T F
81 : * }</pre>
82 : *
83 : * <p>There is no guarantee that the resulting tree is minimal. The only guarantee made is that
84 : * branches that evaluate trivially will be cut off and replaced by primitive values.
85 : */
86 : public abstract BooleanCondition reduce();
87 :
88 : /**
89 : * Check if the condition evaluates to either {@code true} or {@code false} without providing
90 : * additional information to the evaluation tree, e.g. through checks to a remote service such as
91 : * {@code PermissionBackend}.
92 : *
93 : * <p>In this case, the tree can be reduced to skip all non-trivial checks resulting in a
94 : * performance gain.
95 : */
96 : protected abstract boolean evaluatesTrivially();
97 :
98 : private static final class And extends BooleanCondition {
99 : private final BooleanCondition a;
100 : private final BooleanCondition b;
101 :
102 58 : And(BooleanCondition a, BooleanCondition b) {
103 58 : this.a = a;
104 58 : this.b = b;
105 58 : }
106 :
107 : @Override
108 : public boolean value() {
109 57 : if (evaluatesTriviallyToExpectedValue(a, false)
110 57 : || evaluatesTriviallyToExpectedValue(b, false)) {
111 0 : return false;
112 : }
113 57 : return a.value() && b.value();
114 : }
115 :
116 : @Override
117 : public <T> Iterable<T> children(Class<T> type) {
118 57 : return Iterables.concat(a.children(type), b.children(type));
119 : }
120 :
121 : @Override
122 : public BooleanCondition reduce() {
123 58 : if (evaluatesTrivially()) {
124 50 : return Value.valueOf(value());
125 : }
126 58 : return new And(a.reduce(), b.reduce());
127 : }
128 :
129 : @Override
130 : public int hashCode() {
131 0 : return a.hashCode() * 31 + b.hashCode();
132 : }
133 :
134 : @Override
135 : public boolean equals(Object other) {
136 1 : if (other instanceof And) {
137 1 : And o = (And) other;
138 1 : return a.equals(o.a) && b.equals(o.b);
139 : }
140 0 : return false;
141 : }
142 :
143 : @Override
144 : public String toString() {
145 0 : return "(" + maybeTrim(a, getClass()) + " && " + maybeTrim(a, getClass()) + ")";
146 : }
147 :
148 : @Override
149 : protected boolean evaluatesTrivially() {
150 58 : return evaluatesTriviallyToExpectedValue(a, false)
151 58 : || evaluatesTriviallyToExpectedValue(b, false)
152 58 : || (a.evaluatesTrivially() && b.evaluatesTrivially());
153 : }
154 : }
155 :
156 : private static final class Or extends BooleanCondition {
157 : private final BooleanCondition a;
158 : private final BooleanCondition b;
159 :
160 31 : Or(BooleanCondition a, BooleanCondition b) {
161 31 : this.a = a;
162 31 : this.b = b;
163 31 : }
164 :
165 : @Override
166 : public boolean value() {
167 14 : if (evaluatesTriviallyToExpectedValue(a, true)
168 14 : || evaluatesTriviallyToExpectedValue(b, true)) {
169 0 : return true;
170 : }
171 14 : return a.value() || b.value();
172 : }
173 :
174 : @Override
175 : public <T> Iterable<T> children(Class<T> type) {
176 14 : return Iterables.concat(a.children(type), b.children(type));
177 : }
178 :
179 : @Override
180 : public BooleanCondition reduce() {
181 15 : if (evaluatesTrivially()) {
182 0 : return Value.valueOf(value());
183 : }
184 15 : return new Or(a.reduce(), b.reduce());
185 : }
186 :
187 : @Override
188 : public int hashCode() {
189 0 : return a.hashCode() * 31 + b.hashCode();
190 : }
191 :
192 : @Override
193 : public boolean equals(Object other) {
194 1 : if (other instanceof Or) {
195 1 : Or o = (Or) other;
196 1 : return a.equals(o.a) && b.equals(o.b);
197 : }
198 0 : return false;
199 : }
200 :
201 : @Override
202 : public String toString() {
203 0 : return "(" + maybeTrim(a, getClass()) + " || " + maybeTrim(a, getClass()) + ")";
204 : }
205 :
206 : @Override
207 : protected boolean evaluatesTrivially() {
208 15 : return evaluatesTriviallyToExpectedValue(a, true)
209 15 : || evaluatesTriviallyToExpectedValue(b, true)
210 15 : || (a.evaluatesTrivially() && b.evaluatesTrivially());
211 : }
212 : }
213 :
214 : private static final class Not extends BooleanCondition {
215 : private final BooleanCondition cond;
216 :
217 1 : Not(BooleanCondition bc) {
218 1 : cond = bc;
219 1 : }
220 :
221 : @Override
222 : public boolean value() {
223 0 : return !cond.value();
224 : }
225 :
226 : @Override
227 : public <T> Iterable<T> children(Class<T> type) {
228 0 : return cond.children(type);
229 : }
230 :
231 : @Override
232 : public BooleanCondition reduce() {
233 1 : if (evaluatesTrivially()) {
234 0 : return Value.valueOf(value());
235 : }
236 1 : return this;
237 : }
238 :
239 : @Override
240 : public int hashCode() {
241 0 : return cond.hashCode() * 31;
242 : }
243 :
244 : @Override
245 : public boolean equals(Object other) {
246 1 : return other instanceof Not ? cond.equals(((Not) other).cond) : false;
247 : }
248 :
249 : @Override
250 : public String toString() {
251 0 : return "!" + cond;
252 : }
253 :
254 : @Override
255 : protected boolean evaluatesTrivially() {
256 1 : return cond.evaluatesTrivially();
257 : }
258 : }
259 :
260 : private static final class Value extends BooleanCondition {
261 : private final boolean value;
262 :
263 64 : Value(boolean v) {
264 64 : value = v;
265 64 : }
266 :
267 : @Override
268 : public boolean value() {
269 64 : return value;
270 : }
271 :
272 : @Override
273 : public <T> Iterable<T> children(Class<T> type) {
274 61 : return Collections.emptyList();
275 : }
276 :
277 : @Override
278 : public BooleanCondition reduce() {
279 62 : return this;
280 : }
281 :
282 : @Override
283 : public int hashCode() {
284 0 : return value ? 1 : 0;
285 : }
286 :
287 : @Override
288 : public boolean equals(Object other) {
289 1 : return other instanceof Value ? value == ((Value) other).value : false;
290 : }
291 :
292 : @Override
293 : public String toString() {
294 0 : return Boolean.toString(value);
295 : }
296 :
297 : @Override
298 : protected boolean evaluatesTrivially() {
299 58 : return true;
300 : }
301 : }
302 :
303 : /**
304 : * Helper for use in toString methods. Remove leading '(' and trailing ')' if the type is the same
305 : * as the parent.
306 : */
307 : static String maybeTrim(BooleanCondition cond, Class<? extends BooleanCondition> type) {
308 0 : String s = cond.toString();
309 0 : if (cond.getClass() == type
310 0 : && s.length() > 2
311 0 : && s.charAt(0) == '('
312 0 : && s.charAt(s.length() - 1) == ')') {
313 0 : s = s.substring(1, s.length() - 1);
314 : }
315 0 : return s;
316 : }
317 :
318 : private static boolean evaluatesTriviallyToExpectedValue(
319 : BooleanCondition cond, boolean expectedValue) {
320 58 : return cond.evaluatesTrivially() && (cond.value() == expectedValue);
321 : }
322 : }
|
