001/*
002 * (C) Copyright 2014-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.core.storage;
020
021import static java.lang.Boolean.FALSE;
022import static java.lang.Boolean.TRUE;
023import static org.nuxeo.ecm.core.api.trash.TrashService.Feature.TRASHED_STATE_IN_MIGRATION;
024import static org.nuxeo.ecm.core.api.trash.TrashService.Feature.TRASHED_STATE_IS_DEDICATED_PROPERTY;
025import static org.nuxeo.ecm.core.api.trash.TrashService.Feature.TRASHED_STATE_IS_DEDUCED_FROM_LIFECYCLE;
026
027import java.util.ArrayList;
028import java.util.Arrays;
029import java.util.Calendar;
030import java.util.Collections;
031import java.util.Deque;
032import java.util.HashSet;
033import java.util.LinkedList;
034import java.util.List;
035import java.util.Set;
036import java.util.regex.Pattern;
037
038import org.apache.commons.lang3.CharUtils;
039import org.apache.commons.lang3.StringUtils;
040import org.nuxeo.ecm.core.api.LifeCycleConstants;
041import org.nuxeo.ecm.core.api.trash.TrashService;
042import org.nuxeo.ecm.core.query.QueryParseException;
043import org.nuxeo.ecm.core.query.sql.NXQL;
044import org.nuxeo.ecm.core.query.sql.model.BooleanLiteral;
045import org.nuxeo.ecm.core.query.sql.model.DateLiteral;
046import org.nuxeo.ecm.core.query.sql.model.DoubleLiteral;
047import org.nuxeo.ecm.core.query.sql.model.Expression;
048import org.nuxeo.ecm.core.query.sql.model.Function;
049import org.nuxeo.ecm.core.query.sql.model.IntegerLiteral;
050import org.nuxeo.ecm.core.query.sql.model.Literal;
051import org.nuxeo.ecm.core.query.sql.model.LiteralList;
052import org.nuxeo.ecm.core.query.sql.model.MultiExpression;
053import org.nuxeo.ecm.core.query.sql.model.Operand;
054import org.nuxeo.ecm.core.query.sql.model.Operator;
055import org.nuxeo.ecm.core.query.sql.model.Predicate;
056import org.nuxeo.ecm.core.query.sql.model.Reference;
057import org.nuxeo.ecm.core.query.sql.model.StringLiteral;
058import org.nuxeo.runtime.api.Framework;
059
060import com.google.common.collect.Iterators;
061import com.google.common.collect.PeekingIterator;
062
063/**
064 * Evaluator for an {@link Expression}.
065 *
066 * @since 5.9.4
067 */
068public abstract class ExpressionEvaluator {
069
070    /** pseudo NXQL to resolve ancestor ids. */
071    public static final String NXQL_ECM_ANCESTOR_IDS = "ecm:__ancestorIds";
072
073    /** pseudo NXQL to resolve internal path. */
074    public static final String NXQL_ECM_PATH = "ecm:__path";
075
076    /** pseudo NXQL to resolve read acls. */
077    public static final String NXQL_ECM_READ_ACL = "ecm:__read_acl";
078
079    public static final String NXQL_ECM_FULLTEXT_SIMPLE = "ecm:__fulltextSimple";
080
081    public static final String NXQL_ECM_FULLTEXT_BINARY = "ecm:__fulltextBinary";
082
083    protected static final String DATE_CAST = "DATE";
084
085    protected static final String PHRASE_QUOTE = "\"";
086
087    protected static final String NEG_PHRASE_QUOTE = "-\"";
088
089    protected static final String OR = "or";
090
091    /**
092     * Interface for a class that knows how to resolve a path into an id.
093     */
094    public interface PathResolver {
095        /**
096         * Returns the id for a given path.
097         *
098         * @param path the path
099         * @return the id, or {@code null} if not found
100         */
101        String getIdForPath(String path);
102    }
103
104    public final PathResolver pathResolver;
105
106    public final Set<String> principals;
107
108    public final boolean fulltextSearchDisabled;
109
110    public boolean hasFulltext;
111
112    public ExpressionEvaluator(PathResolver pathResolver, String[] principals, boolean fulltextSearchDisabled) {
113        this.pathResolver = pathResolver;
114        this.principals = principals == null ? null : new HashSet<>(Arrays.asList(principals));
115        this.fulltextSearchDisabled = fulltextSearchDisabled;
116    }
117
118    public Object walkExpression(Expression expr) {
119        Operator op = expr.operator;
120        Operand lvalue = expr.lvalue;
121        Operand rvalue = expr.rvalue;
122        Reference ref = lvalue instanceof Reference ? (Reference) lvalue : null;
123        String name = ref != null ? ref.name : null;
124        String cast = ref != null ? ref.cast : null;
125        if (DATE_CAST.equals(cast)) {
126            checkDateLiteralForCast(rvalue, name);
127        }
128        if (op == Operator.STARTSWITH) {
129            return walkStartsWith(lvalue, rvalue);
130        } else if (NXQL.ECM_PATH.equals(name)) {
131            return walkEcmPath(op, rvalue);
132        } else if (NXQL.ECM_ANCESTORID.equals(name)) {
133            return walkAncestorId(op, rvalue);
134        } else if (NXQL.ECM_ISTRASHED.equals(name)) {
135            return walkIsTrashed(op, rvalue);
136        } else if (name != null && name.startsWith(NXQL.ECM_FULLTEXT) && !NXQL.ECM_FULLTEXT_JOBID.equals(name)) {
137            return walkEcmFulltext(name, op, rvalue);
138        } else if (op == Operator.SUM) {
139            throw new UnsupportedOperationException("SUM");
140        } else if (op == Operator.SUB) {
141            throw new UnsupportedOperationException("SUB");
142        } else if (op == Operator.MUL) {
143            throw new UnsupportedOperationException("MUL");
144        } else if (op == Operator.DIV) {
145            throw new UnsupportedOperationException("DIV");
146        } else if (op == Operator.LT) {
147            return walkLt(lvalue, rvalue);
148        } else if (op == Operator.GT) {
149            return walkGt(lvalue, rvalue);
150        } else if (op == Operator.EQ) {
151            return walkEq(lvalue, rvalue);
152        } else if (op == Operator.NOTEQ) {
153            return walkNotEq(lvalue, rvalue);
154        } else if (op == Operator.LTEQ) {
155            return walkLtEq(lvalue, rvalue);
156        } else if (op == Operator.GTEQ) {
157            return walkGtEq(lvalue, rvalue);
158        } else if (op == Operator.AND) {
159            if (expr instanceof MultiExpression) {
160                return walkMultiExpression((MultiExpression) expr);
161            } else {
162                return walkAnd(lvalue, rvalue);
163            }
164        } else if (op == Operator.NOT) {
165            return walkNot(lvalue);
166        } else if (op == Operator.OR) {
167            if (expr instanceof MultiExpression) {
168                return walkMultiExpression((MultiExpression) expr);
169            } else {
170                return walkOr(lvalue, rvalue);
171            }
172        } else if (op == Operator.LIKE) {
173            return walkLike(lvalue, rvalue, true, false);
174        } else if (op == Operator.ILIKE) {
175            return walkLike(lvalue, rvalue, true, true);
176        } else if (op == Operator.NOTLIKE) {
177            return walkLike(lvalue, rvalue, false, false);
178        } else if (op == Operator.NOTILIKE) {
179            return walkLike(lvalue, rvalue, false, true);
180        } else if (op == Operator.IN) {
181            return walkIn(lvalue, rvalue, true);
182        } else if (op == Operator.NOTIN) {
183            return walkIn(lvalue, rvalue, false);
184        } else if (op == Operator.ISNULL) {
185            return walkIsNull(lvalue);
186        } else if (op == Operator.ISNOTNULL) {
187            return walkIsNotNull(lvalue);
188        } else if (op == Operator.BETWEEN) {
189            return walkBetween(lvalue, rvalue, true);
190        } else if (op == Operator.NOTBETWEEN) {
191            return walkBetween(lvalue, rvalue, false);
192        } else {
193            throw new QueryParseException("Unknown operator: " + op);
194        }
195    }
196
197    protected void checkDateLiteralForCast(Operand value, String name) {
198        if (value instanceof DateLiteral && !((DateLiteral) value).onlyDate) {
199            throw new QueryParseException("DATE() cast must be used with DATE literal, not TIMESTAMP: " + name);
200        }
201    }
202
203    protected Boolean walkEcmPath(Operator op, Operand rvalue) {
204        if (op != Operator.EQ && op != Operator.NOTEQ) {
205            throw new QueryParseException(NXQL.ECM_PATH + " requires = or <> operator");
206        }
207        if (!(rvalue instanceof StringLiteral)) {
208            throw new QueryParseException(NXQL.ECM_PATH + " requires literal path as right argument");
209        }
210        String path = ((StringLiteral) rvalue).value;
211        if (path.length() > 1 && path.endsWith("/")) {
212            path = path.substring(0, path.length() - 1);
213        }
214        String id = pathResolver.getIdForPath(path);
215        Object right = walkReference(new Reference(NXQL.ECM_UUID));
216        if (id == null) {
217            return FALSE;
218        }
219        Boolean eq = eq(id, right);
220        return op == Operator.EQ ? eq : not(eq);
221    }
222
223    protected Boolean walkAncestorId(Operator op, Operand rvalue) {
224        if (op != Operator.EQ && op != Operator.NOTEQ) {
225            throw new QueryParseException(NXQL.ECM_ANCESTORID + " requires = or <> operator");
226        }
227        if (!(rvalue instanceof StringLiteral)) {
228            throw new QueryParseException(NXQL.ECM_ANCESTORID + " requires literal id as right argument");
229        }
230        String ancestorId = ((StringLiteral) rvalue).value;
231        Object[] ancestorIds = (Object[]) walkReference(new Reference(NXQL_ECM_ANCESTOR_IDS));
232        boolean eq = op == Operator.EQ ? true : false;
233        if (ancestorIds == null) {
234            // placeless
235            return eq ? FALSE : TRUE;
236        }
237        for (Object id : ancestorIds) {
238            if (ancestorId.equals(id)) {
239                return eq ? TRUE : FALSE;
240            }
241        }
242        return eq ? FALSE : TRUE;
243    }
244
245    protected Boolean walkEcmFulltext(String name, Operator op, Operand rvalue) {
246        if (op != Operator.EQ && op != Operator.LIKE) {
247            throw new QueryParseException(NXQL.ECM_FULLTEXT + " requires = or LIKE operator");
248        }
249        if (!(rvalue instanceof StringLiteral)) {
250            throw new QueryParseException(NXQL.ECM_FULLTEXT + " requires literal string as right argument");
251        }
252        if (fulltextSearchDisabled) {
253            throw new QueryParseException("Fulltext search disabled by configuration");
254        }
255        String query = ((StringLiteral) rvalue).value;
256        if (name.equals(NXQL.ECM_FULLTEXT)) {
257            // standard fulltext query
258            hasFulltext = true;
259            String simple = (String) walkReference(new Reference(NXQL_ECM_FULLTEXT_SIMPLE));
260            String binary = (String) walkReference(new Reference(NXQL_ECM_FULLTEXT_BINARY));
261            return fulltext(simple, binary, query);
262        } else {
263            // secondary index match with explicit field
264            // do a regexp on the field
265            if (name.charAt(NXQL.ECM_FULLTEXT.length()) != '.') {
266                throw new QueryParseException(name + " has incorrect syntax for a secondary fulltext index");
267            }
268            String prop = name.substring(NXQL.ECM_FULLTEXT.length() + 1);
269            String ft = query.replace(" ", "%");
270            rvalue = new StringLiteral(ft);
271            return walkLike(new Reference(prop), rvalue, true, true);
272        }
273    }
274
275    protected Boolean walkIsTrashed(Operator op, Operand rvalue) {
276        if (op != Operator.EQ && op != Operator.NOTEQ) {
277            throw new QueryParseException(NXQL.ECM_ISTRASHED + " requires = or <> operator");
278        }
279        TrashService trashService = Framework.getService(TrashService.class);
280        if (trashService.hasFeature(TRASHED_STATE_IS_DEDUCED_FROM_LIFECYCLE)) {
281            return walkIsTrashed(new Reference(NXQL.ECM_LIFECYCLESTATE), op, rvalue,
282                    new StringLiteral(LifeCycleConstants.DELETED_STATE));
283        } else if (trashService.hasFeature(TRASHED_STATE_IN_MIGRATION)) {
284            Boolean lifeCycleTrashed = walkIsTrashed(new Reference(NXQL.ECM_LIFECYCLESTATE), op, rvalue,
285                    new StringLiteral(LifeCycleConstants.DELETED_STATE));
286            Boolean propertyTrashed = walkIsTrashed(new Reference(NXQL.ECM_ISTRASHED), op, rvalue,
287                    new IntegerLiteral(1L));
288            return or(lifeCycleTrashed, propertyTrashed);
289        } else if (trashService.hasFeature(TRASHED_STATE_IS_DEDICATED_PROPERTY)) {
290            return walkIsTrashed(new Reference(NXQL.ECM_ISTRASHED), op, rvalue, new IntegerLiteral(1L));
291        } else {
292            throw new UnsupportedOperationException("TrashService is in an unknown state");
293        }
294    }
295
296    protected Boolean walkIsTrashed(Reference ref, Operator op, Operand initialRvalue, Literal deletedRvalue) {
297        long v;
298        if (!(initialRvalue instanceof IntegerLiteral)
299                || ((v = ((IntegerLiteral) initialRvalue).value) != 0 && v != 1)) {
300            throw new QueryParseException(NXQL.ECM_ISTRASHED + " requires literal 0 or 1 as right argument");
301        }
302        boolean equalsDeleted = op == Operator.EQ ^ v == 0;
303        if (equalsDeleted) {
304            return walkEq(ref, deletedRvalue);
305        } else {
306            return walkNotEq(ref, deletedRvalue);
307        }
308    }
309
310    public Boolean walkNot(Operand value) {
311        return not(bool(walkOperand(value)));
312    }
313
314    public Boolean walkIsNull(Operand value) {
315        return Boolean.valueOf(walkOperand(value) == null);
316    }
317
318    public Boolean walkIsNotNull(Operand value) {
319        return Boolean.valueOf(walkOperand(value) != null);
320    }
321
322    // ternary logic
323    public Boolean walkMultiExpression(MultiExpression expr) {
324        boolean and = expr.operator == Operator.AND;
325        Boolean res = and ? TRUE : FALSE;
326        for (Predicate predicate : expr.predicates) {
327            Boolean bool = bool(walkExpression(predicate));
328            // don't short-circuit on null, we want to walk all references deterministically
329            if (and) {
330                res = and(res, bool);
331            } else {
332                res = or(res, bool);
333            }
334        }
335        return res;
336    }
337
338    public Boolean walkAnd(Operand lvalue, Operand rvalue) {
339        Boolean left = bool(walkOperand(lvalue));
340        Boolean right = bool(walkOperand(rvalue));
341        return and(left, right);
342    }
343
344    public Boolean walkOr(Operand lvalue, Operand rvalue) {
345        Boolean left = bool(walkOperand(lvalue));
346        Boolean right = bool(walkOperand(rvalue));
347        return or(left, right);
348    }
349
350    public Boolean walkEq(Operand lvalue, Operand rvalue) {
351        Object right = walkOperand(rvalue);
352        if (isMixinTypes(lvalue)) {
353            if (!(right instanceof String)) {
354                throw new QueryParseException("Invalid EQ rhs: " + rvalue);
355            }
356            return walkMixinTypes(Collections.singletonList((String) right), true);
357        }
358        Object left = walkOperand(lvalue);
359        return eqMaybeList(left, right);
360    }
361
362    public Boolean walkNotEq(Operand lvalue, Operand rvalue) {
363        if (isMixinTypes(lvalue)) {
364            Object right = walkOperand(rvalue);
365            if (!(right instanceof String)) {
366                throw new QueryParseException("Invalid NE rhs: " + rvalue);
367            }
368            return walkMixinTypes(Collections.singletonList((String) right), false);
369        }
370        return not(walkEq(lvalue, rvalue));
371    }
372
373    public Boolean walkLt(Operand lvalue, Operand rvalue) {
374        Integer cmp = cmp(lvalue, rvalue);
375        return cmp == null ? null : cmp < 0;
376    }
377
378    public Boolean walkGt(Operand lvalue, Operand rvalue) {
379        Integer cmp = cmp(lvalue, rvalue);
380        return cmp == null ? null : cmp > 0;
381    }
382
383    public Boolean walkLtEq(Operand lvalue, Operand rvalue) {
384        Integer cmp = cmp(lvalue, rvalue);
385        return cmp == null ? null : cmp <= 0;
386    }
387
388    public Boolean walkGtEq(Operand lvalue, Operand rvalue) {
389        Integer cmp = cmp(lvalue, rvalue);
390        return cmp == null ? null : cmp >= 0;
391    }
392
393    public Object walkBetween(Operand lvalue, Operand rvalue, boolean positive) {
394        LiteralList l = (LiteralList) rvalue;
395        Predicate va = new Predicate(lvalue, Operator.GTEQ, l.get(0));
396        Predicate vb = new Predicate(lvalue, Operator.LTEQ, l.get(1));
397        Predicate pred = new Predicate(va, Operator.AND, vb);
398        if (!positive) {
399            pred = new Predicate(pred, Operator.NOT, null);
400        }
401        return walkExpression(pred);
402    }
403
404    public Boolean walkIn(Operand lvalue, Operand rvalue, boolean positive) {
405        Object right = walkOperand(rvalue);
406        if (!(right instanceof List)) {
407            throw new QueryParseException("Invalid IN rhs: " + rvalue);
408        }
409        if (isMixinTypes(lvalue)) {
410            return walkMixinTypes((List<String>) right, positive);
411        }
412        Object left = walkOperand(lvalue);
413        Boolean in = inMaybeList(left, (List<Object>) right);
414        return positive ? in : not(in);
415    }
416
417    public Object walkOperand(Operand op) {
418        if (op instanceof Literal) {
419            return walkLiteral((Literal) op);
420        } else if (op instanceof LiteralList) {
421            return walkLiteralList((LiteralList) op);
422        } else if (op instanceof Function) {
423            return walkFunction((Function) op);
424        } else if (op instanceof Expression) {
425            return walkExpression((Expression) op);
426        } else if (op instanceof Reference) {
427            return walkReference((Reference) op);
428        } else {
429            throw new QueryParseException("Unknown operand: " + op);
430        }
431    }
432
433    public Object walkLiteral(Literal lit) {
434        if (lit instanceof BooleanLiteral) {
435            return walkBooleanLiteral((BooleanLiteral) lit);
436        } else if (lit instanceof DateLiteral) {
437            return walkDateLiteral((DateLiteral) lit);
438        } else if (lit instanceof DoubleLiteral) {
439            return walkDoubleLiteral((DoubleLiteral) lit);
440        } else if (lit instanceof IntegerLiteral) {
441            return walkIntegerLiteral((IntegerLiteral) lit);
442        } else if (lit instanceof StringLiteral) {
443            return walkStringLiteral((StringLiteral) lit);
444        } else {
445            throw new QueryParseException("Unknown literal: " + lit);
446        }
447    }
448
449    public Boolean walkBooleanLiteral(BooleanLiteral lit) {
450        return Boolean.valueOf(lit.value);
451    }
452
453    public Calendar walkDateLiteral(DateLiteral lit) {
454        if (lit.onlyDate) {
455            Calendar date = lit.toCalendar();
456            if (date != null) {
457                date.set(Calendar.HOUR_OF_DAY, 0);
458                date.set(Calendar.MINUTE, 0);
459                date.set(Calendar.SECOND, 0);
460                date.set(Calendar.MILLISECOND, 0);
461            }
462            return date;
463        } else {
464            return lit.toCalendar();
465        }
466    }
467
468    public Double walkDoubleLiteral(DoubleLiteral lit) {
469        return Double.valueOf(lit.value);
470    }
471
472    public Long walkIntegerLiteral(IntegerLiteral lit) {
473        return Long.valueOf(lit.value);
474    }
475
476    public String walkStringLiteral(StringLiteral lit) {
477        return lit.value;
478    }
479
480    public List<Object> walkLiteralList(LiteralList litList) {
481        List<Object> list = new ArrayList<>(litList.size());
482        for (Literal lit : litList) {
483            list.add(walkLiteral(lit));
484        }
485        return list;
486    }
487
488    public Boolean walkLike(Operand lvalue, Operand rvalue, boolean positive, boolean caseInsensitive) {
489        Object left = walkOperand(lvalue);
490        Object right = walkOperand(rvalue);
491        if (!(right instanceof String)) {
492            throw new QueryParseException("Invalid LIKE rhs: " + rvalue);
493        }
494        return likeMaybeList(left, (String) right, positive, caseInsensitive);
495    }
496
497    public Object walkFunction(Function func) {
498        throw new UnsupportedOperationException("Function");
499    }
500
501    public Boolean walkStartsWith(Operand lvalue, Operand rvalue) {
502        if (!(lvalue instanceof Reference)) {
503            throw new QueryParseException("Invalid STARTSWITH query, left hand side must be a property: " + lvalue);
504        }
505        String name = ((Reference) lvalue).name;
506        if (!(rvalue instanceof StringLiteral)) {
507            throw new QueryParseException(
508                    "Invalid STARTSWITH query, right hand side must be a literal path: " + rvalue);
509        }
510        String path = ((StringLiteral) rvalue).value;
511        if (path.length() > 1 && path.endsWith("/")) {
512            path = path.substring(0, path.length() - 1);
513        }
514
515        if (NXQL.ECM_PATH.equals(name)) {
516            return walkStartsWithPath(path);
517        } else {
518            return walkStartsWithNonPath(lvalue, path);
519        }
520    }
521
522    protected Boolean walkStartsWithPath(String path) {
523        // resolve path
524        String ancestorId = pathResolver.getIdForPath(path);
525        // don't return early on null ancestorId, we want to walk all references deterministically
526        Object[] ancestorIds = (Object[]) walkReference(new Reference(NXQL_ECM_ANCESTOR_IDS));
527        if (ancestorId == null) {
528            // no such path
529            return FALSE;
530        }
531        if (ancestorIds == null) {
532            // placeless
533            return FALSE;
534        }
535        for (Object id : ancestorIds) {
536            if (ancestorId.equals(id)) {
537                return TRUE;
538            }
539        }
540        return FALSE;
541    }
542
543    protected Boolean walkStartsWithNonPath(Operand lvalue, String path) {
544        Object left = walkReference((Reference) lvalue);
545        // exact match
546        Boolean bool = eqMaybeList(left, path);
547        if (TRUE.equals(bool)) {
548            return TRUE;
549        }
550        // prefix match TODO escape % chars
551        String pattern = path + "/%";
552        return likeMaybeList(left, pattern, true, false);
553    }
554
555    /**
556     * Evaluates a reference over the context state.
557     *
558     * @param ref the reference
559     */
560    public abstract Object walkReference(Reference ref);
561
562    protected boolean isMixinTypes(Operand op) {
563        if (!(op instanceof Reference)) {
564            return false;
565        }
566        return ((Reference) op).name.equals(NXQL.ECM_MIXINTYPE);
567    }
568
569    protected Boolean bool(Object value) {
570        if (value == null) {
571            return null;
572        }
573        if (!(value instanceof Boolean)) {
574            throw new QueryParseException("Not a boolean: " + value);
575        }
576        return (Boolean) value;
577    }
578
579    // ternary logic
580    protected Boolean not(Boolean value) {
581        if (value == null) {
582            return null;
583        }
584        return !value;
585    }
586
587    // ternary logic
588    protected Boolean and(Boolean left, Boolean right) {
589        if (TRUE.equals(left)) {
590            return right;
591        } else {
592            return left;
593        }
594    }
595
596    // ternary logic
597    protected Boolean or(Boolean left, Boolean right) {
598        if (TRUE.equals(left)) {
599            return left;
600        } else {
601            return right;
602        }
603    }
604
605    // ternary logic
606    protected Boolean eq(Object left, Object right) {
607        if (left == null || right == null) {
608            return null;
609        }
610        if (left instanceof Calendar && right instanceof Calendar) {
611            // avoid timezone issues (NXP-20260)
612            return ((Calendar) left).getTimeInMillis() == ((Calendar) right).getTimeInMillis();
613        }
614        return left.equals(right);
615    }
616
617    // ternary logic
618    protected Boolean in(Object left, List<Object> right) {
619        if (left == null) {
620            return null;
621        }
622        boolean hasNull = false;
623        for (Object r : right) {
624            if (r == null) {
625                hasNull = true;
626            } else if (left.equals(r)) {
627                return TRUE;
628            }
629        }
630        return hasNull ? null : FALSE;
631    }
632
633    protected Integer cmp(Operand lvalue, Operand rvalue) {
634        Object left = walkOperand(lvalue);
635        Object right = walkOperand(rvalue);
636        return cmp(left, right);
637    }
638
639    // ternary logic
640    protected Integer cmp(Object left, Object right) {
641        if (left == null || right == null) {
642            return null;
643        }
644        if (!(left instanceof Comparable)) {
645            throw new QueryParseException("Not a comparable: " + left);
646        }
647        return ((Comparable<Object>) left).compareTo(right);
648    }
649
650    // ternary logic
651    protected Boolean like(Object left, String right, boolean caseInsensitive) {
652        if (left == null || right == null) {
653            return null;
654        }
655        if (!(left instanceof String)) {
656            throw new QueryParseException("Invalid LIKE lhs: " + left);
657        }
658        String value = (String) left;
659        if (caseInsensitive) {
660            value = value.toLowerCase();
661            right = right.toLowerCase();
662        }
663        String regex = likeToRegex(right);
664        boolean match = Pattern.matches(regex.toString(), value);
665        return match;
666    }
667
668    /**
669     * Turns a NXQL LIKE pattern into a regex.
670     * <p>
671     * % and _ are standard wildcards, and \ escapes them.
672     *
673     * @since 7.4
674     */
675    public static String likeToRegex(String like) {
676        StringBuilder regex = new StringBuilder();
677        char[] chars = like.toCharArray();
678        boolean escape = false;
679        for (int i = 0; i < chars.length; i++) {
680            char c = chars[i];
681            boolean escapeNext = false;
682            switch (c) {
683            case '%':
684                if (escape) {
685                    regex.append(c);
686                } else {
687                    regex.append(".*");
688                }
689                break;
690            case '_':
691                if (escape) {
692                    regex.append(c);
693                } else {
694                    regex.append(".");
695                }
696                break;
697            case '\\':
698                if (escape) {
699                    regex.append("\\\\"); // backslash escaped for regexp
700                } else {
701                    escapeNext = true;
702                }
703                break;
704            default:
705                // escape mostly everything just in case
706                if (!CharUtils.isAsciiAlphanumeric(c)) {
707                    regex.append("\\");
708                }
709                regex.append(c);
710                break;
711            }
712            escape = escapeNext;
713        }
714        if (escape) {
715            // invalid string terminated by escape character, ignore
716        }
717        return regex.toString();
718    }
719
720    // if list, use EXIST (SELECT 1 FROM left WHERE left.item = right)
721    protected Boolean eqMaybeList(Object left, Object right) {
722        if (left instanceof Object[]) {
723            for (Object l : ((Object[]) left)) {
724                Boolean eq = eq(l, right);
725                if (TRUE.equals(eq)) {
726                    return TRUE;
727                }
728            }
729            return FALSE;
730        } else {
731            return eq(left, right);
732        }
733    }
734
735    // if list, use EXIST (SELECT 1 FROM left WHERE left.item IN right)
736    protected Boolean inMaybeList(Object left, List<Object> right) {
737        if (left instanceof Object[]) {
738            for (Object l : ((Object[]) left)) {
739                Boolean in = in(l, right);
740                if (TRUE.equals(in)) {
741                    return TRUE;
742                }
743            }
744            return FALSE;
745        } else {
746            return in(left, right);
747        }
748    }
749
750    protected Boolean likeMaybeList(Object left, String right, boolean positive, boolean caseInsensitive) {
751        if (left instanceof Object[]) {
752            for (Object l : ((Object[]) left)) {
753                Boolean like = like(l, right, caseInsensitive);
754                if (TRUE.equals(like)) {
755                    return Boolean.valueOf(positive);
756                }
757            }
758            return Boolean.valueOf(!positive);
759        } else {
760            Boolean like = like(left, right, caseInsensitive);
761            return positive ? like : not(like);
762        }
763    }
764
765    /**
766     * Matches the mixin types against a list of values.
767     * <p>
768     * Used for:
769     * <ul>
770     * <li>ecm:mixinTypes = 'foo'
771     * <li>ecm:mixinTypes != 'foo'
772     * <li>ecm:mixinTypes IN ('foo', 'bar')
773     * <li>ecm:mixinTypes NOT IN ('foo', 'bar')
774     * </ul>
775     *
776     * @param mixins the mixin(s) to match
777     * @param include {@code true} for = and IN
778     * @since 7.4
779     */
780    public abstract Boolean walkMixinTypes(List<String> mixins, boolean include);
781
782    /*
783     * ----- simple parsing, don't try to be exhaustive -----
784     */
785
786    private static final Pattern WORD_PATTERN = Pattern.compile("[\\s\\p{Punct}]+");
787
788    private static final String UNACCENTED = "aaaaaaaceeeeiiii\u00f0nooooo\u00f7ouuuuy\u00fey";
789
790    private static final String STOP_WORDS_STR = "a an are and as at be by for from how " //
791            + "i in is it of on or that the this to was what when where who will with " //
792            + "car donc est il ils je la le les mais ni nous or ou pour tu un une vous " //
793            + "www com net org";
794
795    private static final Set<String> STOP_WORDS = new HashSet<>(Arrays.asList(StringUtils.split(STOP_WORDS_STR, ' ')));
796
797    /**
798     * Checks if the fulltext combination of string1 and string2 matches the query expression.
799     */
800    protected static Boolean fulltext(String string1, String string2, String queryString) {
801        if (queryString == null || (string1 == null && string2 == null)) {
802            return null;
803        }
804        // query
805        List<String> query = new ArrayList<>();
806        String phrase = null;
807        int phraseWordCount = 1;
808        int maxPhraseWordCount = 1; // maximum number of words in a phrase
809        for (String word : StringUtils.split(queryString.toLowerCase(), ' ')) {
810            if (WORD_PATTERN.matcher(word).matches()) {
811                continue;
812            }
813            if (phrase != null) {
814                if (word.endsWith(PHRASE_QUOTE)) {
815                    phrase += " " + word.substring(0, word.length() - 1);
816                    query.add(phrase);
817                    phraseWordCount++;
818                    if (maxPhraseWordCount < phraseWordCount) {
819                        maxPhraseWordCount = phraseWordCount;
820                    }
821                    phrase = null;
822                    phraseWordCount = 1;
823                } else {
824                    phrase += " " + word;
825                    phraseWordCount++;
826                }
827            } else {
828                if (word.startsWith(PHRASE_QUOTE)) {
829                    phrase = word.substring(1);
830                } else if (word.startsWith(NEG_PHRASE_QUOTE)) {
831                    phrase = "-" + word.substring(2);
832                } else {
833                    if (word.startsWith("+")) {
834                        word = word.substring(1);
835                    }
836                    query.add(word);
837                }
838            }
839        }
840        if (query.isEmpty()) {
841            return FALSE;
842        }
843        // fulltext
844        Set<String> fulltext = new HashSet<>();
845        fulltext.addAll(parseFullText(string1, maxPhraseWordCount));
846        fulltext.addAll(parseFullText(string2, maxPhraseWordCount));
847
848        return Boolean.valueOf(fulltext(fulltext, query));
849    }
850
851    private static Set<String> parseFullText(String string, int phraseSize) {
852        if (string == null) {
853            return Collections.emptySet();
854        }
855        Set<String> set = new HashSet<>();
856        Deque<String> phraseWords = new LinkedList<>();
857        for (String word : WORD_PATTERN.split(string)) {
858            word = parseWord(word);
859            if (word != null) {
860                word = word.toLowerCase();
861                set.add(word);
862                if (phraseSize > 1) {
863                    phraseWords.addLast(word);
864                    if (phraseWords.size() > 1) {
865                        if (phraseWords.size() > phraseSize) {
866                            phraseWords.removeFirst();
867                        }
868                        addPhraseWords(set, phraseWords);
869                    }
870                }
871            }
872        }
873        while (phraseWords.size() > 2) {
874            phraseWords.removeFirst();
875            addPhraseWords(set, phraseWords);
876        }
877        return set;
878    }
879
880    /**
881     * Adds to the set all the sub-phrases from the start of the phraseWords.
882     */
883    private static void addPhraseWords(Set<String> set, Deque<String> phraseWords) {
884        String[] array = phraseWords.toArray(new String[0]);
885        for (int len = 2; len <= array.length; len++) {
886            String phrase = StringUtils.join(array, ' ', 0, len);
887            set.add(phrase);
888        }
889    }
890
891    private static String parseWord(String string) {
892        int len = string.length();
893        if (len < 3) {
894            return null;
895        }
896        StringBuilder buf = new StringBuilder(len);
897        for (int i = 0; i < len; i++) {
898            char c = Character.toLowerCase(string.charAt(i));
899            if (c == '\u00e6') {
900                buf.append("ae");
901            } else if (c >= '\u00e0' && c <= '\u00ff') {
902                buf.append(UNACCENTED.charAt((c) - 0xe0));
903            } else if (c == '\u0153') {
904                buf.append("oe");
905            } else {
906                buf.append(c);
907            }
908        }
909        // simple heuristic to remove plurals
910        int l = buf.length();
911        if (l > 3 && buf.charAt(l - 1) == 's') {
912            buf.setLength(l - 1);
913        }
914        String word = buf.toString();
915        if (STOP_WORDS.contains(word)) {
916            return null;
917        }
918        return word;
919    }
920
921    // matches "foo OR bar baz" as "foo OR (bar AND baz)"
922    protected static boolean fulltext(Set<String> fulltext, List<String> query) {
923        boolean andMatch = true;
924        for (PeekingIterator<String> it = Iterators.peekingIterator(query.iterator()); it.hasNext();) {
925            String word = it.next();
926            boolean match;
927            if (word.endsWith("*") || word.endsWith("%")) {
928                // prefix match
929                match = false;
930                String prefix = word.substring(0, word.length() - 2);
931                for (String candidate : fulltext) {
932                    if (candidate.startsWith(prefix)) {
933                        match = true;
934                        break;
935                    }
936                }
937            } else {
938                if (word.startsWith("-")) {
939                    word = word.substring(1);//
940                    match = !fulltext.contains(word);
941                } else {
942                    match = fulltext.contains(word);
943                }
944            }
945            if (!match) {
946                andMatch = false;
947            }
948            if (it.hasNext() && it.peek().equals(OR)) {
949                // end of AND group
950                // swallow OR
951                it.next();
952                // return if the previous AND group matched
953                if (andMatch) {
954                    return true;
955                }
956                // else start next AND group
957                andMatch = true;
958            }
959        }
960        return andMatch;
961    }
962
963    // matches "foo OR bar baz" as "(foo OR bar) AND baz"
964    protected static boolean fulltext1(Set<String> fulltext, List<String> query) {
965        boolean inOr = false; // if we're in a OR group
966        boolean orMatch = false; // value of the OR group
967        for (PeekingIterator<String> it = Iterators.peekingIterator(query.iterator()); it.hasNext();) {
968            String word = it.next();
969            if (it.hasNext() && it.peek().equals(OR)) {
970                inOr = true;
971                orMatch = false;
972            }
973            boolean match;
974            if (word.endsWith("*") || word.endsWith("%")) {
975                // prefix match
976                match = false;
977                String prefix = word.substring(0, word.length() - 2);
978                for (String candidate : fulltext) {
979                    if (candidate.startsWith(prefix)) {
980                        match = true;
981                        break;
982                    }
983                }
984            } else {
985                if (word.startsWith("-")) {
986                    word = word.substring(1);//
987                    match = !fulltext.contains(word);
988                } else {
989                    match = fulltext.contains(word);
990                }
991            }
992            if (inOr) {
993                if (match) {
994                    orMatch = true;
995                }
996                if (it.hasNext() && it.peek().equals(OR)) {
997                    // swallow OR and keep going in OR group
998                    it.next();
999                    continue;
1000                }
1001                // finish OR group
1002                match = orMatch;
1003                inOr = false;
1004            }
1005            if (!match) {
1006                return false;
1007            }
1008        }
1009        if (inOr) {
1010            // trailing OR, ignore and finish previous group
1011            if (!orMatch) {
1012                return false;
1013            }
1014        }
1015        return true;
1016    }
1017
1018}