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}