Source code

001/*
002 * (C) Copyright 2018 Nuxeo (http://nuxeo.com/) and others.
003 *
004 * Licensed under the Apache License, Version 2.0 (the "License");
005 * you may not use this file except in compliance with the License.
006 * You may obtain a copy of the License at
007 *
008 *     http://www.apache.org/licenses/LICENSE-2.0
009 *
010 * Unless required by applicable law or agreed to in writing, software
011 * distributed under the License is distributed on an "AS IS" BASIS,
012 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013 * See the License for the specific language governing permissions and
014 * limitations under the License.
015 *
016 * Contributors:
017 *     Florent Guillaume
018 */
019package org.nuxeo.ecm.directory.multi;
020
021import java.util.Arrays;
022import java.util.Collections;
023import java.util.HashSet;
024import java.util.Iterator;
025import java.util.List;
026import java.util.Map;
027import java.util.Set;
028
029import org.nuxeo.ecm.core.query.QueryParseException;
030import org.nuxeo.ecm.core.query.sql.model.Expression;
031import org.nuxeo.ecm.core.query.sql.model.IdentityQueryTransformer;
032import org.nuxeo.ecm.core.query.sql.model.MultiExpression;
033import org.nuxeo.ecm.core.query.sql.model.Operand;
034import org.nuxeo.ecm.core.query.sql.model.Operator;
035import org.nuxeo.ecm.core.query.sql.model.Predicate;
036import org.nuxeo.ecm.core.query.sql.model.QueryBuilder;
037import org.nuxeo.ecm.core.query.sql.model.Reference;
038import org.nuxeo.ecm.directory.multi.MultiDirectorySession.SourceInfo;
039import org.nuxeo.ecm.directory.multi.MultiDirectorySession.SubDirectoryInfo;
040
041/**
042 * Evaluator for an {@link Expression} in the context of the various subdirectories of a MultiDirectory's source.
043 * <p>
044 * The result is a set of entry ids.
045 * <p>
046 * The strategy for evaluation is to delegate as much as possible of the evaluation of expressions to subdirectories
047 * themselves.
048 * <p>
049 * We do a depth-first evaluation of expressions, delaying actual evaluation while an expression's references all fall
050 * into the same subdirectory.
051 *
052 * @since 10.3
053 */
054public class MultiDirectoryExpressionEvaluator {
055
056    /** The result of an evaluation of an expression. */
057    public interface Result {
058    }
059
060    /** Result is a set of entry ids. */
061    public static class IdsResult implements Result {
062        public final Set<String> ids;
063
064        public IdsResult(Set<String> ids) {
065            this.ids = ids;
066        }
067    }
068
069    /** Result is an operand associated to at most one subdirectory. */
070    public static class OperandResult implements Result {
071
072        public final Operand operand;
073
074        public final boolean hasId;
075
076        public final String dir; // may be null
077
078        public OperandResult(Operand operand, boolean hasId, String dir) {
079            this.operand = operand;
080            this.hasId = hasId;
081            this.dir = dir;
082        }
083    }
084
085    protected final List<SubDirectoryInfo> dirInfos;
086
087    protected final String idField;
088
089    protected final String dirName; // for error messages
090
091    public MultiDirectoryExpressionEvaluator(SourceInfo sourceInfo, String idField, String dirName) {
092        dirInfos = sourceInfo.subDirectoryInfos;
093        this.idField = idField;
094        this.dirName = dirName;
095
096    }
097
098    /**
099     * Evaluates an expression and returns the set of matching ids.
100     */
101    public Set<String> eval(Expression expr) {
102        return evaluate(evalExpression(expr));
103    }
104
105    protected Result evalExpression(Expression expr) {
106        Operator op = expr.operator;
107        if (expr instanceof MultiExpression) {
108            return evalMultiExpression((MultiExpression) expr);
109        } else if (op == Operator.AND || op == Operator.OR) {
110            return evalAndOr(expr);
111        } else {
112            return evalSimpleExpression(expr);
113        }
114    }
115
116    protected Result evalSimpleExpression(Expression expr) {
117        Result left = evalOperand(expr.lvalue);
118        Result right = evalOperand(expr.rvalue);
119
120        // case where we can return a single-dir operand to the caller
121        if (left instanceof OperandResult && right instanceof OperandResult) {
122            // check id and subdirectories
123            OperandResult lop = (OperandResult) left;
124            OperandResult rop = (OperandResult) right;
125            if (lop.dir == null || rop.dir == null || lop.dir.equals(rop.dir)) {
126                // still one subdirectory
127                String dir = lop.dir == null ? rop.dir : lop.dir;
128                return new OperandResult(expr, lop.hasId || rop.hasId, dir);
129            }
130        }
131
132        // else for a simple expression we have no way of doing manual evaluation
133        throw new QueryParseException("Invalid expression for multidirectory: " + expr);
134    }
135
136    protected Result evalOperand(Operand op) {
137        if (op instanceof Expression) {
138            return evalExpression((Expression) op);
139        } else if (op instanceof Reference) {
140            return evalReference((Reference) op);
141        } else { // Literal / LiteralList / Function
142            return new OperandResult(op, false, null);
143        }
144    }
145
146    protected Result evalReference(Reference ref) {
147        String name = ref.name;
148        if (name.equals(idField)) {
149            return new OperandResult(ref, true, null);
150        }
151        for (SubDirectoryInfo dirInfo : dirInfos) {
152            if (dirInfo.fromSource.containsKey(name)) {
153                return new OperandResult(ref, false, dirInfo.dirName);
154            }
155        }
156        throw new QueryParseException("No column: " + name + " for directory: " + dirName);
157    }
158
159    protected Result evalAndOr(Expression expr) {
160        List<Predicate> predicates = Arrays.asList((Predicate) expr.lvalue, (Predicate) expr.rvalue);
161        return evalMultiExpression(new MultiExpression(expr.operator, predicates));
162    }
163
164    protected Result evalMultiExpression(MultiExpression expr) {
165        boolean and = expr.operator == Operator.AND;
166        List<Predicate> predicates = expr.predicates;
167        Iterator<Predicate> it = predicates.iterator();
168        if (!it.hasNext()) {
169            // empty multiexpression
170            return new OperandResult(expr, false, null);
171        }
172        Result previous = evalExpression(it.next());
173        while (it.hasNext()) {
174            if (and && previous instanceof IdsResult && ((IdsResult) previous).ids.isEmpty()) {
175                // optimization, no need to do more work
176                return previous;
177            }
178            Result next = evalExpression(it.next());
179
180            // check if we can keep a single-dir operand
181            if (previous instanceof OperandResult && next instanceof OperandResult) {
182                // check id and subdirectories
183                OperandResult prv = (OperandResult) previous;
184                OperandResult nxt = (OperandResult) next;
185                if (prv.dir == null || nxt.dir == null || prv.dir.equals(nxt.dir)) {
186                    // still one subdirectory
187                    String dir = prv.dir == null ? nxt.dir : prv.dir;
188                    previous = new OperandResult(expr, prv.hasId || nxt.hasId, dir);
189                    continue;
190                }
191            }
192
193            // turn everything into ids and do intersection/union
194            Set<String> previousIds = evaluate(previous);
195            if (and && previousIds.isEmpty()) {
196                // optimization, no need to do more work
197                return new IdsResult(previousIds);
198            }
199            Set<String> nextIds = evaluate(next);
200            Set<String> ids = and ? intersection(previousIds, nextIds) : union(previousIds, nextIds);
201            previous = new IdsResult(ids);
202        }
203        return previous;
204    }
205
206    /**
207     * Evaluates a result and returns the set of matching ids.
208     */
209    protected Set<String> evaluate(Result result) {
210        if (result instanceof IdsResult) {
211            return ((IdsResult) result).ids;
212        } else {
213            return evaluate((OperandResult) result);
214        }
215    }
216
217    /**
218     * Evaluates an operand associated to a single directory and returns the set of matching ids.
219     */
220    protected Set<String> evaluate(OperandResult opr) {
221        // find subdirectory to use
222        SubDirectoryInfo subDirInfo = null;
223        for (SubDirectoryInfo dirInfo : dirInfos) {
224            if (opr.dir != null) {
225                if (opr.dir.equals(dirInfo.dirName)) {
226                    subDirInfo = dirInfo;
227                    break;
228                }
229            } else {
230                // expression without any reference (except maybe id), pick any non-optional directory
231                if (!dirInfo.isOptional) {
232                    subDirInfo = dirInfo;
233                    break;
234                }
235            }
236        }
237        if (subDirInfo == null) {
238            throw new QueryParseException(
239                    "Configuration error: no non-optional subdirectory for multidirectory: " + dirName);
240        }
241        // map field names from multidirectory to subdirectory
242        Predicate predicate = new ReferenceRenamer(subDirInfo.fromSource).transform((Predicate) opr.operand);
243        QueryBuilder queryBuilder = new QueryBuilder();
244        if (predicate instanceof MultiExpression) {
245            queryBuilder.filter((MultiExpression) predicate);
246        } else {
247            queryBuilder.predicate(predicate);
248        }
249        return new HashSet<>(subDirInfo.getSession().queryIds(queryBuilder));
250    }
251
252    /**
253     * Renames the references according to a map.
254     *
255     * @since 10.3
256     */
257    public static class ReferenceRenamer extends IdentityQueryTransformer {
258
259        protected final Map<String, String> map;
260
261        public ReferenceRenamer(Map<String, String> map) {
262            this.map = map;
263        }
264
265        @Override
266        public Reference transform(Reference node) {
267            String name = node.name;
268            String newName = map.getOrDefault(name, name);
269            if (newName.equals(name)) {
270                return node;
271            } else {
272                return new Reference(newName, node.cast, node.esHint);
273            }
274        }
275    }
276
277    /**
278     * Set union.
279     */
280    protected static Set<String> union(Set<String> a, Set<String> b) {
281        if (a.isEmpty()) {
282            return Collections.emptySet();
283        } else if (b.isEmpty()) {
284            return Collections.emptySet();
285        } else {
286            Set<String> set = new HashSet<>(a);
287            if (set.addAll(b)) {
288                return set;
289            } else {
290                return a; // optimization, don't return a new set if there was no change
291            }
292        }
293    }
294
295    /**
296     * Set intersection.
297     */
298    protected static Set<String> intersection(Set<String> a, Set<String> b) {
299        if (a.isEmpty()) {
300            return Collections.emptySet();
301        } else if (b.isEmpty()) {
302            return Collections.emptySet();
303        } else {
304            Set<String> set = new HashSet<>(a);
305            if (set.retainAll(b)) {
306                return set;
307            } else {
308                return a; // optimization, don't return a new set if there was no change
309            }
310        }
311    }
312
313}